張巖

（西安文理學(xué)院信息工程學(xué)院 陜西 西安　710065）

一種基于優(yōu)先級的LEACH算法改進(jìn)及仿真

張巖

（西安文理學(xué)院信息工程學(xué)院 陜西 西安710065）

針對傳統(tǒng)協(xié)議LEACH在簇頭分布、簇頭選取及數(shù)據(jù)傳輸?shù)确矫娲嬖诘牟蛔悖岢鲆环N基于優(yōu)先級的算法對LEACH協(xié)議簇頭選舉公式及簇頭分布位置加以改進(jìn)，保證簇頭分布均勻并且處于網(wǎng)絡(luò)節(jié)點密集區(qū)域，達(dá)到均衡能耗的目的；數(shù)據(jù)傳輸階段采用單、多跳結(jié)合的方式平衡網(wǎng)絡(luò)負(fù)載。仿真結(jié)果表明，與LEACH及LEACH-EI相比，本文算法有效延長了網(wǎng)絡(luò)生命周期。

無線傳感器網(wǎng)絡(luò)；鄰居節(jié)點；能量優(yōu)先；網(wǎng)絡(luò)生命周期

低功耗自適應(yīng)分簇算法LEACH［1］是由麻省理工大學(xué)Heinzelman W.R等人于1999年提出的，它是無線傳感器網(wǎng)絡(luò)的一種分簇路由協(xié)議，更是具代表性的層次管理算法。LEACH算法通過周期性選擇簇頭使得各節(jié)點等概率地?fù)?dān)任簇頭，從而相對均衡了網(wǎng)絡(luò)中節(jié)點能量消耗。本文詳細(xì)分析了LEACH算法的工作原理，并針對其在簇頭選舉及數(shù)據(jù)傳輸方面的不足提出改進(jìn)并進(jìn)行仿真。

1LEACH協(xié)議

LEACH協(xié)議下，網(wǎng)絡(luò)中所有節(jié)點以隨機(jī)的方式輪流成為簇頭節(jié)點，非簇頭節(jié)點就近加入相應(yīng)的簇，網(wǎng)絡(luò)中各節(jié)點將所采集數(shù)據(jù)傳輸給簇頭，簇頭進(jìn)行數(shù)據(jù)融合后再將數(shù)據(jù)包發(fā)送給基站。

1.1LEACH協(xié)議簇頭選舉和簇的建立

依據(jù)所需簇頭比例和節(jié)點是否承擔(dān)過群頭來決定。每輪初時，節(jié)點產(chǎn)生一個[0，1]之間的隨機(jī)數(shù)，次隨機(jī)數(shù)如果小于閾值T（n），則此節(jié)點成為本輪工作的簇頭；反之，皆為普通節(jié)，當(dāng)選簇頭的公式為：

其中，P是網(wǎng)絡(luò)中簇頭節(jié)點所占的比例，r是當(dāng)前運行輪數(shù)，G是本輪未當(dāng)選簇頭的節(jié)點集合。簇頭節(jié)點確立后，即廣播此消息，普通節(jié)點通過所接收到的信號強(qiáng)弱程度發(fā)送加入最近的簇的請求。簇頭節(jié)點為本簇成員建立時隙表并公布。

1.2數(shù)據(jù)通信

簇內(nèi)各節(jié)點在各自時隙內(nèi)將感知數(shù)據(jù)發(fā)送至所屬簇頭，數(shù)據(jù)如果在一個時隙未發(fā)送完，則下一時隙繼續(xù)發(fā)送。簇頭節(jié)點將來自本簇的數(shù)據(jù)進(jìn)行壓縮及融合，進(jìn)而將處理后的數(shù)據(jù)傳給基站。整個過程為一個穩(wěn)定的通信階段[2-3]。

2　LEACH協(xié)議不足及改進(jìn)

2.1LEACH協(xié)議不足

LEACH協(xié)議簇頭選舉完全依賴所產(chǎn)生的隨機(jī)數(shù)，對節(jié)點的剩余能量、分布位置等屬性并未考慮在內(nèi)，導(dǎo)致某些節(jié)點能耗過快；簇頭與基站直接通信導(dǎo)致網(wǎng)絡(luò)中較基站距離遠(yuǎn)的節(jié)點容易出現(xiàn)能量空洞。

2.2LEACH協(xié)議改進(jìn)

根據(jù)LEACH算法簇頭選取及數(shù)據(jù)傳輸方式的缺陷，本文提出一種基于優(yōu)先級的分簇路由方式 LEACH-bop對LEACH算法加以改進(jìn)。

2.2.1LEACH-bop算法簇頭分布及選取方案

為保證簇頭節(jié)點的分布比較均勻，規(guī)定任意兩個簇頭之間的距離應(yīng)大于常數(shù)ds。此方案具體實施為：所有節(jié)點以ds/2為半徑發(fā)布一個信息[4]，用以統(tǒng)計出自己的鄰居節(jié)點數(shù)m，則簇頭選取公式為：

其中，mn為節(jié)點n的鄰居節(jié)點數(shù)，N為網(wǎng)絡(luò)中節(jié)點總數(shù)，En（t）為n的當(dāng)前能量，Eavg（t）為網(wǎng)絡(luò)中節(jié)點平均能量。公式（2）認(rèn)為m數(shù)最大且當(dāng)前能量較大的節(jié)點首先成為本輪工作的一個簇頭，進(jìn)而在距離此簇頭ds外按此公式產(chǎn)生其它簇頭，既保證節(jié)點分布密集區(qū)域存在簇頭節(jié)點并且簇頭分布均勻，又考慮到簇頭節(jié)點當(dāng)前能量較大。

2.2.2數(shù)據(jù)傳輸方案

與LEACH算法相似簇內(nèi)普通節(jié)點在各自時隙內(nèi)單跳向簇頭發(fā)送數(shù)據(jù)，簇頭向基站發(fā)送數(shù)據(jù)的方式LEACH-bop算法作以下改進(jìn)。

網(wǎng)絡(luò)中的簇頭節(jié)點與普通節(jié)點一樣也有傳輸半徑dcrosscover，當(dāng)傳輸距離大于此值時，需要重新調(diào)整（即增大）發(fā)射功率。工作中當(dāng)簇頭選取完畢則有G={V，E}，V={v1，v2，…，vk}，V為簇頭集，則距離基站較遠(yuǎn)的簇頭結(jié)點直接向基站發(fā)送數(shù)據(jù)能量會損失較快，不利于網(wǎng)絡(luò)能量均衡，在簇頭向基站傳輸數(shù)據(jù)時就存在簇間通信路徑的選擇，假定在一個網(wǎng)絡(luò)中均為簇頭，為vi到基站的距離。則簇間數(shù)據(jù)傳輸方案按以下模型:

滿足公式（3）的vi節(jié)點可作為vj的中轉(zhuǎn)節(jié)點，vj向vi發(fā)送數(shù)據(jù)符合自由空間模型，總體能量消耗遠(yuǎn)小于多路衰減模型，減小了距基站較遠(yuǎn)的簇頭的能耗，更均衡了鏈路能耗。LEACH-bop算法節(jié)點與簇頭的通信仍采用單跳的方式，非簇頭節(jié)點在相應(yīng)時隙內(nèi)以單跳方式直接將數(shù)據(jù)傳送給相應(yīng)的簇頭，簇頭選擇單跳或多跳方式與基站通信[5-6]。

3　算法仿真與性能驗證

3.1能耗模型

采用文獻(xiàn)[1]中無線電通信模型。即節(jié)點發(fā)出大小為lbit的信息所消耗的能量為：

Eelec為單位bit數(shù)據(jù)收發(fā)能耗，dcrossove為模型劃分閾值，大于 dcrossove選擇多路衰減模型， 其功放能耗為 Eamp，小于 dcrossove選擇自由空間模型，其功放能耗為Efs，N為節(jié)點總數(shù)，M網(wǎng)絡(luò)監(jiān)測區(qū)域邊長[7-8]。

3.2仿真環(huán)境設(shè)定

仿真實驗在MATLAB環(huán)境下進(jìn)行，以隨機(jī)方式在監(jiān)測區(qū)域內(nèi)部署傳感器節(jié)點，假設(shè)節(jié)點分布在坐標(biāo)為到的區(qū)域內(nèi)。實驗中仿真參數(shù)取值如表1所示。

表1　仿真模型參數(shù)取值Tab.1　Paramters’figures of the simulation model

3.3性能測試與分析

LEACH算法與LEACH-bop算法在網(wǎng)絡(luò)生命周期內(nèi)每一輪能量消耗如圖1所示。

圖1　兩種算法能耗對比Fig.1　The comparison of two algorithms for energy consumption

仿真結(jié)果顯示，模擬環(huán)境與初始能量相同時LEACH算法[9]運行7輪，第8輪出現(xiàn)節(jié)點能量耗盡；而LEACH-bop算法運行12輪左右開始出現(xiàn)能量耗盡的節(jié)點。LEACH-bop算法首節(jié)點死亡輪數(shù)較LEACH算法有明顯延長，并且由圖可見LEACH原算法在前7輪中網(wǎng)絡(luò)能耗均小于LEACH-bop算法，從第8輪以后能量衰減明顯較快，說明LEACH算法在每一輪的工作中考慮到了總能量最小，而缺乏對各個節(jié)點能耗的考慮。而LEACH-bop算法前期每一輪能耗都比原算法高，但是此算法各節(jié)點能耗相差較小[10]，由仿真結(jié)果可見能耗變化趨勢較為平緩，即網(wǎng)絡(luò)中各節(jié)點能耗較為均衡。

3.4對網(wǎng)絡(luò)密度的適應(yīng)性分析

將網(wǎng)絡(luò)節(jié)點數(shù)擴(kuò)展為N=200。對LEACH-bop算法、LEACH算法及基于LEACH的改進(jìn)算法LEACH-EI算法進(jìn)行對比。

圖2顯示LEACH-bop算法首節(jié)點能量耗盡是第27輪，LEACH的算法是18輪，LEACH-EI算法是23輪。即網(wǎng)絡(luò)節(jié)點數(shù)擴(kuò)展后，LEACH-bop算法與LEACH算法相比首節(jié)點死亡時的網(wǎng)絡(luò)生命周期延長了約49%；與LEACH-EI相比，首節(jié)點死亡時的網(wǎng)絡(luò)生命周期延長了約17%。即LEACH-bop

圖2　網(wǎng)絡(luò)節(jié)點數(shù)擴(kuò)展后3種算法能耗對比

4　結(jié)束語

文中提出了基優(yōu)先級的分簇路由算法（LEACH-bop）。此算法采用鄰居節(jié)點數(shù)、節(jié)點當(dāng)前能量等屬性確定簇頭[11]，給出了分簇方式和基于優(yōu)先級的簇頭選擇公式，每輪初始階段均按照優(yōu)先級策略生成一個最具優(yōu)先條件的簇頭，隨后在規(guī)定范圍之外以同樣的方式再選出其余的簇頭[11]，這既保證了簇頭節(jié)點分布的均衡性又兼顧了當(dāng)選簇頭的節(jié)點的能量及位置的優(yōu)先性，即在簇頭分布均勻的基礎(chǔ)上使得其鄰居節(jié)點多且能量優(yōu)先；路由方式采用單、多跳結(jié)合降低網(wǎng)絡(luò)能耗。仿真實驗及對比表明LEACH-bop算法能夠有效均衡網(wǎng)絡(luò)能耗、延長網(wǎng)絡(luò)生命周期，從整體上提升了網(wǎng)絡(luò)性能。

[1]Heinzellnan W B，Chandrakasan A P，Balakrishnan H.An application-specific protocol architecture for wirelessmicrosensor networks[J].IEEE Transactions on Wireless Communications，2002，1（4）:660-670.

[2]Thein M C M，Thein T.An energy efficient cluster-head selection for wireless sensor networks[C]//2010 International Conference on Intelligent Systems，Modelling andSimulation. 2010:287-291．

[3]Li Y L，Ding L W，Liu F.The improvement of LEACHprotocolin WSN[C]//2011 International Conference on Computer Science and Network Technology，2011（2）:1345-1348.

[4]馬杰良，王垚，顧蕾蕾.基于覆蓋率的無線傳感器網(wǎng)絡(luò)LEACH協(xié)議研究及改進(jìn)[J].傳感技術(shù)學(xué)報，2011，24（12）:1777-1781.

[5]白風(fēng)娥，王莉莉，馬艷艷，等.無線傳感器網(wǎng)絡(luò)路由協(xié)議LEACH的算法分析[J].太原理工大學(xué)學(xué)報，2009，40（4），248-252

[6]畢艷忠，孫利民.傳感器網(wǎng)絡(luò)中的數(shù)據(jù)融合[D].計算機(jī)科學(xué)，2004，31（7）:101-103

[7]黃廷輝，楊旻，崔更申，等.基于LEACH協(xié)議的無線傳感器網(wǎng)絡(luò)密鑰管理路由方案[J].傳感技術(shù)學(xué)報，2014，27（8）: 1143-1146.

[8]胡星華，駱堅，譚珊珊，等.固定簇的LEACH半徑自適應(yīng)簇頭改進(jìn)算法[J].傳感技術(shù)學(xué)報，2011，24（1）:79-82.

[9]韓濤，李訓(xùn)銘.基于靜態(tài)分簇的LEACH算法改進(jìn)研究[J].電子設(shè)計工程，2014（6）:109-112.

[10]李菡薏，陳家琪.云計算環(huán)境下任務(wù)調(diào)度算法的研究[J].電子科技，2015（11）:43-46，60.

[11]張飛鴿.LEACH協(xié)議簇頭個數(shù)優(yōu)化的研究[J].計算機(jī)與現(xiàn)代化，2015（9）:95-99，104.

The improvement and simulation of LEACH algorithm based on the priority

ZHANG Yan
（College of Information Engineering，Xi’an University of Arts and Science，Xi’an 710065，China）

Be aimed at the insufficient in the distribution and selection of the cluster heads，the data transmission of the LEACH protocol，this paper proposes an algorithm that improved the LEACH in the selection and the distribution of Cluster head，which Ensures the distribution of cluster heads are uniform and the cluster heads in the dense regions of nodes in the network；The data transmission adopts the methods of one-hop and Multiple-hop.The simulation results show that compared with LEACH algorithm and LEACH-EI algorithm，the scheme prolongs the life cycle of network effectively.

wireless sensor networks；neighbor node；energy priority；lifecycle of the network

TN915.04

A

1674－6236（2016）01-0077-03

2015-05-08稿件編號：201505071

國家自然科學(xué)基金資助項目（41301413）；西安市科技計劃項目（CXY1443WL19）

張 巖（1982—），女，陜西藍(lán)田人，碩士研究生，講師。研究方向：無線傳感器網(wǎng)絡(luò)。