黃真金 李道全 張俊虎2

摘要：針對LEACH協(xié)議中簇首分布不均勻和節(jié)點能量消耗不均衡的問題，為了提高節(jié)點能量利用率，延長網(wǎng)絡(luò)運行周期，提高節(jié)點在網(wǎng)絡(luò)運行過程中的存活率，提出了一種LEACH-NE改進算法。該算法綜合考慮節(jié)點到基站的距離及節(jié)點的剩余能量等因素確定最佳簇首個數(shù)，然后通過考慮能量因素來優(yōu)化簇首選擇。仿真結(jié)果證明了改進后的路由協(xié)議在網(wǎng)絡(luò)運行周期和網(wǎng)絡(luò)能量消耗方面優(yōu)于LEACH協(xié)議。

關(guān)鍵詞：無線傳感器網(wǎng)絡(luò)；路由協(xié)議；網(wǎng)絡(luò)運行周期；能量消耗；最佳簇首個數(shù)；簇首選擇

中圖分類號：TP393 文獻標識碼：A 文章編號：1009-3044（2014）06-1216-04

Improved Routing Protocol Based on LEACH in WSN

HUANG Zhen-jin1， LI Dao-quan1， ZHANG Jun-hu2

（1.College of Computer Engineering， Qingdao Technological University， Qingdao 266033， China； 2.College of Information Science and Technology， Qingdao University of Science and Technology， Qingdao 266044， China）

Abstract： In view of the uneven distribution of cluster head nodes of LEACH agreement energy imbalance problems， in order to improve the utilization efficiency of node energy， prolong the network operation cycle， improve the survival rate in the process of nodes in the network operation， puts forward a improved algorithm LEACH - NE. The distance of the node to the base station considered in the algorithm and the residual energy of nodes factors determine the optimal number of cluster head， then by considering the energy factor to optimize selection of cluster head. The simulation results proved that the improved routing protocol in network operation cycle is better than that of LEACH agreement and the network energy consumption.

Key words： wireless sensor network （WSN）； routing protocols； the network operation cycle； energy consumption； optimal number of cluster head； selection of cluster head

無線傳感器網(wǎng)絡(luò)（WSN）路由協(xié)議按網(wǎng)絡(luò)拓撲結(jié)構(gòu)可以分成平面路由協(xié)議和分層路由協(xié)議。LEACH（low energy adaptive clustering hierarchy）協(xié)議即低功耗自適應(yīng)聚類路由協(xié)議屬于WSN路由協(xié)議的一個分層路由協(xié)議。LEACH協(xié)議隨機選擇節(jié)點做簇首，平均分擔(dān)整個網(wǎng)絡(luò)中的中繼通信業(yè)務(wù)，最終達到平均消耗傳感器網(wǎng)絡(luò)中節(jié)點能量的目的，這種協(xié)議方式延長了網(wǎng)絡(luò)的生命周期。但是，由于它僅考慮了選擇簇首時的公平性，沒有把簇首的剩余能量等因素考慮在內(nèi)，因此容易導(dǎo)致網(wǎng)絡(luò)節(jié)點能耗不均，對整個無線傳感器網(wǎng)絡(luò)的存活周期造成影響。

針對LEACH協(xié)議存在的不足，該文對LEACH協(xié)議進行了改進，該LEACH-NE算法在簇首選擇時，綜合考慮節(jié)點的剩余能量和節(jié)點到基站的不同通信距離等因素，簇首與基站之間采用多跳方式進行數(shù)據(jù)傳輸。改進后的算法不僅提高了節(jié)點能量利用率，降低了節(jié)點能耗，而且延長了網(wǎng)絡(luò)運行周期，均衡了網(wǎng)絡(luò)的負載。

1 LEACH協(xié)議概述

1.1 工作過程

LEACH協(xié)議操作分為簇形成階段和數(shù)據(jù)通信穩(wěn)定工作階段，兩個階段時間總和稱為一輪（簡記“r”，round）。在簇建立階段，隨機選擇簇首，相鄰節(jié)點動態(tài)地加入簇首成簇；簇形成后進入穩(wěn)定數(shù)據(jù)通信工作階段，簇首開始采集簇內(nèi)節(jié)點數(shù)據(jù)，然后對數(shù)據(jù)進行融合，將融合后的數(shù)據(jù)傳輸給基站。

簇首選舉過程如下：節(jié)點隨機產(chǎn)生一個0～1的隨機數(shù)，如果該值小于閾值[T（n）]，則發(fā)布自己是簇首的消息。[T（n）]表示為

[T（n）=p1-p[rmod（1p）]，n∈G0 ，n?G]

其中：[p]是簇首數(shù)占總節(jié)點數(shù)的百分比，[r]是當(dāng)前選舉的輪數(shù)， [G]是在最近[1p]輪中未當(dāng)選過簇首的節(jié)點集合，[n]為節(jié)點標號。

節(jié)點當(dāng)選為簇首后發(fā)布給其他節(jié)點自己是新簇首的廣播消息，然后非簇首節(jié)點通過自己與簇首之間的距離來選擇加入哪個簇，當(dāng)簇首接收到所有加入信息后，就產(chǎn)生一個TDMA定時消息，為本簇節(jié)點安排工作時間。

1.2 LEACH協(xié)議存在的問題

1） LEACH中隨機選擇簇首，未考慮每個節(jié)點的剩余能量，這樣就存在剩余能量少的節(jié)點有可能當(dāng)選簇首，從而加速了該節(jié)點的死亡，進而降低了網(wǎng)絡(luò)壽命。

2） LEACH協(xié)議假設(shè)所有的節(jié)點都能直接與基站通信，離基站距離較遠的簇首可能能量消耗會比較快，這樣會造成網(wǎng)絡(luò)的覆蓋范圍和生存時間受到影響。因此，LEACH協(xié)議在監(jiān)測范圍大的無線傳感器網(wǎng)絡(luò)中不適用。

2 LEACH-NE協(xié)議

新協(xié)議綜合考慮每個節(jié)點的剩余能量和整個網(wǎng)絡(luò)的平均能量，篩選出剩余能量大于或等于網(wǎng)絡(luò)平均能量的節(jié)點，再調(diào)整簇首閥值[T（n）]，提高能量較大者成為簇首的可能性，從而保證各網(wǎng)絡(luò)節(jié)點能耗負載的均衡。

2.1 最佳簇首個數(shù)的確定

2.1.1 最優(yōu)簇首數(shù)計算公式

假定整個網(wǎng)絡(luò)能耗模型在距離[d]上發(fā)送一條長度[k]比特消息的能耗為[ET]，[Ee]為單位比特數(shù)據(jù)在發(fā)射或接收電路中的能耗，[εfs]和[εmp]分別為自由空間模型和多路徑衰減模型下的功率放大損耗，則[ET]的計算公式為：

[ET（k，d）=Ebr（k）+Etx-amp（k，d）=kEe+kεfsd2，d

其中：當(dāng)傳輸距離[d

多徑衰落模型是指在信號的傳播過程中，由于受地面條件的影響，會產(chǎn)生多個經(jīng)過不同路徑到達接收基站的信號，通過矢量疊加后合成時變信號的傳播模型，多徑衰落模型的使用適用于簇成員節(jié)點和簇首節(jié)點之間的距離較遠的情形；自由空間傳播模型是無線電波傳播模型的一種，適用于簇成員節(jié)點和簇首節(jié)點之間距離較近的情形。

假設(shè)整個傳感器網(wǎng)絡(luò)分布在一個[Y×Y]的區(qū)域中，一共有[X]個傳感器節(jié)點，將這些節(jié)點分為[M]個簇，每個分簇有[N]個節(jié)點，設(shè)群首給成員節(jié)點發(fā)送信號能耗記為[ES]、群首接收信號能耗記為[ER]、群首將信號發(fā)送給基站能耗記為[EF]。每個簇首節(jié)點所消耗的能量[ECH]為：

[ECH=ES+EF+ER]

在簇首向基站發(fā)送數(shù)據(jù)時，引入了多跳數(shù)據(jù)傳輸機制，讓距離基站較近的簇首適當(dāng)承擔(dān)一些數(shù)據(jù)中繼轉(zhuǎn)發(fā)任務(wù)，變直接長距離通信為間接多次短距離通信，簇首采用自由空間模型給中繼節(jié)點發(fā)送數(shù)據(jù)，設(shè)距離為[d1]，由公式（1）可知：

[Es=kEe+kεfsd12]

設(shè)[EDA]為融合一個比特數(shù)所消耗的能量，[k]為每條數(shù)據(jù)消息的比特數(shù)，則在數(shù)據(jù)完全累計的情況下簇首累積所消耗的能量EF計算公式為： [EF=kEDAN]

簇首節(jié)點接收成員節(jié)點消耗能量ER計算公式為： [ER=kEe（N-1）]

因此，任一簇首節(jié)點所消耗的能量[ECH]計算公式為：

[ECH=kEe+kεfsd12+kEDAN+kEe（N-1）=k（Ee+EDA）N+kεfsd12] （2）

簇首節(jié)點到成員節(jié)點的距離不遠，設(shè)距離為[d2]，得到每個非簇首節(jié)點的耗能[Enon-CH]計算公式為：

[Enon-CH=kEe+kεfsd22] （3）

在傳感器場離基站較遠的情況下，假定簇首節(jié)點需要經(jīng)過[t]跳才能到達基站，在多跳的過程中進行數(shù)據(jù)累積。每跳距離相等用表示[z]，即有[d2=z]。則Sink節(jié)點把消息傳遞到基站的能耗[EH]計算公式為：

[EH=（t-1）[kEe+（kEe+kεfsz2）+2kEDA]] （4）

假設(shè)一個簇的面積：[S=πR2=NY2X?R=NXπY]，設(shè)[ρ（x，y）]為每個簇中傳感器節(jié)點的分布密度，其值為：[ρ（x，y）=XNY2]，令[x=rcosθ，y=rsinθ]，得到非簇首節(jié)點到達其簇首節(jié)點的平方距離期望值為：

[E[d22]=S（x2+y2）ρ（x，y）dxdy=r2ρ（r，θ）rdrdθ=ρ02πr=0r=NXπYr3drdθ=NY22πX]

代入（3）式得： [Enon-CH=kEe+kεfsY2N2πX]

其中[N=XM]，那么最差情況下整個網(wǎng)絡(luò)的能量消耗為：

[Etotol=[（N-1）Enon-CH+EH+ECH]M] （5）

將（2），（3），（4）代入（5）式并由[dEtotaldM=0]確定最佳簇首的個數(shù)：

[kopt=Y2X/2π×εfs/2（t-1）（Ee+EDA）-Ee+tεfsz2]

2.2 LEACH-NE簇首選擇策略的改進

在選擇簇首之前，記[Ec]為每個節(jié)點的剩余能量，基站在每一輪初始階段，計算全網(wǎng)的平均能量記為[Eav]，當(dāng)前網(wǎng)絡(luò)中[m]個存活節(jié)點的剩余能量之和記為[Eto]，則有[Eav=Etom]，有資格成為簇首的節(jié)點需滿足： [Ec≥Eav]

為了在此基礎(chǔ)上選取能量較大者成為簇首，需將節(jié)點剩余能量和網(wǎng)絡(luò)的總能量等因素考慮進來，調(diào)整閥值[T（n）]可修改為：

[T（n）=p1-prmod（1p）×maxkoptm×EcEav，1，n∈G0 ， n?G]

改進后的簇首選擇策略，使得剩余能量較大的節(jié)點具有更大的簇首閥值，增加其成為簇首的可能性，使得選擇簇首的策略更加合理，更好的保證了網(wǎng)絡(luò)負載的均衡，因此，簇首個數(shù)選取在最佳范圍內(nèi)可以提高網(wǎng)路性能。

3 仿真實驗數(shù)據(jù)分析

本文基于Matlab軟件平臺對LEACH、LEACH-NE算法進行了仿真實驗，參數(shù)設(shè)置如下：100個傳感器節(jié)點隨機分布于一個100 m[×]100 m的傳感器場中，Sink節(jié)點位于（50，50），每個節(jié)點的初始能量為0.5 J，。仿真實驗中的通信能量參數(shù)設(shè)置如下：[Ee=50×10-9J/bit，εfs=10×10-12J，εmp=0.0013×10-12J，EDA=5×10-9J，]開始100個節(jié)點隨機分布在傳感器場中如圖1所示。

圖1 100個傳感器節(jié)點的分布

從仿真結(jié)果圖2可以看出，LEACH協(xié)議出現(xiàn)第一個死亡節(jié)點時網(wǎng)絡(luò)運行的周期數(shù)低于LEACH-NE協(xié)議出現(xiàn)第一個死亡節(jié)點時網(wǎng)絡(luò)運行的周期數(shù)，LEACH-NE整個網(wǎng)絡(luò)生存時間遠遠大于LEACH的網(wǎng)絡(luò)生存時間。從而可知，新算法不但提高了存活節(jié)點利用率，而且延長了網(wǎng)絡(luò)的生存周期。

圖2 種協(xié)議的網(wǎng)絡(luò)存活節(jié)點數(shù)歲運行時間變化關(guān)系

圖3顯示的是改進后的LEACH-NE剩余能量節(jié)點圖和原有的LEACH協(xié)議剩余能量節(jié)點圖隨運行周期變化的曲線。由圖可知，在整個網(wǎng)絡(luò)運行相同周期數(shù)的情形下，LEACH-NE協(xié)議的剩余能量節(jié)點數(shù)目比LEACH剩余能量節(jié)點數(shù)目要多，提高了節(jié)點能量利用率。

圖3 剩余能量節(jié)點隨運行周期變化關(guān)系

4 結(jié)束語

本文針對LEACH協(xié)議在選擇簇首策略方面存在的不足，提出一種新的改進路由協(xié)議LEACH-NE.該協(xié)議在確定最優(yōu)簇首數(shù)的基礎(chǔ)上綜合考慮節(jié)點的剩余能量和整個網(wǎng)絡(luò)的平均能量等因素來達到優(yōu)化簇首選擇的目的，同時在數(shù)據(jù)通信的過程中，并且采用了單跳和多跳相結(jié)合的簇首間通信機制。仿真結(jié)果證明，新改進后的LEACH-NE協(xié)議在節(jié)點能量利用率，網(wǎng)絡(luò)生存周期方面相對于LEACH協(xié)議都有較大的提高。

參考文獻：

[1] Heinzelmam W B. An Application-specific Protocol Architecture for Wireless Microsensor Networks[J].IEEE Trans. on Wireless Communications，2002，4（1）：660-670.

[2] Heinzelmam W R.Energy-efficient Comunication Protocol for Wireless Microsensor Networks[C]//Proceedings of the 33rd Internationl Conference on System Sciences.Hawaii，USA：IEEE Computer Society ，2000：1-10.

[3] Heinzelman W R，Chandrakasan A，Balakrishnan H. An application-specific protocol architecture for wireless microsensor networks[J].IEEE Transactions on Wireless Communications，2002，1（4）：660-670.

[4] 李振科，陳國定，王淑華.基于LEACH協(xié)議的改進路由算法[J].計算機應(yīng)用，2009，29（z2）：63-65.

[5] 孫利民，李建中，陳渝，等.無線傳感器網(wǎng)絡(luò)[M].北京：清華大學(xué)出版社，2005.

[6] 陳林星.無線傳感器網(wǎng)絡(luò)技術(shù)與應(yīng)用[M].北京：電子工業(yè)出版社，2009.

[7] 胡剛.無線傳感器網(wǎng)絡(luò)路由協(xié)議LEACH的研究與改進[J].傳感器學(xué)報，2007，20（6）：1391-1396.

[8] 柳平，陳歡，石中華，呂金鳳.基于LEACH協(xié)議的改進路由算法[J].測試技術(shù)學(xué)報，2012，26（5）：417-421.

[9] 劉愛東，盧忠武，劉德浩.基于LEACH的低功耗路由協(xié)議研究[J].計算機工程與應(yīng)用， 2012，48（24）：88-90.