陶志勇,王和章,劉 影

(遼寧工程技術(shù)大學(xué) 電子與信息工程學(xué)院,遼寧 葫蘆島 125105)

1 引 言

隨著MEMS(Micro Electro Mechanical System)和無線通信技術(shù)的發(fā)展,無線傳感器網(wǎng)絡(luò)(wireless sensor networks,WSN)的應(yīng)用越來越廣泛,如軍事偵察、安全監(jiān)控等[1].WSN是由大量廉價(jià)的具有一定計(jì)算和通信能力的傳感器節(jié)點(diǎn)相互協(xié)作而形成的,傳感器節(jié)點(diǎn)一般采用能量受限的電池,且部署后無法更換[2],這嚴(yán)重限制了WSN的發(fā)展.由于傳感器的能耗與網(wǎng)絡(luò)的路由息息相關(guān),因此如何設(shè)計(jì)能量高效利用的路由協(xié)議成為了WSN研究的重要目標(biāo)[3].

為了延長(zhǎng)網(wǎng)絡(luò)生命周期,許多基于成簇的路由協(xié)議被提出[4].分簇減少了數(shù)據(jù)的傳輸量,降低了能耗.早期的成簇路由協(xié)議大多采用單跳通信的方式,網(wǎng)絡(luò)擴(kuò)展性較差,離基站較遠(yuǎn)的簇首能耗較快.隨著研究的深入,越來越多的成簇網(wǎng)絡(luò)采用多跳通信的方式,這雖然能夠節(jié)省能量,但易導(dǎo)致能量空洞[5].

LEACH[6]是最早提出的一種均勻分簇路由協(xié)議,相比較于平面路由協(xié)議,其能量利用率較高,生命周期較長(zhǎng);但隨機(jī)的簇首選舉導(dǎo)致有些節(jié)點(diǎn)由于能耗過快而過早死亡.因此,李成法等人[7]提出了一種不均勻的成簇路由協(xié)議-EEUC,它通過控制簇首的競(jìng)爭(zhēng)半徑來調(diào)整簇的規(guī)模,使靠近基站的簇規(guī)模較小,這樣距離基站較近的簇首會(huì)由于簇內(nèi)能耗的降低而預(yù)留足夠的能量來轉(zhuǎn)發(fā)其他簇首的數(shù)據(jù);然而簇首的選擇只由概率和門限值決定,無法保證所選簇首最優(yōu).張文梅等人[8]提出利用最小生成樹優(yōu)化數(shù)據(jù)傳輸路徑,均衡了能耗;但網(wǎng)絡(luò)需要遍歷消息,造成了能量的不必要損耗.張雅瓊[9]提出利用K-means算法均勻分簇,避免了極大簇和極小簇的情況;但K-means算法對(duì)初始聚類中心敏感,聚類效果不理想.張品等人[10]提出在熱區(qū)內(nèi)選取傳送節(jié)點(diǎn)來解決負(fù)載不均的問題,通過基于相似數(shù)據(jù)的收集策略休眠部分冗余節(jié)點(diǎn),減少了能耗;但簇間只考慮能量和距離因素,會(huì)導(dǎo)致多跳路徑較大地偏離理想最優(yōu)路徑,增加多跳跳數(shù).Hui等人[11]提出了混合整數(shù)線性規(guī)劃模型,以此來確定簇首的最佳位置.李建洲等人[12]提出了EBCRP (Energy Balanced Clustering Routing Protocol)協(xié)議,在簇間綜合考慮距離和角度因素,有效地平衡了路徑損耗和多跳跳數(shù);然而多跳時(shí)沒有考慮能量因素,導(dǎo)致剩余能量較低的簇頭有可能當(dāng)選為中繼簇頭.

蔣暢江等人[13]提出了DEBUC(Distributed Energy-Balanced Unequal Clustering)協(xié)議,它利用節(jié)點(diǎn)的競(jìng)爭(zhēng)半徑選擇候選簇首,根據(jù)候選簇首以及其鄰居節(jié)點(diǎn)的剩余能量通過基于時(shí)間的競(jìng)爭(zhēng)算法選舉最終簇首,同時(shí)在簇間運(yùn)用貪婪算法選擇中繼節(jié)點(diǎn),均衡了能耗;但由于隨著網(wǎng)絡(luò)規(guī)模的增大,競(jìng)爭(zhēng)半徑逐漸增加,簇內(nèi)通信距離達(dá)到自由空間模型的極限值,導(dǎo)致數(shù)據(jù)傳輸時(shí)能耗增加較快.孫彥清等人[14]提出了UCDP(Uneven Clustering routing protocol based on Dynamic Partition)協(xié)議,它利用能量均衡的非均勻分區(qū)算法將網(wǎng)絡(luò)合理動(dòng)態(tài)分區(qū),選舉簇首與區(qū)頭協(xié)作通信,通過簇內(nèi)單跳、區(qū)內(nèi)以及區(qū)間多跳相結(jié)合的方式建立一個(gè)能耗最優(yōu)的路由協(xié)議;但在路徑建立時(shí),簇內(nèi)以及簇間需要多次通信.

本文綜合以上問題,在改進(jìn)算法的基礎(chǔ)上提出了一種適用于大規(guī)模無線傳感網(wǎng)的成簇路由協(xié)議.該協(xié)議在基站利用K-means++算法估計(jì)類數(shù)K值,同時(shí)通過泊松混合模型將節(jié)點(diǎn)依概率合理分簇;簇間采用多跳路由方式,將能量、距離和角度因素相結(jié)合,對(duì)多跳路徑進(jìn)行優(yōu)化.實(shí)驗(yàn)數(shù)據(jù)表明:該協(xié)議能夠有效延長(zhǎng)網(wǎng)絡(luò)壽命,均衡節(jié)點(diǎn)能耗,并且在大規(guī)模網(wǎng)絡(luò)中具有良好的性能.

2 LEACH協(xié)議

LEACH協(xié)議[6]即低功耗自適應(yīng)集簇分層型協(xié)議,其基本思想是采用“輪”的概念,以循環(huán)的方式不斷地執(zhí)行簇重構(gòu).每輪分為兩個(gè)階段:簇建立和穩(wěn)定的數(shù)據(jù)傳輸.在簇建立階段,每個(gè)節(jié)點(diǎn)產(chǎn)生一個(gè)[0,1]之間的隨機(jī)數(shù),將此隨機(jī)數(shù)與其閾值函數(shù)T(n)比較,若小于,則此節(jié)點(diǎn)成為簇首;當(dāng)選為簇首的節(jié)點(diǎn)向全網(wǎng)廣播當(dāng)選信息(ADV_CH),非簇首節(jié)點(diǎn)根據(jù)接收到的信號(hào)強(qiáng)度選擇值最大的簇首加入.穩(wěn)定的數(shù)據(jù)傳輸階段包括簇內(nèi)通信和簇間通信,兩者均采用單跳的方式.T(n)的計(jì)算式為:

(1)

n為當(dāng)前傳感器節(jié)點(diǎn),p為簇首所占比例,r是當(dāng)前的輪數(shù),G為最近1/p輪未當(dāng)選為簇首的節(jié)點(diǎn)集合.在最近1/p輪中,隨著輪數(shù)的增加,T(n)值越來越大,這意味著未擔(dān)任過簇首的節(jié)點(diǎn)競(jìng)選為簇首的概率越來越大.

3 網(wǎng)絡(luò)模型與能耗模型

3.1 網(wǎng)絡(luò)模型

本文假設(shè)n個(gè)傳感器節(jié)點(diǎn)隨機(jī)分布在M×M的監(jiān)測(cè)區(qū)域內(nèi),且傳感器網(wǎng)絡(luò)具有如下性質(zhì)[13]:

1)基站在監(jiān)測(cè)區(qū)域外,傳感器節(jié)點(diǎn)在監(jiān)測(cè)區(qū)域內(nèi),部署后位置均不變.

2)所有節(jié)點(diǎn)是同構(gòu)的,具有相似的能力(處理/通信),且都有唯一的節(jié)點(diǎn)標(biāo)識(shí)號(hào).

3)鏈路是對(duì)稱的,如果已知發(fā)射端的發(fā)射功率,接收端可以根據(jù)接收到的信號(hào)強(qiáng)度估算兩者的距離.

4)節(jié)點(diǎn)的發(fā)射功率以及通信半徑可以根據(jù)需要自動(dòng)調(diào)整.

5)節(jié)點(diǎn)具有位置感知能力.

6)相對(duì)于節(jié)點(diǎn)感知范圍而言,監(jiān)測(cè)區(qū)域遠(yuǎn)大于單個(gè)節(jié)點(diǎn)的感知區(qū)域.

3.2 能耗模型

本文采用文獻(xiàn)[6]的能耗模型,即一階無線電模型.發(fā)射端向距離為d的接收端發(fā)送l比特的數(shù)據(jù)所消耗的能量為:

(2)

接收端接收l比特的數(shù)據(jù)所消耗的能量為:

ERx(l)=lEelec

(3)

簇首將普通節(jié)點(diǎn)的數(shù)據(jù)進(jìn)行融合同樣需要消耗能量,本文采用與文獻(xiàn)[14]相同的融合模型,即無論簇首接收到多少普通節(jié)點(diǎn)的數(shù)據(jù)均將其融合成l比特.

4 隨機(jī)分布模型

在二維地理空間位置部署的大量傳感器節(jié)點(diǎn)通常是獨(dú)立隨機(jī)分布的,這種分布方式適用于分析沒有先驗(yàn)知識(shí)的地理環(huán)境.傳感器節(jié)點(diǎn)通常采用高空灑落的方式部署在難以監(jiān)測(cè)的環(huán)境中,節(jié)點(diǎn)的位置可以看作服從二維泊松分布[15].

(4)

將節(jié)點(diǎn)密度λ和概率q代入上式可得:

(5)

將公式(5)化簡(jiǎn)可得:

(6)

將公式(6)分為三項(xiàng)求解,當(dāng)n無限大,即n→+∞時(shí),該三項(xiàng)分別為:

1)由重要極限公式可得:

(7)

2)由于第二項(xiàng)中不包含變量n,因此:

(8)

3)將第三項(xiàng)拆開求積得:

(9)

將公式(7)、(8)、(9)代入公式(6):

(10)

由公式(10)可知,某一區(qū)域SD內(nèi)的節(jié)點(diǎn)服從參數(shù)為λSD的泊松分布.

5 大規(guī)模成簇路由協(xié)議-CRPMM

針對(duì)LEACH協(xié)議以及大多基于其改進(jìn)的路由協(xié)議如DEBUC等隨著網(wǎng)絡(luò)規(guī)模的擴(kuò)大其能量利用率較低的問題,本文提出了一種適用于大規(guī)模無線傳感網(wǎng)的基于泊松混合模型的成簇路由協(xié)議.該協(xié)議通過在基站運(yùn)行K-means++算法來估計(jì)K值,然后利用泊松混合模型實(shí)現(xiàn)K值的優(yōu)化和節(jié)點(diǎn)分簇;同時(shí)在簇間綜合考慮節(jié)點(diǎn)的能量因素、距離因素以及角度因素,建立最優(yōu)多跳傳輸路徑.

5.1 K-means++算法估計(jì)K值

經(jīng)典聚類算法如K-means、K-mediods等在聚類前需要首先確定最終的聚類數(shù)K,而K值是否合理直接關(guān)系著聚類的效果.為了增強(qiáng)聚類效果,本文提出在利用泊松混合聚類前先運(yùn)用K-means++算法[16]估計(jì)K值.為了降低能耗,本文采用集中式的方法,節(jié)點(diǎn)將自己感知的位置信息發(fā)送至基站,在基站運(yùn)行K-means++算法.

由于K值與初始種子節(jié)點(diǎn)個(gè)數(shù)相等,因此本文采用K-means++算法估計(jì)K值.其基本思想是:初始的種子節(jié)點(diǎn)之間的相互距離盡可能的遠(yuǎn).K-means++算法估計(jì)K值的具體步驟為:

Step1.在監(jiān)測(cè)區(qū)域內(nèi)隨機(jī)選擇一個(gè)節(jié)點(diǎn)xi作為第一個(gè)初始種子節(jié)點(diǎn).對(duì)于監(jiān)測(cè)區(qū)域內(nèi)的其余節(jié)點(diǎn)xj,分別計(jì)算其與第一個(gè)初始種子節(jié)點(diǎn)的歐式距離dist(i,j).

Step2.選擇一個(gè)新的節(jié)點(diǎn)作為新的初始種子節(jié)點(diǎn),其選取原則為dist(i,j)較大的點(diǎn).對(duì)于監(jiān)測(cè)區(qū)域內(nèi)的非初始種子節(jié)點(diǎn),計(jì)算其與最近的初始種子節(jié)點(diǎn)的距離dist(i,j),根據(jù)可能性Rj選取值最大的節(jié)點(diǎn)作為下一個(gè)初始種子節(jié)點(diǎn),Rj的計(jì)算公式為:

(11)

Step3.重復(fù)Step 2,直到滿足|SilK-SilK-1|≤ξ或K

聚類有效性指標(biāo)反映了聚類結(jié)構(gòu)的類內(nèi)緊密性和類間分散性,主要用于評(píng)價(jià)聚類質(zhì)量和估計(jì)最佳聚類數(shù)[17].設(shè)CI(i)表示節(jié)點(diǎn)xi與類內(nèi)所有其余節(jié)點(diǎn)的平均距離,DI(i)為節(jié)點(diǎn)xi到其他每個(gè)類中節(jié)點(diǎn)平均距離的最小值,則Silhouette指標(biāo)為:

(12)

由式(12)可知,Silhouette指標(biāo)值在[0,1]范圍內(nèi)波動(dòng),Silhouette(i)值越大表明聚類的質(zhì)量越好.因此本文利用所有節(jié)點(diǎn)的Silhouette指標(biāo)的平均值來表示聚類有效性指標(biāo)SilK.

SilK=mean{Silhouette(i)}

(13)

5.2 加速泊松混合聚類

傳統(tǒng)聚類算法如K-means、Birch等判斷節(jié)點(diǎn)的所屬類時(shí)一般只考慮距離因素,并沒有關(guān)注節(jié)點(diǎn)的分布;而在實(shí)際環(huán)境中,節(jié)點(diǎn)是否屬于某一類與節(jié)點(diǎn)的分布有較大的關(guān)系.針對(duì)上述思想,本文提出了一種基于泊松混合模型的加速聚類算法.

由第4章可知,某一監(jiān)測(cè)區(qū)域內(nèi)的節(jié)點(diǎn)服從泊松分布.假設(shè)隨機(jī)節(jié)點(diǎn)xi服從泊松混合分布,則其概率可表示為:

(14)

P(xi|λk,nk)表示第k個(gè)泊松模型的分布律,λk為其均值,nk為該模型分量所包含的節(jié)點(diǎn)數(shù),其表達(dá)式為:

(15)

式(14)中,πk為每個(gè)泊松模型分量的混合系數(shù),代表其所包含的節(jié)點(diǎn)數(shù)占總節(jié)點(diǎn)數(shù)的比例;K為泊松模型分量的個(gè)數(shù).

(16)

式(16)可通過EM算法迭代優(yōu)化求解最大似然參數(shù).EM算法分為兩步:

對(duì)式(16),由Jensen不等式可得:

(17)

(18)

(19)

由EM算法求出最大似然參數(shù)估計(jì)值.其中,混合系數(shù):

(20)

泊松模型分量的均值:

(21)

隱變量:

(22)

(23)

(24)

(25)

為了在泊松混合聚類的迭代初期使參數(shù)θk快速逼近最優(yōu)解,本文采用Steffensen加速方法.當(dāng)接近最優(yōu)解時(shí),由于EM算法步長(zhǎng)變化緩慢,本文使用Broyden對(duì)稱秩1校正公式進(jìn)行校正,使算法快速收斂.因此在整個(gè)迭代周期算法的迭代次數(shù)明顯減少,達(dá)到了加速收斂的目的.

(26)

其中,α為調(diào)節(jié)系數(shù),滿足0≤α≤1,其取值為:

(27)

(28)

(29)

(30)

加速泊松混合聚類的基本步驟為:

Step10.利用隱含參數(shù)信息熵原理,求出三維數(shù)組Ω中不同K值的信息熵H,則H的最小值所對(duì)應(yīng)的K值即為泊松模型成份數(shù)的最優(yōu)解.

Step11.根據(jù)最優(yōu)成份數(shù)K值所對(duì)應(yīng)的zik計(jì)算節(jié)點(diǎn)的簇標(biāo)記,即ηi=argmaxzik.

由以上步驟可以看出,加速泊松混合聚類在每次迭代過程中有一次分量的消除過程(Step 5)以及兩次加速收斂的步驟(Step 2和Step 8),這將大大地減少算法的迭代次數(shù).同時(shí)算法擁有最佳K值的判定過程(Step 10),這將使最終得到的模型成份數(shù)最優(yōu),節(jié)點(diǎn)聚類更合理.聚類完成后,算法進(jìn)入簇內(nèi)選擇簇首階段.

5.3 簇首選擇

本文算法在簇內(nèi)采用文獻(xiàn)[18]的三級(jí)簇首選擇機(jī)制選舉簇首,同時(shí)考慮剩余能量、簇內(nèi)總能耗以及簇內(nèi)節(jié)點(diǎn)的能耗均衡三個(gè)因素.首輪時(shí),簇內(nèi)所有節(jié)點(diǎn)參與競(jìng)選,選舉的簇首不但具有較高的剩余能量,而且能夠保證簇內(nèi)總能耗較低和簇內(nèi)節(jié)點(diǎn)能耗均衡.后續(xù)輪次時(shí),由上一輪簇首指定下一輪簇首.若上一輪簇首的剩余能量最高,則簇首不變;否則,上一輪簇首根據(jù)節(jié)點(diǎn)剩余能量以及與上一輪簇首的距離選擇下一輪簇首,節(jié)點(diǎn)與上一輪簇首的距離越近,簇內(nèi)總能耗越低,簇內(nèi)節(jié)點(diǎn)能耗越均衡.簇首確定后,算法進(jìn)入穩(wěn)定的數(shù)據(jù)傳輸階段.

5.4 數(shù)據(jù)傳輸

數(shù)據(jù)傳輸階段分為簇內(nèi)通信和簇間通信.在簇內(nèi),若節(jié)點(diǎn)到基站的距離小于到簇首的距離,則節(jié)點(diǎn)直接將數(shù)據(jù)傳輸至基站,否則,節(jié)點(diǎn)將數(shù)據(jù)傳輸至簇首.如圖1,E、F為普通節(jié)點(diǎn),D為其簇首,由距離關(guān)系可知,E直接將數(shù)據(jù)發(fā)送至基站,而F將數(shù)據(jù)發(fā)送至D.在簇間,則采用數(shù)據(jù)包在相鄰簇首間中繼轉(zhuǎn)發(fā)的方式,相鄰簇首包括已當(dāng)選為簇首的節(jié)點(diǎn)(普通簇首)和直接與基站通信的節(jié)點(diǎn)(獨(dú)立簇首).

圖1 CRPMM協(xié)議的網(wǎng)絡(luò)拓?fù)銯ig.1 Network topology of the CRPMM protocol

簇間中繼時(shí),下一跳簇首的選擇除了與剩余能量和距離有關(guān)外,實(shí)際上還與方向有關(guān)[19].如圖1所示,簇首B、C是和簇首A距離最近的下一跳簇首,A、B距離與A、C距離相等,且B、C的剩余能量也大致相等.但A到C的方向更加接近于A到基站的方向,方向用A到基站的連線與A到C的連線的夾角表示.在無線傳感器網(wǎng)絡(luò)中,該夾角可以通過定位方法計(jì)算出來.顯然,把C作為下一跳簇首比B更加理想.因此,本文提出了一種綜合考慮能量、距離和角度的多跳路由策略.

根據(jù)貪婪邊界無狀態(tài)路由GPSR[19]的思想,下一跳簇首應(yīng)具有較大的前進(jìn)距離.設(shè)N為當(dāng)前簇首,M為下一跳簇首,T為基站.為了更好地衡量前進(jìn)距離,本文提出相對(duì)距離的概念.相對(duì)距離即下一跳簇首到基站的距離與當(dāng)前簇首到基站的距離的比值,其表達(dá)式為:

Rd=MT/NT

(31)

根據(jù)基于角度的路由CR[19]的思想,路由策略應(yīng)選擇與當(dāng)前最優(yōu)路徑夾角φ較小的簇首作為下一跳,當(dāng)前最優(yōu)路徑為當(dāng)前簇首與基站的連線,這樣選擇的下一跳路徑能最快收斂于當(dāng)前最優(yōu)路徑,且整個(gè)轉(zhuǎn)發(fā)路徑最先收斂于理想最優(yōu)路徑,理想最優(yōu)路徑為源簇首到基站的連線.考慮余弦函數(shù)的特性,當(dāng)夾角越小時(shí),其值越大,否則,其值越小.因此,本文以cosφ來衡量下一跳路徑與當(dāng)前最優(yōu)路徑的夾角.

為了均衡簇首的能耗,路由策略應(yīng)選擇剩余能量較大的簇首作為下一跳.本文以sinπEi來衡量下一跳簇首的剩余能量.

綜上,新的簇間路由策略應(yīng)選擇剩余能量較大、相對(duì)距離較近且角度較小的簇首作為下一跳.本文以值Wi作為其度量標(biāo)準(zhǔn),其計(jì)算式為:

(32)

6 實(shí)驗(yàn)分析

為了驗(yàn)證CRPMM算法的性能,本文使用MATLAB仿真工具在四種不同的網(wǎng)絡(luò)規(guī)模下仿真LEACH[6]、DEBUC[13]和CRPMM三種協(xié)議的網(wǎng)絡(luò)壽命、網(wǎng)絡(luò)總能耗以及節(jié)點(diǎn)平均剩余能量.其中,橫坐標(biāo)為仿真時(shí)間,以輪數(shù)r表示.四種不同的網(wǎng)絡(luò)規(guī)模為100m×100m、200m×200m、400m×400m以及800m×800m,其所對(duì)應(yīng)的節(jié)點(diǎn)數(shù)目為100、400、1600和6400,其他仿真參數(shù)如表1所示.

表1 仿真參數(shù)表Table 1 Simulation parameters

6.1 網(wǎng)絡(luò)壽命

本文定義網(wǎng)絡(luò)壽命為從WSN的第一輪開始到10%節(jié)點(diǎn)失效的輪數(shù).圖2、圖3、圖4和圖5分別為四種不同規(guī)模網(wǎng)絡(luò)下三種協(xié)議的網(wǎng)絡(luò)壽命對(duì)比圖.縱坐標(biāo)為網(wǎng)絡(luò)壽命,以網(wǎng)絡(luò)中存活的節(jié)點(diǎn)數(shù)目表示.

由圖2-圖5可知,隨著網(wǎng)絡(luò)規(guī)模的增大,三種協(xié)議的網(wǎng)絡(luò)壽命在不斷減小.在小規(guī)模網(wǎng)絡(luò)中(如圖2和圖3),三種協(xié)議的網(wǎng)絡(luò)壽命分別為434輪、518輪、560輪和389輪、488輪、536輪,相對(duì)于LEACH和DEBUC協(xié)議,CRPMM協(xié)議在網(wǎng)絡(luò)壽命上分別延長(zhǎng)29.03%、8.11%和37.79%、9.84%;在中規(guī)模網(wǎng)絡(luò)中(如圖4),三種協(xié)議的網(wǎng)絡(luò)壽命分別為135輪、416輪和516輪,CRPMM協(xié)議在網(wǎng)絡(luò)壽命上分別延長(zhǎng)282.2%和24.04%;而在大規(guī)模網(wǎng)絡(luò)中(如圖5),三種協(xié)議的網(wǎng)絡(luò)壽命分別為48輪、241輪和378輪,CRPMM協(xié)議在網(wǎng)絡(luò)壽命上分別延長(zhǎng)687.5%和56.85%.

圖2 規(guī)模為100m×100m的網(wǎng)絡(luò)壽命對(duì)比Fig.2 Comparison of network lifetime in the scale of 100m×100m

圖3 規(guī)模為200m×200m的網(wǎng)絡(luò)壽命對(duì)比Fig.3 Comparison of network lifetime in the scale of 200m×200m

圖4 規(guī)模為400m×400m的網(wǎng)絡(luò)壽命對(duì)比Fig.4 Comparison of network lifetime in the scale of 400m×400m

圖5 規(guī)模為800m×800m的網(wǎng)絡(luò)壽命對(duì)比Fig.5 Comparison of network lifetime in the scale of 800m×800m

以上數(shù)據(jù)表明:相比較于小規(guī)模和中規(guī)模網(wǎng)絡(luò),CRPMM協(xié)議在大規(guī)模網(wǎng)絡(luò)中能夠明顯延長(zhǎng)網(wǎng)絡(luò)壽命.這是因?yàn)殡S著網(wǎng)絡(luò)的增大,LEACH的單跳通信以及DEBUC協(xié)議競(jìng)爭(zhēng)半徑的增加導(dǎo)致了能量的快速消耗,而本文利用K-means++算法和泊松混合模型優(yōu)化了K值,降低了節(jié)點(diǎn)能量的消耗速度,因此CRPMM協(xié)議更加適用于大規(guī)模網(wǎng)絡(luò).

6.2 網(wǎng)絡(luò)總能耗

圖6、圖7、圖8和圖9為四種不同規(guī)模下的三種協(xié)議的網(wǎng)絡(luò)總能耗對(duì)比圖,縱坐標(biāo)為網(wǎng)絡(luò)的總能量消耗.

圖6 規(guī)模為100m×100m的網(wǎng)絡(luò)總能耗Fig.6 Total network energy consumption in the scale of 100m×100m

圖7 規(guī)模為200m×200m的網(wǎng)絡(luò)總能耗Fig.7 Total network energy consumption in the scale of 200m×200m

圖8 規(guī)模為400m×400m的網(wǎng)絡(luò)總能耗Fig.8 Total network energy consumption in the scale of 400m×400m

圖9 規(guī)模為800m×800m的網(wǎng)絡(luò)總能耗Fig.9 Total network energy consumption in the scale of 800m×800m

網(wǎng)絡(luò)總能耗包括普通節(jié)點(diǎn)能耗、普通簇首能耗以及獨(dú)立簇首能耗.設(shè)普通節(jié)點(diǎn)xi每次采集k比特的數(shù)據(jù),則由能耗模型可知,普通節(jié)點(diǎn)能耗為:

(33)

其中,di-ch為普通節(jié)點(diǎn)與相應(yīng)簇首的距離.

設(shè)普通簇首xch所在的簇中共有t個(gè)節(jié)點(diǎn),上一跳簇首個(gè)數(shù)為m,則普通簇首能耗為:

(34)

其中,EDA為融合單位比特?cái)?shù)據(jù)的能耗,dch-ch為當(dāng)前簇首與下一跳簇首的距離,下一跳簇首包括普通簇首、獨(dú)立簇首以及基站.

由普通節(jié)點(diǎn)能耗和普通簇首能耗可知,簇內(nèi)總能耗為:

(35)

設(shè)網(wǎng)絡(luò)中共有l(wèi)個(gè)簇首與獨(dú)立簇首通信,則獨(dú)立簇首能耗為:

(36)

其中,dch-BS為獨(dú)立簇首與基站的距離.

設(shè)網(wǎng)絡(luò)中普通簇首個(gè)數(shù)為v,獨(dú)立簇首個(gè)數(shù)為s,則網(wǎng)絡(luò)總能耗為:

(37)

由圖6-圖9可知,在小規(guī)模(如圖6和圖7)和中規(guī)模網(wǎng)絡(luò)中(如圖8),三種協(xié)議的總能耗差異相對(duì)較小;而在大規(guī)模網(wǎng)絡(luò)中(如圖9),CRPMM協(xié)議的總能耗明顯低于其余兩種協(xié)議,說明在大規(guī)模網(wǎng)絡(luò)中CRPMM協(xié)議能夠有效地降低能耗.

隨著網(wǎng)絡(luò)規(guī)模的增大,LEACH協(xié)議由于簇間采用單跳通信,其節(jié)點(diǎn)能耗增加較快;DEBUC協(xié)議由于競(jìng)爭(zhēng)半徑增大,簇內(nèi)采用多徑衰落模型,其能耗增加也較快;而本文算法將K-means++和泊松混合聚類相結(jié)合,優(yōu)化了簇的數(shù)目K值,實(shí)現(xiàn)了節(jié)點(diǎn)的合理分簇,減緩了能耗的增加速率.因此,CRPMM協(xié)議更加適應(yīng)于大規(guī)模網(wǎng)絡(luò).

6.3 節(jié)點(diǎn)平均剩余能量

圖10、圖11、圖12和圖13為四種不同規(guī)模下三種協(xié)議的節(jié)點(diǎn)平均剩余能量對(duì)比圖,縱坐標(biāo)為節(jié)點(diǎn)的平均剩余能量.

節(jié)點(diǎn)的平均剩余能量越高,節(jié)點(diǎn)的能耗越均衡.從圖中可以得出,在小規(guī)模(如圖10和圖11)和中規(guī)模網(wǎng)絡(luò)中(如圖12),三種不同協(xié)議的節(jié)點(diǎn)平均剩余能量雖然不同,但差異相對(duì)較小;而在大規(guī)模網(wǎng)絡(luò)中(如圖13),本文算法的節(jié)點(diǎn)平均剩余能量在相同的輪數(shù)(如200輪)都明顯高于其余兩種協(xié)議,這說明在大規(guī)模網(wǎng)絡(luò)中CRPMM協(xié)議能夠更好地均衡節(jié)點(diǎn)能耗.

圖10 規(guī)模為100m×100m的節(jié)點(diǎn)平均剩余能量Fig.10 Average residual energy of the nodes in he scale of 100m×100m

圖11 規(guī)模為200m×200m的節(jié)點(diǎn)平均剩余能量Fig.11 Average residual energy of the nodes in the scale of 200m×200m

圖12 規(guī)模為400m×400m的節(jié)點(diǎn)平均剩余能量Fig.12 Average residual energy of the nodes in the scale of 400m×400m

圖13 規(guī)模為800m×800m 的節(jié)點(diǎn)平均剩余能量Fig.13 Average residual energy >of the nodes in the scale of 800m×800m

隨著監(jiān)測(cè)區(qū)域規(guī)模的增加,LEACH協(xié)議中與基站較遠(yuǎn)的簇首和與基站較近的簇首的能耗差距逐漸增大;DEBUC協(xié)議在簇間通信時(shí)由于重點(diǎn)考慮距離因素會(huì)使得簇首在選擇下一跳節(jié)點(diǎn)時(shí)過多偏離理想最優(yōu)路徑,從而增加多跳跳數(shù)和能量消耗;而本文算法在多跳通信時(shí)同時(shí)考慮了距離因素和角度因素,在保證多跳路徑偏離最優(yōu)路徑較小的情況下,均衡了簇首的能耗.因此,與其余兩種協(xié)議相比,CRPMM協(xié)議更加適應(yīng)于大規(guī)模網(wǎng)絡(luò).

7 結(jié)束語

針對(duì)諸多路由協(xié)議如LEACH、DEBUC等在大規(guī)模無線傳感網(wǎng)中的局限性,本文提出了一種適用于大規(guī)模網(wǎng)絡(luò)的基于泊松混合模型的成簇路由協(xié)議.該協(xié)議利用K-means++算法和泊松混合模型實(shí)現(xiàn)了節(jié)點(diǎn)的合理分簇;在簇間兼顧能量、距離和角度建立了能耗均衡的多跳路徑.實(shí)驗(yàn)仿真表明:與LEACH、DEBUC協(xié)議相比,本文算法在大規(guī)模網(wǎng)絡(luò)中具有較明顯的優(yōu)勢(shì),能夠有效延長(zhǎng)網(wǎng)絡(luò)生命周期,均衡節(jié)點(diǎn)的能耗.

雖然本文算法在大規(guī)模網(wǎng)絡(luò)中表現(xiàn)了良好的性能,但實(shí)際環(huán)境中節(jié)點(diǎn)的移動(dòng)以及異構(gòu)網(wǎng)絡(luò)的應(yīng)用越來越廣泛,為了更好地適應(yīng)傳感器網(wǎng)絡(luò)的發(fā)展,下一步的主要工作是在異構(gòu)網(wǎng)絡(luò)中對(duì)算法做出改進(jìn),使其更加適用于實(shí)際場(chǎng)合.

：

[1] Gherbi C,Aliouat Z,Benmohammed M.A Load-Balancing and self-adaptation clustering for lifetime prolonging in large scale wireless sensor networks [J].Procedia Computer Science,2015,73(1):66-75.

[2] Liao Fu-bao,Zhang Wen-mei,Li Xiang-yang,et al.New unequal clustering routing protocol for wireless sensor networks [J].Journal of Chinese Computer System,2015,36(6):1265-1270.

[3] Warrier M M,Kumar A.An energy efficient approach for routing in wireless sensor networks [J].Procedia Technology,2016,25(1):520-527.

[4] Basavaraju T G,Surekha K B,Mohan K G.An energy efficient routing protocol based on closeness factor for wireless sensor networks [J].International Journal of Networks and Communications,2015,5(2):31-36.

[5] Mohemed R E,Saleh A I,Abdelrazzak M,et al.Energy-efficient routing protocols for solving energy hole problem in wireless sensor networks [J].Computer Networks,2017,114(2):51-66.

[6] Heinzelman W,Chandrakasan A,Balakrishnan H.Energy-efficient communication protocol for wireless microsensor networks [C].Proceedings of the 33rd Annual Hawaii International Conference on System Sciences,2000:3005-3014.

[7] Li Cheng-fa,Chen Gui-hai,Ye Mao,et al.An uneven cluster based routing protocol for wireless sensor networks [J].Chinese Journal of Computers,2007,30(1):27-36.

[8] Zhang Wen-mei,Liao Fu-bao.Improved uneven clustering routing algorithm for wireless sensor networks [J].Chinese Journal of Sensors and Actuators,2015,28(5):739-743.

[9] Zhang Ya-qiong.Research on uniform clustering routing algorithm based on K-means in wireless sensor network [J].Control Engineering of China,2015,22(6):1181-1185.

[10] Zhang Pin,Wang Jia-jia,Zhan Meng.An energy efficient uneven clustering routing algorithm for wireless sensor networks [J].Chinese Journal of Sensors and Actuators,2016,29(12):1919-1923.

[11] Hui Lin,Halit Uster.Exact and heuristic algorithms for data-gathering cluster-based wireless sensor network design problem [J].IEEE Transactions on Networking,2014,22(3):903-916.

[12] Li Jian-zhou,Wang Hai-tao,Tao An.An energy balanced clustering routing protocol for WSN [J].Chinese Journal of Sensors and Actuators,2013,26(3):396-401.

[13] Jiang Chang-jiang,Shi Wei-ren,Tang Xian-lun,et al.Energy-balanced unequal clustering routing protocol for wireless sensor networks [J].Journal of Software,2012,23(5):1222-1232.

[14] Sun Yan-qing,Peng Jian,Liu Tang,et al.Uneven clustering routing protocol based on dynamic partition for wireless sensor network [J].Journal on Communications,2014,35(1):198-206.

[15] Xu Yi-xin,Bai Yan,Zhao Tian-yang,et al.Multi-objective coverage control in wireless sensor network based on poisson distribution [J].Journal of Computer Applications,2013,33(7):1820-1824.

[16] Arthur D,Vassilvitskii S.K-means++:the advantages of careful seeding [C].Proceedings of the 18rd Annual Acm-Siam Symposium on Discrete Algorithms,2007,11(6):1027-1035.

[17] Zhou Shi-bing,Xu Zhen-yuan,Tang Xu-qing.New method for determining optimal number of clusters in K-means clustering algorithm [J].Computer Engineering and Applications,2010,46(16):27-31.

[18] Zhai Chun-jie,Xu Jian-min,Liu Yong-gui.Energy-consumption balancing routing protocol based on regions [J].Chinese Journal of Sensors and Actuators,2016,29(1):80-87.

[19] Xie Zhi-heng,Zhang Xiang-li,He Long,et al.Distance and direction based routing scheme in wireless sensor networks [J].Computer Engineering and Applications,2010,46(31):109-110.

附中文參考文獻(xiàn)：

[2] 廖福保,張文梅,李向陽，等.無線傳感器網(wǎng)絡(luò)中一種新的非均勻分簇路由協(xié)議[J].小型微型計(jì)算機(jī)系統(tǒng),2015,36 (6):1265-1270.

[7] 李成法,陳貴海,葉 懋,等.一種基于非均勻分簇的無線傳感器網(wǎng)絡(luò)路由協(xié)議[J].計(jì)算機(jī)學(xué)報(bào),2007,30(1):27-36.

[8] 張文梅,廖福寶.改進(jìn)的無線傳感器網(wǎng)絡(luò)非均勻分簇路由算法[J].傳感技術(shù)學(xué)報(bào),2015,28(5):739-743.

[9] 張雅瓊.基于K-means的無線傳感網(wǎng)均勻分簇路由算法研究[J].控制工程,2015,22(6):1181-1185.

[10] 張 品,王佳佳,占 夢(mèng).能量高效的無線傳感器網(wǎng)絡(luò)非均勻分簇路由算法[J].傳感技術(shù)學(xué)報(bào),2016,29(12):1919-1923.

[12] 李建洲,王海濤,陶 安.一種能耗均衡的WSN分簇路由協(xié)議[J].傳感技術(shù)學(xué)報(bào),2013,26(3):396-401.

[13] 蔣暢江,石為人,唐賢倫,等.能量均衡的無線傳感器網(wǎng)絡(luò)非均勻分簇路由協(xié)議[J].軟件學(xué)報(bào),2012,23(5):1222-1232.

[14] 孫彥清,彭 艦,劉 唐,等.基于動(dòng)態(tài)分區(qū)的無線傳感器網(wǎng)絡(luò)非均勻成簇路由協(xié)議[J].通信學(xué)報(bào),2014,35(1):198-206.

[15] 徐奕昕,白 焰,趙天陽,等.泊松分布下無線傳感器網(wǎng)絡(luò)多目標(biāo)覆蓋控制[J].計(jì)算機(jī)應(yīng)用,2013,33(7):1820-1824.

[17] 周世兵,徐振源,唐旭清.新的K-均值算法最佳聚類數(shù)確定方法[J].計(jì)算機(jī)工程與應(yīng)用,2010,46(16):27-31.

[18] 翟春杰,徐建閩,劉永桂.基于分區(qū)的能耗均衡路由協(xié)議[J].傳感技術(shù)學(xué)報(bào),2016,29(1):80-87.

[19] 謝志恒,張向利,何 龍,等.基于距離和角度的無線傳感器網(wǎng)絡(luò)路由方案[J].計(jì)算機(jī)工程與應(yīng)用,2010,46(31):109-110.