基于能量區(qū)域代理機(jī)制的移動(dòng)Sink路由算法

基于能量區(qū)域代理機(jī)制的移動(dòng)Sink路由算法

張建軍，萬磊，翟琰，魏振春

(合肥工業(yè)大學(xué) 計(jì)算機(jī)與信息學(xué)院，安徽 合肥230009)

摘要:文章提出基于能量區(qū)域代理機(jī)制的移動(dòng)Sink路由算法。該算法使用剩余能量掃描算法將系統(tǒng)劃分為若干個(gè)能量相近的區(qū)域,再在每個(gè)能量區(qū)域內(nèi)構(gòu)建路由信息,根據(jù)已構(gòu)建的路由信息選擇代理節(jié)點(diǎn)作為能量區(qū)域內(nèi)信息存儲(chǔ)和與Sink通信的節(jié)點(diǎn),根據(jù)代理節(jié)點(diǎn)的分布制定Sink最小移動(dòng)路徑策略。仿真實(shí)驗(yàn)表明,在網(wǎng)絡(luò)中使用該算法可以使網(wǎng)絡(luò)能量得到更均衡合理充分的利用,可以很好地延長網(wǎng)絡(luò)壽命。

關(guān)鍵詞:無線傳感器網(wǎng)絡(luò);移動(dòng)Sink;剩余能量掃描算法;代理節(jié)點(diǎn);最小移動(dòng)路徑策略

收稿日期：2014-01-20；修回日期：2014-03-17

基金項(xiàng)目：國家自然科學(xué)基金面上資助項(xiàng)目(61370088);國家國際科技合作專項(xiàng)資助項(xiàng)目(2014DFB10060);安徽省自然科學(xué)基金資助項(xiàng)目(1208085QF113);安徽省國際科技合作計(jì)劃資助項(xiàng)目(1303063009)和安徽省高等學(xué)校省級自然科學(xué)研究資助項(xiàng)目(KJ2011ZD01;KJ2012A224;KJ2012A233)

作者簡介：張建軍(1963-),男,安徽合肥人,博士，合肥工業(yè)大學(xué)教授,碩士生導(dǎo)師.

doi:10.3969/j.issn.1003-5060.2015.01.008

中圖分類號:TP393文獻(xiàn)標(biāo)識(shí)碼：A

MobileSinkroutingalgorithmbasedon

proxymechanismofenergyarea

ZHANGJian-jun,WANLei,ZHAIYan，WEIZhen-chun

(SchoolofComputerandInformation,HefeiUniversityofTechnology,Hefei230009,China)

Abstract:In this paper, the mobile Sink routing algorithm based on the proxy mechanism of energy area is put forward. The residual energy scanning algorithm is used to divide energy areas into several energy-relevant areas, then the routing information is built in each energy-relevant area, and the proxy node is chosen according to the built routing information so as to store the information from the energy area and transmit information to the Sink node. Mobile Sink can formulate the minimum traverse strategy according to the position of the proxy node. The results of simulation experiments show that the energy in the network can be made full and balanced use of in this algorithm, and the network lifetime be prolonged as well.

Keywords:wirelesssensornetwork;mobileSink;residualenergyscanningalgorithm;proxynode;minimumtraversestrategy

無線傳感器網(wǎng)絡(luò) (WSNs) 是一種將信息采集、 信號傳輸、嵌入式結(jié)合于一體的新型信息獲取技術(shù),它是利用具有感知能力的傳感節(jié)點(diǎn)通過無線通信方式建立的一種無線網(wǎng)絡(luò)[1]。Sink是WSNs中一類特殊的節(jié)點(diǎn),它能收集節(jié)點(diǎn)產(chǎn)生的原始數(shù)據(jù)并進(jìn)行處理,然后將信息傳輸?shù)缴弦患墕挝?。而在傳統(tǒng)的WSNs中,Sink是靜態(tài)的[2],并且其他節(jié)點(diǎn)受到工作方式和環(huán)境的限制,可使用的能量有限,這使得距離Sink越近的節(jié)點(diǎn)能量消耗越快,導(dǎo)致整個(gè)網(wǎng)絡(luò)過早死亡。

為解決上述問題,人們提出一系列節(jié)能路由機(jī)制(如動(dòng)態(tài)分簇算法[3]與K均值分簇算法[4]等)試圖均衡節(jié)點(diǎn)間能量消耗,延長網(wǎng)絡(luò)生存時(shí)間。這些文獻(xiàn)所提方案能在一定程度上提高無線傳感器網(wǎng)絡(luò)的性能,緩解了“能量空洞”問題,但無法從根本上進(jìn)行解決。為此,近年來人們提出各種基于移動(dòng)Sink的路由算法,使得全網(wǎng)能量消耗盡可能在更多的節(jié)點(diǎn)之間均衡。如MECA(mobile-sinkbasedenergy-efficientclusteringalgorithm)[5]算法,使Sink圍繞傳感區(qū)域的邊緣以固定的路徑移動(dòng),區(qū)域內(nèi)部劃分為若干個(gè)簇進(jìn)行數(shù)據(jù)收集,但簇頭的選取和更新會(huì)帶來較大的維護(hù)開銷,且不能考慮全局能耗問題。為了能夠更好地實(shí)現(xiàn)全局能耗均衡,文獻(xiàn)[6]提出緩存節(jié)點(diǎn)輔助模式,它是單跳傳輸與多跳傳輸相結(jié)合的數(shù)據(jù)轉(zhuǎn)發(fā)模式。在緩存節(jié)點(diǎn)輔助下,信息或數(shù)據(jù)以多跳轉(zhuǎn)發(fā)方式傳輸?shù)骄彺婀?jié)點(diǎn)上,移動(dòng)Sink以單跳方式訪問緩存節(jié)點(diǎn),使得Sink的移動(dòng)對全網(wǎng)路由信息影響較小。如AVRP(Anchor-basedVoronoi-scopingroutingprotocol)[7]協(xié)議,隨著Sink的移動(dòng)動(dòng)態(tài)地在Sink鄰居節(jié)點(diǎn)中選擇剩余能量最大的傳感節(jié)點(diǎn)作為錨節(jié)點(diǎn)用作數(shù)據(jù)收集,可以靈活地維護(hù)局部的能耗均衡,但錨節(jié)點(diǎn)選取后需要在Voronoi內(nèi)范洪構(gòu)建路由信息,使得每一次錨節(jié)點(diǎn)的選取都進(jìn)行路由信息廣播,造成系統(tǒng)能耗和網(wǎng)絡(luò)通信負(fù)載較大。eScan算法[8]根據(jù)能量消耗模式具有空間局限的特性進(jìn)行能量區(qū)域的劃分,將全網(wǎng)劃分為若干個(gè)能量相近的區(qū)域,便于局部區(qū)域能耗問題的解決,進(jìn)而達(dá)到全網(wǎng)能耗的均衡。

本文在研究eScan算法的基礎(chǔ)上,將全網(wǎng)劃分為若干個(gè)能量相近區(qū)域,并結(jié)合緩存節(jié)點(diǎn)輔助模式[6],在能量區(qū)域內(nèi)選取代理節(jié)點(diǎn)用作該能量區(qū)域內(nèi)所有數(shù)據(jù)的存儲(chǔ)和上傳,同時(shí)Sink根據(jù)代理節(jié)點(diǎn)的分布情況設(shè)定移動(dòng)路徑進(jìn)行數(shù)據(jù)的收集,據(jù)此提出基于能量區(qū)域代理機(jī)制的移動(dòng)Sink路由算法。仿真結(jié)果表明其在能耗均衡及網(wǎng)絡(luò)壽命等指標(biāo)上有很大的改進(jìn),提高了網(wǎng)絡(luò)生命期。

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

網(wǎng)絡(luò)模型如圖1所示。

圖1　網(wǎng)絡(luò)模型

對該網(wǎng)絡(luò)模型做如下假設(shè)：

(1) 基于文獻(xiàn)[9]已設(shè)定的網(wǎng)絡(luò)模型,將網(wǎng)絡(luò)節(jié)點(diǎn)分為負(fù)責(zé)數(shù)據(jù)采集的節(jié)點(diǎn)(Source)、負(fù)責(zé)數(shù)據(jù)轉(zhuǎn)發(fā)的路由節(jié)點(diǎn)(Route)和負(fù)責(zé)數(shù)據(jù)收集的節(jié)點(diǎn)(Sink)3種類型。

(2)WSNs由若干個(gè)Source節(jié)點(diǎn)和若干個(gè)Route節(jié)點(diǎn)以及1個(gè)移動(dòng)Sink節(jié)點(diǎn)組成,且分布在N×N的區(qū)域內(nèi)。

(3) 每個(gè)節(jié)點(diǎn)有唯一的ID標(biāo)志,且每個(gè)節(jié)點(diǎn)有相同的通信半徑r,通信半徑內(nèi)的節(jié)點(diǎn)可以相互通信,交換信息,節(jié)點(diǎn)間通信可以為單跳或多跳模式。

(4)Source和Route具有相同的初始能量,且能量有限為E0,不能移動(dòng);Sink的能量不受限制,且以固定的速度可控移動(dòng)。

(5) 每個(gè)節(jié)點(diǎn)可以通過GPS[10]或其他算法獲知各自的位置信息。

為便于對算法進(jìn)行描述,做如下定義:

定義Source到Route的某一路徑選擇概率P(i)為:

(1)

其中,CountHop為Source到Route的某一路徑跳數(shù);E0為節(jié)點(diǎn)初始能量;En為Source到Route的某一路徑節(jié)點(diǎn)剩余能量之和;(E0CountHop-En)為當(dāng)前路徑已消耗能量總值;λ1、λ2為權(quán)值,用來調(diào)節(jié)跳數(shù)和路徑已消耗能量的重要度,且λ1+λ2=1。

定義代理節(jié)點(diǎn)間的加權(quán)權(quán)值E為:

(2)

2能量區(qū)域劃分

根據(jù)能量消耗具有空間局限性的特性,即相鄰區(qū)域能耗相似度較高,利用eScan算法[8]進(jìn)行能量區(qū)域的劃分,從而均衡局部能量的消耗,進(jìn)而達(dá)到全網(wǎng)的能耗均衡。

2.1　 eScan算法

利用(VALUE,COVERAGE)數(shù)組來表示能量區(qū)域,其中，VALUE=(min,max)分別表示能量區(qū)域內(nèi)節(jié)點(diǎn)的最小、最大的能量值,如A.VALUE=(35%,37%)；COVERAGE則表示VALUE所代表的能量區(qū)域的范圍。

當(dāng)節(jié)點(diǎn)接收到能量掃描命令后,開始對其通信范圍內(nèi)的節(jié)點(diǎn)進(jìn)行能量掃描,假設(shè)存在相鄰的節(jié)點(diǎn)A和B,對這2個(gè)節(jié)點(diǎn)按eScan算法進(jìn)行如下融合:

(1) 比較節(jié)點(diǎn)A和節(jié)點(diǎn)B的相似度，即

(3)

其中,T為剩余能量的最大相對誤差。

(2) 對節(jié)點(diǎn)A和節(jié)點(diǎn)B通信區(qū)域進(jìn)行比較,比較規(guī)則如下:

Distance{A.Cov,B.Cov}

(4)

其中,R為2個(gè)節(jié)點(diǎn)間的融合距離。如果2個(gè)節(jié)點(diǎn)滿足上述的2個(gè)規(guī)則,則可以將這兩者看成一個(gè)新的能量區(qū)域C,則C滿足：

C.min=min{A.min,B.min}

(5)

C.max=max{A.max,B.max}

(6)

C.Cov=Merge{A,B,R}

(7)

從起始的采集節(jié)點(diǎn)Source開始,依次和其通信范圍內(nèi)的節(jié)點(diǎn)進(jìn)行上述比較、融合,通過循環(huán)迭代,可以將整個(gè)網(wǎng)絡(luò)劃分成若干個(gè)能量相近的區(qū)域,且在每個(gè)能量區(qū)域內(nèi)存在若干個(gè)Source和Route節(jié)點(diǎn),如圖2所示。

圖2　某一能量區(qū)域模型

2.2　構(gòu)建能量區(qū)域內(nèi)路由信息

通過eScan算法可將全網(wǎng)劃分為若干個(gè)能量相近區(qū)域,在能量相近區(qū)域內(nèi)包括若干個(gè)Source和Route節(jié)點(diǎn),且Source節(jié)點(diǎn)周期性地發(fā)送路由數(shù)據(jù)包,在上述劃分的能量區(qū)域內(nèi)構(gòu)建路由信息,其中Route可存儲(chǔ)所有Source節(jié)點(diǎn)的信息,并依據(jù)Route中存儲(chǔ)的Source節(jié)點(diǎn)信息,選擇該能量區(qū)域內(nèi)代理節(jié)點(diǎn)用于該能量區(qū)域內(nèi)數(shù)據(jù)的收集和上傳,當(dāng)Sink移動(dòng)至該能量區(qū)域內(nèi)進(jìn)行信息收集時(shí),以該Route代理節(jié)點(diǎn)為信息收集節(jié)點(diǎn)。

采集節(jié)點(diǎn)Source周期性發(fā)送路由數(shù)據(jù)包,數(shù)據(jù)包如圖3a所示。其中，ID代表某個(gè)Source節(jié)點(diǎn)的編號；CountHop代表編號為ID的Source節(jié)點(diǎn)到當(dāng)前Route的跳數(shù)；En代表編號為ID的Source節(jié)點(diǎn)到當(dāng)前Route的路徑節(jié)點(diǎn)的剩余能量之和；SerivalNum代表某一能量區(qū)域標(biāo)志且相同能量區(qū)域的編號相同；PathNum是以位圖的方式存儲(chǔ)從Source到當(dāng)前Route的路徑節(jié)點(diǎn)信息。

Route中存儲(chǔ)路由信息的結(jié)構(gòu)如圖3b所示,其中，ET代表編號為ID的Source到Route的路徑節(jié)點(diǎn)剩余能量之和；P(ID)代表編號為ID的Source到Route的路徑選擇概率,其余項(xiàng)和圖3a中含義相同。

IDCountHopEnSerivalNumPathNum

( a)

(b)

圖3路由信息結(jié)構(gòu)

假設(shè)每一個(gè)Route都有足夠的存儲(chǔ)空間用于存儲(chǔ)能量區(qū)域內(nèi)的所有Source節(jié)點(diǎn)的信息。在Source節(jié)點(diǎn)發(fā)出更新路由數(shù)據(jù)包后,與通信范圍內(nèi)的所有節(jié)點(diǎn)Route通信,首先Route根據(jù)SerivalNum判斷該Source是否屬于當(dāng)前能量區(qū)域,若不屬于,則丟棄;否則,Route根據(jù)ID判斷是否已有該Source的信息,若無,則存儲(chǔ)當(dāng)前Source節(jié)點(diǎn)的信息,并按(8)式中方法更新路由數(shù)據(jù)包信息后在其通信范圍內(nèi)繼續(xù)轉(zhuǎn)發(fā)。

(8)

若Route中已有Source的相關(guān)信息,則通過(1)式計(jì)算P(i)值,并比較P(ID)與P(i)。若P(ID)≥P(i)則原先路徑更優(yōu),即被選擇概率更大,此時(shí)仍按(8)式中方法更新路由數(shù)據(jù)包后繼續(xù)轉(zhuǎn)發(fā);若P(ID)

(9)

由此使得所有Route獲得每一個(gè)Source節(jié)點(diǎn)的最短路由路徑信息,其能量區(qū)域內(nèi)路由算法流程如圖4所示。

圖4　能量區(qū)域內(nèi)路由算法

2.3　代理節(jié)點(diǎn)選取

(10)

其中,W為選取某一Route作為代理節(jié)點(diǎn)的期望;λ3+λ4=1,λ3、λ4為權(quán)衡跳數(shù)最小化和剩余能量最大化的系數(shù)。由(10)式可知剩余能量越大,跳數(shù)越小,則期望值越高。

根據(jù)(10)式計(jì)算能量區(qū)域內(nèi)所有Route作為代理節(jié)點(diǎn)的期望值W,選取具有最大W值的Route作為該能量區(qū)域的代理節(jié)點(diǎn),用于存儲(chǔ)該能量區(qū)域內(nèi)Source產(chǎn)生的信息以及與Sink進(jìn)行數(shù)據(jù)通信的節(jié)點(diǎn),并形成圖5所示的能量區(qū)域信息傳輸路徑。

圖5　某一能量區(qū)域路由路徑

3Sink最小移動(dòng)路徑策略

3.1　基于能量區(qū)域的網(wǎng)絡(luò)模型

在經(jīng)過eScan算法對系統(tǒng)進(jìn)行能量區(qū)域劃分以及能量區(qū)域內(nèi)路由信息的構(gòu)建和代理節(jié)點(diǎn)的選取后,形成圖6所示的系統(tǒng)模型圖,其中底部為能量區(qū)域的劃分,頂部為代理節(jié)點(diǎn)形成的連通圖。

圖6　基于 eScan的網(wǎng)絡(luò)模型圖

3.2　 Sink的移動(dòng)路徑策略

假設(shè)Sink節(jié)點(diǎn)可以獲知各個(gè)代理節(jié)點(diǎn)的位置信息,并根據(jù)代理節(jié)點(diǎn)位置信息制定可控移動(dòng)路徑,同時(shí)假設(shè)Sink節(jié)點(diǎn)移動(dòng)過程中不接收數(shù)據(jù),只在代理節(jié)點(diǎn)處停止時(shí)開始接收數(shù)據(jù)。為更加有效地進(jìn)行數(shù)據(jù)收集,維持系統(tǒng)能耗均衡,本文所描述的Sink移動(dòng)策略應(yīng)考慮以下2個(gè)方面:

(1) 移動(dòng)Sink在系統(tǒng)內(nèi)部收集信息時(shí)的路徑形成環(huán)路,即從起點(diǎn)出發(fā)收集完數(shù)據(jù)后最終又要回到起始點(diǎn)(也為終點(diǎn))。則將問題轉(zhuǎn)化為訪問各能量區(qū)域代理節(jié)點(diǎn)的環(huán)路遍歷問題,如圖6頂部所示。

(2) 能量區(qū)域采集的信息都存儲(chǔ)在Route代理節(jié)點(diǎn),加快了區(qū)域的能量消耗,易造成低能量區(qū)域出現(xiàn)“能量空洞”,不利于信息采集和區(qū)域壽命延長,為了提高低能量區(qū)域的有效性,延長區(qū)域網(wǎng)絡(luò)壽命,則采用低能量區(qū)域優(yōu)先訪問的原則。

在綜合考慮上述2個(gè)方面的基礎(chǔ)上,在最短路徑環(huán)路遍歷和低能量區(qū)域優(yōu)先訪問之間進(jìn)行加權(quán)折中,確保移動(dòng)Sink收集信息的有效性及系統(tǒng)能耗均衡性,延長網(wǎng)絡(luò)生命周期。具體權(quán)值計(jì)算采用(2)式。根據(jù)(2)式可計(jì)算出任意2個(gè)Route代理節(jié)點(diǎn)之間的權(quán)值E,故本文的Sink最小移動(dòng)路徑策略轉(zhuǎn)化為求已形成的帶權(quán)無向連通圖的最小環(huán)路遍歷路徑問題,如圖6頂部所示。

對于最短環(huán)路遍歷問題,為使遍歷路徑總權(quán)值最小,本文依據(jù)Dijkstra[11]算法,提出以下賦權(quán)連通圖的最小環(huán)路遍歷算法,該算法描述如下:

(1) 確定始點(diǎn)A(也為終點(diǎn))。

(2) 應(yīng)用Dijkstra算法求出從始點(diǎn)A到其余各頂點(diǎn)B,C,D，…的最短路徑權(quán)值DistA-B,DistA-C,DistA-D，…以及相應(yīng)的最短路徑PathA-B,PathA-C,PathA-D，…。

(3) 在各最短路徑權(quán)值DistA-B,DistA-C,DistA-D，…中查找最小路徑權(quán)值DistA-i,并求出i到A的次短路徑頂點(diǎn)序列Pathi-A。

(4) 檢查2個(gè)路徑序列PathA-i和Pathi-A中是否包含所有代理節(jié)點(diǎn),若已經(jīng)全部包含,則這2個(gè)路徑頂點(diǎn)序列順序即為Sink節(jié)點(diǎn)的環(huán)路遍歷路徑。否則,保持PathA-i不變,求出i到A的下一個(gè)次短路徑頂點(diǎn)序列Pathi-A,若路徑PathA-i和Pathi-A`包含全部代理節(jié)點(diǎn),則這2個(gè)路徑的頂點(diǎn)序列即為Sink的環(huán)路遍歷路徑,否則,按照上述方式繼續(xù)查找次短路徑頂點(diǎn)序列Pathi-A,直到找到包含全部代理節(jié)點(diǎn)的環(huán)路遍歷路徑或者i到A的路徑已經(jīng)達(dá)到最大。

(5) 若i到A的路徑已經(jīng)達(dá)到最大時(shí)還未求出包含全部代理節(jié)點(diǎn)的環(huán)路遍歷路徑序列,則從A到i的次短路徑開始,繼續(xù)重復(fù)步驟(2)~步驟(4)過程,求出從i到A的下一個(gè)次最短路徑頂點(diǎn)序列并作檢查,直到找到包含全部代理節(jié)點(diǎn)的環(huán)路遍歷路徑序列為止。

結(jié)合圖6頂部數(shù)據(jù)以及步驟(1)~步驟(5)算法,計(jì)算出代理節(jié)點(diǎn)最短環(huán)路遍歷路徑A→E→D→B→C→A,如圖7所示。

圖7　移動(dòng) Sink最短遍歷路徑

Sink計(jì)算出代理節(jié)點(diǎn)最短環(huán)路遍歷路徑后依次按照順序訪問各個(gè)代理節(jié)點(diǎn),當(dāng)Sink回到起始點(diǎn)時(shí),系統(tǒng)依照eScan算法重新進(jìn)行能量區(qū)域劃分,重新制定路由和遍歷路徑,進(jìn)行第2次信息采集。

4仿真實(shí)驗(yàn)

采用TCL/TK語言在NS2[12]環(huán)境下進(jìn)行仿真,對基于能量區(qū)域代理機(jī)制的移動(dòng)Sink路由算法的網(wǎng)絡(luò)壽命進(jìn)行評估與分析,并以AVRP[7]算法和eScan[8]算法作為對象進(jìn)行比較分析網(wǎng)絡(luò)壽命。本文網(wǎng)絡(luò)壽命定義為從網(wǎng)絡(luò)開始運(yùn)行到第1個(gè)節(jié)點(diǎn)死亡時(shí)的時(shí)間。

在仿真試驗(yàn)中,節(jié)點(diǎn)的布設(shè)如圖1所示,傳感節(jié)點(diǎn)被隨機(jī)部署在一塊100m×100m的矩形目標(biāo)區(qū)域中,Source節(jié)點(diǎn)數(shù)量設(shè)為500個(gè),Route節(jié)點(diǎn)為200個(gè),其節(jié)點(diǎn)通信半徑為1m,節(jié)點(diǎn)接收和轉(zhuǎn)發(fā)1個(gè)數(shù)據(jù)均消耗1個(gè)單位能量,MAC協(xié)議采用IEEE802.11,Sink節(jié)點(diǎn)按照設(shè)定路線從起點(diǎn)收集數(shù)據(jù)后返回原點(diǎn)。為便于實(shí)驗(yàn)分析,把矩形區(qū)域劃分為3個(gè)能量相近的區(qū)域,且每個(gè)區(qū)域初始能量隨機(jī)分布在(500±50)、(400±50)、(300±50)個(gè)單位。

圖8描述了節(jié)點(diǎn)能量對網(wǎng)絡(luò)壽命的影響。通過對比分析發(fā)現(xiàn),本文提出的路由算法相比于AVRP算法和eScan算法在每個(gè)區(qū)域的能耗上都能夠很好地將各個(gè)節(jié)點(diǎn)均衡地利用,有效地減少范洪的次數(shù),達(dá)到全局能耗的均衡,網(wǎng)絡(luò)的平均壽命分別提高約40%和25%,故本文提出的路由算法有效地提高了網(wǎng)絡(luò)壽命。

圖8　節(jié)點(diǎn)能量對網(wǎng)絡(luò)壽命的影響

圖9描述了節(jié)點(diǎn)發(fā)包率對網(wǎng)絡(luò)壽命的影響。通過對比分析發(fā)現(xiàn),AVRP算法和eScan算法在Sink移動(dòng)時(shí)只在通信范圍內(nèi)選取代理節(jié)點(diǎn)作為數(shù)據(jù)收集點(diǎn),不僅沒有考慮整體能耗,且路由鏈路也不斷被拓展,隨著節(jié)點(diǎn)發(fā)包率不斷變大,通信負(fù)載也增大,網(wǎng)絡(luò)能量會(huì)較快耗盡,而本文算法都是局部最優(yōu)路由,且在局部最優(yōu)的基礎(chǔ)上,Sink的移動(dòng)也最優(yōu)化,故而隨著發(fā)包率的變化,網(wǎng)絡(luò)壽命平均延長約30%~35%。

圖9　數(shù)據(jù)發(fā)包率對網(wǎng)絡(luò)壽命的影響

5結(jié)束語

在研究eScan算法的基礎(chǔ)上,結(jié)合緩存節(jié)點(diǎn)輔助模式的思想,提出了基于能量區(qū)域代理機(jī)制的移動(dòng)Sink路由算法。仿真實(shí)驗(yàn)結(jié)果表明,通過剩余能量掃描,可以將能量相近的節(jié)點(diǎn)劃分為一個(gè)能量區(qū)域,在每一個(gè)能量區(qū)域中進(jìn)行局部路由的構(gòu)建,有效地避免全局路由的范洪,節(jié)約了路由構(gòu)建的開銷;同時(shí)基于代理節(jié)點(diǎn)的選取,使代理節(jié)點(diǎn)的選取更加合理化,進(jìn)而使得每個(gè)能量區(qū)域的消耗達(dá)到均衡；再結(jié)合Sink最小移動(dòng)路徑策略,使得總體的能耗更為均衡。本文算法從局部到整體都達(dá)到有效的均衡,延長網(wǎng)絡(luò)的壽命。

[參考文獻(xiàn)]

[1]朱紅松,孫利民.無線傳感器網(wǎng)絡(luò)技術(shù)發(fā)展現(xiàn)狀[J].中興通信技術(shù),2009,15(5):1-5.

[2]WuXB,ChenGH,DasSK.Avoidingenergyholesinwirelesssensornetworkswithnonuniformnodedistribution[J].IEEETransactionsonParallelandDistributedSystems,2008,19(5):710-720.

[3]MartaM,CardeiM.Improvedsensornetworklifetimewithmultiplemobilesinks[J].PervasiveandMobileComputing,2009,5(5):542-555.

[4]NakayamaH,AnsariN,JamalipourA,etal.Fault-resilientsensinginwirelesssensornetworks[J].ComputerCommunications,2007,30(11/12):2375-2384.

[5]WangJ,YinY,etal.Anmobile-sinkbasedenergy-efficientclusteringalgorithmforwirelesssensornetworks[C]//ProcofIEEE12thInternationalConferenceonComputerandInformationTechnology,2012:678-683.

[6]TianK,ZhangBX,HuangK,etal.Datagatheringprotocolsforwirelesssensornetworkswithmobilesinks[C]//ProcofIEEEGlobecom,2010.

[7]DemirE,AykanatC,CambazogluBB.Alink-basedstorageschemeforefficientaggregatequeryprocessingonclusteredroadnetworks[J].InformationSystems, 2010, 35(1):75-93.

[8]ZhaoYJ,GovindanR,EstrinD.Residualenergyscanformonitoringsensornetworks[C]//ProcofIEEEWirelessCommunicationsandNetworkingConference,Orlando,2002:356-362.

[9]羅兗,徐云,黃劉生,等.一種動(dòng)態(tài)傳感器網(wǎng)絡(luò)中的新型路由算法[J].計(jì)算機(jī)工程,2008,34(16):141-143.

[10]KaplanED.UnderstandingGPS:principlesandapplications[M].Boston,MA:ArtechHouse,1996.

[11]王締.最佳旅行問題的一種求解方法[J].科教文匯:上旬刊,2011(8):1-3.

[12]KyunghwiK,WonjunL.MBAL:amobilebeacon-assistedlocalizationschemeforwirelesssensornetworks[C]//Procof16thInternationalConferenceonComputerCommunicationsandNetworks,2007:57-62.

(責(zé)任編輯馬國鋒)