Asynchronous wakeup for ad hoc networks

ABSTRACT

Due to the slow advancement of battery technology, power management in wireless networks remains to be a critical issue. Asynchronous wakeup has the merits of not requiring global clock synchronization and being resilient to network dynamics. This paper presents a systematic approach to designing and implementing asynchronous wakeup mechanisms in ad hoc networks. The optimal wakeup schedule design can be formulated as a block design problem in combinatorics. We propose a neighbor discovery and schedule bookkeeping protocol that can operate on the optimal wakeup schedule derived. Two power management policies, i.e. slot-based power management and on-demand power management, are studied to overlay desirable communication schedule over the wakeup schedule mandated by the asynchronous wakeup mechanism. Simulation studies indicate that the proposed asynchronous wakeup protocol is quite effective under various traffic characteristics and loads: energy saving can be as high as 70%, while the packet delivery ratio is comparable to that without power management.

REFERENCES

• 1: Part 11: Wireless lan medium access control (mac) and physical layer (phy) specifications. ANSI/IEEE Std 802.11, 1999 Edition.
• 2: I. Anderson. Combinatorial Designs and Tournaments, chapter 2. Oxford University Press, 1998.
• 3: Mario Ζagalj , Jean-Pierre Hubaux , Christian Enz, Minimum-energy broadcast in all-wireless networks:: NP-completeness and distribution issues, Proceedings of the 8th annual international conference on Mobile computing and networking, September 23-28, 2002, Atlanta, Georgia, USA [doi>10.1145/570645.570667]
• 4: Benjie Chen , Kyle Jamieson , Hari Balakrishnan , Robert Morris, Span: An energy-efficient coordination algorithm for topology maintenance in Ad Hoc wireless networks, Proceedings of the 7th annual international conference on Mobile computing and networking, p.85-96, July 2001, Rome, Italy [doi>10.1145/381677.381686]
• 5: Jeremy Elson , Lewis Girod , Deborah Estrin, Fine-grained network time synchronization using reference broadcasts, Proceedings of the 5th symposium on Operating systems design and implementation

  Due to copyright restrictions we are not able to make the PDFs for this conference available for downloading

  , December 09-11, 2002, Boston, Massachusetts [doi>10.1145/1060289.1060304]
• 6: L. M. Feeney and M. Nilsson. Investigating the energy consumption of a wireless network interface in an ad hoc networking environment. In Proc. of IEEE INFOCOM, April 2001.
• 7: P. Gupta and P. R. Kumar. Critical power for asymptotic connectivity in wireless networks. In Stochastic Analysis, Control, Optimization and Applications: A Volume in Honor of W.H. Fleming, 1998.
• 8: P. Gupta and P. R. Kumar. The capacity of wireless networks. IEEE Transactions on Information Theory, IT-46(2):388--404, 2000.
• 9: 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
• 10: D. B. Johnson and D. A. Maltz. Dynamic source routing in ad hoc wireless networks. draft-ietf-manet-dsr-04.txt, 2001.
• 11: Mamoru Maekawa, A N algorithm for mutual exclusion in decentralized systems, ACM Transactions on Computer Systems (TOCS), v.3 n.2, p.145-159, May 1985 [doi>10.1145/214438.214445]
• 12: S. Narayanaswamy, V. Kawadia, R. S. Sreenivas, and P. R. Kumar. Power control in ad hoc networks : Theory, architecture, algorithm and implementation of the COMPOW protocol. In European Wireless Conference, 2002.
• 13: M. Nosovic and T. Todd. Low power rendezvous and RFID wakeup for embedded wireless networks. In Annual IEEE Computer Communications Workshop, 2000.
• 14: C. E. Perkins and E. M. Royer. Ad hoc on demand distance vector (AODV) routing. Internet draft, IETF MANET working group, July 2000.
• 15: V. Rodoplu and T. H. Meng. Minimum energy mobile wireless networks. In Proceedings of the 1998 IEEE International Conference on Communications (ICC), 1998.
• 16: 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]
• 17: Eugene Shih , Seong-Hwan Cho , Nathan Ickes , Rex Min , Amit Sinha , Alice Wang , Anantha Chandrakasan, Physical layer driven protocol and algorithm design for energy-efficient wireless sensor networks, Proceedings of the 7th annual international conference on Mobile computing and networking, p.272-287, July 2001, Rome, Italy [doi>10.1145/381677.381703]
• 18: Suresh Singh , C. S. Raghavendra, PAMAS—power aware multi-access protocol with signalling for ad hoc networks, ACM SIGCOMM Computer Communication Review, v.28 n.3, p.5-26, July 1998 [doi>10.1145/293927.293928]
• 19: Pradeep K. Sinha, Distributed Operating Systems: Concepts and Design, Wiley-IEEE Press, 1996
• 20: Y.-C. Tseng, C.-S. Hsu, and T.-Y. Hsieh. Power-saving protocols for ieee 802.11-based multi hop ad hoc networks. In Proc. of INFOCOM, 2002.
• 21: UCB/LBNL/VINT. Network simulator - ns (version 2). http://www-mash.cs.berkeley.edu/ns/, January 2000.
• 22: P. J. Wan, G. Calinescu, X.-Y. Li, and O. Frieder. Minimum-energy broadcast routing in static ad hoc wireless networks. In Proc. of INFOCOM, 2001.
• 23: R. Wattenhofer, L. Li, P. Bahl, and Y.-M. Wang. Distributed topology control for power efficient operation in multihop wireless ad hoc networks. In Proc. of IEEE INFOCOM, 2001.
• 24: 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]
• 25: W. Ye, J. Heidemann, and D. Estrin. An energy-efficient MAC protocol for wireless sensor networks. In Proc. of INFOCOM, 2002.
• 26: R. Zheng and R. Kravets. On-demand power management for ad hoc networks. In Proc. of INFOCOM, 2003.

INDEX TERMS

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

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

General Terms:
Algorithms, Theory

Keywords:
asynchronous wakeup, block design and ad hoc networks, power management