WSN 中基于節點密度優化的DB-K-means 分簇算法

◆胡光遠 李昊

（1.南京六九零二科技有限公司 江蘇 210009；2.近地面探測技術重點實驗室 江蘇 214035）

1 研究現狀

無線傳感器網絡技術針對惡劣環境與無人區域的感知監測已經成為必不可少的技術。在傳統WSN 中，網絡結構有平面結構和分簇結構兩種。分簇結構適用于大規模網絡中，依靠節點的自適應分簇以及數據融合傳輸實現感知信息的收集與傳輸。當前對于分簇結構最常用的路由協議為低能量自適應分層路由協議LEACH 算法，因此對LEACH 協議的改進方法一直是國內外學者的研究熱點[1]。

文獻[2]中介紹了LEACH 協議的相關研究，并針對LEACH 算法的缺陷提出改進的LEACH 算法，傳感器將自己的節點剩余能量和位置信息發送給基站，由基站根據發送信息確定合適的簇頭數量。文獻[3]中，作者提出將K-means 均勻分簇和數據回歸的WSN 能量均衡策略進行結合，采用數據回歸的方法來減少普通節點與簇首的通信量，以達到降低功耗的作用。文獻[4]中，作者提出一種基于K-means 的WSN 移動匯聚路由算法，該算法通過K-means 聚類將網絡中的節點劃分至不同的集群，選擇通信成本最低的節點作為各集群的簇首.穩定傳輸階段通過移動Sink 進行數據采集，針對不同的延遲分別規劃Sink 節點的移動軌跡。文獻[5]中介紹了一種基于Mini Batch K-Means和SVM 的入侵檢測方案。該方法利用特征庫和異常行為樣板庫進行Mini Batch K-Means 分簇，取得簇頭作為各簇的代表樣本設置權值，將其傳入SVM 訓練器作為訓練數據，這樣可以有效解決如K-Means，KNN，SVM 等傳統分簇算法在大數據樣本集數據分析中面臨的低效率問題。文獻[6]提出一種基于LEACH 協議，K-means 聚類和蟻群算法的WSN 改進路由算法.首先在預處理階段利用K-means 聚類算法將散布的節點分成多個簇，通過聚類減少數據發送量.其次，利用蟻群算法支持多路徑的特點，在數據傳輸階段形成簇首間多路由機制。文獻[7]提出一種改進的基于加權優化樹的路由算法，將樹型結構應用于分簇路由算法中.根據節點的剩余能量，可用內存，相鄰節點的距離，信道質量設定數據傳輸代價，并以此為基礎對樹型拓撲結構進行加權優化，分布式地在簇內創建樹型網絡拓撲結構.改進的算法降低了網絡中數據傳輸的總代價。文獻[8]該路由算法首先基于對網絡能耗的理論分析確定WSN 的最佳簇頭數目，然后利用二分k-means基于最優簇頭數目對節點進行分簇。

傳統算法包括改進的LEACH 算法均是根據簇頭數決定分簇數。顯然，該方法存在一定的隨機性，簇頭數的過多和過少都不能夠有效發揮LEACH 協議的性能。因此，針對傳統算法沒有根據傳感器節點的分布特性確定分簇數目的缺陷，提出DB-K-means 分簇算法，算法首先根據傳感器節點的分布密度確定最優分簇數目，進一步對網內所有存活節點進行分類，如核心、邊緣、孤立節點，然后從核心節點中進行簇頭選舉。避免了因隨機選舉簇頭陷入局部最優解的情況。完成簇頭選舉后，利用K-means 算法完成所有存活節點的建簇。

2 系統模型

2.1 網絡模型

假設WSN 網絡中，有K個傳感器節點隨機分布在一個N×Nm2的正方形區域中，基站距離WSN 網絡很遠，能量不受限。每個傳感器節點不可移動且初始能量均等，且都可以直接與基站進行通信。每個傳感器節點都能感知到自身剩余能量和位置信息，都有機會當選簇頭，承擔數據融合與傳輸的任務。

圖1 WSN 系統模型

2.2 能量模型

本文采用與如圖2 所示的能量模型圖。傳感器節點發送lbit 的數據消耗能量由發射損耗和功率放大兩部分構成。一個節點經過距離d發送lbit 數據的能耗如下：

其中，l是數據包長度，Eelec是節點能量，εfs和εmp為能量參數，d為節點到基站的傳輸距離，d0是傳輸距離的閾值，一般取值為εfs/εmp。當傳輸距離d小于d0時，采用自由空間信道模型。反之，采用多徑信道模型。

圖2 能量模型

3 LEACH 分簇及K-means 分簇

3.1 LEACH 協議流程

LEACH（Low Energy Adaptive Clustering Hierarchy）是第一個基于分簇概念實現的路由協議。首先，LEACH 協議將網絡分成若干個簇，每個簇由簇頭節點和其他節點構成，節點負責將自身感知到的數據信息發送至所在簇的簇頭，簇頭承擔數據融合和將融合后的數據發送至匯聚節點或基站的任務。簇頭承擔的任務量明顯重于節點，因此，簇頭的選擇對WSN 網絡生命周期是至關重要的。

圖3 LEACH 協議流程圖

LEACH 協議的工作流程如圖XX 所示，LEACH 協議是具有自適應和自組織特性地，在每一輪循環中，都是自適應分簇和自組織建簇，進入到穩定階段后，就可以完成數據融合與匯聚節點的數據傳輸任務。

3.2 LEACH 的分簇

LEACH 是最經典的一個低能量自適應分簇路由協議。每輪都是隨機選擇簇頭進行簇間信息傳輸。區域內的節點感知收集信息后發送給各自簇頭（Cluster Head，CH），CH 將感知到的信息數據轉發到匯聚節點（Sink）或基站。使得終端用戶可以在終端設備上獲取檢測區域的信息。

3.3 K-means 分簇

K-means 算法流程如下圖4 所示。

3.4 分簇算法缺陷分析

盡管LEACH 算法有低能量，自適應分簇，但是LEACH 協議的缺點也是很明顯的。

首先簇頭的選舉是隨機地，其次分簇的數目也是隨機地，如果簇數太多，會增加節點的消耗，反之，簇數太少，會加重簇頭的業務壓力。因此這些缺陷會導致簇內節點數不均衡，可能會導致網絡負載不均衡和加劇損耗網絡生命周期。

4 DB-K-mesan 分簇

4.1 密度相關概念

本小節首先介紹一下基于無線傳感器件的密度的幾個相關概念和密度分布[9]。

eps：節點掃描區域半徑。

minpts：節點掃描區域內的閾值節點數。

Neps(k)：節點k的鄰域信息。

dis(k,c)：節點k與簇頭c間的連接度量。

節點屬性：節點k如果滿足Neps(k)≥minpts，稱節點k為核心節點，如果1＜Neps(k)＜minpts，稱節點k為一般節點，如果Neps(k)=1，稱節點k為孤立節點。

直接密度可達：如果節點k與節點j滿足j∈Neps(k)，則節點j到節點k直接密度可達。

密度可達：如果存在節點鏈o1o2...on，o1=k，on=j，節點鏈中的當前節點oi可由上一個節點oi-1直接密度可達，那么節點k到節點j密度可達。

密度相連：如果節點k與節點j均可由節點o直接密度可達，那么節點k與節點j密度相連。

4.2 密度分布

針對傳統LEACH 協議在建簇時的簇頭選舉隨機的缺陷，提出一種基于節點分布密度選取簇頭的方式，算法流程如圖5 所示。

圖4 K-means 分簇算法

圖5 DB-K-means 分簇算法

如上圖所示，首先對傳感網內的所有節點進行屬性判斷，核心節點顯然更適合作為簇頭，因為核心節點比較密集，反映了傳感網內節點的整體分布，因此可以根據直接密度可達、密度可達、密度相連關系構成G 個核心節點簇，這些核心簇反映了網絡的整體分布，避免了簇數的隨機設置過大，浪費整個網絡資源，或者簇數過小，不能發揮分簇路由協議的優勢。

核心節點中的簇頭更新準則參考以下加權度量準則，有效避免了簇頭選舉的隨機性和容易陷入局部最優解的缺陷。簇頭度量權重更新準則：

R=a1x1+a2x2+a3x3

其中，a1a2a3分別為節點剩余能量x1，節點到簇頭的歐式距離x2，節點密度可達的節點數x3的權重值，其和為1。因此節點的R值越高，該節點成為最優簇頭的可能性最大。

5 仿真分析

5.1 仿真參數

為了驗證本文提出的DB-K-means 的性能，利用MATLAB 軟件設計仿真驗證分簇算法在WSN 網絡中的性能，設計仿真參數如下表1 所示：

表1 仿真參數表

針對DB-K-means 算法，本文設計節點的掃描范圍半徑eps=5，節點掃描區域內的閾值節點數Minpts=15。

5.2 仿真結果

在WSN 網絡性能分析中，剩余存活節點數，網絡剩余能量是兩個重要衡量指標。在表的仿真條件下，圖6 與圖7 分別對比了DB-Kmeans 分簇與基于K-means 的LEACH 協議的性能指標：網絡存活節點數與剩余總能量。

圖6 網絡總耗能與輪數的關系

圖6 為兩種算法下網絡剩余生存節點數與網絡輪數的性能曲線。隨著輪數的增加，三種算法的生存節點數都顯著下降，當輪數達到600 輪時，K-means 算法僅存幾個節點在工作，600 輪時存活節點143，此時DB-K-means 仍然還有183 個節點在工作。DB-K-means 分簇與建簇有效改善了網絡的生存周期，統計可得到，DB-K-means 分簇算法的生命周期比k-means 分簇算法更長。

圖7 為對比了DB-K-means 與K-means 分簇算法下網絡剩余生存節點數與網絡輪數的性能曲線。隨著輪數的上升，網絡剩余能量顯著下降，但是DB-K-means 算法的下降幅度遠低于K-means 分簇算法，但是隨著輪數接近600 輪時，DB-K-means 分簇算法下的網絡剩余總能量很接近K-means 算法，這是由于隨著存活節點數的減少，節點分布較為發散，DB-k_means 算法性能接近k-means，但是想仍有較高的剩余能量。顯然，DB-K-means 能夠有效改善網絡生存周期。

圖7 網絡總耗能與輪數的關系

6 結論

本文針對LEACH 協議存在分簇數目隨機、簇頭選舉隨機、分簇不均勻的缺陷，提出一種基于密度優化的DB-K-means 算法用于LEACH 協議的分簇及簇的建立過程。所提分簇算法有效改善了基于K-means 分簇算法的LEACH 協議的缺陷，提升了分簇準確性，延長了WSN 網絡生存周期。