A peer-to-peer spatial cloaking algorithm for anonymous location-based service

ABSTRACT

This paper tackles a major privacy threat in current location-based services where users have to report their exact locations to the database server in order to obtain their desired services. For example, a mobile user asking about her nearest restaurant has to report her exact location. With untrusted service providers, reporting private location information may lead to several privacy threats. In this paper, we present a peer-to-peer (P2P)spatial cloaking algorithm in which mobile and stationary users can entertain location-based services without revealing their exact location information. The main idea is that before requesting any location-based service, the mobile user will form a group from her peers via single-hop communication and/or multi-hop routing. Then,the spatial cloaked area is computed as the region that covers the entire group of peers. Two modes of operations are supported within the proposed P2P s patial cloaking algorithm, namely, the on-demand mode and the proactive mode. Experimental results show that the P2P spatial cloaking algorithm operated in the on-demand mode has lower communication cost and better quality of services than the proactive mode, but the on-demand incurs longer response time.

REFERENCES

• 1: L. Ackerman, J. Kempf, and T. Miki. Wireless Location Privacy: A Report on Law and Policy in the United States, the Europrean Union, and Japan. Technical Report DCL-TR2003-001, DoCoMo Commuinication Laboratories, USA, 2003.
• 2: Beongku An , Symeon Papavassiliou, A mobility-based clustering approach to support mobility management and multicast routing in mobile ad-hoc wireless networks, International Journal of Network Management, v.11 n.6, p.387-395, November/December 2001 [doi>10.1002/nem.415]
• 3: Daniel Barbará , Tomasz Imieliński, Sleepers and workaholics: caching strategies in mobile environments (extended version), The VLDB Journal — The International Journal on Very Large Data Bases, v.4 n.4, October 1995
• 4: L. Barkhuus and A. K. Dey. Location-Based Services for Mobile Telephony: A Study of Users 'Privacy Concerns. In Proceeding of the IFIP Conference on Human-Computer Interaction, INTERACT 2003.
• 5: Roberto J. Bayardo , Rakesh Agrawal, Data Privacy through Optimal k-Anonymization, Proceedings of the 21st International Conference on Data Engineering (ICDE'05), p.217-228, April 05-08, 2005 [doi>10.1109/ICDE.2005.42]
• 6: Alastair R. Beresford , Frank Stajano, Location Privacy in Pervasive Computing, IEEE Pervasive Computing, v.2 n.1, p.46-55, January 2003 [doi>10.1109/MPRV.2003.1186725]
• 7: Josh Broch , David A. Maltz , David B. Johnson , Yih-Chun Hu , Jorjeta Jetcheva, A performance comparison of multi-hop wireless ad hoc network routing protocols, Proceedings of the 4th annual ACM/IEEE international conference on Mobile computing and networking, p.85-97, October 25-30, 1998, Dallas, Texas, United States [doi>10.1145/288235.288256]
• 8: T. Camp, J. Boleng, and V. Davies. A Survey of Mobility Models for Ad Hoc Network Research. Wireless Communications and Mobile Computing (WCMC) 2(5):483--502, 2002.
• 9: Chi-Yin Chow , Hong Va Leong , Alvin T. S. Chan, Distributed group-based cooperative caching in a mobile broadcast environment, Proceedings of the 6th international conference on Mobile data management, May 09-13, 2005, Ayia Napa, Cyprus [doi>10.1145/1071246.1071261]
• 10: M. Duckham and L. Kulik. A Formal Model of Obfuscation and Negotiation for Location Privacy. In Pervasive 2005.
• 11: A. Ephremides, J. Wieselthier, and D. J. Baker. A Design Concept for Reliable Mobile Radio Networks with Frequency Hopping Signaling. Proceedings of IEEE 75(1):56--73,1987.
• 12: Foxs News. Man Accused of Stalking Ex-Girlfriend With GPS. http://www.foxnews.com/story/0,2933,131487,00.html. Sep 04, 2004.
• 13: B. Gedik and L. Liu. A Customizable k Anonymity Model for Protecting Location Privacy. In ICDCS 2005.
• 14: M. Gruteser and D. Grunwald. Anonymous Usage of Location-Based Services Through Spatial and Temporal Cloaking. In MobiSys 2003.
• 15: M. Gruteser and X. Liu. Protecting Privacy in Continuous Location-Tracking Applications.IEEE Security and Privacy 2(2):28--34, 2004.
• 16: T. Hara. Effective Replica Allocation in Ad Hoc Networks for Improving Data Accessibility. In INFOCOM 2001.
• 17: U. Hengartner and P. Steenkiste. Protecting Access to People Location Information. In Proceeding of the International Conference on Security in Pervasive Computing, SPC 2003.
• 18: Jason I. Hong , James A. Landay, An architecture for privacy-sensitive ubiquitous computing, Proceedings of the 2nd international conference on Mobile systems, applications, and services, June 06-09, 2004, Boston, MA, USA [doi>10.1145/990064.990087]
• 19: Jiun-Long Huang , Ming-Syan Chen , Wen-Chih Peng, Exploring group mobility for replica data allocation in a mobile environment, Proceedings of the twelfth international conference on Information and knowledge management, November 03-08, 2003, New Orleans, LA, USA [doi>10.1145/956863.956894]
• 20: Zhiyong Huang , Christian S. Jensen , Hua Lu , Beng Chin Ooi, Skyline Queries Against Mobile Lightweight Devices in MANETs, Proceedings of the 22nd International Conference on Data Engineering (ICDE'06), p.66, April 03-07, 2006 [doi>10.1109/ICDE.2006.142]
• 21: Tomasz Imielinski , B. R. Badrinath, Mobile wireless computing: challenges in data management, Communications of the ACM, v.37 n.10, p.18-28, Oct. 1994 [doi>10.1145/194313.194317]
• 22: Eija Kaasinen, User needs for location-aware mobile services, Personal and Ubiquitous Computing, v.7 n.1, p.70-79, May 2003 [doi>10.1007/s00779-002-0214-7]
• 23: H. Kido, Y. Yanagisawa, and T. Satoh. An Anonymous Communication Technique using Dummies for Location-based Services. In Proceedings of IEEE International Conference on Pervasive Services, ICPS 2005.
• 24: Wei-Shinn Ku , Roger Zimmermann , Haojun Wang , Chi-Ngai Wan, Adaptive nearest neighbor queries in travel time networks, Proceedings of the 13th annual ACM international workshop on Geographic information systems, November 04-05, 2005, Bremen, Germany [doi>10.1145/1097064.1097094]
• 25: G. H. K. Lam, H. V. Leong, and S. C. F. Chan. GBL: Group-Based Location Updating in Mobile Environment. In DASFAA 2004.
• 26: Kristen LeFevre , David J. DeWitt , Raghu Ramakrishnan, Mondrian Multidimensional K-Anonymity, Proceedings of the 22nd International Conference on Data Engineering (ICDE'06), p.25, April 03-07, 2006 [doi>10.1109/ICDE.2006.101]
• 27: Kristen LeFevre , David J. DeWitt , Raghu Ramakrishnan, Incognito: efficient full-domain K-anonymity, Proceedings of the 2005 ACM SIGMOD international conference on Management of data, June 14-16, 2005, Baltimore, Maryland [doi>10.1145/1066157.1066164]
• 28: Adam Meyerson , Ryan Williams, On the complexity of optimal K-anonymity, Proceedings of the twenty-third ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 14-16, 2004, Paris, France [doi>10.1145/1055558.1055591]
• 29: Mohamed F. Mokbel, Towards Privacy-Aware Location-Based Database Servers, Proceedings of the 22nd International Conference on Data Engineering Workshops (ICDEW'06), p.93, April 03-07, 2006 [doi>10.1109/ICDEW.2006.152]
• 30: Mohamed F. Mokbel , Walid G. Aref , Susanne E. Hambrusch , Sunil Prabhakar, Towards scalable location-aware services: requirements and research issues, Proceedings of the 11th ACM international symposium on Advances in geographic information systems, p.110-117, November 07-08, 2003, New Orleans, Louisiana, USA [doi>10.1145/956676.956691]
• 31: 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
• 32: Maria Papadopouli , Henning Schulzrinne, Effects of power conservation, wireless coverage and cooperation on data dissemination among mobile devices, Proceedings of the 2nd ACM international symposium on Mobile ad hoc networking & computing, October 04-05, 2001, Long Beach, CA, USA [doi>10.1145/501431.501433]
• 33: A. K. Parekh. Selecting Routers in Ad-Hoc Wireless Network. In Proceedings of the International Telecommunications Symposium 1994.
• 34: J. Reed, K. Krizman, B. Woerner, and T. Rappaport. An Overview of the Challenges and Progress in Meeting the E-911 Requirement for Location Service. IEEE Personal Communications Magazine 5(3):30--37, 1998.
• 35: H. Schwetman. User's Guide CSIM19 Simulation Engine (C++ Version)Mesquite Software Inc.
• 36: Randall R. Stewart , Qiaobing Xie, Stream control transmission protocol (SCTP): a reference guide, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 2001
• 37: 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]
• 38: Latanya Sweeney, k-anonymity: a model for protecting privacy, International Journal of Uncertainty, Fuzziness and Knowledge-Based Systems, v.10 n.5, p.557-570, October 2002 [doi>10.1142/S0218488502001648]
• 39: USA Today. Authorities:GPS System Used to Stalk Woman. http://www.usatoday.com/tech/news/2002-12-30-gps- stalker x.htm, Dec 30, 2002.
• 40: Michael Alan Caplinger , Michael Lee Campbell , Michael Anthony Capstick, Cover story: they know where you are, IEEE Spectrum, v.40 n.7, p.20-25, July 2003 [doi>10.1109/MSPEC.2003.1209608]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications
          Subjects: Spatial databases and GIS

General Terms:
Algorithms, Experimentation

Keywords:
location privacy and spatial cloaking, location-based services, mobile computing