Energy-Efficient K-Cover Problem in Hybrid Sensor Networks 3
proved that the maximum covers problem is NP-complete.
They also provide a heuristic to find the cover sets for full
coverage by minimizing the coverage of sparsely covered areas.
Zhang and Hou [16] present an optimal geographical density
control method, which is a decentralized and localized density
control scheme. It claims that if communication range is at
least twice the sensing range, then a complete coverage of
a convex area implies connectivity. In each round, it seeks a
minimal α-cover that maximizes the α-lifetime upper bound of
the remaining set of nodes. Abrams et al. [17] try to maximize
the coverage subject to a lifetime requirement K. They provide
three algorithms to solve this problem: random algorithm,
distributed greedy algorithm and global greedy algorithm. Wang
et al. [18] considered the K-cover problem in sensor network
as an N person card game and also as a potential game. They
analyze the effects of the initial strategies on the gaming results
and extend the optimality of Nash equilibrium in the coverage
game to a more general case.
Based on the above analysis, all of the formerly mentioned
algorithms have a negative assumption that sensing ranges of
sensor nodes are all same. Therefore, inspired by Ai et al. [5]
and Wang et al. [18], we introduce a KGT algorithm based on
the game theory, which is a purely distributed algorithm and
can fully consider the integration of energy cost and different
sensing range of various sensors.
3. NETWORK MODEL AND PROBLEM STATEMENT
3.1. Network model
We consider a typical hybrid sensor network organized with a
relatively high number of sensor nodes equipped with various
of sensors and only one sink node in the given field of interest.
The sensor nodes are deployed in the area randomly and
denoted as s = 1, 2 ,...,n. They are isomorphic with the
same initial energy and the same capacity of computation
and communication, meanwhile the links among them are
symmetrical. The sink node is a powerful data collection device,
which has sufficient energy and computation capability and
responsible for collecting all sensory data generated by sensor
nodes. Such a network is used in detecting different targets
by multiple sensors in the monitoring area. Different types of
sensors may have different sensing ranges while their coverage
area are modeled as disks or sectors in two dimensions. Any
point within the coverage area is assumed to be seen by the
sensor. For any type u sensor, we denote its sensing radius by
R
s
(u), while R
c
denotes the communication radius of all sensor
nodes. In order to maintain the whole network connectivity,
without loss of generality, we consider R
c
≥ 2R
s
(u).We assume
an event-driven application, where the energy consumption of a
node is from the sensing task in the active time. We also assume
that the network time is slotted and the energy consumed by an
active node in a slot is a constant e
s
.
Both the sensor nodes and the sink node are static and stay
in the same place once they are deployed. We also assume that
every sensor node knows its location and can obtain the location
of its neighbors through local communication. We focus only
on the communications between the sensor nodes and the sink
node, whereas the communications between the sink node and
devices outside the network are out of the scope of this paper.
3.2. Problem statement
Now we begin to formulate the problem. The hybrid sensor
network consists of a series of sensor nodes and one sink node.
To meet the requirement of monitoring multi-targets under
a complex environment, each sensor node is assumed to be
equipped with different types of sensors, such as thermal sensor,
humidity sensor, pressure sensor, light sensor and sonic sensor.
Different types of sensors have different sensing ranges. A
sensor is able to perform measurements only within its sensing
range. Even some of them can detect the objects only in an
angle range like a camera sensor. For the sake of simplicity, we
assume that the sensing range of each sensor can be modeled by
a sensing disk or sector with corresponding sensing radius. Once
sensor nodes are deployed, it is very important to determine
whether sufficient coverage exists in the monitoring area. We
consider the application with the constraint named K-cover
problem, where the K represents the number of node sets. It
means that at any given time, only one among these sets is
active. All sensor nodes selected in this set are awake, while the
remaining nodes are asleep to conserve energy. The set of active
nodes must also induce a connected communication topology
so that they can transmit data to the sink node.
K-cover strategies are often employed to decrease the
overlapped sensing area of each sensor while minimizing the
energy consumption. For a given deployment of sensor nodes, as
the parameter K increases, the lifetime of the network improves
at the expense of coverage performance [5]. Besides, given a
desired cover set K, how to select a minimal subset of nodes
to cover the monitoring area is a challenge task. Researches
on K-cover problem have assumed that each node belongs to
only one of the K disjoint cover sets. Their objective is to
maximize the average coverage of sensor nodes and the lifetime
of the network is proportional to the parameter K. However ,
more factors have to be considered in hybrid sensor networks.
Although joining one set can maximize the average coverage of
one type of sensors, the average coverage of other types may
be decreased. Especially some sensors with a smaller sensing
range may be more important for monitoring tasks. With a
comprehensive consideration of the different sensing ranges of
different types of sensors, our object is to design a distributed
algorithm that can be implemented in a distributed manner with
local information and low message complexity. Let s
i
be the
cover set chose by sensor node i, i.e. s
i
= j,j ∈ 1, 2,...,K.
Then, s = s
1
,s
2
,...,s
n
denotes a partition of n sensor nodes
into K cover sets. For each s, the coverage of all type u sensors
The Computer Journal, 2013
at Washington University in St. Louis on January 5, 2015http://comjnl.oxfordjournals.org/Downloaded from