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

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

關(guān)鍵詞：無(wú)線(xiàn)傳感器網(wǎng)絡(luò);模糊C均值聚類(lèi);遺傳算法;均勻分簇;輪詢(xún)機(jī)制

中圖分類(lèi)號(hào)：?TP393.04

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

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

本文在研究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）。該算法的主要特點(diǎn)是：在網(wǎng)絡(luò)初始化階段，由基站采用GA改進(jìn)的FCM算法進(jìn)行集中式分簇;然后，每個(gè)簇內(nèi)節(jié)點(diǎn)根據(jù)自身的剩余能量、到基站的距離以及與簇內(nèi)其他節(jié)點(diǎn)的距離三個(gè)因子進(jìn)行簇頭的競(jìng)選;最后，在數(shù)據(jù)的傳輸階段，簇內(nèi)通信引入輪詢(xún)控制，簇間采用載波偵聽(tīng)多路訪(fǎng)問(wèn)（Carrier Sense Multiple Access，CSMA）機(jī)制。仿真結(jié)果表明，相比LEACH和KUCR，GAFCMCR能夠有效延長(zhǎng)網(wǎng)絡(luò)生命周期，降低能耗，提高網(wǎng)絡(luò)的吞吐量。

1 系統(tǒng)模型

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

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

1.2 能耗模型

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

ETX（l，d）=

lEelec+lεfsd2，?? d

lEelec+lεmpd4， d≥d0

（1）

接收消耗的能量和距離無(wú)關(guān)，接收l(shuí)bit數(shù)據(jù)消耗的能量如下：

ERX=lEelec

（2）

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

2 GAFCMCR

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

2.1 簇的形成

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

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

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

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

（7）

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

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均值聚類(lèi)

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

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

（10）

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

μij的更新公式為：

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

（11）

聚類(lèi)中心更新的公式為：

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

（12）

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

FCM算法流程如圖2所示。

2.1.3 遺傳算法優(yōu)化初始聚類(lèi)中心

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

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

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

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

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

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

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

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

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

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

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

程序前

be gin

t←0;

Initialize Pop（t）;

//初始化種群

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

wh ile t

GA-Operation Pop （t）;

//遺傳算法運(yùn)算

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

t+ +;

end while

bestcenter;

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

repeat

fo r i=1 to n do

fo r j=1 to c do

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

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

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

end for

end for

until

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

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

end

程序后

2.1.4 動(dòng)態(tài)分簇

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

2.2 簇頭的選舉

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

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

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

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

（13）

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

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

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

（14）

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

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

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

（15）

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

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

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

（16）

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

α=Einit/Eres（i）

（17）

β=γ=（1-α）/2

（18）

運(yùn)行過(guò)程中，α動(dòng)態(tài)增大，剩余能量大的節(jié)點(diǎn)當(dāng)選簇頭的概率更高，使得能量更加均衡。

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

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

（19）

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

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

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

簇頭節(jié)點(diǎn)完成一個(gè)輪詢(xún)周期后進(jìn)行數(shù)據(jù)的融合，采用CSMA機(jī)制單跳將數(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é)果和聚類(lèi)中心;

CH←離聚類(lèi)中心最近的節(jié)點(diǎn)

el se

fo r i=1 to n do

根據(jù)式（17）計(jì)算每個(gè)節(jié)點(diǎn)的參量p（i）

end for

if? pCH≤λpmax（i） then

CH←pmax（i）對(duì)應(yīng)節(jié)點(diǎn)

end if

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

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

end if

end if

end for

程序后

2.4 算法復(fù)雜度分析

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

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

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

3 仿真與分析

3.1 仿真環(huán)境

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

3.2 GA改進(jìn)FCM的必要性分析

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

3.3 成簇結(jié)果

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

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

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

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

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

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

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

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

4 結(jié)語(yǔ)

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

參考文獻(xiàn)

[1]?徐晶晶，張欣慧，許必宵，等.無(wú)線(xiàn)傳感器網(wǎng)絡(luò)分簇算法綜述[J].計(jì)算機(jī)科學(xué)，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.