基于改進S-FCM和PSO算法的WSN分簇路由算法

孫愛晶，朱開磊

(西安郵電大學 通信與信息工程學院，陜西 西安 710121)

無線傳感器網絡(Wireless Sensor Network，WSN)由大量低功耗、能量有限的微型的傳感器節點組成，多用于智能家居、智慧農業等場景[1-2]。傳感器節點通過無線鏈路構建自組織網絡，并將感知數據發送至簇首或者基站[3]。傳感器節點能量有限且通常被隨機布置在某些環境惡劣區域，對其進行充電是不現實的[4]。因此，延長網絡生命周期成為當前的熱門研究課題。

針對延長網絡生命周期的問題，研究者們提出了許多基于簇結構的層次性網絡路由協議[5-6]。文獻[7]提出的經典的低功耗自適應集簇分層(Low Energy Adaptive Clustering Hierarchy,LEACH) 協議以循環的方式隨機選擇簇首，使各個節點都有機會成為簇首均衡網絡負載。然而，LEACH協議中簇首的選舉沒有考慮節點剩余能量，當能量低的節點被選為簇首，會加速網絡的死亡。針對LEACH協議存在簇首選舉不合理的問題，文獻[8]提出的LEACH-improve協議將剩余能量因子、間距因子和密度因子融入到傳統LEACH閾值計算公式中，使選舉的簇首更具合理性，網絡生命周期得以提高，但仍會出現極小、極大簇，不利于簇內節點負載均衡。文獻[9]提出了非均勻分簇協議 (Energy-Efficient Uneven Clustering,EEUC)，候選簇首通過使用非均勻的競爭范圍構造大小不等的簇，使靠近基站的簇的規模小于遠離基站的簇，延長了網絡生命周期。文獻[10]將FCM算法(Fuzzy C-means,FCM)和模糊邏輯結合起來，先用FCM算法得到均勻分簇，然后結合能量、距離等因素利用模糊邏輯在簇內選舉簇首，有效地均衡了節點負載，但該算法未對簇首規劃路由，不利于均衡簇首負載。文獻[11]使用遺傳算法優化FCM的初始聚類中心以獲取最優分簇，并結合節點能量及距離因子選舉簇首。但在簇首輪換階段，只說明網絡系數取值過大過小都會加速網絡能量消耗，并未給出最優網絡系數的計算方式和實驗數據。FCM算法雖然得到了均勻分簇，但在大規模節點部署環境下，由于其收斂速度緩慢，不適用于規模大且對網絡實時性要求高的環境。文獻[12]提出了一種基于凝聚嵌套(Agglomerative Nesting,AGENS)聚類的能量均衡WSN路由優化算法(An Energy-Balanced WSN Routing Optimization Algorithm based AGNES Clustering,EBRAA)。該算法首先使用AGENS分簇，然后結合簇內節點的剩余能量和節點與基站距離及兩者權重因子，完成分布式簇首選舉，最后采用改進后的Dijkstra算法產生簇首間最短路徑的多跳路由。但是，并未給出最優權重的證明過程，也未考慮中繼節點的負載因素，這會影響簇首選舉的合理性及加速中繼節點死亡。

為了改善FCM算法在網絡分簇時收斂速度緩慢、簇首選舉不合理和遠端簇首能耗大的問題，在LEACH協議的分簇思想基礎上擬提出基于改進抑制式模糊C-均值和粒子群算法的WSN分簇路由算法(WSN Clustering Routing Algorithm based on Improved S-FCM and PSO Algorithms，CRIS-FCMP)。分簇階段，利用抑制式模糊C-均值算法的目標函數改進抑制率，使改進的抑制式模糊C-均值(Improved Suppressed Fuzzy C-means，IS-FCM) 算法既能提高收斂速度又能保持良好分簇特性；簇首選舉階段，依據簇內節點能量關系構建節點動態能量閾值選舉簇首；數據傳輸階段，依據中繼節點具有高剩余能量、位置適中等特點設計路徑選擇適應度函數，并結合粒子群算法(Particle Swarm Optimization,PSO)為遠端簇首搜尋最優路由路徑。

1 系統模型

1.1 網絡模型

為了均衡網絡中節點的能耗，對網絡中的節點進行分簇，之后在分簇中選舉簇首，最后為簇首規劃路由。涉及的傳感器網絡模型如圖1所示。

圖1 傳感器網絡模型

圖1中基站位于監測區域中心且假設具有無限大的處理能力和穩定能量供應。白圈代表傳感器節點，這些節點隨機布設在監測區域內，布設后將不再移動，每個節點由一個全局唯一的ID標識。此外，這些節點還擁有如下特點：所有節點初始能量相同且同構；節點能夠根據接收信息的信號強度判斷與發送者的近似距離，從而選取自身發射功率；節點可以感知自身位置和其他節點及基站位置，并可以周期性感知監測數據并發送至相應簇首；節點可以感知自己的剩余能量，且有存儲、查詢、計算和數據融合能力。

1.2 能耗模型

無線傳感器網絡的節點能耗主要來自于數據的收發，采用與文獻[13]相同的網絡能耗模型進行節點間的通信。節點信道模型的選擇主要由其收發距離d決定。節點發送l位數據至距離為d的節點消耗的能量為

(1)

節點接收融合lbit數據消耗能量的表達式為

Erx=lEelec+lEda

(2)

式中，Eda表示融合1 bit數據消耗的能量。

結合網絡模型及能耗模型的描述，改進路由算法將從均勻分簇選舉合理簇首和為簇首規劃合理路由的方向進行設計。具體路由算法的改進方案將在下文中進行詳細闡述。

2 改進的抑制式模糊C-均值算法

抑制式模糊C-均值S-FCM(Suppressed Fuzzy C-means，S-FCM)算法[14]由范九倫于2003年提出，S-FCM算法是FCM算法[15]的拓展。考慮該算法具有快速收斂和良好分類的優點，將其應用到WSN分簇中。

FCM算法是通過計算每個節點對類中心的模糊隸屬度、極小化FCM的目標函數得到最優分簇。FCM目標函數表示為

(3)

(4)

(5)

由于FCM算法迭代速度慢，在大規模節點集合環境下，聚類需要消耗大量時間。通過對隸屬度進行合理的修正，可以保證合理分類的同時加快算法收斂速度。對每一個節點xj，節點j在所有類中的最大隸屬度的表達式為

則最大隸屬度和其他隸屬度的修正表達式分別為

(6)

Uij=αuij(i≠p)

(7)

式中，0≤α≤1，表示抑制率。對FCM的隸屬度進行抑制的算法稱為S-FCM。當α=0時，S-FCM變為HCM，即K-means算法；當α=1時，S-FCM變為FCM算法。α作為HCM與FCM之間的折中因子，通常α取值為0.5。為了達到更快分類目的，采用不固定抑制率α的機制，第r輪的改進抑制率和改進抑制式模糊C-均值算法目標函數表達式分別為

(8)

(9)

式中：JIS-FCM(r-1)和JIS-FCM(1)分別為改進抑制式模糊C均值算法的第r-1輪與首輪目標函數；α(r)表示第r輪的抑制率。通過式(8)可以看出，抑制率α每輪隨著上輪的目標函數變化而變化。當分類不合理時JIS-FCM值較大，通過式(6)與式(8)可知，每個節點最大隸屬度的獎勵降低，進而減慢了節點向自身所在類的收斂速度，算法性能向FCM靠近；當節點分類趨于合理時，JIS-FCM變小，α變小，此時增加了對每個節點最大隸屬度的獎勵程度，節點向自身所在類的收斂速度加快，算法性能向HCM靠近。通過以上分析，IS-FCM算法根據分類情況動態地調整抑制率，從而使節點根據分類情況對聚類中心的“吸引力”作實時動態變化，在保證合理分類的同時，加快算法收斂速度。

IS-FCM聚類算法步驟如下。

步驟2依據式(3)計算第r輪節點對各聚類的隸屬度ur。

步驟3結合步驟2得到的隸屬度ur，依據式(6)、式(7)和式(8)計算修正后的隸屬度。

具體的IS-FCM聚類算法的流程如圖2所示。

圖2 IS-FCM聚類算法流程

3 CRIS-FCMP算法

為了加快網絡分簇速度和降低簇首傳輸數據能耗，提出了基于改進抑制式模糊C-均值和粒子群算法的WSN分簇路由算法CRIS-FCMP。

3.1 簇的形成

網絡初始化階段，基站首先為監測區域的每一個節點分配唯一的通信ID，然后各個節點將自身的剩余能量、位置坐標發送給基站，基站獲得節點信息后進行分簇，最終將分簇信息廣播至各節點，廣播信息中包含簇ID、節點與基站的距離。

合理的分簇數目能夠進一步均衡無線傳感器網絡節點的負載，因此采用文獻[11]計算最優分簇數目，最優簇首數目表達式為

(10)

式中：M表示監測區域的邊長；dBS表示簇首到基站的平均距離。由式(10)得到最優分簇數后，將監測區域內的節點視為分類對象，采用改進抑制式模糊C-均值算法進行節點的分簇。此外，隨著網絡的運行，存活節點數目不斷下降，網絡特征發生了變化，當初的最優簇首數不再適合網絡狀態。因此，CRIS-FCMP算法在每輪結束時，基站會根據式(3)計算最優簇首數，當最優簇首數改變時，利用IS-FCM算法進行重新分簇，直至分簇數為1。動態分簇避免了因節點死亡造成的分簇不均勻，從而均衡了簇內負載，延長網絡生命周期。

3.2 簇首選舉

簇首擔任簇內節點數據的接收、融合和轉發任務，較簇內節點每輪消耗更多能量。為了均衡簇內節點的負載，選擇一個剩余能量充沛，距離聚類中心較近的節點作為簇首，以均衡簇內節點負載，延長網絡生命周期。

首先，為了保證選舉的簇首能量充沛，設計了節點動態能量閾值，當節點剩余能量大于其動態能量閾值時，該節點當選為簇首。節點動態能量閾值主要由動態權重和簇內平均剩余能量組成，動態能量閾值和動態權重表達式分別為

θ(i)=F(i)Ecluster_avg

(11)

(12)

式中：Ecluster_avg表示簇內節點平均剩余能量；Emax表示節點i所在簇的最大節點剩余能量；Eres(i)表示節點i的剩余能量。Ecluster_avg作為閾值基數可避免選舉簇首的能量太低，此外，為了降低簇首能量與簇內節點能量的差距，利用節點i的剩余能量Eres(i)和Emax構造F(i)作為動態權重。由式(11)與式(12)可以看出，當Eres(i)與Emax的值相差較小時，θ(i)變小，節點i當選為簇首的概率變高。

簇首擁有充沛合理的剩余能量很關鍵，但仍需要考慮簇首與聚類中心的距離以均衡簇內節點負載。因此，根據簇內節點與聚類中心的距離，按從小到大的順序比較節點i的剩余能量Eres(i)與節點動態能量閾值θ(i)的大小，當Eres(i)≥θ(i)時，節點i選為簇首，否則進行下一節點的比較，直至選舉出簇首，若簇內沒有符合條件的節點，選擇簇內擁有最大剩余能量的節點作為簇首。

3.3 數據傳輸

分簇階段完成后，簇內節點采用時分多址(Time Division Multiple Access,TDMA)協議將數據發送至簇首，然后簇首再將接收的簇內數據融合并發送至基站。但是，隨著節點間距離的增大，數據傳輸能耗按指數級增加[16]。為了減輕簇首因長距離傳輸數據消耗的能量，實現網絡能耗均衡，對簇首進行路由規劃。

針對數據傳輸階段均衡簇首負載的問題，已有的算法[17-18]都是通過簇首到簇首的轉發形式均衡簇首負載，雖然能夠減輕遠端簇首的負載，卻加劇了靠近基站的簇首的負載。因此，利用PSO算法為簇首規劃最優路由路徑，以降低簇首被選為中繼節點的概率。

PSO算法[19]是Eberhart和Kennedy于1995年提出的多目標優化算法。考慮其能有效解決大規模的非線性問題，將該算法應用到簇首路由路徑規劃中。算法中每一個粒子可以看作問題的一個可行解，根據適應度函數可以計算出每個粒子的適應度值，從而得到全局最優位置G和局部最優位置P，即規定粒子適應度值越小則對應的解越優。根據全局最優位置和局部最優位置，粒子的速度更新和位置更新的表達式分別為

Vi(t+1)=ωVi(t)+c1rand1[Pi(t)-Xi(t)]+
c2rand2[G(t)-Xi(t)]

(13)

Xi(t+1)=Xi(t)+Vi(t+1)

(14)

式中：c1,c2為學習因子，通常取2；Vi(t)表示第i個粒子第t代的速度，|Vi(t)|∈[vmin,vmax]，ωmax和ωmin分別表示設置的最大、最小權重；Pi(t)表示第i個粒子在第t代自身搜索到的最好位置；G(t)表示第t代時所有粒子搜索到的最優位置；Xi(t)表示第i個粒子第t代的位置；rand1,rand2為0～1之間的隨機數；ω為慣性權重系數。為了提高PSO算法的尋優能力，ω采用文獻[20]的非線性自適應慣性權重系數，表達式為

ω=

(15)

式中：fmin，fmax，favg分別表示本輪粒子群的最小、最大和平均適應度值；f(i)表示第i個粒子的適應度值。

在利用PSO算法進行簇首路由尋優之前，需要確定路由跳數，為了能夠進一步均衡簇首負載，根據最佳傳輸距離[21]dbest、簇首j到基站的距離dj-bs，計算簇首j經幾跳將數據發送至基站，簇首j的路由跳數的表達式為

(16)

式中，round()表示四舍五入操作。

簇首路由跳數確定后，粒子的編碼形式設為X={xCH,x1,x2,…,xh-1,xBS}，其中：xCH,xBS分別表示簇首和基站的位置；x1,x2,…,xh-1表示簇首的隨機初始中繼節點位置。當PSO算法進行更新時，x1,x2,…,xh-1也進行更新，最終的最優粒子解就是簇首的最優路由路徑。其他簇首按相同方法進行粒子編碼。

PSO算法在為簇首規劃路由時，需要一個標準評價路由的優劣，以得到最優簇首路由路徑。因此，需要為PSO算法設計一個簇首路徑選擇適應度函數。由式(16)可知，簇首j需經hj跳將數據發送至基站，即經hj-1個中繼節點。中繼節點應具備以下幾個特點：中繼節點剩余能量應足夠充沛，保證數據傳輸的穩定；中繼節點與簇首和基站的距離要適中，以均衡簇首和中繼節點的負載；簇首前向路由路徑的長度要盡量的小；中繼節點的選取不應局限于簇首之中，以降低簇首負載；中繼節點不宜作為多個簇首的中繼，以均衡中繼節點負載。

根據上述幾個特點，設計了路徑選擇適應度函數，表達式為

(17)

式中：Edelay-avg表示中繼節點的平均剩余能量；Eavg表示所有存活節點平均剩余能量，中繼節點充沛的剩余能量保證了數據傳輸的穩定；dmin和dmax分別表示簇首前向路由路徑中相鄰節點的最小、最大距離，兩者之間差距越小，則中繼節點位置越適中，中繼節點負載越均衡；dCH-BS表示簇首到基站的直線距離；dtotal表示簇首前向路由路徑的距離之和。節點被選為中繼節點的次數定義為負載L，其值越小表示中繼節點的負載越小，有利于均衡中繼節點的負載。由于L的值在非零時通常大于前兩項，且當其值越大時，節點多次作為中繼節點的概率越小。因此，不在L因素前添加權重系數。通過分析，當froute值越小，結合PSO算法得到的簇首路由路徑就越合理。

此外，隨著網絡的運行，中繼節點的能量顯得尤為重要，故定義權重系數a，b分別為

a=1-b

(18)

(19)

式中，Einit表示節點初始能量。網絡初始階段，Eavg較大，故b值也較大，路徑選擇適應度函數以距離因素為主；隨著網絡運行，Eavg變小，a值變大，路徑選擇適應度函數以能量因素為主。依據節點剩余能量設計的動態權重系數均衡了整個網絡運行階段的簇首路由能耗。

基于PSO的簇首路由算法步驟如下。

步驟1初始化粒子群初始位置、速度及其他參數。

步驟2依據式(17)計算粒子適應度值并依據適應度值判斷全局最優解G和局部最優解P。

步驟3根據式(13)和式(14)更新粒子速度與位置。

步驟4重復步驟2和步驟3，直到最優適應度值收斂或達到最大迭代次數。

步驟5輸出最優解。

輸出的最優解即可解碼為簇首最終路由。CRIS-FCMP算法的總體偽代碼可參考附錄A。

3.4 算法復雜度分析

初始化網絡有k個簇首，N個無線傳感器節點，從CRIS-FCMP算法的簇的形成、簇首選舉和數據傳輸等3個階段分析算法的復雜度。

簇的形成階段，IS-FCM算法迭代次數為z，聚類維度為2k，因此，IS-FCM算法的復雜度為O(zk)；簇首選舉時遍歷N個節點，復雜度為O(N)；數據傳輸階段，PSO算法迭代次數為z，種群規模為c，簇首數為k，那么簇首路由路徑規劃過程的復雜度為O(zck)。

因此，CRIS-FCMP算法每輪復雜度為O(zck)，復雜度等同于算法執行所需要的基本運算次數。CRIS-FCMP算法由簇的形成、簇首選舉和數據傳輸等3階段組成。因此CRIS-FCMP算法每輪能在zck運算次數中得到結果，算法可行。

4 分析及其仿真

釆用計算機仿真軟件對所提的CRIS-FCMP算法和LEACH-improve[8]、GAFCMCR[11]、EBRAA[12]進行仿真，并在相同的仿真環境下對算法進行對比分析，仿真參數如表1所示。

表1 仿真參數

4.1 分簇速度對比分析

為了驗證IS-FCM算法的迭代速度較FCM[15]、Iα-SFCM[22]和S-FCM(α=0.5)[14]算法是否提升，在同一仿真環境和相同參數設置下，運用IS-FCM、Iα-SFCM、S-FCM(α=0.5)和FCM算法分別對100～500個節點(間隔為100)進行分簇運算。為了避免偶然性，對每次分簇的迭代次數和迭代時間分別取50次實驗的平均值。IS-FCM、Iα-SFCM、S-FCM(α=0.5)和FCM算法的迭代次數、迭代時間分別如表2和表3所示。

表2 4種算法迭代次數對比

表3 4種算法迭代時間對比

從表2、表3中可以看出，在100～500個節點分簇仿真中，IS-FCM算法的迭代次數較FCM算法、Iα-SFCM和S-FCM(α=0.5)平均減少了83.6%、29.9%和-3.6%，迭代時間平均減少了81.8%、31.4%和9.3%。IS-FCM算法的收斂速度較FCM算法顯著提高，這得益于IS-FCM算法采用了自身的目標函數構造抑制率，通過上輪的分簇效果反饋給抑制率，對最大節點隸屬度進行了獎勵，而抑制了其他隸屬度，加快了節點向自身所在類的收斂速度。IS-FCM迭代次數高于S-FCM(α=0.5)算法，是因為S-FCM(α=0.5)算法一直處于獎勵最大隸屬度的狀態(α=0.5)，即一直處于加快收斂的狀態，而IS-FCM根據分簇效果動態調整抑制系數，收斂速度忽快忽慢，但分簇效果要比S-FCM(α=0.5)的好。由于Iα-SFCM算法未對噪聲及最大隸屬度低于0.5的節點進行隸屬度的修正，收斂速度要低于IS-FCM算法。

4.2 分簇效果對比分析

4.1節已經驗證了IS-FCM較FCM、Iα-SFCM和S-FCM(α=0.5)算法收斂速度顯著提高，但分簇的合理性同樣重要，那么在同一條件下，對FCM算法、S-FCM(α=0.5)、Iα-SFCM和IS-FCM算法的分簇進行了仿真，分簇結果分別如圖3(a)至圖3(d)所示，圖中實心點表示分簇中心，空心點表示分簇成員。

圖3 4種算法分簇效果

比較圖3(a)、圖3(c)和圖3(d)，可以發現IS-FCM與FCM算法和Iα-SFCM算法的分簇效果幾乎相同，從表4中可以看出其簇成員方差數區別不大，也未出現極小極大簇。雖然圖3(a)、圖3(c)的分簇效果相似，從以上分析中可以發現Iα-SFCM算法的收斂速度要比FCM算法快。因此，Iα-SFCM算法要優于FCM算法，然而IS-FCM算法收斂要快于Iα-SFCM算法，這說明IS-FCM算法比FCM與Iα-SFCM算法收斂速度快的同時保持了均勻分簇的良好特性。

表4 簇成員數對比

對比圖3(b)和圖3(d)，可以明顯看出圖3(b)中的左右兩側出現了極小、極大簇，說明S-FCM(α=0.5)算法的分簇沒有IS-FCM算法的合理。這主要由于S-FCM(α=0.5)采用了固定的抑制率，不能根據分簇情況對抑制率做出實時調整，導致了S-FCM(α=0.5)算法盲目的獎勵節點最大隸屬度，雖然加快了算法收斂速度，但容易使算法陷入局部最優，而IS-FCM算法則利用分簇效果動態調整抑制系數，加速收斂的同時避免算法陷入局部最優。

綜合仿真分析，IS-FCM相較于FCM、Iα-SFCM和S-FCM(α=0.5)算法收斂速度得到提升的同時，仍然保持了良好的分簇特性。IS-FCM的快速良好分簇特性使其可以應用于對實時性要求高的網絡中，特別是大規模網絡環境中。

4.3 網絡生命周期

將CRIS-FCMP算法分別與LEACH-improve、GAFCMCR和EBRAA算法進行節點存活數量變化的仿真比較，相關參數如表1定義，網絡生命周期對比結果如圖4所示。經仿真得出，CRIS-FCMP算法首節點死亡時間出現在第1 025輪，而LEACH-improve、GAFCMCR和EBRAA算法首節點死亡時間分別出現在第472、第700和第715輪。因此，CRIS-FCMP算法較LEACH-improve、GAFCMCR和EBRAA算法分別提高117.2%、46.4%和43.3%。

圖4給出了CRIS-FCMP算法與其他3個算法的網絡生命周期的具體情況，從圖4中可以看出，CRIS-FCMP算法的生命周期明顯大于LEACH-improve、GAFCMCR和EBRAA。LEACH-improve、GAFCMCR和EBRAA算法分別大約在900輪、900輪和1 000輪，僅剩1/5存活節點，而CRIS-FCMP算法此時仍未出現節點死亡的情況，說明了CRIS-FCMP算法有效地延長了網絡生命周期。此外，CRIS-FCMP算法第一個節點死亡后，節點死亡趨勢陡直，說明了該算法有效地均衡了節點的能耗。

圖4 網絡生命周期對比

4.4 網絡能耗

無線傳感器網絡生命周期的延長主要由節點能量消耗的快慢決定。圖5為LEACH-improve、GAFCMCR、EBRAA和CRIS-FCMP算法的節點能量剩余對比結果。

圖5 節點剩余能量對比

從圖5中可以看出，在整個網絡生命周期中，CRIS-FCMP算法的節點剩余能量始終高于LEACH-improve、GAFCMCR和BERAA算法，說明CRIS-FCMP算法降低了每輪節點的能量消耗，從而能夠延長CRIS-FCMP算法的網絡生命周期。這主要得益于均勻的網絡分簇均衡了簇首的負載；其次簇首的選舉考慮了與簇內其他成員的距離的均衡性，降低了簇內其他節點的能耗，簇首的選舉還考慮了與平均剩余能量和最大剩余能量的關系，降低了低能量節點選為簇首的概率。最重要的是CRIS-FCMP算法為簇首規劃了路由，且考慮了中繼節點的合理性，進一步均衡了簇首的負載，而EBRAA算法雖然為簇首規劃了路由，但中繼節點僅在簇首中選取，且未考慮中繼節點的負載因素，加劇了簇首能耗。

5 結語

為了提升FCM算法的收斂速度使其可應用于大規模且對實時性要求高的網絡環境，并延長無線傳感器網絡生命周期，提出了CRIS-FCMP算法。簇的形成階段，采用改進SFCM算法進行網絡分簇，以進一步提升網絡分簇時的收斂速度。簇首選舉階段結合簇內節點的剩余能量關系設計節點動態能量閾值，并參照距離順序選舉簇首。數據傳輸階段，依據中繼節點能量、距離及負載因素結合PSO算法搜尋簇首路由。仿真分析表明，網絡分簇階段所用的IS-FCM算法相對FCM、S-FCM-(α=0.5)算法能夠有效提升合理分類的收斂速度。此外，CRIS-FCMP算法相對已有算法能夠有效均衡節點負載，延長網絡生命周期。

無線傳感器網絡生命周期還受到其他因素的影響，比如移動基站環境下的網絡路由規劃、三維網絡的拓撲變化等，此類影響因素的問題有待進一步研究。