基于改進(jìn)模糊C均值的能量均衡LEACH算法

王宗山，李 波，保利勇，李艾珊，丁洪偉

（1.云南大學(xué) 信息學(xué)院，云南 昆明 650504；2.復(fù)旦大學(xué) 電子工程系，上海 200433）

0 引 言

無線傳感器網(wǎng)絡(luò)（Wireless Sensor Network，WSN）是由很多廉價(jià)的微型傳感器節(jié)點(diǎn)以無線通信方式組成的多跳自組織網(wǎng)絡(luò)，主要用于監(jiān)測(cè)指定區(qū)域并獲取數(shù)據(jù)，但節(jié)點(diǎn)能量有限且無法更換電池[1?3]。針對(duì)上述問題，國內(nèi)外提出了多種路由算法。文獻(xiàn)[4]最早提出了經(jīng)典的分簇路由LEACH算法，顯著提升了網(wǎng)絡(luò)性能，但LEACH隨機(jī)選取簇首導(dǎo)致網(wǎng)絡(luò)分簇不均勻，加大了網(wǎng)絡(luò)能耗。文獻(xiàn)[5]對(duì)LEACH算法進(jìn)行改進(jìn)，提出LEACH?C。LEACH?C在選擇簇首節(jié)點(diǎn)時(shí)，考慮節(jié)點(diǎn)剩余能量，使簇首選舉更加合理，但沒有考慮簇首的位置且過于依賴基站。文獻(xiàn)[6]提出一種基于Fuzzy C?Means聚類的改進(jìn)LEACH算法（NEW LEACH），首先利用Fuzzy C?Means進(jìn)行分簇，在每個(gè)簇內(nèi)考慮剩余能量的LEACH算法選舉簇首，但沒有考慮簇首到基站的距離。文獻(xiàn)[7?10]通過改進(jìn)閾值、引入分區(qū)或動(dòng)態(tài)分簇等方式對(duì)LEACH算法進(jìn)行改進(jìn)。

本文在研究LEACH、NEW LEACH的基礎(chǔ)上，提出一種基于遺傳算法和模糊C均值聚類的改進(jìn)LEACH算法（GFCR?LEACH）。仿真結(jié)果表明，相比于LEACH和NEW LEACH，GFCR?LEACH成簇效果理想，顯著延長(zhǎng)了網(wǎng)絡(luò)生命周期，提高了網(wǎng)絡(luò)吞吐量。

1 LEACH協(xié)議概述

1.1 LEACH協(xié)議簡(jiǎn)介

LEACH協(xié)議是一種經(jīng)典分簇路由協(xié)議，網(wǎng)絡(luò)按輪進(jìn)行，周期性輪換簇首，每輪分為簇的構(gòu)建和數(shù)據(jù)傳輸兩個(gè)階段。

簇構(gòu)建階段：每個(gè)節(jié)點(diǎn)生成一個(gè)0~1之間的隨機(jī)數(shù)μ并和閾值T(n)作比較。若滿足μ

式中：p是成為簇首的理想概率；r是當(dāng)前輪數(shù)；G是1p輪內(nèi)未當(dāng)選過簇首的節(jié)點(diǎn)集。

數(shù)據(jù)傳輸階段：簇首創(chuàng)建TDMA時(shí)隙表，簇內(nèi)成員在自己的時(shí)隙與簇首通信。簇首將接收到的數(shù)據(jù)融合之后單跳發(fā)至基站。至此，本輪結(jié)束。

1.2 能耗模型

LEACH算法中，數(shù)據(jù)傳輸?shù)牧鞒膛c能耗過程如圖1所示[11]。

圖1 數(shù)據(jù)傳輸過程與能耗模型

節(jié)點(diǎn)發(fā)送數(shù)據(jù)的能量消耗主要考慮發(fā)射電路能量消耗和節(jié)點(diǎn)功率放大器能量消耗。節(jié)點(diǎn)經(jīng)距離d發(fā)送kbit數(shù)據(jù)包的能耗為[12]：

接收端消耗的能量為：

式中：Eelec表示發(fā)送單位比特電路消耗的能量；d0是一個(gè)距離常量，當(dāng)傳輸距離d大于閾值d0時(shí)，采用多路徑衰減模型，否則，采用自由空間信道模型[13]；εmp和εfs分別表示兩種信道模型下功率放大所需能量。

2 GFCR?LEACH協(xié)議

LEACH算法隨機(jī)選舉簇首使分簇不均勻，加大了網(wǎng)絡(luò)能耗。本文提出一種改進(jìn)的LEACH算法。網(wǎng)絡(luò)初始化階段，基站根據(jù)節(jié)點(diǎn)坐標(biāo)，采用遺傳算法優(yōu)化的模糊C均值算法將網(wǎng)絡(luò)分割成h個(gè)區(qū)域，在每個(gè)區(qū)域內(nèi)，利用優(yōu)化的LEACH協(xié)議完成簇首的選舉和數(shù)據(jù)的傳輸。

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

為研究GFCR?LEACH對(duì)網(wǎng)絡(luò)的影響，對(duì)網(wǎng)絡(luò)節(jié)點(diǎn)和網(wǎng)絡(luò)模型作出如下假設(shè)：

1）M×M的監(jiān)測(cè)區(qū)域內(nèi)隨機(jī)不均勻散布N個(gè)傳感器節(jié)點(diǎn)；

2）傳感器節(jié)點(diǎn)的初始能量相同且位置固定，部署完成之后再無人為干涉；

3）任意節(jié)點(diǎn)的處理能力和通信能力相等，均可感知自身剩余能量；

4）節(jié)點(diǎn)都能夠與基站通信，可以融合數(shù)據(jù)，具備擔(dān)任簇首的能力；

5）節(jié)點(diǎn)擁有唯一的網(wǎng)絡(luò)ID。

2.2 區(qū)域分割

2.2.1 最優(yōu)簇?cái)?shù)

模糊C均值算法對(duì)網(wǎng)絡(luò)節(jié)點(diǎn)進(jìn)行分類時(shí)需指定分類數(shù)。基于上述網(wǎng)絡(luò)模型和一階無線電能耗模型，網(wǎng)絡(luò)運(yùn)行一輪的能耗為[14]：式中：DtoBS為節(jié)點(diǎn)到基站的距離；EDA為簇首融合1 bit冗余信息的能耗。

對(duì)分類數(shù)h求偏導(dǎo)，滿足偏導(dǎo)數(shù)為零時(shí)的h，即為當(dāng)前網(wǎng)絡(luò)狀態(tài)下的最優(yōu)簇?cái)?shù)。求得的最優(yōu)簇?cái)?shù)為：

2.2.2 模糊C均值聚類算法

模糊C均值聚類算法[15]（FCM）通過優(yōu)化目標(biāo)函數(shù)得到每個(gè)樣本點(diǎn)對(duì)所有類中心的隸屬度，從而決定樣本點(diǎn)的類屬。假設(shè)樣本集合為X={x1,x2,…,x N}，將其分為h個(gè)模糊組，F(xiàn)CM聚類損失函數(shù)為：

式中：x i是第i個(gè)樣本點(diǎn)；m是模糊因子；h j是第j簇的中心；u ij表示樣本i對(duì)聚類中心j的隸屬度。u ij和h j分別滿足下式：

迭代的終止條件為：

式中：k是迭代步數(shù)；ε是誤差閾值。

2.2.3 遺傳算法優(yōu)化FCM初始聚類中心

FCM的性能依賴于初始聚類中心，容易得到局部最優(yōu)值。因此，本文利用遺傳算法確定初始聚類中心。遺傳算法[16]是模擬自然界遺傳機(jī)制和生物進(jìn)化論而形成的一種過程搜索最優(yōu)解算法。遺傳算法優(yōu)化FCM的步驟為[17?19]：

1）初始化參數(shù)：確定種群規(guī)模、交叉概率、變異概率，設(shè)置終止進(jìn)化準(zhǔn)則和聚類個(gè)數(shù)h；采用二進(jìn)制編碼，染色體χ={χ1…χi…χ2h}中的每?jī)蓚€(gè)等位基因代表一個(gè)聚類中心的坐標(biāo)。

2）隨機(jī)產(chǎn)生初始種群，設(shè)置進(jìn)化代數(shù)計(jì)數(shù)器t=0。

3）評(píng)價(jià)個(gè)體適應(yīng)度并記錄。其中，適應(yīng)度函數(shù)為f=1J m。

4）種群進(jìn)化（選擇、交叉、變異）。依據(jù)適應(yīng)度選擇新一代種群P(t+1)，并判斷是否滿足終止進(jìn)化準(zhǔn)則。

5）若滿足終止進(jìn)化準(zhǔn)則，終止計(jì)算并輸出聚類結(jié)果；否則，t=t+1，轉(zhuǎn)至步驟3），繼續(xù)迭代。

2.3 簇首選擇

2.3.1 候選節(jié)點(diǎn)

簇首選舉階段，節(jié)點(diǎn)i將自身剩余能量Erest(i)和所在第j簇的平均剩余能量Eave(j)按下式比較：

若式（11）成立，則節(jié)點(diǎn)i成為本輪候選節(jié)點(diǎn)，否則，置為普通節(jié)點(diǎn)。每個(gè)候選節(jié)點(diǎn)生成一個(gè)0~1之間的隨機(jī)數(shù)μ，與改進(jìn)后的閾值T(n)作比較。如果滿足μ

2.3.2 改進(jìn)閾值公式

本文考慮節(jié)點(diǎn)的剩余能量、與基站之間的距離，對(duì)LEACH算法的閾值公式進(jìn)行改進(jìn)，改進(jìn)后的閾值公式為：

式中：p表示每個(gè)區(qū)域內(nèi)的簇首節(jié)點(diǎn)比例；Erest表示當(dāng)前節(jié)點(diǎn)的剩余能量；Eave表示當(dāng)前節(jié)點(diǎn)所在簇的平均剩余能量；dtoBS表示當(dāng)前節(jié)點(diǎn)到基站的距離；dave表示當(dāng)前節(jié)點(diǎn)所在簇內(nèi)所有節(jié)點(diǎn)到基站的平均距離；α和β是調(diào)節(jié)因子，滿足α+β=1。

根據(jù)式（12）可知，節(jié)點(diǎn)的剩余能量越少、距離基站越遠(yuǎn)，該節(jié)點(diǎn)得到的閾值T(n)就越小，要成為簇首節(jié)點(diǎn)，需要生成相對(duì)較小的隨機(jī)值。相反，節(jié)點(diǎn)的剩余能量越多、距離基站越近，該節(jié)點(diǎn)得到的閾值T(n)就越大。在相同的隨機(jī)數(shù)生成機(jī)制下，該節(jié)點(diǎn)有更大概率當(dāng)選簇首。這樣就保證了剩余能量多、距離基站近的節(jié)點(diǎn)有更大概率當(dāng)選為當(dāng)前輪次的簇首節(jié)點(diǎn)。

改進(jìn)后的閾值公式特點(diǎn)如下：

1）簇首比例：每簇只選一個(gè)簇首，故p等于每個(gè)簇內(nèi)節(jié)點(diǎn)個(gè)數(shù)的倒數(shù)。隨著網(wǎng)絡(luò)的運(yùn)行，簇內(nèi)節(jié)點(diǎn)不斷死亡，p值動(dòng)態(tài)增大，閾值公式相應(yīng)改變，以適應(yīng)當(dāng)前網(wǎng)絡(luò)狀態(tài)。

2）調(diào)節(jié)因子：α和β的取值影響整個(gè)網(wǎng)絡(luò)的性能。網(wǎng)絡(luò)初期，節(jié)點(diǎn)的剩余能量普遍較高，任意兩個(gè)節(jié)點(diǎn)之間的能量相差不多，簇首選舉時(shí)，節(jié)點(diǎn)的剩余能量及到基站的距離兩個(gè)因素重要程度基本相當(dāng)，將α置為0.6，β置為0.4。隨著網(wǎng)絡(luò)的運(yùn)行，節(jié)點(diǎn)的剩余能量參差不齊，能量因素所占比重增大。因此，在超過半數(shù)節(jié)點(diǎn)死亡時(shí)，將α置為0.8，β置為0.2。對(duì)多組取值進(jìn)行仿真實(shí)驗(yàn)對(duì)比，當(dāng)前取值效果良好。

3）改善有資格競(jìng)選簇首的節(jié)點(diǎn)集：不同于LEACH，本文算法在簇首選舉時(shí)，并不考慮節(jié)點(diǎn)在最近的1p輪中是否擔(dān)任過簇首。擔(dān)任過簇首的節(jié)點(diǎn)，只要滿足上述簇首選舉的條件，便可再次當(dāng)選。因?yàn)橛行┕?jié)點(diǎn)雖擔(dān)任過簇首，但剩余能量較多，距離基站較近，相比于其他節(jié)點(diǎn)，更適合當(dāng)選為當(dāng)前輪次的簇首。

2.3.3 特殊情況

每輪每簇只選一個(gè)簇首，因此，簇首選舉時(shí)會(huì)有兩種特殊情況：

1）簇內(nèi)任意候選節(jié)點(diǎn)生成的隨機(jī)值均大于閾值，即沒有節(jié)點(diǎn)能夠擔(dān)任當(dāng)前輪次的簇首；

2）簇內(nèi)多個(gè)候選節(jié)點(diǎn)生成的隨機(jī)值均小于閾值，即多個(gè)候選節(jié)點(diǎn)均可擔(dān)任當(dāng)前輪次的簇首。

上述兩種特殊情況下，選擇α?ErestEave+β?davedtoBS最大的節(jié)點(diǎn)擔(dān)任簇首。其中，α和β根據(jù)存活節(jié)點(diǎn)個(gè)數(shù)取相應(yīng)的值。這樣保證了剩余能量大且距離基站近的節(jié)點(diǎn)有更大概率當(dāng)選為當(dāng)前輪次的簇首。

2.3.4 選擇通信對(duì)象

每輪簇首更新之后，簇首節(jié)點(diǎn)根據(jù)終端節(jié)點(diǎn)的坐標(biāo)計(jì)算其到基站的距離dtoBS和到自身的距離dtoCH，并按下式進(jìn)行比較：

若式（13）成立，代表節(jié)點(diǎn)i到基站的距離小于到簇首的距離，簇首將節(jié)點(diǎn)i從時(shí)隙表中刪除。在當(dāng)前輪次，節(jié)點(diǎn)i直接與基站通信，否則，仍與簇首通信。這樣顯著減少了數(shù)據(jù)傳輸帶來的能耗。

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

LEACH算法的簇內(nèi)通信采用TDMA機(jī)制[7]。成簇之后，簇首建立TDMA方案，節(jié)點(diǎn)在自己的工作時(shí)間內(nèi)履行信息采集等工作，其余時(shí)間處于休眠狀態(tài)。這樣就會(huì)出現(xiàn)空閑時(shí)隙，造成能量浪費(fèi)。為解決這一問題，本文算法的簇內(nèi)通信介質(zhì)訪問控制（Medium Access Control，MAC）機(jī)制采用輪詢控制機(jī)制[20?21]。成簇之后，簇首根據(jù)節(jié)點(diǎn)的反饋信息生成輪詢表，輪詢順序和節(jié)點(diǎn)ID相對(duì)應(yīng)。當(dāng)簇內(nèi)節(jié)點(diǎn)處于休眠狀態(tài)、能量耗盡或直接和基站通信時(shí)，簇首將其從輪詢表中刪除，后面節(jié)點(diǎn)的輪詢順序依次提前。這樣不但可以充分利用時(shí)隙，又可以避免節(jié)點(diǎn)發(fā)送數(shù)據(jù)包時(shí)產(chǎn)生的碰撞，從而減少網(wǎng)絡(luò)能耗，提高網(wǎng)絡(luò)吞吐量。一個(gè)輪詢周期結(jié)束后，簇首對(duì)收集到的數(shù)據(jù)進(jìn)行去冗處理，采用CSMA機(jī)制單跳發(fā)至基站。

改進(jìn)的LEACH算法流程如圖2所示。

3 仿真實(shí)驗(yàn)及性能分析

3.1 仿真參數(shù)設(shè)計(jì)

本文在Matlab R2014b上對(duì)LEACH、NEW LEACH和本文算法進(jìn)行仿真，初始參數(shù)見表1。遺傳算法參數(shù)設(shè)置為[22]：種群大小為50，交叉概率pc=0.25，變異概率pm=0.05，最大迭代次數(shù)T=110，F(xiàn)CM的終止閾值ε=10-6。

3.2 實(shí)驗(yàn)結(jié)果及分析

1）成簇均勻性

LEACH、NEW LEACH、本文算法的成簇結(jié)果如圖3所示。傳統(tǒng)LEACH算法隨機(jī)選取簇首，導(dǎo)致成簇不均勻，分簇?cái)?shù)量不合理。NEW LEACH采用FCM聚類算法形成網(wǎng)絡(luò)分簇，簇首分布均勻，分簇?cái)?shù)量合理，但FCM算法的性能受初始聚類中心的影響，易收斂到局部最優(yōu)，導(dǎo)致簇的大小不均勻。本文算法引入遺傳算法，有效地解決了這一問題，使成簇更加理想。

圖2 改進(jìn)的LEACH算法流程圖

表1 仿真參數(shù)

圖3 成簇結(jié)果對(duì)比

2）網(wǎng)絡(luò)生命周期對(duì)比

與LEACH、NEW LEACH相比，本文算法均衡了網(wǎng)絡(luò)能耗，顯著延長(zhǎng)了網(wǎng)絡(luò)生命周期。三種算法的生命周期對(duì)比如圖4所示，節(jié)點(diǎn)死亡時(shí)間對(duì)比如圖5所示。

圖4 生命周期對(duì)比

圖5 節(jié)點(diǎn)死亡時(shí)間對(duì)比

3）網(wǎng)絡(luò)能耗對(duì)比

與LEACH、NEW LEACH相比，本文算法有效降低了網(wǎng)絡(luò)能耗，使網(wǎng)絡(luò)剩余能量始終多于另外兩種算法。三種算法的網(wǎng)絡(luò)剩余能量對(duì)比如圖6所示。

圖6 網(wǎng)絡(luò)剩余能量對(duì)比

4）網(wǎng)絡(luò)吞吐量對(duì)比

LEACH、NEW LEACH、本文算法的吞吐量對(duì)比如圖7所示。由于本文算法生存期長(zhǎng)，簇內(nèi)通信階段引入輪詢機(jī)制，使得吞吐量自始至終高于其他兩種算法。

圖7 吞吐量對(duì)比

4 結(jié) 語

針對(duì)LEACH算法和NEW LEACH算法分簇不均勻、能耗不均衡等問題，提出一種改進(jìn)的LEACH算法。通過更加均勻的分簇，引入候選節(jié)點(diǎn)，優(yōu)化閾值公式，選擇最佳通信對(duì)象，改進(jìn)通信機(jī)制等方式，在均衡網(wǎng)絡(luò)能耗的同時(shí)延長(zhǎng)了網(wǎng)絡(luò)的生命周期，提升了網(wǎng)絡(luò)的吞吐量，使本文協(xié)議在相同條件下可以獲取更多的監(jiān)測(cè)區(qū)域信息。因此，本文算法在傳感器節(jié)點(diǎn)和基站位置固定的監(jiān)測(cè)環(huán)境下，有更好的監(jiān)測(cè)效果。