時(shí) 磊,潘巨龍,左正魏

(中國(guó)計(jì)量大學(xué) 信息工程學(xué)院,浙江 杭州 310018)

?

一種基于代理服務(wù)的位置隱私保護(hù)方法

時(shí) 磊,潘巨龍,左正魏

(中國(guó)計(jì)量大學(xué) 信息工程學(xué)院,浙江 杭州 310018)

針對(duì)無(wú)線移動(dòng)網(wǎng)絡(luò)中通過(guò)代理用戶(hù)進(jìn)行位置服務(wù)時(shí),不可信賴(lài)的代理用戶(hù)可能帶來(lái)隱私泄露和區(qū)域匿名查詢(xún)?cè)斐赏ㄐ糯鷥r(jià)過(guò)高等問(wèn)題,提出了kAgPrivacy方法.首先,查詢(xún)用戶(hù)通過(guò)用戶(hù)之間協(xié)作形成匿名組,然后將匿名組形成的泛化區(qū)域代替真實(shí)單一位置發(fā)送給代理用戶(hù)進(jìn)行位置服務(wù).這樣既避免用戶(hù)和位置服務(wù)商的直接聯(lián)系,也避免了代理用戶(hù)的不可信性造成的隱私泄露問(wèn)題.同時(shí)，采用增量近鄰查詢(xún),保證了查詢(xún)結(jié)果準(zhǔn)確性;采用Voronoi圖技術(shù)進(jìn)行查詢(xún)返回結(jié)果過(guò)濾,可減少系統(tǒng)通信開(kāi)銷(xiāo).最后通過(guò)和其它算法比較,驗(yàn)證了本文方法的有效性.

代理查詢(xún);位置隱私;基于位置服務(wù);增量近鄰查詢(xún)

隨著智能手機(jī)、平板電腦和導(dǎo)航儀等移動(dòng)終端設(shè)備中導(dǎo)航技術(shù)的提高和無(wú)線移動(dòng)網(wǎng)絡(luò)的普及,以及GPS(Global Position System)、伽利略和北斗等衛(wèi)星定位系統(tǒng)的廣泛運(yùn)用,基于位置服務(wù)(Location Based Services,簡(jiǎn)稱(chēng)LBS)得到迅速發(fā)展[1].但是,在享受LBS帶來(lái)便利的同時(shí)也把自身的位置暴露了,使得個(gè)人隱私泄露的風(fēng)險(xiǎn)也隨之提高[2-3],位置服務(wù)的迅速發(fā)展和普及,基于位置所帶來(lái)的隱私泄露的問(wèn)題也將越來(lái)越引起人們的擔(dān)憂.

由于越來(lái)越多的隱私問(wèn)題在LBS中被提出,基于LBS的用戶(hù)隱私保護(hù)研究得到了更多學(xué)者的重視.目前,這方面研究大多數(shù)是基于位置k-匿名模型、假位置和空間加密等技術(shù).Gruteser等最早在位置隱私保護(hù)中采用數(shù)據(jù)庫(kù)中的k-匿名的思想,提出了位置k-匿名模型[4].大多數(shù)的位置k-匿名模型的研究都是基于可信第三方(trusted third party based)的中心服務(wù)器結(jié)構(gòu).其設(shè)計(jì)思想是當(dāng)用戶(hù)發(fā)出請(qǐng)求時(shí),將具體的位置信息、匿名數(shù)k以及查詢(xún)信息發(fā)給第三方中心服務(wù)器,中心服務(wù)器將用戶(hù)具體位置擴(kuò)展成至少包含k個(gè)用戶(hù)的匿名區(qū)域,再將匿名區(qū)域和用戶(hù)的查詢(xún)服務(wù)信息一起發(fā)送給位置服務(wù)商,獲得返回結(jié)果集后根據(jù)用戶(hù)的具體位置計(jì)算出合適的查詢(xún)結(jié)果,并將此結(jié)果返回給查詢(xún)用戶(hù).然而,當(dāng)中心服務(wù)器不是完全可信時(shí),用戶(hù)的位置信息和查詢(xún)信息等隱私將面臨暴露的風(fēng)險(xiǎn);同時(shí)中心服務(wù)器在用戶(hù)查詢(xún)時(shí)獲得用戶(hù)的所有信息,很容易成為集中攻擊點(diǎn).

由于中心服務(wù)器模型暴露出上述很多安全問(wèn)題,后續(xù)越來(lái)越多的研究采用無(wú)中心服務(wù)器的隱私保護(hù)模型.Chow等人[5]基于無(wú)中心服務(wù)器思想提出了P2P匿名方法,用戶(hù)通過(guò)自組織的方式形成匿名網(wǎng)絡(luò),并且從網(wǎng)絡(luò)中隨機(jī)選擇一個(gè)用戶(hù)作為代理用戶(hù)進(jìn)行代理查詢(xún),并將結(jié)果返回給查詢(xún)用戶(hù).Yiu等人[6]于2008年提出了SpaceTwist隱私保護(hù)算法,該文采用增量查詢(xún)算法進(jìn)行興趣點(diǎn)查詢(xún).用錨點(diǎn)代替用戶(hù)的真實(shí)位置發(fā)出查詢(xún)獲得精確的位置服務(wù)信息,但是他們沒(méi)有實(shí)現(xiàn)k匿名.針對(duì)SpaceTwist方法的缺陷,文獻(xiàn)[7]提出了CoPrivacy算法,在用戶(hù)自組織的情況下實(shí)現(xiàn)位置k-匿名,并且限定了匿名區(qū)域的最小半徑,提高了用戶(hù)的隱私保護(hù)強(qiáng)度.大多數(shù)的無(wú)中心服務(wù)器的隱私保護(hù)算法都是用戶(hù)和位置服務(wù)商直接聯(lián)系的,用戶(hù)查詢(xún)時(shí)雖然提供的是假位置,但是不可避免攻擊者通過(guò)一些信息,聯(lián)系用戶(hù)的ID和查詢(xún)信息也能推測(cè)出用戶(hù)的真實(shí)身份,因此文獻(xiàn)[8]提出AgPrivacy算法,引入代理用戶(hù)的概念進(jìn)行代理查詢(xún),查詢(xún)用戶(hù)將查詢(xún)信息發(fā)送給附近用戶(hù)代理查詢(xún),同時(shí)使用戶(hù)真實(shí)位置泛化成匿名區(qū)域后發(fā)送給代理用戶(hù),避免了代理用戶(hù)的不可信性造成的隱私泄露.但是該算法沒(méi)有使用位置k-匿名模型,假設(shè)泛化區(qū)域有且只有一個(gè)用戶(hù),那么當(dāng)代理用戶(hù)不可信時(shí),攻擊者就很容易從泛化區(qū)域中找到真實(shí)用戶(hù),該算法隱私保護(hù)度不高.

通過(guò)對(duì)已有的位置隱私保護(hù)算法模型的比較研究,本文提出了一種基于代理服務(wù)的隱私保護(hù)算法(kAgPrivacy).該方法采用無(wú)中心服務(wù)器結(jié)構(gòu),用戶(hù)通過(guò)單跳或多跳形成滿足用戶(hù)k匿名要求的匿名組;然而,當(dāng)用戶(hù)較少時(shí),會(huì)出現(xiàn)在一定時(shí)間內(nèi),無(wú)法尋找到k個(gè)用戶(hù)的情況,這時(shí)可以通過(guò)引入啞元等方法湊出k個(gè)用戶(hù)以滿足匿名條件,形成滿足k匿名條件的匿名組后,匿名組內(nèi)用戶(hù)組成區(qū)域的最小外接圓作為查詢(xún)用戶(hù)的泛化區(qū)域代替單一的查詢(xún)用戶(hù)真實(shí)位置,在匿名組中隨機(jī)選擇一個(gè)用戶(hù)作為代理用戶(hù),并把匿名組形成的區(qū)域的中心作為錨點(diǎn)代替查詢(xún)用戶(hù)的真實(shí)位置發(fā)送給位置服務(wù)商進(jìn)行查詢(xún)[9],返回結(jié)果采用Voronoi圖[10]技術(shù)進(jìn)行結(jié)果過(guò)濾,使查詢(xún)用戶(hù)得到準(zhǔn)確的位置服務(wù).這種方法切斷了查詢(xún)用戶(hù)和位置服務(wù)商的直接聯(lián)系,并且引入位置k-匿名模型,提高了隱私保護(hù)度;同時(shí)采用增量近鄰查詢(xún),使得用戶(hù)得到準(zhǔn)確的位置服務(wù).最終實(shí)現(xiàn)了查詢(xún)的服務(wù)質(zhì)量和用戶(hù)隱私保護(hù)之間平衡.

1 kAgPrivacy隱私保護(hù)方法介紹

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

定義1 用戶(hù)類(lèi)型表示：移動(dòng)用戶(hù){U1,U2,…,Uk}自組織形成網(wǎng)絡(luò),其中用戶(hù)UC請(qǐng)求用戶(hù)Up代理進(jìn)行位置服務(wù)查詢(xún),那么定義UC為查詢(xún)用戶(hù),Up為代理用戶(hù).

定義2 UC泛化區(qū)域Ω：UC發(fā)出查詢(xún)匿名參數(shù)要求k后,通過(guò)單跳或者多跳形成至少k個(gè)用戶(hù)的匿名組,該匿名組所構(gòu)成區(qū)域的最小外接圓即為用戶(hù)的泛化區(qū)域.

定義3 匿名組可以用G表示：G={s,k,q′},

其中：

s表示匿名組的標(biāo)記;

k表示組成匿名組用戶(hù)的個(gè)數(shù),是UC指定的匿名參數(shù);

q′=(x′,y′)表示代理錨點(diǎn)的位置坐標(biāo),是匿名組中用戶(hù)形成區(qū)域的中心,也是Up向位置服務(wù)器發(fā)出查詢(xún)代替UC真實(shí)位置時(shí)所用的假位置.(x′,y′)為錨點(diǎn)的經(jīng)緯度.

定義4 UC發(fā)出查詢(xún)請(qǐng)求用Q表示：Q={con,k,rmin};UC發(fā)送給代理用戶(hù)請(qǐng)求用Qc表示：Qc={o,r,con};

其中：

o=(x,y)表示UC泛化區(qū)域Ω的圓心坐標(biāo),(x,y)為圓心的經(jīng)緯度;

r表示UC泛化區(qū)域Ω的半徑;

con表示UC的查詢(xún)內(nèi)容;

k表示組成匿名組用戶(hù)的個(gè)數(shù),是UC指定的匿名參數(shù);

rmin表示UC泛化區(qū)域Ω的半徑最小值.

定義5 Up向位置服務(wù)商發(fā)出請(qǐng)求用Q′表示：Q′={q′,con},

其中：

q′=(x′,y′)表示代理錨點(diǎn)的位置坐標(biāo),(x′,y′)為錨點(diǎn)的經(jīng)緯度;

con表示UC的查詢(xún)內(nèi)容.

定義6 Voronoi圖是平面中的一種區(qū)域劃分結(jié)構(gòu),要求任一興趣點(diǎn)對(duì)應(yīng)一個(gè)劃分區(qū)域,用戶(hù)在該區(qū)域中任何位置到該興趣點(diǎn)的距離最近.其原理是興趣點(diǎn)與其周?chē)呐d趣點(diǎn)作中垂線,根據(jù)中垂線的定義,由中垂線構(gòu)成的區(qū)域中的興趣點(diǎn)就是該區(qū)域內(nèi)用戶(hù)最近鄰查詢(xún)結(jié)果.如圖1,對(duì)于興趣點(diǎn)p1,粗線內(nèi)中心區(qū)域就是其劃分區(qū)域,并且離該區(qū)域中任意位置的用戶(hù)最近的興趣點(diǎn)就是p1.

圖1 Voronoi圖劃分示意Figure 1 Example of Voronoi

1.2 系統(tǒng)結(jié)構(gòu)

本文提出的kAgPrivacy隱私保護(hù)方法是基于無(wú)中心服務(wù)器的隱私保護(hù)模型,主要由自組織構(gòu)成的匿名組和基于位置服務(wù)的服務(wù)器組成,系統(tǒng)的具體結(jié)構(gòu)如圖2.

kAgPrivacy隱私保護(hù)方法的基本思想過(guò)程：1)假設(shè)用戶(hù)UC發(fā)出LBS查詢(xún)請(qǐng)求Q,首先通過(guò)移動(dòng)終端獲得自己真實(shí)的位置q,然后通過(guò)單跳或者多跳形成至少含有k個(gè)用戶(hù)的匿名組,并且把匿名組用戶(hù)形成的區(qū)域的中心作為代替用戶(hù)真實(shí)位置的錨點(diǎn)q′,該區(qū)域的外接圓作為UC的泛化區(qū)域并且保證該外接圓的半徑大于等于rmin,接著形成查詢(xún)請(qǐng)求Qc發(fā)送給代理用戶(hù)Up;2)Up形成代理查詢(xún)請(qǐng)求Q′發(fā)送給位置服務(wù)商進(jìn)行增量近鄰查詢(xún);3)獲得結(jié)果集后采用Voronoi圖[10]的方法對(duì)查詢(xún)結(jié)果進(jìn)行過(guò)濾,然后返回給代理用戶(hù)Up;4).代理用戶(hù)再根據(jù)查詢(xún)用戶(hù)UC信息對(duì)結(jié)果集進(jìn)行過(guò)濾,并且將過(guò)濾后的結(jié)果發(fā)送給查詢(xún)用戶(hù)UC.

圖2 系統(tǒng)結(jié)構(gòu)Figure 2 System structure

2 用戶(hù)匿名

分析SpaceTwist算法發(fā)現(xiàn),沒(méi)有引入位置k-匿名模型,隱私泄露風(fēng)險(xiǎn)較高;分析CoPrivacy算法發(fā)現(xiàn),雖然采用了位置k-匿名模型,但是查詢(xún)用戶(hù)直接與位置服務(wù)器聯(lián)系,攻擊者易獲得用戶(hù)的查詢(xún)信息和背景信息從而推測(cè)出用戶(hù)隱私;分析AgPrivacy算法發(fā)現(xiàn),通過(guò)引入代理用戶(hù)的方式阻斷了查詢(xún)用戶(hù)和位置服務(wù)器的直接聯(lián)系,并且為了避免代理用戶(hù)不安全性引起的隱私泄露問(wèn)題,泛化了查詢(xún)用戶(hù)的真實(shí)位置,但是當(dāng)泛化區(qū)域有且只有查詢(xún)用戶(hù)時(shí),泛化區(qū)域?qū)τ诓豢尚诺拇碛脩?hù)是完全沒(méi)有意義的.因此,要使得對(duì)于不可信的位置服務(wù)器和不可信的代理用戶(hù),查詢(xún)用戶(hù)的隱私均可以得到有效的保護(hù),用戶(hù)UC發(fā)出查詢(xún)請(qǐng)求后通過(guò)單跳或者多跳的通信方式尋找近鄰用戶(hù),直到滿足UC的匿名參數(shù)k為止,形成滿足位置k-匿名的匿名組;計(jì)算匿名組中用戶(hù)構(gòu)成區(qū)域的外接圓作為UC的泛化區(qū)域發(fā)送給代理用戶(hù)Up,使得代理用戶(hù)對(duì)于查詢(xún)用戶(hù)的辨別率為1/k;將匿名組中用戶(hù)構(gòu)成的匿名區(qū)域的中心作為代理用戶(hù)向位置服務(wù)商發(fā)出查詢(xún)時(shí)提供的假位置.具體位置匿名算法如下：

算法：位置匿名

1) Procedure：定位查詢(xún)用戶(hù)UC;生成匿名組標(biāo)記s;

2) 設(shè)置跳數(shù)h←1;已發(fā)現(xiàn)節(jié)點(diǎn)集合為T(mén)←{φ};發(fā)現(xiàn)節(jié)點(diǎn)個(gè)數(shù)n←|T|;隱匿參數(shù)k;用戶(hù)泛化區(qū)域最小半徑值rmin;

3) while n

4) 廣播發(fā)現(xiàn)節(jié)點(diǎn)消息內(nèi)容h和s;

5) 接收響應(yīng)消息的節(jié)點(diǎn)Ui集合為T(mén)′;

6) 接收響應(yīng)消息的節(jié)點(diǎn)Ui位置Ui.l的集合為R′;

7) UC.s←s;Ui.s←s;

8) n=|T′|;

9) if n

10) if T=T′ then

11) 結(jié)束循環(huán);

12) end if

13) h←h+1;T←T′;

14) end if

15) end while

16) R′←{UC.l}∪R′;

17) R←R’中位置信息構(gòu)成的區(qū)域

18) q′←R的密度中心;

19) o←R的最小外接圓的圓心;

20) r′←R的最小外接圓的半徑;

21) if r′>rminthen

22) r←r′;

23) else

24) r←rmin;

25) end if

26) Qc←{o,r,con};

27) Up←隨機(jī)從T中選擇一節(jié)點(diǎn)作為代理用戶(hù);

28) Up←{Qc,q′};

30) End Procedure

用戶(hù)Uc發(fā)出查詢(xún)時(shí),首先進(jìn)行初始值設(shè)定：生成匿名組的記號(hào)s,設(shè)置廣播的跳數(shù)h為1,已經(jīng)發(fā)現(xiàn)的節(jié)點(diǎn)集合T為空集,已經(jīng)發(fā)現(xiàn)的節(jié)點(diǎn)個(gè)數(shù)n為0,以及設(shè)置用戶(hù)選擇的匿名參數(shù)k和用戶(hù)的最小泛化區(qū)域半徑rmin(算法第1-2行);接著廣播節(jié)點(diǎn)發(fā)現(xiàn)的消息,其消息內(nèi)容為參數(shù)h和s,等待近鄰節(jié)點(diǎn)的響應(yīng),并把響應(yīng)節(jié)點(diǎn)放入集合T′中,把響應(yīng)節(jié)點(diǎn)的位置信息放入集合R′中(算法第4-6行);將用戶(hù)Uc的記號(hào)置為匿名組的記號(hào)s,將響應(yīng)用戶(hù)Ui的記號(hào)置為匿名組的記號(hào)s,再將n設(shè)置為集合T′中節(jié)點(diǎn)的個(gè)數(shù)(算法第7-8行);此時(shí)比較n和k-1的大小,如果n大于或者等于k-1,則響應(yīng)節(jié)點(diǎn)的個(gè)數(shù)滿足用戶(hù)的匿名要求,節(jié)點(diǎn)尋找完畢;如果n小于k-1則要先比較集合T和T′,如果兩個(gè)集合相等,說(shuō)明鄰近節(jié)點(diǎn)已經(jīng)飽和,即使增加跳數(shù)也無(wú)法找到更多的用戶(hù),匿名失敗;如果兩個(gè)集合不相等,增加跳數(shù)繼續(xù)廣播發(fā)現(xiàn)節(jié)點(diǎn)信息尋找響應(yīng)用戶(hù)(算法第9-14行);直到最終n大于等于k-1,節(jié)點(diǎn)尋找完畢,結(jié)束while循環(huán).節(jié)點(diǎn)選擇完畢后,將用戶(hù)Uc的位置信息存入集合R′中,并將R′中所有節(jié)點(diǎn)構(gòu)成的區(qū)域設(shè)置為R;R的密度中心設(shè)置為q′作為代理用戶(hù)向位置服務(wù)商發(fā)出查詢(xún)時(shí)代替用戶(hù)真實(shí)位置的假位置信息;R的最小外接圓的圓心設(shè)置為o,最小外接圓的半徑設(shè)置為r′(算法第16-20行);此時(shí)比較r′和rmin的大小,如果r′大于rmin,那么用戶(hù)發(fā)送為代理用戶(hù)的泛化區(qū)域半徑r取r′的值,否則r取rmin的值(算法第21-25行);最后用戶(hù)將由o,r,查詢(xún)內(nèi)容con以及計(jì)算好的錨點(diǎn)q′組成的查詢(xún)內(nèi)容發(fā)送給代理用戶(hù)(算法第26-28行).用戶(hù)匿名結(jié)束.

3 增量近鄰查詢(xún)

代理用戶(hù)獲得錨點(diǎn)q′后,與位置服務(wù)商進(jìn)行增量近鄰查詢(xún).查詢(xún)過(guò)程如圖3,其中虛線內(nèi)中心區(qū)域是查詢(xún)用戶(hù)的泛化區(qū)域.并且涉及需求空間和供應(yīng)空間兩個(gè)參數(shù),需求空間是指以查詢(xún)用戶(hù)泛化區(qū)域Ω的圓心o為圓心,o與興趣點(diǎn)p的距離為半徑(γ)的圓;供應(yīng)空間是指以錨點(diǎn)q′為圓心,q′與興趣點(diǎn)p的距離為半徑(τ)的圓.

代理用戶(hù)以錨點(diǎn)q′作為假位置向位置服務(wù)商發(fā)起查詢(xún),獲得興趣點(diǎn)服務(wù),如圖3(a)；當(dāng)找到第2個(gè)興趣點(diǎn)時(shí),供應(yīng)空間繼續(xù)增大,需求空間繼續(xù)縮小,如圖3(b)；繼續(xù)查找興趣點(diǎn),供應(yīng)空間隨著越來(lái)越多的興趣點(diǎn)的找到將持續(xù)增大,需求空間將持續(xù)縮小,直到供應(yīng)空間完全覆蓋需求空間,判斷供應(yīng)空間是否也完全覆蓋了查詢(xún)用戶(hù)的泛化區(qū)域,如果沒(méi)有完全覆蓋如圖3(c),那么繼續(xù)查找興趣點(diǎn),直到供應(yīng)空間完全覆蓋查詢(xún)用戶(hù)的泛化區(qū)域,查詢(xún)結(jié)束,如圖3(d)；如果當(dāng)供應(yīng)空間完全覆蓋需求空間時(shí),供應(yīng)空間也完全覆蓋了泛化區(qū)域則無(wú)需繼續(xù)查詢(xún),查詢(xún)結(jié)束.

圖3 增量近鄰查詢(xún)Figure 3 Incremental nearest neighbor query

4 Voronoi圖結(jié)果過(guò)濾

由于本文算法中代理用戶(hù)無(wú)法確定查詢(xún)用戶(hù)的具體位置,必須將查詢(xún)結(jié)果全部返回給查詢(xún)用戶(hù),查詢(xún)用戶(hù)再根據(jù)移動(dòng)終端獲取的具體位置與返回結(jié)果進(jìn)行計(jì)算獲得最近鄰的查詢(xún)結(jié)果,這就造成了用戶(hù)自身過(guò)大的通信開(kāi)銷(xiāo)和查詢(xún)時(shí)間過(guò)大.因而可以考慮在位置服務(wù)器階段根據(jù)查詢(xún)結(jié)果劃分區(qū)域進(jìn)行查詢(xún)結(jié)果過(guò)濾,以減少用戶(hù)和代理用戶(hù)的通信開(kāi)銷(xiāo).根據(jù)上文定義6對(duì)Voronoi圖概念及原理的描述可知,其作為一種平面幾何中的分割方法可以在區(qū)域近鄰查詢(xún)中得到應(yīng)用.因而本文的算法思想就是位置服務(wù)器根據(jù)代理用戶(hù)發(fā)送的信息得到查詢(xún)結(jié)果候選集后引入Voronoi圖思想.其基本思路如圖4：首先位置服務(wù)器通過(guò)Voronoi圖思想將返回的候選結(jié)果集組成的區(qū)域進(jìn)行分割,然后將用戶(hù)的泛化區(qū)域Ω與分割后區(qū)域比較,提煉出兩者有交集的Voronoi圖,再將其通過(guò)代理用戶(hù)發(fā)送給查詢(xún)用戶(hù).根據(jù)Voronoi圖中垂線分割的思想,Voronoi圖中的某塊子域包含于匿名區(qū)域Ω中或者與其某塊子域相交,那么該子域中對(duì)應(yīng)的興趣點(diǎn)即為存在與其相交的泛化區(qū)域中的用戶(hù)的最近鄰查詢(xún)結(jié)果,從而避免直接返回查詢(xún)結(jié)果集帶來(lái)的大量計(jì)算,減少了查詢(xún)時(shí)間,降低了通信開(kāi)銷(xiāo)[8].

圖4 Voronoi圖結(jié)果過(guò)濾Figure 4 Filtered result based on Voronoi

5 實(shí)驗(yàn)分析

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

通過(guò)實(shí)驗(yàn)進(jìn)行驗(yàn)證改進(jìn)后的基于代理服務(wù)的位置隱私算法(kAgPrivacy)的有效性,模擬數(shù)據(jù)集由通用的Thomas Brinkhoff路網(wǎng)數(shù)據(jù)生成器生成,該數(shù)據(jù)生成器是通過(guò)導(dǎo)入德國(guó)Oldenburg的交通路網(wǎng)而生成模擬的移動(dòng)用戶(hù).本文算法采用JAVA語(yǔ)言實(shí)現(xiàn),實(shí)驗(yàn)計(jì)算機(jī)環(huán)境為3.2 GHz Intel Core i5處理器,4 GB內(nèi)存,Windows7操作系統(tǒng).實(shí)驗(yàn)中采用的默認(rèn)數(shù)據(jù)參數(shù)如表1.

表1 實(shí)驗(yàn)?zāi)J(rèn)參數(shù)

5.2 算法比較

首先,將改進(jìn)的基于代理的位置隱私保護(hù)方法kAgPrivacy與典型的采用中心服務(wù)器結(jié)構(gòu)的位置隱私保護(hù)方法PrivacyGrid[11]進(jìn)行比較.保持其它實(shí)驗(yàn)參數(shù)不變,比較兩者的匿名成功率和查詢(xún)結(jié)果大小隨著匿名用戶(hù)數(shù)k的變化而變化情況.匿名成功率指查詢(xún)用戶(hù)成功率指查詢(xún)用戶(hù)成功匿名的次數(shù)與實(shí)驗(yàn)用戶(hù)總查詢(xún)次數(shù)的比率.查詢(xún)結(jié)果大小指代理用戶(hù)向位置服務(wù)商發(fā)出增量近鄰查詢(xún)時(shí)返回的近鄰結(jié)果的個(gè)數(shù).其比較結(jié)果如圖5.

圖5 方法kAgPrivacy與方法PrivacyGrid比較Figure 5 Comparison between kAgPrivacy and PrivacyGrid

由圖5可以看出,在方法kAgPrivacy中,隨著用戶(hù)匿名參數(shù)k值的增加,用戶(hù)查詢(xún)匿名成功率略有下降,增量查詢(xún)返回的結(jié)果集有明顯的上升.這是由于隨著k值的增加,查詢(xún)用戶(hù)必須查找更多的鄰近用戶(hù)組成匿名組,匿名組中用戶(hù)個(gè)數(shù)的增加使得查詢(xún)用戶(hù)的泛化區(qū)域擴(kuò)大,錨點(diǎn)與查詢(xún)用戶(hù)真實(shí)位置的距離變大,這就造成了增量查詢(xún)返回的結(jié)果集變大.隨著用戶(hù)匿名參數(shù)k值增加,方法kAgPrivacy與方法PrivacyGrid的用戶(hù)查詢(xún)的匿名成功率相差不多.當(dāng)k值相同時(shí),方法kAgPrivacy較方法PrivacyGrid返回的結(jié)果集更小,尋找的候選結(jié)果更少,篩選出用戶(hù)需求結(jié)果的通信代價(jià)更小,k值越大,其優(yōu)勢(shì)越明顯.但是由于第三方中心服務(wù)器沒(méi)有網(wǎng)絡(luò)延遲,方法kAgPrivacy較方法PrivacyGrid的匿名時(shí)間可能會(huì)增多.不過(guò)相比較中心服務(wù)器易造成隱私泄露的弊端,本文的改進(jìn)算法還是很有優(yōu)勢(shì)的.

然后,將改進(jìn)后的基于代理的位置隱私保護(hù)方法kAgPrivacy與無(wú)中心服務(wù)器結(jié)構(gòu)的P2P空間匿名方法[6]進(jìn)行對(duì)比.保持其它實(shí)驗(yàn)參數(shù)不變,比較兩者的用戶(hù)協(xié)作平均通信消息量和查詢(xún)結(jié)果大小隨著匿名用戶(hù)數(shù)k的變化而變化情況.用戶(hù)協(xié)作平均通信消息數(shù)量指用戶(hù)通過(guò)查找鄰近用戶(hù)形成滿足匿名要求的匿名組到計(jì)算出錨點(diǎn)的平均傳輸消息數(shù)量.其比較結(jié)果如圖6.

圖6 方法kAgPrivacy與方法P2P比較Figure 6 Comparison between kAgPrivacy and P2P

由圖6可以看出,隨著匿名參數(shù)k值的增加,兩種方法的用戶(hù)協(xié)作平均通信消息量和查詢(xún)結(jié)果大小均有明顯增加.這是由于隨著k值的增加,查詢(xún)用戶(hù)必須尋求更多的鄰近用戶(hù)形成匿名組,而移動(dòng)用戶(hù)的總量沒(méi)有變化,那么需要用戶(hù)必須花費(fèi)更多時(shí)間查找更遠(yuǎn)距離的用戶(hù),查詢(xún)用戶(hù)的泛化區(qū)域增大,錨點(diǎn)離用戶(hù)的真實(shí)位置的距離增大,供應(yīng)空間更大,查詢(xún)返回的結(jié)果更多,造成的通信代價(jià)更大.與P2P空間匿名方法相比,在用戶(hù)協(xié)作平均通信消息量方面方法kAgPrivacy有著明顯的優(yōu)勢(shì),但是由于P2P空間匿名方法多選擇主動(dòng)模式查找用戶(hù),因而用戶(hù)的平均響應(yīng)時(shí)間會(huì)優(yōu)于方法kAgPrivacy.這是由于P2P空間匿名方法查找近鄰用戶(hù)時(shí)多選擇主動(dòng)模式,匿名組形成后仍然不斷的發(fā)送信息維持匿名組,因此當(dāng)用戶(hù)查詢(xún)時(shí)可以很快形成匿名區(qū)域,減少響應(yīng)時(shí)間;但是要維持匿名組的存在需要更多的用戶(hù)協(xié)作通信,造成了很大的通信代價(jià).并且本文在結(jié)果篩選方面借鑒了Voronoi圖的思想,避免了用戶(hù)對(duì)每一個(gè)候選結(jié)果的計(jì)算比較,快速準(zhǔn)確的找出用戶(hù)的查詢(xún)結(jié)果,有效地減少了系統(tǒng)通信開(kāi)銷(xiāo).

最后,將改進(jìn)后的基于代理的位置隱私保護(hù)方法kAgPrivacy與沒(méi)有k匿名的隱私保護(hù)方法AgPrivacy進(jìn)行對(duì)比.保持其它實(shí)驗(yàn)參數(shù)不變,比較兩者隨著k值變化的匿名成功率.其中由于AgPrivacy方法中的匿名區(qū)域半徑是用戶(hù)自定義的,本文實(shí)驗(yàn)假設(shè)此半徑為200 m.其比較結(jié)果如圖7.

圖7 方法kAgPrivacy與方法AgPrivacy比較Figure 7 Comparison between kAgPrivacy and AgPrivacy

由圖7可以看出,在方法kAgPrivacy中,隨著用戶(hù)匿名參數(shù)k值的增加,用戶(hù)查詢(xún)匿名成功率只是稍稍有點(diǎn)下降;但是,在方法AgPrivacy中,匿名成功率下降地非常迅速,這是由于在方法kAgPrivacy中,雖然隨著k值的增加,需要的用戶(hù)也越多,在一定時(shí)間內(nèi)沒(méi)有查詢(xún)到k個(gè)用戶(hù)的概率將會(huì)越大,匿名失敗率會(huì)稍微有所增加;可是由于沒(méi)有區(qū)域范圍的限制,整體來(lái)說(shuō)匿名的成功率仍然會(huì)很高.在方法AgPrivacy中由于匿名區(qū)域已經(jīng)限定,供應(yīng)空間的大小也就限定了,那么其中的用戶(hù)個(gè)數(shù)也只受用戶(hù)的疏密程度影響,由于模擬區(qū)域的用戶(hù)數(shù)量已經(jīng)限定,所以供應(yīng)空間內(nèi)的用戶(hù)數(shù)量也是趨于穩(wěn)定.因而,當(dāng)k值較小時(shí),可以滿足條件的概率很高,當(dāng)k值越來(lái)越大時(shí),滿足條件的概率逐步降低,匿名成功率也就越來(lái)越低.當(dāng)然,隨著查詢(xún)用戶(hù)限定的泛化區(qū)域的增大,匿名成功率也會(huì)相應(yīng)的增大,但是這會(huì)帶來(lái)通信代價(jià)過(guò)高的問(wèn)題.對(duì)于通信代價(jià)和匿名區(qū)域大小如何平衡這個(gè)問(wèn)題,也將作為接下來(lái)的研究重點(diǎn),本文就不做過(guò)多的討論.

6 結(jié) 論

針對(duì)無(wú)中心服務(wù)器結(jié)構(gòu)中基于代理用戶(hù)的位置隱私保護(hù)方法進(jìn)行位置服務(wù)時(shí),由于代理用戶(hù)的不可信性造成查詢(xún)用戶(hù)位置隱私和查詢(xún)隱私泄露的問(wèn)題,以及通過(guò)匿名區(qū)域進(jìn)行查詢(xún)?cè)斐刹樵?xún)結(jié)果準(zhǔn)確度難以保證和查詢(xún)通信代價(jià)過(guò)大等問(wèn)題,提出了kAgPrivacy方法.在匿名模塊,查詢(xún)用戶(hù)通過(guò)單跳或者多跳發(fā)現(xiàn)近鄰用戶(hù),構(gòu)成滿足用戶(hù)匿名要求k的匿名組,并將匿名組構(gòu)成的泛化區(qū)域代替用戶(hù)的真實(shí)位置發(fā)送給代理用戶(hù),使得即使代理用戶(hù)不可信時(shí),其識(shí)別查詢(xún)用戶(hù)的概率也只有1/k,以此達(dá)到用戶(hù)位置匿名保護(hù)的目的.在查詢(xún)模塊,借鑒SpaceTwist方法[6]中的增量近鄰查詢(xún),以解決查詢(xún)準(zhǔn)確率的問(wèn)題;并且借鑒Voronoi圖[10]的思想對(duì)位置服務(wù)器返回代理用戶(hù)的查詢(xún)結(jié)果進(jìn)行區(qū)域劃分,起到結(jié)果過(guò)濾的目的,減少了系統(tǒng)通信代價(jià),取得較好的效果.

[1] 左正魏，潘巨龍，魏琳琳.一種路網(wǎng)環(huán)境下LBS隱私保護(hù)算法[J].中國(guó)計(jì)量學(xué)院學(xué)報(bào),2015,26(3):359-364.

ZUO Zhengwei, PAN Julong, WEI Linlin. A privacy protection algorithm designed for LBS in road network[J]. Journal of China University of Metrology,2015,26(3):359-364.

[2] PEDRESCHI D, BONCHI F, TURINI F, et al. Privacy protection: regulations and technologies, opportunities and threats[C]// Mobility, Data Mining and Privacy. Berlin: Springer,2008:101-119.

[3] MOKBEL M F. Privacy in location-based services: state-of-the-art and research directions[C]// International Conference on Mobile Data Management. Mannheim: IEEE,2007:228-228.

[4] 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,2003:31-42.

[5] CHOW C Y,MOKEL M F,LIU X.A peer-to-peer spatial cloaking algorithm for anonymous location-based service[C]//Proceedings of the 14th Annual ACM International Symposium on Advances in Geographic Information Systems. Virginia: ACM,2006:171-178.

[6] YIU M L, 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 IEEE International Conference on Data Engineering. Canccun: IEEE,2008: 366-375.

[7] 黃毅,霍崢,孟小峰. CoPrivacy:一種用戶(hù)協(xié)作無(wú)匿名區(qū)域的位置隱私保護(hù)方法[J].計(jì)算機(jī)學(xué)報(bào),2011,34(10):1976-1985.

HUANG Yi, HUO Zheng, MENG Xiaofeng. CoPrivacy: a collabrative location privacy preserving method without cloaking region[J].Chinese Journal of Computers,2011,34(10):1975-1985

[8] 毛典輝,蔡強(qiáng),李海生,等.AgPrivacy:一種代理服務(wù)的LBS隱私保護(hù)方法[J].北京工業(yè)大學(xué)學(xué)報(bào),2013,39(11):1673-1679.

MAO Dianhui,CAI Qiang,LI Haisheng, et al. AgPrivacy: a LBS privacy protective method based agent service[J]. Journal of Beijing University of Technology,2013,39(11):1673-1679.

[9] HJALTASON G R, SAMET H. Distance browsing in spatial databases[J]. ACM Transactions on Database Systems,1999,24(2):265-318.

[10] LIN Xin, ZHOU Lingchen, CHEN Peng, et al: Privacy preserving reverse nearest-neighbor queries processing on road network[C]// Proceedings of Web-Age Information Management. Berlin Heidelberg:WAIM workshop,2012:19-28.

[11] BAMBA B, LIU L, PESTI P,et al.Supporting anonymous location queries in mobile environments with privacygrid[C]//Proceedings of the 17th International Conference on World Wide Web. New York: ACM,2008:237-246.

A location privacy protection method based on agent service

SHI Lei, PAN Julong, ZUO Zhengwei

(College of Information Engineering, China Jiliang University, Hangzhou 310018, China)

The unbelievable proxy user may cause privacy disclosure and the range query may cause more communication costs when a user needs location-based service(LBS) in wireless mobile networks. A new method called kAgPrivacy was proposed. Anonymity groups were firstly formed by some users through collaboration. The user treated the range which was consisted by members in the group as its location and sended querying to an agent. Not only did it avoid the direct relation between the querying user and the location server but also avoid the user’s real location being exposed. The method of incremental nearest neighbor query was adopted to ensure an accurate search. Voronoi technique was used to filter search results in order to decrease system communication costs. The experiment results show that the new method is effective compared with other methods.

agent query; location privacy; location-based service; incremental nearest neighbor query

2096-2835(2016)03-0330-08

10.3969/j.issn.2096-2835.2016.03.016

2016-05-10 《中國(guó)計(jì)量大學(xué)學(xué)報(bào)》網(wǎng)址：zgjl.cbpt.cnki.net

時(shí)磊(1991- ),女,江蘇省連云港人,碩士研究生,主要研究方向?yàn)長(zhǎng)BS隱私保護(hù). E-mail:1553036003@qq.com

潘巨龍,男,教授. E-mail: pjl@cjlu.edu.cn

TP309

A