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

◆胡光遠(yuǎn) 李昊

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

1 研究現(xiàn)狀

無線傳感器網(wǎng)絡(luò)技術(shù)針對(duì)惡劣環(huán)境與無人區(qū)域的感知監(jiān)測(cè)已經(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é)點(diǎn)的自適應(yīng)分簇以及數(shù)據(jù)融合傳輸實(shí)現(xiàn)感知信息的收集與傳輸。當(dāng)前對(duì)于分簇結(jié)構(gòu)最常用的路由協(xié)議為低能量自適應(yīng)分層路由協(xié)議LEACH 算法，因此對(duì)LEACH 協(xié)議的改進(jìn)方法一直是國(guó)內(nèi)外學(xué)者的研究熱點(diǎn)[1]。

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

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

2 系統(tǒng)模型

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

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

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

2.2 能量模型

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

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

圖2 能量模型

3 LEACH 分簇及K-means 分簇

3.1 LEACH 協(xié)議流程

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

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

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

3.2 LEACH 的分簇

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

3.3 K-means 分簇

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

3.4 分簇算法缺陷分析

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

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

4 DB-K-mesan 分簇

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

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

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

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

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

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

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

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

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

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

4.2 密度分布

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

圖4 K-means 分簇算法

圖5 DB-K-means 分簇算法

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

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

R=a1x1+a2x2+a3x3

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

5 仿真分析

5.1 仿真參數(shù)

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

表1 仿真參數(shù)表

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

5.2 仿真結(jié)果

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

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

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

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

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

6 結(jié)論

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