On the -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 -coverage is found for wireless networks modeled as points uniformly distributed in a unit square, with every node connecting to its nearest neighbors. A network is called -covered if every node, except those near the boundary, can find one of its nearest neighbors in any sector of angle . For all , if , it is shown that the probability of -coverage goes to one as goes to infinity, for any ; on the other hand, if , the probability of -coverage goes to zero. This sharp characterization of -coverage is used to show, via further geometric arguments, that the network will be connected with probability approaching one if . Connections between these results and the performance analysis of wireless networks, especially for routing and topology control algorithms, are discussed. Digital Object Identifier 10.1109/TIT.2006.874384