改进萤火虫群算法协同差分隐私的干扰轨迹发布

doi:10.11772/j.issn.1001-9081.2023030259

《计算机应用》唯一官方网站 ›› 2024, Vol. 44 ›› Issue (2): 496-503.DOI: 10.11772/j.issn.1001-9081.2023030259

所属专题：网络空间安全

改进萤火虫群算法协同差分隐私的干扰轨迹发布

彭鹏¹^,²^,³, 倪志伟¹^,³(), 朱旭辉¹^,³, 陈千¹^,³

^1.合肥工业大学管理学院，合肥 230009
^2.北方民族大学商学院，银川 750021
^3.过程优化与智能决策教育部重点实验室（合肥工业大学），合肥 230009

收稿日期:2023-03-14 修回日期:2023-06-03 接受日期:2023-06-27 发布日期:2023-09-01 出版日期:2024-02-10
通讯作者: 倪志伟
作者简介:彭鹏（1988—），男，安徽巢湖人，讲师，博士研究生，CCF会员，主要研究方向：智能优化、空间众包
朱旭辉（1991—），男，安徽阜阳人，讲师，博士，主要研究方向：深度学习、智能计算
陈千（1991—），男，安徽合肥人，博士研究生，主要研究方向：数据安全、隐私计算。
基金资助:
国家自然科学基金资助项目(71901001);安徽省自然科学基金资助项目(1908085QG298)

Interference trajectory publication based on improved glowworm swarm algorithm and differential privacy

Peng PENG¹^,²^,³, Zhiwei NI¹^,³(), Xuhui ZHU¹^,³, Qian CHEN¹^,³

^1.School of Management，Hefei University of Technology，Hefei Anhui 230009，China
^2.School of Business，North Minzu University，Yinchuan Ningxia 750021，China
^3.Key Laboratory of Process Optimization and Intelligent Decision?making，Ministry of Education（Hefei University of Technology），Hefei Anhui 230009，China

Received:2023-03-14 Revised:2023-06-03 Accepted:2023-06-27 Online:2023-09-01 Published:2024-02-10
Contact: Zhiwei NI
About author:PENG Peng， born in 1988， Ph. D. candidate， lecturer. His research interests include intelligent optimization， spatial crowdsourcing.
ZHU Xuhui， born in 1991， Ph. D.， lecturer. His research interests include deep learning， intelligent computing.
CHEN Qian， born in 1991， Ph. D. candidate. His research interests include data security， privacy computing.
Supported by:
National Natural Science Foundation of China(71901001);Anhui Provincial Natural Science Foundation(1908085QG298)

摘要/Abstract

摘要：

针对历史轨迹加噪发布干扰轨迹时数据集的冗余问题和轨迹形状相似带来的隐私泄露风险，提出轨迹数据先约简后泛化再进行差分隐私加噪的基于改进萤火虫群优化求解的干扰轨迹发布保护机制（IGSO-SDTP）。首先，基于位置显著点约简历史轨迹数据集；其次，结合k?匿名和差分隐私对简化后的轨迹数据集分别进行泛化和加噪；最后，设计了兼顾距离误差和轨迹相似性的加权距离，并以加权距离为评价指标，基于改进萤火虫群优化（IGSO）算法求解加权距离小的干扰轨迹。在多个数据集上的实验结果表明，与RD（Differential privacy for Raw trajectory data）、SDTP（Trajectory Protection of Simplification and Differential privacy）、LIC（Linear Index Clustering algorithm）、DPKTS（Differential Privacy based on K-means Trajectory shape Similarity）相比，IGSO-SDTP方法得到的加权距离分别降低了21.94%、9.15%、14.25%、10.55%，说明所提方法发布的干扰轨迹可用性和稳定性更好。

关键词: 干扰轨迹, 差分隐私, 改进萤火虫群优化算法, 加权距离, 显著点判断

Abstract:

In view of the redundancy of dataset and the risk of privacy leakage caused by the similarity of track shape when the interference track was noised and publicated by the historical track， an IGSO-SDTP （Trajectory Protection of Simplification and Differential privacy of the track data based on Improved Glowworm Swarm Optimization） was proposed. Firstly， the historical trajectory dataset was reduced based on the position salient points. Secondly， the simplified trajectory dataset was generalized and noised by combining k-anonymity and differential privacy. Finally， a weighted distance was designed to take into account the distance error and track similarity， and the weighted distance was used as the evaluation index to solve the interference track with a small weighted distance based on IGSO （Improved Glowworm Swarm Optimization） algorithm. Experimental results on multiple datasets show that compared with the RD（Differential privacy for Raw trajectory data）， SDTP（Trajectory Protection of Simplification and Differential privacy）， LIC（Linear Index Clustering algorithm）， and DPKTS（Differential Privacy based on K-means Trajectory shape Similarity）， the weighted distances obtained by IGSO-SDTP are reduced by 21.94%， 9，15%， 14.25% and 10.55%， respectively. It can be seen that the interference trajectory publicated by IGSO-SDTP has better usability and stability.

Key words: interference trajectory, differential privacy, Improved Glowworm Swarm Optimization (IGSO) algorithm, weighted distance, salient point judgment

中图分类号:

TP301.6

彭鹏, 倪志伟, 朱旭辉, 陈千. 改进萤火虫群算法协同差分隐私的干扰轨迹发布[J]. 计算机应用, 2024, 44(2): 496-503.

Peng PENG, Zhiwei NI, Xuhui ZHU, Qian CHEN. Interference trajectory publication based on improved glowworm swarm algorithm and differential privacy[J]. Journal of Computer Applications, 2024, 44(2): 496-503.

图/表 14

图1 不同的干扰轨迹

Fig.1 Different interference tracks

表1 轨迹加噪的主要符号及含义

Tab. 1 Main symbols and meanings for adding noise to trajectory

符号	含义
T	原始轨迹的位置点的数据集 $T = (l 1, t 1) → (l i, t i) → … → (l n, t n)$
KT	k-匿名泛化后的数据集 $K T = K T 1, K T 2, …, K T n =$ $(l 1 1 ~ k, t 1) → (l 2 1 ~ k, t 2) → … → (l n 1 ~ k, t n)$
$K T'$	k-匿名泛化和差分隐私加噪后的数据集 $K T' = K T 1', K T 2', …, K T n' =$ $(l 1 1 ~ k', t 1) → (l 2 1 ~ k', t 2) → … → (l n 1 ~ k', t n)$
$T'$	干扰轨迹的位置点的数据集 $T' = (l 1 s e m a x 1', t 1) → (l i s e m a x 2', t i) → … → (l n s e m a x n', t n)$
k	每个位置点k-匿名生成的点数
ε	差分隐私预算

表1 轨迹加噪的主要符号及含义

Tab. 1 Main symbols and meanings for adding noise to trajectory

符号	含义
T	原始轨迹的位置点的数据集 $T = (l 1, t 1) → (l i, t i) → … → (l n, t n)$
KT	k-匿名泛化后的数据集 $K T = K T 1, K T 2, …, K T n =$ $(l 1 1 ~ k, t 1) → (l 2 1 ~ k, t 2) → … → (l n 1 ~ k, t n)$
$K T'$	k-匿名泛化和差分隐私加噪后的数据集 $K T' = K T 1', K T 2', …, K T n' =$ $(l 1 1 ~ k', t 1) → (l 2 1 ~ k', t 2) → … → (l n 1 ~ k', t n)$
$T'$	干扰轨迹的位置点的数据集 $T' = (l 1 s e m a x 1', t 1) → (l i s e m a x 2', t i) → … → (l n s e m a x n', t n)$
k	每个位置点k-匿名生成的点数
ε	差分隐私预算

图2 IGSO-SDTP方法框架

Fig.2 Framework of IGSO-SDTP method

图3 Geo1~Geo6的轨迹形态

Fig. 3 Trajectories of Geo1~Geo6

表2 轨迹数据的约简

Tab. 2 Reduction of track data

轨迹	编号	点数	阈值	显著点数	约简率/%
Geo1	2008-3052	1 847	0.10	661	35.79
Geo2	2008-3300	3 683	0.10	1 008	27.37
Geo3	2009-4933	5 705	0.05	653	11.45
Geo4	2008-2204	7 584	0.10	1 538	20.28
Geo5	2008-5305	962	0.10	226	23.49
Geo6	2008-3959	1 499	0.10	424	28.29

表3 不同方法的距离误差

Tab. 3 Distance errors of different methods

轨迹	RD	SDTP	IGSO-SDTP	LIC	DPKTS
Geo1	23.94	21.48	19.53	21.12	24.31
Geo2	21.87	20.39	20.31	20.45	21.14
Geo3	21.76	20.76	20.53	20.89	21.46
Geo4	21.10	20.93	20.52	20.87	22.18
Geo5	20.92	15.28	14.37	18.13	21.54
Geo6	21.12	20.57	19.46	20.78	21.87

表4 不同方法的Frechet距离

Tab. 4 Frechet distances of different methods

轨迹	RD	SDTP	IGSO-SDTP	LIC	DPKTS
Geo1	59.50	46.52	43.86	54.16	48.17
Geo2	59.54	56.17	49.73	58.31	51.23
Geo3	66.41	59.01	52.20	61.28	56.11
Geo4	67.63	60.66	57.41	60.36	60.29
Geo5	60.52	39.66	33.10	50.17	45.74
Geo6	61.32	53.01	43.68	53.72	47.19

表5 不同方法的加权距离

Tab. 5 Weighted distances of different methods

轨迹数据	RD	SDTP	IGSO⁃SDTP	LIC	DPKTS
Geo1	41.72	34.00	31.69	37.64	36.24
Geo2	40.70	38.28	35.02	39.38	36.19
Geo3	44.09	39.88	36.36	41.09	38.79
Geo4	44.36	40.79	38.96	40.62	41.24
Geo5	40.72	27.47	23.74	34.15	33.64
Geo6	41.22	36.79	31.57	37.25	34.53

表6 不同隐私预算下的平均加权距离

Tab. 6 Average weighted distances under different privacy budgets

隐私预算	RD	SDTP	IGSO⁃SDTP	LIC	DPKTS
0.02	125.73	105.95	98.41	108.29	102.37
0.04	63.93	52.88	47.76	54.64	53.17
0.06	43.64	33.50	31.68	38.13	34.28
0.08	32.30	27.81	25.64	28.23	27.52
0.10	24.75	19.35	17.81	21.52	20.96
0.20	11.30	10.02	9.34	10.75	9.51
0.40	5.90	5.01	4.64	5.13	4.89
0.60	3.91	3.28	3.20	3.25	3.22
0.80	2.92	2.32	2.29	2.48	2.41

图4 不同方法的性能比较

Fig. 4 Performance comparison of different methods

表7 半径r的取值分析

Tab. 7 Analysis of radius r

平均

加权距离

平均

加权距离

平均

加权距离

图5 参数k的分析

Fig. 5 Analysis of parameter k

图6 参数p的分析

Fig. 6 Analysis of parameter p

图7 参数g的分析

Fig. 7 Analysis of parameter g

参考文献 31

1	JUNGLAS I A， WATSON R T. Location-based services［J］. Communications of the ACM， 2008， 51（3）： 65-69. 10.1145/1325555.1325568
2	童咏昕，袁野，成雨蓉，等. 时空众包数据管理技术研究综述［J］. 软件学报，2017， 28（1）： 35-58.
	TONG Y X， YUAN Y， CHENG Y R， et al. Survey on spatiotemporal crowdsourced data management techniques［J］. Journal of Software， 2017， 28（1）： 35-58.
3	田丰，吴振强，鲁来凤，等. 面向轨迹数据发布的个性化差分隐私保护机制［J］. 计算机学报， 2021，44（4）：709-723.
	TIAN F， WU Z Q， LU L F， et al. A sample based personalized differential privacy mechanism for trajectory data publication［J］. Chinese Journal of Computers， 2021， 44（4）： 709-723
4	ZHAO P， LI J， ZENG F， et al. ILLIA： enabling k-anonymity based privacy preserving against location injection attacks in continuous LBS queries［J］. IEEE Internet of Things Journal， 2018， 5（2）： 1033-1042. 10.1109/jiot.2018.2799545
5	朱素霞，刘抒伦，孙广路. 基于相对熵和K-means的形状相似差分隐私轨迹保护机制［J］. 通信学报， 2021， 42（2）： 113-123.
	ZHU S X， LIU S L， SUN G L. Shape similarity differential privacy trajectory protection mechanism based on relative entropy and K-means［J］. Journal on Communications， 2021， 42（2）：113-123.
6	巩现勇，李靖涵，行瑞星，等. 一种道路路口和拐点的识别与重要性度量方法［J］. 测绘与空间地理信息， 2018， 41（2）： 5-9. 10.3969/j.issn.1672-5867.2018.02.002
	GONG X Y， LI J H， XING R X， et al. Road roundabout and corner recognition and importance measurement［J］. Geomatics & Spatial Information Technology， 2018， 41（2）： 5-9. 10.3969/j.issn.1672-5867.2018.02.002
7	彭鹏，倪志伟，朱旭辉. 基于用户满意效用的空间众包任务分配方法［J］.计算机应用， 2022， 42（10）： 3235-3243. 10.11772/j.issn.1001-9081.2021081528
	PENG P， NI Z W， ZHU X H. Task allocation method of spatial crowdsourcing based on user satisfaction utility［J］. Journal of Computer Applications， 2022， 42（10）： 3235-3243. 10.11772/j.issn.1001-9081.2021081528
8	HE X， CORMODE G， MACHANAVAJJHALA A， et al. DPT： differentially private trajectory synthesis using hierarchical reference systems［J］. Proceedings of the VLDB Endowment， 2015， 8（11）： 1154-1165. 10.14778/2809974.2809978
9	HE X， RAVAL N， MACHANAVAJJHALA A. A demonstration of VisDPT： visual exploration of differentially private trajectories［J］. The VLDB Endowment， 2016， 9（13）： 1489-1492. 10.14778/3007263.3007291
10	XIAO Y， XIONG L. Protecting locations with differential privacy under temporal correlations［C］// Proceedings of the 22nd ACM SIGSAC Conference on Computer and Communications Security. New York： ACM， 2015： 1298-1309. 10.1145/2810103.2813640
11	WANG S， SINNOTT R， NEPAL S. Protecting the location privacy of mobile social media users［C］// Proceedings of the 2016 IEEE International Conference on Big Data. Piscataway： IEEE， 2016： 1143-1150. 10.1109/bigdata.2016.7840718
12	SWEENEY L. K-anonymity： A model for protecting privacy［J］. International Journal of Uncertainty， Fuzziness and Knowledge-Based Systems， 2002， 10（5）： 557-570. 10.1142/s0218488502001648
13	吴云乘，陈红，赵素云，等.一种基于时空相关性的差分隐私轨迹保护机制［J］.计算机学报， 2018， 41（2）： 309-322. 10.11897/SP.J.1016.2018.00309
	WU Y C， CHEN H， ZHAO S Y， et al. Differentially private trajectory protection based on spatial and temporal correlation［J］. Chinese Journal of Computers， 2018， 41（2）： 309-322. 10.11897/SP.J.1016.2018.00309
14	TERROVITIS M， POULIS G， MAMOULIS N， et al. Local suppression and splitting techniques for privacy preserving publication of trajectories［J］. IEEE Transactions on Knowledge and Data Engineering， 2017， 29（7）： 1466-1479. 10.1109/tkde.2017.2675420
15	YAO L， WANG X， WANG X， et al. Publishing sensitive trajectory data under enhanced l-diversity model［C］// Proceedings of the 2019 20th IEEE International Conference on Mobile Data Management. Piscataway： IEEE， 2019： 160-169. 10.1109/mdm.2019.00-61
16	陈思，付安民，苏铓，等. 基于差分隐私的轨迹隐私保护方案［J］. 通信学报，2021，42（9）：54-64. 10.11959/j.issn.1000-436x.2021168
	CHEN S， FU A M， SU M， et al. Trajectory privacy protection scheme based on differential privacy［J］. Journal on Communications， 2021， 42（9）： 54-64. 10.11959/j.issn.1000-436x.2021168
17	朱素霞，王蕾，孙广路. 满足本地差分隐私的分类变换扰动机制［J］. 计算机研究与发展， 2022， 59（2）： 430-439. 10.7544/issn1000-1239.20200717
	ZHU S X， WANG L， SUN G L. A perturbation mechanism for classified transformation satisfying local differential privacy［J］. Journal of Computer Research and Development， 2022， 59（2）： 430-439. 10.7544/issn1000-1239.20200717
18	DWORK C， McSHERRY F， NISSIM K， et al. Calibrating noise to sensitivity in private data analysis［C］// Proceedings of the 3rd Conference on Theory of Cryptography. Berlin： Springer， 2006： 265-284. 10.1007/11681878_14
19	袁健，王迪，高喜龙，等. 基于差分隐私的匿名组LBS轨迹隐私保护模型［J］.小型微型计算机系统， 2019， 40（2）：341-347. 10.3969/j.issn.1000-1220.2019.02.018
	YUAN J， WAND D， GAO X L， et al. Privacy protection model for anonymous group LBS trajectorybased on differential privacy［J］. Journal of Chinese Computer Systems， 2019， 40（2）：341-347. 10.3969/j.issn.1000-1220.2019.02.018
20	刘振鹏，苗德威，刘倩楠，等. k-匿名下通过本地差分隐私实现位置隐私保护［J］.计算机应用研究， 2022， 39（8）： 2469-2473.
	LIU Z P， MIAO D W， LIU Q N， et al. Location privacy protection through local differential privacy under k-anonymity［J］.Application Research of Computers， 2022， 39（8）： 2469-2473.
21	KRISHNANAND K N， GHOSE D. Glowworm swarm based optimization algorithm for multi modal functions with collective robotics applications［J］. Multiagent and Grid Systems， 2006， 2（3）： 209-222. 10.3233/mgs-2006-2301
22	REDDY D L， PUTTAMADAPPA C， SURESH H N. Merged glowworm swarm with ant colony optimization for energy efficient clustering and routing in Wireless Sensor Network［J］. Pervasive and Mobile Computing， 2021， 71： 101338. 10.1016/j.pmcj.2021.101338
23	BALASUBRAMANIAN K， ANANTHAMOORTHY N P.Improved adaptive neuro-fuzzy inference system based on modified glowworm swarm and differential evolution optimization algorithm for medical diagnosis［J］. Neural Computing and Applications， 2021， 33： 7649-7660. 10.1007/s00521-020-05507-0
24	FU K， GUO Z， YE J. Fire detection method based on improved glowworm swarm optimization-based TWSVM ［C］// Proceedings of the 2020 International Conference on Machine Learning and Big Data Analytics for IoT Security and Privacy. Cham： Springer， 2021： 862-867. 10.1007/978-3-030-62743-0_124
25	ALT H， GODAU M. Computing the Fréchet distance between two polygonal curves［J］. International Journal of Computational Geometry & Applications， 1995， 5（1/2）： 75-91.
26	McSHERRY F， TALWAR K. Mechanism design via differential privacy［C］// Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science. Piscataway： IEEE， 2007： 94-103. 10.1109/focs.2007.66
27	McSHERRY F. Privacy integrated queries： an extensible platform for privacy-preserving data analysis［C］// Proceedings of the 2009 ACM SIGMOD International Conference on Management of Data. New York： ACM， 2009： 19-30. 10.1145/1559845.1559850
28	DWORK C. A firm foundation for private data analysis［J］. Communications of the ACM， 2011， 54（1）： 86-95. 10.1145/1866739.1866758
29	倪志伟，肖宏旺，伍章俊，等.基于改进离散型萤火虫群优化算法和分形维数的属性选择方法［J］.模式识别与人工智能， 2013， 26（12）： 1169-1178. 10.3969/j.issn.1003-6059.2013.12.011
	NI Z W， XIAO H W， WU Z J，et al. Attribute selection method based on improved discrete glowworm swarm optimization and fractal dimension［J］. Pattern Recognition and Arificial Intelligence， 2013，26（12）： 1169-1178. 10.3969/j.issn.1003-6059.2013.12.011
30	KOENKER R， MACHADO J A F. Goodness of fit and related inference processes for quantile regression［J］. Journal of the American Statistical Association，1999，94（448）：1296-1310. 10.1080/01621459.1999.10473882
31	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： 32-39. 10.1109/mdm.2009.50

[1]	张治政, 张啸剑, 王俊清, 冯光辉. 结合差分隐私与安全聚集的联邦空间数据发布方法[J]. 《计算机应用》唯一官方网站, 2024, 44(9): 2777-2784.
[2]	陈廷伟, 张嘉诚, 王俊陆. 面向联邦学习的随机验证区块链构建[J]. 《计算机应用》唯一官方网站, 2024, 44(9): 2770-2776.
[3]	高瑞, 陈学斌, 张祖篡. 面向部分图更新的动态社交网络隐私发布方法[J]. 《计算机应用》唯一官方网站, 2024, 44(12): 3831-3838.
[4]	陈学斌, 单丽洋, 郭如敏. 基于差分隐私的直方图发布方法综述[J]. 《计算机应用》唯一官方网站, 2024, 44(10): 3114-3121.
[5]	徐雪冉, 杨庚, 黄喻先. 横向联邦学习中差分隐私聚类算法[J]. 《计算机应用》唯一官方网站, 2024, 44(1): 217-222.
[6]	黄硕, 李艳辉, 曹建秋. 本地化差分隐私下的频繁序列模式挖掘算法PrivSPM[J]. 《计算机应用》唯一官方网站, 2023, 43(7): 2057-2064.
[7]	陈少权, 蔡剑平, 孙岚. 动态梯度阈值裁剪的差分隐私生成对抗网络算法[J]. 《计算机应用》唯一官方网站, 2023, 43(7): 2065-2072.
[8]	尹春勇, 屈锐. 基于个性化差分隐私的联邦学习算法[J]. 《计算机应用》唯一官方网站, 2023, 43(4): 1160-1168.
[9]	王腾, 霍峥, 黄亚鑫, 范艺琳. 联邦学习中的隐私保护技术研究综述[J]. 《计算机应用》唯一官方网站, 2023, 43(2): 437-449.
[10]	张宇, 蔡英, 崔剑阳, 张猛, 范艳芳. 卷积神经网络中基于差分隐私的动量梯度下降算法[J]. 《计算机应用》唯一官方网站, 2023, 43(12): 3647-3653.
[11]	田蕾, 葛丽娜. 基于差分隐私的广告推荐算法[J]. 《计算机应用》唯一官方网站, 2023, 43(11): 3346-3350.
[12]	王利娥, 李小聪, 刘红翼. 融合知识图谱和差分隐私的新闻推荐方法[J]. 《计算机应用》唯一官方网站, 2022, 42(5): 1339-1346.
[13]	张国鹏, 陈学斌, 王豪石, 翟冉, 马征. 面向本地差分隐私的K-Prototypes聚类方法[J]. 《计算机应用》唯一官方网站, 2022, 42(12): 3813-3821.
[14]	赵乐, 张恩, 秦磊勇, 李功丽. 基于区块链的多方隐私保护k-means聚类方案[J]. 《计算机应用》唯一官方网站, 2022, 42(12): 3801-3812.
[15]	陈恒恒, 倪志伟, 朱旭辉, 金媛媛, 陈千. 基于聚类分析的差分隐私高维数据发布方法[J]. 计算机应用, 2021, 41(9): 2578-2585.

改进萤火虫群算法协同差分隐私的干扰轨迹发布

Interference trajectory publication based on improved glowworm swarm algorithm and differential privacy

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

图/表 14

参考文献 31

相关文章 15

编辑推荐

Metrics