胡　靜　沈連豐

摘要:作為網絡拓撲控制的有效方式之一,分簇算法可顯著降低無線傳感器網絡的能量消耗,提高網絡吞吐率。文章基于無線傳感器網絡分簇的架構,對目前主流的分簇算法進行歸納分類。針對無線傳感器網絡分簇算法設計中存在的難點,文章給出了解決難點的部分成果,并對進一步的研究進行了展望。

關鍵詞:無線傳感器網絡;分簇算法;拓撲控制;簇頭

Abstract: As one of the efficient ways of network topology control, clustering algorithms can reduce the energy consumption of the network 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 this area is foreseen.

Key words: wireless sensor network; clustering algorithm; topology control; cluster head

無線傳感器網絡(WSN)在軍事、環(huán)境監(jiān)測、工業(yè)控制、智能家居和城市交通等方面都有重要的實用價值,已成為熱點研究領域之一[1]。對應于不同的應用需求,各種WSN在硬件平臺、軟件系統和通信協議上都存在較大差異。從網絡拓撲的角度看,WSN可以被分為平面結構以及分簇結構兩大類。平面結構中WSN各節(jié)點的地位都是平等的,而在分簇結構中,網絡中的節(jié)點被劃分為若干個稱為簇的節(jié)點集合,每個簇通常由一個簇頭節(jié)點和多個成員節(jié)點組成,簇頭負責管理和控制簇成員節(jié)點的工作,同時負責簇內數據收集及簇間數據轉發(fā)。與平面結構相比,采用分簇結構的WSN具有能量效率高、可擴展性好等優(yōu)點,但是如何選取簇頭、劃分簇類,需要合適的分簇算法加以解決。

適用于WSN的分簇算法已成為WSN研究領域的核心技術之一。

1 WSN中的分簇架構

在采用分簇結構的無線傳感器網絡中,網絡節(jié)點被劃分為若干個簇。每個簇通常由一個簇頭節(jié)點(CH)以及多個成員節(jié)點(MN)組成。成員節(jié)點只與簇頭通信,簇頭與簇頭構成高一級的虛擬骨干網,負責簇內的數據融合和簇間數據轉發(fā)。因為簇頭節(jié)點的能量消耗較大,通常采用周期性選擇簇頭節(jié)點的方法均衡網絡中節(jié)點能量的消耗。簇頭的集合形成連通統治集(CDS),因為獲得最優(yōu)CDS是NPC問題,因此實際提出的算法均為啟發(fā)式的。圖1給出了分簇結構以及簇內與簇間的數據流向。

WSN采用分簇結構具有如下一些顯著的優(yōu)點:

●在滿足一定約束條件情況下(例如覆蓋范圍與采樣精度要求等),簇成員節(jié)點可以在某些時間段內關閉通信模塊,大幅度減少空閑等待狀況的能量消耗,因此可節(jié)省能量。

●簇頭通常負責采集簇成員發(fā)送來的數據,這些數據具有較大的相關性,因此可以采用數據融合算法,在保證信息量的情況下降低數據通信量,降低數據轉發(fā)的能量開銷。

●因為采用層次結構,簇成員只需了解到所屬簇頭的路由信息,簇頭只需了解簇頭間的路由信息,因此可降低路由協議的復雜度,減少路由表項數目,路由維護開銷也隨之降低。

●具有較好的可擴展性能,更加適合于大規(guī)模WSN的應用場景。

2 算法分類

國內外學者已經提出了大量分簇算法,分別適應于不同的設計目標與應用環(huán)境。根據不同的分類標準,分簇算法可以有多種分類方法。例如,以簇形成是否存在集中控制,可劃分為集中式/分布式算法;以是否需要預先獲得全球定位系統(GPS)信息,可劃分為基于地理位置/不基于地理信息的算法;以每次分簇是否存在一個確定的結果,可劃分為確定性/隨機性算法,等等。需要指出的是,各種分類方法之間可能互相重疊,即一個特定的分簇算法可以同時具有不同方面的分類特性,例如從圖1所示的分簇結構中可以看到該算法屬于單層、簇內單跳、簇間多跳。

2.1 集中式/分布式算法

根據是否存在一個中心控制節(jié)點(通常是基站)負責整個網絡的簇劃分,分簇算法可分為集中式與分布式兩類。典型的集中式算法有LEACH-C[2]、APTEEN[3]等。我們提出的基于徑向基函數(RBF)的分簇算法[4]也屬于此類。中心控制節(jié)點通常有持續(xù)的電源供應、較高的存儲與計算能力,并能獲得網絡的全局信息(如每個節(jié)點的位置以及剩余能量等),因此可以采用復雜的算法獲得優(yōu)化的分簇結果。但是由于普通無線傳感器節(jié)點能量有限,計算與通信能力不強,因此對于大型的WSN,集中式算法在靈活性、可擴展性以及健壯性等方面存在缺陷,例如很多集中式算法要求獲得節(jié)點的剩余能量,因為傳感器節(jié)點運行中能量不斷下降,所以必須隔一段時間就得通知中心控制點更新剩余能量信息,這就造成大量額外數據包的傳輸,使算法的開銷過大。

與集中式算法不同,分布式算法一般只需要相鄰節(jié)點之間互相交換信息,甚至不考慮相鄰節(jié)點獨立作出判斷,這類算法簡單、高效、靈活,因此更適用于大規(guī)模WSN。目前大部分經典的WSN分簇算法如LEACH、HEED[5]等,都屬于分布式算法,Hausdorff算法[6]、響應式分布分簇算法(RDCA)[7]也屬于這一類。

2.2 基于地理位置/地理位置無關算法

根據是否需要借助GPS獲得節(jié)點的地理位置,可以將分簇算法分為基于地理位置的算法與地理位置無關算法兩類。典型的基于地理位置的算法有GAF[8]等,其他大部分常見的分簇算法,如LEACH與HEED算法等,都不需要借助于地理位置信息?；诘乩砦恢玫乃惴ㄓ械男枰@得全局信息,有的只需要通過廣播包獲得相鄰節(jié)點的位置信息。因為傳感器網絡節(jié)點數量大,單個節(jié)點造價低、能量有限,而GPS模塊不但成本高而且會額外消耗節(jié)點能量,因此為每個節(jié)點都配備GPS模塊是不經濟的。通常的做法是在網絡中設置少量信標節(jié)點,一般是通過攜帶GPS定位設備獲得自身的精確位置,然后其他傳感器節(jié)點通過信標節(jié)點的位置信息根據一定的定位算法獲得自身的位置。常用的定位算法有到達時間(TOA)、到達時間差(TDOA)、接收信號強度指示(RSSI)、到達角度(AOA)和距離向量-跳數(DV-Hop)[9]等。不過在室內、水下或森林等有障礙環(huán)境中無法使用GPS系統,使其應用受到一定限制。基于地理位置的分簇算法一般假設節(jié)點已知自身的精確位置,而如何獲得自身位置信息則不包括在算法內。

2.3 確定性/隨機性算法

在網絡拓撲結構與每個節(jié)點的剩余能量不變的情況下,根據分簇算法是否能取得確定結果,可將其分為確定性與隨機性算法。在確定性算法中,節(jié)點必須等待某個特定事件發(fā)生或某些特定節(jié)點已宣布自己的角色(CH還是MN)后,才能做出決定。例如DCA算法[10]必須等待所有權值高于自己的相鄰節(jié)點宣布成為CH或者加入到某個簇后,才能確定自身是成為CH還是MN。確定性算法的一個不足之處就是收斂時間依賴于網絡規(guī)模,DCA算法的時間復雜度為O(d ),d 為網絡直徑(通常用跳數來定義),在最差情況下(節(jié)點線性分布),d 可達到

n -1(n為節(jié)點個數)。此外網絡的魯棒性不好,如果一個節(jié)點在拓撲發(fā)現階段后失效,可能造成其相鄰節(jié)點陷入無限期等待。為消除這種現象,一些算法,例如ACE算法限制節(jié)點在一定次數(如5次后)結束循環(huán)等待[11]。

隨機性算法根據一定的概率確定節(jié)點是否成為簇頭。LEACH算法中節(jié)點成為簇頭的概率僅與過去若干輪次中節(jié)點自身的狀態(tài)有關,HEED算法中的概率與剩余能量有關,還有一些算法同時考慮了節(jié)點度等多種參數。隨機性算法分簇結果的優(yōu)化程度通常不如確定性算法,但是收斂速度較快,開銷較小,魯棒性好,特別適合于大規(guī)模網絡。

2.4 單層/多層算法

根據算法產生的最終拓撲結構,可分為單層和多層算法。單層算法只進行一次分簇,目前提出的大部分分簇算法,如LEACH、HEAD、GAF等都屬于此類,而多層算法在前一次分簇選舉出的簇頭基礎上繼續(xù)進行分簇,選舉出第二層簇頭和簇成員節(jié)點,隨后可以進行第三層、第四層等簇頭選舉。多層算法一般只用于超大規(guī)模WSN,算法較為復雜。文獻[12]提出了一種多層算法(層數從1到5),該算法以最小化系統整體能量消耗為目標,推導出系統整體能量消耗的解析式,然后通過數值計算求出不同節(jié)點密度條件下的最優(yōu)解。

2.5 簇內單跳/多跳算法

根據簇內MN到CH的跳數,可分為簇內單跳與簇內多跳算法,也可采用單跳算法的MN直接與CH進行通信,而多跳算法中的MN可通過其他MH中繼與CH進行通信。LEACH、HEED等算法采用單跳方式,而Max-min D等算法使用多跳方式。

Mhatre等對簇內單跳和多跳的情況做了深入研究[13],提出以簇內第一個節(jié)點死亡作為簇的生命周期(不考慮CH的能耗)并假設所有MN的初始能量相同。單跳情況下,離CH越遠的MN越早耗盡能量;多跳情況下,如果MN的發(fā)射功率相同,則離CH最近的MN因為負擔的中繼任務最重故消耗的能量最多。其分析存在的缺陷是只考慮了節(jié)點發(fā)送以及接收狀態(tài)下消耗的能量,沒有考慮空閑狀態(tài)下的能量消耗。目前很多WSN引入節(jié)點睡眠/喚醒機制,在無感知以及數據傳送的情況下關閉射頻電路以節(jié)省能量。當引入這種機制后,網絡拓撲會發(fā)生動態(tài)變化,很難給出一個確定性的解析式,一般只能采用概率分析的方法并通過仿真得出結果。當采用單跳模式時,MN與CH的通信可以采用TDMA方式,每個MN分配一個時隙,數據傳送只在指配的時隙中進行,其余時間處于睡眠狀態(tài),大大降低了節(jié)點處于空閑狀態(tài)的時間(如LEACH)。而采用多跳模式時,因為節(jié)點還需考慮數據中繼問題,不可避免會耗費較多的等待時間。從這一點上看,單跳方式與多跳方式相比具有一定優(yōu)勢。

3 分簇算法設計難點

從網絡協議分層上看,分簇算法可以看做是拓撲控制的一大類,位于MAC層與網絡層之間。在算法設計中,需要考慮網絡連通性、CH輪轉頻率、簇半徑優(yōu)化以及節(jié)點同步等一系列問題,對這些問題的深入研究可以從跨層設計的角度,結合MAC層、網絡層甚至應用層進行。

3.1 連通性問題

WSN中,保持節(jié)點到基站的連通性是極為重要的。對于采用分簇結構的無線傳感器而言,連通性問題包括MN到CH(簇內通信)以及CH到基站(簇間通信)兩個層次的連通性。如前所述,簇內通信分為單跳與多跳兩種模式,一般由成簇算法確保連通性問題。而簇間通信需要通過虛擬骨干網進行,根據構成虛擬骨干網的節(jié)點不同,可將簇間通信分為兩大類。大部分虛擬骨干網完全由CH節(jié)點構成(如HEED算法),為保證連通性,這一類算法要求節(jié)點發(fā)射功率可調,且CH的密度和覆蓋范圍滿足一定的條件[14];另一些虛擬骨干網則由CH和簇邊緣的網關節(jié)點(GN)構成,如CEC算法[15],一般適用于使用固定發(fā)射功率的網絡。兩類方法相比,前者的優(yōu)勢在于非CH節(jié)點在沒有感知及數據發(fā)送任務時可以進入睡眠狀態(tài),因此更加節(jié)省能量。連通性所帶來的簇半徑以及簇間通信范圍的優(yōu)化選取問題仍然是分簇算法研究的一個重點。

3.2 MAC層設計

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

3.3 簇頭輪換機制

WSN的設計以最大化網絡生命期為最終目標,因而使各節(jié)點盡可能均衡地消耗能量極為重要。而分簇算法中一般CH的能量消耗大大高于MN,容易造成CH節(jié)點因為能量耗盡而提前死亡,為避免這一情況出現,一種方式就是采用簇頭輪換機制,使各節(jié)點每隔一段時間輪流擔任簇頭,從而使各節(jié)點剩余能量盡可能接近相等。簇頭輪換機制通常獨立于分簇算法,與分簇算法互為補充。常見的簇頭輪換機制有被動與主動式兩種。前者每隔固定時間引發(fā),后者需要預先設定一個閥值,當監(jiān)視的參數低于或者超過某閥值時引發(fā)重新分簇,常見的閥值有節(jié)點剩余能量、節(jié)點度等。無論是被動還是主動式簇頭輪換機制,選擇合適的參數都會對算法的最終結果產生重要影響。如果簇頭輪換過于頻繁,則會帶來大量的額外開銷和網絡中斷;如果簇頭輪換頻率過低,則可能造成某些節(jié)點能量過早耗盡。因此,只有進行合理的折中才能獲得最優(yōu)化的網絡生命期。

3.4 節(jié)點休眠/喚醒機制

采用節(jié)點休眠/喚醒機制,使非活躍節(jié)點盡可能處于睡眠狀態(tài)可以大大延長節(jié)點電池壽命。WSN在節(jié)點部署時一般是高度冗余的,即只需要一部分節(jié)點處于活躍狀態(tài)就可以完成任務,這是引入休眠/喚醒機制的前提條件。

WSN是應用相關的,不同應用層業(yè)務適宜采用的休眠/喚醒機制也有所不同。對于周期性數據采集網絡(例如用于環(huán)境監(jiān)測的網絡),非CH節(jié)點在不需要進行感知或者與CH通信時將盡可能地處于休眠狀態(tài)。對于突發(fā)事件監(jiān)測網絡(例如用于森林防火、入侵檢測等),CH可將所屬的MN劃分為若干個冗余組,通知各組輪流進入睡眠狀態(tài),同時保持其中一個組處于活躍狀態(tài)。還有一種方式是在分簇之前就預先選擇一個可以覆蓋目標區(qū)域的節(jié)點集,對這些節(jié)點集內部的節(jié)點進行分簇,分簇產生的CH和MN始終處于活躍狀態(tài),而節(jié)點集外的節(jié)點進入睡眠狀態(tài)以節(jié)省能量。

4 新的分簇算法

4.1 Hausdorff算法

Hausdorff算法也是一種基于節(jié)點位置、通信有效性和網絡聯通性的分布式數據收集算法。該算法分為3部分:首先,由Hausdorff算法將節(jié)點分成幾個靜態(tài)的簇,用歐幾里德距離來計算兩個點之間的距離,用Hausdorff距離來計算兩個點集之間的距離,該算法將Hausdorff距離作為分簇的量度。其次,在整個網絡生命中分簇只執(zhí)行一次,而每個簇中的簇首是由簇中的成員最優(yōu)地輪換調度,該算法基于節(jié)點的剩余能量和其周圍鄰居節(jié)點的接近程度,采用一種貪婪算法在每個周期選擇簇首。第3,簇首之間構成網絡骨架定期地收集、融合和轉發(fā)數據到基站,它們之間的通信是采用最小功耗路由算法,其中利用了Dijkstra最短路徑算法。圖2顯示了傳感器節(jié)點數目從300變化到600時的Hausdorff分簇算法和HEED協議不同情況下的網絡生命期,圖2(a)和圖2(b)的縱坐標分別表示第一個節(jié)點與第二個節(jié)點死亡時所經歷的輪次,從圖2可以看出,無論節(jié)點的密度是多少,Hausdorff分簇算法的性能均優(yōu)于HEED協議。

4.2 RDCA分簇算法

基于負載平衡的響應式分布分簇算法(RDCA)也屬于分布式算法。該算法對DCA算法進行了改進,不需預先得知節(jié)點自身及其他節(jié)點的位置信息,而僅根據局部拓撲信息快速進行分布式的簇頭選舉,并根據代價函數進行簇的劃分,適用于周期性獲取信息的WSN。分析與仿真表明,該算法具有良好的負載平衡性能和較小的協議開銷,與LEACH協議相比,能夠減少能量消耗,網絡生存期大約延長了40%。圖3為相同拓撲環(huán)境和初始能量下DCA算法與RDCA算法(Closest)一次實驗的分簇結果,圖中清楚可見RDCA算法(Closest)具有更好的負載平衡性能。

4.3 基于RBF的分簇算法

該算法屬于集中式/基于地理位置的分簇算法,適用于較小規(guī)模的WSN。分簇決策由基站通過計算得出,同時在算法執(zhí)行前每個節(jié)點均已獲知自己的地理位置。當基站收集到網絡中所有節(jié)點的剩余能量以及位置信息后,建立由輸出層、隱層、輸出層3個層次構成的RBF神經網絡對每個節(jié)點成為簇頭的概率進行計算,其中輸入向量X由節(jié)點剩余能量、覆蓋半徑內的節(jié)點個數、節(jié)點至覆蓋半徑內其他節(jié)點距離的均方差、節(jié)點位置4個分量組成,RBF用于隱層,輸出向量Y包含該節(jié)點成為簇頭的概率?；靖鶕W絡中的全部節(jié)點個數確定簇頭個數k,并選出概率最高的k個節(jié)點成為本輪次的簇頭。算法所使用的RBF神經網絡結構如圖4所示。

5 結束語

作為網絡拓撲控制的有效方式之一,分簇算法的使用可以顯著降低通信開銷,并且有利于與數據融合等技術結合,進一步降低能量消耗。軟硬件技術的進一步提高使傳感器節(jié)點的計算能力增強而硬件成本下降,這也為引入性能更強而復雜度較高的算法提供了前提條件。根據近年來分簇算法的發(fā)展趨勢,我們認為如下幾點值得進一步深入研究。

(1)更精確的仿真模型

目前的分簇算法研究更多的基于以時間為單位的能量消耗模型[16]。現在越來越多的節(jié)點可利用太陽能電池等能量收集技術進行能量補充,針對此類節(jié)點需要根據硬件參數設計特殊的節(jié)點能量模型。此外,目前在仿真中普遍采用的自由空間與多徑衰落模型過于簡單,在實際的網絡部署中還需要考慮天線高度、地形地貌、植被覆蓋等情況,采用更接近于實際使用環(huán)境的鏈路質量模型。

(2)異構網絡的分簇算法

具有更高計算能力、更多能量補充的節(jié)點在簇頭選舉過程中更易于成為簇頭。在實際應用的傳感器網絡系統中,存在多種異構節(jié)點。以節(jié)點異構為前提,設計兼有平面結構和分簇結構優(yōu)點的新型數據傳輸模式,也是一個很有應用前景的研究方向。

(3)QoS性能

大量對WSN分簇算法的研究均以能量有效性及負載平衡作為算法性能的度量標準,但未來的研究應進一步考慮分簇算法對網絡QoS性能的影響,尤其是在數據流量動態(tài)變化的情況下。在涉及到圖像以及視頻傳輸的多媒體WSN中,設計能量感知的QoS分簇算法更加值得關注。

此外,無線傳感器網絡作為一種與應用高度相關的網絡,引入跨層設計機制,與MAC、網絡層甚至應用層實現聯合優(yōu)化,進一步提高網絡的容錯性,降低沖突與干擾,與休眠/喚醒機制相結合,與網絡覆蓋、數據融合等問題聯合考慮等,都是分簇算法需要進一步研究的課題。

6 參考文獻

[1] AKYILDIZ I F, SU W, SANKARASUBRAMANIAM Y, et al. Wireless sensor networks: A survey[J]. Computer Networks Journal, 2002,38:393-422.

[2] HEINZELMAN W B, CHANDRAKASAN A P, BALAKRISHNAN H. An application-specific protocol architecture for wireless microsensor networks[J]. 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 networks[C]//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 networks[J]. Journal 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 networks[J]. IEEE Transactions on Mobile Computing, 2004,3(4): 366-379.

[6] ZHU Xiaorong, SHEN Lianfeng, YUM T S P. Hausdorff clustering and minimum energy routing for wireless sensor networks[J]. 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 routing[C]//Proceedings of 7th Annual 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 networks[C]//Proceedings of 4th ACM International Symposium on Mobile Ad Hoc Networking and Computingin(MobiHoc03,Jun 1-3,2003, Annapolis,MD,USA.New York, NY, USA:ACM, 2003:81-95.