基于四叉樹結構的增量近鄰查詢方法

莊禮金

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

0 引言

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

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

1 位置隱私保護方法

1.1 構建匿名區域

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

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

圖1 四叉樹結構

目標用戶在構造匿名區域時要確認區域內的用戶節點是否大于或等于k，若該區域的用戶節點數大于或等于k，則該區域為目標用戶構造的匿名區域。構造匿名區域的算法如算法1所示。

算法1：

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

輸出：匿名區域節點snode

Su=0；//初始化匿名區域的用戶節點Su

if node leafnode==false

//判斷當前節點是否為葉子節點

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

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

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

算法1進行遞歸判斷

endif

endfor

else while Su

snode=pushnode() //出棧

endwhile

endif

return snode

2 基于四叉樹結構的增量近鄰查詢方法

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

算法2 查詢處理算法

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

輸出：興趣點候選集V

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

3 性能分析

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

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

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

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

4 總結

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