移动Ad Hoc网络中的节能路由协议

陆 伟，杨余旺

(1.南京理工大学 计算机科学与工程学院， 江苏 南京 210094；2.淮阴师范学院 计算机科学与技术学院， 江苏 淮安 223300)

0 引 言

移动Ad Hoc网络(mobile Ad Hoc network，MANET)是一种无任何基础架构的开放式、可扩展式自组织网络。由于MANET节点具有转发功能，其接收数据分组和转发均需要消耗能量。与源节点和目的节点不同，中间节点需要消耗更多的能量维持正常通信和网络连通性[1]。

目前，MANET中已经有针对节能路由协议的研究文献，这些协议均是将功率控制引入到现有各种路由协议设计之中[2-9]。文献[4]提出了一种旨在增强网络寿命的能量感知路由协议框架，和DSR协议相比，改进协议能够节省20%的能量。文献[6]使用图论理论形成网络拓扑结构以确保节点最小能量消耗维持网络连通性，但研究结果并未从能量和时间上进行理论分析及测试。文献[8]提出了一种能量感知多径路由协议AOMR-LM，能够平衡各条支路上的能量消耗和保存节点剩余能量，其使用了一种能量感知机制，通过节点的能量水平选择节点剩余能量并实现路径分类，和其它节能路由相比能够有效提高网络寿命、节约能耗。从上述研究可以发现，大多节能路由协议是基于最短路径算法改进，而最短路径路由中存在的缺陷会同样存在于改进算法之中，缺乏创新性，存在缺少数学解析模型的理论基础。综上所述，由于已有的节能路由协议并未分析出路由寻路效率与能量消耗之间的关系，因此普遍存在节能效率低下的问题。

为此，本文引入MANET信号属性，在其基础上建立简单稳健的数学解析模型，提出了一种能同时解决能量和路由效率的节能路由协议(energy saving routing protocol based on mathematical modeling，ESRP-MM)，最后实验结果验证了ESRP-MM的优越性。

1 问题描述

现有大多数路由协议[10]均使用最短路径寻优技术，但最短路径寻优存在的问题不可忽视，因为其仅考虑了最短传输距离和时间，并未将干扰、衰落、散射、噪声等因素考虑其中。此外，最短路径寻优技术容易造成网络分割中断，这是因为移动节点耗尽能量后可能中断路径重启路由发现过程。再者，将能耗问题和最短路径联合考虑，将会进一步重新定义最短路径的有效性，因为其路径成本和计算复杂度将会因为能耗因素的引入而大为降低。

经典AODV协议[11]是当前MANET节能路由改造中最常用的基础协议，尽管AODV具有低延时和按需建立路由等优点，但其仍存在各种不足使得其能量节省效率难以大幅降低。比如，在大规模高密度MANET网络环境下，AODV会产生不一致的路由从而增加重传次数，从而造成了不必要的能量消耗。

因此，针对上述问题，需要从数学模型建立角度设计路由规则。在能量控制阶段，应该在随机链路选择或者路由维持的基础上考虑设计路由策略，节能策略应该从路由发现过程就开始执行，故下文将设计一种节能路由协议。

2 ESRP-MM协议的设计

本节提出了适用于大规模MANET网络的节能路由协议ESRP-MM，引入了带宽效率到协议中，提高了节能效率和通信性能。为提高计算效率，ESRP-MM使用了成本因素用于选择源目的节点对之间的最佳路由。其次，在路由发现阶段通过更精确的成本计算实现最低能量路由选择。ESRP-MM协议运行在802.11MAC协议[12]之上。

2.1 能量模型

能量模型设计基于MAC层协议，目前MAC媒体接入控制协议分为点协调式接入机制和分布式协调接入机制，由于点协调式接入机制是集中式控制，故ESRP-MM使用分布式协议接入机制。因此，当移动节点想要发送数据给另一个节点时，通常要进行网络分配向量初始检查。如果发现网络分配向量大于0，节点停止发送直至其为0。为了消除MANET隐藏终端[13]的影响，ESRP-MM使用CMRTS和CMCTS两类不同类型的控制分组。源节点发送CMRTS给接收节点，当接收节点收到CMRTS后，目的节点发送CMCTS分组。如果发送节点在特定时间周期内没有收到CMCTS，则重新发送。源节点收到CMCTS后，将发送数据分组，而接收节点收到数据分组后将返回确认分组。此过程一至重复到源节点收到接收节点返回的确认分组为止。图1给出了ESRP-MM状态转移图。

图1 ESRP-MM分组发送状态转移

(1)

式中：ηo为物理层的开销。因此，结合概率理论和上述能量模型，ESRP-MM协议中，数据分组发送需要的累积能量表示为

(2)

式中：Em表示MAC层消耗能量。此外，数据分组成功接收消耗能量为

(3)

式中：在源节点i和目的节点j之间，ESRP-MM认为有(n-1)个中间节点。0,1,2…,M为节点序列号。结合式(2)、式(3)，有数据分组传输需要消耗系统的累积能量表达式为

(4)

2.2 路由成本评估

由前文可知，传输过程中大多数参数是较容易计算的，但也存在一些参数不容易得到。ESRP-MM协议考虑信号衰减由节点的随意移动性引起，衰减速率可被定义为1/DP，其中D为节点间距离，P为路径损耗指数[14]。因此，数据分组接收能量水平Er取决于发射端能量Et和DP比值，其中Et为分组传输所需的能量，故有表达式为

(5)

式中：α是实时环境中和环境因素相关的变量参数。因此，移动节点可以根据已知数据分组的接收能量水平以及期望接收能量值预估出其它数据分组传输需要的能量。此外，数据分组中的比特错误通常由噪声、干扰和冲突造成，802.11MAC使用载波侦听能够有效识别冲突和干扰。因此，在利用噪声和干扰参数的基础上，ESRP-MM能够通过调制方案和接收能量水平预估出误码率。如果分组包含s个比特，误码率为BER，则有分组错误率为1-(1-BER)s。因此，很容易给出RTS、CTS、ACK等控制分组的分组错误率，分组错误率主要受分组大小、干扰、接收能量和噪声等因素影响。不过，RTS控制分组的分组错误率仅受冲突和干扰两个因素影响，结合式(1)，将无线环境中的噪声干扰表示为eIN，冲突为eCL，故有RTS请求控制分组的分组错误率为

eR,i,j=eIN+eCL-eINeCL

(6)

2.3 能量感知路由

ESRP-MM协议旨在路由发现过程中寻找具有高节能效率的路由，通过周期性维护路由以减小动态拓扑造成的不利影响。和传统路由协议相似，ESRP-MM以寻找最短路径的方法初始化路由发现进程。以图2所示的场景为例，在源节点X和目的节点Y之间存在3种路径。考虑到路径上的所有节点，最短路径有XPQY，XRSY，XTUY，而潜在的其它路径有XPY，XQY，XRY，XSY，XTY和XUY。以S表示收发X和Y的路径集合，Ns为路径s的跳数，Es,i是路径s上消耗的能量。因此，最短路径可表示为

Sp=argmin(Ns),s∈S

(7)

类似，可定义节能最短路径为

(8)

图2 一种简单MANET场景

ESRP-MM协议中，设计了一种路由策略用于确保首先找到最短路径再筛选出具有最低能量消耗的路径。在路由发现过程中，RREQ包含能量损耗和跳数等附加信息。源节点广播RREQ分组，接收到RREQ的中间节点更新RREQ中的能量损耗和跳数信息。此外，ESRP-MM再设置两个条件用于判断中间节点是否转发RREQ：①如果之前未收到相同的RREQ分组；②如果收到的分组和之前分组具有相同的跳数，但是具有更低的能量损耗。因此，前者可确保最短路径寻优，后者能够确保能耗最低。

3 性能评估

本节使用OPNET14.5网络仿真软件对ESRP-MM协议进行了性能仿真，从分组传输时间、分组丢失率、数据流丢失数目、耗能等角度给出了协议性能评估，并和文献[8]所提协议、经典协议AODV进行性能对照。由于ESRP-MM借鉴文献[8]的思想，其仿真环境、参数配置相近，而AODV协议则通过适当修改使其能够计算能量消耗，并适用于ESRP-MM的仿真环境。在给定仿真区域面积内，节点位置随机分布，节点采用随机路点移动模型。仿真结果通过独立50次循环求统计平均获得。主要仿真参数配置见表1。

表1 仿真参数配置

图3给出了ESRP-MM协议在不同分组大小、不同节点移动速率条件下的分组传输时间仿真结果。分组传输时间指分组由源节点发送经中间节点转发目的节点接收整个过程需要的时间。由图3可知，分组传输时间会随节点移动速率和分组长度增加而上升。在节点移动速率小的条件下，分组大小变化对分组传输时间的影响呈正相关，但影响较小。在节点移动速率大时，分组长度越大分组传输时间越长。

图3 分组大小不同时的网络分组传输时间仿真结果

图4给出了分组丢失率随仿真时间的变化结果。和文献[8]相比，ESRP-MM分组丢失率更小，表明ESRP-MM具有更优的分组传输性能。

图4 分组丢失率随仿真时间变化趋势

图5给出了不同节点数目条件下请求分组能量消耗结果。仿真对网络内所有节点发送的请求分组的能量消耗进行统计并求平均给出单请求分组耗能结果。据图可知，AODV随着节点数目增加其能量消耗近线性增长，故AODV存在网络节点易耗尽能量关机的问题，这是因为网络规模的增加会使中间节点变多进而加速中间节点能量消耗所致。

图5 节点数目不同时请求信息能量消耗结果

文献[8]使用了迭代计算方法得到节点剩余能量，由于计算方法的低复杂度降低了系统的能量消耗。ESRP-MM由于使用了基于链路成本的路由因子，提高了最佳路由寻找速度，此外并未在能量计算过程中引入额外的复杂度，故大大降低了寻路能耗。

图6给出了不同节点移动速率条件下的单数据分组能量消耗结果。高速移动节点一般会引起网络拓扑结构的急剧变化、路由中断和隐藏终端等问题。相比AODV和文献[8]，ESRP-MM的单分组耗能随着节点移动速率增加并未快速增加，而是保持在一个较稳定的低能耗水平，这和其使用的能量控制策略有关。ESRP-MM的能量控制策略能够有效解决隐藏终端问题，能够在高速移动场景下缩小给邻居节点发送信息的传输范围从而有效降低发送功率，实现单分组传输低能耗的目的。

图6 不同节点移动速率条件下单数据分组能耗结果

4 结束语

能量节省问题是移动Ad Hoc网络路由协议的研究点之一，传统节能路由协议大多是在最短路径路由协议基础上增加能量控制策略实现，普遍存在能量效率低下、缺少数学模型论证的问题。本文提出了一种节能路由协议ESRP-MM，建立了包含节点属性的数学模型，将带宽效率引入到寻路策略中，描述了一种简单能量控制策略，同时实现了最短路径寻优和能量节约。仿真结果验证表明ESRP-MM协议相较传统协议具有更优的传输性能和能量节约性能。下一步，将借鉴ESRP-MM路由思想，研究适用于无线传感器网络的节能路由。