Dynamic delay-constrained minimum-energy dissemination in wireless sensor networks

ABSTRACT

Disseminating data generated by sensors to users is one of useful functions of sensor networks. In probable real-time applications of sensor networks, multiple mobile users should receive data within their end-to-end delay constraint. In this paper, we propose a dynamic DElay-constrained minimum-Energy Dissemination (DEED) scheme. A dissemination tree (d-tree) is updated in a distributed way without regenerating the tree from scratch, such that energy consumption of the tree is minimized while satisfying end-to-end delay constraints. The d-tree is adjusted using delay estimation based on geometric distance. DEED increases the probability that packets arrive at users within an upper-bound end-to-end delay (UBED) and minimizes energy consumption in both building the d-tree and disseminating data to mobile sinks. Evaluation results show that DEED makes each node consume small energy resources and maintains fewer UBED misses when compared to Directed Diffusion and other baselines for sensor networks.

REFERENCES

• 1: Recursive Position Estimation in Sensor Networks, Proceedings of the Ninth International Conference on Network Protocols, p.35, November 11-14, 2001
• 2: Bettahar, H. and Bouabdallah, A. 2002. New algorithms for delay constraint multicast routing. In Networks 2002, Joint Conference of IEEE ICWLHN and IEEE ICN 2002. Atlanta, Georgia.
• 3: Sagnik Bhattacharya , Hyung Kim , Shashi Prabh , Tarek Abdelzaher, Energy-conserving data placement and asynchronous multicast in wireless sensor networks, Proceedings of the 1st international conference on Mobile systems, applications and services, p.173-185, May 05-08, 2003, San Francisco, California [doi>10.1145/1066116.1066120]
• 4: Bonfils, B. and Bonnet, P. 2003. Adaptive and decentralized operator placement for in-network query processing. In Proceedings of Information Processing in Sensor Networks. Palo Alto, CA.
• 5: Bulusu, N., Heidemann, J., and Estrin, D. 2000. Gps-less low cost outdoor localization for very small devices. IEEE Personal Communications, Special Issue on Smart Spaces and Environments 7, 5 (Oct.), 28--34.
• 6: Marco Caccamo , Lynn Y. Zhang , Lui Sha , Giorgio Buttazzo, An Implicit Prioritized Access Protocol for Wireless Sensor Networks, Proceedings of the 23rd IEEE Real-Time Systems Symposium (RTSS'02), p.39, December 03-05, 2002
• 7: Chen, K. and Nahrstedt, K. 2002. Effective location-guided tree construction algorithms for small group multicast in manet. In Proceedings of IEEE INFOCOM 2002. New York. 1180--1189.
• 8: Elson, J. and Estrin, D. 2001. Time synchronization for wireless sensor networks. In Workshop on Parallel and Distributed Computing Issues in Wireless and Mobile Computing. San Francisco, California.
• 9: Elson, J. and Romer, K. 2002. Wireless sensor networks: A new regime for time synchronization. In Proceedings of the First Workshop on Hot Topics In Networks (HotNets-I). Princeton, New Jersey.
• 10: Gui, C. and Mohapatra, P. 2003. Efficient overlay multicast for mobile ad hoc networks. In Proceedings of IEEE Wireless Communications and Networking Conference (WCNC) 2003. New Orleans, Louisiana.
• 11: Tian He , Brian M. Blum , John A. Stankovic , Tarek Abdelzaher, AIDA: Adaptive application-independent data aggregation in wireless sensor networks, ACM Transactions on Embedded Computing Systems (TECS), v.3 n.2, p.426-457, May 2004 [doi>10.1145/993396.993406]
• 12: Tian He , John A. Stankovic , Chenyang Lu , Tarek Abdelzaher, SPEED: A Stateless Protocol for Real-Time Communication in Sensor Networks, Proceedings of the 23rd International Conference on Distributed Computing Systems, p.46, May 19-22, 2003
• 13: 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]
• 14: V. Kanodia , C. Li , A. Sabharwal , B. Sadeghi , E. Knightly, Distributed multi-hop scheduling and medium access with delay and throughput constraints, Proceedings of the 7th annual international conference on Mobile computing and networking, p.200-209, July 2001, Rome, Italy [doi>10.1145/381677.381697]
• 15: 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]
• 16: Hyung Seok Kim , Tarek F. Abdelzaher , Wook Hyun Kwon, Minimum-energy asynchronous dissemination to mobile sinks in wireless 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.958515]
• 17: Stephanie Lindsey , Cauligi Raghavendra , Krishna M. Sivalingam, Data Gathering Algorithms in Sensor Networks Using Energy Metrics, IEEE Transactions on Parallel and Distributed Systems, v.13 n.9, p.924-935, September 2002 [doi>10.1109/TPDS.2002.1036066]
• 18: 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
• 19: Giovanni Resta , Paolo Santi, An analysis of the node spatial distribution of the random waypoint mobility model for ad hoc networks, Proceedings of the second ACM international workshop on Principles of mobile computing, October 30-31, 2002, Toulouse, France [doi>10.1145/584490.584500]
• 20: Elizabeth M. Royer , Charles E. Perkins, Multicast operation of the ad-hoc on-demand distance vector routing protocol, Proceedings of the 5th annual ACM/IEEE international conference on Mobile computing and networking, p.207-218, August 15-19, 1999, Seattle, Washington, United States [doi>10.1145/313451.313538]
• 21: Ural, H. and Zhu, K. 2002. An efficient distributed qos-based multicast routing algorithm. In Proceedings of the IEEE IPCCC'02. Phoenix.
• 22: Upkar Varshney, Multicast over wireless networks, Communications of the ACM, v.45 n.12, p.31-37, December 2002 [doi>10.1145/585597.585598]
• 23: 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]
• 24: Youssef, M. A., Younis, M. F., and Arisha, K. A. 2002. A constrained shortest-path energy-aware routing algortihm for wireless sensor networks. In Proceedings of the IEEE Wireless Communications and Networking Conference (WCNC). Orlando, Florida.
• 25: Qing Zhu , M. Parsa , J. J. Garcia-Luna-Aceves, A source-based algorithm for delay-constrained minimum-cost multicasting, Proceedings of the Fourteenth Annual Joint Conference of the IEEE Computer and Communication Societies (Vol. 1)-Volume, p.377, April 02-06, 1995

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.2 Network Protocols
          Subjects: Routing protocols
  C.3 SPECIAL-PURPOSE AND APPLICATION-BASED SYSTEMS

General Terms:
Algorithms, Design

Keywords:
Sensor network, energy, multicast