Assessment of urban-scale wireless networks with a small number of measurements

ABSTRACT

In order to evaluate, improve, or expand a deployed, city-wide wireless mesh network, it is necessary to assess the network's spatial performance. In this paper, we present a general framework to accurately predict a network's well-served area, termed the metric region, via a small number of measurements. Assessment of deployed networks must address two key issues: non-uniform physical-layer propagation and high spatial variance in performance. Addressing non-uniformity, our framework estimates a mesh node's metric region via a data-driven sectorization of the region. We find each sector's boundary (radius) with a two-stage process of estimation and then measurement-driven "push-pull" refinement of the estimated boundary. To address high spatial variation, our coverage estimation couples signal strength measurements with terrain information from publicly available digital maps to estimate propagation characteristics between a wireless node and the client's location. To limit measurements and yield connected metric regions, we consider performance metrics (such as signal strength) to be monotonic with distance from the wireless node within each sector. We show that despite measured violations in coverage monotonicity, we obtain high accuracy with this assumption. We validate our estimation and refinement framework with measurements from 30,000 client locations obtained in each of two currently operational mesh networks, GoogleWiFi and TFA. We study three illustrative metrics: coverage, modulation rate, and redundancy, and find that to achieve a given accuracy, our framework requires two to five times fewer measurements than grid sampling strategies. Finally, we use the framework to evaluate the two deployments and study the average size and location of their coverage holes as well as the impact of client association policies on load-balancing.

REFERENCES

• 1: Andres Arjona , Sami Takala, The Google Muni Wifi Network--Can it Compete with Cellular Voice?, Proceedings of the The Third Advanced International Conference on Telecommunications, p.11, May 13-19, 2007 [doi>10.1109/AICT.2007.41]
• 2: P. Bernardin, M. F. Yee, and T. Ellis. Cell radius inaccuracy: a new measure of coverage reliability. IEEE Transactions on Vehicular Technology, 47(4):1215--1226, November 1998.
• 3: Joseph Camp , Joshua Robinson , Christopher Steger , Edward Knightly, Measurement driven deployment of a two-tier urban mesh access network, Proceedings of the 4th international conference on Mobile systems, applications and services, June 19-22, 2006, Uppsala, Sweden [doi>10.1145/1134680.1134691]
• 4: S. Cherry. Wi-Fi nodes to talk amongst themselves. IEEE Spectrum Magazine, July 2006.
• 5: V. Erceg, L.J. Greenstein, S. Tjandra, S.R. Parkoff, A. Gupta, B. Kulic, A. Julius, and R. Jastrzab. An empirically-based path loss model for wireless channels in suburban environments. Proceedings of IEEE GLOBECOM, November 1998.
• 6: Anastasios Giannoulis , Marco Fiore , Edward W. Knightly, Supporting vehicular mobility in urban multi-hop wireless networks, Proceeding of the 6th international conference on Mobile systems, applications, and services, June 17-20, 2008, Breckenridge, CO, USA [doi>10.1145/1378600.1378608]
• 7: A. Goldsmith and L. Greenstein. A measurement-based model for predicting coverage areas of urban microcells. IEEE Journal on Selected Areas in Communications, 11(7):1013--1023, September 1993.
• 8: M. Iskander and Z. Yun. Propagation prediction models for wireless communication systems. IEEE Transactions on Microwave Theory and Techniques, 50(3):662--673, Mar 2002.
• 9: Xiaoying Jin , Curt H. Davis, Automated building extraction from high-resolution satellite imagery in urban areas using structural, contextual, and spectral information, EURASIP Journal on Applied Signal Processing, v.2005 n.1, p.2196-2206, 1 January 2005 [doi>10.1155/ASP.2005.2196]
• 10: M. Kamenetsky and M. Unbehaun. Coverage planning for outdoor wireless LAN systems. In International Zurich Seminar on Broadband Communications, Zurich, Switz., February 2002.
• 11: S.-C. Kim, B. J. Guarino Jr., T. M. Willis III, V. Erceg, S. J. Fortune, R. A. Valenzuela, L. W. Thomas, J. Ling, and J. D. Moore. Radio propagation measurements and prediction using three-dimensional ray tracing in urban environments at 908 MHz and 1.9 GHz. IEEE Transactions on Vehicular Technology, 48(3):931--946, May 1999.
• 12: David Kotz , Kobby Essien, Analysis of a campus-wide wireless network, Wireless Networks, v.11 n.1-2, p.115-133, January 2005 [doi>10.1007/s11276-004-4750-0]
• 13: 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]
• 14: M. Lott and I. Forkel. A multi-wall-and-floor model for indoor radio propagation. Proceedings of IEEE Vehicular Technology Conference, 1:464--468, 2001.
• 15: K. Manoj, P. Bernardin, and L. Tamil. Coverage prediction for cellular networks from limited signal strength measurements. The Ninth IEEE International Symposium on Personal, Indoor and Mobile Radio Communications, 3:1147--1151, September 1998.
• 16: T. Okumura, E. Ohmori, and K. Fukuda. Field strength and its variability in VHF and UHF land mobile service. Review Electrical Communication Laboratory, 16(9-10):825--873, 1968.
• 17: Christos H. Papadimitriou , Kenneth Steiglitz, Combinatorial optimization: algorithms and complexity, Prentice-Hall, Inc., Upper Saddle River, NJ, 1982
• 18: R. Pattuelli and V. Zingarelli. Precision of the estimation of area coverage by planning tools in cellular systems. IEEE Personal Communications, 7(3):50--53, Jun 2000.
• 19: Theodore S. Rappaport, Wireless Communications: Principles and Practice, IEEE Press, Piscataway, NJ, 1996
• 20: T. Rautiainen, G. Wolfle, and R. Hoppe. Verifying path loss and delay spread predictions of a 3d ray tracing propagation model in urban environment. Proceedings of IEEE Vehicular Technology Conference, 4:2470--2474, 2002.
• 21: S. Zvanovec, P. Pechac, and M. Klepal. Wireless LAN networks design: Site survey or propagation modeling? Radio Engineering Prague, 12(4):42--49, 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, coverage, deployment, measurement assessment, mesh networks, signal strength, wireless