Wireless Sensor Network, 2010, 2, 343-346
doi:10.4236/wsn.2010.24045 Published Online May 2010 (http://www.SciRP.org/journal/wsn)
Complexity Results for Wireless Sensor Network
Scheduling
Fethi Jarray
Laboratoire Cédric, Paris, France
Gabes University of Sciences, Gabes, Tunisia
Al-Imam Mohamed Ibn Saoud University, Riyadh, Saudi Arabia
Received January 31, 2010; revised February 22, 2010; accepted Febr uary 23, 2010
Abstract
We study the problem of scheduling multiple sensors to visit and observe a group of sites at discrete time
points over a planning horizon of given length. We show that scheduling under a given number of visits for
each site and in each period is an NP-complete problem by providing equivalence with a problem in discrete
tomography. We also give a polynomial time algorithm to schedule the sensors under a given number of vis-
its in each period.
Keywords: Discrete Tomography, Sensor Scheduling, Combinatorial Optimization
1. Introduction
A wireless sensor is a small physical device having a
battery with a limited capacity and having a transmission,
a reception capability of limited range and capable to
take various measurements of its neighborhood. These
measurements include temperature, acoustic, solar radia-
tion, etc. Since a single sensor is not able to monitor a
hole field, a group of sensors should be deployed and
frequently interact with each other to exchange informa-
tion. This group of distributed sensors forms the wireless
sensor networks (WSN). Generally, the basic goal of a
WSN is to ensure the surveillan ce of a given region with
a limited number of sensors and eventually transmit the
sensed data to a processing unit.
The management and the organization of WSN have
been investigated by many researchers. Depending on
the application and the goal of researchers, several com-
binatorial optimization models and solution techniques
have been proposed [1]. These models and problems
include, among others, sensor localization and tracking
[2-5], sensor scheduling [6-11] communication neutrali-
zation [12,13] and energy consumption [14,15]. There
are a wide variety of methods and models because on
one had several issues are considered in WSN. On the
other hand, the most addressed problems are NP-com-
plete, i.e., there is no polynomial time algorithm to
solves these problems unless P = NP.
This paper is concerned with WSN scheduling to pe-
riodically monitor and observe an environment. WSN
scheduling is needed in various applications such as traf-
fic monitoring at roads, military, medical, pollution de-
tection, etc. In this paper, we show the complexity results
of WSN scheduling by supposing that the number of
required visits for each period are given. We will use a
reduction from an independent problem of discrete to-
mography. For clarity, the next section is devoted to the
area of discre t e tomog raphy.
The remainder of this paper is organized as follows. In
Section 2, the problem of discrete tomography and bi-
nary matrices reconstruction will be presented. In Sec-
tion 3, Sensor scheduling with a given numbers of visits
per period and per site will be studied. In Section 4, sen-
sor scheduling with a given numbers of visits per period
is addressed.
2. Discrete Tomography
Discrete Tomography (DT) is an emergent area of com-
puter science (refer to the books of Hermann and Kuba
[16,17] for further information on the theory, algorithms
and applications). It deals with the reconstruction of bi-
nary matrices and images from horizontal and vertical
projections. Let A be a binary matrix of size m × n, we
denote by the number of ones on row i
and by
1
n
i
j
hA


1
m
ij
j
ij
i
vA

 the number of ones on column j.

F. JARRAY 344
The vectors

1,, m
H
hh and are
called the horizontal and the vertical projection respec-
tively. The problem of reconstructing a binary matrix
from orthogonal projections, denoted MB(H,V), is de-
fined as follows: given two vectors H and V, we search
to reconstruct a binary matrix consistent with these pro-
jections or to report that such a matrix does not exist. It is
well known that this problem is polynomial [18] (Figure
1). However, it becomes NP-complete by imposing a
maximal length of sequence of zeros between the con-
secutive ones [19], i.e., we impose a maximal number of
zeros between two consecutive ones.

1,, n
Vv v
i
3. WSN Scheduling with Given Number of
Visits per Period and Site SSHV(a,b)
We consider the following problem SSHV(a, b) of sen-
sors scheduling. There are m sites to observe ,
s
i

, a set of m sensors and a scheduling horizon
(interval) T composed of n periods

1,...,m



1,...,Tn
,;
;
ij

. During
period tj of the time interval T, exactly vj sites should be
observed by vj sensors. Each site si, should be observed
during hi periods. When site si is not observed at period tj,
a non visiting penalty aij is incurred and an information
loss penalty bijlij is also incurred. We suppo se that aij and
bij are given non negative and lij is the number of elapsed
periods since last visiting site si. Note that the informa-
tion loss penalty is p roportional to the time in terval when
the site is not observed . The problem now is to determine
a surveillance schedule, i.e., to decide for each period
which site to observe minimizing the maximum non vis-
iting penalties and information loss penalties.
The problem SSHV(a,b) can be reformulated as a
mixed integer linear program inspired from [11]. We
introduce the binary decision variables xij and the real
variables yij such that xij = 1 and if the site si is observed
at time slot j. The real variable yij represents the last time


,-
1
1j
,
,
0,
,;
1 ,
ij ijij
j
i
i jij
ij
ij
x by
xv j
hi
yy jx
jij
yi
xyR





 



1
1
1
min
..
0,
0,
ij
m
ij
i
n
ij
j
ij
ij
i
ij
C
st
Ca
Px
ij
jx y















 










v
j
h
i
Figure 1. A binary matr ix with horizontal project ion H = (2,
2, 5, 3) and vertical projection V = (3, 1, 3, 1, 4); maximal
length of sequences of zeros is 3.
where site si was observed before period j. This gives us
the following MIP model:
The constraint (1) ensures that the objective function
(C) consists in minimizing the maximum penalty. The
constraint (2) ensures that in each period tj there are vj
visited sites. The constraints (3) ensure that each site si is
visited in hi periods. Constraints (4) and (5) together en-
sure that yij is modified only if site si is visite d (xij = 1) and
takes the value j. Constraint (6) implies that all the sites
are not obs erved bef or e the firs t period.
A solution to the problem SSHV(a,b) will be pre-
sented by an m × n binary matrix A such that aij = 1 only
if site si is visited at period tj.
Consider the subproblem SSHV(0,1) with aij = 0 and
bij = 1 for all the sites over all the periods. Thus for each
couple of site and period (si,tj) the total penalty is (j-yij)
which is the number of consecutive non visiting periods
before time slot tj. If we consider the schedule as a binary
matrix, the total penalty is exactly the length of the se-
quence of zeros before the entry (i,j). Hence the sub-
problem SSHV(0,1) is equivalent to reconstructing a
binary matrix with horizontal projection H and vertical
projection V and minimizing the length of the longest
sequence of zeros which is NP-complete ( see Section 2).
So the general problem SSHV(a,b) is also NP-complete.
Proposition 1
(1) The problem SSHV(a,b) is NP-complete.
(2) 4. WSN Scheduling with a Given Number of
Visits per Period
(3)
(4) In this scheduling problem, we search for a sensor sche-
duling respecting the periodically numbers of visits, i.e.,
in period j there are vj visits while minimizing the maxi-
mal penalty. The problem SSV(a,b) can be considered as
a relaxation of the problem SSHV(a,b) where the number
of visits for each site is omitted. Yavuz and Jeffcoat [11]
studied an NP-complete problem very close to SSV(a,b).
(5)
(6)

F. JARRAY345
They supposed that in each period, at most m sites was
observed instead of exactly vj sites as in SSV(a,b). In this
section, we show that the problem SSV(0,1) can be
solved by a polynomial time a lgorithm.
As in the previous section, a solution to the problem
SSV(0,1) will be presented by an m × n binary matrix A
such that aij = 1 only if site si is visited at period tj. Thus
solving SSV(0,1) with vector of visits V is equivalent to
reconstructing a binary matrix m × n respecting the ver-
tical projection V and minimizing the maximal distance.
We recall that the distance is the length of a sequ ence of
consecutive zeros. We propose the following cyclic al-
gorithm to solve SSV(0,1) where the rows are associated
to the sites and the columns are associated to the periods.
Algorithm A-SSV
 Assign a number from 1 to m to each site
 Assign the visits on column 1 to the first v1
rows
 Assign the visits on column 2 to the next v2
rows
 This process is continued cyclically with row
1 being treated as the next row after row m.
We state the following result:
Proposition 2
The algorithm A-SSV solves SSV(0,1) in O(mn).
Proof The algorithm A-SSV provides a solution S*
respecting the vertical projection since at each step j vj
ones are assigned to the rows.
Let us show that S* minimizes the maximal distance.
Suppose that in S*, the maximal distance is reached be-
tween two 1s placed on cells (i,j) and (i,j') with j < j'.
Since on row i, there is no 1 placed between columns j + 1
and j' – 1 then . If S* is not optimal then
there exists a so lution S with a maximal distance les s than
that of S*. On each row of S, there is at least an 1 placed
between columns j + 1 and j' – 1. Hence ,
contrary with .
1j
k
kj
vm



1j
k
kj
vm



1j
k
kj
vm



Note that in both addressed problems SSV(0,1) and
SSHV(a,b), once the schedule is established, the visits
should be cyclically assigned to the sensors to improve
the lifetime of WSN.
5. Conclusions
In this paper, we have studied the wireless sensor net-
work scheduling problem. We have proved that schedul-
ing with a given number of visits for each site and each
period with a minimum maximal penalty is an NP-com-
plete problem. We have also proposed a polynomial time
algorithm to schedule sensors under only a given number
of visits for each period. The problems studied in this
paper belong to a rich and relatively unexplored area.
Investigating the problems under more real constraints
and designing heuristic to solve the hard problems are
possible research directions.
6. References
[1] A. Sorokin, N. Boyko, V. Boginski, S. Uryasev and P. M.
Pardalos, “Mathematical Programming Techniques for
Sensor Networks,” Algorithms, Vol. 2, 2009, pp. 565-581.
[2] K. Wu, C. Liu, J. Pan and D. Huang, “Robust Range-Free
Localization in Wireless Sensor Networks,” Mobile Net-
works & Applications, Vol. 12, No. 5, 2007, pp. 392-405.
[3] C. Wang and L. Xiao, “Sensor Localization in Concave
Environments,” ACM Transactions on Sensor Networks,
Vol. 4, No. 1, 2008, pp. 1-31.
[4] D. Koutsonikolas, S. M. Das and Y. C. Hu, “Path Plan-
ning of Mobile Landmarks for Localization in Wireless
Sensor Networks,” Computer Communications, Vol. 30,
No. 13, 2007, pp. 2577-2592.
[5] M. Rudafshani and S. Datta, “Localization in Wireless
Sensor Networks,” Proceedings of the 6th International
Conference on Information Processing in Sensor Net-
works, New York, 25 April 2007, pp. 51-60.
[6] J. Jeong, S. Sharafkandi and D. H. C. Du, “Energy-Aware
Scheduling with Quality of Surveillance Guarantee in
Wireless Sensor Networks,” Proceedings of the 2006
Workshop on Dependability Issues in Wireless Ad Hoc
Networks and Sensor Networks, New York, 25 September
2006, pp. 55-64.
[7] K. Wu, Y. Gao, F. Li and Y. Xiao, “Lightweight De-
ployment-Aware Scheduling for Wireless Sensor Net-
works,” Mobile Networks & Applications, Vol. 10, No. 6,
2005, pp. 837-852.
[8] S. S. Singh, N. Kantas, B. N. Vo, A. Doucet and R. J.
Evans, “Simulation-Based Optimal Sensor Scheduling
with Application to Observer Trajectory Planning,” Au-
tomatica, Vol. 43, No. 5, 2007, pp. 817-830.
[9] Klappenecker, H. Lee and J. L. Welch, “Scheduling Sen-
sors by Tilinglattices,” Proceedings of the 27th ACM
Symposium on Principles of Distributed Computing, New
York, 11 June 2008, pp. 437-437.
[10] M. Yavuz and D. Jeffcoat, “Single Sensor Scheduling for
Multi-Site Surveillance,” Technical Report, Air Force
Research Laboratory, Maui, 2007.
[11] M. Yavuz and D. Jeffcoat, “An Analysis and Solution of
the Sensor Scheduling Problem,” Proceedings of the 7th
International Conference on Cooperative Control and
Optimization, Gainesville, 31 January-2 February 2007.
[12] C. Commander, P. Pardalos, V. Ryabchenko and S.
Uryasev, “The Wireless Network Jamming Problem,”
Journal of Combinatorial Optimization, Vol. 14, No. 1,
2007, pp. 481-498.
[13] C. Commander, P. Pardalos, V. Ryabchenko, S. Sarykalin,

F. JARRAY 346
T. Turko and S. Uryasev, “Robust Wireless Network
Jamming Problems,” Lecture Notes in Control and In-
formation Sciences, Springer, Berlin, 2008.
[14] K. Kalpakis, K. Dasgupta and P. Namjoshi, “Efficient
Algorithms for Maximum Lifetime Data Gathering and
Aggregation in Wireless Sensor Networks,” Computer
Networks, Vol. 42, No. 6, 2003, pp. 697-716.
[15] S. Stanczak, M. Wiczanowski and H. Boche, “Theory and
Algorithms for Resource Allocation in Wireless Net-
works,” Lecture Notes in Computer Science, Springer, Ber-
lin, 2006.
[16] G. Herman and A. Kuba, “Discrete Tomography: Foun-
dations, Algorithms and Applications,” Applied and Nu-
merical Harmonic Analysis, Birkhäuser, Boston, 1999.
[17] G. Herman and A. Kuba, “Advances in Discrete Tomo-
graphy and its Applications,” Applied and Numerical Har-
monic Analysis, Birkhäuser, Boston, 2007.
[18] H. J. Ryser, “Combinatorial Properties of Matrices of
Zeros and Ones,” Canadian Journal of Mathematics, Vol.
9, 1957, pp. 371-377.
[19] F. Jarray, M.-C. Costa and C. Picouleau, “Complexity
Results for the Horizontal Bar Packing Problem,” Infor-
mation Processing Letters, Vol. 108, No. 6, 2008, pp.
356-359.