Barrier coverage by sensors with adjustable ranges

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journal

22 Scopus Citations
View graph of relations

Author(s)

  • Haosheng Fan
  • Minming Li
  • Xianwei Sun
  • Peng-Jun Wan
  • Yingchao Zhao

Related Research Unit(s)

Detail(s)

Original languageEnglish
Article number14
Journal / PublicationACM Transactions on Sensor Networks
Volume11
Issue number1
Online published7 Nov 2014
Publication statusPublished - Nov 2014

Abstract

One of the most fundamental tasks of wireless sensor networks is to provide coverage of the deployment region. We study the coverage of a line interval with a set of wireless sensors with adjustable coverage ranges. Each coverage range of a sensor is an interval centered at that sensor whose length is decided by the power the sensor chooses. The objective is to find a range assignment with the minimum cost. There are two variants of the optimization problem. In the discrete variant, each sensor can only choose from a finite set of powers, whereas in the continuous variant, each sensor can choose power from a given interval. For the discrete variant of the problem, a polynomial-time exact algorithm is designed. For the continuous variant of the problem, NP-hardness of the problem is proved and followed by an ILP formulation. Then, constant-approximation algorithms are designed when the cost for all sensors is proportional to rκfor some constant κ ≥ 1, where r is the covering radius corresponding to the chosen power. Specifically, if κ = 1, we give a 1.25-approximation algorithm and a fully polynomial-time approximation scheme; if κ > 1, we give a 2-approximation algorithm. We also show that the approximation analyses are tight.

Research Area(s)

  • Approximation algorithms, Barrier coverage, Wireless sensor networks

Citation Format(s)

Barrier coverage by sensors with adjustable ranges. / Fan, Haosheng; Li, Minming; Sun, Xianwei; Wan, Peng-Jun; Zhao, Yingchao.

In: ACM Transactions on Sensor Networks, Vol. 11, No. 1, 14, 11.2014.

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journal