基于路径稳定性的MAODV路由协议的改进

李帅　蔡明

摘 要： 在Ad Hoc网络中，节点随意快速的移动通常会造成网络拓扑结构的剧烈变化，可能导致传输链路断裂和路径的不稳定。针对这种情况，在分析现有MAODV路由改进技术的基础上，提出了一种改进的、基于路径稳定性的路由协议（RS?MAODV）。新协议与MAODV不同的地方在于：考虑构成路径的链路间的相关性，选择最稳定的路由进行数据传输，以此改善网络性能。利用NS2仿真工具对改进前后网络的丢包率及端到端延迟参数做比较，实验数据表明，改进后协议的网络丢包率及端到端延迟均得到改善。

关键词： 无线自组织网络； 路由协议； 路径稳定度； 网络仿真

中图分类号： TN915.04?34； TP393 文献标识码： A 文章编号： 1004?373X（2015）05?0001?04

MAODV routing protocol improvement based on stability of path

LI Shuai， CAI Ming

（IOT Engineer School， Jiangnan University， Wuxi 214122， China）

Abstract： In Ad Hoc networks， random movement of nodes usually causes severe changes of network topology， which may possibly result in breakage of transmission links and instability of routing path. In view of this situation， based on the analysis of existing MAODV routing improvement technology， an improved routing protocol named RS?MAODV is put forward. The diffe?rence between the new protocol and MAODV lies in that the new routing protocol chooses path with highest stability for data transmission to improve the network performance while considering the correlation between links. The simulation tool NS2 is used to compare the packet loss rate and end?to?end delay parameters before and after improvement. The experiment results that the packet loss rate and end?to?end delay of the improved protocol are better than before.

Keywords： wireless Ad Hoc network； routing protocol； path stability； network simulation

0 引 言

无线自组织网络，又称Ad Hoc网络，是一类由大量移动的、配备有无线收发装置的节点组成的网络，具有多跳、自组织、分布式等特点[1]。该类型网络由于布设灵活，不依赖于预设的固定基础设施，受环境、气候、地理位置等因素影响较小，被广泛应用于灾害预警、桥梁工程、生态监测等领域。然而，Ad Hoc网络中节点的位置会随其移动不断发生变化，从而造成网络拓扑变得不稳定。这种不稳定的变化可能会导致某条正在通信的路由断裂，甚至有可能造成网络分段的严重后果，因而路由的稳定性逐渐成为Ad Hoc网络中研究的热点之一。

MAODV[2]是一种经典的多播路由协议，是无线自组织网络中按需距离矢量路由协议AODV[3]的多播扩展。MAODV是基于树转发结构的多播路由协议，目前，在路由选择过程中，采用最大序列号或最少跳数的路由选择机制，即在源节点和目的节点之间选择一条最短的连通路径，很少考虑所选路径是否稳定。在一些MAODV的改进方案中，为保证路径的稳定性，常使用的解决方法是为链路建立一条备用链路，当原链路遭到破坏时使用；要么是根据链路断裂的时间进行预测，在链路断裂前主动进行修复[4?5]。然而，备用链路也不一定稳定，组成备用链路的节点也会有移动，仍可能导致备用链路的断裂。另外，在这些方案中，均假设相邻链路间是独立的，没有考虑链路的相关性，这与现实中网络的实际情况不符。因而，在现有稳定性理论研究[6?8]的基础上，同时考虑相邻链路的相关性和路径的稳定性，提出了一种基于路径稳定性的路由协议RS?MAODV。在改进后的协议中，为解决路径稳定性的问题，引入两个度量值：链路稳定度SPL；路径稳定度SPR。这两个度量值分别用来衡量链路和路径的稳定程度。在路由选择过程中，选取最稳定的路由作为源节点和目的节点间传输信息的路径。

1 RS?MAODV路由算法

1.1 算法设计思想

大多数路径稳定性算法都基于熵[9]的构造理论，用改造后的熵表示路径的稳定性。然而这种熵的构造主要是通过局部节点的运动变化情况决定的，仅考虑了节点的运动速度，没有考虑节点间的距离因素。在改进后的稳定性算法中，为提高稳定性选择的准确性，通过链路的可持续时间来预测链路的稳定度。

稳定度被定义为在时间间隔Δt内，网络或局部范围内节点相对位置的变化程度。在Δt时间内，假定互为邻居的节点仍在彼此的覆盖范围内。不难推测出，如果节点i和其覆盖范围内的节点（即邻居节点）在Δt内相对位置变化程度剧烈，则说明节点i无线覆盖范围内的拓扑结构稳定性较差，反之稳定性越好；如果某条路径上的节点与其上、下游节点在时间间隔Δt内相对位置变化剧烈，则说明该节点与其上、下游节点组成的链路稳定性较差，包含这些链路的路径稳定性也较差。

在Ad Hoc网络中，源节点和目的节点间的通信往往通过多跳转发实现的，因此，源节点到目的节点的路由通常由一系列链路组成，如图1所示。不难推测，路径中任一条链路的断开都将导致整条路径的断裂和不可用，路径的稳定度主要取决于组成它的各段链路的稳定度。因此，要计算路径的稳定度SPR，一个可行的求解思路是先求出组成该路径的每一段链路的稳定度SPL，然后根据链路和路径的组成关系最终求出路径的稳定度。路由的选择依据路径的SPR值来确定。

链路的稳定度通过链路维持时间预测的方式获取。多数情况下，为处理方便，均假设网络中组成路径的各段链路间彼此相互独立，此时路径的稳定度用链路稳定度联乘法[10]计算得出。然而在实际应用网络中，相邻链路间往往是相关的，为此还需要考虑链路间的相关性。这种情形下路径稳定度的计算方法相对复杂，在网络模型部分详细给出。

1.2 网络模型和标记

将网络抽象为无向图结构G=（V，E），其中V是网络中节点的集合，E是网络中节点间有效链路的集合。这里假设网络中所有节点的特征相似，如其无线覆盖半径相等，记为R。有效链路指此链路为双工类型的链路，双工链路指组成此链路的两节点相互在对方的无线覆盖范围内，彼此间进行双向信息传输，链路两端的节点既是信息的发送方又是信息的接收方，如图2所示。

1.2.1 链路的稳定度SPL

假设节点i和节点j在彼此的覆盖范围内并能互相发送接收消息，则节点i，j构成的链路即称为有效链路，也称节点i和节点j互为邻居节点。如果某时刻节点i移出节点j的无线覆盖范围，则节点i将接收不到节点j广播的位置消息。假设节点i在时刻tk的位置向量表示如下：

[pos（i，tk）=（xi，yi）] （1）

用同样的方法求出节点j在时刻tk的位置向量，那么节点i和节点j在时刻tk的相对位置向量为：

[pos（i，j，tk）=pos（i，tk）-pos（j，tk）] （2）

假设互为邻居的节点i和节点j在时刻tk的地理坐标分别为[xi（tk），yi（tk）]和[xj（tk），yj（tk）]，那么在时刻tk，两节点之间的距离求解公式如下：

[pos（i，j，tk）=（xi（tk）-xj（tk））2+（yi（tk）-yj（tk））2] （3）

在公式（3）中，由图2可知，[pos（i，j，tk）∈][0，R]。

那么在Δt=tk-tk-1时间间隔内，节点i和节点j的相对位置变化量Δdij为：

[Δdij=pos（i，j，tk）-pos（i，j，tk-1）] （4）

由于假设在Δt持续时间内节点i和节点j仍互为邻居节点，可以推测得知Δdij∈[-R，R]，那么[Δdij∈[0，R]，]即计算出在取值区间[0，R]上相应的链路稳定度的值[SPL=Δdij，]其中R表示节点的无线传输半径。为方便处理，对链路稳定度的求解公式做一些调整，处理后稳定度求解表达式如下：

[SPL=1-ΔdijR] （5）

式中：[Δdij]表示Δt时间间隔内节点i和节点j相对位置变化量的绝对值，根据图2与式（4）可得SPL的取值区间为[0，1]。从公式（5）中还可推断出，SPL值越大，节点i和节点j在Δt时间间隔内相对位置变化就越小，说明此链路越稳定，越不容易发生断裂；SPL值越小，节点i和节点j在Δt时间间隔内相对位置变化就越大，节点i相对节点j的局部拓扑结构变化剧烈，此链路越不稳定，发生断裂的可能性越大。

1.2.2 路径的稳定度SPR

由上面论述可得知，路径的稳定度是路由选择最基本的依据，路径的稳定度取决于构成路径的各段链路的稳定度。多数处理模型中，为处理方便，均假设各链路彼此间独立，不存在相关性关系，这时可用连乘法得到路径的稳定度。此时，路径的稳定度求解公式如下：

[SPR=i=1nSPLi] （6）

然而，在实际的Ad Hoc应用网络中，组成路径的各链路间往往是存在相关性关系的。例如，节点1和节点2之间存在链路时，节点1和节点3之间链路的存在将使得节点2、3之间更有可能存在链路。此时求解路径稳定度的公式为：

[SPR=SPL1×f（ρ1）×min{SPL1，SPL2}SPL1…fm-1（ρm-1）×min{SPL（m-1），SPLm}SPL（m-1）] （7）

式中：SPR为所求路径的稳定度；SPL1，SPL2，…，SPLm分别表示组成路径的各段链路的稳定度值；ρ1，ρ2，…，ρm-1分别表示各相邻链路之间的相关因子，详细计算方法见参考文献[11]；f1（ρ1），f2（ρ2），…，fm-1（ρm-1）分别表示各相邻链路间的相关性结构。这里，相关性结构fi（ρi）[（1≤i≤m-1）]利用如下公式求得：

[fi（ρi）=max{SPLi，SPL（i+1）}×ρi+max{SPLi，SPL（i+1）}（2×max{SPLi，SPL（i+1）}-1）×ρi+1] （8）

以上为链路稳定度和路径稳定度的求解方法，下面详细介绍算法相应流程。

1.3 算法流程概述

由于网络中节点是不断移动的，所以节点均配备GPS无线定位装置，目的是获取自身的地理位置信息，并定时在其无线覆盖区域内广播最新的地理位置信息，邻居节点收到后更新相应信息。节点在向邻居节点广播位置信息时，节点的跳数值设置为1，表明此节点仅向邻居节点发送数据包。整体路由过程如图3所示。

算法在路由发现阶段的操作流程如下：

（1） 当源节点想要向多播组成员发送数据分组时，源节点首先会检查其路由表项中是否含有到达该多播组的路由，如果有的话，会沿此路径以单播的方式向多播组发送消息，否则，源节点会广播路由请求消息RREQ到其邻居节点，用以开启路由发现过程。

（2） 中间节点接收到路由请求消息RREQ后，先检查自身是否有到达多播组的路由或者是多播组的某个成员节点，如果是的话，则会检查自身路由表项中的组序列号是否大于或等于RREQ消息中的序列号；如果两个序列号相等，则会检查其路由表项中记录的跳数是否小于RREQ消息中的跳数。如果该节点路由表项中没有到达多播组的路径或不是多播组成员，则继续广播RREQ消息。

（3） RREQ消息到达多播组的成员节点后，收到RREQ消息的节点会更新自身路由表项并记录下序列号。随后会产生路由回复消息RREP，此消息包含路径稳定度域SPR，用来记录从多播组成员节点到达源节点所经路径的稳定度值，初始化SPR=1；另外，还包含路由跳数域count，用来记录所经路由的跳数，初始化count=∞。RREP消息会沿相反方向返回至源节点，中间节点收到RREP分组后，更新count值并计算相应段链路的稳定度值，进而计算并更新从多播组成员到该节点的路径的稳定度值SPR，直到该RREP分组到达多播源节点。

算法在路由选择阶段的操作流程如下：

多播源节点以广播方式发送路由请求消息RREQ以后，会等待一段时间。在这个时间段内，多播源将不断接收返回的RREP分组，同时会记录下分组中的最大序列号和最大路径稳定度，并更新相应路由信息。之后源节点会发送激活消息MACT到提供最大序列号和最大路径稳定度的邻居节点，用于激活该节点成为路径的上游节点。被选中的邻居节点收到MACT消息后将激活路由表项中相应到组地址的路由项，并把MACT消息转发给下一跳路由节点，这样一步一步进行下去，最终激活从多播源到多播组某成员的路径上的所有中间节点的路由项。

2 仿真实验

仿真实验采用NS2[12]网络模拟软件作为仿真工具，在Ubuntu的操作环境下，对本文提出的改进协议RS?MAODV和MOADV路由协议进行了仿真比较。本文采用的NS2版本是2.35，通过NS2软件的仿真实验，比较了不同移动速度下两协议对应的丢包率和端到端时延。

仿真环境设置如下：仿真场景长1 500 m，宽300 m；节点无线传输半径为100 m；MAC层协议：IEEE 802.11；节点数50个，其中源节点个数为1个。节点移动速度范围设置为1～10 m/s；数据类型为CBR，分组大小为512 B，发包速率为2 packets/s。在仿真环境下运行，使用Linux环境下awk[13]工具对网络模拟产生的追踪tr文件进行数据计算和分析，比较了不同移动速度下协议改进前后相应的丢包率和端到端时延。

2.1 丢包率

丢包率指数据包丢失数量与应接收数据包总数的比值。在无线多播情形中，假设单个源节点向包含N个目的节点的多播组传送a个分组，多播组收到分组总数为b个，则丢包率为[（Na-b）Na。]实验中考察了不同移动速度下MAODV和RS?MAODV协议的丢包率情况，实验结果如图4所示。

通过图4可以看出，随着网络中节点移动速度的增加，MAODV和RS?MAODV协议的丢包率均增加。这是因为随着节点移动速度的增加，网络拓扑结构变化剧烈，已有链路可能遭到破坏，网络中拥塞程度加剧，分组间碰撞的可能性增大，整个网络性能随之下降。然而，在同一移动速度下，RS?MAODV协议由于每次选择局部拓扑变化小的路径进行数据传输，使得相同条件下路由中断和重构次数减少，丢包率也相应较小。

2.2 端到端延迟

端到端延迟是指数据包的接收时间和发送时间之差。实验中测定了不同移动速度下两种协议的端到端延迟，实验结果如图5所示。

从图5中观察到，一定节点移动速度下，MAODV协议比RS?MAODV协议的端到端延迟要小，这是因为MAODV协议选择一条从源节点到多播组的最短连通路径，使得相应端到端延迟要小。随着网络运行时间的增加，网络拓扑结构发生变化，用于数据传输的路径不断遭到破坏，网络拥塞程度加剧，两种协议对应的端到端延迟均变大。然而RS?MAODV协议由于考虑了所选路径的稳定性，减少了因节点失效引起的路由恢复和重构的时延，在相同条件下，相比MAODV协议端到端延迟也较小。

3 结 语

本文在研究前人MAODV协议改进技术的基础上，提出了一种改进的、同时考虑相邻链路的相关性和路径稳定性的路由协议RS?MAODV。在RS?MAODV路由协议中，引入链路稳定度和路径稳定度两参数，保证了选择的从源节点到多播组之间的路由是最稳定的，一定程度上提高了路径的稳定性，改善了网络的性能。但求解稳定度时需要计算操作，无疑增加了不必要的开销，下一步工作将集中在减少网络开销上。

参考文献

[1] 闫丽丽，彭代渊，高悦翔.Ad Hoc网络中认证路由协议的改进及其安全性分析[J].电子科技大学学报，2011，40（4）：578?581.

[2] 蔚成英，戴翠琴，雷芳.基于改进MAODV协议的WMN的组播路由算法[J].计算机与数字工程，2012，40（1）：25?28.

[3] 徐文涛，晁爱农.一种移动Ad Hoc网AODV路由协议的改进方法[J].计算机应用与软件，2013，30（3）：225?228.

[4] ZHAO Xin， CHOU Chun?tung， GUO Jun， et al. Protecting multicast sessions in wireless mesh networks [C]// Proceedings of the 31st IEEE Conference on Local Computer Networks. [S.l.]： IEEE Press， 2006： 111?116.

[5] 黄钱飞，万俊，邱海燕.移动自组织网中基于链路预测的路由研究[J].电脑与电信，2012（8）：36?38.

[6] 夏辉，贾智平，张志勇，等.移动Ad Hoc网络中基于链路稳定性预测的组播路由协议研究[J].计算机学报，2012，36（5）：926?935.

[7] 余夕亮，陶洋，黄宏程.基于路径稳定性的MANET路由协议研究与改进[J].计算机工程与应用，2012，43（36）：157?159.

[8] 严秋实，万晓瑜，樊自甫.基于路径稳定性的MAODV改进路由协议[J].计算机工程，2010，36（20）：93?95.

[9] 徐建娥，王新华，朱砚生.Ad Hoc网络中基于熵的QoS多播路由研究[J].电脑知识与技术，2008，7（4）：1634?1636.

[10] 赵继红，金依绅.基于移动预测的MESH网络稳定性算法研究[J].无线通信技术，2012，7（4）：6?10.

[11] ZHANG Hui， DONG Yu?ning. A novel path stability computation model for wireless Ad Hoc networks [J]. IEEE Procee?dings， 2011， 12（14）： 928?931.

[12] 肖权权，段迅.基于NS2的网络仿真与性能测试[J].计算机技术与发展，2012，22（4）：25?28.

[13] 蔺绍良，龙海南.基于稳定性的AODV协议的研究与仿真[J].微型机与应用，2013，32（20）：48?50.