08-05-2012, 10:39 AM
A Privacy-Preserving Location Monitoring System for Wireless Sensor Networks
A Privacy-Preserving Location Monitoring System for Wireless Sensor Networks.pdf (Size: 868.34 KB / Downloads: 52)
Abstract
Monitoring personal locations with a potentially untrusted server poses privacy threats to the monitored individuals. To
this end, we propose a privacy-preserving location monitoring system for wireless sensor networks. In our system, we design two innetwork
location anonymization algorithms, namely, resource- and quality-aware algorithms, that aim to enable the system to provide
high quality location monitoring services for system users, while preserving personal location privacy. Both algorithms rely on the well
established k-anonymity privacy concept, that is, a person is indistinguishable among k persons, to enable trusted sensor nodes to
provide the aggregate location information of monitored persons for our system. Each aggregate location is in a form of a monitored
area A along with the number of monitored persons residing in A, where A contains at least k persons. The resource-aware algorithm
aims to minimize communication and computational cost, while the quality-aware algorithm aims to maximize the accuracy of the
aggregate locations by minimizing their monitored areas. To utilize the aggregate location information to provide location monitoring
services, we use a spatial histogram approach that estimates the distribution of the monitored persons based on the gathered aggregate
location information. Then the estimated distribution is used to provide location monitoring services through answering range queries.
We evaluate our system through simulated experiments. The results show that our system provides high quality location monitoring
services for system users and guarantees the location privacy of the monitored persons.
Index TermsLocation privacy, wireless sensor networks, location monitoring system, aggregate query processing, spatial histogram
F
1 INTRODUCTION
The advance in wireless sensor technologies has resulted
in many new applications for military and/or civilian
purposes. Many cases of these applications rely on the
information of personal locations, for example, surveillance
and location systems. These location-dependent
systems are realized by using either identity sensors
or counting sensors. For identity sensors, for example,
Bat [1] and Cricket [2], each individual has to carry
a signal sender/receiver unit with a globally unique
identier. With identity sensors, the system can pinpoint
the exact location of each monitored person. On the
other hand, counting sensors, for example, photoelectric
sensors [3], [4], and thermal sensors [5], are deployed
to report the number of persons located in their sensing
areas to a server.
Unfortunately, monitoring personal locations with a
potentially untrusted system poses privacy threats to
the monitored individuals, because an adversary could
abuse the location information gathered by the system to
infer personal sensitive information [2], [6], [7], [8]. For
the location monitoring system using identity sensors,
the sensor nodes report the exact location information of
the monitored persons to the server; thus using identity
sensors immediately poses a major privacy breach. To
Chi-Yin Chow, Mohamed F. Mokbel, and Tian He are with the Department
of Computer Science and Engineering, University of Minnesota, Minneapolis,
MN 55455, USA, email: fcchow, mokbel, tianheg[at]cs.umn.edu.
This research was partially supported by NSF Grants IIS-0811998, IIS-
0811935, CNS-0708604, CNS-0720465, and CNS-0626614, and a Microsoft
Research Gift.
tackle such a privacy breach, the concept of aggregate
location information, that is, a collection of location data
relating to a group or category of persons from which
individual identities have been removed [8], [9], has been
suggested as an effective approach to preserve location
privacy [6], [8], [9]. Although the counting sensors by nature
provide aggregate location information, they would
also pose privacy breaches.
Figure 1 gives an example of a privacy breach in a
location monitoring system with counting sensors. There
are 11 counting sensor nodes installed in nine rooms R1
to R9, and two hallways C1 and C2 (Figure 1a). The nonzero
number of persons detected by each sensor node is
depicted as a number in parentheses. Figures 1b and 1c
(a) At time ti
(b) At time ti+1
© At time ti+2
Fig. 1: A location monitoring system using counting
sensors.
IEEE TRANSACTIONS ON MOBILE COMPUTING, VOL. 10, NO. 1, Jan 2011
2
give the numbers reported by the same set of sensor
nodes at two consecutive time instances ti+1 and ti+2,
respectively. If R3 is Alice's ofce room, an adversary
knows that Alice is in room R3 at time ti. Then the
adversary knows that Alice left R3 at time ti+1 and went
to C2 by knowing the number of persons detected by
the sensor nodes in R3 and C2. Likewise, the adversary
can infer that Alice left C2 at time ti+2 and went to R7.
Such knowledge leakage may lead to several privacy
threats. For example, knowing that a person has visited
certain clinical rooms may lead to knowing the her
health records. Also, knowing that a person has visited
a certain bar or restaurant in a mall building may reveal
condential personal information.
This paper proposes a privacy-preserving location
monitoring system for wireless sensor networks to provide
monitoring services. Our system relies on the well
established k-anonymity privacy concept, which requires
each person is indistinguishable among k persons. In our
system, each sensor node blurs its sensing area into a
cloaked area, in which at least k persons are residing. Each
sensor node reports only aggregate location information,
which is in a form of a cloaked area, A, along with the
number of persons, N, located in A, where N k, to the
server. It is important to note that the value of k achieves
a trade-off between the strictness of privacy protection
and the quality of monitoring services. A smaller k indicates
less privacy protection, because a smaller cloaked
area will be reported from the sensor node; hence better
monitoring services. However, a larger k results in a
larger cloaked area, which will reduce the quality of
monitoring services, but it provides better privacy protection.
Our system can avoid the privacy leakage in
the example given in Figure 1 by providing low quality
location monitoring services for small areas that the
adversary could use to track users, while providing high
quality services for larger areas. The denition of a small
area is relative to the required anonymity level, because
our system provides better quality services for the same
area if we relax the required anonymity level. Thus the
adversary cannot infer the number of persons currently
residing in a small area from our system output with
any delity; therefore the adversary cannot know that
Alice is in room R3.
To preserve personal location privacy, we propose
two in-network aggregate location anonymization algorithms,
namely, resource- and quality-aware algorithms.
Both algorithms require the sensor nodes to collaborate
with each other to blur their sensing areas into cloaked
areas, such that each cloaked area contains at least k
persons to constitute a k-anonymous cloaked area. The
resource-aware algorithm aims to minimize communication
and computational cost, while the quality-aware
algorithm aims to minimize the size of the cloaked areas,
in order to maximize the accuracy of the aggregate
locations reported to the server. In the resource-aware
algorithm, each sensor node nds an adequate number
of persons, and then it uses a greedy approach to nd a
cloaked area. On the other hand, the quality-aware algorithm
starts from a cloaked area A, which is computed by
the resource-aware algorithm. Then A will be iteratively
rened based on extra communication among the sensor
nodes until its area reaches the minimal possible size. For
both algorithms, the sensor node reports its cloaked area
with the number of monitored persons in the area as an
aggregate location to the server.
Although our system only knows the aggregate location
information about the monitored persons, it can
still provide monitoring services through answering aggregate
queries, for example, What is the number of
persons in a certain area? To support these monitoring
services, we propose a spatial histogram that analyzes the
gathered aggregate locations to estimate the distribution
of the monitored persons in the system. The estimated
distribution is used to answer aggregate queries.
We evaluate our system through simulated experiments.
The results show that the communication and
computational cost of the resource-aware algorithm
is lower than the quality-aware algorithm, while the
quality-aware algorithm provides more accurate monitoring
services (the average accuracy is about 90%) than
the resource-aware algorithm (the average accuracy is
about 75%). Both algorithms only reveal k-anonymous
aggregate location information to the server, but they are
suitable for different system settings. The resource-aware
algorithm is suitable for the system, where the sensor
nodes have scarce communication and computational
resources, while the quality-aware algorithm is favorable
for the system, where accuracy is the most important
factor in monitoring services.
The rest of this paper is organized as follows. Our
system model is outlined in Section 2. Section 3 presents
the resource- and quality-aware location anonymization
algorithms. Section 4 describes the aggregate query processing.
We describe an attacker model and the experiment
setting of our system in Section 5. The experimental
results are given in Section 6. Section 7 highlights the
related work. Finally, Section 8 concludes the paper.
2 SYSTEM MODEL
Figure 2 depicts the architecture of our system, where
there are three major entities, sensor nodes, server, and
system users. We will dene the problem addressed by
our system, and then describe the detail of each entity
and the privacy model of our system.
Problem denition. Given a set of sensor nodes s1; s2;
: : : ; sn with sensing areas a1; a2; : : : ; an, respectively,
a set of moving objects o1; o2; : : : ; om, and a required
anonymity level k, (1) we nd an aggregate location
for each sensor node si in a form of Ri = (Areai ;Ni),
where Areai is a rectangular area containing the sensing
area of a set of sensor nodes Si and Ni is the number
of objects residing in the sensing areas of the sensor
nodes in Si, such that Ni k, Ni = j [sj2Si Oj j k,
Oj = foljol 2 ajg, 1 i n, and 1 l m; and (2) we
IEEE TRANSACTIONS ON MOBILE COMPUTING, VOL. 10, NO. 1, Jan 2011
3
Fig. 2: System architecture.
build a spatial histogram to answer an aggregate query
Q that asks about the number of objects in a certain area
Q:Area based on the aggregate locations reported from
the sensor nodes.
Sensor nodes. Each sensor node is responsible for determining
the number of objects in its sensing area, blurring
its sensing area into a cloaked area A, which includes
at least k objects, and reporting A with the number of
objects located in A as aggregate location information
to the server. We do not have any assumption about
the network topology, as our system only requires a
communication path from each sensor node to the server
through a distributed tree [10]. Each sensor node is also
aware of its location and sensing area.
Server. The server is responsible for collecting the aggregate
locations reported from the sensor nodes, using
a spatial histogram to estimate the distribution of the
monitored objects, and answering range queries based
on the estimated object distribution. Furthermore, the
administrator can change the anonymized level k of the
system at anytime by disseminating a message with a
new value of k to all the sensor nodes.
System users. Authenticated administrators and users
can issue range queries to our system through either the
server or the sensor nodes, as depicted in Figure 2. The
server uses the spatial histogram to answer their queries.
Privacy model. In our system, the sensor nodes constitute
a trusted zone, where they behave as dened in
our algorithm and communicate with each other through
a secure network channel to avoid internal network
attacks, for example, eavesdropping, trafc analysis, and
malicious nodes [6], [11]. Since establishing such a secure
network channel has been studied in the literature [6],
[11], the discussion of how to get this network channel is
beyond the scope of this paper. However, the solutions
that have been used in previous works can be applied
to our system. Our system also provides anonymous
communication between the sensor nodes and the server
by employing existing anonymous communication techniques
[12], [13]. Thus given an aggregate location R,
the server only knows that the sender of R is one of the
sensor nodes within R. Furthermore, only authenticated
administrators can change the k-anonymity level and the
spatial histogram size. In emergency cases, the administrators
can set the k-anonymity level to a small value
to get more accurate aggregate locations from the sensor
nodes, or even set it to zero to disable our algorithm to
get the original readings from the sensor nodes, in order
to get the best services from the system. Since the server
and the system user are outside the trusted zone, they
are untrusted.
We now discuss the privacy threat in existing location
monitoring systems. In an identity-sensor location monitoring
system, since each sensor node reports the exact
location information of each monitored object to the
server, the adversary can pinpoint each object's exact location.
On the other hand, in a counting-sensor location
monitoring system, each sensor node reports the number
of objects in its sensing area to the server. The adversary
can map the monitored areas of the sensor nodes to the
system layout. If the object count of a monitored area is
very small or equal to one, the adversary can infer the
identity of the monitored objects based on the mapped
monitored area, for example, Alice is in her ofce room
at time instance ti in Figure 1.
Since our system only allows each sensor node to
report a k-anonymous aggregate location to the server,
the adversary cannot infer an object's exact location with
any delity. The larger the anonymity level, k, the more
difcult for the adversary to infer the object's exact
location. With the k-anonymized aggregate locations
reported from the sensor nodes, the underlying spatial
histogram at the server provides low quality location
monitoring services for a small area, and better quality
services for larger areas. This is a nice privacy-preserving
feature, because the object count of a small area is
more likely to reveal personal location information. The
denition of a small area is relative to the required
anonymity level, because our system provides lower
quality services for the same area if the anonymized
level gets stricter. We will also describe an attack model,
where we stimulate an attacker that could be a system
user or the server attempting to infer the object count of
a particular sensor node in Section 5.1. We evaluate our
system's resilience to the attack model and its privacy
protection in Section 6.