航空高动态网络负载感知路由算法

刘 智 徐 桢

(北京航空航天大学 电子信息工程学院，北京100191)

1 问题提出

在民用航空通信领域中，目前的航空电信网无法完全满足飞机间相互通信、分发环境感知信息等需求［1］.因此，为了达到未来空域运行实时交互、高效通信的目标，针对上述缺陷设计适合的通信方式是非常重要的.同时在军用航空通信领域，航空通信网络承载着诸如遥测信息、指令信息等收集、传输、分发等重要任务.由于航空通信环境复杂，对于端到端的信息传输质量有着较高的需求.因此，构建可靠、快速、抗毁性好的空天地一体化通信网络是未来战场的必然需求［2］.

航空高动态网络是整个空天地网络的重要一环，由高速飞行、功能独立又相互协作的飞行器组成.如图1所示，航空高动态网络和卫星通信网络、地面通信网络、高空平台通信系统等构成了完整的空天地一体化结构.典型的航空高动态网络主要包括航空信息传输节点(TA，Transmission Airborne-nodes)、中继节点(RN，Relay Nodes)及相应的信息站(GS，Gate Stations)和网管节点(GW，Gateways)等.和地面的Ad hoc网络相比，航空高动态网络的节点移动速度差异性明显.网络中同时存在速度较低的节点和高速运动的节点，其中高速运动节点相对速度可达2 382 m/s，Ma≈7［3］.而和普通的航空自组网相比，由于应用环境的不同，航空高动态网络中对于飞行器均匀转向飞行模式(CT，Constant Turning)和恒定速度飞行模式(CV，Constant Velocity)的假设并不适用，网络拓扑变化更为频繁，且承载的信息传输任务更为复杂.

图1 空天地一体化通信网络结构示意图Fig.1 Structure of the air-space-ground communication networks

由于航空高动态网络承载着重要信息的传输任务，且飞行器节点和通信环境具有特殊性，在航空高动态网络中提供有质量保证的通信服务比一般的无线网络难度更大.而航空高动态网络的性能很大程度上取决于路由算法的高效性和可靠性.设计合适的航空高动态网络路由算法有以下难点:①设备资源受限.尽管机载通信设备能力在逐渐变强，但受重量、续航等条件的约束，和一般的地面设备相比仍具有较低的计算能力和存储能力，这样就限制了航空高动态网络路由算法的复杂度和可存储的QoS状态数量;②分布式的结构.由于成员节点可以自发地动态组网，航空高动态网络难以提供任何形式的中心控制，通常要求每个节点局部的路由信息更新能够及时地转发，这增加了航空高动态网络路由算法的开销和复杂度;③节点运动难以预测.由于节点的移动模型具有随机和完全独立的特点，因此获取准确的拓扑信息是非常困难的，这也给航空高动态网络路由算法的稳定性造成了冲击.

从国内外研究现状来看［4-15］，现有的航空高动态网络路由算法主要是基于地理位置信息的路由协议，由于可以较好地屏蔽拓扑变化，因此能够高效可靠地应用于高动态航空环境下.代表算法之一是贪婪周边无状态路由协议(GPSR，Greedy Perimeter Stateless Routing)［4］，算法将目的节点的地理位置信息写入路由信息包中，中间节点将其转发至其通信范围内与目的节点地理位置距离最近的节点.GPSR算法在车载自组网及无线传感器网络中有着广泛的应用和研究.另一方面，GLSR算法从机载导航设备获取飞行器的地理位置信息，结合链路层缓存信息降低信息丢失概率［5］.但由于该算法假定飞机的网络拓扑是不变的，这与实际应用情况有较大差距.因此，现有航空高动态网络路由算法一方面没有充分考虑节点高速度、变化轨迹对地理位置信息度量所带来的影响;另一方面，也没有考虑在源节点进行高速数据传输时，由于地理位置原因向某地区汇聚容易导致拥塞的问题.

由此，本文提出一种新的基于地理位置信息的负载感知路由算法(DGLAR，Dynamic Geographic Load Aware Routing protocol)，算法在考虑通信节点地理位置关系的基础上，通过交互网络邻居节点的队列信息来实现网络的流量均衡，避免部分节点拥塞带来的网络吞吐率下降.另外，引入节点相对移动性的动态度量，避免了单一位置度量的路由算法带来的高速流量汇聚问题，同时解决了节点高速运动对路由性能的影响.

2 负载感知路由

目前的机载通信设备能够依靠地空、空空数据链，将导航系统及其他机载设备产生的位置、速度以及流量等状态信息矢量(SV，State Vector)作为数据源，进行周期性对外广播，因而能够更好地辅助信息传输过程.在本文中假设航空飞行器间装载相同格式的数据链，能够直接通信.DGLAR算法主要包括路由发现、下一跳节点选择、数据发送3个部分.在路由发现的阶段，算法收集其通信范围内的节点信息及其状态向量;在下一跳节点选择阶段，算法通过和通信范围内节点的移动性度量和负载信息动态选择下一跳节点;在数据发送阶段，算法设计了相应的数据包转发策略.

2.1 路由发现

航空高动态网络模型可以描述为无向连同图G(V，E)，其中V是航空高动态网络中飞行器的有限集，若(i，j)∈E则表示节点 i，j间存在着通信链路.

在航空高动态网络中，t时刻节点i，j间的欧式距离度量 Ei，j和相对移动速度 Vi，j分别为

假设节点到达节点i，而其目的节点为D，在t时刻转发，地理位置距离为

如图2所示，以X-Y轴为例，源节点S在t时刻以速度vS(t)移动，此时通信范围内的邻居节点有A和B节点，而目的节点D在t时刻以速度vD(t)移动，此时通信范围内的邻居节点仅有C节点可选.

图2 节点位置速度关系图Fig.2 Relative positions and velocities between nodes

若在t时刻节点S进行数据转发，则初始化其邻居信息表，并向通信范围r内的邻居节点发送请求(RREQ，Route Request)报文.邻居节点接收到RREQ报文后，将自身t时刻的位置信息、速度信息、队列长度信息、链路带宽及链路速度等信息写入相应的应答(RREP，Route Reply)报文中，回复给上一跳路由节点作为路径选择依据.

2.2 下一跳节点选择

在传统的地理位置信息路由协议中，数据包通常直接转发给地理位置最接近目的地的下一跳节点，这对节点的移动性和负载特性支持不够，而且这会导致下一跳节点位置处于通信的临界区域.在这种情况下，节点的高速移动会导致信息数据的丢失.而且，流量非常容易在目的节点周围的节点汇聚而导致网络拥塞.在DGLAR算法中，同时考虑节点的相对移动速度和节点的数据拥塞情况，给出了新的路由度量机制.

定义下一跳节点最大队列长度为lj，t时刻队列长度为qj(t)，链路到达速率为xj(t)，cj为链路带宽，定义节点j在t时刻的拥塞因子为

γ≥0，α＞0，均为拥塞系数的加权因子.

因此，在t时刻节点j对于目的节点D的动态路由因子为

当算法应用于强调拓扑变化的应用环境中，可以调节增大β系数;而当算法应用于强调高速数据信息传输的应用环境，可以动态增大γ的权重.中间节点根据请求信息，判断自己是否是目的节点，若是则直接应答接收数据包并处理.否则，将重复进行下一跳的请求应答过程.

因此，下一跳节点的选择:

其中Si(t)为t时刻i节点的邻居节点集合.

2.3 数据发送

当接收到相应的数据信息后，转发节点通过查询其维护的邻居状态信息表来决定如何转发该数据包.在转发节点的传输范围内，算法选择具有最佳动态路由因子的下一跳节点.如果转发节点在时间段内没有下一跳节点作为转发节点，则缓存数据包直至适合的下一跳节点出现在通信范围内.若缓存溢出或超过时钟后仍不能找到合适的下一跳节点，则数据包就会被销毁.

3 算法性能评估

为了验证本文提出的路由算法，采用仿真软件OPNET 10.1建立动态的仿真环境.仿真环境的建立参考了实际航空通信环境中的参数，如传播损耗模型、射频功率等.应用层采用服从均匀分布的恒定比特率业务来模拟数据业务.航空飞行器终端均以相同概率产生新业务，且持续时间服从负指数分布.网络层采用本文提出的DGLAR算法.链路层使用接入控制协议802.11 DCF，节点链路有一个队列长度为15个数据包大小的FIFO队列.实验分为两部分:第一部分测试在不同网络动态程度下的算法表现，第二部分测试在不同负载程度下的算法表现.环境具体仿真的参数如表1所示.

表1 仿真实验的参数取值Table 1 Parameter values of simulation

3.1 节点动态性能实验

首先测试在大数据速率环境下不同节点速度对网络性能的影响，设定低速移动节点速度为100 km/h，高速节点速度在400～600 km/h的范围内逐渐增加.数据发送速率恒定为5 MB/s.图3显示了网络丢包率随节点移动速度增加的变化.

图3 不同移动速度下的网络丢包率对比Fig.3 Packet drop ratio comparison between different movement speed scenarios

从图3中可知，3种路由算法的丢包率都受到节点移动速度的影响.GPSR和GLSR的丢包率随着节点移动速度的增大而快速累积，特别是当速度大于600 km/h时丢包情况进一步严重.这主要是因为高速移动的环境下网络断链情况加剧，从而产生大量的重路由导致数据包的发送失败.另一方面，由于DGLAR考虑了节点的移动速度度量，能够减少相应丢包情况的发生，有效地提高了数据包的成功传输率.

图4表明了网络传输时延随节点移动速度的变化.从图4可以看出，相比 GPSR和 GLSR算法，DGLAR能够减少网络的端到端时延，这主要是由于DGLAR同时考虑了节点移动性和负载的度量，减少了由于移动性带来的重路由和拥塞概率，相应地减少了丢包重传带来传输时延累积.

图4 不同移动速度下的传输时延对比Fig.4 Transmission delay comparison between different movement speed scenarios

3.2 流量负载性能实验

接下来测试在动态环境下不同负载程度对算法性能的影响，设定低速移动节点速度为100 km/h，高速节点速度为400 km/h.数据发送速率从5～35 MB/s逐渐递增.

图5显示了网络丢包率随节点数据发送速率增加的变化.由于节点的缓存队列是有限的，随着发送速率的增加，3种路由算法的丢包率都有所增加.DGLAR的数据包成功传输率优于GPSR和GLSR，这是由于DGLAR在选择下一跳节点的时候考虑了节点的负载度量，避免了网络的流量汇聚带来的拥塞，减少了网络的丢包机率.

图5 不同发送速率下的网络丢包率对比Fig.5 Packet drop ratio comparison under different packets transmitting rates

图6表明了网络传输时延随节点负载程度增加带来的影响.从图6可以看出，在低速发送速率的环境下，DGLAR的优势并不明显.而当数据发送速率超过30 MB/s时，GPSR和GLSR的时延累积情况加剧，DGLAR对高速数据传输的表现有明显优势.

图6 不同发送速率下的传输时延对比Fig.6 Transmission delay comparison under different packets transmitting rates

4 结论

本文在对航空高动态网络特殊性及其对路由算法影响进行深入分析的基础上，设计了一种适合复杂动态环境、高速数据传输的航空高动态路由算法DGLAR.DGLAR根据信息发送节点和邻居节点的地理位置信息、相对移动速度和节点链路拥塞情况动态选择发送路径，提高了传输路径的稳定性和整体网络对高速数据传输的可靠性.实验结果表明:

1)算法可显著减少因节点移动而导致的数据发送失败，从而降低信息传输丢包率，进而减少因重传而产生的拥塞概率，使网络达到负载均衡，提升网络整体资源利用率.相比GLSR算法，因节点移动而产生的丢包率可降低14.5%～43.3%，因数据发送速率增加而导致的丢包增加率可降低8.6%.

2)算法可有效地降低了复杂通信环境的端到端时延，并随节点移动速度和数据发送速率的增加而显示出更好的传输性能，能够更好地满足业务对网络QoS路由的需求.相比GLSR算法，在节点移动速度达700 km/h时，端到端时延可降低63.2%;在节点发送速率为35 MB/s时，端到端时延可降低55.4%.

References)

［1］ Rohrer J P，Jabbar A，Cetinkaya E K，et al.Highly-dynamic cross-layered aeronautical network architecture［J］.IEEE Transactions on Aerospace and Electronic Systems，2011，47(4):2742-2765

［2］ Rohrer J P，Jabbar A，Cetinkaya E K，et al.Airborne telemetry networks:challenges and solutions in the ANTP suite［C］//Proceedings of the IEEE MILCOM.San Jose:IEEE，2010:74-79

［3］ Broyles D，Jabbar A，Sterbenz J P.Design and analysis of a 3-D gauss-markov mobility model for highly-dynamic airborne networks［C］//Proceedings of the International Telemetering Conference.Las Vegas:ISA，2009:1-10

［4］ Karp B，Kung H T.GPSR:greedy perimeter stateless routing for wireless networks［C］//Proceedings of the Sixth Annual ACM/IEEE International Conference on Mobile Computing and Networking.Boston:ACM/IEEE，2000:243-254

［5］ Medina D，Hoffmann F，Rossetto F，et al.Routing in the airborne Internet［C］//Proceedings of the IEEE Integrated Communications Navigation and Surveillance Conference.Mexico:IEEE，2010:1-10

［6］ Peters K，Jabbar A，Cetinkaya E K，et al.A geographical routing protocol for highly-dynamic aeronautical networks［C］//Proceedings of the 2011 IEEE Wireless Communications and Networking Conference.Mexico:IEEE，2011:492-497

［7］ Ayaz S，Hoffmann F，Epple U，et al.Performance evaluation of network mobility handover over future aeronautical data link［J］.Computer Communications，2012，35(3):334-343

［8］ Xiong N，Vasilakos A V，Yang L T.A novel self-tuning feedback controller for active queue management supporting TCP flows［J］.Information Sciences，2010，180(11):2249-2263

［9］ Gu Y，Towsley D，Hollot C V.Congestion control for small buffer high speed networks［C］//Proceedings of IEEE INFOCOM.New York:IEEE，2007:1037-1045

［10］ Chen M Y，Fan X Z，Murhin M N.Normalized queueing delay:congestion control jointly utilizing delay and making［J］.IEEE/ACM Transactions on Networking，2009，17(2):618-631

［11］ Zhang Y，Kang S，Loguinov D.Delay-independent stability and performance of distributed congestion control［J］.IEEE/ACM Transactions on Networking，2007，15(5):838-851

［12］王钢，张军，李彬.适于高动态环境下的随机方向移动模型改进算法研究［J］.航空学报，2007，28(2):376-379 Wang Gang，Zhang Jun，Li Bin.Study on improved algorithm of random direction mobility modeling in high dynamic environment［J］.Acta Aeronautica et Astronautica Sinica，2007，28(2):376-379(in Chinese)

［13］ Jared B，Jeffrey D A，Elizabeth I.Techniques for enabling dynamic routing on airborne platforms［C］//Proceedings of IEEE MILCOM.Boston:IEEE，2009:2083-2091

［14］ Butler R K，Creech L C，Anderson A J.Considerations of connecting MANETs through an airborne networks［C］//Proceedings of IEEE MILCOM.Washington D C:IEEE，2006:1-7

［15］ Erturk M，Haque J，Arslan H.Challenges of aeronautical data networks［C］//Proceedings of IEEE Aerospace Conference.Montana:IEEE，2010:1-7