摘要:針對(duì)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)穩(wěn)定的實(shí)際應(yīng)用,提出了一種混合簇頭選舉算法,包括以質(zhì)心(能量中心)為基礎(chǔ)的簇頭選舉方式和以剩余能量為基礎(chǔ)的簇頭選舉方式。通過(guò)降低系統(tǒng)內(nèi)簇頭與簇內(nèi)節(jié)點(diǎn)之間通信的總能量和平均傳輸時(shí)延來(lái)提高網(wǎng)絡(luò)的生命周期。仿真結(jié)果表明,與GAF算法相比,網(wǎng)絡(luò)的生命周期得到了較大幅度的提高,并且隨著單簇節(jié)點(diǎn)數(shù)的增加,網(wǎng)絡(luò)的生命周期也隨之增加。實(shí)驗(yàn)證明,該方法適用于組建大規(guī)模無(wú)線傳感器網(wǎng)絡(luò)。
關(guān)鍵詞:無(wú)線傳感器網(wǎng)絡(luò); 混合簇頭選舉算法; 地理位置; 質(zhì)心
中圖分類(lèi)號(hào):TP393文獻(xiàn)標(biāo)志碼:A
文章編號(hào):1001-3695(2008)04-1227-03
作為一種全新的信息獲取和處理技術(shù),無(wú)線傳感器網(wǎng)絡(luò)[1]已在軍事、環(huán)境科學(xué)、醫(yī)療健康、空間探索及其他商業(yè)領(lǐng)域得到廣泛應(yīng)用[2]。
無(wú)線傳感器網(wǎng)絡(luò)涉及的關(guān)鍵技術(shù)包括網(wǎng)絡(luò)拓?fù)淇刂啤⒕W(wǎng)絡(luò)協(xié)議、網(wǎng)絡(luò)安全、時(shí)間同步、定位技術(shù)、數(shù)據(jù)管理、無(wú)線通信技術(shù)等[2]。層次型的拓?fù)浣Y(jié)構(gòu)由于具有減少通信量、有利于分布式計(jì)算、可擴(kuò)展性強(qiáng)、能量利用效率高、數(shù)據(jù)融合簡(jiǎn)單、適合大規(guī)模部署網(wǎng)絡(luò)等特點(diǎn),成為當(dāng)前拓?fù)淇刂蒲芯康闹攸c(diǎn)。
層次型拓?fù)浣Y(jié)構(gòu)的分簇算法主要包括LEACH[3]及其改進(jìn)算法LEACH-C(LEACH-centralized)[4]和LEACH-F(LEACH-fixed)[4]、PEGASIS[5]、HEED[6] 、ACE[7]、GAF[8]及其改進(jìn)算法等。這些算法中除GAF(geographical adaptive fidelity)及其改進(jìn)算法外,通常是先選舉出簇頭,再通過(guò)簇頭組織簇,并且均未考慮節(jié)點(diǎn)的位置信息。但在很多應(yīng)用中,如工業(yè)監(jiān)測(cè),節(jié)點(diǎn)位置已經(jīng)布好,并且已知節(jié)點(diǎn)的監(jiān)測(cè)類(lèi)型。因此,分簇情況比較明顯,這就使得簇的形成先于簇頭的形成,與現(xiàn)有的算法存在較大的差別。GAF算法中先對(duì)監(jiān)測(cè)區(qū)域劃分虛擬單元格,在每個(gè)單元格內(nèi)節(jié)點(diǎn)使用競(jìng)爭(zhēng)的方式來(lái)競(jìng)爭(zhēng)簇頭,沒(méi)有充分考慮節(jié)點(diǎn)的剩余能量,并且節(jié)點(diǎn)處于偵聽(tīng)狀態(tài)時(shí)消耗能量較大,降低了網(wǎng)絡(luò)使用壽命。在隨后的GAF改進(jìn)算法中,優(yōu)化了簇頭選舉方式,但要求節(jié)點(diǎn)具有嚴(yán)格的時(shí)間同步。本文結(jié)合工業(yè)現(xiàn)場(chǎng)監(jiān)測(cè)特點(diǎn),以節(jié)點(diǎn)地理位置為研究基礎(chǔ),針對(duì)監(jiān)測(cè)區(qū)域內(nèi)節(jié)點(diǎn)的數(shù)量,提出了根據(jù)簇內(nèi)節(jié)點(diǎn)個(gè)數(shù)的不同,采用新的簇頭選舉算法,在充分考慮節(jié)點(diǎn)的能量消耗的情況下采用能量中心和剩余能量為基礎(chǔ)的動(dòng)態(tài)簇頭選舉算法,使得簇內(nèi)的每個(gè)節(jié)點(diǎn)的能耗均衡,從而提高網(wǎng)絡(luò)的生命周期。
1約束條件和相關(guān)模型
本文所描述的算法遵循以下約束條件:a)為了避免網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)頻繁改變,假定節(jié)點(diǎn)是微移動(dòng)或靜止不動(dòng);b)網(wǎng)絡(luò)節(jié)點(diǎn)組織成簇結(jié)構(gòu)的形式,簇頭執(zhí)行數(shù)據(jù)的融合功能,并負(fù)責(zé)將集中后的數(shù)據(jù)傳輸?shù)絽R聚節(jié)點(diǎn);c)每個(gè)傳感器節(jié)點(diǎn)在每一輪數(shù)據(jù)采集過(guò)程中所產(chǎn)生的數(shù)據(jù)量是相同的; d)簇內(nèi)成員不會(huì)轉(zhuǎn)發(fā)其他傳感器節(jié)點(diǎn)的數(shù)據(jù),簇內(nèi)節(jié)點(diǎn)之間不發(fā)生通信;e) 簇內(nèi)節(jié)點(diǎn)和簇頭節(jié)點(diǎn)的發(fā)射功率一定,并且簇內(nèi)節(jié)點(diǎn)與簇頭節(jié)點(diǎn)之間均在一跳通信范圍內(nèi);f) 節(jié)點(diǎn)具有較大的存儲(chǔ)容量。網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)模型如圖1所示。
能耗模型采用無(wú)線通信能耗模型[9],如圖2所示。在該模型中,發(fā)送節(jié)點(diǎn)的能量消耗包括無(wú)線發(fā)送裝置和放大器兩部分,接收節(jié)點(diǎn)的能量消耗來(lái)自于接收裝置的能量消耗。在圖2中,包括自由空間(d2功率損失)和多徑衰落(d4功率損失)兩種通道模型。實(shí)驗(yàn)中使用何種模型取決于發(fā)送節(jié)點(diǎn)與接收節(jié)點(diǎn)之間的距離。如果發(fā)送節(jié)點(diǎn)與接收節(jié)點(diǎn)之間的距離小于閾值d0,則使用自由空間模型,否則使用多徑衰落模型。
2算法描述
2.1算法核心思想和關(guān)鍵點(diǎn)說(shuō)明
考慮到節(jié)點(diǎn)通過(guò)發(fā)送數(shù)據(jù)包進(jìn)行信息交互來(lái)選舉簇頭的方式將消耗大量的能量。本文提出算法中對(duì)節(jié)點(diǎn)的剩余能量采用估計(jì)的方式。節(jié)點(diǎn)通過(guò)式(1)~(6)及質(zhì)心公式對(duì)每個(gè)節(jié)點(diǎn)的剩余能量進(jìn)行估計(jì)。這樣在每個(gè)節(jié)點(diǎn)通過(guò)計(jì)算就可大致獲得所在簇的質(zhì)心(能量中心)。考慮到計(jì)算節(jié)點(diǎn)剩余能量與真實(shí)情況會(huì)存在偏差,系統(tǒng)會(huì)在每個(gè)周期(簇內(nèi)所有成員均當(dāng)選過(guò)一次簇頭稱(chēng)為一個(gè)周期)之后,通過(guò)發(fā)送數(shù)據(jù)包的方式來(lái)修正每個(gè)節(jié)點(diǎn)由于計(jì)算所得的剩余能量的值。
1) 關(guān)鍵結(jié)構(gòu)說(shuō)明
本算法在簇頭選舉的過(guò)程中主要依靠節(jié)點(diǎn)的計(jì)算,保存在節(jié)點(diǎn)flash中的結(jié)構(gòu)信息的值并不能真實(shí)地反映節(jié)點(diǎn)的剩余能量。計(jì)算所得的節(jié)點(diǎn)的剩余能量可能會(huì)與實(shí)際情況存在一定的偏差,系統(tǒng)會(huì)在每個(gè)周期(簇內(nèi)成員均分別成為一次簇頭稱(chēng)為一個(gè)周期)后通過(guò)一次信息交互來(lái)更新簇內(nèi)節(jié)點(diǎn)的剩余能量。因此要求節(jié)點(diǎn)具有較大的存儲(chǔ)空間,簇內(nèi)的每個(gè)節(jié)點(diǎn)要保存簇內(nèi)成員的相關(guān)信息。簡(jiǎn)單地說(shuō),如果簇內(nèi)有n個(gè)節(jié)點(diǎn)就要保存n個(gè)這樣的結(jié)構(gòu),在每完成一輪計(jì)算后就會(huì)更新節(jié)點(diǎn)的相關(guān)信息。簇內(nèi)成員的相關(guān)信息存儲(chǔ)的結(jié)構(gòu)如下:
StructNode_Info
{
int[n]Node_Id;//節(jié)點(diǎn)的ID
float[n]Distance_Node_to_Cluster; //簇內(nèi)成員到簇頭的距離
float[n]Node_Compute_Energy;//節(jié)點(diǎn)通過(guò)計(jì)算得到的剩余能量
float[n]Node_Real_Energy//簇內(nèi)節(jié)點(diǎn)的真實(shí)剩余能量
float[n]Node_CoordinateX;//節(jié)點(diǎn)的x軸坐標(biāo)值
float[n]Node_CoordinateY;//節(jié)點(diǎn)的y軸坐標(biāo)值
};
其中:n表示簇內(nèi)節(jié)點(diǎn)個(gè)數(shù)。
2) 簇的形成
首先由匯聚節(jié)點(diǎn)廣播一個(gè)開(kāi)始建立簇的消息。節(jié)點(diǎn)收到消息后采用洪泛或者廣播的形式反饋消息。節(jié)點(diǎn)消息中包括監(jiān)測(cè)區(qū)域、監(jiān)測(cè)量類(lèi)型、節(jié)點(diǎn)ID、剩余能量、坐標(biāo)值。由于每個(gè)節(jié)點(diǎn)的位置是固定的,可由人工事先進(jìn)行簇的劃分。
3) 簇頭選舉
針對(duì)簇內(nèi)節(jié)點(diǎn)的數(shù)量采用不同的簇頭選舉方式。如果簇內(nèi)節(jié)點(diǎn)數(shù)量超過(guò)一定的值,采用基于質(zhì)心的簇頭選舉方式。通過(guò)簇內(nèi)節(jié)點(diǎn)坐標(biāo)可以求出這個(gè)簇的質(zhì)心(能量中心)。如果質(zhì)心位置恰好有節(jié)點(diǎn),那么該節(jié)點(diǎn)即作為本輪的簇頭;如果質(zhì)心位置沒(méi)有節(jié)點(diǎn),那么求出每個(gè)節(jié)點(diǎn)到質(zhì)心的距離,將距離最近的節(jié)點(diǎn)作為本輪的簇頭。當(dāng)出現(xiàn)具有多個(gè)節(jié)點(diǎn)到質(zhì)心距離相等的情況,選擇節(jié)點(diǎn)ID號(hào)最大的作為本輪的簇頭。在下一輪的簇頭選舉中,將前面已經(jīng)當(dāng)過(guò)簇頭的節(jié)點(diǎn)排除掉,保證簇內(nèi)所有的節(jié)點(diǎn)依次成為簇頭。如果簇內(nèi)節(jié)點(diǎn)少于一定數(shù)量,則根據(jù)節(jié)點(diǎn)的剩余能量對(duì)該簇進(jìn)行簇頭選舉,每輪選擇剩余能量最多的節(jié)點(diǎn)成為簇頭;如果出現(xiàn)兩個(gè)節(jié)點(diǎn)的剩余能量完全相同,則選擇節(jié)點(diǎn)ID號(hào)較大的作為簇頭。下一輪選舉時(shí),排除前面已經(jīng)當(dāng)選過(guò)簇頭的節(jié)點(diǎn),直到該簇內(nèi)所有節(jié)點(diǎn)均當(dāng)選過(guò)一次后,依此進(jìn)行循環(huán)。
2.2算法實(shí)現(xiàn)關(guān)鍵步驟
1) 簇頭選舉
根據(jù)簇內(nèi)節(jié)點(diǎn)的不同數(shù)量,分別進(jìn)行如下處理:
a)簇內(nèi)節(jié)點(diǎn)數(shù)量超過(guò)n。根據(jù)質(zhì)心公式求得每個(gè)簇的質(zhì)心所在位置。依此比較簇內(nèi)每個(gè)節(jié)點(diǎn)與質(zhì)心的坐標(biāo)值,將距離質(zhì)心最近,并且前面未當(dāng)選過(guò)簇頭的節(jié)點(diǎn),作為本輪的簇頭。將當(dāng)選的簇頭類(lèi)型置為“C”,非簇頭節(jié)點(diǎn)用“N”表示。
質(zhì)心(能量中心)計(jì)算公式為:
=Ey/E=∑ni=1eixi/∑ni=1ei,
=Ex/E=∑ni=1eiyi/∑ni=1ei
其中:ei為節(jié)點(diǎn)的剩余能量;xi為節(jié)點(diǎn)橫坐標(biāo)值;yi為節(jié)點(diǎn)縱坐標(biāo)值。
b)簇內(nèi)節(jié)點(diǎn)數(shù)不超過(guò)n。這時(shí)簇內(nèi)節(jié)點(diǎn)的數(shù)量較少,根據(jù)簇內(nèi)節(jié)點(diǎn)的剩余能量,選擇剩余能量最多,并且在前面沒(méi)有被選舉為簇頭的節(jié)點(diǎn)作為本輪的簇頭。同樣,將當(dāng)選的簇頭類(lèi)型置為“C”,非簇頭節(jié)點(diǎn)用“N”表示。
2) 簇頭分配時(shí)隙
a)簇頭節(jié)點(diǎn)在簇內(nèi)廣播消息,消息內(nèi)容包括節(jié)點(diǎn)ID、剩余能量、電池電量、坐標(biāo)值,通知簇內(nèi)節(jié)點(diǎn)自己當(dāng)選簇頭,并將自己的類(lèi)型置為“C”(簇頭標(biāo)志)。簇內(nèi)非簇頭節(jié)點(diǎn)收到消息后會(huì)返回消息,也包括同樣的內(nèi)容,并將類(lèi)型置為“N”。
b)簇頭作為每輪的控制中心產(chǎn)生TDMA的規(guī)則,并將這個(gè)規(guī)則發(fā)布給簇內(nèi)的其他節(jié)點(diǎn)。這樣確保簇內(nèi)節(jié)點(diǎn)發(fā)送數(shù)據(jù)信息時(shí)不會(huì)產(chǎn)生沖突。簇內(nèi)非簇頭節(jié)點(diǎn)在接收到該規(guī)則后進(jìn)入休眠狀態(tài),只有在規(guī)定的時(shí)隙內(nèi)醒來(lái)后發(fā)送數(shù)據(jù),減少了單個(gè)節(jié)點(diǎn)的能量消耗。
當(dāng)所有的節(jié)點(diǎn)均當(dāng)選過(guò)簇頭之后,將節(jié)點(diǎn)的類(lèi)型全部置為非簇頭,再依此循環(huán)執(zhí)行。該算法流程如圖3所示。
3仿真試驗(yàn)與分析
基于上文提到的混合簇頭選舉算法,下面將通過(guò)量化分析手段來(lái)描述網(wǎng)絡(luò)生命周期與初始能量之間的關(guān)系。算法結(jié)束的條件是網(wǎng)絡(luò)中出現(xiàn)第一個(gè)能量耗盡的節(jié)點(diǎn)。本文算法能耗包括簇內(nèi)節(jié)點(diǎn)和簇頭節(jié)點(diǎn)的能耗。簇內(nèi)節(jié)點(diǎn)的能耗主要是發(fā)送數(shù)據(jù)給簇頭的能耗。簇頭節(jié)點(diǎn)的能耗包括接收簇內(nèi)節(jié)點(diǎn)數(shù)據(jù)的能耗、融合數(shù)據(jù)的能耗和將融合后的數(shù)據(jù)包發(fā)給基站的能耗。在每個(gè)周期(簇內(nèi)節(jié)點(diǎn)均當(dāng)過(guò)一次簇頭稱(chēng)為一個(gè)周期)之后,節(jié)點(diǎn)修正結(jié)構(gòu)中的計(jì)算剩余能量所產(chǎn)生的能耗。仿真實(shí)驗(yàn)分兩步進(jìn)行,試驗(yàn)中使用的通用參數(shù)如表1所示。
第一步,首先比較本文中提出的兩種算法,確定出單簇內(nèi)節(jié)點(diǎn)個(gè)數(shù)的閾值。表1給出了實(shí)驗(yàn)中所使用的參數(shù)。單簇的節(jié)點(diǎn)數(shù)的閾值為n,節(jié)點(diǎn)在區(qū)域內(nèi)隨機(jī)分布。如果簇內(nèi)節(jié)點(diǎn)大于n,則采用基于質(zhì)心的簇頭選舉算法;如果不大于n,則采用基于節(jié)點(diǎn)剩余能量的簇頭選舉算法。考慮到本算法的簇是靜態(tài)穩(wěn)定的,單簇的網(wǎng)絡(luò)生命周期直接決定整個(gè)網(wǎng)絡(luò)的生命周期。因此在進(jìn)行仿真實(shí)驗(yàn)時(shí),只對(duì)本文提出的算法進(jìn)行單簇比較。單簇節(jié)點(diǎn)數(shù)目分別為5、8、10,比較結(jié)果如圖4所示。
根據(jù)圖4(a)可知,當(dāng)簇內(nèi)節(jié)點(diǎn)數(shù)為10時(shí),基于質(zhì)心的簇頭選舉算法的生命周期大于基于剩余能量的簇頭選舉算法的生命周期;由圖4(b)可以看出,當(dāng)簇內(nèi)節(jié)點(diǎn)數(shù)為8時(shí),基于質(zhì)心的簇頭選舉算法和基于剩余能量的簇頭選舉算法的生命周期相差不大;由圖4(c)可以看出,當(dāng)簇內(nèi)節(jié)點(diǎn)數(shù)為5時(shí), 基于剩余能量的簇頭選舉算法的生命周期大于基于質(zhì)心的簇頭選舉算法。由實(shí)驗(yàn)可知,簇內(nèi)節(jié)點(diǎn)數(shù)目的不同,選擇不同的簇頭選舉算法,能夠提高整個(gè)網(wǎng)絡(luò)的生命周期。
第二步,將本文提出的算法與GAF算法進(jìn)行比較,從而可以看出整個(gè)網(wǎng)絡(luò)生命周期的情況。實(shí)驗(yàn)中將整個(gè)網(wǎng)絡(luò)分為4個(gè)簇,每簇的節(jié)點(diǎn)個(gè)數(shù)分別為5、8、10、20。節(jié)點(diǎn)分布如圖5所示。根據(jù)第一步的實(shí)驗(yàn)結(jié)果,節(jié)點(diǎn)數(shù)為5和8時(shí),采用基于剩余能量的簇頭選舉算法,節(jié)點(diǎn)數(shù)為10和20時(shí),采用基于能量中心的簇頭選舉算法。比較結(jié)果如圖6所示。
圖6比較了混合簇頭選舉算法與GAF算法在單簇節(jié)點(diǎn)個(gè)數(shù)、節(jié)點(diǎn)初始能量發(fā)生變化時(shí),網(wǎng)絡(luò)生命周期之間的關(guān)系。從圖中可以看出,相對(duì)GAF算法,混合簇頭選舉算法的網(wǎng)絡(luò)生存周期會(huì)有較大幅度增加。在混合簇頭選舉算法中,簇頭選舉主要依靠節(jié)點(diǎn)自身計(jì)算,相比GAF及其改進(jìn)算法,節(jié)省了簇內(nèi)成員由于競(jìng)爭(zhēng)簇頭而需要發(fā)送的數(shù)據(jù)包所消耗的能量。Pottie等人提出在無(wú)線環(huán)境下,執(zhí)行3 000條指令相當(dāng)于無(wú)線模塊將1 bit信息發(fā)送到100 m的終端所消耗的能量[10]。理論上可知,混合簇頭選舉算法將較大幅度地提高網(wǎng)絡(luò)生命周期。
通過(guò)仿真實(shí)驗(yàn)可知,混合簇頭選舉算法隨著單簇節(jié)點(diǎn)數(shù)的增加網(wǎng)絡(luò)的生命周期也會(huì)相應(yīng)增加,其原因是相同時(shí)間內(nèi),簇內(nèi)節(jié)點(diǎn)數(shù)少的簇內(nèi)成員成為簇頭的次數(shù)多,簇頭會(huì)消耗較大的能量。本文提出的算法相對(duì)于GAF算法更適合于組建較大規(guī)模的傳感器網(wǎng)絡(luò)。實(shí)驗(yàn)中節(jié)點(diǎn)是隨機(jī)分布的,當(dāng)節(jié)點(diǎn)位置發(fā)生變化時(shí),網(wǎng)絡(luò)的生命周期波動(dòng)較小,具有很好的穩(wěn)定性。
4結(jié)束語(yǔ)
本文針對(duì)一些特定應(yīng)用,如工業(yè)現(xiàn)場(chǎng)監(jiān)測(cè),根據(jù)簇內(nèi)節(jié)點(diǎn)數(shù)量的不同,提出了混合簇頭選舉算法的策略,完善了以質(zhì)心為研究基礎(chǔ)的簇頭選舉算法。通過(guò)實(shí)驗(yàn)可以看出,該方法可以提高整個(gè)網(wǎng)絡(luò)的生命周期,并且隨著簇內(nèi)節(jié)點(diǎn)數(shù)的增加網(wǎng)絡(luò)的生命周期也相應(yīng)增加。因此,這種策略非常適合組建大規(guī)模的無(wú)線傳感器網(wǎng)絡(luò)監(jiān)測(cè)系統(tǒng),為建立無(wú)線傳感器網(wǎng)絡(luò)監(jiān)測(cè)系統(tǒng)提供一個(gè)全新的方案。
參考文獻(xiàn):
[1]ILDIZ I F, SU W, SANKARASUBRAMANIAM Y, et al. A survey on sensor networks[J]. IEEE Communications Magazine, 2002,40(8):102-114.
[2]FY, HUANG H N, LIN C. Wireless sensor networks [J].Journal of Software,2003,14(7):1282-1291.
[3]HEINZELMAN W, CHANDRAKASAN A, BALAKRISHNAN H. Energy-efficient communication protocol for wireless microsensor networks[C]//Proc ofthe 33rd Annual Hawaii Int’l Conf on System Sciences. Maui: IEEE Computer Society, 2000. 3005-3014.
[4]HEINZELMAN W. Application-specific protocol architectures for wireless networks [D]. Boston: Massachusetts Institute of Technology, 2000.
[5]LINDSEY S, RAGHAVENDRA C S. PEGASIS: power- efficient gathering in sensor information systems[C]//Proc ofIEEE Aerospace Conf. Montana: IEEE Aerospace and Electronic Systems Society, 2002: 1125-1130.
[6]YOUNIS O, FAHMY S. Heed: a hybrid, energy- efficient, distributed clustering approach for Ad hoc sensor networks[J]. IEEE Trans on Mobile Computing, 2004,3(4):660-669.
[7]CHAN H, PERRIG A. ACE: an emergent algorithm for highly uniform cluster formation[C]//Proc of the 1st European Workshop on Wireless Sensor Networks. LNCS 2920. Berlin: Springer-Verlag, 2004: 154-171.
[8]XU Y, HEIDEMANN J, ESTRIN D. Geography informed energy conservation for Ad hoc routing[C]//Proc of the 7th Annual Int’l Conf on Moblie Computing and Networking (MobileCOM). 2001: 70-84.
[9]HEINZELMAN W R, CHANDRAKASAN A, BALAKRISLMAN H. Energy-efficient communication protocol for wireless microsensor networks[C]//Proc ofHawaii International Conference on System Sciences. Maui, Hawaii:[s.n.], 2000.
[10]POTTIE G J, KAISER W J. Embedding the internet: wireless integrated network sensors[J]. Communications of the ACM, 2000,43(5):51-58,
“本文中所涉及到的圖表、注解、公式等內(nèi)容請(qǐng)以PDF格式閱讀原文”