基于k-means分簇和灰狼優化的無線傳感網絡路由算法

富立琪，王華倩，喬學工

（1.太原理工大學信息與計算機學院，山西晉中 030600；2.國網北京昌平供電公司，北京 102200）

無線傳感網絡(Wireless Sensor Networks,WSN)集成了傳感器技術、計算機技術和無線通信技術等多方面技術，是目前學術界研究的熱點之一[1]。由于傳感器節點的能量有限且無法更換，因此延長傳感器節點和整個網絡生存時間成為了當前領域中的一個熱門研究課題。

文獻[2]中提出的算法由于將監測區域中的節點采用貪心算法形成地理位置上的鏈，并進行數據融合和傳輸，因此該算法較為復雜，存在網絡負載不均衡的問題。文獻[3]采用簇半徑動態確定方式，將監測區域劃分成不同的簇，該算法并未解決簇首分布不均勻的問題，造成節點過早死亡。文獻[4]和文獻[5]分別對簇首選擇的方式和數據傳輸路徑進行了改進，但都未考慮節點與匯聚節點的距離，導致部分節點過早死亡，網絡負載不均衡。文獻[6]雖使用了遺傳算法選擇最優路徑進行傳輸，但該算法計算冗余，計算時延大。文獻[7]將監測區域劃分為4個象限，將節點能量和與匯聚節點的距離作為在LEACH 協議上改進簇首選擇的重要因素。文獻[8]采用k-means 算法劃分簇，并引入休眠機制。但由于k-means 算法形成的簇分布不均勻，會有節點能量消耗過快的問題產生。文獻[9]中采用了聚類評估指標優化簇首數量，該算法在簇首選舉時未考慮節點位置，會導致簇首節點由于能量消耗過快而過早死亡。文獻[10]中提出了k-means 分簇路由算法（KEAC），但“熱區”的問題較為嚴重。為了改進上述算法的不足，文中提出了一種基于k-means分簇和灰狼優化的無線傳感網絡路由算法，該算法引入基于節點的位置和分布密度兩個因素的競爭半徑模型，優化k-means 算法形成的簇，并用改進灰狼優化算法在優化后的簇區域中選取簇首，監測區域內的節點將采用簇內單跳、簇間多跳的傳輸方式將數據發送給匯聚節點。文中使用Matlab對LEACH協議、KEAC 協議以及提出的算法進行仿真，結果表明，改進后的路由算法在延長網絡的生存時間上有明顯提高。

1 網絡模型

在M×M的監測區域內，m個傳感器節點隨機分布，且節點部署后不會移動，每個節點具有相同且有限的能量和唯一的ID；匯聚節點在監測區域外，具有固定的位置和無限能量。監測區域內的每個節點具有一樣的接收、發送和數據處理能力，可感知自己的位置信息；下一跳節點限定在靠近匯聚節點的區域內。

文中引用經典的一階無線電模型[11-12]來計算節點的通信能耗，當傳輸距離為d時，節點發送lbit 數據所要消耗的能量如式（1）所示：

式（1）中，Eelec為發射電路中的能耗，εfs為自由空間模型功率放大能耗，εmp為多徑衰減模型功率放大能耗[13]，兩個參數的距離轉換閾值為

節點接收lbit 數據所要消耗的能量如式（2）所示：

2 改進灰狼優化算法

灰狼優化算法（GWO）具有結構簡單、需要調節的參數少、收斂性能較強、容易實現等優勢[14]。算法將灰狼社會進行數學建模，最優解定義為α狼，優解定義為β狼，次優解定義為δ狼，其余的解定義為χ狼。狩獵時灰狼群體接近并包圍獵物，其表達式為：

式（3）和式（4）中，t表示當前迭代次數，XP(t)是獵物位置，X(t)是灰狼位置，D表示灰狼與獵物的距離，A和C為系數，分別由式（5）和式（6）計算求出：

r1和r2是[0,1]之間的隨機數；收斂因子a隨迭代次數從2 減小到0。參數C的隨機選取避免了算法陷入局部最優，提高了整個迭代過程中的全局搜索能力。在追捕獵物階段，算法進行迭代并不斷更新α狼、β狼及δ狼的位置，同時強迫其他灰狼個體更新位置，逐漸逼近獵物，因此，χ狼根據α狼的當前位置Xα、β狼的當前位置Xβ、δ狼的當前位置Xδ來更新各自的位置，式（7）表示χ狼朝α、β、δ狼前進的步長和方向，式（8）為χ狼的最終位置：

在包圍攻擊階段時，灰狼群體逐漸向獵物靠近，隨著迭代次數的增大，收斂因子a線性減小，A的值也隨著a的減小而減小，當 |A|≤1 時，灰狼群向著獵物攻擊，以實現局部搜索，當|A|>1 時，灰狼會進行全局搜索。

由于灰狼優化算法在搜索過程中是非線性變化的，而在迭代過程中收斂因子a是線性遞減的，與算法的實際搜索過程不符合，同時文中要求算法在局部開發時能夠有較強的收斂精度，所以為了提高算法后期局部的開發能力，并有效提高算法的全局探索和局部開發平衡能力，文中改進了一種基于非線性動態變化收斂因子的更新公式，如式（9）所示：

式（9）中，ainitial和afinal分別為a的初始值和終值，t為當前迭代次數，tmax為最大迭代次數，μ為非線性調制指數，文中μ取1.1。在整個迭代過程中，調整參數a的自適應值來平衡灰狼算法的全局探索和局部開發能力，加強后期的局部開發能力。由于改進后的灰狼優化算法提高了局部搜索能力，因此在利用改進后的灰狼優化算法對簇首進行選舉時，選舉簇首更加準確快速，進而延長了網絡的生存周期。

3 基于k-means分簇和灰狼優化的路由算法

文中提出的路由算法主要分為3 個階段：第一階段為k-means 分簇優化階段，根據節點與匯聚節點的距離和節點密度兩個因素來優化k-means 聚類后所形成的簇結構，使得靠近匯聚節點的簇區域較小，避免“熱區”問題的產生；第二階段為簇首選舉階段，利用改進灰狼優化算法在各簇區域內進行簇首的選擇，均衡網絡負載；第三階段為數據傳輸階段，簇內節點以單跳的傳輸方式向簇首發送數據，簇首以多跳的傳輸方式匯聚節點發送數據，從而均衡網絡能耗。

3.1 k-means分簇

1）k-means 算法分簇時首先給定一個k值，即劃分的簇的數量，然后在每個簇中選舉一個簇首節點。為了降低整個網絡能耗，文中采取文獻[15]和文獻[16]方法確定最佳簇首數量。假設m個節點隨機分布在M×M的監測區域內，監測區域被劃分為k個簇，其中一個簇有mi（1 ≤i≤k）個節點，包含一個簇首節點和mi-1 個普通節點，匯聚節點位置距離監測區域較遠。根據上述網絡能耗模型計算簇首數目的最佳值。簇內節點通過單跳向簇首發送數據所消耗的能量為：

式（10）中，L為數據包大小，dtoCH是簇內節點到簇首節點距離的期望值；

簇首接收簇內節點數據，將數據融合后傳輸給匯聚節點所消耗的能量為：

式（11）中，dtoBS是簇首節點到匯聚節點距離的期望值，EDA是節點融合1 bit 數據所消耗的能量，mi是簇內節點數。整個網絡節點在一輪中所消耗的總能量為：

式（12）中，N（1 ≤N≤m）為當前輪數的存活節點個數。

對式（12）求解k的偏導數，可以得到最低能耗時的k值，即=0，最佳的簇首數量為：

2）根據式（13）求出的最佳簇首數量，令k=kopt，即匯聚節點從m個節點對象中隨機選擇k個節點作為初始聚類中心，計算其他非聚類中心的節點與每個聚類中心的距離，并將節點分配到距離聚類中心最近的簇中。

3）節點分配完畢后，用式（14）重新計算每個簇中所有節點的質心；第i個簇中的質心表示為centeri(xi,yi)。

式（14）中的xj、yj分別為節點j的橫坐標和縱坐標。

4）重復步驟2）和3），直到每次計算出來的質心與原來質心的距離小于設置的閾值（設為0.01）時算法結束，將此時的簇作為初始形成的簇。

由于k-means 算法形成的簇分布不均勻，而且靠近匯聚節點的簇可能會有“熱區”的問題存在，導致簇首節點過早死亡。為了避免這些問題，文中將引入非均勻競爭半徑對初始形成的簇進行優化，使得距離匯聚節點近的簇具有的競爭半徑較小，距離匯聚節點遠的簇具有的競爭半徑較大，簇內的節點數也較少，均衡節點能耗，從而延長網絡生命周期。第i個簇質心centeri的競爭半徑為Ri：

式（15）中的Rmax為最大競爭半徑，和為分別為k個簇的質心到匯聚節點距離的最大值和最小值，di-BS為第i個簇的質心到匯聚節點的距離，λ1、λ2為權重，取值在[0,1]之 間。和分別為k個簇內節點密度的最大值和最小值，densityi為第i個簇內密度。

第i個簇內的簇質心競爭半徑內的節點數為mRi，競爭半徑內節點滿足的條件為表示第i個簇中第j個節點到簇質心的距離，當<φ時，該簇存在“熱區”問題，對該簇結構進行優化，具體過程如下：

①設第i個簇內節點集合為Wi={wi1,wi2,…,wimi}，簇內距離最遠的兩個節點為wi1(xi1,yi1)、wi2(xi2,yi2)，簇質心為centeri(xi,yi)；

②根據式（16）、（17）分別計算wavg1和wavg2，分別以wavg1(xavg1,yavg1)，wavg2(xavg2,yavg2)作為新的聚類中心，將節點分配到距離新聚類中心最近的簇中：

分配完成后，監測區域內的節點最終劃分成了k+z個簇，z為優化后所增加簇的個數。

3.2 簇首選舉

KEAC 協議在簇首選舉時沒有考慮節點的能量和位置，部分簇首在數據傳輸時能量消耗較大，導致簇首節點過早死亡，使得整個網絡能量消耗不均衡，因此文中提出的算法將綜合考慮節點剩余能量、節點與簇質心的距離和節點密度3 個因素，并采用改進的灰狼優化算法選舉簇首，使簇首選擇更加合理，從而均衡網絡能耗。每個簇內節點的坐標值為改進灰狼優化算法中灰狼個體的初始值，具體過程如下：

步驟1：初始化灰狼種群，t為當前迭代次數，mi為種群大小，即每個簇中的節點數量，每個簇內的節點為灰狼個體，初始化a、A和C；初始化Xα、Xβ和Xδ的值。

步驟2：根據適應度函數計算每只灰狼個體所對應的適應度函數值。適應度函數設置如式（18）所示：

步驟3：比較灰狼個體的適應度函數值，將適應度函數值從大到小排列，排在第一位為最優解Xα，排在第二位為優解Xβ，排在第三位為次優解Xδ。

步驟4：搜索位置更新，根據式（5）～（9）更新當前灰狼個體位置。

步驟5：計算灰狼個體的適應度函數值，更新α、β、δ灰狼個體的位置，令t=t+1。

步驟6：若t>tmax，tmax為最大迭代次數，停止搜索，否則轉到步驟2。

步驟7：輸出最優解，最優解所對應灰狼個體的節點就是通過選舉而得到的簇首。

3.3 數據傳輸

數據傳輸階段分為簇內傳輸和簇間傳輸兩個部分。簇內的每個普通節點利用單跳傳輸方式向簇首發送自己采集到的數據，然后簇首將節點發送過來的數據進行融合，在簇間數據傳輸時，將通信半徑范圍里與匯聚節點距離最小的節點作為下一跳節點，若簇首到下一跳節點的距離大于簇首到匯聚節點的距離，那么簇首將數據直接發送給匯聚節點，以避免產生多余的能量消耗，從而均衡網絡負載，延長網絡的生存周期。

4 實驗設置與結果分析

為了驗證文中提出的基于k-means 分簇和灰狼優化的無線傳感網絡路由算法的性能，將其與經典的LEACH 協議和KEAC 協議進行對比。文中采用Matlab2016a 作為仿真工具，參數設置如表1 所示，λ1=0.7，λ2=0.3，φ=0.8。

表1 參數設置

1）聚類圖比較

圖1 是采用k-means 算法形成的分布圖，從圖中可以看出簇分布不均勻，簇內節點數量分布不合理，造成有些節點能量消耗過大，網絡負載不均衡。

圖1 k-means算法的聚類

圖2 是采用文中算法形成的分布圖，從圖中可以看出經過優化后的簇分布均勻，靠近匯聚節點的簇較小，有效地解決了節點能量消耗過快的問題。從而延長了網絡的生存周期。

圖2 改進后的聚類

2）網絡死亡節點個數比較

圖3 是網絡死亡節點個數與輪次之間的關系，從圖中可以看出，文中提出的算法在200 輪時出現了第一個死亡節點，而LEACH 算法和KEAC 算法分別在25 輪和50 輪時出現了第一個死亡節點，文中算法網絡生存周期分別比LEACH 算法和KEAC 算法提高了87.5%和75%，可以得出文中算法有效延長了網絡的生存時間；當LEACH 算法和KEAC 算法分別運行到2 000 輪和3 500 輪左右時，所有節點全部死亡，而文中提出的算法在3 500 輪時大概還有25 個存活節點，可以看出使用改進灰狼優化算法使簇首選擇更合理，均衡了節點的能耗，顯著提高了網絡的生存周期。

圖3 網絡死亡節點數與輪次關系

3）網絡剩余能量比較

圖4 是網絡能量隨時間變化的關系，在初始能量相同的情況下，LEACH 算法能量消耗顯然更快，在2 000 輪時網絡總能量就已耗盡，KEAC 算法在接近3 500 輪時網絡的總能量耗盡，而文中提出算法的網絡能耗速度均小于LEACH 算法和KEAC 算法，能量耗盡的時間較長。綜上分析可知，文中提出的算法的生命周期與LEACH 算法和KEAC 算法相比有明顯提高，可以看出改進后的算法能有效均衡網絡的能耗[17-18]。

圖4 網絡剩余能量與輪次關系

5 結束語

文中針對無線傳感器網絡中簇分布不均勻、簇首選擇不合理的問題，提出了基于k-means 分簇和灰狼優化的無線傳感網絡路由算法。該算法結合節點位置與節點密度兩個方面對k-means 算法形成的簇結構進行優化，在優化后的簇中采用改進灰狼優化算法來選擇簇首，在數據傳輸時，采用單跳和多跳相結合的方式將數據傳輸給匯聚節點。實驗結果表明，與LEACH 和KEAC 兩種協議比較，文中提出的算法解決了“熱區”問題和簇首選擇不合理造成的節點能量消耗不均衡的問題，有效地增加了網絡的生存周期，降低了能量消耗的同時均衡了網絡的能耗。