HOVER: hybrid on-demand distance vector routing for wireless mesh networks

ABSTRACT

Hybrid Wireless Mesh Networks are a combination of mobile ad hoc networks and infrastructure wireless mesh networks, consisting of two types of nodes: mobile Mesh Clients and static Mesh Routers. Mesh Routers, which are typically equipped with multiple radios, provide a wireless multi-hop backhaul. The resource constrained Mesh Clients also participate in the routing and forwarding of packets to extend the reach of the network. Current ad-hoc routing protocols have been designed for relatively homogeneous networks and do not perform well in Hybrid Wireless Mesh Networks. In this paper, we present HOVER (Hybrid On-demand Distance Vector Routing), a modified version of the AODV routing protocol, that achieves significant performance improvements in terms of packet delivery and latency in Hybrid Wireless Mesh Networks. Our modifications include a link quality estimation technique based on HELLO packets, a new routing metric that differentiates between node types, and a channel selection scheme that minimises interference in multi-radio mesh networks. We present an evaluation of our improvements via extensive simulations. We further show the practicality of the protocol through prototype implementation and provide measurement results obtained from our test-bed.

REFERENCES

• 1: Akyildiz, I. F. & Wang, X. (2005), 'A Survey on Wireless Mesh Networks', IEEE Communications Magazine 43(9), S23--S30.
• 2: Anderson, J. K. & Youell, N. (2002), 'A Closer Look at WLAN Throughput and Performance', Bechtel Telecommunications Technical Journal 1(1), 86--94.
• 3: Chakeres, I. & Belding-Royer, E. (2002), The utility of hello messages for determining link connectivity, in 'Proceedings of the 5th International Symposium on Wireless Personal Multimedia Communications', Vol. 2, pp. 504--508.
• 4: Chandra, R. & Bahl, P. (2004), MultiNet: Connecting to Multiple IEEE 802.11 Networks using a Single Wireless Card, in 'Proceedings of the Twenty-third Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM)', Vol. 2, IEEE Press, pp. 882--893.
• 5: Douglas S. J. De Couto , Daniel Aguayo , John Bicket , Robert Morris, A high-throughput path metric for multi-hop wireless routing, Wireless Networks, v.11 n.4, p.419-434, July 2005 [doi>10.1007/s11276-005-1766-z]
• 6: 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]
• 7: Gupta, P. & Kumar, P. R. (2000), 'The Capacity of Wireless Networks', IEEE Transactions on Information Theory 46(2), 388--404.
• 8: Johnson, D. B., Maltz, D. A. & Hu, Y. (2003), 'The Dynamic Source Routing Protocol for Mobile Ad hoc Networks (DSR)', IETF MANET, Internet Draft.
• 9: Ko, B. J., Padhye, J., Misra, V. & Rubenstein, D. (2005), Distributed Channel Assignment in Multi-radio 802.11 Mesh Networks', Technical report, Columbia University.
• 10: Pradeep Kyasanur , Nitin H. Vaidya, Routing and link-layer protocols for multi-channel multi-interface ad hoc wireless networks, ACM SIGMOBILE Mobile Computing and Communications Review, v.10 n.1, p.31-43, January 2006 [doi>10.1145/1119759.1119762]
• 11: NS (1989), 'The Network Simulator', http://www.isi.edu/nsnam/ns/.
• 12: 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
• 13: 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
• 14: C. Perkins , E. Belding-Royer , S. Das, Ad hoc On-Demand Distance Vector (AODV) Routing, RFC Editor, 2003
• 15: Asad Amir Pirzada , Chris McDonald, Establishing trust in pure ad-hoc networks, Proceedings of the 27th Australasian conference on Computer science, p.47-54, January 01, 2004, Dunedin, New Zealand
• 16: Asad Amir Pirzada , Chris McDonald , Amitava Datta, Performance Comparison of Trust-Based Reactive Routing Protocols, IEEE Transactions on Mobile Computing, v.5 n.6, p.695-710, June 2006 [doi>10.1109/TMC.2006.83]
• 17: Asad Amir Pirzada , Marius Portmann , Jadwiga Indulska, Evaluation of multi-radio extensions to AODV for wireless mesh networks, Proceedings of the 4th ACM international workshop on Mobility management and wireless access, October 02-02, 2006, Terromolinos, Spain [doi>10.1145/1164783.1164791]
• 18: Asad Amir Pirzada , Marius Portmann , Jadwiga Indulska, Hybrid mesh ad-hoc on-demand distance vector routing protocol, Proceedings of the thirtieth Australasian conference on Computer science, p.49-58, January 30-February 02, 2007, Ballarat, Victoria, Australia
• 19: Ramachandran, K., Buddhikot, M., Chandranmenon, G., Miller, S., Belding-Royer, E. & Almeroth, K. (2005), On the Design and Implementation of Infrastructure Mesh Networks, in 'Proceedings of the IEEE Workshop on Wireless Mesh Networks (WiMesh)', IEEE Press, pp. 4--15.
• 20: Bhaskaran Raman , Kameswari Chebrolu, Design and evaluation of a new MAC protocol for long-distance 802.11 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.1080847]
• 21: Raniwala, A. & Chiueh, T. C. (2005), Architecture and Algorithms for an IEEE 802.11-based Multi-Channel Wireless Mesh Network, in 'Proceedings of the 24th Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM)', Vol. 3, IEEE Press, pp. 2223--2234.
• 22: Yang, Y., Wang, J. & Kravets, R. (2005), Designing Routing Metrics for Mesh Networks, in 'Proceedings of the IEEE Workshop on Wireless Mesh Networks (WiMesh)', IEEE Press.

INDEX TERMS

Keywords:
mesh, multi-radio, network, routing, wireless