潘 曉 諶偉璋 孫一格 吳 雷

1(石家莊鐵道大學(xué)經(jīng)濟(jì)管理學(xué)院 石家莊 050043)2 (河北省高校人文社會(huì)科學(xué)重點(diǎn)研究基地(石家莊鐵道大學(xué)) 石家莊 050043)

道路網(wǎng)絡(luò)上基于時(shí)空相似性的連續(xù)查詢隱私保護(hù)算法

潘 曉1,2諶偉璋1孫一格1吳 雷1

1(石家莊鐵道大學(xué)經(jīng)濟(jì)管理學(xué)院 石家莊 050043)2(河北省高校人文社會(huì)科學(xué)重點(diǎn)研究基地(石家莊鐵道大學(xué)) 石家莊 050043)

(smallpx@stdu.edu.cn)

連續(xù)查詢作為基于位置服務(wù)中常見的服務(wù)類型之一，為人們的生活和工作帶來了巨大的便利.最近幾年，針對(duì)位置服務(wù)中的隱私保護(hù)引起了學(xué)術(shù)界研究者的廣泛關(guān)注.然而，現(xiàn)有在道路網(wǎng)絡(luò)上的位置隱私保護(hù)工作大多針對(duì)快照查詢提供隱私保護(hù).如果直接將這些算法應(yīng)用于連續(xù)查詢，由于連續(xù)查詢中位置頻繁更新，將同時(shí)產(chǎn)生連續(xù)查詢隱私泄露和精確位置的泄露.由于網(wǎng)絡(luò)拓?fù)涞拇嬖?，移?dòng)用戶的運(yùn)動(dòng)在一段時(shí)間內(nèi)具有時(shí)空相似的特點(diǎn).利用連續(xù)查詢用戶的時(shí)空相似性，提出了一種在道路網(wǎng)絡(luò)上基于時(shí)空相似性的連續(xù)查詢隱私保護(hù)算法.通過采取分組策略構(gòu)造匿名集和K-共享機(jī)制，提出了一種啟發(fā)式寬度優(yōu)先用戶搜索算法HBFS來構(gòu)造匿名用戶集，并提出了一種連續(xù)時(shí)刻內(nèi)匿名路段集生成算法CSGA生成匿名路段集合，可以同時(shí)防止連續(xù)查詢攻擊和位置依賴攻擊.最后，采用4個(gè)評(píng)價(jià)標(biāo)準(zhǔn)對(duì)算法進(jìn)行了一系列實(shí)驗(yàn)，驗(yàn)證了算法的有效性.

位置隱私；連續(xù)查詢；道路網(wǎng)絡(luò)；基于位置服務(wù)；移動(dòng)計(jì)算

隨著移動(dòng)技術(shù)的不斷發(fā)展，基于位置的服務(wù)(location based services, LBSs)已廣泛應(yīng)用于地理導(dǎo)航、社交娛樂、緊急救援、廣告推廣等應(yīng)用，其中連續(xù)查詢是LBS中非常常見的一種服務(wù)形式.用戶在獲得LBS位置服務(wù)帶來的便利的同時(shí)，個(gè)人數(shù)據(jù)也在遭受著隱私泄露的風(fēng)險(xiǎn)[1-2].具體來講，位置查詢中包含的位置信息將幫助攻擊者推理用戶的工作生活方式、身體健康狀況等.

現(xiàn)有道路網(wǎng)絡(luò)上的位置隱私保護(hù)算法多針對(duì)快照查詢提供隱私保護(hù)[3-4].其基本思想是基于位置K匿名和路段L多樣性模型，將K個(gè)用戶的確切位置隱藏于L個(gè)不同的路段中.連續(xù)查詢作為L(zhǎng)BS常見服務(wù)之一，用戶需要在查詢有效期內(nèi)不斷更新位置.如果直接將適用于快照查詢的隱私保護(hù)算法應(yīng)用于連續(xù)查詢，將產(chǎn)生連續(xù)查詢攻擊[5].同時(shí)，攻擊者結(jié)合網(wǎng)絡(luò)拓?fù)?、用戶在路網(wǎng)上的最大運(yùn)動(dòng)速度限制以及不同時(shí)刻的匿名位置，可以推測(cè)用戶的確切位置，造成位置依賴攻擊[6].然而，現(xiàn)有在道路網(wǎng)絡(luò)上的位置隱私保護(hù)工作無法同時(shí)防止連續(xù)查詢攻擊和位置依賴攻擊.

文獻(xiàn)[7]針對(duì)路網(wǎng)中的連續(xù)查詢攻擊問題，提出了一種基于Snet層級(jí)結(jié)構(gòu)的隱私保護(hù)算法.Snet層級(jí)結(jié)構(gòu)基于用戶轉(zhuǎn)移概率，預(yù)先將路網(wǎng)劃分成不同等級(jí)的路段子圖.利用Snet層級(jí)結(jié)構(gòu)可為查詢用戶構(gòu)造具有相似運(yùn)動(dòng)的匿名集，從而防止連續(xù)查詢攻擊.然而，該方法中所使用的轉(zhuǎn)移概率是基于歷史數(shù)據(jù)來預(yù)測(cè)移動(dòng)用戶在路網(wǎng)中的運(yùn)動(dòng)情況，較難準(zhǔn)確地構(gòu)造出能夠保持長(zhǎng)期具有相似運(yùn)動(dòng)的匿名用戶集.所以該方法難以保持較高的匿名成功率且容易出現(xiàn)查詢代價(jià)過大的現(xiàn)象.

文獻(xiàn)[8]針對(duì)路網(wǎng)中位置依賴攻擊問題，提出了一種啟發(fā)式的匿名算法.該算法以移動(dòng)用戶所在路網(wǎng)上的路段集合作為匿名區(qū)域，保證了任意連續(xù)時(shí)刻的匿名路段集合之間的網(wǎng)絡(luò)距離不超過最大速度限制要求從而防止了位置依賴攻擊.雖然該方法僅防止了路網(wǎng)中的位置依賴攻擊，但對(duì)連續(xù)查詢攻擊無效.文獻(xiàn)[8]將連續(xù)查詢位置隱私概念延伸到用戶的路徑隱私上，針對(duì)用戶的路徑隱私問題提出了M-cut隱私需求.M-cut隱私需求其實(shí)是一種基于K匿名的思想，其目的是要讓用戶在連續(xù)時(shí)刻內(nèi)的匿名路段集能夠形成K條完整的路徑，從而不僅能夠保護(hù)用戶的位置隱私而且能夠保護(hù)路徑隱私.但是因?yàn)槠淠涿粷M足文獻(xiàn)[5]提出的要求，所以該方法對(duì)防止連續(xù)查詢攻擊也無效.

為了同時(shí)防止連續(xù)查詢攻擊和位置依賴攻擊，本文提出了一種道路網(wǎng)路上基于時(shí)空相似性的連續(xù)查詢位置隱私保護(hù)算法.綜合考慮用戶的空間相似性和時(shí)間相似性，基于查詢用戶的時(shí)空相似性采取分組策略構(gòu)造匿名集，實(shí)現(xiàn)K-共享機(jī)制.提出了一種啟發(fā)式的寬度優(yōu)先用戶搜索算法以防止連續(xù)查詢攻擊；同時(shí)，在匿名用戶集不變的前提下，提出了一種連續(xù)時(shí)刻內(nèi)匿名路段集生成算法以防止位置依賴攻擊，在位置隱私保護(hù)與服務(wù)質(zhì)量間尋找到了一種均衡.

總結(jié)本文貢獻(xiàn)有3方面：

1) 提出了一種在道路網(wǎng)路上基于時(shí)空相似的連續(xù)查詢隱私保護(hù)算法SCPA，有效地保護(hù)移動(dòng)用戶連續(xù)查詢隱私;

2) 針對(duì)連續(xù)查詢攻擊和位置依賴攻擊，分別提出了啟發(fā)式寬度優(yōu)先用戶搜索算法HBFS和連續(xù)時(shí)刻內(nèi)匿名路段集生成算法CSGA;

3) 進(jìn)行了一系列實(shí)驗(yàn)，驗(yàn)證了算法的有效性.

1 相關(guān)工作

文獻(xiàn)[5]針對(duì)連續(xù)查詢隱私問題研究提出了一種基于組的方法，該方法是一種根據(jù)用戶當(dāng)前位置，找到和其鄰近的用戶構(gòu)成匿名集，匿名集在查詢有效期內(nèi)保持不變.該方法因未考慮用戶位置在未來的鄰近性，容易導(dǎo)致匿名區(qū)域過大，影響服務(wù)質(zhì)量.為了解決這一問題，文獻(xiàn)[9]提出了基于扭曲度的方法，給出了δp-隱私模型和δq-扭曲度模型來平衡用戶隱私和服務(wù)質(zhì)量，該工作不僅考慮到了移動(dòng)用戶連續(xù)查詢隱私需求，而且還考慮了移動(dòng)用戶的運(yùn)動(dòng)速度的影響，從而最小化信息扭曲度，保證了服務(wù)質(zhì)量.文獻(xiàn)[10]將文獻(xiàn)[5]對(duì)匿名集的要求放寬，提出了查詢m-不變性(m-invariance)模型，要求在用戶查詢有效期內(nèi)，所有匿名集合的敏感屬性交集最少有m個(gè)敏感屬性保持不變.另外，文獻(xiàn)[11]提出了一種基于預(yù)先劃分匿名區(qū)域的連續(xù)查詢位置隱私保護(hù)算法.該算法將用戶的運(yùn)動(dòng)軌跡按時(shí)間預(yù)先分成m段，使得各時(shí)間段中的匿名區(qū)域和最小，從而在保證隱私安全的同時(shí)提高服務(wù)質(zhì)量.然而，以上工作僅適用于自由空間.

路網(wǎng)中僅有的一些連續(xù)查詢隱私保護(hù)工作中，Palanisamy等人[12-14]提出了一種基于mix-zone的隱私保護(hù)技術(shù)，其主要思想是以路網(wǎng)交叉路口為中心，沿著路網(wǎng)出口的方向建立具有自適應(yīng)特點(diǎn)的非矩形mix-zone.每當(dāng)用戶進(jìn)入到該mix-zone中，不作任何位置更新并更換用戶進(jìn)入mix-zone前的假名.由于用戶在mix-zone中位置信息被隱藏同時(shí)其對(duì)應(yīng)假名信息也發(fā)生了變更，增加了將同一個(gè)用戶前后使用的假名關(guān)聯(lián)起來的難度,從而達(dá)到了保護(hù)用戶標(biāo)識(shí)的目的.但因mix-zone匿名技術(shù)是一種不規(guī)則形狀局部匿名的思想，其缺點(diǎn)是不能夠保證查詢用戶的全局匿名.當(dāng)用戶處于不規(guī)則區(qū)域外時(shí)，需要發(fā)布確切位置.

Fig. 1 The road networks圖1 路網(wǎng)結(jié)構(gòu)

文獻(xiàn)[7]針對(duì)路網(wǎng)中的連續(xù)查詢攻擊問題，受自由空間中將空間劃分成不同的區(qū)域的匿名處理思想啟發(fā)，提出了一種基于Snet層級(jí)結(jié)構(gòu)的隱私保護(hù)方法，將路網(wǎng)預(yù)先劃分成不同的路段子圖，每一個(gè)子圖為基礎(chǔ)匿名單元，通過歷史數(shù)據(jù)預(yù)測(cè)移動(dòng)用戶的轉(zhuǎn)移概率，從而基于Snet單元構(gòu)造具有相似運(yùn)動(dòng)趨勢(shì)的匿名集.該方法中，為了抵御連續(xù)查詢攻擊，要求連續(xù)查詢有效期內(nèi)的匿名用戶集之間的公共用戶需滿足全局K匿名要求.另外，為了抵御查詢同質(zhì)性攻擊，要求連續(xù)查詢有效期內(nèi)匿名集中的查詢服務(wù)屬性滿足全局查詢L多樣性要求.然而，該工作僅能防止連續(xù)查詢攻擊，忽略了位置依賴攻擊造成的位置泄露問題.

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

2.1 路網(wǎng)模型

定義1. 路網(wǎng)(road network). 路網(wǎng)被形式化地表示為一個(gè)無向圖G(V,E).其中，V={n1,n2,…,nn}，表示路網(wǎng)各結(jié)點(diǎn)集合；E為邊集，其中的每一條邊表示為(eid,ninj,d(e),vmax)，eid為路段標(biāo)識(shí)，ninj為結(jié)點(diǎn)序列表示該路段是從結(jié)點(diǎn)ni到結(jié)點(diǎn)nj(ni,nj∈V)，d(e)表示邊的長(zhǎng)度，vmax為該路段的最大速度限制.

如果一個(gè)移動(dòng)用戶u在邊e上，則用戶u的位置信息被形式化地表示為u={eid，dist，v}，dist為用戶u所在位置距其所在邊的起點(diǎn)之間的距離，v為用戶的運(yùn)動(dòng)速度.路網(wǎng)中的2點(diǎn)pi和pj之間的距離為點(diǎn)pi到點(diǎn)pj之間的最短路徑，可表示為SP(pi,pj).

定義2. 邊到邊的網(wǎng)絡(luò)距離[8].給定2條邊ei和ej，則2邊之間的距離可表示為

SP(ei,ej)=min{SP(a1,b1)+

d(emin),SP(a1,b2)+d(emin),SP(a2,b1)+

d(emin),SP(a2,b2)+d(emin)}，

其中,{a1,a2}和{b1,b2}分別為邊ei和ej的2鄰接點(diǎn)，d(emin)為d(ei)和d(ej)的較小者.

以圖1所示的路網(wǎng)結(jié)構(gòu)為例，如邊e14，其括號(hào)內(nèi)，12表示的是邊的長(zhǎng)度，4為最大速度限制.邊e14到e12之間的網(wǎng)絡(luò)距離SP(e14,e12)=min{SP(n3,n1)+d(e14),SP(n3,n8)+d(e14),SP(n10,n1)+d(e14)，SP(n10,n8)+d(e14)}=SP(n10,n8)+d(e14)=36.

2.2 連續(xù)查詢相似度

一般情況下，連續(xù)查詢可以表示為2種形式：

1)已知用戶當(dāng)前位置和查詢有效期[5,7,9]，如“查詢從當(dāng)前位置開始5 min內(nèi)距離我最近的醫(yī)院”；2)已知用戶在查詢有效期內(nèi)的路徑[15]，如“查詢從人民大學(xué)路徑北京大學(xué)、清華大學(xué)到達(dá)上地過程中距離我最近的飯店”.鑒于道路網(wǎng)絡(luò)上用戶運(yùn)動(dòng)在交叉路口運(yùn)動(dòng)的不可預(yù)知性，本文采用第2種形式表示道路網(wǎng)絡(luò)上移動(dòng)用戶的連續(xù)查詢.

為了簡(jiǎn)便，假設(shè)系統(tǒng)中的連續(xù)查詢用戶的起點(diǎn)和終點(diǎn)都為路段結(jié)點(diǎn).若連續(xù)查詢用戶位于路段中的某個(gè)感興趣點(diǎn)上，系統(tǒng)會(huì)自動(dòng)將其轉(zhuǎn)化為最近鄰路段結(jié)點(diǎn).

為了防止連續(xù)查詢攻擊，文獻(xiàn)[5]提出在查詢有效期內(nèi)保證用戶在每一個(gè)時(shí)刻發(fā)布的匿名集需要包含完全相同的用戶.為了保證匿名集用戶在查詢有效期內(nèi)具有較小的查詢代價(jià)，需要將相似用戶匿名在一起.本文從空間位置和用戶速度2個(gè)方面評(píng)價(jià)移動(dòng)用戶的相似性.

定義4. 空間相似性ζ.已知有2個(gè)用戶ui和uj，其對(duì)應(yīng)的連續(xù)查詢運(yùn)動(dòng)路徑分別為pathi和pathj，連續(xù)查詢的空間相似性ζ可表示為

(1)

其中，分子為路段的公共結(jié)點(diǎn)數(shù)，分母為路段結(jié)點(diǎn)數(shù)的較大值.易知ζ的取值范圍為[0,1]，越接近1則表示空間越相似.

①L可以根據(jù)不同的應(yīng)用和隱私需求，設(shè)置不同的語義，如L個(gè)不同路段數(shù)或L個(gè)不同敏感度的感興趣點(diǎn)等.簡(jiǎn)單起見，本文中的L指的是L個(gè)不同路段.

在給出查詢用戶的速度相似性前，先給出查詢用戶u在其運(yùn)動(dòng)路徑上的平均速度va的計(jì)算為

(2)

平均速度va的計(jì)算公式表示的是：根據(jù)用戶的當(dāng)前運(yùn)動(dòng)速度來預(yù)測(cè)用戶在整個(gè)連續(xù)查詢運(yùn)動(dòng)路徑上的平均速度.其中，u.v為查詢用戶在當(dāng)前路段上的運(yùn)動(dòng)速度，u.vmax為當(dāng)前路段的最大限制速度.

定義5. 速度相似性η.已知有2個(gè)連續(xù)查詢用戶ui和uj，ui.va和uj.va為用戶ui和uj在其運(yùn)動(dòng)路徑上的平均運(yùn)動(dòng)速度.則查詢用戶間的速度相似性η可表示為

(3)

定義5中的速度相似性η僅考慮速度的大小差異.因用戶的連續(xù)查詢運(yùn)動(dòng)路徑為有序結(jié)點(diǎn)的集合，已經(jīng)反應(yīng)了用戶的運(yùn)動(dòng)方向.易知η的取值范圍為[0,1]，越接近1則表示速度越相似.

定義6. 時(shí)空相似性δ.已知有2個(gè)用戶ui和uj，以及他們的空間相似性ζ和速度相似性η.查詢用戶的時(shí)空相似性δ可表示為

δ(ui,uj)=w1×ζ+w2×η，

(4)

其中，系數(shù)w1和w2分別決定了參數(shù)ζ和η的權(quán)重，有w1,w2≥0且w1+w2=1.

易知，δ具有3種性質(zhì)：

1)δ(ui,uj)≥0；

2)δ(ui,uj)=δ(uj,ui)；

3)δ(ui,uj)∈[0,1].

定義7. (K,L)-匿名模型.設(shè)CSi為用戶u的匿名集，其中，CSi={Cusi，Cssi}，Cusi為匿名用戶集合，Cssi為匿名路段集合，則有4個(gè)條件：

1) |Cusi|≥K；

2)Cusi=Cus1；

3) |Cssi|≥L；

4) ?u∈Cusi，u發(fā)布Cssi作為匿名區(qū)域.

其中，條件1確保了匿名集用戶滿足位置K匿名模型；條件2保證了CSi在每一個(gè)時(shí)刻發(fā)布的匿名用戶集包含完全相同的用戶；條件3保證了每個(gè)匿名路段集滿足位置L多樣性①；條件4確保了每個(gè)CSi中的用戶滿足位置K-共享性質(zhì).

3 基于時(shí)空相似性的連續(xù)查詢匿名算法

本文采用中心服務(wù)器結(jié)構(gòu)[6-9]，由匿名服務(wù)器完成匿名工作.3.1節(jié)說明道路網(wǎng)絡(luò)上基于時(shí)空相似性的連續(xù)查詢隱私保護(hù)算法SCPA的主要思想，3.2節(jié)介紹啟發(fā)式寬度優(yōu)先用戶搜索算法HBFS，3.3節(jié)為連續(xù)時(shí)刻內(nèi)匿名路段集生成算法CSGA及安全分析.

3.1 SCPA主要思想

匿名服務(wù)器中的連續(xù)查詢可以分為新到查詢用戶和活動(dòng)查詢用戶2種.新到查詢用戶是指剛剛提出連續(xù)查詢的用戶;活動(dòng)查詢用戶是指在連續(xù)查詢有效期內(nèi)發(fā)生位置更新的用戶.

SCPA算法的基本思想是：若用戶為新到查詢用戶，則基于時(shí)空相似性為查詢用戶分組，構(gòu)造匿名用戶集合Cus，并生成在初始位置的匿名路段集合Css1(具體參見3.2節(jié)).若用戶為活動(dòng)用戶，根據(jù)已知的匿名集用戶進(jìn)行匿名位置Cssi的更新(具體參見3.3節(jié)).

算法1. 道路網(wǎng)路上基于時(shí)空相似性的連續(xù)查詢隱私保護(hù)算法SCPA.

輸入: 連續(xù)查詢的路徑、匿名度需求K、位置L多樣性、路網(wǎng)G(V,E)；

輸出: 時(shí)刻ti的匿名集Csi(1≤i≤m).

① if {Users}是新到查詢用戶 then

② while true do

③u從Users集合中隨機(jī)選取一個(gè)用戶；

④ if {Users}不為空then

⑤ 使用算法2構(gòu)造匿名用戶集Cus；

⑥Users=Users-Cus；

⑦ else

⑧ break；

⑨ end if

⑩ end while

3.2 啟發(fā)式寬度優(yōu)先用戶搜素算法

在匿名初始階段，僅有用戶當(dāng)前時(shí)刻的位置，所以此階段不存在位置依賴攻擊.為了防止連續(xù)查詢攻擊，只需找到在查詢有效期內(nèi)能夠保持一致的匿名用戶集Cus.

算法2. 啟發(fā)式寬度優(yōu)先用戶搜索算法HBFS.

輸入: 連續(xù)查詢用戶u、路網(wǎng)G(V,E)；

輸出: 匿名用戶集合.

①Uset=?；

② while true do

③ 從u.edge開始在G(V,E)上執(zhí)行寬度有限搜索;

④ if在u.path.size()×(1-δ)中的結(jié)點(diǎn)未被訪問過then

⑤ for eachuserinedgedo

⑥ 計(jì)算Similarity(u,user)；

⑦ ifSimilarity≥δthen

⑧Uset.add(user)；

⑨ 更新u.K；

⑩ end if

基于定義6的時(shí)空相似性δ，本文提出了一種啟發(fā)式寬度優(yōu)先用戶搜素算法HBFS.其主要思想是從用戶當(dāng)前所在位置的附近，尋找與用戶具有時(shí)空相似性的用戶.若能夠找到滿足用戶K隱私需求的候選匿名用戶集，則將其作為匿名用戶集返回；否則以寬度優(yōu)先的方式從用戶當(dāng)前位置進(jìn)行擴(kuò)展，繼續(xù)尋找滿足要求的用戶.

表1給出了5個(gè)新到查詢用戶的信息，其在路網(wǎng)中的分布情況如圖2所示(實(shí)心點(diǎn)).設(shè)時(shí)空相似性δ默認(rèn)為0.7.隨機(jī)選取u1，做啟發(fā)式寬度優(yōu)先遍歷搜索用戶.可得用戶u2和u3滿足時(shí)空相似性δ要求，候選匿名用戶集Uset={u1,u2,u3}.又u1的隱私需求K=5，將用戶u從當(dāng)前位置進(jìn)行寬度擴(kuò)展，再次計(jì)算，可得u4，u5也滿足時(shí)空相似性δ要求.最后，有Uset={u1,u2,u3,u4,u5}作為匿名用戶集返回.

Table 1 Sample of Query Users

Fig. 2 Continuous queries on road networks圖2 路網(wǎng)中的連續(xù)查詢

3.3 連續(xù)時(shí)刻內(nèi)匿名路段集生成算法

定義8. 邊到邊集的網(wǎng)絡(luò)距離.給定一條邊edge和一個(gè)邊的集合Css，邊edge到Css的網(wǎng)絡(luò)距離可表示為

ND(edge,Css)=max{e∈{Css}|SP(edge,e)}，

直觀上，邊到邊集的網(wǎng)絡(luò)距離是邊到邊的網(wǎng)絡(luò)距離的最大值.

定義9. 邊集到邊集的網(wǎng)絡(luò)距離[8].給定2個(gè)邊集CssA和CssB，2邊集之間的網(wǎng)絡(luò)距離可表示為

ND(CssA,CssB)=

max{?ex∈CssA|ND(ex,CssB)}，

易知，ND(CssA,CssB)=ND(CssB,CssA).

為了防止道路網(wǎng)路上的連續(xù)查詢最大速度位置依賴攻擊，文獻(xiàn)[8]證明了任意連續(xù)時(shí)刻的匿名路段集合之間的網(wǎng)絡(luò)距離滿足用戶最大速度限制要求.然而，但未考慮用戶在不同路段上具有不同的限制速度的情況.為保證匿名集的位置K-共享屬性，本文在構(gòu)造匿名路段集時(shí)，采用式(5)來判斷路段是否滿足匿名要求：

ND(Cssi,Cssi-1)≤vminΔt，

(5)

其中，Cssi和Cssi-1為2個(gè)連續(xù)時(shí)刻的匿名路段集,vmin為匿名用戶集Cus中用戶的最小速度，Δt為查詢更新的間隔時(shí)間.

易知，對(duì)于任意2個(gè)時(shí)刻的匿名路段集，若匿名用戶集中的用戶能以最小速度到達(dá)最大距離位置，很明顯，對(duì)于匿名集中的任意用戶則都可達(dá).所以應(yīng)用式(5)可保證匿名集滿足位置K-共享屬性，從而能夠有效防止位置依賴攻擊.

算法3. 連續(xù)時(shí)刻匿名路段集生成算法CSGA.

輸入: 連續(xù)查詢用戶u、路網(wǎng)G(V,E)；

輸出: 匿名路段集合.

①Cssi-1=在ti-1匿名路段集合;

②Cus=用戶u的匿名集用戶集合;

③ 找到Cus中用戶當(dāng)前時(shí)刻所在路段Cssi;

④ ifCssi是一個(gè)非連通圖then

⑤ 尋找連通路段加入路段集合Cssi;

⑥ end if

⑦ while |Cssi|

⑧ 選取和匿名路段集合Cssi具有公共結(jié)點(diǎn)的路段插入Cssi;

⑨ end while

⑩ ifND(Cssi,Cssi-1)≥vminΔtthen

繼續(xù)圖2中的例子，假設(shè)查詢用戶u1在時(shí)刻t2更新查詢，此時(shí)，匿名集中的用戶u1,u2,u4位于e10，u3位于邊e14，u5位于邊e5上.根據(jù)連續(xù)時(shí)刻內(nèi)匿名路段集生成算法CSGA，可知，首先應(yīng)找到連通路段e16，接著判斷用戶的L隱私需求.u1所在匿名集的L位置多樣為5，將邊e17加入匿名路段集，接著利式(5)判斷匿名路段集是否滿足位置依賴攻擊的速度限制要求.最后，得到查詢用戶u1在時(shí)刻t2的匿名路段集合集Css2={e10,e14,e5,e16,e17}.

安全分析如下：SCPA算法生成的匿名集采用了降低位置粒度的方法保護(hù)位置隱私，同時(shí)滿足位置K匿名模型.位置K匿名模型可以保護(hù)用戶標(biāo)識(shí)；L路段多樣性將用戶的確切位置隱藏于L個(gè)不同的路段中.定義7中的條件2確保了連續(xù)查詢的匿名集包含完全相同的用戶，條件4確保在匿名集中的用戶均以匿名路段集Css作為匿名位置，保證了位置K-共享性，有效防止了連續(xù)查詢攻擊.另外，利用式(5)保證了匿名路段集之間的網(wǎng)絡(luò)距離滿足位置依賴攻擊的速度限制要求，可有效防止道路網(wǎng)絡(luò)中的位置依賴攻擊.

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

4.1 實(shí)驗(yàn)設(shè)置

本文比較了SCPA算法和NVBA算法.NVBA算法為文獻(xiàn)[8]中抵御路網(wǎng)中的連續(xù)查詢最大速度攻擊的位置匿名算法.所有的匿名算法用Java實(shí)現(xiàn)，并運(yùn)行于2.4 GHz處理器、2 GB內(nèi)存的Windows 7計(jì)算機(jī)上.本實(shí)驗(yàn)使用Thomas Brinkhoff移動(dòng)對(duì)象生產(chǎn)器①生成模擬移動(dòng)對(duì)象.生成器的輸入是Oldenburg地圖，包含6 105個(gè)路段結(jié)點(diǎn)和7 035條邊.實(shí)驗(yàn)?zāi)M生成10 000個(gè)模擬移動(dòng)對(duì)象，設(shè)每個(gè)對(duì)象均提出連續(xù)查詢，每10 s更新一次位置且默認(rèn)包括100個(gè)快照位置，隱私需求K和L的默認(rèn)值都為5，時(shí)空相似性δ的默認(rèn)值為0.7.表2中列出了實(shí)驗(yàn)參數(shù)具體信息.

Table 2 Default System Settings

4.2 評(píng)價(jià)標(biāo)準(zhǔn)

采用的評(píng)價(jià)標(biāo)準(zhǔn)包括信息熵、匿名成功率、查詢處理代價(jià)、匿名時(shí)間.

1) 信息熵[16-17]反映匿名算法為移動(dòng)用戶提供的保護(hù)強(qiáng)度.信息熵越大，則保護(hù)強(qiáng)度越大.

2) 匿名成功率是指成功匿名的移動(dòng)用戶在所有提出查詢的移動(dòng)用戶中所占比例.匿名成功率越高，說明匿名算法對(duì)查詢響應(yīng)能力越好.

3) 匿名時(shí)間指的是一定規(guī)模移動(dòng)用戶的所有查詢請(qǐng)求在多長(zhǎng)時(shí)間內(nèi)可以得到匿名處理.這是反映匿名算法好壞的重要指標(biāo)之一.匿名時(shí)間越短越好，說明了匿名算法的高效性.

4) 查詢處理代價(jià)是指位置經(jīng)過匿名處理后，在服務(wù)提供商端由于保護(hù)隱私查詢處理產(chǎn)生的額外代價(jià).實(shí)驗(yàn)利用文獻(xiàn)[17]中的查詢代價(jià)模型，使用匿名路段集中包含的路段和開放點(diǎn)個(gè)數(shù)評(píng)價(jià)查詢代價(jià).查詢代價(jià)越小越好.

4.3 性能評(píng)估

1) 匿名度K的影響.該部分評(píng)價(jià)了匿名度K對(duì)匿名算法性能的影響.匿名度K從3增加到15.隨著匿名度K的增加，意味著每一個(gè)匿名集需要包含更多的用戶.從圖3(a)觀察到，無論在何種設(shè)置下，SCPA的信息熵均比NVBA高.因?yàn)镾CPA算法采用用戶分組策略，并實(shí)現(xiàn)了K-用戶共享.所以相比于NVBA算法能夠更好地抵御連續(xù)查詢攻擊.圖3(b)顯示隨著匿名需求的變化，2個(gè)匿名算法的成功率均呈現(xiàn)下降的趨勢(shì).因?yàn)楫?dāng)K值越來越大時(shí)，用戶的匿名度要求變的更嚴(yán)格，尋找滿足匿名度要求的用戶集將變得越來越難.但SCPA算法的匿名成功率要比NVBA的高.

Fig. 3 Evaluation on different anonymity level K圖3 2種算法在不同K匿名度需求下的比較

比較SCPA與NVBA的平均匿名時(shí)間.圖3(c)顯示，隨著匿名度K的增加，2種算法的匿名時(shí)間也呈上升的趨勢(shì)，且SCPA比NVBA的算法效率更好.因?yàn)镾CPA算法采用分組構(gòu)造匿名集，相比之下，NVBA需要為每一個(gè)用戶重復(fù)遍歷整個(gè)道路網(wǎng)絡(luò)，將耗費(fèi)更多的時(shí)間.如圖3(d)所示，2種算法的查詢代價(jià)均隨著K的增加而增加，因?yàn)槟涿邪烁嗟穆范?雖然SCPA比NVBA提供了更好的隱私保護(hù)和算法效率，但SCPA的查詢代價(jià)較之NVBA高，然而，SCPA僅比NVBA大約多花費(fèi)了0.03%查詢代價(jià).

2) 位置多樣性L的影響.該部分評(píng)價(jià)匿位置多樣性L對(duì)匿名算法性能的影響.路段差異性需求L增加意味著用戶的位置隱私需求更加嚴(yán)格，L亦從3增加到15.從圖4(a)觀察到，SCPA的信息熵在所有設(shè)置上均比NVBA高，平均要高出5倍，這說明SCPA比NVBA提供了更安全的隱私保護(hù)強(qiáng)度.從圖4(b)中，可以看到NVBA的匿名成功率隨著L的增大逐漸下降，相比NVBA，SCPA算法的匿名成功率要比NVBA的高，且SCPA具有更穩(wěn)定的匿名成功率.從圖4(c)可以看出，對(duì)于L的增加，SCPA的平均匿名時(shí)間并沒有太大變化，從整體情況來看，SCPA比NVBA的算法效率更好.雖然SCPA比NVBA提供了更好的隱私保護(hù)和較好的算法效率，但SCPA的查詢代價(jià)較之NVBA高，從圖4(d)看出，2種算法的查詢代價(jià)均隨著L的增加而增加，因?yàn)槟涿邪烁嗟穆范?

3) 時(shí)空相似性δ的影響.該部分對(duì)系統(tǒng)參數(shù)時(shí)空相似性δ進(jìn)行實(shí)驗(yàn)評(píng)估，以驗(yàn)證時(shí)空相似性δ對(duì)SCPA算法的性能的影響.由于NVBA不涉及時(shí)空相似性，所以此節(jié)僅對(duì)SCPA進(jìn)行了實(shí)驗(yàn)驗(yàn)證.δ值從0.5變化到0.9.

Fig. 4 Evaluation on different location diversity L圖4 2種算法在不同路段差異性L下的比較

Fig. 5 Evaluation on different δ of SCPA Algorithm圖5 SCPA算法在不同時(shí)空相似性δ下的性能評(píng)估

從圖5(a)和5(b)中，可以看到，在δ取值為0.7之前，信息熵和匿名成功率基本保持不變，但當(dāng)δ大于0.7后信息熵和匿名成功率都逐漸下降.因?yàn)殡S著δ值變大，將很難為所有查詢用戶構(gòu)造具有高時(shí)空相似性的匿名集,從而導(dǎo)致用戶的平均信息熵和成功率都呈下降趨勢(shì).圖5(c)顯示，隨著δ的增加，平均匿名時(shí)間先增加，在δ值為0.8時(shí)達(dá)到最大，之后急劇下降.因?yàn)殡S著時(shí)空相似性δ的增加，在為查詢用戶做啟發(fā)式寬度優(yōu)先用戶搜索時(shí)，將需要花費(fèi)更多的時(shí)間.然而，當(dāng)δ值達(dá)到一定值時(shí)，如0.9時(shí)，因系統(tǒng)中大部分查詢用戶難以找到具有如此高相似的匿名用戶集，所以在為用戶生成匿名路段集時(shí)將花費(fèi)相對(duì)較少的時(shí)間.由圖5(d)中所示，隨著δ的增加，查詢代價(jià)逐漸遞減.因?yàn)棣脑酱螅砻鞑樵冇脩粼较嗨?，匿名用戶在路網(wǎng)上將越集中，所以構(gòu)造匿名路段集時(shí)所產(chǎn)生的開放點(diǎn)個(gè)數(shù)將相對(duì)減少，從而查詢代價(jià)變小.

5 結(jié) 論

本文研究了一種在道路網(wǎng)絡(luò)上基于時(shí)空相似性的連續(xù)查詢隱私保護(hù)算法SCPA.現(xiàn)有在道路網(wǎng)絡(luò)上的位置隱私保護(hù)工作大多針對(duì)快照查詢提供隱私保護(hù)，當(dāng)移動(dòng)用戶的位置發(fā)生連續(xù)更新時(shí)，容易遭受連續(xù)查詢攻擊和位置依賴攻擊.為了解決此問題，本文基于查詢用戶的時(shí)空相似性采取分組構(gòu)造匿名集實(shí)現(xiàn)K-共享機(jī)制，并提出了一種啟發(fā)式的寬度優(yōu)先用戶搜索算法和連續(xù)時(shí)刻內(nèi)匿名路段集生成算法.最后通過一系列實(shí)驗(yàn)，驗(yàn)證了算法的有效性，匿名算法可保證平均95%以上的匿名成功率，且平均匿名時(shí)間為18 ms.

[1]Wang Lu, Meng Xiaofeng. Location privacy preservation in big data era: A survey[J]. Journal of Software, 2014, 25(4): 693-712 (in Chinese)(王璐, 孟小峰. 位置大數(shù)據(jù)隱私保護(hù)研究綜述[J]. 軟件學(xué)報(bào), 2014, 25(4): 693-712)

[2]Terrovitis M, Liagouris J, Mamoulis N, et al. Privacy preservation by disassociation[J]. Proceedings of the VLDB Endowment, 2012, 5(10): 944-955

[3]Chow C, Mokbel M F, Bao J, et al. Query-aware location anonymization for road networks[J]. Geoinformatical, 2010, 15(3): 571-607

[4]Wang Ting, Liu Ling. Privacy aware mobile services over road networks[C]Proc of the 35th Int Conf on VLDB. New York: ACM, 2009: 1042-1053

[5]Chow C Y, Mokbel M F. Enabling private continuous queries for revealed user locations[C]Proc of the 10th Int Conf on SSTD. Berlin: Springer, 2007: 258-275

[6]Xu Jianliang, Tang Xueyan, Hu Haibo, et al. Privacy-conscious location-based queries in mobile environments[J]. IEEE Trans on Parallel & Distributed Systems, 2010, 21(3): 313-326

[7]Wang Yong, Xia Yun, Hou Jie, et al. A fast privacy-preserving framework for continuous location-based queries in road networks[J]. Journal of Network & Computer Applications, 2015, 53(3): 57-73

[8]Wang Yilei, Zhou Hao, Wu Yingjie, et al. Preserving location privacy for location-based services with continuous queries on road network[C]Proc of the 7th Int Conf on Computer Science & Education. Los Alamitos, CA: IEEE Computer Society, 2012: 822-827

[9]Pan Xiao, Meng Xiaofeng, Xu Jianliang. Distortion based anonymity for continuous queries in location based mobile services[C]Proc of the ACM SIGSPATIAL, New York: ACM, 2009: 256-265

[10]Dewri R, Ray I, Ray I, et al. Query m-Invariance: Preventing query disclosures in continuous location-based services[C]Proc of the 11th Int Conf on Mobile Data Management. Piscataway, NJ: IEEE, 2010: 95-104

[11]Shin H, Vaidya J, Atluri V, et al. Ensuring privacy and security for LBS through trajectory partitioning[C]Proc of the 11th Int Conf on Mobile Data Management. Piscataway, NJ: IEEE, 2010: 224-226

[12]Palanisamy B, Liu L, Lee K, et al. Anonymizing continuous queries with delay-tolerant mix-zones over road networks[J]. Distributed & Parallel Databases, 2014, 32(1): 91-118

[13]Palanisamy B, Liu L. MobiMix: Protecting location privacy with mix-zones over road networks[C]Proc of Int Conf on ICDE. Piscataway, NJ: IEEE, 2011: 494-505

[14]Palanisamy B, Liu Ling, Lee K, et al. Location privacy with road network mix-zones[C]Proc of Int Conf on MSN. Piscataway, NJ: IEEE, 2012: 124-131

[15]Tao Yufei, Papadias D, Shen Qiongmao. Continuous nearest neighbor search[C]Proc of the 28th Int Conf on VLDB. New York: ACM, 2002: 287-298

[16]Zeng Zhihao, Sun Qi, Yao Bei, et al. A virtual trajectory privacy protection method for continuous queries[J]. Science Technology and Engineering, 2014, 33(1): 93-98 (in Chinese)(曾志浩, 孫琪, 姚貝, 等. 一種面向連續(xù)查詢的虛擬軌跡隱私保護(hù)方法[J]. 科學(xué)技術(shù)與工程, 2014, 33(1): 93-98)

[17]Pan Xiao, Chen Weizhang, Wu Lei, et al. Protecting personalized privacy against sensitivity homogeneity attacks over road networks in mobile services[J]. Frontiers of Computer Science, 2016, 10(2): 370-38

Pan Xiao, born in 1981. PhD. Associate professor at Shjiazhuang Tiedao University. Member of CCF. Her main research interests include mobile computing, social network, and privacy protection.

Chen Weizhang, born in 1992. Master. His main research interests include data mining, data management on moving objects and privacy-aware computing.

Sun Yige, born in 1996. Undergraduate. Her main research interests include data management on moving objects and privacy-aware computing.

Wu Lei, born in 1980. Master. Lecturer at Shjiazhuang Tiedao University. Member of the Soft Science Research Institute on Engineering and Construction Management in Hebei Province. His main research interests include data management on moving objects and location based social network.

2015年《計(jì)算機(jī)研究與發(fā)展》高被引論文TOP10

排名論文信息1王繼業(yè),孟坤,曹軍威,程志華,高靈超,林闖.能源互聯(lián)網(wǎng)信息技術(shù)研究綜述[J].計(jì)算機(jī)研究與發(fā)展,2015,52(5):1109-1126WangJiye,MengKun,CaoJunwei,ChengZhihua,GaoLingchao,LinChuang.InformationTechnologyforEnergyInternet:ASurvey[J].JournalofComputerResearchandDevelopment,2015,52(5):1109-11262張煥龍,胡士強(qiáng),楊國(guó)勝.基于外觀模型學(xué)習(xí)的視頻目標(biāo)跟蹤方法綜述[J].計(jì)算機(jī)研究與發(fā)展,2015,52(1):177-190ZhangHuanlong,HuShiqiang,YangGuosheng.VideoObjectTrackingBasedonAppearanceModelsLearning[J].JournalofComputerResearchandDevelopment,2015,52(1):177-1903王元卓,賈巖濤,劉大偉,靳小龍,程學(xué)旗.基于開放網(wǎng)絡(luò)知識(shí)的信息檢索與數(shù)據(jù)挖掘[J].計(jì)算機(jī)研究與發(fā)展,2015,52(2):456-474WangYuanzhuo,JiaYantao,LiuDawei,JinXiaolong,ChengXueqi.OpenWebKnowledgeAidedInformationSearchandDataMining[J].JournalofComputerResearchandDevelopment,2015,52(2):456-4744段潔,胡清華,張靈均,錢宇華,李德玉.基于鄰域粗糙集的多標(biāo)記分類特征選擇算法[J].計(jì)算機(jī)研究與發(fā)展,2015,52(1):56-65DuanJie,HuQinghua,ZhangLingjun,QianYuhua,LiDeyu.FeatureSelectionforMulti-LabelClassificationBasedonNeighborhoodRoughSets[J].JournalofComputerResearchandDevelopment,2015,52(1):56-655唐成華,劉鵬程,湯申生,謝逸.基于特征選擇的模糊聚類異常入侵行為檢測(cè)[J].計(jì)算機(jī)研究與發(fā)展,2015,52(3):718-728TangChenghua,LiuPengcheng,TangShensheng,XieYi.AnomalyIntrusionBehaviorDetectionBasedonFuzzyClusteringandFeaturesSelection[J].JournalofComputerResearchandDevelopment,2015,52(3):718-7286辛宇,楊靜,湯楚蘅,葛斯喬.基于局部語義聚類的語義重疊社區(qū)發(fā)現(xiàn)算法[J].計(jì)算機(jī)研究與發(fā)展,2015,52(7):1510-1521XinYu,YangJing,TangChuheng,GeSiqiao.AnOverlappingSemanticCommunityDetectionAlgorithmBasedonLocalSemanticCluster[J].JournalofComputerResearchandDevelopment,2015,52(7):1510-15217吳章玲,金培權(quán),岳麗華,孟小峰.基于PCM的大數(shù)據(jù)存儲(chǔ)與管理研究綜述[J].計(jì)算機(jī)研究與發(fā)展,2015,52(2):343-361WuZhangling,JinPeiquan,YueLihua,MengXiaofeng.ASurveyonPCM-BasedBigDataStorageandManagement[J].JournalofComputerResearchandDevelopment,2015,52(2):343-3618秦兵,劉安安,劉挺.無指導(dǎo)的中文開放式實(shí)體關(guān)系抽取[J].計(jì)算機(jī)研究與發(fā)展,2015,52(5):1029-1035QinBing,LiuAnan,LiuTing.UnsupervisedChineseOpenEntityRelationExtraction[J].JournalofComputerRe-searchandDevelopment,2015,52(5):1029-10359陳世敏.大數(shù)據(jù)分析與高速數(shù)據(jù)更新[J].計(jì)算機(jī)研究與發(fā)展,2015,52(2):333-342ChenShimin.BigDataAnalysisandDataVelocity[J].JournalofComputerResearchandDevelopment,2015,52(2):333-34210馬思偉.AVS視頻編碼標(biāo)準(zhǔn)技術(shù)回顧及最新進(jìn)展[J].計(jì)算機(jī)研究與發(fā)展,2015,52(1):27-37MaSiwei.HistoryandRecentDevelopmentsofAVSVideoCodingStandards[J].JournalofComputerResearchandDevelopment,2015,52(1):27-37

數(shù)據(jù)來源：CSCD，中國(guó)知網(wǎng)；統(tǒng)計(jì)日期：2016-12-05

Continuous Queries Privacy Protection Algorithm Based on Spatial-Temporal Similarity Over Road Networks

Pan Xiao1,2, Chen Weizhang1, Sun Yige1, and Wu Lei1

1(SchoolofEconomic&Management,ShijiazhuangTiedaoUniversity,Shijiazhuang050043)2(KeyResearchBaseforHumanitiesandSocialSciencesinHebeiProvince(ShijiazhuangTiedaoUniversity),Shijiazhuang050043)

Continuous queries are one of the most common queries in location-based services (LBSs), although particularly useful, such queries raise serious privacy concerns. However, most of the existing location cloaking approaches over road networks are only applicable for snapshots queries. If these algorithms are applied on continuous queries directly, due to continuous location frequently updated, continuous query privacy will be disclosed. Moreover, combined with the network topology and other network parameters (limited speed etc.), the attackers are knowledgeable, which can easily lead to precise location privacy disclosure. We observe that mobile objects have similar spatial and temporal features due to the existing of network topology. In order to resist continuous query attacks and location-dependent attacks simultaneously, we propose a continuous queries privacy protection algorithm based on spatial-temporal similarity over road networks. The algorithm adopts user grouping andK-sharing privacy requirement strategies to constitute cloaking user sets, which is used to resist continuous queries attack. Then, with the same premise of cloaking user sets, a continuous cloaking segment sets generating algorithm is proposed to resist location-dependent attacks, which makes a balance between location privacy and service quality. Finally, we conduct series of experiments to verify our algorithm with four evaluation measures, and the experimental results show the effectiveness of the proposed algorithm.

location privacy; continuous query; road networks; location based services (LBSs); mobile computing

2016-08-02；

2016-10-10

國(guó)家自然科學(xué)基金項(xiàng)目(61303017,61502146)； 河北省自然科學(xué)基金項(xiàng)目(F2014210068)； 河北省教育廳青年基金項(xiàng)目(QN2016083)；河北省高等學(xué)校人文社會(huì)科學(xué)研究項(xiàng)目(GH161079)；石家莊鐵道大學(xué)第四屆優(yōu)秀青年科學(xué)基金項(xiàng)目(Z661250444)； 河北省研究生創(chuàng)新資助項(xiàng)目(Z99910)；國(guó)家級(jí)大學(xué)生創(chuàng)新創(chuàng)業(yè)訓(xùn)練計(jì)劃項(xiàng)目(201510107013, 201610107003) This work was supported by the National Natural Science Foundation of China (61303017,61502146), the Natural Science Foundation of Hebei Province (F2014210068), the Young Scholars Project of the Hebei Provincial Education Department (QN2016083), the Project of Humanities and Social Sciences for the Colleges in Hebei Province (GH161079), the Fourth Outstanding Youth Foundation of Shijiazhuang Tiedao University (Z661250444), the Graduate Innovative Foundation of Hebei Province(Z99910), and the College Innovative Training Program Foundation of China(201510107013, 201610107003).

TP391