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

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

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