Download (direct link):
Corollary 12.1.9 Assume that n nodes are placed uniformly at random in [0, 1]2, and let G- be the symmetric subgraph of the k-neighbors graph built on these nodes. The CNN for connectivity is
kc = c log n,
for some constant c with c\ < c < c2.
The upper bound on the CNN of G- (and, hence, the same bound for G+) has been recently improved by Wan and Yi in (Wan and Yi 2004) to j3e log n, where e « 2.718 is the natural base and j3 is an arbitrary constant greater than 1. Indeed, the authors proved an even stronger result, showing that the same condition on the number of neighbors is sufficient for ensuring h-connectivity w.h.p., where h is an arbitrary constant with h > 1.
Another extension to Xue and Kumar’s Theorem has been presented in (Blough et al. 2003a), generalizing the result to square deployment regions of arbitrary side. In fact, Theorem 12.1.7 holds under the assumption that the deployment region is fixed (it is the unit square), and the number of nodes grows to infinity. In other words, it can be applied only to dense ad hoc networks, where the number of nodes per unit area is quite large. Blough et al. showed that the same result holds for sparse networks also, and for arbitrary network densities in general. This generalization is important since it formally proves that it is only the number n of nodes in the network, and not the area on which the network is deployed, that determines the CNN.
The minimum number of neighbors needed for connectivity has been investigated in a more practical setting also. In particular, Blough et al. in (Blough et al. 2003b) and in (Blough et al. 2003a) evaluated the CNN by means of extensive simulation. In the simulation
NEIGHBOR-BASED TOPOLOGY CONTROL
Table 12.1 Critical neighbor number for different values of n. kasym is the CNN for the Gk graph and ksym is the same number for the symmetric subgraph of Gk. Here, the CNN is defined as the minimum value of k that guarantees that the generated topology is connected with probability at least 0.95
n kasym ksym n kasym ksym
10 6 6 100 9 9
20 8 8 250 9 9
25 8 8 500 9 9
50 8 9 750 9 10
75 9 9 1000 10 10
setting, the CNN is defined as the minimum value of k that guarantees that the generated topology is connected with probability at least 0.95. Blough et al. considered both the Gk graph and its symmetric subgraph G-. Note that the CNN in case of G- might be higher than that of Gk because the asymmetric link removal might disconnect the graph (see Figures 12.1 and 12.2). The asymmetric CNN, kasym, and the symmetric CNN, ksym, for different values of n are reported in Table 12.1.
As seen from the table, setting k — 9 provides connectivity w.h.p. for a wide range of network sizes (from 50 to 500 nodes). Another important observation concerns the fact that kasym and ksym have the same value, except for a few cases in which
ksym — kasym + 1.
This fact confirms that, as predicted by Corollaries 12.1.8 and 12.1.9, removing all the asymmetric links has asymptotically negligible influence on network connectivity.
To gain more insights on neighbor-based connectivity, Blough et al. have also performed a set of simulations in which the connectivity requirement on G- is weakened. In particular, it is requested that at least 95% of the network nodes are in the same connected component w.h.p. (here, w.h.p. means with probability at least 0.95). We call the minimum value of k satisfying the above connectivity requirement wCNN, where w stands for weak.
The results of this experimental evaluation, which are reported in Table 12.2, are interesting: contrary to the case of CNN, wCNN shows a converging behavior as n increases; in particular, wCNN converges to 6 as n ^-<x>.
It is interesting to compare the different values of the minimum number of neighbors for connectivity that we have characterized in this section: depending on the connectivity requirement on Gk, this value can be equal to n - 1 (worst-case connectivity), or to 0(log n) (connectivity w.h.p.), or to 6 (most of the nodes in the largest connected component w.h.p.). Note that in this latter case we do have a magic number of neighbors, which is 6.
Before ending this section, we give one more comment about the values of wCNN and CNN reported in Table 12.2. These values indicate quite clearly (although there is no theoretical support to this claim) that the giant component phenomenon, which we have discussed in Section 4.1 in case of the CTR for connectivity, occurs in the k-neighbors graph also. In the context of neighbor-based topology control, the giant component phenomenon
NEIGHBOR-BASED TOPOLOGY CONTROL
Table 12.2 WeakCNN and CNN for different values of n. Here, wCNN is defined as the minimum value of k such that at least 95% of the network nodes are in the same connected component with probability at least 0.95
n wCNN CNN n wCNN CNN
10 6 6 100 7 9
20 7 8 250 7 9
25 7 8 500 6 9
50 7 9 750 6 10
75 7 9 1000 6 10
can be explained as follows. Assume every node in the network establishes a connection to its closest neighbor, then to the second closest neighbor, and so on, until connectivity is achieved. The experimental results reported in Table 12.2 indicate that a large connected component in Gk is formed quite soon in this closest-neighbor-connection process: w.h.p., most of the network nodes are in the same connected component after only six steps (i.e. when k = 6), independent of n; on the other hand, if the goal is connecting all the nodes in the network, then the connection process is very likely to stop after ^(log n) steps.