Maximizing Barrier Coverage Lifetime with Mobile Sensors

DOI10.1137/16M1071031zbMATH Open1370.68327arXiv1304.6358MaRDI QIDQ5346541FDOQ5346541

Authors: Amotz Bar-Noy, Peter Terlecky, Dror Rawitz 

Publication date: 24 May 2017

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Abstract: Sensor networks are ubiquitously used for detection and tracking and as a result covering is one of the main tasks of such networks. We study the problem of maximizing the coverage lifetime of a barrier by mobile sensors with limited battery powers, where the coverage lifetime is the time until there is a breakdown in coverage due to the death of a sensor. Sensors are first deployed and then coverage commences. Energy is consumed in proportion to the distance traveled for mobility, while for coverage, energy is consumed in direct proportion to the radius of the sensor raised to a constant exponent. We study two variants which are distinguished by whether the sensing radii are given as part of the input or can be optimized, the fixed radii problem and the variable radii problem. We design parametric search algorithms for both problems for the case where the final order of the sensors is predetermined and for the case where sensors are initially located at barrier endpoints. In contrast, we show that the variable radii problem is strongly NP-hard and provide hardness of approximation results for fixed radii for the case where all the sensors are initially co-located at an internal point of the barrier.

Full work available at URL: https://arxiv.org/abs/1304.6358

Recommendations

• Maximizing barrier coverage lifetime with mobile sensors
• Maximizing barrier coverage lifetime with static sensors
• Maximizing Barrier Coverage Lifetime with Static Sensors
• New Algorithms for Barrier Coverage with Mobile Sensors
• Distributed barrier coverage with relocatable sensors
• ``Green barrier coverage with mobile sensors
• ``Green barrier coverage with mobile sensors

zbMATH Keywords

approximation algorithmssensor networksnetwork lifetimemobile sensorsbarrier coveragesensor deployment

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)

Cites Work

• Title not available (Why is that?)
• Covering a line segment with variable radius discs
• Title not available (Why is that?)
• Optimal movement of mobile sensors for barrier coverage of a planar region
• New Algorithms for Barrier Coverage with Mobile Sensors
• Decomposing coverings and the planar sensor cover problem
• Set it and forget it: approximating the set once strip cover problem
• Changing of the guards: strip cover with duty cycling
• Average case network lifetime on an interval with adjustable sensing ranges
• ``Green barrier coverage with mobile sensors

Cited In (8)

• ``Green barrier coverage with mobile sensors
• ``Green barrier coverage with mobile sensors
• Maximizing barrier coverage lifetime with mobile sensors
• Minimizing the total cost of barrier coverage in a linear domain
• Patrolling a barrier with a network of mobile sensors
• New Algorithms for Barrier Coverage with Mobile Sensors
• Maximizing Barrier Coverage Lifetime with Static Sensors
• Maximizing barrier coverage lifetime with static sensors

This page was built for publication: Maximizing Barrier Coverage Lifetime with Mobile Sensors

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5346541)