# Topologi control in wireles ad hoc and sensor network - Santi P.

ISBN-10 0-470-09453-2

**Download**(direct link)

**:**

**115**> 116 117 118 119 120 121 .. 122 >> Next

For an exhaustive treatment of the theory of GRG, the reader is referred to (Penrose

2003).

B.3 Occupancy Theory

Another applied probability theory that has been successfully used in the analysis of fundamental ad hoc/sensor network properties is the occupancy theory (Kolchin et al. 1978).

In the occupancy theory, it is typically assumed that n balls are thrown independently at random into C urns (or cells), where a ball has the same probability of landing in any cell (equiprobable allocation). Variables C and n are interdependent: commonly, it is assumed that the number C of cells is the independent variable, and n is expressed as a function of C.

Given this setting, the asymptotic distribution of several random variables of interest for

C, n(C) ^ to has been characterized. Among the studied random variables, we cite

- the number of empty cells after all balls have been thrown;

- the number of trials before at least k urns are filled with at least one ball;

238

ELEMENTS OF APPLIED PROBABILITY

- the number of balls in the minimally and in the maximally occupied cell after all balls have been thrown.

Several results have also been extended to the case of nonequiprobable allocation of balls into cells.

The occupancy theory has been used in the context of wireless ad hoc/sensor networks to characterize the critical transmitting range for connectivity (Santi and Blough 2002, 2003), to derive bounds to the network lifetime (Blough and Santi 2002), and to study clustering algorithm properties (Younis and Fahmy 2004; Younis et al. 2004).

Since the usefulness of occupancy theory in the characterization of ad hoc network properties is not self-evident, we briefly explain how the asymptotic characterization of the number of empty cells has been used to provide sufficient conditions for a.a.s. connectivity of the communication graph.

Assume n nodes are deployed in a certain two-dimensional region R. Suppose R is subdivided into C equal-sized cells, and assume nodes have the same transmitting range r. If we further assume that nodes are distributed uniformly at random in R, the problem of determining the minimum number of nodes to be deployed in order to generate a connected communication graph w.h.p. can be stated as an occupancy problem, provided the cell size is appropriately chosen.

Consider the cell lattice reported in Figure B.1. It is simple to see that, with this definition of the cell side, having at least one node in every cell is a sufficient condition for generating a connected communication graph. Hence, a sufficient condition for connectivity can be

< >

r/V(5)

Figure B.l Cell lattice used to derive a sufficient condition for asymptotic connectivity. The nodes have transmitting range r, and the cell side is set to r / s/5. With this definition of the cell side, having at least one node in each cell is a sufficient condition for connectivity of the communication graph.

ELEMENTS OF APPLIED PROBABILITY

239

derived by using results from the occupancy theory that determine the asymptotic distribution of number of empty cells. In particular, we have to study the conditions under which this number equals 0, a.a.s. This technique has been used in (Santi and Blough 2002, 2003).

B.4 Continuum Percolation

A third applied probability that proved useful in the analysis of ad hoc/sensor network properties is the theory of continuum percolation (Meester and Roy 1996).

In the theory of continuum percolation, nodes are distributed in the plane according to a Poisson process of intensity X > 0. In other words, it is assumed that, given any region A of R2 of area a, the probability of having k nodes in A equals

_Xa (Xa)k

P(A contains k nodes) = e ------------- for k = 0, 1, 2.......

k!

Once the nodes are deployed, a disk of a certain radius R is centered at each node, and a graph is formed by connecting any two nodes whose disks intersect (see Figure B.2). In the most general model, the radius Ru of the disk centered at node u is a random variable with a certain distribution f (e.g. uniform distribution in [0, rmax]), and the random variables Rx modeling the disk radii at the different nodes are assumed to be independent with the same distribution f. In a simpler version of the model, all the disks have the same radius equal to r > 0.

Given this setting, researchers have studied the connectivity of the generated graph. In particular, it has been proven that for each X > 0 there exists at most one infinite-order connected component in the graph (a.a.s.). However, the existence of an infinite-order component alone is not sufficient to ensure the connectivity of the generated graph.

y t'—--.

(a)

Figure B.2 Model used in the continuum percolation theory: nodes are deployed according to a two-dimensional Poisson process of intensity X > 0, and a disk is drawn for each node (a); then, a graph is generated by connecting two nodes if and only if their disks intersect (b).

240

ELEMENTS OF APPLIED PROBABILITY

**115**> 116 117 118 119 120 121 .. 122 >> Next