面向隐私的BRNN保护方法优化策略

2021-03-14童威黄启萍

电脑与电信 2021年12期

童威黄启萍

（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查询以空间模糊化为基础，将位置匿名化发送给服务器。但是，这类隐私保护技术可能保护度不够，或者由于匿名隐私保护，导致查询结果精确度不高[4]。本文介绍一种基于PIR的可保证强隐私保护的BRNN查询架构，并提出一种正交优化技术来进一步提高查询效率。

事实上，已有大量文献介绍了对BRNN的查询处理的解决方法。在基于维诺图的方法中，根据所有的服务点和查询点q构建而成，位于q所在的维诺单元的对象即查询结果[5]。查询q基于动态生成，利用维诺图的性质缩小查询边界。制定BRNN查询处理算法如下：LBS首先离线计算出所有服务点的维诺图，当查询q提交时，LBS发送给客户端：

（1）维诺单元包含q的服务点。

（2）这些服务点所在的维诺单元内包含所有对象点。客户端获取这些数据后，通过验证距离的大小，过滤真实的BRNN结果[6]。

3 数据组织

在此系统框架中，数据组织可以分为3个逻辑数据。如图2所示。DB1存储所有的维诺单元，DB2存储每个维诺单元的邻近维诺单元，DB3存储每个维诺单元的对象点集[7]。

图2 3个索引结构示例

4 查询计划

给定数据组织和查询q，基于PIR的查询计划如下：

（1）客户端从DB1查询有关点q的空间划分区域记录，存储了当前的划分空间内所有维诺单元种子的坐标。客户端可以通过计算q到这些种子的距离找到离q最近的种子；

（2）客户端从DB2查询关于种子i的记录，来获得i周围的近邻维诺单元ID，q的维诺单元可以从原始维诺图中的i及其邻居维诺单元集获得；

（3）客户端查询DB3中与q和q的邻居维诺单元中的所有对象点。客户端对这些对象点进行过滤以获得最终结果。

根据图1中的例子结合图2展示的数据组织结构。假设查询q在五角星的位置提交。DB1将整个空间划分为4个区域，分别使用A1、A2、A3、A4表示，每个子区域和若干维诺单元相交。当q提交时，先确定q所在的子区域A4，并在DB1中通过PIR协议查询记录A4。客户端计算出查询点q位于S2单元中，并在DB2中查询B2来获取S2的邻近维诺单元，即S1、S3、S4、S5。客户端由此确定在DB3中查询记录C1、C2、C3、C4和C5。这些记录提供了需要由客户端进行过滤的候选结果集，最终O2、O3和O6被过滤掉。

设计为3个逻辑上的数据库好处如下：

（1）将服务器和对象点分开存储，降低了数据集发生更新的代价。

（2）减少了冗余信息，提高了PIR的检索性能。

数据库中的一条记录占据一个页面的大小。如果不足一个页面，则需要添加假数据来补足。相反，如果数据超过一个数据页的大小，则在数据库的末尾生成一个新的数据页，由一个溢出指针从当前页面指向新生成的页面。

5 优化策略

由于在DB3中记录的缺省存储是给每个记录分配不同的数据页，这就导致了数据页的低利用率，使得PIR访问性能下降。本节基于查询计划提出了合并优化策略，将DB2与DB3有关的记录合并。

策略步骤：

（1）令NDB2、NDB3分别表示DB2和DB3中的记录数。令表示DB2中的第i条记录表示DB3中与eDB2i相关的t条记录。Bm表示DB3中的第m条记录的大小，该记录可能会占用多条数据页，其中bm作为Bm中的一个小片段，表示为bm=Bm%Page_size（只有小片段才会与其他的小片段打包）。

（2）令变量ym,j∈{0,1}表示记录是否存储在DB3中的第j个页面，且xi,j∈{0,1}表示所有记录是否存储在第j个页面。另外，对于，有xi,j≥ym,j。同时其中，P是DB3中缺省排列的数据页个数。

（3）在DB2的第i个记录中涉及的对象点所需的PIR访问次数可以表示为DB3对应对象点位于完整数据页面数和小片段记录合并后的页面数之和，即：

（4）在一个页面中的对象点总数不能超过页面大小，即

（5）令K为DB2中任意记录查询所需的最大PIR访问次数，即：最小化K，满足：

分两步近似求解关于K的整数规划问题：

（1）为线性规划问题，xi,j和ym,j是属于[0,1]的分数，即ym,j表示将记录存储在页面j的可能性，xi,j表示将与相关的记录存储在页面j的可能性。

（2）采取随机取整i策略来获得可行的方案。以ym,j的概率将DB3的第m条记录放置在第j个页面。如果页面溢出，则分配一个空的数据页直到该记录中的所有对象点都放置完毕。

6 仿真实验

6.1 仿真实验环境配置情况

通过实验论证该优化策略的实用性和适用性，为隐私信息加密保护的发展与应用提供新的线索。具体仿真实验配置情况如表1所示。

表1 实验环境设置

6.2 仿真实验结果

由于匿名计算后的位置数据是不稳定的，位置数据是动态的、分散的，不具有任何相关性特征，因此选择查询数据保护的匿名成功率作为度量标准是可行的。同时，为了保证实验的准确性，本文将传统查询计划与优化策略后的查询进行了比较。在固定阈值下，分析了两种方法对查询成功率和查询处理时间的比较。实验结果如图3所示。

图3 仿真实验结果对比

由图3可见，随着匿名度的增加，匿名成功率随之降低，因为随着用户数量的增加，匿名的约束条件和最大值k约束使得匿名成功率降低。经计算，当匿名度为10时，匿名成功率降为86%。当匿名度为2和4时，两种方法的查询处理时间最接近，因为此时都是第一次生成匿名区域，随着匿名度的增长，两种方法的处理时间都有所上升，但是传统的查询方法处理时间上升较快，优化策略方法虽然需要多次匿名，但是每次匿名查询处理时间较短。结合两图可以看出，本文提出的面向隐私的BRNN保护方法优化策略效果比较理想，说明具有较好的稳定性和有效性。