# On the Robot Assisted Movement in Wireless Mobile Sensor Networks

Sajal K. Das111This work of S. K. Das was partially supported by NSF grants
CNS-1850851, OAC-1725755, OAC-2104078, and SCC-1952045<EMAIL_ADDRESS>Rafał
Kapelko222Supported by Polish National Science Center (NCN) grant
2019/33/B/ST6/02988<EMAIL_ADDRESS>Department of Fundamentals of
Computer Science, Wrocław University of Science and Technology, Poland
Missouri University of Science and Technology, USA

###### Abstract

This paper deals with random sensors initially randomly deployed on the line
according to general random process and on the plane according to two
independent general random processes. The mobile robot with carrying capacity
$k$ placed at the origin point is to move the sensors to achieve the general
scheduling requirement such as coverage, connectivity and thus to satisfy the
desired communication property in the network. We study tradeoffs between the
energy consumption in robot’s movement, the numbers of sensors $n$, the sensor
range $r$, the interference distance $s$, and the robot capacity $k$ until
completion of the coverage simultaneously with interference scheduling task.
In this work, we obtain upper bounds for the energy consumption in robot’s
movement and obtain the sharp decrease in the total movement cost of the robot
so as to provide the coverage simultaneously with interference requirement.

###### keywords:

Sensors, Robot, Random process, Coverage, Interference

##  1 Introduction

A wireless sensor network (WSN) typically consists of a large number of sensor
nodes deployed randomly or according to some well defined distribution over a
region of interest to measure and observe the physical phenomena or events
[28, 16, 1, 27, 32]. There exists a wide variety of applications of WSNs such
us border security and surveillance, wildlife habitat monitoring,
environmental monitoring (e.g., underwater, earthquake or seismic activities),
intrusion detection, diagnostics in industrial process control, health
structure of buildings or bridges, and so on. In some situations, the
geographic terrain could be difficult to reach implying the manual deployment
of sensors in deterministic patterns is dangerous or even impossible.
Moreover, due to the terrain, wind and other factors, random deployment may be
the only one option.

In WSNs, a fundamental problem to study is the energy consumption. It is well
known that the mobile sensors consume much more energy during the movement
than that during the sensing or communication process [7]. Thus, how to
minimize the transportation cost of sensors to provide the general scheduling
requirement such as connectivity, coverage in the network has great
significance.

In this study, we focus on the reallocation of random sensors by the mobile
robot. Assume that $n$ sensors are initially randomly deployed on the line by
dropping them from an aircraft according to a general random process and on
the two-dimensional plane according to two independent general random
processes. The robot is placed at a start position and can move the sensors
from any initial position to any final position on the line and on the two-
dimensional plane. The carrying capacity $k$ of the robot is the maximum
number of sensors the robot can carry at a time to deposit all or part of them
at any time and to any suitable position it chooses (see Assumption 1).

The aim of this article is to introduce and analyze the transportation cost
for the robot assisted sensor displacement and compare it with the
transportation cost for the autonomous sensor displacement to provide the
general scheduling requirement in the network such as coverage, connectivity,
or coverage simultaneously with interference. We compare the energy
consumption in robot assisted sensor displacement and the case each sensor
moves autonomously to reduce the transportation cost of mobile sensors for
coverage and interference requirement.

###  1.1 Contributions of This Paper

In this paper we introduce novel robot assisted movement in wireless mobile
sensor networks to reduce the energy consumption of transportation cost for
sensors. In particular, the mobile robot with carrying capacity $k$ moves the
sensors to provide the general scheduling requirement in the network (see
Assumption 1 in Section 2).

The objective is to compare the robot assisted transportation cost with the
autonomous sensor displacement when the sensors are randomly placed on the
line (see Definition 1 and Definition 2 in Section 2) and on the plane (see
Definition 3 and Definition 4 in Section 3) according to general random
process. To this aim, we make the following three novel theoretical
contribution.

  1. 1.

For both sensors on the line and on the plane we present the relationship
between the transportation cost of the robot and the autonomous sensor
displacement which is valid for every desired communication property (see
Theorem 2 in Section 2 and Theorem 3 in Section 3)

  2. 2.

When the $n$ sensors with identical sensing radius $r_{1}$ initially randomly
displaced on the $[0,\infty)$ according to Poisson process with arrival rate
$\lambda>0$ (see Definition 5 and Definition 6 in Subsection 4.1) we derive
tradeoffs between the energy consumption in robot’s movement, the number of
sensors $n$, the sensing radius $r_{1}$, interference distance $s$, the robot
capacity $k$ until completion of the coverage and interference requirement
(see Theorem 4 in Subsection 4.1 and Table 2 in Section 4 for a summary).

  3. 3.

For $n$ sensors with identical square sensing radius $r_{2}$ that are randomly
placed on the plane according to two identical and independent Poisson
processes each with arrival rate $\lambda>0$ (see Definition 7 and Definition
8 in Subsection 4.2) we derive tradeoffs between the energy consumption in
robot’s movement, the number of sensors $n$, the square sensing radius
$r_{2}$, interference distance $s$, the robot capacity $k$ until completion of
the coverage and interference requirement (see Theorem 5 in Subsection 4.2 and
Table 2 in Section 4 for a summary).

Table 2 summarized the results obtained for the random sensors on the line.

When the $n$ sensors with identical sensing radius $r_{1}$ are randomly
displaced on the $[0,\infty)$ according to Poisson process with arrival rate
$\lambda=n,$ we have the following results.

  * 1.

Let $a\in[1,2].$ For the sensing radius $r_{1}=\frac{1}{2n}$ and the
interference distance $s=\frac{1}{n}$, the expected $T^{(a,1)}_{(AS)}$
transportation cost for the autonomous sensor displacement xis
$\Theta\left(n^{1-\frac{a}{2}}\right)$ (see Table 1); and the expected
$T^{(a,1)}_{(RS)}$-transportation cost for the robot assisted sensor
displacement is $\frac{O\left(n^{\frac{a}{2}}\right)}{k^{a}},$ provided that
$n^{1-\frac{1}{a}}\leq k\leq\sqrt{n}$ (see Table 2).

Hence the robot with $\lceil\sqrt{n}\rceil$-capacity reduces the
transportation cost from $\Theta\left(n^{1-\frac{a}{2}}\right)$ to constant
$O(1)$ for $(r_{1},s)$-coverage and interference requirement (see Definition
6).

  * 2.

Let $a\geq 1.$ If the sensing radius $r_{1}>\frac{1}{2n}$ and the interference
distance $s>\frac{1}{n}$, the expected $T^{(a,1)}_{(AS)}$ transportation cost
for the autonomous sensor displacement is $\Theta(n)$ (see Table 1). The
expected $T^{(a,1)}_{(RS)}$-transportation cost for the robot assisted sensor
displacement is $\frac{O\left(n^{a}\right)}{k^{a}},$ provided that
$n^{1-\frac{1}{a}}\leq k\leq n$ (see Table 2).

Therefore, the robot with $n$-capacity reduces the transportation cost from
$\Theta(n)$ to constant $O(1)$ for $(r_{1},s)$-coverage and interference
requirement (see Definition 6).

Table 3 summarized the results obtained for the sensors on the plane.

When $n$ sensors with identical square sensing radius $r_{2}$ are randomly
displaced on the plane according to two identical and independent Poisson
processes each with arrival rate $\lambda=\sqrt{n},$ we have the following
results.

  * 1.

Let $a\in\left[1,\frac{4}{3}\right].$ For the square sensing radius
$r_{1}=\frac{1}{2\sqrt{n}}$ and the interference distance $s=\frac{1}{n}$, the
expected $T^{(a,2)}_{(AS)}$ transportation cost for the autonomous sensor
displacement is $\Theta\left(n^{1-\frac{a}{4}}\right)$ (see Table 1); and the
expected $T^{(a,2)}_{(RS)}$-transportation cost for the robot assisted sensor
displacement is $\frac{O\left(n^{\frac{3a}{4}}\right)}{k^{a}},$ provided that
$n^{1-\frac{1}{a}}\leq k\leq n^{\frac{1}{4}}$ (see Table 3).

Hence the robot with $\lceil n^{\frac{1}{4}}\rceil$-capacity reduces the
transportation cost from $\Theta\left(n^{1-\frac{a}{4}}\right)$ to
$O\left(n^{\frac{a}{2}}\right)$ for $(r_{2},s)$-coverage and interference
requirement (see Definition 8).

  * 2.

Let $a\in\left[1,2\right].$ If the square sensing radius $r_{2}>\frac{1}{2n}$
and the interference distance $s>\frac{1}{n}$, the expected $T^{(a,1)}_{(AS)}$
transportation cost for the autonomous sensor displacement is $\Theta(n)$ (see
Table 1). The expected $T^{(a,2)}_{(RS)}$-transportation cost for the robot
assisted sensor displacement is $\frac{O\left(n^{a}\right)}{k^{a}},$ provided
that $n^{1-\frac{1}{a}}\leq k\leq n^{\frac{1}{2}}$ (see Table 3).

Therefore, the robot with $\lceil\sqrt{n}\rceil$-capacity reduces the
transportation cost from $\Theta(n)$ to constant $n^{\frac{a}{2}}$ for
$(r_{2},s)$-coverage and interference requirement (see Definition 8).

Similar decrease in the transportation cost also holds for all parameters
$\lambda>0.$

The rest of the paper is organized as follows. Subsection 1.2 briefly
summarizes the related works. Section 2 analyzes the robot assisted sensor
movement on the line. Section 3 deals with the robot assisted sensor
reallocation on the plane. In Section 4 we apply the upper bounds from
previous sections for robot assisted movement to provide the coverage
interference requirement on the line and on the plane. Section 5 presents
further insights under various robots assisted scenarios while the numerical
evaluation of Algorithms 2 and 3 are presented in Section 6. The final section
offers conclusions.

###  1.2 Related Works

Autonomous mobile robots have been extensively studied in the literature
(e.g., see [6, 24, 30, 33, 34, 36]). The problem of coverage path planning
(CPP) for multiple cooperating mobile robots is addressed in [34]. In [30],
the authors advance their previous theoretical work by conducting experiments
on a generalized coverage optimization algorithm using a team of heterogeneous
mobile robots. The active simultaneous localization and mapping (SLAM)
framework for a mobile robot to obtain a collision-free trajectory with good
performance in SLAM uncertainty reduction and in an area coverage task is
presented in [6]. In [33], the author studies the problem of patrolling the
border with a set of $k$ robots. In [36], they presented a generalized
complete coverage path planning (CCPP) algorithm and its implementation for a
mobile robot.

The coverage problem in sensor networks has been the subject of extensive
interest (e.g., see [28, 39, 16, 5, 2, 4, 13, 3, 29, 38, 3, 10, 25, 15, 40]).
The theoretical foundations for $k$-barrier coverage were developed in [28],
while [16] presents and compares several state-of-the-art algorithms and
techniques to address the integrated coverage-connectivity issues in WSNs. The
analysis of unreliable sensors in a one-dimensional environment is considered
in [13]. In [10], the authors addressed three optimization problems to achieve
weak barrier coverage in WSNs. The family of problems whose goal is to design
a network with maximal connectedness subject to a fixed budget constraint is
investigated in [40].

It is worth mentioning that, our work in the current paper is related to the
series of papers of the autonomous sensors displacement (see [27, 11, 21, 23,
22, 17, 18, 19, 20, 14, 9]). It includes research on barrier and area coverage
[27, 23, 22, 19, 14], on interference [11], coverage simultaneously with
interference [17, 18], interference simultaneously with connectivity [20] and
coverage-connectivity for the range assignment [9]. In [14], the authors
revisited the asymptotics of a binomial and a Poisson sum that arose as
(average) displacement costs when sensors are randomly placed in anchor
positions.

Our investigation of robot assisted sensor displacement is inspired [8], where
the problem of robot assisted restoration of barrier coverage is introduced in
a deterministic setting. In [8] the authors provide an optimal linear-time
offline algorithm that gives a minimum-length trajectory for a single robot
that starts at the end of a barrier and achieves barrier coverage.

The novelty of the current paper lies in the introduction and investigation of
the robot assisted model and comparison with the recent results for the
autonomous sensor displacement (see [22, 18, 20, 14]).

##  2 Analysis of Robot Assisted Movement on the Line

Let $X_{i}$ be the position of the $i$-th sensor on the line $[0,\infty).$ Let
$n$ sensors $X_{1}\leq X_{2}\leq\dots\leq X_{n}$ be initially randomly placed
on the line $[0,\infty)$ according to general random process.

Initial random placement of the sensors this way does not guarantee such
communication properties as the coverage requirement, interference
requirement, the coverage simultaneously with connectivity, etc. Therefore, we
would like to move the sensors from their initial random location to a new
position so as to achieve the general scheduling requirement, thus providing
the desired communication.

It is assumed that the mobile robot located at the origin moves the sensors.
We define the robot capacity as follows.

######  Assumption 1 ($k$-capacity).

Assume that $k\in\mathrm{N}$ and $1\leq k\leq n.$ The carrying capacity $k$ of
the robot is the maximum number of sensors the robot can carry at a time to
deposit all or part of them at any time and to any suitable position it
chooses.

Obviously the robot can deposit a subset of the sensors it was carrying; it
may choose to pick up and carry new ones as long as it does not exceed the
value $k$. We now define the transportation for the robot assisted
displacement.

######  Definition 1 ($T^{(a,1)}_{(RS)}$-transportation cost).

Let $a\geq 1$ be a constant. Let $T^{(a,1)}_{(RS)}$ be the total distance to
the power $\mathbf{a}$ travelled by the robot of $k$-capacity from the origin
position to the final location so as to move the sensors $X_{i}$ to the
arbitrary final position $X_{i}+M_{i},$ provided that $i=1,2,\dots n.$

In the next two definition, we recall the $T^{(a,1)}_{(AS)}$-transportation
cost for the autonomous sensor displacement.

######  Definition 2 ($T^{(a,1)}_{(AS)}$-transportation cost).

Let $a\geq 1$ be a constant. Assume that, for $i=1,2,\dots,n$ the sensor
$X_{i}$ moves autonomously to the position $X_{i}+M_{i}.$ The
$T^{(a,1)}_{(AS)}$-transportation cost for the autonomous sensor displacement
is defined as the sum $T^{(a,1)}_{(AS)}=\sum_{i=1}^{n}|M_{i}|^{a}.$

In this section we would like to compare $T^{(a,1)}_{(RS)}$-transportation
cost for the robot assisted displacement with
$T^{(a,1)}_{(AS)}$-transportation cost for the autonomous sensor displacement
to provide the general scheduling requirement in the network such as coverage,
connectivity, or coverage simultaneously with interference, etc.

###  2.1 Greedy Procedure

This subsection presents the Greedy Procedure that explains the basic
relationship between $T^{(1,1)}_{(RS)}$-transportation cost and
$T^{(1,1)}_{(AS)}$-transportation cost in Algorithm 1. Algorithm 1 concerns
the mobile robot located at the position $Y_{0}$ provided that $Y_{0}\leq
Y_{1}\leq Y_{2}\leq\dots\leq Y_{l}.$ The mobile robot collects all sensors
$Y_{1}\leq Y_{2}\leq\dots\leq Y_{l}$ and moves to the final destination
$Y_{1}+M_{1}\leq Y_{2}+M_{2}\leq\dots\leq Y_{l}+M_{l}.$ Algoritm 1 is greedy
in the sense that robot located at the position $Y_{0}$ collects all sensors
$Y_{1}\leq Y_{2}\leq\dots\leq Y_{l}.$ Its analysis is crucial in deriving the
results in the next subsection which also analyzes the mentioned relationship.

Algorithm 1 $GP(Y_{0},Y_{1},Y_{2},\dots Y_{l})$, $l\leq$ $k$-capacity of
robot,

0: The initial random location $Y_{0}\leq Y_{1}\leq Y_{2}\leq\dots\leq Y_{l}$
of $l+1$ sensors on the $[0,\infty)$; the robot with carrying capacity $k$
located at the position $Y_{0}.$

0: The final location of the sensors at the points $Y_{0},$ $Y_{1}+M_{1}\leq$
$Y_{2}+M_{2}\leq\dots$ $\leq Y_{l}+M_{l};$ the robot located at the position
$Y_{l}.$

1: the robot starts from $Y_{0}$, moves forward and collect the sensors
$Y_{1},Y_{2},\dots,Y_{l};$

2: Set $q\leftarrow Y_{l};$

3: The robot displaces the sensors $Y_{1},Y_{2},\dots,Y_{l}$ at the
destination $Y_{1}+M_{1}\leq$ $Y_{2}+M_{2}\leq\dots$ $\leq Y_{l}+M_{l};$

4: The robot walks to the position $q;$

The following lemma proves the upper bound on the distance travelled by the
robot in Algorithm 1.

######  Lemma 1.

Fix $l\leq k\leq n.$ For $i=1,2,\dots,l$ assume that the sensor $Y_{i}$ moves
to the arbitrary position $Y_{i}+M_{i}$ and the robot with carrying capacity
$k$ is located at the position $Y_{0}.$ Then the total distance moved by the
robot according to Algorithm 1 is at most

$2|M_{1}|+2|M_{l}|+3(Y_{l}-Y_{0}).$

Before proving Lemma 1, notice that the movement of the robot with carrying
capacity $k\geq l$ in Algorithm 1 is upper bounded by the movements $|M_{1}|,$
$|M_{l}|$ and $(Y_{l}-Y_{0}).$ Also, observe that $|M_{1}|$ and $|M_{l}|$ are
the movements of the first and last sensors in the sequence $Y_{1}\leq
Y_{2}\leq\dots\leq Y_{l}.$ The component $(Y_{l}-Y_{0})$ is independent on the
movement and depends only on the initial random location of the first and last
sensors in the sequence $Y_{0}\leq Y_{2}\leq\dots\leq Y_{l}.$ We are now ready
to prove Lemma 1.

###### Proof.

Let $T_{(l)}$ be the total distance moved by the robot according to Algorithm
1 in our Greedy Procedure. We would like to upper bound $T_{(l)}.$ Observe
that the worst case occurs when $M_{1}<0$ and $M_{l}>0$, i.e.,
$Y_{1}+M_{1}\leq Y_{1}$ and $Y_{l}\leq Y_{l}+M_{l}.$

In this case the robot first moves left-to-right from $Y_{0}$ to $Y_{l}$ to
collect the sensors $Y_{1}\leq Y_{2}\leq\dots\leq Y_{l}.$ Then, the robot
moves left-to-right from $Y_{l}$ to $Y_{l}+M_{l}$ and displaces the sensor
$Y_{l}$ at the final position $Y_{l}+M_{l}.$ Then, the robot moves right-to-
left from $Y_{l}+M_{l}$ to $Y_{1}+M_{1}$ and displaces the sensors
$Y_{l-1}\geq Y_{l-2}\geq\dots\geq Y_{1}$ at the final positions
$Y_{l-1}+M_{l-1}\geq Y_{l-2}+M_{l-2}\geq\dots\geq Y_{1}+M_{1}.$ Finally, the
robot moves left-to-right from $Y_{1}+M_{1}$ to $Y_{l}.$ Hence,

$T_{(l)}=(Y_{l}-Y_{0})+2|M_{l}|+(Y_{l}-Y_{1})+2|M_{1}|+(Y_{l}-Y_{1})\leq
2|M_{1}|+2|M_{l}|+3(Y_{l}-Y_{0}).$

This completes the proof of Lemma 1. ∎

###  2.2 Main Results on the Line

In this subsection we analyze and compare the transportation cost for the
robot assisted movement with the autonomous sensor displacement when the
sensors are on the line.

Let $X_{1}\leq X_{2}\leq\dots\leq X_{n}$ be the initial random positions of
$n$ sensors on the $[0,\infty)$ according to general random process. Assume
that, for $i=1,2,\dots n$ the sensors $X_{i}$ moves to the arbitrary final
position $X_{i}+M_{i}.$

In this subsection we restrict our analysis to optimal movement. Recall that
by the simple monotonicity lemma, no sensor $X_{i}$ is ever placed before
sensor $X_{j},$ for all $i<j,$ i.e.,

$X_{1}+M_{1}\leq X_{2}+M_{2}\leq\dots\leq X_{n}+M_{n}.$

Let $k$ be the capacity of the robot located at the origin $0$. Consider the
following sequence of greedy algorithms $GM_{j}(k,n),$ where
$j\in\\{0,1,\dots,k-1\\}$ (see Algorithm 2).

Algorithm 2 $GM_{j}(k,n)$ Greedy Movement, $j\in\\{0,1,\dots,k-1\\},\,\,$
$k$-capacity of robot, $n$-number of sensors.

0: The initial random location $X_{1}\leq X_{2}\leq\dots\leq X_{n}$ of the $n$
sensors on the $[0,\infty)$ according to general random process. The mobile
robot with carrying $k$-capacity located at the origin $0.$

0: The final positions of the sensors at the location$X_{1}+M_{1}\leq
X_{2}+M_{2}\leq\dots\leq X_{n}+M_{n}.$

1: if $j=0$ then

2: do nothing;

3: else

4: Set $X_{0}\leftarrow 0;$

5: Execute $GP(X_{0},X_{1},X_{2},\dots,X_{j});$

6: end if

7: for $i=1$ to $\left\lfloor\frac{n-j}{k}\right\rfloor$ do

8: Execute $GP\left(X_{j+k(i-1)},X_{j+k(i-1)+1},\dots,X_{j+k(i-1)+k}\right);$

9: end for

10: if $j+k\left\lfloor\frac{n-j}{k}\right\rfloor<n$ then

11: Execute
$GP\left(X_{j+k\left\lfloor\frac{n-j}{k}\right\rfloor},X_{j+k\left\lfloor\frac{n-j}{k}\right\rfloor+1},\dots,X_{n}\right);$

12: else

13: do nothing;

14: end if

Observe that Algorithm $GM_{j}(k,n)$ runs in rounds. It is a sequence of
Greedy Procedures for $l=j\leq k$ when $j>0$ (Steps $(1-6)$; $l=k$ (Steps
$(7-9)$); and for $l=n-j-k\left\lfloor\frac{n-j}{k}\right\rfloor\leq
n-j-k\left(\frac{n-j}{k}-1\right)=k$ when
$j+k\left\lfloor\frac{n-j}{k}\right\rfloor<n$ (Steps $(10-11)$). Thus,
Algorithm 2 moves the sensors $X_{1}\leq X_{2}\leq\dots\leq X_{n}$ to the
final location $X_{1}+M_{1}\leq X_{2}+M_{2}\leq\dots\leq X_{n}+M_{n}.$ Hence,
it is correct.

We note that the presented relationship between the transportation cost of the
robot and the autonomous sensor displacement in Theorem 2 is valid for every
desired communication property.

######  Theorem 2.

Fix $1\leq k\leq n.$ Let $j\in\\{0,1,\dots,k-1\\}.$ Let $T^{(a,1)}_{(j,RS)}$
be $T^{(a,1)}_{(RS)}$-transportation cost in algorithm $GM_{j}(k,n).$ Then,

$\min_{0\leq j\leq k-1}T^{(a,1)}_{(j,RS)}$

is at most

$6^{a}X^{a}_{n}+\left(4\left\lfloor\frac{n}{k}\right\rfloor+16\right)^{a-1}\left(2|M_{1}|^{a}+2|M_{n}|^{a}+\frac{4T^{(a,1)}_{(AS)}}{k}\right).$
(1)

###### Proof.

Let us recall the inequality between general means. Assume that $a\geq 1.$ and
$b_{1},b_{2},\dots b_{l}$ are positive. Then

$\frac{b_{1}+b_{2}+\dots+b_{l}}{l}\leq\left(\frac{b_{1}^{a}+b_{2}^{a}+\dots+b_{l}^{a}}{l}\right)^{\frac{1}{a}}$
(2)

(see [31, Theorem 1, Section 2.14.2]).

By Definition 3,

$T^{(a,1)}_{(AS)}=\sum_{i=1}^{n}|M_{i}|^{a}$ (3)

is the transportation cost for the autonomous sensor displacement in Algorithm
2. Let $T^{(a,1)}_{(j,RS)}$ be $T^{(a,1)}_{(RS)}$-transportation cost in
Algorithm $GM_{j}(k,n)$ for $j=0,1,\dots,k-1.$ From Lemma 1, we have the
following upper bound

$T^{(a,1)}_{(j,RS)}\leq\left(A_{j}+B_{j}+2\sum_{i=1}^{\left\lfloor\frac{n-j}{k}\right\rfloor}\left(\left|M_{j+k(i-1)+1}\right|+\left|M_{j+ki}\right|\right)+C_{j}+D_{j}+3X_{n}\right)^{a},$

where

$\displaystyle A_{j}=\begin{cases}0\,\,\,&\text{if}\,\,\ j=0,\\\
2|M_{1}|\,\,\,&\text{if}\,\,\
j>0,\end{cases}\,\,\,\,\,\,\,\,\,\,\,\,B_{j}=\begin{cases}0\,\,\,&\text{if}\,\,\
j=0,1,\\\ 2|M_{j}|\,\,\,&\text{if}\,\,\ j>1,\end{cases}$

$C_{j}=\begin{cases}0\,\,\,&\text{if}\,\,\
j+k\left\lfloor\frac{n-j}{k}\right\rfloor=n,\\\ 2|M_{n}|\,\,\,&\text{if}\,\,\
j+k\left\lfloor\frac{n-j}{k}\right\rfloor\leq n-1,\end{cases}$
$D_{j}=\begin{cases}0\,\,\,&\text{if}\,\,\
j+k\left\lfloor\frac{n-j}{k}\right\rfloor=n-1,n,\\\
2|M_{j+k\left\lfloor\frac{n-j}{k}\right\rfloor+1|}|\,\,\,&\text{if}\,\,\
j+k\left\lfloor\frac{n-j}{k}\right\rfloor<n-1.\end{cases}$

Applying Inequality (2) we get

$T^{(a,1)}_{(j,RS)}\leq
6^{a}X_{n}^{a}+2^{a-1}\left(A_{j}+B_{j}+2\sum_{i=1}^{\left\lfloor\frac{n-j}{k}\right\rfloor}\left(\left|M_{j+k(i-1)+1}\right|+\left|M_{j+ki}\right|\right)+C_{j}+D_{j}\right)^{a}.$

Once again, applying Inequality (2) we have

$\displaystyle T^{(a,1)}_{(j,RS)}$ $\displaystyle\leq
6^{a}X^{a}_{n}+\left(4\left\lfloor\frac{n-j}{k}\right\rfloor+16\right)^{a-1}\Big{(}2\sum_{i=1}^{\left\lfloor\frac{n-j}{k}\right\rfloor}\left(\left|M_{j+k(i-1)+1}\right|^{a}+\left|M_{j+ki}\right|^{a}\right)\Big{)}$
$\displaystyle+\left(4\left\lfloor\frac{n-j}{k}\right\rfloor+16\right)^{a-1}\Big{(}2(A_{j}/2)^{a}+2(B_{j}/2)^{a}+2(C_{j}/2)^{a}+2(D_{j}/2)^{a}\Big{)}.$
(4)

Let us now make the following important observation

$\sum_{j=0}^{k-1}T^{(a,1)}_{(j,RS)}\leq
k6^{a}X^{a}_{n}+\left(4\left\lfloor\frac{n}{k}\right\rfloor+16\right)^{a-1}\\\
\left(2k|M_{1}|^{a}+4\sum_{i=1}^{n}|M_{i}|^{a}+2k|M_{n}|^{a}\right).$ (5)

Figure 1 illustrates Inequality (4) for $n=8$ and $k=3.$ Namely $T_{(j,RS)}$
is the transportation cost Algorithm $GM_{j}(k,8)$ for $j=0,1,\dots,3.$ Let us
recall that, for $i=1,2,\dots,8$ the sensor $X_{i}$ moves to the position
$X_{i}+M_{i}.$ In Figure 1, the black dots indicate the movements
$2|M_{i}|^{a}$ which consider in the upper bound estimation (4) of
$T^{(a,1)}_{(j,RS)}$ for Algorithm $GM_{j}(k,8),$ provided $j=0,1,\dots,3.$
(Obviously, the white dots indicate the movements $2|M_{i}|^{a}$ which don’t
appear in the upper bound estimation (4) of $T^{(a,1)}_{(j,RS)}$ for Algorithm
$GM_{j}(k,8),$ provided $j=0,1,\dots,3$). Now, two times sum of the black dots
in Figure 1 is equal to

$6|M_{1}|^{a}+4\sum_{i=1}^{8}|M_{i}|^{a}+6|M_{8}|^{a}.$

This confirms the movements $|M_{1}|^{a},$ $|M_{2}|^{a},\dots$ $|M_{n}|^{a}$
in the upper bound Inequality (5) for $n=8$ and $k=3$ very well.

$|M_{1}|^{a}$$|M_{2}|^{a}$$|M_{3}|^{a}$$|M_{4}|^{a}$$|M_{5}|^{a}$$|M_{6}|^{a}$$|M_{7}|^{a}$$|M_{8}|^{a}$$GM_{0}(3,8)$

$|M_{1}|^{a}$$|M_{2}|^{a}$$|M_{3}|^{a}$$|M_{4}|^{a}$$|M_{5}|^{a}$$|M_{6}|^{a}$$|M_{7}|^{a}$$|M_{8}|^{a}$$GM_{1}(3,8)$

$|M_{1}|^{a}$$|M_{2}|^{a}$$|M_{3}|^{a}$$|M_{4}|^{a}$$|M_{5}|^{a}$$|M_{6}|^{a}$$|M_{7}|^{a}$$|M_{8}|^{a}$$GM_{2}(3,8)$

Figure 1: Movement of $n=8$ sensors for the robot with carrying $3-$capacity
according to Algorithm $GM_{j}(3,8),$ when $j\in\\{0,1,2\\}.$

Note that the minimal cost satisfies

$\min_{0\leq j\leq
k-1}T^{(a,1)}_{(j,RS)}\leq\frac{T^{(a,1)}_{(0,RS)}+T^{(a,1)}_{(1,RS)}+\dots+T^{(a,1)}_{(k-1,RS)}}{k}.$

Hence, applying Inequality (5) and Formula (3) we have

$6^{a}X^{a}_{n}+\left(4\left\lfloor\frac{n}{k}\right\rfloor+16\right)^{a-1}\left(2|M_{1}|^{a}+2|M_{n}|^{a}+\frac{4T^{(a,1)}_{(AS)}}{k}\right).$

This is enough to complete the proof of Theorem 2. ∎

We can also prove the lower bound.

######  Corollary 1.

Fix $1\leq k\leq n.$ Assume that $n$ sensors $X_{1}\leq X_{2}\leq\dots\leq
X_{n}$ are initially randomly placed on the $[0,\infty)$ according to general
random process and the mobile robot with carrying $k$-capacity is located at
the origin $0.$ Then, $T^{(a,1)}_{(RS)}$-transportation cost according to
every robot assisted algorithm is at least $X^{a}_{n}.$

###### Proof.

The robot in the origin point $0$ has to collect all the sensors $X_{1}\leq
X_{2}\leq\dots\leq X_{n}.$ Hence, the robot has to move from the origin point
$0$ to the random point $X_{n}.$ Therefore $T^{(a,1)}_{(RS)}$ is at least
$\left(X_{n}-0\right)^{a}=X^{a}_{n}.$ ∎

##  3 Analysis of Robot Assisted Movement on the Plane

In this section we look at the transportation cost for the robot assisted
movement when the sensors are on the plane.

More precisely, we consider $n$ sensors placed in the quadrant
$[0,\infty)\times[0,\infty)$ according to two independent general random
processes $X_{i}$ and $Y_{i}.$ The random position of the sensor on the plane
is determined by the pair $(X_{i_{1}},Y_{i_{2}}),$ where
$i_{1},i_{2}=1,2,\dots,\sqrt{n}$ and $n=m^{2}$ for some $m\in\mathbf{N}.$

We are now ready to define the transportation cost for robot assisted
displacement and the transportation cost for the autonomous sensor
displacement on the plane.

######  Definition 3 ($T^{(a,2)}_{(RS)}$-transportation cost).

Let $a\geq 1$ be a constant. Let $T^{(a,2)}_{(RS)}$ be the total distance to
the power $\mathbf{a}$ travelled by the robot of $k$-capacity from the origin
position $(0,0)$ to the final location so as to move the sensor
$(X_{i_{1}},Y_{i_{2}}),$ to the arbitrary final position
$(X_{i_{1}}+M_{i_{1}},Y_{i_{2}}+N_{i_{2}}),$ provided that
$i_{1},i_{2}=1,2,\dots,\sqrt{n}.$

######  Definition 4 ($T^{(a,2)}_{(AS)}$-transportation cost).

Let $a\geq 1$ be a constant. Assume that, for $i=1,2,\dots,n$ the sensor
$(X_{i_{1}},Y_{i_{2}})$ moves autonomously to the arbitrary final position
$(X_{i_{1}}+M_{i_{1}},Y_{i_{2}}+N_{i_{2}})$ for
$i_{1},i_{2}=1,2,\dots,\sqrt{n}.$ The $T^{(a,2)}_{(AS)}$-transportation cost
for the autonomous sensor displacement is defined as the sum
$T^{(a,2)}_{(AS)}=\sum_{i_{1},i_{2}=1}^{\sqrt{n}}\left(|M_{i_{1}}|^{a}+|N_{i_{2}}|^{a}\right).$

###  3.1 Main Results on the Plane

In this subsection we analyze and compare the transportation cost for the
robot assisted movement with the autonomous sensor displacement when the
sensors are on the plane. In order to move the sensors on the plane we present
the sequence of greedy algorithms $GM_{j_{1},j_{2}}(k,n),$ where
$j_{1},j_{2}\in\\{0,1,\dots,k-1\\},\,\,$ (see Algorithm 3). Algorithm 3 works
in two phases. During the first phase (Steps $(1-5)$), we execute Algorithm 1
according to the first coordinate. Thus, in the second phase (Steps $(7-11)$),
Algorithm 1 is executed according to the second coordinate. Thus, the robot
movements on the plane is reduced to the robot movements on the line. Hence,
Algorithm 3 is correct. We apply Theorem 2 on the line from Subsection 2.2 and
prove Theorem 3 on the plane.

Figure 2 illustrates the trajectory of the robot in Steps $(1-5)$ of Algorithm
3 for $n=9$ and $k=3.$ The robot’s trajectory is the line segment from $(0,0)$
to $(0,Y_{1});$ $(0,Y_{1})$ to $(\max(X_{3},X_{3}+M_{3}),Y_{1});$
$(\max(X_{3},X_{3}+M_{3}),Y_{1})$ to $(0,Y_{1});$ $(0,Y_{1}),$ to $(0,Y_{2});$
$(0,Y_{2})$ to
$(\max(X_{3},X_{3}+M_{3}),Y_{2});$ $(\max(X_{3},X_{3}+M_{3}),Y_{2})$ to
$(0,Y_{2});$ $(0,Y_{2}),$ to $(0,Y_{3});$ $(0,Y_{3})$ to
$(\max(X_{3},X_{3}+M_{3}),Y_{3})$ and $(\max(X_{3},X_{3}+M_{3}),Y_{3})$ to
$(0,Y_{3}).$

Algorithm 3 $GM_{j_{1},j_{2}}(k,n)$ Greedy Movement,
$j_{1},j_{2}\in\\{0,1,\dots,k-1\\},\,\,$ $k$-capacity of robot, $1\leq
k\leq\sqrt{n},$ $n$-number of sensors, $n=m^{2}$ for some $m\in\mathbf{N}$.

0: The initial random location $(X_{i_{1}},Y_{i_{2}})$ of the $n$ sensors in
the $[0,\infty)\times[0,\infty),$ where $i_{1},i_{2}=1,2,\dots\sqrt{n}$
according to two general random processes. The mobile robot with carrying
$k$-capacity is located at the origin $(0,0).$

0: The final positions of the sensors at the
location$(X_{i_{1}}+M_{i_{1}},Y_{i_{2}}+N_{i_{2}}),$ where
$i_{1},i_{2}=1,2,\dots,\sqrt{n}.$

1: for $i_{2}=1$ to $\sqrt{n}$ do

2: The robot walks to the position $(0,Y_{i_{2}});$

3: Execute algorithm $GM_{j_{2}}(k,\sqrt{n})$ according to the firstcoordinate
of the sensors $(X_{1},Y_{i_{2}}),$
$(X_{2},Y_{i_{2}}),\dots,$$(X_{\sqrt{n}},Y_{i_{2}}).$ It means to move to the
positions $(X_{1}+M_{1},Y_{i_{2}}),$ $(X_{2}+M_{2},Y_{i_{2}}),\dots,$
$(X_{\sqrt{n}}+M_{\sqrt{n}},Y_{i_{2}});$

4: The robot walks to the position $(0,Y_{i_{2}});$

5: end for

6: The robot walks to the origin $(0,0);$

7: for $i_{1}=1$ to $\sqrt{n}$ do

8: The robot walks to the position $(X_{i_{1}}+M_{i_{1}},0);$

9: Execute algorithm $GM_{j_{1}}(k,\sqrt{n})$ according to the second
coordinate of the sensors $(X_{i_{1}}+M_{i_{1}},Y_{1}),$
$(X_{i_{1}}+M_{i_{1}},Y_{2}),\dots,$ $(X_{i_{1}}+M_{i_{1}},Y_{\sqrt{n}}).$ It
means to move to the positions$(X_{i_{1}}+M_{i_{1}},Y_{1}+N_{1}),$
$(X_{i_{1}}+M_{i_{1}},Y_{2}+N_{2}),\dots,$$(X_{i_{1}}+M_{i_{1}},Y_{\sqrt{n}}+N_{\sqrt{n}});$

10: The robot walks to the position $(X_{i_{1}}+M_{i_{1}},0);$

11: end for

$(0,0)$$X_{1}$$X_{2}$$X_{3}$$Y_{1}$$Y_{2}$$Y_{3}$ Figure 2: The trajectory of
robot in Steps $(1-5)$ of Algorithm 3 for $n=9.$

######  Theorem 3.

Fix $1\leq k\leq\sqrt{n}.$ Let $j_{1},j_{2}\in\\{0,1,\dots,k-1\\}.$ Let
$T^{(a,2)}_{(j_{1},j_{2},RS)}$ be $T^{(a,2)}_{(RS)}$-transportation cost in
algorithm $GM_{j_{1},j_{2}}(k,n).$ Then,

$\min_{0\leq j_{1},j_{2}\leq k-1}T^{(a,2)}_{(j_{1},j_{2},RS)}$

is at most

$\displaystyle
4^{a}n^{a/2-1/2}\left(4\left\lfloor\frac{\sqrt{n}}{k}\right\rfloor+16\right)^{a-1}\frac{T^{(a,2)}_{(AS)}}{k}+4^{a-1}n^{a/2}\left(4\left\lfloor\frac{\sqrt{n}}{k}\right\rfloor+16\right)^{a-1}\left(2|M_{1}|^{a}+2|M_{\sqrt{n}}|^{a}\right)$
$\displaystyle+4^{a-1}n^{a/2}\left(4\left\lfloor\frac{\sqrt{n}}{k}\right\rfloor+16\right)^{a-1}\left(2|N_{1}|^{a}+2|N_{\sqrt{n}}|^{a}\right)+\left(2^{3a-1}+6^{a}4^{a-1}n^{a/2}\right)Y^{a}_{\sqrt{n}}$
$\displaystyle+\left(4^{a-1}+6^{a}4^{a-1}n^{a/2}\right)X^{a}_{\sqrt{n}}.$ (6)

###### Proof.

Let $j_{1},j_{2}\in\\{0,1,\dots,k-1\\}$ and let $T^{(a,2)}_{(j_{1},j_{2},RS)}$
be $T^{(a,2)}_{(RS)}$-transportation cost in algorithm
$GM_{j_{1},j_{2}}(k,n).$

Let $D_{1}(j_{2},i_{2})$ be the distance travelled by the robot in Step $(3)$
of Algorithm 3, provided that $i_{2}\in\\{1,2,\dots,\sqrt{n}\\}.$

Let $D_{2}(j_{1},i_{1})$ be the distance travelled by the robot in Step $(9)$
of Algorithm 3, provided that $i_{1}\in\\{1,2,\dots,\sqrt{n}\\}.$

Hence, the distance travelled by the robot in Steps $(1-5)$ of Algorithm 3 is
equal to

$\sqrt{n}D_{1}(j_{2},1)+Y_{\sqrt{n}}$ (7)

and the distance travelled by the robot is Steps $(7-11)$ of Algorithm 3 is
equal to

$\sqrt{n}D_{2}(j_{1},1)+X_{\sqrt{n}}.$ (8)

It is easy to see that the distance travelled by the robot in Step $(6)$ of
Algorithm 3 is equal to

$Y_{\sqrt{n}}.$ (9)

Combining Expressions (7-9) we have

$T^{(a,2)}_{(j_{1},j_{2},RS)}=\left(\sqrt{n}D_{1}(j_{2},1)+\sqrt{n}D_{2}(j_{1},1)+2Y_{\sqrt{n}}+X_{\sqrt{n}}\right)^{a}.$

Applying Inequality (2) we get

$T^{(a,2)}_{(j_{1},j_{2},RS)}=4^{a-1}\left(n^{a/2}D^{a}_{1}(j_{2},1)+n^{a/2}D^{a}_{2}(j_{1},1)+2^{a}Y^{a}_{\sqrt{n}}+X^{a}_{\sqrt{n}}\right).$
(10)

Applying Theorem 2 for $n:=\sqrt{n}$ and the sensors
$X_{1},X_{2},\dots,X_{\sqrt{n}}$ we have

$\min_{0\leq j_{2}\leq k-1}D^{a}_{1}(j_{2},1)\leq
6^{a}X^{a}_{\sqrt{n}}+\left(4\left\lfloor\frac{\sqrt{n}}{k}\right\rfloor+16\right)^{a-1}\left(2|M_{1}|^{a}+2|M_{\sqrt{n}}|^{a}+\frac{4\sum_{i=1}^{\sqrt{n}}|M_{i}|^{a}}{k}\right).$
(11)

Using Theorem 2 for $n:=\sqrt{n}$ and the sensors
$Y_{1},Y_{2},\dots,Y_{\sqrt{n}}$ we get

$\min_{0\leq j_{1}\leq k-1}D^{a}_{1}(1,j_{1})\leq
6^{a}Y^{a}_{\sqrt{n}}+\left(4\left\lfloor\frac{\sqrt{n}}{k}\right\rfloor+16\right)^{a-1}\left(2|N_{1}|^{a}+2|N_{\sqrt{n}}|^{a}+\frac{4\sum_{i=1}^{\sqrt{n}}|N_{i}|^{a}}{k}\right).$
(12)

Finally, combining Estimations $(\ref{eq:astra}-\ref{eq:100ad})$ we have the
desired upper bound (6). This completes the proof of Theorem 3. ∎

We can also prove the lower bound.

######  Corollary 2.

Assume that $n$ sensors are placed on the plane $[0,\infty)\times[0,\infty)$
according to two identical and independent Poisson processes $X_{i}$ and
$Y_{i},$ for $i=1,2,\dots,\sqrt{n}$ each with arrival rate $\lambda>0$ and the
mobile robot with carrying $k$-capacity is located at the origin $(0,0).$ The
random position of the sensor on the plane is determined by the pair
$(X_{i_{1}},Y_{i_{2}}),$ where $i_{1},i_{2}=1,2,\dots,\sqrt{n}$ and $n=m^{2}$
for some $m\in\mathbf{N}.$ Then, $T^{(a,1)}_{(RS)}$-transportation cost
according to every robot assisted algorithm is at least $X^{a}_{n}.$

###### Proof.

The robot in the origin point $(0,0)$ has to collect all the sensors
$(X_{i_{1}},Y_{i_{2}}),$ where $i_{1},i_{2}=1,2,\dots,\sqrt{n}$ and $n=m^{2}$
for some $m\in\mathbf{N}.$ Hence, the robot has to move from the origin point
$(0,0)$ to the random point $(X_{\sqrt{n}},Y_{\sqrt{n}}).$ Therefore
$T^{(a,1)}_{(RS)}$ is at least
$\left(\sqrt{n}\left(X_{\sqrt{n}}-X_{1}\right)\right)^{a}=n^{a/2}\left(X_{\sqrt{n}}-X_{1}\right)^{a}.$
∎

##  4 Application to Coverage and Interference in Sensor Networks

In this section we apply the upper bounds obtained from Theorem 2 and Theorem
3 to the coverage simultaneously with the interference problem. Namely, we
compare the known results for the energy consumption in autonomous sensor
displacement to fulfil the coverage and interference requirement obtained in
[17], [18], [20] with the current estimations in Sections 2 and 3. As the
result we obtain novel upper bounds for the energy consumption in robot
assisted displacement to provide the coverage and interference requirement.

###  4.1 Coverage and Interference on the Line

In this subsection we look at the $(r_{1},s)$-coverage and interference
problem on the line. Let us recall the definition of the sensing radius.

######  Definition 5 (Sensing Radius).

We assume that a sensor placed at location $x$ on the line can sense any point
at distance $r_{1}$ at most reither to the left or right of $x$ and call
$r_{1}$ the sensing radius of the sensor.

In particular, we consider $n$ random sensors $X_{1}\leq X_{2}\leq\dots\leq
X_{n}$ with identical sensing radius $r_{1}$ initially randomly displaced on
the $[0,\infty)$ according to Poisson process with arrival rate $\lambda>0.$
The formal definition of $(r_{1},s)$-coverage and interference problem on the
line is as follows.

######  Definition 6 ($(r_{1},s)$-coverage and interference).

We move the sensors from the initial random locations $X_{1}\leq
X_{2}\leq\dots\leq X_{n}$ to the final positions $X_{1}+M_{1}\leq$
$X_{2}+M_{2}\leq\dots\leq X_{n}+M_{n}$ so as to:

  * 1.

Ensure coverage in the sense that every point in the interval
$[0,X_{n}+M_{n}]$ is in the sensing radius of at least one sensor.

  * 2.

Avoid interference, i.e., each pair of sensors is at interference distance
greater or equal to $s.$

In the recent paper [17], the maximum of the expected sensor’s displacements
to the power $a\geq 1$ metric given by

$\mathbf{E_{\max}}\left[T^{(a,1)}_{(AS)}\right]=\max_{1\leq i\leq
n}\mathbf{E}\left[|M_{i}|^{a}\right]$ (13)

was investigated for $(r_{1},s)$-coverage and interference problem when the
sensors autonomously move on the line.

Further, the author in [20] considered the expected $a-$total movement as
follows

$\mathbf{E}\left[T^{(a,1)}_{(AS)}\right]=\sum_{i=1}^{n}\mathbf{E}\left[|M_{i}|^{a}\right],\,\,\,\text{provided
that}\,\,\,a\geq 1.$ (14)

for interference-connectivity problem for the autonomous sensor displacement
on the line and in the higher dimension.

It is worth pointing out that the main results of [20] for interference-
connectivity problem are easily applicable to $(r_{1},s)$-coverage and
interference problem when the sensors move autonomously on the line.

Table 1 for $d=1$ summarizes the known results on the line.

Table 1: The minimal maximum of expected sensor’s displacements and the expected minimal $T^{(a,d)}_{(AS)}$-transportation cost for $(r_{d},s)$-coverage and interference problem of $n$ sensors in the $[0,\infty)^{d}$ for $d\in\\{1,2\\}$ provided that $\epsilon\geq\delta>0$ are arbitrarily small constants independent on $\lambda$ and $n$ (see [17], [18], [20]).  | Sensing radius $r_{1},$
---
Square sensing radius $r_{2}$
Interference distance $s$ | $\mathbf{E_{\max}}\left[T^{(a,d)}_{(AS)}\right]$ | $\mathbf{E}\left[T^{(a,d)}_{(AS)}\right]$
$r_{d}=\frac{1+\epsilon}{2\lambda}$ | $s=\frac{1-\delta}{\lambda}$ | $\Theta(1)/\lambda^{a}$ | $O(n)/\lambda^{a}$
$r_{d}=\frac{1}{2\lambda},$ | $s=\frac{1}{\lambda}$ | $\Theta\left(n^{\frac{a}{2d}}\right)/\lambda^{a}$ | $\Theta\left(n^{1+\frac{a}{2d}}\right)/\lambda^{a}$
$r=\frac{1+\epsilon}{2\lambda}$ | $s=\frac{1+\delta}{\lambda}$ | $\Theta\left(n^{\frac{a}{d}}\right)/\lambda^{a}$ | $\Theta\left(n^{1+\frac{a}{d}}\right)/\lambda^{a}$

In order to compare the results about the autonomous sensor displacement in
Table 1 for $d=1$ with the robot assisted displacement in Section 2, we have
to reformulate Equation (1) in Theorem 2 and Corollary 1 (see Subsection 2.2)
for the expected transportation cost. This is the subject of Theorem 4.

######  Theorem 4.

Assume that the sensors $X_{1}\leq X_{2}\leq\dots\leq X_{n}$ are initially
randomly placed on the $[0,\infty)$ according to Poisson process with arrival
rate $\lambda>0.$ Fix $1\leq k\leq n.$ Let $j\in\\{0,1,\dots,k-1\\}.$ Let
$T^{(a,1)}_{(j,RS)}$ be $T^{(a,1)}_{(RS)}$-transportation cost in algorithm
$GM_{j}(k,n).$ Then

$\frac{n^{a}}{\lambda^{a}}\left(1+O\left(\frac{1}{n}\right)\right)\leq\mathbf{E}\left[\min_{0\leq
j\leq k-1}T^{(a,1)}_{(j,RS)}\right],$ (15) $\mathbf{E}\left[\min_{0\leq j\leq
k-1}T^{(a,1)}_{(j,RS)}\right]\leq\frac{6^{a}n^{a}}{\lambda^{a}}\left(1+O\left(\frac{1}{n}\right)\right)+\left(4\left\lfloor\frac{n}{k}\right\rfloor+16\right)^{a-1}\Bigg{(}4\mathbf{E_{\max}}\left[T^{(a,1)}_{(AS)}\right]+\frac{4\mathbf{E}\left[T^{(a,1)}_{(AS)}\right]}{k}\Bigg{)}.$
(16)

###### Proof.

There are two cases to consider

Case 1: Inequality (15)

We know that the random variable $X_{i}$, i.e., the random position of $i$-th
sensor is the sum of $i$ independent and identically distributed exponential
random variables with parameter $\lambda$ and obeys Gamma distribution with
parameters $i\in\mathbb{N}\setminus\\{0\\},\lambda>0$ (see [26, 37]). Notice
that,

$\mathbf{E}[|X_{k}|^{a}]=\frac{1}{\lambda^{k}}\frac{\Gamma(k+a)}{\Gamma(k)},\,\,\,\text{when}\,\,\,k\in\\{1,2,\dots,n\\}\,\,\,\text{and}\,\,\,a>0$
(17)

(see [12, Chapter 15, 22]).

The following asymptotic expansion for Gamma function is well known (see [35,
Identity 5.11.13] for $z=n$ and $b=0$)

$\frac{\Gamma(n+a)}{\Gamma(n)}=n^{a}\left(1+O\left(\frac{1}{n}\right)\right).$
(18)

Passing to the expectation in Corollary 1 and applying Formulas (17), (18) we
have the lower bound.

Case 2: Inequality (16)

Passing to the expectation in Equation (1) (see Theorem 2), applying Formulas
(13), (14), (17), (18) as well as the estimation

$\mathbf{E}\left[|M_{1}|^{a}\right]+\mathbf{E}\left[|M_{n}|^{a}\right]\leq
2\mathbf{E_{\max}}\left[T^{(a,1)}_{(AS)}\right]$

we get the upper bound.

It completes the proof of Theorem 4. ∎

We now compare the new result of Theorem 4 for the robot assisted movement
($\min_{0\leq j\leq k-1}T_{(j,RS)}$ transportation cost) with the known
results for the autonomous sensors displacement ($T^{(a,1)}_{(AS)}$
transportation cost) in Table 1 for $d=1.$ Specifically, we find

$\min\left(\mathbf{E}\left[\min_{0\leq j\leq
k-1}T^{(a,1)}_{(j,RS)}\right],\mathbf{E}\left[T^{(a,1)}_{(AS)}\right]\right)$

as the function of the robot capacity $k,$ the sensing radius $r_{1}$ and the
interference distance $s.$

Table 2 displays the described comparison of the energy consumption in the
robot assisted movement and in the autonomous sensor displacement.

Table 2: Comparison of the expected transportation cost for the robot assisted movement with $k$-capacity and the autonomous sensor displacement to ensure $(r_{1},s)$-coverage and interference problem for $n$ sensors in the $[0,\infty),$ provided that $\epsilon\geq\delta>0$ are arbitrary small constants independent on $\lambda$ and $n.$ | Sensing
---
radius $r_{1},$
| Interference
---
distance $s$
Movement |  | Expected transportation cost
---
(Energy consumption)
$r_{1}=\frac{1+\epsilon}{2\lambda}$ | $s=\frac{1-\delta}{\lambda}$ |  $T^{(a,1)}_{(AS)}$ if $a\geq 1$ | $O\left(n\right)/\lambda^{a}$
$r_{2}=\frac{1}{2\lambda}$ | $s=\frac{1}{\lambda}$ |  $T^{(a,1)}_{(AS)}$ if $a>2$ | $O\left(n^{1+\frac{a}{2}}\right)/\lambda^{a}$
$r_{1}=\frac{1}{2\lambda}$ | $s=\frac{1}{\lambda}$ |  $T^{(a,1)}_{(RS)}$, if $a\in[1,2]$ |  |  $O\left(n^{\frac{3a}{2}}\right)/(k\lambda)^{a}\,\,\,$ if $\,\,\,k\in\left[n^{1-\frac{1}{a}},\sqrt{n}\right]$
---
$\,\,\,\,\,\,\Theta\left(n^{a}\right)/\lambda^{a}\,\,\,$ if
$\,\,\,k\in\left[\sqrt{n},n\right]$
$r_{1}=\frac{1+\epsilon}{2\lambda}$ | $s=\frac{1+\delta}{\lambda}$ |  $T^{(a,1)}_{(RS)}$ if $a\geq 1$ |  $O\left(n^{2a}\right)/(k\lambda)^{a}\,\,\,$ if $k\in\left[n^{1-1/a},n\right]$

###  4.2 Coverage and Interference on the Plane

In this subsection we analyze the $(r_{2},s)$-coverage and interference
problem on the plane.

We consider $n$ sensors that are randomly placed on the
$[0,\infty)\times[0,\infty)$ according to two identical and independent
Poisson processes $X_{i}$ and $Y_{i},$ for $i=1,2,\dots,\sqrt{n}$ each with
arrival rate $\lambda>0,$ and $n=m^{2}$ for some $m\in\mathbf{N}.$ The random
position of the sensor with identical square sensing radius $r_{2}$ on the
plane is determined by the pair $(X_{i_{1}},Y_{i_{2}}),$ where
$i_{1},i_{2}=1,2,\dots,\sqrt{n}.$

Let us recall the concept of the square sensing radius.

######  Definition 7 (cf. [21], Square Sensing Radius).

We assume that a sensor located in position $(x,y)$ can cover any point in the
area delimited by the square with $4$ vertices $(x\pm r_{2},y\pm r_{2})$ and
call $r_{2}$ the square sensing radius of the sensor.

However, if the generally accepted coverage area of a sensor is a circular
disk of radius $r_{c}$ the upper bound results proved in the sequel for the
square sensing radius $r_{2}$ hold for circular disk of radius
$r_{c}=\sqrt{2}r_{2}.$ The formal definition of $(r_{2},s)$-coverage and
interference problem on the plane is as follows.

######  Definition 8 ($(r_{2},s)$-coverage and interference).

We move the sensors from initial positions $(X_{i_{1}},Y_{i_{2}})$ to the
final locations $(X_{i_{1}}+M_{i_{1}},Y_{i_{2}}+N_{i_{2}}),$ for
$i_{1},i_{2}=1,2,\dots,\sqrt{n}$ such that:

  * 1.

Move the sensors only along the axes provided that

$\displaystyle X_{1}+M_{1}$ $\displaystyle\leq X_{2}+M_{2}\leq\dots\leq
X_{\sqrt{n}}+M_{\sqrt{n}},$ $\displaystyle Y_{1}+N_{1}$ $\displaystyle\leq
Y_{2}+N_{2}\leq\dots\leq Y_{\sqrt{n}}+N_{\sqrt{n}},$

and the final position of each sensor is in the same row and column as its
initial position.

  * 2.

Ensure coverage in the sense that every point in the area delimited by the
rectangle with $4$ vertices $(0,0),$ $(X_{\sqrt{n}}+M_{\sqrt{n}},0),$
$(X_{\sqrt{n}}+M_{\sqrt{n}},Y_{\sqrt{n}}+N_{\sqrt{n}})$, and
$(0,Y_{\sqrt{n}}+N_{\sqrt{n}})$ is in the square sensing radius of at least
one sensor.

  * 3.

Avoid interference, i.e., each pair of sensors is at interference distance
greater or equal to $s$.

Observe that the main results for the maximum of the expected sensor’s
displacement metric and $(r_{1},s)$-coverage and interference problem on the
line (see [17]) are easily applicable to $(r_{2},s)$-coverage and interference
problem on the plane. For $d=2$, Table 1 displays the results on the plane for

$\max\left(\mathbf{E}\left[T^{(a,2)}_{(AS)}\right]\right)=\max_{1\leq
i\leq\sqrt{n}}\mathbf{E}\left[|M_{i}|^{a}\right]+\max_{1\leq
i\leq\sqrt{n}}\mathbf{E}\left[|N_{i}|^{a}\right].$ (19)

Moreover, in [20] the expected transportation cost

$\mathbf{E}\left[T^{(a,2)}_{(AS)}\right]=\sqrt{n}\sum_{i=1}^{\sqrt{n}}\left(\mathbf{E}\left[|M_{i}|^{a}\right]+\mathbf{E}\left[|N_{i}|^{a}\right]\right)$
(20)

was investigated for interference-connectivity problem for the autonomous
sensor displacement on the plane. The main results of [20] for interference-
connectivity problem are applicable to $(r_{2},s)$-coverage and interference
problem when the sensors move autonomously on the plane. (see Table 1 for
$d=2$).

In order to compare the results about the autonomous sensor displacement in
Table 1 for $d=2$ with the robot assisted displacement in Section 3, we have
to reformulate Theorem 3 in Section 3 for the expected transportation cost.
This is the subject of Theorem 5.

######  Theorem 5.

Assume that $n$ sensors are placed on the plane $[0,\infty)\times[0,\infty)$
according to two identical and independent Poisson processes $X_{i}$ and
$Y_{i},$ for $i=1,2,\dots,\sqrt{n}$ each with arrival rate $\lambda>0.$ The
random position of the sensor on the plane is determined by the pair
$(X_{i_{1}},Y_{i_{2}}),$ where $i_{1},i_{2}=1,2,\dots,\sqrt{n}$ and $n=m^{2}$
for some $m\in\mathbf{N}.$ Fix $1\leq k\leq\sqrt{n}.$ Let
$j_{1},j_{2}\in\\{0,1,\dots,k-1\\}.$ Let $T^{(a,2)}_{(j_{1},j_{2},RS)}$ be
$T^{(a,2)}_{(RS)}$-transportation cost in algorithm $GM_{j_{1},j_{2}}(k,n).$
Then

$\frac{n^{a}}{\lambda^{a}}\left(1+O\left(\frac{1}{\sqrt{n}}\right)\right)\leq\mathbf{E}\left[\min_{0\leq
j_{1},j_{2}\leq k-1}T^{(a,2)}_{(j_{1},j_{2},RS)}\right],$ (21)
$\displaystyle\mathbf{E}\left[\min_{0\leq j_{1},j_{2}\leq
k-1}T^{(a,2)}_{(j_{1},j_{2},RS)}\right]$
$\displaystyle\leq\frac{(2^{3a-1}3^{a})n^{a}}{\lambda^{a}}\left(1+O\left(\frac{1}{\sqrt{n}}\right)\right)$
$\displaystyle+\left(4\left\lfloor\frac{\sqrt{n}}{k}\right\rfloor+16\right)^{a-1}4^{a-1}n^{a/2}\Bigg{(}4\mathbf{E_{\max}}\left[T^{(a,2)}_{(AS)}\right]+\frac{4\mathbf{E}\left[T^{(a,2)}_{(AS)}\right]}{k\sqrt{n}}\Bigg{)}.$
(22)

###### Proof.

There are two cases to consider

Case 1: Inequality (21)

Let us recall that the random variable $X_{i}-X_{1}$ is the sum of $i-1$
independent and identically distributed exponential random variables with
parameter $\lambda$ and obeys Gamma distribution with parameters
$i-1\in\mathbb{N}\setminus\\{0\\},\lambda>0$ (see [26, 37]). Therefore,
passing to the expectation in Corollary 2 and applying Formulas (17), (18) we
have the lower bound.

Case 2: Inequality (22)

Passing to the expectation in Equation (6) (see Theorem 3), applying Formulas
(17), (18), (19), (20), as well as the estimations

$\mathbf{E}\left[|M_{1}|^{a}\right]+\mathbf{E}\left[|N_{1}|^{a}\right]+\mathbf{E}\left[|M_{n}|^{a}\right]+\mathbf{E}\left[|N_{n}|^{a}\right]\leq
2\mathbf{E_{\max}}\left[T^{(a,2)}_{(AS)}\right]$

we get the upper bound.

It completes the proof of Theorem 5. ∎

Let us now compare the new result of Theorem 5 for the robot assisted movement
($\min_{0\leq j_{1},j_{2}\leq k-1}T^{(a,2)}_{(j_{1},j_{2},RS)}$ transportation
cost) with the known results for the autonomous sensors displacement
($T^{(a,2)}_{(AS)}$ transportation cost) in Table 1 for $d=2.$ Namely we find

$\min\left(\mathbf{E}\left[\min_{0\leq j_{1},j_{2}\leq
k-1}T^{(a,2)}_{(j_{1},j_{2},RS)}\right],\mathbf{E}\left[T^{(a,2)}_{(AS)}\right]\right)$

as the function of the robot capacity $k,$ the square sensing radius $r_{2}$
and the interference distance $s.$

Table 2 for $d=2$ displays the described comparison of the energy consumption
in the robot assisted movement and in the autonomous sensor displacement.

Table 3: Comparison of the expected transportation cost for the robot assisted movement with $k$-capacity and the autonomous sensor displacement to ensure $(r_{2},s)$-coverage and interference problem for $n$ sensors in the $[0,\infty)^{2},$ provided that $\epsilon\geq\delta>0$ are arbitrary small constants independent on $\lambda$ and $n.$ | Square
---
sensing
radius $r_{2}$
| Interference
---
distance $s$
Movement |  | Expected transportation cost
---
(Energy consumption)
$r_{2}=\frac{1+\epsilon}{2\lambda}$ | $s=\frac{1-\delta}{\lambda}$ |  $T^{(a,2)}_{(AS)}$ if $a\geq 1$ | $O\left(n\right)/\lambda^{a}$
$r_{2}=\frac{1}{2\lambda}$ | $s=\frac{1}{\lambda}$ |  $T^{(a,2)}_{(AS)}$ if $a>\frac{4}{3}$ | $O\left(n^{1+\frac{a}{4}}\right)/\lambda^{a}$
$r_{2}=\frac{1}{2\lambda}$ | $s=\frac{1}{\lambda}$ |  $T^{(a,2)}_{(RS)}$ if $a\in\left[1,\frac{4}{3}\right]$ |  |  $O\left(n^{\frac{5a}{4}}\right)/(k\lambda)^{a}\,\,\,$ if $\,\,\,k\in\left[n^{1-\frac{1}{a}},n^{\frac{1}{4}}\right]$
---
$\,\,\,\,\,\,\Theta\left(n^{a}\right)/\lambda^{a}\,\,\,$ if
$\,\,\,k\in\left[n^{\frac{1}{4}},\sqrt{n}\right]$
$r_{2}=\frac{1}{2\lambda}$ | $s=\frac{1}{\lambda}$ |  $T^{(a,2)}_{(AS)}$ if $a>2$ | $O\left(n^{1+\frac{a}{2}}\right)/\lambda^{a}$
$r_{2}=\frac{1+\epsilon}{2\lambda}$ | $s=\frac{1+\delta}{\lambda}$ |  $T^{(a,2)}_{(RS)}$ if $a\in\left[1,2\right]$ |  $O\left(n^{\frac{3a}{2}}\right)/(k\lambda)^{a}\,\,\,$ if $k\in\left[n^{1-\frac{1}{a}},\sqrt{n}\right]$

##  5 Discussions

In this study, the mobile robot with carrying capacity $k$ moves the random
sensors on the line and on the plane to provide the desired scheduling task.
The energy consumption in robot assisted movement is compared with the energy
consumption in autonomous sensor displacement. As the application to the
coverage and interference requirement, we obtained sharp decrease in the
expected transportation cost (see Table 1 and Table 2).

###  5.1 Unreliable Sensors

In the analysis of the coverage and interference requirement, the sensors were
assumed to be reliable, i.e., they sense and communicate correctly. However,
the proposed approach in Sections 2 and 3 is not limited only to the reliable
sensors. In fact, Theorem 2 and Theorem 3 also hold for unreliable sensors.
Moreover, when the sensors can not move, the robot assisted displacement is
the only option.

###  5.2 Sensors in the Higher Dimensions

The proposed theory for the robot assisted movement on the plane can be
extended to the higher dimensions. Fix $d\in\mathbf{N}\setminus\\{0,1,2\\}.$
Assume that $n$ sensors are initially randomly deployed on the
$[0,\infty)^{d}$ according to $d$ independent and general random processes and
$n=m^{d}$ for some $m\in\mathbf{N}.$ Let us recall that the mobile robot in
Algorithm 3 moves the sensors only in vertical and horizontal fashion. Hence,
Algorithm 3 can be extended to the sensors on the $[0,\infty)^{d}$ and the
robot’s movement to the movement only according to the axes. In particular,
the results in Table 3 can be extended valid to the sensors on the
$[0,\infty)^{d}$

###  5.3 Many Robots

Here we discuss a greedy approach to many robots assisted displacement. Fix
$p\in\mathrm{N}.$ Let $k_{j}\in\mathrm{N}$ and $1\leq k_{j}\leq n$ for
$j=1,2,\dots,p$. Assume that $j$-th robot can carry at most $k_{j}$ sensors
and deposit all or part of them at any time and to any suitable position it
chooses. The carrying capacity of the system of $p$ robots is defined as
$\sum_{j=1}^{p}k_{j}.$ Algorithm 1 (Greedy Procedure) can be modified for the
system of $p$ robots. Let $k:=\sum_{j=1}^{p}k_{j}$ and
$l\leq\sum_{j=1}^{p}k_{j}$ in Algorithm 1. Assume that all $p$ robots move
together, collect the sensors $Y_{1}\leq Y_{2}\leq\dots\leq Y_{l}$ and
displace at the final positions. Then, it is possible to develop the theory
similar to that presented in this paper. In particular, in modified Table 2
and Table 3 for the system of $p$ robots, the parameter $k$ is the arithmetic
mean of capacities $k_{1},k_{2},\dots,k_{p}$, i.e.,
$k=\frac{1}{p}\sum_{j=1}^{p}k_{j}$.

##  6 Numerical Results

In this section we use a set of experiments to show how the robot capacity $k$
impacts the transportation cost for the coverage and interference requirement
when the $n$ sensors are randomly placed on the line according to Poisson
process with arrival rate $\lambda=n$ and on the plane according to two
identical and independent Poisson processes each with arrival rate
$\lambda=\sqrt{n}.$ Namely, we implement Algorithm 2 for $a=1,$ $j=0$ and
$k\in\left\\{1,\lceil\sqrt{n}\rceil,n\right\\};$ Algorithm 2 for $a=2,$ $j=0$
and $k\in\left\\{\lceil\sqrt{n}\rceil,n\right\\};$ Algorithm 3 for $a=1,$
$j_{1}=j_{2}=0$ and $k\in\left\\{1,\sqrt{n}\right\\}.$

###  6.1 Evaluation of Algorithm 2 for $a=1$ and $j=0$

$T^{(1,1)}_{(0,RS)}=\frac{\sqrt{2}}{\Gamma\left(\frac{5}{2}\right)}\sqrt{n}$ Figure 3: The expected $T^{(1,1)}_{(0,RS)}$ transportation cost of Algorithm $GM_{0}(1,n)$ for $M_{i}=\frac{i}{n}-\frac{1}{2n}$ where $i=1,2,\dots,n$ and $k=1$ |  $T^{(1,1)}_{(0,RS)}=\Theta(1)$ Figure 4: The expected $T^{(1,1)}_{(0,RS)}$ transportation cost of Algorithm $GM_{0}\left(\lceil\sqrt{n}\rceil,n\right)$ for $X_{i}+M_{i}=\frac{i}{n}-\frac{1}{2n},$ where $i=1,2,\dots,n$ and $k=\lceil\sqrt{n}\rceil$
---|---
$T^{(1,1)}_{(0,RS)}=\frac{1}{5}n$ Figure 5: The expected $T^{(1,1)}_{(0,RS)}$ transportation cost of Algorithm $GM_{0}(1,n)$ for $X_{i}+M_{i}=\left(1+\frac{1}{5}\right)\left(\frac{i}{n}-\frac{1}{2n}\right),$ where $i=1,2,\dots,n$ and $k=1$ |  $T^{(1,1)}_{(0,RS)}=\Theta(1)$ Figure 6: The expected $T^{(1,1)}_{(0,RS)}$ transportation cost of Algorithm $GM_{0}(n,n)$ for $X_{i}+M_{i}=\left(1+\frac{1}{5}\right)\left(\frac{i}{n}-\frac{1}{2n}\right),$ where $i=1,2,\dots,n$ and $k=n$
---|---

For the case of Algorithm $GM_{0}(1,n)$ when the robot capacity $k=1$
(Algorithm 2 for $j=0$ and $k=1$) we conduct Algorithm 4.

Algorithm 4

1: $n:=1$

2: while n $\leq$ 55 do

3: for $l=1$ to $100$ do

4: Generate $X_{1}(l),X_{2}(l),\dots,X_{n^{2}}(l)$ random points on the
$[0,\infty)$ such that $\forall_{i\in\\{1,2,\dots,n^{2}\\}}\,\,X_{i}(l)$ is
the sum of $i$ independent and identically distributed exponential random
variables with parameter $\lambda=n^{2};$

5: Calculate $T_{1,n^{2}}(l)$ the distance travelled by the robotin Algorithm
2 for $j=0,$ and $k=1;$

6: end for

7: for $p=1$ to $10$ do

8: Calculate the
average$T_{1,n^{2}}=\frac{1}{5}\sum_{q=1}^{5}T_{1,n^{2}}(q+(p-1)*10);$

9: Insert the points $(n^{2},T_{1,n^{2}})$ into the chart;

10: end for

11: $n:=n+1$

12: end while

In Figures 4 and 6 the black dots represent the numerical results of conducted
Algorithm 4 for $X_{i}+M_{i}=\frac{i}{n}-\frac{1}{2n}$ and
$X_{i}+M_{i}=\left(1+\frac{1}{5}\right)\left(\frac{i}{n}-\frac{1}{2n}\right)$
where $i=1,2,\dots,n.$ The additional lines
$\left\\{(n,\frac{\sqrt{2}}{\Gamma(5/2)}\sqrt{n}),1\leq n\leq
55^{2}\right\\},$ $\left\\{(n,\frac{1}{5}n),1\leq n\leq 55^{2}\right\\},$ are
the leading terms in the theoretical estimation of the distance travelled by
the robot in Algorithm $GM_{0}(1,n)$ for $k=1$ when
$X_{i}+M_{i}=\frac{i}{n}-\frac{1}{2n}$ and
$X_{i}+M_{i}=\left(1+\frac{1}{5}\right)\left(\frac{i}{n}-\frac{1}{2n}\right)$
provided $i=1,2,\dots,n.$

Algorithm 5

1: $n:=1$

2: while n $\leq$ 50 do

3: for $l=1$ to $50$ do

4: Generate $X_{1}(l),X_{2}(l),\dots,X_{60n}(l)$ random points on the
$[0,\infty)$ such that $\forall_{i\in\\{1,2,\dots,n^{2}\\}}\,\,X_{i}(l)$ is
the sum of $i$ independent and identically distributed exponential random
variables with parameter $\lambda=n^{2};$

5: Calculate $\mathbf{V_{a,60n}}(l)$ the distance to the power $a$ travelled
by the robot in Algorithm 2 for $j=0,$ and $k;$

6: end for

7: for $p=1$ to $5$ do

8: Calculate the
average$\mathbf{V_{a,60n}}=\frac{1}{10}\sum_{v=1}^{10}\mathbf{V_{a,60n}}(v+(p-1)10);$

9: Insert the points $\mathbf{V_{a}}(60n)$ into the chart;

10: end for

11: $n:=n+1$

12: end while

Figures 4 and 6 depict the experimental distance travelled by the robot in
Algorithm 2 considering the parameters $j=0,$ $k=\lceil\sqrt{n}\rceil,$
$X_{i}+M_{i}=\frac{i}{n}-\frac{1}{2n},$ and $j=0,$ $k=n,$
$X_{i}+M_{i}=\left(1+\frac{1}{5}\right)\left(\frac{i}{n}-\frac{1}{2n}\right).$
In this case we conduct Algorithm 5 considering the parameters $a=1,$
$k=\lceil\sqrt{n}\rceil;$ $a=1,$ $k=n.$

The experimental distance travelled by the robot in Figures 4 and 6 is in
$\Theta(1).$ Hence, the carried out experiments confirm very well the obtained
theoretical upper bound $O(1)$ (see Table 2 for $a=1,$ $\lambda=n,$
$r_{1}=\frac{1}{2n},$ $s=\frac{1}{n},$ $k=\lceil\sqrt{n}\rceil$ and for $a=1,$
$\lambda=n,$ $r_{1}=\frac{1+\frac{1}{5}}{2n},$ $s=\frac{1+\frac{1}{5}}{n},$
$k=n$).

###  6.2 Evaluation of Algorithm 2 for $a=2$ and $j=0$

$T^{(2,1)}_{(0,RS)}=\Theta(1)$ Figure 7: The expected $T^{(2,1)}_{(0,RS)}$ transportation cost of Algorithm $GM_{0}\left(\lceil\sqrt{n}\rceil,n\right)$ for $X_{i}+M_{i}=\frac{i}{n}-\frac{1}{2n},$ where $i=1,2,\dots,n$ and $k=\lceil\sqrt{n}\rceil$ |  $T^{(2,1)}_{(0,RS)}=\Theta(1)$ Figure 8: The expected $T^{(2,1)}_{(0,RS)}$ transportation cost of Algorithm $GM_{0}(1,n)$ for $X_{i}+M_{i}=\left(1+\frac{1}{5}\right)\left(\frac{i}{n}-\frac{1}{2n}\right),$ where $i=1,2,\dots,n$ and $k=n$
---|---

We evaluate the distance to the power $2$ travelled by the robot in Algorithm
$GM_{0}(k,n)$ when the robot capacity $k=\lceil\sqrt{n}\rceil$ or $k=n$
(Algorithm 2 for $j=0$ and $k=\lceil\sqrt{n}\rceil,n$).

Figures 8 and 8 depict the experimental distance to the power $2$ travelled by
the robot in Algorithm 2 considering the parameters $j=0,$
$k=\lceil\sqrt{n}\rceil,$ $X_{i}+M_{i}=\frac{i}{n}-\frac{1}{2n},$ and $j=0,$
$k=n,$
$X_{i}+M_{i}=\left(1+\frac{1}{5}\right)\left(\frac{i}{n}-\frac{1}{2n}\right).$
In this case we conduct Algorithm 5 considering the parameters $a=2,$
$k=\lceil\sqrt{n}\rceil;$ $a=2,$ $k=n.$

The experimental distance to the power $2$ travelled by the robot in Figures 8
and 8 is in $\Theta(1).$ Hence, the carried out experiments confirm very well
the obtained theoretical upper bound $O(1)$ (see Table 2 for $a=2,$
$\lambda=n,$ $r_{1}=\frac{1}{2n},$ $s=\frac{1}{n},$ $k=1,\lceil\sqrt{n}\rceil$
and for $a=2,$ $\lambda=n,$ $r_{1}=\frac{1+\frac{1}{5}}{2n},$
$s=\frac{1+\frac{1}{5}}{n},$

###  6.3 Evaluation of Algorithm 3 for $a=1$ and $j_{1}=j_{2}=0$

For the case of Algorithm $GM_{0,0}(k,n)$ when the robot capacity $k=1$ or
$k=\sqrt{n}$ (Algorithm 3 for $j_{1}=j_{2}=0$ and $k=1,\sqrt{n}$), we conduct
Algorithm 6 for $k=1$ and $k=\sqrt{n}.$

Algorithm 6

1: $n:=1$

2: while n $\leq$ 55 do

3: for $l=1$ to $100$ do

4: Generate $n^{2}$ random points on the $[0,\infty)\times[0,\infty)$
according to two identical and independent Poisson processes $X_{i}$ and
$Y_{i},$ for $i=1,2,\dots,\sqrt{n^{2}}$ each with arrival rate
$\lambda=\sqrt{n^{2}}.$ The random position of the sensor with identical
square sensing radius $r_{2}$ on the plane is determined by the pair
$(X_{i_{1}}(l),Y_{i_{2}}(l)),$ where $i_{1},i_{2}=1,2,\dots\sqrt{n};$

5: Calculate $W_{1,n^{2}}(l)$ the distance travelled by the robotin Algorithm
3 for $j_{1}=j_{2}=0$ and $k;$

6: end for

7: for $p=1$ to $10$ do

8: Calculate the
average$W_{1,n^{2}}=\frac{1}{5}\sum_{q=1}^{5}W_{1,n^{2}}(q+(p-1)*10);$

9: Insert the points $(n^{2},W_{1,n^{2}})$ into the chart;

10: end for

11: $n:=n+1$

12: end while

$T^{(1,2)}_{(0,0,RS)}=\Theta(n)$ Figure 9: The expected $T^{(1,2)}_{(0,0,RS)}$ transportation cost of Algorithm $GM_{0,0}(1,n)$ for $\left(X_{i_{1}}+M_{i_{1}},Y_{i_{2}}+M_{i_{2}}\right)=\left(1+\frac{1}{5}\right)\left(\frac{i_{1}}{\sqrt{n}}-\frac{1}{2\sqrt{n}},\frac{i_{2}}{\sqrt{n}}-\frac{1}{2\sqrt{n}}\right),$ where $i_{1},i_{2}=1,2,\dots,\sqrt{n}$ and $k=1$ |  $T^{(1,2)}_{(0,0,RS)}=\Theta(\sqrt{n})$ Figure 10: The expected $T^{(1,2)}_{(0,0,RS)}$ transportation cost of Algorithm $GM_{0,0}(\sqrt{n},n)$ for $\left(X_{i_{1}}+M_{i_{1}},Y_{i_{2}}+M_{i_{2}}\right)=\left(1+\frac{1}{5}\right)\left(\frac{i_{1}}{\sqrt{n}}-\frac{1}{2\sqrt{n}},\frac{i_{2}}{\sqrt{n}}-\frac{1}{2\sqrt{n}}\right),$ where $i_{1},i_{2}=1,2,\dots,\sqrt{n}$ and $k=\sqrt{n}$
---|---

In Figures 6 and 10, the black dots represent the numerical results of
conducted Algorithm 6 for

$\left(X_{i_{1}}+M_{i_{1}},Y_{i_{2}}+M_{i_{2}}\right)=\left(1+\frac{1}{5}\right)\left(\frac{i_{1}}{\sqrt{n}}-\frac{1}{2\sqrt{n}},\frac{i_{2}}{\sqrt{n}}-\frac{1}{2\sqrt{n}}\right)$

where $i_{1},i_{2}=1,2,\dots,\sqrt{n},$ $k=1$ and $k=\sqrt{n}.$

Notice that, the experimental distance travelled by the robot in Figure 6 is
in $\Theta(n)$ and in Figure 10 is in $\Theta(\sqrt{n}).$ Hence, the carried
out experiments confirm very well the obtained theoretical upper bound $O(n)$
and $O(\sqrt{n})$ (see Table 3 for $a=1,$ $\lambda=\sqrt{n},$
$r_{2}=\frac{1+\frac{1}{5}}{2\sqrt{n}},$ $s=\frac{1+\frac{1}{5}}{\sqrt{n}},$
$k=1$ and for $a=1,$ $\lambda=\sqrt{n},$
$r_{2}=\frac{1+\frac{1}{5}}{2\sqrt{n}},$ $s=\frac{1+\frac{1}{5}}{\sqrt{n}},$
$k=\sqrt{n}$).

##  7 Conclusions

In this paper we addressed the problem of the robot assisted movement in WSNs
in which the sensors are initially randomly deployed on the line according to
general random process, and on the plane according to two independent general
random processes. To this end, we compared the transportation cost for robot
assisted movement with the transportation cost for autonomous sensor
displacement. We obtained tradeoffs between the energy consumption in robot’s
movement, the number of sensors $n$, the sensor range $r$, interference
distance $s$, the robot capacity $k$ until completion of the coverage and
interference scheduling task. While we have discussed the applicability of our
approach to greedy many robots assisted displacement, an open problem for
future study is the system of many robots assisted movement. Additionally, it
would be interesting to explore the system of many robots for others
trajectories on the plane and in the higher dimension.

## 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] H. M. Ammari and S. K. Das.  Critical density for coverage and connectivity in three-dimensional wireless sensor networks using continuum percolation.  IEEE Transactions on Parallel and Distributed Systems, 20(6):872–885, 2009.
  * [3] H. M. Ammari and S. K. Das.  Fault tolerance measures for large-scale wireless sensor networks.  ACM Trans. Auton. Adapt. Syst., 4(1), 2009.
  * [4] H. M. Ammari and S. K. Das.  Centralized and clustered k-coverage protocols for wireless sensor networks.  IEEE Transactions on Computers, 61(1):118–133, 2012.
  * [5] 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.
  * [6] Y. Chen, S. Huang, and R. Fitch.  Active slam for mobile robots with area coverage and obstacle avoidance.  IEEE/ASME Transactions on Mechatronics, 25(3):1182–1192, 2020.
  * [7] Z. Chen, X. Gao, F. Wu, and G. Chen.  A ptas to minimize mobile sensor movement for target coverage problem.  In IEEE INFOCOM 2016 - The 35th Annual IEEE International Conference on Computer Communications, pages 1–9, 2016.
  * [8] J. Czyzowicz, E. Kranakis, D. Krizanc, L. Narayanan, and J. Opatrny.  Optimal online and offline algorithms for robot-assisted restoration of barrier coverage.  Discrete Applied Mathematics, 285:650 – 662, 2020.
  * [9] Sajal K. Das and R. Kapelko.  On the range assignment in wireless sensor networks for minimizing the coverage-connectivity cost.  ACM Trans. Sen. Netw., 17(4), 2021.
  * [10] S. Dobrev, E. Kranakis, D. Krizanc, M. Lafond, J. Manuch, L. Narayanan, J. Opatrny, S. Shende, and L. Stacho.  Weak coverage of a rectangular barrier.  Algorithmica, 82:721–746, 2020.
  * [11] Kranakis E. and Shaikhet G.  Displacing random sensors to avoid interference.  In COCOON, volume 8591 of LNCS, pages 501–512. Springer, 2014\.
  * [12] C. Forbes, M. Evans, N. Hasting, and B. Peacock.  Statistical Distributions.  Wiley, 2011.
  * [13] P. Frasca, F. Garin, B. Gerencsér, and Hendrickx J. M.  Optimal one-dimensional coverage by unreliable sensors.  SIAM Journal on Control and Optimization, 53(5):3120–3140, 2015\.
  * [14] M. Fuchs, L. Kao, and W. Wu.  On binomial and poisson sums arising from the displacement of randomly placed sensors.  Taiwanese Journal of Mathematics, 24(6):1353 – 1382, 2020.
  * [15] X. Gao, J. Fan, F. Wu, and G. Chen.  Approximation algorithms for sweep coverage problem with multiple mobile sensors.  IEEE/ACM Transactions on Networking, 26(2):990–1003, 2018.
  * [16] A. Ghosh and S. K. Das.  Coverage and connectivity issues in wireless sensor networks: A survey.  Pervasive and Mobile Computing, 4:303–334, 2008.
  * [17] R. Kapelko.  On the maximum movement of random sensors for coverage and interference on a line.  In Proceedings of the 19th International Conference on Distributed Computing and Networking, pages 36:1–36:10. ACM, 2018.
  * [18] R. Kapelko.  On the maximum movement to the power of random sensors for coverage and interference.  Pervasive and Mobile Computing, 51:174 – 192, 2018.
  * [19] R. Kapelko.  Asymptotic formula for sum of moment mean deviation for order statistics from uniform distribution.  Discrete Mathematics, Algorithms and Applications, 11:1–23, April 2019.
  * [20] R. Kapelko.  On the energy in displacement of random sensors for interference and connectivity.  In Proceedings of the 21st International Conference on Distributed Computing and Networking, pages 1–10. ACM, 2020.
  * [21] R. Kapelko and E. Kranakis.  On the displacement for covering a square with randomly placed sensors.  In ADHOCNOW, volume 9143 of LNCS, pages 148–162. Springer, 2015.
  * [22] R. Kapelko and E. Kranakis.  On the displacement for covering a d-dimensional cube with randomly placed sensors.  Ad Hoc Networks, 40:37–45, 2016.
  * [23] R. Kapelko and E. Kranakis.  On the displacement for covering a unit interval with randomly placed sensors.  Information Processing Letters, 116:710–717, 2016.
  * [24] A. Khan, I. Noreen, and Z. Habib.  An energy efficient coverage path planning approach for mobile robots.  In Intelligent Computing, pages 387–397. Springer International Publishing, 2019.
  * [25] H. Kim, H. Oh, P. Bellavista, and J. Ben-Othman.  Constructing event-driven partial barriers with resilience in wireless mobile sensor networks.  Journal of Network and Computer Applications, 82:77 – 92, 2017\.
  * [26] J.F.C. Kingman.  Poisson Process, volume 3.  Oxford University Press, 1992.
  * [27] 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.
  * [28] S. Kumar, T. H. Lai, and A. Arora.  Barrier coverage with wireless sensors.  Wireless Networks, 13(6):817–834, Dec 2007.
  * [29] F. Li, J Luo, S. Xin, and Y. He.  Autonomous deployment of wireless sensor networks for optimal coverage with directional sensing model.  Computer Networks, 108:120 – 132, 2016.
  * [30] M.S. Miah and J. Knoll.  Area coverage optimization using heterogeneous robots: Algorithm and implementation.  IEEE Transactions on Instrumentation and Measurement, 67(6):1380–1388, 2018.
  * [31] D. S. Mitrinovic.  Analytic Inequalities.  Springer, 1970.
  * [32] S.M. Mohamed, H.S. Hamza, and I.A. Saroit.  Coverage in mobile wireless sensor networks (m-wsn): A survey.  Computer Communications, 110:133 – 150, 2017.
  * [33] O. Morales-Ponce.  Optimal patrolling of high priority segments while visiting the unit interval with a set of mobile robots.  In Proceedings of the 21st International Conference on Distributed Computing and Networking, ICDCN 2020, New York, NY, USA, 2020. Association for Computing Machinery.
  * [34] Vishnu G. Nair and K. R. Guruprasad.  Gm-vpc: An algorithm for multi-robot coverage of known spaces using generalized voronoi partition.  Robotica, 38(5):845–860, 2020.
  * [35] NIST Digital Library of Mathematical Functions.  http://dlmf.nist.gov/8.17.
  * [36] Chu-Liang L. Ping-Min H. and Meng-Yao Y.  On the complete coverage path planning for mobile robots.  Journal of Intelligent & Robotic Systems, 74:945–963, 2014.
  * [37] S. M. Ross.  Probability Models for Computer Science.  Academic press, 2002.
  * [38] J. Tian, X. Liang, and G. Wang.  Deployment and reallocation in mobile survivability-heterogeneous wireless sensor networks for barrier coverage.  Ad Hoc Networks, 36:321–331, 2016.
  * [39] M. Younis and K. Akkaya.  Strategies and techniques for node placement in wireless sensor networks: A survey.  Ad Hoc Networks, 6(4):621–655, 2008.
  * [40] Ch. Zhou, A. Mazumder, A. Das, K. Basu, N. Matin-Moghaddam, S. Mehrani, and A. Sen.  Relay node placement under budget constraint.  Pervasive and Mobile Computing, 53:1 – 12, 2019.