一種改進(jìn)的多簇頭路由協(xié)議

丁緒星,蔡 偉,潘承先

（安徽師范大學(xué)物理與電子信息學(xué)院,安徽 蕪湖 241000）

0 引言

無(wú)線傳感器網(wǎng)絡(luò)目前研究的熱點(diǎn)之一是路由算法[1-3],RRCH[4]算法在整個(gè)生命周期按輪詢周期分簇工作。算法的基本思想是在全網(wǎng)過(guò)程中只實(shí)行一次簇的建立過(guò)程,之后固定每個(gè)簇,當(dāng)需要更換簇頭時(shí),在每個(gè)簇內(nèi)選舉一個(gè)剩余能量最高的成員節(jié)點(diǎn)作為下一輪的簇頭,相比每一輪都進(jìn)行全網(wǎng)簇頭選舉的算法,這種簇頭選舉方法減少節(jié)點(diǎn)的能耗。但是RRCH算法選舉出的簇頭,可能分布在簇的邊緣,造成部分簇內(nèi)成員節(jié)點(diǎn)離簇頭過(guò)遠(yuǎn),而且每輪只選出唯一簇頭,會(huì)導(dǎo)致此簇頭節(jié)點(diǎn)通信時(shí)消耗更多的能量。提出了一種改進(jìn)分簇路由協(xié)議:多簇頭路由算法?；舅枷胧窃诖仡^選舉過(guò)程中,選出2個(gè)簇頭協(xié)同工作管理整個(gè)簇,每個(gè)簇分給2個(gè)簇頭管理,簇成員按照就近原則發(fā)送監(jiān)控信息給2個(gè)簇頭中的1個(gè),再由簇頭轉(zhuǎn)發(fā)給匯聚節(jié)點(diǎn)。

1 網(wǎng)絡(luò)通信模型

通信模型對(duì)無(wú)線傳感器網(wǎng)絡(luò)做了如下假設(shè):匯聚節(jié)點(diǎn)（Sink）位置固定且離監(jiān)控網(wǎng)絡(luò)較遠(yuǎn)所有傳感器節(jié)點(diǎn)位置固定,具有相同的傳輸距離網(wǎng)絡(luò)中所有傳感器節(jié)點(diǎn)具有相同的初始能量,并且能量有限,每個(gè)節(jié)點(diǎn)的ID號(hào)唯一。

傳感器節(jié)點(diǎn)在數(shù)據(jù)傳輸過(guò)程中消耗的能量模型[5]主要由2部分組成:發(fā)送數(shù)據(jù)能耗和接受數(shù)據(jù)能耗。發(fā)送數(shù)據(jù)能耗主要由2部分組成:發(fā)射電路損耗和功率放大損耗。即發(fā)送1bit的數(shù)據(jù)經(jīng)過(guò)d距離消耗的能量為:

式中,Eelec為發(fā)送或接受電路損耗;d0為距離門限;Efsd2為傳輸距離小于d0時(shí),自由空間信道模型的功率放大器功耗;Eampd為距離大于等于d0時(shí),多徑衰落信道模型的功率放大器功耗。

接受1 bit數(shù)據(jù)消耗的能量為:

簇頭節(jié)點(diǎn)融合m個(gè)L比特的數(shù)據(jù)包,所需要的能量為:

式中,Efusion為融合每1 bit所消耗的能量。

2 改進(jìn)的算法

算法即主從式簇頭路由算法,主要分為2步:簇的建立階段和數(shù)據(jù)傳輸形成階段。

2.1 簇的建立階段

第1輪時(shí),網(wǎng)絡(luò)中的每個(gè)節(jié)點(diǎn)產(chǎn)生1個(gè)隨機(jī)數(shù)R與設(shè)定的閾值T比較,若R小于T,該節(jié)點(diǎn)標(biāo)識(shí)自身為候選節(jié)點(diǎn),廣播一個(gè)包含自身ID和剩余能量Energy的CANDIDATE消息。假設(shè)當(dāng)候選節(jié)點(diǎn)接收到鄰居候選節(jié)點(diǎn)的CANDIDATE消息時(shí),將該鄰居添加到候選節(jié)點(diǎn)集CLUSTER中,從CLUSTER中選舉1個(gè)剩余能量最大的節(jié)點(diǎn)作為簇頭節(jié)點(diǎn)。如果這個(gè)簇頭是本身,則本身廣播一條包括自身ID和剩余能量的HEAD消息通知其鄰居節(jié)點(diǎn),如果本身不是簇頭,則廣播一條COMMON消息宣布自身為普通節(jié)點(diǎn)。

對(duì)于1個(gè)普通節(jié)點(diǎn),收到1條HEAD消息后將發(fā)送該消息的節(jié)點(diǎn)信息ID,Energy添加到自己的簇頭節(jié)點(diǎn)集中,從CLUSTER中選舉出剩余能量最高的節(jié)點(diǎn)作為簇頭節(jié)點(diǎn),并發(fā)送1條JOIN消息給該簇頭。對(duì)于1個(gè)簇頭節(jié)點(diǎn),收到1條JOIN消息后將發(fā)送消息的節(jié)點(diǎn)信息添加到成員節(jié)點(diǎn)集中,簇頭節(jié)點(diǎn)從中再選舉出1個(gè)剩余能量最高的成員節(jié)點(diǎn)作為另1個(gè)簇頭節(jié)點(diǎn)CLUSTERHEAD2,并且廣播1條包含節(jié)點(diǎn)ID的MESSAGE消息。當(dāng)成員節(jié)點(diǎn)收到MESSAGE消息后,在其鄰居節(jié)點(diǎn)集中尋找此節(jié)點(diǎn),再按照就近原則,加入離自己較近的簇頭。這樣1個(gè)含有2個(gè)簇頭節(jié)點(diǎn)的簇建立完成。簇頭再為每個(gè)節(jié)點(diǎn)分配TDMA時(shí)隙,為傳輸數(shù)據(jù)準(zhǔn)備。下一輪,簇繼續(xù)選擇剩余能量大的2個(gè)節(jié)點(diǎn)作為為簇頭,過(guò)程與RRCH相同。首輪簇頭選舉過(guò)程如圖1所示。

圖1 首輪簇頭選舉過(guò)程

2.2 數(shù)據(jù)傳輸階段

成簇之后,每個(gè)簇頭廣播1條包含自身ID和權(quán)值V的WEIGHT剩余能量消息。假設(shè)簇頭節(jié)點(diǎn)i收到來(lái)自簇頭節(jié)點(diǎn)j的WEIGHT剩余能量消息,節(jié)點(diǎn)i會(huì)計(jì)算出權(quán)值剩余能量差Vij∶Vij=Vi-Vj,（i,j=0,1,……N）,最后節(jié)點(diǎn)i會(huì)從中選擇權(quán)值差Vij最小的節(jié)點(diǎn)作為傳送數(shù)據(jù)到Sink的下一跳,這樣就構(gòu)成了一條多跳路由,最終由離Sink最近的簇頭節(jié)點(diǎn),直接與Sink通信。如果某簇頭節(jié)點(diǎn)在其通信范圍內(nèi)不能與其他節(jié)點(diǎn)通信,則直接發(fā)送數(shù)據(jù)給Sink。

3 算法仿真分析

算法在OMNET++仿真平臺(tái)下對(duì)算法進(jìn)行仿真,按照上文所討論的無(wú)線通信模型編程設(shè)定節(jié)點(diǎn)發(fā)送與接收數(shù)據(jù)時(shí)的能耗,設(shè)定仿真參數(shù)如表1所示。

表1 仿真參數(shù)值設(shè)置

仿真?zhèn)鞑^(qū)域?yàn)?00*500,節(jié)點(diǎn)數(shù)目為100,Sink節(jié)點(diǎn)位置（250m,875m）。圖2和圖3的縱軸分別顯示的是節(jié)點(diǎn)死亡數(shù)和能量消耗值,橫軸均為仿真時(shí)間。兩圖分別為節(jié)點(diǎn)死亡數(shù)對(duì)比和消耗能量對(duì)比;由圖可知,隨著仿真時(shí)間的延長(zhǎng),MCHB算法的節(jié)點(diǎn)死亡數(shù)以及能量消耗均比傳統(tǒng)的RRCH算法小。RRCH算法的缺點(diǎn)在于成簇過(guò)程中,只有1個(gè)簇頭管理整個(gè)簇,當(dāng)該簇頭位于整個(gè)簇的邊緣時(shí),簇內(nèi)部分成員節(jié)點(diǎn)離該簇頭較遠(yuǎn),從而消耗了更多的能量。MCHB算法每個(gè)簇中,2個(gè)簇頭同時(shí)工作,同時(shí)路由采用多跳通信解決了RRCH算法的問(wèn)題。

圖2 死亡節(jié)點(diǎn)數(shù)

圖3 總能量消耗

將仿真?zhèn)鞑^(qū)域增大為1000m*1000m,Sink節(jié)點(diǎn)位置（500m,1750m）。仿真結(jié)果如圖4和圖5所示。

從圖4中可以看出,RRCH算法死亡節(jié)點(diǎn)數(shù)達(dá)到50個(gè)時(shí),MCHB才達(dá)到35左右,相比死亡節(jié)點(diǎn)數(shù)降低了約30%;從圖5中可以得到,網(wǎng)絡(luò)能耗降低了約28%。

圖4 死亡節(jié)點(diǎn)數(shù)

圖5 總能量消耗

4 結(jié)束語(yǔ)

提出了一種MCHB算法,選出2個(gè)簇頭協(xié)同工作管理整個(gè)簇,每個(gè)簇分給2個(gè)簇頭管理,簇成員按照就近原則發(fā)送監(jiān)控信息給2個(gè)簇頭中的一個(gè),再由該簇頭轉(zhuǎn)發(fā)給下一跳節(jié)點(diǎn),最后通過(guò)多跳通信傳給匯聚節(jié)點(diǎn)。在仿真實(shí)驗(yàn)中,MCHB與RRCH作結(jié)果顯示MCHB能有效平衡網(wǎng)絡(luò)負(fù)載,延長(zhǎng)網(wǎng)絡(luò)生存時(shí)間。

[1]RAGHUNATHAN V,SCHURGERS C,PARK S.Energy-aware wireless microsensor networks[J].IEEE Signal Processing Magazine,2002,19（2）:40-50.

[2]MNJESHWAR A,GRAWAL D P.TEEN:A protocol for enhanced efficiency in wireless sensor networks[C]//Proc of the 15th Parallel and Distributed Processing Symp.San Francisco:IEEE Computer Society,2001,5（7）:2009-2015.

[3]BENINI L,BOGLIOLO A,MICHELI D G.A survey of design techniques for system-level dynamic power Management[J].IEEE Transactions on Very Large Scale Integration Systems,2000:299-316.

[4]NAM Do-hyun,MIN Hong-ki.An energy-efficient clustering using a round-obinmethod in awireless sensor network[C]//Proceedings of the 5th ACIS International Conference on Software Engineering Research,Management&Applications,2007:54-60.

[5]HEINZEL MAN W,CHANDR AKASAN A.Energy-Efficient communications protocol for wireless microsensor networks[C]// Proceedings of the 33rd Annual Havaii Int'1 Conference onSystem Sciences,2000:1-10.