DYNAMIC SENSOR NETWORKS:
AN APPROACH TO OPTIMAL DYNAMIC FIELD COVERAGE
Simone Gabriele and Paolo Di Giamberardino
Dipartimento di Informatica e Sistemistica ”Antonio Ruberti”
Universit
`
a degli Studi di Roma ”La Sapienza”
Via Eudossiana 18, Roma, Italia
Keywords:
Sensor network, dynamic configuration, optimal motion.
Abstract:
In the paper a solution to the sensor network coverage problem is proposed, based on the usage of moving
sensors that allow a larger fields coverage using a smaller number of devices. The problem than moves from
the optimal allocation of fixed or almost fixed sensors to the determination of optimal trajectories for moving
sensors. In the paper a suboptimal solution obtained from the sampled optimal problem is given. First, in
order to put in evidence the formulation and the solution approach to the optimization problem, a single
moving sensor has been addressed. Then, the results for multisensor systems are shown. Some simulation
results are also reported to show the behavior of the sensors network.
1 INTRODUCTION
Distributed sensors systems and networks are grow-
ing relevance in the scientific and engineering com-
munity. Their introduction into several applications
for monitoring or surveillance, like for example tem-
perature, ground humidity and solar radiation in farms
or parks, presence and distribution of people in criti-
cal structures, temperature for fire prevention (build-
ings as well as woods), and so on, together with the
growth of decentralized control in large and com-
plex structures (factories, refineries, energy produc-
tion and distribution, etc) makes the interest of many
researchers for these kind of problems growing and
growing, as proved for example by (Akyildiz et al.,
2002; Lewis, 2004).
The use of several sensors, suitably deployed,
makes the range of measurements as wide as required.
Then, one common features required by sensor net-
works is the full coverage of a given (large) area
with the union of each single field of measurement.
This problem has been usually faced studying opti-
mal, suboptimal or heuristic solutions to the coverage
problem in terms of good allocation of sensors in the
area under measurement. In other terms, the prob-
lem usually has been posed answering the question
””which are the best places to put the N sensors?”,
where best is often considered with respect to ener-
getic costs (for the deployment as well as for the com-
munications) or number of sensors.
Such a problem has been well studied in a lot of
works, such as (V. Isler and Daniilidis, 2004; Yung-
Tsung Hou, 2006; Zou and Chakrabarty, 2004; Lin,
2005; Huang and Tseng, 2005; Meguerdichian et al.,
2001).
In (Tan et al., 2004; Howard, 2002) the problem of
self-deploying mobile sensors, able to configure ac-
cording to the environment, is addressed and some
solutions are proposed. In these kind of approaches
a common fact is the use of a lot of quasi static sensor
units to cover a given area.
An alternative idea is to use a reduced number of
sensor units moving continuously; such an approach
is the one followed by the authors in the present work.
A result based on the solution of a suitable coordi-
nated optimal control problem is presented in the se-
quel. The only limit of this approach is the impos-
sibility of getting a continuous measure for a given
point of the area under monitoring, allowing the user
only to fix the maximum acceptable time between two
consecutive measures of the same point. The problem
is than to plan trajectories optimally in sense of area
coverage. An optimal control formulation for this
problem is proposed in (Wang, 2003). In (Tsai, 2004;
237
Gabriele S. and Di Giamberardino P. (2007).
DYNAMIC SENSOR NETWORKS: AN APPROACH TO OPTIMAL DYNAMIC FIELD COVERAGE.
In Proceedings of the Fourth International Conference on Informatics in Control, Automation and Robotics, pages 237-242
DOI: 10.5220/0001631202370242
Copyright
c
SciTePress
Cecil and Marthler, 2006) the same problem has been
studied in the level set framework and some subop-
timal solutions are proposed. An approach based on
space decomposition and Voronoy graphs is proposed
in (Acar et al., 2006).
In the present work we suggest a customizable op-
timal control framework that allow the study of a set
of different case of the described problem.
The motion problem both for a single sensor and
for a set of sensors, under kinematic and dynamic
constraints on the motion, with the objective to maxi-
mize the area covered during the movement is formu-
lated as an optimal control problem Since this prob-
lem, in the general case, cannot be solved analyti-
cally, a discretization of space and time is performed,
so obtaining a discrete time optimal control problem
tractable as a Non Linear Programming (NLP) one.
Similar approach to optimal control problems was
proposed for industrial manipulators control in (Bic-
chi and Tonietti, 2004) and for path planning in (Ma
and Miller, 2006).
The paper is organized as follows. In Section 2
the mathematical model of the sensor(s) is given, to-
gether with the constraints to be satisfied. Model and
constraints are then used to propose a formulation for
the optimal control problem. In Section 3 the discrete
problem, obtained by spatial and temporal discretiza-
tion, is formulated in terms of a solvable NLP prob-
lem. Section 4 is devoted to the particularization of
the problem for some cases, showing the respective
simulation results. Some final comments in Section 5
end the paper.
2 PROBLEM FORMULATION
2.1 The Mathematical Model
A mobile sensor is modeled, from the dynamic point
of view, as a material point of unitary mass, moving
on a space W ⊂ IR
2
, called the workspace, under the
action of two independent control input forces named
u
1
(t) and u
2
(t). Then, the position of the sensor in
W at time t is described by its Cartesian coordinates
(x
1
(t), x
2
(t)). The motion satisfies the well known
equations:
¨x
1
(t) = u
1
(t)
¨x
2
(t) = u
2
(t)
(1)
The linearity of 1 allows one to write the dynamics
in the form
˙z(t) = Az(t) + Bu(t)
y(t) = Cz(t)
(2)
where
A =
0 0 0 0
1 0 0 0
0 0 0 0
0 0 1 0
B =
1 0
0 0
0 1
0 0
C =
0 1 0 0
0 0 1 0
once the state vector z(t) =
˙x
1
(t), x
1
(t), ˙x
2
(t), x
2
(t)
T
and the output
y(t) =
x
1
(t), x
2
(t)
T
are defined. Clearly,
y(t) denotes the trajectory followed by the mobile
sensor.
If the workspace M is supposed to be a rectangu-
lar subset of IR
2
, the trajectory must satisfy the con-
straints
x
1,min
≤ x
1
(t) ≤ x
1,max
x
2,min
≤ x
2
(t) ≤ x
2,max
Moreover, physical limits on the actuators (for the
motion) and/or on the sensors (in terms of velocity in
the measure acquisition) suggest the introduction of
the following additional constraints
| ˙x
1
(t)| ≤ v
max
| ˙x
2
(t)| ≤ v
max
|u
1
(t)| ≤ u
max
|u
2
(t)| ≤ u
max
In this work the hypothesis that the mobile sensor
at time t can take measures within a circular area of
radius ρ around its current position y(t) is considered.
Such an area under sensor visibility will be denoted as
M(t) = σ(y(t),ρ)
In other words, M(t) denotes the area over which the
sensor can take measures at time t.
2.2 The Mathematical Formulation of
the Coverage Problem
According to what stated in subsection 2.1, given a
time interval Θ = [0,t
f
], the geometric expression of
the area covered by the measures during Θ, say M
Θ
,
can be easily given by
M
Θ
=
t∈Θ
M(t) =
t∈Θ
σ(y(t), ρ) (3)
However, such a formulation is not easy to be used
in an analytical optimal control problem formulation.
Then, alternative expressions that gives in an analytic
form how a given trajectory reflects on the space cov-
erage for the sensor measure must be found.
ICINCO 2007 - International Conference on Informatics in Control, Automation and Robotics
238
The one used in this work is based on the dis-
tance d(y(t), P) between the points {P|P ∈ W} of the
workspace and the trajectory.
Once the distance between a point P of the
workspace and a given trajectory y(t) is defined as
d(y(t), P) = min
t∈Θ
||
y(t) − P
||
(4)
and making use of the function
pos(ξ) =
ξ if ξ > 0
0 if ξ ≤ 0
(5)
that fixes to zero any nonpositive value, the function
ˆ
d(y(t), P, ρ) = pos(d(y(t), P) − ρ) ≥ 0
can be defined. Then, a measure of how the trajectory
y(t) produces a good coverage of the workspace can
be given by
J(y(t)) =
P∈W
ˆ
d(y(t), P, ρ) (6)
Smaller is J(y(t), better is the coverage.
If J(y(t)) = 0 than y(t) covers completely the
workspace.
2.3 The Optimal Control Problem
Formulation
Making use of the element introduced in previous
subsections, the Optimal Control Problem can be for-
mulated in order to find the best trajectory y
∗
(t) that
maximizes the area covered by sensor measurement
during the time interval Θ, as defined in previous sub-
section, and satisfies the constraints. Then a con-
strained optimal control problem is obtained, whose
form is
minJ(Λ(u(t)))
f(u(t)) = 0
g(u(t)) ≤ 0
(7)
In (7), the cost functional J(·) is given by (from
(6))
J(Λ(u(t))) =
p∈W
ˆ
d(Λ(u(t)), p, ρ) (8)
The optimal solution u(t) = u
∗
(t) (t ∈ Θ)is the
control that produces the optimal trajectory y
∗
(t) =
Λ(u
∗
(t)) (t ∈ Θ).
In general is not possible to solve analytically the
optimal control problem defined in the precedent sec-
tion, due the functional form of J(·) in (7). In next
section a solvable discrete problem is defined.
3 DISCRETE TIME
FORMULATION
In order to overcome the difficulty of solving a prob-
lem as (7) due to the complexity of the cost function
J(·), a discretization is performed, both with respect
to space W, and with respect to time in all the time
dependent expressions.
The workspace is divided into square cells c
i, j
with resolution (size) l
res
, and the trajectory is dis-
cretized with sample time T
s
. The equations of the
discrete time dynamics are:
z((k+ 1)T
s
) = A
d
z(kT
s
) + B
d
u(kT
s
)
y(kT
s
) = Cz(kT
s
)
(9)
where A
d
= e
AT
s
and B
d
=
T
s
0
e
Aτ
Bdτ
The state vector z(t) at the generic time instant t =
NT
s
depends on the initial state z
0
and on the controls
from time t = 0 to time t = (N − 1)T
s
z(NT
s
) = A
N
d
z
0
+
N−1
∑
i=0
A
i
d
B
d
u((N − 1)T
s
− iT
s
) (10)
The following matrices are now defined:
Z
N
=
z(T
s
)
.
.
.
z(NT
s
)
Y
N
=
y(0)
.
.
.
y(NT
s
)
A
N
=
A
d
A
2
d
.
.
.
A
N
d
B
N
=
B
d
0 ... 0 0
A
d
B
d
B
d
... 0 0
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
A
N−1
d
B
d
A
N−2
d
B
d
... A
d
B
d
B
d
U
N
=
u(0)
.
.
.
u((N − 1)T
s
)
U
max
=
u
max
.
.
.
u
max
Z
max
=
v
max
x
1,max
v
max
x
2,max
−−
.
.
.
−−
v
max
x
1,max
v
max
x
2,max
Z
min
=
−v
max
x
1,min
−v
max
x
2,min
−−
.
.
.
−−
−v
max
x
1,min
−v
max
x
2,min
DYNAMIC SENSOR NETWORKS: AN APPROACH TO OPTIMAL DYNAMIC FIELD COVERAGE
239
Making use of such matrices, the sequence of val-
ues for the sampled state vector z(kT
s
), with 0 ≤ K ≤
(N +1), can be expressed in the simple compact form
Z
N
= A
N
z
0
+ B
N
U
N
(11)
The cost function can then be written as:
J(Y
N
) =
ν
x
∑
i=1
ν
y
∑
j=1
ˆ
d(Λ(U
N
), c
i, j
, ρ) (12)
where ν
x
=
(x
max
−x
min
)
l
res
, ν
y
=
(y
max
−y
min
)
l
res
and
Λ(U
N
) = Y
N
.
3.1 The Nonlinear Programming
Problem Formulation
The problem of finding the maximum area coverage
trajectory can now be written as a tractable discrete
optimization problem with linear inequality and box
constraints
min
U
N
ν
x
∑
i=1
ν
y
∑
j=1
ˆ
d(Λ(U
N
), c
i, j
, ρ)
A
model
U
N
≤ B
model
(13)
−U
max
≤ U
N
≤ U
max
where A
model
=
B
N
−B
N
and B
model
=
Z
max
− A
N
z
0
−Z
min
+ A
N
z
0
Suboptimal solutions can be computed using nu-
merical methods. In the simulations performed, the
SQP (Sequential Quadratic Programming) method
has been applied. The obtained model can be cus-
tomized according to the specific task, as shown in
the following section.
4 MODEL CUSTOMIZATION
AND CASE SOLUTIONS
In this section some cases are faced in order to put in
evidence the capabilities and he effectiveness of the
proposed solution. The values of parameters used in
all the simulations are:
u
max
= 0.5N, v
max
= 1.5
m
sec
, x
max
= y
max
=
4m,x
min
= y
min
= −4m, T
s
= 0.5sec
4.1 The Case of a Single Sensor
Fixed initial state
The formulation adopted allows to find covering tra-
jectories for a single sensor who start from a given ini-
tial state. In figure 1 the corresponding simulation re-
sults, for z
0
=
0 0 0 0.
T
are depicted. With
t
f
= 20sec the sensor covers the 70.9% of total area.
−4 −3 −2 −1 0 1 2 3 4
−4
−3
−2
−1
0
1
2
3
4
x
1
x
2
Figure 1: Suboptimal trajectory for one moving sensor with
arbitrary starting point (z = 0).
Optimal initial state
The initial state z
0
can be included among the set
of variables of the optimization problem. In fact,
defining
V
N
=
z(0)
u(0)
.
.
.
u((N − 1)T
s
))
H
N
=
A
d
B
d
... 0 0
A
2
d
A
d
B
d
... 0 0
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
A
N
d
A
N−1
d
B
d
... A
d
B
d
B
d
it is possible to write
Z
N
= H
N
V
N
(14)
The new optimization problem is then obtained
setting
A
model
=
H
N
−H
N
and B
model
=
Z
max
−Z
min
Leaving the initial condition free, better results are
obtained since the initial state is also optimal, as it is
shown in figure 2.
Here in the same time of the precedent simulation
(t
f
= 20sec), the sensor covers 73.49% of total area,
versus the 70.9% of the fixed starting state case.
Periodic trajectory
Cyclic trajectories can be very useful in area mon-
itoring or surveillance tasks because this choice, once
ICINCO 2007 - International Conference on Informatics in Control, Automation and Robotics
240
−4 −3 −2 −1 0 1 2 3 4
−4
−3
−2
−1
0
1
2
3
4
x
1
x
2
Figure 2: Suboptimal trajectory for one moving sensor with
suboptimal starting point.
the maximum time NT
S
between measures on the
same point is fixed, allows to repeat the measure in
the same point periodically.
According to the present formulation, the sampled
dynamics over N sampled instants has a periodic be-
havior if and only if
z((N + 1)T
s
) = z(0) (15)
Observing that the computation of the (N +1)−th
sampled values for the state gives
z((N + 1)T
s
) = [
A
N+1
d
... A
d
B
d
B
d
]V
N
while
z(0) = [
I 0 ... 0 0
]V
N
condition (15) can be rewritten as
[
A
N+1
d
− I ... A
d
B
d
B
d
]V
N
= 0 (16)
Equation (16) must be added as a new constraint
in the optimization problem in order to get periodic
solutions.
The figure 3 shows the results obtained by simu-
lations for this case.
With t
f
= 40sec the 98, 17% of the workspace area
is covered.
−4 −3 −2 −1 0 1 2 3 4
−4
−3
−2
−1
0
1
2
3
4
x
1
x
2
Figure 3: Sub-optimal trajectory for one moving sensor.
4.2 The Case of Multiple Sensors
The models shown above are very easily extended to
the case under interest of area coverage with multiple
moving sensors. The use of multiple sensors instead
of one allows to reduce the time t
f
within the same
coverage or, equivalently, increase the coverage for
the same t
f
.
If n is the number of the moving sensors, the opti-
mization problem can be formulated in the same way
once the following matrices are defined and used in-
stead of the corresponding ones:
U
n
N
=
U
N,1
.
.
.
U
N,n
where U
N,i
stands for the control set (U
N
) of the i−th
sensor.
A
n
model
=
A
model,1
0 ... 0
.
.
.
.
.
.
.
.
.
.
.
.
0 0 ... A
model,n
B
n
model
=
B
model,1
.
.
.
B
model,n
where A
model,i
and B
model,i
are the A
model
and the
B
model
matrices of the i−th single sensor model.
In figure 4 the result for the multi-sensor case with
n = 2 is depicted. In timet
f
= 25sec the 99.86% of the
workspace area is covered. The gain of time respect
to the single sensor case is evident.
−4 −3 −2 −1 0 1 2 3 4
−4
−3
−2
−1
0
1
2
3
4
x
1
x
2
Figure 4: Sub-optimal cyclic trajectories for moving sensor
1 (blue) and moving sensor 2 (green), the yellow circles
show the measures area.
DYNAMIC SENSOR NETWORKS: AN APPROACH TO OPTIMAL DYNAMIC FIELD COVERAGE
241
5 CONCLUSIONS AND FUTURE
WORKS
In the present paper a measurement system composed
by several sensors moving within the area under mea-
sure has been considered. This system has been called
dynamic sensor network. For this kind of system the
formulation for an optimal solution to the area cov-
erage problem has been provided. The complexity of
the cost function makes very hard (actually impossi-
ble) the computation of the optimal solution. Then, in
order to get a solution, a sampled model has been con-
sidered, bringing to a nonlinear programming prob-
lem that has been solved numerically. The results for
a single sensor with different choices for initial con-
ditions (freely given or optimal) and for behavior of
the trajectory (non periodic or periodic) show the ef-
fectiveness of the proposed procedure. The case of a
n-sensors systems has also been considered and, for
n = 2 has been simulated in order to show the re-
sults when more sensors are present. The problem at
present under investigation concerns the inclusion of
non collision constraints, where non collisions are to
be considered both between moving sensors and with
fixed obstacles that can be present in the measurement
area.
REFERENCES
Acar, E., Choset, H., and Lee, J. Y. (2006). Sensor-based
coverage with extended range detectors. Robotics,
IEEE Transactions on [see also Robotics and Automa-
tion, IEEE Transactions on], 22(1):189–198.
Akyildiz, I., Su, W., Sankarasubramaniam, Y., and Cayirci,
E. (2002). A survey on sensor networks. Communi-
cations Magazine, IEEE, 40(8):102–114.
Bicchi, A. and Tonietti, G. (2004). Fast and ”soft-arm” tac-
tics [robot arm design]. Robotics & Automation Mag-
azine, IEEE, 11(2):22–33.
Cecil and Marthler (2006). A variational approach to path
planning in three dimensions using level set methods.
Journal of Computational Physics, 221:179–197.
Howard, Mataric, S. (2002). An incremental self-
deployment for mobile sensor networks. Autonomus
Robots.
Huang, C.-F. and Tseng, Y.-C. (2005). The coverage prob-
lem in a wireless sensor network. Mobile Networks
and Applications, 10:519–528.
Lewis, F. L. (2004). Smart Environments: Technologies,
Protocols and Applications, chapter 2. D.J. Cook and
S. K. Das.
Lin, F.Y.S. Chiu, P. (2005). A near-optimal sensor
placement algorithm to achieve complete coverage-
discrimination in sensor networks. Communications
Letters, IEEE, 9:43–45.
Ma, C. and Miller, R. (2006). Milp optimal path planning
for real-time applications. In American Control Con-
ference, 2006, page 6pp.
Meguerdichian, S., Koushanfar, F., Potkonjak, M., and Sri-
vastava, M. (2001). Coverage problems in wireless ad-
hoc sensor networks. In INFOCOM 2001. Twentieth
Annual Joint Conference of the IEEE Computer and
Communications Societies. Proceedings. IEEE, vol-
ume 3, pages 1380–1387vol.3.
Tan, J., Lozano, O., Xi, N., and Sheng, W. (2004). Mul-
tiple vehicle systems for sensor network area cover-
age. In Intelligent Control and Automation, 2004.
WCICA 2004. Fifth World Congress on, volume 5,
pages 4666–4670Vol.5.
Tsai, Cheng, O. B.-S. (2004). Visibility and its dynamics in
a pde based implicit framework. Journal of Computa-
tional Physics, 199:260–290.
V. Isler, S. K. and Daniilidis, K. (2004). Sampling
based sensor-network deployment. In Proceedings
of IEEE/RSJ International Conference on Intelligent
Robots and Systems IROS.
Wang, P. K. C. (2003). Optimal path planing based on vis-
ibility. Journal of Optimization Theory and Applica-
tions, 117:157–181.
Yung-Tsung Hou, Tzu-Chen Lee, C.-M. C. B. J. (2006).
Node placement for optimal coverage in sensor net-
works. In Proceedings of IEEE International Confer-
ence on Sensor Networks, Ubiquitous, and Trustwor-
thy Computing.
Zou, Y. and Chakrabarty, K. (2004). Uncertainty-aware
and coverage-oriented deployment for sensor net-
works. Journal of Parallel and Distributed Comput-
ing, 64:788–798.
ICINCO 2007 - International Conference on Informatics in Control, Automation and Robotics
242
