基于生成圖算法的混合WSNs的避障調度研究*

謝光前， 李春光， 潘 豐

(1.江南大學 輕工過程先進控制教育部重點實驗室，江蘇 無錫 214122；2.常州工學院 計算機信息工程學院，江蘇 常州 213000))

基于生成圖算法的混合WSNs的避障調度研究*

謝光前1,2， 李春光1,2， 潘 豐1

(1.江南大學 輕工過程先進控制教育部重點實驗室，江蘇 無錫 214122；2.常州工學院 計算機信息工程學院，江蘇 常州 213000))

為了解決存在障礙物的混合無線傳感器網絡(WSNs)的動態傳感器調度問題，構建了基于生成圖的調度算法和模型。利用基于網格的技術獲得了障礙物的規整化圖形；根據基于生成圖的算法，使得最短路徑的搜索空間限制在連通圖中；在實現最短避障路徑的基礎上，獲得了動態傳感器的能量有效性的調度目標。通過仿真，驗證了方法的有效性。

混合無線傳感器網絡； 基于網格的； 生成圖； 調度

0 引 言

混合無線傳感器網絡(WSNs)已成為當前的熱點研究問題之一。在混合WSNs中，靜態傳感器感知目標區域的信息，并把這些信息向外傳送，功能較單一。動態傳感器根據靜態傳感器反饋過來的結果，移動到目標地區進行更深入的分析，然后進行相應的處理[1]。這里假定靜態傳感器的生命周期足夠長，這樣問題就歸結為如何有效調度動態傳感器，使得整個網絡系統的生命周期最長,因此，整個網絡系統的生命周期是由動態傳感器節點能量決定的。通常只要出現一個動態傳感器節點能量耗盡的情況，則意味整個網絡系統生命周期的結束,所以,合理調度動態傳感器的旅行路徑尤為關鍵。關于動態傳感器調度的問題，當前很多文獻已經做了大量的研究[2～4],但這些研究很少考慮WSNs中存在障礙物的情況,而在實際的應用環境中，會或多或少存在障礙物。

本文針對混合WSNs存在障礙物的情況下，提出了基于生成圖算法的動態傳感器調度方案。

1 調度模型的建立

1.1 初始模型

在實際應用中，網絡區域內環境多變，會存在大小不一，形狀各異的障礙物。隨著能量捕獲技術的進步，這里不考慮靜態傳感器的能量，認為其具有足夠的能量。所以,混合WSNs的生命周期由動態傳感器決定，只要有一個動態傳感器能量耗盡，則整個網絡生命周期結束。盡可能降低動態傳感器的能耗，最直接的辦法是以最短路徑到達目標區域。考慮到系統的復雜性，研究只考慮最簡單的情況，也就是只有一個動態傳感器，同時目標區域也只有一個。如圖1所示，監控區域是個矩形，黑色圓點代表隨機分布的靜

態傳感。黑色不規則圖形代表障礙物，這里假定有兩處障礙物。黑色實三角形S代表動態傳感器的初始區域位置，而白色虛三角形t代表目標區域位置。很顯然,從位置S移動到位置t的過程中存在繞行路徑，此種情況求解最短路徑存在一定的困難。

圖1 系統初始調度模型Fig 1 Initial scheduling model of system

1.2 模型的網格化處理

基于網格劃分技術目前已被廣泛應用于分析WSNs[5]。本文研究所劃分的網格單元為正方形，網格單元也是動態傳感器進行信息收集與處理的基本單位。每個網格單元存在一個匯聚點位置，在此位置，可以收集網格單元中所有傳感器的信息。匯聚點位置一般位于網格單元的中心，這樣便于收集網格單元中所有傳感器的信息。為了研究的方便，本文假定動態傳感器的最小移動單位為1，并且動態傳感器只能沿著水平或者垂直方向移動。圖2是圖1網格化的結果,其中小圓點代表每個網格單元的匯聚點位置，網格單元的邊長為單位1。

圖2與圖1相比，很顯然障礙物的邊緣地帶會與網格單元相交，可能只占用部分網格單元。假如:網格單元被部分占用，就認為此網格單元即為障礙物，這樣障礙物就變成了比較規整的圖形。圖2中，動態傳感器一開始位于起點黑色實三角形S所在網格單元的匯聚點位置，需要以最短路徑移動到終點白色虛三角形t的匯聚點位置即可。

圖2 系統模型網絡圖Fig 2 Grid graph of system model

2 基于生成圖算法的調度

文獻[6]提出了基于生成圖算法的基本思想，并解決了最小生成樹問題。動態傳感器的最短移動路徑問題，可轉化為最小生成樹問題。基于生成圖算法調度的基本思想是利用線掃描技術生成可能的調度路徑，并以此為基礎，利用Dijkstra算法容易找到最短路徑。本文基于其近似算法，對于某個確定點，對整個平面進行4等分,在不影響調度結果的前提下，使問題的求解大大簡化。如圖3(a)所示，黑色矩形為障礙物，障礙物的4個頂點分別為p1～p4，R1～R8是以p1～p4為原點的平面劃分區域。圖3(b)為動態傳感器初始或目標所在位置p的平面劃分區域。

圖3 生成圖算法中頂點位置搜索區域劃分Fig 3 Search region division for vertex in spanninggraph algorithm

利用圖3的區域劃分的方法，并根據算法1，生成圖4。因此,本文的調度目標就轉化為從生成圖中找到從源點S到目標點t的最短路徑。動態傳感器應該沿著障礙物邊線和基于算法1生成的連接線方向移動。這里需要說明的是本文的方法基于網格化基礎之上的，并且動態傳感器的移動只能水平或者垂直移動。所以，實際的動態傳感器的移動路徑不是沿著算法 1生成的連接線方向移動，而是基于連接線的Manhattan距離移動的。

圖4 系統模型生成圖Fig 4 Spanning graph of system model

算法1是利用線掃描技術，分別在頂點對應的各區域執行連線操作，頂點區域劃分見圖3，最終構建了系統模型的生成圖。

算法1生成圖的構建

輸入:

數組Vs:頂點坐標位置，包含障礙物各頂點位置和動態傳感器初始點以及目標點位置

輸出:

生成圖G:最終的連接圖，數組Vs中各點位于連接圖上

1)begin

2)數組Vs按x軸方向遞增排序;

3)障礙物頂點R2，R6區域，找到該區間最短路徑；

4)數組Vs按y軸方向遞增排序;

5)障礙物頂點R4，R8區域，找到該區間最短路徑;

6)數組Vs按x+y軸方向遞增排序;

7)障礙物頂點R1，R5區域及動態傳感器初始點目標點R1，R3區域，找到該區間最短路徑；

8)數組Vs按y-x軸方向遞增排序;

9)障礙物頂點R3，R7區域與動態傳感器初始點目標點R2，R4區域，找到該區間最短路徑；

10)end

3 仿真結果與分析

3.1 實驗場景

實驗場景如圖1中所示。網絡區域的大小為20×15,動態傳感器的最小移動單位為1，因此,把整個網絡區域劃分成20×15=300個網格單元，如圖2所示。實驗所使用的臺式機是Intel i5—2400處理器，4 GB內存和32位的Windows7系統。

3.2 評估結果

圖5顯示了在網格圖中動態傳感器的搜索空間極其最終的移動路徑。其中，黑色實三角形S為起點，白色虛三角形t為終點，圓點為算法的搜索空間，一共有104個網格單元。黑色圓點為動態傳感器的最終移動路徑，從起點S到終點t，一共移動了23個單位。根據實驗結果，很明顯最終的路徑也是最短路徑。

圖5 網格圖中動態傳感器的頂點擴展Fig 5 Vertex expansion of dynamic sensor in grid graph

圖6顯示了在生成圖中動態傳感器的搜索空間及其最終的移動路徑。從圖形中可以看出搜索空間只占34個單元格，而最終的動態傳感器也移動了23個單位，即為動態傳感器的最短移動距離。與圖5相比，圖6的搜索空間減小了2/3，但最終動態傳感器的移動距離大小一致，均為最短移動路徑。

圖6 生成圖中動態傳感器的頂點擴展Fig 6 Vertex expansion of dynamic sensor in spanning graph

表1顯示了兩種情形下，程序的運行時間。在網格圖中，程序運行了0.112 s，而在生成圖中，程序運行了0.034 s，與網格圖相比，生成圖程序運行時間大約減少了2/3。

根據實驗結果表明:基于生成圖的方法，明顯效率更高，在不影響找到最短路徑的前提下，減小了算法的搜索空間，提高了效率。

表1 兩種模型運行時間的比較
Tab 1 Comparison of run time of two models

模型運行時間(s)網格圖0．112生成圖0．034

4 結 論

本文提出了具體的實現方案，將問題的求解范圍局限于實現的生成圖中，從而減小了搜索空間，提高了搜索效率。最終找到了最短路徑，提高了網絡的生命周期。本文只研究了一對一這種最基本的情形，即一個動態傳感器對應一個目標區域。

[1] Gu Y,Ji Y,Li J,et al.ESWC:Efficient scheduling for the mobile sink in wireless sensor networks with delay constraint[J].IEEE Transactions on Parallel and Distributed Systems,2013,24(7):1310-1320.

[2] Wang Y C,Peng W C,Tseng Y C.Energy-balanced dispatch of mobile sensors in a hybrid wireless sensor networks[J].IEEE Transactions on Parallel and Distributed Systems,2010,21(12):1836-1850.

[3] Wang Y C.A two-phase dispatch heuristic to schedule the movement of multi-attribute mobile sensors in a hybrid wireless sensor networks[J].IEEE Transactions on Mobile Computing,2014,13(4):709-722.

[4] Shwetha G K,Sagarika B,Jithendranath M.Energy balanced dispatch of mobile sensors in hybrid wireless sensor networks with obstacles[J].IOSR Journal of Computer Engineering,2012,2(1):47-51.

[5] Peng H,Chen Y W.Energy consumption bounds analysis and its applications for grid-based wireless sensor networks[J].Journal of Network and Computer Applications,2013,36(1):444-451.

[6] Zhou H,Shenoy N,Nicholls W.Efficient spanning tree construction without Delaunay triangulation[J].Information Processing Letter,2002,81(5):271-276.

Research on obstacle avoidance scheduling based on spanning graphs algorithm for hybrid WSNs*

XIE Guang-qian1,2, LI Chun-guang1,2, PAN Feng1

(1.Key Laboratory of Advanced Process Control for Light Industry,Ministry of Education,Jiangnan University,Wuxi 214122,China; 2.College of Computer and Information Engineering,Changzhou Institute of Technology,Changzhou 213000,China)

To solve scheduling problem of dynamic sensors in hybrid wireless sensor networks(WSNs)with obstacles，a scheduling algorithm and model based on spanning graphs is constructed.Regularization shape of obstacles is obtained by grid-based techniques;according to algorithm based on spanning graphs,search space of the shortest path is restricted within connection graphs;a goal of energy-efficient scheduling for dynamic sensors is achieved,on the basis of realizing the shortest path of obstacle avoidance.Through simulation,the effectiveness of the method is verified.

hybrid WSNs; grid-based; spanning graph; scheduling

10.13873/J.1000—9787(2015)12—0019—03

2015—03—15

國家自然科學基金資助項目(61273131)

TP 393

： A

： 1000—9787(2015)12—0019—03

謝光前(1977-)，男，安徽安慶人，博士研究生，主要從事無線傳感器網絡、智能控制等方面的研究。