for the same model is devised in Behdani et al. [23], which
is claimed to be more efficient with respect to the required
computational time. Another paper with a similar setting
but with multiple mobile sinks is due to Luo and Hubaux
[24]. They give an MILP model to maximize the network
lifetime that is defined as the sum of the period lengths
where a period is taken as the amount of time for a given
sink configuration. The period changes if one or more of
the sink locations change.
None of the aforementioned works considers the inte-
gration of the four major WSN design issues (i.e., sensor
locations, activity scheduling, data and mobile sink routes)
into a monolithic MILP model. All of them assume a prede-
fined set of sensor locations, and none of them considers
activity schedules. Moreover, almost half of the studies
employ a predefined data propagation method, namely
shortest path data propagation strategy. On the other hand,
the MILP model given in Keskin et al. [6] is the only one
which attempts to obtain an optimal WSN design in terms
of the network lifetime with respect to all of the above
mentioned fundamental design issues. This work demon-
strates the favorable effect of the integration by comparing
WSN network lifetimes obtained by an integrated model
with those found by some mathematical models from the
literature, on the randomly generated WSN design prob-
lems. However, the MILP model becomes unsolvable for
realistic sized networks. Hence, practical heuristic solution
strategies are still needed, which we try to accomplish in
this work. In the next section, we provide a mathematical
model to integrate WSN design decisions of sensor places,
activity schedules, data routes, trajectory of the mobile
sink(s), and then present two heuristic strategies for the
solution of the model. We experimentally demonstrate
the efficiency and accuracy of the new heuristic ap-
proaches on a large set of randomly generated test
problems.
3. Mathematical model
Here we present a mathematical optimization model,
which simultaneously addresses the fundamental issues
in WSN design. In other words, an optimal solution of the
sensor location, activity scheduling, mobile sink and data
routing Problem (SAMDP) is obtained by solving this MILP
formulation. In order to visualize the problem better, we
illustrate in Fig. 1 a sample solution to a sensor network
with a lifetime of two periods. There are two sinks with
15 possible visit points and 30 candidate sensor locations.
The figure shows the locations of the sensors and sinks,
and the data routes are represented by arrows in both peri-
ods. We observe that some of the sensors are in active
mode in both periods, whereas some of them are in stand-
by mode in one period and active in the other. Moreover,
the sensing and communication ranges of the sensors are
both equal to one. As the coverage requirement, each point
that must be covered by at least two sensors is seen to be
satisfied in the solution depicted in Fig. 1 since each point
of the sensor field is within the sensing range of at least
two sensors in each time period. Another observation we
can make is that some sensors send the collected data
directly to a sink, while some others send their data to
neighboring sensors which act as relay nodes.
The formal description of the MILP model is as follows.
The definitions of the parameters and decision variables
are given in Table 1.
SAMDP :
max
X
t2T
w
t
ð1Þ
s:t:
X
s2R
X
j:i2S
js
x
jsirt
þ h
r
a
irt
¼
X
‘2N
ir
y
ir‘t
þ
X
s2R
X
j2S
ir
x
irjst
i 2S; r 2R; t 2T ð2Þ
X
t2T
c
s
a
irt
þc
r
X
s2R
X
j:i2S
js
x
jsirt
0
@
þ
X
s2R
X
j2S
ir
c
t
ij
x
irjst
þ
X
‘2N
ir
c
t
i‘
y
ir‘t
!
6 E
r
i 2S; r 2R ð3Þ
X
r2R
X
i:‘2N
ir
y
ir‘t
6 Mz
‘t
‘ 2N; t 2T ð4Þ
X
‘2N
z
‘t
¼ Pt2T ð5Þ
X
r2R
X
i:k2K
ir
q
irt
P d
k
k 2K; t 2T ð6Þ
X
i2S
X
r2R
f
ir
p
ir
6 B ð7Þ
q
irt
6 p
ir
i 2S; r 2R; t 2T ð8Þ
X
s2R
X
j2S
ir
x
irjst
6 Mq
irt
i 2S; r 2R; t 2T ð9Þ
X
s2R
X
j:i2S
js
x
jsirt
6 Mq
irt
i 2S; r 2R; t 2T ð10Þ
a
irt
6 w
t
i 2S; r 2R; t 2T ð11Þ
a
irt
6 Mq
irt
i 2S; r 2R; t 2T ð12Þ
a
irt
P w
t
Mð1 q
irt
Þ i 2S; r 2R; t 2T ð13Þ
w
t
; a
irt
; y
ir‘t
; x
irjst
P 0 ð14Þ
z
‘t
; p
ir
; q
irt
2f0;1gð15Þ
The objective function (1) represents the network life-
time which is defined as the sum of the period lengths.
Constraints (2) are the flow balance equations which are
defined for each sensor of all types in each period and they
simply equate the amount of data that is either produced
by the sensor or received from the neighboring sensors
to the total data sent out of the sensor to the neighboring
sinks and sensors. Constraints (3) set an upper bound on
the energy spent by each sensor throughout the network
lifetime. Note that a
irt
replaces the product w
t
q
irt
where
w
t
is the length of period t and q
irt
indicates whether or
not sensor ði; rÞ is active in period t. This implies that if sen-
sor ði; rÞ is active in period t, it generates data that should
be taken into consideration in constraints (2). It also
spends energy for sensing and processing the data that is
considered by constraints (3). Therefore, the amount of
energy used by each sensor for its sensing and processing
duties is taken into account with the first term in (3).
Moreover, the amount of energy used for receiving data
from the neighboring sensors is handled in the second
M.E. Keskin et al. / Ad Hoc Networks 17 (2014) 18–36
21