王 桐， 楊 磊

(哈爾濱工程大學 信息與通信工程學院，哈爾濱 150001)

0 引言

無線傳感器網(wǎng)絡(luò)(wireless sensor networks，WSN)是由大量的微型的傳感器節(jié)點構(gòu)成的，各個節(jié)點通過自組織方式構(gòu)成無線網(wǎng)絡(luò)，并以相互協(xié)作的方式感知、采集和處理網(wǎng)絡(luò)覆蓋區(qū)域內(nèi)的特定信息[1]。與傳統(tǒng)無線網(wǎng)絡(luò)不同，組成網(wǎng)絡(luò)的傳感器節(jié)點的能量有限，且通常無法進行更換。因此，在設(shè)計WSN路由算法時，需要重點考慮節(jié)點的能量效率以便盡最大可能地延長網(wǎng)絡(luò)的工作時間[2]。

近年來，在無線傳感器網(wǎng)絡(luò)中，有很多分簇路由算法被提出。為了避免簇頭過多地消耗能量和減少通信業(yè)務(wù)量，文獻[3]提出了一種低功耗自適應(yīng)分簇路由算法(low energy adaptive clustering hierarchy，LEACH)。采用循環(huán)隨機成簇方式，各節(jié)點輪流擔任簇頭，使網(wǎng)絡(luò)的能量負載均衡到各個節(jié)點上，延長了網(wǎng)絡(luò)的生存時間，但是LEACH采用單跳通信方式，簇頭與基站進行直接通信，造成簇頭的通信開銷很大。研究已表明，在數(shù)據(jù)轉(zhuǎn)發(fā)過程中簇頭和基站之間采用多跳通信方式更有利于節(jié)約能量[4]。多跳通信方式進行數(shù)據(jù)傳輸和轉(zhuǎn)發(fā)時，很容易導(dǎo)致與基站較近的簇頭因需承擔過多的轉(zhuǎn)發(fā)任務(wù)而過早的死亡，造成網(wǎng)絡(luò)能耗極不均衡，即所謂“熱區(qū)”問題[5－6]。針對該問題，文獻[7]給出了一種基于分布式的非均勻分簇算法(energy－efficient uneven clustering，EEUC)，根據(jù)候選簇頭到基站的距離遠近，從地理位置上將網(wǎng)絡(luò)分成大小不等的非均勻的簇類結(jié)構(gòu)，以便均衡簇頭的負載，但是在簇頭競選時沒有考慮節(jié)點的剩余能量，而且成簇過程中容易出現(xiàn)迭代現(xiàn)象，成簇開銷比較大。文獻[8]從部署模型上進行考慮，采用蟻群算法優(yōu)化網(wǎng)絡(luò)中各個節(jié)點的能耗問題，仿真表明，能夠延長網(wǎng)絡(luò)的生存時間，但是需要人工部署限制了其在實際環(huán)境中的應(yīng)用。文獻[9]提出了負載均衡的自適應(yīng)分簇算法，在簇頭選擇上同時考慮簇半徑、節(jié)點剩余能量和簇頭間距，并采用多跳方式進行數(shù)據(jù)通信。文獻[10]對其進行了改進，還考慮了相鄰節(jié)點的剩余能量。文獻[11]選擇剩余能量最多的節(jié)點擔任簇頭，且限制簇的規(guī)模。文獻[12]針對“熱區(qū)”問題，提出了采用剩余能量啟發(fā)合作的傳輸方式來進行數(shù)據(jù)傳輸?shù)姆椒?，以避免能量空洞。但是，上述路由算法皆沒有考慮簇間數(shù)據(jù)傳輸時的長距離通信問題。

鑒于此，筆者對EEUC算法進行改進，提出了一種基于分層的非均勻分簇路由算法(layered unequal clustering routing algorithm，LUCRA)。LUCRA 的改進之處:一是在EEUC算法的競爭半徑計算方式上引入了節(jié)點的剩余能量，以使簇頭負載更加均衡。二是改進了EEUC算法的成簇過程，避免出現(xiàn)迭代現(xiàn)象，提高了算法的收斂速度。三是通過對簇間長距離通信展開分析，建立多個層次的網(wǎng)絡(luò)結(jié)構(gòu)，并利用相鄰簇的交叉節(jié)點進行數(shù)據(jù)轉(zhuǎn)發(fā)，極大地減少了數(shù)據(jù)通信開銷，進一步延長了網(wǎng)絡(luò)的生存時間。

1 系統(tǒng)模型和問題分析

1.1 系統(tǒng)模型

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

假設(shè)無線傳感網(wǎng)絡(luò)由N個節(jié)點組成，節(jié)點分布在一個固定大小的區(qū)域內(nèi)。設(shè)第i個節(jié)點為si，則節(jié)點集 S={s1，s2，s3，…，sN－2，sN－1，sN}，|S|=N。傳感器網(wǎng)絡(luò)的應(yīng)用環(huán)境是周期性的數(shù)據(jù)采集，且具有如下性質(zhì):基站和節(jié)點部署以后不可以移動，且基站僅有一個并位于監(jiān)測區(qū)域外;所有節(jié)點具有相同的屬性和功能;節(jié)點可以根據(jù)發(fā)射接收信號的強度估算與發(fā)射源之間的相對位置;無線發(fā)射功率可控，節(jié)點能夠根據(jù)距離調(diào)整發(fā)射功率的大小。

1.1.2 無線通信模型

采用文獻[13]中使用的無線信道模型來計算節(jié)點發(fā)送和接收數(shù)據(jù)所消耗的能量。

假設(shè)節(jié)點A向節(jié)點B發(fā)送l字節(jié)的數(shù)據(jù)，兩節(jié)點間距離為d，則其能量損耗:

節(jié)點B接收l字節(jié)數(shù)據(jù)所消耗的能量為

其中，門限值d0:

式中:Eelec——發(fā)送電路和接受電路發(fā)送或接受單位比特數(shù)據(jù)消耗的能量;

εamp——信號放大器的倍數(shù);

εfsd2、εmpd4——無線電功率放大損耗。

1.2 簇間長距離通信

如圖1所示，節(jié)點A向節(jié)點C發(fā)送數(shù)據(jù)有兩種方式可以選擇，一是直接通信即從A到C;二是間接通信即從A到B再到C，其中節(jié)點B位于節(jié)點A和節(jié)點C之間。各節(jié)點之間的通信距離分別為dAB、dBC、dAC。

圖1 數(shù)據(jù)轉(zhuǎn)發(fā)Fig.1 Data forwarding

假設(shè)dAC大于 d0而 dAB、dBC小于 d0。從節(jié)點 A向節(jié)點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。當dAC在零到r之間，不等式(4)成立，即有EAC＜EABC，若dAC大于r時，不等式(4)不成立，即有EAC＞EABC。也就是說當兩節(jié)點間距離小于r時，采用直接通信比間接通信所消耗的能量要少，而當兩節(jié)點間距離大于r時，采用間接通信比直接通信所消耗的能量要少。經(jīng)估算r的值在160 m左右。因此，如果在數(shù)據(jù)轉(zhuǎn)發(fā)過程中依照此原則進行路徑選擇，就可以有效地降低網(wǎng)絡(luò)的傳輸能耗。

2 交叉非均勻分簇路由算法

LUCRA算法的整個實現(xiàn)過程包括三個部分:建立網(wǎng)絡(luò)層次結(jié)構(gòu)、簇形成和多跳傳輸。

2.1 網(wǎng)絡(luò)層次結(jié)構(gòu)

假設(shè)根據(jù)距離基站的遠近，整個傳感器網(wǎng)絡(luò)被劃分為m個層次。若以基站為原點向外輻射來對各個層次進行統(tǒng)一編號，則最內(nèi)層為第1層，最外層為第m層。層次數(shù):

式中:dmin——基站距離感知區(qū)域的最近距離;

dmax——基站距離感知區(qū)域的最遠距離。

其中，各個層次的左右邊界BLi、BRi分別為

傳感器節(jié)點部署以后，基站以一定的功率向網(wǎng)絡(luò)內(nèi)的所有節(jié)點廣播網(wǎng)絡(luò)結(jié)構(gòu)消息。各節(jié)點根據(jù)接收信號的強度和該消息所包含的各層左右邊界信息，確定自身的所屬層次，以便競選簇頭和數(shù)據(jù)傳輸時使用。

2.2 簇形成

LUCRA算法中，每個節(jié)點以一定概率成為候選節(jié)點來參與簇頭競選，競選機制采用非均勻分布的方式進行，同時將節(jié)點與基站間的距離和節(jié)點的剩余能量作為評價標準。網(wǎng)絡(luò)采用輪計數(shù)方式，每一輪開始時需要重新進行簇頭選擇。

規(guī)則 在簇頭競選過程中，若si當選簇頭，則si的競爭半徑Rcmp不允許有其他節(jié)點再成為簇頭。候選節(jié)點的競爭半徑Rcmp為

式中:dsi，BS——節(jié)點 i到基站的距離;

ε1、ε2——(0，1)之間的常數(shù);

R0——系統(tǒng)設(shè)置的成簇半徑。

從式(5)可見，節(jié)點的成簇半徑Rcmp隨著節(jié)點距基站的距離和剩余能量而動態(tài)變化，距離基站越近，剩余能量越低，成簇半徑越小。

LUCRA算法的整個成簇過程分為6個步驟:

第1步，成簇開始時，節(jié)點產(chǎn)生一個0～1的隨機數(shù)，如果該隨機數(shù)小于某一值T時，那么該節(jié)點成為候選簇頭。

第2步，候選簇頭根據(jù)式(5)計算自身的競爭半徑并向競爭半徑內(nèi)所有節(jié)點廣播競選信息COMPETE－HEAD－MSG，包括節(jié)點的位置、競爭半徑和剩余能量。

第3步，若節(jié)點i收到節(jié)點j的競選信息，并且兩節(jié)點之間的距離小于兩節(jié)點中任意一個的競爭半徑，則節(jié)點i就將節(jié)點j的競選信息存儲到本地的Sct中。

第4步，一段時間后，候選簇頭將自身的剩余能量與本地Sct中各競選信息對應(yīng)的候選簇頭的剩余能量進行比較，如果該候選簇頭比本地Sct中任一候選簇頭的剩余能量都要大，那么該候選簇頭就成為網(wǎng)絡(luò)的實際簇頭，否則競選失敗。然后，成為實際簇頭的節(jié)點向周圍廣播競選結(jié)束信息 FINISH－ELECT－MSG。

第5步，收到結(jié)束競選信息的非簇頭節(jié)點，根據(jù)接收到的競選結(jié)束信息的信號強度選擇加入最近的簇頭。如果某個節(jié)點收到多條競選結(jié)束信息，那么它將選擇其中信號強度最大的簇頭作為自身的主簇頭，并選擇信號強度次最大的簇頭作為自身的次簇頭，成為兩相鄰簇之間的交叉節(jié)點。

第6步，以此類推，建立網(wǎng)絡(luò)簇類結(jié)構(gòu)，如圖2所示。

圖2 LUCRA成簇結(jié)構(gòu)Fig.2 Clustering structure of LUCRA

2.3 多跳傳輸

LUCRA算法采用層間多跳通信方式進行數(shù)據(jù)傳遞。網(wǎng)絡(luò)簇類結(jié)構(gòu)建立以后，每一個簇頭搜索并在本地保存一個相鄰簇頭的集合Gch和一個本簇內(nèi)交叉節(jié)點的集合Cnodes。簇內(nèi)節(jié)點將采集的數(shù)據(jù)直接發(fā)送給簇頭，上一層簇頭再將數(shù)據(jù)轉(zhuǎn)發(fā)給下一層的簇頭，直至數(shù)據(jù)到達基站為止。其中，在簇頭間多跳路徑構(gòu)建中，當簇頭si選擇下一跳路徑時，其轉(zhuǎn)發(fā)策略如下:①若si位于第1層，那么它就將數(shù)據(jù)直接發(fā)送給基站。②若si位于其他層中，并且si·Gch中存在下一層中的某一個簇頭sj使得d2(si，sj)+d2(sj，BS)最小，那么 si將選擇sj作為其下一跳路由。③當si選擇sj作為下一跳路由時，若d(si，sj)＞DIS－MAX，那么 si搜素 si·Cnodes中是否兩者所在簇的交叉節(jié)點，如果存在就以該交叉節(jié)點為橋梁進行兩者的數(shù)據(jù)轉(zhuǎn)發(fā)，若 d(si，sj)＜DIS－MAX，那么 si直接將數(shù)據(jù)轉(zhuǎn)發(fā)給sj。④若si·Gch中沒有下一層的簇頭，那么si就將數(shù)據(jù)轉(zhuǎn)發(fā)給同層中距離其最近的簇頭，否則，直接將數(shù)據(jù)轉(zhuǎn)發(fā)給基站。

2.4 LUCRA算法分析

首先，分析LUCRA算法消息的復(fù)雜度。在成簇開始時，有N×T個節(jié)點成為候選簇頭，需要廣播N×T條競選消息COMPETE－HEAD－MSG。假設(shè)其中有K個節(jié)點當選實際簇頭，又需要廣播K條競選結(jié)束消息FINISH－ELECT－MSG。網(wǎng)絡(luò)成簇過程中總共需要廣播的消息開銷為N×T+K條，而EEUC算法的消息開銷為(2T+1)K條。因此，相對EEUC算法，LUCRA算法的成簇開銷比較小。還有一點，EEUC算法需要經(jīng)過多次消息迭代才能完成簇頭的選擇，而LUCRA算法并不需要，從而它的收斂速度較快。

其次，與EEUC算法不同，LUCRA算法在競爭半徑Rcmp中還考慮了節(jié)點的剩余能量。候選簇頭的競爭半徑由候選簇頭與基站間的距離和它的剩余能量來決定。其中參數(shù)ε1、ε2決定兩者對競爭半徑的影響程度，當ε1取值為0時，競爭半徑的大小僅由候選簇頭的剩余能量決定;當ε2取值為0時，競爭半徑的大小僅由候選簇頭與基站間的距離決定。對于不同的網(wǎng)絡(luò)規(guī)模，參數(shù)ε1、ε2的優(yōu)化取值也不同。針對文中的仿真規(guī)模，經(jīng)大量的實驗發(fā)現(xiàn)ε1、ε2分別為0.6和0.4時網(wǎng)絡(luò)具有良好的性能。

最后，根據(jù)式(4)得到LUCRA算法，采用交叉節(jié)點作為簇頭間數(shù)據(jù)轉(zhuǎn)發(fā)的中介可以在一定程度上減少數(shù)據(jù)傳輸?shù)哪芰繐p耗。而且，LUCRA算法采用層間數(shù)據(jù)轉(zhuǎn)發(fā)模式，能夠極大地簡化路徑尋址過程。

3 仿真及結(jié)果分析

3.1 參數(shù)設(shè)置

利用MATLAB對LUCRA算法與LEACH和EEUC算法進行仿真比較。假設(shè)采用理想的MAC協(xié)議，并忽略無線鏈路中發(fā)生的丟包和碰撞錯誤。仿真參數(shù)如表1所示。

表1 網(wǎng)絡(luò)仿真參數(shù)Table 1 Network simulation parameters

3.2 結(jié)果分析

從實驗數(shù)據(jù)中隨機選取15輪，統(tǒng)計每一輪所有簇頭消耗的總能量。圖3是三種分簇路由算法在每輪中所有簇頭消耗的能量之和?？梢姡诖仡^能量損耗上，LEACH消耗最多、EEUC次之、LUCRA最少。這是因為LUCRA和EEUC算法采用多跳通信的方式，可以有效地節(jié)省通信開銷，同時，LUCRA對簇間通信進行了改進，還避免了簇間的長距離通信。

圖3 每輪所有簇頭消耗的總能量Fig.3 Total energy consumption of all cluster heads in each round

圖4是網(wǎng)絡(luò)中存活的節(jié)點數(shù)目隨著時間的變化。在仿真過程中，假定當節(jié)點的剩余能量小于0.002 J時，則認定該節(jié)點死亡，當網(wǎng)絡(luò)中有50%的節(jié)點死亡，則認定網(wǎng)絡(luò)生存時間到此結(jié)束。很明顯，無論是在第一個節(jié)點死亡時間上還最后一個節(jié)點死亡時間上，LUCRA皆較EEUC和LEACH具有良好的性能表現(xiàn)。

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

4 結(jié)束語

筆者提出了一種基于分層的非均勻分簇路由算法LUCRA。該算法保留了EEUC算法的優(yōu)點并對其不足之處進行了改進，在競爭半徑的計算中同時考慮節(jié)點剩余能量和節(jié)點與基站間的距離，使得簇大小可以動態(tài)變化。另外，LUCRA算法在簇間通信中引入交叉節(jié)點來作為簇頭間數(shù)據(jù)轉(zhuǎn)發(fā)的橋梁，有效減少簇頭能量損耗。最后，LUCRA算法采用從外層到內(nèi)層的路由尋址方式，實現(xiàn)過程簡單、方便。實驗表明，與LEACH、EEUC算法相比，LUCRA有效地均衡了網(wǎng)絡(luò)的系統(tǒng)能耗，顯著提高網(wǎng)絡(luò)生存時間。

[1]孫利民，李建中，陳 渝.無線傳感器網(wǎng)絡(luò)[M].北京:清華大學出版社，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ǎng)絡(luò)節(jié)點定位算法[J].黑龍江科技學院學報，2012，22(2):168－171.

[7]李成法，陳貴海，吳 杰，等.一種基于非均勻分簇的無線傳感器網(wǎng)路路由協(xié)議[J].計算機學報，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]李志宇，史浩山.一種負載均衡的無線傳感器網(wǎng)絡(luò)自適應(yīng)分簇算法[J].西北工業(yè)大學學報，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]彭 鐸，張秋余，賈科軍.能量高效地無線傳感器網(wǎng)絡(luò)分簇路由協(xié)議[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ǎng)絡(luò)中基于可調(diào)發(fā)射功率的能量空洞避免[J].計算機學報，2010，33(1):13－14.