分簇技術(shù)在無線傳感器網(wǎng)絡(luò)中的應(yīng)用

分簇技術(shù)在無線傳感器網(wǎng)絡(luò)中的應(yīng)用

0節(jié)點防波劑分簇算法由于無線傳感器網(wǎng)絡(luò)存在著嚴(yán)重的能量限制，我們主要目標(biāo)是盡量減少節(jié)點的能量消耗，延長網(wǎng)絡(luò)的生存時間。分簇機(jī)制是將網(wǎng)絡(luò)劃分成可以相互通信的,并覆蓋網(wǎng)絡(luò)中所有節(jié)點的多個簇,周期性地為每個簇選擇簇頭節(jié)點,這樣可以均衡網(wǎng)絡(luò)中的節(jié)點能量消耗。分簇算法是一個重要的研究方面。一個好的分簇算法能夠形成優(yōu)良的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu),提高路由協(xié)議及MAC協(xié)議的效率,為數(shù)據(jù)融合、時間同步和目標(biāo)定位等提供基礎(chǔ)。研究表明,對于大規(guī)模的無線傳感器網(wǎng)絡(luò),層次型分簇路由算法比平面路由算法具有更好的適應(yīng)性和節(jié)能性。但是這就不可避免地導(dǎo)致“熱區(qū)”問題,即鄰近sink節(jié)點的簇頭由于轉(zhuǎn)發(fā)大量的數(shù)據(jù),使其能量消耗過快,造成網(wǎng)絡(luò)分割現(xiàn)象,降低網(wǎng)絡(luò)存活時間。在網(wǎng)絡(luò)中,大部分包碰撞、網(wǎng)絡(luò)擁塞、包丟失都發(fā)生在距離基站節(jié)點幾跳的范圍之內(nèi),僅僅依靠分布式擁塞控制、層次式網(wǎng)絡(luò)設(shè)計、數(shù)據(jù)融合等并不能徹底改善基站附近節(jié)點的瓶頸環(huán)境。所以對sink節(jié)點附近的節(jié)點進(jìn)行負(fù)載平衡,不但可以對包碰撞、網(wǎng)絡(luò)擁塞、包丟失的發(fā)生有所緩解,還可以平衡節(jié)點的能量消耗,延長傳感器網(wǎng)絡(luò)的生命期。近年來,研究人員提出了多種傳感器網(wǎng)絡(luò)的分簇算法來緩解“熱區(qū)”問題,其中文獻(xiàn)提出了一種基于非均勻分簇(Energy-EfficientUnevenClustering,EEUC)算法,靠近sink節(jié)點的簇的規(guī)模小于遠(yuǎn)離匯聚點的簇,因此靠近sink節(jié)點的簇頭可以為簇間的數(shù)據(jù)轉(zhuǎn)發(fā)預(yù)留能量,這在一定程度上平衡了簇頭的能量消耗。但由于靠近sink節(jié)點的簇的成員數(shù)目較小,從而增加了簇的數(shù)量,不利于簇頭進(jìn)行數(shù)據(jù)融合,會增加數(shù)據(jù)的流量。在文獻(xiàn)中提出了把剩余能量最大的兩個簇員作為新的簇頭和新的候選簇頭算法,即雙簇頭算法,這種算法簇頭耗能較快,因為算法結(jié)束時,簇頭和候選簇頭都要向本簇所有成員發(fā)出通告消息,能耗兩倍于單簇頭。但這種算法達(dá)到了負(fù)載平衡的目的。有研究證明雙簇頭模型比單簇頭模型更能延長網(wǎng)絡(luò)的生存期,有更好的穩(wěn)定性和安全性。由于網(wǎng)絡(luò)邊緣區(qū)域的簇頭節(jié)點不轉(zhuǎn)發(fā)或只轉(zhuǎn)發(fā)少量的數(shù)據(jù),“熱區(qū)”內(nèi)的簇頭需要新一輪的選舉時,“熱區(qū)”外的簇頭很可能還沒有達(dá)到閾值。所以在“熱區(qū)”內(nèi)使用雙簇頭算法不但可以提高網(wǎng)絡(luò)的穩(wěn)定性和安全性,還能更好地平衡節(jié)點的能耗。為了方便地把“熱區(qū)”定量的劃分出來,在文中使用GAF(geographicaladaptivefidelity)算法將傳感器網(wǎng)絡(luò)劃分成若干個簇。GAF算法是以節(jié)點地理位置為依據(jù)的分簇算法。該算法把監(jiān)測區(qū)域劃分成虛擬單元格,將節(jié)點按照位置信息劃入相應(yīng)的單元格;每個單元格為一個簇,每個簇中只有簇頭節(jié)點保持活動,其他節(jié)點進(jìn)入睡眠狀態(tài)。基于以上的考慮,提出了一種基于GAF的無線傳感器網(wǎng)絡(luò)分簇算法——簇頭非均勻分布(ClusterHeadUnevenDistributing,CHUD)算法,此算法將在“熱區(qū)”內(nèi)的簇執(zhí)行雙簇頭算法,來實現(xiàn)負(fù)載平衡。這樣“熱區(qū)”內(nèi)的簇就不必進(jìn)行頻繁的簇頭輪換和簇重組,以延長網(wǎng)絡(luò)的生存時間;在“熱區(qū)”以外的簇執(zhí)行單簇頭算法,簇頭工作時,其它節(jié)點處于休眠狀態(tài),以節(jié)約能耗。1傳感器網(wǎng)絡(luò)模型首先,需要利用GAF算法將整個無線傳感器網(wǎng)絡(luò)劃分成若干個正方形虛擬單元格。各節(jié)點再根據(jù)以下定理判斷自己是否在“熱區(qū)”內(nèi)。定理:假定sink節(jié)點O的坐標(biāo)為(0,0),“熱區(qū)”為H(m,n),若任意傳感節(jié)點p(x,y)是相對sink節(jié)點O的坐標(biāo),sink節(jié)點與傳感節(jié)點有相同的通信半徑R,當(dāng)且僅當(dāng)下式同時成立,稱傳感節(jié)點p(x,y)在“熱區(qū)”內(nèi)。m≥?x/R5√m≥?x/R5,n≥?y/R5√n≥?y/R5;其中“/”為除法運算符,“「?”為向上取整運算符。證明:為了方便討論,作出以下假設(shè):(1)所有傳感器網(wǎng)絡(luò)中的節(jié)點隨機(jī)分布在以sink節(jié)點為原點的二維坐標(biāo)系上,節(jié)點都知道自己的地理位置,即自己的坐標(biāo),并且所有節(jié)點的各項性能參數(shù)相同。(2)網(wǎng)絡(luò)具有穩(wěn)定的拓?fù)浣Y(jié)構(gòu),即傳感器節(jié)點部署之后不再移動。(3)sink節(jié)點的能量是無限的,網(wǎng)絡(luò)中其它所有節(jié)點的能量是有限的。(4)節(jié)點有狀態(tài)切換功能,當(dāng)節(jié)點空閑時可以進(jìn)入休眠狀態(tài)以節(jié)省能量。假設(shè)網(wǎng)絡(luò)區(qū)域劃分的正方形虛擬單元格邊長為r(見圖1),為了保證相鄰兩個單元格中任意兩個節(jié)點能夠直接通信,需要滿足關(guān)系:r2+(2r)2=R2?r≤R5√r2+(2r)2=R2?r≤R5從而易證以上定理。將鄰近sink節(jié)點一跳范圍稱為“一跳熱區(qū)”。由于網(wǎng)絡(luò)中所有的數(shù)據(jù)都要經(jīng)過“一跳熱區(qū)”轉(zhuǎn)發(fā)給sink節(jié)點,所以該區(qū)域能量消耗速度最快,如果“一跳熱區(qū)”內(nèi)的傳感節(jié)點能量耗盡,網(wǎng)絡(luò)中的數(shù)據(jù)就無法發(fā)送給sink節(jié)點,那么網(wǎng)絡(luò)的生命期就此結(jié)束。因此在網(wǎng)絡(luò)初始運行時,m,n的值一般不會太大,當(dāng)鄰近“熱區(qū)”的節(jié)點能耗達(dá)到一定程度時,可以根據(jù)實際情況將m,n適當(dāng)增大,以延長網(wǎng)絡(luò)的生命期。2簇頭節(jié)點的選舉基于P.Santi等人提出的一種GAF改進(jìn)算法,在GAF算法的基礎(chǔ)上提出了一種完全簇頭選擇算法,該算法要求每個節(jié)點都知道自己的ID及屬于哪個單元格,并且同一單元格內(nèi)的節(jié)點保持時間同步。對此算法稍做改進(jìn),在算法運行的過程中,不但選出剩余能量最大的節(jié)點,同時選出剩余能量次大的節(jié)點,剩余能量最大的節(jié)點做為簇頭節(jié)點,然后判定簇是否在H(m,n)內(nèi),如果在,則將剩余能量次大的節(jié)點做為候選簇頭節(jié)點,所謂候選簇頭節(jié)點就是當(dāng)簇頭節(jié)點剩余能量達(dá)到閾值時,該節(jié)點被喚醒并接任簇頭節(jié)點的工作。在算法開始時,節(jié)點按照編號依次發(fā)送和接收通告消息M(P1,P2,Emax,Emax′),其中,Emax為簇內(nèi)節(jié)點中最大的剩余能量值,Emax′為剩余能量次大值,P1,P2為相應(yīng)的ID。假設(shè)其中一個簇內(nèi)節(jié)點集為N,任意一個節(jié)點的編號為Pn,能量為Ep,Tr為初始時刻,Ts為每個節(jié)點每次通告消息需要的時間,具體簇頭選舉過程如下:Step1初始化Tr時刻?P∈N,設(shè)置每個節(jié)點每次通告消息的時間為Ts。Step2在Tr+(P-1)×Ts時刻,?P∈N執(zhí)行以下步驟:①如果Pn=P,轉(zhuǎn)到②;否則轉(zhuǎn)到Step3;②接收通告消息M(P1,P2,Emax,Emax′);如果Ep>Emax,轉(zhuǎn)到③;如果Emax′<Ep<Emax,轉(zhuǎn)到④;③將M(P1,P2,Emax,Emax′)替換成M(Pn,P2,Ep,Emax′);④將M(P1,P2,Emax,Emax′)替換成M(P1,Pn,Emax,Ep);⑤如果Pn=n;轉(zhuǎn)到Step3;Step3如果M第一個數(shù)據(jù)域的坐標(biāo)(x,y)同時滿足:m≥?x/R5√m≥?x/R5,n≥?y/R5√n≥?y/R5,向全簇發(fā)送通告消息M,M第一個數(shù)據(jù)域為簇頭,第二個數(shù)據(jù)域為候選簇頭;否則第一個數(shù)據(jù)域為簇頭;如果Pn≠n,在Tr+P×Ts時刻發(fā)送M。在Tr+n×Ts時刻,在“熱區(qū)”H(m,n)內(nèi)的單元格中所有節(jié)點打開通信模塊,接收第n個節(jié)點發(fā)送的通告消息M,這樣,所有的節(jié)點均得知簇頭節(jié)點和候選簇頭節(jié)點的ID和剩余能量值,除簇頭節(jié)點外,其它節(jié)點再次關(guān)閉通信模塊進(jìn)入睡眠狀態(tài),當(dāng)簇頭節(jié)點不能繼續(xù)工作時,喚醒候選簇頭節(jié)點接替簇頭節(jié)點的工作。在“熱區(qū)”H(m,n)外簇頭節(jié)點選舉結(jié)束后,對候選簇頭節(jié)點不再進(jìn)行標(biāo)識,即除簇頭節(jié)點外,其它節(jié)點關(guān)閉通信模塊進(jìn)入睡眠狀態(tài),因為“一跳熱區(qū)”內(nèi)的簇頭能耗速度極快,在此區(qū)域內(nèi)需要開始下一輪簇頭選舉算法時,其它區(qū)域內(nèi)的簇頭還沒有達(dá)到閾值。3chud算法性能分析在仿真實驗中,400個無線傳感器網(wǎng)絡(luò)節(jié)點隨機(jī)分布在200*200的正方形區(qū)域內(nèi),基站的位置坐標(biāo)是O(0,0),在不影響結(jié)果的情況下,sink節(jié)點可以為網(wǎng)絡(luò)中任意位置的節(jié)點。節(jié)點的初始能量都為0.5J,節(jié)點每發(fā)送1bit數(shù)據(jù)耗能50nJ,節(jié)點每融合1bit數(shù)據(jù)耗能5nJ,數(shù)據(jù)包大小為4000bits。在仿真過程中,為了方便分析CHUD算法的能量效率,假設(shè)采用理想的MAC協(xié)議,無線鏈路中丟包率為零。由于簇頭的能耗占整個網(wǎng)絡(luò)能耗的主要部分,在實驗過程中,記錄每運行一次簇頭輪換算法,網(wǎng)絡(luò)中所有簇頭消耗的能量之和。隨機(jī)抽取10輪,結(jié)果如圖2所示。與經(jīng)典的LEACH協(xié)議相比,CHUD算法大大降低了簇頭的能耗;與EEUC算法相比,不但簇頭的能耗有所減少,而且每輪簇頭的能耗比較平穩(wěn),說明CHUD算法實現(xiàn)了一定程度的負(fù)載平衡。無線傳感器網(wǎng)絡(luò)的生命期與網(wǎng)絡(luò)中節(jié)點的生存?zhèn)€數(shù)息息相關(guān),在圖3中,看到隨著仿真時間的延長,CHUD算法網(wǎng)絡(luò)中節(jié)點的生存?zhèn)€數(shù)遠(yuǎn)遠(yuǎn)大于LEACH算法和EEUC算法,但是在圖2中CHUD算法簇頭的能耗僅略低于EEUC算法,原因在于任一種簇頭輪換算法每運行一次,都要消耗網(wǎng)絡(luò)中大量的能量,而CHUD算法運行簇頭輪換算法的頻率低于其它兩種算法,從而節(jié)約了大量的能量。在CHUD算法中,任一時刻網(wǎng)絡(luò)中工作的節(jié)點都是簇頭節(jié)點,其它節(jié)點處于休眠狀態(tài),而且簇頭選舉的頻率很低,使整個網(wǎng)絡(luò)的能耗大大降低,從而延長網(wǎng)絡(luò)的生命期。本算法中每一輪選舉中簇頭能量消耗平穩(wěn),也證明了該算法的是穩(wěn)定的,提高了網(wǎng)絡(luò)的穩(wěn)定性。4打造無線傳感器網(wǎng)絡(luò)在大規(guī)模無線傳感器網(wǎng)絡(luò)中,利用分布式擁塞控制、層次式網(wǎng)絡(luò)設(shè)計、數(shù)據(jù)融合等技術(shù),雖