An optimal wake-up scheduling algorithm for minimizing energy consumption while limiting maximum delay in a mesh sensor network

ABSTRACT

This paper presents an algorithm for maximizing the lifetime of a sensor network while guaranteeing an upper bound on the end-to-end delay. We prove that the proposed algorithm is optimal and requires simple computing operations that can be implemented by simple devices. To the best of our knowledge, this is the first paper to propose a sensor wake-up frequency that depends on the sensor's location in the routing paths. Using simulations, we show that the proposed algorithm significantly increases the lifetime of the network while guaranteeing a maximum on the end-to-end delay.

REFERENCES

• 1: Q. Li and D. Rus, "Global clock synchronization in sensor networks," in Proc. INFOCOM, Hong Kong, China, Mar. 2004.
• 2: Jeremy Elson , Kay Römer, Wireless sensor networks: a new regime for time synchronization, ACM SIGCOMM Computer Communication Review, v.33 n.1, p.149-154, January 2003 [doi>10.1145/774763.774787]
• 3: Y. Li, W. Ye, and J. Heidemann, "Energy and latency control in low duty cycle MAC protocols," in Proc. IEEE Wireless Commun. Netw. Conf., New Orleans, LA, USA, Mar. 2005, pp. 676-682.
• 4: Jeremy Elson , Lewis Girod , Deborah Estrin, Fine-grained network time synchronization using reference broadcasts, ACM SIGOPS Operating Systems Review, v.36 n.SI, Winter 2002 [doi>10.1145/844128.844143]
• 5: Sameer Tilak , Nael B. Abu-Ghazaleh , Wendi Heinzelman, A taxonomy of wireless micro-sensor network models, ACM SIGMOBILE Mobile Computing and Communications Review, v.6 n.2, p.28-36, April 2002 [doi>10.1145/565702.565708]
• 6: V. Annamalai, S. Gupta, and L. Schwiebert, "On tree-based converge-casting in wireless sensor networks," in Proc. IEEE Wireless Commun. Netw. Conf., Mar. 16-20, 2003, vol. 3, pp. 1942-1947.
• 7: Y. Xue and B. Li, "A location-aided power-aware routing protocol in mobile ad hoc networks," in Proc. IEEE GLOBECOM, San Antonio, TX, Nov. 2001, vol. 5, pp. 2837-2841.
• 8: C. Inc., Cc2420 Data Sheet.
• 9: Hui Cao , Kenneth Parker , Anish Arora, O-MAC: A Receiver Centric Power Management Protocol, Proceedings of the Proceedings of the 2006 IEEE International Conference on Network Protocols, p.311-320, November 12-15, 2006 [doi>10.1109/ICNP.2006.320181]
• 10: Wei Ye , Fabio Silva , John Heidemann, Ultra-low duty cycle MAC with scheduled channel polling, Proceedings of the 4th international conference on Embedded networked sensor systems, October 31-November 03, 2006, Boulder, Colorado, USA [doi>10.1145/1182807.1182839]
• 11: Cintia B. Margi , Katia Obraczka, Instrumenting Network Simulators for Evaluating Energy Consumption in Power-Aware Ad-Hoc Network Protocols, Proceedings of the The IEEE Computer Society's 12th Annual International Symposium on Modeling, Analysis, and Simulation of Computer and Telecommunications Systems, p.337-346, October 04-08, 2004
• 12: Wei Ye , John Heidemann , Deborah Estrin, Medium access control with coordinated adaptive sleeping for wireless sensor networks, IEEE/ACM Transactions on Networking (TON), v.12 n.3, p.493-506, June 2004 [doi>10.1109/TNET.2004.828953]
• 13: G. Lu, N. Sadagopan, B. Krishnamachari, and A. Goel, "Delay efficient sleep scheduling in wireless sensor networks," in Proc. INFOCOM, Miami, FL, Mar. 2005, pp. 2470-2481.
• 14: G. Lu, B. Krishnamachari, and C. S. Raghavendra, "An adaptive energy-efficient and low-latency MAC for data gathering in wireless sensor networks," in Proc. IPDPS, Santa Fe, NM, Apr. 2004, p. 224.
• 15: W. Lai and I. C. Paschalidis, "Routing through noise and sleeping nodes in sensor networks: Latency vs. energy trade-offs," in Proc. 45th IEEE Conf. Decision Control, Dec. 2006, pp. 2716-2721.
• 16: A. E. Gamal and J. Mammen, "Optimal hopping in ad hoc wireless networks," in Proc. INFOCOM, Barcelona, Spain, Apr. 2006, pp. 1-10.
• 17: Olivier Dousse , Petteri Mannersalo , Patrick Thiran, Latency of wireless sensor networks with uncoordinated power saving mechanisms, 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.989474]
• 18: B. Prabhakar, E. Uysal-Biyikoglu, and A. E. Gamal, "Energy-efficient transmission over a wireless link via lazy packet scheduling," in Proc. INFOCOM, Anchorage, AK, Apr. 2001, pp. 386-394.
• 19: C. Nair, A. E. Gamal, B. Prabhakar, E. Uysal-Biyikoglu, and S. Zahedi, "Energy-efficient scheduling of packet transmissions over wireless networks," in Proc. INFOCOM, New York, NY, Jun. 2002.
• 20: L. Miao and C. G. Cassandras, "Optimal transmission scheduling for energy-efficient wireless networks," in Proc. INFOCOM, Barcelona, Spain, Apr. 2006, p. 1-11.
• 21: Y. Yu, B. Krishnamachari, and V. K. Prasanna, "Energy-latency tradeoffs for data gathering in wireless sensor networks," in Proc. INFOCOM, Hong Kong, China, 2004.
• 22: Edgar H. Callaway, Wireless Sensor Networks: Architectures and Protocols, CRC Press, Inc., Boca Raton, FL, 2003
• 23: 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]
• 24: Jana van Greunen , Jan Rabaey, Lightweight time synchronization for sensor networks, Proceedings of the 2nd ACM international conference on Wireless sensor networks and applications, September 19-19, 2003, San Diego, CA, USA [doi>10.1145/941350.941353]
• 25: 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]
• 26: Roberto Solis-Oba, 2-Approximation Algorithm for Finding a Spanning Tree with Maximum Number of Leaves, Proceedings of the 6th Annual European Symposium on Algorithms, p.441-452, August 24-26, 1998

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.5 Local and Wide-Area Networks
          Subjects: Access schemes

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Wireless communication; Network topology
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Performance attributes

  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sequencing and scheduling

General Terms:
Algorithms, Design, Management, Performance

Keywords:
scheduling in wireless networks, sensor networks