.png){kind=icon}
返回
Efficient Algorithms for Max-Weighted Point Sweep Coverage on Lines
.png){kind=icon}
OA
AI
DOI：10.3390/s21041457.png)
.png){kind=icon}
.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
As an important application of wireless sensor networks (WSNs), deployment of mobile sensors to periodically monitor (sweep cover) a set of points of interest (PoIs) arises in various applications, such as environmental monitoring and data collection. For a set of PoIs in an Eulerian graph, the point sweep coverage problem of deploying the fewest sensors to periodically cover a set of PoIs is known to be Non-deterministic Polynomial Hard (NP-hard), even if all sensors have the same velocity. In this paper, we consider the problem of finding the set of PoIs on a line periodically covered by a given set of mobile sensors that has the maximum sum of weight. The problem is first proven NP-hard when sensors are with different velocities in this paper. Optimal and approximate solutions are also presented for sensors with the same and different velocities, respectively. For M sensors and N PoIs, the optimal algorithm for the case when sensors are with the same velocity runs in O(MN) time; our polynomial-time approximation algorithm for the case when sensors have a constant number of velocities achieves approximation ratio 1/2; for the general case of arbitrary velocities, 1/2 alpha and 1/2(1-1/e) approximation algorithms are presented, respectively, where integer alpha >= 2 is the tradeoff factor between time complexity and approximation ratio.
Keyword:
WSN
mobile sensors
sweep coverage
approximation algorithm
combinatorial mathematics
AI总结
对已上传原文的论文进行重点信息的提取，主要内容包括：简要概述、研究摘要、背景介绍、关键亮点、图文解析、展望与总结。
期刊
IF:
3.5
论文数:
7.2W
被引数:
20.9W
机构
引用论文
分享收藏Convetive heat transfer at the Soultz-sous-Forets Geothermal Site: implications for oil potential.png)
First Break
First BreakIF0
PREAI
分享收藏Cadmium exposure and the epigenome: Exposure-associated patterns of DNA methylation in leukocytes from mother-baby pairsEpigeneticsOAAI
EpigeneticsIF0
OAAI分享收藏Movement-Efficient Sensor Deployment in Wireless Sensor Networks With Limited Communication RangeOAAI
OAAI分享收藏
查看更多内容