Routing in multi-radio, multi-hop wireless mesh networks

ABSTRACT

We present a new metric for routing in multi-radio, multi-hop wireless networks. We focus on wireless networks with stationary nodes, such as community wireless networks.The goal of the metric is to choose a high-throughput path between a source and a destination. Our metric assigns weights to individual links based on the Expected Transmission Time (ETT) of a packet over the link. The ETT is a function of the loss rate and the bandwidth of the link. The individual link weights are combined into a path metric called Weighted Cumulative ETT (WCETT) that explicitly accounts for the interference among links that use the same channel. The WCETT metric is incorporated into a routing protocol that we call Multi-Radio Link-Quality Source Routing.We studied the performance of our metric by implementing it in a wireless testbed consisting of 23 nodes, each equipped with two 802.11 wireless cards. We find that in a multi-radio environment, our metric significantly outperforms previously-proposed routing metrics by making judicious use of the second radio.

REFERENCES

• 1: Hari Adiseshu , Guru Parulkar , George Varghese, A reliable and scalable striping protocol, Conference proceedings on Applications, technologies, architectures, and protocols for computer communications, p.131-141, August 28-30, 1996, Palo Alto, California, United States
• 2: Atul Adya , Paramvir Bahl , Jitendra Padhye , Alec Wolman , Lidong Zhou, A Multi-Radio Unification Protocol for IEEE 802.11 Wireless Networks, Proceedings of the First International Conference on Broadband Networks (BROADNETS'04), p.344-354, October 25-29, 2004 [doi>10.1109/BROADNETS.2004.8]
• 3: M. Allman, H. Kruse, and S. Ostermann. An application-level solution to TCP's satellite inefficiencies. In WOSBIS, 1996.
• 4: B. Awerbuch, D. Holmer, and H. Rubens. High throughput route selection in mult-rate ad hoc wireless networks. Technical report, Johns Hopkins University, 2003.
• 5: Paramvir Bahl , Atul Adya , Jitendra Padhye , Alec Walman, Reconsidering wireless systems with multiple radios, ACM SIGCOMM Computer Communication Review, v.34 n.5, October 2004 [doi>10.1145/1039111.1039122]
• 6: Bay area wireless users group. http://www.bawug.org/.
• 7: Sumitha Bhandarkar , Nauzad Erach Sadry , A. L. Narasimha Reddy , Nitin H. Vaidya, TCP-DCR: A Novel Protocol for Tolerating Wireless Channel Errors, IEEE Transactions on Mobile Computing, v.4 n.5, p.517-529, September 2005 [doi>10.1109/TMC.2005.72]
• 8: G. Bianchi. Performance analysis of the IEEE 802.11 distributed coordinated function. IEEE JSAC, 18(3):535--547, March 2000.
• 9: Josh Broch , David A. Maltz , David B. Johnson, Supporting Hierarchy and Heterogeneous Interfaces in Multi-Hop Wireless Ad Hoc Networks, Proceedings of the 1999 International Symposium on Parallel Architectures, Algorithms and Networks (ISPAN '99), p.370, June 23-25, 1999
• 10: F. Cali, M. Conti, and E. Gregori. IEEE 802.11 wireless LAN capacity analysis and protocol enhancement. In INFOCOM, 1998.
• 11: R. Chandra, V. Bahl, and P. Bahl. MultiNet: Connecting to multiple IEEE 802.11 networks using a single wireless card. In INFOCOM, 2004.
• 12: C. Y. Chang, P. C. Huang, C. T. Chang, and Y.-S. Chen. Dynamic channel assignment and reassignment for exploiting channel reuse opportunities in ad hoc wireless networks. IEICE Trans on Comm, Apr 2003.
• 13: Kwan-Wu Chin , John Judge , Aidan Williams , Roger Kermode, Implementation experience with MANET routing protocols, ACM SIGCOMM Computer Communication Review, v.32 n.5, November 2002 [doi>10.1145/774749.774758]
• 14: R. R. Choudhury and N. Vaidya. Impact of directional antennas on ad hoc routing. In PWC, 2003.
• 15: 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]
• 16: R. Draves, J. Padhye, and B. Zill. The architecture of the Link Quality Source Routing Protocol. Technical Report MSR-TR-2004-57, Microsoft Research, 2004.
• 17: Richard Draves , Jitendra Padhye , Brian Zill, Comparison of routing metrics for static multi-hop wireless networks, Proceedings of the 2004 conference on Applications, technologies, architectures, and protocols for computer communications, August 30-September 03, 2004, Portland, Oregon, USA
• 18: R. Dube, C. Rais, K.-E. Wang, and S. Tripathi. Signal stability based adaptive routing (SSA) for ad-hoc mobile networks. IEEE Personal Comm, Feb 1997.
• 19: Z. Fu, P. Zerfos, H. Luo, S. Lu, L. Zhang, and M. Gerla. The Impact of Multihop Wireless Channel on TCP Throughput and Loss. In INFOCOM, 2003.
• 20: 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]
• 21: P. Gupta and P. R. Kumar. The capacity of wireless networks. IEEE Trans on Info Theory, Mar 2000.
• 22: Gavin Holland , Nitin Vaidya , Paramvir Bahl, A rate-adaptive MAC protocol for multi-Hop wireless networks, Proceedings of the 7th annual international conference on Mobile computing and networking, p.236-251, July 2001, Rome, Italy [doi>10.1145/381677.381700]
• 23: Hung-Yun Hsieh , Raghupathy Sivakumar, A transport layer approach for achieving aggregate bandwidths on multi-homed mobile hosts, Proceedings of the 8th annual international conference on Mobile computing and networking, September 23-28, 2002, Atlanta, Georgia, USA [doi>10.1145/570645.570656]
• 24: Y.-C. Hu and D. B. Johnson. Design and demonstration of live audio and video over multi-hop wireless networks. In MILCOM, 2002.
• 25: Kamal Jain , Jitendra Padhye , Venkata N. Padmanabhan , Lili Qiu, Impact of interference on multi-hop wireless network performance, Proceedings of the 9th annual international conference on Mobile computing and networking, September 14-19, 2003, San Diego, CA, USA [doi>10.1145/938985.938993]
• 26: D. B. Johnson and D. A. Maltz. Dynamic source routing in ad-hoc wireless networks. In Mobile Computing. Kluwer Academic Publishers, 1996.
• 27: R. Karrer, A. Sabharwal, and E. Knightly. Enabling Large-scale Wireless Broadband: The Case for TAPs. In HotNets, 2003.
• 28: Srinivasan Keshav, A control-theoretic approach to flow control, ACM SIGCOMM Computer Communication Review, v.21 n.4, p.3-15, Sept. 1991
• 29: Jinyang Li , Charles Blake , Douglas S.J. De Couto , Hu Imm Lee , Robert Morris, Capacity of Ad Hoc wireless networks, Proceedings of the 7th annual international conference on Mobile computing and networking, p.61-69, July 2001, Rome, Italy [doi>10.1145/381677.381684]
• 30: Haiyun Luo , Ramachandran Ramjee , Prasun Sinha , Li (Erran) Li , Songwu Lu, UCAN: a unified cellular and ad-hoc network architecture, Proceedings of the 9th annual international conference on Mobile computing and networking, September 14-19, 2003, San Diego, CA, USA [doi>10.1145/938985.939021]
• 31: Mesh Networks Inc. Mesh networks technology overview. http://www.meshnetworks.com.
• 32: A. Nasipuri and S. R. Das. A multichannel CSMA MAC protocol for mobile multihop networks. In WCNC, 1999.
• 33: Charles E. Perkins , Elizabeth M. Royer, Ad-hoc On-Demand Distance Vector Routing, Proceedings of the Second IEEE Workshop on Mobile Computer Systems and Applications, p.90, February 25-26, 1999
• 34: Radiant Networks. http://www.radiantnetworks.com/.
• 35: MIT roofnet. http://www.pdos.lcs.mit.edu/roofnet/.
• 36: B. Sagdehi, V. Kanodia, A. Sabharwal, and E. Knightly. Opportunistic media access for multirate ad hoc networks. In MOBICOM, 2002.
• 37: Seattle wireless. http://www.seattlewireless.net/.
• 38: A. Snoeren. Adaptive inverse multiplexing for wide-area wireless networks. In GLOBECOM, 1999.
• 39: M. Stemm and R. H. Katz. Vertical handoffs in wireless overlay networks. ACM MONET, Summer 1998.
• 40: Jacob Strauss , Dina Katabi , Frans Kaashoek, A measurement study of available bandwidth estimation tools, Proceedings of the 3rd ACM SIGCOMM conference on Internet measurement, October 27-29, 2003, Miami Beach, FL, USA [doi>10.1145/948205.948211]
• 41: Z. Tang and J. J. Garcia-Luna-Aceves. Hop-reservation multiple access (HRMA) for ad-hoc networks. In INFOCOM, 1999.
• 42: A. Tzamaloukas and J. J. Garcia-Luna-Aceves. A receiver-initiated collision-avoidance protocol for multi-channel networks. In INFOCOM, 2001.
• 43: 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]
• 44: S.-L. Wu , C.-Y Lin , Y.-C. Tseng , J.-P. Sheu, A New Multi-Channel MAC Protocol with On-Demand Channel Assignment for Multi-Hop Mobile Ad Hoc Networks, Proceedings of the 2000 International Symposium on Parallel Architectures, Algorithms and Networks (ISPAN '00), p.232, December 07-07, 2000
• 45: S. Xu and T. Saadwi. Does the IEEE 802.11 MAC protocol work well in multihop wireless ad hoc networks. IEEE Comm, Jun 2001.

INDEX TERMS

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

General Terms:
Experimentation, Measurement, Performance

Keywords:
multi-radio, performance, routing, wireless multi-hop networks