24-09-2013, 03:35 PM
Privacy-Conscious Location-Based Queries in Mobile Environments
Privacy-Conscious Location.pdf (Size: 610.98 KB / Downloads: 18)
Abstract
In location-based services, users with location-aware
mobile devices are able to make queries about their surroundings
anywhere and at any time. While this ubiquitous computing
paradigm brings great convenience for information access, it also
raises concerns over potential intrusion into user location privacy.
To protect location privacy, one typical approach is to cloak
user locations into spatial regions based on user-specified pri-
vacy requirements, and to transform location-based queries into
region-based queries. In this paper, we identify and address three
new issues concerning this location cloaking approach. First, we
study the representation of cloaking regions and show that a
circular region generally leads to a small result size for region-
based queries. Second, we develop a mobility-aware location
cloaking technique to resist trace analysis attacks. Two cloaking
algorithms, namely MaxAccu Cloak and MinComm Cloak, are
designed based on different performance objectives. Finally, we
develop an efficient polynomial algorithm for evaluating circular-
region-based kNN queries. Two query processing modes, namely
bulk and progressive, are presented to return query results either
all at once or in an incremental manner. Experimental results
show that our proposed mobility-aware cloaking algorithms
significantly improve the quality of location cloaking in terms
of an entropy measure without compromising much on query
latency or communication cost. Moreover, the progressive query
processing mode achieves a shorter response time than the
bulk mode by parallelizing the query evaluation and result
transmission.
INTRODUCTION
Location-based services (LBS) are emerging as a major
application of mobile geospatial technologies [7], [21], [23],
[35]. In LBS, users with location-aware mobile devices are
able to make queries about their surroundings anywhere and at
any time. Spatial range queries and k-nearest-neighbor (kNN)
queries are two types of the most commonly used queries in
LBS. For example, a user can make a range query to find out
all shopping centers within a certain distance of her current
location, or make a kNN query to find out the k nearest gas
stations. In these queries, the user has to provide the LBS
server with her current location. But the disclosure of location
information to the server raises privacy concerns, which have
hampered the widespread use of LBS [18], [19], [30]. Thus,
how to provision location-based services while protecting user
location privacy has recently become a hot research topic [6],
[13], [15], [24], [25], [26].
RELATED W ORK
Location Privacy Protection. There are two main approaches
to protecting location privacy in LBS. The first approach relies
on a trusted LBS server to restrict access to location data based
on rule-based policies [10], [11], [36]. The second category of
approaches run a trustworthy agent between the client and the
LBS server. Every time the user makes a location-based query,
the agent anonymizes the user identity and/or location before
forwarding the query to the LBS server [5], [13], [26]. Our
study falls into the second category.
Early studies on location privacy protection considered ob-
ject tracking applications, where a proxy server is employed to
collect exact locations from moving clients and to anonymize
location data through de-personalization before release. In [5],
once a client enters a pre-defined zone, its identity is mixed
with all other clients in the same zone. It appears that this
idea can be extended to deal with trace analysis attacks by
associating each LBS request with a different pseudonym.
Unfortunately, this approach may not be effective because
historical user locations are highly correlative and, hence, they
could be re-linked using trajectory tracking methods (e.g.,
multi-target tracking [27], [32]) even without knowing any
identity [34].
MOBILITY-AWARE LOCATION CLOAKING
We now study how to generate circular cloaking regions
based on privacy requirements. Under isolated cloaking, for
each query with a cloaking area requirement Amin , a circle
with radius Amin /π covering the user location l is randomly
generated to serve as the cloaking region. But this scheme
is vulnerable to trace analysis attacks. As discussed in the
Introduction, by correlating the query trace and the mobility
pattern, the LBS server (adversary) is likely to derive the
probabilities of user locations in the cloaking region. This
leads to a significant degradation of the quality of location
cloaking. In this section, we develop an optimal mobility-
aware cloaking technique that works as follows. For the first
query, a random cloaking region is generated.
Effectiveness of Mobility-Aware Cloaking
In this section, we compare the proposed optimal mobility-
aware cloaking technique (Algorithm 1) against the isolated
cloaking scheme (described at the beginning of Section V).
For both the optimal and isolated cloaking techniques, initially
a cloaking region is randomly generated based on the user
location. In other words, the user is equally likely to be at any
location in the cloaking region. We measure the quality of the
cloaking region for a subsequent query in terms of entropy
based on 1,500 sample locations and 1,000 random queries.
As shown in Figures 13a and 13b, when the query interval
is small (i.e., 1 min), the entropy of isolated cloaking is
nearly 20% lower than that of optimal cloaking for all queries
tested. With increasing query interval, the average entropy of
isolated cloaking improves (see Figure 13c) but is still far
lower than that of optimal cloaking. When the query interval
is 8 min, Figure 13a and 13b show that the entropy of isolated
cloaking is 40% lower than that of optimal cloaking for over
15% of the queries tested and 20% lower for over 40% of
the queries tested. Note that the results shown here are for
one successive query only. With more successive queries, the
quality of isolated cloaking would further degrade.
CONCLUSION
This paper has presented a complete study on processing
privacy-conscious location-based queries in mobile environ-
ments. The technical contributions made in this paper are
summarized as follows:
• We have studied the representation of cloaking regions
and showed that a circular region generally leads to a
small result superset.
• We have developed an optimal mobility-aware location
cloaking technique to resist trace analysis attacks. Two
cloaking algorithms, namely MaxAccu Cloak and Min-
Comm Cloak, have been designed to favor different per-
formance objectives.
• We have developed two efficient polynomial algorithms,
namely bulk and progressive, for processing circular-
region-based kNN queries.