On the Displacement for Covering a Unit Interval with Randomly Placed Sensors
Rafał Kapelkoa,1,∗, Evangelos Kranakisb,2
a

Department of Computer Science, Faculty of Fundamental Problems of Technology, Wrocław University of Technology, Poland
b School of Computer Science, Carleton University, Ottawa, ON, Canada

arXiv:1507.08923v3 [] 22 Jun 2016

Abstract
Consider n mobile sensors placed independently at random with the uniform distribution on a barrier represented as the unit
line segment [0, 1]. The sensors have identical sensing radius, say r. When a sensor is displaced on the line a distance equal to
d it consumes energy (in movement) which is proportional to some (fixed) power a > 0 of the distance d traveled. The energy
consumption of a system of n sensors thus displaced is defined as the sum of the energy consumptions for the displacement of the
individual sensors.
We focus on the problem of energy efficient displacement of the sensors so that in their final placement the sensor system
ensures coverage of the barrier and the energy consumed for the displacement of the sensors to these final positions is minimized
in expectation. In particular, we analyze the problem of displacing the sensors from their initial positions so as to attain coverage
of the unit interval and derive trade-offs for this displacement as a function of the sensor range. We obtain several tight bounds in
this setting thus generalizing several of the results of [10] to any power a > 0.
Keywords: barrier, displacement, distance, random, sensors,

1. Introduction

if the ith sensor is displaced a distance di , for i = 1, 2, . . . , n,
then the energy consumed by the whole system of n sensors is
Pn a
i=1 di .
In this paper we study the minimum total (or sum) energy
consumption (in expectation) in the movement of the sensors so
as to attain coverage of the unit segment when the energy consumed per sensor is proportional to some (fixed) power of the
distance traveled. The present study generalizes some known
results (see [10]) on the sensor displacement for a = 1 to arbitrary a > 0. Motivation for the extended model being proposed
is that the energy consumption induced by individual sensor
displacement may not be linear in this displacement, but rather
be dependent on some power of the distance traversed. Further,
the parameter a in the exponent may well represent various conditions of the surface of the barrier, e.g., friction, lubrication,
etc, which may affect the overall energy consumption of the
sensor system.

One of the most important problems in sensor networks is
minimizing battery consumption when accomplishing various
tasks such as monitoring an environment, tracking events along
a barrier and communicating. In this study, the environment
being considered consists of a line segment barrier (which for
simplicity is set to the unit interval [0, 1]), while the accompanying monitoring problem investigated is ensuring coverage of
the barrier in the sense that every point in the line segment is
within the range of a sensor.
We consider the case where the sensors are equipped with
omnidirectional sensing antennas of identical range r > 0; thus
a sensor placed at location x in the unit interval can sense any
point at distance at most r either to the left or right of x. The
initial placement of the sensors does not guarantee barrier coverage since the sensors have been placed initially independently
at random with the uniform distribution on a barrier. To attain
coverage of the line segment it is required to displace the sensors from their original locations to new positions on the line
while at the same time taking into account their sensing range
r. Further, for some fixed constant a > 0 if a sensor is displaced
a distance d the energy consumed by this sensor is considered
to be proportional to da . More generally, for a set of n sensors,

1.1. Related work
There is extensive literature about area and barrier (also
known as perimeter) coverage by a set of sensors (e.g., see
[1, 3, 15, 12, 14, 5]). The coverage problem for planar domains
with pre-existing anchor (or destination) points was introduced
in [4]. The deterministic version of the sensor displacement
problem on a linear domain (or interval) was introduced in [6].
Several optimization variants of the displacement problem were
considered.The complexity of finding an algorithm that optimizes the displacement depends 1) on the types of the sensors,
2) the type of the domain, and 3) whether one is minimizing
the sum or maximum of the sensor movements. For the unit
interval the problem of minimizing the sum is NP-complete if

∗ Corresponding author at: Department of Computer Science, Faculty of
Fundamental Problems of Technology, Wrocław University of Technology,
Wybrzeże Wyspiańskiego 27, 50-370 Wrocław, Poland. Tel.: +48 71 320 33
62; fax: +48 71 320 07 51.
Email addresses: rafal.kapelko@pwr.edu.pl (Rafał Kapelko),
kranakis@scs.carleton.ca (Evangelos Kranakis)
1 Research supported by grant nr S500129/K1102.
2 Research supported in part by NSERC Discovery grant.

1

is defined for all complex numbers c, d such as ℜ(c) > 0 and
ℜ(d) > 0. Moreover, for positive integer numbers c, d we have
!
c+d−1
−1
B(c, d) =
c
(2)
c

the sensors may have different ranges but is in polynomial time
when all the sensor ranges are identical [7]. The problem of
minimizing the maximum is NP-complete if the region consists
of two intervals [6] but is polynomial time for a single interval
even when the sensors may have different ranges [5]. Related
work on deterministic algorithms for minimizing the total and
maximum movement of sensors for barrier coverage of a planar
region may be found in [4].
More importantly, our work is closely related to the work
of [10] where the authors consider the expected minimum total displacement for establishing full coverage of a unit interval
for n sensors placed uniformly at random. Our analysis and
problem statement generalizes some of the work of [10] from
a = 1 to all exponents a > 0. A comprehensive study of sensor
displacement to arbitrary probability distributions using techniques from queueing theory can be found in the forthcoming
[11].

Let us define a function gc:d (x) = xc−1 (1 − x)d−1 on the interval
[0, 1]. We say that a random variable Xc,d concentrated on the
interval [0, 1] has the B(c, d) distribution with parameters c, d if
it has the probability density function f (x) = (B(c, d))−1 xc−1 (1−
x)d−1 . Hence,
Z t
1
gc:d (x)dx
(3)
Pr[Xc,d < t] =
B(c, d) 0
We will use the following notations for the rising and falling
factorial respectively [9]



for k = 0
1
k
n =

n(n + 1) . . . (n + k − 1) for k ≥ 1,



for k = 0
1
k
n =

n(n − 1) . . . (n − (k − 1)) for k ≥ 1.
hni nno
Let k , k be the Stirling numbers of the first and second kind
respectively, which are defined for all integer numbers such that
0 ≤ k ≤ n. The following two equations for Stirling numbers of
the first and second kind are well known (see [9, identity 6.10]
and [9, identity 6.13]):
X ( m)
(4)
xm =
(x)l
l
l
X "m#
(−1)m−l xl
(5)
(x)m =
l
l

1.2. Outline and results of the paper
Our work generalizes some of the work of [10] to the more
general setting when the cost of movement is proportional to a
fixed power of the distance displacement.
The overall organization of the paper is as follows. In Section 2 we provide several basic combinatorial facts that will be
used in the sequel. In Section 3 we prove combinatorially how
1
.
to obtain tight bounds when the range of the sensors is r = 2n
We show that the expected sum of displacement to the power a
is
 
!
a
1
1
2 !
,
+
O
a
a
a
2 2 (1 + a) n 2 −1
n2
when a is an even positive number , and in
!
1
Θ a −1 ,
n2

Assume that b is a constant independent of m. Then the following Stirling numbers
"
# "
# (
) (
)
m
m+b
m
m+b
,
,
,
(6)
m−b
m
m−b
m

when a is an odd natural number. In Section 4 we prove the
occurrence of threshold whereby the expected minimum sum
of displacements
 to the power a (a is positive natural number)
remains in Θ

1
provided
a
n 2 −1
−3/2

that r =

1
2n

+

f (n)
2 ,

where f (n) > 0

are polynomials
in the variable m and of degree 2b (see [9]).
DD EE
Let nk be the Eulerian numbers, which are defined for all
integer numbers such that 0 ≤ k ≤ n. The following three identities for Euler numbers are well known (see identities (6.42),
(6.43) and (6.44) in [9]):
X  m  (2m)! 1
(7)
=
(m)! 2m
l
l
(
) X ** ++
!
m
b
m+b−1−l
=
(8)
m−b
l
2b
l
"
# X ** ++
!
m
b
m+l
=
(9)
m−b
l
2b
l

and f (n) = o(n ). In Section 5 we study the more general
version of the sensors movement to the power a, where a > 0
6
1
. If r ≥ 2n
we first present the Algorithm 1 that uses
and r > 2n
expected

!a 
 1 ln n 2 


O  a −1
n
n2
total movement to power a, where a > 0. Finally, Section 6
provides the conclusions.
2. Basic facts
In this section we recall some known facts about special functions and special numbers which will be useful in the analysis
in the next sections. The Euler Beta function (see [13])
Z 1
B(c, d) =
xc−1 (1 − x)d−1 dx
(1)
0

2

Let d, f be non-negative integers. Notice that (see [9, identity
5.41])
!
d
X
(d)!(d)!
d (−1)l
=
(10)
l d + 1 + l (2d + 1)!
l=0

Observe that
(i − 1)d · i f =

x = n, m = l2 + 1 we deduce that
a− j

n
X
· ij
i − 12
j
n
(n + 1) j
i=1

 l 
n (i − 1)a− j−l1 1 1 i j 
X a − j! X

2


= nj


j

l
1
(n
+
1)
i=1
l1


 n
l2 j 
X a − j ! 1 !l1 X (a − j − l1 ) X
i
(i
−
1)


j


=n


j
a − j − l1 2
l2
i=1 (n + 1)
l1
l2


X a − j ! 1 !l1 X (a − j − l1 )

1
l
+1
j

2

n 
=n
l2 + j + 1
l2
a − j − l1 2

(i − 1)d · i f +1 − (i − 2)d · (i − 1) f +1
.
f +d+1

Applying this formula for i = 1 to n we easily derive
n
X
i=1

(i − 1)d · i f =

1
(n − 1)d · n f +1
f +d+1

(11)

We will also use Euler’s Finite Difference Theorem (see [8,
identity 10.1]). Assume that a is a natural number. Let f ( j) =
jm and m ∈ N. Then

l2

l1


!
a

X

if m < a
a
0
j
(−1) f ( j) = 

a
(−1) a! if m = a
j
j=0

!

!l1

i−


1 a− j
2

a− j
1
2
a
−
j
−
l
1
l1


(
X X a − j − l1 )"l2 + 1#

1
l
+
j
l
+1−l

3
2
3
× 
n  .
(−1)
l2 + j + 1
l2
l3
l
l

(12)

=

3. Tight bounds for total displacement to the power a when
1
r = 2n

X

3

2

Hence

n
X

In this section we extend Theorem 1 from [10] for the displacement to the power a, where a is a positive natural number.
1
are thrown uniformly and
Assume that n sensors with range 2n
independently at random in the unit interval and move from
1
, for
their current location to the anchor location ti = ni − 2n
i = 1, . . . , n. Notice that the only way to attain the coverage is
for the sensors to occupy the positions ti , for i = 1, . . . , n. We
prove that the expected
sum of displacement to the power a is
 
( a2 )! 1
1
+ O a2 , when a is an even positive number, and in
a
a
2 2 (1+a) n2 −1
n
1
Θ 2a −1 , when a is an odd natural number. We begin with the
n
following lemma which will be helpful in the proof of Theorem
2. It is worth pointing out that the proof of Lemma 1 is technically complicated. Our proof of Lemma 1 proceeds along the
P (i− 12 )a− j ·i j
following steps. Firstly, we reduce the inner sum ni=1 (n+1)
j
Pn (i−1)l2 i j
to the sum i=1 (n+1) j which is known (see equation (11)).
Then we have the following sum

i=1

n

j



(n +

· ij

1) j

=

a+1
X

Ca+1−k na+1−k .

k=0

Now we prove that Ca+1−k is the polynomial of variable a − j
of degree less than or equal 2k. Observe that
Ca+1−k
X
=

! !l1
a− j
1
a
−
j
−
l
2
1
l1

 (

X a − j − l1 )" l2 + 1 #
1
l
−a+k+
j


2
(−1)
× 

l
a
+
1
−
k
−
j
l
+
j
+
1
2
2
l2
X a − j ! 1 !l1
=
a − j − l1 2
l1
 (

)"
#
l4
X

a
−
j
+
l
−
k
+
1
(−1)
a
−
j
−
l
4
1
 .
× 
a − j + l4 − k
a + 1 − k − j a + 1 − k + l4 
l
4



!
a+1
a
X
X
1 a
j
(−1)
Ca+1−k na+1−k ,
a j
n
k=0
j=0
where Ca+1−k is the polynomial of variable a − j of degree less
than or equal 2k. Finally, the asymptotic follows from Euler’s
Finite Difference Theorem (see equation ( 12)).
Lemma 1. Assume that a is an even positive number. Then
a− j

 
!
!
a
a X
n
X
· ij
i − 21
1 a
1
1
2 !
j j
+
O
(−1)
n
=
a
a
a
na j
2 2 (1 + a) n 2 −1
n2
(n + 1) j
j=0 i=1
Proof. As a first step, we evaluate the inner sum. Let j ∈
{0, . . . , a}. Applying equation (4) for x = i − 1, m = a − j − l1 ,
and equation (11) for d = l2 , f = j, as well equation (5) for


Since a−a−j−lj 1 is the polynomial of variable a − j of degree l1 ,
n a− j−l o
1
of variable a − j − l1 of degree 2(k −
a− j+l4 −k is hthe polynomial
i
a− j+l4 −k+1
l1 − l4 ) and a+1−k− j is the polynomial of variable a + 1 − j − k
of degree 2l4 (see (6)), we obtain that, Ca+1−k is the polynomial
of variable a − j of degree less than or equal 2k.
Now we give the coefficient of the term j2k in the polynomials Ca+1−k . Applying identity (8) for m = a − j, b = k − l4 and
identity (9) for m = a − j + l4 − k + 1, b = l4 we observe that the
coefficient of the term j2k in the polynomials Ca+1−k equals


X X ** k − l4 ++

1


da+1,k =
j1
(2(k − l4 ))! 
j1
l4
 ** ++

X l4
1 
(−1)l4

× 
j2 (2l4 )! a + 1 − k + l4
j
2

3

for j ∈ {0, 1, . . . , a} and i ∈ {1, 2, . . . , n}. Observe that

Therefore, from equation (7) we have
da+1,k =

!
k
(−1)l4
1 X k
.
k
2 k! l =0 l4 a + 1 − k + l4

D(a)
i =

a
2

From the definition of Beta function and identity (2) we get
!

1
=
a .
(1 + a)! 2 2

da+1, a2

D(a)
i, j

We now apply equation ( 12)) in order to get

!

a

X
if 2k < a

a
0 a
a
.
(−1) jCa+1−k = 
!(−1)
)
(


j
 222a (1+a) if 2k = a
j=0

This finishes the proof of Theorem 2.


a− j
!
a X
n
X
i − 21
· ij
1 a
j j
(−1) n
na j
(n + 1) j
j=0 i=1
!
a+1 a+1−k X
a
X
a
n
=
(−1) j Ca+1−k
na j=0 j
k=0
 
!
a
1
1
2 !
+O a .
= a
a
2 2 (1 + a) n 2 −1
n2

3.2. Tight bound for total displacement to the power a when
1
and a is an odd natural number
r = 2n
Theorem 3. Let a be an odd natural number. Assume that n
mobile sensors are thrown uniformly and independently at random in the unit interval. The expected sum of displacements to
the power a of all sensors to move from their current location
1
to anchor location ti = ni − 2n
, for i = 1, . . . , n, respectively is


1
Θ 2a −1 .
n

This completes the proof of Lemma 1.

Proof. Let a be an odd natural number. Firstly, observe that the
result for a = 1 follows from [[10], Theorem 1]. Therefore,
we may assume that a ≥ 3. Let D(a)
i be the expected distance
to the power a between Xi and the ith target anchor location,
1
ti = ni − 2n
, on the unit interval, hence given by:

3.1. Tight bound for total displacement to the power a when
1
r = 2n
and a is an even positive number
Theorem 2. Let a be an even positive number. Assume that
n mobile sensors are thrown uniformly and independently at
random in the unit interval. The expected sum of displacements
to the power a of all sensors to move from their current location
1
to the anchor location ti = ni − 2n
, for i = 1, . . . , n, respectively
is
 
!
a
1
1
2 !
.
+
O
a
a
a
2 2 (1 + a) n 2 −1
n2

D(a)
i

=i

n
i
n
i

!Z

n
X

!Z

1

|ti − x|a gi:n−i+1 (x)dx.

0

a
 n
 a+1
X  (a)  a+1

a 

D
≤ 

i

i=1

1
 n  a+1
X 
 1

i=1

a
 n
 a+1
X  (a)  a+1

1
a 
 n a+1
= 
.
Di

(13)

i=1

Next we use Hölder inequality for integrals with parameters
a+1
a , a + 1 and get

1

|x − ti |a gi:n−i+1 (x)dx

Z

0
1

(ti − x)a gi:n−i+1 (x)dx.
0

!
!
Z 1
n a− j a
j
(−1)
= i ti
x j gi:n−i+1 (x)dx
j
i
0

D(a)
i

i=1

Now we define
D(a)
i, j

n
=i
i

First we prove the upper bound. We use discrete Hölder inequality with parameters a+1
a , a + 1 and get

Proof. Let Xi be the ith order statistic, i.e., the position of the ith
sensor in interval [0, 1]. We know that the random variable Xi
has the B(i, n − i + 1) distribution. For example see [2]. Assume
that a is an even positive number. Let D(a)
be the expected
i
distance to the power a between Xi and the ith sensor anchor
1
, on the unit interval, hence given by:
location, ti = ni − 2n
D(a)
i =i

a− j

!
· ij
i − 12
1 a
j j
= a (−1) n
.
n j
(n + 1) j

Hence applying Lemma 1 we conclude that
 
!
a
n X
a
a X
n
X
X
1
1
2 !
(a)
(a)
+O a .
Di, j =
Di, j = a
a
2 2 (1 + a) n 2 −1
n2
i=1 j=0
j=0 i=1

Putting everything together, we finally obtain

!Z

D(a)
i, j .

j=0

4

Using identity (10) we deduce that
 

a
X

1

!
n
|ti − x| gi:n−i+1 (x)i dx
i
a
! ! a+1
Z 1
a+1
n
(|ti − x|a ) a gi:n−i+1 (x)i dx
,
≤
i
0
a

0

so
4



D(a)
i

 a+1
a

≤ D(a+1)
i

(14)

1
+ f (n),
Proof. Let a be a natural number. Assume that r = 2n
−3/2
where f (n) > 0 and f (n) = o(n
).
Throughout
the
proof
we


 
1
(a) 1
use the fact that E
2n ∈ Θ n a2 −1 .


First we prove the upper bound E (a) (r) ∈ O 2a1−1 . This is
n
easy because we can displace the sensors to the anchor loca1
tions ti = ni − 2n
, for i = 1, 2, . . . , n at a total displacement


1
1
since in this case the
cost of O 2a −1 . This suffices if r ≥ 2n
n
contiguous coverage is assured.



Putting together Theorem 2 for a := a + 1 and equations (13),
(14) we deduce that
n
X

D(a)
i

1

≤ Θ
n

i=1

a+1
2 −1

a
!! a+1

n

1
a+1

1

=Θ

a

n 2 −1

!

.

Next we prove the lower bound. We use discrete Hölder ina
equality with parameters a−1
, a and get
n
X

D(a−1)
i

i=1

 a−1
 n
a  a
X  (a−1)  a−1

≤ 
D

i

i=1

 n  a1
X 
 1

Next we prove the lower bound E (a) (r) ∈ Ω 2a1−1 . We would
n
like to know how much we can reduce the sum of displacements
1
1
to 2n
+ f (n)
if we change the radius from 2n
2 , where f (n) > 0 and
−3/2
f (n) = o(n ). Let bi be the sequence such that 0 ≤ b1 ≤
b2 ≤ . . . bn ≤ 1, b1 ≤ r, 1 − bn ≤ r and bi+1 − bi ≤ r, for
i = 1, . . . , n − 1. Let Xi be the position of the ith sensor in the
interval [0, 1]. It is sufficient to show that
!
n
X


1
E |Xi − bi |a ∈ Ω a −1 .
n2
i=1

i=1

 n
 a−1
a  a
X  (a−1)  a−1
1

= 
Di
 n a

(15)

i=1

Next we use Hölder inequality for integrals with parameters
a
a−1 , a and get
Z

1

|ti − x|

a−1

0

≤

Z

1

0

so



!
n
gi:n−i+1 (x)i dx
i

|ti − x|



a−1

a
 a−1

 a
(a−1) a−1

Di

! ! a−1
a
n
,
gi:n−i+1 (x)i dx
i

Let us recall that ti =
inequality (for a ∈ N+ )

i=1

D(a)
i

≤ D(a)
i

(16)

n
X
i=1

1

a−1

a
!! a−1

n

i=1

i=1

n

n
X


E |Xi − ti |a ∈ Θ

−1
a−1

i=1

a is positive natural number, remains in Θ

a

n 2 −1
−3/2

where f (n) > 0 and f (n) = o(n

a

n 2 −1

!

(18)

Clearly, if the ith sensor occupies position bi , for i = 1, 2, . . . , m,
then the distance between consecutive sensors is equal to 2r.
Observe that bi − ti ≤ bi+1 − ai+1 , for i = 1, 2, . . . , m. and

In this section we prove the occurrence of threshold whereby
the expected minimum sum of displacements
a, where

 to power
1

1





1
Assume that bi = min (i − 1) n1 + f (n) + 2n
+ f (n)
,
1
, for i =
2
1, 2, . . . , n. Let m + 1 be the smallest positive i, such that
!
1
f (n)
1
+ f (n) +
+
> 1.
(i − 1)
n
2n
2

4. A Threshold on the minimum displacement

+

n

X 


 X
E |Xi − bi |a ≥ 2−a+1
E |Xi − ti |a −
|bi − ti |a (17)

By Theorem 2, Theorem 3 we know

This finishes the proof of the lower bound and completes the
proof of Theorem 3.

r=

for i = 1, 2, . . . , n. Using the

i=1

n 2 −1
!
1
= Θ a −1 .
n2

f (n)
2 ,

1
2n ,

we get

 a
 n
X (a−1)  a−1 −1

Di  n a−1
≥ 
= Θ

1
2n

−

|Xi − ti |a ≤ 2a−1 (|Xi − bi |a + |bi − ti |a )

Putting together Theorem 2 for a := a − 1 and equations (15),
(16) we obtain
n
X

i
n

max |bi − ti |a ≤ na ( f (n))a .

i=1,2,...,n

provided that

Hence,

).

Definition 4. Given a, r we denote by E (a) (r) the expected minimum sum of displacement to the power a (where a is positive
natural number) of n sensors with range r.

n
X

|bi − ti |a ≤ na+1 ( f (n))a .

i=1

Theorem 5. Assume that a is a natural number. Let r > 0 be
1
+ f (n)
, where f (n) > 0 and
the range of the sensors. If r = 2n

2
1
−3/2
(a)
f (n) = o(n ), then E (r) ∈ Θ a2 −1 .
n

5

Therefore, we conclude that for all sequences bi , such that 0 ≤
b1 ≤ b2 ≤ . . . bn ≤ 1, b1 ≤ r, 1 − bn ≤ r and bi+1 − bi ≤ r, for
i = 1, . . . , n − 1,
!
n
X
1
a
a+1
a
|bi − ti | ≤ n ( f (n)) = o a −1
(19)
n2
i=1

Putting together (17), (18) and (19) we get
n
X
i=1



E |Xi − bi |a ≥ 2−a+1 Θ

1
a

n 2 −1

!

−o

Putting together Theorem 2, Theorem 3 and equations (20),
(21) we deduce that
1
a

n 2 −1

!

=Θ

1
a

n 2 −1

!

.

n
X
i=1

This is sufficient to complete the proof of Theorem 5.

Di(a)

1

≤ Θ
n

⌈a⌉
2 −1

!! ⌈a⌉a

n

⌈a⌉−a
⌈a⌉

=Θ

1
a

n 2 −1

!

.

This finishes the proof of Theorem 6.
5. Upper bounds for total displacement when r >

1
2n

Now we give a lemma which indicates how to scale the results of Theorem 6 to intervals of arbitrary length.

Now we study a more general version of the sensor movement to power a, where a > 0. Suppose that n sensors with
radius r = 2nf are thrown randomly and independently with
the uniform distribution in the unit interval. The question is
how to estimate the total expected movement to the power a for
f > 1? If f > 6 we present Algorithm 1 that uses expected
 a
O 2a1−1 lnnn 2 , total movement to power a, where a > 0. The
n
correctness of the algorithm is derived from Theorem 8.
We begin with a theorem which indicates how to apply the
results of Theorem 2 and Theorem 3 to displacements to the
fractional power a.

Lemma 7. Let a > 0. Assume that m mobile sensors are thrown
uniformly and independently at random in the interval of length
x. The sensors are to be moved to equidistant positions (within
the interval) at distance x/m from each other. Then the total


expected movement to the power a of the sensors is O

i
n

−

1
2n ,

for i = 1, . . . , n, respectively is O

1
a
n 2 −1

movement to the power a in the unit interval is in O 1a2 −1 .
m
Now by multiplying their coordinates by x we get the desired
result.
Our upper bound on the total sensor movement to power a is
based on the Algorithm 1.

.

Algorithm 1 Displacement to the power a when a > 0, p =
9
3
4 (2 + a), q = 4 (2 + a), x0 is the real solution of the equation
x
=
3
such
that x0 ≥ 3
9
(2+a) ln x

Proof. By Theorem 2 and Theorem 3 we may assume that a >
0 and a < N+ . Let D(a)
i be the expected distance to the power a
1
between Xi and the ith anchor location, ti = ni − 2n
, on the unit
interval, hence given by:
D(a)
i

n
X

4

Require: n ≥ ⌈x0 ⌉ mobile sensors with identical sensing radius r = 2nf , f > 6 placed uniformly and independently at
random on the interval [0, 1]
Ensure: The final positions of sensors to attain coverage of the
interval [0, 1]
1: Divide the interval into subintervals of length j 1n k ;

!Z 1
n
=i
|ti − x|a gi:n−i+1 (x)dx.
i 0

D(a)
i

i=1

 n
a
X  (a)  ⌈a⌉a  ⌈a⌉

≤ 
D
i

i=1

 n  ⌈a⌉−a
X  ⌈a⌉
 1

p ln n

⌈a⌉
a ,

Then we use discrete Hölder inequality with parameters
⌈a⌉
⌈a⌉−a and get

1j n k
3 n

2:

if there is a subinterval with fewer than

3:
4:

moves all n sensors to positions that are equidistant;
else
in each subinterval choose ⌊q ln n⌋ sensors at random and
move the chosen sensors to equidistant position so as to
cover the subinterval;
end if

sensors then

p ln n

5:

i=1

a
 n
X  (a)  ⌈a⌉a  ⌈a⌉ ⌈a⌉−a
 n ⌈a⌉

= 
Di

.

Proof. Assume that m sensors are in the interval [0, x]. Then
multiply their coordinates by 1/x. From Theorem 6 the

 total

Theorem 6. Let a > 0 . Assume that n mobile sensors are
thrown uniformly and independently at random in the unit interval. The expected sum of displacements to the power a of all
sensors to move from their current location to anchor
 location
ti =

xa
a
m 2 −1

6:

(20)

i=1

Next we use Hölder inequality for integrals with parameters
⌈a⌉
⌈a⌉−a and get
Z

0

1

Theorem 8. Let a > 0, f > 6 and n ≥ ⌈x0 ⌉, where x0 is the
x
solution of the equation 9 (2+a)
= 3 such that x0 ≥ 3. Assume
ln x

⌈a⌉
a ,

4

that n sensors of radius r = 2nf are thrown randomly and independently with uniform distribution on a unit interval. Then
the total expected movement
 to power
 a of sensors required to

!
n
|ti − x| gi:n−i+1 (x)i dx
i
! ! ⌈a⌉a
Z 1
⌈a⌉
n
a a
(|ti − x| ) gi:n−i+1 (x)i dx ,
≤
i
0
a

so


D(a)
i

 ⌈a⌉a

≤ D(⌈a⌉)
i

cover the interval is in O

a
1
( ln n ) 2
a
n 2 −1 n

.

Proof. Assume that a > 0. Let p = 49 (2 + a) and q = 34 (2 + a),
x
= 3 such that x0 ≥ 3.
x0 is the solution of the equation 9 (2+a)
ln x
4
n
First of all, observe that p ln(n) > 3 for n ≥ ⌈x0 ⌉. We will prove

(21)
6

Hence,

that the
movement to power a of Algorithm 1 is

 total expected
in O

a
( ln n ) 2
a
n 2 −1 n

1

1 n
n
j
k≤j
k−
n
n
3

.

There are two cases to consider.
Case 1: There exists a subinterval with fewer than

p ln n

1j n k
3 n

sensors.
1j n k
3 n .

n
p ln n

p ln n

Hence it is possible to choose ⌊q ln n⌋ sensors at random in each
subinterval with more than 31 j nn k sensors. Let us consider the
p ln n
sequence
$
%
6
n
an = ⌊q ln n⌋
for n ≥ ⌈x0 ⌉.
n p ln n
Applying inequality ⌊x⌋ > x − 1 we see that
!
!
p ln n
1
1−
an > 2 1 −
q ln n
n

n
p ln n

sensors is less than e−(1+ 2 ) ln n <
Chernoff bound
a

1
a
n1+ 2

. Specifically we use the
2

m=

j n

n
p ln n

Pr[X < (1 − δ)m] < e−δ m/2 ,
q
j
k
j
k
(2+a) ln n
n
n
k, δ =
n
p ln n . As there are p ln n subinter-

vals, the event that one has fewer than
s
(2 + a)n ln n
n
j
j
k−
k .

(22)

n
p ln n

Observe that
p ln n 1
1
1
≤ ,
≤
for n ≥ ⌈x0 ⌉
n
3 q ln n 4

(24)

p ln n

p ln n

From the inequality ⌊x⌋ ≤ x we deduce that, ⌊q ln n⌋ ≤

n
p ln n

the probability that a given subinterval has fewer than
s
n
(2 + a)n ln n
j
j
k−
k

n

1j n k
3 n

(2 + a)n ln n
j
k

The number of sensors falling in a subinterval is a Bernoulli
process with probability of success j 1n k . By Chernoff bounds,

p ln n

sensors.
 In this case the total expected movement to power a is

1
O 2a −1 by Theorem 6.
Case 2: All subintervals contain at least

p ln n

s

n
p ln n

sensors occurs with probability less than
tion (24) completes the proof of Claim 9.

(23)

j

n
p ln n
a
n1+ 2

k

. This and Equa-

Using Claim 9 we can upper bound the total expected movement to power a as follows:
k 
j

! 2a   j n k 
!
n


1 − p ln n  O  1 ln n  +  p ln n  O 1
a 
a
  1+ 2a 

 2a −1 n
n1+ 2 
n
n
n 2 −1

!a 
 1 ln n 2 
 ,

= O  a −1
n
n2

Putting together Equation (22) and Equation (23) we get
$
%
n
f
≥ an > 1.
⌊q ln n⌋
n p ln n
Therefore, ⌊q ln n⌋ chosen sensors are enough to attain the coverage. By the independence of the sensors positions, the ⌊q ln n⌋
chosen sensors in any given subinterval are distributed randomly and independently with uniform distribution over the
subinterval of length j 1n k . By Lemma 7 the total expected

which proves Theorem 8.

p ln n

movement to power a inside each subinterval is


!
a
 1

1
(ln n) 2




O  j
(ln n) .
ka
 = O
a
n
na
⌊q ln n⌋ 2 −1 

6. Conclusion
In this paper we studied the expected minimum total (or sum)
energy consumption in the movement of sensors with identical range when the energy consumed per sensor is proportional
to some (fixed) power of the distance traveled. We obtained
bounds on the expected minimum energy consumed depending
on the range of the sensors.

p ln n

k
j
Since, there are p lnn n subintervals, the total expected
movement
to power a over all subintervals must be in

  2a 
1
ln n
.
O 2a −1 n
n

It remains to consider the probability with which each of
these cases occurs. The proof of the theorem will be a consequence of the following Claim.
Claim 9. Let p =
1j n k
3 n
p ln n

9
4 (2

References
[1] A.A. Abbasi, M. Younis, and K. Akkaya. Movement-assisted connectivity restoration in wireless sensor and actor networks. Parallel and Distributed Systems, IEEE Trans. on, 20(9):1366–1379, 2009.
[2] B. Arnold, N. Balakrishnan, and H. Nagaraja. A first course in order
statistics, volume 54. SIAM, 1992.
[3] P. Balister, B. Bollobas, A. Sarkar, and S. Kumar. Reliable density estimates for coverage and connectivity in thin strips of finite length. In Proc.
of MobiCom’07, pages 75–86, 2007.
[4] B. Bhattacharya, M. Burmester, Y. Hu, E. Kranakis, Q. Shi, and A. Wiese.
Optimal movement of mobile sensors for barrier coverage of a planar
region. TCS, 410(52):5515–5528, 2009.

+ a). The probability
that fewer than
k
j

sensors fall in any subinterval is <

n
p ln n
1+ a
n 2

.

Proof. (Claim 9) First of all, from the inequality ⌊x⌋ ≤ x we get
s
$
%
2
(2 + a) ln n
n
≤ .
n
p ln n
3
7

[5] D. Chen, Y. Gu, J. Li, and H. Wang. Algorithms on minimizing the maximum sensor movement for barrier coverage of a linear domain. Algorithm
Theory–SWAT 2012, pages 177–188, 2012.
[6] J. Czyzowicz, E. Kranakis, D. Krizanc, I. Lambadaris, L. Narayanan,
J. Opatrny, L. Stacho, J. Urrutia, and M. Yazdani. On minimizing the
maximum sensor movement for barrier coverage of a line segment. ADHOCNOW, pages 194–212, 2009.
[7] J. Czyzowicz, E. Kranakis, D. Krizanc, I. Lambadaris, L. Narayanan,
J. Opatrny, L. Stacho, J. Urrutia, and M. Yazdani. On minimizing the
sum of sensor movements for barrier coverage of a line segment. ADHOCNOW, pages 29–42, 2010.
[8] H. Gould and J. Quaintance.
Tables of Combinatorial Identities
(From the seven unpublished manuscripts of H. W. Gould), volume 4.
http://www.math.wvu.edu/˜gould/Vol.4.PDF, May 3, 2010.
[9] R. Graham, D. Knuth, and O. Patashnik. Concrete Mathematics A Foundation for Computer Science. Addison-Wesley, Reading, MA, 1994.
[10] E. Kranakis, D. Krizanc, O. Morales-Ponce, L. Narayanan, J. Opatrny,
and S. Shende. Expected sum and maximum of displacement of random
sensors for coverage of a domain. In Proceedings of the 25th ACM symposium on Parallelism in algorithms and architectures, pages 73–82. ACM,
2013.
[11] E. Kranakis and G. Shaikhet. Sensor allocation problems on the real line.
Journal of Applied Probability, 2016 (to appear).
[12] S. Kumar, T. H. Lai, and A. Arora. Barrier coverage with wireless sensors.
In Proceedings of the 11th annual International Conference on Mobile
Computing and Networking, pages 284–298. ACM, 2005.
[13] NIST
Digital
Library
of
Mathematical
Functions.
http://dlmf.nist.gov/8.17.
[14] A. Saipulla, C. Westphal, B. Liu, and J. Wang. Barrier coverage of linebased deployed wireless sensor networks. In INFOCOM, pages 127–135.
IEEE, 2009.
[15] C. K. Seow, W. K. G. Seah, and Z. Liu. Hybrid mobile wireless sensor network cooperative localization. In Proceedings of IEEE 22nd Int.
Symposium on Intelligent Control, pages 29–34, 2007.

8

