一種改進(jìn)的虛擬力重定位覆蓋增強(qiáng)算法

周非; 郭浩田; 楊伊

doi:10.11999/JEIT190662

一種改進(jìn)的虛擬力重定位覆蓋增強(qiáng)算法

doi: 10.11999/JEIT190662

重慶郵電大學(xué)通信與信息工程學(xué)院重慶 400065

基金項目: 國家自然科學(xué)基金(61471077)

詳細(xì)信息

作者簡介:
周非：男，1977年生，博士，教授，研究方向為無線定位、信號處理、圖像處理等

郭浩田：男，1994年生，碩士，研究方向為無線傳感網(wǎng)絡(luò)

楊伊：女，1992年生，碩士，研究方向為無線傳感網(wǎng)絡(luò)

通訊作者:
郭浩田　17784456880@163.com

中圖分類號: TN915.1; TP391.9
計量
- 文章訪問數(shù): 2711
- HTML全文瀏覽量: 883
- PDF下載量: 65
- 被引次數(shù): 0
出版歷程
- 收稿日期: 2019-08-30
- 修回日期: 2020-02-27
- 網(wǎng)絡(luò)出版日期: 2020-04-15
- 刊出日期: 2020-09-27

An Improved Virtual Force Relocation Coverage Enhancement Algorithm

School of Communication and Information Engineering,Chongqing University of Posts and Telecommunications, Chongqing 400065, China

Funds: The National Natural Science Foundation of China (61471077)

摘要

摘要: 在移動無線傳感網(wǎng)絡(luò)(MWSN)的部署問題中最關(guān)鍵的是如何提供最大的區(qū)域覆蓋范圍。針對現(xiàn)有的覆蓋控制算法存在覆蓋率不理想、部署效率低、能耗過高的問題，該文提出了一種高效部署策略。第1階段利用Voronoi圖獲得整個網(wǎng)絡(luò)的覆蓋孔，檢測Voronoi多邊形內(nèi)的未覆蓋區(qū)域，并提供虛擬力驅(qū)動傳感器移動，同時采用動態(tài)調(diào)整策略改變移動步長，從而減少能量損耗；第2階段提出一種檢測機(jī)制，利用Delaunay三角網(wǎng)檢測傳感器之間的局部覆蓋孔并進(jìn)行修復(fù)。仿真結(jié)果表明，該算法在提高網(wǎng)絡(luò)覆蓋率的同時加快了收斂速度，為部署移動無線傳感網(wǎng)絡(luò)提供了新的解決思路。
- 移動無線傳感網(wǎng) /
- 網(wǎng)絡(luò)覆蓋 /
- 虛擬力 /
- voronoi圖 /
- delaunay三角
Abstract: The most critical issue in the deployment of Mobile Wireless Sensor Networks (MWSN) is how to provide maximum regional coverage.To solve the problem that the existing coverage control algorithm has unsatisfactory coverage, low deployment efficiency and high energy consumption, an efficient deployment strategy is proposed.The first stage uses the Voronoi diagram to obtain the coverage hole of the entire network, and detects the uncovered area in the Voronoi polygon, and provides virtual force to drive the sensor movement, and uses the dynamic adjustment strategy to change the moving step size, thereby reducing energy loss;The second stage proposes a detection mechanism that uses a Delaunay triangulation to detect local coverage holes between sensors and repair them.The simulation results show that the algorithm accelerates the convergence speed while improving the network coverage, and provides a new solution for deploying mobile wireless sensor networks.
- Mobile Wireless Sensor Network (MWSN) /
- Network coverage /
- Virtual force /
- Voronoi graph /
- Delaunay triangle

HTML全文

圖 1 局部覆蓋孔

下載: 全尺寸圖片幻燈片

圖 2 基于形心傳感器移動示意圖

下載: 全尺寸圖片幻燈片

圖 3 基于虛擬力傳感器移動示意圖

下載: 全尺寸圖片幻燈片

圖 4 基于檢測機(jī)制漏洞修復(fù)示意圖

下載: 全尺寸圖片幻燈片

圖 5 傳感器運(yùn)動過程圖

下載: 全尺寸圖片幻燈片

圖 6 覆蓋率變化圖

下載: 全尺寸圖片幻燈片

圖 7 單次蒙特卡洛仿真覆蓋率變化曲線

下載: 全尺寸圖片幻燈片

圖 8 不同節(jié)點(diǎn)個數(shù)，4種算法性能對比圖

下載: 全尺寸圖片幻燈片

表 1 基于Voronoi圖的虛擬力重定位算法

　Randomly deploy N sensors in the monitoring area;

　Repeat

　Construct Voronoi polygons based on the position of the
　sensors;

　　For each $i{\rm{ (} }1 \le i \le N)$

　　　For each $j{\rm{ } }(1 \le j \le {\rm{vertex(} }i\rm{)})$// vertex: the number of
　　　Voronoi polygon vertices;

　　　　If ${{\rm dist(} }i,j{) < }{R_s}$ //case 1: Voronoi polygon vertices are
　　　　all covered;

　　　　　Calculate the force of the centroid on the sensor and
　　　　　the position of the sensor;

　　　　Else //case 2: Voronoi polygon vertices are not all
　　　　covered;

　　　　　Calculate ${F_{\rm{uncov}}}$ and the position of the sensor at the
　　　　　next moment;// ${F_{\rm{uncov}}}$:the force of the uncovered grid
　　　　　point on the sensor;

　　　　　End for

　　　Sensor location update;

　　End for

　Until termination criterion is met

下載: 導(dǎo)出CSV

表 2 基于Delaunay三角的局部覆蓋空洞修復(fù)算法

　Construct a Delaunay triangulation based on the position of the
　sensors;

　For each $j{\rm{ } }(1 \le j \le {\rm{TRI} }\left( i \right))$// TRI: the number of Delaunay
　triangles

　　　Calculate empty circle center coordinates and radius;

　　　If there is a gap between the sensors:

　　　　Calculate the force of the centroid of the empty circle on
　　　　the sensor and the position of the sensor circle on the
　　　　sensor;

　　　　If ${\rm{fitness} }(x(t)) \ge {\rm{fitness} }(x(t - {\rm{1} }))$

　　　　　Sensor location update;

　　　　　Break;

　　　Else

　　　　　Sensor position unchanged;

　　　End if

　End for

下載: 導(dǎo)出CSV

參考文獻(xiàn)(16)

YUE Yinggao and HE Ping. A comprehensive survey on the reliability of mobile wireless sensor networks: Taxonomy, challenges, and future directions[J]. Information Fusion, 2018, 44: 188–204. doi: 10.1016/j.inffus.2018.03.005

ETANCELIN J M, FABBRI A, GUINAND F, et al. DACYCLEM: A decentralized algorithm for maximizing coverage and lifetime in a mobile wireless sensor network[J]. Ad Hoc Networks, 2019, 87: 174–187. doi: 10.1016/j.adhoc.2018.12.008

HACIOGLU G, KAND V F A, and SESLI E. Multi objective clustering for wireless sensor networks[J]. Expert Systems with Applications, 2016, 59: 86–100. doi: 10.1016/j.eswa.2016.04.016

ALIA O M and Al-AJOURI A. Maximizing wireless sensor network coverage with minimum cost using harmony search algorithm[J]. IEEE Sensors Journal, 2017, 17(3): 882–896. doi: 10.1109/jsen.2016.2633409

ABO-ZAHHAD M, SABOR N, SASAKI S, et al. A centralized immune-Voronoi deployment algorithm for coverage maximization and energy conservation in mobile wireless sensor networks[J]. Information Fusion, 2016, 30: 36–51. doi: 10.1016/j.inffus.2015.11.005

XU Ying, DING Ou, QU Rong, et al. Hybrid multi-objective evolutionary algorithms based on decomposition for wireless sensor network coverage optimization[J]. Applied Soft Computing, 2018, 68: 268–282. doi: 10.1016/j.asoc.2018.03.053

ROUT M and ROY R. Dynamic deployment of randomly deployed mobile sensor nodes in the presence of obstacles[J]. Ad Hoc Networks, 2016, 46: 12–22. doi: 10.1016/j.adhoc.2016.03.004

MAHBOUBI H and AGHDAM A G. Distributed deployment algorithms for coverage improvement in a network of wireless mobile sensors: Relocation by virtual force[J]. IEEE Transactions on Control of Network Systems, 2017, 4(4): 736–748. doi: 10.1109/TCNS.2016.2547579

HABIBI J, MAHBOUBI H, and AGHDAM A G. A gradient-based coverage optimization strategy for mobile sensor networks[J]. IEEE Transactions on Control of Network Systems, 2017, 4(3): 477–488. doi: 10.1109/TCNS.2016.2515370

LEE H J, KIM Y H, HAN Y H, et al. Centroid-Based movement assisted sensor deployment schemes in wireless sensor networks[C]. The 70th Vehicular Technology Conference Fall, Anchorage, USA, 2009. doi: 10.1109/VETECF.2009.5379087.

FANG Wei, SONG Xinhong, WU Xiaojun, et al. Novel efficient deployment schemes for sensor coverage in mobile wireless sensor networks[J]. Information Fusion, 2018, 41: 25–36. doi: 10.1016/j.inffus.2017.08.001

BARTOLINI N, BONGIOVANNI G, PORTA T L, et al. Voronoi-based deployment of mobile sensors in the face of adversaries[C]. 2014 IEEE International Conference on Communications, Sydney, Australia, 2014: 532–537. doi: 10.1109/ICC.2014.6883373.

QIU Chenxi and SHEN Haiying. A delaunay-based coordinate-free mechanism for full coverage in wireless sensor networks[J]. IEEE Transactions on Parallel and Distributed Systems, 2014, 25(4): 828–839. doi: 10.1109/TPDS.2013.134

LI Wei and ZHANG Wei. Coverage hole and boundary nodes detection in wireless sensor networks[J]. Journal of Network and Computer Applications, 2015, 48: 35–43. doi: 10.1016/j.jnca.2014.10.011

JOSHITHA K L and JAYASHRI S. A novel redundant hole identification and healing algorithm for a homogeneous distributed Wireless Sensor Network[J]. Wireless Personal Communications, 2019, 104(4): 1261–1282. doi: 10.1007/s11277-018-6079-5

SO-IN C, NGUYEN T G, and NGUYEN N G. An efficient coverage hole-healing algorithm for area-coverage improvements in mobile sensor networks[J]. Peer-to-Peer Networking and Applications, 2019, 12(3): 541–552. doi: 10.1007/s12083-018-0675-8

相關(guān)文章

施引文獻(xiàn)

資源附件(0)

訪問統(tǒng)計