童威黃啟萍

（1.安徽文達(dá)信息工程學(xué)院，安徽 合肥 231201；2.安徽電氣工程職業(yè)技術(shù)學(xué)院，安徽 合肥 230051）

1 引言

基于位置的服務(wù)（Location Based Services,LBS），即獲得移動對象的位置后，用戶獲取相關(guān)位置查詢?；谖恢梅?wù)中的隱私內(nèi)容包括位置信息和敏感信息。前者為隱私用戶查詢的確切位置，后者即隱藏與用戶個人隱私有關(guān)的敏感信息[1]。

傳統(tǒng)LBS隱私保護(hù)技術(shù)包含三類：基于數(shù)據(jù)失真的位置隱私保護(hù)技術(shù)；基于抑制發(fā)布的位置隱私保護(hù)技術(shù)；基于數(shù)據(jù)加密的位置隱私保護(hù)技術(shù)[2]。前兩者無法滿足較高隱私需求的用戶要求。本文面向隱私的BRNN查詢（雙色反向最近鄰查詢）保護(hù)方法即基于數(shù)據(jù)加密的位置隱私保護(hù)技術(shù)進(jìn)行探討。

2 預(yù)備知識

在LBS的大部分應(yīng)用中，BRNN是一種常見的查詢方法。給定兩個點集S（服務(wù)集）、R（對象點集），查詢點q∈S，BRNN要查找的是最近鄰q的對象點集合。圖1為一個BRNN示例，圓點表示住宅區(qū)Qi，方塊表示服務(wù)點Si（超市）。某客戶如果想開一家超市，有2個候選位置q1,q2。哪個位置開店可以在距離上吸引更多原本在其他超市購物的居民？通過對候選位置的BRNN查詢，可以得知優(yōu)先度q2>q1，因為q2有最大的BRNN查詢結(jié)果集，包括3個住宅區(qū)Q2,Q3,Q6。

圖1 BRNN示例

隨著移動計算和位置服務(wù)的不斷發(fā)展，BRNN查詢更加廣泛地應(yīng)用在如地圖查詢、資源定位、急救調(diào)度、基于移動現(xiàn)實游戲等領(lǐng)域中[3]。

然而，BRNN查詢可能會導(dǎo)致用戶的隱私泄露。例如，以上示例中，用戶的查詢位置以及商業(yè)意圖將完全暴露給服務(wù)器。已有的BRNN查詢以空間模糊化為基礎(chǔ)，將位置匿名化發(fā)送給服務(wù)器。但是，這類隱私保護(hù)技術(shù)可能保護(hù)度不夠，或者由于匿名隱私保護(hù)，導(dǎo)致查詢結(jié)果精確度不高[4]。本文介紹一種基于PIR的可保證強(qiáng)隱私保護(hù)的BRNN查詢架構(gòu)，并提出一種正交優(yōu)化技術(shù)來進(jìn)一步提高查詢效率。

事實上，已有大量文獻(xiàn)介紹了對BRNN的查詢處理的解決方法。在基于維諾圖的方法中，根據(jù)所有的服務(wù)點和查詢點q構(gòu)建而成，位于q所在的維諾單元的對象即查詢結(jié)果[5]。查詢q基于動態(tài)生成，利用維諾圖的性質(zhì)縮小查詢邊界。制定BRNN查詢處理算法如下：LBS首先離線計算出所有服務(wù)點的維諾圖，當(dāng)查詢q提交時，LBS發(fā)送給客戶端：

（1）維諾單元包含q的服務(wù)點。

（2）這些服務(wù)點所在的維諾單元內(nèi)包含所有對象點。客戶端獲取這些數(shù)據(jù)后，通過驗證距離的大小，過濾真實的BRNN結(jié)果[6]。

3 數(shù)據(jù)組織

在此系統(tǒng)框架中，數(shù)據(jù)組織可以分為3個邏輯數(shù)據(jù)。如圖2所示。DB1存儲所有的維諾單元，DB2存儲每個維諾單元的鄰近維諾單元，DB3存儲每個維諾單元的對象點集[7]。

圖2 3個索引結(jié)構(gòu)示例

4 查詢計劃

給定數(shù)據(jù)組織和查詢q，基于PIR的查詢計劃如下：

（1）客戶端從DB1查詢有關(guān)點q的空間劃分區(qū)域記錄，存儲了當(dāng)前的劃分空間內(nèi)所有維諾單元種子的坐標(biāo)?？蛻舳丝梢酝ㄟ^計算q到這些種子的距離找到離q最近的種子；

（2）客戶端從DB2查詢關(guān)于種子i的記錄，來獲得i周圍的近鄰維諾單元ID，q的維諾單元可以從原始維諾圖中的i及其鄰居維諾單元集獲得；

（3）客戶端查詢DB3中與q和q的鄰居維諾單元中的所有對象點?？蛻舳藢@些對象點進(jìn)行過濾以獲得最終結(jié)果。

根據(jù)圖1中的例子結(jié)合圖2展示的數(shù)據(jù)組織結(jié)構(gòu)。假設(shè)查詢q在五角星的位置提交。DB1將整個空間劃分為4個區(qū)域，分別使用A1、A2、A3、A4表示，每個子區(qū)域和若干維諾單元相交。當(dāng)q提交時，先確定q所在的子區(qū)域A4，并在DB1中通過PIR協(xié)議查詢記錄A4?？蛻舳擞嬎愠霾樵凕cq位于S2單元中，并在DB2中查詢B2來獲取S2的鄰近維諾單元，即S1、S3、S4、S5?？蛻舳擞纱舜_定在DB3中查詢記錄C1、C2、C3、C4和C5。這些記錄提供了需要由客戶端進(jìn)行過濾的候選結(jié)果集，最終O2、O3和O6被過濾掉。

設(shè)計為3個邏輯上的數(shù)據(jù)庫好處如下：

（1）將服務(wù)器和對象點分開存儲，降低了數(shù)據(jù)集發(fā)生更新的代價。

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

數(shù)據(jù)庫中的一條記錄占據(jù)一個頁面的大小。如果不足一個頁面，則需要添加假數(shù)據(jù)來補(bǔ)足。相反，如果數(shù)據(jù)超過一個數(shù)據(jù)頁的大小，則在數(shù)據(jù)庫的末尾生成一個新的數(shù)據(jù)頁，由一個溢出指針從當(dāng)前頁面指向新生成的頁面。

5 優(yōu)化策略

由于在DB3中記錄的缺省存儲是給每個記錄分配不同的數(shù)據(jù)頁，這就導(dǎo)致了數(shù)據(jù)頁的低利用率，使得PIR訪問性能下降。本節(jié)基于查詢計劃提出了合并優(yōu)化策略，將DB2與DB3有關(guān)的記錄合并。

策略步驟：

（1）令NDB2、NDB3分別表示DB2和DB3中的記錄數(shù)。令表示DB2中的第i條記錄表示DB3中與eDB2i相關(guān)的t條記錄。Bm表示DB3中的第m條記錄的大小，該記錄可能會占用多條數(shù)據(jù)頁，其中bm作為Bm中的一個小片段，表示為bm=Bm%Page_size（只有小片段才會與其他的小片段打包）。

（2）令變量ym,j∈{0,1}表示記錄是否存儲在DB3中的第j個頁面，且xi,j∈{0,1}表示所有記錄是否存儲在第j個頁面。另外，對于，有xi,j≥ym,j。同時其中，P是DB3中缺省排列的數(shù)據(jù)頁個數(shù)。

（3）在DB2的第i個記錄中涉及的對象點所需的PIR訪問次數(shù)可以表示為DB3對應(yīng)對象點位于完整數(shù)據(jù)頁面數(shù)和小片段記錄合并后的頁面數(shù)之和，即：

（4）在一個頁面中的對象點總數(shù)不能超過頁面大小，即

（5）令K為DB2中任意記錄查詢所需的最大PIR訪問次數(shù)，即：最小化K，滿足：

分兩步近似求解關(guān)于K的整數(shù)規(guī)劃問題：

（1）為線性規(guī)劃問題，xi,j和ym,j是屬于[0,1]的分?jǐn)?shù)，即ym,j表示將記錄存儲在頁面j的可能性，xi,j表示將與相關(guān)的記錄存儲在頁面j的可能性。

（2）采取隨機(jī)取整i策略來獲得可行的方案。以ym,j的概率將DB3的第m條記錄放置在第j個頁面。如果頁面溢出，則分配一個空的數(shù)據(jù)頁直到該記錄中的所有對象點都放置完畢。

6 仿真實驗

6.1 仿真實驗環(huán)境配置情況

通過實驗論證該優(yōu)化策略的實用性和適用性，為隱私信息加密保護(hù)的發(fā)展與應(yīng)用提供新的線索。具體仿真實驗配置情況如表1所示。

表1 實驗環(huán)境設(shè)置

6.2 仿真實驗結(jié)果

由于匿名計算后的位置數(shù)據(jù)是不穩(wěn)定的，位置數(shù)據(jù)是動態(tài)的、分散的，不具有任何相關(guān)性特征，因此選擇查詢數(shù)據(jù)保護(hù)的匿名成功率作為度量標(biāo)準(zhǔn)是可行的。同時，為了保證實驗的準(zhǔn)確性，本文將傳統(tǒng)查詢計劃與優(yōu)化策略后的查詢進(jìn)行了比較。在固定閾值下，分析了兩種方法對查詢成功率和查詢處理時間的比較。實驗結(jié)果如圖3所示。

圖3 仿真實驗結(jié)果對比

由圖3可見，隨著匿名度的增加，匿名成功率隨之降低，因為隨著用戶數(shù)量的增加，匿名的約束條件和最大值k約束使得匿名成功率降低。經(jīng)計算，當(dāng)匿名度為10時，匿名成功率降為86%。當(dāng)匿名度為2和4時，兩種方法的查詢處理時間最接近，因為此時都是第一次生成匿名區(qū)域，隨著匿名度的增長，兩種方法的處理時間都有所上升，但是傳統(tǒng)的查詢方法處理時間上升較快，優(yōu)化策略方法雖然需要多次匿名，但是每次匿名查詢處理時間較短。結(jié)合兩圖可以看出，本文提出的面向隱私的BRNN保護(hù)方法優(yōu)化策略效果比較理想，說明具有較好的穩(wěn)定性和有效性。

7 結(jié)束語

本文提出的面向隱私的BRNN保護(hù)方法優(yōu)化策略，使得用戶在使用位置服務(wù)的信息時，在不降低匿名度的情況下，最大程度降低查詢處理時間，實時得到精確位置服務(wù)。然而，本研究還存在一些不足之處，希望在下一步的研究中，能夠?qū)Χㄎ淮髷?shù)據(jù)的預(yù)處理過程進(jìn)行有針對性的研究。