一种适用于军用无线自组网的可靠多径路由协议
2014-02-01王辛果杜晓明
夏 辉，王辛果，杜晓明
(1.海军装备研究院，上海 200436；2.中国西南电子技术研究所，成都 610036；3.中国北方工业公司，北京 100053)
1 引 言
由于作战应用的特殊需求，军用无线自组网对通信路径的可靠性和稳定性要求极高。如何在动态变化的网络拓扑中建立满足QoS(Quality of Service)需求的通信路径是无线自组网研究的关键问题之一[1]。多径路由协议在源和目的节点之间维护多条路径，与单径路由相比具有更高的可靠性和稳定性[2]。
与民用无线自组网相比，军用无线自组网还具有一些特性需要在设计路由协议时予以充分考虑：无线通信环境更加恶劣，经常会受到外部的严重干扰；节点移动的群体性更强，属于同一编队的节点运动轨迹相关性较高；节点移动速率高，断链可能会频繁发生；节点通常具有地理定位模块，地理位置信息易于获取。
在多径路由中，除了优化每条路径的路径指标外，还应让连接相同源和目的节点的路径之间保持低相关性，以提升路由可靠性。本文首先分析了路径相关性与网络拓扑的关系，定义了一种新的基于地理位置的路径相关因子来进一步量化路径之间的相关程度；然后，提出了一种最小化路径相关性的多径路由协议，该协议选择多条既能满足给定的单路径指标又具有最低相关性的路径，从而最大程度保证多径路由的可靠性和稳定性。
2 选路指标
2.1 路径指标
路径指标主要包括可靠性和稳定性，路径由多跳链路组成，因而路径指标取决于链路指标。
2.1.1 可靠性
链路质量指标[3](Link Quality Indication,LQI)为链路的一次性传输的成功率，该值的计算方法如下：
(1)
其中，Nrx是接收方正确接收的消息数量；Ntx是发送方发送的消息数量。每个节点通过周期性广播的HELLO消息向相邻节点反馈本节点正确接收的消息数量。
路径质量指标(Path Quality Indication,PQI)则为路径上所有链路的一次性传输成功率的乘积：
PQI=∏LQIk
(2)
将路径质量指标PQI作为可靠性指标。
2.1.2 稳定性
如图1所示，在评估从节点i到节点j的链路失效时间时，建立以节点i的位置为原点的三维垂直坐标系。链路失效时间(Link Expiration Time,LET)定义为按照节点间目前的相对运动速度，节点j离开i的通信半径范围R所需的时间。
图1 链路失效时间估计模型Fig.1 LET estimation model
通过交换位置和速度信息，可以计算得到当前时刻节点i和j之间的距离d以及它们之间的相对运动速度向量v与向量ij的夹角θ。根据余弦定理，可以得到
(3)
当θ小于90°时，平台i与j将相向运动，链路失效时间相对较长；否则，平台i与j将背向运动，链路失效时间相对较短。
路径失效时间(Path Expiration Time,PET)则定义为路径上所有链路的失效时间的最小值：
PET=min {LETk}
(4)
将路径失效时间PET作为稳定性指标。
2.2 路径相关性
路径相关性是指两条路径之间在可靠性和稳定性方面的相关程度，路由协议选择多条路径时应选择路径两两之间的相关性尽可能低的路径集[4]。如图2所示，按照是否具有相同的转发节点，路径的关系可以分为相交和不相交，前者的相关性显然高于后者。
图2 路径相关性Fig.2 Path correlation
对于相交的两条路径，根据具有相同的转发节点数量化它们的相关性，路径具有的相同转发节点越多，路径的相关性就越高；对于不相交的两条路径，根据路径之间的空间距离量化它们的相关性。在实际网络中，距离越近的多跳链路越有可能因受到来自相同干扰源的干扰而造成多条路径同时失效，距离越近的节点越有可能属于同一编队而同时离开目前所在区域造成多跳路径同时断开。因此，距离越近的路径之间的相关性越高，反之亦然。
假设路径Pi上的节点依次为s,r1,r2,…,rm,d。其中，s为源节点，d为目的节点，转发节点集Ri为
如图3所示，路径i和j的相关因子PCFi,j的正式定义如下：
PCFi,j=
(5)
其中，H为网络中最大节点间距离。路径相交时，相关因子等于两条路径具有的相同转发节点的数量，PCF≥1；路径不相交时，相关因子取决于两条路径的质心距和H的比值，0≤PCF<1 。
图3 路径相关因子Fig.3 Path correlation factor
3 路由协议
3.1 选路算法
多径路由算法选出满足给定的可靠性和稳定性要求且任两条路径的相关性尽可能低的L(L≥2)条路径，该路径集合记为P。选路算法可以建模为下面的优化问题：
(6)
s.t. |P|=L
PQIi≥γ,PQIj≥γ,∀i,j∈P
PETi≥τ,PETj≥τ,∀i,j∈P
其中，γ为最低链路可靠性，τ为最小路径持续时间。优化目标为最小化L条路径的互相关因子的最大值。第一个约束条件是必须选出L条路径，第二和第三个约束条件分别是选择的路径的可靠性和稳定性指标必须满足要求。
假设满足可靠性和稳定性要求的路径共有N条，路径集合为P，路径的转发节点集为
步骤1：进行如下操作，直至C=∅或|P|=L:
(2)将路径s从路径集P中删除，重新计算C;
(3)如果C=∅，则进行步骤2)，如果|P|=L，则算法结束;
步骤2：经过步骤1后，路径集P中仅剩下不相交路径，进行如下操作，直至|P|=L，算法结束:
(1)找到路径集P中PCF最大的路径对
(2)如果maxPCFi,k∈{P-{i,j}}>maxPCFj,k∈{P-{i,j}}，将路径i从P中删除；
(3)否则，将路径j从P中删除。
3.2 协议细节
RMRP协议采用先应式的路由策略，每个节点通过与其他邻居节点不断地交换链路状态消息，获取全网的拓扑信息，并维护本节点到网络中其他所有节点的L条最优路径。
3.2.1 链路建立
网络中所有节点周期性地广播HELLO消息，获取与本节点邻接的链路状态。该消息中包含本节点地址、本节点的地理位置和运动速度、本节点在统计窗口内收到的来自邻居节点的HELLO消息数列表等信息。收到HELLO消息后，计算邻居节点到本节点的链路传输质量和链路失效时间。HELLO消息的传播距离为一跳，仅用于感知邻接链路状态和快速建立链路。
3.2.2 拓扑感知
网络中所有节点周期性地广播TC(Topology Control)消息共享邻接链路状态信息，从而获取全网的拓扑信息。TC消息包含链路的发送地址和接收地址、时间戳、链路质量指标、链路持续时间。节点在全网拓扑表中维护所有感知到的链路状态，并在拓扑表发生变化时调用选路算法。
RMRP协议采用与OLSR(Optimized Link State Routing)[5]协议中多点中继类似的拓扑信息广播机制，以减少TC消息的广播次数，降低控制开销。每个节点从其一跳邻居节点集中挑选一部分节点作为MPR(Multi-Point Relay)节点。MPR节点的邻居节点集合的并集全包含源节点的两跳邻居节点集，保证可通过MPR节点到达所有两条邻居节点。节点广播TC消息后，只有被选为MPR的邻居节点才负责转发TC消息。
3.2.3 多径路由
多径选路算法计算L条连接源节点和目的节点的相关性低的路径。为确保该性质，采用源路由方式，即源节点将路径上所有节点的地址包含在消息中，中间节点转发消息时直接从消息的头部中查找下跳节点。为保持负载均衡和网络公平性，源节点在每次发送消息时从L条路径中随机选择之一作为传输路径。
4 仿真实验及结果分析
采用OPNET网络仿真平台[6]比较RMRP、DT-MAODV[7]在投送成功率和端到端时延方面的性能。DT-MAODV是为Ad Hoc网络设计的多径路由协议，该协议通过选择不相交的多条路径来提升传输可靠性。不失一般性，仿真场景为边长为800 km的正方形区域，节点总数为200，节点通信半径设为100 km。节点采用参考点组移动模型[8]作随机运动。在该模型中，属于同一个组的在指定的参考点区域内随机运动。参考点的运动采用RWP(Random Way Point)模型，最大运动速率为680 m/s。所有仿真结果均为10次仿真实验的统计平均值。协议配置参数为L=3，γ=0.9，τ=20 s。应用层采用CBR(Constant Bit Rate)流量模型，源节点产生消息的间隔为0.1 s，每条消息的大小为512 B，消息的目的接收节点为随机产生。
投送成功率定义为目的节点收到消息数与源节点发送消息数的比值，该指标是路由协议可靠性的重要指标。如图4所示，两种协议的投送成功率均随链路干扰比例上升或节点运动速率增加而下降。由于RMRP协议能够选择相关性更低的多条路径，端到端传输的可靠性更高。在相同网络场景配置下，RMRP的投送成功率比DT-MAODV更高，链路干扰比例越高或者节点的运动速率越大，RMRP的优势越明显。当链路干扰比例为0.4时，RMRP的投送成功率比DT-MAODV 高46.7%；当节点的运动速率为680 m/s时，RMRP的投送成功率比DT-MAODV高23.7%。
图4 投送成功率Fig.4 Delivery ratio
在传输层增加可靠传输机制，并考察消息的端到端时延。该时延定义为从源节点应用层开始产生消息到目的节点应用层收到消息的总时延。如图5所示，链路干扰比例越高或运动速率越大，所有消息的平均端到端时延越高。在相同网络场景配置下，RMRP的端到端时延比DT-MAODV更低，链路干扰比例越高或者节点的运动速率越大，RMRP的优势越明显。当链路干扰比例为0.4时，RMRP的端到端时延比DT-MAODV 低60.1%；当节点的运动速率为680 m/s时，RMRP的端到端时延比DT-MAODV低37.1%。
图5 端到端时延Fig.5 End-to-end delay
5 总 结
本文针对军用无线自组网的通信环境和平台移动特性设计了一种可靠多径路由协议，即RMRP协议。首先，定义了路径的可靠性和稳定性指标以及路径之间的相关因子；接着，提出了一种保证可靠性和稳定性要求且相关性尽可能低的多径选择算法。仿真结果表明，RMRP比DT-MAODV具有更高的投送成功率和更低的端到端时延。如何利用RMRP提供的L条路径进一步提升投送成功率是值得继续深入研究的问题。
[1] Zhang N,Anpalagan A.Comparative Review of qos-aware on-demand routing in ad hoc wireless networks [J].Wireless Sensor Network,2010(2):274-284.
[2] Mareo A,Gareia-Luna-Aeeves J J.Improving route discovery in on-demand routing protocols using two-hop connected dominating sets [J].Ad Hoc Networks,2006,4(4):509-531.
[3] Wang Y,Liu J.A backup multipath routing protocol for ad hoc networks with dynamic topology[C] / / Proceedings of 2012 IEEE ICSEM Conference.Guiyang:IEEE,2012:237-241.
[4] Biswas S,Morris R.ExOR:Opportunistic multi-hop routing for wireless networks[C] / / Proceedings of 2005 ACM SIGCOMM Conference.Philadelphia,PA,USA:IEEE,2005:133-143.
[5] RFC 3626,Optimized Link State Routing Protocol(OLSR) [S].
[6] 龙华.OPNET Modeler与计算机网络仿真[M].西安:西安电子科技大学出版社,2006.
LONG Hua.OPNET Modeler and Computer Network Simulation[M].Xi′an:Xidian University Press,2006.(in Chinese)
[7] Sahu R K,Saha R,Chaudhari N S.Fault Tolerant Reliable Multipath Routing Protocol for Ad hoc Network[C] / / Proceedings of 2012 IEEE CICN Conference.Mathura,India:IEEE,2012:117-121.
[8] 徐鑫鑫.无线移动Ad hoc网络移动模型研究[D].长沙：国防科技大学,2008.
XU Xin-xin.Research of Mobility Model in Wireless Mobile Ad Hoc Network[D].Changsha:National University of Defense Technology,2008.(in Chinese)
