# An Efficient Dummy-Based Location Privacy-Preserving Scheme for Internet of Things Services
## 2 Preliminaries
### Review the Dummy-Based Location Privacy-Preserving Scheme  
The DLP scheme is used to solve the problem that the traditional dummy location selection scheme has a higher computational cost when selecting the dummy location. According to the value of \(k\), the DLP scheme needs to efficiently generate \(k-1\) dummy locations against side information that may be exploited by the attacker. The following steps show how it works:  
1. A user needs to give the degree of anonymity \(k\).
2. The DLP scheme needs to obtain the historical query probability of all locations and sort them in ascending order. Then, the DLP scheme calculates the number of locations (denoted as \(N\)) with the same historical query probability of the user's location (denoted as \(p\)). The anonymous set of the user is denoted as \(C\).
3. If \(N\geq k\), the DLP scheme arbitrarily selects \(k-1\) locations whose query probability is the same as \(p\) from \(N\) locations and user location \(p\) to form an anonymous set \(C\).
4. If \(k>N\geq k/4\), the DLP scheme selects \(N-1\) locations with the same query probability as the user location \(p\) from the sorted list and puts them into \(C\). The DLP scheme selects \(2k\) locations that are the most similar to the user's location \(p\) as a candidate set (denoted as \(S\)). The DLP scheme uses the greedy scheme \(k-N\) times to find \(k-N\) dummy locations from \(S\), and also puts them into \(C\) to form the anonymous set.
5. If \(N<k/4\), the DLP scheme chooses \(2k-\varepsilon\) locations less than, and \(2k-\omega\) locations greater than the real location to form a \(4k-\omega-\varepsilon\) candidate set from the sorted list (denoted as \(S_{b}\)).Then, the DLP arbitrarily selects one location from \(S_{b}\) and puts the location and the user's real location into \(C\). The DLP scheme uses the greedy scheme \(k-2\) times to find \(k-2\) dummy locations and puts them into \(C\) to form an anonymous set.
6. Finally, the optimal anonymous set \(C\) is found.  
Greedy scheme: A complex problem is divided into several steps, and each step can obtain a local optimal solution, so that the final result approximates the global optimal solution. In the Enhanced-DLP scheme, the basic idea of the greedy scheme is to find the optimal dummy location step by step from a candidate set. According to the measurement of the positional entropy, the dummy location selected in each step must ensure that the current anonymous set can obtain the max entropy. In the greedy scheme of the DLP scheme, each greedy choice needs to decide which location in the candidate set can give the current anonymous set the maximum entropy, and finally achieve the optimal dummy location.  
From the analysis of the DLP scheme, it can be seen that the DLP scheme is divided into three branches. In the first branch and the third branch, the scheme of generating the dummy location is already optimal. Our work is mainly to improve the scheme of generating the dummy location in the second branch by using the improved greedy scheme, which makes it possible to find the current optimal dummy location without traversing all the locations in the candidate set when generating the dummy location, in order to obtain a lower computational cost and lower attack probability. In addition the Enhanced-DLP can guarantee that the anonymous set has the same entropy as the anonymous set generated by the existing DLP scheme.