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

毛善麗，李曉卉*，蔡 彬，丁月民

(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