魏春娟，楊俊杰，張志美

(1.上海電力學院電子與信息工程學院，上海200090;2.沈陽師范大學，物理科學與技術學院，沈陽110034)

無線傳感器網(wǎng)絡WSN(Wireless Sensor Network)采用分布式處理，通過大量部署在監(jiān)測區(qū)域內的傳感器節(jié)點，采集網(wǎng)絡覆蓋區(qū)域內感知對象的信息。節(jié)點間通過多跳的無線通信方式，將收集、處理后的信息傳送到基站進行處理，最終提供給終端用戶［1］。由于無線傳感器節(jié)點大多采用能量有限的電池供電，且節(jié)點數(shù)目多、分布廣、所處環(huán)境復雜，通過更換電池來補充能源不易實現(xiàn)，而能量消耗直接決定了傳感器網(wǎng)絡的使用壽命，因此設計優(yōu)化網(wǎng)絡的整體能耗效率、延長網(wǎng)絡壽命的路由協(xié)議是無線傳感器網(wǎng)絡的一項重要研究內容［2－3］。

本文提出了一種分布式能量有效的分簇路由協(xié)議DEEC(Distributed Energy-efficient Clustering Routing Protocol)。DEEC采用基于時間的簇首選擇算法，廣播時間取決于自身剩余能量和其鄰居節(jié)點的剩余能量。在數(shù)據(jù)傳輸階段，采用簇內單跳與簇間多跳相結合的方式，各簇首根據(jù)節(jié)點剩余能量、到基站的距離及簇內成員的個數(shù)計算權值，然后依據(jù)權值大小建立到達基站的路由樹。仿真實驗結果表明，與LEACH，PEGASIS協(xié)議相比，DEEC能夠有效地節(jié)約單個節(jié)點能量、均衡網(wǎng)絡能耗、延長網(wǎng)絡生存周期。

1 相關工作

分簇路由協(xié)議將網(wǎng)絡感知的數(shù)據(jù)進行融合后再進行傳輸，減少冗余數(shù)據(jù)傳輸產生的能量開銷及增強網(wǎng)絡的可擴展性，近年來已成為WSN中研究的熱點。

LEACH (Low-Energy Adaptive Clustering Hierarchy)［4］是MIT 的Wendi B Heinzelman 等人為無線傳感器網(wǎng)絡設計的低功耗自適應聚類路由算法，它是第一個基于分簇結構的無線傳感器網(wǎng)絡路由協(xié)議。為了將能量負載均勻地分配到各節(jié)點上，LEACH協(xié)議按輪運行，并在每一輪中通過等概率地隨機對簇首進行輪換。當簇生成以后，簇首將聚合其收到的各成員節(jié)點的采集信息，并將聚合信息直接單跳傳輸?shù)交尽Ｓ捎跍p少了與基站直接通信的節(jié)點數(shù)量以及通信量，LEACH協(xié)議可以有效地延長網(wǎng)絡生命周期。然而，LEACH算法對以下幾點沒有考慮:①簇首數(shù)目的優(yōu)化，LEACH每輪中任意節(jié)點成為簇首的概率為p，因此簇首的數(shù)目與節(jié)點的數(shù)量規(guī)模成正比;②所有簇首直接與基站通信，對于遠離基站的簇首其能量損耗很快;③由于簇首是隨機選取的，因此算法不能保證簇首在網(wǎng)絡中的分布，而簇首的分布將決定該輪中傳感器網(wǎng)絡的能量損耗狀況。

Lindsey等人提出的 PEGASIS(Power-Efficient Gathering in Sensor Information Systems)［5］協(xié)議，把所有的傳感器節(jié)點視為一個簇，根據(jù)節(jié)點的地理位置通過貪婪算法形成一條相鄰節(jié)點之間距離最短的鏈，數(shù)據(jù)在鏈上經融合處理，最后傳輸至匯聚點。Younis等人提出一種混合式的分簇協(xié)議HEED(a Hybrid Energy-Efficient Distributed Clustering Approach)［6］，算法首先根據(jù)節(jié)點的剩余能量來概率性地選取一些候選簇頭，然后以簇內通信代價的高低來競爭產生最終簇頭。與LEACH不同的是，它的簇生成算法需要在簇半徑內進行多次消息迭代，由此帶來的通信開銷比較顯著。TEEN［7］算法建立起多級分簇結構，在分簇過程完成之后，通過硬閥值和軟閥值兩個參數(shù)控制數(shù)據(jù)的發(fā)送次數(shù)，只有當監(jiān)測到的數(shù)據(jù)大于硬閾值，并且與保存的監(jiān)測值的差大于等于軟門限值時才上傳數(shù)據(jù)，通過這樣的過程以達到節(jié)能的效果。APTEEN［8］算法在TEEN算法的基礎上，通過計數(shù)器的方式周期性地采集數(shù)據(jù)并對突發(fā)事件做出快速反應。

此外，針對網(wǎng)絡中部分簇首節(jié)點可能會承擔較多的網(wǎng)絡流量或者在單位時間內有較多的能耗引起“能量空洞”問題，提出了一些非均勻分簇策略。EECS［9］，EEUC［10］，EADEEG［11］、DEBUC［12］、DEEUC［13］等 協(xié) 議通過調節(jié)簇半徑的大小實現(xiàn)能耗均衡，即在離基站較近的能耗較多的區(qū)域形成較小的簇，這樣簇首節(jié)點有較多的剩余能量用于轉發(fā)來自其他節(jié)點的數(shù)據(jù)。文獻［14－15］分別采用蟻群算法和粒子群算法優(yōu)化路徑搜索。

本文提出一種基于LEACH的分布式能量有效的分簇路由協(xié)議DEEC，并從簇首選擇、數(shù)據(jù)傳輸?shù)确矫鎸EACH進行改進。在簇首競爭階段，根據(jù)節(jié)點剩余能量與鄰居節(jié)點平均剩余能量的比值計算廣播時間;在數(shù)據(jù)傳輸階段，采用簇內單跳與簇間多跳相結合的方式，各簇頭在選擇中繼節(jié)點時綜合考慮剩余能量、到基站的距離和簇內成員的個數(shù)等因素，然后依據(jù)權值大小建立到達基站的路由樹。仿真結果顯示，DEEC協(xié)議對LEACH有較大改進，可提高網(wǎng)絡能效性能達37.5%。

2 系統(tǒng)模型

2.1 網(wǎng)絡模型

考慮一個由N個隨機部署的傳感器節(jié)點形成的網(wǎng)絡，其應用場景為周期性的數(shù)據(jù)收集。假設N個節(jié)點隨機均勻分布在一個M×M的二維正方形區(qū)域A內，并具有如下性質:①傳感器網(wǎng)絡為高密度靜態(tài)網(wǎng)絡，即節(jié)點部署后不再移動。②基站部署在區(qū)域A以外的一個固定位置，且基站是唯一的。③所有節(jié)點都是同構的，即具有相同的數(shù)據(jù)處理能力、通信能力和初始能量等，并且地位平等，都能充當簇頭節(jié)點或普通節(jié)點，每個節(jié)點都有一個唯一的標識(ID)。④節(jié)點不能獲知其位置信息。節(jié)點獲取位置信息需要依靠GPS、有向天線或定位算法等輔助設施或算法，必然增加其成本和能耗開銷。⑤節(jié)點的無線發(fā)射功率可調，即節(jié)點可以根據(jù)距離遠近來調整發(fā)射功率的大小。例如，Berkeley Motes節(jié)點具有100個發(fā)射功率等級。⑥通信鏈路是對稱的，即節(jié)點間可以使用相同的傳輸能量進行通信。若已知對方發(fā)射功率，節(jié)點可以根據(jù)接收信號的強度RSSI計算出發(fā)送者到自己的近似距離。

2.2 能耗模型

我們采用與文獻［4］相同的無線通信能量消耗模型，節(jié)點能耗包括3部分:發(fā)送數(shù)據(jù)能耗、接收數(shù)據(jù)能耗、數(shù)據(jù)融合能耗。各個模塊的能耗如圖1所示。

圖1 傳感器節(jié)點無線通信能耗模型

節(jié)點發(fā)射比特的數(shù)據(jù)到距離為d的位置，消耗的能量由發(fā)射電路損耗和功率放大損耗兩部分組成，即

其中Eelec表示發(fā)射電路損耗的能量。若傳輸距離小于閾值d0，功率放大損耗采用自由空間模型;當傳輸距離大于等于閾值d0時，采用多徑衰減模型。εfs、εmp分別為這兩種模型中功率放大所需的能量。節(jié)點接收比特的數(shù)據(jù)消耗的能量為

此外，數(shù)據(jù)融合也消耗一定的能量，我們假設鄰近節(jié)點采集的數(shù)據(jù)具有較高的冗余度，簇首可以將其成員的數(shù)據(jù)和自身的數(shù)據(jù)融合成一個長度固定的數(shù)據(jù)包，然后發(fā)送給匯聚點。融合過程中消耗的能量Ec由式(3)決定

式中，EDA表示融合單位數(shù)據(jù)信號消耗的能量，M為簇內成員的個數(shù)。

3 協(xié)議描述

由于簇首節(jié)點的能耗遠大于普通的成員節(jié)點，為了均衡節(jié)點的能量負載并保持算法的分布性，DEEC按輪運行，每輪分為簇首的選擇、簇的形成和數(shù)據(jù)傳輸3個階段。在每一輪初始時重新構造簇，并根據(jù)節(jié)點剩余能量與鄰居節(jié)點平均剩余能量的比值選擇簇首，然后簇首融合簇內數(shù)據(jù)并多跳傳遞到基站。

3.1 簇首選擇

DEEC采用分布式簇首競爭算法，簇首的選擇以節(jié)點及其鄰居節(jié)點的剩余能量為主要依據(jù)。為計算鄰居節(jié)點的平均能量，每個節(jié)點需保存一張鄰居節(jié)點信息表，以儲存其鄰居節(jié)點的ID及剩余能量。

每輪開始時，采取與LEACH相同的做法，每個節(jié)點隨機產生介于0與1之間的數(shù)，如果這個數(shù)小于閾值，則該節(jié)點成為候選簇首;否則作為普通節(jié)點進入休眠狀態(tài)直到簇首選舉算法結束。對于每個候選簇首節(jié)點，首先以半徑r廣播包括自身ID和剩余能量的E_MSG消息。然后根據(jù)所有鄰居節(jié)點發(fā)送來的E_MSG更新其鄰居表，并求出其所有鄰居節(jié)點的平均剩余能量。節(jié)點i的所有鄰居節(jié)點的平均剩余能量為:

其中，m表示節(jié)點i的所有鄰居節(jié)點的數(shù)量，Ej為節(jié)點j的剩余能量。

這里，k是一個隨機均勻分布在［0.9，1］之間的實數(shù)值，T則是預先設置的簇首選擇算法的最長時間，Ei表示節(jié)點i的剩余能量。

在DEEC協(xié)議中，若候選簇首節(jié)點在時刻t前沒有收到任何鄰居節(jié)點發(fā)出的HEAD_MSG消息，則該節(jié)點向鄰居節(jié)點廣播HEAD_MSG消息，申明其成功競選為簇首。如果節(jié)點在其t時刻前已經收到了鄰居廣播的HEAD_MSG消息，則該節(jié)點放棄簇首競爭，成為普通節(jié)點，并向最近的簇首發(fā)送JOIN_MSG消息加入該簇。

根據(jù)式(5)，廣播時間t取決于節(jié)點的剩余能量和其鄰居節(jié)點的平均剩余能量。如果節(jié)點在其所處區(qū)域具有較大的能量，則它成為簇首的等待時間較短，概率較大。由于簇首競爭過程中只有少量節(jié)點發(fā)送一條HEAD_MSG消息，使得DEEC協(xié)議的控制消息開銷非常小。

3.2 簇的形成

在簇首被選擇出來后，采用與LEACH協(xié)議相同的簇生成方法，即每個簇首節(jié)點廣播當選的HEAD_MSG消息到周圍節(jié)點，其他非簇首節(jié)點根據(jù)接收到的信號強度選擇離自己最近的簇首決定加入這個簇，并通過CSMA的MAC協(xié)議發(fā)送請求加入簇的JOIN_MSG消息到對應簇首。至此，網(wǎng)絡的分簇完成。

3.3 簇的數(shù)據(jù)傳輸

DEEC協(xié)議采用簇內單跳和簇間多跳數(shù)據(jù)傳輸方式。每個簇首需要從鄰居簇首中選擇一個作為其中繼節(jié)點，轉發(fā)數(shù)據(jù)至基站。本文假設數(shù)據(jù)的冗余度有限，來自不同簇的數(shù)據(jù)無法進一步融合，中繼簇首節(jié)點只是簡單轉發(fā)來自其他簇首的數(shù)據(jù)。

DEEC協(xié)議簇間多跳路由的建立也采用分布式策略。首先，簇首CHi向覆蓋半徑2r內的節(jié)點廣播WEIGHT_MSG消息，這條消息包含簇首ID及權值W(CHi)。然后，各簇首將自身的權值與收到的WEIGHT_MSG中包含的權值進行比較:①若該節(jié)點權值大于所有鄰居節(jié)點的權值，則該簇首節(jié)點直接發(fā)送數(shù)據(jù)至基站;②若該節(jié)點權值較小，則選取權值最大的節(jié)點作為父節(jié)點(中繼節(jié)點)，并發(fā)送CHILD_MSG通知父節(jié)點，這樣權值最大的節(jié)點將成為樹的根節(jié)點，如此建立起一棵路由樹;③若發(fā)生權值相等的情況，則進一步根據(jù)ID值大小選擇下一跳節(jié)點。

接下來，簇首沿著構造好的多跳路由樹將收集到的數(shù)據(jù)轉發(fā)給父節(jié)點，一級一級傳遞到根節(jié)點，最后由根節(jié)點將融合后的數(shù)據(jù)傳送到基站，即簇首與基站采用多跳路由方式進行通信。

在計算簇首權值時，綜合考慮它的剩余能量、到基站的距離以及簇內成員的個數(shù)。簇首CHi的權值計算公式為:

式中:①ECHi為簇首CHi的當前剩余能量，ECH_max為簇首的最大能量。中繼節(jié)點完成數(shù)據(jù)轉發(fā)的任務，需要消耗更多的能量，故能量因素是首先需要考慮的，擁有更多剩余能量的簇首成為中繼節(jié)點的概率較大?；诮档湍芎?，減少不必要的計算量的原則(以下選取參數(shù)也遵循此原則)，本文取ECH_max等于節(jié)點的初始能量。②dCHi_toBS表示簇首CHi到基站的距離，dCH_toBS_max表示簇首到基站的最大距離。距離基站越近的簇首承擔的數(shù)據(jù)轉發(fā)任務越重，其數(shù)據(jù)轉發(fā)能耗越大。為了避免基站附近的簇首過早地耗盡能量而失效，簇首被選為父節(jié)點的概率與節(jié)點到基站的距離成反比，以增加基站附近父節(jié)點的數(shù)目。本文取dCH_toBS_max等于坐標原點到基站的距離。③Nnon_CHi表示以簇首CHi構建的簇中包含的成員節(jié)點的個數(shù)，Nnon_CH_max表示簇內成員個數(shù)的最大值。選擇簇內成員節(jié)點較少的簇首作為中繼節(jié)點。成員節(jié)點較少的簇首在簇內通信中消耗的能量較少，故有較多的能量保留下來用于簇間數(shù)據(jù)轉發(fā)。本文取Nnon_CH_max等于網(wǎng)絡中節(jié)點數(shù)N。④α、β、γ表示加權系數(shù)，且滿足α+β+γ=1。這樣，能量足夠、距離基站較近且簇內成員較少的簇首將優(yōu)先成為根節(jié)點。

4 性能分析

4.1 實驗參數(shù)設置

為了驗證協(xié)議的性能，利用MATLAB在相同條件下仿真 LEACH，PEGASIS和本協(xié)議 DEEC，并對比多項性能。仿真實驗均基于同一實驗場景:在100 m×100 m的區(qū)域內隨機部署200個節(jié)點，Sink節(jié)點位于坐標(50，175)，所有節(jié)點一旦放置就不再移動。簇首權值計算公式中取 α=0.6，β=0.3，γ=0.1。簇半徑r根據(jù)文獻［15］取最優(yōu)值，仿真實驗的其他參數(shù)如見表1。

表1 實驗參數(shù)

4.2 仿真結果分析

為了全面衡量協(xié)議性能，仿真分析了3種網(wǎng)絡壽命:第一個節(jié)點死亡 first_dead，10%節(jié)點死亡teenth_dead，以及全部節(jié)點死亡all_dead。表2列出了LEACH，PEGASIS，DEEC協(xié)議的3種網(wǎng)絡壽命及當時網(wǎng)絡節(jié)點的平均剩余能量。與LEACH和PEGASIS相比，DEEC協(xié)議使得第一個節(jié)點死亡對應的網(wǎng)絡生存周期分別提高了37.5%和13.5%。

表2 網(wǎng)絡生存周期對比

圖2顯示了網(wǎng)絡死亡節(jié)點數(shù)量隨時間變化的情況。從圖中可以看出，DEEC相對于 LEACH和PEGASIS明顯提高了網(wǎng)絡生存周期。由于LEACH以隨機的方式選擇簇頭，簇頭分布不均勻，導致一些節(jié)點與基站直接通信，節(jié)點很快死亡。PEGASIS協(xié)議由于要獲得所有節(jié)點的全局消息，在節(jié)點數(shù)量較多的情況下控制開銷較大，所以性能受到一定的影響。DEEC采用計時廣播方式有效減小了簇頭競爭階段的通信能耗，簇間多跳路由更有效地平衡了不同位置簇頭節(jié)點的能耗。

圖2 死亡節(jié)點數(shù)隨時間的變化

圖3對比了3種協(xié)議的網(wǎng)絡節(jié)點的平均剩余能量隨仿真周期的變化曲線。較小的坡度顯示較慢的能量消耗速度和較長的生存時間，DEEC協(xié)議的坡度明顯小于LEACH和PEGASIS，并且DEEC的網(wǎng)絡節(jié)點能量均值一直都比LEACH或者PEGASIS的高，表明DEEC協(xié)議能夠更有效的節(jié)約節(jié)點能量。同時，從表2中可看出，DEEC中10%節(jié)點死亡時，節(jié)點平均能量已經很小(0.029 7 J)，而LEACH與PEGASIS此時節(jié)點平均能量分別為0.079 8 J和0.045 2 J。說明DEEC能夠有效地平衡節(jié)點間的能耗。

圖3 節(jié)點平均剩余能量隨時間的變化

5 總結

基于較大規(guī)模WSNs應用，本文提出一種分布式能量有效的分簇路由協(xié)議DEEC，該協(xié)議基于網(wǎng)絡局部信息實現(xiàn)簇首選擇和簇間多跳路由。在簇首競爭階段，采用計時廣播機制，使得鄰居節(jié)點平均剩余能量與自身剩余能量比值大的節(jié)點等待的時間更短，成為簇首的概率更大。在數(shù)據(jù)傳輸階段，采用簇內單跳與簇間多跳相結合的方式，引入權值函數(shù)優(yōu)化簇頭中繼節(jié)點的選擇。仿真結果顯示，DEEC協(xié)議可以有效地提高傳感器網(wǎng)絡的生存周期，均衡網(wǎng)絡能耗。在下一步工作中，我們將考慮將DEEC協(xié)議引入異構傳感器網(wǎng)絡中，使DEEC協(xié)議具有更加廣泛的應用場合。

［1］ 任豐原，黃海寧，林闖.無線傳感器網(wǎng)絡［J］.軟件學報，2003，14(7):1282－1291.

［2］ 劉群，白全煒，曾憲華，等.能量感知的WSN節(jié)點分類控制路由算法［J］.傳感技術學報，2011，24(7):1053－1059.

［3］ 李建奇，曹斌芳，王搖立，等.一種結合LEACH和PEGASIS協(xié)議的WSN的路由協(xié)議研究［J］.傳感技術學報，2012，25(2):263－267.

［4］ Heinzelman W R.An Application-Specific Protocol Architecture for Wireless Microsensor Networks［J］.IEEE Trans on Wireless Communications，2002，1(4):660－670.

［5］ Lindsey S，Raghavendra C S.Pegasis:Power-Efficient Gathering in Sensor Information Systems［C］//Proc of the IEEE Aerospace Conf Montana:IEEE Aerospace and Electronic Systems Society，2002.1125－1130.

［6］ Younis O，F(xiàn)ahmy S.Heed:A Hybrid，Energy-Efficient，Distributed Clustering Approach for Ad-Hoc Sensor Networks［J］.IEEE Trans on Mobile Computing，2004，3(4):660－669.

［7］ Manjeshwar A，Grawal DP.TEEN:A Protocol for Enhanced Efficiency in Wireless Sensor Networks［C］//Proc.of the 15th Parallel and Distributed Processing Symp.San Francisco:IEEE Computer Society，2001.2009－2015.

［8］ Manjeshwar A，Agrawal D P.APTEEN:A Hybrid Protocol for Efficient Routing and Comprehensive Information Retrieval in Wireless Sensor Networks［C］//Proc of the 2nd Int’l Workshop on Parallel and Distributed Computing Issues in Wireless Networks and Mobile Computing.IEEE Computer Society，2002.195－202.

［9］ Ye M，Li C F，Chen G H，et al.EECS:An Energy Efficient Clustering Scheme in Wireless Sensor Networks［C］//Proc of the IEEE Int’l Performance Computing and Communications Cone NewYork:IEEE Press，2005.535－540.

［10］ Chen G H，Li C，Ye M，et al.An Unequal Cluster-Based Routing Protocol in Wireless Sensor Networks［J］.Wireless Networks，2007，15(2):193－207.

［11］劉明，曹建農，陳貴海，等.EADEEG:能量感知的無線傳感器網(wǎng)絡數(shù)據(jù)收集協(xié)議［J］.軟件學報，2007，18(5):1092－1109.

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

［13］ 尚鳳軍，Mehran Abolhasan，Tadeusz Wysocki.無線傳感器網(wǎng)絡的分布式能量有效非均勻成簇算法［J］.通信學報，2009，30(10):34－43.

［14］張榮博，曹建福.利用蟻群優(yōu)化的非均勻分簇無線傳感器網(wǎng)絡路由算法［J］.西安交通大學學報，2010，44(6):33－38.

［15］秦智超，周正，趙小川.利用粒子群優(yōu)化的WSN環(huán)狀簇路由協(xié)議［J］.北京郵電大學學報，2012，35(5):26－30.