1、傳感網分簇算法研究及其進展摘要:作為網絡拓撲控制的有效方式之一，分簇算法可顯著降低無線傳感器網絡的能量消耗，提高網絡吞吐率。文章基于無線傳感器網絡分簇的架構，對目前主流的分簇算法進行歸納分類。針對無線傳感器網絡分簇算法設計中存在的難點，文章給出了解決難點的部分成果，并對進一步的研究進行了展望。關鍵字:無線傳感器網絡；分簇算法；拓撲控制；簇頭英文摘要:As one of the efficient ways of network topology control, clustering algorithms can reduce the energy consumption of the net

2、work and obviously improve the throughput ratio. Based on the architecture of clustering in WSN, the article classifies the representative clustering algorithms. The article analyzes the difficulties and problems in the algorithm design and illustrates some of the results; and further research of th

3、is area is foreseen.英文關鍵字:wireless sensor network; clustering algorithm; topology control; cluster head基金項目：國家重點基礎研究發展規劃(“973”計劃)項目(2007CB310606)；東南大學移動通信國家重點實驗室自主研究課題資助項目(2008A08、2008B05b)       無線傳感器網絡(WSN)在軍事、環境監測、工業控制、智能家居和城市交通等方面都有重要的實用價值，已成為熱點研究領域之一1。對應于不同的應用需求，各種

4、WSN在硬件平臺、軟件系統和通信協議上都存在較大差異。從網絡拓撲的角度看，WSN可以被分為平面結構以及分簇結構兩大類。平面結構中WSN各節點的地位都是平等的，而在分簇結構中，網絡中的節點被劃分為若干個稱為簇的節點集合，每個簇通常由一個簇頭節點和多個成員節點組成，簇頭負責管理和控制簇成員節點的工作，同時負責簇內數據收集及簇間數據轉發。與平面結構相比，采用分簇結構的WSN具有能量效率高、可擴展性好等優點，但是如何選取簇頭、劃分簇類，需要合適的分簇算法加以解決。    適用于WSN的分簇算法已成為WSN研究領域的核心技術之一。1 WSN中的分簇架構  

5、;  在采用分簇結構的無線傳感器網絡中，網絡節點被劃分為若干個簇。每個簇通常由一個簇頭節點(CH)以及多個成員節點(MN)組成。成員節點只與簇頭通信，簇頭與簇頭構成高一級的虛擬骨干網，負責簇內的數據融合和簇間數據轉發。因為簇頭節點的能量消耗較大，通常采用周期性選擇簇頭節點的方法均衡網絡中節點能量的消耗。簇頭的集合形成連通統治集(CDS)，因為獲得最優CDS是NPC問題，因此實際提出的算法均為啟發式的。圖1給出了分簇結構以及簇內與簇間的數據流向。     WSN采用分簇結構具有如下一些顯著的優點： · 在滿足一定約束條件情況下

6、(例如覆蓋范圍與采樣精度要求等)，簇成員節點可以在某些時間段內關閉通信模塊，大幅度減少空閑等待狀況的能量消耗，因此可節省能量。 · 簇頭通常負責采集簇成員發送來的數據，這些數據具有較大的相關性，因此可以采用數據融合算法，在保證信息量的情況下降低數據通信量，降低數據轉發的能量開銷。 · 因為采用層次結構，簇成員只需了解到所屬簇頭的路由信息，簇頭只需了解簇頭間的路由信息，因此可降低路由協議的復雜度，減少路由表項數目，路由維護開銷也隨之降低。 · 具有較好的可擴展性能，更加適合于大規模WSN的應用場景。  2.1 集中式/分布式算法 

7、60;  根據是否存在一個中心控制節點(通常是基站)負責整個網絡的簇劃分，分簇算法可分為集中式與分布式兩類。典型的集中式算法有LEACH-C2、APTEEN3等。我們提出的基于徑向基函數(RBF)的分簇算法4也屬于此類。中心控制節點通常有持續的電源供應、較高的存儲與計算能力，并能獲得網絡的全局信息(如每個節點的位置以及剩余能量等)，因此可以采用復雜的算法獲得優化的分簇結果。但是由于普通無線傳感器節點能量有限，計算與通信能力不強，因此對于大型的WSN，集中式算法在靈活性、可擴展性以及健壯性等方面存在缺陷，例如很多集中式算法要求獲得節點的剩余能量，因為傳感器節點運行中能量不斷下降，所以必

8、須隔一段時間就得通知中心控制點更新剩余能量信息，這就造成大量額外數據包的傳輸，使算法的開銷過大。    與集中式算法不同，分布式算法一般只需要相鄰節點之間互相交換信息，甚至不考慮相鄰節點獨立作出判斷，這類算法簡單、高效、靈活，因此更適用于大規模WSN。目前大部分經典的WSN分簇算法如LEACH、HEED5等，都屬于分布式算法，Hausdorff算法6、響應式分布分簇算法(RDCA)7也屬于這一類。 2.2 基于地理位置/地理位置無關算法    根據是否需要借助GPS獲得節點的地理位置，可以將分簇算法分為基于地理位置的算法與地

9、理位置無關算法兩類。典型的基于地理位置的算法有GAF8等，其他大部分常見的分簇算法，如LEACH與HEED算法等，都不需要借助于地理位置信息。基于地理位置的算法有的需要獲得全局信息，有的只需要通過廣播包獲得相鄰節點的位置信息。因為傳感器網絡節點數量大，單個節點造價低、能量有限，而GPS模塊不但成本高而且會額外消耗節點能量，因此為每個節點都配備GPS模塊是不經濟的。通常的做法是在網絡中設置少量信標節點，一般是通過攜帶GPS定位設備獲得自身的精確位置，然后其他傳感器節點通過信標節點的位置信息根據一定的定位算法獲得自身的位置。常用的定位算法有到達時間(TOA)、到達時間差(TDOA)、接收信號強度指

10、示(RSSI)、到達角度(AOA)和距離向量-跳數(DV-Hop)9等。不過在室內、水下或森林等有障礙環境中無法使用GPS系統，使其應用受到一定限制。基于地理位置的分簇算法一般假設節點已知自身的精確位置，而如何獲得自身位置信息則不包括在算法內。 2.3 確定性/隨機性算法    在網絡拓撲結構與每個節點的剩余能量不變的情況下，根據分簇算法是否能取得確定結果，可將其分為確定性與隨機性算法。在確定性算法中，節點必須等待某個特定事件發生或某些特定節點已宣布自己的角色(CH還是MN)后，才能做出決定。例如DCA算法10必須等待所有權值高于自己的相鄰節點宣布成為C

11、H或者加入到某個簇后，才能確定自身是成為CH還是MN。確定性算法的一個不足之處就是收斂時間依賴于網絡規模，DCA算法的時間復雜度為O(d )，d 為網絡直徑(通常用跳數來定義)，在最差情況下(節點線性分布)，d 可達到n -1(n為節點個數)。此外網絡的魯棒性不好，如果一個節點在拓撲發現階段后失效，可能造成其相鄰節點陷入無限期等待。為消除這種現象，一些算法，例如ACE算法限制節點在一定次數(如5次后)結束循環等待11。    隨機性算法根據一定的概率確定節點是否成為簇頭。LEACH算法中節點成為簇頭的概率僅與過去若干輪次中節點自身的狀態有關，HEED算法中的概率與

12、剩余能量有關，還有一些算法同時考慮了節點度等多種參數。隨機性算法分簇結果的優化程度通常不如確定性算法，但是收斂速度較快，開銷較小，魯棒性好，特別適合于大規模網絡。 2.4 單層/多層算法    根據算法產生的最終拓撲結構，可分為單層和多層算法。單層算法只進行一次分簇，目前提出的大部分分簇算法，如LEACH、HEAD、GAF等都屬于此類，而多層算法在前一次分簇選舉出的簇頭基礎上繼續進行分簇，選舉出第二層簇頭和簇成員節點，隨后可以進行第三層、第四層等簇頭選舉。多層算法一般只用于超大規模WSN，算法較為復雜。文獻12提出了一種多層算法(層數從1到5)，該算法以

13、最小化系統整體能量消耗為目標，推導出系統整體能量消耗的解析式，然后通過數值計算求出不同節點密度條件下的最優解。 2.5 簇內單跳/多跳算法    根據簇內MN到CH的跳數，可分為簇內單跳與簇內多跳算法，也可采用單跳算法的MN直接與CH進行通信，而多跳算法中的MN可通過其他MH中繼與CH進行通信。LEACH、HEED等算法采用單跳方式，而Max-min D等算法使用多跳方式。    Mhatre等對簇內單跳和多跳的情況做了深入研究13，提出以簇內第一個節點死亡作為簇的生命周期(不考慮CH的能耗)并假設所有MN的初始能量相同。單

14、跳情況下，離CH越遠的MN越早耗盡能量；多跳情況下，如果MN的發射功率相同，則離CH最近的MN因為負擔的中繼任務最重故消耗的能量最多。其分析存在的缺陷是只考慮了節點發送以及接收狀態下消耗的能量，沒有考慮空閑狀態下的能量消耗。目前很多WSN引入節點睡眠/喚醒機制，在無感知以及數據傳送的情況下關閉射頻電路以節省能量。當引入這種機制后，網絡拓撲會發生動態變化，很難給出一個確定性的解析式，一般只能采用概率分析的方法并通過仿真得出結果。當采用單跳模式時，MN與CH的通信可以采用TDMA方式，每個MN分配一個時隙，數據傳送只在指配的時隙中進行，其余時間處于睡眠狀態，大大降低了節點處于空閑狀態的時間(如LE

15、ACH)。而采用多跳模式時，因為節點還需考慮數據中繼問題，不可避免會耗費較多的等待時間。從這一點上看，單跳方式與多跳方式相比具有一定優勢。3 分簇算法設計難點    從網絡協議分層上看，分簇算法可以看做是拓撲控制的一大類，位于MAC層與網絡層之間。在算法設計中，需要考慮網絡連通性、CH輪轉頻率、簇半徑優化以及節點同步等一系列問題，對這些問題的深入研究可以從跨層設計的角度，結合MAC層、網絡層甚至應用層進行。 3.1 連通性問題    WSN中，保持節點到基站的連通性是極為重要的。對于采用分簇結構的無線傳感器而言，連通性問題包

16、括MN到CH(簇內通信)以及CH到基站(簇間通信)兩個層次的連通性。如前所述，簇內通信分為單跳與多跳兩種模式，一般由成簇算法確保連通性問題。而簇間通信需要通過虛擬骨干網進行，根據構成虛擬骨干網的節點不同，可將簇間通信分為兩大類。大部分虛擬骨干網完全由CH節點構成(如HEED算法)，為保證連通性，這一類算法要求節點發射功率可調，且CH的密度和覆蓋范圍滿足一定的條件14；另一些虛擬骨干網則由CH和簇邊緣的網關節點(GN)構成，如CEC算法15，一般適用于使用固定發射功率的網絡。兩類方法相比，前者的優勢在于非CH節點在沒有感知及數據發送任務時可以進入睡眠狀態，因此更加節省能量。連通性所帶來的簇半徑以

17、及簇間通信范圍的優化選取問題仍然是分簇算法研究的一個重點。 3.2 MAC層設計    通常進行分簇算法分析和仿真時都假設信道是無沖突的，而在實際情況下，尤其是單信道環境下，沖突和干擾不可避免。分簇算法經常使用TDMA模式的MAC層協議，使用TDMA方式雖然能夠消除簇內通信沖突，對相鄰簇之間的簇間沖突卻無能為力，當CH為進行簇間通信而提高發射功率時，這種沖突帶來的影響更為明顯。使用CDMA方式可以使簇內通信與簇間通信并發進行成為可能，但CDMA器件價格昂貴，難以在強調低成本的無線傳感器節點中大規模使用。如何設計與選用合適的MAC層協議降低沖突與干擾，也是

18、分簇算法研究的難點之一。 3.3 簇頭輪換機制    WSN的設計以最大化網絡生命期為最終目標，因而使各節點盡可能均衡地消耗能量極為重要。而分簇算法中一般CH的能量消耗大大高于MN，容易造成CH節點因為能量耗盡而提前死亡，為避免這一情況出現，一種方式就是采用簇頭輪換機制，使各節點每隔一段時間輪流擔任簇頭，從而使各節點剩余能量盡可能接近相等。簇頭輪換機制通常獨立于分簇算法，與分簇算法互為補充。常見的簇頭輪換機制有被動與主動式兩種。前者每隔固定時間引發，后者需要預先設定一個閥值，當監視的參數低于或者超過某閥值時引發重新分簇，常見的閥值有節點剩余能量、節點度等

19、。無論是被動還是主動式簇頭輪換機制，選擇合適的參數都會對算法的最終結果產生重要影響。如果簇頭輪換過于頻繁，則會帶來大量的額外開銷和網絡中斷；如果簇頭輪換頻率過低，則可能造成某些節點能量過早耗盡。因此，只有進行合理的折中才能獲得最優化的網絡生命期。 3.4 節點休眠/喚醒機制    采用節點休眠/喚醒機制，使非活躍節點盡可能處于睡眠狀態可以大大延長節點電池壽命。WSN在節點部署時一般是高度冗余的，即只需要一部分節點處于活躍狀態就可以完成任務，這是引入休眠/喚醒機制的前提條件。    WSN是應用相關的，不同應用層業務適宜采用的

20、休眠/喚醒機制也有所不同。對于周期性數據采集網絡(例如用于環境監測的網絡)，非CH節點在不需要進行感知或者與CH通信時將盡可能地處于休眠狀態。對于突發事件監測網絡(例如用于森林防火、入侵檢測等)，CH可將所屬的MN劃分為若干個冗余組，通知各組輪流進入睡眠狀態，同時保持其中一個組處于活躍狀態。還有一種方式是在分簇之前就預先選擇一個可以覆蓋目標區域的節點集，對這些節點集內部的節點進行分簇，分簇產生的CH和MN始終處于活躍狀態，而節點集外的節點進入睡眠狀態以節省能量。4 新的分簇算法 4.1 Hausdorff算法    Hausdorff算法也是一種基于節點

21、位置、通信有效性和網絡聯通性的分布式數據收集算法。該算法分為3部分：首先，由Hausdorff算法將節點分成幾個靜態的簇，用歐幾里德距離來計算兩個點之間的距離，用Hausdorff距離來計算兩個點集之間的距離，該算法將Hausdorff距離作為分簇的量度。其次，在整個網絡生命中分簇只執行一次，而每個簇中的簇首是由簇中的成員最優地輪換調度，該算法基于節點的剩余能量和其周圍鄰居節點的接近程度，采用一種貪婪算法在每個周期選擇簇首。第3，簇首之間構成網絡骨架定期地收集、融合和轉發數據到基站，它們之間的通信是采用最小功耗路由算法，其中利用了Dijkstra最短路徑算法。圖2顯示了傳感器節點數目從300變

22、化到600時的Hausdorff分簇算法和HEED協議不同情況下的網絡生命期，圖2(a)和圖2(b)的縱坐標分別表示第一個節點與第二個節點死亡時所經歷的輪次，從圖2可以看出，無論節點的密度是多少，Hausdorff分簇算法的性能均優于HEED協議。  4.2 RDCA分簇算法    基于負載平衡的響應式分布分簇算法(RDCA)也屬于分布式算法。該算法對DCA算法進行了改進，不需預先得知節點自身及其他節點的位置信息，而僅根據局部拓撲信息快速進行分布式的簇頭選舉，并根據代價函數進行簇的劃分，適用于周期性獲取信息的WSN。分析與仿真表明，該算法具有良

23、好的負載平衡性能和較小的協議開銷，與LEACH協議相比，能夠減少能量消耗，網絡生存期大約延長了40%。圖3為相同拓撲環境和初始能量下DCA算法與RDCA算法(Closest)一次實驗的分簇結果，圖中清楚可見RDCA算法(Closest)具有更好的負載平衡性能。  4.3 基于RBF的分簇算法    該算法屬于集中式/基于地理位置的分簇算法，適用于較小規模的WSN。分簇決策由基站通過計算得出，同時在算法執行前每個節點均已獲知自己的地理位置。當基站收集到網絡中所有節點的剩余能量以及位置信息后，建立由輸出層、隱層、輸出層3個層次構成的RBF神經網絡對

24、每個節點成為簇頭的概率進行計算，其中輸入向量X由節點剩余能量、覆蓋半徑內的節點個數、節點至覆蓋半徑內其他節點距離的均方差、節點位置4個分量組成，RBF用于隱層，輸出向量Y包含該節點成為簇頭的概率。基站根據網絡中的全部節點個數確定簇頭個數k，并選出概率最高的k個節點成為本輪次的簇頭。算法所使用的RBF神經網絡結構如圖4所示。 5 結束語    作為網絡拓撲控制的有效方式之一，分簇算法的使用可以顯著降低通信開銷，并且有利于與數據融合等技術結合，進一步降低能量消耗。軟硬件技術的進一步提高使傳感器節點的計算能力增強而硬件成本下降，這也為引入性能更強而復雜度較高的

25、算法提供了前提條件。根據近年來分簇算法的發展趨勢，我們認為如下幾點值得進一步深入研究。    (1)更精確的仿真模型    目前的分簇算法研究更多的基于以時間為單位的能量消耗模型16。現在越來越多的節點可利用太陽能電池等能量收集技術進行能量補充，針對此類節點需要根據硬件參數設計特殊的節點能量模型。此外，目前在仿真中普遍采用的自由空間與多徑衰落模型過于簡單，在實際的網絡部署中還需要考慮天線高度、地形地貌、植被覆蓋等情況，采用更接近于實際使用環境的鏈路質量模型。    (2)異構網絡的分簇算法 &#

26、160;  具有更高計算能力、更多能量補充的節點在簇頭選舉過程中更易于成為簇頭。在實際應用的傳感器網絡系統中，存在多種異構節點。以節點異構為前提，設計兼有平面結構和分簇結構優點的新型數據傳輸模式，也是一個很有應用前景的研究方向。    (3)QoS性能    大量對WSN分簇算法的研究均以能量有效性及負載平衡作為算法性能的度量標準，但未來的研究應進一步考慮分簇算法對網絡QoS性能的影響，尤其是在數據流量動態變化的情況下。在涉及到圖像以及視頻傳輸的多媒體WSN中，設計能量感知的QoS分簇算法更加值得關注。  

27、;  此外，無線傳感器網絡作為一種與應用高度相關的網絡，引入跨層設計機制，與MAC、網絡層甚至應用層實現聯合優化，進一步提高網絡的容錯性，降低沖突與干擾，與休眠/喚醒機制相結合，與網絡覆蓋、數據融合等問題聯合考慮等，都是分簇算法需要進一步研究的課題。6 參考文獻1 AKYILDIZ I F, SU W, SANKARASUBRAMANIAM Y, et al. Wireless sensor networks: A surveyJ. Computer Networks Journal, 2002,38:393-422.2 HEINZELMAN W B, CHANDRAKASAN A

28、P, BALAKRISHNAN H. An application-specific protocol architecture for wireless microsensor networksJ. IEEE Transactions on Wireless Communications, 2002,1(4):660-670.3 MANJESHWAR A, AGRAWAL D P. APTEEN: A hybrid protocol for efficient routing and comprehensive information retrieval in wireless sensor

29、 networksC/Proceedings of 16th International Parallel and Distributed Processing Symposium(IPDPS02), Apr 15-19,2002,Fort Lauderdale, FL,USA.Los Alamitos, CA,USA:IEEE Computer Society, 2002:195-202.4 ZHU Xiaorong, SHEN Lianfeng. RBF-based cluster-head selection for wireless sensor networksJ. Journal

30、of Southeast University (English Edition), 2006,22(4):451-455.5 YOUNIS O, FALMY S. HEED: A hybrid, energy-efficient, distributed clustering approach for Ad hoc sensor networksJ. IEEE Transactions on Mobile Computing, 2004,3(4): 366-379.6 ZHU Xiaorong, SHEN Lianfeng, YUM T S P. Hausdorff clustering a

31、nd minimum energy routing for wireless sensor networksJ. IEEE Transactions on Vehicular Technology, 2009,58(2):990-997.7 胡靜, 沈連豐, 宋鐵成, 等. 新的無線傳感器網絡分簇算法J. 通信學報, 2008,29(7):20-26.8 XU Y, HEIDEMANN J, ESTRIN D. Geography-informed energy conservation for ad hoc routingC/Proceedings of   7th An

32、nual International Conference on Mobile Computing and Networking (MOBICOM01), Jul 16-21,2001, Rome, Italy. New York, NY,USA:ACM, 2001:70-84.9 HE T, HUANG C, BLUM B M, et al. Range-free localization schemes for large scale sensor networksC/Proceedings of 4th ACM International Symposium on Mobile Ad H

33、oc Networking and Computingin(MobiHoc03,Jun 1-3,2003, Annapolis,MD,USA.New York, NY, USA:ACM, 2003:81-95.10 BASAGNI S. Distributed clustering algorithm for ad-hoc networksC/Proceedings of the 1999 International Symposium on Parallel Architectures, Algorithms and Networks (ISPAN99), Jun 23-25,1999, F

34、remantle, Australia. Los Alamitos, CA,USA:IEEE Computer Society, 1999:310-315.11 CHAN H, PERRIG A. ACE: An emergent algorithm for highly uniform cluster formationC/Proceedings of the 1st European Workshop on Wireless Sensor Networks (EWSN04), Jan 19-21, 2004, Berlin, Germany. Los Alamitos, CA,USA:IE

35、EE Computer Society, 2004:154-171.12 BANDYOPADHYAY S, COYLE E J. An energy efficient hierarchical clustering algorithm for Wireless Sensor NetworksC. Proceedings of the 22nd Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM 03):Vol 3,Mar 30-Apr 3,2003, San Francisco, CA,USA. Piscataway, NJ,USA:IEEE, 2003:1713-1723.13 MHATRE V, ROSENBERG C. Design guideline for wireless sensor networks: communication, clustering and aggregation. Ad Hoc Networ