吳 慧, 張 品

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

0 引 言

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

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

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

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

1 能量模型

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

(1)

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

ER(M,d)=M×Eelec

(2)

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

Emix=C×M×EDA

(3)

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

2 基于CS算法的改進LEACH算法

2.1 簇首選舉

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

(4)

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

2.2 極值雙簇首機制

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

(5)

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

fi=1/di,BS

(6)

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

2.3 簇間多跳路由

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

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

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

(7)

(8)

(9)

μ～N(0,1)

(10)

v～N(0,1)

(11)

(12)

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

圖1 距離關(guān)系

(13)

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

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

2.4 改進算法設(shè)計

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

圖2 算法流程圖

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

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

圖3 節(jié)點分布

實驗參數(shù)設(shè)置如下：節(jié)點初始能量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,每個傳感器節(jié)點發(fā)送的控制數(shù)據(jù)大小m為200 bit,每個傳感器節(jié)點發(fā)送的數(shù)據(jù)大小M為4 000 bit,步長控制量α為0.001,β為1.5。

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

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

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

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

圖4 仿真實驗結(jié)果

4 結(jié) 論

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