Techniques for maintaining connectivity in wireless ad-hoc networks under energy constraints

ABSTRACT

Distributed wireless systems (DWSs) are emerging as the enabler for next-generation wireless applications. There is a consensus that DWS-based applications, such as pervasive computing, sensor networks, wireless information networks, and speech and data communication networks, will form the backbone of the next technological revolution. Simultaneously, with great economic, industrial, consumer, and scientific potential, DWSs pose numerous technical challenges. Among them, two are widely considered as crucial: autonomous localized operation and minimization of energy consumption. We address the fundamental problem of how to maximize the lifetime of the network using only local information, while preserving network connectivity. We start by introducing the care-free sleep (CS) Theorem that provides provably optimal conditions for a node to go into sleep mode while ensuring that global connectivity is not affected. The CS theorem is the basis for an efficient localized algorithm that decides which nodes will go to into sleep mode and for how long. We have also developed mechanisms for collecting neighborhood information and for the coordination of distributed energy minimization protocols. The effectiveness of the approach is demonstrated using a comprehensive study of the performance of the algorithm over a wide range of network parameters. Another important highlight is the first mathematical and Monte Carlo analysis that establishes the importance of considering nodes within a small number of hops in order to preserve energy.

REFERENCES

• 1: Josh Broch , David A. Maltz , David B. Johnson , Yih-Chun Hu , Jorjeta Jetcheva, A performance comparison of multi-hop wireless ad hoc network routing protocols, Proceedings of the 4th annual ACM/IEEE international conference on Mobile computing and networking, p.85-97, October 25-30, 1998, Dallas, Texas, United States [doi>10.1145/288235.288256]
• 2: Cerpa, A. and Estrin, D. 2002. Ascent: Adaptive self-configuring sensor networks topologies. In IEEE Infocom. vol. 3. 1278--1287.
• 3: Alberto Cerpa , Jennifer L. Wong , Louane Kuang , Miodrag Potkonjak , Deborah Estrin, Statistical model of lossy links in wireless sensor networks, Proceedings of the 4th international symposium on Information processing in sensor networks, April 24-27, 2005, Los Angeles, California
• 4: Alberto Cerpa , Jennifer L. Wong , Miodrag Potkonjak , Deborah Estrin, Temporal properties of low power wireless links: modeling and implications on multi-hop routing, Proceedings of the 6th ACM international symposium on Mobile ad hoc networking and computing, May 25-27, 2005, Urbana-Champaign, IL, USA [doi>10.1145/1062689.1062741]
• 5: Chandrakasan, A., Sheng, S., and Brodersen, R. 1992. Low-power cmos digital design. IEEE Journal of Solid-State Circuits (JSSC) 27, 4, 473--484.
• 6: Chandrakasan, A., Potkonjak, M., Mehra, R., Rabaey, J., and Brodersen, R. 1995. Optimizing power using transformations. IEEE Transactions on CAD 14, 1, 12--31.
• 7: Benjie Chen , Kyle Jamieson , Hari Balakrishnan , Robert Morris, Span: an energy-efficient coordination algorithm for topology maintenance in ad hoc wireless networks, Wireless Networks, v.8 n.5, p.481-494, September 2002 [doi>10.1023/A:1016542229220]
• 8: Fei Dai , Jie Wu, On Constructing k-Connected k-Dominating Set in Wireless Networks, Proceedings of the 19th IEEE International Parallel and Distributed Processing Symposium (IPDPS'05) - Papers, p.81.1, April 04-08, 2005 [doi>10.1109/IPDPS.2005.302]
• 9: Edsger W. Dijkstra, The structure of the “THE”-multiprogramming system, Communications of the ACM, v.11 n.5, p.341-346, May 1968 [doi>10.1145/363095.363143]
• 10: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 11: A. Ghosh , S. Devadas , K. Keutzer , J. White, Estimation of average switching activity in combinational and sequential circuits, Proceedings of the 29th ACM/IEEE conference on Design automation, p.253-259, June 08-12, 1992, Anaheim, California, United States
• 12: Haber, S. 1970. Numerical evaluation of multiple integrals. SIAM Review 12, 481--526.
• 13: Han, B., Fu, H., Lin, L., and Jia, W. 2004. Efficient construction of connected dominating set in wireless ad hoc networks. In IEEE International Conference on Mobile Ad-hoc and Sensor Systems. 570--572.
• 14: Hong, I., Kirovski, D., Qu, G., Potkonjak, M., and Srivastava, M. 1999. Power optimization of variable voltage core-based systems. IEEE Transaction on CAD 18, 12, 1702--1714.
• 15: Kasten, O. 2001. Measurements of energy consumption for digitan 2 mbps wireless lan module (ieee 802.11/2mbps). http://www.inf.ethz.ch/~kasten/research.
• 16: F. Koushanfar , A. Davare , D. T. Nguyen , M. Potkonjak , A. Sangiovanni-Vincentelli, Low power coordination in wireless ad-hoc networks, Proceedings of the 2003 international symposium on Low power electronics and design, August 25-27, 2003, Seoul, Korea [doi>10.1145/871506.871623]
• 17: Leighton, F. 1979. A graph coloring algorithm for large scheduling problems. Journal of Research of the National Bureau of Standards 84, 489--506.
• 18: Enrico Macii , Massoud Pedram , Fabio Somenzi, High-level power modeling, estimation, and optimization, Proceedings of the 34th annual conference on Design automation, p.504-511, June 09-13, 1997, Anaheim, California, United States [doi>10.1145/266021.266268]
• 19: Mosteller, F. 1965. Fifty Challenging Problems in Probability With Solutions. Addison-Wesley, Reading, MA.
• 20: Reuven Y. Rubinstein, Simulation and the Monte Carlo Method, John Wiley & Sons, Inc., New York, NY, 1981
• 21: Curt Schurgers , Vlasios Tsiatsis , Saurabh Ganeriwal , Mani Srivastava, Topology management for sensor networks: exploiting latency and density, Proceedings of the 3rd ACM international symposium on Mobile ad hoc networking & computing, June 09-11, 2002, Lausanne, Switzerland [doi>10.1145/513800.513817]
• 22: Silberschatz, A., Galvin, P., and Gagne, G. 2003. Operating system concepts: Windows xp update.
• 23: Tajana Simunic , Luca Benini , Andrea Acquaviva , Peter Glynn , Giovanni De Micheli, Dynamic voltage scaling and power management for portable systems, Proceedings of the 38th conference on Design automation, p.524-529, June 2001, Las Vegas, Nevada, United States [doi>10.1145/378239.379016]
• 24: Ivan Stojmenovic , Mahtab Seddigh , Jovisa Zunic, Dominating Sets and Neighbor Elimination-Based Broadcasting Algorithms in Wireless Networks, IEEE Transactions on Parallel and Distributed Systems, v.13 n.1, p.14-25, January 2002 [doi>10.1109/71.980024]
• 25: WolframResearch. 2001. Mathematica 4.1, symbolic programming. http://www.wolfram.com/products/mathematica/index.html.
• 26: Jie Wu , Hailan Li, On calculating connected dominating set for efficient routing in ad hoc wireless networks, Proceedings of the 3rd international workshop on Discrete algorithms and methods for mobile computing and communications, p.7-14, August 20-20, 1999, Seattle, Washington, United States [doi>10.1145/313239.313261]
• 27: Ya Xu , John Heidemann , Deborah Estrin, Geography-informed energy conservation for Ad Hoc routing, Proceedings of the 7th annual international conference on Mobile computing and networking, p.70-84, July 2001, Rome, Italy [doi>10.1145/381677.381685]
• 28: F. Yao , A. Demers , S. Shenker, A scheduling model for reduced CPU energy, Proceedings of the 36th Annual Symposium on Foundations of Computer Science (FOCS'95), p.374, October 23-25, 1995
• 29: Zheng, R. and Kravets, R. 2005. On-demand power management for ad hoc networks. Ad Hoc Networks 3, 1, 51--68.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.3 SPECIAL-PURPOSE AND APPLICATION-BASED SYSTEMS

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.3 Network Operations

  D. Software
  D.4 OPERATING SYSTEMS
      D.4.4 Communications Management
      D.4.7 Organization and Design

General Terms:
Performance, Reliability

Keywords:
Low power, ad-hoc networks, connectivity, energy management, power management, sleeping coordination