高能量有效的基于分簇的無線傳感器網(wǎng)絡(luò)路由協(xié)議

摘 要:在無線傳感器網(wǎng)絡(luò)能量消耗模型的基礎(chǔ)上，分析了經(jīng)典的分簇路由算法LEACH的不足，提出了一種高能量有效的分簇路由算法(HEHC)，算法重新考慮了通信過程中的能量損耗，并依據(jù)能量因子參數(shù)優(yōu)選簇首，同時使用了分簇規(guī)模約束機(jī)制。仿真結(jié)果表明，該算法能有效地減少能量損耗，延長網(wǎng)絡(luò)的生存周期。

關(guān)鍵詞:無線傳感器網(wǎng)絡(luò); 路由協(xié)議; 簇; 能量有效

中圖分類號:TP393文獻(xiàn)標(biāo)志碼:A

文章編號:1001-3695(2010)06-2201-03

doi:10.3969/j.issn.1001-3695.2010.06.058

High energyefficient clusterbased routing protocol for WSN

DAI Shijin， LI Lemin

(Key Laboratory of Broadband Optical Fiber Transmission Communication Networks， University of Electronic Science Technology of China， Chengdu 610054， China)

Abstract:This paper analyzed the LEACH’s shortcomings， based on the energy consumption model in WSNs. It proposed a novel high energyefficient hierarchical clusterbased routing protocol (HEHC) for WSNs in the aftermentioned content. HEHC presented a new strategy of cluster heads selection and cluster formation. The simulation results show that the HEHC protocol can efficiently save the energy consumption and prolong the wireless sensor network lifetime.

Key words:wireless sensor networks(WSN); routing protocol; cluster; energyefficient

0 引言

微機(jī)電系統(tǒng)以及處理器技術(shù)、存儲技術(shù)的飛速進(jìn)步，極大地推動了價格低、功耗小、功能多的微傳感器的快速發(fā)展，從而使其能夠在微小體積內(nèi)集合了信息采集、數(shù)據(jù)處理和無線通信的能力。無線傳感器網(wǎng)絡(luò)(WSNs)由布置在觀測區(qū)域內(nèi)的成百上千的傳感器節(jié)點，通過無線Ad hoc方式自組織組成。節(jié)點之間通過無線方式進(jìn)行通信，其目的是協(xié)作地感知、采集和處理網(wǎng)絡(luò)覆蓋的地理區(qū)域中感知對象的信息，并發(fā)送給匯聚節(jié)點(sink或base station)。由于WSNs可以廣泛地應(yīng)用于國防軍事、環(huán)境監(jiān)測、交通管理、醫(yī)療衛(wèi)生、制造業(yè)、反恐抗災(zāi)等各個領(lǐng)域，受到了學(xué)術(shù)界和工業(yè)界的廣泛關(guān)注[1~3]，但由于其節(jié)點能量受限，在設(shè)計無線傳感器網(wǎng)絡(luò)路由協(xié)議時，能量有效性就成為首要的考慮因素。

無線傳感器網(wǎng)絡(luò)的路由協(xié)議按照網(wǎng)絡(luò)結(jié)構(gòu)可劃分為平面型和分級型路由協(xié)議。在平面式路由協(xié)議中，所有節(jié)點的地位是平等的，原則上不存在瓶頸問題。典型的平面路由算法有定向擴(kuò)散(directed diffusion)、SPIN(sensor protocol for information via negotiation)、Rumor Routing等。由于平面型路由協(xié)議需維持較大的路由表，可擴(kuò)展性差，不適用于較大規(guī)模的無線傳感器網(wǎng)絡(luò);分級型路由協(xié)議通過將傳感器節(jié)點組織成簇的結(jié)構(gòu)，可在一定程度上解決此類問題。文獻(xiàn)[4， 5]比較了當(dāng)前典型的分簇路由算法的特點和適用情況，其中LEACH(low energy adaptive clustering hierarchy)協(xié)議就是一種典型的考慮了優(yōu)化能量使用效率的比較成熟且常用的分級型路由算法。在LEACH算法中第一次提出了分簇的概念，同時它也是第一個提出數(shù)據(jù)融合的分簇路由算法。其成簇的思想貫穿于之后提出的大量分簇路由協(xié)議中， 如文獻(xiàn)[6~8]中提出的算法均是基于成簇的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)。

1 LEACH協(xié)議及其存在的問題

MIT的Heinzelman等人[9]提出了一種基于分簇的低能耗自適應(yīng)路由協(xié)議LEACH，算法中傳感器節(jié)點自組織成為不同的簇，每個簇中均有一個簇首節(jié)點。簇內(nèi)其他節(jié)點將感知的數(shù)據(jù)發(fā)送給本簇的簇首節(jié)點，簇首節(jié)點將數(shù)據(jù)進(jìn)行一些特定的處理(數(shù)據(jù)融合)后轉(zhuǎn)發(fā)給遠(yuǎn)端的sink節(jié)點。因此，擔(dān)任數(shù)據(jù)融合及數(shù)據(jù)轉(zhuǎn)發(fā)任務(wù)的簇首節(jié)點所消耗的能量要遠(yuǎn)高于非簇首節(jié)點的能量消耗。如果簇首節(jié)點固定不變，那這些節(jié)點的能量將很快耗盡，其簇內(nèi)的其他節(jié)點將失去與遠(yuǎn)端匯聚節(jié)點通信的能力。所以LEACH算法提出簇首隨機(jī)輪換算法以避免某些節(jié)點的能量很快耗盡。LEACH中的操作分成一次次的循環(huán)，每次循環(huán)稱之為一輪(round)，每輪由簇建立和穩(wěn)定的數(shù)據(jù)傳輸兩個階段組成。通常情況下，穩(wěn)定態(tài)持續(xù)較長的時間。在簇建立階段，每個節(jié)點自身產(chǎn)生一個0~1的隨機(jī)數(shù)，并與門限值T(n)進(jìn)行比較，小于門限值則該節(jié)點成為簇首。T(n)的計算式如下:

T(n)=p1-pr mod 1p如果n∈G

0其他(1)

其中:p為簇首節(jié)點占網(wǎng)絡(luò)中節(jié)點總數(shù)的百分比，也即節(jié)點成為簇首的概率;r為當(dāng)前循環(huán)進(jìn)行的輪數(shù);G是在最后的1/p輪循環(huán)中還未成為簇首的節(jié)點集合。由T(n)的計算公式可以得知，當(dāng)選過簇首的節(jié)點在接下的1/p輪循環(huán)中將不能成為簇首。節(jié)點成為簇首后，該簇首發(fā)出廣播消息，非簇首節(jié)點根據(jù)接收到廣播消息的信號強(qiáng)度動態(tài)地自動形成簇，簇首為其簇成員分配傳輸時隙。在穩(wěn)定的數(shù)據(jù)傳輸階段，傳感器節(jié)點持續(xù)采集監(jiān)測數(shù)據(jù)，并在其分配的通信時隙將數(shù)據(jù)傳送到簇首，其余時間傳感器節(jié)點處于休眠(sleep)狀態(tài)以節(jié)約能源。簇首接收到所有的數(shù)據(jù)后，先進(jìn)行數(shù)據(jù)融合，隨后把融合后的數(shù)據(jù)發(fā)送給匯聚節(jié)點。

在實際應(yīng)用中，最優(yōu)p值的確定是十分困難的，它與網(wǎng)絡(luò)的規(guī)模、節(jié)點密度和匯聚節(jié)點的位置等均密切相關(guān)。在理想狀況下，LEACH算法可保證各網(wǎng)絡(luò)節(jié)點均有平等的機(jī)會成為簇首，這基于以下的假設(shè):a)網(wǎng)絡(luò)中的傳感器節(jié)點為同構(gòu)，即該無線傳感器網(wǎng)絡(luò)由完全相同的傳感器節(jié)點組成(如初始能量、功能等);b)各簇首節(jié)點在擔(dān)任簇首期間消耗相同的能量。然而，由于實際成簇時每個簇大小不等，以及各簇首到基站的距離不等，從而使得條件b)很難達(dá)到。網(wǎng)絡(luò)運行一段時間后，其中有些節(jié)點的能量消耗較快，有些節(jié)點的能量消耗較慢，此時，能量較少的節(jié)點若被選為簇首，則加速了節(jié)點的死亡，將大大減少傳感器網(wǎng)絡(luò)的生存周期。

2 HEHC算法

基于LEACH協(xié)議中存在的問題，本文提出了一種高能量有效的算法HEHC。該算法從以下三個方面著手解決問題:a)結(jié)合簇建立階段通信能量損耗計算出最優(yōu)簇數(shù)目;b)設(shè)定新的簇首選擇門限從而保證剩余能量高的節(jié)點更多地?fù)?dān)任簇首工作;c)提出了一種分簇規(guī)模約束機(jī)制用于確保簇間負(fù)載均衡。

根據(jù)文獻(xiàn)[9]，最優(yōu)簇的數(shù)目是在分析每輪循環(huán)傳感器網(wǎng)絡(luò)消耗能量的基礎(chǔ)上得到的。其基本思想是選擇最優(yōu)的簇數(shù)目N使得每輪循環(huán)網(wǎng)絡(luò)消耗的總能量最少。為了簡化算法，首先假設(shè)每個簇中的節(jié)點數(shù)目都是相等的，這樣如果傳感器網(wǎng)絡(luò)的節(jié)點總數(shù)為T，有N個簇，則每個簇內(nèi)的傳感器節(jié)點數(shù)目為T/N。

傳感器網(wǎng)絡(luò)中能量消耗主要用于以下三個部分，感知數(shù)據(jù)、數(shù)據(jù)融合和通信。由文獻(xiàn)[10， 11]可知，通信過程中消耗的能量要遠(yuǎn)遠(yuǎn)高于數(shù)據(jù)融合消耗，而感知數(shù)據(jù)所需能量最少，因此，在考慮每次循環(huán)網(wǎng)絡(luò)所消耗的能量時，只考慮通信及數(shù)據(jù)融合所消耗的能量。由此，每輪循環(huán)中傳感器網(wǎng)絡(luò)的能量消耗可分為兩部分考慮，即簇首節(jié)點消耗的能量和非簇首節(jié)點消耗的能量。

本文采用文獻(xiàn)[9]中的能耗模型，基于以下兩個假設(shè):

a)網(wǎng)絡(luò)中使用同構(gòu)節(jié)點(node)。

b)無線傳感器網(wǎng)絡(luò)的無線通信信道是對稱的，也即從A到B傳輸一個消息所消耗的能量與從B到A傳輸一個消息消耗的能量相同。

根據(jù)上述能耗模型，傳感器節(jié)點(node)發(fā)送k bit信息傳輸d m距離消耗的能量ETx為

ETx(k，d)=kEelec+kεfsd2d

kEelec+kεmpd4d≥dcrossover(2)

傳感器節(jié)點接收k bit信息需要的能量為

ERx(k)=kEelec(3)

其中:Eelec是發(fā)送電路和接收電路消耗的能量;εfs、εmp分別為兩種情況下放大器功率放大所需的能量。當(dāng)傳輸距離d小于門限值dcrossover時，功率放大損耗采用自由空間模型，能量消耗與d2成正比;當(dāng)傳輸距離大于或等于門限值dcrossover時，采用多徑衰落模型，能量消耗與d4成正比。

簇首節(jié)點的能量消耗用于以下幾個方面，即建立簇時通信所需能量、接收簇內(nèi)非簇首節(jié)點數(shù)據(jù)、進(jìn)行必要的數(shù)據(jù)融合以及傳輸經(jīng)處理的數(shù)據(jù)給sink節(jié)點所需能量。經(jīng)計算，簇首節(jié)點能量消耗ECH如下所示:

ECH=k(Eelec+εfsd2toCH)+kEelec(T/N-1)+

kEDA T/N+αk(Eelec+εmpd4toBS)(4)

其中:α為數(shù)據(jù)融合系數(shù)，為計算方便，取α的值為1;EDA為單位比特數(shù)據(jù)融合所需能量;dtoCH為簇內(nèi)非簇首節(jié)點到簇首節(jié)點的距離;dtoBS為簇首節(jié)點到sink節(jié)點的距離。根據(jù)文獻(xiàn)[9]，可計算得出

E[d2toCH]=12π M2N(5)

其中:M為傳感器網(wǎng)絡(luò)區(qū)域的邊長。

非簇首節(jié)點消耗的能量EnonCH用于建立簇時通信所用以及傳輸感知到的數(shù)據(jù)，經(jīng)計算如下所示:

EnonCH=NkEelec+k(Eelec+εfsd2toBS)(6)

根據(jù)上面的公式，可以得到每輪循環(huán)中每個簇所消耗的能量Ecluster如下式所示:

Ecluster=ECH+TN-1EnonCH(7)

考慮到(T/N-1)≈T/N后，式(7)可轉(zhuǎn)換為

Ecluster=ECH+(T/N) EnonCH(8)

因此，一輪循環(huán)中傳感器網(wǎng)絡(luò)消耗的總能量Eround為

Eround=NEcluster(9)

式(9)最終可為

Eround=kEelec(2T+NT)+(T/N+1)kεfsM2/(2π) +

kEDAT+KN(Eelec+εmpd4toBS)(10)

由此，可以最終確定最優(yōu)的簇首節(jié)點數(shù)目Nopt，如下式所示:

Nopt=T2π MεfsEelec(T+1)+εmpd4toBS(11)

在確定了最優(yōu)簇數(shù)目后，傳感器網(wǎng)絡(luò)整體能量消耗將盡可能降到最低，同時在每輪循環(huán)中的能量消耗也是最小，綜合兩方面的作用將有效地提高整個網(wǎng)絡(luò)的生存周期，從而使傳感器網(wǎng)絡(luò)性能得到優(yōu)化，能更有效地監(jiān)測被控環(huán)境。

傳感器節(jié)點在自我選擇是否成為簇首節(jié)點時，本文使用了基于節(jié)點si在第r輪循環(huán)時的剩余能量Ei(r)作為參數(shù)的新的門限值Tnew(i)，從而可以保證具有更多剩余能量的節(jié)點能更多地?fù)?dān)任簇首工作，以延長網(wǎng)絡(luò)的生存周期。Tnew(i)如下所示:

Tnew(i)=NT-N×(r modTN)×Ei(r)E(r)(12)

其中:E(r)表示第r輪循環(huán)時網(wǎng)絡(luò)節(jié)點的平均能量，由于平均能量只是作為節(jié)點剩余能量的參考值，使用估計值并不會影響算法的性能。如果知道網(wǎng)絡(luò)的生存周期，就能夠近似估計網(wǎng)絡(luò)每輪循環(huán)的平均能耗。假設(shè)在理想情況下，網(wǎng)絡(luò)在每一輪循環(huán)中所消耗的能量是一樣的，即令所有的節(jié)點在幾乎相同的時刻死掉，則可以得到網(wǎng)絡(luò)生存時間的估計值R。假設(shè)每個節(jié)點均勻消耗能量，即每個節(jié)點每輪循環(huán)中消耗相同的能量，于是可計算出第r輪循環(huán)時網(wǎng)絡(luò)中每個節(jié)點的平均能量E(r)為

E(r)=E(1-r/R)(13)

其中:E為節(jié)點的初始能量。

在簇形成的過程中，HEHC算法提出了一種分簇規(guī)模的約束機(jī)制，即在簇形成階段，設(shè)置簇內(nèi)非簇首節(jié)點數(shù)目的門限值以控制簇的規(guī)模。具體流程為:在傳感網(wǎng)絡(luò)部署形成后，匯聚節(jié)點用大功率向全網(wǎng)所有傳感器節(jié)點廣播一個信號，每個節(jié)點在接收到信號后根據(jù)信號強(qiáng)度估算出其到匯聚節(jié)點的近似距離，此距離記為Dsink。在簇首選擇階段，一旦節(jié)點i當(dāng)選為簇首，其簇內(nèi)非簇首節(jié)點數(shù)目的門限值為

S(i)=[n+(Dsink-Dmin)/(Dmax-Dmin)](1/p-1)(14)

其中:Dmax和Dmin分別代表傳感節(jié)點到匯聚節(jié)點距離的最大值和最小值;n為加權(quán)因子，決定簇規(guī)模大小，本文中取n=2/3。從式(14)中可以看出，簇內(nèi)節(jié)點數(shù)目與節(jié)點到匯聚節(jié)點的距離呈線性遞增的關(guān)系，即距離sink節(jié)點近的簇規(guī)模小、數(shù)量多，遠(yuǎn)離sink節(jié)點的簇規(guī)模大、數(shù)量少。簇建立過程中，簇首按照接收到的信號強(qiáng)度決定接受哪些節(jié)點作為其簇內(nèi)節(jié)點。當(dāng)簇內(nèi)節(jié)點數(shù)達(dá)到門限值s時，簇首節(jié)點將拒絕接受新的節(jié)點成簇。這樣，就達(dá)到了控制簇規(guī)模的目的，使得簇間保持了負(fù)載均衡。

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

仿真實驗是基于筆者編寫的C代碼，并用Visual C++ 6.0軟件對實驗進(jìn)行了分析仿真，并與LEACH、LEACHE、EECHS協(xié)議進(jìn)行了對比，主要從網(wǎng)絡(luò)生存周期和簇首節(jié)點能耗兩個方面進(jìn)行了比較。仿真環(huán)境設(shè)置如下:將100個初始能量為2 J的傳感器節(jié)點隨機(jī)分布在(x=0，y=0)和(x=100，y=100)組成的正方形區(qū)域內(nèi)組成實驗用傳感器網(wǎng)絡(luò)，sink節(jié)點位于(x=50，y=175)的位置。在仿真中網(wǎng)絡(luò)拓?fù)淙鐖D1所示，設(shè)置的環(huán)境變量參數(shù)如表1所示。

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

參數(shù)取值參數(shù)取值

εfs10 pJ/bit/m3εmp0.0013 pJ/bit/m4

T100k4000 bit

M100 mDcrossover87 m

Xsink50Ysink175

EDA5 nJ/bit/signalEelec5 nJ/bit

網(wǎng)絡(luò)生存周期與剩余存活節(jié)點數(shù)的對比仿真如圖2所示。使用LEACHE、EECHS、HEHC協(xié)議，網(wǎng)絡(luò)運行的輪數(shù)分別延長了13.4%、22.1%、39.5%，HEHC算法的網(wǎng)絡(luò)生存周期最長，明顯延長了網(wǎng)絡(luò)的生存周期。圖3給出了前10輪四種算法簇首消耗總能量的比較，HEHC的簇首能量消耗明顯小于其余三種算法。由此可知，HEHC通過使用新的選取簇首門限值，結(jié)合簇建立階段通信能量損耗計算出的最優(yōu)簇數(shù)目，以及采用分簇規(guī)模約束機(jī)制可以有效節(jié)省簇首能量損耗，均衡簇間負(fù)載平衡，延長無線傳感器網(wǎng)絡(luò)的生存周期，是一種高能量有效性的路由協(xié)議。

4 結(jié)束語

本文針對無線傳感器網(wǎng)絡(luò)，在理論分析的基礎(chǔ)上提出了一種高能量有效性的基于分簇結(jié)構(gòu)的無線傳感器網(wǎng)絡(luò)路由協(xié)議HEHC。該算法結(jié)合簇建立階段通信能量損耗計算出最優(yōu)簇數(shù)目，并優(yōu)化簇首選擇策略，制定簇規(guī)模約束機(jī)制，從而形成最優(yōu)簇以節(jié)省節(jié)點能量，均衡了簇間負(fù)載。仿真結(jié)果表明，HEHC算法具有高能量有效性，能有效地延長無線傳感器網(wǎng)絡(luò)的生存周期。

參考文獻(xiàn):

[1]AKYILDIZ I F， SU W， SANKARASUBRAMANIAM Y， et al. Wireless sensor networks: a survey[J]. Computer Networks(Elsevier)， 2002， 38(4): 393-422.

[2]RAGHUNATHAN V， GANERIWAL S， SRIVASTAVA M. Emerging techniques for long lived wireless sensor networks[J]. IEEE Communications Magazine， 2006， 44(4): 108-114.

[3]DAI Shijin， JING Xiaorong， LI Lemin. Research and analysis on routing protocols for wireless sensor networks[C]//Proc of International Conference on Communications， Circuits and Systems. Hong Kong: [s.n.]， 2005: 407-411.

[4]沈波， 張世永，鐘亦平. 無線傳感器網(wǎng)絡(luò)分簇路由協(xié)議[J]. 軟件學(xué)報， 2006， 17(7): 1588-1600.

[5]JIANG Congfeng， YUAN Daomin， ZHAO Yinghui. Towards clustering algorithms in wireless sensor networks: a survey[C]//Proc of IEEE Conference on Wireless Communications and Networking Conference. Piscataway， NJ: IEEE Press，2009:2009-2014.

[6]付華， 趙剛. 無線傳感器網(wǎng)絡(luò)中一種能量均衡的分簇策略[J]. 計算機(jī)應(yīng)用研究， 2009， 26(4): 1494-1496.

[7]武春濤， 胡艷軍. 無線傳感器網(wǎng)絡(luò)LEACH算法的改進(jìn)[J]. 計算機(jī)技術(shù)與發(fā)展， 2009， 19(3): 80-83.

[8]張秋余， 彭鐸， 劉洪國. 基于能量的無線傳感器網(wǎng)絡(luò)分簇路由算法[J]. 計算機(jī)應(yīng)用研究， 2009， 26(2): 674-676.

[9]HEINZELMAN W B， CHANDRAKASAN A P， BALAKRISHNAN H. An applicationspecific protocol architecture for wireless microsensor networks[J]. IEEE Trans on Wireless Communications， 2002， 1(4): 660-670.

[10]RIEDY E J， SZEWCZYK R. Power and control in networked sensors[EB/OL]. http://www.tinyos.net/papers/cs294-8.pdf.

[11]POTTIE G J， KAISER W J. Wireless integrated network sensors[J]. Communications of the ACM， 2000， 43(5): 51-58.