能量高效的無線傳感器網絡非均勻分簇路由算法*

張 品，王佳佳，占 夢

（杭州電子科技大學通信工程學院，杭州310018）

能量高效的無線傳感器網絡非均勻分簇路由算法*

張 品*，王佳佳，占 夢

（杭州電子科技大學通信工程學院，杭州310018）

針對無線傳感器網絡能量有限的問題，提出了一種能量高效的非均勻分簇路由算法。算法中首先通過在“熱區”內選舉傳送節點，有效的解決了“熱區”內負載不均衡的問題；非“熱區”內的節點根據節點的剩余能量選舉簇頭，簇頭選舉結束后其余節點加入到距其最近的簇頭中；節點入簇后，基于相似數據的收集策略，尋找符合條件的相似節點，休眠其中部分冗余的節點；改進的算法中不再每輪結束后都重新選舉簇頭，減少了能量的浪費；最后在數據傳輸階段，采用改進的簇內單跳，簇間多跳的通信方式傳輸數據。仿真結果表明，本算法有效的降低了能量的消耗，改善了傳感器網絡的性能，提高了網絡的生存時間。

無線傳感器網絡；非均勻分簇；能量高效；節點休眠；路由算法

無線傳感器網絡是有大量有監控功能的傳感器節點組成，作為一個動態的自組織，自管理，多跳的通信網絡［1-2］，傳感器網絡被應用于眾多場合中。但是傳感器節點一般只有電池提供能量，且節點部署環境復雜，所以網絡中的節點的能量資源，計算能力，通信帶寬，存儲能量都非常有限。在網絡層，設計有效的路由協議來提高網絡的連接性，降低能量的損耗，延長網絡的生命周期成為核心的問題之一。

LEACH算法［3-6］是無線傳感器網中典型的路由協議，LEACH算法定義了“輪”的概念，每一輪包括簇的建立階段和數據傳輸階段，在簇的建立階段，各個節點隨機生成0～1之間的隨機數，隨機數與閾值T(n)相比較，如果小于該閾值，則此節點就成為簇頭。T(n)的計算公式如下：

式中：P為節點成為簇頭節點的百分數，r為當前輪數，G為在最近的1/P輪中未當選簇頭的節點集合。雖然LEACH算法通過循環的方式隨機選擇簇頭，在一定程度上平衡了網絡的負載，提高了網絡生存時間，但仍然存在簇頭選舉不合理，能耗不均，選擇單跳路由等缺陷。

目前，針對LEACH的缺陷，提出了很多的改進算法。文獻［4］中基于粒子群改進的LEACH-PSOC算法將整個網絡區域劃分成若干個相同規模的簇，使簇頭均勻分布，減少了能量的消耗，但增加了網絡的延遲。文獻［5］中的算法優點是根據能量選舉簇頭并提出選舉中繼節點傳輸數據，有效的解決了“熱區”內負載不均衡的問題，缺點是簇間路由的選擇優化效果不理想。文獻［6］中構造了基于最小生成樹的最優傳輸路徑，優化了數據傳輸路徑，但對網絡進行了消息遍歷，造成了能量的消耗。文獻［7］中的EUCP協議采用參數可調的休眠/喚醒機制，最大限度的節約網絡能量。

本文借鑒了上述改進算法的優點，提出了一種新的改進算法，算法中首先通過在“熱區”內選舉傳送節點，有效的解決了“熱區”內負載不均衡的問題；非“熱區”內的節點根據節點的剩余能量選舉簇頭，簇頭選舉結束后其余節點加入到距其最近的簇頭中；節點入簇后，基于相似數據的收集［8-10］策略，尋找符合條件的相似節點，休眠其中部分冗余的節點；改進的算法中不再每輪結束后都重新選舉簇頭，減少了能量的浪費；最后在數據傳輸階段，采用改進的簇內單跳，簇間多跳的通信方式傳輸數據。

1 網絡模型和能量模型

1.1 網絡模型

本文假設n個傳感器節點在M×M的正方形區域是隨機分布的，并且傳感器網絡具有以下屬性：①它是一個靜態的網絡，所有的節點部署后保持靜止且能量有限不可充電；②基站的位置部署后固定且能量不受限；③所有的傳感器節點能夠根據接收到的信號強度（RSSI）獲得自己距離發送者的距離；④節點的無線發射功率是可控的，例如節點可以根據到目標節點的距離調整其發射功率；⑤所有的節點有唯一的標示，用Si表示第i個節點，則節點的集合

1.2 能量模型

我們采用文獻［3］中的無線通信能耗模型。發射器發射傳輸距離為d的k比特能量所消耗的能量公式如下：

式中：Eelec為節點發送或者接收每比特數據所消耗的電路能耗，d0為恒定的門限距離值，εfs與εamp為兩種信道下功率放大時電路能耗系數。

節點接收k比特數據的能耗為：

簇頭j融合來自m個簇成員的k比特數據，簇頭j消耗能量：

式中：EDA表示融合系數。

2 算法概述

本算法主要分為簇的建立，節點的休眠和數據的傳輸3個階段，在簇的建立階段主要考慮了節點的剩余能量；在選擇節點休眠階段，考慮到節點感知的數據有空間關聯性和時間關聯性，所以選擇收集到相似數據節點中能量較低的節點；在數據的傳輸階段，考慮了選為中繼簇頭與自身節點的距離，中繼簇頭距離基站的距離以及節點剩余能量。

2.1 概念描述

對本文中涉及到的參數說明如下：

①競爭半徑 節點競爭簇頭時的半徑，本文改進了文獻［11］中的公式去計算競爭半徑。

式中：dmax和dmin分別表示節點距離基站的最大距離和最小距離；c是用于控制取值范圍的參數，在-1～1之間取值，di,BS表示節點距離基站的距離，ropt是最佳簇半徑。文獻［12］已經證明，最小化網絡能耗的最佳簇半徑計算如下：

式中：||A||表示監視區域的面積，n表示監視區域內傳感器節點的數量。

②鄰居節點 節點Si和節點Sj互為鄰居節點滿足：

③鄰居表 鄰居表中存有鄰居節點的基本信息，如表1所示。

表1 節點的鄰居表信息

表1中，Route_flag等于1時代表節點為簇頭，等于0是代表節點為普通節點。

④節點平均剩余能量Eavg

式中：Nneig為節點Si的鄰居節點的數量。

⑤網絡節點覆蓋度Ccover

式中：ndeath為網絡內能量耗盡的節點數量，nsleep是當前網絡中處于休眠狀態的節點數量。

2.2 改進后的算法

2.2.1“熱區”內傳送節點的選舉

首先基站向網絡內所有節點廣播選舉簇頭的消息Elec_CluHea_SIG，所有的節點接收到消息后，根據接收到消息的信號強度計算節點與基站的距離di,BS，在熱區內選擇符合條件的傳送節點，負責轉發距離基站較遠的簇頭發來的數據，以減少距離基站較近的簇頭的能耗。

熱區是以基站為圓心，在其半徑rh范圍內的子區域，在熱區范圍（di,BS≤rh）內，在傳送選舉節點的選舉過程中，節點的剩余能量Ei≥Eavg的節點成為熱區內的傳送節點，并設置Route_flag=1。傳送節點既要發送收集到的數據，又要承擔轉發來自距離基站較遠的簇頭的數據。熱區內節點的鄰居表中有所有在熱區內的節點的信息。熱區內所有節點通過單跳的通信方式與基站進行數據的傳輸。

熱區范圍內所有節點不再參與非熱區區域的簇頭選舉及簇的劃分，這樣可以避免數據重復發送，減少能量的損耗。

2.2.2 非“熱區”中簇頭的選擇：

非熱區區域選擇簇頭的選舉方式類似于LEACH算法，但本算法考慮了節點的剩余能量，調整后的簇頭閾值計算方法如下：

式中：E0是節點的初始能量值，Ei是節點的剩余能量。

簇頭選舉結束后，簇頭在競爭半徑Ri范圍內向節點廣播自己成為簇頭的消息CluHea_SIG，消息包含節點的ID和節點的剩余能量Ei及節點的狀態Route_flag，簇頭也會收集周圍簇頭的信息保存到鄰居表中，為以后的路由做準備。

2.2.3 節點入簇：

正常情況下，接收到簇頭的信號越強，距離該簇頭就越近，信息傳輸的能耗就越低；接收到簇頭的信號越弱，距離該簇頭就越遠，信息傳輸的能耗就越高。考慮到能量消耗的問題，非熱區的簇頭在廣播消息CluHea_SIG時，若普通節點收到多個簇頭的消息時，根據收到的信息的強度，普通節點加入接收到信號更強的簇頭的簇中。節點依據簇頭發出的信號的強度加入到相應的簇中，能最大限度的節省能量的消耗，延長了網絡的使用壽命。

節點確定了加入的對應簇之后，向對應的簇頭發送入簇的消息JOIN_CLU_SIG，此消息包含節點的ID和節點的剩余能量Ei及節點的狀態Route_flag。

2.2.4 節點的休眠

節點入簇后，考慮到無線傳感器網絡中節點感知的數據與其所在地理位置關系密切，在相近的位置收集到的數據具有相似性。利用信息的相似性，選出簇內的相似節點，并對相似節點進行休眠操作。

本文中，節點Si和節點Sj之間的數據差異度定義為D（Si，Sj，t）=|Vi（t）-Vj（t）|，Vi（t）是t時刻節點Si感知的數據。給出差值常量λ，若D(Si,Sj,t)≤λ，則節點Si和節點Sj為相似節點，相似的節點Si和節點Sj若都處于喚醒狀態，休眠其中剩余能量較低的節點。但相似節點不具有傳遞性，例如D(Si,Sj,t)≤λ，D(Sj,Sk,t)≤λ，D(Sk,Sj,t)＞λ，節點Sk和節點Sj不是相似節點。根據節點的相似性休眠節點，既保證了簇內節點信息的傳送，又減少了簇內能量的消耗，延長了網絡的壽命。

2.2.4 簇首的輪換

在LEACH算法中，為了均衡簇首的能量消耗，需要每一輪都重新選舉簇頭，但每一輪的重新選舉也會消耗簇頭大量能量，為了避免頻繁的選舉簇頭，在改進的算法中不再每輪都需要重新選舉簇頭，簇頭在循環L輪之后才重新選簇頭。在到達L輪之前，若簇頭死亡，則由簇內剩余能量最大的節點代理簇頭。這樣既使網絡數據傳輸不被中斷，保證了網絡良好的性能，又減少了簇頭輪換時網絡消耗的能量。

2.2.5 簇間路由

本算法采用簇內單跳，簇間多跳的通信方式進行數據的傳送。熱區內的節點采用單跳的方式向基站傳輸信息。非熱區的簇頭經過改進的多跳方式將信息傳送到基站。每個距離基站較遠的簇頭傳送數據到基站在多跳的過程中，需要選擇中繼的簇頭節點進行數據的傳送，在選擇合適的中繼的簇頭節點時，應該要考慮中繼簇頭的剩余能量Ej，自身節點距離中繼簇頭的距離和中繼簇頭距離基站的距離，節點通過計算權值wij綜合考慮以上因素，權值計算公式如下：

式中：dij是簇頭Si與簇頭Sj之間的距離值，dj,BS是簇頭Sj與基站之間的距離值，α和β是加權系數。簇頭選擇計算的權值wij最小的簇頭最為下一跳的中繼節點，從式中可以看出，選擇的下一跳的中繼簇頭距離簇頭節點越近，距離基站越近，且能量越高，權值wij就越小。所以選擇計算出權值wij最小的值作為下一跳的中繼簇頭既能節省能量的消耗又能均衡節點的負載。

3 仿真及結果分析

我們用MATLAB對LEACH，EEUC及本文的算法進行了仿真比較。實際應用環境中的節點很難做到均勻分布，所以本文中的節點隨機分布于監測區域中，圖1是網絡節點分布圖，仿真環境參數如表2所示。仿真從網絡的生存時間，能量的消耗，網絡死亡率三個方面進行了比較。根據文獻［13］，定義網絡的存活節點比例為70%，若超過30%的節點死亡則定義為網絡死亡，這樣使得本文的仿真更加的接近實際，增強了說服力。為了避免偶然性，對本文中的仿真數據進行了多次求平均得到仿真圖。

圖1 網絡節點分布圖

表2 實驗仿真參數

圖2和圖3中標明了本文算法在500輪和950輪時候的簇頭和傳送節點的分布情況，圖中簇頭分布均勻，有效的均衡了能量的消耗。

圖2 500輪時的簇頭和傳送節點分布圖

圖3 950輪時的簇頭和傳送節點分布圖

圖4是LEACH協議，EEUC協議與本文算法3種協議的網絡存活節點數與生命周期的關系圖。由圖4可以看出在網絡死亡時，本文算法的生命周期比LEACH協議和EEUC協議分別提高了640輪和224輪，而且本文算法的在809輪是第1個節點失效，比LEACH協議和EEUC協議分別提高了468輪和123輪。說明本文算法有效的延長了網絡的壽命，而且顯著提高了網絡的穩定性。

圖4 網絡存活節點數與生命周期的關系

圖5是消耗總能量為70%時三種算法運行輪數變化圖，圖中本文算法較其他兩種算法相比能耗的坡度更小，能量消耗更加均衡，更加有效的節省了能量的消耗。

圖6是3種算法在全網節點死亡率達到10%、20%及30%時網絡的工作時間的對比圖，本文算法改善了網絡的性能，良好的保證了無線網絡應有的規模，有效的降低了能耗，延長了網絡的壽命。

圖5 網絡節點消耗的總能量與生命周期的關系

圖6 節點死亡率對比圖

4 結束語

為了解決在大規模的無線傳感器網絡中節點消耗過快的問題，提出了一種能量高效的非均勻分簇的算法。算法中，在“熱區”內選舉傳送節點，利用節點收集相似數據休眠部分冗余節點，降低重新選簇的頻率，最后結合簇內單跳簇間多跳的通信方式，從各方面最大限度的節省能量的消耗。仿真結果表明算法有效的解決“熱區”內節點能耗過快的問題，均衡了簇間負載，延長了網絡的生存壽命。

［1］陳志，駱平，岳文靜，等.一種能量感知的無線傳感網拓撲控制算法［J］.傳感技術學報，2013，26（3）：382-387.

［2］孫利民，李建中，陳渝.無線傳感器網絡［M］.北京：清華大學出版社，2005：3-9.

［3］Heinzelman W，Chandrakasan A，Balakrishnam H.Energy-Efficient Communication Protocol for Wireless Microsensor Networks［C］//Proc of the 33rd Conf on System Sciences.Piscataway.NJ：IEEE.2000：3005-3014．

［4］陳曉娟，王卓，吳潔.一種基于LEACH的改進WSN路由算法［J］.傳感技術學報，2013，26（1）：116-121．

［5］李亞男，徐夫田，陳金鑫.基于LEACH的WSNs分簇優化策略［J］.傳感技術學報，2014，27（5）：670-674.

［6］張文梅，廖福寶.改進的無線傳感器網絡非均勻分簇路由算法［J］.傳感技術學報，2015，28（5）：739-743.

［7］彭鐸，黎鎖平，楊喜娟.一種能量高效的無線傳感器網絡非均勻分簇路由協議［J］.傳感技術學報，2014，27（12）：1687-1691.

［8］Pazand B，Datta A.An Energy-Efficient Node Scheduling Scheme for Wireless Sensor Networks Based on Minimum Dominating sets［J］.International Journal of Network Management，2009，19（2）：75-99．

［9］Yang H Y，Lin C H，Tsai M J.Distributed Algorithm for Efficient Construction and Maintenance of Connectedk-hop Dominating Sets in Mobile Ad Hoc Networks［J］.IEEE Transactions on Mobile Computing，2008，7（4）：444-457．

［10］Hung C C，Peng W C，Lee W C.Energy-Aware Set-Covering Approaches for Approximate Data Collection in Wireless Sensor Networks［J］.IEEE Transactions on Knowledge and Data Engineering，2012，24（11）：1993-2007．

［11］李成法，陳貴海，葉懋，等.一種基于非均勻分簇的無線傳感器網絡路由協議［J］.計算機學報，2007，30（1）：27-36．

［12］Lin M，Cao J N，Chen G H，et al.EADEEG：An Energy Aware Data Gathering Protocol for Wireless Sensor Networks［J］.Journal of Software，2007，18（5）：1092-1109.

［13］Parikh S，Vokkarane V，Xing L，et al Node-Replacement Policies to Maintain Threshold-Coverage in Wireless Sensor Networks［C］//Proceedings of the 16th International Conference Computer Communication Networks，Honolulu，HI，2007：760-765.

張 品（1971-），男，杭州電子科技大學通信工程學院副教授，1992年7月畢業于上海交通大學電子工程系，獲工學學士學位，2000年7月于西南交通大學應用數學系獲理學碩士學位，2004年12月電子科技大學通信工程學院獲博士學位，主要研究方向為計算機網絡、無線網絡，zhangpin@hdu.edu.cn；

王佳佳（1990-），女，杭州電子科技大學通信工程學院，碩士研究生，主要研究方向無線傳感器網絡，wangjiaqqw@163.com。

An Energy Efficient Uneven Clustering Routing Algorithm for Wireless Sensor Networks*

ZHANG Pin*，WANG Jiajia，ZHAN Meng
（Department of Communication Engineering，Hangzhou Dianzi University，Hangzhou310018，China）

For limited energy in wireless sensor network，this paper proposed a model based on Energy Efficient Uneven Routing Algorithm.This method effectively solves the load balancing problem by selecting the transfer nodes in the“hot zone”.In the clustered formation stage，this algorithm selects among all the nodes some specific cluster heads based on the residual energy of node；the remaining nodes that cannot be cluster heads are selected to join the cluster nearest in order to complete the process of clustering and the network is divided into clusters with different size.Then，the sensor nodes with the same readings can be clustered such that only the representative nodes report their readings.Meanwhile，decreasing the frequency of clustering reduce the energy consumption.Finally，in the data transfer stage，the ordinary nodes send the data through a single-hop routing while the cluster heads send through a multi-hop routing.Our simulation results show that this algorithm is efficient to reduce energy consumption and improve the performance and lifetime of the wireless sensor network.

wireless sensor network；uneven clustering；energy efficient；node sleeping；routing algorithm

TP393

A

1004-1699（2016）12-1919-05

??7230

10.3969/j.issn.1004-1699.2016.12.023

項目來源：錢江人才計劃項目（2013R10071）

2016-04-24修改日期：2016-09-20