Minimizing the total cost of barrier coverage in a linear domain
Lists
Only you see this
Abstract
Barrier coverage, as one of the most important applications of wireless sensor network (WSNs), is to provide coverage for the boundary of a target region. We study the barrier coverage problem by using a set of n sensors with adjustable coverage radii deployed along a line interval or circle. Our goal is to determine a range assignment $$\mathbf {R}=({r_{1}},{r_{2}}, \ldots , {r_{n}})$$ R = ( r 1 , r 2 , … , r n ) of sensors such that the line interval or circle is fully covered and its total cost $$C(\mathbf {R})=\sum _{i=1}^n {r_{i}}^\alpha $$ C ( R ) = ∑ i = 1 n r i α is minimized. For the line interval case, we formulate the barrier coverage problem of line-based offsets deployment, and present two approximation algorithms to solve it. One is an approximation algorithm of ratio 4 / 3 runs in $$O(n^{2})$$ O ( n 2 ) time, while the other is a fully polynomial time approximation scheme (FPTAS) of computational complexity $$O(\frac{n^{2}}{\epsilon })$$ O ( n 2 ϵ ) . For the circle case, we optimally solve it when $$\alpha = 1$$ α = 1 and present a $$2(\frac{\pi }{2})^\alpha $$ 2 ( π 2 ) α -approximation algorithm when $$\alpha > 1$$ α > 1 . Besides, we propose an integer linear programming (ILP) to minimize the total cost of the barrier coverage problem such that each point of the line interval is covered by at least k sensors.
BibTeX
@article{zhang2018minimizing,
author = {Xiao Zhang and Haosheng Fan and Victor C. S. Lee and Minming Li and Yingchao Zhao and Chuang Liu},
title = {{Minimizing the total cost of barrier coverage in a linear domain}},
journal = {J. Comb. Optim.},
year = {2018},
url = {https://openreview.net/forum?id=Uk6bvGjXOwU},
}Loading related content...