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

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

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