楊永剛， 崔寶同

(江南大學(xué) 物聯(lián)網(wǎng)工程學(xué)院，江蘇 無(wú)錫 214122)

0 引 言

無(wú)線(xiàn)傳感器網(wǎng)絡(luò)(wireless sensor networks,WSNs)是由部署在監(jiān)測(cè)區(qū)域內(nèi)的大量微型傳感器節(jié)點(diǎn)通過(guò)無(wú)線(xiàn)通信方式形成的一個(gè)自組織的網(wǎng)絡(luò)系統(tǒng)[1]，在軍事和民用領(lǐng)域獲得廣泛應(yīng)用。無(wú)線(xiàn)傳感器網(wǎng)絡(luò)的特點(diǎn)決定網(wǎng)絡(luò)的能量受限，延長(zhǎng)網(wǎng)絡(luò)壽命和提高網(wǎng)絡(luò)利用率成了研究和應(yīng)用的關(guān)鍵，分簇正是為了解決這些問(wèn)題而引入對(duì)網(wǎng)絡(luò)分層方法的重要技術(shù)[2]。

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

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

1 量子粒子群優(yōu)化算法

(1)

其中,Q為粒子在空間某一點(diǎn)出現(xiàn)的概率。通過(guò)蒙特—卡羅隨機(jī)模擬的方法，將量子狀態(tài)轉(zhuǎn)變?yōu)槠匠顟B(tài)，并最終得到粒子的位置更新公式

(2)

(3)

(4)

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

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

(5)

其中,t為當(dāng)前迭代次數(shù)，tmax為最大迭代次數(shù)。

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

2.1 無(wú)線(xiàn)通信能耗模型

無(wú)線(xiàn)通信消耗節(jié)點(diǎn)的絕大部分的能量，本文采用與文獻(xiàn)[7]相同的無(wú)線(xiàn)通信模型。節(jié)點(diǎn)發(fā)送和接收kbit信息傳輸距離為d情況下所消耗的能量分別為

(6)

ERx(k)=kEelec.

(7)

2.2 適應(yīng)值函數(shù)確定

首先，考慮簇首的能量，因?yàn)榇厥滓却貎?nèi)節(jié)點(diǎn)消耗更多能量；其次，考慮簇頭距基站的距離，簇頭距基站越近，其與基站的通信能耗越??；最后考慮分簇的緊湊性。構(gòu)造如文獻(xiàn)[8]的適應(yīng)值函數(shù)fitness

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

(8)

(9)

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

(10)

(11)

2.3 種群適應(yīng)值方差的早熟判斷機(jī)制

為避免種群陷入局部最優(yōu)解，引入文獻(xiàn)[9]的種群適應(yīng)值方差σ2的早熟判斷機(jī)制

(12)

其中，n為種群中粒子數(shù)目，fi為第i個(gè)粒子的適應(yīng)度值，favg為目前的種群目前的平均適應(yīng)度值，f取值如下

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

(13)

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

2.4 模擬退火局部?jī)?yōu)化算法

模擬退火算法的思想最早由Metropolis N等人[10]提出，之后，Kirkpatrick S等人[11]將Metropolis準(zhǔn)則應(yīng)用到組合優(yōu)化問(wèn)題，提出了模擬退火算法。結(jié)合文獻(xiàn)[12]，并根據(jù)其在本文中的具體應(yīng)用，執(zhí)行過(guò)程可描述如下：

1)設(shè)定退火當(dāng)前溫度t為初始溫度t0，初始解x；

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

3)在溫度t下重復(fù)執(zhí)行如下操作，直至達(dá)到該溫度內(nèi)循環(huán)的終止條件：

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

b.對(duì)xj進(jìn)行Metropolis過(guò)程(為便于在混合算法中應(yīng)用模擬退火算法，文中新?tīng)顟B(tài)以均勻概率分布產(chǎn)生[13])

(14)

其中,ρ為擾動(dòng)系數(shù)，隨溫度而變化

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

(15)

其中,k為外循環(huán)當(dāng)前迭代次數(shù)(降溫次數(shù))，α,β為參數(shù)。

c.計(jì)算評(píng)價(jià)函數(shù)f(x′)和f(x)的差值Δf。若Δf≤0，則接受新?tīng)顟B(tài)x=x′,轉(zhuǎn)到(d)；若Δf>0，當(dāng)min{1,exp(-Δf/t)}>rand(0,1)，則接受新?tīng)顟B(tài)x=x′，j=j+1，重復(fù)步驟(c),否則,不接受新?tīng)顟B(tài)，j=j+1，重復(fù)步驟(c)。

d.若進(jìn)化次數(shù)小于預(yù)定最大迭代次數(shù)，令t=λ·t，其中,λ∈(0,1)，轉(zhuǎn)到步驟(c)；否則,算法結(jié)束，輸出最優(yōu)解。

2.5 混合算法流程描述

首先，確定最優(yōu)簇首數(shù)K，文獻(xiàn)[14]作者已推導(dǎo)出的最優(yōu)簇首個(gè)數(shù)Kopt的表達(dá)式

(16)

其中,N為網(wǎng)絡(luò)節(jié)點(diǎn)個(gè)數(shù)，εfs和εmp均為參數(shù)，A為網(wǎng)絡(luò)區(qū)域的邊長(zhǎng)，LBS為基站到網(wǎng)絡(luò)中心的距離。

在確定了最優(yōu)簇首數(shù)的基礎(chǔ)上，接下來(lái)運(yùn)用量子粒子群優(yōu)化算法全局搜索的策略進(jìn)行簇頭選取：

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

2)通過(guò)式(8)～式(11)計(jì)算每個(gè)粒子的適應(yīng)值，記錄Pbest和Gbest；

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

4)將粒子當(dāng)前位置適應(yīng)值與粒子個(gè)體最好位置Pbest比較，若更優(yōu)，則更新Pbest；

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

6)當(dāng)量子粒子群優(yōu)化迭代一定次數(shù)時(shí)，根據(jù)式(12)～式(13)計(jì)算種群適應(yīng)值方差σ2，若σ2

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

8)根據(jù)最接近候選簇頭位置調(diào)整粒子位置；

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

3 算法仿真與分析比較

使用Matlab對(duì)算法進(jìn)行性能分析和評(píng)估。實(shí)驗(yàn)中，隨機(jī)安放在200 m×200 m范圍內(nèi)200個(gè)節(jié)點(diǎn)，基站坐標(biāo)為(100,300)，位于網(wǎng)絡(luò)外部。節(jié)點(diǎn)的初始能量均為0.5 J，數(shù)據(jù)包長(zhǎng)度為4 000 bit，控制包頭長(zhǎng)度為100 bit；根據(jù)式(17)，簇頭數(shù)量K取6。初始化粒子數(shù)為20，權(quán)重λ1=0.4，λ2=0.2，λ3=0.4。量子粒子群的最大迭代次數(shù)為1 000，迭代700次后，進(jìn)行種群適應(yīng)值方差比較，種群適應(yīng)值方差閾值S設(shè)為0.1。模擬退火局部?jī)?yōu)化中初始溫度t0為50，外循環(huán)最大迭代次數(shù)為15，溫度冷卻系數(shù)λ為0.85。

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

圖1 簇分布情況比較

接著，本文對(duì)LEACH算法和本文提出的改進(jìn)算法關(guān)于節(jié)點(diǎn)生存時(shí)間進(jìn)行了仿真，網(wǎng)絡(luò)存活節(jié)點(diǎn)隨時(shí)間的變化曲線(xiàn)如圖2所示。第一個(gè)節(jié)點(diǎn)的死亡時(shí)間，本文算法(302輪)較LEACH(176輪)延長(zhǎng)了71.59 %；50 %節(jié)點(diǎn)死亡時(shí)間，本文算法(725輪)較LEACH(433輪)延長(zhǎng)了67.44 %。說(shuō)明本文提出的改進(jìn)算法整體的能量消耗非常均衡，避免個(gè)別節(jié)點(diǎn)因負(fù)載過(guò)度導(dǎo)致很快死亡。

圖2 網(wǎng)絡(luò)生存時(shí)間比較

需要注意的是，圖2的曲線(xiàn)還表明，改進(jìn)算法網(wǎng)絡(luò)生命周期要比LEACH算法略短，這是由于在仿真后期節(jié)點(diǎn)的能量很均衡且都接近耗盡，導(dǎo)致節(jié)點(diǎn)后期大片死亡，而LEACH后期個(gè)別節(jié)點(diǎn)仍具有較大能量，能耗不均衡，故仍能保持很長(zhǎng)一段時(shí)間。然而，無(wú)線(xiàn)傳感器網(wǎng)絡(luò)的工作是由大量節(jié)點(diǎn)協(xié)同完成的，雖然LEACH的生命周期比改進(jìn)算法的略長(zhǎng)，但是由于后期節(jié)點(diǎn)過(guò)少，整個(gè)網(wǎng)絡(luò)已經(jīng)基本沒(méi)有工作能力。

4 結(jié)束語(yǔ)

本文提出了一種基于節(jié)點(diǎn)負(fù)載均衡的無(wú)線(xiàn)傳感器網(wǎng)絡(luò)分簇算法，將每種簇頭選擇方案作為一個(gè)粒子，引入了早熟判斷機(jī)制，當(dāng)粒子群陷入早熟收斂時(shí)，利用模擬退火的概率突跳特性促使尋優(yōu)過(guò)程跳出局部極值，保證了群體的多樣性，從而找到更優(yōu)的解。仿真結(jié)果表明：此算法能夠有效均衡了節(jié)點(diǎn)負(fù)載，顯著提高了網(wǎng)絡(luò)整體性能。

參考文獻(xiàn):

[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] 湯宇時(shí),徐 楓.基于分簇算法能量?jī)?yōu)化的研究[J].計(jì)算機(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的無(wú)線(xiàn)傳感器網(wǎng)絡(luò)技能分簇協(xié)議[J].計(jì)算機(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] 張梅鳳,邵 誠(chéng),甘 勇，等.基于變異算子與模擬退火混合的人工魚(yú)群優(yōu)化算法[J].電子學(xué)報(bào),2006,34(8):1381-1385.

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

[14] 劉園莉,李臘元,盧 迪.節(jié)能的無(wú)線(xiàn)傳感器網(wǎng)絡(luò)分簇路由協(xié)議的研究[J].傳感技術(shù)學(xué)報(bào),2010,23(12):1492-1497.