鄧 鵬， 蘇 娟

(湖南大學 電氣與信息工程學院，湖南 長沙 410082)

0 引 言

如何在無線傳感器網(wǎng)絡(wireless sensor networks,WSNs)工作過程中節(jié)省能源,最大化網(wǎng)絡的生命周期,是WSNs重要的研究課題之一[1]。文獻[2]提出一種能量均衡自適應分簇算法,將節(jié)點當前的能量作為重要考慮因素,對簇頭進行自適應選擇。文獻[3]提出一種基于粒子群優(yōu)化(particle swarm optimization,PSO) 的WSNs雙簇頭分簇算法,該算法將選擇出的主副簇頭分配不同的任務,使節(jié)點達到了能量負載均勻分布。但兩文獻均存在簇頭隨機分布、直接與基站通信,使簇頭間的能耗分布不均等問題。

針對以上問題，本文利用模糊C均值(fuzzy—C means，F(xiàn)CM)聚類及WSNs雙簇頭分簇路由算法的優(yōu)點,提出了基于遺傳優(yōu)化的FCM聚類分簇與最小樹的WSNs路由協(xié)議(genetic optimization FCM clustering and minimum tree,GOFCMT)。通過遺傳算法優(yōu)化FCM使聚類算法跳出局部最優(yōu),更合理的生成簇類。采用簇內(nèi)雙簇頭策略:主簇頭接收融合簇內(nèi)節(jié)點數(shù)據(jù)并發(fā)送給副簇頭;副簇頭接收主簇頭數(shù)據(jù)并向基站發(fā)送數(shù)據(jù),均衡簇頭能耗,運用近優(yōu)最小匯聚樹算法生成副簇頭與基站的通信路徑,使得節(jié)點能耗更均衡、網(wǎng)絡生命周期更長。

1 系統(tǒng)模型

假設N個傳感器節(jié)點隨機分布在M×M區(qū)域內(nèi),基站處于該區(qū)域之外,其他基本假設如下:1)基站位置信息已知；2)所有隨機分布的節(jié)點皆為靜態(tài)節(jié)點；3)每個節(jié)點有獨立的ID號和相同的初始能量Eo；4)節(jié)點未配置GPS,但在網(wǎng)絡初始化階段,節(jié)點可以根據(jù)RSSI值計算自身與基站的距離；5)節(jié)點可以根據(jù)自身與基站的距離調(diào)整傳輸半徑。

節(jié)點無線傳輸?shù)哪芎哪Ｐ筒捎靡浑A無線電模型[4]，每k比特數(shù)據(jù)傳輸距離d所需要的能耗ETx(k,d)和接收該數(shù)據(jù)的能耗ERx(k)為

(1)

ERx(k)=kEel

(2)

2 GOFCMT

本文借鑒低功耗自適應集簇分層型協(xié)議(low-energy adaptive clustering hierarchy protocol，LEACH)的分層思想，同時針對LEACH存在隨機選擇簇頭,簇頭節(jié)點分布不均,造成簇內(nèi)數(shù)據(jù)傳輸時能量利用效率低等缺點, 提出了GOFCMT。

2.1 遺傳算法優(yōu)化FCM聚類算法

利用遺傳算法優(yōu)化FCM,使FCM跳出局部最優(yōu)[5]。遺傳算法優(yōu)化FCM聚類算法(genetic algorithm optimization FCM clustering algorithm，GAFCM)流程如圖1。

圖1 GAFCM流程

2.2 簇類的建立和數(shù)據(jù)傳輸

根據(jù)式(3)和式(4)在每個簇類里選擇節(jié)點作為主副簇頭:

1)選擇主簇頭:因為主簇頭的任務是接收融合簇內(nèi)普通節(jié)點發(fā)送的數(shù)據(jù),所以需要考慮與簇內(nèi)其他普通節(jié)點之間距離;同時也要考慮自身剩余的能量。

2)決定副簇頭節(jié)點：主要考慮副簇頭與基站的距離,以及副簇頭自身的剩余能量[6]。文獻[6]提出在選擇主副簇頭時的適應函數(shù)f1和f2如下

f1=αg1+βg2,f2=εg1+δg3，α+β=1,ε+δ=1

(3)

(4)

式中g1為節(jié)點ni的能量，使選擇的主副簇頭具有較多的能量,g2為簇內(nèi)節(jié)點到主簇頭節(jié)點平均距離的倒數(shù)，使主簇頭到簇內(nèi)節(jié)點之間的平均距離最小，m為簇內(nèi)節(jié)點的個數(shù)，CH為主簇頭;d(ni,CH)為節(jié)點ni到主簇頭節(jié)點的距離，g3為副簇頭節(jié)點到基站距離的倒數(shù)， 使副簇頭到基站節(jié)點的距離最小BS為基站，d(ni,BS)為節(jié)點ni到基站節(jié)點的距離。通過α和β可以調(diào)節(jié)g1和g2兩個因素在適應值函數(shù)f1中所占的比重,通過ε和δ可以調(diào)節(jié)g1和g3兩個因素在適應值函數(shù)f2中所占的比重。

2.3 近優(yōu)最小匯集樹思想

選出的副簇頭代表本簇類,簇類抽象為副簇頭節(jié)點,將節(jié)點相連接,且節(jié)點間的能量花費作為邊權(quán)重Cost(i,j),構(gòu)造出一個具有權(quán)重的連通圖,即G=(V,E),V為副簇頭節(jié)點和基站集合,E為簇頭間數(shù)據(jù)傳輸?shù)臋?quán)重Cost(i,j)。其計算如式(5)所示,其考慮了副簇頭間的發(fā)送能量消耗、接收能量消耗、當前剩余能量以及簇頭所代表的簇類規(guī)模大小,使得權(quán)重計算更加合理。

節(jié)點能否成為數(shù)據(jù)轉(zhuǎn)發(fā)節(jié)點,則取決于其Cost(i,j)值，當Cost(i,j)值越大時,數(shù)據(jù)轉(zhuǎn)發(fā)的概率越低[8]

(5)

式中d(i,j)為副簇頭i和j之間的距離，ETx(l,d(i,j))為副簇頭i向副簇頭j發(fā)送數(shù)據(jù)消耗的能量，ERx為副簇頭j接收副簇頭i的數(shù)據(jù)消耗的能量，ec為副簇頭當前剩余能量，a,b,c(a+b+c=1)為(0,1)之間的常量，用于調(diào)整右式中前后兩項的權(quán)重，S為副簇頭i所代表的聚類規(guī)模大小。

路由選擇算法綜合考慮了副簇頭節(jié)點剩余能量、簇頭節(jié)點之間以及簇頭與基站之間的距離、簇的規(guī)模大小,使數(shù)據(jù)傳輸路徑更加的合理,能量消耗更加均衡,提高了WSNs的健壯性,延長了網(wǎng)絡生存周期。

3 仿真與性能評估

本文為了研究基站在相同的位置下LEACH、基于K-means聚類的能耗均衡路由算法(a balanced energy consumption routing algorithm based on K-means,KBECRA)和GOFCMT算法的性能差異,在MATLAB 2010b中進行了模擬,通過仿真網(wǎng)絡的生命周期和能量消耗來驗證改進的算法的網(wǎng)絡性能。

在模擬參數(shù)設置為區(qū)域大小為200 m×200 m內(nèi)，節(jié)點數(shù)為200個，匯聚節(jié)點Sink位置為(250 m，250 m),初始能量為0.5 J，數(shù)據(jù)包長度為4 000 bit，Eel為5×10-8J,ξfs為10-11J，ξmp為1.3×10-15J，每融合比特電路能耗EDA為5×10-9J，rc為25，d0為87 m[9]。權(quán)重參數(shù)取以下值：a=0.5,b=0.3,c=0.2,δ=0.6,ε=0.4,β=0.4,α=0.6。

3.1 GAFCM算法和FCM算法目標值對比

圖2為2種算法在不同輪生成聚類的目標函數(shù)值J?？芍磧?yōu)化的FCM算法的J值隨著輪數(shù)的變化而變化,非常不穩(wěn)定,使得FCM更容易收斂到局部最優(yōu)解,所產(chǎn)生的聚類非最優(yōu),導致聚類的耗能未達到最佳,縮短網(wǎng)絡的生命周期; GOFCMT算法的J值一直非常平穩(wěn),每輪均能到達最優(yōu)目標值,當網(wǎng)絡節(jié)點量大時GOFCMT優(yōu)勢更加明顯，使得產(chǎn)生的聚類為最優(yōu),聚類的耗能達到最佳,延長網(wǎng)絡的生命周期。

圖2 2算法適應值對比

3.2 網(wǎng)絡生命周期對比

圖3為LEACH，KBECRA和GOFAR算法中WSNs生命周期對比。

圖3 算法生命周期對比

可知GOFCMT的優(yōu)勢得到充分的體現(xiàn),其首個節(jié)點死亡的時間和10 %的節(jié)點死亡的時間都遠遠遲于 LEACH和KBECRA,這是因為簇頭和基站之間的通信距離加大,簇頭單次的通信能量損耗也隨之加大,而GOFCMT將通信能耗分散給最小樹上的簇頭,減少了由此產(chǎn)生的影響，另外,從第1個節(jié)點死亡到10 %節(jié)點死亡的時間跨度表明網(wǎng)絡的能量使用高效。

3.3 能量消耗對比

圖4 為GOFCMT，KBECRA和LEACH的能量消耗，可知, GOFCMT節(jié)省了網(wǎng)絡中通信的能量消耗且使能量均勻消耗,和 KBECRA，LEACH相比,具有很明顯的節(jié)能優(yōu)勢。

圖4 算法能量消耗

4 結(jié) 論

本文提出GOFCMT,通過FCM聚類算法進行分簇,在簇內(nèi)則根據(jù)不同的適應值選擇主副簇頭,簇間由近優(yōu)最小匯聚樹實現(xiàn)簇間多跳，較好地平衡了網(wǎng)絡的能量負載,從而達到了延長網(wǎng)絡生命周期的效果,仿真實驗證明算法具有較好的性能,能達到預期效果。