一種分布式能量有效的無線傳感器網絡分簇路由協議*

魏春娟，楊俊杰，張志美

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

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

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

1 相關工作

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

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

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

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

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

2 系統模型

2.1 網絡模型

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

2.2 能耗模型

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

圖1 傳感器節點無線通信能耗模型

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

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

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

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

3 協議描述

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

3.1 簇首選擇

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

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

其中，m表示節點i的所有鄰居節點的數量，Ej為節點j的剩余能量。

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

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

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

3.2 簇的形成

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

3.3 簇的數據傳輸

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

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

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

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

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

4 性能分析

4.1 實驗參數設置

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

表1 實驗參數

4.2 仿真結果分析

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

表2 網絡生存周期對比

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

圖2 死亡節點數隨時間的變化

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

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

5 總結

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

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

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

［3］ 李建奇，曹斌芳，王搖立，等.一種結合LEACH和PEGASIS協議的WSN的路由協議研究［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，Fahmy 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:能量感知的無線傳感器網絡數據收集協議［J］.軟件學報，2007，18(5):1092－1109.

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

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

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

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