Geometrically aware communication in random wireless networks

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.

REFERENCES

• 1: I. F. Akyildiz, W. Su, Y. Sankarasubramaniam, and E. Cayirci. A survey on sensor networks. IEEE Communications Magazine, 40(8):102--114, 2002.
• 2: D. J. Baker and A. Ephremides. The architectural organization of a mobile radio network via a distributed algorithm. IEEE Transactions on Communications, COM-29(11):1694--1701, November 1981.
• 3: M. W. Bern, D. Eppstein, and F. Yao. The expected extremes in a delaunay triangulation. International Journal of Computatinal Geometry and Applications, 1(1):79--91, 1991.
• 4: Prosenjit Bose , Pat Morin, Online Routing in Triangulations, Proceedings of the 10th International Symposium on Algorithms and Computation, p.113-122, December 16-18, 1999
• 5: Prosenjit Bose , Pat Morin , Ivan Stojmenović , Jorge Urrutia, Routing with guaranteed delivery in ad hoc wireless networks, Wireless Networks, v.7 n.6, p.609-616, November 2001 [doi>10.1023/A:1012319418150]
• 6: J. Chang and L. Tassiulas. Routing for maximum system lifetime in wireless ad-hoc networks. In Proceedings of 37-th Annual Allerton Conference on Communication, Control, and Computing, Monticello, IL, September 1999.
• 7: J.-H. Chang and L. Tassiulas. Energy conserving routing in wireless ad-hoc networks. In Proc. of IEEE INFOCOM 2000, pages 22--31, 2000.
• 8: Carla-Fabiana Chiasserini , Imrich Chlamtac , Paolo Monti , Antonio Nucci, Energy Efficient Design of Wireless Ad Hoc Networks, Proceedings of the Second International IFIP-TC6 Networking Conference on Networking Technologies, Services, and Protocols; Performance of Computer and Communication Networks; and Mobile and Wireless Communications, p.376-386, May 19-24, 2002
• 9: Mark de Berg , Marc van Kreveld , Mark Overmars , Otfried Schwarzkopf, Computational geometry: algorithms and applications, Springer-Verlag New York, Inc., Secaucus, NJ, 1997
• 10: K. A. Delin and S. P. Jackson. Sensor web for in situ exploration of gaseous biosignatures, 2000.
• 11: A. Ephremides, J. E. Wieselthier, and D. J. Baker. A design concept for reliable mobile radio networks with frequency hopping signaling. In Proceedings of the IEEE, volume 75, pages 56--73, January 1987.
• 12: Deborah Estrin , Ramesh Govindan , John Heidemann , Satish Kumar, Next century challenges: scalable coordination in sensor networks, Proceedings of the 5th annual ACM/IEEE international conference on Mobile computing and networking, p.263-270, August 15-19, 1999, Seattle, Washington, United States [doi>10.1145/313451.313556]
• 13: R. G. Gallager , P. A. Humblet , P. M. Spira, A Distributed Algorithm for Minimum-Weight Spanning Trees, ACM Transactions on Programming Languages and Systems (TOPLAS), v.5 n.1, p.66-77, Jan. 1983 [doi>10.1145/357195.357200]
• 14: D. Ganesan, B. Krishnamachari, A. Woo, D. Culler, D. Estrin, and S. Wicker. Complex behavior at scale: An experimental study of low-power wireless sensor networks. Technical Report CSD-TR 02-0013, UCLA, 2002.
• 15: Jie Gao , Leonidas J. Guibas , John Hershberger , Li Zhang , An Zhu, Geometric spanner for routing in mobile networks, Proceedings of the 2nd ACM international symposium on Mobile ad hoc networking & computing, October 04-05, 2001, Long Beach, CA, USA [doi>10.1145/501422.501424]
• 16: E. N. Gilbert and H. O. Pollak. Steiner random minimal trees. SIAM J. Appl. Math., 16:1--29, 1968.
• 17: Wendi Rabiner Heinzelman , Joanna Kulik , Hari Balakrishnan, Adaptive protocols for information dissemination in wireless sensor networks, Proceedings of the 5th annual ACM/IEEE international conference on Mobile computing and networking, p.174-185, August 15-19, 1999, Seattle, Washington, United States [doi>10.1145/313451.313529]
• 18: Wendi Rabiner Heinzelman , Anantha Chandrakasan , Hari Balakrishnan, Energy-Efficient Communication Protocol for Wireless Microsensor Networks, Proceedings of the 33rd Hawaii International Conference on System Sciences-Volume 8, p.8020, January 04-07, 2000
• 19: J. M. Kahn , R. H. Katz , K. S. J. Pister, Next century challenges: mobile networking for “Smart Dust”, Proceedings of the 5th annual ACM/IEEE international conference on Mobile computing and networking, p.271-278, August 15-19, 1999, Seattle, Washington, United States [doi>10.1145/313451.313558]
• 20: K. Kar, M. Kodialam, T. V. Lakshman, and L. Tassiulas. Routing for network capacity maximization in energy-constrained ad-hoc networks. In Proc. of IEEE INFOCOM 2003, Apr. 2003.
• 21: Menelaos I. Karavelas , Leonidas J. Guibas, Static and kinetic geometric spanners with applications, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.168-176, January 07-09, 2001, Washington, D.C., United States
• 22: Brad Karp , H. T. Kung, GPSR: greedy perimeter stateless routing for wireless networks, Proceedings of the 6th annual international conference on Mobile computing and networking, p.243-254, August 06-11, 2000, Boston, Massachusetts, United States [doi>10.1145/345910.345953]
• 23: G. Kozma, Z. Lotker, and G. Stupp. The minimal spanning tree and the upper box dimension. ArXiv Mathematics e-prints, Nov. 2003.
• 24: E. Kranakis, H. Singh, and J. Urrutia. Compass routing on geometric networks. In Proc. 11 th Canadian Conference on Computational Geometry, pages 51--54, Vancouver, August 1999.
• 25: Fabian Kuhn , Roger Wattenhofer , Yan Zhang , Aaron Zollinger, Geometric ad-hoc routing: of theory and practice, Proceedings of the twenty-second annual symposium on Principles of distributed computing, p.63-72, July 13-16, 2003, Boston, Massachusetts [doi>10.1145/872035.872044]
• 26: Fabian Kuhn , Roger Wattenhofer , Aaron Zollinger, Asymptotically optimal geometric mobile ad-hoc routing, Proceedings of the 6th international workshop on Discrete algorithms and methods for mobile computing and communications, September 28-28, 2002, Atlanta, Georgia, USA [doi>10.1145/570810.570814]
• 27: Fabian Kuhn , Roger Wattenhofer , Aaron Zollinger, Worst-Case optimal and average-case efficient geometric ad-hoc routing, Proceedings of the 4th ACM international symposium on Mobile ad hoc networking & computing, June 01-03, 2003, Annapolis, Maryland, USA [doi>10.1145/778415.778447]
• 28: L. Li and J. Halpern. Minimum energy mobile wireless networks revisited. In Proc. IEEE International Conference on Communications (ICC), June 2001.
• 29: R. Meester and R. Roy. Continuum percolation. Cambridge University Press, 1996.
• 30: Atsuyuki Okabe , Barry Boots , Kokichi Sugihara, Spatial tessellations: concepts and applications of Voronoi diagrams, John Wiley & Sons, Inc., New York, NY, 1992
• 31: G. J. Pottie , W. J. Kaiser, Wireless integrated network sensors, Communications of the ACM, v.43 n.5, p.51-58, May 2000 [doi>10.1145/332833.332838]
• 32: A. R'enyi and R. Sulanke. Uber die konvexe hulle von n zufallig gewahlten punkten. Z. Wahrscheinlichkeitstheorie, 2:75--84, 1963.
• 33: R. Shah and J. Rabaey. Energy aware routing for low energy ad hoc sensor networks. In Proc. IEEE Wireless Communications and Networking Conference (WCNC), Orlando, FL, March 2002.
• 34: Suresh Singh , Mike Woo , C. S. Raghavendra, Power-aware routing in mobile ad hoc networks, Proceedings of the 4th annual ACM/IEEE international conference on Mobile computing and networking, p.181-190, October 25-30, 1998, Dallas, Texas, United States [doi>10.1145/288235.288286]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Geometrical problems and computations

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.2 Network Protocols
          Subjects: Routing protocols

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Network problems

General Terms:
Algorithms, Performance, Theory

Keywords:
delaunay triangulation, geometric flooding, geometric routing