# Collaborative Caching for Implementing a Location-Privacy Aware LBS on a MANET
## 5 Data Security and Privacy Considerations
### Location Privacy Analysis  
We consider a network system consisting of \(m\) disjoint spatial cells, each cell of size \(rxr\) as shown in Figure 2, containing \(n\) equally probable positions that represent the minimum location resolution. The probability of a cell being queried is proportional to its query frequency. To protect their privacy, users can select \(k\) cells to form a k-anonymity set when submitting location-based queries. We assume that a total of \(U\) users are moving within the network, and a fraction of them are located within each cell \(j\). _The entropy of a single cell, \(H(C)\), is given by \(H(C)=\log_{2}n\), which is based on the uniform probability distribution of the location of a user within the cell [31]. Before a user enters a cell or submits a query, the cell's master has no knowledge of the user's location, and the entropy is \(H(\text{before query})=\log_{2}(m\times n)\). After the query is broadcast to the cell, the cell's master (and other users in the cell) learns that the user is within its cell, reducing the entropy to \(H(\text{after query})=\log_{2}n\). The privacy loss for the cell's master is thus privacy loss (Cell) \(=\log_{2}m\). Similarly, the _LBS server's entropy_ before the query is \(H(\text{before query})=\log_{2}(m\times n)\). After receiving a query with \(k\)_-anonymity_, the LBS server learns that the user is within one of the \(k\) cells in the anonymity set, resulting in an approximate entropy of \(H(\text{after query})\approx\log_{2}(k\times n)\). The privacy loss for the LBS server is privacy loss (LBS) \(\approx\log_{2}(m/k)\). _The accumulated privacy loss (APL)_ is proposed to capture the cumulative privacy loss across all users in the system. The formulation for APL is based on the following considerations. * For cell-based queries, the APL is defined as \[APL(cell_{j})=V_{j}\times N_{j}\times\log_{2}m\] (1) where \(V_{j}\) is the number of queries based on cell \(j\) issued by users in cell \(j\), and \(N_{j}\) is the total number of nodes in cell \(j\). This formulation accounts for the fact that all nodes in the cell potentially receive the query information, not just the master node. The privacy loss is thus multiplied by the number of nodes in the cell, as each of these nodes could potentially compromise the privacy of the querying users. * For LBS-based queries with k-anonymity, the APL is defined as \[APL(\text{LBS})\approx\alpha\times U_{\text{LBS}}\times\log_{2}(m/k)\] (2) where \(U_{\text{LBS}}\) is the number of queries sent to the LBS server, and \(\alpha\) is a weighting factor to account for the LBS server's ability to maintain and accumulate historical information from all cells over time. In contrast to the cells' master node, the LBS server is a centralized entity that collects information from all cells over time, potentially leading to a higher cumulative privacy loss. The weighting factor \(\alpha\) (\(\alpha>1\)) can be chosen based on the desired level of privacy protection and the relative importance of the comprehensive view of the LBS server compared to the limited view of cell nodes. For simplicity, in this work, we assume \(\alpha=1\). The average APL across all cells is given by  
\[APL(cell) =\frac{1}{m}\sum_{j=1}^{m}APL(cell_{j}) \tag{3}\] \[=\frac{1}{m}\sum_{j=1}^{m}V_{j}\times N_{j}\times\log_{2}m\]  
For APL(LBS) to be greater than the average APL(cell), the following condition should be satisfied:  
\[U_{\text{LBS}}\times\log_{2}(m/k)>\frac{1}{m}\sum_{j=1}^{m}V_{j}\times N_{j} \times\log_{2}m \tag{4}\]This condition depends on multiple factors: the number of queries sent to the LBS (\(U_{\text{LBS}}\)), the number of cells in the _k-anonymity_ set (_k_), the number of queries issued within each cell (_V_), and the total number of nodes in each cell (_N_). The inclusion of _N_j in the cell-based privacy loss calculation reflects the potential for all nodes in a cell to access query information, not just the cell master.