傳感器網絡中多移動sink節點的路徑規劃算法

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

（1. 電子科技大學計算機科學與工程學院 成都 611731；2. 桂林電子科技大學廣西自動檢測技術與儀器重點實驗室 廣西 桂林 541004）

傳感器網絡中多移動sink節點的路徑規劃算法

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

（1. 電子科技大學計算機科學與工程學院 成都 611731；2. 桂林電子科技大學廣西自動檢測技術與儀器重點實驗室 廣西 桂林 541004）

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

近似算法； k-TSPN； 多移動sink； 無線傳感器網絡

數據采集是無線傳感器網絡的重要技術之一。傳統的數據采集模式首先依靠節點的自組織特性構建出完全連通的通信網絡，收集到的感知數據依據路由協議從感知區域傳輸到處理區域，從而完成感知數據的傳輸［1］。在實際應用中，經常會存在如下因素影響感知數據的采集：1） 對于大范圍的目標監控應用，采用傳感器節點隨機拋灑的方式進行傳感器節點的部署，有可能形成不能完全連通的傳感器網絡［2］；2） 由于地理位置或物理條件的限制、節點的能量耗盡、突發災難性事件等原因，傳感器網絡往往會主動或被動的演化為若干個互不連通的子網絡，從而影響數據采集和傳輸任務［3］；3） 各傳感器節點因為能量受限和頻繁的數據轉發，會形成感知區域的覆蓋空洞，從而降低整個傳感網絡的可用性［4］。

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

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

1 網絡模型和問題描述

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

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

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

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

2.1 k個移動sink路徑指派問題的求解

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

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

2.2 訪問點位置的優化

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

在優化路徑上，每一個節點的訪問點對應的θ的取值范圍，可以由［0，2π］縮小到由該節點通信圓盤到下一個節點通信圓盤的兩條外切線所包圍的區間［4］。文獻［4］利用這一特性壓縮了訪問點取值的搜索范圍，從而提高了求解效率。由于沒有考慮前后節點的位置對當前訪問點的影響，搜索范圍仍然比較大，為此本文進行如下設計進一步壓縮搜索范圍，提高求解效率。如圖1所示考慮兩個靜態節點的情形，移動sink的從基站S出發，依次訪問節點A、B后回到基站。節點A上訪問點的可行取值區域位于弧與弧的交集即弧之間，同理，B上的可行區域在弧之間?；《蔚娜≈捣秶鸀槠渲?，為節點A、B間的距離。對于多個靜態節點的情形，每個節點對應弧段的起始范圍可用類似的方法計算得到。

圖1 移動sink由S出發依次訪問節點A、B的通信區域

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

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

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

目標函數的梯度可表示為：

所用迭代公式為：

由以上分析可得設計的算法如下：

算法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

在迭代中θ的初值設為TSP路徑與各個節點通信圓盤的第一個交點的弧度，若θ超出壓縮后解空間的范圍，取對應的上界或下界的值，當兩次迭代得到的路徑長度小于閾值時迭代終止。

2.3 算法時間復雜度及近似比分析

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

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

3 算法仿真及比較

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

表1 100個節點時不同的ρ對算法的影響

表2 改進后的k-splitour與k-splitour的性能對比

為了驗證改進后的k-splitour算法的性能，本文在與以上實驗相同的場景下，設置不同的移動節點數目進行了測試，考察1 000次隨機實驗的均值，得到的結果如表2所示。從表2中可以發現，k取不同值時，改進后的k-splitour算法的均較原有算法的性能有所提升。同時從表2中也可以看出，隨著移動sink數目k的增加，改進算法所獲得的性能提升越明顯，這是因為子路徑數目的增加會導致更多的路徑自相交。

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

圖3 不同節點數目下路徑長度的比較圖

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

圖4顯示了50個節點的情況下，路徑長度隨著通信半徑增長的變化情況，可以看出當節點通信范圍超過70 m之后，GAGBS算法的性能開始下降，這是由于梯度下降所用步長設置過大導致的，該參數可以根據實際應用進一步優化。

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

圖5 使用4個移動sink時的路徑示例

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

4 結 論

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

本文得到廣西自動檢測技術與儀器重點實驗室基金（YQ16205）、廣西高校云計算與復雜系統重點實驗室資助項目（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］ 袁遠， 彭宇行， 李姍姍， 等. 高效的移動Sink路由問題的啟發式算法［J］. 通信學報， 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

國家科技重大專項（2014ZX03002001）；國家自然科學基金（61363070，61163058）；廣西自然科學基金（2014GXNSFAA118370）

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