基于虛擬區(qū)域劃分的wsn網(wǎng)絡(luò)非均衡簇路由算法

基于虛擬區(qū)域劃分的wsn網(wǎng)絡(luò)非均衡簇路由算法

0熱區(qū)問題和多源異構(gòu)網(wǎng)絡(luò)的協(xié)調(diào)解決方法在集群組織的傳感器網(wǎng)絡(luò)中，傳感器節(jié)點的角色分為兩個部分。集群頭和聚集成員。作為集群的中心，簇頭負責(zé)創(chuàng)建簇的結(jié)構(gòu)，收集集群成員的數(shù)據(jù)，并進行整合和傳輸。由于集群距離收集節(jié)點的距離通常很遠，因此有必要通過集群頭形成的骨干網(wǎng)實現(xiàn)多跳道路徑，這有利于節(jié)能。然而，這種方法導(dǎo)致了能耗不平衡的問題。由于需要大量其他集群數(shù)據(jù)，集群節(jié)點附近的節(jié)點負擔(dān)沉重，過度消耗自己的能量，網(wǎng)絡(luò)分離，網(wǎng)絡(luò)生存時間減少。研究人員稱之為，這個問題是一個“熱區(qū)域”。在傳統(tǒng)的同構(gòu)網(wǎng)絡(luò)分簇協(xié)議中,通過周期性地重新選擇簇頭(如LEACH,HEED),可以平衡簇頭與簇成員節(jié)點之間的能量消耗,但不能解決上述的“熱區(qū)”問題.以節(jié)點的剩余能量為依據(jù)選擇簇頭的方法(如EECS)也不能完全解決這個問題,因為它只是在網(wǎng)絡(luò)的局部比較節(jié)點剩余能量,無法從整體上協(xié)調(diào)節(jié)點的能量消耗以解決“熱區(qū)”問題.可以認為上述兩種方法都是以被動的方式來均衡網(wǎng)絡(luò)中節(jié)點的能量消耗,即在網(wǎng)絡(luò)中出現(xiàn)能量消耗不均衡之后才采取措施來均衡能量消耗.通過對傳感器節(jié)點能量消耗情況和無線傳感器網(wǎng)絡(luò)路由協(xié)議的研究,我們提出一種基于單元格的帶管理節(jié)點的分簇路由協(xié)議TCBCRP(traffic-basedclusterroutingprotocol),該協(xié)議的主要思想是利用可補充能量的匯聚節(jié)點采用集中式方式將傳感器節(jié)點覆蓋的區(qū)域固定劃分為許多單元格,每個單元格作為一個簇.在每個簇中設(shè)置一個管理節(jié)點,管理節(jié)點基于Markov模型的流量預(yù)測,以分布式方式實現(xiàn)每個簇中簇頭的重新選舉,以減少成簇的開銷,實現(xiàn)簇頭的均衡能量消耗,同時增強網(wǎng)絡(luò)的健壯性,延長WSN網(wǎng)絡(luò)生存時間.1節(jié)點位置及功能假設(shè)傳感器節(jié)點隨機分布在一個正方形監(jiān)測區(qū)域內(nèi),并且該傳感器網(wǎng)絡(luò)具有以下性質(zhì):1.以匯聚節(jié)點為中心建立無線傳感器網(wǎng)絡(luò)環(huán)境,節(jié)點均勻分布于匯聚節(jié)點四周,以匯聚節(jié)點為原點建立坐標系;2.匯聚節(jié)點具有較強的計算、存儲能力,且能量能無限制;3.所有傳感器節(jié)點部署后靜止不動,并且具有相同的初始能量值,具有相似的處理通信能力,地位是對稱平等的;4.所有節(jié)點都是同構(gòu)的,具備數(shù)據(jù)融合的功能;5.根據(jù)接收者的距離遠近,節(jié)點可以自由調(diào)節(jié)其發(fā)送功率以節(jié)約能量消耗;6.所有節(jié)點可以獲知自己的坐標位置.2簇頭節(jié)點劃分TCBCR與LEACH算法是不同之處在于TCBCRP算法將所有傳感器節(jié)點按地理位置劃分為多個簇,簇的劃分由能量充足的匯聚節(jié)點來完成,并且簇一旦形成,分簇在整個穩(wěn)定數(shù)據(jù)通信階段不再變化,當(dāng)簇頭節(jié)點出現(xiàn)故障或者能量小于某個閾值時,采用分布式方式在簇范圍內(nèi)重新選舉簇頭,而不是在整個網(wǎng)絡(luò)中實行新一輪的聚簇.如圖1(b)所示.這樣,就將監(jiān)測區(qū)域內(nèi)所有節(jié)點劃分為許多簇,并且確定了每個簇的簇頭節(jié)點和管理節(jié)點,劃分后的結(jié)果如圖1(c)所示.3rcbcrp協(xié)議3.1節(jié)點時間節(jié)點遷移概率簇的更替存在的問題有網(wǎng)絡(luò)中每個簇的簇頭是否有權(quán)利發(fā)起更換簇頭的請求;每個簇的簇頭在什么樣的情況之下才能發(fā)起更換簇頭的請求;簇頭的更換是集中進行還是分布進行等.如在簇頭與匯聚節(jié)點之間通信采用多跳方式(即通過簇頭組成的骨干網(wǎng)實現(xiàn)的多跳路由)更有利于節(jié)約能量,但是這種做法也帶來了一個能量消耗不均衡的問題:在這種所有傳感器節(jié)點的數(shù)據(jù)都發(fā)送到匯聚節(jié)點的“多對1”數(shù)據(jù)傳輸模式中,靠近匯聚節(jié)點的簇頭由于需要轉(zhuǎn)發(fā)大量來自其他簇的數(shù)據(jù)而負擔(dān)過重,在該節(jié)點擔(dān)當(dāng)簇頭的一輪中,會因為更換簇頭的時間未到,或者是沒有單獨更換簇頭的權(quán)利(即分布式簇頭更替,每個簇的簇頭更替是根據(jù)自身情況進行),而過早耗盡自身能量而失效.本文基于Markov流量預(yù)測模型應(yīng)用到了主簇頭節(jié)點的更換過程中,提出了一種基于Markov流量預(yù)測機制的主簇頭節(jié)點更換策略.1.在每個節(jié)點中用一個隨機變量序列X0,X1,X2,…來表示節(jié)點在這段時間的狀態(tài).既然每個節(jié)點都有一個隨機變量序列,那么在同一時間,不同節(jié)點可以處在不同的模式下.在可能的操作模式集合中,如果Xn=i,傳感器節(jié)點在時域n處在操作模式i下,一個時域就是一小段時間,假定所有的狀態(tài)遷移發(fā)生在任何時域的開始階段,每次節(jié)點在狀態(tài)i時有一些固定的概率,如果下一個狀態(tài)是j,則用Pij來表示.這個概率可用下式來表示:Ρij=Ρ{Xm+1=j|Xm=i}.(1)Pij=P{Xm+1=j|Xm=i}.(1)Pij表示一個節(jié)點在操作狀態(tài)i時下一個狀態(tài)進入到狀態(tài)j的概率,定義二階的遷移概率P(2)ij(2)ij,表示一個節(jié)點當(dāng)前在狀態(tài)i,經(jīng)歷兩個狀態(tài)遷移后到狀態(tài)j.即Ρ(2)ij=Ρ{Xm+2=j|Xm=i}.(2)P(2)ij=P{Xm+2=j|Xm=i}.(2)P(2)ij(2)ij可由Pij經(jīng)過式(3)計算出來:Ρ(2)ij=Μ∑k=1ΡikΡkj.(3)P(2)ij=∑k=1MPikPkj.(3)n階的遷移概率表示為P(n)ij(n)ij,Chapman-Kolmogorov方程式定義如下:Ρ(n)ij=Μ∑k=1Ρ(r)ikΡ(n-r)kj.(4)P(n)ij=∑k=1MP(r)ikP(n?r)kj.(4)2.對于任意0<r<n的值,另一個表示Markov鏈概率的方法是用一個M×M矩陣P來表示,它被叫作遷移概率矩陣,在這個矩陣中,第i行第j列的元素Pij表示概率.Ρ=[Ρ11Ρ12?Ρ1ΜΡ21Ρ22?Ρ2Μ???ΡΜ1ΡΜ2?ΡΜΜ].(5)P=??????P11P21?PM1P12P22?PM2???P1MP2M?PMM??????.(5)P(2)ij(2)ij的值是矩陣P和它自身的乘積矩陣中第i行第j列的元素.用P2表示P×P,意味著P(2)ij(2)ij是矩陣P2的第i行第j列的元素.同樣地,P(n)ij(n)ij是矩陣P的n次方的第i行第j列的元素.既然Pm+n=Pm×Pn,那么這意味著Ρ(m+n)ij=Μ∑k=1Ρ(m)ikΡ(n)kj.(6)P(m+n)ij=∑k=1MP(m)ikP(n)kj.(6)3.在模型中,遷移概率矩陣代表傳感器節(jié)點的行為.根據(jù)遷移概率矩陣和每個節(jié)點的初態(tài)X0,我們就可以建立整個無線傳感器網(wǎng)絡(luò)能量消耗序列.一個節(jié)點在T個時域后到達狀態(tài)s共經(jīng)歷多少個時域,假定現(xiàn)在節(jié)點在狀態(tài)i,即X0=i.由于P(t)is(t)is代表一個節(jié)點當(dāng)前處在狀態(tài)i,經(jīng)歷t個狀態(tài)遷移到達狀態(tài)s,那么,對任意的狀態(tài)s,一個節(jié)點停留在狀態(tài)s的時域數(shù)可用式(7)計算:S=Τ∑t=1Ρ(t)is.(7)S=∑t=1TP(t)is.(7)假設(shè)Bs是一個節(jié)點在狀態(tài)s停留一個時域傳輸?shù)臄?shù)據(jù)量,而節(jié)點經(jīng)過T個時域到達狀態(tài)s的期望時域數(shù)可由計算出來,即如果節(jié)點當(dāng)前處在狀態(tài)i,那么經(jīng)過T個時域,傳輸?shù)臄?shù)據(jù)總量BT是:BΤ=Μ∑s=1(Τ∑t=1Ρ(t)is)×Bs.(8)BT=∑s=1M(∑t=1TP(t)is)×Bs.(8)每個節(jié)點在時間T的數(shù)據(jù)由Τ∑t=1Ρ(t)is∑t=1TP(t)is計算,總的節(jié)點數(shù)由式(9)來計算:Btotal=Ck-n∑Ck-1Μ∑s=1(Τ∑t=1Ρ(t)is)×Bs,(9)Btotal=∑Ck?1Ck?n∑s=1M(∑t=1TP(t)is)×Bs,(9)其中Ck-i表示它是屬于簇Ck的第i個傳感器節(jié)點,Bs表示一個節(jié)點在狀態(tài)s停留一個時域傳輸?shù)臄?shù)據(jù)量.Pis表示從狀態(tài)i遷移到狀態(tài)s的概率.3.2主簇頭節(jié)點路由在某一普通節(jié)點完成數(shù)據(jù)監(jiān)測任務(wù)后,將會傳送監(jiān)測數(shù)據(jù)至主簇頭節(jié)點,然后主簇頭節(jié)點收集簇內(nèi)監(jiān)測節(jié)點采集數(shù)據(jù)后,進行數(shù)據(jù)融合,再將融合數(shù)據(jù)發(fā)送到匯聚節(jié)點.普通節(jié)點為了能夠?qū)?shù)據(jù)發(fā)送到主簇頭節(jié)點,將需要維護自己鄰居節(jié)點的簡單的路由信息表以及主簇頭節(jié)點和從簇頭節(jié)點的相關(guān)信息.當(dāng)自身的能量消耗超過預(yù)先設(shè)定的層次閾值ΔE時,該節(jié)點會將其新的能量層次值進行廣播(NOP消息),其鄰節(jié)點收到NOP消息后,便更新自己路由信息表中的數(shù)據(jù).在網(wǎng)絡(luò)運行的穩(wěn)定階段也即數(shù)據(jù)傳輸階段,主簇頭節(jié)點負責(zé)收集簇內(nèi)普通節(jié)點采集的數(shù)據(jù),然后對數(shù)據(jù)進行融合計算,然后通過多跳路由方式將融合數(shù)據(jù)通過鄰居主簇頭節(jié)點轉(zhuǎn)發(fā)至匯聚節(jié)點.具體過程描述如下:假設(shè)需要傳輸數(shù)據(jù)的主簇頭節(jié)點為(0,2,0,0),記為MCHi,距離匯聚節(jié)點的距離記為Di;記主簇頭節(jié)點MCHi相鄰m個主簇頭節(jié)點集合為Sn={MCHj,…,MCHm},主簇頭節(jié)點MCHi,MCHj,…,MCHm和匯聚節(jié)點之間的距離分別為Di,Dj,…,Dk.具體路由過程可描述如下:第1步.設(shè)存在主簇頭節(jié)點集合Sv={MCHv|MCHv∈SN&Dv<Di},如果集合Sv為空,則主簇頭節(jié)點直接傳送融合數(shù)據(jù)到匯聚節(jié)點,否則轉(zhuǎn)到下一步);第2步.在集合Sv中選擇能量水平值最大的主簇頭節(jié)點,如果能量水平值最大的節(jié)點是唯一的,則將該節(jié)點作為下一跳路由節(jié)點,否則從多個能量相等的主簇頭節(jié)點中挑選Dv最小的主簇頭節(jié)點作為下一跳;第3步.將該主簇頭節(jié)點作為路由起始節(jié)點,重復(fù)上述操作.這樣,在每個采集信息的普通節(jié)點和匯聚節(jié)點之間就形成了一條穩(wěn)定的路徑,如圖2所示:4以匯聚節(jié)點為基點的仿真為了評價本文提出算法的性能,本文在NS2仿真軟件中對算法進行仿真驗證.仿真環(huán)境具體配置如下:在500m×500m的正方形區(qū)域內(nèi),假設(shè)匯聚節(jié)點的坐標為(0,0),即坐標原點.以匯聚節(jié)點為原點建立坐標系,則200個傳感器節(jié)點均勻地分布在匯聚節(jié)點周圍.并且所有的傳感器節(jié)點以固定的頻率采集數(shù)據(jù),即節(jié)點以固定的頻率發(fā)送采集數(shù)據(jù),且數(shù)據(jù)包的大小是固定的,均為2000b,所有節(jié)點的初始能量值相等,均為0.25J,每層簇頭個數(shù)actual_ΝCΗ(i)=α(ri+ri-1)ri-ri-1?4<α<3π,仿真中α取2π,εamp=0.0013pJ(b·m2)-1,Eelec=50nJ·b-1,β=6.4.1節(jié)點個數(shù)仿真在傳感器網(wǎng)絡(luò)中,傳感器節(jié)點一般采用電池供電且不可更換,因此,降低能量消耗,延長網(wǎng)絡(luò)生命周期是設(shè)計網(wǎng)絡(luò)時要考慮的重要因素之一,網(wǎng)絡(luò)的存活節(jié)點數(shù)表明了隨著時間的推移仍然存活的節(jié)點的總數(shù),是體現(xiàn)路由協(xié)議是否屬于能源有效性協(xié)議的一個重要指標.圖3表示隨時間推移網(wǎng)絡(luò)中處于存活狀態(tài)的節(jié)點個數(shù).根據(jù)仿真結(jié)果,LEACH算法在240s時出現(xiàn)第1個死亡節(jié)點,LEACH-F算法在200s時出現(xiàn)第1個死亡節(jié)點;本文提出的UCA-M算法的第1個死亡節(jié)點推遲在430s時出現(xiàn),因為UCA-M算法利用非均衡簇結(jié)構(gòu)消除了多條路由算法中的“熱區(qū)”問題,網(wǎng)絡(luò)中簇頭節(jié)點能量消耗相對平衡,此外,算法還引入了主、從簇頭的概念,使網(wǎng)絡(luò)中簇頭的更換可以分布式的進行,從而整個網(wǎng)絡(luò)的性能得到了良好的改善.從圖3中可以看出,在430s～920s之間,UCA-M算法節(jié)點死亡的速度明顯比前2個算法要快,這是因為在UCA-M算法前期,盡量是網(wǎng)絡(luò)能量均衡消耗;而到了網(wǎng)絡(luò)運行的后期階段,由于所有節(jié)點的剩余能量水平都很低,因此節(jié)點也會在這一階段相繼死亡,網(wǎng)絡(luò)質(zhì)量快速下降.4.2評估uca-m和letch-m算法的負載在分簇的傳感器網(wǎng)絡(luò)中,簇頭扮演著極其重要的角色,簇頭能量消耗的快慢直接影響著整個網(wǎng)絡(luò)的性能好壞.本文主要以網(wǎng)絡(luò)中簇頭節(jié)點的負載均衡度來衡量整個網(wǎng)絡(luò)的負載.具體計算公式如下LBF=11+1mm∑i=1(ki-ˉ?)2,其中,ki表示第i個簇頭的負載,ˉ?表示平均負載.從圖4與圖5中我們可以很明顯的看出,UCA-M算法的LBF比LEACH算法和LEACH-C算法高,說明了UCA-M算法中簇頭節(jié)點的的負載比較均衡.這是因為在UCA-M算法中,距離匯聚節(jié)點近的簇頭節(jié)點所管理的成員節(jié)點要少于距離匯聚節(jié)點遠的簇頭節(jié)點,這就可以讓距離匯聚節(jié)點近的那些簇頭節(jié)點節(jié)省一部分能量用于轉(zhuǎn)發(fā)來自外層的監(jiān)測數(shù)據(jù),從而減少了由于瓶頸因素而造成的簇頭節(jié)點負擔(dān)過重而提前進入死亡狀態(tài).LEACH-C算法的LBF則介于UCA-M算法和LEACH算法之間,其簇頭的選擇僅考慮了節(jié)點的位置和能量,沒有考慮簇的規(guī)模問題.4.3接收數(shù)據(jù)的速度從圖4與圖5中可以看出,UCA-M算法中匯聚節(jié)點在整個網(wǎng)絡(luò)生命周期內(nèi)接收到的數(shù)據(jù)包總數(shù)是最多的.此外,當(dāng)網(wǎng)絡(luò)中節(jié)點未進入死亡周期時,3種算法匯聚節(jié)點接收到的數(shù)據(jù)包總量都隨時間線性增長,并且LEACH算法線性增長的速度大于LEACH-F和UCA-M算法,這是因為UCA-M算法采用的是多跳路由策略,而LEACH和LEACH-F算法是簇頭直接給匯聚節(jié)點發(fā)送數(shù)據(jù),在UCA-M算法中,由于數(shù)據(jù)需要經(jīng)過多