WSN 中基于節(jié)點密度優(yōu)化的DB-K-means 分簇算法

◆胡光遠 李昊

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

1 研究現(xiàn)狀

無線傳感器網(wǎng)絡(luò)技術(shù)針對惡劣環(huán)境與無人區(qū)域的感知監(jiān)測已經(jīng)成為必不可少的技術(shù)。在傳統(tǒng)WSN 中，網(wǎng)絡(luò)結(jié)構(gòu)有平面結(jié)構(gòu)和分簇結(jié)構(gòu)兩種。分簇結(jié)構(gòu)適用于大規(guī)模網(wǎng)絡(luò)中，依靠節(jié)點的自適應(yīng)分簇以及數(shù)據(jù)融合傳輸實現(xiàn)感知信息的收集與傳輸。當前對于分簇結(jié)構(gòu)最常用的路由協(xié)議為低能量自適應(yīng)分層路由協(xié)議LEACH 算法，因此對LEACH 協(xié)議的改進方法一直是國內(nèi)外學(xué)者的研究熱點[1]。

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

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

2 系統(tǒng)模型

2.1 網(wǎng)絡(luò)模型

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

圖1 WSN 系統(tǒng)模型

2.2 能量模型

本文采用與如圖2 所示的能量模型圖。傳感器節(jié)點發(fā)送lbit 的數(shù)據(jù)消耗能量由發(fā)射損耗和功率放大兩部分構(gòu)成。一個節(jié)點經(jīng)過距離d發(fā)送lbit 數(shù)據(jù)的能耗如下：

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

圖2 能量模型

3 LEACH 分簇及K-means 分簇

3.1 LEACH 協(xié)議流程

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

圖3 LEACH 協(xié)議流程圖

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

3.2 LEACH 的分簇

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

3.3 K-means 分簇

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

3.4 分簇算法缺陷分析

盡管LEACH 算法有低能量，自適應(yīng)分簇，但是LEACH 協(xié)議的缺點也是很明顯的。

首先簇頭的選舉是隨機地，其次分簇的數(shù)目也是隨機地，如果簇數(shù)太多，會增加節(jié)點的消耗，反之，簇數(shù)太少，會加重簇頭的業(yè)務(wù)壓力。因此這些缺陷會導(dǎo)致簇內(nèi)節(jié)點數(shù)不均衡，可能會導(dǎo)致網(wǎng)絡(luò)負載不均衡和加劇損耗網(wǎng)絡(luò)生命周期。

4 DB-K-mesan 分簇

4.1 密度相關(guān)概念

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

eps：節(jié)點掃描區(qū)域半徑。

minpts：節(jié)點掃描區(qū)域內(nèi)的閾值節(jié)點數(shù)。

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

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

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

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

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

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

4.2 密度分布

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

圖4 K-means 分簇算法

圖5 DB-K-means 分簇算法

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

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

R=a1x1+a2x2+a3x3

其中，a1a2a3分別為節(jié)點剩余能量x1，節(jié)點到簇頭的歐式距離x2，節(jié)點密度可達的節(jié)點數(shù)x3的權(quán)重值，其和為1。因此節(jié)點的R值越高，該節(jié)點成為最優(yōu)簇頭的可能性最大。

5 仿真分析

5.1 仿真參數(shù)

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

表1 仿真參數(shù)表

針對DB-K-means 算法，本文設(shè)計節(jié)點的掃描范圍半徑eps=5，節(jié)點掃描區(qū)域內(nèi)的閾值節(jié)點數(shù)Minpts=15。

5.2 仿真結(jié)果

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

圖6 網(wǎng)絡(luò)總耗能與輪數(shù)的關(guān)系

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

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

圖7 網(wǎng)絡(luò)總耗能與輪數(shù)的關(guān)系

6 結(jié)論

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