2018, Vol. 29
近年来, 随着GPS通信技术的发展和移动用户的急速增长, 基于位置的服务(LBS)得到了广泛应用[1].通过具有定位功能的智能移动设备, 人们可以随时随地获得方便快捷的位置服务.在众多位置服务中, 与兴趣点(point of interest, 简称POI)有关的查询一直是广泛使用的一项服务.兴趣点是指电子地图上的某类特殊建筑, 如医院、学校、银行等, 典型的兴趣点查询包括“离我最近的K个医院”“距我K公里以内的银行”等.人们在享受位置服务带来便利的同时, 也面临隐私泄露的风险.如何在不影响服务质量的前提下保护用户的位置隐私, 成为学术界研究的热点.
近年来的LBS隐私保护研究大多集中在欧式空间中[2-8], 路网环境下的位置k-匿名方案大多是基于网络拓张[9-12]的方法, 其思想是:从用户所在位置按照距离从近到远向外拓张, 直至匿名集中的用户数等于k时停止.该方法存在着匿名集不满足相互性[4]的缺陷, 如图 1所示, 用二元组表示边的长度和用户数, 在k=5且路段总长度len=18的条件下, 即构造的匿名集中超过k个用户、总路段长度超过len的隐私保护要求下, 通过网络拓张构造的用户u1的匿名集AS(u1)={(p1, p8), (p1, p4)}, 用户u2的匿名集AS(u2)={(p1, p4), (p4, p6), (p6, p9)}.已知u2在路段(p1, p4)上, u1在路段(p1, p8)上, 显然, u2在u1的匿名集中, u1却不在u2的匿名集中.同时, 由于网络拓张方法从用户所在位置按照距离大小向外进行拓张, 当路网人数众多时, 在用户所在路段或用户附近为数不多的路段内便可达到k匿名, 产生的匿名区域极小, 对用户的真实位置构成极大威胁.此外, 路网上的隐私保护方法并没有考虑到路网概率信息(如不同区域的历史查询频率), 因此攻击者可能根据路网的分布情况、历史查询统计情况来推测用户的实际位置.
|
Fig. 1 k-anonymous method on road network 图 1 路网上的k-匿名方法 |
当前, 路网环境下的位置隐私保护方法主要存在以下问题:(1)未考虑路网中的路段历史查询概率等信息; (2)生成较小的匿名区域; (3)匿名集不满足相互性.为了解决上述问题, 本文在路网上根据兴趣点划分网络Voronoi单元, 利用Hilbert曲线填充路网空间, 并根据兴趣点的Hilbert值对其排序, 在与用户具有相同查询频率的网络Voronoi单元内选择与用户相对位置相同的路段生成假位置.本文生成的假位置具有与用户真实位置查询频率相同、位置分散的特点, 且匿名集内各路段相互匿名, 具有相互性.本文的主要贡献如下:
1) 以兴趣点为种子节点, 将路网划分为独立不重叠的网络Voronoi单元, 通过考虑每个网络Voronoi单元的历史查询频率, 实现位置k-匿名;
2) 利用Hilbert曲线对兴趣点排序, 并按固定间隔选取假位置所在的k-1个网络Voronoi单元, 使得生成的假位置分布广泛, 避免了传统匿名方法生成较小的匿名区, 能够形成较大的匿名区域, 从而抵制攻击者的攻击(如单一路段攻击[13]、区域攻击[7]);
3) 通过将历史查询频率相同的网络Voronoi单元封装成桶, 然后对每个网络Voronoi单元内的路段进行统一划分, 从而使匿名集满足相互性;
4) 通过理论分析, 证实匿名算法可以抵御重放攻击和推断攻击, 通过对比实验, 验证生成的假位置能够有效保护用户的真实位置.
本文第1节简单描述隐私保护领域的研究成果及不足之处.第2节介绍网络Voronoi图、Hilbert空间填充曲线等本文方法需要用到的背景知识.第3节描述本文的攻击模型及系统框架.第4节详细说明隐私保护方法的算法及步骤.第5节对本文提出的隐私保护方法进行安全分析.第6节给出实验结果及分析.第7节总结全文, 并指出未来值得关注的研究方向.
1 相关工作在保护位置隐私方面, 研究者提出了大量的研究方法.其中, Gruteser等人[2]第1次提出位置k-匿名模型, 该模型指出:如果在[t1, t2]时间间隔内, 出现在[x1, x2], [y1, y2]区域中的除了移动用户的位置还包含其他k-1个用户的位置, 那么这个区域就满足了k匿名, 该三元组([x1, x2], [y1, y2], [t1, t2])就会被发送给服务器, 使得攻击者无法将用户的真实位置与其他k-1个位置区分开来.目前, 根据隐私保护算法的应用环境, 可以分为基于欧式空间的位置隐私保护方法和基于路网的位置隐私保护方法.
在欧式空间中, Kido等人[3]提出了假位置(也称哑元)方法, 即:通过匿名算法添加k-1个假位置, 将包括用户真实位置在内的k个位置发送给位置服务商, 以实现k匿名的方法.本文所提的位置隐私方案基于假位置方法. Niu等人[3]提出了Dummy-Location Selection(DLS)方法, 该方法通过最大熵原则选择假位置, 保证了k个位置的位置分散度; 同时, 该方法构造假位置时考虑到用户与假位置之间查询频率的差异性可能导致位置暴露、不能有效地实现k-匿名的问题.图 2中, 平面区域共计有100个历史查询, 根据每个区域的历史查询数量占所有区域历史查询数量的比例, 统计出每个区域的查询频率.由于每个区域查询热度的差异, 导致各个区域的查询频率的差异, 用户所在区域的历史查询频率为0.0163, 添加的虚假位置的查询频率与用户所在位置相差甚远, 攻击者很容易利用这种差异, 将查询频率为0和0.0016的假位置排除掉.由于DLS方法是在2k个候选区域中枚举出k个具有最大熵的区域, 因此其具有复杂度高、迭代慢、匿名集不具有相互性的缺点.
|
Fig. 2 Selection of dummy locations in Euclidean space 图 2 欧式空间的假位置选择方法 |
路网环境下, 基于网络拓张的思想实现k-匿名是位置隐私保护领域的经典算法.然而路网结构复杂、数据庞大, 传统的网络拓张方法需要在线对整个路网进行扫描遍历, 给匿名处理和网络通信带来巨大压力.同时, 该方法不能保证匿名集的相互性, 攻击者很容易根据多次查询所构造的交集判断出用户的真实位置.在网络拓张的基础上, Mouratidis等人[9]提出了基于图遍历将边上的用户进行分装的方法.其主要思想是:将路网中的点或边进行全局编号排序, 根据编号大小, 把路网上的所有用户按每k个用户分装一个桶的方式进行分装.如图 3所示, 箭头的顺序代表边的遍历顺序, 路网中有10个用户, 假设k=2, 则会将用户分入5个桶中, b1={u1, u2}, b2={u3, u4}, b3={u5, u6}, b4={u7, u8}, b5={u9, u10}.该分装方法有效地实现了相互性, 即, 在一个桶中的用户匿名集总是相等的, 但是也存在两个问题:(1)存在单一路径问题, 即, k个用户均在一条路段上, 如在一个桶中的用户u1, u2都在边(p14, p8)上, 实际上就是向攻击者暴露匿名集内的用户真实所在路段就是(p14, p8); (2)在同一路段上的用户产生的匿名集不同, 易遭受推断攻击[13], 如在同一路段(p5, p4)上的用户u6, u7, 分属于b3, b4两个桶, 其产生的匿名集分别为AS(u6)=AS(u5)=AS(b3)={(p2, p5), (p5, p4)}, AS(u7)=AS(u8)=AS(b4)={(p5, p4), (p4, p6)}, 则根据排除法可以判断出u5在(p2, p5)上, u8在(p4, p6)上.
|
Fig. 3 Location preserving method based on graph traversal 图 3 基于图遍历的位置保护方法 |
目前, 基于假位置的方法大多只适用于欧式空间, 但是路网环境更适合基于兴趣点的位置服务.因此, 本文提出的隐私保护方法旨在路网环境下生成假位置, 并且使添加的假位置的查询频率与用户所在区域的查询频率保持一致、假位置之间位置分散度高且匿名路段之间具有相互性.
2 模型与框架 2.1 攻击模型在位置隐私保护领域, 攻击者可分为被动攻击者[6]和主动攻击者[14].被动攻击者主要通过窃听实体之间的通信来获取查询信息.在本文的攻击模型中, 假设网络通信信道是安全的, 并且实体之间的通信安全可以通过已有的加密策略实现.而主动攻击者则可以通过恶意攻击LBS服务器, 从而获得隐私保护算法的工作机制和历史查询概率.基于LBS服务器拥有最多的背景知识, 本文假设LBS服务器是主动攻击者.提出的匿名算法的安全目标是可以抵御主动攻击者的重放攻击[10]和推断攻击[7], 并使得主动攻击者识别真实用户位置的概率不大于1/k.
2.2 系统框架在传统的基于客户端-服务器(CS)的隐私保护框架中, 由客户端完成对历史查询信息的统计及对位置的匿名工作, 并且需要由客户端精炼LBS返回的查询结果.目前, 基于假位置的隐私保护方法均采用CS框架, 大量的计算增加了客户端的计算消耗, 从而降低了服务质量.本文的隐私保护框架如图 4所示.该框架主要通过可信的第三方匿名服务器来连接用户和LBS服务器并实现匿名算法.与CS框架相比, 基于第三方匿名服务器的隐私保护结构能够在很大程度上缓解客户端的计算压力.同时, 由于匿名服务器执行了查询结果的精炼过程, 能够快速响应查询服务请求.
用户对兴趣点的查询可以用四元组 < uid, t, loc, content>表示, 其中, 每个元组分别表示用户ID、查询时间、用户位置信息、查询内容.如图 4所示, 当用户发起查询请求时, 假位置计算模块将产生k-1个假位置, 与用户的真实位置组成位置匿名区, 并将生成的位置匿名查询 < uid, t, CR, content>发送给LBS服务器, 其中, CR表示位置匿名区, 由包含用户真实位置在内的k个位置组成.匿名服务器中的历史信息存储模块用来记录历史查询点的位置信息, 该模块是为了保证匿名服务器根据匿名算法找到k-1个匿名路段后, 不是在这些路段上随机产生假位置, 而是选取该路段上的历史查询点作为匿名位置, 避免了在路段中人迹稀少的区域选取假位置, 从而导致具有历史位置信息的攻击者进行推断攻击.为了使生成的假位置更具真实性, 规定假位置计算模块总是在k-1条路段上, 提取最近时刻的历史查询点的位置作为假位置.LBS服务器进行查询处理后, 将结果返回给匿名服务器, 匿名服务器通过查询求精模块, 将用户的真实查询结果提取出来并返回给用户.
|
Fig. 4 Overall framework of location privacy preserving 图 4 位置隐私保护框架 |
3 支持分散性与相互性的路网表示
通常采用无向图G=(V, E)表示路网, E={e1, e2, …, em}表示路网网络拓扑中的路段, V={p1, p2, …, pn}表示路段的交叉点, 任意两点距离采用的是路网距离.设V中有t个顶点被用户标记为兴趣点.
本文提出的位置隐私保护方法旨在保护路网环境下兴趣点查询的用户位置.为了支持基于兴趣点查询的用户位置匿名的分散性与相互性, 利用网络Voronoi图理论[15]对路网进行划分, 以满足匿名的分散性.利用Hilbert空间填充曲线(Hilbert curve)[16]对兴趣点进行排序, 以满足匿名的相互性.本文中使用的符号见表 1.
|
Table 1 Symbol definition 表 1 符号定义 |
3.1 基于网络Voronoi图的路网划分
路网环境下, 以兴趣点作为种子节点构造路网上的网络Voronoi图, 用于处理相关的兴趣点查询服务.具体地, 需要将路网划分为独立不重叠的子区域, 并在子区域内寻找假位置.因此, 首先需要将路网表示成以兴趣点为种子节点的网络Voronoi图, 然后将路网划分为独立且互不重叠的网络Voronoi单元.通过该方法生成的假位置总是位于不同的子区域内且彼此距离分散, 能够形成较大的匿名区域.本文的相关定义如下.
给定两个兴趣点pi和pj, 如果它们在G上的最短路径上不存在其他兴趣点, 则在G中必然存在子区域G’, 使得G’中任意一点到pi的路网距离都小于等于该点到pj的路网距离, 称G’为pi对于pj的支配区域, 记为Dom(pi, pj).
定义1(兴趣点的网络Voronoi单元(NVC)).兴趣点pi的Voronoi单元是路网上一组路段或子路段的集合, 记做NVC(pi).在这个集合内的路段上的任意一点到pi的距离都必须小于等于该点到其他兴趣点的距离, 即, NVC(pi)是pi相对于其他兴趣点的支配区域的并集.
定义2(网络Voronoi图).由所有兴趣点P的网络Voronoi单元共同组成的图称为该网络的网络Voronoi图, 记为
| $ NVD\left( P \right)=\left\{ NVC\left( {{p}_{1}} \right), \ldots, NVC\left( {{p}_{t}} \right) \right\} $ | (1) |
定义3(兴趣点pi与pj之间的边界点).兴趣点pi与pj之间的边界点是位于pi与pj最短路径上的某个位置点, 记为b(pi, pj).它将该条最短路径分为两部分:一部分属于兴趣点pi的Voronoi单元, 而另一部分属于兴趣点pj的Voronoi单元.
性质1.兴趣点pi与pj之间的边界点是这两个兴趣点之间最短路径上的中心点, 即:边界点b(pi, pj)在pi与pj的最短路径上, 且b(pi, pj)到pi的距离与b(pi, pj)到pj的距离相等.
由于兴趣点的分布是固定的, 因此, 以兴趣点为种子节点的网络Voronoi单元就是唯一确定的, 由各个独立不重叠的网络Voronoi单元组成的网络Voronoi图也是唯一确定的.
如图 5所示, {p1, ..., p16}为路网上的路段交叉点, 其中, 黑色节点为兴趣点P={p1, p2, p9, p10, p14, p16}, 灰色节点为非兴趣点, {b1, ..., b12}是兴趣点之间的边界点.根据定义2, NVD(P)由NVC(p1), NVC(p2), NVC(p9), NVC(p10), NVC(p14), NVC(p16)组成, 其中, NVC(p1)是由b1, b2, b6围成的左上角区域, NVC(p2)是由b1, b3, b5围成的右上角区域, NVC(p9), NVC(p10), NVC(p14), NVC(p16)等依次排开.
|
Fig. 5 Network Voronoi diagram 图 5 网络Voronoi图 |
3.2 基于Hilbert空间填充曲线的兴趣点索引
定义4(相互性[4]).匿名集的相互性是指同一匿名集内的任意两个用户ui和uj, 其构造的匿名集分别是ASi和ASj, 如果ASi=ASj, 则匿名集满足相互性.
在假位置方法构造k匿名的情况下, 用户ui和uj分别构造的匿名集分别由k条路段组成, 匿名集具有相互性, 即:当用户uj所在路段出现在用户ui的匿名集中时, 对用户uj构造的匿名集与用户ui的匿名集完全相同.
大部分支持路网的k匿名方法不具有相互性, 攻击者很容易通过多次查询构造的匿名集, 推断出真正的用户位置[16].文献[17]虽然提出了支持路网并保证相互的匿名方法, 但并没有实现绝对的相互性.具体地, 当用户ui出现在uj的匿名集中时, 若不能保证uj也出现在ui的匿名集中, 则会增大uj, ui的匿名集差异性, 使uj, ui的匿名集完全不同, 以逃避攻击者的推断攻击.该方法需要在生成匿名集后再次检测其是否满足相互性, 若不满足则需要生成完全不同的匿名集, 这无疑降低了在线匿名的性能.文献[18]已经证明:利用Hilbert曲线遍历顺序, 将匿名位置封装成桶来实现k匿名的方法能够满足相互性, 可以抵御推断攻击.
定义5(Hilbert空间填充曲线(Hilbert curve)[19]). Hilbert空间填充曲线定义为S维空间RS与一维空间R之间的一一映射, 记作H:RS→R.若点p∈RS, 则H(p)∈R, H(p)称为点p的Hilbert值.对于点集{p1, p2, …, pn}, 有:
| $ H\left\{ {{p}_{1}}, {{p}_{2}}, \ldots, {{p}_{n}} \right\}=\left\{ H\left( {{p}_{1}} \right), H\left( {{p}_{2}} \right), \ldots, H\left( {{p}_{n}} \right) \right\}. $ |
图 6为在二维空间下进行4×4和8×8网格划分的Hilbert填充曲线.由Hilbert曲线的性质可知:在二维空间上位置相近的两个点, 它们的Hilbert值也相近.
|
Fig. 6 Hilbert curve 图 6 Hilbert曲线 |
4 基于网络Voronoi单元查询频率的匿名方法
基于第2.1节中的攻击模型, 本文假设攻击者拥有路网中用户在每条路段上的历史查询信息, 即, 攻击者可以根据不同网络Voronoi单元的历史查询信息推断查询用户的真实位置.本文的匿名方法使得假位置分布于不同的NVC中.给定两个兴趣点的NVC:NVC(A)和NVC(B), 设查询用户的真实位置位于某个兴趣点的NVC(A)的路段上, 系统拟在某个兴趣点的NVC(B)的路段上添加用户的虚假位置.如果系统发现在这两个NVC的历史用户的查询数量差距较大, 系统可以根据这个差异轻易地发现添加的虚假位置, 不能真正实现用户位置的k匿名.因此, 本文的匿名算法需要统计历史用户(包括具有真实位置的用户和虚假位置的用户)在各NVC路段上发出查询请求的数量占历史用户在整个路网路段上发出查询请求数量的比例, 即NVC查询频率.为了使生成的假位置更具真实性, 应保证假位置所在NVC的查询频率与真实用户所在NVC的查询频率保持一致, 以防攻击者根据NVC之间的查询频率差异推导出用户的真实位置.
4.1 网络Voronoi图的构建为了解决基于路网的兴趣点查询的隐私保护问题, 第1步就是要将路网构造成一个针对兴趣点集合的网络Voronoi图.以路网上的兴趣点作为种子节点, 采用Dijkstra算法生成网络Voronoi图, 算法如下.
算法1.网络Voronoi图构建算法.
输入:路网G(V, E), 兴趣点集P;
输出:网络Voronoi图(NVD).
1. for each v∈V
2. 构造标签(POI(v), d(v)); //P(v), d(v)表示距离v最近的兴趣点及距离//
3. end for
4. foreach (v, u)∈E, u∈V //向外拓展寻找v的邻接点//
5. if (P(u)∩P(v)=Ø) //如果u, v属于不同的NVC//
6. 计算边界点b的位置;
7. 保存边界点b(u, v|d(u)-d(v)-dis(u, v)/2); //dis(u, v)表示u, v构成的边的长度//
8. end if
9. end for
10. return NVD;
算法1首先对所有节点构造标签(P(v), d(v)), 其中, P(v)表示距离v最近的兴趣点, d(v)是v到P(v)的最短路径距离.对于兴趣点pi∈P, 其标签为(pi, 0);对于非兴趣点, 通过Dijkstra算法在路网上拓展, 拓展中遇到的第1个兴趣点即为最近的兴趣点, 将该兴趣点与对应的最短路径距离构造标签.算法的第3行~第8行描述了寻找边界点的过程.对于每一条边(v, u)∈E, 如果顶点v和顶点u的最近邻兴趣点不同, 说明边(v, u)上必然存在边界点, 记v, u的最近邻兴趣点为P(v), P(u), 根据两个兴趣点路径之间的中点构造边界点, 则边界点到P(v)的距离为d(u)-d(v)-dis(u, v)/2, 到P(u)的距离为d(v)-d(u)-dis(u, v)/2, 且d(u)-d(v)-dis(u, v)/2=d(v)-d(u)-dis(u, v)/2.通过该方法, 计算所有边界点并存储, 最终实现对NVD的构建.根据文献[10]的分析, 该算法在最坏情况下的复杂度为O(n+(n-t)m’+ (n-k)2log(n-t)), 其中, n=|V|, t=|P|, m’=|V-P|.
4.2 网络Voronoi单元的Hilbert顺序本文提出的匿名算法需要选取距离彼此分散的k-1个网络Voronoi单元并在其中添加假位置, 由于兴趣点的Hilbert顺序即可反映其距离远近关系, 进一步地, 则可利用兴趣点的Hilbert顺序来表示网络Voronoi单元之间的距离远近关系, 并按固定间隔依次选取k-1个网络Voroni单元.
为了获取网络Voronoi单元的Hilbert顺序, 本文利用Hilbert曲线依次遍历路网空间, 并将兴趣点的Hilbert遍历顺序作为其所在网络Voronoi单元的遍历顺序.算法2讲述了NVC的Hilbert遍历顺序的计算过程, 该算法的时间复杂度为O(n×logn+t×logt).具体地, 算法首先根据路网大小及兴趣点的分布情况确定划分阶数n, 将路网空间划分成2n×2n个均等的网格.随后, 用Hilbert曲线对划分好的网格空间进行填充, 按照遍历顺序, 每个网格对应唯一一个Hilbert值.算法的第3行~第6行, 对于每一个兴趣点, 寻找其所在网格的Hilbert值; 第7行将兴趣点的Hilbert值进行排序, 该顺序表现了NVC之间的距离关系.为了避免产生较小的匿名区域而暴露用户的位置隐私, 本文算法生成的假位置所在NVC的距离较远, 从而产生较大的匿名区域.
算法2. NVC的Hilbert顺序计算算法.
输入:兴趣点集P={p1, p2, …, pt}, 路网空间的划分阶数n;
输出:NVC的Hilbert遍历顺序表HI.
1. (2n×2n)cell←Map(G);
2. AL=Hilbert((2n×2n)cell); //将路网空间划分为2nx2n个网格, 并进行Hilbert曲线填充//
3. foreach (pi∈P)
4. H(pi)=AL(pi.cell); //找到兴趣点所对应的Hilbert值//
5. HI.add(H(pi));
6. end for
7. HI.sort(); //对NVC的Hilbert值排序//
8. return HI;
如图 5所示, 路网上具有6个兴趣点p1, p2, p9, p10, p14, p16.根据算法2, 将空间划分成4×4的网格, 并利用Hilbert曲线依次遍历这些网格.如图 7所示, 每个兴趣点所在的网格对应的Hilbert值即为该点NVC的Hilbert值.例如H(NVC(p1))=5.
|
Fig. 7 Hilbert value of each POI 图 7 兴趣点的Hilbert值 |
4.3 满足相互性的路段划分算法
基于概率信息的位置隐私保护方法需要统计某一区域的查询频率信息, 并通过在与用户所在区域的查询频率相同的区域中添加假位置来实现位置匿名.本文提出的隐私保护方法是针对路网环境下的兴趣点查询, 故需要在与用户所在NVC的查询频率相同的其他NVC中添加假位置.NVC查询频率的定义如下.
定义6(NVC查询频率Pvi).设Qi代表第i个NVC中的历史查询数量, 网络Voronoi图有n个NVC, 则有:
| $ {{P}_{vi}}=\frac{{{Q}_{i}}}{\sum\limits_{i=1}^{n}{{{Q}_{i}}}} $ | (2) |
为了保证匿名集的相互性, 需要在k-1个与用户所在NVC查询频率相同的NVC中添加假位置, 并且添加了假位置的路段在NVC中的排序需要与用户位置所在路段在NVC中的排序相同.但是, 不同的NVC中包含的边数的差异无法满足相互匿名的要求, 如用户的位置位于其所在NVC内的第10条边, 为了保证匿名集的相互性, 需要在其他k-1个NVC内第10条边上添加假位置, 但当其他NVC内包含的边数小于10时, 则无法找到与用户相对编号一样的边.为了解决上述问题, 需要统计所有NVC中包含的最大边数Lmax, 并将边数小于Lmax的NVC进行路段划分, 使得每个NVC均拥有Lmax个路段编号.
定义7(最大边编号Lmax).设各个NVC中包含的边的数量为Li, i=1, 2, …, t, 则有:
| $ {{L}_{\rm{max}}}={\rm{max}}\left( {{L}_{i}} \right), i=1, 2, \ldots, t $ | (3) |
以Lmax为上界, 将包含边数少于Lmax的NVC进行边的划分, 将每条边均匀划分为多个路段编号, 使得划分出的路段数等于Lmax.在考虑查询均匀分布的条件下, 我们将各个边进行均匀划分, 使之成为多条路段, 划分后的每个路段的查询频率为
| $ {{P}_{ij}}=\frac{{{P}_{vi}}}{{{L}_{\rm{max}}}}, j=1, 2, ..., {{L}_{\rm{max}}} $ | (4) |
当NVC内的边数少于Lmax时, 就需要对NVC内的边进行再划分, 算法3描述了路段划分算法.算法3为确定性算法, 保证划分后的每个NVC包含的路段数一定为Lmax, 算法的时间复杂度为O(t×Lmax).
算法3.路段划分算法.
输入:网络Voronoi图(NVD);
输出:路段划分表T.
1. for each (NVC(i)∈NVD & & Li < Lmax)
2. foreach (ej∈NVC(i)) //对于第i个NVC中的每一条边//
3. if (Lmax%Li≠0 & & j < (Lmax%Li))
4. T←(⌈Lmax/Li⌉)ej
5. else T←(⌈Lmax/Li⌉)ej //对边ej进行均匀划分//
6. end if
7. end for
8. end for
9. return T;
由于兴趣点及网络拓扑都是固定不变的, 对路网进行网络Voronoi图的划分、对兴趣点进行Hilbert值排序、对各个NVC内路段的划分和编号都是可以离线建立的, 从而缩短了匿名时间和服务响应时间.
以图 8中的网络Voronoi图为例, 在每个NVC内, 根据路网中边的顺序(边的排序对算法没有影响, 可以为任意顺序, 本文采用路网数据集中默认的边的顺序)对NVC内的边进行编号.如图 8所示, NVC(p1), NVC(p2), NVC(p9), NVC(p10), NVC(p14), NVC(p16)包含的边数分别为4, 5, 7, 9, 6, 4, 即, NVC(p10)拥有最大边数且Lmax=9, 则需要对其他5个NVC中的边进行划分.由算法3可以知道, 每个NVC(pi)需要划分的边数为Lmax-Li.在每个NVC(pi)内, 从编号1开始划分.以NVC(p1)为例, NVC(p1)需要增加Lmax-L1=5条边, 从第1条边开始进行划分, 则需要将第1条边平均拆分为3条路段, 将第2条~第4条边平均拆分为2条路段, 新的路段编号紧跟边的顺序, 依次递增, 以此类推, 将所有NVC都划分为9条路段.
|
Fig. 8 Road segment in each NVC 图 8 NVC内路段划分 |
当路网中所有NVC中的路段数都与Lmax相等时, 用户处于任意NVC中的任意路段时, 在其他NVC中总能找到与之编号相同的路段, 这为匿名集满足相互性提供了前提.
4.4 生成假位置当用户发起查询时, 匿名服务器根据匿名算法生成相应的假位置, 该算法根据用户的真实位置及隐私保护度k值的大小在线计算.算法4描述了匿名服务器生成假位置的过程, 该算法的时间复杂度为O(t×logt).根据分析可知:当路网中兴趣点固定不变时, 该算法的时间复杂度与隐私保护度k成反比关系, 实验部分验证了算法4的平均执行时间与隐私保护度k的关系.
算法4.假位置生成算法.
输入:网络Voronoi图(NVD), 兴趣点的希尔伯特值索引HI, 路段划分表T, 历史查询位置表HP, 隐私保护度k, 用户所在NVC的查询频率Pvi;
输出:假位置集合Pos.
1. count←0;
2. for each (NVC(j)∈NVD & & |Pvj-Pvi| < δ)
3. count++; //统计频率相同的NVC个数//
4. bucket1←HI(NVC(j)); //频率相同的NVC放入桶bucket1//
5. end for
6. bucket1.sort(); //对兴趣点的Hilbert值排序//
7. for (k’=0; k’ < ⌈count/(⌊count/k⌋)⌉; k’++)
8. bucket2(k’)←(⌊count/k⌋)bucket1 //二级分桶, 每⌊count/k⌋个NVC放入一个桶//
9. end for
10. for (i=0; i < k’; i++)
11. Pos←HP(bucket(i).rankR.rankL); //rankR为用户所在NVC在桶内的相对位置, rankL为用户所在路段在NVC内的编号//
12. end for
13. return Pos;
算法4描述了生成假位置的过程.首先, 查找所有与用户所在NVC查询频率相同的NVC并统计其个数count.在这些频率相同的NVC中, 根据其兴趣点的Hilbert值大小进行排序.算法的第7行~第9行, 将这些NVC平均划分为k’个桶, 其中k’=⌈count/(⌊count/k⌋)⌉, 根据分析, k’为[k, k+1]之间的整数, 即k’={Z|k≤k’≤k+1}.记用户所在NVC在桶内的相对位置为rankR, 用户所在路段在其NVC内的编号记为rankL, 在其他(k’-1)个桶中寻找桶内相对位置为rankR的NVC, 并在这些NVC中寻找编号为rankL的路段作为假位置生成路段.需要注意的是:假位置在路段中并不是随机产生的, 而是将该路段的最新时刻的历史查询点位置作为假位置, 这样使得添加的假位置满足位置的真实性.
值得注意的是:在兴趣点比较多时, 多个兴趣点可能位于同一个网格内.在这种情况下, 有两种解决方案.(1)调整划分阶数n的大小, 将整个路网空间划分为更细粒度的网格, 使得一个网格内最多存在一个兴趣点; (2)使用文献[6]提出的修正的Hilbert曲线方法, 将存在多个兴趣点的网格划分为4个子网格, 如图 9所示.
|
Fig. 9 Modified Hilbert curve 图 9 修正的Hilbert曲线 |
图 7中假设与用户所在的NVC(p14)具有相同查询频率的NVC是NVC(p1), NVC(p9), NVC(p10), NVC(p2), NVC(p16), 即与用户查询频率相同的NVC个数count=6(包含用户所在NVC), 将这6个NVC根据其兴趣点的Hilbert值从小到大排序为:NVC(p14), NVC(p9), NVC(p1), NVC(p2), NVC(p10), NVC(p16), 以隐私保护度k=3的情况为例, 将每⌊count/k⌋=2个NVC为一个桶, 即NVC(p14), NVC(p9)为一个桶, NVC(p1), NVC(p2)为一个桶, NVC(p10), NVC(p16)为一个桶, 已知NVC(p1)在桶内的相对位置为1, 因此选取相对位置也为1的NVC(p1), NVC(p10)作为添加假位置的NVC, 之后, 根据用户真实位置所在路段在其NVC中的编号, 在NVC(p1), NVC(p10)的相同编号的路段添加假位置, 假设用户在相对位置为1的路段, 则也在NVC(p1), NVC(p9)中编号为1的路段, 将历史位置表HP中该路段的最近时刻的历史查询点位置作为最终的假位置点.
值得注意的是:当有用户在该匿名集内的其他任意路段内进行位置匿名时, 其产生的匿名集仍然是这k条路段, 即, 满足匿名集的相互性.以图 7为例, 当k=3时, NVC(p1), NVC(p10), NVC(p14)的编号为1的路段组成一个匿名集, 则当有用户在NVC(p1)的编号为1的路段发起查询请求时, 匿名算法仍然会在NVC(p10), NVC(p14)的编号为1的路段中添加假位置; 当有用户在NVC(p10)的编号为1的路段发起查询请求时, 算法4也会在NVC(p21), NVC(p14)的编号为1的路段中添加假位置.
5 安全分析 5.1 抵御重放攻击路网上的重放攻击是指攻击者具备匿名算法的原理和生成的匿名集等背景知识, 攻击者利用这些背景知识对匿名集中的每个路段进行位置匿名, 并与匿名集进行比较, 从而判断出用户真正位置的攻击方式.
定理1.提出的匿名算法可以抵御重放攻击.
证明:为了证明所提出的匿名算法可以抵御重放攻击, 需要说明无论在哪一个路段上进行多少次查询, 对其位置的匿名总是选择不变的另外k-1个路段, 即, 产生的匿名集满足相互性.假设本文提出的匿名算法为A(*), 匿名服务器利用匿名算法A(*)为用户u的真实位置产生的路段匿名集为S={l1, l2, …, lk}, 则对S中的每一路段li(i=1, 2, …, k)运行算法A(*), 生成新的匿名集合S’, 记用户所在NVC为NVC(v1), NVC(v1)的查询频率为Pv1, 在由所有查询频率都为Pv1的NVC划分而成的k个桶中, NVC(v1)在桶内的位置记为rankR, 用户所在路段在NVC(v1)内的相对位置为rankL.根据匿名原则, 总是在频率相同、桶内位置相同的k-1个NVC内寻找相对位置相同的路段添加假位置.因此, 在本文的匿名方法中, 在匿名集内任意路段上的用户, 其所在NVC的查询频率都为Pv1, 所在NVC在桶内的位置都为rankR, 所在路段在NVC内的相对位置都为rankL, 因此, 匿名集内的路段添加的假位置的路段也总是相互的, 即S’=S={l1, l2, …, lk}.因此, 无论在哪一个路段上进行多少次查询, 对其位置的匿名总是选择不变的另外k-1个路段, 即产生的匿名集满足相互性.因此, 我们提出的方案能够抵御重放攻击.
5.2 抵御推断攻击推断攻击指攻击者通过攻陷LBS服务器从而获得相关背景知识(如查询频率、历史查询位置、匿名集等), 通过这些知识, 攻击者可以在匿名集中识别用户的真正位置.
定理2.提出的匿名算法可以抵御推断攻击.
证明:为了证明所提出的匿名算法可以抵御推断攻击, 需要说明在攻击者拥有相关的路网背景知识, 即路网中每个NVC的历史查询频率信息的前提下, 本文提出的匿名算法仍然保证攻击者不能将用户的真实位置从k个位置中区分出来.假设用户所在NVC为NVC(v1), 用户所在NVC的查询频率为Pv1, 攻击者根据匿名算法可以获取到用户的匿名NVC集合为N={NVC(v1), NVC(v2), NVC(v3), …, NVC(vn)}; 同时, 攻击者通过与LBS服务器相互勾结, 可以获取路网中不同NVC的历史查询频率信息, 则对于匿名算法寻找的k-1个匿名NVC, NVC(v2), NVC(v3), …, NVC(vn), 其NVC的查询频率分别记为
在本节中, 我们根据公式(2)依次统计了每个NVC中的历史查询频率, 并在真实路网数据集上测试本文提出的匿名方法.
6.1 度量标准在实验中, 我们利用方差、熵[20]和平均路径距离度量匿名位置的不确定性.具体地, 方差值体现了k个位置之间的查询频率的差异, 方差越小, 假位置的真实性越高.熵主要用于衡量信息的不确定性, 熵值越大, 代表信息的不确定性越高, 即, 攻击者从k个位置中分辨出真实位置的可能性越小.平均路径距离指k-1个假位置到真实位置之间的平均路网距离, 平均路径距离越大, 代表假位置越分散, 距离真实位置越远.方差S2、熵H和平均路径距离APD的定义如下:
| $ {{S}^{2}}=\frac{\sum\limits_{i=1}^{k-1}{{{({{P}_{ij}}-{{P}_{uj}})}^{2}}}}{k-1} $ | (5) |
| $ H=-\sum\limits_{i=1}^{k}{{{P}_{ij}}\rm{log}{{P}_{ij}}} $ | (6) |
| $ APD=\frac{\sum\limits_{i=1}^{k-1}{dis(lo{{c}_{dummy}}, lo{{c}_{user}})}}{k-1} $ | (7) |
其中, Puj代表用户所在路段的查询频率, Pij代表第i个假位置所在路段的查询频率, dis(locdummy, locuser)表示假位置与用户之间的最短路径距离.
6.2 实验环境与数据集实验在ubuntu 15.04上使用C++实现, 采用g++编译.实验运行在Intel Core i7-6700的PC上, 内存和CPU分别为8GB和3.40 GHz, 硬盘大小为1TB.基于第3.2节中设定网络通信是安全可信的, 实验部分不考虑网络通信等带来的能耗.本文采用德国Oldenburg路网数据集和新加坡Singapore城市路网数据集来分别测试算法在稀疏路网环境下和稠密路网环境下的表现, 其中, Oldenburg数据集包含6 105个节点、7 035条边, Singapore数据集包含20 801个节点、55 892条边, 数据集的参数见表 2.实验从这两个数据集中随机选择1 000个节点作为兴趣点, 默认采取200 000的查询频数来模拟不同用户发起的200 000次查询请求.为了进一步加快匿名服务的响应速度, 匿名服务器离线建立兴趣点的网络Voronoi单元及其Hilbert值索引.
|
|
Table 2 Parameters of the experimental data set 表 2 实验数据集参数 |
6.3 实验结果
本节通过11组实验, 分析和验证算法的可行性和高效性.实验中, 首先测试了随着k值的变化, 相应方差的变化情况.现有的路网环境下的隐私保护方法可分为基于网络拓张的匿名技术[9]、基于X-star的匿名技术[11, 18]和基于Mix Zone[21-23]的匿名技术, 由于这些方法形成的匿名区域较小, 因此其他k-1个匿名位置与用户距离也极小, 很容易遭受区域攻击[7].文献[18]为X-Star的变种, 图 10中, DepthFirst方法是在此基础上提出的一种针对路网环境下的位置隐私保护方法, 其思想是:首先使用深度遍历方法将边进行排序, 随后将路网中的边均等放入k个桶中, 根据用户所在边在桶中的相对位置, 在其他k-1个桶中挑选与用户在桶内相对位置相同的边, 将这k-1条边上的最近一次历史查询位置作为添加的假位置.相较于传统的匿名技术, 该方法产生的匿名位置能够拥有较大的平均路径距离.BreadthFirst[21]与DepthFirst相似, 边的排序编号采用宽度遍历方式.Random为路网上随机游走选择假位置的方法[5], 该方法为基于假位置的位置隐私保护领域的基本算法.HilbertCurve为本文提出的位置隐私保护方法, 由于HilbertCurve方法考虑了真假位置间的查询频率的相似性, 随着k值的增大, 其方差总是远远小于Random方法.
|
Fig. 10 Effect of k on variance 图 10 k值对方差的影响 |
熵值主要用于体现匿名集中各个位置间所包含信息的差异性和不确定性.由图 11可以看出:熵值随着k的增大而增大, 本文提出的位置保护方法的熵值略大于其他3种方法.即:在攻击者具有频率背景知识的前提下, 本文提出的方法更能抵御攻击者的攻击.
|
Fig. 11 Effect of k on entropy 图 11 k值对熵的影响 |
图 12反映了随着k的变化, 平均路径距离的变化情况.实验结果表明:无论k值如何变化, 本文提出的位置隐私保护方法比其他3种方法的平均路径距离都大, 假位置分布更分散.
|
Fig. 12 Effect of k on average path distance 图 12 k值对平均路径距离的影响 |
平均匿名时间指匿名服务器平均对一个用户查询进行位置匿名的时间, 在本文中, 算法4的平均执行时间即平均匿名时间.图 13反映了在添加200 000次~600 000次查询请求时, 平均匿名时间的变化情况.随着查询数量的增大, 平均匿名时间趋于下降, 表现了良好的可拓展性.值得注意的是:随着k值的增大, 平均匿名时间也趋于下降.这是由于当与用户所在NVC查询频率相同的NVC数量count不变时, 根据算法4, 匿名算法需要将这些NVC每隔⌊count/k⌋个装入一个桶中.随着k值增大, 每个桶包含的NVC数量将趋于下降, 分桶时间降低.
|
Fig. 13 Effect of k on average anonymous time 图 13 k值对平均匿名时间的影响 |
平均查询时间[24]指用户从发起查询到获得查询结果的平均时间.图 14反映了在进行200 000次~600 000次NN查询[25]时, 平均查询时间随k值的变化情况.如图 14所示:平均查询时间的变化与平均匿名时间相似, 均随着k值及查询数量的增大而变小.
|
Fig. 14 Effect of k on average query time 图 14 k值对平均查询时间的影响 |
K-NN查询[26]旨在查找距离用户最近的K个兴趣点, 图 15反映了在查询频数为200 000次~600 000次的条件下, 当用户查询距离其最近的K个兴趣点时, 平均查询时间随K的变化情况.当K增大时, 由于搜索路径变长, 不同查询频数下的平均查询时间都会趋于增加; 当K取值不变时, 平均查询时间随着查询频数的增加而趋于下降, 与NN查询的变化趋势一致.
|
Fig. 15 Effect of the number of POIs that users query K on average query time 图 15 用户查询POI数K对平均查询时间的影响 |
当路网数据庞大、道路繁多时, 兴趣点的数量也会大幅增加, 对匿名算法的性能要求也会随之提高.图 16反映了POI数目对构建NVC(算法1)时间的影响.随着POI数目的增多, 构建NVC的时间反而大幅降低.造成这种现象的原因是随着POI数量的增多, 顶点到最近POI的路径距离变小, 搜索时间变短.
|
Fig. 16 Effect of the number of POIs on the time of constructing each NVC 图 16 兴趣点数量对NVC构建时间的影响 |
图 17反映了POI数目对计算NVC的Hilbert顺序(算法2)时间的影响.随着POI数目的增加, 需要计算的NVC相应增加, 因此, NVC的Hilbert值的计算时间也呈上升趋势.
|
Fig. 17 Effect of the number of POIs on the time of constructing the Hilbert value of calculating each NVC 图 17 兴趣点数量对NVC的Hilbert值的计算时间的影响 |
图 18反映了POI数目对路段划分(算法3)时间的影响.随着POI数目的增多, 路段划分的时间趋于下降, 这是因为当兴趣点增多时, 每个NVC内包含的路段数变少, 导致路段划分的基数变小, 划分时间变短.
|
Fig. 18 Effect of the number of POIs on the time of edge partition time 图 18 兴趣点数量对路段划分时间的影响 |
当路网中的POI数量增加时, 由于NVC个数的增加, 与用户查询频率相同的NVC个数也增加, 即:匿名的候选NVC个数增加, 则导致平均匿名时间趋于增加, 如图 19所示.但值得注意的是:与图 13、图 14相似, 图 20中随着POI数量的增加, 平均查询时间的上升趋势与平均匿名时间相似, 说明平均查询时间的增加主要源于平均匿名时间, 即, POI数量对查询本身并不产生较大影响.
|
Fig. 19 Effect of the number of POIs on the average anonymous time 图 19 兴趣点数量对平均匿名时间的影响 |
|
Fig. 20 Effect of the number of POIs on the average query time 图 20 兴趣点数量对平均查询时间的影响 |
由图 16~图 20可知:在路网复杂、POI分布密集的情况下, 本文匿名算法也能表现出良好的拓展性.根据算法在两个数据集上的表现可以得出结论:在稀疏和稠密的路网环境下, 本文提出的方法都能表现出良好的性能.
7 结束语本文提出了一种针对路网环境下兴趣点查询的隐私保护方法, 该方法充分考虑到路网的历史查询频率以及匿名路段之间的相互性问题, 使得生成的假位置频率相近、位置分散, 能够抵御重放攻击和推断攻击.本文提出的假位置生成算法在熵值、方差、平均路径距离上都具有显著优势, 因此, 本文提出的位置匿名算法可以有效保护用户的位置隐私.实验结果表明:本文方法具有良好的扩展性, 能够在不影响服务质量的前提下保护用户的位置隐私, 对路网环境下进行兴趣点查询的位置隐私保护领域具有广泛而深远的现实意义.
当然, 路网环境下的位置隐私保护领域还有许多其他问题有待深入探索和解决.在未来的工作中, 我们将向两个方向进行拓展:(1)进一步提高算法的性能, 使其能够提供更高效便捷的隐私保护服务; (2)研究更优的隐私保护方法, 将其应用到更广泛的位置服务领域, 不局限于路网上的兴趣点查询范围.
| [1] |
Wang B, Yang X, Wang G, Yu G, Zang W, Yu M. Energy efficient approximate self-adaptive data collection in wireless sensor networks. Frontiers of Computer Science, 2006, 10(5): 936–950.
[doi:10.1007/s11704-016-4525-7] |
| [2] |
Gruteser M, Grunwal D. Anonymous usage of location-based services through spatial and temporal cloaking. In: Proc. of the Int'l Conf. on Mobile Systems, Applications, and Services (MobiSys). 2003. 163-168. [doi: 10.1145/1066116.1189037] |
| [3] |
Ido H, Yanagisawa Y, Satoh T. An anonymous communication technique using dummies for location-based services. In: Proc. of the Int'l Conf. on Pervasive Services. 2005. 88-97. [doi: 10.1109/PERSER.2005.1506394] |
| [4] |
Kalnis P, Ghinita G, Mouratidis K, Papadias D. Preventing location-based identity inference in anonymous spatial queries. IEEE Trans. on Knowledge and Data Engineering, 2007, 19(12): 1719–1733.
[doi:10.1109/TKDE.2007.190662] |
| [5] |
Niu B, Li Q, Zhu X, Cao G, Li H. Achieving k-anonymity in privacy-aware location-based services. In: Proc. of the 33rd Annual IEEE Int'l Conf. on Computer Communications. 2014. 754-762. [doi: 10.1109/INFOCOM.2014.6848002] |
| [6] |
Niu B, Li Q, Zhu X, Li H. A fine-grained spatial cloaking scheme for privacy-aware users in location-based services. In: Proc. of the Int'l Conf. on Computer Communication and Networks. 2014. 1-8. [doi: 10.1109/ICCCN.2014.6911813] |
| [7] |
Cui N, Yang X, Wang B. A novel spatial cloaking scheme using hierarchical Hilbert curve for location-based services. In: Proc. of the 17th Int'l Conf. on Web-Age Information Management. 2016. 15-27. [doi: 10.1007/978-3-319-39958-4_2] |
| [8] |
Lee HJ, Hong ST, Yoon M, Um JH, Chang JW. A new cloaking algorithm using Hilbert curves for privacy protection. In: Proc. of the ACM Sigspatial Int'l Workshop on Security and Privacy in Gis and Lbs. 2010. 42-46. [doi: 10.1145/1868470.1868480] |
| [9] |
Mouratidis K, Yiu ML. Anonymous query processing in road networks. IEEE Trans. on Knowledge and Data Engineering, 2010, 22(1): 2–15.
[doi:10.1109/TKDE.2009.48] |
| [10] |
Papadias D, Zhang J, Mamoulis N, Tao Y. Query processing in spatial network databases. In: Proc. of the 29th Int'l Conf. on Very Large Data Bases. 2003. 802-813. [doi: 10.1016/B978-012722442-8/50076-8] |
| [11] |
Wang T, Liu L. Privacy-Aware mobile services over road networks. In: Proc. of the 35th Int'l Conf. on Very Large Data Bases. 2009. 1042-1053. [doi: 10.14778/1687627.1687745] |
| [12] |
Chow CY, Mokbel MF, Bao J, Xuan J. Query-Aware location anonymization for road networks. GeoInformatica, 2011, 15(3): 571–607.
[doi:10.1007/s10707-010-0117-0] |
| [13] |
Li M, Qin Z. Survey of location privacy protection over road networks. Application Research of Computers, 2014, 31(9): 2576–2580(in Chinese with English abstract).
[doi:10.3969/j.issn.1001-3695.2014.09.003] |
| [14] |
Zhu H, Wang J, Wang B, Yang X. Location privacy preserving obstructed nearest neighbor queries. Journal of Computer Research and Development, 2014, 51(1): 115–125(in Chinese with English abstract).
[doi:10.7544/issn1000-1239.2014.20130694] |
| [15] |
Erwig M, Hagen F. The graph Voronoi diagram with applications. Journal of Network, 2000, 36(3): 156–163.
[doi:10.1002/1097-0037(200010)36:3<156::AID-NET2>3.0.CO;2-L] |
| [16] |
Chen XH, Pang J. Measuring query privacy in location-based services. In: Proc. of the 2nd ACM Conf. on Data and Application Security and Privacy. 2012. 49-60. [doi: 10.1145/2133601.2133608] |
| [17] |
Zheng M, Wang B, Yang XC. Privacy preservation approach for location-based service on road network. Journal of East China Normal University (Natural Science), 2015, 183(5): 116–127(in Chinese with English abstract).
[doi:10.3969/j.issn.1000-5641.2015.05.010] |
| [18] |
Kim YK, Hossian A, Hossian AA, Chang JW. Hilbert-Order based spatial cloaking algorithm in road network. Concurrency and Computation:Practice and Experience, 2013, 25(1): 143–158.
[doi:10.1002/cpe.2844] |
| [19] |
Mokbel MF, Aref WG, Kamel I. Analysis of multi-dimensional space-filling curves. GeoInformatica, 2003, 7(3): 179–209.
[doi:10.1023/A:1025196714293] |
| [20] |
Serjantov A, Danezis G. Towards an information theoretic metric for anonymity. In: Proc. of the 2nd Privacy Enhancing Technologies Workshop. 2003. 41-53. [doi: 10.1007/3-540-36467-6_4] |
| [21] |
Freudiger J, Shokri R, Hubaux JP. On the optimal placement of mix zones. In: Proc. of the Int'l Symp. on Privacy Enhancing Technologies. 2009. 216-234. [doi: 10.1007/978-3-642-03168-7_13] |
| [22] |
Palanisamy B, Liu L. MobiMix: Protecting location privacy with mix-zones over road networks. In: Proc. of the Int'l Conf. on Data Engineering. 2011. 494-505. [doi: 10.1109/ICDE.2011.5767898] |
| [23] |
Freudiger J, Raya M, Félegyházi M, Papadimitratos P, Hubauxet JP. Mix-Zones for location privacy in vehicular networks. In: Proc. of the 1st Int'l Workshop on Wireless Networking for Intelligent Transportation Systems. 2007. |
| [24] |
Yang X, Wang B, Yang K, Liu C, Zheng B. A novel representation and compression for queries on trajectories in road networks. IEEE Trans. of Data Engineering (TKDE), 2018.
[doi:10.1109/TKDE.2017.2776927] |
| [25] |
Zhu H, Yang X, Wang B, Lee WC. Range-Based obstructed nearest neighbor queries. In: Proc. of the ACM Int'l Conf. on Management of Data (SIGMOD). 2016. 2053-2068. [doi: 10.1145/2882903.2915234] |
| [26] |
Wang B, Zhu R, Yang X, Wang G. Top-K representative documents query over geo-textual data stream. World Wide Web-Internet & Web Information Systems, 2017, 20(8): 1–19.
[doi:10.1007/s11280-017-0470-0] |
| [13] |
李敏, 秦志光. 路网环境下位置隐私保护技术研究进展. 计算机应用研究, 2014, 31(9): 2576–2580.
[doi:10.3969/j.issn.1001-3695.2014.09.003]
|
| [14] |
朱怀杰, 王佳英, 王斌, 杨晓春. 障碍空间中保持位置隐私的最近邻查询方法. 计算机研究与发展, 2014, 51(1): 115–125.
[doi:10.7544/issn1000-1239.2014.20130694]
|
| [17] |
郑淼, 王斌, 杨晓春. 路网环境下基于位置服务的隐私保护方法. 华东师范大学学报(自然科学版), 2015, 183(5): 116–127.
[doi:10.3969/j.issn.1000-5641.2015.05.010]
|