王艷紅

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

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

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

1相關工作

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

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

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

2 系統(tǒng)模型

2.1模型假設

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

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

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

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

（4） 相鄰監(jiān)測區(qū)域內的數據具有相關性，可以進行數據融合；

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

2.2 能量模型

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

數據發(fā)送： （1）

數據接收： （2）

3改進的路由協(xié)議

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

圖1 100個節(jié)點被分成10層

Fig.1 100 nodes are divided into 10 layers

3.1成簇階段

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

（3）

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

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

圖2 簇內數據傳輸過程

Fig.2 Data transmission within a cluster

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

3.2簇間路由

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

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

Fig.3 Data transmission process of the LCCPR algorithm

3.3數據傳輸

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

3.4改進后的算法過程

LCCRP算法的執(zhí)行過程如下：

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

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

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

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

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

4仿真分析

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

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

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

圖4 三種協(xié)議平均能量消耗對比

Fig.4 Comparing the average energy consumption of three protocols

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

圖5 三種協(xié)議延遲比較

Fig.5 Comparing the delay of three protocols

5結束語

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

參考文獻：

[1]程英，高慶德，吳曉朝.無線傳感器網絡節(jié)能路由協(xié)議的改進[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]劉園莉，李臘元，盧迪.節(jié)能的無線傳感器網絡分簇路由協(xié)議的研究[J].傳感技術學報，2010， 23 （12）： 1792-1797.

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

[6]姚光順，溫衛(wèi)敏，張永定，等.改進的無線傳感器網絡簇首選擇策略及其路由算法[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的簇頭成鏈可靠路由協(xié)議研究[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.