劉興 楊濟(jì)海 楊濤 韓晴

摘 ? 要：在無線傳感器網(wǎng)絡(luò)中，分簇型路由在路由協(xié)議中占據(jù)重要的地位，該協(xié)議方便拓?fù)浣Y(jié)構(gòu)管理，能源利用率高，數(shù)據(jù)融合簡單。文章從簇頭生成、簇形成和簇路由3個角度對典型的分簇路由算法LEACH，HEED，EEUC，PEGASIS進(jìn)行了系統(tǒng)描述，從網(wǎng)絡(luò)生命周期和節(jié)點(diǎn)存活數(shù)量等方面，對比了其優(yōu)缺點(diǎn)，結(jié)合該領(lǐng)域的研究現(xiàn)狀，指出了未來研究的方向。

關(guān)鍵詞：無線傳感器網(wǎng)絡(luò);分簇;路由協(xié)議

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

1 ? ?無線傳感器網(wǎng)絡(luò)分簇路由算法概述

與其他類型的路由協(xié)議相比，分簇路由協(xié)議具有更好的性能，是目前研究的重點(diǎn)和熱點(diǎn)。分簇路由協(xié)議的拓?fù)浣Y(jié)構(gòu)如圖1所示，整個網(wǎng)絡(luò)被隨機(jī)分成若干個簇，每個簇由一個簇頭節(jié)點(diǎn)和若干個成員節(jié)點(diǎn)構(gòu)成，成員節(jié)點(diǎn)負(fù)責(zé)采集數(shù)據(jù)，并將數(shù)據(jù)發(fā)給對應(yīng)的簇頭節(jié)點(diǎn);簇頭節(jié)點(diǎn)負(fù)責(zé)進(jìn)行數(shù)據(jù)的匯聚和壓縮，并通過一跳或者多跳的方式，將數(shù)據(jù)發(fā)送到基站（Base Station，BS）。

分簇路由協(xié)議的重點(diǎn)和核心內(nèi)容是快速和有效的構(gòu)建簇結(jié)構(gòu)，本文通過對常用分簇型路由協(xié)議進(jìn)行描述和對比分析，力求明確未來重點(diǎn)研究方向。

2 ? ?常用分簇型路由協(xié)議分析

2.1 ?LEACH協(xié)議

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

（1）

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

LEACH協(xié)議的優(yōu)點(diǎn)：（1）采用分布式算法選舉簇頭，各節(jié)點(diǎn)的機(jī)會相同，可盡量平衡能量消耗。（2）在簇內(nèi)的數(shù)據(jù)融合完成時，傳輸距離被減小，可在一定程度上節(jié)約能量。

LEACH協(xié)議的缺點(diǎn)：（1）簇頭的成本開銷大，需要每輪進(jìn)行簇頭重選。（2）簇頭之間的負(fù)載不均衡，簇頭在整個網(wǎng)絡(luò)中分布不均，簇內(nèi)成員節(jié)點(diǎn)分布不均。（3）簇內(nèi)成員節(jié)點(diǎn)直接與簇頭交換數(shù)據(jù)，加快了簇頭的能量消耗，導(dǎo)致了每個簇的規(guī)模有限，不適合大規(guī)模網(wǎng)絡(luò)。

2.2 ?HEED協(xié)議

在簇頭選舉過程中，HEED協(xié)議主要依賴于基本參數(shù)和副參數(shù)[3]。基本參數(shù)是指所選擇節(jié)點(diǎn)的剩余能量，節(jié)點(diǎn)剩余能量越多，該節(jié)點(diǎn)成為簇頭節(jié)點(diǎn)的概率就越大;副參數(shù)是指簇內(nèi)的通信代價(jià)，其主要目標(biāo)是確保最終成簇和簇頭之間的負(fù)載平衡。在發(fā)送相關(guān)的競爭信息時，利用公式（2）計(jì)算節(jié)點(diǎn)的當(dāng)選概率，即：

（2）

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

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

HEED協(xié)議的優(yōu)點(diǎn)：（1）簇頭分布相對比較均勻，聚類效率高，網(wǎng)絡(luò)拓?fù)涓茖W(xué)。（2）簇頭選舉考慮了剩余能量的影響，引入基本參數(shù)、副參數(shù)的多重約束，更合理。

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

2.3 ?EEUC協(xié)議

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

（3）

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

EEUC協(xié)議的優(yōu)點(diǎn)：（1）簇頭選舉考慮了能耗的不平衡問題，延長了網(wǎng)絡(luò)的生命周期。（2）簇間的多跳通信減少了網(wǎng)絡(luò)流量。

EEUC協(xié)議的缺點(diǎn)：（1）簇生成過程復(fù)雜且成本較大。（2）相對不同基站、不同的簇半徑，數(shù)據(jù)采集與傳輸存在較大的隨機(jī)誤差。

2.4 ?PEGASIS協(xié)議

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

PEGASIS協(xié)議主要包括兩個步驟：第一，利用貪婪算法創(chuàng)建鏈，并且選擇距離自身最近的鄰居節(jié)點(diǎn)作為下一跳節(jié)點(diǎn);第二，數(shù)據(jù)傳輸階段中，在鏈路上數(shù)據(jù)按順序傳輸，并進(jìn)行融合處理，最終將由鏈?zhǔn)讓?shù)據(jù)直接傳送給匯聚節(jié)點(diǎn)。其鏈結(jié)構(gòu)示意如圖2所示。

PEGASIS協(xié)議的優(yōu)點(diǎn)：（1）基于地理位置，降低了通信節(jié)點(diǎn)的平均距離，減少了簇的成本。（2）利用“令牌”確保數(shù)據(jù)傳輸?shù)目煽啃?。?）采用數(shù)據(jù)融合，減少了數(shù)據(jù)分發(fā)量，降低了能量消耗。

PEGASIS協(xié)議的缺點(diǎn)：（1）由于節(jié)點(diǎn)基于地理位置形成一條鏈，數(shù)據(jù)傳送擴(kuò)展性大。（2）簇頭選擇基本上是一致的，造成簇間干擾大、開銷大。

3 ? ?常用分簇路由協(xié)議比較

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

4 ? ?結(jié)語

根據(jù)分簇路由協(xié)議的特點(diǎn)，本文對LEACH，HEED，EEUC，PEGASIS 4種典型的分簇路由協(xié)議進(jìn)行了分析，對比了其路由機(jī)制的優(yōu)缺點(diǎn)，并且從簇頭選舉階段、成簇階段、簇維護(hù)成本、算法的穩(wěn)定性等方面進(jìn)行了總結(jié)與比較。結(jié)合該領(lǐng)域的研究現(xiàn)狀，指出了未來研究的方向。

[參考文獻(xiàn)]

[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