基于四叉樹結(jié)構(gòu)的增量近鄰查詢方法

莊禮金

（廣東理工學院，廣東肇慶，526100）

0 引言

傳感器技術(shù)和移動通訊設(shè)備飛速發(fā)展，使位置服務(wù)得到廣泛的應(yīng)用。位置是將移動通信設(shè)備的位置和其他信息整合起來，為用戶提供增值服務(wù)，即用戶將當前位置信息和查詢請求內(nèi)容發(fā)送給位置服務(wù)器，以獲得查詢位置服務(wù)，其中最主要的位置服務(wù)有：廣告分發(fā)服務(wù)；交通導航服務(wù)；信息娛樂服務(wù)等等。攻擊者能夠根據(jù)位置數(shù)據(jù)的時空敏感特性推測出用戶的個人信息、位置信息等。用戶獲取位置服務(wù)既有利又有弊，因而位置隱私問題亟待解決。

現(xiàn)有的位置隱私保護方法主要分為3類：基于加密法、基于政策法和基于扭曲法的位置隱私保護[1]。目前，許多研究者致力于基于扭曲法的位置隱私保護的隱私需求和服務(wù)質(zhì)量之間尋找一個平衡點。Yiu等人提出SpaceTwist的查詢方法[2]是用代理查詢點代替目標用戶進行查詢處理，目標用戶根據(jù)自身的隱私需求在興趣點候選集中選取k個近鄰興趣點。由于目標用戶直接選取代理查詢點進行查詢處理，沒有構(gòu)造匿名區(qū)域，其計算代價和通信代價較低，但是目標用戶查詢處理過程中沒有和其他用戶進行協(xié)作，沒有達到k-匿名。文獻[3]提出一種基于SpaceTwist的k-匿名增量近鄰查詢位置隱私保護算法，該算法是目標用戶根據(jù)自身的隱私需求與路網(wǎng)環(huán)境構(gòu)造匿名區(qū)域進行查詢處理。文獻[4]采用客戶服務(wù)器系統(tǒng)結(jié)構(gòu)，容易實現(xiàn)的同時造成共享資源浪費。目標用戶利用四叉樹索引劃分路網(wǎng)節(jié)點構(gòu)建匿名區(qū)，請求路網(wǎng)和興趣點位置信息，增加查詢通信開銷。文獻[5]提出的CoPrivacy方法在構(gòu)建匿名用戶組時，假設(shè)用戶彼此之間的協(xié)作是可信的，沒有考慮到用戶之間存在不可信的情況。本文提出的基于四叉樹結(jié)構(gòu)的增量近鄰查詢方法是研究目標用戶如何根據(jù)自身的隱私需求構(gòu)造匿名區(qū)域，在匿名區(qū)域中使用博弈論選取錨點進行查詢處理。

1 位置隱私保護方法

1.1 構(gòu)建匿名區(qū)域

SpaceTwist方法采用分布式結(jié)構(gòu)，在目標用戶附近隨意選取一個點作為代理查詢點進行查詢請求。由于不確定目標用戶所在區(qū)域的節(jié)點密度，攻擊者容易攻擊節(jié)點稀疏的用戶。目標用戶在請求位置服務(wù)時，需構(gòu)造合理的匿名區(qū)域進行查詢處理。匿名區(qū)域不能隨機選取，若匿名區(qū)域過大，則代理用戶與位置服務(wù)器的通訊開銷會不可控。因此，目標用戶在進行查詢請求前，需構(gòu)造合理的匿名區(qū)域。

本文采用四叉樹結(jié)構(gòu)將目標用戶所在的區(qū)域以十字遞歸形式不斷分割成4個大小相等的正方形區(qū)域，四叉樹的每個節(jié)點最多有4個子節(jié)點，每個節(jié)點代表一個正方形區(qū)域。K-匿名機制是將目標用戶泛化一個區(qū)域，該區(qū)域包含k-1個不同但相關(guān)的用戶節(jié)點，從而使第三方無法在區(qū)域中辨別目標用戶。為了防止最近鄰攻擊，目標用戶在進行查詢請求時，所發(fā)送的位置信息不是當前的坐標位置，而是當前所在的匿名區(qū)域，其匿名區(qū)域必須滿足k-匿名機制，第三方要識別目標用戶的位置信息的概率為1/k。如圖1所示。

圖1 四叉樹結(jié)構(gòu)

目標用戶在構(gòu)造匿名區(qū)域時要確認區(qū)域內(nèi)的用戶節(jié)點是否大于或等于k，若該區(qū)域的用戶節(jié)點數(shù)大于或等于k，則該區(qū)域為目標用戶構(gòu)造的匿名區(qū)域。構(gòu)造匿名區(qū)域的算法如算法1所示。

算法1：

輸入：四叉樹根節(jié)點pnode，目標用戶的坐標l，隱私需求K

輸出：匿名區(qū)域節(jié)點snode

Su=0；//初始化匿名區(qū)域的用戶節(jié)點Su

if node leafnode==false

//判斷當前節(jié)點是否為葉子節(jié)點

Num.push(pnode) //將當前節(jié)點進棧

for i=4 downto 1 do //判斷目標用戶所在的節(jié)點

if pnode.children[i]!=0 //查找用戶所在的節(jié)點

算法1進行遞歸判斷

endif

endfor

else while Su

snode=pushnode() //出棧

endwhile

endif

return snode

2 基于四叉樹結(jié)構(gòu)的增量近鄰查詢方法

在分布式結(jié)構(gòu)中，k匿名的位置隱私方法是在匿名區(qū)域內(nèi)選取一個節(jié)點作為一個代理查詢點，使得第三方無法在k個匿名區(qū)域中識別目標用戶。SpaceTwist方法進行查詢處理時，其查詢結(jié)果總是以錨點為中心不均勻分布，降低位置查詢的查全率。本文采用博弈論計算錨點,提高攻擊者推測目標用戶坐標信息的難度。在查詢處理過程中，目標用戶首先通過四叉樹結(jié)構(gòu)構(gòu)建匿名區(qū)域，采用博弈論計算錨點0U ，以0U 為中心向位置服務(wù)器發(fā)起增量近鄰查詢請求，位置服務(wù)器逐步增量返回興趣點候選集。

算法2 查詢處理算法

輸入：目標用戶1U ，興趣點集為C，錨點為0U ，單次返回興趣點個數(shù)β，位置查詢內(nèi)容為CS；

輸出：興趣點候選集V

dist(ip,1U )//興趣點與用戶位置之間的距離

3 性能分析

（1）隱私保護度分析：采用四叉樹結(jié)構(gòu)構(gòu)建匿名區(qū)域，其匿名區(qū)域滿足k-匿名機制，增加用戶的隱私保護度。攻擊者若想攻擊目標用戶，必須在匿名區(qū)域的k個用戶中識別目標用戶，從而攻擊者很難獲取用戶信息，增加了隱私保護度。之后，利用博弈論計算錨點，確保目標用戶節(jié)點信息和錨點信息不同但相關(guān)，保護匿名區(qū)域內(nèi)各個用戶節(jié)點的隱私，確保信息的傳輸安全。

（2）服務(wù)質(zhì)量分析：本文的服務(wù)質(zhì)量分析主要從查詢效率和查詢精確度進行分析。從查詢效率來看，分布式結(jié)構(gòu)為基于四叉樹結(jié)構(gòu)的增量近鄰查詢方法提供負載均衡的保障，解決集中式結(jié)構(gòu)系統(tǒng)性能的瓶頸。 近鄰查詢方法考慮到興趣檢索點在錨點的反方向分布不均的問題，以博弈論計算錨點并進行增量近鄰查詢方法，可以獲取錨點反方向的興趣點。顯然在這種情況下，位置服務(wù)質(zhì)量比其他算法明顯要高。

表1 展示各種方法的性能比較

從表1中可以看出，本文方法綜合性能較好：（1）匿名成功率：本文方法在查詢預處理中，通過四叉樹結(jié)構(gòu)構(gòu)建匿名區(qū)域，使用博弈論計算錨點，確保目標用戶和錨點在匿名區(qū)域中。而SpaceTwist不需要考慮匿名區(qū)域，直接選取匿名用戶組進行查詢處理；經(jīng)典K-匿名方法使用可信第三方，沒有考慮到用戶節(jié)點密度過大或過小問題。（2）查準率：經(jīng)典K-匿名方法在進行查詢處理過程中，只要找到一個近鄰的興趣節(jié)點就結(jié)束檢索。SpaceTwist方法在查詢過程中，沒有考慮到興趣節(jié)點在錨點的反方向分布。本方法是在經(jīng)典K-匿名方法和SpaceTwist方法的基礎(chǔ)上，進行增量近鄰查詢，在考慮錨點反方向的同時返回k個近鄰檢索的興趣節(jié)點。

4 總結(jié)

本文采用分布式結(jié)構(gòu)解決可信第三方的性能瓶頸和集中攻擊的問題，通過四叉樹結(jié)構(gòu)構(gòu)造匿名區(qū)域，用博弈論計算錨點，平衡服務(wù)質(zhì)量和位置隱私，利用增量近鄰查詢方法提高查詢準確度。