# Trajectory Privacy Preserving for Continuous LBSs in VANET

Authors: Zhihong Li; Xiaoshuang Xing; Jin Qian; Hui Li; Gaofei Sun
Journal: Wireless Communications and Mobile Computing
 (2022)

---

## Abstract

Location-based services (LBSs) support various applications in vehicular ad hoc network (VANET). However, location/trajectory privacy becomes a serious concern for LBSs. Existing location/trajectory privacy-preserving schemes rarely take the attack model of adversaries into consideration, and the cost for achieving privacy has not been carefully studied. To deal with these problems, this study proposes a collaborative trajectory obfuscation scheme based on analyzing the attack model and designs a privacy-preserving efficiency metric that balances the achieved privacy and the cost. Through simulation, the effects of the density of vehicles using the same LBSs on the performance of our design and an existing scheme are investigated. The performance comparison results validate the effectiveness and efficiency of our scheme.


---

## Body

## 1. Introduction

Vehicular ad hoc network (VANET) has become an important framework of the intelligent transportation system (ITS) for applications such as navigation, road safety, and entertainment [1]. Location-based service (LBS) usually acts as the foundation that supports these applications. For example, a vehicle that wants to find a nearby supermarket and decide a suitable driving route should submit its identity, location, and service requests to corresponding LBS providers (LBSPs). While providing LBSs, LBSPs collect vehicles’ locations. Once the LBSP is untrustworthy or attacked by malicious adversaries, vehicles’ identities and locations will be disclosed. By analyzing frequently visited locations, private information of vehicle drivers, such as personal preferences, work locations, home addresses, and health conditions, can be revealed [2, 3]. To deal with these threats, location privacy preserving for LBSs has long been considered as an important research topic in VANETs.The basic idea for location privacy preserving is to use pseudonyms instead of real identities when submitting LBS requests to eliminate the link between vehicles’ identities and locations [4]. However, simple pseudonym replacement can only provide a single-point location privacy preserving [5]. When continuous LBSs are used, frequently visited location and/or trajectories of vehicles can still be revealed if locations are submitted to LBSPs periodically with the same pseudonym. To deal with this problem, pseudonym-changing schemes such as silent period [6, 7] and mix zone [8] are proposed, but their performance is unsatisfactory when facing the correlation attacks and their real-time performance is expected to be improved.Location/trajectory obfuscation schemes have been designed to solve the aforementioned problems. In location obfuscation schemes, vehicles change their actual location coordinates within a tolerable error range and submit the changed locations to LBSPs. In this way, location privacy is preserved with the cost of decreased service quality since the LBSs are provided based on changed locations [9]. In trajectory obfuscation schemes, fake LBS requests, whose locations are obtained from collaborators, are submitted together with vehicles’ actual LBS requests. In this way, adversaries will be misled and failed to trace the trajectories when proper collaborators are selected [10]. Trajectory obfuscation schemes preserve privacy without decreasing the service quality. However, most work has not taken the attack model of adversaries into consideration for designing trajectory obfuscation schemes. Intuitively, trajectory privacy can be better preserved if we understand how the attackers trace the trajectories. Besides, the scenario when not all vehicles are using the same LBS has not been carefully studied. When vehicle v selects a vehicle not using the same LBS as the collaborator, the collaborator will not be able to cause significant bifurcation of the trajectory. Consequently, an attacker can still trace the trajectory successfully with high probability. Regarding the performance evaluation, various metrics, such as tracking successful ratio [11], location/trajectory entropy [12], and anonymity set size [13], have been designed to measure the achieved location/trajectory privacy. However, the cost for achieving such privacy-preserving performance has rarely been studied.In this study, we tackle these challenges by making the following contributions:(1)
We propose a novel trajectory privacy-preserving scheme based on understanding the attack model of adversaries. We first analyze how the adversaries predict/trace the vehicles’ trajectories using the Kalman filter. Then, vehicles using LBSs predict their future locations with the Kalman filter and select collaborators based on predicted locations. In this way, collaborators that are most capable of misleading the adversaries can be selected and the trajectory privacy-preserving performance can be ensured.(2)
A privacy-preserving efficiency metric is designed to evaluate the trajectory privacy-preserving performance and the cost for achieving such privacy performance.(3)
Unlike the simulation settings of the existing collaborative solutions, we set the density of vehicles using the same LBSs as a variable to better reproduce the real usage scenario. The effects of the density on our design and an existing scheme are investigated.The rest of the study is organized as follows. Related works are reviewed in Section2. Section 3 describes the considered system model. The attack model of adversaries is analyzed in Section 4, based on which a collaborative trajectory obfuscation scheme is proposed in Section 5. The performance of our design is compared with some exiting schemes in Section 6, and this study is concluded in Section 7.


## 2. Related Work

LBS supports a broad range of applications in VANETs. Locations are submitted to the LBS provider together with vehicle identities, which threaten users’ location privacy and trajectory privacy. To deal with these threats, pseudonym-changing-based schemes and location/trajectory obfuscation-based schemes have been extensively studied [14].In pseudonym-changing-based schemes, vehicles use pseudonyms instead of real identities when submitting LBS requests. In this way, links between locations and identities are broken, and location privacy can be preserved. Moreover, a vehicle changes pseudonyms following designed algorithms. Thus, links among locations of a vehicle at different times are broken and trajectory privacy can be preserved.The silent period is an early proposed pseudonym-changing algorithm [6, 7]. A time period is defined as silent period, within which vehicles do not submit any LBS requests (i.e., keep silent) and after which vehicles submit LBS requests with changed pseudonyms. This method can mislead the attacker when more than one vehicles change their pseudonyms at the end of a silent period. However, due to the silence period, applications with high real-time requirements cannot be satisfied.Mix zone is considered as a promising pseudonym-changing algorithm [8, 15] where mutually cooperative vehicles concurrently change their pseudonyms in mix zones created by themselves. The effectiveness of the mix zone depends on factors such as geometry, vehicle density, and geographic location in the road network. In addition, most mix zone schemes cannot avoid the continuous query correlation attack, thus limiting their performance in continuous LBS applications.Due to the limitations mentioned above, pseudonym changing is usually used together with location/trajectory obfuscation. In location obfuscation, a vehicle changes the actual location coordinates within a tolerable error range. Then, the changed location is submitted to the LBSP. A method called CoPrivacy is proposed in [16], where vehicles form k anonymity groups through collaboration and a vehicle replaces its actual location by the regional density center of the anonymous group it belongs to. Reference [17] explores the minimum amounts of obfuscation and anonymization to block attacks on user’s location privacy using an information-theoretic approach with the Markov chains. However, location obfuscation preserves location privacy with the cost of decreased service quality since LBSP provides service based on the changed locations [9].In 2016, [18] proposed a trajectory obfuscation scheme called mutual obfuscating path (MOP) to preserve privacy without decreasing the service quality. For each vehicle v, it selects a collaborator from vehicles that are currently within its communication range. Vehicles whose trajectories are predicted to converge on v’s trajectory within a predefined time threshold form the candidate collaborator set and within which the vehicle being nearest to v is selected as the collaborator. Then, v will send two LBS requests with two different pseudonyms to the LBSP. The locations of these two requests will be v’s actual location and the collaborator’s predicted location, respectively. From the attacker’s perspective, the trajectories continue to bifurcate over time, which impedes the attacker from successful trajectory tracing. Reference [10] pointed out that there may be nefarious vehicles in the internal cooperation of MOP. To deal with this problem, it proposed a non-collaborative approach. A vehicle independently decides whether to exploit the fake location of the surrounding vehicles based on the proposed algorithm.Despite the real time and guaranteed service quality of these two schemes, there are still open challenges to be solved. First, the attack model has not been investigated in this work. Intuitively, trajectory privacy can be better preserved if we understand how the attackers trace the trajectories. Therefore, in this work, we will design a trajectory obfuscation scheme based on analyzing the attack model. Second, this work does not consider the scenario when not all vehicles are using the same LBS. When vehiclev selects a vehicle not using the same LBS as the collaborator, the collaborator will not be able to cause significant bifurcation of the trajectory. Consequently, an attacker can still trace the trajectory successfully with high probability. Therefore, we will take the scenario when not all vehicles are using the same LBS into consideration and the effects of the density of vehicles using the same LBS on the trajectory obfuscation performance will be investigated.


## 3. System Model

For easier following, we summarize the notations introduced throughout the next three sections in Table1.Table 1
Summary of notations.
SymbolMeaningn,mNumber of vehicles on the road, number of LBSPsvk,VThekth vehicle 1≤k≤n, set of vehicles on the roadpi,PTheith LBSP 1≤i≤m, set of LBSPstjThejth timestamp of vk using pi0≤j≤endIk,I˜kjIdentity ofvk, pseudonym of vk at tjLokj,Lakj,Lockjvk’s longitude at tj, vk’s latitude at tj, vk’s location at tjRkivk’s service request to piTintThe time interval between two continuous LBS requestsviSubset of vehicles using theith LBS 1≤i≤mCISet ofvi’s information collected by pixjState vector formed by the adversary attjxvijInitial state of thevith vehicle that is using pi’s service at tjVoj,VajVelocity in the longitude direction and the latitude direction attjDojDistance between locationsLoj,Laj and Loj−1,Laj in the longitude directionDajDistance between locationsLoj,Laj and Loj−1,Laj in the latitude directionx¯kj,xkjEstimated state ofvk at tjj≠0, vk’s state considered by the adversary at tjukjvk’s acceleration vector at tjA,B,HState transition matrix, input matrix, measurement matrixAokj,Aakjvk’s acceleration in the longitude direction and the latitude direction at tjw,vDisturbance noise, measurement noiseQ,RCovariance ofw, covariance of vEnUnit matrix withn rows and n columnsPj,P¯jError covariance attj, error covariance calculated according to Pj−1 at tjLo¯kj,La¯kjEstimated longitude and latitude ofvk at tjVo¯kj,Va¯kjEstimated velocity in the longitude direction and the latitude direction ofvk at tjG,CDistance threshold, set of vehicles meeting the conditionGpk′,jProbability thatxk′j is considered by the adversary to be vk′’s state at tjZk′jMeasurement value consisting ofLok′j,Lak′jKKalman gainskj,Skjvk’s recorded information regarding coordinate, velocity, and acceleration at tj, set of skjVkjSet ofvk’s neighbors at time tjySerial number of the minimum distance betweenLoc¯kj+1 andvkyCollaborator selected byvkIn the considered system model, there aren vehicles, denoted by V=v1,v2,…,vn on the road, and m LBS providers (LBSPs), denoted by P=p1,p2,…,pm, providing m different LBSs. Each vehicle can access to pi∈P for LBS or do not use LBS depending on its demand. Each vehicle is equipped with an onboard unit (OBU). Through the OBU, a vehicle can obtain real-time information about the surrounding environment and communicate with other vehicles or infrastructures in VANET. When a vehicle wants to use the ith 1≤i≤m LBS, it sends a request to pi via Internet service provider (ISP). ISP is a communication agency between OBU and LBSP via which the LBS requests and responses are sent. The considered LBS model is shown in Figure 1.Figure 1
LBS system model in VANET.In our work, we mainly focus on the continuous LBS scenario, where a vehicle periodically sends the LBS request to LBSP during the service time. A topical continuous LBS is navigation. Assume a vehiclevk uses the ith LBS from time t0 to time tend. The LBS request sent by vk at time t0≤tj≤tend can be denoted by Ik,Lockj,Rki,tj. Here, Ik denotes the identity of vk, Lockj=Lokj,LakjT indicates vk’s location at tj with Lokj and Lakj being the longitude and the latitude, Rki represents vk’s service request to LBSP pi, and tj is the timestamp. Let Tint=tj+1−tj denote the time interval between two continuous LBS requests. Without loss of generality, we let Tint be an unit time in this study. To resist the identity-link attacks, vehicles usually use time-changing pseudonyms instead of real identity for LBS request. Therefore, the LBS request can be revised as I˜kj,Lockj,Rki,tj with I˜kj being the pseudonym of vk at tj.Letvi∈V denote the subset of vehicles using the ith LBS from t0 to tend. By the end of tend, pi collects information regarding the pseudonyms and locations of these vehicles at different time points as CI=I˜k0,Lock0,t0,…,I˜kend,Lockend,tend, vk∈vi. If pi is malicious or it is attacked by malicious adversaries, the possible trajectories of vehicles in vi can be predicted using the Kalman filter or other methods. Thus, the private trajectory information will be disclosed. To tackle this problem and preserve the trajectory privacy, a collaborative obfuscation method will be designed based on the understanding of the adversary’s attack model.


## 4. Adversary Model When the Kalman Filter Is Used for Trajectory Prediction

To effectively protect the trajectory information from being disclosed, we should understand how the adversaries predict the trajectories. Therefore, we will analyze the attack model of adversaries when the Kalman filter is used for trajectory prediction. Based onCI collected at the LBSP pi, the adversary forms a state vector xj=Loj,Laj,Voj,VajT to denote the state of a LBS request with timestamp tj. Here, Loj and Laj denote the longitude and the latitude obtained from the LBS request, and Voj and Vaj denote the velocity in the longitude direction and the latitude direction. Vo0 and Va0 are set to be 0. Voj and Vajj≠0 can be calculated as Voj=1/TintDoj and Vaj=1/TintDaj) with Doj indicating the distance between locations Loj,Laj and Loj−1,Laj in the longitude direction and Daj indicating the distance between locations Loj,Laj and Loj−1,Laj in the latitude direction.Fort0, the adversary will form vi state vectors x1j, x2j,…,xvij to denote the initial states of the vi vehicles that are using pi’s service. For tjj≠0, the adversary may not be able to identify the state of vk∈vi due to pseudonym changing. Let us take an example for better understanding. Let 110011,41.40,2.17,t0,110000,40.40,2.31,t0,110011,42.40,2.17,t1,110000,40.87,2.40,t1,100110,42.98,2.39,t2,001100,41.05,2.37,t2 denote the CI collected by pi from t0 to t2. Two state vectors x10=41.40,2.17,0,0T and x20=40.40,2.31,0,0T will be formed at t0. Since the pseudonyms are not changed from t0 to t1, the adversary easily identifies x11 and x22 from CI as x11=42.40,2.17,Vo11,Va11T and x21=40.87,2.40,Vo21,Va21T. At t3, the pseudonyms of vehicles are changed. The adversary cannot identify directly from CI whether location 42.98,2.39 or location 41.05,2.37 belongs to x13. In this case, the Kalman filter will be applied by the adversary to make a prediction and decide which location belongs to x13.Vehiclevk∈vi is taken as an example, and we will describe how the adversary predicts vk’s trajectory. Let x¯kj denote the state of vk at tjj≠0 estimated using motion model, and it can be given as follows:(1)x¯kj=Axkj−1+Bukj−1+w,where xkj−1 is considered by the adversary to be vk’s state at tj−1 with probability pk,j−1 and pk,0 is set to be 1. The calculation of pk,j−1 will be given later in this section. A is called as the state transition matrix, and B is called as the input matrix. They are defined as follows:(2)A=1010010100100001,B=1201001201T.ukj−1 is called as the acceleration vector and is defined as ukj−1=Aokj−1,Aakj−1T with Aokj−1 and Aakj−1 denoting vk’s acceleration in the longitude direction and the latitude direction at time tj−1. Note that Aok0 and Aak0 are set to be 0. Therefore, Axkj−1+Bukj−1 can be used to estimate the location and velocity of vk at time tj based on the location, velocity, and acceleration at tj−1. Considering the error caused by imprecise estimation, a disturbance noise w is added in (1). Assume that w is a Gaussian white noise, and the covariance Q can be given as follows:(3)Q=qE4.Here,En denotes an unit matrix with n rows and n columns. The error covariance P¯ caused by w can be calculated as follows:(4)P¯j=APj−1AT+Q,where Pj−1 is the error covariance at time tj−1 and P0 is set to be E4.Gettingx¯kj=Lo¯kj,La¯kj,Vo¯kj,Va¯kjT, the adversary will check CI and find a set of vehicles:(5)C=vk′|Disk′<G.Here,Disk′ indicates the distance between locations Lo¯kj,La¯kj and Lok′j,Lak′j, G is a distance threshold set based on the longest distance traveled by the vehicle in one Tint under the speed limit on the road. Here, we set G to a fixed value 15. Then, vehicle vk′ will be considered to be vehicle vk by the adversary at time tj with probability pk′,j, and pk′,j can be calculated as follows:(6)pk′,j=∑vk′′∈C/vk′Disk″∑vk′′∈CDisk′′×pk,j−1C−1.Here,pk,j−1 is the probability that xkj−1 is considered by the adversary to be vk’s state at tj−1. When vehicle vk′ is considered by the adversary to be vehicle vk at time tj, Zk′j=Lok′j,Lak′jT will be taken as vk’s location at time tj. Considering the errors caused by imprecise positioning, the relationship between Zk′j and the actual location Hxk′j can be described as follows:(7)Zk′j=Hxk′j+v.Here,H is a measurement matrix:(8)H=10000100,where v is the measurement noise caused by imprecise positioning. Assume that v in (7) is a Gaussian white noise, and the covariances R can be given as follows:(9)R=rE2,The parameters of the Kalman filter are updated andvk’s state at time tj is predicted using the following formula:(10)K=P¯jHTHP¯jHT+R−1,xkj=x¯kj+KZk′j−Hx¯kj,Pj=E4−KHP¯j,where K is called as the Kalman gain. It can be found from (10) that K decreases with R. That is, smaller R will lead to more trustable estimation using the Kalman filter. Given today’s increasingly precise positioning systems, we assume that there is almost no deviation between Zk′j and xk′j. Thus, r is set to be a small value r=0.05. As for the setting of q, we refer to the conclusion in [5] and q=0.05 is set. It should be noted that xkj obtained using (10) denotes vk’s state at time tj predicted by the adversary when vk′ is considered to be vk. xkj will be substituted into (1) to estimate x¯kj+1 and correspondingly pk,j−1 in (6) will be replaced by pk′,j.


## 5. Collaborative Obfuscation for Trajectory Privacy Preserving

Understanding how the adversary traces the vehicles’ trajectories, we will design a collaborative trajectory obfuscation algorithm in this section.Our main idea is to find collaborators for each vehiclevk, and the collaborators will help vk by sending the same LBS request with their pseudonyms and locations. When proper collaborators are selected, the adversary will mistake the collaborators for vk and thus be misled during trajectory tracing. It should be noted that it is meaningless if a collaborator is driving on the same road with vk and the adversary is successfully misled by the collaborator since vk is still predicted to be on that road and the adversary can still get vk’s trajectory. Therefore, this work only selects collaborators at intersections and vehicles that are most capable of misleading the adversary will be selected as collaborators.While driving, a vehiclevk keeps recording its locations, velocities, and accelerations for the current time and N most recent historical time points. Assume the current time point is tj, and the recorded information can be denoted as Skj=skj,skj−1,…,skj−N with skj=Lokj,Lakj,Vokj,Vakj,Aokj,Aakj. Here, Lo/La, Vo/Va, and Ao/Aa denote the coordinate, velocity, and acceleration in the longitude/latitude direction, subscript k denotes vehicle vk, and superscript j denotes time tj. With the recorded information, vk will predict its location in the future time tj+1, denoted by Loc¯kj+1, using the Kalman filter. The prediction process is given in Algorithm 1.Algorithm 1: Location prediction process of vehicle vk.
Input:Skj=skj,skj−1,…,skj−N, Pj−N=E4Output:Loc¯kj+1(1)
xkj−N=Lokj−N,Lakj−N,Vokj−N,Vakj−NT(2)
forl←j−N to j−1do(3)
ukl=Aokj,AakjT(4)
x¯kl+1=Axkl+Bukl(5)
Zkl+1=Lokl+1,Lakl+1T(6)
P¯l+1=APlAT+Q(7)
K=P¯l+1HTHP¯l+1HT+R−1(8)
xkl+1=x¯l+1+KZl+1−Hx¯l+1(9)
Pl+1=E4−KHP¯l+1(10)
end for(11)
Loc¯kj+1=HAxkj+BukjWhen arriving at an intersection, vehicles predict their future locations attj+1 according to Algorithm 1. Each vehicle adds its predicted location to the beacon message and broadcasts the message to neighbors, which are vehicles within its communication range. In our work, we assume that all vehicles have the same radius of communication range. Therefore, vk is a neighbor of vx if vehicle vx is a neighbor of vk. For vehicle vk, let Vkj=vk1,vk2,…,vkY denote the set of its neighbors at time tj. vk will select vky∈Vkj as the collaborator if:(11)y=argmin1≤y≤YDisLoc¯kj+1,Loc¯kyj+1,and(12)DisLoc¯kj+1,Loc¯kyj+1≤G.Here,G is a distance threshold as described in Section 4. After selecting vky as the collaborator, vk sends to vky a cooperative awareness message containing the LBSP vk is connected to and the kind of LBS request it is using. Then, vky will help vk send fake LBS requests with vky’s pseudonyms and locations to the LBSP. We assume that all vehicles are willing to collaborate since a selfish vehicle who does not collaborate will threaten its own privacy [18]. Therefore, motivation schemes will not be considered in our work.As we have mentioned, the scenario where not all vehicles are using the same LBS should be considered when designing algorithms to preserve trajectory privacy. Under this scenario, if the selected collaboratorvky is not using the same LBS as vk and vky just sends one fake request to the LBSP, it will be easy for the adversary to identify the fake request. To deal with this problem, the collaborator should keep sending fake LBS requests for a period of time.In our design,vky, which is selected as the collaborator at an intersection, is required to keep sending fake LBS requests until arriving at the next intersection. Once the attacker mistakenly tracks vky, its predicted trajectory may create more divergences at the next intersection. In this way, trajectory privacy of vehicles will be better preserved. The distance between two intersections is generally more than 600 meters in the main urban roads, and the distance between the two gateways of the expressway is even further [19]. According to [20], the average speed of vehicles on weekday in first-tier cities is about 24km/h, while it can reach 30−45km/h in other major cities. Therefore, we assume that the average speed of vehicles is 10m/s and the time required for a collaborator to keep sending fake requests is 60s.


## 6. Performance Evaluation

In this section, we conduct traffic simulation to evaluate the performance of the proposed trajectory privacy-preserving scheme. 219 vehicles drive on an 6 km× 6 km map of Suzhou, China, as shown in Figure 2, using SUMO [21, 22]. We consider that a LBSP collects the received LBS requests for 5 minutes. Within these 5 minutes, vehicles using this LBS move randomly on the map following traffic rules. The LBS requests are sent by the vehicles every Tint. To investigate the effects of the density of vehicles using the LBS on the performance of our design, four situations, where 25%, 50%, 75%, and 100% vehicles on the road are using the LBS, are set.Figure 2
Map used in simulation.As described in Section5, a vehicle vk records its locations, velocities, and accelerations of N most recent historical time points. This information of N time points will be used to predict vk’s location at the future time and the collaborator will be selected based on the predicted location. A proper set of N will help vk make an accurate prediction, thus selecting a capable collaborator, with small memory and computation cost. To set a proper value of N, we try to make location predictions using the moving information of the 219 vehicles. As shown in Figure 3, prediction deviation, the average distance difference between predicted locations and real locations, changes with N. Generally, smaller deviation comes with greater N. This is intuitive since more information leads to more precise prediction. However, fluctuation occurs in Figure 3. This is because that vehicles cannot stay on the same moving pattern on different points of the road. For example, the velocity tends to be stable or change slightly between intersections, while the velocity tends to decrease and the acceleration tends to be stable or change slightly when a vehicle approaches the intersections. These complex road conditions cause fluctuations in the results of our predictions of vehicles’ full trajectories. Therefore, if N is not set properly, a vehicle will use the moving pattern between intersections to predict the moving pattern approaching intersections leading to imprecise predictions and increased deviations. According to the results shown in Figure 3, N is set to be 5 in our simulation.Figure 3
Prediction deviation with differentN values.


### 6.1. Performance Metrics

Two metrics are designed to evaluate the trajectory privacy-preserving performance. First, tracking success ratio is designed to represent the possibility that the actual trajectory isvk’s trajectory in the adversary’s eyes. For a time t, the tracking success ratio is defined as follows:(13)SRt=∏j=0tpk,j,where k satisfies that location Lokj,Lakj is on the trajectory.Then, we propose a metric to investigate the trajectory privacy-preserving efficiency. For collaborative obfuscation, collaborators are required to send fake LBS requests. Therefore, the number of collaborators selected byvk is considered as the cost to preserve vk’s trajectory privacy. Let NCVt denote the number of selected collaborators until time t, and the privacy-preserving efficiency Et is defined as follows:(14)Et=1−SRtNCVt.


### 6.2. Performance Analysis and Comparison

We first investigate the average tracking success ratio of each density. As can be seen from Figure4, tracking success ratio of each density decreases gradually and reduces to almost 0 over time. The tracking success ratio of low density is obviously higher than that of high density. This result confirms the influence of the number of obfuscation locations on privacy preserving. More vehicles using the same LBS will lead to more LBS requests with similar locations submitted at a specific time. These requests can help each other mislead the adversary. That is, the actual LBS requests from other vehicles play the role of fake requests for vk.Figure 4
Tracking success ratiov.s. The density of vehicles using the LBS.The tracking success ratio of our design is also compared with that of the scheme proposed in [10], referred to RefScheme in the rest of this section. It can be seen from Figure 4 that our scheme holds similar tracking success ratio with RefScheme and our scheme performances slightly worse than RefScheme before 2 minutes under 50% and 75% densities. It is because that vehicles generate fake locations all the time on their way in RefScheme, while our scheme only works at intersections. Less collaborators are selected, and less fake LBS requests are sent leading to a slightly worse performance with less communication cost for collaborator selection and request sending. However, our design outperforms RefScheme when the density of vehicles using the LBS is low. This is because that more confusing trajectories are generated by our scheme. When the density reaches 100%, because the vehicles on the road are using the same LBS and the location updates received by LBSP under these two schemes are the same, the tracking success ratio of the two schemes is the same.Figure5 shows the efficiency defined in (14) of two schemes. We can see that the efficiency of both is 0 at first since SR0=1. Clearly, our scheme outperforms RefScheme since a similar tracking success ratio can be achieved by our scheme with less collaborators. It should be noted that all curves in Figure 5 are not monotonous. This is because that NCV does not increase monotonically due to the randomness of vehicle movement.Figure 5
Privacy-preserving efficiency for different densities.Moreover, the proposed scheme can be qualitatively compared with other existing methods, such as silent period [7], mix zone [15], and location obfuscation [17] from the perspectives of privacy performance and service quality. The comparison result is shown in Table 2. References [7, 17] provide good privacy protection with compromise on service quality since no service request is sent during the silent period and service is provided based on deviated locations, respectively. The service quality of scheme [15] can be guaranteed, but it is vulnerable to continuous tracking attacks. Our scheme overcomes these drawbacks since fake requests from collaborators protect trajectory privacy, while actual requests ensure service quality.Table 2
Qualitative performance comparison.
SchemeService qualityPrivacy performanceThe proposed schemeHighHighSilent period [7]LowHighMix zone [15]HighLowLocation obfuscation [17]LowHigh


## 6.1. Performance Metrics

Two metrics are designed to evaluate the trajectory privacy-preserving performance. First, tracking success ratio is designed to represent the possibility that the actual trajectory isvk’s trajectory in the adversary’s eyes. For a time t, the tracking success ratio is defined as follows:(13)SRt=∏j=0tpk,j,where k satisfies that location Lokj,Lakj is on the trajectory.Then, we propose a metric to investigate the trajectory privacy-preserving efficiency. For collaborative obfuscation, collaborators are required to send fake LBS requests. Therefore, the number of collaborators selected byvk is considered as the cost to preserve vk’s trajectory privacy. Let NCVt denote the number of selected collaborators until time t, and the privacy-preserving efficiency Et is defined as follows:(14)Et=1−SRtNCVt.


## 6.2. Performance Analysis and Comparison

We first investigate the average tracking success ratio of each density. As can be seen from Figure4, tracking success ratio of each density decreases gradually and reduces to almost 0 over time. The tracking success ratio of low density is obviously higher than that of high density. This result confirms the influence of the number of obfuscation locations on privacy preserving. More vehicles using the same LBS will lead to more LBS requests with similar locations submitted at a specific time. These requests can help each other mislead the adversary. That is, the actual LBS requests from other vehicles play the role of fake requests for vk.Figure 4
Tracking success ratiov.s. The density of vehicles using the LBS.The tracking success ratio of our design is also compared with that of the scheme proposed in [10], referred to RefScheme in the rest of this section. It can be seen from Figure 4 that our scheme holds similar tracking success ratio with RefScheme and our scheme performances slightly worse than RefScheme before 2 minutes under 50% and 75% densities. It is because that vehicles generate fake locations all the time on their way in RefScheme, while our scheme only works at intersections. Less collaborators are selected, and less fake LBS requests are sent leading to a slightly worse performance with less communication cost for collaborator selection and request sending. However, our design outperforms RefScheme when the density of vehicles using the LBS is low. This is because that more confusing trajectories are generated by our scheme. When the density reaches 100%, because the vehicles on the road are using the same LBS and the location updates received by LBSP under these two schemes are the same, the tracking success ratio of the two schemes is the same.Figure5 shows the efficiency defined in (14) of two schemes. We can see that the efficiency of both is 0 at first since SR0=1. Clearly, our scheme outperforms RefScheme since a similar tracking success ratio can be achieved by our scheme with less collaborators. It should be noted that all curves in Figure 5 are not monotonous. This is because that NCV does not increase monotonically due to the randomness of vehicle movement.Figure 5
Privacy-preserving efficiency for different densities.Moreover, the proposed scheme can be qualitatively compared with other existing methods, such as silent period [7], mix zone [15], and location obfuscation [17] from the perspectives of privacy performance and service quality. The comparison result is shown in Table 2. References [7, 17] provide good privacy protection with compromise on service quality since no service request is sent during the silent period and service is provided based on deviated locations, respectively. The service quality of scheme [15] can be guaranteed, but it is vulnerable to continuous tracking attacks. Our scheme overcomes these drawbacks since fake requests from collaborators protect trajectory privacy, while actual requests ensure service quality.Table 2
Qualitative performance comparison.
SchemeService qualityPrivacy performanceThe proposed schemeHighHighSilent period [7]LowHighMix zone [15]HighLowLocation obfuscation [17]LowHigh


## 7. Conclusion

This study proposes a collaborative trajectory obfuscation scheme based on analyzing the attack model of adversaries. Compared with exiting works, our design has high service quality and high privacy strength and can preserve the trajectory privacy with less cost, that is, fewer collaborators. To better reproduce the real usage scenario where not all vehicles are using the same LBS, we introduce the density of vehicles using the same LBS as a variable in our simulation. The results show that low density will increase the risk of trajectory exposure, and therefore, density should be considered when designing trajectory privacy-preserving schemes.



---

*Source: 1424078-2022-02-15.xml*