毛善丽，李晓卉*，蔡 彬，丁月民

(1.武汉科技大学信息科学与工程学院，武汉430081;2.天津理工大学计算机与通信工程学院，天津300384)

基于EHWSN的能量均衡动态最大流路由算法*

毛善丽1，李晓卉1*，蔡 彬1，丁月民2

(1.武汉科技大学信息科学与工程学院，武汉430081;2.天津理工大学计算机与通信工程学院，天津300384)

针对最大流算法应用于能量收集无线传感器网络求解网络负载流量时，存在能量不均衡，网络容量受初始容量限制的问题，提出了一种能量均衡的动态最大流路由算法——EB-DMF。该算法在增广路径的选择中引入能量均衡机制，并根据节点收集的能量动态更新容量值，使网络能耗均衡，达到延长网络生命期，增大网络负载流量的目的。仿真结果表明与最大流算法相比，该算法能在增大网络负载流量的同时延长网络的生命期。

能量收集无线传感器网络;负载流量;动态最大流路由算法;能量均衡

在传统的无线传感器网络 WSN(Wireless Sensor Networks)中，电池供电是传感器节点的主要供能方式。然而，对WSN的生命期要求较高但电池更换困难的应用，节点电池储能的耗尽意味着整个无线传感器网络的瘫痪，因此，能量受限一直是WSN应用的瓶颈［1］。这就使得传统WSN路由的设计都是以减少能耗、均衡负载来延长网络生命周期为首要目标［2－5］。近年来硬件技术的发展使得节点可以利用能量收集装置从外界环境中获取能量［6］，例如太阳能［7］、振动［8－9］、温度差等。能量收集技术的出现在一定程度上缓解了无线传感器网络节点能量受限的问题，使得自供能、持久且免维护的能量收集无线传感器网络EHWSN(Energy Harvesting Wireless Sensor Network)成为可能。由于能量采集的特性，EHWSN路由设计主要围绕均衡网络能耗，最大化网络负载流量而展开［10］，网络负载流量指的是网络生命周期内所能承载的数据包个数。

目前不少学者为提高EHWSN的吞吐量将解决最大流问题的 Ford-Fulkerson(FF)算法引入到EHWSN中［11－12］，将节点的能量与容量关联，通过FF算法寻找增广路径，计算网络的最大流量。文献［11］论证了FF算法可以用于无线传感器网络来寻找最大流，并给出了网络能量可维持需要满足的条件。文献［12］在文献［11］的基础上设计了一种优化路由算法，来最大化自供能网络的负载流量。然而，将FF算法应用于能量收集无线传感器网络存在以下两个问题:①节点的能量是不断更新的，节点收集到的能量可以用于数据包的传输，不更新容量的静态最大流路由算法受初始容量限制，网络无法达到最大流量。②基于FF最大流路由算法的增广路径选择具有随意性，使得网络中部分节点的能量消耗过快，网络能耗不均衡，节点会过早死亡，网络无法达到最大流量。

为解决上述问题，本文提出了一种能量均衡动态最大流路由算法 EB-DMF(Energy Balanced and Dynamic Maximum Flow routing algorithm)。该算法在FF最大流算法的基础上，①根据节点收集到的能量动态更新FF算法的容量值，并利用新的容量值计算网络的增广路径及流量;②根据节点的剩余能量来选择增广路径，达到能量均衡的目的。仿真结果表明:与FF算法相比，该算法能在增大网络负载流量的同时均衡网络能量消耗延长网络生命周期。

1 能量收集无线传感器网络

1.1 能量收集无线传感器网络的结构

能量收集无线传感器网络的结构如图1所示。能量收集无线传感器节点由能量收集装置，无线通信模块，传感器和控制器组成。图1以收集太阳能为例，节点将收集的太阳能转换成电能，存储在电池中，用于节点数据包的处理。

图1 EHWSN的结构

1.2 网络模型

能量收集无线传感器网络可以用有向图G= (V，E)表示。其中，v∈V的顶点代表网络的节点。(vi，vj)∈E可以表示节点间的无线链路，数据包传递的方向就是流量流动的方向。对于每条边(vi，vj)，赋予容量值C(vi，vj)≥0，来表示允许通过该边的容量。在实际的数据包传输过程中，根据FF算法计算增广路径，增广路径上的每条边都会有一个流量f(vi，vj)。所有增广路径上的流量之和即为网络的最大负载流量。

设置网络中所有边的流量初始值f(vi，vj)=0，根据节点的剩余能量计算的容量值为C(vi，vj)，由最大流算法可以计算出从源节点到目的节点的每条增广路径pk∈P上的流量fpk及增广路径集合P。

每条增广路径pk均可以用节点集合表示:

增广路径pk上的流量:

即增广路径pk上的流量等于该条路径上边容量的最小值。

网络负载流量f可表示如下:

由上述公式可知，增大网络负载流量需要增大增广路径上边容量C(vi，vj)的值。

2 基于EHWSN的EB-DMF路由算法

2.1 动态更新EB-DMF的容量值

节点处理数据包的能耗包括数据的采样、处理能耗和数据包的传输能耗。其中，数据的采集、处理能耗可以近似为常量，且相对于传输能耗可以忽略不计［13］。因此本文处理数据包的能耗指的是数据包的传输能耗，即发送和接收数据包的能耗。

设节点i在t时刻的剩余能量为Ei(t)，数据包发送的时间间隔为τs，数据包传输的路径可以用节点的集合{vs，…，vm，…，vt}表示。发送一个数据包的能耗为Esend，接收一个数据包的能耗为Erec，节点i每秒收集到的能量为Ehav，源节点的发包速率为Rpkg，即源节点每秒发送的数据包数目为Rpkg。节点i在t+τ时刻的剩余能量Ei(t+τ)可以根据下述公式计算:

t+τ时刻的边容量计算如下:

式中:C(vi，vj)表示边(vi，vj)上的容量，Ni表示根据广度优先搜索计算的节点i的下层邻居节点个数。

2.2 算法步骤

为了解决最大流算法计算流量受初始容量限制的问题，同时平衡网络中各节点的能耗，以达到增大网络负载流量的目的，本文提出了EB-DMF路由算法。该算法的实现过程如图2所示。

图2 EB-DMF路由算法的流程图

Step 1 算法的初始化

初始化网络，设置源节点和目的节点的能量为∞，其他节点的能量为初始能量值。根据式(6)计算每条边上的容量C(vi，vj)。设置节点的发包速率。根据边容量C(vi，vj)计算增广路径和流量。

Step 2 更新节点的能量和边容量

将源节点的待发包数目设置为发包速率的取值(发包时间间隔设置为1 s)。如果数据包是第1次传输，此时没有能量收集过程，不需要更新节点的能量和边容量，转到Step 3。若数据包不是第1次传输，则需要更新能量和边容量，重新计算增广路径和流量，转到Step 3。

Step 3 寻找节点的下一跳

亲缘、地缘的关系中，不光只是合作、支持，有时也有相互竞争的情况。从促进成功这一个角度来看，与同伴的竞争是通往成功的必然之路。很多时候，觉得前途迷茫、不知道干什么的时候，恰好是与自己有竞争关系的同伴提醒了该往哪里走。同伴是一面镜子，看到自己的不足，大家又互相为门面，彼此给对方增加光彩，让彼此更具有立体感。在组织中，无论是领导者、被领导者，存在感是需要对方来见证。

遍历所有的节点，若节点有数据包待发送，则根据增广路径寻找节点的下一跳。若节点有多个可选下一跳，则选择剩余能量最大的节点作为下一跳节点。

Step 4 向下一跳节点传递数据包

向下一跳节点传递数据包，更新发包节点和收包节点的剩余能量值。将收包节点的待发包数目设置为发包节点的待发包数目，发包节点的待发送数据包数目清零。

判断当前节点是否为目的节点，若节点为目的节点说明此次数据包的传输完成，转到Step 5。若节点不是目的节点，说明仍需要为节点寻找下一跳节点，转到Step 3。

Step 5 判断是否有节点死亡

若有节点死亡，则结束程序。若无节点死亡，则开始新一轮的数据包投递，转到Step 2。

3 算法仿真

当发包速率较小时，节点在发包间隔内收集到的能量足以补充节点发送数据包所消耗的能量，节点不会因为能量耗尽而死亡，此时网络是能量可维持的。相反，当发包速率过大时，节点在发包间隔内收集到的能量不足以补充节点发送数据包所消耗的能量，节点必然会因为能量耗尽而死亡，此时网络是能量不可维持的。网络能量是否可维持与发包速率和能量收集速率有关。网络能量可维持时，网络负载流量是无限大的;网络能量不可维持时，网络负载流量是有限的。在本文中，只讨论网络能量不可维持时的负载流量，研究在能量收集速率不变的情况下发包速率的改变对负载流量的影响。

为了分析EB-DMF路由算法用于EHWSN中计算网络负载流量的性能，在MATLAB中仿真实现EB-DMF路由算法、动态最大流算法(Dynamic Maximum Flow algorithm，DMF)，并与FF算法和改进的能量均衡 Ford-Fulkerson算法(Energy Balanced Ford-Fulkerson algorithm，EB-FF)作比较。

仿真中节点个数设置为8个，包括一个源节点、一个目的节点和6个路由节点。路由节点按照2～7进行编号。能量收集速率如表1设置时，仿真结果表明，当发包速率取值大于18时，网络是能量不可维持的。仿真的所有参数如表1所示。

表1 仿真参数的设置

本文共设置两个仿真场景:

仿真场景1:发包速率取值为24，即每秒发送24个数据包。比较FF、DMF、EB-FF、EB-DMF算法下的网络负载流量，以及各节点的剩余能量。

仿真场景2:能量收集速率不变，改变源节点的发包速率，取值分别为21，24，27，30，33，观察FF、DMF、EB-FF、EB-DMF算法的网络负载流量随发包速率的变化。

3.2 仿真结果分析

3.2.1 仿真场景1下各算法网络负载流量的比较

分别在仿真场景中运行FF、DMF、EB-FF、EBDMF算法，记录网络负载流量，如表2所示。

表2 各种算法下的网络负载流量

①比较DMF算法与FF算法:DMF算法与FF算法有相同的网络负载流量。DMF算法虽然根据收集的能量动态更新了容量值，网络中存在增广路径，却由于增广路径选择的随意性，网络因能量不均衡节点死亡而瘫痪，与同样因为网络能量不均衡的FF算法有相同的负载流量。为比较动态更新容量值和容量受初始能量限制情况下的网络负载流量，不考虑能量不均衡导致的网络生命期过短对网络负载流量的影响，分别在DMF和FF算法中引入能量均衡机制，即②中的EB-DMF算法和EB-FF算法。

②比较EB-DMF算法和EB-FF算法:EB-DMF算法比EB-FF算法有更大的网络负载流量。因为EB-DMF算法根据收集到的能量动态更新边容量，算法因所有路由节点的能量耗尽而结束;而EB-FF算法受初始容量的限制，容量值无法根据收集到的能量更新，算法因为网络中不存在增广路径而结束。

③比较EB-DMF算法和DMF算法:EB-DMF算法比DMF算法有更大的网络负载流量。EB-DMF算法较DMF算法均衡了各节点的能耗，因为剩余能量少的节点不会包含在下一次包投递选择的增广路径中，节点只收集能量，不消耗能量，从而延长了网络的生命期，增大了网络负载流量。

3.2.2 EB-DMF算法、DMF算法、EB-FF算法、FF算法各路由节点剩余能量的比较

从图3中可以看出，FF、DMF算法中，各节点的能耗非常不均衡，出现了2号节点能量耗尽而死亡。这是因为最大流算法增广路径选择的随意性，在一条增广路径上没有达到所能承载的最大流量时，不会选择其他路径，从而导致网络因为能耗不均衡而瘫痪，尽管此时网络中仍存在增广路径。而在FF、DMF算法的基础上进行能量均衡的EB-FF、EBDMF算法，各节点能耗均衡，不会出现部分节点提前耗尽能量的现象，延长网络生命周期的同时也增大了网络负载流量。

图3 各节点的剩余能量比较(FF算法中出现第1个死亡节点时，FF、DMF、EB-FF、EB-DMF算法中各路由节点的剩余能量)

3.2.3 不同发包速率下，各算法网络负载流量比较

图4 不同发包速率下的网络负载流量

从图4可以看出，对于FF和DMF算法，发包速率对网络流量的影响不大，数据包会重复选择同一条路径来传递，只要发包速率取值在该条路径容量所允许的范围内，网络负载流量等于该条增广路径上的容量，而与发包速率无关。对于EB-FF算法和EB-DMF算法，随着发包速率的增加，网络的负载流量减小。在能量收集速率不变的情况下，发包速率越大，每次数据包传输后节点的剩余能量越小，节点的能量耗尽越快，自然网络的生命期就越短，网络能够承载的负载流量也越小。但是无论发包速率怎么变化，整个网络在本文所述的EB-DMF算法下比其他3种算法有更大的负载流量，体现了本文所述算法的优越性。

4 结束语

本文针对能量收集无线传感器网络的最大流量问题，对Ford-Fulkson最大流算法进行改进，提出了EB-DMF路由算法。在增广路径的选择中选取剩余能量较大的节点，以均衡网络能耗，延长网络的生命期。同时，动态更新网络的容量值，解决了网络容量受初始容量限制的问题，从而保证了节点收集到的能量能用于网络容量的计算。仿真结果显示，EBDMF路由协议能够增大网络负载流量，延长网络的生命期。本文目前研究了节点能量收集速率相同情况下的网络负载流量，而节点能量收集速率不相同时，节点是否需要休眠，网络拓扑是否连通等相关问题对网络负载流量的影响还需要进行深入研究。在后续的工作中，主要针对节点能量收集速率不同情况下，节点状态和可变拓扑对路由选取和网络负载流量的影响进行进一步的研究。

［1］ Shaikh F K，Zeadally S，Exposito E.Enabling Technologies for Green Internet of Things［J］.IEEE Systems Journal，2015:1－12.

［2］ Abd M A，Al-Rubeaai S F M，Singh B K，et al.Extending Wireless Sensor Network Lifetime with Global Energy Balance［J］.IEEE Sensors Journal，2015，15(9):5053－5063.

［3］ Razaque A，Abdulgader M，Joshi C，et al.P-LEACH:Energy Efficient Routing Protocol for Wireless Sensor Networks［C］//2016 IEEE Long Island Systems，Applications and Technology Conference (LISAT).New York:IEEE，2016:1－5.

［4］ 仇英辉，陈玲.基于普通节点负载均衡的RPL路由协议［J］.传感技术学报，2016，29(7):1077－1082.

［5］ 叶继华，王文，江爱文.一种基于LEACH的异构WSN能量均衡成簇协议［J］.传感技术学报，2015，28(12):1853－1860.

［6］ Shaikh F K，Zeadally S.Energy Harvesting in Wireless Sensor Networks:A Comprehensive Review［J］.Renewable and Sustainable Energy Reviews，2016，55:1041－1054.

［7］ Yi J M，Kang M J，Noh D K.Solar Castalia:Solar Energy Harvesting Wireless Sensor Network Simulator［J］.International Journal of Distributed Sensor Networks，2015:1－10.

［8］ Jia Y，Seshia A A.Power Optimization by Mass Tuning for MEMS Piezoelectric Cantilever Vibration Energy Harvesting［J］.Journal of Microelectromechanical Systems，2016，25(1):108－117.

［9］ 李朝辉，张珣.环境能量收集技术及其在无线传感器网络中的应用［J］.物联网技术，2014，4(11):76－78.

［10］张明.具有能量收集功能的无线传感器网络最优传输策略研究［D］.南京:南京邮电大学，2014.

［11］Bogliolo A，Lattanzi E，Acquaviva A.Energetic Sustainability of Environmentally Powered Wireless Sensor Networks［C］//Proceedings of the 3rd ACM International Workshop on Performance Evaluation of Wireless Ad Hoc，Sensor and Ubiquitous Networks.Spain: ACM，2006:149－152.

［12］ Lattanzi E，Regini E，Acquaviva A，et al.Energetic Sustainability of Routing Algorithms for Energy-Harvesting Wireless Sensor Networks［J］.Computer Communications，2007，30(14):2976－2986.

［13］王战备.无线传感器网络能耗分析与节能策略研究［J］.信息通信，2010(4):41－43.

毛善丽(1991－)，女，湖北荆州人，硕士研究生，研究方向为无线传感器网络，maoshanli_wust@163.com;

李晓卉(1978－)，女，博士、教授、硕士导师，研究方向为无线传感器网络技术，智能家居控制，复杂网络理论，智能电网需求响应理论及应用等，lixiaohui @wust.edu.cn。

The Energy Balanced and Dynamic Maximum Flow Routing Algorithm Based on EHWSN*

MAO Shanli1，LI Xiaohui1*，CAI Bin1，DING Yuemin2
(1.College of Information Science and Engineering，Wuhan University of Science and Technology，Wuhan 430081，China; 2.College of Computer and Communication Engineering，Tianjin University of Technology，Tianjin 300384，China)

When using maximum flow algorithm for the energy harvesting wireless sensor network(EHWSN)to achieve the maximum load flow，it is easy to make energy consumption unbalanced and the capacity of the network is limited to its initial energy.To solve the above problems，an improved energy balanced and dynamic maximum flow(EB-DMF)routing algorithm was proposed.The proposed routing algorithm introduced energy balanced mechanism to the selection of augmenting path，and automatically updated the value of capacity according to the harvested energy of the nodes.Accordingly，energy consumption of the network was balanced.Moreover，the lifetime and load flow of the network were extended.Simulation results show that the proposed EB-DMF algorithm has advantages over maximum flow algorithm with respect to extending the load flow and lifetime of the network.

energy harvesting wireless sensor network(EHWSN);load flow;dynamic maximum flow routing algorithm;energy balanced

TP393

A

1004－1699(2017)02－0291－05

C:6150P

10.3969/j.issn.1004－1699.2017.02.021

项目来源:国家自然科学基金项目(61105070);天津市科委面上项目(15JCYBJC52400);湖北省高校图工委科研基金研究项目(2015－YB－06)

2016－08－10 修改日期:2016－09－14