Architecture and evaluation of an unplanned 802.11b mesh network

ABSTRACT

This paper evaluates the ability of a wireless mesh architecture to provide high performance Internet access while demanding little deployment planning or operational management. The architecture considered in this paper has unplanned node placement (rather than planned topology), omni-directional antennas (rather than directional links), and multi-hop routing (rather than single-hop base stations). These design decisions contribute to ease of deployment, an important requirement for community wireless networks. However, this architecture carries the risk that lack of planning might render the network's performance unusably low. For example, it might be necessary to place nodes carefully to ensure connectivity; the omni-directional antennas might provide uselessly short radio ranges; or the inefficiency of multi-hop forwarding might leave some users effectively disconnected.The paper evaluates this unplanned mesh architecture with a case study of the Roofnet 802.11b mesh network. Roofnet consists of 37 nodes spread over four square kilometers of an urban area. The network provides users with usable performance despite lack of planning: the average inter-node throughput is 627 kbits/second, even though the average route has three hops.The paper evaluates multiple aspects of the architecture: the effect of node density on connectivity and throughput; the characteristics of the links that the routing protocol elects to use; the usefulness of the highly connected mesh afforded by omni-directional antennas for robustness and throughput; and the potential performance of a single-hop network using the same nodes as Roofnet.

REFERENCES

• 1: Champaign-Urbana Community Wireless Network CUWiN. http://www.curwireless.net/.
• 2: Locust World.org. http://www.locustworld.com/.
• 3: meshcube.org. http://www.meshcube.org/.
• 4: NYCWireless. http://www.nycwireless.com.
• 5: Seattle Wireless. http://www.seattlewireless.net/.
• 6: Tropos networks technology whitepaper, May 2003. http://www.troposnetworks.com/.
• 7: 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
• 8: Pravin Bhagwat, Bhaskaran Raman, and Dheeraj Sanghi. Turning 802.11 inside-out. In Second Workshop on Hot Topics in Networks (HotNets-II), November 2003.
• 9: John Bicket. Bit-rate selection in wireless networks. Master's thesis, Massachusetts Institute of Technology, February 2005.
• 10: Josh Broch , David A. Maltz , David B. Johnson , Yih-Chun Hu , Jorjeta Jetcheva, A performance comparison of multi-hop wireless ad hoc network routing protocols, Proceedings of the 4th annual ACM/IEEE international conference on Mobile computing and networking, p.85-97, October 25-30, 1998, Dallas, Texas, United States [doi>10.1145/288235.288256]
• 11: 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]
• 12: Samir Das, Charles Perkins, and Elizabeth Royer. Performance comparison of two on-demand routing protocols for ad hoc networks. In Proc. IEEE Infocom, pages 3--12, March 2000.
• 13: 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]
• 14: 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
• 15: 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]
• 16: David Eckhardt , Peter Steenkiste, Measurement and analysis of the error characteristics of an in-building wireless network, ACM SIGCOMM Computer Communication Review, v.26 n.4, p.243-254, Oct. 1996
• 17: Zhenghua Fu, Petros Zerfos, Haiyun Luo, Songwu Lu, Lixia Zhang, and Mario Gerla. The impact of multihop wireless channel on TCP throughput and loss. In IEEE INFOCOM'03, March 2003.
• 18: 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. Technical report UCLA/CSD-TR 02-0013, UCLA CS Department, 2002.
• 19: Robert S. Gray , David Kotz , Calvin Newport , Nikita Dubrovsky , Aaron Fiske , Jason Liu , Christopher Masone , Susan McGrath , Yougu Yuan, Outdoor experimental comparison of four ad hoc routing algorithms, Proceedings of the 7th ACM international symposium on Modeling, analysis and simulation of wireless and mobile systems, October 04-06, 2004, Venice, Italy [doi>10.1145/1023663.1023703]
• 20: David B. Johnson. Routing in ad hoc networks of mobile hosts. In Proc. of the IEEE Workshop on Mobile Computing Systems and Applications, pages 158--163, December 1994.
• 21: John Jubin and Janet D. Tornow. The DARPA packet radio network protocols. Proceedings of the IEEE, 75(1), January 1987.
• 22: Eddie Kohler , Robert Morris , Benjie Chen , John Jannotti , M. Frans Kaashoek, The click modular router, ACM Transactions on Computer Systems (TOCS), v.18 n.3, p.263-297, Aug. 2000 [doi>10.1145/354871.354874]
• 23: David Kotz , Calvin Newport , Robert S. Gray , Jason Liu , Yougu Yuan , Chip Elliott, Experimental evaluation of wireless simulation assumptions, Proceedings of the 7th ACM international symposium on Modeling, analysis and simulation of wireless and mobile systems, October 04-06, 2004, Venice, Italy [doi>10.1145/1023663.1023679]
• 24: 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]
• 25: Henrik Lundgren , Erik Nordströ , Christian Tschudin, Coping with communication gray zones in IEEE 802.11b based ad hoc networks, Proceedings of the 5th ACM international workshop on Wireless mobile multimedia, September 28-28, 2002, Atlanta, Georgia, USA [doi>10.1145/570790.570799]
• 26: David A. Maltz, Josh Broch, and David B. Johnson. Experiences designing and building a multi-hop wireless ad hoc network testbed. CMU-CS-99-116, Carnegie Mellon University, School of Computer Science, March 1999.
• 27: David A. Maltz, Josh Broch, and David B. Johnson. Quantitative lessons from a full-scale multi-hop wireless ad hoc network testbed. In Proceedings of the IEEE Wireless Communications and Networking Conference, September 2000.
• 28: Eric Nordstrom. APE - a large scale ad hoc network testbed for reproducible performance tests. Master's thesis, Uppsala University, June 2002.
• 29: Bhaskaran Raman and Kameswari Chebrolu. Revisiting MAC design for an 802.11-based mesh network. In Third Workshop on Hot Topics in Networks (HotNets-III), November 2004.
• 30: Mike Ritter , Robert J. Friday , Rodrigo Garces , Weill San Filippo , Cuong-Thinh Nguyen, Mobile connectivity protocols and throughput measurements in the Ricochet Microcellular data network (MCDN) system, Proceedings of the 7th annual international conference on Mobile computing and networking, p.322-331, July 2001, Rome, Italy [doi>10.1145/381677.381707]
• 31: Rudi van Drunen, Jasper Koolhaas, Huub Schuurmans, and Marten Vijn. Building a wireless community network in the Netherlands. In USENIX/Freenix Conference, June 2003.
• 32: 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]
• 33: Kaixin Xu, Mario Gerla, and Sang Bae. Effectiveness of RTS/CTS handshake in IEEE 802.11 based ad hoc networks. Ad Hoc Network Journal, 1(1), July 2003.
• 34: Jasmeet Chhabra , Brent Elliott, Real-World Experiences with an Interactive Ad Hoc Sensor Network, Proceedings of the 2002 International Conference on Parallel Processing Workshops, p.143, August 18-21, 2002

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.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.2 Network Protocols
          Subjects: Routing protocols

General Terms:
Design, Experimentation, Measurement, Performance

Keywords:
Ad hoc networks, mesh networks, multi-hop wireless networks, route metrics, wireless routing