Abstract
Route Planning Systems (RPS) are a core component of autonomous personal transport systems essential for safe and efficient navigation of dynamic urban environments with the support of edge-based smart city infrastructure, but they also raise concerns about user route privacy in the context of both privately owned and commercial vehicles. Numerous high-profile data breaches in recent years have fortunately motivated research on privacy preserving RPS, but most of them are rendered impractical by greatly increased communication and processing overhead. We address this by proposing an approach called Hierarchical Privacy-Preserving Route Planning (HPRoP), which divides and distributes the route-planning task across multiple levels and protects locations along the entire route. This is done by combining Inertial Flow partitioning, Private Information Retrieval (PIR), and Edge Computing techniques with our novel route-planning heuristic algorithm. Normalized metrics were also formulated to quantify the privacy of the source/destination points (endpoint location privacy) and the route itself (route privacy). Evaluation on a simulated road network showed that HPRoP reliably produces routes differing only by ≤ 20% in length from optimal shortest paths, with completion times within ∼25 seconds, which is reasonable for a PIR-based approach. On top of this, more than half of the produced routes achieved near-optimal endpoint location privacy (∼1.0) and good route privacy (≥ 0.8).
Recommended Citation
F. Tiausas et al., "HPRoP: Hierarchical Privacy-preserving Route Planning For Smart Cities," ACM Transactions on Cyber-Physical Systems, vol. 7, no. 4, article no. 27, Association for Computing Machinery (ACM), Oct 2023.
The definitive version is available at https://doi.org/10.1145/3616874
Department(s)
Computer Science
Publication Status
Open Access
Keywords and Phrases
Additional Key Words and PhrasesRoute planning services; location privacy; route-planning algorithms
International Standard Serial Number (ISSN)
2378-9638; 2378-962X
Document Type
Article - Journal
Document Version
Citation
File Type
text
Language(s)
English
Rights
© 2023 Association for Computing Machinery (ACM), All rights reserved.
Publication Date
14 Oct 2023
Comments
National Science Foundation, Grant 1647015