# An Efficient Dummy-Based Location Privacy-Preserving Scheme for Internet of Things Services
## 3 Enhanced-DLP Scheme
### The Basic Idea of the Enhanced-DLP Scheme  
The goal of the Enhanced-DLP scheme is to efficiently select the dummy locations in an enhanced greedy manner by considering some side information that is available to an adversary. Namely, when constructing the \(k\) anonymous set, we select the \(k\) dummy locations with the most similar history query probability to the user's real location in an enhanced greedy manner. Our goal is to generate an anonymous set with sufficiently large entropy. For example, we suppose that there is a candidate set (denoted as \(D\)) of size \(2k\). If the Enhanced-DLP has already selected \(i\) (where \(i<k\)) locations from set \(D\) as a set denoted as \(C\). When selecting the \((i+1)^{th}\) location, the Enhanced-DLP needs to calculate the location with the maximum query probability (denoted as \(p_{max}\)) and the location with the minimum query probability (denoted as \(p_{min}\)) in the anonymous set \(C\). Then the Enhanced-DLP finds two locations from candidate list \(D\), where one is the location with the maximum query probability less than \(p_{min}\) (denoted by \(p_{min-max}\)), and the other is the location with the minimum query probability greater than \(p_{max}\) (denoted by \(p_{max-min}\)). Finally, the Enhanced-DLP needs to calculate \(H(C,p_{min-max})\)  
Figure 2: LSB privacy-protection model in IoT. and \(H(C,p_{max-min})\) according to Equation (3). From Equation (4), the \(p_{n+1}\) is not greater than the maximum of set \(C\), and the \(p_{n+1}\) is not less than the minimum of set \(C\) as well. \[ \begin{split} H\left(C,p_{n+1}\right)=&-\sum_{p_{j} \in C}\frac{p_{j}}{\sum_{p_{j}\in C}p_{j}+p_{n+1}}\log_{2}\frac{p_{j}}{\sum_{p_ {j}\in C}p_{j}+p_{n+1}}\\ &-\frac{p_{n+1}}{\sum_{p_{j}\in C}p_{j}+p_{n+1}}\log_{2}\frac{p_{ n+1}}{\sum_{p_{j}\in C}p_{j}+p_{n+1}}\end{split}  \tag{3}\]  
\[\min(C)\leq p_{n+1}=\exp\left(\frac{\sum_{p_{j}\in C}p_{j}\log_{2}p_{j}}{\sum_{ p_{j}\in C}p_{j}}\right)\leq\max(C) \tag{4}\]  
where \(p_{j}\) denotes the historical query probability at location \(j\). The Enhanced-DLP scheme's basic steps are as follows:  
1. In the beginning, a user sets the value of the privacy degree \(k\) according to the privacy requirement. Then, the Enhanced-DLP obtains all the historical query probability of all locations on the LBS server and sorts them in ascending order according to the historical query probability (denoted as \(S\)). Let \(p\) denote the query probability of the user's real location, and let \(C\) denote the final anonymous set. 2. The Enhanced-DLP scheme counts the number of locations that have the same historical query probability as \(p\) in set \(S\), which is denoted by \(k_{b}\). 3. If size (\(k_{b}\)) \(\geq\) k, then the Enhanced-DLP randomly selects \(k-1\) locations that have the same historical query probabilities as the user's location \(p\) from \(k_{b}\) and puts them into \(C\). Then, the Enhanced-DLP randomly inserts the user's real location \(p\) into \(C\). 4. If \(1<\text{size}(k_{b})<k\), the Enhanced-DLP scheme puts each location in \(k_{b}\) and user's location \(p\) into \(C\). Then, the Enhanced-DLP selects \(2k\)-\(2\) candidate locations (denoted as set \(D\)), in which \(k-1\) locations are less than the \(p\) and the other \(k-1\) locations are greater than the \(p\) in the set \(S\). Otherwise, it goes to Step (7). 5. The Enhanced-DLP finds the location maximum with query probability (denoted as \(p_{max}\)) and location with minimum query probability (denoted as \(p_{min}\)) from set \(C\). The Enhanced-DLP finds two locations in set \(D\), which is the location with the maximum query probability less than \(p_{min}\) (denoted by \(p_{min-max}\)), and the other is the location minimum query probability being greater than \(p_{max}\) (denoted by \(p_{max-min}\)). Then, the Enhanced-DLP needs to calculate \(H(C,p_{max-min})\) and \(H(C,p_{min-max})\) according to Equation (3) and add the location into set \(C\), to attempt to achieve max entropy in set \(C\). 6.