潘 曉 諶偉璋 孫一格 吳 雷

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

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

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

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

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

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

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

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

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

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

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

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

1 相關(guān)工作

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

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

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

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

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

2.1 路網(wǎng)模型

定義1. 路網(wǎng)(road network). 路網(wǎng)被形式化地表示為一個(gè)無(wú)向圖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)用戶(hù)u在邊e上，則用戶(hù)u的位置信息被形式化地表示為u={eid，dist，v}，dist為用戶(hù)u所在位置距其所在邊的起點(diǎn)之間的距離，v為用戶(hù)的運(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ún)相似度

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

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

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

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

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

(1)

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

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

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

(2)

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

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

(3)

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

定義6. 時(shí)空相似性δ.已知有2個(gè)用戶(hù)ui和uj，以及他們的空間相似性ζ和速度相似性η.查詢(xún)用戶(hù)的時(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為用戶(hù)u的匿名集，其中，CSi={Cusi，Cssi}，Cusi為匿名用戶(hù)集合，Cssi為匿名路段集合，則有4個(gè)條件：

1) |Cusi|≥K；

2)Cusi=Cus1；

3) |Cssi|≥L；

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

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

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

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

3.1 SCPA主要思想

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

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

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

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

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

① if {Users}是新到查詢(xún)用戶(hù) then

② while true do

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

④ if {Users}不為空then

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

⑥Users=Users-Cus；

⑦ else

⑧ break；

⑨ end if

⑩ end while

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

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

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

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

輸出: 匿名用戶(hù)集合.

①Uset=?；

② while true do

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

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

⑤ for eachuserinedgedo

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

⑦ ifSimilarity≥δthen

⑧Uset.add(user)；

⑨ 更新u.K；

⑩ end if

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

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

Table 1 Sample of Query Users

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

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

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

(5)

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

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

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

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

輸出: 匿名路段集合.

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

②Cus=用戶(hù)u的匿名集用戶(hù)集合;

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

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

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

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

本文比較了SCPA算法和NVBA算法.NVBA算法為文獻(xiàn)[8]中抵御路網(wǎng)中的連續(xù)查詢(xún)最大速度攻擊的位置匿名算法.所有的匿名算法用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ù)查詢(xún)，每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)包括信息熵、匿名成功率、查詢(xún)處理代價(jià)、匿名時(shí)間.

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

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

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

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

4.3 性能評(píng)估

1) 匿名度K的影響.該部分評(píng)價(jià)了匿名度K對(duì)匿名算法性能的影響.匿名度K從3增加到15.隨著匿名度K的增加，意味著每一個(gè)匿名集需要包含更多的用戶(hù).從圖3(a)觀察到，無(wú)論在何種設(shè)置下，SCPA的信息熵均比NVBA高.因?yàn)镾CPA算法采用用戶(hù)分組策略，并實(shí)現(xiàn)了K-用戶(hù)共享.所以相比于NVBA算法能夠更好地抵御連續(xù)查詢(xún)攻擊.圖3(b)顯示隨著匿名需求的變化，2個(gè)匿名算法的成功率均呈現(xiàn)下降的趨勢(shì).因?yàn)楫?dāng)K值越來(lái)越大時(shí)，用戶(hù)的匿名度要求變的更嚴(yán)格，尋找滿(mǎn)足匿名度要求的用戶(hù)集將變得越來(lái)越難.但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è)用戶(hù)重復(fù)遍歷整個(gè)道路網(wǎng)絡(luò)，將耗費(fèi)更多的時(shí)間.如圖3(d)所示，2種算法的查詢(xún)代價(jià)均隨著K的增加而增加，因?yàn)槟涿邪烁嗟穆范?雖然SCPA比NVBA提供了更好的隱私保護(hù)和算法效率，但SCPA的查詢(xún)代價(jià)較之NVBA高，然而，SCPA僅比NVBA大約多花費(fèi)了0.03%查詢(xún)代價(jià).

2) 位置多樣性L的影響.該部分評(píng)價(jià)匿位置多樣性L對(duì)匿名算法性能的影響.路段差異性需求L增加意味著用戶(hù)的位置隱私需求更加嚴(yán)格，L亦從3增加到15.從圖4(a)觀察到，SCPA的信息熵在所有設(shè)置上均比NVBA高，平均要高出5倍，這說(shuō)明SCPA比NVBA提供了更安全的隱私保護(hù)強(qiáng)度.從圖4(b)中，可以看到NVBA的匿名成功率隨著L的增大逐漸下降，相比NVBA，SCPA算法的匿名成功率要比NVBA的高，且SCPA具有更穩(wěn)定的匿名成功率.從圖4(c)可以看出，對(duì)于L的增加，SCPA的平均匿名時(shí)間并沒(méi)有太大變化，從整體情況來(lái)看，SCPA比NVBA的算法效率更好.雖然SCPA比NVBA提供了更好的隱私保護(hù)和較好的算法效率，但SCPA的查詢(xún)代價(jià)較之NVBA高，從圖4(d)看出，2種算法的查詢(xún)代價(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著δ值變大，將很難為所有查詢(xún)用戶(hù)構(gòu)造具有高時(shí)空相似性的匿名集,從而導(dǎo)致用戶(hù)的平均信息熵和成功率都呈下降趨勢(shì).圖5(c)顯示，隨著δ的增加，平均匿名時(shí)間先增加，在δ值為0.8時(shí)達(dá)到最大，之后急劇下降.因?yàn)殡S著時(shí)空相似性δ的增加，在為查詢(xún)用戶(hù)做啟發(fā)式寬度優(yōu)先用戶(hù)搜索時(shí)，將需要花費(fèi)更多的時(shí)間.然而，當(dāng)δ值達(dá)到一定值時(shí)，如0.9時(shí)，因系統(tǒng)中大部分查詢(xún)用戶(hù)難以找到具有如此高相似的匿名用戶(hù)集，所以在為用戶(hù)生成匿名路段集時(shí)將花費(fèi)相對(duì)較少的時(shí)間.由圖5(d)中所示，隨著δ的增加，查詢(xún)代價(jià)逐漸遞減.因?yàn)棣脑酱?，表明查?xún)用戶(hù)越相似，匿名用戶(hù)在路網(wǎng)上將越集中，所以構(gòu)造匿名路段集時(shí)所產(chǎn)生的開(kāi)放點(diǎn)個(gè)數(shù)將相對(duì)減少，從而查詢(xún)代價(jià)變小.

5 結(jié) 論

本文研究了一種在道路網(wǎng)絡(luò)上基于時(shí)空相似性的連續(xù)查詢(xún)隱私保護(hù)算法SCPA.現(xiàn)有在道路網(wǎng)絡(luò)上的位置隱私保護(hù)工作大多針對(duì)快照查詢(xún)提供隱私保護(hù)，當(dāng)移動(dòng)用戶(hù)的位置發(fā)生連續(xù)更新時(shí)，容易遭受連續(xù)查詢(xún)攻擊和位置依賴(lài)攻擊.為了解決此問(wèn)題，本文基于查詢(xún)用戶(hù)的時(shí)空相似性采取分組構(gòu)造匿名集實(shí)現(xiàn)K-共享機(jī)制，并提出了一種啟發(fā)式的寬度優(yōu)先用戶(hù)搜索算法和連續(xù)時(shí)刻內(nèi)匿名路段集生成算法.最后通過(guò)一系列實(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ù)查詢(xún)的虛擬軌跡隱私保護(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é)旗.基于開(kāi)放網(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段潔,胡清華,張靈均,錢(qián)宇華,李德玉.基于鄰域粗糙集的多標(biāo)記分類(lèi)特征選擇算法[J].計(jì)算機(jī)研究與發(fā)展,2015,52(1):56-65DuanJie,HuQinghua,ZhangLingjun,QianYuhua,LiDeyu.FeatureSelectionforMulti-LabelClassificationBasedonNeighborhoodRoughSets[J].JournalofComputerResearchandDevelopment,2015,52(1):56-655唐成華,劉鵬程,湯申生,謝逸.基于特征選擇的模糊聚類(lèi)異常入侵行為檢測(cè)[J].計(jì)算機(jī)研究與發(fā)展,2015,52(3):718-728TangChenghua,LiuPengcheng,TangShensheng,XieYi.AnomalyIntrusionBehaviorDetectionBasedonFuzzyClusteringandFeaturesSelection[J].JournalofComputerResearchandDevelopment,2015,52(3):718-7286辛宇,楊靜,湯楚蘅,葛斯喬.基于局部語(yǔ)義聚類(lèi)的語(yǔ)義重疊社區(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秦兵,劉安安,劉挺.無(wú)指導(dǎo)的中文開(kāi)放式實(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ù)來(lái)源：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