# KLPPS: Ak-Anonymous Location Privacy Protection Scheme via Dummies and Stackelberg Game

Authors: Dongdong Yang; Baopeng Ye; Wenyin Zhang; Huiyu Zhou; Xiaobin Qian
Journal: Security and Communication Networks
 (2021)

---

## Abstract

Protecting location privacy has become an irreversible trend; some problems also come such as system structures adopted by location privacy protection schemes suffer from single point of failure or the mobile device performance bottlenecks, and these schemes cannot resist single-point attacks and inference attacks and achieve a tradeoff between privacy level and service quality. To solve these problems, we propose ak-anonymous location privacy protection scheme via dummies and Stackelberg game. First, we analyze the merits and drawbacks of the existing location privacy preservation system architecture and propose a semitrusted third party-based location privacy preservation architecture. Next, taking into account both location semantic diversity, physical dispersion, and query probability, etc., we design a dummy location selection algorithm based on location semantics and physical distance, which can protect users’ privacy against single-point attack. And then, we propose a location anonymous optimization method based on Stackelberg game to improve the algorithm. Specifically, we formalize the mutual optimization of user-adversary objectives by using the framework of Stackelberg game to find an optimal dummy location set. The optimal dummy location set can resist single-point attacks and inference attacks while effectively balancing service quality and location privacy. Finally, we provide exhaustive simulation evaluation for the proposed scheme compared with existing schemes in multiple aspects, and the results show that the proposed scheme can effectively resist the single-point attack and inference attack while balancing the service quality and location privacy.


---

## Body

## 1. Introduction

With the rapid development of mobile devices and social networks, location-based service (LBS) has become a vital part of our daily activities in recent years. With smartphones or tablets, users can download location-based applications from Apple Store or Google Play Store. With the help of these applications, users can easily send queries to a service provider and obtain LBSs related to some points of interest. For example, users can check the bus schedule, the price information of nearby restaurants or gas stations, etc. Undoubtedly, by submitting LBS queries, users can enjoy the convenience provided by LBS. However, since the untrusted service provider has all the information about users such as where they are at which time, what kind of queries they submit, what they are doing, etc., he may track users in various ways or release their personal data to third parties. Thus, we need to take appropriate measures to protect users’ privacy.Many approaches [1–3] have been taken to address such privacy problems, where the location k−anonymity and location perturbation are commonly used. The existing location k−anonymity technology usually adopts the structure based on a trusted third party TTP [3]. The TTP structure refers to introduce a trusted third party, called centralized location anonymizer, between the user and the service provider, and the usage of the location anonymizer to make the target user’s information indistinguishable from that of at least k−1 other users, so that the probability of location leakage is therefore at most 1/k. Specifically, to achieve k− anonymity, an LBS-related query is submitted to the service provider via a centralized location anonymizer, which enlarges the queried location into a bigger cloaking region covering many other users (e.g., k−1 geographically. As a result, it is hard for the untrusted service provider to distinguish the user’s real location from this area. However, these approaches of using k− anonymity have a fatal problem. It heavily relies on the location anonymizer, which suffers from a single point of failure [4]. If the adversary gains control of it, the privacy of all users will be compromised.In response to the problems existed in theTTP structure, some researchers have proposed a dummy location technology that can also achieve k−anonymity, which uses an independent system structure [2]. The independent structure only contains the user and the service provider, where the user uses the mobile terminal to generate k−1 dummy locations and then sends k−1 dummy locations combined with the user’s real location to the service provider. As a result, it is hard for the untrusted service provider to distinguish the user’s real location from the other dummy locations. Since the structure achieves functions such as location anonymity and filtering query results through a mobile terminal instead of a location anonymizer, there is no single point of failure caused by the location anonymizer. In 2008, with the birth of Bitcoin [5], blockchain technology has been widely used in finance, medical care, supply chain, and other fields. Blockchain [6–8], as the underlying technology of Bitcoin, realizes distributed information interaction and collective maintenance of data in a decentralized and autonomous way, with decentralization, tamper-proof, autonomy, traceability, etc. Simultaneously, the security of consensus protocols [9] and the protection of user privacy [10] in the blockchain has become a new research hotspot. Chen et al. [11] proposed a dynamic multikey fully homomorphic encryption. The decentralized characteristic of blockchain opens a new door for location privacy protection. Based on this idea, [12] proposes a distributed k−anonymity location privacy protection scheme based on blockchain, which can also achieve k−anonymity without the help of a location anonymizer.In the LBS, the user firstly adopts approaches that are based on perturbing the information reported to the service provider, so to prevent the disclosure of one’s location. Clearly, the perturbation of the information sent to the service provider leads to a degradation of service quality, and consequently, there is a trade-off between the level of privacy that the user wishes to guarantee and the service quality loss that she will have to accept; however, the adversary formulates corresponding strategies based on the privacy protection method adopted by the user and infers the real location of the user by observing the perturbation of the information. Since the relationship between users and adversaries objectively conforms to the game relationship between participants in the Stackelberg game model, introducing the Stackelberg game method into the field of location privacy protection is an important research direction. Shokri et al. [13] took the lead in introducing the Stackelberg game into location privacy protection and proposed a location privacy protection scheme based on the Stackelberg game SG. The solution assumes that the adversary has acquired prior knowledge and allows the user and the adversary to play the game in turn: The level of privacy protection is maximized by user when the service quality loss is less than a given threshold, whereas the adversary strives to minimize the level of privacy protection based on prior knowledge and offset location. By playing the game above, this strategy can finally optimize the level of privacy protection while ensuring that the service quality loss is less than a given threshold.Based on the analysis above, the existing location privacy protection schemes have the following shortcomings: (1) the existing location privacy protection schemes either adoptTTP structure that has a single point of failure or the independent system structure. However, users in the independent structure use mobile terminals to perform location anonymity algorithms and filter query results, which will greatly increase the client’s pressure, affecting the service quality in turn. (2) On the one hand, these schemes do not fully consider the semantics, physical dispersion, and query probability of the location when selecting dummy locations. On the other hand, they do not fully consider the background knowledge that the adversary may have, which adversaries can use to infer the users’ location privacy information. So they cannot effectively resist single-point attacks and inference attacks. (3) Since such schemes need to sacrifice the service quality for improving the privacy protection level, there is no trade-off between service quality and privacy protection level. Aiming at related shortcomings above, this paper comprehensively considers features such as side information, location semantics, physical dispersion of locations combined with dummy locations, k−anonymity technology, Stackelberg game and other ideas, and then designs a k−anonymous location privacy protection scheme KLPPS based on Stackelberg game and dummy locations, which can resist single-point attacks and inference attacks while effectively balancing service quality and location privacy. Our contributions are mainly as follows:(1)
A semitrusted third partySTTP based location privacy protection structure is proposed. The STTP is based on the TTP structure by adding an encryption server and WiFi-AP, and stores the user’s privacy information on three party servers through a certain mechanism. In the STTP, even if the adversary steals the information on the location anonymizer, he still cannot locate the user and obtain the user’s complete privacy information, which effectively solves the single point of failure existed in the TTP structure. Meanwhile, the location anonymizer is responsible for implementing location anonymity algorithms and filtering query results, etc., therefore, also solve the mobile device performance bottlenecks that exist in the independent structure.(2)
We propose a dummy location selection algorithm based on location semantics and physical distanceSPDDS. Compared with existing dummy location selection algorithms, SPDDS takes into account the characteristics such as location semantic diversity, physical dispersion, query probability and offset location when selecting dummy locations, which can effectively protect users’ location privacy against single-point attack. Furthermore, we propose a location anonymous optimization method based on Stackelberg game, which introduces Stackelberg game to improve the dummy location selection algorithm. More specifically, we formalize the mutual optimization of user-adversary objectives (location privacy vs. correctness of inferring location) by using the framework of Stackelberg games, and find an optimal dummy location set by solving the game equilibrium. The optimal dummy location set can resist single-point attacks and inference attacks while effectively balancing service quality and location privacy.(3)
We conduct a comprehensive experiment to evaluate the proposed scheme. Experimental results show that our scheme can effectively resist single-point attacks and inference attacks while effectively balancing service quality and location privacye when compared with other dummy-based schemes.The rest of the paper is organized as follows. We discuss the related work in Section2. Section 3 presents some preliminaries of this paper. Section 4 presents the structure of STTP and the interactive process. We present the SPDDS algorithms and a location anonymous optimization method based on Stackelberg game in Section 5. Section 6 presents the experimental process as well as results. We conclude the paper in Section 7.


## 2. Related Works

In this section, we first analyze the merits and drawbacks of mainstream existing location privacy protection system structure. Furthermore, we review major existing techniques for preventing location privacy leakage including privacy protection scheme based on dummy and privacy protection scheme based on Stackelberg game in Sections2.2 to 2.3, respectively.


### 2.1. Location Privacy Protection System Structure

As a large body of location privacy protection technologies has been proposed, the system structure on which various privacy protection technologies depend has shown distinct category differences. As the carrier of privacy protection technology implementation, the system structure has got sufficiently researched and developed.Currently, there are two mainstream system structures:TTP−based central server structure and independent system structure. In the TTP structure [14–16], the location anonymizer obtains the location information of all users and is responsible for implementing the location privacy protection mechanism. It is currently a more commonly used privacy protection system structure, the advantage of which is that the location anonymizer can obtain the location information of all users and assist users in filtering service data. The disadvantage is that it relies on a location anonymizer to enlarge the queried location into a bigger cloaking region, and hence the location anonymizer becomes the central point of failure. References [2, 17, 18] proposed an independent system structure, where users can protect their location privacy according to their own capabilities and knowledge. The architecture treats each user as an independent individual, allows the user’s device to implement a location privacy protection mechanism, directly sends a service request to the service provider, and receives the query result. The advantage of this system structure is that the deployment is conveniently simple, and it is convenient for users to adjust the privacy protection granularity according to their privacy protection needs. However, the implementation of privacy protection algorithms has been limited by the performance of mobile devices. Meanwhile, filtering query results will also increase the burden on the mobile client, which in turn affects service quality.


### 2.2. Privacy Protection Scheme Based on Dummy

Location dummies are aimed to secure users’ accurate location by sendingk−1 false locations (“dummies”) together with the true location so that the probability of location leakage is reduced to 1/k. Compared to the traditional k−anonymity, this approach sends exact locations instead of cloaked regions to a service provider, which can return a more precise query result and avoid single-point failure.Kido et al. [19, 20] first proposed to use dummy locations to achieve anonymity without employing a central server. However, they only concentrate on reducing the communication costs. Moreover, they employ a random walk model to generate dummy locations, and it cannot resist side information attacks due to lack of considering factors such as query probability. Subsequently, although Dapeng et al. [21] proposed the ABR algorithm based on query probability, which can resist side information attacks. However, it cannot resist homogeneity attacks and location similarity attacks for not considering the physical dispersion and location semantic diversity. The UPHIF algorithm proposed by Chang et al. [22] protected location privacy to a certain extent, but did not consider the location semantic diversity, so it cannot deal with location similarity attacks. Niu et al. [23] selected dummy locations based on entropy metrics, and proposed a dummy location selection DLS scheme and its improved scheme enhanced−DLS. Although the enhanced−DLS scheme can resist side information attacks and homogeneity attacks, which cannot resist location similarity attacks for lacking of considering the location semantic diversity. References [24, 25] all considered the user’s location semantic diversity, which can effectively resist location similarity attacks, but all have the problem that the cloaked region is too big, affecting the service quality in turn. Although [26, 27] fully considered the location semantic diversity and physical dispersion, which can effectively resist homogeneity attacks and location similarity attacks, but they cannot resist the side information attack for not considering the query probability.


### 2.3. Privacy Protection Scheme Based on Stackelberg Game

In a big data environment, an adversary can use the various data collected to infer the privacy information of the user’s location [28], which is called the location inference attack. Because the traditional dummy-based privacy protection scheme cannot effectively resist this kind of inference attack, the location privacy protection mechanism based on probabilistic reasoning [29, 30] has gradually attracted the attention of scholars. Such methods are based on perturbing the real locations of a user to the service provider, in order to increase the uncertainty of the adversary about a user’s true whereabouts. However, the perturbation of the information sent to the service provider leads to a degradation of service quality, and consequently, there is a trade-off between the level of privacy that the user wishes to guarantee and the service quality loss that she will have to accept. So, the Stackelberg game has become an important means of balancing the level of privacy protection and service-quality requirements in such methods.Based on [13] and combined the ideas of k−anonymity and dummy location, Xingyou et al. [31] propose HCLS and its improved scheme HCLS−SG. Although the HCLS−SG scheme can effectively resist inference attacks and better balance service quality and location privacy, it cannot resist location similarity attacks for not considering location semantic diversity. Bordenabe et al. [32] also introduced differential privacy on the basis of [13] and constructed a privacy protection mechanism that optimizes the quality of service. Since differential privacy does not depend on prior, this mechanism can minimize the service quality loss under the premise of satisfying location indistinguishability. Shokri [18] further proposed using two indicators of differential privacy and distortion privacy to optimize the privacy protection strategy based on the Stackelberg game. Differential privacy limits the extent of user privacy leakage, while distortion privacy measures the error rate of inferring a user’s privacy. By combining these two standards, this privacy protection strategy can resist more kinds of inference attacks while ensuring privacy protection requirements.


## 2.1. Location Privacy Protection System Structure

As a large body of location privacy protection technologies has been proposed, the system structure on which various privacy protection technologies depend has shown distinct category differences. As the carrier of privacy protection technology implementation, the system structure has got sufficiently researched and developed.Currently, there are two mainstream system structures:TTP−based central server structure and independent system structure. In the TTP structure [14–16], the location anonymizer obtains the location information of all users and is responsible for implementing the location privacy protection mechanism. It is currently a more commonly used privacy protection system structure, the advantage of which is that the location anonymizer can obtain the location information of all users and assist users in filtering service data. The disadvantage is that it relies on a location anonymizer to enlarge the queried location into a bigger cloaking region, and hence the location anonymizer becomes the central point of failure. References [2, 17, 18] proposed an independent system structure, where users can protect their location privacy according to their own capabilities and knowledge. The architecture treats each user as an independent individual, allows the user’s device to implement a location privacy protection mechanism, directly sends a service request to the service provider, and receives the query result. The advantage of this system structure is that the deployment is conveniently simple, and it is convenient for users to adjust the privacy protection granularity according to their privacy protection needs. However, the implementation of privacy protection algorithms has been limited by the performance of mobile devices. Meanwhile, filtering query results will also increase the burden on the mobile client, which in turn affects service quality.


## 2.2. Privacy Protection Scheme Based on Dummy

Location dummies are aimed to secure users’ accurate location by sendingk−1 false locations (“dummies”) together with the true location so that the probability of location leakage is reduced to 1/k. Compared to the traditional k−anonymity, this approach sends exact locations instead of cloaked regions to a service provider, which can return a more precise query result and avoid single-point failure.Kido et al. [19, 20] first proposed to use dummy locations to achieve anonymity without employing a central server. However, they only concentrate on reducing the communication costs. Moreover, they employ a random walk model to generate dummy locations, and it cannot resist side information attacks due to lack of considering factors such as query probability. Subsequently, although Dapeng et al. [21] proposed the ABR algorithm based on query probability, which can resist side information attacks. However, it cannot resist homogeneity attacks and location similarity attacks for not considering the physical dispersion and location semantic diversity. The UPHIF algorithm proposed by Chang et al. [22] protected location privacy to a certain extent, but did not consider the location semantic diversity, so it cannot deal with location similarity attacks. Niu et al. [23] selected dummy locations based on entropy metrics, and proposed a dummy location selection DLS scheme and its improved scheme enhanced−DLS. Although the enhanced−DLS scheme can resist side information attacks and homogeneity attacks, which cannot resist location similarity attacks for lacking of considering the location semantic diversity. References [24, 25] all considered the user’s location semantic diversity, which can effectively resist location similarity attacks, but all have the problem that the cloaked region is too big, affecting the service quality in turn. Although [26, 27] fully considered the location semantic diversity and physical dispersion, which can effectively resist homogeneity attacks and location similarity attacks, but they cannot resist the side information attack for not considering the query probability.


## 2.3. Privacy Protection Scheme Based on Stackelberg Game

In a big data environment, an adversary can use the various data collected to infer the privacy information of the user’s location [28], which is called the location inference attack. Because the traditional dummy-based privacy protection scheme cannot effectively resist this kind of inference attack, the location privacy protection mechanism based on probabilistic reasoning [29, 30] has gradually attracted the attention of scholars. Such methods are based on perturbing the real locations of a user to the service provider, in order to increase the uncertainty of the adversary about a user’s true whereabouts. However, the perturbation of the information sent to the service provider leads to a degradation of service quality, and consequently, there is a trade-off between the level of privacy that the user wishes to guarantee and the service quality loss that she will have to accept. So, the Stackelberg game has become an important means of balancing the level of privacy protection and service-quality requirements in such methods.Based on [13] and combined the ideas of k−anonymity and dummy location, Xingyou et al. [31] propose HCLS and its improved scheme HCLS−SG. Although the HCLS−SG scheme can effectively resist inference attacks and better balance service quality and location privacy, it cannot resist location similarity attacks for not considering location semantic diversity. Bordenabe et al. [32] also introduced differential privacy on the basis of [13] and constructed a privacy protection mechanism that optimizes the quality of service. Since differential privacy does not depend on prior, this mechanism can minimize the service quality loss under the premise of satisfying location indistinguishability. Shokri [18] further proposed using two indicators of differential privacy and distortion privacy to optimize the privacy protection strategy based on the Stackelberg game. Differential privacy limits the extent of user privacy leakage, while distortion privacy measures the error rate of inferring a user’s privacy. By combining these two standards, this privacy protection strategy can resist more kinds of inference attacks while ensuring privacy protection requirements.


## 3. Preliminaries

In this section, we first introduce some relative definitions of location privacy protection algorithm; meanwhile, we summarize the notations introduced throughout the section in Table1 and then introduce the relative concepts of Stackelberg game.Table 1
Summary of notations.
SymbolMeaningdsemli,ljThe semantic distance between two locationsli,lji≠jdphyli,ljThe physical distance between two locationsli,lji≠jdqueli,ljThe query probability distance between two locationsli,lji≠j, which is obtained by calculating the difference between the query probabilities of two locationsθRepresentation of the semantic diversity between locationsφlLocation access profile of the user (probability of being at location when accessing the LBS)lActual locationl of the userldOffset location output by thefld|lDLSSet of possible dummy locations output by the LPPMfDLS|lThe location privacy protection mechanism (LPPM): probability of replacingl with DLSl^Adversary’s estimate of the user’s actual locationgl^|DLSAdversary’s attack function: probability of estimatingl^ as user’s actual location, if DLS is observedfld|lFunction of generating offset location: probability of replacingl with ldQoslossExpected quality loss of an LPPM with location obfuscation functionfld|lQlossmaxMaximum tolerable service quality lossPLExpected location privacy of the user with profileφl using LPPM fDLS|l against attack gl^|DLS


### 3.1. Relative Definitions of Location Privacy Protection Algorithm

Definition 1.
According to [27], location semantic tree LST, a true structure used to represent the semantic relations between two locations within the range of a Wi-Fi access points (Wi-Fi AP), which satisfies the following requirements:(a)
Each nonleaf node stands for the category of its children nodes and each leaf node for a real locationl(b)
The depth ofLST, denoted as h, is equal to the maximum number of layers of categories plus 1(c)
The semantic distancedsemli,lj between two locations li,lji≠j is the number of hops from leaf node ni to leaf node njDefinition 2.
User’s privacy requirementsS, represented by two-tuple k,u that has the following meanings:(a)
k denotes the anonymous degree of our location privacy preservation model. More specifically, each query is sent with at least k−1 dummy locations and its offset location (we use offset location instead of the real location), making that the probability of offset location leakage is therefore 1/k.(b)
u represents the minimum acceptable value of semantic distance between two locations in dummy location set DLS. In other words, it satisfies the inequality:(1)mindsemli,lj≥u.Definition 3.
(location map distance). If we letMapcur represent the map information within the range of the current Wi-Fi AP. For any two locations li,lji≠j, the location map distance is the physical distance between the two locations on Mapcur, the value of which ranges from tens of meters to hundreds.Definition 4.
(location query probabilityLQP). As shown in Figure 1, in a map divided into m×m cells with equal size. Each cell has a query probability based on the previous query history, which is denoted as(2)pi=number of queries in cellsnumber of queries inwhole map,where i=1,2,…,m2,∑i=1m2pi=1. The depth of the color in the figure indicates LQP (the darker the color, the greater the LQP, and the white area indicates that the location has never had a location service request, so these locations may be rivers, barren mountains, and other places that are easily filtered by the adversary.Figure 1
Location query probability diagram.Definition 5.
The probability of exposing real locationPERL, which has been used to measure the effectiveness of the algorithm against side information attacks, is computed by(3)PERL=1k−k′,where k denotes the anonymous degree and k′ represents the number of dummy locations filtered by the adversary through the side information attack. The larger the PERL, the less effective the algorithm resists side information attacks; the smaller the PERL, the better the algorithm resists side information attacks.Definition 6.
Location physical dispersionPD, which has been used to measure the effectiveness of the algorithm against location homogeneity attacks, is obtained by computing the minimum physical distance between any two locations in a DLS. The specific process is shown in (4):(4)PD=Mindphyli,lj,where i,j=1,2,…,k,i≠j. The greater the minimum distance between any two locations in the DLS, the greater the PD and the greater the coverage of the DLS, the better the algorithm’s resistance to location homogeneity attacks.Definition 7.
θ−secure set of dummy locations. Dummy location set DLS consisting of k−1 dummy locations and the offset location, where the semantic distance between li and lj satisfies(5)1−SEMCk2≥θ,where SEM=dsem|dsemli,lj<u, k=DLS, and Ck2 is a combination formulas, we call DLS a θ− secure set. We use θ as a privacy protection index of location semantics in our experimental analysis in Section 6. Our aim is to achieve the maximum θ, i.e., to make it equal to 1, such that two locations in DLS belong to different categories.Definition 8.
The adversary uses background knowledge to run an inference attack onDLS in order to output estimation l^ of the user’s actual locations and the attack result can be denoted as gl^|DLS, and we define the location privacy protection mechanism (LPPM) that the adversary knows as fDLS|l. Then, we follow the definition in [33] and quantify the user’s privacy level PL as the adversary’s expected error in his inference attack, i.e., the expected distortion in the reconstructed event. We compute the expectation over all l, l^, and DLS:(6)PL=∑l,l^,DLSφlfDLS|lgl^|DLSdphyl,l^,PL directly reflects the adversary’s inference on the user’s actual location. The larger the PL, the less accurate the adversary’s inference, and the better the effect of the algorithm resist the inference attack.Definition 9.
We define the process of generating the offset locationld as fld|l. Then, following the definition in [13], the LBS response quality depends on the offset location ld output by fld|l and not on the user’s actual location l. The distortion introduced in the offset location determines the quality of service that the user experiences. The more similar the actual and the offset location are, the higher the service quality is. The expected quality loss Qosloss due to fld|l is computed as an average of dphyl,ld over all l and ld:(7)Qosloss=∑l,ldφlfld|ldphyl,ld.
We set a service quality thresholdQlossmax, which represents the maximum service quality loss that the user can accept. The location privacy protection scheme designed in this paper needs to guarantee Qosloss≤Qlossmax because if the service quality loss exceeds the threshold, the location service request results obtained cannot satisfy the requirements of users.


### 3.2. Stackelberg Game

The classic Stackelberg game is a two-player game composed of a leader and a follower [34]. The leader first determines his strategy, and after observing the leader’s strategy, the follower chooses the strategy that maximizes his utility to play the game. In the field of location privacy protection, the terms “protector” and “leader,” “adversary” and “follower” can be used interchangeably. For simplicity of expression, the leader (protector), denoted as Θ, is often referred to as she, whereas the follower (adversary), represented by Ψ, is referred to as he.Definition 10.
In the field of location privacy protection, the strong Stackelberg equilibriumSSE is generally used as the solution of the Stackelberg game. The definition of SSE is described as follows.
A strategy combination isSSE, if and only if it satisfies the following conditions:(a)
The leader’s strategy is the best response:(8)∑γ∈ΓΩΘx,q,γ≥∑γ∈ΓΩΘx′,q,γ∀x,x′∈X,q∈Q,whereγ∈Γ means a particular type of follower, x,x′∈X represents the leaders’ mixed strategy, and q∈Q represents the followers’ mixed strategy.(b)
The follower’s strategy is the best response:(9)∑γ∈ΓΩΨx,q,γ≥∑γ∈ΓΩΨx,q′,γ∀x∈X,q,q′∈Q,wherex∈X represents the leaders’ mixed strategy, q,q′∈Q represents the followers’ mixed strategy.(c)
If there are multiple best responses for the followers, the followers choose the most favorable strategy for the leader to break the deadlock:(10)∑γ∈ΓΩΨx,qr,γ≥∑γ∈ΓΩΨx,qr′,γ∀x∈X,qr,qr′∈Q∗x,whereQ∗x is the follower’s best response strategy set under the leader’s strategy is x.


## 3.1. Relative Definitions of Location Privacy Protection Algorithm

Definition 1.
According to [27], location semantic tree LST, a true structure used to represent the semantic relations between two locations within the range of a Wi-Fi access points (Wi-Fi AP), which satisfies the following requirements:(a)
Each nonleaf node stands for the category of its children nodes and each leaf node for a real locationl(b)
The depth ofLST, denoted as h, is equal to the maximum number of layers of categories plus 1(c)
The semantic distancedsemli,lj between two locations li,lji≠j is the number of hops from leaf node ni to leaf node njDefinition 2.
User’s privacy requirementsS, represented by two-tuple k,u that has the following meanings:(a)
k denotes the anonymous degree of our location privacy preservation model. More specifically, each query is sent with at least k−1 dummy locations and its offset location (we use offset location instead of the real location), making that the probability of offset location leakage is therefore 1/k.(b)
u represents the minimum acceptable value of semantic distance between two locations in dummy location set DLS. In other words, it satisfies the inequality:(1)mindsemli,lj≥u.Definition 3.
(location map distance). If we letMapcur represent the map information within the range of the current Wi-Fi AP. For any two locations li,lji≠j, the location map distance is the physical distance between the two locations on Mapcur, the value of which ranges from tens of meters to hundreds.Definition 4.
(location query probabilityLQP). As shown in Figure 1, in a map divided into m×m cells with equal size. Each cell has a query probability based on the previous query history, which is denoted as(2)pi=number of queries in cellsnumber of queries inwhole map,where i=1,2,…,m2,∑i=1m2pi=1. The depth of the color in the figure indicates LQP (the darker the color, the greater the LQP, and the white area indicates that the location has never had a location service request, so these locations may be rivers, barren mountains, and other places that are easily filtered by the adversary.Figure 1
Location query probability diagram.Definition 5.
The probability of exposing real locationPERL, which has been used to measure the effectiveness of the algorithm against side information attacks, is computed by(3)PERL=1k−k′,where k denotes the anonymous degree and k′ represents the number of dummy locations filtered by the adversary through the side information attack. The larger the PERL, the less effective the algorithm resists side information attacks; the smaller the PERL, the better the algorithm resists side information attacks.Definition 6.
Location physical dispersionPD, which has been used to measure the effectiveness of the algorithm against location homogeneity attacks, is obtained by computing the minimum physical distance between any two locations in a DLS. The specific process is shown in (4):(4)PD=Mindphyli,lj,where i,j=1,2,…,k,i≠j. The greater the minimum distance between any two locations in the DLS, the greater the PD and the greater the coverage of the DLS, the better the algorithm’s resistance to location homogeneity attacks.Definition 7.
θ−secure set of dummy locations. Dummy location set DLS consisting of k−1 dummy locations and the offset location, where the semantic distance between li and lj satisfies(5)1−SEMCk2≥θ,where SEM=dsem|dsemli,lj<u, k=DLS, and Ck2 is a combination formulas, we call DLS a θ− secure set. We use θ as a privacy protection index of location semantics in our experimental analysis in Section 6. Our aim is to achieve the maximum θ, i.e., to make it equal to 1, such that two locations in DLS belong to different categories.Definition 8.
The adversary uses background knowledge to run an inference attack onDLS in order to output estimation l^ of the user’s actual locations and the attack result can be denoted as gl^|DLS, and we define the location privacy protection mechanism (LPPM) that the adversary knows as fDLS|l. Then, we follow the definition in [33] and quantify the user’s privacy level PL as the adversary’s expected error in his inference attack, i.e., the expected distortion in the reconstructed event. We compute the expectation over all l, l^, and DLS:(6)PL=∑l,l^,DLSφlfDLS|lgl^|DLSdphyl,l^,PL directly reflects the adversary’s inference on the user’s actual location. The larger the PL, the less accurate the adversary’s inference, and the better the effect of the algorithm resist the inference attack.Definition 9.
We define the process of generating the offset locationld as fld|l. Then, following the definition in [13], the LBS response quality depends on the offset location ld output by fld|l and not on the user’s actual location l. The distortion introduced in the offset location determines the quality of service that the user experiences. The more similar the actual and the offset location are, the higher the service quality is. The expected quality loss Qosloss due to fld|l is computed as an average of dphyl,ld over all l and ld:(7)Qosloss=∑l,ldφlfld|ldphyl,ld.
We set a service quality thresholdQlossmax, which represents the maximum service quality loss that the user can accept. The location privacy protection scheme designed in this paper needs to guarantee Qosloss≤Qlossmax because if the service quality loss exceeds the threshold, the location service request results obtained cannot satisfy the requirements of users.


## 3.2. Stackelberg Game

The classic Stackelberg game is a two-player game composed of a leader and a follower [34]. The leader first determines his strategy, and after observing the leader’s strategy, the follower chooses the strategy that maximizes his utility to play the game. In the field of location privacy protection, the terms “protector” and “leader,” “adversary” and “follower” can be used interchangeably. For simplicity of expression, the leader (protector), denoted as Θ, is often referred to as she, whereas the follower (adversary), represented by Ψ, is referred to as he.Definition 10.
In the field of location privacy protection, the strong Stackelberg equilibriumSSE is generally used as the solution of the Stackelberg game. The definition of SSE is described as follows.
A strategy combination isSSE, if and only if it satisfies the following conditions:(a)
The leader’s strategy is the best response:(8)∑γ∈ΓΩΘx,q,γ≥∑γ∈ΓΩΘx′,q,γ∀x,x′∈X,q∈Q,whereγ∈Γ means a particular type of follower, x,x′∈X represents the leaders’ mixed strategy, and q∈Q represents the followers’ mixed strategy.(b)
The follower’s strategy is the best response:(9)∑γ∈ΓΩΨx,q,γ≥∑γ∈ΓΩΨx,q′,γ∀x∈X,q,q′∈Q,wherex∈X represents the leaders’ mixed strategy, q,q′∈Q represents the followers’ mixed strategy.(c)
If there are multiple best responses for the followers, the followers choose the most favorable strategy for the leader to break the deadlock:(10)∑γ∈ΓΩΨx,qr,γ≥∑γ∈ΓΩΨx,qr′,γ∀x∈X,qr,qr′∈Q∗x,whereQ∗x is the follower’s best response strategy set under the leader’s strategy is x.


## 4. System Model

We first give the definition of the single-point attack mode and inference attack mode in Sections4.1 and 4.2 respectively, and then introduce the structure of STTP in Section 4.3. Finally we present the interactive process of our scheme in Section 4.4.


### 4.1. Single-Point Attack Model

From the time dimension, the adversary relies on the intercepted single location-service request to infer the user’s private information, which is called the single-point attack model [35]. In the model, the main attack methods of adversaries include side information attacks, homogeneity attacks and location similarity attacks.Side information refers to information used by adversaries to filter dummy locations and help reduce anonymity, including map information and location query probability. For example, for a randomly generated dummy location set, some locations may be in a river or no man’s land, and adversaries can easily filter out these locations based on the map information. Assuming that the location anonymity requirement isk, when k′ of the k−1 dummy locations are filtered by the adversary based on the side information, the k−anonymity requirement is not satisfied, resulting in a decrease in the level of privacy protection.Homogeneity attack means that the adversary analyzes the distance between multiple locations in aDLS to infer a user’s privacy. Specifically, if the distance between any two locations is very close such as in the same building, although the DLS satisfies k−anonymity, the user’s location privacy cannot be well protected because the cloaking region is too small.The location similarity attack means that the adversary analyzes the semantic information in the cloaking region to infer a user’s privacy. More specifically, if the region contains only one kind of semantic information, such as a hospital or school, the adversary can infer the user’s behavior.


### 4.2. Inference Attack Model

In a big data environment, an adversary can use the various data collected to infer the privacy information of the user’s location [28], which is called the location inference attack.In the location inference model, the adversary has certain background knowledge such as the user’s service request history records, LPPM, etc. Using the user’s service request history records, the adversary can calculate the user’s query probability distributionφl. When the user sends a query request again, if the location query probability distribution in the anonymous set is not uniform, the adversary can infer that the user is likely to be located in a location with a higher probability. While for the LPPM, the adversary can analyze the intercepted location request, combined with the anonymity algorithm, to infer the probability that each location in the anonymous set is the user’s true location, so as to make the inference attack more accurate.


### 4.3. The Structure of STTP

It can be seen from Section2.1 that, for the current two mainstream location privacy protection system structures, the TTP structure has the problem of a single point of failure, while the independent structure has the problem of mobile device performance bottlenecks. In view of the problems above, we have designed a semi-trusted third party STTP based location privacy protection structure. STTP is based on the traditional TTP structure by adding an encryption server and Wi-Fi AP and stores the user’s private information in the three-party server through a certain mechanism, which results in that even if the location anonymizer has been controlled by adversaries, STTP also protects the user’s private information to a certain extent. Furthermore, the location anonymizer is responsible for implementing the privacy protection algorithms and filtering query results, so there are no problems such as mobile device performance bottlenecks. STTP is shown in Figure 2, which consists of the following five entities:User: using a mobile terminal to initiate a location service request when needed.Wi-Fi AP: providing network support, and calculating, storingLST and LQP.Encryption server (ES): providing encryption and decryption key pairs corresponding to the user’s pseudonym.Location anonymizer (LA): converting the user’s actual location into a dummy location set, and after the service provider returns the query result, extracting appropriate service information and returning it to the user.Service provider (SP): return the corresponding service result according to the location query request.Figure 2
A semitrusted third party based location privacy protection structure.The proposed scheme assumes that ES, LA, and SP are “honest and curious.” On the one hand, they will not disrupt the protocol process and can faithfully complete their work following the agreement; on the other hand, they all want to analyze more other sensitive information about the user from what they have mastered. Meanwhile, we further set that ES, LA, and SP cannot collude with each other, that is, they will not be controlled by an adversary simultaneously. There will be no secrets for the user if the three parties conspire, so this setting is reasonable.


### 4.4. Interactive Process

There are eight steps in the interactive process of the proposed scheme. The specific implementation of each step is described below (as shown in Figure2):(1)
Before initiating a location service request, the user first requestsMapcur, LST, and LQP from the Wi-Fi AP.(2)
The Wi-Fi AP generatesMapcur, computes and stores LQP of all locations within its current coverage area, generates and saves LST by collecting location semantic information within its radio range, and then sends Mapcur, LST, and LQP to the user. It should be noted that for any Wi-Fi AP, the location within its coverage area is relatively stable, so LST and LQP do not need to change frequently.(3)
The user then requests the pseudonymUpseu and key pair from ES. Specifically, if there are multiple service requests at the same location within the limited time tsession, the user only applies for the pseudonym and key pair once; when the time exceeds tsession or the user’s real location changes, she will reapply for a new pseudonym and key, so as to achieve the effect of confusing her identity.(4)
ES generates the corresponding pseudonymUpseu and RSA key pair Keypublic,Keyprivacy, returns Upseu and Keypublic to the user, and sends Upseu and Keyprivacy to the SP. It should be noted that, as an example, the solution uses the classic RSA algorithm for encryption, and it can be replaced by other encryption algorithms according to actual requirements. In addition, the solution requires ES to only act as a provider of pseudonyms and keys, so ES does not store related pseudonyms and keys locally.(5)
The user first encrypts his query contentQuery with the public key Keypublic and then sends his current pseudonym Upseu, encrypted query content Query′, current real location l, Mapcur, LQP, and LST to LA together.(6)
After receiving the information, LA performs the corresponding location anonymity algorithm that generates a dummy location setDLS to hide l and then sends Upseu, Query′ and DLS to the SP.(7)
After receiving the location service request, the SP first searches for the corresponding private keyKeyprivacy according to Upseu, which is used to decrypt Query′, and then provides the service result ResultQuery|DLS according to Query and DLS, finally return it to LA.(8)
After receivingResultQuery|DLS, the LA first identifies the corresponding location ld according to the Upseu, and then filters out the query result Resultld from ResultQuery|DLS and finally returns it to the user.


## 4.1. Single-Point Attack Model

From the time dimension, the adversary relies on the intercepted single location-service request to infer the user’s private information, which is called the single-point attack model [35]. In the model, the main attack methods of adversaries include side information attacks, homogeneity attacks and location similarity attacks.Side information refers to information used by adversaries to filter dummy locations and help reduce anonymity, including map information and location query probability. For example, for a randomly generated dummy location set, some locations may be in a river or no man’s land, and adversaries can easily filter out these locations based on the map information. Assuming that the location anonymity requirement isk, when k′ of the k−1 dummy locations are filtered by the adversary based on the side information, the k−anonymity requirement is not satisfied, resulting in a decrease in the level of privacy protection.Homogeneity attack means that the adversary analyzes the distance between multiple locations in aDLS to infer a user’s privacy. Specifically, if the distance between any two locations is very close such as in the same building, although the DLS satisfies k−anonymity, the user’s location privacy cannot be well protected because the cloaking region is too small.The location similarity attack means that the adversary analyzes the semantic information in the cloaking region to infer a user’s privacy. More specifically, if the region contains only one kind of semantic information, such as a hospital or school, the adversary can infer the user’s behavior.


## 4.2. Inference Attack Model

In a big data environment, an adversary can use the various data collected to infer the privacy information of the user’s location [28], which is called the location inference attack.In the location inference model, the adversary has certain background knowledge such as the user’s service request history records, LPPM, etc. Using the user’s service request history records, the adversary can calculate the user’s query probability distributionφl. When the user sends a query request again, if the location query probability distribution in the anonymous set is not uniform, the adversary can infer that the user is likely to be located in a location with a higher probability. While for the LPPM, the adversary can analyze the intercepted location request, combined with the anonymity algorithm, to infer the probability that each location in the anonymous set is the user’s true location, so as to make the inference attack more accurate.


## 4.3. The Structure of STTP

It can be seen from Section2.1 that, for the current two mainstream location privacy protection system structures, the TTP structure has the problem of a single point of failure, while the independent structure has the problem of mobile device performance bottlenecks. In view of the problems above, we have designed a semi-trusted third party STTP based location privacy protection structure. STTP is based on the traditional TTP structure by adding an encryption server and Wi-Fi AP and stores the user’s private information in the three-party server through a certain mechanism, which results in that even if the location anonymizer has been controlled by adversaries, STTP also protects the user’s private information to a certain extent. Furthermore, the location anonymizer is responsible for implementing the privacy protection algorithms and filtering query results, so there are no problems such as mobile device performance bottlenecks. STTP is shown in Figure 2, which consists of the following five entities:User: using a mobile terminal to initiate a location service request when needed.Wi-Fi AP: providing network support, and calculating, storingLST and LQP.Encryption server (ES): providing encryption and decryption key pairs corresponding to the user’s pseudonym.Location anonymizer (LA): converting the user’s actual location into a dummy location set, and after the service provider returns the query result, extracting appropriate service information and returning it to the user.Service provider (SP): return the corresponding service result according to the location query request.Figure 2
A semitrusted third party based location privacy protection structure.The proposed scheme assumes that ES, LA, and SP are “honest and curious.” On the one hand, they will not disrupt the protocol process and can faithfully complete their work following the agreement; on the other hand, they all want to analyze more other sensitive information about the user from what they have mastered. Meanwhile, we further set that ES, LA, and SP cannot collude with each other, that is, they will not be controlled by an adversary simultaneously. There will be no secrets for the user if the three parties conspire, so this setting is reasonable.


## 4.4. Interactive Process

There are eight steps in the interactive process of the proposed scheme. The specific implementation of each step is described below (as shown in Figure2):(1)
Before initiating a location service request, the user first requestsMapcur, LST, and LQP from the Wi-Fi AP.(2)
The Wi-Fi AP generatesMapcur, computes and stores LQP of all locations within its current coverage area, generates and saves LST by collecting location semantic information within its radio range, and then sends Mapcur, LST, and LQP to the user. It should be noted that for any Wi-Fi AP, the location within its coverage area is relatively stable, so LST and LQP do not need to change frequently.(3)
The user then requests the pseudonymUpseu and key pair from ES. Specifically, if there are multiple service requests at the same location within the limited time tsession, the user only applies for the pseudonym and key pair once; when the time exceeds tsession or the user’s real location changes, she will reapply for a new pseudonym and key, so as to achieve the effect of confusing her identity.(4)
ES generates the corresponding pseudonymUpseu and RSA key pair Keypublic,Keyprivacy, returns Upseu and Keypublic to the user, and sends Upseu and Keyprivacy to the SP. It should be noted that, as an example, the solution uses the classic RSA algorithm for encryption, and it can be replaced by other encryption algorithms according to actual requirements. In addition, the solution requires ES to only act as a provider of pseudonyms and keys, so ES does not store related pseudonyms and keys locally.(5)
The user first encrypts his query contentQuery with the public key Keypublic and then sends his current pseudonym Upseu, encrypted query content Query′, current real location l, Mapcur, LQP, and LST to LA together.(6)
After receiving the information, LA performs the corresponding location anonymity algorithm that generates a dummy location setDLS to hide l and then sends Upseu, Query′ and DLS to the SP.(7)
After receiving the location service request, the SP first searches for the corresponding private keyKeyprivacy according to Upseu, which is used to decrypt Query′, and then provides the service result ResultQuery|DLS according to Query and DLS, finally return it to LA.(8)
After receivingResultQuery|DLS, the LA first identifies the corresponding location ld according to the Upseu, and then filters out the query result Resultld from ResultQuery|DLS and finally returns it to the user.


## 5. Proposed Scheme

In this section, we first introduce a dummy location selection algorithm based on location semantics and physical distanceSPDDS and then present a location anonymous optimization method based on Stackelberg game.


### 5.1. A Dummy Location Selection Algorithm Based on Location Semantics and Physical Distance

Based on the analysis above, the final dummy location set not only needs to avoid selecting places that are easy to be filtered by adversaries, such as rivers and no man’s land but also to meet the semantic diversity while making the locations as dispersed as possible. In other words, the final dummy location set needs to simultaneously satisfy (11)–(13)(11)DLS=argminmaxdqueli,lj,(12)DLS=argmaxmindsemli,lj,(13)DLS=argmaxmindphyli,lj,where li,lj∈DLS,i≠j,Prli>0,Prld>0. It can be formulated as a multiobjective optimization problem (MOP) since three factors are considered simultaneously. However, we put forward a simpler objective formulas considering the complexity of MOP. In each dummy location set, we would like to make sure that (14) can be satisfied. Consequently, we propose a dummy location selection algorithm based on location semantics and physical distance SPDDS.(14)DLS=argmaxmindsemli,lj+r⋅dphyli,ljmaxdqueli,lj+1,where li,lj∈DLS,i≠j. dqueli,lj+1 is to avoid the situation where the two locations have the same probability, that is, the difference between the query probability of the two locations is 0. Here, r is a controllable factor for balancing the share of semantic distance, physical distance, and query probability distance since dsemli,lj≤2⋅h−1, where h is the depth of LST and hence is usually less than 10 while dphyli,lj, as Wi-Fi transmission distance, ranges from hundreds of meters to thousands, whereas the query probability distance is always less than 1. Consequently, we set r=0.03.Meanwhile, in order to balance service quality while the proposed algorithm can resist inference attacks effectively, we should take into account bothPL and Qosloss. So, we propose a location anonymous optimization method based on Stackelberg game, which introduces Stackelberg game to optimize the dummy location selection algorithm. More specifically, we formalize the mutual optimization of user-adversary objectives (location privacy vs. correctness of inferring location) by using the framework of Stackelberg games, to find an optimal dummy location set. The optimal dummy location set can resist single-point attacks and inference attacks while effectively balancing service quality and location privacy.The main idea ofSPDDS is to first select an offset location to replace the user’s real location; secondly, selecting all locations that satisfy the semantic difference with the existing locations in the current dummy location set as the dummy location candidate set DLCS; then, selecting an optimal location in the DLCS which refers to the location formed by satisfying (14); finally, a set consisting of an offset location and k−1 dummy locations is generated. Algorithm 1 shows the formal description of the SPDDS algorithm.Algorithm 1:A dummy location selection algorithm based on location semantic and physical distance.
Input:l: user’s real locationS: user’s privacy requirementMapcur: map information in current Wi-Fi AP LST: location semantic tree LQP: location query probability;Output:DLS: dummy location set;(1)
Divide theMapcur as the sample space into m×m grids;(2)
Generate semantic distance matricSDM according to the LST and geographic distance matrix GDM according to the Mapcur and probability distance matric PDM according to the LQP respectively(3)
According toGDM and PDM, choose the n−1 locations with pi>0, which are closest to l, and then a offset location set Mset consisting of the n−1 locations and l has been generated;(4)
Randomly choose a location fromMset as offset location ld(5)
Generate a dummy location candidate setDLCS for all pi>0 locations in the wholegrid space;(6)
DLS=ld(7)
Removeld from DLCS;(8)
whileDLS<kdo(9)
ifDLCS=ϕthen(10)
anonymity failed;(11)
else(12)
max=0; BestLoc=ϕ;(13)
foreachLocinDLCSdo(14)
ifdsemLoc,DLS.last≤uthen(15)
anonymity failed;(16)
go back to line 13;(17)
else(18)
m=dsemLoc,DLS.last+r⋅dphyLoc,DLS.last/dqueLoc,DLS.last(19)
compute the maximumm according to SDM, GDM and PDM, which is recorded with max, and then assign the corresponding Loc to BestLoc(20)
end(21)
end(22)
DLS=DLS∪BestLoc(23)
removeBestLoc from DLCS;(24)
end(25)
end(26)
outputDLS;


### 5.2. A Location Anonymous Optimization Method Based on Stackelberg Game

We propose a location anonymous optimization method based on Stackelberg game, which optimizes the dummy location selection algorithm by introducing the Stackelberg game. More specifically, we formalize the mutual optimization of user-adversary objectives (location privacy vs. correctness of inferring location) by using the framework of Stackelberg game, and based on which we construct the related linear programs. We can find an optimal dummy location set by solving the linear programs, which can resist single-point attacks and inference attacks while effectively balancing service quality and location privacy.


#### 5.2.1. Location Inference Model

In the location inference model, the adversary has certain background knowledge such as the user’s service request history records, LPPM, etc. Using the user’s service request history records, the adversary can calculate the user’s query probability distributionφl. When the user sends a query request again, if the location query probability distribution in the anonymous set is not uniform, the adversary can infer that the user is likely to be located in a location with a higher probability. While for the LPPM, the adversary can analyze the intercepted location request, combined with the anonymity algorithm, to infer the probability that each location in the anonymous set is the user’s true location, so as to make the inference attack more accurate.Based on the existing knowledgeφl,fDLS|l, etc.), the adversary can form the posterior distribution on the true location l of the user, conditional on the anonymous set DLS:(15)Prl|DLS=Prl,DLSPrDLS=φlfDLS|l∑lφlfDLS|l.The adversary’s objective is then to choosel^ to minimize the user’s conditional expected privacy, where the expectation is taken under Prl|DLS. The user’s conditional expected privacy for an arbitrary l^ is(16)∑lPrl|DLSdphyl,l^,and for the minimizing l^, it is(17)minl^∑lPrl|DLSdphyl,l^.If there are multiple values ofl^ that satisfy (17), then the adversary randomizes arbitrarily among them. The probability with which l^ is chosen in this randomization is gl^|DLS.


#### 5.2.2. Stackelberg Game Optimization Process

Here, we assume that the adversary has some background knowledge. Specifically, he will infer the user’s actual locationl as much as possible according to φl, the LPPM used by the LA, the anonymous result DLS, and other background knowledge. Relatively, we can assume that all the background knowledge that LA knows will be used by the adversary, so LA can use the adversary’s optimal attack strategy as a parameter to optimize the generation process of the dummy location set DLS.We formalize the process above by using the framework of Stackelberg game. In a Stackelberg game the leader, in our case, the LA plays first by giving the dummy location setDLS according to the relative location privacy protection algorithm fDLS|l. The follower, in our case the adversary, plays next by estimating the user’s true location, knowing some background knowledge.We use the distance between the adversary’s inferred locationl^ and the user’s actual location l to measure the utility of the participants in the game: the greater the distance, the greater the LA returns, indicating that the anonymous algorithm is more effective in resisting inference attacks; on the contrary, the smaller the distance, the greater the adversary returns, the more effective the adversary’s attack strategy.The game model is also an instance of a zero-sum game, as the adversary’s gains (or losses) of utility is exactly balanced by the losses (or gains) of the utility of the user: the information gained (lost) by the adversary is the location privacy lost (gained) by the user.The purpose of Stackelberg game optimization is to findSSE so that the adversary cannot obtain more benefits by optimizing the attack strategy (that is, the adversary cannot make more accurate inferences about the actual location of the user). In this paper, SPDDS optimized by Stackelberg game is denoted as SPDDS_SG.It should be noted thatDLS is the result obtained by ld further anonymously, so fDLS|l can be further expressed by(18)fDLS|l=fld|l⋅fDLS|ld.In some cases,fDLS|l and fld|l are equal, the reason is that the adversary can filter out dummy locations except ld in such cases.We see that, for a givenDLS, the user’s conditional expected privacy is given by (17). The probability that DLS is output by the LPPM is PrDLS=∑lφlfDLS|l. Hence, the user’s unconditional expected privacy (averaged over all DLS is(19)∑DLSPrDLSminl^∑lPrl|DLSdphyl,l^=∑DLSminl^∑lφlfDLS|ldphyl,l^.To facilitate the computations, we define(20)xΔ¯¯minl^∑lφlfDLS|ldphyl,l^.Incorporatingx into (19), we write the unconditional expected privacy of the user as(21)∑DLSx,which the user aims to maximize by choosing the optimal DLS. To facilitate the computations, (20) can be transformed to a series of linear constraints:(22)x≤∑lφlfDLS|ldphyl,l^=∑lφlfld|lfDLS|lddphyl,l^,∀l^.In addition,SPDDS_SG needs to conceal the user’s real location on the premise of ensuring the user’s service quality. In order to ensure the quality of service, we set the service quality threshold Qlossmax to limit the maximum service quality loss. The specific process is (23)∑l,ldφlfld|ldphyl,ld≤Qlossmax.In summary,SPDDS_SG can be solved by a linear program. The final definition of linear program is (24)Maximize∑DLSx,s.t.C1:x≤∑lφlfld|lfDLS|lddphyl,l^,C2:∑l,ldφlfld|ldphyl,ld≤Qlossmax,C3:∑DLSfDLS|l=1,C4:fDLS|l≥0,∀l,DLS,where C1 is used to maximize the utility of the adversary; C2 reflects the service quality constraint; C3 indicates that the sum of the generation probability of the dummy location set must be 1; C4 indicates the probability of each candidate dummy location set is greater than zero.SPDDS_SG solves the objective function under the constraints in (24) and obtains the optimal dummy location set, which can resist single-point attacks and inference attacks while effectively balancing service quality and location privacy.


## 5.1. A Dummy Location Selection Algorithm Based on Location Semantics and Physical Distance

Based on the analysis above, the final dummy location set not only needs to avoid selecting places that are easy to be filtered by adversaries, such as rivers and no man’s land but also to meet the semantic diversity while making the locations as dispersed as possible. In other words, the final dummy location set needs to simultaneously satisfy (11)–(13)(11)DLS=argminmaxdqueli,lj,(12)DLS=argmaxmindsemli,lj,(13)DLS=argmaxmindphyli,lj,where li,lj∈DLS,i≠j,Prli>0,Prld>0. It can be formulated as a multiobjective optimization problem (MOP) since three factors are considered simultaneously. However, we put forward a simpler objective formulas considering the complexity of MOP. In each dummy location set, we would like to make sure that (14) can be satisfied. Consequently, we propose a dummy location selection algorithm based on location semantics and physical distance SPDDS.(14)DLS=argmaxmindsemli,lj+r⋅dphyli,ljmaxdqueli,lj+1,where li,lj∈DLS,i≠j. dqueli,lj+1 is to avoid the situation where the two locations have the same probability, that is, the difference between the query probability of the two locations is 0. Here, r is a controllable factor for balancing the share of semantic distance, physical distance, and query probability distance since dsemli,lj≤2⋅h−1, where h is the depth of LST and hence is usually less than 10 while dphyli,lj, as Wi-Fi transmission distance, ranges from hundreds of meters to thousands, whereas the query probability distance is always less than 1. Consequently, we set r=0.03.Meanwhile, in order to balance service quality while the proposed algorithm can resist inference attacks effectively, we should take into account bothPL and Qosloss. So, we propose a location anonymous optimization method based on Stackelberg game, which introduces Stackelberg game to optimize the dummy location selection algorithm. More specifically, we formalize the mutual optimization of user-adversary objectives (location privacy vs. correctness of inferring location) by using the framework of Stackelberg games, to find an optimal dummy location set. The optimal dummy location set can resist single-point attacks and inference attacks while effectively balancing service quality and location privacy.The main idea ofSPDDS is to first select an offset location to replace the user’s real location; secondly, selecting all locations that satisfy the semantic difference with the existing locations in the current dummy location set as the dummy location candidate set DLCS; then, selecting an optimal location in the DLCS which refers to the location formed by satisfying (14); finally, a set consisting of an offset location and k−1 dummy locations is generated. Algorithm 1 shows the formal description of the SPDDS algorithm.Algorithm 1:A dummy location selection algorithm based on location semantic and physical distance.
Input:l: user’s real locationS: user’s privacy requirementMapcur: map information in current Wi-Fi AP LST: location semantic tree LQP: location query probability;Output:DLS: dummy location set;(1)
Divide theMapcur as the sample space into m×m grids;(2)
Generate semantic distance matricSDM according to the LST and geographic distance matrix GDM according to the Mapcur and probability distance matric PDM according to the LQP respectively(3)
According toGDM and PDM, choose the n−1 locations with pi>0, which are closest to l, and then a offset location set Mset consisting of the n−1 locations and l has been generated;(4)
Randomly choose a location fromMset as offset location ld(5)
Generate a dummy location candidate setDLCS for all pi>0 locations in the wholegrid space;(6)
DLS=ld(7)
Removeld from DLCS;(8)
whileDLS<kdo(9)
ifDLCS=ϕthen(10)
anonymity failed;(11)
else(12)
max=0; BestLoc=ϕ;(13)
foreachLocinDLCSdo(14)
ifdsemLoc,DLS.last≤uthen(15)
anonymity failed;(16)
go back to line 13;(17)
else(18)
m=dsemLoc,DLS.last+r⋅dphyLoc,DLS.last/dqueLoc,DLS.last(19)
compute the maximumm according to SDM, GDM and PDM, which is recorded with max, and then assign the corresponding Loc to BestLoc(20)
end(21)
end(22)
DLS=DLS∪BestLoc(23)
removeBestLoc from DLCS;(24)
end(25)
end(26)
outputDLS;


## 5.2. A Location Anonymous Optimization Method Based on Stackelberg Game

We propose a location anonymous optimization method based on Stackelberg game, which optimizes the dummy location selection algorithm by introducing the Stackelberg game. More specifically, we formalize the mutual optimization of user-adversary objectives (location privacy vs. correctness of inferring location) by using the framework of Stackelberg game, and based on which we construct the related linear programs. We can find an optimal dummy location set by solving the linear programs, which can resist single-point attacks and inference attacks while effectively balancing service quality and location privacy.


### 5.2.1. Location Inference Model

In the location inference model, the adversary has certain background knowledge such as the user’s service request history records, LPPM, etc. Using the user’s service request history records, the adversary can calculate the user’s query probability distributionφl. When the user sends a query request again, if the location query probability distribution in the anonymous set is not uniform, the adversary can infer that the user is likely to be located in a location with a higher probability. While for the LPPM, the adversary can analyze the intercepted location request, combined with the anonymity algorithm, to infer the probability that each location in the anonymous set is the user’s true location, so as to make the inference attack more accurate.Based on the existing knowledgeφl,fDLS|l, etc.), the adversary can form the posterior distribution on the true location l of the user, conditional on the anonymous set DLS:(15)Prl|DLS=Prl,DLSPrDLS=φlfDLS|l∑lφlfDLS|l.The adversary’s objective is then to choosel^ to minimize the user’s conditional expected privacy, where the expectation is taken under Prl|DLS. The user’s conditional expected privacy for an arbitrary l^ is(16)∑lPrl|DLSdphyl,l^,and for the minimizing l^, it is(17)minl^∑lPrl|DLSdphyl,l^.If there are multiple values ofl^ that satisfy (17), then the adversary randomizes arbitrarily among them. The probability with which l^ is chosen in this randomization is gl^|DLS.


### 5.2.2. Stackelberg Game Optimization Process

Here, we assume that the adversary has some background knowledge. Specifically, he will infer the user’s actual locationl as much as possible according to φl, the LPPM used by the LA, the anonymous result DLS, and other background knowledge. Relatively, we can assume that all the background knowledge that LA knows will be used by the adversary, so LA can use the adversary’s optimal attack strategy as a parameter to optimize the generation process of the dummy location set DLS.We formalize the process above by using the framework of Stackelberg game. In a Stackelberg game the leader, in our case, the LA plays first by giving the dummy location setDLS according to the relative location privacy protection algorithm fDLS|l. The follower, in our case the adversary, plays next by estimating the user’s true location, knowing some background knowledge.We use the distance between the adversary’s inferred locationl^ and the user’s actual location l to measure the utility of the participants in the game: the greater the distance, the greater the LA returns, indicating that the anonymous algorithm is more effective in resisting inference attacks; on the contrary, the smaller the distance, the greater the adversary returns, the more effective the adversary’s attack strategy.The game model is also an instance of a zero-sum game, as the adversary’s gains (or losses) of utility is exactly balanced by the losses (or gains) of the utility of the user: the information gained (lost) by the adversary is the location privacy lost (gained) by the user.The purpose of Stackelberg game optimization is to findSSE so that the adversary cannot obtain more benefits by optimizing the attack strategy (that is, the adversary cannot make more accurate inferences about the actual location of the user). In this paper, SPDDS optimized by Stackelberg game is denoted as SPDDS_SG.It should be noted thatDLS is the result obtained by ld further anonymously, so fDLS|l can be further expressed by(18)fDLS|l=fld|l⋅fDLS|ld.In some cases,fDLS|l and fld|l are equal, the reason is that the adversary can filter out dummy locations except ld in such cases.We see that, for a givenDLS, the user’s conditional expected privacy is given by (17). The probability that DLS is output by the LPPM is PrDLS=∑lφlfDLS|l. Hence, the user’s unconditional expected privacy (averaged over all DLS is(19)∑DLSPrDLSminl^∑lPrl|DLSdphyl,l^=∑DLSminl^∑lφlfDLS|ldphyl,l^.To facilitate the computations, we define(20)xΔ¯¯minl^∑lφlfDLS|ldphyl,l^.Incorporatingx into (19), we write the unconditional expected privacy of the user as(21)∑DLSx,which the user aims to maximize by choosing the optimal DLS. To facilitate the computations, (20) can be transformed to a series of linear constraints:(22)x≤∑lφlfDLS|ldphyl,l^=∑lφlfld|lfDLS|lddphyl,l^,∀l^.In addition,SPDDS_SG needs to conceal the user’s real location on the premise of ensuring the user’s service quality. In order to ensure the quality of service, we set the service quality threshold Qlossmax to limit the maximum service quality loss. The specific process is (23)∑l,ldφlfld|ldphyl,ld≤Qlossmax.In summary,SPDDS_SG can be solved by a linear program. The final definition of linear program is (24)Maximize∑DLSx,s.t.C1:x≤∑lφlfld|lfDLS|lddphyl,l^,C2:∑l,ldφlfld|ldphyl,ld≤Qlossmax,C3:∑DLSfDLS|l=1,C4:fDLS|l≥0,∀l,DLS,where C1 is used to maximize the utility of the adversary; C2 reflects the service quality constraint; C3 indicates that the sum of the generation probability of the dummy location set must be 1; C4 indicates the probability of each candidate dummy location set is greater than zero.SPDDS_SG solves the objective function under the constraints in (24) and obtains the optimal dummy location set, which can resist single-point attacks and inference attacks while effectively balancing service quality and location privacy.


## 5.2.1. Location Inference Model

In the location inference model, the adversary has certain background knowledge such as the user’s service request history records, LPPM, etc. Using the user’s service request history records, the adversary can calculate the user’s query probability distributionφl. When the user sends a query request again, if the location query probability distribution in the anonymous set is not uniform, the adversary can infer that the user is likely to be located in a location with a higher probability. While for the LPPM, the adversary can analyze the intercepted location request, combined with the anonymity algorithm, to infer the probability that each location in the anonymous set is the user’s true location, so as to make the inference attack more accurate.Based on the existing knowledgeφl,fDLS|l, etc.), the adversary can form the posterior distribution on the true location l of the user, conditional on the anonymous set DLS:(15)Prl|DLS=Prl,DLSPrDLS=φlfDLS|l∑lφlfDLS|l.The adversary’s objective is then to choosel^ to minimize the user’s conditional expected privacy, where the expectation is taken under Prl|DLS. The user’s conditional expected privacy for an arbitrary l^ is(16)∑lPrl|DLSdphyl,l^,and for the minimizing l^, it is(17)minl^∑lPrl|DLSdphyl,l^.If there are multiple values ofl^ that satisfy (17), then the adversary randomizes arbitrarily among them. The probability with which l^ is chosen in this randomization is gl^|DLS.


## 5.2.2. Stackelberg Game Optimization Process

Here, we assume that the adversary has some background knowledge. Specifically, he will infer the user’s actual locationl as much as possible according to φl, the LPPM used by the LA, the anonymous result DLS, and other background knowledge. Relatively, we can assume that all the background knowledge that LA knows will be used by the adversary, so LA can use the adversary’s optimal attack strategy as a parameter to optimize the generation process of the dummy location set DLS.We formalize the process above by using the framework of Stackelberg game. In a Stackelberg game the leader, in our case, the LA plays first by giving the dummy location setDLS according to the relative location privacy protection algorithm fDLS|l. The follower, in our case the adversary, plays next by estimating the user’s true location, knowing some background knowledge.We use the distance between the adversary’s inferred locationl^ and the user’s actual location l to measure the utility of the participants in the game: the greater the distance, the greater the LA returns, indicating that the anonymous algorithm is more effective in resisting inference attacks; on the contrary, the smaller the distance, the greater the adversary returns, the more effective the adversary’s attack strategy.The game model is also an instance of a zero-sum game, as the adversary’s gains (or losses) of utility is exactly balanced by the losses (or gains) of the utility of the user: the information gained (lost) by the adversary is the location privacy lost (gained) by the user.The purpose of Stackelberg game optimization is to findSSE so that the adversary cannot obtain more benefits by optimizing the attack strategy (that is, the adversary cannot make more accurate inferences about the actual location of the user). In this paper, SPDDS optimized by Stackelberg game is denoted as SPDDS_SG.It should be noted thatDLS is the result obtained by ld further anonymously, so fDLS|l can be further expressed by(18)fDLS|l=fld|l⋅fDLS|ld.In some cases,fDLS|l and fld|l are equal, the reason is that the adversary can filter out dummy locations except ld in such cases.We see that, for a givenDLS, the user’s conditional expected privacy is given by (17). The probability that DLS is output by the LPPM is PrDLS=∑lφlfDLS|l. Hence, the user’s unconditional expected privacy (averaged over all DLS is(19)∑DLSPrDLSminl^∑lPrl|DLSdphyl,l^=∑DLSminl^∑lφlfDLS|ldphyl,l^.To facilitate the computations, we define(20)xΔ¯¯minl^∑lφlfDLS|ldphyl,l^.Incorporatingx into (19), we write the unconditional expected privacy of the user as(21)∑DLSx,which the user aims to maximize by choosing the optimal DLS. To facilitate the computations, (20) can be transformed to a series of linear constraints:(22)x≤∑lφlfDLS|ldphyl,l^=∑lφlfld|lfDLS|lddphyl,l^,∀l^.In addition,SPDDS_SG needs to conceal the user’s real location on the premise of ensuring the user’s service quality. In order to ensure the quality of service, we set the service quality threshold Qlossmax to limit the maximum service quality loss. The specific process is (23)∑l,ldφlfld|ldphyl,ld≤Qlossmax.In summary,SPDDS_SG can be solved by a linear program. The final definition of linear program is (24)Maximize∑DLSx,s.t.C1:x≤∑lφlfld|lfDLS|lddphyl,l^,C2:∑l,ldφlfld|ldphyl,ld≤Qlossmax,C3:∑DLSfDLS|l=1,C4:fDLS|l≥0,∀l,DLS,where C1 is used to maximize the utility of the adversary; C2 reflects the service quality constraint; C3 indicates that the sum of the generation probability of the dummy location set must be 1; C4 indicates the probability of each candidate dummy location set is greater than zero.SPDDS_SG solves the objective function under the constraints in (24) and obtains the optimal dummy location set, which can resist single-point attacks and inference attacks while effectively balancing service quality and location privacy.


## 6. Simulations and Results

In this section, we use Python software to simulate the experiment. First, we give the relevant parameters of the experiment. Furthermore, we simulate the experimental results and analysis of the proposed scheme.


### 6.1. Simulation Setup

Our scheme is implemented in MATLAB and performed on a Windows 10 PC with an Intel Core i5-8500 CPU, a 3.00 GHz processor and a 8.00 GB main memory. We use a real road map of Guangzhou from Google Maps, since Guangzhou as a provincial capital in southern China is a big city with enough users in LBS and its central urban area has been covered by Wi-Fi APs in 2016. The coverage area of each Wi-Fi AP is about700∼800m, the sample space is divided into 13×13 cells with equal size, and a total of 13 559 sample trajectories are used as historical data to calculate the historical query probability of each cell. Besides, all locations in our experiments are divided into 6 categories semantically as follows: Education and Science, Administration and Housing, Medical care, Shopping malls, Public places, Catering and Entertainment. The value ranges of the main parameters u and k of the experiment are 3≤u≤7 and 2≤k≤30, respectively.


### 6.2. Results and Analysis

We first evaluate the effectiveness of our proposed scheme in resisting single-point attacks from three assessment metrics as follows: (1)PERL. As is shown in Definition 5, it reflects the effectiveness of the algorithm in resisting side information attack. (2) PD. As is shown in Definition 6, the larger the PD, the more dispersed the dummy locations in the DLS, and the better the effectiveness of the algorithm in resisting homogeneity attack. (3) θ. As is shown in Definition 7, it refers to the level of semantic diversity in the anonymous set, which reflects the effectiveness of the algorithm in resisting location similarity attack; Next, evaluating the effectiveness of the scheme in resisting inference attack while balancing location privacy and service quality from two assessment metrics as follows: (1) PL. As is shown in Definition 8, the larger the PL is, the better the effect of LPPM against inference attacks is. (2) Qosloss. As is shown in Definition 9, it reflects the effectiveness of the algorithm in balancing location privacy and service quality.


#### 6.2.1. Effectiveness of the Scheme against Single-point Attacks

(1)PERLvsk. In Figure 3(a), we compare the PERL of KLPPS, Max Min Dist DS [27], Simp Max Min Dist DS [27], enhanced−DLS [23], and HCLS−SG [31] schemes. As we can see, the PERL of the five schemes shows a downward trend with the increase of k, which means that the larger the k, the more difficult it is for adversaries to filter out invalid locations in the anonymous set through side information attacks, the better the effect of the scheme against side information attacks. The PERL of the KLPPS, enhanced−DLS, and HCLS−SG is lower than that of the Max Min Dist DS and Simp Max Min Dist DS. And that of the KLPPS, enhanced−DLS, and HCLS−SG are basically the same. The reason is that the KLPPS, enhanced−DLS and HCLS−SG all consider the query probability and avoid selecting locations with low access probability such as lakes and forests to form an anonymous set; whereas the Max Min Dist DS and Simp Max Min Dist DS do not consider the query probability, so there will be cases where invalid locations are selected, and thereby the adversary can filter out ones through side information attacks. In summary, the KLPPS scheme can effectively resist side information attacks.Figure 3
KLPPS scheme against single-point attack. (a)PERL vs.k. (b)  PD vs.k. (c)  θvs.k.
(a)(b)(c)(2)PDvsk. Figure 3(b) shows the PD comparison chart of KLPPS, Max Min Dist DS, Simp Max Min Dist DS, enhanced−DLS, and HCLS−SG schemes. As we can see, the PD of KLPPS, HCLS−SG, enhanced−DLS, and Max Min Dist DS are close when k≤4; at k≥5, the PD of Max Min Dist DS is slightly larger than that of KLPPS, HCLS−SG and enhanced−DLS. Under the same value of k, the PD of KLPPS, HCLS−SG, and enhanced−DLS is slightly larger than that of Simp Max Min Dist DS. In additional, with the increase of k, the PD of the five schemes are both reduced gradually. The reason for this is obvious: it becomes harder to maintain a high level of dispersion with more and more dummies. In summary, Max Min Dist DS has the largest PD, KLPPS, HCLS−SG, enhanced−DLS, and Simp Max Min Dist DS decrease in order, which means that the Max Min Dist DS is better in resisting homogeneity attacks than the other four schemes, but the KLPPS scheme is also acceptable.(3)θvsk. Figure 3(c) shows the value of θ comparison between KLPPS, Max Min Dist DS, Simp Max Min Dist DS, enhanced−DLS, and HCLS−SG schemes. As shown in Figure 3(c), with the increases of k, the value of θ of KLPPS, Max Min Dist DS, and Simp Max Min Dist DS schemes hardly change and close to the maximum value 1. However, that of enhanced−DLS and HCLS−SG schemes is always at a relative low. The reason is that the KLPPS, Max Min Dist DS, and Simp Max Min Dist DS schemes all consider the semantic information of the location when selecting dummy locations, thereby ensuring semantic diversity, while the enhanced−DLS and HCLS−SG schemes only consider the query probability of each location point instead of considering the situation that each location point may have the same semantic information. Moreover, the location points with higher query probability are often in hotspot areas, between which the semantic information is very similar and therefore not satisfying the semantic diversity. Consequently, the enhanced−DLS and HCLS−SG schemes behave such badly in semantic diversity that they cannot resist location similarity attacks. In summary, the KLPPS scheme can effectively resist location similarity attacks.The experimental results above show that theKLPPS scheme can effectively resist homogeneity attacks, location similarity attacks, and side information attacks simultaneously compared with the Max Min Dist DS, Simp Max Min Dist DS, enhanced−DLS, and HCLS−SG schemes, thereby effectively resisting single-point attacks.


#### 6.2.2. Effectiveness of the Scheme against Inference Attacks and BalancesPL and Qosloss

Combining the location inference model and (6), it can be seen that the adversary can perform inference attacks, the purpose of which is to choose l^ based on existing knowledge to minimize the expected user privacy. (25) defines this attack strategy:(25)l^=argmin PLl^.Combining (6) and (25), we can construct the following linear program to find the optimal l^:(26)minimize∑l,l^,DLSφlfDLS|lgl^|DLSdphyl,l^,s.t.C1:∑l^gl^|DLS=1,∀DLS,C2:gl^|DLS≥0,∀DLS,l^.We use the model defined by (26) to run inference attacks on KLPPS, HCLS [31], SG [13], and HCLS−SG to make a comparison from two aspects of PL and Qosloss, evaluating the effectiveness of the KLPPS scheme.(1)PL. The definition of PL is shown in (6), the larger the PL, the better the effect of LPPM against inference attacks. As shown in (24), the preset service quality loss threshold Qlossmax and anonymous degree k have a greater impact on PL, so we evaluate the effectiveness of the KLPPS scheme against inference attacks from the two assessment metrics of Qlossmax and k.(a)
PL vsQlossmaxWe compare thePL of KLPPS, HCLS, SG, and HCLS−SG schemes under different Qlossmax in Figure 4(a). As shown in the figure, we can draw the following 3 conclusions. First, the PL of KLPPS, SG, and HCLS−SG is significantly better than HCLS, which results from that HCLS does not consider the inference attack strategy of the adversary. Secondly, the KLPPS and HCLS−SG behave better than SG, the reason is that the former two use dummy location anonymity, increasing the difficulty of the adversary’s inference. Finally, with the increase of Qlossmax, the PL of the four schemes all increase, however the growth trend of PL of the four schemes slows down when reaching a certain level, which is related to the query probability distribution of user’s location, indicating that the influence of Qlossmax on PL is limited.(b)
PL vskWe compare thePL of KLPPS, HCLS, SG, and HCLS−SG schemes under different k in Figure 4(b). As we can see, three conclusions have been drawn below. First of all, as the value of k increases, the PL of KLPPS, HCLS, and HCLS−SG are significantly improved while not the SG. The reason is that SG only provides offset locations and does not consider dummy location anonymity; Secondly, the KLPPS and HCLS−SG behave better in improving PL than that of HCLS, which results from that the former two all consider the adversary’s inference attack strategy, while the latter does not, so HCLS is less effective in resisting inference attacks than that of the KLPPS and HCLS−SG; Finally, the growth trend of of the four schemes slows down when reaching a certain level, which results from that the four schemes all use the offset location instead of the real location to protect users’ privacy. More specifically, the choice of ld will make the service quality loss Qosloss is gradually approaching Qlossmax with the increase of k, and the four schemes are all maximized PL under the premise of ensuring that Qosloss≤Qlossmax, which means that when Qosloss gradually approaches Qlossmax, the growth trend of PL slows down until Qosloss=Qlossmax, reaching the maximum value.Figure 4
KLPPS scheme against inference attack. (a)PL vsQlossmax. (b)  PL vsk.
(a)(b)(2)Qosloss. Qosloss is closely related to PL. Specifically, in some cases, users allow losing a certain service quality in exchange for higher privacy. In the experiment, we set the maximum service quality loss that the user can accept as Qlossmax=0,0.5,1,1.5,2,2.5,3,3.5,4,4.5 and analyze the relationship between Qosloss and PL on this condition. Figure 5 shows the experimental results. First of all, it can be seen from the figure that the Qosloss and PL of the three schemes all increase with the increase of Qlossmax. The reason for this is obvious: in the first place, we can see the PL will increase to a certain extent with the increase of Qlossmax from Figure 4(a). In the second place, from the definition of Qlossmax and Qosloss, it is obvious that Qosloss will increase to a certain extent with the increase of Qlossmax. Secondly, under the same Qlossmax, the PL of KLPPS and HCLS−SG is significantly higher than that of HCLS, but Qosloss is also higher than HCLS to a certain extent, which results from that both KLPPS and HCLS−SG will make full use of the limited maximum service quality loss to optimize the selection of dummy location set, so as to improve location privacy as much as possible while ensuring that the loss of service quality does not exceed the constraints of service quality, thereby effectively balancing service quality and location privacy. In addition, under the same Qlossmax, the PL of KLPPS is slightly larger than that of HCLS−SG while Qosloss is slightly smaller than that of HCLS−SG, indicating that KLPPS is better than HCLS−SG in balancing service quality and location privacy.Figure 5
KLPPS scheme balancesPL and Qosloss.The experimental results above show that the scheme can effectively resist inference attacks while effectively balancing service quality and location privacy compared with theSG, HCLS, and HCLS−SG schemes.


## 6.1. Simulation Setup

Our scheme is implemented in MATLAB and performed on a Windows 10 PC with an Intel Core i5-8500 CPU, a 3.00 GHz processor and a 8.00 GB main memory. We use a real road map of Guangzhou from Google Maps, since Guangzhou as a provincial capital in southern China is a big city with enough users in LBS and its central urban area has been covered by Wi-Fi APs in 2016. The coverage area of each Wi-Fi AP is about700∼800m, the sample space is divided into 13×13 cells with equal size, and a total of 13 559 sample trajectories are used as historical data to calculate the historical query probability of each cell. Besides, all locations in our experiments are divided into 6 categories semantically as follows: Education and Science, Administration and Housing, Medical care, Shopping malls, Public places, Catering and Entertainment. The value ranges of the main parameters u and k of the experiment are 3≤u≤7 and 2≤k≤30, respectively.


## 6.2. Results and Analysis

We first evaluate the effectiveness of our proposed scheme in resisting single-point attacks from three assessment metrics as follows: (1)PERL. As is shown in Definition 5, it reflects the effectiveness of the algorithm in resisting side information attack. (2) PD. As is shown in Definition 6, the larger the PD, the more dispersed the dummy locations in the DLS, and the better the effectiveness of the algorithm in resisting homogeneity attack. (3) θ. As is shown in Definition 7, it refers to the level of semantic diversity in the anonymous set, which reflects the effectiveness of the algorithm in resisting location similarity attack; Next, evaluating the effectiveness of the scheme in resisting inference attack while balancing location privacy and service quality from two assessment metrics as follows: (1) PL. As is shown in Definition 8, the larger the PL is, the better the effect of LPPM against inference attacks is. (2) Qosloss. As is shown in Definition 9, it reflects the effectiveness of the algorithm in balancing location privacy and service quality.


### 6.2.1. Effectiveness of the Scheme against Single-point Attacks

(1)PERLvsk. In Figure 3(a), we compare the PERL of KLPPS, Max Min Dist DS [27], Simp Max Min Dist DS [27], enhanced−DLS [23], and HCLS−SG [31] schemes. As we can see, the PERL of the five schemes shows a downward trend with the increase of k, which means that the larger the k, the more difficult it is for adversaries to filter out invalid locations in the anonymous set through side information attacks, the better the effect of the scheme against side information attacks. The PERL of the KLPPS, enhanced−DLS, and HCLS−SG is lower than that of the Max Min Dist DS and Simp Max Min Dist DS. And that of the KLPPS, enhanced−DLS, and HCLS−SG are basically the same. The reason is that the KLPPS, enhanced−DLS and HCLS−SG all consider the query probability and avoid selecting locations with low access probability such as lakes and forests to form an anonymous set; whereas the Max Min Dist DS and Simp Max Min Dist DS do not consider the query probability, so there will be cases where invalid locations are selected, and thereby the adversary can filter out ones through side information attacks. In summary, the KLPPS scheme can effectively resist side information attacks.Figure 3
KLPPS scheme against single-point attack. (a)PERL vs.k. (b)  PD vs.k. (c)  θvs.k.
(a)(b)(c)(2)PDvsk. Figure 3(b) shows the PD comparison chart of KLPPS, Max Min Dist DS, Simp Max Min Dist DS, enhanced−DLS, and HCLS−SG schemes. As we can see, the PD of KLPPS, HCLS−SG, enhanced−DLS, and Max Min Dist DS are close when k≤4; at k≥5, the PD of Max Min Dist DS is slightly larger than that of KLPPS, HCLS−SG and enhanced−DLS. Under the same value of k, the PD of KLPPS, HCLS−SG, and enhanced−DLS is slightly larger than that of Simp Max Min Dist DS. In additional, with the increase of k, the PD of the five schemes are both reduced gradually. The reason for this is obvious: it becomes harder to maintain a high level of dispersion with more and more dummies. In summary, Max Min Dist DS has the largest PD, KLPPS, HCLS−SG, enhanced−DLS, and Simp Max Min Dist DS decrease in order, which means that the Max Min Dist DS is better in resisting homogeneity attacks than the other four schemes, but the KLPPS scheme is also acceptable.(3)θvsk. Figure 3(c) shows the value of θ comparison between KLPPS, Max Min Dist DS, Simp Max Min Dist DS, enhanced−DLS, and HCLS−SG schemes. As shown in Figure 3(c), with the increases of k, the value of θ of KLPPS, Max Min Dist DS, and Simp Max Min Dist DS schemes hardly change and close to the maximum value 1. However, that of enhanced−DLS and HCLS−SG schemes is always at a relative low. The reason is that the KLPPS, Max Min Dist DS, and Simp Max Min Dist DS schemes all consider the semantic information of the location when selecting dummy locations, thereby ensuring semantic diversity, while the enhanced−DLS and HCLS−SG schemes only consider the query probability of each location point instead of considering the situation that each location point may have the same semantic information. Moreover, the location points with higher query probability are often in hotspot areas, between which the semantic information is very similar and therefore not satisfying the semantic diversity. Consequently, the enhanced−DLS and HCLS−SG schemes behave such badly in semantic diversity that they cannot resist location similarity attacks. In summary, the KLPPS scheme can effectively resist location similarity attacks.The experimental results above show that theKLPPS scheme can effectively resist homogeneity attacks, location similarity attacks, and side information attacks simultaneously compared with the Max Min Dist DS, Simp Max Min Dist DS, enhanced−DLS, and HCLS−SG schemes, thereby effectively resisting single-point attacks.


### 6.2.2. Effectiveness of the Scheme against Inference Attacks and BalancesPL and Qosloss

Combining the location inference model and (6), it can be seen that the adversary can perform inference attacks, the purpose of which is to choose l^ based on existing knowledge to minimize the expected user privacy. (25) defines this attack strategy:(25)l^=argmin PLl^.Combining (6) and (25), we can construct the following linear program to find the optimal l^:(26)minimize∑l,l^,DLSφlfDLS|lgl^|DLSdphyl,l^,s.t.C1:∑l^gl^|DLS=1,∀DLS,C2:gl^|DLS≥0,∀DLS,l^.We use the model defined by (26) to run inference attacks on KLPPS, HCLS [31], SG [13], and HCLS−SG to make a comparison from two aspects of PL and Qosloss, evaluating the effectiveness of the KLPPS scheme.(1)PL. The definition of PL is shown in (6), the larger the PL, the better the effect of LPPM against inference attacks. As shown in (24), the preset service quality loss threshold Qlossmax and anonymous degree k have a greater impact on PL, so we evaluate the effectiveness of the KLPPS scheme against inference attacks from the two assessment metrics of Qlossmax and k.(a)
PL vsQlossmaxWe compare thePL of KLPPS, HCLS, SG, and HCLS−SG schemes under different Qlossmax in Figure 4(a). As shown in the figure, we can draw the following 3 conclusions. First, the PL of KLPPS, SG, and HCLS−SG is significantly better than HCLS, which results from that HCLS does not consider the inference attack strategy of the adversary. Secondly, the KLPPS and HCLS−SG behave better than SG, the reason is that the former two use dummy location anonymity, increasing the difficulty of the adversary’s inference. Finally, with the increase of Qlossmax, the PL of the four schemes all increase, however the growth trend of PL of the four schemes slows down when reaching a certain level, which is related to the query probability distribution of user’s location, indicating that the influence of Qlossmax on PL is limited.(b)
PL vskWe compare thePL of KLPPS, HCLS, SG, and HCLS−SG schemes under different k in Figure 4(b). As we can see, three conclusions have been drawn below. First of all, as the value of k increases, the PL of KLPPS, HCLS, and HCLS−SG are significantly improved while not the SG. The reason is that SG only provides offset locations and does not consider dummy location anonymity; Secondly, the KLPPS and HCLS−SG behave better in improving PL than that of HCLS, which results from that the former two all consider the adversary’s inference attack strategy, while the latter does not, so HCLS is less effective in resisting inference attacks than that of the KLPPS and HCLS−SG; Finally, the growth trend of of the four schemes slows down when reaching a certain level, which results from that the four schemes all use the offset location instead of the real location to protect users’ privacy. More specifically, the choice of ld will make the service quality loss Qosloss is gradually approaching Qlossmax with the increase of k, and the four schemes are all maximized PL under the premise of ensuring that Qosloss≤Qlossmax, which means that when Qosloss gradually approaches Qlossmax, the growth trend of PL slows down until Qosloss=Qlossmax, reaching the maximum value.Figure 4
KLPPS scheme against inference attack. (a)PL vsQlossmax. (b)  PL vsk.
(a)(b)(2)Qosloss. Qosloss is closely related to PL. Specifically, in some cases, users allow losing a certain service quality in exchange for higher privacy. In the experiment, we set the maximum service quality loss that the user can accept as Qlossmax=0,0.5,1,1.5,2,2.5,3,3.5,4,4.5 and analyze the relationship between Qosloss and PL on this condition. Figure 5 shows the experimental results. First of all, it can be seen from the figure that the Qosloss and PL of the three schemes all increase with the increase of Qlossmax. The reason for this is obvious: in the first place, we can see the PL will increase to a certain extent with the increase of Qlossmax from Figure 4(a). In the second place, from the definition of Qlossmax and Qosloss, it is obvious that Qosloss will increase to a certain extent with the increase of Qlossmax. Secondly, under the same Qlossmax, the PL of KLPPS and HCLS−SG is significantly higher than that of HCLS, but Qosloss is also higher than HCLS to a certain extent, which results from that both KLPPS and HCLS−SG will make full use of the limited maximum service quality loss to optimize the selection of dummy location set, so as to improve location privacy as much as possible while ensuring that the loss of service quality does not exceed the constraints of service quality, thereby effectively balancing service quality and location privacy. In addition, under the same Qlossmax, the PL of KLPPS is slightly larger than that of HCLS−SG while Qosloss is slightly smaller than that of HCLS−SG, indicating that KLPPS is better than HCLS−SG in balancing service quality and location privacy.Figure 5
KLPPS scheme balancesPL and Qosloss.The experimental results above show that the scheme can effectively resist inference attacks while effectively balancing service quality and location privacy compared with theSG, HCLS, and HCLS−SG schemes.


## 6.2.1. Effectiveness of the Scheme against Single-point Attacks

(1)PERLvsk. In Figure 3(a), we compare the PERL of KLPPS, Max Min Dist DS [27], Simp Max Min Dist DS [27], enhanced−DLS [23], and HCLS−SG [31] schemes. As we can see, the PERL of the five schemes shows a downward trend with the increase of k, which means that the larger the k, the more difficult it is for adversaries to filter out invalid locations in the anonymous set through side information attacks, the better the effect of the scheme against side information attacks. The PERL of the KLPPS, enhanced−DLS, and HCLS−SG is lower than that of the Max Min Dist DS and Simp Max Min Dist DS. And that of the KLPPS, enhanced−DLS, and HCLS−SG are basically the same. The reason is that the KLPPS, enhanced−DLS and HCLS−SG all consider the query probability and avoid selecting locations with low access probability such as lakes and forests to form an anonymous set; whereas the Max Min Dist DS and Simp Max Min Dist DS do not consider the query probability, so there will be cases where invalid locations are selected, and thereby the adversary can filter out ones through side information attacks. In summary, the KLPPS scheme can effectively resist side information attacks.Figure 3
KLPPS scheme against single-point attack. (a)PERL vs.k. (b)  PD vs.k. (c)  θvs.k.
(a)(b)(c)(2)PDvsk. Figure 3(b) shows the PD comparison chart of KLPPS, Max Min Dist DS, Simp Max Min Dist DS, enhanced−DLS, and HCLS−SG schemes. As we can see, the PD of KLPPS, HCLS−SG, enhanced−DLS, and Max Min Dist DS are close when k≤4; at k≥5, the PD of Max Min Dist DS is slightly larger than that of KLPPS, HCLS−SG and enhanced−DLS. Under the same value of k, the PD of KLPPS, HCLS−SG, and enhanced−DLS is slightly larger than that of Simp Max Min Dist DS. In additional, with the increase of k, the PD of the five schemes are both reduced gradually. The reason for this is obvious: it becomes harder to maintain a high level of dispersion with more and more dummies. In summary, Max Min Dist DS has the largest PD, KLPPS, HCLS−SG, enhanced−DLS, and Simp Max Min Dist DS decrease in order, which means that the Max Min Dist DS is better in resisting homogeneity attacks than the other four schemes, but the KLPPS scheme is also acceptable.(3)θvsk. Figure 3(c) shows the value of θ comparison between KLPPS, Max Min Dist DS, Simp Max Min Dist DS, enhanced−DLS, and HCLS−SG schemes. As shown in Figure 3(c), with the increases of k, the value of θ of KLPPS, Max Min Dist DS, and Simp Max Min Dist DS schemes hardly change and close to the maximum value 1. However, that of enhanced−DLS and HCLS−SG schemes is always at a relative low. The reason is that the KLPPS, Max Min Dist DS, and Simp Max Min Dist DS schemes all consider the semantic information of the location when selecting dummy locations, thereby ensuring semantic diversity, while the enhanced−DLS and HCLS−SG schemes only consider the query probability of each location point instead of considering the situation that each location point may have the same semantic information. Moreover, the location points with higher query probability are often in hotspot areas, between which the semantic information is very similar and therefore not satisfying the semantic diversity. Consequently, the enhanced−DLS and HCLS−SG schemes behave such badly in semantic diversity that they cannot resist location similarity attacks. In summary, the KLPPS scheme can effectively resist location similarity attacks.The experimental results above show that theKLPPS scheme can effectively resist homogeneity attacks, location similarity attacks, and side information attacks simultaneously compared with the Max Min Dist DS, Simp Max Min Dist DS, enhanced−DLS, and HCLS−SG schemes, thereby effectively resisting single-point attacks.


## 6.2.2. Effectiveness of the Scheme against Inference Attacks and BalancesPL and Qosloss

Combining the location inference model and (6), it can be seen that the adversary can perform inference attacks, the purpose of which is to choose l^ based on existing knowledge to minimize the expected user privacy. (25) defines this attack strategy:(25)l^=argmin PLl^.Combining (6) and (25), we can construct the following linear program to find the optimal l^:(26)minimize∑l,l^,DLSφlfDLS|lgl^|DLSdphyl,l^,s.t.C1:∑l^gl^|DLS=1,∀DLS,C2:gl^|DLS≥0,∀DLS,l^.We use the model defined by (26) to run inference attacks on KLPPS, HCLS [31], SG [13], and HCLS−SG to make a comparison from two aspects of PL and Qosloss, evaluating the effectiveness of the KLPPS scheme.(1)PL. The definition of PL is shown in (6), the larger the PL, the better the effect of LPPM against inference attacks. As shown in (24), the preset service quality loss threshold Qlossmax and anonymous degree k have a greater impact on PL, so we evaluate the effectiveness of the KLPPS scheme against inference attacks from the two assessment metrics of Qlossmax and k.(a)
PL vsQlossmaxWe compare thePL of KLPPS, HCLS, SG, and HCLS−SG schemes under different Qlossmax in Figure 4(a). As shown in the figure, we can draw the following 3 conclusions. First, the PL of KLPPS, SG, and HCLS−SG is significantly better than HCLS, which results from that HCLS does not consider the inference attack strategy of the adversary. Secondly, the KLPPS and HCLS−SG behave better than SG, the reason is that the former two use dummy location anonymity, increasing the difficulty of the adversary’s inference. Finally, with the increase of Qlossmax, the PL of the four schemes all increase, however the growth trend of PL of the four schemes slows down when reaching a certain level, which is related to the query probability distribution of user’s location, indicating that the influence of Qlossmax on PL is limited.(b)
PL vskWe compare thePL of KLPPS, HCLS, SG, and HCLS−SG schemes under different k in Figure 4(b). As we can see, three conclusions have been drawn below. First of all, as the value of k increases, the PL of KLPPS, HCLS, and HCLS−SG are significantly improved while not the SG. The reason is that SG only provides offset locations and does not consider dummy location anonymity; Secondly, the KLPPS and HCLS−SG behave better in improving PL than that of HCLS, which results from that the former two all consider the adversary’s inference attack strategy, while the latter does not, so HCLS is less effective in resisting inference attacks than that of the KLPPS and HCLS−SG; Finally, the growth trend of of the four schemes slows down when reaching a certain level, which results from that the four schemes all use the offset location instead of the real location to protect users’ privacy. More specifically, the choice of ld will make the service quality loss Qosloss is gradually approaching Qlossmax with the increase of k, and the four schemes are all maximized PL under the premise of ensuring that Qosloss≤Qlossmax, which means that when Qosloss gradually approaches Qlossmax, the growth trend of PL slows down until Qosloss=Qlossmax, reaching the maximum value.Figure 4
KLPPS scheme against inference attack. (a)PL vsQlossmax. (b)  PL vsk.
(a)(b)(2)Qosloss. Qosloss is closely related to PL. Specifically, in some cases, users allow losing a certain service quality in exchange for higher privacy. In the experiment, we set the maximum service quality loss that the user can accept as Qlossmax=0,0.5,1,1.5,2,2.5,3,3.5,4,4.5 and analyze the relationship between Qosloss and PL on this condition. Figure 5 shows the experimental results. First of all, it can be seen from the figure that the Qosloss and PL of the three schemes all increase with the increase of Qlossmax. The reason for this is obvious: in the first place, we can see the PL will increase to a certain extent with the increase of Qlossmax from Figure 4(a). In the second place, from the definition of Qlossmax and Qosloss, it is obvious that Qosloss will increase to a certain extent with the increase of Qlossmax. Secondly, under the same Qlossmax, the PL of KLPPS and HCLS−SG is significantly higher than that of HCLS, but Qosloss is also higher than HCLS to a certain extent, which results from that both KLPPS and HCLS−SG will make full use of the limited maximum service quality loss to optimize the selection of dummy location set, so as to improve location privacy as much as possible while ensuring that the loss of service quality does not exceed the constraints of service quality, thereby effectively balancing service quality and location privacy. In addition, under the same Qlossmax, the PL of KLPPS is slightly larger than that of HCLS−SG while Qosloss is slightly smaller than that of HCLS−SG, indicating that KLPPS is better than HCLS−SG in balancing service quality and location privacy.Figure 5
KLPPS scheme balancesPL and Qosloss.The experimental results above show that the scheme can effectively resist inference attacks while effectively balancing service quality and location privacy compared with theSG, HCLS, and HCLS−SG schemes.


## 7. Conclusion

There are some problems such as single point of failure and without the ability to effectively resist single-point attack and inference attack, etc., in the traditionalk−anonymous location privacy protection schemes. To solve the problems above, by analyzing the merits and drawbacks of the existing location privacy protection system architecture, we propose a semitrusted third party based location privacy protection architecture that can tackle performance bottleneck of mobile device and single point of failure. Then, comprehensively considering the characteristics of side information, semantic diversity, and physical dispersion of locations combined with the ideas of dummy location technology and offset location, a dummy location selection algorithm based on location semantics and physical distance is proposed to effectively resist single-point attacks. Finally, we propose a location anonymous optimization method based on Stackelberg game to optimize the dummy selection algorithm. Specifically, we formalize the mutual optimization of user-adversary objectives (location privacy vs. correctness of inferring location) by using the framework of Stackelberg games, to find an optimal dummy location set. The optimal dummy location set can resist single-point attacks and inference attacks while effectively balancing service quality and location privacy. The experimental results further verify the effectiveness of the proposed scheme. However, our work still has the following shortcomings. First, in LBS, more and more people use continuous query services such as navigation services, etc., while our scheme can be only applied in snapshot query scenario not the continuous query scenario. Secondly, in different application scenarios, users have different requirements for privacy protection level and service quality, so it needs to be improved as much as possible in terms of balancing data validity and privacy levels. The next work hopes to improve our scheme to make it suitable for continuous query scenarios. Meanwhile, aiming at users with different needs in different scenarios, on the basis of further balancing service quality and privacy protection level, we design a personalized location privacy protection scheme.



---

*Source: 9635411-2021-12-07.xml*