# A Location Privacy Preservation Method Based on Dummy Locations in Internet of Vehicles
## 4 Algorithm Design
### Dummy Location Selection Algorithm under Road Restriction  
In order to ensure the validity of dummy locations, two conditions should be considered simultaneously for selecting the dummy locations. One is to maximize the anonymous entropy of the candidate set. The other is to maximize the effective distance of the candidate set. Figure 4: The diagram of effective distance. Figure 3: Schematic diagram of vehicle location distribution. (**a**) vehicle aggregation distribution; (**b**) vehicle dispersed distribution. Hence, the optimization problem formulated in (3) can convert to a multiple object optimization problem as  
\[\max_{\mathcal{G}}\left\{-\sum\limits_{r_{ij}\in\mathcal{G}^{\prime}}p_{ij}\log_{ 2}p_{ij},\sum\limits_{r_{ij}\in\mathcal{G}}d\left(r_{ij}\right)\right\} \tag{6}\] \[\text{s.t.}G(\mathbf{r},\mathbf{q},\mathbf{e})\subset Q(\mathbf{r},\mathbf{q},\mathbf{e})\] \[\forall\mathbf{r}_{i,j}\in\mathcal{G},\mathbf{r}_{i,j}\in\mathcal{C},\bm {r}_{i,j}\in\mathbf{R}\] \[\left|\mathcal{G}\right|=k,\]  
where candidate set \(\mathcal{G}\) consists of the vehicle user's location and \(k-1\) selected dummy locations. Obviously, the problem formulated in (6) is difficult to resolve. Hence, we decouple the problem in (6) into two sub-problems, the anonymous entropy maximization sub-problem and the effective distance maximization sub-problem. According to the background knowledge of the LBS server and the purpose of the dummy location selection algorithm, we give priority to the sub-problem of anonymous entropy maximization. That is,  
\[\max_{\mathcal{G}^{\prime}}\left\{-\sum\limits_{r_{ij}\in\mathcal{G}^{\prime}}p _{ij}\log_{2}p_{ij}\right\} \tag{7}\] \[\text{s.t.}G^{\prime}(\mathbf{r},\mathbf{q},\mathbf{e})\subset Q(\mathbf{r},\mathbf{q },\mathbf{e})\] \[\forall\mathbf{r}_{i,j}\in\mathcal{G}^{\prime},\mathbf{r}_{i,j}\in \mathcal{C},\mathbf{r}_{i,j}\in\mathbf{R}\] \[\left|\mathcal{G}^{\prime}\right|=k^{\prime},\]  
where set \(\mathcal{G}^{\prime}\) including the vehicle user's location and \(k^{\prime}-1\) selected dummy locations is set up to resolve the sub-problem formulated in (7), \(k^{\prime}\) is the number of locations in set \(\mathcal{G}^{\prime}\), and \(k^{\prime}>k\). According to \(Q(\mathbf{r},\mathbf{q},\mathbf{e})\), the vehicle user calculates the probability of service request at each location in \(\mathbf{R}\), \(q^{\prime}_{(i,j),u}\), \(i=1,2,\ldots,l,j=1,2,\ldots,l\), \(u=1,2,\ldots,l\), \(cell_{ij}\in\mathbf{R}\). According to service request probability of content \(C_{0}\), the vehicle user selects other \(k^{\prime}-1\) locations whose service request probabilities are close to that of the vehicle user. Hence, a candidate set \(\mathcal{G}^{\prime}\) is constructed with the vehicle user's location and \(k^{\prime}-1\) selected dummy locations. Then, the sub-problem for maximizing the effective distance of the candidate set is to resolve. That is,  
Figure 3:0 Figure 3:1 Figure 3:2 Figure 3:3  
where set \(\mathcal{G}^{\prime\prime}\) including the vehicle user's location and \(k-1\) selected dummy locations is set up to resolve the sub-problem formulated in (8). To solve the sub-problem formulated in (8), the vehicle user selects \(k-1\) dummy locations in a greedy manner. Let \(\mathbf{r}_{0,0}\) denote the location of the vehicle user. \(\mathcal{G}^{\prime\prime}=\{\mathbf{r}_{0,0}\}\) and \(\mathcal{G}^{\prime\prime}=\mathcal{G}^{\prime\prime}\setminus\{\mathbf{r}_{0,0}\}\). The vehicle user chooses \(k-1\) locations with the maximum effective distance through \(k-1\) rounds. In the \(i\)th round, \(i=1,2,\ldots,k-1\), the vehicle user calculates the effective distance of the location(s) in \(\mathcal{G}^{\prime}\) to the location(s) in \(\mathcal{G}^{\prime\prime}\).