無(wú)線傳感網(wǎng)能量約束模糊c-均值聚類(lèi)算法

姚美琴， 胡黃水*， 王出航， 韓優(yōu)佳

(1.長(zhǎng)春工業(yè)大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院， 吉林 長(zhǎng)春 130012;2.長(zhǎng)春師范大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院， 吉林 長(zhǎng)春 130021)

0 引 言

隨著互聯(lián)網(wǎng)和信息技術(shù)的快速發(fā)展，許多應(yīng)用領(lǐng)域?qū)a(chǎn)生大量數(shù)據(jù),這些數(shù)據(jù)的規(guī)模和容量遠(yuǎn)遠(yuǎn)超過(guò)了人類(lèi)的直接處理能力。為了更方便地表達(dá)和理解數(shù)據(jù)，通過(guò)計(jì)算機(jī)對(duì)數(shù)據(jù)進(jìn)行分類(lèi)或聚類(lèi)是非常重要的。無(wú)線傳感器網(wǎng)絡(luò)(WSNs)是一種大型無(wú)基礎(chǔ)設(shè)施無(wú)線傳感器網(wǎng)絡(luò)，由數(shù)千個(gè)傳感器節(jié)點(diǎn)組成，并以自組織形式形成網(wǎng)絡(luò)。傳感器節(jié)點(diǎn)之間通過(guò)互助進(jìn)行信息交互和數(shù)據(jù)采集與處理，在許多領(lǐng)域得到應(yīng)用[1-4]。網(wǎng)絡(luò)中存在大量的特征信息，因此特別適合將聚類(lèi)應(yīng)用于無(wú)線傳感器網(wǎng)絡(luò)中。

LEACH(低能量自適應(yīng)聚類(lèi)層次結(jié)構(gòu))[5-7]是最具代表性的層次聚類(lèi)路由算法之一。 其核心思想是通過(guò)隨機(jī)周期選擇簇頭節(jié)點(diǎn)，將整個(gè)網(wǎng)絡(luò)的能量負(fù)載均勻分布到每個(gè)節(jié)點(diǎn)，從而降低網(wǎng)絡(luò)能耗，延長(zhǎng)網(wǎng)絡(luò)生命周期。LEACH-C[8]集中選擇簇頭以使簇頭的分布更加合理，但集中控制使得sink節(jié)點(diǎn)需要頻繁地與所有節(jié)點(diǎn)交換信息，導(dǎo)致能源浪費(fèi);文獻(xiàn)[9]采用自適應(yīng)調(diào)整機(jī)制來(lái)控制簇頭廣播消息的廣播半徑，平衡節(jié)點(diǎn)分布和能耗，但該算法以丟失大量網(wǎng)絡(luò)信息為代價(jià)改善網(wǎng)絡(luò)生命周期;文獻(xiàn)[10]通過(guò)減少基站節(jié)點(diǎn)的簇半徑實(shí)現(xiàn)非均勻聚類(lèi)，然后在整個(gè)網(wǎng)絡(luò)中實(shí)現(xiàn)能量平衡;文獻(xiàn)[11]提出了一種估算數(shù)值數(shù)據(jù)聚類(lèi)中心的有效方法,該方法可用于確定簇的數(shù)量及其初始值，用于初始化迭代優(yōu)化的聚類(lèi)算法，例如模糊聚類(lèi)算法;文獻(xiàn)[12]提出了一種新的基于Renyi信息的聚類(lèi)算法，該算法和眾所周知的模糊聚類(lèi)算法FCM具有相同的聚類(lèi)軌跡。 這一事實(shí)構(gòu)成了概率聚類(lèi)與模糊聚類(lèi)之間的橋梁，而Renyi entropy measure的研究成果可以幫助我們進(jìn)一步理解模糊聚類(lèi)的本質(zhì);Bensay[13]提出的有效性函數(shù)表明，值越小，聚類(lèi)效果越好。通過(guò)對(duì)結(jié)果的分析，確定最優(yōu)聚類(lèi)數(shù)量，大大提高了計(jì)算成本。文中提出了一種能量限制模糊c-均值聚類(lèi)無(wú)線傳感器網(wǎng)絡(luò)聚類(lèi)算法(FCM-E)，在聚類(lèi)過(guò)程中引入能量限制項(xiàng)來(lái)提高聚類(lèi)算法對(duì)能量的敏感性，通過(guò)cos指數(shù)確定最佳聚類(lèi)數(shù)。該算法可以自動(dòng)確定最優(yōu)聚類(lèi)數(shù)，大大降低計(jì)算成本，延長(zhǎng)網(wǎng)絡(luò)壽命。

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

提出的FCM-E算法檢查了在100 m×100 m監(jiān)測(cè)區(qū)域中隨機(jī)部署的100個(gè)傳感器節(jié)點(diǎn)，基于以下假設(shè)：

1)所有傳感器節(jié)點(diǎn)都是同構(gòu)的，能量有限，匯聚節(jié)點(diǎn)的能量是無(wú)限的；

2)匯聚節(jié)點(diǎn)和傳感器節(jié)點(diǎn)在部署后是固定的，匯聚節(jié)點(diǎn)遠(yuǎn)離監(jiān)控區(qū)域；

3)傳感器節(jié)點(diǎn)之間的無(wú)線通信可以是對(duì)稱(chēng)的，位置信息可以通過(guò)GPS或定位算法確定并傳輸?shù)絽R聚節(jié)點(diǎn)。

Heinzelman的無(wú)線通信系統(tǒng)模型用于網(wǎng)絡(luò)能量消耗，自由空間信道模型和多徑衰落模型用于通信距離。發(fā)送節(jié)點(diǎn)的能量消耗包括發(fā)送電路的能量消耗和功率放大。 通過(guò)該模型將kbit數(shù)據(jù)發(fā)送到距離d的能量消耗為

ETx(k)=ETx-elec(k)+ETx-amp(k,d)=

(1)

接收節(jié)點(diǎn)接收kbit數(shù)據(jù)的能量消耗為

ERx(k)=ERx-elec=Eelec*k,

(2)

式中：Eelec----發(fā)送或接收電路的能量消耗；

d0----通信距離的閾值。

2 基于FCM-E的聚類(lèi)路由算法設(shè)計(jì)

2.1 基于FCM-E的模糊聚類(lèi)模型

文中提出了一種基于改進(jìn)模糊c-均值聚類(lèi)算法的聚類(lèi)路由協(xié)議(FCM-E)。主要思想是將傳感器節(jié)點(diǎn)作為分類(lèi)對(duì)象并將其劃分為C個(gè)部分，其中每個(gè)部分都有一個(gè)聚類(lèi)中心，最佳聚類(lèi)數(shù)由cos索引確定，這里，F(xiàn)CM-E算法給出了一個(gè)目標(biāo)函數(shù)來(lái)調(diào)整聚類(lèi)中心。 當(dāng)目標(biāo)函數(shù)的值小于給定閾值時(shí)，停止迭代以獲得最終聚類(lèi)結(jié)果X={x1,x2,…，xn}，X是節(jié)點(diǎn)集，xi表示每個(gè)節(jié)點(diǎn)。

X={x1,x2,…，xn}是M維數(shù)據(jù)空間中的有限樣本數(shù)據(jù)集，n是數(shù)據(jù)集中元素的數(shù)量，xj(j=1,2,…，n)是數(shù)據(jù)集中的樣本點(diǎn)。

(3)

式中：Enow----節(jié)點(diǎn)的當(dāng)前能量；

Enode----節(jié)點(diǎn)的總能量；

m----加權(quán)指數(shù)，m?[0,1)。

(4)

(5)

當(dāng)目標(biāo)函數(shù)最小化時(shí)，需要迭代調(diào)整聚類(lèi)中心。 給定閾值ε(0.001<ε<0.01)，如果目標(biāo)函數(shù)值大于閾值，則迭代更新隸屬度，否則迭代停止。

2.2 選擇最佳聚類(lèi)數(shù)

通過(guò)上述聚類(lèi)方法得到一組聚類(lèi)數(shù)C，然后構(gòu)造有效函數(shù)以確定最優(yōu)聚類(lèi)數(shù)。聚類(lèi)結(jié)果的質(zhì)量可以通過(guò)聚類(lèi)內(nèi)的緊湊程度和聚類(lèi)之間的分離程度來(lái)確定。也就是說(shuō)，集群內(nèi)的對(duì)象盡可能緊湊，集群外盡可能分開(kāi)。

首先，選擇不同聚類(lèi)類(lèi)別的數(shù)量。最終的聚類(lèi)結(jié)果由簇內(nèi)緊湊性、簇間重疊度和簇間分離確定。

緊致率

(6)

其中，樣本xi到第i類(lèi)的緊致率定義為

(7)

式中:C----聚類(lèi)數(shù);

n----樣本總數(shù);

μij----屬于類(lèi)i的樣本xj的隸屬度;

vi----類(lèi)i的聚類(lèi)中心;

μ0----緊湊度閾值。

重疊度

(8)

其中，樣本xi在第i1類(lèi)和第i2類(lèi)之間的重疊程度為

式中：μ1----重疊閾值。

分離

(9)

考慮到數(shù)據(jù)分布的差異，引入了新度量的cos索引重疊度，兩個(gè)類(lèi)之間的重疊程度由屬于某一閾值內(nèi)兩個(gè)類(lèi)的樣本點(diǎn)的隸屬度差異表示，兩類(lèi)之間所有樣本的重疊度之和是兩類(lèi)的重疊度。根據(jù)緊致度指數(shù)，緊湊性值越小，緊湊性越好;根據(jù)分離指數(shù)，分離度值越高，分離程度越高。因此，構(gòu)造了以下聚類(lèi)有效性函數(shù)

(10)

對(duì)應(yīng)于cos索引最大值的聚類(lèi)數(shù)是由該索引確定的最佳聚類(lèi)數(shù)。

2.3 算法描述

1)輸入傳感器節(jié)點(diǎn)和節(jié)點(diǎn)特征索引矩陣。

2)根據(jù)上述改進(jìn)算法計(jì)算并初始化聚類(lèi)中心，設(shè)置迭代計(jì)數(shù)器b=0。

3)構(gòu)造模糊相似度矩陣U=(μij)c×n。

4)根據(jù)式(5)更新聚類(lèi)中心v。

5)根據(jù)式(4)更新模糊分類(lèi)矩陣μ。

6)當(dāng)?shù)僮鬟_(dá)到收斂‖vb+1-vb‖<ε時(shí)，輸出聚類(lèi)中心v(簇頭節(jié)點(diǎn))，網(wǎng)絡(luò)中的每個(gè)節(jié)點(diǎn)屬于不同的聚類(lèi)，并具有每個(gè)聚類(lèi)的標(biāo)識(shí)。否則，如果b=b+1，則轉(zhuǎn)到3)。

7)計(jì)算余弦(cos)函數(shù)，選擇最大余弦(cos)生成最優(yōu)聚類(lèi)數(shù)C，使用聚類(lèi)中心得到聚類(lèi)簇頭，選擇最接近聚類(lèi)中心的節(jié)點(diǎn)作為聚類(lèi)簇頭節(jié)點(diǎn)，并根據(jù)聚類(lèi)結(jié)果形成c簇。

3 模擬分析

在仿真中，主要考慮了傳感器節(jié)點(diǎn)在數(shù)據(jù)融合中消耗的能量，計(jì)算了網(wǎng)絡(luò)中幸存節(jié)點(diǎn)的數(shù)量和總剩余能量，分析算法的能量效率。在相同的仿真條件下，對(duì)LEACH和FCM-E進(jìn)行比較。 LEACH的參數(shù)模型仿真參數(shù)：發(fā)送或接收電路消耗;自由空間模型;多徑衰減模型;距離閉合值;數(shù)據(jù)處理功率;數(shù)據(jù)包大小為250 bit。FCM-C和FCM-E算法的fuzziness indexm=2, stop parameter=0.1。

設(shè)置基站節(jié)點(diǎn)(0，0)在100 m×100 m方形區(qū)域中，隨機(jī)設(shè)置100個(gè)節(jié)點(diǎn)以確定參數(shù)緊湊性閾值。從式(8)計(jì)算重疊閾值，以計(jì)算簇頭的最佳數(shù)量，見(jiàn)表1。

表1 簇頭的最佳數(shù)量

從表1可以確定，當(dāng)C=5時(shí)，獲得cos的最大值，最佳聚類(lèi)數(shù)為5，Lt-1，Lt-2分別是第一個(gè)節(jié)點(diǎn)死亡時(shí)間和30%節(jié)點(diǎn)死亡時(shí)間。節(jié)點(diǎn)的初始能量為0.02j，群內(nèi)通信采用單跳方式，群集間通信采用多跳方式。

算法的網(wǎng)絡(luò)生命周期見(jiàn)表2。

表2 簇頭死亡時(shí)間

從表2可以看出，當(dāng)C=5時(shí)，無(wú)線傳感器網(wǎng)絡(luò)的壽命最長(zhǎng)，適合驗(yàn)證cos的最佳數(shù)量。當(dāng)網(wǎng)絡(luò)中的簇頭數(shù)量太少時(shí)，簇頭節(jié)點(diǎn)過(guò)載，并且簇頭節(jié)點(diǎn)通常必須將數(shù)據(jù)傳輸?shù)较嗑嗪苓h(yuǎn)的簇頭節(jié)點(diǎn)(中繼節(jié)點(diǎn))，這導(dǎo)致節(jié)點(diǎn)消耗更大的能量。當(dāng)簇頭數(shù)量較大時(shí)，會(huì)導(dǎo)致簇中更多的本地?cái)?shù)據(jù)融合消耗，因此,最佳簇頭數(shù)量的選擇需要在合適的范圍內(nèi)。

比較LEACH和FCM-E在網(wǎng)絡(luò)生命周期和能耗方面的表現(xiàn),分別如圖1和圖2所示。

圖1 算法生命周期

圖2 算法能耗

從圖1和圖2可以看出，F(xiàn)CM-E算法比LEACH算法顯著提高了網(wǎng)絡(luò)生命周期,降低了網(wǎng)絡(luò)能耗。與LEACH算法相比，F(xiàn)CM-E算法的能耗更加漸進(jìn)，這使得網(wǎng)絡(luò)能量消耗更加均勻，提高了網(wǎng)絡(luò)的性能。FCM-E算法在網(wǎng)絡(luò)生命周期中具有梯度。FCM-E算法采用固定聚類(lèi)方法，當(dāng)集群能量消耗較快時(shí)，集群中的節(jié)點(diǎn)將一起死亡。 能耗方面，F(xiàn)CM-E算法更加平坦，并且隨著輪數(shù)的增加，能耗差距更加明顯。

4 結(jié) 語(yǔ)

提出了一種用于無(wú)線傳感器網(wǎng)絡(luò)的能量約束模糊c-均值聚類(lèi)算法，引入能量限制項(xiàng)來(lái)提高聚類(lèi)算法在聚類(lèi)過(guò)程中對(duì)能量的敏感性，確定最優(yōu)聚類(lèi)數(shù)。 仿真結(jié)果表明，與LEACH算法相比，該算法能夠獲得合理的簇頭節(jié)點(diǎn)分布，延緩第一個(gè)節(jié)點(diǎn)的死亡時(shí)間，延長(zhǎng)網(wǎng)絡(luò)生命周期，平衡節(jié)點(diǎn)的能耗。