Data forwarding in extremely low duty-cycle sensor networks with unreliable communication links

ABSTRACT

In extremely low duty-cycle sensor networks, end-to-end communications cannot afford to maintain an always-awake communication backbone. Low duty-cycle, accompanied by the unreliable nature of wireless communication, makes it essential to design a new data forwarding scheme for such networks, so as to achieve network energy efficiency, reliability, and timeliness in an integrated fashion.

In this work, we introduce the concept of dynamic switch-based forwarding (DSF) that optimizes the (i) expected data delivery ratio, (ii) expected communication delay, or (iii) expected energy consumption. DSF is designed for networks with possibly unreliable communication links and predetermined node communication schedules. Interestingly, we reveal that allowing opportunistic looping can actually reduce the end-to-end delay. To our knowledge, these are the most encouraging results to date in this new research direction. In this paper, DSF is evaluated with a theoretical analysis, extensive simulation, and physical testbed consisting of 20 MicaZ motes. Results reveal the remarkable advantage of DSF in extremely low duty-cycle sensor networks in comparison to three well-known solutions (ETX [3], PRRxD [19] and DESS [16]). We also demonstrate our solution defaults into ETX in always-awake networks and DESS in perfect-link networks.

REFERENCES

• 1: Qing Cao , Tarek Abdelzaher , Tian He , John Stankovic, Towards optimal sleep scheduling in sensor networks for rare-event detection, Proceedings of the 4th international symposium on Information processing in sensor networks, April 24-27, 2005, Los Angeles, California
• 2: Chipcon. CC2420 Product Information and Data Sheet. Avaiable at http://www.chipcon.com/.
• 3: Douglas S. J. De Couto , Daniel Aguayo , John Bicket , Robert Morris, A high-throughput path metric for multi-hop wireless routing, Proceedings of the 9th annual international conference on Mobile computing and networking, September 14-19, 2003, San Diego, CA, USA [doi>10.1145/938985.939000]
• 4: 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]
• 5: David Gay , Philip Levis , Robert von Behren , Matt Welsh , Eric Brewer , David Culler, The nesC language: A holistic approach to networked embedded systems, Proceedings of the ACM SIGPLAN 2003 conference on Programming language design and implementation, June 09-11, 2003, San Diego, California, USA
• 6: Yu Gu , Joengmin Hwang , Tian He , David Hung-Chang Du, uSense: A Unified Asymmetric Sensing Coverage Architecture for Wireless Sensor Networks, Proceedings of the 27th International Conference on Distributed Computing Systems, p.8, June 25-27, 2007 [doi>10.1109/ICDCS.2007.150]
• 7: Tian He , Sudha Krishnamurthy , Liqian Luo , Ting Yan , Lin Gu , Radu Stoleru , Gang Zhou , Qing Cao , Pascal Vicaire , John A. Stankovic , Tarek F. Abdelzaher , Jonathan Hui , Bruce Krogh, VigilNet: An integrated sensor network system for energy-efficient surveillance, ACM Transactions on Sensor Networks (TOSN), v.2 n.1, p.1-38, February 2006 [doi>10.1145/1138127.1138128]
• 8: Jonathan W. Hui , David Culler, The dynamic behavior of a data dissemination protocol for network programming at scale, Proceedings of the 2nd international conference on Embedded networked sensor systems, November 03-05, 2004, Baltimore, MD, USA [doi>10.1145/1031495.1031506]
• 9: Abtin Keshavarzian , Huang Lee , Lakshmi Venkatraman, Wakeup scheduling in wireless sensor networks, Proceedings of the 7th ACM international symposium on Mobile ad hoc networking and computing, May 22-25, 2006, Florence, Italy [doi>10.1145/1132905.1132941]
• 10: H. Kiehne. Battery Technology Handbook. Marcel Dekker, 2003.
• 11: Young-Jin Kim , Ramesh Govindan , Brad Karp , Scott Shenker, Geographic routing made practical, Proceedings of the 2nd conference on Symposium on Networked Systems Design & Implementation, p.217-230, May 02-04, 2005
• 12: S. Lee, K. J. Kwak, and A. T. Campbell. Solicitation-Based Forwarding for Sensor Networks. In SECON'06, 2006.
• 13: Y. Li, W. Ye, and J. Heidemann. Energy and Latency Control in Low Duty Cycle MAC Protocols. In WCNC'05, 2005.
• 14: Shan Lin , Jingbin Zhang , Gang Zhou , Lin Gu , John A. Stankovic , Tian He, ATPC: adaptive transmission power control for wireless sensor networks, Proceedings of the 4th international conference on Embedded networked sensor systems, October 31-November 03, 2006, Boulder, Colorado, USA [doi>10.1145/1182807.1182830]
• 15: J. Liu, F. Zhao, P. Cheung, and L. Guibas. Apply Geometric Duality to Energy-efficient Non-local Phenomenon Awareness using Sensor Networks. IEEE Wireless Communications, 11(6), 2004.
• 16: G. Lu, N. Sadagopan, B. Krishnamachari, and A. Goel. Delay Efficient Sleep Scheduling in WIreless Sensor Networks. In INFOCOM'05, 2005.
• 17: Miklós Maróti , Branislav Kusy , Gyula Simon , Ákos Lédeczi, The flooding time synchronization protocol, Proceedings of the 2nd international conference on Embedded networked sensor systems, November 03-05, 2004, Baltimore, MD, USA [doi>10.1145/1031495.1031501]
• 18: Joseph Polastre , Jason Hill , David Culler, Versatile low power media access for wireless sensor networks, Proceedings of the 2nd international conference on Embedded networked sensor systems, November 03-05, 2004, Baltimore, MD, USA [doi>10.1145/1031495.1031508]
• 19: Karim Seada , Marco Zuniga , Ahmed Helmy , Bhaskar Krishnamachari, Energy-efficient forwarding strategies for geographic routing in lossy wireless sensor networks, Proceedings of the 2nd international conference on Embedded networked sensor systems, November 03-05, 2004, Baltimore, MD, USA [doi>10.1145/1031495.1031509]
• 20: N. Shrivastava , R. Mudumbai U. Madhow , S. Suri, Target tracking with binary proximity sensors: fundamental limits, minimal descriptions, and algorithms, Proceedings of the 4th international conference on Embedded networked sensor systems, October 31-November 03, 2006, Boulder, Colorado, USA [doi>10.1145/1182807.1182833]
• 21: Ivan Stoianov , Lama Nachman , Sam Madden , Timur Tokmouline, PIPENETa wireless sensor network for pipeline monitoring, Proceedings of the 6th international conference on Information processing in sensor networks, April 25-27, 2007, Cambridge, Massachusetts, USA [doi>10.1145/1236360.1236396]
• 22: Xiaorui Wang , Guoliang Xing , Yuanfang Zhang , Chenyang Lu , Robert Pless , Christopher Gill, Integrated coverage and connectivity configuration 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.958496]
• 23: Alec Woo , Terence Tong , David Culler, Taming the underlying challenges of reliable multihop routing in 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.958494]
• 24: Ting Yan , Tian He , John A. Stankovic, Differentiated surveillance 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.958498]
• 25: W. Ye, J. Heidemann, and D. Estrin. An Energy-Efficient MAC Protocol for Wireless Sensor Networks. In INFOCOM, 2002.
• 26: 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]
• 27: Y. Yu, B. Krishnamachari, and V. K. Prasanna. Energy-Latency Tradeoffs for Data Gathering in Wireless Sensor Networks. In IEEE INFOCOM, 2004.
• 28: Jerry Zhao , Ramesh Govindan, Understanding packet delivery performance in dense 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.958493]
• 29: Gang Zhou , Tian He , Sudha Krishnamurthy , John A. Stankovic, Impact of radio irregularity on wireless sensor networks, Proceedings of the 2nd international conference on Mobile systems, applications, and services, June 06-09, 2004, Boston, MA, USA [doi>10.1145/990064.990081]
• 30: M. Zuniga and B. Krishnamachari. Analyzing the Transitional Region in Low Power Wireless Links. In IEEE SECON'04, 2004.

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

General Terms:
Algorithms, Design, Performance

Keywords:
DSF, data forwarding, lossy radio link, low duty-cycle