無(wú)線傳感器網(wǎng)絡(luò)分簇算法的研究

無(wú)線傳感器網(wǎng)絡(luò)分簇算法的研究

1合理運(yùn)用能量有效性無(wú)線傳感器網(wǎng)絡(luò)（wsd）是一個(gè)分布傳感器網(wǎng)絡(luò)，由具有計(jì)算、存儲(chǔ)和無(wú)線通信能力的小型智能設(shè)備組成。傳感器節(jié)點(diǎn)負(fù)責(zé)收集監(jiān)測(cè)區(qū)域內(nèi)的聲音、電磁或地震信號(hào)等多種信息,通過(guò)無(wú)線信道將它們發(fā)送到Sink節(jié)點(diǎn)(或稱匯聚點(diǎn)、基站basestation)。Sink節(jié)點(diǎn)具有更強(qiáng)的處理能力,能夠進(jìn)一步處理信息,或擁有更大的發(fā)送范圍,可以將信息送往某個(gè)大型網(wǎng)絡(luò),使遠(yuǎn)程用戶能夠檢索到該信息。通常傳感器節(jié)點(diǎn)體積都非常小,只具有有限的計(jì)算能力、有限的存儲(chǔ)能力、有限的無(wú)線通信能力和有限的電源供應(yīng)(電池供電),因此滿足能量有效性成為無(wú)線傳感器網(wǎng)絡(luò)通信協(xié)議設(shè)計(jì)的主要目標(biāo)。所謂能量有效性是指網(wǎng)絡(luò)在有限的能源條件下能夠處理的請(qǐng)求數(shù)量。具體表現(xiàn)在WSN中就是盡量節(jié)約傳感器的能量,最大化地延長(zhǎng)工作的壽命。理論和實(shí)驗(yàn)證明,采用層次路由比平面路由更能滿足能量有效性的要求。層次路由通過(guò)分簇算法對(duì)無(wú)線傳感器網(wǎng)絡(luò)中的節(jié)點(diǎn)進(jìn)行層次劃分,將數(shù)據(jù)采集和通信任務(wù)分配給角色不同的節(jié)點(diǎn)執(zhí)行,有利于能耗在全網(wǎng)節(jié)點(diǎn)上的均勻、一致地分布,達(dá)到提高工作壽命的目的。分簇算法也可以用于執(zhí)行數(shù)據(jù)融合,數(shù)據(jù)融合將傳感器感測(cè)的大量數(shù)據(jù)組合成少量有意義的信息集合,在達(dá)到應(yīng)用規(guī)定的數(shù)據(jù)率的條件下,傳輸?shù)南⒃缴俟?jié)省的能量就越多。本文主要討論根據(jù)節(jié)點(diǎn)的分布數(shù)目與區(qū)域特征,對(duì)分簇算法中如何確定成簇的數(shù)目以及層數(shù)進(jìn)行優(yōu)化分析,使之滿足能量有效性的要求,并通過(guò)仿真結(jié)果進(jìn)行驗(yàn)證。2多層分簇算法分簇是對(duì)網(wǎng)絡(luò)中的節(jié)點(diǎn)進(jìn)行層次劃分,若干地理位置相鄰節(jié)點(diǎn)構(gòu)成一個(gè)簇,每個(gè)簇內(nèi)選舉一個(gè)簇首(clusterheader)。簇內(nèi)的節(jié)點(diǎn)將采集到的數(shù)據(jù)直接傳送給簇首,而簇首將數(shù)據(jù)融合后發(fā)送到sink,如果簇首距離sink比較遠(yuǎn),可以通過(guò)其它簇首進(jìn)行轉(zhuǎn)發(fā)。在分簇算法中主要包括成簇、簇維護(hù)、簇內(nèi)路由和簇間路由4個(gè)部分。成簇主要解決如何在動(dòng)態(tài)分布式網(wǎng)絡(luò)環(huán)境下使節(jié)點(diǎn)高效地聚集成簇,它是分簇算法的關(guān)鍵,簇維護(hù)解決在節(jié)點(diǎn)移動(dòng)過(guò)程中的簇結(jié)構(gòu)維護(hù),其中包括移動(dòng)節(jié)點(diǎn)退出和加入簇、簇的產(chǎn)生和消亡等功能。簇內(nèi)(intra-cluster)和簇間(inter-cluster)路由主要是從降低能量消耗的角度,選擇最優(yōu)化的路由。衡量一個(gè)分簇算法的優(yōu)劣主要有以下幾個(gè)標(biāo)準(zhǔn),簇結(jié)構(gòu)的穩(wěn)定性,簇首節(jié)點(diǎn)的數(shù)量以及負(fù)載均衡度等。無(wú)線傳感器網(wǎng)絡(luò)中最具有代表性的分簇算法是低功耗自適應(yīng)簇類路由協(xié)議即(LEACH,LowEnergyAdaptiveClusteringHierarchy),LEACH中定義了“輪(round)”的概念,一輪由初始化和穩(wěn)定工作兩個(gè)階段組成;LEACH實(shí)現(xiàn)了一個(gè)負(fù)載平衡進(jìn)程,允許不同節(jié)點(diǎn)在不同的時(shí)間以隨機(jī)概率P成為簇首,平均分擔(dān)中繼通信業(yè)務(wù)。同平面路由協(xié)議相比,LEACH提高了網(wǎng)絡(luò)的整體性能,均衡了傳感器節(jié)點(diǎn)之間的能量消耗;后續(xù)很多分簇算法都是在LEACH基礎(chǔ)上進(jìn)行改進(jìn)。多層分簇是無(wú)線傳感器網(wǎng)絡(luò)的一種新的分簇實(shí)現(xiàn)機(jī)制,這種算法的設(shè)計(jì)思想是根據(jù)所要求達(dá)到的層數(shù),在原來(lái)傳統(tǒng)分簇的基礎(chǔ)上,采用由底至上(bottom-up)的原則繼續(xù)進(jìn)行分簇,每一層的簇首由下一層簇首以一定的概率產(chǎn)生,直到最高層的簇首選出,就完成了整個(gè)分簇體系。在多層分簇中,假設(shè)網(wǎng)絡(luò)節(jié)點(diǎn)被分成h層簇,則整個(gè)通信過(guò)程是由最底層的傳感器節(jié)點(diǎn)將采集的數(shù)據(jù)傳遞給第1層簇首,第1層簇首將數(shù)據(jù)融合后傳遞給第2層簇首,這樣依次進(jìn)行下去。最后,當(dāng)?shù)贏層簇首收到來(lái)自第h-1層簇首發(fā)送來(lái)的數(shù)據(jù),進(jìn)行融合處理后發(fā)送到Sink節(jié)點(diǎn)。因此,整個(gè)通信過(guò)程中所消耗的能量為每層通信所消耗能量的求和。多層分簇更好地滿足了能量有效性要求,但實(shí)施的復(fù)雜度也有所增加。3成簇的數(shù)目成簇是分簇算法的關(guān)鍵問(wèn)題,而如何在給定的網(wǎng)絡(luò)條件下,達(dá)到合適的成簇?cái)?shù)目并且滿足能量有效性的要求成為設(shè)計(jì)成簇的核心思想。成簇的數(shù)目不能太多也不能太少,如果太多將會(huì)引入大量的成簇開(kāi)銷,節(jié)點(diǎn)的能耗將增大,而且可允許復(fù)用的網(wǎng)絡(luò)資源有限:如果數(shù)目太少,每個(gè)簇內(nèi)的成員節(jié)點(diǎn)數(shù)增多,簇首將承擔(dān)過(guò)重的收發(fā)負(fù)擔(dān),能量消耗增加而導(dǎo)致過(guò)早死亡,因此合適的成簇?cái)?shù)目不僅可以均衡節(jié)點(diǎn)的能耗,延長(zhǎng)工作壽命,而且可以有效地提高鏈路的利用率。下面分別對(duì)單層分簇和多層分簇中成簇?cái)?shù)目的優(yōu)化問(wèn)題進(jìn)行討論。3.1系統(tǒng)模型的計(jì)算確定合理的簇首數(shù)目是建立在充分考慮能量有效性的基礎(chǔ)之上,因此,首先定義節(jié)點(diǎn)在通信過(guò)程中能量損耗模型。我們使用文獻(xiàn)中的無(wú)線通信系統(tǒng)模型進(jìn)行計(jì)算,該模型由發(fā)送電路、功率放大器和接收電路構(gòu)成,當(dāng)發(fā)端傳輸b比特?cái)?shù)據(jù)到距離為d的接收端時(shí),發(fā)送所消耗的能量為接收所消耗的能量為ERx=bEelect其中為距離的臨界值,當(dāng)收發(fā)之間的距離小于該臨界值,則使用自由空間模型;如果大于該值,則使用雙路徑模型。各個(gè)參數(shù)的具體含義和取值如表1所示。3.2打造網(wǎng)絡(luò)空間總能量的求解初始化狀態(tài)網(wǎng)絡(luò)中節(jié)點(diǎn)具有相同的能量,簇首的產(chǎn)生一般有兩種情況,首先節(jié)點(diǎn)以廣播的形式向鄰居節(jié)點(diǎn)發(fā)送成簇信息,相鄰節(jié)點(diǎn)根據(jù)收到信號(hào)的強(qiáng)弱選擇準(zhǔn)備加入的簇,并向發(fā)送節(jié)點(diǎn)返回確認(rèn)消息,則發(fā)送節(jié)點(diǎn)成為自愿簇首(volunteerclusterhead);如果節(jié)點(diǎn)沒(méi)有收到其它節(jié)點(diǎn)的消息,則節(jié)點(diǎn)成為強(qiáng)迫簇首(forcedclusterhead),最終成簇?cái)?shù)目為兩種簇首數(shù)目之和。假設(shè)無(wú)線傳感器網(wǎng)絡(luò)中有N個(gè)節(jié)點(diǎn),分布在邊長(zhǎng)為A×A的正方形區(qū)域內(nèi),分布密度服從參數(shù)為λ=N/A2的泊松分布,Sink節(jié)點(diǎn)位于分布區(qū)域以外,節(jié)點(diǎn)的傳播范圍為r,理想的成簇概率為P,其中自愿簇首的概率為P1,強(qiáng)迫簇首的概率為P2,最終成簇的數(shù)目為K-NP,簇首節(jié)點(diǎn)的分布密度為λ1=pλ,普通節(jié)點(diǎn)的分布密度λ0=(1-p)λ。如果λ1,λ0相互獨(dú)立,則根據(jù)文獻(xiàn)的推論結(jié)果,每個(gè)簇內(nèi)的成員節(jié)點(diǎn)的數(shù)目為,簇內(nèi)成員到簇首的平均距離為dtoCH=1/(πλ1),設(shè)簇內(nèi)節(jié)點(diǎn)發(fā)送數(shù)據(jù)給簇首所消耗的能量為Eno-CH,根據(jù)能量損耗模型則有:簇首將收到的數(shù)據(jù)進(jìn)行融合處理后發(fā)送給匯聚點(diǎn),消耗能量為ECH:將式(1),式(2)代入到式(4)中,令p=K/N,并將λ1,λ0轉(zhuǎn)換為以k為自變量的函數(shù),得到消耗總能量的表達(dá)式:從式(6)可知,在給定分布區(qū)域大小A和節(jié)點(diǎn)數(shù)目N的條件下,代入相關(guān)能量參數(shù)可以得到滿足能量有效性條件下的理想分簇?cái)?shù)目K。當(dāng)確定簇首數(shù)目以后,可求得成簇概率p=K/N,則節(jié)點(diǎn)成為自愿簇首概率P1和強(qiáng)迫簇首概率P2滿足下式:證明隨機(jī)變量X表示網(wǎng)絡(luò)中產(chǎn)生簇首數(shù)目,節(jié)點(diǎn)i成為簇首,則有Xi=1(i=1,2,…,N),設(shè)Xi,1,Xi,2分別表示節(jié)點(diǎn)i成為自愿簇首或是強(qiáng)迫簇首,兩者相互獨(dú)立。其中(節(jié)點(diǎn)i沒(méi)選作自愿簇首的概率)又因,所以式(7)成立。證畢在單層分簇的基礎(chǔ)上,根據(jù)層數(shù)的要求繼續(xù)對(duì)網(wǎng)絡(luò)中的節(jié)點(diǎn)進(jìn)行分簇,假設(shè)每層簇首數(shù)目為ki,其中i=1,2,…,h,h為最高層。對(duì)于第i層的節(jié)點(diǎn)來(lái)說(shuō),簇首數(shù)目ki是在第i-1層ki-1個(gè)節(jié)點(diǎn)中以一定概率產(chǎn)生,每個(gè)簇內(nèi)有ki-1/ki成員節(jié)點(diǎn),簇首的分布密度服從λi=ki/A2。根據(jù)上節(jié)的分析,一個(gè)簇內(nèi)消耗的總能量為簇首和成員節(jié)點(diǎn)的能量之和,即其中簇內(nèi)成員消耗的能量:簇首消耗的能量分為兩種情況:當(dāng)簇首節(jié)點(diǎn)處于i=h層時(shí),收集和處理后的數(shù)據(jù)將直接發(fā)送到匯聚節(jié)點(diǎn),而當(dāng)層數(shù)小于h時(shí),簇首將數(shù)據(jù)發(fā)送到其相鄰的第i+1層節(jié)點(diǎn),因此:綜上,第i層中ki個(gè)簇所消耗的總能量為網(wǎng)絡(luò)所消耗的總能量是各層能耗的求和,由于最高層的簇首直接將數(shù)據(jù)發(fā)送給匯聚節(jié)點(diǎn)sink,同其底下各層簇節(jié)點(diǎn)的操作有所不同,先對(duì)第1層到第h-1層所消耗的能量進(jìn)行求和,最后再加上最高層h的能耗。具體求解如下:令從i=1到i=h-1所消耗的能量為,則有表達(dá)式:令i=h消耗的能量為,則有表達(dá)式將式(12),式(13)合并得到網(wǎng)絡(luò)消耗的總能量,化簡(jiǎn)整理后:根據(jù)總能量的表達(dá)式,當(dāng)滿足能耗最小值時(shí),直接求解每層的成簇?cái)?shù)目比較困難。可以通過(guò)對(duì)式(14)求不同參數(shù)的導(dǎo)數(shù)后,得出成簇?cái)?shù)目之間的關(guān)系式。因,對(duì)式(14)進(jìn)行變形整理。當(dāng),得到k1與k2之間的關(guān)系式當(dāng),得到ki與之間關(guān)系式當(dāng),得到kh所滿足的關(guān)系式從上面的關(guān)系式中可知,隨著分簇層數(shù)的增加,計(jì)算復(fù)雜度也隨之增加,因此,多層分簇中層數(shù)取值并不越大越好,過(guò)多的分層反而將會(huì)產(chǎn)生較大的通信開(kāi)銷。針對(duì)多層分簇中成簇?cái)?shù)目和分層數(shù)目不能通過(guò)理論分析直接求得,我們將采用仿真的方法做進(jìn)一步的分析。4目數(shù)提出的節(jié)能方案首先建立一個(gè)簡(jiǎn)單的網(wǎng)絡(luò)模型,100個(gè)傳感器節(jié)點(diǎn)均勻分布在100m×100m的正方形區(qū)域內(nèi)組成一個(gè)無(wú)線傳感器網(wǎng)絡(luò),匯聚節(jié)點(diǎn)sink位于分布區(qū)域之外,能量參數(shù)的取值如表1所示,每個(gè)節(jié)點(diǎn)的初始能量為2J,數(shù)據(jù)包大小為500byte。每一輪持續(xù)的時(shí)間為175s,總共進(jìn)行了5次仿真,最終結(jié)果取平均值。對(duì)于單層分簇,通過(guò)改變成簇的數(shù)目(k的取值從1到10),觀察網(wǎng)絡(luò)能量消耗的大小變化,如圖1所示,隨著成簇?cái)?shù)目的增加,系統(tǒng)的總能耗先減少后增加,當(dāng)成簇?cái)?shù)目k=3時(shí),能耗取得最小值。這同理論分析得出k=2.8的結(jié)果非常相近。分簇?cái)?shù)目的增大而導(dǎo)致能耗增加的原因主要是當(dāng)網(wǎng)絡(luò)中簇的數(shù)目過(guò)多時(shí),簇內(nèi)與簇間節(jié)點(diǎn)需要維護(hù)的通信開(kāi)銷就增多,因而能耗也隨之增大,特別是簇首與匯聚節(jié)點(diǎn)之間的通信采用的是雙路徑模型,距離sink較遠(yuǎn)的簇首能量消耗會(huì)更大。所以在確定滿足能量有效性的成簇?cái)?shù)目時(shí),應(yīng)當(dāng)充分依據(jù)節(jié)點(diǎn)的數(shù)目和分布區(qū)域等具體的網(wǎng)絡(luò)特征。對(duì)于多層分簇,我們?cè)趩螌臃执氐幕A(chǔ)上繼續(xù)對(duì)其分簇,當(dāng)層數(shù)達(dá)到5時(shí)終止程序的執(zhí)行。得到層數(shù)與能耗之間的變化關(guān)系如圖2所示。隨著分簇層數(shù)的增加,網(wǎng)絡(luò)的總能耗也相應(yīng)減少,這同理論分析是一致的,尤其是當(dāng)分簇的層數(shù)從1層增加到2層時(shí),能耗降低了10%左右,變化幅度非常明顯,而當(dāng)層數(shù)再繼續(xù)增加時(shí),能耗的降低幅度變得比較小。因此,采用多層分簇進(jìn)一步節(jié)約節(jié)點(diǎn)的能耗是可取的,但是考慮到實(shí)施的復(fù)雜度,并不是層數(shù)越多越好。當(dāng)分簇的層數(shù)達(dá)到2或3時(shí),從節(jié)能和降低復(fù)雜度兩方面均衡考慮,效果是比較理想的。根據(jù)以上的討論,我們對(duì)節(jié)能效果比較好的2層分簇算法作進(jìn)一步的研究,主要根據(jù)式(15)和式(16)對(duì)如何確定每層的成簇?cái)?shù)目進(jìn)行分析。k1,k2分別表示第1層簇首和第2層簇首的數(shù)目,兩者不同的取值引起網(wǎng)絡(luò)的能耗變化。在圖3所示的三維曲面圖中,顏色的深淺程度表示了能耗大小的變化趨勢(shì),其中最深色區(qū)域表示能量的最小值,此時(shí)求得,第1層簇首<的取值接近9,第2層簇首k2的取值在之間。該結(jié)果驗(yàn)證了多層分簇對(duì)節(jié)約節(jié)點(diǎn)能耗和延長(zhǎng)工作壽命有重要作用,尤其是層數(shù)值較低的多層分簇,總