近幾年適地性服務(location-based services, LBS)已成為人們日常生活中相當熱門的應用服務，但使用者的隱私同時也受到相當大的威脅。過去在道路網路上的隱私保護大多採用k-匿名技術並搭配中央集權式架構來保護使用者的位置隱私。雖然，目前演算法的遮蔽空間結果可滿足使用者隱私需求，但卻可能提供過大的隱匿空間，而降低服務品質(例如：過多的候選答案、溝通時間…等)。

本篇論文將基於真實道路網狀分佈資訊，對適地性服務(LBS)的使用者提供隱私保護的議題進行研究。本論文有以下幾個特色: (1) 提出最適優先隱匿演算法(Best-First Cloaking algorithm, BFC)來產生一個更貼近使用者需求的隱匿空間，並達到隱私與服務品質的平衡。(2) 同時我們另外提出進階版的最適優先隱匿演算法(稱為Advanced Best-First Cloaking algorithm, ABFC)來改善BFC的效能。(3) 探討單一時點的服務查詢(snapshot queries)遭遇到的推論攻擊與過去的解決方法，並提出新的解決概念。(4) 實驗結果顯示，我們的演算法相較於過去的研究提供滿足使用者隱私需求的更佳匿名層級。

Recently location-based services (LBS) are massively used in the daily life, but users’ location privacy could have been threatened as well. Most of the prior works, especially in the road network, implement k-anonymity in the centralized trusted third party architecture to protect the users’ location privacy. Although the cloaked segment sets of all the cloaking algorithms could satisfy the user-specified privacy requirements, might have unnecessary anonymity level and include too many cloaked segments. This will produce larger candidate answers and cost more communication effort.

In this paper, we are going to do research on the privacy protect techniques for the LBS users in road networks. The key features of this paper can be summarized as follows: (1) we proposed the Best-First Cloaking algorithm (named as BFC) to generate a cloaked segment set which is more matched to the user-specified privacy requirements. The BFC algorithm makes good trade-off between users’ location privacy and LBS QoS. (2) We proposed the Advanced Best-First algorithm (named as ABFC) to improve the performance of BFC algorithm. (3) We discuss the query sample attack [2] of snapshot queries and its existing solution. Then we suggest a novel solution. (4) Experimental results show that our proposed cloaking algorithms not only provide a more appropriate anonymity level but also satisfy the user-specified privacy requirements compared with the others.

中文摘要I
AbstractII
誌 謝III
ContentsIV
List of FiguresV
List of TablesVI
Chapter 1 Introduction1
Chapter 2 Related Work4
Chapter 3 Preliminaries10
3.1 System Architecture10
3.2 Personalized Privacy Requirements12
3.3 Requirements of the location cloaking algorithm13
3.4 Two anonymization algorithms14
3.4.1 The Spatial-Temporal Connective Cloaking (STCC)15
3.4.1.1 The Hierarchical index structure15
3.4.1.2 Algorithm Description18
3.4.2 Location cloaking algorithm based on Network Expansion20
3.5 Discussion21
Chapter 4 Proposed Cloaking Algorithms23
4.1 Data Structure25
4.2 The Best-First Cloaking algorithm (BFC)26
4.3 The Advanced Best-First Cloaking algorithm (ABFC)32
Chapter 5 Experimental Results38
5.1 Effect of Privacy Requirements40
5.2 Scalability44
Chapter 6 Discussion48
Chapter 7 Conclusion and Future Work50
Reference51

[1]B. Gedik and L. Liu. Location Privacy in Mobile Systems: A Personalized Anonymization Model. In Proceeding of the International Conference on Distributed Computing Systems (ICDCS), pp. 620-629, 2005.
[2]C. Chow, M. F. Mokbel. Enabling Private Continuous Queries for Revealed User Locations. In International Symposium on Spatial and Temporal Databases (SSTD), pages 258-275, 2007.
[3]C. Chow, M. F. Mokbel, and X. Liu. A Peer-to-peer Spatial Cloaking Algorithm for Anonymous Location-based Service. In International Symposium on Geographic Information Systems (ACM-GIS), pages 171-178, 2006.
[4]D. Papadias, J. Zhang, N. Mamoulis, and Y. Tao. Query processing in spatial network databases. In Proceedings of the International Conference on Very Large Data Bases (VLDB), Vol. 29, pp. 802-813, 2003.
[5]D. Kifer and J. Gehrke. l-diversity: Privacy beyond k-anonymity. In International Conference on Data Engineering (ICDE), 2006.
[6]Fox-News: Man Charged With Stalking Woman Via Phone's GPS. http://www.foxnews.com/us/2010/03/02/man-charged-stalking-woman-phones-gps/
[7]H. Kido, Y. Yanagisawa, and T. Satoh. An Anonymous Communication Technique using Dummies for Location-based Services. In IEEE International Conference on Pervasive Services (ICPS), pp. 1248, 2005.
[8]IEEE Spectrum: Stalked by Satellite: An alarming rise in GPS-enabled harassment. http://spectrum.ieee.org/aerospace/satellites/stalked-by-satellite
[9]J. I. Hong and J. A. Landay. An architecture for privacy-sensitive ubiquitous computing. In Proceedings of the second international conference on mobile systems, applications, and services (MOBISYS), pp. 177–189, 2004.
[10]J. Bao, H. Chen, and W.-S. Ku. Pros: a peer-to-peer system for location privacy protection on road networks. In GIS, pp. 552–553, 2009.
[11]K. Mouratidis, M. Yiu. Anonymous Query Processing in Road Networks. IEEE Transactions on Knowledge and Data Engineering (TKDE), 22(1), 2-15, 2010.
[12]L. Sweene. k-Anonymity: A Model for Protecting Privacy. In International Journal of Uncertainty, Fuzziness and Knowledge-Based Systems (IJUFKS), 10(5):557-570, 2002.
[13]L. Liu. From data privacy to location privacy: Models & Algorithms. Tutorial. In Proceedings of the International Conference on Very Large Data Bases (VLDB), pp. 1429-1430, 2007.
[14]M. F. Mokbel, C. Chow, and W. G. Aref. The New Casper: Query Processing for Location Services without Compromising Privacy. In Proceedings of the International Conference on Very Large Data Bases (VLDB), pages 763-774, 2006.
[15]M. Gruteser, D. Grunwald. Anonymous Usage of Location-Based Services through Spatial and Temporal Cloaking. In Proceedings of the International Conference on Mobile Systems, Applications, and Services. (MobiSys), pp. 31-42, 2003.
[16]M. Duckham and L. Kulik. A Formal Model of Obfuscation and Negotiation for Location Privacy. In Pervasive, pp. 152-170, 2005.
[17]M. L. Yiu, C. Jensen, X. Huang, and H. Lu. Spacetwist: Managing the trade-offs among location privacy, query performance, and query accuracy in mobile services. In International Conference on Data Engineering (ICDE), 2008.
[18]P.-Y. Li, W.-C. Peng, T.-W. Wang, W.-S. Ku, and J. Xu, A Cloaking Algorithm Based on Spatial Networks for Location Privacy, In Proceedings of the IEEE International Conference on Sensor Networks, Ubiquitous, and Trustworthy Computing (SUTC), 2008.
[19]T. Brinkhoff®. A Framework for Generating Network-Based Moving Objects. GeoInformatica, 6(2):153-180, 2002.
[20]T. Wang and L. Liu. Privacy-aware mobile services over road networks. In Proceedings of the International Conference on Very Large Data Bases (VLDB), 2009.
[21]W.-S. Ku, R. Zimmermann, W.-C. Peng and S. Shroff. Privacy protected query processing on spatial networks. In IEEE International Conference on Data Engineering (ICDE), pp. 215–220, 2007.
[22]李柏逸，「以道路網路狀的遮蓋機制來保護位置隱私權」，碩士論文，國立交通大學資訊科學與工程研究所，新竹 (2007)。