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

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

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