基于信息缓存的位置隐私保护
基于位置的服务（Location-Based Service，LBS）是当前最受欢迎的社交应用之一。
利用此类应用程序，用户可以很容易地获得所在位置附近的各种兴趣点（Point of Interest，POI），例如附近的医院、餐馆和酒吧等。
然而，为了享受这些便利，用户不得不向不可信的LBS服务器提交查询。
但由于查询中通常包含一些个人信息，例如用户的当前位置和所查询的内容等，LBS服务器可以轻易地推断出谁在什么地方干什么，甚至可以直接跟踪用户或将其个人信息发布给更不可信的第三方，如广告商等，进一步威胁用户隐私。
因此，如何在服务过程中更好地保护用户隐私成为亟待解决的问题。
LBS中移动用户的隐私保护方案既可以关注保护发送到LBS服务器的查询隐私，也可以通过减少发送到LBS服务器的查询数量达到隐私保护，越少的查询意味着服务器将获取越少的位置信息，因此暴露用户位置的机会就更少。
减少发送到LBS服务器的查询数量的一种常见方法是利用缓存，可以通过缓存的方法从先前查询中收集缓存服务数据，以响应之后的查询，从而减少后续用户向不可信服务器提交查询的数量。
有行业专家曾提出了一种基于信息缓存和虚假位置的方案，以保护LBS中用户的位置隐私。
其基本思想是收集并存储查询过程中真实位置和虚假位置所获得的服务数据，并利用缓存的数据直接服务用户之后所产生的查询，从而减少发送到LBS服务器的查询次数。
该方案的核心是提出了一种考虑缓存且基于熵的隐私度量方法，并基于该度量方法设计了基于缓存的虚假位置选择算法（Caching-aware DummySelection Algorithm，CaDSA）。
在选择虚假位置时，CaDSA不仅可以使当前查询的隐私保护效果最大化，还可以确保虚假位置带来的服务数据对缓存的贡献最大化，从而进一步提升隐私保护效果。
1.问题描述
上图说明了CaDSA的基本思想，主要关注两个因素：
隐私（如图（a）和图（b）所示）和缓存（如图（c）和图（d）所示）。
在图（a）和图（b）中，单元格中的不同阴影表示不同的查询概率，带有√的单元格表示这些单元格是虚假位置的候选项。
在图（c）和图（d）中，阴影单元格表示已经为其缓存了服务数据，而空白单元格表示其服务数据还没有被缓存。
灰度表示每个单元格所缓存服务数据的新鲜程度。
例如，较暗的单元格表示缓存在这些单元格上的服务数据仍然是较新的数据，而较亮的单元格表示这些服务数据可能很快就会过期。
加粗虚线矩形内的区域表示基于当前位置和查询范围的用户查询区域。
为了有效地提供能用于抵御带有先验信息攻击者的k-匿名性，方案偏向于将虚假位置分配给具有类似查询概率的单元（如图（b）所示），而不是随机选择虚假位置（如图（a）所示）。
其次，基于图（b）中获得的14个标记为√的候选对象，CaDSA的目标是提高缓存命中率。
因此，方案更倾向于选择可以对缓存做出更大贡献的位置。图（c）显示了一个最佳情况，其中所有选定的虚假位置都对缓存做出了最大贡献（在查询区域内有6个空白单元）。
但是，由于以下两个重要因素，CaDSA在某些情况下可能无法正常运行：
①用户通常在附近查询服务数据；
②缓存中经常查询的单元应在过期之前进行更新（再次缓存）。
考虑到上述两个因素可以更好地评估虚假位置对缓存的贡献，最终所选择的虚假位置如图（d）所示，方案更倾向于选择在真实位置附近并且服务数据已过期或即将过期的虚假位置。
