@inproceedings{4c6e3c235aa74a0f9ec9799a6689b84f,
title = "Optimal k-support coverage paths in wireless sensor networks",
abstract = "Coverage is a fundamental problem in wireless sensor networks since sensors may be spread in arbitrary manner. In this paper, we addressed the k-support coverage problem. Most of the existing works assume that the coverage degree is 1, i.e. every point in a certain path falls within the sensing range of at least one sensor node. In this work, we focus on the case when we require that every point on the path is covered by at least k sensors, while optimizing certain objectives. We give an optimal polynomial-time algorithm and prove that the time complexity of our algorithm is O(k2n2). To the best of our knowledge, this is the first polynomial time algorithm finding an optimum k coverage path in sensor networks with general sensing radius and general k.",
author = "Shaoiie Tang and Mao, \{Xu Fei\} and Li, \{Xiang Yang\}",
year = "2009",
doi = "10.1109/PERCOM.2009.4912843",
language = "English",
isbn = "9781424433049",
series = "7th Annual IEEE International Conference on Pervasive Computing and Communications, PerCom 2009",
publisher = "IEEE Computer Society",
booktitle = "7th Annual IEEE International Conference on Pervasive Computing and Communications, PerCom 2009",
address = "United States",
note = "7th Annual IEEE International Conference on Pervasive Computing and Communications, PerCom 2009 ; Conference date: 09-03-2009 Through 13-03-2009",
}