謝光前， 李春光， 潘 豐

(1.江南大學(xué) 輕工過程先進(jìn)控制教育部重點(diǎn)實(shí)驗(yàn)室，江蘇 無錫 214122；2.常州工學(xué)院 計算機(jī)信息工程學(xué)院，江蘇 常州 213000))

基于生成圖算法的混合WSNs的避障調(diào)度研究*

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

(1.江南大學(xué) 輕工過程先進(jìn)控制教育部重點(diǎn)實(shí)驗(yàn)室，江蘇 無錫 214122；2.常州工學(xué)院 計算機(jī)信息工程學(xué)院，江蘇 常州 213000))

為了解決存在障礙物的混合無線傳感器網(wǎng)絡(luò)(WSNs)的動態(tài)傳感器調(diào)度問題，構(gòu)建了基于生成圖的調(diào)度算法和模型。利用基于網(wǎng)格的技術(shù)獲得了障礙物的規(guī)整化圖形；根據(jù)基于生成圖的算法，使得最短路徑的搜索空間限制在連通圖中；在實(shí)現(xiàn)最短避障路徑的基礎(chǔ)上，獲得了動態(tài)傳感器的能量有效性的調(diào)度目標(biāo)。通過仿真，驗(yàn)證了方法的有效性。

混合無線傳感器網(wǎng)絡(luò)； 基于網(wǎng)格的； 生成圖； 調(diào)度

0 引 言

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

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

1 調(diào)度模型的建立

1.1 初始模型

在實(shí)際應(yīng)用中，網(wǎng)絡(luò)區(qū)域內(nèi)環(huán)境多變，會存在大小不一，形狀各異的障礙物。隨著能量捕獲技術(shù)的進(jìn)步，這里不考慮靜態(tài)傳感器的能量，認(rèn)為其具有足夠的能量。所以,混合WSNs的生命周期由動態(tài)傳感器決定，只要有一個動態(tài)傳感器能量耗盡，則整個網(wǎng)絡(luò)生命周期結(jié)束。盡可能降低動態(tài)傳感器的能耗，最直接的辦法是以最短路徑到達(dá)目標(biāo)區(qū)域。考慮到系統(tǒng)的復(fù)雜性，研究只考慮最簡單的情況，也就是只有一個動態(tài)傳感器，同時目標(biāo)區(qū)域也只有一個。如圖1所示，監(jiān)控區(qū)域是個矩形，黑色圓點(diǎn)代表隨機(jī)分布的靜

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

圖1 系統(tǒng)初始調(diào)度模型Fig 1 Initial scheduling model of system

1.2 模型的網(wǎng)格化處理

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

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

圖2 系統(tǒng)模型網(wǎng)絡(luò)圖Fig 2 Grid graph of system model

2 基于生成圖算法的調(diào)度

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

圖3 生成圖算法中頂點(diǎn)位置搜索區(qū)域劃分Fig 3 Search region division for vertex in spanninggraph algorithm

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

圖4 系統(tǒng)模型生成圖Fig 4 Spanning graph of system model

算法1是利用線掃描技術(shù)，分別在頂點(diǎn)對應(yīng)的各區(qū)域執(zhí)行連線操作，頂點(diǎn)區(qū)域劃分見圖3，最終構(gòu)建了系統(tǒng)模型的生成圖。

算法1生成圖的構(gòu)建

輸入:

數(shù)組Vs:頂點(diǎn)坐標(biāo)位置，包含障礙物各頂點(diǎn)位置和動態(tài)傳感器初始點(diǎn)以及目標(biāo)點(diǎn)位置

輸出:

生成圖G:最終的連接圖，數(shù)組Vs中各點(diǎn)位于連接圖上

1)begin

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

3)障礙物頂點(diǎn)R2，R6區(qū)域，找到該區(qū)間最短路徑；

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

5)障礙物頂點(diǎn)R4，R8區(qū)域，找到該區(qū)間最短路徑;

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

7)障礙物頂點(diǎn)R1，R5區(qū)域及動態(tài)傳感器初始點(diǎn)目標(biāo)點(diǎn)R1，R3區(qū)域，找到該區(qū)間最短路徑；

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

9)障礙物頂點(diǎn)R3，R7區(qū)域與動態(tài)傳感器初始點(diǎn)目標(biāo)點(diǎn)R2，R4區(qū)域，找到該區(qū)間最短路徑；

10)end

3 仿真結(jié)果與分析

3.1 實(shí)驗(yàn)場景

實(shí)驗(yàn)場景如圖1中所示。網(wǎng)絡(luò)區(qū)域的大小為20×15,動態(tài)傳感器的最小移動單位為1，因此,把整個網(wǎng)絡(luò)區(qū)域劃分成20×15=300個網(wǎng)格單元，如圖2所示。實(shí)驗(yàn)所使用的臺式機(jī)是Intel i5—2400處理器，4 GB內(nèi)存和32位的Windows7系統(tǒng)。

3.2 評估結(jié)果

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

圖5 網(wǎng)格圖中動態(tài)傳感器的頂點(diǎn)擴(kuò)展Fig 5 Vertex expansion of dynamic sensor in grid graph

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

圖6 生成圖中動態(tài)傳感器的頂點(diǎn)擴(kuò)展Fig 6 Vertex expansion of dynamic sensor in spanning graph

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

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

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

模型運(yùn)行時間(s)網(wǎng)格圖0．112生成圖0．034

4 結(jié) 論

本文提出了具體的實(shí)現(xiàn)方案，將問題的求解范圍局限于實(shí)現(xiàn)的生成圖中，從而減小了搜索空間，提高了搜索效率。最終找到了最短路徑，提高了網(wǎng)絡(luò)的生命周期。本文只研究了一對一這種最基本的情形，即一個動態(tài)傳感器對應(yīng)一個目標(biāo)區(qū)域。

[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

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

TP 393

： A

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

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