王 桐, 楊 磊
(哈爾濱工程大學(xué) 信息與通信工程學(xué)院,哈爾濱 150001)
無(wú)線傳感器網(wǎng)絡(luò)(wireless sensor networks,WSN)是由大量的微型的傳感器節(jié)點(diǎn)構(gòu)成的,各個(gè)節(jié)點(diǎn)通過(guò)自組織方式構(gòu)成無(wú)線網(wǎng)絡(luò),并以相互協(xié)作的方式感知、采集和處理網(wǎng)絡(luò)覆蓋區(qū)域內(nèi)的特定信息[1]。與傳統(tǒng)無(wú)線網(wǎng)絡(luò)不同,組成網(wǎng)絡(luò)的傳感器節(jié)點(diǎn)的能量有限,且通常無(wú)法進(jìn)行更換。因此,在設(shè)計(jì)WSN路由算法時(shí),需要重點(diǎn)考慮節(jié)點(diǎn)的能量效率以便盡最大可能地延長(zhǎng)網(wǎng)絡(luò)的工作時(shí)間[2]。
近年來(lái),在無(wú)線傳感器網(wǎng)絡(luò)中,有很多分簇路由算法被提出。為了避免簇頭過(guò)多地消耗能量和減少通信業(yè)務(wù)量,文獻(xiàn)[3]提出了一種低功耗自適應(yīng)分簇路由算法(low energy adaptive clustering hierarchy,LEACH)。采用循環(huán)隨機(jī)成簇方式,各節(jié)點(diǎn)輪流擔(dān)任簇頭,使網(wǎng)絡(luò)的能量負(fù)載均衡到各個(gè)節(jié)點(diǎn)上,延長(zhǎng)了網(wǎng)絡(luò)的生存時(shí)間,但是LEACH采用單跳通信方式,簇頭與基站進(jìn)行直接通信,造成簇頭的通信開銷很大。研究已表明,在數(shù)據(jù)轉(zhuǎn)發(fā)過(guò)程中簇頭和基站之間采用多跳通信方式更有利于節(jié)約能量[4]。多跳通信方式進(jìn)行數(shù)據(jù)傳輸和轉(zhuǎn)發(fā)時(shí),很容易導(dǎo)致與基站較近的簇頭因需承擔(dān)過(guò)多的轉(zhuǎn)發(fā)任務(wù)而過(guò)早的死亡,造成網(wǎng)絡(luò)能耗極不均衡,即所謂“熱區(qū)”問(wèn)題[5-6]。針對(duì)該問(wèn)題,文獻(xiàn)[7]給出了一種基于分布式的非均勻分簇算法(energy-efficient uneven clustering,EEUC),根據(jù)候選簇頭到基站的距離遠(yuǎn)近,從地理位置上將網(wǎng)絡(luò)分成大小不等的非均勻的簇類結(jié)構(gòu),以便均衡簇頭的負(fù)載,但是在簇頭競(jìng)選時(shí)沒(méi)有考慮節(jié)點(diǎn)的剩余能量,而且成簇過(guò)程中容易出現(xiàn)迭代現(xiàn)象,成簇開銷比較大。文獻(xiàn)[8]從部署模型上進(jìn)行考慮,采用蟻群算法優(yōu)化網(wǎng)絡(luò)中各個(gè)節(jié)點(diǎn)的能耗問(wèn)題,仿真表明,能夠延長(zhǎng)網(wǎng)絡(luò)的生存時(shí)間,但是需要人工部署限制了其在實(shí)際環(huán)境中的應(yīng)用。文獻(xiàn)[9]提出了負(fù)載均衡的自適應(yīng)分簇算法,在簇頭選擇上同時(shí)考慮簇半徑、節(jié)點(diǎn)剩余能量和簇頭間距,并采用多跳方式進(jìn)行數(shù)據(jù)通信。文獻(xiàn)[10]對(duì)其進(jìn)行了改進(jìn),還考慮了相鄰節(jié)點(diǎn)的剩余能量。文獻(xiàn)[11]選擇剩余能量最多的節(jié)點(diǎn)擔(dān)任簇頭,且限制簇的規(guī)模。文獻(xiàn)[12]針對(duì)“熱區(qū)”問(wèn)題,提出了采用剩余能量啟發(fā)合作的傳輸方式來(lái)進(jìn)行數(shù)據(jù)傳輸?shù)姆椒?,以避免能量空洞。但是,上述路由算法皆沒(méi)有考慮簇間數(shù)據(jù)傳輸時(shí)的長(zhǎng)距離通信問(wèn)題。
鑒于此,筆者對(duì)EEUC算法進(jìn)行改進(jìn),提出了一種基于分層的非均勻分簇路由算法(layered unequal clustering routing algorithm,LUCRA)。LUCRA 的改進(jìn)之處:一是在EEUC算法的競(jìng)爭(zhēng)半徑計(jì)算方式上引入了節(jié)點(diǎn)的剩余能量,以使簇頭負(fù)載更加均衡。二是改進(jìn)了EEUC算法的成簇過(guò)程,避免出現(xiàn)迭代現(xiàn)象,提高了算法的收斂速度。三是通過(guò)對(duì)簇間長(zhǎng)距離通信展開分析,建立多個(gè)層次的網(wǎng)絡(luò)結(jié)構(gòu),并利用相鄰簇的交叉節(jié)點(diǎn)進(jìn)行數(shù)據(jù)轉(zhuǎn)發(fā),極大地減少了數(shù)據(jù)通信開銷,進(jìn)一步延長(zhǎng)了網(wǎng)絡(luò)的生存時(shí)間。
1.1.1 網(wǎng)絡(luò)模型
假設(shè)無(wú)線傳感網(wǎng)絡(luò)由N個(gè)節(jié)點(diǎn)組成,節(jié)點(diǎn)分布在一個(gè)固定大小的區(qū)域內(nèi)。設(shè)第i個(gè)節(jié)點(diǎn)為si,則節(jié)點(diǎn)集 S={s1,s2,s3,…,sN-2,sN-1,sN},|S|=N。傳感器網(wǎng)絡(luò)的應(yīng)用環(huán)境是周期性的數(shù)據(jù)采集,且具有如下性質(zhì):基站和節(jié)點(diǎn)部署以后不可以移動(dòng),且基站僅有一個(gè)并位于監(jiān)測(cè)區(qū)域外;所有節(jié)點(diǎn)具有相同的屬性和功能;節(jié)點(diǎn)可以根據(jù)發(fā)射接收信號(hào)的強(qiáng)度估算與發(fā)射源之間的相對(duì)位置;無(wú)線發(fā)射功率可控,節(jié)點(diǎn)能夠根據(jù)距離調(diào)整發(fā)射功率的大小。
1.1.2 無(wú)線通信模型
采用文獻(xiàn)[13]中使用的無(wú)線信道模型來(lái)計(jì)算節(jié)點(diǎn)發(fā)送和接收數(shù)據(jù)所消耗的能量。
假設(shè)節(jié)點(diǎn)A向節(jié)點(diǎn)B發(fā)送l字節(jié)的數(shù)據(jù),兩節(jié)點(diǎn)間距離為d,則其能量損耗:
節(jié)點(diǎn)B接收l(shuí)字節(jié)數(shù)據(jù)所消耗的能量為
其中,門限值d0:
式中:Eelec——發(fā)送電路和接受電路發(fā)送或接受單位比特?cái)?shù)據(jù)消耗的能量;
εamp——信號(hào)放大器的倍數(shù);
εfsd2、εmpd4——無(wú)線電功率放大損耗。
如圖1所示,節(jié)點(diǎn)A向節(jié)點(diǎn)C發(fā)送數(shù)據(jù)有兩種方式可以選擇,一是直接通信即從A到C;二是間接通信即從A到B再到C,其中節(jié)點(diǎn)B位于節(jié)點(diǎn)A和節(jié)點(diǎn)C之間。各節(jié)點(diǎn)之間的通信距離分別為dAB、dBC、dAC。
圖1 數(shù)據(jù)轉(zhuǎn)發(fā)Fig.1 Data forwarding
假設(shè)dAC大于 d0而 dAB、dBC小于 d0。從節(jié)點(diǎn) A向節(jié)點(diǎn)C發(fā)送單位比特的數(shù)據(jù),根據(jù)式(1)、(2),路徑A→C所消耗的能量為
路徑A→B→C所消耗的能量為
則EAC與EABC之比:
又由 dAB+dBC=dAC、d2AB+d2BC≥2dABdBC,可得
推導(dǎo)可得:
若令不等式(3)右邊小于1,可得
變換可得
求解可知,存在某一值,記為r。當(dāng)dAC在零到r之間,不等式(4)成立,即有EAC<EABC,若dAC大于r時(shí),不等式(4)不成立,即有EAC>EABC。也就是說(shuō)當(dāng)兩節(jié)點(diǎn)間距離小于r時(shí),采用直接通信比間接通信所消耗的能量要少,而當(dāng)兩節(jié)點(diǎn)間距離大于r時(shí),采用間接通信比直接通信所消耗的能量要少。經(jīng)估算r的值在160 m左右。因此,如果在數(shù)據(jù)轉(zhuǎn)發(fā)過(guò)程中依照此原則進(jìn)行路徑選擇,就可以有效地降低網(wǎng)絡(luò)的傳輸能耗。
LUCRA算法的整個(gè)實(shí)現(xiàn)過(guò)程包括三個(gè)部分:建立網(wǎng)絡(luò)層次結(jié)構(gòu)、簇形成和多跳傳輸。
假設(shè)根據(jù)距離基站的遠(yuǎn)近,整個(gè)傳感器網(wǎng)絡(luò)被劃分為m個(gè)層次。若以基站為原點(diǎn)向外輻射來(lái)對(duì)各個(gè)層次進(jìn)行統(tǒng)一編號(hào),則最內(nèi)層為第1層,最外層為第m層。層次數(shù):
式中:dmin——基站距離感知區(qū)域的最近距離;
dmax——基站距離感知區(qū)域的最遠(yuǎn)距離。
其中,各個(gè)層次的左右邊界BLi、BRi分別為
傳感器節(jié)點(diǎn)部署以后,基站以一定的功率向網(wǎng)絡(luò)內(nèi)的所有節(jié)點(diǎn)廣播網(wǎng)絡(luò)結(jié)構(gòu)消息。各節(jié)點(diǎn)根據(jù)接收信號(hào)的強(qiáng)度和該消息所包含的各層左右邊界信息,確定自身的所屬層次,以便競(jìng)選簇頭和數(shù)據(jù)傳輸時(shí)使用。
LUCRA算法中,每個(gè)節(jié)點(diǎn)以一定概率成為候選節(jié)點(diǎn)來(lái)參與簇頭競(jìng)選,競(jìng)選機(jī)制采用非均勻分布的方式進(jìn)行,同時(shí)將節(jié)點(diǎn)與基站間的距離和節(jié)點(diǎn)的剩余能量作為評(píng)價(jià)標(biāo)準(zhǔn)。網(wǎng)絡(luò)采用輪計(jì)數(shù)方式,每一輪開始時(shí)需要重新進(jìn)行簇頭選擇。
規(guī)則 在簇頭競(jìng)選過(guò)程中,若si當(dāng)選簇頭,則si的競(jìng)爭(zhēng)半徑Rcmp不允許有其他節(jié)點(diǎn)再成為簇頭。候選節(jié)點(diǎn)的競(jìng)爭(zhēng)半徑Rcmp為
式中:dsi,BS——節(jié)點(diǎn) i到基站的距離;
ε1、ε2——(0,1)之間的常數(shù);
R0——系統(tǒng)設(shè)置的成簇半徑。
從式(5)可見(jiàn),節(jié)點(diǎn)的成簇半徑Rcmp隨著節(jié)點(diǎn)距基站的距離和剩余能量而動(dòng)態(tài)變化,距離基站越近,剩余能量越低,成簇半徑越小。
LUCRA算法的整個(gè)成簇過(guò)程分為6個(gè)步驟:
第1步,成簇開始時(shí),節(jié)點(diǎn)產(chǎn)生一個(gè)0~1的隨機(jī)數(shù),如果該隨機(jī)數(shù)小于某一值T時(shí),那么該節(jié)點(diǎn)成為候選簇頭。
第2步,候選簇頭根據(jù)式(5)計(jì)算自身的競(jìng)爭(zhēng)半徑并向競(jìng)爭(zhēng)半徑內(nèi)所有節(jié)點(diǎn)廣播競(jìng)選信息COMPETE-HEAD-MSG,包括節(jié)點(diǎn)的位置、競(jìng)爭(zhēng)半徑和剩余能量。
第3步,若節(jié)點(diǎn)i收到節(jié)點(diǎn)j的競(jìng)選信息,并且兩節(jié)點(diǎn)之間的距離小于兩節(jié)點(diǎn)中任意一個(gè)的競(jìng)爭(zhēng)半徑,則節(jié)點(diǎn)i就將節(jié)點(diǎn)j的競(jìng)選信息存儲(chǔ)到本地的Sct中。
第4步,一段時(shí)間后,候選簇頭將自身的剩余能量與本地Sct中各競(jìng)選信息對(duì)應(yīng)的候選簇頭的剩余能量進(jìn)行比較,如果該候選簇頭比本地Sct中任一候選簇頭的剩余能量都要大,那么該候選簇頭就成為網(wǎng)絡(luò)的實(shí)際簇頭,否則競(jìng)選失敗。然后,成為實(shí)際簇頭的節(jié)點(diǎn)向周圍廣播競(jìng)選結(jié)束信息 FINISH-ELECT-MSG。
第5步,收到結(jié)束競(jìng)選信息的非簇頭節(jié)點(diǎn),根據(jù)接收到的競(jìng)選結(jié)束信息的信號(hào)強(qiáng)度選擇加入最近的簇頭。如果某個(gè)節(jié)點(diǎn)收到多條競(jìng)選結(jié)束信息,那么它將選擇其中信號(hào)強(qiáng)度最大的簇頭作為自身的主簇頭,并選擇信號(hào)強(qiáng)度次最大的簇頭作為自身的次簇頭,成為兩相鄰簇之間的交叉節(jié)點(diǎn)。
第6步,以此類推,建立網(wǎng)絡(luò)簇類結(jié)構(gòu),如圖2所示。
圖2 LUCRA成簇結(jié)構(gòu)Fig.2 Clustering structure of LUCRA
LUCRA算法采用層間多跳通信方式進(jìn)行數(shù)據(jù)傳遞。網(wǎng)絡(luò)簇類結(jié)構(gòu)建立以后,每一個(gè)簇頭搜索并在本地保存一個(gè)相鄰簇頭的集合Gch和一個(gè)本簇內(nèi)交叉節(jié)點(diǎn)的集合Cnodes。簇內(nèi)節(jié)點(diǎn)將采集的數(shù)據(jù)直接發(fā)送給簇頭,上一層簇頭再將數(shù)據(jù)轉(zhuǎn)發(fā)給下一層的簇頭,直至數(shù)據(jù)到達(dá)基站為止。其中,在簇頭間多跳路徑構(gòu)建中,當(dāng)簇頭si選擇下一跳路徑時(shí),其轉(zhuǎn)發(fā)策略如下:①若si位于第1層,那么它就將數(shù)據(jù)直接發(fā)送給基站。②若si位于其他層中,并且si·Gch中存在下一層中的某一個(gè)簇頭sj使得d2(si,sj)+d2(sj,BS)最小,那么 si將選擇sj作為其下一跳路由。③當(dāng)si選擇sj作為下一跳路由時(shí),若d(si,sj)>DIS-MAX,那么 si搜素 si·Cnodes中是否兩者所在簇的交叉節(jié)點(diǎn),如果存在就以該交叉節(jié)點(diǎn)為橋梁進(jìn)行兩者的數(shù)據(jù)轉(zhuǎn)發(fā),若 d(si,sj)<DIS-MAX,那么 si直接將數(shù)據(jù)轉(zhuǎn)發(fā)給sj。④若si·Gch中沒(méi)有下一層的簇頭,那么si就將數(shù)據(jù)轉(zhuǎn)發(fā)給同層中距離其最近的簇頭,否則,直接將數(shù)據(jù)轉(zhuǎn)發(fā)給基站。
首先,分析LUCRA算法消息的復(fù)雜度。在成簇開始時(shí),有N×T個(gè)節(jié)點(diǎn)成為候選簇頭,需要廣播N×T條競(jìng)選消息COMPETE-HEAD-MSG。假設(shè)其中有K個(gè)節(jié)點(diǎn)當(dāng)選實(shí)際簇頭,又需要廣播K條競(jìng)選結(jié)束消息FINISH-ELECT-MSG。網(wǎng)絡(luò)成簇過(guò)程中總共需要廣播的消息開銷為N×T+K條,而EEUC算法的消息開銷為(2T+1)K條。因此,相對(duì)EEUC算法,LUCRA算法的成簇開銷比較小。還有一點(diǎn),EEUC算法需要經(jīng)過(guò)多次消息迭代才能完成簇頭的選擇,而LUCRA算法并不需要,從而它的收斂速度較快。
其次,與EEUC算法不同,LUCRA算法在競(jìng)爭(zhēng)半徑Rcmp中還考慮了節(jié)點(diǎn)的剩余能量。候選簇頭的競(jìng)爭(zhēng)半徑由候選簇頭與基站間的距離和它的剩余能量來(lái)決定。其中參數(shù)ε1、ε2決定兩者對(duì)競(jìng)爭(zhēng)半徑的影響程度,當(dāng)ε1取值為0時(shí),競(jìng)爭(zhēng)半徑的大小僅由候選簇頭的剩余能量決定;當(dāng)ε2取值為0時(shí),競(jìng)爭(zhēng)半徑的大小僅由候選簇頭與基站間的距離決定。對(duì)于不同的網(wǎng)絡(luò)規(guī)模,參數(shù)ε1、ε2的優(yōu)化取值也不同。針對(duì)文中的仿真規(guī)模,經(jīng)大量的實(shí)驗(yàn)發(fā)現(xiàn)ε1、ε2分別為0.6和0.4時(shí)網(wǎng)絡(luò)具有良好的性能。
最后,根據(jù)式(4)得到LUCRA算法,采用交叉節(jié)點(diǎn)作為簇頭間數(shù)據(jù)轉(zhuǎn)發(fā)的中介可以在一定程度上減少數(shù)據(jù)傳輸?shù)哪芰繐p耗。而且,LUCRA算法采用層間數(shù)據(jù)轉(zhuǎn)發(fā)模式,能夠極大地簡(jiǎn)化路徑尋址過(guò)程。
利用MATLAB對(duì)LUCRA算法與LEACH和EEUC算法進(jìn)行仿真比較。假設(shè)采用理想的MAC協(xié)議,并忽略無(wú)線鏈路中發(fā)生的丟包和碰撞錯(cuò)誤。仿真參數(shù)如表1所示。
表1 網(wǎng)絡(luò)仿真參數(shù)Table 1 Network simulation parameters
從實(shí)驗(yàn)數(shù)據(jù)中隨機(jī)選取15輪,統(tǒng)計(jì)每一輪所有簇頭消耗的總能量。圖3是三種分簇路由算法在每輪中所有簇頭消耗的能量之和。可見(jiàn),在簇頭能量損耗上,LEACH消耗最多、EEUC次之、LUCRA最少。這是因?yàn)長(zhǎng)UCRA和EEUC算法采用多跳通信的方式,可以有效地節(jié)省通信開銷,同時(shí),LUCRA對(duì)簇間通信進(jìn)行了改進(jìn),還避免了簇間的長(zhǎng)距離通信。
圖3 每輪所有簇頭消耗的總能量Fig.3 Total energy consumption of all cluster heads in each round
圖4是網(wǎng)絡(luò)中存活的節(jié)點(diǎn)數(shù)目隨著時(shí)間的變化。在仿真過(guò)程中,假定當(dāng)節(jié)點(diǎn)的剩余能量小于0.002 J時(shí),則認(rèn)定該節(jié)點(diǎn)死亡,當(dāng)網(wǎng)絡(luò)中有50%的節(jié)點(diǎn)死亡,則認(rèn)定網(wǎng)絡(luò)生存時(shí)間到此結(jié)束。很明顯,無(wú)論是在第一個(gè)節(jié)點(diǎn)死亡時(shí)間上還最后一個(gè)節(jié)點(diǎn)死亡時(shí)間上,LUCRA皆較EEUC和LEACH具有良好的性能表現(xiàn)。
圖4 網(wǎng)絡(luò)生存時(shí)間Fig.4 Network lifetime
筆者提出了一種基于分層的非均勻分簇路由算法LUCRA。該算法保留了EEUC算法的優(yōu)點(diǎn)并對(duì)其不足之處進(jìn)行了改進(jìn),在競(jìng)爭(zhēng)半徑的計(jì)算中同時(shí)考慮節(jié)點(diǎn)剩余能量和節(jié)點(diǎn)與基站間的距離,使得簇大小可以動(dòng)態(tài)變化。另外,LUCRA算法在簇間通信中引入交叉節(jié)點(diǎn)來(lái)作為簇頭間數(shù)據(jù)轉(zhuǎn)發(fā)的橋梁,有效減少簇頭能量損耗。最后,LUCRA算法采用從外層到內(nèi)層的路由尋址方式,實(shí)現(xiàn)過(guò)程簡(jiǎn)單、方便。實(shí)驗(yàn)表明,與LEACH、EEUC算法相比,LUCRA有效地均衡了網(wǎng)絡(luò)的系統(tǒng)能耗,顯著提高網(wǎng)絡(luò)生存時(shí)間。
[1]孫利民,李建中,陳 渝.無(wú)線傳感器網(wǎng)絡(luò)[M].北京:清華大學(xué)出版社,2005:3-96.
[2]NICULESCU D,AMERIC N L.Communication paradigms for sensor networks[J].IEEE Communication Magazine,2005,43(3):116-122.
[3]HEIZELMAN W,CHANDRAKSA A,BALAKRISHNAN H.Energy efficient communication protocol for wireless microsensor networks[C]//Proceedings of the 33rdHawaii International Conference on System Science.Washington,DC:IEEE Computer Society,2000:3005 -3014.
[4]MARCELLONI F,VECCHIO M.Enabling energy-efficient and lossy-aware data compression in wireless sensor networks by multiobjective evolutionary optimization[J].Information Sciences,2010,180(10):1924-1941.
[5]JUNG J W,INGRAM M A.Residual-energy-activated cooperative transmission to avoid the energy hole[C]//Proceedings of IEEE International Conference on Communications Workshops.Piscataway,NJ:IEEE Press,2010:1 -5.
[6]趙志信,郭繼坤,彭 保.基于功率控制的無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位算法[J].黑龍江科技學(xué)院學(xué)報(bào),2012,22(2):168-171.
[7]李成法,陳貴海,吳 杰,等.一種基于非均勻分簇的無(wú)線傳感器網(wǎng)路路由協(xié)議[J].計(jì)算機(jī)學(xué)報(bào),2007,30(1):27-36.
[8]LIAO WENHWA,KAO YUCHENG,WU RUTING.Ant colony optimization based sensor deployment protocol for wireless sensor networks[J].Expert Systems with Applications,2011,38(6):6599-6605.
[9]李志宇,史浩山.一種負(fù)載均衡的無(wú)線傳感器網(wǎng)絡(luò)自適應(yīng)分簇算法[J].西北工業(yè)大學(xué)學(xué)報(bào),2009,27(6):822-826.
[10]HE YONGGANG,XU TINGRONG.An improved uneven clustering routing algorithm for sensor networks[C]//The International Symposium on Computer Networks and Multimedia Technology.Piscataway,NJ:IEEE Press,2009:1 -5.
[11]彭 鐸,張秋余,賈科軍.能量高效地?zé)o線傳感器網(wǎng)絡(luò)分簇路由協(xié)議[J].計(jì)算機(jī)工程,2009,35(17):123-125.
[12]JUNG J W,INGRAM M A.Residual energy activated cooperative transmission to avoid the energy hole[C]//Proceedings of IEEE International Conference on Communications Workshops.Piscataway,NJ:IEEE Press,2010:1 -5.
[13]曾至文,陳志剛,劉安豐.無(wú)線傳感器網(wǎng)絡(luò)中基于可調(diào)發(fā)射功率的能量空洞避免[J].計(jì)算機(jī)學(xué)報(bào),2010,33(1):13-14.