王薇, 史浩山, 黃鵬宇, 高寶建, 牛進(jìn)平, 王舉

1.西北工業(yè)大學(xué) 電子信息學(xué)院, 陜西 西安 710072; 2.西北大學(xué) 信息科學(xué)與技術(shù)學(xué)院, 陜西 西安 710069 3.西安電子科技大學(xué) 通信工程學(xué)院, 陜西 西安 710071

基于二次柵格劃分的移動(dòng)sink最小路徑構(gòu)建算法

王薇1,2, 史浩山1, 黃鵬宇3, 高寶建2, 牛進(jìn)平2, 王舉2

1.西北工業(yè)大學(xué) 電子信息學(xué)院, 陜西 西安 710072; 2.西北大學(xué) 信息科學(xué)與技術(shù)學(xué)院, 陜西 西安 710069 3.西安電子科技大學(xué) 通信工程學(xué)院, 陜西 西安 710071

在無線傳感器網(wǎng)絡(luò)中引入移動(dòng)sink能夠有效解決能量空洞問題,從而提高無線傳感器網(wǎng)絡(luò)的生存時(shí)間。但是移動(dòng)sink的移動(dòng)速度限制通常會(huì)影響數(shù)據(jù)收集的時(shí)延特性,文章的研究重點(diǎn)即如何為移動(dòng)sink構(gòu)建最佳巡航路徑,從而減小信息收集時(shí)延。充分利用傳感器節(jié)點(diǎn)的通信范圍,將構(gòu)建最佳路徑問題轉(zhuǎn)化為求解帶鄰域的旅行商問題TSPN(traveling salesman problem with neighborhoods),并提出了一種基于二次柵格劃分的可變長(zhǎng)編碼單親遺傳算法的最佳路徑構(gòu)建方法。該算法首先在網(wǎng)絡(luò)區(qū)域中使用粗粒度柵格進(jìn)行劃分,并利用可變長(zhǎng)度編碼的單親遺傳算法獲得最佳途經(jīng)柵格,從而構(gòu)造出初始最佳路徑。然后對(duì)于每一個(gè)途經(jīng)柵格再次使用細(xì)粒度柵格進(jìn)行劃分以優(yōu)化收集路徑。仿真結(jié)果表明,新算法能夠獲得更短的數(shù)據(jù)收集路徑,大幅度減低了網(wǎng)絡(luò)信息收集時(shí)延,有效地拓展了網(wǎng)絡(luò)的生存時(shí)間。

無線傳感器網(wǎng)絡(luò);移動(dòng)sink;TSPN;柵格;最短路徑

近年來無線傳感器網(wǎng)絡(luò)WSN(wireless sensor network)在環(huán)境監(jiān)測(cè)、火情監(jiān)測(cè)、戰(zhàn)場(chǎng)探察等方面得到了廣泛的應(yīng)用[1]。在這些網(wǎng)絡(luò)中,大量的感知節(jié)點(diǎn)被部署到被測(cè)區(qū)域中,每當(dāng)有敏感事件發(fā)生時(shí),傳感器節(jié)點(diǎn)將收集到的數(shù)據(jù)經(jīng)由多跳路徑傳輸給靜止的匯聚節(jié)點(diǎn)(sink節(jié)點(diǎn))。由于全網(wǎng)收集的信息都要逐漸中轉(zhuǎn)、匯聚,因此必然會(huì)導(dǎo)致靠近sink節(jié)點(diǎn)的普通節(jié)點(diǎn)需要承載更多傳輸負(fù)荷,從而消耗更多的能量,最終加速其死亡,并縮短了整個(gè)網(wǎng)絡(luò)的生存時(shí)間,這就是所謂的“能量空洞”問題[2]。

在本項(xiàng)目組所承擔(dān)的野生金絲猴相關(guān)研究課題中,我們也發(fā)現(xiàn)了“能量空洞”問題的存在。我們將大量的無線傳感器節(jié)點(diǎn)部署在金絲猴經(jīng)常出現(xiàn)的區(qū)域,由于野外地形所限,sink節(jié)點(diǎn)的數(shù)量有限,因此其余節(jié)點(diǎn)的數(shù)據(jù)都需要經(jīng)過多次中轉(zhuǎn)后到達(dá)sink節(jié)點(diǎn)。運(yùn)行一段時(shí)間之后,我們發(fā)現(xiàn)靠近sink節(jié)點(diǎn)的普通節(jié)點(diǎn)總是最先耗盡電池。但是由于地處野外,節(jié)點(diǎn)電池難以更換,因此非常需要相應(yīng)的方法來解決能量空洞問題。

近年來,移動(dòng)sink的概念應(yīng)運(yùn)而生,利用移動(dòng)sink可以優(yōu)化數(shù)據(jù)的采集過程,并延長(zhǎng)整個(gè)網(wǎng)絡(luò)的生存時(shí)間[3-5],也可利用移動(dòng)sink來輔助節(jié)點(diǎn)定位,由此顯著提高定位精度[6-7]。在以上的研究中,我們可以看到由于移動(dòng)節(jié)點(diǎn)收集信息時(shí)更貼近傳感器節(jié)點(diǎn),因此更利于提高信息收集的數(shù)量與質(zhì)量,很好地解決sink固定時(shí)節(jié)點(diǎn)間耗能均衡的問題。

但是在實(shí)際的應(yīng)用環(huán)境中,WSN布設(shè)范圍通常較大,而受數(shù)據(jù)傳輸和承載平臺(tái)的限制，移動(dòng)sink的移動(dòng)速度大多不高,因此與靜止sink節(jié)點(diǎn)相比較,移動(dòng)sink常常需要更多的時(shí)間才能完成全網(wǎng)數(shù)據(jù)的收集工作。而信息收集時(shí)延的大小在實(shí)際應(yīng)用中是一個(gè)非常重要的性能衡量指標(biāo),因此有必要深入研究移動(dòng)sink的移動(dòng)路徑規(guī)劃問題,從而盡可能減少數(shù)據(jù)包的延遲。本文研究的重點(diǎn)即如何為移動(dòng)sink設(shè)計(jì)最短的行進(jìn)路由,從而獲得最小的數(shù)據(jù)采集時(shí)延。

1 相關(guān)工作

在收集WSN中的數(shù)據(jù)時(shí),移動(dòng)sink通常需要在網(wǎng)絡(luò)中按照某種路徑往復(fù)運(yùn)行。在移動(dòng)過程中,為了節(jié)省能量移動(dòng)sink通常僅會(huì)在某些信息匯聚點(diǎn)RP(rendezvous points)上才會(huì)開機(jī)采集數(shù)據(jù),而在運(yùn)動(dòng)過程中關(guān)閉傳輸電路以節(jié)省能量。當(dāng)移動(dòng)sink移動(dòng)到信息收集點(diǎn)時(shí),如果傳感器節(jié)點(diǎn)位于移動(dòng)sink的通信范圍之內(nèi),則上傳其相關(guān)信息。

按照移動(dòng)sink是否采用傳感器節(jié)點(diǎn)的自身位置作為信息收集點(diǎn),我們可以將移動(dòng)sink信息收集方式分為2種類型:①使用傳感器節(jié)點(diǎn)位置作為信息收集點(diǎn)坐標(biāo)的方法,在這類方法中將移動(dòng)sink的路徑規(guī)劃歸結(jié)為TSP(travelling salesman problem)問題,見文獻(xiàn)[8-12];②不使用傳感器節(jié)點(diǎn)位置作為信息收集點(diǎn)坐標(biāo)的算法,此時(shí)可以將問題歸結(jié)為TSP的一種變形——TSPN問題,見文獻(xiàn)[13]。

基于第一種思路,文獻(xiàn)[8]研究了在WSN節(jié)點(diǎn)隨機(jī)分布的情況下,移動(dòng)sink的移動(dòng)速度與信息收集效率之間的關(guān)系,并提出了一種MASP(maximum amount shortest path)算法。該算法將時(shí)延受限的信息收集問題轉(zhuǎn)化為一個(gè)整數(shù)線性規(guī)劃問題,并使用遺傳算法以及一種分布式近似算法確定路徑最優(yōu)解。文獻(xiàn)[9]將數(shù)據(jù)收集路徑長(zhǎng)度最小化問題歸結(jié)為一個(gè)單跳數(shù)據(jù)收集問題SHDGP(single-hop data gathering problem)。并將SHDGP問題轉(zhuǎn)化為一個(gè)混合的整數(shù)規(guī)劃問題進(jìn)行求解。文獻(xiàn)[10]以滿足時(shí)延要求和最小化網(wǎng)絡(luò)整體能耗為優(yōu)化目標(biāo),提出了一種基于虛擬點(diǎn)優(yōu)先級(jí)的移動(dòng)sink路徑優(yōu)化選擇方法。該方法在犧牲少量能耗的前提下能顯著降低算法時(shí)間復(fù)雜度。文獻(xiàn)[11-12]則提出了一種基于信息匯聚點(diǎn)RP的移動(dòng)sink數(shù)據(jù)收集機(jī)制。在該機(jī)制中傳感器節(jié)點(diǎn)將采集的信息以多跳方式發(fā)送給距離最近的RP節(jié)點(diǎn),移動(dòng)sink依次訪問各PR節(jié)點(diǎn)以收集數(shù)據(jù)。根據(jù)第二種思路,文獻(xiàn)[13]將移動(dòng)sink最短信息收集路徑問題看作是一種帶鄰近區(qū)域的旅行商問題TSPN,提出了一種啟發(fā)式算法構(gòu)建信息收集路徑,利用TSP路徑為不自交環(huán)路的特征構(gòu)建賽道,通過內(nèi)圈啟發(fā)式、彎道啟發(fā)式以及捷徑搜索尋找賽道內(nèi)的近似最短路徑。

對(duì)于以TSP問題為核心的算法,由于移動(dòng)sink直接遍歷各個(gè)傳感器節(jié)點(diǎn),因此不必考慮節(jié)點(diǎn)的通信范圍,從而簡(jiǎn)化信息收集問題。但是由于這種方法需要遍歷所有的節(jié)點(diǎn),因此即使感知區(qū)域不變,當(dāng)傳感器節(jié)點(diǎn)數(shù)量增多時(shí)移動(dòng)sink的信息收集路徑長(zhǎng)度也會(huì)相應(yīng)增多,從而導(dǎo)致網(wǎng)絡(luò)信息收集時(shí)延也隨之增大,所以這一方法在擴(kuò)展性和實(shí)用性方面都存在問題。

相較于基于TSP的方法,采用以TSPN為核心的方法是一個(gè)較好的思路。在這類算法中,移動(dòng)sink并不直接遍歷傳感器節(jié)點(diǎn)的位置坐標(biāo),而是首先確定一些信息收集點(diǎn)IGP(information gathering position)。這些信息收集點(diǎn)并不僅限于節(jié)點(diǎn)的位置,而有可能是部署區(qū)域中的任意位置點(diǎn)。移動(dòng)sink在工作的過程中并不連續(xù)收集信息,而是移動(dòng)到信息收集點(diǎn)的時(shí)候才激活以該點(diǎn)為中心的通信范圍內(nèi)的傳感器節(jié)點(diǎn)完成信息收集任務(wù)。同時(shí),由于不需要限制IGP的選擇范圍,構(gòu)建信息收集路徑的將會(huì)更加靈活,因此可以在很大程度上縮短信息收集路徑的長(zhǎng)度。并且由于不需要簇頭中轉(zhuǎn)、匯聚信息,所以有更好的能耗表現(xiàn)。但是基于TSPN方法的難點(diǎn)在于如何構(gòu)建最佳的信息收集路徑。

根據(jù)以上分析,本文中我們提出了一種新穎的算法來解決移動(dòng)sink路徑規(guī)劃問題。該算法采用二級(jí)柵格劃分的方法對(duì)收集點(diǎn)位置進(jìn)行逐層篩選以減少路徑搜索的空間復(fù)雜度,并采用可變長(zhǎng)編碼的退火單親遺傳算法計(jì)算收集點(diǎn)的最佳遍歷路徑。仿真結(jié)果顯示本文算法能夠獲得更短的信息收集路徑長(zhǎng)度,可顯著減小移動(dòng)sink信息收集時(shí)延。

2 基于二級(jí)柵格劃分的可變長(zhǎng)編碼單親遺傳算法

由于基于TSPN的移動(dòng)sink的最佳信息收集路徑問題的關(guān)鍵在于如何選取信息收集點(diǎn)以及如何構(gòu)建一條最短信息收集路徑。所以,本文所研究的問題可以歸納為:在給定傳感器網(wǎng)絡(luò)節(jié)點(diǎn)分布的條件下,選擇合適的信息收集點(diǎn),并確定一條最短的信息收集路徑,依次遍歷所有信息收集點(diǎn)收集信息,最終使信息收集過程的時(shí)延最小。

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

本文算法可以分為2個(gè)步驟:

步驟1 為了獲得最佳信息收集路徑,我們首先使用一個(gè)較大間隔的柵格將仿真區(qū)域劃分為若干柵格單元,并以每個(gè)柵格的中心點(diǎn)作為備選的信息收集點(diǎn),然后在這些備選的收集點(diǎn)集合中使用可變長(zhǎng)編碼單親遺傳算法構(gòu)建一條能夠覆蓋所有節(jié)點(diǎn)的最短的信息收集路徑。

在這個(gè)過程中,由于節(jié)點(diǎn)分布的不均勻性,因此構(gòu)建的路徑不一定包含所有的備選收集點(diǎn)。我們僅需要在備選收集點(diǎn)集合中找出一個(gè)子集,在該子集上收集信息就可以覆蓋網(wǎng)絡(luò)中所有節(jié)點(diǎn)。這個(gè)問題是一個(gè)典型的集合覆蓋問題SCP(set cover problem),SCP問題同樣是一個(gè)NP-hard問題。而且由于這種覆蓋集所涵蓋的備選信息收集點(diǎn)數(shù)目是可變的,所以如果使用遺傳算法構(gòu)建最佳路徑,則無法使用經(jīng)典的固定長(zhǎng)度編碼方式來表示遍歷路徑的位置序列,所以在這里我們無法使用常規(guī)的遺傳算法進(jìn)行求解。本文中我們使用可變長(zhǎng)度編碼的方法來解決這個(gè)問題,并對(duì)常規(guī)的單親遺傳算法進(jìn)行修改以適應(yīng)可變長(zhǎng)度編碼的問題。

步驟2 通過步驟1我們獲得了第一級(jí)最佳路徑。但由于其中所使用的柵格的劃分間隔比較大,所以第一級(jí)最佳路徑只是最佳路徑的一個(gè)初步結(jié)果。為了進(jìn)一步獲得更精確的遍歷路徑,我們?cè)俅吾槍?duì)步驟1中所獲最佳路徑對(duì)應(yīng)的一級(jí)柵格再做一次細(xì)粒度的柵格劃分。在更細(xì)的柵格劃分的基礎(chǔ)上進(jìn)一步確定收集點(diǎn)的精確位置坐標(biāo)。在步驟2中由于在每一個(gè)一級(jí)柵格中還是選取一個(gè)收集點(diǎn)位置,所以在該過程中收集點(diǎn)的數(shù)量是固定不變的,且與一級(jí)最佳路徑中涉及的柵格數(shù)相同。因此,為了提高運(yùn)算速度,在這里我們使用固定長(zhǎng)度編碼的單親遺傳算法進(jìn)行計(jì)算。最終就可以獲得更加精確的二級(jí)最佳信息收集路徑,并將其作為我們算法的最終結(jié)果。

圖1 二級(jí)柵格劃分方法

通過這種二級(jí)柵格篩選方法可以有效簡(jiǎn)化信息收集點(diǎn)的選擇,降低算法的計(jì)算量,為之后最佳路徑計(jì)算創(chuàng)造了有利條件。

2.2 算法流程

i∈I,j∈J,l∈N}

式中,nodel表示第l個(gè)傳感器節(jié)點(diǎn)的位置坐標(biāo),I、J分別表示橫、縱軸劃分的柵格數(shù),N表示場(chǎng)景中的節(jié)點(diǎn)數(shù),“‖‖”表示進(jìn)行歐氏距離計(jì)算。

算法流程描述如下:

Step1 產(chǎn)生初始種群

Step2 計(jì)算適應(yīng)值

適應(yīng)值是遺傳算法的進(jìn)化依據(jù),在本文算法中,選擇個(gè)體對(duì)應(yīng)路徑長(zhǎng)度作為個(gè)體的適應(yīng)值,適應(yīng)值越小代表個(gè)體越優(yōu)秀。

Step3 運(yùn)行可變長(zhǎng)度編碼單親遺傳算法

為了保持進(jìn)化過程中個(gè)體長(zhǎng)度的可變特性,本文設(shè)計(jì)了2個(gè)算子:倒序算子和置換算子。

倒序算子:對(duì)于一個(gè)個(gè)體,根據(jù)個(gè)體長(zhǎng)度隨機(jī)選擇倒序的起始、終結(jié)位置t1,t2,不失一般性設(shè)t1≤t2,然后將t1→t2的路徑倒置為t2→t1的路徑。

Step4 最優(yōu)保持策略

在算法的運(yùn)行過程中,將每一代中的最優(yōu)個(gè)體保存下來;在倒序、置換操作完成后,比較上一代的最優(yōu)個(gè)體值與當(dāng)代最優(yōu)個(gè)體值;若當(dāng)代最優(yōu)個(gè)體較差,則使用上代最優(yōu)個(gè)體替換當(dāng)代最差個(gè)體。

Step5 退出條件判斷。

Step6 二次柵格劃分及求解

在通過粗粒度柵格劃分大致確定最佳信息收集路徑之后,為了獲得更加精確的信息收集路徑,從而進(jìn)一步減少信息收集時(shí)延,我們對(duì)所獲得的一級(jí)最佳路徑所涉及的一級(jí)柵格再次使用更小粒度的柵格進(jìn)行劃分,并且在每一個(gè)粗粒度柵格中只選擇一個(gè)細(xì)粒度柵格中心作為路徑的信息收集點(diǎn)備選位置。通過這一過程,整個(gè)路徑的進(jìn)一步構(gòu)建就轉(zhuǎn)化為對(duì)每個(gè)粗粒度柵格中細(xì)粒度柵格中心的選擇過程,由于此時(shí)粗粒度柵格的數(shù)目已經(jīng)固定,所以這里的搜索問題就變成一個(gè)固定IGP數(shù)量的路徑優(yōu)化問題,即信息收集路徑上的信息收集點(diǎn)的數(shù)目是固定的。因此,我們?cè)谶@里就可以采用定長(zhǎng)編碼的單親遺傳算法來加以解決,最終可以獲得一條更好、更短的信息收集路徑。

3 仿真結(jié)果分析

我們對(duì)文中所提出的算法進(jìn)行了仿真,并將仿真結(jié)果與基于TSP的方法以及一種基于TSPN思路的算法——COM算法[14]進(jìn)行對(duì)比分析,為方便起見,我們將本文所提出的算法簡(jiǎn)稱為TGDA。

為了對(duì)比方便,本文采用和文獻(xiàn)[14]相同的仿真設(shè)置。仿真中傳感器節(jié)點(diǎn)均勻分布在在500 m×500 m的矩形區(qū)域里;節(jié)點(diǎn)數(shù)50～100個(gè)節(jié)點(diǎn);傳感器節(jié)點(diǎn)與移動(dòng)sink節(jié)點(diǎn)具有相同的通信半徑,半徑設(shè)置為20～100 m;每次生成50個(gè)拓?fù)?每一個(gè)拓?fù)浞抡?0次。

為了更加清晰地體現(xiàn)算法性能,首先我們固定節(jié)點(diǎn)的通信半徑為50 m和100 m,節(jié)點(diǎn)數(shù)由50逐級(jí)增加到100,并在這一過程中對(duì)3個(gè)算法的性能進(jìn)行仿真,結(jié)果如圖2所示。然后我們將節(jié)點(diǎn)數(shù)固定為50和100,節(jié)點(diǎn)的通信半徑從20 m逐漸增加到100 m,再次對(duì)3個(gè)算法進(jìn)行仿真,獲得的結(jié)果顯示如圖3所示。

圖2 節(jié)點(diǎn)通信半徑固定時(shí)TGDA算法的性能 圖3 節(jié)點(diǎn)數(shù)固定時(shí)TGDA算法的性能

從圖2的仿真結(jié)果可以看出,在通信半徑固定的情況下,無論網(wǎng)絡(luò)中的節(jié)點(diǎn)數(shù)為50還是100,3種算法所獲得的最佳路徑長(zhǎng)度都在逐漸增加。這是因?yàn)殡S著節(jié)點(diǎn)數(shù)的增多,移動(dòng)sink需要經(jīng)歷的節(jié)點(diǎn)數(shù)也會(huì)同步增長(zhǎng),所以路徑長(zhǎng)度會(huì)隨之增加。在節(jié)點(diǎn)數(shù)的不同設(shè)置下,顯而易見TSP算法的性能都是最差的。這是由于在TSP算法中,每個(gè)傳感器節(jié)點(diǎn)的位置就是IGP的位置,因此移動(dòng)sink需要遍歷所有節(jié)點(diǎn)位置才能完成信息收集任務(wù),因此該算法所獲得的路徑長(zhǎng)度必然是其中最長(zhǎng)的。相較于TSP算法,COM算法的性能有了不小的提高。由于COM算法會(huì)根據(jù)相鄰IGP覆蓋范圍的重疊程度選擇合并相鄰的IGP,這樣COM算法生成的路徑中包含的IGP更少,所以生成的路徑長(zhǎng)度相對(duì)更好。相較于對(duì)比算法本文提出的TGDA算法具有最好的算法性能,在通信半徑50m、節(jié)點(diǎn)數(shù)50的情況下TGDA算法生成的路徑長(zhǎng)度比COM算法縮短了33.37%。若節(jié)點(diǎn)數(shù)增加為100,TGDA算法的優(yōu)勢(shì)更是擴(kuò)大到了35.19%。

在固定節(jié)點(diǎn)數(shù)為50和100,節(jié)點(diǎn)通信半徑由20 m增加到100 m時(shí),仿真結(jié)果同樣相似。在固定節(jié)點(diǎn)數(shù)時(shí)可以看到由于TSP算法遍歷所有的節(jié)點(diǎn)位置,因此在節(jié)點(diǎn)數(shù)不變的情況下TSP算法的性能基本沒有變化。隨著節(jié)點(diǎn)通信半徑的增加,由于COM和TGDA算法都考慮到節(jié)點(diǎn)的通信范圍能力,因此這2種算法的性能都有了相應(yīng)提高。并且節(jié)點(diǎn)通信半徑越大意味著移動(dòng)sink節(jié)點(diǎn)可以在更大的范圍內(nèi)收集到節(jié)點(diǎn)上傳信息。所以隨著通信半徑的增長(zhǎng),COM以及TGDA算法的性能提高程度都隨之?dāng)U大,但本文算法提高程度更高。從圖3中看到,在節(jié)點(diǎn)數(shù)為50、通信半徑為100 m時(shí),相較于COM算法TGDA算法的路徑長(zhǎng)度減少了43.51%,若節(jié)點(diǎn)數(shù)增加到100,TGA算法的優(yōu)勢(shì)擴(kuò)大到48.16%。

以上仿真結(jié)果可見在不同的仿真配置下,本文提出的TGDA算法都取得了優(yōu)異的結(jié)果。TGDA算法能有效減少了移動(dòng)sink的信息收集路徑長(zhǎng)度,從而降低了移動(dòng)sink系統(tǒng)的信息收集時(shí)延,進(jìn)而提高了整個(gè)系統(tǒng)的執(zhí)行效率。

4 結(jié) 論

信息收集是WSN的一個(gè)關(guān)鍵應(yīng)用領(lǐng)域,是WSN實(shí)際應(yīng)用的基礎(chǔ)。移動(dòng)sink的引入使sink節(jié)點(diǎn)只需要通過傳感器節(jié)點(diǎn)通信范圍即可完成節(jié)點(diǎn)信息的收集,減少了信息傳輸?shù)沫h(huán)節(jié),簡(jiǎn)化了網(wǎng)絡(luò)協(xié)議的復(fù)雜度。本文在充分考慮節(jié)點(diǎn)的無線通信特性的條件下,研究了移動(dòng)sink在WSN中的最佳信息收集路徑規(guī)劃問題。在移動(dòng)sink最佳信息收集路徑的搜索過程中,本文算法通過二次柵格劃分的方法來篩選信息收集點(diǎn)的搜索范圍,簡(jiǎn)化算法的計(jì)算復(fù)雜度,在路徑構(gòu)建過程中的提出了一種新穎的基于可變長(zhǎng)編碼的單親遺傳算法來進(jìn)行路徑搜索。仿真結(jié)果表明本文算法與傳統(tǒng)的基于TSP的算法相比,能夠獲得更好(短)的信息收集路徑,減少了傳感器節(jié)點(diǎn)的傳輸能耗、延長(zhǎng)了網(wǎng)絡(luò)的生存時(shí)間。與基于TSPN的算法相比本文算法原理簡(jiǎn)單,擴(kuò)展性好,能夠獲得更好的信息收集路徑。因此本文算法非常適用于大規(guī)模WSN網(wǎng)絡(luò)信息收集路徑的構(gòu)建應(yīng)用。

[1] Ou C H. A Localization Scheme for Wireless Sensor Networks Using Mobile Anchors With Directional Antennas[J]. IEEE Sensors Journal, 2011, 11(7):1607-1616

[2] Olariu S, Stojmenovi I. Design Guidelines for Maximizing Lifetimeand Avoiding Energy Holes in Sensor Networks with Uniform Distribution and Uniform Reporting[C]∥IEEE Infocom, 2006: 1-12

[3] Zhao M, Yang Y. Bounded Relay Hop Mobile Data Gathering in Wireless Sensor Networks[J]. IEEE Trans on Computers, 2012, 61(2): 265-277

[4] Lin K, Chen M, Zeadally S, et al. Balancing Energy Consumption with Mobile Agents in Wireless Sensor Networks[J]. Future Generation Computer Systems, 2012, 28(2): 446-456

[5] Guo S, Wang C, Yang Y. Joint Mobile Data Gathering and Energy Provisioning in Wireless Rechargeable Sensor Networks[J]. IEEE Trans on Mobile Computing, 2014, 13(12): 2836-2852

[6] Liao W H, Lee Y C, Kedia S P. Mobile Anchor Positioning for Wireless Sensor Networks[J]. IET Communications, 2011, 5(7):914-921

[7] Chen H, Shi Q, Tan R, et al. Mobile Element Assisted Cooperative Localization for Wireless Sensor Networks with Obstacles[J]. IEEE Trans on Wireless Communications, 2010, 9(3): 956-963

[8] Gao S, Zhang H, Das S K. Efficient Data Collection in Wireless Sensor Networks with Path-Constrained Mobile Sinks[J]. IEEE Trans on Mobile Computing, 2010, 10(4): 592-608

[9] Ma M, Yang Y, Zhao M. Tour Planning for Mobile Data-Gathering Mechanisms in Wireless Sensor Networks[J]. IEEE Trans on Vehicular Technology, 2013, 62(4):1472-1483

[10] 郜帥, 張宏科. 時(shí)延受限傳感器網(wǎng)絡(luò)移動(dòng)Sink路徑選擇方法研究[J]. 電子學(xué)報(bào), 2011, 39(4):742-747 Gao Shuai, Zhang Hongke. Optimal Path Selection for Mobile Sink in Delay-guaranteed[J]. Acta Electronica Sinica, 2011, 39(4):742-747 (in Chinese)

[11] Xing G, Wang T, Jia W, et al. Rendezvous Design Algorithms for Wireless Sensor Networks with a Mobile Base Station[C]∥ACM International Symposium on Mobile Ad Hoc Networking and Computing, 2008: 231-240

[12] Xing G, Wang T, Xie Z, et al. Rendezvous Planning in Wireless Sensor Networks with Mobile Elements[J]. IEEE Trans on Mobile Computing, 2008, 7(12):1430-1443

[13] 袁遠(yuǎn), 彭宇行, 李?yuàn)檴?等. 高效的移動(dòng)sink路由問題的啟發(fā)式算法[J]. 通信學(xué)報(bào), 2011, 32(10):107-117 Yuan Yuan, Peng Yuxing, Li Shanshan, et al. Efficient Heuristic Algorithm for the Mobile Sink Routing Problem[J]. Journal on Communications, 2011, 32(10):107-117 (in Chinese)

[14] He L, Pan J, Xu J. A Progressive Approach to Reducing Data Collection Latency in Wireless Sensor Networks with Mobile Elements[J]. IEEE Trans on Mobile Computing, 2013, 12(7):1308-1320

A Routing Planning Algorithm base on Twice Grid Division for Mobile Sink

Wang Wei1,2, Shi Haoshan1, Huang Pengyu3,Gao Baojian2, Niu Jinping2, Wang Ju2

1.School of Electronics and Information, Northwestern Polytechnical University, Xi′an 710072, China 2. School of Information and Technology, Northwest University, Xi′an 710069, China 3. School of Telecommunications Engineering, Xidian University, Xi′an 710071, China

Introduce mobile sinks into wireless sensor networks can balance the energy level of the sensor nodes, resolve the hotspot problem and prolong the lifetime of the whole network. However, the mobility of the sink may also introduce additional delays. Therefore, it is important to design an efficient routing protocol for the mobile sink. In this paper, we deduce this routing planning problem into a Traveling Salesman Problem with Neighborhoods (TSPN). In addition, we propose a routing design algorithm base on twice grid division and variable-length Partheno-genetic Algorithm. In this algorithm, we divide the network area with the grids coarse-grained, and obtain the grids on the best path with variable-length Partheno-genetic Algorithm. We then divide every grid on the path with the grids fine-grained in order to optimize the path. Finally, we implement this algorithm in Matlab and the simulation results show that the proposed algorithm can significantly improves the efficiency and effectiveness of the routing planning for the mobile sink.

wireless sensor network; mobile sink; TSPN; routing planning; grid division

2016-04-12 基金項(xiàng)目：國家自然科學(xué)基金(61170218、61602379)與陜西省教育廳自然科學(xué)基金(15JK1742、12JK0937)資助

王薇(1977—)，女，西北工業(yè)大學(xué)博士研究生，西北大學(xué)講師，主要從事信息網(wǎng)絡(luò)理論、無線傳感器網(wǎng)絡(luò)研究。

TP393

A

1000-2758(2016)06-1016-06