一种空间信息网多径路由算法_刘军

第32卷第6期2011年6月东北大学学报(自然科学版)JournalofNortheasternUniversity(NaturalScience)Vol 32,No.6Jun.2011

一种空间信息网多径路由算法

刘 军1,刘向军2,叶 宁1,沙 毅1

(1.东北大学信息科学与工程学院,辽宁沈阳 110819;2.中国软件与技术服务股份有限公司,北京 100081)

摘 要:分析空间信息网特点,提出一种多径路由算法,将网络拓扑分为骨干网和非骨干网 在骨干网内充分利用节点运行的周期性和可预知性,进行路由的静态配置,引入了节点被选概率因子,有效避免了瓶颈节点的形成;非骨干网节点因其拓扑动态变化的特点采用按需路由,减少了路由维护的开销 依据网络环境建立节点不相交多路径路由,并且在多路径间进行合理的负载均衡 在网络拓扑变化时自主维护路由,提高网络的自治性 仿真表明,算法收敛快、开销小,提高了网络的处理能力,适合空间网络环境 关 键 词:空间信息网;路由;星际链路;多径;负载均衡

中图分类号:TP393 文献标志码:A 文章编号:1005-3026(2011)06-0795-03

AMultipathRoutingAlgorithmforSpaceInformationNetworks

LIUJun1,LIUXiang-jun2,YENing1,SHAYi1

(1.SchoolofInformationScience&Engineering,NortheasternUniversity,Shenyang110819,China;2.ChinaNationalSoftware&ServiceCo.,Ltd.,Beijing100081,China.Correspondingauthor:LIUJun,E-mail:liujun@http://www.77cn.com.cn)

Abstract:Amultipathroutingalgorithmisproposedforspaceinformationnetworksonthebasisofadeepinterviewtoitscharacteristics.Inthealgorithm,aspaceinformationnetworktopologyisdividedintobackboneandnon-backbone.Sincethemotionsofbackbonenodesareperiodicandpredictive,routsbetweenthemarestaticallyconfigured.Inthestaticconfiguration,eachnodeisassignedaselectionfactorthatindicatestheprobabilitytobeselectedinacertainroute,whicheffectivelyavoidsnetworkbottleneck.Routscontainingnon-backbonenodesasapartaregeneratedondemandfordramaticchangeofnon-backbonetopology,whichmakesoverheadofroutmaintainingundertightcontrol.Multipathroutingisconstructedadaptivelyaccordingtonetworkenvironment,andaloadbalancemechanismisalsodesignedtobalanceloadamongmultipath.Routmaintainingautomaticallyoperatesonthechangeoftopology,whichimprovesautonomousabilityofthenetwork.Simulationresultsshowthattheproposedalgorithmhasafastconvergencespeedwithlittlecost,andimprovesnetworkprocessingability,whichindicatesthealgorithmwellsuitsspaceinformationnetworks.

Keywords:spaceinformationnetwork;routing;inter-satellitelinks(ISL);multipath;loadbalance

空间信息网由部署在不同轨道、执行不同任务的航天器组成,是智能化、自主运行的通信网络 由于通信距离远、费用与通信距离无关、覆盖面积大、不受地理条件限制,是提供可靠的海、陆、空三维移动通信的重要手段,对于情报收集、侦察监视、通信保障等具有重要的应用价值

路由技术作为组网技术的核心,已成为研究

热点[1-4]

,目前空间信息网的路由技术大多针对

卫星网络,主要分为两种:基于星间链路的(以铱星系统为代表)和不基于星间链路的(以全球星系统为代表) 使用星间链路进行路由不需要地面设施,是未来的发展方向 目前,国内外科研人员已经就基于星间链路的路由提出了许多算法和协议[5-8]

收稿日期:2010-05-05

基金项目:国家自然科学基金资助项目(10878017);中央高校基本科研业务费专项资金资助项目(N09404008) 作者简介:刘 军(1969-),男,辽宁锦州人,东北大学副教授,博士

796东北大学学报(自然科学版) 第32卷

上述路由算法都有一个共同的特点:路由的计算充分利用卫星网络运行的周期性和可预知性,并假设节点数目相对固定,这种方法具有算法简单、系统开销小的优点,但也存在着适用范围有限、通用性不足、对QoS支持较少等问题

考虑到空间信息网的复杂性,充分利用网络中不同节点的特点,提出了一种空间信息网多路径路由算法(spaceinformationnetworksmult-ipathroute,SMPR),协议采用表驱动和按需路由相结合的方式实现路由控制,对于网络中拓扑稳定的节点,为其路由静态配置,简化路由过程,为网络中的动态节点设计按需动态路由,提高路由的自适应性,使算法在低信令开销和高效率这两个互相矛盾的性能指标间寻找一个合理的折中

那么很容易造成热区节点的形成,某些节点过多地被选为路由的中间节点,在负载较重情况下,在该节点易形成拥塞 为了避免这一现象的发生,定义节点被选概率因子 ,描述骨干网络中节点被选为路由中间节点的度量, 越小,表示该节点被选为路由中间节点的次数越多 通过节点被选概率因子的动态变化,使得节点参与静态路由配置过程的优先等级不同,尽量不选被选概率因子较小的节点作为路由中间节点,这样可以均衡网络资源,有效避免热区节点的形成,抑制拥塞

初始时每个节点被赋予被选概率因子 (初值为 init),节点每次被选中作为路径中间节点, 都会减少 ,所以节点的被选概率因子用式(1)计算:

= init-n

(1)

其中n是节点被选作路由的中间节点的次数

采用静态路径评估函数(staticpathcostfunction,SPCF)对源到目的的多条路径进行全面评价,挑选合适的路径

如果第k条路径最小的被选概率小于等于0,则将SPCF(k)值置为0 如果第k条路径最小的被选概率大于0,则对其SPCF(k)进行计算,综合考虑路径跳数和节点被选概率因素 第k条路径的静态路径评估函数值用式(2)计算:

1 路由的建立与维护

利用空间信息网多数节点运行具有周期性和可预知性的特点,通过合理划分时间片的方法,建立骨干网和非骨干网组成的网络拓扑模型[9],拓扑相对固定节点组成骨干网,其他节点为动态节点 骨干网具有拓扑稳定、结构冗余等特点,为每个节点离线计算到其他所有节点的最优多路径路由

静态路由配置时通常只选择跳数来作为衡量路径优劣的度量 若一味遵循为节点配置最短路, SPCF(k)=

0,

其中:SPCF(k)为第k条路径的静态路径评估函数值; , 为比例协调因子;hops(k)为第k条路径的跳数; min为第k条路径最小的被选概率; sum为第k条路径的被选概率之和

骨干网路由静态配置算法描述如下:

1)初始化节点信息,包括节点被选概率因子、节点的全局数组等

2)从骨干网节点中依次选择DEST,开始自适应配置其他所有节点到DEST的节点不相交多路径路由

3)从骨干网节点中(除当前DEST)依次选择源节点Vs,开始自适应配置Vs到DEST的节点不相交多路径路由

4)开始标号,首先初始化节点的标号信息,然后从源节点Vs开始,逐步给每个节点Vj标号[d,jVjVs,

hops(k)

2

(k)sum- (k)min

(k)min+(1- )

+(1- )0

, (k)min>0; (k)min 0

(2)

Vi为该最短路线上的前一节点 首先为源节点Vs进行标号[0,Vs]

5)把剩余节点集V分成两类:VA(已标号节点集),VB(未标号节点集)

6)每个节点负责对其邻居节点进行标号,考虑所有这样的边[Vi,Vj],其中Vi属于VA,Vj属于VB,并且Vj不是已记录路径的中间节点,对Vj进行标号,将Vj划入VA 直至对目的节点进行标号,反向得到一条最短路径,并临时记录这条最短路

7)跳转至步骤4),直至将Vs到DEST间所有节点不相交多路径路由搜索出来 若路径数目小于等于K,则直接使用这K条路径静态配置;若数目大于K,则引入静态路径评估函数对这些路径进行评价,挑选合适的路径进行最终配置 并将最

第6期 刘 军等:一种空间信息网多径路由算法8)清除临时路径记录,跳转至步骤3),直至所有节点都作为Vs进行配置

9)跳转至步骤2),直至所有节点都作为DEST进行配置,算法结束

对于骨干网,当网络拓扑发生变化时,主要指节点或链路故障,采用SODV路由维护算法进行路由重构,保证骨干网路由信息的及时有效

非骨干网采用按需寻路方式通信,路由建立维护参考AdHoc网络的AODV路由协议及其改进的多径协议AOMDV

797

由OSPF和反应式路由AODV进行对比分析

图1是随着网络负载变化的网络吞吐率曲线,当网络负载较轻时网络平均吞吐率为1,而当网络负载进一步加重,直到接近网络中的带宽资源能够承担负载的最大值时,网络平均吞吐率开始下降 这时节点中的输入、输出缓冲区逐渐被占满,多余的数据包因为无法获得更多的缓存空间或因为等待时间过长而被丢弃

2 路由的负载均衡

充分利用路由协议多路径的特点,采用负载均衡技术增加吞吐量、加强网络数据处理能力、提高网络的灵活性和可用性的

采用路径适应度(Pfitness)描述路径当前处理能力,Pfitness越大,表示该路径的处理能力越大,反之越小

第i条路径的路径适应度用式(3)进行计算:SPCF(i),

Pfitness(i)=DPCF(i),

骨干网路径;

非骨干网路径 (3)

图1 网络平均吞吐率

Fig.1 Averagenetworkthroughput

OSPF和AODV协议由于路由都依靠寻路过程建立,产生大量的路由开销,增加网络负担,且由于路由控制报文在网络中具有较高的优先级,会阻碍数据报文的传递,同时路由信息的增加必然会导致网络总负载增加,从而影响网络的性能,使网络平均吞吐率下降

而SMDR协议骨干网中静态配置有路由信息,在网络无故障时,节点完全按照离线计算的路由方案中转数据,而这些离线计算的路由方案是根据空间信息网可预知性、周期性的拓扑结构全网优化的,因此效率很高 此外,SMDR协议维护多条路由,通过引入节点利用因子和路径利用因子来考虑可行路径处理能力,进行负载均衡,大大提高了分组转发率和吞吐量,降低了延迟和节点消耗的能量,提高了网络在重负载情况下的性能,因此网络平均吞吐较好

图2是随着网络负载变化的网络平均时延曲线,OSPF和AODV的路由选择时都是以跳数作为依据,很多情况下会因为到高轨卫星跳数少,而

通过引入路径适应度来考虑可行路径处理能力问题,根据网络情况把流量按照路径适应度的大小分配到多条路径中,进行负载均衡,以减少网络拥塞

采用周期轮循的方式进行负载均衡,假设周期为T,节点每秒发送m个数据分组,则在周期T内节点发送的数据分组个数为T m,周期T内每条路径上分配的流量为Ci应符合以下条件:

Ci=T m

Pfitness(i)Ptotal

(4)

其中:Ptotal为所有路径适应度的总和,用式(5)计算,n为路径数:

Ptotal=

Pfitness(i),n 3 i=1

n

(5)

3 SMDR路由协议性能分析

利用STK和OPNET网络模拟软件对所提算法进行仿真,仿真网络包括3颗同步轨道卫星,120颗低轨道卫星,平均分为10个轨道面,分别

在北京、纽约和悉尼设置3个地面节点,其中低轨卫星组成骨干网,地面节点和同步卫星划分为动态节点,仿真中随机设置10条CBR数据流,每个报文长度512字节

为了说明SMDR路由协议的性能,在相同测

,图2 网络平均时延

Fig.2 Averagenetworkdelay

()

第6期 喻春阳等:超大地形分块建模算法的研究801

4 结 论

本文提出了一种超大规模地形的建模方法,使用地形分片降低地形数据的处理,使用逆向碰撞盒检测法实现跨地形分片间的实时访问 本文研究的初始条件是在确定的超大地形下由大化小地进行地形分块;相反,可以在确定的小的地形分块的基础上,由小到大地拼接出实际需要的超大地形,因此,该地形分块建模方法具有很高的灵活性 参考文献:

[1]

ClarkJH.Hierarchicalgeometricmodelsforvisiblesurfacealgorithm[J].CommunicationsoftheACM,1976,19(10):547-554.[2]

LosassoF,HoppeH.Geometryclipmaps:terrainrenderingusingnestedregulargrids[J].ACMTransactionsonGraphics(TOG),2004,23(3):769-776.[3]

ZhouZC,MiaoXL,WangWG.Atilingtechnologyforcreatingextra-largescaleterrain[C] MultimediaandExpoIEEEInternationalConference.Beijing,2007:576-578.

[4]

许少华,修春来 改进的分块ROAM的地形简化生成算法[J] 齐齐哈尔大学学报:自然科学版,2009,25(3):56-59

(XuShao-hua,XiuChun-lai.ImprovedblockROAMterrainsimplifiedalgorithm[J].Journalof

QiqiharUniversity:

NaturalScienceEdition,2009,25(3):56-59.)

[5]

胡金星,马照亭,吴焕萍,等 基于格网划分的海量地形数据三维可视化[J] 计算机辅助设计与图形学学报,2004,16(8):1164-1168 (HuJin-xing,MaZhao-ting,WuHuan-ping,etal.3Dvisualizationofmassiveterraindatabasedongridpartition[J].JournalofComputerAidedDesign&ComputerGraphics,2004,16(8):1164-1168.)

[6]AgrawalA,RadhakrishnaM,JoshiRC.Dynamic

multiresolutionlevelofdetailmeshsimplificationforrea-ltimerenderingoflargedigitalterrainmodels[C] IEEEIndiaAnnualConference.NewDelhi,2004:278-282.[7]

PajarolaR,AntonijuanM,LarioR.QuadTIN:quadtreebasedtriangulated[8]

irregular

networks[C]

IEEE

Visualization.Boston,2002:395-402.

谭兵,徐青,周杨 大区域地形可视化技术的研究[J] 中国图像图形学报,2003,8(5):578-584

(TanBing,XuQing,ZhouYang.Theresearchoflargescaleterrainvisualization[J].JournalofImageandGraphics,2003,8(5):578-584.)

(上接第797页)

在选路时采用高轨卫星作为中继节点,造成时延增大,SMDR选路时不单单考虑跳数,常常会以低轨卫星间多跳通信代替高轨卫星,因此时延减小,而负载均衡降低了在重负载情况下因阻塞造成的时延增加

[4][3]

22(2):231-245.

ChenC,EkiciE.AroutingprotocolforhierarchicalLEO/MEOsatelliteIPnetworks[J].WirelessNetworks,2005,11(4):507-521.

白建军,卢锡城,彭伟 LEO卫星网络中一种简洁的星上分布式路由协议[J] 软件学报,2005,16(12):2139-2149 (BaiJian-jun,LuX-icheng,PengWei.Alightweighton-boarddistributedroutingprotocolforLEOsatellitenetworks[J].JournalofSoftware,2005,16(12):2139-2149.)[5]

AkyildizIF,EkiciE,BenderMD.MLSR:anovelroutingalgorithmformultilayeredsatelliteIPnetworks[J].IEEE/ACMTransactionsonNetworking,2002,10(3):411-424.[6]

MohorcicM,SvigeljA,KandusG,etal.Demographicallyweightedtrafficflowmodelsforadaptiveroutinginpacket-switchednon-geostationarysatellitemeshednetworks[J].InternationalJournalofComputerandTelecommunicationsNetworking,2003,43(2):113-131.[7]

KarapantazisS,PapapetrouE,PavlidouFN.Multiserviceon-demandroutinginLEOsatellitenetworks[J].-112.[8]

PavlidouFN,PapapetrouE.AnalyticstudyofDoppler-basedhandovermanagementinLEOsatellitesystems[J].IEEETransactionsonAerospaceandElectronicSystems,2005,41(3):830-839.[9]

刘军,李 空间网络路由协议研究[J] 系统仿真学报,2007,19(1):221-225

(LiuJun,LiZhe.Researchonroutingprotocolinspacenetworks[J].JournalofSystemSimulation,2007,19(1):221-225.)

IEEE

TransactionsonWirelessCommunications,2009,8(1):107

4 结 语

将空间信息网分为骨干网和非骨干网,在骨干网内充分利用节点运行的周期性和可预知性,进行路由的静态配置,引入了节点被选概率因子,有效避免了瓶颈节点的形成,非骨干网节点因其拓扑动态变化的特点采用按需路由,减少了路由维护的开销 依据网络环境建立节点不相交多路径路由,并且在多路径间进行合理的负载均衡 仿真表明,算法收敛快、开销小,提高了网络的处理能力,适合空间网络环境 参考文献:

[1]

WangJF,

ZhouMT,

LiL.

Topologicaldynamics

characterizationforLEOsatellitenetworks[J].ComputerNetworks,2007,51(1):43-53.[2]

PapapetrouE,KarapantazisS,DimitriadisG,etal.SatellitehandovertechniquesforLEOnetworks[J].InternationalJournalofSatelliteCommunicationsandNetworking,2004,

本文来源：https://www.bwwdw.com/article/kh5i.html