WSN中LEACH協(xié)議的改進與研究*

張 浩，趙建平

0 引 言

隨著傳感器技術、嵌入式計算技術、微電子技術和無線通信技術的日趨成熟，無線傳感器網(wǎng)絡（Wireless Sensor Networks，WSN）[1]應 運 而 生，并廣泛應用于軍事、環(huán)境參數(shù)監(jiān)測與采集、智能家居、溫室大棚等領域[2]。無線傳感器網(wǎng)絡是由數(shù)量眾多、體積微小、僅電池供電的傳感器節(jié)點組成，并以自組織方式互相協(xié)同工作的分布式感知網(wǎng)絡。由于傳感器節(jié)點能量有限且大多部署在電池不易更換的環(huán)境中，因此如何均衡網(wǎng)絡能耗、最大程度延長網(wǎng)絡生命周期成為首要問題[3]。路由協(xié)議作為延長網(wǎng)絡生命最有效的方式之一[4]，受到國內外研究人員的廣泛關注。研究表明，層次型路由協(xié)議相比較于平面路由，解決了其建立、維護路由開銷大、信息冗余大、數(shù)據(jù)傳輸跳數(shù)多、網(wǎng)絡規(guī)模小的問題。而LEACH[5]協(xié)議是層次型路由協(xié)議最具代表性的。所以，后續(xù)的一系列協(xié)議都是對LEACH協(xié)議某種程度的改進[6]。

相較于一般的平面多跳路由協(xié)議和靜態(tài)分層算法，LEACH協(xié)議可以將網(wǎng)絡周期延長15%[7]，但尚存在不足，主要體現(xiàn)在：

①LEACH協(xié)議假定所有的節(jié)點都可以與匯聚節(jié)點直接通信，因此該協(xié)議無法在大規(guī)模WSN中應用[8]；

②在簇頭的競選階段沒有考慮當選為簇頭的節(jié)點可能剩余的能量較低，大大縮短了網(wǎng)絡的生命周期[9]；

③沒有考慮簇頭的位置，選出的簇頭可能集中在某一個區(qū)域，導致一些普通節(jié)點周圍沒有任何簇頭節(jié)點。

本文針對無線傳感器網(wǎng)絡LEACH（Low Energy Adaptive Clustering Hierarchy）算法中簇頭隨機選取造成網(wǎng)絡能耗過快、網(wǎng)絡生命周期變短的問題，提出一種基于節(jié)點剩余能量和距離基站距離[10]的簇頭選取算法（LEACH-ED）。實驗驗證結果表明，綜合考慮節(jié)點剩余能量和到基站距離的LEACH-ED算法，相比較于基本的LEACH算法，系統(tǒng)的整體耗能減小，網(wǎng)絡生命周期延長60%，且網(wǎng)絡的擴展性能更好。

1 LEACH協(xié)議概述

LEACH是最早提出的分簇路由協(xié)議，奠定了分簇路由協(xié)議的基本思想。在運行過程中，它不斷執(zhí)行簇的重構過程。重構過程以“輪”為單位[11]，分為兩個階段：簇的建立階段和數(shù)據(jù)傳輸?shù)姆€(wěn)定階段。為了節(jié)省網(wǎng)絡開銷，穩(wěn)定階段的持續(xù)時間要大于建立階段持續(xù)的時間。簇的建立階段主要包括簇頭節(jié)點的選擇、簇頭節(jié)點的廣播、簇頭節(jié)點的建立和調度機制的生成；數(shù)據(jù)傳輸穩(wěn)定階段主要負責數(shù)據(jù)的融合和傳輸。在所有數(shù)據(jù)傳輸完成后，新的一輪開始，網(wǎng)絡需要重新選擇簇頭。

1.1 簇形成過程

1.1.1 簇頭的選擇

每一個傳感器節(jié)點產生一個（0，1）之間的隨機數(shù)，然后與式（1）生成的閾值T(n)進行比較。如果節(jié)點產生的隨機數(shù)小于T(n)，則此節(jié)點可能當選為簇頭。如果最終當選簇頭，則將當選為簇頭的消息廣播告知網(wǎng)絡其他節(jié)點。

式中，p為簇首的比例，r表示網(wǎng)絡當前運行的輪數(shù)，G表示在最后的1/p輪中還沒有成為簇首節(jié)點的集合。在r=0時，每個節(jié)點都以p的概率成為簇頭，經過1/p-1輪后閾值變?yōu)?。

1.1.2 簇的建立

簇頭選舉過程完成后，成為簇頭的節(jié)點廣播自己成為簇頭的消息到整個網(wǎng)絡。該消息主要包括簇頭的ID、位置等。普通節(jié)點根據(jù)接收到消息的強弱選擇強度最大的簇，并向對應的簇頭返回消息，確保加入距離自身最近的簇頭。簇頭根據(jù)簇內包括的節(jié)點個數(shù)，采用TDMA方式為簇中每個節(jié)點分配向其傳輸數(shù)據(jù)的時間點。

在數(shù)據(jù)傳輸穩(wěn)定階段，簇內節(jié)點根據(jù)簇頭分配的數(shù)據(jù)傳輸時間點，定時喚醒。此時，向簇頭傳輸數(shù)據(jù)，其余時間處于休眠狀態(tài)，以便降低耗能。整個過程中，簇頭始終處于開啟狀態(tài)，以接收本簇成員的數(shù)據(jù)。將本簇成員數(shù)據(jù)和自身采集的數(shù)據(jù)融合后，簇頭采用載波偵聽同步CSMA的方式，將融合后的數(shù)據(jù)發(fā)送到匯聚節(jié)點，避免了簇頭同時向匯聚節(jié)點發(fā)送數(shù)據(jù)時的阻塞現(xiàn)象。所有簇首完成數(shù)據(jù)傳送后，新的一輪開始，網(wǎng)絡重新進入簇建立階段。

1.2 網(wǎng)絡能耗模型

LEACH算法的能耗模型定義為：

ETx是發(fā)送k比特數(shù)據(jù)、傳輸距離d的能耗，ERx則是接收k比特數(shù)據(jù)的能耗，Eelec是收發(fā)1 bit數(shù)據(jù)電路消耗的能量，εfs表示自由空間放大器傳播損耗，εmp表示多徑衰減放大器傳輸損耗，d0為常數(shù)且

2 LEACH協(xié)議改進算法

2.1 改進算法網(wǎng)絡模型

改進后的算法采用的無線通信模型與LEACH協(xié)議一致，傳感器節(jié)點隨機分布在已知區(qū)域內，普通傳感節(jié)點能夠感知、采集數(shù)據(jù)并發(fā)送給簇頭節(jié)點，簇頭節(jié)點融合、整理后發(fā)送給匯聚節(jié)點。在設計算法時，同時做以下假設：

①傳感器節(jié)點初始能量相同且有限；

②傳感器節(jié)點和匯聚節(jié)點位置確定后，在剩余網(wǎng)絡周期內不再移動；

③節(jié)點在發(fā)送能量時，能夠自動調整發(fā)射功率以節(jié)省能量；

④匯聚節(jié)點位于已知區(qū)域外。

2.2 改進算法描述

LEACH-ED基于LEACH協(xié)議，考慮加入剩余能量和到匯聚節(jié)點的距離因素后提出的新算法，其中新算法在簇的建立、穩(wěn)定數(shù)據(jù)傳輸階段與最基本的LEACH算法相同，最主要的區(qū)別體現(xiàn)在簇頭選擇和更新過程。思想如下：首先計算基于存活節(jié)點數(shù)的最佳簇頭個數(shù)，假設在當前網(wǎng)絡中有Nr個節(jié)點存活且隨機分布在M×M的區(qū)域內，這塊區(qū)域被平分為K個簇，此時每個簇中含有的節(jié)點個數(shù)為Nr/K（包含一個簇頭節(jié)點和Nr/K-1個普通節(jié)點），則最佳簇頭的個數(shù)就等于所分成的簇數(shù)。根據(jù)節(jié)點的能耗模型，簇頭傳輸l bit的數(shù)據(jù)所消耗的能量為：

每一個簇成員節(jié)點消耗的能量為：

則每一個簇收發(fā)l bit的數(shù)據(jù)時所消耗的最大能耗是：

一幀中，所有的Nr個節(jié)點消耗的總能量為：

設sink節(jié)點的坐標為(x0, y0)，當前節(jié)點的坐標為(xi, yi)，則當前節(jié)點到sink節(jié)點的距離為：

每個簇所占據(jù)的面積約為M2/K，假設是一個簇頭節(jié)點位于簇的中間且密度為ρ(x, y)的任意形狀的區(qū)域。根據(jù)節(jié)點的通信半徑r= M /e，則普通節(jié)點到簇頭節(jié)點的距離為：

對式（9）進行極坐標變換。令x=rsinθ、y=rcosθ，其中，代入得：

將式（8）、式（10）代入式（6），然后再代入式（7），可得整個網(wǎng)絡的總能耗為：

要使整個網(wǎng)絡的能耗最低，將Etotal對K求導并讓其等于零，可得到理想的簇頭數(shù)：

改進后的算法將某一節(jié)點的剩余能量與網(wǎng)絡平均能量的比值作為考慮因素，使剩余能量最大的節(jié)點能夠優(yōu)先競選選為簇頭。選用當前節(jié)點到sink節(jié)點距離與所有活著的節(jié)點到sink節(jié)點較近的節(jié)點優(yōu)先被選舉為簇頭。改進后的T(n)為：

其中 α, β∈(0,1)且 α+β=1，同時有：

通過綜合考慮節(jié)點的剩余能量與網(wǎng)絡的平均能量的比值、到節(jié)點到匯聚節(jié)點的距離與節(jié)點的匯聚節(jié)點的距離的比值，可以使剩余能量大、距離匯聚節(jié)點近的節(jié)點優(yōu)先競選成為簇頭，從而使網(wǎng)絡的能耗更加均衡，延長網(wǎng)絡的生命周期。

3 仿真分析

為了驗證LEACH-ED算法性能是否高于LEACH算法，選擇MATLAB平臺，在100 m×100 m的網(wǎng)絡區(qū)域內隨機分布100個節(jié)點進行仿真。分別從網(wǎng)絡節(jié)點存活數(shù)、死亡數(shù)、數(shù)據(jù)包接收數(shù)等方面，對改進后的算法性能進行評價，參數(shù)設置見表1。

表1 仿真參數(shù)

在一定的環(huán)境下，LEACH-ED算法隨著運行輪數(shù)的增加，網(wǎng)絡中死亡節(jié)點數(shù)目與存活節(jié)點數(shù)目的變化人別如圖1、圖2所示。其中，LEACH算法在2 000輪時出現(xiàn)了大面積死亡，而LEACH-ED算法大面積死亡的時間是3 200輪；在網(wǎng)絡生命周期上，LEACH-ED算法比LEACH延長了60%。LEACH存活的數(shù)目在2 100輪全部死亡，而LEACH-ED存活的時間達到了4 100輪。所以，改進算法提高了節(jié)點的存活率，延長了網(wǎng)絡壽命。

圖1 節(jié)點死亡數(shù)-工作輪數(shù)

圖2 節(jié)點存活數(shù)-工作輪數(shù)

圖3 為基站收到的數(shù)據(jù)包數(shù)與工作輪數(shù)的關系變化曲線?？梢钥闯?，相比LEACH算法，改進后的LEACH—ED算法在相同的輪數(shù)下接收的數(shù)據(jù)包數(shù)大大提升，提高了網(wǎng)絡的工作效率。

圖3 基站收到的數(shù)據(jù)包數(shù)-工作輪數(shù)

圖4 為簇頭數(shù)與工作輪數(shù)的關系變化曲線。從圖4可以看出，在相同的輪數(shù)下，改進的算法簇頭數(shù)更多，簇頭分布更加均勻，均衡了網(wǎng)絡能耗。

圖4 每一輪的簇頭數(shù)-工作輪數(shù)

圖5 為不同LEACH協(xié)議的網(wǎng)絡能耗測試結果。

圖5 能量消耗-工作輪數(shù)

從圖5可知，隨著輪數(shù)不斷增加，兩種LEACH協(xié)議的網(wǎng)絡總能耗逐漸增加；但對于LEACH協(xié)議，LEACH-ED協(xié)議的能耗增加更為緩慢，節(jié)能效果明顯。

4 結 語

本文對無線傳感器分簇路由算法LEACH進行改進，提出了改進后的路由協(xié)議——LEACH-ED。在簇頭競爭階段，LEACH-ED對影響簇頭選舉的閾值進行改進，改進后的閾值綜合考慮了節(jié)點的剩余能量、到基站的距離，使改進后的簇頭選舉更加合理，簇頭分布更加均勻，有效減少了簇頭選舉能耗。仿真結果表明，相比較于LEACH協(xié)議，LEACHED有效均衡了網(wǎng)絡的能量負載，使節(jié)點的存活率更高，延長了網(wǎng)絡的生命周期。

[1] 趙麗霞,紀松波.無線傳感器網(wǎng)絡在智能交通中的應用[J].物聯(lián)網(wǎng)技術,2012,2(06):25-27.ZHAO Li-xia,JI Song-bo.The Application of Wireless Sensor Network in Intelligent Transportation[J].Internet of Things Technology,2012,2(06):25-27.

[2] 孫利民,李建中,陳渝等.無線傳感器網(wǎng)絡[M].北京:清華出版社,2005:1-25.SU Li-min,LI Jian-zhong,CHEN Yu,et al.Wireless Sensor Network[M].Beijing:Tsinghua Press,2005:1-25.

[3] KATIYAR V,CHAND N,GAUTAM,et al.Improvement in LEACH Protocol for Large-scale Wireless Sensor Networks[C].Proceeding of the 2011 Emerging Trends in Electrical and Computer Technology Piscataway,2011:1070-1075.

[4] 石為人,柏蕩,高鵬等.無線傳感器網(wǎng)絡簇頭半徑自適應調節(jié)路由算法[J].儀器儀表報,2012(02):1779-1785.SHI Wei-ren,BAI Dang,GAO Peng,et al.Wireless Sensor Network Cluster Head Radius Adaptive Routing Algorithm[J].Chinese Journal of Scientific Instrument,2012(02):1779-1785.

[5] 王臻躍.基于LEACH的改進路由算法[J].軟件導刊,2015(03):114-116.WANG Zhen-yue.Improved Routing Algorithm based on LEACH[J].Software Guide,2015(03):114-116.

[6] 吳標,余劍.基于節(jié)點剩余能量的分時分簇LEACH改進算法[J].火力與指揮控制,2016(10):84-88,93.WU Biao,YU Jian.The Algorithm of LEACH Improvement based on the Residual Energy of Nodes is Proposed[J].Fire and Command Control, 2016(10):84-88,93.

[7] Nayebi A,Sarbazi-Azad H.Performance Modeling of the LEACH Protocol for Mobile Wireless Sensor Networks[J].J. Parallel Distrib. Comput.,2011(02):4.

[8] Heinzelman W R.Energy-Efficient Communication Protocol for Wireless Microsensor Networks[C].Proceedings of the 33rd Ha-waii International Conference On System Sciences,IEEE Computer Society,2000.

[9] 潘霞,于宏毅,張霞.一種基于LEACH的能耗均衡分簇算法[J].電路與系統(tǒng)學報,2012,17(01):75-80.PAN Xia,YU Hong-yi,ZHANG Xia.A Balanced Clustering Algorithm based on LEACH[J].Journal of Circuits and Systems,2012,17(01):75-80.

[10] 李建坡,鐘鑫鑫,徐純.無線傳感器網(wǎng)絡動態(tài)節(jié)點定位算法綜述[J].東北電力大學學報,2015(35):52-58.LI Jian-po,ZHONG Xin-xin,XU Chun.Wireless Sensor Network Dynamic Node Location Algorithm Overview[J].Journal of Northeast Dianli University,2015(35):52-58.

[11] 過文亮,施惠昌.一種新型的自適應最佳簇首分簇算法[J].微計算機信息,2009,25(02):183-184.GUO Wen-liang,SHI Hui-chang.A Novel Adaptive Optimal Cluster First Clustering Algorithm[J].Microcomputer Information,2009,25(02):183-184.