An efficient organization mechanism for spatial networks

Spatial networks, also known as random geometric graphs, are random graphs with certain distance metric, in which each node is connected to some others within its neighborhood disc. Due to the rapid increase of network scales, the design of spatial networks becomes increasingly challenging. Inspired by the recently discovered small-world topology in relational networks, we identify an efficient organization mechanism for spatial networks, which we believe is useful for spatial network design. Two types of discs are introduced. Edges in the large discs are counterparts of "shortcuts." We find that such "two-radius" spatial networks exhibit small characteristic path length, yet with low cost. This mechanism is applied to broadcasting protocol design for wireless ad hoc/sensor networks. (c) 2005 Elsevier B.V. All rights reserved.