基于遺傳算法和模糊C均值聚類的WSN分簇路由算法

董發志 丁洪偉 楊志軍 熊成彪 張穎婕

摘 要：針對無線傳感器網絡（WSN）的節點能量有限、生命周期短、吞吐量低等問題，提出一種基于遺傳算法（GA）和模糊C均值（FCM）聚類的WSN分簇路由算法GAFCMCR，采取“集中分簇，分布簇頭選舉”的方式。網絡初始化時基站采用由GA優化的FCM聚類算法形成網絡分簇。第一輪簇頭由距簇中心最近的節點擔任;從第二輪開始，簇頭的選舉由上一輪的簇頭負責，選舉過程綜合考慮候選節點的剩余能量、與基站的距離、與簇內其他節點的平均距離三個因子，并根據網絡狀態實時調整三個因子的權重。在數據傳輸階段，將輪詢機制引入簇內通信。仿真結果表明，相同網絡環境下，與LEACH算法和基于K-Means的均勻分簇路由（KUCR）算法相比，GAFCMCR將網絡生命周期延長了105%和20%。GAFCMCR成簇效果良好，具有良好的能量均衡性和更高的吞吐量。

關鍵詞：無線傳感器網絡;模糊C均值聚類;遺傳算法;均勻分簇;輪詢機制

中圖分類號：?TP393.04

文獻標志碼：A

WSN clustering routing algorithm based on genetic algorithm and fuzzy C-means clustering

DONG Fazhi1， DING Hongwei1*， YANG Zhijun1，2， XIONG Chengbiao1， ZHANG Yingjie1

1.School of Information Science and Engineering， Yunnan University， Kunming Yunnan 650500， China?;

2.Yunnan Academy of Educational Sciences， Kunming Yunnan 650223， China

Abstract：?Aiming at the problems of limited energy of nodes， short life cycle and low throughput of Wireless Sensor Network （WSN）， a WSN Clustering Routing algorithm based on Genetic Algorithm （GA） and Fuzzy C-Means （FCM） clustering （GAFCMCR） was proposed， which adopted the method of centralized clustering and distributed cluster head election. Network clustering was performed by the base station using a FCM clustering algorithm optimized by GA during network initialization. The cluster head of the first round was the node closest to the center of the cluster. From the second round， the election of the cluster head was carried out by the cluster head of the previous round. The residual energy of candidate node， the distance from the node to the base station， and the mean distance from the node to other nodes in the cluster were considered in the election process， and the weights of these three factors were real-time adjusted according to network status. In the data transfer phase， the polling mechanism was introduced into intra-cluster communication. The simulation results show that， compared with the LEACH （Low Energy Adaptive Clustering Hierarchy） algorithm and the K-means-based Uniform Clustering Routing （KUCR） algorithm， the life cycle of the network in GAFCMCR is prolonged by 105% and 20% respectively. GAFCMCR has good clustering effect， good energy balance and higher throughput.

Key words：?Wireless Sensor Network （WSN）; Fuzzy C-Means （FCM） clustering; Genetic Algorithm （GA）; uniform clustering; polling mechanism

0 引言

無線傳感器網絡（Wireless Sensor Network，WSN）由大量廉價的微傳感器節點組成，可以部署在監控區域，并可以通過無線通信方式形成自組織網絡。傳感器節點可以感知網絡，收集和處理數據并將信息傳輸給監測中心[1]。近年來WSN廣泛應用于監測、跟蹤、事件檢測、監視和災害管理等各方面[2]。WSN的長期有用性主要依賴于節點的生命周期。節點的壽命完全取決于其電池電量，由于這些電池幾乎不可更換，所以通過節約電池能量可以實現無線傳感器網絡生命周期的延長[3]。針對這個問題，許多層次型路由協議被提出，通過控制成簇、優化網絡的拓撲結構達到降低網絡能耗、延長網絡生命周期的目的[4]。

最經典的分簇路由協議是由Heinzelman等[5]提出的LEACH（Low Energy Adaptive Clustering Hierarchy）算法，它將無線傳感器網絡劃分為若干簇，每個簇中隨機選取至少一個簇頭，簇內節點將自己收集的數據發送給簇頭，簇頭進行數據融合之后通過單跳或者多跳將數據發送給基站。采用“輪”的方式將能量損耗均勻分布到各個節點，從而延長了生命周期;但是簇頭的選取沒有考慮節點的剩余能量，若能量低的節點被選為簇頭，則會加快節點的死亡。Heinzelman等[6]在LEACH的基礎上又提出了LEACH-C（LEACH-centralized）算法，由基站集中計算分簇，減少了簇頭的計算能耗，但是沒有考慮簇頭節點的位置。Kumar等[7]提出了U-LEACH（Universal-Low Energy Adaptive Cluster Hierarchy）算法，利用不均勻成簇解決了LEACH協議中的熱點區域問題。Bakaraniya等[8]提出了基于K-means分簇的K-LEACH（Kmedoids-LEACH protocol）算法，初始階段利用K-means進行分簇，提升了網絡性能，但簇頭的選舉未考慮節點能量。張雅瓊[9]提出的基于K-Means 的均勻分簇路由（Uniform Clustering Routing based on K-Means，KUCR）算法利用K-Means進行分簇，采取一次成簇、多次簇頭更新的機制，提升了性能，但簇頭選舉時并未考慮節點與其他節點的距離關系。嚴靜靜等[10]利用粗糙C-均值聚類改進了LEACH算法，利用粗糙C-均值聚類進行分簇，保證了簇頭節點分布均勻，延長了生命周期，但在簇頭選舉時未考慮節點與基站的距離。

本文在研究LEACH、KUCR算法的基礎上，提出了一種基于遺傳算法（Genetic Algorithm，GA）和模糊C均值（Fuzzy C-Means，FCM）的WSN分簇算法（Clustering Routing algorithm based on Genetic Algorithm and fuzzy C-means clustering， GAFCMCR）。該算法的主要特點是：在網絡初始化階段，由基站采用GA改進的FCM算法進行集中式分簇;然后，每個簇內節點根據自身的剩余能量、到基站的距離以及與簇內其他節點的距離三個因子進行簇頭的競選;最后，在數據的傳輸階段，簇內通信引入輪詢控制，簇間采用載波偵聽多路訪問（Carrier Sense Multiple Access，CSMA）機制。仿真結果表明，相比LEACH和KUCR，GAFCMCR能夠有效延長網絡生命周期，降低能耗，提高網絡的吞吐量。

1 系統模型

1.1 網絡模型

本文對無線傳感器網絡作出如下假設：網絡中有N個節點隨機分布在面積為M×M的監測區域中，節點部署之后不隨時間移動;節點的初始能量相同，可以獲取自身的位置和剩余能量，且都可以擔任簇頭，能夠進行計算處理和數據融合，具有唯一地址;基站位于監測區域中心，能量和計算能力無限;所有節點都可以和基站直接通信。

1.2 能耗模型

本文采用與文獻[11]相同的一階無線電能耗模型，節點發送lbit的數據消耗的能量包括發射損耗和功率放大損耗兩部分，一個節點經過距離d發送lbit數據的能耗如下：

ETX（l，d）=

lEelec+lεfsd2，?? d

lEelec+lεmpd4， d≥d0

（1）

接收消耗的能量和距離無關，接收lbit數據消耗的能量如下：

ERX=lEelec

（2）

式中：Eelec為節點每發送或接收1bit數據消耗的能量;d0為節點之間傳輸數據的模型選擇的一個閾值，取值為d0= εfs/εmp 。當傳輸距離小于d0時，采用自由空間信道模型;當傳輸距離大于d0時，采用多路徑衰減模型[12-14]。其中相應的參數εfs和εmp表示的是上述兩種情況下單位功率放大時需要的能量。

2 GAFCMCR

GAFCMCR采用與LEACH相同的按“輪”運行方式，如圖1所示，分為簇的形成、簇頭選舉和穩定傳輸三個過程。在初始化階段各節點將位置信息發送給基站，由基站采用優化的FCM算法進行迭代計算，形成C個簇。不同于LEACH算法每輪都需要重新分簇，GAFCMCR的第一輪分簇完成后，以后的輪次只在簇內進行簇頭的更新，只在最優簇數發生改變時才重新分簇。這樣有的輪次簇結構和簇頭都是不變的，減少了頻繁分簇和簇頭選舉帶來的能量損耗，能延長生命周期。

2.1 簇的形成

網絡初始化時，基站首先為每個節點分配唯一的通信ID，各節點將自身的位置坐標發送給基站，基站經過計算，將分簇信息廣播給節點。廣播信息包括簇ID、節點與基站的距離。

2.1.1 最優簇頭數

FCM算法需指定聚類數目，在無線傳感器網絡中，為了得到合理的分簇，根據網絡特征確定最優簇頭數。對于本文的網絡模型和能耗模型，基站位于監測區域中心，所以每個節點到基站的距離都小于等于d0，故簇頭和簇內節點運行一輪消耗的能量[15]為：

ECH=l Eelec ?N c -1 +Eda? N c +Eelec+εfsd2toBS

（3）

EnoCH=l（Eelec+εfsd2toCH）

（4）

式中：c為簇頭數，Eda為融合1bit數據消耗的能量。則網絡的總能耗為：

Etotal=l[2NEelec+NEda+cεfsd4toBS+Nεfsd2toCH]

（5）

要使得總能耗最小，則

Etotal c =0

（6）

dtoBS為節點到基站的距離，計算如下：

E[dtoBS]=∫A x2+y2? 1 A dA=0.765 m 2

（7）

dtoCH為節點到簇頭的距離，計算如下：

E[d2toCH]=

（x2+y2）ρ（x，y）dxdy=ρ∫2π0∫ m? πc? 0 r3drdθ= m2 2πc

（8）

綜上可得最優簇頭數：

c=? N 2π ??m dtoBS =? N 2π ???2 0.765

（9）

2.1.2 模糊C均值聚類

FCM算法首先是由Ruspini[16]提出來的，目前在機器學習中應用廣泛，將FCM應用到無線器網絡的分簇中，能夠將網絡中的節點按照緊密程度分為固定的幾個簇，有效減少了由于簇結構不均勻帶來的能量損耗。FCM算法的目標函數為：

Jm=∑ N i=1 ∑ C j=1 （μij）m（dij）2; m∈[1，∞）

（10）

式中：dij=‖xi-cj‖，xi為第i個樣本，cj為第j個聚類中心;μij是樣本xi對第j個聚類中心的隸屬度;m是模糊因子。

μij的更新公式為：

μij= 1 ∑ C k=1?? dij dik ??2 m-1

（11）

聚類中心更新的公式為：

Cj= ∑ N i=1 （μij）mxi ∑ N i=1 （μij）m

（12）

算法終止條件為：‖ U （k+1）- U （k）‖≤ε。

FCM算法流程如圖2所示。

2.1.3 遺傳算法優化初始聚類中心

FCM算法對初始聚類中心敏感，容易收斂于局部最優解，為了克服該缺點，將GA應用于FCM算法的優化計算中，由GA得到初始聚類中心，再使用標準的FCM算法得到最終的分類結果。

遺傳算法源于生物進化論和遺傳學，是一種模仿自然界適者生存機制的自適應搜索算法[17-18]。GA優化FCM算法的步驟[19-20]為：

步驟1? 參數初始化， 設置種群規模N，交叉概率pc，變異概率pm，終止進化的迭代次數T以及初始聚類數目c。采用二進制編碼，根據聚類中心坐標（xi，yi），將其編碼為基因串α={α1α2…αi…αq}，其中，q=c×2，在α中每兩個值代表一個聚類中心的坐標。

步驟2? 設置迭代次數t=0，并隨機選取初始種群。

步驟3? 計算個體適應值，其適應函數f=1/Jm。

步驟4? 進行選擇、交叉、變異，獲得新一代的種群，判斷新種群是否滿足停止迭代準則，t=t+1。

步驟5? 如果t大于最大迭代次數，則停止迭代，輸出聚類個數和聚類中心，否則返回步驟2繼續迭代。

GA優化FCM算法的流程如圖3所示。

GA優化的FCM算法的偽代碼如下：

輸入? ?X ={x1，x2，…，xN}T（樣本集合），c（聚類數目），m（模糊因子），N（種群規模）， pc（交叉概率），變異概率pm（交叉概率）， T（迭代次數）;

輸出? 聚類結果，聚類中心。

程序前

be gin

t←0;

Initialize Pop（t）;

//初始化種群

計算初始化種群個體適應值f=1/Jm;

wh ile t

GA-Operation Pop （t）;

//遺傳算法運算

計算個體適應值f=1/Jm;

t+ +;

end while

bestcenter;

//最優初始聚類中心

repeat

fo r i=1 to n do

fo r j=1 to c do

根據式（11）計算價值函數

根據式（12）計算隸屬度矩陣 U

根據式（13）更新聚類中心

end for

end for

until

‖ U （k+1）- U （k）‖≤ε

return 聚類結果和聚類中心

end

程序后

2.1.4 動態分簇

隨著網絡的運行，存活節點數不斷減少，網絡特征發生了變化，初始化階段確定的最優簇數不再適合當前網絡狀態。所以GAFCMCR在每一輪運行結束時，基站會根據式（9）計算最優簇數，當最優簇數改變時，就重新分簇，直到簇數為1。動態的分簇過程優化了性能，延長了網絡的生命周期。

2.2 簇頭的選舉

為了減少簇頭的能耗，避免節點過早死亡從而導致網絡失效，本文算法的簇頭選舉綜合考慮節點的剩余能量、到基站的距離以及與簇內其他節點的距離關系等三個因素。第一輪分簇完成后，基站廣播分簇結果時將每一簇離簇中心最近的節點指定為簇頭。

第二輪開始，簇頭的選舉綜合考慮剩余能量、與基站的距離及它與簇內其他節點的距離等三個因素。

剩余能量是簇頭選舉的重要參考，GAFCMCR采用節點的剩余能量與所屬簇內所有節點平均剩余能量的比值作為參考標準，如式（13）：

f1（i）= Eres（i）? 1 n ∑ n j=1 Eres（i）

（13）

式中：n為節點i所屬簇的節點總數。f1越大說明節點i的剩余能量越高。

式（14）表示候選節點到基站的距離因素：

f2（i）=? 1 n ∑ n j=1 dtoBS（i） dtoBS（i）

（14）

式中，dtoBS（i）為節點i到基站的距離。f2越大，說明節點距離基站越近，簇頭到基站傳輸數據的距離越短，能耗越低。

式（15）表示候選節點與簇內其他節點的距離關系：

f3（i）= n ∑ n j=1 d（i， j）

（15）

式中，d（i， j）為節點i到節點j的距離。 f3越大，說明相對于其他節點，候選節點能夠使簇內通信的距離更小。

每一輪的最后一幀，節點將自身位置和剩余能量發送給簇頭，簇頭根據式（16）重新計算每個節點的參量p。節點剩余能量多、距離基站近且與其他節點緊密程度較好的節點能夠成為候選簇頭。

p（i）=αf1（i）+βf2（i）+γf3（i）

（16）

其中， α、β、γ為權重參數，用來調整三個因子的重要程度。初始化階段， α=β=γ=1/3;隨著網絡的運行，節點能量不斷下降，成為影響網絡生命周期的重要因子，所以權重應該隨著網絡的運行而變化。將α、β、γ按照下式進行更新：

α=Einit/Eres（i）

（17）

β=γ=（1-α）/2

（18）

運行過程中，α動態增大，剩余能量大的節點當選簇頭的概率更高，使得能量更加均衡。

簇頭節點選取參量最大的節點i與自身參量進行比較：

pCH≤λpmax（i），λ∈（0，1）

（19）

如果式（19）成立，則簇頭通知節點i當選為新簇頭，并交換成員信息，節點i廣播成為簇頭信息;若不成立，則本輪次不進行簇頭的更新。由于不是每輪都需要更新簇頭，從而節省了能耗，降低了時延。式（19）中，λ為網絡系數，影響網絡的更新速度：取值太小，則個別節點會長時間擔任簇頭而導致能量消耗大，縮短了節點生命周期;取值太大，則需要頻繁更新簇頭，也導致能耗增加。

2.3 數據傳輸

LEACH及其大多數改進算法的簇內通信機制均采用時分多址（Time Division Multiple Access，TDMA）機制[21-22]，簇頭為每個成員節點劃分一個時隙，節點在固定的時隙內傳輸數據。但在無線傳感器網絡中，并不是所有節點都一直處于活躍狀態，有些節點在一定時期處于休眠狀態，當需要采集數據時再喚醒。這就會出現空閑的時隙，增加了能量的浪費。因此根據文獻[23]，將輪詢控制引入無線傳感器網絡，作為GAFCMCR的簇內通信介質訪問控制（Medium Access Control， MAC）機制，采用由簇頭節點依次輪詢成員節點的方式來傳輸信息，簇頭節點建立輪詢表來記錄所需要輪詢的節點。輪詢表記錄的是輪詢順序和節點ID的對應關系，而且輪詢表并不是一一對應，一個節點ID可以對應多個序號，反映了該節點具有較高優先級，在一個輪詢周期內被多次訪問。當節點能量耗盡或者處于休眠狀態時，將此節點從輪詢列表中移除，充分利用了時隙，又可以有效避免常見協議因碰撞帶來的能量損耗。

簇頭節點完成一個輪詢周期后進行數據的融合，采用CSMA機制單跳將數據發送至基站。

GAFCMCR的偽代碼如下：

程序前

初始化網絡，設定相關參數;

fo r round=1 to maxround do

if? round= =0 then

執行GA優化的FCM算法，得到結果和聚類中心;

CH←離聚類中心最近的節點

el se

fo r i=1 to n do

根據式（17）計算每個節點的參量p（i）

end for

if? pCH≤λpmax（i） then

CH←pmax（i）對應節點

end if

if? 最優簇數發生改變&&最優簇數大于1 then

執行GA優化的FCM算法，更新各參數

end if

end if

end for

程序后

2.4 算法復雜度分析

假設網絡中有N個節點，每輪選取K個簇頭，下面對算法的復雜度進行分析：

不同于其他輪，第一輪的簇頭選舉直接由基站指定，當分簇完成后，基站廣播N條消息，消息中包含了哪些節點是簇頭和各節點所屬簇，各節點不用發送請求直接入簇。所以算法第一輪的復雜度為：O（N）。

從第二輪開始，每輪選舉K個簇頭，當前簇頭發送一條消息與新簇頭進行成員信息的交換，共發送K條消息;新的簇頭向成員發送消息，告知其他節點自己成為簇頭，此過程共產生N-K條消息。因此每輪的總消息數為：K+N-K=N。所以算法每輪的復雜度為：O（N）。

3 仿真與分析

3.1 仿真環境

本文使用Matlab 2014Rb軟件進行無線傳感器網絡的仿真。 在理想的信道條件下，忽略隨機因素的干擾和信號沖突等影響，監測在100m×100m傳感器網絡區域內隨機分布的100個節點。節點的能量損耗主要考慮數據包和控制包的發送和接收能量損失，以及數據融合能量。仿真所用到的具體參數見表1。遺傳算法的參數設置為：種群規模N=N×10×2，交叉概率pc=0.7，變異概率pm=0.01，終止進化的迭代次數T=100;FCM算法終止條件閾值ε=10-6。

3.2 GA改進FCM的必要性分析

FCM算法和GA改進的FCM算法應用于無線傳感器網絡同一環境的成簇結果如圖4所示。從圖中能夠直觀地看出，GA改進后的FCM算法成簇結果更加均勻。FCM算法成簇后有幾個簇的成員到簇頭的距離過遠，這勢必會增加簇內通信的能耗，而改進的FCM則使得簇間的通信距離比較均勻，能夠減少能耗。說明用GA改進FCM算法形成網絡分簇能夠改善成簇效果。

3.3 成簇結果

GAFCMCR與KUCR、LEACH算法的成簇對比如圖5所示，可以看出，LEACH算法由于簇頭選舉的隨機性，成簇不理想，簇頭分布不合理，簇的數量和大小不均勻，導致了能耗的增加;KUCR算法采用K-means聚類算法，根據節點位置和節點ID計算形成分簇結果，分簇比較均勻，但是由于K-means算法對于初始聚類中心敏感，容易陷入局部最優，成簇存在“極大簇”“極小簇”，造成了能耗失衡。GAFCMCR使用GA優化的FCM聚類算法進行分簇，使得成簇相比其他兩種算法更加均勻，簇頭分布位置更加合理。

3.4? 網絡生命周期

將網絡生命周期定義為網絡開始運行到出現第一個死亡節點期間的運行輪數，此定義下GAFCMCR算法的生命周期為2238輪，比LEACH和KUCR分別延長了105%和20%。也有研究將生命周期定義為網絡運行開始到網絡中全部節點都死亡所運行的輪數或者網絡運行截止到一半節點死亡的運行輪數。表2統計了不同比例節點死亡運行到的輪數，從表中可以看出，網絡運行的整個階段GAFCMCR算法的生命周期都有優勢。

圖6是各算法生命周期對比，從圖中可以看出，相比LEACH和KUCR，GAFCMCR有效提升了生命周期，而且GAFCMCR的曲線的斜率較大，說明能量均衡性好。GAFCMCR具有優勢的原因是改進了聚類算法、成簇方式以及簇頭的選舉方式。

3.5 網絡能耗

三種算法的網絡剩余能量對比如圖7所示，在相同初始能量下，GAFCMCR的網絡剩余能量始終高于另外兩種算法。這表明GAFCMCR能夠有效降低能耗，主要原因是：GAFCMCR使用GA改進的FCM算法進行分簇，不存在極大、極小簇，簇頭的選舉過程綜合考慮了剩余能量、節點與基站的距離以及與其他節點的緊密程度，距離基站近、與簇內其他節點近的節點大概率當選簇頭，降低了簇頭傳輸數據和簇間通信的能耗。

3.6 網絡吞吐量

傳感網絡節點部署的主要目的就是收集監測區域的各種數據，因此網絡的吞吐量是一個重要的性能指標。本文用基站接收到總的數據量來衡量網絡的吞吐量。GAFCMCR和其他兩種算法的吞吐量對比如圖8所示，從圖中可以看出：相比LEACH和KUCR，由于GAFCMCR的生命周期較長，所以基站接收了更多的數據;而且GAFCMCR的吞吐量從網絡運行開始就高于其他算法，這得益于數據傳輸階段引入了輪詢機制，充分了利用了時隙。

4 結語

為了延長無線傳感器網絡的生命周期、降低能耗和提高吞吐量，本文提出了基于GA和FCM的WSN分簇算法GAFCMCR。在成簇階段，利用FCM算法實現分簇，并針對FCM算法對初始值敏感的問題，使用GA優化初始聚類中心后再進行聚類;在簇頭選舉階段，綜合考慮節點的狀態，使得選出的簇頭更合理;在數據傳輸階段，將輪詢引入簇內通信，提高了網絡的吞吐量。實驗結果表明，GAFCMCR能夠有效降低能耗，提高能量的均衡性，明顯延長網絡生命期。

參考文獻

[1]?徐晶晶，張欣慧，許必宵，等.無線傳感器網絡分簇算法綜述[J].計算機科學，2017，44（2）：31-37. （XU J J， ZHANG X H， XU B X， et al. Overview of clustering algorithms for wireless sensor networks [J]. Computer Science， 2017， 44 （2）： 31-37.）

[2]?SINGH S P， SHARMA S C. Cluster based routing algorithms for wireless sensor networks [J]. IJETI International Journal of Engineering & Technology Innovations， 2014， 1（4）： 1-8.

https：//pdfs.semanticscholar.org/32cf/4e781fa41fd314f567960cf1cb666fee9715.pdf

https：//zz.glgoo.top/scholar？hl=zh-CN&as_sdt=0%2C5&q=Cluster+based+routing+algorithms+for+wireless+sensor+networks&btnG=

[3]?LIU F， WANG Y， LIN M， et al. A distributed routing algorithm for data collection in low-duty-cycle wireless sensor networks [J]. IEEE Internet of Things Journal， 2017， 4（5）： 1420-1433.

[4]?GULERIA K， VERMA A K. Comprehensive review for energy efficient hierarchical routing protocols on wireless sensor networks [J]. Wireless Networks， 2019， 25（3）： 1159-1183.