檀童和　重庆邮电大学通信与信息工程学院硕士研究生李志立　重庆邮电大学通信与信息工程学院硕士研究生苏艳涛　重庆邮电大学通信与信息工程学院硕士研究生



路网环境中基于Voronoi图的位置隐私保护算法

檀童和重庆邮电大学通信与信息工程学院硕士研究生
李志立重庆邮电大学通信与信息工程学院硕士研究生
苏艳涛重庆邮电大学通信与信息工程学院硕士研究生

摘要：位置隐私保护和基于位置的服务的查询服务质量是矛盾的，在实际的路网环境下，需要考虑到诸多的影响因素对位置隐私保护算法的影响。在追求位置隐私保护的过程中，如何在提供用户隐私保护的同时保证查询服务质量是近年来的研究热点。利用泰森多变形（Voronoi）划分平面区域的方法对路网图进行划分，可以在减小匿名区域的同时提高抗边权攻击能力；采用匿名区域扩展和生成哑元的融合方式来构造匿名框。只有在划分单元内用户数量严重不足的情况下，才进行划分区域扩展。仿真结果表明本文算法在保护用户位置隐私方面和抗边权攻击方面有明显的优势。

关键词：基于位置的服务；V图；边权攻击；路网

1　引言

随着无线通信技术和移动终端的迅速发展，移动终端给人们的生活带来了很大的便利。定位技术（GPS、Wi-Fi、蜂窝网）的成熟，使得移动终端（智能手机、平板电脑）能够及时、准确地获得自己的位置信息。因此，基于位置的服务得到广泛的应用。在享受位置服务的时候，移动用户必须将自己的准确位置信息以及自己的查询内容提供给位置服务提供商，但是不能保证位置服务提供商是可信的，一旦位置信息暴露必然会导致其余相关信息的泄露。

近年来，在路网环境下，研究者提出了很多的位置隐私保护算法，TingWang等提出了路网环境下的“路段多样性”思想，构造的匿名框需要包含l条路段，从而增强抗路段推断攻击的能力。为了能够提高抗路段推断攻击的能力，提出了“匿名蜂窝模型”，先对路网进行蜂窝划分，然后根据相邻路径优先成组的方式构成匿名集合。蜂窝划分存在以下缺点：蜂窝是根据到其它节点的距离来构造的，如果路段过长，匿名区域过大就会过大，这就造成服务质量下降；存在蜂窝区域相互覆盖，用户在进行匿名时，需要进行蜂窝的选择，增加搜索成本；蜂窝划分，存在死角，有部分用户不属于任何蜂窝，造成匿名失败。本文提出了“匿名环”和“匿名森林”图的结构，构造匿名环路和匿名森林，并将其发送给匿名服务器。但是构造匿名环和匿名森林存在以下缺点：每条路径上的用户数分布不均匀，容易导致边权攻击的发生；部分路段过长，会匿名区域过大，增大系统开销，降低服务质量。在星型扩展模型的基础上，提出了XStar算法模型，XStar模型能够很好地平衡服务质量和抗攻击能力之间的关系，但是该算法有以下缺点：没有密集的路段分叉结构，不能很好地保证匿名集内路段的多样性；搜索用户时，没有考虑用户分布情况。另外，本文提出了匿名算法，该方法能够很好地保障路段多样性，不存在V区重合和部分用户不在V区的情况，但是存在以下缺点：对V区用户进行整体匿名，匿名框用户数过多，影响匿名服务质量；算法只考虑到空间容忍度，没有考虑到边权攻击的情况。本文还提出了基于Voronoi划分的V-W隐私保护算法，该算法利用Voronoi图划分法构造V区，这在减小搜索区域和抗边权攻击方面有比较明显的优势，但是该算法在形成匿名框时并未考虑到个别路段跨越多个V区，这将会增加后期的搜索成本，该算法在本V区用户数不够的情况下，采用V区扩展方式来达到高的匿名成功率，这将造成匿名框区域过大，造成后期较大的搜索成本。

这些算法存在以下问题：没有考虑到可能存在的边权攻击；只是一味地扩大匿名区域来达到匿名需求，没有考虑到服务质量与匿名需求之间的平衡。

结合现有的路网位置隐私保护算法存在的一些问题，本文算法在位置隐私保护方面，将k-匿名模型和l-匿名相结合，k-匿名实现集体匿名，形成匿名框；l-匿名能够保证匿名框内路段的多样性。本算法有以下特征：采用数学上的泰森多边形方法（Voronoi）对路网图进行划分，形成一个个小的V图区域，这就有效保证匿名框内路段的多样性；采用平均信息熵来衡量抗边权攻击能力，在算法中通过构造候选匿名集的方法来提高抗边权攻击的能力；通过仿真验证了本算法具有很好的匿名成功率并且能很好地保护用户隐私。

2　Voronoi划分理论

Voronoi是最早由荷兰气候学家A·H·Thiessen提出的根据离散分布的气象站的降雨量来计算平均降雨量的方法。后期被用于平面的划分，设某平面区域Q包括n个点，表示为集合P=｛P1，P2，…Pn｝，以这n个点为中心对平面进行划分形成一个个的Voronoi区域（简称V区）V（P1），V（P1）为平面内所有到P1距离最近的点的集合：，P1为V图的生成元。

3　系统模型

位置隐私保护模型中，中心匿名服务器结构应用最为广泛。中心匿名服务器结构能够处理能力强，能降低移动终端的负担。系统包括用户端、中心匿名服务器、LBS服务器3部分，具体参见图1。

图1　中心服务器结构系统模型

匿名过程如下：移动终端提交请求信息（＜ID，Loc（x，y），k，l，query＞）到中心匿名服务器；中心匿名服务器运行EVW匿名算法，产生匿名集合S。中心匿名服务器将用户ID、S、query发送到LBS服务器；LBS服务器将查询结果返回给中心匿名服务器，中心匿名服务器完成结果的求精；中心匿名服务器将求精结果发送给请求用户，完成整个匿名过程。

4　匿名算法

为了解决V-W算法形成匿名框过大导致查询复杂度增高的问题，本文对V-W算法进行改进。不同于V-W算法，EVW算法在添加路段加入匿名框时，不再是将整条路段加入匿名框，而是将V区内部分路段加入匿名框；在需要进行V区扩展时，EVW算法需要对V区用户的数目进行一个判断，只有在严重缺少用户时才进行V区扩展。EVW算法这两点改进均能在保证匿名成功率的情况下有效的减轻后期K近邻（KNearest Neighbors，KNN）搜索的难度，从而提高基于位置服务的查询质量。匿名算法参见表1。

5　仿真分析

为了证明所提算法的性能，给出算法的匿名成功率、匿名时间、相对匿名率、边权推断攻击平均信息熵，并与传统的匿名蜂窝算法、匿名环算法、V-W算法作比较。

（1）试验环境及参数设置（见表2）

本文采用重庆市主城区路网图作为仿真对象（见图2），试验用户数据由Thomas Brinkhoff移动对象生成器产生，重庆市主城路网用户的分布情况参见图3。

（2）匿名成功率

表1　算法1

匿名成功率表示用户向系统提交匿名申请时，匿名服务器能为其成功匿名的概率，匿名成功率越高，系统性能越好。图4所示为系统匿名成功率曲线图，图4（a）显示了系统匿名成功率随平均k匿名需求变化情况。由图4可知，随着k值增大，匿名成功率稍微有点下降，这是由于随着系统匿名需求的增大，即使选中所有路段，用户数目还是不能满足匿名需求，与V-W算法相比，本文算法匿名成功率稍低，这是由于在选择路段时，只选择V区内用户，这样在k匿名指标上更不容易达到，但是本文算法匿名成功率总体维持在90%；图4（b）显示了系统匿名成功率随l值变化的情况，很显然随着路段要求的提高匿名成功率下降很快，这是由于随着用户路段数要求的提高，即使将附近V区都扩展后仍然无法满足路段数要求。本文算法为了保证服务质量，尽量不进行V区扩展，因此在匿名成功率上稍微低于其它3种算法。

表2　试验环境及参数设置

图2　重庆市主城路网V图

图3　重庆市主城路网用户分布

（3）平均匿名时间

平均匿名时间平均完成一次匿名所消耗的系统时间，时间越短，系统的性能越好。图5所示为系统平均匿名时间曲线图，图5（a）为平均匿名时间随k值的变化情况，平均系统匿名时间随着k值的增大而增大，这是由于k需求增大，系统需要花费更多的时间去搜索匿名路段，甚至是进行V区扩展。图5（b）为平均匿名时间随l值的变化情况，随着l值的增加平均匿名时间逐渐增加，这与图5（a）这种趋势的原因是一样的。由图5可知，本文算法在平均匿名时间上比匿名环算法和匿名蜂窝算法显著减少，这是由于本文算法并未一味的追求匿名成功率，而是在保证匿名成功率的同时，不进行区域的再一步扩大，这样从另一方面提高了服务质量。与V-W算法相比，平均匿名时间稍高，这是由于在生成假用户后，后面的匿名条件仍然不能满足匿名需求，还是需要进行V区扩展，这就浪费了一部分时间。但是时间相差并不是很多。

图4　系统匿名成功率曲线图

图5　系统平均匿名时间

（4）相对匿名度

相对匿名度分相对k匿名度Relk和相对l匿名度Rell。Relk表示匿名成功时，匿名集内用户数nk与用户提出的k匿名需求ki的比值，相应的Rell表示匿名集内路段数ni与用户提出的l匿名需求li的比值。很显然，Relk、Rell的值越接近1则表明匿名效果最好，Relk、Rell值的偏大会导致匿名区域的扩大，降低服务质量，图6显示了本文算法的Relk、Rell值与匿名蜂窝算法相似，明显优于匿名环算法和V-W算法。本文算法相比V-W算法之所以能在相对匿名度上有明显改进，原因是在向匿名集添加用户时，本文算法没有采取整条路段的添加方法。

图6　系统相对匿名率

（5）边权攻击平均信息熵

边权攻击平均信息熵表示系统抗边权推断攻击的能力，攻击者利用背景知识及获取的匿名集信息推断出用户分布于每条路段上的概率Pib如公式（1）所示，式中ei.w表示第i条路段上的用户数目，用边权推断平均信息熵He表示推断出用户所在路段的不确定度，如公

图7所示为平均边权推断攻击信息熵曲线图，图7 （a）为平均边权推断攻击信息熵随k值的变化情况。随着k值的变化平均边权推断攻击信息熵变化不大，这是由于各路段用户数目均足够多；随着k值的变化，路段数并不会出现明显的变化。图7（b）为平均边权推断攻击信息熵随l值的变化情况，随着l值的增大，平均边权推断攻击信息熵显著增大，这是由于路段数的增加会直接增加用户路段分布的随机性。由于V-W算法和本文算法都考虑到选择用户数目相等的路段来构造匿名框，所以平均边权推断攻击信息熵明显高于匿名环算法和匿名蜂窝算法。本文算法由于在构造匿名框时，只选择V区内路段构造匿名框，相近路段用户分布情况类似，所以这能够稍微提高平均边权推断攻击信息熵。

6　结束语

本文算法针对V-W算法进行改进，构造匿名框时，仅选择V区内部分加入准匿名集，在V区用户缺少不是很多情况下生成哑元。仿真试验证明，本文算法相比V-W算法在匿名成功率和平均匿名时间方面相差不大，但在相对匿名率方面和抗边权攻击方面有较大优势，因此本文算法更适合路网位置隐私保护环境。

参考文献

［1］徐健，徐明，林欣.路网限制环境下基于匿名蜂窝的位置隐私保护［J］.浙江大学学报，2011，45（3）:429-434.

［2］薛姣，刘向宇，杨晓春.一种面向公路网络的位置隐私保护方法［J］.计算机学报，2011，34（5）:865-878.

［3］Al-Amin Hossain，Amina Hossain，Hye-KyeomYoo，Jae-Woo Chang.H-star:Hilbert-orderbasedstarnetworkexpansioncloaking algorithm in road networks［C］. Computational Science and Engineering（CSE 2011），2011 International Conference on. IEEE，2011:81-88.

［4］T Wang，L Liu. Privacy- aware mobile services over road networks［J］. Proceedings of the VLDB Endowment，2009，2（1）: 1042-1053.

［5］赵平，马春光，高训兵.路网环境下基于Voronoi图的位置隐私保护方法［J］.计算机科学，2013，40（7）:116-120.

［6］Xinyue Fan， Jin Tu， Chaolong Ye， Fei Zhou. The research for protecting location privacy based on V-W algorithm［J］. Eurasip Journal on Wireless Communications and Networking，2014（1）: 1686-1706.

［7］Jung- Ho Um， Mi- Young Jang， Kyoung- Jin Jo， Jae- Woo Chang.Anew cloaking method supporting both K-anonymity and L-diversity for privacy protection in location-based services［C］. Parallel Distributed Processing with Applications， 2009 InternationalSymposiumon. IEEE，2009:79-85.

［8］Xinxin Liu， Xiaolin Li. Privacy preserving techniques for location based services in mobile networks［C］. Parallel and Distributed Processing Symposium Workshops PhD Forum （IPDPSW）， 2012 International Conference on. IEEE， 2012:2474- 2477.

［9］Chunguang Ma， Changli Zhou， and Songtao Yang.Avoronoibased location privacy-preserving method for continuous query in LBS［J］.International Journal of Distributed Sensor Networks， 2015，2015:1-17.

［10］Chow Chi-Yin， Mokbel Mohamed， Bao Jie， Liu Xua. Queryaware location anonymization for road networks［J］. GeoInformatica， 2011，15（3）:571-607.

［11］Atsuyuki Okabe， Barry Boots， Kokichi Sugihara. Spatial tessellations concepts and applications of voronoi diagrams［M］. Tokyo:Wiley，2000:65-115.

Location privacy protection through voronoimapcells in road network

TanTonghe， Li Zhili ，SuYantao

Abstract：Location privacy protection and query service quality of location based services is contradictory， in the actual network environment， many factors on the influence of location privacy protection algorithm should be considered. How to provide user privacy protection and ensure the quality of the query service at the same time is a hot research topic in recent years. The method of using voronoi map to divide network diagram can reduce the anonymous area and improve the edge weight attack resistance at the same time， the fusion way using of the anonymous regional extension and generating dummy is used to generate anonymous frame structure. The way of voronoi cell extension can be used under the condition of serious shortage of the number of users.The simulation results show the obvious advantage of the algorithm at location privacy protection and edge weight attack resistance.

Keywords：location based service（LBS）； voronoimap；edge weight inference； road network

收稿日期：（2016-02-20）