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

張巖

（西安文理學院信息工程學院 陜西 西安　710065）

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

張巖

（西安文理學院信息工程學院 陜西 西安710065）

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

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

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

1LEACH協(xié)議

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

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

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

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

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

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

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

2.1LEACH協(xié)議不足

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

2.2LEACH協(xié)議改進

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

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

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

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

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

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

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

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

3　算法仿真與性能驗證

3.1能耗模型

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

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

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

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

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

3.3性能測試與分析

LEACH算法與LEACH-bop算法在網絡生命周期內每一輪能量消耗如圖1所示。

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

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

3.4對網絡密度的適應性分析

將網絡節(jié)點數(shù)擴展為N=200。對LEACH-bop算法、LEACH算法及基于LEACH的改進算法LEACH-EI算法進行對比。

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

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

4　結束語

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

[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]馬杰良，王垚，顧蕾蕾.基于覆蓋率的無線傳感器網絡LEACH協(xié)議研究及改進[J].傳感技術學報，2011，24（12）:1777-1781.

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

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

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

[8]胡星華，駱堅，譚珊珊，等.固定簇的LEACH半徑自適應簇頭改進算法[J].傳感技術學報，2011，24（1）:79-82.

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

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

[11]張飛鴿.LEACH協(xié)議簇頭個數(shù)優(yōu)化的研究[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

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

張 巖（1982—），女，陜西藍田人，碩士研究生，講師。研究方向：無線傳感器網絡。