改進(jìn)的FCM算法在UASN分簇中的應(yīng)用

江萌萌，劉廣鐘

(上海海事大學(xué) 信息工程學(xué)院，上海 201306)

0 引 言

水聲傳感器網(wǎng)絡(luò)(underwater acoustic sensor networks，UASN)由于水下環(huán)境的潛在利益和獨(dú)特的挑戰(zhàn)而受到學(xué)術(shù)界和工業(yè)界的高度重視。UASN允許大量的應(yīng)用程序變得可行又有效，包括商業(yè)開發(fā)，海洋學(xué)數(shù)據(jù)收集和海岸線保護(hù)關(guān)于水聲傳感器網(wǎng)絡(luò)方面的一些重要技術(shù)的研究引起了廣泛重視[1-2]。

UASN由大量便宜的便攜式傳感器節(jié)點(diǎn)以自組織的方式組成，具有有限的功率，存儲(chǔ)和計(jì)算能力。由于水下信道的復(fù)雜性，水聲傳感器網(wǎng)絡(luò)環(huán)境下的數(shù)據(jù)傳輸速率和網(wǎng)絡(luò)生存時(shí)間等都會(huì)受到嚴(yán)重影響，同時(shí)在水下工作想要更換節(jié)點(diǎn)電池是不可行的，所以節(jié)點(diǎn)的能量消耗必然引起人們的重視[3]。提出的分簇路由協(xié)議，可以通過僅允許一些節(jié)點(diǎn)與基站通信來減少能量消耗。這些稱為簇頭的節(jié)點(diǎn)收集該簇中的每個(gè)節(jié)點(diǎn)發(fā)送的數(shù)據(jù)，并將其融合數(shù)據(jù)發(fā)送到基站[4]。

在模糊聚類算法[5-6]中，樣本按一定的隸屬度分類，得到了樣本屬于各個(gè)類別的不確定性程度，這樣更能準(zhǔn)確地反映現(xiàn)實(shí)世界。水聲傳感器網(wǎng)絡(luò)的分簇過程類似模糊聚類分析，將水聲傳感器節(jié)點(diǎn)分簇路由問題建模為樣本空間的模糊聚類劃分問題。整個(gè)UASN看作一個(gè)模糊聚類的對(duì)象集合，每個(gè)傳感器節(jié)點(diǎn)作為該集合中的一個(gè)樣本，最接近模糊聚類得到的聚類中心就是UASN中的簇頭節(jié)點(diǎn)，聚類得到的子集就是UASN中的每個(gè)簇。

1 相關(guān)工作

目前已有的分簇算法是基于節(jié)點(diǎn)的剩余能量，簇頭的位置分布和覆蓋度等準(zhǔn)則提出的。典型的分簇路由算法有LEACH[4]、HEED[7]、APTEEN[8]、DAEA[9]、TEEN[10]等。這里主要介紹基于模糊邏輯控制的CEFL分簇算法[11]。

在CEFL算法中，使用模糊邏輯控制模型中最常用的模糊推理技術(shù)，提出了基于能量、集中度和中心性三個(gè)描述符的簇頭選舉分簇算法，通過精確地修改每個(gè)模糊集的形狀，進(jìn)一步改善網(wǎng)絡(luò)壽命和能量消耗。模糊規(guī)則庫目前包括以下規(guī)則：如果能量高，集中度高，中心性接近，節(jié)點(diǎn)當(dāng)選機(jī)會(huì)大。但該算法存在一些缺點(diǎn)：首先，每個(gè)節(jié)點(diǎn)概率地決定是否成為簇頭，所以可能選出彼此相鄰的兩個(gè)簇頭，增加了網(wǎng)絡(luò)中耗盡的總能量。其次，CEFL算法最后生成的簇頭節(jié)點(diǎn)的數(shù)量不是固定的，所以有時(shí)它可能大于或小于優(yōu)選值。

針對(duì)上述問題，提出一種基于改進(jìn)的模糊C-均值聚類算法的水聲傳感器網(wǎng)絡(luò)分簇路由協(xié)議(FCM-L)。采用FACM-L對(duì)水聲傳感器節(jié)點(diǎn)進(jìn)行聚類，在計(jì)算初始化聚類中心時(shí)通過考慮節(jié)點(diǎn)間的相對(duì)距離和能量衰減率這兩個(gè)因素，避免了FCM算法對(duì)初始化聚類中心敏感這一缺點(diǎn)，并構(gòu)造一個(gè)有效性函數(shù)來選定最佳聚類類別數(shù)，根據(jù)已產(chǎn)生的最佳聚類數(shù)完成水聲傳感器節(jié)點(diǎn)分簇過程。

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

在分簇的UASN架構(gòu)中，基站遠(yuǎn)離傳感器節(jié)點(diǎn)并且是靜止的，簇頭節(jié)點(diǎn)負(fù)責(zé)控制簇內(nèi)節(jié)點(diǎn)的協(xié)同工作，簇內(nèi)節(jié)點(diǎn)向相應(yīng)的簇頭發(fā)送數(shù)據(jù)，簇頭節(jié)點(diǎn)將收集到的數(shù)據(jù)信息壓縮融合處理后將其發(fā)送到基站。

文中對(duì)網(wǎng)絡(luò)模型做如下假設(shè)：

(1)假設(shè)水聲傳感器網(wǎng)絡(luò)是同構(gòu)網(wǎng)絡(luò)，每個(gè)節(jié)點(diǎn)都有唯一的ID。

(2)主要針對(duì)二維靜態(tài)水聲傳感器網(wǎng)絡(luò)，不考慮節(jié)點(diǎn)移動(dòng)性。

(3)每個(gè)節(jié)點(diǎn)都有可能競選簇頭。

(4)每個(gè)節(jié)點(diǎn)都具有相同初始能量，具有數(shù)據(jù)融合功能，而且節(jié)點(diǎn)能根據(jù)距離的遠(yuǎn)近來調(diào)整發(fā)射功率。

(5)基站的能量是無限的，而且能覆蓋整個(gè)網(wǎng)絡(luò)。

由于簇頭節(jié)點(diǎn)不僅要完成通信，還要進(jìn)行數(shù)據(jù)融合傳輸信息量，所以簇頭節(jié)點(diǎn)的能量直接導(dǎo)致節(jié)點(diǎn)間的信息傳輸。這里將構(gòu)建水聲通信系統(tǒng)模型考慮節(jié)點(diǎn)在發(fā)送接收過程中確定節(jié)點(diǎn)傳輸數(shù)據(jù)所消耗的能量。引用文獻(xiàn)[12-13]中的能耗模型，定義如下:

發(fā)送節(jié)點(diǎn)的最低發(fā)送功率為：

(1)

其中，P0表示節(jié)點(diǎn)接收端正常接收一個(gè)數(shù)據(jù)包的最低功率；k為能量擴(kuò)展因子，通常取1.5；α為與頻率有關(guān)的能力衰減系數(shù)，通常α=10α(f)/10，α(f)為吸收損耗系數(shù)：

(2)

其中，f表示節(jié)點(diǎn)工作頻率。

節(jié)點(diǎn)能量衰減率為：

(3)

符號(hào)含義見表1。

表1 符號(hào)含義

3 基于FCM-L的分簇路由算法設(shè)計(jì)

3.1 基于FCM-L的模糊聚類模型

文中提出一種基于改進(jìn)的模糊C-均值聚類算法的水聲傳感器網(wǎng)絡(luò)分簇路由協(xié)議(FCM-L)。主要思想為將水聲傳感器節(jié)點(diǎn)作為分類對(duì)象，將其分為c個(gè)部分，其中每個(gè)部分都有一個(gè)聚類中心。這里需要利用FCM算法給出一個(gè)目標(biāo)函數(shù)來調(diào)整聚類中心，當(dāng)該目標(biāo)函數(shù)值小于給定閾值時(shí)，停止迭代，得到最后的聚類結(jié)果。設(shè)被分類對(duì)象的集合為X={x1,x2,…,xn}，X為節(jié)點(diǎn)集合，xi表示每個(gè)節(jié)點(diǎn)。

3.1.1 初始化聚類中心

考慮FCM算法對(duì)初始化聚類中心敏感，容易出現(xiàn)局部最優(yōu)，導(dǎo)致簇頭節(jié)點(diǎn)在網(wǎng)絡(luò)中分布不均勻。所以通過計(jì)算分析數(shù)據(jù)對(duì)象兩兩之間的距離與能量衰減率倒數(shù)的乘積，能量衰減越快，倒數(shù)越小，所以對(duì)于下式結(jié)果越小越好，以便得到一個(gè)較好的初始聚類中心。

(4)

比較分析找出兩個(gè)節(jié)點(diǎn)之間最小的β，創(chuàng)建新的數(shù)據(jù)對(duì)象集Y1，使這兩個(gè)節(jié)點(diǎn)歸入Y1，即(xi,xj)∈Y1。然后在原數(shù)據(jù)集中刪除xi，xj，原數(shù)據(jù)對(duì)象集變?yōu)?x1,x2,…,xn-2)，接著計(jì)算Y1中每一個(gè)節(jié)點(diǎn)與數(shù)據(jù)集X中每一個(gè)節(jié)點(diǎn)的距離與能量衰減率，找出最小的β，將該節(jié)點(diǎn)歸入Y1中，設(shè)置閾值γ，當(dāng)Y1中的節(jié)點(diǎn)個(gè)數(shù)達(dá)到一定閾值,新建數(shù)據(jù)對(duì)象集Y2，重復(fù)數(shù)據(jù)對(duì)象集Y1的形成過程，直到形成k個(gè)數(shù)據(jù)對(duì)象集。將這k個(gè)聚類中心作為K均值聚類算法的初始聚類中心。

于是把數(shù)據(jù)對(duì)象集X分成c類，設(shè)c個(gè)聚類中心向量構(gòu)成矩陣W：

(5)

3.1.2 構(gòu)造模糊相似矩陣

模糊分類中被分類的對(duì)象集合X中的對(duì)象xi以一定的隸屬度屬于某一類，因此每一類就認(rèn)為是對(duì)象集合X上的一個(gè)模糊子集，每一種模糊分類就是一個(gè)c×n的模糊矩陣R。使用夾角余弦法求出隸屬度rij，具體求解過程參考文獻(xiàn)[14]。每個(gè)rij∈[0,1]，于是構(gòu)造模糊相似矩陣R=(rij)c×n。

3.1.3 聚類求解

聚類準(zhǔn)則是通過不斷迭代使如下目標(biāo)函數(shù)達(dá)到最小值，得到最終的聚類結(jié)果:

(6)

(7)

(8)

3.1.4 確定最佳聚類數(shù)

通過上述聚類方法得到一組聚類數(shù)c，接下來將構(gòu)建一個(gè)有效性函數(shù)來確定一個(gè)最佳聚類數(shù)。根據(jù)文獻(xiàn)[16]，衡量聚類結(jié)果的好壞可根據(jù)簇內(nèi)的緊湊度和簇間的分離度決定，即簇內(nèi)的對(duì)象盡可能緊湊，簇間盡可能分離。具體步驟如下：

首先選取得到的不同聚類類別數(shù)c，利用簇內(nèi)緊湊度和簇間分離度決定最終聚類結(jié)果。

求解簇內(nèi)緊湊度：

(9)

求解簇間分離度：

(10)

根據(jù)緊湊度度量簇內(nèi)的緊致性，緊湊度越小，緊致性越好；分離度度量簇間的分離性，分離度越大，分離性越好。于是構(gòu)造以下聚類有效性函數(shù)：

(11)

最后參考CS(c)，它越小代表較好的聚類結(jié)果與CS(c)最小值相對(duì)應(yīng)的c值就是最佳的簇頭節(jié)點(diǎn)數(shù)。

3.2 算法描述

Step1：輸入對(duì)象集矩陣—水聲傳感器節(jié)點(diǎn)和節(jié)點(diǎn)特性指標(biāo)矩陣。

Step2：根據(jù)上述改進(jìn)算法計(jì)算初始化聚類中心。

Step3：構(gòu)造模糊相似矩陣R=(rij)c×n。

Step4：根據(jù)式7更新聚類中心w。

Step5：根據(jù)式8更新模糊分類矩陣R。

Step7：計(jì)算有效性函數(shù)CS(c)，選擇最小的CS(c)生成最佳聚類數(shù)c，利用聚類中心得到簇頭，與聚類中心最近的節(jié)點(diǎn)當(dāng)選簇頭節(jié)點(diǎn)，并根據(jù)聚類結(jié)果形成c個(gè)簇。

4 仿真實(shí)驗(yàn)

使用MATLAB進(jìn)行仿真實(shí)驗(yàn)并與基于模糊控制理論的CEFL方法進(jìn)行比較。仿真實(shí)驗(yàn)中將采用理想的環(huán)境，主要考慮傳感器節(jié)點(diǎn)發(fā)送數(shù)據(jù)、接收數(shù)據(jù)和進(jìn)行數(shù)據(jù)融合所消耗的能量，通過分析網(wǎng)絡(luò)中的總能量消耗和存活節(jié)點(diǎn)數(shù)目評(píng)定該協(xié)議的性能。

仿真實(shí)驗(yàn)是由100個(gè)水聲傳感器節(jié)點(diǎn)隨機(jī)分布在100 m×100 m的范圍內(nèi)。將從簇頭節(jié)點(diǎn)分布和節(jié)點(diǎn)平均剩余能量兩個(gè)方面比較文中算法與CEFL的性能。利用水聲通信能量模型，P0=2×10-3J/b作為數(shù)據(jù)能被接收的最低功率，融合功率Ed=5×10-4J/b，接收功率Pr=0.2×10-3J/b，每個(gè)節(jié)點(diǎn)的初始能量為0.5 J/node。

從圖1(圓圈表示簇頭節(jié)點(diǎn))可以看出，實(shí)驗(yàn)仿真100次后，CEFL分簇算法得到的簇頭節(jié)點(diǎn)分布不夠均勻，有些距離較遠(yuǎn)的節(jié)點(diǎn)可能無法與簇頭節(jié)點(diǎn)通信，容易使節(jié)點(diǎn)能耗不均勻，網(wǎng)絡(luò)生存周期比較短，這是由于CEFL算法中每個(gè)節(jié)點(diǎn)概率地決定是否成為簇頭，可能存在兩個(gè)簇頭彼此相鄰選擇的情況。而FCM-L算法采用改進(jìn)的模糊C-均值聚類算法初始化聚類中心，能有效控制分簇結(jié)果陷入局部最優(yōu)。從圖2可看出，同樣在仿真100次后，F(xiàn)CM-L選出的這5個(gè)簇頭節(jié)點(diǎn)相較于圖1分布均勻，而且簇頭節(jié)點(diǎn)的個(gè)數(shù)也比較接近最佳簇頭個(gè)數(shù)，相對(duì)來說能有效延長網(wǎng)絡(luò)生存周期。

圖1 CEFL簇頭選舉結(jié)果

圖2 FCM-L簇頭選舉結(jié)果

圖3是兩種算法的節(jié)點(diǎn)總能量消耗比較。FCM-L算法相較于CEFL算法，它的能量消耗趨勢相對(duì)緩慢一些，因?yàn)镕CM-L算法根據(jù)節(jié)點(diǎn)間的距離與能量衰減率得到初始化聚類中心，保證了簇頭節(jié)點(diǎn)能均勻分布在網(wǎng)絡(luò)中，并權(quán)衡了簇頭節(jié)點(diǎn)的能量消耗問題。所以可以看FCM-L算法得到的總能量消耗趨勢比較緩慢，而且能量消耗結(jié)束的輪數(shù)也有一定的延遲。

圖3 節(jié)點(diǎn)總能量消耗

圖4是兩種算法的死亡節(jié)點(diǎn)數(shù)量變化的比較?？煽吹皆诘?30輪左右，利用FCM-L算法第一個(gè)節(jié)點(diǎn)開始死亡，比CEFL算法推遲了140輪，而且在FCM-L算法中節(jié)點(diǎn)的死亡趨勢較為平緩，所以它的生命周期較CEFL算法延遲了500輪左右。這是由于FCM-L算法以合理的簇頭個(gè)數(shù)進(jìn)行分簇，得到一個(gè)負(fù)載均衡的網(wǎng)絡(luò)結(jié)構(gòu)，使得整個(gè)生命周期得到延遲。而CEFL算法產(chǎn)生的簇頭個(gè)數(shù)具有不穩(wěn)定性，導(dǎo)致節(jié)點(diǎn)死亡趨勢相對(duì)較快和不穩(wěn)定。

圖5是在不同簇頭個(gè)數(shù)下所有節(jié)點(diǎn)的總能量消耗比較。首先c=4時(shí)，明顯看出它在整個(gè)網(wǎng)絡(luò)中的能量消耗比c=5、c=6時(shí)的趨勢較快，而且在1 200輪時(shí)能量已消耗殆盡，簇頭個(gè)數(shù)為5和6時(shí)消耗趨勢相差不大，但是當(dāng)實(shí)驗(yàn)進(jìn)行到第800輪以后，簇頭個(gè)數(shù)為5時(shí)的能量消耗趨勢逐漸緩慢，充分說明如果能選出一個(gè)最優(yōu)的簇頭個(gè)數(shù)將有效地減緩能量的消耗。

圖4 死亡節(jié)點(diǎn)趨勢圖

圖5 不同簇頭個(gè)數(shù)的總能量消耗

5 結(jié)束語

提出了一種水聲傳感器網(wǎng)絡(luò)簇頭選舉方法，將水聲傳感器網(wǎng)絡(luò)的分簇過程建模為樣本空間的模糊聚類劃分問題。使用FCM-L對(duì)水聲傳感器網(wǎng)絡(luò)節(jié)點(diǎn)進(jìn)行聚類分簇，構(gòu)造一個(gè)有效性函數(shù)確定劃分最佳簇頭數(shù)。與CEFL相比，F(xiàn)CM-L算法產(chǎn)生的簇頭節(jié)點(diǎn)在網(wǎng)絡(luò)中分布更加均勻，從而實(shí)現(xiàn)了網(wǎng)絡(luò)壽命的顯著增加，進(jìn)一步改善了能量消耗。

由于在初始化聚類中心時(shí)，在每一次創(chuàng)建數(shù)據(jù)對(duì)象集的時(shí)候都要計(jì)算節(jié)點(diǎn)間的距離，雖然這一操作可以避免簇頭節(jié)點(diǎn)陷入局部最優(yōu)，但是也帶來了一定的計(jì)算復(fù)雜度。因此，在以后的研究中可以通過降低計(jì)算復(fù)雜度來重新設(shè)置初始化聚類中心，使得這種分簇路由算法更加適用于水聲傳感器網(wǎng)絡(luò)。