I. Introduction
Location-based services (LBSs) provide mobile users with points of interest (POIs) close to their locations, such as restaurants, gas stations, shopping malls, and social events. With great advances in mobile devices, e.g., smart phones and tablets, LBSs have recently emerged as a very popular application in mobile networks. According to ABI Research [1], LBS revenue is forecasted to reach an annual global total of $13.3 billion by 2013. However, since LBS service providers require users to report their location information, one major concern in LBSs is users' location privacy. For example, the LBS providers can be compromised by attackers to track some users, or they themselves may use users' location information for mobile advertising. Thus, how to provide LBSs while protecting users' location privacy is an important and challenging problem. In the literature, there are generally two kinds of approaches addressing location privacy in LBSs: k-anonymity cloaking [2]–[10] and location obfuscation [11]–[15]. -anonymity cloaking is firstly proposed by Gruteser and Grunwald [2]. Instead of sending one single user's LBS request to the server, including his/her exact location. -anonymity cloaking employs a trusted third-party who collects neighboring users' requests and sends them all together to the LBS service provider. However, an adversary can know that the user of interest must be located in one of the locations. Besides, this scheme may lead to large service delay if there are not enough users requesting LBSs. Following [2], Gedik and Liu [3] design a joint spatial and temporal cloaking algorithm, which collects LBS requests, each from a different user, in a specified cloaking area within a specified time period and then sends them to the service provider. In this scheme, however, users' requests will be blocked if there are only less than requests within the predefined time period. Moreover, in the above two works, when user density is high, the users' locations may be very close to each other, and hence these approaches will still reveal user's location privacy to some extent. Later on, Mokbel et al. [4] set a minimum size for the cloaking area, and require all mobile users to report their position frequently to an anonymizer (i.e., a third party) in order to provide LBSs with low delay. Unfortunately, frequent position update can incur overwhelming communication overhead for mobile users. Besides, [8], [9], [16] propose to let users exchange their pseudonyms when they meet in mix zones, which need the participation of other users. Note that [9] may not provide real-time services. In addition, Meyerowitz and Choudhury [10] predict users' paths and LBS queries, and send the results to users' before they submit queries. This approach may incur significant communication overhead in order to achieve good service accuracy, and also take up large storage spaces.