CN112333109B - Ant colony optimization-based load balancing routing method in low-orbit satellite network - Google Patents
Ant colony optimization-based load balancing routing method in low-orbit satellite networkDownload PDFInfo
- Publication number
- CN112333109B CN112333109BCN202011284624.2ACN202011284624ACN112333109BCN 112333109 BCN112333109 BCN 112333109BCN 202011284624 ACN202011284624 ACN 202011284624ACN 112333109 BCN112333109 BCN 112333109B
- Authority
- CN
- China
- Prior art keywords
- satellite
- link
- routing
- pheromone
- path
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Active
Links
- 238000000034methodMethods0.000titleclaimsabstractdescription27
- 238000005457optimizationMethods0.000titleclaimsabstractdescription18
- 239000003016pheromoneSubstances0.000claimsabstractdescription49
- 241000257303HymenopteraSpecies0.000claimsabstractdescription22
- 238000004364calculation methodMethods0.000claimsdescription5
- 238000011217control strategyMethods0.000claimsdescription5
- 230000005540biological transmissionEffects0.000claimsdescription4
- 238000012546transferMethods0.000claimsdescription3
- 108010046685Rho FactorProteins0.000claims1
- 238000004891communicationMethods0.000abstractdescription3
- 238000004422calculation algorithmMethods0.000description16
- 229910052741iridiumInorganic materials0.000description7
- GKOZUEZYRPOHIO-UHFFFAOYSA-Niridium atomChemical compound[Ir]GKOZUEZYRPOHIO-UHFFFAOYSA-N0.000description7
- 238000004088simulationMethods0.000description7
- 238000010586diagramMethods0.000description3
- 230000000737periodic effectEffects0.000description3
- 230000007423decreaseEffects0.000description2
- 238000012986modificationMethods0.000description2
- 230000004048modificationEffects0.000description2
- 238000012545processingMethods0.000description2
- 230000003068static effectEffects0.000description2
- 230000003247decreasing effectEffects0.000description1
- 238000013461designMethods0.000description1
- 230000000694effectsEffects0.000description1
- 230000008676importEffects0.000description1
- 238000009434installationMethods0.000description1
- 230000003993interactionEffects0.000description1
- 239000011159matrix materialSubstances0.000description1
- 230000008569processEffects0.000description1
- 238000000275quality assuranceMethods0.000description1
- 238000012216screeningMethods0.000description1
- 230000008054signal transmissionEffects0.000description1
- 238000006467substitution reactionMethods0.000description1
- 230000007704transitionEffects0.000description1
Images
Classifications
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
- H04L47/00—Traffic control in data switching networks
- H04L47/10—Flow control; Congestion control
- H04L47/12—Avoiding congestion; Recovering from congestion
- H04L47/125—Avoiding congestion; Recovering from congestion by balancing the load, e.g. traffic engineering
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04B—TRANSMISSION
- H04B7/00—Radio transmission systems, i.e. using radiation field
- H04B7/14—Relay systems
- H04B7/15—Active relay systems
- H04B7/185—Space-based or airborne stations; Stations for satellite systems
Landscapes
- Engineering & Computer Science (AREA)
- Computer Networks & Wireless Communication (AREA)
- Signal Processing (AREA)
- Physics & Mathematics (AREA)
- Astronomy & Astrophysics (AREA)
- Aviation & Aerospace Engineering (AREA)
- General Physics & Mathematics (AREA)
- Data Exchanges In Wide-Area Networks (AREA)
- Radio Relay Systems (AREA)
Abstract
Description
Translated fromChinese技术领域technical field
本发明属于卫星通信技术领域，涉及一种低轨卫星网络中基于蚁群优化的负载均衡路由方法。The invention belongs to the technical field of satellite communication, and relates to a load balancing routing method based on ant colony optimization in a low-orbit satellite network.
背景技术Background technique
由于低地球轨道(Low Earth Orbit,LEO)卫星高度一般为1000km左右，相较于20000km以上高度的中高轨卫星，低轨卫星信号传输路径更短，信号时延和功率损耗更小，正日益成为卫星通信领域的热门话题。但是，除了轨道高度较低之外，LEO卫星网络还具有链路切换频繁和高动态拓扑变化的特点，路由计算开销会大大占用有限的星上计算资源。此外，由于星座规模大，地面网络的路由协议在拓扑变化后难以快速收敛，导致丢包率增加，吞吐量下降。因此，适用于卫星网络的路由协议应该不同于现有的用于地面网络的协议，必须针对卫星网络的结构特点研究和设计新的路由算法。Since the altitude of Low Earth Orbit (LEO) satellites is generally about 1000km, compared with medium and high orbit satellites with altitudes above 20,000km, the signal transmission path of LEO satellites is shorter, and the signal delay and power loss are smaller. A hot topic in satellite communications. However, in addition to the low orbit height, the LEO satellite network also has the characteristics of frequent link switching and high dynamic topology changes, and the routing calculation overhead will greatly occupy the limited on-board computing resources. In addition, due to the large scale of the constellation, it is difficult for the routing protocol of the terrestrial network to converge quickly after topology changes, resulting in increased packet loss rate and decreased throughput. Therefore, the routing protocol suitable for satellite networks should be different from the existing protocols for terrestrial networks, and new routing algorithms must be researched and designed according to the structural characteristics of satellite networks.
目前最常用的星上路由选择算法依然是基于虚拟拓扑控制策略下的连续快照路由算法，该算法不仅在计算上很复杂，需要计算卫星位置和最短路径。而且，这些预先计算好的路由不具备动态处理突发情况的能力，大大降低星间路由的有效性，也不能提供服务质量的保证。At present, the most commonly used on-board routing algorithm is still the continuous snapshot routing algorithm based on the virtual topology control strategy. This algorithm is not only computationally complex, but also needs to calculate the satellite position and the shortest path. Moreover, these pre-calculated routes do not have the ability to dynamically handle emergencies, which greatly reduces the effectiveness of inter-satellite routing and cannot provide service quality assurance.
发明内容SUMMARY OF THE INVENTION
本发明的目的在于提供一种适用于低轨卫星网络的基于蚁群优化的负载均衡路由策略。该路由策略首先利用低轨卫星轨道的周期特性以及星座结构的可预测特性，采用虚拟拓扑的控制策略得到一个卫星系统运行周期内的连续静态拓扑快照。然后，利用星间链路距离、时延抖动与拥塞程度计算星间链路的转移概率，每次选取概率最大的链路转发数据包，同时根据局部信息素更新规则更新已选的星间链路的信息素。当任意一只蚂蚁成功的完成路由选择后，记录当前成功路径并更新全局链路信息素。The purpose of the present invention is to provide a load balancing routing strategy based on ant colony optimization suitable for low-orbit satellite networks. The routing strategy firstly utilizes the periodic characteristics of low-orbit satellite orbits and the predictable characteristics of constellation structure, and adopts the control strategy of virtual topology to obtain continuous static topology snapshots during the operation period of a satellite system. Then, use the inter-satellite link distance, delay jitter and congestion degree to calculate the transition probability of the inter-satellite link, select the link with the highest probability to forward data packets each time, and update the selected inter-satellite link according to the local pheromone update rule. Pheromones of the road. When any ant successfully completes the route selection, the current successful route is recorded and the global link pheromone is updated.
本发明解决上述技术问题采用如下的技术方案：The present invention solves the above-mentioned technical problems and adopts the following technical solutions:
一种低轨卫星网络中基于蚁群优化的负载均衡路由方法，所述路由方法包括以下步骤：A load balancing routing method based on ant colony optimization in a low-orbit satellite network, the routing method comprising the following steps:
任意蚂蚁基于卫星之间的链路距离、时延抖动与拥塞程度计算出与当前卫星相邻的链路的选路概率，并依据概率最大原则选择出下一跳卫星；Any ant calculates the routing probability of the link adjacent to the current satellite based on the link distance, delay jitter and congestion degree between satellites, and selects the next hop satellite according to the principle of maximum probability;
判断选择出的所述下一跳卫星是否为目的卫星；Judging whether the selected next-hop satellite is a destination satellite;
若不是目的卫星，则将数据包转发给所述下一跳卫星，根据局部更新公式更新当前卫星走过路径上的信息素，继续依据概率最大原则选择出下一跳卫星；If it is not the destination satellite, forward the data packet to the next-hop satellite, update the pheromone on the path that the current satellite travels according to the local update formula, and continue to select the next-hop satellite according to the principle of maximum probability;
若是目的卫星，则将数据包转发给所述目的卫星，根据局部更新和全局更新公式更新路由拓扑上所有链路上的信息素，存储当前卫星到目的卫星的一条路由路径；If it is a destination satellite, then the data packet is forwarded to the destination satellite, the pheromone on all links on the routing topology is updated according to the local update and the global update formula, and a routing path from the current satellite to the destination satellite is stored;
当所有蚂蚁都完成卫星的链路选路后，比较每次找到的路径，选择出时延最低的路径作为当前卫星的路由路径。After all the ants have completed the satellite link routing, compare the paths found each time, and select the path with the lowest delay as the current satellite routing path.
本发明是一种低轨卫星网络中基于蚁群优化的负载均衡路由方法。本发明在原有的路径策略上还考虑了时延抖动和拥塞程度对链路概率的影响，对蚁群算法进行改进，并选取概率最大的链路转发数据包，当所有蚂蚁都完成选路，选取时延最小的路径作为最优路由。The invention is a load balancing routing method based on ant colony optimization in a low-orbit satellite network. In the original path strategy, the invention also considers the influence of delay jitter and congestion degree on the link probability, improves the ant colony algorithm, and selects the link with the highest probability to forward the data packet. When all the ants complete the route selection, The path with the smallest delay is selected as the optimal route.
与传统的快照路由算法相比，本发明基于蚁群优化的方式，将链路距离、时延抖动与拥塞程度加入概率选路公式中，当卫星中某个卫星遇到突发拥塞时，可使网络的时延降低37％，丢包率降低41％，能达到很好的负载均衡的效果。本发明不仅可以保证低时延，还能在遇到一定拥塞的情况下，依然能找到一条较优的路径，即引导流量分布在较空闲的链路上，提升了整个网络的可靠性。Compared with the traditional snapshot routing algorithm, the present invention is based on the ant colony optimization method, and the link distance, delay jitter and congestion degree are added to the probability routing formula. When a certain satellite in the satellite encounters sudden congestion, it can be The network delay is reduced by 37%, the packet loss rate is reduced by 41%, and a good load balancing effect can be achieved. The present invention can not only ensure low time delay, but also can find a better path in the case of certain congestion, that is, guide traffic to be distributed on relatively idle links, and improve the reliability of the entire network.
附图说明Description of drawings
图1是本发明的一种低轨卫星网络中基于蚁群优化的负载均衡路由方法流程图；1 is a flowchart of a load balancing routing method based on ant colony optimization in a low-orbit satellite network of the present invention;
图2是本发明所采用的低轨卫星网络星座系统模型图；Fig. 2 is a low-orbit satellite network constellation system model diagram adopted by the present invention;
图3是本发明与现有技术的端到端时延随时间的变化仿真图；Fig. 3 is the simulation diagram of the end-to-end delay time variation of the present invention and the prior art;
图4是本发明与现有技术的丢包率随时间的变化仿真图。FIG. 4 is a simulation diagram of the variation of the packet loss rate with time in the present invention and the prior art.
具体实施方式Detailed ways
下面将结合本发明实施例中的附图，对本发明实施例中的技术方案进行清楚、完整地描述，显然，所描述的实施例仅仅是本发明一部分实施例，而不是全部的实施例。基于本发明中的实施例，本领域普通技术人员在没有做出创造性劳动前提下所获得的所有其他实施例，都属于本发明保护的范围。The technical solutions in the embodiments of the present invention will be clearly and completely described below with reference to the accompanying drawings in the embodiments of the present invention. Obviously, the described embodiments are only a part of the embodiments of the present invention, but not all of the embodiments. Based on the embodiments of the present invention, all other embodiments obtained by those of ordinary skill in the art without creative efforts shall fall within the protection scope of the present invention.
图1是一种低轨卫星网络中基于蚁群优化的负载均衡路由方法流程图，如图1所示，具体包括如下步骤：Figure 1 is a flowchart of a load balancing routing method based on ant colony optimization in a low-orbit satellite network, as shown in Figure 1, which specifically includes the following steps:
S1、任意蚂蚁基于卫星之间的链路距离、时延抖动与拥塞程度计算出与当前卫星相邻的链路的选路概率，并依据概率最大原则选择出下一跳卫星；S1. Any ant calculates the routing probability of the link adjacent to the current satellite based on the link distance between satellites, the delay jitter and the congestion degree, and selects the next hop satellite according to the principle of maximum probability;
在一些实施例中，利用低轨卫星轨道的周期特性以及星座结构的可预测特性，采用虚拟拓扑的控制策略得到一个卫星系统运行周期内的连续静态拓扑快照。本发明采用虚拟拓扑的控制策略运行，具体包括在卫星运转的周期T内，将时间离散化为z个时间间隔；每个时间间隔内的网络拓扑用一个拓扑快照来表示，相邻的两个拓扑快照的时间间隔为
在步骤S1中，假定LEO卫星网络中的所有卫星集合为P＝{v0,v1,…,vn}，其中发出数据包的源卫星为vs，目的卫星为vd，集合S存放源卫星vs到目的卫星vd中的某一条路径。此路径中的每个卫星都是依靠概率选路公式选择出来的，打破了传统路由算法中仅考虑链路距离的局限，在t时刻蚂蚁k由卫星vi转移到卫星vj的概率计算公式如下：In stepS1 , it is assumed that all satellite sets in the LEO satellite network are P={v0 , v1 , . A certain path from the source satellite vs to the destination satellite vd . Each satellite in this path is selected by the probability routing formula, which breaks the limitation of only considering the link distance in the traditional routing algorithm. At time t, the antk is transferred from the satellite vi to the satellite v j. as follows:
其中，A表示蚂蚁k下一步允许选择的卫星集合；l表示A集合中的卫星；τij(t)为t时刻路径(vi,vj)上的信息素浓度；在初始时刻各条路径上的信息量相等；α表示蚂蚁释放的信息素的相对重要性，反映了蚂蚁在运动过程中所产生的信息素在选路时的重要程度。ηij(t)为路径(vi,vj)链路信息启发函数，其计算公式如下：Among them, A represents the set of satellites that ant k is allowed to select in the next step; l represents the satellites in the set A; τij (t) is the pheromone concentration on the path (vi , vj ) at timet ; each path at the initial time The amount of information on the ants is equal; α represents the relative importance of the pheromone released by the ants, reflecting the importance of the pheromone produced by the ants in the process of moving. ηij (t) is the path (vi , v j) link information heuristic function, and its calculation formula is as follows:
其中，dij表示卫星vi与卫星vj之间的星间链路的距离，ω1表示星间链路距离的约束重要程度；Bij表示卫星vi与卫星vj之间的星间链路的时延抖动，ω2表示星间链路时延抖动的约束重要程度；Cij表示卫星vi与卫星vj之间的拥塞程度，ω3表示星间链路拥塞程度的约束重要程度；ω1+ω2+ω3＝1。Among them, dij represents the distance of the inter-satellite link between satellite vi and satellite vj , ω1 represents the constraint importance of the inter-satellite link distance; Bijrepresents the inter-satellitelink between satellite vi and satellite vj The delay jitter of the link, ω2 represents the importance of the constraint on the delay jitter of the inter-satellite link; Cij represents the degree of congestion between the satellite vi and the satellite vj , and ω3 represents the importance of the constraint on the degree of congestion of the inter-satellite link degree; ω1 +ω2 +ω3 =1.
卫星vi与卫星vj之间的星间链路的距离表示为：The distance of the inter-satellite link between satellite vi and satellite vj is expressed as:
其中，Hi表示卫星vi的轨道高度；Hj表示卫星vj的轨道高度；Oi是卫星vi的星下点；Oj是卫星vj的星下点，R为地球半径；cosθ是卫星vi与卫星点vj夹角的余弦值。Among them, Hi represents the orbital height of the satellite vi ; Hj represents the orbital height of the satellite vj ; Oi is the sub-satellite point of the satellite vi ; Oj is the sub-satellite point of the satellite vj , R is the radius of the earth; cosθ is the cosine of the angle between satellite vi and satellite point vj .
卫星vi与卫星vj之间的星间链路的时延抖动表示为：The delay jitter of the inter-satellite link between satellite vi and satellite vj is expressed as:
其中，L为当前时刻要发送的数据包长度，rh表示发送数据包h时链路能传送的最高数据率，rh+1表示发送数据包h+1时链路能传送的最高数据率。由于同一条链路而言，链路距离长度和传播速率不变的情况下，传播时延相同，因此时延抖动的计算仅与传输时延有关，即链路能传送的数据率相差越小，则时延抖动越小。对蚂蚁k而言，dij越小，Bij越小，则ηij(t)越大，
卫星vi与卫星vj之间的拥塞程度表示为：The degree of congestion between satellite vi and satellite vj is expressed as:
式中bsj为卫星vj缓冲队列大小，bpj表示卫星vj的缓冲区占用率，v为星间链路传输速率，c为光速。where bsj is the buffer queue size of satellite vj , bpj is the buffer occupancy rate of satellite vj , v is the transmission rate of the inter-satellite link, and c is the speed of light.
由于传统路由算法在计算路径时，仅以距离作为链路权重，因此在考虑缓冲队列的拥塞程度时，需要将其表示成距离，在邻接矩阵中加入该距离，可以准确的反映网络的拥塞程度，将流量分配到空闲的链路上，做到负载均衡。显然，将链路距离、时延抖动以及拥塞程度直接相加并不能直接反应相互之间的制约，因此ω1,ω2,ω3表示这三者之间的约束重要程度。Since the traditional routing algorithm only uses the distance as the link weight when calculating the path, when considering the congestion degree of the buffer queue, it needs to be expressed as a distance. Adding this distance to the adjacency matrix can accurately reflect the network congestion degree. , distribute traffic to idle links to achieve load balancing. Obviously, adding the link distance, delay jitter and congestion degree directly cannot reflect the constraints between them, so ω1 , ω2 , and ω3 represent the importance of the constraints among the three.
S2、判断选择出的所述下一跳卫星是否为目的卫星；S2, determine whether the selected next-hop satellite is a destination satellite;
通过在蚁群算法中改进选路概率，能够通过蚂蚁选择出当前卫星的下一跳卫星，此时判断下一跳卫星是否为目的卫星，如果是目的卫星则代表该蚂蚁找到了目的卫星，如果是中间卫星，则表示该蚂蚁还需要继续寻找下一跳卫星，直至有蚂蚁找到目的卫星。By improving the routing probability in the ant colony algorithm, the ants can select the next hop satellite of the current satellite, and then judge whether the next hop satellite is the destination satellite. If it is the destination satellite, it means that the ant has found the destination satellite. If it is an intermediate satellite, it means that the ant needs to continue to search for the next hop satellite until an ant finds the target satellite.
S3、若不是目的卫星，则将数据包转发给所述下一跳卫星，根据局部更新公式更新当前卫星走过路径上的信息素，继续依据概率最大原则选择出下一跳卫星；S3, if it is not the destination satellite, then forward the data packet to the next-hop satellite, update the pheromone on the current satellite's path according to the local update formula, and continue to select the next-hop satellite according to the principle of maximum probability;
由于每只蚂蚁走完一步即步入下一跳卫星，就会在相应的路径上释放一定量的信息素，这些释放出来的信息素与链路上的初始信息素都要及时进行更新处理。由此，对于第k只蚂蚁从卫星vi转移到卫星vj，各链路的初始信息素为τ0，则t+1时刻在路径(vi,vj)上的信息量以局部更新的方式可按如下规则进行调整：Since each ant steps into the next hop satellite after one step, it will release a certain amount of pheromone on the corresponding path, and the released pheromone and the initial pheromone on the link must be updated in time. Therefore, for the kth ant to transfer from satellite vi to satellite vj , the initial pheromone of each link is τ0 , then the amount of information on the path (vi , vj ) at timet +1 is updated locally can be adjusted according to the following rules:
式中，
S4、若是目的卫星，则将数据包转发给所述目的卫星，根据局部更新和全局更新公式更新路由拓扑上所有链路上的信息素，存储当前卫星到目的卫星的一条路由路径；S4, if it is a destination satellite, then forward the data packet to the destination satellite, update the pheromone on all links on the routing topology according to the local update and the global update formula, and store a routing path from the current satellite to the destination satellite;
当有蚂蚁到达目的节点，即跳出循环时，此蚂蚁经过的所有路径上的信息素τsd将进行全局更新，更新公式如下：When an ant reaches the destination node, that is, jumps out of the loop, the pheromone τsd on all paths passed by the ant will be globally updated, and the update formula is as follows:
对于其他蚂蚁未经过的路径上的信息素按照下式进行局部更新：For the pheromone on the path not traversed by other ants, the local update is performed according to the following formula:
τij＝(1-ρ1)τijτij =(1-ρ1 )τij
其中，ρ1表示当前拓扑所有可通信的星间链路信息素随时间变化的挥发系数，则1-ρ1表示信息素残留因子，ρ1的取值范围为[0,1)。n表示蚁群中所有蚂蚁完成一次转移的时间，即蚂蚁完成一个循环。Q表示信息素强度，它在一定程度上影响算法的收敛速度。
可以理解的是，步骤S3和步骤S4所采用的局部更新公式是不同的，步骤S3所采用的局部更新公式由信息素挥发因子ρ0决定；步骤S4所采用的局部更新由当前拓扑所有可通信的星间链路信息素随时间变化的挥发系数ρ1决定。It can be understood that the local update formulas used in step S3 and step S4 are different, and the local update formula used in step S3 is determined by the pheromone volatility factor p0 ; The inter-satellite link pheromone is determined by the time- varying volatility coefficient ρ1.
S5、当所有蚂蚁都完成卫星的链路选路后，比较每次找到的路径，选择出时延最低的路径作为当前卫星的路由路径。S5. After all the ants have completed the satellite link routing, compare the paths found each time, and select the path with the lowest delay as the current satellite routing path.
当所有蚂蚁都找到卫星的链路选路后，比较每个蚂蚁找到的路径，选择中其中时延最低的路径作为当前卫星的路由路径，实现源卫星为vs到目的卫星为vd路由连接。After all the ants have found the link route selection of the satellite, compare the paths found by each ant, select the path with the lowest delay among them as the routing path of the current satellite, and realize the routing connection between the source satellite vs and the destination satellite vd .
在本发明的优选实施例中，本发明还采用了优先级筛选的方式来提高蚂蚁选路的效率；In a preferred embodiment of the present invention, the present invention also adopts the method of priority screening to improve the efficiency of ant route selection;
具体的，在计算选路概率之前，还包括计算链路优先级；去除优先级较低的链路；蚂蚁将从剩下的优先级较高的链路中进行选择；所述链路优先级的计算公式如下：Specifically, before calculating the route selection probability, it also includes calculating the link priority; removing the link with lower priority; ants will select from the remaining links with higher priority; the link priority The calculation formula is as follows:
其中，Plij为卫星节点vi与卫星节点vj之间的星间链路优先级，l为所有与卫星节点vi相邻的节点，λ1为同轨因子，λ2为高纬因子，λ3为方向因子。Among them, Plij is the priority of the inter-satellite link between the satellite node vi and the satellite node vj , l is all the nodes adjacent to the satellite node vi , λ1 is the co-orbit factor, and λ2 is the high latitude factor , λ3 is the direction factor.
可以理解的是，这里的优先级高低可以通过人为的方式进行划分，假设Plij的值为0～1，我们可以设定0～0.5为低等级，0.5～1为高等级；在蚂蚁进行选路前，可以剔除全部或者部分低等级的星间链路。It can be understood that the priority here can be divided artificially. Assuming that the value of Plij is 0 to 1, we can set 0 to 0.5 as a low level and 0.5 to 1 as a high level; Before the road, all or part of the low-level inter-satellite links can be eliminated.
下面举一个具体的实施例，已知铱星系统采用经典的每颗卫星有4条相邻的星间链路，源卫星节点为vs，目的卫星节点为vd，其相邻链路优先级判断如下：A specific example is given below. It is known that the iridium system adopts the classic classic that each satellite has 4 adjacent inter-satellite links, the source satellite node is vs , the destination satellite node is vd , and its adjacent links have priority The grades are judged as follows:
首先，由于轨道面内的卫星间距离恒定且不容易发生链路断开等突发情况，因此轨道面内的星间链路优先级大于轨道面间的星间链路优先级；其次，还要考虑纬度高低的影响，处于不同轨道时的高纬度的星间链路距离更短，人口分布更不密集，传播时延更小，链路空闲率就越高，即高纬度星间链路的优先级大于低纬度星间链路的优先级。再次，处于源卫星节点到目的卫星节点之间的星间链路优先级更高。例如，针对铱星系统的6条轨道，源卫星节点设为301,目的卫星节点为503，则处于轨道3、轨道4、轨道5之间的星间链路优先级大于轨道1、轨道6星间链路优先级。本发明所设计的优先级选路方式相当于缩小了卫星选择的范围，即选择剩下的链路优先级较高的星间链路进行转发。First, since the inter-satellite distances within the orbital plane are constant and sudden situations such as link disconnection are not easy to occur, the inter-satellite link priority within the orbital plane is greater than that of the inter-satellite link between the orbital planes; Considering the influence of latitude, the inter-satellite link distance at high latitude in different orbits is shorter, the population distribution is less dense, the propagation delay is smaller, and the link idle rate is higher, that is, the high-latitude inter-satellite link is higher than that of low-latitude inter-satellite links. Again, the inter-satellite link between the source satellite node and the destination satellite node has a higher priority. For example, for the 6 orbits of the Iridium system, the source satellite node is set to 301 and the destination satellite node is 503, then the inter-satellite link between orbit 3, orbit 4 and orbit 5 has a higher priority than orbit 1 and orbit 6. inter-link priority. The priority routing method designed in the present invention is equivalent to narrowing the range of satellite selection, that is, selecting the remaining inter-satellite links with higher priority for forwarding.
本发明选用66/6/3铱星星座系统模型。铱星星座的轨道高度为780km,属于近地轨道星座，由66颗在轨卫星组成。将卫星编号为XYY，其中X代表轨道号，YY代表轨道内卫星编号，如图2所示。假设卫星都具有星上处理与路由交换能力，可以完成路由器的功能，即可以按照特定规则将数据包通过ISL转发到相邻卫星。星间链路可分为轨道面内的星间链路和轨道面间的星间链路。每颗卫星分别与轨道面内和轨道面间的相邻卫星建立星间链路，一般情况下每颗卫星具有4条星间链路，也有少量星座系统设计有更多星间链路。多于4条星间链路的星座系统设计虽然提高了网络的连通性，但是在速率足够高时对系统性能并没有太大的增益，与此同时卫星的复杂度却大大增加，因此在本方法中均采用典型的4条星间链路。The present invention selects the 66/6/3 iridium constellation system model. The Iridium constellation has an orbital altitude of 780km and is a low-Earth orbit constellation consisting of 66 satellites in orbit. The satellites are numbered as XYY, where X represents the orbit number and YY represents the satellite number in the orbit, as shown in Figure 2. Assuming that the satellites have on-board processing and routing switching capabilities, they can complete the function of routers, that is, they can forward data packets to adjacent satellites through ISL according to specific rules. Inter-satellite links can be divided into inter-satellite links within orbital planes and inter-satellite links between orbital planes. Each satellite establishes inter-satellite links with adjacent satellites within the orbital plane and between the orbital planes. Generally, each satellite has 4 inter-satellite links, and a small number of constellation systems are designed with more inter-satellite links. Although the constellation system design with more than 4 inter-satellite links improves the connectivity of the network, it does not have much gain in system performance when the rate is high enough, and at the same time the complexity of the satellite increases greatly. Four typical inter-satellite links are used in the method.
由于铱星星座属于对于近极轨星座，在两极附近卫星比较密集，相邻轨道面间的卫星相对运动角速度也较高，跨越极区时还会发生左右关系互换，天线指向跟踪困难，另一方面两极区域业务量很低，因此在卫星纬度高于门限时将关闭轨道面间ISL和部分波束，以β表示该纬度门限值。铱星系统中此值设为β＝70°，即当卫星位置大于此门限值时，与此卫星连接的星间链路设为不可通信。LEO卫星网络模型的参数如表1所示。Since the Iridium constellation belongs to the near-polar orbit constellation, the satellites are relatively dense near the two poles, and the relative motion angular velocity of the satellites between adjacent orbital planes is also high. On the one hand, the traffic volume in the polar regions is very low, so when the satellite latitude is higher than the threshold, the inter-orbital plane ISL and some beams will be closed, and the latitude threshold value is represented by β. In the iridium satellite system, this value is set to β=70°, that is, when the satellite position is greater than this threshold value, the inter-satellite link connected to this satellite is set to be non-communicable. The parameters of the LEO satellite network model are shown in Table 1.
表1 LEO卫星网络模型参数Table 1 LEO satellite network model parameters
为了解决低轨卫星网络拓扑频繁变化的问题，利用卫星轨道的周期特性以及星座结构的可预测特性，在卫星运转的周期T内，将时间离散化为z个时间间隔。每个时间间隔内的网络拓扑用一个拓扑快照来表示，相邻的两个快照的时间间隔为
本发明提供的这种路由方法，在选择下一卫星时不仅考虑了链路距离，还包含了当前状态下的时延抖动以及卫星的拥塞程度，然后通过蚁群优化来选出最短时延路径，当卫星遇到突发拥塞时，可以有效的避开，平衡整个网络的负载。在网络高负载的情况下，可以减少时延和丢包率，大大提升了网络的可靠性。The routing method provided by the present invention not only considers the link distance when selecting the next satellite, but also includes the delay jitter in the current state and the congestion degree of the satellite, and then selects the shortest delay path through ant colony optimization , when the satellite encounters sudden congestion, it can effectively avoid it and balance the load of the entire network. In the case of high network load, the delay and packet loss rate can be reduced, which greatly improves the reliability of the network.
为了验证所提路由策略的有效性，在OPNET平台上进行了仿真，设置卫星链路的最大缓存数据包个数为100个，数据速率为2Mbps,源卫星每秒产生200个数据包，每个数据包大小为1024bit。当仿真运行到第600秒时突发产生2000个数据包导致链路拥塞，20秒后再恢复正常发包，仿真时间为20分钟。仿真结果如图3所示。在网络发生拥塞之前，连续快照算法和负载均衡算法的时延表现出一样的性能，说明负载均衡算法能在保证时延最低的前提上进行选路。当仿真运行到第10分钟时，由于链路突发的拥塞，连续快照算法依然以链路距离作为选路的唯一依据，导致时延的剧烈上升，丢包率也随之上升，如图4所示。而本文提出的负载均衡算法相比连续快照算法的时延降低了37％，即它及时的切换到了另一条空闲的路径，从而进行了负载均衡的处理，丢包率也随之下降。In order to verify the effectiveness of the proposed routing strategy, a simulation was carried out on the OPNET platform. The maximum number of buffered data packets of the satellite link was set to 100, the data rate was 2 Mbps, and the source satellite generated 200 data packets per second. The packet size is 1024bit. When the simulation runs to the 600th second, a burst of 2000 data packets is generated, which causes the link to be congested. After 20 seconds, the normal packet transmission is resumed. The simulation time is 20 minutes. The simulation results are shown in Figure 3. Before the network congestion occurs, the delay of the continuous snapshot algorithm and the load balancing algorithm show the same performance, indicating that the load balancing algorithm can select the route on the premise of ensuring the lowest delay. When the simulation runs to the 10th minute, due to the sudden congestion of the link, the continuous snapshot algorithm still uses the link distance as the only basis for route selection, resulting in a dramatic increase in the delay and the packet loss rate, as shown in Figure 4 shown. Compared with the continuous snapshot algorithm, the load balancing algorithm proposed in this paper reduces the delay by 37%, that is, it switches to another idle path in time, thus performing load balancing processing, and the packet loss rate also decreases.
本发明针对低轨卫星网络，提出一种基于蚁群优化方法的负载均衡路由方法，根据时延，时延抖动和卫星拥塞程度决定路由的选路策略，在保证低时延的同时，还做到了负载均衡，大大提高了网络的可靠性。Aiming at the low-orbit satellite network, the invention proposes a load balancing routing method based on the ant colony optimization method. The routing strategy is determined according to the delay, the delay jitter and the degree of satellite congestion. While ensuring low delay, it also makes To load balancing, greatly improve the reliability of the network.
在本发明的描述中，需要理解的是，术语“同轴”、“底部”、“一端”、“顶部”、“中部”、“另一端”、“上”、“一侧”、“顶部”、“内”、“外”、“前部”、“中央”、“两端”等指示的方位或位置关系为基于附图所示的方位或位置关系，仅是为了便于描述本发明和简化描述，而不是指示或暗示所指的装置或元件必须具有特定的方位、以特定的方位构造和操作，因此不能理解为对本发明的限制。In the description of the present invention, it should be understood that the terms "coaxial", "bottom", "one end", "top", "middle", "the other end", "upper", "one side", "top" "," "inside", "outside", "front", "center", "both ends", etc. indicate the orientation or positional relationship based on the orientation or positional relationship shown in the accompanying drawings, only for the convenience of describing the present invention and The description is simplified rather than indicating or implying that the device or element referred to must have a particular orientation, be constructed and operate in a particular orientation, and therefore should not be construed as limiting the invention.
在本发明中，除非另有明确的规定和限定，术语“安装”、“设置”、“连接”、“固定”、“旋转”等术语应做广义理解，例如，可以是固定连接，也可以是可拆卸连接，或成一体；可以是机械连接，也可以是电连接；可以是直接相连，也可以通过中间媒介间接相连，可以是两个元件内部的连通或两个元件的相互作用关系，除非另有明确的限定，对于本领域的普通技术人员而言，可以根据具体情况理解上述术语在本发明中的具体含义。In the present invention, unless otherwise expressly specified and limited, terms such as "installation", "arrangement", "connection", "fixation" and "rotation" should be understood in a broad sense, for example, it may be a fixed connection or a It can be a detachable connection, or integrated; it can be a mechanical connection or an electrical connection; it can be directly connected or indirectly connected through an intermediate medium, it can be the internal connection of two elements or the interaction relationship between the two elements, Unless otherwise clearly defined, those of ordinary skill in the art can understand the specific meanings of the above terms in the present invention according to specific situations.
尽管已经示出和描述了本发明的实施例，对于本领域的普通技术人员而言，可以理解在不脱离本发明的原理和精神的情况下可以对这些实施例进行多种变化、修改、替换和变型，本发明的范围由所附权利要求及其等同物限定。Although embodiments of the present invention have been shown and described, it will be understood by those skilled in the art that various changes, modifications, and substitutions can be made in these embodiments without departing from the principle and spirit of the invention and modifications, the scope of the present invention is defined by the appended claims and their equivalents.
Claims (7)
Translated fromChinese
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN202011284624.2ACN112333109B (en) | 2020-11-17 | 2020-11-17 | Ant colony optimization-based load balancing routing method in low-orbit satellite network |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN202011284624.2ACN112333109B (en) | 2020-11-17 | 2020-11-17 | Ant colony optimization-based load balancing routing method in low-orbit satellite network |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| CN112333109A CN112333109A (en) | 2021-02-05 |
| CN112333109Btrue CN112333109B (en) | 2022-07-15 |
Family
ID=74320890
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| CN202011284624.2AActiveCN112333109B (en) | 2020-11-17 | 2020-11-17 | Ant colony optimization-based load balancing routing method in low-orbit satellite network |
Country Status (1)
| Country | Link |
|---|---|
| CN (1) | CN112333109B (en) |
Families Citing this family (14)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN112996019B (en)* | 2021-03-01 | 2021-08-27 | 军事科学院系统工程研究院网络信息研究所 | Terahertz frequency band distributed constellation access control method based on multi-objective optimization |
| CN113067775B (en)* | 2021-03-12 | 2022-09-02 | 鹏城实验室 | Protocol-independent heuristic source route discovery method |
| CN113055079B (en)* | 2021-03-12 | 2022-11-25 | 重庆邮电大学 | A Routing Method Based on Fuzzy Logic in LEO Satellite Network |
| CN113259950B (en)* | 2021-05-13 | 2022-03-11 | 重庆邮电大学 | Low-orbit satellite spot beam closing method based on service prediction |
| CN113301591B (en)* | 2021-05-26 | 2023-09-15 | 中国科学院微小卫星创新研究院 | Inter-satellite network optimization method for global networking observation satellite constellation |
| CN113179213A (en)* | 2021-06-29 | 2021-07-27 | 凯睿星通信息科技(南京)股份有限公司 | Satellite communication delay optimization method and intelligent gateway |
| CN113825199A (en)* | 2021-09-29 | 2021-12-21 | 广东天镝科技有限公司 | Satellite network distributed multi-path routing method and system based on ant colony algorithm |
| CN114244774B (en)* | 2022-02-23 | 2022-05-06 | 武汉烽火凯卓科技有限公司 | LEO satellite network congestion multicast routing avoiding method based on swarm intelligence |
| CN115276757B (en)* | 2022-06-21 | 2023-09-26 | 重庆邮电大学 | Low-orbit satellite constellation survivability optimization method based on link establishment probability |
| CN115696355B (en)* | 2022-10-31 | 2024-10-29 | 航天恒星科技有限公司 | Low-orbit giant constellation beam position planning method based on user distribution |
| CN116015424B (en)* | 2023-01-10 | 2025-05-02 | 广州大学 | Artificial bee colony low-orbit satellite network routing method, system, device and medium |
| CN115811772A (en)* | 2023-02-07 | 2023-03-17 | 凯睿星通信息科技(南京)股份有限公司 | Satellite communication routing method based on ant colony optimization |
| CN117749256B (en)* | 2024-02-19 | 2024-05-14 | 中国人民解放军战略支援部队航天工程大学 | Method and system for balancing inter-satellite load routing in low-orbit satellites |
| CN119151264B (en)* | 2024-11-19 | 2025-03-14 | 南京邮电大学 | Active power distribution network route scheduling and dynamic selection method and system driven by service demand |
Citations (6)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN103634842A (en)* | 2013-12-20 | 2014-03-12 | 大连大学 | Inter-group routing method for distributed satellite network |
| CN104244356A (en)* | 2014-09-02 | 2014-12-24 | 北京空间飞行器总体设计部 | Orientation ant colony route optimization method based on evolution graph full route forecasting |
| CN105471730A (en)* | 2015-11-16 | 2016-04-06 | 国家电网公司 | Power communication hierarchical routing path determining method |
| CN110730131A (en)* | 2019-10-22 | 2020-01-24 | 电子科技大学 | Multi-QoS Constrained Routing Method for SDN Satellite Network Based on Improved Ant Colony |
| CN111556545A (en)* | 2020-05-11 | 2020-08-18 | 广州鹄志信息咨询有限公司 | Novel wireless sensor network routing algorithm based on Beidou positioning system |
| AU2020102041A4 (en)* | 2020-08-28 | 2020-10-08 | Lin, Shudong Mr | Construction and maintenance of satellite-to-ground and inter-satellite laser communication network based on ants colony algorithm |
Family Cites Families (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN103685025A (en)* | 2013-12-04 | 2014-03-26 | 中国空间技术研究院 | Cross-layer dynamic self-adapting routing method based on LEO satellite network |
| CN108418623A (en)* | 2018-03-21 | 2018-08-17 | 大连大学 | A Satellite QoS Routing Algorithm Based on Improved Ant Colony Algorithm |
- 2020
- 2020-11-17CNCN202011284624.2Apatent/CN112333109B/enactiveActive
Patent Citations (6)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN103634842A (en)* | 2013-12-20 | 2014-03-12 | 大连大学 | Inter-group routing method for distributed satellite network |
| CN104244356A (en)* | 2014-09-02 | 2014-12-24 | 北京空间飞行器总体设计部 | Orientation ant colony route optimization method based on evolution graph full route forecasting |
| CN105471730A (en)* | 2015-11-16 | 2016-04-06 | 国家电网公司 | Power communication hierarchical routing path determining method |
| CN110730131A (en)* | 2019-10-22 | 2020-01-24 | 电子科技大学 | Multi-QoS Constrained Routing Method for SDN Satellite Network Based on Improved Ant Colony |
| CN111556545A (en)* | 2020-05-11 | 2020-08-18 | 广州鹄志信息咨询有限公司 | Novel wireless sensor network routing algorithm based on Beidou positioning system |
| AU2020102041A4 (en)* | 2020-08-28 | 2020-10-08 | Lin, Shudong Mr | Construction and maintenance of satellite-to-ground and inter-satellite laser communication network based on ants colony algorithm |
Non-Patent Citations (3)
| Title |
|---|
| Network routing algorithm of middle and high orbit satellite constellation based on ant colony algorithm;Chen Jianyun等;《2019 14th IEEE International Conference on Electronic Measurement & Instruments (ICEMI)》;20200527;全文* |
| 卫星网络中基于多 QoS 约束的蚁群优化路由算法;魏德宾等;《计算机工程》;20190731;全文* |
| 卫星网络中基于蚁群优化的概率路由算法;戴翠琴等;《重庆邮电大学学报(自然科学版)》;20180615(第03期);全文* |
Also Published As
| Publication number | Publication date |
|---|---|
| CN112333109A (en) | 2021-02-05 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| CN112333109B (en) | Ant colony optimization-based load balancing routing method in low-orbit satellite network | |
| CN112821940B (en) | Satellite network dynamic routing method based on inter-satellite link attribute | |
| CN111148161A (en) | Method and system for balancing load route between low-orbit satellite constellation satellites | |
| CN110391983B (en) | Distributed congestion avoidance routing algorithm for satellite-ground integrated network | |
| CN106656302B (en) | An Adaptive Routing Algorithm for Distributed Nodes in LEO Satellite Networks | |
| Dong et al. | Load balancing routing algorithm based on extended link states in LEO constellation network | |
| CN105245451B (en) | The time diffusivity of satellite DTN network routes method for searching | |
| CN103634842B (en) | Method for routing between a kind of distributed satellite network group | |
| CN114828144B (en) | A quality of service routing method for low-orbit satellite constellations | |
| CN111416655A (en) | Low-orbit satellite routing improvement method based on virtual topology | |
| CN109586785B (en) | Routing strategy for low-orbit satellite network based on K shortest path algorithm | |
| CN113099505B (en) | Air-space-ground integrated network routing method | |
| CN106921523B (en) | A Data Transmission Method Based on GEO/LEO Satellite Network | |
| CN107453801A (en) | A kind of Layered Multipath method for routing towards satellite network | |
| CN117614882A (en) | Low orbit satellite network route decision-making method and device based on multiple intelligent agents | |
| CN111294108A (en) | Efficient routing method for orthogonal circular orbit configuration satellite constellation | |
| US20240305364A1 (en) | Leo satellite congestion control routing method | |
| CN112261681B (en) | Low earth orbit satellite DTN network routing path selection method and system | |
| CN114422017B (en) | A method for realizing traffic load balancing of low-orbit constellations | |
| CN115483972B (en) | A communication system based on a two-layer satellite optical network architecture and its dynamic flow control method | |
| CN112020117A (en) | Routing method based on transmission speed and node capacity in low-orbit satellite communication network | |
| CN114499639A (en) | An Ant Colony Optimization Routing Method with Multiple QoS Constraints in Low Orbit Satellite Networks | |
| CN119921843B (en) | Dynamic scheduling method, device and medium for multipath route of satellite communication system | |
| CN118473503A (en) | Multi-path reliable transmission method and system for local perception of satellite network | |
| CN119966885A (en) | A low-orbit satellite constellation routing method, system, device and storage medium |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| PB01 | Publication | ||
| PB01 | Publication | ||
| SE01 | Entry into force of request for substantive examination | ||
| SE01 | Entry into force of request for substantive examination | ||
| GR01 | Patent grant | ||
| GR01 | Patent grant |