Measurement driven deployment of a two-tier urban mesh access network

ABSTRACT

Multihop wireless mesh networks can provide Internet access over a wide area with minimal infrastructure expenditure. In this work, we present a measurement driven deployment strategy and a data-driven model to study the impact of design and topology decisions on network-wide performance and cost. We perform extensive measurements in a two-tier urban scenario to characterize the propagation environment and correlate received signal strength with application layer throughput. We find that well-known estimates for pathloss produce either heavily overprovisioned networks resulting in an order of magnitude increase in cost for high pathloss estimates or completely disconnected networks for low pathloss estimates. Modeling throughput with wireless interface manufacturer specifications similarly results in severely underprovisioned networks. Further, we measure competing, multihop flow traffic matrices to empirically define achievable throughputs of fully backlogged, rate limited, and web-emulated traffic. We find that while fully backlogged flows produce starving nodes, rate-controlling flows to a fixed value yields fairness and high aggregate throughput. Likewise, transmission gaps occurring in statistically multiplexed web traffic, even under high offered load, remove starvation and yield high performance. In comparison, we find that well-known noncompeting flow models for mesh networks over-estimate network-wide throughput by a factor of 2. Finally, our placement study shows that a regular grid topology achieves up to 50 percent greater throughput than random node placement.

REFERENCES

• 1: R. Karrer, A. Sabharwal, and E. Knightly, "Enabling large-scale wireless broadband: the case for TAPs," in Proceedings of HotNets-II, Cambridge, MA, Nov. 2003.
• 2: J. Camp, E. Knightly, and W. Reed, "Developing and deploying multihop wireless networks for low-income communities," in Proceedings of Digital Communities, Napoli, Italy, June 2005.
• 3: Theodore S. Rappaport, Wireless Communications: Principles and Practice, IEEE Press, Piscataway, NJ, 1996
• 4: Gordon L. Stüber, Principles of mobile communication (2nd ed.), Kluwer Academic Publishers, Norwell, MA, 2001
• 5: D. Neff, "Wireless Philadelphia business plan: Wireless broadband as the foundation for a digital city," 9 February 2005.
• 6: John Bicket , Daniel Aguayo , Sanjit Biswas , Robert Morris, Architecture and evaluation of an unplanned 802.11b mesh network, Proceedings of the 11th annual international conference on Mobile computing and networking, August 28-September 02, 2005, Cologne, Germany [doi>10.1145/1080829.1080833]
• 7: C. Steger, P. Radosavljevic, and J. Frantz, "Performance of IEEE 802.11b wireless LAN in an emulated mobile channel," in Proceedings of IEEE Vehicular Technology Conference, vol. 2, April 2003, pp. 1479--1483.
• 8: G. Woodward, I. Oppermann, and J. Talvitie, "Outdoor-indoor temporal and spatial wideband channel model for ISM bands," in Proceedings of IEEE Vehicular Technology Conference, vol. 1, Fall 1999, pp. 136--140.
• 9: 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
• 10: Violeta Gambiroza , Bahareh Sadeghi , Edward W. Knightly, End-to-end performance and fairness in multihop wireless backhaul 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.1023749]
• 11: S. Ranjan, R. Karrer, and E. W. Knightly, "Wide area redirection of dynamic content in internet data centers," in Proceedings of IEEE INFOCOM '04, March 2004.
• 12: H. Zepernick and T. Wysocki, "Multipath channel parameters for the indoor radio at 2.4 GHz ISM band," in Proceedings of IEEE Vehicular Technology Conference, vol. 1, Spring 1999, pp. 190--193.
• 13: C. Huang and R. Khayata, "Delay spreads and channel dynamics measurements at ISM bands," in Proceedings of IEEE International Conference on Communications, vol. 3, June 1992, pp. 1222--1226.
• 14: M. Yarvis, K. Papagiannaki, and W. S. Connor, "Characterization of 802.11 wireless networks in the home," in Proceedings of Wireless Network Measurements (WiNMee), Riva del Garda, Italy, April 2005.
• 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: D. Johnson, "Routing in ad hoc networks of mobile hosts," in Proceedings of the IEEE Workshop on Mobile Computing Systems and Applications, December 1994, pp. 158--163.
• 17: D. Maltz, J. Broch, and D. Johnson, "Quantitive lessons from a full-scale multi-hop wireless ad hoc network testbed," in Proceedings of the IEEE Wireless Communications and Networking Conference, September 2000.
• 18: P. Gupta and P. R. Kumar, "The capacity of wireless networks," IEEE Transactions on Information Theory, vol. 46, no. 2, Mar. 2000.
• 19: Z. F. Li, S. Nandi, and A. K. Gupta, "Study of IEEE 802.11 fairness and its interaction with routing mechanism," in IFIP MWCN 2003, Singapore, May 2003.
• 20: Xiao Long Huang , Brahim Bensaou, On max-min fairness and scheduling in wireless ad-hoc networks: analytical framework and implementation, Proceedings of the 2nd ACM international symposium on Mobile ad hoc networking & computing, October 04-05, 2001, Long Beach, CA, USA [doi>10.1145/501445.501447]
• 21: Thyagarajan Nandagopal , Tae-Eun Kim , Xia Gao , Vaduvur Bharghavan, Achieving MAC layer fairness in wireless packet networks, Proceedings of the 6th annual international conference on Mobile computing and networking, p.87-98, August 06-11, 2000, Boston, Massachusetts, United States [doi>10.1145/345910.345925]
• 22: Ranveer Chandra , Lili Qiu , Kamal Jain , Mohammad Mahdian, Optimizing the Placement of Internet TAPs in Wireless Neighborhood Networks, Proceedings of the Network Protocols, 12th IEEE International Conference on (ICNP'04), p.271-282, October 05-08, 2004
• 23: B. Liu, Z. Liu, and D. Towsley, "On the capacity of hybrid wireless networks," in Proceedings of IEEE Infocom, San Fransisco, CA, April 2003.

INDEX TERMS

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

General Terms:
Algorithms, Design, Experimentation, Measurement, Performance, Reliability

Keywords:
access network, deployment, fairness, measurement-driven, mesh, pathloss, placement, two-tier architecture, urban, wireless