02-05-2013, 03:52 PM
Using Rotatable and Directional (R&D) Sensors to Achieve Temporal Coverage of Objects and Its Surveillance Application
Using Rotatable and Directional.pdf (Size: 2.15 MB / Downloads: 19)
Abstract
Due to hardware design or cost consideration, sensors may possess sector-like sensing coverage. Furthermore, by
stepper motors, sensors can rotate to cover the objects around them. This type of sensors are called rotatable and directional (R&D)
sensors. Through rotation, R&D sensors provide temporal coverage to objects by “periodically” detecting their existence. In the paper,
we first develop an event-driven surveillance system by R&D sensors, where objects are monitored by the sensors equipped with
infrared detectors and cameras. When an object is taken away, the sensor monitoring the object reports a warning message along with
detailed snapshots from the surroundings. Then, motivated by the system, we formulate an R&D sensor deployment problem, which
tries to deploy the minimum number of R&D sensors to cover a given set of objects such that each object is covered by 0 < 1 ratio
of time in every frame. We show this problem to be NP-hard and propose two efficient heuristics. The maximum covering deployment
(MCD) heuristic iteratively deploys a sensor to cover more objects, and performs well when objects congregate together. The diskoverlapping
deployment (DOD) heuristic deploys sensors to cover the joint sectors of overlapped disks, so it works better when objects
are arbitrarily placed in the sensing field. The paper contributes in defining a new temporal coverage model by R&D sensors,
developing a surveillance application for this model, and proposing efficient heuristics to reduce the deployment cost.
INTRODUCTION
WIRELESS sensor networks (WSNs) are characterized by
ad hoc networking, cooperative sensing, and distributed
processing. They are widely adopted in various
military and civil applications [1]. Sensors need to organize
a connected network that covers a sensing field or specific
point-locations to make the WSN function well. Conventional
research on WSNs usually assumes omnidirectional
sensors with disk-like sensing coverage [2]. However, due
to hardware design or cost consideration, sensors may
possess sector-like sensing coverage, which we call directional
sensors. Practical examples include infrared, camera,
and ultrasonic sensors. By integrating directional sensors
with robotic actuators, such as stepper motors, these
sensors can rotate to provide spatiotemporal monitoring
of the environment [3]. We call the sensors with such
capability rotatable and directional (R&D) sensors.
Sensing Coverage Issues
Conventional research on sensing coverage usually focuses
on full coverage in regular regions such as a rectangle. Most
studies aim at the k-coverage problem whose goal is to activate
a subset of sensors to make every location in the sensing field
be monitored by at least k sensors. Solutions for omnidirectional
sensors [12], [13] and directional sensors [14] have
been developed. In addition, Kumar et al. [15] propose
barrier coverage for long-thin belt regions, where a belt region
is said to be k-barrier covered by an omnidirectional WSN if all
crossing paths through the region are k-covered. Since
barrier coverage focuses on crossing paths in belt regions,
existing solutions of the k-coverage problem may not be
directly applied. The result of barrier coverage is also
extended to directional sensors [16].
RELATED WORK
The subjects of sensing coverage and network deployment in
WSNs have been widely studied. Below, we first discuss the
sensing coverage issues, and then review the deployment
schemes in both omnidirectional and directional WSNs.
Sensing Coverage Issues
Conventional research on sensing coverage usually focuses
on full coverage in regular regions such as a rectangle. Most
studies aim at the k-coverage problem whose goal is to activate
a subset of sensors to make every location in the sensing field
be monitored by at least k sensors. Solutions for omnidirectional
sensors [12], [13] and directional sensors [14] have
been developed. In addition, Kumar et al. [15] propose
barrier coverage for long-thin belt regions, where a belt region
is said to be k-barrier covered by an omnidirectional WSN if all
crossing paths through the region are k-covered. Since
barrier coverage focuses on crossing paths in belt regions,
existing solutions of the k-coverage problem may not be
directly applied. The result of barrier coverage is also
extended to directional sensors [16].
Deployment Schemes in Directional WSNs
Given a set of static targets, Ai and Abouzeid [41] consider a
maximum coverage with minimum sensors problem whose goal
is to activate the minimum number of directional sensors to
cover the maximum number of targets. This problem is
formulated by integer linear programming and a greedy
strategy by selecting sensors to cover more objects is
proposed. Assuming that directional sensors can switch to
specific directions, Cai et al. [42] organize the directions of
sensors into multiple cover sets, where in each cover set all
targets are covered by the corresponding sensors. Then, a
cover set is selected (and the corresponding sensors are
activated) in each period to extend the network lifetime. Ma
and Liu [43] consider that sensors have directional sensing
and communication ranges and model the WSN by a directed
communication graph to check the connectivity among
sensors. Assuming that directional sensors can only rotate
within a constrained angle and the network has a subset of
anchor sensors with known positions, Lee [6] considers a
localization problem to calibrate the positions of nonanchor
sensors. Each sensor measures the relative ranges from
other sensors and compensates the confined field of view by
rotating. However, these studies do not consider the R&D
sensor deployment problem.
THE PROPOSED SENSOR DEPLOYMENT
HEURISTICS
Our idea is to first calculate disks to cover all objects and
then select a subset of disks to deploy with R&D sensors
such that all objects are -time covered. We propose two
heuristics, where MCD suggests deploying sensors on the
disks that cover more objects, while DOD exploits disk
overlap by deploying sensors to cover joint sectors. Then,
we add the minimum number of relay nodes to maintain
the network connectivity.
Disk-Overlapping Deployment Heuristic
When objects are arbitrarily placed in the sensing field, each
sector may cover only few objects. In this case, each disk
requires more sectors to cover its objects and thus we may
need to deploy multiple sensors on each of most disks.
Therefore, the efficiency of MCD may degrade. To handle
this case, we propose DOD whose idea is to exploit disk
overlap to save sensors. Fig. 7 gives an example, where
¼ 0:5. Both disks da and db are divided into more than two
sectors but a sensor can cover only two sectors. Thus, MCD
deploys totally four sensors at sa and sb to cover all objects.
However, since sectors A, B, and E overlap with each other,
we can use one sensor to cover their objects. Specifically, we
deploy one sensor at si to cover the objects in sectors A, B,
and E, one sensor at sa to cover sectors C and D, and one
sensor at sb to cover sectors F and G, which totally requires
only three sensors. Here, sectors A, B, and E are called joint
sectors since they can be “jointly” covered by one disk.