肖燕芳，徐紅云

(華南理工大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院，廣州 510006)

1 概述

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

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

(1)利用率低

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

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

用戶發(fā)送給服務(wù)器的k個(gè)節(jié)點(diǎn)進(jìn)行查詢請(qǐng)求，服務(wù)器將k個(gè)節(jié)點(diǎn)的查詢結(jié)果返回給用戶，用戶從眾多的結(jié)果集中查找到自己所需要的結(jié)果，此過程造成過多不必要的查詢處理開銷和通信開銷。

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

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

2 位置隱私模型

本文基于中心服務(wù)器結(jié)構(gòu)的位置隱私模型展開研究，該模型的結(jié)構(gòu)如圖1所示。

圖1 位置隱私模型

模型主要包括3個(gè)部分：

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

(2)位置匿名服務(wù)器，主要包括：1)位置匿名模塊，用于將位置信息進(jìn)行匿名；2)數(shù)據(jù)存儲(chǔ)模塊，存儲(chǔ)的數(shù)據(jù)包括用戶查詢請(qǐng)求信息和服務(wù)器返回結(jié)果集；3)共享存儲(chǔ)模塊，用于實(shí)現(xiàn)位置匿名信息與服務(wù)器返回結(jié)果集的完全共享。

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

3 隱私攻擊模型

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

4 匿名區(qū)域變換法

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

4.1 預(yù)備知識(shí)

在移動(dòng)位置服務(wù)中，用戶所在位置周圍的移動(dòng)節(jié)點(diǎn)分布可以分為2種情況：(1)均勻分布，如圖2所示，用戶 A周圍 2個(gè)矩形區(qū)域內(nèi)節(jié)點(diǎn)數(shù)大致相同；(2)非均勻分布，如圖3所示，用戶A周圍2個(gè)矩形區(qū)域內(nèi)節(jié)點(diǎn)數(shù)相差較大。

圖2 節(jié)點(diǎn)均勻分布情況

圖3 節(jié)點(diǎn)非均勻分布情況

針對(duì)以上2種節(jié)點(diǎn)分布情況，位置匿名服務(wù)器采用匿名區(qū)域變換法生成匿名區(qū)域時(shí)，匿名區(qū)域中移動(dòng)節(jié)點(diǎn)數(shù)目差別較大，本文主要研究均勻分布的情況。算法中所用到的參數(shù)定義如下：

定義1 用戶發(fā)出的查詢請(qǐng)求File表示為：

File=(L,Key,Range)

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

定義 2 位置匿名服務(wù)器向位置訪問服務(wù)器發(fā)出的匿名區(qū)域查詢請(qǐng)求File’表示為：

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

其中，L’是經(jīng)過匿名處理后的匿名區(qū)域；Key是用戶查詢的關(guān)鍵字；Range’是匿名區(qū)域內(nèi)匿名節(jié)點(diǎn)的查找范圍。

4.2 位置匿名與鄰近節(jié)點(diǎn)處理

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

圖4 匿名區(qū)域變換示意圖

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

ART方法實(shí)現(xiàn)位置隱私查詢的步驟如下：

(1)定位用戶q的地理位置坐標(biāo)，即點(diǎn)A的坐標(biāo)。

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

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

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

(5)根據(jù)匿名需求，生成邊長為s的特定大小的匿名區(qū)域BCFN，區(qū)域BCFN內(nèi)節(jié)點(diǎn)表示為 q1, q2,… ,qn。

(6)位置匿名服務(wù)器向位置訪問服務(wù)器分別發(fā)送節(jié)點(diǎn) q1, q2,… ,qn的范圍查詢服務(wù)請(qǐng)求。

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

(8)位置匿名服務(wù)器檢索位置訪問服務(wù)器返回的查詢結(jié)果，從中選取恰當(dāng)?shù)牟樵兘Y(jié)果返回給用戶。

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

圖5 Range’

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

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

第 1種情況為 Range’

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

第 3 種情況為 Range’=dist(q, q’)+Range，即匿名區(qū)域內(nèi)移動(dòng)節(jié)點(diǎn)查找范圍半徑OP覆蓋查詢用戶q的查找范圍半徑 AQ，此情況下能夠很好地實(shí)現(xiàn)位置匿名，提供良好的服務(wù)質(zhì)量。

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

其中，q表示用戶所在位置；q’表示匿名區(qū)域內(nèi)移動(dòng)節(jié)點(diǎn)的位置。

用戶進(jìn)行服務(wù)請(qǐng)求的查詢范圍 Range由用戶定義，匿名區(qū)域內(nèi)移動(dòng)節(jié)點(diǎn)查詢范圍Range’由用戶與移動(dòng)節(jié)點(diǎn)間的距離dist（ q,q′）和用戶實(shí)際查找范圍Range決定。位置匿名服務(wù)器執(zhí)行匿名算法，選取錨點(diǎn) q’，直觀地，當(dāng)用戶 q距離錨點(diǎn) q’近時(shí)，Range’的選取范圍小，此時(shí)查詢處理開銷較低，隱私保護(hù)力度也降低。q’的選取由用戶的匿名需求決定。

5 算法性能分析

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

5.1 查準(zhǔn)率

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

設(shè)C內(nèi)目標(biāo)集合為Objectc，則：

設(shè)點(diǎn)A所在位置的用戶q范圍查詢區(qū)域?yàn)镃A，則CA內(nèi)目標(biāo)集合為：

采用本文的位置匿名方法處理后，服務(wù)器能夠提供的服務(wù)質(zhì)量 Q可以用用戶范圍查詢結(jié)果集與經(jīng)過位置匿名后的匿名節(jié)點(diǎn)查詢返回的結(jié)果集之比表示：

由式(1)可以看出，當(dāng)所選匿名區(qū)域包含用戶的查詢請(qǐng)求區(qū)域時(shí)，用戶的查準(zhǔn)率能夠達(dá)到 100%，但通信開銷增加；當(dāng)所選匿名區(qū)域與用戶查詢區(qū)域相交時(shí)，通過位置匿名中間件的處理，通信開銷少，能夠?qū)崿F(xiàn)良好的查準(zhǔn)率。

5.2 查詢開銷

用戶請(qǐng)求服務(wù)開銷主要包括以下3個(gè)方面：

(1)位置匿名服務(wù)器根據(jù)用戶的隱私需求進(jìn)行匿名處理時(shí)需要時(shí)間開銷，匿名處理時(shí)間與用戶的隱私要求和周圍節(jié)點(diǎn)密集度有關(guān)，當(dāng)密集度高時(shí)，處理時(shí)間長，反之，處理時(shí)間短。

(2)位置訪問服務(wù)器響應(yīng)匿名處理后的查詢請(qǐng)求需要時(shí)間開銷，將查詢結(jié)果返回給位置匿名服務(wù)器需要通信帶寬開銷。

(3)位置匿名服務(wù)器對(duì)查詢結(jié)果集進(jìn)行優(yōu)化處理，選擇與用戶鄰近匿名區(qū)域中的節(jié)點(diǎn)相對(duì)應(yīng)的查詢結(jié)果，剔除掉遠(yuǎn)離用戶的其他節(jié)點(diǎn)對(duì)應(yīng)的查詢結(jié)果需要時(shí)間開銷。

假設(shè)匿名處理時(shí)間為ψ(q)，服務(wù)器處理時(shí)間為ω，通信時(shí)間開銷為 T，查詢結(jié)果優(yōu)化時(shí)間為 ε，則總的查詢服務(wù)開銷Cost為：

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

5.3 匿名性

因?yàn)楣粽吣芙孬@匿名處理后的查詢請(qǐng)求File’(L’, Key, Range’)以及位置訪問服務(wù)器返回給位置匿名服務(wù)器的查詢結(jié)果集，所以攻擊者能夠獲知位置匿名查詢范圍Range’和匿名區(qū)域大小s2。攻擊者將匿名區(qū)域內(nèi)的節(jié)點(diǎn)進(jìn)行范圍查詢所覆蓋區(qū)域作為用戶的可能位置，從而推斷出用戶所在的區(qū)域?yàn)椋?/p>

攻擊者能夠推斷出用戶可能所在位置為距離匿名區(qū)域內(nèi)節(jié)點(diǎn) dist（ q, q′） 范圍內(nèi)的節(jié)點(diǎn)位置，因此，攻擊者推斷出用戶所在的區(qū)域?yàn)椋?/p>

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

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

定義隱私度T為區(qū)域Ψ內(nèi)所有節(jié)點(diǎn)與真實(shí)查詢用戶q的平均距離。

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

當(dāng)隱私度 T值增大時(shí)，dist（ q, q′）增大，而攻擊者推斷用戶所在區(qū)域范圍增大，攻擊者推斷用戶真實(shí)位置的難度增加，從而能夠?yàn)橛脩籼峁└玫奈恢秒[私保護(hù)。

6 實(shí)驗(yàn)評(píng)估

算法采用Java編程語言實(shí)現(xiàn)，實(shí)驗(yàn)環(huán)境為2.2 GHz的 Intel雙核 CPU，1 GB內(nèi)存。操作系統(tǒng)平臺(tái)是Microsoft Windows XP Professional。

6.1 參數(shù)設(shè)置和實(shí)驗(yàn)結(jié)果分析

實(shí)驗(yàn)數(shù)據(jù)采用 Thomas Brinkhoff的 Networkbased Generator of Moving Object[10]隨機(jī)生成的Oldenburg市的空間數(shù)據(jù)集，分別研究節(jié)點(diǎn)密集度和錨點(diǎn)距離 dist（ q, q′）對(duì)匿名區(qū)域變換算法ART性能的影響，針對(duì)不同參數(shù)，比較ART與Cloaking Region 算法和 SpaceTwist算法在通信開銷和匿名性方面的優(yōu)劣。其中，節(jié)點(diǎn)數(shù) 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，用戶離錨點(diǎn)距離 dist(q, q’)分別取50 m、100 m、150 m、200 m、250 m、300 m。

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

圖8 匿名區(qū)域內(nèi)節(jié)點(diǎn)數(shù)目及dist(q, q’)對(duì)查準(zhǔn)率的影響

圖9顯示了用戶數(shù)目與通信時(shí)間開銷之間的關(guān)

圖9 節(jié)點(diǎn)數(shù)目與通信時(shí)間開銷之間的關(guān)系

6.2 與CR算法的比較

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

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

表2 不同節(jié)點(diǎn)數(shù)目下2種算法的通信時(shí)間開銷 s

6.3 與SpaceTwist算法的比較

圖10顯示了 dist（ q, q′）=200 m時(shí)，ART算法和SpaceTwist算法的通信開銷比較結(jié)果。結(jié)果顯示，在特定空間節(jié)點(diǎn)數(shù)目下，ART算法的通信時(shí)間開銷略優(yōu)于SpaceTwist算法。

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

圖11是節(jié)點(diǎn)數(shù)為160 000時(shí) dist（ q, q′）對(duì) 2種算法通信時(shí)間開銷的影響，實(shí)驗(yàn)結(jié)果表明，d ist（ q, q′） 值的改變幾乎不會(huì)影響通信時(shí)間開銷。

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

圖12顯示了當(dāng) dist（ q, q′）改變時(shí)，SpaceTwist算法的查準(zhǔn)率優(yōu)于ART算法。這是因?yàn)镾paceTwist采用客戶-服務(wù)器體系結(jié)構(gòu)，不斷向位置訪問服務(wù)器請(qǐng)求最近POI (Point of Interest)，直到出現(xiàn)滿足用戶的請(qǐng)求結(jié)果，算法結(jié)束，此算法處理過程雖能夠?qū)崿F(xiàn)良好的查準(zhǔn)率，但不斷地向服務(wù)器發(fā)送請(qǐng)求導(dǎo)致通信開銷太大。由4.1節(jié)可知，當(dāng)式(1)中匿名區(qū)域內(nèi)節(jié)點(diǎn)查詢的目標(biāo)集合 ObjectC包含用戶q范圍查詢的結(jié)果區(qū)域CA中的目標(biāo)時(shí)，ART算法也能達(dá)到較高查準(zhǔn)率。

圖12 ART與SpaceTwist的查準(zhǔn)率比較

7 結(jié)束語

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

[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].計(jì)算機(jī)科學(xué)與探索, 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.