research-article

Virtual trip lines for distributed privacy-preserving traffic monitoring

Authors:

Marco Gruteser,

Juan-Carlos Herrera,

Alexandre M. Bayen,

Murali Annavaram,

Quinn JacobsonAuthors Info & Claims

MobiSys '08: Proceedings of the 6th international conference on Mobile systems, applications, and services

Pages 15 - 28

https://doi.org/10.1145/1378600.1378604

Published: 17 June 2008 Publication History

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]

D. Agrawal and C. C. Aggarwal. On the design and quantification of privacy preserving data mining algorithms. In Symposium on Principles of Database Systems, 2001.

Digital Library

[11]

R. Agrawal and R. Srikant. Privacy-preserving data mining. In Proc. of the ACM SIGMOD Conference on Management of Data, pages 439--450. ACM Press, May 2000.

Digital Library

[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]

A. Beresford and F. Stajano. Mix zones: User privacy in location-aware services. In IEEE PerSec, 2004.

Digital Library

[15]

C. Bettini, X. SeanWang, and S. Jajodia. Protecting privacy against location-based personal identification,. In 2nd VLDB Workshop SDM, 2005.

Digital Library

[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]

R. Dingledine, N. Mathewson, and P. F. Syverson. Tor: The second-generation onion router. In USENIX Security Symposium, pages 303--320, 2004.

Digital Library

[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]

A. Gal and V. Atluri. An authorization model for temporal data. In Proceedings of the 7th ACM CCS, pages 144--153, New York, NY, USA, 2000. ACM Press.

Digital Library

[27]

B. Gedik and L. Liu. Location privacy in mobile systems: A personalized anonymization model. In Proceedings of the 25th IEEE ICDCS 2005, pages 620--629, Washington, DC, USA, 2005.

Digital Library

[28]

D. Goldschlag, M. Reed, and P. Syverson. Onion routing. Communications of the ACM, 42(2):39--41, 1999.

Digital Library

[29]

D. Goldschlag, M. Reed, and P. Syverson. Onion routing for anonymous and private internet connections. Communications of the ACM (USA), 42(2):39--41, 1999.

Digital Library

[30]

M. Gruteser and D. Grunwald. Anonymous usage of location-based services through spatial and temporal cloaking. In Proceedings of the ACM MobiSys, 2003.

Digital Library

[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.

Digital Library

[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.

Digital Library

[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]

B. Hoh and M. Gruteser. Protecting location privacy through path confusion. In Proceedings of IEEE/Create-Net SecureComm, Athens, Greece, September 2005.

Digital Library

[36]

B. Hoh, M. Gruteser, H. Xiong, and A. Alrabady. Enhancing security and privacy in traffic-monitoring systems. IEEE Pervasive Computing, 5(4):38--46, 2006.

Digital Library

[37]

B. Hoh, M. Gruteser, H. Xiong, and A. Alrabady. Preserving privacy in gps traces via uncertainty-aware path cloaking. In Proceedings of ACM CCS 2007, October 2007.

Digital Library

[38]

B. Hull, V. Bychkovsky, Y. Zhang, K. Chen, M. Goraczko, A. K. Miu, E. Shih, H. Balakrishnan, and S. Madden. CarTel: A Distributed Mobile Sensor Computing System. In 4th ACM SenSys, Boulder, CO, November 2006.

Digital Library

[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]

P. Kalnis, G. Ghinita, K. Mouratidis, and D. Papadias. Preventing location-based identity inference in anonymous spatial queries. IEEE Transactions on Knowledge and Data Engineering, 19(12):1719--1733, 2007.

Digital Library

[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]

T. Kohno, A. Broido, and K. C. Claffy. Remote physical device fingerprinting. In SP '05: Proceedings of the 2005 IEEE Symposium on Security and Privacy, pages 211--225, Washington, DC, USA, 2005. IEEE Computer Society.

Digital Library

[44]

J. Krumm. Inference attacks on location tracks. In Proceedings of the 5th International Conference on Pervasive Computing (Pervasive 2007), May 2007.

Digital Library

[45]

M. Li, K. Sampigethaya, L. Huang, and R. Poovendran. Swing & swap: user-centric approaches towards maximizing location privacy. In Proceedings of the 5th ACM WPES '06, pages 19--28, New York, NY, USA, 2006. ACM Press.

Digital Library

[46]

A. Machanavajjhala, J. Gehrke, D. Kifer, and M. Venkitasubramaniam. l-diversity: Privacy beyond k-anonymity. In Proceedings of the 22nd International Conference on Data Engineering (ICDE'06), page 24, 2006.

Digital Library

[47]

B. Mikhalkin, H. Payne, and L. Isaksen. Estimation of speed from presence detectors. Highway Research Record, 388:73--83, 1972.

[48]

M. F. Mokbel, C.-Y. Chow, and W. G. Aref. The new casper: query processing for location services without compromising privacy. In Proceedings of the 32nd VLDB'2006, pages 763--774. VLDB Endowment, 2006.

Digital Library

[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]

L. Sweeney. Achieving k-Anonymity Privacy Protection Using Generalization and Suppression. International Journal on Uncertainty, Fuzziness and Knowledge-based Systems, 10(5):571--588, 2002.

Digital Library

[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]

J. Yoon, B. Noble, and M. Liu. Surface street traffic estimation. In MobiSys '07: Proceedings of the 5th international conference on Mobile systems, applications and services, pages 220--232, New York, NY, USA, 2007. ACM.

Digital Library

[59]

M. Youssef, V. Atluri, and N. R. Adam. Preserving mobile customer privacy: an access control system for moving objects and customer profiles. In Proceedings of the 6th MDM '05, pages 67--76, New York, NY, USA, 2005. ACM Press.

Digital Library

[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.

Digital Library

Cited By

Luo CLi DKhan M(2024)An efficient certificateless anonymous signcryption communication scheme for vehicular adhoc networkScientific Reports10.1038/s41598-024-77992-514:1Online publication date: 7-Nov-2024
https://doi.org/10.1038/s41598-024-77992-5
Akallouch MAkallouch OFardousse KBouhoute ABerrada I(2022)Prediction and Privacy Scheme for Traffic Flow Estimation on the Highway Road NetworkInformation10.3390/info1308038113:8(381)Online publication date: 9-Aug-2022
https://doi.org/10.3390/info13080381
Li YZhou DLi YWeng JSun MYang YLi M(2022)Privacy-Preserving and Real-Time Detection of Vehicular Congestion Using Multilayer Perceptron Approach for Internet of VehiclesIEEE Transactions on Vehicular Technology10.1109/TVT.2022.319940771:12(12530-12542)Online publication date: Dec-2022
https://doi.org/10.1109/TVT.2022.3199407
Show More Cited By

Index Terms

Virtual trip lines for distributed privacy-preserving traffic monitoring
1. Security and privacy
  1. Human and societal aspects of security and privacy
2. Social and professional topics
  1. Computing / technology policy
    1. Computer crime
    2. Privacy policies

Recommendations

Preserving privacy in gps traces via uncertainty-aware path cloaking
CCS '07: Proceedings of the 14th ACM conference on Computer and communications security

Motivated by a probe-vehicle based automotive traffic monitoring system, this paper considers the problem of guaranteed anonymity in a dataset of location traces while maintaining high data accuracy. We find through analysis of a set of GPS traces from ...
Enhancing Privacy and Accuracy in Probe Vehicle-Based Traffic Monitoring via Virtual Trip Lines

Traffic monitoring using probe vehicles with GPS receivers promises significant improvements in cost, coverage, and accuracy over dedicated infrastructure systems. Current approaches, however, raise privacy concerns because they require participants to ...
Privacy-aware traffic monitoring

Traffic-monitoring systems (TMSs) are vital for safety and traffic optimization. However, these systems may compromise the privacy of drivers once they track the position of each driver with a high degree of temporal precision. In this paper, we argue ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

MobiSys '08: Proceedings of the 6th international conference on Mobile systems, applications, and services

June 2008

304 pages

ISBN:9781605581392

DOI:10.1145/1378600

General Chairs:
Dirk Grunwald
University of Colorado, USA
,
Richard Han
University of Colorado, USA
,
Program Chairs:
Eyal de Lara
University of Toronto, Canada
,
Carla Ellis
Duke University, USA

Copyright © 2008 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 17 June 2008

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

Mobisys08

Sponsor:

Mobisys08: The 6th International Conference on Mobile Systems, Applications, and Services

June 17 - 20, 2008

CO, Breckenridge, USA

Acceptance Rates

Overall Acceptance Rate 274 of 1,679 submissions, 16%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

254
Total Citations
View Citations
1,935
Total Downloads

Downloads (Last 12 months)73
Downloads (Last 6 weeks)12

Reflects downloads up to 09 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Luo CLi DKhan M(2024)An efficient certificateless anonymous signcryption communication scheme for vehicular adhoc networkScientific Reports10.1038/s41598-024-77992-514:1Online publication date: 7-Nov-2024
https://doi.org/10.1038/s41598-024-77992-5
Akallouch MAkallouch OFardousse KBouhoute ABerrada I(2022)Prediction and Privacy Scheme for Traffic Flow Estimation on the Highway Road NetworkInformation10.3390/info1308038113:8(381)Online publication date: 9-Aug-2022
https://doi.org/10.3390/info13080381
Li YZhou DLi YWeng JSun MYang YLi M(2022)Privacy-Preserving and Real-Time Detection of Vehicular Congestion Using Multilayer Perceptron Approach for Internet of VehiclesIEEE Transactions on Vehicular Technology10.1109/TVT.2022.319940771:12(12530-12542)Online publication date: Dec-2022
https://doi.org/10.1109/TVT.2022.3199407
Li MZhu LZhang ZLal CConti MAlazab M(2022)User-Defined Privacy-Preserving Traffic Monitoring Against n-by-1 Jamming AttackIEEE/ACM Transactions on Networking10.1109/TNET.2022.315765430:5(2060-2073)Online publication date: Oct-2022
https://doi.org/10.1109/TNET.2022.3157654
Gao RSun FXing WTao DFang JChai H(2022)CTTE: Customized Travel Time Estimation via Mobile CrowdsensingIEEE Transactions on Intelligent Transportation Systems10.1109/TITS.2022.316046823:10(19335-19347)Online publication date: Oct-2022
https://doi.org/10.1109/TITS.2022.3160468
Zavvos EGerding EYazdanpanah VMaple CStein Sschraefel m(2022)Privacy and Trust in the Internet of VehiclesIEEE Transactions on Intelligent Transportation Systems10.1109/TITS.2021.312112523:8(10126-10141)Online publication date: Aug-2022
https://doi.org/10.1109/TITS.2021.3121125
Overko ROrdonez-Hurtado RZhuk SFerraro PCullen AShorten R(2022)Spatial Positioning Token (SPToken) for Smart MobilityIEEE Transactions on Intelligent Transportation Systems10.1109/TITS.2020.302953723:2(1529-1542)Online publication date: Feb-2022
https://doi.org/10.1109/TITS.2020.3029537
Kim JEdemacu KJang B(2022)Privacy-preserving mechanisms for location privacy in mobile crowdsensingJournal of Network and Computer Applications10.1016/j.jnca.2021.103315200:COnline publication date: 9-May-2022
https://dl.acm.org/doi/10.1016/j.jnca.2021.103315
Silva PGonçalves CAntunes NCurado MWalek B(2022)Privacy risk assessment and privacy-preserving data monitoringExpert Systems with Applications10.1016/j.eswa.2022.116867200(116867)Online publication date: Aug-2022
https://doi.org/10.1016/j.eswa.2022.116867
Perez AZeadally S(2022)Secure and privacy-preserving crowdsensing using smart contractsComputer Science Review10.1016/j.cosrev.2021.10045043:COnline publication date: 9-May-2022
https://dl.acm.org/doi/10.1016/j.cosrev.2021.100450
Show More Cited By

View Options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents