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

丁緒星,蔡 偉,潘承先

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

0 引言

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

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

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

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

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

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

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

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

2 改進的算法

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

2.1 簇的建立階段

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

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

圖1 首輪簇頭選舉過程

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

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

3 算法仿真分析

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

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

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

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

圖3 總能量消耗

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

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

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

圖5 總能量消耗

4 結束語

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

[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.