基于PSO 優(yōu)化模糊C 均值的WSN 分簇路由算法

孫愛晶，李世昌，張藝才

（1.西安郵電大學(xué)通信與信息工程學(xué)院，陜西 西安 710121；2.西安郵電大學(xué)電子工程學(xué)院，陜西 西安 710121）

1 引言

無線傳感器網(wǎng)絡(luò)（WSN,wireless sensor network）位于物聯(lián)網(wǎng)的感知層，是由眾多的傳感器節(jié)點(diǎn)構(gòu)成的一種自組織網(wǎng)絡(luò)，目前，已被廣泛地應(yīng)用于環(huán)境檢測等領(lǐng)域[1]。傳感器節(jié)點(diǎn)具有體積小、性能穩(wěn)定和功耗低等特點(diǎn)。然而，由于節(jié)點(diǎn)自身能量有限，網(wǎng)絡(luò)的生命周期主要由節(jié)點(diǎn)的能量決定，因此如何平衡節(jié)點(diǎn)的負(fù)載始終是眾多學(xué)者研究的熱點(diǎn)問題。目前，研究者已經(jīng)提出多種優(yōu)化算法來解決這一問題，主要通過優(yōu)化網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)、提高網(wǎng)絡(luò)的通信效率來延長網(wǎng)絡(luò)的生命周期。

針對節(jié)點(diǎn)的能耗問題，文獻(xiàn)[2]提出了經(jīng)典的LEACH（low energy adaptive clustering hierarchy）算法，將每一輪分為2 個階段：成簇階段和數(shù)據(jù)傳輸階段。成簇階段，LEACH 算法通過循環(huán)的方式在網(wǎng)絡(luò)中隨機(jī)挑選簇首，以實(shí)現(xiàn)網(wǎng)絡(luò)整體能耗的均衡。數(shù)據(jù)傳輸階段，簇首直接與基站通信，但由于簇首分布不均，且容易形成極大簇和極小簇，導(dǎo)致一些節(jié)點(diǎn)過載，使網(wǎng)絡(luò)的生命周期變短。

針對LEACH 算法存在的問題，學(xué)者提出多種改進(jìn)方法。文獻(xiàn)[3]在LEACH 算法的基礎(chǔ)上提出LEACH-C 算法，成簇階段不再采用隨機(jī)挑選簇首的方式，而是由基站根據(jù)節(jié)點(diǎn)的剩余能量來選擇簇首，但簇首選取僅考慮了節(jié)點(diǎn)的剩余能量。文獻(xiàn)[4]針對LEACH 算法提出了改進(jìn)的EE-LEACH，成簇階段選取剩余能量較高的節(jié)點(diǎn)作為簇首，同時(shí)數(shù)據(jù)傳輸階段選擇剩余能量較高的節(jié)點(diǎn)作為中繼節(jié)點(diǎn)，平衡網(wǎng)絡(luò)中的能耗，但數(shù)據(jù)傳輸階段可能會形成路由環(huán)路和數(shù)據(jù)分組向后轉(zhuǎn)發(fā)。文獻(xiàn)[5]提出了LEACH-improved 算法，通過在成簇階段加入間距因子、剩余能量因子和節(jié)點(diǎn)密度因子來改進(jìn)LEACH 閾值計(jì)算式，同時(shí)綜合考慮節(jié)點(diǎn)剩余能量和地理位置選擇簇首，減緩了節(jié)點(diǎn)死亡，但容易形成極大簇和極小簇。

針對分簇路由方法，學(xué)者進(jìn)行了多種改進(jìn)。文獻(xiàn)[6]提出了EEUC（energy-efficient uneven clustering）算法，成簇階段利用非均勻成簇的方法，數(shù)據(jù)傳輸階段的簇首以多跳的方式將數(shù)據(jù)傳到基站，有效地平衡了簇首的負(fù)載，但網(wǎng)絡(luò)規(guī)模越大，距離基站遠(yuǎn)的簇就越大，不利于大規(guī)模部署。文獻(xiàn)[7]提出了FUCHAR（fuzzy based unequal clustering and ACO based routing）算法，成簇階段使用模糊邏輯算法選取簇首，并將網(wǎng)絡(luò)劃分為不等簇，然后根據(jù)閾值動態(tài)更新簇首，數(shù)據(jù)傳輸階段使用蟻群算法規(guī)劃路由，實(shí)現(xiàn)了網(wǎng)絡(luò)負(fù)載均衡。文獻(xiàn)[8]提出了FBECS（fuzzy based enhanced cluster head selection）算法，成簇階段使用模糊邏輯算法，根據(jù)節(jié)點(diǎn)剩余能量、節(jié)點(diǎn)密度與基站的距離計(jì)算每個節(jié)點(diǎn)的資格指數(shù)，節(jié)點(diǎn)通過隨機(jī)生成的隨機(jī)數(shù)與資格指數(shù)比較以產(chǎn)生簇首，有效地平衡了負(fù)載，但數(shù)據(jù)傳輸階段僅考慮了單跳傳輸，不利于大規(guī)模部署。文獻(xiàn)[9]提出PECE（predictive energy consumption efficiency）算法，成簇階段通過節(jié)點(diǎn)度、節(jié)點(diǎn)間的相對距離和節(jié)點(diǎn)剩余能量選擇簇首，數(shù)據(jù)傳輸階段在考慮路徑能量消耗和傳播時(shí)延的基礎(chǔ)上，使用蜂群優(yōu)化算法選擇最優(yōu)路徑，提高整體的網(wǎng)絡(luò)性能，平衡整個網(wǎng)絡(luò)的負(fù)載，延長網(wǎng)絡(luò)的生命周期。文獻(xiàn)[10]提出了BeeSwarm 算法，該算法在成簇階段首先使用人工蜂群算法基于能量和距離因子尋找最優(yōu)簇首并成簇，數(shù)據(jù)傳輸階段使用人工蜂群算法為簇內(nèi)節(jié)點(diǎn)規(guī)劃到簇首的路由路徑，簇首直接與基站通信。但BeeSwarm 算法在規(guī)劃路徑的過程中并沒有考慮中繼節(jié)點(diǎn)的能量，這會導(dǎo)致節(jié)點(diǎn)早衰。

為了解決上述問題，本文在已有研究的基礎(chǔ)上提出了一種基于粒子群優(yōu)化（PSO,particle swarm optimization）算法優(yōu)化模糊C 均值（FCM,fuzzy C-means）的分簇路由算法POFCA。在成簇階段，使用PSO 算法優(yōu)化FCM 算法的初始聚類中心，避免FCM 算法在聚類過程中陷入局部最優(yōu)。同時(shí)考慮到節(jié)點(diǎn)的隨機(jī)部署會使一些節(jié)點(diǎn)距基站較近，因此在總簇?cái)?shù)的基礎(chǔ)上加入了基站簇，簇內(nèi)節(jié)點(diǎn)直接與基站通信。為了防止簇首過載，簇首通過簇內(nèi)節(jié)點(diǎn)的剩余能量、相對距離計(jì)算出每個節(jié)點(diǎn)的適應(yīng)度函數(shù)值，動態(tài)地更新簇首。在數(shù)據(jù)傳輸階段，簇內(nèi)節(jié)點(diǎn)直接將數(shù)據(jù)包發(fā)送給簇首，簇首將收集的數(shù)據(jù)融合之后，通過最佳能距比，判斷簇首是否需要多跳傳輸將數(shù)據(jù)轉(zhuǎn)發(fā)到基站，并基于距離因子、能量因子和節(jié)點(diǎn)負(fù)載，使用貓群優(yōu)化算法為簇首規(guī)劃最優(yōu)前向路由路徑，降低簇首負(fù)載。

2 系統(tǒng)模型

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

對本文算法與對比算法所使用的網(wǎng)絡(luò)模型，做出如下幾點(diǎn)假設(shè)。

1) 節(jié)點(diǎn)被隨機(jī)部署在目標(biāo)區(qū)域內(nèi)，部署后節(jié)點(diǎn)不再移動，每個節(jié)點(diǎn)都有唯一的ID。

2) 所有的節(jié)點(diǎn)具有相同的初始能量、計(jì)算能力與通信能力，可自動調(diào)節(jié)發(fā)送功率。

3) 每個節(jié)點(diǎn)都可獨(dú)立地與基站通信，基站的位置已知。

4) 節(jié)點(diǎn)可以根據(jù)信號的到達(dá)角與信號強(qiáng)度計(jì)算自身的相對位置[11]。

2.2 能量模型

無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)的能耗主要產(chǎn)生于數(shù)據(jù)分組的收發(fā)，本文采用與LEACH[2]相同的能量模型進(jìn)行節(jié)點(diǎn)之間的通信。根據(jù)節(jié)點(diǎn)i與節(jié)點(diǎn)j之間的距離，選擇信道模型。節(jié)點(diǎn)發(fā)送kbit 數(shù)據(jù)到距離為d的節(jié)點(diǎn)所需消耗的能量為

節(jié)點(diǎn)接收和融合kbit 數(shù)據(jù)消耗的能量為

其中，Eelec為接收或發(fā)送1 bit 數(shù)據(jù)所需消耗的能量，Eda為節(jié)點(diǎn)融合1 bit 數(shù)據(jù)所消耗的能量。節(jié)點(diǎn)選用何種發(fā)射模型進(jìn)行通信由決定，fsε和εmp為自由空間信道模型和多徑衰落模型功率放大所需的能量，當(dāng)節(jié)點(diǎn)間的距離d＜d0時(shí)，選擇自由空間信道模型，否則選擇多徑衰落模型。

3 FCM 算法的優(yōu)化

3.1 FCM 算法

FCM 算法[12]是一種軟聚類算法，被廣泛地應(yīng)用于機(jī)器學(xué)習(xí)之中，在無線傳感器網(wǎng)絡(luò)中可以表現(xiàn)為節(jié)點(diǎn)對某一聚類中心的隸屬度是模糊的，可以表示為

其中，uij表示節(jié)點(diǎn)i對聚類中心j的隸屬度，c表示聚類中心數(shù)，節(jié)點(diǎn)i對所有聚類中心的隸屬度總和為1。

假設(shè)有N個節(jié)點(diǎn)被隨機(jī)拋灑在目標(biāo)區(qū)域內(nèi)，網(wǎng)絡(luò)的聚類中心數(shù)為c，F(xiàn)CM 算法可以通過最小化目標(biāo)函數(shù)，將整個網(wǎng)絡(luò)按地理相似度進(jìn)行劃分。FCM算法的目標(biāo)函數(shù)可以表示為

其中，m為模糊因子，dij為第i個節(jié)點(diǎn)與第j個聚類中心的歐氏距離，uij為節(jié)點(diǎn)i對聚類中心j的隸屬度，可以表示為

聚類中心數(shù)可以表示為

當(dāng)?shù)Ｖ箷r(shí)，輸出最優(yōu)聚類中心。

3.2 PSO 算法優(yōu)化FCM 算法

FCM 算法簡單，收斂快，但對初始聚類中心較敏感，容易陷入局部最優(yōu)，這在一定程度上限制了FCM 算法的應(yīng)用。

PSO 算法[13]是模擬鳥群覓食行為的一種群體優(yōu)化算法。PSO 算法中，每個粒子都可以看作一個可行解，根據(jù)適應(yīng)度函數(shù)可以計(jì)算出每個粒子的適應(yīng)度值，從而得到全局最優(yōu)解gBest 和局部最優(yōu)解pBest。每個粒子根據(jù)全局最優(yōu)解和局部最優(yōu)解更新自身的速度和位置，可以表示為

其中，c1、c2為學(xué)習(xí)因子，通常取2；v∈[vmin,vmax]；rand ∈(0,1)；w為慣性權(quán)重，w越大，全局尋優(yōu)能力越強(qiáng)；w越小，局部尋優(yōu)能力越強(qiáng)，w一般隨著迭代次數(shù)增加而線性下降，可以表示為

其中，w∈[wmin,wmax]，iter 為當(dāng)前迭代次數(shù)，itermax為最大迭代次數(shù)。

PSO 算法優(yōu)化FCM 算法的步驟如下[14-15]。

步驟1PSO 算法種群初始化，參數(shù)初始化

步驟2根據(jù)式(4)，計(jì)算全局最優(yōu)解gBest 和局部最優(yōu)解pBest

步驟3根據(jù)全局最優(yōu)解gBest 和局部最優(yōu)解pBest 更新每個粒子的速度和位置

步驟4重復(fù)步驟2 和步驟3，直至達(dá)到最大迭代次數(shù)

步驟5將PSO 算法迭代的最優(yōu)解作為FCM算法的初始聚類中心

步驟6執(zhí)行FCM 算法

步驟7輸出最優(yōu)聚類中心

PSO 算法優(yōu)化FCM 算法流程如圖1 所示。

4 POFCA

POFCA 以輪為基本單位，每輪由成簇階段和數(shù)據(jù)傳輸階段組成。成簇階段，基于最優(yōu)簇首數(shù)，使用PSO 算法優(yōu)化FCM 算法對網(wǎng)絡(luò)進(jìn)行分簇，并基于剩余能量和相對距離動態(tài)地更新簇首。數(shù)據(jù)傳輸階段，通過最優(yōu)能距比判斷簇首是否需要多跳，并基于距離因子、能量因子和節(jié)點(diǎn)負(fù)載，使用貓群算法為簇首規(guī)劃最優(yōu)前向路由路徑。

圖1 PSO 算法優(yōu)化FCM 算法流程

4.1 成簇階段

成簇階段使用PSO 算法優(yōu)化FCM 算法，根據(jù)最優(yōu)簇首數(shù)加上額外的基站簇，將整個網(wǎng)絡(luò)劃分為均勻的簇，降低簇內(nèi)節(jié)點(diǎn)的通信成本。同時(shí)動態(tài)的簇首更新機(jī)制可以避免簇首過載，使簇內(nèi)的負(fù)載更加均衡。

4.1.1 簇的形成

合理的簇首數(shù)有利于形成更加均勻的簇，同時(shí)降低網(wǎng)絡(luò)的整體能量消耗成本。本文采用與文獻(xiàn)[16]相同的最優(yōu)簇首數(shù)，可以表示為

基于網(wǎng)絡(luò)最優(yōu)簇首數(shù)對粒子進(jìn)行編碼，編碼格式為{x1y1x2y2…xc yc}，其中，xi和yi代表聚類中心在目標(biāo)區(qū)域中的位置，可以表示為

其中，xmin、ymin、xmax、ymax分別代表目標(biāo)區(qū)域的邊界。

首先使用PSO 算法對聚類中心的位置進(jìn)行優(yōu)化，迭代結(jié)束后將最優(yōu)粒子作為FCM 算法的初始聚類中心，F(xiàn)CM 算法繼續(xù)進(jìn)行優(yōu)化，直至迭代停止，輸出最優(yōu)聚類中心，選擇距離聚類中心最近的節(jié)點(diǎn)作為簇首。然后簇首為簇內(nèi)成員分配TDMA 時(shí)隙，簇內(nèi)節(jié)點(diǎn)僅在分配給自己的時(shí)隙到來時(shí)發(fā)送數(shù)據(jù)，其他時(shí)候都保持休眠。

考慮到節(jié)點(diǎn)的隨機(jī)部署會存在一些節(jié)點(diǎn)距基站較近的情況，因此本文在最優(yōu)簇首數(shù)的基礎(chǔ)上額外增添了一個基站簇，使部分節(jié)點(diǎn)可以直接與基站進(jìn)行通信，減少了節(jié)點(diǎn)回傳所造成的額外能量消耗。新的粒子編碼格式為{x1y1x2y2…xc y cxBSyBS}，其中，xBS和yBS為基站坐標(biāo)，執(zhí)行PSO 算法優(yōu)化FCM算法時(shí)只需優(yōu)化前2c個位，最后兩位保持不變。

隨著網(wǎng)絡(luò)的運(yùn)行，存活節(jié)點(diǎn)的數(shù)目也會逐漸減少，因此分簇是一個動態(tài)的過程，當(dāng)最優(yōu)的簇首數(shù)發(fā)生變化時(shí)，就需要重新成簇。

4.1.2 動態(tài)簇首的選舉

簇首收集簇內(nèi)節(jié)點(diǎn)數(shù)據(jù)會給簇首帶來較大的負(fù)載，而簇內(nèi)節(jié)點(diǎn)的負(fù)載則相對較小，為了平衡簇內(nèi)節(jié)點(diǎn)的負(fù)載，考慮簇內(nèi)節(jié)點(diǎn)的剩余能量與相對距離這2 個因素動態(tài)更新簇首。每次分簇完成后的首輪都以距聚類中心最近的節(jié)點(diǎn)擔(dān)任簇首，其他輪則綜合考慮剩余能量與節(jié)點(diǎn)之間的相對距離計(jì)算每個節(jié)點(diǎn)的適應(yīng)度函數(shù)的值，評價(jià)是否擔(dān)任簇首。

能量是節(jié)點(diǎn)面臨的最重要的挑戰(zhàn)，選擇能量高的節(jié)點(diǎn)擔(dān)任簇首有助于簇內(nèi)負(fù)載更均衡。因此，考慮節(jié)點(diǎn)i的剩余能量與簇內(nèi)所有存活節(jié)點(diǎn)的平均剩余能量的比值作為參考，可以表示為

其中，n為節(jié)點(diǎn)i所在簇內(nèi)存活節(jié)點(diǎn)的數(shù)目，Eres(i)為節(jié)點(diǎn)i的剩余能量。節(jié)點(diǎn)i剩余能量越大，f1(i) 就越大，當(dāng)選簇首的概率就越高。

節(jié)點(diǎn)的相對距離可以表示為

其中，dij表示為節(jié)點(diǎn)i與簇內(nèi)其他節(jié)點(diǎn)j之間的距離。由式(13)可知，f2(i) 越大，節(jié)點(diǎn)之間的相對距離越小，節(jié)點(diǎn)之間的通信代價(jià)就越小。

每輪數(shù)據(jù)傳輸階段，節(jié)點(diǎn)都會將自身剩余能量和位置包含在數(shù)據(jù)分組中，簇首根據(jù)約定好的通信協(xié)議讀取該數(shù)據(jù)，然后通過式(14)計(jì)算每個節(jié)點(diǎn)的適應(yīng)度值。節(jié)點(diǎn)的剩余能量越高，相對距離越大，節(jié)點(diǎn)在下一輪當(dāng)選簇首的概率就會越大。

其中，α、β為權(quán)重因子，用于動態(tài)調(diào)整參數(shù)的權(quán)重，初始階段。隨著網(wǎng)絡(luò)的運(yùn)行，節(jié)點(diǎn)的剩余能量將會成為直接影響網(wǎng)絡(luò)生命周期的重要因素，因此α、β需要在網(wǎng)絡(luò)運(yùn)行階段動態(tài)更新，可表示為

其中，Eloss為簇內(nèi)所有節(jié)點(diǎn)所消耗的能量，Etotal為簇內(nèi)初始的總能量。能量消耗越多，α就會越大，節(jié)點(diǎn)的剩余能量也就越重要，整個簇內(nèi)負(fù)載就會更加均衡。

為了避免頻繁更換簇首造成不必要的通信損耗，當(dāng)前的簇首節(jié)點(diǎn)會將自身的適應(yīng)度函數(shù)值與簇內(nèi)最大的適應(yīng)度函數(shù)值的節(jié)點(diǎn)做比較[16]。

其中，λ為網(wǎng)絡(luò)系數(shù)，決定簇首的更新速度。若式(16)滿足，則簇首通知適應(yīng)度函數(shù)值最大的節(jié)點(diǎn)作為下一輪的簇首，并交換簇內(nèi)成員信息。新簇首為簇內(nèi)成員分配新的TDMA 時(shí)隙，節(jié)點(diǎn)僅在時(shí)隙到來時(shí)發(fā)送數(shù)據(jù)分組，其他時(shí)間則休眠，降低節(jié)點(diǎn)能量損耗。若式(16)不滿足，則保持當(dāng)前簇首，下一輪簇內(nèi)其他節(jié)點(diǎn)還是默認(rèn)將數(shù)據(jù)發(fā)送到當(dāng)前簇首。

4.2 數(shù)據(jù)傳輸階段

簇內(nèi)節(jié)點(diǎn)根據(jù)TDMA 時(shí)隙將數(shù)據(jù)分組發(fā)送給簇首后，簇首對收集到的數(shù)據(jù)進(jìn)行融合，并基于簇首到基站的距離選擇合適的中繼節(jié)點(diǎn)將數(shù)據(jù)轉(zhuǎn)發(fā)到基站，減輕長距離傳輸給簇首帶來的負(fù)載，實(shí)現(xiàn)簇首負(fù)載平衡。

針對數(shù)據(jù)傳輸階段簇首負(fù)載平衡，已有的算法[17-18]都是采用簇首到簇首的轉(zhuǎn)發(fā)來平衡簇首負(fù)載。盡管能夠在一定程度上減輕一些距基站較遠(yuǎn)簇首的負(fù)載，但簇首與簇首轉(zhuǎn)發(fā)會給相距較近的基站的簇首帶來額外負(fù)載。

為了減輕簇首的負(fù)載，基于簇首節(jié)點(diǎn)i與基站的距離di_BS，決定簇首應(yīng)該經(jīng)過幾次中繼然后將數(shù)據(jù)轉(zhuǎn)發(fā)到基站，round()表示四舍五入。根據(jù)最優(yōu)傳輸距離[19]dbest計(jì)算跳數(shù)，可以表示為

4.2.1 貓群算法

對于組合優(yōu)化問題的求解，仿生算法往往可以帶來好的結(jié)果。貓群優(yōu)化（CSO,cat swarm optimization）算法[20]通過觀測貓的習(xí)性而提出，同時(shí)基于貓的習(xí)性，將貓群分為搜索貓和跟蹤貓，使其具有更好的全局尋優(yōu)且不易陷入局部最優(yōu)的特性，相較于遺傳算法與PSO 算法，其實(shí)現(xiàn)起來也更加容易，收斂速度也更快。因此選擇CSO 算法求解最優(yōu)路徑。

CSO 算法中每只貓都代表一個可行解。每只貓由貓的位置、貓的速度、適應(yīng)度和標(biāo)志值4 個屬性組成，標(biāo)志值用于區(qū)分貓?zhí)幱谒褜つＪ竭€是跟蹤模式，CSO 算法根據(jù)貓所處的模式進(jìn)行不同的操作。

1) 搜尋模式

搜尋模式是一種全局尋優(yōu)模式，通過模擬貓尋找下一個較優(yōu)位置，這一狀態(tài)定義了4 個變量。

SMP（記憶池），定義了每只貓的記憶大小，在搜尋模式下，將自身的位置復(fù)制M份。

SRD（變化域），定義了域的變化范圍，一般取0.2。

CDC（變化數(shù)），定義了變異的維度大小。

SPC（自身位置判斷），計(jì)算變異池中每只貓的適應(yīng)度，選擇適應(yīng)度最高的替代當(dāng)前貓。

處于搜尋模式的貓首先會將自身的位置復(fù)制M份，對于記憶池中的副本，根據(jù)CDC 的大小，隨機(jī)地對當(dāng)前值加上或者減去自身的SRD%，然后計(jì)算記憶池中所有副本的適應(yīng)度函數(shù)，選取適應(yīng)度最大的副本替代當(dāng)前貓。

2) 跟蹤模式

跟蹤模式是一種局部尋優(yōu)的模式，處于當(dāng)前模式的貓根據(jù)當(dāng)前全局最優(yōu)解更新自身的速度和位置。

其中，為全局最優(yōu)貓?jiān)诘赿維的位置，rand ∈(0,1)；c3是一個常量，一般取0.5；(t)為t時(shí)刻第k只貓?jiān)诘赿維的速度，(t+1)為更新后的速度。

CSO 算法可以分為以下5 個步驟。

步驟1初始化每只貓的位置和速度

步驟2根據(jù)分組率MR 將貓群隨機(jī)劃分為搜尋模式和跟蹤模式

步驟3根據(jù)貓所處模式分別進(jìn)行搜索算子和跟蹤算子

步驟4計(jì)算每只貓的適應(yīng)度，找到全局最優(yōu)解

步驟5判斷是否滿足停止條件，否則執(zhí)行步驟2～步驟4

貓群算法的工作流程如圖2 所示。

圖2 貓群算法的工作流程

CSO 算法尋找最優(yōu)路徑的過程需要評價(jià)路徑的好壞，才能進(jìn)一步尋找最優(yōu)路徑，因此需要為CSO 算法設(shè)計(jì)一個路徑選擇的適應(yīng)度函數(shù)。

4.2.2 路徑選擇適應(yīng)度函數(shù)設(shè)計(jì)

WSN 前向路由主要是為距基站較遠(yuǎn)的簇首選擇中繼節(jié)點(diǎn)，通過轉(zhuǎn)發(fā)來自簇首的數(shù)據(jù)分組，降低簇首的負(fù)載。假設(shè)數(shù)據(jù)分組需要經(jīng)過n跳發(fā)送到基站，也就是途經(jīng)n-1 個中繼節(jié)點(diǎn)，則最優(yōu)的中繼節(jié)點(diǎn)應(yīng)具備以下幾個特征。

1) 中繼節(jié)點(diǎn)與中繼節(jié)點(diǎn)之間的距離應(yīng)該盡量均衡。

2) 中繼節(jié)點(diǎn)應(yīng)該具備較高的能量，以滿足數(shù)據(jù)的傳輸需求。

3) 總距離應(yīng)該盡可能地接近簇首與基站直接通信的距離。

4) 中繼節(jié)點(diǎn)的選擇應(yīng)該避免選到其他簇首。

5) 中繼節(jié)點(diǎn)的負(fù)載應(yīng)該盡可能小，避免過度開發(fā)。

根據(jù)上述幾點(diǎn)要求，設(shè)計(jì)了相應(yīng)的適應(yīng)度函數(shù)，可以表示為

其中，Emin是中繼節(jié)點(diǎn)中能量最小的節(jié)點(diǎn)；節(jié)點(diǎn)的負(fù)載由節(jié)點(diǎn)接收數(shù)據(jù)分組的數(shù)量決定，loadmax是中繼節(jié)點(diǎn)中具有最大負(fù)載的節(jié)點(diǎn)；dmin和dmax分別是前向路由路徑中相鄰節(jié)點(diǎn)距離的最小值和最大值；dinit和dtotal分別是簇首與基站的距離和整條前向路由路徑的距離之和；α與β按照式(15)更新，將簇內(nèi)節(jié)點(diǎn)的總能量消耗換為需要規(guī)劃路由的簇首消耗的能量，簇內(nèi)總能量換為簇首的初始能量，隨著網(wǎng)絡(luò)的運(yùn)行，動態(tài)地調(diào)整參數(shù)權(quán)重比。

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

初始化階段網(wǎng)絡(luò)中共有N個節(jié)點(diǎn)，最優(yōu)簇首數(shù)為c，算法復(fù)雜度從成簇階段和數(shù)據(jù)傳輸階段2 個階段進(jìn)行分析。

成簇階段，PSO 迭代次為M，種群大小為K，維度為2c，因此PSO 算法的復(fù)雜度為O(MKc)。FCM 算法的迭代次數(shù)為M，聚類中心維度為2c，因此FCM 算法的復(fù)雜度為O(Mc)。當(dāng)簇首動態(tài)更新時(shí)，遍歷的節(jié)點(diǎn)數(shù)為N，復(fù)雜度為O(N)。因此，成簇階段的復(fù)雜度為O(MKc)。

數(shù)據(jù)傳輸階段，簇首數(shù)為c，迭代次數(shù)為M，種群大小為K，因此，CSO 算法的復(fù)雜度為O(MKc)。

因此，POFCA 每輪的復(fù)雜度為O(MKc)，復(fù)雜度等同于算法執(zhí)行所需要的基本運(yùn)算次數(shù)。POFCA的每輪由成簇階段和數(shù)據(jù)傳輸階段組成，每階段執(zhí)行所需要的基本運(yùn)算次數(shù)為MKc，即POFCA 每輪可以在2MKc次的運(yùn)算次數(shù)中得到結(jié)果，算法可行。

5 仿真分析

采用 MATLAB 對本文算法和 LEACH[2]、LEACH-improved[7]等對比算法進(jìn)行仿真，并在相同的仿真環(huán)境中對算法進(jìn)行對比分析，仿真參數(shù)如表1所示。

5.1 成簇結(jié)果對比

圖3 為LEACH 成簇結(jié)果。LEACH 的簇首是隨機(jī)生成的，從圖3 可以得出，2 號簇、3 號簇、5 號簇和8 號簇分別有15、21、15、15 個節(jié)點(diǎn)，而1 號簇只有4 個節(jié)點(diǎn)。4 個較大的簇吸引了65%的節(jié)點(diǎn)，而最小的簇僅吸引了4%的節(jié)點(diǎn)，同時(shí)簇首在簇中的位置不夠合理，會增加額外的通信開銷。

表1 仿真參數(shù)

圖3 LEACH 成簇結(jié)果

圖4 為FCM 算法成簇結(jié)果。FCM 算法需要指定聚類的數(shù)目，將聚類數(shù)目設(shè)為10，并對初始聚類中心進(jìn)行初始化。從圖4 中可以看出，1～3 號簇是完全重合的，這是由于FCM 算法對初始聚類中心敏感，若初始聚類中心相隔較近，則會重合，因此對FCM 算法進(jìn)行優(yōu)化是有必要的。

圖5 為POFCA 成簇結(jié)果。POFCA 的聚類數(shù)由最優(yōu)簇首數(shù)+1（基站簇）決定。從圖5 中可以看出，POFCA 的每個簇都比較均勻，簇內(nèi)節(jié)點(diǎn)的數(shù)目較穩(wěn)定，同時(shí)簇首在簇中的位置也比較居中，基站簇（11 號簇）使距基站更近的節(jié)點(diǎn)直接加入基站進(jìn)行直接通信，更合理。

圖4 FCM 算法成簇結(jié)果

圖5 POFCA 成簇結(jié)果

由圖3～圖5 可以看出，與LEACH 相比，POFCA的成簇結(jié)果更均勻，并克服了極大簇和極小簇的缺點(diǎn)。同時(shí)，使用PSO 算法優(yōu)化FCM 算法克服了FCM算法對聚類中心敏感的問題，驗(yàn)證了POFCA 成簇的可行性和優(yōu)越性。

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

網(wǎng)絡(luò)節(jié)點(diǎn)一經(jīng)部署便無法移動或補(bǔ)充能量。隨著工作輪數(shù)的增加，一些節(jié)點(diǎn)由于能量耗盡而死亡，產(chǎn)生新的覆蓋空洞，影響整個網(wǎng)絡(luò)的性能，因此網(wǎng)絡(luò)生命周期是評價(jià)無線傳感器網(wǎng)絡(luò)性能的重要指標(biāo)。

圖6 是POFCA 和LEACH 算法、LEACHimproved 算法節(jié)點(diǎn)存活數(shù)的對比。從圖6 中可以看出，POFCA、LEACH 算法和LEACH-improved 算法首個節(jié)點(diǎn)的死亡時(shí)間分別為1 173 輪、877 輪和816 輪，POFCA 比LEACH 算法、LEACH-improved算法分別提升了34%和44%。同時(shí)，POFCA 存活節(jié)點(diǎn)數(shù)目在整體上均高于2 種對比算法。因此，本文算法能有效地提高WSN 的網(wǎng)絡(luò)生命周期。

圖6 POFCA 和LEACH 算法、LEACH-improved 算法節(jié)點(diǎn)存活數(shù)的對比

5.3 網(wǎng)絡(luò)剩余能量

圖7 為3 種算法剩余能量的對比。從圖7 中可以看出，LEACH 算法和LEACH-improved 算法的能量消耗差距不大，因?yàn)樗鼈冊诰垲惖倪^程中形成極大簇和極小簇的概率非常大，所以能量消耗不均衡。POFCA 是一種依靠地理位置的均勻分簇算法，簇首的選擇和簇的構(gòu)建都考慮了整體的負(fù)載均衡，因此所需消耗的能量較少。

圖7 3 種算法剩余能量的對比

6 結(jié)束語

為了平衡WSN 負(fù)載，本文提出了一種新的分簇路由算法POFCA，該算法分別在成簇階段和數(shù)據(jù)傳輸階段進(jìn)行了優(yōu)化。在成簇階段，使用PSO 算法優(yōu)化FCM 算法，克服了FCM 算法容易陷入局部最優(yōu)的缺點(diǎn)，使每個簇都更加緊湊，動態(tài)的簇首更新機(jī)制也使每個簇內(nèi)的負(fù)載更均衡，同時(shí)基站簇的加入減少了節(jié)點(diǎn)的回傳。在數(shù)據(jù)傳輸階段，根據(jù)最佳能距比判斷簇首是否需要多跳，基于距離因子、能量因子和節(jié)點(diǎn)負(fù)載使用CSO 算法為簇首規(guī)劃前向路由路徑。仿真分析結(jié)果表明，相較于已有算法，POFCA 的分簇結(jié)果更加均勻，可以有效地延長網(wǎng)絡(luò)生命周期，降低節(jié)點(diǎn)的能量損耗。

本文算法主要針對二維網(wǎng)絡(luò)，后續(xù)的工作可結(jié)合實(shí)際場景進(jìn)一步研究三維WSN、無基站場景下WSN 的路由優(yōu)化問題。