移動混合傳感網(wǎng)中節(jié)點自主部署算法

秦寧寧 余穎華 吳德恩

?

移動混合傳感網(wǎng)中節(jié)點自主部署算法

秦寧寧*余穎華 吳德恩

(江南大學(xué)輕工過程先進控制教育部重點實驗室 無錫 214122)

針對節(jié)點感知半徑不均衡的移動傳感網(wǎng)絡(luò)節(jié)點的部署問題，論文提出一種基于VL (Voronoi Laguerre)圖分割的節(jié)點自主部署算法(Autonomous Deployment Algorithm, ADA)。ADA先對目標(biāo)區(qū)域做VL圖劃分，將目標(biāo)區(qū)域的覆蓋任務(wù)在各個傳感器節(jié)點之間進行分配。分配到覆蓋子區(qū)間任務(wù)的節(jié)點通過構(gòu)造VL受控多邊形來確定下一輪候選目標(biāo)位置。未分配到覆蓋子區(qū)間的節(jié)點則根據(jù)自身與鄰居節(jié)點感知圓及目標(biāo)區(qū)域邊界的幾何位置關(guān)系計算所受虛擬力，最終確定下一輪目標(biāo)點坐標(biāo)。網(wǎng)絡(luò)各個節(jié)點通過逐輪更新自身位置，從而提高網(wǎng)絡(luò)覆蓋。仿真結(jié)果表明，ADA算法在網(wǎng)絡(luò)覆蓋率、節(jié)點部署速度和節(jié)點分布均勻性等方面具有明顯的優(yōu)勢。

移動傳感網(wǎng)絡(luò)；VL (Voronoi Laguerre)圖；受控多邊形；覆蓋率

1 引言

在移動傳感器網(wǎng)絡(luò)的現(xiàn)實應(yīng)用中，節(jié)點的初次部署通常由隨機拋撒實現(xiàn)，因此很難保證對檢測區(qū)域的覆蓋率以及網(wǎng)絡(luò)連通性[1]，節(jié)點需要自身的再次部署定位以獲得滿足應(yīng)用需求的感知覆蓋。

針對移動節(jié)點的再次部署問題[2,3]，文獻[4]提出了一種基于Voronoi多邊形[5,6]形心的部署策略(Centroid-Based Scheme, CBS)，將目標(biāo)區(qū)域的覆蓋問題轉(zhuǎn)換為每個節(jié)點對各自Voronoi多邊形的覆蓋優(yōu)化問題。文獻[7]在CBS的基礎(chǔ)之上提出了一種基于Voronoi盲區(qū)多邊形形心的部署策略，可有效提高網(wǎng)絡(luò)覆蓋率，但子區(qū)間的劃分方法只適合節(jié)點感知半徑均一的同構(gòu)網(wǎng)絡(luò)。針對節(jié)點感知半徑不同的異構(gòu)網(wǎng)絡(luò)，文獻[8]提出了一種基于VL (Voronoi Laguerre)圖[9]的Minmax部署策略。該算法部署速率相對較高，但部署效果易受節(jié)點位置的影響，部署完成后存在部分小感知半徑節(jié)點始終位于其他節(jié)點的感知范圍內(nèi)，造成覆蓋冗余，魯棒性較差。文獻[10]采用 MW-Voronoi圖分割目標(biāo)區(qū)間，各個節(jié)點在自身所受虛擬力[11]的作用下定向移動。但由于各子區(qū)間包含曲線邊界，增大了算法運算復(fù)雜度[12]。

基于上述分析，本文在文獻[8]的基礎(chǔ)之上提出了一種面向移動異構(gòu)傳感器網(wǎng)絡(luò)[13]的節(jié)點自主部署算法(Autonomous Deployment Algorithm, ADA)。算法采用VL圖劃分目標(biāo)區(qū)域，針對由此產(chǎn)生的兩類節(jié)點分別采用不同的策略進行移動部署，不僅克服了VorLag算法魯棒性較差的缺點，同時避免了因節(jié)點半徑差異而造成的覆蓋冗余，可以有效提高單個節(jié)點覆蓋效率、網(wǎng)絡(luò)覆蓋率以及節(jié)點分布均衡性。

2 基本知識

2.1 網(wǎng)絡(luò)模型

2.2 VL圖

圖1 VL圖劃分

在VL圖中，VL多邊形內(nèi)盲區(qū)的判定可轉(zhuǎn)化為對多邊形頂點的點覆蓋判決，具體對應(yīng)關(guān)系為：如果VL多邊形頂點不完全被其對應(yīng)節(jié)點覆蓋，則該VL多邊形內(nèi)存在覆蓋盲區(qū)，且每個被覆蓋頂點同時被另外兩個一類節(jié)點覆蓋；否則，該VL多邊形內(nèi)不存在覆蓋盲區(qū)。

3 ADA算法

3.1 一類節(jié)點的VCS部署

根據(jù)節(jié)點對其VL多邊形頂點的覆蓋關(guān)系，節(jié)點VL受控多邊形的構(gòu)造情況為：若VL多邊形的頂點未全部被覆蓋，則可根據(jù)定義構(gòu)造VL受控多邊形；若VL多邊形的所有頂點均被覆蓋，內(nèi)無覆蓋盲區(qū)，VL受控多邊形不存在。

3.1.1 節(jié)點候選位置

3.1.2 VL受控多邊形的構(gòu)造

不失一般性，以圖2網(wǎng)絡(luò)為例，介紹VL受控多邊形的構(gòu)造機理。圖2中節(jié)點覆蓋了自身VL多邊形()的頂點，根據(jù)VL多邊形非邊界頂點的覆蓋情況，此時節(jié)點和也同時覆蓋。由于,對的覆蓋影響，導(dǎo)致內(nèi)由節(jié)點負(fù)責(zé)的最大凈覆蓋區(qū)域變小。此時按定義為構(gòu)造受控多邊形(，分別對,運行VCS策略，所得候選目標(biāo)位置分別為圖2中三角形和圓形。顯然，當(dāng)節(jié)點位于圓形位置時可實現(xiàn)對更有效的覆蓋。

由VL受控多邊形的定義可知，受控多邊形的構(gòu)造中有時也會出現(xiàn)凹多邊形，如圖3中的受控多邊形。為簡化VCS的計算復(fù)雜度，并兼顧?quán)従庸?jié)點對VL多邊形覆蓋影響，可直接將受控多邊形中內(nèi)角為鈍角的頂點剔除，由剩余頂點構(gòu)成的多邊形，即為考慮了鄰居節(jié)點覆蓋影響后的受控凸多邊形。

圖2節(jié)點候選位置選擇 圖3 VL-受控凹多邊形

3.2 二類節(jié)點的VRS部署策略

在節(jié)點部署過程中，文獻[8]未考慮二類節(jié)點的移動需求，部署完成后存在部分二類節(jié)點位于一類節(jié)點的感知范圍內(nèi)，造成網(wǎng)絡(luò)覆蓋率降低以及資源浪費。為使二類節(jié)點自主遠離臨近節(jié)點以及檢測區(qū)域邊界，可為其設(shè)計如下部署策略：

3.3 ADA算法步驟

在VCS和VRS部署策略中，為減小能量損耗，當(dāng)一類節(jié)點對VL多邊形的覆蓋面積增長率不小于門限值，二類節(jié)點所受合斥力不小于門限斥力時，節(jié)點才能移動。ADA算法實現(xiàn)步驟如表1所示。

表1 ADA算法

4 仿真實驗

4.1 覆蓋率

圖4(a)–圖4(c)顯示了某網(wǎng)絡(luò)單次ADA算法對60個節(jié)點的部署過程。其中，初始覆蓋率為, 5次迭代后達到，經(jīng)過14次迭代后覆蓋率穩(wěn)定在。圖4(d)–圖4(f)顯示了簡化ADA算法的節(jié)點部署情況。在相同初始條件下，經(jīng)過16次迭代，簡化ADA算法可取得的最終覆蓋率約為。雖然簡化ADA的覆蓋性能略低于ADA，但由于具有更高的運算效率，增強了算法本身的現(xiàn)實應(yīng)用性。

圖4 ADA和簡化ADA算法下的某次部署過程

為考察ADA的性能，在相同條件下分別運行VorLag, ADA和簡化ADA算法，網(wǎng)絡(luò)覆蓋率的變化如圖5所示。每次迭代中，ADA和簡化ADA的覆蓋率總高于VorLag。這是由于ADA通過構(gòu)造受控多邊形來優(yōu)化節(jié)點候選目標(biāo)位置，增強了節(jié)點對自身VL多邊形的覆蓋效果。同時二類節(jié)點自主遠離鄰近節(jié)點的感知區(qū)域，覆蓋冗余的減小也相應(yīng)提高了網(wǎng)絡(luò)凈覆蓋面積。ADA中節(jié)點的候選位置為節(jié)點多邊形形心和最小最大點二者中可提高更高覆蓋的點，而簡化ADA中節(jié)點的候選位置僅由多邊形的形心決定，因此在每次迭代中，簡化ADA的網(wǎng)絡(luò)覆蓋率會略低于ADA，但明顯高于VorLag算法。

圖5平均覆蓋率隨迭代次數(shù)的變化

圖6覆蓋率隨節(jié)點數(shù)目的變化

4.2 快速性

圖7針對不同的節(jié)點數(shù)目，分析了VorLag和ADA算法中節(jié)點移動的平均次數(shù)。當(dāng)節(jié)點數(shù)目小于60時，隨著節(jié)點數(shù)目的增加，每個節(jié)點劃分到的VL多邊形相對變小，節(jié)點需要通過更多次移動才能實現(xiàn)對VL多邊形的最大覆蓋。當(dāng)節(jié)點數(shù)目高于60以后，越來越多的節(jié)點完全覆蓋自身的VL多邊形，節(jié)點移動較少的次數(shù)即達到終止條件，最終導(dǎo)致節(jié)點移動次數(shù)隨著節(jié)點數(shù)目的增加逐漸減小。

圖7所需迭代次數(shù)隨節(jié)點數(shù)目的變化

4.3 節(jié)點覆蓋性能指標(biāo)

參考文獻：[15]，定義節(jié)點感知半徑不均衡網(wǎng)絡(luò)節(jié)點分布均勻性指標(biāo)，即為每個節(jié)點與其一跳鄰居距離與兩者感知半徑和差值的絕對值的標(biāo)準(zhǔn)差均值。表2統(tǒng)計了VorLag和ADA在不同節(jié)點數(shù)目下，覆蓋效率CE以及的變化情況。由表2數(shù)據(jù)可知，在任何節(jié)點數(shù)目下，ADA算法的覆蓋性能均優(yōu)于VorLag算法。當(dāng)較小時，網(wǎng)絡(luò)節(jié)點分布均勻性隨節(jié)點個數(shù)的增加而變好，當(dāng)高于某個數(shù)值時，隨節(jié)點數(shù)目的增加，節(jié)點分布均勻性逐漸變差。隨著的增大，區(qū)域覆蓋冗余程度變高，兩種算法中的節(jié)點覆蓋效率均呈下降趨勢，但ADA始終優(yōu)于VorLag算法。

表2 節(jié)點覆蓋性能指標(biāo)

5 總結(jié)

本文提出了一種移動混合傳感網(wǎng)節(jié)點的自主部署算法，針對目標(biāo)區(qū)間劃分產(chǎn)生的兩類節(jié)點，分別采用不同的策略確定其候選位置。其中，一類節(jié)點通過構(gòu)造VL受控多邊形，將Minimax策略和CBS策略相結(jié)合來優(yōu)化節(jié)點候選目標(biāo)位置；二類節(jié)點根據(jù)自身與周圍節(jié)點的幾何位置關(guān)系計算所受虛擬斥力，從而確定移動目標(biāo)點位置，在提高網(wǎng)絡(luò)覆蓋率和部署快速性的同時，增強了網(wǎng)絡(luò)節(jié)點分布均勻性。網(wǎng)絡(luò)中所有節(jié)點通過逐輪移動最終實現(xiàn)對檢測區(qū)域的最大覆蓋。

參 考 文 獻

[1] 錢志鴻, 王義君. 面向物聯(lián)網(wǎng)的無線傳感器網(wǎng)絡(luò)綜述[J]. 電子與信息學(xué)報, 2013, 35(1): 215-227. doi: 10.3724/SP.J.1146. 2012.00876.

QIAN Zhihong and WANG Yijun. Internet of things-oriented wireless sensor networks review[J].&, 2013, 35(1): 215-227. doi: 10.3724/ SP.J.1146.2012.00876.

[2] MAHBOUBI H. Distributed deployment algorithms for efficient coverage in a network of mobile sensors with nonidentical sensing Capabilities[J]., 2014, 63(8): 3998-4016.

[3] MAHBOUBI H, MOEZZI K, AGHDAM A G,. Distributed deployment algorithms for improved coverage in a network of wireless mobile sensors[J]., 2014, 10(1): 163-174.

[4] LEE H J, KIM Y H, HAN Y H,. Centroid-based movement assisted sensor deployment schemes in wireless sensor networks[C]. the IEEE 70th Vehicular Technology Conference Fall (VTC 2009-Fall), Anchorage, 2009: 20-23.

[5] CORTES J and BULLO F. Coordination and geometric optimization via distributed dynamical systems[J]., 2005, 44(5): 1543-1574.

[6] BARTOLINI N, BONGIOVANNI G, POTTA T L,. Voronoi-based deployment of mobile sensors in the face of adversaries[C]. 2014 IEEE International Conference on Communications (ICC), Sydney, 2014: 532-537.

[7] 方偉, 宋鑫宏. 基于Voronoi圖盲區(qū)的無線傳感器網(wǎng)絡(luò)覆蓋控制部署策略[J]. 物理學(xué)報, 2014, 63(22): 220701.

FANG Wei and SONG Xinhong. An coverage control

deployment strategy of wireless sensor networks based on blind-zone of voronoi diagram[J]., 2014, 63(22): 220701.

[8] BARTOLINI N, CALAMONERI T, LA PORTAT T F.. Autonomous deployment of heterogeneous mobile sensors[J]., 2011, 10(6): 753-766.

[9] IMAI H, IRI M, and MUROTA K. Voronoi diagram in the laguerre geometry and its applications[J]., 1985, 14(1): 93-105.

[10] MAHBOUBI H and AGHDAM A G. Distributed deployment strategies to increase coverage in a network of wireless mobile sensors[C]. Proceedings of 2013 American Control Conference (ACC), Washington, 2013: 17-19.

[11] LIN T Y, SANTOSO H A, and WU K R. Global sensor deployment and local coverage- aware recovery schemes for smart environments[J].,2015, 14(7): 1382-1396.

[12] KASHI S S and SHARIFI M. Coverage rate calculation in wireless sensor networks[J]., 2012, 94(11): 833-856.

[13] 杜曉玉, 孫力娟, 郭劍, 等. 異構(gòu)無線傳感器網(wǎng)絡(luò)覆蓋優(yōu)化算法[J]. 電子與信息學(xué)報, 2014, 36(3): 696-702. doi: 10.3724/ SP.J.1146.2013.00730.

DU Xiaoyu, SUN Lijuan, Guo Jian,. Coverage optimization algorithm for heterogeneous WSNs[J].&, 2014, 36(3): 696-702. doi: 10.3724/SP.J.1146.2013.00730.

[14] CORTES J, MARTINEZ S, KARATAS T,. Coverage control for mobile sensing networks[J]., 2004, 20(2): 243-255.

[15] NOJEONG H and VARSHNEY P K. An intelligent deployment and clustering algorithm for a distributed mobile sensor network[C]. 2003 IEEE International Conference on Systems, Man and Cybernetics, Washington, 2003, 5: 4576-4581.

Autonomous Deployment Algorithm in Mobile Heterogeneous Networks

QIN Ningning YU Yinghua WU De’en

(,,,214122,)

To solve the deployment problem of nodes with unbalanced sensing radiuses in mobile sensor network, an Autonomous Deployment Algorithm (ADA) based on the VL (Voronoi Laguerre) graph is proposed. First, the VL graph is used to divide the target area, the coverage tasks of target area are allocated among different sensor nodes. Then, the node assigned with coverage subinterval confirms its candidate target location in next round by structuring the VL controlled polygon. The node without sub-range calculates its virtual repulsion according to the geometrical position relationship with its neighbor nodes’ perception circles and the target area’s borders to ultimately ascertain the target point moving to. Each node in the network updates its position by rounds to improve the network coverage. The simulation results show ADA algorithm has obvious advantages in network coverage rate, deployment speed, nodes’ distribution uniformity and so on.

Mobile sensor network; VL (Voronoi Laguerre) graph; Controlled polygon; Coverage rate

TP393

A

1009-5896(2016)07-1838-05

10.11999/JEIT151063

2015-09-21；改回日期：2016-03-03；網(wǎng)絡(luò)出版：2016-04-26

秦寧寧 ningning801108@163.com

江蘇省“六大人才高峰”第十一批高層次人才項目(DZXX-026)，國家自然科學(xué)基金(61304264)，江蘇省產(chǎn)學(xué)研聯(lián)合創(chuàng)新資金前瞻性聯(lián)合研究項目(BY2014023-31)

The Eleventh Batch High-level Talents Project of “Six Talent Peaks” in Jiangsu Province (DZXX-026), The National Natural Science Foundation of China (61304264), Union Innovation Funds Prospective Joint Research Project in Jiangsu Province (BY2014023-31)

秦寧寧： 女，1980年生，副教授，碩士生導(dǎo)師，主要研究方向為無線傳感器網(wǎng)絡(luò)及應(yīng)用.

余穎華： 女，1989年生，碩士生，研究方向為無線傳感網(wǎng)覆蓋.

吳德恩： 男，1988年生，碩士生，研究方向為無線傳感網(wǎng)覆蓋.