Tradeoff Between Location Quality and Privacy in Crowdsensing: An Optimization Perspective
Tradeoff Between Location Quality and Privacy in Crowdsensing: An Optimization Perspective
复制标题
DOI：
10.1109/jiot.2020.2972555
复制
发表时间：
2020-02
影响因子：
10.6
通讯作者：
Yuhui Zhang;Ming Li;Dejun Yang;Jian Tang;G. Xue;Jia Xu
中科院分区：
文献类型：
--
作者：
Yuhui Zhang;Ming Li;Dejun Yang;Jian Tang;G. Xue;Jia Xu
Crowdsensing可以进行广泛的数据收集，其中数据通常标记有私人位置。保护用户的位置隐私一直是一个核心问题。各种位置扰动技术的研究，例如，$k$ -匿名性，因位置隐私受到广泛关注。尽管巨大的承诺和相当大的关注，可证明的好算法考虑位置隐私和位置信息质量之间的权衡，从优化的角度在人群感知的文献中缺乏。在这篇文章中，我们从两个不同的角度研究了两个相关的优化问题。第一个问题是最小化由于保护用户位置隐私而导致的位置质量下降。我们提出了一个有效的优化算法OLoQ这个问题。第二个问题是最大限度地保护用户的数量，受到位置质量下降的约束。为了满足平台的不同要求，我们考虑了两种情况：1）重叠和2）非重叠扰动。对于前一种情况，我们给出了一个有效的优化算法OPUMO。对于后一种情况，我们首先证明了它的NP-困难性。然后我们设计了一个$（1-\n）$ -近似算法NckN和一个快速有效的启发式算法HckN。大量的模拟表明，OLoQ，OPUMO和HALBN显着优于现有的算法。
Crowdsensing enables a wide range of data collection, where the data are usually tagged with private locations. Protecting users’ location privacy has been a central issue. The study of various location perturbation techniques, e.g., $k$ -anonymity, for location privacy has received widespread attention. Despite the huge promise and considerable attention, provable good algorithms considering the tradeoff between location privacy and location information quality from the optimization perspective in crowdsensing are lacking in the literature. In this article, we study two related optimization problems from two different perspectives. The first problem is to minimize the location quality degradation caused by the protection of users’ location privacy. We present an efficient optimal algorithm OLoQ for this problem. The second problem is to maximize the number of protected users, subject to a location quality degradation constraint. To satisfy the different requirements of the platform, we consider two cases for this problem: 1) overlapping and 2) nonoverlapping perturbations. For the former case, we give an efficient optimal algorithm OPUMO. For the latter case, we first prove its NP-hardness. We then design a $(1-\epsilon)$ -approximation algorithm NPUMN and a fast and effective heuristic algorithm HPUMN. Extensive simulations demonstrate that OLoQ, OPUMO, and HPUMN significantly outperform an existing algorithm.