Energy-efficient forwarding strategies for geographic routing in lossy wireless sensor networks

ABSTRACT

Recent experimental studies have shown that wireless links in real sensor networks can be extremely unreliable, deviating to a large extent from the idealized perfect-reception-within-range models used in common network simulation tools. Previously proposed geographic routing protocols commonly employ a maximum-distance greedy forwarding technique that works well in ideal conditions. However, such a forwarding technique performs poorly in realistic conditions as it tends to forward packets on lossy links. We identify and illustrate this weak-link problem and the related distance-hop trade-off, whereby energy efficient geographic forwarding must strike a balance between shorter, high-quality links, and longer lossy links. The study is done for scenarios with and without automatic repeat request (ARQ).

Based on an analytical link loss model, we study the distance-hop trade-off via mathematical analysis and extensive simulations of a wide array of blacklisting/link-selection strategies; we also validate some strategies using a set of real experiments on motes. Our analysis, simulations and experiments all show that the product of the packet reception rate (PRR) and the distance traversed towards destination is the optimal forwarding metric for the ARQ case, and is a good metric even without ARQ. Nodes using this metric often take advantage of neighbors in the transitional region (high-variance links). Our results also show that reception-based forwarding strategies are more efficient than purely distance-based strategies; relative blacklisting schemes reduce disconnections and achieve higher delivery rates than absolute blacklisting schemes; and that ARQ schemes become more important in larger networks.

REFERENCES

• 1: Prosenjit Bose , Pat Morin , Ivan Stojmenović , Jorge Urrutia, Routing with guaranteed delivery in ad hoc wireless networks, Proceedings of the 3rd international workshop on Discrete algorithms and methods for mobile computing and communications, p.48-55, August 20-20, 1999, Seattle, Washington, United States [doi>10.1145/313239.313282]
• 2: G. G. Finn. "Routing and Addressing Problems in Large Metropolitan-Scale Internetworks". Tech. Rep. ISI/RR-87-180, ISI, Mar. 1987.
• 3: 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]
• 4: E. Kranakis, H. Singh and J. Urrutia. "Compass Routing on Geometric Networks". In Proc. 11th Canadian Conference on Computational Geometry, August 1999.
• 5: Fabian Kuhn , Roger Wattenhofer , Aaron Zollinger, Worst-Case optimal and average-case efficient geometric ad-hoc routing, Proceedings of the 4th ACM international symposium on Mobile ad hoc networking & computing, June 01-03, 2003, Annapolis, Maryland, USA [doi>10.1145/778415.778447]
• 6: D. Kotz, C. Newport and C. Elliott. "The mistaken axioms of wireless-network research". Technical Report TR2003-467, Dept. of Computer Science, Dartmouth College, July 2003.
• 7: D. Ganesan, B. Krishnamachari, A. Woo, D. Culler, D. Estrin and S. Wicker. "Complex Behavior at Scale: An Experimental Study of Low-Power Wireless Sensor Networks". UCLA CS Technical Report UCLA/CSD-TR 02-0013, 2002.
• 8: 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]
• 9: 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]
• 10: 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]
• 11: 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]
• 12: M. Mauve, J. Widmer and H. Hartenstein. "A Survey on Position-based Routing in Mobile Ad Hoc Networks". IEEE Network Magazine, Vol. 15, No. 6, pp. 30--39, November 2001.
• 13: K. Seada and A. Helmy. "Geographic Protocols in Sensor Networks". USC Technical Report, July 2004.
• 14: A. Cerpa, N. Busek and D. Estrin. "SCALE: A tool for Simple Connectivity Assessment in Lossy Environments". CENS Tech. Rep., September 2003.
• 15: A. Cerpa, J. L. Wong, L. Kuang, M. Potkonjak and D. Estrin. "Statistical Model of Lossy Links in Wireless Sensor Networks". CENS Tech. Rep., April 2004.
• 16: M. Zuniga and B. Krishnamachari, "Analyzing the Transitional Region in Low Power Wireless Links", IEEE Secon 2004.
• 17: F. Silva, J. Heidemann and R. Govindan, Network Routing API 9.1, ISI Laboratory for Embedded Networked Sensor Experimentation, June 12th, 2003. Available online at http://www.isi.edu/ilense/pubs/
• 18: Theodore S. Rappaport, Wireless Communications: Principles and Practice, IEEE Press, Piscataway, NJ, 1996

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.4 PERFORMANCE OF SYSTEMS
      Subjects: Performance attributes

  I. Computing Methodologies
  I.6 SIMULATION AND MODELING

General Terms:
Design, Performance

Keywords:
blacklisting, geographic routing, wireless sensor networks