面向实时位置的隐私保护优化与加速求解算法

Optimizing and Accelerating Privacy Protection Algorithm for Real-Time Location

现有的电动汽车API平台(如SmartCar)使用访问控制机制来保护用户的隐私.为了在启用不可信位置服务功能的同时保护位置隐私,位置隐私保护机制(LPPM)根据用户的真实位置生成一个随机的伪位置作为报告位置.现有技术通过在离散网格上解决一个最优化问题构建一个最佳的LPPM,该最佳LPPM实现了在最低可容忍效用限制下的最高隐私,反之亦然.然而,它们很难直接应用于电动汽车等实时场景,因为生成最佳LPPM所需的运行时间太长(可能需要数天).另一个问题涉及构建出的LPPMs的最佳性.揭示了一些意外情况(异常),即在粒度更高的细网格上构建的最佳LPPM效用比在粒度较低的粗网格上差.引入了粒度独立性作为有效解决方法,提出了一个名为Divide-and-Coin的最佳LPPM,其可以实时执行.Divide-and-Coin将生成最佳报告位置的运行时间从至少O(n^(2.055))缩短到O(log n),其中n是报告位置的数量.实验结果显示,Divide-and-Coin可以在1s内从城市级区域生成建筑级别的最佳报告位置.

Existing electric vehicle API platforms(e.g.,SmartCar),use access control mechanisms to preserve users’privacy.To preserve location privacy and meanwhile enable functionality of untrustworthy location-based services,a location privacy preserving mechanism(LPPM)can be used to generate a random pseudo-location as a reported location based on a user’s true location.Existing techniques solve an optimization problem on a discrete grid,to construct an optimal LPPM which achieves the highest privacy bounded by minimum tolerable utility,or vice versa.However,they cannot be applied to real-time electric vehicle scenarios since the running time required to generate an optimal LPPM is too long(which can be several days).Another problem deals with optimality of constructed LPPMs.We reveal unexpected cases(anomaly)when the optimal LPPM constructed on a fine grid with superior granularity is worse than that on a coarse one with inferior granularity.We introduce granularity independence as a formal treatment,and propose an optimal LPPM named Divide-and-Coin which can be performed on the fly.Divide-and-Coin improves the running time from at least O(n^(2.055))to O(log n),where n is the number of reported locations.Our experimental results show that Divide-and-Coin generates an optimal building-level reported location from a city-level area within one second.