分簇算法在傳感器網(wǎng)絡(luò)中的應(yīng)用

分簇算法在傳感器網(wǎng)絡(luò)中的應(yīng)用

1基于空間相關(guān)性的網(wǎng)絡(luò)結(jié)構(gòu)無(wú)線傳感器網(wǎng)絡(luò)（無(wú)線傳感器網(wǎng)絡(luò)）是由許多傳感器節(jié)點(diǎn)以自組織的方式創(chuàng)建的無(wú)線網(wǎng)絡(luò)。目標(biāo)是相互信任地感知、收集和處理網(wǎng)絡(luò)覆蓋區(qū)域內(nèi)感知對(duì)象的信息，并將其傳輸給用戶。它是集數(shù)據(jù)采集、數(shù)據(jù)處理、數(shù)據(jù)傳輸于一體的復(fù)雜系統(tǒng)。傳感器網(wǎng)絡(luò)與傳統(tǒng)無(wú)線網(wǎng)絡(luò)相比,具有節(jié)點(diǎn)電池能量、通信能力、計(jì)算和存儲(chǔ)能力有限等特點(diǎn)。因此,WSN路由協(xié)議必須以節(jié)約能源和提高網(wǎng)絡(luò)生存時(shí)間為目標(biāo)。移動(dòng)代理平面路由算法LCF要求移動(dòng)代理遍歷感知區(qū)域內(nèi)所有節(jié)點(diǎn),消耗了大量的能量,所以基于數(shù)據(jù)相關(guān)性的分簇路由算法相對(duì)平面路由算法具有更好的適應(yīng)性和節(jié)能性。基于地理信息的GAF分簇算法根據(jù)節(jié)點(diǎn)的位置信息和通信半徑,把監(jiān)測(cè)區(qū)域劃分成若干虛擬單元格。但虛擬單元格的劃分并未考慮WSN節(jié)點(diǎn)關(guān)于位置信息的感知數(shù)據(jù)空間相關(guān)性。文獻(xiàn)基于用戶查詢誤差門限,提出的CAG算法通過(guò)比較簇頭與其鄰居節(jié)點(diǎn)感知數(shù)據(jù)值的大小進(jìn)行分簇。但簇的建立過(guò)程需要相鄰節(jié)點(diǎn)互相通信,增加了通信開銷和時(shí)延。數(shù)據(jù)相關(guān)性馬爾可夫(Markovian)模型中某節(jié)點(diǎn)的感知數(shù)據(jù)值可按不同概率由其它相鄰節(jié)點(diǎn)的感知數(shù)據(jù)值得到,但模型只針對(duì)規(guī)則拓?fù)浣Y(jié)構(gòu),非規(guī)則拓?fù)浣Y(jié)構(gòu)未能涉及。本文在文獻(xiàn)的基礎(chǔ)上提出了一種新的基于空間相關(guān)性的事件驅(qū)動(dòng)傳感器網(wǎng)絡(luò)分簇算法(Event-DrivenClusteringAlgorithm,EDCA)。當(dāng)一個(gè)事件被觸發(fā),匯聚節(jié)點(diǎn)(Sink)無(wú)需知道感知區(qū)域內(nèi)節(jié)點(diǎn)的感知數(shù)據(jù)值,即可由用戶查詢誤差門限及數(shù)據(jù)相關(guān)性馬爾可夫模型將感知區(qū)域劃分成虛擬極坐標(biāo)等價(jià)層。每個(gè)等價(jià)層根據(jù)層內(nèi)節(jié)點(diǎn)當(dāng)前剩余能量選出簇頭;由匯聚節(jié)點(diǎn)派出的移動(dòng)代理只需收集滿足用戶要求的少量有意義的簇頭感知信息,從而減少了網(wǎng)絡(luò)的大量冗余感知數(shù)據(jù)的傳輸,節(jié)省了能量開銷。本文安排如下:第2節(jié)討論空間相關(guān)性模型;第3節(jié)給出了基于空間相關(guān)性的事件驅(qū)動(dòng)傳感器網(wǎng)絡(luò)分簇算法;第4節(jié)給出了仿真結(jié)果和性能分析;第5節(jié)為結(jié)束語(yǔ)。2相關(guān)模型的空間相關(guān)性2.1極坐標(biāo)中同向隨機(jī)變量的估計(jì)統(tǒng)計(jì)學(xué)利用變量圖(variogram)作數(shù)據(jù)相關(guān)性分析。假設(shè)位于(x,y)、(xr,yr)的節(jié)點(diǎn)S(x,y),,其感知數(shù)據(jù)值為V(x,y),V(xr,yr),則變量圖為其中(x-xr)2+(y-yr)2=r2。特別地,若V(xi,yi)(i=1,2,…,m(r))為一組節(jié)點(diǎn)的感知數(shù)據(jù),則γ(r)的估計(jì)值為:其中(x-xi)2+(y-yi)2=r2。因γ(r)為同向隨機(jī)變量,于是在極坐標(biāo)中定義節(jié)點(diǎn)S(r,θ)的數(shù)據(jù)值為V(r,θ),且其分布密度函數(shù)為fV(v);顯然V(r,θ)也為同向隨機(jī)變量。不失一般性,假設(shè)事件觸發(fā)點(diǎn)位于(0,0),其數(shù)據(jù)值為V(0,0),則由圖1有:其中U=H表示V(0,0)由相鄰節(jié)點(diǎn)的感知數(shù)據(jù)值獲得,其概率為1-β;U=T表示V(0,0)由隨機(jī)變量Y獲得,其概率為β;隨機(jī)變量Y和Z與V互相獨(dú)立,且Z～N(0,σZ2),方差zσ可由式(2)統(tǒng)計(jì)計(jì)算求得;隨機(jī)變量R的分布密度函數(shù)為;隨機(jī)變量Θ的分布密度函于是選取θ1=0,θ2=2π,事件感知半徑L區(qū)域內(nèi)的節(jié)點(diǎn)可分布為以事件觸發(fā)點(diǎn)為中心,相應(yīng)于不同感知精度和γ(r)的一系列虛擬同心圓,如圖2。圖2中在相同圓上的節(jié)點(diǎn)具有相同的感知精度,于是數(shù)據(jù)相關(guān)性馬爾可夫模型為其中Vkri(1≤k≤N(ri),0<ri<rmax)為與S(0,0)距離ri的節(jié)點(diǎn)集中的第k個(gè)節(jié)點(diǎn)的數(shù)據(jù)值。3基于相關(guān)空間的事件驅(qū)動(dòng)傳感器網(wǎng)絡(luò)的分割算法3.1節(jié)點(diǎn)性估計(jì)模型圖2給出了事件感知區(qū)域內(nèi)傳感器節(jié)點(diǎn)隨感知精度變化的規(guī)則拓?fù)浣Y(jié)構(gòu),但實(shí)際問(wèn)題通常為非規(guī)則拓?fù)浣Y(jié)構(gòu),如圖3?；贑AG算法,不妨假設(shè)事件觸發(fā)點(diǎn)(0,0)為虛擬簇頭S0r1,其讀數(shù)為,則圖3第1個(gè)虛擬同心圓內(nèi)第k個(gè)節(jié)點(diǎn)Skr1(1≤k≤N(r1))的讀數(shù)Vkr1(rk,θk)滿足:|Vkr1(rk,θk)-V0r1(r1)|<μ,其中μ是用戶查詢誤差門限;而第1個(gè)虛擬同心圓上節(jié)點(diǎn)S0r2的讀數(shù)滿足:|V0r2(r2)-V0r1(r1)|≤μ,于是:其中C(σz,μ)是σz,μ的函數(shù),。通常γ(r)有多種估計(jì)模型,本文由文獻(xiàn)選取γ(r)=c(1-e-λr2),參數(shù)c和λ可由節(jié)點(diǎn)歷史數(shù)據(jù)按式(2)計(jì)算求得。于是綜上,第i(1≤i≤n)個(gè)虛擬圓環(huán)內(nèi)第k個(gè)節(jié)點(diǎn)Skri(1≤k≤N(ri))的讀數(shù)Vkri(rk,θk)滿足:|Vkri(rk,θk)-V0ir(ri)|<μ,|Vkri(rk,θk)-V0r1(r1)|<iμ;而第i個(gè)虛擬同心圓上虛擬簇頭S0ir的讀數(shù)V0ir(ri)滿足:|V0ir(ri)-V0r1(r1)|≤(i-1)μ,于是:,其中取使得上式為實(shí)數(shù)的最大值。若,則rn+1=rmax;反之,則;由此構(gòu)成半徑序列。3.2sisk網(wǎng)絡(luò)效應(yīng)步驟1Sink由事件觸發(fā)點(diǎn)和相關(guān)性模型(4)確定事件驅(qū)動(dòng)半徑L,即節(jié)點(diǎn)感知區(qū)域。步驟2Sink由節(jié)點(diǎn)位置和半徑序列{ir},將節(jié)點(diǎn)感知區(qū)域劃分成虛擬等價(jià)層。步驟3Sink選出虛擬等價(jià)層中剩余能量最大的節(jié)點(diǎn)作為簇頭。步驟4Sink派出移動(dòng)代理訪問(wèn)各簇頭,收集、融合數(shù)據(jù),并將融合后的信息帶回Sink,再由Sink發(fā)送給用戶。4網(wǎng)絡(luò)參數(shù)的確定利用MATLAB仿真平臺(tái)測(cè)試本文新算法EDCA的性能。假設(shè)在500m×500m的區(qū)域內(nèi)隨機(jī)拋撒600個(gè)無(wú)線傳感器節(jié)點(diǎn),每個(gè)節(jié)點(diǎn)產(chǎn)生一個(gè)100字節(jié)的數(shù)據(jù)包,并隨機(jī)給每個(gè)節(jié)點(diǎn)賦予不同的初始能量;根據(jù)相關(guān)性模型式(4)給每個(gè)節(jié)點(diǎn)賦值;隨機(jī)生成事件觸發(fā)點(diǎn)和Sink。圖4(a)中當(dāng)用戶查詢誤差門限μ確定時(shí),隨著相關(guān)性參數(shù)σz的增加,則EDCA的虛擬等價(jià)層的數(shù)目相應(yīng)減少,移動(dòng)代理訪問(wèn)的簇頭數(shù)目也相應(yīng)減少,從而EDCA比LCF減少了大量冗余數(shù)據(jù)的傳輸。例如固定μ=1.5,EDCA數(shù)據(jù)傳輸能量比LCF最多減少了89.15%。圖4(b)固定σz=2.7,隨著用戶查詢誤差門限μ的增大,移動(dòng)代理訪問(wèn)的簇頭數(shù)目也相應(yīng)減少,從而EDCA的數(shù)據(jù)傳輸能量比LCF最多減少了89.75%,提高了能量效率。通常移動(dòng)代理訪問(wèn)的相關(guān)性節(jié)點(diǎn)越多,收集的感知信息越精確,但能量開銷也會(huì)大大增加,不利于節(jié)能;而EDCA中移動(dòng)代理訪問(wèn)較少相關(guān)性節(jié)點(diǎn)也能滿足用戶精度要求,如圖5。圖5(a)中當(dāng)感知區(qū)域內(nèi)的節(jié)點(diǎn)相關(guān)性確定時(shí),EDCA中移動(dòng)代理訪問(wèn)較少簇頭時(shí)(如圖5(b)),其精度與LCF和CAG非常接近,也能滿足用戶要求。圖5(c)中當(dāng)σz=2.3時(shí),隨著用戶查詢誤差門限μ的增大,EDCA的誤差只比CAG最大多0.2858%,而圖5(d)中簇頭數(shù)目比CAG最小少30%。因此EDCA中移動(dòng)代理收集的相關(guān)性數(shù)據(jù)的精度接近于CAG,但減少了大量冗余數(shù)據(jù)的傳輸,達(dá)到節(jié)能目的。5提升網(wǎng)絡(luò)能量效率本文在無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)據(jù)相關(guān)性馬爾可夫模型的基礎(chǔ)上,根據(jù)用戶查詢誤差門限將事件驅(qū)動(dòng)的感知區(qū)域劃分成虛擬極坐標(biāo)等價(jià)層,構(gòu)造了一種新的分簇算法:EDCA。算法不僅可收集滿足用戶不同要求的感知信息,而且大大減少了傳輸數(shù)據(jù)量,提高了網(wǎng)絡(luò)能量效率。仿真結(jié)果顯示EDCA的節(jié)能性能優(yōu)于遍歷所有感知節(jié)點(diǎn)的LCF和根據(jù)感知數(shù)據(jù)進(jìn)行分簇的CAG。數(shù)為,且假設(shè)不妨假設(shè)為虛擬簇頭,則第2個(gè)虛擬圓環(huán)內(nèi)第k個(gè)節(jié)點(diǎn)的讀數(shù)滿足:;而第2個(gè)虛擬同心圓上虛擬簇頭的讀數(shù)滿足:。EDCA的性能可由(1)數(shù)據(jù)傳輸能量減少率,其中TE為數(shù)據(jù)傳輸能量;(2)事件觸發(fā)點(diǎn)的真實(shí)值(