張 品，王佳佳，占 夢

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

能量高效的無線傳感器網(wǎng)絡(luò)非均勻分簇路由算法*

張 品*，王佳佳，占 夢

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

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

無線傳感器網(wǎng)絡(luò)；非均勻分簇；能量高效；節(jié)點休眠；路由算法

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

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

式中：P為節(jié)點成為簇頭節(jié)點的百分?jǐn)?shù)，r為當(dāng)前輪數(shù)，G為在最近的1/P輪中未當(dāng)選簇頭的節(jié)點集合。雖然LEACH算法通過循環(huán)的方式隨機選擇簇頭，在一定程度上平衡了網(wǎng)絡(luò)的負(fù)載，提高了網(wǎng)絡(luò)生存時間，但仍然存在簇頭選舉不合理，能耗不均，選擇單跳路由等缺陷。

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

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

1 網(wǎng)絡(luò)模型和能量模型

1.1 網(wǎng)絡(luò)模型

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

1.2 能量模型

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

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

節(jié)點接收k比特數(shù)據(jù)的能耗為：

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

式中：EDA表示融合系數(shù)。

2 算法概述

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

2.1 概念描述

對本文中涉及到的參數(shù)說明如下：

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

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

式中：||A||表示監(jiān)視區(qū)域的面積，n表示監(jiān)視區(qū)域內(nèi)傳感器節(jié)點的數(shù)量。

②鄰居節(jié)點 節(jié)點Si和節(jié)點Sj互為鄰居節(jié)點滿足：

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

表1 節(jié)點的鄰居表信息

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

④節(jié)點平均剩余能量Eavg

式中：Nneig為節(jié)點Si的鄰居節(jié)點的數(shù)量。

⑤網(wǎng)絡(luò)節(jié)點覆蓋度Ccover

式中：ndeath為網(wǎng)絡(luò)內(nèi)能量耗盡的節(jié)點數(shù)量，nsleep是當(dāng)前網(wǎng)絡(luò)中處于休眠狀態(tài)的節(jié)點數(shù)量。

2.2 改進后的算法

2.2.1“熱區(qū)”內(nèi)傳送節(jié)點的選舉

首先基站向網(wǎng)絡(luò)內(nèi)所有節(jié)點廣播選舉簇頭的消息Elec_CluHea_SIG，所有的節(jié)點接收到消息后，根據(jù)接收到消息的信號強度計算節(jié)點與基站的距離di,BS，在熱區(qū)內(nèi)選擇符合條件的傳送節(jié)點，負(fù)責(zé)轉(zhuǎn)發(fā)距離基站較遠(yuǎn)的簇頭發(fā)來的數(shù)據(jù)，以減少距離基站較近的簇頭的能耗。

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

熱區(qū)范圍內(nèi)所有節(jié)點不再參與非熱區(qū)區(qū)域的簇頭選舉及簇的劃分，這樣可以避免數(shù)據(jù)重復(fù)發(fā)送，減少能量的損耗。

2.2.2 非“熱區(qū)”中簇頭的選擇：

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

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

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

2.2.3 節(jié)點入簇：

正常情況下，接收到簇頭的信號越強，距離該簇頭就越近，信息傳輸?shù)哪芎木驮降?；接收到簇頭的信號越弱，距離該簇頭就越遠(yuǎn)，信息傳輸?shù)哪芎木驮礁??？紤]到能量消耗的問題，非熱區(qū)的簇頭在廣播消息CluHea_SIG時，若普通節(jié)點收到多個簇頭的消息時，根據(jù)收到的信息的強度，普通節(jié)點加入接收到信號更強的簇頭的簇中。節(jié)點依據(jù)簇頭發(fā)出的信號的強度加入到相應(yīng)的簇中，能最大限度的節(jié)省能量的消耗，延長了網(wǎng)絡(luò)的使用壽命。

節(jié)點確定了加入的對應(yīng)簇之后，向?qū)?yīng)的簇頭發(fā)送入簇的消息JOIN_CLU_SIG，此消息包含節(jié)點的ID和節(jié)點的剩余能量Ei及節(jié)點的狀態(tài)Route_flag。

2.2.4 節(jié)點的休眠

節(jié)點入簇后，考慮到無線傳感器網(wǎng)絡(luò)中節(jié)點感知的數(shù)據(jù)與其所在地理位置關(guān)系密切，在相近的位置收集到的數(shù)據(jù)具有相似性。利用信息的相似性，選出簇內(nèi)的相似節(jié)點，并對相似節(jié)點進行休眠操作。

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

2.2.4 簇首的輪換

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

2.2.5 簇間路由

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

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

3 仿真及結(jié)果分析

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

圖1 網(wǎng)絡(luò)節(jié)點分布圖

表2 實驗仿真參數(shù)

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

圖2 500輪時的簇頭和傳送節(jié)點分布圖

圖3 950輪時的簇頭和傳送節(jié)點分布圖

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

圖4 網(wǎng)絡(luò)存活節(jié)點數(shù)與生命周期的關(guān)系

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

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

圖5 網(wǎng)絡(luò)節(jié)點消耗的總能量與生命周期的關(guān)系

圖6 節(jié)點死亡率對比圖

4 結(jié)束語

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

［1］陳志，駱平，岳文靜，等.一種能量感知的無線傳感網(wǎng)拓?fù)淇刂扑惴ǎ跩］.傳感技術(shù)學(xué)報，2013，26（3）：382-387.

［2］孫利民，李建中，陳渝.無線傳感器網(wǎng)絡(luò)［M］.北京：清華大學(xué)出版社，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］.傳感技術(shù)學(xué)報，2013，26（1）：116-121．

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

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

［7］彭鐸，黎鎖平，楊喜娟.一種能量高效的無線傳感器網(wǎng)絡(luò)非均勻分簇路由協(xié)議［J］.傳感技術(shù)學(xué)報，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］李成法，陳貴海，葉懋，等.一種基于非均勻分簇的無線傳感器網(wǎng)絡(luò)路由協(xié)議［J］.計算機學(xué)報，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-），男，杭州電子科技大學(xué)通信工程學(xué)院副教授，1992年7月畢業(yè)于上海交通大學(xué)電子工程系，獲工學(xué)學(xué)士學(xué)位，2000年7月于西南交通大學(xué)應(yīng)用數(shù)學(xué)系獲理學(xué)碩士學(xué)位，2004年12月電子科技大學(xué)通信工程學(xué)院獲博士學(xué)位，主要研究方向為計算機網(wǎng)絡(luò)、無線網(wǎng)絡(luò)，zhangpin@hdu.edu.cn；

王佳佳（1990-），女，杭州電子科技大學(xué)通信工程學(xué)院，碩士研究生，主要研究方向無線傳感器網(wǎng)絡(luò)，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