一種基于優先級的LEACH算法改進及仿真

張巖

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

一種基于優先級的LEACH算法改進及仿真

張巖

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

針對傳統協議LEACH在簇頭分布、簇頭選取及數據傳輸等方面存在的不足，提出一種基于優先級的算法對LEACH協議簇頭選舉公式及簇頭分布位置加以改進，保證簇頭分布均勻并且處于網絡節點密集區域，達到均衡能耗的目的；數據傳輸階段采用單、多跳結合的方式平衡網絡負載。仿真結果表明，與LEACH及LEACH-EI相比，本文算法有效延長了網絡生命周期。

無線傳感器網絡；鄰居節點；能量優先；網絡生命周期

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

1LEACH協議

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

1.1LEACH協議簇頭選舉和簇的建立

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

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

1.2數據通信

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

2　LEACH協議不足及改進

2.1LEACH協議不足

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

2.2LEACH協議改進

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

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

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

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

2.2.2數據傳輸方案

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

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

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

3　算法仿真與性能驗證

3.1能耗模型

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

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

3.2仿真環境設定

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

表1　仿真模型參數取值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

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

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

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

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

圖2　網絡節點數擴展后3種算法能耗對比

4　結束語

文中提出了基優先級的分簇路由算法（LEACH-bop）。此算法采用鄰居節點數、節點當前能量等屬性確定簇頭[11]，給出了分簇方式和基于優先級的簇頭選擇公式，每輪初始階段均按照優先級策略生成一個最具優先條件的簇頭，隨后在規定范圍之外以同樣的方式再選出其余的簇頭[11]，這既保證了簇頭節點分布的均衡性又兼顧了當選簇頭的節點的能量及位置的優先性，即在簇頭分布均勻的基礎上使得其鄰居節點多且能量優先；路由方式采用單、多跳結合降低網絡能耗。仿真實驗及對比表明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協議研究及改進[J].傳感技術學報，2011，24（12）:1777-1781.

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

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

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

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

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

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

[11]張飛鴿.LEACH協議簇頭個數優化的研究[J].計算機與現代化，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—），女，陜西藍田人，碩士研究生，講師。研究方向：無線傳感器網絡。