張巖

摘 要： 針對LEACH算法簇頭選取及能量消耗方面的不足，提出一種基于能量、距離和節(jié)點度的分簇路由算法CMEDD，通過均勻分簇減少重建過程，對簇頭選舉公式進行改進，合理選擇簇頭，從而均衡節(jié)點能耗。采用基于代價因子的單跳和多跳相結(jié)合的方式建立最優(yōu)路徑進行數(shù)據(jù)傳輸。仿真結(jié)果表明，與LEACH算法和RMCRW算法相比，CMEDD算法能夠有效均衡節(jié)點能耗，可相對延長網(wǎng)絡生存周期。

關鍵詞： 無線傳感器網(wǎng)絡； 能耗均衡； 簇頭選?。?網(wǎng)絡生命周期

中圖分類號： TN711?34； TP393 文獻標識碼： A 文章編號： 1004?373X（2015）18?0026?04

Abstract： Aiming at the insufficiency of cluster head selection and energy consumption of LEACH algorithm， a CMEDD clustering routing algorithm based on energy， distance and node degree is proposed to simplify the reconstruction process by uniform clustering， improve the way to select cluster head， and select the cluster head reasonably， so that the energy consumption of the nodes can be balanced. Moreover the optimal path was set up by the mode combining single hop and multi hop based on cost factor to transmit data. The simulation results show that compared with LEACH algorithm and RMCRW algorithm， the CMEDD algorithm can more effectively balance the node energy consumption and prolong the network lifetime relatively.

Keywords： wireless sensor network （WSN）； energy consumption balance； cluster head selection； network lifecycle

無線傳感器網(wǎng)絡中，傳感器節(jié)點多采用能量有限的電池供電，使得整個網(wǎng)絡對數(shù)據(jù)的存儲處理和傳輸能力受到了限制。所以如何有效使用傳感器節(jié)點能量，以及如何延長網(wǎng)絡的生命周期就成為設計無線傳感器網(wǎng)絡路由協(xié)議的一個重點，其中從管理的角度上對網(wǎng)絡進行層次化管理是目前該領域的一個研究熱點。

文獻[1]提出了無線傳感網(wǎng)拓撲控制典型的低功耗自適應算法LEACH，與平面拓撲算法相比，該協(xié)議可以延長網(wǎng)絡生命期約30%。但是LEACH 算法沒有考慮能量不平衡問題，存在很大改進空間。

針對LEACH算法存在的問題，學者們提出一系列改進的算法[2?7]。文獻[2?4]均提出基于剩余能量的自適應分簇算法，算法選擇剩余能量最大的節(jié)點作為簇頭，平衡能耗。文獻[5]提出了基于節(jié)點能量閾值的簇頭競爭算法，當簇頭節(jié)點的剩余能量值降低到特定閾值下時，算法就啟動新一輪簇的建立過程。文獻[6]利用節(jié)點到基站的距離作為簇頭選擇的權重對LEACH算法進行改進。文獻[7]LEACH?EI算法，考慮節(jié)點初始能量和當前能量2個因素，利用動態(tài)分簇的方式計算能量閾值，根據(jù)能量閾值選擇簇頭。文獻[8]ECRED算法通過引入備選簇頭減少簇的重建，用以降低簇頭選舉的能耗。文獻[9]RMCRW算法提出基于環(huán)的簇頭選舉方式，引入權值控制簇頭轉(zhuǎn)發(fā)路徑，達到節(jié)能目的。另外也有研究者將已有的一些優(yōu)化算法如遺傳算法、蟻群算法等應用到路由算法的設計中，從而延長網(wǎng)絡壽命。

在深入研究無線傳感器網(wǎng)絡LEACH及其相關改進協(xié)議的基礎上，本文設計了一種基于能量、距離、節(jié)點度的算法（A Cluster Head Make up?Energy?Distance?Density Algorithm Improved Based on LEACH Algorithm，CMEDD）。

1 網(wǎng)絡模型

1.1 本文采用的節(jié)點模型假設如下：

（1） 基站距離較遠且能量無限，位置不發(fā)生改變；

（2） 節(jié)點同構且初始能量相等，一經(jīng)部署其位置不再發(fā)生改變；

（3） 節(jié)點發(fā)送功率可以進行調(diào)整，即具有調(diào)節(jié)無線收發(fā)器工作能耗的控制功能；

（4） 節(jié)點能夠支持多種MAC協(xié)議（如TDMA等）；

（5） 傳感器節(jié)點具有足夠的計算能力，即具有一定的數(shù)據(jù)融合功能。

1.2 能耗模型

節(jié)點[l]位的數(shù)據(jù)包傳送長度為[d]，通信模型為[9]：

[ETx（l，d）=lEelec+lEFSd2， d

式中：[Eelec]為單位[bit]數(shù)據(jù)收發(fā)能耗；[dcrossover]為模型劃分閾值，d大于[dcrossover]選擇多路衰減模型，其功放能耗為[Eamp]，d小于[dcrossover]選擇自由空間模型，其功放能耗為[Efs]。設[EDA]為簇頭節(jié)點數(shù)據(jù)融合能耗；[dtoBS]為簇頭到基站的距離；[N]為節(jié)點總數(shù)；[M]為正方形區(qū)域邊長，一輪工作總能耗為[Etotal]，則：[Etotal=l（EelecN+EDAN+kEampd4toBS+NEelec+NEfs12πM2k）] （2）

2 CMEDD算法描述

2.1 簇頭選擇

在分簇結(jié)構的無限傳感器網(wǎng)絡中簇頭個數(shù)[k]是影響分簇路由算法網(wǎng)絡能耗的一個重要參數(shù)。CMEDD算法采用文獻[10]中簇頭個數(shù)[k]的取值算法。本算法規(guī)定首輪成簇及廣播工作由基站完成，基站按照最佳簇頭個數(shù)將網(wǎng)絡化分成[k]個虛擬網(wǎng)格，進而基站在每個網(wǎng)格內(nèi)隨機選取一個節(jié)點作為本簇的簇頭，同時生成一個鄰居列表消息Message_neighbour，并將此信息廣播給各自簇（網(wǎng)格）內(nèi)成員節(jié)點 [11]。基站公布本次的信息匹配之前，所有節(jié)點不知道自己所屬的簇區(qū)域，因此基站發(fā)布的Message_neighbour消息覆蓋范圍要確保網(wǎng)絡內(nèi)所有節(jié)點都能接收到。

基站可以從第1輪各簇頭發(fā)送的數(shù)據(jù)確定所有節(jié)點及基站之間的距離關系，為第2輪及以后的簇頭選舉提供必要數(shù)據(jù)。在經(jīng)過[Nk]輪的工作之后，由于各種隨機事件使得簇內(nèi)節(jié)點能量可能差異較大。為了均衡網(wǎng)絡能耗并延長其使用周期，在隨后的簇頭選舉中將綜合考慮到節(jié)點剩余能量、簇內(nèi)節(jié)點平均距離及節(jié)點距基站距離、節(jié)點度等三方面因素：

（1） 節(jié)點剩余能量

在每一輪的工作結(jié)束時，每個節(jié)點查看自身的[En（r）]值，并向簇頭報告，簇頭計算簇內(nèi)的平均能量值，并向簇內(nèi)廣播。

（2） 簇內(nèi)節(jié)點平均距離及節(jié)點距基站距離

其次分析節(jié)點與簇內(nèi)其余節(jié)點以及與基站之間的距離參數(shù)[Dn]：

在網(wǎng)絡運行中傳感器節(jié)點一經(jīng)部署其位置不會改變，因此每個節(jié)點的距離參數(shù)只需要計算1次。節(jié)點位置信息的傳遞是在簇建立過程中對能量消息的傳遞中一起進行的，從而減少了信息交互中的通信損耗。

（3） 節(jié)點度析節(jié)點的度

節(jié)點為布爾感知模型[12]，即每個節(jié)點都具有一個固定的感知半徑[R]，其感知范圍是以節(jié)點為圓心，[R]為半徑的圓。簇內(nèi)處于某節(jié)點感知半徑內(nèi)的節(jié)點為此節(jié)點的一步通信節(jié)點。 一步通信節(jié)點個數(shù)稱作節(jié)點的度[Measuren]。一步通信節(jié)點較多，即其周圍節(jié)點分布較為密集，則該節(jié)點當選簇頭的概率也應隨之增大。節(jié)點的度調(diào)節(jié)參數(shù)[Mn]的模型及約束條件如下：

改進后的公式使得當前節(jié)點的剩余能量越大、節(jié)點到基站以及到其他節(jié)點之間的平均距離的關系參數(shù)越大，節(jié)點的度越大，則閾值[Tn]越大，從而該節(jié)點當選為簇頭的幾率越大，反之當選為簇頭的幾率越小。

2.2 簇間路由

網(wǎng)絡中的簇頭節(jié)點與普通節(jié)點一樣也有通信模型閾值[dcrosscover]，當傳輸距離小于此值時，其能耗與距離平方成線性關系。網(wǎng)絡中簇頭選取完畢則存在[G=V，E]，[V=v1，v2，…，vk]，[V]為簇頭集，[E]為可直接通信的兩節(jié)點間的通信能耗。則距離基站較遠的簇頭節(jié)點直接向基站發(fā)送數(shù)據(jù)能量會損失較快，不利于網(wǎng)絡能量均衡。CMEDD算法在簇頭向基站傳輸數(shù)據(jù)時，按照代價因子公式尋找下一跳中轉(zhuǎn)接點。

假定在網(wǎng)絡中[vi，vj]均為簇頭，則簇頭節(jié)點[vj]作為簇頭節(jié)點[vi]的下一跳中轉(zhuǎn)節(jié)點的代價因子為：

[fcost（vj）=Ei，j·si，j·sjEvj] （11）

式中：[Ei，j∈E]；[Evj]為簇頭節(jié)點[vj]的當前能量；[sij]為[vi，vj]之間距離，且[sij≤][dcrosscover]；[Sj]為[vj]到基站的距離，[j=1，2，…，k]。節(jié)點[vi]從屬于集合[V]并且與自身距離小于[dcrosscover]的節(jié)點中找到代價因子最小的節(jié)點[vj]，作為自己的下一跳中轉(zhuǎn)節(jié)點。[vj]再以同樣的方式找到自己的下一跳中轉(zhuǎn)節(jié)點，從而形成一條通向基站的通信鏈路。則[vj]可作為[vi]的中轉(zhuǎn)節(jié)點，[vi]向[vj]發(fā)送數(shù)據(jù)符合自由空間模型，通信鏈路上的總體能量消耗遠小于多路衰減模型。

3 算法仿真與性能驗證

為了驗證CMEDD算法的有效性，對CMEDD，RMCRW和LEACH算法進行對比。仿真實驗在Matlab R2014a環(huán)境下進行，以隨機方式在監(jiān)測區(qū)域內(nèi)部署傳感器節(jié)點，假設節(jié)點分布在坐標為[0，0]到[100，100]的區(qū)域內(nèi)。仿真實驗使用參數(shù)取值分別為：N=100，M=100，數(shù)據(jù)包長度l=500，基站的坐標（50，175），Efs=10 pJ，Eamp=0.001 3 pJ，節(jié)點初始能量E0=2×1010 pJ，EDA=5×103 pJ，Eelec=50×103 pJ。

無線傳感器網(wǎng)絡的生命周期著重從首節(jié)點能量耗盡所用時間進行考慮?；谶@一原因?qū)嶒瀸W(wǎng)絡節(jié)點數(shù)分別為100，200時三種算法運行期間存活節(jié)點數(shù)進行仿真，其仿真圖分別如圖1，圖2所示。

如圖1所示，模擬環(huán)境與初始能量相同，100個節(jié)點時LEACH算法運行16輪，第17輪出現(xiàn)節(jié)點能量耗盡；RMCRW算法運行20輪，第21輪出現(xiàn)節(jié)點能量耗盡；而CMEDD算法運行22輪左右開始出現(xiàn)能量耗盡的節(jié)點。CMEDD算法首節(jié)點死亡輪數(shù)較LEACH算法延長了37.5%、較RMCRW算法延長了10.1%。說明同樣的運行時間，CMEDD算法節(jié)點能耗更低，并使節(jié)點能耗的分布更加均勻，即有效延長了節(jié)點的生存時間。由圖2可知，在各項參數(shù)保持不變的環(huán)境下，將節(jié)點數(shù)增至200，CMEDD，RMCRW和LEACH三種算法的首節(jié)點死亡輪數(shù)分別為31，28和23，即CMEDD算法首節(jié)點死亡輪數(shù)較LEACH和RMCRW分別提高了34.8%和10.7%。說明本算法對網(wǎng)絡密度具有較好的適應性。綜合分析圖1，圖2可以看出，CMEDD算法節(jié)點生命曲線與LEACH和RMCRW相比較而言坡度較大，說明節(jié)點能耗更為均衡。

當網(wǎng)絡節(jié)點分別為100和200時，CMEDD算法與LEACH和RMCRW算法節(jié)點的能量消耗曲線如圖3，圖4所示。

分析圖3，圖4可知，初始階段三者能耗差別較小，但隨著運行輪數(shù)的增加，CMEDD算法的節(jié)點存活數(shù)目及平均能量逐漸高于LEACH和RMCRW算法，即CMEDD算法對網(wǎng)絡密度具有良好適應性。

4 結(jié) 語

本文提出了基于能量、距離及節(jié)點度的非變換分簇的一種能耗均衡的路由算法（CMEDD）。算法給出了分簇方式、簇頭選擇公式及簇間路由形式，首輪由基站選擇簇頭，第2輪以后利用基于節(jié)點的剩余能量、節(jié)點到基站以及到其他節(jié)點之間的平均距離和節(jié)點的度3項參數(shù)的閾值公式選取簇頭；數(shù)據(jù)傳輸階段簇頭根據(jù)代價因子選擇中繼節(jié)點，從而實現(xiàn)單、多跳結(jié)合的路由方式，降低網(wǎng)絡能耗。仿真實驗及對比表明，CMEDD算法能夠有效均衡網(wǎng)絡能耗、延長網(wǎng)絡生命周期。

CMEDD算法在均衡網(wǎng)絡能耗方面有一定優(yōu)勢，但是仍然存在一些問題，如在網(wǎng)絡運行中簇頭進行數(shù)據(jù)融合的高效性以及在較大網(wǎng)絡中算法的安全性和可擴展性都有待進一步的研究。

參考文獻

[1] HEINZELLNAN 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] KUBISCH M， KARL H， WOLISZ A， et al. Distributed algorithm for transmission power control in wireless sensor networks [C]// Proceedings of the 2003 IEEE Wireless Communications Networking. Washington，USA： IEEE Communications Society， 2003： 16?20.

[3] BAI L， ZHAO L， LIAO Z. Energy balance in cooperative wireless sensor networks [C]// Proceedings of the 14th European wireless conference. Prague， Czech Republic： IEEE， 2008： 143?145.

[4] LI Y L， DING L W， LIU F. The improvement of LEACH protocol in WSN [C]// Proceedings of the 2011 International Conference on Computer Science and Network Technology. Harbin， China： IEEE， 2011： 1345?1348.

[5] AKYILDIZ I F， SANKARASUBRAMANIAM Y， SU W， et al. A survey on sensor networks [J]. Proc IEEE Communications Magazine， 2007， 40（8）： 102?114.

[6] ENAMI N， MOGHADAM R A， DADASHTABAR K. Neural network based energy efficiency in wireless sensor networks： A survey [J]. International Journal of Computer Science & Engineering Survey， 2010： 1（1）： 39?53.

[7] 白鳳娥，王莉莉，馬艷艷，等.無線傳感器網(wǎng)絡路由協(xié)議LEACH的算法分析[J].太原理工大學學報，2009，40（4）：348?352.

[8] 張詩悅，吳建德，王曉東，等.一種能耗均衡的無線傳感器網(wǎng)絡分簇路由算法[J].計算機工程，2014，40（8）：6?9.

[9] 魯松，徐文春，楊云.一種分環(huán)多跳的無線傳感器網(wǎng)絡分簇路由加權算法[J].山東大學學報：工學版，2012，42（4）：24?28.

[10] CHANDRAKASAN A， REX M， BHARDWAJ M， et al. Power aware wireless microsensor systems [C]// Proceedings of the 32nd European Solid?State Device Research Conference. [S.l.]： IEEE， 2002： 47?54.

[11] 沈夢南，耿生玲，劉震.基于LEACH的無線傳感器網(wǎng)絡混合優(yōu)化協(xié)議算法[J].計算機應用，2014，34（8）：2148?2154.

[12] 陳炳才，么華卓，楊明川，等.一種基于LEACH協(xié)議改進的簇間多跳路由協(xié)議[J].傳感技術學報，2014，27（3）：373?377.