ñòð. 38 |

(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 |