基于Fréchet距離函數(shù)的軌跡隱私保護(hù)方法

張興蘭，楊文金

(1.北京工業(yè)大學(xué)信息學(xué)部，北京 100124； 2.可信計(jì)算北京市重點(diǎn)實(shí)驗(yàn)室，北京 100124)

隨著全球定位系統(tǒng)(global positioning system，GPS)的發(fā)展，基于位置服務(wù)[1](location based services，LBS)的應(yīng)用越來越廣泛，人們通過這些應(yīng)用可以發(fā)現(xiàn)最近的酒店、超市和醫(yī)院等，它們正在改變著信息時(shí)代人們的生活[2-3]. LBS在服務(wù)過程中會(huì)產(chǎn)生大量包含用戶的會(huì)見、位置信息的數(shù)據(jù). 人們可以通過對這些數(shù)據(jù)進(jìn)行挖掘、分析得到許多有用信息以幫助決策，比如：通過分析某區(qū)域內(nèi)用戶的軌跡信息可以發(fā)現(xiàn)用戶感興趣的位置，在這些位置建立商業(yè)圈，能幫助投資者實(shí)現(xiàn)盈利的最大化. 然而，對這些軌跡數(shù)據(jù)進(jìn)行分析，也可以推測出用戶的生活軌跡、健康狀況等隱私信息，如果這些個(gè)人隱私信息被泄露會(huì)對用戶造成極大的威脅[4-8]. 因此，對用戶軌跡隱私信息保護(hù)技術(shù)的研究，已經(jīng)成為信息安全領(lǐng)域研究的重要內(nèi)容之一.

Clarke等[9]提出一種能夠保護(hù)用戶的位置隱私和軌跡隱私的方法. 該方法選擇了多個(gè)特定的合作伙伴來保護(hù)用戶的位置隱私，并且通過構(gòu)建在間隔時(shí)間內(nèi)與用戶的軌跡類似的多個(gè)軌跡來保護(hù)用戶的軌跡隱私. Abul等[10]提出NWA(never walk alone)方法，該方法基于共定位的(k，δ)-匿名模型，將軌跡集合劃分為互不相交的子集，然后通過聚類形成軌跡k-匿名集合. 吳英杰等[11]提出了一種基于聚類雜交的k-匿名隱私保護(hù)技術(shù)，該方法是針對軌跡等價(jià)類特征所提出的，同時(shí)考慮了時(shí)間和空間對軌跡相似性的影響. Shen等[12]提出了一種以用戶為中心的軌跡隱私保護(hù)方法以防止軌跡攻擊. 他們引入位置語義多樣性以最大化軌跡隱私，將攻擊和防御問題轉(zhuǎn)化為貝葉斯 Stackelberg 方式以進(jìn)行定量分析. Gao等[13]提出了一種基于個(gè)性化軌跡隱私圖模型的隱私保護(hù)方法，該方法同時(shí)考慮了時(shí)間、空間和軌跡方向?qū)壽E相似性的影響. 文獻(xiàn)[10-13]中軌跡k-匿名技術(shù)在度量軌跡相似性時(shí)均采用歐幾里得距離函數(shù)，只能度量等長且時(shí)間點(diǎn)一一對應(yīng)的軌跡的距離. 因此，在構(gòu)造同步軌跡集過程中，不等長軌跡轉(zhuǎn)換等長軌跡時(shí)會(huì)有較多軌跡首部和尾部的位置點(diǎn)被刪除，造成較大信息損失.

這些隱私保護(hù)方法一定程度上保護(hù)了軌跡隱私，但是均未考慮軌跡的形狀，另外，未考慮軌跡的速度. 本文提出一種基于Fréchet 距離函數(shù)的軌跡隱私保護(hù)方法，在計(jì)算軌跡間距離的同時(shí)能夠考慮軌跡的形狀，另外，在軌跡方向相似的基礎(chǔ)上考慮軌跡的速度使得軌跡間相似性更高，攻擊者識(shí)別軌跡的難度增加. 最后，通過軌跡圖劃分形成軌跡匿名集合.

1 相關(guān)概念

定義1軌跡. 移動(dòng)對象O的軌跡T為三維時(shí)空坐標(biāo)擬合的曲線，表示為T={Id,(x1,y1,t1,v1),(x2,y2,t2,v2),…,(xm,ym,tm,vm)}. 其中：Id為移動(dòng)對象的身份標(biāo)識(shí)；(xi,yi)為O在i時(shí)刻的位置坐標(biāo)并且t1

定義2[14]同步軌跡. 2條不同的軌跡Tp和Tq，如果Tp和Tq具有相同的時(shí)間序列，那么稱Tp和Tq是同步軌跡；如果軌跡集合中的任意2條軌跡兩兩同步，則稱軌跡集合是同步的.

然而，在實(shí)際環(huán)境中移動(dòng)對象的軌跡往往不是同步的. 主要有2個(gè)原因：一是由于移動(dòng)終端或GPS對每個(gè)移動(dòng)對象位置的采樣時(shí)間不同，二是由于不同移動(dòng)對象向LBS發(fā)送請求服務(wù)的時(shí)間各不相同. 另外，本文在做軌跡處理時(shí)，假設(shè)軌跡在2個(gè)樣本時(shí)間點(diǎn)內(nèi)勻速直線運(yùn)動(dòng)，對于軌跡Tp和Tq間不同時(shí)間坐標(biāo)，通過在軌跡中插入相應(yīng)時(shí)刻的位置坐標(biāo)來實(shí)現(xiàn)軌跡Tp和Tq的同步. 圖1顯示了2個(gè)同步軌跡.

設(shè)二元組(S,d)是一個(gè)度量空間，其中d是S上的度量函數(shù). 在單位區(qū)間[0,1]上的映射γ:[0,1]→S是連續(xù)映射，則稱γ為S上的連續(xù)曲線. 從單位區(qū)間到其自身的映射ζ：[0,1]→[0,1]滿足如下3個(gè)條件：1)ζ是連續(xù)的；2)ζ是非降的，即對于任意x,y∈[0,1]且x≤y，都有ζ(x)≤ζ(y)成立；3)ζ是滿射，則稱函數(shù)ζ為單位區(qū)間[0,1]的重參數(shù)化函數(shù)且此時(shí)有ζ(0)=0,ζ(1)=1. 特別地，當(dāng)ζ為恒等函數(shù)ζ(x)=x時(shí)，稱ζ為平凡重參數(shù)化函數(shù)，否則，稱ζ為非平凡重參數(shù)化函數(shù). 顯然單位區(qū)間的重參數(shù)化函數(shù)有無窮多個(gè).

設(shè)A和B是S上的2條連續(xù)曲線，即A:[0,1]→S,B:[0,1]→S. 又設(shè)α和β是單位區(qū)間的2個(gè)重參數(shù)化函數(shù)，即α:[0,1]→S,β:[0,1]→S，則曲線A和B的Fréchet距離F(A,B)定義為

(1)

式中d是S上的度量函數(shù).

Fréchet距離是法國數(shù)學(xué)家Maurice René Fréchet在1906年提出的一種路徑空間相似形描述，這種描述同時(shí)還考慮了路徑空間距離的因素，對空間路徑的相似性比較適用. 直觀地理解，F(xiàn)réchet距離就是狗繩距離，即主人走路徑A，狗走路徑B，各自走完這2條路徑過程中所需要的最短狗繩長度，如圖2所示.

圖2 狗繩距離Fig.2 Distance of dog and rope

設(shè)P:[0,n]→V是一條曲線，用σ(P)表示曲線上所有的數(shù)據(jù)點(diǎn)，即σ(P)={u1,u2,…,up}.

δdF(P,Q)=min {‖L‖}

(2)

圖3展示了離散化的Fréchet距離.

圖3 離散Fréchet距離Fig.3 Discrete Fréchet distance

定義5軌跡夾角. 軌跡等價(jià)類中2條軌跡Ta={(x1,y1,t1,v1)，(x2,y2,t2,v2)，…，(xn,yn，tn,vn)}和Tb={(x1,y1,t1,v1),(x2,y2,t2,v2),…(xn,yn,tn,vn)}在時(shí)間段[ti,ti+1]內(nèi)的移動(dòng)向量為Ta[i,i+1]和Tb[i,i+1]，那么時(shí)間段[ti,ti+1]內(nèi)的軌跡夾角弦定義為

(3)

則軌跡Ta和Tb的夾角為

(4)

定義7軌跡距離. 設(shè)軌跡Tp={Idp,(x1,y1,t1,v1),…,(xn,yn,tn,vn)}和Tq={Idq,(x1,y2,t1,v1),…,(xn,yn,tn,vn)}的距離為

Distance(Tp,Tq)=F(Tp,Tq)=δdF(P,Q)

(5)

2 基于Fréchet 距離函數(shù)的軌跡匿名方法

本文提出一種基于Fréchet距離函數(shù)的軌跡隱私保護(hù)方法，該方法主要包含以下幾個(gè)方面：1) 軌跡預(yù)處理，對軌跡進(jìn)行預(yù)處理得到軌跡等價(jià)類；2) 計(jì)算軌跡等價(jià)類的Fréchet距離并將其存起來以供構(gòu)建無向圖時(shí)使用，對軌跡等價(jià)類中所有軌跡進(jìn)行遍歷，按照算法3構(gòu)建軌跡圖；3) 利用圖劃分算法對第2步形成的軌跡無向圖進(jìn)行劃分，形成最終的軌跡k-匿名集合.

2.1 軌跡預(yù)處理

軌跡預(yù)處理過程有以下2個(gè)步驟：

1) 選取具有相同開始時(shí)間和結(jié)束時(shí)間的軌跡構(gòu)造軌跡等價(jià)類；針對實(shí)際環(huán)境中的移動(dòng)對象同時(shí)開始并且同時(shí)結(jié)束的數(shù)量非常少，為了減少信息損失率，本文選取一個(gè)給定時(shí)間間隔內(nèi)的軌跡以確保軌跡間的高相似性.

2) 將第一步已經(jīng)選取的軌跡通過軌跡同步化形成軌跡等價(jià)類.

算法1預(yù)處理算法(Pre-process)

輸入：原始軌跡集合Tr.

輸出：軌跡等價(jià)類T′r.

(1)forTxinTr:

(2) if 軌跡的開始、結(jié)束時(shí)間在給定范圍內(nèi)，那么

(3) 將Tx添加到T′r中

(4)for eachTi,Tj∈T′r

(5) fortm∈Ot(Ti,Tj)

(6) iftm∈tiandtm?tj

(7) 將tm時(shí)間點(diǎn)插入Tj中

(8) else 將tm時(shí)間點(diǎn)插入Ti中

(9)返回Tr

2.2 構(gòu)造軌跡無向圖

軌跡間的相似性通過軌跡的夾角和軌跡運(yùn)動(dòng)形狀決定. 軌跡的形狀越相似并且軌跡的夾角越小，軌跡的相似性越高；反之，軌跡的相似性越小. 盡管2條軌跡的夾角很小且形狀相似，但2條軌跡的速度相差很大，目標(biāo)軌跡也很容易被識(shí)別出來；因此，在構(gòu)造軌跡圖階段有2個(gè)步驟：

1) 計(jì)算軌跡間的Fréchet距離，軌跡Fréchet距離通過算法2進(jìn)行計(jì)算.

2) 構(gòu)造軌跡圖，利用軌跡間的夾角和軌跡的平均速度控制軌跡圖的規(guī)模變化.

算法2Fréchet-軌跡距離算法

輸入：軌跡的坐標(biāo)位置P={(x1,y1),…,(xm,ym)},Q={(x1,y1),…,(xm,ym)}.

輸出：δdF(P,Q).

(1)初始化一個(gè)m×m的矩陣C，初始值均為-1

(2)functionC(i,j):

(3) ifC(i,j)>-1，那么返回C(i,j)

(4) else ifi=1 andj=1，那么直接計(jì)算(u1,v1)的距離

(5) else ifi>1 andj=1，那么遞歸計(jì)算C(i-1,1)的值并且C(i,j)為C(i-1,1)和(ui,v1)距離的最大值

(6) else ifi=1 andj>1 遞歸計(jì)算C(i-1,1)，那么C(i,j)為(C(1,j-1),d(u1,vj))的最大值

(7) else ifi>1 andj>1，那么

(8) 遞歸計(jì)算C(i-1,j)，C(i-1,j-1)，C(i,j-1)的值并選擇3個(gè)值中的最小值，然后計(jì)算d(ui,vi)的距離，返回最小值和的最大值

(9) elseC(i,j)=∞

(10) 返回C(m,m)

定義8軌跡圖. 軌跡等價(jià)類Tr={T1,T2,…,Tn}，Tr的軌跡圖G=(V,E,W)是一個(gè)帶權(quán)無向圖，滿足：V是軌跡圖G的頂點(diǎn)集合，?vi∈V都對應(yīng)等價(jià)類中的一條軌跡Ti(1≤i≤n)；E是軌跡圖的邊集，如果軌跡Ti和Tj滿足(s,v)-約束，則頂點(diǎn)vi和vj之間存在一條邊ei,j；W是一個(gè)n階對稱矩陣，?wi,j∈W表示軌跡Ti和Tj的邊權(quán).

定義9軌跡圖邊權(quán). 軌跡圖G={V,E,W}，任意軌跡Tp,Tq∈V，如果邊(Tp,Tq)∈E，那么Tp和Tq的邊權(quán)wp,q為

(6)

式中：β∈[0,1],α+β=1；Distance(Tp,Tq)是軌跡Tp和Tq的Fréchet距離；Min是等價(jià)類的最小距離；Max是軌跡間的最大距離.

本節(jié)給出了軌跡圖的構(gòu)造，其基本思想為：首先任取一條軌跡T1加入到集合V中，剩余軌跡加入集合V′中，任取V′中的一條軌跡T2與V中每一條軌跡判斷它們是否滿足(s,v)-約束，如果滿足則計(jì)算2條軌跡的邊權(quán)，并將T2放入集合V中，將邊(T1,T2)放入邊集E中，從集合V′中刪除T2，重復(fù)此過程直到集合V′為空，具體算法描述如算法3所示. 根據(jù)移動(dòng)軌跡的數(shù)據(jù)可用性和隱私保護(hù)程度的不同，本文提出一種使用方向特征α和距離特征β調(diào)整軌跡圖邊權(quán)的個(gè)性化方法，首先計(jì)算2個(gè)軌跡間的Fréchet距離和夾角，然后根據(jù)定義9計(jì)算軌跡圖邊權(quán).

算法3構(gòu)建軌跡無向圖

輸入：軌跡等價(jià)類Tr={T1,T2,…,Tn}，軌跡夾角約束s，軌跡平均速度約束v，軌跡的距離特征β，軌跡方向特征α.

輸出：軌跡圖G.

(2)Tr←Tr-T1

(3)當(dāng)軌跡等價(jià)類Tr不為空時(shí)

(4)如果軌跡Ti在T中并且與V中所有軌跡Tj滿足(s,v)-約束，那么

(5)計(jì)算軌跡距離Distacnce(Ti,Tj)

(6)Wi,j←Weight(Ti,Tj)=αs+βDistance(Ti,Tj)

(7)E←(Ti,Tj)

(8)V←V+Ti

(9) 從軌跡等價(jià)類Tr中刪除Ti

(10) 否則

(11)V←V+Ti

(12)Tr←Tr-T

2.3 構(gòu)建匿名集合

軌跡k-匿名集合受到軌跡隱私保護(hù)水平和數(shù)據(jù)可用性的影響. 每個(gè)用戶要求至少k-1個(gè)相似用戶，并且形成的匿名區(qū)域足夠小，也就是要求軌跡的相似性s更大，軌跡間的距離F(a,b)足夠小.

定義10合并代價(jià).G1和G2是軌跡圖G的子圖，并且G1和G2交集為空，如果?v∈G1,v′∈G2，邊權(quán)為wv,v′，則合并代價(jià)為Min(wv,v′).

本文將構(gòu)建軌跡k-匿名集合轉(zhuǎn)化為圖劃分問題，其基本思想為：對于頂點(diǎn)數(shù)大于k的軌跡圖，首先選擇權(quán)重最小的邊，將對應(yīng)頂點(diǎn)加入集合V′中；其次，尋找與V′中相關(guān)聯(lián)且權(quán)重最小的頂點(diǎn)加入V′中，重復(fù)此過程直到頂點(diǎn)小于k；對于頂點(diǎn)小于k的軌跡圖，將其并入合并代價(jià)最小的匿名集合. 具體如算法4所示.

算法4軌跡匿名算法

輸入：軌跡圖G=(V,E,W).

輸出：匿名集合T″r.

(1)T″r=φ,V′=φ,w=φ

(2)MinWeight=W0,1,r=0,s=1

(3)選擇開始點(diǎn)，在軌跡圖中尋找邊權(quán)最小的頂點(diǎn)Vi,Vj，V′={Vi,Vj}

(4)對V′中每個(gè)頂點(diǎn)v尋找所有與v關(guān)聯(lián)的頂點(diǎn)，選擇最小權(quán)值的頂點(diǎn)加入V′，重復(fù)此過程直到V′中的頂點(diǎn)數(shù)大于等于k

(5)重復(fù)步驟4直到軌跡圖所含頂點(diǎn)個(gè)數(shù)小于k

(6)將頂點(diǎn)數(shù)小于k的集合并入合并代價(jià)最小的匿名集合

(7)返回匿名軌跡T″r={V′1,…,V′m}

3 軌跡隱私水平和數(shù)據(jù)可用性

本文所得到的匿名集合的基本思想為：首先，對原始數(shù)據(jù)進(jìn)行軌跡預(yù)處理得到軌跡等價(jià)類；其次，將軌跡等價(jià)類轉(zhuǎn)化為軌跡圖；最后，通過軌跡圖的劃分得到相應(yīng)的匿名集合. 軌跡的相關(guān)性依賴于權(quán)值數(shù)，即軌跡圖的邊權(quán)，軌跡的權(quán)值函數(shù)包含軌跡隱私和數(shù)據(jù)可用性. 本文從2個(gè)方面分析算法有效性，一是k-匿名的隱私保護(hù)程度，二是分析軌跡的信息損失率.

3.1 隱私水平

軌跡隱私保護(hù)主要通過攻擊者從軌跡發(fā)布數(shù)據(jù)庫中識(shí)別一個(gè)軌跡的概率來衡量. 本文構(gòu)建的軌跡匿名集合通過軌跡圖的劃分構(gòu)建，考慮到不同的隱私保護(hù)程度和數(shù)據(jù)可用性，提出了一個(gè)不同的構(gòu)建軌跡k-匿名集合方法. 在計(jì)算軌跡距離時(shí)，采用一種考慮軌跡形狀的Fréchet距離公式來計(jì)算，并且軌跡之間要求滿足(s,v)-約束.

軌跡被重新識(shí)別的概率即為軌跡的隱私保護(hù)水平，是攻擊者能夠從軌跡發(fā)布數(shù)據(jù)庫中區(qū)分軌跡信息點(diǎn)或者軌跡的概率. 本文通過分析軌跡間相關(guān)性來衡量軌跡的隱私保護(hù)水平，即分析軌跡間的相似性. 假設(shè)構(gòu)造的k-匿名集合為T={T′1,T′2,…,T′k}，并且每個(gè)軌跡滿足定義1. 用軌跡匿名集合平均相似性Savg表示軌跡k-匿名集合的相似性，軌跡相似度Savg計(jì)算公式為

(7)

軌跡的隱私保護(hù)水平采用所有匿名集合的平均值表示，即

(8)

式中p表示形成的匿名集合個(gè)數(shù).

3.2 信息損失率

在計(jì)算信息損失率時(shí)，僅僅考慮構(gòu)建軌跡匿名集合時(shí)造成的信息損失，不考慮軌跡預(yù)處理的信息損失. 本文通過軌跡的匿名區(qū)域與整個(gè)軌跡空間區(qū)域面積的比值來衡量信息損失，軌跡匿名區(qū)域與數(shù)據(jù)可用性成反比，匿名區(qū)域面積越大數(shù)據(jù)可用性越小，反之?dāng)?shù)據(jù)可用性越大，表示為

(9)

式中：Area(xji,yji,tj)為tj時(shí)刻的匿名區(qū)域面積；MaxAreai為第i個(gè)匿名集合的最大面積；p為匿名集合的個(gè)數(shù).

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

本文從2個(gè)方面分析算法的可行性和有效性，一是隱私保護(hù)水平，二是信息損失率. 把本文提出的基于Fréchet 距離函數(shù)的匿名算法和NWA[10]匿名算法以及將本文計(jì)算軌跡距離換成歐式距離進(jìn)行對比實(shí)驗(yàn).

4.1 實(shí)驗(yàn)環(huán)境和數(shù)據(jù)

本文的實(shí)驗(yàn)環(huán)境為Inter(R) Core(TM) i5- 4590 CPU @3.30 GHz；8 GB內(nèi)存；Microsoft Windows 7.sp. 64位操作系統(tǒng)；本算法在pycharm中實(shí)現(xiàn).

實(shí)驗(yàn)中使用的實(shí)驗(yàn)數(shù)據(jù)集是由Brinkhoff生成器基于德國奧爾登堡市交通地圖生成的[16]，初始數(shù)據(jù)集如表1所示. 第1列表示移動(dòng)對象的編號；第2列是移動(dòng)對象位置編號，即表示該點(diǎn)是軌跡的第幾個(gè)位置；第3列表示數(shù)據(jù)返回的概率，0表示以百分百的概率生成數(shù)據(jù)點(diǎn)；第4列表示軌跡所處的時(shí)間；第5、6列表示軌跡所處的位置信息；第7列表示軌跡的當(dāng)前速度；最后2列表示軌跡下一時(shí)刻將要到達(dá)的位置.

表1 部分?jǐn)?shù)據(jù)

4.2 隱私保護(hù)水平

圖4反映了在方向參數(shù)α=0.2和數(shù)據(jù)可用性參數(shù)β=0.8時(shí),本文使用基于Fréchet 距離函數(shù)的軌跡匿名算法和基于歐氏距離的方法及NWA軌跡匿名算法的比較. 從圖中可以看出，隨著k值的增大軌跡的相似程度會(huì)逐漸變小，即隱私保護(hù)水平隨之下降；基于Fréchet 距離函數(shù)的軌跡匿名算法要比NWA[10]軌跡匿名算法和基于歐氏距離的匿名算法所形成的軌跡匿名集合的相似度更高，即軌跡的隱私保護(hù)水平更高. 這是因?yàn)樵跇?gòu)建匿名集合時(shí)不僅考慮軌跡的運(yùn)動(dòng)方向相近，同時(shí)它們的平均速度也必須相近，這就增加了構(gòu)建的匿名集合之間的相似性，另外，F(xiàn)réchet 距離函數(shù)在計(jì)算軌跡距離時(shí)考慮軌跡的形狀使得軌跡間的相似性比其他方式構(gòu)造的更高.

圖4 不同方法的隱私保護(hù)水平Fig.4 Privacy protection level of different methods

4.3 信息損失

在方向約束參數(shù)α=0.2和數(shù)據(jù)可用性參數(shù)β=0.8的約束下不同方法的信息損失比較如圖5所示. 從圖中可以看出，隨著k值的逐漸增大，信息損失越來越大，但本文提出的算法信息損失略低于另外2種方法. 因?yàn)橄啾扔贜WA算法和采用歐氏距離度量軌跡距離的方法，本文基于Fréchet算法和(s,v)-約束將軌跡速度和運(yùn)動(dòng)方向、軌跡形狀相似的軌跡匿名到一個(gè)集合，因此，產(chǎn)生的信息損失較小，數(shù)據(jù)利用率增大. 從實(shí)驗(yàn)中得出，本文提出的方法最大信息損失約為26%，而另2種方法最大信息損失約為34%，信息損失降低約為8%.

圖5 不同方法對應(yīng)的信息損失Fig.5 Information loss corresponding to different methods

圖6顯示了方向約束參數(shù)α和數(shù)據(jù)利用率參數(shù)β分別為(1.0,0)、(0.2,0.8)、(0.8,0.2)、(0,1.0)時(shí)本文提出算法的信息損失比較. 從圖中可以看出，對于4種不同的(α,β)參數(shù)，軌跡匿名之后的數(shù)據(jù)信息損失并不完全相同，但是當(dāng)β≠0時(shí)，不同k信息損失率相差并不大，這是因?yàn)楸疚乃惴ㄋ捎玫木嚯x計(jì)算函數(shù)在計(jì)算距離時(shí)考慮了軌跡的形狀，增加了軌跡的相似性，所以相差不大. 當(dāng)僅考慮軌跡的隱私保護(hù)時(shí)，軌跡間更為相似，但是軌跡間距離變得更大，導(dǎo)致匿名區(qū)域變大，因此，信息損失較大. 另外，從圖中也可以看出，隨著k增大，信息損失也越來越大.

圖6 不同(α,β)的信息損失率Fig.6 Information loss rates of different (α,β)

4.4 算法運(yùn)行效率分析

圖7為不同隱私保護(hù)參數(shù)α和數(shù)據(jù)利用率參數(shù)β分別在(0,1.0)、(0.4,0.6)、(0.7,0.3)、(1.0,0)四種情況下本文提出算法的運(yùn)行時(shí)間比較. 從圖7可以清晰地看出，在這4種情況下算法的運(yùn)行時(shí)間基本相同，并且隨著k值的增加而增加. 因?yàn)樵谶@4種參數(shù)下，算法構(gòu)造軌跡圖的權(quán)重雖然不同，但是匿名集合的規(guī)模基本相同，故算法的運(yùn)行時(shí)間大致相同. 另外，隨著k值的增加匿名集合的規(guī)模變大，需要更多時(shí)間找到k條相似的軌跡，因此，算法的運(yùn)行時(shí)間隨著k值增加而增加.

圖7 不同參數(shù)執(zhí)行效率比較Fig.7 Execution efficiency of different parameters

圖8為隱私保護(hù)參數(shù)和數(shù)據(jù)利用率取(0.3,0.7)時(shí)本文提出的算法和其他2種算法的執(zhí)行效率比較. 從圖中可以看出，幾種方法的運(yùn)行時(shí)間隨著k值的增加而增加，這是由于隨著k值增大，需要更多的時(shí)間尋找滿足隱私需求的軌跡. 本文提出的算法綜合考慮軌跡的夾角、距離、速度、形狀等因素，同時(shí)設(shè)置了隱私保護(hù)參數(shù)，在構(gòu)建匿名集合時(shí)約束條件更多，故運(yùn)行時(shí)間相比其他算法稍長. 但在實(shí)際應(yīng)用中，本文提出的方法能夠提供較高的隱私保護(hù)和較好的數(shù)據(jù)利用，隨著計(jì)算機(jī)硬件設(shè)備性能的不斷增強(qiáng)，算法略高的開銷是可以被接受的.

圖8 不同方法的運(yùn)行時(shí)間Fig.8 Different methods of run times

5 結(jié)論

1) 基于Fréchet距離函數(shù)的軌跡隱私保護(hù)方法，在數(shù)據(jù)可用性和隱私保護(hù)程度方面都有所提高，雖然算法開銷略高，但是，由于現(xiàn)在設(shè)備的性能高，算法開銷仍可接受.

2) 利用圖劃分思想構(gòu)建軌跡匿名集合，通過設(shè)定參數(shù)α和β的值能夠更好地調(diào)節(jié)軌跡圖的邊權(quán)來實(shí)現(xiàn)隱私保護(hù)和數(shù)據(jù)可用性的動(dòng)態(tài)平衡.

3) 提出的(s,v)-約束使得軌跡在運(yùn)行方向相似，同時(shí)各個(gè)軌跡的速度也相近，從而使得攻擊者更難識(shí)別軌跡，提高了軌跡隱私保護(hù)程度.