道路网络上基于时空相似性的连续查询隐私保护算法

潘 晓 谌伟璋 孙一格 吴 雷

1(石家庄铁道大学经济管理学院 石家庄 050043)2 (河北省高校人文社会科学重点研究基地(石家庄铁道大学) 石家庄 050043)

道路网络上基于时空相似性的连续查询隐私保护算法

潘 晓1,2谌伟璋1孙一格1吴 雷1

1(石家庄铁道大学经济管理学院 石家庄 050043)2(河北省高校人文社会科学重点研究基地(石家庄铁道大学) 石家庄 050043)

(smallpx@stdu.edu.cn)

连续查询作为基于位置服务中常见的服务类型之一，为人们的生活和工作带来了巨大的便利.最近几年，针对位置服务中的隐私保护引起了学术界研究者的广泛关注.然而，现有在道路网络上的位置隐私保护工作大多针对快照查询提供隐私保护.如果直接将这些算法应用于连续查询，由于连续查询中位置频繁更新，将同时产生连续查询隐私泄露和精确位置的泄露.由于网络拓扑的存在，移动用户的运动在一段时间内具有时空相似的特点.利用连续查询用户的时空相似性，提出了一种在道路网络上基于时空相似性的连续查询隐私保护算法.通过采取分组策略构造匿名集和K-共享机制，提出了一种启发式宽度优先用户搜索算法HBFS来构造匿名用户集，并提出了一种连续时刻内匿名路段集生成算法CSGA生成匿名路段集合，可以同时防止连续查询攻击和位置依赖攻击.最后，采用4个评价标准对算法进行了一系列实验，验证了算法的有效性.

位置隐私；连续查询；道路网络；基于位置服务；移动计算

随着移动技术的不断发展，基于位置的服务(location based services, LBSs)已广泛应用于地理导航、社交娱乐、紧急救援、广告推广等应用，其中连续查询是LBS中非常常见的一种服务形式.用户在获得LBS位置服务带来的便利的同时，个人数据也在遭受着隐私泄露的风险[1-2].具体来讲，位置查询中包含的位置信息将帮助攻击者推理用户的工作生活方式、身体健康状况等.

现有道路网络上的位置隐私保护算法多针对快照查询提供隐私保护[3-4].其基本思想是基于位置K匿名和路段L多样性模型，将K个用户的确切位置隐藏于L个不同的路段中.连续查询作为LBS常见服务之一，用户需要在查询有效期内不断更新位置.如果直接将适用于快照查询的隐私保护算法应用于连续查询，将产生连续查询攻击[5].同时，攻击者结合网络拓扑、用户在路网上的最大运动速度限制以及不同时刻的匿名位置，可以推测用户的确切位置，造成位置依赖攻击[6].然而，现有在道路网络上的位置隐私保护工作无法同时防止连续查询攻击和位置依赖攻击.

文献[7]针对路网中的连续查询攻击问题，提出了一种基于Snet层级结构的隐私保护算法.Snet层级结构基于用户转移概率，预先将路网划分成不同等级的路段子图.利用Snet层级结构可为查询用户构造具有相似运动的匿名集，从而防止连续查询攻击.然而，该方法中所使用的转移概率是基于历史数据来预测移动用户在路网中的运动情况，较难准确地构造出能够保持长期具有相似运动的匿名用户集.所以该方法难以保持较高的匿名成功率且容易出现查询代价过大的现象.

文献[8]针对路网中位置依赖攻击问题，提出了一种启发式的匿名算法.该算法以移动用户所在路网上的路段集合作为匿名区域，保证了任意连续时刻的匿名路段集合之间的网络距离不超过最大速度限制要求从而防止了位置依赖攻击.虽然该方法仅防止了路网中的位置依赖攻击，但对连续查询攻击无效.文献[8]将连续查询位置隐私概念延伸到用户的路径隐私上，针对用户的路径隐私问题提出了M-cut隐私需求.M-cut隐私需求其实是一种基于K匿名的思想，其目的是要让用户在连续时刻内的匿名路段集能够形成K条完整的路径，从而不仅能够保护用户的位置隐私而且能够保护路径隐私.但是因为其匿名集不满足文献[5]提出的要求，所以该方法对防止连续查询攻击也无效.

为了同时防止连续查询攻击和位置依赖攻击，本文提出了一种道路网路上基于时空相似性的连续查询位置隐私保护算法.综合考虑用户的空间相似性和时间相似性，基于查询用户的时空相似性采取分组策略构造匿名集，实现K-共享机制.提出了一种启发式的宽度优先用户搜索算法以防止连续查询攻击；同时，在匿名用户集不变的前提下，提出了一种连续时刻内匿名路段集生成算法以防止位置依赖攻击，在位置隐私保护与服务质量间寻找到了一种均衡.

总结本文贡献有3方面：

1) 提出了一种在道路网路上基于时空相似的连续查询隐私保护算法SCPA，有效地保护移动用户连续查询隐私;

2) 针对连续查询攻击和位置依赖攻击，分别提出了启发式宽度优先用户搜索算法HBFS和连续时刻内匿名路段集生成算法CSGA;

3) 进行了一系列实验，验证了算法的有效性.

1 相关工作

文献[5]针对连续查询隐私问题研究提出了一种基于组的方法，该方法是一种根据用户当前位置，找到和其邻近的用户构成匿名集，匿名集在查询有效期内保持不变.该方法因未考虑用户位置在未来的邻近性，容易导致匿名区域过大，影响服务质量.为了解决这一问题，文献[9]提出了基于扭曲度的方法，给出了δp-隐私模型和δq-扭曲度模型来平衡用户隐私和服务质量，该工作不仅考虑到了移动用户连续查询隐私需求，而且还考虑了移动用户的运动速度的影响，从而最小化信息扭曲度，保证了服务质量.文献[10]将文献[5]对匿名集的要求放宽，提出了查询m-不变性(m-invariance)模型，要求在用户查询有效期内，所有匿名集合的敏感属性交集最少有m个敏感属性保持不变.另外，文献[11]提出了一种基于预先划分匿名区域的连续查询位置隐私保护算法.该算法将用户的运动轨迹按时间预先分成m段，使得各时间段中的匿名区域和最小，从而在保证隐私安全的同时提高服务质量.然而，以上工作仅适用于自由空间.

路网中仅有的一些连续查询隐私保护工作中，Palanisamy等人[12-14]提出了一种基于mix-zone的隐私保护技术，其主要思想是以路网交叉路口为中心，沿着路网出口的方向建立具有自适应特点的非矩形mix-zone.每当用户进入到该mix-zone中，不作任何位置更新并更换用户进入mix-zone前的假名.由于用户在mix-zone中位置信息被隐藏同时其对应假名信息也发生了变更，增加了将同一个用户前后使用的假名关联起来的难度,从而达到了保护用户标识的目的.但因mix-zone匿名技术是一种不规则形状局部匿名的思想，其缺点是不能够保证查询用户的全局匿名.当用户处于不规则区域外时，需要发布确切位置.

Fig. 1 The road networks图1 路网结构

文献[7]针对路网中的连续查询攻击问题，受自由空间中将空间划分成不同的区域的匿名处理思想启发，提出了一种基于Snet层级结构的隐私保护方法，将路网预先划分成不同的路段子图，每一个子图为基础匿名单元，通过历史数据预测移动用户的转移概率，从而基于Snet单元构造具有相似运动趋势的匿名集.该方法中，为了抵御连续查询攻击，要求连续查询有效期内的匿名用户集之间的公共用户需满足全局K匿名要求.另外，为了抵御查询同质性攻击，要求连续查询有效期内匿名集中的查询服务属性满足全局查询L多样性要求.然而，该工作仅能防止连续查询攻击，忽略了位置依赖攻击造成的位置泄露问题.

2 预备知识

2.1 路网模型

定义1. 路网(road network). 路网被形式化地表示为一个无向图G(V,E).其中，V={n1,n2,…,nn}，表示路网各结点集合；E为边集，其中的每一条边表示为(eid,ninj,d(e),vmax)，eid为路段标识，ninj为结点序列表示该路段是从结点ni到结点nj(ni,nj∈V)，d(e)表示边的长度，vmax为该路段的最大速度限制.

如果一个移动用户u在边e上，则用户u的位置信息被形式化地表示为u={eid，dist，v}，dist为用户u所在位置距其所在边的起点之间的距离，v为用户的运动速度.路网中的2点pi和pj之间的距离为点pi到点pj之间的最短路径，可表示为SP(pi,pj).

定义2. 边到边的网络距离[8].给定2条边ei和ej，则2边之间的距离可表示为

SP(ei,ej)=min{SP(a1,b1)+

d(emin),SP(a1,b2)+d(emin),SP(a2,b1)+

d(emin),SP(a2,b2)+d(emin)}，

其中,{a1,a2}和{b1,b2}分别为边ei和ej的2邻接点，d(emin)为d(ei)和d(ej)的较小者.

以图1所示的路网结构为例，如边e14，其括号内，12表示的是边的长度，4为最大速度限制.边e14到e12之间的网络距离SP(e14,e12)=min{SP(n3,n1)+d(e14),SP(n3,n8)+d(e14),SP(n10,n1)+d(e14)，SP(n10,n8)+d(e14)}=SP(n10,n8)+d(e14)=36.

2.2 连续查询相似度

一般情况下，连续查询可以表示为2种形式：

1)已知用户当前位置和查询有效期[5,7,9]，如“查询从当前位置开始5 min内距离我最近的医院”；2)已知用户在查询有效期内的路径[15]，如“查询从人民大学路径北京大学、清华大学到达上地过程中距离我最近的饭店”.鉴于道路网络上用户运动在交叉路口运动的不可预知性，本文采用第2种形式表示道路网络上移动用户的连续查询.

为了简便，假设系统中的连续查询用户的起点和终点都为路段结点.若连续查询用户位于路段中的某个感兴趣点上，系统会自动将其转化为最近邻路段结点.

为了防止连续查询攻击，文献[5]提出在查询有效期内保证用户在每一个时刻发布的匿名集需要包含完全相同的用户.为了保证匿名集用户在查询有效期内具有较小的查询代价，需要将相似用户匿名在一起.本文从空间位置和用户速度2个方面评价移动用户的相似性.

定义4. 空间相似性ζ.已知有2个用户ui和uj，其对应的连续查询运动路径分别为pathi和pathj，连续查询的空间相似性ζ可表示为

(1)

其中，分子为路段的公共结点数，分母为路段结点数的较大值.易知ζ的取值范围为[0,1]，越接近1则表示空间越相似.

①L可以根据不同的应用和隐私需求，设置不同的语义，如L个不同路段数或L个不同敏感度的感兴趣点等.简单起见，本文中的L指的是L个不同路段.

在给出查询用户的速度相似性前，先给出查询用户u在其运动路径上的平均速度va的计算为

(2)

平均速度va的计算公式表示的是：根据用户的当前运动速度来预测用户在整个连续查询运动路径上的平均速度.其中，u.v为查询用户在当前路段上的运动速度，u.vmax为当前路段的最大限制速度.

定义5. 速度相似性η.已知有2个连续查询用户ui和uj，ui.va和uj.va为用户ui和uj在其运动路径上的平均运动速度.则查询用户间的速度相似性η可表示为

(3)

定义5中的速度相似性η仅考虑速度的大小差异.因用户的连续查询运动路径为有序结点的集合，已经反应了用户的运动方向.易知η的取值范围为[0,1]，越接近1则表示速度越相似.

定义6. 时空相似性δ.已知有2个用户ui和uj，以及他们的空间相似性ζ和速度相似性η.查询用户的时空相似性δ可表示为

δ(ui,uj)=w1×ζ+w2×η，

(4)

其中，系数w1和w2分别决定了参数ζ和η的权重，有w1,w2≥0且w1+w2=1.

易知，δ具有3种性质：

1)δ(ui,uj)≥0；

2)δ(ui,uj)=δ(uj,ui)；

3)δ(ui,uj)∈[0,1].

定义7. (K,L)-匿名模型.设CSi为用户u的匿名集，其中，CSi={Cusi，Cssi}，Cusi为匿名用户集合，Cssi为匿名路段集合，则有4个条件：

1) |Cusi|≥K；

2)Cusi=Cus1；

3) |Cssi|≥L；

4) ∀u∈Cusi，u发布Cssi作为匿名区域.

其中，条件1确保了匿名集用户满足位置K匿名模型；条件2保证了CSi在每一个时刻发布的匿名用户集包含完全相同的用户；条件3保证了每个匿名路段集满足位置L多样性①；条件4确保了每个CSi中的用户满足位置K-共享性质.

3 基于时空相似性的连续查询匿名算法

本文采用中心服务器结构[6-9]，由匿名服务器完成匿名工作.3.1节说明道路网络上基于时空相似性的连续查询隐私保护算法SCPA的主要思想，3.2节介绍启发式宽度优先用户搜索算法HBFS，3.3节为连续时刻内匿名路段集生成算法CSGA及安全分析.

3.1 SCPA主要思想

匿名服务器中的连续查询可以分为新到查询用户和活动查询用户2种.新到查询用户是指刚刚提出连续查询的用户;活动查询用户是指在连续查询有效期内发生位置更新的用户.

SCPA算法的基本思想是：若用户为新到查询用户，则基于时空相似性为查询用户分组，构造匿名用户集合Cus，并生成在初始位置的匿名路段集合Css1(具体参见3.2节).若用户为活动用户，根据已知的匿名集用户进行匿名位置Cssi的更新(具体参见3.3节).

算法1. 道路网路上基于时空相似性的连续查询隐私保护算法SCPA.

输入: 连续查询的路径、匿名度需求K、位置L多样性、路网G(V,E)；

输出: 时刻ti的匿名集Csi(1≤i≤m).

① if {Users}是新到查询用户 then

② while true do

③u从Users集合中随机选取一个用户；

④ if {Users}不为空then

⑤ 使用算法2构造匿名用户集Cus；

⑥Users=Users-Cus；

⑦ else

⑧ break；

⑨ end if

⑩ end while

3.2 启发式宽度优先用户搜素算法

在匿名初始阶段，仅有用户当前时刻的位置，所以此阶段不存在位置依赖攻击.为了防止连续查询攻击，只需找到在查询有效期内能够保持一致的匿名用户集Cus.

算法2. 启发式宽度优先用户搜索算法HBFS.

输入: 连续查询用户u、路网G(V,E)；

输出: 匿名用户集合.

①Uset=∅；

② while true do

③ 从u.edge开始在G(V,E)上执行宽度有限搜索;

④ if在u.path.size()×(1-δ)中的结点未被访问过then

⑤ for eachuserinedgedo

⑥ 计算Similarity(u,user)；

⑦ ifSimilarity≥δthen

⑧Uset.add(user)；

⑨ 更新u.K；

⑩ end if

基于定义6的时空相似性δ，本文提出了一种启发式宽度优先用户搜素算法HBFS.其主要思想是从用户当前所在位置的附近，寻找与用户具有时空相似性的用户.若能够找到满足用户K隐私需求的候选匿名用户集，则将其作为匿名用户集返回；否则以宽度优先的方式从用户当前位置进行扩展，继续寻找满足要求的用户.

表1给出了5个新到查询用户的信息，其在路网中的分布情况如图2所示(实心点).设时空相似性δ默认为0.7.随机选取u1，做启发式宽度优先遍历搜索用户.可得用户u2和u3满足时空相似性δ要求，候选匿名用户集Uset={u1,u2,u3}.又u1的隐私需求K=5，将用户u从当前位置进行宽度扩展，再次计算，可得u4，u5也满足时空相似性δ要求.最后，有Uset={u1,u2,u3,u4,u5}作为匿名用户集返回.

Table 1 Sample of Query Users

Fig. 2 Continuous queries on road networks图2 路网中的连续查询

3.3 连续时刻内匿名路段集生成算法

定义8. 边到边集的网络距离.给定一条边edge和一个边的集合Css，边edge到Css的网络距离可表示为

ND(edge,Css)=max{e∈{Css}|SP(edge,e)}，

直观上，边到边集的网络距离是边到边的网络距离的最大值.

定义9. 边集到边集的网络距离[8].给定2个边集CssA和CssB，2边集之间的网络距离可表示为

ND(CssA,CssB)=

max{∀ex∈CssA|ND(ex,CssB)}，

易知，ND(CssA,CssB)=ND(CssB,CssA).

为了防止道路网路上的连续查询最大速度位置依赖攻击，文献[8]证明了任意连续时刻的匿名路段集合之间的网络距离满足用户最大速度限制要求.然而，但未考虑用户在不同路段上具有不同的限制速度的情况.为保证匿名集的位置K-共享属性，本文在构造匿名路段集时，采用式(5)来判断路段是否满足匿名要求：

ND(Cssi,Cssi-1)≤vminΔt，

(5)

其中，Cssi和Cssi-1为2个连续时刻的匿名路段集,vmin为匿名用户集Cus中用户的最小速度，Δt为查询更新的间隔时间.

易知，对于任意2个时刻的匿名路段集，若匿名用户集中的用户能以最小速度到达最大距离位置，很明显，对于匿名集中的任意用户则都可达.所以应用式(5)可保证匿名集满足位置K-共享属性，从而能够有效防止位置依赖攻击.

算法3. 连续时刻匿名路段集生成算法CSGA.

输入: 连续查询用户u、路网G(V,E)；

输出: 匿名路段集合.

①Cssi-1=在ti-1匿名路段集合;

②Cus=用户u的匿名集用户集合;

③ 找到Cus中用户当前时刻所在路段Cssi;

④ ifCssi是一个非连通图then

⑤ 寻找连通路段加入路段集合Cssi;

⑥ end if

⑦ while |Cssi|

⑧ 选取和匿名路段集合Cssi具有公共结点的路段插入Cssi;

⑨ end while

⑩ ifND(Cssi,Cssi-1)≥vminΔtthen

继续图2中的例子，假设查询用户u1在时刻t2更新查询，此时，匿名集中的用户u1,u2,u4位于e10，u3位于边e14，u5位于边e5上.根据连续时刻内匿名路段集生成算法CSGA，可知，首先应找到连通路段e16，接着判断用户的L隐私需求.u1所在匿名集的L位置多样为5，将边e17加入匿名路段集，接着利式(5)判断匿名路段集是否满足位置依赖攻击的速度限制要求.最后，得到查询用户u1在时刻t2的匿名路段集合集Css2={e10,e14,e5,e16,e17}.

安全分析如下：SCPA算法生成的匿名集采用了降低位置粒度的方法保护位置隐私，同时满足位置K匿名模型.位置K匿名模型可以保护用户标识；L路段多样性将用户的确切位置隐藏于L个不同的路段中.定义7中的条件2确保了连续查询的匿名集包含完全相同的用户，条件4确保在匿名集中的用户均以匿名路段集Css作为匿名位置，保证了位置K-共享性，有效防止了连续查询攻击.另外，利用式(5)保证了匿名路段集之间的网络距离满足位置依赖攻击的速度限制要求，可有效防止道路网络中的位置依赖攻击.

4 实验结果与分析

4.1 实验设置

本文比较了SCPA算法和NVBA算法.NVBA算法为文献[8]中抵御路网中的连续查询最大速度攻击的位置匿名算法.所有的匿名算法用Java实现，并运行于2.4 GHz处理器、2 GB内存的Windows 7计算机上.本实验使用Thomas Brinkhoff移动对象生产器①生成模拟移动对象.生成器的输入是Oldenburg地图，包含6 105个路段结点和7 035条边.实验模拟生成10 000个模拟移动对象，设每个对象均提出连续查询，每10 s更新一次位置且默认包括100个快照位置，隐私需求K和L的默认值都为5，时空相似性δ的默认值为0.7.表2中列出了实验参数具体信息.

Table 2 Default System Settings

4.2 评价标准

采用的评价标准包括信息熵、匿名成功率、查询处理代价、匿名时间.

1) 信息熵[16-17]反映匿名算法为移动用户提供的保护强度.信息熵越大，则保护强度越大.

2) 匿名成功率是指成功匿名的移动用户在所有提出查询的移动用户中所占比例.匿名成功率越高，说明匿名算法对查询响应能力越好.

3) 匿名时间指的是一定规模移动用户的所有查询请求在多长时间内可以得到匿名处理.这是反映匿名算法好坏的重要指标之一.匿名时间越短越好，说明了匿名算法的高效性.

4) 查询处理代价是指位置经过匿名处理后，在服务提供商端由于保护隐私查询处理产生的额外代价.实验利用文献[17]中的查询代价模型，使用匿名路段集中包含的路段和开放点个数评价查询代价.查询代价越小越好.

4.3 性能评估

1) 匿名度K的影响.该部分评价了匿名度K对匿名算法性能的影响.匿名度K从3增加到15.随着匿名度K的增加，意味着每一个匿名集需要包含更多的用户.从图3(a)观察到，无论在何种设置下，SCPA的信息熵均比NVBA高.因为SCPA算法采用用户分组策略，并实现了K-用户共享.所以相比于NVBA算法能够更好地抵御连续查询攻击.图3(b)显示随着匿名需求的变化，2个匿名算法的成功率均呈现下降的趋势.因为当K值越来越大时，用户的匿名度要求变的更严格，寻找满足匿名度要求的用户集将变得越来越难.但SCPA算法的匿名成功率要比NVBA的高.

Fig. 3 Evaluation on different anonymity level K图3 2种算法在不同K匿名度需求下的比较

比较SCPA与NVBA的平均匿名时间.图3(c)显示，随着匿名度K的增加，2种算法的匿名时间也呈上升的趋势，且SCPA比NVBA的算法效率更好.因为SCPA算法采用分组构造匿名集，相比之下，NVBA需要为每一个用户重复遍历整个道路网络，将耗费更多的时间.如图3(d)所示，2种算法的查询代价均随着K的增加而增加，因为匿名集中包含了更多的路段.虽然SCPA比NVBA提供了更好的隐私保护和算法效率，但SCPA的查询代价较之NVBA高，然而，SCPA仅比NVBA大约多花费了0.03%查询代价.

2) 位置多样性L的影响.该部分评价匿位置多样性L对匿名算法性能的影响.路段差异性需求L增加意味着用户的位置隐私需求更加严格，L亦从3增加到15.从图4(a)观察到，SCPA的信息熵在所有设置上均比NVBA高，平均要高出5倍，这说明SCPA比NVBA提供了更安全的隐私保护强度.从图4(b)中，可以看到NVBA的匿名成功率随着L的增大逐渐下降，相比NVBA，SCPA算法的匿名成功率要比NVBA的高，且SCPA具有更稳定的匿名成功率.从图4(c)可以看出，对于L的增加，SCPA的平均匿名时间并没有太大变化，从整体情况来看，SCPA比NVBA的算法效率更好.虽然SCPA比NVBA提供了更好的隐私保护和较好的算法效率，但SCPA的查询代价较之NVBA高，从图4(d)看出，2种算法的查询代价均随着L的增加而增加，因为匿名集中包含了更多的路段.

3) 时空相似性δ的影响.该部分对系统参数时空相似性δ进行实验评估，以验证时空相似性δ对SCPA算法的性能的影响.由于NVBA不涉及时空相似性，所以此节仅对SCPA进行了实验验证.δ值从0.5变化到0.9.

Fig. 4 Evaluation on different location diversity L图4 2种算法在不同路段差异性L下的比较

Fig. 5 Evaluation on different δ of SCPA Algorithm图5 SCPA算法在不同时空相似性δ下的性能评估

从图5(a)和5(b)中，可以看到，在δ取值为0.7之前，信息熵和匿名成功率基本保持不变，但当δ大于0.7后信息熵和匿名成功率都逐渐下降.因为随着δ值变大，将很难为所有查询用户构造具有高时空相似性的匿名集,从而导致用户的平均信息熵和成功率都呈下降趋势.图5(c)显示，随着δ的增加，平均匿名时间先增加，在δ值为0.8时达到最大，之后急剧下降.因为随着时空相似性δ的增加，在为查询用户做启发式宽度优先用户搜索时，将需要花费更多的时间.然而，当δ值达到一定值时，如0.9时，因系统中大部分查询用户难以找到具有如此高相似的匿名用户集，所以在为用户生成匿名路段集时将花费相对较少的时间.由图5(d)中所示，随着δ的增加，查询代价逐渐递减.因为δ越大，表明查询用户越相似，匿名用户在路网上将越集中，所以构造匿名路段集时所产生的开放点个数将相对减少，从而查询代价变小.

5 结 论

本文研究了一种在道路网络上基于时空相似性的连续查询隐私保护算法SCPA.现有在道路网络上的位置隐私保护工作大多针对快照查询提供隐私保护，当移动用户的位置发生连续更新时，容易遭受连续查询攻击和位置依赖攻击.为了解决此问题，本文基于查询用户的时空相似性采取分组构造匿名集实现K-共享机制，并提出了一种启发式的宽度优先用户搜索算法和连续时刻内匿名路段集生成算法.最后通过一系列实验，验证了算法的有效性，匿名算法可保证平均95%以上的匿名成功率，且平均匿名时间为18 ms.

[1]Wang Lu, Meng Xiaofeng. Location privacy preservation in big data era: A survey[J]. Journal of Software, 2014, 25(4): 693-712 (in Chinese)(王璐, 孟小峰. 位置大数据隐私保护研究综述[J]. 软件学报, 2014, 25(4): 693-712)

[2]Terrovitis M, Liagouris J, Mamoulis N, et al. Privacy preservation by disassociation[J]. Proceedings of the VLDB Endowment, 2012, 5(10): 944-955

[3]Chow C, Mokbel M F, Bao J, et al. Query-aware location anonymization for road networks[J]. Geoinformatical, 2010, 15(3): 571-607

[4]Wang Ting, Liu Ling. Privacy aware mobile services over road networks[C]Proc of the 35th Int Conf on VLDB. New York: ACM, 2009: 1042-1053

[5]Chow C Y, Mokbel M F. Enabling private continuous queries for revealed user locations[C]Proc of the 10th Int Conf on SSTD. Berlin: Springer, 2007: 258-275

[6]Xu Jianliang, Tang Xueyan, Hu Haibo, et al. Privacy-conscious location-based queries in mobile environments[J]. IEEE Trans on Parallel & Distributed Systems, 2010, 21(3): 313-326

[7]Wang Yong, Xia Yun, Hou Jie, et al. A fast privacy-preserving framework for continuous location-based queries in road networks[J]. Journal of Network & Computer Applications, 2015, 53(3): 57-73

[8]Wang Yilei, Zhou Hao, Wu Yingjie, et al. Preserving location privacy for location-based services with continuous queries on road network[C]Proc of the 7th Int Conf on Computer Science & Education. Los Alamitos, CA: IEEE Computer Society, 2012: 822-827

[9]Pan Xiao, Meng Xiaofeng, Xu Jianliang. Distortion based anonymity for continuous queries in location based mobile services[C]Proc of the ACM SIGSPATIAL, New York: ACM, 2009: 256-265

[10]Dewri R, Ray I, Ray I, et al. Query m-Invariance: Preventing query disclosures in continuous location-based services[C]Proc of the 11th Int Conf on Mobile Data Management. Piscataway, NJ: IEEE, 2010: 95-104

[11]Shin H, Vaidya J, Atluri V, et al. Ensuring privacy and security for LBS through trajectory partitioning[C]Proc of the 11th Int Conf on Mobile Data Management. Piscataway, NJ: IEEE, 2010: 224-226

[12]Palanisamy B, Liu L, Lee K, et al. Anonymizing continuous queries with delay-tolerant mix-zones over road networks[J]. Distributed & Parallel Databases, 2014, 32(1): 91-118

[13]Palanisamy B, Liu L. MobiMix: Protecting location privacy with mix-zones over road networks[C]Proc of Int Conf on ICDE. Piscataway, NJ: IEEE, 2011: 494-505

[14]Palanisamy B, Liu Ling, Lee K, et al. Location privacy with road network mix-zones[C]Proc of Int Conf on MSN. Piscataway, NJ: IEEE, 2012: 124-131

[15]Tao Yufei, Papadias D, Shen Qiongmao. Continuous nearest neighbor search[C]Proc of the 28th Int Conf on VLDB. New York: ACM, 2002: 287-298

[16]Zeng Zhihao, Sun Qi, Yao Bei, et al. A virtual trajectory privacy protection method for continuous queries[J]. Science Technology and Engineering, 2014, 33(1): 93-98 (in Chinese)(曾志浩, 孙琪, 姚贝, 等. 一种面向连续查询的虚拟轨迹隐私保护方法[J]. 科学技术与工程, 2014, 33(1): 93-98)

[17]Pan Xiao, Chen Weizhang, Wu Lei, et al. Protecting personalized privacy against sensitivity homogeneity attacks over road networks in mobile services[J]. Frontiers of Computer Science, 2016, 10(2): 370-38

Pan Xiao, born in 1981. PhD. Associate professor at Shjiazhuang Tiedao University. Member of CCF. Her main research interests include mobile computing, social network, and privacy protection.

Chen Weizhang, born in 1992. Master. His main research interests include data mining, data management on moving objects and privacy-aware computing.

Sun Yige, born in 1996. Undergraduate. Her main research interests include data management on moving objects and privacy-aware computing.

Wu Lei, born in 1980. Master. Lecturer at Shjiazhuang Tiedao University. Member of the Soft Science Research Institute on Engineering and Construction Management in Hebei Province. His main research interests include data management on moving objects and location based social network.

2015年《计算机研究与发展》高被引论文TOP10

排名论文信息1王继业,孟坤,曹军威,程志华,高灵超,林闯.能源互联网信息技术研究综述[J].计算机研究与发展,2015,52(5):1109-1126WangJiye,MengKun,CaoJunwei,ChengZhihua,GaoLingchao,LinChuang.InformationTechnologyforEnergyInternet:ASurvey[J].JournalofComputerResearchandDevelopment,2015,52(5):1109-11262张焕龙,胡士强,杨国胜.基于外观模型学习的视频目标跟踪方法综述[J].计算机研究与发展,2015,52(1):177-190ZhangHuanlong,HuShiqiang,YangGuosheng.VideoObjectTrackingBasedonAppearanceModelsLearning[J].JournalofComputerResearchandDevelopment,2015,52(1):177-1903王元卓,贾岩涛,刘大伟,靳小龙,程学旗.基于开放网络知识的信息检索与数据挖掘[J].计算机研究与发展,2015,52(2):456-474WangYuanzhuo,JiaYantao,LiuDawei,JinXiaolong,ChengXueqi.OpenWebKnowledgeAidedInformationSearchandDataMining[J].JournalofComputerResearchandDevelopment,2015,52(2):456-4744段洁,胡清华,张灵均,钱宇华,李德玉.基于邻域粗糙集的多标记分类特征选择算法[J].计算机研究与发展,2015,52(1):56-65DuanJie,HuQinghua,ZhangLingjun,QianYuhua,LiDeyu.FeatureSelectionforMulti-LabelClassificationBasedonNeighborhoodRoughSets[J].JournalofComputerResearchandDevelopment,2015,52(1):56-655唐成华,刘鹏程,汤申生,谢逸.基于特征选择的模糊聚类异常入侵行为检测[J].计算机研究与发展,2015,52(3):718-728TangChenghua,LiuPengcheng,TangShensheng,XieYi.AnomalyIntrusionBehaviorDetectionBasedonFuzzyClusteringandFeaturesSelection[J].JournalofComputerResearchandDevelopment,2015,52(3):718-7286辛宇,杨静,汤楚蘅,葛斯乔.基于局部语义聚类的语义重叠社区发现算法[J].计算机研究与发展,2015,52(7):1510-1521XinYu,YangJing,TangChuheng,GeSiqiao.AnOverlappingSemanticCommunityDetectionAlgorithmBasedonLocalSemanticCluster[J].JournalofComputerResearchandDevelopment,2015,52(7):1510-15217吴章玲,金培权,岳丽华,孟小峰.基于PCM的大数据存储与管理研究综述[J].计算机研究与发展,2015,52(2):343-361WuZhangling,JinPeiquan,YueLihua,MengXiaofeng.ASurveyonPCM-BasedBigDataStorageandManagement[J].JournalofComputerResearchandDevelopment,2015,52(2):343-3618秦兵,刘安安,刘挺.无指导的中文开放式实体关系抽取[J].计算机研究与发展,2015,52(5):1029-1035QinBing,LiuAnan,LiuTing.UnsupervisedChineseOpenEntityRelationExtraction[J].JournalofComputerRe-searchandDevelopment,2015,52(5):1029-10359陈世敏.大数据分析与高速数据更新[J].计算机研究与发展,2015,52(2):333-342ChenShimin.BigDataAnalysisandDataVelocity[J].JournalofComputerResearchandDevelopment,2015,52(2):333-34210马思伟.AVS视频编码标准技术回顾及最新进展[J].计算机研究与发展,2015,52(1):27-37MaSiwei.HistoryandRecentDevelopmentsofAVSVideoCodingStandards[J].JournalofComputerResearchandDevelopment,2015,52(1):27-37

数据来源：CSCD，中国知网；统计日期：2016-12-05

Continuous Queries Privacy Protection Algorithm Based on Spatial-Temporal Similarity Over Road Networks

Pan Xiao1,2, Chen Weizhang1, Sun Yige1, and Wu Lei1

1(SchoolofEconomic&Management,ShijiazhuangTiedaoUniversity,Shijiazhuang050043)2(KeyResearchBaseforHumanitiesandSocialSciencesinHebeiProvince(ShijiazhuangTiedaoUniversity),Shijiazhuang050043)

Continuous queries are one of the most common queries in location-based services (LBSs), although particularly useful, such queries raise serious privacy concerns. However, most of the existing location cloaking approaches over road networks are only applicable for snapshots queries. If these algorithms are applied on continuous queries directly, due to continuous location frequently updated, continuous query privacy will be disclosed. Moreover, combined with the network topology and other network parameters (limited speed etc.), the attackers are knowledgeable, which can easily lead to precise location privacy disclosure. We observe that mobile objects have similar spatial and temporal features due to the existing of network topology. In order to resist continuous query attacks and location-dependent attacks simultaneously, we propose a continuous queries privacy protection algorithm based on spatial-temporal similarity over road networks. The algorithm adopts user grouping andK-sharing privacy requirement strategies to constitute cloaking user sets, which is used to resist continuous queries attack. Then, with the same premise of cloaking user sets, a continuous cloaking segment sets generating algorithm is proposed to resist location-dependent attacks, which makes a balance between location privacy and service quality. Finally, we conduct series of experiments to verify our algorithm with four evaluation measures, and the experimental results show the effectiveness of the proposed algorithm.

location privacy; continuous query; road networks; location based services (LBSs); mobile computing

2016-08-02；

2016-10-10

国家自然科学基金项目(61303017,61502146)； 河北省自然科学基金项目(F2014210068)； 河北省教育厅青年基金项目(QN2016083)；河北省高等学校人文社会科学研究项目(GH161079)；石家庄铁道大学第四届优秀青年科学基金项目(Z661250444)； 河北省研究生创新资助项目(Z99910)；国家级大学生创新创业训练计划项目(201510107013, 201610107003) This work was supported by the National Natural Science Foundation of China (61303017,61502146), the Natural Science Foundation of Hebei Province (F2014210068), the Young Scholars Project of the Hebei Provincial Education Department (QN2016083), the Project of Humanities and Social Sciences for the Colleges in Hebei Province (GH161079), the Fourth Outstanding Youth Foundation of Shijiazhuang Tiedao University (Z661250444), the Graduate Innovative Foundation of Hebei Province(Z99910), and the College Innovative Training Program Foundation of China(201510107013, 201610107003).

TP391