TELKOM
NIKA
, Vol. 11, No. 4, April 2013, pp. 2029
~20
3
6
ISSN: 2302-4
046
2029
Re
cei
v
ed
De
cem
ber 3
0
, 2012; Re
vi
sed
Febr
uary 22,
2013; Accept
ed March 4, 2
013
A Sweep Coverage Sch
e
me Based on Vehicle Routing
Problem
Li Shu
1
, Wei
Wang
2
, Feng
Lin
3
, Zhonghao Liu
4
, Jiliu Zhou*
4
1,2,
3,4
School of Comp
uter Scie
nce, Sichu
an U
n
iversit
y
, Ch
in
a
*Corres
p
o
ndi
n
g
author, e-ma
i
l
: zhouj
l@scu.e
du.cn
A
b
st
r
a
ct
As an e
m
er
g
i
ng cov
e
ra
ge
prob
le
m in w
i
r
eless se
nsor
netw
o
rks, sw
eep cover
a
g
e
w
h
ich
introd
ucin
g
mo
bile s
ens
ors to
cover p
o
ints
of interest
w
i
th
in certai
n ti
me
interval c
an s
a
tisfy mo
nitor
i
ng
requ
est in
so
me p
a
rticul
ar a
p
p
licati
o
n
scen
a
r
ios w
i
th
l
e
ss
nu
mb
er of
no
d
e
s tha
n
th
e co
nventi
o
n
a
l stati
c
covera
ge
ap
p
r
oach. In
this
w
o
rk, ai
mi
ng
to su
pp
ort
dyna
mical
POI covera
ge
a
nd
data
de
liv
ery
si
mu
l
t
an
e
o
u
s
l
y
, a
no
vel
swe
e
p
co
ve
rag
e
sche
me
, nam
ed
VR
PSC
(Ve
h
i
cl
e R
o
u
t
i
n
g Prob
le
m ba
sed
Sweep
Cover
age), is p
r
opos
ed by mo
deli
ng the
mi
ni
mu
m n
u
m
ber
o
f
required se
ns
ors probl
e
m
in
sw
eep covera
g
e
as a Ve
hicl
e
Routi
ng Pro
b
l
e
m (VRP). In V
R
PSC, an
ins
e
rtion
algorithm
is first in
trod
u
c
ed
to
crea
te
the
initia
l sca
nni
ng
routes for POIs, and the
n
th
e Si
mu
la
ted
A
nne
ali
ng
is e
m
ploy
ed to
opti
m
i
z
e
thes
e rou
t
es.
T
he simul
a
tion
results show
that the VRPSC sche
m
e
ac
hiev
es better perfor
m
a
n
ce tha
n
exi
s
ting sche
m
es.
Ke
y
w
ords
: w
i
reless se
nsor n
e
tw
ork, coverage, VRP, sw
eep covera
ge
Copy
right
©
2013 Un
ive
r
sita
s Ah
mad
Dah
l
an
. All rig
h
t
s r
ese
rved
.
1. Introduc
tion
As a measure of QoS, coverage p
r
obl
em is
one of prima
r
y issue
s
for Wirele
ss Sensor
Networks
(WSN) [1]. Different covera
g
e
schem
es
h
a
ve been
pro
posed for va
rious a
ppli
c
ati
ons
of WSN. Th
ese
coverag
e
scheme
s
are focusi
ng
on deployin
g stationa
ry sen
s
o
r
nod
e
s
to
provide
conti
nuou
sly cove
rage
se
rvice f
o
r the whol
e
sen
s
in
g are
a
or a ba
rri
er, i
n
whi
c
h a h
u
g
e
numbe
r of
se
nso
r
n
ode
s a
r
e requi
red
[2-5]. Howeve
r, in fact, in
some
spe
c
ific ap
plication
s
of
WSN,
su
ch
a
s
p
a
trol
in
spe
c
tion, in
stea
d
of
cont
inu
o
u
s
cove
rage
of
the
whol
e a
r
ea, pe
riodi
cal
l
y
coverage
of
certain
poi
nts
of in
terest
s
(POIs) could
satisfy monito
ring
req
u
irem
ents. In
this
kind
of covera
ge
scena
rio, inst
ead of a larg
e numbe
r
of static node
s, a small number of mob
ile
node
s co
uld
be employe
d
to cover POIs within a ce
rtain time. Resea
r
che
r
s na
med this type
of
dynamic
cove
rage a
s
swe
e
p
coverage [6
].
Esse
ntially, swee
p
covera
ge
can
de
cre
a
se
t
he num
b
e
r of
sen
s
ors in
a WS
N
a
p
p
licatio
n
by takin
g
a
d
vantage
of the
mobility of
sensor
nod
es.
Thu
s
, the
ke
y issue
of
sweep
cove
rag
e
is
to sch
edul
e the traje
c
tory
of mobile se
nso
r
to
sati
sfy the covera
ge re
quireme
nt of POIs wi
th
minimum n
u
m
ber
of se
n
s
ors. Thi
s
p
r
oblem i
s
na
med a
s
the
minimum n
u
m
ber
of req
u
ired
sen
s
o
r
s p
r
obl
em. Recently, some soluti
ons a
r
e prop
ose
d
to achie
v
e swee
p co
verage in WSN.
In [7], authors first
study
the
sweep coverage scenario
to ut
ilize a sm
all number of m
o
bile
sen
s
o
r
s to m
onitor
ce
rtain
POIs pe
riodi
cally. The
auth
o
rs al
so p
r
ov
e the p
r
obl
e
m
of determi
ning
the minimum
numbe
r of required
sen
s
ors i
n
swe
e
p
coverage i
s
NP-Hard. T
w
o TSP-ba
sed
sweep cove
rage scheme
s
,
named CS
wee
p
for
th
e
cent
ralized
algorith
m
an
d DSweep fo
r the
distrib
u
ted al
gorithm,
re
sp
ectively, are
prop
osed.
In
[8], Z. Zhang,
et al. tran
sfo
r
m the mi
nim
u
m
numbe
r of re
quire
d se
nso
r
s p
r
oble
m
to MTSP
and employee PSO algorithm
to addre
ss this
probl
em. Chu
et.al. investigate swe
ep co
verage a
nd its ability to be used to dete
c
t a flashove
r
i
n
[9]. A patrol point algorithm (PPA) is propos
ed to k
e
ep the
patrol times
of mobile node
approximate
to one
anot
her. A
de
ce
ntralized
alg
o
rithm to
archive
sweep
cove
rag
e
in
the
uncertain
env
ironm
ent
with
different
co
m
m
unication to
pologi
es is
propo
sed
in [10
]. Although th
e
algorith
m
fail
s to a
c
hi
eve
sweep
cove
rage of th
e gi
v
en regio
n
wit
h
optimal
ope
ration time
du
e to
the un
ce
rtain
t
ies, auth
o
rs
give the
e
s
timation
on th
e differen
c
e
betwe
en th
e
actual
covera
ge
time
a
n
d
th
e
o
p
t
ima
l
time
.
In
[1
1
], D
u
e
t.a
l. p
r
es
en
t two
sw
ee
p
c
o
ve
r
a
ge
a
l
g
o
r
i
th
ms
, Min
E
xp
and
and OSweep
. MinExpand
is used
whi
l
e the mobile
sen
s
or i
s
restri
cted to follow the sa
me
trajecto
ry in different swe
ep peri
o
d
s
. On t
he other hand, OSwe
ep is appli
e
d
in the scen
a
rio
Evaluation Warning : The document was created with Spire.PDF for Python.
ISSN: 23
02-4
046
TELKOM
NIKA
Vol. 11, No. 4, April 2013 : 2029 – 2
036
2030
whe
r
e the m
obile sen
s
o
r
s are not
re
stricted to follo
w the same
trajecto
ry in
different swe
e
p
perio
ds.
Ho
wever,
the
s
e
existing
scheme
s
only f
o
cu
s
on
ho
w
to co
ntrol
the
traje
c
tory
of
sen
s
o
r
s
to scan POI
s
within a given time, without co
n
s
ide
r
i
ng how the
mobile nod
es delivery sen
s
ed
data to si
nk.
Actually, in
som
e
swe
e
p
cove
rag
e
scena
rio
s
, d
ue to the li
mitation of n
ode
transmissio
n rang
e an
d sp
arse no
de de
nsity, it
is hard to find an e
nd-to
-en
d
pat
h from mo
bile
sen
s
o
r
s to si
nk, which me
ans
se
nsors
can’t d
e
liver
t
he sen
s
ed
da
ta to sin
k
di
re
ctly. Unde
r th
is
situation, it i
s
obviou
s
that i
n
trodu
cin
g
static
relay n
o
d
e
to b
u
ild
a m
u
lti-hop
ba
se
d data
delive
r
y,
just a
s
in t
r
ad
itional WS
N, i
s
not
an effe
ctive
option. O
ne po
ssible
solution i
s
tre
a
t
ing sin
k
nod
e
as a
spe
c
ial
POI and controllin
g the
trajecto
ry
of moving se
n
s
ors to visit
the sin
k
no
de
perio
dically whe
r
e the m
o
ving se
nsors can tra
n
sf
er
se
ns
e
d
da
ta
to
s
i
nk
dir
e
c
t
ly. T
h
er
efo
r
e
,
sweep
coverage sch
e
me
has to integ
r
a
t
e POI covera
ge req
u
ireme
n
t and data d
e
livery.
In this work,
we a
nalyze the minim
u
m
numbe
r of
re
quire
d sen
s
o
r
s
pro
b
lem i
n
sweep
coverage as a
variation of
Vehicle Ro
uting
Pr
obl
em (VRP) an
d formulize th
e mi
nimum nu
mb
er
of re
quired
sensors p
r
o
b
l
e
m in
swee
p
cove
rag
e
by
improving Fi
she
r
a
nd
Jai
k
umar form
ula
for
VRP. Then a
novel swe
e
p
covera
ge scheme, nam
e
d
VRPSC, which
supp
ort
s
dynamical P
O
I
coverage a
n
d
data delivery
simultane
ou
sly, is
prop
osed by improvi
ng a VRP alg
o
rithm.
2. Problem Descriptio
n
In this
se
ctio
n, we
first
gi
ve the d
e
scri
ption of
swee
p covera
ge.
Then
we
revi
ew V
R
P
and a
nalysi
s
the minimu
m
numb
e
r
of required
se
ns
ors p
r
oble
m
i
n
swee
p
cov
e
rag
e
with V
R
P.
Finally, we formuli
z
e the m
i
nimum num
b
e
r of
req
u
ire
d
sen
s
ors p
r
ob
lem in sweep
coverage.
2.1. Descrip
tion of S
w
e
e
p
Cov
e
rage
The swe
ep
coverag
e
prob
lem ca
n be d
e
scrib
ed to fi
nding a
set o
f
accessin
g routes fo
r
a fleet of mobile node
s, ori
g
inating a
nd termin
ati
ng at the sin
k
, to cover a num
be
r of POIs duri
n
g
a given time interval. The o
p
timization o
b
jective is to find the lea
s
t numbe
r of mobile no
des.
Assu
me that
there a
r
e
N P
O
Is
12
{,
,
.
.
.
}
n
Pp
p
p
and one
sin
k
nod
e
0
p
distribute
d
in 2
-
D
area X*Y. Th
e position
s
of
all POIs and sink no
de are kno
w
n befo
r
e sche
dulin
g
.
Let
,
ij
d
denote
the di
stan
ce
betwe
en
i
p
and
j
p
. Eac
h
(0
)
i
pi
h
a
s
a
s
p
ec
ifie
d
co
ve
r
a
ge
r
e
qu
ir
eme
n
t
i
T
, whic
h
mean
s at lea
s
t one mo
bile
node h
a
s to
scan
(0
)
i
pi
once
within
i
T
. Without
losing
gen
erality,
assume
that
each mo
bile
sen
s
o
r
n
ode
s have
con
s
ta
nt moving vel
o
city
V
, co
nsta
n
t
transmissio
n
rang
e
, and same data b
u
ffer si
ze
L
. Further a
s
sume t
hat each mo
bile nod
e ha
s to stay a
c
o
ns
tant time interval
s
en
s
e
T
at any POI where it sca
n
s to
sen
s
e
data
a
nd stays a co
nstant
tim
e
interval
tr
a
n
s
T
at sink to delive
r
data it ca
rri
ed. Assume
that there a
r
e
i
q
bytes dat
a will be
colle
cted, o
n
c
e a
mobil
e
n
ode a
c
ce
ss certain POI
i
p
. Assu
me that
there
are
K
mo
b
ile
se
ns
or
node
s which are a
s
signe
d into
M
route
s
in the solutio
n
to acce
ss all
the POIs. Let
m
de
not
e
the set of POIs on the
th
m
ro
u
t
e and
m
k
den
ote the numbe
r of mobile se
nso
r
nod
es
which a
r
e
assign
ed for t
he
th
m
route. Let
m
R
den
ote the acce
ss
seq
u
ence of POIs in the
th
m
ro
ute, which
is o
r
igin
ating
and te
rminati
ng at
0
p
. A s
o
lution
S
to archive
sweep
coverage
can
be
repre
s
e
n
ted
as
{(
,
)
1..
.
}
ii
Sk
R
i
M
, where
(,
)
ii
kR
repre
s
ent
s as t
he
th
i
route in solution
S
.
2.2. Rev
i
e
w
on Vehicle Routing Probl
em
The vehi
cle
routing
pro
b
le
m (VRP
) i
s
a
cla
s
sical co
mbination
a
l o
p
timization
p
r
oblem,
whi
c
h i
n
volves the
de
sig
n
of a
set of mi
nimum-co
st v
ehicl
e route
s
, origi
nating
a
nd terminatin
g at
a depot, for
a fleet of vehicle
s
that se
rvices
a
set of
cu
stome
r
s
with kno
w
n d
e
m
and
s. In VRP,
each
cu
stom
er i
s
se
rviced
exactly o
n
ce
and, furt
h
e
rm
ore, all
the
cu
stome
r
s mu
st be
assign
ed
to
vehicle
s
with
out excee
d
in
g vehi
cle
ca
pacitie
s. In [12], Fishe
r
a
nd Jai
k
u
m
ar formulize VRP
probl
em in th
e followi
ng
way. Let
i
q
denot
e the de
man
d
of custom
er
(1
.
.
.
)
ii
n
,
i
Q
denote th
e
cap
a
city of v
ehicl
e
(1
.
.
.
)
kk
K
, and
,
ik
d
den
ote a
m
easure
of th
e di
stan
ce
contributio
n of
cu
st
ome
r
i
to the route follo
wed by vehi
cl
e
k
if
i
were to be delivered
by
k
.
Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM
NIKA
ISSN:
2302-4
046
A Sweep Coverag
e
Sch
e
m
e
based on V
ehicl
e Ro
uting Problem
(Li
Shu)
2031
Define
.
Then, the VRP problem
ca
n be formuli
z
ed as
Equati
on (1
). In Equat
ion (1
), Equation (1
a)
rep
r
e
s
ent
s the total di
st
ance travel
ed
; Equation
(1
b) e
n
sure
s
e
a
ch
co
stum
er is a
s
sign
ed t
o
a
vehicle; an
d
Equation (1 c) rep
r
e
s
e
n
ts the co
nst
r
aint
on vehicl
e capa
city. The VRP has
bee
n
proved a
s
a
NP-h
ard p
r
o
b
l
em.
11
1
1
m
i
n
(
1
a
)
1
1
,
...
,
(
1
b
)
1
,
..
.,
(
1
c
)
nK
ik
ik
ik
K
ik
k
n
ii
k
k
i
dx
Su
bje
c
t
to
xi
n
qx
Q
k
K
(1)
2.3. Formulization th
e Minimum Number of Requi
red Sensor
s Problem
The mi
nimum
num
ber of
re
quire
d
sen
s
o
r
s p
r
o
b
le
m i
n
sweep
coverage i
s
ve
ry
si
milar to
the VRP.
We
co
uld treat
si
nk
nod
e a
s
d
epot of V
R
P
whi
c
h i
s
al
so
simila
r to th
e
mobile
nod
e f
o
r
vehicle a
nd P
O
I for the cu
stome
r
. The
buffer si
ze of
mobile no
de
s and th
e time req
u
ire
m
en
t of
POIs will be t
he co
nstraint
s in swee
p co
verage.
Whe
r
ea
s, th
e
r
e i
s
an im
po
rtant differen
c
e
between
VRP an
d the
minimum
nu
mber of
requi
re
d se
nsors
problem.
It is assume
d
in VRP t
hat each custom
er is
se
rvice
d
exactly once
.
In
sweep coverage, due to the spa
r
se de
nsity of POI a
nd the low m
obile velocity of sensor no
d
e
, it
is po
ssible
th
at there
exist
som
e
POIs
wh
o
s
e
cove
rage
req
u
irem
ents a
r
e l
e
ss than twi
c
e
a
s
much time sp
ent on any mobile nod
e moving from t
he sink to the
POI. To address this pa
rticular
situation,
ad
ditional m
obil
e
no
de
ha
s
to be i
n
tro
d
u
c
ed
in thi
s
route to
en
su
re full
cove
rage
requi
rem
ent.
Define
,,
1
i
f n
o
d
e
mo
v
e
s
fro
m
t
o
0o
t
h
e
r
w
i
s
e
ij
ij
k
kp
p
x
.
The mi
nimu
m num
ber
of re
quired
sen
s
o
r
s p
r
o
b
lem in
swe
ep
coverage
ca
n b
e
formulate
d
as:
1
1
,,
(0)
(
0
)
1
=
(
2
a
)
(
2
b
)
mm
M
m
m
M
m
m
K
ij
k
m
ij
k
Mi
n
K
k
Subj
e
c
t
t
o
N
xk
0,
,
01
,0
,
01
,,
00
(2
c
)
(
2
d
)
(
2
e
)
(
*
)
(
NK
jk
jk
NK
ik
ik
NN
ij
k
i
ij
xK
xK
xq
Q
2 f
)
/
(
)
(
)
(
2
g
)
m
m
m
s
e
n
s
e
t
r
ans
i
m
lk
V
T
T
M
i
n
T
i
(
2
)
1
i
f cu
st
o
m
er i
i
s
d
e
l
i
v
e
red
b
y
v
e
h
i
cl
e
k
0o
t
h
e
r
w
i
s
e
ik
x
Evaluation Warning : The document was created with Spire.PDF for Python.
ISSN: 23
02-4
046
TELKOM
NIKA
Vol. 11, No. 4, April 2013 : 2029 – 2
036
2032
Equation
(2
a
)
represents the opt
imi
z
ati
on
obj
ective. Equation (2 b
)
an
d
(2 c) en
sure
all
the POIs are
covered by route
exactly once. Equatio
n (2 d)
and (2
e) en
sure all the route
s
sta
r
t
and termin
ate with the si
nk nod
e. Equation (2 f)
repre
s
e
n
ts th
e con
s
trai
nt on buffer si
ze of
mobile no
de
s. Equation (2
g) re
pre
s
e
n
ts the covera
ge
requi
reme
nt con
s
trai
nt.
3. VRPSC Scheme
To solve the
minimum
nu
mber of requi
red
se
nsors p
r
oble
m
, in V
R
PSC sch
e
me,
we
first
prop
ose an i
n
se
rtion h
euristics to ge
ne
rate r
oute
s
b
y
improving
Solomon I1
algorith
m
. Th
en,
two optimizations a
r
e introd
uce
d
in or
der
to optimize the initial soluti
on.
3.1. Route G
e
nera
tion Al
gorithm
Solomon I1
algorith
m
[13
]
is a cla
ssi
cal heu
risti
c
for VRP solut
i
on. We imp
r
ove this
algorith
m
to gene
rate the
access
rout
es for th
e problem in
swe
ep cove
ra
ge.
In the prop
o
s
ed
algorith
m
, we
introd
uce two mea
s
u
r
em
ents a
s
belo
w
to
sele
ct a
particula
r un
-routed
POI
u
p
to
ins
e
rt adjac
ent POI
i
p
and
j
p
in the cu
rre
nt route.
1,
,
,
()
iu
u
j
i
j
cm
i
n
d
d
d
(3)
21
((
)
)
cm
i
n
c
u
(4)
Clea
rly, the measurement
1
c
denote
s
th
e minimum i
n
creme
n
t for inse
rting th
e un-
routed POI
u
p
which ca
n
be use
d
to sele
ct the
best inserti
on pla
c
e. Moreove
r
, the
measurement
2
c
denote
s
th
e parti
cula
r
POI
u
p
whi
c
h
costs th
e mini
mum in
cre
m
ent for the
curre
n
t route
after insertion
.
In the propo
sed in
se
rtion
algorith
m
, two sets
are u
s
ed to store th
e
un-route
d
PO
Is. The set
C
stores th
e ca
n
d
idate POIs
of current p
a
th, and the
se
t
F
contain
s
the un-ro
uted
POIs which f
a
ils to in
se
rt into cu
rrent p
a
th. The rout
e set
R
is al
so
use
d
to save
the outp
u
t ro
ute. The
pro
posed i
n
serti
on al
gorit
h
m
is
pre
s
e
n
ted
as bel
ow. A
fter ru
nnin
g
t
h
e
route ge
ne
rat
i
on algo
rithm,
an initial solu
tion
S
can b
e
g
enerated.
Route G
ene
ration Algorith
m
:
3.2. SA-ba
s
e
d
Optim
i
za
tion
After ro
ute g
e
neratio
n
algo
rithm, we
ca
n
get
th
e initial solution for the minimum
numbe
r
of re
quired
sensors
pro
b
l
e
m in
swe
e
p
cove
ra
ge.
T
herefo
r
e, we
can
ap
ply
a metaheu
ri
stics
to
optimize thi
s
initial solution.
Simulated A
nneali
ng
(SA) is in
spi
r
ed
by an
nealin
g in m
e
tallu
rgy. Annealin
g is the
physi
cal process of increa
sing the
cryst
a
l size of a material an
d re
duci
ng the de
feats throu
g
h
a
controllabl
e
cooli
ng p
r
o
c
edure. SA
exhibits
goo
d pe
rform
a
n
c
e i
n
solvin
g combin
ato
r
ial
optimizatio
n probl
em
s, an
d in theory it conve
r
ge
s to
globally opti
m
al solutio
n
with pro
babili
ty 1.
After initial route g
ene
rati
on p
r
o
c
e
s
s i
n
VRPSC, S
A
algo
rithm i
s
a
pplied
to
archive a
fin
a
l
s
o
lution.
0
s
t
e
p
1
:
i
n
iti
liz
a
tio
n
:
;
s
t
e
p
2:
;
t
h
e
num
be
r
o
f
s
e
ns
o
r
s
a
t
t
a
che
d
t
o
c
u
r
r
e
nt
r
o
ut
e
1
step
3
:
creat
e
a n
e
w
r
o
u
t
e
,
w
h
ich
s
t
ar
t an
d
t
e
rm
i
n
a
t
e
w
i
th
step
4
:
se
l
ect
t
h
at
i
s
t
h
e
n
earest
P
O
I
to
u
CP
Fm
Rp
p
0
in
C
,
in
ser
t
i
n
to
step
5
:
ch
e
c
k
if
is
f
easib
l
e
t
o
eq
u
a
t
i
o
n
(2
f)
an
d
(
2
g
)
. I
f
i
t
d
o
es, d
e
l
e
t
e
p
f
r
o
m
C
,
g
o
t
o
step
6
;
o
t
h
e
r
w
i
s
e,
i
f
i
s
t
h
e o
n
ly
P
O
I
in
R
,
th
en
,
r
ep
eat
e cu
r
u
u
u
pp
R
R
pm
re
n
t
s
t
e
p
;
els
e
d
e
lete
p
fro
m
C
,
ad
d
p
to
F
.
step
6
:
if
C
i
s
em
p
t
y
,
o
u
t
p
u
t
R
an
d
c
h
eck
i
f
F
is em
p
t
y
.
i
f
so
, en
d
th
e alg
o
r
it
h
m
;
ot
h
e
r
w
i
s
e
C
F
;
got
o
s
t
e
p
2
.
e
l
s
e
got
o
s
t
e
p
7
.
st
uu
12
e
p
7:
ba
se
d
o
n
c
a
nd
c
s
e
l
e
c
t
p
a
nd i
n
s
e
r
t
p
i
n
t
o
R
.
g
o
t
o
s
t
e
p
5
uu
C
Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM
NIKA
ISSN:
2302-4
046
A Sweep Coverag
e
Sch
e
m
e
based on V
ehicl
e Ro
uting Problem
(Li
Shu)
2033
1) Algori
t
hm
Process
In ord
e
r to
a
c
curately
evaluate solution
s
which de
pe
nd up
on the
algorith
m
’s
di
fferent
states, the
o
b
jective fun
c
t
i
on
()
f
S
in SA is defined a
s
th
e total numb
e
r of mobil
e
sen
s
o
r
s to
achi
eve swee
p coverage a
m
ong POIs.
To red
u
ce the compl
e
xity
of the algorit
hm
, we set t
he startin
g
a
nd endi
ng te
mperature
to a fixed val
ue an
d
zero resp
ectively. Once a
ce
rtai
n num
ber of i
t
eration
s
a
r
e
carrie
d out
wi
thin
a certai
n tem
peratu
r
e
ra
ng
e, or
the
stat
e of a
solutio
n
maint
a
ins a
predefine
d
n
u
mbe
r
of tim
e
s,
the coolin
g
step i
s
p
e
rfo
r
m
ed by
red
u
ci
n
g
the
cu
rrent temperature.
A
geom
etric cooli
ng strate
gy
is a
dopted
a
nd the te
mpe
r
ature d
e
cre
m
ent facto
r
i
s
set to
a d
e
fa
ult value that
is le
ss tha
n
and
clo
s
e to one.
The de
cisio
n
wheth
e
r to
accept or
rej
e
ct a ne
w so
lution is mad
e
according t
o
a
probability function. The S
A
pr
ocess is
presented as
below.
SA Algorithm:
ma
x
st
e
p
1
:
initia
li
z
a
tio
n: o
b
t
a
in c
u
r
r
e
n
t so
lu
t
i
o
n
,
c
a
l
c
u
la
t
e
(
)
,
s
e
t i
n
it
ial t
e
m
p
er
st
e
p
2
:
initia
li
z
e
the
num
b
e
r o
f
unim
p
r
o
v
e
d ite
ra
tio
ns
=0
and the num
ber
o
f
i
t
era
Sf
S
ature
t
t
ma
x
m
a
x
t
i
o
ns
i
n
cu
rrent
t
e
m
p
erat
ure
=
0
s
t
e
p
3
:
i
f
(
=
=
|
|
)
,
got
o s
t
e
p
7
s
t
ep 4:
;
(
)
;
cal
cu
l
a
t
e
(
)
s
t
ep 5:
i
f
(
(
)
(
)),
accep
t
,
,
o
t
herw
i
s
e
st
e
p
6:
if (
(
(
)
-
(
))
/
)
S
n
e
i
gh
bor
S
f
S
fS
fS
S
S
S
fS
fS
t
mi
n
(
0
,
1
),
accep
t
,
, g
o
t
o
s
t
ep
3
s
t
ep
7:
,
(
)
,
o
u
t
p
u
t
,
end
S
A
;
o
t
h
e
rw
i
s
e g
o
t
o
s
t
ep
2
rand
S
S
S
tt
i
f
t
t
S
2) Neig
hbor
Gener
a
tion
For a m
e
tah
euri
s
tics, nei
ghbo
r ge
nera
t
ion plays a
key rol
e
in al
gorithm p
e
rfo
r
man
c
e.
Here, the pro
posed nei
ghb
or ge
neration
algorithm
i
s
comp
osed of
two pha
se
s:
deletion ph
a
s
e
and rei
n
sertio
n pha
se. Figu
re 1 de
scrib
e
s
the proce
ss of neighbo
r g
eneration.
(a) Cu
rre
nt Sol
u
ti
on
S
(b) Deletion p
hase
(c) Reinsertion p
hase and ne
w
solution
S
Figure 1. The
Proce
s
s of Neighb
or Ge
ne
ration
Deletion phase.
Once a nei
g
hbori
ng
soluti
on
S
is asked
from the nei
g
hborhoo
d of
curre
n
t soluti
o
n
S
,
/
POIs
in
S
will be del
eted f
r
om thei
r current routes, where
pre
s
e
n
ts the
cu
rre
nt
numbe
r of u
n
i
mprove
d iterations
and
is a wei
ght p
a
rameter
rel
a
te
d the total n
u
m
ber
of POIs.
Since
is a variabl
e and related to the numbe
r of
un
improve
d
iterations, we
ca
n ensu
r
e the
intensifi
c
ation
of SA. A del
eted POI
i
p
is
rand
omly
sel
e
cted
from
its route
,
()
jj
kR
, which is
also
rand
omly sel
e
cted fro
m
S
. I
f
i
p
is the only
POI in
j
R
,
,
()
jj
kR
will be simply del
eted. Thus, t
h
e
deleted probability for certain is
Evaluation Warning : The document was created with Spire.PDF for Python.
ISSN: 23
02-4
046
TELKOM
NIKA
Vol. 11, No. 4, April 2013 : 2029 – 2
036
2034
11
Pr
(
)
ii
j
j
j
pp
k
(5)
In this
way, t
he POI
whose route
contains
l
e
ss POI
s
has the
high
er probability to be
deleted. As a
result, we co
uld red
u
ce th
e numbe
r of
mobile no
de
s and incre
a
se
the chan
ce
s
to
get the bette
r optimi
z
atio
n sol
u
tion by
decrea
s
in
g
the numb
e
r
of route
s
in
a sol
u
tion. After
deleting
POIs
from
c
u
rrent s
o
lution
S
, we ca
n move f
o
rward to rei
n
sertio
n ph
ase
to gene
rate
new solutio
n
S
.
Rein
se
rtion p
hase.
In the phase,
the deleted
POIs will be reinse
rted i
n
to the existing
routes to generate
S
as follo
ws. F
o
r a delete
d
POI
i
p
, find an un-del
eted P
O
I
j
p
which h
a
s
the lea
s
t
,
ij
d
.
For the
existing ro
ute
(,
)
mm
kR
where
jm
p
, ins
e
rt
i
p
into
m
R
based
on the mea
s
u
r
eme
n
ts
1
c
and
2
c
.
Thus,
a ne
w scan seq
uen
ce
m
R
is ge
nera
t
ed. Then
cal
c
ulate
m
k
to mak
e
(,
)
mm
kR
feasibl
e
.
After all the deleted POIs a
r
e rei
n
serted,
the new solu
tion
S
is archived.
4. Performan
ce Ev
aluation
We
provid
e
simulatio
n
re
sults on th
e
perfo
rma
n
ce of VRPS
C with V
C
++
and al
so
impleme
n
t CSweep i
n
[6,
7] as a
co
mp
arison.
Sin
c
e
CSwe
ep d
o
e
s
n’t con
s
ide
r
the data d
e
livery
and ha
s no b
u
ffer con
s
trai
nt, the buffer size of mobil
e
node
s in CSweep i
s
infinite. In VRPSW,
sin
k
is t
r
eate
d
as
a no
rma
l
POI. When
acce
ssi
ng th
e sin
k
, mobil
e
nod
es
co
ul
d delivery the
data
in their buff
e
r. Du
ring t
he wh
ole si
mulation,
PO
Is are
rand
o
m
ly deploye
d
in an are
a
o
f
2
500
50
0
me
t
e
r
. The
req
u
ire
d
covera
ge ti
me inte
rval o
f
each POI i
s
rand
omly d
i
stribute
d
in
[
100
,
100
0]
se
con
d
s.
The
mobil
e
sen
s
ors
st
ay
20
se
nse
T
seco
nds at
any P
O
I for data
se
nsin
g a
nd
st
ay
20
tr
ans
T
se
con
d
s
at the sin
k
f
o
r data tran
smissi
on.
Fo
r all the POIs i
n
WSN, the
collected
data size
i
q
at
(0
)
i
pi
is a
co
nsta
nt value of
10
bytes. The
d
e
fault setting
for SA i
s
giv
en in
Table 1.
Table 1. The
Default Settings for SA
starting Tempe
r
a
t
ure
ma
x
t
100
final Temperatu
r
e
mi
n
t
0
decrement const
ant
0.9
the maximum of
unimproved itera
t
ions
max
100
the maximum of i
nner iterations
ma
x
20
Duri
ng
the
si
mulation,
we
focu
s o
n
th
e t
w
o
co
ntaints
of the mi
nimu
m num
be
r of
requi
re
d
sen
s
o
r
s
pro
b
l
e
m in swee
p
coverage.
We try to us
e the impa
ct of velocity of mobile no
de
s to
reflect the co
verage
contai
nt and the impact of bu
ffer size of mobil
e
node
s to re
flect the buffer
contai
nt. We evaluate two
measurement
s to ex
press the perfo
rma
n
c
e of VRPSC: the number of
requi
re
d mobi
le sen
s
o
r
nod
es an
d the ca
lculatio
n time co
st.
4.1. Impact of Velocit
y
of
Mobile Sensors
We first explore the im
pa
ct of velocity of
mobile no
des. In eleve
n
ran
domly g
enerated
POI topology
, whe
r
e the
numbe
r of P
O
Is chan
ge
s from 50 to
1
50, we
co
mp
are V
R
PSC
with
CSwe
ep_
with
_data_
delivery in the vari
ous m
obile
n
ode velo
city at 3m/s a
nd
7m/s. In the
s
e
simulatio
n
s, t
he buffer
si
ze of mobile
node
s in V
R
PSC is set a
s
12
0 bytes.
The sim
u
lati
o
n
results is
showed in Figure 2.
From Fi
gure
2 (a
), it is cl
ear to
see th
a
t, in all the scena
rio
s
, VRPSC requi
red le
ss
numbe
r of m
obile n
ode
s t
o
pe
rform
co
verage
ta
sk t
han
CSweep
whe
n
the ve
locity of mobi
le
node
s i
s
equ
al in
both
sch
e
mes.
Acco
rd
ing to Fi
gu
re
2 (b
), T
he va
rious velo
city of mobile
no
d
e
s
have little impact o
n
CS
weep. With th
e
numbe
r of P
O
Is in
crea
sin
g
linea
rly, the cal
c
ulatio
n time
co
st in
CS
we
ep h
a
s an
ex
pone
ntially growth. O
n
th
e
other ha
nd, t
he va
riou
s ve
locitie
s
of
mo
bile
Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM
NIKA
ISSN:
2302-4
046
A Sweep Coverag
e
Sch
e
m
e
based on V
ehicl
e Ro
uting Problem
(Li
Shu)
2035
node
s ma
ke
s a great im
pa
ct on the
cal
c
ulation cost o
f
VRPSC. This is b
e
cau
s
e
that, accordi
n
g
to Equation (2 g), the hig
her velo
city mobile no
de
s have, the more POIs
can
be cove
red i
n
a
certai
n route.
As a re
sult, there
are
m
o
re se
arch
op
eration
s
will
be
com
p
leted
to find
the
b
e
st
inse
rtion po
sition for the best inse
rtion POI
can
d
idate in the prop
osed route ge
nera
t
ion
algorith
m
. It is al
so
noti
c
e
d
that
with t
he n
u
mbe
r
o
f
POIs in
cre
a
sin
g
, the
ca
lculatio
n time
in
VRPSC al
so i
n
tende
d to in
cre
a
se expo
n
entially. Ho
wever, the calculation time
cost in VRPS
C is
less than in
CSwe
ep elev
en ran
domly
gene
rat
ed P
O
I topologie
s
, where the numbe
r of POIs
cha
nge
s fro
m
50 to 150, we comp
are VRPSC wi
th CSwee
p
_
w
ith_d
ata_d
e
livery in various
mobile
se
nso
r
s vel
o
citie
s
at 3m/s
and
7m/s. In the
s
e sim
u
lation
s, the buffer
size of m
obil
e
node
s in VRP
S
C is set as
120 bytes.
(a)
Numbe
r
of required
mobile sensor nodes
(b)
Calculation Time Cost
Figure 2. Impact of Velocit
y
of Mobile Node
s
4.2. Impact of Buffer Size of Mobile Sensors
The impa
ct of buffer size on mobile
nodes
i
s
al
so be inve
stigated. In the eleven
scena
rio
s
, th
e velo
city of
mobile
se
nso
r
s is fi
xed at,
and
the
buff
e
r
si
ze
on
m
obile
nod
es in
VRPSC is set as 30 bytes, 120 byte
s, and 56
0 bytes, respe
c
tively. Figure 3 sho
w
s the
simulat
i
o
n
re
sult
s
s
h
o
w
s
t
he
simulat
i
o
n
re
sult
s
wit
h
eleven scen
a
r
ios
in whi
c
h
velocity
of
m
obile
sen
s
o
r
s is fixed at
3 m/
s,
and th
e b
u
ffer
sizes on
mo
bile
sen
s
o
r
s
are
set to 3
0
bytes,120
bytes
and 56
0 bytes re
spe
c
tively.
(a) Nu
mber of
R
equired Mobile S
ensor Nodes
(b) Calculation T
i
me Cost
Figure 3. Impact of Buffer Size of Mobil
e
Nod
e
s
Acco
rdi
ng to Figure 3 (a
), the numbe
r o
f
r
equired mo
bile se
nso
r
n
ode
s be
come
s pretty
high when th
e buffer
size of mobile no
des e
qual
s to
30 bytes. Th
is is b
e
cau
s
e
the less buff
e
r
size mean
s t
he less POI can’t be
cove
red in a
cert
ain route. Th
erefo
r
e VRP
S
C has to
create
new
route
s
with additional
mobile no
de
s to complete
coverage.
When the value
of buffer size
is
pretty small, the buffer
con
s
traint play
s a main
rol
e
in route ge
ne
ration. It can be also foun
d in
Evaluation Warning : The document was created with Spire.PDF for Python.
ISSN: 23
02-4
046
TELKOM
NIKA
Vol. 11, No. 4, April 2013 : 2029 – 2
036
2036
Figure 3 (a) t
hat the numb
e
r of requi
re
d
mobile se
nsors in the val
ue of buffer si
ze eq
uals to
120
bytes g
r
o
w
s f
a
ster than it i
n
the valu
e o
f
buffe
r
size
equal
s to
56
0 bytes. T
h
is is b
e
cau
s
e t
he
buffer
con
s
tra
i
nt play le
ss i
m
porta
nt rol
e
with th
e
buff
e
r
size in
crea
sing. It
can
b
e
cl
ear to find
in
Figure 3 (b
)
whe
n
the buff
e
r si
ze e
qual
s to 30 bytes,
the cal
c
ulati
on time is mu
ch le
ss th
an i
t
in
the other co
n
d
itions. The reason is ea
ch route ca
n’t cover mo
re than 3 POIs whe
n
the value of
buffer
s
i
ze is s
e
t as
30 bytes
.
As
a
res
u
lt,
the n
u
m
ber
of se
arch o
peration
s
in b
o
th ro
ute
gene
ration
al
gorithm
an
d
SA algorith
m
is ve
ry
small
.
We
also n
o
t
iced th
at wit
h
the
numb
e
r of
POIs increa
si
ng, the cal
c
ul
ation time co
st increa
se e
x
ponentially.
5. Conclusio
n
In this pape
r, we study th
e sweep
cov
e
rag
e
in wi
re
less se
nsor
netwo
rks, wh
ich can
decrea
s
e th
e
netwo
rks
co
st by in
tro
d
u
c
ing m
obile
sen
s
o
r
no
de
s pe
riodi
cally
cove
r POIs in
surveill
an
ce
area. Th
e ke
y issue in sweep covera
ge
is how to schedul
e the trajecto
ry of mobile
node
s to
co
ver POIs
wi
th minimum
req
u
ire
d
m
obile n
ode
s.
Satisfying
POIs covera
ge
requi
rem
ent
and data
del
ivery are e
q
ually impor
ta
nt for mobile
node
s sch
e
duling in
sweep
coverage. In
this wo
rk,
a novel swe
ep cove
rag
e
sch
eme, na
med VRPSC, is prop
ose
d
to
compl
e
te sweep cove
ra
g
e
an
d data d
e
livery simult
aneo
usly.
V
R
PSC first generate a
n
initia
l
solutio
n
by i
m
provin
g Sol
o
mon I1
alg
o
rithm a
nd
o
p
timize thi
s
i
n
itial sol
u
tion
to archive fi
nal
solutio
n
of
swee
p covera
ge by Simul
a
ted Anne
alin
g. The
simul
a
tion re
sult
s show th
e p
r
op
ose
d
scheme h
a
s
much b
e
tter p
e
rform
a
n
c
e than CS
we
e
p
and ad
apts
well unde
r different co
ndition
s.
Referen
ces
[1]
M Cardei, J W
u
.
Covera
ge i
n
w
i
reless sens
o
r
netw
o
rks. Ilya
s M, Mahgou
b I /eds. Handb
o
o
k of Senso
r
Netw
orks
. Boca Raton: CR
C Press Inc. 200
4.
[2]
M Hefee
da,
M Bagh
eri.
Ef
ficient k-cov
e
r
age
al
gorith
m
s for w
i
reless
sensor
netw
o
rks.
School
of
Comp
uting Sci
ence, Simo
n F
r
aser Un
iversit
y
. 2006; 22.
[3]
S Kumar,
T
H
Lai, A Arora.
Barrier cov
e
ra
ge w
i
th w
i
reles
s
sensors
. Pro
c
eed
ings of A
C
M MobiC
o
m.
Colo
gn
e. 200
5: 284-2
98.
[4]
X
Ch
en, F
L
i
, L W
a
n
g
. F
a
u
l
t-T
o
lerant Met
hod
for D
e
tecting
Cov
e
rag
e
Holes
of W
i
re
l
e
ss Se
nso
r
Net
w
orks.
T
E
L
K
OMNIKA Indones
ian J
ourn
a
l of Electrica
l
Engi
neer
in
g
. 2012; 10(
4): 818
-826.
[5]
H Kotta, K Rantelo
bo, S T
ena. W
i
reless se
nsor net
w
o
rk for lan
d
sli
de m
onitor
i
ng i
n
Nu
sa T
engga
r
a
T
i
mur.
T
E
LKOMNIKA Indone
sian Jo
urna
l of Electrical E
ngi
neer
ing
. 2
011;
9(1): 9-18.
[6]
W
Cheng, M L
i
, K Liu, Y Li
u.
Sw
eep cover
age w
i
th
mo
bil
e
sens
ors
. P
r
o
c
e
e
d
i
n
g
s
o
f
th
e
2
0
0
8
IEEE
Internatio
na
l Parall
el a
nd Dist
r
ibute
d
Pr
oces
sing S
y
mp
osiu
m. Miami. 200
8: 1-9.
[7]
M Li, W
Cheng
, K Liu, Y He,
X Li. S
w
e
ep co
verag
e
w
i
th mo
bile se
nsors.
IEEE Transactions on Mobile
Co
mp
uting
. 2
0
11; 10(1
1
): 153
4-15
45.
[8]
Z
Z
hang, Y
C
hen
g, H C
h
e
n
g
, Q F
ang.
M
T
SP base
d
so
lutio
n
for
mi
ni
mu
m mob
ile
n
ode
nu
mber
prob
le
m in sw
e
ep conv
erg
e
of w
i
reless sens
or netw
o
rk
. Proceed
ings
of 20
11 Intern
ation
a
l
Confer
enc
e
on Com
puter S
c
ienc
e an
d Net
w
o
r
k T
e
chnolo
g
y
. H
a
rbi
n
. 201
1: 1827-
18
30.
[9]
HC C
hu, W
K
W
ang, Y
H
L
a
i.
Sw
eep
Co
verag
e
Mec
h
a
n
is
m for W
i
r
e
l
e
ss Se
nsor
N
e
tw
orks w
i
th
Approx
i
m
ate P
a
trol T
i
mes
. Procee
din
g
s of the 7th Internati
o
nal
C
onfer
ence
on Ubi
q
u
i
tous
Intelli
genc
e
and C
o
mputi
n
g
(
UIC). Xi’
an. 2
010: 82-
87.
[10]
C Z
hai, Y H
o
n
g
.
Sw
eep cov
e
rage
alg
o
rith
m and c
o
ver
age
time
esti
mati
o
n
for multi-
age
nt systems
.
Procee
din
g
s of
the 24th Ch
ine
s
e Contro
l an
d Deci
si
on C
onfe
r
ence (CC
DC).
T
a
i
y
u
an. 20
12
: 133-13
8.
[11]
J Du, YLi, H L
i
u, K Sha.
On Sw
eep Cov
e
rag
e
w
i
th Mini
mu
m Mo
bil
e
Sens
ors
. Procee
din
g
s of the 1
6
t
h
Internatio
na
l C
onfere
n
ce o
n
Parall
el a
nd Dist
r
i
bute
d
S
y
stem
s (ICPADS). Shan
gh
ai. 201
0:
283-2
90.
[12]
ML F
i
sher, R Jaikum
ar. A gener
aliz
ed
ass
i
gnm
ent he
uris
tic for vehicl
e routin
g.
Netw
orks
. 1
9
81;
11(2): 10
9-1
2
4
.
[13]
MM Solomo
n. Algorithms f
o
r the vehic
l
e
r
outing a
nd
sched
uli
ng pr
obl
ems
w
i
th time
w
i
n
d
o
w
constrai
nts.
Operatio
ns resear
ch
. 1987; 3
5
(2)
:
254-26
5.
Evaluation Warning : The document was created with Spire.PDF for Python.