Geometrically aware communication in random wireless networks
Authors:
Open Access
- 25 July 2004
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 310-319
Abstract
Some of the first routing algorithms for position-aware wireless networks used the Delaunay triangulation of the point-locations of the network's nodes as the underlying connectivity graph. Later on these solutions were considered impractical because the Delaunay triangulation may in general contain arbitrarily long edges and because calculating the Delaunay triangulation may require a global view of the network. Many other algorithms were then suggested for geometric routing, often assuming random placement of network nodes for analysis or simulation [27, 5, 28, 15]. But as we show, when the nodes are uniformly placed in the unit disk the Delaunay triangulation does not contain long edges, it is easy to compute locally and it is in many ways optimal for geometric routing and flooding.In particular, we prove that with high probability the maximal length of an edge in Del(P), the Delaunay triangulation of a set P of n nodes uniformly placed in the unit disk, is O(3√3log novern), and that the expected sum of squares of all the edges in Del(P) is O(1). These geometric results imply that for wireless networks, randomly distributed in a unit disk (1) computing the Delaunay triangulation locally is asymptotically easy; (2) simple "face routing" through the Delaunay triangulation optimizes, up to poly-logarithmic factors, the energy load on the nodes, and (3) flooding the network, an operation quite common in sensor nets, is with high probability optimal up to a constant factor. The last property is particularly important for geocasting because the Delaunay triangulation is known to be a spanner.Keywords
This publication has 22 references indexed in Scilit:
- A survey on sensor networksIEEE Communications Magazine, 2002
- Geometric spanner for routing in mobile networks2001
- GPSR2000
- Wireless integrated network sensorsCommunications of the ACM, 2000
- Next century challenges1999
- Adaptive protocols for information dissemination in wireless sensor networks1999
- Power-aware routing in mobile ad hoc networks1998
- THE EXPECTED EXTREMES IN A DELAUNAY TRIANGULATIONInternational Journal of Computational Geometry & Applications, 1991
- Steiner Minimal TreesSIAM Journal on Applied Mathematics, 1968
- ber die konvexe H lle von n zuf llig gew hlten PunktenProbability Theory and Related Fields, 1963