基于節點度和距離的WSN分簇路由算法

李 輝，劉書吉

?

基于節點度和距離的WSN分簇路由算法

李 輝，劉書吉

(河南理工大學電氣工程與自動化學院，河南 焦作 454000)

針對無線傳感器網絡(WSN)中節點的負載均衡問題，提出一種基于節點度和距離的WSN非均勻分簇路由算法。該算法在首輪成簇時采用了定時機制的簇頭競爭方案，定時的長短取決于節點本身的節點度和距離基站的距離，且節點根據不同的競爭半徑形成不同的簇。在首輪成簇結束后，簇的結構不再發生變化，而簇頭的輪換則根據簇內節點的剩余能量和距離本簇質心的通信代價在簇內進行動態輪換。采用簇間多跳路由，根據節點的剩余能量、距離基站的距離、節點間通信代價和節點的轉發熱度來選擇中繼節點。仿真結果表明，該算法的網絡生命周期與LEACH協議相比延長了2倍以上，與EEUC協議相比延長了13.97%，且均衡了網絡的能量消耗。

無線傳感器網絡；非均勻分簇；節點度；距離；轉發熱度；動態輪換

1 概述

無線傳感器網絡(Wireless Sensor Networks, WSN)是繼互聯網之后的又一個對人類生活產生重大影響的IT技術[1]。由于傳感器節點的能量受限，因此基于分層的路由協議備受關注。基于概率的低功耗自適應分簇協議(Low-energy Adaptive Clustering Hierarchy, LEACH)[2]是最早的分簇路由協議，幾乎貫穿了后來發展的大多數分簇協議。該協議通過等概率隨機循環地選擇簇頭以此來將整個網絡的能量負載平均分配到每個傳感器節點上，從而達到降低網絡能量耗費、延長網絡生命周期的目的[3]。LEACH協議成簇時簇首選擇方法簡單，易于實現。但是，LEACH協議的缺點也非常明顯：(1)在簇頭選擇時沒有考慮能量因素，無論節點的剩余能量多少都有可能成為簇頭，從而加速了低能量節點的死亡；(2)簇頭分布不均；(3)在數據傳輸時采用了單跳模式數據傳輸，當傳輸相同的數據時距離基站遠的簇頭的節點能耗較快。文獻[4]的HEED算法在簇頭選擇時依據主參數能量和次參數簇內通信代價，其分簇速度更快，并且產生的簇頭分布比較均勻、網絡的拓撲結構也更加合理。但是在成簇時通信開銷大。文獻[5]提出的最小ID分簇算法，方法簡單易行。但是在成簇時需要相互交換ID號，帶來很大的能量開銷，并且選擇的簇頭分布不太均勻。文獻[6]提出的集中式分簇算法(LEACH-C)，每輪結束時將能量信息和位置信息發送給基站，由基站來選擇簇頭。雖然解決了簇頭分布不均問題，但是每輪都要發送能量和位置信息浪費了大量的能量。文獻[7]提出的基于競爭的非均勻分簇算法(EEUC)中提出一種部分節點競爭的方式來競爭簇頭。但是每輪都要進行簇頭的競爭，若是參與競爭的節點多時能量浪費比較嚴重。文獻[8]提出了CEERP協議，該協議在數據轉發時利用的是代價函數。主要考慮了當前節點和成為下一跳節點之間的距離和能量的加權值。文獻[9]提出的WSN中基于能量代價的能量優化路由算法在選擇平面路由時利用了節點間能量代價函數和前向區域來選擇下一跳節點。文獻[10]提出的能量均衡的無線傳感器網絡非均勻分簇路由協議分簇時采用了定時機制，一定程度上減少了信息交互量。而選擇路由時采用了貪婪機制和代價函數相結合的方法選擇下一跳。然而，在選擇中繼節點時僅考慮鏈路代價函數，父節點在選擇下一跳節點時具有明顯的傾向性，即在滿足條件的節點中選擇最好的節點來轉發數據，而沒有考慮到節點間的負載均衡。文獻[11]提出支持負載均衡的無線傳感路由協議中為了均衡網絡的能量消耗，使用了“熱度聲明”的策略，通過設定閾值來實現。然而，采用設定閾值的策略，會造成一些有能力承擔轉發任務的節點，因為閾值的原因而不再承擔轉發任務。

針對上述算法不足，本文提出一種基于節點度和距離的無線傳感器網絡非均勻分簇路由算法(Unequal Clustering Routing Algorithm Based on Node Degree and Distance for WSN, UCDD)，該算法在首輪采用定時驅動機制和競爭半徑相結合實現非均勻分簇。簇形成后簇的結構不變，而簇頭的輪換采用簇內動態輪換。在數據傳輸過程中采用了多跳數據傳輸模式，簇頭節點在選擇下一跳中繼節點時依據一種新的代價函數，新的代價函數不僅考慮了節點間的通信代價和節點的剩余能量，還考慮了簇頭的“轉發熱度”。

2 相關模型的假設

2.1 網絡模型的假設

在本文中，網絡中有個傳感器節點隨機分布在一個邊長為正方形區域內，并假設傳感器網絡具有如下性質：

(1)基站部署在正方形監測區域的外側。傳感器節點和基站部署后均不再發生位置變化，且基站唯一。

(2)所有的傳感器節點都是同構的，并在網絡中的地位、作用相同，具有相同的初始能量，并且都有一個且唯一一個ID號，均具備數據融合的能力。

(3)各傳感器節點的能量受限，并且節點具有活動和睡眠兩種狀態的切換能力。

(4)鏈路是對稱的。若已知發送方的發射功率，接收方可以根據信號的強度計算兩者間距離的近似值。

(5)節點位置可以通過定位算法或GPS等方法獲得。

(6)節點可根據距離的遠近調節發射功率以節省能量。

2.2 網絡的能量模型

2.3 數據融合模型

3 UCDD算法的基本思想

本文提出的基于節點度和距離的無線傳感器網絡非均勻分簇路由算法(UCDD)在首輪成簇時采用了基于定時機制的分布式競爭成簇算法，減少了在成簇時信息交互帶來的能量消耗，并且在生成定時器時充分考慮了節點度和節點距離基站的距離因素。多數分簇路由協議采用的周期性成簇機制會帶來一些不必要的能量消耗。因此，UCDD算法只在首輪進行成簇操作，簇一旦形成將不再發生改變，在一定程度上減少了成簇帶來的能量消耗，還可以穩定簇頭的個數。為了減少“熱區”給網絡帶來的影響采用了非均勻分簇的思想，使成簇大小隨著距離基站的距離的增加而增大。簇首的輪換采用簇內動態輪換，在輪換時簇頭節點根據本簇的存活節點的平均能量水平來決定是否選取下一任簇頭節點，并充分考慮了下一任節點的能量水平和距離本簇質心的通信代價。在穩定的數據傳輸階段，簇頭通過多跳的方式將本簇的數據傳給基站，在建立路由時提出一種合理選擇下一跳的代價函數，不僅考慮了節點間的通信代價和節點的剩余能量，還考慮了簇頭的“轉發熱度”。在多跳傳輸過程中，節點通過計算滿足條件的簇頭的代價函數，選擇代價最小的簇頭作為下一跳進行數據的傳輸。由于在選擇下一跳節點時考慮了簇頭的“轉發熱度”，在一定程度上均衡了鏈路之間的能耗，延長了網絡的生命周期。圖1為UCDD算法的原理，圖中大小圓圈代表簇和簇頭，五邊形是基站，帶箭頭的線表示簇間路由[10]。

圖1 UCDD算法原理

3.1 簇的形成

UCDD算法的一種完全分布式的競爭成簇算法，最終目標是實現非均勻分簇。當節點部署結束后，節點通過廣播交換信息來統計節點度信息，根據接收的基站的廣播信號強度計算距離基站的距離。節點信息表見表1。

表1 節點信息表

節點的競爭規則如下：

規則在競爭過程中，節點一旦競爭勝利，將在自己的競爭半徑內廣播成為簇頭的消息，在其競爭半徑內的節點將不再參與競爭，進入休眠狀態直到競爭結束。否則繼續競爭。

本文的算法借鑒了EEUC算法中競爭半徑的計算方法，節點的競爭半徑公式如下：

本文算法在簇頭競爭階段采用定時廣播代替了協商機制。傳統的算法如EEUC在簇頭競爭過程中節點的剩余能量大于所有的候選簇頭時競選才成功，并且要廣播通知信息和接收其他候選簇頭的放棄競爭的廣播信息。如果節點密度較大時每個候選簇頭都要接收和廣播大量信息，浪費很多能量。若采用定時驅動機制在一定程度上減少算法的迭代次數和信息交互帶來的能量消耗。本文定時公式如下：

其中，是均勻分布在之間的隨機數，用于減小廣播消息時間沖突的可能性；為設定的簇頭最大競爭時間；為節點的節點度；是網絡中布撒的節點個數；是節點與基站之間的距離；是網絡中節點到基站的最大距離。由式(7)可知，節點度越高，距離基站的距離越小，生成的定時時間就越短，成為最終簇的概率就越大。簇的形成流程見圖2。在成簇時，節點根據接收到簇首的信號強度選擇信號強度最大的加入，若節點接收的簇頭的信號強度相同，選擇簇頭節點度低的簇頭加入。成簇結束后簇頭節點為每個簇成員分配一個TMDA時隙，簇內節點根據分配的時隙與各自的簇頭進行通信。

3.2 簇間路由的建立

UCDD算法采用了簇內單跳和簇間多跳的方式進行數據的傳輸。簇頭節點只是在其鄰居簇首集合中選擇一個合適的簇頭中繼來轉發數據到基站。和PEGASIS算法[13]不同，UCDD算法中的中繼簇頭只是簡單的轉發并不融合轉發的數據。

定義3轉發熱度就是利用該簇頭作為中繼節點的所有子簇頭的個數，簇頭初始轉發熱度為0。

在建立簇間路由時，每個簇首節點以3倍[10]于自身競爭半徑進行廣播簇間通信信息。并且路由的發起從最遠端發起，簇頭節點根據距離基站的距離依次建立路由。簇頭節點廣播信息包括簇頭的ID、簇首與基站之間的距離、簇頭剩余能量，簇首節點通過接收的簇頭廣播信息計算相互間的距離。簇頭節點根據收到的廣播信息，建立鄰居簇首集合。鄰居簇頭集合分為子節點集合和父節點集合。

3.3 簇頭的輪換機制

(14)

由式(11)可知，在進行簇頭輪換時利用節點的剩余能量和距離簇質心的距離來選擇下一任簇頭，使得越靠近質心能量越高的節點當選簇頭權值就越大。當簇頭靠近質心時，簇內節點在傳輸數據時簇內消耗的能量就越少，降低了簇內能量消耗，在一定程度上延長了網絡的生命。簇頭輪換流程如圖3所示。

圖3 簇頭輪換流程

4 仿真與結果分析

4.1 仿真參數的設定

本文采用Matlb軟件對提出的算法進行了驗證，并在相同的條件下與LEACH協議和EEUC協議進行了對比分析。相關參數設置如表2所示。

表2 網絡環境的參數設定

4.2 簇頭的特性

在分層的路由協議中，成簇時的簇頭個數對網絡的性能將產生很大的影響。一個好的分簇路由協議，當網絡的參數一定時，產生的簇頭個數應該在一定的期望范圍內。本文對UCDD算法和LEACH協議都進行了100次的仿真并統計了簇頭的分布情況，如圖4、圖5所示。從圖4可以看出，LEACH協議產生的簇頭個數范圍波動比較大，其主要的原因是LEACH協議采用了等概率選擇簇頭的模型，通過隨機數和閾值來決定該節點是否當選為簇頭節點。而UCDD協議產生的簇頭個數相對集中在一定的范圍之內，產生的簇頭相對比較穩定。主要原因是在簇頭選舉的時采用了節點度和局部競爭相結合的方式，在一定程度上控制了產生的簇頭數量。從整體上來看，UCDD算法產生的簇頭個數相對穩定，可靠性較好。

圖4 LEACH算法簇頭數量分布

圖5 UCDD算法簇頭數量分布

在分簇的路由協議中，由于簇頭的特殊位置，簇頭消耗的能量占據了網絡能耗的主要部分，因此本文對比了 3種協議簇首在一輪中所消耗的總能量。本文隨機選取了10輪，統計了每輪中所有簇頭消耗的能量，如圖6所示。本文UCDD算法和EEUC算法消耗的能量較小，主要的原因是在進行數據傳輸時采用了多跳通信的方式，節約了能量消耗。而LEACH協議每輪簇首消耗的能量明顯多于UCDD算法和EEUC算法，不僅因為LEACH協議是在進行數據傳輸時采用了單跳進行傳輸，還有LEACH協議產生的簇頭個數也比較多，增加了與基站通信的次數，從而增加了能量消耗。另外，LEACH協議在進行簇頭選舉時沒有控制簇頭在網絡中的分布，而且簇頭的數量也不確定，因此每輪簇首消耗的能量之和有較大的波動。UCDD協議在一定程度上克服了LEACH協議的不足，降低了網絡的能量消耗。

圖6 簇頭的每輪能耗之和

4.3 能量效率

對網絡的能量效率的證明中，網絡的生命周期是一個重要指標。本文首先對比了3種協議的網絡生命周期。然而，網絡的生命周期目前也沒有統一的定論，有的以第一個節點死亡的時間作為網絡的生命周期(FND)，有的以一半節點死亡的時間作為網絡生命周期(HND)，還有以最后一個節點死亡作為網絡生命周期的(LND)[14]。

從圖7和圖8可以看出，3種協議中網絡存活節點個數隨著仿真時間的變化逐步減少。顯然，首個節點死亡的時間、半數節點死亡的時間、最后一個節點死亡的時間，UCDD協議均優于EEUC協議。只有最后一個節點死亡的時間UCDD協議略微低于LEACH協議。從第一個節點開始死亡到最后一個節點死亡的時間可以反映出網絡中節點的能量均衡情況，跨度越短說明網絡的能量使用越高效。UCDD協議不僅在一定程度上延長網絡的生命周期，而且時間跨度也遠小于LEACH協議，略小于EEUC協議。說明UCDD協議很好地均衡了網絡中所有節點的能量消耗。LEACH協議在進行簇頭選擇時采用了等概率模型，沒有考慮節點的剩余能量，并且在數據傳輸時采用了單跳模式，所以第一個節點死亡較早。EEUC協議雖然考慮了節點的剩余能量，但是在進行簇頭選擇時采用部分節點競爭機制，由于每輪都要進行簇頭的選舉消耗了部分能量，并且在進行數據傳輸時只考慮了下一跳節點的剩余能量和距離，這樣會出現多個節點選擇一個簇首作為中繼的現象，會造成能耗均衡性降低。如果以第一個節點死亡的時間進行對比，LEACH協議出現首個節點死亡的輪數是268輪，EEUC協議出現的首個節點死亡的輪數是766輪，而UCDD協議是873輪。

本文提出的協議在生命周期方面比LEACH協議提高了2倍多，比EEUC協議提高了13.97%。

圖7 節點存活個數與輪數之間的關系

圖8 網絡的存活時間

圖9對比了網絡的整體能耗變化的趨勢，曲線的坡度越小代表著較慢的能耗速度和較長的網絡生命周期。從圖中可以看出，UCDD協議的坡度要小于EEUC協議和LEACH協議。當網絡都運行到500輪時，LEACH協議消耗了161.12 J，而EEUC協議消耗了119.15 J，而UCDD算法只消耗了108.9 J，比LEACH協議提高32.4%，比EEUC提高8.6%。

圖9 網絡的總能耗與輪數之間的關系

5 結束語

本文在對現有路由協議研究的基礎上，針對周期性成簇、周期性選舉簇頭和利用代價函數，建立路由時容易出現多個節點同時選擇一個節點作為中繼的問題，從簇頭選舉、簇頭的動態輪換和簇間路由的建立3個方面進行了改進，UCDD算法不僅充分利用了節點的能量，而且緩解了“熱區”對網絡的影響。仿真實驗表明，該算法能更好地均衡網絡的能量消耗，有效延長網絡的生命周期。下一步將以網絡編碼為基礎對節點發送的數據進行編碼，以此減少數據的發送量，降低節點的能耗。

[1] 景 博, 張 劼, 孫 勇. 智能網絡傳感器與無線傳感器網絡[M]. 北京: 國防工業出版社, 2011.

[2] Heinzelman W, Chandrakasan A, Balakrishnan H. Energy- Efficient Communication Protocol for Wireless Microsensor Networks[C]//Proc. of the 33rd Hawaii International Conference on System Sciences. Cambridge, USA: IEEE Press, 2000: 8020-8030.

[3] 沈 波, 張世永, 鐘亦平. 無線傳感器網絡分簇路由協 議[J]. 軟件學報, 2006, 17(7): 1588-1600.

[4] Younis O, Fahmy S. HEED: A Hybrid Energy-efficient Distri- buted Clustering Approach for Ad-hoc Sensor Networks[J]. IEEE Transactions on Mobile Computing, 2004, 3(4): 366- 379.

[5] Lin C H R, Gerla M. A Distributed Architecture for Multi-

media in Dynamic Wireless Networks[C]//Proc. of IEEE GLOBECOM’95. Los Angeles, USA: [s. n.], 1995: 1468- 1472.

[6] Heinzelman W R, Chandrakasan A P, Balakrishnan H. An Application-specific Protocol Architectures for Wireless Microsensor Networks[J]. IEEE Transactions on Wireless Communications, 2002, 1(4): 660-669.

[7] 李成法, 陳貴海. 一種基于非均勻分簇的無線傳感器網絡路由協議[J]. 計算機學報, 2007, 30(1): 28-36.

[8] 劉星成, 袁東升. 基于代價函數的WSN能效路由協議性能分析[J]. 軟件學報, 2011, 32(6): 133-140.

[9] 江海峰, 錢建生. WSN中基于能量代價的能量優化路由算法[J]. 計算機科學, 2012, 39(1): 73-76.

[10] 蔣暢江, 石為人. 能量均衡的無線傳感器網絡非均勻分簇路由協議[J]. 軟件學報, 2012, 23(5): 1222-1232.

[11] 尹 安, 汪秉文. MintRoute-HNLB: 一種支持負載均衡的無線傳感器網絡路由協議[J]. 計算機科學, 2010, 37(5): 77-80.

[12] 李成岳, 申鉉京. 無線傳感器網絡中LEACH路由算法的研究與改進[J]. 傳感技術學報, 2010, 23(8): 1164-1167.

[13] Lindsey S, Raghavendra C S. PEGASIS: Power-efficient Gather in Sensor Information Systems[C]//Proc. of IEEE Aerospace Conferwnce. [S. 1.]: IEEE Press, 2002: 1125-1130.

[14] 胡 平.基于節能的無線傳感器網絡分簇路由協議研究[D]. 南京: 南京理工大學, 2009.

編輯 索書志

Clustering Routing Algorithm Based on Node Degree and Distance for Wireless Sensor Networks

LI Hui, LIU Shu-ji

(School of Electrical Engineering and Automation, Henan Polytechnic University, Jiaozuo 454000, China)

Aiming at the problem of unnecessary energy consumption caused by periodic clustering and the load balance problem in the Wireless Sensor Networks(WSN), an Unequal Clustering routing algorithm based on node Degree and Distance for WSN(UCDD) is proposed. UCDD algorithm adopts the time competitive mechanism in the first round of clustering. The length of time depends on the nodes’ node degree and the distance from the base station, and different clusters are formed according to the different radius of competition. After the first round, the clusters’ structure does not change any more. Cluster head dynamically choose next cluster head according to the residual energy and the communication costs. Inter-cluster multihop routing is used in UCDD algorithm, and the relay node is selected according to node residual energy, distance from the base station, communication cost of nodes and relay hot. Simulation results show that the algorithm can prolong the networks lifetime by more than two times compared with LEACH protocol and by 13.97% compared with EEUC protocol. Besides, it balances the energy dissipation of the networks.

Wireless Sensor Networks(WSN); unequal clustering; node degree; distance; relay heat; dynamic rotation

1000-3428(2014)03-0113-07

A

TP391

李 輝(1976－)，男，副教授，主研方向：無線傳感器網絡；劉書吉，碩士研究生。

2013-03-04

2013-04-18 E-mail：li20042007@163.com

10.3969/j.issn.1000-3428.2014.03.023