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

張巖

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

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

中圖分類號(hào)： TN711?34； TP393 文獻(xiàn)標(biāo)識(shí)碼： A 文章編號(hào)： 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)絡(luò)中，傳感器節(jié)點(diǎn)多采用能量有限的電池供電，使得整個(gè)網(wǎng)絡(luò)對(duì)數(shù)據(jù)的存儲(chǔ)處理和傳輸能力受到了限制。所以如何有效使用傳感器節(jié)點(diǎn)能量，以及如何延長(zhǎng)網(wǎng)絡(luò)的生命周期就成為設(shè)計(jì)無線傳感器網(wǎng)絡(luò)路由協(xié)議的一個(gè)重點(diǎn)，其中從管理的角度上對(duì)網(wǎng)絡(luò)進(jìn)行層次化管理是目前該領(lǐng)域的一個(gè)研究熱點(diǎn)。

文獻(xiàn)[1]提出了無線傳感網(wǎng)拓?fù)淇刂频湫偷牡凸淖赃m應(yīng)算法LEACH，與平面拓?fù)渌惴ㄏ啾?，該協(xié)議可以延長(zhǎng)網(wǎng)絡(luò)生命期約30%。但是LEACH 算法沒有考慮能量不平衡問題，存在很大改進(jìn)空間。

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

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

1 網(wǎng)絡(luò)模型

1.1 本文采用的節(jié)點(diǎn)模型假設(shè)如下：

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

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

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

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

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

1.2 能耗模型

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

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

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

2 CMEDD算法描述

2.1 簇頭選擇

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

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

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

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

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

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

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

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

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

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

2.2 簇間路由

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

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

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

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

3 算法仿真與性能驗(yàn)證

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

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

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

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

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

4 結(jié) 語

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

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

參考文獻(xiàn)

[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)絡(luò)路由協(xié)議LEACH的算法分析[J].太原理工大學(xué)學(xué)報(bào)，2009，40（4）：348?352.

[8] 張?jiān)姁偅瑓墙ǖ?，王曉東，等.一種能耗均衡的無線傳感器網(wǎng)絡(luò)分簇路由算法[J].計(jì)算機(jī)工程，2014，40（8）：6?9.

[9] 魯松，徐文春，楊云.一種分環(huán)多跳的無線傳感器網(wǎng)絡(luò)分簇路由加權(quán)算法[J].山東大學(xué)學(xué)報(bào)：工學(xué)版，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] 沈夢(mèng)南，耿生玲，劉震.基于LEACH的無線傳感器網(wǎng)絡(luò)混合優(yōu)化協(xié)議算法[J].計(jì)算機(jī)應(yīng)用，2014，34（8）：2148?2154.

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