On the theta-coverage and connectivity of large random networks
Wireless planar networks have been used to model wireless networks in a tradition that dates back to 1961 to the work of E. N. Gilbert. Indeed, the study of connected components in wireless networks was the motivation for his pioneering work that spawned the modern field of continuum percolation theory. Given that node locations in wireless networks are not known, random planar modeling can be used to provide preliminary assessments of important quantities such as range, number of neighbors, power consumption, and connectivity, and issues such as spatial reuse and capacity. In this paper, the problem of connectivity based on nearest neighbors is addressed. The exact threshold function for theta-coverage is found for wireless networks modeled as n points uniformly distributed in a unit square, with every node connecting to its 0, nearest neighbors. A network is called theta-covered if every node, except those near the boundary, can find one of its On nearest neighbors in any sector of angle theta. For all theta is an element of (0, 2 pi), if phi n = (1 + delta) log 2 pi/2 pi-0 n, it is shown that the probability of theta-coverage goes to one as goes to infinity, for any delta > 0; on the other hand, if phi(n) = (1 - delta) log 2 pi/2 pi-0 n, the probability of theta-coverage goes to zero. This sharp characterization of theta-coverage is used to show, via further geometric arguments, that the network will be connected with probability approaching one if phi(n) = (1 + delta.) log(2) n. Connections between these results and the performance analysis of wireless networks, especially for routing and topology control algorithms, are discussed.
connectivity wireless networks topology control ad hoc networks coverage random geometric graphs sensor networks transmission power control