一種基于匿名區域變換的位置隱私保護方法

肖燕芳，徐紅云

(華南理工大學計算機科學與工程學院，廣州 510006)

1 概述

位置探查設備的快速發展開拓了一個新的研究領域——基于位置的服務。目前，基于位置的服務中的隱私保護是研究的熱點問題，移動互聯網提供基于位置的服務，如查詢基于當前位置的感興趣的點，此類服務都是基于k近鄰(k Nearest Neighbors, kNN)查詢[1-2]，即查詢距離用戶位置最近的 k個可能目標。用戶在獲取此類基于位置的服務時，總是希望自己的位置不被暴露，即位置隱私得到保護。實際上，享受服務與隱私保護是一對矛盾：高效的服務需要提供精確的位置；好的隱私保護策略需要使用戶的位置信息盡量模糊化。近年來，許多研究者致力于在高效的位置服務和位置隱私保護之間尋求一個平衡點，即在最少暴露用戶位置的前提下，獲得最好的位置服務，讓暴露的位置處于可控的狀態[3]。

針對位置隱私保護問題，國內外提出了很多解決方案，如匿名[4]、假名[5]、假地址[6]、路徑混淆[7]、k-匿名[8-9]等，這些方案大體可以劃分為空間區域混淆和假位置 2種技術。其中，k-匿名[8-9]和路徑混淆[7]都是空間區域混淆技術，采用該技術實現位置匿名主要存在以下問題：

(1)利用率低

在k-匿名查詢中，用戶選取服務器返回的k個查詢結果中的一個，利用率為 1/k，用戶需要的隱私度越高，利用率越低；在 kNN查詢中，服務器需要返回混淆區域中每個節點的k個最近鄰查詢結果，服務器處理開銷和通信開銷將增加 k倍，利用率進一步降低。

(2)查詢處理開銷和通信開銷大

用戶發送給服務器的k個節點進行查詢請求，服務器將k個節點的查詢結果返回給用戶，用戶從眾多的結果集中查找到自己所需要的結果，此過程造成過多不必要的查詢處理開銷和通信開銷。

利用假位置技術，用戶不發送自己的準確位置，而是基于一個假位置來獲取基于位置的服務，從而保護用戶的位置隱私。這類位置隱私保護方法的主要缺點是通信開銷大。如典型的使用假位置技術的SpaceTwist[6]，采用TCP包的數目來衡量通信開銷，查詢服務過程為每次返回一定大小(設定為 β bit)的TCP包，其中包含 m個目標節點的信息，當返回的TCP包里包含滿足用戶查詢請求的目標節點時，算法終止。假設滿足算法終止的第 n個 TCP包里的第1個節點是滿足算法終止的目標節點，則包中其余m－1個節點是無用信息，增加了不必要的開銷，隨著β的增大，通信開銷將增加。

針對這些問題，本文提出一種基于匿名區域變換的位置隱私保護方法，通過采用匿名區域變換方法實現位置匿名，在實現位置隱私保護的同時，降低通信開銷和查詢處理開銷，提高查詢效率。

2 位置隱私模型

本文基于中心服務器結構的位置隱私模型展開研究，該模型的結構如圖1所示。

圖1 位置隱私模型

模型主要包括3個部分：

(1)終端用戶，即使用便攜式設備進行 kNN范圍查詢的人，便攜式設備包括 PDA(Personal Digital Assistant)、筆記本、全球定位系統(Global Positioning System, GPS)、手機等，其特點是存儲能力和處理能力有限。

(2)位置匿名服務器，主要包括：1)位置匿名模塊，用于將位置信息進行匿名；2)數據存儲模塊，存儲的數據包括用戶查詢請求信息和服務器返回結果集；3)共享存儲模塊，用于實現位置匿名信息與服務器返回結果集的完全共享。

(3)位置訪問服務器，包括提供kNN查詢以及其他位置服務的 Internet服務提供商(Internet Service Provider, ISP)。

3 隱私攻擊模型

本文假定攻擊者具有如下特征：(1)攻擊者具有足夠大的存儲空間和強大的計算能力，能夠截獲位置匿名服務器發送到位置訪問服務器的相關信息，以及服務器返回給位置匿名服務器的查詢結果集。(2)攻擊者不能篡改數據包的內容，也不能毀壞位置匿名服務器，僅能監聽位置匿名服務器與位置訪問服務器間的通信數據。

4 匿名區域變換法

基于上述位置隱私模型和隱私攻擊模型，本文提出了一種基于匿名區域變換的位置隱私保護方法ART(Anonymous Region Transformation)。

4.1 預備知識

在移動位置服務中，用戶所在位置周圍的移動節點分布可以分為2種情況：(1)均勻分布，如圖2所示，用戶 A周圍 2個矩形區域內節點數大致相同；(2)非均勻分布，如圖3所示，用戶A周圍2個矩形區域內節點數相差較大。

圖2 節點均勻分布情況

圖3 節點非均勻分布情況

針對以上2種節點分布情況，位置匿名服務器采用匿名區域變換法生成匿名區域時，匿名區域中移動節點數目差別較大，本文主要研究均勻分布的情況。算法中所用到的參數定義如下：

定義1 用戶發出的查詢請求File表示為：

File=(L,Key,Range)

其中，L=(x, y)是用戶的位置信息，x表示位置的經度；y表示位置的緯度；Key是查詢關鍵字；Range是查詢范圍參數。

定義 2 位置匿名服務器向位置訪問服務器發出的匿名區域查詢請求File’表示為：

File’=(L’, Key, Range’)

其中，L’是經過匿名處理后的匿名區域；Key是用戶查詢的關鍵字；Range’是匿名區域內匿名節點的查找范圍。

4.2 位置匿名與鄰近節點處理

匿名區域變換即采用變換的方法，確定位置隱私用戶的匿名區域。圖4為匿名區域變換示意圖。

圖4 匿名區域變換示意圖

對于圖4，確定用戶q的匿名區域的方法如下：在平面直角坐標系下，用戶q的位置標示為A，將A所在位置設置為原點，在距離 A點任意方向(α∈[0°,360°])的 k米處任取一點 O，錨點 q’的位置標示為 O點所在位置，過點O作線段NF，使NF=2NO。以NF為邊，作正方形BCFN，該正方形即為用戶q的匿名區域。為了實現對查詢用戶q的位置匿名，經過以上的匿名區域變換后，對用戶的范圍查詢即可轉換成對匿名區域BCFN內移動節點的范圍查詢。例如，用戶提出“查找距離我R千米的加油站的位置”，其中，L是用戶的位置信息；Key是查詢關鍵字“加油站”；Range是查詢范圍參數“R千米”，位置匿名服務器選取距離用戶 k千米的 O點作為錨點，生成匿名區域BCFN，通過BCFN內移動節點“查詢距離我n千米的加油站的位置”實現，位置匿名服務器查詢請求File’中，L’是經過匿名處理后的匿名區域BCFN，Key為用戶范圍查找的關鍵字“加油站”，Range’是匿名區域中匿名節點的查找范圍“n千米”。位置訪問服務器處理查詢請求 File’(L’,Key, Range’)，并將查詢結果發送給位置匿名服務器，位置匿名服務器對結果集進行鄰近節點處理，精確提煉出用戶q的范圍查詢結果，返回給用戶q。

ART方法實現位置隱私查詢的步驟如下：

(1)定位用戶q的地理位置坐標，即點A的坐標。

(2)在距離 A點 dist(q, q’)處找一錨點 q’，即點 O的位置坐標，其中，dist(q, q’)表示用戶 q與錨點 q’的距離。

(3)以A為圓心、以AO為半徑作圓。

(4)根據給定的角度 α，作出與圓相交于點 O的線段。

(5)根據匿名需求，生成邊長為s的特定大小的匿名區域BCFN，區域BCFN內節點表示為 q1, q2,… ,qn。

(6)位置匿名服務器向位置訪問服務器分別發送節點 q1, q2,… ,qn的范圍查詢服務請求。

(7)位置訪問服務器向位置匿名服務器返回節點q1, q2,… ,qn的范圍查詢結果。

(8)位置匿名服務器檢索位置訪問服務器返回的查詢結果，從中選取恰當的查詢結果返回給用戶。

在4.2節方法中，匿名區域變換算法涉及到參數Range、dist(q, q’)、Range’，參數 Range、dist(q, q’)、Range’的選取分3種情況，當匿名區域內的移動節點正好位于q’時，3種情況分別如圖5～圖7所示，其中，Range、dist(q, q’)和 Range’分別表示為 AQ、AO、OP；匿名區域的邊長為s。

圖5 Range’

圖6 Range’=dist(q, q’)的情況

圖7 Range’=dist(q, q’)+Range 的情況

第 1種情況為 Range’

第 2種情況為 Range’=dist(q, q’)，即匿名區域內移動節點的查找范圍半徑OP等于用戶q與匿名區域內移動節點 q’的距離 AO，此時，匿名區域移動內節點查詢范圍恰好包含查詢用戶q的位置，返回的結果集包含大部分用戶查詢所需結果。

第 3 種情況為 Range’=dist(q, q’)+Range，即匿名區域內移動節點查找范圍半徑OP覆蓋查詢用戶q的查找范圍半徑 AQ，此情況下能夠很好地實現位置匿名，提供良好的服務質量。

綜上所述，Range’的有效選取范圍為：Range’∈{dist(q, q’),dist(q, q’)+Range}

其中，q表示用戶所在位置；q’表示匿名區域內移動節點的位置。

用戶進行服務請求的查詢范圍 Range由用戶定義，匿名區域內移動節點查詢范圍Range’由用戶與移動節點間的距離dist（ q,q′）和用戶實際查找范圍Range決定。位置匿名服務器執行匿名算法，選取錨點 q’，直觀地，當用戶 q距離錨點 q’近時，Range’的選取范圍小，此時查詢處理開銷較低，隱私保護力度也降低。q’的選取由用戶的匿名需求決定。

5 算法性能分析

本節從查準率、查詢開銷、匿名性3個方面來衡量本文算法的性能。其中，查準率用來衡量服務器的服務質量，采用用戶查詢結果所占實際用戶查詢結果的比例來表示；查詢開銷即用戶采用匿名區域變換算法所用時間開銷和通信開銷；匿名性用攻擊者所能推斷的用戶隱私區域大小來衡量。

5.1 查準率

定義 3 對任意Node∈CR(匿名區域)進行范圍查詢，假設Node1, Node2,… ,N oden進行范圍查詢返回的區域分別為C1, C2,… ,Cn，則位置訪問服務器返回的結果集為：

設C內目標集合為Objectc，則：

設點A所在位置的用戶q范圍查詢區域為CA，則CA內目標集合為：

采用本文的位置匿名方法處理后，服務器能夠提供的服務質量 Q可以用用戶范圍查詢結果集與經過位置匿名后的匿名節點查詢返回的結果集之比表示：

由式(1)可以看出，當所選匿名區域包含用戶的查詢請求區域時，用戶的查準率能夠達到 100%，但通信開銷增加；當所選匿名區域與用戶查詢區域相交時，通過位置匿名中間件的處理，通信開銷少，能夠實現良好的查準率。

5.2 查詢開銷

用戶請求服務開銷主要包括以下3個方面：

(1)位置匿名服務器根據用戶的隱私需求進行匿名處理時需要時間開銷，匿名處理時間與用戶的隱私要求和周圍節點密集度有關，當密集度高時，處理時間長，反之，處理時間短。

(2)位置訪問服務器響應匿名處理后的查詢請求需要時間開銷，將查詢結果返回給位置匿名服務器需要通信帶寬開銷。

(3)位置匿名服務器對查詢結果集進行優化處理，選擇與用戶鄰近匿名區域中的節點相對應的查詢結果，剔除掉遠離用戶的其他節點對應的查詢結果需要時間開銷。

假設匿名處理時間為ψ(q)，服務器處理時間為ω，通信時間開銷為 T，查詢結果優化時間為 ε，則總的查詢服務開銷Cost為：

通過查詢結果集的鄰近節點處理，返回給用戶的節點集只包含鄰近用戶的查詢結果，減少了位置匿名服務器與位置訪問服務器間的通信量、時間開銷T以及用戶檢索自己所需查詢結果的時間 ε，因此，減少了總的查詢開銷Cost，提高了查詢效率。

5.3 匿名性

因為攻擊者能截獲匿名處理后的查詢請求File’(L’, Key, Range’)以及位置訪問服務器返回給位置匿名服務器的查詢結果集，所以攻擊者能夠獲知位置匿名查詢范圍Range’和匿名區域大小s2。攻擊者將匿名區域內的節點進行范圍查詢所覆蓋區域作為用戶的可能位置，從而推斷出用戶所在的區域為：

攻擊者能夠推斷出用戶可能所在位置為距離匿名區域內節點 dist（ q, q′） 范圍內的節點位置，因此，攻擊者推斷出用戶所在的區域為：

由4.2節知，算法中Range’的有效取值范圍為：

因此，攻擊者推斷出用戶所在的區域范圍為：

定義隱私度T為區域Ψ內所有節點與真實查詢用戶q的平均距離。

位置匿名服務器根據用戶的隱私需求定義隱私度T，而攻擊者無從獲知。用戶進行服務請求的查詢范圍為Range2，攻擊者推斷出的用戶所在區域范圍由式(5)給出。

當隱私度 T值增大時，dist（ q, q′）增大，而攻擊者推斷用戶所在區域范圍增大，攻擊者推斷用戶真實位置的難度增加，從而能夠為用戶提供更好的位置隱私保護。

6 實驗評估

算法采用Java編程語言實現，實驗環境為2.2 GHz的 Intel雙核 CPU，1 GB內存。操作系統平臺是Microsoft Windows XP Professional。

6.1 參數設置和實驗結果分析

實驗數據采用 Thomas Brinkhoff的 Networkbased Generator of Moving Object[10]隨機生成的Oldenburg市的空間數據集，分別研究節點密集度和錨點距離 dist（ q, q′）對匿名區域變換算法ART性能的影響，針對不同參數，比較ART與Cloaking Region 算法和 SpaceTwist算法在通信開銷和匿名性方面的優劣。其中，節點數 N 分別取 1 000、2 000、3 000、4 000、5 000、6 000、7 000、8 000、9 000、10 000、80 000、120 000、160 000，用戶離錨點距離 dist(q, q’)分別取50 m、100 m、150 m、200 m、250 m、300 m。

圖8給出匿名區域內用戶數目N及用戶離錨點的距離 dist（ q, q′） 對查準率的影響。從中可以看出，隨著區域內用戶數目的增加，查準率提高，誤差減小。隨著 dist（ q, q′） 值的增大，誤差率增加，查準率降低。這是因為區域內用戶數目增加，節點密集度增加，采用匿名區域變換算法的匿名區域內節點數目增加，所以發送到位置訪問服務器端進行查詢服務請求的節點數目 q1, q2,… ,qn中的n值增加，供位置匿名服務器進行鄰近節點處理的節點返回值接近用戶的實際查詢結果。當 dist（ q, q′） 值小時，距離用戶越近的節點的查詢結果越接近用戶所需要的查詢結果，所以，隨著 dist（ q, q′）的減小，距離用戶越近的節點的結果越精確，誤差率降低，查準率增加。系。當 dist（ q, q′） 一定時，隨著用戶數目的增加，請求服務的通信開銷增加，但當節點密集度繼續增大時，通信開銷增加很少。由4.2節可知，這是因為服務器需要處理的匿名區域內節點數目增加到一定程度時，將獲得匿名區域內任意位置上的范圍查詢結果，即使再增加查詢，也不能產生新的查詢結果，從而使通信開銷增加得很少。

圖8 匿名區域內節點數目及dist(q, q’)對查準率的影響

圖9顯示了用戶數目與通信時間開銷之間的關

圖9 節點數目與通信時間開銷之間的關系

6.2 與CR算法的比較

表1給出采用ART算法和CR(Cloaking Region)算法時 dist（ q, q′） 對查準率的影響。實驗結果表明，ART的查準率與 dist（ q, q′） 密切相關，而 dist（ q, q′） 對CR算法的影響較小，不論 dist（ q, q′） 取值多少，CR算法的查準率趨近1。ART算法與CR算法相比，查準率略低。在表2中，CR算法和ART算法均采用匿名區域方法，受節點密集度的影響，當節點分布密集時，匿名區域內節點數目增多，所需查詢請求節點數增加，兩者通信開銷增加。受節點分布影響，當q周圍節點密集度大于q’周圍節點密集度時，CR算法的時間開銷大于ART 算法，反之，CR算法時間開銷小于ART算法。實驗結果顯示，ART算法通信開銷略小于CR算法，這是因為ART算法采用了鄰近節點處理的方法，減少了總的通信時間開銷。

表1 不同 dist(q, q’)下2種算法的查準率

表2 不同節點數目下2種算法的通信時間開銷 s

6.3 與SpaceTwist算法的比較

圖10顯示了 dist（ q, q′）=200 m時，ART算法和SpaceTwist算法的通信開銷比較結果。結果顯示，在特定空間節點數目下，ART算法的通信時間開銷略優于SpaceTwist算法。

圖10 dist(q, q’)一定時2種算法通信時間開銷對比

圖11是節點數為160 000時 dist（ q, q′）對 2種算法通信時間開銷的影響，實驗結果表明，d ist（ q, q′） 值的改變幾乎不會影響通信時間開銷。

圖11 不同dist(q, q’)下2種算法通信時間開銷比較

圖12顯示了當 dist（ q, q′）改變時，SpaceTwist算法的查準率優于ART算法。這是因為SpaceTwist采用客戶-服務器體系結構，不斷向位置訪問服務器請求最近POI (Point of Interest)，直到出現滿足用戶的請求結果，算法結束，此算法處理過程雖能夠實現良好的查準率，但不斷地向服務器發送請求導致通信開銷太大。由4.1節可知，當式(1)中匿名區域內節點查詢的目標集合 ObjectC包含用戶q范圍查詢的結果區域CA中的目標時，ART算法也能達到較高查準率。

圖12 ART與SpaceTwist的查準率比較

7 結束語

以往的位置隱私保護方法普遍采用包含用戶位置的匿名區域代替用戶真實位置進行查詢處理，造成位置隱私度不高和通信開銷大。本文提出一種用戶真實位置不包含在匿名區域中的方法實現位置隱私保護，在離用戶一定距離處選一錨點生成匿名區域，由匿名區域內移動用戶發起到服務器的服務請求，經過位置匿名服務器對返回結果集進行鄰近節點處理，提高了位置隱私度，降低了通信開銷，優化了查詢結果。由于用戶的真實位置不包含在匿名區域內，因此提高了用戶的抗攻擊能力。理論分析和實驗結果表明，匿名區域變換方法能夠保證在較低的通信開銷下提供較好的位置隱私保護。但本文方法只適用于用戶周圍節點分布均勻的情況，之后將對用戶周圍節點分布不均勻的情況展開研究。

[1]Roussopoulos N, Kelley S, Vincent F.Nearest Neighbor Queries[C]//Proceedings of ACM SIGMOD International Conference on Management of Data.[S.l.]: ACM Press,1995: 71-79.

[2]Hjaltason G R, Samet H.Distance Browsing in Spatial Databases[J].ACM Transactions on Database Systems,1999, 24(2): 265-318.

[3]潘 曉, 肖 珍, 孟小峰.位置隱私研究綜述[J].計算機科學與探索, 2007, 1(3): 268-281.

[4]Shankar P, Ganapathy V, Iftode L.Privately Querying Location Based Services with SybilQuery[C]//Proceedings of the 11th ACM International Conference on Ubiquitous Computing.Orlando, USA: ACM Press, 2009.

[5]Cornelius C, Kapadia A, Kotz D, et al.AnonySense:Privacy Aware People Centric Sensing[EB/OL].[2011-05-23].http://www.cs.indiana.edu/～kapadia/papers/anonysense_mobisys08.pdf.

[6]Yiu Man-Lung, Jensen C S, Huang Xuegang, et al.SpaceTwist: Managing the Trade-offs Among Location Privacy, Query Performance, and Query Accuracy in Mobile Services[C]//Proceedings of the 24th International Conference on Data Engineering.[S.l.]: IEEE Press, 2008:366-375.

[7]Meyerowitz J, Choudhury R R.Hiding Stars with Fireworks: Location Privacy Through Camouflage[C]//Proceedings of ACM Special Interest Group on Mobility of Systems, Users, Data and Computing.Beijing, China:[s.n.], 2009: 345-356.

[8]Gruteser M, Grunwald D.Anonymous Usage of Locationbased Services Through Spatial and Temporal Cloaking[C]//Proceedings of the International Conference on Mobile Systems, Applications, and Services.New York,USA: ACM Press, 2003: 163-168.

[9]Samarati P, Sweeney L.Protecting Privacy When Disclosing Information: k-anonymity and Its Enforcement Through Generalization and Suppression[R]. SRI Computer Science Laboratory, Tech.Rep.: SRI-CLS-98-04, 1998.

[10]Brink H T.A Framework for Generating Network Based Moving Objects[J].GeoInformatica, 2002, 6(2): 153-180.