無線傳感器網絡中一種節點負載均衡的分簇算法*

楊永剛， 崔寶同

(江南大學 物聯網工程學院，江蘇 無錫 214122)

0 引 言

無線傳感器網絡(wireless sensor networks,WSNs)是由部署在監測區域內的大量微型傳感器節點通過無線通信方式形成的一個自組織的網絡系統[1]，在軍事和民用領域獲得廣泛應用。無線傳感器網絡的特點決定網絡的能量受限，延長網絡壽命和提高網絡利用率成了研究和應用的關鍵，分簇正是為了解決這些問題而引入對網絡分層方法的重要技術[2]。

LEACH(low energy adaptive clustering hierarchy)[3]是最早提出的分簇路由協議，該協議循環隨機選擇簇首，將整個網絡的能量負載平均分配到每個節點上，從而降低能耗、延長網絡的生存時間。但是忽略了節點的剩余能量和位置等因素，導致簇頭發布不均衡。它的成簇思想貫穿于其后發展的許多分簇路由協議中，PEGASIS(power efficient gathe-ring in sensor information system)正是在LEACH協議的基礎上建立的路由協議[4]，該協議采用貪婪算法生成一條鏈，節點只需要與它最近的鄰居節點進行通信，能有效利用能量，大幅提高網絡的生存時間。但該協議是一條鏈式結構，從而數據傳輸延時增加，不適合實時應用。HEED (hybrid energy-efficient distributed)聚合算法綜合節點剩余能量和簇內節點通信代價對網絡生存時間的影響[5]，周期性迭代選取簇頭，有效避免了簇頭分布不均勻的問題。但是若網絡節點分布不均勻，會使節點負載不均衡。

針對與文獻[3]相似的網絡模型，本文提出了一種新的基于節點負載均衡的分簇路由協議。應用量子粒子群進行簇頭選取優化，量子粒子群優化(quantum-behaved particle swarm optimization,QPSO)算法的全局搜索性能優于標準粒子群算法，但依然容易陷入局部最優。為進一步提高收斂的速度和精度，本文將模擬退火(simulated annealing，SA)算法運用到量子粒子群中進行局部優化，新協議同時考慮了節點剩余能量、與匯聚節點的距離以及簇的范圍等因素，有效均衡節點負載，延長網絡壽命。

1 量子粒子群優化算法

(1)

其中,Q為粒子在空間某一點出現的概率。通過蒙特—卡羅隨機模擬的方法，將量子狀態轉變為平常狀態，并最終得到粒子的位置更新公式

(2)

(3)

(4)

其中,β為收縮擴張系數，M為種群所含微粒數，a,b,u均為(0,1)的隨機數，Pi為粒子當前位置，Pbest為個體極值，Gbest為全局極值，Mbest為Pbest的中間位置，±的選取由u決定，大于0.5取加;否則,取減。通常取

β=(1.0-1.5)(tmax-t)/tmax+0.5.

(5)

其中,t為當前迭代次數，tmax為最大迭代次數。

2 基于量子粒子群和模擬退火的混合算法

2.1 無線通信能耗模型

無線通信消耗節點的絕大部分的能量，本文采用與文獻[7]相同的無線通信模型。節點發送和接收kbit信息傳輸距離為d情況下所消耗的能量分別為

(6)

ERx(k)=kEelec.

(7)

2.2 適應值函數確定

首先，考慮簇首的能量，因為簇首要比簇內節點消耗更多能量；其次，考慮簇頭距基站的距離，簇頭距基站越近，其與基站的通信能耗越小；最后考慮分簇的緊湊性。構造如文獻[8]的適應值函數fitness

fitness=λ1f1+λ2f2+λ3f3,

(8)

(9)

f2=maxk=1,2,…K{d(BS,CHp,k)/d(BS,NC)},

(10)

(11)

2.3 種群適應值方差的早熟判斷機制

為避免種群陷入局部最優解，引入文獻[9]的種群適應值方差σ2的早熟判斷機制

(12)

其中，n為種群中粒子數目，fi為第i個粒子的適應度值，favg為目前的種群目前的平均適應度值，f取值如下

f=max[1,max(|fi-favg|)] ，i∈[1,n].

(13)

種群適應值方差σ2反映粒子的收斂程度。σ2越小，表示種群聚集程度越大，種群失去多樣性而陷入早熟狀態。

2.4 模擬退火局部優化算法

模擬退火算法的思想最早由Metropolis N等人[10]提出，之后，Kirkpatrick S等人[11]將Metropolis準則應用到組合優化問題，提出了模擬退火算法。結合文獻[12]，并根據其在本文中的具體應用，執行過程可描述如下：

1)設定退火當前溫度t為初始溫度t0，初始解x；

2)j=1，選取x中的第j個變量xj；

3)在溫度t下重復執行如下操作，直至達到該溫度內循環的終止條件：

a.若j>N(N為x的維數)，則j=1。

b.對xj進行Metropolis過程(為便于在混合算法中應用模擬退火算法，文中新狀態以均勻概率分布產生[13])

(14)

其中,ρ為擾動系數，隨溫度而變化

ρ=1/(k/α+β).

(15)

其中,k為外循環當前迭代次數(降溫次數)，α,β為參數。

c.計算評價函數f(x′)和f(x)的差值Δf。若Δf≤0，則接受新狀態x=x′,轉到(d)；若Δf>0，當min{1,exp(-Δf/t)}>rand(0,1)，則接受新狀態x=x′，j=j+1，重復步驟(c),否則,不接受新狀態，j=j+1，重復步驟(c)。

d.若進化次數小于預定最大迭代次數，令t=λ·t，其中,λ∈(0,1)，轉到步驟(c)；否則,算法結束，輸出最優解。

2.5 混合算法流程描述

首先，確定最優簇首數K，文獻[14]作者已推導出的最優簇首個數Kopt的表達式

(16)

其中,N為網絡節點個數，εfs和εmp均為參數，A為網絡區域的邊長，LBS為基站到網絡中心的距離。

在確定了最優簇首數的基礎上，接下來運用量子粒子群優化算法全局搜索的策略進行簇頭選取：

1)初始化M個K維的粒子，每個粒子代表一種分簇可能；

2)通過式(8)～式(11)計算每個粒子的適應值，記錄Pbest和Gbest；

3)通過式(1)～式(4)更新粒子的位置；

4)將粒子當前位置適應值與粒子個體最好位置Pbest比較，若更優，則更新Pbest；

5)將粒子當前位置適應值與種群目前搜索到的最好位置Gbest比較，若更優，則更新Gbest；

6)當量子粒子群優化迭代一定次數時，根據式(12)～式(13)計算種群適應值方差σ2，若σ2

7)對迭代產生的Gbest作為初始解，運用模擬退火算法進行局部搜索，得到高精度的最終解；

8)根據最接近候選簇頭位置調整粒子位置；

9)若未達到終止條件，返回步驟(2)；否則，算法結束，發布簇頭信息。

3 算法仿真與分析比較

使用Matlab對算法進行性能分析和評估。實驗中，隨機安放在200 m×200 m范圍內200個節點，基站坐標為(100,300)，位于網絡外部。節點的初始能量均為0.5 J，數據包長度為4 000 bit，控制包頭長度為100 bit；根據式(17)，簇頭數量K取6。初始化粒子數為20，權重λ1=0.4，λ2=0.2，λ3=0.4。量子粒子群的最大迭代次數為1 000，迭代700次后，進行種群適應值方差比較，種群適應值方差閾值S設為0.1。模擬退火局部優化中初始溫度t0為50，外循環最大迭代次數為15，溫度冷卻系數λ為0.85。

首先比較本文算法和LEACH算法的簇分布情況，圖1給出了隨機抽取一輪的簇頭分布情況，根據簇頭的分布繪制了Voronoi圖。由圖可知，LEACH中簇頭分布的隨機性導致各個簇的負載很不平衡；而本文算法的簇頭分布則是距離基站越遠簇的規模越大，有效均衡了各個簇的負載。

圖1 簇分布情況比較

接著，本文對LEACH算法和本文提出的改進算法關于節點生存時間進行了仿真，網絡存活節點隨時間的變化曲線如圖2所示。第一個節點的死亡時間，本文算法(302輪)較LEACH(176輪)延長了71.59 %；50 %節點死亡時間，本文算法(725輪)較LEACH(433輪)延長了67.44 %。說明本文提出的改進算法整體的能量消耗非常均衡，避免個別節點因負載過度導致很快死亡。

圖2 網絡生存時間比較

需要注意的是，圖2的曲線還表明，改進算法網絡生命周期要比LEACH算法略短，這是由于在仿真后期節點的能量很均衡且都接近耗盡，導致節點后期大片死亡，而LEACH后期個別節點仍具有較大能量，能耗不均衡，故仍能保持很長一段時間。然而，無線傳感器網絡的工作是由大量節點協同完成的，雖然LEACH的生命周期比改進算法的略長，但是由于后期節點過少，整個網絡已經基本沒有工作能力。

4 結束語

本文提出了一種基于節點負載均衡的無線傳感器網絡分簇算法，將每種簇頭選擇方案作為一個粒子，引入了早熟判斷機制，當粒子群陷入早熟收斂時，利用模擬退火的概率突跳特性促使尋優過程跳出局部極值，保證了群體的多樣性，從而找到更優的解。仿真結果表明：此算法能夠有效均衡了節點負載，顯著提高了網絡整體性能。

參考文獻:

[1] Akyildiz I F,Su W,Sankarasubramaniam Y,et al.A survey on sensor networks[J].IEEE Communication Magazine,2002,40(8):102-116.

[2] 湯宇時,徐 楓.基于分簇算法能量優化的研究[J].計算機仿真,2008,25(3):142-145.

[3] Heinzelman W B,Chandrakasan A P,Balakrishnan H.An application-specific protocol architecture for wireless microsensor networks[J].IEEE Transactions on Wireless Communication,2002,1(4):660-670.

[4] Linasey S,Raghavenda C S.PEGASIS:Power efficient gathering in sensor information system[C]∥Proceedings of IEEE Aerospace Conference,2002:1125-1130.

[5] Younis O,Fahmy S.Heed:A hybrid,energy-efficient,distributed clustering approach for Ad-Hoc sensor networks[J].IEEE Tran-sactions on Mobile Computing,2004,3(4):660-669.

[6] Sun J,Feng B,Xu W B.Particle swarm optimization with particles having quantum behavior[C]∥Proceedings of 2004 Congress on Evolutionary Computation，Piscataway,NJ:IEEE,2004:325-331.

[7] Heinzelman W B,Chandrakasan A P,Balakrishnan H.An application-specific protocol architecture for wireless microsensor networks[J].IEEE Transactions on Wireless Communication,2002,1(4):660-670.

[8] 蔣暢江,石為人,向 敏，等.基于PSO的無線傳感器網絡技能分簇協議[J].計算機工程,2010,36(8):15-18.

[9] Chen M,Wang T,Feng J,et al.A hybrid particle swarm optimization improved by mutative scale chaos algorithm[C]∥IEEE International Conference on Computational and Information Science,2012:321-324.

[10] Metropolis N,Rosenbluth Metal.Equation of state calculations by fast computing machines[J].Journal of Chemical Physics,1953,56(21):1087-1092.

[11] Kirkpatrick S,Jr Gelatt C D,Vecchi M P.Optimization by simulated annealing[J].Science,1983,220(11):650-671.

[12] 張梅鳳,邵 誠,甘 勇，等.基于變異算子與模擬退火混合的人工魚群優化算法[J].電子學報,2006,34(8):1381-1385.

[13] 張 穎,劉艷秋.軟計算方法[M].北京:科學出版社,2002:109-134.

[14] 劉園莉,李臘元,盧 迪.節能的無線傳感器網絡分簇路由協議的研究[J].傳感技術學報,2010,23(12):1492-1497.