劉曉樂　李　博

(河南工程學(xué)院計(jì)算機(jī)學(xué)院　河南 鄭州 451191)

?

隱私保護(hù)下的組最近鄰查詢算法研究

劉曉樂李博

(河南工程學(xué)院計(jì)算機(jī)學(xué)院河南 鄭州 451191)

摘要針對(duì)現(xiàn)有的組最近鄰GNN(Group Nearest Neighbor)查詢的隱私保護(hù)算法沒有考慮地圖匹配攻擊的問題，在無可信第三方的模型下，提出基于三階段的保護(hù)用戶位置隱私的組最近鄰算法SFR(Send-Filter-Refine)。發(fā)送階段中用戶向服務(wù)商發(fā)送可防御地圖匹配攻擊的矩形區(qū)域來代替精確位置；過濾階段中服務(wù)商利用各區(qū)域計(jì)算所有可能成為結(jié)果的數(shù)據(jù)點(diǎn)并回傳給用戶；求精階段為了防止發(fā)起查詢的用戶間的隱私泄露，通過用戶間的無序交互來得到最終的查詢結(jié)果,并提出多個(gè)剪枝策略來加快查詢速度。基于真實(shí)路網(wǎng)的實(shí)驗(yàn)結(jié)果表明，SFR與傳統(tǒng)方法相比，有更高的查詢效率和更低的受攻擊率。

關(guān)鍵詞組最近鄰隱私保護(hù)位置服務(wù)提供商

0引言

近年來，隨著移動(dòng)計(jì)算技術(shù)和通信技術(shù)的不斷發(fā)展，隨時(shí)隨地獲得個(gè)人精確位置成為可能，基于位置的服務(wù)LBS(Location Based Service)受到人們的普遍關(guān)注。組最近鄰GNN查詢[1]是最近鄰NN查詢[2]的一種變體，它查找的是到給定多個(gè)查詢對(duì)象距離之和最小的點(diǎn)。GNN查詢在現(xiàn)實(shí)生活中有廣泛的應(yīng)用，例如，由多個(gè)社區(qū)所組成的社交網(wǎng)絡(luò)中，查找各個(gè)社區(qū)的領(lǐng)導(dǎo)者/核心，可以查找到該社區(qū)中各成員距離和(表示成員間的熟悉程度)最小的人；同一城市的一組用戶想查詢一家離他們距離之和最小的餐館作為見面地點(diǎn)等。

然而，用戶在享用LBS的同時(shí)，包含他們精確位置的信息被位置服務(wù)提供商LSP(Location Service Provider)所獲取。LSP能夠根據(jù)這些信息得到用戶的生活方式、健康狀況和政治背景等[3]。個(gè)人隱私泄露問題逐漸引起廣大學(xué)者的關(guān)注[4-6]。

圖1　用戶的精確位置及相應(yīng)的位置區(qū)域

為了在提供LBS的同時(shí)，保護(hù)用戶的隱私，一種解決方法是利用可信的第三團(tuán)體TTP(Trusted Third Party)在用戶和LSP之間進(jìn)行通信[7]。這種方法有一定的局限：(1)所有用戶將位置信息暴露給TTP，存在單點(diǎn)被攻擊的危險(xiǎn)；(2)用戶的隱私只在當(dāng)前時(shí)刻被保護(hù)，不能保證“相關(guān)攻擊”(如用戶運(yùn)動(dòng)的歷史軌跡)。另一種常用的方法是用戶向LSP發(fā)送一個(gè)位置范圍(通常是一個(gè)矩形)來代替精確的位置[3]，如圖1所示，用矩形區(qū)域代替精確位置點(diǎn)。LSP返回該矩形下所有可能成為查詢結(jié)果的數(shù)據(jù)點(diǎn)，用戶再根據(jù)自己的精確位置，從這些點(diǎn)中直接找到最終的結(jié)果。這種無TTP參與的模型，避免了上述問題。本文采取的就是無TTP模型。

盡管無TTP模型下的NN查詢相關(guān)的隱私保護(hù)技術(shù)有很多[8]。但由于GNN查詢中發(fā)出查詢的用戶有多個(gè)，它的查詢結(jié)果取決于所有查詢用戶的位置，單個(gè)用戶無法只根據(jù)自己的精確位置信息來得到GNN結(jié)果。因此，傳統(tǒng)用于NN查詢的隱私保護(hù)技術(shù)無法直接應(yīng)用到GNN查詢中。文獻(xiàn)[9]首次解決了隱私保護(hù)下的GNN查詢算法，但算法使用簡單的矩形區(qū)域代替用戶的精確位置，容易受到地圖匹配的攻擊。例如，攻擊者在獲取地圖信息后，可通過地圖匹配的方法排除一些障礙區(qū)域(如湖泊等)，從而大大增加攻擊的概率。此外，地圖中所包含一些如醫(yī)院、減肥中心等重要的語義信息，簡單的矩形區(qū)域可能包含這些敏感信息，也容易泄露用戶個(gè)人隱私。另外，發(fā)出GNN查詢的用戶雖然有可能彼此熟識(shí)，但用戶之間也需要保護(hù)位置隱私，這為隱私保護(hù)下的GNN查詢提出了新的挑戰(zhàn)。

本文解決了GNN查詢的隱私保護(hù)問題，所提出的基于三階段的查詢算法SFR。不僅可有效防御地圖匹配攻擊，還能保護(hù)發(fā)起查詢的各個(gè)用戶間的位置隱私。在發(fā)送階段，用戶結(jié)合地圖中的語義信息向LSP發(fā)送各自的位置區(qū)域來代替精確位置，避免用戶位置隱私的泄露并防御地圖匹配攻擊；在過濾階段，提出了針對(duì)位置區(qū)域的GNN查詢算法，所提的剪枝策略能夠有效過濾掉那些一定不是結(jié)果的數(shù)據(jù)點(diǎn)；最后在求精階段計(jì)算出最終精確的GNN結(jié)果，用戶間進(jìn)行的無序交互，避免了用戶間的隱私泄露，并最終得到正確的查詢結(jié)果。

最后，基于真實(shí)城市路網(wǎng)，對(duì)本文所提算法SFR與文獻(xiàn)[9]所提的算法IPPF進(jìn)行了性能比較和驗(yàn)證。實(shí)驗(yàn)結(jié)果表明，與IPPF相比，SFR有更高的查詢效率和更低的受攻擊率。

1問題定義

本文假設(shè)用戶和LSP通過網(wǎng)絡(luò)(移動(dòng)網(wǎng)絡(luò)或因特網(wǎng))互相連接，查詢集合Q由n個(gè)用戶u1,u2, …,un組成，它們相應(yīng)的位置用l1,l2, …,ln來表示，被查詢的數(shù)據(jù)點(diǎn)集合用P表示。下面列出了傳統(tǒng)針對(duì)點(diǎn)的GNN查詢以及隱私保護(hù)下針對(duì)區(qū)域的GNN查詢的形式化定義。

隱私保護(hù)下的GNN查詢中，LSP只知道各用戶的位置區(qū)域，所有用戶到數(shù)據(jù)點(diǎn)的距離之和是一個(gè)范圍，而不是一個(gè)值，因此無法直接得到精確的GNN結(jié)果。算法SFR先執(zhí)行針對(duì)這些區(qū)域的GNN查詢，來得到所有可能成為結(jié)果的數(shù)據(jù)點(diǎn)，放在候選集合Scnd中。Scnd中的對(duì)象都是可能成為最終GNN結(jié)果的點(diǎn)，所有可能成為GNN結(jié)果的點(diǎn)也一定在Scnd中。本文在下一節(jié)中對(duì)如何快速得到Scnd，以及如何利用Scnd進(jìn)一步得到最終的GNN結(jié)果進(jìn)行了詳細(xì)的介紹。

2隱私保護(hù)下的GNN查詢算法SFR

SFR采用無TTP模型，即不存在任何中心節(jié)點(diǎn)參與查詢運(yùn)算，但由于GNN查詢結(jié)果取決于所有發(fā)出查詢用戶的精確位置，單個(gè)用戶無法直接根據(jù)自己的位置計(jì)算出結(jié)果，這給無TTP模型下的GNN查詢帶來了難度和挑戰(zhàn)。

本文提出了由協(xié)調(diào)者參與的查詢算法框架，在進(jìn)行GNN查詢之前，系統(tǒng)隨機(jī)選取一個(gè)協(xié)調(diào)者，用來協(xié)助系統(tǒng)完成隱私保護(hù)下的GNN查詢。該協(xié)調(diào)者可以是發(fā)出GNN查詢的其中一個(gè)用戶，也可以是系統(tǒng)中不參與查詢的其他用戶。它與中心節(jié)點(diǎn)的不同之處在于，不同的GNN查詢，系統(tǒng)所選取的協(xié)調(diào)者是不同的，從而消除了單個(gè)節(jié)點(diǎn)被攻擊的危險(xiǎn)。此外，協(xié)調(diào)者只能獲得用戶的ID以及它所發(fā)出的查詢類型，而不知道用戶所在的位置，進(jìn)而保護(hù)了用戶與協(xié)調(diào)者之間的位置隱私。本節(jié)將對(duì)基于三階段的SFR算法進(jìn)行詳細(xì)介紹。

2.1發(fā)送階段

發(fā)出GNN查詢的組內(nèi)每個(gè)用戶首先向協(xié)調(diào)者注冊自己的ID(如IP地址、電話號(hào)碼等)，并從協(xié)調(diào)者處獲得一個(gè)查詢ID(QID)。再結(jié)合地圖中的語義信息，生成自己的安全位置區(qū)域，把該區(qū)域和QID發(fā)送給LSP，在因特網(wǎng)中發(fā)送時(shí)可采用假名服務(wù)[10]的方法，在無線個(gè)人區(qū)域網(wǎng)絡(luò)(如藍(lán)牙或802.11)中發(fā)送時(shí)可采用隨機(jī)選取節(jié)點(diǎn)[8]的方法。這些技術(shù)能夠向LSP隱藏用戶的ID信息。最后，協(xié)調(diào)者只把與GNN查詢有關(guān)的信息(QID、組查詢用戶個(gè)數(shù))發(fā)送給LSP。

生成用戶的安全位置區(qū)域首先要考慮地圖匹配攻擊，這是因?yàn)楣粽咴讷@取地圖信息后，可通過地圖匹配的方法排除一些行人車輛無法到達(dá)的障礙區(qū)域(如湖泊等)，從而增加攻擊的概率；其次還要考慮地圖中包含的重要語義信息的泄露，這是因?yàn)榈貓D文件不僅包含位置坐標(biāo)等信息，還包含著更重要的語義信息，如醫(yī)院、減肥中心和軍事要地等。攻擊者可根據(jù)一些敏感的語義信息來獲取用戶生活方式、健康狀況和政治背景等個(gè)人隱私。

針對(duì)重要語義信息的保護(hù)問題，系統(tǒng)先在地圖上定義了幾個(gè)類型的重點(diǎn)保護(hù)區(qū)域(如醫(yī)院、減肥中心、心理診所等)，先離線預(yù)計(jì)算出這些區(qū)域?qū)?yīng)的一些安全區(qū)域，使得安全區(qū)域要么不包括重要區(qū)域，要么包含k種重要區(qū)域。若用戶處在這些重點(diǎn)保護(hù)區(qū)域內(nèi)，直接為其生成安全區(qū)域。當(dāng)用戶所要保護(hù)的語義類型不在系統(tǒng)的預(yù)計(jì)算列表中時(shí)，系統(tǒng)再為用戶在線構(gòu)建安全的位置區(qū)域。發(fā)送階段的安全區(qū)域生成算法見算法1。

算法1安全區(qū)域生成算法

輸入：N個(gè)用戶的精確位置(*ax, *ay), 障礙閾值δ;

輸出：N個(gè)用戶的安全區(qū)域(*lx, *ly, *hx, *hy);

1.for(i =1toN)

2.if(該點(diǎn)處在預(yù)計(jì)算的重點(diǎn)保護(hù)區(qū)域內(nèi))

3.return相應(yīng)的(lx[i], ly[i], hx[i], hy[i]);

4.else

5.生成一個(gè)包含點(diǎn)(ax[i], ay[i])、長寬各為

1000的矩形(lx[i], ly[i], hx[i], hy[i]);

6.Swhole= 1000000;

7.計(jì)算該矩形內(nèi)障礙空間的面積Sobstacle;

9.改變矩形或增加長和寬;

10. 重新計(jì)算Swhole；

11.return滿足閥值的lx[i],ly[i],hx[i],hy[i];

2.2過濾階段

LSP接到GNN查詢請求后，執(zhí)行RGNN查詢。由于用戶的位置是一個(gè)區(qū)域，數(shù)據(jù)點(diǎn)與查詢用戶間的距離是一個(gè)范圍而不是一個(gè)固定值，許多數(shù)據(jù)點(diǎn)都可能成為最終的結(jié)果。過濾階段的目的就是如何快速得到RGNN定義中的候選集合Scnd，使得Scnd中的對(duì)象都是可能成為最終GNN結(jié)果的點(diǎn)，而所有可能成為GNN結(jié)果的點(diǎn)也一定在Scnd中。本文改進(jìn)傳統(tǒng)最佳優(yōu)先BF(Best-First)[11]查找算法，提出了MBF(ModifiedBest-First)算法來執(zhí)行RGNN查詢。

MBF算法與BF算法的執(zhí)行過程類似，但由于MBF處理的是多個(gè)區(qū)域(矩形)，元素到多個(gè)矩形的距離之和是一個(gè)范圍，因此查找過程以及算法結(jié)束條件更加復(fù)雜。算法的思想就是按照ds值由小到大來處理R*樹中的結(jié)點(diǎn)，直到找到某結(jié)點(diǎn)。若其ds值大于當(dāng)前所處理過的結(jié)點(diǎn)中最小的dl值，剩下結(jié)點(diǎn)中的數(shù)據(jù)點(diǎn)就可以被過濾掉。具體見算法2。

算法2過濾算法MBF (Modified Best-First)

輸入：N個(gè)用戶的位置區(qū)域(*lx,*ly,*hx,*hy),R*樹;

輸出：可能成為結(jié)果的候選集合Scnd;

1.Scnd初始化為空;

2.優(yōu)先隊(duì)列PQ初始化為R*樹的根結(jié)點(diǎn)root;

3.全局變量minmaxdist= root.dl;

4.while (PQ不為空) do

5.從PQ中取一個(gè)結(jié)點(diǎn)pc;

6.if (pc.ds>minmaxdist) returnScnd;

7.minmaxdist= min{minmaxdist,pc.dl};

8.if (pc是中間結(jié)點(diǎn))

9.計(jì)算每個(gè)孩子的ds值并按升序插到PQ中;

10.else

11.將pc插入到集合Scnd中;

12.returnScnd;

初始時(shí)把根結(jié)點(diǎn)(root)放入優(yōu)先隊(duì)列PQ中，優(yōu)先隊(duì)列中的元素(中間結(jié)點(diǎn)MBR或者是葉子結(jié)點(diǎn)存儲(chǔ)的數(shù)據(jù)點(diǎn))按照其ds進(jìn)行升序排列。算法不斷地從隊(duì)列中取出有最小ds的元素進(jìn)行處理。記錄和更新全局變量minmaxdist使它始終是所有被處理過的數(shù)據(jù)點(diǎn)的dl的最小值(行3和7)。這樣，當(dāng)從優(yōu)先隊(duì)列中取出的元素pc的ds大于minmaxdist時(shí)，pc以及優(yōu)先隊(duì)列中的其他元素就可被剪枝掉(行6)，在pc之前被處理的數(shù)據(jù)點(diǎn)則被放入候選集合中(行11)。下面給出MBF算法的正確性證明。

定理1假設(shè)minmaxdist是某數(shù)據(jù)點(diǎn)p到各查詢矩形最大距離之和，pc是從當(dāng)前從優(yōu)先隊(duì)列中取出的元素，若ds(pc)>minmaxdist，則pc以及優(yōu)先隊(duì)列中的剩余元素不可能是最終的GNN查詢結(jié)果。

證明：反證法。假設(shè)最終的GNN結(jié)果是pc或優(yōu)先隊(duì)列中剩余元素中的其中一個(gè)，記作pr。根據(jù)RGNN的定義可知，無論發(fā)出查詢的n個(gè)用戶處在查詢矩形的哪個(gè)位置，pr到這n個(gè)用戶的距離之和都要小于其他數(shù)據(jù)點(diǎn)。根據(jù)已知條件pc.ds>minmaxdist，且優(yōu)先隊(duì)列是按照各元素的ds值進(jìn)行升序排列，因此pr.ds>pc.ds>minmaxdist。也就是說，無論發(fā)出查詢的n個(gè)用戶處在查詢矩形的哪個(gè)位置，p到這n個(gè)用戶的距離之和都要小于pr。與假設(shè)相矛盾，定理成立，證畢。

2.3求精階段

求精階段是保護(hù)用戶與LSP之間以及用戶彼此間隱私的關(guān)鍵，該階段的目的是在不泄露用戶隱私的前提下，對(duì)Scnd中的數(shù)據(jù)點(diǎn)進(jìn)行求精計(jì)算，進(jìn)而得到最終正確的GNN結(jié)果。

假設(shè)發(fā)出GNN查詢的用戶有4個(gè)，過濾階段得到的候選集中有5個(gè)數(shù)據(jù)點(diǎn)。用戶與各數(shù)據(jù)點(diǎn)間的距離如表1所示。為保護(hù)用戶與LSP間的隱私，用戶不會(huì)把位置信息發(fā)送給LSP，而是通過用戶間的交互，把最終的距離和發(fā)送給LSP。如表2所示，u1把其到p1的距離2發(fā)送給u2，u2再用其到p1的距離更新當(dāng)前和，即得到11，并發(fā)送給u3。最后，u4計(jì)算出全部和24，發(fā)送給LSP。以此類推，計(jì)算出所有點(diǎn)的距離和，和最小的點(diǎn)就是最終結(jié)果，即p4。

表1　用戶與Scnd中各數(shù)據(jù)點(diǎn)的精確距離

表2　用戶更新與Scnd中各數(shù)據(jù)點(diǎn)的距離和

以上方法在用戶之間進(jìn)行距離傳遞時(shí)，可能會(huì)在彼此間泄露隱私。例如u1總是把自己到其他數(shù)據(jù)點(diǎn)的距離傳遞給u2，u2就可以根據(jù)u1到任意兩個(gè)數(shù)據(jù)點(diǎn)的距離來得到u1的精確位置。為了保護(hù)用戶間的隱私，SFR在更新距離和時(shí)，對(duì)Scnd中不同的數(shù)據(jù)點(diǎn)，用戶的交互(更新)順序隨機(jī)產(chǎn)生。當(dāng)GNN查詢只有2個(gè)用戶時(shí)，先更新距離的第一個(gè)用戶會(huì)把自己的位置信息暴露給第二個(gè)用戶。這種情況下，協(xié)調(diào)者需要充當(dāng)?shù)谌齻€(gè)用戶參與交互。由于用戶只向協(xié)調(diào)者發(fā)送QID以及更新后的距離信息，并不會(huì)暴露自己的ID和位置信息，從而保護(hù)了用戶的隱私。

此外，為了提高計(jì)算效率，本文還提出了剪枝算法來優(yōu)化求精過程。SFR用一個(gè)全局變量SUM記錄當(dāng)前已計(jì)算的距離和的最小值用來剪枝。若某用戶更新后的距離和大于SUM，則該數(shù)據(jù)點(diǎn)就可被剪枝掉，無需再計(jì)算其他用戶到該點(diǎn)的距離，從而減少了計(jì)算代價(jià)。具體算法見算法3。

算法3優(yōu)化求精算法

輸入：用戶個(gè)數(shù)N, 候選集合Scnd以及候選對(duì)象個(gè)數(shù)M;

輸出：查詢結(jié)果rst;

1.全局變量SUM= ∞; *sum=0;

2.for (i= 1 toM)

3.隨機(jī)產(chǎn)生用戶的一個(gè)更新順序list;

4.for (j= 1 toN)

5.計(jì)算用戶list[j]到對(duì)象Scnd[i]的距離dist；

6.sum[i] =sum[i] +dist;

7.if (sum[i] >SUM)

8.break;

9.if (j==N&&sum[i]

10.SUM=sum[i];

11.rst=Scnd[i];

12.returnrst;

根據(jù)算法3，表3給出了優(yōu)化后的求精算法的一個(gè)測試用例。根據(jù)表1中用戶與數(shù)據(jù)點(diǎn)的實(shí)際距離可知，p2經(jīng)過各用戶的更新，所得到的SUM值13是當(dāng)前最小的距離和(行9-11)。對(duì)于p3，在u4更新完距離和后，當(dāng)前距離和16大于13，因此p3可直接被剪枝，u1到p3的距離無需計(jì)算(行7-8)。同理，計(jì)算p5時(shí)，也減少了兩個(gè)用戶的距離計(jì)算。最終的結(jié)果rst就是p4。

表3優(yōu)化后的求精過程

3實(shí)驗(yàn)結(jié)果

為驗(yàn)證本文所提算法SFR的有效性，本節(jié)在真實(shí)城市路網(wǎng)上生成數(shù)據(jù)集對(duì)算法SFR以及文獻(xiàn)[9]所提的算法IPPF從查詢效率和受攻擊率兩個(gè)角度進(jìn)行了對(duì)比實(shí)驗(yàn)。兩個(gè)算法的區(qū)別之一是SFR在生成安全區(qū)域時(shí)考慮了地圖匹配攻擊，產(chǎn)生的區(qū)域可能比算法IPPF要大，但可以減少受攻擊的次數(shù)。區(qū)別之二是在用戶更新時(shí)，SFR考慮了用戶間的隱私泄露問題，并提出了優(yōu)化的求精算法。

3.1實(shí)驗(yàn)環(huán)境

本文使用Oldenburg(德國城市)真實(shí)的道路網(wǎng)絡(luò)，并基于該路網(wǎng)定義了一些障礙空間(每10條街道產(chǎn)生一個(gè)100×100的障礙區(qū)域)以及一些包含語義信息的點(diǎn)(每條街道平均產(chǎn)生五個(gè)語義點(diǎn)，代表超市、餐廳、商場、醫(yī)院等)。假設(shè)攻擊者了解地圖的這些信息，當(dāng)用戶發(fā)出一個(gè)矩形區(qū)域時(shí)，攻擊者先根據(jù)地圖信息去掉該矩形區(qū)域內(nèi)的障礙空間，再從剩余區(qū)域內(nèi)隨機(jī)選擇一個(gè)語義點(diǎn)作為攻擊，如果與該用戶的實(shí)際位置一致，則認(rèn)為用戶隱私泄露。

查詢算法的響應(yīng)時(shí)間是衡量算法性能最重要的標(biāo)準(zhǔn)之一。當(dāng)被查詢數(shù)據(jù)點(diǎn)的個(gè)數(shù)、發(fā)出查詢的用戶個(gè)數(shù)以及用戶發(fā)送給LSP的位置區(qū)域面積這三個(gè)因素的規(guī)模增大時(shí)，算法響應(yīng)時(shí)間的增加速度能夠反映算法的可擴(kuò)展性。因此，本文實(shí)驗(yàn)中分別考察了這三個(gè)因素對(duì)查詢算法響應(yīng)時(shí)間的影響，從而驗(yàn)證算法的可擴(kuò)展性。對(duì)于隱私保護(hù)下的查詢算法來說，除了算法的響應(yīng)時(shí)間，其受攻擊率是另外一個(gè)重要的衡量標(biāo)準(zhǔn)。顯然，用戶發(fā)送給LSP的位置區(qū)域面積與受攻擊率之間的關(guān)系較為密切，因此，本文在實(shí)驗(yàn)中還考察了該因素對(duì)查詢算法受攻擊率的影響。其中數(shù)據(jù)點(diǎn)個(gè)數(shù)從5000增加到20 000，20 000是默認(rèn)值。用戶個(gè)數(shù)從4到1024以4的倍數(shù)增長，默認(rèn)值是64。位置區(qū)域大小則從2002增加到10002，默認(rèn)值是6002。在研究一種參數(shù)對(duì)算法效率的影響時(shí)，其他參數(shù)設(shè)置為默認(rèn)值。每組實(shí)驗(yàn)中，執(zhí)行100次GNN查詢，再取平均值用來分析。

本文所有算法都使用標(biāo)準(zhǔn)C++在Windows 7操作系統(tǒng)下實(shí)現(xiàn)，電腦配置為：Intel Core2 CPU, 2.20 GHz,2 GB內(nèi)存，500 GB硬盤。

3.2結(jié)果分析

圖2列出了被查詢的數(shù)據(jù)點(diǎn)個(gè)數(shù)對(duì)SFR和IPPF算法響應(yīng)時(shí)間的影響?？梢钥闯觯S著數(shù)據(jù)點(diǎn)個(gè)數(shù)的增加，兩個(gè)算法的響應(yīng)時(shí)間都有所增加。這是因?yàn)楸徊樵凕c(diǎn)越多，需要進(jìn)行的距離計(jì)算越多。另外，可能成為用戶組最近鄰結(jié)果的對(duì)象數(shù)目也會(huì)增加，從而導(dǎo)致過濾階段得到的候選結(jié)果增多，求精階段用戶所需要更新的距離也隨之增加。從圖中還可以看出，SFR查詢效率略微高于IPPF。這是由于SFR算法在求精階段利用保存的全局變量對(duì)候選結(jié)果進(jìn)行剪枝，減少了用戶到候選結(jié)果之間距離的計(jì)算代價(jià)，從而提高了整體的查詢效率。

圖2　數(shù)據(jù)點(diǎn)個(gè)數(shù)對(duì)算法響應(yīng)時(shí)間的影響

圖3給出了兩種算法響應(yīng)時(shí)間隨著同一查詢集合內(nèi)用戶個(gè)數(shù)增加的變化趨勢。用戶個(gè)數(shù)增多，所需的距離計(jì)算增多，用戶與LSP交互過程中需要傳輸?shù)臄?shù)據(jù)也增多。另外傳送給LSP的矩形增多，也會(huì)使可能成為組最近鄰的候選對(duì)象增多，增加了后續(xù)剪枝和交互的計(jì)算代價(jià)，因此兩個(gè)算法的響應(yīng)時(shí)間都有所增加。與IPPF相比，SFR算法響應(yīng)時(shí)間增加得比較緩慢，表現(xiàn)出了良好的擴(kuò)展性。

圖3　用戶個(gè)數(shù)對(duì)算法響應(yīng)時(shí)間的影響

圖4和圖5分別列出了用戶向LSP發(fā)送的位置區(qū)域的大小對(duì)SFR和IPPF算法在查詢響應(yīng)時(shí)間和受攻擊率兩方面的影響。對(duì)于算法IPPF來說，橫坐標(biāo)的值就代表用戶發(fā)出的位置區(qū)域的邊長；而對(duì)SFR來說，由于考慮地圖匹配攻擊，算法會(huì)在默認(rèn)區(qū)域的基礎(chǔ)上，通過調(diào)整位置或大小來滿足指定的障礙閾值δ，因此一般會(huì)比原區(qū)域略大一些。從圖4可以看出，隨著區(qū)域的增大，兩種算法的響應(yīng)時(shí)間都增加了。主要原因就是區(qū)域的增加使得LSP計(jì)算的可能成為組最近鄰結(jié)果的對(duì)象變多，增加了求精階段的計(jì)算代價(jià)。與IPPF相比，SFR查詢時(shí)間的變化較小，這是因?yàn)镾FR在位置區(qū)域默認(rèn)較小時(shí)，考慮到地圖匹配攻擊，也會(huì)將大的區(qū)域發(fā)送給LSP，因此響應(yīng)時(shí)間變化不明顯。

從圖5可以看出，區(qū)域的增大，使得IPPF的受攻擊率有所下降。這是因?yàn)閰^(qū)域增大，攻擊者能夠猜到用戶真實(shí)位置的概率會(huì)下降，因此受到攻擊的次數(shù)變少。而對(duì)SFR來說，受攻擊率并沒有受區(qū)域大小的變化有太大的影響，始終都保持在一個(gè)較低的受攻擊率，這是由于無論默認(rèn)的區(qū)域是多大，SFR在發(fā)送階段都考慮了可能遭受的地圖匹配攻擊，因此能夠一直保持較高的隱私保護(hù)能力。

圖4　位置區(qū)域大小對(duì)算法響應(yīng)時(shí)間的影響

圖5　位置區(qū)域大小對(duì)算法受攻擊率的影響

4結(jié)語

本文基于無TTP模型，提出了隱私保護(hù)下的基于三階段的GNN查詢算法SFR。首先用戶向LSP只發(fā)送能有效防御地圖匹配攻擊的位置區(qū)域來隱藏各自的真實(shí)位置信息；其次，基于這些位置區(qū)域，LSP利用剪枝策略過濾掉那些不可能成為查詢結(jié)果的數(shù)據(jù)點(diǎn)，快速得到候選集合；最后通過用戶之間的交互，從候選集中查找最終的結(jié)果，在交互過程中不僅充分考慮了用戶間的隱私保護(hù)問題，還提出了剪枝算法來優(yōu)化計(jì)算過程?；谡鎸?shí)城市路網(wǎng)下的實(shí)驗(yàn)結(jié)果表明，SFR與傳統(tǒng)方法相比，有較高的查詢效率和較低的受攻擊率。

參考文獻(xiàn)

[1] Deng K, Sadiq S, Zhou X F, et al. On group nearest neighbor query processing[J].IEEE Transactions on Knowledge and Data Engineering (TKDE), 2012,24(2):295-308.

[2] Chatzimlioudis G, Zeinalipour-Yazti D, Lee W Q, et al. Continuous all k-nearest-neighbor querying in smartphone networks[C]//Proceedings of the 13th International Conference on Mobile Data Management，MDM’12, 2012:79-88.

[3] Shin K G, Ju X, Chen Z, et al. Privacy protection for users of location-based services[J].Wireless Communications,2012,19(1): 30-39.

[4] 朱青, 趙桐, 王珊. 面向查詢服務(wù)的數(shù)據(jù)隱私保護(hù)算法[J].計(jì)算機(jī)學(xué)報(bào), 2010,33(8):1315-1323.

[5] 李瑋, 楊庚. 保護(hù)隱私性與完整性的低能耗數(shù)據(jù)融合算法[J].計(jì)算機(jī)應(yīng)用,2013,33(9):2505-2510, 2515.

[6] 崔麗群，張明杰.車載網(wǎng)絡(luò)中隱私保護(hù)方法[J]. 計(jì)算機(jī)應(yīng)用, 2013, 33(9):2516-2519, 2524.

[7] Wernke M, Skvortsov P, Durr F, et al. A classification of location privacy attacks and approaches[J].Personal and ubiquitous computing, 2014,18(1):163-175.

[8] Wernke M, Durr F, Rothermel K. PShare: Ensuring location privacy in non-trusted systems through multi-secret sharing[J]. Pervasive and Mobile Computing, 2013,9(3):339-352.

[9] Hashem T, Kulik L, Zhang R. Privacy preserving group nearest neighbor queries[C]//In EDBT, 2010:489-500.

[10] Vu K, Zheng R, Gao J. Efficient algorithms for k-anonymous location privacy in participatory sensing[C]//Proceedings of the 2012 International Conference on INFOCOM, 2012:2399-2407.

[11] Hjaltason G R, Samet H. Distance browsing in spatial databases[J].Acm Transactions on Database System,1999,24(2):265-318.

[12] Beckmann N, Kriegel H P, Schneider R, et al. The R*tree: an efficient and robust access method for points and rectangles[J].Acm Sigmod Record,1990,19(2):322-331.

ON GROUP NEAREST NEIGHBOUR QUERY ALGORITHM FOR PRIVACY-PRESERVING

Liu XiaoleLi Bo

(SchoolofComputer,HenanInstituteofEngineering,Zhengzhou451191,Henan,China)

AbstractExisting private-preserving algorithm for group nearest neighbour (GNN) query ignores map matching attacks. To avoid this problem, we proposed a GNN algorithm for preserving the privacy of users location, which is based on three phases of send-filter-refine (SFR), in the model of no-trusted third party. In sending phase, users send the rectangular regions capable of defending map matching attacks instead of accurate locations to location service provider (LSP). In filtering phase, LSP utilises these regions to calculate all the points possibly being the GNN results and returns them to users. And in refining phase, in order to prevent revealing the privacies among those users initiating queries, the final query result is obtained by unordered interactions between users, and we proposed a couple of pruning strategies to speed up the query. Result of the experiment based on real road network showed that SFR had higher query efficiency and lower rate of being attacked than the traditional algorithm.

KeywordsGroup nearest neighbourPrivacy-preservingLocation service provider

收稿日期：2014-09-02。國家自然科學(xué)基金項(xiàng)目(61301232)；河南省科技廳基礎(chǔ)與前沿技術(shù)研究計(jì)劃項(xiàng)目(142300410131)。劉曉樂，講師，主研領(lǐng)域：計(jì)算機(jī)應(yīng)用，網(wǎng)絡(luò)信息安全。李博，講師。

中圖分類號(hào)TP391

文獻(xiàn)標(biāo)識(shí)碼A

DOI:10.3969/j.issn.1000-386x.2016.05.075