能量高效的無(wú)線傳感器網(wǎng)絡(luò)分簇路由協(xié)議*

賈惠麗, 范訓(xùn)禮, 呂艷峰

(西北大學(xué) 信息科學(xué)與技術(shù)學(xué)院，陜西 西安 710127)

0 引 言

如何高效利用節(jié)點(diǎn)能量并最大化網(wǎng)絡(luò)生存周期是無(wú)線傳感器網(wǎng)絡(luò)( wireless sensor networks,WSNs) 研究領(lǐng)域始終面臨的一個(gè)難點(diǎn)和實(shí)用性問(wèn)題。

文獻(xiàn)[1,2]中基于低能量自適應(yīng)聚簇分層(low energy adaptive clustering hierarchy,LEACH)協(xié)議[3]存在隨機(jī)選擇簇首(cluster head,CH)的缺點(diǎn)，引入剩余能量等因素,根據(jù)能量和距離選擇中繼節(jié)點(diǎn)，構(gòu)造簇首多跳傳輸路徑。但在選擇簇首時(shí)并未考慮節(jié)點(diǎn)的位置因素。為了優(yōu)化網(wǎng)絡(luò)節(jié)點(diǎn)分簇，提出基于K均值(K-means)聚類(lèi)的分簇路由協(xié)議[4～7]。算法在初始階段，利用K-means對(duì)節(jié)點(diǎn)進(jìn)行分簇，根據(jù)某個(gè)或多個(gè)狀態(tài)優(yōu)化簇首選擇。文獻(xiàn)[4,8]中提出基于粒子群優(yōu)化算法的分簇路由協(xié)議,但在數(shù)據(jù)傳輸時(shí)仍然采用單跳通信方式，增加網(wǎng)絡(luò)能耗。文獻(xiàn)[9,10]中基于遺傳算法優(yōu)化網(wǎng)路性能，但在選擇簇首時(shí)未考慮節(jié)點(diǎn)的剩余能量。Singh R等人[9]提出基于交叉層感知的分簇算法，但該算法仍采用LEACH協(xié)議選擇簇首，并且節(jié)點(diǎn)使用單跳模式通信，增加傳輸能耗。文獻(xiàn)[12]中提出基于ZigBee的無(wú)線傳感器網(wǎng)絡(luò)改進(jìn)，引入時(shí)間同步和碰撞避免等措施減少能量消耗。文獻(xiàn)[13,14]分別采用了數(shù)據(jù)壓縮感知，優(yōu)化分簇結(jié)構(gòu)提高感知節(jié)點(diǎn)的能量效率。

本文提出基于K-means和模糊綜合評(píng)價(jià)方法——KAF(K-means and FAH)算法，根據(jù)改進(jìn)的K-means聚類(lèi)模型，優(yōu)化分簇結(jié)構(gòu)；結(jié)合節(jié)點(diǎn)當(dāng)前狀態(tài)改進(jìn)簇首選擇方式、考慮節(jié)點(diǎn)間距離、能量、可負(fù)載能力等因素，優(yōu)化了數(shù)據(jù)傳輸時(shí)的多跳路由方式，減少傳輸能量耗費(fèi)，延長(zhǎng)網(wǎng)絡(luò)生命周期。

1 能耗模型

本文采用一階無(wú)線電能耗模型，節(jié)點(diǎn)在傳輸L-bit感知數(shù)據(jù)時(shí)的能耗計(jì)算為

(1)

(2)

節(jié)點(diǎn)接收L-bit的數(shù)據(jù)需要消耗的能量為

Erx=l×Eele

(3)

式中Eele為接收或者發(fā)送L-bit數(shù)據(jù)時(shí)電路所消耗的能量；Efs和Ems分別為自由空間信道模型及多路徑衰減模型下的放大器的功率放大倍數(shù)；d為節(jié)點(diǎn)間的物理距離

(4)

式中 (x1,y1)和(x2,y2)為兩節(jié)點(diǎn)的坐標(biāo)。

2 KAF算法

2.1 算法模型

算法中采用的網(wǎng)絡(luò)模型特點(diǎn)為：1)節(jié)點(diǎn)隨機(jī)部署在監(jiān)測(cè)環(huán)境范圍內(nèi)；2)節(jié)點(diǎn)和基站的位置固定不可移動(dòng)；3)接收方節(jié)點(diǎn)根據(jù)發(fā)送方節(jié)點(diǎn)的發(fā)射功率計(jì)算出兩者之間的距離；4)傳感器節(jié)點(diǎn)的類(lèi)型相同，具有數(shù)據(jù)融合的能力，彼此之間能夠通信且均具有唯一的編號(hào)。

2.2 簇的劃分

KAF在初始化階段，采用K-means算法對(duì)節(jié)點(diǎn)進(jìn)行分簇，為避免聚類(lèi)效果依賴(lài)于初始聚類(lèi)中心的選擇，易陷入局部最優(yōu)，引入蟻群聚類(lèi)算法優(yōu)化K-means對(duì)初始聚類(lèi)中心的選擇。此外，基本的K-means聚類(lèi)將節(jié)點(diǎn)分配給距離最近的簇，較大的傳輸距離增加了網(wǎng)絡(luò)的能耗，因此，為了使K-means更加適用于節(jié)點(diǎn)分簇，同時(shí)避免較低能量的簇首負(fù)載過(guò)重，考慮節(jié)點(diǎn)剩余能量，當(dāng)節(jié)點(diǎn)選擇簇首時(shí)，通過(guò)權(quán)值函數(shù)(式(5))優(yōu)化節(jié)點(diǎn)分簇

(5)

2.3 簇首競(jìng)爭(zhēng)

在選擇簇首時(shí)，采用模糊層次綜合評(píng)價(jià)方法，根據(jù)節(jié)點(diǎn)的當(dāng)前狀態(tài)選擇簇首。主要步驟如下：

1)根據(jù)9標(biāo)度法表構(gòu)成判斷矩陣A。

2)計(jì)算矩陣A中各行元素的乘積

(6)

3)計(jì)算Mi的n次方根，得到新的向量B

(7)

4)對(duì)向量B進(jìn)行歸一化處理，得到向量G

(8)

5)計(jì)算A和G的乘積，得到權(quán)值向量W。

6)計(jì)算最大特征值

(9)

7)對(duì)最大特征值進(jìn)行一致性檢驗(yàn)

(10)

式中RI為平均隨機(jī)一致性指標(biāo)，可查表獲取具體值;n為矩陣A的階數(shù)。

8)若計(jì)算出的CR值小于0.1，表示最后得到的權(quán)值向量W是可接受的。

9)確定簇內(nèi)節(jié)點(diǎn)的評(píng)價(jià)指標(biāo)構(gòu)成的因素集U=(u1，u2,u3,…,un),其中ui為節(jié)點(diǎn)的剩余能量、節(jié)點(diǎn)的能量效率、到基站的距離、距簇中心的距離、節(jié)點(diǎn)計(jì)算能力等評(píng)價(jià)指標(biāo)。

10)確定評(píng)價(jià)對(duì)象，即簇內(nèi)所有可能被選為CH的節(jié)點(diǎn)。根據(jù)步驟(8)確定節(jié)點(diǎn)i在評(píng)價(jià)指標(biāo)j處的值|uij|。

11)確定評(píng)價(jià)矩陣R=|rij|

(11)

式中umax,umin為所有評(píng)價(jià)對(duì)象在評(píng)價(jià)指標(biāo)j處的最大、最小值

12)由層次分析法求得的評(píng)價(jià)指標(biāo)權(quán)重，計(jì)算W×R，得到各對(duì)象的評(píng)價(jià)結(jié)果向量B，對(duì)B進(jìn)行歸一化操作，即可得到各節(jié)點(diǎn)成為簇首的概率。選擇值最大的節(jié)點(diǎn)作為簇首節(jié)點(diǎn)。

2.4 數(shù)據(jù)轉(zhuǎn)發(fā)

KAF算法采用多跳路由對(duì)節(jié)點(diǎn)的數(shù)據(jù)進(jìn)行轉(zhuǎn)發(fā)。網(wǎng)絡(luò)中，所有CH和基站(base station,BS)構(gòu)成連通無(wú)向圖。 在該無(wú)向圖中，CH與之間存在一條或多條傳輸路徑，可通過(guò)以下標(biāo)準(zhǔn)判斷最優(yōu)路徑：1)通過(guò)該條路徑所消耗的能量；2)該路徑上節(jié)點(diǎn)剩余總能量；3)該路徑到基站經(jīng)過(guò)的跳數(shù)。

最終判斷權(quán)重函數(shù)式(12)評(píng)估路徑是否為最優(yōu)

(12)

CH選擇其中一條路徑進(jìn)行傳輸數(shù)據(jù)時(shí)，根據(jù)式(12)計(jì)算路徑的適應(yīng)度值，選擇最優(yōu)路徑進(jìn)行數(shù)據(jù)轉(zhuǎn)發(fā)。

3 仿真與分析

3.1 實(shí)驗(yàn)仿真環(huán)境及參數(shù)設(shè)定

采用MATLAB平臺(tái)對(duì)KAF算法進(jìn)行仿真實(shí)驗(yàn)，并將實(shí)驗(yàn)結(jié)果與(K-means-based routing,KMR)[11]， LEACH-K(LEACH and K-means),(K-means and particle swarm optimization,KPSO)[7]，KEE(energy efficient algorithm based K-means)[10]進(jìn)行了比較。實(shí)驗(yàn)仿真環(huán)境為100 m×100 m區(qū)域中隨機(jī)分布100個(gè)感知節(jié)點(diǎn)，匯聚節(jié)點(diǎn)位于(50 m,50 m)位置，每個(gè)節(jié)點(diǎn)初始能量為0.5 J，Eele，εfs，εms分別為50 nJ/bit， 10 pJ/bit/m2， 0.001 3 pJ/bit/m4。

3.2 實(shí)驗(yàn)結(jié)果

圖1為各個(gè)算法的死亡節(jié)點(diǎn)隨著迭代次數(shù)增加時(shí)的變化趨勢(shì)。在相同時(shí)間內(nèi)LEACH-K中節(jié)點(diǎn)死亡較多。而KAF算法優(yōu)化了K-means分簇結(jié)構(gòu)和簇首生成機(jī)制，首節(jié)點(diǎn)死亡時(shí)間最遲，有效延長(zhǎng)了節(jié)點(diǎn)的生命周期。

圖1 死亡節(jié)點(diǎn)變化對(duì)比

圖2給出了各算法在進(jìn)行一定輪次數(shù)據(jù)傳輸后節(jié)點(diǎn)剩余能量的變化情況。KAF算法中，簇首根據(jù)適應(yīng)值函數(shù)選擇最優(yōu)路徑進(jìn)行數(shù)據(jù)轉(zhuǎn)發(fā)，和其他算法相比較，有效地減少了節(jié)點(diǎn)能耗。

圖2 節(jié)點(diǎn)總能量變化對(duì)比

圖3表示不同算法的網(wǎng)絡(luò)吞吐量變化趨勢(shì)。結(jié)果顯示， KAF由于節(jié)點(diǎn)能耗的減少使得基站在每輪中接收到更多的數(shù)據(jù)包，具有較高的網(wǎng)絡(luò)吞吐量。

圖3 每輪次傳送數(shù)據(jù)包的個(gè)數(shù)

圖4、圖5表明，當(dāng)基站距離監(jiān)測(cè)環(huán)境較遠(yuǎn)時(shí)，死亡節(jié)點(diǎn)和網(wǎng)絡(luò)總能量的變化趨勢(shì)。KAF中簇首根據(jù)權(quán)值函數(shù)選擇合適的路由，采用多跳轉(zhuǎn)發(fā)的方式進(jìn)行數(shù)據(jù)傳輸，有效減少了節(jié)點(diǎn)的能量消耗，節(jié)點(diǎn)具有較長(zhǎng)的生命周期。

圖4 死亡節(jié)點(diǎn)變化

圖5 網(wǎng)絡(luò)總能量變化

4 結(jié) 論

本文提出了基于分簇的KAF路由算法，擴(kuò)展了網(wǎng)絡(luò)的應(yīng)用規(guī)模，延長(zhǎng)了節(jié)點(diǎn)的生命周期，增加了網(wǎng)絡(luò)吞吐量。