Abstract
A measure of privacy infringement for agents (or participants) travelling across a transportation network in participatory-sensing schemes for traffic estimation is introduced. The measure is defined to be the conditional probability that an external observer assigns to the private nodes in the transportation network, e.g., location of home or office, given all the position measurements that it broadcasts over time. An algorithm for finding an optimal trade-off between the measure of privacy infringement and the expected estimation error, captured by the number of the nodes over which the participant stops broadcasting its position, is proposed. The algorithm searches over a family of policies in which an agent stops transmitting its position measurements if its distance (in terms of the number of hops) to the privacy sensitive node is smaller than a prescribed threshold. Employing such symmetric policies are advantageous in terms of the resources required for implementation and the ease of computation. The results are expanded to more general policies. Further, the effect of the heterogeneity of the population density on the optimal policy is explored. Finally, the relationship between the betweenness measure of centrality and the optimal privacy-preserving policy of the agents is numerically explored.
Introduction
Participatory-sensing schemes, such as Waze or Strava, rely on users sharing real-time GPS data to estimate traffic flow and travel times. While beneficial for the community, this data sharing introduces significant privacy risks. An external observer can often infer a user's "private nodes"—sensitive locations like a home or workplace—by analyzing the start and end points of their trajectories.
Traditional privacy-preserving methods, such as Differential Privacy (adding random noise to coordinates), are often ineffective in this context. For instance, if a user remains at a static location (like home) for an extended period, an observer can average the noisy measurements to pinpoint the exact location. This paper proposes a "privacy zone" framework where agents strategically stop broadcasting their position when they are within a certain distance of a sensitive node.
Problem Formulation and Methods
The transportation network is modeled as an undirected graph $G = (V, E)$, where nodes $V$ represent intersections and edges $E$ represent road segments.
Privacy Measure
The authors define privacy infringement ($\pi_a$) as the conditional probability that an observer correctly identifies an agent's private node $s_a$, given the set of locations where the agent chose to broadcast data.
Symmetric Policies
To ensure computational efficiency and ease of implementation on mobile devices, the study focuses on symmetric policies. Under such a policy, an agent stops broadcasting if their distance (measured in hops) to a private node $s_a$ is less than or equal to a threshold radius $h_a$. This creates a "privacy zone" $\mathcal{B}(s_a, h_a)$ around the sensitive location.
The optimization goal is to find a threshold $h_a$ that minimizes a weighted sum of the privacy risk ($\pi_a$) and the utility cost (the number of road segments where data is hidden), or to minimize cost while keeping risk below a certain bound.
Key Insights: The Role of Centrality
A critical finding of the research is the relationship between a node's betweenness centrality and its privacy requirements. Betweenness centrality measures how often a node lies on the shortest paths between other nodes in the network.
Nodes with high betweenness centrality act as major thoroughfares. If an agent's private node is centrally located, an observer can more easily "triangulate" the location based on the patterns of surrounding broadcasts. Consequently, users living in central areas require a larger privacy radius $h_a$ to achieve the same level of privacy as those in peripheral areas.
As shown in Figure 2, for nodes with high betweenness, the privacy risk $\pi_a$ remains high for small radii and drops sharply only at larger $h_a$, while the cost increases more rapidly compared to peripheral nodes.
Results and Real-World Application
The proposed algorithms were evaluated using both synthetic Random Geometric Graphs and the real-world road network of Melbourne's city center.
- Risk Reduction: In the Melbourne simulation, even a relatively small radius $h_a$ significantly reduced the probability of identifying a private node.
- Utility Preservation: The "cost" to the traffic estimation system—measured by the number of un-sensed edges—remained low enough to maintain the viability of collective traffic estimation.
- Population Density: The model also accounts for population density. In high-density areas, the "prior probability" of any specific node being the private one is lower, allowing for smaller, more efficient privacy zones.
Conclusion and Future Work
This paper provides a provable method for balancing individual privacy with the utility of participatory-sensing systems. By using radius-based symmetric policies, the authors offer a solution that is both mathematically sound and computationally practical for real-time applications.
Future research directions include explicitly simulating the impact of hidden data on traffic flow estimation error and exploring incentive mechanisms to encourage data reporting in areas where privacy risks are minimal.
Summary updated