秦寧寧 余穎華 吳德恩

?

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

秦寧寧*余穎華 吳德恩

(江南大學(xué)輕工過(guò)程先進(jìn)控制教育部重點(diǎn)實(shí)驗(yàn)室 無(wú)錫 214122)

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

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

1 引言

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

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

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

2 基本知識(shí)

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

2.2 VL圖

圖1 VL圖劃分

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

3 ADA算法

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

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

3.1.1 節(jié)點(diǎn)候選位置

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

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

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

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

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

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

3.3 ADA算法步驟

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

表1 ADA算法

4 仿真實(shí)驗(yàn)

4.1 覆蓋率

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

圖4 ADA和簡(jiǎn)化ADA算法下的某次部署過(guò)程

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

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

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

4.2 快速性

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

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

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

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

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

5 總結(jié)

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

參 考 文 獻(xiàn)

[1] 錢志鴻, 王義君. 面向物聯(lián)網(wǎng)的無(wú)線傳感器網(wǎng)絡(luò)綜述[J]. 電子與信息學(xué)報(bào), 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ú)線傳感器網(wǎng)絡(luò)覆蓋控制部署策略[J]. 物理學(xué)報(bào), 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ú)線傳感器網(wǎng)絡(luò)覆蓋優(yōu)化算法[J]. 電子與信息學(xué)報(bào), 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

江蘇省“六大人才高峰”第十一批高層次人才項(xiàng)目(DZXX-026)，國(guó)家自然科學(xué)基金(61304264)，江蘇省產(chǎn)學(xué)研聯(lián)合創(chuàng)新資金前瞻性聯(lián)合研究項(xiàng)目(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)師，主要研究方向?yàn)闊o(wú)線傳感器網(wǎng)絡(luò)及應(yīng)用.

余穎華： 女，1989年生，碩士生，研究方向?yàn)闊o(wú)線傳感網(wǎng)覆蓋.

吳德恩： 男，1988年生，碩士生，研究方向?yàn)闊o(wú)線傳感網(wǎng)覆蓋.