改進螢火蟲群算法協(xié)同差分隱私的干擾軌跡發(fā)布

彭 鵬，倪志偉，朱旭輝，陳 千

（1.合肥工業(yè)大學(xué) 管理學(xué)院，合肥 230009；2.北方民族大學(xué) 商學(xué)院，銀川 750021；3.過程優(yōu)化與智能決策教育部重點實驗室（合肥工業(yè)大學(xué)），合肥 230009）

0 引言

隨著互聯(lián)網(wǎng)、全球定位系統(tǒng)（Global Positioning System，GPS）和智能設(shè)備的廣泛應(yīng)用，用戶通過提交位置及需求等信息，可以獲得基于位置的服務(wù)（Location-Based Services，LBS）［1］。在LBS 不斷發(fā)展下，眾包應(yīng)用也逐漸發(fā)展和拓展，產(chǎn)生了大量的空間眾包應(yīng)用［2］，如導(dǎo)航軟件、美團外賣APP、滴滴快車APP 等。用戶不間斷上傳位置數(shù)據(jù)，軟件及服務(wù)器獲取大量數(shù)據(jù)，這些序列化的時間、位置數(shù)據(jù)即軌跡數(shù)據(jù)［3］。發(fā)布及分析軌跡數(shù)據(jù)對市政規(guī)劃、交通管理和應(yīng)急預(yù)案等優(yōu)化配置具有重要價值。軌跡數(shù)據(jù)包含用戶隱私的個人信息，根據(jù)某一用戶軌跡的起點、終點和經(jīng)常停留的位置等信息可能得到用戶的家庭住址、單位住址和興趣愛好。文獻［4］中記錄了15 個基于位置的應(yīng)用都出現(xiàn)了泄露位置信息的情況，所以軌跡數(shù)據(jù)發(fā)布亟須可靠的保護機制。

軌跡數(shù)據(jù)保護機制的研究，除了考慮軌跡的數(shù)據(jù)安全外，還需考慮以下3 方面問題：

1）軌跡可用性的綜合評價。現(xiàn)有文獻通常用距離誤差衡量軌跡可用性［3］，平均距離誤差越小，軌跡可用性越高。如圖1 所示，真實軌跡共生產(chǎn)兩條干擾軌跡，雖然軌跡2 和真實軌跡的平均距離小于軌跡1 和真實軌跡的平均距離，但軌跡2 與真實軌跡的相似性更低。相似性也會影響軌跡的可用性。此外，干擾軌跡2 與原始軌跡反復(fù)交叉，這會讓攻擊者采用濾波等手段過濾異常，增加數(shù)據(jù)泄露的風(fēng)險［5］。

圖1 不同的干擾軌跡Fig.1 Different interference tracks

2）軌跡的復(fù)雜度。假設(shè)時間戳B1 和B2 為同等時間，但軌跡復(fù)雜程度明顯不同。在實際應(yīng)用中，軌跡通常被作為一個位置與時間對應(yīng)的有序離散數(shù)據(jù)集［3］，因此根據(jù)軌跡復(fù)雜度，適當(dāng)增減離散點，提取更多的特征點［6］，有利于描繪更準確的軌跡。

3）生成兼顧距離誤差及相似性的干擾軌跡的方法。在加噪發(fā)布干擾軌跡時，干擾軌跡由各干擾點連接生成，任何一個干擾點的有效性都會影響干擾軌跡的可用性。假設(shè)某條軌跡離散為M個時刻的點，某個位置點泛化和加噪后得到N個位置不同的點，則共有NM種組合［7］。如何得到可用性較高的干擾軌跡，屬于NP-Hard 問題。

基于以上問題，本文針對歷史軌跡數(shù)據(jù)發(fā)布問題，采用中心化差分隱私，建立k-匿名融合差分隱私的加密模型。通過提取顯著特征點，構(gòu)建加權(quán)距離評估目標，引入改進的螢火蟲群優(yōu)化（Improved Glowworm Swarm Optimization，IGSO）算法，實現(xiàn)軌跡數(shù)據(jù)先約簡后泛化，再進行差分隱私加噪的基于IGSO算法尋優(yōu)求解的干擾軌跡發(fā)布保護（Trajectory Protection of Simplification and Differential privacy of the track data based on IGSO，IGSO-SDTP）機制。本文的主要工作如下：

1）構(gòu)建新的軌跡可用性評估指標——加權(quán)距離。加權(quán)距離同時考慮兩條軌跡的相似度和距離誤差，進一步提升生成的干擾軌跡的可用性和安全性。

2）提取顯著位置點并簡化軌跡點集。軌跡數(shù)據(jù)集中并不是每個軌跡點都具有相同的影響，因此本文提取特征點，減少非特征點數(shù)，簡化軌跡點集，從而提高生成干擾軌跡的準確性和效率。

3）通過k-匿名泛化結(jié)合差分隱私的加噪方式生成滿足差分隱私的位置點數(shù)據(jù)集，通過改進離散螢火蟲群優(yōu)化算法，以加權(quán)距離為目標函數(shù)，計算生成可用性高且安全的干擾軌跡。

4）在Geolife 數(shù)據(jù)集上通過實驗驗證IGSO-SDTP 方法在生成干擾軌跡中的有效性，并對參數(shù)進行相關(guān)實驗。

1 相關(guān)工作

1.1 干擾軌跡發(fā)布

軌跡隱私保護和發(fā)布研究根據(jù)應(yīng)用場景不同主要分為歷史軌跡［3，8-9］和實時軌跡的發(fā)布［10-11］。實時軌跡數(shù)據(jù)發(fā)布一般用于各類基于位置服務(wù)的軟件；歷史軌跡數(shù)據(jù)發(fā)布一般用于市政、公司的數(shù)據(jù)挖掘和分析，對調(diào)整行業(yè)未來規(guī)劃、資源優(yōu)化配置具有重要意義。文獻［3］中利用Hilbert 曲線提取軌跡分布特征，并結(jié)合個性化隱私需求，對歷史軌跡生成發(fā)布軌跡數(shù)據(jù)；文獻［8］中通過離散化軌跡生成多粒度系統(tǒng)，并構(gòu)建前綴樹和采用權(quán)重進行發(fā)布，提高歷史軌跡數(shù)據(jù)可用性；文獻［9］中提出多層次前綴樹，用不同層次網(wǎng)絡(luò)結(jié)構(gòu)呈現(xiàn)具有不同速度特性的軌跡，提高歷史軌跡可用性。實時軌跡數(shù)據(jù)隱私保護通常使用馬爾可夫鏈、本地化差分隱私等技術(shù)。文獻［10］中用馬爾可夫鏈表示位置時序關(guān)系，提出基于凸包的差分隱私機制，保護了當(dāng)前實時位置的隱私；文獻［11］中基于本地差分隱私，基于真實位置生成攻擊者推測的最有可能存在的位置集合，并重新定義敏感度可對軌跡發(fā)布進行實時保護。軌跡隱私保護和發(fā)布研究根據(jù)數(shù)據(jù)源類別，分為單源數(shù)據(jù)軌跡發(fā)布和多源數(shù)據(jù)軌跡發(fā)布：單源數(shù)據(jù)軌跡發(fā)布主要使用中心化差分隱私［3］和k-匿名［12］；多源數(shù)據(jù)軌跡發(fā)布因為有多個數(shù)據(jù)來源，通常使用本地化差分隱私［11］在每個數(shù)據(jù)差分隱私保護后，再統(tǒng)一發(fā)給第三方發(fā)布，防止第三方攻擊。

1.2 k-匿名和差分隱私

針對LBS 中的位置和軌跡隱私信息，吳云乘等［13］提出了不同隱私保護方法，最常用的是泛化和擾亂：泛化指將某個敏感位置替換成一個區(qū)域或者多個位置，最常用的是k-匿名；擾亂指通過添加噪聲將真實位置生成假的位置進行替換，差分隱私是近年來廣泛使用的擾亂方法。

k-匿名將真實信息替換成包含k個用戶的空間信息，用戶的真實信息與其他k-1 個用戶不可區(qū)分［12］。文獻［14-15］中分別通過軌跡分割、位置點擾動的方式模糊化軌跡中的用戶真實特征，滿足k-匿名。面對前景知識攻擊、組合攻擊等具備背景知識的攻擊者時，k-匿名模型會失去保護作用，差分隱私［7］能夠很好地解決上述問題。

差分隱私一般分為中心化差分隱私［3，16］和本地化差分隱私［17］：中心化差分隱私基于存在可信的第三方服務(wù)器存儲敏感數(shù)據(jù)，經(jīng)差分隱私加噪后，功能服務(wù)器獲取并使用加噪數(shù)據(jù)集；本地化差分隱私指用戶實時上傳加噪的位置點數(shù)據(jù)，用戶和服務(wù)器間傳輸?shù)募釉胲壽E數(shù)據(jù)實時交互。差分隱私由Dwork 等［18］提出，具有嚴格的數(shù)學(xué)定義和證明，主要過程是對原始查詢結(jié)果添加隨機噪聲，攻擊者即使掌握一定背景知識，也無法識別添加或刪除一條記錄帶來的影響，從而很難推導(dǎo)出某條真實信息。許多學(xué)者結(jié)合差分隱私研究了不同場景下軌跡數(shù)據(jù)的隱私保護方法。文獻［16］中通過時間泛化和空間分割的采樣模型，使用隱私保護對軌跡數(shù)據(jù)進行雙重擾動，從而保證發(fā)布軌跡數(shù)據(jù)的精度；文獻［17］中對連續(xù)數(shù)值型數(shù)據(jù)進行劃分變換和分段，根據(jù)分段轉(zhuǎn)化為二元分類數(shù)據(jù)并進行差分隱私加噪。

k-匿名的實質(zhì)是增加干擾位置，差分隱私是對現(xiàn)有數(shù)據(jù)進行不規(guī)則的擾動，兩者并不沖突，有機結(jié)合會加強隱私保護的作用。如文獻［19］中設(shè)計了一種Laplace 機制和k-匿名相結(jié)合的軌跡保護算法，對用戶真實位置進行多輪加噪生成匿名組，用匿名組獲取LBS 服務(wù)，增強了軌跡隱私保護效果。文獻［20］中結(jié)合k-匿名和本地差分隱私，對k-匿名集中的候選位置進行擾動，在保證性能的同時降低了攻擊者獲取用戶信息的概率。與本文方法相比，文獻［19-20］都結(jié)合差分隱私和k-匿名進行加密，但文獻［19］中用多輪加噪生成的匿名組獲取LBS 服務(wù)，消耗隱私預(yù)算較大，且任務(wù)分配效用較低；文獻［20］中的方法雖用于位置加密，但使用本地差分隱私，加密方法不同，且如果不對數(shù)據(jù)預(yù)處理，直接應(yīng)用于空間眾包任務(wù)分配，會顯著增加位置的噪聲，最終降低任務(wù)分配的效用。

1.3 螢火蟲群優(yōu)化算法

近年來，螢火蟲群優(yōu)化（Glowworm Swarm Optimization，GSO）算法［21］被廣泛應(yīng)用于解決調(diào)度、旅行商問題等組合問題。GSO 算法是受螢火蟲群體之間智能協(xié)作啟發(fā)的算法，相較于粒子群算法、蟻群算法等，具有運算較快、有較強尋優(yōu)能力的優(yōu)點，但算法收斂速度和全局尋優(yōu)能力有待進一步提升。通過初始化、變步長、離散化和改變移動策略等方式［22-24］可進一步優(yōu)化算法性能，推廣應(yīng)用范圍。

2 理論知識

2.1 軌跡可用性評估

一條軌跡是位置與對應(yīng)時間的有序數(shù)據(jù)集列表，通常表示為T=(l1，t1) →(l2，t2) →… →(ln，tn)。其中：位置li表示離散點，用經(jīng)緯度表示；ti是位置li對應(yīng)的時刻。本文將誤差距離以及軌跡相似性兩個方面都作為軌跡可用性的評估。

假設(shè)某真實軌跡T某時刻t的真實位置為lt，發(fā)布軌跡T'對應(yīng)時刻位置為rt，軌跡共有n個點，距離誤差（Distance Error，DE）為距離均方根總和［3］，如式（1）所示：

Frechet 距離離散化的計算方式［25］如式（2）所示，常用于衡量兩條軌跡的相似性，距離越小表示軌跡越相似，距離越大表示越不相似。

其中：T、T'表示兩條軌跡；d(T(i(t))，T'(j(t)))表示兩個采樣點在時刻t的歐氏距離；infi，j，t∈[0，1]表示曲線i和曲線j之間距離最大值的下界值。每次采樣時，t離散地遍歷［0，1］，得到最大距離max{d(T(i(t))，T'(j(t)))}，即Frechet 距離。

2.2 k-匿名

定義1k-匿名。原始數(shù)據(jù)集T，泛化后的數(shù)據(jù)集T'。若T中的任意數(shù)據(jù)li在T'對應(yīng)的數(shù)據(jù)中均有不少于k個近似的數(shù)據(jù)，則稱T滿足k-匿名［13］。

2.3 差分隱私

差分隱私具體如定義2［20］，主要性質(zhì)包括全局敏感度［26］、序列組合性［26］、并行組合性［27］、Laplace 噪聲機制［28］和指數(shù)噪聲機制［28］等。本文將相關(guān)的部分性質(zhì)介紹如下。

定義2ε-差分隱私（ε-DP）。給定相鄰數(shù)據(jù)集T和T'及一個算法A。若算法A 在T和T'的任意輸出O滿足式（4），則算法A 滿足差分隱私。

其中：參數(shù)εt表示t時刻的差分隱私預(yù)算，εt越大，噪聲越小，隱私保護程度越小；反之則隱私保護程度越大。

定義3全局敏感度。對查詢函數(shù)f：T→Td，Δf=則稱Δf為函數(shù)f的全局敏感度。全局敏感度與數(shù)據(jù)集T無關(guān)，只與查詢函數(shù)f有關(guān)。

定義4并行組合性。將一個數(shù)據(jù)集T分成n個互不相交的集合{T1，T2，…，Tn}，每個集合依次對應(yīng)隨機算法，任意Ai均符合εi-DP，則{A1，A2，…，An}在T上的并列序列組合滿足(maxεi)-DP。

Laplace 噪聲機制是差分隱私的噪聲機制之一，向返回的結(jié)果加入符合拉普拉斯函數(shù)分布的隨機噪聲。Laplace 函數(shù)為式（5）：

在差分隱私中，通常令μ=0，b=Δf/ε，此時Laplace 函數(shù)記為式（6）：

定理1對任意函數(shù)f：T→Td，若隨機算法A 的輸出結(jié)果滿足式（7），則稱算法A 滿足ε-DP。

Lap(Δf/ε)是添加的Laplace 噪聲，噪聲與全局敏感度成正比，與ε成反比。

2.4 顯著點判斷

結(jié)合文獻［6］中道路拐角顯著性的判斷方法，對軌跡所有離散點，結(jié)合式（8）判斷如下：

假設(shè)某位置點li的前一點和后一點構(gòu)成的基線Lb，a長度為Len(b，a)，位置點li到Lb，a垂直距離為h（如果垂足不在基線Lb，a內(nèi)，則以Len(li，a)和Len(li，b)中較小者為準）。設(shè)置閾值g（c常數(shù)），若g>gc，則稱該位置點顯著，簡化軌跡數(shù)據(jù)集時應(yīng)予以保留；否則可以忽略。

2.5 螢火蟲群優(yōu)化算法

螢火蟲群優(yōu)化算法步驟依次是熒光素更新、選擇移動方向、位置更新和決策域更新等階段［21］，具體步驟如下：

其中：li(t)是熒光素值；ρ是螢火素揮發(fā)系數(shù)；γ、J(xi(t))分別指增強系數(shù)和第t次迭代的目標函數(shù)值；Ni(t)是螢火蟲xi在第t次迭代時比它更亮的螢火蟲集合；ρij(t)指當(dāng)前螢火蟲xi移向更亮螢火蟲xj的概率；s是步長，β為感知半徑系數(shù)；nt為鄰域螢火蟲數(shù)量閾值；rs為鄰域感知半徑，(t)表示第i只螢火蟲t時刻的動態(tài)決策范圍。

3 方案設(shè)計

3.1 主要符號

本文符號主要包含兩部分：第一部分包含軌跡數(shù)據(jù)、k-匿名、差分隱私加噪、提取顯著點和數(shù)據(jù)評估等軌跡數(shù)據(jù)處理各環(huán)節(jié)的符號；第二部分包含螢火蟲群優(yōu)化算法及IGSO 算法運行的相關(guān)參數(shù)符號。主要參數(shù)及含義介紹見表1，算法相關(guān)參數(shù)見2.5 節(jié)和3.2 節(jié)。

表1 軌跡加噪的主要符號及含義Tab.1 Main symbols and meanings for adding noise to trajectory

3.2 IGSO-SDTP整體思路

IGSO-SDTP 具體過程如圖2，分為IGSO 和SDTP 兩部分，通過算法目標函數(shù)和螢火蟲熒光素關(guān)聯(lián)。目標函數(shù)考慮了誤差距離和軌跡相似性兩個方面的影響因素。

圖2 IGSO-SDTP方法框架Fig.2 Framework of IGSO-SDTP method

1）IGSO-SDTP 方法步驟。

在軌跡數(shù)據(jù)的處理過程中，首先對軌跡數(shù)據(jù)集進行預(yù)處理。預(yù)處理方法是將經(jīng)緯度位置坐標轉(zhuǎn)化成直角坐標系坐標，再通過映射，轉(zhuǎn)化到指定的數(shù)字區(qū)間。然后，運用式（8）判斷軌跡數(shù)據(jù)集中的顯著點和非顯著點，進一步簡化軌跡數(shù)據(jù)集；在k-匿名泛化時，按照式（3）要求，將簡化后軌跡數(shù)據(jù)集生成具體k個近似數(shù)據(jù)的等價數(shù)據(jù)集，再利用差分隱私進行加噪；以軌跡可用性評估指標為目標函數(shù)，利用IGSO 算法從加噪后的數(shù)據(jù)集中尋找位置點的最優(yōu)組合；最后，進行解碼，發(fā)布尋找到的較優(yōu)干擾軌跡。

2）IGSO 算法的目標函數(shù)。

目標函數(shù)構(gòu)建如式（14）所示，通過構(gòu)建加權(quán)線性函數(shù)將多目標問題轉(zhuǎn)為單目標問題再求解。

其中：式（15）表示目標函數(shù)的約束條件；sei表示螢火蟲選擇的各個離散位置點的編號組合，每個點均是從1～k泛化數(shù)據(jù)集中對應(yīng)時刻任意選中的一點；SEi表示對一條軌跡通過k-匿名泛化和差分隱私加噪后的數(shù)據(jù)集，通過螢火蟲群優(yōu)化算法對數(shù)據(jù)集n個離散點選擇的編號集合；r1、r2為誤差距離和軌跡相似度的權(quán)重系數(shù)，體現(xiàn)重要程度。其他相關(guān)公式和符號含義詳見第2 章和第4 章。

3.3 改進螢火蟲群優(yōu)化算法

螢火蟲群優(yōu)化算法主要用于連續(xù)解空間問題，對于組合應(yīng)用問題，要在初始解和移動策略方面進行離散化處理［29］。

1）編碼和解碼。

假設(shè)一條軌跡共有5 個位置點，每個點k-匿名泛化和差分隱私加噪后都分別產(chǎn)生4 個點。假設(shè)螢火蟲每個維度與位置點依次對應(yīng)，每個維度上的數(shù)字表示選擇該位置點4 個點中的第幾號點。xi={2，3，4，2，1}表示該干擾軌跡的第1個位置點選擇的是泛化加噪后數(shù)據(jù)集對應(yīng)位置上的第2 號點，第2 個位置點選擇的3 號點，依此類推進行編碼和解碼。

2）反向?qū)W習(xí)協(xié)同初始化。

反向?qū)W習(xí)是根據(jù)反向數(shù)生成反向解的優(yōu)化方法［30］。設(shè)R上d維離散點xd=[m，n]，d1∈{1，2，…，d}，則x在d1維的反向數(shù)定義為：

反向?qū)W習(xí)協(xié)同初始化是指在初始化種群基礎(chǔ)上，利用反向?qū)W習(xí)獲得另一組種群。根據(jù)對應(yīng)目標函數(shù)，將兩組種群的目標函數(shù)降序。在每組目標函數(shù)中分別選擇較好一半的解空間對應(yīng)的子種群，協(xié)同混合生成一組質(zhì)量較好的初始化種群。

3）距離計算。

因為解空間是離散編碼，故不能用原有步長計算方式。螢火蟲i和螢火蟲j在d維上的距離及總距離用海明距離計算，d∈[1，m]，如式（17）～（18）：

4）移動策略。

在隨機概率（rand）小于等于變異因子p時，螢火蟲i利用輪盤賭方式尋優(yōu)。假設(shè)螢火蟲j在第g維上優(yōu)于螢火蟲i，則參照式（11）的概率被該值替代。為了增加螢火蟲的移動，當(dāng)隨機概率大于變異因子p時，引入前期工作中自適應(yīng)的4 種移動策略（Four Adaptive Mobile strategies，AM4）［7］，可避免算法過早過快陷入局部最優(yōu)，加強算法在多維空間的尋優(yōu)能力。具體移動策略見式（19）：

3.4 算法偽代碼描述

算法1 主要是對軌跡數(shù)據(jù)集的處理，核心是3 個步驟，先約簡再泛化后加噪，詳見圖2 的SDTP 部分；算法2 主要是在處理后的數(shù)據(jù)集中根據(jù)目標函數(shù)尋找符合要求的干擾軌跡，詳見圖2 的IGSO 部分。

算法1 軌跡約簡的隱私保護算法。

輸入 原始軌跡數(shù)據(jù)T；

3.5 算法的時間復(fù)雜度

設(shè)種群規(guī)模為m，某條軌跡位置點n個，匿名泛化加噪后每個位置點生成k個點，每只螢火蟲（n維）代表一組位置點自由組合，最大迭代數(shù)為tmax。

初始化螢火蟲種群時間復(fù)雜度為O（m），計算一條軌跡組合的時間復(fù)雜度為O（nk），故每次迭代總時間復(fù)雜度為O（mnk）；計算螢火蟲個體間距離的時間復(fù)雜度為O（n）；每次迭代中計算螢火蟲個體移動的時間復(fù)雜度為O（n2）；每次迭代中計算螢火蟲種群位置更新的時間復(fù)雜度為O(mn2)；因此IGSO 算法的計算時間復(fù)雜度為O（mn2tmax）（一般n>k）。

3.6 隱私保護分析

定理2在KT數(shù)據(jù)集加噪得到KT'過程中，IGSO-SDTP符合ε-差分隱私。

由于IGSO-SDTP 作用在KT'數(shù)據(jù)集上，T'是所有時間序列上對應(yīng)位置的泛化數(shù)據(jù)集上的任意一點，所以T'是KT'的子集，符合差分隱私保護。此外，每一位置點是先進行k-匿名泛化，再進行整體差分隱私加噪處理，所以有更好的安全性。

4 實驗與結(jié)果分析

4.1 數(shù)據(jù)和實驗說明

實驗環(huán)境為：Intel i5-10400F 2.9 GHz，16 GB 內(nèi)存，Windows 10 操作系統(tǒng)，算法在Matlab 2016 運行，軌跡繪圖使用OziExplorer 軟件。本文采用Geolife 數(shù)據(jù)集［31］進行實驗，該數(shù)據(jù)集收集了182 個用戶從2007 至2012 年的17 621 個軌跡數(shù)據(jù)，包含時間為序的位置點集的經(jīng)緯度信息。

在Geolife 抽取了6 條軌跡數(shù)據(jù)Geo1～Geo6 作為研究案例的具體數(shù)據(jù)。它們的軌跡形態(tài)、復(fù)雜程度和位置點數(shù)均不相同，6 條軌跡形態(tài)差異較大，圖3 是Geo1～Geo6 軌跡數(shù)據(jù)集生成的軌跡圖。其中：Geo1、Geo2、Geo4 軌跡整體運動方向是由西向東；Geo3 是由西南向東北；Geo5 是先由北向南，再由西向東；Geo6 是先由西向東，再由北向南。Geo1、Geo2 彎曲較多，軌跡曲線較復(fù)雜；Geo4～Geo6 適中；Geo3 大部分軌跡呈直線，復(fù)雜程度最簡單。

圖3 Geo1～Geo6的軌跡形態(tài)Fig.3 Trajectories of Geo1～Geo6

因此，在利用顯著點約簡和設(shè)置判斷顯著點的閾值時，Geo3 采用閾值0.05，其他軌跡均使用閾值0.1，相關(guān)數(shù)據(jù)見表2。

表2 軌跡數(shù)據(jù)的約簡Tab.2 Reduction of track data

本文共對比了5 種軌跡進行差分隱私加噪發(fā)布的方法，具體如下：

1）RD（Differential privacy for Raw trajectory data）：將原始軌跡直接進行差分隱私加噪并進行軌跡發(fā)布。

2）LIC（Linear Index Clustering algorithm）［3］：利用Hilbert曲線提取軌跡分布特征并利用位置代表元對原始軌跡進行加噪的發(fā)布方法。

3）DPKTS（Differential Privacy based on K-means shape Similarity）［5］：基于相對熵和K-means 聚類并引入Frechet 距離利用原始軌跡考慮軌跡相似性的軌跡加噪發(fā)布。

4）SDTP：顯著點約簡后的軌跡的加噪發(fā)布。

5）IGSO-SDTP：本文提出的使用IGSO 算法協(xié)同SDTP 方法的加噪軌跡發(fā)布。

SDTP 和IGSO-SDTP 是本文提出的兩種軌跡發(fā)布方法，選擇LIC 和DPKTS 作為對比方法，是因為這兩種方法性能好且適用于本文的應(yīng)用場景。為了避免實驗結(jié)果的偶然性，案例分析及實驗均取20 次實驗的平均值。

IGSO-SDTP 中的參數(shù)包含IGSO 算法參數(shù)和隱私保護的參數(shù)。IGSO 算法的參數(shù)取值參照文獻［24，29］中的取值經(jīng)驗，默認的取值為p=0.3，n=20，nt=rs=8，ρ=0.4，γ=0.6，β=0.08，r1=0.5，r2=0.5；隱私保護的參數(shù)包含k-匿名的k、距離kd、隱私預(yù)算ε，根據(jù)參數(shù)實驗分析，參數(shù)默認取值為k=10，kd=0.01，ε=0.06。LIC 涉及參數(shù)Hilbert 曲線階數(shù)h，聚簇數(shù)量k1。DPKTS 參數(shù)包括簇頭數(shù)k2，隱私模型參數(shù)σ。根據(jù)文獻［3，8］，h=12，kl=50，k2=5，σ=0.06。

4.2 案例分析

5 種方法在發(fā)布6 條軌跡數(shù)據(jù)的距離誤差見表3。SDTP的距離誤差整體小于RD，說明SDTP 利用顯著點簡化軌跡后，刪除了部分冗余軌跡位置信息，提升了軌跡位置點的有效性；LIC 的距離誤差與SDTP 相當(dāng)，說明利用Hilbert 曲線提取軌跡分布特征生成位置的代表元的過程，與顯著點簡化的作用近似；DPKTS 在Geo2、Geo3 軌跡上小于RD，在其他軌跡上大于RD，說明在生成形狀相似的干擾軌跡時，可能會加大距離誤差；IGSO-SDTP 整體小于SDTP，在5 種方法中的距離誤差最小，說明通過IGSO 算法進一步組合尋優(yōu)，可以在SDTP 基礎(chǔ)上降低發(fā)布干擾軌跡的距離誤差，進一步提高干擾軌跡的可用性。

表3 不同方法的距離誤差Tab.3 Distance errors of different methods

5 種方法在發(fā)布6 條軌跡數(shù)據(jù)的Frechet 距離見表4。SDTP 的Frechet 距離誤差整體小于RD，這說明SDTP 利用顯著點簡化軌跡后，保留了軌跡的顯著特征，提升了發(fā)布的干擾軌跡的有效性；LIC 的SDTP 距離小于RD 但大于SDTP，說明減小距離誤差在一定程度內(nèi)有利于提升軌跡的相似性；DPKTS 在Geo2、Geo3、Geo4、Geo6 軌跡上小于SDTP，在Geo1、Geo5 軌跡上大于SDTP 但小于RD，說明使用相對熵和K-means 聚類對提升干擾軌跡的相似性的效果較好；IGSOSDTP 在5 種方法中得到的Frechet 距離最小，說明IGSO 算法在SDTP 基礎(chǔ)上組合尋優(yōu)，可提升發(fā)布干擾軌跡的相似性，進一步提高干擾軌跡的可用性。

表4 不同方法的Frechet距離Tab.4 Frechet distances of different methods

5 種方法在發(fā)布6 條軌跡數(shù)據(jù)的加權(quán)距離見表5。SDTP整體小于RD，說明SDTP 利用顯著點簡化軌跡后，刪除了部分冗余軌跡位置信息，提升了軌跡加噪發(fā)布的有效性；LIC在Geo4 計算得到的加權(quán)距離比DPKTS 大，在其他5 個數(shù)據(jù)集上計算得到的加權(quán)距離比DPKTS 小，說明DPKTS 在加權(quán)距離指標上的整體效果好于LIC。IGSO-SDTP 在不同數(shù)據(jù)集上計算得到的加權(quán)距離均最小，相較于RD、SDTP、LIC、DPKTS 分別降低了21.94%、9.15%、14.25%、10.55%。

表5 不同方法的加權(quán)距離Tab.5 Weighted distances of different methods

4.3 數(shù)據(jù)集實驗

采用Geolife 數(shù)據(jù)集進行實驗，計算5 種方法在不同隱私預(yù)算下軌跡加噪發(fā)布的誤差。表6 是5 種方法基于Geolife 數(shù)據(jù)集20 次實驗計算出的平均加權(quán)距離指標。

表6 不同隱私預(yù)算下的平均加權(quán)距離Tab.6 Average weighted distances under different privacy budgets

SDTP 平均加權(quán)距離整體依然小于RD，說明SDTP 利用顯著點簡化軌跡提升軌跡加噪發(fā)布始終是有效的；雖然在案例分析時DPKTS 基于Geo4 子數(shù)據(jù)集的計算結(jié)果比LIC 略大，但整體上DPKTS 在Geolife 數(shù)據(jù)集得到的平均加權(quán)距離比LIC 都小，說明DPKTS 利用軌跡相似性原理，不僅可以提升軌跡相似性，同時可以減小軌跡誤差，總體效用好于LIC；SDTP 計算的結(jié)果在ε為0.02、0.08、0.2、0.4 時介于LIC 和DPKTS 之間，在ε為0.04、0.06、0.1、0.8 時小于LIC 和DPKTS，在ε為0.6 時，大于LIC 和DPKTS，說明SDTP 方法的穩(wěn)定性較差；IGSO-SDTP 在任何隱私預(yù)算下計算的平均加權(quán)距離始終小于其他算法，說明該方法能泛化加噪并選擇出較好質(zhì)量的干擾軌跡，且發(fā)布的穩(wěn)定性較好。

圖4 是IGSO-SDTP 方法相較于其他方法在不同隱私預(yù)算下的性能提升程度。可以看出，IGSO-SDTP 方法相較于RD 方法提升最多，相較于DPKTS 提升最小。在ε<0.1 時，IGSO-SDTP 較其他4 種方法整體提升的程度較優(yōu)，隨著ε的逐漸增大，IGSO-SDTP 較其他4 種方法整體提升的幅度較小，說明IGSO-SDTP 在ε較小時，發(fā)布的干擾軌跡質(zhì)量較高。IGSO-SDTP 相較于SDTP 發(fā)布干擾軌跡的性能有所提升，是因為基于k-匿名協(xié)同差分隱私的升維以及IGSO 算法的降維結(jié)合，進一步提升了發(fā)布干擾軌跡在距離誤差和Frechet 距離兩個方面的性能，降低了加權(quán)距離。

圖4 不同方法的性能比較Fig.4 Performance comparison of different methods

4.4 參數(shù)分析

對影響IGSO-SDTP 性能的主要參數(shù)實驗，保持其他參數(shù)不變，實驗?zāi)骋粎?shù)取不同值時IGSO-SDTP 在Geo1 數(shù)據(jù)集上計算得到的加權(quán)距離，并取20 次實驗的平均值。

關(guān)于k-匿名的半徑r參數(shù)分析如表7，整體變化是隨r的增大，平均加權(quán)距離先減小后增大，當(dāng)r取0.01 時，平均加權(quán)距離最小。

表7 半徑r的取值分析Tab.7 Analysis of radius r

關(guān)于k-匿名的泛化數(shù)量k參數(shù)分析如圖5，平均加權(quán)距離整體隨k增大不斷減小，直到k取10 后趨于穩(wěn)定，因為k越大，泛化生成的位置點更均衡，加噪后得到的數(shù)據(jù)集更能尋找發(fā)布出兼顧距離誤差和相似性的干擾軌跡，即加權(quán)距離較小，當(dāng)k增大一定程度后，加權(quán)距離趨于穩(wěn)定。

圖5 參數(shù)k的分析Fig.5 Analysis of parameter k

關(guān)于變異因子p的參數(shù)分析如圖6，整體變化是隨p的增大，平均加權(quán)距離先減小后增大，當(dāng)p取0.3 時，平均加權(quán)距離最小。

圖6 參數(shù)p的分析Fig.6 Analysis of parameter p

關(guān)于顯著點閾值g的參數(shù)分析如圖7，雖然約簡率隨閾值增大持續(xù)下降，但平均加權(quán)距離先減小后增大，因為軌跡數(shù)據(jù)中的一些位置點是冗余信息，但約簡率過大時，可能過濾了部分關(guān)鍵信息，會影響發(fā)布干擾軌跡的可用性，所以g要取適中的值0.1。

圖7 參數(shù)g的分析Fig.7 Analysis of parameter g

隱私預(yù)算ε見圖4，當(dāng)ε取0.06 或0.1，IGSO-SDTP 方法相較于其他方法提升較大，且絕對差距在ε取0.06 較大，所以ε取0.06。

5 結(jié)語

針對歷史軌跡數(shù)據(jù)加噪發(fā)布干擾軌跡的問題，本文通過顯著點的判斷，先對軌跡數(shù)據(jù)集進行了約簡，并結(jié)合k-匿名和差分隱私對約簡后的數(shù)據(jù)集泛化和加噪；通過改進螢火蟲群優(yōu)化算法，基于加權(quán)距離評價指標，尋找到的干擾軌跡既考慮到了距離誤差，又兼顧到了軌跡的相似性，因此安全性和可用性都更好。理論分析和實驗結(jié)果驗證，本文方法在確保軌跡隱私的前提下，提高了干擾軌跡可用性。