基于時間驅(qū)動簇頭選擇非均勻分簇路由算法?

柳 平,石中華,呂金風(fēng)

(汕頭大學(xué)電子工程系,廣東汕頭 515063)

隨著傳感技術(shù)、嵌入式技術(shù)以及低功耗無線通信技術(shù)的發(fā)展,生產(chǎn)具備感應(yīng)、無線通信以及信息處理能力的微型無線傳感器已成為可能.這些傳感器節(jié)點之間通過相互協(xié)作,將其監(jiān)測和感應(yīng)的多種環(huán)境信息(如溫度和濕度等)傳送到基站進行處理,無線傳感器網(wǎng)絡(luò)廣泛應(yīng)用在國防軍事、救急和環(huán)境監(jiān)測等領(lǐng)域[1,2].

與無線移動自組網(wǎng)不同,無線傳感器網(wǎng)絡(luò)一般具有較大的節(jié)點密度且沒有IP地址,同時由于受到成本和體積等原因限制,無線傳感器節(jié)點的處理能力低和無線帶寬以及電池容量等資源匱乏.在大多數(shù)應(yīng)用中,傳感器節(jié)點被部署后就無法對其充電,這使得如何提高網(wǎng)絡(luò)生存時間成為無線傳感器網(wǎng)絡(luò)研究主要方向之一.

1 相關(guān)研究

無線傳感器網(wǎng)絡(luò)的主要任務(wù)是把傳感器節(jié)點收集數(shù)據(jù)發(fā)送到基站,這是節(jié)點消耗能量主要部分.在文獻[3]中,提出了直接傳送即網(wǎng)絡(luò)中的每個節(jié)點把收集到數(shù)據(jù)直接傳送到基站,這種方法簡單,然而,對于遠離基站的節(jié)點,將消耗更多能量,很快就死亡.在文獻[4]中定義網(wǎng)絡(luò)生存時間是網(wǎng)絡(luò)中第一個節(jié)點死亡的時間,所以均衡節(jié)點能量消耗尤其重要.Heinzelman等人提出 LEACH分簇協(xié)議[5],每個簇包含一個簇頭和多個簇成員節(jié)點,簇頭周期輪換,將整個網(wǎng)絡(luò)的能量負載平均分配給每個節(jié)點,延長網(wǎng)絡(luò)生存周期.Younis等提出了一種混合式的分簇協(xié)議HEED[6],算法首先根據(jù)剩余能量來概率性選擇一些候選簇頭,然后以簇內(nèi)通信代價的高低來競爭產(chǎn)生簇頭.但需要在簇內(nèi)進行多次消息迭代,由此帶來的通信開銷比較顯著.文獻[7]提出了EECS分簇協(xié)議,節(jié)點在選擇簇頭時不是簡單地選擇距離自身最近的簇頭,而是考慮候選簇頭到基站的距離,這樣使得靠近基站的簇頭將有更多的簇成員節(jié)點,遠離基站的簇頭有比較少的簇成員節(jié)點,有利于均衡簇頭間負載.

上述介紹路由協(xié)議屬于簇頭單跳傳送數(shù)據(jù)協(xié)議,對于大型網(wǎng)絡(luò),簇頭離基站較遠,通過單跳將消耗更多能量.文獻[8]指出,采用簇頭組成的骨干網(wǎng)實現(xiàn)多跳路由的方式更有利于節(jié)約能量,然而這種做法帶來了能量消耗不均衡的問題:靠近基站的簇頭由于轉(zhuǎn)發(fā)大量來自其它簇頭的數(shù)據(jù)而負擔(dān)過重,過早耗盡自身能量而死亡,造成網(wǎng)絡(luò)分割降低網(wǎng)絡(luò)存活時間,研究者稱這個問題為“熱區(qū)”問題[9].Soro等人首次在文獻[10]提出利用非均勻分簇的思想解決這個“熱區(qū)”問題,假設(shè)網(wǎng)絡(luò)拓撲環(huán)繞基站的兩層同心圓環(huán),內(nèi)環(huán)簇頭靠近基站,需要承擔(dān)數(shù)據(jù)轉(zhuǎn)發(fā)任務(wù),通過減少的簇成員數(shù)量降低簇內(nèi)處理中消耗的能量,為簇頭間數(shù)據(jù)轉(zhuǎn)發(fā)保留能量.但是他們考慮是一個異構(gòu)網(wǎng)絡(luò),簇頭的分布是事先設(shè)計好的,不適合隨機部署的網(wǎng)絡(luò).李成發(fā)等人在文獻[11]和[12]中提出了EEUC算法以及文獻[13]提出了MRPUC算法,它們是一種基于競爭的多跳非均勻分簇算法,仿真結(jié)果顯示了較好的結(jié)果.但此算法在簇頭選舉時存在以下不足:①很多能量較少的節(jié)點被激活參與競選卻不能獲勝,浪費能量;②隨機激活無法保證獲勝節(jié)點最優(yōu);③每個競選節(jié)點都會發(fā)送和接收競爭廣播等消息并進行計算,網(wǎng)絡(luò)開銷大.

為了很好解決EEUC算法在簇頭選舉時存在的不足,本文提出一種基于時間驅(qū)動簇頭選擇非均勻分簇路由算法,該算法直接通過節(jié)點廣播成為簇頭消息產(chǎn)生簇頭,廣播時間與其剩余能量成反比,減少了由競爭產(chǎn)生簇頭帶來的能量消耗,保證了選出簇頭有較高剩余能量且每輪產(chǎn)生簇頭數(shù)目波動小.

2 網(wǎng)絡(luò)模型

研究的網(wǎng)絡(luò)分布在一正方形區(qū)域內(nèi),由個隨機分布的傳感器節(jié)點組成,其應(yīng)用場景是網(wǎng)絡(luò)周期性的數(shù)據(jù)收集,并且該傳感器網(wǎng)絡(luò)具有如下性質(zhì):①傳感器節(jié)點部署后不再移動,基站部署在區(qū)域外的一個固定位置.②所有節(jié)點具有相似的數(shù)據(jù)處理、通信等功能,并且地位平等,都有一個唯一的標識(ID).③根據(jù)接收者的距離遠近,節(jié)點可以自動調(diào)節(jié)其發(fā)射功率.④鏈路是對稱的,若已知對方發(fā)射功率,節(jié)點根據(jù)接收的信號強度計算出發(fā)送者離自身的距離[11].

本文與文獻[4]使用相同的無線通信能量消耗模型,該模型給出一個閾值do,當(dāng)發(fā)送節(jié)點與接收節(jié)點距離小于時do,發(fā)送節(jié)點發(fā)送數(shù)據(jù)的能量損耗與距離的平方成正比,否則與距離的4次方成正比.上述兩種能量衰減模型分別稱為自由空間模型(free space)和多路衰減模型(multipath fading).例如節(jié)點a向節(jié)點b發(fā)送k比特數(shù)據(jù),兩者相距距離為d,節(jié)點a發(fā)送數(shù)據(jù)能量消耗由發(fā)射電路損耗和功率放大損耗兩部分組成,即

而b接收a數(shù)據(jù)能量消耗為

式中:Eelec表示無線收發(fā)電路所消耗的能量;εfs和 εmp分別為這兩種模型中功率放大所需的能量.

本文采用了數(shù)據(jù)融合技術(shù)減少發(fā)送和接收的數(shù)據(jù)量,用 EDF表示融合單位比特數(shù)據(jù)消耗能量.假設(shè)鄰近節(jié)點采集數(shù)據(jù)有較高的冗余度,簇頭可以將其簇成員發(fā)送來的數(shù)據(jù)融合成一個長度固定的數(shù)據(jù)包,而簇與簇之間數(shù)據(jù)不發(fā)生融合.

3 本文路由算法

在網(wǎng)絡(luò)建立階段,基站需要用足夠大的發(fā)送功率向全網(wǎng)絡(luò)廣播信息,消息包括其發(fā)送功率.網(wǎng)絡(luò)中節(jié)點根據(jù)基站的發(fā)送功率計算出到基站的近似距離,利用此距離不僅可以調(diào)節(jié)向基站發(fā)送數(shù)據(jù)所需的發(fā)送功率,還可以用它計算其競爭半徑.

該算法包括分簇和數(shù)據(jù)傳輸兩個階段,分簇又可以分為簇頭選擇和簇的形成兩部分,數(shù)據(jù)傳輸也分為簇內(nèi)數(shù)據(jù)傳輸和簇頭間數(shù)據(jù)傳輸.為了使簇內(nèi)信息進行交流,本文引入了簇內(nèi)信息交流階段,它們在每一輪中有對應(yīng)時隙,如圖1所示.

圖1 每輪時隙圖Fig.1 Time slot at each round

3.1 簇頭選擇

在無線傳感器網(wǎng)絡(luò)中,每輪進行簇頭選擇時,首先傳感器節(jié)點根據(jù)剩余能量計算出其廣播成為簇頭消息CLUSTER_ HEAD_MSG 的時間,其表達式為

式中:T1為網(wǎng)絡(luò)中簇頭選擇時間;Ei表示節(jié)點i剩余能量;Ea,Emin和Emax分別表示上一輪節(jié)點所在簇平均剩余能量、簇內(nèi)節(jié)點最小剩余能量和最大剩余能量;ni∈(0,1)隨機數(shù),用于避讓相同剩余能量節(jié)點廣播消息引起的沖突.

在每輪簇頭選擇時,所有節(jié)點按照自身發(fā)送時間來廣播CLUSTER_ HEAD_ MSG 消息.因此,剩余能量高的節(jié)點,先廣播其消息,它的廣播半徑不是最大的競爭半徑,而是自身的競爭半徑,可以節(jié)省能量,如節(jié)點i競爭半徑為

式中:dmax和dmin分別表示節(jié)點到基站距離的最大值和最小值;di為節(jié)點i到基站的距離;Rp為最大競爭半徑;c∈(0,1)為調(diào)節(jié)參數(shù).

當(dāng)普通節(jié)點接收到CLUSTER HEAD_MSG 消息,此節(jié)點將不廣播CLUSTER_ HEAD_ MSG消息并記錄發(fā)送者的信息.簇頭接收到CLUSTER_ HEAD MSG消息后,不做處理.經(jīng)過時間T1后,網(wǎng)絡(luò)中簇頭全部選出.

3.2 簇的形成

簇頭選擇完成后,普通節(jié)點如果只接收到一個簇頭發(fā)送來的CLUSTER HEAD MSG 消息,就選擇該簇頭.如果接收到多個簇頭發(fā)送來的CLUSTER_ HEAD_ MSG 消息,就選擇簇內(nèi)通信代價最小亦即接收信號強度最大的簇頭.普通節(jié)點選擇自身簇頭后,就發(fā)送加入消息JOIN_CLUSTER_ MAG 通知該簇頭.簇頭接收到該消息后,進行構(gòu)建TDMA調(diào)度并將它發(fā)送給簇內(nèi)所有節(jié)點,確保簇內(nèi)所有節(jié)點發(fā)送數(shù)據(jù)沒有碰撞,同時可以讓節(jié)點除了自身發(fā)送時間外進行休眠,節(jié)省節(jié)點能量.

3.3 數(shù)據(jù)傳輸

簇頭首先收集從簇內(nèi)成員節(jié)點發(fā)送來數(shù)據(jù),并進行數(shù)據(jù)融合,然后把數(shù)據(jù)發(fā)送給中繼簇頭或基站.中繼簇頭只是簡單轉(zhuǎn)發(fā)來自其它簇頭的數(shù)據(jù),而不能進行數(shù)據(jù)融合.

在簇間傳輸數(shù)據(jù)開始時,每個簇頭以相同的功率向全網(wǎng)絡(luò)廣播一條消息NODESTATE_MSG ,包含ID、當(dāng)前剩余能量和它到基站的距離.如果簇頭i收到由簇頭j廣播的NODE_STATEMSG 消息,就可以計算出它們之間的近似距離dij.同時定義簇頭的中繼簇頭集合RCH(i)為

如果RCH(i)為空集,則節(jié)點直接與基站通信.

由于采用的無線通信能量消耗模型,發(fā)送數(shù)據(jù)能量消耗與距離的平方或4次方成正比,由于采用了多跳傳輸,可以假設(shè)與距離的平方成正比.簇頭i選擇中繼簇頭從能量開銷指標如式(6)和中繼簇頭剩余能量考慮,首先找到與簇頭i最小能量開銷Erelay兩個簇頭,然后從中選出剩余能量最大的簇頭作為中繼簇頭.

為了減輕靠近基站邊緣地區(qū)節(jié)點轉(zhuǎn)發(fā)數(shù)據(jù)的負擔(dān),引入了一個閾值 TD_MAX ,若簇頭到基站的距離小于TD_ MAX ,它就直接與基站進行通信,否則通過其它簇頭轉(zhuǎn)發(fā)把數(shù)據(jù)送到基站.

簇間傳輸數(shù)據(jù)結(jié)束后,進入簇內(nèi)信息交流階段,各簇簇內(nèi)成員節(jié)點把自身剩余能量發(fā)送到簇頭,簇頭接收并計算出簇內(nèi)平均剩余能量Ea、簇內(nèi)節(jié)點最小剩余能量Emin和最大剩余能量Emax,然后向簇內(nèi)廣播一條包含Ea,Emin和Emax的消息 CLUSTER_ENERGY_MSG.

4 算法分析

本文算法是一個分布式動態(tài)算法,以節(jié)點剩余能量選擇簇頭,在每輪中,該算法簇頭選擇的消息復(fù)雜度為O(N).假設(shè)共選出了k個簇頭,則它們就廣播k條CLUSTER_HEADMSG 消息,而N-k個簇成員發(fā)送N-k條JOIN_CLUSTER_ MAG 消息.消息的開銷為k+N-k=N,所以其復(fù)雜度為O(N).

該算法比EEUC算法消息開銷小,且不需要設(shè)置文獻[11]中普通節(jié)點成為候選簇頭的概率閾值,它對于EEUC算法有很大影響,閾值過大,會增加消息的開銷,閾值過小,使候選簇頭過小,導(dǎo)致選出的簇頭不是最優(yōu),同時本文算法廣播消息不是以最大競爭半徑廣播,將節(jié)省節(jié)點能量.

本文算法中參數(shù)Rp和c取值對網(wǎng)絡(luò)生存時間的影響與文獻[11]一樣,c的值越大,候選簇頭的競爭半徑差異越大,因此簇成員數(shù)目間的差異越明顯.算法中所產(chǎn)生的簇的數(shù)目由Rp和c共同決定,固定Rp,當(dāng)c增大時,每個簇頭競爭半徑隨之減小,所生成的簇的數(shù)目將增加.固定c,當(dāng)Rp增大時,每個簇頭競爭半徑隨之增大,所生成簇的數(shù)目將減小.Rp和c優(yōu)化取值可以優(yōu)化網(wǎng)絡(luò)中節(jié)點的能量消耗,延長網(wǎng)絡(luò)存活時間.用理論化的方法選擇最優(yōu)參數(shù)值還要進一步研究.

5 仿真和分析

為了說明算法效果,對算法進行仿真測試,選擇的仿真參數(shù)設(shè)置取自文獻[11],如表1所示.

圖2是LEACH、EEUC和本文算法網(wǎng)絡(luò)生存時間的比較,從圖中可以看出,本文算法的網(wǎng)絡(luò)生存時間最長,EEUC次之,LEACH最差.從第一個節(jié)點死亡到最后死亡節(jié)點的時間跨度可以反映網(wǎng)絡(luò)中節(jié)點能量均衡情況,跨度越短說明網(wǎng)絡(luò)能量使用越高效,本文算法跨度最短,EEUC略差于本文算法,LEACH跨度很大.原因是本文算法采用時間驅(qū)動簇頭選擇,可以降低消息復(fù)雜度和節(jié)省節(jié)點能量.EEUC算法采用隨機數(shù)和閾值機制產(chǎn)生候選簇頭,再由候選簇頭競爭產(chǎn)生簇頭,這將消耗大量能量.LEACH算法隨機產(chǎn)生簇頭,沒有考慮節(jié)點剩余能量,可能選出簇頭能量低,這樣會加速節(jié)點死亡.

表1 仿真參數(shù)Tab.1 Simulation parameters

圖2 網(wǎng)絡(luò)生存時間Fig.2 Network lifetime

圖3 簇頭數(shù)量對比Fig.3 The number of cluster head comparison

圖3是3種算法生成簇頭數(shù)量對比,從圖中可以看出,EEUC和本文算法產(chǎn)生的簇頭數(shù)量穩(wěn)定,LEACH簇頭數(shù)量的波動范圍最大,這是因為LEACH單純采用隨機數(shù)與閾值的機制產(chǎn)生簇頭,因此簇頭數(shù)量變化比較明顯.EEUC和本文算法簇頭數(shù)量變化比較集中,這是因為2種算法均采用了局部區(qū)域競爭的方法,有效地控制了算法所生成的簇頭數(shù)量.但是,本文算法產(chǎn)生的簇頭數(shù)量更集中,主要原因是由時間驅(qū)動直接產(chǎn)生簇頭,不像EEUC算法由隨機數(shù)與閾值的機制產(chǎn)生候選簇頭,因此本文算法產(chǎn)生的簇頭數(shù)量更加穩(wěn)定.

圖4 基站接收到數(shù)據(jù)包總數(shù)Fig.4 Total amount of data packects received at BS

圖4是3種算法中基站接收數(shù)據(jù)包數(shù)目比較,從圖中可以看出,在本文算法下,基站接收的數(shù)據(jù)包隨輪數(shù)線性增長且總數(shù)目最多,說該算法運行穩(wěn)定,能量效率高.EEUC接收的數(shù)據(jù)包隨輪數(shù)近似線性增長且總數(shù)目低,說明了算法能有效平衡節(jié)點能耗但能量效率低.LEACH算法在700輪后數(shù)據(jù)包數(shù)增加緩慢,由于節(jié)點能量消耗不均,造成網(wǎng)絡(luò)中大量的節(jié)點死亡,減少了節(jié)點發(fā)送到基站數(shù)據(jù)包數(shù)目.

綜合實驗結(jié)果,本文提出路由算法具有以下優(yōu)點:①分簇算法穩(wěn)定,所生成簇的數(shù)目波動小;②有效平衡了網(wǎng)絡(luò)中節(jié)點的消耗,延長網(wǎng)絡(luò)生存時間;③基站能夠從網(wǎng)絡(luò)中獲得較多數(shù)據(jù),有利于判斷環(huán)境的變化.

6 結(jié) 論

本文提出了一種基于時間驅(qū)動簇頭選擇非均勻分簇路由算法,它的核心思想是:首先,節(jié)點利用其剩余能量競選簇頭,避免由網(wǎng)絡(luò)隨機產(chǎn)生候選簇頭,再由候選簇頭通過競爭產(chǎn)生簇頭的繁瑣過程,同時降低了算法消息復(fù)雜度.其次,普通節(jié)點根據(jù)簇內(nèi)通信代價最小選擇簇頭,構(gòu)造出大小不等的簇,對于解決由多跳路由引起傳感器網(wǎng)絡(luò)“熱區(qū)”問題很有效.實驗證明,該算法比LEACH和EEUC算法更能延長網(wǎng)絡(luò)生存時間.

本算法雖然有效解決了EEUC算法對普通節(jié)點成為候選簇頭的概率取值,但未能對其它參數(shù)優(yōu)化取值進行詳細分析,事實上它們對于網(wǎng)絡(luò)生存時間有很大影響,因此,在以后工作中,將對這些參數(shù)的最優(yōu)取值進行研究.

[1]Estrin D,Girod L,Pottie G,et al.Instrumenting the World with Wireless Sensor Networks[C].In:Proc.of the Int′l Conf.on Acoustics,Speech,and Signal Processing(ICASSP 2001),2001.

[2]Pottie G J,Kaiser W J.Wireless integrated network sensors[J].Communications of the ACM,2000,43(5):51-58.

[3]Estrin D.Next Century Challenges:Scalable Coordination in Sensor Networks[C].In:Proc.of the MobiCOM′99,1999:263-270.

[4]Chang J H,Tassiulas L.Maximum lifetime routing in wireles sensor networks[J].IEEE/ACM Trans.on Networking,2004,12(4):609-619.

[5]Heinzelman W R,ChandrakasanA P,Balakrishnan H.An application specific protocol architecture for wireless microsensor networks[J].IEEE Trans on Wireless Communications,2002,1(4):660-670.

[6]Younis O,Fahmy S.HEED:A hybrid,energy efficient,distributed clustering approach for ad hoc sensor networks[J].IEEE Transactions on Mobile Computing,2004,3(4):660-669.

[7]Ye M,Li C,Chen G,et al.EECS:An Energy Efficient Cluster Scheme in Wireless Sensor Networks[M].New York:Proceedings of the IEEE IPCCC,2005:535-540.

[8]Mhatre V,Rosenberg C.Design guidelines for wreless sensornetworks:communication.clustering and aggregation[J].Ad-Hoc Network,2004,2(l):45-63.

[9]Li C,Ye M,Chen G,et al.An Energy Effieient Unequal Clustering Mechanism for Wireless Sensor Networks[C].Proeedings of the 2th IEEE International Conference on Mobile Ad hoc and Sensor Systems.Washington,DC,2005:597-604.

[10]Soro S,Heinzelman W.Prolonging the Lifetimeof Wireless Sensor Networks Via Unequal Clustering[C].Proceedings of the 5th International Workshop on Algorithms for Wireless,Mobile,Ad Hoc and Sensor Networks,Denver,CO,2005.

[11]李成法,陳貴海,葉懋,等.一種基于非均勻分簇的無線傳感器網(wǎng)絡(luò)路由協(xié)議[J].計算機學(xué)報,2007,30(1):27-36.

Li Chengfa,Chen Guihai,Ye Mao,et al.An uneven cluster-based routing protocol for wireless sensor networks[J].Chinese Journal of Computers,2007,30(1):27-36.(in Chinese)

[12]ChenGuihai,LiChengfa,Ye Mao,et al.An unequal cluster-based routing protocolin wirelesssensor networks[J].Wireless Networks,2009,15(2):193-207.

[13]Gong Bencan,Li Layuan Li,Wang Shaorong,et al.Multihop Routing Protocolwith Unequal Clustering for WirelessSensor Networks[C].Computing,Communication,Control,and Management,2008.CCCM′08.ISECS InternationalColloquium on,2008:552-556.