基于CS算法的LEACH極值雙簇首分簇方法

吳 慧, 張 品

(杭州電子科技大學(xué) 通信工程學(xué)院,浙江 杭州 310018)

0 引 言

無(wú)線傳感器網(wǎng)絡(luò)(wireless sensor networks,WSNs)中傳感器節(jié)點(diǎn)在數(shù)據(jù)傳輸過程中存在能量有限的問題,設(shè)計(jì)出一種降低傳感器能量消耗的路由算法至關(guān)重要[1,2]。

LEACH協(xié)議是WSNs中典型的分簇協(xié)議[3],以“輪”為周期進(jìn)行數(shù)據(jù)傳輸,每“輪”分為兩個(gè)階段,第一個(gè)階段是成簇過程,每個(gè)節(jié)點(diǎn)產(chǎn)生一個(gè)0～1之間的隨機(jī)數(shù),并與預(yù)先定義好的閾值T(n)進(jìn)行比較,若產(chǎn)生的隨機(jī)數(shù)小于T(n),成為簇首,否則成為普通節(jié)點(diǎn)。簇首廣播成簇消息(包括自身的ID和建簇信息),普通節(jié)點(diǎn)根據(jù)接收信號(hào)強(qiáng)度(received signal strength indication,RSSI)加入合適的簇中,感知、收集和預(yù)處理監(jiān)測(cè)信息并與簇首直接通信；簇首需要對(duì)簇內(nèi)的節(jié)點(diǎn)分配數(shù)據(jù)傳輸時(shí)的時(shí)隙并融合發(fā)送來(lái)的數(shù)據(jù),等到全部節(jié)點(diǎn)都加入到某一個(gè)簇中,第一階段結(jié)束。閾值T(n)定義：當(dāng)n∈Gr時(shí),T(n)=p/{1-p[r×mod(1/p)]};當(dāng)n?Gr時(shí),T(n)=0。其中,p為全網(wǎng)中的簇首數(shù)與全部節(jié)點(diǎn)的比值,r為當(dāng)前經(jīng)歷的輪數(shù),Gr為前r-1輪未被選為簇首的節(jié)點(diǎn)集合。第二階段是數(shù)據(jù)傳輸階段,普通節(jié)點(diǎn)在規(guī)定的時(shí)間內(nèi)將收集到的數(shù)據(jù)直接傳輸給簇首,不在規(guī)定傳輸時(shí)間內(nèi)則進(jìn)入休眠狀態(tài),簇首等收集完全部數(shù)據(jù)后再將數(shù)據(jù)傳送給基站[4,5]。雖LEACH算法以循環(huán)方式選舉簇首平衡了網(wǎng)絡(luò)負(fù)載,但未考慮節(jié)點(diǎn)自身的任何因素使得簇首選舉不合理,單跳通信使得距離較遠(yuǎn)的節(jié)點(diǎn)需要消耗大量的能量甚至出現(xiàn)數(shù)據(jù)無(wú)法到達(dá)的情況。

目前針對(duì)WSNs中節(jié)點(diǎn)的數(shù)據(jù)傳輸方式,先后提出了許多改進(jìn)算法,文獻(xiàn)[6]中不再采用隨機(jī)方式選舉簇首,而是加入了當(dāng)前節(jié)點(diǎn)的剩余能量來(lái)豐富簇首選舉公式,使得產(chǎn)生的簇首更加準(zhǔn)確,但仍不夠完善；文獻(xiàn)[7]構(gòu)造了基于最小生成樹的數(shù)據(jù)傳輸路由,雖然可以有效均衡能量消耗,但需要對(duì)網(wǎng)絡(luò)進(jìn)行消息遍歷,對(duì)能量有過高要求；文獻(xiàn)[8]利用粒子群算法優(yōu)化簇間路由,根據(jù)每個(gè)節(jié)點(diǎn)發(fā)送能耗和接收能耗來(lái)選擇中繼節(jié)點(diǎn),減少了能量消耗,但粒子群算法搜索速度較慢,且容易陷入局部最優(yōu)解；文獻(xiàn)[9]改善了原有LEACH協(xié)議的分簇方式,均勻各個(gè)簇內(nèi)節(jié)點(diǎn)的個(gè)數(shù),設(shè)置簇內(nèi)節(jié)點(diǎn)閾值數(shù),防止簇的不規(guī)則導(dǎo)致節(jié)點(diǎn)能耗不均,出現(xiàn)能量空洞,但會(huì)在建簇過程中花費(fèi)較長(zhǎng)時(shí)間,且簇首在管理控制上消耗不必要的能量；文獻(xiàn)[10]將節(jié)點(diǎn)能量因素引入簇首選舉公式中,數(shù)據(jù)傳輸采用簇間多跳方式,當(dāng)前簇首選擇距離自己最近的簇首作為下一跳轉(zhuǎn)發(fā)節(jié)點(diǎn),但每輪每個(gè)節(jié)點(diǎn)會(huì)形成單一固定路由而出現(xiàn)節(jié)點(diǎn)能耗不均。

本文考慮到上述算法的缺點(diǎn),提出一種基于布谷鳥搜索(cuckoo search,CS)的改進(jìn)LEACH算法。首先采用LEACH算法來(lái)選擇簇首,引入了節(jié)點(diǎn)到基站之間的距離,節(jié)點(diǎn)當(dāng)前的剩余能量?jī)蓚€(gè)參考因素,并在節(jié)點(diǎn)入簇后選出兩個(gè)極值簇,實(shí)施雙簇首機(jī)制,根據(jù)不同的耗能情況建立不同的副簇首選舉標(biāo)準(zhǔn),最后簇首通過高效的布谷鳥搜索算法來(lái)優(yōu)化到基站的數(shù)據(jù)傳輸路由。

1 能量模型

傳感器節(jié)點(diǎn)發(fā)送數(shù)據(jù)耗能[11～14]公式如下

(1)

接收數(shù)據(jù)消耗的能量

ER(M,d)=M×Eelec

(2)

簇首融合數(shù)據(jù)時(shí)消耗的能量

Emix=C×M×EDA

(3)

式中EDA為融合系數(shù),C為簇內(nèi)全部的節(jié)點(diǎn)個(gè)數(shù)。

2 基于CS算法的改進(jìn)LEACH算法

2.1 簇首選舉

為避免因原始LEACH簇首隨機(jī)選舉公式帶來(lái)的簇首分布不均勻,現(xiàn)引入節(jié)點(diǎn)剩余能量因素和距離因素,有

(4)

式中Ei為節(jié)點(diǎn)i當(dāng)前的剩余能量,E0為節(jié)點(diǎn)的初始能量,dmax為所有節(jié)點(diǎn)中到基站最遠(yuǎn)的距離,dmin為所有節(jié)點(diǎn)中到基站最近的距離,di,BS為節(jié)點(diǎn)i到基站的距離。

2.2 極值雙簇首機(jī)制

為避免造成單一簇首的能量過載,簇中引入極值雙簇首機(jī)制。但為保證簇首數(shù)目的最佳性,不是每個(gè)簇都需要選舉副簇首來(lái)分擔(dān)主簇首的部分功能,僅對(duì)于簇內(nèi)節(jié)點(diǎn)數(shù)最多的簇(文中以Area1表示)以及其簇內(nèi)的簇首離基站最遠(yuǎn)的簇(文中以Area2表示)引入該機(jī)制。主簇首的選舉通過式(4)的閾值公式實(shí)現(xiàn),而副簇首的選擇由不同函數(shù)來(lái)實(shí)現(xiàn)。由于兩個(gè)簇的主簇首耗能方式的差異,使得副簇首的選擇考慮的因素也不同,為Area1定義副簇首選舉的能量函數(shù)

(5)

同時(shí)，為Area2定義副簇首的距離函數(shù)

fi=1/di,BS

(6)

其中，fi越大,選為副簇首的概率越高,副簇首也會(huì)參與后續(xù)數(shù)據(jù)的轉(zhuǎn)發(fā)。

2.3 簇間多跳路由

原有的單跳傳輸使得距離較遠(yuǎn)的簇首在傳輸數(shù)據(jù)時(shí)發(fā)生數(shù)據(jù)失真,甚至低于接收的閾值功率而無(wú)法恢復(fù)數(shù)據(jù)的完整性,多跳通信方式可以很好地解決此問題。根據(jù)CS算法選擇數(shù)據(jù)傳輸?shù)南乱粋€(gè)簇首節(jié)點(diǎn)。

CS算法是在2009年時(shí)英國(guó)劍橋大學(xué)學(xué)者Yang X S教授和Deb S提出的一種智能優(yōu)化算法,其思想最初來(lái)源于大自然中布谷鳥尋找鳥窩的行為,常用來(lái)求解最優(yōu)解的問題[15,16]。為模擬CS算法,理想化規(guī)定[17,18]：

1)每個(gè)布谷鳥一次只產(chǎn)一個(gè)蛋,并且隨機(jī)選擇鳥窩來(lái)放置鳥蛋；2)隨機(jī)選擇的一組鳥窩中,將最好的鳥窩保留到下一代；3)鳥巢數(shù)量一定,鳥巢的主人發(fā)現(xiàn)陌生鳥蛋的概率為,一旦鳥蛋被主人發(fā)現(xiàn),丟棄鳥蛋或摧毀鳥巢。

(7)

(8)

(9)

μ～N(0,1)

(10)

v～N(0,1)

(11)

(12)

每次的飛行之后,在更新的鳥巢位置上若無(wú)法找到真實(shí)環(huán)境部署的傳感器節(jié)點(diǎn),則按照“就近原則”映射到最近的節(jié)點(diǎn),gbest對(duì)應(yīng)的映射節(jié)點(diǎn)是被選擇的轉(zhuǎn)發(fā)簇首,每個(gè)鳥巢的滿意函數(shù)F與鳥巢的好壞成正比,鳥巢的滿意函數(shù)在傳感器網(wǎng)絡(luò)中類似于節(jié)點(diǎn)性能函數(shù),從選擇最佳轉(zhuǎn)發(fā)節(jié)點(diǎn)的角度出發(fā)性能函數(shù)由兩個(gè)因素綜合考慮,其中之一涉及到節(jié)點(diǎn)的剩余能量,剩余能量越多,說(shuō)明節(jié)點(diǎn)存活時(shí)間還長(zhǎng),有足夠能力轉(zhuǎn)發(fā)數(shù)據(jù),另一個(gè)則考慮到節(jié)點(diǎn)的距離,如圖1,d1與d2的和越趨于d3,節(jié)點(diǎn)消耗的能量越少,適合作為轉(zhuǎn)發(fā)節(jié)點(diǎn)[14],其表達(dá)式為

圖1 距離關(guān)系

(13)

式中Ei為節(jié)點(diǎn)i當(dāng)前的剩余能量,allowk為候選簇首節(jié)點(diǎn)的集合,di,BS為候選節(jié)點(diǎn)i與基站之間的距離,dcurrent,i為當(dāng)前簇首與候選簇首i之間的距離。

式(5)表明節(jié)點(diǎn)剩余能量越多,距離當(dāng)前節(jié)點(diǎn)越近,距離基站越近,選為中繼節(jié)點(diǎn)的概率越大。

2.4 改進(jìn)算法設(shè)計(jì)

算法流程圖如圖2所示,算法過程只考慮到每輪均有數(shù)據(jù)傳輸?shù)那闆r。

圖2 算法流程圖

3 算法仿真與結(jié)果分析

使用MATLAB軟件進(jìn)行實(shí)驗(yàn)仿真,假設(shè)傳感網(wǎng)絡(luò)區(qū)域是一個(gè)200 m×200 m的正方形,隨機(jī)部署100個(gè)節(jié)點(diǎn),用○表示,基站位置固定,坐標(biāo)為(100,160)m,用*表示,具體分布如圖3所示。

圖3 節(jié)點(diǎn)分布

實(shí)驗(yàn)參數(shù)設(shè)置如下：節(jié)點(diǎn)初始能量E0為0.5 J,發(fā)送電路和接收電路消耗的能量Eelec為50 nJ/bit,多徑衰落模型放大倍數(shù)εmp為0.001 3 pJ/(bit·m4),自由空間模型放大系數(shù)εfs為100 pJ/(bit·m2),數(shù)據(jù)融合系數(shù)EDA為5 nJ/bit,最大輪數(shù)rmax為1 500,每個(gè)傳感器節(jié)點(diǎn)發(fā)送的控制數(shù)據(jù)大小m為200 bit,每個(gè)傳感器節(jié)點(diǎn)發(fā)送的數(shù)據(jù)大小M為4 000 bit,步長(zhǎng)控制量α為0.001,β為1.5。

為了驗(yàn)證算法的有效性,本文從網(wǎng)絡(luò)中節(jié)點(diǎn)死亡個(gè)數(shù)、網(wǎng)絡(luò)剩余能量和節(jié)點(diǎn)存活率三個(gè)方面進(jìn)行算法性能的評(píng)價(jià),對(duì)本文中的仿真數(shù)據(jù)進(jìn)行了50次實(shí)驗(yàn)求平均得到數(shù)據(jù)及仿真結(jié)果如圖4所示。

圖4(a)是LEACH協(xié)議,文獻(xiàn)[10]提出的算法和本文算法的網(wǎng)絡(luò)死亡節(jié)點(diǎn)數(shù)與輪數(shù)的關(guān)系圖,網(wǎng)絡(luò)節(jié)點(diǎn)的死亡數(shù)的多少能夠直觀的判斷該網(wǎng)絡(luò)工作的時(shí)間,隨著輪數(shù)的增加,每個(gè)節(jié)點(diǎn)不斷耗盡自身能量直到死亡。從圖中可以看出在本文算法中,第一個(gè)節(jié)點(diǎn)在869輪出現(xiàn)死亡,相比于LEACH算法和文獻(xiàn)[10]算法延長(zhǎng)了近1倍的輪數(shù)。出現(xiàn)上述情況一方面是副簇首分擔(dān)了部分主簇首的任務(wù),使得降低了主簇首的能耗速度,另一方面是候選簇首均有相同的機(jī)會(huì)競(jìng)爭(zhēng)簇間路由中的轉(zhuǎn)發(fā)節(jié)點(diǎn),避免了“能量空洞”現(xiàn)象,一定程度上提升了網(wǎng)絡(luò)質(zhì)量。

圖4(b)為L(zhǎng)EACH協(xié)議,文獻(xiàn)[10]算法和本文算法的網(wǎng)絡(luò)剩余能量與輪數(shù)的關(guān)系圖,隨著輪數(shù)的增加,網(wǎng)絡(luò)中剩余能量越少。本算法的生命周期為1364輪,較LEACH算法和文獻(xiàn)[10]算法分別提高了48.26 %和21.89 %,更好的節(jié)約了能量消耗,延長(zhǎng)了網(wǎng)絡(luò)的實(shí)際可用時(shí)間。

圖4(c)為三種算法下不同節(jié)點(diǎn)存活率下的輪數(shù)(時(shí)間)折線圖,在每個(gè)節(jié)點(diǎn)存活率下,本文算法的節(jié)點(diǎn)存活數(shù)都比其他兩種算法要多,且仍舊保持變化的平緩,均衡能耗,保持網(wǎng)絡(luò)的穩(wěn)定性。

圖4 仿真實(shí)驗(yàn)結(jié)果

4 結(jié) 論

本文提出了基于CS算法的LEACH協(xié)議的極值雙簇首分簇算法,考慮能量因素和距離因素選擇簇首,確保簇首的最佳性,并在節(jié)點(diǎn)數(shù)最多以及簇首距離基站最遠(yuǎn)的兩個(gè)極值簇內(nèi)根據(jù)不同的耗能原因建立副簇首的選舉標(biāo)準(zhǔn),并參與后續(xù)數(shù)據(jù)的轉(zhuǎn)發(fā),引入收斂速度快,搜索效率高的CS算法建立起當(dāng)前節(jié)點(diǎn)到基站之間的傳輸路徑。通過仿真實(shí)驗(yàn)比較不同算法,證明了本算法能達(dá)到很好的節(jié)能效果,均衡簇間負(fù)載,改善了無(wú)線傳感網(wǎng)絡(luò)一直以來(lái)的能量瓶頸問題。