Minimizing the total cost of barrier coverage in a linear domain |
| |
Authors: | Xiao Zhang Haosheng Fan Victor C S Lee Minming Li Yingchao Zhao Chuang Liu |
| |
Affiliation: | 1.Department of Computer Science,City University of Hong Kong,Hong Kong SAR,China;2.Department of Marketing,Hong Kong University of Science and Technology,Hong Kong SAR,China;3.Department of Computer Science,Caritas Institute of Higher Education,Hong Kong SAR,China;4.Department of Computer Science and Technology, Harbin Institute of Technology Shenzhen Graduate School,Shenzhen Key Laboratory of Internet Information Collaboration,Shenzhen,China |
| |
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}})\) 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 \) 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})\) time, while the other is a fully polynomial time approximation scheme (FPTAS) of computational complexity \(O(\frac{n^{2}}{\epsilon })\). For the circle case, we optimally solve it when \(\alpha = 1\) and present a \(2(\frac{\pi }{2})^\alpha \)-approximation algorithm when \(\alpha > 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. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|