CN106953876B - 一种基于语义上下文的位置隐私保护方法 - Google Patents

Abstract

本发明公开了一种基于语义上下文的位置隐私保护方法，包括如下步骤：(1)中心匿名服务器初始化地图数据，将地图数据模型化为公路网络；(2)用户根据需求发起查询，将定位信息，查询内容，隐私需求及身份信息封装成消息Q发送给中心匿名服务器；(3)中心匿名服务器根据Q，分析确定用户在路网上的位置Loc,初始化匿名集S＝{Loc}，初始化缓冲匿名集ES＝{}和ES’＝{S}。本发明具有在匿名成功率及降低匿名集大小两方面具有良好的效果等优点。

Description

一种基于语义上下文的位置隐私保护方法

技术领域

本发明涉及一种隐私保护技术，尤其涉及一种基于语义上下文的位置隐私保护方法，该位置隐私保护方法为一种基于语义上下文并且考虑了移动用户在不同语义位置的隐私保护方法。

背景技术

在科技发展水平极高的今天，定位技术已不仅仅局限于军事用途，随着移动设备的普及被广泛应用到人们日常生活中，如导航，查询等。基于定位技术与移动设备，一种新型的数据请求方式应运而生--基于位置的服务(Location-based Service：LBS)技术；该方式根据用户的定位，为用户提供各类服务。例如，用户开启某购物应用程序后，购物系统根据用户的定位信息推荐一些靠近用户位置的商铺信息；再如，用户到某一地方后，打开地图应用程序，查询附近的酒店，超市等。基于定位的服务改变了人们的生活方式和出行方式，但问题也随之而来，用户享受这一类服务的前提是提供自身的位置信息，个人查询信息等，这将会直接或间接泄露用户隐私信息。例如，用户Alice请求其所在位置附近的酒店，则可能暴露用户所在的位置；再如，用户Alice基于定位导航到某专科医院，则可以推测出用户可能存在健康问题。

精确的位置信息可以确保用户享受精确的位置服务，但精确的位置信息也可能严重损害用户的隐私安全；如何平衡用户隐私保护程度与用户享受的服务质量是LBS中隐私保护的重要研究课题之一。针对LBS中的隐私保护问题，学者们进行了大量的研究，这些研究大致可以分类以下两类：1)保护用户的位置；2)保护用户的身份。假位置、空间转换、隐匿空间等是最常用的位置隐私保护方法。假位置是指随机伪造一个假的位置代替用户的真实位置发起查询，为保证服务质量，该方法通常会限定一个范围，伪造的位置仅能在该范围内；空间转换的主要思想是将用户所在位置进行平移或旋转得到一个新的位置，使用新的位置代替用户所在位置发起查询；隐匿空间的主要思想是将用户所在位置拓展为一个区域，使用该区域代替用户所在位置发起查询，通常对隐匿空间还设定一些其他的要求，如隐匿空间内用户数目不少于K。

针对身份保护方面，常用的方法有：假名，混合区域等。假名主要思想是使用伪造的身份代替用户真实身份发起查询；混合区域是指在路网上设定一些区域，用户进入区域后遵守如下约定：不能发起查询，随机与区域内其他用户进行身份交换。当用户离开区域后，攻击者所看到的用户信息并非其真实身份。

上述方法虽然在一定程度上保护了用户的隐私信息，但有的还存在一些弱点，容易被攻击利用；例如假位置方法中所随机伪造的位置可能位于不合理的地点，如某些禁止船只通行的河里；隐匿空间如包含不合理的区域，则攻击者可以缩小隐匿空间的面积，增加定位用户所在位置的概率。此外，区域中除了用户数，路段数过少会导致用户隐私泄露之外，区域中的语义信息也是导致用户隐私泄露的因素之一，如用户数次在某一个专科医院发起查询，攻击者则可从专科医院这一语义位置推测用户可能暂时在该医院治疗，从而推测该用户存在健康问题。现存方法中，考虑了语义因素的方法较少，具体如下：

1)Xue等人的文章《Location Diversity:Enhanced Privacy Protection inLocation Based Services》提出每次查询中必须包含L个不同语义类型的位置，从而攻击者无法得知用户发起查询位置的语义，但该方法无考虑各位置语义对用户而言敏感程度不同的情况，仍容易被攻击者推理识破；

2)L.Byoungyoung等人的文章《Protecting location privacy using locationsemantics》使用用户的停留时间来区分不同的语义，匿名时选择L个语义不同的位置聚集一起，从而避免隐私泄露，该方法也存在局限性，不同的语义也可能拥有相同的停留时间，例早上8时经过A处停留20分钟，A可能是餐厅，用户在A处就餐，A处也可能是学校，用户护送人上学；因此，停留时间无法清晰区分各类语义。

此外在现实中，移动用户在道路上移动，但上述工作的地图模型皆为欧几里得空间模型，而欧几里得空间中存在很多用户无法到达的区域。因此学者们又提出了一些结合路网与位置语义的位置隐私保护方法，例如：

3)Damiani M L等人的文章《The PROBE Framework for the PersonalizedCloaking of Private Locations》提出的Probe模型考虑每一类语义位置被访问的概率不同，使用流行度对各类语义进行描述，并将语义分为敏感与非敏感的，然后构造匿名区域来实现保护隐私；

4)Li等人的文章《Sensitive Semantics-Aware Personality Cloaking onRoad-Network Environment》将包含位置语义的路网图用泰森多边形进行划分，然后针对敏感和非敏感语义位置分布进行隐私保护。

上述方法虽然在路网的环境下考虑了语义情况，但其执行过程中仅仅为了达到用户隐私需求，并无考虑匿名集是否最优，匿名集大小等情况，即如果匿名集中包含大量的敏感语义位置，则需要更多的非敏感语义位置来进行淡化。这样构成的匿名集虽然满足隐私需求，但其包含较多的位置，导致通信开销与查询开销大，从而影响用户的服务质量。

因此，设计算法时，不仅仅要满足用户隐私需求，还要尽可能使用户享受较高的服务质量，即降低用户等待时间，降低查询开销。

发明内容

本发明的目的在于克服现有技术的缺点与不足，提供一种基于语义上下文的位置隐私保护方法，该位置隐私保护方法在路网环境下，保证用户享受个性化隐私保护的同时，提出基于语义敏感度缺失值的概念，构造包含敏感语义位置较少的匿名集，以降低匿名集的大小，减少通讯开销及查询开销，确保用户享受到质量高的服务。

本发明的目的通过以下技术方案实现：一种基于语义上下文的位置隐私保护方法，包括如下步骤：

(1)中心匿名服务器初始化地图数据，将地图数据模型化为公路网络；

(2)用户根据需求发起查询，将定位信息，查询内容，隐私需求及身份信息封装成消息Q发送给中心匿名服务器；

(3)中心匿名服务器根据Q，分析确定用户在路网上的位置Loc,初始化匿名集S＝{Loc}，初始化缓冲匿名集ES＝{}和ES’＝{S}。

所述中心匿名服务器依据以下步骤构造匿名集：

1)设缓冲匿名集ES’的元素数目为num,对ES’所有元素按缺失值升序排列；对于ES’中的元素S_i，其中1≤i≤num且S_i为节点集，遍历集合S_i中所有节点的邻居，设集合S_i的节点数目为m_i，其中1≤i≤num，将集合S_i的m_i个节点的邻居分别与S_i组合，得到

个新的集合，组合时，邻居为交叉路口的优先，其次是非敏感的语义位置，最后是敏感语义位置，然后按添加顺序计算集合S_j的敏感率r_Sj，如r_Sj不超过θ，返回S_j作为匿名集，匿名结束，其中

否则，ES＝ES∪{S_j}；

2)清空缓冲匿名集ES’；此时，如果|ES|>Cmax，在缓冲匿名集ES中选取缺失值较小的前Cmax个元素加入ES’；否则将ES全部元素加入ES’；最后清空ES；

3)判断缓冲匿名集ES’中任意一个元素S_i所包含的节点数是否大于Lmax，1≤i≤Cmax，S_i为节点集，如S_i所包含的节点数大于Lmax，算法终止，匿名失败，返回空集；否则转步骤1)。

所述位置隐私保护方法采用缓冲匿名集的方式结合局部最优和全局最优，用两个由用户定义大小的缓冲匿名集ES与ES’来寻找最优的匿名集。

在步骤(3)中，构造的匿名集进行优劣判断，判断依据为：流行度度缺失值越小的匿名集越好，缺失值的计算采用如下公式：

其中，S为匿名集，pop_S()表示计算匿名集S中某一类语义流行度之和，pop_s(Sens)表示匿名集S中对用户敏感的语义流行度之和；pop_s(.)表示匿名集S总的流行度之和。

本发明在移动用户发起查询时，为移动用户提供一种位置隐私保护机制。该机制使用流行度缺失值的方式，结合缓冲匿名集，每一轮从缓冲匿名集中选择最接近用户所要求的敏感率的匿名集，即选择缺失值最小的匿名集，作为候选匿名集为用户构造匿名集。在机制中，缓冲匿名集的大小根据用户的需求来指定，满足其个性化需求。使用该机制，匿名服务器在构造匿名集时，可以保证有较高的匿名成功率，且在保证用户隐私的情况下，所构造的匿名集较小，以降低请求服务数据时的通信开销和查询开销，降低用户的等待时间，提高用户享受的服务质量。最后，本发明公开了机制的执行过程，实施例证明其在匿名成功率及降低匿名集大小两方面具有较好的效果。

本发明相对于现有技术，具有如下的优点与有益效果：

本发明采用缓冲匿名集的方式，使用全局最优和局部最优相结合的方法，在内存开销较小的情况下构造出趋向于全局最优的匿名集，以在满足用户隐私要求的前提下，降低匿名集的平均大小，提高用户的服务质量；其次，本发明提出缺失值的概念，每一轮优先选择缺失值最小的候选匿名集，以缩短匿名集构造时间，提高匿名成功率。

附图说明

图1是本发明涉及的用户查询过程示意图。

图2是本发明方法的详细流程图。

图3(a)是本发明实施例所使用的奥登堡市路网模型。

图3(b)是本发明实施例所使用的路网子图。

具体实施方式

本节详细讲解本发明的具体算法过程，接着结合实施例及附图对本发明方法作进一步解释。

实施例

本发明的基于语义上下文的位置隐私保护方法，首次提出缓冲匿名集方式，基于缓冲匿名集，帮助用户完成匿名集构造的同时，使匿名集中包含较少的敏感语义位置，即使匿名集相对较小，从而使用户可以享受较高的服务质量。由于用户一般是在道路上活动，路网模型更符合实际情况，因此本发明使用路网模型对地图进行建模。其次，本发明方法考虑的位置语义，将地图上的位置语义着附在距离其最近的道路交叉点上，即部分道路交叉点包含语义信息，这一类道路交叉点对用户而言具有一定的敏感性。本发明中用户发起查询享受服务的完整过程如图1所示，包含以下步骤。

第一步：用户通过移动设备主动请求定位装置对用户进行定位；

第二步：用户根据实际需要，向中心匿名服务器发起基于位置的隐私查询；

第三步：中心匿名服务器根据用户请求，为用户构造匿名集，匿名集的构造过程如图2所示；

第四步：中心匿名服务器使用匿名集代替用户真实位置向LBS服务器发起查询；

第五步：LBS服务器根据中心匿名服务器发来的查询，检索数据库，将符合要求的数据发回给中心匿名服务器；

第六步：中心匿名服务器将接收到的数据过滤后，回发给移动用户。

本发明的核心方法主要作用于第三步：构造符合用户隐私要求的最优匿名集。本发明涉及到的概念或模块如下。

定义1：语义位置流行度，用pop表示，衡量用户出现在该语义位置的概率，pop∈[0,1)。

定义2：位置语义类型，用pt表示，描述语义的具体含义，如医院，学校，娱乐场所等。

定义3：语义位置路网，用无向图G＝(V,E,pts,pops)表示。其中：V是顶点集，每个顶点是一个道路交叉点；E是边集，每条边代表一条路段，连接着两个顶点。pts为路网的语义类型集合，pops为路网的语义流行度集合。本方法中，路段的语义位置信息着附在距离该位置最近的顶点上，即V中部分节点包含语义信息，约定对无着附语义信息的顶点称为“交叉路口”，着附了语义的顶点称为语义位置。

定义4：匿名集，用S表示，是G的子集。

定义5：缓冲匿名集，将匿名集缓冲，其所有元素皆为候选匿名集。

定义6：用户配置文件，使用Pfile表示，Pfile＝{longitude，latitude，ID，PTs，θ，Q，Lmax，Cmax}。其中longitude与latitude表示用户所在位置的经纬度；ID为用户身份；PTs为对用户而言敏感的语义类型；θ为匿名集S的敏感值要求；Q为用户查询；Lmax表示匿名集S中元素个数不能超过Lmax，Cmax表示缓冲匿名集中存放元素的个数不能超过Cmax。

定义7：敏感率(Sensitive ratio),用r表示，用于度量匿名集的敏感程度。对给定的匿名集S的敏感率r_S由公式1定义：

r_S＝pop_S(Sens)/pop_S(.)，公式1

其中，pop_S(Sens)表示匿名集S中节点的语义类型在PTs内的流行度之和，pop_S(.)表示匿名集S中所有节点流行度之和。

定义8：θ-安全匿名集，指敏感率不超过θ的匿名集。

定义9：流行度缺失值用dp表示，匿名集S达到θ-安全前所需的流行度值记为dp_S，其定义如公式2所示：

模块1：邻居查找模块。查找集合中所有节点的邻接节点。

模块2：敏感率计算模块。依据公式1计算匿名集S的敏感率r_S。

模块3：定位模块。根据用户发送的经纬度确定用户所在的位置。

本发明主要部署在中心匿名服务器上，中心匿名服务器主要完成如下两个工作：1)接受用户请求，并为用户构造最优匿名集；2)当LBS服务器将结果返回之后，需要对结果进行过滤，仅将符合用户要求的数据发给用户。匿名集中包含的节点越多，LBS服务器需要执行的查询越多，时间消耗越多，因此匿名服务器的目标是：如何在确保用户隐私要求的前提下，尽可能选择包含节点数最少的匿名集。这也是本发明重点解决的问题。

本发明实施例中匿名服务器采用PC仿真，并在地图模拟器(Network-basedGenerator of Moving Objects：NGMO)中执行。该模拟器预先将地图数据导入，模拟用户的查询过程，并帮助用户完成最优匿名集的构造。其详细过程如下：

第一步：用户发送请求，包括：longitude，latitude，ID，PTs，θ，Q，Lmax，Cmax；

第二步：中心匿名服务器初始化各个变量，定义匿名集S，两个缓冲匿名集ES和ES’，根据发送的经纬度确定用户所在的位置Loc。S＝{Loc}，ES＝{}，ES’＝{S}；

第三步：构造匿名集，其具体流程如图2，详细步骤如下：

1)设缓冲匿名集ES’的元素数目为num,对ES’所有元素按缺失值升序排列。对于ES’中的元素S_i(1≤i≤num，S_i为节点集)，遍历S_i中所有节点的邻居，设S_i的节点数目为m_i(1≤i≤num)，将S_i的m_i个节点的邻居分别与S_i组合，得到

个新的集合，组合时，邻居为交叉路口的优先，其次是非敏感的语义位置，最后是敏感语义位置，然后按添加顺序计算集合

的敏感率r_Sj，如果r_Sj不超过θ，则返回S_j作为匿名集，匿名结束。否则，ES＝ES∪{S_j}。

2)清空缓冲匿名集ES’。如果|ES|>Cmax，在ES中选取缺失值较小的前Cmax个元素加入ES’；否则将ES全部元素加入ES’，ES＝{}；

3)判断ES’中任意一个元素S_i(1≤i≤Cmax，S_i为节点集)所包含的节点数是否大于Lmax，如S_i所包含的节点数大于Lmax，算法终止，匿名失败，返回空集。否则转1)。

上述过程结束后，有两种结果：1)一个包含不超过Lmax个元素的集合，匿名成功；2)一个空集，匿名失败。上述步骤首次采用了缓冲匿名集的方式构造匿名集，在满足用户θ-安全的情况下，匿名集所包含的顶点数最少。

下文将介绍实施例的实施过程。本实施例包括两部分，第一部分以案例形式讲解算法具体过程；第二部分分析实施例仿真实验结果，包括算法匿名成功率和匿名集平均大小。

图3(a)为本次实施例仿真平台NGMO所用的地图模型。图3(b)为图3(a)中某部分区域的语义路网模型。其节点属性包括：语义类型及节点标号。语义类型H对应医院，O对应办公室，Sc对应学校，E对应娱乐场所，M对应超市，P对应公园，I表示没有语义的道路交叉点。

第一部分的用户配置信息如下：PTs＝{H,O}，θ＝0.5，Lmax＝3，Cmax＝1；设用户位于v1节点，即图3(b)人状图形处；所使用的各类语义位置的流行度设定为{H＝0.15，Sc＝0.2，O＝0.25，E＝0.15，M＝0.15，P＝0.1，I＝0}；

第一轮，ES’＝{S}，S＝{v1}，故集合S的邻居是v2、v5。v2为交叉路口，优先选择v2与S组成新集合S₁＝{v1,v2}，此时r_S1＝0.15/0.15＝1>0.5，不满足隐私需求，ES＝ES∪{S₁}。然后将v5与集合S组成新集合S₂＝{v1，v5}，r_S2＝0.4/0.4＝1>0.5，不满足隐私需求，ES＝ES∪{S₂}，此时ES＝{{v1,v2}，{v1,v5}}，将缓冲匿名集ES’清空。另外一个缓冲匿名集ES中元素个数为2，比Cmax大。因此根据流行度缺失值在其中ES中挑选出前Cmax个加入ES’，dp_S1＝0.15/0.5–0.15＝0.15，dp_S2＝0.4/0.5–0.4＝0.4。由于dp_S1<dp_S2，选择S₁作为较优匿名集。此时，ES’＝{{v1,v2}},ES＝{}。集合S₁中包含的位置数为2，小于Lmax，算法继续。

第二轮，缓冲匿名集ES’中只有{v1,v2}，则ES’的邻居是v5、v3、v6。按照敏感程度，优先选择v6与S₁组成新集合S₃＝{v1,v2,v6}，其敏感率r_S3＝0.15/0.4<0.5,集合S₃达到θ安全，因此直接返回S₃作为匿名集。算法终止。

如果此时不存在集合的敏感率不超过0.5，则需按第一轮的方式，将{v1,v2,v5}，{v1,v2,v6}与{v1，v2，v3}中敏感率缺失值最小的集合添加至ES’，然后判断ES’中任意一集合的节点数是否超过Lmax，如未超过Lmax，继续执行算法，直至匿名成功；如已超过Lmax则匿名失败。

第二部分：本部分仿真用户发起查询，分析算法在各方面的表现。实施例模拟用户发起查询100,000次，分析本发明实施例在匿名成功率与匿名集大小方面的表现。表1列出了本发明实施过程的详细参数：

表1

经过实施例在中心匿名服务器执行后，其仿真结果表2所示，表2表示匿名成功率、匿名集平均大小与θ的关系表。

θ	0.2	0.4	0.6	0.8
					匿名成功率	0.810345	0.982758	1	1
平均匿名集大小	12.5957	6.6491	4.4482	4.3103

表2

表2列出了匿名成功率与匿名集平均大小随θ的变化情况。在成功率方面，在θ＝0.2的情况下，即敏感度要求很严格，成功率能达到80％以上，当匿名集敏感度降至0.6时，成功率可达到百分百。在匿名集大小方面，在θ＝0.2时，匿名集的平均大小仅为12.5957。当敏感率要求降低至0.6时，平均匿名集大小仅4.3103。以上数据表明本发明以较高的成功率保障用户隐私的同时，大大降低了匿名集平均大小，使得LBS服务器在数据查询上花费较少的时间，提高用户所享受的服务质量。

综上所述，本发明提出一种基于语义上下文的位置隐私保护方法，针对现存方法仅考虑隐私保护却无平衡用户服务质量的问题，在方法中首次提出缓冲匿名集的方式，保证用户隐私的同时，为用户构造包含最少位置的最优匿名集。该方法以较高的匿名成功率保证用户隐私安全的同时，使得匿名集大小相对较小，降低了用户等待时间，提高了用户享受服务的质量。

上述实施例为本发明较佳的实施方式，但本发明的实施方式并不受上述实施例的限制，其他的任何未背离本发明的精神实质与原理下所作的改变、修饰、替代、组合、简化，均应为等效的置换方式，都包含在本发明的保护范围之内。

Claims (3)

1.一种基于语义上下文的位置隐私保护方法，其特征在于，包括如下步骤：

(1)中心匿名服务器初始化地图数据，将地图数据模型化为公路网络；

(2)用户根据需求发起查询，将定位信息，查询内容，隐私需求及身份信息封装成消息Q发送给中心匿名服务器；

(3)中心匿名服务器根据Q，分析确定用户在路网上的位置Loc,初始化匿名集S＝{Loc}，初始化缓冲匿名集ES＝{}和ES’＝{S}；

所述中心匿名服务器依据以下步骤构造匿名集：

1)设缓冲匿名集ES’的元素数目为num,对ES’所有元素按缺失值升序排列；对于ES’中的元素S_i，其中1≤i≤num且S_i为节点集，遍历集合S_i中所有节点的邻居，设集合S_i的节点数目为m_i，其中1≤i≤num，将集合S_i的m_i个节点的邻居分别与S_i组合，得到

个新的集合，组合时，邻居为交叉路口的优先，其次是非敏感的语义位置，最后是敏感语义位置，然后按添加顺序计算集合S_j的敏感率r_Sj，如r_Sj不超过用户设定的匿名集的敏感值θ，返回S_j作为匿名集，匿名结束，其中

否则，ES＝ES∪{S_j}；

2)清空缓冲匿名集ES’；此时，如果|ES|>Cmax，其中Cmax表示缓冲匿名集ES’中存放元素的最大个数，在缓冲匿名集ES中选取缺失值较小的前Cmax个元素加入ES’；否则将ES全部元素加入ES’；最后清空ES；

3)判断缓冲匿名集ES’中任意一个元素S_i所包含的节点数是否大于用户设定的匿名集中的最大元素个数Lmax，1≤i≤Cmax，S_i为节点集，如S_i所包含的节点数大于Lmax，算法终止，匿名失败，返回空集；否则转步骤1)。

2.根据权利要求1所述的基于语义上下文的位置隐私保护方法，其特征在于，在步骤(3)中，采用缓冲匿名集的方式结合局部最优和全局最优，用两个由用户定义大小的缓冲匿名集ES与ES’寻找最优的匿名集。

3.根据权利要求1所述的基于语义上下文的位置隐私保护方法，其特征在于，对步骤(3)中构造的匿名集进行优劣判断，判断依据为：流行度度缺失值越小的匿名集越好，缺失值的计算采用如下公式：

其中，S为匿名集，pop_S()表示计算匿名集S中某一类语义流行度之和，pop_s(Sens)表示匿名集S中对用户敏感的语义流行度之和；pop_s(.)表示匿名集S总的流行度之和。

Images