無線傳感器網絡分簇路由協議研究

劉興 楊濟海 楊濤 韓晴

摘 ? 要：在無線傳感器網絡中，分簇型路由在路由協議中占據重要的地位，該協議方便拓撲結構管理，能源利用率高，數據融合簡單。文章從簇頭生成、簇形成和簇路由3個角度對典型的分簇路由算法LEACH，HEED，EEUC，PEGASIS進行了系統描述，從網絡生命周期和節點存活數量等方面，對比了其優缺點，結合該領域的研究現狀，指出了未來研究的方向。

關鍵詞：無線傳感器網絡;分簇;路由協議

無線傳感器網絡（Qireless Sensor Network，WSN）作為數據采集和處理的新方式，在各行業受到了越來越廣泛的應用[1]。它是由大量傳感器節點組成的一個自組織無線網絡系統，具有數據采集、數據處理、數據存儲和無線通信等功能，被廣泛應用于軍事偵察、環境監測、醫療監控、農業、養殖、空間探索等領域。由于網絡中節點的計算能力、存儲容量和能量資源有限，使得路由協議的設計成為無線傳感器網絡的關鍵技術之一，在WSN路由協議中，分簇型路由協議由于其能量利用率高而受到越來越廣泛的應用。

1 ? ?無線傳感器網絡分簇路由算法概述

與其他類型的路由協議相比，分簇路由協議具有更好的性能，是目前研究的重點和熱點。分簇路由協議的拓撲結構如圖1所示，整個網絡被隨機分成若干個簇，每個簇由一個簇頭節點和若干個成員節點構成，成員節點負責采集數據，并將數據發給對應的簇頭節點;簇頭節點負責進行數據的匯聚和壓縮，并通過一跳或者多跳的方式，將數據發送到基站（Base Station，BS）。

分簇路由協議的重點和核心內容是快速和有效的構建簇結構，本文通過對常用分簇型路由協議進行描述和對比分析，力求明確未來重點研究方向。

2 ? ?常用分簇型路由協議分析

2.1 ?LEACH協議

LEACH協議是首次針對WSN提出的一種自適應聚類路由協議[2]。LEACH協議采用了“輪”的概念，并將每輪通信過程分為簇建立階段和數據傳輸階段。在簇建立階段，重點實現簇頭選舉和成簇，簇頭選舉時，每個節點將生成0～1之間的一個隨機數，根據當前輪數計算閾值，如果閾值比隨機數大時，則被選舉為簇頭節點，當選的概率為：

（1）

其中，P是簇頭占總節點的比例，R是當前的輪數。簇頭節點將選舉結果廣播到整個網絡，使其余節點加入最近的簇。在數據傳輸階段，每個簇的成員節點依據TDMA時隙采集并發送數據給簇頭節點，簇頭節點接收簇內成員節點的數據并進行壓縮融合，然后通過一跳或者多跳的方式將數據匯聚到基站。

LEACH協議的優點：（1）采用分布式算法選舉簇頭，各節點的機會相同，可盡量平衡能量消耗。（2）在簇內的數據融合完成時，傳輸距離被減小，可在一定程度上節約能量。

LEACH協議的缺點：（1）簇頭的成本開銷大，需要每輪進行簇頭重選。（2）簇頭之間的負載不均衡，簇頭在整個網絡中分布不均，簇內成員節點分布不均。（3）簇內成員節點直接與簇頭交換數據，加快了簇頭的能量消耗，導致了每個簇的規模有限，不適合大規模網絡。

2.2 ?HEED協議

在簇頭選舉過程中，HEED協議主要依賴于基本參數和副參數[3]。基本參數是指所選擇節點的剩余能量，節點剩余能量越多，該節點成為簇頭節點的概率就越大;副參數是指簇內的通信代價，其主要目標是確保最終成簇和簇頭之間的負載平衡。在發送相關的競爭信息時，利用公式（2）計算節點的當選概率，即：

（2）

其中，Cprob與Pmin是固定值，Eresident表示節點的剩余能量，Emax表示節點的初始能量（最大值），為了防止收斂速度過慢，設置了剩余能量的最小比率。

與LEACH協議類似，HEED協議也采用了“輪”的概念，但與基本LEACH協議最大的區別是，HEED協議采用了多跳方式與基站通信，而LEACH協議采用的是單跳方式。

HEED協議的優點：（1）簇頭分布相對比較均勻，聚類效率高，網絡拓撲更科學。（2）簇頭選舉考慮了剩余能量的影響，引入基本參數、副參數的多重約束，更合理。

HEED協議的缺點：（1）每一輪簇重組都會產生較大的簇頭成本。（2）簇的覆蓋范圍是重疊的，簇間干擾相對嚴重。

2.3 ?EEUC協議

EEUC協議中簇頭選舉也考慮了剩余能量的影響[4]，其主要出發點是為了克服均勻分簇的不足、簇頭向基站轉發數據能量消耗大等不足。為了節約簇頭之間傳輸信息的能量，該協議使用非均勻分簇的競爭機制，使簇根據具體情況分為不同大小的簇，讓靠近基站的簇存在較少的成員并且具有小競爭半徑。簇半徑計算公式為：

（3）

其中，R0是候選簇頭競爭半徑的最大值;c是簇半徑控制參數，介于0～1之間;dmax是節點到BS的最大距離;dmin代表了節點到BS的最小距離;d（i，BS）代表簇頭i到BS的距離。

EEUC協議的優點：（1）簇頭選舉考慮了能耗的不平衡問題，延長了網絡的生命周期。（2）簇間的多跳通信減少了網絡流量。

EEUC協議的缺點：（1）簇生成過程復雜且成本較大。（2）相對不同基站、不同的簇半徑，數據采集與傳輸存在較大的隨機誤差。

2.4 ?PEGASIS協議

PEGASIS協議是在LEACH協議的基礎上改進而來的，該協議選擇了定期選擇簇頭的方式，同時節點根據地理位置被串入鏈，并由貪心算法實現[5]。在該協議中，節點只需要與距離它們最近的鄰居節點通信，并且下一個節點將采集到的自身數據和所接收的數據進行融合，然后傳送到目的節點。

PEGASIS協議主要包括兩個步驟：第一，利用貪婪算法創建鏈，并且選擇距離自身最近的鄰居節點作為下一跳節點;第二，數據傳輸階段中，在鏈路上數據按順序傳輸，并進行融合處理，最終將由鏈首將數據直接傳送給匯聚節點。其鏈結構示意如圖2所示。

PEGASIS協議的優點：（1）基于地理位置，降低了通信節點的平均距離，減少了簇的成本。（2）利用“令牌”確保數據傳輸的可靠性。（3）采用數據融合，減少了數據分發量，降低了能量消耗。

PEGASIS協議的缺點：（1）由于節點基于地理位置形成一條鏈，數據傳送擴展性大。（2）簇頭選擇基本上是一致的，造成簇間干擾大、開銷大。

3 ? ?常用分簇路由協議比較

綜上，本文分析了LEACH，HEED，EEUC，PEGASIS 4種分簇路由協議的基本思想、優勢和劣勢，結合影響協議的幾個因素，對其進行總體對比，如表1所示。

4 ? ?結語

根據分簇路由協議的特點，本文對LEACH，HEED，EEUC，PEGASIS 4種典型的分簇路由協議進行了分析，對比了其路由機制的優缺點，并且從簇頭選舉階段、成簇階段、簇維護成本、算法的穩定性等方面進行了總結與比較。結合該領域的研究現狀，指出了未來研究的方向。

[參考文獻]

[1]AKYILDIZ IF，SU W，SANKARASUBRAMANIAM Y，et al.A survey on sensor networks[J].IEEE Communications Magazine，2002（8）：102-114.

[2]WENDI R H，ANANTHA C，HARI B.Energy-efficient communication protocol for wireless sensor networks[C].Hawaii：Proceedings of the 33rd Annual Hawaii International Conference on System Sciences，2000.

[3]OSSAMA Y，SONIA F.HEED：a hybrid，energy-efficient，distributed clustering approach for ad hoc sensor networks[J].IEEE Transactions on Mobile Computing，2004（4）：366-379.

[4]LI C F，YE M，CHEN G H，et al.An energy-efficient unequal clustering mechanism for wireless sensor networks[C].Singapore：Proceedings of the 2nd IEEE International Conference on Mobile Ad hoc and Sensor Systems，2005.

[5]STEPHANIE L，CAULIGI S R.Pegasis：power efficient gathering in sensor information systems[C].San Francisco：Proceedings of the IEEE Aerospace Conference，2002.

Research on clustering routing protocol for wireless sensor networks

Liu Xing1， Yang Jihai1， Yang Tao1， Han Qing2

（1.State Grid Jiangxi Information & Telecommunication Company， Nanchang 330096， China;

2.School of Electrical Engineering， Northeast Electric Power University， Jilin 132012， China）

Abstract：In wireless sensor networks， clustering routing plays an important role in routing protocol， which is convenient for topology management， high energy efficiency and simple data fusion. In this paper， LEACH， HEED， EEUC， PEGASIS， which are typical clustering routing algorithms， are systematically described from three aspects of cluster head generation， cluster formation and cluster routing. The advantages and disadvantages of LEACH， HEED， EEUC， PEGASIS are compared from the aspects of network life cycle and node survival number. Combined with the research status in this field， the future research direction is pointed out.

Key words：wireless sensor work;clustering;routing protocol