一種基于分層的簇首成鏈WSN路由協議

王艷紅

摘 要：能量有效利用是路由算法首要目標，基于LEACH和PEGASIS算法設計出一種基于分層的簇首成鏈WSN路由協議（Layer Based Cluster-Chain Routing Protocol for Wireless Sensor Networks），該算法將網絡分成層并分成兩個階段運行，第一階段每層隨機選出簇首并將剩余節點按照貪心算法成簇，第二階段在所有層中選出剩余能量最大一個簇首節點作為Leader節點直接與基站通信，其余簇首節點選擇離自己最近的簇首節點多跳傳輸。并實驗表明改進的算法能有效延長網絡生命周期，降低數據延遲。

關鍵字：無線傳感器網絡；LEACH；PEGASIS；路由協議

中圖分類號：TP393 文件標志碼：A 文章編號：2095-2163（2015）05-

Cluster-Chain Routing Protocol for Wireless Sensor Networks based Layer

WANG Yanhong

（Nantong Shipping College Management information Department， Nantong Jiangsu 226010，China）

Abstract： Energy effective utilization is the most important goal to routing algorithm . Based on LEACH and PEGASIS algorithm， this paper designs a Routing Protocol on base of hierarchical Cluster heading into Chain （Layer -based Cluster-Chain Routing Protocol for Wireless Sensor Networks）. The algorithm separates network into layers and runs in two stages. In the first phase each layer of the nodes clusters according to the greedy algorithm， and in the second stage it selects the largest residual energy of a cluster head node to communicate directly with the base station as a leader node. The rest of the cluster head nodes choose the nearest cluster head nodes to do multi-hop communication. And the experiment shows that the improved algorithm can effectively prolong the network life cycle and reduce the data latency.

Key words： Wireless Sensor Network （WSN）； LEACH； PEGASIS； Routing Protocol

0引 言

無線傳感器網絡（Wireless sensor networks ，WSN）是一種特殊的網絡，與以往的傳統無線網絡相比具有鮮明顯著的特點。無線傳感器網絡由成千上萬微型傳感器節點所組成，無線傳感器網絡節點由于受到成本的限制，使得節點的感知能力、通信能力和數據處理能力都非常有限[1]。正是無線傳感器網絡中節點的這些物理特性使得無線傳感器網絡路由協議在設計時面臨著很多挑戰。其中，無線傳感器網絡節點由于電池供電能量有限則可證得當下即是無線傳感網絡路由協議設計升級時的重點研發因素。基于此，有效利用節點能量、并延長網絡生命周期就勢將成為路由協議設計中的現實關鍵研究課題[2-3]。相應地，本文將針對這一領域方向展開如下具體分析研究。

1相關工作

無線傳感器網絡路由協議根據網絡拓撲結構可以將路由協議分成兩大類，平面路由和分簇路由。其中的分簇路由將網絡分成多個子集，每個子集稱為一個簇，由簇首和多個簇內節點組成。由于分簇協議能夠平衡節點負載，與平面路由相比分簇協議能夠有效地延長網絡生命周期。因此，分簇協議是近期學者研究的重點。典型的分簇路由主要有LEACH、PEGASIS、HEED、TEEN等。尤其是LEACH[4]是最早提出的、也是經典的分簇協議之一，LEACH協議采用“輪”機制，每輪分為簇首選舉、成簇和數據傳輸三個階段，簇首負責收集簇內節點數據并將數據直接傳輸給基站。相對于一般的平面靜態路由協議，LEACH可以將網絡生存時間延長近15%。但是LEACH協議仍然表現有明顯的不足，例如隨機選取簇首導致簇首分布不均勻，簇首與基站直接通信導致通信能耗過大。這些都影響著網絡的生命周期，所以大量學者基于LEACH做了很多改進性研究。文獻[5，6]主要從簇首的選舉進行優化，在LEACH協議中引入競爭機制，保證簇首的分布。文獻[7]針對LEACH協議中簇首直接與基站通信的缺點提出了一定改進，在簇首間采用多跳傳輸通信，降低遠離基站簇首節點的通信能耗，從而延長網絡生命。文獻[8]同樣是針對簇首間通信的改進，簇首間以基站為根形成最小生成樹多跳通信。

PEGASIS[9]協議是在LEACH基礎上改進演變而來的，與LEACH協議不同的是PEGASIS協議將網絡看成一個簇，只有一個簇首。PEGASIS協議的主要思想是將全網節點形成一條鏈，鏈上隨機選出簇首節點，在數據傳輸階段鏈上的普通節點只與自己相鄰的節點通信，最后數據匯聚到鏈上的簇首節點，簇首節點直接將數據發送到基站。由于PEGASIS協議在全網形成一條鏈，鏈上的節點只需與相鄰的節點通信，如此即顯著降低了節點的通信能耗，但在此同時PEGASIS協議卻增加了數據傳輸的時延。

為了有效延長網絡生命周期，基于LEACH和PEGASIS協議的眾多后續升級算法則相繼獲得提出。文獻[10]提出了簇首成鏈算法，該算法就是基于LEACH和PEGASIS兩種協議的結合改進，在改進的簇首選擇機制的基礎上，簇首按照PEGASIS協議形成鏈，算法中采用鏈式簇首間鏈式能夠平衡簇首的負載，但是并沒有考慮鏈式路由帶來的數據延遲。為了解決這個問題，該文設計出了基于分層的簇首成鏈協議，協議將網絡分層，每層中的節點采用貪婪算法形成一條鏈，每層隨機選出簇首，簇首間同樣采用鏈式通信。其后的應用實踐表明該協議能夠適應大型網絡結構、降低能耗、延長網絡周期。

2 系統模型

2.1模型假設

假設傳感器網絡中 N 個傳感器節點分布在一定的區域當中，并且具有以下性質：

（1） 節點在監測區域內均勻分布并保持靜止不動，所有的節點是同質的，即初始能量、計算能量、存儲能力都相同；

（2） 每個節點能夠計算自身的剩余能量以及自身的地理位置；

（3） 基站位于傳感器監測區域以外的固定一點，基站能量不受限制，物理安全有保證；

（4） 相鄰監測區域內的數據具有相關性，可以進行數據融合；

（5） 節點之間通信鏈路是對稱的，例如節點a發送數據到節點v消耗的能量等于節點v發送數據到節點a的能耗。

2.2 能量模型

本協議的能量模型采用LEACH協議中的能量模型[11]。式（1）為發射 bit數據耗損的能量，由發射電路耗損和功率放大耗損兩部分構成。功率放大耗損根據發送者和接收者之間的距離（ 表示通信距離， 為其臨界值）分別采用自由空間模型和多路徑衰減模型。具體地， 為發射電路的耗損能量； 和 分別表示兩種信道模型下功率放大所需能量。式（2）為接收 數據的能量耗損，僅由電路耗損引起。

數據發送： （1）

數據接收： （2）

3改進的路由協議

本文結合 LEACH 和 PERASIS 的協議各自的優點，提出一個基于分層的簇首成鏈的路由協議LCCRP（Layer Based Cluster-Chain Routing Protocol）。LCCRP算法摒棄了LEACH 和PERASIS 各自的缺點，采用了如下的分層思想，即簇內成鏈傳輸數據至簇首，數據匯總后再簇首成鏈傳送數據至基站。在此假設一個無線傳感器網絡的N個節點均勻分布在L（m）×L（m）的區域內。如果N等于100，即可假設每層的節點個數等于10，那么就把區域分成了10層，如圖1所示。

圖1 100個節點被分成10層

Fig.1 100 nodes are divided into 10 layers

3.1成簇階段

在這個階段，每層隨機選擇一個節點作為簇首，然后簇首節點向層的兩端發送消息宣告自己是簇首節點，之后每層的端節點向距離自己最近的鄰居節點發送數據，鄰居節點接收到數據后、并將數據融合后再轉發給自己的鄰居節點，直到每層的數據都到達簇首。本文采用類似LEACH協議中的簇首選舉機制，簇首選舉公式如公式（3）所示。

（3）

簇首選舉成功之后，每層節點入簇，和LEACH協議不同的是節點不再根據收到信號強弱加入簇，而是由每層選舉出來的簇首向層兩端最遠距離發送成鏈的信息，每層距離簇首最遠的兩個端點則將選擇離自己最近的節點作為下一跳，最終每層的節點形成一條鏈通信。

在此，研究中舉例說明了某一層的成簇過程，具體如圖2所示。圖2中黑色的節點代表隨機選出的簇首節點。在開始的時候層兩端的節點收到由簇首發來的消息，兩端的兩個節點就可以把數據以及簇首的消息發送給鄰居節點，鄰居節點在收到上個節點發來的數據后將自己的數據與之融合再轉發給鄰居節點，以此類推直至數據都到達簇首。

圖2 簇內數據傳輸過程

Fig.2 Data transmission within a cluster

在每層內節點只須與自己相鄰的兩個節點通信，減少了節點之間傳送數據的平均距離。簇內的節點除了兩端的節點都要將數據融合后再轉發，減少了數據轉發量。當分簇完成之后，進入到第二個階段，簇間路由的形成。

3.2簇間路由

如上面所述，當所有層的節點將數據發送給每層的簇首之后，即進入到簇間通信的階段。首先在所有的簇首中選出剩余能量最大的作為簇首鏈的Leader節點。每個簇首節點向其他簇首節點廣播自己的剩余能量消息。每個簇首節點接收到這樣消息時對比自己的剩余能量與接收到的節點的剩余能量大小。如果一個簇首節點發現自己的能量比其他的簇首節點都大，就將作為Leader節點并向其他簇首廣播。當有兩個以上的簇首剩余能量都最大，為了避免沖突，第一個發送廣播消息的簇首則當選Leader。每層的簇首同樣看成一個簇，Leader節點即是簇首，其他層的簇首節點形成鏈式多跳通信。Leader節點向離自己最遠的兩個簇首發送消息，簇首間以貪心算法形成鏈。簇首節點依次向自己的鄰居節點發送數據。鄰居節點接收到數據后將數據與自己的數據融合后轉發。當所有數據到達簇首的Leader節點后，Leader節點將數據與自己的數據融合后發送給基站。在圖3中顯示了LCCRP算法的數據傳輸過程。

圖3 LCCRP算法的數據傳輸過程

Fig.3 Data transmission process of the LCCPR algorithm

3.3數據傳輸

當簇間路由形成階段完成之后網絡進入數據傳輸，首先每層的節點收集數據，之后每層的簇首向層內兩端節點發送消息，兩端的節點接收到簇首發來的消息就將自己的數據按照層內的數據鏈轉發給離自己最近的鄰居節點，鄰居節點收到上個節點發來的數據并與自己的數據融合后轉發至鄰居節點依次類推直到層內的數據匯總到簇首，然后簇內節點進入休眠狀態。在簇間路由中數據的傳輸與簇內傳輸類似，由選出的Leader節點向最遠的兩個簇首節點發送令牌環，離Leader最遠的兩個簇首節點將接收到的數據融合后，繼而轉發給臨近層的簇首，直至數據匯聚到Leader節點，Leader節點則與基站直接通信。

3.4改進后的算法過程

LCCRP算法的執行過程如下：

（1）網絡分層，由基站將網絡均勻分層。

（2）簇首選舉，采用類似LEACH協議相同的選舉方法選出每層的簇首節點。

（3）各層成鏈，由選舉出的簇首節點向層的兩端節點發送成鏈信號，每層節點采用貪婪算法形成鏈。

（4）簇間路由，在所有的簇首中選出能量最大的簇首節點作為Leader節點，簇首間的通信同樣以Leader節點為簇首們的簇首形成鏈。最后由Leader節點直接與基站通信。

（5）數據傳輸，當簇首間路由建立之后，網絡進入數據傳輸，首先每層的簇首節點向鏈上最遠的兩端節點發送收集數據的信息包，每層的節點依次將數據轉發至本層的簇首節點，之后每層的簇首節點同樣通過簇間路由將數據轉發至Leader節點，最后由Leader節點將數據直接發送給基站。

4仿真分析

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

LCCRP 算法改進了已有算法中節點負載不均衡，能量消耗差異等缺點，以延長整個網絡生存周期為設計目標，結合LEACH協議和PEGASIS協議，汲取了兩者的優點、同時摒棄了各自不足，通過采用簇首間鏈式多跳通信降低了簇首與基站直接通信的能耗，并且將網絡分層結合使得每層的鏈明顯減短，由此而降低了PEGASIS協議將整個網絡形成一條鏈帶來的數據延遲。

其中圖 4 表示的是 LCCRP 協議與LEACH 協議，PEGASIS 協議平均一輪能量消耗的比較。由于傳感器的節點分布，簇頭的選擇以及成鏈的隨機因素很大。所以每種協議循環計算 50 次取其平均值從而得到結果。在網絡中傳輸通信是網絡中最大的能量消耗因素，LEACH協議中所有簇首都與基站直接通信，尤其是遠離基站的簇首節點消耗的能量更大，PEGASIS協議通過鏈式通信能夠改進LEACH協議的缺點，每輪能耗明顯降低了，改進的協議同樣采用PEGASIS的鏈式通信，所以三種協議相比，LEACH協議中每輪的能耗最大。從圖4可以看出LCCRP能量消耗幾乎和PEGASIS 協議相同，但只有LEACH協議的20%左右。可以得出改進的協議相比較LEACH協議則能有效演唱網絡的生命周期。圖5表示三種協議數據延遲對比，從圖中可以看到改進的協議數據延遲和LEACH協議相同，只是PEGASIS協議的28%。

圖4 三種協議平均能量消耗對比

Fig.4 Comparing the average energy consumption of three protocols

PEGASIS協議理論上的性能是非常好的，但是會帶來較大的滯后性，同時鏈上個別節點的失效，會導致數據采集的整體失敗。LCCRP協議將網絡分層成鏈，避免了整個網絡形成一條鏈時數據傳輸的時延。為了實驗的簡便，假設一次數據轉發計為一個單位的數據延遲。圖5表示三種協議數據傳輸延遲對比情況。LEACH協議每輪的分簇數目不定，所以同樣統計50輪分簇數目的平均值來計算延遲，從圖中可以看出LCCRP協議的延遲略高于LEACH協議，但只有PEGASIS協議的22%左右。由此可得，改進算法結合上述兩個協議的優點不僅有效地降低了能耗，而且保證了必要的實時性。

圖5 三種協議延遲比較

Fig.5 Comparing the delay of three protocols

5結束語

論文以平衡網絡負載延長網絡生命周期為研究目的，提出了一種基于分層的簇首成鏈路由協議LCCRP，該協議綜合了 LEACH 協議和 PERASIS 協議的優點，將網絡分為層，并在每層中按照貪心算法成簇，整個網絡數據傳輸分成兩個階段運行，第一階段每層的節點將數據融合發送給鄰居節點直到發送到簇首節點，第二階段簇首節點選出剩余能量最大一個簇首節點作為Leader節點，并直接與基站通信。簇間通信由簇首選擇離自己最近的簇首節點多跳傳輸。由仿真結果可得，改進的新協議在更大程度上能夠優化節點能量，延長網絡的生命周期，并且分層的成鏈操作也可減小數據的傳輸時延。

參考文獻：

[1]程英，高慶德，吳曉朝.無線傳感器網絡節能路由協議的改進[J].計算機科學，2012， 11（39）：93-95.

[2] LOTF J J， HOSSEINZADEH M， ALGULIEV R M. Hierarchical routing in Wireless Sensor Networks： A survey[C]//Proceedings of 2010 2nd International Conference on Computer Engineering and Technology， Chengdu， China： IEEE， 2010： 650-654.

[3] WAWARE S， SARWADE D N， GANGURDE P. A review of power efficient hierarchical routing protocols in Wireless Sensor Networks[J]. International Journal of Engineering Research and Applications （IJERA）， 2012， 2（2）： 1096-1102.

[4]劉園莉，李臘元，盧迪.節能的無線傳感器網絡分簇路由協議的研究[J].傳感技術學報，2010， 23 （12）： 1792-1797.

[5]張然，覃少華. 基于LEACH的無線傳感器網絡分簇路由協議[J].計算機工程與設計，2012，33（4）：1333-1335+1336.

[6]姚光順，溫衛敏，張永定，等.改進的無線傳感器網絡簇首選擇策略及其路由算法[J].計算機應用，2013，33（4）：908-911+915.

[7]周冬鑫，金文光，容志能. 基于分層的無線傳感網絡多跳分簇路由算法[J]. 傳感技術學報，2011，24（1）：73-78.

[8]張明才，薛安榮，王偉.基于最小生成樹的非均勻分簇路由算法[J].計算機應用， 2012，32（3）. 787-790.

[9] KRISHNAVENI P， SUTHA J. Analysis of routing protocols for wireless sensor networks[J].International Journal of Emerging Technology and Advanced Engineering，2012，2（11）：401-407.

[10]張震，閆連山，潘煒，等.基于LEACH和PEGASIS的簇頭成鏈可靠路由協議研究[J].傳感技術學報， 2010， 23（8）： 1173-1178.

[11] LIU Xuxun.A survey on clustering routing protocols in Wireless Sensor Networks [J]. sensors， 2012， 12： 11113-11153.