陳君梅

（廣州大學華軟軟件學院軟件工程系，廣州 510900）

0 引言

最近幾年，研究者已經(jīng)為WSN提出了很多聚類方法，其中，節(jié)約能耗是這類協(xié)議的主要目標。聚類協(xié)議的操作通常分為三個階段：聚類頭選舉、聚類形成以及數(shù)據(jù)傳輸。每一個協(xié)議的主要部分都是聚類頭選舉算法，因為它能定義一個網(wǎng)絡(luò)的能效。除了能效，聚類協(xié)議還有其他的聚類目標，例如覆蓋率和容錯性等。

本文旨在綜述WSN中近十年的聚類協(xié)議。首先，本文討論了WSN中的聚類目標和聚類特征分類，然后詳細概述了各個聚類協(xié)議的聚類頭選舉與維護過程，最后統(tǒng)計并分析了這些聚類選舉的聚類特征和選舉聚類頭節(jié)點的考慮因素。

1 WSN中聚類協(xié)議的聚類目標和特征

在聚類協(xié)議中，節(jié)點被組成了若干個聚類，每個聚類都有一個聚類頭節(jié)點，該類節(jié)點用于更高層次的通信，從而可降低通信消費，分層的WSN如圖1表示。

不同的聚類協(xié)議，聚類頭選舉算法存在不同。故在該部分我們首先討論了聚類目標，然后討論了聚類特征，為后面統(tǒng)計與分析各類聚類協(xié)議做準備。

圖1 分層的WSN[1]

（ 1）聚類目標

在現(xiàn)有的文獻中，聚類算法的目的各有不同。在WSN中，聚類也有著不同的目的。其中，節(jié)能是這些目的中最重要也是最常見的。我們將這些聚類目標大致分為首要和次要的。首要目標意味著在聚類過程中最重要且最本質(zhì)，而次要目標意味著對于網(wǎng)絡(luò)來說不是最本質(zhì)，但是它們能夠通過聚類而達到。文獻[2]中給出了聚類目標，如圖2所示。

圖2 聚類目標概述[2]

（ 2）聚類特征

為了討論各類聚類方法，該部分將給出一些聚類特征。通常，WSN聚類協(xié)議有三種主要的特征：聚類及其聚類頭的特性，以及聚類過程的特性。其中，聚類特性通常有：聚類的數(shù)目、大小、聚類內(nèi)部通信，以及聚類間通信；聚類頭特性包括節(jié)點的移動性、類型以及充當?shù)慕巧?；聚類過程中，通?？紤]的是聚類的方法、目標，以及聚類頭的選擇等特性。圖3給出了聚類特征的一個分類。

圖3 WSN中聚類協(xié)議的聚類特征[2]

2 聚類頭選舉與維護算法

該部分，本文將詳細闡述WSN近十年來的聚類頭選舉與維護算法。本文即將討論的聚類頭選舉與維護協(xié)議如圖4所示。

圖4 聚類協(xié)議分類圖

（ 1）LEACH

LEACH（Low-Energy Adaptive Clustering Hierar?chy，低能耗自適應(yīng)聚類分層）是WSN中最有名的分層聚類協(xié)議，在該協(xié)議中，一群節(jié)點形成一個聚類，并由一個節(jié)點充當這群節(jié)點的聚類頭節(jié)點。這些節(jié)點基于接收信號強度選舉聚類頭，使得該節(jié)點充當傳遞信息至基站的路由者。這種方式可能減少能耗，因為只有聚類頭節(jié)點而不是所有的節(jié)點在傳輸數(shù)據(jù)。最佳的聚類頭節(jié)點個數(shù)為總節(jié)點個數(shù)的1/5。所有數(shù)據(jù)處理，例如數(shù)據(jù)融合和聚集的工作都由聚類頭節(jié)點擔任。為了均衡節(jié)點的能耗，LEACH在運行過程中不斷地循環(huán)執(zhí)行聚類頭的重構(gòu)。算法操作使用了“輪”的概念，每一輪由初始化和穩(wěn)定工作兩個階段組成。在初始化階段，每個節(jié)點產(chǎn)生一個0～1之間的隨機數(shù)，如果某個節(jié)點產(chǎn)生的隨機數(shù)小于所設(shè)的閾值T()n，則該節(jié)點發(fā)布自己是聚類頭的消息[3]。

（ 2）CCR

CCR（Cluster-based Coordination and Routing frame?work，基于聚類的協(xié)作與路由框架）通過傳感器-傳感器協(xié)作（AAP）使用自適應(yīng)聚類協(xié)議配置傳感器節(jié)點。在AAP中，聚類過程的執(zhí)行包括三個階段：①確定網(wǎng)絡(luò)中最佳的聚類數(shù)目(k)；②選舉合適的聚類節(jié)點充當聚類頭；③限制配置的頻率。每個節(jié)點基于剩余能量、數(shù)據(jù)速率和節(jié)點的度計算其權(quán)重。讓Di成為節(jié)點i到其鄰居節(jié)點的平均距離，Ni是其鄰居節(jié)點的總數(shù)，Ei是其可用的能量以及pi是通信速率。節(jié)點i計算它的權(quán)重Wi為：

由于節(jié)點的異構(gòu)性，E0和ρ0分別代表最低能量級別和節(jié)點的數(shù)據(jù)速率。系數(shù)c1和c2分別代表能量和數(shù)據(jù)速率參數(shù)的權(quán)重因子。最終選出權(quán)重大于其所有鄰居節(jié)點的節(jié)點作為聚類頭[4]。

（ 3）MRCEP

MRCEP（Multipath Routing for Cluster-based and Event-based Protocol，基于聚類和事件的多路徑路由協(xié)議）的主要設(shè)計特征是能效和多跳傳輸。該協(xié)議的目的在于權(quán)衡中繼節(jié)點的剩余能量（能效）和中繼節(jié)點距離基站的距離（最短）的來尋找最佳的傳輸匯集數(shù)據(jù)至基站的中繼路徑。MRCEP的操作被分割成輪，每一輪都包括兩個階段：形成聚類和選擇聚類頭，以及中繼節(jié)點的選擇。在每一輪之后，該協(xié)議將通知聚類選舉聚類頭以及重新創(chuàng)建一系列中繼節(jié)點的路徑。

當網(wǎng)絡(luò)探測到突發(fā)事件，則該事件附近的節(jié)點將被觸發(fā)去測量指定的感知屬性。這些節(jié)點廣播REQ_CLUSTER消息給它們的鄰居，該消息包含節(jié)點IDi，剩余能量數(shù)Rres(i)以及從事件處感知的描述信息數(shù)據(jù)I(i)。在時間t1期間，每個節(jié)點將從所有的其他節(jié)點處接收REQ_CLUSTER消息并且執(zhí)行聚類頭函數(shù)：

其中，X是被事件激活的節(jié)點集合。在t1時間之后，擁有最大函數(shù)集合的節(jié)點，其選舉自身為聚類頭并存儲所有節(jié)點的節(jié)點ID，然后在節(jié)點能夠傳輸其感知數(shù)據(jù)至基站時創(chuàng)建TDMA調(diào)度去安排每個節(jié)點。這些調(diào)度的功能就是避免數(shù)據(jù)傳輸時的沖突。聚類頭接收到所有其他節(jié)點的數(shù)據(jù)，收集并聚集他們，然后選擇中繼節(jié)點，創(chuàng)建至基站的路徑[5]。

（ 4）DSBCA

DSBCA(A Balanced Clustering Algorithm with Dis?tributed Self-Organization，分布式自組織網(wǎng)絡(luò)的均衡聚類算法)中指出，DSBCA有3個階段：聚類頭選舉、建立和循環(huán)。第一階段中，DSBCA首次隨機選擇一個節(jié)點Ut去觸發(fā)聚類過程，然后觸發(fā)節(jié)點Ut去計算它的連通度和距離基站的距離，以此去決定聚類半徑k，從而成為臨時的聚類頭。DSBCA遵循分布式方法，以自組織模式而沒有中心控制的方式去建立分層結(jié)構(gòu)。在這個階段，聚類頭由Ut的k跳鄰居中權(quán)重最大的擔當。其權(quán)重公式中考慮的因素有：剩余能量、連通度和節(jié)點被選為聚類頭節(jié)點的次數(shù)。這使得本文生成的聚類將均衡能耗和位置[6]。

（ 5）UCAPN

如果節(jié)點si沒有在ti時間內(nèi)接收到Head_Msg，該節(jié)點則在其通信范圍Rc內(nèi)廣播其為聚類頭的消息，否則則將進入聚類頭選舉的競爭階段。為了產(chǎn)生一個不均衡的聚類，每個節(jié)點計算自身的競爭半徑Rc。

其中，dmax和dmin分別是距離基站的最大和最小距離，c是一個權(quán)重因子，R0c是一個最大競爭半徑。每個節(jié)點發(fā)送Join_Msg信息至最近的聚類頭，該信息包括id和剩余能量。每個聚類頭根據(jù)接收的Join_Msg創(chuàng)建一個節(jié)點調(diào)度清單，并通過廣播Sync_Msg發(fā)送調(diào)度清單給聚類成員[7]。

（ 6）SCSGR

SCSGR(A Secure Clustering Scheme for Geographi?cally Routed Wireless AD Hoc Networks，安全聚類方案)使用CCA重聚類算法，它是一個保護加權(quán)算法，網(wǎng)絡(luò)中的節(jié)點i均基于聚類變量Ci值決策局部的聚類頭，它可以是多個聚類參數(shù)的加權(quán)和。聚類變量的Ci等式為：Ci=a×di+b×Eri。其中，di為節(jié)點i的連通度，Eri為節(jié)點i的剩余能量，系數(shù)a和b滿足：a+b=1。節(jié)點周期性廣播信標，以此決策出最滿足聚類指標的鄰居節(jié)點[8]。

（7）EEMA

EEMA（Proposed Energy-Efficient Multi-Layered Architecture，能效的多層結(jié)構(gòu)）中指出，在許多聚類協(xié)議中，每個協(xié)議最重要的部分是聚類頭選舉算法。本文的思路是選舉高剩余能量、與基站距離小的節(jié)點擔任聚類頭節(jié)點。為達此目的，本文介紹了新的概率法，如下所示：

其中，Eres和Emax分別表示節(jié)點i的剩余能量和初始能量，k是節(jié)點i在聚類范圍Rc內(nèi)的鄰居節(jié)點數(shù)，d(i,j)表示節(jié)點i和 j之間的歐氏距離，dmax和d(i ,BS)分別表示網(wǎng)絡(luò)中最遠節(jié)點和節(jié)點i到基站的距離。該概率使得那些具有更高剩余能量的節(jié)點能更接近節(jié)點較密集區(qū)，也使得這些節(jié)點到基站的聚類更近，這使得其概率比其他節(jié)點更高，因此，更有機會被選舉為新的聚類頭[9]。

（8）CCCFGA

CCCFGA（A Cluster-Based Coordination and Com?munication Framework Using GA，使用遺傳算法的基于聚類的協(xié)作和通信框架）中指出，GA選擇可以成為聚類頭的最佳候選節(jié)點。GA的輸入是能量參數(shù)，即：①節(jié)點的初始化能量；②節(jié)點的剩余能量；③網(wǎng)絡(luò)的平均能量。無線電模塊在能耗以及網(wǎng)絡(luò)生命周期中占有重要角色。節(jié)點通過GA算法計算概率選舉聚類頭。GA重復(fù)循環(huán)產(chǎn)生最佳結(jié)果。每一次循環(huán)均包括以下步驟：①選舉；②再產(chǎn)生；③評估；④替代。適應(yīng)度函數(shù)檢查每一次新一代產(chǎn)生的結(jié)果去得到最佳值[10]。

（9）CMRP

CMRP（Cluster based Multipath Routing Protocol，基于聚類的多路徑路由協(xié)議），在該協(xié)議中，基站選取聚類頭節(jié)點的條件為：①任何兩個聚類頭不應(yīng)該在彼此的鄰居節(jié)點中；②每個聚類頭的剩余能量Er應(yīng)該大于其閾值；③每個聚類頭至少有k個鄰居節(jié)點。即，基站依賴于兩個獨立的因素選舉聚類頭：一個是剩余能量Er，另外一個是節(jié)點的度D（鄰居節(jié)點數(shù)目）。讓Pr表示任何節(jié)點x成為聚類頭節(jié)點的概率，其公式表達為：

在重新聚類階段，基站發(fā)起重新聚類的過程，為了平衡傳感器節(jié)點間的負載，基站監(jiān)測網(wǎng)絡(luò)中每個傳感器節(jié)點的剩余能量，如果發(fā)現(xiàn)剩余能量低于閾值的聚類頭節(jié)點，基站將選擇另外的聚類頭以及相應(yīng)的路徑，這確保了剩余能量低于閾值的節(jié)點不充當聚類頭，而是充當聚類成員，該行為增加了網(wǎng)絡(luò)的生命周期[11]。

（10）DBHCP

DBHCP（A Distance-Based Hierarchical Clustering Protocol，基于距離的分層聚類協(xié)議）的首要目標是增加網(wǎng)絡(luò)生命周期，該算法由基站收集所有節(jié)點信息，將此形成節(jié)點信息表，然后執(zhí)行聚類頭選舉：基站首先設(shè)置信息表中的第一個節(jié)點為聚類頭，然后該聚類頭發(fā)布選舉消息，而最近節(jié)點通過發(fā)送一個ACK報文給聚類頭作為響應(yīng)，聚類頭發(fā)送一個TDMA給成員節(jié)點，聚類頭發(fā)送新形成的聚類成員給基站。接著，基站考慮表中下一個節(jié)點作為聚類頭的選舉：如果該節(jié)點已經(jīng)是一個聚類頭，或者是先前形成的聚類的一員，它將發(fā)送一個NAK報文給基站，基站然后移動到表中的下一個節(jié)點；如果考慮的節(jié)點不是聚類頭，或者不是聚類的一員，它將被選舉為聚類頭。相應(yīng)地，它發(fā)送一個ACK報文給基站。重復(fù)上述過程直到所有節(jié)點均在聚類內(nèi)。

而在聚類頭輪換過程中，將由最初形成的聚類維護所有循環(huán)，在每一次循環(huán)的開始，聚類頭基于剩余能量在一個聚類內(nèi)部循環(huán)，擁有最高剩余能量的節(jié)點成為聚類頭，新的聚類頭傳輸一個TDMA給所有成員節(jié)點。當一個聚類中的所有節(jié)點均死亡，那么該聚類將從網(wǎng)絡(luò)中消失[12]。

（11）DCHEP

DCHEP（Dynamic Cluster Head Election Protocol，動態(tài)聚類頭選舉協(xié)議）是動態(tài)聚類頭選舉協(xié)議。為了建立分層的網(wǎng)絡(luò)，匯聚節(jié)點發(fā)送信標去廣播它的身份，鄰居節(jié)點收到該信標，將發(fā)送一個聯(lián)合請求給發(fā)送者，并設(shè)置其發(fā)送者為父類節(jié)點。在網(wǎng)絡(luò)建立階段，連接著的節(jié)點會基于一個利用偽隨機數(shù)值設(shè)計可變剩余能量的方式?jīng)Q策是否成為聚類頭。聚類頭將以同樣的方式廣播自己的身份。

每個節(jié)點通過使用可變的剩余能量、初始能量以及值為0～1的連通性計算優(yōu)先級，使得那些沒有可變路徑到達匯聚節(jié)點的節(jié)點不能成為聚類頭節(jié)點，成為聚類頭節(jié)點的概率計算公式如下：

該計算在節(jié)點第一時間收到信標，或者節(jié)點在連接之后錯過了信標的最大數(shù)時被觸發(fā)。事先定義的聚類節(jié)點數(shù)是很重要的參數(shù)，因為它會影響網(wǎng)絡(luò)覆蓋率和聚類間的沖突。為一個移動分層WSN選擇最佳數(shù)目的聚類頭節(jié)點取決于應(yīng)用需求和節(jié)點的移動速度。聚類節(jié)點數(shù)目的設(shè)置不作為本文的研究點，本文在配置文件中設(shè)置聚類節(jié)點數(shù)為總節(jié)點數(shù)的20%。每個節(jié)點根據(jù)P(CH)生成的偽隨機數(shù)決策自身是否成為聚類頭節(jié)點[13]。

（12）HACSH

HACSH（Hierarchical Agglomerative Clustering Sin?gle Hop，單跳分層分塊聚類）使用分層式分塊聚類形成聚類，該方法的優(yōu)點以及特點在于它能返回最佳的聚類個數(shù)。不像其他的類似K-means方法，需要使用一個隨機數(shù)k來決定聚類個數(shù)。本文的提出的聚類頭選擇算法包括初始化聚類、重新聚類以及選擇聚類頭三個階段。初始化階段使用HAC算法生成聚類數(shù)k，k的值小于節(jié)點數(shù)n，在第一次循環(huán)時，我們通過最小距離選取出每個聚類中距離基站最近的節(jié)點。節(jié)點i與基站的距離計算公式如下：

然后將節(jié)點劃分到根據(jù)HAC算法生成的聚類數(shù)目的聚類中，并且把距離基站最近的節(jié)點分別安排在各個聚類中。重新聚類時，每個節(jié)點均關(guān)聯(lián)k個聚類中的某一個，本文通過以下公式計算聚類的opti點。

（13）EDLeach

本文提出了EDLeach協(xié)議，它在LEACH協(xié)議選舉聚類頭的概率公式中綜合考慮了節(jié)點的能量和地理位置，在聚類頭選舉時通過概率選取出最合理的節(jié)點成為聚類頭。DELeach協(xié)議的聚類頭選舉閾值公式如下：

（14）OCHE

OCHE（an agent based Optimal Cluster Head Elec?tion technique，基于代理的最佳聚類頭選取技術(shù)）是基于代理的最佳聚類頭選取技術(shù)。該技術(shù)包含了最佳聚類頭選舉算法，該算法使用剩余能量級別(REL)和剩余停留時間(RTS)兩個參數(shù)選擇聚類頭。其中，REL指節(jié)點在任何時間的剩余能量級別，RTS指該節(jié)點的下一個移動時間或者計算它在該聚類中的剩余停留時間。本文提出的OCHE算法選出的聚類頭節(jié)點是聚類中剩余能量最多，以及剩余停留時間最長的節(jié)點。即：

由此可見，聚類頭選舉頻率也是影響移動WSN功率的因素之一，因為頻繁的重新選舉聚類頭將會消耗節(jié)點的能耗。所以本文提出的算法考慮了聚類頭選舉的次數(shù)的最小化[16]。

（15）WDCR

WDCR(Weight Driven Cluster head Rotation for wire?less sensor network，權(quán)重驅(qū)動的聚類頭輪詢)是權(quán)重驅(qū)動聚類頭循環(huán)算法，該算法在聚類頭選舉開始階段，每個節(jié)點計算自身距離基站的距離。為了建立一個不等聚類大小的網(wǎng)絡(luò)，所有的節(jié)點將計算競爭性半徑，然后廣播一個hello報文給所有的鄰居節(jié)點。hello報文包括節(jié)點的唯一標識、剩余能量、節(jié)點成為聚類頭節(jié)點的次數(shù)，以及距離基站的距離。一旦hello報文被重新保存，節(jié)點開始初始化它的參數(shù)。此外，所有的節(jié)點計算機自身的權(quán)重，以及初始化聚類頭變量的默認值為false。在競爭階段，每個節(jié)點基于自身的權(quán)重計算它的等待時長。如果超過時長，節(jié)點 j未曾收到聚類頭報文，它將設(shè)置聚類頭的值為true，并且在其半徑范圍內(nèi)廣播聚類頭報文。此外，為了成為最終的聚類頭，每個被選的聚類頭節(jié)點將基于權(quán)重值再次決策，若其權(quán)重在它的通信范圍內(nèi)最高，它將宣稱自身為最終的聚類頭節(jié)點。另外，如果在其范圍內(nèi)有其他的節(jié)點權(quán)重大于它，則它將放棄聚類頭的競爭，宣布自身為聚類成員，之后將通過廣播加入報文加入最近的聚類[17]。

（16）WCA

WCA（Clustering Approach Using Node Mobility，使用節(jié)點移動性的聚類方法）是考慮了節(jié)點移動性的聚類方法。本文認為節(jié)點的移動性是造成能量消耗的重要原因。因此，選擇低移動性節(jié)點充當聚類頭能限制能耗從而最大化網(wǎng)絡(luò)生命周期。開始階段，本文通過如下公式計算節(jié)點的移動性。

該等式計算了節(jié)點直至當前時間T的移動性。(xt,yt)和(xt-1,yt-1)分別是節(jié)點v在t和t-1時的坐標。節(jié)點移動性級別ML可定義為移動速度超過6 m h。節(jié)點的速度若是等于或者大于ML將被認為是惡意節(jié)點。該類節(jié)點不能參與聚類頭節(jié)點的選取。而移動能力較為弱的節(jié)點將會進入聚類頭選舉環(huán)節(jié)。選舉的過程如下：

①每個節(jié)點廣播一個hello報文用于發(fā)現(xiàn)他的鄰居節(jié)點，節(jié)點的鄰居節(jié)點集為：

②每個節(jié)點計算自身的連通性、剩余能量和自身與其鄰居節(jié)點之間的距離。距離計算如下：

（17）FCHEA

FCHEA（Fuzzy Cluster Head Election Algorithm，模糊聚類頭選舉算法）是模糊聚類頭選舉算法。類似于LEACH協(xié)議，本文提出的算法也采用論的概念，在每一輪中，每個節(jié)點選擇一個[0～1]之間的隨機數(shù)，如果隨機數(shù)小于閾值T，那么該節(jié)點被選為當前的聚類頭節(jié)點。該聚類頭節(jié)點使用模糊方法計算它們的機會值，然后廣播聚類頭消息至所有在其通信范圍內(nèi)的節(jié)點。聚類頭消息包括節(jié)點id，剩余能量以及機會值。被選為聚類頭節(jié)點的節(jié)點其剩余能量最多。如果當前聚類頭收到剩余能量大于自身的聚類頭消息，那么當前聚類頭將降為成員節(jié)點，并選擇最近的聚類頭，加入其形成聚類。然后，在分配的時間槽期間，成員節(jié)點發(fā)送其數(shù)據(jù)至相應(yīng)聚類頭，其余時間處于休眠狀態(tài)從而節(jié)約能量[19]。

（18）IDE-LEACH

IDE-LEACH（Improved Distance Energy based LEACH，基于距離能量的LEACH）是基于距離能量的LEACH方案。該方案使用初始化能量、節(jié)點距離匯聚節(jié)點或基站的距離以及節(jié)點的持續(xù)能量來考慮聚類頭的選擇。閾值計算公式如下：

（19）K-CRA

K-CRA（A research on Clustering Routing Algorithm based on K-means++，基于K-means的聚類路由算法）是K-means的聚類路由算法。本文認為基于隨機選擇聚類頭會造成數(shù)量不均的聚類以及不均衡的能量消耗，故本文提出了一個基于K-means算法去劃分聚類，以及改進了LEACH算法計算聚類頭的公式，具體操作如下：

本文的聚類頭選舉分為兩個階段：網(wǎng)絡(luò)初始化階段和聚類頭更新階段。在網(wǎng)絡(luò)初始化階段，每個聚類的聚類頭由基站選舉出每個聚類中距離聚類中心最近的節(jié)點作為聚類頭節(jié)點。距離計算公式如下：

當聚類頭的能量低于閾值，將會根據(jù)如下公式選出新的聚類頭。

其中，α和β是相關(guān)參數(shù)，Ecur和Eave分別是節(jié)點的剩余能量和平均能量，L(Di,Mz)和L(Di,BS)分別是節(jié)點距離聚類中心和基站的距離。最后將選出每個聚類當中CHsele值最大的節(jié)點作為該聚類的聚類頭[21]。

（20）LEACH-KPP

LEACH-KPP（research on wireless sensor networks clustering algorithm based on K-means++，基于 K-means++的無線傳感網(wǎng)分簇算法）是基于K-means++的無線傳感網(wǎng)分簇算法。該算法綜合考慮了節(jié)點的剩余能量、與基站間的距離，以及與上一輪聚類頭間的距離。從而避免與基站遠以及剩余能量少的節(jié)點擔任聚類頭，并且選出的聚類頭會接近上一輪聚類頭。聚類頭選取函數(shù)T()n改進為：

（21）CHERDC

CHERDC（Cluster Head Election using Residual En?ergy and Density Control，使用剩余能量和密集度控制的聚類頭選舉）算法在聚類頭選舉階段，每個節(jié)點決策自身為聚類頭還是聚類成員。在每一輪中，節(jié)點將會接收RTi報文，RTi報文包含其鄰居節(jié)點的所有信息。在該算法中，Ni.Stat表示節(jié)點i的狀態(tài)。事實上，節(jié)點 j在一開始都會設(shè)置自身為聚類頭節(jié)點，然后加入競爭階段，其狀態(tài)可能變改為聚類成員或依舊為聚類頭節(jié)點，每個節(jié)點與其鄰居節(jié)點比較剩余能量，如果發(fā)現(xiàn)鄰居節(jié)點剩余能量大于自身，則不得不設(shè)置自己的狀態(tài)為聚類成員。如果二者的剩余能量相等，則進一步比較節(jié)點的密集度，密集度更高的節(jié)點將更有可能成為聚類頭節(jié)點。節(jié)點密集度的計算公式如下：

該公式可以保證在每個節(jié)點的傳遞范圍內(nèi)，只會存在一個聚類頭節(jié)點[23]。

（22）ICEEOA

ICEEOA（Energy Optimization Algorithm for Hierar?chical Routing Based on Improved Cluster Election，改進聚類頭選舉的分層傳感網(wǎng)絡(luò)能力優(yōu)化算法）是改進聚類頭選舉的分層傳感網(wǎng)絡(luò)能力優(yōu)化算法。本文提出的聚類頭選舉算法中，在聚類頭競爭時，基于原來計時機制的基礎(chǔ)上，增加了成員個數(shù)參數(shù)，這避免了成員個數(shù)較多的候選聚類頭節(jié)點成為聚類頭節(jié)點的概率，改進的公式為：

3 聚類頭選舉與維護協(xié)議的統(tǒng)計與分析

本部分，我們首先根據(jù)聚類協(xié)議的聚類特征，統(tǒng)計了上述闡述的聚類算法，如表1所示，接著以柱狀圖的形式分析了各個聚類算法的聚類特性、聚類頭特性和聚類過程特性，分別如圖5、圖6、圖7所示；然后統(tǒng)計了各個聚類協(xié)議中聚類頭選舉的考慮因素，如表2所示，并以餅狀圖的形式展現(xiàn)了各類因素在選取聚類頭時所占的權(quán)重，如圖8所示。

由表1，分別統(tǒng)計了聚類協(xié)議的聚類特性、聚類頭特性、聚類過程特性，分別如圖5、圖6、圖7所示。其中：

圖5聚類協(xié)議的聚類特性

圖5 顯示，現(xiàn)有的聚類協(xié)議在考慮聚類特性時，聚類尺寸相同的情況多于尺寸不同的情況，而聚類的數(shù)目，隨機生成的數(shù)目和固定的數(shù)目基本持平，而聚類數(shù)目變化的情況多半是因為在選舉聚類頭節(jié)點時采用了隨機函數(shù)，從而使得聚類數(shù)目不固定；而在數(shù)據(jù)傳遞過程中，現(xiàn)有的聚類協(xié)議中，單跳的使用遠遠大于多跳，這也正是為了節(jié)約能耗的表現(xiàn)。

圖6顯示，現(xiàn)有的聚類協(xié)議在考慮聚類頭特性過程中，聚類頭處于靜止狀態(tài)的情況多于處于移動的情況，因為聚類頭的移動會造成網(wǎng)絡(luò)拓撲的變化從而使得它的管理費用比固定節(jié)點的消費要高，并且，節(jié)點的移動會造成重新聚類的頻率增高，也會增加能耗。而在考慮節(jié)點的類型時，大都數(shù)的WSN，節(jié)點的初始功率都是相等的，只有少部分考慮了節(jié)點的異構(gòu)性。此外，聚類協(xié)議中的聚類頭，基本在充當中繼角色的同時，還會承擔一定的數(shù)據(jù)聚集與融合工作。

圖6 聚類協(xié)議的聚類頭特性

圖7聚類協(xié)議的聚類頭特性

圖7 顯示，現(xiàn)有的聚類協(xié)議在考慮聚類過程特性時，在方法的采取方面，分布式方法遠遠多于集中式管理，這也是由于WSN中節(jié)點數(shù)目較多，分布式管理更加有效；而在考慮聚類目標時，主要目的是增加節(jié)點的能效、減少數(shù)據(jù)的傳輸時延，從而延長網(wǎng)絡(luò)的生命周期。選取聚類頭時，考慮到隨機生成容易選出能效差的節(jié)點充當，從而增大重新聚類的頻率會浪費節(jié)點能耗，故而，越來越多的聚類協(xié)議采取基于屬性的方式生成聚類頭，使得生成的聚類頭最優(yōu)，從而降低能耗。

每個節(jié)點在考慮聚類頭時，考慮的因素各不相同，表2統(tǒng)計了各類聚類協(xié)議采取的聚類頭選取因素。

表1 聚類協(xié)議的聚類特性、聚類頭特性以及聚類過程特性統(tǒng)計表

表2 聚類協(xié)議的聚類頭選舉的考慮因子

根據(jù)表2，統(tǒng)計出各個聚類協(xié)議在選舉聚類頭時考慮的因素比例，如圖8所示。

圖8選舉聚類頭時考慮的因素

圖8 表示，在現(xiàn)有的聚類協(xié)議中，聚類頭的選舉與維護主要考慮的因素是節(jié)點的剩余能量、其次是與基站的距離以及節(jié)點的度。剩余能量多、與基站較近，以及自身的鄰居節(jié)點更多的節(jié)點有更高的幾率被選為聚類頭節(jié)點，這樣的節(jié)點充當聚類頭，能夠保證聚類的穩(wěn)定性，也會降低聚類頭選舉的頻率，從而提高節(jié)點的能效，最終達到延長網(wǎng)絡(luò)生命周期的目的。

4 結(jié)語

聚類協(xié)議在無線傳感器中扮演著一個重要的角色，而聚類頭的選舉與維護又是聚類協(xié)議中最關(guān)鍵的部分，故，本文綜述了WSN中22個各類聚類協(xié)議的聚類頭選舉與維護算法，統(tǒng)計并分析了這22個算法的聚類特征以及選取聚類頭的考慮因素。分析結(jié)果表示：①現(xiàn)有的聚類協(xié)議在考慮聚類特性時，聚類尺寸相同的情況多于尺寸不同的情況，而聚類的數(shù)目，隨機生成的數(shù)目和固定的數(shù)目基本持平，數(shù)據(jù)傳遞多數(shù)采用單跳的方式。②現(xiàn)有的聚類協(xié)議在考慮聚類頭特性過程中，聚類頭處于靜止狀態(tài)的情況多于處于移動的情況，節(jié)點的類型大多數(shù)是同構(gòu)節(jié)點而異構(gòu)節(jié)點，此外，聚類協(xié)議中的聚類頭，基本在充當中繼角色的同時，還會承擔一定的數(shù)據(jù)聚集與融合工作。③現(xiàn)有的聚類協(xié)議在考慮聚類過程特性時，分布式方法遠遠多于集中式管理，考慮聚類目標時，主要目的是增加節(jié)點的能效、減少數(shù)據(jù)的傳輸時延，從而延長網(wǎng)絡(luò)的生命周期，而選取聚類頭時，越來越多的聚類協(xié)議采取基于屬性的方式生成聚類頭，使得生成的聚類頭最優(yōu)，從而降低能耗。而所考慮的屬性性質(zhì)當中，節(jié)點的剩余能量、節(jié)點距離基站的距離以及節(jié)點的度又是主要考慮的因素。