一種基于LEACH與PEGASIS協議的分層成鏈優化路由算法*

嚴 英，郭 麗，許建真

(南京郵電大學計算機學院和計算機技術研究所，南京 210003)

無線傳感器網絡(Wireless Sensor Network，WSN)是散布在一定區域的大量傳感器節點，通過無線通信方式形成多跳自組織的網絡系統。網絡中的節點由電池供電，因其數目多、分布廣、所處環境復雜等特點，造成了節點嚴重的能量約束問題。通常，傳感器節點的能量是受限的，當節點的能量耗盡之后，網絡便失去了作用。因為WSN由大量低成本的微型節點組成，能量、帶寬、計算、存儲等資源非常有限。有效管理和使用這些資源，最大限度地延長網絡壽命是WSN研究所面臨的一個關鍵技術挑戰。因此，網絡的能耗和路由協議是無線傳感網絡的重要研究內容［1］。

在WSN中，節點中的能量大部分消耗在了數據的接收及轉發的過程中［2］，由于節點分布的位置不均勻，所以距離基站(Basic Station，BS)遠的節點消耗的能量比較快，容易及早死亡。而距離BS較近的節點，也會由于要進行鄰接節點數據的融合而消耗大量的能量，加速死亡的概率。這樣就導致了節點能耗的分布不均問題。

本文基于PERASIS的鏈狀結構，吸收了LEACH的分簇思想，提出一種新型的分簇分層成鏈的優化路由算法，既避免了PERASIS協議相鄰節點容易形成長鏈的缺點也解決了LEACH協議的各個節點負載不平衡的問題，使探測區域不容易出現盲區。

1 MSN路由協議比較分析

1.1 LEACH 協議

LEACH協議是一種基于聚類(clustering)的低功耗自適應路由協議［3］，建立在每個節點的能量都是相等的基礎上的，把無線傳感網絡(Wireless Sensor Network)分為以簇為單位的若干單元，在每個簇內都定義一個簇頭(Cluster Head)，負責將該簇內各個傳感器收集到的信息傳輸給接收器節點(Sink)。傳送以輪為單位，在一輪結束之后，Sink節點負責更換簇頭節點，以便進行下一輪的數據傳輸。這種模式可以有效的降低網絡能量消耗，延長網絡生存周期［3－4］。

在初始化階段，每個節點產生一個0～1之間的隨機數，如果這個數小于閾值T(n)，則該節點向整個網絡廣播它是簇頭。T(n)的計算公式為［5－6］

p:期望的簇頭節點在總的節點中所占百分比;r:當前輪數;G:在剩余的1/p輪中未成為簇頭節點的節點集。

節點被選作簇頭后，向該簇內各節點通知其是簇頭，其余各節點根據接收信號的大小決定加入至該簇，并返回加入信號。簇頭，簇內節點與Sink節點的具體數據傳輸方式如圖1所示。

圖1 LEACH協議以“輪”傳輸數據方式

但是LEACH協議存在不足之處:①每輪簇頭更換會導致大量能量的浪費，而且在此被選擇的簇頭，只能保證下一輪不被選為簇頭，而以后則不可以保證;②簇頭的選擇是隨機的，簇頭的能量剩余問題考慮的不完善，有可能導致某些節點的能量提早耗盡;③在簇頭選擇完畢之后，開始分簇傳遞數據，簇頭節點管理整個簇的數據接收工作，這樣簇內節點同時傳送數據會造成簇頭的工作量加大，從而導致簇頭的能量消耗的過快，生命周期衰減的速度也加快。

1.2 PERASIS 協議

PERASIS協議是一種典型的鏈狀結構的路由協議［7］，它使用貪婪算法把WSN中的所有節點鏈接成一條鏈［8］，鏈上的節點只跟自己的鄰接節點通信。從離BS最遠端的節點開始構建鏈，構鏈完成之后，從遠端節點依次向其鏈接節點傳遞數據信息，除了端節點之外的其他節點都要進行數據融合之后再傳遞給自身的鄰接節點，直到傳遞到簇頭節點，簇頭節點將自己的數據跟接收的數據融合之后傳遞給BS。當鏈中有一個節點死亡時，鏈就需要重新構建［9］。

圖2 PERASIS協議構造數據鏈方式

相比LEACH協議，PERASIS協議取的了以下幾個方面的優勢:①基于鏈狀的拓撲結構減少了節點之間傳送數據的平均距離;②僅僅只有一個LEADER節點向BS傳遞數據，減少了向遠端節點發送的數據量，從而減少了能量的消耗［10］;③PERASIS的建鏈算法比較簡單，時間復雜度為O(n2)。

雖然PERASIS在網絡壽命以及能量均衡方面取的了優勢，但是還是存在一些不足之處:①長鏈的出現:由于在鏈上的某個節點死亡之后會重新構造鏈，從而死亡節點的鄰接節點就不可避免的會出現長鏈現象，這樣就會導致傳送數據時，在長鏈部分會消耗過多的能量而造成節點的生命周期縮短;②簇頭節點的更換問題:PERASIS采用的是輪流在鏈上選擇簇頭的方式進行簇頭與BS之間的通信，如果離BS較遠的節點擔任了簇頭，就會該簇頭的能量消耗不均衡問題，導致過早的死亡。

2 優化路由協議LDBPL

基于上述分析，結合LEACH和PERASIS的協議各自的優點，提出一個分簇分層成鏈的路由算法LDBPL。LDBPL算法擯棄了上述提出的LEACH和PERASIS各自的缺點，采用簇內成鏈傳輸數據至簇頭，數據匯總后再簇頭成鏈傳送數據至BS的分層思想。本算法假設:①節點是靜止的，BS知道每個節點的能量信息以及地理位置信息;②每個節點的初始能量均衡;③在每一輪數據傳輸完畢后，每個節點都能反饋自己的剩余能量信息給BS。

LDBPL算法分為以下幾個階段。

2.1 分簇階段

與LEACH協議相似，由BS統一管理簇頭的選擇，但是為了避免LEACH協議隨機的選擇簇頭容易導致整個傳感器網絡的能量分配不均衡，本協議在選擇簇頭以及劃分簇團范圍時采用了文獻［11］的方法，從節點的剩余能量以及其地理位置方面考慮簇頭的選擇問題。文獻［11］總體算法是利用等角度分區避免簇頭分布不均的問題，根據簇內各節點剩余能量決定簇頭的選取，其仿真結果證明了算法具有更高的能量使用率和更長的生存時間。這就避免了LEACH協議的缺點②由于隨機選擇簇頭而導致整個網絡的能量不均衡。

根據文獻［11］的優化算法得出的簇團結構為:簇頭位于簇中心，簇內節點分布均衡，并且區內節點把自身帶有的node_id，area_id和標示本身能量的信息傳輸給它的鄰節點，這樣同區域內的每個節點都相互知道其它節點的相關信息［11］。這樣就為下一階段的簇內成鏈階段奠定了基礎。

假設有N個節點均勻分布在M*M區域內k為簇頭數，則簇內節點數即為N/k。

從節點到簇頭的平均距離計算公式如下:

2.2 成鏈階段

LDBPL算法在分簇階段完成之后，以每個簇為一個集團開始做成鏈操作，每個簇頭在接收完成本簇內的信息之后，BS根據各個簇頭的剩余能量選定一個LEADER節點(假設BS選擇LEADER節點所消耗的能量全部由BS承擔)，再成鏈傳遞數據至LEADER節點，之后LEADER節點把數據與自身的數據相融合之后，與BS直接通信。具體操作如下:

(1)簇內成鏈

借用 PEGASIS的成鏈方法，由簇頭集中管理［12］，根據PERASIS協議的貪婪算法成鏈，這種分簇成鏈就會避免整體成鏈帶來的能量的損耗，也可以避免長鏈的產生。具體成鏈方法如下:

算法中出現的變量含義表述如下:①V—已經入鏈的節點，V'—還沒有入鏈的節點;②vi，vj，vk—簇內節點，vhead—簇頭節點;③pi，j—節點 vi到 vj傳送數據所需要能耗的加權值。

算法描述如下:步驟一:初始狀態:V={vhead}，V'={v1，v2，…，vn};步驟二:由 V 廣播信息至 V'內各節點，要求報告 pv，j，使得對任意 vj屬于 V'，都有pv，i＜ =pv，j，把 vj節點吸收進入 V 集合，V'=V'－{vj};步驟三:循環執行步驟二一直到 V'為空集結束。

整個吸收節點成鏈的模型圖如下(節點之間的虛線說所示的數字是節點之間相互傳送數據所消耗的能耗加權值 Pi，j):

圖3 PERASIS分鏈成圖

圖4 PERASIG分鏈詳細圖

本算法采用無線通信模型，發送傳輸n bit的數據到距離為d2的接收方所消耗的能量為:

其中，Eelec表示發射電路消耗的能量;￡fs和￡mp為信號放大器所消耗的能量;d0為常量。

節點接收n bit的數據所消耗的能量為:

將M個長度為n bit的數據包融合所消耗的能量為:

其中，k表示簇頭數目;N/k表示整個WSN一共有多少個簇;EDA表示簇頭進行數據融合所消耗的能量。則簇頭消耗的總能量為:

(2)簇頭成鏈

成鏈步驟跟簇內成鏈的步驟大體相同，其中有一個主要的區別，即BS選擇簇頭的LEADER節點時，考慮到了簇頭節點的剩余能量以及距離BS的距離。也就是說BS在選擇LEADER節點的時候會優先選取剩余能量多而且距離近的簇頭節點，這樣在數據傳送的時候就會減少能量的消耗。

簇頭成鏈的步驟如下:①由BS發出廣播相信，要求每個接受到信息的簇頭節點反饋node_id以及area_id;②收到BS廣播信息的簇頭開始單播的發送反饋信息給簇頭，其他的非簇頭節點則不做任何反應，進入休眠狀態;③在BS接受到簇頭節點的反饋的信息做以下計算:

(xi，yi，zi)是簇頭節點的坐標;(XBS，YBS，ZBS)是BS的坐標;E剩:表示簇頭的剩余能量;Qi:表示d與E剩的函數。

④BS把Qi最大的節點設置為LEADER節點，廣播給所有的簇頭節點LEADER節點的node_id并且從遠離LEADER節點的簇頭節點開始建鏈;⑤建鏈的過程同簇內成鏈的步驟一樣;⑥建鏈完成之后的數據傳輸與PERASIS協議聲明的一樣，從最遠端輸送數據給相鄰節點，相鄰節點接收到數據之后與自身的數據融合在傳送到次相鄰節點，以此類推。直到簇內所有成鏈的節點把數據傳送給LEADER節點，LEADER節點在進行自身的數據融合之后傳送給BS。到此，整個LDBPL算法一輪完成。

下圖表示在一個100 m×100 m的范圍內有60個傳感器節點，利用LDBPL建鏈方法得到的鏈如圖5所示。

圖5 LDBPL方法成鏈方法

與PEGASIS算法一樣，在LDBPL算法中，無論是簇內成鏈還是簇頭成鏈，只要鏈上任何一個節點死亡都將重新按上述方法重新建鏈，并且LDBPL沒有增加計算的時間復雜度，其時間復雜度和PEGASIS算法一樣為O(n2)。

LDBPL算法采用了文獻［10］的思路，即不是在每輪通信之后重新選擇簇頭節點，而是在一定輪數的通信完成之后才選擇節點，這就節省了簇頭重新選擇耗費的大量不可再生的能源。根據文獻［10］的仿真算法可以得出這類思想一定的延長了WSN的網絡生存時間。該思想根據節點的剩余率的多少來計算重新選擇簇頭節點的輪數。

表1 剩余率與選擇簇頭關系表

值得注意的是:LEADER節點是在每輪通信之后就重新選擇，這是考慮到了LEADER節點直接與BS通信的耗能問題。由于LEADER節點是從簇頭節點中選取的，簇頭在簇內成鏈，簇頭成鏈以及數據融合節點消耗了大量的能量。如果LEADER節點也根據上述表格每隔一定的輪數選取，會導致LEADER節點的能耗過早的消耗完畢，使得整個WSN負載不均衡。

3 仿真結果及分析

本文利采用了MATLAB軟件對LDBPL算法，LEACH算法和PEGASIS算法進行了對比，分別從網絡生存周期和數據傳輸時延兩方面考慮，評價LDBPL算法的性能。在范圍為100 m×100 m的區域內有100個傳感器節點，設節點的坐標值在(0，0)～(100，100)范圍內變化，BS的位置位于(50，175)的位置上，節點的初始能量Eo=1 J，發送和接收電路通信耗能Eelec=50 nJ/bit，數據融合耗能EDA=5 nJ/bit/signal，￡mp和￡fs分別為 0.001 3 pJ/bit/m4、10 pJ/bit/m2。

LDBPL算法改進了以往算法中節點負載不均衡，能量消耗差異等缺點，以延長整個網絡生存周期為設計目標。其中圖6表示的是LDBPL協議與LEACH協議，PEGASIS協議節點生存周期的比較。由于傳感器的節點分布，簇頭的選擇以及成鏈的隨機因素很大。所以，每種協議循環計算100次取其平均值從而得到結果。

圖6 100個節點的網絡生存時間

由仿真結果得出:LEACH協議的第一個節點死亡和全部節點死亡分別出現在第在第700輪和第1 250輪;PEGASIS協議的第一個節點死亡和全部節點死亡分別出現自第780輪和第1330輪;而LDBPL協議的第一個節點死亡和全部節點死亡分別出現在第850輪和第1 520輪(以上均為模糊取值)。同時本文還計算了當整個WSN網絡中有1%、20%、50%、100%節點死亡時，LDBPL算法的通信輪數與LEACH算法以及PEGASIS算法的比較，可得出LDBPL算法相對于LEACH算法在分別延長了25%、38%、47%、56%相對于PEGASIS分別延長了19%、31%、35%和45%。

LDBPL算法還縮短了數據傳輸間的時延問題。本文通過仿真計算LEACH協議、PEGASIS協議以及LDBPL協議中每輪通信數據的端到端時延來驗證數據傳輸時延的改進情況。

圖7 節點的端到端時延

LEACH協議的數據傳送:在成簇階段完成之后，簇內節點開始按照TDMA方式向簇頭節點傳送數據信息，待簇頭節點接收到簇內全部節點的數據之后開始進行數據融合，數據融合完成后發往BS，故LEACH協議的數據傳輸時延為:簇內節點到簇頭的的傳輸時延與簇頭到BS傳輸時延之和。由于節點的分布是隨機的，而且數量眾多，所以計算的是數據傳輸時延最長的一輪，故端到端傳輸時延如圖7所示。

其中，D(Ni)表示簇內節點到簇頭的時延。

PEGASIS協議的數據傳送:整個WSN內的節點成鏈，之后在鏈中選擇一個領導節點，領導節點在接收到鏈中所有節點的數據之后，與自己的數據進行融合，融合之后再發往BS。故PEGASIS協議的數據傳輸時延為:整條鏈中節點傳遞數據的時延與領導節點到BS的傳輸時延之和。

其中，DL_BS表示CH到BS的時延

LDBPL協議的數據傳送:分簇之后先簇內成鏈，簇頭節點接收到簇內的數據之后再簇頭成鏈，之后傳遞給LEADER節點進行數據融合后發往BS，忽略BS進行LEADER節點選擇所引起的時間遲延。故LDBPL協議的數據傳輸時延為:簇內節點鏈傳輸數據的時延，簇頭成鏈傳輸數據的時延以及LEADER節點發往BS的傳輸時延三者之和。

其中，dij為第i個簇中的第j個節點。

仿真證明LDBPL協議相對于LEACH協議以及PEGASIS協議在網絡生存周期和數據傳輸時延方面有一定的改進，使用LDBPL協議均衡了網絡節點的能耗，也節省了網絡節點在傳送數據以及每輪更換節點的能量消耗。

4 結論

LDBPL協議吸取了LEACH協議和PERASIS協議的優點，改善了LEACH協議中每輪隨機選擇節點當簇頭以及頻繁的更換簇頭而導致的整個傳感網絡節點能量不均衡的問題，同時也避免了PERASIS協議所產生的長鏈問題。采用均勻成簇，簇內成鏈，簇頭成鏈的方法傳遞整個WSN中節點的數據信息。由仿真結果可得，改進的新協議更加的能節省節點能量，延長網絡的生命周期并且分層的成鏈操作減小了數據的傳輸時延。

［1］李曉維，徐勇軍，任豐原.無線傳感器網絡技術［M］.第1版.北京:北京工業大學出版社，2007:1－17.

［2］羅玉紅，陳松喬，王建新.移動自組網中能量有效的路由算法［J］.計算機工程及應用，2004，36:15－21.

［3］Wendi Rabiner Heinzelman，Anantha Chandrakasan，Hari Balakrishnan.Energy-Efficient Communication Protocol for Wireless SensorNetworks［J］.IEEE Computer Society，2000(8):30－47.

［4］胡鋼，謝冬梅，吳元忠.無線傳感器網絡路由協議LEACH的研究與改進［J］.傳感技術學報，2007，20(6):1391－1396.

［5］Heinzelman W R，Chandrakasan A，Balakrishnan H.Energy-Efficient Communication Protocol for Wireless Microsensor Networks，Proc.of the 33rd Annual Hawaii International Conference on System Sciences(HICSS)［M］.January 4 ～ 7，2000.Maui，Hawaii.p.3005－3014.

［6］Heinzelman W.Energy—Efficient Communication Protocol for Wireless Microsensor Networks［A］.Proceedings of the 33rd Annual Hawaii International Conference on System Sciences［C］.Hawaii，USA，2000.4－7.

［7］Stephanie Lindsey，Cauligi S，Raghavendra.PEGASIS:Power Efficient Gathering in Sensor Information Systems［J］.IEEE Aerospace Conference Proceedings，2002，3(3):1125－1130.

［8］張震，閆連山，潘煒，等.基于LEACH和PEGASIS的簇頭成鏈可靠路由協議研究［J］.傳感技術學報，2010，23(8):1173－1178.

［9］Jung Sung-Min，Han Young-Ju，Chung Tai-Myoung.The Concentric Clustering Scheme for Efficient Energy Consumption in the PEGASIS［C］//Proceeding of 9th International Conference on Advanced Communication Technology，2007:260－265.

［10］余勇昌，韋崗.無線傳感器網絡中基于PEGASIS協議的改進算法［J］.電子學報，2008，36(7):1309－1313.

［11］丁睿，南建國.基于LEACH協議簇頭選擇算法的改進［J］.微計算機信息，2009，24:187－189.

［12］姜華，鄭春雷，劉海濤.無線傳感網絡中鏈路級能量有效策略的研究［J］.傳感技術學報，2006，19(6):2738－2742.