一種能量高效的分布式非均勻分簇路由算法*

孫彥景，林昌林，江海峰

(1.中國礦業(yè)大學(xué)信息與電氣工程學(xué)院，江蘇徐州221116；2.江蘇省煤礦電氣與自動化工程實(shí)驗(yàn)室，江蘇徐州221008；3.中國礦業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，江蘇徐州221116)

一種能量高效的分布式非均勻分簇路由算法*

孫彥景1，2*，林昌林1，江海峰3

(1.中國礦業(yè)大學(xué)信息與電氣工程學(xué)院，江蘇徐州221116；2.江蘇省煤礦電氣與自動化工程實(shí)驗(yàn)室，江蘇徐州221008；3.中國礦業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，江蘇徐州221116)

針對分布式分簇路由多跳通信方式中出現(xiàn)的“熱區(qū)”問題，在現(xiàn)有的分布式分簇路由協(xié)議的基礎(chǔ)上改進(jìn)，并提出了能量均衡前行路由算法（EBFA）。該算法采用非均勻分簇和簇間多跳轉(zhuǎn)發(fā)策略，在多跳轉(zhuǎn)發(fā)階段，引入社會福利函數(shù)預(yù)先評估數(shù)據(jù)轉(zhuǎn)發(fā)路徑上節(jié)點(diǎn)間的能量均衡程度，選擇能量均衡程度較好的作為轉(zhuǎn)發(fā)節(jié)點(diǎn)。仿真結(jié)果表明：相比于LEACH和EEUC，此算法最大程度上延長了網(wǎng)絡(luò)的生存周期，較好地均衡了節(jié)點(diǎn)間的能量，解決了多跳路由中熱區(qū)的問題。

WSNs；非均勻分簇；社會福利函數(shù)；多跳轉(zhuǎn)發(fā)

無線傳感器網(wǎng)絡(luò)(Wireless Sensor Networks，WSNs)分簇路由協(xié)議按照控制方式可分為集中式路由協(xié)議［1-3］和分布式路由協(xié)議［4-10］。相比于集中式算法，分布式分簇路由協(xié)議只需獲得網(wǎng)絡(luò)的局部信息，并且具有良好的拓展性，適合大規(guī)模的WSNs網(wǎng)絡(luò)。在以分簇方式自組織的WSNs網(wǎng)絡(luò)中，節(jié)點(diǎn)被分為簇頭和簇成員，簇頭作為簇的中心負(fù)責(zé)簇的的構(gòu)建，收集和融合簇成員新數(shù)據(jù)并轉(zhuǎn)發(fā)給基站，這使得簇頭的能量消耗速度遠(yuǎn)遠(yuǎn)高于其他簇成員。為解決這一問題，LEACH［4］協(xié)議采用隨機(jī)分簇和周期性簇頭輪換策略，把簇頭的負(fù)載分散到網(wǎng)絡(luò)中；文獻(xiàn)［5］［6］在LEACH的基礎(chǔ)上改進(jìn)了分簇算法，將剩余能量、節(jié)點(diǎn)度等考慮在內(nèi)，克服了LEACH中簇頭產(chǎn)生的隨機(jī)性，保證了簇頭的質(zhì)量。上述協(xié)議中，簇頭與基站均采用單跳方式直接通信，遠(yuǎn)離基站的簇頭具有較大的能耗，易造成這些節(jié)點(diǎn)較早失效。然而，在簇頭與基站采用多跳方式通信的網(wǎng)絡(luò)中，距離基站較近的節(jié)點(diǎn)由于需要大量轉(zhuǎn)發(fā)其他簇頭的數(shù)據(jù)給基站，能耗較高，也容易較早失效，影響整個(gè)網(wǎng)絡(luò)的性能。

因此分簇路由中無論采用單跳或多跳方式轉(zhuǎn)發(fā)數(shù)據(jù)，簇首間能耗不均衡的問題仍然存在。針對這一問題，UCS［7］采用了非均勻分簇和簇間多跳的思想，在簇頭產(chǎn)生后首先構(gòu)造簇間多跳路由，根據(jù)期望轉(zhuǎn)發(fā)負(fù)荷，通過調(diào)整簇的大小的方式，減小簇頭間能耗的差距，解決能耗不均衡的問題；EEUC［8］則根據(jù)距基站的遠(yuǎn)近來調(diào)整簇的大小，距基站較近的簇具有較小的規(guī)模，從而節(jié)省能量用來轉(zhuǎn)發(fā)其他簇頭的數(shù)據(jù)。以上方法通常是在評估當(dāng)前網(wǎng)絡(luò)狀態(tài)后做出選擇，對于節(jié)點(diǎn)執(zhí)行后的網(wǎng)絡(luò)狀態(tài)沒有預(yù)先考慮。

因此，本文在EEUC非均勻分簇的基礎(chǔ)上，對簇頭的產(chǎn)生和多跳路徑的建立進(jìn)行了改進(jìn)，依據(jù)經(jīng)濟(jì)學(xué)領(lǐng)域度量收入分配不平等程度的社會福利函數(shù)預(yù)先評估下一跳中繼節(jié)點(diǎn)選擇后的網(wǎng)絡(luò)狀態(tài)，從而選擇下一跳簇頭節(jié)點(diǎn)，提出能量均衡前行算法(Energy Balanced Forwarding Algorithms，EBFA)，解決多跳通信方式中節(jié)點(diǎn)的能耗不均衡的問題，以延長WSNs網(wǎng)絡(luò)的生存時(shí)間。

1 網(wǎng)絡(luò)模型與假設(shè)

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

本文中路由協(xié)議的應(yīng)用場景為周期性數(shù)據(jù)收集，即在一個(gè)M×M二維正方形區(qū)域A的隨機(jī)部署N個(gè)傳感器節(jié)點(diǎn)，區(qū)域A中的傳感器節(jié)點(diǎn)定時(shí)地將采集到的數(shù)據(jù)（如溫度，濕度和氣壓等）匯聚到基站。假設(shè)該網(wǎng)絡(luò)有如下幾個(gè)特性：①基站（匯聚節(jié)點(diǎn)）位于一個(gè)正方形監(jiān)測區(qū)域A的外側(cè)，地理位置固定，計(jì)算能力較強(qiáng)，能量不受限制；②所有節(jié)點(diǎn)結(jié)構(gòu)相同，隨機(jī)分布在監(jiān)測區(qū)域內(nèi)，具備數(shù)據(jù)融合功能和唯一的標(biāo)識(ID)，并且能保證時(shí)間同步；③鏈路是對稱的。若已知對方發(fā)射功率，節(jié)點(diǎn)可以根據(jù)接收信號的強(qiáng)度計(jì)算出發(fā)送者到自己的近似距離；④節(jié)點(diǎn)可以根據(jù)與接收者的傳輸距離，自由調(diào)整其通訊功率，既能滿足通訊的需求，也可以節(jié)省節(jié)點(diǎn)的能量消耗。

1.2 無線通信能耗模型

本文采用與文獻(xiàn)［4］相同的無線通信能耗，在該模型中，發(fā)送端所消耗的能量用于無線電通信發(fā)送和功率放大兩部分，而接收端消耗的能量僅僅用于無線電通信接收。該模型如1圖所示。

圖1 無線通信模型

無線信號的能量衰減根據(jù)接收端和發(fā)送端的距離的不同，分別使用Friss自由空間模型(Friss Free Space Model)和多徑衰落信道模型(Multi-path Fading Channel Model)。若兩者間的距離小于d0使用自由空間模型，傳播能量損失與d2成反比；若距離大于d0則使用多徑衰落信道模型，傳播能量損失與d4成反比。為了保證接收方正常接收數(shù)據(jù)，發(fā)送方必須具有功率控制能力，以抵消無線信號在傳播過程中的能量損耗。因此，發(fā)一個(gè)l比特的數(shù)據(jù)包到距離發(fā)送端d的節(jié)點(diǎn)需要消耗的能量為：

而接收到這個(gè)數(shù)據(jù)包需要消耗的能量為：

本文考慮簇內(nèi)數(shù)據(jù)有較大冗余，可以數(shù)據(jù)融合，簇間轉(zhuǎn)發(fā)則不考慮數(shù)據(jù)融合。數(shù)據(jù)融合消耗的能量EDA為5 nJ·bit-1·signal-1，εfs為10 pJ·bit-1·m-2，εmp為0.001 3 pJ·bit-1·m-4），Eelec為50 nJ·bit-1，d0=87 m。

2 算法詳述

EBFA協(xié)議采用經(jīng)典的輪循機(jī)制，每一輪包括四個(gè)階段：簇頭競爭，簇間多跳路由路徑建立，簇的形成和穩(wěn)定階段。

2.1 簇首競爭算法

EBFA協(xié)議在簇頭競選階段采用計(jì)時(shí)廣播［9］代替EEUC的協(xié)商機(jī)制。為了控制候選簇頭的比例，網(wǎng)絡(luò)中的節(jié)點(diǎn)在每輪開始時(shí)以概率T選擇自己作為候選簇頭，其他節(jié)點(diǎn)則進(jìn)入休眠狀態(tài)直到被喚醒。候選簇頭Vi根據(jù)公式計(jì)算等待時(shí)間ti，等待時(shí)間ti到達(dá)則廣播FINAL_HEAD_MSG消息，宣布自己成為簇頭，在其競爭范圍內(nèi)的其他簇頭則退出競選。

式中：λ是在0.9～1.0之間的隨機(jī)數(shù)，用于避免廣播消息發(fā)生沖突；TCH是預(yù)先定義的簇頭競爭所需要的最大時(shí)間；Ei是Vi的剩余能量；E0是Vi節(jié)點(diǎn)的初始能量。根據(jù)上述公式，廣播時(shí)間ti很大程度上取決于節(jié)點(diǎn)的剩余能量。如果節(jié)點(diǎn)比其所處區(qū)域的其他節(jié)點(diǎn)具有較大的能量，則它成為簇頭的等待時(shí)間較短，概率較大。但是，當(dāng)網(wǎng)絡(luò)運(yùn)行了相當(dāng)一段時(shí)間之后，所有節(jié)點(diǎn)的剩余能量Ei變得非常低，等待時(shí)間ti則會變得相當(dāng)大。為此我們又改進(jìn)了ti的計(jì)算方法：

這樣，等待時(shí)間會在（0.5～1.0）TCH之間變化，盡可能地減少了網(wǎng)絡(luò)的延時(shí)。根據(jù)公式，在簇頭的競爭的競爭階段，只有少量候選簇頭廣播競選成功消息，這樣在簇頭競選階段候選簇頭之間的通信減少，可以有效減少簇頭的通信消耗。

簇頭選舉的偽代碼如下：

同時(shí)，每個(gè)候選簇頭設(shè)置一個(gè)競爭范圍Rcomp，它是該節(jié)點(diǎn)與基站距離的函數(shù)［8］，用于控制簇頭在網(wǎng)絡(luò)中的分布。假設(shè)是預(yù)先定義的最大競爭半徑，候選簇頭Vi的Rcomp為：

式中：dmax和dmin分別代表節(jié)點(diǎn)和基站的最大距離和最小距離，d(Vi，BS)代表Vi和基站的距離，c是位于0和1之間的常數(shù)。根據(jù)上述公式，候選簇頭的競爭范圍在(1-c)到之間變化，并且隨著候選簇頭到基站距離的減小，其競爭半徑應(yīng)該隨之減少。因此距離基站較近的區(qū)域選舉簇頭簇頭較多，簇的幾何尺寸也較小。較小的幾何尺寸是為了減少簇內(nèi)通信消耗，節(jié)省下來的能量則用于簇間轉(zhuǎn)發(fā)，避免過早死亡。

下圖給出了一張候選簇頭的競爭示意圖，其中圓圈表示候選簇頭的競爭區(qū)域。由公式可知，V1和V2不互為鄰居節(jié)點(diǎn)，V3位于V4的競爭范圍內(nèi)，而V4不位于V3的競爭范圍，所以V1和V2可以同時(shí)成為簇頭，當(dāng)V4首先成為簇頭后，V3則不能成為簇頭。

圖2 候選簇頭的競爭區(qū)域

2.2 簇間多跳路由協(xié)議

EBFA協(xié)議采用簇內(nèi)單跳和簇間多跳相結(jié)合的數(shù)據(jù)傳輸方式。每個(gè)成功競選的簇頭選擇其他簇頭作為中繼節(jié)點(diǎn)，轉(zhuǎn)發(fā)數(shù)據(jù)分組至基站，這就需要提前建立多跳傳輸路徑。我們假設(shè)數(shù)據(jù)冗余度有限，中繼節(jié)點(diǎn)無法融合其他簇頭和自身數(shù)據(jù)，只能簡單轉(zhuǎn)發(fā)來自其他簇頭的數(shù)據(jù)。

首先，競選成功的簇頭CHi(i=1，2，3，4，...，K，K為簇頭數(shù)量)，已經(jīng)廣播一條FINAL_HEAD_MSG消息，廣播功率覆蓋xi,yi倍簇頭競爭半徑范圍內(nèi)的節(jié)點(diǎn)。這條消息包括簇頭ID，剩余能量Ei，競爭半徑Rcomp和到基站距離dtoBS等。簇頭CHi接收到簇頭CHj信息后，計(jì)算CHi到CHj的大概距離，建立一個(gè)候選中繼節(jié)點(diǎn)信息表，如表1所示：在多跳路由建立過程中，簇首CHi的中繼候選節(jié)點(diǎn)集合N(i)為：

式中：k∈［1，3］，k取值越大，中繼候選節(jié)點(diǎn)集合中節(jié)點(diǎn)越多。簇頭CHi運(yùn)用貪婪算法在其候選中繼集合中，選擇其中中繼節(jié)點(diǎn)N(i)，中繼節(jié)點(diǎn)N(i)在所有候選節(jié)點(diǎn)中具有最小的代價(jià)函數(shù)。

代價(jià)函數(shù)參考阿特金森福利函數(shù)設(shè)計(jì)［11］。社會福利函數(shù)是經(jīng)濟(jì)學(xué)領(lǐng)域度量收入分配不平等程度的一種方法，社會收入差距越小，阿特金森指數(shù)值也就越小。阿特金森指數(shù)值的取值范圍為［0，1］，其中0代表了社會達(dá)到了收入的完全公平分配。代價(jià)函數(shù)如下：

EUB描述了節(jié)點(diǎn)在單跳通信可達(dá)區(qū)域范圍H內(nèi)的能量平衡狀態(tài)，其中n是區(qū)域內(nèi)的節(jié)點(diǎn)的個(gè)數(shù)，E(i)表示節(jié)點(diǎn)的剩余能量，Eˉ表示區(qū)域內(nèi)所有節(jié)點(diǎn)的平均剩余能量。nj≥2,j=1,2,3,4是不平等厭惡指數(shù)，在0到正無窮取值，常用的取值為1.5、2.0、2.5。

在選擇中繼節(jié)點(diǎn)時(shí)，簇頭CHi運(yùn)用貪婪算法在其候選簇頭節(jié)點(diǎn)中，計(jì)算將數(shù)據(jù)傳給其中一個(gè)候選中繼節(jié)點(diǎn)的EUB的預(yù)測值，最終代價(jià)函數(shù)值最小的一個(gè)候選中繼節(jié)點(diǎn)將作為中繼節(jié)點(diǎn)。詳述其過程：我們假定將候選中繼節(jié)點(diǎn)k作為下一跳的中繼節(jié)點(diǎn)，并假設(shè)將數(shù)據(jù)分組傳給候選中繼節(jié)點(diǎn)k，我們能計(jì)算出候選中繼節(jié)點(diǎn)k預(yù)期中的剩余能量為：

候選中繼節(jié)點(diǎn)k接收到數(shù)據(jù)分組后，還要將數(shù)據(jù)分組傳送給基站，則它預(yù)期中的剩余能量為：

而其他的候選中繼節(jié)點(diǎn)則沒有消耗能量，它們的剩余能量為：

根據(jù)上述公式，估算作為當(dāng)前CHi節(jié)點(diǎn)的候選中繼節(jié)點(diǎn)集合N(i)中每一個(gè)節(jié)點(diǎn)的EUBik，即阿特金斯福利指數(shù)：

其中

當(dāng)前節(jié)點(diǎn)CHi從中繼節(jié)點(diǎn)集合N(i)中選擇阿特金斯福利指數(shù)EUBik最小的節(jié)點(diǎn)作為下一跳節(jié)點(diǎn)。

下面對此代價(jià)函數(shù)做幾點(diǎn)說明：

①單跳通信可達(dá)區(qū)域范圍H即可與簇頭通信的候選中繼節(jié)點(diǎn)集合，候選中繼節(jié)點(diǎn)到基站都比簇頭到基站的距離小，最終的中繼節(jié)點(diǎn)都是從候選中繼節(jié)點(diǎn)選取出來的，所以每一跳數(shù)據(jù)分組都是向基站方向單向流動。不可能出現(xiàn)為了消除區(qū)域內(nèi)的能量不平衡狀態(tài)，數(shù)據(jù)分組在一個(gè)回路上反復(fù)轉(zhuǎn)發(fā)；②多跳路由的最終目的是將數(shù)據(jù)轉(zhuǎn)發(fā)到基站，供用戶使用。有兩種情況簇頭會將數(shù)據(jù)發(fā)送給基站，完成多跳路由的建立：一是簇頭距離基站較近，候選中繼節(jié)點(diǎn)為空；二是假若基站在簇頭可通信范圍(本文中簇頭的可通信范文半徑為)內(nèi)，預(yù)先評估將數(shù)據(jù)分組直接發(fā)送給基站的EUB值，若其代價(jià)函數(shù)最小則簇頭發(fā)送給基站。

2.3 分簇算法

簇間的多跳路徑建立完成后，簇頭廣播公告消息，普通節(jié)點(diǎn)從休眠狀態(tài)被喚醒，進(jìn)入分群階段。公告消息是控制信息短消息，包含發(fā)送節(jié)點(diǎn)的ID，剩余能量（簇間轉(zhuǎn)發(fā)后的預(yù)期值）和到基站距離等，消息的廣播半徑是簇頭競爭半徑的δ倍，其中δ∈［1，3］。每個(gè)普通節(jié)點(diǎn)按照以下方法確定自己本輪的簇頭：節(jié)點(diǎn)接收簇頭的廣播信息后，在競爭半徑覆蓋到自己的幾個(gè)簇頭中，選擇剩余能量較大的節(jié)點(diǎn)加入；若沒有簇頭覆蓋到自己，則主動廣播請求消息并加入首先回復(fù)確認(rèn)消息的簇頭。

2.4 穩(wěn)定階段

穩(wěn)定階段，非簇頭的無線通訊模塊關(guān)閉，直到分配的傳輸數(shù)據(jù)時(shí)間到來，這樣可以節(jié)約節(jié)點(diǎn)能量。簇首完成所有節(jié)點(diǎn)數(shù)據(jù)收集后，進(jìn)行數(shù)據(jù)融合，然后經(jīng)由簇間多跳路由傳送數(shù)據(jù)至基站。

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

為了驗(yàn)證EBFA協(xié)議的性能，利用MATLAB在相同條件下仿真LEACH、EEUC和EBFA協(xié)議并對比多項(xiàng)性能。仿真參數(shù)如表1所示，其中網(wǎng)絡(luò)參數(shù)取自文獻(xiàn)［8］，協(xié)議中的參數(shù)通過運(yùn)行多次實(shí)驗(yàn)來找出其最優(yōu)值。

表1 網(wǎng)絡(luò)環(huán)境與參數(shù)

3.1 簇頭數(shù)量

在網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)相對穩(wěn)定的情況下，一個(gè)優(yōu)秀的分簇算法每輪選出的簇頭數(shù)量應(yīng)該比較穩(wěn)定，集中于簇頭數(shù)量最優(yōu)值的附近，以優(yōu)化網(wǎng)絡(luò)的結(jié)構(gòu)。在沒有任何節(jié)點(diǎn)死亡的情況下，圖3比較了LEACH、EEUC和EBFA路由協(xié)議算法隨機(jī)選取的100輪種的簇頭數(shù)量的分布情況。

圖3 簇頭的數(shù)量分布統(tǒng)計(jì)

由圖3可見，LEACH的簇頭數(shù)量波動范圍較大，而EEUC和EBFA的波動范圍較小，其中EBFA產(chǎn)生的簇頭成正態(tài)分布更為穩(wěn)定。這樣的結(jié)果與算法的簇頭選舉算法密切相關(guān)，LEACH的簇頭選舉采用隨機(jī)數(shù)和閥值的控制機(jī)制，難以控制每輪生成的簇頭數(shù)量，而EEUC和EBFA采用了候選簇頭局部競爭的方法，所生成的簇頭的數(shù)量得到很好的控制，并使之分布于簇頭最優(yōu)數(shù)量作于很小的鄰域內(nèi)。相比EEUC，EBFA采用計(jì)時(shí)廣播的方式代替了競爭協(xié)商，減少了用于控制信息的開銷；并且EBFA不再維護(hù)候選簇頭的鄰居候選節(jié)點(diǎn)，競選成功的簇頭只需要通知其競爭半徑范圍的其他候選推出競選。

3.2 網(wǎng)絡(luò)生命周期

本協(xié)議的思想之一就是利用非均勻分簇的思想來解決熱點(diǎn)問題，延長網(wǎng)絡(luò)的存存時(shí)間。下面首先通過網(wǎng)絡(luò)生存周期來驗(yàn)證3種協(xié)議的能量有效性。

圖4顯示了存活節(jié)點(diǎn)數(shù)隨著仿真周期的變化情況。從圖中可以看出，本協(xié)議相對于LEACH和EEUC明顯提高了網(wǎng)絡(luò)生存周期。由于采用了非均勻分簇和簇間多跳路由有機(jī)結(jié)合的方式，本協(xié)議有效地平衡了靠近基站的簇和遠(yuǎn)離基站的簇之間的數(shù)據(jù)傳輸能耗。LEACH的網(wǎng)絡(luò)生命周期與另外兩種協(xié)議相差很大這是因?yàn)長EACH只適合小型網(wǎng)絡(luò)不適合本文仿真的網(wǎng)絡(luò)環(huán)境。相比于EEUC，本協(xié)議采用計(jì)時(shí)廣播方式代替協(xié)商機(jī)制，有效減少了簇頭競爭階段的通信耗能；并且依據(jù)阿特金森福利函數(shù)建立的簇間優(yōu)化路由不僅有效的平衡了不同位置簇頭的能耗，也減少了網(wǎng)絡(luò)的整體能量消耗。

圖4 三種協(xié)議存活節(jié)點(diǎn)數(shù)隨著時(shí)間的變化曲線

表2是三種協(xié)議的網(wǎng)絡(luò)生命周期。EBFA與LEACH、EEUC相比，在LT1上分別提高了169.3%和54.5%，在LT2上分別提高了90.8%和39.4%，網(wǎng)絡(luò)生命周期最大程度上得到延長。

表2 網(wǎng)絡(luò)生命周期

3.3 網(wǎng)絡(luò)的能量均衡性

本文主要從節(jié)點(diǎn)剩余能量方差、節(jié)點(diǎn)剩余能量分布和死亡節(jié)點(diǎn)分布來衡量網(wǎng)絡(luò)的能量均衡性［12］。

圖5 網(wǎng)絡(luò)節(jié)點(diǎn)剩余能量方差變化曲線

圖5給出了三種協(xié)議節(jié)點(diǎn)能量方差隨時(shí)間變化的比較，本協(xié)議的網(wǎng)絡(luò)節(jié)點(diǎn)能量方差一直都很低變化不大，表明本協(xié)議能有效的均衡網(wǎng)絡(luò)及節(jié)點(diǎn)能量，從圖5可以看出，LEACH簇頭的產(chǎn)生具有隨機(jī)性，且不同位置的簇頭能量消耗差異很大，所以均衡性較差；EEUC采用非均勻分簇的思想來平衡簇頭之間的能耗，達(dá)到了較好的均衡效果；EBFA協(xié)議同樣采用非均勻分簇，但能量均衡性能表現(xiàn)最好，這說明通過福利函數(shù)評價(jià)建立的簇間多跳路徑在平衡能量消耗方面發(fā)揮了較好的作用。

本文還比較了節(jié)點(diǎn)剩余能量的分布情況。圖6中三圖是當(dāng)網(wǎng)絡(luò)中第一個(gè)節(jié)點(diǎn)死亡時(shí)，網(wǎng)絡(luò)中所有節(jié)點(diǎn)剩余能量的數(shù)量分布，直觀顯示了網(wǎng)絡(luò)中節(jié)點(diǎn)之間剩余能量的差距。LEACH協(xié)議中，當(dāng)?shù)谝粋€(gè)節(jié)點(diǎn)死亡時(shí)，仍有大量節(jié)點(diǎn)剩余較多的能量，能量均衡性較差；EEUC中引入非均勻分簇的多跳路由機(jī)制，較好解決了這個(gè)問題，當(dāng)?shù)谝粋€(gè)節(jié)點(diǎn)死亡時(shí)，沒有節(jié)點(diǎn)仍剩余較多能量，其他節(jié)點(diǎn)剩余能量差距不大；EBFA中，當(dāng)網(wǎng)絡(luò)中出現(xiàn)第一個(gè)死亡節(jié)點(diǎn)時(shí)，網(wǎng)絡(luò)已經(jīng)運(yùn)行了相當(dāng)一段時(shí)間，并且節(jié)點(diǎn)剩余能量都都在20%左右，節(jié)點(diǎn)間的能量均能最好。

圖6 剩余節(jié)點(diǎn)能量分布

圖7中三圖是網(wǎng)絡(luò)中死亡節(jié)點(diǎn)到達(dá)20%時(shí)，死亡節(jié)點(diǎn)的分布情況，圖中‘o’代表存活節(jié)點(diǎn)，‘x’表示死亡節(jié)。從圖中我們可以看出：LEACH死亡節(jié)點(diǎn)全都集中在距離基站較遠(yuǎn)的區(qū)域，這是因?yàn)樗鼈冃枰拇罅磕芰哭D(zhuǎn)發(fā)簇內(nèi)節(jié)點(diǎn)收集的信息，EEUC則由于靠近基站的節(jié)點(diǎn)承擔(dān)過量的轉(zhuǎn)發(fā)任務(wù)而大量死亡，EBFA協(xié)議很好地解決了能量均衡性的問題，死亡節(jié)點(diǎn)分布比較均勻，網(wǎng)絡(luò)未出現(xiàn)嚴(yán)重的“能量空洞”現(xiàn)象。

圖7 死亡節(jié)點(diǎn)分布圖

4 總結(jié)

本文汲取EEUC非均勻分簇和簇間多跳路由的算法思想，提出了改進(jìn)的分布式非均勻分簇路由算法，即EBFA。EBFA協(xié)議在簇頭競爭階段采用計(jì)時(shí)廣播機(jī)制，降低了控制消息的開銷；簇間多跳的建立引入依據(jù)社會福利函數(shù)設(shè)計(jì)的代價(jià)函數(shù)，優(yōu)化了中繼節(jié)點(diǎn)的選擇。仿真結(jié)果表明，EBFA能夠有效均衡網(wǎng)絡(luò)能量消耗，延長網(wǎng)絡(luò)的生命周期。

［1］Heinzelman W B，Chandrakasan A P，Balakrishnan H.An Application-Specific Protocol Architecture for Wireless Microsensor Networks［J］.IEEE Transactions on Wireless Communications，2002，1(4)：660-670.

［2］雷霖，李偉峰，王厚軍.基于遺傳算法的無線傳感器網(wǎng)絡(luò)路徑優(yōu)化［J］.電子科技大學(xué)學(xué)報(bào)，2009，38(2)：227-230.

［3］陳曉娟，王卓，吳潔.一種基于LEACH的改進(jìn)WSN路由算法［J］.傳感技術(shù)學(xué)報(bào)，2013(1)：116-121.

［4］Heinzelman W R，Chandrakasan A，Balakrishnan H.Energy-Efficient Communication Protocol for Wireless Microsensor Networks［C］//Proceedings of the 33rd Annual Hawaii International Conference on System Sciences，2000.IEEE，2000：10 pp.vol.2.

［5］Younis O，F(xiàn)ahmy S.Distributed Clustering in Ad-Hoc Sensor Networks：A Hybrid，Energy-Efficient Approach［C］//INFOCOM 2004.Twenty-Third Annual Joint Conference of the IEEE Computer and Communications Societies.IEEE，2004，1.

［6］蔡鑌，陳向東，楊英.節(jié)點(diǎn)密度自適應(yīng)的傳感器網(wǎng)絡(luò)加權(quán)分簇算法［J］.傳感技術(shù)學(xué)報(bào)，2009，22(4)：558-562.

［7］Soro S，Heinzelman W B.Prolonging the Lifetime of Wireless Sensor Networks Via Unequal Clustering［C］//Parallel and Distributed Processing Symposium，2005.Proceedings.19th IEEE International.IEEE，2005：8.

［8］李成法，陳貴海，葉懋，等.一種基于非均勻分簇的無線傳感器網(wǎng)絡(luò)路由協(xié)議［J］.計(jì)算機(jī)學(xué)報(bào)，2007，30(1)：27-36.

［9］蔣暢江，石為人，唐賢倫，等.能量均衡的無線傳感器網(wǎng)絡(luò)非均勻分簇路由協(xié)議［J］.軟件學(xué)報(bào)，2012，23(5)：1222-1232.

［10］曾華圣，熊慶宇，杜敏，等.一種分布式能量高效的WSNs非均勻分簇路由協(xié)議［J］.傳感器與微系統(tǒng)，2014，33(3)：146-149.

［11］Jiang H，Sun Y，Sun R，et al.Fuzzy-Logic-Based Energy Optimized Routing for Wireless Sensor Networks［J］.International Journal of Distributed Sensor Networks，2013.

［12］黃丹.無線傳感器網(wǎng)絡(luò)分簇路由協(xié)議研究［D］.大連：大連海事大學(xué)，2013.

孫彥景(1977-)，男，山東滕州，博士，教授，博士生導(dǎo)師，主要研究領(lǐng)域?yàn)榈V井無線通信與監(jiān)控，礦山物聯(lián)網(wǎng)等，yanjingsun_cn@163.com；

林昌林（1990-），男，碩士研究生，主要研究領(lǐng)域?yàn)闊o線通信和自組織網(wǎng)絡(luò)，mymail1991@163.com

An Energy Efficient Distributed Uneven Clustering Routing Algorithm for WSNs*

SUN Yanjing1，2*，LIN Changlin1，JIANG Haifeng3
(1.School of Information and Electrical Engineering，China University of Mining and Technology，Xuzhou Jiangsu 221116，China；2.Coal Mine Electrical Engineering and Automation Laboratory in JiangSu Province，Xuzhou Jiangsu 221008，China；3.School of Computer Science and Technology，China University of Mining and Technology，Xuzhou Jiangsu 221116，China)

To solve the"hot zone"problem appearing in distributed clustering routing multi-hop communication，this paper proposes an energy balanced forwarding algorithm(EBFA)based on distributed clustering routing protocols.EBFA adopts the uneven clustering techniques and multi-hop inter-cluster strategy.During the multi-hop forwarding，the social welfare function is introduced to pre-assess the extent of energy balance between nodes in the data forwarding path，and the node with a better energy balance is chosen as the forwarding node.Simulation results show that：Compared to LEACH and EEUC，EBFA prolongs the lifetime of the network and balances the energy consumption among sensor nodes，which solves the hot zone problem in the multi-hop routing.

WSNs；uneven clustering；social welfare function；multi-hop forwarding

TP92

A

1004-1699(2015)08-1194-07

??7230；6150P

10.3969/j.issn.1004-1699.2015.08.016

項(xiàng)目來源：國家自然科學(xué)基金面上項(xiàng)目(51274202)；中央高?；究蒲袠I(yè)務(wù)費(fèi)專項(xiàng)資金項(xiàng)目(2013RC11)；江蘇省科技成果轉(zhuǎn)化項(xiàng)目(子課題)(BA2012068)；江蘇省自然科學(xué)基金面上項(xiàng)目(BK20130199，BK20131124)；江蘇省產(chǎn)學(xué)研前瞻性聯(lián)合研究項(xiàng)目(BY2014028-01)；中國礦業(yè)大學(xué)重大項(xiàng)目培育專項(xiàng)(2014ZDPY16)

2015-02-12 修改日期：2015-05-28