# A Road Truncation-Based Location Privacy-Preserving Method against Side-Weight Inference Attack
## 3 Preliminaries and Problem Definition
### System Model  
In this paper, we consider the location privacy preserving issue for LBS in a city scenario. The mathematical symbols are shown in Table 2.  
As shown in Figure 1, the system consists of three parts, users, base stations (BS) and LBS providers. The users' activities are restricted by road network topology. With embedded GPS sensors, the users can get precise location coordinates and velocity. The base stations are connected by optical fibers and communicate with all users. They have background knowledge of road network topology and user distribution.  
When a user acquires the LBS, it needs to upload its personal location to the LBS providers through the base station. Navigation and query of POIs are basic LBS applications, which facilitate people's daily life. For example, the POI helps the user discover unknown environmental resources. A user can easily get the location information of interested buildings such as shops, banks and gas stations in the surrounding area. In order to protect location privacy, the user will communicate with the base station to get the information of user distribution and generate an anonymous set. The query message is uploaded to the base station and finally forwarded to LBS providers. The LBS provider deals with the query request and responds to the user with query results according to the anonymous set.  
\begin{table}
\begin{tabular}{c c} \hline \hline
**Privacy Preservation Mechanism** & **Reference** & **Characteristic** \\ \hline \(k\)-anonymity & [13; 28] & flexible and easy to implement; lack of location accuracy \\ \(l\)-diversity & [31; 32; 35] & \(k\)-anonymity method considering road network \\ Caching scheme & [15; 24] & accurate location; not applicable for real-time service \\ Dummy location & [16; 25] & accurate location; false location data causing resource waste \\ Homomorphic encryption & [17; 26; 27] & ciphertext can be calculated; high computation cost \\ Differential privacy & [18; 19; 20] & strict proof of privacy assessment \\ \hline \hline \end{tabular}
\end{table}
Table 1: Summary of Privacy Preserving Schemes that address Location Privacy.  
\begin{table}
\begin{tabular}{c c} \hline \hline
**Parameter** & **Description** \\ \hline \(C\) & the user’s query content \\ \(e_{i}\) & road section \(i\) \\ \(E(S)\) & the number of edges in anonymity set \(S\) \\ \(l\) & \(l\)-diversity \\ \(loc\) & the user’s location information \\ \(k\) & \(k\)-anonymity \\ \(n\) & the number of query objects required by the user \\ \(Q\) & LBS query message \\ \(S\) & anonymity set \\ \(t_{0}\) & the starting time of the algorithm \\ \(t_{n}\) & the current time of the algorithm \\ \(u_{id}\) & a user’s identity \\ \(V_{o}(S)\) & the number of marginal nodes \\ \(w(e_{i})\) & the weight of edge \(e_{i}\) \\ \((x,y)\) & location coordinates \\ \(\alpha\) & number of roads in candidate set \(C_{i}\) \\ \(\beta\) & number of roads that are truncated in \(C_{i}\) \\ \(\delta_{t}\) & the tolerant time for generating an anonymity set \\ \(\lambda\) & distribution degree \\ \(e\) & the ratio between the weight of edge \(e_{i}\) and the whole of the anonymous set \\ \hline \hline \end{tabular}
\end{table}
Table 2: Mathematical symbols.