Distributed Construction of the Critical Geometric Graph in Dense Wireless Sensor Networks

Wireless sensor networks are often modeled in terms of a dense deployment of smart sensor nodes in a two-dimensional region. Given a node deployment, the Critical Geometric Graph (CGG) over these locations (i.e., the connected Geometric Graph (GG) with the smallest radius) is a useful structure since it provides the most accurate proportionality between hop-count and Euclidean distance. Hence, it can be used for GPS-free node localisation as well as minimum distance packet forwarding. It is also known to be asymptotically optimal for network transport capacity and power efficiency.