Localized algorithms for energy efficient topology in wireless ad hoc networks

ABSTRACT

We propose several novel localized algorithms to construct energy efficient routing structures for homogeneous wireless ad hoc networks, where all nodes have same maximum transmission ranges. Our first structure has the following attractive properties: (1) It is energy efficient: given any two nodes u and v, there is a path connecting them in the structure with total energy cost at most ρ = 1/1-(2sin π/k)^β times of the energy cost of any path connecting them in original communication graph; (2) Its node degree is bounded from above by a positive constant k+5 where k>6 is an adjustable parameter; (3) It is a planar structure, which enables several localized routing algorithms; (4) It can be constructed and maintained locally and dynamically. Moreover, by assuming that the node ID and its position can be represented in O(log n) bits each for a wireless network of n nodes, we show that the structure can be constructed using at most 24n messages, where each message is O(log n) bits. Our second method improves the degree bound to k, relaxes the theoretical power spanning ratio to ρ = √2 ^β/1 -(2√2sinπ/k)^β, where k›8 is an adjustable parameter, and keeps all other properties. We show that the second structure can be constructed using at most 3n messages, where each message has size of O(log n) bit.We also experimentally evaluate the performance of these new energy efficient network topologies. The theoretical results are corroborated by the simulations: these structures are more efficient in practice, compared with other known structures used in wireless ad hoc networks and are easier to construct. In addition, the power assignment based on our new structures shows low energy cost and small interference at each wireless node.

REFERENCES

• 1: Matthias Grünewald , Tamás Lukovszki , Christian Schindelhauer , Klaus Volbert, Distributed Maintenance of Resource Efficient Wireless Network Topologies (Distinguished Paper), Proceedings of the 8th International Euro-Par Conference on Parallel Processing, p.935-946, August 27-30, 2002
• 2: Li Li , Joseph Y. Halpern , Paramvir Bahl , Yi-Min Wang , Roger Wattenhofer, Analysis of a cone-based distributed topology control algorithm for wireless multi-hop networks, Proceedings of the twentieth annual ACM symposium on Principles of distributed computing, p.264-273, August 2001, Newport, Rhode Island, United States [doi>10.1145/383962.384043]
• 3: Xiang-Yang Li, Peng-Jun Wan, and Yu Wang, "Power efficient and sparse spanner for wireless ad hoc networks," in IEEE Int. Conf. on Computer Communications and Networks(ICCCN01), 2001, pp. 564--567.
• 4: X.-Y. Li , P.-J. Wan , Y. Wang , O. Frieder, Sparse Power Efficient Topology for Wireless Networks, Proceedings of the 35th Annual Hawaii International Conference on System Sciences (HICSS'02)-Volume 9, p.296.2, January 07-10, 2002
• 5: Rajmohan Rajaraman, Topology control and routing in ad hoc networks: a survey, ACM SIGACT News, v.33 n.2, June 2002 [doi>10.1145/564585.564602]
• 6: R. Ramanathan and R. Rosales-Hain, "Topology control of multihop wireless networks using transmit power adjustment," in IEEE INFOCOM, 2000.
• 7: Yu Wang, Xiang-Yang Li, and Ophir Frieder, "Distributed spanner with bounded degree for wireless networks," International Journal of Foundations of Computer Science, Vol. 14, no. 2, pp. 183-200, 2003.
• 8: Roger Wattenhofer, Li Li, Paramvir Bahl, and Yi-Min Wang, "Distributed topology control for wireless multihop ad-hoc networks," in IEEE INFOCOM'01, 2001.
• 9: 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]
• 10: 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]
• 11: 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]
• 12: 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]
• 13: Yu Wang , Xiang-Yang Li, Localized construction of bounded degree and planar spanner for wireless ad hoc networks, Proceedings of the 2003 joint workshop on Foundations of mobile computing, p.59-68, September 19, 2003, San Diego, CA, USA [doi>10.1145/941079.941088]
• 14: Xiang-Yang Li, G. Calinescu, and Peng-Jun Wan, "Distributed construction of planar spanner and routing for ad hoc wireless networks," in 21st Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM), 2002, vol. 3.
• 15: A. C.-C. Yao, "On constructing minimum spanning trees in k-dimensional spaces and related problems," SIAM J. Computing, vol. 11, pp. 721--736, 1982.
• 16: L. Kleinrock and J. Silvester, "Optimum transmission radii for packet radio networks or why six isa magic number," in Proceedings of the IEEE National Telecommunications Conference, 1978, pp. 431--435.
• 17: Godfried T. Toussaint, "The relative neighborhood graph of a finite planar set," Pattern Recognition, vol. 12, no. 4, pp. 261--268, 1980.
• 18: K.R. Gabriel and R.R. Sokal, "A new statistical approach to geographic variation analysis," Systematic Zoology, vol. 18, pp. 259--278, 1969.
• 19: Tamas Lukovszki, New Results on Geometric Spanners and Their Applications, Ph.D. thesis, University of Paderborn, 1999.
• 20: J. Mark Keil , Carl A. Gutwin, Classes of graphs which approximate the complete Euclidean graph, Discrete & Computational Geometry, v.7 n.1, p.13-28, 1992 [doi>10.1007/BF02187821]
• 21: Prosenjit Bose , Luc Devroye , William S. Evans , David G. Kirkpatrick, On the Spanning Ratio of Gabriel Graphs and beta-skeletons, Proceedings of the 5th Latin American Symposium on Theoretical Informatics, p.479-493, April 03-06, 2002
• 22: WeiZhao Wang, Xiang-Yang Li, Kousha Moaveninejad, Yu Wang, and Wen-Zhan Song, "The spanning ratios of $beta$-skeleton," in Canadian Conference on Computational Geometry (CCCG), 2003, Accepted for publication.
• 23: 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]
• 24: Prosenjit Bose , Joachim Gudmundsson , Michiel H. M. Smid, Constructing Plane Spanners of Bounded Degree and Low Weight, Proceedings of the 10th Annual European Symposium on Algorithms, p.234-246, September 17-21, 2002
• 25: David P. Dobkin , Steven J. Friedman , Kenneth J. Supowit, Delaunay graphs are almost as good as complete graphs, Discrete & Computational Geometry, v.5 n.4, p.399-407, Jul. 1990 [doi>10.1007/BF02187801]
• 26: J. Mark Keil , Carl A. Gutwin, The Delauney Triangulation Closely Approximates the Complete Euclidean Graph, Proceedings of the Workshop on Algorithms and Data Structures, p.47-56, August 17-19, 1989
• 27: Gruia Cv alinescu, "Computing 2-hop neighborhoods in ad hoc wireless networks," AD-HOC Networks and Wireless (AdHoc-Now), 2003.
• 28: Peng-Jun Wan Xiang-Yang Li Gruia Calinescu and Yu Wang, "Localized delaunay triangulation with application in wireless ad hoc networks," IEEE Transaction on Parallel and Distributed Processing, 2003, Accepted for publication. Short version appeared at IEEE INFOCOM 2002.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Graph algorithms

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Network topology; Wireless communication

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

General Terms:
Algorithms, Design, Theory

Keywords:
bounded degree, planar, spanner, topology control, wireless ad hoc networks