Constructing accurate, space-efficient, wireless coverage maps for vehicular contexts

ABSTRACT

Wireless connectivity for vehicles is a fast-growing market, with a plethora of different network technologies already in use. Surveys of the numbers of IEEE 802.11b/g access points in cities point to hundreds to thousands of networks within each square kilometre, with coverage areas that are not easily predicted due to the complexities of the urban environment. In order to take advantage of the diversity in wireless networks available, we need data concerning their coverage. Methods of generating such coverage maps that are accurate, space-efficient and easy to query are not a well addressed area. In this paper, we present and evaluate, using a large corpus of real-world data, novel algorithms for processing large quantities of signal strength values into coverage maps that satisfy such requirements.

REFERENCES

• 1: Aditya Akella , Glenn Judd , Srinivasan Seshan , Peter Steenkiste, Self-management in chaotic wireless deployments, Wireless Networks, v.13 n.6, p.737-755, December 2007 [doi>10.1007/s11276-006-9852-4]
• 2: P. Bahl and V. N. Padmanabhan. RADAR: An in-building RF-based user location and tracking system. In IEEE INFOCOM, volume 2, pages 775--784, 2000.
• 3: Vladimir Bychkovsky , Bret Hull , Allen Miu , Hari Balakrishnan , Samuel Madden, A measurement study of vehicular internet access using in situ Wi-Fi networks, Proceedings of the 12th annual international conference on Mobile computing and networking, September 23-29, 2006, Los Angeles, CA, USA [doi>10.1145/1161089.1161097]
• 4: Yu-Chung Cheng , Yatin Chawathe , Anthony LaMarca , John Krumm, Accuracy characterization for metropolitan-scale Wi-Fi localization, Proceedings of the 3rd international conference on Mobile systems, applications, and services, June 06-08, 2005, Seattle, Washington [doi>10.1145/1067170.1067195]
• 5: J. J. Davies, D. N. Cottingham, and B. D. Jones. A sensor platform for sentient transportation research. In Proc. EuroSSC, LNCS 4272, pages 226--229, Oct. 2006.
• 6: J. Derksen et al. HSDPA performance and evolution. Ericsson Review, 84(3), 2006.
• 7: Herbert Freeman, Computer Processing of Line-Drawing Images, ACM Computing Surveys (CSUR), v.6 n.1, p.57-97, March 1974 [doi>10.1145/356625.356627]
• 8: Gregor Gaertner , Vinny Cahill, Understanding Link Quality in 802.11 Mobile Ad Hoc Networks, IEEE Internet Computing, v.8 n.1, p.55-60, January 2004 [doi>10.1109/MIC.2004.1260704]
• 9: Andreas Haeberlen , Eliot Flannery , Andrew M. Ladd , Algis Rudys , Dan S. Wallach , Lydia E. Kavraki, Practical robust localization over large-scale 802.11 wireless 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.1023728]
• 10: Theodoros Kamakaris , Jeffrey V. Nickerson, Connectivity Maps: Measurements and Applications, Proceedings of the Proceedings of the 38th Annual Hawaii International Conference on System Sciences, p.307, January 03-06, 2005 [doi>10.1109/HICSS.2005.162]
• 11: A. LaMarca et al. Place Lab: Device positioning using radio beacons in the wild. In Proc. PerCom, volume 3468 of LNCS, pages 116--133, 2005.
• 12: H. Larkin. Wireless signal strength topology maps in mobile adhoc networks. In Proc. Embedded and Ubiquitous Computing Conference, volume LNCS 3207, pages 538--547, 2004.
• 13: D.-S. Lee and Y.-H. Hsueh. Bandwidth-reservation scheme based on road information for next-generation cellular networks. IEEE Trans. Vehicular Technology, 53(1):243--252, Jan. 2004.
• 14: U. Lee, E. Magistretti, M. Gerla, P. Bellavista, and A. Corradi. Dissemination and harvesting of urban data using vehicular sensor platforms. Submitted to IEEE Trans. Vehicular Technology, 2008.
• 15: S. Lück, C. M. Mueller, M. Scharf, and R. Fetscher. Algorithms for hotspot coverage estimation based on field strength measurements. In Proc. IEEE VTC, pages 1086--1090, Apr. 2007.
• 16: Ratul Mahajan , John Zahorjan , Brian Zill, Understanding wifi-based connectivity from moving vehicles, Proceedings of the 7th ACM SIGCOMM conference on Internet measurement, October 24-26, 2007, San Diego, California, USA [doi>10.1145/1298306.1298351]
• 17: C. Na, J. K. Chen, and T. S. Rappaport. Measured traffic statistics and throughput of IEEE 802.11b public WLAN hotspots with three different applications. IEEE Trans. Wireless Communications, 5(11):3296--3305, Nov. 2006.
• 18: Vishnu Navda , Anand Prabhu Subramanian , Kannan Dhanasekaran , Andreas Timm-Giel , Samir Das, MobiSteer: using steerable beam directional antenna for vehicular network access, Proceedings of the 5th international conference on Mobile systems, applications and services, June 11-13, 2007, San Juan, Puerto Rico [doi>10.1145/1247660.1247684]
• 19: J. Ott and D. Kutscher. A disconnection-tolerant transport for drive-thru internet environments. In Proc. IEEE INFOCOM, Mar. 2005.
• 20: W. H. Press, S. A. Teukolsky, W. T. Vetterling, and B. P. Flannery. Numerical Recipes in C++, chapter 14, pages 655--660. Cambridge University Press, 2002.
• 21: A. Rosenfeld and E. Johnston. Angle detection on digital curves. IEEE Trans. Computers, C-22:875--878, Sep. 1973.
• 22: A. Savitzky and M. J. E. Golay. Smoothing and differentiation of data by simplified least squares procedures. Analytical Chemistry, 36:1627--1639, Jul. 1964.
• 23: Donald Shepard, A two-dimensional interpolation function for irregularly-spaced data, Proceedings of the 1968 23rd ACM national conference, p.517-524, August 27-29, 1968 [doi>10.1145/800186.810616]
• 24: M. Siebert, M. Lott, M. Schinnenburg, and S. Göbbels. Hybrid information system. In Proc. IEEE VTC, May 2004.
• 25: C. H. Teh , R. T. Chin, On the Detection of Dominant Points on Digital Curves, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.11 n.8, p.859-872, August 1989 [doi>10.1109/34.31447]
• 26: Wen-Yen Wu, A dynamic method for dominant point detection, Graphical Models, v.64 n.5, p.304-315, September 2002 [doi>10.1016/S1077-3169(02)00008-4]

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, Measurement

Keywords:
coverage maps, vehicles, wireless