無線傳感器網絡的成簇算法

摘 要:如何合理、有效地利用成簇算法使得網絡節點具有均衡的負載和較小能耗率成為當前無線傳感器網絡研究領域的熱點問題之一。根據無線傳感器網絡的分簇機制，著重從簇首的選舉、簇組織和簇的路由三個方面系統地分析了當前典型的成簇算法，對算法的特點和適用情況進行了比較分析，并指出了目前算法存在的問題和需要進一步研究的內容。

關鍵詞:無線傳感器; 成簇算法; 路由; 簇

中圖分類號:TP393文獻標志碼:A

文章編號:1001-3695(2009)09-3222-05

doi:10.3969/j.issn.1001-3695.2009.09.006

Clustering algorithm in wireless sensor networks

WANG Sheng-cai ，LI Ai-hua ，WANG Tao ，ZHANG Bo2

(1.Second Artillery Engineering College， Xi’an 710025， China;2.96634 Unit in PLA， Nanchang 330201， China)

Abstract:One of the current hot topics in wireless sensor networks is how to make the nodes’ load more balanced and consuming energy rate lower by adopting new clustering algorithms reasonably and effectively. This paper analyzed the current classic algorithms by electing cluster heads， forming clusters， and clustering routing. Analyzed the character and applicability of the algorithms comparatively， and pointed out the existing problems and research trends.

Key words:wireless sensor networks(WSN); clustering algorithm; routing; cluster

隨著無線傳感器自組網絡規模的擴大，平面路由方案會因鏈路處理開銷的增加和動態反應速度的降低而變得不適用，解決辦法之一是采用成簇的路由方案。在成簇算法中，網絡由多個簇組成，每個簇包括簇首和成員兩種類型的節點，處于同一簇內的簇首和成員節點共同維護所在簇內的路由信息。簇首節點負責所管轄簇內拓撲信息的壓縮和融合處理，并與其他簇首節點交換處理后的拓撲信息，直到傳感數據傳送至基站[1]。

采用成簇的路由思路的目的是:a)通過減少參與路由計算的節點數目，減小路由表尺寸，降低交換路由信息所需的通信開銷和維護路由表所需的內存開銷[2];b)基于某種簇生成策略產生較為穩定的子網絡，減少拓撲結構變化對路由算法的影響[3];c)簇成員節點定期蘇醒上傳數據至簇首并融合，大大減少節點能耗和數據通信量，從而提高網絡壽命[4]。

1 無線傳感器網絡簇運算概述

學術界對Ad hoc網絡的研究比WSN要早，目前已經提出了很多針對Ad hoc網絡的分簇路由算法，如采用LCC(least cluster change)算法形成簇結構的CGSR協議、結合按需和主動路由策略的ZRP(zone routing protocol)算法等[1]，而無線傳感器網絡中的分簇算法正處于研究階段。同Ad hoc網相比，WSN中的分簇算法更側重于保持網絡整體能量消耗的均衡，避免出現“熱點”問題，最大化地延長網絡生存時間[5，6]。

LEACH是MIT的Heinzelman等人專門為WSN設計的低功耗自適應分層路由算法[7]，也是WSN中最早提出的成簇路由算法。它的基本思想是以循環的方式隨機選擇簇首節點，將整個網絡的能量負載平均分配到每個傳感器節點中，從而達到降低網絡能源消耗、提高網絡整體生存時間的目的。這個思想貫穿于后來的很多簇算法研究之中，成為簇運算的基點。

LEACH算法將簇的建立過程分為三個階段，即簇首節點的選擇、簇的組織和簇的連接 [6]。從目前的文獻來看，對簇算法的研究大多是從這三個方面著手。

2 簇首的選擇

成為簇首意味著要肩負額外的任務，即組織簇內媒體的接入、節點數據的融合和路由決策的選擇。這是一個密集型操作，所以它必須通過輪換所有節點的角色使簇首的能量不會消耗過多。為了能進行簇首的輪換，分簇算法不能只運行一次，而必須重復執行。例如，這種重復可以周期性出現或由節點的移動觸發。當然，合理地選擇周期和觸發閾值是一個很重要的優化問題[8]。

按照成簇的方式可以將傳感網絡分為分布式和集中式兩種類型。當網絡是分布式時，簇首選舉側重于節點能量的均衡;當網絡是集中式時，簇首選舉更側重于簇首分布的均勻性。

2.1 分布式網絡

在分布式網絡中，各節點具有同等地位，它們之間通過信息交互實現對鄰居節點的感知。在進行簇首選擇時，基本上都是圍繞著某個指標來進行，如ID號、剩余能量、節點度、權值、定時器和屬性等。通過這些指標的比較來進行簇首的選擇。這些策略中，有效果好的也有效果差的，有簡單的也有復雜的，但都是為了解決一個問題，那就是均衡各個節點的能量，讓網絡的壽命更長。

2.1.1 LEACH算法

LEACH算法[9]是最早也是最基本的分簇算法。簇首節點的選擇依據網絡中所需要的簇首節點總數和迄今為止每個節點已成為簇首的次數來決定。具體的選擇辦法是:每個傳感器節點隨機選擇0~1的一個值，如果選定的值小于某一個閾值T(n)，那么這個節點成為簇首節點。T(n)值計算如下:

T(n)=k/{N-k[r mod(N/k)]}若n∈G

0其他情況(1)

其中:N為網絡中傳感器節點的總數;k為一個回合網絡中的簇首節點數;r為已完成的回合數。

對于這種隨機選舉簇首的方法，需要得到簇首數與節點總數的最優比。考慮到與距離較遠的簇首節點通信時成本較高，所以增加幾個簇首的操作會迅速提高整體的能量效率，但當超過某個比值時，分簇的優點會慢慢消失。Heinzelman等人[7]經過計算認為最優值是5%。

2.1.2 LCA

LEACH在簇首的選舉機制中通過N/k次循環輪換了所有的節點，在一定程度上均衡了各個節點的能耗。但由于LEACH算法采用隨機的方式產生簇首，可能導致簇首節點的分布不均勻。在這種情況下，Baker等人[10]提出了基于節點ID判斷的成簇思想:a)每個節點廣播自身的ID并且監聽其他節點的傳播信息; b)節點廣播其監聽到的鄰居節點信息，直到每一個節點都知道它一跳和兩跳內鄰居節點的情況;c)在某個節點的一跳鄰居節點中擁有最大ID號的將成為簇首。

這種方法通過ID值的比較可以將簇首初步分開，至少能保證在節點一跳范圍內只存在一個簇首。

2.1.3 DCHS算法

LCA雖然初步解決了簇首分布不均的問題，但由于只有鄰居節點中有最大ID號的節點才能成為簇首，導致ID號越大的節點成為簇首的機會越大，也越容易耗盡能量。因而Handy等人[11]將節點剩余能量考慮到了成簇的過程中，形成了DCHS(deterministic cluster-head selection)算法，即將LEACH中的時間閾值改進為

T(n)=k/{N-k[r mod(N/k)]}×(Ecurrent/Emax)(2)

其中:Ecurrent為當前節點的能量，Emax為節點的最大能量。這種策略保證了有較多能量的節點有更大的機會成為簇首，從而均衡了整個網絡的能量消耗。

2.1.4 HEED算法

DCHS算法仍然采用了隨機策略，所不同的只是增大了能量高的節點成為簇首的概率，這雖然均衡了節點的能耗，但對簇之間的負載均衡無法解決，即各個簇的能耗率可能隨節點分布的不均而產生很大差別。Younis等人[12]提出了HEED(hybrid energy-efficient distributed clusting)算法，通過采用節點剩余能量和通信代價兩個指標選舉簇首，一方面保證了擁有能量多的節點有更大幾率成為簇首，另一方面保證了生成的簇具有大致均衡的能耗率。

算法分為三個階段，在初始化階段，所有節點設置一個初始的簇首概率值Cprob，并按式(3)計算其成為簇首的概率CHprob:

CHprob(r，0)=max{Cprob*Eresidual/Emax，pmin}(3)

其中:CHprob(r，0)是節點在第r輪第0次迭代成為簇首的概率，Eresidual是節點的剩余能量，Emax是節點的初始能量，pmin是概率底線值。

在迭代階段，節點按式(4)進行迭代直到CHprob(r，j)=1。迭代結束并聲明自己為簇首節點，其他未成為簇首的節點收到聲明后停止迭代。

CHprob(r，j)=2×CHprob(r，j-1)(4)

在最后階段，若非簇首節點收到多個簇首的聲明，將選擇通信代價低的簇加入，以達到簇間能耗盡可能均勻。

2.1.5 加權分簇算法

到目前為止，討論過的節點的指標都相當簡單，這些參數并不能完全表示節點作為簇首的各個方面的特性。而且，可能還有其他系統層強加給拓撲選擇的限制，如簇的大小或深度，而通常規定一個簇首能夠有效控制的簇大小是一件優化簇必須要做的事情。

Chatterjee等人[8，13]介紹了一個考慮了以下因素來計算節點權值的分簇算法:簇不應超過最大規模δ、電池功率、移動性(傾向于移動慢的節點)、鄰節點的接近程度(簇內成員的距離越小越好)。節點v的權值用公式表示為

Wv=w1dv-δ+w2∑u∈N(v)dist(v，u)+w3S(v)+w4T(v)(5)

其中:wi是非負權值因子，N(v)是v的鄰節點，S(v)是節點v的平均速率，T(v)是節點v已經作為簇首的時間。

實際的算法和上面討論過的那些基本一致，其中小權值優先。這個算法的一個令人感興趣的方面是它會在節點中自適應地輪換簇首的角色，以保證在這些節點中分擔負載。

2.1.6 EA(emergent algorithms)

上面的算法雖然復雜程度不一，但都存在一個與算法結合的明確目標，即依據某個指標來確定簇首。Chan Hao-wei等人[14]構建了一種可以不使用這種明顯目標的本地算法，即浮現算法，它能夠移動簇首節點，直到簇的分布是均勻的為止。

算法中，每個節點都會有三種狀態，即未分簇的、簇首和追隨者。如果在未分簇的節點附近沒有簇，它們會自發地變成簇首，這些簇首把它們的鄰節點征召為追隨者。如果一個簇首的追隨者能夠成為一個更好的簇首，如它有更多的追隨者并且與其他簇的重疊部分少，那么這個簇首就會退位。這個追隨者就會由舊簇首，即退位的簇首，推選為新簇首。實際上，簇首的角色在網絡中不斷移動。

這個算法的一個特性是對給定區域的壓縮接近于最緊六邊形分布，它的運行時間是恒定的(因為簇首是由分布式算法產生的)，與網絡的規模無關。

2.2集中式網絡

分布式算法通過對指標的比較可以均衡節點的能量，讓網絡節點盡量同時死亡，但是由于缺少全局信息，很難做到讓簇首均勻分布，導致部分簇首能量消耗過快。集中式網絡在此基礎上發揮了它掌握全局信息的優點，從地理位置、節點能量占網絡平均能量的比值等參數開展了大量對簇首均勻分布的思考。目前流行的如LEACH-C、GAF等，算法先用集中式選擇簇首使得算法具有較好的健壯性，然后又進行局部的簇首選舉算法，使得所選簇首在區域內分布較均勻，延長網絡的生命期。

2.2.1 LEACH系列算法

針對LEACH算法簇首分布不均的問題，Heinzelman等人[9]在LEACH的基礎上提出了一系列算法，包括LEACH-C、LEACH-F等，它們均采用集中式算法，在成簇階段各節點將自身位置信息和剩余能量匯報給基站，由基站根據各節點剩余能量占網絡總能量的比例等指標進行優化運算，并指導節點分布，選出合適的簇首，再向全網廣播。改進后節點Si在第r輪成為簇首的概率為

Pi(r)=min{k[Ei(r)/Etotal(r)]，1}(6)

其中:k表示簇首個數，Ei(r)表示節點Si在第r輪的剩余能量，Etotal(r)表示在第r輪全網的剩余能量。該方法不僅可以促使節點的能量均衡，還能改善簇首節點的分布。這兩種算法的不同之處在于，LEACH-C仍然采用定期成簇、簇首輪轉的策略，但LEACH-F一旦成簇后就不再組織簇，簇頭節點僅在本簇內輪轉，這樣雖然減少了開銷，但不能動態處理節點的加入、失敗和移動。

2.2.2 GAF算法

LEACH系列算法通過基站對各節點的地理位置、剩余能量的采集，達到了掌握全局的目的，但這需要消耗較多的通信能量和較大的延時。GAF(geographical adaptive fidelity)算法把監測區域劃分成虛擬單元格(圖1)，將節點按照地理位置信息劃入相應的單元格，在每個單元格中定期選舉產生一個簇首節點，并且簇內只有簇首節點保持活動，其他節點進入睡眠狀態[15]。與GAF算法類似的GS3[2]和Voronoi圖算法[16]也同樣采用預先從地理上劃分出相互隔離的區域，然后在小區域中選舉簇首的方法，所不同的是GS3構筑的是正六邊形的結構(圖2)，而Voronoi圖算法是進行Voronoi圖劃分。

3 簇組織算法

簇組織通常是基于傳感器節點的剩余能量和與簇首的接近程度來進行的。大部分與LEACH一樣，根據收到信號的強度決定加入哪個簇。隨著研究的深入，又產生了一些新的更適合的成簇方式，如上面講到的HEED算法，采用了一種基于通信代價的成簇方式，當節點落入多個簇首的覆蓋范圍時，選擇通信代價比較小的簇首加入，以達到簇的負載均衡。

3.1 DWEHC算法

在簇的組織過程中，一般簇內節點采用一跳的方式與簇首通信，但是當距離較遠時，這種方式的能耗仍然比較高，因而Mhatre等人[17]研究了什么時候應該在簇內使用多跳的問題，假設了一個非齊次的系統模型。其中簇首與遠處的基站直接通信，傳感器把自己的數據發送給簇首，并在簇首進行融合。這些傳感器要么與簇首直接通信，要么通過多跳進行通信。作者認為超過某個確定的距離就應該使用多跳，并提供了一個表達式來計算它，這個距離只由無線參數決定(尤其時路徑損耗系數)，并且與網絡特性相互獨立。

在這種情況下，Ding Ping等人[18]提出了DWEHC(distri-buted weight-based energy-efficient hierarchical clustering)算法，它是一種分布式的成簇算法，時間復雜度為O(1)。每個傳感器節點根據節點的剩余能量和與鄰居節點的接近程度確定權值，在所有鄰居節點中擁有最大權重的節點首先成為簇首，其他節點則成為成員節點。由于它們能直接與簇首通信，也稱為第一層成員節點。這些節點遍歷鄰居非簇首節點尋找到達簇首的最小通信代價路徑，并評估出是作為第一層節點好還是第二層節點好。若作為第二層節點更加節省能量，那么該成員節點將變為第二層成員節點，直到簇內形成最有效的拓撲結構。為了限制簇內信號轉發的層數，算法為每個簇都指派了一個區域，在區域之外的節點將加入別的簇，簇內拓撲如圖3所示。

3.2 PEGASIS和分層PEGASIS算法

與上面的多簇結構不同，PEGASIS協議[19]在傳感器節點中采用鏈式結構進行連接，運行時每個節點首先利用信號的強度來衡量其所有鄰居節點距離的遠近，在確定其最近鄰居的同時調整發送信號的強度，以便只有這個鄰居能夠聽到。其次，鏈中每個節點向鄰居節點發送和接收數據，并且只選擇一個節點作為鏈首向匯聚點傳輸數據。采集到的數據以點到點的方式傳送、融合，并最終被送到匯聚點。這種算法減小了LEACH在簇重構過程中產生的開銷，并且通過數據融合降低了收發過程的次數，從而降低了能量的消耗;但算法所構建的節點鏈中，元距離的節點會引起過多的數據延遲，而且鏈首節點的惟一性使得鏈首會成為瓶頸。

為此，Lindsy等人又在PEGASIS的基礎上提出了分層PEGASIS來降低數據包到匯聚點傳送過程中所引起的延時。該算法采用樹狀分層結構的方式，每一層選擇的節點向更高一級的節點傳送數據。要求在每個回合的數據采集中，給定層的節點都向附近的鄰居發送數據，所有接收數據的節點被提升為上一層的節點。依此類推，最后頂層只有一個節點被保留下來并成為鏈首節點。這種分層方式保證了數據的并行傳輸，并有效地降低了傳輸時延。

3.3 EEUCAA算法

目前，大多分簇都是盡量將簇大小分成一致，以滿足簇的負載均衡，但是在簇間通信時可能會出現熱點問題。因為某些距離基站比較近的簇首，除了需要承擔本簇內數據的收集、融合和傳輸任務，還需要為其他的簇首提供中繼數據的服務，能量消耗非常大。一旦這些簇首的能量耗盡，就會嚴重影響網絡的正常工作，因此，不等簇的概念應運而生。EEUCAA算法通過減小基站附近簇的規模(即增大基站附近簇的數量)來均衡熱點問題，取得了較好的效果。

a)網絡中具有較多能量的節點以一定的概率參與簇首的競爭，并根據與基站的距離，產生一個競爭范圍Rcomp

Rcomp=[1-c(dmax-d(si，BS))/(dmax-dmin)]R0comp(7)

其中:C為(0，1)間的常數，dmax、dmin分別為網絡中節點距離基站的最大與最小距離，d(si，BS)為節點si與基站之間的距離，R0comp為所允許的最大競爭范圍(預先設定)。

b)其余節點為了節能先進入休眠狀態，等待新選出的簇首廣播簇首消息，一旦監測到簇首廣播了簇首消息就進入工作狀態并加入該簇。

通過競爭的方式，最終成為簇首的節點應該滿足這樣的條件，即在它的競爭范圍Rcomp內不存在其他的簇首節點;當距離基站越近時，競爭范圍的取值越小，即競爭范圍隨著節點與基站間距的減小而減小，這樣可以保證在基站附近產生的簇的數目較多，而距離基站較遠的區域產生的簇的數目較少，使得在基站附近的簇首可以保留更多的能量用于簇間的數據轉發，從而延長網路的壽命，如圖4所示。

4 簇的路由

LEACH算法最大的優勢在于它將多個節點形成了一個集合，而只由簇首節點進行數據的傳輸，大大減少了能量的消耗和路由的復雜度。但它是在所有節點能夠與基站直接通信的假設下進行的，具有一定的局限性，能耗也很大。為此，很多學者對簇的路由算法進行了研究，目前，簇的路由有三種方式，即多層分簇、簇首多跳和設置網關節點。

4.1 HCC(hierarchical control clustering)算法

無線信道中，能量消耗E與距離d存在關系:E=kdn。其中k為常數，2≤n≤4。傳感器網絡中節點通常貼近地面，應用環境中有很多障礙物，接收天線能力有限，所以節點直接將數據傳送到基站將耗費大量的能量。由于LEACH的先天不足，一個很自然的改進策略就是在保持簇數量不變的前提下，減少直接向基站傳輸的節點數。

Bandyopadhyay建議，在傳感器節點將傳感器的數據報送遠端處理中心的情況下，可以使用多層分簇來節省能量[8]。他們從一個簡單的、隨機選舉簇首的算法開始。其中節點成為簇首的概率為p，簇的大小為k;沒有被這些簇覆蓋的節點將“被迫地”成為簇首。假設能量消耗和節點部署都是標準的，p和k的閉合解均可以通過解析的方法來求得。用這種隨機的算法能很容易地形成多個層:a)從第一層簇首中選出一些節點作為第二層簇首，并把這個消息向鄰居不多于k1跳的簇首節點通告;b)這些節點會加入第二層形成第二級簇。顯然，這還可以擴展到更多的層。通過處理中心發送數據時所需的最小能量可以確定pi和ki的最優值。收集數據時，每個節點把它的數據發送到上一級的簇首，進行數據融合并轉發。多層分簇的示意圖如圖5所示，這個方案在節省能量方面比其他分簇方案性能優越，而且這個算法的復雜度也比較低。

4.2 LEACH-M算法

多層分簇的方式在減少能量消耗方面起了不小的作用，但是它仍然是以假定所有節點都能與基站通信為前提，需要某個或某幾個節點直接向基站傳輸數據。在大型網絡中，這種方法將顯得不太現實，因而，將平面路由算法應用于簇首之間的路由成為改善網絡結構的一個方向。

當網絡是中小規模時，簇首節點并不多，這樣采用最簡單的泛洪策略就可以將數據傳輸出去。但是隨著網絡規模的擴大，這種泛洪策略就像在平面路由中一樣，可能會導致“內爆”現象，因而李巖等人[20]將DD算法應用到簇首的路由中，取得了較好的效果。

a)匯聚節點以廣播、多跳的方式向網絡中所有簇首發布命令，命令信息用含有任務類型、數據發送速率、時間戳等參數的興趣描述。每個簇首緩存接收到興趣，并通過記錄發來興趣的相應鄰居節點等來建立梯度。b)當節點采集到匹配數據時，通過梯度路徑發向匯聚點，匯聚點或中間節點可能收到經過多個鄰居節點的相同數據，中間節點利用本地化規則實現數據的再融合。c)匯聚點在收到這些低速數據后，向數據到達最快的鄰居簇首節點發送增強消息，增強消息表示匯聚節點要求高速率發送數據，據此構建數據發送的主路徑，數據以后就通過主路徑發送到匯聚節點，該算法在節能和減小延時方面效果明顯。

4.3 設置網關節點

數據在簇首之間進行傳播時，若簇首分布不均或者由于障礙物的阻隔，可能導致個別簇首相對孤立，不能與其余簇首建立起有效的連接。為了增加簇的連通性，一個有效且穩妥的辦法就是在相鄰簇間尋找一些能夠擔任中轉任務的網關節點，保證簇的可靠連通。

滑楠等人[21]建立了一種簇間網關路由的方法。設有兩個相鄰簇cluster 1和cluster 2，其簇首分別用CH1和CH2標志，用CM1和CM2分別標志兩個簇的任意成員，并假定路由建立過程由cluster 1發起。簇間路由算法包含四個并行過程，分別對應圖6中的四種連通方式。

這四個過程在應用中究竟采用哪一種路由方式，主要取決于鄰近簇首最先收到的請求信息來源于何種節點。若簇首CH2最先收到的信息來源于節點CM1，則說明簇首間不能直接連通，必須通過網關節點路由，對應過程3。這種方法對動態簇組織算法有很好的支持能力，但由于節點間協商的存在，增大了網絡的開銷。采用目前市場上流行的可調發射功率芯片可以簡化簇間路由，建立簇間的直接通信。

5 算法的比較分析

上述算法大多都是針對特定的應用而設計的，在不同的環境中表現出各自的特色和優勢，因此不能絕對地判斷哪種算法的優劣。表1對上述的算法進行了比較。

a)選擇簇首有三種方法。最簡單的方法就是按概率自我選擇，周期輪換。為了能提高算法的能量均衡:(a)在門限值中加入剩余能量是一個不錯的選擇，但是這種方法選擇的簇首過于隨機，在數據收集時浪費了太多的能量;(b)通過鄰居節點間的信息交互來達到對局部網絡的了解，從而選出合適的簇首，該方法具有較好的擴展性、較快的收斂速度和較低的能耗率，但算法比較復雜，時間延遲、網絡均衡仍然是一大挑戰[22];(c)基站節點通過收集各個傳感節點的能量和位置等信息來計算網絡最佳的簇首數量、大小和位置，這種方法生成的簇首均勻、能量均衡、健壯性好，但成簇開銷大，擴展性差、網絡流量以及信號干擾的概率都會增加，一般只適合中小型網絡。

b)簇的輪轉周期的確定。簇的建立階段會有大量能量開銷，且不能傳輸數據，從而導致事件延遲，所以盡可能縮短這個周期，增大工作階段和建立階段的比值是提高效率的有效手段，但每輪的周期又不能太長，否則對網絡的變化響應太慢。目前，采用固定周期或以某個量(如節點剩余能量)的百分比作為門限來實現網絡同步輪轉的方法比較常見，如果不用全網同步輪轉，則同步要求和網絡開銷會得到很大降低，這是一個值得研究的問題[23，24]。

c)簇組織在一般算法中都是根據信號的強弱來加入簇，如果簇首分布不均勻就可能導致簇間的負載不均衡，引入通信代價可以減弱這種不均衡，但同時也增加了開銷和算法的復雜度。采用簇內多跳是減小成簇開銷的一種有效方法，尤其是簇的通信半徑比較大，簇內節點較多的時候。當然要想延長網絡的壽命，還必須對網絡中的熱點進行考慮，采用小半徑成簇或不均勻簇是解決這個問題的常用方法。此外，利用分布式的特點建立更高效的啟發機制、通過節點之間的互動和信息反饋來分簇是目前重點研究的一個方向[25，26]。

d)由于簇首單跳向基站傳輸數據能耗過大且不能保證連通，采用簇間路由是一個理想的辦法。目前簇間路由最廣泛的方法是使用樹狀拓撲[27]或到基站的最小跳數來組織路由，但熱點問題的存在又極大限制了路由算法的發展。采用分層路由實際是LEACH算法和簇間路由的一種折中，在中小型網絡中具有很好的應用前景。

6 需要進一步研究的內容

本文總結了當前無線傳感器網絡分簇算法中最具代表性的工作，并將簇首選擇、簇的形成以及簇的路由三方面的算法進行了比較分析，總結了各自的特點和不足，點明了分簇算法的發展趨勢。分簇算法中需要進一步研究的內容概括如下:

a)設計兼有平面結構和分簇結構優點的新型數據傳輸模式是目前很有趣的一個研究方向。在某些基于簇的路由協議中，并沒有簇首的概念，每個節點直到它將轉發的下一個節點，將這類協議叫做基于虛擬簇的平面路由協議。這類協議既能有效地管理網絡拓撲結構，較好地處理節點的移動性，又能有效利用能量傳輸數據。

b)進一步提高算法的節能性。WSN通過高效的分簇算法形成合理的網絡結構，通過主動的能量管理阻止網絡連通性的下降，從而在保證數據可靠傳輸的前提下，延長網絡的生命周期。但僅僅考慮網絡層的節能是遠遠不夠的，將MAC層和路由層協議捆綁，用跨層技術來進一步節省功耗是一個值得關注的方向。

c)在簇內進行合理的數據融合。為避免浪費通信帶寬和能量、提高信息收集效率，采用數據融合是必要的手段。但如何引入簇內被測數據的相關性，使得相關性強的節點形成在一個簇中，從而提高數據壓縮率和融合率，還值得深入探索。此外，尋找網絡數據融合率和網絡延遲、魯棒性之間的合理折中，也是進一步提高網絡性能的必要保證。

d)研究符合實際應用環境的模型系統。一般認為網絡中的所有節點都具有相同的最大發射功率，但由于天線質量、地形等許多方面的差異，各個節點所形成的發射范圍各不相同，異構網絡相對于同構網絡而言是更現實的網絡模型[28]。但由于網絡的異構性給理論分析帶來了困難，人們對異構網絡的研究還比較少。這使得目前的研究結果普遍停留在仿真的水平，缺乏足夠的說服力。

參考文獻:

[1]于海斌，曾鵬，梁韋華.智能無線傳感器網絡系統[M].北京:科學出版社，2006.

[2]AKKAYA K， YOUNIS M. A survey on routing protocols for wireless sensor networks[J]. Ad hoc Networks， 2003， 3(5):325-349.

[3]HOU Y T， SHI Y， SHERALI H D， et al. On energy provisioning and relay node placement for wireless sensor networks[J]. IEEE Trans on Wireless Communications， 2005， 4(5):2579-2590.

[4]AL-KARAKI J N， KAMAL A E. Routing techniques in wireless sensor networks:a survey[J]. IEEE Wireless Communications， 2004， 11(6):6-28.

[5]李莉，董樹松， 溫向明.無線傳感器網絡中的分簇算法[J].無線通信技術，2006，15(3):47-51，62.

[6]沈波，張世永，鐘亦平.無線傳感器網絡分簇路由協議[J].軟件學報，2006，17(7):1588-1600.

[7]HEINZELMAN W R， CHANDRAKASAN A， BALAKRISHNAN H. Energy-efficient communication protocols for wireless microsensor networks[C]//Proc of the 33rd Hawaii International Conference on System Sciences. Washington DC:IEEE Computer Society， 2000.

[8]KARL H， WILLIG A. Protocols and architectures for wireless sensor networks[M]. Beijing:Publishing House of Electronics Industry， 2007.

[9]HEINEELMAN W， CHANDRAKASAN A， BALAKRISHNAN H. An application-specific protocol architecture for wireless microsensor networks[J]. IEEE Trans on Wireless Communications， 2002，1(4):660-670.

[10]BAKER D， EPHREMIDES A. The architectural organization of a mobile radio network via a distributed algorithm[J]. IEEE Trans on Communications， 1981， 29(11):1694-1701.

[11]HANDY M J， HAASE M， TIMMERMANN D. Low energy adaptive clustering hierarchy with deterministic cluster-head selection[C]//Proc of the 4th International Workshop on Mobile and Wireless Communications Network.2002:368-372.

[12]YOUNIS O， FAHMY S. HEED: a hybrid， energy-efficient distributed clustering approach for Ad hoc sensor networks[J]. IEEE Trans on Mobile Computing， 2004，3(4):366-379.

[13]CHATTERJEE M， DAS S K， TRUGUT D. WCA: a weighted clustering algorithm for mobile Ad hoc networks[J]. Cluster Computing Journal， 2002，5(2):193-204.

[14]CHAN Hao-wei， PERRIG A. ACE: an emergent algorithm for highly uniform cluster formation[C]//Proc of the 1st European Workshop on Wireless Sensor Networks. Berlin:Springer， 2004:154-171.

[15]孫利民，李建中 陳渝.無線傳感器網絡[M]. 北京:清華大學出版社，2005.

[16]王威，唐文勝，羅娟.分簇算法中簇首分布及可靠性問題研究[J].計算機工程與應用， 2007，43(27):133-136.

[17]MHATRE V， ROSENBERG C. Design guidelines for wireless sensor networks:communication， clustering and aggregation[J]. Ad hoc Networks， 2004，2(1):45-63.

[18]DING P， HOLLIDAY J. CELIK A. Distributed energy-efficient hierarchical clustering for wireless sensor networks[C]//Proc of the 1st IEEE International Conference on Distributed Computing in Sensor Systems. Berlin:Springer， 2005:322-339.

[19]LINDSEY S， RAGHAVENDRA C S. PEGASIS: power efficient gathe-ring in sensor information system[C]//Proc of IEEE Aerospace Conference. 2002:1125-1130.

[20]李巖，張曦煌，李彥中.基于LEACH算法的簇首多跳(LEACH-M)算法[J].計算機工程與設計，2007， 28(17):4158-4160.

[21]滑楠，史浩山，吳健，等.無線傳感器網絡簇間路由算法研究[J].計算機工程與應用，2005，41(30):125-129.

[22]湯宇時，胡國綿.基于適應度的簇劃分算法研究[J].計算機仿真，2008，25(2):172-174.

[23]KAWADIA V， KUMAR P R. Power control and clustering in Ad hoc networks[C]//Proc of IEEE Conference on Computer Communications[M]. New York: IEEE Press， 2003:459-469.

[24]陳聞杰，陳迅，高麗強.無線傳感器網絡成簇算法研究[J].小型微型計算機系統，2008，29(2):220-222.

[25]ESTRIN D， GOVINDAN R， HEIDEMANN J， et al. Next century challenges: scalable coordination in sensor networks[C]//Proc of ACM International Conference on Mobile Compting and Networking. New York:ACM Press， 1999:263-270.

[26]JIANG Ming-liang， LI Jin-yang， TAY Y C. Cluster based routing protocol(CBRP)[EB/OL]. (1999-08-14). http://www.math.nus.edu.sg/~mattyc/cbrp.txt.

[27]SONG Ci， GUIZANI M， SHARIF H. Adaptive clustering in wireless sensor networks by mining sensor energy data[J]. Computer Communications， 2007， 34(5):2968-2975.

[28]LI Xiang-yang， SONG Wen-zhan， WANG Yu. Localized topology control for heterogeneous wireless sensor networks[J]. ACM Trans on Sensor Networks， 2005， 2(1):129-153.