一種無線傳感器網絡路由協議LEACH的改進算法

李蘭英++劉昌東

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

關鍵詞：無線傳感器網絡；LEACH協議；網絡生存時間：NS-2仿真；能量均衡

DOI： 10.15938/j.jhust.2015.02.014

中圖分類號：TP391.1

文獻標志碼：A

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

0 引 言

無線傳感器網絡WSN（ wireless serisor net-works）被認為是21世紀最重要的技術之一，是一種南大量無線傳感器節點組成的白組織多跳網絡，其日的是協作地感知、采集和處理網絡覆蓋區域感知對象的信息，并發送給觀察者，傳感囂、感知對象和觀察者構成了傳感器網絡的3個要素.傳感器節點由匯聚節點SN（sink node）和普通傳感器節點組成.無線傳感器網絡節點一般以電池供電，但針對應用業務的不同需求，有時需要太陽能、震動能、風能、熱能等額外能量提取技術.WSN的能耗主要分為通信能耗、感知能耗和計算能耗，其中通信能耗所占比重最大，所以均衡通信能耗能有效的延長整個網絡的生存時間，在無線傳感器網絡中，網絡的拓撲控制與優化重要性表現在：影響整個網絡的生存時問；減小節點間通信干擾，提高網絡通信效率和為路由協議提供基礎，

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

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

1 LEACH協議簡介

L l 算法概述

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

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

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

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

LEACH協議采用了隨機選舉簇頭的方式來輪換簇頭，避免了簇頭過分消耗能量，采用數據融合則有效地減少了通信量，與一般的多跳路由協議和靜態聚類算法相比，能夠將網絡生命延長15%.

1.2 算法不足

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

2 LEACH協議的改進算法

2.1NEWLEACH算法的基本思想

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

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

2.2 NEWLEACH算法

2.2.1簇頭選舉

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

傳統的LFACH協議不涉及節點的剩余能量問題，改進的NEWLEACH算法用節點的當前剩余能量和初始能量相比，這樣做可以使剩余能量更多的節點有更大幾率稱為簇頭，

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

C，（4）

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

2.2.2數據通信

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

3 仿真結果及分析

假設在100m×100m的范圍內隨機播散100個節點，基站坐標為（50，175），節點的初始能量為2J，最佳簇頭數為5個.在LinuX平臺下，利用NS-2軟件對LFACH算法和改進后的算法NE—WLEACH進行仿真實現.

3.1 確定α，β的取值

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

3.2 網絡生存時間對比

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

3.3基站接收數據對比

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

3.4能量消耗對比

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

4 結 語

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