面向隱私的BRNN保護方法優化策略

童威黃啟萍

（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保護方法優化策略效果比較理想，說明具有較好的穩定性和有效性。

7 結束語

本文提出的面向隱私的BRNN保護方法優化策略，使得用戶在使用位置服務的信息時，在不降低匿名度的情況下，最大程度降低查詢處理時間，實時得到精確位置服務。然而，本研究還存在一些不足之處，希望在下一步的研究中，能夠對定位大數據的預處理過程進行有針對性的研究。