基于能量感知的最小能量动态源路由*

张继锋，周继鹏

(暨南大学 信息科学技术学院，广东 广州 510632)

移动Ad hoc网络MANET(Mobile Ad hoc Networks)是由一组具有路由功能的移动节点自组织成的无线多跳系统。由于网络规模小、无基础设施和构建快速等特点，MANET广泛应用于野外考察、作战现场、灾难救助等场合。MANET中的节点一般通过电池供电，而目前电池容量有限。另一方面，随着网络终端性能的提升、功能的不断加强，产生的能耗会越来越大，对能源的要求也会越来越高，能量问题可能成为Ad hoc网络广泛应用的瓶颈，从而使得节能策略成为当前一个研究热点。

传统路由协议都使用一组度量指标来寻找维护最佳路径，最常用的度量指标是最少跳数。然而这个指标没有考虑节点和网络的耗能和寿命问题，可能导致节点能源的浪费和过度使用等问题，最终使得节点和网络的寿命严重下降。

动态源路由(DSR)[1]协议在转发数据时，使用最少跳数的路径进行数据转发。在发射器以固定能量水平发送的Ad hoc网络中，DSR协议并没有考虑路径的剩余能量。由于DSR协议始终选择最少跳数的路径进行数据转发，因此在最少跳数路径上的节点被过度使用的可能性很大。节点的过度使用极易使节点死亡造成网络发生分割，缩短网络的使用寿命。

最小能量动态源路由MEDSR(Minimum Energy Dynamic Source Routing)[2]协议除了发射器的能量水平可调整外，其余的都与DSR协议相同，所以MEDSR协议也有DSR协议所面临的问题。

本文针对DSR协议和MEDSR协议在节能策略方面存在的缺陷，以减少节点的过度使用和延长网络生存时间为设计目标，以MEDSR路由协议为基础，提出了一种基于能量感知的最小能量动态源路由协议。引入能量感知策略就是使路径的剩余能量成为主要的度量指标来选取最佳路径。通过在路由发现过程中动态地进行路径剩余能量的计算，选择剩余能量最大的路径转发数据，与传统的按需路由协议相比，大大减少了节点的过度使用，延长了网络的生存时间。

1 相关算法

最小最大链路功率路由协议(MLRP)算法旨在寻找一条低功率的路由，其中每个节点都能根据自己要进行通信的邻近节点自适应地调整发射功率。在此算法中，路由寻找的发起者决定转发RREQ请求的中间节点的统一发射功率，当路由建立尝试失败时，能相应地减小此功率值。因此，此路由进程主要考虑最小化每个参与节点消耗的能量，以及减小所选路径消耗的能量。最小电池开销路由(MBCR)[3]算法中定义了节点电池开销函数，从而计算出包含n个节点的路径m的总电池开销，而最大剩余电池能量的路径即是拥有最小电池开销的那条路径。有条件最大最小电池容量路由(CMMBCR)算法[4]也是对MBCR的改进，设计CMMBCR的出发点是能够使整个网络的生命周期最大，同时又公平地使用每个节点。其基本思想是首先找出从源节点到目的节点的所有电量充足的路径(即路径上的所有节点都具有大于某个阈值(0～100)的剩余电量)，然后从中选择出总传输能量最小的那条路径作为路由选择的最终结果。

2 最小能量动态源路由(MEDSR)

2.1 最小能量路由协议的背景

传统的路由协议都是采用固定的发射功率进行数据包的转发，由于节点发射功率的大小直接影响到邻近节点的通信，发射功率太小虽然可以相对减少能量消耗，但是有可能使得两个节点的通信无法进行；发射功率太大虽然可以保证两个节点之间的通信，但是有可能会影响其他节点的通信。

发射功率水平过高或者过低都会严重影响网络的连通性，在保证节点通信成功的情况下，采用最小发射功率水平不仅可以保证网络的连通性，而且还减少节点的能量消耗。

2.2 最小能量动态源路由简介(MEDSR)

MEDSR协议是在DSR协议的基础上，采用可调整的发射功率，并且在DSR协议的路由发现过程当中改进而得来的。最小能量体现在保持通信质量的情况下，使得节点的发射功率水平达到最低。

MEDSR协议的路由发现过程当中包含两个机制：

(1)多功率水平路由发现机制

源节点首先使用低功率水平发送RREQ，RREQ中包含功率水平信息。如果使用低功率水平发送失败，则选择高功率水平发送。下一跳节点也选择可调整的功率水平将RREQ转发，并且将自己的功率水平信息加到RREQ中。此过程一直操作下去，直到RREQ到达目标节点。此时，目标节点发送RREP，RREP中同样包含能量水平信息。功率水平的调整过程就是通过转发RREP进行的。此过程一直进行，直到RREP到达源节点。

(2)逐段功率水平调整机制

图1(a)中节点C接收到目标节点D发送过来的RREP，测量节点C接收到的能量水平Precv。因为RREP中包含目的节点的发送功率水平信息Pt。节点C计算到达目标节点 D所需最少的传送能量：Pmin=Pt-Precv，然后节点C将所需的最少传送能量存储在自己的能量表中。节点C再将RREP转发给节点B，重复同样的工作，直到RREP到达源节点S。

图1 路由发现

3 协议描述

3.1 能量感知

3.1.1 路由请求包(RREQ)的结构

为了实现MEDSR协议中功率调整，需要在RREQ中增添功率值列表字段Power list，如表1所示。

表1 路由请求包(RREQ)的结构

3.1.2 路由回复包(RREP)的结构

路径的剩余能量是指该路径中的节点剩余能量的最小值。

能量感知的目的就是在返回的众多路径中选择剩余能量最大的路径。

按需路由协议并不像表驱动路由协议那样预先知道网络全局的拓扑信息，按需路由协议是根据发送数据分组的需要按需进行路由发现过程，所以MEDSR协议中路径的剩余能量只能通过路由发现过程动态地获得。因此，需要在RREP中增添路径剩余能量字段Path energy，如表 2所示。

表2 路由回复包(RREP)的结构

3.1.3 节点本地cache表的结构

为了满足能量感知的目标，需要在MEDSR协议的基础上，对网络节点的cache表中再增加剩余能量值字段Residual energy和临时剩余能量字段Temporary energy，以及发射功率值字段Power level，如表 3所示。

表3 节点剩余能量值和功率水平

Residual energy字段记录节点当前的剩余能量值，Temporary energy字段记录Residual energy字段与Power level字段的差值，用于和RREP中的Path energy字段比较，Power level字段记录经调整的发射功率值。

采用Temporary energy字段是因为MEDSR协议的发射功率是可调整的，即不同路径上节点的发射功率大小不同，如果此时简单地使用Residual energy值作为比较对象，有可能使Residual energy最大的节点由于Power level过大而造成节点能量的过快消耗。此时采用Temporary energy可预先考虑节点能量的消耗速率，这样对路径剩余能量的比较更公平准确。

3.1.4 能量感知过程说明

变量说明：R代表 cache中的 Residual energy字段记录的值；P代表 cache中的 Power level字段记录的值；T代表cache中的Temporary energy字段记录的值(用于和RREP中的 E比较)；E代表RREP的Path energy字段记录的值。

(1)节点剩余能量的计算过程

每个节点都保存着自己剩余能量的数值R，同时，保存着临时的发射功率水平数值P(P是MEDSR协议经过能量水平调整而暂时存储在本地cache表当中的)。每转发一个数据包，节点就进行操作：R：=R-P。

(2)路径剩余能量的计算过程

在MEDSR协议路由应答过程中，目的节点的下一跳邻居节点进行能量水平调整以及相应的临时剩余能量T计算。首先进行计算 T：=R-P，然后将自己的T赋值到RREP中的Path energy字段。当RREP到达目的节点的次下一跳邻居节点时，该节点也进行能量水平调整和临时剩余能量T计算，然后将自己的T值和RREP中的 E 值进行比较：如果 T＜E，则 E：=T；如果 T＞=E，则 E不做任何改变。

将RREP继续往源节点转发，RREP中只储存唯一的一个E值。根据上面分析可知，E储存的是该路径的剩余能量。

当源节点接收到经过多个RREP后，比较它们当中的E值，源节点首先选择E最大的的路径进行数据包的转发，即选择剩余能量最大的路径进行数据转发。

3.1.5 能量感知形式化说明

图2(a)和图 2(b)分别用无向图和有向图表示同一个网络[5]。图2(a)中节点旁边的数字代表节点的剩余能量R，节点之间的数字代表经过调整发射能量水平数值P。图2(b)中节点旁边的数字代表节点的剩余能量R，节点之间的数字代表临时剩余能量T。

如图 2(b)，节点 d和节点 b进行通信，d、b之间有两条路径，分别是d-a-b和d-c-b，路径d-a-b的剩余能量 E是 60；路径 d-c-b的剩余能量 E是 55，所以节点d和节点b进行通信时，会优先选择剩余能量值较大的d-a-b路径。再如，节点 a和节点 c进行通信，a、c之间有两条路径，分别是a-b-c和 a-d-c，路径 a-b-c的剩余能量 E是 35；路径 a-d-c的剩余能量 E是 55，所以节点a和节点c进行通信时，会优先选择剩余能量值较大的a-d-c路径。

图2 能量感知

3.2 路由算法

3.2.1 路由请求

(1)源节点S在本地路由缓存中检查是否存在到达目的节点D的路由。如果存在，则转(2)，否则开始路由请求过程：节点选择可调整的功率水平转发RREQ。首先，源节点S使用低功率水平发送路由请求数据包RREQ，如果发送成功，则将功率水平信息存放到RREQ发射功率值列表字段Power list中；否则，选择高功率水平发送路由请求数据包RREQ，如果发射成功，进行如上述功率水平信息同样的操作，并转(3)。否则，路由请求失败。

(2)使用该路由发送数据分组。

(3)下一跳邻居节点接收到RREQ后，首先检查路由请求表中是否有对应的表项，如果有，直接丢弃该RREQ；否则，检查路由请求分组的路由记录是否已含有该节点，如果有，丢弃该分组。然后，如果路由请求分组的目的节点为节点本身，即将自己的地址信息加到RREQ中，并将功率水平信息加到RREQ中发射功率值列表字段Power list中，该节点同时反向转发RREP，RREP中保存RREQ中功率水平信息；如果不是节点本身，也将自己的地址信息加到RREQ中，该节点同样选择可调整的功率水平转发RREQ，并且将自己的功率水平信息加到RREQ功率值列表字段Power list中，并转发RREQ。

(4)次下一跳邻居节点接收到RREQ后，重复操作(3)。

(5)所有中间节点按照步骤(3)操作，直到所有RREQ到达目的节点D。

3.2.2 路由应答

(1)目的节点D将自己的地址信息和功率水平信息加到 RREP中，并反向转发 RREP，并转（2），同时进行路径剩余能量的计算。

(2)下一跳邻居节点接收到RREP后，首先根据MEDSR协议中的功率水平调整机制进行功率的调整，并将计算得到的Pmin存放到本地cache中的 Power level字段。然后进行临时剩余能量的计算T：=R-P，将自己的T赋值到RREP中的Path energy字段。最后继续转发RREP。

(3)次下一跳邻居节点接收到RREP后，首先根据MEDSR协议中的功率水平调整机制进行功率的调整，并将计算得到的Pmin存放到本地cache中的Power level字段。然后进行临时剩余能量的计算T：=R-P，将自己的T值和RREP中的E值进行比较：

如果 T＜E，则 E：=T；如果 T＞=E，则 E 不做任何改变。最后继续转发RREP。

(4)所有中间节点按照步骤(3)操作后，向下一邻居节点继续转发RREP，直到RREP到达源节点S。

(5)源节点 S选取 Path energy值最大的 RREP提供的路由信息进行数据分组的转发。

3.3 路由过程

3.3.1 路由请求过程

(1)从如图3可以看到源节点S在路由缓存中并没有发现到达目的节点D的缓存路由。源节点S开始路由请求过程：节点S使用可调整的功率水平发送路由请求数据包RREQ，将功率水平信息存放到RREQ功率值列表字段 Power list中，并转发 RREQ。图 3中(S，B)的功率水平值为 20，(S，E)的功率水平值为 15。

(2)下一跳邻居节点B和E接收到RREQ后，首先，节点B和E检查路由请求表并没有发现对应的表项；同时检查路由请求分组的路由记录也没有发现含有该节点，则不丢弃RREQ。然后，节点B和E检查路由请求分组的目的节点不是节点B和E本身，同时将自己的地址信息加到RREQ中，该节点同样选择可调整的功率水平转发RREQ，将自己的功率水平信息加到RREQ功率值列表字段中，并转发RREQ。图3中(E，F)的功率水平值为 15，(B，C)的功率水平值为 20。

(3)次下一跳邻居节点 F和 C接收到 RREQ后，首先，节点F和C检查路由请求表并没有发现对应的表项；同时检查路由请求分组的路由记录也没有发现含有该节点，则不丢弃RREQ。然后，节点F和C检查路由请求分组的目的节点不是节点F和C本身，同时将自己的地址信息加到RREQ中，该节点同样选择可调整的功率水平转发RREQ，将自己的功率水平信息加到RREQ功率值列表字段中，并转发RREQ。图3中(F，G)的功率水平值为 15。

但是，次下一跳邻居节点H接收到节点B和E转发过来的RREQ，如图3中节点H先接收到节点B转发过来的RREQ，并且不丢弃，节点H检查路由请求分组的目的节点不是节点H本身，同时将自己的地址信息加到RREQ中，该节点同样选择可调整的功率水平转发RREQ，将自己的功率水平信息加到RREQ功率值列表字段中，并转发该RREQ。此后，节点H接收节点E转发过来的RREQ，发现路由请求表中有对应的表项，丢弃掉该RREQ。

(4)同理，中间节点C接收到节点B和H转发过来的RREQ，图3中节点C先接收到节点B转发过来的RREQ，并且不丢弃，节点C检查路由请求分组的目的节点不是节点C本身，同时将自己的地址信息加到RREQ中，该节点同样选择可调整的功率水平转发RREQ，将自己的功率水平信息加到RREQ功率值列表字段中，并转发该RREQ。此后，节点C接收节点H转发过来的RREQ，发现路由请求表中有对应的表项，丢弃掉该RREQ。图3中(C，D)的功率水平值为 15。

(5)最后，直到所有RREQ到达目的节点D。如图 3中(S，E，F，G)和(S，B，C)到达目的节点 D。

图3 路由请求示意图

3.3.2 路由应答过程

(1)目的节点D将自己的功率水平信息加到RREP中，并反向转发RREP，如图4所示。

(2)下一跳邻居节点 C和 G接收到 RREP后，首先根据MEDSR协议中的功率水平调整机制进行功率的调整，并将计算Pmin存放到cache中的Power level字段。图4中C和G的Pmin都是15。然后进行临时剩余能量的计算 T：=R-P，C的剩余能量 R是 85，因此，C的 T值为70。同理，G的 T值为75，然后将自己的 T赋值到RREP 中的 Path energy 字段。 (S，B，C，D)中，M：=70；(S，E，F，G，D)中，M：=75。 最后继续转发 RREP。

图4 路由应答示意图

(3)次下一跳节点 B和 F接收到 RREP后，首先根据MEDSR协议中的功率水平调整机制进行功率的调整，并将计算Pmin存放到cache中的Power level字段。如图4，B和F的Pmin都是15。然后进行临时剩余能量的计算 T：=R-P，B的剩余能量 R是 70,因此 B的 T值为55。同理，F的 T值为 65，然后将自己的 T值和 RREP中的M值进行比较：

(S，B，C，D)中，55＜70 则 E：=55；

(S，E，F，G，D)中，65＜75 则 E：=65。

(4)所有中间节点进行临时剩余能量计算以及路径剩余能量计算操作后，向下一节点继续转发RREP，直到RREP到达源节点S。

(5)源节点S选取 Path energy最大的 RREP提供的路由信息进行数据分组的转发。

(S，B，C，D)中，E=55；

(S，E，F，G，D)中，E=65。

所以源节点 S 选取(S，E，F，G，D)进行数据分组的转发，并不是选择跳数较少的(S，B，C，D)进行数据分组的转发。

本文针对MEDSR协议中存在的问题对路由发现过程进行改进，加入能量感知策略，能量感知可使数据流平均地分布在网络的各个节点中，减少网络节点的过度使用，使网络分割的可能性减小，延长网络的使用寿命。减少了路径上中间节点的能量消耗，从而降低了由于能量消耗殆尽导致的网络分割或拓扑变化发生的概率。

下一步工作是深入模拟和分析该协议的性能，并与DSR协议和MEDSR协议进行比较。

[1]于宏毅.无线移动自组织网[M].北京：人民邮电出版社，2005.

[2]TARIQUE M，TEPE K E.Minimum energy hierarchical dynamic source routing for mobile ad hoc networks[J].Ad Hoc Networks 2009，7(6)：1125-1135.

[3]SINGH S， WOO M， RAGHAVENDRA C S.Power-aware routing in mobile ad hoc networks[C].Proceedings of the 4th Annual ACM/IEEE Intemational Conferere on Mobile Computing and Netwodeing， 1998：181-190.

[4]TOH C K，COBB H，SCOTT D A.Performance evaluation of battery-lifeaware routing schemes for wireless ad hoc networks[C].IEEE International Conference on Communications(ICC)， 2001：2824-2829.

[5]MOHANOOR A B， RADHAKRISHNAN S， SARANGAN V.Online energy aware routing in wireless networks[J].Ad Hoc Networks， 2009，7(5)：918-931.