一种路网环境中的轨迹隐私保护技术

A TRAJECTORY PRIVACY PROTECTION TECHNOLOGY IN ROAD NETWORK ENVIRONMENT

不经过隐私处理直接发布轨迹数据会导致移动对象的个人隐私泄露,传统的轨迹隐私保护技术用聚类的方法产生轨迹k-匿名集,只适用在自由空间环境,并不适用于道路网络环境中。针对上述问题设计了一种路网环境中的轨迹隐私保护方法,将路网环境中的轨迹模拟到无向图上,并将轨迹k-匿名问题归结到无向图的knode划分问题上。证明了图的k-node划分是NP-完全问题,并提出贪心算法解决此问题。通过实验验证了该算法的匿名成功率平均接近60%,最高可达80%以上。

Directly publishing trajectory data without privacy processing can result in the disclosure of personal privacy of the moving object. Traditional trajectory privacy protection technology uses the method of clustering to generate trajectory k-anonymous set, which only applies to free space environment and does not apply to road network environment. A trajectory privacy protection method in road network environment was designed to simulate the trajectory in the road network environment to an undirected graph, and the k-anonymity problem was reduced to the k-node partition problem of undirected graphs. It was proved that the k-node partition of the graph is an NP-complete problem and a greedy algorithm was proposed to solve this problem. The anonymous success rate of the algorithm was verified to be close to 60% on average, and the maximum is over 80%.