基于位置语义和查询概率的假位置选择算法

王洁，王春茹，马建峰，李洪涛

（1.山西师范大学数学与计算机科学学院，山西 临汾 041099；2.西安电子科技大学网络与信息安全学院，陕西 西安 710071）

1 引言

近年来，随着手机等移动智能终端的普及和移动互联网技术的发展，基于位置的服务（LBS,location based service）在日常生活中得到广泛的应用。用户下载LBS 应用程序后，使用这些应用程序可以很方便地向LBS 服务器发送请求，从而获取与某个兴趣点相关的信息，如交通导航信息、附近的餐厅等。然而，人们在享受LBS 提供便利的同时，也面临着严重的隐私泄露风险。不受信任的LBS 服务器会获取用户的查询数据，如用户的位置、提交的查询类型等。根据这些数据，LBS 服务提供者可以进一步推断出用户的一些个人敏感信息，如目标用户的社会关系、家庭住址、日常行为等；也可以直接追踪用户或泄露用户的个人信息，这将导致用户的隐私泄露，因此，位置隐私的保护变得越来越重要。

针对位置隐私保护问题，国内外研究学者提出了多种用户位置隐私保护方法，其中k-匿名是最常用的方法之一。现有的位置k-匿名技术通常依靠可信第三方服务器将用户的准确位置泛化为一个包含k 个用户（包含目标用户）的区域[1-3]。这样不受信任的LBS 服务器很难从此区域中区分出目标用户的真实位置。但是上述隐私保护模型存在一定的局限性。首先，存在单点故障。因为它依赖于一个受信任的匿名服务器，一旦匿名器服务器被对手控制，那么所有用户的隐私都将受到损害；其次，很难平衡服务可用性和位置隐私，如果泛化区域过大，会影响服务质量，泛化区域过小，又容易造成位置泄露。为了在不受第三方影响的情况下保护用户的位置隐私，有研究者提出了同样能实现k-匿名的假位置技术，但是如何选择合适的假位置是一个难题。现有的假位置选择方案考虑到对手已掌握了位置查询概率，提出基于熵度量选择虚拟位置的方法，保护了用户的位置隐私[4-6]。然而当真实位置和k-1 个假位置都是同一语义类型时，对手还是可以很容易地推断出用户的个人信息，例如所有的地点都位于学校时，对手就能推断出用户的身份可能是教师或者学生，因此，在选择假位置时要充分考虑位置的语义信息，生成的假位置集需满足语义差异性。现有的方案[7-8]大多采用欧氏距离或余弦距离度量语义差异度，计算量庞大，影响算法的执行效率，降低用户的服务质量。文献[9]采用树形结构组织所有位置，并根据位置节点间的跳数来计算语义距离，将语义距离作为语义差异度的度量标准，使生成的假位置集满足语义差异性，但是当假位置集中包含湖泊、森林等访问概率较低的位置时，对手很容易将它们过滤；此外，如果生成的假位置都在真实位置附近，对手就会将真实位置锁定在一个小区域，进而推测出真实位置。

本文充分考虑了用户边信息和背景知识可能被攻击者手利用的情况，提出了一种基于位置语义和查询概率的最大最小假位置选择（MMDS,maximum and minimum dummy selection）算法。在选择假位置时，首先保证最后生成的假位置集中k个位置的语义满足差异性；然后，使假位置集中k个位置间的查询概率尽量相近；最后，使假位置间的地理位置尽量分散，并针对考虑位置之间在地图上分散且查询概率尽可能相近这2 个因素进行了多目标优化。本文算法解决了攻击者具有边信息可以排除部分假位置的问题，能有效保护用户的位置隐私。仿真实验分别从假位置集生成时间、物理分散度、语义差异性以及位置熵这4 个方面将本文算法与已有算法进行对比，验证了本文算法的有效性。

2 预备知识

2.1 系统架构

本文采用的系统架构如图1 所示，主要由Wi-Fi接入点（AP,access point）、LBS 服务器及智能终端三部分组成。

图1 系统结构

目前，Wi-Fi 覆盖面较广，计算能力和存储能力也较强。本文系统中Wi-Fi AP 可提供网络支持，计算并存储当前覆盖范围内所有位置的历史查询概率，在其无线电范围内收集位置语义信息，并生成和保存位置语义树。对任意Wi-Fi AP，它所覆盖范围内的位置是相对稳定的，所以位置语义树和历史查询概率不需要频繁变化。

各种智能终端设备用于执行假位置选择算法，生成假位置集，并筛选由LBS 服务器返回的候选结果集。

LBS 服务器提供基于位置的服务。本文假设攻击者能够成功攻破LBS 服务器，并且攻击者所掌握的边信息包括用户的匿名机制、位置的历史查询概率以及位置的语义信息和地图信息。

查询前，智能终端用户首先请求Wi-Fi AP，获取当前Wi-Fi AP 覆盖范围内的地图信息、位置语义树及历史查询概率；其次，根据假位置选择机制生成满足自身隐私保护需求的k-1 个假位置；然后，用户将真实位置和k-1 个假位置发送至LBS服务器请求查询，LBS 服务器根据用户发送的位置返回候选结果集；最后，用户筛选结果，得到当前查询的目标结果。

2.2 假位置集构造原则

定义1用户的真实位置 lreal。lreal包含用户位置的地理坐标及语义信息。

定义2用户隐私需求S。以二元组(k,u)表示某用户的隐私需求S，其包含以下2 个方面含义。

1)匿名度k，表示每次查询时都发送一个真实位置和至少k-1 个假位置给服务器，且判断出真实位置的概率为。

2)语义差异度u，表示假位置集中任意2 个位置间的语义距离的最小可接受值。本文设置u=4，即对假位置集中任意 2 个位置 li和 lj，满足[dsem(li,lj)]min ≥ u(1)，则生成的假位置集中位置之间满足语义差异性。

2.3 位置地图距离计算方法

令Mapcur表示当前Wi-Fi AP 覆盖范围内的地图信息，对于任意2 个位置 li,lj(i≠ j)，位置地图距离dphy(li,lj)为2 个位置在地图信息Mapcur上的距离，其取值范围为几米到几千米。

2.4 位置查询概率距离计算方法

定义3位置查询概率（LQP,location query probability）。将每个Wi-Fi AP 将其覆盖范围内的地图作为样本空间按照网格进行划分，如图2 所示，每个网格中包含一个位置单元，确定每个位置单元的坐标，通过数据训练集来训练每个位置的查询概率。使用计算每个位置单元的历史查询概率并保存，其中，i=1,2,…,m2，ni表示某个位置单元的查询次数，表示所有位置单元的总查询次数，。

图2 样本空间划分

对于任意2 个位置 li,lj(i≠ j)，位置查询概率距离即2 个位置查询概率之间的差值，用 dque(li,lj)表示。

2.5 位置语义距离计算方法

定义4位置语义树（LST,location semantic tree）。将当前Wi-Fi AP 覆盖的所有位置根据其语义组织为一种树形结构，每个叶节点表示地图上的真实位置 lreal，每个非叶节点表示其子节点的类别，LST 的深度为h，h 的值等于LST 中分类的层数加1。

对于任意 2 个位置 li,lj(i≠ j)，语义距离dsem(li,lj)即位置语义树中2 个位置叶节点之间的跳数。下面举例说明语义距离计算方法。以某一Wi-Fi AP 覆盖的一块真实的地图信息为例，图3(a)为该区域的示意图，★表示真实位置。将图3(a)中位置分为教育与科学、行政与居住等类型，在图3(b)中显示所形成的部分LST，其叶节点表示真实位置，非叶节点表示子节点的类别。根据此LST 可以得出实验小学与职业技术学院（图中灰色实线路径）的语义距离为2，文化展览馆与社区（图中灰色虚线路径）的语义距离为6。

图3 真实地图信息及其LST

根据上述分析，最后的假位置集需要满足位置在地图上尽量分散且其历史查询概率尽可能相近，即最后的假位置集DLS 需同时满足式(2)和式(3)。

由于需要同时考虑2 个因素，可将其转化为多目标优化问题，由此本文提出一种最大最小假位置选择（MMDS）算法，该算法确保DLS 满足式(4)。

其中，li,lj∈DLS，i≠ j。dque(li,lj)+1 避免了两位置概率相同，即差值为0 的情况。为了平衡地理距离和概率差值这2 个因素，设置参数r=100。通过式(4)使假位置在地图上尽量分散且其历史查询概率尽可能相近。

3 最大最小假位置选择算法

根据假位置集构造原则，选择合适的假位置构成假位置集DLS。本文采用边选择边判断的策略，其主要思想是，选择与当前假位置集中已有位置满足语义差异的所有位置作为候选假位置集；然后，在候选假位置集中选择一个最优位置，最优位置是指由该位置构成的DLS 满足式(3)；最后，生成一个由用户所在真实位置和k-1 个假位置构成的集合DLS。算法1 给出了最大最小假位置选择算法的伪代码。

算法1最大最小假位置选择（MMDS）算法

输入真实位置 lreal，用户隐私需求S，当前Wi-Fi AP 覆盖范围内的地图信息Mapcur，位置语义树LST，位置查询概率LQP

输出假位置集DLS

算法1 的输入参数为用户的真实位置 lreal、用户隐私需求S（包含隐私需求参数k 和语义差异性需求参数u）、当前Wi-Fi AP 覆盖范围内的地图信息Mapcur、位置语义树 LST、位置查询概率LQP。首先，将地图信息Mapcur中的所有位置生成候选假位置集CLS（第1）行），然后由位置语义树LST 得到语义差异度矩阵SDM，由Mapcur得到位置地理距离矩阵GDM，由位置查询概率LQP生成概率距离矩阵PDM（第2）行），将真实位置加入假位置集DLS 中，并将其从CLS 中移除，根据SDM 将CLS 中与DLS 新加入的假位置（DLS.last）语义距离小于u 的位置过滤掉（第3)～11)行），再根据LDM 及QDM 从CLS 剩余位置中选择与DLS.last 满足的位置Loc 作为新的假位置放入DLS（第14)～18)行），并将此位置从CLS 中移除（第19)行），循环执行以上语句（第5)～20)行），直到DLS 的个数等于k，最后返回最优假位置集DLS。

4 算法理论分析

4.1 安全性分析

由系统架构可知，本文的假位置选择算法在智能终端设备上进行时，智能终端设备不会将其准确位置坐标发送给任何实体。所以攻击者无法通过链路攻击来获取用户的准确位置。

攻击能力较强的强攻击者企图根据已获得的地图和语义信息以及历史查询概率数据来推测用户的真实位置，本文算法可以有效抵抗此类攻击者。首先，在选择假位置时保证了其与当前假位置集DLS 中已有位置的语义均不同，即对于任意2个位置 li、lj，满足 dsem(li,lj)≥ u，使攻击者无法推断用户的位置语义信息；其次，假位置间的查询概率接近，即满足pi≈ pj(pi,pj表示位置 li、lj的历史查询概率)，根据位置熵的计算式可知，查询概率越接近时信息熵越大，且对于含k 个位置的假位置集DLS，攻击者推出真实位置的概率约为，因此本文算法可以有效抵抗强攻击者，保护用户的位置隐私。

4.2 算法复杂度分析

MMDS 算法开始时，假位置集DLS 中只有用户的真实位置 lreal，假设候选位置有n 个。MMDS算法分为2 个阶段，第一阶段是通过比较将候选位置中与DLS中新加入的假位置语义相同的位置过滤掉，第二阶段是通过式(3)从剩余候选位置中选择出最优假位置加入DLS。每个阶段的时间复杂度均为 O(n)，因此总的时间复杂度为 O(n)。

5 实验结果与分析

5.1 实验设置

实验选用某城市真实地图数据，其中心城区已经被Wi-Fi 全面覆盖且拥有大量的LBS 用户。每个Wi-Fi AP 覆盖范围约为700～800 m，样本空间被均匀划分为28×28 的矩形网格，共13 579 个样本轨迹点作为历史数据，计算每个网格内地理位置的历史查询概率。实验将位置语义主要分为六大类，分别为教育与科学、行政与居住、医疗救护、商城、公共场所和餐饮娱乐。

实验采用MyEclipse 开发平台，以Java 编程语言实现。硬件环境为Windows 7 操作系统，3.40 GHz Intel Core i7 处理器，4 GB 内存。实验参数如表1 所示。

表1 实验参数

5.2 实验结果

首先，通过分析匿名成功率对MMDS 评价；然后，将MMDS 样考虑位置语义的MaxMinDistDS算法[9]和SimpMaxMinDistDS算法[9]从假位置集生成时间、物理分散度、语义差异性比较，以及位置熵四方面进行比较，验证MMDS 算法的有效性。

5.2.1 匿名成功率

图4 匿名成功率的变化情况

图4 给出了匿名成功率相对于地图中位置的数目Mapi.LN、匿名度k 以及语义差异度u 的变化情况。图4(a)结果显示，地图中位置数越多，越有利于匿名执行，匿名成功率越高。这是因为位置数越多，位置语义的种类数就越多，更有利于构造满足隐私需求的假位置集，匿名成功率得到提高。反之，当地图中位置的数目较少时，很难使匿名集位置间的语义互不相同，导致匿名失败。在图4(b)中，随着隐私需求的匿名度k 的增加，匿名成功率有所下降，因为满足语义差异度的位置数不能满足匿名度k 的要求。图4(c)中，随着语义差异度u 的增加，匿名成功率同样呈下降趋势，因为语义差异度要求越高，假位置集的语义差异性越难满足。综上所述，实际操作中匿名度k 与语义差异度u 不能设置得过大。

5.2.2 假位置集生成效率

在考虑位置语义的假位置选择算法中，MaxMinDistDS 算法、SimpMaxMinDistDS 算法和MMDS算法生成假位置集的平均生成时间如表2所示。图5 为这3 种算法假位置集生成时间的对比结果，其中k 的取值范围为2～8。

表2 假位置集平均生成时间

从图5(a)可以看出，随着k 值的增加，MMDS 算法的假位置集平均生成时间远小于MaxMinDistDS算法，MMDS 算法生成假位置集的效率更高。因为MMDS 算法在选择候选位置时，过滤了与当前假位置集已有位置语义距离相近的位置，避免了不必要的时间开销。从图5(b)可以看出，当k ≤5 时，MMDS 算法的假位置集生成时间要高于SimpMaxMinDistDS 算法，当k ≥6 时，MMDS算法的假位置集生成时间低于SimpMaxMinDistDS算法。

通过对比还可以看出，随着k 值的增加，3 种算法生成假位置集所花费的时间都增加，但MMDS 算法明显比SimpMaxMinDistDS 算法和MaxMinDistDS算法的增加幅度小。也就是说，随着k 值的增大，MMDS 算法所花费的时间更小，优势更加明显，更具有实用性。

图5 假位置集生成时间随k 的变化

5.2.3 物理分散性比较

假位置间的距离越大则位置越分散，本文通过比较假位置集中任意两位置间的最小距离来衡量假位置集的物理分散性，最小距离越大说明越分散。图6 表示本文MMDS 算法、MaxMinDistDS 算法、SimpMaxMinDistDS 算法这3 种算法在不同k值下假位置间的最小距离。

图6 假位置间的最小距离

通过实验对比可以看出，当k ≤ 4时，MMDS算法与 MaxMinDistDS 算法的最小距离接近；k ≥ 5时，MaxMinDistDS 算法的最小距离要大于MMDS 算法。在相同k 值下，MMDS 算法的最小距离略大于SimpMaxMinDistDS 算法。这3 种算法假位置间的最小距离都随k 值的增加而呈下降趋势，且随着k 值的增大，最小距离趋近相同，均能保持良好的物理分散性。

5.2.4 语义差异性比较

本实验采用θ-安全值来度量假位置集的语义差异性。θ-安全值的计算如下

其中，SEM={dsem|dsem(li,lj)＜ u}，k =|DLS|，DLS是包含真实位置在内的假位置集，表示组运算式。当θ 无限接近1 时，则说明假位置集满足语义差异性。

MMDS 算法、MaxMinDistDS 算法、Simp-MaxMinDistDS 算法的θ-安全值如图7 所示。可以看出，3 种算法的θ-安全值始终接近1，这是因为它们在选择假位置时均考虑到了位置的语义信息，从而保证了语义差异性。

图7 假位置集的θ-安全值

5.2.5 位置熵比较

在位置隐私保护中位置熵主要用来衡量真实位置的不确定性，熵值越大表明匿名化程度越高,反之则匿名化程度越低。

3 种算法在不同k 值下的位置熵如图8 所示，可以看出，随着k 值的增大，3 种算法的位置熵都呈整体增大趋势，但是MMDS 算法的位置熵要明显大于另外2 种算法，这是因为MMDS 算法不仅考虑到位置语义差异性，还考虑到位置的访问概率，用户真实位置的不确定性更大，可以更有效地保护用户的位置隐私。

通过以上实验对比发现，MMDS 算法在尽可能满足地理位置之间分散和语义多样化的同时，还具有较高的假位置生成效率和位置熵值，能有效提高位置服务质量。

图8 3 种算法在不同k 值下的位置熵

6 相关工作

现有的基于位置服务的隐私保护技术主要有空间转换、匿名区域和伪造数据3 类。文献[10]提出一种基于空间转换的位置隐私保护方法。该方法采用Hilbert 曲线来转换用户坐标，使匿名服务器无法获得用户的位置信息，但匿名服务器可以从中得到用户的运动方向、运动速度等信息，造成用户位置信息泄露。文献[11]提出基于差分隐私的位置隐私方案，考虑由于轨迹中位置之间的相关性，独立应用噪声会泄露隐私，利用一个简单的预测函数和2 个预算支出策略，改善独立应用噪声易造成隐私泄露的问题。文献[12]中提出基于查询范围的匿名区构造方案，考虑位置服务提供商（LSP,location service provider）的查询区域面积，将用户的查询范围引入匿名区的构造中，在保护用户隐私的同时有效降低LSP 的查询区域面积。文献[13]提出基于用户偏好选择的假位置生成方案，根据历史查询概率选取用户发出请求较多的位置生成假位置，并考虑其速度、行驶方向，选取与用户位置相似度较高的假位置构造匿名区域。

文献[10-13]在一定程度上保护了位置隐私，但未考虑位置的语义信息，无法应对具有一定语义背景知识的攻击。文献[14]为了防止敏感语义信息泄露，充分考虑了每种语义位置类型的普及度与敏感度，提出一种满足个性化需求的位置语义保护方法。文献[15]通过 Voronoi 分割区域“有选择”的扩展来构建θ-语义安全的隐匿区域，θ 越小，其保护程度越高。文献[16]提出一种针对路网环境下的语义位置隐私保护方法，使匿名集中用户所处语义位置类型所占比例尽可能小，从而增加用户所处语义位置的不确定性。文献[17]提出一种面向连续查询的敏感语义位置隐私保护方案，为同时抵抗连续查询追踪攻击和语义推断攻击，构建满足-隐私模型的匿名区域。文献[14-17]均有效保护了用户的位置语义信息，但均存在匿名区域过大的问题，影响用户的服务质量，且大部分都需要第三方服务器的参与，容易引发单点故障。文献[18]提出一种基于假位置的k-匿名位置隐私保护方法。该方法采用独立式架构，并充分考虑了位置的语义信息等特征，选取语义相似度最小的k-1 个位置点作为假位置集，保证了位置的语义安全。但因未考虑位置的查询概率信息，所以无法应对具有查询概率背景知识的攻击。

通过以上分析可知，本文所提的MMDS 算法充分考虑了位置语义和概率信息，能够抵抗攻击者具有位置语义和查询概率信息的背景知识攻击，可以提供较强的位置隐私保护。

7 结束语

针对当前大多数基于假位置的k-匿名位置隐私保护方案没有充分考虑攻击者拥有边信息或者背景知识等问题，本文的假位置集构造方法可以从3 个方面达到位置隐私保护的效果。首先，保证假位置集k 个位置之间满足语义差异性，提高用户位置语义的不可区分性，防止因语义推断造成的位置语义泄露；然后，使位置之间查询概率尽量相近，防止因过滤查询概率较低的位置，影响用户隐私需求的实现；最后，使假位置之间的地理位置尽量分散，防止因匿名区域过小造成的位置隐私泄露。实验分别从假位置集生成时间、物理分散度、语义差异性比较以及位置熵四方面将本文所提 MMDS 算法与 MaxMinDistDS 算法和SimpMaxMinDistDS 算法进行对比，结果表明，MMDS 算法能有效提高位置熵值，且具有更好的生成效率，可以有效保护用户的位置隐私。本文方案主要考虑了快照查询的位置隐私保护，而快照查询可以看作连续查询的特殊情况，因此下一步将研究连续查询的位置隐私保护。