# A Privacy-Preserving Location-Based System for Continuous Spatial Queries

Authors: Doohee Song; Kwangjin Park
Journal: Mobile Information Systems
 (2016)

---

## Abstract

K-anonymization generated a cloaked region (CR) that was K-anonymous; that is, the query issuer was indistinguishable from K-1 other users (nearest neighbors) within the CR. This reduced the probability of the query issuer’s location being exposed to untrusted parties (1/K). However, location cloaking is vulnerable to query tracking attacks, wherein the adversary can infer the query issuer by comparing the two regions in continuous LBS queries. This paper proposes a novel location cloaking method to resist this attack. The target systems of the proposed method are road networks where the mobile clients’ trajectories are fixed (the road network is preknown and fixed, instead of the trajectories), such as subways, railways, and highways. The proposed method, called adaptive-fixed K-anonymization (A-KF), takes this issue into account and generates smaller CRs without compromising the privacy of the query issuer’s location. Our results show that the proposed A-KF method outperforms previous location cloaking methods.


---

## Body

## 1. Introduction

With the growth of location-based services (LBS) in mobile computing, many businesses are interested in analyzing user location data to better understand patterns and relationships. For example, social marketing relying on social network services takes the form of coupons or advertising directed at customers based on their current locations. In general, mobile clients must expose their exact location information to an LBS provider before receiving their desired services. The location of a mobile client can be obtained via a variety of outdoor and indoor positioning technologies (e.g., Global Positioning System and Wi-Fi). LBS include services to identify the location of a person or object, such as the nearest point of interest (POI) or the whereabouts of a friend or employee. Typical LBS applications include road navigation and vehicle tracking services [1–4]. As LBS have become more numerous and diverse, user privacy violations have become more commonplace. Unfortunately, laws and regulations regarding LBS and location privacy have tended to become less rigorous. This paper proposes a technical approach for location data protection in LBS. For example, when a user sends a continuous K-anonymity query, the number of K-1 clients may change the expected user. Thus, a user’s ID will be exposed by the service provider. In other words, the service provider can store the information from user’s query contents and cloaked regions (CRs) from client. Therefore, we propose a novel algorithm to protect users’ query contents and CRs (trajectory). In this scheme, if random KF were to travel in opposite directions from the user, the CRs would increase, at which point a service provider may search many POIs.Much research has been done on protecting a user’s location. Yi et al. [5] introduced a method for protecting various categories of data. The first categories were information access control, mix-zone, and K-anonymity. To function, this method required an anonymization server; a trusted server, such as middleware, that functioned as an intermediary between the client and the LBS server; and every client to be stored in the anonymization server.The secondary categories were dummy location, geographic data transformation, and private information retrieval (PIR). Within these categories, the anonymization server could be exposed to an adversary. Therefore, a user had to make a dummy to protect his or her position using the dummy technique. Alternatively, the PIR technique required more than one server (K≥2).We propose protecting users’ locations using aK-anonymity technique. The K-anonymity functions as follows.Location cloaking blurs a user’s location into a CR that satisfies the privacy parameter (theK-anonymity metric) specified by the user at query time. Location cloaking has attracted a tremendous amount of research as a solution to protect user privacy in LBS. Previous location cloaking methods perform K-anonymization (i.e., identification of K-anonymous users) at the moment that a user issues a query with K-anonymity [6–11].Figure1 illustrates an example of 4-anonymization. The anonymization server, a trusted third party that functions as an intermediary between the client and the LBS server, identifies a CR that satisfies the 4-anonymity requirement. This enables the query issuer to have the query result without disclosing his or her exact location to the LBS server. K-anonymization generates a CR that is K-anonymous; that is, the query issuer is indistinguishable from K-1 other users (nearest neighbors) within the CR. This reduces the probability of the query issuer’s location being exposed to untrusted parties to 1/K. However, location cloaking is vulnerable to query tracking attacks, and a query issuer is not safe when launching continuous LBS queries. For example, if a client issues two queries at times  t-1 and t with corresponding CRs, it is easy for an adversary to compare these two regions to find the query issuer [12–15].Figure 1
An example ofK-anonymization (K=4).This paper proposes a novel location cloaking method calledA-KF that resists query tracking attacks. This proposed method can generate minimized CRs while protecting the location and trajectory privacy of the query issuer.The contributions of this paper are as follows.(i)
A systematic model prevents both the query contents and CRs (trajectory) from being exposed to continuous spatial queries, because the query issuer is indistinguishable fromKF.(ii)
The proposal of an effective anonymization method,A-KF, can reduce CRs within KF and resist query tracking attacks (refer to Section 4). Previous location cloaking methods [15, 16] perform K-anonymization at each moment, whereas the proposed method prevents a query’s trajectory from KF.(iii)
The demonstration of the performance of the proposed method is presented in a variety of settings.The rest of the paper is organized as follows. Section2 reviews existing works on location anonymity. Section 3 introduces the problem statement, and Section 4 presents the system model and algorithms for the proposed method. In Section 5, the results of the experiment are presented. Finally, Section 6 concludes the paper.The terms frequently used in this paper are defined in Definition of Terms Section.


## 2. Related Work

### 2.1. Issues Related to Location Privacy Protection

Today’s mobile devices, typically smartphones, enable users to gain access to various LBS that provide dynamic content based on the user’s location. In LBS, the transmission and sharing of user location data are necessary, and such data can be analyzed by third parties for various purposes. For example, one can infer sensitive private information about a person’s health conditions or lifestyle by analyzing his or her whereabouts, length of stay, and movement patterns. Analyzing user locations along with other personal information such as credit card details allows for the creation of more sophisticated and precise user information, which also gives rise to privacy and safety concerns. Hence, businesses and government organizations have made numerous efforts to protect location privacy. However, mandatory controls and regulatory standards that determine the priority between protection of location privacy and development of LBS and other location-based technologies are still lacking; therefore, there are currently no clear and objective criteria regarding this issue [17–20].


### 2.2. Research Trends

Among various techniques that aim to protect the privacy of LBS users, a dummy is created when the mobile user queries the LBS, during which he or she sends many random locations to the LBS provider to obfuscate his or her location. However, the dummy is not derived from real clients. Thus, we cannot compare our method with the dummy method [21].Private information retrieval (PIR) allows a user to retrieve a record from servers. To do so, PIR needs more than one server (K≥2). Therefore, this technique cannot be compared with our technique [22–24].Location cloaking based onK-anonymity predominates and a great deal of research has been conducted on this technique [6–15, 25–30].Figure1 presents an example of 4-anonymization. In this example, the minimum CR that satisfies the 4-anonymity requirement is outlined by a red rectangle (the CR contains 4-anonymous clients Cq, C1, C2, and C4). One problem this presents is that the size of the CR can increase when all K clients are kept in the CR after they are selected. To address this problem, a method that forms a CR with K-1 clients that are nearest to the query issuer at a given time has been suggested. However, this method is vulnerable to query tracking attacks. It is very likely that the initial CR members other than the query issuer are updated in continuous queries. The adversary can easily guess the authentic query issuer by monitoring the CRs at different time points, and the one that constantly remains in the CRs is the query issuer (e.g., Cq,C1,C2,C4→Cq,C8,C10,C12).Solutions have been proposed to resolve this problem. In [7], K-1 clients are found in proximity to the query issuer and a temporary CR is set that is twice as large as the initially calculated CR. In this method, the anonymization server must calculate the movement paths of all the clients, which increases the computational cost. Additionally, the accuracy of query results might be low due to the use of a movement probability matrix.


## 2.1. Issues Related to Location Privacy Protection

Today’s mobile devices, typically smartphones, enable users to gain access to various LBS that provide dynamic content based on the user’s location. In LBS, the transmission and sharing of user location data are necessary, and such data can be analyzed by third parties for various purposes. For example, one can infer sensitive private information about a person’s health conditions or lifestyle by analyzing his or her whereabouts, length of stay, and movement patterns. Analyzing user locations along with other personal information such as credit card details allows for the creation of more sophisticated and precise user information, which also gives rise to privacy and safety concerns. Hence, businesses and government organizations have made numerous efforts to protect location privacy. However, mandatory controls and regulatory standards that determine the priority between protection of location privacy and development of LBS and other location-based technologies are still lacking; therefore, there are currently no clear and objective criteria regarding this issue [17–20].


## 2.2. Research Trends

Among various techniques that aim to protect the privacy of LBS users, a dummy is created when the mobile user queries the LBS, during which he or she sends many random locations to the LBS provider to obfuscate his or her location. However, the dummy is not derived from real clients. Thus, we cannot compare our method with the dummy method [21].Private information retrieval (PIR) allows a user to retrieve a record from servers. To do so, PIR needs more than one server (K≥2). Therefore, this technique cannot be compared with our technique [22–24].Location cloaking based onK-anonymity predominates and a great deal of research has been conducted on this technique [6–15, 25–30].Figure1 presents an example of 4-anonymization. In this example, the minimum CR that satisfies the 4-anonymity requirement is outlined by a red rectangle (the CR contains 4-anonymous clients Cq, C1, C2, and C4). One problem this presents is that the size of the CR can increase when all K clients are kept in the CR after they are selected. To address this problem, a method that forms a CR with K-1 clients that are nearest to the query issuer at a given time has been suggested. However, this method is vulnerable to query tracking attacks. It is very likely that the initial CR members other than the query issuer are updated in continuous queries. The adversary can easily guess the authentic query issuer by monitoring the CRs at different time points, and the one that constantly remains in the CRs is the query issuer (e.g., Cq,C1,C2,C4→Cq,C8,C10,C12).Solutions have been proposed to resolve this problem. In [7], K-1 clients are found in proximity to the query issuer and a temporary CR is set that is twice as large as the initially calculated CR. In this method, the anonymization server must calculate the movement paths of all the clients, which increases the computational cost. Additionally, the accuracy of query results might be low due to the use of a movement probability matrix.


## 3. Problem Statement

This section presents the definitions for the proposedA-KF method. Previous location anonymization methods have experienced location privacy threats related to continuous queries, as depicted in Figure 2. A-KF method proposed in this paper is designed to solve this problem. The terms and variables frequently used in the proposed method are summarized in Definition of Terms Section.Figure 2
AK-anonymization problem related to continuous spatial queries.
(a)
t = 1 (b)
t = 2Definition 1.
A given set of clients,C, includes CN (CN≥K). That is, C∋CN∋A-KF (CN: candidate set of K close to a querier).Definition 2.
A- K F = K and A-KF=KF+KNF (refer to Definition of Terms Section).
The criteria for selecting A-KF are as follows: (1) CN denotes the number of clients that are searched by Cq (CN=CN+Cq) and, (2) among CN members, those with the smallest distance between the origin and the destination are chosen as KF members (KF∋Cq).Definition 3.
Under fixed-K, KF=K. KF is greater than or equal to 1 and less than or equal to K(K≥KF≥1) (refer to Definition of Terms Section).Definition 4.
A set of clients,C, includes Cq and CN={C1,C2,…,Cn-1,Cn,Cq} (CN must be greater than K and can include all the clients except Cq).In Figure1, CN={C1,C2,…,C11,C12,Cq}. In Figure 2, when CN=4 and KF=2, Algorithm 1 computes that KF member other than Cq is C2; that is, KF={Cq,C2}.Algorithm 1:Query issuer’s query request.
Input: q (query issuer’s point location), K (number of requested clients for anonymity) Output: A CR satisfying the user-specified K-anonymity requirement (1) Check q; (2) Calculate the minimum distance (R=∞, K = null); (3) Obtain the CRs satisfying the K-anonymity requirement from the anonymizer; (4) Choose the CR requested by the query issuer; (5) Send a query with the chosen CR to the anonymizer;Figure2 depicts the problem in which the location of the querying client can be exposed in continuous queries with K-anonymity. Figure 1 shows 4-anonymization at time t=0, and Figures 2(a) and 2(b) present 4-anonymization at t=1 and t=2, respectively (CRs are represented by a rectangle). This example indicates that the location of Cq as well as its trajectory can be disclosed over time. When the CR is increased to reduce the probability of revealing a query issuer’s location, it may be necessary for the LBS server to send more objects corresponding to the increased CR to the query issuer, which increases the communication and computational costs.Alternatively, loweringK of the K-anonymity requirement decreases the size of the CR but increases the probability of exposing a query issuer’s location to third parties. The proposed method assumes a road network environment where the client movement trajectories are fixed (e.g., subway, railway, and highway networks). Suppose that the clients nearest to the query issuer are selected as fixed CR members in such an environment. If clients that move in directions opposite to a query issuer are bounded in a CR along with the query issuer, the size of the CR increases dramatically over time.


## 4. Protection of User Location and Trajectory Privacy

### 4.1. System Model

In Figure1, Cq issues a query with 4-anonymity (i.e., K=4). The anonymizer (Algorithm 2), a location anonymization server in a LBS system that knows the locations of clients and generates blurred locations for them, checks the locations of all clients Ci and generates a minimum CR that contains 4 clients including Cq (see the solid rectangle in Figure 1).Algorithm 2:Anonymizer’s query processing.
Input: query issuer’s current location and destination, CR chosen by the query issuer, K and KF (number of clients for location anonymity), content of the query Output: K-anonymous clients in a minimum CR, KF member clients (1) Check the CR chosen by the query issuer using the anonymizer; (2) Calculate the minimum distance (K, KF, KNF, K[i] = null); (3) if  K<KF+KNF-1  then return 0 (4)  e←0 (5)  while  e≠K (6)   e←K (7)   Ki=e; (8)   i++; (9)    if (i<K-2); (10)      continuous; (11)     else end if; (12)   end while; (13) if (periodically measure the CRs of dist(q, K[i]) and sort the CRs in ascending order (i.e., from the smallest to the largest)) (14) return  K[i]; (ith is from 1 to K)The anonymization server then sends queries with CRs to the LBS server that stores information about the queried objects.In the proposed method, the query issuer first determines the destination,K (nonfixed K (KNF) + fixed K (KF)), and CN (the number of clients for selecting KF members). The query issuer then issues a nearest-neighbor query (CN⊃K⊃KF⊃Cq). The anonymizer checks the current locations and the destinations of the clients. As CN increases, the computational cost increases, but the size of the CRs decreases.WhenCq moves from the origin to the destination, the clients are sorted so that those nearest to Cq are listed first (∑t=0t=qdist(C0,Ci)). Subsequently, the top KF clients in the sorted list are selected as KF members (KF is given by the query issuer). This procedure is represented in Algorithm 1.


### 4.2. Adaptive-FixedK-Anonymization (A-KF)

In Figure3(a), Cq’s nearest neighbors are C1, C2, and C4 when CN=4. At t=0, the client nearest to Cq is C4, the second nearest is C1, and the third nearest is C2. Thus, the sorted order of CN member clients is {Cq,C4,C1,C2}. Figures 3(b) and 3(c) show that the movement of clients will cause changes in the distance between CN members and Cq. Suppose that the time period between the moment that a client issues a query and the moment that the client arrives at the destination is T. T is divided by n (T/n=t), and the distances of Ci (CN⊃Ci) to Cq are calculated at every t second. In Figures 3(a)–3(c), the movement of Cq is depicted, and the sorted order of CN members is changed to {C2,C4,C1} according to the updated distance, ∑t=0t=ndist(Cq,Ci). KF members are Cq and C2 when KF=2. And Figure 4 shows that KF members are Cq, C2, C4, and, C1 when KF=4.Figure 3
An example of adaptive-fixed 2-anonymization (CN=4).Figure 4
An example of adaptive-fixed 4-anonymization (CN=4).In Figures4(a)–4(c), the movement of Cq is depicted, and the sorted order of CN members is changed to {C2,C4,C1} according to the updated area, ∑t=0t=narea(Cq,Ci). The proposed method selects CN and KF based on the query issuer’s request. To decrease the amount of information to be transmitted while preserving location privacy, the anonymizer generates a minimum bounding rectangle (MBR) that includes the CRs.


## 4.1. System Model

In Figure1, Cq issues a query with 4-anonymity (i.e., K=4). The anonymizer (Algorithm 2), a location anonymization server in a LBS system that knows the locations of clients and generates blurred locations for them, checks the locations of all clients Ci and generates a minimum CR that contains 4 clients including Cq (see the solid rectangle in Figure 1).Algorithm 2:Anonymizer’s query processing.
Input: query issuer’s current location and destination, CR chosen by the query issuer, K and KF (number of clients for location anonymity), content of the query Output: K-anonymous clients in a minimum CR, KF member clients (1) Check the CR chosen by the query issuer using the anonymizer; (2) Calculate the minimum distance (K, KF, KNF, K[i] = null); (3) if  K<KF+KNF-1  then return 0 (4)  e←0 (5)  while  e≠K (6)   e←K (7)   Ki=e; (8)   i++; (9)    if (i<K-2); (10)      continuous; (11)     else end if; (12)   end while; (13) if (periodically measure the CRs of dist(q, K[i]) and sort the CRs in ascending order (i.e., from the smallest to the largest)) (14) return  K[i]; (ith is from 1 to K)The anonymization server then sends queries with CRs to the LBS server that stores information about the queried objects.In the proposed method, the query issuer first determines the destination,K (nonfixed K (KNF) + fixed K (KF)), and CN (the number of clients for selecting KF members). The query issuer then issues a nearest-neighbor query (CN⊃K⊃KF⊃Cq). The anonymizer checks the current locations and the destinations of the clients. As CN increases, the computational cost increases, but the size of the CRs decreases.WhenCq moves from the origin to the destination, the clients are sorted so that those nearest to Cq are listed first (∑t=0t=qdist(C0,Ci)). Subsequently, the top KF clients in the sorted list are selected as KF members (KF is given by the query issuer). This procedure is represented in Algorithm 1.


## 4.2. Adaptive-FixedK-Anonymization (A-KF)

In Figure3(a), Cq’s nearest neighbors are C1, C2, and C4 when CN=4. At t=0, the client nearest to Cq is C4, the second nearest is C1, and the third nearest is C2. Thus, the sorted order of CN member clients is {Cq,C4,C1,C2}. Figures 3(b) and 3(c) show that the movement of clients will cause changes in the distance between CN members and Cq. Suppose that the time period between the moment that a client issues a query and the moment that the client arrives at the destination is T. T is divided by n (T/n=t), and the distances of Ci (CN⊃Ci) to Cq are calculated at every t second. In Figures 3(a)–3(c), the movement of Cq is depicted, and the sorted order of CN members is changed to {C2,C4,C1} according to the updated distance, ∑t=0t=ndist(Cq,Ci). KF members are Cq and C2 when KF=2. And Figure 4 shows that KF members are Cq, C2, C4, and, C1 when KF=4.Figure 3
An example of adaptive-fixed 2-anonymization (CN=4).Figure 4
An example of adaptive-fixed 4-anonymization (CN=4).In Figures4(a)–4(c), the movement of Cq is depicted, and the sorted order of CN members is changed to {C2,C4,C1} according to the updated area, ∑t=0t=narea(Cq,Ci). The proposed method selects CN and KF based on the query issuer’s request. To decrease the amount of information to be transmitted while preserving location privacy, the anonymizer generates a minimum bounding rectangle (MBR) that includes the CRs.


## 5. Performance Evaluation

Figure5 shows the possible directions of movement of a client. Initially, a query issuer Cq can move in one of eight different directions (w=0 through w=7). After t+1, Cq moves to w=2. It is assumed that Cq can move in the directions at a ±45° angle from the current direction of movement. Here, the client moved in a set direction. This assumption was made to obscure a client’s movement pattern because, if a client was moving back and forth repeatedly, there might be a discernible location.Figure 5
Directions of movement of a mobile client.
(a)
t (b)
t + 1


### 5.1. Experimental Settings

This section evaluates the performance of the proposed method in comparison with that of the existing AMV method. The experiments were carried out using a computer with a 2.9 GHz processor, 4 GB memory, and Microsoft visual C++ 6.0. It was assumed that LBS clients are moving and that they are evenly distributed throughout the grid cells. The dataset comprised simulated uniform data. The length of a single grid cell was assumed to be 1 meter (m), and time (t) was in seconds. Our proposed method was compared with all fixed K [16] and nonfixed K [15] methods. We assumed the service provider and anonymization server in our experimental environment [15]. Table 1 describes the parameter settings for the experiments.Table 1
Experimental environment.
Parameter Setting values Number of gird cells 200 × 200 Number of clients 4,000 Client’s movement radius (number of grids) 1~3 K-anonymity (K) 10 Update time (sec;t) 0, 2, 4, 6 The average number of experiments 10,000


### 5.2. Experiment Results

Figure6 shows how the sizes of the CRs associated with fixed anonymous clients (KF) change over time. When K=5, KF is 2. The fixed-K method determines which five clients are nearest to the query issuer (KF=5). A-KF method generates a CR for the query issuer when CN=10 and KF=2 (in which case a reconfiguration is needed). Compared to the AMV method, the sizes of the CRs created by A-KF method are 12% lower. The proposed A-KF method can generate smaller CRs than the AMV method because A-KF selects optimal KF clients by monitoring CN members’ movements and updating the distances of moving clients to the query issuer Cq.Figure 6
The sizes of the CRs over time.Figure7 shows the sizes of the CRs, which change in connection with changes in CN. Here, K is 5. At t=0, the sizes of the CRs created by the proposed A-KF method increase as CN increases. This is because CN member clients that have the same destination as the query issuer must be searched, increasing the initial computational cost. However, the expansion ratios of the CRs gradually decrease over time.Figure 7
The sizes of the CRs with regard to changes inCN.Figure8 shows the sizes of the CRs with regard to changes in KF (the number of fixed anonymous clients). When K=5, KF can be 2, 3, or 4. The fixed-K method selects the five clients nearest to the query issuer as KF members. A-KF method generates the CRs for the query issuer with CN=10 and KF=2.Figure 8
The sizes of the CRs with regard to changes inKF.Figure9 shows the sizes of the CRs, which vary according to the velocity (V) of the clients’ movement. It is assumed that the clients’ speeds are 1 m, 3 m, and 5 m per second. The CRs created by the proposed A-KF method when V=1 are smaller than those created when V=3 by 29.9%, and they are smaller than those created when V=5 by 42.7%. That is, the size of the CR increases as V increases.Figure 9
The sizes of the CRs with regard to changes in velocity (V).Figure10 presents the number of queried objects, which changes according to changes in KF. As shown in Figure 8, the sizes of the CRs increase as KF increases. This implies that the search area for the query issuer increases as KF increases, which, in turn, increases the number of objects to be searched.Figure 10
The numbers of queried objects with regard to changes inKF.Figure11 presents the sizes of the CRs in connection with changes in the number of LBS clients. The sizes of the CRs decrease as the number of clients increases. This is because LBS clients become more densely populated in a grid map.Figure 11
The sizes of the CRs with regard to the number of clients.Figure12 shows how K (the anonymity degree) changes under the three different anonymization methods over time. At t=0, both the AMV and A-KF methods have the same K (K=10). CN is fixed at 20, and KF is fixed at 5. As time passes, the anonymity level K gradually decreases, except for under the fixed-K method. K drops to nearly 1 under the AMV method, and K decreases to 4 as t increases under A-KF method.Figure 12
Changes inK over time.Figure13 presents the probability of protecting a query issuer’s location at different time points t. As described in Figure 12, K decreases over time in the AMV and A-KF methods and is unable to meet the requested anonymity metric of 10. This increases the probability of revealing a query issuer’s location to third parties.Figure 13
The accuracies of theK-anonymization methods over time.


## 5.1. Experimental Settings

This section evaluates the performance of the proposed method in comparison with that of the existing AMV method. The experiments were carried out using a computer with a 2.9 GHz processor, 4 GB memory, and Microsoft visual C++ 6.0. It was assumed that LBS clients are moving and that they are evenly distributed throughout the grid cells. The dataset comprised simulated uniform data. The length of a single grid cell was assumed to be 1 meter (m), and time (t) was in seconds. Our proposed method was compared with all fixed K [16] and nonfixed K [15] methods. We assumed the service provider and anonymization server in our experimental environment [15]. Table 1 describes the parameter settings for the experiments.Table 1
Experimental environment.
Parameter Setting values Number of gird cells 200 × 200 Number of clients 4,000 Client’s movement radius (number of grids) 1~3 K-anonymity (K) 10 Update time (sec;t) 0, 2, 4, 6 The average number of experiments 10,000


## 5.2. Experiment Results

Figure6 shows how the sizes of the CRs associated with fixed anonymous clients (KF) change over time. When K=5, KF is 2. The fixed-K method determines which five clients are nearest to the query issuer (KF=5). A-KF method generates a CR for the query issuer when CN=10 and KF=2 (in which case a reconfiguration is needed). Compared to the AMV method, the sizes of the CRs created by A-KF method are 12% lower. The proposed A-KF method can generate smaller CRs than the AMV method because A-KF selects optimal KF clients by monitoring CN members’ movements and updating the distances of moving clients to the query issuer Cq.Figure 6
The sizes of the CRs over time.Figure7 shows the sizes of the CRs, which change in connection with changes in CN. Here, K is 5. At t=0, the sizes of the CRs created by the proposed A-KF method increase as CN increases. This is because CN member clients that have the same destination as the query issuer must be searched, increasing the initial computational cost. However, the expansion ratios of the CRs gradually decrease over time.Figure 7
The sizes of the CRs with regard to changes inCN.Figure8 shows the sizes of the CRs with regard to changes in KF (the number of fixed anonymous clients). When K=5, KF can be 2, 3, or 4. The fixed-K method selects the five clients nearest to the query issuer as KF members. A-KF method generates the CRs for the query issuer with CN=10 and KF=2.Figure 8
The sizes of the CRs with regard to changes inKF.Figure9 shows the sizes of the CRs, which vary according to the velocity (V) of the clients’ movement. It is assumed that the clients’ speeds are 1 m, 3 m, and 5 m per second. The CRs created by the proposed A-KF method when V=1 are smaller than those created when V=3 by 29.9%, and they are smaller than those created when V=5 by 42.7%. That is, the size of the CR increases as V increases.Figure 9
The sizes of the CRs with regard to changes in velocity (V).Figure10 presents the number of queried objects, which changes according to changes in KF. As shown in Figure 8, the sizes of the CRs increase as KF increases. This implies that the search area for the query issuer increases as KF increases, which, in turn, increases the number of objects to be searched.Figure 10
The numbers of queried objects with regard to changes inKF.Figure11 presents the sizes of the CRs in connection with changes in the number of LBS clients. The sizes of the CRs decrease as the number of clients increases. This is because LBS clients become more densely populated in a grid map.Figure 11
The sizes of the CRs with regard to the number of clients.Figure12 shows how K (the anonymity degree) changes under the three different anonymization methods over time. At t=0, both the AMV and A-KF methods have the same K (K=10). CN is fixed at 20, and KF is fixed at 5. As time passes, the anonymity level K gradually decreases, except for under the fixed-K method. K drops to nearly 1 under the AMV method, and K decreases to 4 as t increases under A-KF method.Figure 12
Changes inK over time.Figure13 presents the probability of protecting a query issuer’s location at different time points t. As described in Figure 12, K decreases over time in the AMV and A-KF methods and is unable to meet the requested anonymity metric of 10. This increases the probability of revealing a query issuer’s location to third parties.Figure 13
The accuracies of theK-anonymization methods over time.


## 6. Conclusion

This paper stated a drawback of existingK-anonymous location cloaking methods that can occur in continuous LBS queries and proposed A-KF method, which is effective in preventing this problem. The proposed A-KF method determines K based on the query issuer’s request, increasing the query issuer’s satisfaction and decreasing the workload in the anonymization server. The proposed method can achieve smaller CRs than existing location anonymization methods while preserving K-anonymity.In the future, the movement information of mobile LBS clients will be analyzed, and the proposed A-KF method will be further refined to query requests for time and conditions. Additionally, algorithms to reduce errors that occur in the process of a movement information analysis will be studied.



---

*Source: 6182769-2016-10-24.xml*