能量感知和链路稳定度的多径MANET路由

曾文锋，戴建辉

（①长沙通信职业技术学院，湖南 长沙 410015；②华中科技大学 电子与信息工程系，湖北 武汉 430074）

0 引言

移动自组织网络（MANET，Mobile Ad hoc Networks）[1]是不依赖任何固定的基础设施，由一组移动节点组成的自治系统。MANET的移动节点带有无线收发装置，在网络中既是主机又兼有路由器的功能，网络建立展开快捷灵活。路由问题是移动自组网的主要挑战[2]，由于节点的随机运动造成的拓扑结构动态变化，增加了MANET中路由的难度。MANET中节点依靠电池供电，节电能延长网络的生存时间，而稳定的链路能够减少链路的频繁断裂。因此，链路稳定和节能是移动自组网络由协议面临的重要问题[3-4]。

在AOMDV[5-6]协议的基础上，综合考虑节点的剩余能量和链路的稳定度，提出了一种基于能量感知和链路稳定度的多路径MANET路由协议(ELMRP，Energy-awareness and Link-steady-degree based Multi-path Routing Protocol for Mobile Ad hoc Networks)。新协议在路由发现过程中搜集路径的能量和稳定度信息并计算路径代价值。根据路径代价，在多条节点不相交路径中分配数据分组流量。该协议有效地降低并均衡了AOMDV路由协议的能量消耗，延长了网络的生存时间，并提高了分组递送率。

1 AOMDV路由协议

AOMDV可以用来寻找节点不相交或链路不相交的路由。在节点路由表中，到同一目的的多条路径具有相同的序列号。所有不相交路径中最大的跳数值称为广告跳数(AHC，Advertised Hop Count)，用来传播目的节点的路由广播。节点通过接受到的重复的路由广播，构造到目的的多条不相交路径。为了确保避免环路，节点只处理到相同目的节点的跳数小于广告跳数的路由广播。因为广告跳数使用了最大跳数值，所以相同序列号的广告跳数不会改变。当节点接受到了序列号更大的路由广播，删除所有的下一跳节点列表并重新初始化广告跳数。

AOMDV为了寻找节点不相交路由，节点并不立即拒绝重复的RREQ。通过源节点的不同的邻居节点到达的每个RREQ确定了一个节点不相交路径。这是因为节点不广播重复的RREQ，通过源节点的不同的邻居到达中间节点的两个RREQ不可能经过同一个节点。当寻找多个链路不相交路由时，目的节点响应接收到的每个RREQ而不考虑它们的第一跳。为了在RREP的第一跳节点确保链路不相交的特性，目的节点仅对通过不同的邻居到达的RREQ发送相应的RREP。在第一跳之后，RREP沿着节点不相交的反转路由发送至源节点。每个RREP的可能会在中间节点相交，但是不同的反向路由可以保证链路不相交特性。

AOMDV路由协议的在寻找到达目的结点的路径时，不仅是找出一条路径，而是找出多条路径存储起来，根据规则选择其中一条较好的路径传输数据分组。与单路由协议相比具有很大的优点：当所采用的路径中的链路断开时，不用重新进行路由发现，只需从维护的其它路径中找出一条来代替就可以了。

2 链路稳定度

Ad hoc网络中正在通信的两节点，在已知节点通信范围、节点位置、运动方向和速度的条件下，可以预测两节点的连接时间。节点间预期的连接时间，称为链路稳定度(LET，Link Expiration Time)[7]。

在Ad hoc网络中利用移动节点的全球定位系统(Global Position System, GPS)提供的位置和移动信息，可以计算链路连接度LET。LET计算公式定义如下：

式（1）中LET为两节点保持连接的预期最大时间，式中r为节点的信号有效传输距离，(xi, yi)、(xj, yj)分别为节点i、j的坐标，vi、vj为节点运动速度，θi、θj为运动方向。若节点运动速度和运动方向确定，则对处于不同位置的两节点的连接时间就可通过公式计算出来。当保持连接的两节点主机的方向与速度都一致时，LET为无穷大，则可一直保持连接。若LET为负数，则认为两节点不能保持连接。预期连接时间长的链路即LET值大的链路，具有更高的稳定度。

3 ELMRP路由协议

ELMRP是在AOMDV协议基础上的改进。ELMRP引入了路径的剩余能量和路径稳定度的概念。路径剩余能量E和路径稳定度S定义如下：

其中，从源节点的ns到目的节点nd的路径P=ns, n1, n2,…,nd，ek为P上中间节点k的能量，L为路径P上的链路集合，sk为路径P上链路k的稳定度。

ELMRP采用了AOMDV的路由发现机制查找多条节点不相交路径，在路由发现的过程中搜集路径的剩余能量和路径稳定度的信息，并根据代价函数计算路径的代价。通过在RREQ和RREP分组中分别加入2个字段energy和let，用来传播路径的能量和稳定度。

源节点通过向所有的邻居节点广播 RREQ发起路由发现过程。若将RREQ到达节点ni所通过的节点ni的邻居节点记为nj，源节点为ns，则节点ni接收RREQ的处理过程如算法1。

算法1：节点ni接收RREQ的处理算法

路径P的代价函数定义如下：

在式(4)中，ρ为权系数，决定了路径剩余能量E和路径稳定度S对于计算代价值的影响。通过改变ρ的值，可以调整E和S对于代价值的影响。当ρ等于1时，代价值由完全E决定；当ρ等于0时，代价值完全由S决定；当ρ在0和1之间时，代价值按照比例由E和S共同决定。在本文的仿真中ρ取值为0.5。由公式(4)可以看出，剩余能量大和路径稳定度大的路径具有较小的代价值。

目的节点接收到RREQ，根据携带的信息生成RREP。丢弃RREQ，沿反向路径发送RREP。节点接受并处理RREP的算法与算法(1)类似，建立多条到目的节点的节点不相交路径，并根据RREP携带的信息计算路径代价。

源节点接收到RREP，路由发现过程完成，源节点和目的节点间建立起多条节点不相交路径，源节点开始向目的节点发送数据分组。ELMRP路由协议在发送数据分组时，选择了与AOMDV路由协议不同的策略。

AOMDV路由协议中，所有的数据分组都经过跳数最小的路径传输。因而在最小跳数路径上的各节点，能量消耗的速度比其他不相交路径上的节点更快，导致了各不相交路径上的节点的剩余能量不平衡。而在ELMRP路由协议中，根据路径的代价值，在多条结点不相交的路径上分配数据分组的流量。对于代价值小的路径，即路径的剩余能量和路径稳定度的路径，具有更大的数据流量。

在图1所示的网络拓扑中，源节点A到目的节点E有3条节点不相交的路径，AOMDV中所有的数据分组都沿着跳数最小的路径A－F－G－E发送。而ELMRP路由协议中数据分组在A－B－C－D－E，A－F－G－E和A－H－I－J－E三条路径中按照代价值分配数据分组流量。

ELMRP路由选择机制可以描述为：对于给定的源节点ns和目的节点nd，所有可能的路径集合P，对于多条节点不相交路径，选择满足的n条路径。EL MRP中数据分组选择第i条节点不相交路径pi的概率probi如下：

图1 一个网络拓扑结构

4 协议仿真

4.1 仿真环境

我们在NS2[8-9]仿真软件上实现了ELMRP。仿真场景由100个移动节点组成，随机分布于1000 m×1000 m的矩形区域；链路层采用IEEE802.11协议；节点停留时间为0；利用setdest生成7个仿真场景，节点平均移动速度分别为1 m/s，2.5 m/s，5 m/s，7.5 m/s和 10 m/s。

通信模型采用CBR数据源，共有50个通信对，数据分组大小为512 byte，发送分组速率1 packet/s。

4.2 仿真结果

在5个不同的场景中对ELMRP协议与AOMDV协议分别进行了仿真试验，对产生的 trace文件进行处理分析，着重于网络生存时间，分组递送率路由发现频率的比较。

协议的网络生存时间比较如图2所示。随着节点运动速度的增加，两种协议的网络生存时间的曲线均呈下降的趋势。在所有的5个仿真场景中，ELMRP比AOMDV的具有更长网络生存时间，最大的差距到达40 s。AOMDV由于数据分组集中于最短的路径发送，因而最短路径上的各节点比其它路径上的节点的电池能量消耗更快，更早消耗完电池能量；而ELMRP按照路径能量和稳定度计算出的代价值，在多条不相交路径中分配数据分组的流量，较稳定并且剩余能量较大的路径上承担较多的分组流量，均衡了各个路径上节点的能量消耗速度，因而延长了网络生存时间。

图2 网络生存时间比较

协议的分组递送率比较如图3所示。在节点低运动性的场景中，两种协议都表现了较好的性能，均在90%以上。随着节点运动加剧，协议的分组递送率下降。ELMRP比AOMDV的分组递送率平均提高了约3%。ELMRP在评价路径质量计算代价值时，考虑了路径的稳定度，稳定的路径分配了更多的流量，因而减少了路由失效的次数，提高了数据分组递送率。

图3 分组递送率比较

协议的路由发现频率比较如图4所示。从图4可以看出，ELMRP路由发现频度在 5个场景中均低于 AOMDV。ELMRP路由协议中除了路径上节点的剩余能量，稳定度也是路由评价的标准之一。在路由发现的过程中建立的多条节点不相交路径中，稳定的路由具有更小的代价值。数据分组更多的通过稳定的路径，因而减少了路由失败的次数并避免了再次的路由发现。

图4 路由发现频度比较

5 结语

移动自组织网络中的路由问题一直以来是研究的热点领域。本文在AOMDV的基础上提出了一种新的按需路由协议ELMRP。该路由协议充分考虑路径的剩余能量和稳定度，在多条不相交路径中根据代价值分配网络数据分组流量。较稳定并且剩余能量较大的路径上承担较多的分组流量，因而均衡网络中各节点的能量消耗速度，延长了网络的生存时间，提高了分组递送率，降低了路由发现频度。

[1] RAMANATHAN R, REDI J.A Brief Overview of Mobile Ad hoc Networks:Challenges and Directions[J].IEEE Communications Magazine,2002, 40(05): 20-22.

[2] 陈世奎, 李腊元.移动自组网路由协议AODV的性能研究[J].交通与计算机, 2006, 24(06): 122-124.

[3] 葛安峰,王华,王海龙.基于链路稳定性的 MANET组播路由协议[J].计算机工程与应用, 2011, 47(12): 75-79.

[4] 朱斌,曾孝平,廖红云,等.能量高效与移动预测的路由算法分析[J].重庆大学学报, 2010, 33(10): 88 - 93.

[5] MARINA M K, DAS S R.On-Demand Multipath Distance Vector Routing in Ad hoc Networks[J].Mobile Computing and Communications Review, 2002, 6(03): 92-93.

[6] MARINA M K, DAS S D.On-demand Multipath Distance Vector Routing in Ad Hoc Networks[C].Proceedings of IEEE International Conference on Network Protocols (ICNP 2001),Riverside, USA, 11-14, 2001:14-23.

[7] LEE Sung-Ju, SU William, GERLA Mario.Wireless Ad Hoc Multicast Routing with Mobility Prediction [J].Mobile Networks and Applications, 2001, 6(04): 351-360.

[8] 于斌,孙斌,温暖,等.NS2与网络模拟[M].北京:人民邮电出版社,2007: 1-5.

[9] 黎方正.基于 NS2的航空自组网节点移动模型仿真研究[J].通信技术, 2009, 42(01): 186-188.