基于移动—能量代价函数的无线自组织网络路由策略研究*

刘半藤，周 莹，陈友荣，王章权

(1.浙江树人大学信息科技学院，杭州310015;2.浙江大学控制与工程学院，杭州310058)

基于移动—能量代价函数的无线自组织网络路由策略研究*

刘半藤1，2*，周 莹1，陈友荣1，王章权1

(1.浙江树人大学信息科技学院，杭州310015;2.浙江大学控制与工程学院，杭州310058)

能量均衡技术一直是无线自组织网络的热点研究领域。在深入研究网络信息传输特性的基础上，提出了一种基于移动—能量代价函数的无线自组织网络路由策略，并用于网络信息传输。首先，本文考虑节点连通性、能量均衡性，提出了一种节点移动策略;然后，以传输路径节点集合中的瓶颈节点剩余能量、传输链路数量作为准则，建立以网络节点为对象的能量代价函数。基于移动—能量代价函数的路由策略从链路层的决策转移到节点层的决策。最后，采用MATLAB数值仿真该路由策略的性能，结果显示:本文提出的移动—能量代价函数的路由策略既保持了原有路由优化的精度，延迟网络瓶颈节点能量下降速度，提高网络生存时间。

能量代价;生存时间;瓶颈节点;动态规划;路由策略

无线自组织网络是一种由几十乃至上百个具有感知、计算和通信能力的可移动节点组成，采用无线通信方式动态组成的对等网络［1］。近些年，随着传感器技术、嵌入式计算技术、通讯技术和计算机网络技术日趋成熟，使得无线自组织网络的各种应用逐渐成为可能，成为21世纪信息产业的重要支柱。在无线自组织网络的各项技术中，路由策略和能量均衡技术一直是该研究领域的关键问题，制约着无线自组织网络的进一步发展，引发了国内外专家学者的广泛关注。在无线自组织网络的实际应用中，网络节点采用电池供电，且通常要求网络能持续工作几个月乃至几年时间。将网络中第1个节点由于能量耗尽退出网络的时间定义为网络生存时间，网络生存时间是评估无线自组织网性能的最重要指标之一［2－3］。

因此，研究网络能量均衡技术并将其应用于网络路由协议提高无线自组织网络的生存时间显得尤为关键与重要。近年来，国内外专家学者针对能量路由开展了广泛的研究。如文献［4］中，作者提出了最小传送能量路由算法。该算法选择具有最小传输能量消耗的路径将数据包从源节点发送到目的节点，这种算法具有较好的能量有效性。但是由于能量有效的路径上承担过大的负载，容易造成能量有效的路由路径提前死亡，从而其网络生存时间并不高。文献［5］中，作者提出了一种的能量均衡路由协议。在该协议中，通过在剩余能量大于某一阈值的节点集合中选择具有最小传输能量消耗的节点作为信息传输的下一跳节点。这样可以平衡整个网络的能量传输消耗，避免最短路由上的节点过早消耗尽能量，以实现一定程度上的能量消耗均衡性。文献［6］中，作者提出了一种图论算法，该算法试图通过计算每一条路由的剩余能量水平，然后排除任何剩余能量水平高于最低能量路径若干倍的路由。由于算法的性能取决于依靠经验参数，因此算法并不能总是给出最优的解决方案。文献［7］中，针对网络中某些关键节点过度消耗能量，致使网络节点能耗分布不均，影响网络的性能的缺陷，提出了一种基于博弈论的均衡路由协议，设计基于可靠度和节点的剩余能量的选择路径，解决节点能耗不均的问题，同时鼓励节点参与协作。

在以上的文献中，均没有提到网络节点的移动性会对网络能耗所产生的影响。无线自组织网络中拓扑结构动态变化，节点无序移动性可能造成部分关键节点过早退出网络，也可能使得网络能量消耗更加均衡。为此，本文在分析网络节点移动特性的基础上，提出了一种基于移动—能量代价函数的路由策略。每次信息业务传输时，以传输路径节点集合中的瓶颈节点剩余能量、信息链路数量作为代价函数，将路由协议中链路层的决策转移到节点层的决策。

1 网络节点移动策略研究

无线自组织网节点可以自由地在网络区域内移动，节点的无序移动性使得网络计算变得更为复杂。因此，本文首先介绍一种节点移动策略，该策略可以提高网络节点连通性与能量均衡性，同时也可以降低网络搜索计算量。

假设有N节点随机地分布于无线自组织网络区域中，当源节点s向目的节点d发送信息时，考虑信息中的1个比特B。传输比特B时，每个节点的坐标可以表示为［xi(B)，yi(B)］， i=1，2，…，N。无线自组织网络中的每个节点都有1个稳定的通信半径R［8］。因此，传输比特B时，无线自组织网络的拓扑结构可以用联通矩阵C=［cij(B)］N×N和距离矩阵D=［dij(B)］N×N进行表述。2个矩阵的元素含义如下:

传输比特 B时，节点 i的剩余能量可以用 Ei(B)表示。假设在信息发送间隙，每个节点最大移动距离为L，L可以由网络内信息发送频率确定。结合网络连通性与节点剩余能量，本文提出了一种使用于无线自组织网络的节点移动策略:①如果网络中存在孤立节点i(即0)，应该设计一种方法使该节点尽快进入网络连通区域。首先，寻找网络节点中与此孤立节点最近的节点

如果dij＜L+R，则可以要求节点i向节点j移动min{L，dij－R}，节点j的移动策略不发生变化。如果dij≥2L+R，则可以要求节点i向节点j移动L，同时考虑节点j是否需要向节点i移动;如果节点j移动后LT上升，则节点j向节点i移动L，否则节点j的移动策略不发生变化。如果L+R＜dij＜2L+R，则可以要求节点i向节点j移动L，同时考虑节点j是否需要向节点i移动;如果节点j移动后LT上升，则节点j向节点i移动dij－R－L，否则节点j的移动策略不发生变化。

注意:即便节点k也是孤立点也没有关系，节点i和节点k的相互移动会使得两者不再是孤立点，提高网络连通性。j。如果dij=mini≠kdik，说明节点j和节点i距离最近。

建立关于网络连通性的指标LT，用于评价节点i与节点j的相对移动是否会影响原有网络拓扑结构的连通性。

②对于网络中的非孤立节点，每个剩余能量高的节点都向节点剩余能量低的方向移动。对于其中的一个非孤立节点i而言，节点i可以感知到与其相邻节点j的剩余容量，即Ej(B)。寻找到与节点i相邻、剩余能量最低的节点考虑节点i是否需要向节点k移动。如果节点dik≤L，则可以要求节点i向节点k移动dik，同时节点k向节点i移动dik，形成节点i与节点k的位置互换，并不改变网络连通性。如果节点dik＞L，考虑节点i与节点k的相互移动是否会影响网络连通性的指标LT。如果2个节点间相互移动并不影响LT，则可以要求节点i向节点k移动L，同时节点k向节点i移动L;否则，节点i和节点k并不发生移动。

本文所提出的移动策略如图1所示。

图1 节点移动策略

2 基于网络能量代价函数的构造

当源节点s向目的节点d发送信息时，考虑信息中的一个比特B，由中间节点组成的集合中{vi(B)}，剩余能量最小的节点k也就是限制链路传输时间的关键瓶颈节点。节点k的确定过程如下:

动态源路由协议DSR是专家学者们提出的一种适用于无线自组织网络信息传输的路由协议［9］。DSR路由协议的核心思想是以较少的链路数为代价将信息从源节点传输到目的节点。该思想容易造成网络中的部分节点由于业务过于繁忙而提早退出网络，实际的网络生存时间并不高。考虑瓶颈节点剩余能量Ek(B)的影响，本节提出了一种基于能量代价函数的构造方式。当源节点s向目的节点d发送信息时，每一个中间节点都将选择能量代价函数最大的相邻节点进行信息传输。节点i能量代价函数fi(B)可以表达如下:

式中:fj(B)表示与节点i相邻的可用于比特B传输的下游节点j的能量代价函数。

为了防止出现多条剩余能量相同的节点，本文以传输路径节点集合中的瓶颈节点剩余生存时间作为第一目标、传输链路数量作为第二目标。第二目标的函数如下:

式中:hi(B)表示比特B从源节点发送到节点i所经历的链路数量，节点j是节点i的上游节点。

以上述代价函数进行路径搜索时，以能量代价fi(B)作为主要判别依据，链路数量代价hi(B)作为第二指标进行判别。该算法从源节点出发，每个中间节点都寻找下一跳的最优节点，从而将链路层的决策转化为节点层的决策。

该算法采用局部最优的思想降低网络计算量，但是并未考虑传输节点的能量消耗速率。通过式(5)、式(6)进行修正，每个中间节点都需要判断链路的能量消耗速率，并以此作为代价函数进行路径搜索［10］。因此，基于能量代价函数f*i(B)可以修正如下:

式中:E0表示无线自组织网络中节点单次发送或者接收数据所消耗的能量，Fi表示节点间两两通信一次所消耗的能量。

3 仿真分析

为了深入分析本文提出的基于移动—能量代价函数的路由策略对于无线自组织网络生存时间、网络容量产生的影响，本节采用MATLAB软件对算法进行数值仿真。

在一个300 m×300 m的矩形无线自组织网络区域内，随机散布着80个网络节点，每个节点的通信半径为50 m。对比网络节点是否移动两种策略对于网络连通性的影响。当网络节点按照本文所提出的移动策略移动时，网络连通性随时间而呈现上升状态，而当网络节点处于静止时网络的连通性不发生任何变化，即为初始时刻的连通性61%。

假设无线自组织网络中每个节点的初始剩余能量均与“1”，每个节点在每次处理信息时消耗0.001，不考虑网络节点移动与待机所产生的影响。采用DSR路由协议，针对节点是否发生移动2种情况，无线自组织网络瓶颈节点的能量变化如图3所示。通过图3可以发现:固定式网络中可能由于部分核心节点能量消耗过快，而使得网络生存时间过低。

图2 本文移动策略下，网络连通性变化曲线

图3 2种策略下，网络瓶颈节点能量变化曲线

对比分析基于移动—能量代价函数的路由策略与DSR路由策略，分析网络瓶颈节点随仿真时间的变化趋势如图4所示。

图4 2种路由协议瓶颈节点剩余能量的变化趋势

通过图4可以发现:本文提出的基于移动—能量代价函数的路由策略可以有效地降低为网络瓶颈节点能量下降速率，提高网络生存时间。

4 结束语

在深入研究网络节点移动特性的基础上，本文提出了一种移动—能量代价函数的构造方法，并用于指导网络信息传输。首先，本文基于节点连通性、能量均衡性，提出了一种节点移动策略;然后，以传输路径节点集合中的瓶颈节点剩余能量、传输链路数量作为准则，建立以网络节点为对象的能量代价函数。数值仿真结果显示:本文提出的移动—能量代价函数的路由策略既保持了原有路由优化的精度，也能提高网络生存时间。

［1］ 刘杰，王玲，王杉，等.基于能量有效的逆向AODV路由协议研究［J］.计算机应用研究，2015，32(6):1849－1851.

［2］ Vrinda Gupta，Rajoo Pandey.An Improved Energy Aware Distributed Unequal Clustering Protocol for Heterogeneous Wireless Sensor Networks［J］.Engineering Science and Technology，an International Journal，Volume 19，Issue 2，June 2016:1050－1058.

［3］ Zhang Deyu，Chen Zhigang，Zhou Haibo，et al.Energy-Balanced Cooperative Transmission Based on Relay Selection and Power Control in Energy Harvesting Wireless Sensor Network［J］.Computer Networks，2016，104(20):189－197.

［4］ 黄浩军，尹浩，陈和平，等.无线Ad Hoc网络能量感知地理路由协议研究进展［J］.软件学报，2014，(5):1061－1084.

［5］ 彭铎，黎锁平，杨喜娟，等.一种能量高效的无线传感器网络非均匀分簇路由协议［J］.传感技术学报，2014，27(12):1687－1691.

［6］ 蒋文贤.压缩感知的能量异构WSN分簇路由协议［J］.传感技术学报，2013，26(6):894－900.

［7］ Fatih Deniz，Hakki Bagci，Ibrahim Korpeoglu，et al.An Adaptive，Energy-Aware and Distributed Fault-Tolerant Topology-Control Algorithm for Heterogeneous Wireless Sensor Networks［J］.Ad Hoc Networks，2016，44:104－117.

［8］ Hao Xiaochen，Liu Weijing，Yao Ning，et al.Distributed Topology Construction Algorithm to Improve Link Quality and Energy Efficiency for Wireless Sensor Networks［J］.Journal of Network and Computer Applications，Available online，22 April 2016.

［9］ Huang Gaofei，Tu Wanqing.Optimal Resource Allocation in Wireless-Powered OFDM Relay Networks［J］.Computer Networks，2016，104: 94－107.

［10］Zhao Feng，Wei Lina，Chen Hongbin.Optimal Time Allocation for Multi-Antenna Wireless Powered Heterogeneous Sensor Network Communications under Imperfect CSI［J］.Signal Processing，2016，126:159－164.

刘半藤(1984－)，男，汉族，杭州余姚人，工科硕士，讲师，主要研究方向为无线传感网络，信息融合技术，hupo3@ sina.com。

Research on the Routing Algorithm in MANETs Based on the Energy Cost Function*

LIU Benteng1，2*，ZHOU Ying1，CHEN Yourong1，WANG Zhangquan1
(1.College of Information Science and Technology，Zhejiang Shuren University，Hangzhou 310015，China; 2.College of Control Science and Engineering，Zhejiang University，Hangzhou 310058，China)

The energy balance technology is a hot research field of the wireless selforganizing network.After the further study of the network information transmission characteristics，a kind of wireless selforganized network routing strategy used for network information transmission is proposed based on mobile-energy cost function.At first，considering the node connectivity and energy balance，a node mobile strategy is carried out;then a energy cost function is designed With residual energy of transmission path bottleneck nodes and transmission link number as criterion，and the routing strategy is determined in node layer instead of link layer;at last，the numerical simulation is performed on MATLAB，the result shows the routing strategy proposed keep the original optimal routing precision，delay the network bottleneck node energy falling speed and improve the network survival time.

energy cost;survival life;bottleneck node;dynamic programming;routing strategy

TP393

A

1004－1699(2017)02－0302－04

C:7230

10.3969/j.issn.1004－1699.2017.02.023

项目来源:浙江省自然科学基金项目(LY15F030004);国家自然科学基金项目(61501403);浙江省公益性技术应用研究计划项目(2016C33038);浙江树人大学校级科研项目(2104A11001)

2016－06－11 修改日期:2016－10－27