WSN中基于能量感知的最小跳數路由算法

朱報開

(廣東科創工程技術有限公司，廣東 東莞 523808)

WSN中基于能量感知的最小跳數路由算法

朱報開

(廣東科創工程技術有限公司，廣東 東莞 523808)

無線傳感器網絡的拓撲往往由于節點死亡而發生變化。網絡拓撲的重新構建加速了剩余傳感器節點的死亡，縮短了網絡的生存時間。針對無線傳感器網絡對網絡生存時間的苛刻要求，提出了一種基于能量感知的最小跳數路由算法。建立路由時，該算法綜合考慮了節點剩余能量和該節點潛在的轉發能力。仿真結果顯示，該算法在生存時間、存活節點數和吞吐量方面的性能要遠優于LEACH算法和HEED算法。

無線傳感器網絡;能量感知;最小跳數;生存時間;存活節點;吞吐量

0 引言

對城市供水水質的監測是保障居民用水安全、建設智慧城市的一個重要手段。當前普遍的做法是在供水管網的重要位置或區域，通過密集地布置大量傳感器節點組成的無線傳感器網絡(Wireless Sensor Networks，WSN)對水質進行測控;甚至可以通過無線傳感器網絡采集到的數據，發現水質變化的趨勢，達到盡早地介入、進行預處理的預警目的。由于能量限制的原因，無線傳感器網絡的拓撲經常會由于節點死亡而重構，重構的過程又會進一步加劇生存節點的能量消耗，文獻［1－9］就如何延長無線傳感器網絡的生存時間這一熱點問題做了一些研究。針對水質監測預警，設計了一種結合了能量感知和最小跳數的路由算法，在延長無線傳感器網絡生存周期的同時，又能盡快地交付數據。

1 研究背景

無線傳感器網絡是由大量靜止的或移動的傳感器節點以自組和多跳方式構成的無線網絡，主要功能為感知、采集和處理網絡覆蓋地理區域內被感知對象的信息。無線傳感器網絡示意如圖1所示。

圖1 無線傳感器網絡示意

圖1中，普通節點根據特定的路由協議將采集到的數據上傳給簇頭，然后由簇頭通過sink節點發送給其他網絡。由于WSN中的節點基本上采用的都是自供電方式，因此，研發簡潔有效的路由協議是影響整個網絡生存時間和數據交付的重要因素之一。近年來，有不少學者圍繞著無線傳感器網絡的能量感知和最小跳數路由方面展開了研究工作。

文獻［10］提出了一種用于無線傳感器網絡中的能量平衡分簇算法，在簇信息共享、簇頭選擇、簇內節點和簇間通信等方面達成能量開銷的平衡，以其達到延長網絡生存時間的目的;文獻［11］針對LEACH(Low Energy Adaptive Clustering Hierarchy)協議中隨機選擇簇頭的缺陷提出了能量自適應的優化措施，保證了整個網絡中能耗的平衡;文獻［12］提出了一種概率簇頭選擇方法對無線傳感器網絡中的能耗和生存時間進行了分析和仿真;文獻［13］提出了一種無線傳感器網絡中錯誤容忍分簇的算法，當分簇失敗時該算法使用了檢測和重新發現2個步驟從漏選的網關中重新發現傳感器節點的，從而避免了系統中重新分簇的問題;文獻［14］為單跳傳感器網絡設計了一種能效分簇機制來解決周期性采集數據時的能耗問題，該機制通過自主地選擇剩余能量更多的節點作為簇頭，從而達到了在簇頭間平衡負載的目的;文獻［15］提出的層次型能效分簇算法通過分層次的選舉簇頭達到降低能耗的目的，仿真結果表明隨著層次數量的增多，能耗降低越多。但是，由于基于能量感知的路由算法沒有考慮路徑的長短，過長的路徑勢必影響到數據的實時性交付。所以，以上研究并不適用于實時性很強的應用，如水質監測預警等。

文獻［16］提出了一種基于最小跳數的分簇路由算法，算法優化了 HEED(Hybrid Energy-Efficient，Distributed clustering)算法中簇頭的選擇策略，此外，算法中節點根據其鄰節點的廣播信息計算最小跳數，在下一跳節點的選擇過程中考慮了候選節點到基站的最小跳數、節點的能量以及節點到基站的距離，并在不同情況下令3個因素所起的作用不同，進而提高路由效率。文獻［17］在節點中利用鄰居表記錄了所有相鄰節點的信息，節點依照父節點(跳數比自身小1)、兄弟節點(跳數與自身相等)、子節點(跳數比自身大1)順序的優先級，隨機挑選下一跳節點并轉發數據分組。文獻［18］提出在每個節點打開時，向周圍節點發送join報文，周圍節點接收到該報文后，將各自的跳數值返回給新加入的節點來完成梯度的建立與更新。該算法能避免通過周期性洪泛實現網絡組建而造成不必要的資源消耗并解決節點實時加入網絡的問題，但同時回復 join報文也增加了周圍節點的能量消耗。

然而，基于最小跳數的路由算法有時會在網絡中產生大量的冗余信息，同時沒有考慮網絡的能量消耗，從而影響到網絡的生存時間。文獻［19］研究了基于改進蟻群算法的無線傳感器網絡最小跳數路由選擇方法，利用改進蟻群算法出色的全局尋優能力，對無線傳感器網絡中最小跳數路由選擇問題進行優化，從而優化了無線傳感器網絡節點傳播和處理數據的能力，減少了節點能量消耗。

鑒于基于能量感知和最小跳數路由存在的缺陷，本文提出了一種基于最小跳數的高效路由算法。此算法的思想是:當存在多條相同跳數的最小路徑時，進行能量最優化選擇，選擇能效較高的路徑進行數據傳輸。所謂的能效較高，就是在路由時選擇節點能效較高地進行數據傳輸，這樣低能效節點就可以延長其壽命，整個網絡的生存時間得以延長。

2 算法設計

首先，對本文使用的幾個概念進行說明:

節點剩余能量:傳感器節點在任何狀態下所剩下的能量，使得傳感器節點能繼續工作的剩余能量。

節點服務度:指的是需要經過某節點將數據轉發給sink的所有節點數，即該節點可以為多少個節點提供服務。

節點能效:指的是剩余能量/節點服務度，即某節點能夠為一單位服務提供的能量。單位服務所能提供的能量越高，節點能效就越高。

節點路徑能效:從sink到某節點路徑上最小的路徑服務能效，綜合了最小路徑和服務能效2方面，傳感器節點在傳輸數據過程中根據節點路徑能效來選擇下一跳節點。

算法的核心思想是用遞歸函數進行迭代運算出某節點到sink的最小路徑能效，節點通過最小路徑能效值尋找下一跳。整個網絡通過迭代計算出某一節點到sink的最大路徑能效，然后將該路徑的最大路徑能效值與該節點的服務能效進行比較，選出其中最小值作為路徑的最小路徑能效。

2．1 構建網絡拓撲

① 傳感器節點隨機分布在某一區域，網絡初始化結束后，普通節點會在網絡中廣播Hello分組，網絡中的多個節點會收到未入網節點的 Hello分組，但只有sink或其他已入網的節點收到Hello分組后會反饋Beacon幀給該未入網的節點，使得該節點能夠入網。

② Beacon幀包含節點的地址，跳數和能量信息。節點提取 Beacon的信息，通過比較節點跳數，選擇跳數最小的節點。將最小跳數節點加入直連父節點鄰居列表，并保存節點的位置信息和剩余能量，更新本節點到sink的最小跳數。

③節點確定自己的父節點后會發送ACK幀進行確認，表明隸屬于該父節點。由于節點的父節點鄰居列表中可能含有多個最小跳數的父節點，就需要發送多個 ACK幀。ACK幀包含節點的位置信息，目的節點的位置信息(父節點的信息)。當父節點收到子節點的信息后，將子節點列入子節點的鄰居列表中，保存子節點的位置信息。

2．2 獲取節點服務度

節點的服務度包含節點的子節點，以及子節點的所有下級節點。節點的服務度值是運用一個遞歸函數進行統計節點的服務度，每個節點都有自己的子節點鄰居列表，通過層層計算返回每一層節點的服務度便可以計算出該節點的服務度。

2．3 計算節點能效

服務單位節點數可用的能量值，節點統計自身剩余能量和服務度后，計算出節點能效值，為計算路徑能效做好準備。

2．4 計算路徑能效值

節點路徑能效取值是比較最小路徑中所有節點的節點能效，取能效最低的那個值，稱為最小路徑能效。節點路徑能效也是運用一個遞歸函數進行運算的。通過不斷調用遞歸函數，層層遞歸算出每個節點的路徑能效，一直推算到距離sink一跳范圍內的節點(最后一跳)，最后一跳節點的路徑能效值就等于最后一跳節點的能效值，這就是該遞歸的函數的截至條件。

2．5 路由選擇

當有數據包需要轉發的時候，節點會計算路徑能效值，在路由選擇過程中，每個節點都保存最小路徑臨近下一跳的信息，當每個節點有多個下一跳可供選擇時，此時要比較不同路徑的路徑能效值，選擇路徑能效值最大的作為路由。依此類推，一直重復到將數據交付給sink為止。

3 算法仿真和性能分析

為了很好地評估算法的性能，選擇了基于能量感知的LEACH算法和基于最小跳數的HEED算法進行對比。

LEACH協議中，為了盡可能地平衡各個節點的能耗，簇頭是周期性按輪隨機選舉出來的。每輪可以分為簇建立和穩定工作2個階段。在簇建立階段，協議按照一定比例隨機地選取若干個節點作為簇頭。在選定簇頭后，簇頭向周圍節點廣播自己成為簇頭的消息，節點根據接收到的消息強度來決定加入哪個簇，并告知相應的簇頭，從而進行通信。在穩定工作階段，節點持續采集數據，交付給簇頭，進行必要的融合處理之后，發送到 sink。持續一段時間以后，整個網絡進入下一輪工作周期，重新選擇簇頭。

HEED協議是混合的能量有效的分布式簇頭選舉協議，對LEACH簇頭分布不均勻問題進行了改進。HEED除了把節點剩余能量作為一個參數引入算法外，還考慮到了簇內平均可達能量，在簇重疊區域中的節點根據簇內平均可達能量選擇最終加入哪個簇。HEED協議能產生分布更均勻的簇頭，全網能耗更加均衡。

在節點平均剩余能量、網絡存活節點數和吞吐量3個方面進行了比較:

① 節點平均剩余能量是指仿真結束時，傳感器網絡中所有節點剩余能量的平均值;

② 網絡存活節點數是指仿真結束時，網絡中存活節點數;

③ 吞吐量指的是指仿真結束時，通過sink的總數據量。

仿真是在Matlab 7．0．4的環境下進行的。在一個100 m×100 m的區域中，100個傳感器節點隨機分布在sink周圍。節點信道延遲100 μs，單個數據分組長度16 Bytes，節點丟包率5%，設置節點初始化能量為1 000個單位量，發送一個分組消耗1個單位量，接收一個分組消耗0．5單位量，節點能量小于10單位量則視為死亡，仿真時間為300 s。3種算法節點平均剩余能量的比較如圖2所示。

從圖2中可以看出，仿真結束時本文提出的算法節點平均剩余能量約為570個單位量，節點平均能量降低了43%;HEED的約為460個單位量，節點平均能量降低了54%;LEACH的約為320個單位量，節點平均能量降低了68%。3種算法中，本文提出的算法性能最優，HEED次之，LEACH最差，分別改善了約11%和25%。

圖2 3種算法節點平均剩余能量的對比

使用3種算法網絡中存活節點數量的對比如圖3所示。

圖3 3種算法存活節點數量的對比

從圖3可以看出，仿真結束時，使用本文提出的算法性能最優，存活節點數為28個，節點生存比例達到了28%;使用HEED和LEACH的分別是10個和7個，節點生存比例分別是10%和7%。

整個仿真期間，使用3種算法WSN中吞吐量的對比如圖4所示。

圖4 3種算法吞吐量的對比

從圖4可以看出，仿真結束時，本文提出的算法完成了約 8．2 MB的吞吐量，HEED完成了約6．9 MB，而LEACH只完成了約5．7 MB。

進行性能對比的節點平均剩余能量的多少直接決定了存活節點數量和吞吐量的大小。通過仿真結果可以看出，在節點平均剩余能量、存活節點數量和吞吐量方面，本文提出的算法性能最好，HEED的次之，LEACH的性能最差。這是因為在LEACH協議中，由于簇頭是隨機選擇的，因此LEACH協議不能保證簇頭節點的均勻分布，這將導致部分簇頭節點的能耗過大，影響網絡的生存時間;另外，LEACH中要頻繁地選舉簇頭，并且每次選舉的過程中所有非簇節點都要參與;多輪LEACH協議后，每個節點的剩余電量會出現較大的差異，距離簇頭或基站比較遠的節點耗能比較多，能量很容易耗盡，從而死亡。HEED協議綜合考慮了節點剩余能量和簇內平均可達能量，使得簇頭分布更均勻，全網能耗更加均衡。但是，在選擇路由方面沒有考慮最小跳數，而本文提出的算法兼顧了節點剩余能量和路由選擇的最小跳數，所以無論在節點的平均剩余能量、存活節點數量和吞吐量方面都具有良好的表現。

4 結束語

無線傳感器網絡以其能夠通過分布式處理大量的采集信息和冗余節點等優勢在很多領域得到了應用。但是由于傳感器節點都是依靠自給供電，節點能量有限，如何延長無線傳感器網絡的生存周期無疑成了設計無線傳感器網絡的首要目標。針對當前主流的路由算法缺陷，本文提出了一種基于能量感知的最小跳數路由算法，兼顧了節點剩余能量和路由選擇時的最小跳數。仿真結果證明，該算法無論在節點的平均剩余能量，還是在存活節點數量以及吞吐量方面都有良好的表現。

［1］ 孫大洋，劉衍珩，楊 東，等．無線傳感器網絡生存期優化體系研究［J］．計算機研究與發展，2012，49(1): 193－201．

［2］ 陳 燕，張尚尚，梁俊斌，等．無線傳感網中生命最大化的泛在數據收集協議［J］．計算機應用研究，2014，31 (3):866－871．

［3］ 明 勇，王華軍．WSN中考慮節點磨損的分布式自穩定網絡壽命優化算法［J］．計算機應用研究，2016，33 (3):827－831．

［4］ 唐 偉，郭 偉．WSN聚合數據率約束最大生命期路由［J］．電子科技大學學報，2011，40(1):30－35．

［5］ 張 霞，周 剛，于宏毅．一種協作和中繼混合的傳感網壽命最大化路由算法［J］．軟件學報，2013，24(12): 2 859－2 870．

［6］ 路 綱，周明天，佘 堃，等．無線傳感器網絡路由協議的壽命分析［J］．軟件學報，2009，20(2):375－393．

［7］ ALFIERI A，BIANCO A，BRANDIMARTE P，et al．Maximizing System Lifetime in Wireless Sensor Networks［C］∥USA:in Proceeding of the fourth International Conference on Information Processing in Sensor Networks，2005: 390－402．

［8］ EMRE K M，KUBAN A I，NECATI A，et al．Wireless Sensor Network Lifetime Maximization by Optimal Sensor Deployment，Activity Scheduling，Data Routing and Sink Mobility［J］．Ad Hoc Networks，2014(17):18－36．

［9］ KUMARA A，THOMAS A．Energy Efficiency and Network Lifetime Maximization in Wireless Sensor Networks Using Improved Ant Colony Optimization［J］．Procedia Engineering，2012(38):3 797－3 805．

［10］NAZIR B，HASBULLAH H．Energy Balanced Clustering in Wireless Sensor Network［C］∥USA:in Proceeding of 2010 IEEE International Conference on Information Technology，2010(2):569－574．

［11］LIANG Ying，YU Hai-bin．Energy Adaptive Cluster-Head Selection forWirelessSensorNetworks［C］∥ USA:in Proceeding of Sixth International Conference on Parallel and Distributed Computing，Applications and Technologies，2005: 634－638．

［12］CHOI J，LEE C．Energy Consumption and Lifetime Analysis in Clustered Multi-Hop Wireless Sensor Networks Using the Probabilistic Cluster-Head Selection Method［J］．Eurasip Journalon WirelessCommunications＆ Networking，2011(1):1－13．

［13］GAURAV G，MOHAMED Y．Fault-Tolerant Clustering of Wireless Sensor Network［C］∥USA:in Proceeding of IEEE International Conference on Wireless Communications and Networking，2003:1 579－1 584．

［14］YE Mao，LI Ceng-fa，CHEN Gui-hai，et al．ECCS:An Energy Efficient Clustering Scheme in Wireless Sensor Networks［C］∥USA:in Proceeding of 24th IEEE International Conference on Performance，Computing and Communications，2005:535－540．

［15］SEEMA B，EDWARD J．An Energy Efficient Hierarchical Clustering Algorithm for Wireless Sensor Networks［C］∥USA:in Proceeding of Twenty-Second Annual Joint Conference of the IEEE Computer and Communications，2003:1 713－1 723．

［16］范書平，馬寶英，高晨光，等．一種分簇WSN最小跳數路由算法研究［J］．小型微型計算機系統，2014，35 (8):1 775－1 779．

［17］CHANG S S，HUANG C H，CHANG K C．A Minimum Hop Routing Protocol for Home Security System Using WirelessSensorNetworks［J］．ConsumerElectronics，2007，53(4):1 483－1 489．

［18］段文芳，齊建東．無線傳感器網絡最小跳數路由算法的研究［J］．計算機工程與應用，2010，46(22):88－90．

［19］趙 晗，黃少卿．基于改進蟻群算法的無線傳感器網絡最小跳數路由選擇方法［J］．電信科學，2016，32(3): 113－117．

朱報開 男，(1972—)，工程師。主要研究方向:計算機應用與自動化控制。

A Minimum-hop Routing Algorithm Based on Energy Awareness for Wireless Sensor Networks

ZHU Bao-kai

(Guangdong Forcon Engineering Technology Co．，Ltd，Dongguan Guangdong 523808，China)

The network topology usually varies due to the death of nodes in wireless sensor networks．And，the network lifetime is reduced because the residual nodes will die earlier due to the reconstruction of network topology．Focusing on the strict requirement of wireless sensor networks on the lifetime，a minimum-hop routing algorithm based on energy awareness is proposed．While establishing the routes，the residual energy and the transferring capacity are simultaneously taken into account．Simulation results show that the proposed algorithm can achieve an outstanding performance in terms of lifetime，the number of nodes alive and the throughput compared with LEACH and HEED．

wireless sensor networks;energy awareness;minimum hop;lifetime;node alive;throughput

TP391.4

A< class="emphasis_bold">文章編號 1

1003－3106(2017)02－0015－05

10．3969/j．issn．1003－3106．2017．02．04

朱報開．WSN中基于能量感知的最小跳數路由算法［J］．無線電工程，2017，47(2):15－19．

2016-11-08

廣東省社會公益及能力建設基金資助項目(2015A010103020)。