Karim Seada
Ahmed Helmy
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.
- P. Bose, P. Morin, I. Stojmenovic and J. Urrutia. "Routing with Guaranteed Delivery in Ad Hoc Wireless Networks". Workshop on Discrete Algorithms and Methods for Mobile Computing and Communications (DialM 1999). Google Scholar
Digital Library
- G. G. Finn. "Routing and Addressing Problems in Large Metropolitan-Scale Internetworks". Tech. Rep. ISI/RR-87-180, ISI, Mar. 1987.Google Scholar
- B. Karp and H.T. Kung. "GPSR: Greedy Perimeter Stateless Routing for Wireless Networks". ACM MOBICOM 2000. Google ScholarDigital Library
- E. Kranakis, H. Singh and J. Urrutia. "Compass Routing on Geometric Networks". In Proc. 11th Canadian Conference on Computational Geometry, August 1999.Google Scholar
- F. Kuhn, R. Wattenhofer and A. Zollinger. "Worst-Case Optimal and Average-Case Efficient Geometric Ad-Hoc Routing". ACM Mobihoc 2003. Google ScholarDigital Library
- 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.Google Scholar
- 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.Google Scholar
- D. S. J. De Couto, D. Aguayo, J. Bicket and R. Morris. "A High-Throughput Path Metric for Multi-Hop Wireless Routing". ACM MobiCom, September 2003. Google ScholarDigital Library
- A. Woo, T. Tong and D. Culler. "Taming the Underlying Issues for Reliable Multhop Routing in Sensor Networks". ACM SenSys, November 2003. Google ScholarDigital Library
- J. Zhao and R. Govindan. "Understanding Packet Delivery Performance in Dense Wireless Sensor Networks". ACM Sensys, November 2003. Google ScholarDigital Library
- G. Zhou, T. He, S. Krishnamurthy and J. A. Stankovic. "Impact of Radio Irregularity on Wireless Sensor Networks". ACM MobiSys 2004. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- K. Seada and A. Helmy. "Geographic Protocols in Sensor Networks". USC Technical Report, July 2004.Google Scholar
- A. Cerpa, N. Busek and D. Estrin. "SCALE: A tool for Simple Connectivity Assessment in Lossy Environments". CENS Tech. Rep., September 2003.Google Scholar
- 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.Google Scholar
- M. Zuniga and B. Krishnamachari, "Analyzing the Transitional Region in Low Power Wireless Links", IEEE Secon 2004.Google Scholar
- 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/Google Scholar
- T. S. Rappapport. "Wireless Communications: Principles and Practice". Prentice Hall. Google ScholarDigital Library
Index Terms
- Energy-efficient forwarding strategies for geographic routing in lossy wireless sensor networks
Recommendations
Efficient geographic routing in multihop wireless networks
MobiHoc '05: Proceedings of the 6th ACM international symposium on Mobile ad hoc networking and computingWe propose a new link metric called normalized advance (NADV) for geographic routing in multihop wireless networks. NADV selects neighbors with the optimal trade-off between proximity and link cost. Coupled with the local next hop decision in geographic ...
Efficient geographic routing over lossy links in wireless sensor networks
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 ...
A geographic routing hybrid approach for void resolution in wireless sensor networks
Abstract: Geographic routing is one of the most suitable routing strategies for large scale wireless sensor networks due to its low overhead and high scalability features. A geographic routing scheme usually combines a geographic greedy forwarding with ...
Comments