A unified energy-efficient topology for unicast and broadcast

ABSTRACT

We propose a novel communication efficient topology control algorithm for each wireless node to select communication neighbors and adjust its transmission power, such that all nodes together self-form a topology that is energy efficient simultaneously for both unicast and broadcast communications. We prove that the proposed topology is planar, which guarantees packet delivery if a certain localized routing method is used; it is power efficient for unicast-- the energy needed to connect any pair of nodes is within a small constant factor of the minimum under a common power attenuation model; it is efficient for broadcast: the energy consumption for broadcasting data on top of it is asymptotically the best compared with structures constructed locally; it has a constant bounded logical degree, which will potentially reduce interference and signal contention. We further prove that the average physical degree of all nodes is bounded by a small constant. To the best of our knowledge, this is the first communication-efficient distributed algorithm to achieve all these properties. Previously, only a centralized algorithm was reported in [3]. Moreover, by assuming that the ID and position of every node can be represented in O(log n) bits for a wireless network of n nodes, our method uses at most 13n messages, where each message is of O(log n) bits. We also show that this structure can be efficiently updated for dynamical network environment. Our theoretical results are corroborated in the simulations.

REFERENCES

• 1: I.F. Akyildiz, W. Su, Y. Sankarasubramaniam, and E.Cayirci. A survey on sensor networks. IEEE Communications Magazine, 40(8):102--114, August 2002.
• 2: Prosenjit Bose , Pat Morin , Ivan Stojmenović , Jorge Urrutia, Routing with guaranteed delivery in ad hoc wireless networks, Proceedings of the 3rd international workshop on Discrete algorithms and methods for mobile computing and communications, p.48-55, August 20-20, 1999, Seattle, Washington, United States [doi>10.1145/313239.313282]
• 3: 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
• 4: 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
• 5: Martin Burkhart , Pascal von Rickenbach , Roger Wattenhofer , Aaron Zollinger, Does topology control reduce interference?, Proceedings of the 5th ACM international symposium on Mobile ad hoc networking and computing, May 24-26, 2004, Roppongi Hills, Tokyo, Japan [doi>10.1145/989459.989462]
• 6: Gruia Calinescu. Computing 2-hop neighborhoods in ad hoc wireless networks, 2003. AD-HOC NetwOrks and Wireless Conference.
• 7: J. Cartigny, D. Simplot, and I. Stojmenovic. Localized minimum-energy broadcasting in ad-hoc networks. In IEEE INFOCOM, 2003.
• 8: Cheng, X., Thaeler, A., Xue, G., and Chen, D., TPS: A time-based positioning scheme for outdoor wireless sensor networks. In IEEE INFOCOM. 2004.
• 9: Andrea E. F. Clementi , Pierluigi Crescenzi , Paolo Penna , Gianluca Rossi , Paola Vocca, On the Complexity of Computing Minimum Energy Consumption Broadcast Subgraphs, Proceedings of the 18th Annual Symposium on Theoretical Aspects of Computer Science, p.121-131, February 15-17, 2001
• 10: Gautam Das , Giri Narasimhan , Jeffrey Salowe, A new way to weigh Malnourished Euclidean graphs, Proceedings of the sixth annual ACM-SIAM symposium on Discrete algorithms, p.215-222, January 22-24, 1995, San Francisco, California, United States
• 11: 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]
• 12: Michele Flammini , Alfredo Navarra , Ralf Klasing , Stéphane Pérennes, Improved approximation results for the minimum energy broadcasting problem, Proceedings of the 2004 joint workshop on Foundations of mobile computing, October 01-01, 2004, Philadelphia, PA, USA [doi>10.1145/1022630.1022644]
• 13: K.R. Gabriel and R.R. Sokal. A new statistical approach to geographic variation analysis. Systematic Zoology, 18:259--278, 1969.
• 14: 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]
• 15: Lingxuan Hu , David Evans, Localization for mobile sensor networks, Proceedings of the 10th annual international conference on Mobile computing and networking, September 26-October 01, 2004, Philadelphia, PA, USA [doi>10.1145/1023720.1023726]
• 16: Chalermek Intanagonwiwat , Ramesh Govindan , Deborah Estrin , John Heidemann , Fabio Silva, Directed diffusion for wireless sensor networking, IEEE/ACM Transactions on Networking (TON), v.11 n.1, p.2-16, February 2003 [doi>10.1109/TNET.2002.808417]
• 17: D. B. Johnson, D. A. Maltz, Y.-C. Hu, and J. G. Jetcheva. The dynamic source routing protocol for mobile ad hoc networks. IETF Internet Draft, November 2001. draft-ietf-manet-dsr-06.txt.
• 18: 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]
• 19: 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]
• 20: 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
• 21: Lefteris M. Kirousis , Evangelos Kranakis , Danny Krizanc , Andrzej Pelc, Power consumption in packet radio networks, Theoretical Computer Science, v.243 n.1-2, p.289-305, July 28, 2000 [doi>10.1016/S0304-3975(98)00223-0]
• 22: L. Kleinrock and J. Silvester. Optimum transmission radii for packet radio networks or why six is a magic number. In Proceedings of the IEEE National Telecommunications Conference, pages 431--435, 1978.
• 23: Fabian Kuhn , Thomas Moscibroda , Roger Wattenhofer, What cannot be computed locally!, Proceedings of the twenty-third annual ACM symposium on Principles of distributed computing, July 25-28, 2004, St. John's, Newfoundland, Canada [doi>10.1145/1011767.1011811]
• 24: 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]
• 25: 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]
• 26: Ning Li , Jennifer C. Hou, FLSS: a fault-tolerant topology control algorithm for wireless networks, Proceedings of the 10th annual international conference on Mobile computing and networking, September 26-October 01, 2004, Philadelphia, PA, USA [doi>10.1145/1023720.1023747]
• 27: Xiang-Yang Li, G. Calinescu, Peng-Jun Wan, and Yu Wang Localized Delaunay Triangulation with Applications in Wireless Ad Hoc Networks, IEEE Transactions on Parallel and Distributed Systems. October 2003 (Vol. 14, No. 10), pages 1035--1047.
• 28: Xiang-Yang Li , Peng-Jun Wan , Yu Wang , Chih-Wei Yi, Fault tolerant deployment and topology control in wireless ad hoc networks: Research Articles, Wireless Communications & Mobile Computing, v.4 n.1, p.109-125, February 2004 [doi>10.1002/wcm.v4:1]
• 29: 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]
• 30: Xiang-Yang Li. Approximate mst for UDG locally. In COCOON, 2003.
• 31: 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
• 32: Xiang-Yang Li, Yu~Wang, Wen-Zhan Song, Peng-Jun Wan, and Ophir Frieder. Localized minimum spanning tree and its applications in wireless ad hoc networks. In IEEE INFOCOM, 2004.
• 33: Weifa Liang, Constructing minimum-energy broadcast trees in wireless ad hoc networks, Proceedings of the 3rd ACM international symposium on Mobile ad hoc networking & computing, June 09-11, 2002, Lausanne, Switzerland [doi>10.1145/513800.513815]
• 34: Moni Naor , Larry Stockmeyer, What can be computed locally?, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.184-193, May 16-18, 1993, San Diego, California, United States [doi>10.1145/167088.167149]
• 35: Dragos Niculescu and Badri Nath. Ad hoc positioning system (APS). In IEEE GLOBECOM (1), pages 2926--2931, 2001.
• 36: V. Park and M. S. Corson. Temporally-ordered routing algorithm (tora) version 1 specification. IETF Internet Draft, November 2000. draft-ietf-manet-tora-spec-03.txt.
• 37: Mathew Penrose. The longest edge of the random minimal spanning tree. Annals of Applied Probability, 7:340--361, 1997.
• 38: C. E. Perkins, E. M. Belding-Royer, and S. Das. Ad hoc on demand distance vector (AODV) routing. IETF Internet Draft, March 2002. draft-ietf-manet-aodv-10.txt.
• 39: Charles E. Perkins , Pravin Bhagwat, Highly dynamic Destination-Sequenced Distance-Vector routing (DSDV) for mobile computers, ACM SIGCOMM Computer Communication Review, v.24 n.4, p.234-244, Oct. 1994
• 40: Mahtab Seddigh , Julio Solano González , Ivan Stojmenovic, RNG and internal node based broadcasting algorithms for wireless one-to-one networks, ACM SIGMOBILE Mobile Computing and Communications Review, v.5 n.2, p.37-44, April 2001 [doi>10.1145/584066.584069]
• 41: R. C. Shah and J. M. Rabaey. Energy aware routing for low energy ad hoc sensor networks. In IEEE Wireless Communication and Networking Conference (WCNC) 2002, pages 350--355, March 2002.
• 42: Wen-Zhan Song , Yu Wang , Xiang-Yang Li , Ophir Frieder, Localized algorithms for energy efficient topology in wireless ad hoc networks, Proceedings of the 5th ACM international symposium on Mobile ad hoc networking and computing, May 24-26, 2004, Roppongi Hills, Tokyo, Japan [doi>10.1145/989459.989473]
• 43: Godfried T. Toussaint. The relative neighborhood graph of a finite planar set. Pattern Recognition, 12(4):261--268, 1980.
• 44: Peng-Jun Wan, G. Calinescu, Xiang-Yang Li, and Ophir Frieder. Minimum-energy broadcast routing in static ad hoc wireless networks. In IEEE Infocom, 2001.
• 45: P. J. Wan , G. Călinescu , X. Y. Li , O. Frieder, Minimum-energy broadcasting in static ad hoc wireless networks, Wireless Networks, v.8 n.6, p.607-617, November 2002 [doi>10.1023/A:1020381720601]
• 46: Yu Wang and Xiang-Yang Li. Efficient construction of bounded degree and planar spanner for wireless networks. In ACM DIALM-POMC Workshop, 2003.
• 47: L. Orecchia , A. Panconesi , C. Petrioli , A. Vitaletti, Localized techniques for broadcasting in wireless sensor networks, Proceedings of the 2004 joint workshop on Foundations of mobile computing, October 01-01, 2004, Philadelphia, PA, USA [doi>10.1145/1022630.1022638]
• 48: 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.
• 49: J. Wieselthier, G. Nguyen, and A. Ephremides. On the construction of energy-efficient broadcast and multicast trees in wireless networks. In Proc. IEEE INFOCOM 2000, pages 586--594, 2000.
• 50: Jie Wu , Fei Dai, A Generic Broadcast Protocol in Ad Hoc Networks Based on Self-Pruning, Proceedings of the 17th International Symposium on Parallel and Distributed Processing, p.29.1, April 22-26, 2003
• 51: A. C.-C. Yao. On constructing minimum spanning trees in k-dimensional spaces and related problems. SIAM Journal of Computing, 11:721--736, 1982.
• 52: Fan Ye , Haiyun Luo , Jerry Cheng , Songwu Lu , Lixia Zhang, A two-tier data dissemination model for large-scale wireless sensor networks, Proceedings of the 8th annual international conference on Mobile computing and networking, September 23-28, 2002, Atlanta, Georgia, USA [doi>10.1145/570645.570664]

INDEX TERMS

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

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

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

General Terms:
Algorithms, Design, Theory

Keywords:
broadcast, graph theory, interference, low weight, power efficient, topology control, unicast, wireless ad hoc networks