能量高效的無線傳感器網絡分簇路由協議*

賈惠麗, 范訓禮, 呂艷峰

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

0 引 言

如何高效利用節點能量并最大化網絡生存周期是無線傳感器網絡( wireless sensor networks,WSNs) 研究領域始終面臨的一個難點和實用性問題。

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

本文提出基于K-means和模糊綜合評價方法——KAF(K-means and FAH)算法，根據改進的K-means聚類模型，優化分簇結構；結合節點當前狀態改進簇首選擇方式、考慮節點間距離、能量、可負載能力等因素，優化了數據傳輸時的多跳路由方式，減少傳輸能量耗費，延長網絡生命周期。

1 能耗模型

本文采用一階無線電能耗模型，節點在傳輸L-bit感知數據時的能耗計算為

(1)

(2)

節點接收L-bit的數據需要消耗的能量為

Erx=l×Eele

(3)

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

(4)

式中 (x1,y1)和(x2,y2)為兩節點的坐標。

2 KAF算法

2.1 算法模型

算法中采用的網絡模型特點為：1)節點隨機部署在監測環境范圍內；2)節點和基站的位置固定不可移動；3)接收方節點根據發送方節點的發射功率計算出兩者之間的距離；4)傳感器節點的類型相同，具有數據融合的能力，彼此之間能夠通信且均具有唯一的編號。

2.2 簇的劃分

KAF在初始化階段，采用K-means算法對節點進行分簇，為避免聚類效果依賴于初始聚類中心的選擇，易陷入局部最優，引入蟻群聚類算法優化K-means對初始聚類中心的選擇。此外，基本的K-means聚類將節點分配給距離最近的簇，較大的傳輸距離增加了網絡的能耗，因此，為了使K-means更加適用于節點分簇，同時避免較低能量的簇首負載過重，考慮節點剩余能量，當節點選擇簇首時，通過權值函數(式(5))優化節點分簇

(5)

2.3 簇首競爭

在選擇簇首時，采用模糊層次綜合評價方法，根據節點的當前狀態選擇簇首。主要步驟如下：

1)根據9標度法表構成判斷矩陣A。

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

(6)

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

(7)

4)對向量B進行歸一化處理，得到向量G

(8)

5)計算A和G的乘積，得到權值向量W。

6)計算最大特征值

(9)

7)對最大特征值進行一致性檢驗

(10)

式中RI為平均隨機一致性指標，可查表獲取具體值;n為矩陣A的階數。

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

9)確定簇內節點的評價指標構成的因素集U=(u1，u2,u3,…,un),其中ui為節點的剩余能量、節點的能量效率、到基站的距離、距簇中心的距離、節點計算能力等評價指標。

10)確定評價對象，即簇內所有可能被選為CH的節點。根據步驟(8)確定節點i在評價指標j處的值|uij|。

11)確定評價矩陣R=|rij|

(11)

式中umax,umin為所有評價對象在評價指標j處的最大、最小值

12)由層次分析法求得的評價指標權重，計算W×R，得到各對象的評價結果向量B，對B進行歸一化操作，即可得到各節點成為簇首的概率。選擇值最大的節點作為簇首節點。

2.4 數據轉發

KAF算法采用多跳路由對節點的數據進行轉發。網絡中，所有CH和基站(base station,BS)構成連通無向圖。 在該無向圖中，CH與之間存在一條或多條傳輸路徑，可通過以下標準判斷最優路徑：1)通過該條路徑所消耗的能量；2)該路徑上節點剩余總能量；3)該路徑到基站經過的跳數。

最終判斷權重函數式(12)評估路徑是否為最優

(12)

CH選擇其中一條路徑進行傳輸數據時，根據式(12)計算路徑的適應度值，選擇最優路徑進行數據轉發。

3 仿真與分析

3.1 實驗仿真環境及參數設定

采用MATLAB平臺對KAF算法進行仿真實驗，并將實驗結果與(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]進行了比較。實驗仿真環境為100 m×100 m區域中隨機分布100個感知節點，匯聚節點位于(50 m,50 m)位置，每個節點初始能量為0.5 J，Eele，εfs，εms分別為50 nJ/bit， 10 pJ/bit/m2， 0.001 3 pJ/bit/m4。

3.2 實驗結果

圖1為各個算法的死亡節點隨著迭代次數增加時的變化趨勢。在相同時間內LEACH-K中節點死亡較多。而KAF算法優化了K-means分簇結構和簇首生成機制，首節點死亡時間最遲，有效延長了節點的生命周期。

圖1 死亡節點變化對比

圖2給出了各算法在進行一定輪次數據傳輸后節點剩余能量的變化情況。KAF算法中，簇首根據適應值函數選擇最優路徑進行數據轉發，和其他算法相比較，有效地減少了節點能耗。

圖2 節點總能量變化對比

圖3表示不同算法的網絡吞吐量變化趨勢。結果顯示， KAF由于節點能耗的減少使得基站在每輪中接收到更多的數據包，具有較高的網絡吞吐量。

圖3 每輪次傳送數據包的個數

圖4、圖5表明，當基站距離監測環境較遠時，死亡節點和網絡總能量的變化趨勢。KAF中簇首根據權值函數選擇合適的路由，采用多跳轉發的方式進行數據傳輸，有效減少了節點的能量消耗，節點具有較長的生命周期。

圖4 死亡節點變化

圖5 網絡總能量變化

4 結 論

本文提出了基于分簇的KAF路由算法，擴展了網絡的應用規模，延長了節點的生命周期，增加了網絡吞吐量。