基于LBS的连续查询位置隐私保护模型的动态规划算法

雷建云，张镭钟

(中南民族大学 计算机科学学院，武汉 430074)

基于LBS的连续查询位置隐私保护模型的动态规划算法

雷建云，张镭钟

(中南民族大学 计算机科学学院，武汉 430074)

针对现有的算法大多都是静态位置隐私保护的，如果将静态算法应用于动态的连续查询中，会导致位置隐私泄露，提出了一种基于连续查询的动态规划改进算法，旨在保护用户的位置隐私，仿真实验结果证明：该算法在匿名处理时间、匿名成功率和轨迹扭曲度等方面优于现有算法.

位置服务；隐私泄露；K-匿名；连续查询；动态规划

随着科技的发展，移动定位技术在互联网中得到了广泛的应用，而移动技术和无线设备的结合，能够随时随地确定用户的精确位置.因此位置服务(LBS)应运而生，可以根据用户所在的位置提供相应的服务[1].例如，用户可以查询最近的饭馆、医院、车站、加油站，可以进行导航等.但是，人们在享受这些服务的同时，容易造成个人位置隐私的泄露问题，甚至可能威胁到用户的人身安全.因此，保护用户的位置信息不易被攻击者获得，同时又能使用户享受高质量的服务，这个问题引起了广大学者的关注，成为近年来研究的热点问题之一.

近年来，许多的位置隐私保护技术被提出用来解决移动用户的隐私问题，其中应用最广泛的模型之一是位置k-匿名.在位置k-匿名中，发送给LBS服务器的是一块区域，这块区域中包含至少k个用户，而并不是某个用户的确切位置.从攻击者的角度来看，攻击者得到的是用户请求的一块区域，而不是某个用户的真实位置，这样就能确保用户的位置隐私.因此寻找合适的匿名区域成为了广大学者的研究重点.

1 现有的匿名算法

保护用户的位置隐私，目前最常用的是匿名技术.关于匿名技术的方法有：发布假位置、时空匿名、个性化隐私需求匿名、位置k-匿名等[2].

位置匿名系统的结构有3种，独立式结构、中心服务器结构和分布式的点对点结构[2].独立式结构是用户在客户端完成位置匿名；中心服务器结构是在独立式结构的基础上增加了一个可信第三方的中间件，由中间件来生成位置匿名；分布式的点对点结构是移动用户和位置服务器的两端结构，移动用户与移动用户之间应该相互信任，从而找到合适的位置匿名.现在常用的是中心服务器结构和分布式点对点结构.

文献[3]在位置保护隐私领域已有的术语基础上，提出了一组更加精确的术语，例如匿名、不可关联性、不可观察性、和假名等.不但帮助了这个领域的更好发展，而且避免了每一位研究人员对同一术语的不同描述.

文献[4]中Gruteser等人是最早提出保护用户位置隐私的k-匿名方法的.当一个移动用户的位置无法与其他(k-1)个用户的位置相区别时，称此位置满足位置k-匿名[5].例如，用户A在t1时刻形成了一个匿名集{A，D，E，F}，如图1所示，那么在匿名后，攻击者获得的位置信息就是一个位置集合，而不能得到用户A的确切位置，这样可以保护用户A的位置.虽然这种方法也可以用于连续查询，但是可能会出现一系列的问题，最重要的就是可能会导致位置隐私泄露，比如，用户A在t1时刻形成的匿名框为{A，B，C}，在t2时刻形成的匿名框为{A，C，D}，在t3时刻形成的匿名框为{A，D，F}，如果攻击者知道用户使用的是连续查询，那么将t1、t2、t3时刻的匿名框取他们的交集，如图2所示，就能知道是用户A提出的查询并能知道A所在的位置.

图1 匿名位置集合Fig.1 Collection of anonymous location

图2 匿名框交集Fig.2 Anonymous box intersection

文献[6]中第一次提出了连续查询下的位置隐私保护.如图3所示，用户A在t1时刻形成的匿名集为{A，B，F}，则在t2和t3时刻形成的匿名集仍然是{A，B，F}，这样攻击者就无法通过对不同时刻匿名集形成的交集获得用户的具体位置.但是，这种算法也有它的局限性，因为没有考虑到用户未来的移动方向，仅仅只是考虑到了当前的位置，因此如果未来的运动方向是相反的，那么会导致匿名框的范围变得越来越大，影响了最终的服务质量；如果未来的运动方向是相向的，那么在某一时刻，匿名框的范围有可能会聚集于一点，那么用户的位置隐私也就暴露了.

图3 不同时刻取不同范围的匿名集Fig.3 Anonymous collection taken in different range at different time

文献[7]提出了采用信息熵的概念来保护用户的位置隐私.但是信息熵不能反映用户的位置分布情况，可能会导致匿名框中的用户汇聚于一点的情况，从而导致了用户位置隐私的泄露.

使用现有的匿名算法保护连续查询的位置隐私，存在以下3个问题：1)连续查询的位置隐私有很大可能会泄露；2)因连续查询具有实时更新和位置频繁变换的特点，造成匿名服务器的负担变重，从而导致系统瓶颈；3)很多的网络资源被传输新位置和新的匿名框而占用，浪费了许多的资源，可能会导致网络拥堵.

因此，结合已有的匿名算法，提出一种改进的连续查询隐私保护的动态规划算法.

2 动态规划算法

2.1 相关定义

定义1 查询结构体Q=(cid，l，v，t，Texp，con)，其中：

cid表示提出查询的用户ID；l=(x，y)表示用户所在的位置；v =(vx，vy)表示的是速度向量，其中vx、vy分别表示在x、y轴方向上的速度分量；t表示该查询是在时刻t提出的；Texp表示查询的有效时间；con表示查询的内容.

定义2 匿名集CR=(CID，Qlist，RL，t)，其中：

CID表示匿名集的唯一标识；Qlist表示匿名集中所包含的查询结构体；RL，t=(Lx-，t，Ly-，t，Lx+，t，Ly+，t)表示匿名框，是覆盖Qlist中所有用户位置的最小边界矩形，其中(Lx-，t，Ly-，t)和(Lx+，t，Ly+，t)是最小边界矩形的左下角和右上角在时刻t的坐标值.

定义3 速度相似度

规定以正北方向为二维坐标轴的y轴正方向，以正东方向为x轴正方向.速度向量可以拆分成速度大小和速度方向，根据速度大小可以得到速度大小相似度，根据速度方向可以求出两个速度之间的夹角，用夹角来判断速度方向相似度，由此可知，速度大小差距越小，夹角越小，速度相似度越高；反之，速度大小差距越大，夹角越大，速度相似度越低.

图4 速度向量夹角Fig.4 Speed vector angle

如图4所示，是t时刻的两个用户的移动速度向量，速度大小的差距直接比较即可，主要是要算得它们的夹角，那么问题就演变为求两个向量之间的夹角，可以用反余弦公式求夹角.

定义4 时效相似度

时效相似度是指在时刻t形成的匿名集中，查询Q1与Q2在其生命有效期内的相似度，计算2个查询的差值，差值越小，相似度越接近.

定义5 相对位置

通过求查询Q1与Q2的相对距离，获得2个用户之间距离的远近关系，从而确定匿名框的大小范围.可以将用户的位置看作是二维坐标上的一个点，那么求2个用户之间的距离，其实就是求平面直角坐标系中2个点之间的欧式距离.

定义6 轨迹扭曲度

如果轨迹M={CR1,CR2,CR3,…,CRn}是一条匿名轨迹，那么轨迹扭曲度为：

(1)

2.2 t时刻的k-匿名算法

//当新查询nq来临时

MapCR=newMap();

ListqueryList=newArrayList();

queryList.add(nq);

insertnqintoRL,t;

forqinquerys

if(|nq.Texp-q.Texp| > δT) //判断时效相似性

continue;

else

//计算速度相似性

if(SpeedSimilarity(q, nq))

//判断距离，不能太近，导致位置泄露，

//也不能太远，影响服务质量

if(Distortion(q, nq))

queryList.add(q);

insertqintoRL,t;

endif;

endif;

endif;

endfor;

CR.put(“CID”, CID);

CR.put(“QList”, queryList);

CR.put(“RL,t”, RL,t);

returnCR.

2.3 速度相似度算法

speed_size = | |nq.v| - |q.v| |;

cosθ=

//根据|θ|<10°,cos10°=0.985,cos11°=0.982,cos12°=0.978，推出cosθ>=0.98

if(speed_size<= 1andcosθ >= 0.98)

returntrue;

else

returnfalse.

2.4 位置扭曲度算法

假设t时刻的匿名集是CR，匿名框为RL，t,查询nq∈CR.QList,也就是说，在t时刻，查询nq的用户的位置被泛化为了RL，t,那么位置扭曲度为：

(2)

其中，R.x和R.y是匿名框的宽和高，Ax和Ay是整个空间的宽和高，具体算法如下所示：

//大于给定的隐私概率，保证了匿名框不会聚集于一点，导致隐私泄露

if(rate >= δp)

//小于给定的质量概率，保证了匿名框不会过大，影响服务质量

if(rate <=δq)

returntrue;

else

returnfalse;

else

returnfalse.

2.5 动态规划算法

采用动态规划的思想找出运动的轨迹，可以将每一时刻形成的匿名集看作是轨迹的一部分，将真实用户的运动轨迹从线变成区域，并将用户ID进行加密，这样每次形成的匿名框都不可能产生交集，那么攻击者就找不出真实的用户位置，从而保护了用户的位置隐私，同时，每次生成的匿名集都尽可能的保证匿名集中的用户运动状态是一致的，并且保证了匿名框的大小范围不会小于隐私范围，不会超出服务范围，那么可以说，匿名集中的用户就相当于是在同一辆汽车中，一起运动，这样就保护了用户的位置隐私.具体算法如下：

i = 0,M[i]={};

fori=1ton

ifnqisnewquery

CR(i) =Anonymity(nq);

M[i] = CR(i);

else

ifq.speed-nq.speed<δspandrelativePos(CR(i-1),nq)

M[i] = M[i-1]+CR(i-1);

else

CR(i) =Anonymity(nq);

M[i] = M[i-1]+CR(i);

returnM[i].

3 实验仿真与结果分析

3.1 实验数据及仿真环境

实验采用的数据是根据城市Oldenburg的真实路网情况(面积大约为25km×25km)，用ThomasBrinkhoff[8]路网数据生成器生成的.生成了共10000个移动用户，从这些移动用户中随机产生3000个查询请求用户，表1给出了实验需要的相关参数及其范围.其中，n代表移动用户数，q代表查询用户数，t代表连续查询时间，k代表匿名隐私需求，δsp代表最小速度差，δp代表最小隐私率，δq代表最大服务质量.

表1 实验相关参数

注：实验实现环境为：Windows 7 旗舰版操作系统，2GB内存，用Java编程语言实现算法

3.2 实验结果分析

根据不同算法的特征，将本文提出的动态规划算法(dynamic)与文献[5] greedy算法进行匿名处理时间与匿名成功率的比较.与文献[7] GP算法、文献[9] DP算法以及文献[6] Naive算法进行轨迹扭曲度的比较分析.

3.2.1 dynamic算法与greedy算法的比较

如图5所示，随着匿名隐私度的增加，匿名处理时间增加，，但是图中可以看出，dynamic的处理时间比greedy算法的整体处理时间要短，并且dynamic算法的增长幅度明显比greedy算法的要低.而图6展示的是匿名成功率的趋势.匿名成功率是指在连续查询期间，成功获得匿名查询占总查询量的百分比.从图中可以得出结论，随着匿名隐私度的增大，匿名成功率在降低[10].但是总体来看，dynamic算法的匿名成功率要远高于greedy算法.从两张图的对比结果来看，贪心匿名算法并不能保证全局最优，而使用动态规划算法可以保证全局最优性.

图5 匿名处理时间Fig.5 Anonymous processing time

图6 匿名成功率Fig.6 Anonymous success rate

3.2.2 dynamic算法与GP算法、DP算法和Naive算法的比较

如图7所示的是4种算法的轨迹扭曲度随着匿名隐私度的变化情况.从图中可以看出，随着匿名隐私度的增加，轨迹扭曲度也在增加，呈现出上升的趋势.其中，Naive算法的轨迹扭曲度最大，因为在初始时刻形成的匿名集，并没有考虑未来的运动方向和运动速度，因此随着匿名隐私度的增大，扭曲度会快速变大.

图中可以看出GP算法的轨迹扭曲度始终都比DP算法的要大，充分证明了动态规划算法的全局最优性.同时dynamic算法的轨迹扭曲度比DP算法的还要小，证明了dynamic算法更好，因为dynamic算法是根据真实用户的运动轨迹进行匿名查询的，而DP算法是根据历史轨迹进行匿名查询的，dynamic算法的匿名轨迹更加靠近真实用户的运动轨迹，因此扭曲度更小.

图7 轨迹扭曲度Fig.7 Track twist

4 结语

本文主要研究基于LBS的连续查询位置隐私保护模型的动态规划算法，描述了现有的静态匿名算法不适用于连续查询的原因及其可能产生的问题，并提出了速度相似度算法和位置扭曲度算法，充分考虑匿名用户的未来运动速度、方向和匿名框的范围大小，在查询有效期内使用动态规划算法，将真实用户的运动轨迹扩展成匿名框的运动轨迹，并将实验结果与贪心算法、基于轨迹的贪心算法、基于轨迹的动态规划算法和初始时刻形成匿名集作为查询有效期内的匿名算法进行了比较，证明本文提出的动态规划算法明显优于以上现有算法.

[1] JIA Jin-ying, ZHANG Feng-li. Overview of location privacy protection technology[J].Application Research of Computers,2013,30(3):641-646.

[2] 潘 晓，郝 兴，孟小峰.位置隐私研究综述[J].计算机科学与探索,2007，1(3)：268-281.

[3] PFITZMANN A,KHNTOPP M. Anonymity，unobservabi- lity and pseudonymity a proposal for terminology[J]. Lecture Notes in Computer Science,2001, (2009): 1-9.

[4] Marco Gruteser，Dirk Grunwald. Anonymous usage of location-based services through spatial and temporal cloaking[C]// Department of Computer Science University of Colorado at Boulder. The First International Conference on Mobile System，Application，and Services. San Francisco:CA,2003：31-42.

[5] Pan Xiao, Hao Xing, Meng Xiaofeng. Privacy preserving towards continuous query in location-based services[J].Journal of Computer Research and Development,2010，47(1)：121-129.

[6] Chow C Y，Mokbel M F，Enabling privacy continuous queries for revealed user locations[C]//Anonymous.Proceedings of the 10th International Symposium on Advances in Spatial and Temporal Databases. Boston：Springer，2007：258-275.

[7] Xu T，Cai Y.Location anonymity in continuous location-based services[C]// Anonymous.Proceedings of the 15th ACM International Symposium on Advances in Geographic Information Systems. Seattle：ACM Press，2007：39.

[8] Brinkhoff T.A framework for generating network-based moving objects [J].An Int Journal on Advances of Computer Science for Geographic Information Systems (GeoInformatica),2002,6(2):153-180.

[9] 王一蕾，周 浩，吴英杰，等.位置服务中连续查询隐私保护的动态规划算法[J].华中科技大学学报，2013，41(Z2):279-284.

[10] 胡文领，王永利.QR-TCM:具有质量保证的位置服务隐私保护模型[J].计算机科学，2014，41(4):95-98.

The Dynamic Programming Algorithm on Privacy Protection Model of Continuous Location Queries Based on LBS

LeiJianyun,ZhangLeizhong

(College of Computer Science, South-central University for Nationalities, Wuhan 430074，China)

Most of the existing algorithms are static position for privacy, if the static algorithm applied in dynamically continuous query, it will lead to the disclosure of position privacy, An improved dynamic programming algorithm based on continuous queries is proposed, designed to protect the user's location privacy, The simulation results show that: The algorithm outperforms the existing methods in terms anonymous processing time, anonymous success rate and track twist.

location-based services; loss of privacy; K- Anonymous; continuous query; dynamic programming

2015-07-02

雷建云(1972-)，男，教授，研究方向：信息安全，E-mail：leijianyun@mail.scuec.edu.cn

湖北省自然科学基金资助项目(2013CFB445)

TP393.08

A

1672-4321(2015)03-0083-05