一种能量有效的多径Ad Hoc网路由算法

吴 慧， 侯 嘉

（苏州大学 电子信息学院，江苏 苏州215006）

0 引言

Ad Hoc网络多径路由的可靠性和网络资源利用率比单径路由高，国内外的专家学者就 Ad Hoc网络多径路由技术提出了不少建设性的方案[1-7]。每种路由协议都有各自的优缺点，很难设计出适合所有应用环境的路由协议，特别是有些应用环境对传输不同数据会有不同等级的可靠性和实时性要求，如果将所有数据按照统一的要求进行处理，将会对网络资源造成极大的浪费，缩短网络的生存时间。现研究一种能满足QoS需求的多路径多速率路由算法EAMM，该算法中的节点能根据数据的可靠性和实时性要求，结合地理位置、延迟时间、丢包率和剩余能量信息选择符合要求的若干条路径。仿真结果显示，该算法在保证各等级可靠性和实时性的数据按照要求传输的情况下能均衡网络的能量消耗，延长网络的生存时间。

1 算法参数介绍

1.1 速率的计算

首先是利用一种保证网络传输速率在一个全局定义的传输速率阈值之上的SPEED[8]协议思想。文中假设数据包的有效期限 treq和可靠性preq已知。源节点s根据数据的有效期限 treq和到目标节点d距离的ls,d计算出最小的传输速率：

对于中间节点i，其到达邻居节点j的速率为：

这里，τi,j是节点i到节点j传输延时的估计值。

1.2 节点丢包率的计算

每个节点 i保留的最近一段观察时间Δt内到邻居节点j的平均丢包率为：

其中，Nsend为在Δt内节点 i发送的数据包个数，Ndrop为在Δt内邻居节点j未收到的数据包个数。

1.3 能量消耗的计算

处理一个数据包所需要的时间为：

其中，L(n)表示第n个数据包的长度，B表示带宽。

发送和接收一个数据包的能量消耗分别为：

节点的剩余能量：

2 协议描述

前提假设：每个节点知道自己和它通信范围内的相邻节点的地理位置，并且会周期性地发送位置信息包进行更新。

2.1 路由选择策略

节点依据到邻居节点的传输速率reqV将邻居节点分成3种速率等级。源节点根据最小传输速率要求req

V将数据包划分到相应的速率层。此方法可以满足数据传输的实时性要求，但是并不能保证可靠性，还需要采取多路径机制。

节点i根据到每个邻居节点j的平均丢包率ei,j，预测出节点i经过邻居节点j到达目标节点d的概率：

源节点首先从邻居节点集中选择到目标节点 s的距离lj,d小于ls,d的若干个节点j，且将源节点s到目标节点d总的到达概率P设为0，然后，每增加一个转发节点，P就按式(9)更新一次：

当转发节点个数增加到使得reqP≥P时，就不再增加转发节点。数据包通过MAC层多播协议转发给邻居节点。选取多路径时并不是路径越短越好，为了负载的平衡和避开最短路径上剩余能量很低的节点，只要这条路径能在reqt内完成数据传输即可。同时，由于Ad Hoc网络节点的能量有限，节省节点的能量和延长整个网络的生存时间很重要。为此综合考虑转发概率和剩余能量E，引入节点稳定性因子：residual

2.2 中间节点处理数据包

中间节点i接收到数据包后，按照以下步骤处理数据包：①判断该节点不是目标节点且第一次收到该数据包。根据最小传输速率要求Vreq将数据包划分到合适的速率层；②根据公式(8)计算经过邻居节点j到达目标节点d的概率结合数据包的可靠性要求Preq和公式(9)计算转发节点个数m；③根据公式(10)计算邻居节点的稳定性因子Qnode，将满足要求的邻居节点按照Qnode由高到低排序，优先选取前m个节点作为转发节点；④将数据包发送给m个转发节点。

2.3 路由更新

同样，由于选择多个转发节点时是完全基于本地平均丢包率估计ei,j的，所以中间节点很可能会发现之前的估计信息不准确,需要采取动态补偿机制，及时地增加或者减少转发节点个数。

3 仿真实验

3.1 仿真环境

在windows操作系统下利用NS-2.31仿真平台对本算法进行仿真模拟,并和多播路由协议MAODV进行对比。地形设置为1000×1000的平面区域，节点个数50个。节点的传输距离为150 m，信道带宽为2 Mb/s。数据包大小为512 Byte。以恒定的CBR比特流模拟节点的实时业务。仿真结果如下，其中EAMM(a,b)中a表示可靠性，b表示数据有效期限。

由于 EAMM 考虑了数据包的可靠性和实时性要求，在路径选择过程中，综合考虑转发节点的这两方面性能，从而建立了具有QoS保证的路径。从图1和图2 可以看出，EAMM算法的数据包投递率和端到端延迟的性能都优于MAODV。图1中，当数据的有效期限都设为 0.5，可靠性分别为 0.65和0.8时，后者的数据包投递率高于前者，说明EAMM算法是有效的。图2中，当可靠性都设为0.65，有效期限分别为0.5和0.2时，后者的端到端延迟小于前者。图3表明，随着数据包发送率的增加，两种算法的网络生存时间都逐渐减少，EAMM的网络生存时间比MAODV长。原因是EAMM选择剩余能量高的节点传输数据，均衡了网络的能量消耗，延长了网络的生存时间。图1、图2和图3横坐标表示的发送率为每个数据包所用时间。

4 结语

本文研究了一种满足QoS需求的能量有效的多路径多速率路由算法EAMM，该算法中的节点能综合考虑地理位置、延迟时间、丢包率和剩余能量信息，选择符合要求的若干条路径，满足数据传输的可靠性和实时性要求，延长了网络的生存时间。仿真结果显示，与传统的多播路由协议相比，该算法是有效的自组网多路径算法。

[1] MARINAL M K,DAS S R. Adhoc on-demand Multipath Distance Vector Routing [J].Wirel Commun Mob Comput,2006(06):969-988.

[2] YU Ming, MALVANKAR A, SU Wei, et al. A Link Availability-based QoS-aware Routing Protocol for Mobile Ad Hoc Sensor Networks[J].Computer Communications, 2007,30(18):3823-3831.

[3] 曾文锋,戴建辉.能量感知和链路稳定度的多径MANET路由[J].通信技术,2011,44(08):54-57.

[4] 梁荣坚,蔡茂国,张立海.Adhoc网络中基于链路稳定度的QoS路由协议[J].计算机工程与应用,2010, 46(32): 105.

[5] 杨吟君,汪学明.基于AOMDV的多径路由协议改进及仿真分析[J].通信技术, 2011,44(08):45-47.

[6] 吕建军,李志蜀,刘勇.Ad hoc网络稳定的蚁群多路由算法[J].电子科技大学学报,2010,39(04):603-606.

[7] 刘军,彭宇扬,彭自成.MANET实时传输的可靠性研究[J].通信技术,2008,41(05):59-63.

[8] HE T, STANKOVIC J, LU C,et al. SPEED: A Stateless Protocol for Real-Time Commu- nication in Sensor Networks[J]. Proc. IEEE Int. Conf. on Distributed Computing Systems, 2003 (19-22):46-55.