傳感器網(wǎng)絡(luò)中多移動sink節(jié)點(diǎn)的路徑規(guī)劃算法

俸 皓，羅 蕾，董榮勝，王 勇

（1. 電子科技大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院 成都 611731；2. 桂林電子科技大學(xué)廣西自動檢測技術(shù)與儀器重點(diǎn)實(shí)驗(yàn)室 廣西 桂林 541004）

傳感器網(wǎng)絡(luò)中多移動sink節(jié)點(diǎn)的路徑規(guī)劃算法

俸 皓1，2，羅 蕾1，董榮勝2，王 勇2

（1. 電子科技大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院 成都 611731；2. 桂林電子科技大學(xué)廣西自動檢測技術(shù)與儀器重點(diǎn)實(shí)驗(yàn)室 廣西 桂林 541004）

考慮多移動sink且路徑端點(diǎn)在圓周邊界上的情形，將此抽象為一個(gè)混合優(yōu)化問題，該優(yōu)化問題具有維數(shù)高和搜索空間大的特點(diǎn)，經(jīng)典的算法（如k-splitour算法）無法針對其連續(xù)分量進(jìn)行優(yōu)化，為此該文首先以k-splitour算法獲得k條子路徑并設(shè)計(jì)了消除子路徑交叉的方法，以獲得對離散分量的局部尋優(yōu)，再通過設(shè)計(jì)對連續(xù)分量的局部優(yōu)化方法以確定每個(gè)通信圓盤上訪問點(diǎn)的位置，從而可以高效地獲取多個(gè)sink移動節(jié)點(diǎn)的規(guī)劃路徑解。給出了算法結(jié)果的上界及其理論證明。最后通過實(shí)驗(yàn)驗(yàn)證了所設(shè)計(jì)的模型及其求解算法能有效地解決數(shù)據(jù)采集中的路徑規(guī)劃問題。

近似算法； k-TSPN； 多移動sink； 無線傳感器網(wǎng)絡(luò)

數(shù)據(jù)采集是無線傳感器網(wǎng)絡(luò)的重要技術(shù)之一。傳統(tǒng)的數(shù)據(jù)采集模式首先依靠節(jié)點(diǎn)的自組織特性構(gòu)建出完全連通的通信網(wǎng)絡(luò)，收集到的感知數(shù)據(jù)依據(jù)路由協(xié)議從感知區(qū)域傳輸?shù)教幚韰^(qū)域，從而完成感知數(shù)據(jù)的傳輸［1］。在實(shí)際應(yīng)用中，經(jīng)常會存在如下因素影響感知數(shù)據(jù)的采集：1） 對于大范圍的目標(biāo)監(jiān)控應(yīng)用，采用傳感器節(jié)點(diǎn)隨機(jī)拋灑的方式進(jìn)行傳感器節(jié)點(diǎn)的部署，有可能形成不能完全連通的傳感器網(wǎng)絡(luò)［2］；2） 由于地理位置或物理?xiàng)l件的限制、節(jié)點(diǎn)的能量耗盡、突發(fā)災(zāi)難性事件等原因，傳感器網(wǎng)絡(luò)往往會主動或被動的演化為若干個(gè)互不連通的子網(wǎng)絡(luò)，從而影響數(shù)據(jù)采集和傳輸任務(wù)［3］；3） 各傳感器節(jié)點(diǎn)因?yàn)槟芰渴芟藓皖l繁的數(shù)據(jù)轉(zhuǎn)發(fā)，會形成感知區(qū)域的覆蓋空洞，從而降低整個(gè)傳感網(wǎng)絡(luò)的可用性［4］。

為了提高無線傳感器網(wǎng)絡(luò)的可用性、減少節(jié)點(diǎn)的通信能量消耗及平衡節(jié)點(diǎn)的負(fù)載，近年來研究者引入了具備可控移動能力的sink節(jié)點(diǎn)代替?zhèn)鹘y(tǒng)傳感器網(wǎng)絡(luò)中的固定sink節(jié)點(diǎn)實(shí)施數(shù)據(jù)收集任務(wù)［5］。在各種基于移動sink的數(shù)據(jù)采集方案中，單跳數(shù)據(jù)采集的方式由于能夠最大限度地減少傳感器節(jié)點(diǎn)的通信能量消耗和平衡節(jié)點(diǎn)的負(fù)載，且通信鏈路質(zhì)量能夠得到更好的保證，從而得到了廣泛的關(guān)注和應(yīng)用［6］。如何獲取移動sink的最短路徑，以降低網(wǎng)絡(luò)的數(shù)據(jù)采集延遲及移動sink的能耗，一直是研究中的關(guān)鍵問題［5］。在考慮了傳感器節(jié)點(diǎn)的通信范圍之后，問題可建模為帶有圓形鄰域且鄰域可相互重疊的帶鄰域的旅行商問題（traveling salesman problem with neighborhoods， TSPN），該問題已經(jīng)被證明是APXHard的［7］。在實(shí)際應(yīng)用之中，由于節(jié)點(diǎn)的數(shù)目往往比較多，低時(shí)間復(fù)雜度的近似算法更加受到重視。近似算法可分為旅行商問題（traveling salesman problem， TSP）后置型和TSP前置型兩類。TSP后置算法［8-10］首先獲取各個(gè)近鄰區(qū)域的訪問點(diǎn)，然后再計(jì)算這些訪問點(diǎn)的TSP路徑。對鄰域不重疊的特殊情況，可取得比較好的效果，但當(dāng)存在重疊鄰域時(shí)，由于很難評價(jià)每次選擇的訪問點(diǎn)對最終路徑的影響程度，所以此時(shí)TSP后置型算法的效果并不理想。在隨機(jī)部署的無線傳感器網(wǎng)絡(luò)中，通信區(qū)域的重疊往往不可避免，因此這類算法在隨機(jī)部署的傳感器網(wǎng)絡(luò)中應(yīng)用較少。TSP前置算法先使用通信區(qū)域的中心構(gòu)建一條TSP路徑，再以此為基礎(chǔ)進(jìn)行路徑優(yōu)化，這種方法的優(yōu)點(diǎn)是便于采用漸進(jìn)式的優(yōu)化算法且解的效果便于評價(jià)，但沒有討論訪問點(diǎn)在圓盤上的情形［11-12］。文獻(xiàn)［11-12］將路徑優(yōu)化問題建模為“標(biāo)簽覆蓋”的問題，采用動態(tài)規(guī)劃算法在O（n3）的時(shí)間復(fù)雜度內(nèi)得到TSP路徑中圓心之間的捷徑，但該方法只考慮了子路徑上的端點(diǎn)是某個(gè)通信區(qū)域的中心的情形，沒有考慮端點(diǎn)可以在圓周邊界的情況，這限制了該算法性能的提升，而且這樣對模型的簡單化處理是以增加移動sink的延時(shí)為代價(jià)的。文獻(xiàn)［13］提出了一種O（n2）時(shí)間復(fù)雜度的近似算法，該算法首先應(yīng)用TSP路徑不自交的特性，構(gòu)建一條賽道，隨后在賽道上采用內(nèi)圈啟發(fā)式、彎道啟發(fā)式搜索策略得到近似最短路徑，但是該算法只支持單個(gè)移動sink的情形。在文獻(xiàn)［14］提出的CSS算法之中，以TSP路徑為基礎(chǔ)，首先采用確定性的最小圓覆蓋算法減少路徑中訪問區(qū)域的數(shù)目，再使用路徑覆蓋和二分搜索進(jìn)一步對路徑進(jìn)行優(yōu)化，時(shí)間復(fù)雜度為O（n2（logn+log（1/δ）），δ是一個(gè)足夠小的常數(shù)，用于在二分搜索算法中判斷兩個(gè)點(diǎn)是否足夠相近。但該算法也是只對多移動sink提供支持。從目前能夠查到的文獻(xiàn)來看還沒有考慮多個(gè)移動sink節(jié)點(diǎn)且路徑端點(diǎn)在圓周邊界上的模型及其近似求解算法的討論。

本文將數(shù)據(jù)采集問題中基于多移動sink且路徑端點(diǎn)在圓周邊界上的節(jié)點(diǎn)路徑規(guī)劃問題抽象為一個(gè)復(fù)雜的離散與連續(xù)混合優(yōu)化問題，該優(yōu)化問題具有維數(shù)高和搜索空間大難于求解的特點(diǎn)，經(jīng)典的k-splitour算法無法針對連續(xù)分量進(jìn)行優(yōu)化，而且會產(chǎn)生交叉的不可行子路徑解，為此本文首先通過k-splitour算法獲得k條子路徑，并設(shè)計(jì)了順序交換的局部尋優(yōu)方法，再通過貪婪路徑覆蓋與近似梯度下降算法確定每個(gè)通信圓盤上訪問點(diǎn)的位置以達(dá)到對連續(xù)分量的局部尋優(yōu)，從而可以高效地獲取近似最優(yōu)的多個(gè)sink移動節(jié)點(diǎn)的規(guī)劃路徑解。

1 網(wǎng)絡(luò)模型和問題描述

假設(shè)二維平面上部署有n個(gè)傳感器節(jié)點(diǎn)，記為｛（v0， r0）， （v1， r1），， （vi， ri），， （vn， rn）｝，vi表示第i個(gè)傳感器的位置，其通信范圍建模為圓形區(qū)域，ri表示對應(yīng)的通信半徑，其中 v0為基站位置， r0=0。假設(shè)給定有k個(gè)移動sink節(jié)點(diǎn)分別由基站出發(fā)，每個(gè)移動sink可以沿著各自事先規(guī)劃好的子路徑依次經(jīng)過部分傳感器節(jié)點(diǎn)的通信范圍，完成數(shù)據(jù)收集后返回基站，記第i個(gè)移動sink需要訪問的傳感器節(jié)點(diǎn)數(shù)目為mi。將第i條子路徑第一次進(jìn)入到路徑上第j個(gè)傳感器節(jié)點(diǎn)的通信范圍的位置稱為節(jié)點(diǎn)j上的訪問點(diǎn)，記作piπj。在各種可能的子路徑規(guī)劃方案中，讓各個(gè)子路徑長度中最大的取值最小，減少移動sink的遍歷時(shí)間，從而降低數(shù)據(jù)采集的延時(shí)。由此多移動sink路徑規(guī)劃問題可表示為：

式中，d（p，q）表示平面上兩點(diǎn)之間的距離；訪問點(diǎn)piπj總是位于以第i個(gè)傳感器節(jié)點(diǎn)為圓心、以ri為半徑的通信圓盤上。傳感器節(jié)點(diǎn)vji的訪問點(diǎn)piπj可以表示為

2 多移動sink路徑規(guī)劃問題的近似算法

上節(jié)式（1）中的子路徑如何指派以及各個(gè)訪問點(diǎn)的位置如何確定均需要優(yōu)化。為此本文將問題（1）分解為兩個(gè)階段解決：首先基于k-splitour解決多個(gè)移動sink的路徑指派問題，并設(shè)計(jì)了順序交換的局部尋優(yōu)方法，然后提出了貪婪近似梯度下降搜索算法解決訪問點(diǎn)的位置優(yōu)化問題，具體的算法設(shè)計(jì)步驟與分析如下。

2.1 k個(gè)移動sink路徑指派問題的求解

文獻(xiàn)［15］提出的k-splitour算法可以在O（n）的時(shí)間復(fù)雜度之內(nèi)獲得k條TSP路徑，算法的近似比為α+1-1/k，α是所采用的1-TSP算法的近似比。通過對k-splitour算法的分析可發(fā)現(xiàn)，每條子路徑的起始邊和結(jié)束邊，可能與該子路徑之前的邊產(chǎn)生相交。依據(jù)三角不等式，最優(yōu)TSP路徑中是不存在自相交的邊的，因此設(shè)計(jì)了順序交換的方法對該子路徑去除自相交，進(jìn)一步縮短子路徑的長度達(dá)到局部尋優(yōu)的效果。具體設(shè)計(jì)的算法如下：

算法1：OX-k-splitour算法

1） Find a 1-TSP tour TTSP=

2） for all i（i=1，2，…， k-1） do

3） find the last node vp（i）such that the length of the path from v0to vp（i）along TTSPis not greater than（i/k）（L-2cmax）+cmax， where cmax= maxjd（v0， vj）；

4） end for

5） form k subtours as ST1=

6） for all i（i=1，2，…，k） do

7） Eend= e（vp（i）， v0）；

8） Estart= e（v0， v1）；

9） for all nodes j in STi

10） if e（vj， vj+1） intersected with Eend

11） vj+1?vp（i）；

12） reverse visit sequence of

13） end if

14） end for

15） for all nodes j in STi

16） if e（vj， vj+1） intersected with Estart

17） vj+1?v1；

18） reverse visit sequence of

19） end if

20） end for

21） end for

22） return ST=｛ST1， ST2，…， STk｝

算法1首先使用現(xiàn)有TSP問題求解算法或工具（如concorde［16］）找到一條TSP回路，第2）～5）行采用k-splitour算法得到k條TSP子路徑，第9）～14）行以及第15）～20）行分別用于檢測及消除各個(gè)子路徑中起始邊及結(jié)束邊所產(chǎn)生的自相交，時(shí)間復(fù)雜度均為O（n），因此算法1的時(shí)間復(fù)雜度為CTSP+O（n），CTSP是所用TSP近似算法的時(shí)間復(fù)雜度。由于消除了k-splitour中的自相交邊，所以算法的近似比APP≤ α+1-1/k。

2.2 訪問點(diǎn)位置的優(yōu)化

由算法1可以得到各條可行子路徑解，接下來需要確定子路徑上在圓周邊界上的訪問點(diǎn)的位置。由于式（1）中的訪問點(diǎn)要求在傳感器通信圓盤上［4］，傳感器節(jié)點(diǎn)vji的訪問點(diǎn)piπji可以表示為

在優(yōu)化路徑上，每一個(gè)節(jié)點(diǎn)的訪問點(diǎn)對應(yīng)的θ的取值范圍，可以由［0，2π］縮小到由該節(jié)點(diǎn)通信圓盤到下一個(gè)節(jié)點(diǎn)通信圓盤的兩條外切線所包圍的區(qū)間［4］。文獻(xiàn)［4］利用這一特性壓縮了訪問點(diǎn)取值的搜索范圍，從而提高了求解效率。由于沒有考慮前后節(jié)點(diǎn)的位置對當(dāng)前訪問點(diǎn)的影響，搜索范圍仍然比較大，為此本文進(jìn)行如下設(shè)計(jì)進(jìn)一步壓縮搜索范圍，提高求解效率。如圖1所示考慮兩個(gè)靜態(tài)節(jié)點(diǎn)的情形，移動sink的從基站S出發(fā)，依次訪問節(jié)點(diǎn)A、B后回到基站。節(jié)點(diǎn)A上訪問點(diǎn)的可行取值區(qū)域位于弧與弧的交集即弧之間，同理，B上的可行區(qū)域在弧之間。弧段的取值范圍為其中，為節(jié)點(diǎn)A、B間的距離。對于多個(gè)靜態(tài)節(jié)點(diǎn)的情形，每個(gè)節(jié)點(diǎn)對應(yīng)弧段的起始范圍可用類似的方法計(jì)算得到。

圖1 移動sink由S出發(fā)依次訪問節(jié)點(diǎn)A、B的通信區(qū)域

對θ的取值范圍作了裁剪限定之后，除了減少了搜索空間的范圍，解空間中的極值點(diǎn)也減少了。圖2給出了示例圖的解空間分布的情況。如圖2a所示，在［0， 2π］的整個(gè)定義域上，路徑長度存在多個(gè)極值點(diǎn)，而在壓縮了θ的取值范圍之后，圖2b所示的解空間呈現(xiàn)出單一最值的波谷，為優(yōu)化解的搜索提供了極大的便利。

圖2 示例圖1中的完全搜索空間和壓縮之后的搜索空間比較

受裁剪搜索空間之后解結(jié)構(gòu)空間變化的啟發(fā)，本文提出了一種基于貪婪路徑覆蓋和近似梯度下降的搜索策略，用于獲取路徑規(guī)劃問題的近似最優(yōu)解。算法的主要思想是從當(dāng)前節(jié)點(diǎn)vi的訪問點(diǎn)位置pi開始，以路徑覆蓋的方式，前向查找到第一個(gè)未能構(gòu)成路徑覆蓋的節(jié)點(diǎn)vj，隨后在vi和vj構(gòu)成的節(jié)點(diǎn)集合之上，使用梯度下降算法搜索每個(gè)節(jié)點(diǎn)之上的訪問點(diǎn)位置對應(yīng)的θ。對參數(shù)θvi的偏導(dǎo)數(shù)可由下式計(jì)算得到：

目標(biāo)函數(shù)的梯度可表示為：

所用迭代公式為：

由以上分析可得設(shè)計(jì)的算法如下：

算法2：貪婪近似梯度下降搜索算法（Greedy approximate gradient based search algorithm， GAGBS）

Input： TSP tour for V（v0presents base station which location is p0）： i.e. TTSP=

1） TGAGBS←p0；

2） caculate θi's upper and lower bound for all nodes in TTSP

3） for all viin TTSP

4） find the largest vjthat the distance of all the sensor nodes（vi，vi+1，…， vj） to the tour less than ri

5） form the subtour ST=

6） apply approximate gradient based local search on

ST， obtain access points

7） append

8） replace

9） end for

10） combine turn point for TGAGBS

11） return TGAGBS

在迭代中θ的初值設(shè)為TSP路徑與各個(gè)節(jié)點(diǎn)通信圓盤的第一個(gè)交點(diǎn)的弧度，若θ超出壓縮后解空間的范圍，取對應(yīng)的上界或下界的值，當(dāng)兩次迭代得到的路徑長度小于閾值時(shí)迭代終止。

2.3 算法時(shí)間復(fù)雜度及近似比分析

該算法采用分段路徑上的梯度信息代替全局梯度信息，可避免梯度下降迭代過程中由于節(jié)點(diǎn)數(shù)目過大導(dǎo)致的每次計(jì)算目標(biāo)函數(shù)時(shí)的用時(shí)過高，且容易過早陷入全局極值的缺陷。貪婪梯度搜索過程中，每個(gè)節(jié)點(diǎn)迭代次數(shù)的上界是，算法的時(shí)間復(fù)雜度為其中ρ為梯度下降的步長，m是每次貪婪路徑覆蓋的節(jié)點(diǎn)數(shù)目的平均期望值，m≤n。由于路徑上過多的轉(zhuǎn)折點(diǎn)的數(shù)目會對移動sink的移動性產(chǎn)生影響，所以在算法的第10）行，對已獲得的訪問點(diǎn)再使用路徑覆蓋的思想進(jìn)行一次時(shí)間復(fù)雜度為O（n）的轉(zhuǎn)折點(diǎn)合并操作，達(dá)到減少轉(zhuǎn)折點(diǎn)數(shù)目并進(jìn)一步縮短路徑長度的目的。綜合以上分析，算法的時(shí)間復(fù)雜度為

證明：整個(gè)算法由算法1和算法2兩階段組成。設(shè)此子路徑所對應(yīng)的最優(yōu)TSP路徑為TTSP，由2.1節(jié)對算法1的分析可知，|Tox| / |TTSP|≤（α+1-1/k）。在算法2每次迭代中，都有|Tk+1|≤|Tk|，因此算法產(chǎn)生的是一個(gè)非增序列。由于子路徑初始長度為|Tox|，所以|TGAGBS|≤|Tox|。因?yàn)門opt到路徑上第i個(gè)節(jié)點(diǎn)的距離一定小于ri，所以移動sink沿著Topt到每個(gè)節(jié)點(diǎn)的通信區(qū)域時(shí)，訪問該節(jié)點(diǎn)一次之后再返回到Topt繼續(xù)前進(jìn)所形成的路徑也是TSP問題的近似解，所以有綜合以上分析，定理得證。

3 算法仿真及比較

為了驗(yàn)證本文所提出的路徑規(guī)劃模型及其求解算法的有效性，進(jìn)行了如下仿真實(shí)驗(yàn)。所用硬件平臺為 Intel（R） Core（TM） i7-3632QM 2.2GHz，4 GB內(nèi)存，軟件平臺為Matlab2012b。文獻(xiàn)［11，13］指出延時(shí)性能與路徑長度呈正相關(guān)關(guān)系，進(jìn)而以路徑長度衡量延時(shí)性能，本文采取同樣的方法與其他算法進(jìn)行比較。仿真實(shí)驗(yàn)在500 m×500 m的監(jiān)控區(qū)域內(nèi)隨機(jī)部署傳感器節(jié)點(diǎn)。為觀察算法所用參數(shù)對算法性能的影響，在隨機(jī)分布有100個(gè)通信范圍為20 m的節(jié)點(diǎn)的場景下進(jìn)行了實(shí)驗(yàn)。實(shí)驗(yàn)隨機(jī)生成了1 000個(gè)樣本，統(tǒng)計(jì)結(jié)果見表1，其中，計(jì)算時(shí)間為各次計(jì)算的均值。可以看出，當(dāng)ρ=π/20時(shí)可以以較低的計(jì)算時(shí)間取得較好的計(jì)算結(jié)果。

表1 100個(gè)節(jié)點(diǎn)時(shí)不同的ρ對算法的影響

表2 改進(jìn)后的k-splitour與k-splitour的性能對比

為了驗(yàn)證改進(jìn)后的k-splitour算法的性能，本文在與以上實(shí)驗(yàn)相同的場景下，設(shè)置不同的移動節(jié)點(diǎn)數(shù)目進(jìn)行了測試，考察1 000次隨機(jī)實(shí)驗(yàn)的均值，得到的結(jié)果如表2所示。從表2中可以發(fā)現(xiàn)，k取不同值時(shí)，改進(jìn)后的k-splitour算法的均較原有算法的性能有所提升。同時(shí)從表2中也可以看出，隨著移動sink數(shù)目k的增加，改進(jìn)算法所獲得的性能提升越明顯，這是因?yàn)樽勇窂綌?shù)目的增加會導(dǎo)致更多的路徑自相交。

為了測試算法的在不同節(jié)點(diǎn)規(guī)模問題下的性能，設(shè)計(jì)了如下的場景進(jìn)行測試：節(jié)點(diǎn)數(shù)目分別從初始值50開始，以10為增量逐步增加到100個(gè)，對于每種節(jié)點(diǎn)數(shù)目的場景，分別生成100個(gè)測試樣本。統(tǒng)計(jì)結(jié)果是針對該場景下所有測試樣本的均值。近似梯度下降所用參數(shù)ρ=π/20，迭代終止閾值為0.5。為驗(yàn)證GAGBS算法的有效性，首先比較了使用單移動sink時(shí)不同算法的表現(xiàn)。本文采用與文獻(xiàn)［14］一致的參數(shù)，即對于所有的節(jié)點(diǎn)，通信半徑均取值為20 m。與LC算法［12］和CSS算法［14］對比的結(jié)果如圖3所示?？梢钥闯觯珿AGBS算法的性能較LC算法有較大的提升，比CSS算法亦有5%左右的改進(jìn)。

圖3 不同節(jié)點(diǎn)數(shù)目下路徑長度的比較圖

圖4 不同通信范圍時(shí)路徑長度的比較圖

圖4顯示了50個(gè)節(jié)點(diǎn)的情況下，路徑長度隨著通信半徑增長的變化情況，可以看出當(dāng)節(jié)點(diǎn)通信范圍超過70 m之后，GAGBS算法的性能開始下降，這是由于梯度下降所用步長設(shè)置過大導(dǎo)致的，該參數(shù)可以根據(jù)實(shí)際應(yīng)用進(jìn)一步優(yōu)化。

圖5顯示了一個(gè)使用4個(gè)移動sink，節(jié)點(diǎn)通信范圍服從20～50 m之間的均勻分布（表示為U（20，50）場景下的路徑實(shí)例。圖6的實(shí)驗(yàn)顯示了使用100個(gè)傳感器節(jié)點(diǎn)，通信范圍服從U（20，50）分布時(shí)，不同數(shù)目的移動sink對k-splitour、k-LC和k-GAGBS算法產(chǎn)生的路徑影響，可以看出本文所提出的算法大大縮短了子路徑的長度，取得了較好的效果。

圖5 使用4個(gè)移動sink時(shí)的路徑示例

圖6 不同移動sink數(shù)目最大路徑長度的比較圖

4 結(jié) 論

本文將無線傳感器網(wǎng)絡(luò)中多移動sink數(shù)據(jù)收集中的路徑規(guī)劃問題建模為路徑端點(diǎn)在通信圓盤之上的混合優(yōu)化問題，并設(shè)計(jì)了求解的近似算法。給出并在理論上證明了算法的上界，最后通過仿真實(shí)驗(yàn)及與經(jīng)典的CSS、k-LC算法的對比，驗(yàn)證了該模型及其求解算法的有效性。

本文得到廣西自動檢測技術(shù)與儀器重點(diǎn)實(shí)驗(yàn)室基金（YQ16205）、廣西高校云計(jì)算與復(fù)雜系統(tǒng)重點(diǎn)實(shí)驗(yàn)室資助項(xiàng)目（2015209）資助，在此表示感謝。

［1］ XU X， LUO J， ZHANG Q. Delay tolerant event collection in sensor networks with mobile sink［C］//Proceedings of the IEEE INFOCOM. San Diego， USA： IEEE， 2010： 1-9.

［2］ GUPTA P， KUMAR P. Critical power for asymptotic connectivity in wireless networks［M］//WILLIAM M M，GEORGE Y， ZHANG Qing. Stochastic Analysis， Control， Optimization and Applications. New York： Springer， 1998：547-566.

［3］ WU Fang-jing， TSENG Yu chee. Energy-Conserving data gathering by mobile mules in a spatially separated wireless sensor network［J］. Wireless Communications and Mobile Computing， 2013， 13（15）： 1369-1385.

［4］ YUAN Bo， ORLOWSKA M， SADIQ S. On the optimal robot routing problem in wireless sensor networks［J］. IEEE Trans on Knowledge and Data Engineering， 2007， 19（9）：1252-1261.

［5］ MARIO D F， SAJAL K D， GIUSEPPE A. Data collection in wireless sensor networks with mobile elements： a survey［J］. ACM Trans on Sensor Networks， 2011， 8（1）： 108-142.

［6］ MA Ming， YANG Yuan-yuan， ZHAO Miao. Tour planning for mobile data-gathering mechanisms in wireless sensor networks［J］. IEEE Trans on Vehicular Technology， 2013，62（4）： 1472-1483.

［7］ DE BERG M， GUDMUNDSSON J， KATZ M J， et al. TSP with neighborhoods of varying size［J］. Journal of Algorithms， 2005， 57： 22-36.

［8］ DUMITRESCU A， MITCHELL J S B. Approximation algorithms for TSP with neighborhoods in the plane［J］. Journal of Algorithms， 2003， 48（1）： 135-159.

［9］ ELBASSIONI K， FISHKIN A， MUSTAFA N， et al. Approximation algorithms for euclidean group TSP［C］//32nd Internationall Colloquium on Automata，Languages and Programming. Lisbon： Springer Verlag， 2005：1115-1126.

［10］ MITCHELL J. A constant-factor approximation algorithm for TSP with pairwise-disjoint connected neighborhoods in the plane［C］//Proceedings of SoCG. New York， NY， USA：ACM， 2010.

［11］ SUGIHARA R， GUPTA R. Improving the data delivery latency in sensor networks with controlled mobility［C］// Proceedings of DCOSS. Santorini Island， Greece： ［s.n.］，2008： 386-399.

［12］ SUGIHARA R， RAJESH K G. Path planning of data mules in sensor networks［J］. ACM Transactions on Sensor Networks， 2011， 8（1）： 1-27.

［13］ 袁遠(yuǎn)， 彭宇行， 李姍姍， 等. 高效的移動Sink路由問題的啟發(fā)式算法［J］. 通信學(xué)報(bào)， 2011， 32（10）： 107-117. YUAN Yuan， PENG Yu-xing， LI Shan-shan， et al. Efficient heuristic algorithm for the mobile sink routing problem［J］. Journal on Communications， 2011， 32（10）： 107-117.

［14］ HE Liang， PAN Jian-ping， XU Jing-dong. 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.

［15］ FREDERICKSON G N， HECHT M S， KIM C E. Approximation algorithms for some routing problems［C］// Symposium of foundations of Computer Science. Houston，TX， USA： IEEE， 1976： 216-227.

［16］ COOK W. Concorde TSP solver［EB/OL］. ［2014-06-02］. http：//www.math.uwaterloo.ca/tsp/concorde.html.

編 輯 蔣 曉

Tour Planning in Wireless Sensor Networks for Multi-Mobile Sinks

FENG Hao1，2， LUO Lei1， DONG Rong-sheng2， and WANG Yong2
（1. School of Computer Science and Engineering， University of Electronic Science and Technology of China Chengdu 611731；2. Guangxi Key Laboratory of Automatic Detecting Technology and Instruments， Guilin University of Electronic Technology Guilin Guangxi 541004）

This paper considers the situation where multi-mobile sinks and path endpoints are located along the edge of the circumference， and abstracts it as a hybrid optimization problem characterized in high dimensionality and large searching space. Classic algorithms like the k-splitour algorithm cannot optimize its continuous variables. This paper first obtains k sub-paths by adopting k-splitour algorithm and designs the method to eliminate the crossing of sub-paths to acquire local optimum for discrete variables. Then the algorithm acquires multi-mobile sinks path planning results efficiently by designing local optimization methods for continuous variables to decide on the location of access points on each communication disk. The upper bound of the algorithm and its theoretical proof are presented. The experiments show the effectiveness of both the designed model and its algorithm in solving the path planning problem in data collection.

approximate algorithm； k-TSPN； multi-mobile sinks； wireless sensor networks

TP393

A

10.3969/j.issn.1001-0548.2016.02.017

2015 - 07 - 14；

2016 - 02 - 26

國家科技重大專項(xiàng)（2014ZX03002001）；國家自然科學(xué)基金（61363070，61163058）；廣西自然科學(xué)基金（2014GXNSFAA118370）

俸皓（1978 - ），男，博士生，主要從事無線傳感器網(wǎng)絡(luò)、嵌入式實(shí)時(shí)軟件等方面的研究.