基于Ad hoc 能量均衡的AODV 协议改进

屈长青 李玲香

（湖南科技学院 计算机与通信工程系，湖南 永州 425199）

1 引言

移动Ad Hoc 网络是由一组带有无线收发装置的移动节点组成的一个多跳的临时性自治系统，网络中的节点主要靠电池供电，属于一种能量受限节点，如果不考虑节点的能量，就很容易使某些节点成为主要的中间节点，从而使得这些节点过早的死亡，影响整个网络的生存时间。根据移动Ad Hoc 网络路由协议的特殊性，近年来国外学者提出了多种移动Ad Hoc 网络路由协议，如DSDV[1]、DSR[2]、AODV[3]、ABR[4]、TORA[5]等。源头性的研究性工作主要集中在2001 年以前，后续的成果多为对这些协议的改进。

目前，路由协议的研究仍然是移动Ad Hoc 网络研究成果最集中的部分。基于节点能耗的节能算法备受研究者的关注，在节点能量受限的情况下，正在进行对节省能耗和均衡能耗的深入研究，将节点能量的使用情况转化成数据通过控制信息传输，用节点的能耗情况作为最终路由选择的准则等。文献[6]提出了一种具有终端节点能量感知的路由协议EARP，在一定程度上实现了负载均衡，保护了低能量节点。文献[7]应用全球定位系统（GPS）提供的信息作为启发式信息，以减少网络维护的开销，有效降低了通信延时，但同时，GPS 又增加了新的能耗。文献[8]在AODV 协议的基础上通过中间节点对链路平均能耗的估算来进行选路，对过度使用的中间节点进行了有效保护。

本文针对Ad hoc 网络中移动节点能量受限的问题，综合考虑节点剩余能量和节点能量消耗速率两方面因素，对AODV协议进行了研究，提出了如下改进：1)改进选路机制，将节点剩余能量与数据传输能耗的比作为控制信息，根据不同的业务确定不同的比值，节点以“量力而行”或“尽力而为”的方式进行数据发送；2)改进Hello 机制，通过侦听相邻节点的有效发送来代替Hello 信息。

2 选路机制改进

改进选路机制，其目的是既要尽力保证AODV 路由协议的优点，又要保证链路中主要的中间节点不至于过早失效，从而保护低能量节点，延长网络生存时间。

设所有相邻节点具有相同的覆盖能力，每个节点的实时剩余能量为E(t)，节点能感知自己的剩余能量，业务数据传输能耗为E(d)，令节点剩余能量与数据传输能耗的比E(t)/ E(d)=K，以K 作为节点是否参与路由的控制信息。

考查实时业务RTT（Real Time Traffic） 和尽力而为BET（Best Effort Traffic） 两类业务，协议约定，对于实时业务，K 取值K（rtt），对于尽力而为类业务，K 取值为K（bet）。

2.1 路由请求

将业务类型，节点数据传输能耗引入路由请求，路由请求（RREQ）消息格式如图1。

图1 . 改进的路由请求（RREQ）消息格式

改进的路由请求消息的格式增加标志位和字段：T（Traffic flag 业务类型标志）：标志置位则表示尽力而为业务。

Data Transmission Energy Consumption（数据传输能耗），节点转发本次数据所要消耗的能量，即E(d)。

节点要发送数据时，首先检查自己路由表中是否有可用的有效路由，若没有现成可用路由，则向邻居节点发送RREQ。

2.2 RREQ 处理和转发

当一个非目标节点接收到一个新的有效 RREQ，查看 RREQ 中的标志位 T，以确定业务类型，查看Data Transmission Energy Consumption（数据传输能耗）字段，读出数据传输能耗值E(d)，读出自己的剩余能量E(t)，计算自己的K，对于实时业务，若K≤K（rtt）,或者对于尽力而为类业务，若K≤K（bet）, 那么这个节点会丢弃这个RREQ，不作任何操作。否则，节点将按AODV 协议对EERQ 进行处理和转发。首先，该节点会将RREQ 消息内的跳数加一，表明该RREQ 又跳过了一个中间节点。然后该节点使用最长前缀匹配法搜索到发起节点IP 地址的反向路由，如果有必要，这条路由会被创建，或者用RREQ 消息内的Originator Sequence Number 来更新[9]。

2.3 路由回复

目标节点接收到有效RREQ 消息，忽略其中的标志位T 和Data Transmission Energy Consumption（数据传输能耗）字段，创建一条路由回复消息RREP；如果接收到有效RREQ 消息的中间节点，它到目的节点有一条有效路由，则可直接向发起节点发送RREP 完成路由发现过程。

RREP 一旦被创建，RREP 消息就将被送往通向发起路由询问的节点的下一跳节点，这个节点由路由表里通向发起节点的路由表项给出。当RREP 被转发回发起节点时，它里面的“跳数”逐跳加一，确保当RREP 到达发起节点时，往返跳数一致[9]。

3 Hello 机制改进

在AODV 中，活动路由中的节点通过广播本地Hello 消息提供连接信息，每经过HELLO_INTERVAL 毫秒，节点检查它在过去的HELLO_INTERVAL 是否发出了一个广播消息。如果没有，就播出一个TTL = 1 的Hello 信息RREP，RREP 信息字段设置如下：

目的IP 地址：此节点的IP 地址。

目的序列号：此节点的最新序列号。

跳数：0。

生命期：ALLOWED_HELLO_LOSS * HELLO_INTERVAL。

每当一个节点从临近节点收到一个Hello 消息，该节点应该确保它与此临近节点有一条活动的路由，如果没有，则创建一条， 如果一条路由已经存在，那么这条路由的生命期应该增加至少ALLOWED_HELLO_LOSS * HELLO_INTERVAL 毫秒。

Ad Hoc 网络的传输是基于同频共享信道时分收发分配技术的，因此当节点处于有效发送时，在传输能力覆盖范围内的相邻节点都能够接收或侦听到该节点发送的信息，尽管它可能不做任何处理。AODV 协议中的Hello 消息独立于业务范围之外固定周期性地广播，在网络业务负载相对较重的情况下，会导致网络传输效率下降，增加网络负载，进而增加网络时延和节点能耗。

对Hello 机制改进如下：取消独立于数据业务之外固定周期性地广播的Hello 消息，通过侦听相邻节点的有效发送来提供连接信息。在RREP、RERR 等控制消息及业务数据包中增加一个Hello 消息标志H，如有必要，增加Hello 消息中的目的IP 地址和目的序列号字段。通过定时器，H 每隔HELLO_INTERVAL 毫秒置位，以避免相邻节点的频繁处理，置位维持时间为ALLOWED_HELLO_LOSS * HELLO_INTERVAL 毫秒，即与原Hello 消息包的生命期一致。

节点侦听相邻节点的有效发送时，若发现标志位H 置位，则读取在相邻节点上发送的控制消息或数据包中的目的IP 地址和目的序列号字段值，按AODV 协议的Hello 消息机制进行处理。

节点处理算法如下：

Procedure Packet process

If（侦听到的标志位H 置位）

Then （读取相关信息）

Then （更新、建立路由）

Else （继续侦听）

4 结束语

研究改进基于能量均衡的路由，可以使节点在不影响网络整体性能的前提下有更长的工作期，进而使整个网络维持更长的生命期。实验验证本文的算法能满足多种业务的传输要求又能均衡全局网络节点能量消耗，并且能够延长网络的有效生命周期。进一步的研究工作重点是将本文提出的路由改正机制作进一步的深化研究，具体从如下几个方面努力：

（1）在能量消耗和节点路由上做进一步客观的、动态的均衡，对实时业务和尽力而为业务动态、合理地选择相关阈值K（rtt）、K（bet），使网络中的能量消耗更公平，负载更均衡；

（2）进一步均衡和减少路由建立的能量损耗和时间开销；

（3）根据实际移动Ad Hoc 网络的不同要求来提高协议某些方面的QoS 性能。

[1]Charles E Perkins. Highly dynamic destination-sequenced distance-vector routing for mobile computers.In: Proc ACMSIGCOMM’94 Conference, London, England,1994,234-244.

[2]Johnson D B.Routing in ad hoc networks of mobile hosts.In: Proc IEEE Workshop on Mobile Computing Systems and Applications,1994,158-163.

[3]C. E. Perkins and E. M. Royer, Ad hoc On-Demand Distance Vector Routing. Proceedings of the 2nd IEEE Workshop on Mobile Computing Systems and Applications (WMCSA’99), New Orleans, LA, USA, February 1999:90-100.

[4]Toh C-K.Associativity based routing for ad hoc mobile networks. Wireless Personal Communication Journal. Special Issue on Mobile Networking&Computing Systems,1997,4(2):1-36.

[5]Park V,Corson M S.A highly adaptive distributed routing algorithm for mobile wireless networks.In:Proc IEEEINFOCOM’97,Kobe,Japan,1997,1405-1413.

[6]郑石,吴伟强,张钦宇,张乃通.基于能量感知的Ad hoc 路由算法研究[J].通信学报,2012,(4):9-15.

[7]王安保,胡小明.基于GPS 的启发式Ad hoc 路由算法研究[J].计算机应用研究,2010,(12):4708-4710.

[8]REN P Y, FENG J, HU P et al, J. Energy saving ad-hoc on-demand distance vector routing for mobile ad-hoc NETworks[A].IEEEICC’09[C]. Dresden, Germany 2009,1-5.

[9][美]巴萨尼,等.移动Ad hoc 网络[M].西安:西安交通大学出版社,2012.