江萌萌，劉廣鐘

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

0 引 言

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

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

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

1 相關(guān)工作

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

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

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

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

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

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

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

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

(3)每個節(jié)點都有可能競選簇頭。

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

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

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

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

(1)

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

(2)

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

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

(3)

符號含義見表1。

表1 符號含義

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

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

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

3.1.1 初始化聚類中心

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

(4)

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

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

(5)

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

模糊分類中被分類的對象集合X中的對象xi以一定的隸屬度屬于某一類，因此每一類就認(rèn)為是對象集合X上的一個模糊子集，每一種模糊分類就是一個c×n的模糊矩陣R。使用夾角余弦法求出隸屬度rij，具體求解過程參考文獻[14]。每個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)建一個有效性函數(shù)來確定一個最佳聚類數(shù)。根據(jù)文獻[16]，衡量聚類結(jié)果的好壞可根據(jù)簇內(nèi)的緊湊度和簇間的分離度決定，即簇內(nèi)的對象盡可能緊湊，簇間盡可能分離。具體步驟如下：

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

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

(9)

求解簇間分離度：

(10)

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

(11)

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

3.2 算法描述

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

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

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

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

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

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

4 仿真實驗

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

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

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

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

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

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

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

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

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

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

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

5 結(jié)束語

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

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