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

ISBN-10 0-470-09453-2

**Download**(direct link)

**:**

**39**> 40 41 42 43 44 45 .. 122 >> Next

Theorem 6.2.1 Assume n nodes are distributed uniformly at random in the disk of unit area. Let r„ (f) = for some constant f, and let pa (respectively, pi)be the minimum

transmitting range such that graph A(n, pA, p) (respectively, I(n, pI, p))is connected. Then,

lim P{pa < rnif)) = exp(-pe(-?)),

n^TO

lim P(pi < rn(f)) = exp(-e(-?)).

Corollary 6.2.2 Assume n nodes are distributed uniformly at random in the disk of unit area, and assume that nodes are active with constant, independent probability p, with 0 < p < 1. The CTR for connectivity of A(n, rn, p) and of I(n, rn, p) is the same and equals

/log« + f{n)

'BN = ,/----------------.

y npn

where f(n) is an arbitrary function such that lim„^TO f(n) = +to.

68

OTHER CHARACTERIZATIONS OF THE CTR

Comparing the expressions of the CTR without and with Bernoulli nodes (corollaries 4.1.2 - which holds also when nodes are distributed in the disk of unit area - and 6.2.2), the only difference is in the additional multiplicative term p at the denominator of rBN. In other words, the expression of the CTR for connectivity with Bernoulli nodes is the same as in the traditional model, with n replaced by pn (expected number of active nodes).

To conclude this section, we give a numeric example. Suppose 1000 nodes are uniformly distributed in the unit disk. Assume we want to create a connected network with probability

0.99. Let us first consider the traditional point graph model. The value of the constant j3 in Theorem 4.1.1 such that exp(-e~^) = 0.99 is approximately 4.6. With this value of j3, we get a value of the transmitting range equal to 0.060523. Assume now that nodes are active with probability p = 0.5. In order to have probability 0.99 that A(1000, r, 0.5) is connected, we must set r to 0.0829867, which is an approximately 37% increase with respect to the case of always active nodes. In order to have the same probability that 7(1000, r, 0.5) is connected, we must set r to 0.0855924, which is an approximately 41% increase with respect to the case of always active nodes.

6.3 The Critical Coverage Range

The Critical Coverage Range (CCR) problem is defined as follows:

Definition 6.3.1 (Critical coverage range) Assume n nodes are deployed into a certain region R. A point x in region R is said to be covered if it is at a distance of, at most, r from at least one of the network nodes, where r is the nodes’ covering range. We say that region R is covered if all of its points are covered. The CCR problem is to find, given a node deployment, the minimum value of r such that R is covered.

Similar to the CTR problem, the CCR problem can be easily solved if nodes’ positions are known. Furthermore, it can be formulated also in the reverse way, that is: assume a certain region R must be covered using nodes with sensing range r; which is the minimum number n of nodes to be deployed in order to cover R?

The study of the CCR problems stated above finds its motivation in the context of wireless sensor networks used for monitoring applications, such as surveillance or habitat monitoring. In the design of this type of networks, it is often assumed that every node (sensor) can ‘sense’ an event within a certain maximum range (the coverage range), and the typical requirement is that the monitored region is covered. Since sensor nodes in this context are typically randomly deployed (for instance, using a moving vehicle such as airplane), the CCR is studied under the assumption of random node deployment.

The reader would have noticed the strong similarities between the CTR and the CCR problem. Indeed, it is easy to prove that a node deployment that covers R under the assumption that nodes have coverage range rc also generates a connected communication graph under the assumption that nodes have transmitting range rt > 2rc (see Figure 6.4). This is formally stated in the theorem below, which has been proven in (Wang et al. 2003).

Theorem 6.3.2 (Wang et al. 2003) Assume that a set S of n nodes with coverage range rc and transmitting range rt > 2rt are deployed in a certain region R and that the nodes in S cover R. Then, the communication graph generated by nodes in S is connected.

OTHER CHARACTERIZATIONS OF THE CTR

69

Figure 6.4 Relation between the coverage range (rc) and the transmitting range (rt): setting rt = 2rc, the covering ranges of two nodes overlap if and only if they are in each other transmitting range.

Note that the reverse of the theorem above does not hold. This is depicted in Figure 6.5: the communication graph formed by the nodes in S is connected, but the region R is not covered. This example shows that coverage is, in general, a stronger requirement than connectivity, even when rt > 2rc: a set of nodes that is concentrated in a subregion of R can be connected, but it does not satisfy coverage (Figure 6.5).

The critical coverage range has been investigated in (Philips et al. 1989) for the case of nodes distributed in a square with side of length l according to a Poisson process of fixed density X.

**39**> 40 41 42 43 44 45 .. 122 >> Next