![](https://csdnimg.cn/release/download_crawler_static/18269728/bg1.jpg)
收稿日期:20180916;修回日期:20181202 基金项目:中国博士后基金项目(2019M661260);黑龙江省自然科学基金优秀青年项目
(
YQ2019F018);黑龙江省普通本科高等学校青年创新人才培养计划资助项目(UNPYSCT2017149);佳木斯大学优秀学科团队项目(JDXKTD
2019008)
作者简介:孙悦(1995),吉林梨树人,硕士,主要研究方向为隐私保护、数据挖掘;张磊(1982),男(通信作者),副教授,博士,主要研究方向为
隐私保护、信息安全(1458516851@qq.com);李晶(1968),女,教授,硕士,主要研究方向为网络安全、数据挖掘;张震(1994),男,硕士,主要研究
方向为隐私保护、人工智能.
基于遗传算法的空间网格划分匿名算法
孙 悦
a
,张 磊
a
,李 晶
a
,张 震
b
(佳木斯大学 a.信息电子技术学院;b.机械工程学院,黑龙江 佳木斯 154007)
摘 要:隐私泄露问题已经成为阻碍基于位置的服务(locationbasedservices,LBS)进一步发展的原因。针对当
LBS用户发送查询时,用户的个人隐私可能会泄露给攻击者的问题,提出了基于遗传算法的空间网格划分的隐
私保护算法(
GAGP)。算法包括两个方法,即地图分割算法和假名生成法。地图分割算法利用遗传算法给每个
网格赋权值,再通过使用邻接网格扩展的方法,保证每个划分区域的查询频率基本相等。假名生成法是用户在
每次发送查询时使用假名来应对长期统计的攻击方式。通过实验证明所提算法与其他三种算法相比结果较好,
所以提出的方案能够有效地保护用户的隐私。
关键词:位置隐私保护;网格划分;假名;遗传算法;位置服务
中图分类号:TP309.2 文献标志码:A 文章编号:10013695(2020)04043115803
doi:10.19734/j.issn.10013695.2018.09.0753
Anonymousalgorithmforspatialmeshgenerationbasedongeneticalgorithm
SunYue
a
,ZhangLei
a
,LiJing
a
,ZhangZhen
b
(a.SchoolofInformation& ElectronicTechnology,b.SchoolofMechanicalEngineering,JiamusiUniversity,JiamusiHeilongjiang154007,
China)
Abstract:PrivacybreacheshavebecomeanobstacletothefurtherdevelopmentofLBS.ConcernsthatwhenanLBSuser
sendsaquery
,theuser’spersonalprivacymaybedisclosedtoanattacker.Thispaperproposedaschemecalledgridbased
geneticprivacyprotectionalgorithm(GAGP)thatbasedontheconceptionofweightedoptimalgeneticalgorithm.Thisscheme
involvedtwobasicprocedures:mapsegmentationandpseudonymgeneration.Mapsegmentationalgorithmusedgeneticalgo
rithmtoassignvaluestoeachgrid
,andthenusedthemethodofadjacentgridexpansiontoensurethatthequeryfrequencyof
eachpartitionareawasbasicallyequal.Kanagenerationwasawayforuserstouseapseudonymeachtimetheysentaqueryin
responsetoalongtermstatisticalattack.Theexperimentalresultsshowthattheproposedalgorithm isbetterthantheother
threealgorithms,sotheproposedschemecaneffectivelyprotecttheprivacyofusers.
Keywords:locationprivacyprotection;gridgeneration;pseudonym;geneticalgorithm;locationbasedservice
当今社会网络定位技术不断发展,位置服务(LBS)已经是
人们生活中不可或缺的服务
[1,2]
。随着 LBS给用户提供服务
的同时,也给人们带来了位置隐私泄露的问题,因此能否解决
用户隐私保护的需要也就成为了公众安心使用 LBS的重要前
提
[3~5]
。随着技术的逐步发展,出现了多种对位置数据隐私保
护 的 方 法
[6~8]
。例 如,假 位 置
[9]
、位 置 k匿 名
[10]
、空 间 加
密
[11,12]
等方法,其中使用最为广泛的是 k匿名方法
[13~16]
。最
早使用的
Random不考虑查询概率,通过随机选择生成匿名区
域的算法;后来的 GridDummy
[17]
是在满足用户隐私要求的情
况下获取匿名区域的方法;
enDLS
[18]
算法是基于从用户的历
史位置提出的虚拟位置选择的算法。但它们都仅通过用户的
位置信息来保护用户位置隐私,不能应对针对长期统计的攻击
方法以达到隐私保护的目的。为了解决上述讨论的问题,本文
提出 GAGP算法。首先用户可以进行网格的预划分,代理可以
根据所获得的历史查询数据计算出每个网格提交查询的概率,
使用基于遗传算法的方法算出权值;然后根据水平扩展方法来
扩张网格区域,保证每个查询区域的权值基本相同即每个匿名
区域的查询频率基本相同;最后采用多假名的方法防止
LBS
服务器的长期统计攻击。实验中使用真实数据对 GAGP算法
进行实验仿真与分析,并与其他三种算法进行对比,最终实验
结果验证了
GAGP算法的良好性能。
1 准备工作
11 LBS
在现有的 LBS查询方法中,用户向 LBS服务器提交查询
前,移动用户首先通过内置于智能手机的
GPS/WiFi模块来获
取自己的当前位置。智能手机直接或者通过第三方服务器将
查询内容发送到
LBS服务器,包括标志符、确切位置、兴趣和
查询范围等。最后 LBS服务器将根据用户的查询反馈 POI,如
图 1所示。为了使用户的隐私信息不受到侵害,在传统的隐私
保护算法中,选择 k-1个用户建立协作组来混淆攻击者来保
护用户的真实位置,但协作用户的位置常常很难选择,在较为
密集的地方组成的
k匿名集合的用户通常非常接近真实用户
导致匿名区域较小。使用虚拟位置可以用来解决这些问题,然
而大多数现有作品一般使用随机的方法来选择虚拟位置。如
下例所示,这并不是最好的解决方法。例如 Alice发送查询,在
随机方案中,虚拟位置是随机选择的,这时 Alice会认为自己
第 37卷第 4期
2020年 4月
计 算 机 应 用 研 究
ApplicationResearchofComputers
Vol.37No.4
Apr.2020