基于EHWSN的能量均衡動態(tài)最大流路由算法*

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

(1.武漢科技大學信息科學與工程學院，武漢430081;2.天津理工大學計算機與通信工程學院，天津300384)

基于EHWSN的能量均衡動態(tài)最大流路由算法*

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

(1.武漢科技大學信息科學與工程學院，武漢430081;2.天津理工大學計算機與通信工程學院，天津300384)

針對最大流算法應用于能量收集無線傳感器網(wǎng)絡求解網(wǎng)絡負載流量時，存在能量不均衡，網(wǎng)絡容量受初始容量限制的問題，提出了一種能量均衡的動態(tài)最大流路由算法——EB-DMF。該算法在增廣路徑的選擇中引入能量均衡機制，并根據(jù)節(jié)點收集的能量動態(tài)更新容量值，使網(wǎng)絡能耗均衡，達到延長網(wǎng)絡生命期，增大網(wǎng)絡負載流量的目的。仿真結果表明與最大流算法相比，該算法能在增大網(wǎng)絡負載流量的同時延長網(wǎng)絡的生命期。

能量收集無線傳感器網(wǎng)絡;負載流量;動態(tài)最大流路由算法;能量均衡

在傳統(tǒng)的無線傳感器網(wǎng)絡 WSN(Wireless Sensor Networks)中，電池供電是傳感器節(jié)點的主要供能方式。然而，對WSN的生命期要求較高但電池更換困難的應用，節(jié)點電池儲能的耗盡意味著整個無線傳感器網(wǎng)絡的癱瘓，因此，能量受限一直是WSN應用的瓶頸［1］。這就使得傳統(tǒng)WSN路由的設計都是以減少能耗、均衡負載來延長網(wǎng)絡生命周期為首要目標［2－5］。近年來硬件技術的發(fā)展使得節(jié)點可以利用能量收集裝置從外界環(huán)境中獲取能量［6］，例如太陽能［7］、振動［8－9］、溫度差等。能量收集技術的出現(xiàn)在一定程度上緩解了無線傳感器網(wǎng)絡節(jié)點能量受限的問題，使得自供能、持久且免維護的能量收集無線傳感器網(wǎng)絡EHWSN(Energy Harvesting Wireless Sensor Network)成為可能。由于能量采集的特性，EHWSN路由設計主要圍繞均衡網(wǎng)絡能耗，最大化網(wǎng)絡負載流量而展開［10］，網(wǎng)絡負載流量指的是網(wǎng)絡生命周期內所能承載的數(shù)據(jù)包個數(shù)。

目前不少學者為提高EHWSN的吞吐量將解決最大流問題的 Ford-Fulkerson(FF)算法引入到EHWSN中［11－12］，將節(jié)點的能量與容量關聯(lián)，通過FF算法尋找增廣路徑，計算網(wǎng)絡的最大流量。文獻［11］論證了FF算法可以用于無線傳感器網(wǎng)絡來尋找最大流，并給出了網(wǎng)絡能量可維持需要滿足的條件。文獻［12］在文獻［11］的基礎上設計了一種優(yōu)化路由算法，來最大化自供能網(wǎng)絡的負載流量。然而，將FF算法應用于能量收集無線傳感器網(wǎng)絡存在以下兩個問題:①節(jié)點的能量是不斷更新的，節(jié)點收集到的能量可以用于數(shù)據(jù)包的傳輸，不更新容量的靜態(tài)最大流路由算法受初始容量限制，網(wǎng)絡無法達到最大流量。②基于FF最大流路由算法的增廣路徑選擇具有隨意性，使得網(wǎng)絡中部分節(jié)點的能量消耗過快，網(wǎng)絡能耗不均衡，節(jié)點會過早死亡，網(wǎng)絡無法達到最大流量。

為解決上述問題，本文提出了一種能量均衡動態(tài)最大流路由算法 EB-DMF(Energy Balanced and Dynamic Maximum Flow routing algorithm)。該算法在FF最大流算法的基礎上，①根據(jù)節(jié)點收集到的能量動態(tài)更新FF算法的容量值，并利用新的容量值計算網(wǎng)絡的增廣路徑及流量;②根據(jù)節(jié)點的剩余能量來選擇增廣路徑，達到能量均衡的目的。仿真結果表明:與FF算法相比，該算法能在增大網(wǎng)絡負載流量的同時均衡網(wǎng)絡能量消耗延長網(wǎng)絡生命周期。

1 能量收集無線傳感器網(wǎng)絡

1.1 能量收集無線傳感器網(wǎng)絡的結構

能量收集無線傳感器網(wǎng)絡的結構如圖1所示。能量收集無線傳感器節(jié)點由能量收集裝置，無線通信模塊，傳感器和控制器組成。圖1以收集太陽能為例，節(jié)點將收集的太陽能轉換成電能，存儲在電池中，用于節(jié)點數(shù)據(jù)包的處理。

圖1 EHWSN的結構

1.2 網(wǎng)絡模型

能量收集無線傳感器網(wǎng)絡可以用有向圖G= (V，E)表示。其中，v∈V的頂點代表網(wǎng)絡的節(jié)點。(vi，vj)∈E可以表示節(jié)點間的無線鏈路，數(shù)據(jù)包傳遞的方向就是流量流動的方向。對于每條邊(vi，vj)，賦予容量值C(vi，vj)≥0，來表示允許通過該邊的容量。在實際的數(shù)據(jù)包傳輸過程中，根據(jù)FF算法計算增廣路徑，增廣路徑上的每條邊都會有一個流量f(vi，vj)。所有增廣路徑上的流量之和即為網(wǎng)絡的最大負載流量。

設置網(wǎng)絡中所有邊的流量初始值f(vi，vj)=0，根據(jù)節(jié)點的剩余能量計算的容量值為C(vi，vj)，由最大流算法可以計算出從源節(jié)點到目的節(jié)點的每條增廣路徑pk∈P上的流量fpk及增廣路徑集合P。

每條增廣路徑pk均可以用節(jié)點集合表示:

增廣路徑pk上的流量:

即增廣路徑pk上的流量等于該條路徑上邊容量的最小值。

網(wǎng)絡負載流量f可表示如下:

由上述公式可知，增大網(wǎng)絡負載流量需要增大增廣路徑上邊容量C(vi，vj)的值。

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

2.1 動態(tài)更新EB-DMF的容量值

節(jié)點處理數(shù)據(jù)包的能耗包括數(shù)據(jù)的采樣、處理能耗和數(shù)據(jù)包的傳輸能耗。其中，數(shù)據(jù)的采集、處理能耗可以近似為常量，且相對于傳輸能耗可以忽略不計［13］。因此本文處理數(shù)據(jù)包的能耗指的是數(shù)據(jù)包的傳輸能耗，即發(fā)送和接收數(shù)據(jù)包的能耗。

設節(jié)點i在t時刻的剩余能量為Ei(t)，數(shù)據(jù)包發(fā)送的時間間隔為τs，數(shù)據(jù)包傳輸?shù)穆窂娇梢杂霉?jié)點的集合{vs，…，vm，…，vt}表示。發(fā)送一個數(shù)據(jù)包的能耗為Esend，接收一個數(shù)據(jù)包的能耗為Erec，節(jié)點i每秒收集到的能量為Ehav，源節(jié)點的發(fā)包速率為Rpkg，即源節(jié)點每秒發(fā)送的數(shù)據(jù)包數(shù)目為Rpkg。節(jié)點i在t+τ時刻的剩余能量Ei(t+τ)可以根據(jù)下述公式計算:

t+τ時刻的邊容量計算如下:

式中:C(vi，vj)表示邊(vi，vj)上的容量，Ni表示根據(jù)廣度優(yōu)先搜索計算的節(jié)點i的下層鄰居節(jié)點個數(shù)。

2.2 算法步驟

為了解決最大流算法計算流量受初始容量限制的問題，同時平衡網(wǎng)絡中各節(jié)點的能耗，以達到增大網(wǎng)絡負載流量的目的，本文提出了EB-DMF路由算法。該算法的實現(xiàn)過程如圖2所示。

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

Step 1 算法的初始化

初始化網(wǎng)絡，設置源節(jié)點和目的節(jié)點的能量為∞，其他節(jié)點的能量為初始能量值。根據(jù)式(6)計算每條邊上的容量C(vi，vj)。設置節(jié)點的發(fā)包速率。根據(jù)邊容量C(vi，vj)計算增廣路徑和流量。

Step 2 更新節(jié)點的能量和邊容量

將源節(jié)點的待發(fā)包數(shù)目設置為發(fā)包速率的取值(發(fā)包時間間隔設置為1 s)。如果數(shù)據(jù)包是第1次傳輸，此時沒有能量收集過程，不需要更新節(jié)點的能量和邊容量，轉到Step 3。若數(shù)據(jù)包不是第1次傳輸，則需要更新能量和邊容量，重新計算增廣路徑和流量，轉到Step 3。

Step 3 尋找節(jié)點的下一跳

親緣、地緣的關系中，不光只是合作、支持，有時也有相互競爭的情況。從促進成功這一個角度來看，與同伴的競爭是通往成功的必然之路。很多時候，覺得前途迷茫、不知道干什么的時候，恰好是與自己有競爭關系的同伴提醒了該往哪里走。同伴是一面鏡子，看到自己的不足，大家又互相為門面，彼此給對方增加光彩，讓彼此更具有立體感。在組織中，無論是領導者、被領導者，存在感是需要對方來見證。

遍歷所有的節(jié)點，若節(jié)點有數(shù)據(jù)包待發(fā)送，則根據(jù)增廣路徑尋找節(jié)點的下一跳。若節(jié)點有多個可選下一跳，則選擇剩余能量最大的節(jié)點作為下一跳節(jié)點。

Step 4 向下一跳節(jié)點傳遞數(shù)據(jù)包

向下一跳節(jié)點傳遞數(shù)據(jù)包，更新發(fā)包節(jié)點和收包節(jié)點的剩余能量值。將收包節(jié)點的待發(fā)包數(shù)目設置為發(fā)包節(jié)點的待發(fā)包數(shù)目，發(fā)包節(jié)點的待發(fā)送數(shù)據(jù)包數(shù)目清零。

判斷當前節(jié)點是否為目的節(jié)點，若節(jié)點為目的節(jié)點說明此次數(shù)據(jù)包的傳輸完成，轉到Step 5。若節(jié)點不是目的節(jié)點，說明仍需要為節(jié)點尋找下一跳節(jié)點，轉到Step 3。

Step 5 判斷是否有節(jié)點死亡

若有節(jié)點死亡，則結束程序。若無節(jié)點死亡，則開始新一輪的數(shù)據(jù)包投遞，轉到Step 2。

3 算法仿真

當發(fā)包速率較小時，節(jié)點在發(fā)包間隔內收集到的能量足以補充節(jié)點發(fā)送數(shù)據(jù)包所消耗的能量，節(jié)點不會因為能量耗盡而死亡，此時網(wǎng)絡是能量可維持的。相反，當發(fā)包速率過大時，節(jié)點在發(fā)包間隔內收集到的能量不足以補充節(jié)點發(fā)送數(shù)據(jù)包所消耗的能量，節(jié)點必然會因為能量耗盡而死亡，此時網(wǎng)絡是能量不可維持的。網(wǎng)絡能量是否可維持與發(fā)包速率和能量收集速率有關。網(wǎng)絡能量可維持時，網(wǎng)絡負載流量是無限大的;網(wǎng)絡能量不可維持時，網(wǎng)絡負載流量是有限的。在本文中，只討論網(wǎng)絡能量不可維持時的負載流量，研究在能量收集速率不變的情況下發(fā)包速率的改變對負載流量的影響。

為了分析EB-DMF路由算法用于EHWSN中計算網(wǎng)絡負載流量的性能，在MATLAB中仿真實現(xiàn)EB-DMF路由算法、動態(tài)最大流算法(Dynamic Maximum Flow algorithm，DMF)，并與FF算法和改進的能量均衡 Ford-Fulkerson算法(Energy Balanced Ford-Fulkerson algorithm，EB-FF)作比較。

仿真中節(jié)點個數(shù)設置為8個，包括一個源節(jié)點、一個目的節(jié)點和6個路由節(jié)點。路由節(jié)點按照2～7進行編號。能量收集速率如表1設置時，仿真結果表明，當發(fā)包速率取值大于18時，網(wǎng)絡是能量不可維持的。仿真的所有參數(shù)如表1所示。

表1 仿真參數(shù)的設置

本文共設置兩個仿真場景:

仿真場景1:發(fā)包速率取值為24，即每秒發(fā)送24個數(shù)據(jù)包。比較FF、DMF、EB-FF、EB-DMF算法下的網(wǎng)絡負載流量，以及各節(jié)點的剩余能量。

仿真場景2:能量收集速率不變，改變源節(jié)點的發(fā)包速率，取值分別為21，24，27，30，33，觀察FF、DMF、EB-FF、EB-DMF算法的網(wǎng)絡負載流量隨發(fā)包速率的變化。

3.2 仿真結果分析

3.2.1 仿真場景1下各算法網(wǎng)絡負載流量的比較

分別在仿真場景中運行FF、DMF、EB-FF、EBDMF算法，記錄網(wǎng)絡負載流量，如表2所示。

表2 各種算法下的網(wǎng)絡負載流量

①比較DMF算法與FF算法:DMF算法與FF算法有相同的網(wǎng)絡負載流量。DMF算法雖然根據(jù)收集的能量動態(tài)更新了容量值，網(wǎng)絡中存在增廣路徑，卻由于增廣路徑選擇的隨意性，網(wǎng)絡因能量不均衡節(jié)點死亡而癱瘓，與同樣因為網(wǎng)絡能量不均衡的FF算法有相同的負載流量。為比較動態(tài)更新容量值和容量受初始能量限制情況下的網(wǎng)絡負載流量，不考慮能量不均衡導致的網(wǎng)絡生命期過短對網(wǎng)絡負載流量的影響，分別在DMF和FF算法中引入能量均衡機制，即②中的EB-DMF算法和EB-FF算法。

②比較EB-DMF算法和EB-FF算法:EB-DMF算法比EB-FF算法有更大的網(wǎng)絡負載流量。因為EB-DMF算法根據(jù)收集到的能量動態(tài)更新邊容量，算法因所有路由節(jié)點的能量耗盡而結束;而EB-FF算法受初始容量的限制，容量值無法根據(jù)收集到的能量更新，算法因為網(wǎng)絡中不存在增廣路徑而結束。

③比較EB-DMF算法和DMF算法:EB-DMF算法比DMF算法有更大的網(wǎng)絡負載流量。EB-DMF算法較DMF算法均衡了各節(jié)點的能耗，因為剩余能量少的節(jié)點不會包含在下一次包投遞選擇的增廣路徑中，節(jié)點只收集能量，不消耗能量，從而延長了網(wǎng)絡的生命期，增大了網(wǎng)絡負載流量。

3.2.2 EB-DMF算法、DMF算法、EB-FF算法、FF算法各路由節(jié)點剩余能量的比較

從圖3中可以看出，F(xiàn)F、DMF算法中，各節(jié)點的能耗非常不均衡，出現(xiàn)了2號節(jié)點能量耗盡而死亡。這是因為最大流算法增廣路徑選擇的隨意性，在一條增廣路徑上沒有達到所能承載的最大流量時，不會選擇其他路徑，從而導致網(wǎng)絡因為能耗不均衡而癱瘓，盡管此時網(wǎng)絡中仍存在增廣路徑。而在FF、DMF算法的基礎上進行能量均衡的EB-FF、EBDMF算法，各節(jié)點能耗均衡，不會出現(xiàn)部分節(jié)點提前耗盡能量的現(xiàn)象，延長網(wǎng)絡生命周期的同時也增大了網(wǎng)絡負載流量。

圖3 各節(jié)點的剩余能量比較(FF算法中出現(xiàn)第1個死亡節(jié)點時，F(xiàn)F、DMF、EB-FF、EB-DMF算法中各路由節(jié)點的剩余能量)

3.2.3 不同發(fā)包速率下，各算法網(wǎng)絡負載流量比較

圖4 不同發(fā)包速率下的網(wǎng)絡負載流量

從圖4可以看出，對于FF和DMF算法，發(fā)包速率對網(wǎng)絡流量的影響不大，數(shù)據(jù)包會重復選擇同一條路徑來傳遞，只要發(fā)包速率取值在該條路徑容量所允許的范圍內，網(wǎng)絡負載流量等于該條增廣路徑上的容量，而與發(fā)包速率無關。對于EB-FF算法和EB-DMF算法，隨著發(fā)包速率的增加，網(wǎng)絡的負載流量減小。在能量收集速率不變的情況下，發(fā)包速率越大，每次數(shù)據(jù)包傳輸后節(jié)點的剩余能量越小，節(jié)點的能量耗盡越快，自然網(wǎng)絡的生命期就越短，網(wǎng)絡能夠承載的負載流量也越小。但是無論發(fā)包速率怎么變化，整個網(wǎng)絡在本文所述的EB-DMF算法下比其他3種算法有更大的負載流量，體現(xiàn)了本文所述算法的優(yōu)越性。

4 結束語

本文針對能量收集無線傳感器網(wǎng)絡的最大流量問題，對Ford-Fulkson最大流算法進行改進，提出了EB-DMF路由算法。在增廣路徑的選擇中選取剩余能量較大的節(jié)點，以均衡網(wǎng)絡能耗，延長網(wǎng)絡的生命期。同時，動態(tài)更新網(wǎng)絡的容量值，解決了網(wǎng)絡容量受初始容量限制的問題，從而保證了節(jié)點收集到的能量能用于網(wǎng)絡容量的計算。仿真結果顯示，EBDMF路由協(xié)議能夠增大網(wǎng)絡負載流量，延長網(wǎng)絡的生命期。本文目前研究了節(jié)點能量收集速率相同情況下的網(wǎng)絡負載流量，而節(jié)點能量收集速率不相同時，節(jié)點是否需要休眠，網(wǎng)絡拓撲是否連通等相關問題對網(wǎng)絡負載流量的影響還需要進行深入研究。在后續(xù)的工作中，主要針對節(jié)點能量收集速率不同情況下，節(jié)點狀態(tài)和可變拓撲對路由選取和網(wǎng)絡負載流量的影響進行進一步的研究。

［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］ 仇英輝，陳玲.基于普通節(jié)點負載均衡的RPL路由協(xié)議［J］.傳感技術學報，2016，29(7):1077－1082.

［5］ 葉繼華，王文，江愛文.一種基于LEACH的異構WSN能量均衡成簇協(xié)議［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］ 李朝輝，張珣.環(huán)境能量收集技術及其在無線傳感器網(wǎng)絡中的應用［J］.物聯(lián)網(wǎng)技術，2014，4(11):76－78.

［10］張明.具有能量收集功能的無線傳感器網(wǎng)絡最優(yōu)傳輸策略研究［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］王戰(zhàn)備.無線傳感器網(wǎng)絡能耗分析與節(jié)能策略研究［J］.信息通信，2010(4):41－43.

毛善麗(1991－)，女，湖北荊州人，碩士研究生，研究方向為無線傳感器網(wǎng)絡，maoshanli_wust@163.com;

李曉卉(1978－)，女，博士、教授、碩士導師，研究方向為無線傳感器網(wǎng)絡技術，智能家居控制，復雜網(wǎng)絡理論，智能電網(wǎng)需求響應理論及應用等，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