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

董發(fā)志 丁洪偉 楊志軍 熊成彪 張穎婕

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

關(guān)鍵詞：無線傳感器網(wǎng)絡(luò);模糊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 引言

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

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

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

1 系統(tǒng)模型

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

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

1.2 能耗模型

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

ETX（l，d）=

lEelec+lεfsd2，?? d

lEelec+lεmpd4， d≥d0

（1）

接收消耗的能量和距離無關(guān)，接收lbit數(shù)據(jù)消耗的能量如下：

ERX=lEelec

（2）

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

2 GAFCMCR

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

2.1 簇的形成

網(wǎng)絡(luò)初始化時，基站首先為每個節(jié)點分配唯一的通信ID，各節(jié)點將自身的位置坐標發(fā)送給基站，基站經(jīng)過計算，將分簇信息廣播給節(jié)點。廣播信息包括簇ID、節(jié)點與基站的距離。

2.1.1 最優(yōu)簇頭數(shù)

FCM算法需指定聚類數(shù)目，在無線傳感器網(wǎng)絡(luò)中，為了得到合理的分簇，根據(jù)網(wǎng)絡(luò)特征確定最優(yōu)簇頭數(shù)。對于本文的網(wǎng)絡(luò)模型和能耗模型，基站位于監(jiān)測區(qū)域中心，所以每個節(jié)點到基站的距離都小于等于d0，故簇頭和簇內(nèi)節(jié)點運行一輪消耗的能量[15]為：

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

（3）

EnoCH=l（Eelec+εfsd2toCH）

（4）

式中：c為簇頭數(shù)，Eda為融合1bit數(shù)據(jù)消耗的能量。則網(wǎng)絡(luò)的總能耗為：

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

（5）

要使得總能耗最小，則

Etotal c =0

（6）

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

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

（7）

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

E[d2toCH]=

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

（8）

綜上可得最優(yōu)簇頭數(shù)：

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

（9）

2.1.2 模糊C均值聚類

FCM算法首先是由Ruspini[16]提出來的，目前在機器學習中應(yīng)用廣泛，將FCM應(yīng)用到無線器網(wǎng)絡(luò)的分簇中，能夠?qū)⒕W(wǎng)絡(luò)中的節(jié)點按照緊密程度分為固定的幾個簇，有效減少了由于簇結(jié)構(gòu)不均勻帶來的能量損耗。FCM算法的目標函數(shù)為：

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 遺傳算法優(yōu)化初始聚類中心

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

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

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

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

步驟3? 計算個體適應(yīng)值，其適應(yīng)函數(shù)f=1/Jm。

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

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

GA優(yōu)化FCM算法的流程如圖3所示。

GA優(yōu)化的FCM算法的偽代碼如下：

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

輸出? 聚類結(jié)果，聚類中心。

程序前

be gin

t←0;

Initialize Pop（t）;

//初始化種群

計算初始化種群個體適應(yīng)值f=1/Jm;

wh ile t

GA-Operation Pop （t）;

//遺傳算法運算

計算個體適應(yīng)值f=1/Jm;

t+ +;

end while

bestcenter;

//最優(yōu)初始聚類中心

repeat

fo r i=1 to n do

fo r j=1 to c do

根據(jù)式（11）計算價值函數(shù)

根據(jù)式（12）計算隸屬度矩陣 U

根據(jù)式（13）更新聚類中心

end for

end for

until

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

return 聚類結(jié)果和聚類中心

end

程序后

2.1.4 動態(tài)分簇

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

2.2 簇頭的選舉

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

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

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

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

（13）

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

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

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

（14）

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

式（15）表示候選節(jié)點與簇內(nèi)其他節(jié)點的距離關(guān)系：

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

（15）

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

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

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

（16）

其中， α、β、γ為權(quán)重參數(shù)，用來調(diào)整三個因子的重要程度。初始化階段， α=β=γ=1/3;隨著網(wǎng)絡(luò)的運行，節(jié)點能量不斷下降，成為影響網(wǎng)絡(luò)生命周期的重要因子，所以權(quán)重應(yīng)該隨著網(wǎng)絡(luò)的運行而變化。將α、β、γ按照下式進行更新：

α=Einit/Eres（i）

（17）

β=γ=（1-α）/2

（18）

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

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

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

（19）

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

2.3 數(shù)據(jù)傳輸

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

簇頭節(jié)點完成一個輪詢周期后進行數(shù)據(jù)的融合，采用CSMA機制單跳將數(shù)據(jù)發(fā)送至基站。

GAFCMCR的偽代碼如下：

程序前

初始化網(wǎng)絡(luò)，設(shè)定相關(guān)參數(shù);

fo r round=1 to maxround do

if? round= =0 then

執(zhí)行GA優(yōu)化的FCM算法，得到結(jié)果和聚類中心;

CH←離聚類中心最近的節(jié)點

el se

fo r i=1 to n do

根據(jù)式（17）計算每個節(jié)點的參量p（i）

end for

if? pCH≤λpmax（i） then

CH←pmax（i）對應(yīng)節(jié)點

end if

if? 最優(yōu)簇數(shù)發(fā)生改變&&最優(yōu)簇數(shù)大于1 then

執(zhí)行GA優(yōu)化的FCM算法，更新各參數(shù)

end if

end if

end for

程序后

2.4 算法復雜度分析

假設(shè)網(wǎng)絡(luò)中有N個節(jié)點，每輪選取K個簇頭，下面對算法的復雜度進行分析：

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

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

3 仿真與分析

3.1 仿真環(huán)境

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

3.2 GA改進FCM的必要性分析

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

3.3 成簇結(jié)果

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

3.4? 網(wǎng)絡(luò)生命周期

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

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

3.5 網(wǎng)絡(luò)能耗

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

3.6 網(wǎng)絡(luò)吞吐量

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

4 結(jié)語

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

參考文獻

[1]?徐晶晶，張欣慧，許必宵，等.無線傳感器網(wǎng)絡(luò)分簇算法綜述[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.