<<

. 38
( 87 .)



>>

For simplicity, we assume that the wireless devices are distributed in a unit-area square
(or disk) according to some distribution function, e.g., uniform distribution or Poisson
process. A point set process is said to be a random uniform point process, denoted by Xn,
in a unit-area square C = [“0.5, 0.5] — [“0.5, 0.5] if it consists of n independent points each
of which is uniformly and randomly distributed over C.
The standard probabilistic model of a homogeneous Poisson process with density n,
denoted by Pn, is characterized by the property that the number of nodes in a region is a
random variable depending only on the area (or volume in higher dimensions) of the re-
gion. In other words,
193
6.4 STOCHASTIC GEOMETRY


The probability that there are exactly k nodes appearing in any region of area A is
[(n/A)k/k] · e“nA.
For any region , the conditional distribution of nodes in given that exactly k
nodes in the region is joint uniform.

Hereafter, we assume that the movement of wireless devices still keeps them in the
same distribution (uniform or Poisson process). Gupta and Kumar [72] showed that there
is almost surely a critical power at which the wireless nodes are randomly and uniformly
distributed in a unit area disk. The result by Penrose [71] implies the same conclusion.
Moreover, Penrose [71] gave the probability of the network to be connected if the trans-
mission radius is set as a positive real number r and n goes to infinity.
The theoretical value of the transmission ranges gives us insight into how to set the
transmission radius to achieve the k-connectivity with a certain probability. These results
also apply to mobile networks in which the moving of wireless nodes always generates
randomly (or Poisson process) distributed node positions. They also have applications in
system design of large scale wireless networks. For example, for setting up a sensor net-
work monitoring a certain region, we should deploy how many sensors in order to have a
multiple connected network, knowing that each sensor can transmit a range r0? Notice
that most results hold only when the number of wireless devices n goes to infinity, which
is difficult to deploy practically. Li et al. [73] conducted extensive simulations to study the
transmission radius achieving k-connectivity with certain probability for practical set-
tings.
Let G(V, r) be the graph defined on V with edges uv E if and only if ||uv|| r. Here
||uv|| is the Euclidean distance between nodes u and v. Let G(Xn, rn) be the set of graphs
G(V, rn) for n nodes V that are uniformly and independently distributed in a two-dimen-
sional unit-area disk D with center at the origin. The problem considered by Gupta and
Kumar [72] is then to determine the value of rn such that a random graph in G(Xn, rn) is as-
ymptotically connected with probability one as n goes to infinity. Let Pk(Xn, rn) be the
probability that a graph in G(Xn, rn) is k-connected.
Fault tolerance is one of the central challenges in designing wireless ad hoc networks.
To make fault tolerance possible, first of all, the underlying network topology must have
multiple disjoint paths to connect any two given wireless devices. Here, the path could be
vertex disjoint or edge disjoint. Considering the communication nature of the wireless
networks, the vertex disjoint multiple paths are often used in the literature. Here, we are
interested in what is the condition of rn such that the underlying network topology G(V,
rn) is k-connected almost surely when V is uniformly and randomly distributed over a two-
dimensional domain . A graph is called k-vertex connected (k-connected for simplicity)
if, for each pair of vertices, there are k mutually vertex disjoint paths (except end-vertices)
connecting them. Equivalently, a graph is k-connected if there is no set of k “ 1 nodes
whose removal will partition the network into at least two components. Thus, a k-connect-
ed wireless network can sustain the failure of k “ 1 nodes.
The vertex connectivity, denoted by (G), of a graph G is the maximum k such that G is
k-vertex connected. The edge connectivity, denoted by (G), of a graph G is the maximum
k such that G is k-edge connected. The minimum degree of a graph G is denoted by (G)
and the maximum degree of a graph G is denoted by (G). Clearly, for any graph G, (G)
(G) (G) (G).
A graph property is called monotone increasing if G has such a property and all graphs
on the same vertex set containing G as a subgraph have this property. Let Q be any monot-
194 TOPOLOGY CONTROL IN WIRELESS AD HOC NETWORKS


Probability of k-connected when n =100
1


0.9


0.8


0.7


0.6
Probability




0.5


0.4


0.3 k=1
k=2
k=3
k=4
0.2


0.1


0
0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9
scaled transmission radius

n = 100



Probability of k-connected when n = 200
1


0.9


0.8


0.7


0.6
Probability




0.5


0.4


0.3 k=1
k=2
k=3
k=4
0.2


0.1


0
0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9
scaled transmission radius

n = 200

Figure 6.7. Transition phenomena of graph G(V, r) being k-connected.
195
6.4 STOCHASTIC GEOMETRY


Probability of k-connected when n = 300
1


0.9


0.8


0.7


0.6
Probability




0.5


0.4


0.3 k=1
k=2
k=3
k=4
0.2


0.1


0
0 0.1 0.2 0.3 0.4 0.5 0.6 0.7
scaled transmission radius

n = 300



Probability of k-connected when n = 400
1


0.9


0.8


0.7


0.6
Probability




0.5


0.4


0.3 k=1
k=2
k=3
k=4
0.2


0.1


0
0 0.1 0.2 0.3 0.4 0.5 0.6 0.7
scaled transmission radius

n = 400

Figure 6.7. Continued.
196 TOPOLOGY CONTROL IN WIRELESS AD HOC NETWORKS


one increasing property of graphs, for example, the connectivity, the k-edge connectivity,
the k-vertex connectivity, the minimum node degree at least k, and so on. The hitting ra-
dius (V, Q) is the infimum of all r such that graph G(V, r) has property Q. For example,
(V, k) is the minimum radius r such that G(V, r) is at least k-vertex connected; (V,
k) is the minimum radius r at which the graph G(V, r) has the minimum degree k. Obvi-
ously, for any V,

(V, k) (V, k)

Penrose [74] showed that these two hitting radii are asymptotically the same for n points V
randomly and uniformly distributed in a unit square and n goes infinity.
The connectivity of random graphs, especially the geometric graphs and their variations,
have been considered in the random graph theory literature [75], in the stochastic geometry
literature [71, 74, 76“78], and the wireless ad hoc network literature [72, 79“86].
Let us first consider the connectivity problem. Given n nodes V randomly and indepen-
dently distributed in a unit-area disk D, Gupta and Kumar [72] showed that G(V, rn) is
connected almost surely if n · r 2 ln n + c(n) for any c(n) with c(n) as n goes in-
n
finity. Notice that this bound is tight, as they also proved that G(Xn, rn) is asymptotically
disconnected with positive probability if n · r 2 = ln n + c(n) and lim supn c(n) < + . No-
n
tice that they actually derived their results for a homogeneous Poisson process of points in
D instead of the independent and uniform point process. They showed that the difference
between them is negligible. Penrose [71] showed that the same result holds if the geome-
try domain in which the wireless nodes are distributed is a unit-area square C instead of
the unit-area disk D.
Independently, Penrose [71] showed that the longest edge Mn of the minimum spanning
tree of n points randomly and uniformly distributed in a unit area square C satisfies

<<

. 38
( 87 .)



>>