一種基于K-means 的WSN 移動匯聚路由算法*

陳軼林，吳正坤，江凌云

（南京郵電大學 通信與信息工程學院，江蘇 南京 210003）

0 引言

無線傳感器網絡（Wireless Sensor Network，WSN）是當今無線技術領域的關鍵組成部分。資源受限一直是無線傳感器網絡的最大特點，網絡中節點的計算和存儲數據能力較弱，一旦網絡中部分節點的能量耗盡，整個網絡的性能將受到很大的影響。因此，均衡網絡能耗一直是無線傳感器網絡路由算法研究的熱點。WSN 中傳感器節點數據往往通過中繼節點發送至匯聚（Sink）節點。如圖1 所示，在匯聚節點位置固定的情況下，與Sink 距離較近的部分節點往往會承擔更多的轉發任務。隨著時間的推移，這些節點將率先死亡，從而便產生“能量空洞”的問題[1]。

圖1 無線傳感網絡結構

“能量空洞”問題的出現嚴重影響著網絡的生命周期，造成該問題的根本原因是網絡中節點能耗不均[2]。為了解決“能量空洞”問題，研究者們提出在層次路由中通過簇頭（Cluster Head，CH）節點的輪轉，使處于同一集群的節點輪流承擔匯聚轉發的任務。該方法可以有效均衡網絡中節點的能耗，其中最經典的是低功耗自適應分簇協議（Low Energy Adaptive Clustering Hierarchy，LEACH）。通過簇頭節點的輪轉，該方法一定程度上緩解了“能量空洞”的問題，但依舊存在一定的缺陷。首先，CH 節點位置和數量均不可控，且CH 與Sink 節點間始終以單跳的方式傳輸數據。若CH 分布在網絡的邊緣，則會大大增加傳輸數據的能耗。為了提高網絡的能量效率，通過優化成簇的方式和簇頭節點的選取策略，研究者們相繼提出了ALEACH、LEACH-DCHS、LEACH-C 等路由算法[3]。

為了更好地緩解“能量空洞”問題，21 世紀初R.Shah 等人提出了移動匯聚節點的策略。研究表明，通過Sink 節點的隨機或受控移動，可以有效均衡網絡能耗，延長網絡的壽命[4]。而移動策略的核心是通過規劃Sink 節點移動的路徑，更好地均衡網絡的能耗，延長網絡的壽命。本文基于LEACH-C協議提出了一種新的路由算法，在成簇階段通過K-means 算法對節點進行聚類，并結合節點的位置和能量信息計算通信成本選擇合適的簇首。在穩定傳輸階段通過匯聚節點的受控移動均衡各集群的通信能耗，延長網絡的生命周期。

1 相關工作

近年來，研究者們從多跳傳輸、網絡結構、路由等方面提出諸多有關無線傳感器網絡的數據采集方案[5]。這些方案大多采用層次路由的結構，網絡中的節點被劃分至不同的集群，通常稱之為簇。每個簇中選取CH 節點融合集群內的數據，再通過Sink 節點收集來自不同集群的數據。在以往的研究中，對于WSN 路由算法的改進通常聚焦于算法中集群的劃分、簇間路由的選擇以及移動匯聚中對sink 節點的移動路徑規劃。下面介紹一些具有代表性的方法。LEACH-C[6]協議是為了克服LEACH協議的缺點而提出的，因在WSN 中的適用性而受到了研究者們的高度評價。LEACH-C 的工作原理與LEACH 非常相似，只是在設置階段，集群和簇首的選擇由BS 基站執行[7]。在每一輪的開始，網絡中各節點將其位置（使用GPS 技術）及其剩余能量數據發送到Sink，Sink 再根據模擬退火算法進行分簇并選出CH 節點。該方法可以保證集群數量的穩定，且在一定程度上保證了簇頭的剩余能量，因此相比LEACH 協議有效提高了網絡的能源分配效率[8]。為了進一步均衡網絡能耗，文獻[8]借鑒了LEACH-C 協議的成簇方式，并結合Sink 節點的受控移動提出了LEACH-CD 算法。該算法沿用了LEACH-C 的集群劃分方式，在傳輸階段通過Dijkstra 算法計算Sink 節點遍歷各個集群的最短路徑。與LEACH-C 相比，通過Sink 節點的移動縮短了傳輸距離，降低了簇首節點的能耗，提高了能量效率，但也造成了數據的延遲問題。為了研究如何通過Sink 節點的移動最大化網絡的壽命，文獻[9]中提出一種線性模型下最大化無線傳感網絡壽命的策略。在各節點數據實時傳輸的前提下，通過控制Sink 節點在各節點處的停留時間均衡不同位置的能量消耗，有效延長了網絡壽命。但是，該方法局限于一維的網絡模型，僅從停留時間的角度進行了研究和分析。

結合無線傳感網絡層次路由的特點，本文從集群的劃分和Sink 移動策略兩方面入手，提出基于K-means 算法的成簇方案，并針對不同的延遲要求在兩種場景下分別提出Sink 節點的移動策略。

2 基于K-means 聚類的分簇算法

本文采用K-means 聚類算法，結合LEACH-C協議的一些特性，在初始階段將網絡中的節點劃分成不同的集群（簇）。分簇階段完成后再根據簇內節點與集群中心的距離和節點的剩余能量選擇簇頭節點。

2.1 WSN 中K-means 算法的應用

K-means 是聚類分析中一種基于劃分的算法，具有思想簡單、效果好且容易實現的優點[10]。這里采用歐式距離作為衡量數據對象相似度的指標。使用該算法進行集群劃分前，需事先規定集群個數并初始化中心點坐標。核心思想是通過計算對象與聚類中心Ci（1 ≤i≤k）的歐式距離，將目標劃分到距離最近的聚類中心Ci對應的集群中[11]。劃分完成后重新計算不同集群的中心坐標，作為新的中心坐標，通過迭代直至結果穩定或誤差平方和局部最小。

計算網絡中傳感器節點與Ci的歐式距離公式如下：

其中Nj表示網絡中的普通節點；Ci為聚類中心；xNj、yNj、xci、yci分別為傳感器節點和聚類中心的二維坐標。

衡量聚類結果優劣的最小誤差平方和EK-means定義如下：

其中k為集群個數，Qi表示第i個集群，Ci為前者的中心坐標。

在使用K-means 聚類前需先確定聚類個數和初始聚類中心[12]，因此應用于無線傳感器網絡場景下首先要確定簇的個數和初始聚類中心。本文中WSN 場景下節點部署在M×M范圍內的矩形區域。LEACH-C 協議中，研究者給出了最優簇個數的推導，本文中沿用該協議下對最優簇頭個數k的定義，公式如下：

其中N為網絡中傳感器節點的總數；ξf和ξm為受傳輸距離的影響，不同模型下對應的功率放大系數；dtoBS為簇頭節點到匯聚節點的距離。

初始聚類中心的選取直接影響簇的分布，簇的個數確定后還需確定初始聚類中心。為了使簇的分布更合理，文中先隨機選擇一個節點作為初始聚類中心，之后以距離最大為準則，選擇與先前確定的若干中心距離之和最遠的節點作為下一個聚類中心。重復該步驟直至完成k個初始聚類中心的設置。

2.2 集群劃分與簇首選擇

在簇的劃分階段，本文使用K-means 聚類的方法將網絡劃分成不同的集群（簇），通過LEACH-C 協議中確定最優簇首個數的方法調整初始聚類中心的個數。

新算法在每輪的初始階段執行以下步驟：

（1）Sink 節點根據K-means 算法完成集群劃分；

（2）計算集群的中心坐標，并選擇簇頭節點；

（3）Sink 節點移動至指定坐標位置；

（4）簇首節點融合集群內各節點數據；

（5）簇首節點向Sink 節點發送數據。

集群劃分流程如圖2 所示。

圖2 集群劃分流程

集群劃分工作完成后，需為集群指定簇頭節點。為了均衡網絡的能耗，本文中根據集群中節點的剩余能量Ei和與集群中心的距離di計算通信代價，根據結果選擇每輪中的簇頭節點。假設網絡中各節點初始能量相同，首輪中選擇與各集群中心距離最近的節點作為簇首。在之后的每輪傳輸中，與LEACH-C 算法類似，首先計算集群內節點剩余能耗的平均值Eavg。當剩余能量Ei＞Eavg時，則節點加入簇首的競選。節點滿足剩余能量要求后，根據式（4）計算與Sink 節點通信的代價函數：

本文采用文獻[13]中簡化的無線硬件能耗模型，模型中傳感器節點的能耗與傳輸距離成反比，功率放大系數隨傳輸距離變化而變化。如式（4）所示，當傳輸距離超過閾值d0時，能耗受距離的影響更大。傳輸距離閾值d0的計算公式如下：

簇首選擇過程如圖3 所示。

圖3 簇首選擇流程

如圖3 所示，通過式（4）計算符合剩余能量要求節點的通信代價，選擇函數值最小的節點作為簇頭節點。在穩定傳輸階段負責融合集群剩余節點的數據，并向sink 節點發送。

3 Sink 節點移動策略

在WSN 下的移動匯聚策略可分為實時數據傳輸和延遲容忍條件下的數據傳輸。前者對數據實時性要求較高，各簇首節點直接向Sink 節點傳輸數據；后者通常應用于實時性要求不高的場景，Sink 節點移動到指定位置，簇首節點收到請求后再進行數據傳輸。本文針對兩種場景分別規劃Sink 節點的移動策略。

3.1 實時匯聚的Sink 移動策略

每輪中在集群劃分完成后，Sink 節點根據各集群簇首節點坐標計算各簇首節點間的中心坐標，并移動至中心位置進行數據采集。Sink 節點移動位置如圖4 所示。

圖4 Sink 節點位置

如圖4 所示，Sink 節點受控移動，每輪集群劃分完成后Sink 計算目標位置坐標，使其始終處于各簇頭節點坐標的中心位置。該方法旨在均衡不同集群每輪傳輸過程中的能耗，避免部分集群因簇首與Sink 節點距離過遠而造成能量快速耗盡的問題。

3.2 延時容忍的Sink 移動策略

針對實時性要求不高的應用場合，通常采用的策略是假設節點具有一定緩存數據的能力，Sink 節點移動到目標附近后，CH 再向其發送緩存的數據。本文中通過控制Sink 節點的移動軌跡，使其在每一輪中遍歷每個集群。移動軌跡如圖5 所示。

圖5 Sink 節點移動軌跡

如圖5 所示，每輪集群劃分完成后，穩定傳輸階段簇首節點收集簇內節點數據并緩存。Sink 節點依次移動至各集群中心并發送請求，受到請求后簇首節點再將融合的數據向集群中心發送。該策略通過控制Sink 節點的移動，縮短了與CHs 間的通信距離，從而有效降低了傳輸階段的能耗。

4 仿真結果及分析

為了驗證提出的移動匯聚算法的性能，本文將提出的算法分別與Sink 節點位置固定條件下的LEACH 協議和LEACH-C 協議進行了比較。

4.1 實驗環境與參數

本文通過MATLAB 建立仿真模型。在集群劃分階段，對比使用K-means 聚類分簇算法和傳統LEACH 算法時的簇頭分布情況，并分析不同算法下網絡剩余能量和存活節點數量隨輪數的變化。仿真參數如表1 所示。

表1 仿真參數

4.2 結果分析

節點隨機分布在目標區域內，中心坐標處的“×”代表Sink 節點。每輪中成為簇首的節點會被黑色叉號標記。若節點能量耗盡，該節點將被標記為點。圖6 和圖7 分別顯示了兩種算法在仿真過程中簇首的分布情況。

LEACH 協議中簇首隨機選取的機制并沒有考慮集群位置的分布，會造成集群位置分布不均和集群個數不穩定的問題。如圖6 所示，通過簇首節點的分布可以看出集群的劃分很不合理，部分區域節點離簇首節點距離很遠，很大程度上增加了節點在傳輸階段的能耗。相比之下如圖7 所示，采用K-means 聚類算法進行集群劃分的結果更為理想，各集群中心坐標相對均勻地分布在網絡中，且集群數量穩定可控，在此基礎上進行數據傳輸可以更好地均衡網絡中節點的能耗。因此，使用K-means 聚類的集群劃分方式優化了分簇的結果。

圖6 LEACH 協議下簇首節點分布情況

圖7 K-means 聚類算法下集群中心分布

表2 實驗對比了4 種算法中不同節點死亡情況對應的輪數。可以看到，LEACH 算法因為其簇首選擇的隨機性導致網絡中節點死亡較快，而LEACH-C 協議相比前者由Sink 節點指定簇首節點，優先考慮節點的剩余能量，相比隨機的機制更為合理，一定程度上提高了網絡的能量效率。本文提出使用K-means 聚類算法進行集群劃分的策略，在選取簇首時將剩余能量與通信距離作為參考，通過比較通信代價函數的方式使簇首的選取更為合理，同時集群的分布較LEACH 更均勻，因此節點死亡數相同時完成的傳輸輪數更多。由于LEACH-KTD 算法在延時容忍的場景下大大縮短了Sink 節點與簇首的通信距離，相較前面幾種方法生命周期明顯更長。

表2 生命周期對比

圖8 是仿真實驗中使用LEACH、LEACH-C 及本文提出的兩種算法時網絡剩余總能量的變化趨勢。LEACH-C 與本文提出的LEACH-K 算法均提高了高能節點當選簇首的概率，延緩了節點的死亡。LEACH-K 較前者簇首分布更合理且結合了Sink 節點的移動，因此網絡剩余總能量更高。而延時容忍場景下的LEACH-KTD 算法則不考慮數據的延時，通過Sink 節點的移動大大縮短了通信距離，相同輪數下網絡剩余能量最多。綜上，通過K-means 聚類算法進行集群劃分并結合Sink 節點的受控移動可以有效均衡網絡能耗，延長網絡的生命周期。

圖8 網絡剩余能量對比情況

5 結語

本文在LEACH-C 協議的基礎上提出了一種新的基于K-means 聚類算法的分簇策略，優化了網絡中集群的分布和簇首節點的選取方式。同時，針對數據延時要求不同的場景，分別提出了Sink 節點的移動接收策略。MATLAB 仿真結果顯示，本文提出的成簇策略能夠有效控制簇首的數量與分布。可見，結合Sink 節點的受控移動能有效降低傳輸能耗，延長網絡的生命周期。