改進的FCM算法在UASN分簇中的應用

江萌萌，劉廣鐘

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

0 引 言

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

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

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

1 相關工作

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

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

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

2 網絡模型

在分簇的UASN架構中，基站遠離傳感器節點并且是靜止的，簇頭節點負責控制簇內節點的協同工作，簇內節點向相應的簇頭發送數據，簇頭節點將收集到的數據信息壓縮融合處理后將其發送到基站。

文中對網絡模型做如下假設：

(1)假設水聲傳感器網絡是同構網絡，每個節點都有唯一的ID。

(2)主要針對二維靜態水聲傳感器網絡，不考慮節點移動性。

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

(4)每個節點都具有相同初始能量，具有數據融合功能，而且節點能根據距離的遠近來調整發射功率。

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

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

發送節點的最低發送功率為：

(1)

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

(2)

其中，f表示節點工作頻率。

節點能量衰減率為：

(3)

符號含義見表1。

表1 符號含義

3 基于FCM-L的分簇路由算法設計

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

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

3.1.1 初始化聚類中心

考慮FCM算法對初始化聚類中心敏感，容易出現局部最優，導致簇頭節點在網絡中分布不均勻。所以通過計算分析數據對象兩兩之間的距離與能量衰減率倒數的乘積，能量衰減越快，倒數越小，所以對于下式結果越小越好，以便得到一個較好的初始聚類中心。

(4)

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

于是把數據對象集X分成c類，設c個聚類中心向量構成矩陣W：

(5)

3.1.2 構造模糊相似矩陣

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

3.1.3 聚類求解

聚類準則是通過不斷迭代使如下目標函數達到最小值，得到最終的聚類結果:

(6)

(7)

(8)

3.1.4 確定最佳聚類數

通過上述聚類方法得到一組聚類數c，接下來將構建一個有效性函數來確定一個最佳聚類數。根據文獻[16]，衡量聚類結果的好壞可根據簇內的緊湊度和簇間的分離度決定，即簇內的對象盡可能緊湊，簇間盡可能分離。具體步驟如下：

首先選取得到的不同聚類類別數c，利用簇內緊湊度和簇間分離度決定最終聚類結果。

求解簇內緊湊度：

(9)

求解簇間分離度：

(10)

根據緊湊度度量簇內的緊致性，緊湊度越小，緊致性越好；分離度度量簇間的分離性，分離度越大，分離性越好。于是構造以下聚類有效性函數：

(11)

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

3.2 算法描述

Step1：輸入對象集矩陣—水聲傳感器節點和節點特性指標矩陣。

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

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

Step4：根據式7更新聚類中心w。

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

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

4 仿真實驗

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

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

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

圖1 CEFL簇頭選舉結果

圖2 FCM-L簇頭選舉結果

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

圖3 節點總能量消耗

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

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

圖4 死亡節點趨勢圖

圖5 不同簇頭個數的總能量消耗

5 結束語

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

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