# Differential Privacy Location Protection Method Based on the Markov Model

Authors: Hongtao Li; Yue Wang; Feng Guo; Jie Wang; Bo Wang; Chuankun Wu
Journal: Wireless Communications and Mobile Computing
 (2021)

---

## Abstract

Location-based services (LBS) have become an important research area with the rapid development of mobile Internet technology, GPS positioning technology, and the widespread application of smart phones and social networks. LBS can provide convenience and flexibility for the users’ daily life, but at the same time, it also brings security risks to the users’ privacy. Untrusted or malicious LBS servers can collect users’ location data through various ways and disclose it to the third party, thus causing users’ privacy leakage. In this paper, a differential privacy location protection method based on the Markov model for user’s location privacy is proposed. Firstly, the transition probability matrix between states of then-order Markov model is used to predict the occurrence state and development trend of events; thereby, the user’s location is predicted, and then a location prediction algorithm based on the Markov model (LPAM) is proposed. Secondly, a location protection algorithm based on differential privacy (LPADP) is proposed, in which location privacy tree (LPT) is constructed according to the location data and the difficulty of retrieval, the two nodes with the largest predicted value of LPT are allocated with a reasonable privacy budget, and Laplace noise is added to protect location privacy. Theoretical analysis and experimental results show that the proposed method not only meets the requirements of differential privacy and protects location privacy effectively but also has high data availability and low time complexity.


---

## Body

## 1. Introduction

In recent years, the rapid development of mobile Internet technology, Internet of things technology, and GPS positioning technology has promoted the rapid development of various smart devices and social networks, making location-based services (LBS) widely applied in people’s lives [1–4]. Users can send their identity, location, interests, and other information to the LBS server through the LBS application, so as to query and obtain the required information, such as the nearest shopping center, supermarket, and restaurant. The LBS service provider can also predict the next location of the user according to the current location of the user and provide the user with relevant information of the area before the user enters the next area. For example, in the aspect of traffic, vehicle positioning and prediction can enable users to get a faster and more convenient path. However, while users enjoy the convenience brought by LBS service, it will also lead to the risk of sensitive information leakage. When users query information from the LBS server, they need to send personal identity, location, interests, and other information to the LBS server. If this information is leaked by untrusted or malicious LBS servers, the attackers can not only link the user’s identity with location and interests but can also infer more user’s private information. Therefore, location privacy protection in LBS is becoming more and more important and has been attached great importance to by relevant fields.At present, domestic and foreign researchers have conducted a large number of studies on location privacy protection and proposed a variety of solutions to the privacy protection problems in LBS. The dominating location privacy protection technologies include cryptography,k-anonymity, and differential privacy.Cryptography was proposed by Diffie and Hellman with the idea of public key cryptography in 1976 [5]. The main idea of location privacy protection technology using cryptography is to encrypt the user’s query information. Because the users’ query information is not visible to the server, the attacker cannot infer the true data of the user even after obtaining the encrypted data. Although cryptography can effectively protect the privacy of users, it costs a lot in computing and communication and suffers insufficient data availability.k-anonymity was proposed by Samarati and Sweeney in 1998 [6], which can ensure that each individual record stored in the publication dataset cannot be distinguished from other k−1 individuals for sensitive attributes. k-anonymity mechanism requires that the same quasiidentifier must have at least k records; so, the attackers cannot link the records through the quasiidentifier. Although k-anonymity technology can prevent identity disclosure, it cannot prevent attribute disclosure nor can it resist homogeneous attacks and background knowledge attacks.Differential privacy was proposed by Dwork et al. in 2006 [7], which can protect the privacy information effectively even if the attacker gets the user’ background knowledge. Differential privacy has a rigorous statistical model that facilitates the use of mathematical tools and quantitative analysis and proof.At present, location privacy protection faces great challenges. In this paper, a differential privacy location protection method based on the Markov model is proposed. The main contributions of this paper as follows:(1)
In this paper, the Markov model is used to predict the location information, and the probability transfer matrix between the states of theN-order Markov model is used to predict the state of occurrence of events and their development trend, so as to predict the user’s location. Then, a location prediction algorithm based on the Markov model (LPAM) is proposed(2)
A location protection algorithm based on differential privacy (LPADP) is proposed, in which location privacy tree (LPT) is constructed according to the location data and the difficulty of retrieval, the two nodes with the largest predicted value of LPT are allocated a reasonable privacy budget, and Laplace noise is added to protect location privacy(3)
A comprehensive theoretical and experimental analysis has been done between the proposed method and the related works. Results show that our method meets the requirements of differential privacy and protects user location privacy effectivelyThe rest of this paper is organized as follows: Section2 introduces the related works; Section 3 introduces the definition, transition probability matrix, system model, and attack model; Section 4 introduces the LPAM algorithm and LPADP proposed in this paper; Section 5 conducts experiments on data availability, privacy protection degree, and algorithm run-time of algorithm proposed in this paper; Section 6 is the conclusion of this paper.


## 2. Preliminaries

### 2.1. Definitions

Definition 1. (Markov model) [8, 9].
LetE be the discrete state space of random sequence Xn,n=0,1,2,⋯. If for any m nonnegative integers n1,n2,⋯,nm0≤n1<n2<⋯<nm and any natural number k, and any i1,i2,⋯,im, j∈E satisfies the following conditions:
(1)PXnm+k∣Xn1,Xn2,⋯,Xnm=PXnm+k∣Xnm.
Then,Xn,n=0,1,2,⋯ is called the one-order Markov model. This equation shows that the state of the next moment only depends on the present moment and has nothing to do with the past moment. This property is the Markov model with no aftereffect.
Then-order Markov model means that the state of the next moment is not only related to the present moment but also related to the past moment; so, the prediction is more comprehensive and effective.Definition 2. (Neighboring dataset).
Let the data setD and D′ have the same attribute structure, and the symmetric difference between the D and D′ is recorded as D∆D′,D∆D′ represents the number of symmetry differences. If D∆D′=1, then D and D′D′ are called neighboring dataset (also known as brothers data sets).Definition 3. (Differential privacy) [10, 11].
There is a random algorithmM and all possible outputs of M are SM. For any two neighboring datasets D and D′, if algorithm M satisfies the following conditions:
(2)PrMD∈SM≤eε×PrMD′∈SM,
then algorithmM provides ε-differential privacy protection, where parameter ε is called privacy protection budget. The larger the ε is, the higher the data availability is, and the lower the degree of privacy protection is; on the contrary, the lower the data availability is, the higher the degree of privacy protection is.Definition 4. (Sensitivity).
Letd be a positive integer, D is a a set of data sets, and f:D→Rd is a function. The function sensitivity represented by ∆f has the following definition: ∆f=maxfD−fD′1,where .1 is the Manhattan distance.Definition 5. (Laplace mechanism) [12, 13].
Given datasetD, there is a function f:D⟶Rd, the sensitivity is ∆f, and then the random algorithm MD=fD+Y provides ε-differential privacy protection, where Y~Lap∆f/ε is the random noise and obeys the Laplace distribution with the scale parameter ∆f/ε.


### 2.2. Transition Probability

In this paper, then-order Markov model is used to predict the location. The basic method of Markov prediction is to use the transition probability matrix between states to predict the occurrence and development probability of events.The transition probability is derived by using the one-order Markov model [14, 15].
(3)P=Nij∑j=1nNij,where Nij is the number of times that location i turns to location j, and P is called one-step transition probability.The recurrence relation can be obtained by C-K equation.(4)Pn=PPn−1=Pn−1P,(5)Pn=Pn,where Pn is called the n-step transition probability matrix of the Markov model.


### 2.3. System Structure and Threat Model

The system structure of this paper is shown in Figure1, which is mainly composed of client module, privacy protection module, and location service provider module. The client module acquires the user’s location information mainly through the GPS positioning module and stores the location data in the database. The privacy protection module is composed of prediction module and location protection module. The prediction module predicts users’ location by the Markov model, while the location protection module protects users’ location by differential privacy. Location service providers can respond to users’ query requests, feedback the query results to users, and use the feedback results for data analysis, data sharing and data query, and other services.Figure 1
System structure.In this paper, a differential privacy location protection method based on the Markov model is proposed to solve the problem of users’ location privacy disclosure. The user’s location is acquired through the GPS positioning module and stored in the database. In the prediction module, then-order Markov model is used to predict the user’s location, and the LPAM algorithm is proposed. In the location protection module, differential privacy technology is used to protect location data, and LPADP algorithm is proposed. Location service providers can respond to users’ query requests, feedback the query results to users, and use the feedback results for data analysis, data sharing, and data query and other services.Almost all LBS providers collect users’ personal data, such as identity, location, and interests. Many LBS providers provide different security guarantees, such as Google, Twitter, and Youtube. Once these LBS providers are attacked, users’ privacy information will be leaked. The threat model of this paper is shown in Figure2. The users’ location data is acquired through the smart mobile devices equipped with positioning technology, such as mobile phones, portable computers, and cars, and the obtained location data is uploaded to the database. Then, the location data is transferred to the LBS servers for further intelligent data processing, which allows users to get convenient services from the LBS providers, such as in the aspect of traffic, vehicle positioning, and prediction that can enable users to get a faster and more convenient path; in terms of travel, location positioning and prediction can help users obtain nearby scenic spots and accommodations with better evaluations. The intelligent data processing of LBS servers mainly includes two parts: location prediction and location protection. The attackers can obtain the user’s personal data by attacking the user’s smart terminals, LBS servers, or location service providers, which will result in the users’ privacy being breached.Figure 2
Threat model.


## 2.1. Definitions

Definition 1. (Markov model) [8, 9].
LetE be the discrete state space of random sequence Xn,n=0,1,2,⋯. If for any m nonnegative integers n1,n2,⋯,nm0≤n1<n2<⋯<nm and any natural number k, and any i1,i2,⋯,im, j∈E satisfies the following conditions:
(1)PXnm+k∣Xn1,Xn2,⋯,Xnm=PXnm+k∣Xnm.
Then,Xn,n=0,1,2,⋯ is called the one-order Markov model. This equation shows that the state of the next moment only depends on the present moment and has nothing to do with the past moment. This property is the Markov model with no aftereffect.
Then-order Markov model means that the state of the next moment is not only related to the present moment but also related to the past moment; so, the prediction is more comprehensive and effective.Definition 2. (Neighboring dataset).
Let the data setD and D′ have the same attribute structure, and the symmetric difference between the D and D′ is recorded as D∆D′,D∆D′ represents the number of symmetry differences. If D∆D′=1, then D and D′D′ are called neighboring dataset (also known as brothers data sets).Definition 3. (Differential privacy) [10, 11].
There is a random algorithmM and all possible outputs of M are SM. For any two neighboring datasets D and D′, if algorithm M satisfies the following conditions:
(2)PrMD∈SM≤eε×PrMD′∈SM,
then algorithmM provides ε-differential privacy protection, where parameter ε is called privacy protection budget. The larger the ε is, the higher the data availability is, and the lower the degree of privacy protection is; on the contrary, the lower the data availability is, the higher the degree of privacy protection is.Definition 4. (Sensitivity).
Letd be a positive integer, D is a a set of data sets, and f:D→Rd is a function. The function sensitivity represented by ∆f has the following definition: ∆f=maxfD−fD′1,where .1 is the Manhattan distance.Definition 5. (Laplace mechanism) [12, 13].
Given datasetD, there is a function f:D⟶Rd, the sensitivity is ∆f, and then the random algorithm MD=fD+Y provides ε-differential privacy protection, where Y~Lap∆f/ε is the random noise and obeys the Laplace distribution with the scale parameter ∆f/ε.


## 2.2. Transition Probability

In this paper, then-order Markov model is used to predict the location. The basic method of Markov prediction is to use the transition probability matrix between states to predict the occurrence and development probability of events.The transition probability is derived by using the one-order Markov model [14, 15].
(3)P=Nij∑j=1nNij,where Nij is the number of times that location i turns to location j, and P is called one-step transition probability.The recurrence relation can be obtained by C-K equation.(4)Pn=PPn−1=Pn−1P,(5)Pn=Pn,where Pn is called the n-step transition probability matrix of the Markov model.


## 2.3. System Structure and Threat Model

The system structure of this paper is shown in Figure1, which is mainly composed of client module, privacy protection module, and location service provider module. The client module acquires the user’s location information mainly through the GPS positioning module and stores the location data in the database. The privacy protection module is composed of prediction module and location protection module. The prediction module predicts users’ location by the Markov model, while the location protection module protects users’ location by differential privacy. Location service providers can respond to users’ query requests, feedback the query results to users, and use the feedback results for data analysis, data sharing and data query, and other services.Figure 1
System structure.In this paper, a differential privacy location protection method based on the Markov model is proposed to solve the problem of users’ location privacy disclosure. The user’s location is acquired through the GPS positioning module and stored in the database. In the prediction module, then-order Markov model is used to predict the user’s location, and the LPAM algorithm is proposed. In the location protection module, differential privacy technology is used to protect location data, and LPADP algorithm is proposed. Location service providers can respond to users’ query requests, feedback the query results to users, and use the feedback results for data analysis, data sharing, and data query and other services.Almost all LBS providers collect users’ personal data, such as identity, location, and interests. Many LBS providers provide different security guarantees, such as Google, Twitter, and Youtube. Once these LBS providers are attacked, users’ privacy information will be leaked. The threat model of this paper is shown in Figure2. The users’ location data is acquired through the smart mobile devices equipped with positioning technology, such as mobile phones, portable computers, and cars, and the obtained location data is uploaded to the database. Then, the location data is transferred to the LBS servers for further intelligent data processing, which allows users to get convenient services from the LBS providers, such as in the aspect of traffic, vehicle positioning, and prediction that can enable users to get a faster and more convenient path; in terms of travel, location positioning and prediction can help users obtain nearby scenic spots and accommodations with better evaluations. The intelligent data processing of LBS servers mainly includes two parts: location prediction and location protection. The attackers can obtain the user’s personal data by attacking the user’s smart terminals, LBS servers, or location service providers, which will result in the users’ privacy being breached.Figure 2
Threat model.


## 3. Differential Privacy Location Protection Method Based on the Markov Model

To solve the problem of users’ location privacy leakage, a differential privacy location protection method based on the Markov model is proposed in this paper. Firstly, the transition probability matrix between states of then-order Markov model is used to predict the location information, and LPAM algorithm is proposed. Secondly, LPT is constructed according to the characteristics of location data and the difficulty of retrieval. Finally, the LPADP algorithm is proposed to protect users’ location information by using differential privacy technology.


### 3.1. Location Prediction Algorithm Based on the Markov Model

Location prediction enriches and expands LBS, which is of great significance to LBS. The location prediction methods can be mainly divided into three categories: the location prediction method based on linear or nonlinear mathematical model [16], the location prediction method based on frequent track pattern mining [17], and the location prediction method based on the Markov model.The location prediction method based on the linear or nonlinear mathematical model is to establish a mathematical model according to the current running speed and time to simulate the trajectory of moving objects, thereby predicting the location. The location prediction method based on frequent trajectory pattern mining is to find the frequent trajectory pattern from the user’s historical trajectory and then match the current query trajectory with the frequent trajectory pattern to predict the location. The location prediction method based on the Markov model uses the transition probability matrix between states to predict the state of the event and its development trend, so as to predict the user’s location.Then-order Markov model is used to predict the user’s next location in this paper. The basic method of Markov prediction is to predict the occurrence and development trend of events by using the transfer probability matrix between states. The Markov model has the advantages of low time complexity and high prediction accuracy, which not only avoids the problem that the user’s moving speed and direction are affected by the road network in the first method but also avoids the problem that the query time is too long in the second method, which affects the prediction efficiency and the redundant noise affects the trajectory prediction accuracy.Location prediction is fundamentally determined by the current location and historical location. Obviously, the historical location that is closer to the current location has the greatest impact on the next location. Therefore, this paper obtains the predicted value of each location based on the Markov model weighting method.(6)Xt=a1St−1P+a2St−2P2+⋯+anSt−nPn.In equation (6), t is the time of the next location, andt−1is the time of the current location. Xt is a 1×n matrix that represents the predicted value of each location. Si,1≤i≤n, is a 1×n matrix, the value of column i is 1, and the rest is 0. P is an n×n probability transition matrix. a1, a2,… ak are weights, representing the influence degree of the 1,2,3,...n locations on the next location decision. Based on the Markov model, this paper proposes a location prediction algorithm. The specific content of the algorithm is as follows:Algorithm 1: Location prediction based on the Markov model (LPAM).
Input: N=Nijn∗n; // degree transition matrixS=Si; // location at time k-1now; // current locationX=Xi1∗n; // estimate each locationa=ai1∗n; // weight arrayOutput: result // output all predicted locations1. FOREACHNi∈N2.sum=cumulateNij∈Ni; //cumulate is an accumulation process3.  FOREACHNij∈Ni4.Pij=Nij/sum;5.M1=P // one step transition probability matrix P is obtained6. FORi=2 to n Do7.Mi=matrixMulMi−1,P; // calculate n-step transition probability matrix8. ENDFOR9. setZero(X); // clear X and calculate the estimate10. FORi=1 to n Do11.Tepmatrix=matrixMulSi,Mi,ai; // multiplication of weight and matrix12.X=matrixAddX,Tepmatrix; // calculate X13. ENDFOR14.result=putX1,X2,⋯,Xn; // output all predicted locations15. RETURN result;Analysis shows that Algorithm1 is a location prediction algorithm based on the Markov model, which contains four modules. First, step 1 to step 5, the one-step transition probability matrix M1 is obtained according to equation (3). The one-step transition probability matrix indicates that the next predicted position is only related to the current position; secondly, step 6 to step 8, the n-step transition probability matrix is obtained according to equation (5). The n-step transition probability matrix indicates that the predicted next position is related to all historical positions and is comprehensive; thirdly, step 9 to step 12, the predicted value of each position is calculated according to equation (6). Because the closer the historical position has the greater influence on the next position, the weight a is set for each historical position; finally, step 14 outputs the predicted probabilities of all positions.


### 3.2. Location Protection Algorithm Based on Differential Privacy

In the location protection module, this paper proposes the LPADP algorithm. The basic principle is as follows: Firstly, LPT is constructed for all locations predicted by the LPAM algorithm; secondly, the two nodes with the largest prediction value on LPT are protected by adding Laplacian noise. The algorithm is as follows:Algorithm 2: Location protection based on Differential privacy (LPADP).
Input: X=Xi1∗n ; // location from Algorithm 2Output: The two locations with the largest prediction probability are protected by adding noise1. Constructing LPT;2. void fun(int∗X, int ∗X1, int ∗X2) // select the two nodes with the largest prediction probability on LPT(X1,X2)3. {4.  inti;5.∗max=X0;6.  for(i=1; i<strlenX; i++)7.  if(∗max<∗X+i) ∗X1=∗X+i; // select the nodes with the highest prediction probability X18.∗X2=X0;9.  for(i=1; i<strlenX; i++)10.  {11.   if(∗X2<∗X+i && ∗X2<∗X1)12.∗X2=∗X+i; // select the next largest value node X213.  }14.result=putX1,X2;//output X1, X215. }16.ε=ε1+ε2; //ε1<ε217.Xi′=Xi+Lapεi // Laplacian noise is added to the two location nodes with the largest prediction valueThe analysis shows that Algorithm2 is a location protection algorithm based on differential privacy, which contains three modules. The main purpose of Algorithm 2 is to add Laplacian noise to the two position nodes with the largest predicted value for protection. Firstly, the first step is to construct LPT for all positions predicted by Algorithm 1, which LPT is constructed according to the location data and the difficulty of retrieval; secondly, the function of the second step to the fifteenth step is to traverse all positions on the LPT to obtain the node with the largest predicted value and the node with the second largest predicted value. There are two loop functions in the second step to the fifteenth step. Among them, the first position node on the LPT is defaulted to the maximum value node, and then the nodes on the LPT are traversed in turn, the function of the first loop is to obtain the node X1 with the largest predicted value (that is, the fourth to seventh steps), and the function of the second loop is to obtain the node X2 with the second largest predicted value (that is, the eighth to thirteenth steps); finally, the sixteenth to seventeenth steps are to protect the two locations X1 and X2. The sixteenth step is to allocate a reasonable privacy budget to the two locations, and the seventeenth step is to add Laplace noise to X1 and X2 according to the privacy budget, so as to protect the two positions.


### 3.3. Algorithm Analysis

#### 3.3.1. Safety Analysis

The basic principle of differential privacy technology is as follows: when the user submits a query request to the data provider, if the user directly publishes the accurate query results, it may lead to privacy leakage, because the attacker may use the query result to deduct private information. In order to avoid this problem, the differential privacy technology requires a middleware to be extracted from the database, and a specially designed random algorithm is used to inject an appropriate amount of noise into the middleware to obtain a noisy middleware; then, a noisy query result is derived from the noisy middleware and returned to the user. In this way, even if the attacker can deduce the noisy middleware from the noisy result, it is impossible for him to infer the noiseless middleware accurately, let alone infer the original database, so as to achieve the purpose of protecting the user’s privacy.This paper uses differential privacy technology to protect the user’s location privacy. The main reason is that differential privacy technology has three major advantages: (1) differential privacy strictly defines the background knowledge of the attacker: except for a certain record, the attacker knows all the information in the original data. Such an attacker is almost the most powerful. In this case, differential privacy can still effectively protect private information; (2) differential privacy has a rigorous statistical model, which greatly facilitates the use of mathematical tools and quantitative analysis and verification; and (3) differential privacy does not require special attack assumptions, does not care about the background knowledge of the attacker, and quantitatively analyzes the risk of privacy leakage.The main implementation mechanism of differential privacy technology is to add random noise to input or output to protect the privacy of users’, such as Laplace mechanism, Gaussian mechanism, and Exponential mechanism. In this paper, Laplacian mechanism is used to protect the user’s location by adding Laplacian noise.Laplacian noise is essentially a group of random values satisfying the Laplacian distribution, and the basic principle is to add noise that obeys Lap (b) to the original data and statistical results, so that the query results after adding the noise meet the differential privacy constraint effect. Laplacian noise is added in the LPADP algorithm, which conforms to ε-differential privacy. The proof process is as follows:It can be known from the probability density function of the laplace mechanism:(7)PxzPyz=∏i=1ke−εfxi−zi/∆fe−εfyi−zi/∆f=∏i=1keεfyi−zi−fxi−zi∆f≤∏i=1keεfxi−fyi∆f≤eεfx−fy1∆f=eϵ.According to the definition of differential privacy, the LPADP algorithm proposed in this paper satisfiesε-differential privacy.


#### 3.3.2. Complexity Analysis

Assuming that the location data table containsn pieces of records data. The privacy protection module in Figure 1 mainly contains two modules: prediction module and location protection module. So, the complexity of the algorithm in this paper mainly includes two aspects: the time complexity of the LPAM algorithm in the prediction module and the LPADP algorithm in the location protection module. The LPAM algorithm mainly uses the n-order Markov model to predict the position.The realization of the LPAM algorithm mainly includes three parts: first, calculate the one-step transition probability matrix according to formula (3), and its time complexity is On2, reflected in the first to fifth steps of Algorithm 1; secondly, calculate the n-step transition probability matrix according to formula (5), and its time complexity is On, reflected in the sixth to eighth steps of Algorithm 1; finally, calculate and output the predicted value of each position according to formula (6), and its time complexity is On, reflected in the tenth to fourteenth steps of Algorithm 1.The LPADP algorithm mainly allocates a reasonable privacy budget to the two locations with the larger predicted value on the LPT and then adds Laplacian noise to protect the location privacy. The realization of the LPADP algorithm mainly includes three parts: first, construct LPT for all positions predicted by Algorithm1, and its time complexity is On, reflected in the first step of Algorithm 2; secondly, traverse all the position nodes on the LPT and then select the two nodes with the largest predicted value, and the time complexity is On, reflected in the second to the fifteenth steps of Algorithm 2; finally, a reasonable privacy budget is allocated to the two nodes with the largest predicted value, Laplacian noise is added for protection, and the time complexity is O (1), reflected in the sixteenth to seventeenth steps of Algorithm 2. In general, the time complexity required in this article is
(8)On2+On+On+On+On+O1≈On2.


## 3.1. Location Prediction Algorithm Based on the Markov Model

Location prediction enriches and expands LBS, which is of great significance to LBS. The location prediction methods can be mainly divided into three categories: the location prediction method based on linear or nonlinear mathematical model [16], the location prediction method based on frequent track pattern mining [17], and the location prediction method based on the Markov model.The location prediction method based on the linear or nonlinear mathematical model is to establish a mathematical model according to the current running speed and time to simulate the trajectory of moving objects, thereby predicting the location. The location prediction method based on frequent trajectory pattern mining is to find the frequent trajectory pattern from the user’s historical trajectory and then match the current query trajectory with the frequent trajectory pattern to predict the location. The location prediction method based on the Markov model uses the transition probability matrix between states to predict the state of the event and its development trend, so as to predict the user’s location.Then-order Markov model is used to predict the user’s next location in this paper. The basic method of Markov prediction is to predict the occurrence and development trend of events by using the transfer probability matrix between states. The Markov model has the advantages of low time complexity and high prediction accuracy, which not only avoids the problem that the user’s moving speed and direction are affected by the road network in the first method but also avoids the problem that the query time is too long in the second method, which affects the prediction efficiency and the redundant noise affects the trajectory prediction accuracy.Location prediction is fundamentally determined by the current location and historical location. Obviously, the historical location that is closer to the current location has the greatest impact on the next location. Therefore, this paper obtains the predicted value of each location based on the Markov model weighting method.(6)Xt=a1St−1P+a2St−2P2+⋯+anSt−nPn.In equation (6), t is the time of the next location, andt−1is the time of the current location. Xt is a 1×n matrix that represents the predicted value of each location. Si,1≤i≤n, is a 1×n matrix, the value of column i is 1, and the rest is 0. P is an n×n probability transition matrix. a1, a2,… ak are weights, representing the influence degree of the 1,2,3,...n locations on the next location decision. Based on the Markov model, this paper proposes a location prediction algorithm. The specific content of the algorithm is as follows:Algorithm 1: Location prediction based on the Markov model (LPAM).
Input: N=Nijn∗n; // degree transition matrixS=Si; // location at time k-1now; // current locationX=Xi1∗n; // estimate each locationa=ai1∗n; // weight arrayOutput: result // output all predicted locations1. FOREACHNi∈N2.sum=cumulateNij∈Ni; //cumulate is an accumulation process3.  FOREACHNij∈Ni4.Pij=Nij/sum;5.M1=P // one step transition probability matrix P is obtained6. FORi=2 to n Do7.Mi=matrixMulMi−1,P; // calculate n-step transition probability matrix8. ENDFOR9. setZero(X); // clear X and calculate the estimate10. FORi=1 to n Do11.Tepmatrix=matrixMulSi,Mi,ai; // multiplication of weight and matrix12.X=matrixAddX,Tepmatrix; // calculate X13. ENDFOR14.result=putX1,X2,⋯,Xn; // output all predicted locations15. RETURN result;Analysis shows that Algorithm1 is a location prediction algorithm based on the Markov model, which contains four modules. First, step 1 to step 5, the one-step transition probability matrix M1 is obtained according to equation (3). The one-step transition probability matrix indicates that the next predicted position is only related to the current position; secondly, step 6 to step 8, the n-step transition probability matrix is obtained according to equation (5). The n-step transition probability matrix indicates that the predicted next position is related to all historical positions and is comprehensive; thirdly, step 9 to step 12, the predicted value of each position is calculated according to equation (6). Because the closer the historical position has the greater influence on the next position, the weight a is set for each historical position; finally, step 14 outputs the predicted probabilities of all positions.


## 3.2. Location Protection Algorithm Based on Differential Privacy

In the location protection module, this paper proposes the LPADP algorithm. The basic principle is as follows: Firstly, LPT is constructed for all locations predicted by the LPAM algorithm; secondly, the two nodes with the largest prediction value on LPT are protected by adding Laplacian noise. The algorithm is as follows:Algorithm 2: Location protection based on Differential privacy (LPADP).
Input: X=Xi1∗n ; // location from Algorithm 2Output: The two locations with the largest prediction probability are protected by adding noise1. Constructing LPT;2. void fun(int∗X, int ∗X1, int ∗X2) // select the two nodes with the largest prediction probability on LPT(X1,X2)3. {4.  inti;5.∗max=X0;6.  for(i=1; i<strlenX; i++)7.  if(∗max<∗X+i) ∗X1=∗X+i; // select the nodes with the highest prediction probability X18.∗X2=X0;9.  for(i=1; i<strlenX; i++)10.  {11.   if(∗X2<∗X+i && ∗X2<∗X1)12.∗X2=∗X+i; // select the next largest value node X213.  }14.result=putX1,X2;//output X1, X215. }16.ε=ε1+ε2; //ε1<ε217.Xi′=Xi+Lapεi // Laplacian noise is added to the two location nodes with the largest prediction valueThe analysis shows that Algorithm2 is a location protection algorithm based on differential privacy, which contains three modules. The main purpose of Algorithm 2 is to add Laplacian noise to the two position nodes with the largest predicted value for protection. Firstly, the first step is to construct LPT for all positions predicted by Algorithm 1, which LPT is constructed according to the location data and the difficulty of retrieval; secondly, the function of the second step to the fifteenth step is to traverse all positions on the LPT to obtain the node with the largest predicted value and the node with the second largest predicted value. There are two loop functions in the second step to the fifteenth step. Among them, the first position node on the LPT is defaulted to the maximum value node, and then the nodes on the LPT are traversed in turn, the function of the first loop is to obtain the node X1 with the largest predicted value (that is, the fourth to seventh steps), and the function of the second loop is to obtain the node X2 with the second largest predicted value (that is, the eighth to thirteenth steps); finally, the sixteenth to seventeenth steps are to protect the two locations X1 and X2. The sixteenth step is to allocate a reasonable privacy budget to the two locations, and the seventeenth step is to add Laplace noise to X1 and X2 according to the privacy budget, so as to protect the two positions.


## 3.3. Algorithm Analysis

### 3.3.1. Safety Analysis

The basic principle of differential privacy technology is as follows: when the user submits a query request to the data provider, if the user directly publishes the accurate query results, it may lead to privacy leakage, because the attacker may use the query result to deduct private information. In order to avoid this problem, the differential privacy technology requires a middleware to be extracted from the database, and a specially designed random algorithm is used to inject an appropriate amount of noise into the middleware to obtain a noisy middleware; then, a noisy query result is derived from the noisy middleware and returned to the user. In this way, even if the attacker can deduce the noisy middleware from the noisy result, it is impossible for him to infer the noiseless middleware accurately, let alone infer the original database, so as to achieve the purpose of protecting the user’s privacy.This paper uses differential privacy technology to protect the user’s location privacy. The main reason is that differential privacy technology has three major advantages: (1) differential privacy strictly defines the background knowledge of the attacker: except for a certain record, the attacker knows all the information in the original data. Such an attacker is almost the most powerful. In this case, differential privacy can still effectively protect private information; (2) differential privacy has a rigorous statistical model, which greatly facilitates the use of mathematical tools and quantitative analysis and verification; and (3) differential privacy does not require special attack assumptions, does not care about the background knowledge of the attacker, and quantitatively analyzes the risk of privacy leakage.The main implementation mechanism of differential privacy technology is to add random noise to input or output to protect the privacy of users’, such as Laplace mechanism, Gaussian mechanism, and Exponential mechanism. In this paper, Laplacian mechanism is used to protect the user’s location by adding Laplacian noise.Laplacian noise is essentially a group of random values satisfying the Laplacian distribution, and the basic principle is to add noise that obeys Lap (b) to the original data and statistical results, so that the query results after adding the noise meet the differential privacy constraint effect. Laplacian noise is added in the LPADP algorithm, which conforms to ε-differential privacy. The proof process is as follows:It can be known from the probability density function of the laplace mechanism:(7)PxzPyz=∏i=1ke−εfxi−zi/∆fe−εfyi−zi/∆f=∏i=1keεfyi−zi−fxi−zi∆f≤∏i=1keεfxi−fyi∆f≤eεfx−fy1∆f=eϵ.According to the definition of differential privacy, the LPADP algorithm proposed in this paper satisfiesε-differential privacy.


### 3.3.2. Complexity Analysis

Assuming that the location data table containsn pieces of records data. The privacy protection module in Figure 1 mainly contains two modules: prediction module and location protection module. So, the complexity of the algorithm in this paper mainly includes two aspects: the time complexity of the LPAM algorithm in the prediction module and the LPADP algorithm in the location protection module. The LPAM algorithm mainly uses the n-order Markov model to predict the position.The realization of the LPAM algorithm mainly includes three parts: first, calculate the one-step transition probability matrix according to formula (3), and its time complexity is On2, reflected in the first to fifth steps of Algorithm 1; secondly, calculate the n-step transition probability matrix according to formula (5), and its time complexity is On, reflected in the sixth to eighth steps of Algorithm 1; finally, calculate and output the predicted value of each position according to formula (6), and its time complexity is On, reflected in the tenth to fourteenth steps of Algorithm 1.The LPADP algorithm mainly allocates a reasonable privacy budget to the two locations with the larger predicted value on the LPT and then adds Laplacian noise to protect the location privacy. The realization of the LPADP algorithm mainly includes three parts: first, construct LPT for all positions predicted by Algorithm1, and its time complexity is On, reflected in the first step of Algorithm 2; secondly, traverse all the position nodes on the LPT and then select the two nodes with the largest predicted value, and the time complexity is On, reflected in the second to the fifteenth steps of Algorithm 2; finally, a reasonable privacy budget is allocated to the two nodes with the largest predicted value, Laplacian noise is added for protection, and the time complexity is O (1), reflected in the sixteenth to seventeenth steps of Algorithm 2. In general, the time complexity required in this article is
(8)On2+On+On+On+On+O1≈On2.


## 3.3.1. Safety Analysis

The basic principle of differential privacy technology is as follows: when the user submits a query request to the data provider, if the user directly publishes the accurate query results, it may lead to privacy leakage, because the attacker may use the query result to deduct private information. In order to avoid this problem, the differential privacy technology requires a middleware to be extracted from the database, and a specially designed random algorithm is used to inject an appropriate amount of noise into the middleware to obtain a noisy middleware; then, a noisy query result is derived from the noisy middleware and returned to the user. In this way, even if the attacker can deduce the noisy middleware from the noisy result, it is impossible for him to infer the noiseless middleware accurately, let alone infer the original database, so as to achieve the purpose of protecting the user’s privacy.This paper uses differential privacy technology to protect the user’s location privacy. The main reason is that differential privacy technology has three major advantages: (1) differential privacy strictly defines the background knowledge of the attacker: except for a certain record, the attacker knows all the information in the original data. Such an attacker is almost the most powerful. In this case, differential privacy can still effectively protect private information; (2) differential privacy has a rigorous statistical model, which greatly facilitates the use of mathematical tools and quantitative analysis and verification; and (3) differential privacy does not require special attack assumptions, does not care about the background knowledge of the attacker, and quantitatively analyzes the risk of privacy leakage.The main implementation mechanism of differential privacy technology is to add random noise to input or output to protect the privacy of users’, such as Laplace mechanism, Gaussian mechanism, and Exponential mechanism. In this paper, Laplacian mechanism is used to protect the user’s location by adding Laplacian noise.Laplacian noise is essentially a group of random values satisfying the Laplacian distribution, and the basic principle is to add noise that obeys Lap (b) to the original data and statistical results, so that the query results after adding the noise meet the differential privacy constraint effect. Laplacian noise is added in the LPADP algorithm, which conforms to ε-differential privacy. The proof process is as follows:It can be known from the probability density function of the laplace mechanism:(7)PxzPyz=∏i=1ke−εfxi−zi/∆fe−εfyi−zi/∆f=∏i=1keεfyi−zi−fxi−zi∆f≤∏i=1keεfxi−fyi∆f≤eεfx−fy1∆f=eϵ.According to the definition of differential privacy, the LPADP algorithm proposed in this paper satisfiesε-differential privacy.


## 3.3.2. Complexity Analysis

Assuming that the location data table containsn pieces of records data. The privacy protection module in Figure 1 mainly contains two modules: prediction module and location protection module. So, the complexity of the algorithm in this paper mainly includes two aspects: the time complexity of the LPAM algorithm in the prediction module and the LPADP algorithm in the location protection module. The LPAM algorithm mainly uses the n-order Markov model to predict the position.The realization of the LPAM algorithm mainly includes three parts: first, calculate the one-step transition probability matrix according to formula (3), and its time complexity is On2, reflected in the first to fifth steps of Algorithm 1; secondly, calculate the n-step transition probability matrix according to formula (5), and its time complexity is On, reflected in the sixth to eighth steps of Algorithm 1; finally, calculate and output the predicted value of each position according to formula (6), and its time complexity is On, reflected in the tenth to fourteenth steps of Algorithm 1.The LPADP algorithm mainly allocates a reasonable privacy budget to the two locations with the larger predicted value on the LPT and then adds Laplacian noise to protect the location privacy. The realization of the LPADP algorithm mainly includes three parts: first, construct LPT for all positions predicted by Algorithm1, and its time complexity is On, reflected in the first step of Algorithm 2; secondly, traverse all the position nodes on the LPT and then select the two nodes with the largest predicted value, and the time complexity is On, reflected in the second to the fifteenth steps of Algorithm 2; finally, a reasonable privacy budget is allocated to the two nodes with the largest predicted value, Laplacian noise is added for protection, and the time complexity is O (1), reflected in the sixteenth to seventeenth steps of Algorithm 2. In general, the time complexity required in this article is
(8)On2+On+On+On+On+O1≈On2.


## 4. Experimental Results and Analysis

### 4.1. Environment Configuration

In order to test the performance of the location privacy protection method proposed in this paper, the algorithm has been fully experimented in terms of data availability, privacy protection degree, and algorithm running time. The experiment is implemented using Python, and the data sets are Gowalla data set and Geolife data set [18, 19]. The experimental environment of this article is PyCharm. The hardware environment is 2.60GHz i7 CPU, 8.00RAM, Win10 system 64-bit.


### 4.2. Data Availability Analysis

For the same query functionQ, the similarity of the output query results before and after the noise is added to the data that reflects the influence of the privacy protection algorithm on the availability of the data. Let GQ be the query result of the data before adding noise, and G′Q be the query result of the data after adding noise, and then the degree of approximation SQ can be defined as the first-order normal form distance between the two output results SQ=GQ−G′Q1.For continuous queryQi∈Q1,Q2,⋯,Qk, the availability of data published by location services is defined as
(9)E=1Qi∑SQieε/2.Comparing the method proposed in this paper with TDPS_LP_Signal and TDPS_EP [20] in terms of data availability, the results are shown in Figure 3. The X-axis represents the value of ε, and the Y-axis represents the data availability. The E value of the three algorithms will decrease with the increase of ε, because the larger the ε, the smaller the noise addition and the better the data availability. When ε>0.015, the data availability of the method proposed in this paper tends to be stable. Therefore, the method proposed in this paper has better data availability compared with TDPS_LP_Signal and TDPS_EP. The data availability of the TDPS_LP_Signal algorithm is between the algorithm proposed in this paper and TDPS_EP, and the data availability of TDPS_EP is relatively poor.Figure 3
The effect ofε on data availability.
(a)
Gowalla(b)
GeolifeComparing the Markov model with the trajectory mining model and linear or nonlinear mathematical model in data availability, the results are shown in Figure4. The X-axis represents the number of historical locations, and the Y-axis represents data availability. The E value of the three algorithms will decrease with the increase in the number of historical locations, because the increase in the number of historical locations, the more accurate the prediction and the better the data availability. The n-order Markov model is more accurate and comprehensive in location prediction; so, it has better data availability. The trajectory mining model is between the Markov model and linear or nonlinear mathematical model in terms of data availability, and the data availability of the linear or nonlinear mathematical model is poor.Figure 4
The impact of the number of historical locations on data availability.
(a)
Gowalla(b)
Geolife


### 4.3. Analysis of the Degree of Privacy Protection

Comparing the method proposed in this paper with TDPS_LP_Signal and TDPS_EP in terms of privacy protection degree, the result is shown in Figure5. The X-axis represents the value of ε, and the Y-axis represents the degree of privacy protection. The degree of privacy protection of the three algorithms will decrease with the increase of ε, because the larger the ε, the smaller the noise addition and the worse the degree of privacy protection. The algorithm proposed in this paper uses differential privacy technology to protect the location and has better security. The degree of privacy protection of the TDPS_LP_Signal algorithm is between the algorithm proposed in this paper and the TDPS_EP algorithm, and the degree of privacy protection of the TDPS_EP algorithm is relatively low.Figure 5
The effect ofε on the degree of privacy protection.
(a)
Gowalla(b)
GeolifeComparing the Markov model with the trajectory mining model and linear or nonlinear mathematical model in the degree of privacy protection, the result is shown in Figure6. The X-axis represents the number of historical locations, and the Y-axis represents the degree of privacy protection. The degree of privacy protection of the three algorithms will increase with the increase in the number of historical locations, because the increase in the number of historical locations, the more accurate the prediction and the better the degree of privacy protection. The n-order Markov model is more accurate and comprehensive in location prediction and has better security. The privacy protection degree of the trajectory mining mode algorithm is between the Markov model and the linear and nonlinear mathematical model. The privacy protection degree of the linear or nonlinear mathematical model algorithm is relatively low.Figure 6
The influence of the number of historical locations on the degree of privacy protection.
(a)
Gowalla(b)
Geolife


### 4.4. Analysis of Algorithm Running Time

Comparing the method proposed in this paper with TDPS_LP_Signal and TDPS_EP in terms of algorithm running time, the result is shown in Figure7. The X-axis represents the value of ε, and the Y-axis represents the running time of the algorithm. The running time of the three algorithms will decrease with the increase of ε, because the larger the ε, the smaller the noise addition and the shorter the running time. The method proposed in this paper only protects the two locations with the largest predicted value and has less algorithm running time. The running time of the TDPS_LP_Signal algorithm is between the algorithm proposed in this paper and the TDPS_EP algorithm, and the TDPS_EP algorithm requires relatively more time.Figure 7
The effect ofε on the running time of the algorithm.
(a)
Gowalla(b)
GeolifeComparing the Markov model with the trajectory mining model and linear or nonlinear mathematical model in terms of algorithm running time, the results are shown in Figure8. The X-axis represents the number of historical locations, and the Y-axis represents the running time of the algorithm. The running time of the three algorithms will increase as the number of historical locations increases, because the number of historical locations increases, the prediction time increases, thereby increasing the running time. Because the Markov model has the advantage of low time complexity, it has less algorithm running time. The running time of the trajectory mining pattern algorithm is between the Markov model and linear and nonlinear mathematical model, and linear and nonlinear mathematical model algorithm takes more time.Figure 8
The effect of the number of historical locations on the running time of the algorithm.
(a)
Gowalla(b)
Geolife


## 4.1. Environment Configuration

In order to test the performance of the location privacy protection method proposed in this paper, the algorithm has been fully experimented in terms of data availability, privacy protection degree, and algorithm running time. The experiment is implemented using Python, and the data sets are Gowalla data set and Geolife data set [18, 19]. The experimental environment of this article is PyCharm. The hardware environment is 2.60GHz i7 CPU, 8.00RAM, Win10 system 64-bit.


## 4.2. Data Availability Analysis

For the same query functionQ, the similarity of the output query results before and after the noise is added to the data that reflects the influence of the privacy protection algorithm on the availability of the data. Let GQ be the query result of the data before adding noise, and G′Q be the query result of the data after adding noise, and then the degree of approximation SQ can be defined as the first-order normal form distance between the two output results SQ=GQ−G′Q1.For continuous queryQi∈Q1,Q2,⋯,Qk, the availability of data published by location services is defined as
(9)E=1Qi∑SQieε/2.Comparing the method proposed in this paper with TDPS_LP_Signal and TDPS_EP [20] in terms of data availability, the results are shown in Figure 3. The X-axis represents the value of ε, and the Y-axis represents the data availability. The E value of the three algorithms will decrease with the increase of ε, because the larger the ε, the smaller the noise addition and the better the data availability. When ε>0.015, the data availability of the method proposed in this paper tends to be stable. Therefore, the method proposed in this paper has better data availability compared with TDPS_LP_Signal and TDPS_EP. The data availability of the TDPS_LP_Signal algorithm is between the algorithm proposed in this paper and TDPS_EP, and the data availability of TDPS_EP is relatively poor.Figure 3
The effect ofε on data availability.
(a)
Gowalla(b)
GeolifeComparing the Markov model with the trajectory mining model and linear or nonlinear mathematical model in data availability, the results are shown in Figure4. The X-axis represents the number of historical locations, and the Y-axis represents data availability. The E value of the three algorithms will decrease with the increase in the number of historical locations, because the increase in the number of historical locations, the more accurate the prediction and the better the data availability. The n-order Markov model is more accurate and comprehensive in location prediction; so, it has better data availability. The trajectory mining model is between the Markov model and linear or nonlinear mathematical model in terms of data availability, and the data availability of the linear or nonlinear mathematical model is poor.Figure 4
The impact of the number of historical locations on data availability.
(a)
Gowalla(b)
Geolife


## 4.3. Analysis of the Degree of Privacy Protection

Comparing the method proposed in this paper with TDPS_LP_Signal and TDPS_EP in terms of privacy protection degree, the result is shown in Figure5. The X-axis represents the value of ε, and the Y-axis represents the degree of privacy protection. The degree of privacy protection of the three algorithms will decrease with the increase of ε, because the larger the ε, the smaller the noise addition and the worse the degree of privacy protection. The algorithm proposed in this paper uses differential privacy technology to protect the location and has better security. The degree of privacy protection of the TDPS_LP_Signal algorithm is between the algorithm proposed in this paper and the TDPS_EP algorithm, and the degree of privacy protection of the TDPS_EP algorithm is relatively low.Figure 5
The effect ofε on the degree of privacy protection.
(a)
Gowalla(b)
GeolifeComparing the Markov model with the trajectory mining model and linear or nonlinear mathematical model in the degree of privacy protection, the result is shown in Figure6. The X-axis represents the number of historical locations, and the Y-axis represents the degree of privacy protection. The degree of privacy protection of the three algorithms will increase with the increase in the number of historical locations, because the increase in the number of historical locations, the more accurate the prediction and the better the degree of privacy protection. The n-order Markov model is more accurate and comprehensive in location prediction and has better security. The privacy protection degree of the trajectory mining mode algorithm is between the Markov model and the linear and nonlinear mathematical model. The privacy protection degree of the linear or nonlinear mathematical model algorithm is relatively low.Figure 6
The influence of the number of historical locations on the degree of privacy protection.
(a)
Gowalla(b)
Geolife


## 4.4. Analysis of Algorithm Running Time

Comparing the method proposed in this paper with TDPS_LP_Signal and TDPS_EP in terms of algorithm running time, the result is shown in Figure7. The X-axis represents the value of ε, and the Y-axis represents the running time of the algorithm. The running time of the three algorithms will decrease with the increase of ε, because the larger the ε, the smaller the noise addition and the shorter the running time. The method proposed in this paper only protects the two locations with the largest predicted value and has less algorithm running time. The running time of the TDPS_LP_Signal algorithm is between the algorithm proposed in this paper and the TDPS_EP algorithm, and the TDPS_EP algorithm requires relatively more time.Figure 7
The effect ofε on the running time of the algorithm.
(a)
Gowalla(b)
GeolifeComparing the Markov model with the trajectory mining model and linear or nonlinear mathematical model in terms of algorithm running time, the results are shown in Figure8. The X-axis represents the number of historical locations, and the Y-axis represents the running time of the algorithm. The running time of the three algorithms will increase as the number of historical locations increases, because the number of historical locations increases, the prediction time increases, thereby increasing the running time. Because the Markov model has the advantage of low time complexity, it has less algorithm running time. The running time of the trajectory mining pattern algorithm is between the Markov model and linear and nonlinear mathematical model, and linear and nonlinear mathematical model algorithm takes more time.Figure 8
The effect of the number of historical locations on the running time of the algorithm.
(a)
Gowalla(b)
Geolife


## 5. Related Work

As LBS has privacy that becomes the focus of research, more and more scholars have paid close attention to LBS privacy protection methods. At present, the main methods of location privacy protection include cryptography,k-anonymity, and differential privacy.Cryptography is a privacy protection method based on encryption and signature, which realizes privacy protection by encrypting users’ information [21–23]. Liang et al. proposed a privacy protection method based on POI query inthe road network environment by combining Hilbert curve with anonymous technology, which effectively avoided inference attack against location information [24].While it is known that unconditionally secure position-based cryptography is impossible both in the classical and the quantum setting, it has been shown that some quantum protocols for position verification are secure against attackers which share a quantum state of bounded dimension. Bluhm et al. considered the security of the qubit routing protocol. The protocol has the advantage that an honest prover only has to manipulate a single qubit and a classical string of length 2n and shows that the protocol is secure if each of the attackers holds at most n/2−3 qubits [25]. However, cryptography is difficult to implement because of huge computing and communication costs.k-anonymity requires that the same quasiidentifier must have at least k records, and each individual record cannot be distinguished from other k-1 individuals for sensitive attributes; so, the attackers cannot link the records through the quasiidentifier [26–28]. In reference [29], the user’s real location was replaced by the anonymous users’ area; so, the attacker could not identify the user’s real location. In reference [30], the users used historical information to process real information anonymously, so as to protect users’ location privacy. In reference [31], the users cooperated with each other, shared part of the location information, and formed an anonymous space to achieve the effect of k-anonymity. Mingyan et al. [32] proposed a location anonymity algorithm based on the mobile P2P structure, which avoided the risk of information leakage caused by single point failure. Xingyou et al. [33] selected the location anonymous set in the grid that published the request according to the real service request data and sent the location anonymous set to the server instead of the user’s real location. Although k-anonymity technology can prevent the disclosure of identity, it cannot resist homogeneous attacks and background knowledge attacks.Differential privacy can protect privacy effectively and has a rigorous statistical model [34–36]. Zhiqiang et al. [37] proposed a location data acquisition scheme based on local differential privacy, which used the random response mechanism to obtain location data, and the data collector used direct statistics and expectation maximum method to analyze the location data to ensure that the normal analysis can be carried out. In order to solve the problem of privacy leakage in crowdsourcing, Zheng et al. [38] proposed a crowdsourcing location data acquisition scheme that satisfied the localized differential privacy. In this scheme, the road network space was divided into Voronoi diagram, and a method of spatial range query on disturbed data set was designed. Fuzzy C-means clustering algorithm is one of the typical clustering algorithms in data mining applications. However, due to the sensitive information in the dataset, there is a risk of user privacy being leaked during the clustering process. Zhang et al. [39] aimed at the problem that the algorithm accuracy is reduced by randomly initializing the membership matrix of fuzzy C-means; in this paper, the maximum distance method is firstly used to determine the initial center point. Then, the Gaussian value of the cluster center point is used to calculate the privacy budget allocation ratio. Additionally, Laplace noise is added to complete differential privacy protection. Wei et al. [40] proposed a differential privacy-based location protection (DPLP) scheme, and DPLP splits the exact locations of both workers and tasks into noisy multilevel grids by using adaptive three-level grid decomposition (ATGD) algorithm and DP-based adaptive complete pyramid grid (DPACPG) algorithm, respectively, thereby considering the grid granularity and location privacy. Furthermore, DPLP adopts an optimal greedy algorithm to calculate a geocast region around the task grid, which achieves the trade-off between acceptance rate and system overhead, which protects the location privacy of both workers and tasks, and achieves task allocation with high data utility.In view of the problem of location privacy protection, this paper uses differential privacy technology to protect the location privacy of users’. Differential privacy can not only resist the background knowledge attack and homogeneous attacks but also can effectively protect the user’s privacy when adding or deleting a record without affecting the query result.


## 6. Conclusions

The continuous use of LBS will expose the user’s location information, which results in the disclosure of user’s privacy. In order to solve issues of user privacy disclosure in LBS, a differential privacy location protection method based on the Markov model is proposed in this paper. Experiments show that this method can protect location privacy effectively and has high data availability and low time complexity. In the future research, the research mainly focuses on two aspects. On the one hand, the location prediction of the Markov model does not consider the situation of new users; so, the future research direction is to predict the location of new users and protect the predicted location information. On the other hand, the Markov model predicts and protects the position, which realizes the direct protection of the position, but ignores the spatiotemporal correlation between the predicted positions. Therefore, the future research direction is to protect the position indirectly according to the spatiotemporal correlation between the predicted positions.



---

*Source: 4696455-2021-07-01.xml*