童威黄启萍

（1.安徽文达信息工程学院，安徽 合肥 231201；2.安徽电气工程职业技术学院，安徽 合肥 230051）

1 引言

基于位置的服务（Location Based Services,LBS），即获得移动对象的位置后，用户获取相关位置查询。基于位置服务中的隐私内容包括位置信息和敏感信息。前者为隐私用户查询的确切位置，后者即隐藏与用户个人隐私有关的敏感信息[1]。

传统LBS隐私保护技术包含三类：基于数据失真的位置隐私保护技术；基于抑制发布的位置隐私保护技术；基于数据加密的位置隐私保护技术[2]。前两者无法满足较高隐私需求的用户要求。本文面向隐私的BRNN查询（双色反向最近邻查询）保护方法即基于数据加密的位置隐私保护技术进行探讨。

2 预备知识

在LBS的大部分应用中，BRNN是一种常见的查询方法。给定两个点集S（服务集）、R（对象点集），查询点q∈S，BRNN要查找的是最近邻q的对象点集合。图1为一个BRNN示例，圆点表示住宅区Qi，方块表示服务点Si（超市）。某客户如果想开一家超市，有2个候选位置q1,q2。哪个位置开店可以在距离上吸引更多原本在其他超市购物的居民？通过对候选位置的BRNN查询，可以得知优先度q2>q1，因为q2有最大的BRNN查询结果集，包括3个住宅区Q2,Q3,Q6。

图1 BRNN示例

随着移动计算和位置服务的不断发展，BRNN查询更加广泛地应用在如地图查询、资源定位、急救调度、基于移动现实游戏等领域中[3]。

然而，BRNN查询可能会导致用户的隐私泄露。例如，以上示例中，用户的查询位置以及商业意图将完全暴露给服务器。已有的BRNN查询以空间模糊化为基础，将位置匿名化发送给服务器。但……