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

1、收稿日期:2010-05-05基金项目:国家自然科学基金资助项目(10878017;中央高校基本科研业务费专项资金资助项目(N09404008 作者简介:刘 军(1969-,男,辽宁锦州人,东北大学副教授,博士一种空间信息网多径路由算法刘 军1,刘向军2,叶 宁1,沙 毅1(1.东北大学信息科学与工程学院,辽宁沈阳 110819; 2.中国软件与技术服务股份有限公司,北京 100081摘 要:分析空间信息网特点,提出一种多径路由算法,将网络拓扑分为骨干网和非骨干网 在骨干网内充分利用节点运行的周期性和可预知性,进行路由的静态配置,引入了节点被选概率因子,有效避免了瓶颈节点的形成;非骨干网节点因

2、其拓扑动态变化的特点采用按需路由,减少了路由维护的开销 依据网络环境建立节点不相交多路径路由,并且在多路径间进行合理的负载均衡 在网络拓扑变化时自主维护路由,提高网络的自治性 仿真表明,算法收敛快、开销小,提高了网络的处理能力,适合空间网络环境 关 键 词:空间信息网;路由;星际链路;多径;负载均衡中图分类号:T P 393 文献标志码:A 文章编号:1005-3026(201106-0795-03A Multipath Routing Algorithm for Space Information NetworksL I U Jun 1,LI U X iang -j un 2,YE Ning

3、 1,SH A Yi 1Abstract:A multipath routing algorithm is proposed for space information networks on the basis of a deep interview to its characteristics.In the algorithm,a space information netw ork topolog y is divided into backbone and non -backbone.Since the motions of backbone nodes are periodic an

4、d predictive,routs betw een them are statically configured.In the static configuration,each node is assig ned a selection factor that indicates the probability to be selected in a certain route,w hich effectively avoids netw ork bottleneck.Routs containing non -backbone nodes as a part are g enerate

5、d on demand for dram atic change of non -backbone topology,w hich makes overhead of rout maintaining under tight control.M ultipath routing is constructed adaptively according to network env ironment,and a load balance mechanism is also designed to balance load among multipath.Rout maintaining autom

6、atically operates on the change of topolog y,w hich improves autonomous ability of the netw ork.Simulation results show that the proposed algorithm has a fast convergence speed w ith little cost,and improves network processing ability,w hich indicates the algorithm w ell suits space information netw

7、orks.Key words:space information netw ork;routing;inter -satellite links (ISL;multipath;load balance空间信息网由部署在不同轨道、执行不同任务的航天器组成,是智能化、自主运行的通信网络 由于通信距离远、费用与通信距离无关、覆盖面积大、不受地理条件限制,是提供可靠的海、陆、空三维移动通信的重要手段,对于情报收集、侦察监视、通信保障等具有重要的应用价值路由技术作为组网技术的核心,已成为研究热点1-4,目前空间信息网的路由技术大多针对卫星网络,主要分为两种:基于星间链路的(以铱星系统为代表和不基于星间链

8、路的(以全球星系统为代表 使用星间链路进行路由不需要地面设施,是未来的发展方向 目前,国内外科研人员已经就基于星间链路的路由提出了许多算法和协议5-8上述路由算法都有一个共同的特点:路由的计算充分利用卫星网络运行的周期性和可预知性,并假设节点数目相对固定,这种方法具有算法简单、系统开销小的优点,但也存在着适用范围有限、通用性不足、对QoS支持较少等问题考虑到空间信息网的复杂性,充分利用网络中不同节点的特点,提出了一种空间信息网多路径路由算法(space information netw orks mult-i path route,SM PR,协议采用表驱动和按需路由相结合的方式实现路由控制,

9、对于网络中拓扑稳定的节点,为其路由静态配置,简化路由过程,为网络中的动态节点设计按需动态路由,提高路由的自适应性,使算法在低信令开销和高效率这两个互相矛盾的性能指标间寻找一个合理的折中 1 路由的建立与维护利用空间信息网多数节点运行具有周期性和可预知性的特点,通过合理划分时间片的方法,建立骨干网和非骨干网组成的网络拓扑模型9,拓扑相对固定节点组成骨干网,其他节点为动态节点 骨干网具有拓扑稳定、结构冗余等特点,为每个节点离线计算到其他所有节点的最优多路径路由 静态路由配置时通常只选择跳数来作为衡量路径优劣的度量 若一味遵循为节点配置最短路,那么很容易造成热区节点的形成,某些节点过多地被选为路由的

10、中间节点,在负载较重情况下,在该节点易形成拥塞 为了避免这一现象的发生,定义节点被选概率因子 ,描述骨干网络中节点被选为路由中间节点的度量, 越小,表示该节点被选为路由中间节点的次数越多 通过节点被选概率因子的动态变化,使得节点参与静态路由配置过程的优先等级不同,尽量不选被选概率因子较小的节点作为路由中间节点,这样可以均衡网络资源,有效避免热区节点的形成,抑制拥塞 初始时每个节点被赋予被选概率因子 (初值为 i nit,节点每次被选中作为路径中间节点, 都会减少 ,所以节点的被选概率因子用式(1计算:= init-n (1其中n是节点被选作路由的中间节点的次数 采用静态路径评估函数(stati

11、c path cost function,SPCF对源到目的的多条路径进行全面评价,挑选合适的路径如果第k条路径最小的被选概率小于等于0,则将SPCF(k值置为0 如果第k条路径最小的被选概率大于0,则对其SPCF(k进行计算,综合考虑路径跳数和节点被选概率因素 第k条路径的静态路径评估函数值用式(2计算:SPCF(k=1hops(k2+(1- (km i n+(1- (ksum- (kminhops(k-12, (km i n>0;0, (km i n 0(2其中:SPCF(k为第k条路径的静态路径评估函数值; , 为比例协调因子;hops(k为第k条路径的跳数; min为第k条路径最

12、小的被选概率; sum为第k条路径的被选概率之和骨干网路由静态配置算法描述如下:1初始化节点信息,包括节点被选概率因子、节点的全局数组等2从骨干网节点中依次选择DEST,开始自适应配置其他所有节点到DEST的节点不相交多路径路由3从骨干网节点中(除当前DEST依次选择源节点V s,开始自适应配置V s到DEST的节点不相交多路径路由4开始标号,首先初始化节点的标号信息,然后从源节点V s开始,逐步给每个节点V j标号d j,V i,其中d j为V j到源节点V s的最短距离,V i为该最短路线上的前一节点 首先为源节点V s进行标号0,V s5把剩余节点集V分成两类:V A(已标号节点集,V

13、B(未标号节点集6每个节点负责对其邻居节点进行标号,考虑所有这样的边V i,V j,其中V i属于V A,V j 属于V B,并且V j不是已记录路径的中间节点,对V j进行标号,将V j划入V A 直至对目的节点进行标号,反向得到一条最短路径,并临时记录这条最短路7跳转至步骤4,直至将V s到DEST间所有节点不相交多路径路由搜索出来 若路径数目小于等于K,则直接使用这K条路径静态配置;若数目大于K,则引入静态路径评估函数对这些路径进行评价,挑选合适的路径进行最终配置 并将最终确定的路径中间节点的被选概率因子减少796东北大学学报(自然科学版 第32卷8清除临时路径记录,跳转至步骤3,直至所

14、有节点都作为V s 进行配置9跳转至步骤2,直至所有节点都作为DEST 进行配置,算法结束对于骨干网,当网络拓扑发生变化时,主要指节点或链路故障,采用SODV 路由维护算法进行路由重构,保证骨干网路由信息的及时有效非骨干网采用按需寻路方式通信,路由建立维护参考Ad Hoc 网络的AODV 路由协议及其改进的多径协议AOMDV2 路由的负载均衡充分利用路由协议多路径的特点,采用负载均衡技术增加吞吐量、加强网络数据处理能力、提高网络的灵活性和可用性的采用路径适应度(P fitness 描述路径当前处理能力,P fitness 越大,表示该路径的处理能力越大,反之越小第i 条路径的路径适应度用式(3

15、进行计算: P fitness (i =SPCF (i ,骨干网路径;DPCF (i,非骨干网路径 (3通过引入路径适应度来考虑可行路径处理能力问题,根据网络情况把流量按照路径适应度的大小分配到多条路径中,进行负载均衡,以减少网络拥塞采用周期轮循的方式进行负载均衡,假设周期为T ,节点每秒发送m 个数据分组,则在周期T 内节点发送的数据分组个数为T m ,周期T 内每条路径上分配的流量为C i 应符合以下条件:C i =T mP fitne ss (iP total(4其中:P total 为所有路径适应度的总和,用式(5计算,n 为路径数:P to tal =ni =1P fi t ness

16、 (i,n 3 (53 SM DR 路由协议性能分析利用ST K 和OPNET 网络模拟软件对所提算法进行仿真,仿真网络包括3颗同步轨道卫星,120颗低轨道卫星,平均分为10个轨道面,分别在北京、纽约和悉尼设置3个地面节点,其中低轨卫星组成骨干网,地面节点和同步卫星划分为动态节点,仿真中随机设置10条CBR 数据流,每个报文长度512字节为了说明SMDR 路由协议的性能,在相同测 试环境和条件下,将仿真结果与常用的先验式路由OSPF 和反应式路由AODV 进行对比分析图1是随着网络负载变化的网络吞吐率曲线,当网络负载较轻时网络平均吞吐率为1,而当网络负载进一步加重,直到接近网络中的带宽资源能够

17、承担负载的最大值时,网络平均吞吐率开始下降 这时节点中的输入、输出缓冲区逐渐被占满,多余的数据包因为无法获得更多的缓存空间或因为等待时间过长而被丢弃图1 网络平均吞吐率Fig.1 Average network throughputOSPF 和AODV 协议由于路由都依靠寻路过程建立,产生大量的路由开销,增加网络负担,且由于路由控制报文在网络中具有较高的优先级,会阻碍数据报文的传递,同时路由信息的增加必然会导致网络总负载增加,从而影响网络的性能,使网络平均吞吐率下降而SMDR 协议骨干网中静态配置有路由信息,在网络无故障时,节点完全按照离线计算的路由方案中转数据,而这些离线计算的路由方案是根据

18、空间信息网可预知性、周期性的拓扑结构全网优化的,因此效率很高 此外,SM DR 协议维护多条路由,通过引入节点利用因子和路径利用因子来考虑可行路径处理能力,进行负载均衡,大大提高了分组转发率和吞吐量,降低了延迟和节点消耗的能量,提高了网络在重负载情况下的性能,因此网络平均吞吐较好图2是随着网络负载变化的网络平均时延曲线,OSPF 和AODV 的路由选择时都是以跳数作为依据,很多情况下会因为到高轨卫星跳数少,而图2 网络平均时延Fig.2 Average network delay(下转第801页797第6期 刘 军等:一种空间信息网多径路由算法4 结 论本文提出了一种超大规模地形的建模方法,使

19、用地形分片降低地形数据的处理,使用逆向碰撞盒检测法实现跨地形分片间的实时访问 本文研究的初始条件是在确定的超大地形下由大化小地进行地形分块;相反,可以在确定的小的地形分块的基础上,由小到大地拼接出实际需要的超大地形,因此,该地形分块建模方法具有很高的灵活性参考文献:1Clark J H.Hierarchical geom etric models for visible surfacealgorithmJ.Com munications of the ACM,1976,19(10: 547-554.2Losasso F,Hoppe H.Geometry clipmaps:terrain ren

20、deringusing nes ted regular gridsJ.ACM T ransac tions on G raphics (T OG,2004,23(3:769-776.3Zhou Z C,M iao X L,Wang W G.A tiling technology forcreating extra-large scale terrainC M ul timedia an d Expo IEEE International Conference.Beijing,2007:576-578.4许少华,修春来 改进的分块ROAM的地形简化生成算法J 齐齐哈尔大学学报:自然科学版,200

21、9,25(3:56-59 (Xu Shao-hua,Xiu Chun-lai.Improved block ROAM terrain simplified algorithmJ.Journal o f Qiqihar Univer sity: Natu ral Scie nc e Edition,2009,25(3:56-59.5胡金星,马照亭,吴焕萍,等 基于格网划分的海量地形数据三维可视化J 计算机辅助设计与图形学学报,2004, 16(8:1164-1168(Hu Jin-xing,M a Zhao-ting,Wu H uan-ping,et al.3D visualization of

22、 mas sive terrain data based on grid partitionJ.Jour nal of Comp uter Aided Desig n&Comp uter G raphics, 2004,16(8:1164-1168.6Agraw al A,Radhakrishna M,Joshi R C.Dynamicmultires oluti on level of detail mesh simplification for rea-l timerendering of large digi tal terrain modelsC IEEE IndiaAnnua

23、l Conference.New Delhi,2004:278-282.7Pajarola R,Antonijuan M,Lario R.QuadT IN:quadtreebased triangulated irregular netw orksC IE EE Visualization.Boston,2002:395-402.8谭兵,徐青,周杨 大区域地形可视化技术的研究J 中国图像图形学报,2003,8(5:578-584(T an Bing,Xu Qing,Zhou Yang.The research of large scale terrain visualizationJ.Jour

24、nal of Image a nd G raphics, 2003,8(5:578-584.(上接第797页在选路时采用高轨卫星作为中继节点,造成时延增大,SMDR选路时不单单考虑跳数,常常会以低轨卫星间多跳通信代替高轨卫星,因此时延减小,而负载均衡降低了在重负载情况下因阻塞造成的时延增加4 结 语将空间信息网分为骨干网和非骨干网,在骨干网内充分利用节点运行的周期性和可预知性,进行路由的静态配置,引入了节点被选概率因子,有效避免了瓶颈节点的形成,非骨干网节点因其拓扑动态变化的特点采用按需路由,减少了路由维护的开销 依据网络环境建立节点不相交多路径路由,并且在多路径间进行合理的负载均衡 仿真表明

25、,算法收敛快、开销小,提高了网络的处理能力,适合空间网络环境参考文献:1Wang J F,Zhou M T,Li L.T opological dynam i cscharacteri zati on for LEO satellite networksJ.Comp uterNetw orks,2007,51(1:43-53.2Papapetrou E,Karapantazis S,Dimitriadis G,e t al.S atellitehandover techniques for LEO networksJ.International Jour nal o f Satellite C

26、om munications and Netw orking,2004,22(2:231-245.3Chen C,Ekici E.A routing protocol for hierarchical LEO/M EO s atelli te IP netw orksJ.W ireless Ne tw orks,2005,11(4:507-521.4白建军,卢锡城,彭伟 LEO卫星网络中一种简洁的星上分布式路由协议J 软件学报,2005,16(12:2139-2149(Bai Jian-jun,Lu X-i cheng,Peng W ei.A light w eight on-board distributed routing protocol for LEO satellite netw orks J.Jour nal o f Sof tw ar e,2005,16(12:2139-2149. 5Akyildiz I F,Ekici E,Bender M D.M LSR:a novel routingalgorithm for multil