Minimizing the total cost of barrier coverage in a linear domain

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journalNot applicablepeer-review

View graph of relations

Author(s)

  • Xiao Zhang
  • Haosheng Fan
  • Yingchao Zhao
  • Chuang Liu

Related Research Unit(s)

Detail(s)

Original languageEnglish
Pages (from-to)434–457
Journal / PublicationJournal of Combinatorial Optimization
Volume36
Issue number2
Early online date16 May 2018
Publication statusPublished - Aug 2018

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 R = (r1r2,..., rn) of sensors such that the line interval or circle is fully covered and its total cost C(R) = ∑ni=1 riα 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(n2) time, while the other is a fully polynomial time approximation scheme (FPTAS) of computational complexity O(n2/ε). For the circle case, we optimally solve it when α = 1 and present a 2(π/2)α-approximation algorithm when α > 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.

Research Area(s)

  • Approximation algorithm, Barrier coverage, Range assignment, Wireless sensor networks

Citation Format(s)

Minimizing the total cost of barrier coverage in a linear domain. / Zhang, Xiao; Fan, Haosheng; Lee, Victor C. S.; Li, Minming; Zhao, Yingchao; Liu, Chuang.

In: Journal of Combinatorial Optimization, Vol. 36, No. 2, 08.2018, p. 434–457.

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journalNot applicablepeer-review