基于轨迹扰动和路网匹配的位置隐私保护算法

doi:10.11772/j.issn.1001-9081.2023050680

《计算机应用》唯一官方网站 ›› 2024, Vol. 44 ›› Issue (5): 1546-1554.DOI: 10.11772/j.issn.1001-9081.2023050680

• 网络空间安全 • 上一篇

基于轨迹扰动和路网匹配的位置隐私保护算法

刘沛骞¹, 王水莲², 申自浩², 王辉¹()

^1.河南理工大学软件学院，河南焦作 454000
^2.河南理工大学计算机科学与技术学院，河南焦作 454000

收稿日期:2023-05-30 修回日期:2023-07-30 接受日期:2023-08-11 发布日期:2023-09-01 出版日期:2024-05-10
通讯作者: 王辉
作者简介:刘沛骞（1970—），男，山西大同人，副教授，博士，主要研究方向：机器学习、自然语言处理、信息安全
王水莲（1999—），女，河南周口人，硕士研究生，主要研究方向：网络信息安全、智能信息处理
申自浩（1980—），男，河南南阳人，副教授，博士，主要研究方向：网络与信息安全、智能信息处理、信息仿真
第一联系人：王辉（1975—），男，河南焦作人，教授，博士，主要研究方向：移动互联网隐私保护、网络信息安全、信息系统研发及仿真。
基金资助:
河南省高等学校重点科研项目(23A520033);河南理工大学博士基金资助项目(B2022?16)

Location privacy protection algorithm based on trajectory perturbation and road network matching

Peiqian LIU¹, Shuilian WANG², Zihao SHEN², Hui WANG¹()

^1.School of Software，Henan Polytechnic University，Jiaozuo Henan 454000，China
^2.School of Computer Science and Technology，Henan Polytechnic University，Jiaozuo Henan 454000，China

Received:2023-05-30 Revised:2023-07-30 Accepted:2023-08-11 Online:2023-09-01 Published:2024-05-10
Contact: Hui WANG
About author:LIU Peiqian， born in 1970， Ph. D.， associate professor. His research interests include machine learning， natural language processing， information security.
WANG Shuilian， born in 1999， M. S. candidate. Her research interests include network information security， intelligent information processing.
SHEN Zihao， born in 1980， Ph. D.， associate professor. His research interests include network and information security， intelligent information processing， information simulation.
Supported by:
Key Scientific Research Projects of Colleges and Universities in Henan Province(23A520033);Doctoral Scientific Fund of Henan Polytechnic University(B2022?16)

摘要/Abstract

摘要：

针对现有扰动机制未考虑位置点语义关系导致数据可用性较低的问题，提出一种基于差分隐私（DP）的轨迹位置隐私保护机制（DP-TLPM）。首先，DP-TLPM利用滑动窗口提取轨迹停留点生成模糊区域，再利用指数机制和拉普拉斯机制对该区域进行采样；其次，为了消除采样点中可能存在的无语义位置点，提出一种路网匹配算法，对轨迹分段并利用误差椭圆匹配（EEM）进行迭代匹配；最后，根据匹配后的位置点形成扰动轨迹，由用户端将扰动轨迹发送至服务器。实验以混淆质量和均方根误差（RMSE）为评价标准对该机制进行综合评测。与GeoInd算法相比，DP?TLPM的数据质量损失降低了24%，轨迹的混淆质量提高了52%，从隐私保护强度和数据质量两方面验证了该算法的有效性。

关键词: 轨迹隐私保护, 路网匹配, 位置扰动, 拉普拉斯机制

Abstract:

Aiming at the problem of low data availability caused by existing disturbance mechanisms that do not consider the semantic relationship of location points， a Trajectory Location Privacy protection Mechanism based on Differential Privacy was proposed， namely DP-TLPM. Firstly， the sliding windows were used to extract trajectory dwell points to generate the fuzzy regions， and the regions were sampled using exponential and Laplacian mechanisms. Secondly， a road network matching algorithm was proposed to eliminate possible semantic free location points in the sampled points， and the trajectory was segmented and iteratively matched by using Error Ellipse Matching （EEM）. Finally， a disturbance trajectory was formed based on the matched location points， which was sent to the server by the user. The mechanism was evaluated comprehensively by confusion quality and Root Mean Square Error （RMSE）. Compared with the GeoInd algorithm， the data quality loss of the DP-TLPM is reduced by 24% and the confusion quality of the trajectories is improved by 52%， verifying the effectiveness of DP-TLPM in terms of both privacy protection strength and data quality.

Key words: trajectory privacy protection, road network matching, position disturbance, Laplacian mechanism

中图分类号:

TP309

刘沛骞, 王水莲, 申自浩, 王辉. 基于轨迹扰动和路网匹配的位置隐私保护算法[J]. 计算机应用, 2024, 44(5): 1546-1554.

Peiqian LIU, Shuilian WANG, Zihao SHEN, Hui WANG. Location privacy protection algorithm based on trajectory perturbation and road network matching[J]. Journal of Computer Applications, 2024, 44(5): 1546-1554.

图/表 17

表1 符号及其描述

Tab.1 Symbol and description

符号	含义
$s p i$	第i个停留点
$r i, k$	第i个停留点的第k个模糊子区域
$r i, k c$	第i个停留点的第k个子区域的中心点
$S t$	扰动轨迹
$S i$	$S t$ 中的轨迹段
$C l s$	更新后的关键样本集合
$C l p$	更新后的候选弧段
$C l s i$	第i个关键样本
$C l p i j$	第i个关键样本对应的第j个候选弧
$i n t e r s e c t (e l p, C l p i k)$	椭圆与候选弧段之间的交线

表1 符号及其描述

Tab.1 Symbol and description

符号	含义
$s p i$	第i个停留点
$r i, k$	第i个停留点的第k个模糊子区域
$r i, k c$	第i个停留点的第k个子区域的中心点
$S t$	扰动轨迹
$S i$	$S t$ 中的轨迹段
$C l s$	更新后的关键样本集合
$C l p$	更新后的候选弧段
$C l s i$	第i个关键样本
$C l p i j$	第i个关键样本对应的第j个候选弧
$i n t e r s e c t (e l p, C l p i k)$	椭圆与候选弧段之间的交线

图1 停留点类型

Fig. 1 Types of dwell points

图2 DP-TLPM隐私模型

Fig. 2 DP-TLPM privacy model

图3 采样点选取

Fig. 3 Selection of sampled nodes

图4 轨迹缓冲区的路段选择

Fig. 4 Section selection of trajectory buffer

图5 用户的轨迹段

Fig. 5 User trajectory segments

图6 寻找回溯次数

Fig. 6 Acquisition of backtracking times

图7 候选弧的选择

Fig. 7 Selection of candidate arcs

图8 路段信息

Fig. 8 Road section information

图9 误差椭圆的迭代过程

Fig. 9 Iterative process of error ellipse

图10 存在两个交线

Fig. 10 Existence of two intersecting lines

图11 匹配后的轨迹处理

Fig. 11 Trajectory processing after matching

图12 不同隐私预算下各算法的混淆质量与RMSE对比

Fig. 12 Comparison of confusion quality and RMSE for each algorithm at different privacy budget

图13 DP-TLPM与DMM的匹配精度对比

Fig. 13 Matching accuracy comparison of DP-TLPM and DMM

图14 匹配前后的数据质量

Fig. 14 Data quality before and after matching

图15 效用权重的影响

Fig. 15 Effect of utility weight

图16 地图匹配前后的可视化匹配结果

Fig. 16 Visual matching results before and after map matching

参考文献 25

1	XING L， JIA X， GAO J， et al. A location privacy protection algorithm based on double k-anonymity in the social internet of vehicles［J］. IEEE Communications Letters， 2021， 25（10）： 3199-3203. 10.1109/lcomm.2021.3072671
2	LIU H， ZHANG S， LI M， et al. An effective location privacy-preserving k-anonymity scheme in location based services［C］// Proceedings of the 2021 IEEE International Conference on Electronic Technology， Communication and Information. Piscataway： IEEE， 2021： 24-29. 10.1109/icetci53161.2021.9563598
3	DWORK C. Differential privacy： a survey of results［C］// Proceedings of the 2008 International Conference on Theory and Applications of Models of Computation. Berlin： Springer， 2008： 1-19. 10.1007/978-3-540-79228-4
4	WANG B， LI H T， REN X， et al. An efficient differential privacy-based method for location privacy protection in location-based services［J］. Sensors， 2023， 23（11）： 5219. 10.3390/s23115219
5	ZHANG Z， XU X， XIAO F. LGAN-DP： a novel differential private publication mechanism of trajectory data［J］. Future Generation Computer Systems， 2023， 141： 692-703. 10.1016/j.future.2022.12.011
6	QIAN X， WU Y， LI M， et al. LAST： location-appearance-semantic-temporal clustering based poi summarization［J］. IEEE Transactions on Multimedia， 2021， 23： 378-390. 10.1109/tmm.2020.2977478
7	NING B， SUN Y， TAO X， et al. Differential privacy protection on weighted graph in wireless networks［J］. Ad Hoc Networks， 2021， 110： 102303. 10.1016/j.adhoc.2020.102303
8	LIU H， LI X， LI H， et al. Spatiotemporal correlation-aware dummy-based privacy protection scheme for location-based services［C］// Proceedings of the 2017 IEEE Conference on Computer Communications. Piscataway： IEEE， 2017： 1-9. 10.1109/infocom.2017.8056978
9	WANG Y， LI M， LUO S， et al. LRM： a location recombination mechanism for achieving trajectory k-anonymity privacy protection［J］. IEEE Access， 2019， 7： 182886-182905. 10.1109/access.2019.2960008
10	YANG D， YE B， ZHANG W， et al. KLPPS： a k-anonymous location privacy protection scheme via dummies and Stackelberg game［J］. Security and Communication Networks， 2021， 2021： 9635411. 10.1155/2021/9635411
11	YUAN S， PI D， ZHAO X， et al. Differential privacy trajectory data protection scheme based on R-tree［J］. Expert Systems with Applications， 2021， 182： 115215. 10.1016/j.eswa.2021.115215
12	YAN Y， SUN Z， MAHMOOD A， et al. Achieving differential privacy publishing of location-based statistical data using grid clustering［J］. ISPRS International Journal of Geo-Information， 2022， 11（7）： 404. 10.3390/ijgi11070404
13	郑磊，张俊星.面向连续位置服务的位置感知隐私保护方案［J］.浙江大学学报（工学版），2020，54（12）：2437-2444 .
	ZHENG L， ZHANG J X. Location-aware privacy protection scheme in continuous location-based service［J］. Journal of Zhejiang University （Engineering Science）， 2020， 54（12）： 2437-2444.
14	周长利，陈永红，田晖，等.保护位置隐私和查询内容隐私的路网K近邻查询方法［J］.软件学报，2020，31（2）：471-492.
	ZHOU C L， CHEN Y H， TIAN H， et al. Location privacy and query privacy preserving method for K-nearest neighbor query in road networks ［J］. Journal of Software， 2020，31（2）：471-492.
15	左开中，刘蕊，赵俊，等.融合语义信息的时空关联位置隐私保护方法［J］.西安电子科技大学学报（自然科学版），2022，49（1）：67-77.
	ZUO K Z， LIU R， ZHAO J， et al. Method for the protection of spatiotemporal correlation location privacy with semantic information ［J］. Journal of Xidian University （Natural Science）， 2022， 49（1）： 67-77.
16	YANG Z， WANG R， WU D， et al. Local trajectory privacy protection in 5G enabled industrial intelligent logistics［J］. IEEE Transactions on Industrial Informatics， 2022， 18（4）： 2868-2876. 10.1109/tii.2021.3116529
17	CHENG W， WEN R， HUANG H， et al. OPTDP： towards optimal personalized trajectory differential privacy for trajectory data publishing［J］. Neurocomputing， 2022， 472： 201-211. 10.1016/j.neucom.2021.04.137
18	QIU S， PI D， WANG Y， et al. Novel trajectory privacy protection method against prediction attacks［J］. Expert Systems with Applications， 2023， 213： 118870. 10.1016/j.eswa.2022.118870
19	WANG Y， XIONG R， TANG P， et al. Fast and reliable map matching from large-scale noisy positioning records［J］. Journal of Computing in Civil Engineering， 2023， 37（1）： 1-14. 10.1061/(asce)cp.1943-5487.0001054
20	DOGRAMADZI M， KHAN A. Accelerated map matching for GPS trajectories［J］. IEEE Transactions on Intelligent Transportation Systems， 2022， 23（5）： 4593-4602. 10.1109/tits.2020.3046375
21	GAO Z， HUANG Y， ZHENG L， et al. Protecting location privacy of users based on trajectory obfuscation in mobile crowdsensing［J］. IEEE Transactions on Industrial Informatics， 2022， 18（9）： 6290-6299. 10.1109/tii.2022.3146281
22	YU Q， HU F， YE Z， et al. High-frequency trajectory map matching algorithm based on road network topology［J］. IEEE Transactions on Intelligent Transportation Systems， 2022， 23（10）： 17530-17545. 10.1109/tits.2022.3155689
23	ZHENG Y， XIE X， MA W-Y. GeoLife： a collaborative social networking service among user， location and trajectory［J］. IEEE Data Engineering Bulletin， 2010， 33（2）： 32-39.
24	LI J， CHEN G. A personalized trajectory privacy protection method［J］. Computers & Security， 2021， 108： 102323. 10.1016/j.cose.2021.102323
25	ZHAO X， PI D， CHEN J. Novel trajectory privacy-preserving method based on clustering using differential privacy［J］. Expert Systems with Applications， 2020， 149： 113241. 10.1016/j.eswa.2020.113241

[1]	刘向宇, 陈金梅, 夏秀峰, Singh Manish, 宗传玉, 朱睿. 防止暴露位置攻击的轨迹隐私保护[J]. 《计算机应用》唯一官方网站, 2020, 40(2): 479-485.
[2]	郭良敏, 王安鑫, 郑孝遥. 基于区域划分的轨迹隐私保护方法[J]. 计算机应用, 2018, 38(11): 3263-3269.

基于轨迹扰动和路网匹配的位置隐私保护算法

Location privacy protection algorithm based on trajectory perturbation and road network matching

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

图/表 17

参考文献 25

相关文章 2

编辑推荐

Metrics