改進螢火蟲群算法協同差分隱私的干擾軌跡發布

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

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

0 引言

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

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

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

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

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

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

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

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

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

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

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

1 相關工作

1.1 干擾軌跡發布

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

1.2 k-匿名和差分隱私

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

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

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

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

1.3 螢火蟲群優化算法

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

2 理論知識

2.1 軌跡可用性評估

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

假設某真實軌跡T某時刻t的真實位置為lt，發布軌跡T'對應時刻位置為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-匿名。原始數據集T，泛化后的數據集T'。若T中的任意數據li在T'對應的數據中均有不少于k個近似的數據，則稱T滿足k-匿名［13］。

2.3 差分隱私

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

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

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

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

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

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

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

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

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

2.4 顯著點判斷

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

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

2.5 螢火蟲群優化算法

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

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

3 方案設計

3.1 主要符號

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

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

3.2 IGSO-SDTP整體思路

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

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

1）IGSO-SDTP 方法步驟。

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

2）IGSO 算法的目標函數。

目標函數構建如式（14）所示，通過構建加權線性函數將多目標問題轉為單目標問題再求解。

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

3.3 改進螢火蟲群優化算法

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

1）編碼和解碼。

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

2）反向學習協同初始化。

反向學習是根據反向數生成反向解的優化方法［30］。設R上d維離散點xd=[m，n]，d1∈{1，2，…，d}，則x在d1維的反向數定義為：

反向學習協同初始化是指在初始化種群基礎上，利用反向學習獲得另一組種群。根據對應目標函數，將兩組種群的目標函數降序。在每組目標函數中分別選擇較好一半的解空間對應的子種群，協同混合生成一組質量較好的初始化種群。

3）距離計算。

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

4）移動策略。

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

3.4 算法偽代碼描述

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

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

輸入 原始軌跡數據T；

3.5 算法的時間復雜度

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

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

3.6 隱私保護分析

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

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

4 實驗與結果分析

4.1 數據和實驗說明

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

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

圖3 Geo1～Geo6的軌跡形態Fig.3 Trajectories of Geo1～Geo6

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

表2 軌跡數據的約簡Tab.2 Reduction of track data

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

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

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

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

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

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

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

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

4.2 案例分析

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

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

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

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

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

表5 不同方法的加權距離Tab.5 Weighted distances of different methods

4.3 數據集實驗

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

表6 不同隱私預算下的平均加權距離Tab.6 Average weighted distances under different privacy budgets

SDTP 平均加權距離整體依然小于RD，說明SDTP 利用顯著點簡化軌跡提升軌跡加噪發布始終是有效的；雖然在案例分析時DPKTS 基于Geo4 子數據集的計算結果比LIC 略大，但整體上DPKTS 在Geolife 數據集得到的平均加權距離比LIC 都小，說明DPKTS 利用軌跡相似性原理，不僅可以提升軌跡相似性，同時可以減小軌跡誤差，總體效用好于LIC；SDTP 計算的結果在ε為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 方法的穩定性較差；IGSO-SDTP 在任何隱私預算下計算的平均加權距離始終小于其他算法，說明該方法能泛化加噪并選擇出較好質量的干擾軌跡，且發布的穩定性較好。

圖4 是IGSO-SDTP 方法相較于其他方法在不同隱私預算下的性能提升程度?？梢钥闯?，IGSO-SDTP 方法相較于RD 方法提升最多，相較于DPKTS 提升最小。在ε<0.1 時，IGSO-SDTP 較其他4 種方法整體提升的程度較優，隨著ε的逐漸增大，IGSO-SDTP 較其他4 種方法整體提升的幅度較小，說明IGSO-SDTP 在ε較小時，發布的干擾軌跡質量較高。IGSO-SDTP 相較于SDTP 發布干擾軌跡的性能有所提升，是因為基于k-匿名協同差分隱私的升維以及IGSO 算法的降維結合，進一步提升了發布干擾軌跡在距離誤差和Frechet 距離兩個方面的性能，降低了加權距離。

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

4.4 參數分析

對影響IGSO-SDTP 性能的主要參數實驗，保持其他參數不變，實驗某一參數取不同值時IGSO-SDTP 在Geo1 數據集上計算得到的加權距離，并取20 次實驗的平均值。

關于k-匿名的半徑r參數分析如表7，整體變化是隨r的增大，平均加權距離先減小后增大，當r取0.01 時，平均加權距離最小。

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

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

圖5 參數k的分析Fig.5 Analysis of parameter k

關于變異因子p的參數分析如圖6，整體變化是隨p的增大，平均加權距離先減小后增大，當p取0.3 時，平均加權距離最小。

圖6 參數p的分析Fig.6 Analysis of parameter p

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

圖7 參數g的分析Fig.7 Analysis of parameter g

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

5 結語

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