路径rip协议

LEO卫星网络路径选择策略研究(段思睿,刘元安,胡鹤飞,李虎(北京邮电大学电子工程学院,北京100876)摘要:路由算法在选择路径时,主要考虑传输延迟和跳数这两个因素,分别选取最短延迟路径(LeastDelayPath,LDP)或最少跳数路径(LeastHopsPath,LHP).
在卫星网络中,基于LHP选径策略实现更加简单,但其应用在LEO卫星网络中合理性的研究成果不多.
本文对极轨道LEO卫星网络中,LDP和LHP之间关系进行详细的理论分析,验证了LHP选径策略的合理性.
并在此基础上,提出一种基于横向传输优先级(HorizontalTransmittingPriority,HTP)的LHP最短路径选择策略,利用横向链路长短特性简化路径决策流程.
通过仿真,该方法能够快速寻找到最短LHP路径,为LEO卫星网络路由算法提供一定的研究基础.
关键词:LEO;卫星网络;卫星星座;路径选择中图分类号:TP393文献标志码:A文章编号:ResearchonPathSelectingStrategyinLEOSatelliteNetworkDUANSirui,LIUYuanan,HUHefei,LIHu(SchoolofElectronicEngineering,BeijingUniversityofPostsandTelecommunications,Beijing100876,China)Abstract:Thetransmissiondelayandthenumberofhopsinpatharethetwomainfactorswhichshouldbeconsideredwhendesigningaroutingalgorithmforaspecificnetwork.
Thepathsgeneratedbythedifferentroutingstrategyarecalledleastdelaypath(LDP)andleasthoppath(LHP).
Insatellitenetwork,thealgorithmforLHPismuchsimpler,butthereislimitedresearchachievementsfortherationalityofLHP.
Inthispaper,wehaveadetailedtheoreticalanalysisforthedifferencesbetweenLDPandLHPinpolarcircularLEOsatellitenetwork.
Basingontheresultsofouranalysis,weproposeasimplifiedLHPpathselectingstrategywithanideaofhorizontaltransmittingpriority(HTP)byusingthefeaturesofhorizontallinklength.
ThesimulationresultsprovethatourpathselectingstrategycanquicklyfindouttheshortestpathamongalltheLHPbetweeneverytwonodes.
ItprovidesafoundationfortheresearchofroutingalgorithmsinLEOsatellitenetwork.
Keywords:LEO;Satellitenetwork;SatelliteConstellation;Routing在网络路由算法的研究过程中,选择路径代价的度量参数是一个非常重要的问题.
在传统的网络路由协议中,RIP协议以跳数作为度量参数,OSPF协议为每一条路由选择基于服务类型的代价(网络延迟、数据带宽等)作为路由算法的度量参数.
然而在网络路径中,最短延迟路径(LDP)和最少跳路径(LHP)之间并无直接联系,两种选择策略有各自适用的网络环境.

LEO卫星网络路由有如下四类方式:基于虚拟拓扑的路由算法[1-4]、基于数据驱动的路由算法[5,6]、基于覆盖区域划分的路由算法[7]以及基于虚拟节点的路由算法[8,9].
其中,前两类算法的选径策略是基于LDP的.
而基于LHP的路由算法,在实现上非常简单,极大的减少了卫星节点的存储和计算开销,满足星上设备性能有限的实际情况.
但是LHP路径不一定就是全局的最短路径,其在LEO网络中的适用性需要验证.

在极轨道的LEO卫星网络中,LDP和LHP并无特定的关系.
文献[10]中,作者在预先设定的几种星座模型中,采取遍历比较的方式,得出了在LEO星座中,LDP属于LHP集合的结论,是不完全准确的.
本文通过详尽推导,计算出LDP和LHP,与卫星星座参数的关系;在此基础上,提出了一种基于横向转发权限(HTP)LHP最短路径选择策略.
通过软件仿真结果证明,在不同卫星星座参数下LDP和LHP的关系符合理论推导;基于HTP的路径选择策略能够简单快速的选择最短的LHP路径,为分布式的LEO卫星网络路由技术提供了新的优化方向.

1LEO星座结构和链路特点LEO网络卫星星座LEO卫星星座结构的选择,对卫星网络的性能,网络路由算法有重大的影响.
常用的星座结构有极轨道星座[11,12],Walker星座[13,14]等.
而在采用分布式路由算法的相关文献中,都采用的是极轨道或近似极轨道的星座参数,主要原因是分布式路由算法需要均匀分布的星座结构,以便于对整个网络区域进行均匀的区域划分.

星座参数可记为N*M/N/F:h:i,F=0,1,…,N-1.
其中M为单轨道面内的卫星数,N代表轨道面数,N*M即为星座中卫星总数.
F表示相位因子,h为轨道高度,i为轨道倾角.
在极轨道星座中,i=90°.
相位因子F可以计算相邻轨道平面上同序号卫星之间的相位偏移角度θ.
如图1中,轨道间链路相连的两颗卫星是相邻轨道面的同序号卫星,当F=0时,表示两颗卫星在各自轨道面的圆内相位相同.
若F≠0,则两颗卫星的相位角差θ=360°*F/(M*N)的.
如图2中,圆弧表示轨道面卫星运动轨迹,重合在同一平面内.
相邻轨道的同序号卫星A,B在各自轨道平面内的相位为θA,θB,则相位夹角为θ.

文献[8]中,将极轨道LEO卫星网络抽象为一种ManhattanStreet网络,如图3所示.
而极轨道卫星网络与ManhattanStreet网络存在下述两点不同:(1)轨道内链路(纵向)在网络中是等长的,而轨道间链路(横向)在网络中是变长的,其长度与节点所处的纬度密切相关.
链路长度因距离过长,直接影响网络延迟,这一点在图2中无法体现出来.
(2)在极地区域和反向缝两侧的轨道间链路是不存在的.

图1极轨道星座的结构图Fig.
1StructureofPolarorbitConstellation图2相位因子Fig.
2Phasefactor图3曼哈顿网络结构Fig.
3StructureofManhattanStreetnetwork基于上述原因可以将图3调整如图4的,类似"8"字型的网络拓扑结构.
图中黑色区域,代表两个极地区域,轨道间链路无法建立;左右两侧的网络节点之间没有直连链路,表示反向缝两侧的链路无法建立.

星间链路1.
2.
1轨道内链路每个网络节点都具有两条轨道内链路.
轨道方向相对于地球表面都是纵向的,所有的卫星都沿着各自轨道按照相同的方向和速度运动,节点间由于方位角固定,因此轨道内链路是相对静态且不会中断.
用表示轨道内链路的长度:(1)其中R表示轨道半径,等于地球半径与轨道高度之和;M表示轨道内卫星颗数.
图4极轨道卫星网络拓扑结构Fig.
4StructureofPolarorbitsatellitesnetwork根据(1)可知,轨道内链路长度在整个过程中是保持不变的.
1.
2.
2轨道间链路除第一条与第N条轨道面上的卫星节点只有一条轨道间链路,其余节点都有两条轨道间链路.
当星座的相位因子F=0时,轨道方向相都是横向的,因此本文将轨道间链路也称为横向链路.
用表示轨道间链路的长度:(2)其中N表示星座的轨道数量,lat表示当前链路所处的纬度.
若星座参数F0,则轨道间链路长度(3)根据公式(2)(3)可以看出,轨道间链路长度随着其所在的纬度增加而缩短.
1.
3网络节点地址为区别网络节点,首先需要将全网节点赋予一个唯一的地址.
设网络中存在一个初始的静止状态,如图4中,用表示某节点的地址,其中n为轨道面序号,m为同轨道面内节点的序号.
例如此刻左上角的卫星地址为.
节点地址在网络中固定,不会因为卫星的运动而改变.
如当图4中,左下角的卫星跨域过极点,来到左上角的区域时,其地址仍然是.

2LDP与LHP在文献[10]中,作者设计了星座参数为48/6/3的卫星网路环境,利用路径遍历对比的方式,得到LDP属于LHP集合的结果,从而推断在所有星座参数的情况下LDP都属于LHP集合的结论,缺乏足够的理论依据.
本节将利用数学推导的方式,对LEO卫星网络中,LDP不完全属于LHP集合的存在性进行证明,并对两个集合的相互关系进行归纳.

在证明之前,定义相关函数:定义1:函数表示两点间的路径,它由一个节点序列组成.
(4)表示这条路径上依次经过的网络节点.
例如,两个节点.
在路径上增加一跳,会使n和m之中的一个加1或者减1.
定义2:函数表示两点间的路径P的跳数.
(5)定义3:函数用以计算路径P的总长度.
根据节点位置和链路类型,利用公式(1)(2)(3)累加计算.
而链路的总传输延迟(6)其中,C代表光速.
图5网络拓扑Fig.
5Topologyofnetwork假设区域网络拓扑环境如图5所示,有任意和两个网络节点.
令.
其中根据网络拓扑的结构和上述定义,我们可以做出如下推论:推论1:任意LHP路径,其跳数等于,且路径经过的节点一定在A、B、、四个网络节点组成的矩形区域内(图5中灰色区域),以下简称为最少跳区域.
证明:因为,则:(7)当且仅当与随着i增加而增加或不变的情况下上式中的等号成立.
同时与单调增加也保证了,即LHP经过的节点范围在最少跳区域内.
推论2:若存在LDP路径不属于LHP路径集合,则LDP会在纵向上跨越出最少跳区域,引入了更高纬度的水平路径.
图6场景1Fig.
6Scenario1证明:(8)(9)x、y分别代表了LHP路径在纵向和横向的跳数,、代表了LDP路径在纵向和横向的跳数.
根据式(8)可以看出,最短的LHP其横向链路一定是的最少跳区域中的最高纬度的横向链路.
若LDP不属于LHP集合,也就是LDP的总跳数大于LHP的跳数,则和,两者至少满足一项,否则LDP的跳数和LHP相等.
假设,则LDP会横向跨出最少跳区域(不考虑路径在最少跳区域内折返的情况),如图6所示.
将不等式代入式(9)(10)LDP传输延迟大于LHP路径传输延迟最小值,则假设不成立.
图7场景2Fig.
7Scenario2若假设,则如图7所示,LDP会从纵向跨出最少跳区域,这样会引入其他纬度的水平路径.
由于在四方形的网络中,路径跳数只会以偶数增加,即,为保证成立,j取1.
(11)若式(11)中的最小值,小于,则证明存在LDP路径不属于LHP路径集合,且LDP一定在纵向上跨越出最少跳区域,引入了更高纬度的水平路径.
现对的成立性进行证明:因为的最小值为,则LDP路径不存在于LHP集合的充分条件是:(12)由于在纵向上延伸路径,不会对水平方向上路径长度产生影响,可取.
由式(12)可得(13)为确保不等式成立,可取最大值N,即星座参数的轨道面数.
(14)上式的物理意义在于,引入更高纬度的横向链路而缩短的横向距离,若能抵消加入的两跳纵向链路的长度,则LDP不属于LHP的集合.
由于,且在范围内单调递增.
的最大值即极轨道星座的极地区域边界纬度值,根据文献[8],取边界值,则式(14)可进一步简化为(15)将,代入(15),即可得到下式(16)利用MATLAB,以M、N、F作为变量,对不等式(16)左面进行计算,并绘制得到图8.
图8MATLAB计算结果Fig.
8CalculatedbyMATLAB根据上图所示,当曲面Z轴值小于0时,也即不等式(16)不成立,则在此星座参数的组合下,LDP一定属于LHP集合;当曲面大于0时,不等式(16)成立,在此星座参数的组合下存在部分LDP不属于LHP集合.
文献[10]中对48/6/3的星座参数进行了仿真,得到了所有的LDP链路都是属于相对的LHP集合的结论,该结论也是符合本文的上述推论的.

以上推导,虽然只考虑相邻横向链路纬度递减的情况,也就是两个节点处于同一个半球面内.
而其他分布情况仍然符合上述推论.
例如当两个节点分处与南北半球时,类似与两个图5的网络结构反向组合的情况.

在推导过程中,有如下重要结论:由式(8)可以看出,最短的LHP其横向链路一定是的最少跳区域中处于最高纬度的横向链路.
根据式(14),LDP路径不属于LHP路径的主要因素,是跨出最少跳区域,引入更高纬度的横向链路,而缩短的横向距离,能够抵消加入的两跳纵向链路的长度.
3基于HTP的路径选择策略根据上一节的分析结论,最短的LHP其横向链路一定是的最少跳区域中处于最高纬度的横向链路,则选择最短路径的关键是在最少跳区域内选择最高纬度的横向链路进行数据传送.
因此数据发送节点必须清楚目的节点纬度信息,才能寻找到最短的路径.

图9区域化卫星网络结构Fig.
9RegionalizedStructureofsatellitesnetwork现对图4中的网络拓扑进行改进得到图9中的网络拓扑图.
表1HTP值Tab.
1ValuesofHTPs区域编号HTP值102332415263708392101112123为了体现轨道间链路的不等长特性,引入横向转发优先级(HTP)概念.
HTP表示相对区域内横向链路(轨道间链路)长度与全网内横向链路长度的比较关系.
横向链路长度越短,其HTP值越高.
考虑到卫星在圆形轨道下的对称排列,,0表示该区域不存在横向链路,如极地区域.
链路的长短直接影响卫星网路中数据传输的延迟.
HTP值是网络节点决定下一跳路径的决定因素,因为在需要横向传输数据的情况下,选择HTP值越高(链路长度越短)的横向链路,其传输的延迟更小.
全网内的HTP值如表1所示:由于轨道面内的节点数M和图8中的区域数相等,因此当节点获知数据包的目的节点地址,根据自身所在区域,则可以利用式推算出目的节点所在的区域.
(17)其中表示目的节点区域,表示当前节点所在区域.
在已知当前节点和目的节点区域的情况下,通过查表操作判断当前节点是否处于二者区域间最高的HTP值的区域,若当前节点所在区域拥有最高的HTP值,则当前节点选择横向路径发送数据,否则选择纵向路径将数据发送至更高HTP值的区域.

使用该策略需保证单轨道面内的卫星数量为偶数,利用轨道面内拓扑对称的特性,卫星只需要知道自身所处于的区域位置,以及数据目的地址,通过查询表1,即可选择最短的横向链路.
从而避免了节点间的位置信息的交互,简化了选径流程.

4仿真与结果分析4.
1LDP与LHP关系验证图10仿真流程Fig.
10Simulationflowchart本节利用仿真软件,对各种星座参数的LEO卫星轨道机型仿真,并验证LDP和LHP的相互关系是否与推论一致.
仿真原理采取了文献[3]等中所介绍的基于虚拟拓扑的理念,将LEO卫星网络在一个周期内的运动过程离散为多个静态网络拓扑,利用STK软件和MATLAB软件相结合的方式进行验证.
具体仿真流程如图10所示.

按照上述流程操作,计算每个静态网络拓扑中的每一条链路的长度信息,并将数据导入MATLAB.
在MATLAB中,分别使用Dijkstra算法[1-3],和本文介绍的基于HTP的路径寻找策略分别寻找LDP和最短LHP,最后比较两种算法的计算结果.
表2中列出的几组星座参数下,LDP路径和LHP路径集合的关系情况.

表2不同星座参数中LDP与LHP关系Tab.
2RelationshipbetweenLDPandLHPindifferentconstellation星座参数LDP路径是否都属于LHP路径48/6/0否48/6/1否48/6/2是48/6/3是66/6/0否66/6/3是72/12/0否72/12/3是从表所示,通过仿真结果可以看出,各种星座参数的组合下LDP与LHP的关系符合第二章分析所得到的图8的结论.
4.
2LDP与LHP差异性本节考虑在72/12/0:1375Km:90°的星座参数情况下,对比LDP和LHP的具体差异.
验证的方法与图10所描述的方法相同.
为对比LDP和LHP的链路的差异性,在路径对比阶段,分别计算了全部节点对之间LDP和LHP链路的传输延迟,共5112对.
并定义相似度函数(18)其中(19)仿真时间为56分钟,为半个轨道周期时间.
相似度函数记录如图11所示为便于分析成因,按照网络节点在区域内的位置关系,计算两种算法得到的所有路径的传输延迟差,记录于图11中.
由于节点数与区域数都为12,因此区域的宽度为360°/12=30°,且每个节点在所属区域位置是相同的.

图11相似度函数Fig.
11Similarityrates图12两种算法路径总延迟差Fig.
12Totaldelaydifference由图11可以看出,LDP和LHP的相似度成周期性的变换,且数量上差异不大.
LDP路径和LHP虽然在大部分时间中存在部分LDP路径和LHP路径不重合的情况,但是这个差异度普遍在1%以内.
从图12可以看出,LDP和LHP的在总延迟上差距不大,虽然在离区域中心15°时延迟差陡增,而出现差异的路径总数也增加(对应图11的波谷值).
路径延迟差异周期性变化的原因是区域2、6、8、12的边界也是极地区域的边界,当卫星处于边界时(离区域中心越远),部分路径满足第二章节总结的第二个结论的条件,产生了LDP与LHP不重合的情况.
在存在差异的路径当中,LHP链路最大传输延迟增量为32.
3ms,平均增量为16.
31ms.
这个延迟与轨道高度成正比关系,但在LEO轨道高度300Km-2000Km的范围中,这个传输延迟增量差异值变化在5ms内.
10ms级别的延迟差异在卫星网络中几乎是可以忽略的.

5结论本文通过理论分析,仿真验证的方式,对比了星座参数下,LDP与LHP两种路由策略在所选择路径的差异性.
具体取得了如下结论:在LEO卫星网络中,LDP路径并不一定就是LHP路径,两者关系与星座参数设计有关.
具体关系如图8所示,图中大于零的星座参数组合表示LDP与LHP存在出入.
文中分析了LDP不属于LHP路径的存在条件.
其关键之处在于,因引入更高纬度的横向链路缩短的横向距离,是否抵消了加入的多条跳纵向链路的长度.
相位因子越大,横向链路长度增加,上述的条件就更难满足.
因此从图8可以看出当相位因子增加后,LDP和LHP路径相同.
但不能为寻求两者重合而选择过高的相位因子,因为增加横向链路长度也就意味着增加了网络的平均传输延迟.

基于HTP的最少跳LEO路径选择策略,主要考虑纬度对横向路径长度的影响,利用网络拓扑对称特性,寻找LHP中的最短路径.
通过仿真分析,该方法能够找到最接近LDP的路径.
且两种方式寻径的差异只占全网路径的1%,且最大延迟增量在10毫秒的量级.