基于最小跳数路径的分布式低轨卫星星间路由算法

王子涵 ,  吴迪 ,  胡涛

信息工程大学学报 ›› 2025, Vol. 26 ›› Issue (04) : 408 -414.

PDF (2307KB)
信息工程大学学报 ›› 2025, Vol. 26 ›› Issue (04) : 408 -414. DOI: 10.3969/j.issn.1671-0673.2025.04.005
信息与通信工程

基于最小跳数路径的分布式低轨卫星星间路由算法

作者信息 +

Distributed Low-Orbit Satellite Inter-Satellite Routing Algorithm Based on Minimum Hop Number Path

Author information +
文章历史 +
PDF (2361K)

摘要

针对低地球轨道(LEO)卫星网络出现负载拥塞导致数据传输时延增加的问题,提出一种基于最小跳数路径的分布式星间路由算法。该算法首先利用低轨卫星星座分布对称且规则的特点建立网络拓扑模型,并以最小转发跳数作为路由的必要条件;其次,通过最大化剩余转发区域的路径数量,降低节点拥塞的概率;最后,读取相邻卫星节点的负载状态,以提高数据到达率。仿真实验表明,所提算法在不同数据传输速率下相较于最短时延路径算法(MDP)和流量平均分配路径算法(ATDP)能更有效地降低端到端时延和丢包率,并在较高传输速率下更好地避免网络拥塞。该算法复杂度低、易于实现,为分布式星间路由研究提供了新的方法。

Abstract

A distributed inter-satellite routing algorithm based on the minimum hop path is proposed to address the issue of increased data transmission delay caused by load congestion in Low-Earth orbit (LEO) satellite networks. Firstly, the network topology model is established by leveraging the symmetrical and regular distribution characteristics of LEO satellite constellations, with the minimum number of forwarding hops set as a necessary routing condition. Secondly, the probability of node congestion is reduced by maximizing the number of paths in the remaining forwarding area. Finally, the load status of neighboring satellite nodes is read to improve data delivery rates. Simulation results demonstrate that, under different data transmission rates, the proposed algorithm effectively reduces end-to-end delay and packet loss rate compared to the minimum delay path (MDP) algorithm and the average traffic distribution path (ATDP) algorithm. Moreover, it better prevents network congestion at higher transmission rates. With low complexity and ease of implementation, this algorithm provides a novel approach for distributed inter-satellite routing research.

Graphical abstract

关键词

低轨卫星通信 / 网络拓扑 / 拥塞避免 / 分布式路由算法 / 星间路由算法

Key words

Low-Earth orbit satellite communication / network topology / congestion avoidance / distributed routing algorithm / inter-satellite routing algorithm

引用本文

引用格式 ▾
王子涵,吴迪,胡涛. 基于最小跳数路径的分布式低轨卫星星间路由算法[J]. 信息工程大学学报, 2025, 26(04): 408-414 DOI:10.3969/j.issn.1671-0673.2025.04.005

登录浏览全文

4963

注册一个新账户 忘记密码

0 引言

卫星网络[1]作为空间信息网络的关键组成部分,具有覆盖全球和稳定性高的优点[2],对于高度依赖互联网的现代社会发展具有重要意义。其中,低轨卫星网络因其传播时延小、部署灵活、系统可靠性高等优点[3],相较于其他卫星网络具有更高的研究和应用价值[4]。然而,随着全球业务量的日益增加,低轨卫星通信网络中会出现数据流量拥塞的情况[5-6]。目前,已有部分学者针对避免网络拥塞进行研究。例如,文献[6]提出了一种基于信念消息重要性散度的路由算法,通过融合卫星性能属性,优化低轨卫星网络中的路由决策,显著提高了吞吐量并减少了延迟和丢包率。文献[7]提出了一种基于跳数的分布式背压路由协议,通过计算链路权重和限制传播区域,实现低轨卫星网络的负载均衡和高效路由,从而提高网络吞吐量并降低时延。文献[8]提出了一种基于多属性的低轨卫星网络多路径路由算法,通过自适应调整传输成本模型和分布式路由选择,提升了在网络负载和故障情况下的性能和负载均衡能力。文献[9]设计了一种混合星间链路和CPU集中调度方法,通过改进的Q-routing算法优化低轨卫星通信网络的路由,旨在提升链路容量和计算资源利用率,并减少传输和处理延迟。文献[10]提出了一种快速收敛的强化学习卫星路由算法,以应对低轨卫星网络中频繁的拓扑变化,通过快速感知网络状态和自适应调整转发策略,提升了平均时延、数据包到达率和网络负载均衡性能。文献[11]针对传统路由规划算法未能考虑时延变化和计算量过大的问题,提出了一种最优时延路由算法,该算法基于时延排队图形评估和审查技术和最小路径集对卫星网络进行建模,筛选出所有有效的候选路径,提升了处理不确定时延信息能力。

尽管现有研究提出了多种方法来优化低轨卫星网络的路由性能和负载均衡,但这些方法仍存在一些不足。首先,许多算法在面对低轨卫星网络中频繁变化的拓扑环境时响应较慢,缺乏足够的自适应能力。其次,部分算法的复杂度较高,可能在实际应用中难以实现,特别是在资源受限或实时性要求高的应用场景下,计算开销成为一个不可忽视的瓶颈。

针对这些问题,本文提出了一种基于最小跳数路径的分布式低轨卫星星间路由算法,该算法通过提高数据包传输路径的生存概率,来有效降低数据流量增加时产生的拥塞问题。与传统路由算法不同,所提算法不仅考虑路径的最小跳数,还结合了网络负载等多维度因素,从而实现更加高效和灵活的路由决策。通过引入动态拓扑适应机制,算法能够实时感知网络状态的变化,动态调整路径选择,有效应对低轨卫星网络中的拓扑变化。与此同时,算法通过优化路径选择,优先选择具有较高生存概率的路径,从而减少了网络拥塞带来的丢包风险,并有效降低了传输时延。仿真结果表明,所提算法在不同数据传输速率下,相较于最短时延路径算法(Minimum Delay Path, MDP)和流量平均分配路径算法(Average Traffic Distribution Path, ATDP),能够显著降低端到端时延和丢包率,并在较高传输速率下展现出更优的拥塞避免能力。同时,作为一种最小跳数路由算法,所提算法保证了较低的信令开销,具备了在大规模低轨卫星网络中实际应用的优势。

1 低轨卫星星座网络模型构建

本文采用单层低轨卫星网络模型,星座构型符合Walker倾斜轨道星座[12-13],即在赤道面上均匀分布N个倾角相同且不为90°的倾斜轨道,每个轨道面上均匀分布M颗卫星,相邻轨道卫星间相位差相同且保持不变,其网络模型如图1所示。星座内卫星间通过建立星间链路进行连通[14],考虑到实际开销与复杂度,本文采用在Walker中常见的星间链路建立方式,即每颗卫星与其相邻4颗卫星建立链接[15],这其中包括相邻的2颗同轨卫星和2颗异轨卫星,星间链路连接情况如图2所示。

Walker倾斜轨道星座具有高度的规则性和对称性,其星座结构可近似看成网状结构[16-18],记第N个轨道面上的第M颗卫星为SN, M[19],其星下点经纬度坐标为latN, M, lonN, M [20]。由于卫星相对于地面高速运动,星座网络拓扑结构处于动态变化中,为避免拓扑动态性对路由计算造成的影响,采用虚拟节点法[21]屏蔽拓扑动态性。将地球表面区域划分为N×M个逻辑区域,每颗卫星与其星下点所在的逻辑区域一一映射,在计算路由时,认为每颗卫星与其对应的逻辑区域相对静止。

2 路由算法设计

提出一种基于最小跳数的低轨卫星网络路由算法,以最小跳数为路径开销条件,并最大化可选最小跳数路径数量,降低拥塞概率,提高传输效率。算法通过计算路径选择域和生存概率优化下一跳选择,减少延迟与拥塞。

2.1 最小跳数路径与路径选择域

在起始节点与目的节点之间无法建立直接星间链路的情况下,必须通过多跳转发路径实现数据传输。不同路径的跳数各不相同,每一次数据包转发都会消耗中继卫星节点的资源,增加网络拥塞的可能性,并延长数据传输的处理时间。因此,转发路径的跳数越少越好。本文提出的路由算法将跳数作为路径开销的主要评价标准,并以最小跳数作为选择最优路径的必要条件。

在起始节点与目的节点之间通常存在多条可选路径。跳数最少的路径集合称为路径选择域。在卫星网络的虚拟拓扑中,路径选择域通常对应于从源节点到目的节点的最小矩形区域,如图3所示。

2.2 路径生存概率

由上一节可知,最小条数路径包含在由起始卫星节点和目的卫星节点确定的矩形网格区域内,记其两个方向上包含的边的个数分别为ΔN和ΔM,则由起始卫星到目的卫星转发可选择的最小跳数路径的个数为

PΔN, ΔM=CΔN+ΔMΔN=ΔN+ΔM!ΔN!ΔM!

可以看出,当ΔN和ΔM均大于0时,数据包传输可选择的最小跳数路径大于1条。在分布式路由算法中,由于卫星无法直接获取与非相邻节点或网络的拥塞状态,数据包的路径选择将更多依赖于路径选择域中的可选路径数量及其生存概率。因此,生存概率在评估路径选择的有效性中起到了关键作用。

在路径选择过程中,生存概率是指数据包在多跳转发路径中成功到达目的节点的概率。假设数据包从源节点到目的节点有多个最小跳数路径可选,记路径选择域中包含的最小跳数路径个数为PΔN,ΔM,则生存概率可以定义为数据包在下一跳转发时仍然能够选择最优路径的可能性。生存概率与剩余路径选择域中可选路径数量成正比,即:

Psurvival∝PΔN,ΔM

路径选择域中的最小跳数路径越多,生存概率越高,说明数据包有更多的路径选择余地来应对潜在的拥塞问题,从而降低了传输失败的风险。

2.3 路由转发策略

基于上一节的观点,数据包在进行数据转发时,在下一跳卫星的选择上应保持剩余路径选择域中包含的最小跳数路径个数尽可能多。如图4所示,对于一个ΔN×ΔM的路径选择域,数据包从起始卫星节点经过一跳卫星转发后,剩余路径选择域的规格为ΔN×ΔM-1或ΔN-1×ΔM,即当沿同轨方向转发时,剩余路径选择域为ΔN×ΔM-1维网格构型;当沿异轨方向转发时,剩余路径选择域为ΔN-1×ΔM维网格构型。

当ΔN>0且ΔM>0时,对于ΔN×ΔM-1维网络,其包含的最小跳数路径个数为

PΔN, ΔM-1=CΔN+ΔM-1ΔN=                  ΔN+ΔM-1!ΔN!ΔM-1!=                  ΔN+ΔM-1!ΔN!ΔM!⋅ΔM

对于ΔN-1×ΔM维网络,其包含的最小跳数路径个数为

PΔN-1, ΔM=CΔN-1+ΔMΔN-1=                 ΔN-1+ΔM!ΔN-1!ΔM!=                 ΔN-1+ΔM!ΔN!ΔM!⋅ΔN

由以上两式可以看出,当ΔN<ΔM时,PΔN-1, ΔM<PΔN, ΔM-1,此时数据包沿异轨方向进行下一跳转发所得到的剩余路径选择域中包含的最小跳数路径个数较多,数据包的剩余路径生存概率更大。反之当ΔN>ΔM时,PΔN-1,ΔM>PΔN,ΔM-1,此时数据包沿同轨方向进行下一跳转发所得到的剩余路径选择域中包含的最小跳数路径个数较多,数据包的剩余路径生存概率更大。

考虑到实际情况中,卫星节点出现拥塞的情况较为常见,因此为了尽可能减小丢包率,本文算法设计了一个自适应调整机制以应对低轨卫星网络中频繁的拓扑变化。在每次路径选择时,卫星节点会周期性地感知其邻近卫星的链路状态(包括链路延迟、负载情况等),并根据动态变化的网络状态实时调整下一跳节点的选择。特别是在路径选择域的更新过程中,算法不仅考虑最小跳数路径,还对邻近节点的负载状态和链路质量进行评估。当某一方向上的链路出现拥塞时,算法会优先选择未拥塞的方向,从而有效降低了传输时延和丢包率。

对于ΔN×ΔM维构型的路径选择域,提出的数据包选择下一跳节点的算法流程图如图5所示。

通过这种动态调整机制,算法能够在低轨卫星网络中频繁的拓扑变化下保持高效的数据传输性能,并最大程度地避免因拥塞导致的数据包丢失。

该算法选择下一跳卫星节点准则如下。

算法1 下一跳节点选择

输入:当前节点坐标(N1, M1),目的节点坐标(N2, M2)

输出:下一跳卫星节点(N1*, M1*)

1.计算ΔN和ΔM

2.如果ΔN==0且ΔM==0:

输出“数据包到达目的卫星节点,转发结束”

返回(N1, M1)

3.如果ΔN或ΔM中只有一个为0

如果下一跳卫星不处于拥塞状态:

选择该唯一确定的下一跳卫星节点(N1*, M1*) 进行转发

返回(N1*,M1*)

4.如果ΔN!=0且ΔM!=0

判断数据包两个备选转发方向的下一颗卫星是否 处于拥塞状态

如果一个方向上出现拥塞,另一个方向未出现:

选择未出现拥塞的方向进行转发

返回(N1*, M1*)

如果两个方向均出现拥塞:

比较ΔN与ΔM的大小

如果ΔN<ΔM:

选择同轨方向的下一跳卫星节点(N1*, M1*) 进行数据转发

否则如果ΔN>ΔM:

选择异轨方向的下一跳卫星节点(N1*, M1*)进行数据转发

否则(ΔN==ΔM):

比较两方向上下一跳卫星的拥塞程度

选择拥塞程度较轻的卫星节点(N1*, M1*) 进行转发

返回(N1*, M1*)

5. 如果所有备选方向的下一跳卫星均处于拥塞状态

输出“该数据包终止转发,计入数据丢失”

ΔN和ΔM可由起始卫星和目的卫星的节点编号SN1,M1和SN2,M2确定,计算方式如下:

ΔN=minN1-N2, N-N1-N2;ΔM=minM1-M2, M-M1-M2.

该算法算例示意如图6所示(无拥塞条件下)。

2.4 算法复杂度分析

本文提出的基于最小跳数路径的分布式低轨卫星网络星间路由算法,其计算复杂度主要体现在路径选择域的构建和路径生存概率的计算两个方面。

假设卫星星座网络中的卫星节点总数为N×M,每个卫星节点的相邻节点数量为k(一般情况下k=4,即每个节点与其相邻的4个节点保持连接)。在路由计算过程中,算法需要遍历所有可能的路径来构建路径选择域。由于每个卫星节点最多需要访问其相邻的4个节点,因此路径选择域的构建复杂度为O(N×M),即算法在构建路径选择域时需要遍历所有卫星节点,复杂度与网络规模成线性关系。

路径生存概率的计算主要基于路径选择域中剩余最小跳数路径的数量。假设在每一步转发过程中,剩余路径选择域中包含的最小跳数路径的数量为PΔN,ΔM,则每一次转发时,算法需要计算所有剩余路径的生存概率。基于之前对路径生存概率的分析,可以得出,本文算法对于路径生存概率方面的算法复杂度为O(ΔN+ΔM)。

综合考虑路径选择域的构建和路径生存概率的计算,本文算法的总体时间复杂度为O(N×M+ΔN+ΔM),忽略掉低阶后结果为O(N×M)。为了验证本文算法的复杂度优势,现将其与其他常见的路由算法即MDP、ATDP和基于星间链路状态的路由算法(Routing Algorithm Based on Inter-Satellite Link State, RA-ISLS)进行对比,如表1所示。

相比之下,所提算法由于在路径选择过程中通过最小跳数路径的筛选大大减少了计算量,整体复杂度为O(N×M),与复杂度较低的最短时延路径算法和流量平均分配路径算法保持在相同的水平,适合在资源受限的大规模低轨卫星网络中实现。

3 仿真验证

3.1 性能评价指标

1)时延分布。时延分布是评估卫星网络路由在进行端到端数据传输时,不同时刻发送的数据包所经历的传输时延的一个关键评价指标。其包括每颗卫星发送和处理数据的时延,排队时延以及链路传播时延。它通过对数据包从发送端到接收端所需时间的统计和分析,反映了网络传输的稳定性和效率如下式:

D=DT+DP+DQ+Dprocess

式中:D为数据包在传输过程中经历的端到端总时延;DT为数据发送时延;DP为链路传播时延;DQ为排队时延;Dprocess为数据包处理时延。

2)平均时延。端到端平均时延是数据包从源端产生到路由到达目的卫星节点的时间间隔的平均值。

Davg=1n∑i=1nDi

式中:Davg为在某一数据率下的端到端平均时延;Di为每个数据包历经的传输总时延;n为数据包个数。

3)丢包率。由于网络拥塞,数据包在卫星网络传输过程中会遇到缓存溢出的现象。此时,数据包将丢失。丢包数与网络中传输的数据总数之比即为丢包率。

η=nlossnsend

式中:η为丢包率;nloss为在传输过程中丢失的数据包个数;nsend为发送端发送的数据包总数。

3.2 仿真结果与分析

本文采用MDP、ATDP和RA-ISLS作为对照组实验,其中前两种算法与本文提出的最小跳数路径选择域优化算法均为分布式路由算法。

1) MDP。在进行路由决策时,卫星节点不考虑负载因素。当数据包到达时,根据当前卫星和目的卫星的经纬度选择下一跳节点进行路由,最短时延路径算法采用固定方向策略。

2) ATDP。卫星节点在路由决策时不考虑负载条件。当数据包到达时,卫星从路由算法计算出的两个备选方向中随机选择一个作为下一跳节点来转发数据包,这样可以避免某些链路上的传输拥塞,从而增强网络的路由能力。

3) RA-ISLS。基于星间链路状态的路由算法是一种专门用于低轨道卫星网络中动态路由决策的算法。其核心思想是通过实时感知卫星间链路状态的变化,优化路由选择,从而提升数据传输的效率和网络的稳定性。

仿真使用的部分参数如表2所示。

1)时延分布。图7展示了不同数据传输速率下的端到端时延分布情况。在80 MB/s时,4种算法的时延分布曲线相似且稳定,表明无显著拥塞,RA-ISLS通过链路状态动态调整排队时延的权重,整体时延较高;在100 MB/s时,MDP、ATDP与RA-ISLS的时延显著上升,而本文算法的时延仍然保持稳定,显示了本文算法在较高传输速率下的优越性,能有效避免拥塞;在120 MB/s时,其他3种算法的时延继续上升,而本文算法的时延虽有所增加但幅度较小,进一步体现了其在高负载下的优势;在140 MB/s时,4种算法的时延曲线均明显上升,表明在极高传输速率下,各算法均出现拥塞,但本文算法仍表现出相对较小的时延增幅,展现出其在拥塞控制方面的潜力。

2)平均时延。图8展示了4种算法的平均端到端时延。在80~140 MB/s范围内,本文算法的平均时延显著低于MDP和RA-ISLS,略低于ATDP,表明其在降低传输时延和避免网络拥塞方面具有明显优势。即使在较高的传输速率下,本文算法仍能保持相对较低的平均时延,进一步证明了其在高负载条件下的有效性和稳定性。

3)丢包率。图9展示了4种算法的丢包率。随着数据传输速率的增加,4种算法的丢包率均有所上升,但本文算法在各传输速率下的丢包率始终低于MDP与ATDP,与RA-ISLS接近。表明本文算法在高数据传输速率下能够有效减少数据包丢失,保证数据包的成功传输,进一步凸显了其在拥塞控制和数据传输可靠性方面的优越性。

4 结束语

随着全球互联网服务需求的不断增长,低轨卫星网络面临的负载拥塞问题愈发严重,导致数据传输时延增加和丢包率上升。针对这一挑战,提出了一种基于最小跳数路径的分布式低轨卫星网络星间路由算法。该算法利用低轨卫星星座的对称和规则分布特点,通过优化路径选择,并监测相邻卫星节点的负载状态来提升数据传输的可靠性和效率。所提算法通过最大化剩余转发区域的路径数量,降低了节点拥塞的概率。仿真实验结果显示,该算法在不同数据传输速率下,更显著地降低了端到端时延和丢包率,在较高传输速率下表现尤为出色。此外,该算法复杂度低,易于实现,具有实际应用潜力。

参考文献

[1]

吴巍.天地一体化信息网络发展综述[J].天地一体化信息网络,2020,1(1):1-16.

[2]

李贺武,吴茜,徐恪,等.天地一体化网络研究进展与趋势[J].科技导报,2016,34(14):95-106.

[3]

王鹏,张佳鑫,张兴,等.低轨卫星智能多接入边缘计算网络:需求、架构、机遇与挑战[J].移动通信,2021,45(5):35-46.

[4]

甘仲民.卫星通信技术的新发展(Ⅰ)[J].数字通信世界,2013(9):12-17.

[5]

HAN Z Z, XU C, ZHAO G F, et al. Time-varying topology model for dynamic routing in LEO satellite constellation networks[J]. IEEE Transactions on Vehicular Technology, 2023,72(3):3440-3454.

[6]

WANG Z H, LI J Z, CHEN H Q, et al. A novel divergence measure-based routing algorithm in large-scale satellite networks[J]. IET Communications,2021,15(5):708-722.

[7]

韩驰,熊伟,于荣欢,等.基于跳数背压策略的低轨卫星网络负载均衡路由[J].系统工程与电子技术,2024,46(10):3557-3566.

[8]

孙正阳,杜晔,李桂领,等.链路及节点多属性融合的低轨卫星网络路由算法[J].计算机工程与应用,2024,60(18):266-274.

[9]

ZHENG F, WANG C, ZHOU Z, et al. LEO laser microwave hybrid inter-satellite routing strategy based on modified Q-routing algorithm[J]. EURASIP Journal on Wireless Communications and Networking, 2022(1):No.36.

[10]

DING Z L, LIU H J, TIAN F, et al. Fast-convergence reinforcement learning for routing in LEO satellite networks[J]. Sensors, 2023,23(11):No.5180.

[11]

GENG S Y, LIU S F, FANG Z G, et al. An optimal delay routing algorithm considering delay variation in the LEO satellite communication network[J]. Computer Networks, 2020,173:No.107166.

[12]

范丽,张育林.Walker星座星间链路构建准则及优化设计研究[J].飞行力学,2007,25(2):93-96.

[13]

WALKER J G. Some circular orbit patterns providing continuous whole earth coverage[J]. Journal of the British Interplanetary Society, 1971,24:369-384.

[14]

况鸿凤.低轨大星座系统路由策略研究[D].成都:电子科技大学,2018:1-75.

[15]

张悦.低轨卫星网络路由算法研究[D].西安:西安电子科技大学,2019:1-97.

[16]

WOOD L, CLERGET A, ANDRIKOPOULOS I, et al. IP routing issues in satellite constellation networks[J]. International Journal of Satellite Communications, 2001,19(1):69-92.

[17]

CHEN C, EKICI E. A routing protocol for hierarchical LEO/MEO satellite IP networks[J]. Wireless Networks, 2005,11(4):507-521.

[18]

EKICI E, AKYILDIZ I F, BENDER M D. A distributed routing algorithm for datagram traffic in LEO satellite networks[J]. IEEE/ACM Transactions on Networking, 2001,9(2):137-147.

[19]

LIU J, LUO R Z, HUANG T, et al. A load balancing routing strategy for LEO satellite network[J]. IEEE Access, 2020,8:155136-155144.

[20]

冯玺宝.多层卫星网络QoS路由协议研究[D].哈尔滨:哈尔滨工业大学,2016:1-84.

[21]

卢勇,赵有健,孙富春,等.卫星网络路由技术[J].软件学报,2014,25(5):1085-1100.

AI Summary AI Mindmap
PDF (2307KB)

840

访问

0

被引

详细

导航
相关文章

AI思维导图

/

〈 〉