道路網絡上基于時空相似性的連續查詢隱私保護算法

潘 曉 諶偉璋 孫一格 吳 雷

1(石家莊鐵道大學經濟管理學院 石家莊 050043)2 (河北省高校人文社會科學重點研究基地(石家莊鐵道大學) 石家莊 050043)

道路網絡上基于時空相似性的連續查詢隱私保護算法

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

1(石家莊鐵道大學經濟管理學院 石家莊 050043)2(河北省高校人文社會科學重點研究基地(石家莊鐵道大學) 石家莊 050043)

(smallpx@stdu.edu.cn)

連續查詢作為基于位置服務中常見的服務類型之一，為人們的生活和工作帶來了巨大的便利.最近幾年，針對位置服務中的隱私保護引起了學術界研究者的廣泛關注.然而，現有在道路網絡上的位置隱私保護工作大多針對快照查詢提供隱私保護.如果直接將這些算法應用于連續查詢，由于連續查詢中位置頻繁更新，將同時產生連續查詢隱私泄露和精確位置的泄露.由于網絡拓撲的存在，移動用戶的運動在一段時間內具有時空相似的特點.利用連續查詢用戶的時空相似性，提出了一種在道路網絡上基于時空相似性的連續查詢隱私保護算法.通過采取分組策略構造匿名集和K-共享機制，提出了一種啟發式寬度優先用戶搜索算法HBFS來構造匿名用戶集，并提出了一種連續時刻內匿名路段集生成算法CSGA生成匿名路段集合，可以同時防止連續查詢攻擊和位置依賴攻擊.最后，采用4個評價標準對算法進行了一系列實驗，驗證了算法的有效性.

位置隱私；連續查詢；道路網絡；基于位置服務；移動計算

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

現有道路網絡上的位置隱私保護算法多針對快照查詢提供隱私保護[3-4].其基本思想是基于位置K匿名和路段L多樣性模型，將K個用戶的確切位置隱藏于L個不同的路段中.連續查詢作為LBS常見服務之一，用戶需要在查詢有效期內不斷更新位置.如果直接將適用于快照查詢的隱私保護算法應用于連續查詢，將產生連續查詢攻擊[5].同時，攻擊者結合網絡拓撲、用戶在路網上的最大運動速度限制以及不同時刻的匿名位置，可以推測用戶的確切位置，造成位置依賴攻擊[6].然而，現有在道路網絡上的位置隱私保護工作無法同時防止連續查詢攻擊和位置依賴攻擊.

文獻[7]針對路網中的連續查詢攻擊問題，提出了一種基于Snet層級結構的隱私保護算法.Snet層級結構基于用戶轉移概率，預先將路網劃分成不同等級的路段子圖.利用Snet層級結構可為查詢用戶構造具有相似運動的匿名集，從而防止連續查詢攻擊.然而，該方法中所使用的轉移概率是基于歷史數據來預測移動用戶在路網中的運動情況，較難準確地構造出能夠保持長期具有相似運動的匿名用戶集.所以該方法難以保持較高的匿名成功率且容易出現查詢代價過大的現象.

文獻[8]針對路網中位置依賴攻擊問題，提出了一種啟發式的匿名算法.該算法以移動用戶所在路網上的路段集合作為匿名區域，保證了任意連續時刻的匿名路段集合之間的網絡距離不超過最大速度限制要求從而防止了位置依賴攻擊.雖然該方法僅防止了路網中的位置依賴攻擊，但對連續查詢攻擊無效.文獻[8]將連續查詢位置隱私概念延伸到用戶的路徑隱私上，針對用戶的路徑隱私問題提出了M-cut隱私需求.M-cut隱私需求其實是一種基于K匿名的思想，其目的是要讓用戶在連續時刻內的匿名路段集能夠形成K條完整的路徑，從而不僅能夠保護用戶的位置隱私而且能夠保護路徑隱私.但是因為其匿名集不滿足文獻[5]提出的要求，所以該方法對防止連續查詢攻擊也無效.

為了同時防止連續查詢攻擊和位置依賴攻擊，本文提出了一種道路網路上基于時空相似性的連續查詢位置隱私保護算法.綜合考慮用戶的空間相似性和時間相似性，基于查詢用戶的時空相似性采取分組策略構造匿名集，實現K-共享機制.提出了一種啟發式的寬度優先用戶搜索算法以防止連續查詢攻擊；同時，在匿名用戶集不變的前提下，提出了一種連續時刻內匿名路段集生成算法以防止位置依賴攻擊，在位置隱私保護與服務質量間尋找到了一種均衡.

總結本文貢獻有3方面：

1) 提出了一種在道路網路上基于時空相似的連續查詢隱私保護算法SCPA，有效地保護移動用戶連續查詢隱私;

2) 針對連續查詢攻擊和位置依賴攻擊，分別提出了啟發式寬度優先用戶搜索算法HBFS和連續時刻內匿名路段集生成算法CSGA;

3) 進行了一系列實驗，驗證了算法的有效性.

1 相關工作

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

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

Fig. 1 The road networks圖1 路網結構

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

2 預備知識

2.1 路網模型

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

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

定義2. 邊到邊的網絡距離[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鄰接點，d(emin)為d(ei)和d(ej)的較小者.

以圖1所示的路網結構為例，如邊e14，其括號內，12表示的是邊的長度，4為最大速度限制.邊e14到e12之間的網絡距離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 連續查詢相似度

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

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

為了簡便，假設系統中的連續查詢用戶的起點和終點都為路段結點.若連續查詢用戶位于路段中的某個感興趣點上，系統會自動將其轉化為最近鄰路段結點.

為了防止連續查詢攻擊，文獻[5]提出在查詢有效期內保證用戶在每一個時刻發布的匿名集需要包含完全相同的用戶.為了保證匿名集用戶在查詢有效期內具有較小的查詢代價，需要將相似用戶匿名在一起.本文從空間位置和用戶速度2個方面評價移動用戶的相似性.

定義4. 空間相似性ζ.已知有2個用戶ui和uj，其對應的連續查詢運動路徑分別為pathi和pathj，連續查詢的空間相似性ζ可表示為

(1)

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

①L可以根據不同的應用和隱私需求，設置不同的語義，如L個不同路段數或L個不同敏感度的感興趣點等.簡單起見，本文中的L指的是L個不同路段.

在給出查詢用戶的速度相似性前，先給出查詢用戶u在其運動路徑上的平均速度va的計算為

(2)

平均速度va的計算公式表示的是：根據用戶的當前運動速度來預測用戶在整個連續查詢運動路徑上的平均速度.其中，u.v為查詢用戶在當前路段上的運動速度，u.vmax為當前路段的最大限制速度.

定義5. 速度相似性η.已知有2個連續查詢用戶ui和uj，ui.va和uj.va為用戶ui和uj在其運動路徑上的平均運動速度.則查詢用戶間的速度相似性η可表示為

(3)

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

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

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

(4)

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

易知，δ具有3種性質：

1)δ(ui,uj)≥0；

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

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

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

1) |Cusi|≥K；

2)Cusi=Cus1；

3) |Cssi|≥L；

4) ?u∈Cusi，u發布Cssi作為匿名區域.

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

3 基于時空相似性的連續查詢匿名算法

本文采用中心服務器結構[6-9]，由匿名服務器完成匿名工作.3.1節說明道路網絡上基于時空相似性的連續查詢隱私保護算法SCPA的主要思想，3.2節介紹啟發式寬度優先用戶搜索算法HBFS，3.3節為連續時刻內匿名路段集生成算法CSGA及安全分析.

3.1 SCPA主要思想

匿名服務器中的連續查詢可以分為新到查詢用戶和活動查詢用戶2種.新到查詢用戶是指剛剛提出連續查詢的用戶;活動查詢用戶是指在連續查詢有效期內發生位置更新的用戶.

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

算法1. 道路網路上基于時空相似性的連續查詢隱私保護算法SCPA.

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

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

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

② while true do

③u從Users集合中隨機選取一個用戶；

④ if {Users}不為空then

⑤ 使用算法2構造匿名用戶集Cus；

⑥Users=Users-Cus；

⑦ else

⑧ break；

⑨ end if

⑩ end while

3.2 啟發式寬度優先用戶搜素算法

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

算法2. 啟發式寬度優先用戶搜索算法HBFS.

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

輸出: 匿名用戶集合.

①Uset=?；

② while true do

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

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

⑤ for eachuserinedgedo

⑥ 計算Similarity(u,user)；

⑦ ifSimilarity≥δthen

⑧Uset.add(user)；

⑨ 更新u.K；

⑩ end if

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

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

Table 1 Sample of Query Users

Fig. 2 Continuous queries on road networks圖2 路網中的連續查詢

3.3 連續時刻內匿名路段集生成算法

定義8. 邊到邊集的網絡距離.給定一條邊edge和一個邊的集合Css，邊edge到Css的網絡距離可表示為

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

直觀上，邊到邊集的網絡距離是邊到邊的網絡距離的最大值.

定義9. 邊集到邊集的網絡距離[8].給定2個邊集CssA和CssB，2邊集之間的網絡距離可表示為

ND(CssA,CssB)=

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

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

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

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

(5)

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

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

算法3. 連續時刻匿名路段集生成算法CSGA.

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

輸出: 匿名路段集合.

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

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

③ 找到Cus中用戶當前時刻所在路段Cssi;

④ ifCssi是一個非連通圖then

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

⑥ end if

⑦ while |Cssi|

⑧ 選取和匿名路段集合Cssi具有公共結點的路段插入Cssi;

⑨ end while

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

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

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

4 實驗結果與分析

4.1 實驗設置

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

Table 2 Default System Settings

4.2 評價標準

采用的評價標準包括信息熵、匿名成功率、查詢處理代價、匿名時間.

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

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

3) 匿名時間指的是一定規模移動用戶的所有查詢請求在多長時間內可以得到匿名處理.這是反映匿名算法好壞的重要指標之一.匿名時間越短越好，說明了匿名算法的高效性.

4) 查詢處理代價是指位置經過匿名處理后，在服務提供商端由于保護隱私查詢處理產生的額外代價.實驗利用文獻[17]中的查詢代價模型，使用匿名路段集中包含的路段和開放點個數評價查詢代價.查詢代價越小越好.

4.3 性能評估

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

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

比較SCPA與NVBA的平均匿名時間.圖3(c)顯示，隨著匿名度K的增加，2種算法的匿名時間也呈上升的趨勢，且SCPA比NVBA的算法效率更好.因為SCPA算法采用分組構造匿名集，相比之下，NVBA需要為每一個用戶重復遍歷整個道路網絡，將耗費更多的時間.如圖3(d)所示，2種算法的查詢代價均隨著K的增加而增加，因為匿名集中包含了更多的路段.雖然SCPA比NVBA提供了更好的隱私保護和算法效率，但SCPA的查詢代價較之NVBA高，然而，SCPA僅比NVBA大約多花費了0.03%查詢代價.

2) 位置多樣性L的影響.該部分評價匿位置多樣性L對匿名算法性能的影響.路段差異性需求L增加意味著用戶的位置隱私需求更加嚴格，L亦從3增加到15.從圖4(a)觀察到，SCPA的信息熵在所有設置上均比NVBA高，平均要高出5倍，這說明SCPA比NVBA提供了更安全的隱私保護強度.從圖4(b)中，可以看到NVBA的匿名成功率隨著L的增大逐漸下降，相比NVBA，SCPA算法的匿名成功率要比NVBA的高，且SCPA具有更穩定的匿名成功率.從圖4(c)可以看出，對于L的增加，SCPA的平均匿名時間并沒有太大變化，從整體情況來看，SCPA比NVBA的算法效率更好.雖然SCPA比NVBA提供了更好的隱私保護和較好的算法效率，但SCPA的查詢代價較之NVBA高，從圖4(d)看出，2種算法的查詢代價均隨著L的增加而增加，因為匿名集中包含了更多的路段.

3) 時空相似性δ的影響.該部分對系統參數時空相似性δ進行實驗評估，以驗證時空相似性δ對SCPA算法的性能的影響.由于NVBA不涉及時空相似性，所以此節僅對SCPA進行了實驗驗證.δ值從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算法在不同時空相似性δ下的性能評估

從圖5(a)和5(b)中，可以看到，在δ取值為0.7之前，信息熵和匿名成功率基本保持不變，但當δ大于0.7后信息熵和匿名成功率都逐漸下降.因為隨著δ值變大，將很難為所有查詢用戶構造具有高時空相似性的匿名集,從而導致用戶的平均信息熵和成功率都呈下降趨勢.圖5(c)顯示，隨著δ的增加，平均匿名時間先增加，在δ值為0.8時達到最大，之后急劇下降.因為隨著時空相似性δ的增加，在為查詢用戶做啟發式寬度優先用戶搜索時，將需要花費更多的時間.然而，當δ值達到一定值時，如0.9時，因系統中大部分查詢用戶難以找到具有如此高相似的匿名用戶集，所以在為用戶生成匿名路段集時將花費相對較少的時間.由圖5(d)中所示，隨著δ的增加，查詢代價逐漸遞減.因為δ越大，表明查詢用戶越相似，匿名用戶在路網上將越集中，所以構造匿名路段集時所產生的開放點個數將相對減少，從而查詢代價變小.

5 結 論

本文研究了一種在道路網絡上基于時空相似性的連續查詢隱私保護算法SCPA.現有在道路網絡上的位置隱私保護工作大多針對快照查詢提供隱私保護，當移動用戶的位置發生連續更新時，容易遭受連續查詢攻擊和位置依賴攻擊.為了解決此問題，本文基于查詢用戶的時空相似性采取分組構造匿名集實現K-共享機制，并提出了一種啟發式的寬度優先用戶搜索算法和連續時刻內匿名路段集生成算法.最后通過一系列實驗，驗證了算法的有效性，匿名算法可保證平均95%以上的匿名成功率，且平均匿名時間為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)(王璐, 孟小峰. 位置大數據隱私保護研究綜述[J]. 軟件學報, 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)(曾志浩, 孫琪, 姚貝, 等. 一種面向連續查詢的虛擬軌跡隱私保護方法[J]. 科學技術與工程, 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年《計算機研究與發展》高被引論文TOP10

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

數據來源：CSCD，中國知網；統計日期：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

國家自然科學基金項目(61303017,61502146)； 河北省自然科學基金項目(F2014210068)； 河北省教育廳青年基金項目(QN2016083)；河北省高等學校人文社會科學研究項目(GH161079)；石家莊鐵道大學第四屆優秀青年科學基金項目(Z661250444)； 河北省研究生創新資助項目(Z99910)；國家級大學生創新創業訓練計劃項目(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