一種高效節(jié)能的無線傳感器網(wǎng)絡(luò)分簇路由算法

施志剛， 李桂娟， 李 亮， 張持健

(安徽師范大學(xué) 物理與電子信息學(xué)院，安徽 蕪湖 241000)

0 引 言

無線傳感器網(wǎng)絡(luò)(wireless sensor networks,WSNs)在智能交通、環(huán)境監(jiān)測、工業(yè)控制等領(lǐng)域有著相當(dāng)?shù)陌l(fā)展優(yōu)勢，但電池更換困難，因此設(shè)計一種高效節(jié)能的路由算法，最大限度地延長網(wǎng)絡(luò)生存周期尤為重要。Heinzelman W等人[1]在2000年提出了分簇路由算法的典型代表LEACH算法。近年來,在LEACH算法基礎(chǔ)上相繼提出了多種改進方法，pLEACH算法[2]中提出將網(wǎng)絡(luò)分區(qū)，然后在各個子區(qū)域中選出剩余能量最高的節(jié)點作為簇頭；覃海生等人[3]在細(xì)胞膜優(yōu)化算法的基礎(chǔ)上通過濃度、能量和距離三因子完成對節(jié)點的分簇；羅琴等人[4]運用模糊理論計算節(jié)點擔(dān)任簇頭的概率來改進閾值公式；嚴(yán)斌亨等人[5]通過節(jié)點的剩余能量和連通度來優(yōu)化簇頭選舉。上述算法在一定程度上降低了網(wǎng)絡(luò)能耗，但簇頭分布的隨機性沒有得到很好解決,且未從全局和局部兩個方面來考慮簇內(nèi)、簇頭間的能耗問題。

本文給出了一種高效節(jié)能的WSNs分簇路由算法(efficient and energy-saving clustering routing algorithm for WSNs，ECRAW)，其特點在于：結(jié)合最優(yōu)簇頭數(shù)運用遺傳算法(genetic algorithm,GA)和引力對簇的形成進行改進；簇頭選舉時考慮節(jié)點的剩余能量、節(jié)點與基站以及節(jié)點與簇中心之間的距離；引入通信代價函數(shù)建立簇頭與基站的多跳通信。

1 經(jīng)典LEACH算法不足

雖然相比于傳統(tǒng)的平面路由算法,LEACH算法將網(wǎng)絡(luò)生存周期提高了15 %[6]，但仍存在一些問題：1)簇頭選舉的隨機性導(dǎo)致簇頭分布不均勻；2)簇頭的選舉未考慮節(jié)點的剩余能量，低能量的節(jié)點擔(dān)任簇頭會導(dǎo)致簇頭過早死亡，影響數(shù)據(jù)的傳輸，出現(xiàn)監(jiān)測盲區(qū)現(xiàn)象；3)數(shù)據(jù)傳輸采用單跳的方式，遠(yuǎn)距離傳輸消耗大量的能量，不適用于大規(guī)模的無線傳感網(wǎng)絡(luò)。

2 ECRAW算法

本文從分簇方式、簇頭的選舉和路由方式3個方面對LEACH算法加以改進，與LEACH算法類似，每一輪也分為簇的建立和穩(wěn)定傳輸，不同的是ECRAW算法在簇的建立階段先進行簇的劃分，再執(zhí)行簇頭選舉。

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

本文采用文獻[7]的最優(yōu)簇頭數(shù)K計算方法為

(1)

2.2 GA和引力改進簇的形成

本文采用GA優(yōu)化初始聚類中心，以避免聚類效果受初始聚類中心的干擾，陷入局部最優(yōu)。優(yōu)化步驟如下：

1)編碼方式:隨機選取K個節(jié)點組成1個個體，染色體采用節(jié)點下標(biāo)進行編碼，即1,2,…,K；

2)初始化種群，按上述編碼方式，重復(fù)H次得到種群；

3)構(gòu)造適應(yīng)度函數(shù)(式(2))；

4)經(jīng)過選擇、交叉和變異操作得到新的種群；

5)重復(fù)步驟(4)，達到最大的迭代次數(shù)，并輸出種群中適應(yīng)度最大的個體即優(yōu)化之后的初始聚類中心。

在簇的形成過程中引入引力思想，傳感節(jié)點看成是有質(zhì)量無體積的質(zhì)點，引力大小和簇內(nèi)節(jié)點個數(shù)(質(zhì)點質(zhì)量)正比，與質(zhì)點之間的距離成反比。由于只需比較兩個引力相對大小，每次待分簇的質(zhì)點在參與引力運算時，其個數(shù)一直是1，即可省略一個m，同時G可以忽略不計。為了避免簇內(nèi)節(jié)點數(shù)過多，所造成引力過大帶來“黑洞”問題以及簇頭負(fù)載過重加快死亡現(xiàn)象，改進后的引力公式為

(2)

根據(jù)式(2)知，待分簇節(jié)點與簇中心的距離越小，簇內(nèi)節(jié)點越多，引力就越大,該節(jié)點加入該簇的機會就越大。簇的形成過程如下：

1)設(shè)置GA運行參數(shù)，執(zhí)行GA算法，適應(yīng)度最大的個體即初始聚類中心；

2)基站逐一計算網(wǎng)絡(luò)節(jié)點與K個初始聚類中心間引力大小，并加入引力較大的簇，開始成簇，并更新簇中心；

3)基站逐一計算剩余網(wǎng)絡(luò)節(jié)點與更新后的聚類中心之間的引力大小，并更新簇中心；

4)重復(fù)步驟(3)，直到所有節(jié)點均入簇，分簇完成。

2.3 簇頭選舉

分簇完成之后，在簇內(nèi)進行簇頭的選舉，結(jié)合最優(yōu)簇頭比例在LEACH算法基礎(chǔ)上，考慮節(jié)點的剰余能量、節(jié)點到基站以及節(jié)點到簇中心的距離，得到新的閾值為

(3)

(4)

每輪中節(jié)點通過rand(1,1)隨機產(chǎn)生1個數(shù)，若小于式(3)，節(jié)點當(dāng)選為該簇的簇頭，重復(fù)上述過程，在每個簇中選出簇頭。改進后的閾值計算公式使剩余能量較多、距離基站和距離簇中心較近的節(jié)點有更多的機會當(dāng)選為簇頭，在一定程度上使簇頭分布均勻，均衡網(wǎng)絡(luò)能耗。

2.4 穩(wěn)定傳輸

ECRAW算法整體流程如圖1。

圖1 ECRAW算法工作流程

3 算法仿真及對比分析

3.1 實驗網(wǎng)絡(luò)參數(shù)

為了驗證ECRAW算法的性能，采用一階無線通信能耗模型[8]，本文通過MATLAB 2014a平臺將其與LEACH,LEACH-EC算法[5]在死亡節(jié)點數(shù)、剩余能量和消耗能量3個方面進行了仿真比較。設(shè)有100個初始能量為1J的節(jié)點隨機部署在100 m×100 m的區(qū)域中，基站位于(50 m,50 m)處，實驗的相關(guān)網(wǎng)絡(luò)參數(shù)如下：數(shù)據(jù)包長度4 000 bits，εfs為10 pJ/bit/m2，εamp為0.001 3 pJ/bit/m4，數(shù)據(jù)融合能耗EDA為5 nJ/bit，收發(fā)電路能耗Eelec為50 nJ/bit。

3.2 仿真結(jié)果

評價網(wǎng)絡(luò)的生存周期通常看第1個節(jié)點死亡時間(first node dead-time,FND)和1/2節(jié)點死亡時間(half node dead-time,HND)。圖2中相比于LEACH和LEACH-EC算法本文算法從FND到最后一個節(jié)點死亡時間均滯后，延長了網(wǎng)絡(luò)的生存周期。本文算法FND出現(xiàn)在第2 375輪，較LEACH提高了1.64倍，較LEACH-EC延長了58.4 %；HND出現(xiàn)在2 521輪，較LEACH提高1.09倍，較LEACH-EC延長23.3 %；另外圖中本文算法的曲線陡峭，說明節(jié)點能量消耗均衡性較好，可見，本文算法具有明顯的優(yōu)勢，主要原因是改進了簇的形成和簇頭的選舉，使簇頭分布更均勻，簇頭與基站通信的機制的改進降低了網(wǎng)絡(luò)能耗。

圖2 網(wǎng)絡(luò)生存周期對比

隨著網(wǎng)絡(luò)的運行，圖3說明了網(wǎng)絡(luò)能量在不斷消耗，相比之下，在相同的時間內(nèi)，運用本文算法消耗的總能量少于其他2種算法；相同的初始能量下，總能量耗盡較晚。圖4中本文算法的剩余能量高于其他2種算法，表明了在相同的初始能量下，改進后的算法較LEACH 和 LEACH-EC 能耗較小，有效地節(jié)約能量，另外，ECRAW算法傾斜度較為平緩，說明網(wǎng)絡(luò)性能較為穩(wěn)定。

圖3 消耗總能量對比

圖4 剩余總能量對比

4 結(jié)束語

本文在LEACH算法的基礎(chǔ)上提出了一種ECRAW算法，仿真結(jié)果表明，該算法在存活節(jié)點個數(shù)、消耗總能量和剩余總能量方面均優(yōu)于 LEACH 和LEACH-EC算法，有效降低網(wǎng)絡(luò)能耗，均衡了節(jié)點能量消耗，延長了網(wǎng)絡(luò)生存周期。