基于混沌粒子群的改進(jìn)LEACH算法

劉曉理，王出航，王 雪

(長春師范大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，吉林 長春 130012)

0 引 言

無線傳感器網(wǎng)絡(luò)(Wireless Sensor Networks，WSNs)是由大量廉價的微型傳感器節(jié)點(diǎn)組成的[1]。由于WSNs具有傳感、計(jì)算、數(shù)據(jù)處理和通信能力等特點(diǎn)[2]，逐漸被廣泛應(yīng)用于需要感知和監(jiān)測數(shù)據(jù)的各個領(lǐng)域，如軍事戰(zhàn)爭、工農(nóng)業(yè)生產(chǎn)和智能家居等多個領(lǐng)域。

無線傳感器中節(jié)點(diǎn)自身能量有限且不易補(bǔ)充，使其在功率、存儲以及計(jì)算過程方面受到諸多限制[3]。因此，如何最大程度地降低網(wǎng)絡(luò)能耗成為WSNs路由協(xié)議設(shè)計(jì)中最具挑戰(zhàn)的問題之一。LEACH算法因具有能量利用率高的特點(diǎn)被廣泛應(yīng)用于路由協(xié)議設(shè)計(jì)中[4-5]，其運(yùn)行過程分為簇的建立和數(shù)據(jù)傳輸[6]。但LEACH算法僅是通過隨機(jī)概率的方式產(chǎn)生簇頭，并未考慮到節(jié)點(diǎn)能耗的差異性[7]。針對此問題，文獻(xiàn)[8]通過計(jì)算每個節(jié)點(diǎn)的中心度和鄰居數(shù)解決了選擇簇頭節(jié)點(diǎn)產(chǎn)生的隨機(jī)性。文獻(xiàn)[9]提出的粒子群算法雖然優(yōu)化了簇頭選擇，但沒有考慮到粒子群算法易陷入局部極值的問題。

針對LEACH算法中隨機(jī)概率選擇簇頭所產(chǎn)生的能耗問題和粒子群算法自身所存在的缺陷問題，文中提出一種基于混沌粒子群的LEACH算法(CPSOLEACH)，該算法基于混沌粒子群算法優(yōu)化簇頭選擇，同時引入混沌序列，增加粒子群的多樣性，這樣既能提高能量效率，均衡節(jié)點(diǎn)之間消耗，減少盲節(jié)點(diǎn)出現(xiàn)，也能避免粒子群算法陷入局部最優(yōu)。

1 系統(tǒng)模型

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

文中研究的網(wǎng)絡(luò)模型是在M×M區(qū)域內(nèi)隨機(jī)部署N個傳感器節(jié)點(diǎn)，基站位于區(qū)域內(nèi)的中心位置，具體設(shè)定條件如下[10]：

1)網(wǎng)絡(luò)部署完成后，包括基站在內(nèi)的所有節(jié)點(diǎn)都不可移動;

2)同構(gòu)節(jié)點(diǎn)被認(rèn)為具有相同的傳感、處理、存儲、通信能力和初始能量;

3)基站在能量、處理、通信能力等方面沒有限制，可以與網(wǎng)絡(luò)中的所有節(jié)點(diǎn)進(jìn)行通信;

4)任意兩個節(jié)點(diǎn)之間的無線傳輸鏈路是完全對稱的，因此，對于兩個節(jié)點(diǎn)之間相同數(shù)量的數(shù)據(jù)傳輸能耗是相同的;

5)任意兩個節(jié)點(diǎn)之間的距離可以通過接收到的信號強(qiáng)度來獲得。

1.2 能量模型

在LEACH算法中，采用與文獻(xiàn)[10]相同的能量模型，即一階無線電模型。具體計(jì)算為

(1)

式中：Eelec——發(fā)送或接收數(shù)據(jù)所消耗的能量;

εfs、εmp——分別表示處于自由空間模型和多徑衰落信道模型時的功率放大所需要的能量系數(shù)；

當(dāng)發(fā)送距離d小于距離閾值d0時，采用自由空間模型，反之，則采用多徑衰落信道[11]。

2 算法設(shè)計(jì)

2.1 混沌粒子群算法

基本粒子群算法是一種模擬自然界中鳥群覓食行為的隨機(jī)優(yōu)化算法，每個粒子都可以看作是一個解[12]。每個粒子的適應(yīng)度值是由給出的適應(yīng)度函數(shù)計(jì)算而來，從而得知每個粒子的個體極值和全局極值。粒子會根據(jù)個體極值和全局極值不斷更新粒子的速度和位置，如下式

混沌是一種具有內(nèi)在規(guī)律性的非線性隨機(jī)運(yùn)動形式，具有對初始條件極端敏感性、遍歷性和類隨機(jī)性的特點(diǎn)[13]，在較長時間內(nèi)混沌可以不重復(fù)地遍歷相空間中的各個點(diǎn)[14]，因此在粒子群算法中引用混沌思想有助于算法保持群體的多樣性，擴(kuò)大種群搜索范圍，跳出局部最優(yōu)。經(jīng)過驗(yàn)證，Tent映射比Logistic更能產(chǎn)生分布較均勻的初始值，具有更好的均勻遍歷性[15]，文中采用Tent映射的方式產(chǎn)生混沌序列，

(3)

其中，xn∈[0,1],n=1,2,3,…。

2.2 基于混沌粒子群的LEACH算法

CPSOLEACH算法通過改進(jìn)的粒子迭代公式，尋找能量較多且與基站距離較近的節(jié)點(diǎn)作為簇頭，具體流程如下：

1)初始化相關(guān)參數(shù)，包括粒子群算法中的個體學(xué)習(xí)因子值c1、群體學(xué)習(xí)因子值c2、慣性權(quán)值w、粒子群種群規(guī)模n、粒子維數(shù)d(也就是網(wǎng)絡(luò)中節(jié)點(diǎn)的個數(shù))、最大迭代次數(shù)Tmax、粒子飛行速度的上限vmax和下限vmin。

2)預(yù)分簇階段，初始化粒子群，即隨機(jī)生成N×D的01矩陣，其中1為簇頭，0為普通節(jié)點(diǎn)，確定最優(yōu)簇頭數(shù)為K[14]，

(4)

式中：N——網(wǎng)絡(luò)中存活的節(jié)點(diǎn)個數(shù)；

D——網(wǎng)絡(luò)區(qū)域的長度；

l——簇頭節(jié)點(diǎn)到基站之間的距離[14]。

3)計(jì)算簇頭的適應(yīng)度函數(shù)值fitnessi，適應(yīng)度公式為

(5)

式中：f1——能量評價因子，表示簇頭的剩余能量與網(wǎng)絡(luò)中所有節(jié)點(diǎn)的剩余能量總和之比；

qk——第k個競選簇頭的剩余能量；

qi——網(wǎng)絡(luò)中第i個節(jié)點(diǎn)的剩余能量；

f2——距離評價因子，表示網(wǎng)絡(luò)中所有節(jié)點(diǎn)與基站的距離之和與此時當(dāng)選的簇頭與基站的距離之比；

li——網(wǎng)絡(luò)中第i個節(jié)點(diǎn)與基站之間的距離；

lk——第k個簇頭與基站之間的距離；

α、β——均為影響因子,滿足α+β=1。

從式(5)可以看出，網(wǎng)絡(luò)中的節(jié)點(diǎn)擁有剩余能量越多，并且與基站之間的距離越近，適應(yīng)度值越大，其當(dāng)選為簇頭節(jié)點(diǎn)的概率越高。

4)根據(jù)文中新適應(yīng)度函數(shù)公式更新個體極值pbest和全局極值gbest，并根據(jù)式(2)更新粒子的位置和速度，根據(jù)式(3)對粒子序列進(jìn)行混沌優(yōu)化。

5)迭代次數(shù)加1，回到3)，直至達(dá)到最大迭代次數(shù)，輸出全局極值，最優(yōu)粒子極值即最優(yōu)簇頭。

3 仿真分析

采用Matlab仿真平臺，模擬網(wǎng)絡(luò)區(qū)域?yàn)?00 m×100 m的正方形區(qū)域，基站位于區(qū)域中心(50，50)，隨機(jī)部署網(wǎng)絡(luò)節(jié)點(diǎn)，其分布模型如圖1所示。

圖1 網(wǎng)絡(luò)節(jié)點(diǎn)部署示意圖

為了驗(yàn)證CPSOLEACH算法的有效性，從能量消耗總和、存活節(jié)點(diǎn)數(shù)和網(wǎng)絡(luò)剩余能量3個方面對LEACH、LEACH-E和CPSOLEACH算法進(jìn)行對比分析，分別如圖2和圖3所示。

圖2 能量消耗總和對比

圖3 存活節(jié)點(diǎn)數(shù)目對比

由圖2可見，LEACH算法和LEACH-E算法分別在第1 253輪和1 467輪時能量就已經(jīng)全部消耗完畢，而CPSOLEACH算法在第1 781輪時能量才全部消耗完畢。

由圖3可見，LEACH、LEACH-E算法在第1 253輪和1 466輪時區(qū)域內(nèi)的節(jié)點(diǎn)就已經(jīng)全部死亡，而CPSOLEACH算法是在第1 781輪時區(qū)域內(nèi)的節(jié)點(diǎn)才全部死亡。

網(wǎng)絡(luò)剩余能量對比如圖4所示。

圖4顯示了3種算法在能量均衡方面的性能，CPSOLEACH算法中的網(wǎng)絡(luò)剩余能量一直都比LEACH和LEACH-E高。

從上述幾個方面可知，CPSOLEACH算法能夠有效節(jié)省能量，延長網(wǎng)絡(luò)生命周期，這是因?yàn)镃PSOLEACH算法采用混沌粒子群算法優(yōu)化了簇頭選擇，均衡了網(wǎng)絡(luò)能量。

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

4 結(jié) 語

在傳統(tǒng)LEACH和粒子群算法的基礎(chǔ)上，提出CPSOLEACH算法。結(jié)合LEACH算法給出含有節(jié)點(diǎn)能量因素和與基站距離因素的適應(yīng)度函數(shù)，并運(yùn)用新的適應(yīng)度函數(shù)進(jìn)行迭代選取最優(yōu)簇頭，即剩余能量多和與基站距離較近的節(jié)點(diǎn)當(dāng)選簇頭。同時，在搜索簇頭的過程中，采用Tent混沌映射優(yōu)化粒子群算法，擴(kuò)大了簇頭的搜索范圍，也避免了粒子群算法后期陷入局部最優(yōu)。通過Matlab仿真分析，證明了CPSOLEACH算法可以降低節(jié)點(diǎn)和網(wǎng)絡(luò)能量消耗，延長網(wǎng)絡(luò)生命周期。