無線傳感器網絡中一種能量均衡的分簇策略

（遼寧工程技術大學 電氣與控制工程學院， 遼寧 葫蘆島 125105）

摘 要：以無線傳感器網絡中的能量消耗模型為基礎，提出了一種能量均衡的無線傳感器網絡分簇路由協議EECHS(energy-effficient cluster-head selection)。該協議通過節點的剩余能量和節點距離基站的距離來調節其成為簇首的概率，并進一步調節簇的大小。仿真結果表明，與改進后的DCHS協議相比，該策略使網絡的生命周期和穩定周期分別提高了31%和45%以上。

關鍵詞：無線傳感器網絡；能量均衡；分簇；路由協議

中圖分類號：TP393文獻標志碼：A

文章編號：1001-3695(2009)04-1494-03

Balanced-energy clustering scheme for wireless sensor networks

FU Hua，ZHAO Gang

（School of Electrical Engineering Control， Liaoning Technical University， Huludao Liaoning 125105， China）

Abstract:This paper proposed a balanced-energy clustering routing protocol，based on the energy consumption model in wireless sensor networks.This routing protocol adjusted the probability of a node to become a cluster-head，and controls the size of each cluster by using its residual energy and the distance between nodes to the base station.The simulation results show that，compared with the improved DCHS protocol，the scheme improves the network life-time and stable-time up to 31% and 45% respectively.

Key words:wireless sensor networks; energy balance; clustering; routing protocol

0 引言

在無線傳感器網絡中，節點的能量一般不能補充。因此節能成為無線傳感器網絡研究的重點內容之一。路由協議是一套將數據從源節點傳輸到目的節點的機制[1]。設計高效、節能的路由協議成為當前研究的熱點。無線傳感器網絡的路由協議可以分為平面路由協議和分層路由協議兩種。由于平面路由協議需要維持較大的路由表，占據較多的存儲空間，因而并不適合在大規模的網絡中采用。分層路由算法可以在一定程度上解決這個問題[1]。

LEACH[2]路由算法是最早提出的分層路由算法，它主要是考慮一簇內節點的能量消耗問題，其目的是延長節點的工作時間，實現節點的能量平衡。網絡周期性的選擇簇首，非簇首節點以就近原則加入相應的簇首，形成虛擬簇。LEACH協議從傳輸數據的能量和數量上進行了優化。簇首的選舉過程是：每個節點產生一個0~1之間的隨機數，如果這個數小于閾值T(n)，則該節點向周圍節點廣播它是簇頭的消息。T(n)的計算公式為

T（n）=p/[1-p(r mod 1/p)] n∈G

0otherwise(1)

其中:P是簇首占所有節點的百分比，即節點當選簇首的概率;r是目前循環進行的輪數;G是最近1/P輪中還未當選過簇首的節點集合。從T(n)可以看出，當選過簇首的節點在接下來的1/P輪循環中將不能成為簇首，剩余節點當選簇首的閾值T(n)增大，節點產生小于T(n)的隨機數的概率隨之增大，所以節點當選簇首的概率增大。P值決定了每輪產生的簇首數量，在實際應用中，最佳P值的確定是十分困難的，這與網絡規模和節點密度有關。另外，T(n)沒有考慮能量因素，這種算法必須基于兩個前提假設才能達到每個節點平均耗費能量的預期目標:a)每個節點初始能量均等;b)每個節點擔任簇首期間耗費的能量均等。然而，由于每個簇的大小以及簇首到基站的距離不一樣，前提假設b)不符合現實。

針對LEACH中T(n)計算式(1)的不足，DCHS[3]（deterministic cluster-head selection)將能量因素考慮進來，改進了T(n)的計算方法為

T(n)new=p/[1-p(r mod 1/p)] (En_current/En_max)(2)

其中：En_current表示節點的當前能量；En_max表示節點的初始能量。式(2)的改進，

En_current/En_max可以使能量消耗較低的節點優先當選簇首，避免了網絡的“盲節點”過早出現。實驗結果表明，該節點選取算法能在LEACH基礎上有效提高網絡生命周期20%~30%。式(2)的這種改進還有一個缺陷：當網絡運行了相當長一段時間之后，所有節點的當前能量En_current都變得很低，那么閾值T(n)就會變小，所有節點成為簇首的概率都大大降低，每輪當選的簇首數量減少，最終導致網絡能量耗費不均衡，網絡生命周期縮短。為此，DCHS再次改進了T(n)的計算方法為［4］

T(n)new= p/[1-p(r mod 1/p)][En_current/En_max+(rs div 1/p)(1-En_current/En_max)](3)

其中：rs表示節點連續未當選過簇首的輪次，一旦當選了簇首，rs重置為0。式(3)的改進有效地解決了式(2)的缺陷，綜合考慮了節點能量和閾值大小對簇首選取的影響，使算法更公平合理。

以上幾種算法都是簇首與基站均單跳通信。在大規模無線多跳網絡環境中，由于簇首距離基站的距離一般較遠，已有研究表明在簇首與基站之間通信時采取多跳的方式（即通過簇首組成的骨干網實現多跳路由）更有利于節約能量（如文獻[5]）。然而這種做法帶來了一個能量消耗不均衡的問題：在這種所有傳感器節點的數據都發送到基站的多對一數據傳輸模式中，靠近基站的節點由于需要轉發大量來自其他簇的數據而負擔過重，過早耗盡自身能量而失效，造成網絡分割，降低網絡存活時間，研究者稱這個問題為熱區（hot spot）問題。

本文結合無線多跳網絡的特點，在LEACH、DCHS和improved DCHS路由算法的基礎上，提出了一種新的能量均衡分簇策略EECHS。通過節點的消耗能量和節點距基站的距離，來改變節點分布區域的簇首數目，使節點能量消耗大的地區節點被選成簇首的概率增加；節點能量消耗小的地區節點被選為簇首的概率減小，相應地改變了該地區簇的大小，進而使整個網絡的能量消耗均衡，延長網絡的生命周期。

1 EECHS分簇策略

1.1 網絡模型

本文采用如下的傳感器網絡模型（圖1）：

a)所有節點初始能量相等，都有計算能力和信號處理能力，且地位平等。

b）節點的發射功率可控，節點可以根據距離來調整發射功率的大小。

c）簇內節點單跳到達簇首。研究中不考慮基站的能量消耗，假定其有充足的能量消耗。

d）節點是靜止的，每個節點都有自己的ID號。

e）各節點鏈路是對稱的。若已知對方發射功率，節點可以根據接收信號的強度RSSI計算發送者到自己的近似距離(如文獻[6])。

1.2 EECHS協議方法

本文EECHS協議的設計方法是：初始階段網絡中所有節點的能量相等，每個節點均設置初始的定時器和計數器并同時進入信道監聽狀態；然后節點向基站發布自己的ID號并根據信號強度計算自己距基站的距離。首個周期簇首根據式（12）選定，并公布其ID號。簇首選定后根據信號強度和就近原則，普通節點加入相應的簇首并算出節點距簇首的距離，以及相鄰簇首間的距離。首個周期（可由基站調整周期的大?。┕ぷ骱?，計數器隨之開始工作，簇首節點的計數器記錄所在簇的節點個數和中繼其他簇首的個數，普通節點記錄當前周期內該節點發送數據的幀數。根據計數器所得數據及1.3節中的公式可以得出該節點或簇首的剩余能量。

1.3 網絡能耗分析

采用文獻[7]中的能耗模型，發送端所耗的能量用于無線電通信和能量放大兩部分，接收端所耗的能量僅僅用于無線電通信。根據接收端和發送端的距離不同，分別使用自由空間模型和多徑衰落信道模型。若兩者之間的距離小于d0使用自由空間模型；若兩者之間距離大于d0使用多徑衰落信道模型。因此，發送一個l比特的數據包到距離為d的節點需要消耗能量為

ETX(l，d)=ETX_elec(l)+ETX_amp(l，d)=

lEelec+lεfsd2 d＜d0

lEelec+lεmpd4d＞d0(4)

其中:Eelec表示接收和發送單位比特數據時電路消耗的能量；εfs和εmp是放大器消耗的能量。接收這個數據包需要消耗的能量為

ERX(l)=ETX_elec(l)=lEelec(5)

當前簇首轉發其他簇首所消耗的能量為

Ech_ch=2(l1+l2+…ln)Eelec+(l1+l2+…ln)ε fsd2to_chd＜d0

2(l1+l2+…ln)Eelec+(l1+l2+…ln)εmpd4to_chd＞d0(6)

其中:l1為本簇首轉發第一個簇的數據包比特數；l2為本簇首轉發第二個簇的數據包比特數；ln為本簇首轉發第n個簇的數據包比特數；dto_ch為本簇首到下一簇首的距離。

假設一個簇內有n個節點，則每處理一幀數據，簇首所耗的能量為

ECH=lEelec(n-1)+lEDAn+lEelec+lεfsd2to_n+Ech_ch d＜d0

lEelec(n-1)+lEDAn+lEelec+lεmpd4to_n+Ech_chd＞d0(7)

其中：l為本簇內數據包的比特數；EDA為數據融合消耗能量的系數。而每個非簇首節點消耗的能量為

Enon_CH=lEelec+lεfsd2toCH d＜d0

lEelec+lεmpd4toCHd＞d0(8)

其中：dtoCH是非簇首節點到簇首的距離。

如果每個簇內減少x個節點，簇首消耗的能量減少為

EΔch_x=xl(Eelec+EDA)（9）

同理，如果每個簇內增加y個節點，簇首消耗的能量增加為

EΔch_y=yl(Eelec+EDA)（10）

從以上的分析可得出：為了使網絡能耗平衡，可使離基站近的區域簇變小，減少能量消耗；距離基站遠的區域簇變大，增大其能量消耗。以當前簇首只中繼一個簇首為例（圖1），通過式（6）（9）（10）得出

Ech_ch=EΔch_x+EΔfch_y（11）

其中：Ech_ch為當前簇首中繼一個簇首所耗的能量；EΔch_x為當前簇首減少x個節點所減少的能耗；EΔfch_y為被中繼簇首增加y個節點所耗能量。此時當前簇的能量消耗與被中繼簇首的能量消耗達到了平衡。

1.4 EECHS協議簇首的選擇

在改進后DCHS的基礎上對式（3）作了進一步改進，T(n)的計算式為

T(n)=p/((1-p)m mod(1/p))aEn_current/En_max+(rsdiv 1/p)(1-En_current/En_max)+(1-a)（Dmax-d）/（Dmax-Dmin）；a∈[0，1](12)

其中:P是簇首占所有節點的百分比，即節點當選簇首的概率;m是目前循環進行的輪數;En_current表示節點的當前能量，En_max表示節點的初始能量；d為節點到BS的距離，Dmax為節點到BS的最遠距離；Dmin為節點到BS的最短距離，a為[0，1]內的系數，可根據實際情況來調整。

由于每個簇的大小以及簇首到基站的距離不一樣以及節點所處的位置受各種環境的影響，每個節點在擔任簇首期間所耗的能量是不可能相等的。En_current/En_max可以使能量消耗較低的節點優先當選簇首，避免了網絡的“盲節點”過早出現；同時（Dmax-d）/（Dmax-Dmin）能夠增大了靠近BS的節點成為簇首的可能性，使離BS越近簇首越多，相應的該區域的簇變小。這樣可以很好的解決熱區問題。

2 實驗結果及分析

用MATLAB仿真EECHS協議的性能，為了方便研究，用600個節點均勻分布在R=150 m的半圓區域內?；驹诎雸A的圓心。P0設為0.1，實驗中數據包的大小為4 000 bit，a的值設為0.4，并認為節點能量降到初始能量的40％時節點失效。仿真中所用的參數如表1所示。

表1 仿真參數表

參數取值

節點初始能量0.4 J

Eelec50 nJ/bit

εfs10 pJ/bit/m2

εmp0.0013 pJ/bit/m4

E5 nJ/bit/signal

d087 m

由前面的研究可知，改進后DCHS優于LEACH和DCHS，所以用改進后的DCHS為基準來比較。圖2描述了網絡在運行這兩種算法時，節點在各輪失效的個數。從圖中可以看出，發生首個節點失效的輪數和網絡有30％的節點失效時的輪數，即比較兩種情況下網絡的穩定性和生命周期。在圖2中EECHS相對與改進后的DCHS來說把網絡的穩定周期延長了45％以上，同時把網絡的生命周期延長了31％以上。這是由于EECHS通過調節整個網絡中簇的大小，很好的平衡了各節點的網絡開消，避免過早發生“盲節點”的緣故。

圖3給出了前10輪兩種算法簇首消耗能量總和的比較，由于improved DCHS 采用的是簇首與基站之間時單跳通信的模式；而EECHS采用的是多跳路由，EECHS的簇首能量消耗要小于improved DCHS的簇首能量消耗。

圖4給出的是隨機取第50輪時，距基站不同的半圓區域內節點當選簇首的數目。從圖中可以得出EECHS協議在第50輪時隨著半徑的增加，單位平方米內簇首的數目在減少。

3 結束語

本文針對無線傳感器網絡，在理論分析的基礎上提出了一種新的分簇協議EECHS。該協議在選擇簇首上，充分地考慮了該節點的剩余能量和距離基站位置的遠近，進而使簇的大小更為合理，最終使整個網絡的能耗達到平衡。通過對實驗結果的分析，它更好地解決了多跳網絡中存在的hot spot問題，可以使網絡生命周期延長31％以上。

用接收信號強度測定節點間距離的方法，雖然符合低功率、低成本的要求，但因為電磁波的不穩定，可能產生一定的測距誤差。本文致力于設計能量高效的路由協議，未能對算法中的參數優化取值進行詳細分析。另外在簇首選定后，兩個簇首之必然存在相互干擾的情況，普通節點歸屬那一個簇首問題也有待研究。下一步工作將改進測距方法，并研究算法參數的最優取值和研究簇首的歸屬問題。

參考文獻：

［1］

李曉維，徐勇軍，任豐原.無線傳感器網絡技術[M].北京：北京理工大學出版社，2007：24，31-32.

[2]HEINZELMAN W，CHANDRAKASAN A，BALAKRISHNAN H.Energy-efficient communication protocol for wireless microsensor networks[C]//Proc of the 33rd Annual Hawaii Int’l Conf on System Sciences. Maui:IEEE Computer Society，2000:3005-3014.

[3]HANDY M J，HAASE M，TIMMERMANN D.Low energly adaptive clustering hierarchy with deterministic cluster-head selection[C]//Proc of the 4th IEEE Conf. on Mobile and Wireless Communications Networks. Stockholm: IEEE Communications Society， 2002：368-372.

［4］沈波，張世永，鐘亦平.無線傳感網絡分簇路由協議[J].軟件學報，2006，17（7）：1588-1600.

[5]LI C F，YE M，CHEN G H，et al.An energy-efficient unequal clustering mechanism for wireless sensor network[C]//Proc of the 2th IEEE International Conference on Mobile Ad hot and Sensor Systems(MASS 2005).Washington DC:IEEE Computer Society，2005:597-604.

[6]GIBSON J.The mobile communication handbook[M].Boca Raton:CRC Press，1999.

[7]HEINZELMAN W B，CHANDRAKASAN A P，BALAKRISHNAN H.An application_specific protocols architecture for wireless microsensor networks[J].IEEE Trans on Wireless Communications，2002，1(4):660-670.