2. 总参信息化部驻北京地区军事代表室, 北京 100083
单向链路会对自组网按需距离矢量组播路由协议(MAODV)的路由维护机制造成一定影响, 为提高通信的实时性和完整性, 针对单向链路, 提出了改进的路由算法MAODV-UNI.在路由维护过程中及时对单向链路进行检测并做出处理, 合理有效的利用单向链路, 简化路由修复, 有效提高了路由性能.用NS2仿真平台进行仿真验证, 模拟单向链路, 将改进后的协议与原始的MAODV协议进行比较, 结果表明MAODV-UNI算法在分组投递率和时延方面优于MAODV协议, 证明了该协议的有效性.
2. Military Representative Agent of Information Department of General Staff Stationed Beijing Region, Beijing 100083, China
Unidirectional links have impacts on the routing maintenance mechanism of origin multicast Ad hoc on-demand distance vector (MAODV) protocol. In order to enhance the real-time performance and completeness of communication, this article put forward an improved routing protocol MAODV-UNI for unidirectional links. It can improve the routing efficiency by detecting the unidirectional links timely during the route maintenance and reasonably use it. Then use NS2 to simulate MAODV-UNI and compare with the original MAODV protocol in the same scene with unidirectional links. It is proven that MAODV-UNI has advantages about packet delivery rate and delay that make it more effective compare with original MAODV.
自组网按需距离矢量组播(MAODV，multicast Ad hoc on-demand distance vector)路由协议是移动自组网中常用的组播路由协议，相较于单播，组播可以节省带宽和能源，提高无线链接的有效性.由于移动自组网的拓扑动态变化频繁，所以路由的维护是非常必要的.在实际无线Ad hoc网络中，由于节点发射功率的差异或者无线环境的干扰，会造成节点之间出现单向链路，单向链路的出现会导致网络连通性的降低，对传输时延和投递率造成影响.所以在进行链路修复时，应充分考虑单向链路问题. MAODV中基于双向链路有比较完善的维护机制.但在单向链路情况下，原有的路由修复机制会存在一些问题.目前国内外的研究中对于单向链路的处理主要有2种：一种是避免单向链路，如AODV-EUDA[1]和AODVUD[2]算法采用黑名单机制、RREQ包等待机制和Hello报文检测机制等方法；另一种是利用单向链路，如AntHocNet[3]和ORPUL[4]等，根据获得的链路状态信息和记录的单向链路节点，择优选择正向反向链路.然而，目前提出的改进思路主要是围绕单播路由进行的，几乎没有研究针对组播路由协议提出利用单向链路的有效改进方法.因此，笔者针对组播路由中的单向链路问题进行进一步的研究.
1 MAODV单向链路场景分析MAODV协议是基于双向链路来进行设计的，因此在单向链路出现时，协议的性能会受到影响.根据数据源在组播树上的位置以及单向链路的方向不同，分成4种场景，如图 1~图 4所示，分别对单向链路下MAODV路由修复进行讨论.
|
图 1 MADOV单向链路场景1 |
|
图 2 MADOV单向链路场景2 |
|
图 3 MADOV单向链路场景3 |
|
图 4 MADOV单向链路场景4 |
1) 如图 1所示，数据源在断链上游，上游节点A的通信范围小于下游节点B的通信范围，B→A可通信，A→B不能通信.下游节点B在一段时间收不到A的数据包或Hello消息后，判断A→B的链路不通，开始进行断链修复，重新发送消息加入组播树.而A由于单向链路一直能收到B的消息，未能及时检测到断链，因此会继续发送组播数据分组，但是下游节点B并不能收到来自于上游节点的数据.在本场景里，无论有无单向链路，由于数据源在断链上游，因此在断链修复过程中上游节点发送的组播数据都会被丢弃，此时单向链路的存在与双向链路断链对业务的时延和投递率的影响基本相同.
2) 如图 2所示，数据源在断链上游，上游节点A的通信范围大于下游节点B的通信范围，A→B可通信，B→A不能通信.上游节点A在一段时间收不到B的Hello消息后，判断B→A的链路不通，进行断链处理，但不对B进行任何通知.节点B经过一段时间收不到来自A的数据包或Hello消息，才判断A→B的链路断开，开始进行断链修复.此时，下游节点要等待2倍的断链发现时间才能触发路由修复.在本场景里，由于数据源在断链的上游，对于上游节点A而言，A关心的是下游节点B能否收到自己发送的数据，而不是B能不能把数据包发送过来.如果A能确定B可以收到自己的数据包，下游节点也没有必要立即进行断链修复.因此，可以利用这种单向链路，且不需要进行断链修复.
3) 如图 3所示，数据源在断链下游，上游节点A的通信范围小于下游节点B的通信范围，B→A可通信，A→B不能通信.下游节点B在一段时间收不到A的Hello消息后，判断A→B的链路不通，开始进行断链修复.此时，节点A可以单向收到B的信息. B节点通过其他树枝重新加入组播树中，继续向组播树发送来自下游数据源的数据.从B节点发现断链到重新加入组播树修复成功的过程中，经过的数据全部被丢弃.在本场景里，由于数据源在断链的下游，数据传输的方向为自下而上，对于节点B而言，B更关心的是上游节点A能否收到自己的数据.因此，若A能及时通知B自己能正常接收来自下游节点的数据，则B不必丢弃数据，不需要立即进行断链修复.
4) 如图 4所示，数据源在断链下游，上游节点A的通信范围大于下游节点B的通信范围，A→B可通信，B→A不能通信.上游节点A在一段时间收不到B的Hello消息或数据包后，判断B→A的链路不通，进行断链处理，但不向B发送任何通知.此后，下游节点B经过一段时间收不到来自上游节点A的Hello消息，判断A→B的链路断开，开始进行断链修复，通过其他组成员重新加入组播树.在本场景里，由于数据源在断链的下游，因此下游节点更希望上游节点在不能收到来自下游的数据时，立即主动通知自己进行链路修复，而不是被动地等待2倍的断链发现时间.并且下游节点一直认为链路是通畅的，会正常发送数据，而上游节点不会收到.
2 改进的MAODV-UNI协议为在单向链路存在的情况下进行快速有效的路由修复，笔者基于原链路修复机制提出了适用于单向链路的改进协议MAODV-UNI，具体步骤如下.
1) 当节点通过链路层检测机制或邻居间Hello消息检测到了链路损坏后，首先判断自己是这条链路的上游还是下游节点.如果是上游节点，再判断数据是否由它发至下游.如果有数据发送，则先将数据缓存.之后，上游节点单播一个RREP-P消息到下游，通知其自己收不到对方信息.如果是单向链路，则下游节点能收到此RREP-P消息.如果数据是从上游发来的，则此单向链路仍能使用，所以不需要修复，只需广播一个RREP-UNI消息，通知上游节点继续发送消息即可；如果数据是由下游发到上游的，则下游此时应立即发起路由修复.如果是双向链路断开，则此时下游节点虽然收不到RREP-P消息，但它也能检测到链路损坏，可以立即进行修复.
2) 若检测到链路损坏的节点是链路的下游节点，同样地再判断数据传输方向.如果有数据传向上游节点，则先将数据包缓存，之后判断自己是不是组成员，若是组成员，或虽不是组成员，但需要接收上游发送的数据，则不管场景如何，都发送RREQ-J重新寻路加入组播组.如果数据是由下游发往上游的，则此时若存在下游到上游的单向链路，可以充分利用而不用进行修复，所以此节点向上游节点单播一个RREQ-UNI消息，并设置定时器，在定时器停止前若收到RREP-UNI，说明下游到上游存在可用单向链路，不用做其他修复；如果定时器超时后仍未收到RREP-UNI，则发送RREQ重新进行寻路.
3) 当节点收到来自对方的RREQ-UNI时，说明对方到自己的单向链路是通的，此时应回复相应的RREP-UNI，但因为此时自己到对方方向链路不通，所以此RREP-UNI不能采用单播发送，而是采用广播形式发送，可经过多次转发到达目的节点.
3 MAODV-UNI仿真与分析在NS2下对改进后的协议MAODV-UNI进行仿真，并与原始的MAODV进行比较分析.
3.1 仿真场景设置仿真在500 m×500 m的通信面积中随机设置20个通信节点，节点分布相对密集.通过设置接收门限和降低节点发射功率来产生单向链路.随机选择几个节点，将它们的通信覆盖范围改为150 m，而其他节点保持250 m.从20个节点中选择6个节点加入1个组播组，由1个数据源向该组播组发送256 kB大小的数据包.场景中每个节点的移动模型为随机路点移动模型，由NS2自带的setdest工具生成.仿真时间为210 s.
3.2 评价指标选择以下3个最常用的指标来评估协议的性能.
1) 数据包投递率=目的节点收到的数据包数/源节点发送的数据包数；
2) 控制开销=发送和转发的控制包数/目的节点接收的数据包数；
3) 端到端时延=收到数据包的总时延/目的节点接收的数据包数.
3.3 仿真分析3.3.1 移动性影响网络中节点的移动性会造成网络拓扑的动态变化，从而导致链路的失效和单向链路的产生.观察在移动性影响下，MAODV和MAODV-UNI的性能.仿真时节点最大移动速度分别取值1 m/s、5 m/s、10 m/s、15 m/s、20 m/s，发包频率为10 packet/s，其他参数设置如3.1小节所述.在不同速度下分别进行10次仿真，计算投递率、开销和时延，剔除坏值，将结果取平均，得到仿真结果如图 5~图 7所示.
|
图 5 不同移动速度下的投递率 |
|
图 6 不同移动速度下的控制开销 |
|
图 7 不同移动速度下的端到端时延 |
由图 5可以看出，随节点移动速度的增加，网络动态变化变快，单向链路产生的几率变大，导致投递率整体呈下降趋势，但是幅度不大；相较于原始的MAODV协议，改进的MAODV-UNI协议的投递率有了明显提高.
由图 6可以看出，随着网络动态变化加快，链路损坏情况增多，所以修复消耗的控制消息增多，控制开销增加；因为MAODV-UNI修复过程中添加了RREP-P和RREQ-UNI等控制消息，所以它的控制开销比MAODV大.
由图 7可以看出，随着移动速度的增加，网络链路损坏较多，链路修复耗费一定时延，时延呈增加趋势；当单向链路较多时，MAODV-UNI机制中减少了单向链路情况下的等待时间，因此移动速度较大时MAODV-UNI的时延比MAODV小.
3.3.2 网络负载影响通过改变发包频率来改变网络的负载，观察在网络负载不断增大的情况下MAODV和MAODV-UNI的性能.仿真时将发包频率设置为变量，分别取值10 packet/s、20 packet/s、30 packet/s、40 packet/s、50 packet/s，节点最大移动速度为5 m/s，其他参数设置如3.1小节所述.在不同的发包频率下分别进行10次仿真，计算投递率、开销和时延，剔除坏值，将多次结果取平均，得到仿真结果如图 8~图 10所示.
|
图 8 不同发包频率下的投递率 |
|
图 9 不同发包频率下的控制开销 |
|
图 10 不同发包频率下的时延 |
由图 8可以看出，当发包频率变大时，网络的负载不断增加，容易产生碰撞和阻塞，导致链路出现问题，所以投递率呈下降趋势；但是可以看出，在这种情况下，MAODV-UNI的投递率比MAODV要高.
由图 9可以看出，当每秒发送的包数增加时，目的节点收到的总数据包数也增加，而控制消息只在寻路和维护时产生，增加得较少，所以控制开销是呈下降趋势的；因为在修复时增加了控制消息，所以MAODV-UNI的控制开销大于MAODV.
由图 10可以看出，当发包频率变大时，网络容易出现阻塞和碰撞，所以时延会增大；因为MAODV-UNI的修复机制中相对于MAODV减少了时延，所以在总的时延上，MAODV-UNI比MAODV少.
4 结束语主要针对单向链路问题，在MAODV基础上提出了新的路由修复机制MAODV-UNI，并在NS2仿真平台下构造了单向链路情况，进行了仿真，同时与MAODV进行了对比分析.
通过仿真结果可以看出，在单向链路情况下，改进的MAODV-UNI路由机制在整体性能上明显优于原来的MAODV路由机制，特别是在投递率方面，MAODV-UNI有显著提高.
| [1] | Ko Y B, Lee S J, Lee J B. Ad hoc routing with early unidirectionality detection and avoidance[J].Lecture Notes in Computer Science, 2004: 132–146. |
| [2] | Qiu Jingyi, Xu Jun, Xu Dexing. Optimized routing algorithm of Ad hoc mobile network with unidirectional links: AODVUD[J].Journal of Chinese Computer Systems, 2010(2): 206–210. |
| [3] | Gianni D C, Frederick D, Luca M G. AntHocNet: an adaptive nature-inspired algorithm for routing in mobile Ad hoc networks[J].European Transactions on Telecommunications, 2005, 16(5): 443–455. doi: 10.1002/(ISSN)1541-8251 |
| [4] | Venkataramanan K, Aravindan D, Ganesh K. On demand routing protocol to support unidirectional links in mobile Ad hoc networks[J].Lecture Notes in Computer Science, 2004, 3090: 144–153. doi: 10.1007/b99472 |