Virtual trip lines for distributed privacy-preserving traffic monitoring

ABSTRACT

Automotive traffic monitoring using probe vehicles with Global Positioning System receivers promises significant improvements in cost, coverage, and accuracy. Current approaches, however, raise privacy concerns because they require participants to reveal their positions to an external traffic monitoring server. To address this challenge, we propose a system based on virtual trip lines and an associated cloaking technique. Virtual trip lines are geographic markers that indicate where vehicles should provide location updates. These markers can be placed to avoid particularly privacy sensitive locations. They also allow aggregating and cloaking several location updates based on trip line identifiers, without knowing the actual geographic locations of these trip lines. Thus they facilitate the design of a distributed architecture, where no single entity has a complete knowledge of probe identities and fine-grained location information. We have implemented the system with GPS smartphone clients and conducted a controlled experiment with 20 phone-equipped drivers circling a highway segment. Results show that even with this low number of probe vehicles, travel time estimates can be provided with less than 15% error, and applying the cloaking techniques reduces travel time estimation accuracy by less than 5% compared to a standard periodic sampling approach.

REFERENCES

• 1: http://bard.wr.usgs.gov/.
• 2: http://jcp.org/en/jsr/detail?id=179/.
• 3: http://pems.eecs.berkeley.edu/public/.
• 4: http://www.fcc.gov/bureaus/wireless/.
• 5: http://www.paramics-online.com.
• 6: http://www.privacyrights.org/ar/chrondatabreaches.htm.
• 7: TeleNav. http://www.telenav.net/, 2004.
• 8: Inrix. http://www.inrix.com/, 2006.
• 9: Intellione. http://www.intellione.com/, 2006.
• 10: Dakshi Agrawal , Charu C. Aggarwal, On the design and quantification of privacy preserving data mining algorithms, Proceedings of the twentieth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.247-255, May 2001, Santa Barbara, California, United States [doi>10.1145/375551.375602]
• 11: Rakesh Agrawal , Ramakrishnan Srikant, Privacy-preserving data mining, Proceedings of the 2000 ACM SIGMOD international conference on Management of data, p.439-450, May 15-18, 2000, Dallas, Texas, United States
• 12: M. Annavaram, Q. Jacobson, and J. P. Shen. Hangout: A privacy preserving social networking application. In Proc. of International Workshop on Mobile Devices and Urban Sensing (to appear), St. Louis, USA, 2008.
• 13: X. Ban, R. Herring, J. Margulici, and A. Bayen. Optimal sensor placement for freeway travel time estimation. Interim technical report (available at http://www.calccit.org/resources/2008-pdf/OptSenDP_InterimReport_2008.pdf, California Center for Innovative Transportation, 2008. Revised version to be submitted to the 18th International Symposium on Traffic and Transportation Theory (ISTTT).
• 14: Alastair R. Beresford , Frank Stajano, Mix Zones: User Privacy in Location-aware Services, Proceedings of the Second IEEE Annual Conference on Pervasive Computing and Communications Workshops, p.127, March 14-17, 2004
• 15: C. Bettini, X. SeanWang, and S. Jajodia. Protecting privacy against location-based personal identification,. In 2nd VLDB Workshop SDM, 2005.
• 16: D. Boneh, X. Boyen, and H. Shacham. Short group signatures. In CRYPTO 2004, volume 3152 of Lecture Notes in Computer Science, pages 41--55. Springer, 2004.
• 17: R. Cayford and T. Johnson. Operational parameters affecting the use of anonymous cell phone tracking for generating traffic information. Transportation Research Board 82nd Annual Meeting, 1(3):03--3865, 2003.
• 18: D. Chaum and E. V. Heyst. Group signatures. In Advances in Cryptology-EUROCRYPT '91, volume 547 of Lecture Notes in Computer Science, pages 257--265. Springer, 1991.
• 19: L. Chu, S. Oh, and W. Recker. Adaptive Kalman filter based freeway travel time estimation. In 84th TRB Annual Meeting, Washington D.C., January 9-13 2005. Transportation Research Board.
• 20: B. Coifman. Using dual loop speed traps to identify detector errors. Transportation Research Board, Transportation Research Record 1683(-1):47--58, 1999.
• 21: B. Coifman. Improved velocity estimation using single loop detectors. Transportation Research Part A, 35(10):863--880, 2001.
• 22: X. Dai, M. Ferman, and R. Roesser. A simulation evaluation of a real-time traffic information system using probe vehicles. In Proceedings of the IEEE Intelligent Transportation Systems, pages 475--480, 2003.
• 23: Roger Dingledine , Nick Mathewson , Paul Syverson, Tor: the second-generation onion router, Proceedings of the 13th conference on USENIX Security Symposium, p.21-21, August 09-13, 2004, San Diego, CA
• 24: A.-M. Elliott. Tomtom announces tomtom high definition traffic. http://www.pocket-lint.co.uk/news/news.phtml/11248/12272/TomTom-High-Definition-Traffic-announced.phtml, Nov 2007.
• 25: M. Ferman, D. Blumenfeld, and X. Dai. A simple analytical model of a probe-based traffic information system. In Proceedings of the IEEE Intelligent Transportation Systems, pages 263--268, 2003.
• 26: Avigdor Gal , Vijayalakshmi Atluri, An authorization model for temporal data, Proceedings of the 7th ACM conference on Computer and communications security, p.144-153, November 01-04, 2000, Athens, Greece [doi>10.1145/352600.352621]
• 27: Bugra Gedik , Ling Liu, Location Privacy in Mobile Systems: A Personalized Anonymization Model, Proceedings of the 25th IEEE International Conference on Distributed Computing Systems, p.620-629, June 06-10, 2005 [doi>10.1109/ICDCS.2005.48]
• 28: David Goldschlag , Michael Reed , Paul Syverson, Onion routing, Communications of the ACM, v.42 n.2, p.39-41, Feb. 1999 [doi>10.1145/293411.293443]
• 29: David Goldschlag , Michael Reed , Paul Syverson, Onion routing, Communications of the ACM, v.42 n.2, p.39-41, Feb. 1999 [doi>10.1145/293411.293443]
• 30: Marco Gruteser , Dirk Grunwald, Anonymous Usage of Location-Based Services Through Spatial and Temporal Cloaking, Proceedings of the 1st international conference on Mobile systems, applications and services, p.31-42, May 05-08, 2003, San Francisco, California [doi>10.1145/1066116.1189037]
• 31: M. Gruteser and B. Hoh. On the anonymity of periodic location samples. In Proceedings of the Second International Conference on Security in Pervasive Computing, 2005.
• 32: F. Hall and B. Persaud. Evaluation of speed estimates made with single-detector data from freeway traffic management systems. Transportation Research Board, Transportation Research Record 1232:9--16, 1989.
• 33: U. Hengartner. Hiding location information from location-based services. In Proc. of International Workshop on Privacy-Aware Location-based Mobile Services (PALMS), Mannheim, Germany, 2007.
• 34: J. Herrera and A. M. Bayen. Traffic flow reconstruction using mobile sensors and loop detector data. In 87th TRB Annual Meeting, Washington D.C., January 12-16 2008. Transportation Research Board.
• 35: Baik Hoh , Marco Gruteser, Protecting Location Privacy Through Path Confusion, Proceedings of the First International Conference on Security and Privacy for Emerging Areas in Communications Networks, p.194-205, September 05-09, 2005 [doi>10.1109/SECURECOMM.2005.33]
• 36: Baik Hoh , Marco Gruteser , Hui Xiong , Ansaf Alrabady, Enhancing Security and Privacy in Traffic-Monitoring Systems, IEEE Pervasive Computing, v.5 n.4, p.38-46, October 2006 [doi>10.1109/MPRV.2006.69]
• 37: Baik Hoh , Marco Gruteser , Hui Xiong , Ansaf Alrabady, Preserving privacy in gps traces via uncertainty-aware path cloaking, Proceedings of the 14th ACM conference on Computer and communications security, October 28-31, 2007, Alexandria, Virginia, USA [doi>10.1145/1315245.1315266]
• 38: Bret Hull , Vladimir Bychkovsky , Yang Zhang , Kevin Chen , Michel Goraczko , Allen Miu , Eugene Shih , Hari Balakrishnan , Samuel Madden, CarTel: a distributed mobile sensor computing system, Proceedings of the 4th international conference on Embedded networked sensor systems, October 31-November 03, 2006, Boulder, Colorado, USA [doi>10.1145/1182807.1182821]
• 39: Z. Jia, C. Chen, B. Coifman, and P. Varaiya. The PeMS algorithms for accurate, real-time estimates of g-factors and speeds from single-loop detectors. IEEE Control Systems Magazine, 21(4):26--33, 2001.
• 40: Panos Kalnis , Gabriel Ghinita , Kyriakos Mouratidis , Dimitris Papadias, Preventing Location-Based Identity Inference in Anonymous Spatial Queries, IEEE Transactions on Knowledge and Data Engineering, v.19 n.12, p.1719-1733, December 2007 [doi>10.1109/TKDE.2007.190662]
• 41: H. Kargupta, S. Datta, Q. Wang, and K. Sivakumar. Random data perturbation techniques and privacy preserving data mining. In IEEE ICDM. IEEE Press, 2003.
• 42: L. Klein, M. Mills, and D. Gibson. Traffic Detector Handbook, volume 1 and 2. Third edition, October 2006.
• 43: Tadayoshi Kohno , Andre Broido , K. C. Claffy, Remote Physical Device Fingerprinting, Proceedings of the 2005 IEEE Symposium on Security and Privacy, p.211-225, May 08-11, 2005 [doi>10.1109/SP.2005.18]
• 44: J. Krumm. Inference attacks on location tracks. In Proceedings of the 5th International Conference on Pervasive Computing (Pervasive 2007), May 2007.
• 45: Mingyan Li , Krishna Sampigethaya , Leping Huang , Radha Poovendran, Swing & swap: user-centric approaches towards maximizing location privacy, Proceedings of the 5th ACM workshop on Privacy in electronic society, October 30-30, 2006, Alexandria, Virginia, USA [doi>10.1145/1179601.1179605]
• 46: Ashwin Machanavajjhala , Johannes Gehrke , Daniel Kifer , Muthuramakrishnan Venkitasubramaniam, \ell -Diversity: Privacy Beyond \kappa -Anonymity, Proceedings of the 22nd International Conference on Data Engineering, p.24, April 03-07, 2006 [doi>10.1109/ICDE.2006.1]
• 47: B. Mikhalkin, H. Payne, and L. Isaksen. Estimation of speed from presence detectors. Highway Research Record, 388:73--83, 1972.
• 48: Mohamed F. Mokbel , Chi-Yin Chow , Walid G. Aref, The new Casper: query processing for location services without compromising privacy, Proceedings of the 32nd international conference on Very large data bases, September 12-15, 2006, Seoul, Korea
• 49: C. Nanthawichit, T. Nakatsuji, and H. Suzuki. Application of probe-vehicle data for real-time traffic-state estimation and short-term travel-time prediction on a freeway. Transportation Research Record, 1855:49--59, 2003.
• 50: H. Payne and S. Thompson. Malfunction detection and data repair for induction-loop sensors using i-880 data base. Transportation Research Board, Transportation Research Record 1570(-1):191--201, 1997.
• 51: A. Pushkar, F. Hall, and J. Acha-Daza. Estimation of speeds from single-loop freeway flow and occupancy detectors using cusp catastrophy theory model. Transportation Research Board, Transportation Research Record 1457:149--157, 1994.
• 52: D. Reid. An algorithm for tracking multiple targets. IEEE Transactions on Automatic Control, 24(6):843--854, Dec 1979.
• 53: P. Samarati and L. Sweeney. Protecting privacy when disclosing information: k-anonymity and its enforcement through generalization and suppression. In Proceedings of IEEE Symposium on Research in Security and Privacy, 1998.
• 54: K. Sampigethaya, L. Huang, M. Li, R. Poovendran, K. Matsuura, and K. Sezaki. Caravan: Providing location privacy for vanet. In 3rd workshop on Embedded Security in Cars (ESCAR2005), 2005.
• 55: B. Smith, H. Zhang, M. Fontaine, and M. Green. Cell phone probes as an ATMS tool. Research Report UVACTS-15-5-79, June 2003.
• 56: Latanya Sweeney, Achieving k-anonymity privacy protection using generalization and suppression, International Journal of Uncertainty, Fuzziness and Knowledge-Based Systems, v.10 n.5, p.571-588, October 2002 [doi>10.1142/S021848850200165X]
• 57: U. o. M. Transportation Studies Center. Final Evaluation Report for the CAPITAL-ITS Operational Test and Demonstration Program. Transportation Studies Center, University of Maryland, 1997.
• 58: Jungkeun Yoon , Brian Noble , Mingyan Liu, Surface street traffic estimation, Proceedings of the 5th international conference on Mobile systems, applications and services, June 11-13, 2007, San Juan, Puerto Rico [doi>10.1145/1247660.1247686]
• 59: Mahmoud Youssef , Vijayalakshmi Atluri , Nabil R. Adam, Preserving mobile customer privacy: an access control system for moving objects and customer profiles, Proceedings of the 6th international conference on Mobile data management, May 09-13, 2005, Ayia Napa, Cyprus [doi>10.1145/1071246.1071257]
• 60: G. Zhong, I. Goldberg, and U. Hengartner. Louis, lester and pierre: Three protocols for location privacy. In Privacy Enhancing Technologies, pages 62--76, 2007.

INDEX TERMS

Primary Classification:
  K. Computing Milieux
  K.4 COMPUTERS AND SOCIETY
      K.4.1 Public Policy Issues
          Subjects: Privacy

Additional Classification:
  K. Computing Milieux
  K.6 MANAGEMENT OF COMPUTING AND INFORMATION SYSTEMS
      K.6.5 Security and Protection (D.4.6, K.4.2)

General Terms:
Algorithms, Design, Experimentation, Security

Keywords:
data integrity, gps, privacy, traffic