近年來，隨著基於位置服務(Location-Based Service, 簡稱LBS)快速的發展，我們的生活也更加便利。然而使用者傳送的查詢內容中包含其私人訊息，因此當攻擊者獲得了查詢內容也會跟著得知了該使用者的私人訊息，從而曝露了隱私的資訊。為了保護使用者的隱私，已經有很多的方法被提出來。其中一個方法是在使用者查詢的內容中加入虛擬的擾亂訊息以此來保護使用者所在的位置。然而這類方法在保護使用者位置隱私的同時往往忽略效能的問題。因此我們不使用虛擬的擾亂訊息，而是將多個查詢合併在一起讓查詢彼此間是混淆的。本篇論文中提出了兩個新的演算法將多個查詢內容合併：基於群演算法(Cluster-Based algorithm) 以及基於點演算法(Point-Based algorithm)。這兩個演算法的主要目標是希望在提升LBS提供商的服務效能時，也可以有效的保護使用者的隱私。首先演算法會將所有查詢分群，而同一個群集中的查詢內容將會合併起來作為匿名查詢傳送給服務提供商（LBS provider），因此，服務提供商可以同時處理多個查詢內容以提升服務的效能。從使用者隱私保護的層面來看，當攻擊者得到了合併後的查詢內容也無法從中得知哪個使用者位於哪個位置，因為對於一個使用者來說同一個群集的其他使用者都是干擾的訊息。最後會透過模擬的實驗來顯示無論是基於群演算法或是基於點演算法在效能以及隱私保護上都擁有傑出的表現。

In recent years, with the rapid development of Location-Based Service(LBS), our life has become more convenient. However, the content of the query sent by the user contains their private information. When the attacker obtains the content of the query, he or she will also know the private information of the user, thus, causing the privacy problem. In order to protect the location privacy of the user, many methods have been proposed. One of the methods is to add some virtual disturbances to the query of the user to protect the location of the user. However, such methods often ignore the problem of service effectiveness, when they focus on protecting the privacy of the user location. Therefore, we do not adopt the virtual disturbances generation, we merge multiple queries to obfuscate each queries. In this paper, we propose two new algorithms to merge multiple queries: Cluster-based algorithm and Point-based algorithm. The primary goal of both algorithms is to enhance the service effectiveness of LBS provider while protecting the privacy of the user location. Firstly, both algorithms will cluster each queries, and queries in the same cluster will be merged and sent as anonymous query to LBS provider, thus, LBS provider can handle many query of users at a time to enhance the service effectiveness. From the perspective of user privacy protection, when the attacker gets the anonymity query, location of the user cannot be known, because other users of the same cluster are disturbances for one user. Finally, through simulation experiments, it is shown that both Cluster-based algorithm and Point-based algorithm have outstanding performance in increasing the service effectiveness and also performing well in terms of privacy protection.

[1] J. S. Lee, A. Fuchs, and J. B. Bullock, “Method and apparatus for providing navigational services in a wireless communication device,” Apr. 16 2002. US Patent 6,374,177.
[2] K. Shyamsunder, N. Goyal, V. Mangat, D. Schonfeld, and B. S. Kaliski Jr, “Smart navigation services,” Jan. 22 2019. US Patent App. 10/185,741.
[3] K. Obraczka, P. B. Danzig, and S.-H. Li, “Internet resource discovery services,” Computer, vol. 26, no. 9, pp. 8–22, 1993.
[4] B. Liu, Y. Fu, Z. Yao, and H. Xiong, “Learning geographical preferences for point-of interest recommendation,” in Proceedings of the 19th ACM SIGKDD international conference on knowledge discovery and data mining, pp. 1043–1051, ACM, 2013.
[5] S. S. Wang, ““I share, therefore I am”: Personality traits, life satisfaction, and facebook check-ins,” cyberpsychology, behavior, and social networking, vol. 16, no. 12, pp. 870–877, 2013.
[6] H. Li, Y. Ge, R. Hong, and H. Zhu, “Point-of-interest recommendations: Learning potential check-ins from friends,” in Proceedings of the 22nd ACM SIGKDD international conference on knowledge discovery and data mining, pp. 975–984, ACM, 2016.
[7] R. Daley, E. Wang, and S. Marolia, “Friends finder service for a mobile device in a network,” Apr. 3 2008. US Patent App. 11/839,396.
[8] A. Fattori, A. Reina, A. Gerino, and S. Mascetti, “On the privacy of real-world friend-finder services,” in Proceedings of 14th IEEE international conference on mobile data management, vol. 1, pp. 331–334, IEEE, 2013.
[9] G. Ghinita, P. Kalnis, A. Khoshgozaran, C. Shahabi, and K.-L. Tan, “Private queries in location based services: Anonymizers are not necessary,” in Proceedings of the international conference on management of data, pp. 121–132, ACM, 2008.
[10] C.-Y. Chow, M. F. Mokbel, and X. Liu, “A peer-to-peer spatial cloaking algorithm for anonymous location-based service,” in Proceedings of the international symposium on advances in geographic information systems, pp. 171–178, ACM, 2006.
[11] 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, vol. 19, no. 12, pp. 1719–1733, 2007.
[12] H. Ngo and J. Kim, “Location privacy via differential private perturbation of cloaking area,” in Proceedings of 28th IEEE computer security foundations symposium, pp. 63–74, IEEE, 2015.
[13] M. Gruteser and D. Grunwald, “Anonymous usage of location-based services
through spatial and temporal cloaking,” in Proceedings of the 1st international conference on mobile systems, applications and services, pp. 31–42, ACM, 2003.
[14] 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 international conference on very large data bases, pp. 763–774, VLDB Endowment,
2006.
[15] B. Bamba, L. Liu, P. Pesti, and T. Wang, “Supporting anonymous location queries in mobile environments with privacygrid,” in Proceedings of the 17th international conference on world wide web, pp. 237–246, ACM, 2008.
[16] Y. Wang, D. Xu, X. He, C. Zhang, F. Li, and B. Xu, “L2P2: Location-aware location privacy protection for location-based services,” in Proceedings IEEE INFOCOM, pp. 1996–2004, IEEE, 2012.
[17] L. Sweeney, “k-anonymity: A model for protecting privacy,” International journal of uncertainty, fuzziness and knowledge-based systems, vol. 10, no. 05, pp. 557–570, 2002.
[18] H. Kido, Y. Yanagisawa, and T. Satoh, “An anonymous communication technique using dummies for location-based services,” in Proceedings of the international conference on pervasive services, pp. 88–97, IEEE, 2005.
[19] H. Lu, C. S. Jensen, and M. L. Yiu, “PAD: Privacy-area aware, dummy-based location privacy in mobile services,” in Proceedings of the 7th ACM international
workshop on data engineering for wireless and mobile access, pp. 16–23, ACM, 2008.
[20] B. Niu, Q. Li, X. Zhu, G. Cao, and H. Li, “Achieving k-anonymity in privacy-aware location-based services,” in Proceedings IEEE INFOCOM, pp. 754–762, IEEE,
2014.
[21] B. Niu, Q. Li, X. Zhu, G. Cao, and H. Li, “Enhancing privacy through caching in location-based services,” in Proceedings IEEE INFOCOM, pp. 1017–1025, IEEE,
2015.
[22] R. Xu and I. Donald Wunsch, “Survey of clustering algorithms,” IEEE transactions on neural networks, vol. 16, no. 3, p. 645, 2005.
[23] B. Gedik and L. Liu, “Location privacy in mobile systems: A personalized anonymization model,” in Proceedings of 25th international conference on distributed computing systems, pp. 620–629, IEEE, 2005.
[24] N. Li, T. Li, and S. Venkatasubramanian, “t-closeness: Privacy beyond k-anonymity and l-diversity,” in Proceedings of the 23rd international conference on data engineering, pp. 106–115, IEEE, 2007.
[25] G. Ghinita, P. Kalnis, and S. Skiadopoulos, “PRIVE: Anonymous location-based queries in distributed mobile systems,” in Proceedings of the 16th international conference on world wide web, pp. 371–380, ACM, 2007.
[26] K. Jung and S. Park, “Collaborative caching techniques for privacy-preserving location-based services in peer-to-peer environments,” in Proceedings of the IEEE international conference on big data, pp. 4497–4506, IEEE, 2017.
[27] C.-Y. Chow, M. F. Mokbel, and W. G. Aref, “Casper*: Query processing for location services without compromising privacy,” ACM transactions on database systems, vol. 34, no. 4, p. 24, 2009.
[28] M. Duckham and L. Kulik, “A formal model of obfuscation and negotiation for location privacy,” in Proceedings of the international conference on pervasive computing, pp. 152–170, Springer, 2005.
[29] N. E. Bordenabe, K. Chatzikokolakis, and C. Palamidessi, “Optimal geo-indistinguishable mechanisms for location privacy,” in Proceedings of the conference on computer and communications security, pp. 251–262, ACM, 2014.
[30] A. Khoshgozaran and C. Shahabi, “Blind evaluation of nearest neighbor queries using space transformation to preserve location privacy,” in Proceedings of international symposium on spatial and temporal databases, pages=239–257, year=2007, organization=Springer.
[31] L. Wang, D. Yang, X. Han, T. Wang, D. Zhang, and X. Ma, “Location privacy-preserving task allocation for mobile crowdsensing with differential geo-obfuscation,” in Proceedings of the 26th international conference on world wide
web, pp. 627–636, IW3C2, 2017.
[32] M. L. Yiu, C. S. Jensen, J. Møller, and H. Lu, “Design and analysis of a ranking approach to private location-based services,” ACM transactions on database systems, vol. 36, no. 2, p. 10, 2011.
[33] P. Perazzo and G. Dini, “A uniformity-based approach to location privacy,” Computer communications, vol. 64, pp. 21–32, 2015.
[34] H. Liu, X. Li, H. Li, J. Ma, and X. Ma, “Spatiotemporal correlation-aware dummy-based privacy protection scheme for location-based services,” in Proceedings IEEE INFOCOM, pp. 1–9, IEEE, 2017.
[35] R. Paulet, M. G. Kaosar, X. Yi, and E. Bertino, “Privacy-preserving and content-protecting location based queries,” IEEE transactions on knowledge and data engineering, vol. 26, no. 5, pp. 1200–1210, 2013.
[36] X. Yi, R. Paulet, E. Bertino, and V. Varadharajan, “Practical approximate k nearest neighbor queries with location and query privacy,” IEEE transactions on knowledge and data engineering, vol. 28, no. 6, pp. 1546–1559, 2016.
[37] L. F. Cranor, “P3P: Making privacy policies more useful,” IEEE security & privacy, vol. 99, no. 6, pp. 50–55, 2003.
[38] J. Angulo, S. Fischer-Hübner, E. Wästlund, and T. Pulls, “Towards usable privacy policy display and management,” Information management & computer Security, vol. 20, no. 1, pp. 4–17, 2012.
[39] S. Kiyomoto, T. Nakamura, H. Takasaki, R. Watanabe, and Y. Miyake, “Ppm: Privacy policy manager for personalized services,” in Proceedings of international conference on availability, reliability, and security, pp. 377–392, Springer, 2013.
[40] S. Hayashida, D. Amagata, T. Hara, and X. Xie, “Dummy generation based on user-movement estimation for location privacy protection,” IEEE Access, vol. 6, pp. 22958–22969, 2018.
[41] G. Sun, S. Cai, H. Yu, S. Maharjan, V. Chang, X. Du, and M. Guizani, “Location privacy preservation for mobile users in location-based services,” IEEE Access, 2019.
[42] J. Wang, Z. Cai, Y. Li, D. Yang, J. Li, and H. Gao, “Protecting query privacy with differentially private k-anonymity in location-based services,” Personal and ubiquitous computing, vol. 22, no. 3, pp. 453–469, 2018.
[43] B. Niu, Z. Zhang, X. Li, and H. Li, “Privacy-area aware dummy generation algorithms for location-based services,” in Proceedings of IEEE international conference on communications, pp. 957–962, IEEE, 2014.