Find in Library

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 <i>M</i> sensors and <i>N</i> PoIs, the optimal algorithm for the case when sensors are with the same velocity runs in <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>O</mi><mo>(</mo><mi>M</mi><mi>N</mi><mo>)</mo></mrow></semantics></math></inline-formula> time; our polynomial-time approximation algorithm for the case when sensors have a constant number of velocities achieves approximation ratio <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mfrac><mn>1</mn><mn>2</mn></mfrac></semantics></math></inline-formula>; for the general case of arbitrary velocities, <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mfrac><mn>1</mn><mrow><mn>2</mn><mi>α</mi></mrow></mfrac></semantics></math></inline-formula> and <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mfrac><mn>1</mn><mn>2</mn></mfrac><mrow><mo>(</mo><mn>1</mn><mo>−</mo><mn>1</mn><mo>/</mo><mi>e</mi><mo>)</mo></mrow></mrow></semantics></math></inline-formula> approximation algorithms are presented, respectively, where integer <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>α</mi><mo>≥</mo><mn>2</mn></mrow></semantics></math></inline-formula> is the tradeoff factor between time complexity and approximation ratio.