arXiv:1611.02861v2  [stat.AP]  30 Jan 2018
EXPECTED COVERAGE OF RANDOM WALK MOBILITY
ALGORITHM
MORITZ KOHLS AND TANJA HERNANDEZ
Abstract. Unmanned aerial vehicles (UAVs) have been increasingly used for explor-
ing areas. Many mobility algorithms were designed to achieve a fast coverage of a
given area. We focus on analysing the expected coverage of the symmetric random
walk algorithm with independent mobility.
Therefore we proof the dependence of
certain events and develop Markov models, in order to provide an analytical solution
for the expected coverage. The analytic solution is afterwards compared to those of
another work and to simulation results.
1. Introduction
There are several reasons to use UAVs instead of helicopters for exploring the area
of interest. The most important advantage should be the safety. The life of the crew is
risked, when the helicopter comes into operation in dangerous places. In some diﬃcult
surroundings there might be too many obstacles nearby, where the helicopter cannot
provide suﬃcient mobility to discover the area. Even in ﬂat terrain it argues for the
commitment of drones, because a helicopter ﬂight is associated with great costs. In
case of emergency it is necessary to discover the place of interest as fast as possible. A
network of UAVs can work together to achieve this goal faster than a single helicopter
could.
One of the simplest mobility algorithms for this purpose is the bordered symmetric
random walk. However, it may be supposed that this algorithm provides a rather weak
coverage performance. The aim of this work is therefore to deduce an analytical solution
for the expected coverage performance of this algorithm, so that one can compare the
coverage performance to those of other mobility algorithms. In especially, our results of
the expected coverage of the bordered symmetric random walk are compared to those
of another paper [1], to check the validation of the analytical results.
The composition of this work is made as follows. In chapter 2 related work is presen-
ted, in which another analytic solution is already contained. Chapter 3 involves the
analysis of the random walk mobility algorithms.
At ﬁrst, bordered and boundless
Markov chains for the mobility algorithms are proposed. Subsequently, the coverage
performance using the example of expected coverage is calculated. Finally, the two
analytical solutions are compared to the simulation results.
Department of Electrical Engineering and Information Technology
Technische Universität Dortmund, Germany
E-mail addresses: moritz.kohls@udo.edu, tanja.hernandez@hs-owl.de.
1
2
EXPECTED COVERAGE OF RANDOM WALK MOBILITY ALGORITHM
1
2
· · · · · · · · ··
· · · · · · · · ··
w −1
w
w + 1
w + 2
· · · · · · · · ··
· · · · · · · · ··
2w −1
2w
· · · · · · · · ··
· · · · · · · · ··
· · · · · · · · ··
· · · · · · · · ··
· · · · · · · · ··
· · · · · · · · ··
· · · · · · · · ··
· · · · · · · · ··
· · · · · · · · ··
· · · · · · · · ··
· · · · · · · · ··
· · · · · · · · ··
(d −2)w + 1
(d −2)w + 2
· · · · · · · · ··
· · · · · · · · ··
(d −1)w −1
(d −1)w
(d −1)w + 1
(d −1)w + 2
· · · · · · · · ··
· · · · · · · · ··
dw −1
dw
Table 1. Sequence of all dw states of the two-dimensional exploration
area with width w and depth d.
2. Related work
An analytical approach to the calculation of the expected coverage is given in [1]. A
stochastic process is deﬁned, which enables the authors to provide a formula for cover-
age metrics like expected coverage and full coverage probability. However, the formulas
of the metrics derived from the examined Markov model base upon not mentioned
preconditions, which do not apply to Markov models generally. By taking the precon-
ditions of the Markov model into consideration, the analytical solution for the expected
coverage becomes considerably more complicated. The exposure to Markov chains is
executed in [2]. The numeric programming is accomplished by statistical software R
[3].
3. Analysis of the Markov chains
3.1. Markov Chain. At ﬁrst, it is necessary to introduce the mobility algorithm that
is investigated in this paper. Foremost, we focus on examining the mobility algorithm
in a two-dimensional exploration area.
Indeed, the three-dimensional case provides
similar results, but with the great drawback that with an increasing number of states
the computation time for realistic large areas increases unnecessarily. Another practical
problem of the three-dimensional model would be the huge size of the required matrices,
which have to be multiplied for the analytic solution. This often exceeds the limits of
the utilised numerical software. Thus, for now we constrain the exploration area of the
UAVs to a two-dimensional lattice. For convenience, we determine the position of the
drones as a ﬁnite set of states where they can be located on discrete time points. The
units of location and time can be chosen arbitrarily.
The UAVs move randomly, therefore we deal with a discrete-value and discrete-time
stochastic process, which equates to a homogeneous and discrete-time Markov chain
M := (E, π0, P). The state space E contains every point on a two-dimensional grid
with width w and depth d for the two-dimensional case and additionally height h for
the three-dimensional case. One could deﬁne these points as two-dimensional vectors
(i, j) for i = 1, . . . , w and j = 1, . . . , d, however, for the mathematical handling we
need to sequence the individual states in order to receive a one-dimensional numbering.
For this purpose we sequence the states on the considered rectangular grid as in table
1. An algorithm for sequencing an arbitrary three-dimensional grid is provided in the
appendix.
EXPECTED COVERAGE OF RANDOM WALK MOBILITY ALGORITHM
3
1
2
3
4
5
6
7
8
9
1/4
1/4
1/4
1/4
1/2
1/2
1/3
1/3
1/3
Figure 3.1. Transition probabilities of the bordered symmetric random
walk of the states 1, 5 and 6.
So, the state space consists of d · w single states E := {1, . . . , dw}. The starting
distribution π0 contains the probabilities for the points, in which the drones start their
ﬂight at point in time 0. If all UAVs start from the same point i ∈{1, . . . , dw}, we
would choose π0 as the unit vector ei. If one refuses to decide on a deterministic starting
point, π0 :=
  1
dw, . . . , 1
dw

is a reasonable election for the starting distribution, because
then every state has an equal probability for the start.
The examined mobility algorithm determines the transition probabilities pij for a
transition from state i to state j.
The transition probabilities form the transition
matrix P, which has as many rows and columns as the Markov chain has diﬀerent
states, thus dw for the two-dimensional example.
The distance between two places
can be calculated by using the taxicab geometry. So the drones are only allowed to
ﬂy into at most four diﬀerent directions in a two-dimensional world and six directions
(dimensions times two) in the three-dimensional world.
Figure 3.1 shows the transition probabilities for the ﬁrstly named application. Inside
of the exploration area there is an equal probability of 1
4 for ﬂying forward, backward,
to the left or right on a symmetric random walk.
On the brinks of the area three
directions remain and in the corners only two ﬂight directions are still possible, at
least when borders exist which should be standard case. Without borders the drones
can leave the grid, only to reappear on the opposite side (see ﬁgure 3.2). In this case
the transition probabilities remain at 1
4 even for the marginal and corner states. For
example, we present the transition matrix of the 3 × 3 bordered symmetric random
walk in table 2, whereupon entries with probability 0 are omitted on grounds of clarity.
3.2. Calculation of the Expected Coverage. It takes some deﬁnitions concerning
random variables to calculate the expected coverage of the symmetric random walk
(Xn)n∈N0. Let Cn,z indicate, if drone d has visited state z until point in time n, thus
4
EXPECTED COVERAGE OF RANDOM WALK MOBILITY ALGORITHM
1
2
3
4
5
6
7
8
9
1/4
1/4
1/4
1/4
1/4
1/4
1/4
1/4
1/4
1/4
1/4
1/4
Figure 3.2. Transition probabilities of the symmetric random walk
without borders of the states 1, 5 and 6.













1
2
1
2
1
3
1
3
1
3
1
2
1
2
1
3
1
3
1
3
1
4
1
4
1
4
1
4
1
3
1
3
1
3
1
2
1
2
1
3
1
3
1
3
1
2
1
2













Table 2. Transition matrix of the bordered symmetric random walk
with width and depth 3.
whether a coverage occurred (Cn,z = 1) or not. So, it is essential that
(3.1)
Cn,z :=
(
1
if X0 = z ∨X1 = z ∨... ∨Xn = z
0
else
.
These random variables are Bernoulli-distributed with for now unknown parameters
pn,z. It should be mentioned that for a constant point in time n the random variables
Cn,z for z = 1, . . . , |E| neither are stochastically independent nor identical distributed
which can be proven trivially. The same proposition can be made for all n ∈N0, if a
particular state z is considered. We will now conﬁrm the dependence of the random
variables in the last named case. But primarily, some characteristics of probability
theory are needed.
Deﬁnition 3.1. Independence of Events
Let A1, . . . , An be events at the same probability space. The events A1, . . . , An are
stochastically independent if and only if for all k ∈{1, ..., n} and every index space
EXPECTED COVERAGE OF RANDOM WALK MOBILITY ALGORITHM
5
I = {i1, ...ik} ⊆{1, ..., n} of the cardinality k
(3.2)
P(Ai1 ∩... ∩Aik) = P(Ai1) · ... · P(Aik)
is valid.
Corollary 3.2. Independence of Events
The events A and B are stochastically independent, if and only if P(B) = 0 or the
equation
(3.3)
P(A|B) = P(A)
is satisﬁed for P(B) > 0.
Proposition 3.3. State Probabilities of a Markov Chain
The starting distribution π0 is a |E|- dimensional row vector and contains the prob-
abilities for starting in each of the states z ∈E. The state probabilities after n time
steps are calculated by
πn = π0 · P n.
Below we proof the mentioned claim, which is the central conclusion of this paper.
Proposition 3.4. Dependence of Coverage Events (1)
The events {X0 = z}, ..., {Xn = z} are stochastically dependent for n ≥3 and at
least one state z.
Proof. The exploration area of the UAVs shall be big enough on grounds of realistic
scenarios which requires a minimum cell count of ﬁve in each dimension. Apparently,
the Markov chain holds P(Xt = z, Xt+1 = z) = 0 for every point in time and state,
because the drones keep in motion.
Case 1: The starting distribution has at least two states with an uneven Manhattan-
distance to each other, that both have a positive probability on point in time zero.
In this case all states have a positive probability from a particular point in time
onwards. Mathematically expressed, P(Xt = z) > 0 and P(Xt+1 = z) > 0 apply from
a particular point in time n for every state z. In worst-case, n constitutes still less
than width + depth for the two-dimensional case respectively width + depth + height
for the three-dimensional case. The worst-case occurs, if the UAVs can only start from
a corner, however state z is located in the opposite corner.
Not later than at this
particular time applies
P(Xt = z, Xt+1 = z) = 0 < P(Xt = z) · P(Xt+1 = z),
whereby the chronologically succeeding events {Xt = z} and {Xt+1 = z} are stochastic-
ally dependent, likewise all chronologically succeeding events for arbitrary z ∈E.
A typical special case of the ﬁrst case is the starting distribution with an equal
probability for every state. One realizes easily that the requirement in ﬁrst case is
achieved, if a random walk without borders has at least an uneven width, depth or
height.
Case 2: The starting distribution has no pair of states with an uneven Manhattan-
distance to each other.
6
EXPECTED COVERAGE OF RANDOM WALK MOBILITY ALGORITHM
A typical example is, if the drone takes oﬀdeﬁnitely from one particular whereabouts.
It needs at the most width + depth (+ height) time steps, until approximately half of
the states receive a positive probability.
(If dw is even, there are exactly
dw
2
such
states for the two-dimensional case; if dw is uneven, the number of such states switches
between
dw−1
2
and
dw+1
2
). Let this point in time be notated as m.
Now we pick a
state z and check the independence property P(Xm+2 = z|Xm = z) = P(Xm+2 = z)
as mentioned in corollary 3.2. The conditional probability P(Xm+2 = z|Xm = z) is
only deﬁned, if P(Xm = z) is greater than zero. Otherwise the events {Xm = z} and
{Xm+2 = z} would be stochastically independent, which is true for up to half of the
states in the bordered random walk for the second case. Below we will show that both
events are even independent under the constraint P(Xm = z) = 1.
P(Xm+2 = z|Xm = z)
=
P(Xm+2 = z)
(3.4)
⇔P 2(z, z)
=
|E|
X
i=1
P(Xm = i)P 2(i, z)
(3.5)
⇔P 2(z, z)
=
P(Xm = z)P 2(z, z) +
|E|
X
i=1,i̸=z
P(Xm = i)P 2(i, z)
(3.6)
⇐
P(Xm = z) = 1
(3.7)
Hence it can be reasoned that both events are independent, if P(Xm = z) ∈{0, 1}. This
applies in the mentioned special case, if the drone departs deﬁnitely from one particular
state. Then {X0 = z}, {X1 = z} and {X2 = z} are independent for all states z ∈E.
On the contrary, for diﬀerent starting distributions, {X0 = z} and {X2 = z} can be
stochastically dependent, because at least two distinct states z1 and z2 provide the
inequality 0 < π0(z1), π0(z2) < 1.
To summarize, the events {Xm = z} and {Xm+2 = z} are dependent if and only if
(3.8)
P(Xm = z) ∈(0, 1)
and
(3.9)
(1 −P(Xm = z)) P 2(z, z) ̸=
|E|
X
i=1,i̸=z
P(Xm = i)P 2(i, z).
This should be valid in most examined Markov models at least for one state z ∈E
and m ≥1. Below, the second case is analysed in more detail, in order to proof the
dependence for some sub cases. Note that for the missing sub cases the dependence
characteristic can be conﬁrmed by checking the correctness of the above mentioned
formulas 3.8 and 3.9, as soon as the concrete Markov model is created.
Special Case of case 2: Bordered Random Walk
We will focus on the two-dimensional bordered random walk, ﬁrstly with an uneven
width and depth. The three-dimensional case proceeds similarly. The starting distri-
bution shall be symmetric for now, for example the drone starts certainly in the middle
of the grid. Let the point of time m be such that in the corners 1, w, (d −1)w + 1
and dw the states have a positive probability. Notice that this is only possible with
EXPECTED COVERAGE OF RANDOM WALK MOBILITY ALGORITHM
7
an uneven width and depth. For the transition probability in two steps one can easily
deduce P 2(1, 1) = P 2(w, w) = P 2 ((d −1)w + 1, (d −1)w + 1) = P 2(dw, dw) = 1
3. The
unconditional probability P(Xm+2 = z) can be obtained by formula
(3.10)
P(Xm+2 = z) =
|E|
X
i=1
P(Xm = i)P 2(i, z).
This implicates for the top left corner the equality
P(Xm+2 = 1)
= P(Xm = 1) · P 2(1, 1) + P(Xm = 3) · P 2(3, 1)
+P(Xm = 2w + 1) · P 2(2w + 1, 1) + P(Xm = w + 2) · P 2(w + 2, 1)
= 1
3P (Xm = 1) + 1
9P (Xm = 3) + 1
9P (Xm = 2w + 1) + 1
12P (Xm = w + 2)
= 1
3
as a necessary and suﬃcient constraint for the independence. Due to the symmetric
starting distribution all corner states provide the same probability P(Xm+2 = 1) =
P(Xm+2 = w) = P (Xm+2 = (d −1)w + 1)) = P(Xm+2 = dw) whose sum can be at
most 1. The outcome of this is P(Xm+2 = 1) ≤
1
4 which is less than 1
3, hence the
condition 3.5 is not pervaded and therefore the events are dependent.
In some settings the starting distribution cannot be modelled as symmetric and the
recent proof cannot be executed in an analogous manner, although the probabilities
for the corner states will converge to the same positive value, if only even respectively
uneven points in time are considered. Below we will consider not only an asymmetric
starting distribution, but also a grid with at least one even dimension. At least half of
the dw states have a positive probability on time step m, if at least one corner state
provides a positive probability. Remember that this is only true for times m, m + 2,
m + 4 and so on in the event of uneven width and depth, but true for all times m,
m + 1, m + 2 and so on in the event of at least one even dimension.
According to this, the average state probability of those states with a positive probab-
ility is not exceeding
2
dw−1. It should be clear that the corner states provide a probability
less than this in the long run because of the secluded location. So, for a particular corner
state z∗the probability should be P(Xm+2 = z∗) ≤
2
dw−1. In grids of not less than 8
states the probability P(Xm+2 = z∗) becomes less than
2
8−1 =
2
7 ≤
1
3 and therefore
independence becomes impossible. The two-step probability remains at 1
3, but in big
exploration areas each state is visited infrequently and the probability for being in a
corner state drops below 1
3.
Case 3: Boundless Random Walk
A boundless random walk enables the UAVs to leave the grid on one side, in order
to reappear on the other side. We will now examine a grid with at least one uneven
dimension. A drone can ﬂy in one direction and straight back in two time units. In a
bordered random walk the recurrence time to any state is always even, in contrast in
a boundless random walk with at least one uneven dimension a drone can back to the
8
EXPECTED COVERAGE OF RANDOM WALK MOBILITY ALGORITHM
starting point in an uneven number of time steps, too. This reduces to the ﬁrst case,
by what the events are dependent.
□
The objective is to calculate the expected coverage and therefore it is not in someone’s
interest to have independent events {X0 = z} , {X1 = z} , {X2 = z} , . . . , but to have
independent events {X0 ̸= z} , {X1 ̸= z} , {X2 ̸= z} and so on.
Claim 3.5. The events A and B are independent, if and only if the complementary
events Ac and Bc are independent.
Proof. As argued before, the events A and B are independent, if and only if P(A∩B) =
P(A) · P(B) is valid.
P(Ac ∩Bc)
=
P((A ∪B)c) = 1 −P(A ∪B) = 1 −(P(A) + P(B) −P(A ∩B))
P(Ac) · P(Bc)
=
(1 −P(A))(1 −P(B)) = 1 −P(A) −P(B) + P(A)P(B)
=
1 −(P(A) + P(B) −P(A)P(B))
The equation P(Ac∩Bc) = P(Ac)·P(Bc) is true, if and only if P(A∩B) = P(A)·P(B)
is valid.
□
Theorem 3.6. Dependence of Coverage Events (2)
The events {X0 ̸= z}, ..., {Xn ̸= z} are stochastically dependent for n ≥3 and at
least one state z.
Proof. The proof follows directly from proposition 3.4 and claim 3.5.
□
It was shown that the considered events {X0 ̸= z}, ..., {Xn ̸= z} are stochastically
dependent generally. Recall the deﬁnition
Cn,z =
(
1
if X0 = z ∨X1 = z ∨... ∨Xn = z
0
else
for the coverage of state z up to time step n. If one takes no notice of the dependence
characteristic and assumes independence, the coverage probability of a single state is
easy to calculate. The just made assumption leads to the coverage probability
(3.11)
P (Cn,z = 1) = 1 −
n
Y
t=0
(1 −P(Xt = z) ,
like written in [1]. However, this formula cannot be true in general, because it disregards
the presence of theorem 3.6. In order to take the dependence characteristic into account,
one must specify appropriate Markov chains. Let the ﬁrst arrival time in state z be Az
with the relation
Az := n ⇐⇒X0 ̸= z, X1 ̸= z, ..., Xn−1 ̸= z, Xn = z.
State z is visited until time n, if and only if the ﬁrst arrival in this state is at the latest
on point n of time. By reason of
(3.12)
P(Cn,z = 1) = P(Az ≤n)
EXPECTED COVERAGE OF RANDOM WALK MOBILITY ALGORITHM
9













1
2
1
2
1
3
1
3
1
3
1
2
1
2
1
3
1
3
1
3
1
1
3
1
3
1
3
1
2
1
2
1
3
1
3
1
3
1
2
1
2













Table 3. Transition matrix P5 of the bordered symmetric random walk
in a 3 × 3 - grid with absorbing state 5.
the coverage probabilities can be reduced to the calculation of arrival probabilities. In
order to receive the sought-after probabilities, we need to create a new Markov chain for
every state in the considered random walk model. Subject to state r ∈E the associated
Markov chain is named Mr. The just introduced new Markov chains M1, . . . M|E| accord
with the Markov chain M (for example as in table 2) nearly complete, but there are
minor diﬀerences. State space and starting distribution coincide perfectly, but there is
a change in row r of the transition matrix Mr, r = 1, . . . |E|. The transition matrix Pr
contains a one in row and column r and zeros elsewhere in row r, as is evident in table
3.
This change eﬀects an altered behaviour of the Markov chain Mr compared to M.
State r is called absorbing, because the stochastic process remains in this state as soon
as it has visited this state for the ﬁrst time. Until this event, the behaviour of Markov
chain Mr is identical to that of the original Markov chain M. In order to calculate
the probability P(Ar ≤n) in the original Markov chain M, we can go over to the new
Markov chain Mr which will be used henceforward. The ﬁrst arrival time does not
change, because both Markov chains behave exactly identical till the ﬁrst arrival. In
the new Markov model Mr it meets to check the location of the random walk on point
n of time, because
(3.13)
Ar ≤n ⇐⇒Xn = r
holds. The probability of the latter term can be obtained, as customary in Markov
chains, by multiplication of the starting distribution with the exponentiated transition
matrix, thus
(3.14)
P(Cn,r = 1) = (π0P n
r )r
and the r-th value of this row vector is selected. This can be done for all states r ∈E,
but remember that every state r requires its own transition matrix Pr. The expected
coverage of the random walk after n time steps is the expected value
(3.15)
E
P
r∈E Cn,r
|E|

=
P
r∈E E (Cn,r)
|E|
=
P
r∈E P (Cn,r = 1)
|E|
=
P
r∈E (π0P n
r )r
|E|
10
EXPECTED COVERAGE OF RANDOM WALK MOBILITY ALGORITHM
divided by the number of states in the Markov model. It is about the ratio of the
states in the Markov chain that has been visited after n time steps, that is to be expec-
ted. Altogether the handling with dependent events leads to a much more complicated
solution of the expected coverage as though one ignores this pre-assumption.
3.3. Independent Mobility. So far, the expected coverage of a single UAV was cal-
culated. However, one of the greatest advantages of the operation of UAVs in contrary
to helicopters is that the former can be used in groups, even at places with little room.
Together they can explore the target area faster, especially if they cooperate.
For
the sake of convenience we limit on independent mobility, so that each drone uses the
same Markov model M for exploring, independent of the movement of the other UAVs.
Thereby the coverage probability in 3.14 changes to
(3.16)
P
 Cmulti
n,r
= 1

= 1 −(1 −P (Cn,r = 1))|E| = 1 −(1 −(π0P n
r )r)|E| .
3.4. Comparison of Analytic and Simulation Results. The analytic solution of
the expected coverage was deduced on the whole. The analytic results are conﬁrmed
by MCMC simulations which can be easily coded once the transition probabilities are
available. However, there is a great gap between the analytic formula 3.11, that ignores
the dependence of events, and the correct analytic results 3.14 as well as the simulation
results. In [1] it is concluded that this peculiarity is due to error propagation. This
argument can be excluded, because the correct formula 3.14 and the simulation results
show no deviation and therefore are in agreement. On grounds of numerical computab-
ility, MCMC- simulations should be preferred opposite to the analytic formula, because
the simulations can provide approximately exact results and can handle Markov models
with huge state spaces considerably better.
4. Conclusions
In this work, we introduced Markov chains with and without borders in two and
three dimensions. We deduced an analytic solution of the expected coverage in case of
independent mobility. Though it was proven that certain events are not independent,
which complicates the calculation vastly. The non-consideration of this fact leads to an
incorrect solution for the expected coverage which cannot be explained by numerical
inaccuracy.
Hence, MCMC simulations provide still a good approximation for the
analytic results.
References
[1] E. Yanmaz, C. Costanzo, C. Bettstetter and W. Elmenreich, "A discrete stochastic process for
coverage analysis of autonomous UAV networks," 2010 IEEE Globecom Workshops, Miami, FL,
2010, pp. 1777-1782.
[2] Pierre Bremaud: Markov Chains: Gibbs Fields, Monte Carlo Simulation, and Queues. Berlin
Heidelberg: Springer Science & Business Media, 2013.
[3] R Core Team (2016). R: A language and environment for statistical computing. R Foundation for
Statistical Computing, Vienna, Austria. URL https://www.R-project.org/.
EXPECTED COVERAGE OF RANDOM WALK MOBILITY ALGORITHM
11
Appendix: Sequencing in Three-Dimensional Grids
The sequencing and computation of the transition matrix for the bordered symmetric
random walk in three-dimensional grids are programmed in R [3].
# The st a t es
are
sequenced
f i r s t l y
on p o s i t i v e x−direction ,
# then in
p o s i t i v e y−dir ect io n
and eventually
in
p o s i t i v e z−dir ect io n .
# That means ,
the node with the
coordinates
(x , y , z )
# holds the number x+w(y−1)+wd( z −1).
calculateTransitionMatrix3d = function
( width
, depth
,
height
) {
w = width
d = depth
h = height
numberOfStates = w∗d∗h
P = matrix ( 0
, nrow = numberOfStates
,
ncol = numberOfStates )
nodePoints = matrix ( 0
, nrow = numberOfStates
,
ncol = 3 )
nodeNumber = 0
f o r
( z in
1: h ) {
f o r
( y in
1: d ) {
f o r
( x in
1:w ) {
nodeNumber = nodeNumber + 1
nodePoints
[ nodeNumber
,
] = c (x , y , z )
}
}
}
calculateNeighbourNodes = function
( x
, y
, z ) {
neighbourNodes = matrix ( nrow = 0
,
ncol = 3)
i f
( x > 1 )
neighbourNodes = rbind
( neighbourNodes
, c ( x−1 , y
, z ) )
i f
( x < w )
neighbourNodes = rbind
( neighbourNodes
, c ( x+1 , y
, z ) )
i f
( y > 1 )
neighbourNodes = rbind
( neighbourNodes
, c ( x
, y−1 , z ) )
i f
( y < d )
neighbourNodes = rbind
( neighbourNodes
, c ( x
, y+1 , z ) )
i f
( z > 1 )
neighbourNodes = rbind
( neighbourNodes
, c ( x
, y
, z−1 ) )
i f
( z < h )
neighbourNodes = rbind
( neighbourNodes
, c ( x
, y
, z+1 ) )
12
EXPECTED COVERAGE OF RANDOM WALK MOBILITY ALGORITHM
return
( neighbourNodes
)
}
neighbourNodes = l i s t
()
nodeDegrees = c ()
nodeNumber = 0
f o r
( z in
1: h ) {
f o r
( y in
1: d ) {
f o r
( x in
1:w ) {
nodeNumber = nodeNumber + 1
neighbourNodes
[ [
nodeNumber
] ]
= calculateNeighbourNodes
( x
, y
, z )
nodeDegrees
[ [
nodeNumber
] ]
= nrow ( neighbourNodes
[ [
nodeNumber
] ]
)
}
}
}
nodeTransformation = function
( x
, y
, z ) {
return
( x + w ∗(y−1) + w ∗d ∗( z−1) )
}
transformedNeighbourNodes = l i s t ()
nodeNumber = 0
f o r
( z in
1: h ) {
f o r
( y in
1: d ) {
f o r
( x in
1:w ) {
res = c ()
nodeNumber = nodeNumber + 1
f o r
(
i
in
1: nrow ( neighbourNodes
[ [
nodeNumber
] ]
) ) {
value1 = neighbourNodes
[ [
nodeNumber
] ]
[ i , 1 ]
value2 = neighbourNodes
[ [
nodeNumber
] ]
[ i , 2 ]
value3 = neighbourNodes
[ [
nodeNumber
] ]
[ i , 3 ]
res = c (
res
, nodeTransformation
(
value1
,
value2
,
value3
) )
}
transformedNeighbourNodes
[ [
nodeNumber
] ] = res
}
}
}
EXPECTED COVERAGE OF RANDOM WALK MOBILITY ALGORITHM
13
f o r
( nodeNumber in
1: numberOfStates ) {
P [ nodeNumber
, transformedNeighbourNodes
[ [
nodeNumber
] ]
]
= 1 / nodeDegrees
[ nodeNumber ]
}
return
( P )
}