基于二分K-means的無(wú)線傳感器網(wǎng)絡(luò)分簇方法

張本宏, 江賀訓(xùn)

(合肥工業(yè)大學(xué) 計(jì)算機(jī)與信息學(xué)院, 安徽 合肥 230601)

無(wú)線傳感器網(wǎng)絡(luò)(wireless sensor network,WSN)是由部署在監(jiān)測(cè)區(qū)域內(nèi)大量的微型傳感器節(jié)點(diǎn)和基站組成的,通過(guò)無(wú)線通信方式形成的一個(gè)多跳的自組織的網(wǎng)絡(luò)系統(tǒng)[1]。目的是協(xié)作地感知、采集和處理網(wǎng)絡(luò)覆蓋區(qū)域中被感知對(duì)象的信息,并發(fā)送給匯聚節(jié)點(diǎn)[2]。由于WSN的能耗低、抗毀壞性強(qiáng)，可以被廣泛應(yīng)用于環(huán)境監(jiān)測(cè)、國(guó)防軍事、安全監(jiān)測(cè)、家居生活等眾多領(lǐng)域。因?yàn)闊o(wú)線傳感器節(jié)點(diǎn)通常是投放到人跡罕至的地方,而無(wú)線傳感網(wǎng)絡(luò)節(jié)點(diǎn)的計(jì)算能力、帶寬、能量都十分有限[3]，所以WSN的路由協(xié)議設(shè)計(jì)的重要目標(biāo)是降低節(jié)點(diǎn)能量損耗,延長(zhǎng)整個(gè)網(wǎng)絡(luò)的生命周期[4-5]。分簇算法是有效管理網(wǎng)絡(luò)能耗從而延長(zhǎng)網(wǎng)絡(luò)整體壽命的方法之一。分簇算法通過(guò)將整個(gè)網(wǎng)絡(luò)分成幾個(gè)較小的簇進(jìn)行管理,在每個(gè)簇中選舉簇頭對(duì)簇內(nèi)節(jié)點(diǎn)采集的數(shù)據(jù)進(jìn)行接收并融合再傳輸給基站,降低了網(wǎng)絡(luò)整體的通信,較好地提高了網(wǎng)絡(luò)均衡能耗。文獻(xiàn)[6]提出了低功耗自適應(yīng)集簇分層型協(xié)議(low-energy adaptive clustering hierarchy,LEACH)算法,該算法是一種基于層次式路由的分簇方法,采用隨機(jī)選舉簇頭的策略,網(wǎng)絡(luò)中的傳感器節(jié)點(diǎn)都有一定的幾率被選為簇頭節(jié)點(diǎn)。雖然LEACH分簇算法可以在一定程度上降低網(wǎng)絡(luò)的能耗提高網(wǎng)絡(luò)生命周期，但是無(wú)法保證選舉簇頭的數(shù)量是否合適，同時(shí)也不能保證選舉出的簇頭在網(wǎng)絡(luò)中均勻分布。文獻(xiàn)[7]對(duì)LEACH分簇算法的缺陷進(jìn)行改進(jìn)，提出了LEACH-CC算法,傳感器節(jié)點(diǎn)將自己的剩余能量和位置信息發(fā)送給基站,由基站根據(jù)信息對(duì)網(wǎng)絡(luò)進(jìn)行分簇以確定合適的簇頭數(shù)量；文獻(xiàn)[8]提出一種能耗均衡的混合通信算法,由基站通過(guò)分析節(jié)點(diǎn)剩余能量以及簇頭之間的距離選舉簇頭,并且簇內(nèi)節(jié)點(diǎn)分別以一定的概率通過(guò)單跳和多跳混合的方式與簇頭通信;文獻(xiàn)[9]提出一種基于壓縮感知理論的WSN六邊形格狀優(yōu)化分簇路由算法,定量分析數(shù)據(jù)傳輸次數(shù)與分簇多少的關(guān)系。雖然能夠在一定程度上降低網(wǎng)絡(luò)的能耗但是不能保證簇頭的均勻分布以及合理的簇頭數(shù)量。

這些分簇算法雖然能在一定程度上提高能量的有效性,但是不能保證各個(gè)簇的能量消耗均衡。與非簇頭節(jié)點(diǎn)相比,由于簇首節(jié)點(diǎn)既要負(fù)責(zé)接收并融合簇內(nèi)采集的數(shù)據(jù)又要將數(shù)據(jù)傳送給遠(yuǎn)端的基站,導(dǎo)致簇頭節(jié)點(diǎn)能量損耗過(guò)快容易過(guò)早失效,從而導(dǎo)致網(wǎng)絡(luò)整體效率降低。因此在選舉簇頭時(shí)需要考慮好節(jié)點(diǎn)的剩余能量以及簇頭的能量均衡負(fù)載。文獻(xiàn)[10]提出負(fù)載均衡感知的無(wú)線傳感器網(wǎng)絡(luò)容錯(cuò)分簇算法,利用遺傳因子算法設(shè)計(jì)了一種自適應(yīng)的基于離散粒子群算法來(lái)優(yōu)化簇頭的選舉;文獻(xiàn)[11]提出DBCL算法,通過(guò)控制每個(gè)簇中的成員數(shù)量達(dá)到各個(gè)簇之間能量負(fù)載均衡的效果,但是算法仍然采用的是隨機(jī)選舉簇頭的方式,沒(méi)有考慮節(jié)點(diǎn)的剩余能量;文獻(xiàn)[12]提出EACHS分簇算法先通過(guò)LEACH分簇算法分簇,然后調(diào)整簇頭節(jié)點(diǎn)的位置,并且控制每個(gè)簇內(nèi)成員節(jié)點(diǎn)的數(shù)量從而達(dá)到能量負(fù)載均衡的目的。以上幾種算法都不能保證選出合適的簇頭節(jié)點(diǎn)，并且不能保證簇頭節(jié)點(diǎn)均勻分布在無(wú)線傳感網(wǎng)絡(luò)中,從而導(dǎo)致網(wǎng)絡(luò)能量消耗更大,影響網(wǎng)絡(luò)的整體壽命。

簇頭節(jié)點(diǎn)的數(shù)量對(duì)網(wǎng)絡(luò)能耗很大,簇頭數(shù)量過(guò)多，簇內(nèi)節(jié)點(diǎn)數(shù)量就會(huì)過(guò)少,過(guò)量的簇頭消耗的能量反而更多;簇頭數(shù)量太少失去了分簇算法的意義。因此,選出均勻分布于無(wú)線傳感網(wǎng)絡(luò)中并具有高效能量的最優(yōu)簇頭集合是一個(gè)重要問(wèn)題。二分K-means[13]是基于傳統(tǒng)K-means聚類算法提出的改進(jìn)型算法,它解決了K-means算法對(duì)于初始種子選取過(guò)于依賴導(dǎo)致的分簇不均問(wèn)題,并且運(yùn)行簡(jiǎn)單快捷。本文基于二分K-means算法提出了一種優(yōu)化簇頭選舉的均勻分簇(uniform clustering optimization algorithm,UCOA)算法，其他分簇算法是先以一定概率選舉簇頭，再通過(guò)簇頭廣播信息成員節(jié)點(diǎn)加入的成簇方式,UCOA分簇算法首先基于對(duì)網(wǎng)絡(luò)能耗的理論分析確定WSN的最佳簇頭數(shù)目,然后利用二分K-means進(jìn)行網(wǎng)絡(luò)均勻分簇。在各個(gè)分好的簇中利用改進(jìn)過(guò)后的簇頭選舉算法選出每個(gè)簇中唯一的簇頭。這樣既能保證成簇的均勻也能保證擁有合適的簇頭數(shù)目。

1 系統(tǒng)模型

1.1 拓?fù)淠Ｐ?/h3>

假設(shè)現(xiàn)有一個(gè)用于數(shù)據(jù)采集的無(wú)線傳感網(wǎng)絡(luò),形狀近似為一個(gè)邊長(zhǎng)為M的正方形區(qū)域，其中均勻且隨機(jī)地分布著N個(gè)傳感器節(jié)點(diǎn)。傳感器節(jié)點(diǎn)的位置固定且具有唯一的網(wǎng)絡(luò)標(biāo)識(shí),初始能量相同且有限并能隨時(shí)感知自己的剩余能量,傳感器節(jié)點(diǎn)的感知半徑相同,能根據(jù)自己到簇頭之間的距離自適應(yīng)地調(diào)整發(fā)射頻率?；疚恢霉潭ú⑶译x傳感網(wǎng)絡(luò)很遠(yuǎn)。利用聚類算法將整個(gè)無(wú)線傳感網(wǎng)絡(luò)均勻分成幾個(gè)簇,在各個(gè)簇內(nèi)以節(jié)點(diǎn)的剩余能量和距離基站的遠(yuǎn)近作為考量選舉簇頭。簇內(nèi)節(jié)點(diǎn)與相應(yīng)的簇頭采取單跳通信而簇頭與基站之間采取多跳單跳混合通信的設(shè)計(jì)思想。簇頭節(jié)點(diǎn)采用TDMA的方式為簇內(nèi)的節(jié)點(diǎn)分配數(shù)據(jù)傳輸所需要的時(shí)間點(diǎn),不同的簇采用不同的CDMA代碼的方式與簇頭節(jié)點(diǎn)直接通信,以求避免來(lái)自其他簇中節(jié)點(diǎn)的干擾。

1.2 能量模型

假設(shè)每輪進(jìn)行數(shù)據(jù)采集時(shí)簇內(nèi)的節(jié)點(diǎn)只會(huì)發(fā)送一個(gè)自己所采集到的數(shù)據(jù)包給所在簇的簇頭節(jié)點(diǎn),并且與任何其他簇中的節(jié)點(diǎn)都不會(huì)進(jìn)行通信。每個(gè)簇中的傳感器節(jié)點(diǎn)受到自己所在簇內(nèi)的簇頭管理,將自己所收集到的信息發(fā)送給簇頭,簇頭對(duì)簇內(nèi)節(jié)點(diǎn)傳輸過(guò)來(lái)的數(shù)據(jù)包進(jìn)行必要的融合。在每一輪數(shù)據(jù)采集的期間每個(gè)簇頭只會(huì)發(fā)送一個(gè)數(shù)據(jù)包給基站。為了方便計(jì)算,參考文獻(xiàn)[14]中的能量損耗模型,如圖1所示。

圖1 能量損耗模型

圖1中,Eelec為無(wú)線發(fā)射線路節(jié)點(diǎn)發(fā)送或接收一個(gè)數(shù)據(jù)包所需要的能量消耗;k1為無(wú)線發(fā)射功率放大器在自由空間時(shí)的消耗參數(shù);k2為無(wú)線發(fā)射功率放大器在多路徑傳輸時(shí)的消耗參數(shù)。假設(shè)所有的簇頭在進(jìn)行路由處理和MAC時(shí)不考慮數(shù)據(jù)包的碰撞和空閑監(jiān)聽(tīng)的能量損耗。從一個(gè)傳感器節(jié)點(diǎn)發(fā)送a個(gè)數(shù)據(jù)包到另一個(gè)傳感器節(jié)點(diǎn),傳輸距離為d的能量損耗包括發(fā)送a個(gè)數(shù)據(jù)的能耗以及傳輸過(guò)程中放大器的能耗,即

ETX(a,d)=ETX-elec(a)+ETX-amp(a,d)=

(1)

節(jié)點(diǎn)接收a個(gè)數(shù)據(jù)包的能耗為:

ERX=ERX-elec(a)=aEelec

(2)

2 分簇策略

WSN的分簇算法中,需要合理的簇?cái)?shù)量以及兼顧選舉簇頭時(shí)考慮到簇間能耗負(fù)載均衡,因?yàn)榇仡^需要處理簇間的大部分事務(wù),能耗是所有節(jié)點(diǎn)中最大的，所以選舉簇頭時(shí)需要考慮的一個(gè)重要因素就是節(jié)點(diǎn)剩余能量。同時(shí)簇頭需要直接與基站通信,遠(yuǎn)距離的通信勢(shì)必導(dǎo)致能耗的增加,因此在選舉簇頭時(shí)應(yīng)該考慮到節(jié)點(diǎn)與基站距離的遠(yuǎn)近。本文將簇頭數(shù)目、節(jié)點(diǎn)剩余能量、節(jié)點(diǎn)距離因子加入到簇頭的優(yōu)化選舉中,并設(shè)計(jì)出一種用于簇頭選舉的基于二分K-means的簇頭選舉算法。

2.1 最優(yōu)簇頭數(shù)的計(jì)算

根據(jù)本文的拓?fù)淠Ｐ?設(shè)無(wú)線傳感網(wǎng)絡(luò)中有Y個(gè)簇,則有Y個(gè)簇頭,每個(gè)簇中的非簇頭節(jié)點(diǎn)平均為N/Y-1個(gè)。每個(gè)簇頭消耗的能量組成為接收簇內(nèi)成員數(shù)據(jù)所產(chǎn)生的能耗,融合數(shù)據(jù)產(chǎn)生的能耗,將融合數(shù)據(jù)發(fā)送到基站所產(chǎn)生的能耗以及功率放大器在多路徑傳輸中產(chǎn)生的能耗為:

(3)

簇內(nèi)每個(gè)非簇頭節(jié)點(diǎn)的能耗為:

(4)

每個(gè)簇的能耗為:

(5)

所有簇的總能耗為:

(6)

由于(6)式中的(1-A/a)KEelec與其他項(xiàng)比較數(shù)值太小,忽略不計(jì)所有簇的總能耗,(6)式可以簡(jiǎn)化為:

(7)

(8)

2.2 均勻分簇

無(wú)線傳感網(wǎng)絡(luò)的分簇方法一般都是先進(jìn)行簇頭的選舉,然后通過(guò)簇頭廣播信息成簇。這樣導(dǎo)致的問(wèn)題就是不能保證簇頭的均勻分布,加大無(wú)線傳感器網(wǎng)絡(luò)的能量損耗。UCOA分簇算法采用二分K-means對(duì)無(wú)線傳感網(wǎng)絡(luò)先進(jìn)行均勻分簇,再在分好的簇內(nèi)進(jìn)行簇頭選舉。通常為了快速均勻分簇會(huì)采用K-means算法,K-means算法最關(guān)鍵的步驟是進(jìn)行初始質(zhì)心的選擇,K-means初始時(shí)隨機(jī)指定若干個(gè)節(jié)點(diǎn)為質(zhì)心,可能導(dǎo)致質(zhì)心在網(wǎng)絡(luò)中分布不均從而導(dǎo)致聚類效果不佳。為了改善K-means聚類算法對(duì)于初始質(zhì)心的選擇過(guò)于依賴,采用二分K-means算法進(jìn)行分簇以保證分簇的均勻。在具體的無(wú)線傳感器網(wǎng)絡(luò)可以計(jì)算出最優(yōu)簇頭數(shù)目,通過(guò)設(shè)定k值為最優(yōu)簇頭數(shù)目保證簇頭個(gè)數(shù)的合理。在無(wú)線傳感網(wǎng)絡(luò)節(jié)點(diǎn)布置好之后,以基站為原點(diǎn)建立二維坐標(biāo)系,節(jié)點(diǎn)將自己的位置信息發(fā)送給基站從而得到所有節(jié)點(diǎn)的坐標(biāo)。分簇步驟如下:

(1) 將無(wú)線傳感網(wǎng)絡(luò)中的所有節(jié)點(diǎn)初始化為一個(gè)簇,利用K-means聚類算法將其分成2個(gè)簇。

(2) 分別計(jì)算簇的誤差平方和(sum of squares for error,SSE),計(jì)算公式為：

(9)

其中,ci為質(zhì)心坐標(biāo);x為質(zhì)心ci的簇內(nèi)節(jié)點(diǎn);dist為空間2個(gè)向量的歐幾里得距離。

SSE能夠很好地衡量聚類性能,SSE值越小,說(shuō)明節(jié)點(diǎn)越接近于它們的質(zhì)心,聚類效果越好;反之,SSE值越大,說(shuō)明該簇聚類的效果越不好,有更大的可能性是將幾個(gè)簇當(dāng)成了一個(gè)簇。因此需要首先對(duì)該簇進(jìn)行劃分。

(3) 利用K-means算法將SSE更大的那個(gè)簇分成2個(gè)簇。

(4) 重復(fù)步驟(2)、步驟(3)直到將網(wǎng)絡(luò)分成k個(gè)簇為止。

2.3 簇頭選舉

考慮到簇頭所承擔(dān)的簇內(nèi)簇間事務(wù)很多,能量消耗巨大。將剩余能量和節(jié)點(diǎn)距離基站距離遠(yuǎn)近加入到簇頭選舉的考慮中。UCOA分簇算法只進(jìn)行一次分簇,而簇頭的選舉每輪都會(huì)進(jìn)行。將節(jié)點(diǎn)剩余能量和節(jié)點(diǎn)距離基站距離遠(yuǎn)近加入對(duì)簇頭選舉閾值公式中,選舉簇頭的時(shí)候每個(gè)節(jié)點(diǎn)會(huì)隨機(jī)產(chǎn)生一個(gè)0～1之間的數(shù),然后與閾值T(n)比較,若這個(gè)數(shù)比閾值小則當(dāng)選為簇頭。閾值公式為:

(10)

(11)

(12)

其中,P為每一個(gè)區(qū)域里面簇頭個(gè)數(shù)的百分比,在UCOA分簇算法中要求每個(gè)簇內(nèi)只能有一個(gè)簇頭節(jié)點(diǎn),因此具體到分好的每個(gè)簇內(nèi)P值就是簇內(nèi)節(jié)點(diǎn)個(gè)數(shù)的倒數(shù);rmod(1/p)為以1/p輪為周期的循環(huán)在當(dāng)前還剩余的輪數(shù);G為剩余輪數(shù)中還沒(méi)有成為過(guò)簇頭節(jié)點(diǎn)的集合;ω(n)為加入了剩余能量因子和距離遠(yuǎn)近因子的閾值修正函數(shù);Eini(n)為節(jié)點(diǎn)的初始能量;Eres(n)為節(jié)點(diǎn)當(dāng)前的剩余能量;Dmax(n)為每個(gè)簇內(nèi)節(jié)點(diǎn)中距離基站最遠(yuǎn)的距離;Dmin(n)為簇內(nèi)節(jié)點(diǎn)中距離基站最近的距離。網(wǎng)絡(luò)運(yùn)行之初所有節(jié)點(diǎn)的初始能量都相同,此時(shí)主要由節(jié)點(diǎn)距離基站距離遠(yuǎn)近控制簇頭的選舉,距離基站近的節(jié)點(diǎn)當(dāng)選簇頭耗能相對(duì)更少。隨著網(wǎng)絡(luò)運(yùn)行輪數(shù)的增加,節(jié)點(diǎn)耗能不均衡性開(kāi)始體現(xiàn),因此此時(shí)應(yīng)該將剩余能量在閾值修正函數(shù)中的權(quán)重增加以求更好的網(wǎng)絡(luò)耗能均衡。若某個(gè)簇中選出的簇頭不止一個(gè),則優(yōu)先選擇剩余能量大的節(jié)點(diǎn)當(dāng)選簇頭。

3 數(shù)據(jù)傳輸階段

無(wú)線傳感網(wǎng)絡(luò)中簇頭節(jié)點(diǎn)與基站,簇內(nèi)成員節(jié)點(diǎn)與簇頭節(jié)點(diǎn)都是通過(guò)單跳方式進(jìn)行數(shù)據(jù)傳輸?shù)?長(zhǎng)距離的數(shù)據(jù)傳輸會(huì)造成能量的過(guò)早耗盡,UCOA分簇算法中簇頭采用單跳與多跳相結(jié)合的數(shù)據(jù)傳輸方式進(jìn)行網(wǎng)絡(luò)通信。文獻(xiàn)[15]分析了單跳路由和多跳路由的能量消耗關(guān)系,它將無(wú)線傳感網(wǎng)絡(luò)簡(jiǎn)化為一個(gè)簡(jiǎn)單的線性網(wǎng)絡(luò),在線性網(wǎng)絡(luò)中各節(jié)點(diǎn)的距離相等,兩點(diǎn)之間的距離為s。當(dāng)一個(gè)節(jié)點(diǎn)與匯聚節(jié)點(diǎn)距離為ns,這個(gè)節(jié)點(diǎn)發(fā)送kbit數(shù)據(jù)到匯聚節(jié)點(diǎn)時(shí),根據(jù)(1)式可以算出直接通信Edirect的值，即

Edirect=ETX(a,d=ns)=

aEelec+k1a(ns)2=

a(Eelec+k1n2s2)

(13)

而在多跳路由中,若每個(gè)節(jié)點(diǎn)把數(shù)據(jù)先傳送給離自己最近的節(jié)點(diǎn)最后到達(dá)匯聚節(jié)點(diǎn),則離匯聚節(jié)點(diǎn)距離為ns的節(jié)點(diǎn)傳送abit數(shù)據(jù)到匯聚節(jié)點(diǎn)的過(guò)程中需要有n次的數(shù)據(jù)發(fā)送和n-1次的數(shù)據(jù)接收,根據(jù)(1)式、(2)式可以得到多跳通信的能量消耗EMTE為:

EMTE=nETX(a,d=s)+(n-1)ERX(a)=

n(aEelec+k1as2)+a(n-1)Eelec=

a(2n-1)Eelec+k1ns2

(14)

當(dāng)Edirect

a(Eelec+k1n2s2)

(15)

當(dāng)Edirect=50 nJ/bit,k1=10 pJ/bit時(shí),若設(shè)n=2,則由(15)式得s<71,因此當(dāng)節(jié)點(diǎn)距離匯聚節(jié)點(diǎn)的傳輸距離大于71 m時(shí)采用多跳傳輸,當(dāng)傳輸距離小于71 m時(shí)采用通信直接傳輸。

4 仿真與分析

4.1 仿真環(huán)境與性能指標(biāo)

為了驗(yàn)證分簇算法效果,采用仿真工具M(jìn)atlab對(duì)LEACH、UCOA分簇算法進(jìn)行仿真比較。在本實(shí)驗(yàn)中布置無(wú)線傳感網(wǎng)絡(luò)覆蓋區(qū)域?yàn)橹苯亲鴺?biāo)區(qū)域:0≤x≤100,0≤y≤100,區(qū)域內(nèi)隨機(jī)分布100個(gè)傳感器節(jié)點(diǎn),基站的坐標(biāo)為(50,150)。具體的仿真參數(shù)見(jiàn)表 1所列。

表1 仿真參數(shù)

根據(jù)仿真參數(shù)可以計(jì)算出距離閾值d0=87.5 m,根據(jù)上文中的最優(yōu)簇頭公式求得最優(yōu)簇頭數(shù)Y=5。實(shí)驗(yàn)分別從網(wǎng)絡(luò)簇頭分布、網(wǎng)絡(luò)節(jié)點(diǎn)存活情況、網(wǎng)絡(luò)節(jié)點(diǎn)能量消耗幾個(gè)方面對(duì)比LEACH和UCOA分簇算法的性能。路由協(xié)議的性能主要以第1個(gè)死亡節(jié)點(diǎn)出現(xiàn)的時(shí)間為依據(jù),傳感器節(jié)點(diǎn)開(kāi)始死亡的時(shí)間越晚,死亡出現(xiàn)得越集中,表明協(xié)議性能就越好。若節(jié)點(diǎn)的剩余能量為0,則表明節(jié)點(diǎn)死亡;若整個(gè)網(wǎng)絡(luò)的死亡節(jié)點(diǎn)數(shù)占到總節(jié)點(diǎn)數(shù)的80%,則可以視作整個(gè)網(wǎng)絡(luò)死亡。因此本文的仿真評(píng)估以第1個(gè)節(jié)點(diǎn)死亡的輪數(shù)和所有節(jié)點(diǎn)總數(shù)的80%死亡的輪數(shù)作為評(píng)判標(biāo)準(zhǔn)。

4.2 仿真結(jié)果與分析

LEACH與UCOA分簇算法某輪中的簇頭分布如圖2所示,LEACH分簇算法以隨機(jī)指定的方式選取簇頭節(jié)點(diǎn),不能保證簇頭數(shù)量合理還可能導(dǎo)致簇頭節(jié)點(diǎn)分布不均,有的地方簇頭密集有的地方簇頭稀疏,加劇網(wǎng)絡(luò)能量的損耗。UCOA分簇算法通過(guò)設(shè)定最優(yōu)簇頭數(shù)的方式首先對(duì)整個(gè)無(wú)線傳感器網(wǎng)絡(luò)進(jìn)行均勻分簇,再在各個(gè)簇中利用優(yōu)化過(guò)的簇頭選舉算法來(lái)選舉簇頭,既保證了簇頭數(shù)量的合理，也保證了簇頭的均勻分布,從而很好地均衡了簇頭以及簇間的能耗均衡。

(a) LEACH分簇算法

(b) UCOA分簇算法圖2 LEACH、UCOA分簇算法簇頭分布

LEACH分簇算法與UCOA分簇算法運(yùn)行期間網(wǎng)絡(luò)存活節(jié)點(diǎn)的數(shù)目變化情況的仿真結(jié)果如圖3所示。從圖3可以看出,LEACH分簇算法第1個(gè)節(jié)點(diǎn)死亡出現(xiàn)在820 輪左右。而UCOA分簇算法第1個(gè)死亡節(jié)點(diǎn)出現(xiàn)在1 260 輪左右。第1個(gè)死亡節(jié)點(diǎn)的輪數(shù)推遲了53%左右。整個(gè)網(wǎng)絡(luò)運(yùn)行期間UCOA分簇算法出現(xiàn)了幾次大面積節(jié)點(diǎn)死亡的現(xiàn)象,這是由于UCOA分簇算法網(wǎng)絡(luò)能耗均勻節(jié)點(diǎn)死亡時(shí)間段集中,但是也恰恰說(shuō)明節(jié)點(diǎn)的真實(shí)工作效率高。而LEACH分簇算法的節(jié)點(diǎn)死亡相對(duì)比較分散,特別是一些關(guān)鍵性節(jié)點(diǎn)的死亡影響整個(gè)網(wǎng)絡(luò)工作的效率導(dǎo)致剩下節(jié)點(diǎn)的作用有限。LEACH分簇算法隨機(jī)選舉節(jié)點(diǎn)成為簇頭,容易導(dǎo)致簇頭分布不均,數(shù)量不合適。在簇間傳輸時(shí)只使用單跳傳輸節(jié)點(diǎn)耗能不均。UCOA分簇算法先使用二分K-means將整個(gè)網(wǎng)絡(luò)均勻分簇,在選舉簇頭時(shí)加入剩余能量和節(jié)點(diǎn)與基站之間距離遠(yuǎn)近做調(diào)節(jié)使得節(jié)點(diǎn)耗能均衡。當(dāng)網(wǎng)絡(luò)死亡節(jié)點(diǎn)數(shù)超過(guò)80%時(shí)網(wǎng)絡(luò)失效,從80%節(jié)點(diǎn)死亡到全部節(jié)點(diǎn)死亡,UCOA分簇算法只經(jīng)過(guò)了很短的時(shí)間。而LEACH分簇算法經(jīng)過(guò)了很漫長(zhǎng)的一段時(shí)間。這是由于LEACH算法簇頭的選舉與輪數(shù)r和簇頭概率p有關(guān),隨著網(wǎng)絡(luò)剩余的節(jié)點(diǎn)越來(lái)越少,LEACH算法越來(lái)越難選出簇頭,在很多輪中其實(shí)是沒(méi)有選出簇頭的，也就是網(wǎng)絡(luò)沒(méi)有進(jìn)行工作也沒(méi)有能量的損耗。而UCOA分簇算法在每個(gè)簇中產(chǎn)生唯一的簇頭，每輪中都會(huì)選擇一個(gè)簇頭。因此從80%死亡節(jié)點(diǎn)到節(jié)點(diǎn)全部死亡,UCOA分簇算法經(jīng)歷的時(shí)間非常短。這也說(shuō)明了UCOA分簇算法耗能更加均衡。為了更直觀地說(shuō)明UCOA分簇算法的性能,根據(jù)節(jié)點(diǎn)不同階段的死亡時(shí)間繪制節(jié)點(diǎn)死亡時(shí)間表和節(jié)點(diǎn)生存周期柱狀圖,見(jiàn)表2所列,如圖4所示。

圖3 存活節(jié)點(diǎn)趨勢(shì)

表2 節(jié)點(diǎn)死亡時(shí)間對(duì)照 輪

圖4 網(wǎng)絡(luò)生命周期柱狀圖

網(wǎng)絡(luò)剩余能量對(duì)比如圖5所示,由圖5可知,隨著程序的不斷運(yùn)行,在初期2種算法的耗能差不多。但是隨著實(shí)驗(yàn)輪數(shù)的不斷增加,兩者的網(wǎng)絡(luò)總能耗都在增加時(shí),UCOA分簇算法的耗能明顯比LEACH分簇算法更慢,而隨著實(shí)驗(yàn)不斷進(jìn)行，這種優(yōu)勢(shì)體現(xiàn)得更加明顯。相同的實(shí)驗(yàn)輪數(shù)時(shí)，UCOA分簇算法的網(wǎng)絡(luò)總體剩余能量遠(yuǎn)遠(yuǎn)高于LEACH分簇算法。

圖5 網(wǎng)絡(luò)剩余能量對(duì)比

5 結(jié) 論

合理高效地利用無(wú)線傳感網(wǎng)絡(luò)節(jié)點(diǎn)有限的能量,從而延長(zhǎng)整個(gè)網(wǎng)絡(luò)的生命周期是當(dāng)前對(duì)無(wú)線傳感器網(wǎng)絡(luò)研究的熱點(diǎn)問(wèn)題之一。本文在研究了WSN分簇算法的優(yōu)缺點(diǎn)基礎(chǔ)之上,提出了一種基于二分K-means的均勻分簇路由算法。首先基于對(duì)網(wǎng)絡(luò)能量模型分析計(jì)算網(wǎng)絡(luò)最優(yōu)簇頭數(shù)目。利用二分K-means對(duì)無(wú)線傳感網(wǎng)絡(luò)的節(jié)點(diǎn)進(jìn)行均勻分簇。并利用改進(jìn)的簇頭閾值計(jì)算公式在簇中選出唯一的簇頭。簇頭與基站進(jìn)行數(shù)據(jù)傳輸時(shí)運(yùn)用單跳與多跳相結(jié)合的方式。仿真實(shí)驗(yàn)表明,本文提出的算法均衡了網(wǎng)絡(luò)的能耗,延長(zhǎng)了網(wǎng)絡(luò)整體生存時(shí)間。