非變換簇的WSN分簇路由算法

張巖

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

關鍵詞： 無線傳感器網絡； 能耗均衡； 簇頭選取； 網絡生命周期

中圖分類號： 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

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

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

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

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

1 網絡模型

1.1 本文采用的節點模型假設如下：

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

（2） 節點同構且初始能量相等，一經部署其位置不再發生改變；

（3） 節點發送功率可以進行調整，即具有調節無線收發器工作能耗的控制功能；

（4） 節點能夠支持多種MAC協議（如TDMA等）；

（5） 傳感器節點具有足夠的計算能力，即具有一定的數據融合功能。

1.2 能耗模型

節點[l]位的數據包傳送長度為[d]，通信模型為[9]：

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

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

2 CMEDD算法描述

2.1 簇頭選擇

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

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

（1） 節點剩余能量

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

（2） 簇內節點平均距離及節點距基站距離

其次分析節點與簇內其余節點以及與基站之間的距離參數[Dn]：

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

（3） 節點度析節點的度

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

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

2.2 簇間路由

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

假定在網絡中[vi，vj]均為簇頭，則簇頭節點[vj]作為簇頭節點[vi]的下一跳中轉節點的代價因子為：

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

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

3 算法仿真與性能驗證

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

無線傳感器網絡的生命周期著重從首節點能量耗盡所用時間進行考慮。基于這一原因實驗對網絡節點數分別為100，200時三種算法運行期間存活節點數進行仿真，其仿真圖分別如圖1，圖2所示。

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

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

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

4 結 語

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

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

參考文獻

[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] 白鳳娥，王莉莉，馬艷艷，等.無線傳感器網絡路由協議LEACH的算法分析[J].太原理工大學學報，2009，40（4）：348?352.

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

[9] 魯松，徐文春，楊云.一種分環多跳的無線傳感器網絡分簇路由加權算法[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的無線傳感器網絡混合優化協議算法[J].計算機應用，2014，34（8）：2148?2154.

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