On Minimizing the Maximum Sensor Movement for Barrier Coverage of a Line Segment

被引：0

作者：

Czyzowicz, J. ^{[1
]}

Kranakis, E. ^{[2
]}

Krizanc, D. ^{[3
]}

Lambadaris, I. ^{[4
]}

Narayanan, L. ^{[5
]}

Opatrny, J. ^{[5
]}

Stacho, L. ^{[6
]}

Urrutia, J. ^{[7
]}

Yazdani, M. ^{[4
]}

机构：

[1] Univ Quebec Outaouais, Dept Informat, Gatineau, PQ J8X 3X7, Canada

[2] Carleton Univ, Sch Comp Sci, Ottawa, ON K1S 5B6, Canada

[3] Wesleyan Univ, Dept Math & Comp Sci, Middletown, CT 06459 USA

[4] Carleton Univ, Dept Syst & Comp Engn, Ottawa, ON K1S 5B6, Canada

[5] Concordia Univ, Dept Comp Sci, Montreal, PQ H3G 1M8, Canada

[6] Simon Fraser Univ, Dept Math, Burnaby, BC V5A 1S6, Canada

[7] Univ Nacl Autonoma Mexico, Inst Matemat, Area Invest Cientif Circuito Exterior, Mexico City 04510, DF, Mexico

来源：

AD-HOC, MOBILE AND WIRELESS NETWORKS, PROCEEDINGS | 2009年 / 5793卷

基金：

加拿大自然科学与工程研究理事会;

关键词：

Barriet Coverage; Detection; Intruder; Line Segment; Optimal Movement; Sensors; NP-complete; PTAS;

D O I：

暂无

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

We consider n mobile sensors located on a line containing a barrier represented by a finite line segment Sensors form a Wireless Sensor network and are able to move within the line An intruder traversing the barrier can be detected only when it is within the sensing range of at least one sensor The sensor network establishes barrier coverage of the segment if no intruder can penetrade the barrier from any direction in the plane without being detected Starting from arbitrary initial positions of sensors oil the line we are interested in finding final positions of sensors that establish barrier coverage and minimize the maximum distance traversed by any sensor We distinguish Several Variants of the problem, based on (a) whether or not the sensors have identical ranges (b) whether or not complete coverage is possible and (c) in the case when complete coverage is impossible, whether or not the maximal cover age is required to be contiguous For the owe or n sensors identical range, When complete coverage is impossible, we give linear tune optimal algorithms that achieve maximal coverage: both for the contigous and non-contigous case. when Complete coverage is possible, we give an O(n(2)) algorithin for an optimal solution a linear time approximation scheme with approximation factor 2 and a, (1 + c) PTAS When the sensors have unequal ranges we show that a variation of the problem is NP-complete and identify some instances Much can be solved will our algorithms for sensors with unequal ranges

引用

页码：194 / +

页数：4