一種基于LBS 的用戶錨點(diǎn)區(qū)域混淆隱私保護(hù)方案

王智明

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

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

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

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

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

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

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

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

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

1 面向位置服務(wù)的匿名隱私保護(hù)方案模型

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

1.1 ARCS 方案模型

文中ARCS 方案基于服務(wù)器結(jié)構(gòu)如圖1 所示，它是由移動(dòng)用戶、位置匿名服務(wù)器、LBS 服務(wù)器3 部分構(gòu)成。

圖1 ARCS 方案服務(wù)器結(jié)構(gòu)Fig.1 ARCS scheme server structure

1.1.1 移動(dòng)用戶 指使用便攜設(shè)備(如PDA、手機(jī)、全球定位系統(tǒng)GPS 等)發(fā)出有關(guān)位置查詢請求的用戶，便攜設(shè)備特點(diǎn)是體積小便于隨身攜帶，但數(shù)據(jù)存儲(chǔ)與處理能力較弱。

1.1.2 位置匿名服務(wù)器 該服務(wù)器主要功能包括實(shí)現(xiàn)位置的匿名處理，將用戶準(zhǔn)確的位置信息處理成為一片匿名的區(qū)域(當(dāng)前能夠處理的匿名區(qū)域一般是矩形或圓形);存儲(chǔ)用戶高頻率的查詢請求以及相對應(yīng)的候選結(jié)果集［11］;對用戶的查詢進(jìn)行匹配處理，共享候選結(jié)果集，以提高系統(tǒng)效率。

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

ARCS 方案模型具體工作流程:移動(dòng)用戶將查詢內(nèi)容與隱私要求，通過文件的形式發(fā)送到位置匿名服務(wù)器，位置匿名服務(wù)器首先在查詢?nèi)罩颈碇胁樵兪欠翊嬖谠撚脩?、是否有符合該用戶的候選結(jié)果集，若有的話將該結(jié)果直接共享給用戶，提高查詢系統(tǒng)效率;若沒有則退而查找是否有符合該用戶的匿名區(qū)域，有的話就共享該匿名區(qū)域。如果匹配的匿名區(qū)域也不存在，通過ARCS 方案算法產(chǎn)生新的匿名區(qū)域，完整走一遍ARCS 方案算法，直到得到用戶所需查詢結(jié)果(見圖1)。

1.2 ARCS 方案的位置匿名與鄰近節(jié)點(diǎn)處理過程

ARCS 方案模型如圖2 所示。實(shí)現(xiàn)位置隱私查詢的具體步驟:

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

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

3)位置匿名服務(wù)器分別將圓形匿名區(qū)域內(nèi)的節(jié)點(diǎn)q1，q2，… qn的范圍查詢請求，發(fā)送到LBS 服務(wù)器，LBS 服務(wù)器將處理產(chǎn)生的候選結(jié)果集，返回給位置匿名服務(wù)器。

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

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

下面討論在ARCS 方案算法中匿名區(qū)域內(nèi)的節(jié)點(diǎn)查找范圍U'K 的相關(guān)取值情況。

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

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

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

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

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

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

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

公式(1)中，用戶U 的查找半徑UK 由用戶提出，在UK 值一定時(shí)，當(dāng)dist(U，U')越小，匿名區(qū)域節(jié)點(diǎn)的查詢范圍U'K 就越小，相應(yīng)LBS 服務(wù)器需要的查詢處理開銷也就越少。但dist(U，U')的減小會(huì)造成隱私保護(hù)有效性降低，因此，需要根據(jù)用戶的匿名要求，平衡系統(tǒng)查詢開銷與隱私保護(hù)的有效性，選取合理的錨點(diǎn)U'。

2 ARCS 方案性能分析

關(guān)于ARCS 方案的性能，主要從查詢結(jié)果誤差率、查詢時(shí)間開銷和匿名性3 個(gè)方面來衡量。

2.1 查詢誤差率

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

設(shè)任意匿名區(qū)域內(nèi)有移動(dòng)節(jié)點(diǎn)p1，p2，p3，…，pn，各節(jié)點(diǎn)進(jìn)行范圍查詢處理所對應(yīng)的區(qū)域分別記做C1，C2，C3，…，Cn，則LBS 服務(wù)器返回的結(jié)果集記作Pc= {p| ?p ∈C}，其中C = C1∪C2∪C3…∪Cn，即C =;設(shè)用戶U 查詢的范圍區(qū)域?yàn)镃U，則該區(qū)域內(nèi)目標(biāo)集用PU表示，記作PU= {p | ?p ∈CU}，則LBS 服務(wù)器查詢處理的誤差率W 可以記作

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

2.2 查詢時(shí)間開銷

查詢時(shí)間開銷主要包含匿名處理、篩選結(jié)果集、產(chǎn)生候選集、數(shù)據(jù)通信方面的開銷。

1)匿名處理時(shí)間開銷:用戶提交查詢要求后，位置匿名服務(wù)器進(jìn)行匿名處理所耗費(fèi)時(shí)間的，記為Tanony(p，q)。Tanony(p，q)值的大小，取決于用戶隱私程度的要求p 和匿名區(qū)節(jié)點(diǎn)密度q 的情況，隱私要求程度p 越高，節(jié)點(diǎn)密度q 越高，匿名處理時(shí)間開銷Tanony (p，q)就越大。

2)篩選結(jié)果集:位置匿名服務(wù)器需要對LBS 服務(wù)器返回的查詢結(jié)果集篩選處理，去除那些與用戶相距較遠(yuǎn)的匿名區(qū)域節(jié)點(diǎn)，篩查出與用戶U 鄰近的節(jié)點(diǎn)，整個(gè)篩選過程的時(shí)間開銷記為Tfilter。

3)產(chǎn)生候選集:LBS 服務(wù)器對匿名區(qū)域節(jié)點(diǎn)的查詢處理生成候選結(jié)果集需要耗費(fèi)時(shí)間，記為Tcandi。

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

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

2.3 匿名性

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

進(jìn)一步可得

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

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

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

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

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

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

3.2 查詢誤差的比較

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

圖6 不同dist(U，U')取值下3 種算法查詢準(zhǔn)確率對照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 時(shí)，ARCS 算法查詢誤差率略小于SpaceTwist 算法，而當(dāng)dist(U，U')取值200 ～300 時(shí)，SpaceTwist 算法查詢誤差率略小。這是因?yàn)镾paceTwist 算法需要不斷向LBS 服務(wù)器請求最近的興趣點(diǎn)POI，直到用戶得到滿意結(jié)果為止，雖然這樣能達(dá)到較低的誤差率，但不斷向服務(wù)器發(fā)送請求也導(dǎo)致了通信開銷的加大。而由公式(2)知，當(dāng)匿名區(qū)域各節(jié)點(diǎn)返回的查詢區(qū)域集PC覆蓋用戶U 的查詢范圍區(qū)域PU時(shí)，ARCS 算法能達(dá)到100%的查詢準(zhǔn)確率，即實(shí)現(xiàn)零查詢誤差率。

3.3 查詢時(shí)間開銷比較

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

如圖9 實(shí)驗(yàn)結(jié)果所示，SpaceTwist 算法的通信時(shí)間開銷同樣受到匿名區(qū)間節(jié)點(diǎn)的密度影響明顯，隨著匿名區(qū)間節(jié)點(diǎn)數(shù)變大，兩種算法的系統(tǒng)通信消耗時(shí)間都明顯增加，但ARCS 算法相比SpaceTwist算法，在查詢時(shí)間消耗上有一定的優(yōu)勢。這主要是因?yàn)镾paceTwist 算法需要不斷地向LBS 服務(wù)器發(fā)出請求，獲取最近的興趣點(diǎn)POI，因而增加了通信量開銷。

圖8 不同節(jié)點(diǎn)數(shù)下NNC 和ARCS 算法的時(shí)間開銷比較Fig.8 Time cost comparison of the ARCS and NNC algorithms for different nodes

4 結(jié) 語

圖9 不同節(jié)點(diǎn)數(shù)下SpaceTwist 和ARCS 算法時(shí)間開銷比較Fig.9 Time cost comparison of the ARCS and SpaceTwist algorithms for different nodes

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

［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 圖預(yù)劃分的LBS 位置隱私保護(hù)方法［J］.通信學(xué)報(bào)，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.