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

(1.長春工業(yè)大學(xué) 計算機(jī)科學(xué)與工程學(xué)院， 吉林 長春 130012;2.長春師范大學(xué) 計算機(jī)科學(xué)與技術(shù)學(xué)院， 吉林 長春 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)超過了人類的直接處理能力。為了更方便地表達(dá)和理解數(shù)據(jù)，通過計算機(jī)對數(shù)據(jù)進(jìn)行分類或聚類是非常重要的。無線傳感器網(wǎng)絡(luò)(WSNs)是一種大型無基礎(chǔ)設(shè)施無線傳感器網(wǎng)絡(luò)，由數(shù)千個傳感器節(jié)點(diǎn)組成，并以自組織形式形成網(wǎng)絡(luò)。傳感器節(jié)點(diǎn)之間通過互助進(jìn)行信息交互和數(shù)據(jù)采集與處理，在許多領(lǐng)域得到應(yīng)用[1-4]。網(wǎng)絡(luò)中存在大量的特征信息，因此特別適合將聚類應(yīng)用于無線傳感器網(wǎng)絡(luò)中。

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

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

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

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

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

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

Heinzelman的無線通信系統(tǒng)模型用于網(wǎng)絡(luò)能量消耗，自由空間信道模型和多徑衰落模型用于通信距離。發(fā)送節(jié)點(diǎn)的能量消耗包括發(fā)送電路的能量消耗和功率放大。 通過該模型將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的聚類路由算法設(shè)計

2.1 基于FCM-E的模糊聚類模型

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

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

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

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

緊致率

(6)

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

(7)

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

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

μij----屬于類i的樣本xj的隸屬度;

vi----類i的聚類中心;

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

重疊度

(8)

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

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

分離

(9)

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

(10)

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

2.3 算法描述

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

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

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

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

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

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

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

3 模擬分析

在仿真中，主要考慮了傳感器節(jié)點(diǎn)在數(shù)據(jù)融合中消耗的能量，計算了網(wǎng)絡(luò)中幸存節(jié)點(diǎn)的數(shù)量和總剩余能量，分析算法的能量效率。在相同的仿真條件下，對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個節(jié)點(diǎn)以確定參數(shù)緊湊性閾值。從式(8)計算重疊閾值，以計算簇頭的最佳數(shù)量，見表1。

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

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

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

表2 簇頭死亡時間

從表2可以看出，當(dāng)C=5時，無線傳感器網(wǎng)絡(luò)的壽命最長，適合驗(yàn)證cos的最佳數(shù)量。當(dāng)網(wǎng)絡(luò)中的簇頭數(shù)量太少時，簇頭節(jié)點(diǎn)過載，并且簇頭節(jié)點(diǎn)通常必須將數(shù)據(jù)傳輸?shù)较嗑嗪苓h(yuǎn)的簇頭節(jié)點(diǎn)(中繼節(jié)點(diǎn))，這導(dǎo)致節(jié)點(diǎn)消耗更大的能量。當(dāng)簇頭數(shù)量較大時，會導(dǎo)致簇中更多的本地數(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算法采用固定聚類方法，當(dāng)集群能量消耗較快時，集群中的節(jié)點(diǎn)將一起死亡。 能耗方面，F(xiàn)CM-E算法更加平坦，并且隨著輪數(shù)的增加，能耗差距更加明顯。

4 結(jié) 語

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