We study the problem of power-efficient routing for multihop wireless ad hoc sensor networks. The guiding insight of our work is that unlike an ad hoc wireless network, a wireless ad hoc sensor network does not require full connectivity among the nodes. As long as the sensing region is well covered by connected nodes, the network can perform its task. We consider two kinds of geometric random graphs as base interconnection structures: unit disk graphs @math and @math -nearest-neighbor graphs @math built on points generated by a Poisson point process of density @math in @math . We provide subgraph constructions for these two models @math and @math and show that there are values @math and @math above which these constructions have the following good properties: (i) they are sparse; (ii) they are power-efficient in the sense that the graph distance is no more than a constant times the Euclidean distance between any pair of points; (iii) they cover the space well; (iv) the subgraphs can be set up easily using local information at each node. We also describe a simple local algorithm for routing packets on these subgraphs. Our constructions also give new upper bounds for the critical values of the parameters @math and @math for the models @math and @math .
@cite_15: Let P be a realization of a homogeneous Poisson point process in ℝd with density 1. We prove that there exists a constant kd, 1<kd<∞, such that the k-nearest neighborhood graph of P has an infinite connected component with probability 1 when k≥kd. In particular, we prove that k2≤213. Our analysis establishes and exploits a close connection between the k-nearest neighborhood graphs of a Poisson point set and classical percolation theory. We give simulation results which suggest k2=3. We also obtain similar results for finite random point sets.
@cite_14: Consider a Poisson process X in Rd with density 1. We connect each point of X to its k nearest neighbors by undirected edges. The number k is the parameter in this model. We show that, for k = 1, no percolation occurs in any dimension, while, for k = 2, percolation occurs when the dimension is sufficiently large. We also show that if percolation occurs, then there is exactly one infinite cluster. Another percolation model is obtained by putting balls of radius zero around each point of X and let the radii grow linearly in time until they hit another ball. We show that this model exists and that there is no percolation in the limiting configuration. Finally we discuss some general properties of percolation models where balls placed at Poisson points are not allowed to overlap (but are allowed to be tangent). 0 1996 John Wiley & Sons, Inc.
The @math model was introduced by H "aggstr "om and Meester @cite_14 . They showed that there was a finite critical value, @math for all @math such that an infinite cluster exists in this model. They proved that the infinite cluster was unique and that there was a value @math such that @math for all @math . Teng and Yao gave an upper bound of 213 for @math @cite_15 .