面向隱私的BRNN保護(hù)方法優(yōu)化策略

童威黃啟萍

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

1 引言

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

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

2 預(yù)備知識(shí)

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

圖1 BRNN示例

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

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

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

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

（2）這些服務(wù)點(diǎn)所在的維諾單元內(nèi)包含所有對(duì)象點(diǎn)?？蛻?hù)端獲取這些數(shù)據(jù)后，通過(guò)驗(yàn)證距離的大小，過(guò)濾真實(shí)的BRNN結(jié)果[6]。

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

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

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

4 查詢(xún)計(jì)劃

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

（1）客戶(hù)端從DB1查詢(xún)有關(guān)點(diǎn)q的空間劃分區(qū)域記錄，存儲(chǔ)了當(dāng)前的劃分空間內(nèi)所有維諾單元種子的坐標(biāo)?？蛻?hù)端可以通過(guò)計(jì)算q到這些種子的距離找到離q最近的種子；

（2）客戶(hù)端從DB2查詢(xún)關(guān)于種子i的記錄，來(lái)獲得i周?chē)慕従S諾單元ID，q的維諾單元可以從原始維諾圖中的i及其鄰居維諾單元集獲得；

（3）客戶(hù)端查詢(xún)DB3中與q和q的鄰居維諾單元中的所有對(duì)象點(diǎn)?？蛻?hù)端對(duì)這些對(duì)象點(diǎn)進(jìn)行過(guò)濾以獲得最終結(jié)果。

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

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

（1）將服務(wù)器和對(duì)象點(diǎn)分開(kāi)存儲(chǔ)，降低了數(shù)據(jù)集發(fā)生更新的代價(jià)。

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

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

5 優(yōu)化策略

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

策略步驟：

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

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

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

（4）在一個(gè)頁(yè)面中的對(duì)象點(diǎn)總數(shù)不能超過(guò)頁(yè)面大小，即

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

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

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

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

6 仿真實(shí)驗(yàn)

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

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

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

6.2 仿真實(shí)驗(yàn)結(jié)果

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

圖3 仿真實(shí)驗(yàn)結(jié)果對(duì)比

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

7 結(jié)束語(yǔ)

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