A statistical analysis of the long-run node spatial distribution in mobile ad hoc networks.
In this paper, we analyze the node spatial distribution of mobile wireless ad hoc networks. Characterizing this distribution is of fundamental importance in the analysis of many relevant properties of mobile ad hoc networks, such as connectivity, average route length, and network capacity. In particular, we have investigated under what conditions the node spatial distribution resulting after a large number of mobility steps resembles the uniform distribution. This is motivated by the fact that the existing theoretical results concerning mobile ad hoc networks are based on this assumption. In order to test this hypothesis, we performed extensive simulations using two well-known mobility models: the random waypoint model, which resembles intentional movement, and a Brownian-like model, which resembles nonintentional movement. Our analysis has shown that in Brownian-like motion the uniformity assumption does hold, and that the intensity of the concentration of nodes in the center of the deployment region that occurs in the random waypoint model heavily depends on the choice of some mobility parameters. For extreme values of these parameters, the uniformity assumption is impaired.
INTRODUCTION
ad hoc networks have received increasing interest
in the scientic community in recent years. However,
due to their complex and unstructured nature, very few analytical
results describing their fundamental properties have
been derived. Among them, the most notable concern the
connectivity and coverage problems for stationary networks,
which have been analyzed in [10, 20]. A common assumption
in these studies is that nodes are distributed in a given area
according to a probability distribution; the value of the node
transmitting range ensuring a connected network (or coverage
of the deployment area) with high probability is then
derived. Another important theoretical result for stationary
ad hoc networks is presented in [11], where it is shown that
the capacity of the network does not scale with its size.
If deriving analytical results for stationary networks is dif-
cult, even more challenging is deriving theoretical results
regarding mobile ad hoc networks. This has been done, for
example, in [9], where it is shown that, contrary to the stationary
case, the capacity of mobile ad hoc networks can
actually scale with the size. Less general analytical results
for mobile networks have been derived in [1, 17], where two
variations of the DSR routing protocol are evaluated in a
theoretical framework.
As in the case of stationary networks, these results rely on
some assumptions on the node spatial distribution, which
are designed to simplify the analysis. In particular, in [1,
9] it is assumed that: 1. (uniformity assumption) in any
snapshot of the mobile network the nodes are distributed
uniformly and independently at random in the deployment
area; 2. (independence assumption) dierent snapshots are
independent. With these hypotheses, a mobile network composed
by n nodes performing N mobility steps can be modeled
as N independent experiments, where each experiment
consists in distributing the n nodes uniformly in the deployment
region.
Although these assumptions are not unrealistic, their likelihood
heavily depends on the initial node distribution and
on the mobility pattern considered. It follows that the choice
of the mobility model and/or of the initial node distribution
could have a dramatic impact on the accuracy of these analytical
results. Hence, the in
uence of the mobility pattern
and/or of the initial distribution on the node spatial distribution
after a large number of mobility steps should be
precisely evaluated.
Probabilistic mobility modeling has been extensively studied
in the related eld of cellular networks. For a survey of
probabilistic modeling of cellular networks see [3]. However,
these results are not applicable to ad hoc networks. In fact,
most of them concern specic properties of cellular networks
(e.g., cell residence time, number of handos during a call,
and so on). Furthermore, the emphasis is usually on modeling
the properties of a single mobile user, rather than on
the global mobile user's distribution. Finally, the mobility
patterns considered resemble the typical motions that occur
in cellular systems, i.e. human and vehicular motion.
Hence, an accurate study of the probabilistic properties of a
mobile ad hoc network is, to the best of our knowledge, still
lacking.
Preliminary steps in this direction have been recently done
in [3, 4], where it has been observed that in the well known
random waypoint model nodes tend to concentrate in the
center of the deployment region, causing the so called border
eect. However, the intensity of this border eect has
not been carefully evaluated, and in particular its dependence
on the choice of the mobility parameters has not been
In this paper, we perform a further step in understanding
the node spatial distribution generated by mobile ad hoc
networks. In particular, we study under what conditions is
the uniformity assumption used to derive the analytical results
of [1, 9] valid. The mobility patterns considered, which
are described in detail in Section 3, account for two dierent
kinds of motion: intentional, which is modeled using the random
waypoint model, and non-intentional, which is modeled
by a Brownian-like motion. In the case of the random way-point
model, we investigate the conditions (i.e., the choices
of the mobility parameters) under which the spatial distribution
(which is not uniform) can be well approximated by
the uniform distribution.
In order to test the uniformity of the nodes' spatial dis-
tribution, we have designed a collection of statistical tests
tailored to wireless ad hoc networks. Each of these tests
measures a feature of the node distribution that is of interest
in the design of wireless ad hoc networks. Details on the
uniformity test used in this paper can be found in Section
2.
In addition to its intrinsic importance as a fundamental
property of mobile ad hoc networks, the study of the node
spatial distribution is signicant in a number of ways. For
example, the distribution of route lengths is of critical importance
in determining the performance of mobile routing
algorithms [1, 12, 17]. Longer routes have a higher probability
of becoming invalid due to node mobility than shorter
ones. When routes become invalid, these algorithms incur
overhead in discovering new ones. Observe that the route
length distribution can be determined directly from the node
spatial distribution when all nodes have the same transmitting
range.
Another area in which node spatial distribution is highly
relevant is in the evaluation of network capacity, where route
length and node spatial distribution are important factors
[9, 11]. For example, a node concentration in the center
of the deployment region, as we see with the random way-point
model, reduces average route lengths, which tends to
increase capacity. However, this concentration also exacerbates
interference, which has the opposite eect of decreasing
capacity. A detailed modeling and evaluation of capacity
is beyond the scope of this paper, but quantifying the
node spatial distribution should make more accurate capacity
evaluation possible in the future.
2. AN UNIFORMITY TEST FOR AD HOC
Statistical tests are commonly used to verify the conformity
of a large set of observations to a given distribu-
tion. A typical test is as follows. Suppose H is the statistical
hypothesis that we want to test, i.e. that a sample
consisting of a large number of independent observations
is taken from the continuous distribution
F (x). Let  be a statistic calculated on the sam-
ple, and assume that, in the hypothesis that observations
are distributed according to F (x), the limit distribution of
, i.e. the probability distribution of  when l ! 1, is
known. Let CDF be the cumulative distribution function
of this distribution, i.e. CDF
let
be the value of the statistic calculated on X . The
test is as follows: if C1
C2 the hypothesis H is
adopted, otherwise it is rejected. If l is su-ciently large,
the error of the rst kind, i.e. the probability of rejecting
H when this hypothesis is true, is well approximated by
By appropriately choosing constants C1 and C2 , we get the
desired test accuracy.
Observe that the test described above provides only uni-directional
information. In fact, if the sample is rejected,
then we know that it is very unlikely that the hypothesis
actually holds. However, if the test passes, we can only
conclude that the sample does not violate H and this, in
general, is not su-cient to conclude that H actually holds.
To clarify this point, consider the following example. Suppose
that observations are a set of points taken from the
closed interval [0; 1], and assume that the hypothesis H is
that the points are uniformly and independently distributed
in that interval. Let  be the statistic that measures the
distance between the extreme points in the sample, and let
E[] be its expectation under the hypothesis H. Consider
now a sample
X in which a point is located at coordinate
0, another is located at coordinate E[], and the remaining
l 2 points are distributed uniformly and independently in
(0; E[]). Clearly, the sample passes the test, but hypothesis
H is violated. In order to circumvent this problem, more
than one statistic can be considered: if the sample passes all
the tests it is accepted, otherwise it is rejected. Returning to
the example above, if we also calculate the sum of the values
of the points, the sample
X will be probably rejected.
The discussion above indicates that the test accuracy can
be signicantly improved by considering dierent statistics
on the same sample, which must be adequately chosen given
the nature of the observations and the hypothesized distribution

In this paper, an observation consists of the positions of
the nodes of a mobile ad hoc network at an arbitrary instant
of time t. We assume that the network is composed
by n nodes, which move in a square region of unit area.
Hence, the observation taken at time t, also called snap-shot
at time t, can be formally dened as the set X
are the coordinates of the
point in [0; 1] 2 that represent the position of node i at time
t.
The statistical hypothesis H that we want to test is that
the points in X (t) are independently and uniformly distributed
in the deployment region [0; 1] 2 . To this purpose,
we will consider the following statistics on X (t):
1. the length of the longest nearest neighbor edge, dened
as
min
denotes the Euclidean distance
between points x i (t) and x j (t);
2. the length of the longest edge of the Euclidean minimum
spanning tree (MST) built on the points in X (t);
3. the total edge length of the MST on X (t);
4. the total edge length of the Voronoi diagram on X (t);
5. the total edge length of the Delaunay triangulation on
6. the number of empty cells.
A formal denition of Voronoi diagram and Delaunay triangulation
can be found in [8]. The empty cell statistic is obtained
by partitioning the deployment region into n square
cells of side 1
n that are arranged in a grid fashion, and by
counting the number of vacant cells.
The statistics above have been chosen since their limit
distributions are known, and since they are relevant parameters
in wireless ad hoc networks. In fact, the length of
the longest nearest neighbor edge is a lower bound to the
critical transmitting range 1 , while the length of the longest
edge in the MST is exactly the critical transmitting range
[6, 18]. The critical transmitting range in ad hoc networks
has been studied in [10, 20]. The total edge length of the
MST is closely related to the cost of the optimal transmitting
range assignment [13], while the Voronoi diagram and
Delaunay triangulation, or derivation of these graphs, are
used to construct spanners for power-e-cient routing [7],
and in the evaluation of sensor networks coverage and exposure
[15, 16]. Finally, a subdivision of the deployment
region into square cells is used, for instance, to implement
cooperative strategies aimed at extending network lifetime
[22].
The limit distributions of these statistics, under the assumption
that nodes are distributed uniformly and independently
at random in [0; 1] 2 , have been widely studied. In
particular, it has been shown that:
{ the longest nearest neighbor edge and the longest edge
of the MST have the same limit distribution, which is
double exponential. Denoting with NNL and LMST
the random variables corresponding to these statistics,
we have [6, 18]:
lim
r
r
1 The critical transmitting range is the minimum value r of
the transmitting range that ensures that the communication
graph obtained by connecting nodes at distance at most r
is strongly connected.
{ denoting by TMST the total edge length of the MST,
we have [2, 21]:
lim
where c is a constant, with 0:600822  c  0:707.
The value of c has been experimentally evaluated as
0:656. Although a formal proof does not exist,
there are many evidences that the limit distribution
of TMST is the normal distribution [21].
{ the limit distribution of the total edge length of the
Voronoi diagram and of the Delaunay triangulation is
the normal distribution [19].
{ the limit distribution of the number of empty cells is
the normal distribution of parameters
In the following sections, we will use these statistics to
test our hypothesis H.
3. THE MOBILITY MODELS
Two mobility models will be used in the following to test
the statistical hypothesis described in the previous section.
The rst model is the random waypoint model [12], which
is commonly used to evaluate the performance of routing
protocols in ad hoc networks. In this model, every node
chooses uniformly at random a destination in [0;
moves toward it with a velocity chosen uniformly at random
in the interval [vmin ; vmax ]. When it reaches the destination,
it remains stationary for a predened pause time tpause , and
then it starts moving again according to the same rule. We
have also included a further parameter in the model, namely
the probability pstat that a node remains stationary during
the entire simulation time. Hence, only (1 pstat)  n nodes
(on the average) will move. Introducing pstat in the model
accounts for those situations in which some nodes are not
able to move. For example, this could be the case when
sensors are spread from a moving vehicle, and some of them
remain entangled, say, in a bush or tree. This can also model
a situation where two types of nodes are used, one type that
is stationary and another type that is mobile.
It has been observed in [3] that nodes moving according to
the random waypoint model tend to concentrate in the center
of the deployment region. This phenomenon, called the
border eect, is due to the fact that when the starting and
ending point of the node's movement are chosen uniformly
at random in a bounded region, it is very likely that the trajectory
that connects them crosses the center of the region.
Depending on the intensity of the border eect, the node
spatial distribution generated by a mobile network could be
rejected by at least one of the statistical tests for uniformity
described above. As we will see in Section 5, the intensity
of the border eect is closely related to some parameters of
the random waypoint model and, for extreme values of these
parameters, causes the failure of the uniformity test for at
least one statistic.
The second mobility model considered in this paper resembles
the Brownian two-dimensional motion. Mobility is
modeled using parameters pstat , pmove and m. Parameter
pstat is dened as in the random waypoint model. Parameter
pmove is the probability that a node moves at a given
step. This parameter accounts for heterogeneous mobility
patterns, in which nodes may move at dierent times. In-
tuitively, the smaller is the value of pmove , the more heterogeneous
is the mobility pattern. However, values of pmove
close to 0 result in an almost stationary network. If a node
is moving at step i, its position in step uniformly
at random in the square of side 2m centered at the
current node location. Parameter m models, to a certain
extent, the velocity of the nodes: the larger m is, the more
likely it is that a node moves far away from its position in
the previous step.
Observe that, contrary to the case of the random way-point
model, in the Brownian-like motion it is possible that
a moving node close to the border chooses as its next position
a point which is outside the boundary of the deployment
region. To circumvent this problem, we need a so called border
rule [3], which denes what to do with these nodes. In
this situation, the node can be: 1. bounced back according
to some rule; 2. positioned at the point of intersection of
the boundary with the line connecting the current and the
desired next position; 3. wrapped around to the other side
of the region, which is considered as a torus; 4. \deleted",
and a new node is initialized according to the initial dis-
5. forced to choose another position, until the
chosen position is inside the boundaries of the deployment
region.
Depending on the choice of the border rule, non-uniformity
can be produced in the Brownian-like model also. For ex-
ample, the second rule described above places nodes exactly
on the boundary of the region with higher probability than
at other points. This is the reverse of the border eect discussed
so far, in which nodes are more likely to be near the
center of the region. In fact, the only two rules that do not
appear to favor one part of the region over another are the
torus rule and the one in which a node is eliminated when
it would cross the boundary and a new node is created in
its place. The latter rule does not have any basis in the real
world, so we do not consider it here. The torus rule would
seem to apply to the real world only in some very specic
applications and so we do not consider it either. There does
not appear to be a large dierence between the other models
and so we arbitrarily chose the last rule to implement in
our simulator. As we will see in Section 5, the intensity of
the border eect in the Brownian-like model when using this
border rule is very weak, and does not prevent the resulting
node spatial distribution from passing all the uniformity
tests.
4. THE SIMULATION MODEL
To test the uniformity of the node spatial distribution of
mobile ad hoc networks we have developed an ad hoc simu-
lator. The simulator takes as input the number n of nodes
to distribute, the number ]sim of simulations to run, the
number ]steps of mobility steps to perform for each simula-
tion, and the mobility model to use, along with its parame-
ters. Nodes are distributed uniformly and independently at
random in [0; moving according to the
specied mobility model. After ]steps of mobility, the statistics
used for the uniformity test are calculated. In order to
calculate the empty cell statistic, the deployment region is
divided into n square cells of side 1
and the number of
vacant cells is counted. For the sake of simplicity, in our
experiments we have always used perfect-square values for
namely 49, 100 and 900.
The simulator returns the average value and the standard
deviation over the ]sim runs for each of the six statistics
considered. These values are used to test the \uniformity" of
the node spatial distribution as described in Section 2. The
simulator also returns six output les containing all the ]sim
values of each statistic. These les are used for the single test
evaluation described in Section 5.1. Finally, the simulator
returns the occupancy le needed for the occupancy-based
analysis described in Section 5.3.
5. SIMULATION RESULTS
5.1 Evaluating the test accuracy
Before testing the uniformity of mobile networks, we have
performed preliminary simulations on stationary networks
(which are obtained by setting ]steps to 0).
The purpose of these simulations was to determine the
parameters (expected value and standard deviation) of the
limit distribution for the total edge length of the MST,
Voronoi diagram, and Delaunay triangulation. We recall
that, contrary to the case of the other statistics, the limit
distribution of the statistics above is known to be normal,
but the actual parameters are unknown. In order to be
accurate, we considered a very large sample of 100000 simu-
lations. The average value and standard deviation of these
statistics for networks of size n=49, n=100 and n=900 have
been determined. These values are used to derive the upper
and lower bounds for the corresponding statistical test as
described in Section 2.
Another goal of this set of preliminary simulations was to
evaluate the rate of convergence of the experimental distribution
obtained from a large sample of uniformly distributed
points to the limit distribution. In fact, if the rate of convergence
of the actual distribution to the limit distribution is
very low, the uniformity test could be inaccurate. In other
words, it could be the case that, for moderate values of n,
the test (which is based on the limit distribution) is not
passed even by a sample of uniformly distributed nodes.
In order to keep the simulation time reasonable and the
size of the output les manageable, we considered a network
of n=100 nodes and a sample of 10000 experiments. From
the data contained in each le, we generated a histogram
representing the experimental density of the statistic. For
the test to be accurate, this histogram should closely resemble
the theoretical density function, which is obtained by
the limit distribution 2 .
As shown in Figure 1, this is actually the case for the
MST, Voronoi diagram and Delaunay triangulation total
edge length statistic, and for the empty cell statistic, meaning
that the tests based on these parameters are very ac-
curate. On the contrary, the longest nearest neighbor edge
and, more notably, the longest MST edge statistic show sig-
nicant discrepancy between the experimental and the theoretical
distribution. As observed above, this is due to the
fact that the rate of convergence to the limit distribution is
very low. In the case of the longest nearest neighbor edge
statistic, the resemblance is anyway su-cient to ensure the
accuracy of the test: when the test is executed on small in-
2 In the case of the MST, Voronoi diagram, and Delaunay
triangulation total edge length statistic, we have used the
parameters calculated in the preliminary simulation.
30. 35. 40. 45.0.10.20.3
TotalDelaunaytriangulationsedgelength
TotalVoronoidiagramedgelength
14. 15. 16. 17. 18.0.40.8
5.5 6. 6.5 7. 7.5 8.1TotalMST edgelength
LongestMST edge
LongestNearestNeighboredge

Figure

1: Experimental vs. theoretical density of the six statistics considered.
stances (n=49) of uniformly distributed nodes, it is passed.
This is not the case of the longest MST edge statistic, for
which the test on uniformly distributed nodes is not passed
even for very large instances (n=900). Hence, the test based
on this statistic is inaccurate, and will not be considered in
the remainder of this paper.
5.2 The uniformity test
In the second set of simulations, we have performed the
uniformity test on networks of size n=49, n=100 and n=900
using the two mobility models with dierent parameters.
First, we considered the random waypoint model, setting
the mobility parameters as follows: tpause=0, vmin=0.001,
vmax=0.01, pstat=0. Then, we varied each of these parameters
separately (for the velocity, we considered only dierent
values of vmax ). 3 For each experiment, we ran 10000 simulations
with 1000 steps of mobility each, and we performed
all the statistical tests. The tests, all with a 95% accuracy,
were performed on the average value of the statistic of inter-
est, measured on the node distribution resulting at the end
of the 1000 mobility steps.
The results of these experiments, which are reported in

Tables

1, have shown a signicant eect of the pause time
on the test outcomes: a longer pause time results in a more
uniform node spatial distribution. A pause time of 200 steps
(over 1000 steps of mobility) is su-cient to render the node
spatial distribution indistinguishable from uniform, except
for the longest nearest neighbor edge statistic when n=900.
A similar, although less evident, eect on the node spatial
distribution is displayed by pstat . Conversely, the uniformity
of the node spatial distribution appears to be completely independent
of vmax . Indeed, this is due to the fact that in
our simulations we varied the velocity when tpause was set
to 0: in this scenario, varying the velocity has no eect on
the intensity of the border eect, which is responsible for
the non-uniformity of the distribution. However, vmax has
some in
uence on the uniformity when tpause is greater than
0: with an increased velocity, nodes arrive quickly at desti-
nation, where they rest for tpause steps; hence, the fraction
of moving nodes in the network (which is responsible for the
3 The unit of time is a \simulation step", and velocity is
expressed as normalized spatial unit over simulation step.
border eect) is reduced. Anyway, the in
uence of vmax on
the node spatial distribution is very limited [5].
Regarding the size of the network, small networks (n=49)
passed more uniformity tests than larger ones (n=100 and
n=900). As discussed in Section 2, this does not necessarily
imply that the node spatial distribution for small networks
is \more uniform" than for large ones. It could also be the
case that since the accuracy of the statistical test increases
with n, it succeeds in rejecting an \almost uniform" sample
only for large values of n.
A similar set of simulations was also performed using the
Brownian-like mobility model. The default values of the
mobility parameters were set to pmove = 0:7,
m=0.1. As in the case of the random waypoint simulations,
we varied each parameter separately and we performed the
ve statistical tests. In particular, we varied pmove from
0.7 to 1 in steps of 0.1, pstat from 0 to 0.5 in steps of 0.25,
and m from 0.01 to 0.1 in steps of 0.03. The experiments
produced the same positive test outcomes, i.e. all the statistical
tests were passed for each combination of the mobility
values considered. These results conrm the intuition that
the Brownian-like motion has a \more uniform" nature compared
to the random waypoint model.
The results of the statistical tests presented above give
only a qualitative analysis of the node spatial distribution
of mobile networks, and give no numerical estimate of how
close to the uniform distribution they actually are. In order
to better evaluate this aspect, we performed a further set of
simulations. We considered each statistic separately, and we
compared the theoretical probability density function (ob-
tained by the limit distribution) with the experimental density
obtained in dierent mobile network scenarios. Since
the resemblance of the experimental distribution with the
uniform distribution in the random waypoint model is not
always guaranteed, we focused our attention on this mobility
model. In particular, we simulated two mobile scenarios
for a network with n=100 nodes: one which is critical
from the uniformity's point of view (tpause=0, vmin=0.001,
vmax=0.01 and pstat=0), and the other for which all the uniformity
tests are passed (tpause=200, vmin=0.001, vmax=0.01,
pstat=0.3). As in the previous simulations, the size of the
sample was 10000, and the statistics were calculated at the
LongestNN TotalMST TotalVor TotalDel EmptyCells
pause 0 yes no no no no no yes yes no no no no yes yes no
100 yes yes no yes yes no yes yes no yes yes no yes yes no
200 yes yes no yes yes yes yes yes yes yes yes yes yes yes yes
300 yes yes no yes yes yes yes yes yes yes yes yes yes yes yes
no no no no no yes yes no no no no yes yes no
yes no no no no no yes yes no no no no yes yes no
yes no no no no no yes yes no no no no yes yes no
pstat 0 yes no no no no no yes yes no no no no yes yes no
0.3 yes no no yes no no yes yes no yes yes no yes yes no
yes yes no yes yes yes yes yes yes yes yes no yes yes yes

Table

1: Outcomes of the statistical tests on networks of size n=49, 100 and 900 with dierent mobility
parameters.
Theoretical
"Non-uniform"mobilescenario
"Uniform"mobilescenario
TotalMST edgelength
LongestNearestNeighboredge

Figure

2: Density functions of the longest nearest neighbor edge, total MST edge length, and number of
empty cells for the theoretical distribution, and for two dierent mobile scenarios.
end of the 1000 mobility steps.
The results of these simulations are reported in Figure
2. The graphics report three curves: the theoretical den-
sity, and the experimental density in the \non-uniform" and
\uniform" mobile scenarios. Due to the low rate of convergence
to the limit distribution, for the longest nearest neighbor
edge statistic we have reported, instead of the theoretical
density, the experimental density obtained from a very
large sample of uniformly distributed points. The graphics
for the total Voronoi diagram and Delaunay triangulation
edge length are not shown, since they are very similar to
that of the total MST edge length.
As it is seen, the density in the mobile \non-uniform" scenario
is similar in shape to the theoretical density, but it is
shifted and somewhat scaled with respect to the theoretical
curve. This seems to indicate that, also in presence of a
relevant border eect, the limit distribution of the statistics
considered is the same. However, the parameters of these
limit distributions (expected value and standard deviation)
are dierent.
This fact, at least for the total MST, Voronoi diagram,
and Delaunay triangulation edge length, and for the empty
cell statistic, is conrmed by the very close resemblance of
the experimental distribution to the normal distribution,
where the parameters of the latter distribution are the average
value and the standard deviation obtained by the experimental
data. An interesting open issue is characterizing
these parameters as a function of the mobility parameters.
As it is seen from Figure 2, the expected number of empty
cells is larger than in the uniform case (this easily follows
from the fact that nodes are concentrated in the center of
the deployment region), while the expected total MST edge
length (as well as the total Voronoi diagram and Delaunay
triangulation edge length) is smaller than in the uniform
case. This fact merits some discussion. The nodes' concentration
in the center of the deployment region caused by
the border eect tends, on one hand, to reduce the length
of the \inner" edges of the graph 4 . On the other hand,
the \outer" edges, i.e. those close to the boundary, tend
to be longer. The results of our simulations have shown
that, on the average, the overall length reduction of \inner"
edges outweighs the increment of the \outer" edges. A nal
observation regards the Voronoi diagram statistic, which is
calculated considering only the internal Voronoi edges, i.e.
those edges that do not intersect the boundary of the deployment
region. In this case, the dierence between the
theoretical and the \non-uniform" mobile density is signi-
cantly reduced.
The experimental density in the \uniform" mobile scenario
was always very similar to the theoretical (or, in the
case of the longest nearest neighbor statistic, to the experimental
density. In the case of the Voronoi diagram
statistic, the two densities were almost identical.
Altogether, the results presented in this subsection have
shown that, if the border eect is not too intense, the node
spatial distribution of a mobile network can be well approximated
by the uniform distribution. If the border eect is
very intense, the similarity with the uniform distribution
is no longer valid. However, the limit distributions of many
statistics of interest calculated on these networks remain the
same, although with dierent parameters.
5.3 Occupancy-based analysis
The results presented in the previous subsection have proved
that in the Brownian-like model and, for appropriate
values of the mobility parameters, in the random waypoint
model, the node spatial distribution resulting after a large
number of mobility steps is compatible with the uniform
4 With the word graph, we intend here either the MST, the
Voronoi diagram or the Delaunay triangulation.
distribution. Once more, we want to emphasize that this
does not mean that the distribution is uniform, but that,
from the point of view of the ve statistics considered, it
is indistinguishable from the uniform distribution. On the
other hand, it is known that in the random waypoint model
and, to a lesser extent, in the Brownian-like model, nodes
are subject to the border eect, which tends to concentrate
them in the center of the deployment region. In order to
better evaluate and \visualize" this phenomenon, we have
performed a last set of simulations.
As in the case of the empty cell test, we subdivided the
deployment region into n square cells of side 1
are
arranged in a grid fashion. Once the nodes are distributed
uniformly at random in the region, they move according to
the chosen mobility model for 1000 steps. At the end of the
mobility steps, the number of nodes in each cell is recorded.
Each experiment consisted of 10000 such simulations, and
the simulator reported the cumulative number of nodes in
each cell. If the node spatial distribution was uniform, this
number should be approximately 10000 in every cell (we
have n nodes to be distributed in n cells, hence the expected
number of nodes in a cell for each simulation is 1). However,
if the border eect occurs, cells in the center of the region
should record a larger number of nodes than boundary cells.
The outcomes of these simulations have been used to build
an \occupancy graphic", i.e. a three-dimensional graphic
that for each cell in the 2D-plane, reports the cumulative
number of nodes as its value in the third dimension. These
graphics allow us to \visualize" the border eect.
As in the case of the previous simulations, we considered
the two mobility models, and we assigned default values
(the same as in the previous subsection) to the mobility
parameters. Then, we varied each parameter separately, and
we built the occupancy graphic.
The occupancy graphics for the random waypoint model
with dierent settings of the mobility parameters have been
calculated (n was set to 100), and are reported in the full
version of the paper [5]. The central cross-cross section of
these graphics, reported in Figure 3, have shown that tpause
has a signicant eect on the intensity of the border ef-
fect: when tpause = 0, the average number of nodes (over
the 10000 simulations) in the corner cells is approximately
0.19, while in central cells this number is above 2, i.e. it is
more than ten times larger than in the corner cells. As the
pause time increases, the node spatial distribution becomes
more and more
at: when tpause = 300, the average number
of nodes in corner cells is approximately 0.76, while in the
central cells it is approximately 1.31, and the ratio between
these numbers is below 2. A similar behavior is displayed
for increasing values of pstat , while the eect of vmax on the
node spatial distribution is negligible.
We have also investigated whether the intensity of the
border eect is in
uenced by the size of the network or not.
To this purpose, we set tpause=200,
and 0:01, and we simulated networks of sizes n=49,
n=100 and n=900. The occupancy graphics obtained by
these simulations, which are reported in the full version of
the paper [5], have shown that the intensity of the border
eect seems to be virtually independent of the size of the
network. However, a slight increment of the intensity for
large networks is observed: while the ratio of the maximally
over the minimally occupied cell is 2.027 when n=49, it is
2.191 when n=100, and 2.399 when n=900.
Finally, we simulated the Brownian-like mobility model.
We considered networks of size n=100, we set the default
values of the mobility parameters as in Subsection 5.2, and
we varied each parameter separately. As expected, the node
spatial distribution was practically indistinguishable from
the uniform distribution for many combinations of the mobility
parameters. The only parameter that displayed some
in
uence on the node spatial distribution is m, whose increment
causes a moderate border eect. This is due to the fact
that, as m increases, nodes more and more distant from the
border may choose as next position a point which is outside
the boundaries of the deployment region. Hence, the \bias-
ing towards the center" caused by the border rule becomes
more and more intense. The occupancy graphics generated
for dierent values of m are reported in Figure 4. As it is
seen, the border eect is perceivable for m=0.05 and, more
clearly, for m=0.1. However, it seems to be very dierent in
nature from the border eect displayed by networks whose
nodes move according to the random waypoint model. In
fact, in the random waypoint nodes tend to be \smoothly"
concentrated in the center of the deployment region; i.e.,
the node density is low at the borders, it becomes larger
and larger as the cell is closer to the center, and is maximum
in the central cells. What is observed here, instead, is
a \sharp" and \localized" border eect: the node density is
very low in boundaries cells, but it is practically uniform in
the rest of the deployment area.
As a nal comment, it should be observed that, while
the \smooth" border eect generated by the random way-point
model renders the node spatial distribution remarkably
dierent from the uniform distribution (we recall that
when tpause=0 many statistical tests are not passed), this is
not the case of the \sharp" border eect generated by the
Brownian-like motion, for which the resulting node spatial
distribution is always indistinguishable from uniform.
6. CONCLUSIONS
In this paper we have investigated the node spatial distribution
generated by a wireless ad hoc network whose nodes
move for a large number of steps. In particular, we have
tested whether this distribution can be approximated by the
uniform distribution or not.
The results of the extensive simulations presented in this
paper have shown that the truth of this hypothesis depends
on the mobility model adopted: if we consider a Brownian-
like motion, the hypothesis holds, except for a slight and
\sharp" border eect; conversely, in the random waypoint
model the hypothesis holds only when the border eect is
not too intense. The intensity of the border eect depends
on the pause time and, to a lesser extent, on pstat , while it
is only marginally in
uenced by the velocity of the nodes.
For most typical settings of the mobility parameter (e.g.,
200), the uniformity assumption holds, at least as
far as the ve statistics considered in this paper are consid-
ered. As a side eect, the results presented in this paper
have indicated that the limit distribution of these statistics
are the same as those resulting from a uniform node distri-
bution, except for the values of their parameters (expected
value and standard deviation).
We believe that the results presented in this paper are a
further step in understanding the fundamental properties of
a mobile ad hoc network. As further directions of research
that this work has originated, we mention considering the
t_p=0
t_p=100
t_p=200
t_p=3000,51,52,5
P_s=0.3

Figure

3: Central cross-section of the occupancy graphics for the random waypoint model with dierent
values of the mobility parameters.4826100.51.5261048012
Figure

4: Occupancy graphics for the Brownian-like mobility model with dierent values of m.
impact of dierent initial node distributions (besides the
uniform distribution considered in this paper) on the nal
spatial distribution, and considering group mobility models.
Another very interesting direction of research is trying to
formally characterize the spatial distribution generated by
the mobility models considered in this paper.
7.



--R








Handbook of Discrete and Computational Geometry














--TR
Handbook of discrete and computational geometry
Analytical comparison of local and end-to-end error recovery in reactive routing protocols for mobile ad hoc networks
Power consumption in packet radio networks
Smooth is better than sharp
Capacity of Ad Hoc wireless networks
Geography-informed energy conservation for Ad Hoc routing
Performance of multipath routing for on-demand protocols in mobile ad hoc networks
Geometric spanner for routing in mobile networks
Localized algorithms in wireless ad-hoc networks
A probabilistic analysis for the range assignment problem in ad hoc networks
Investigating upper bounds on network lifetime extension for cell-based energy conservation techniques in stationary ad hoc networks
On the Symmetric Range Assignment Problem in Wireless Ad Hoc Networks

--CTR
Markus Borschbach, Improving ad hoc connectivity, Proceedings of the 9th WSEAS International Conference on Communications, p.1-5, July 14-16, 2005, Athens, Greece
mobility modeling;mobile ad hoc networks;random waypoint model;node spatial distribution