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

doi:10.11772/j.issn.1001-9081.2023030259

Journal of Computer Applications ›› 2024, Vol. 44 ›› Issue (2): 496-503.DOI: 10.11772/j.issn.1001-9081.2023030259

Special Issue: 网络空间安全

• Cyber security • Previous Articles Next Articles

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)

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

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

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

通讯作者: 倪志伟
作者简介:彭鹏（1988—），男，安徽巢湖人，讲师，博士研究生，CCF会员，主要研究方向：智能优化、空间众包
朱旭辉（1991—），男，安徽阜阳人，讲师，博士，主要研究方向：深度学习、智能计算
陈千（1991—），男，安徽合肥人，博士研究生，主要研究方向：数据安全、隐私计算。
基金资助:
国家自然科学基金资助项目(71901001);安徽省自然科学基金资助项目(1908085QG298)

Abstract

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

摘要：

针对历史轨迹加噪发布干扰轨迹时数据集的冗余问题和轨迹形状相似带来的隐私泄露风险，提出轨迹数据先约简后泛化再进行差分隐私加噪的基于改进萤火虫群优化求解的干扰轨迹发布保护机制（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%，说明所提方法发布的干扰轨迹可用性和稳定性更好。

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

CLC Number:

TP301.6

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.

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

Figures/Tables 14

Fig.1 Different interference tracks

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-匿名生成的点数
ε	差分隐私预算

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-匿名生成的点数
ε	差分隐私预算

Fig.2 Framework of IGSO-SDTP method

Fig. 3 Trajectories of Geo1~Geo6

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

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

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

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

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

Fig. 4 Performance comparison of different methods

Tab. 7 Analysis of radius r

平均

加权距离

平均

加权距离

平均

加权距离

Fig. 5 Analysis of parameter k

Fig. 6 Analysis of parameter p

Fig. 7 Analysis of parameter g

References 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]	Zhizheng ZHANG, Xiaojian ZHANG, Junqing WANG, Guanghui FENG. Federated spatial data publication method with differential privacy and secure aggregation [J]. Journal of Computer Applications, 2024, 44(9): 2777-2784.
[2]	Tingwei CHEN, Jiacheng ZHANG, Junlu WANG. Random validation blockchain construction for federated learning [J]. Journal of Computer Applications, 2024, 44(9): 2770-2776.
[3]	Rui GAO, Xuebin CHEN, Zucuan ZHANG. Dynamic social network privacy publishing method for partial graph updating [J]. Journal of Computer Applications, 2024, 44(12): 3831-3838.
[4]	Xuebin CHEN, Liyang SHAN, Rumin GUO. Review of histogram publication methods based on differential privacy [J]. Journal of Computer Applications, 2024, 44(10): 3114-3121.
[5]	Xueran XU, Geng YANG, Yuxian HUANG. Differential privacy clustering algorithm in horizontal federated learning [J]. Journal of Computer Applications, 2024, 44(1): 217-222.
[6]	Shuo HUANG, Yanhui LI, Jianqiu CAO. PrivSPM： frequent sequential pattern mining algorithm under local differential privacy [J]. Journal of Computer Applications, 2023, 43(7): 2057-2064.
[7]	Shaoquan CHEN, Jianping CAI, Lan SUN. Differential privacy generative adversarial network algorithm with dynamic gradient threshold clipping [J]. Journal of Computer Applications, 2023, 43(7): 2065-2072.
[8]	Chunyong YIN, Rui QU. Federated learning algorithm based on personalized differential privacy [J]. Journal of Computer Applications, 2023, 43(4): 1160-1168.
[9]	Teng WANG, Zheng HUO, Yaxin HUANG, Yilin FAN. Review on privacy-preserving technologies in federated learning [J]. Journal of Computer Applications, 2023, 43(2): 437-449.
[10]	Yu ZHANG, Ying CAI, Jianyang CUI, Meng ZHANG, Yanfang FAN. Gradient descent with momentum algorithm based on differential privacy in convolutional neural network [J]. Journal of Computer Applications, 2023, 43(12): 3647-3653.
[11]	Lei TIAN, Lina GE. Advertising recommendation algorithm based on differential privacy [J]. Journal of Computer Applications, 2023, 43(11): 3346-3350.
[12]	Li’e WANG, Xiaocong LI, Hongyi LIU. News recommendation method with knowledge graph and differential privacy [J]. Journal of Computer Applications, 2022, 42(5): 1339-1346.
[13]	Le ZHAO, En ZHANG, Leiyong QIN, Gongli LI. Multi-party privacy preserving k-means clustering scheme based on blockchain [J]. Journal of Computer Applications, 2022, 42(12): 3801-3812.
[14]	Guopeng ZHANG, Xuebin CHEN, Haoshi WANG, Ran ZHAI, Zheng MA. K-Prototypes clustering method for local differential privacy [J]. Journal of Computer Applications, 2022, 42(12): 3813-3821.
[15]	CHEN Hengheng, NI Zhiwei, ZHU Xuhui, JIN Yuanyuan, CHEN Qian. Differential privacy high-dimensional data publishing method via clustering analysis [J]. Journal of Computer Applications, 2021, 41(9): 2578-2585.

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

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

RichHTML

PDF

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 14

References 31

Related Articles 15

Recommended Articles

Metrics