本发明涉及网络与信息安全领域，特别是涉及一种基于密度分布的k-匿名位置隐私保护方法及系统。
背景技术：
随着移动定位技术和无线通信技术的发展，市场上越来越多的移动设备具备gps精确定位功能，使得位置服务(location-basedservice，lbs)成为为移动用户提供的最有前途的服务之一。然而，当lbs给人们提供便利、给社会带来巨大效益的同时，人们也对使用lbs时导致敏感信息泄露的问题倍加关注。由于服务的获取需要在不同的位置服务提供商(locationservicesprovider，lsp)之间进行交互工作，用户的位置数据必须在它们之间分享。不可信的第三方通过对以上这些位置信息进行分析对比，能比较容易地获得用户的一些重要个人信息。一旦这些隐私信息落入非法的体系中，将严重威胁用户安全。
位置隐私保护方法主要分为空间匿名方法、假位置方法和加密方法。sweeney等人(“sweeney.k-anonymity:amodelforprotectingprivacy[j].internationaljournalofuncertaintyfuzzinessandknowledge-basedsystems,2012,10(05):557-570.”)提出的空间匿名方法隐私保护效果好，但该方法在匿名区域面积过大时，不仅消耗较多时间，降低查询的准确性，而且需要中心匿名服务器的协助，容易成为系统瓶颈。hwangrh等人(“hwangrh,hsuehyl,wujj,etal.socialhide:adistributedframeworkforlocationprivacyprotection[j].journalofnetwork&computerapplications,2016,76:87-100.”)提出的基于p2p的空间匿名方法实现分布式系统的k-匿名隐私保护，但是忽视了邻居节点的安全问题，而且大大增加了智能手机的各种软硬件资源开销和通信开销。kimhi等人(“kimhi,kimhj,changjw.asecureknnqueryprocessingalgorithmusinghomomorphicencryptiononoutsourceddatabase[j].data&knowledgeengineering,2017.”)提出的加密方法能够很好的保护位置隐私，但资源开销太大。而假位置方法不需要构建匿名区域，不需要ttp的协助，在移动客户端通过生成假位置实现位置匿名，能很好地弥补空间匿名方法和加密方法的不足。
目前，k-匿名是位置隐私保护的首选方法。k-匿名方法诞生在关系数据库中，使用泛化与模糊的技术手段对数据库中的关键属性值进行处理，使得泛化后的k条记录中，任意一条记录无法单独从中区分出来，从而实现位置匿名化。gruteser等人(“gruteserm,grunwaldd.anonymoususageoflocation-basedservicesthroughspatialandtemporalcloaking[c]//internationalconferenceonmobilesystems,applications.dblp,2003:31-42.”)将k-匿名方法引入到位置隐私保护中。gedik等人(“gedikb,liul.protectinglocationprivacywithpersonalizedk-anonymity:architectureandalgorithms[j].ieeetransactionsonmobilecomputing,2008,7(1):1-18.”)提出了满足用户个性化隐私需求的位置k-匿名方法，用户可以自己定义k值和匿名等级来实现个性化匿名，但该方法k值过大时实际效果较差。
在k-匿名区域构造方法的研究中，bamba等人(“bambab,liul,pestip,etal.supportinganonymouslocationqueriesinmobileenvironmentswithprivacygrid[c]//internationalconferenceonworldwideweb.acm,2008:237-246.”)提出了网格划分的方法。在该方法中，对于不同隐私度需求，提供了top-downgridcloaking和bottom-upgrid两种算法，可供选择使用。xu等人(“xuj,tangx,huh,etal.privacy-consciouslocation-basedqueriesinmobileenvironments[j].ieeetransactionsonparallel&distributedsystems,2010,21(3):313-326.”)证明了k-匿名区域的大小对查询结果准确性有很大的影响，这对匿名区域划分方法的研究提供了指导。在此基础上，zhao等人(“zhaoz,huh,zhangf,etal.ak-anonymousalgorithminlocationprivacyprotectionbasedoncircularzoning[j].journalofbeijingjiaotonguniversity,2013,37(5):13-18.”)提出了圆形区域划分匿名方法，yang等人(“yangy,wangr.rectangularregionk-anonymitylocationprivacyprotectionbasedonlbsinaugmentedreality[j].journalofnanjingnormaluniversity(naturalscience),2016,39(4):44-49.”)提出了增强现实的矩形区域划分匿名方法。这些方法在一定程度上提高了匿名效果，但没有充分考虑k-密度分布和地形地域特点。xie等人(“xiep.a-anonymouspolygonareaconstructionmethodandalgorithmbasedonlbsprivacyprotecting[j].journalofinformation&computationalscience,2015,12(15):5713-5724.”)提出了不规则多边形的k-匿名算法，通过构造不规则多边形匿名区域，缩小了匿名区域的有效面积。但该方法所采用的匿名区域生成算法时间复杂度较高，从而影响服务质量，而且，此方法只考虑了欧式空间距离，而没有考虑用户密度分布和环境的多样性。
现有的k-匿名位置隐私保护方法虽然都能较好地保护位置隐私，但都存在着共同的缺点：(1)大都选择规则几何形状构造匿名区域，没有考虑地形地域特征，攻击者可能通过地理特征排除无效区域而推断出用户的真实位置；(2)大多数没有考虑区域匿名方法因k值不足失败后，需重新采用另外的位置隐私保护方法，大大增加了预处理时间，降低了查询服务质量；(3)大多数没有考虑k-密度分布，在k值太大或k值太小的情况下，都将更容易暴露查询用户的位置隐私。
技术实现要素：
本发明的目的是提供一种基于密度分布的k-匿名位置隐私保护方法及系统，解决了现有k-匿名位置隐私保护方法没有充分考虑查询用户所在位置的地域特征以及k-密度分布的问题，有效提高k-匿名位置隐私保护方法的隐私保护效果和查询服务质量。
为实现上述目的，本发明提供了如下方案：
一种基于密度分布的k-匿名位置隐私保护方法，包括：
获取查询用户周边查找到的k-1个近邻用户位置点；
根据所述k-1个近邻用户位置点和查询用户位置点，采用快速凸包生成算法，构造多边形k匿名区域；
计算所述多边形k匿名区域的k-密度值；
将所述k-密度值分别与设定的最大密度阈值和最小密度阈值比较；
当所述k-密度值位于所述最大密度阈值和所述最小密度阈值之间时，以多边形k匿名区域的几何中心为锚点，将所述多边形k匿名区域发送给服务器以进行位置查询；
当所述k-密度值大于所述最大密度阈值时，扩大所述多边形k匿名区域，并以扩大后的多边形k匿名区域的几何中心为锚点，将所述扩大后的多边形k匿名区域发送给服务器以进行位置查询；
当所述k-密度值小于所述最小密度阈值时，在所述多边形k匿名区域内添加若干假位置点，并将所述k-1个近邻用户位置点、所述查询用户位置点以及所述假位置点发送给服务器以进行位置查询。
可选的，所述获取查询用户周边查找到的k-1个近邻用户位置点，具体包括：
在所述查询用户周边设置一个位置点为中点，扫描得到k-1个近邻用户位置点。
可选的，所述根据所述k-1个近邻用户位置点和查询用户位置点，采用快速凸包生成算法，构造多边形k匿名区域，具体包括：
在所述k-1个近邻用户位置点和查询用户位置点中选择一个横坐标最小的位置点，确定为特殊位置点，并当所述特殊位置点为多个时，在所述特殊位置点中选择一个纵坐标最小的位置点，确定为最终的特殊位置点；
选定一个方向为逆时针方向，计算除所述特殊位置点外所有剩余的每一个位置点与所述特殊位置点形成的特殊向量；
计算每个所述特殊向量与y轴负方向的夹角；
按所述夹角从小到大对所有位置点进行排序，得到一个有序集合；
按照设定时刻双端队列的状态，对所述有序集合中的每一个位置点进行遍历，构造多边形k匿名区域。
可选的，所述计算所述多边形k匿名区域的k-密度值，具体包括：
采用递归方式计算所述多边形k匿名区域的面积值；
根据所述面积值，计算所述多边形k匿名区域的k-密度值。
一种基于密度分布的k-匿名位置隐私保护方法，包括：
获取查询用户周边查找到的k-1个近邻用户位置点；
根据所述k-1个近邻用户位置点和查询用户位置点，采用快速凸包生成算法，构造多边形k匿名区域；
计算所述多边形k匿名区域的面积值；
将所述面积值分别与设定的最大面积阈值和最小面积阈值比较；
当所述面积值位于所述最大面积阈值和所述最小面积阈值之间时，以多边形k匿名区域的几何中心为锚点，将所述多边形k匿名区域发送给服务器以进行位置查询；
当所述面积值小于所述最小面积阈值时，扩大所述多边形k匿名区域，并以扩大后的多边形k匿名区域的几何中心为锚点，将所述扩大后的多边形k匿名区域发送给服务器以进行位置查询；
当所述面积值大于所述最大面积阈值时，在所述多边形k匿名区域内添加若干假位置点，并将所述k-1个近邻用户位置点、所述查询用户位置点以及所述假位置点发送给服务器以进行位置查询。
一种基于密度分布的k-匿名位置隐私保护系统，包括：
位置点获取模块，用于获取查询用户周边查找到的k-1个近邻用户位置点；
多边形k匿名区域构造模块，用于根据所述k-1个近邻用户位置点和查询用户位置点，采用快速凸包生成算法，构造多边形k匿名区域；
k-密度值计算模块，用于计算所述多边形k匿名区域的k-密度值；
比较模块，用于将所述k-密度值分别与设定的最大密度阈值和最小密度阈值比较；
第一发送模块，用于当所述k-密度值位于所述最大密度阈值和所述最小密度阈值之间时，以多边形k匿名区域的几何中心为锚点，将所述多边形k匿名区域发送给服务器以进行位置查询；
第二发送模块，用于当所述k-密度值大于所述最大密度阈值时，扩大所述多边形k匿名区域，并以扩大后的多边形k匿名区域的几何中心为锚点，将所述扩大后的多边形k匿名区域发送给服务器以进行位置查询；
第三发送模块，用于当所述k-密度值小于所述最小密度阈值时，在所述多边形k匿名区域内添加若干假位置点，并将所述k-1个近邻用户位置点、所述查询用户位置点以及所述假位置点发送给服务器以进行位置查询。
可选的，所述位置点获取模块，具体包括：
位置点获取单元，在所述查询用户周边设置一个位置点为中点，扫描得到k-1个近邻用户位置点。
可选的，所述多边形k匿名区域构造模块，具体包括：
特殊位置点确定单元，用于在所述k-1个近邻用户位置点和查询用户位置点中选择一个横坐标最小的位置点，确定为特殊位置点，并当所述特殊位置点为多个时，在所述特殊位置点中选择一个纵坐标最小的位置点，确定为最终的特殊位置点；
特殊向量计算单元，用于选定一个方向为逆时针方向，计算除所述特殊位置点外所有剩余的每一个位置点与所述特殊位置点形成的特殊向量；
夹角计算单元，用于计算每个所述特殊向量与y轴负方向的夹角；
有序集合确定单元，用于按所述夹角从小到大对所有位置点进行排序，得到一个有序集合；
多边形k匿名区域构造单元，用于按照设定时刻双端队列的状态，对所述有序集合中的每一个位置点进行遍历，构造多边形k匿名区域。
可选的，所述k-密度值计算模块，具体包括：
面积值计算单元，用于采用递归方式计算所述多边形k匿名区域的面积值；
k-密度值计算单元，用于根据所述面积值，计算所述多边形k匿名区域的k-密度值。
一种基于密度分布的k-匿名位置隐私保护系统，包括：
位置点获取模块，用于获取查询用户周边查找到的k-1个近邻用户位置点；
多边形k匿名区域构造模块，用于根据所述k-1个近邻用户位置点和查询用户位置点，采用快速凸包生成算法，构造多边形k匿名区域；
面积值计算模块，用于计算所述多边形k匿名区域的面积值；
比较模块，用于将所述面积值分别与设定的最大面积阈值和最小面积阈值比较；
第一发送模块，用于当所述面积值位于所述最大面积阈值和所述最小面积阈值之间时，以多边形k匿名区域的几何中心为锚点，将所述多边形k匿名区域发送给服务器以进行位置查询；
第二发送模块，用于当所述面积值小于所述最小面积阈值时，扩大所述多边形k匿名区域，并以扩大后的多边形k匿名区域的几何中心为锚点，将所述扩大后的多边形k匿名区域发送给服务器以进行位置查询；
第三发送模块，用于当所述面积值大于所述最大面积阈值时，在所述多边形k匿名区域内添加若干假位置点，并将所述k-1个近邻用户位置点、所述查询用户位置点以及所述假位置点发送给服务器以进行位置查询。
根据本发明提供的具体实施例，本发明公开了以下技术效果：
(1)根据查询用户所处区域的不同地形特征，构造多边形匿名区域。
(2)应用快速多边形生成算法，进一步提高了k-匿名区域生成效率。
(3)根据k-密度分布，采用区域匿名和假位置相结合的方法，进一步提高了k-匿名位置隐私保护的有效性。
本发明提高了k-匿名区域生成效率，提高了k-匿名位置隐私保护的有效性，在保证隐私保护效果的同时，进一步提高了位置查询服务质量。
附图说明
为了更清楚地说明本发明实施例或现有技术中的技术方案，下面将对实施例中所需要使用的附图作简单地介绍，显而易见地，下面描述中的附图仅仅是本发明的一些实施例，对于本领域普通技术人员来讲，在不付出创造性劳动性的前提下，还可以根据这些附图获得其他的附图。
图1为本发明基于密度分布的k-匿名位置隐私保护方法的简单框图；
图2为本发明基于密度分布的k-匿名位置隐私保护方法的流程图；
图3为本发明基于密度分布的k-匿名位置隐私保护系统的结构图；
图4为本发明真实区域地形特征图；
图5为本发明生成的多边形k-匿名区域；
图6为本发明无效匿名区域图；
图7为本发明区域匿名和假位置相结合的隐私保护区域图。
具体实施方式
下面将结合本发明实施例中的附图，对本发明实施例中的技术方案进行清楚、完整地描述，显然，所描述的实施例仅仅是本发明一部分实施例，而不是全部的实施例。基于本发明中的实施例，本领域普通技术人员在没有做出创造性劳动前提下所获得的所有其他实施例，都属于本发明保护的范围。
针对现有k-匿名位置隐私保护方法没有充分考虑查询用户当前位置所处区域的地形特征和k-密度分布等问题，为了提高查询服务质量和隐私保护效果，本发明提出一种基于密度分布的多边形k-匿名位置隐私保护方法及系统。本发明提出的多边形匿名区域构造算法，能快速构造与地形特征相吻合的匿名区域，根据k-密度阈值，应用区域匿名和假位置相结合的策略实施位置隐私保护，有效提高位置隐私保护效果和查询服务质量。
为使本发明的上述目的、特征和优点能够更加明显易懂，下面结合附图和具体实施方式对本发明作进一步详细的说明。
实施例一
本发明公开了一种基于密度分布的k-匿名位置隐私保护方法，主要解决现有基于k-匿名的位置隐私保护方法中，生成匿名区域时没有充分考虑用户所处地域的地形特征和k值密度分布的问题。如图1所示，首先在当前用户周围查找到k-1个近邻用户位置点，根据凸包计算生成一个不规则多边形区域；然后计算该多边形区域内k个用户的分布密度，根据密度参数值的大小，应用不同的策略实施位置隐私保护。当k-密度值满足设定的密度阈值时，以该多边形几何中心为锚点，将该多边形区域发送给lbs服务器进行位置查询；当k-密度值大于设定的最大密度阈值时，进一步扩大多边形匿名区域，然后以扩大后的多边形几何中心为锚点，将该多边形区域发送给lbs服务器进行位置查询；当k-密度值小于设定的最小密度阈值时，在该多边形区域内添加若干假位置点，并将k-1个近邻用户位置点、查询用户位置点以及假位置点分别发送给lbs服务器进行查询。
如图2所示，本发明提供的一种基于密度分布的k-匿名位置隐私保护方法，具体包括以下步骤。
步骤101：获取查询用户周边查找到的k-1个近邻用户位置点。具体为：
在所述查询用户周边设置一个位置点为中点，扫描得到k-1个近邻用户位置点。
步骤102：根据所述k-1个近邻用户位置点和查询用户位置点，采用快速凸包生成算法，构造多边形k匿名区域。具体为：
(1)在所述k-1个近邻用户位置点和查询用户位置点中选择一个横坐标最小的位置点，确定为特殊位置点，并当所述特殊位置点为多个时，在所述特殊位置点中选择一个纵坐标最小的位置点，确定为最终的特殊位置点p0。
(2)选定一个方向为逆时针方向，计算除所述特殊位置点p0外所有剩余的每一个位置点px与所述特殊位置点p0形成的特殊向量
(3)计算每个所述特殊向量
(4)按所述夹角从小到大对所有位置点进行排序，得到一个有序集合s＝{p0,p1,p2,…,pk-1}。
(5)按照设定时刻双端队列的状态ptpt-1p0…pb-1pb，对所述有序集合中的每一个位置点进行遍历，构造多边形k匿名区域。
步骤(5)进一步包括：
如果是p0则首先将p0入队尾，如果是p1则入队尾，如果是p2则入队首并且入队尾。
假设遍历到当前节点pi：如果pb-1pbpi能保持左转特性则继续，否则pb出队尾，如此往复直到pb-m-1pb-mpi能够满足左转特性，pt入队尾。
假设遍历到当前节点pi：如果piptpt-1能保持左转特性则继续，否则pt出队首，如此往复直到pipt-npt-n-1能够满足左转特性，pi入队首。
返回双端队列d，多边形区域构造完成。
步骤103：计算所述多边形k匿名区域的k-密度值。具体为：
采用递归方式计算所述多边形k匿名区域的面积值。
根据所述面积值，计算所述多边形k匿名区域的k-密度值。
步骤104：将所述k-密度值分别与设定的最大密度阈值和最小密度阈值比较。
步骤105：当所述k-密度值位于所述最大密度阈值和所述最小密度阈值之间时，以多边形k匿名区域的几何中心为锚点，将所述多边形k匿名区域发送给服务器以进行位置查询。
步骤106：当所述k-密度值大于所述最大密度阈值时，扩大所述多边形k匿名区域，并以扩大后的多边形k匿名区域的几何中心为锚点，将所述扩大后的多边形k匿名区域发送给服务器以进行位置查询。具体为：
当所述k-密度值大于所述最大密度阈值时，扩大所述多边形k匿名区域，直到所述k-密度值位于所述最大密度阈值和所述最小密度阈值之间时停止，然后以扩大后的多边形k匿名区域的几何中心为锚点，将所述扩大后的多边形k匿名区域发送给服务器以进行位置查询。
步骤107：当所述k-密度值小于所述最小密度阈值时，在所述多边形k匿名区域内添加若干假位置点，并将所述k-1个近邻用户位置点、所述查询用户位置点以及所述假位置点发送给服务器以进行位置查询。具体为：
当所述k-密度值小于所述最小密度阈值时，在所述多边形k匿名区域内添加若干假位置点，直到所述k-密度值位于所述最大密度阈值和所述最小密度阈值之间时停止，然后将所述k-1个近邻用户位置点、所述查询用户位置点以及所述假位置点发送给服务器以进行位置查询。
本发明提出的一种基于密度分布的k-匿名位置隐私保护方法效率高，采用的多边形区域生成方法能得到与地形特征相吻合匿名区域，用区域匿名和假位置相结合策略实施位置隐私保护，在保证查询服务质量的同时，进一步提高了隐私保护效果。尤其对于区域匿名方法失效的情况下，结合假位置的方法提高了k-匿名位置隐私保护的有效性。
实施例二
本发明是一种基于密度分布的k-匿名位置隐私保护方法，当用户需要位置查询时，首先将当前位置和查询请求发送给ttp，ttp接收到查询请求后，任意选取当前用户位置点附近的某一位置点为中心，查询到k个(包含当前查询位置)近邻用户位置点，应用凸包算法构造多边形匿名区域。然后根据设定的k-密度参数ρamx和ρmin，计算有效匿名区域的最小面积阈值(smin)和最大面积阈值(smax)，应用递归的方法计算多边形匿名区域面积s(rs)，根据区域面积大小，采用扩大匿名区域和添加假位置相结合的方法实施位置隐私保护。当s(rs)＞smax时，在该区域内添加若干假位置，ttp将查找到的近邻用户位置、添加的假位置以及当前查询用户位置分别发送给lbs服务器进行位置查询。
包括如下步骤：
获取查询用户周边查找到的k-1个近邻用户位置点。
根据所述k-1个近邻用户位置点和查询用户位置点，采用快速凸包生成算法，构造多边形k匿名区域。
计算所述多边形k匿名区域的面积值。
将所述面积值分别与设定的最大面积阈值和最小面积阈值比较。
当所述面积值位于所述最大面积阈值和所述最小面积阈值之间时，以多边形k匿名区域的几何中心为锚点，将所述多边形k匿名区域发送给服务器以进行位置查询。
当所述面积值小于所述最小面积阈值时，扩大所述多边形k匿名区域，并以扩大后的多边形k匿名区域的几何中心为锚点，将所述扩大后的多边形k匿名区域发送给服务器以进行位置查询。
当所述面积值大于所述最大面积阈值时，在所述多边形k匿名区域内添加若干假位置点，并将所述k-1个近邻用户位置点、所述查询用户位置点以及所述假位置点发送给服务器以进行位置查询。
其中，多边形k匿名区域构造过程如下：
(1a)在查询用户周围设定一个位置点为中心，扫描得到k个(包含当前查询用户位置)近邻用户位置点。
(1b)从位置点坐标中选取其横坐标最小的点，若最小的横坐标值不唯一，则选取纵坐标值同时最小的点，并将该位置点记为p0。
(1c)选定一个方向为逆时针方向，计算除p0外所有剩余的每一个点px与p0形成的向量
(1e)按夹角从小到大对所有点进行排序，依次得到一个有序集合s＝{p0,p1,p2,...,pn-1}；记某一时刻双端队列d的状态为：ptpt-1p0...pb-1pb，对s中的每一个点进行遍历。
(1f)如果是p0则首先将p0入队尾，如果是p1则入队尾，如果是p2则入队首并且入队尾。
(1g)假设遍历到当前节点pi：如果pb-1pbpi能保持左转特性则继续，否则pb出队尾，如此往复直到pb-m-1pb-mpi能够满足左转特性，pt入队尾。
(1h)假设遍历到当前节点pi：如果piptpt-1能保持左转特性则继续，否则pt出队首，如此往复直到pipt-npt-n-1能够满足左转特性，pi入队首。
(1i)返回双端队列d，多边形区域构造完成。
k-密度值计算和比较过程如下：
(2a)设定多边形k匿名区域中k-密度的最大密度阈值(ρamx)和最小密度阈值(ρmin)。
(2b)根据密度阈值计算最小面积阈值(smin)和最大面积阈值(smax)。计算公式如下：
(2c)应用递归的方法计算多边形k匿名区域的面积值s(rs)，并进行比较。
计算公式如下：
(2d)当s(rs)＜smin时，进一步扩大多边形k匿名区域面积，直到满足面积阈值。
(2e)当smin＜s(rs)＜smax时，以该多边形k匿名区域的几何中心为锚点，将该多边形k匿名区域发送给lbs服务器进行位置查询。
(2f)当s(rs)＞smax时，在多边形k匿名区域内添加若干假位置点，直到满足面积阈值，并将得到的假位置点保存到有序集合s中，得到假位置候选集s1。
假位置隐私保护方法的实施过程如下：
(3a)当s(rs)＞smax时，在多边形k匿名区域内添加若干假位置。
(3b)将m个位置(包括查找的近邻用户位置、添加的假位置、当前查询用户位置)分别发送给lbs服务器进行查询。
(3c)查询到位置数据后，lbs服务器将k个查询结果发送给ttp。
(3d)ttp求精后，将当前位置的查询结果返回给查询用户。
本发明在整个多边形k匿名位置隐私保护方法过程很简单，容易实现，区域匿名和假位置的添加都在多边形区域内通过ttp实施，在移动设备中容易实现。本发明提出的多边形匿名区域构造算法，能快速构造与地形特征相吻合的匿名区域，并且提高了匿名效率。依据k-密度参数值，计算面积阈值，根据面积阈值应用区域匿名和假位置相结合的策略实施位置隐私保护，有效提高位置隐私保护效果和查询服务质量。
实施例三
为上述目的，本发明还提供了一种基于密度分布的k-匿名位置隐私保护系统，如图3所示，包括：
位置点获取模块201，用于获取查询用户周边查找到的k-1个近邻用户位置点。
多边形k匿名区域构造模块202，用于根据所述k-1个近邻用户位置点和查询用户位置点，采用快速凸包生成算法，构造多边形k匿名区域。
k-密度值计算模块203，用于计算所述多边形k匿名区域的k-密度值。
比较模块204，用于将所述k-密度值分别与设定的最大密度阈值和最小密度阈值比较。
第一发送模块205，用于当所述k-密度值位于所述最大密度阈值和所述最小密度阈值之间时，以多边形k匿名区域的几何中心为锚点，将所述多边形k匿名区域发送给服务器以进行位置查询。
第二发送模块206，用于当所述k-密度值大于所述最大密度阈值时，扩大所述多边形k匿名区域，并以扩大后的多边形k匿名区域的几何中心为锚点，将所述扩大后的多边形k匿名区域发送给服务器以进行位置查询。
第三发送模块207，用于当所述k-密度值小于所述最小密度阈值时，在所述多边形k匿名区域内添加若干假位置点，并将所述k-1个近邻用户位置点、所述查询用户位置点以及所述假位置点发送给服务器以进行位置查询。
所述位置点获取模块201，具体包括：位置点获取单元，在所述查询用户周边设置一个位置点为中点，扫描得到k-1个近邻用户位置点。
所述多边形k匿名区域构造模块202，具体包括：
特殊位置点确定单元，用于在所述k-1个近邻用户位置点和查询用户位置点中选择一个横坐标最小的位置点，确定为特殊位置点，并当所述特殊位置点为多个时，在所述特殊位置点中选择一个纵坐标最小的位置点，确定为最终的特殊位置点。
特殊向量计算单元，用于选定一个方向为逆时针方向，计算除所述特殊位置点外所有剩余的每一个位置点与所述特殊位置点形成的特殊向量。
夹角计算单元，用于计算每个所述特殊向量与y轴负方向的夹角。
有序集合确定单元，用于按所述夹角从小到大对所有位置点进行排序，得到一个有序集合。
多边形k匿名区域构造单元，用于按照设定时刻双端队列的状态，对所述有序集合中的每一个位置点进行遍历，构造多边形k匿名区域。
所述k-密度值计算模块203，具体包括：
面积值计算单元，用于采用递归方式计算所述多边形k匿名区域的面积值；k-密度值计算单元，用于根据所述面积值，计算所述多边形k匿名区域的k-密度值。
实施例四
为实现上述目的，本发明还提供了一种基于密度分布的k-匿名位置隐私保护系统，包括：
位置点获取模块，用于获取查询用户周边查找到的k-1个近邻用户位置点。
多边形k匿名区域构造模块，用于根据所述k-1个近邻用户位置点和查询用户位置点，采用快速凸包生成算法，构造多边形k匿名区域。
面积值计算模块，用于计算所述多边形k匿名区域的面积值。
比较模块，用于将所述面积值分别与设定的最大面积阈值和最小面积阈值比较。
第一发送模块，用于当所述面积值位于所述最大面积阈值和所述最小面积阈值之间时，以多边形k匿名区域的几何中心为锚点，将所述多边形k匿名区域发送给服务器以进行位置查询。
第二发送模块，用于当所述面积值小于所述最小面积阈值时，扩大所述多边形k匿名区域，并以扩大后的多边形k匿名区域的几何中心为锚点，将所述扩大后的多边形k匿名区域发送给服务器以进行位置查询。
第三发送模块，用于当所述面积值大于所述最大面积阈值时，在所述多边形k匿名区域内添加若干假位置点，并将所述k-1个近邻用户位置点、所述查询用户位置点以及所述假位置点发送给服务器以进行位置查询。
下面通过实验说明上述实施例。
1.实验条件与性能评价标准：
本发明实验选用thomasbrinkhoff(“brinkhofft.aframeworkforgeneratingnetwork-basedmovingobjects[j].geoinformatica,2002,6(2):153-180.”)开发的基于网络的移动节点生成器，通过如图4所示的真实地图生成分布在整个区域的1000个数据节点。实验的主要参数k的取值为：1≤k≤100，优点可通过以下仿真实验进一步说明。
实验环境为：
(1)硬件环境为：intel(r)core(tm)i5-3337ucpu，1.80ghz，内存4g。
(2)软件环境为：windows7操作系统，采用myeclipse开发平台，以java编程语言实现。
2.实验内容
实验1：效率测试与分析
不同算法生成假位置的时间比较
本发明提出的多边形匿名区域生成算法通过表格形式与xie方法(“xiep.a-anonymouspolygonareaconstructionmethodandalgorithmbasedonlbsprivacyprotecting[j].journalofinformation&computationalscience,2015,12(15):5713-5724”)的不规则多边形匿名区域生成算法进行了效率对比，对比结果如表1所示。
表1不同算法匿名区域生成时间比较
从表1可以看出，k从10到100，随着k值的增加，本发明方法和基于密度分布的多边形划分方法的匿名域形成时间都在增加，并且两者的增长幅度和趋势大体相当。在相同k值的情况下，比较两种算法在构造匿名区域时所花费的时间，本发明方法的k-匿名区域生成时间比xie方法少得多。可见，与xie方法相比，本发明方法提高了匿名效率。
实验2：与其他方法的匿名区域面积比较
本发明提出的一种基于密度分布的k-匿名位置隐私保护方法通过表格形式与xie方法(“xiep.a-anonymouspolygonareaconstructionmethodandalgorithmbasedonlbsprivacyprotecting[j].journalofinformation&computationalscience,2015,12(15):5713-5724.”)、bamba方法(“bambab,liul,pestip,etal.supportinganonymouslocationqueriesinmobileenvironmentswithprivacygrid[c]//internationalconferenceonworldwideweb.acm,2008:237-246.”)、zhao方法(“zhaoz,huh,zhangf,etal.ak-anonymousalgorithminlocationprivacyprotectionbasedoncircularzoning[j].journalofbeijingjiaotonguniversity,2013,37(5):13-18.”)、yang方法(“yangy,wangr.rectangularregionk-anonymitylocationprivacyprotectionbasedonlbsinaugmentedreality[j].journalofnanjingnormaluniversity(naturalscience),2016,39(4):44-49.”)对匿名区域面积进行了对比，对比结果如表2所示。
表2不同方法匿名区域面积比较(×104m2)
由表2可以看出，随着k值的增加，尽管几种匿名区域划分方法的面积随k值的变大都在增长，但增长的速度各不相同，这是由各自划分方法的几何形状决定的。在相同k值的情况下，本发明方法和xie方法最小，说明多边形区域匿名方法查询准确性更高。从表2可以看出：当k值在(0，20)之间时，本发明方法的面积略大于xie方法；当k>20时，两种方法的面积增长趋势完全相同。这是因为本发明方法设置了密度阈值。
实验3：有效性分析
本发明生成的多边形k-匿名区域如图5所示，本发明提出的多边形匿名区域与圆形、矩形匿名区域的无效区域进行比较，如图6所示。多边形匿名区域中的无效区域面积明显小于矩形和圆形，证明多边形匿名区域具有更好的隐私性和查询准确性。
实验4：熵的比较
本发明区域匿名和假位置相结合的隐私保护区域图如图7所示，本发明提出的基于密度分布的k-匿名位置隐私保护方法通过表格形式与random方法、lu方法(“luh,jensencs,manly.pad:privacy-areaaware,dummy-basedlocationprivacyinmobileservices[c]//acminternationalworkshopondataengineeringforwirelessandmobileaccess,mobide2008,june13,2008,vancouver,britishcolumbia,canada,proceedings.dblp,2008:16-27.”)中的girdummy算法和griddummy算法对熵进行对比，对比结果如表3所示。
表3不同算法假位置信息熵比较
由表3看出，随着k值的增加，几种方法的熵值都在增长，但在相同k值情况下，本发明方法熵值最大，证明本发明方法与其他三种方法相比，具有最好的隐私保护性。
通过实验对比分析，本发明在尽可能满足位置点之间较好的物理分散性和语义多样化的同时，具有更高的假位置生成效率，能有效提高位置服务质量。
本说明书中各个实施例采用递进的方式描述，每个实施例重点说明的都是与其他实施例的不同之处，各个实施例之间相同相似部分互相参见即可。对于实施例公开的系统而言，由于其与实施例公开的方法相对应，所以描述的比较简单，相关之处参见方法部分说明即可。
本文中应用了具体个例对本发明的原理及实施方式进行了阐述，以上实施例的说明只是用于帮助理解本发明的方法及其核心思想；同时，对于本领域的一般技术人员，依据本发明的思想，在具体实施方式及应用范围上均会有改变之处。综上所述，本说明书内容不应理解为对本发明的限制。
1.一种基于密度分布的k-匿名位置隐私保护方法，其特征在于，包括：
获取查询用户周边查找到的k-1个近邻用户位置点；
根据所述k-1个近邻用户位置点和查询用户位置点，采用快速凸包生成算法，构造多边形k匿名区域；
计算所述多边形k匿名区域的k-密度值；
将所述k-密度值分别与设定的最大密度阈值和最小密度阈值比较；
当所述k-密度值位于所述最大密度阈值和所述最小密度阈值之间时，以多边形k匿名区域的几何中心为锚点，将所述多边形k匿名区域发送给服务器以进行位置查询；
当所述k-密度值大于所述最大密度阈值时，扩大所述多边形k匿名区域，并以扩大后的多边形k匿名区域的几何中心为锚点，将所述扩大后的多边形k匿名区域发送给服务器以进行位置查询；
当所述k-密度值小于所述最小密度阈值时，在所述多边形k匿名区域内添加若干假位置点，并将所述k-1个近邻用户位置点、所述查询用户位置点以及所述假位置点发送给服务器以进行位置查询。
2.根据权利要求1所述的一种基于密度分布的k-匿名位置隐私保护方法，其特征在于，所述获取查询用户周边查找到的k-1个近邻用户位置点，具体包括：
在所述查询用户周边设置一个位置点为中点，扫描得到k-1个近邻用户位置点。
3.根据权利要求1所述的一种基于密度分布的k-匿名位置隐私保护方法，其特征在于，所述根据所述k-1个近邻用户位置点和查询用户位置点，采用快速凸包生成算法，构造多边形k匿名区域，具体包括：
在所述k-1个近邻用户位置点和查询用户位置点中选择一个横坐标最小的位置点，确定为特殊位置点，并当所述特殊位置点为多个时，在所述特殊位置点中选择一个纵坐标最小的位置点，确定为最终的特殊位置点；
选定一个方向为逆时针方向，计算除所述特殊位置点外所有剩余的每一个位置点与所述特殊位置点形成的特殊向量；
计算每个所述特殊向量与y轴负方向的夹角；
按所述夹角从小到大对所有位置点进行排序，得到一个有序集合；
按照设定时刻双端队列的状态，对所述有序集合中的每一个位置点进行遍历，构造多边形k匿名区域。
4.根据权利要求1所述的一种基于密度分布的k-匿名位置隐私保护方法，其特征在于，所述计算所述多边形k匿名区域的k-密度值，具体包括：
采用递归方式计算所述多边形k匿名区域的面积值；
根据所述面积值，计算所述多边形k匿名区域的k-密度值。
5.一种基于密度分布的k-匿名位置隐私保护方法，其特征在于，包括：
获取查询用户周边查找到的k-1个近邻用户位置点；
根据所述k-1个近邻用户位置点和查询用户位置点，采用快速凸包生成算法，构造多边形k匿名区域；
计算所述多边形k匿名区域的面积值；
将所述面积值分别与设定的最大面积阈值和最小面积阈值比较；
当所述面积值位于所述最大面积阈值和所述最小面积阈值之间时，以多边形k匿名区域的几何中心为锚点，将所述多边形k匿名区域发送给服务器以进行位置查询；
当所述面积值小于所述最小面积阈值时，扩大所述多边形k匿名区域，并以扩大后的多边形k匿名区域的几何中心为锚点，将所述扩大后的多边形k匿名区域发送给服务器以进行位置查询；
当所述面积值大于所述最大面积阈值时，在所述多边形k匿名区域内添加若干假位置点，并将所述k-1个近邻用户位置点、所述查询用户位置点以及所述假位置点发送给服务器以进行位置查询。
6.一种基于密度分布的k-匿名位置隐私保护系统，其特征在于，包括：
位置点获取模块，用于获取查询用户周边查找到的k-1个近邻用户位置点；
多边形k匿名区域构造模块，用于根据所述k-1个近邻用户位置点和查询用户位置点，采用快速凸包生成算法，构造多边形k匿名区域；
k-密度值计算模块，用于计算所述多边形k匿名区域的k-密度值；
比较模块，用于将所述k-密度值分别与设定的最大密度阈值和最小密度阈值比较；
第一发送模块，用于当所述k-密度值位于所述最大密度阈值和所述最小密度阈值之间时，以多边形k匿名区域的几何中心为锚点，将所述多边形k匿名区域发送给服务器以进行位置查询；
第二发送模块，用于当所述k-密度值大于所述最大密度阈值时，扩大所述多边形k匿名区域，并以扩大后的多边形k匿名区域的几何中心为锚点，将所述扩大后的多边形k匿名区域发送给服务器以进行位置查询；
第三发送模块，用于当所述k-密度值小于所述最小密度阈值时，在所述多边形k匿名区域内添加若干假位置点，并将所述k-1个近邻用户位置点、所述查询用户位置点以及所述假位置点发送给服务器以进行位置查询。
7.根据权利要求6所述的一种基于密度分布的k-匿名位置隐私保护系统，其特征在于，所述位置点获取模块，具体包括：
位置点获取单元，在所述查询用户周边设置一个位置点为中点，扫描得到k-1个近邻用户位置点。
8.根据权利要求6所述的一种基于密度分布的k-匿名位置隐私保护系统，其特征在于，所述多边形k匿名区域构造模块，具体包括：
特殊位置点确定单元，用于在所述k-1个近邻用户位置点和查询用户位置点中选择一个横坐标最小的位置点，确定为特殊位置点，并当所述特殊位置点为多个时，在所述特殊位置点中选择一个纵坐标最小的位置点，确定为最终的特殊位置点；
特殊向量计算单元，用于选定一个方向为逆时针方向，计算除所述特殊位置点外所有剩余的每一个位置点与所述特殊位置点形成的特殊向量；
夹角计算单元，用于计算每个所述特殊向量与y轴负方向的夹角；
有序集合确定单元，用于按所述夹角从小到大对所有位置点进行排序，得到一个有序集合；
多边形k匿名区域构造单元，用于按照设定时刻双端队列的状态，对所述有序集合中的每一个位置点进行遍历，构造多边形k匿名区域。
9.根据权利要求6所述的一种基于密度分布的k-匿名位置隐私保护系统，其特征在于，所述k-密度值计算模块，具体包括：
面积值计算单元，用于采用递归方式计算所述多边形k匿名区域的面积值；
k-密度值计算单元，用于根据所述面积值，计算所述多边形k匿名区域的k-密度值。
10.一种基于密度分布的k-匿名位置隐私保护系统，其特征在于，包括：
位置点获取模块，用于获取查询用户周边查找到的k-1个近邻用户位置点；
多边形k匿名区域构造模块，用于根据所述k-1个近邻用户位置点和查询用户位置点，采用快速凸包生成算法，构造多边形k匿名区域；
面积值计算模块，用于计算所述多边形k匿名区域的面积值；
比较模块，用于将所述面积值分别与设定的最大面积阈值和最小面积阈值比较；
第一发送模块，用于当所述面积值位于所述最大面积阈值和所述最小面积阈值之间时，以多边形k匿名区域的几何中心为锚点，将所述多边形k匿名区域发送给服务器以进行位置查询；
第二发送模块，用于当所述面积值小于所述最小面积阈值时，扩大所述多边形k匿名区域，并以扩大后的多边形k匿名区域的几何中心为锚点，将所述扩大后的多边形k匿名区域发送给服务器以进行位置查询；
第三发送模块，用于当所述面积值大于所述最大面积阈值时，在所述多边形k匿名区域内添加若干假位置点，并将所述k-1个近邻用户位置点、所述查询用户位置点以及所述假位置点发送给服务器以进行位置查询。
技术总结