1
Efficient k-Coverage Algorithms for Wireless
Sensor Networks
Mohamed Hefeeda, Member, IEEE, and Majid Bagheri
Abstract— We propose new algorithms to achieve k-coverage
in dense sensor networks. In such networks, covering sensor
locations approximates covering the whole area. However, it has
been shown before that selecting the minimum set of sensors to
activate from an already deployed set of sensors is NP-hard. We
propose an efficient approximation algorithm which achieves a
solution of size within a logarithmic factor of the optimal. We
prove that our algorithm is correct and analyze its complexity.
We implement our algorithm and compare it against two others
in the literature. Our results show that the logarithmic factor
is only a worst-case upper bound and the solution size is close
to the optimal in most cases. A key feature of our algorithm
is that it can be implemented in a distributed manner with
local information and low message complexity. We design and
implement a fully distributed version of our algorithm. Our
distributed algorithm does not require that sensors know their
locations. Comparison with two other distributed algorithms in
the literature indicates that our algorithm: (i) converges much
faster than the others, (ii) activates near-optimal number of
sensors, and (iii) significantly prolongs (almost doubles) the
network lifetime because it consumes much less energy than the
other algorithms.
Index Terms— Sensor Networks, Coverage Protocols, K-
coverage Protocols
I. INTRODUCTION
Mass production of sensor devices with low cost enables
the deployment of large-scale sensor networks for real-life
applications such as forest fire detection and vehicle traffic
monitoring. A fundamental issue in such applications is the
quality of monitoring provided by the network. This quality is
usually measured by how well deployed sensors cover a target
area. In its simplest form, coverage means that every point in
the target area is monitored by, i.e., within the sensing range
of, at least one sensor. This is c