高能量有效的基于分簇的無線傳感器網絡路由協議

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

關鍵詞:無線傳感器網絡; 路由協議; 簇; 能量有效

中圖分類號:TP393文獻標志碼: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 引言

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

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

1 LEACH協議及其存在的問題

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

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

0其他(1)

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

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

2 HEHC算法

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

根據文獻[9]，最優簇的數目是在分析每輪循環傳感器網絡消耗能量的基礎上得到的。其基本思想是選擇最優的簇數目N使得每輪循環網絡消耗的總能量最少。為了簡化算法，首先假設每個簇中的節點數目都是相等的，這樣如果傳感器網絡的節點總數為T，有N個簇，則每個簇內的傳感器節點數目為T/N。

傳感器網絡中能量消耗主要用于以下三個部分，感知數據、數據融合和通信。由文獻[10， 11]可知，通信過程中消耗的能量要遠遠高于數據融合消耗，而感知數據所需能量最少，因此，在考慮每次循環網絡所消耗的能量時，只考慮通信及數據融合所消耗的能量。由此，每輪循環中傳感器網絡的能量消耗可分為兩部分考慮，即簇首節點消耗的能量和非簇首節點消耗的能量。

本文采用文獻[9]中的能耗模型，基于以下兩個假設:

a)網絡中使用同構節點(node)。

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

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

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

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

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

ERx(k)=kEelec(3)

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

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

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

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

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

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

其中:M為傳感器網絡區域的邊長。

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

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

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

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

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

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

因此，一輪循環中傳感器網絡消耗的總能量Eround為

Eround=NEcluster(9)

式(9)最終可為

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

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

由此，可以最終確定最優的簇首節點數目Nopt，如下式所示:

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

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

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

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

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

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

其中:E為節點的初始能量。

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

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

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

3 實驗仿真及結果分析

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

表1 仿真參數設置

參數取值參數取值

ε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

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

4 結束語

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

參考文獻:

[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]沈波， 張世永，鐘亦平. 無線傳感器網絡分簇路由協議[J]. 軟件學報， 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]付華， 趙剛. 無線傳感器網絡中一種能量均衡的分簇策略[J]. 計算機應用研究， 2009， 26(4): 1494-1496.

[7]武春濤， 胡艷軍. 無線傳感器網絡LEACH算法的改進[J]. 計算機技術與發展， 2009， 19(3): 80-83.

[8]張秋余， 彭鐸， 劉洪國. 基于能量的無線傳感器網絡分簇路由算法[J]. 計算機應用研究， 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.