On accurate measurement of link quality in multi-hop wireless mesh networks

ABSTRACT

This paper presents a highly efficient and accurate link-quality measurement framework, called EAR (Efficient and Accurate link-quality monitoR), for multi-hop wireless mesh networks, that has several salient features. First, it exploits three complementary measurement schemes: passive, cooperative, and active monitoring. EAR maximizes the measurement accuracy by (i) dynamically and adaptively adopting one of these schemes and (ii) opportunistically exploiting the nicast application traffic present in the network, while minimizing the measurement overhead. Second, EAR effectively identifies the existence of wireless link asymmetry by measuring the quality of each link in both directions of the link, thus improving the utilization of network capacity by up to 114%. Finally, its reliance on both the network layer and the IEEE 802.11-based device driver solutions makes EAR easily deployable in existing multi-hop wireless mesh networks without system recompilation or MAC firmware modification. EAR has been evaluated extensively via both ns-2-based simulation and experimentation on our Linux-based implementation. Both simulation and experimentation results have shown EAR to provide highly accurate link-quality measurements with minimum overhead.

REFERENCES

• 1: Linux-WLAN project. http://www.linux-wlan.com/.
• 2: Mesh dynamics inc. http://www.meshdynamics.com.
• 3: Mesh networking summit. http://research.microsoft.com/meshsummit.
• 4: MIT roofnet. http://www.pdos.lcs.mit.edu/roofnet.
• 5: Multiband atheros driver for wifi. http://madwifi.org/.
• 6: Netfilter. http://www.netfilter.org.
• 7: ns-2 network simulator. http://www.isi.edu/nsnam/ns.
• 8: Seattle wireless. http://www.seattlewireless.net.
• 9: IEEE 802.11, wireless LAN medium access control (MAC) and physical layer (PHY) specifications. Standard, IEEE, Aug. 1999.
• 10: Daniel Aguayo , John Bicket , Sanjit Biswas , Glenn Judd , Robert Morris, Link-level measurements from an 802.11b mesh network, Proceedings of the 2004 conference on Applications, technologies, architectures, and protocols for computer communications, August 30-September 03, 2004, Portland, Oregon, USA
• 11: Mansoor Alicherry , Randeep Bhatia , Li (Erran) Li, Joint channel assignment and routing for throughput optimization in multi-radio wireless mesh networks, Proceedings of the 11th annual international conference on Mobile computing and networking, August 28-September 02, 2005, Cologne, Germany [doi>10.1145/1080829.1080836]
• 12: Paramvir Bahl , Ranveer Chandra , John Dunagan, SSCH: slotted seeded channel hopping for capacity improvement in IEEE 802.11 ad-hoc wireless networks, Proceedings of the 10th annual international conference on Mobile computing and networking, September 26-October 01, 2004, Philadelphia, PA, USA [doi>10.1145/1023720.1023742]
• 13: S. Biswas and R. Morris. Opportunistic routing in multi-hop wireless networks. In Proceedings of the Second Workshop on Hot Topics in Networks (HotNets-II), Cambridge, MA, Nov. 2003.
• 14: Sanjit Biswas , Robert Morris, ExOR: opportunistic multi-hop routing for wireless networks, Proceedings of the 2005 conference on Applications, technologies, architectures, and protocols for computer communications, August 22-26, 2005, Philadelphia, Pennsylvania, USA
• 15: S. Chen and K. Nahrstedt. Distributed quality-of-service routing in ad hoc networks. IEEE JSAC, 17(8):1488--1505, 1999.
• 16: David D. Clark , Craig Partridge , J. Christopher Ramming , John T. Wroclawski, A knowledge plane for the internet, Proceedings of the 2003 conference on Applications, technologies, architectures, and protocols for computer communications, August 25-29, 2003, Karlsruhe, Germany [doi>10.1145/863955.863957]
• 17: 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]
• 18: D. S. D. Couto, D. Aguayo, B. A. Chambers, and R. Morris. Performance of multi-hop wireless networks: Shortest path is not enough. In Proceedings of the First Workshop on Hot Topics in Networks (HotNets-I), Princeton, New Jersey, Oct. 2002.
• 19: C. Dovrolis, P. Ramanathan, and D. Moore. What do packet dispersion techniques measure? In Proceedings of IEEE InfoCom, Anchorage, AK, Apr. 2001.
• 20: Allen B. Downey, Using pathchar to estimate Internet link characteristics, Proceedings of the conference on Applications, technologies, architectures, and protocols for computer communication, p.241-250, August 30-September 03, 1999, Cambridge, Massachusetts, United States
• 21: Richard Draves , Jitendra Padhye , Brian Zill, Routing in multi-radio, multi-hop wireless mesh networks, Proceedings of the 10th annual international conference on Mobile computing and networking, September 26-October 01, 2004, Philadelphia, PA, USA [doi>10.1145/1023720.1023732]
• 22: Tom Goff , Nael B. Abu-Ghazaleh , Dhananjay S. Phatak , Ridvan Kahvecioglu, Preemptive routing in Ad Hoc networks, Proceedings of the 7th annual international conference on Mobile computing and networking, p.43-52, July 2001, Rome, Italy [doi>10.1145/381677.381682]
• 23: S. Haykin. Cognitive radio: Brain-empowered wireless communications. IEEE JSAC, 23(2), Feb. 2005.
• 24: C. L. Hedrick, Routing Information Protocol, RFC Editor, 1988
• 25: Camden C. Ho , Krishna N. Ramachandran , Kevin C. Almeroth , Elizabeth M. Belding-Royer, A scalable framework for wireless network monitoring, Proceedings of the 2nd ACM international workshop on Wireless mobile applications and services on WLAN hotspots, October 01-01, 2004, Philadelphia, PA, USA [doi>10.1145/1024733.1024745]
• 26: A. Jain, D. Qiao, and K. G. Shin. RT-WLAN: A soft real-time extension to the orinoco linux device driver. In Proceedings of IEEE PIMRC, Beijing, China, Sept. 2003.
• 27: D. B. Johnson and D. A. Maltz. Dynamic source routing in ad hoc wireless networks. In the Book of Mobile Computing, volume 353. Kluwer Academic Publishers, 1996.
• 28: Murali Kodialam , Thyaga Nandagopal, Characterizing the capacity region in multi-radio multi-channel wireless mesh networks, Proceedings of the 11th annual international conference on Mobile computing and networking, August 28-September 02, 2005, Cologne, Germany [doi>10.1145/1080829.1080837]
• 29: D. Kotz, C. Newport, R. S. Gray, J. Liu, Y. Yuan, and C. Elliott. Experimental evaluation of wireless simulation assumptions. Technical Report TR2004-507, Dept. of Computer Science, Dartmouth College, June 2004.
• 30: Seungjoon Lee , Bobby Bhattacharjee , Suman Banerjee, Efficient geographic routing in multihop wireless networks, Proceedings of the 6th ACM international symposium on Mobile ad hoc networking and computing, May 25-27, 2005, Urbana-Champaign, IL, USA [doi>10.1145/1062689.1062720]
• 31: B. M. Maggs. Asymmetric wireless networks. http://www-2.cs.cmu.edu/ bmm/wireless.html.
• 32: J. Moy. OSPF version 2. Internet Request for Comments 2328 (rfc2328.txt), Apr. 1998.
• 33: C. Perkins , E. Belding-Royer , S. Das, Ad hoc On-Demand Distance Vector (AODV) Routing, RFC Editor, 2003
• 34: Charles E. Perkins , Pravin Bhagwat, Highly dynamic Destination-Sequenced Distance-Vector routing (DSDV) for mobile computers, Proceedings of the conference on Communications architectures, protocols and applications, p.234-244, August 31-September 02, 1994, London, United Kingdom
• 35: Lili Qiu , Paramvir Bahl , Ananth Rao , Lidong Zhou, Troubleshooting multihop wireless networks, Proceedings of the 2005 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, June 06-10, 2005, Banff, Alberta, Canada
• 36: A. Raniwala and T. Chiueh. Architecture and algorithms for an IEEE 802.11-based multi-channel wireless mesh network. In Proceedings of IEEE InfoCom, Miami, FL, Mar. 2005.
• 37: S. Seshan, M. Stemm, and R. Katz. SPAND: Shared passive network performance discovery. In Proceedings of USENIX Symposium on Internet Technologies and Systems, Monterey, CA, Dec. 1997.
• 38: R. Sivakumar, P. Sinha, and V. Bharghavan. CEDAR: Core extraction distributed ad hoc routing. IEEE JSAC, 17(8):1454--65, 1999.
• 39: Carey Williamson, Internet Traffic Measurement, IEEE Internet Computing, v.5 n.6, p.70-74, November 2001 [doi>10.1109/4236.968834]
• 40: Chansu Yu , Kang G. Shin , Lubo Song, Link-layer salvaging for making routing progress in mobile ad hoc networks, Proceedings of the 6th ACM international symposium on Mobile ad hoc networking and computing, May 25-27, 2005, Urbana-Champaign, IL, USA [doi>10.1145/1062689.1062721]

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design

General Terms:
Design, Experimentation, Measurement, Performance

Keywords:
asymmetric link quality, link-quality measurement, wireless mesh networks