近年来，无线通信技术取得了突飞猛进的发展，随之而来的是通讯成本的快速降低，智能手机的广泛普及. 位置服务（location-based services，LBS）使人们的生活更加舒适和方便，基于LBS研发的各类软件已经成为人们生活中的热门应用^[1-2]. LBS是依赖于用户位置信息的服务，如路径导航，查找酒店、餐馆或加油站等目的地位置，用户通常使用移动设备获取这类服务^[3-4]. 为了享受这些便利，移动用户须向不可信的位置服务提供商（location service provider，LSP）提交查询. 通过收集用户的请求数据，LSP可以推断用户的个人信息，如用户的位置、偏好、家庭背景等^[5]，LSP有可能向第三方披露用户的私人信息. 因此，在LBS中保护用户的个人隐私成为人们关注的焦点.

如何才能保护LBS中移动用户的个人隐私，有很多研究提出了解决方案. 其中，大多数解决方案依赖于包含可信第三方（trusted third-party，TTP）的架构，TTP的功能是构造匿名区^[6-8]. 这些方案的问题是，方案将所有隐私信息都集中到TTP服务器，一旦TTP服务器被对手攻击导致信息泄露，用户的个人隐私将得不到保护. 另一些方案是利用TTP服务器的缓存来记录和查询数据. 虽然用户从缓存中获取所需的服务数据，可以减少与LSP的交互次数^[9-11]，但是这些方案未能充分利用缓存和历史数据来更好地保护用户的个人隐私. 为了提高对用户个人隐私的保护程度，同时提高对缓存数据的利用效率，本研究提出基于本地缓存的位置感知匿名隐私保护方案（location-aware anonymous selection algorithm, LaSA）. 在本方案中，用户不依赖于TTP，而是利用移动终端的缓存构造匿名集. 当用户需要LBS查询服务时，用户先在本地移动终端的缓存中查询结果. 如果缓存中的数据能够满足用户需求，则用户无须再向LSP发起请求，用户的隐私信息不会被暴露给LSP. 如果缓存数据不能满足用户需求，方案将在本地移动终端构造一组可以覆盖其真实查询区域的匿名位置集，再把对匿名位置集的查询请求发送给LSP. 生成匿名集的过程是利用基于历史数据所建立的马尔可夫模型预测下一个可能查询的位置.

本方案将用户的查询结果缓存在移动终端中，可以通过缓存直接应答部分用户查询，降低用户将个人隐私信息暴露给LSP的机率. 利用匿名覆盖技术增强用户隐私. 根据用户需要查询范围，选取k个位置组成匿名集合，用匿名位置集合覆盖用户的真实查询区域，从而隐藏用户真实的位置. 该方案使用真实历史轨迹数据来构建马尔可夫模型，该模型在用户发送服务请求之前预测用户的未来位置. 为了进一步提高缓存命中率，根据预测位置、缓存贡献率和数据新鲜度形成覆盖真实位置的匿名区域，从而减少用户与LSP之间的交互次数.

在LBS位置隐私保护中，主要有2种常用的架构：依赖TTP的架构^[12]和不依赖TTP的架构.

在依赖TTP的架构中有一个名为匿名器的可信的第三方组件，它位于用户和LSP之间. 匿名器的作用是执行位置匿名，使得LSP无法分辨真实用户和其他用户. 匿名器的引入增强了保护用户隐私的能力^[13-14]. 但是，所有提交的查询都必须通过匿名器，使得匿名器成为此类架构的性能瓶颈. 如果恶意第三方攻击该服务器，所有用户的隐私都将受到危害.

在不依赖TTP的架构中，用户通过移动终端直接与LSP通信，客户端通过独立^[15]或协作^[16-17]的方式构造匿名区域. 该类架构的优点是易于部署. 然而，在这些方案中，独立构建匿名区域的方法虽然能够实现对用户隐私信息的保护，但隐私保护的程度不够. 在用户相互协作的方法中，用户和协作方须拥有2个独立的通信网络，分别用于P2P通信和LBS查询，这严重降低了该类方案的实用性.

目前，在有关LBS的研究中已经提出了许多位置隐私保护技术. 通常将现有方案分为两大类：构建匿名区域技术和位置混淆技术. 另外，近年来缓存技术作为辅助手段也被应用到位置隐私保护技术中.

在构建匿名区域的技术中，主要方法包含匿名和混淆. 前者主要通过生成一系列假位置来隐藏用户的真实位置，以降低用户隐私暴露的风险. 例如，Zhang等^[18]提出基于实际道路条件构建匿名位置的方法. Shuhei等^[19]使用基于估计的虚拟轨迹生成方法，该方法根据给定的访问点来估计用户的移动计划，并生成虚拟轨迹，使得对手无法区分用户和假用户. 身份匿名方法是通过使用附近用户信息来隐藏自身的真实身份，从而防止攻击者锁定目标用户^[20]. 该方法对用户隐私的保护程度主要取决于用户身份与特定位置用户之间的关联. 因此，在这类方法中，用户须频繁更换自己的假名.

混淆技术通常将用户的查询点扩大为一个区域，然后将该区域发送到LSP进行查询；因此，攻击者只知道用户所在的区域^[21]. Hwang等^[22]将S-段范式与R-匿名、K-匿名技术相融合，提出将基于用户隐私的隐藏位置信息与真实环境条件相结合，以避免LSP挖掘用户真实轨迹. Zhang等^[23]设计基于偏差的查询交换方案，该方案对不同用户的查询点进行混淆操作，从而阻碍轨迹推断，降低用户隐私暴露的风险.

缓存方法的基本思想是利用先前查询的缓存数据来应答后续查询. 例如，Kangsoo等^[24]设想了使用虚拟专用服务器来保护LBS中位置隐私的保护方案. 在匿名过程中，该方案使用协作缓存来保证系统稳定. Peng等^[25]开发了通过协作缓存保护用户轨迹信息的隐私保护方案. 该方案给恶意第三方试图重绘用户轨迹造成较大困难. Zhang等^[26]提出将网格和缓存相结合的方案来增强用户隐私保护. 该方案可以防止不同的用户查询相同的区域，但是会增大客户端开销. Niu等^[27-28]提出基于缓存的方案，使用多种基于缓存的匿名位置选择算法，以提高用户的位置隐私。但上述这些方案不适用于连续的LBS服务.

综上所述，在现有隐私保护方法中，TTP是系统瓶颈. 另外，没能充分利用历史信息和缓存数据. 本研究旨在提出基于历史信息和缓存数据的匿名区域形成方法，通过轨迹位置预测，提高缓存命中率，增强隐私保护效果.

本研究的应用场景是连续LBS. 连续LBS是指在一段时间内，移动用户持续向服务器发起LBS请求，例如在导航、兴趣点（points of interests, POIs）查询以及其他须持续保持请求的服务中. 用户在这段时间内发起的请求可以是连续或间歇的.

本研究提出的LaSA方案采用不依赖TTP的架构，用户通过手机直接与LSP通信，以实现连续查询下保护用户位置隐私的目的. 如图1所示，该体系结构由2个主要部分组成：移动单元和LSP. 其主要功能描述如下。

1）移动单元. 每个移动单元都是携带智能终端的个人用户，其中智能终端是具有诸如信息处理、数据存储、全球定位单元和网络通信等基本功能的移动设备. 移动单元与服务器之间采用长期演进（long term evolution, LTE）通信方式. 利用智能终端的运算能力和存储能力，将生成K-匿名和缓存查询结果的任务也布置在智能终端上. 缓存数据可以根据预测模型来预测用户的下一个查询.

2）LSP. 所提方案假设不可信的LSP是竞争对手. LSP为移动单元提供POIs查询服务. 另一方面，通过监控用户发送的查询，LSP可以轻松获得所有查询的统计信息. 此外，它还了解该系统中所使用的位置隐私保护机制，以及已经缓存的数据. 基于这些数据，LSP可以进行推理攻击来推断和学习用户的位置信息.

当移动用户需要LBS服务时，用户通过智能手机向不可信的LSP提交基于位置的相关查询，以获取和享受相应的服务（查询附近POIs），例如附近的可用停车位、酒店优惠或公交车站台信息等. 特别是当移动用户向LSP发起连续查询时，会增大轨迹识别的风险. 其次，不同的用户先后向LSP发起相同的查询请求，会增加用户隐私暴露风险以及通信开销.

针对用户向不可信LSP发送信息的问题，一般的方法是使用K-匿名来降低用户隐私暴露水平。然而，基于相关背景知识的数据挖掘攻击依然可以识别出隐藏于所选虚拟位置中的真实位置. 因此，如何选择合适的匿名位置是一个挑战. 针对不同用户重复查询的问题，为了提高对历史数据的利用效率，考虑一种允许用户直接从缓存中检索数据的方法，可以增强用户隐私安全并减少其通信开销，然而，如何提高缓存命中率是一个挑战. 为了解决上述问题，所提方案的基本思想是将缓存、马尔可夫预测模型和K-匿名技术相结合来保护用户隐私.

所提方案在移动终端缓存用户和匿名集先前在本地客户端上的查询数据. 在后续查询中先查询本地缓存，降低将用户信息暴露给LSP的风险. 为了进一步降低隐私暴露程度，本方案不将用户的真实位置发送到LSP. 如图2（a）所示，对匿名集合的查询结果进行组合（位置2、3、4）来获得真正的查询区域（位置1）. 与随机选择匿名位置相比，本方案倾向于选择覆盖真实查询区域的位置. 为了提高缓存命中率，在连续的LBS查询中，考虑匿名位置的缓存贡献率和用户的移动趋势，并使用基于马尔可夫的位置预测模型来估计用户的后序位置. 如图2（b）所示，蓝色虚线表示真实轨迹，阴影网格表示该网格服务信息已经保存在缓存中. 虽然位置4的缓存贡献率高于位置2、3，但位置4不在用户的预测轨迹路径中. 本方案更倾向于选择位于用户预测路径中的候选位置，以形成匿名位置集.

背景信息是指用户在某一特定位置或特定区域发送查询请求的概率. 如在包含n²个基本单元的地图中，使用位置单元发起的查询数量n_i与整个地图上的查询总数量m的比率作为位置单元l_i的查询概率q_i. 查询概率公式定义为

(1) $ {q_i} = {{{n_i}}}/{m}. $

式中： $i = 1,\;2, \cdots ,{n^2}$. 对整个地图而言，有 $\displaystyle\sum\nolimits_{i = 1}^{{n^2}} {{q_i}} = 1$.

如果不考虑背景信息，用户在匿名化后向LSP发送查询请求，对手能够推断出用户真实位置的概率为1/k，k为匿名化过程中位置集合的大小. 位置单元l_i是用户的实际位置的概率的表达式为

(2) $ {p_i} = {{{q_i}}}/{{\displaystyle\sum\limits_{j = 1}^k {{q_j}} }}. $

式中： $i = 1,\;2, \cdots ,k$， $\displaystyle\sum\nolimits_{i = 1}^k {{p_i}} = 1$.

根据文献[27]、[28]，对位置隐私指标定义如下.

1）位置熵H. 对手推断用户真实位置信息的不确定度，表达式为

(3) $ H = - \sum\limits_{i = 1}^k {{p_i}} {\log _2}\;{p_i}. $

2）匿名集合C_a. 按照一定的规则从地图中选择|C_a|个位置单元形成匿名位置集.

3）缓存命中率γ. 移动单元通过查询缓存获取LBS服务的概率. 将缓存的服务响应记为Q_cac，将LSP的服务响应记为Q_ser. 缓存命中率定义为

(4) $ \gamma = \frac{{|{\cal{Q}}_{{\rm{cac}}}|}}{{|{\cal{Q}}_{{\rm{ser}}}| + |{\cal{Q}}_{{\rm{cac}}}|}}. $

4）隐私度λ. 在使用缓存的方案中，系统的隐私保护能力定义如下：

(5) $ \lambda = \frac{{\displaystyle\sum\nolimits_{q \in {{\cal{Q}}_{{\rm{ser}}}}} {{H_q}} }}{{|{{\cal{Q}}_{{\rm{ser}}}}| + |{{\cal{Q}}_{{\rm{cac}}}}|}} + \gamma {\log _2}\;{n^2}. $

式中：H_q为匿名集的位置熵. 从式（5）可知，有2种方式可以增强系统的隐私保护效果，即提高位置熵H_q或提高缓存命中率γ. 因此，想要更高的隐私保护程度，须选择拥有更大H_q和γ的匿名集合.

5）缓存贡献度δ. 用来判断位置单元l_i的服务数据是否已被缓存. 计算公式为δ = q_i g. 对于已存在于缓存的位置单元l_i，将其添加至缓存列表并不能增加缓存命中率，则g = 0；反之，g = 1. 位置l_i的查询概率q_i与其缓存贡献度δ成正比.

6）数据新鲜度F. 对于提交给LBS服务器的查询，当查询范围大于位置单元时，每个位置获取的服务数据覆盖该位置单元周围的多个单元格. 对于整体匿名集合的平均数据新鲜度可以定义为

(6) $ F = {{\displaystyle\sum\limits_{i = 1}^{l k} {{f_i}} }}/\left( {{{lk}}} \right). $

式中：f_i为单元格i的新鲜度，l为查询范围内的单元格数.

由于用户的移动具有一定规律性，使用马尔可夫模型根据历史轨迹预测用户的后序查询位置，并根据预测的位置选择k个单元形成空间K-匿名，从而提高用户的后续缓存命中率. 一般来说，基于马尔可夫的轨迹预测包括以下几个基本阶段：1）输入历史用户的轨迹数据；2）根据历史数据构造状态转移概率矩阵；3）根据用户的当前位置，查询状态转移概率矩阵，并预测用户下一时刻可能出现的位置.

假设一个轨迹被描述为 $\left\{ {{P_i}\left| {i = 1,\;2, \cdots ,k} \right.} \right\}$. P_i可以由元组 $\left\{ {l{_i},{t_i}} \right\}$表示，表示在t_i时刻，用户的位置是l_i. 位置轨迹由坐标值组成，包括当前坐标的经度和纬度. 假设用户的轨迹状态序列是一个包含k项的马尔可夫链. 由马尔可夫稳定无后效理论可知，P_i+1在该轨迹中的位置仅取决于P_i，于是有 $\left\{ {{P_{i + 1}}\left| {{P_i},{P_{i - 1}},{P_{i - 2}},\cdots,{P_1}} \right.} \right\} = \left\{ {{P_{i + \;1}}\left| {{P_i}} \right.} \right\}$. 通过计算状态转移矩阵来求得P_i+1的最大概率.

当用户请求LBS时，将优先查询智能手机的缓存系统. 如果没有匹配或匹配的服务数据不能满足其要求，则用户向LSP发送查询，请求位置集C_a所对应的服务数据. 用户不发送个人的真实位置，而是令k个匿名位置的查询结果覆盖其真实查询范围. 同时，所得匿名集的查询结果也包含用户未来可能查询的区域. 在向LSP发起查询结束后，所获取的服务数据将用于更新缓存. 如果缓存的服务数据能够满足用户的需求，则无须向LSP服务器发送查询. 当用户向LBS服务器提交查询时，其隐私安全受所提LaSA方案的保护；当向缓存发起查询时，隐私是通过缓存来保护的，因为在此情况下不必向LSP服务器发送查询.

本方案的目标是选择一组匿名位置来确保整体位置熵较高. 其查询区域可以覆盖真实的查询范围，并包括有最大概率的预测位置，另外可以对缓存命中率有更多的贡献. 当响应查询时，缓存无须具有查询范围内的所有单元格的服务数据. 具体来讲，每个用户都可以设置一个阈值τ，该阈值表示已缓存单元数量与所查询区域单元数量之比的最小值. 定义参数ξ表示在查询范围内实际缓存的单元格的百分比. 如果为ξ≥τ，则可以通过缓存回答用户的查询；如果ξ<τ，则用户必须向LSP发起查询. 通过优化τ，用户可以调整服务质量和隐私之间的权衡. 一组匿名位置对缓存的总贡献定义如下：

(7) $ \varDelta = (1 - F)\sum\limits_{i = 1}^k {{\delta _i}}. $

算法1详细描述了本研究所提方案. 基于实际位置C_r和查询半径R_e，选择2k个单元形成候选集C_c，这些单元具有相近的q与C_r. 从C_c中找到满足覆盖度τ的子集构成C_s. 根据当前位置C_r和转移矩阵TM，计算可能在下一时刻的一组预测位置C''. 再从C_s中选取具有最大缓存贡献度的部分和集合C'求并集，最终得到所求匿名集合C_a.

算法1　位置感知的匿名选择算法

输入 　 C_r（真实位置），k（匿名度），R_e（查询半径），τ（覆盖度），ε（预测度），s（候选数量），TM（预测转移矩阵）

输出 　 C_a（匿名位置集合）

1. Select (2R_e+1)² cells around C_r as constraint set Q_s

2. choose s cells around C_rand sort by query probability q

3. Select 2k cells similar to C_r query probability as the candidate set

4. C = {C′| C′ $ \subset $ C_c, | C′ | = k − ε}

5. For each C′ ∈ C do

6. compute D_e = C′ ∩ Q_s

7. If |D_e| > τ then add C′ to C_s

8. End

9. For each C′ ∈C_s do

10. compute $\varDelta $ for the k – ε dummies in C′

11. End

12. Search TM, select the first ε cells to form C''

13. Output ${C_{\rm{a}}} = \mathop {\arg \max }\limits_{{C^\prime } \subset {C_{\rm{s}}}} \varDelta \cup C''$

当用户发起LBS请求时，用户先对本地缓存进行查询. 如果缓存中的数据能够满足用户需求，则用户可以直接获取服务数据. 缓存服务过程只存在于用户的移动终端，并不存在端到端的通信过程，因此该类服务是安全的. 另一方面，标准的加解密技术可以很方便地布置到本研究方案中，以抵御发生在用户和LSP之间无线信道上的窃听攻击.

LSP掌握整个地图的查询概率以及所有用户的历史查询信息，它可以根据这些信息进行推理攻击. 在该方案中，用户利用LaSA算法，选择一组能够覆盖当前和未来时间段的真实查询区域，并根据缓存贡献率和数据新鲜度选择满足条件的k个位置作为匿名位置集合. 用户使用该匿名集合发起查询请求. 在该集合中，不包括用户当前的真实位置，而是将真实查询区域分散隐藏到k − n个位置中. 即使预测的n个位置包含用户未来的真实位置，本方案也使用其他k − n个相似位置作为匿名区域. 因此，对于单次查询，对手推断用户实际位置的概率小于1/k.

LSP还可以利用不同位置的背景信息来推断用户的真实位置. 所创建的匿名集合包含具有相似背景信息的混淆位置和预测位置. 混淆位置集合中的元素与实际位置查询概率相近. 预测位置集合中的元素来自具有多个语义信息的真实历史轨迹. 因此，所提出的LaSA算法可以保证所有匿名区域单元具有相似的查询概率，并且LSP无法从提交的匿名区域中估计出用户的真实位置.

轨迹数据集来自文献[29]，包括由23 667 828个点组成的17 621条轨迹. 这个数据集包含5 a多来收集的约1 229 951英里的GPS数据. 这些数据由多种支持GPS的设备收集. 该数据集中的轨迹大部分分布在北京地区. 选取北京市区的12024个轨迹数据作为本实验使用的数据集. 将30 km×26 km的地图划分为200 m×200 m的单元网格. 每个网格的初始查询概率可以从Google Maps API获得. 在实验中，先用90%的轨迹数据建立马尔可夫转移矩阵. 使用剩余10%的轨迹来模拟连续的LBS查询. 设置用户发起连续LBS查询的时间间隔为2 min. 详细的实验参数表如表1所示. 表中，N_t为轨迹数量，（x₁, y₁）、（x₂, y₂）分别为起点（左下）、最大（右上）坐标。

实验电脑配置为Intel(R)Core(TM)i7-8550U CPU@1.80 GHz 2.00 GHz和8 GB RAM；所提隐私保护方案的实验环境为Anaconda3和Python3.7. Enhanced-CaDSA^[27]和MobiCache^[9]方案将作为对照方案与所提方案进行对比.

首先评估匿名度k对所提方案的影响. 如图3（a）所示为匿名度和用户向LSP发起查询的次数之间的关系. 随着匿名度的增加，所构造的匿名区域范围变得更大，查询数量也随着k的增加而增加. 相比于对照方案，LaSA方案始终需要更少查询次数. 这意味着所提方案可以更有效地利用缓存信息，如图3（b）所示，随着匿名度k的增加，不同方案的缓存命中率都在增大. 可以看到，所提方案的缓存命中率始终高于Enhanced-CaDSA和MobiCache方案.

MobiCache方案^[9]是在地图中选择缓存贡献度较高的位置来构成匿名集合，这使它仅在局部时间范围内保证较高的缓存利用率. Enhanced-CaDSA^[27]除了考虑缓存贡献度，还考虑归一化距离，于是所选位置接近实际位置，但它没有考虑用户的移动性. 另外，还评估了匿名度对隐私度的影响. LaSA方案具有最高的缓存利用率，因此需要的查询次数更少. 在这种情况下，用户的隐私保护效果是最好的，如图3（c）所示. 结果表明，所提方案可以更有效地利用来自LSP服务器的查询数据，从而减少移动单元向LSP发送查询的次数，能够增强对用户隐私的保护.

如图4（a）所示为缓存命中率随预测度ε（预测位置数与匿名位置数之比）的变化. 一般来说，缓存命中率随着预测度的增加而增加，因为相对于随机选择附近位置的方法，更多的选择预测位置可以有效减少后续向LSP发起查询的次数. 然而，随着匿名度的增加，系统将缓存更多的无效预测位置，导致缓存命中率不会进一步增加. 另一方面，如图4（b）所示，随着覆盖度的增加，缓存命中率将呈现下降趋势. 这是因为更大的覆盖度意味着更高的查询精度，需要更多的查询来覆盖真正的查询范围.

针对位置服务中用户的隐私安全问题，综合考虑用户位置的历史数据和背景信息，引入移动终端的缓存机制，并结合K-匿名技术和马尔可夫预测模型，提出基于本地缓存的位置感知匿名选择算法. 构造不依赖于可信第三方的隐私保护方案，减少用户与LBS服务器之间的交互次数，抵抗来自具有背景信息的对手的多重推理攻击. 安全性分析和实验评估结果进一步验证所提出方案的有效性，并分析了不同参数设置对方案性能的影响. 实验结果表明，所提方案可以提高缓存命中率，减少用户与LSP的交互次数，保护用户隐私数据.

未来研究将集中在2个方面，一方面将所提方案扩展到可穿戴设备的使用场景中，研究个人医疗隐私数据的保护问题；另一方面研究真实场景下隐私保护方案的部署问题，进一步提升方案的有效性和通用性.