基于连续最邻近查询的缓存位置隐私保护算法*

贾媛媛, 史志才, 方 凯, 许华根

(1.上海工程技术大学 电子电气工程学院,上海201620;2.上海市信息安全综合管理技术研究重点实验室,上海 200240)

0 引 言

随着移动物联网的迅速发展,移动终端设备、无线传感器网络定位技术的兴起[1],基于位置服务(location-based service,LBS)为人们带来了巨大便利。空间查询是最重要的LBS之一。根据空间限制,空间查询可以分为最近邻(nearest neighbor,NN)查询和R范围查询(R range query)[2]。

为了避免空间位置查询暴露移动用户的敏感信息,文献[3]中提出将查询结果和相应的有效区域(VR)缓存在客户端缓存中,以缓解上述问题。在文献[4]提出在移动客户端和LBS服务器之间部署代理以构建有效区域(EVR)。其中代理提供估计的EVR,通过缓存基于先前查询创建的EVR来回答对相同对象感兴趣的后续查询。尽管文献[4]中的代理部署和EVR成功设置完成,但是NN查询的EVR增长缓慢,导致较低的缓存命中率。文献[5]通过使用基于希尔—伯特曲线的分布式索引对无线广播系统中的窗口进行查询,但是没有考虑保护用户的位置隐私。目前针对连续查询位置隐私保护问题,主要分为两类结构[6]：点对点和基于可信第三方(trusted third party,TTP)的中心服务器结构。

为了避免客户端计算量过大,本文提出计算包含NN结果的候选集框任务由第三方可信匿名服务器承担。

1 系统架构

采用基于第三方可信匿名服务器的系统架构。系统架构由三部分组成：1)LBS服务器。 2)第三方可信匿名服务器。 3)移动客户端。如图1所示。

图1 系统架构

2 EVR树

第三方可信服务器基于NN查询历史记录和可用数据对象构建NN查询的EVR。它维护一个对象高速缓存和一个索引结构：用于NN查询的EVR树,如图2所示。EVR树是由EVR组成的R树,其中每个EVR都包裹在最小边界框(MBR)中。EVR由相对于数据对象的区域顶点和指向高速缓存中相应对象的指针组成。缓存对象包含以下信息{ID,(x,y),eID,cell_flag,Object_info}。假设每个数据对象p具有唯一的ID。(x,y)是p的二维坐标。eID表示相应EVR的ID,而cell_flag表示p是否位于完全缓存的单元中。Object_info中的对象包含p的基本信息。例如,餐馆包括烹饪类型,营业时间,电话号码等。当将p的EVR插入EVR树时,将更新相应对象的eID。类似地,一旦p所在的覆盖单元变为完全高速缓存,则cell_flag设置为true。使用该信息,当必须替换p时,可以从EVR树中移除相应的EVR或将完全缓存的单元恢复为未缓存。

图2 EVR树索引

3 NN查询缓存位置隐私保护方法

3.1 总体方法

当接收到NN查询时,第三方服务器首先尝试使用EVR树来回答查询。如果匿名服务器不能回答查询,通过虚拟选择算法向LBS服务器提交一个或两个2NN查询。将接收到的NN查询扩展为2NN查询的基本原理是,根据文献[7]的理论结果,最近的对象和第二最近的对象之间的距离有利于构建最近对象的EVR。通过利用LBS服务器返回的对象,可以扩展现有的对象或创建新的EVR。这里给定一个对象p,它的EVR用EVR(p)表示。第三方可信匿名服务器执行的处理步骤如下：

步骤1 匿名服务器通过执行一般的R树搜索操作来检查NN查询位置(xq,yq)是否在EVR树的任何EVR中。如果是,请转到步骤7。

步骤2 匿名服务器将收到的NN查询扩展为具有相同查询位置(xq,yq)的2NN查询,并将2NN查询通过虚拟选择算法形成空间k—匿名区域提交给LBS服务器。令p1和p2分别为q的最近和第二近的对象。

步骤3 位置服务提供商从数据库中查询用户查询范围内的POI,获取查询结果,并将其返回给匿名器,当从LBS服务器获取p1和p2时,匿名服务器在EVR树中搜索EVR(p1)。如果找到EVR(p1),请转到步骤6。

步骤4 可信匿名服务器生成另一个带查询位置(x1,y1)的2NN查询,其中(x1,y1)是p1的位置。显然,(x1,y1)最近的对象是p1。设第二个最近的对象(x1,y1)为p3,运行算法EVR-Creation以基于p1,p2和p3创建p1的EVR。

步骤5 将p1和EVR(p1)分别插入对象缓存和EVR树。转到步骤7。

步骤6 使用q,p1和p2,以及算法EVR-Extension扩展现有EVR(p1)。将更新的EVR(p1)重新插入EVR树。

步骤7 匿名服务器将应答对象p1和相应的EVR(p1)返回给移动客户端。

3.2 EVR创建

当EVR树索引不能回答具有位置(xq,yq)的NN查询时,匿名服务器将为查询对象p1创建一个新的EVR,如下所示。首先,将NN查询扩展为2NN查询,并将2NN查询通过虚拟选择算法提交给LBS服务器。在获得2NN查询的对象p1和p2(其中dis(q,p1)< dis(q,p2))之后,可信匿名服务器首先通过建立一个以q为中心的圆C1来创建EVR。作为半径,其中r1=(dis(q,p2)- dis(q,p1))/2。设p1的位置为(x1,y1)。接下来,将另一个具有查询位置(x1,y1)的2NN查询提交到LBS服务器。显然,最接近位置(x1,y1)的对象是p1。让这个新的2NN查询的第二个最接近的对象是位置为(x3,y3)的p3。类似地,如图3所示,匿名服务器以中心(x1,y1)和半径r2构建另一个圆C2,其中r2=dis(p1,p3)/2。然后,以q为原点,以θ为q与p1之间的夹角,创建7个顶点V1(xnew1,ynew1),V2(xnew2,ynew2),V3(xnew3,ynew3),V4(xnew4,ynew4),V5(xnew5,ynew5),V6(xnew6,ynew6)和V7(xnew7,ynew7)由以下等式表示

图3 EVR的创建

xnew1=xq+r1cos(θ+π/2),ynew1=yq+r1sin(θ+π/2)

xnew2=xq+r1cos(θ-π/2),ynew2=yq+r1sin(θ-π/2)

xnew3=xq+r1cos(θ+3π/4),ynew3=yq+r1sin(θ+3π/4)

xnew4=xq+r1cos(θ-3π/4),ynew4=yq+r1sin(θ-3π/4)

xnew5=xq+r1cos(θ+π),ynew5=yq+r1sin(θ+π)

xnew6=x1+r2cos(θ-π/2),ynew6=y1+r2sin(θ-π/2)

xnew7=x1+r2cos(θ+π/2),ynew7=y1+r2sin(θ+π/2)

3.3 EVR扩建

如前所述,当匿名服务器接收到提交的2NN查询位置为(x1,y1)的对象p1和位置为(x2,y2)的对象p2时,它首先检查是否缓存了EVR(p1)。如果是,则通过以下步骤调用算法EVR-Extension以更新EVR。首先,匿名服务器从EVR树中检索现有的EVR(p1)。让(xold,yold)为EVR(p1)的形心,并按照3.2节中给出的方法构建圆C1,如图4所示。

图4 EVR创建

以(xold,yold)作为原点,θ作为q与p1之间的夹角,进行计算,如图5所示。如下确定5个顶点v1(xext1,yext1),v2(xext2,yext2),v3(xext3,yext3),v4(xext4,yext4)和v5(xext5,yext5)的坐标。然后,使用5个顶点v1,v2,v3,v4和v5扩展原始EVR(p1)。5个顶点坐标确定如下

图5 EVR的扩展

xext1=xq+r1cos(θ+π/2),yext1=yq+r1sin(θ+π/2)

xext2=xq+r1cos(θ-π/2),yext2=yq+r1sin(θ-π/2)

xext3=xq+r1cos(θ+3π/4),yext3=yq+r1sin(θ+3π/4)

xext4=xq+r1cos(θ-3π/4),yext4=yq+r1sin(θ-3π/4)

xext5=xq+r1cos(θ+π),yext5=yq+r1sin(θ+π)

由于更新后的EVR可能会变成凹面多边形,因此,采用Melkman算法计算更新后的EVR的凸面多边形,以删除不必要的顶点并获得更大的区域大小。凸多边形用作p1的最终更新EVR。可以参考文献[8]获得所提出算法的证明。

3.4 虚拟选择算法

本文提出一种虚拟选择算法增强用户隐私。根据用户需要查询的单元格,生成实际的虚拟位置,匿名器选择K个单元形成隐藏区域,该区域可以隐藏真实用户的位置,以混淆不受信任的LBS服务器。从单元格中选择虚拟位置。在此算法中,Cr是真实位置；k是k—匿名相关的输出集的大小；Cp是包含所有候选单元格的集合,C是包含当前实际位置和k-1个所选虚拟位置的输出集。在算法开始时,用户Alice需要将集合R中的所有单元格与M进行比较,并获得集合Cp。此后,Alice可以从Cp中随机选择k-1个单元格作为其虚拟位置。将k-1个选定的单元格和Cr组合在一起作为输出集C。

虚拟选择算法：

Input:R,M,n,Cr,k

Output:C

1)for (i=1;i≤n2,i≠r;i++) do

2)if (Ci∉M) then

3)Ci→Cp;

4)end if

5)end for

6)Cr→C;

7)selectk-1 cells fromCprandomly→C。

4 实验性能与安全性分析

4.1 实验环境

算法采用Java实现,实验运行平台为Windows 7操作系统,Intel®CoreTMi5—8265U处理器、8GB内存,实验数据采用研究业界认可的Thomas Brinkhoff路网数据生成器[9],输入德国Oldenburg城市的交通网络图。EVR树的大小设置为服务器缓存大小的22 %。参照了文献[10]中的移动模型对仿真参数进行设置。

这里使用两个性能指标：客户端缓存命中率和服务器负载。客户端缓存命中率表示缓存的EVR和VR在移动客户端的有效性以及移动设备资源消耗。服务器负载定义为LBS服务器上的总计算时间。

4.2 缓存命中率的分析

主要针对本方案中的缓存命中率分析。将本文提出的算法与文献[11]中的LDQ算法进行对比,实验结果表明客户端缓存命中率随着缓存大小的增加而增加,如图6(a),这与实际相符。对于NN查询,如图6(b),移动速度快会降低缓存命中率。这是因为移动速度越高,移动客户端越频繁地移出缓存的EVR或VR,从而提交更多查询。但是,与LDQ算法相比,本文方法优势明显。

图6 两种算法缓存命中率结果分析

4.3 服务器负载分析

如图7(a)所示,随着移动速度的增加,服务器负载逐渐变大,由于用户提交更多查询,客户端缓存的命中率低,LDQ算法在所有移动速度下均表现不佳。服务器端负载随着缓存大小的增加而减少,如图7(b),这是因为本文方法使用缓存对象可以直接回答许多客户端的查询,从而降低服务器负载。

图7 服务器负载对比结果分析

4.4 安全性分析

当用户向位置服务提供商发送查询请求,并且匿名器端缓存所有结果数据时,用户直接从缓存中提取 POIs。在此过程中,用户不会与位置服务提供商进行交互,位置服务提供商无法从用户获取任何信息。

如果用户无法获取缓存中的结果数据,则匿名器将形成隐藏区域并发送给位置服务器。即使位置服务器识别隐藏区域中的所有用户,但隐藏区域至少有k个用户,因此它可以猜测指定用户的概率只有1/k。

5 结束语

本文提出一种基于缓存候选结果集的连续位置隐私保护方法,利用缓存思想和基于虚拟选择算法进行k—匿名技术,减少用户与 LBS 服务之间的交互。实验结果显示,与LDQ方案比较,本文算法能减少 LBS 服务器的开销,提高缓存命中率,但本文虚拟选择算法选择以前未查询过的虚拟位置。因此,在下一步工作中,将会考虑从单元中选择对缓存率有更多贡献的位置产生虚拟位置,以进一步提高用户的位置隐私。