無線傳感器網(wǎng)絡(luò)中競爭能量輔助的節(jié)能分布式分簇算法

無線傳感器網(wǎng)絡(luò)中競爭能量輔助的節(jié)能分布式分簇算法

“集群分離技術(shù)”將節(jié)點分為集群或集群。每個集群有一個集群頭和許多集群節(jié)點。集群將網(wǎng)絡(luò)劃分為兩層結(jié)構(gòu)。集群節(jié)點形成頂層，成員節(jié)點形成底層。集群節(jié)點將數(shù)據(jù)發(fā)送給集群節(jié)點，并將數(shù)據(jù)整合到其他集群節(jié)點。集群技術(shù)是一種優(yōu)化能耗的拓撲數(shù)據(jù)結(jié)構(gòu)，它可以減少冗余數(shù)據(jù)的存儲，延長網(wǎng)絡(luò)的使用壽命，有效地集成網(wǎng)內(nèi)數(shù)據(jù)，減少數(shù)據(jù)報告的延遲，提高網(wǎng)絡(luò)的可擴展性。由于集群節(jié)點總是遠程傳輸數(shù)據(jù)，因此需要更多的能量。因此，網(wǎng)絡(luò)定期重新排列，選擇能量豐富的節(jié)點來執(zhí)行集群節(jié)點，并將負載均勻地分布到所有節(jié)點。集群路徑是傳感器網(wǎng)絡(luò)的一個熱門研究領(lǐng)域。其研究重點是集群分割算法。一般來說，集群分割算法可以控制每個節(jié)點的常數(shù)級消息的通信能力，這是分布式算法比集中分發(fā)算法的主要優(yōu)點。分布分發(fā)算法通常需要當(dāng)?shù)赜嬎慵悍职l(fā)算法，以控制集群數(shù)據(jù)的占用，這是分布式算法比集中算法的主要優(yōu)勢。雖然分布分發(fā)分割算法通常需要在本地計算簇頭競爭，但數(shù)據(jù)計算的能力遠低于數(shù)據(jù)結(jié)構(gòu)。因此，對于傳感器網(wǎng)絡(luò)，數(shù)據(jù)處理的能力往往可以忽略不計。此外，集群技術(shù)對網(wǎng)絡(luò)的吞吐量沒有負面的影響。正如heed協(xié)議驗證所示，在高通信負載下，由于降低信噪比競爭，網(wǎng)絡(luò)的吞吐量顯著增加。1網(wǎng)絡(luò)模型和問題描述1.1聚合節(jié)點的確定本文不妨假設(shè)n個傳感器節(jié)點按均勻分布隨機高密度部署在一個監(jiān)測區(qū)域A內(nèi),具有如下性質(zhì):1)傳感器網(wǎng)絡(luò)為高密度靜態(tài)網(wǎng)絡(luò),節(jié)點部署后可擴充.所有傳感器節(jié)點都被事先編排唯一的ID號,編號不妨為1,2,…,n,唯一的匯聚節(jié)點Sink編號為*,Sink節(jié)點位置任意.2)節(jié)點的能量可異構(gòu),但不能補充,即不要求所有節(jié)點的初始能量E具有相同值.3)所有節(jié)點不能獲知其位置信息.4)通常各節(jié)點通信半徑為rC,但各節(jié)點無線發(fā)射功率可調(diào).例如,BerkeleyMotes節(jié)點是一種典型的實例,它經(jīng)由標準的ioctl()系統(tǒng)調(diào)用直接設(shè)置發(fā)射功率級別.5)網(wǎng)絡(luò)中節(jié)點的時間是同步的.1.2eadeeg協(xié)議的分簇算法文獻對國外典型的無線傳感器網(wǎng)絡(luò)分簇算法進行了詳細的分析和比較.我國學(xué)者對無線傳感器網(wǎng)絡(luò)分簇技術(shù)也展開了大量研究,其中文獻提出的一種基于簇結(jié)構(gòu)的無線傳感器網(wǎng)絡(luò)數(shù)據(jù)收集協(xié)議EADEEG(anenergy-awaredatagatheringprotocolforwirelesssensornetworks)是近年來提出的頗有新意的算法.該協(xié)議采用了一種全新的簇頭競爭機制,能夠更好地解決節(jié)點能量異構(gòu)問題,提出了一種以鄰居節(jié)點的平均剩余能量與節(jié)點本身的剩余能量的比值作為節(jié)點競爭簇頭參數(shù)的簇頭產(chǎn)生算法,該方法使簇分配更加均勻且延長了網(wǎng)絡(luò)壽命.但通過仔細分析,EADEEG存在以下有待進一步改善的問題.問題1.EADEEG協(xié)議的分簇算法在某些情況下會在檢測區(qū)域產(chǎn)生一些縫隙區(qū)域,如圖1所示,縫隙區(qū)域中盡管存在節(jié)點5,該節(jié)點由于剩余能量小于鄰居6,7,8,9的平均能量而超時(指t越過T的值),不能競爭簇頭,但又收不到鄰近的任何簇頭1,2,3,4發(fā)出的簇頭申明消息,不能屬于任何簇而成為“孤點”,周圍的縫隙區(qū)域也變得不可監(jiān)測.問題2.在EADEEG協(xié)議的分簇算法中,為了保證由所有簇頭節(jié)點形成的子圖是連通的,文獻中將簇間通信半徑設(shè)置為2rC,以確保由簇頭形成的子圖的連通性.但圖1顯示,有簇頭節(jié)點1并不能與簇頭2,3,4中的任何一個簇頭連接,因為它們之間的距離都大于2rC.可見這種假設(shè)并不能保證分布式分簇算法產(chǎn)生的簇頭集合的連通性.問題3.由EADEEG分簇算法產(chǎn)生的簇頭數(shù)量下界由于同樣的原因也必須重新估算.2bpec分布式分簇算法描述本文提出了一種以鄰居節(jié)點的平均剩余能量與節(jié)點本身的剩余能量比值為主要參數(shù)、以節(jié)點的“度”作為節(jié)點競爭簇頭的輔助參數(shù)的分布式分簇算法(AdistributedalgorithmoftheclusteringtechniqueBasedontheParametersusedforElectingCHs),簡稱為BPEC分布式分簇算法.BPEC分簇算法基本解決了EADEEG算法存在的問題.在描述BPEC分簇算法之前,本文定義傳感器節(jié)點的狀態(tài)呈現(xiàn)候選態(tài)、簇頭節(jié)點態(tài)和簇成員態(tài)3種,分別用“白球”、“黑球”和“灰球”表示.表1列出了為BPEC設(shè)計的所有報文格式及其描述:另外,假定傳感器網(wǎng)絡(luò)中各節(jié)點各自將節(jié)點的局部數(shù)據(jù)信息保存在數(shù)據(jù)結(jié)構(gòu)NLI中,其數(shù)據(jù)結(jié)構(gòu)形式說明如下:intID;/*全網(wǎng)唯一的整數(shù)值標識*/floatEr;*節(jié)點剩余能量值*intd;/*鄰居節(jié)點個數(shù),也稱為度*/charstate;/*黑球表示簇頭,灰球表示簇成員,初始均為白球*/}NODEDATA;intparent;/*指示器指示其所屬簇頭*}NLI;/將節(jié)點的鄰居相關(guān)信息保存在NT中.其數(shù)據(jù)結(jié)構(gòu)形式說明如下:intID;/*全網(wǎng)唯一的整數(shù)值標識*/charstate;/*簇頭或簇內(nèi)成員狀態(tài)*/NeighborhoodTableNT;對BPEC分布式分簇算法描述如下:首先,每輪分簇開始時,進入鄰居信息獲取時段(neighbordiscoveryphase),事先規(guī)定持續(xù)時間長度為TND;然后進入其核心階段,即簇頭確定時段(headdecisionphase),事先規(guī)定持續(xù)時間長度為THD;最后進入節(jié)點歸屬時段(nodeattachmentphase),用于非簇頭節(jié)點決定其歸屬于哪個簇的時段,事先規(guī)定持續(xù)時間長度為TNA.網(wǎng)絡(luò)中的每個節(jié)點先進行時間同步,再同時啟動算法完成下列步驟.第1步:節(jié)點以通信半徑rC廣播SensorMsg報文,該報文包含該節(jié)點的ID號、節(jié)點的剩余能量值Er.然后,節(jié)點接收所有鄰居節(jié)點廣播的SensorMsg報文內(nèi)容,計算并更新節(jié)點本地信息數(shù)據(jù)結(jié)構(gòu)NLI中的平均剩余能量Ea和節(jié)點的“度”d的值.不妨任取某一節(jié)點vi,vj為其鄰居,則先計算Ea值:,這里,用Er表示節(jié)點j的剩余能量.再對節(jié)點按下列式(1)計算該節(jié)點可能有資格發(fā)送簇頭申明消息HeadMsg的時刻t:情形1.當(dāng)節(jié)點滿足條件:Er>Ea時,有:情形2.當(dāng)節(jié)點滿足條件:Er≤Ea時,有:這里,式(2)中的E是節(jié)點的初始能量,ρ是一個均勻分布在[0.9,1]之間的一個隨機實數(shù),其作用是減小兩個節(jié)點可能取相同t值的概率.下面證明的定理給出了結(jié)論:.說明BPEC分簇算法用于網(wǎng)絡(luò)簇頭的競爭階段共用了THD時間,其中前半段時間(從0持續(xù)到THD2)確定大部分簇頭,而THD的后半段時間(從THD2持續(xù)到THD)則在第1批簇頭沒能覆蓋的區(qū)域節(jié)點中,按節(jié)點的剩余能量與該節(jié)點初始能量之比值為大者,選擇作為剩下的少量簇頭.第2步:TND超時后本輪進入簇頭競爭時段,持續(xù)THD時間(從0持續(xù)到THD).BPEC算法這樣來產(chǎn)生簇頭:節(jié)點如果在時刻t到達時,還沒有收到任何鄰居節(jié)點發(fā)出的HeadMsg報文,則該節(jié)點向鄰居節(jié)點廣播HeadMsg報文,申明自己是簇頭;否則該節(jié)點立刻放棄簇頭競爭,而成為非簇頭節(jié)點角色.節(jié)點一旦確定了自己的角色,就修改節(jié)點本地信息數(shù)據(jù)結(jié)構(gòu)NLI的State欄,如果是簇頭,則由白球“White”變?yōu)楹谇颉癇lack”;如果是非簇頭節(jié)點,則由白球“White”變?yōu)榛仪颉癎ray”.第3步:簇頭確定階段后,本輪進入節(jié)點歸屬時段,持續(xù)TNA時間.對非簇頭節(jié)點而言,可能已經(jīng)收到幾個來自不同簇頭節(jié)點的HeadMsg報文,該節(jié)點通過查找自己的鄰居表NT,向剩余能量最多的簇頭發(fā)送JoinMsg報文,申請加入該簇,其中state欄為“Gray”的節(jié)點還需進一步更新parent欄,使該指示器的取值指向所屬簇頭的ID.而對簇頭節(jié)點來說,接收來自其所有簇內(nèi)成員節(jié)點的JoinMsg報文,并且將不屬于本簇的節(jié)點在自己的鄰居表NT中刪除,同時更新節(jié)點的本地信息NLI的d值.至此,分簇過程完畢.BPEC分簇算法具有如下特點:1)BPEC分簇算法是一個完全分布式的并行算法,擴充性好,更適合于大規(guī)模的無線傳感器網(wǎng)絡(luò).2)BPEC分簇算法利用,在前THD/2時間內(nèi)并行產(chǎn)生了大部分簇頭,作為節(jié)點競爭簇頭的主要參數(shù)因子Ea/Er,保證了剩余能量“相對”比較突出的節(jié)點充當(dāng)簇頭,而不是簡單地選擇節(jié)點的剩余能量“絕對”最大者作為簇頭,這樣做的結(jié)果是若干“輪”后,各節(jié)點均衡地消耗能量,從而延長整個網(wǎng)絡(luò)的壽命.3)作為節(jié)點競爭簇頭的另一個參數(shù)因子1/(d+1),由于節(jié)點隨機均勻播撒在檢測區(qū)域,所以區(qū)域內(nèi)部每個節(jié)點的“度”d的值接近,該參數(shù)對t的影響不大,但是對于一些位于監(jiān)測邊界的節(jié)點,由于這些節(jié)點的度明顯趨小,勢必增大了t的值,從而避免了位于邊界的節(jié)點成為簇頭.4)對一些暫時未能覆蓋的“縫隙”區(qū)域,利用公式在后THD/2時間內(nèi)并行產(chǎn)生了剩余的簇頭.由于“縫隙”區(qū)域包含的節(jié)點較少,所以,作為節(jié)點競爭簇頭的參數(shù)因子Er/E,客觀上拒絕了低能量的節(jié)點成為簇頭.3bec分簇算法的原理WSNs網(wǎng)絡(luò)拓撲可利用無向連通圖G(V,E)來描述,其中V表示傳感器節(jié)點的集合,E表示兩個節(jié)點間的雙向鏈路集,鏈路距離為節(jié)點的通信半徑rc.定義1.如果一個集合V的子集合S可以連通集合V內(nèi)所有節(jié)點,即u∈V,v∈S,du,v≤rc,式中du,v表示節(jié)點u和節(jié)點v的距離,rc表示通信半徑,則稱子集合S“覆蓋”了集合V.定義2.無向連通圖G(V,E)中任一個節(jié)點v的鄰居節(jié)點集合為N(v),N(v)={udu,v≤rc,u∈V}.定義3.在無向連通圖G(V,E)中取一個節(jié)點集合S?V,如果u∈S,v∈S,有(u,v)E,則稱S是一個獨立集.定義4.在無向圖G(V,E)中存在一個獨立集S,如果添加任意一個節(jié)點u∈V-S到S中,都會使S不再是一個獨立集,則稱S是圖G(V,E)的最大獨立集(maximumindependentset).定義5.支配集(dominatingset)是指可以覆蓋無向圖全網(wǎng)節(jié)點的節(jié)點集合,它是V的子集.無向圖G(V,E)的支配集S有以下性質(zhì):v∈V,N(v)∩S≠,即網(wǎng)內(nèi)任意一個節(jié)點要么本身屬于支配集,要么該節(jié)點至少有一個鄰居節(jié)點屬于支配集.顯然,本文對無線傳感器網(wǎng)絡(luò)分簇的過程實際上就是對無向連通圖G(V,E)構(gòu)造支配集的過程,支配集中的節(jié)點就是本文要找的簇頭節(jié)點,如果支配集中的節(jié)點是連通的,則構(gòu)造的支配集就是連通支配集.下面證明上述BPEC算法產(chǎn)生的簇頭節(jié)點集合構(gòu)成了支配集.定理1.按式(1)(2)計算節(jié)點發(fā)送簇頭申明消息的時刻,滿足不等式:.證明.已知節(jié)點的初始能量E>0,節(jié)點的剩余能量Er≥0,節(jié)點鄰居的平均剩余能量Ea≥0,節(jié)點的“度”d是大于等于1的正整數(shù).當(dāng)節(jié)點滿足條件Er>Ea時,有,這時,Er>Ea,有,所以,當(dāng)節(jié)點滿足條件Er≤Ea時,有并且,,所以,不等式成立.類似于文獻引理1的證明方法可以得到結(jié)論,由BPEC分簇算法產(chǎn)生的任意一個簇內(nèi)有且只有一個簇頭.定理2.由BPEC分簇算法產(chǎn)生的簇頭節(jié)點集合C是無線傳感器網(wǎng)絡(luò)G(V,E)的最大獨立集.證明.首先證明C是獨立集.反證法:假設(shè)C不是獨立集,即在C中存在兩個簇頭節(jié)點u和v,滿足(u,v)∈E,亦滿足du,v≤rc,但由BPEC算法可知,必有u或v之一屬于簇成員節(jié)點,與假設(shè)矛盾.故由簇頭組成的集合C必為獨立集.因為在無線傳感器網(wǎng)絡(luò)G(V,E)中的節(jié)點運行BPEC算法后,所有節(jié)點要么屬于簇頭集合C,要么屬于某簇的成員節(jié)點,所以V中的節(jié)點均為成員節(jié)點,取其中任一節(jié)點加入C中都會破壞C的獨立集性質(zhì),所以,C為最大獨立集.引理1.最大獨立集S同時也是無向圖G(V,E)的支配集,即對于任意一個節(jié)點v∈V,N(v)∩S≠,表示空集.證明.顯然,添加任意一個節(jié)點vS都會破壞S的獨立性質(zhì),則v必然有一個鄰節(jié)點在S中,因此,最大獨立集S是圖G(V,E)的支配集.定理3.由BPEC分簇算法產(chǎn)生的簇頭節(jié)點集合C是無線傳感器網(wǎng)絡(luò)G(V,E)的支配集.證明.由引理1直接得證.另外由圖論理論可以得到結(jié)論,對于圖G(V,E)內(nèi)任意一個節(jié)點v和圖G(V,E)的最大獨立集S,與v相鄰的,屬于S中的節(jié)點數(shù)小于6個,即N(v)∩S<6.就節(jié)點的通信半徑rc來說,上述定理2、定理3說明:1)由BPEC分簇算法產(chǎn)生的簇頭節(jié)點集合C覆蓋了網(wǎng)絡(luò)所有的節(jié)點;2)由BPEC分簇算法產(chǎn)生的集合C中的任意兩個簇頭節(jié)點在通信半徑rc內(nèi)都不連通;3)由BPEC分簇算法產(chǎn)生的每一個簇頭支配一個簇,所有非簇頭節(jié)點屬于并且僅屬于一個簇內(nèi);4)BPEC分簇算法的節(jié)點歸屬階段,每個非簇頭節(jié)點收到的HeadMsg報文不會超過6個,與節(jié)點總數(shù)無關(guān).定理4.如果‖A‖為網(wǎng)絡(luò)監(jiān)測區(qū)域的面積,由BPEC分簇算法產(chǎn)生的簇頭集合為C,則集合C的簇頭數(shù)量有明確的上下界,上界為,下界為,期望值為.證明.如圖2所示,簇頭A的6個鄰居簇頭節(jié)點(B,C,D,E,F,G)構(gòu)成一個正六邊形,任意兩個節(jié)點間的距離為rc+ε,其中,ε是一個很小的值.當(dāng)任意兩簇頭之間的距離不大于通信半徑rc時,簇頭A將被其6個鄰居節(jié)點所覆蓋.圖2(a)表示了簇頭數(shù)量最多的情況.簇頭A所代表的簇是一個邊長為的正六邊形,其簇面積為,故整個網(wǎng)絡(luò)中最密集的簇覆蓋集的簇頭數(shù)量為.如圖2(b)所示,簇頭A的6個鄰居簇頭節(jié)點構(gòu)成一個正六邊形.任意兩個簇頭節(jié)點間的最遠距離為,當(dāng)任意兩簇頭間距離大于時,將會有區(qū)域不能被撒布的節(jié)點通信覆蓋,這與已知矛盾.圖2(b)表示了相鄰簇間重疊面積最小的情況,簇頭A代表的簇是一個邊長為rc的正六邊形,將其各邊向外擴張rc/2距離,則得到一個邊長為,其面積等于的正六邊形,它包含了簇頭A代表的邊長為rc的正六邊形,故整個無線傳感器網(wǎng)絡(luò)中,最稀疏的簇覆蓋集合的簇頭數(shù)量為.因此,對于任意一個簇Ci,其實際簇面積滿足,考慮到節(jié)點的均勻分布,因此整個網(wǎng)絡(luò)中實際簇頭數(shù)量的期望值為.定理5.在BPEC分簇算法中,整個網(wǎng)絡(luò)的廣播消息量復(fù)雜度為O(n).證明.在BPEC分簇算法中,每一輪(round)開始階段所有節(jié)點都會發(fā)送一條SensorMsg控制報文,消息量為n;在每一輪的簇頭選擇階段,對于簇頭節(jié)點需要發(fā)送1條HeadMsg簇頭申明消息,在每一輪的節(jié)點歸屬時段,對于成員節(jié)點都需要發(fā)送1條JoinMsg消息用于加入簇,兩者相加,消息量也為n.則BPEC分簇算法整個廣播消息量為2×n,所以,整個網(wǎng)絡(luò)的廣播消息量復(fù)雜度為O(n).定理6.在BPEC分簇算法中,整個網(wǎng)絡(luò)的時間復(fù)雜度為O(1).證明.在BPEC分簇算法中,由于采用分布式并行算法,網(wǎng)絡(luò)的時間復(fù)雜度就是單個節(jié)點的時間復(fù)雜度,而BPEC分簇算法單個節(jié)點的時間復(fù)雜度為常數(shù),與網(wǎng)絡(luò)的規(guī)模n無關(guān),所以,整個網(wǎng)絡(luò)的時間復(fù)雜度為O(1).另外由圖論的基本性質(zhì)可得到引理2的證明.引理2.對無向連通圖G(V,E)的最大獨立集S而言,如果S內(nèi)的節(jié)點數(shù)不小于2,則S內(nèi)的任意一個節(jié)點v三跳之內(nèi)必存在至少一個最大獨立集節(jié)點,即N3(v)∩S≠.定理7.由BPEC分簇算法產(chǎn)生的簇頭節(jié)點集合C是無線傳感器網(wǎng)絡(luò)G(V,E)的一個最大獨立集,則C內(nèi)的任意一個簇頭節(jié)點v三跳之內(nèi)必存在至少一個最大獨立集節(jié)點,即N3(v)∩S≠.證明.由引理2得知,C內(nèi)的任意一個簇頭節(jié)點v三跳之內(nèi)必存在至少一個最大獨立集節(jié)點.因此,節(jié)點v三跳之內(nèi)必然存在一個最大獨立集節(jié)點u,其可能的連接形式如圖3所示:定理7的結(jié)論作為本文構(gòu)造無線傳感器網(wǎng)絡(luò)連通支配集的理論基礎(chǔ).因此,由BPEC分簇算法產(chǎn)生的簇頭集合是一個支配集,只要將無線射頻信號通信半徑rc調(diào)節(jié)到原來的3倍,不妨設(shè)新的通信半徑為Rc,這里Rc=3×rc就可保證簇頭集合為連通支配集合.這是將簇頭節(jié)點不借助其他輔助節(jié)點構(gòu)成匯集樹的基礎(chǔ).值得一提的是,Zhang等人首先對節(jié)點的覆蓋與連通之間的關(guān)系進行了分析,并證明了如果節(jié)點的通信半徑大于兩倍節(jié)點的感知半徑,則節(jié)點對整個凸區(qū)域的全覆蓋就保證了所有節(jié)點的連通性.這一結(jié)論并不能應(yīng)用到BPEC產(chǎn)生的簇頭集的連通性.因為盡管網(wǎng)絡(luò)所有的節(jié)點保證了對凸區(qū)域的全感應(yīng)覆蓋,但由BPEC分簇算法產(chǎn)生的簇頭集中的所有簇頭節(jié)點并不能保證對整個凸區(qū)域的全覆蓋.另外,本文討論的連通支配集問題是一個典型的點覆蓋問題,它要求連通支配集(簇頭集合)覆蓋所有的簇頭節(jié)點,而不是感知覆蓋整個區(qū)域.4實驗結(jié)果分析下面主要仿真分析BPEC和EADEEG分簇算法產(chǎn)生簇頭的實驗值和理論分析值的關(guān)系.假定n個傳感器節(jié)點隨機均勻分布于一個邊長為a的正方形監(jiān)測區(qū)域A內(nèi),每個節(jié)點的通信半徑定為rcm.根據(jù)定理4,BPEC分簇算法期望產(chǎn)生的簇頭數(shù)目為實驗時分為高密度(500個節(jié)點播撒在邊長為a=100m的正方形檢測區(qū)域)和低密度(100個節(jié)點播撒在邊長為a=100m的正方形檢測區(qū)域)兩個實驗場景.以下的實驗結(jié)果(如圖4所示)均為100次獨