大規(guī)模無(wú)線傳感網(wǎng)基于CFSFDP和泊松混合模型的分簇路由算法*

陶志勇,王和章,劉 影

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

大規(guī)模無(wú)線傳感網(wǎng)基于CFSFDP和泊松混合模型的分簇路由算法*

陶志勇*,王和章,劉 影

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

針對(duì)無(wú)線傳感網(wǎng)隨規(guī)模的擴(kuò)大其節(jié)點(diǎn)能量利用率較低的問(wèn)題,提出了一種適用于大規(guī)模無(wú)線傳感網(wǎng)的基于CFSFDP和泊松混合模型的分簇路由算法(CRCPMM)。其核心思想是:在基站利用改進(jìn)的CFSFDP算法自動(dòng)估計(jì)簇的數(shù)目K值并選取聚類(lèi)中心,然后運(yùn)用泊松混合模型將節(jié)點(diǎn)合理聚類(lèi),以保證聚類(lèi)效果最優(yōu);簇間采用多跳傳輸方式,綜合考慮簇首等效剩余能量、簇首之間的距離以及多跳路徑與理想最優(yōu)路徑之間的角度。仿真結(jié)果表明:與低功耗自適應(yīng)集簇(LEACH)協(xié)議、分布式能量有效非均勻成簇(DEBUC)協(xié)議相比,CRCPMM協(xié)議在大規(guī)模網(wǎng)絡(luò)中具有明顯的優(yōu)勢(shì),能夠有效均衡節(jié)點(diǎn)能耗,延長(zhǎng)網(wǎng)絡(luò)生命周期。

無(wú)線傳感器網(wǎng)絡(luò);能耗均衡;CFSFDP;泊松混合模型;角度

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

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

LEACH[7]是最早提出的一種均勻分簇路由協(xié)議,相比較于平面路由協(xié)議,其能量利用率較高,生命周期較長(zhǎng);但隨機(jī)的簇首選舉和簇間單跳通信易導(dǎo)致某些節(jié)點(diǎn)由于能耗過(guò)快而過(guò)早死亡。因此,李成法等人[8]提出了一種不均勻的成簇路由協(xié)議-EEUC(Energy-Efficient Uneven Clustering),它通過(guò)控制簇首的競(jìng)爭(zhēng)半徑來(lái)調(diào)整簇的規(guī)模,使靠近基站的簇規(guī)模較小,這樣距離基站較近的簇首會(huì)由于簇內(nèi)能耗的降低而預(yù)留足夠的能量來(lái)轉(zhuǎn)發(fā)其他簇首的數(shù)據(jù);然而簇首的選擇只由概率和門(mén)限值決定,無(wú)法保證所選簇首最優(yōu)。Hui等人[9]提出了混合整數(shù)線性規(guī)劃模型,以此來(lái)確定簇首的最佳位置。陳海南等人[10]提出利用遺傳算法和概率準(zhǔn)則的有效結(jié)合來(lái)均衡網(wǎng)絡(luò)能耗。張雅瓊[11]提出利用K-means算法均勻分簇,避免了極大簇和極小簇的情況;但K-means算法對(duì)初始聚類(lèi)中心敏感,聚類(lèi)效果不理想。Rodriguez等人[12]提出了一種綜合考慮局部密度和距離的聚類(lèi)算法-CFSFDP(Clustering by Fast Search and Find of Density Peaks),該算法能夠從網(wǎng)絡(luò)中選取最優(yōu)聚類(lèi)中心;但聚類(lèi)中心的選擇需要借助人工輔助,很難應(yīng)用于實(shí)踐。因此,在此基礎(chǔ)上,馬春來(lái)等人[13]提出了一種聚類(lèi)中心自動(dòng)選取策略,通過(guò)引入拐點(diǎn)實(shí)現(xiàn)CFSFDP算法的自動(dòng)化。

蔣暢江等人[14]提出了DEBUC(Distributed Energy-Balanced Unequal Clustering)協(xié)議,它利用節(jié)點(diǎn)的競(jìng)爭(zhēng)半徑選擇候選簇首,根據(jù)候選簇首以及其鄰居節(jié)點(diǎn)的剩余能量通過(guò)基于時(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í)能耗增加較快。孫彥清等人[15]提出了UCDP(Uneven Clustering routing protocol based on Dynamic Partition)協(xié)議,它利用能量均衡的非均勻分區(qū)算法將網(wǎng)絡(luò)合理動(dòng)態(tài)分區(qū),選舉簇首與區(qū)頭協(xié)作通信,通過(guò)簇內(nèi)單跳、區(qū)內(nèi)以及區(qū)間多跳相結(jié)合的方式建立一個(gè)能耗最優(yōu)的路由協(xié)議;但在路徑建立時(shí),簇內(nèi)以及簇間需要多次通信。

本文綜合以上問(wèn)題,在改進(jìn)算法的基礎(chǔ)上提出了一種適用于大規(guī)模無(wú)線傳感網(wǎng)的分簇路由算法。該算法在基站利用改進(jìn)的CFSFDP算法自動(dòng)估計(jì)類(lèi)數(shù)K值和選取聚類(lèi)中心;通過(guò)泊松混合模型將節(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ò)中具有良好的性能。

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

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

本文假設(shè)N個(gè)傳感器節(jié)點(diǎn)隨機(jī)分布在M×M的監(jiān)測(cè)區(qū)域內(nèi),且傳感器網(wǎng)絡(luò)具有如下性質(zhì)[14]:①基站在監(jiān)測(cè)區(qū)域外,傳感器節(jié)點(diǎn)在監(jiān)測(cè)區(qū)域內(nèi),部署后位置均不變。②所有節(jié)點(diǎn)同構(gòu),即具有相似的能力(處理/通信),且都有唯一的節(jié)點(diǎn)標(biāo)識(shí)號(hào)。③鏈路對(duì)稱(chēng),即已知發(fā)射端的發(fā)射功率,接收端可以根據(jù)接收到的信號(hào)強(qiáng)度估算兩者的距離。④節(jié)點(diǎn)的發(fā)射功率以及通信半徑可以根據(jù)需要自動(dòng)調(diào)整。⑤節(jié)點(diǎn)具有位置感知能力。⑥相對(duì)于節(jié)點(diǎn)感知范圍而言,監(jiān)測(cè)區(qū)域遠(yuǎn)大于單個(gè)節(jié)點(diǎn)的感知區(qū)域。

1.2 能耗模型

本文采用文獻(xiàn)[7]的能耗模型,即一階無(wú)線電模型。發(fā)射端向距離為d的接收端發(fā)送l比特?cái)?shù)據(jù)的能耗為:

(1)

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

ERx(l)=lEelec

(2)

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

2 大規(guī)模分簇路由算法-CRCPMM

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

2.1 改進(jìn)的CFSFDP算法

經(jīng)典聚類(lèi)算法如K-means、K-medoids等在聚類(lèi)時(shí)首先需要確定最終聚類(lèi)數(shù)K以及初始種子節(jié)點(diǎn),而兩者的選擇大多采用隨機(jī)或人為指定的方式,這使得算法帶有一定的主觀性和隨意性。因此本文提出在利用泊松混合聚類(lèi)前先采用改進(jìn)的CFSFDP聚類(lèi)算法選取初始種子節(jié)點(diǎn)以及估計(jì)網(wǎng)絡(luò)K值。為了降低能耗,本文采用集中式的方法,由基站控制運(yùn)行改進(jìn)的CFSFDP算法。

局部密度ρi主要用來(lái)刻畫(huà)聚類(lèi)中心的鄰居節(jié)點(diǎn)個(gè)數(shù)。鄰居節(jié)點(diǎn)個(gè)數(shù)越多,ρi越大;反之,ρi越小。根據(jù)局部密度的含義,其表達(dá)式為:

(3)

式中:dc為截?cái)嗑嚯x。由式(3)可知,與節(jié)點(diǎn)xi的距離小于dc的節(jié)點(diǎn)數(shù)越多,ρi越大。

d1≤d2≤…≤dNN

(4)

取dc=df(NNt),f(NNt)表示對(duì)NNt進(jìn)行四舍五入運(yùn)算,t取經(jīng)驗(yàn)值0.02[12]。

ρq1≥ρq2≥…ρqN

(5)

根據(jù)距離的含義,其表達(dá)式為:

(6)

盡管CFSFDP無(wú)需復(fù)雜的參數(shù)設(shè)置和迭代運(yùn)算[13],但是在選取聚類(lèi)中心時(shí)仍需要人工輔助?；诖?本文在局部密度ρi和距離δi的基礎(chǔ)上提出一種適用于CFSFDP的聚類(lèi)中心自動(dòng)選取策略,其核心思想在于對(duì)決策圖中拐點(diǎn)的刻畫(huà)。

聚類(lèi)中心自動(dòng)選取策略首先將ρi和δi的歸一化乘積γi作為節(jié)點(diǎn)的決策值,其表達(dá)式為式(7)。然后將γi按照降序排列并取前n(n=N/3)[13]個(gè)節(jié)點(diǎn)作為聚類(lèi)中心候選節(jié)點(diǎn)。本文以網(wǎng)絡(luò)中共有100個(gè)節(jié)點(diǎn)為例,其決策圖如圖1。

(7)

圖1 決策圖

由圖1可知,按照γi減小的方向聚類(lèi)中心候選節(jié)點(diǎn)的密度逐漸增大,且在某一特殊點(diǎn)密度變化最大,此特殊點(diǎn)即為拐點(diǎn)。候選節(jié)點(diǎn)xi的密度為與xi的γi值小于ε的其他候選節(jié)點(diǎn)數(shù)目,其表達(dá)式為:

(8)

式中:χij為特殊函數(shù),其計(jì)算公式為:

(9)

為了更好地刻畫(huà)拐點(diǎn),本文引入密度變化率,其表達(dá)式為式(10)。根據(jù)上述拐點(diǎn)的含義,密度變化率最大的候選節(jié)點(diǎn)即為拐點(diǎn),圖1的拐點(diǎn)判斷圖如圖2所示。設(shè)拐點(diǎn)的決策值為γt,則K值為決策值不小于γt的聚類(lèi)中心候選節(jié)點(diǎn)數(shù)目,其所對(duì)應(yīng)的節(jié)點(diǎn)即為初始種子節(jié)點(diǎn)。本文以上述K值和初始種子節(jié)點(diǎn)對(duì)泊松混合聚類(lèi)進(jìn)行初始化。

DCRi=βi+1-βi

(10)

圖2 拐點(diǎn)判斷圖

2.2 加速泊松混合聚類(lèi)

在二維地理空間位置部署的大量傳感器節(jié)點(diǎn)通常是獨(dú)立隨機(jī)分布的,這種分布方式適用于分析沒(méi)有先驗(yàn)知識(shí)的地理環(huán)境。傳感器節(jié)點(diǎn)通常采用高空灑落的方式部署在難以監(jiān)測(cè)的環(huán)境中,節(jié)點(diǎn)的位置可以看作服從二維泊松分布[16]。設(shè)傳感器節(jié)點(diǎn)在單位監(jiān)測(cè)區(qū)域A內(nèi)呈密度為λ的隨機(jī)分布,則區(qū)域內(nèi)的節(jié)點(diǎn)數(shù)N(A)服從泊松分布,其概率為:

(11)

式中:‖A‖表示單位監(jiān)測(cè)區(qū)域的面積。

2.2.1 建立泊松混合模型

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

假設(shè)服從泊松混合分布的隨機(jī)節(jié)點(diǎn)為xi,則其概率可表示為:

(12)

式中:πk為每個(gè)泊松模型分量的混合系數(shù),代表其所包含的節(jié)點(diǎn)數(shù)占總節(jié)點(diǎn)數(shù)的比例;K為泊松模型分量的個(gè)數(shù);MDik為節(jié)點(diǎn)xi與聚類(lèi)中心ck的曼哈頓距離,MDmin為MDik的最小值,即MDmin=min{MDik,k=1,2,…,K};P(xi|λk,nk)表示第k個(gè)泊松模型的分布律,λk為其均值,nk為該模型分量所包含的節(jié)點(diǎn)數(shù),其表達(dá)式為:

(13)

設(shè)Z={zik}為隱變量集,zik表示節(jié)點(diǎn)xi屬于第k類(lèi)的概率,泊松模型的參數(shù)為θk=(λk,nk),則節(jié)點(diǎn)集的最大對(duì)數(shù)似然函數(shù)為:

(14)

2.2.2 改進(jìn)的EM算法

本文采用EM算法迭代求解式(14)的最大似然參數(shù)。EM算法(Expectation Maximization Algorithm)是一種迭代優(yōu)化求解概率模型參數(shù)的最大似然估計(jì)方法,其具體步驟分為兩步:E-Step和M-Step。

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

(15)

(16)

(17)

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

(18)

泊松模型分量的均值:

(19)

隱變量:

(20)

(21)

(22)

(23)

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

(24)

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

(25)

為了使算法快速逼近最優(yōu)解,迭代開(kāi)始時(shí)令α=1,同時(shí)初始化混合系數(shù)πk=1/K。隨著迭代的進(jìn)行,相比較于式(14),式(24)的似然函數(shù)L(zik,πk|x)增加速度較快,且前后兩次迭代的混合系數(shù)差異越來(lái)越小,直到α=0,迭代停止。

(26)

(27)

(28)

2.2.3 求解最優(yōu)K值

2.2.4 加速泊松混合聚類(lèi)的基本步驟

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

Step 11 根據(jù)最優(yōu)成份數(shù)K值所對(duì)應(yīng)的zik以及能耗均衡性確定節(jié)點(diǎn)的簇標(biāo)記,即對(duì)于節(jié)點(diǎn)xi,從zik中選擇兩個(gè)較大值,并計(jì)算其能負(fù)比,從中選擇值最大的作為節(jié)點(diǎn)的簇。能負(fù)比為聚類(lèi)中心的剩余能量與該類(lèi)中節(jié)點(diǎn)數(shù)的比值,其表達(dá)式為式(29),Ej表示剩余能量,nj表示節(jié)點(diǎn)個(gè)數(shù)。

ECRj=Ej/nj

(29)

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

2.3 簇首選擇

本文算法在簇內(nèi)采用文獻(xiàn)[17]的三級(jí)簇首選擇機(jī)制選舉簇首,同時(shí)考慮剩余能量、簇內(nèi)總能耗以及簇內(nèi)節(jié)點(diǎn)的能耗均衡3個(gè)因素。

由文獻(xiàn)[15]可知,節(jié)點(diǎn)可以獲取自身的當(dāng)前剩余能量Er;由1.1可知,節(jié)點(diǎn)具有位置感知能力,即任意兩個(gè)節(jié)點(diǎn)之間的距離是已知的,則簇內(nèi)某一節(jié)點(diǎn)當(dāng)選為簇首時(shí)的簇內(nèi)總能耗TECi為:

(30)

式中:l,Eelec,εfs,dk-i的意義與式(1)相同。

由式(1)可知,簇內(nèi)節(jié)點(diǎn)向簇首發(fā)送數(shù)據(jù)時(shí)所消耗的能量與距離的平方成正比,簇內(nèi)節(jié)點(diǎn)到簇首的距離的差異越小,簇內(nèi)節(jié)點(diǎn)的能耗越均衡。因此,當(dāng)簇內(nèi)某一節(jié)點(diǎn)當(dāng)選為簇首時(shí),簇內(nèi)節(jié)點(diǎn)的能耗均衡性EBi為:

(31)

首輪時(shí),簇內(nèi)所有節(jié)點(diǎn)參與競(jìng)選,選舉的簇首不但具有較高的剩余能量,而且能夠保證簇內(nèi)總能耗較低和簇內(nèi)節(jié)點(diǎn)能耗均衡。后續(xù)輪次時(shí),本文算法采用由上一輪簇首指定下一輪簇首的方式。若上一輪簇首的剩余能量最高,則簇首不變;否則,上一輪簇首根據(jù)節(jié)點(diǎn)剩余能量以及與自身的距離選擇下一輪簇首。下一輪簇首與上一輪簇首的距離越近,簇內(nèi)總能耗越低,簇內(nèi)節(jié)點(diǎn)能耗越均衡。簇首確定后,算法進(jìn)入穩(wěn)定的數(shù)據(jù)傳輸階段。

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

數(shù)據(jù)傳輸階段分為簇內(nèi)通信和簇間通信。在簇內(nèi),若節(jié)點(diǎn)到基站的距離小于到簇首的距離,則節(jié)點(diǎn)直接將數(shù)據(jù)傳輸至基站,否則,節(jié)點(diǎn)將數(shù)據(jù)傳輸至簇首。在簇間,采用數(shù)據(jù)包在相鄰簇首間中繼轉(zhuǎn)發(fā)的方式,相鄰簇首包括已當(dāng)選為簇首的節(jié)點(diǎn)和直接與基站通信的節(jié)點(diǎn)。

簇間中繼時(shí),下一跳簇首的選擇除了與等效剩余能量和距離有關(guān)外,實(shí)際上還與方向有關(guān)[18]。因此,本文提出了一種綜合考慮等效能量、距離和角度的多跳路由策略。

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

(32)

根據(jù)CR[18]的思想,路由策略應(yīng)選擇與當(dāng)前最優(yōu)路徑夾角φ較小的簇首作為下一跳,這樣選擇的下一跳路徑能最快收斂于當(dāng)前最優(yōu)路徑,且整個(gè)轉(zhuǎn)發(fā)路徑最先收斂于理想最優(yōu)路徑,理想最優(yōu)路徑為源簇首到基站的連線。在WSN中,該夾角φ可以通過(guò)定位技術(shù)計(jì)算得出[19]?？紤]余弦函數(shù)的特性,當(dāng)夾角越小時(shí),其值越大,否則,其值越小。因此,本文以cosφ來(lái)衡量下一跳路徑與當(dāng)前最優(yōu)路徑的夾角。

為了均衡簇首的能耗,路由策略應(yīng)選擇等效剩余能量較大的簇首作為下一跳。等效剩余能量為簇首剩余能量與簇內(nèi)節(jié)點(diǎn)個(gè)數(shù)的關(guān)系,本文以sin(πEi)來(lái)衡量簇首的剩余能量,以式(33)來(lái)衡量簇內(nèi)節(jié)點(diǎn)個(gè)數(shù),mi為第i個(gè)簇內(nèi)的節(jié)點(diǎn)數(shù),mmax為最大的簇所包含的節(jié)點(diǎn)數(shù)。等效剩余能量的計(jì)算公式為式(34),由公式可知,簇首剩余能量越大,所包含的節(jié)點(diǎn)數(shù)越少,其等效剩余能量越大。

(33)

(34)

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

(35)

2.5 算法時(shí)間復(fù)雜度分析

CRCPMM算法的時(shí)間復(fù)雜度由四部分組成,即CFSFDP的時(shí)間復(fù)雜度、加速泊松混合聚類(lèi)的時(shí)間復(fù)雜度以及簇首選擇和數(shù)據(jù)傳輸?shù)臅r(shí)間復(fù)雜度。

假設(shè)網(wǎng)絡(luò)中共有N個(gè)節(jié)點(diǎn),候選聚類(lèi)中心個(gè)數(shù)為n,簇首數(shù)目為K,則CRCPMM算法的時(shí)間復(fù)雜度為O(N2)。

證明CRCPMM算法利用改進(jìn)的CFSFDP自動(dòng)估計(jì)聚類(lèi)中心個(gè)數(shù)。首先,基站計(jì)算參數(shù)dij,ρi,δi,時(shí)間復(fù)雜度均為O(N2);其次,計(jì)算ρi和δi的歸一化乘積γi,并將γi按照降序排列,時(shí)間復(fù)雜度分別為O(N)和O(nlogn);然后,計(jì)算βi和密度變化率DCRi,時(shí)間復(fù)雜度分別為O(n2)和O(n)。因此,CFSFDP的時(shí)間復(fù)雜度為:

O(N2+N2+N2+N+nlogn+n2+n)=O(N2)

(36)

在加速泊松混合聚類(lèi)中,首先建立泊松混合模型,時(shí)間復(fù)雜度為O(N);其次,利用EM算法迭代求解概率模型參數(shù),設(shè)迭代次數(shù)為t,則其時(shí)間復(fù)雜度為O(NKt);然后將節(jié)點(diǎn)聚類(lèi),時(shí)間復(fù)雜度為O(N)。因此,加速泊松混合聚類(lèi)的時(shí)間復(fù)雜度為O(N+N+NKt)。

在簇首選擇過(guò)程中,節(jié)點(diǎn)需要計(jì)算其作為簇首時(shí)的TECi和EBi,時(shí)間復(fù)雜度均為O(N)。在數(shù)據(jù)傳輸過(guò)程中,簇首需要計(jì)算下一跳簇首的EREi,cosφ,Rd,時(shí)間復(fù)雜度均為O(K2)。因此,簇首選擇和數(shù)據(jù)傳輸過(guò)程的時(shí)間復(fù)雜度為O(N+N+K2+K2+K2),即O(N+K2)。

根據(jù)以上分析,由于N≥K且N≥t,因此整個(gè)算法的時(shí)間復(fù)雜度為O(N2)。

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

為了驗(yàn)證CRCPMM算法的性能,本文分別在不同的網(wǎng)絡(luò)規(guī)模下仿真LEACH[7]、DEBUC[14]和CRCPMM 3種協(xié)議的網(wǎng)絡(luò)壽命、網(wǎng)絡(luò)總能耗以及節(jié)點(diǎn)平均剩余能量,橫坐標(biāo)為仿真時(shí)間,以輪數(shù)表示。其中,4種網(wǎng)絡(luò)規(guī)模分別為100 m×100 m、200 m×200 m、400 m×400 m以及800 m×800 m,網(wǎng)絡(luò)中的節(jié)點(diǎn)總數(shù)分別為100、400、1600和6400。具體仿真參數(shù)如表1所示。

表1 仿真參數(shù)表

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

本文定義網(wǎng)絡(luò)壽命為從WSN的第一輪開(kāi)始到10%節(jié)點(diǎn)失效的輪數(shù)。圖3～圖6分別為4種不同網(wǎng)絡(luò)規(guī)模下3種協(xié)議的網(wǎng)絡(luò)壽命對(duì)比圖,縱坐標(biāo)為網(wǎng)絡(luò)中存活的節(jié)點(diǎn)個(gè)數(shù)。

圖3 規(guī)模為100 m×100 m的網(wǎng)絡(luò)壽命對(duì)比

圖4 規(guī)模為200 m×200 m的網(wǎng)絡(luò)壽命對(duì)比

圖5 規(guī)模為400 m×400 m的網(wǎng)絡(luò)壽命對(duì)比

圖6 規(guī)模為800 m×800 m的網(wǎng)絡(luò)壽命對(duì)比

由以上4個(gè)圖可知,隨著網(wǎng)絡(luò)規(guī)模的增大,3種協(xié)議的網(wǎng)絡(luò)壽命在不斷減小。在小規(guī)模網(wǎng)絡(luò)中(如圖3和圖4),3種協(xié)議的網(wǎng)絡(luò)壽命分別為435輪、516輪、559輪和389輪、488輪、546輪,相對(duì)于LEACH和DEBUC協(xié)議,CRCPMM協(xié)議在網(wǎng)絡(luò)壽命上分別延長(zhǎng)28.5%、8.33%和40.35%、11.88%;在中規(guī)模網(wǎng)絡(luò)中(如圖5),3種協(xié)議的網(wǎng)絡(luò)壽命分別為135輪、416輪和526輪,CRCPMM協(xié)議在網(wǎng)絡(luò)壽命上分別延長(zhǎng)289.6%和26.44%;而在大規(guī)模網(wǎng)絡(luò)中(如圖6),3種協(xié)議的網(wǎng)絡(luò)壽命分別為48輪、241輪和383輪,CRCPMM協(xié)議在網(wǎng)絡(luò)壽命上分別延長(zhǎng)697.9%和58.92%。

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

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

圖7～圖10為4種不同網(wǎng)絡(luò)規(guī)模下3種協(xié)議的網(wǎng)絡(luò)總能耗對(duì)比圖,縱坐標(biāo)為網(wǎng)絡(luò)的總能量消耗。

圖9 規(guī)模為400 m×400 m的網(wǎng)絡(luò)總能耗

圖7 規(guī)模為100 m×100 m的網(wǎng)絡(luò)總能耗

圖8 規(guī)模為200 m×200 m的網(wǎng)絡(luò)總能耗

圖10 規(guī)模為800 m×800 m的網(wǎng)絡(luò)總能耗

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

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

圖12 規(guī)模為200 m×200 m的節(jié)點(diǎn)平均剩余能量

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

圖11～圖14為4種不同網(wǎng)絡(luò)規(guī)模下3種協(xié)議的節(jié)點(diǎn)平均剩余能量對(duì)比圖,縱坐標(biāo)為節(jié)點(diǎn)的平均剩余能量。

圖11 規(guī)模為100 m×100 m的節(jié)點(diǎn)平均剩余能量

圖13 規(guī)模為400 m×400 m的節(jié)點(diǎn)平均剩余能量

圖14 規(guī)模為800 m×800 m的節(jié)點(diǎn)平均剩余能量

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

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

4 結(jié)束語(yǔ)

針對(duì)諸多路由協(xié)議如LEACH、DEBUC等在大規(guī)模無(wú)線傳感網(wǎng)中的局限性,本文提出了一種適用于大規(guī)模網(wǎng)絡(luò)的基于CFSFDP和泊松混合模型的分簇路由算法。該算法利用改進(jìn)的CFSFDP和泊松混合模型實(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)境中移動(dòng)節(jié)點(diǎn)以及異構(gòu)網(wǎng)絡(luò)的應(yīng)用越來(lái)越廣泛,為了更好地適應(yīng)傳感器網(wǎng)絡(luò)的發(fā)展,下一步的主要工作是在異構(gòu)網(wǎng)絡(luò)中對(duì)算法做出改進(jìn),使其更加適用于實(shí)際場(chǎng)合。

[1] Zhang D,Li G,Zheng K,et al. An Energy-Balanced Routing Method Based on Forward-Aware Factor for Wireless Sensor Network[J]. IEEE Transactions on Industrial Informatics,2013,10(1):766-773.

[2] Gherbi C,Aliouat Z,Benmohammed M. An Adaptive Clustering Approach to Dynamic Load Balancing and Energy Efficiency in Wireless Sensor Networks[J]. Energy,2016(114):647-662.

[3] Arora V K,Sharma V,Sachdeva M. A Survey on LEACH and Other’s Routing Protocols in Wireless Sensor Network[J]. Optik-International Journal for Light and Electron Optics,2016,127(16):6590-6600.

[4] 吳勇,張靈. 基于多目標(biāo)優(yōu)化的WSN簇首選擇算法[J]. 傳感技術(shù)學(xué)報(bào),2016,29(7):1062-1067.

[5] Barati H,Movaghar A,Rahmani A M. EACHP:Energy Aware Clustering Hierarchy Protocol for Large Scale Wireless Sensor Networks[J]. Wireless Personal Communications,2015,85(3):765-789.

[6] 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.

[7] Heinzelman W,Chandrakasan A,Balakrishnan H. An Application-Specific Protocol Architecture for Wireless Microsensor Networks[J]. IEEE Transactions on Wireless Communication,2002,1(4):660-670.

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

[9] Lin H,Uster H. Exact and Heuristic Algorithms for Data-Gathering Cluster-Based Wireless Sensor Network Design Problem[J]. IEEE Transactions on Networking,2014,22(3):903-916.

[10] 陳海南,劉廣聰,吳曉鴿,等. 一種基于遺傳算法與概率轉(zhuǎn)發(fā)的分簇協(xié)議[J]. 計(jì)算機(jī)科學(xué),2015,42(3):71-73.

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

[12] Rodriguez A,Laio A. Clustering by Fast Search and Find of Density Peaks[J]. Science,2014,344(6191):1492-1496.

[13] 馬春來(lái),單洪,馬濤,等. 一種基于CFSFDP改進(jìn)算法的重要地點(diǎn)識(shí)別方法研究[J]. 計(jì)算機(jī)應(yīng)用研究,2017,34(1):136-140.

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

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

[16] Liu B Y,Towsley D. A Study of the Coverage of Large-Scale Sensor Networks[C]//Proceedings of 2004 IEEE International Conference on Mobile Ad-Hoc and Sensor Systems. Piscataway:IEEE Press,2004:475-483.

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

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

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

陶志勇(1978-),男,博士,副教授,碩士生導(dǎo)師,主要研究方向是多媒體通信,82456020@qq.com;

王和章(1992-),男,碩士研究生,主要研究方向是無(wú)線傳感網(wǎng)路由協(xié)議;

劉影(1983-),女,博士,講師,主要研究方向是無(wú)線網(wǎng)絡(luò)定位和物聯(lián)網(wǎng)。

ClusteringRoutingAlgorithmBasedonCFSFDPandPoissonMixtureModelinLarge-ScaleWirelessSensorNetworks*

TAOZhiyong*,WANGHezhang,LIUYing

(School of Electrics and Information Engineering,Liaoning Technical University,Huludao Liaoning 125105,China)

With the expansion of the scale in wireless sensor networks,the node energy utilization becomes lower. A clustering routing algorithm is proposed,which was based on CFSFDP and poisson mixture model(CRCPMM)for the large-scale wireless sensor networks. Its core idea is that it uses modified CFSFDP algorithm to estimate theKvalue of the number of clusters and select clustering center automatically at base station. Then it utilizes poisson mixture model to cluster the nodes reasonably to ensure the optimal clustering. In the inter-cluster,the CRCPMM algorithm adopts multi-hop transmission mode,which considers cluster-heads equivalent residual energy,the distances among cluster-heads and the angles between multi-hop paths and ideal optimal path. Simulation results show that compared with the LEACH(Low Energy Adaptive Clustering Hierarchy)protocol and the DEBUC(Distributed Energy Balanced Unequal Clustering routing)protocol,the CRCPMM protocol has obvious advantages in the large-scale networks,which can balance energy consumption of nodes and extend the network lifetime effectively.

wireless sensor networks;energy consumption balancing;CFSFDP;poisson mixture model;angle

TP393

A

1004-1699(2017)11-1719-10

項(xiàng)目來(lái)源:國(guó)家自然科學(xué)基金項(xiàng)目(61240014);遼寧省自然基金項(xiàng)目(2015020100);遼寧省博士啟動(dòng)基金(20170520098)

2017-04-17修改日期2017-07-05

10.3969/j.issn.1004-1699.2017.11.018