基于改進蜂群算法及K均值聚類的WSN分簇路由算法

王海玲 楊俊杰

(上海電力大學電子與信息工程學院 上海 200090)

0 引 言

在當前“云大物移智”等現代信息技術和先進通信技術快速發展的背景下，無線傳感器網絡成為物聯網發展的重要支撐技術。無線傳感器網絡(Wireless Sensor Network，WSN)是由部署在監控區域內的大量具有感知、計算和通信能力的傳感節點所組成的網絡[1]，因其具有低功耗、低成本、組網靈活等優點，被廣泛應用于軍事、醫療、電力、商業、環境等領域[2]。無線傳感器網絡中傳感器節點使用電池供電，但其自身能量有限同時受節點部署環境影響，電池無法及時更換或進行能量補充，因此需要選擇合適的路由算法降低網絡能耗，延長網絡的生存時間[3]。

在當前能量高效路由算法中，基于分簇的路由算法能夠有效地延長網絡生命周期，大多分簇路由算法都借鑒了LEACH[4](Low-Energy Adaptive Clustering Hierarchy)算法的思想，簇內普通節點負責感知、從周圍環境中收集信息并發送給簇頭，簇頭負責將接收到的數據進行融合、傳輸及網絡管理[5]。LEACH是一種典型的低功耗自適應聚類路由協議，網絡每輪隨機選舉一定數量的簇頭，選舉出的簇頭收集簇間數據并以單跳形式向基站傳輸數據，由于選舉簇頭時沒有考慮節點的剩余能量，容易導致低能量節點過快地死亡。EAMMH[6](Energy Aware Multi-hop Multi-path Hierarchical)是對LEACH的改進之一，具有與LEACH相同的兩個階段，但選舉出的簇頭收集簇間數據以多跳和多路徑形式向基站傳輸數據，解決了簇內節點能耗不平衡的問題。Fuzzy C-means[7]以簇內通信距離為目標將網絡分簇。簇頭選舉時考慮簇內其他節點間的平均路徑損耗與基站路徑損耗及候選節點的剩余能量等。KUCR[8]使用K-Means算法對網絡分簇，但由于K-Means對初始聚類中心敏感，容易使分簇結果陷入局部最優，簇頭輪換時沒有考慮簇頭與其他節點的距離關系。

本文提出基于改進蜂群算法和K均值聚類的能量均衡路由(IABCKEB)算法。首先通過IABC-K(Improve ABC and K-Means)聚類算法對傳感器節點進行均勻分簇，網絡運行期間簇結構保持不變；然后在簇頭選舉時綜合考慮傳感器節點的剩余能量和綜合距離，并根據網絡狀態實時調整其權重；最后建立簇間層次路由樹確定最優通信路徑進行數據傳輸。結果證明該路由算法有效地均衡網絡能耗，明顯地延長網絡生命周期。

1 網絡與能耗模型

1.1 網絡模型

假定無線傳感器網絡具有如下性質：(1) 傳感器節點隨機部署在監測區域，位置固定；(2) 所有傳感器節點初始能量固定且相等；(3) 傳感器節點有唯一的ID，且都具有位置感知能力；(4) 傳感器節點擔任簇頭時具有數據融合去除冗余能力；(5) 基站位于監測區域中心，基站能量無限。

1.2 能耗模型

本文使用一階無線電模型[4]，當通信距離小于傳輸距離閾值時，使用自由空間信道模型，否則采用多路徑衰減模型，εfs、εmp分別為兩模型對應下的傳輸增益，Eelec為每比特數據在發送或接收時消耗的能量，EDA為節點融合每比特數據消耗的能量。節點發送k比特數據到距離d的接收節點，其所消耗的能量ETX(k,d)為：

(1)

節點接收k比特數據所消耗的能量ERX(k)為：

ERX(k)=kEelec

(2)

若節點為簇頭，則經過距離d發送k比特數據所消耗的能量ETX(k,d)為：

(3)

傳輸距離閾值d0為：

(4)

2 算法設計

2.1 簇的形成

為了降低簇頭與簇內節點通信的能量消耗，本文使用IABC-K算法對傳感節點進行分簇，成簇結果均勻并優化了簇頭與簇內節點間的距離。網絡運行期間簇結構保持不變，避免了頻繁成簇帶來的額外能量消耗。簇內普通節點與簇頭直接通信。

2.1.1最佳簇頭個數

使用IABC-K算法對傳感節點進行分簇前需要確定分簇個數，簇數太多會使數據傳輸路徑較長，造成通信時延；簇數太少會使簇內節點距離大，簇內通信能耗高。因此，最佳簇頭個數是與分簇算法相關的重要參數。為取得網絡最佳性能，利用式(5)計算最佳簇頭個數Kopt[9]。

(5)

式中：N為傳感器節點總個數；A為傳感器監測區域面積；L為傳感器節點到基站的平均距離。

2.1.2原始的K-Means算法

K-Means算法是一種經典的聚類方法[10]，假設X=(x1,x2,…,xn)為聚類樣本，xi為d維向量，k個節點的聚類中心記作K=(K1,K2,…,Kk)。

其目標函數S=(s1,s2,…,sk)為：

(6)

聚類中心坐標更新的公式為：

(7)

2.1.3人工蜂群(ABC)算法

人工蜂群(ABC)算法是模擬蜂群覓食行為的群體智能優化算法。ABC算法包括四個連續的階段：初始階段、雇傭階段、跟隨階段和偵察階段。蜂群中蜜蜂分為雇傭蜂、跟隨蜂和偵察蜂三類，其目標是尋找高質量的蜜源[11]。

算法思想為：在初始階段，首先在邊界劃定的范圍內隨機確定N個蜜源位置；在雇傭階段，雇傭蜂發現蜜源并在各蜜源附近按式(8)搜索得到新蜜源，根據新舊蜜源的適應度值更新蜜源；在跟隨階段，跟隨蜂按照式(9)計算概率選擇要跟隨的蜜源，并根據式(8)搜索得到新蜜源并選取較優蜜源；在偵察階段，當雇傭蜂連續經過若干次沒有更新蜜源，則該只雇傭蜂變成偵察蜂，并隨機尋找新蜜源。

具體算法流程如圖1所示。

圖1 人工蜂群算法流程

領域搜索公式為：

vij=xij+rij(xij-xkj)k≠i,rij∈[-1，1]

j∈{1,2,…,d},k∈{1,2,…,K}

(8)

概率計算公式：

(9)

2.1.4基于改進人工蜂群的IABC-K算法

本文對ABC算法的適應度函數fitnessj做如下改進：

fitnessj=KNj/Jjj=1,2,…,k

(10)

式中:KNj為第j類內節點的個數。

算法思想是對IABC算法和K-Means聚類兩者交替執行直到滿足最大迭代次數，IABC-K算法的偽代碼如算法1所示。

算法1IABC-K算法偽代碼

1. Load dataset

2. Set the number of employed bees and follow bees, SetMCN,LimitandK

3. Generate the initial populationxj={x1,x2,…,xK}

4. Setcycleto 1

5.Repeat

6.FOREvaluate the fitness(fi) of the population by (11)

7.FOReach employed bee {

Produce new solutionviby (9)

Calculate the valuefi

Apply greedy selection process}

8. Calculate the probability valuespifor the solutions (xi) by (10)

9.FOReach follow bee {

Select a solutionxidepending onpi

Produce new solutionvi

Calculate the valuefi

Apply greedy selection process}

10.Ifthere is an abandoned solution for the scout

Thenreplace it with a new solution which will be randomly produced

11. Using the new solutionvi

Clustering on the dataset perform once K-means iterative

12. Memorize the best solution so far

13.cycle=cycle+1

14.Untilcycle=MCN

IABC-K算法提出新的適應度函數表示為簇內節點到簇中心平均距離的倒數，當適應度越大時，簇內節點平均距離越小，簇內節點通信能耗越小。IABC-K算法同時改善了K-Means全局搜索能力差的問題，使得分簇結果比較均勻，從而網絡負載均衡。

2.2 簇頭選舉

網絡能耗主要包括所有傳感器節點數據接收的消耗、簇頭通過單跳或多跳方式到基站的數據傳輸消耗以及其他簇頭到基站的數據中繼消耗[12]。為實現網絡能耗均衡，簇頭選舉時綜合考慮傳感器節點的剩余能量和綜合距離兩個因子，并根據網絡狀態實時調整兩個因子的權重。綜合距離是指節點到基站的距離及節點與簇內其他節點之間的距離。

為實現網絡負載均衡，應盡可能使剩余能量較高的節點擔任簇頭，剩余能量因子W(Ek)為:

(11)

傳感器節點到基站的距離和節點與簇內其他節點之間的距離越小，數據傳輸的能耗也越小[13]。綜合距離因子D(vk)的計算公式為：

(12)

式中：m為節點k所在簇的節點總個數；d(k,ME)為節點k到基站的距離；d(k,j)為節點k、j之間距離。

節點根據式(13)計算自身參量Wk-ch，選擇簇內自身參量最大的節點為當前簇頭：

Wk-ch=aW(Ek)+bD(vk)

(13)

式中：a、b為權重參數，且a+b=1。

(14)

式中：E0為節點初始能量，隨著網絡的運行，權重參數a逐漸增大，節點剩余能量成為選舉簇頭的關鍵，有利于網絡負載均衡。

2.3 簇間通信

無線傳感網絡中傳感器節點的發射能耗與發射距離成正比，當簇頭與基站距離較遠時，直接通信能耗較大，所以需要選擇合適的中繼簇頭進行數據傳輸以減少簇間通信能耗[14]。本文采用文獻[9]中建立簇間層次路由樹方法,將下一跳節點的距離與剩余能量作為其是否當選為中繼節點的標準，從而避免低能量簇頭擔任過多轉發任務而過快死亡。

節點根據式(15)計算下一跳節點權值Wtr。

(15)

式中：E(t)、E(r)分別為發送數據簇頭C(t)和接收數據簇頭C(r)的剩余能量；ΔE(t)和ΔE(r)為計算出的能量消耗。

3 仿真與實驗

3.1 仿真環境

本文使用Windows平臺下的MATLAB R2014a軟件對LEACH、EAMMH和IABCKEB三種算法進行了仿真實驗，IABC-K算法中設置最大迭代次數MCN=100，控制參數Limit=20,聚類數目K=20。仿真實驗在100 m×100 m的區域內隨機部署100個傳感器節點,基站位于區域中心(50 m,50 m)，設定傳感器節點初始能量為0.1 J,數據包大小為4 000 bit，εfs為10 pJ/(bit·m2)，εmp為0.001 3 pJ/(bit·m4)，Eelec為50 nJ/bit，EDA為5 nJ/bit。

3.2 IABC-K分簇結果分析

在同一無線傳感網絡環境中，IABC-K算法、LEACH和K-Means算法的成簇結果如圖2-圖4所示。可以看出，LEACH使用隨機選舉簇頭，普通節點再入簇的成簇方法，使得成簇大小不均勻；K-Means算法使用均勻分區的方法進行分簇，但容易出現局部最優，使得成簇結果大小不一，不均勻的分簇必然會導致網絡負載不均衡[15]。IABC-K算法解決了K-Means算法出現局部最優的缺點，改進的ABC算法使得簇內節點平均距離較為合理，從而簇內節點通信能耗較小。結果證明IABC-K算法的成簇均勻性和簇間的通信距離更加合理。

圖2 LEACH成簇

圖3 K-means成簇

圖4 IABC-K成簇

3.3 生命周期及網絡能耗分析

網絡生命周期是指網絡開始運行到出現第一個死亡節點期間的運行輪數[16]。從圖5可以看出，LEACH和EAMMH算法分別在第76輪和第95輪出現第一個死亡節點，本文所提出的IABCKEB算法在第219輪時出現死亡節點；LEACH和EAMMH算法中，節點在第250輪左右時全部死亡，在IABCKEB算法中，節點在第280輪左右全部死亡。

圖5 生命周期對比

圖5表明，相比LEACH和EAMMH算法，IABCKEB算法可以明顯地延長網絡的生命周期。因為IABCKEB使用了IABC-K算法使網絡分簇更均勻；在選擇簇頭時考慮節點的綜合距離也考慮節點的剩余能量，實現負載均衡；而且通過建立簇間層次路由樹方法完成簇頭與基站之間的通信，選擇中繼節點同時考慮下一跳節點距離與剩余能量，從而避免低能量簇頭擔任過多轉發任務而過快死亡。

三種算法的網絡剩余能量比較如圖6所示。可以看出，在網絡的整個運行過程中，IABCKEB的網絡剩余能量始終是最高的，說明IABCKEB算法能明顯地降低網絡的能量消耗，這是因為IABC-K算法分簇均勻；簇頭輪換降低簇內通信能耗；簇間通信通過最優路徑進行數據傳輸，從而降低了網絡能耗。

圖6 網絡剩余能量對比

4 結 語

無線傳感器技術以低成本、可靠性高的特點成為物聯網重要組成部分[17]。為了延長無線傳感器網絡的生命周期，本文提出基于能量均衡的IABCKEB路由算法。首先通過IABC-K聚類算法對傳感器節點進行均勻分簇，網絡運行期間簇結構保持不變；然后在簇頭選舉時綜合考慮傳感器節點的剩余能量和綜合距離，并根據網絡狀態實時調整其權重；最后建立簇間層次路由樹確定最優通信路徑進行數據傳輸。仿真結果表明，IABCKEB路由算法能夠有效均衡網絡能耗，明顯地延長網絡生命周期。本文僅考慮電池能量有限的無線傳感網絡，接下來將進一步研究無線可充電傳感網絡的能量優化問題，以及充電設備的充電路徑規劃問題和大規模無線傳感網絡中多個充電設備的協同調度問題。