Energy efficient real-time data aggregation in wireless sensor networks

ABSTRACT

This paper studies the energy efficient routing for data aggregation in wireless sensor networks. The data aggregation tree is a tree where the root of the tree is the data center called the sink node and the other nodes are sensor nodes. The sensor nodes sense the data and pass the data back to the data center along the data aggregation tree. We consider a real-time scenario where the data aggregation must be performed within a specified latency constraint. The objective is to minimize the overall energy cost of the sensor nodes for data aggregation subject to the latency constraint. The original contributions of the paper include: 1) Development of an analytic model for IEEE Standard 802.15.4 CSMA-CA to compute the worst case delay for a sensor node to aggregate the data from all its child nodes in the aggregation tree; 2) Proposal of a heuristic algorithm for constructing data aggregation trees that minimize total energy cost under the latency bound obtained from our analytical model. Extensive simulations have been conducted and the results verify the validity of the proposed analytical model and the superior performance of the proposed algorithm for constructing aggregation trees.

REFERENCES

• 1: David Culler , Deborah Estrin , Mani Srivastava, Guest Editors' Introduction: Overview of Sensor Networks, Computer, v.37 n.8, p.41-49, August 2004 [doi>10.1109/MC.2004.93]
• 2: Alan Mainwaring , David Culler , Joseph Polastre , Robert Szewczyk , John Anderson, Wireless sensor networks for habitat monitoring, Proceedings of the 1st ACM international workshop on Wireless sensor networks and applications, September 28-28, 2002, Atlanta, Georgia, USA [doi>10.1145/570738.570751]
• 3: Chalermek Intanagonwiwat , Ramesh Govindan , Deborah Estrin, Directed diffusion: a scalable and robust communication paradigm for sensor networks, Proceedings of the 6th annual international conference on Mobile computing and networking, p.56-67, August 06-11, 2000, Boston, Massachusetts, United States [doi>10.1145/345910.345920]
• 4: G. J. Pottie , W. J. Kaiser, Wireless integrated network sensors, Communications of the ACM, v.43 n.5, p.51-58, May 2000 [doi>10.1145/332833.332838]
• 5: Saurabh Ganeriwal , Ram Kumar , Mani B. Srivastava, Timing-sync protocol for sensor networks, Proceedings of the 1st international conference on Embedded networked sensor systems, November 05-07, 2003, Los Angeles, California, USA [doi>10.1145/958491.958508]
• 6: Standard for part 15.4: Wireless medium access control (MAC) and physical layer (PHY) specification for low rate wireless personal area networks (WPANS). IEEE Standard 802.15.4, IEEE, New York, NY, 2003.
• 7: Jelena Misic , Vojislav B. Misic , Shairmina Shafi, Performance of IEEE 802.15.4 Beacon Enabled PAN with Uplink Transmissions in Non-Saturation Mode - Access Delay for Finite Buffers, Proceedings of the First International Conference on Broadband Networks (BROADNETS'04), p.416-425, October 25-29, 2004 [doi>10.1109/BROADNETS.2004.61]
• 8: J. Mišic, and V. B. Mišic, "Queuing analysis of sleep management in an 802.15.4 beacon enabled PAN", in IEEE/ACM First International Workshop on Broadband Wireless Services and Applications BroadWISE, (San Jose, CA), October 2004.
• 9: Y. Yu, B. Krishnamachari, and V. K. Prasanna, "Energy-latency tradeoffs for data gathering in wireless sensor networks", The 23rd Conference of IEEE Communication Society (INFOCOM), Hong Kong, SAR China, Mar 2004.
• 10: Curt Schurgers , Olivier Aberthorne , Mani Srivastava, Modulation scaling for Energy Aware Communication Systems, Proceedings of the 2001 international symposium on Low power electronics and design, p.96-99, August 2001, Huntington Beach, California, United States [doi>10.1145/383082.383103]
• 11: B. Prabhakar, E. Uysal-Biyikoglu, and A. E. Gamal, "Energy-efficient transmission over a wireless link via lazy packet scheduling", The 20th Conference of IEEE Communication Society (INFOCOM), Anchorage, Alaska, April 2001.
• 12: Chalermek Intanagonwiwat , Deborah Estrin , Ramesh Govindan , John Heidemann, Impact of Network Density on Data Aggregation in Wireless Sensor Networks, Proceedings of the 22 nd International Conference on Distributed Computing Systems (ICDCS'02), p.457, July 02-05, 2002
• 13: Chenyang Lu , Brian M. Blum , Tarek F. Abdelzaher , John A. Stankovic , Tian He, RAP: A Real-Time Communication Architecture for Large-Scale Wireless Sensor Networks, Proceedings of the Eighth IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS'02), p.55, September 25-27, 2002
• 14: K. Akkaya, M. Younis, and M. Youssef, "Efficient aggregation for delay-constrained data in wireless sensor networks", The Proceedings of Internet Compatible QoS in Ad Hoc Wireless Networks, 2005.
• 15: L. J. Kleinrock, Queuing System, volume 1: Theory, Wiley, New York, 1972.
• 16: X. Cheng, A. Thaeler, G. Xue, and D. Chen, "TPS: a time-based positioning scheme for outdoor sensor networks", The 23rd Conference of IEEE Communication Society (INFOCOM), Hong Kong, SAR China, Mar 2004.
• 17: 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
• 18: X. Cheng, X. Huang, D. Y. Li, W. L. Wu, and D. Z. Du, "A polynomial-time approximation scheme for the minimum-connected dominating set in ad hoc wireless networks", Networks, Vol. 42, No. 4, pp. 202--208, 2003.
• 19: 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
• 20: S. Khuller, B. Raghavachari, and N. Young, "Balancing minimum spanning trees and shortest-path trees", Algorithmica, Vol. 14, No. 4, pp. 305--321, 1995.
• 21: K. B. Kumar and J. M. Jaffe, "Routing to multiple destinations in computer networks", IEEE Transactions on Communication, Vol. 31, No. 3, pp. 343--351, 1983.
• 22: J. Misic and V. B. Misic, "Access delay for nodes with finite buffers in IEEE 802.15.4 beacon enabled PAN with uplink transmissions", Computer Communications J urnal, 2005.

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:
  G. Mathematics of Computing
  G.4 MATHEMATICAL SOFTWARE
      Subjects: Algorithm design and analysis

General Terms:
Algorithms, Design, Theory

Keywords:
IEEE 802.15.4 CSMA-CA, algorithms, data aggregation, real-time, wireless sensor networks