一種無線傳感器網(wǎng)絡(luò)路由協(xié)議LEACH的改進(jìn)算法

李蘭英++劉昌東

摘 要：針對低功耗自適應(yīng)集簇分層型協(xié)議LEACH（low energy adaptive clustering hierarchy）的節(jié)點生命周期短和能量消耗不平衡的問題，提出了一種LFACH協(xié)議的改進(jìn)算法.算法的主要思想是考慮了節(jié)點的當(dāng)前位置以及當(dāng)前能量，從而可以使簇頭的分布更加均勻，延長節(jié)點的生命周期，對改進(jìn)后的LEACH協(xié)議和原LEACH協(xié)議進(jìn)行仿真，結(jié)果表明改進(jìn)后的協(xié)議在生存時間上提高了40.7%，并增加了數(shù)據(jù)的發(fā)送量，減少了節(jié)點的能量消耗.

關(guān)鍵詞：無線傳感器網(wǎng)絡(luò)；LEACH協(xié)議；網(wǎng)絡(luò)生存時間：NS-2仿真；能量均衡

DOI： 10.15938/j.jhust.2015.02.014

中圖分類號：TP391.1

文獻(xiàn)標(biāo)志碼：A

文章編號：1007-2683（2015）02-0075-05

0 引 言

無線傳感器網(wǎng)絡(luò)WSN（ wireless serisor net-works）被認(rèn)為是21世紀(jì)最重要的技術(shù)之一，是一種南大量無線傳感器節(jié)點組成的白組織多跳網(wǎng)絡(luò)，其日的是協(xié)作地感知、采集和處理網(wǎng)絡(luò)覆蓋區(qū)域感知對象的信息，并發(fā)送給觀察者，傳感囂、感知對象和觀察者構(gòu)成了傳感器網(wǎng)絡(luò)的3個要素.傳感器節(jié)點由匯聚節(jié)點SN（sink node）和普通傳感器節(jié)點組成.無線傳感器網(wǎng)絡(luò)節(jié)點一般以電池供電，但針對應(yīng)用業(yè)務(wù)的不同需求，有時需要太陽能、震動能、風(fēng)能、熱能等額外能量提取技術(shù).WSN的能耗主要分為通信能耗、感知能耗和計算能耗，其中通信能耗所占比重最大，所以均衡通信能耗能有效的延長整個網(wǎng)絡(luò)的生存時間，在無線傳感器網(wǎng)絡(luò)中，網(wǎng)絡(luò)的拓?fù)淇刂婆c優(yōu)化重要性表現(xiàn)在：影響整個網(wǎng)絡(luò)的生存時問；減小節(jié)點間通信干擾，提高網(wǎng)絡(luò)通信效率和為路由協(xié)議提供基礎(chǔ)，

在無線傳感器網(wǎng)絡(luò)體系結(jié)構(gòu)中，網(wǎng)絡(luò)層的路由技術(shù)對無線傳感器網(wǎng)絡(luò)的性能好壞有著重要影響.隨著國內(nèi)外無線傳感器網(wǎng)絡(luò)的研究發(fā)展，許多路由協(xié)議被提了出來，從網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的角度可以大體把它們分為兩類：平面路由結(jié)構(gòu)和層次路由結(jié)構(gòu)，層次路由算法是現(xiàn)有無線傳感器網(wǎng)絡(luò)路由算法的研究重點，下面將概述一下LEACH路由協(xié)議研究：LEACH是無線傳感器網(wǎng)絡(luò)中提出的第一個層次型路由協(xié)議，運用了數(shù)據(jù)壓縮技術(shù)和分層動態(tài)技術(shù)，通過隨機(jī)選取某些節(jié)點為簇頭來均衡網(wǎng)絡(luò)內(nèi)部負(fù)載；文描述了一種基于LFACH的改進(jìn)型非均勻分簇協(xié)議UCS（unequal clustering size），協(xié)議的中心思想是：考慮候選簇頭節(jié)點到基站的遠(yuǎn)近，構(gòu)造出大小非均勻的簇，從而實現(xiàn)了網(wǎng)絡(luò)中節(jié)點能耗的均衡；文中的LEACH-C是LEACH協(xié)議自身的提出者后來在LFACH協(xié)議上所做的改進(jìn)算法；文提出的TEEN（threshold sensitive energy efficient sen-sor network protocol）是閾值敏感能量高效傳感器網(wǎng)絡(luò)協(xié)議，它采用與LEACH類似的簇結(jié)構(gòu)和運行方式，定義了軟、硬兩個閾值來確實是否發(fā)送數(shù)據(jù)；文提出的混合有效能量分布式分簇HEED（hybirdenergy-efficient distributed clustering）算法是在LEACH算法簇頭分布不均勻這一問題基礎(chǔ)之上做出的對LEACH協(xié)議的改進(jìn)；在文中，高能效傳感器采集信息協(xié)議PFGASIS（power-efficientgathering in sensor information system）是使用貪婪算法GA（greeciy algorithm）形成鏈?zhǔn)降拇亟Y(jié)構(gòu)；文中，LEACH-M協(xié)議中引入了遺傳模擬退火算法.

LEACH算法與一般平面多跳路南算法相比，可以將網(wǎng)絡(luò)生命周期延長15%，但卻存在簇受開銷大、重復(fù)形成簇和簇規(guī)模分布不合理等不足，為此本文提出一種改進(jìn)算法.

1 LEACH協(xié)議簡介

L l 算法概述

LEACH協(xié)議是由MIT的Hei nzelman等提出的，該算法是為無線傳感器網(wǎng)絡(luò)設(shè)計的一種低功耗自適應(yīng)的分層路由協(xié)議，假定了一個均勻的、節(jié)點能量有限的密集傳感器網(wǎng)絡(luò)，各節(jié)點向接收點報告其數(shù)據(jù).LEACH協(xié)議將基于TDMA的MAC協(xié)議與聚類協(xié)}義和一個簡單的“路由”協(xié)議集成在一起，其基本思想是：通過循環(huán)的方式隨機(jī)選擇簇頭節(jié)點，對簇頭節(jié)點進(jìn)行輪換，把整個網(wǎng)絡(luò)的能量負(fù)載平均分配到各個節(jié)點上，從而平衡和降低能耗、延長網(wǎng)絡(luò)的生存周期.

LEACH協(xié)議提出“輪”的概念，算法的執(zhí)行過程是周期性的，每輪循環(huán)分為簇的建立階段和穩(wěn)定的數(shù)據(jù)通信階段，在簇的建立階段，隨機(jī)選擇節(jié)點作為簇頭節(jié)點，簇頭節(jié)點確定后即向周圍廣播信息，其他節(jié)點根據(jù)接收到的廣播信息信號的強(qiáng)弱來選擇要加入的簇，并告知相應(yīng)的簇頭節(jié)點，從而網(wǎng)絡(luò)被劃分為若干個簇.在數(shù)據(jù)通信階段，網(wǎng)絡(luò)完成簇結(jié)構(gòu)構(gòu)建，普通節(jié)點將采集數(shù)據(jù)發(fā)送給簇頭節(jié)點，由簇頭節(jié)點對數(shù)據(jù)進(jìn)行處理（如數(shù)據(jù)融合）操作，再轉(zhuǎn)發(fā)給匯聚節(jié)點，為了避免額外的處理開銷，數(shù)據(jù)通信階段一般持續(xù)較長的時間.每一輪結(jié)束后，網(wǎng)絡(luò)將重新進(jìn)入下一輪，繼續(xù)執(zhí)行這兩個階段的過程.

LEACH算法選舉簇頭的過程如下：節(jié)點產(chǎn)生一個0-1之間的隨機(jī)數(shù)，如果這個數(shù)小于閾值T（n），則發(fā)布自己是簇頭的公告消息.在每輪循環(huán)中，如果節(jié)點已經(jīng)當(dāng)選過簇頭，則把T（n）設(shè)置為0，這樣該節(jié)點就不再會再次當(dāng)選為簇頭，對于未當(dāng)選過簇頭的節(jié)點，則將以T（n）的概率當(dāng)選；隨著當(dāng)選過簇頭的節(jié)點數(shù)目增加，剩余節(jié)點當(dāng)選簇頭的閾值T（n）隨之增大，節(jié)點產(chǎn)生小于T（n）的隨機(jī)數(shù)的概率隨之增大，所以節(jié)點當(dāng)選簇頭的概率增大，當(dāng)只剩一個節(jié)點未當(dāng)選時，T（n）=1，表示這個節(jié)點一定當(dāng)選.T（n）如式（1）所示：其中：P簇頭在所有節(jié)點中所占的百分比；r是選舉輪數(shù)；rmod（l/P）代表這一輪循環(huán)中當(dāng)選簇頭的節(jié)點個數(shù)；G這一輪循環(huán)中未當(dāng)選過簇頭的節(jié)點集合.

采用這種隨機(jī)選舉簇頭的方法，需要得到節(jié)點總數(shù)與簇頭數(shù)的最優(yōu)比；因為基站是在遠(yuǎn)離仿真區(qū)域的位置，與距離較遠(yuǎn)的節(jié)點通信時，需要設(shè)置一些簇頭節(jié)點提升通信的效率，但是也不能過多（在極端情況下，每一個節(jié)點都是簇頭，和沒有分簇是一樣的，沒有多跳和數(shù)據(jù)融合優(yōu)勢），在相對低的比值處有一個最優(yōu)的數(shù)值；在一種典型的情況下，Heinzelman等認(rèn)為最優(yōu)值是5%，但是這要依賴于特定的設(shè)置并且要求預(yù)先確定.

LEACH協(xié)議采用了隨機(jī)選舉簇頭的方式來輪換簇頭，避免了簇頭過分消耗能量，采用數(shù)據(jù)融合則有效地減少了通信量，與一般的多跳路由協(xié)議和靜態(tài)聚類算法相比，能夠?qū)⒕W(wǎng)絡(luò)生命延長15%.

1.2 算法不足

1）由于LEACH協(xié)議是假定所有節(jié)點都能直接和基站進(jìn)行通信，而且每個節(jié)點都具備支持不同MAC的能力，因此該協(xié)議不大適合在大規(guī)模部署的應(yīng)用場景.2）LEACH協(xié)議沒有說明簇頭節(jié)點要怎么分布才更加均勻，有可能在實際應(yīng)用中出現(xiàn)一個區(qū)域有很多的簇頭節(jié)點，而有的很大的區(qū)域沒有任何的簇頭節(jié)點，這樣會出現(xiàn)網(wǎng)絡(luò)能耗不均衡.3） LFACH協(xié)議假定每個節(jié)點的能耗都差不多，這使得該協(xié)議不適用于節(jié)點能量不均衡負(fù)載的網(wǎng)絡(luò)部署中.4）LEACH協(xié)議的簇頭選舉算法沒有考慮剩余能量低的節(jié)點當(dāng)選為簇頭節(jié)點的情況，該節(jié)點很快會耗盡能量提早失效.不利于延長網(wǎng)絡(luò)的生存時間，網(wǎng)絡(luò)的魯棒性也不好.5）簇頭節(jié)點將采集到的數(shù)據(jù)通過數(shù)據(jù)融合后直接發(fā)送到基站，若傳感器節(jié)點分布在很廣的范圍內(nèi)，經(jīng)過很多輪后，距離基站近的簇頭節(jié)點與距離基站遠(yuǎn)的節(jié)點剩余能量相差很大；如果傳感器節(jié)點的初始能量值一致，距離匯聚節(jié)點遠(yuǎn)的節(jié)點能量最先消耗完，從而導(dǎo)致整體網(wǎng)絡(luò)生存時間縮短；假設(shè)簇頭節(jié)點和匯聚節(jié)點之間只采用多跳路由方式轉(zhuǎn)發(fā)數(shù)據(jù)，那么在網(wǎng)絡(luò)節(jié)點部署區(qū).域廣、節(jié)點數(shù)日眾多的情形下，距離基站近的區(qū)域的節(jié)點因為頻繁參與數(shù)據(jù)的轉(zhuǎn)發(fā)，能量消耗極快，該區(qū)域的節(jié)點反而很容易死掉，進(jìn)而影響整個網(wǎng)絡(luò)的生命周期.針對LEACH路由協(xié)議的不足，本文提出一種改進(jìn)的算法，我們且稱為NEWLEACH.

2 LEACH協(xié)議的改進(jìn)算法

2.1NEWLEACH算法的基本思想

因為涉及到距離，先簡單介紹下LEACH的物理模型：LEACH算法采用第一順序無線電能量模型FORM（first order radio model），該模型由發(fā)送電路、放大電路和接收電路組成.假定信道是雙向?qū)ΨQ的，即節(jié)點A傳送數(shù)據(jù)到節(jié)點B的能量消耗與B傳送到A是相同的.在傳輸距離為d時，傳感器節(jié)點發(fā)送和接收kbits消息所消耗的能量見式（2）和式（3）.其中：E是發(fā)送電路和接收電路無線電通信消耗的功率值，信號傳輸距離為d.信號在無線信道傳輸中的能量消耗與距離dr成正比，在短距離無線傳輸，即dd0時，r=4.上述的兩種能量衰減模型分別稱為自由空間（free space）衰減模型和多路信道衰減（multi-pathfading）模型.εam，，為自由空間衰減模型的衰減系數(shù)，εfs為多路信道衰減模型的衰減系數(shù).因此，根據(jù)發(fā)送節(jié)點與接收節(jié)點之間的距離，發(fā)送節(jié)點可以使用不同的能耗模型計算發(fā)送數(shù)據(jù)所需要的能量.Etx（k，d）表示發(fā)送節(jié)點所消耗的總能量，Enx（k）表示接收節(jié)點所消耗的總能量，分別表示接收電路和傳送電路中所消耗的功率值，并且是發(fā)送端發(fā)送消息經(jīng)過放大器時所消耗的能量.

本文的算法基本思想是：從上面的能量消耗模型可以看出，能量消耗其實也和距離有關(guān)，在設(shè)計優(yōu)化的簇頭選舉方法時，應(yīng)該根據(jù)距離來選擇不同的能量衰減模型；簇頭的最優(yōu)選擇應(yīng)該是，在當(dāng)前輪數(shù)剩余能量較高的，又或者是距離基站更近的節(jié)點，在數(shù)據(jù)的通信階段，應(yīng)該選擇當(dāng)前輪剩余節(jié)點剩余能量最高的節(jié)點進(jìn)行數(shù)據(jù)融合，如果該節(jié)點恰好是簇頭節(jié)點，在完成數(shù)據(jù)融合后，將數(shù)據(jù)發(fā)送給基站；如果是普通節(jié)點，在完成了數(shù)據(jù)融合后，將數(shù)據(jù)轉(zhuǎn)發(fā)給簇頭節(jié)點，簇頭節(jié)點再發(fā)送給基站.

2.2 NEWLEACH算法

2.2.1簇頭選舉

假設(shè)仿真區(qū)域是在100m×100m的區(qū)域內(nèi)進(jìn)行的，基站的坐標(biāo)是在（50，175），我們稱為bs，存仿真區(qū)域內(nèi)有一個中心點，我們稱為center，任一節(jié)點到bs的距離為（d1，到centei‘的距離為d2，如圖l所示.從圖中我們可以看出d1》d2，因此在設(shè)計距離因子時，把節(jié)點到基站的距離看成多路信道衰減模型，把節(jié)點到中心點的距離看成自由空間衰減模型根.據(jù)不同的情況選用不同的模型，使得距離基站近的有更大幾率當(dāng)選為簇頭.

傳統(tǒng)的LFACH協(xié)議不涉及節(jié)點的剩余能量問題，改進(jìn)的NEWLEACH算法用節(jié)點的當(dāng)前剩余能量和初始能量相比，這樣做可以使剩余能量更多的節(jié)點有更大幾率稱為簇頭，

改進(jìn)后的簇頭選舉如式（4）所示.式（4）是在式（1）的基礎(chǔ)上做的一個改進(jìn)：在最壞的情況下（‰…?！禘..州且d?！禿，），式（4）和式（1）是等價的，在其他的情形下，式（4）能夠在一定的程度卜優(yōu)化簇頭的選舉情況. -P[rmod（l/P）…案+盧羔]胙r（n）：I -P[rmod（l/P）

C，（4）

0，其他.其中：k為最佳簇頭數(shù)；理為能量因子；E。。。。.為當(dāng)前節(jié)點的剩余能量值；E訓(xùn)為當(dāng)前輪所有節(jié)點的剩余能量總值；β為距離因子；定義β=1-a，d2為節(jié)點到中心點的距離；d1為節(jié)點到基站的距離.

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

每一輪都有一個數(shù)據(jù)通信階段，因為要進(jìn)行數(shù)據(jù)融合，這將消耗非常多的能量，而簇頭也在簇的建立階段消耗很大一部分能量，有可能不再是簇內(nèi)能量最高的節(jié)點了，因此，本文采用的方法是：簇建完后，在本簇內(nèi)尋找一個剩余能量最高的節(jié)點，不一定非是簇頭節(jié)點，進(jìn)行數(shù)據(jù)融合后，再發(fā)送給基站，這將會減少簇內(nèi)簇頭節(jié)點的耗能，對平衡整個簇內(nèi)的能量起到至關(guān)重要的作用.

3 仿真結(jié)果及分析

假設(shè)在100m×100m的范圍內(nèi)隨機(jī)播散100個節(jié)點，基站坐標(biāo)為（50，175），節(jié)點的初始能量為2J，最佳簇頭數(shù)為5個.在LinuX平臺下，利用NS-2軟件對LFACH算法和改進(jìn)后的算法NE—WLEACH進(jìn)行仿真實現(xiàn).

3.1 確定α，β的取值

NEWLFACH改進(jìn)協(xié)議的目的是為了使網(wǎng)絡(luò)整體壽命延長，因此我們用節(jié)點的生存時間為指標(biāo)做了仿真，如圖2所示.在圖中用NEWLEACHX中的最后一個數(shù)字代表了lOa，例如NEWLFACHI代表了a=0.1，α從0.1到1每隔0.1取值一次，共9組數(shù)據(jù).從圖中可以看出NEWLFACH4表現(xiàn)最好，因為第一個節(jié)點死亡較晚，而且整個網(wǎng)絡(luò)的生存時間也較長，其他的取值要么死亡節(jié)點出現(xiàn)過早，要么整體壽命太短，所以取值α=0.4，p=0.6.

3.2 網(wǎng)絡(luò)生存時間對比

網(wǎng)絡(luò)生存周期對比如圖3所示，較長的是NE-WLEACH，較短的是LEACH.從圖中可以看出，NE-WLEACH整體壽命延長了，首次出現(xiàn)死亡節(jié)點是在380s，而LEACH首次出現(xiàn)死亡節(jié)點是在270s.LEACH在490s的時候只有6個存活節(jié)點，而NE—WLEACH在81Os時還有8個節(jié)點存活，節(jié)點壽命延長了40.7%.

3.3基站接收數(shù)據(jù)對比

基站的接收數(shù)據(jù)對比圖如圖4所示，在前490s，NEWLEACH和LEACH的發(fā)送數(shù)據(jù)量相差不大，所以曲線基本重合了.LEACH在490s時向基站發(fā)送了l116429bit數(shù)據(jù)，NEWLEACHA-810s時向基站發(fā)送了2338967bit個數(shù)據(jù)，說明改進(jìn)后的協(xié)議數(shù)據(jù)通信能力也得到了提高，但是存在一樣的時間里面，基站接收的數(shù)據(jù)差異并不那么明顯.

3.4能量消耗對比

節(jié)點的能量消耗對比如圖5所示，在上面的是LFACH，下面的是NWELEACH.在初始能量一致的情況下，在前120s內(nèi)，改進(jìn)后的協(xié)議消耗較快，有可能足計算各個節(jié)點的位置所消耗了一部分能量，但是在很大一部分時間內(nèi)，LEACH要比NE-WLEACH能量消耗快得多，也說明了改進(jìn)后的協(xié)議在能耗上也有了改善.

4 結(jié) 語

本文分析了LEACH協(xié)議的簇頭選舉過程，針對其存在的缺陷，提出了一種基于位置和剩余能量的新的簇頭選舉方法，通過仿真對比發(fā)現(xiàn)：新的算法延長了網(wǎng)絡(luò)節(jié)點生存時間，增加了節(jié)點與基站的通信量，也減少網(wǎng)絡(luò)節(jié)點能量的消耗；但是在通信階段，在相同的時問里，基站接收到的數(shù)據(jù)相差并不大，說明了新協(xié)議在數(shù)據(jù)的融合方面并沒有得到顯著的改善.另外，在仿真的初期，整體的能量消耗要比LEACH高一些，這是今后需要改進(jìn)的地方，希望本文的研究思路及結(jié)果對研發(fā)適用性廣、性能穩(wěn)定高效的新型無線傳感協(xié)議有所幫助.