一種基于LBS 的用戶錨點區域混淆隱私保護方案

王智明

(莆田學院 信息工程學院，福建 莆田351100)

隨著21 世紀空間定位技術，尤其是GPS 和基站定位技術的飛速發展，給人們的生活方式帶來了深刻的影響，通過便攜設備可以輕易地獲得關于個人位置的各種服務。面對巨大商機，各大廠商和電信移動公司更是不甘落后，從傳統的電信、移動公司，到國內外IT 業界巨頭如騰訊、Google、Facebook 等紛紛推出各種基于位置的服務LBS。典型的LBS 應用如尋找周圍街區顧客口碑好的咖啡店、從當前地點到某旅游點的最佳路線、給商戶周邊500 m 內的用戶發送打折信息等［1］。

在體驗LBS 服務帶來巨大便利的同時，用戶個人隱私的泄露成為越來越嚴重的社會問題，泄露的主要途徑有:(1)用戶發往服務器的LBS 查詢中途被截取;(2)服務器被攻破，黑客獲取用戶的LBS 查詢;(3)不良的中間服務提供商或個人將用戶信息出售獲利。利用這些被泄露的信息，就可獲知用戶活動規律，推斷用戶個人興趣、活動習慣、宗教信仰、疾病就診歷史等這些用戶本不愿公開的隱私［2］。隨著LBS 服務的深入發展，位置隱私保護問題日益引起人們的重視，學術界提出來不少關于個人位置隱私的保護方法，除了部分是對用戶標識符、查詢內容本身的保護［3］，大部分還是側重于對用戶位置信息的保護。

1998 年，P.Samarati 和L.Sweeney 為了阻止連接攻擊，提出k-匿名隱私保護模型［4］，規定匿名區域必須至少有k 個用戶，而攻擊者不能從這k 個用戶中識別出真正的用戶。而后Gruteser 等［5］將k-匿名技術引入到LBS 隱私保護中，通過對用戶的真實位置進行概化處理，模糊用戶的空間位置，達到隱私保護的目的。在Gruteser 之后，為減小匿名區域，提高查詢服務質量，先后有學者提出一些新的匿名方 案:如 New Casper［6］，NNC(Nearest Neighbor Cloak)［7］，HC(Hilbert Cloak)［7］，ANNC(Adaptive Nearest Neighborhood Cloaking)［8］等等。這些方案都采用了中心服務器的系統結構，即匿名區域的構建任務交由可信的第三方匿名服務器來完成。

除了以上基于k-匿名技術的隱私保護模型，在LBS 查詢服務中，還有一些隱私保護是采用假位置［9］，即移動用戶通過假位置，向服務器發起查詢請求，這樣即便查詢相關數據被攻擊者截獲，也無法獲知真實的用戶位置。如文獻［9］提出的基于LBS 的隱私區域感知虛擬生成算法，通過選取一些基于虛擬圓或網格方法的候選用戶，并將這些候選用戶位置模糊處理，形成基于熵隱私度量的虛擬位置。文獻［10］提出的逆向增量近鄰查詢算法，通過設定取代真實位置的錨點，逐步獲取興趣點候選集并計算出查詢結果，增加匿名隱私效果的同時提高了查詢結果的準確性。又如SpaceTwist［11］算法也是基于假位置的算法，用戶隨機選取附近的某個點作為錨點［7，10］，通過此錨點向LBS 服務器發出增量近鄰查詢［11］。以用戶真實位置U 為圓心，已發現的第k個近鄰為半徑畫圓，形成的區域稱為需求空間;類似的以錨點U' 為圓心畫圓［10］，將LBS 服務器返回的近鄰結果統統包含其中，此區域稱作供應空間。算法開始時，初始化供應空間為空集，需求空間為整個空間，隨著算法進行，供應空間不斷擴大，需求空間不斷縮減，直到需求空間完全覆蓋供應空間時SpaceTwist 算法結束。

文中分別選取基于k-匿名和假位置的位置隱私保護的典型算法NNC(Nearest Neighbor Cloak)、SpaceTwist 進行分析:

1)基于k-匿名的NNC 算法，其本質是一種以服務質量換取隱私保護的技術。此算法有兩個不足:(1)用戶最終獲得的并非精確的查詢結果，而是一個模糊的值;(2)把用戶所在的具體位置一個點，使用一個區域來替換，會導致候選結果集大量增加，從而帶來更大的系統計算和通信量。

2)基于假位置技術的SpaceTwist 算法，雖然沒有k-匿名那么高的計算量和通信量，但由于缺少用戶間的協作［10］，沒能實現k-匿名，故隱私保護功能較差。通過用戶查詢請求的分析，攻擊者就能將用戶鎖定于在某個區域范圍，而此時若該區域只有一個查詢用戶，攻擊者就很容易鑒別出用戶。此外SpaceTwist 算法中，每次查詢服務會返回一個包含k個目標節點信息的TCP 包，當算法結束時此TCP 包中，僅有1 個目標節點信息是有效的，其余k － 1 個節點構成了數據冗余，增加了系統的開銷［9］。

基于上述存在的問題，文中提出了一種基于LBS 的用戶錨點區域混淆隱私保護方案即ARCS(Anchor Region Confusing Scheme)，首先選取用戶錨點，并利用錨點構建的區域進行位置混淆，提高了抗攻擊能力，同時ARCS 也降低通信開銷和查詢時間開銷，提高了查詢效率。

1 面向位置服務的匿名隱私保護方案模型

文中ARCS 方案基于以下假定:(1)攻擊者只能監聽位置匿名服務器與LBS 服務器之間的數據包內容，攻擊者不能篡改或破壞數據;(2)查詢用戶所在位置周圍的移動節點是均勻分布的，用戶位置空間分布的越均勻空間信息熵就越大，相應地用戶能得到更好的隱私保護［10］。

1.1 ARCS 方案模型

文中ARCS 方案基于服務器結構如圖1 所示，它是由移動用戶、位置匿名服務器、LBS 服務器3 部分構成。

圖1 ARCS 方案服務器結構Fig.1 ARCS scheme server structure

1.1.1 移動用戶 指使用便攜設備(如PDA、手機、全球定位系統GPS 等)發出有關位置查詢請求的用戶，便攜設備特點是體積小便于隨身攜帶，但數據存儲與處理能力較弱。

1.1.2 位置匿名服務器 該服務器主要功能包括實現位置的匿名處理，將用戶準確的位置信息處理成為一片匿名的區域(當前能夠處理的匿名區域一般是矩形或圓形);存儲用戶高頻率的查詢請求以及相對應的候選結果集［11］;對用戶的查詢進行匹配處理，共享候選結果集，以提高系統效率。

1.1.3 位置訪問LBS 服務器 作為ISP (Internet Service Provider)為終端用戶提供k 近鄰查詢和其他相關位置的服務。

ARCS 方案模型具體工作流程:移動用戶將查詢內容與隱私要求，通過文件的形式發送到位置匿名服務器，位置匿名服務器首先在查詢日志表中查詢是否存在該用戶、是否有符合該用戶的候選結果集，若有的話將該結果直接共享給用戶，提高查詢系統效率;若沒有則退而查找是否有符合該用戶的匿名區域，有的話就共享該匿名區域。如果匹配的匿名區域也不存在，通過ARCS 方案算法產生新的匿名區域，完整走一遍ARCS 方案算法，直到得到用戶所需查詢結果(見圖1)。

1.2 ARCS 方案的位置匿名與鄰近節點處理過程

ARCS 方案模型如圖2 所示。實現位置隱私查詢的具體步驟:

1)以用戶U 的實際地理位置為坐標中心。由給定的角度θ(相對于x 坐標)按照用戶隱私要求確定錨點 U'，用戶 U 與錨點 U' 之間距離記作dist(U，U')。

2)在用戶U 與錨點U'的延長線上取點O，其中OU'長度為r，以O 為圓心做半徑為r 的圓形匿名區域(半徑r 的大小作為參數，根據匿名程度和節點密度情況設置)。

3)位置匿名服務器分別將圓形匿名區域內的節點q1，q2，… qn的范圍查詢請求，發送到LBS 服務器，LBS 服務器將處理產生的候選結果集，返回給位置匿名服務器。

4)位置匿名服務器對步驟3)中得到的結果集進一步篩選，并將最終結果集交給用戶U，完成ARCS 算法。

圖2 ARCS 方案模型Fig.2 ARCS scheme model

下面討論在ARCS 方案算法中匿名區域內的節點查找范圍U'K 的相關取值情況。

如圖3 所示，U 是查詢用戶U 所在點，UM 是用戶查詢范圍參數，大小由查詢用戶給出，當U'K ＜dist(U，U')時，即匿名區域內的節點查找半徑小于用戶U 與匿名區域內錨點U'的距離，LBS 服務器處理得到的結果集，只包含小部分用戶U 查詢需求范圍，大部分查詢結果都被遺漏，故無法得到滿意的查詢結果［12］。

圖3 U'K ＜dist(U，U')情況Fig.3 U'K ＜dist(U，U')case

如圖4 所示，當U'K = dist(U，U')時，匿名區域內的節點查找半徑等于用戶U 與匿名區域內錨點U' 的距離，匿名區域內的節點查詢范圍U'K，正好覆蓋查詢用戶U 所在的位置，即U 與K 兩點重合，此時LBS 服務器處理得到的結果集能包含較多用戶U 所需要的結果，故查詢結果基本能令用戶滿意。

圖4 U'K = dist(U，U')情況Fig.4 U'K = dist(U，U')case

如圖5 所示，當U'K = dist(U，U')+ UK，這時用戶U 的查找半徑加上用戶U 與錨點U'間的距離，正好等于匿名區域內的節點查找半徑，U'K 正好覆蓋了用戶U 的查找半徑UK，LBS 服務器處理得到的結果集能包含用戶U 所需要的全部結果，此時用戶能得到滿意的查詢結果。

圖5 U'K = dist(U，U')+ UK 情況Fig.5 U'K = dist(U，U')+ UK case

綜合以上3 種情況，在ARCS 方案算法中，為了讓用戶得到較理想的查詢結果，規定U'K 的取值范圍定在dist(U，U')與dist(U，U')+ UK 之間，記作

公式(1)中，用戶U 的查找半徑UK 由用戶提出，在UK 值一定時，當dist(U，U')越小，匿名區域節點的查詢范圍U'K 就越小，相應LBS 服務器需要的查詢處理開銷也就越少。但dist(U，U')的減小會造成隱私保護有效性降低，因此，需要根據用戶的匿名要求，平衡系統查詢開銷與隱私保護的有效性，選取合理的錨點U'。

2 ARCS 方案性能分析

關于ARCS 方案的性能，主要從查詢結果誤差率、查詢時間開銷和匿名性3 個方面來衡量。

2.1 查詢誤差率

查詢誤差率是衡量LBS 服務器查詢處理的一個有效指標，誤差率W 可以表示為用戶查詢漏選目標在用戶查詢范圍內目標集中所占的比例。

設任意匿名區域內有移動節點p1，p2，p3，…，pn，各節點進行范圍查詢處理所對應的區域分別記做C1，C2，C3，…，Cn，則LBS 服務器返回的結果集記作Pc= {p| ?p ∈C}，其中C = C1∪C2∪C3…∪Cn，即C =;設用戶U 查詢的范圍區域為CU，則該區域內目標集用PU表示，記作PU= {p | ?p ∈CU}，則LBS 服務器查詢處理的誤差率W 可以記作

由式(2)可以看出，當PU∩PC的結果集變少，查詢誤差率變大，系統開銷變小。理論上當匿名區域各節點返回的查詢結果集Pc能覆蓋用戶U 的查詢范圍區域結果集PU時，用戶的查詢誤差率能夠達到0%，即完全無誤差狀態。當然要達到該狀態，需消耗較大的系統開銷。

2.2 查詢時間開銷

查詢時間開銷主要包含匿名處理、篩選結果集、產生候選集、數據通信方面的開銷。

1)匿名處理時間開銷:用戶提交查詢要求后，位置匿名服務器進行匿名處理所耗費時間的，記為Tanony(p，q)。Tanony(p，q)值的大小，取決于用戶隱私程度的要求p 和匿名區節點密度q 的情況，隱私要求程度p 越高，節點密度q 越高，匿名處理時間開銷Tanony (p，q)就越大。

2)篩選結果集:位置匿名服務器需要對LBS 服務器返回的查詢結果集篩選處理，去除那些與用戶相距較遠的匿名區域節點，篩查出與用戶U 鄰近的節點，整個篩選過程的時間開銷記為Tfilter。

3)產生候選集:LBS 服務器對匿名區域節點的查詢處理生成候選結果集需要耗費時間，記為Tcandi。

4)數據通信:包括位置匿名服務器將匿名區域傳遞給LBS 服務器，LBS 將候選查詢結果集傳輸給位置匿名服務器需要消耗的時間，以及用戶U 與位置匿名服務器間通信，總耗費時間記為Tcomm。綜上幾個主要因素，查詢總時間開銷可記為

從公式(3)看出，LBS 服務器通過用戶錨點U'的合理選取，位置匿名服務器候選結果集進行篩選處理減少結果集，優化了系統通信流量，也縮短了查詢處理的時間。另外，對于頻率高的查詢服務，位置匿名服務器將其保存于共享數據庫中，便于有類似查詢需求的用戶共享，進一步減少了查詢時間開銷Tcost。

2.3 匿名性

攻擊者通過截取匿名服務器與LBS 服務器間的數據通信，可以推斷出用戶所在區域范圍:(r +dist(U，U'))2。由公式(1)

進一步可得

故攻擊者可推斷出用戶所在區域范圍:

根據隱私保護的需要，只要增加錨點的距離即dist(U，U')，由公式(1)可知匿名區域節點的查詢范圍U'K 相應增大，攻擊者推斷出用戶所在區域范圍{(r + U'K － UK)2，(r + U'K)2}也成平方級增加，大大降低了用戶位置暴露的風險。

3 實驗結果與分析

3.1 實驗環境

實驗運行環境為Intel Core2 Duo，2.13GHZ，2G RAM，Windows XP 的PC 機，算法采用Java 語言。實驗中所有的移動對象是由基于網絡的移動對象生成器產生(Network-based Generator of Moving Objects)，生成器的輸入端為德國城市古登堡Oldenburg 的交通路網，區域面積:23.572 km*26.915 km。

分別研究節點密集度、用戶與錨點距離dist(U，U')不同取值情況下，ARCS、NNC 和SpaceTwist 算法在查詢誤差率、查詢時間開銷和匿名性方面的表現。實驗所用參數:節點密集度通過Oldenburg 市節點個數來衡量，參數取值(1 000，2 000，4 000，6 000，8 000，10 000，20 000，40 000，60 000，80 000，100 000，120 000)、用戶與錨點距離dist(U，U')以米為單位，參數取值(50，100，150，200，250，300)。

3.2 查詢誤差的比較

圖6 是用戶與錨點距離dist(U，U')取值不同情況下，3 種算法在查詢準確率上的表現。從圖6 可以看到，NNC 算法對于dist(U，U')不敏感，隨著dist(U，U')取值50 ～500 的變化，該算法的查詢準確率始終趨近1，也就是查詢誤差率保持為0;而SpaceTwist 算法(其算法查詢過程見圖7)和ARCS算法的查詢準確率與dist(U，U')參數相關性較大，隨著dist(U，U')的值增加，兩算法查詢準確率都出現一定程度下降，查詢誤差率越來越大。

圖6 不同dist(U，U')取值下3 種算法查詢準確率對照Fig.6 Comparison results of the query accuracy of the three algorithms using the different dist(U，U')

圖7 SpaceTwist 算法查詢過程Fig.7 SpaceTwist algorithm query process

dist(U，U')取值50 ～150 時，ARCS 算法查詢誤差率略小于SpaceTwist 算法，而當dist(U，U')取值200 ～300 時，SpaceTwist 算法查詢誤差率略小。這是因為SpaceTwist 算法需要不斷向LBS 服務器請求最近的興趣點POI，直到用戶得到滿意結果為止，雖然這樣能達到較低的誤差率，但不斷向服務器發送請求也導致了通信開銷的加大。而由公式(2)知，當匿名區域各節點返回的查詢區域集PC覆蓋用戶U 的查詢范圍區域PU時，ARCS 算法能達到100%的查詢準確率，即實現零查詢誤差率。

3.3 查詢時間開銷比較

實驗結果如圖8 所示。NNC 和ARCS 2 種算法的查詢時間開銷都受到匿名區間節點密度的影響，隨著匿名區間節點數變大，兩種算法的系統消耗時間均明顯增加。NNC 算法和ARCS 算法在不同節點數測試中，沒有哪個算法在查詢時間開銷上明顯占優勢，當用戶U 周邊的節點密度大于錨點U'，即P(U)＞P(U')時，ARCS 算法通信消耗時間稍優于NNC 算法;而當P(U)＜P(U')時，NNC 算法則稍占優于ARCS 算法。綜合來看，在實驗的6 種節點數情況下，NNC 算法平均耗時1.898 s，ARCS 算法平均耗時1.847 s，ARCS 算法時間開銷稍好于NNC 算法。這主要是由于ARCS 算法中位置匿名服務器對查詢結果集進行優化處理，剔除了遠離用戶的那些節點，很大程度上減小了服務器間的通信量。

如圖9 實驗結果所示，SpaceTwist 算法的通信時間開銷同樣受到匿名區間節點的密度影響明顯，隨著匿名區間節點數變大，兩種算法的系統通信消耗時間都明顯增加，但ARCS 算法相比SpaceTwist算法，在查詢時間消耗上有一定的優勢。這主要是因為SpaceTwist 算法需要不斷地向LBS 服務器發出請求，獲取最近的興趣點POI，因而增加了通信量開銷。

圖8 不同節點數下NNC 和ARCS 算法的時間開銷比較Fig.8 Time cost comparison of the ARCS and NNC algorithms for different nodes

4 結 語

圖9 不同節點數下SpaceTwist 和ARCS 算法時間開銷比較Fig.9 Time cost comparison of the ARCS and SpaceTwist algorithms for different nodes

隨著人們對基于位置的服務質量要求越來越高，個人位置隱私日益受到重視。在對當前位置隱私保護技術進行較全面了解的基礎上，通過對NNC、SpaceTwist 兩種算法的分析和改進，文中提出了一種面向位置服務的匿名隱私保護方案ARCS，并通過了理論分析和實驗驗證。該方案選取與用戶有一定距離的假地址來產生匿名區域，隱藏了用戶的真實位置，提高了算法的安全性。另外，通過候選結果集篩選處理和查詢結果共享，提高了系統整體查詢效率。

［1］Wemke Mariiis，Durr Frank，Rothennel Kurt. PShare:position sharing for location privacybased on multi-secret sharing［C］//Proceedings of the 10th IEEE International Conference on Pervasive Computing and Communications. Lugano，Switzerland:Computer Society，2012.

［2］Talukder N，Ahamed S I. Preventing multi-query attack in location-based services［C］//Proceedings of the Third ACM Conference on Wireless Network Security (WiSec).New York:2010:25-26.

［3］Samarati P.Protecting respondents identities in microdata release［J］. IEEE Transactions on Knowledge and Data Engineering，2001，13(6):1010-1027.

［4］Samarati P，Sweeney L.Generalizing data to provide anonymity when disclosing information(abstract)［C］//Proceedings of the 17th ACM SIGACT-SIGMODSIGART Symposium on Principles of Database Systems.New York:ACM Press，1998.

［5］Gruteser M，Grunwald D.Anonymous usage of location-based services through spatial and temporal cloaking［C］//Proceedings of the 1st International Conference on Mobile Systems，Applications And Services.New York:ACM Press，2003.

［6］Mokbel M F，Chow Chi-Yin，Aref W G. The new Casper:query processing for location services without compromising privacy［C］//Proceedings of the 32nd International Conference on Very Large Data Bases(VLDB’06).New York:ACM Press，2006.

［7］Kalnis P，Ghinita G，Mouratidis K，et al. Preventing location-based identity inference in anonymous spatial queries［J］. IEEE Transaction on Knowledge and Data Engineering，2007，19(12):1719-1733.

［8］Talukder N，Ahamed S I. Preventing multi-query attack in location-based services［C］//Proceedings of the 3rd ACM Conference on Wireless Network Security.New York:ACM Press，2010.

［9］NIU B，ZHANG Z，LI X，et al. Privacy-area aware dummy generation algorithms for Location-Based Services［C］//Communications (ICC)，2014 IEEE International Conference on.Sydney，Australia:IEEE，2014:957-962.

［10］馬春光，周長利，楊松濤，等.基于Voronoi 圖預劃分的LBS 位置隱私保護方法［J］.通信學報，2015(5):5-16.

MA Chunguang，ZHOU Changli，YANG Songtao，et al.LBS location privacy preserving method based on voronoi graph partitioning［J］.Journal on Communications，2015(5):5-16.(in Chinese)

［11］YIU M L，Jensen C S，HUANG X，et al.SpaceTwist:managing the trade-offs among location privacy，query performance，and query accuracy in mobile services［C］// Proceedings of the IEEE International Conference on Data Engineering(ICDE.08).Cancun，Mexico:IEEE，2008.

［12］Kim Yong-Ki，Hossain Amina，Hossain Al-Amin，et al. Hilbert-order based spatial cloaking algorithm in road network［J］.Concurrency and Computation:Practice and Experience，2013，25(1):81-88.