战术无线自组网中稳定多径路由协议

王 硕， 周 阳， 陈英伟， 周 桃， 严晞隽

(北京宇航系统工程研究所，北京 100076)

战术无线自组网中稳定多径路由协议

王 硕， 周 阳， 陈英伟， 周 桃， 严晞隽

(北京宇航系统工程研究所，北京 100076)

在战术通信网络中，节点快速移动会导致网络拓扑变化较快，从而频繁触发新的路由发现进程，导致网络稳定性下降。提出了一种稳定缠绕多径路由协议SWMR，在利用源路由信息建立节点不相交多径路由的同时，利用无线通信特性，构建缠绕主路由间的备份路径，减少网络路由开销，增强网络稳定性。仿真结果表明，在网络拓扑快速变化场景下，SWMR协议在快速移动发送成功率、平均端到端延时和归一化路由开销等方面与AOMDV和AODV协议相比具有一定优势。

战术通信网络； 自组网； 缠绕路径； 多径路由

0 引言

战术无线自组网络是一种在战术环境下无需基础设施的多跳临时性无线自组移动网络，具有无中心、自组织、多跳路由、独立组网、节点移动等特点。在战术无线自组网中，节点作为路由器需要转发来自其他节点的分组信息。但是受移动性、通信范围的限制，特别是在节点高速移动的情况下，网络拓扑结构变化很快，会频繁触发路由发现过程，增加路由开销。

为了提高网络路由的稳定可靠性，战术无线自组网中多采用多径路由。在多径路由协议中，只有当所有路径均失效后才会启动新的路由发现，大大减少了路由开销[1]。文献[2]利用节点的地理位置信息将网络划分成不相交区域，快速建立最大限度不相交多径路由；文献[3]通过选择邻居节点变化率和路由长度低的节点来提高路由稳定性；文献[4]利用链路状态感知信息及时切换备用路径，以降低路由延时。但在以上路由协议中，当某一段链路失效时，即使该路由上其他链路仍处于完好状态，仍会导致该路由中断，降低网络性能。

为充分利用既有仍处于完好状态的路由信息，增强网络稳定性，本文提出了稳定缠绕多径路由协议(Stable Wrapped Multipath Routing，SWMR)。SWMR协议在源路由信息的基础上，充分利用无线信道广播通信的特性，在源-目的节点间的节点不相交主路由旁边建立多条备份路径，以实现对完好路径的充分利用。

1 多径路由稳定性分析

网络的路径稳定性同许多因素有关，比如说无线信道干扰、地理位置、节点移动性等。在本文的稳定性分析中，不考虑其他因素，只考虑节点的移动性以及路径相关性对路径稳定所产生的影响。

1.1 参考模型

节点S和D之间的多径路由MP0，包括路径P=(A1,A2,…,An)和路径P=(B1,B2,…,Bn)，多径路由MP1包括路径P=(C1,C2,…,Cn)和路径P=(E1,E2,…,En)。MP0与MP1有相同的跳数，但MP0是节点不相关的，而MP1是链路不相关(有共享节点)[5]。

假设每个节点的移动概率相同，均为p。对路径P=(A1,A2,…,An)，其中断概率为

p(Pbreak)=1-(1-p)n

(1)

其稳定性概率为

p(Pstability)=(1-p)n。

(2)

定义MPi为包含两条路径的多径路由,其中,i值为2条路径的共享中间节点数。设其中第1条路径的跳数为n，第2条为m。

对于MPi的稳定性分析，可计算MPi2条路径均中断的概率。定义p(MPi)为MPi2条路径均中断的概率。

当i=0时，

p(MP0)=p[Pbreak(A1,A2,…,An)]∩p[Pbreak(B1,B2,…,Bn)]=[1-(1-p)n][1-(1-p)m] 。

(3)

当i=1时，

p(MP1)=p[Pbreak(C1,C2,…,Cn)]∩p[Pbreak(E1,E2,…,Em)]=[1-(1-p)n-1][1-(1-p)m-1]+p。

(4)

将p(MP1)和p(MP0)相减，即

f1(p)=p(MP1)-p(MP0)=p[1-(1-p)n-1-

(1-p)m-1+(2-p)(1-p)n-1(1-p)m-1]≥0 。

(5)

将p(MP2)和p(MP1)相减，即

f2(p)=p(MP2)-p(MP1)=p[1-(1-p)n-2-

(1-p)m-2+(2-p)(1-p)n-2(1-p)m-2]≥0 。

(6)

由式(5)、式(6)结果，对i值扩展后可以得出

p(MPk)≥…≥p(MPl)≥…≥p(MP0)

(7)

式中,k>l>0，k

1.2 结论分析

从对上述节点不相关路径和链路不相关路径的稳定性分析中，可以得出如下两个结论。

1) 多径路由的中断概率与中间节点的移动性以及中间节点的个数相关。

2) 多径路由的中断概率还与路径的相关性有联系，即多径路由中共用的节点数越少，其中断的概率就越小。节点不相关的多径路由，其稳定性要好于链路不相关的多径路由。

2 SWMR路由协议

为了减少由路由失效而导致额外的路由发现开销，SWMR协议在每一对源-目的节点间构建了2条节点不相交的主路由和若干缠绕在主路由周围的备份路径。当源-目的节点主路由某一段链路失效断开后，SWMR协议会启用缠绕主路由周围的备份路径快速恢复主路由，从而避免整条主路由失效，减少重启路由发现次数，从而减少网络路由开销。SWMR协议可分为路由建立和路由维护2部分。

2.1 路由建立

当源节点有数据包发送但没有到达目的节点的路由信息时，SWMR协议则启动路由建立机制。SWMR路由建立机制主要完成在源-目的节点间发现和建立2条节点不相交的主路由和若干围绕在主路由周边的备份路径。

SWMR协议路由建立可分为两部分：1) 寻找从源节点s到目的节点d间可达路径的路径发现过程；2) 构建从目的节点d到源节点s的不相交多径路由及缠绕主路由间的备份路由的路径构建过程。

2.1.1 路径发现

源节点首先广播发送路由请求包RREQ，并建立路由表。网络中间节点第1次从接收到的RREQ中获取到所经历的路由信息后，将其前向广播给邻居节点。对后续接收到的RREQ，中间节点在判断其跳数不大于第1个RREQ且与第1个RREQ经过的路径无交叉的情况下将其前向广播，否则丢弃。

在AODV协议中，当中间节点自身存在到达目的节点路由信息时，接收到路由请求RREQ后会直接向源节点发送路由回复包RREP。但如此一来，目的节点则可能收集不到足够的RREQ所带的路由探测信息，从而无法建立节点不相交多径路由。因此，SWMR协议中只有目的节点才能给源节点发送路由回复包。

2.1.2 路径构建

当目的节点接收到路由请求包RREQ后，按照接收时间顺序从中选取2条节点不相交的主路由，然后通过主路由分别回传路由回复包RREP。路由回复包可分为主路由回复包RREP和备份路由回复包RREP_AP。

在无线通信网络中，节点通过电磁波在空间广播的方式进行信号传输，在电磁波通信范围内其他节点均能监听到该信息。借助该特性，SWMR协议在中继回传路由回复包RREP过程中构建围绕主路由的备份路径。

图1给出了SWMR协议建立围绕主路由的备份路径的过程示意。其具体过程如下。

1) 目的节点d接收到源节点s发起的多个路由请求RREQ，而a，b，c，e，f等中间节点在前传RREQ的同时获取了各自到达源节点的反向路由。

2) 目的节点d优选出s-a-b-c-d作为主路由后，向节点c发送路由回复包RREP。

3) 目的节点d的邻居节点c，g，j同时接收到该RREP。节点c接收到后记录下主路由信息，并向节点b广播。节点g，j监听到该RREP后，发现其存在到达主路由下一跳节点b的路由，则构建一条到目的节点的备份路径，并向节点b发送备份路由回复RREP_AP。RREP_AP只在1跳范围内传播。

4) 节点b接收到RREP_AP后，将节点g， f作为备份路径的下一跳记录在路由表中。节点f，i接收到该RREP_AP后，发现自己不在主路由中，则丢弃该数据包。

5) 当源节点s接收到节点a发送的RREP和节点e，h发送的RREP_AP后，则构建s-a-b-c-d的主路由及缠绕期间的备份路径，见图1c，路径构建过程完毕。

图1 主/备份路由建立过程Fig.1 Primary routes and backup routes construction

2.2 路由维护

在节点快速运动导致网络拓扑变化、路由失效时，SWMR协议启动路由维护过程，主要面临的情况有2种。

1) 前向发送数据包失败。当节点i向主路由下一跳节点j传输数据包失败时，首先节点i从路由表中删除经节点j转发的所有路由信息，然后查询是否存在到达目的节点的备份路径信息。如存在备份路径则节点i通过已有的备份路径转发数据包;如不存在备份路径或所有备份路径均失效的情况下，节点i中止转发数据包，并向源节点发送路由错误包RERR。

2) 接收到路由错误包RERR。当中间节点i接收到节点j回传的路由错误包RERR后，节点i从路由表中删除经节点j到达目的节点的路由信息，并回传RERR。源节点收到RERR后，删除该主路由信息，并将网络负载重新分配到另一条主路由上。当源-目的节点间所有路由均失效时，源节点启动新一轮路由建立过程。

3 仿真环境及性能指标

3.1 仿真环境设置

本文采用OPNET 14.5作为仿真平台。节点随机分布在仿真场景中，每个节点从仿真时间10 s开始产生数据分组直至仿真结束，数据源类型为CBR。数据链路层采用OPNET提供的IEEE 802.11 DCF无线接入协议，传输速率设置为2.4 Mbit/s。仿真的其他参数如表1所示[6-10]。

表1 仿真参数表

本文选择经典的单径路由协议AODV和多径路由协议AOMDV与SWMR协议进行对比仿真分析。每个仿真结果为5个不同仿真种子实验下仿真结果的平均。

3.2 仿真性能指标

1) 发送成功率：接收端接收的数据包数/发送端发送的数据包数,反映了网络传输的可靠性，数值越大可靠性越高。

2) 平均端到端延时：目的节点收到数据包的时间与源节点发送数据包的时间差,值越小网络反应越快，网络质量越令人满意。

3) 归一化路由开销：单位数据包个数所引起的额外路由包个数，反映了路由协议的运行效率。

4 仿真结果分析

仿真试验中网络节点运动速率分别为0 m/s，5 m/s，10 m/s，15 m/s，20 m/s，主要测试SWMR，AOMDV，AODV 3种协议在不同网络移动性下的网络性能差异。从图2中可以看出，随着网络拓扑变化加快，路由失效概率增大，3种协议的发送成功率降低。由于SWMR协议构建了节点不相交的主路由和缠绕其间的备份路由，降低了路由失效次数，在部分路径失效后能够通过备份路由快速修复，因此其发送成功率高于AOMDV和AODV。

图2 发送成功率对比Fig.2 Packet delivery ratio vs velocity

图3显示随着节点移动速率增加，3种协议的平均端到端时延增加，但SWMR协议的时延增加幅度最小。当节点移动速率较小时，AOMDV和AODV协议延时比SWMR协议小，这是由于中间节点不回复路由和目的节点多径选择而延迟回复RREP所导致。当节点移动速率较大时，SWMR协议延时比AOMDV,AODV协议低。究其原因是，由不相交多径路由和备份路由构建的稳定传输链路减少了路由中断次数，有效地减少因路由失效而引起的数据包缓存数量，降低了排队时延。

图3 平均端到端延时对比Fig.3 Average delay vs velocity

图4显示当节点低速率移动时，3种协议的路由开销较小，但随着节点移动速率增加，网络拓扑不稳定，路由开销增大。

图4 归一化路由开销对比Fig.4 Normalized routing load vs velocity

SWMR协议中，减少了由中间节点发送的RREP数量，同时增加了用于建立备份路由的RREP_AP。因而在移动速度较低时，3种协议路由开销大致相同。而随着速度增加，SWMR协议路由开销远小于AOMDV,AODV协议。这是由于构建的稳定路由降低了由于某一段链路中断而导致新路由发现启动次数，从而减少了路由开销。

5 结束语

本文提出的稳定缠绕多径路由SWMR协议，在路由发现过程中构建2条节点不相交主路由，并利用无线信道广播特性以较小的开销建立若干缠绕在主路由边的备份路径，形成了较为稳定的路由网络，使其能较好地适应战术移动网络应用场景。仿真结果表明，相比AOMDV和AODV协议，在节点移动速度较快时，SWMR协议具有更高的发送成功率，更低的端到端平均延时和路由开销。SWMR协议的提出为设计和优化多径路由协议提供了一种新的思路，在流媒体网络方面拥有较好的应用前景。

[1] RADI M,DEZFOULI B,BAKAR K.A,et al.Multipath routing in wireless sensor networks:survey and research challenges [J].Sensors,2012,12(1):650-685.

[2] 董萍,钱焕延,魏晓飞,等.Ad Hoc网络基于平面区域划分的多径路由协议[J].计算机应用研究,2014,31(5):1554-1557.

[3] 王顶,王珊珊,席效禹.基于路由长度的多径路由协议[J].计算机工程，2014,40(9):82-86.

[4] 谢忠明,何华冰,李云飞,等.一种基于链路状态感知的Zigbee多径路由算法[J].微电子学与计算机，2015,32(9):65-69.

[5] 袁博.Ad Hoc网络多路路由研究[D].杭州:浙江大学,2005.

[6] LEE Y O,NARASIMHA A L.Constructing disjoint paths for failure recovery and multipath routing [J].Computer Networks,2012,56(2):719-730.

[7] 潘胜利,杨析儒,张志勇,等.单源多径路由网络拥塞链路识别[J].电子与信息学报,2015,37(9):2232-2237.

[8] 赵科莉,李铮,李皓,等.基于OPNET的多数据链组网设计与仿真[J].电光与控制,2014,21(9):61-64.

[9] PERKINS C E,ROYER E M.Ad-Hoc on-demand distance vector routing(AODV)[R].California:University of California,2013.

[10] JOHNSON D,HU Y,MALTZ D.RFC4728 on the Dyna-mic Source Routing protocol (DSR) for mobile Ad Hoc networks for IPv4[EB/OL].[2007-02-13].http://www.ietf.org/rfc/rfc4728.txt.

StableMulti-pathRoutingProtocolinTacticalAdHocNetwork

WANG Shuo, ZHOU Yang, CHEN Ying-wei, ZHOU Tao, YAN Xi-jun

(Beijing Institute of Astronautics System Engineering,Beijing 100076,China)

Nodes moving with high speed can bring rapid topology change in tactical communication network,which may invoke new route discovery processes and lead to network performance degradation.To alleviate this problem,a novel Stable Wrapped Multi-path Routing (SWMR) protocol is proposed,which uses source routing approach to establish node-disjoint primary routes,and builds up several backup paths among each primary route synchronously by utilizing overheard route reply packets.By constructing such multi-path routes,the protocol not only provides higher network stability,but also reduces route discovery latency and routing overheads.Simulation results show that:compared with AOMDV and AODV,SWMR has a better routing performance in packet delivery ratio,average delay and normalized load metrics when the network topology changes rapidly.

tactical communication network; Ad Hoc; wrapped path; multi-path routing

TP393

A

1671-637X(2017)03-0085-04

2016-09-14

2016-10-19

王 硕(1985 —),男，湖北荆州人，硕士，工程师，研究方向为战术通信网络技术。