基于模糊C均值聚類及群體智能的WSN分層路由算法

戚 攀，包開陽，馬皛源

(1.中國科學院 上海高等研究院，上海 201210； 2.中國科學院大學，北京 100049)(*通信作者電子郵箱maxy@sari.ac.cn)

0 引言

當前，無線傳感器網絡(Wireless Sensor Network， WSN)在很多領域得到了大量的應用，比如環境監控、病患管理、工業自動化[1]。它的主要功能是借助大量部署具有無線通信能力的傳感器節點并自組織形成網絡，最終將傳感器節點感知到的信息進行處理后通過無線通信方式發送至基站，從而使監測者了解監測區域的信息。然而廉價微型的傳感器節點的存儲、計算能力通常非常有限，特別是由于使用電池供電，節點自身能量有限，在戰場火場等應用環境下又不可能及時地更換電池進行能量補充[2]，因此，在能量有限的前提下，要有效地延長網絡的生存時間就需要一個能量高效的無線傳感網路由算法。在已有的眾多能量高效路由算法當中，基于分簇的分層路由已經被證明是提高網絡能量利用效率最有效的技術之一[3]。

現有的分層路由算法大部分都借鑒了低功耗自適應分簇(Low Energy Adaptive Cluster Hierarchy， LEACH)路由算法[4]的思想。LEACH的核心思想是將傳感網進行分區，每個分區內所有傳感器節點成為一簇，每簇選取一個節點作為簇頭。每次收集信息時先由普通節點將感知到的信息發送至所屬分簇的簇頭，簇頭將接收到的數據進行融合去除冗余后通過單跳或者多跳的方式發送至基站。這樣一次完整的數據采集過程稱為一輪，網絡的生存時間通過運行輪數來計算，稱為生命周期。

基于分層路由算法的機制，設計一個能量高效分層路由算法需要解決三個關鍵問題：1)分簇；2)簇頭選取；3)消息發送路徑。LEACH算法采用的“簇頭隨機，就近入簇，單跳至基站”的解決方案。由于簇頭是隨機選取的，完全沒有考慮節點的剩余能量和簇頭的個數，LEACH算法有可能選取低能量的節點作為簇頭，簇頭節點相對于普通節點要消耗更多的能量，這樣就容易導致低能量節點過快地死亡，形成“死區”。LEACH算法在成簇的時候是通過普通節點就近入簇的方式完成的，這樣就容易形成不均勻的“極大、極小簇”，其中的“極大簇”的簇頭節點負載過大，容易死亡。在LEACH算法中簇頭通過單跳的方式直接與基站通信，在距離較遠的情況下簇頭的能量消耗會急劇地增加。此外，LEACH算法每輪都需要重選簇頭，新簇頭被選出來后都需要進行廣播告知新簇頭信息，浪費了大量能量。針對LEACH算法存在的這些問題，后續出現的分層路由算法提出了很多解決方案。改進的低功耗自適應分簇(Improved Low Energy Adaptive Cluster Hierarchy， I-LEACH)路由算法[5]將檢測區域均勻地分為五個分區，每個分區內的所有節點成為一簇，在一定程度解決了成簇不均勻的問題，但分區方式過于簡單，沒有考慮網絡內節點具體的分布情況和相對于基站的位置。能量高效的非均勻分簇(Energy-Efficient Uneven Clustering， EEUC)路由算法[6]在選取簇頭時考慮了節點相對于基站的位置，離基站近的節點有更大概率擔任簇頭；但是沒有考慮簇頭相對于簇內普通節點的位置，沒有優化簇內通信的能量消耗。能量負載均衡的簇頭選取(Leader Election with Load balancing Energy， LELE)路由算法[7]在選取簇頭時考慮了節點的剩余能量，剩余能量大的節點更容易當選簇頭。基于最優簇數和改進引力搜索的(Optimal Number of Clusters and Improved Gravitational Search, ONCIGS)路由算法[8]在簇頭與基站的通信過程中采用簇頭間多跳轉發的方法，避免了簇頭與基站距離過大時單跳通信造成的巨大發射能耗。經過修改的低功耗自適應分簇(MODified Low Energy Adaptive Cluster Hierarchy， MODLEACH)路由算法[9]為了避免每輪都需重選簇頭的問題，使用了一種使用閾值控制簇頭重選的方法，只有當簇頭節點的剩余能量下降到設定的閾值以下時才會觸發簇頭重選。

以上的這些研究針對分簇路由算法的三個關鍵問題提出了一些非常值得參考的解決方法，但是也還存在一些問題。比如LELE算法和EEUC算法的分簇結果不夠合理，ONGIGS算法對簇頭選取的考慮還不夠全面。經過分析后，為了盡可能地降低網絡能耗并延長其生命周期，本文提出一種基于模糊C-均值(Fuzzy C-Means， FCM)聚類和群體智能算法(人工蜂群(Artificial Bee Colony, ABC)算法、蟻群優化(Ant Colony Optimization, ACO)算法)的WSN分層路由算法(WSN hierarchical routing algorithm based on Fuzzy C-Means clustering and Swarm Intelligence， FCM-SI)。在分簇階段，針對網絡的實時情況動態地確定最優分區數量，并通過FCM實現網絡動態均衡的分簇；在簇頭選取階段，使用節點的剩余能量、節點到基站的距離、節點到所在分簇內其他節點的平均距離三個特征作為參數構造適應函數，采用人工蜂群算法計算每個分簇內最適合擔任簇頭的節點的位置；在簇間路由階段，將最小能量消耗作為目標函數，采用最擅長執行路徑的蟻群優化算法搜索最小消耗的簇間多跳數據轉發路徑。仿真結果顯示，FCM-SI可以明顯地降低網絡能量消耗，延遲第一個節點和最后一個節點的死亡時間，有效地延長了網絡的生命周期。

1 系統模型

1.1 網絡模型

本文對傳感網網絡作出如下假設：

1)節點隨機分布在監測區域內，所有節點靜止不動，基站位于監測區域外；

2)節點數為N，監測區域面積為M×M；

3)所有節點的能量相等并且有限，基站能量無限；

4)節點可以感知自身位置，且可以根據相互間的距離控制發射功率；

5)所有節點具有相同屬性和性能，都可以擔任普通節點或者簇頭，簇頭節點會進行數據融合去除冗余。

1.2 能量模型

本文使用了和經典的LEACH算法相同的一階無線電模型。設Eelec為節點每發送或接收1比特消息消耗的能量；εfree為節點放大器在自由空間模型下的傳輸增益，εmulti-path為放大器在多徑衰落模型下的傳輸增益；l為消息長度,單位為比特；d為消息傳輸距離；dgate為傳輸距離閾值，當消息傳輸距離小于dgate時采用自由空間模型,否則使用多徑衰落模型。一個節點經過距離d的發送l比特數據的傳輸功耗為：

(1)

接收l比特數據功耗為：

Erx(l)=lEelec

(2)

由式(1)可知：

(3)

設定Eelec=50 nJ/b，εfree=10 pJ/(b·m2)，εmulti-path=0.001 3 pJ/(b·m4)。簇頭進行數據融合消耗的能量為n·m·EDA。其中n為分區的節點數；m為每個節點發送的消息長度,單位為比特，EDA=5 nJ/(b·signal)。

2 FCM-SI

2.1 動態分簇

為了降低簇內普通節點與簇頭通信的能耗，本文使用了模糊C均值聚類進行分簇，成簇均勻并優化了簇內節點與簇頭間的距離。由于網絡狀態隨著運行不斷變化，存活節點數會逐步減少，導致最佳簇頭數也是動態變化的。為了取得最佳的網絡性能，在網絡運行的過程中根據網絡當前狀態動態地控制簇頭數。

2.1.1 模糊C均值聚類

模糊C均值(FCM)聚類是一種無監督聚類算法，這個聚類方法由Dunn在1973年首次提出[10]，并在1981年由Bezdek[11]改進之后已經成為了一種常用的模式識別方法。FCM的目標是使得數據點到所屬分類中心的距離的和最小化，利用FCM的這一特性將其應用到無線傳感網的分簇當中，就可以將網絡中的節點分為幾個最緊密的簇，優化簇內節點到簇頭間的相互距離，有效地降低簇內通信消耗的能量。不同于常見的C-均值和K-均值聚類這種非此即彼的硬劃分方法，FCM是一種模糊劃分方法，這使得FCM能處理復雜的數據分布情況[12]。該聚類算法的目標函數為：

(4)

其中：xi為第i個數據點；cj為第j個聚類中心；uij為數據點xi相對于分類j的歸屬度；m為權重系數，一般按照經驗值取為2；N為數據點數量；C為分類數量；‖xi-cj‖為數據點xi到聚類中心cj的距離，一般采用歐氏距離。聚類的過程就是通過迭代使目標函數最小化的過程。每次迭代，歸屬度矩陣的更新公式為：

(5)

聚類中心坐標的更新公式為：

(6)

迭代結束條件為：

(7)

其中：k為迭代步數，ε為迭代終止閾值。算法的具體步驟描述如下：

1)輸入數據點集合X={x1,x2,…,xi,…,xN}T和分類數量K,并初始化歸屬度矩陣U(0)。

2)第k次迭代：按式(6)使用歸屬度矩陣計算聚類中心坐標C(k)。

3)按式(5)更新歸屬度矩陣U(k)、U(k+1)。

4)如果滿足式(7)的條件則停止迭代算法完成；否則轉到第2)步繼續迭代。

2.1.2 基于FCM的動態分簇

由于FCM需要先確定分類數量，應用到網絡分簇就需要在分簇之前根據網絡特征確定最合理的簇頭數量。根據上面介紹的網絡模型和能量模型，整個網絡運行一輪消耗的能量[13]為：

Eone_round≈N(E·l+εfree·l·M2/(2πk))+

(8)

其中k為簇頭數。對k求偏導，并令其值為零，可求得使得功耗最低的最優簇頭數為：

(9)

由式(9)可知，最優簇頭數與存活節點數的開方成正比。在初始節點數為100、監測區域長寬為100 m的初始條件下可求得最優簇頭數為5。然而隨著網絡的不斷運行，開始出現死亡節點，存活節點數開始下降，最優簇頭數也對應減少，需要再次分簇；例如當存活節點數減少到81時，最優簇頭數變為4，直到最終整個網絡只有一個簇。

另外，不同于很多分層路由算法每一輪都需要重新分簇，在本文提出的FCM-SI規定一個節點的剩余能量大于最小簇頭能量ECH_min才有可能當選為簇頭：

ECH_min=Eone_round+Eselect+Edivide

(10)

其中：Eone_round為簇頭運行一輪所需的能量，Eselect為廣播一次重新選擇簇頭的控制包的能量，Edivide為廣播一次重新分簇的控制包的能量。在FCM-SI中，當某個簇頭節點的能量達到動態閾值時，該簇頭(編號i)會向其他所有簇頭廣播一個控制包，通知其他簇頭運行三參數人工蜂群(ABC)算法重新選擇簇頭。Eselect就是廣播這個控制包需要的能量。在新的簇頭被選取出來后，如果這些新的簇頭都和原來的都是同一批就說明當前網絡中某個分簇內部已經沒有節點適合成為簇頭,那么簇頭(編號i)需要向其他所有節點廣播一個控制包，通知所有節點開始重新分區。Edivide就是廣播這個控制包需要的能量，所以，只有剩余能量大于最小簇頭能量ECH_min的節點才能當選為簇頭。然而一旦FCM完成一次分簇后，那么直到下一次分簇之前每個簇包含的節點都不再變化。這樣就有可能出現某個簇內的所有節點的剩余能量都不足以擔任簇頭的情況，這種情況下也需要再次分簇。

所以觸發網絡重新分簇的條件是出現以下兩種情況之一：1)存活節點數下降到最優簇頭數需要變化時；2)某個簇內的所有節點的剩余能量都小于擔任節點的最小能量時。當觸發重新分簇后，再次運行FCM生成新的分簇，這樣就完成了整個網絡生命周期內的動態分簇過程。

2.2 簇頭選取

在網絡的初始化階段，最初由基站在每個分簇內隨機選取一個候選簇頭。同一分簇內的每個節點都可以相互感知對方的位置和能量信息。隨后，由候選簇頭采用ABC算法選取正式的簇頭。候選簇頭完成簇頭選取后要廣播一短信息，將簇頭的坐標、簇頭所屬的分簇編號以及簇頭的ID告知所有節點。普通節點收到廣播信息后通過自身所屬的分簇編號與簇頭進行匹配入簇，簇頭節點也需要相互存儲其他簇頭節點的位置和編號，用于簇頭間消息傳遞路徑的計算。

2.2.1 人工蜂群算法

人工蜂群(ABC)算法[14]是一種受自然界中蜜蜂采蜜行為啟發的群體智能算法，蜂群中的蜜蜂分為不同的幾個工種，每個工種承擔不同的工作，在工作的過程中完成信息的交流和分享，從而在有限的時間復雜度內大概率找到問題的最優解。這個算法在解決全局優化問題方面展現出了非常強的能力。

ABC算法將人工蜂群中的蜜蜂分為三種：雇傭蜂、跟隨蜂和偵察蜂。雇傭蜂搜索蜜源并與跟隨蜂分享蜜源信息，比如蜜源的花蜜量，蜜量大的蜜源代表具有更大的適應值，代表更好的解。完成和所有雇傭蜂的蜜源信息分享后，跟隨蜂會按照一定概率挑選一個蜜源并基于這個蜜源尋找新的蜜源，蜜源的蜜量越大被跟隨蜂選擇的概率也就越大。偵查蜂的作用是隨機地尋找新的蜜源，一旦偵查蜂和跟隨蜂找到了新的高質量蜜源就會轉換成雇傭蜂。

在算法的初始化階段，ABC首先生成包括三種蜜蜂的種群和它們的蜜源位置。雇傭蜂的數量和跟隨蜂的數量相同，每個雇傭蜂對應一個蜜源。每個蜜源的位置稱為一個解，蜜源的蜜量是這個解的適應值。每個解xi(i=1,2,…,n)是一個d維的解向量，n是蜜源的數量。每只雇傭蜂會記住當前對應蜜源的位置并生成一個新的蜜源，如果新發現的蜜源的適應值要好于舊蜜源，雇傭蜂將會存儲新蜜源的位置坐標并刪除舊蜜源的位置坐標；否則繼續保持舊蜜源的位置坐標不變。雇傭蜂尋找新蜜源的公式如下：

xij′=xij+rij(xij-xkj);i≠k,r∈[-1,1],

j∈[1,2,…,d]

(11)

其中rij是一個隨機系數，也就是用另一個蜜源對當前蜜源的第j維分量作用，從而完成在當前蜜源周圍的搜索。當所有的雇傭蜂完成一次發現和位置更新后，就會與跟隨蜂分享蜜源信息。跟隨蜂得到蜜源信息后會按照一定概率選擇一個蜜源，具體的概率計算公式如下：

(12)

其中fitnessi是解xi的適應值，可以看到一個適應值更大的蜜源將會吸引更多數量的跟隨蜂。選擇蜜源之后，跟隨蜂同樣要按照式(11)搜索新的蜜源。如果經過多次發現后，在規定的有限的步驟內某一個蜜源的適應值沒有改善，那么將丟棄這個蜜源，蜜源對應的雇傭蜂身份改為偵察蜂。新出現的偵查蜂按照如下公式發現新的蜜源：

?i∈(1,2,…,n)

(13)

其中：lb,ub分別為解的第j分量的上下界，r是一個-1到1之間的隨機數。如果新產生的解的分量超過了上下界，那么直接取值為被超過的界值。

綜上，ABC算法的流程如下：

1)初始化蜜源和雇傭蜂的位置坐標xi(i=1,2,…,n)。

2)雇傭蜂根據式(11)發現新蜜源，并計算適應值，執行貪婪算法更新蜜源位置。

3)跟隨蜂根據雇傭蜂分享的信息按照一定概率選擇蜜源，并使用雇傭蜂同樣的方式發現新蜜源。

4)如果某個解達到廢棄條件即達到最大發現次數(本文定義為20)后解沒有改善，則根據式(13)產生新解。

5)判斷是否達到終止條件即達到最大迭代次數(本文定義為20)，如果達到輸出最終解；否則返回步驟2)。

使用ABC算法的關鍵在于適應函數的定義，也就是怎樣去衡量一個解的優劣，將ABC應用到簇頭的選取需要結合無線傳感網的具體特征去定義適應函數。下面將介紹FCM-SI定義適應函數并完成簇頭選取的過程。

2.2.2 基于ABC的簇頭選取

FCM-SI在選取簇頭時主要考慮了節點的三個特征：節點的剩余能量、節點到基站的距離、節點與其所在簇內的普通節點之間的緊密程度。由于簇頭節點需要擔任更多的數據收發和融合任務，相對普通節點需要消耗更多的能量，所以一般情況下選擇剩余能量多的節點作為簇頭能有效地改善網絡能量均衡性能。另外，簇頭到基站的距離越小，簇頭將數據發送至基站消耗的能量也相應越小；簇頭到所在分簇其他節點的平均距離越小，擔任簇頭后普通節點發送數據給它時消耗的能量就會越小，所以簇頭的選取問題就是一個通過改變節點位置(選取不同的節點)來改善上述三個參數指標的多參數優化問題，針對多參數優化求解，ABC算法是一種低復雜度的高效的求解方法。一個簇內包括的每個節點都是一個可能解，基于上述三個參數構造一個適應函數，計算節點擔任簇頭的適應值并將每個節點都建模為一個ABC算法中的蜜源模型，就可以采用ABC算法在簇內搜索最適合擔任簇頭的節點，從而完成簇頭選取。基于以上分析，本文將簇頭選取的適應函數定義如下：

fitness(i)=af1(i)+bf2(i)+cf3(i)

(14)

(15)

(16)

(17)

其中：a,b,c為權重因子，控制三個參數的重要程度；f1是候選節點的剩余能量與所屬簇內所有節點的平均能量的比值，體現了剩余能量對簇頭選取的影響；f2為候選節點到基站的距離與所屬簇內所有節點到基站距離的平均值的比值；f3為候選節點到所屬簇內其他節點距離的平均值與其他節點擔任候選節點到其他節點距離平均值的比值，體現了簇頭節點在區間內與普通節點的緊密程度。f2、f3體現了節點位置對簇頭選取的影響。其他參數中：n為節點i所在分簇的節點總數，Eres(i)為節點i的剩余能量，dtoBS(i)為節點i到基站的距離，d(j,k)為節點j到節點k的距離。在網絡的初始化階段定義a=b=c=1/3，也就是三個參數的重要程度相同。然后隨著網絡的運行，節點能量不斷地降低，成為更加重要的瓶頸參數，所以隨著網絡的運行將f1的權重動態增大。本文將a、b、c定義為：

(18)

b=c=(1-a)/2

(19)

可以看到，經過以上的定義之后，隨著網絡的運行f1的權重從1/3動態增加到2/3,剩余能量大的節點有更大概率成為簇頭，有利于優化整個網絡的能量負載均衡。

2.3 簇間多跳路徑搜索

為了降低簇頭能耗并均衡簇間負載，采用改進的蟻群優化算法搜索簇頭至基站的最優路徑，簇頭與基站通信時，會沿著搜索到的最優路徑簇間多跳將數據轉發至基站。

2.3.1 蟻群優化算法

和人工蜂群算法相同，蟻群優化(ACO)算法[15]也是一種啟發式群體智能算法，該算法主要是受到螞蟻種群的覓食行為的啟發。自然界中的螞蟻在自身沒有視覺也沒有其他外界信息的情況下可以通過個體間釋放信息素進行消息傳遞，協作搜索蟻巢到食物源之間的最短路徑，構成了一種典型的集體尋優行為。該算法尤其擅長解決路徑搜索類問題，已經被成功地應用于求解旅行商問題這類NP(Non-deterministic Polynomial)問題，取得了非常好的實驗效果。經過研究發現，螞蟻在搜尋食物源時，會在經過的路徑上釋放信息素，沒有視覺能力的螞蟻通過感知周圍的信息素決定行動的方向，并有更大概率向信息素濃度高的方向移動。信息素會隨著時間逐步揮發，一般情況下，在單位時間內越短的路徑經過的螞蟻越多，該路徑上的信息素濃度也越大，吸引更多的螞蟻。由于這種正反饋機制，經過一段時間后所有的螞蟻都將選擇這條最短的路徑[16]。

初始化時，所有路徑的信息素濃度初始化為τ0，螞蟻種群數量為m。螞蟻被隨機地投放在某個起點位置，然后開始逐個遍歷位置點，直到將所有位置點遍歷完畢。位于位置點i的螞蟻下一步向位置點j移動的概率為：

(20)

其中：τij(t)表示i、j之間路徑的信息素濃度，等于i、j之間的距離的倒數；α表示信息素的相對重要程度；β表示啟發式因子的相對重要程度；Jk為下一步可以選擇的目的地合集，起到禁忌表的作用。所有的m只螞蟻都完成一次遍歷后，找出其中最短的路徑，按照路徑長度更新信息素，信息素更新公式為：

τij(t+1)=(1-ρ)·τij(t)+Δτij

(21)

(22)

(23)

其中：Q為正常數，Lk表示本次遍歷到的最短路徑的長度，ρ為揮發因子。也就是只有屬于最短路徑的邊上的信息素會得到加強，正是這個正反饋機制使得ACO有著比模擬退火和遺傳算法更快的收斂速度。

2.3.2 基于ACO的多跳路徑搜索

在無線傳感網中節點的發射功率與發射距離成正相關關系，簇頭間多跳轉發路徑長度越短，一般情況下消耗的能量也越小，所以ACO非常適合用于搜索最小能耗簇間轉發路徑，降低網絡能耗。此外，為了使得網絡的能量負載更加均衡，同時將簇頭節點的剩余能量也考慮到路徑搜索的過程中，使得搜索到的路徑有更大概率經過剩余能量高的簇頭節點，避免低能量簇頭承擔過多轉發任務過快死亡。將簇頭節點的剩余能量考慮進ACO的信息素項中后，信息素項的形式為：

(24)

其中Eres(j)為簇頭j的剩余能量，那么ACO融合剩余能量參數后的轉移概率計算公式為：

(25)

螞蟻通過改進后的轉移概率公式搜索簇間多跳路徑，簇間通信通過搜索到的路徑進行，在減少能耗的同時也兼顧了能量負載均衡。

3 實驗仿真與結果分析

為了驗證FCM-SI對網絡性能的改善，本文采用了Windows平臺下的Matlab 2012a版本對FCM-SI、基于蟻群優化的LEACH(LEACH based on ANT， ANT-LEACH)算法、基于人工蜂群優化的LEACH(LEACH based on ABC， ABC-LEACH)算法和I-LEACH算法進行仿真分析。仿真網絡環境設定如下：網絡覆蓋面積為100 m×100 m，節點數為100，基站位置位于(50,175)。網絡環境參數如表1，其他算法參數如表2。

表1 網絡環境參數

3.1 成簇結果

FCM-SI與其他三個算法的成簇結果對比如圖1所示。可以看到，ABC-LEACH算法使用了ABC算法選擇簇頭，使得簇頭的位置比較合理；但是，由于ANT-LEACH是通過先隨機產生簇頭，普通節點再入簇的方法成簇，簇的數量和大小都不確定，不均勻的分簇容易導致網絡的負載不均衡。I-LEACH算法使用了均勻分區的方法進行分簇，使得簇的大小比較均勻，數量也更加合理；但是，由于該算法在選擇簇頭時只考慮了節點的剩余能量，導致選出的簇頭的位置不夠合理。ABC-LEACH對LEACH算法的主要改進是在簇間路由階段使用ACO搜索多跳路徑，在成簇階段的表現則沒有進行優化，成簇的均勻性和簇頭的位置都不夠合理。本文提出的FCM-SI使用了FCM聚類算進行分簇和三參數的ABC算法選取簇頭，成簇的均勻性和簇頭的位置比起三個比較算法都更加合理。

表2 算法參數

圖1 成簇結果對比

3.2 動態分簇

網絡的動態分簇過程如圖2所示。很多算法通過計算的最優簇頭數在初始化確定簇的數量并在后面的運行過程中一直沿用不再改變；但是隨著網絡的運行，開始出現死亡節點，存活的節點數也就是網絡規模是不斷變化的，與網絡規模直接相關的最優簇頭數也應該是動態變化的，所以，FCM-SI采取了動態分簇的策略，根據網絡的實時情況，動態地調整最優的簇頭數量。圖2顯示了隨著網絡運行，存活節點數開始減少，簇頭的數量從最初的5個動態地調整為1個的過程。

3.3 網絡生命周期

一般將從網絡開始運行到最后一個節點死亡(Last Node Dies， LND)期間的運行輪數稱為網絡的生命周期，此定義下的FCM-SI與另外三個算法的生命周期對比結果如圖3所示。由圖3可知，ABC-LEACH、ANT-LEACH、I-LEACH、FCM-SI的生命周期分別為624輪、689輪、799輪、1 031輪。相比三個比較算法，FCM-SI分別延長了65.2%、49.6%和29.0%的生命周期。

圖2 動態分簇過程

除了將網絡生命周期定義為LND之外，根據網絡的具體應用要求，也有研究將網絡運行截止到出現第一個死亡節點(First Node Dies， FND)的運行輪數或者網絡運行截止到一半節點死亡(Half Node Dies， HND)的運行輪數定義為網絡生命周期。FCM-SI與三個對比算法在FND、HND和LND三種定義下的生命周期表現如圖4所示。可以看到，在三種生命周期定義下，FCM-SI都大幅度地延長了網絡的生命周期。

圖3 生命周期對比

上面的數據表明，相比其他三個算法，FCM-SI可以有效地延長網絡的生命周期。這是因為FCM-SI基于最優簇頭數和FCM聚類算法實現了比較均勻的分簇，使得簇頭的負載比較均衡。而且由于簇頭與基站之間的通信是通過蟻群優化算法搜索到的最優路徑多跳完成的，進一步節省了簇頭節點的能量，在搜索路徑時還考慮了簇頭間的負載均衡，避免了某個簇頭承擔過多轉發任務能量下降過快，這些能量均衡方法在很大程度上延遲了第一個節點的死亡時間。在選擇簇頭時考慮了簇頭節點到普通節點的距離，減少了普通節點發送數據到簇頭消耗的能量，從而在整體上減少了網絡的能耗，使得FCM-SI在FND、HND和LND三種生命周期定義下的表現都是最優的，這說明FCM-SI相比三種對比算法具有更好的通用性。

圖4 三種生命周期對比

3.4 網絡能量消耗

FCM-SI與另外三個算法的網絡能量消耗情況對比結果如圖5所示。從圖5可以看出，在網絡的整個運行過程中，FCM-SI的網絡能量下降都是最慢的。這就說明，相對于其他三個算法，FCM-SI能明顯地降低網絡的能量消耗。這得益于在分簇階段由FCM算法形成的分簇中節點到簇中心的距離是最小的，在選取簇頭的時候又考慮了簇頭到簇中心的距離，使得普通節點與簇頭間簇內通信的能量消耗有效地降低。而簇間通信的最優路徑搜索又進一步降低了網絡的能量消耗。

3.5 網絡數據量

無線傳感網的主要功能就是感知并發送環境數據，網絡的數據量是衡量網絡性能的一個重要指標。FCM-SI與其他三個算法的數據發送總量比較結果如圖6所示。可以看到：前期因為存活節點數都相同，四個算法的數據發送量曲線重合；后期得益于存活節點數比較多的優勢，FCM-SI的信息發送總量明顯多于其他三個算法。基站接收數據總量比較結果如圖7所示。基站最終接收到的數據量直接影響網絡對其監測區域的感知的有效程度。可以看到，從網絡開始運行到最后一個節點死亡，FCM-SI的基站接收數據總量也始終多于其他三個算法。

圖5 網絡能量消耗對比

圖7 基站接收數據總量對比

4 結語

針對已有的一些WSN分層路由算法在分簇、簇頭選取和簇間路由搜索等方面的不完善導致網絡生命周期受限、網絡能量高效性不夠的問題，本文提出了一種基于模糊C均值聚類和群體智能的分層路由算法(FCM-SI)。首先根據實時的網絡環境計算最優簇頭并利用FCM聚類算法實現實時動態的分簇；然后，采用三參數的ABC算法選取合理的簇頭；最后，在簇間路由階段采用綜合考慮能量高效和能量均衡的ACO算法搜索最優簇間多跳路徑。仿真結果表明，FCM-SI能有效地降低網絡能耗，并改善網絡能量負載均衡，明顯地延長網絡生命周期。雖然本文在簇頭選取和簇間路徑搜索的過程中都考慮到了節點的能量負載均衡，但是通過動態分簇過程還是可以看到靠近基站的節點因為承擔了比較多的轉發任務，能量下降速度明顯比其他區域的節點要快；另外本研究是在固定規模固定節點的條件下進行，還沒有考慮到網絡規模和移動節點對網絡性能的影響；所以，下一步的工作將集中于進一步改善網絡能量負載均衡和優化算法在多種網絡規模下的表現，并參考無線通信移動平臺[17-18]的相關技術使算法適用于存在移動節點的無線傳感網。