基于能量均衡的自组网改进型混合路由协议

刘玉军，王一博，蔡猛

(陆军装甲兵学院，北京 100072)

0 引 言

移动自组网络(Mobile Ad hoc Network, MANET)在无通信基础设施支持环境下有着广阔的应用前景，如军事、野外探险、自然灾害救援通信等领域。便携型的自组网节点一般采用电池供电，一旦自身携带的电池能量耗尽，不仅节点本身无法通信，还将影响网络整体的连通性、服务质量和生存时间。

MANET协议栈的大部分协议由传统网络协议修改而来，特别是路由协议，主要依据最小代价尽力交付的原则在维系网络拓扑，这导致无线环境下协议开销较大，必然引起能耗加剧，而且多数协议忽略了无线通信功率、节点能耗对网络通信质量和网络生存时间[1,2]的影响。因此，在路由协议中加入能耗因素，对提升无线移动自组网性能具有重要的研究意义。

1 相关研究

目前，移动自组网中针对能量限制的路由协议改进主要有负载均衡和能量感知两类方案。文献[1]提出了一种能量有效负载均衡的多径路由算法，该算法考虑了节点的能量、路由跳数、网络拓扑，以及控制关键节点过载等情况，但是没有考虑传输中节点的能量消耗。文献[2]和文献[3]提出了能量优化的按需路由协议，该协议引入能量感知概念，根据剩余能量信息选择路由路径，均衡了节点的能量使用情况，但该协议没有考虑均衡节点的负载情况，增加了网络延时。文献[4]提出了一种能量感知强制协作路由协议，协议通过检测节点的剩余电量，强制剩余电量较多的节点承担数据转发任务，该协议均衡使用了节点能量。但加剧了部分节点的能量消耗。文献[5]在按需路由的基础上提出了基于剩余能量感知的多策略路由协议，该协议对节点能量设置多个阈值，根据剩余能量对应的阈值区间，均衡节点的负载，降低节点能量消耗，延长了网络的生存时间，但是当节点能量均处于较低水平时，该协议的连通率较低。文献[6]提出了基于网络负载与能量均衡的多径路由协议，融合了能量感知和负载均衡两方面技术，均衡负载的同时降低节点的能量消耗，但该协议通过节点负载和剩余能量各占一半的方式融合，存在一定局限性。文献[7] 研究了能量节约型路由协议，但协议需要对网络条件进行诸多限制，影响了研究成果的适用范围。

目前，能量均衡路由协议多数以AODV、DSV等按需路由为基础改进，这类方案虽然延长了自组网的生存时间，但是存在较高延时和大型网络适应性差等问题。

为了克服上述问题，本文拟采用传输延迟小、支持较大网络规模的优化链路状态路由(Optimized Link State Routing，OLSR)协议进行改进。但是OLSR协议在路由建立与维护中消耗了大量的计算、存储和能量等资源，缩短了网络的生存时间。为此，本文引入剩余能量和负载均衡相结合的改进方案，控制节点的能量消耗；改进拓扑控制(Topology Control，TC)消息，引入次优多跳路由的思想，有效降低路由OSLR协议开销，提高节点的能量利用效率。

2 改进型OLSR协议设计方案

OLSR协议与其他协议的显著区别是引入多点中继[8](Multi-Point Relay，MPR)，通过算法选择合适的中继节点，可以降低拓扑维护的开销，但算法造成了MPR节点业务和信令负载过重，加速MPR节点的能量消耗，降低了这些节点的生存时间。为此本文从能量均衡消耗的角度出发，在传统OLSR协议的MPR节点决策算法中引入能量代价函数，将网络路由维护任务更均匀分散在所有网络节点中，实现路由层的能量均衡消耗。

2.1 能量代价函数设计

在传统OLSR协议的基础上，基于网络节点的剩余能量建立一个函数，对网络中每一个节点的信号传输进行可量化的能量投递代价[9]度量，记为C，并将该概念引入到MPR节点的决策环节中。函数定义如下：

(1)

从表达式(1)可以看出，随着节点入网后时间的推移，节点的剩余电量不断减少，节点的能量投递代价数C将不断增大。

OLSR协议的一个关键环节是网络中的MPR节点的选择。传统协议的决策算法主要是基于网络最小连通拓扑树。在节点能量受限场景下，这种机制将导致部分关键位置的网络节点承担了网络中大部分的拓扑维护和数据业务的中继任务，从而导致能量消耗速度明显高于其他节点，过快出现“死亡”节点，影响了网络的整体连通性和通信性能。

本文提出一种基于能量投递代价C和网络节点总能量消耗之和Eall的MPR集合综合选择机制，去掉部分非功率高效和剩余电量较小的邻居节点，增大节能路由和能量均衡路由的选择概率，从而达到网络节能和能量消耗均衡的目的。令Ni表示具备发射功率控制能力的网络节点i的信令两跳扩散的目的节点集合，则从网络节点总能量消耗之和Eall角度出发，MPR集合选择的优化目标函数具体为：

(2)

从表达式(2)的优化目标函数可以看出，节点的剩余电量越小，其能量投递代价越大，则该节点被选为MPR节点的概率就越小。另外该函数也一定程度考虑了节点能量的利用率因素，这就使得剩余电量较多和节点能量利用率更高的节点更主动承担更多的网络拓扑维护和数据业务的中继传输任务，从而在保障能量利用率的基础上，尽可能均衡使用各网络节点能量，有效延长网络节点的生存时间。

2.2 控制协议改进

OLSR的控制协议主要体现在HELLO和TC消息。结合上述的MPR节点选择机制，本文对这两类消息的协议内容改进如下：

(1)节点将根据自己的剩余电量来自适应决定向邻居节点发送 HELLO 消息的周期。剩余能量投递代价小于预设的阈值C0时(这里设定为能量消耗一半后)，按正常频度f0发送HELLO消息；大于该阈值时，则逐渐降低HELLO消息发送的频度f，算法见表达式(3)为:

(3)

根据HELLO信息，节点可以获得：

·邻居节点感知(Neighbor sensing)；

·节点链路状态检测：单向链路、双向链路或者未确定；

·加入能量字段，检测节点剩余能量的投递代价；

·基于HELLO信息携带的邻居节点的能量投递代价C进行MPR 节点计算。

(2)为进一步降低路由维护的能量消耗，本文引入自适应路由机制，即维护近端节点之间的高精度路由信息(2跳之内)，而中远端节点之间仅维护次优的路由信息，设计思路如下：

设置两类TC消息并添加信令类型字段便于识别，第一类TC消息用于近端区域的精准路由，增加TTL字段以设置节点的精准路由范围，在范围内发送一类无失真TC消息，建立精准路由拓扑关系；第二类TC消息用于中远端路由拓扑关系建立，采用次优多跳路由思想，仅记录节点的一跳范围拓扑关系，并降低全网范围内的广播频度。

3 协议实现

本节从实现层面进一步描述对OLSR协议的改进内容。

3.1 MPR节点选择算法实现

令集合N1表示节点的1跳邻居节点集合，N2表示节点的2跳邻居节点集合。标准OLSR协议的MPR节点选择流程具体如图1所示。

图1 标准OLSR协议MPR节点选择

对图2所示的网络拓扑而言，如果根据标准OLSR算法，网络中的节点7、节点10和节点11处于网络拓扑的中心位置，这些节点充当其它节点的MPR节点以及数据业务中继节点的概率很大，因此将很快耗尽能量而成为死亡节点，导致网络连接出现中断。

图2 基于标准OLSR协议选择的MPR节点集合

而表达式(2)的优化函数的改进型MPR节点选择流程如图3所示：

图3 改进型MPR节点选择

基于图3的流程可以看出，采用基于能量的改进型OLSR协议后，在网络运行初期，网络节点的能量基本相同，则节点7、节点10和节点11仍将充当MPR节点，但随着这些节点的剩余能量降低，相应的剩余能量投递代价将提高。MPR节点的选择结果将随着网络的运行而不断发生变化，其它剩余电量较多的节点也将逐渐承担更多比例的网络管理和数据中继任务，如图4所示，从而满足均衡使用各网络节点能量的要求，提升网络整体的生存时间。

图4 改进型OLSR选择的MPR节点集合

3.2 OLSR路由控制消息改进

OLSR协议采用周期性的路由控制信息交换机制来实现网络拓扑的维护。这个过程在能量受限的网络中也需要进行必要的改进以节约能量。改进如下：

3.2.1 HELLO消息改进

在HELLO消息的保留字段(即Reserved字段)中加入节点计算好的剩余能量投递代价C。节点通过改进的HELLO信息交换链路信息和剩余能量投递代价，根据交换的HELLO信息建立新的邻居节点信息库，并加入邻居节点的剩余能量投递代价。更改后的HELLO消息格式如表1所示：

表1 HELLO消息格式

3.2.2 TC消息改进

为降低信令开销和能量消耗，TC消息设置两类信令类型并设置信令类型字段，第一类信令分组将在信令分组中设置TTL 字段来控制信令的扩散范围，主要进行局部扩散，建立精准路由，默认TTL的值为128(可根据实际应用调整)。其信令分组格式如表2所示：

表2 第一类TC消息格式

此外，第二类信令并不设置TTL字段，主要用于中远端节点的次优路由维护，其分组格式如表3所示：

表3 第二类TC消息格式

节点接受TC消息后，首先判断信令类型，若第一类则记录源节点到本节点的精准路由拓扑关系；若第二类则仅记录TC消息的源地址和上一跳节点地址，后转发该TC分组。

图5给出了基于上述路由机制的维护结果。

图5 近端和中远端拓扑关系图

由于节点可能从多个节点重复接收到同一消息，为避免同一消息重复处理的能量消耗，每个节点将设置一个基于时间有效性的复制集合，该集合可以避免消息的重复处理和转发。改进如下：

(1)如果第一类消息的 TTL 小于等于 0 或消息是接收节点自身发送的，该消息必须立刻丢弃；

(2)如果节点接收到没有消息的分组信令数据(如分组长度小于分组包头长度)，则这个分组数据必须立刻丢弃；

(3)如果分组信令数据在复制集合中已经存在一个记录，表明该消息已经进行处理，则这个数据必须立刻丢弃；

(4)如果信令数据为有效信令，则根据信令类型进行相应的处理。

4 仿真实验

为验证本文提出的改进型协议性能，对改进型协议和传统OLSR协议进行仿真和分析。

4.1 仿真场景描述

为减少仿真结果的偶然性，设置了3个仿真场景。场景一：16节点的4跳网络；场景二：16节点的8跳网络；场景三：32节点的4跳网络。场景的用户分布模型依次如图6-图8所示：

图6 16节点4跳

图7 16节点8跳

图8 32节点4跳

4.2 仿真结果与分析

三个仿真场景下传统OLSR协议和本协议在网络建网时间、全网转发吞吐量的性能仿真结果如下：

(1)场景一的仿真结果

图9a 传统OLSR建网时间

图9b 改进型协议建网时间

图10a 传统OLSR全网转发吞吐率

图10b 改进型协议全网转发吞吐率

(2)场景二的仿真结果

图11a 传统OLSR建网时间

图11b 改进型协议建网时间

图12a 传统OLSR全网转发吞吐率

图12b 改进型协议全网转发吞吐率

(3)场景三的性能仿真结果

图13a 传统OLSR建网时间

图13b 改进型协议建网时间

图14a 传统OLSR全网转发吞吐率

图14b 改进型协议全网转发吞吐率

图15a 传统OLSR网络中心区和边缘节点的电量消耗曲线

图15b 改进型协议网络中心区和边缘节点的电量消耗曲线

比较3个场景的仿真结果(图9a至图14b)可以看出，本文提出的混合路由协议，在建网时间和网络吞吐率上获得了与传统路由协议相当的性能。在节点电量消耗效果方面，图15a和图15b则分别给出了使用传统OLSR协议和本文改进型协议，在相同的业务负荷时，场景1中一个网络中心区节点和一个边缘节点在同时满电量(归一化为1)入网后，随着仿真时间的推移各自的剩余电量情况。可以看出传统协议中网络中心区的节点一直充当MPR节点，能量消耗速率明显快于边缘节点，很快电量耗尽导致节点死亡；协议改进后，虽然入网初期中心区节点的电量消耗速率还是明显高于边缘节点，但随着时间推移，边缘节点将逐渐取代中心节点来承担更多网络责任，从而导致双方能量消耗速率出现转变，实现了节点能量的均匀消耗，比起传统协议，相同入网电量和相同业务负荷场景下，节点的生存周期增加了一倍。

5 结 语

本文针对能量受限网络，完成了基于能量均衡Ad Hoc网络的混合路由协议设计与实现。对传统的OLSR路由协议算法进行了深入的分析与改进，实现了表驱动路由协议与能量感知和负载均衡的结合，并引入次优多跳路由的思想，改善了OLSR路由协议路由开销较大和各节点能量消耗不均衡的问题，延长了网络的生存周期。

[1] 李晓鸿等. 一种最大化Ad Hoc网络生存期的拓扑控制算法.计算机研究与发展，2013，50(3):461-471.

[2] 袁韵洁等. 一种自适应功率控制的信道预约多址接入协议.西安电子科技大学学报(自然科学版),2013,40(2)：181-186.

[3] 樊志平等.无线传感网络能量有效负载均衡的多路径路由策略. 小型微型计算机系统,2013,34(2):254-257.

[4] K.Sumathia,A.Priyadharshinib.ENERGY OPTIMIZATI- ON IN MANETS USING ONDEMAND ROUTING PROTOCOL, Procedia Computer Science,2015,47:460-470.

[5] AL-Gabri Malek,Chunlin LI, Zhiyong Yang,Naji Hasan.A.H,Xiaoqing Zhang. Improved the Energy of Ad Hoc On-Demand Distance Vector Routing Protocol. IERI Procedia,2012,2:355-361.

[6] Abeer Ghandera, Eman Shaaban.Power Aware Coopera- tion Enforcement MANET Routing Protocols. Procedia Computer Science,2015,73:162-171.

[7] 郑石等. 基于能量感知的ad hoc 路由算法研究.通信学报，2012，33(4)：9-16.

[8] 秦军等. 一种基于组合度量的OLSR 扩展链路状态路由协议.计算机技术与发展,2013,23(4):47-54.

[9] 刘半藤等.基于移动—能量代价函数的无线自组织网络路由测量研究.传感技术学报，2017,12(4)：15-19.