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

（1.合肥工業(yè)大學(xué) 管理學(xué)院，合肥 230009；2.北方民族大學(xué) 商學(xué)院，銀川 750021；3.過程優(yōu)化與智能決策教育部重點(diǎn)實(shí)驗(yàn)室（合肥工業(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)航軟件、美團(tuán)外賣APP、滴滴快車APP 等。用戶不間斷上傳位置數(shù)據(jù)，軟件及服務(wù)器獲取大量數(shù)據(jù)，這些序列化的時(shí)間、位置數(shù)據(jù)即軌跡數(shù)據(jù)［3］。發(fā)布及分析軌跡數(shù)據(jù)對市政規(guī)劃、交通管理和應(yīng)急預(yù)案等優(yōu)化配置具有重要價(jià)值。軌跡數(shù)據(jù)包含用戶隱私的個(gè)人信息，根據(jù)某一用戶軌跡的起點(diǎn)、終點(diǎn)和經(jīng)常停留的位置等信息可能得到用戶的家庭住址、單位住址和興趣愛好。文獻(xiàn)［4］中記錄了15 個(gè)基于位置的應(yīng)用都出現(xiàn)了泄露位置信息的情況，所以軌跡數(shù)據(jù)發(fā)布亟須可靠的保護(hù)機(jī)制。

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

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

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

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

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

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

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

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

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

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

1 相關(guān)工作

1.1 干擾軌跡發(fā)布

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

1.2 k-匿名和差分隱私

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

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

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

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

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

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

2 理論知識

2.1 軌跡可用性評估

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

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

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

其中：T、T'表示兩條軌跡；d(T(i(t))，T'(j(t)))表示兩個(gè)采樣點(diǎn)在時(shí)刻t的歐氏距離；infi，j，t∈[0，1]表示曲線i和曲線j之間距離最大值的下界值。每次采樣時(shí)，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個(gè)近似的數(shù)據(jù)，則稱T滿足k-匿名［13］。

2.3 差分隱私

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

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

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

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

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

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

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

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

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

2.4 顯著點(diǎn)判斷

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

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

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

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

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

3 方案設(shè)計(jì)

3.1 主要符號

本文符號主要包含兩部分：第一部分包含軌跡數(shù)據(jù)、k-匿名、差分隱私加噪、提取顯著點(diǎn)和數(shù)據(jù)評估等軌跡數(shù)據(jù)處理各環(huán)節(jié)的符號；第二部分包含螢火蟲群優(yōu)化算法及IGSO 算法運(yùn)行的相關(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 兩部分，通過算法目標(biāo)函數(shù)和螢火蟲熒光素關(guān)聯(lián)。目標(biāo)函數(shù)考慮了誤差距離和軌跡相似性兩個(gè)方面的影響因素。

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

1）IGSO-SDTP 方法步驟。

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

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

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

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

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

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

1）編碼和解碼。

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

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

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

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

3）距離計(jì)算。

因?yàn)榻饪臻g是離散編碼，故不能用原有步長計(jì)算方式。螢火蟲i和螢火蟲j在d維上的距離及總距離用海明距離計(jì)算，d∈[1，m]，如式（17）～（18）：

4）移動(dòng)策略。

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

3.4 算法偽代碼描述

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

算法1 軌跡約簡的隱私保護(hù)算法。

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

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

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

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

3.6 隱私保護(hù)分析

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

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

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

4.1 數(shù)據(jù)和實(shí)驗(yàn)說明

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

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

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

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

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

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

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

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

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

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

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

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

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

4.2 案例分析

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

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

5 種方法在發(fā)布6 條軌跡數(shù)據(jù)的Frechet 距離見表4。SDTP 的Frechet 距離誤差整體小于RD，這說明SDTP 利用顯著點(diǎn)簡化軌跡后，保留了軌跡的顯著特征，提升了發(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ā)布干擾軌跡的相似性，進(jìn)一步提高干擾軌跡的可用性。

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

5 種方法在發(fā)布6 條軌跡數(shù)據(jù)的加權(quán)距離見表5。SDTP整體小于RD，說明SDTP 利用顯著點(diǎn)簡化軌跡后，刪除了部分冗余軌跡位置信息，提升了軌跡加噪發(fā)布的有效性；LIC在Geo4 計(jì)算得到的加權(quán)距離比DPKTS 大，在其他5 個(gè)數(shù)據(jù)集上計(jì)算得到的加權(quán)距離比DPKTS 小，說明DPKTS 在加權(quán)距離指標(biāo)上的整體效果好于LIC。IGSO-SDTP 在不同數(shù)據(jù)集上計(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ù)集實(shí)驗(yàn)

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

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

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

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

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

4.4 參數(shù)分析

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

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

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

關(guān)于k-匿名的泛化數(shù)量k參數(shù)分析如圖5，平均加權(quán)距離整體隨k增大不斷減小，直到k取10 后趨于穩(wěn)定，因?yàn)閗越大，泛化生成的位置點(diǎn)更均衡，加噪后得到的數(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 時(shí)，平均加權(quán)距離最小。

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

關(guān)于顯著點(diǎn)閾值g的參數(shù)分析如圖7，雖然約簡率隨閾值增大持續(xù)下降，但平均加權(quán)距離先減小后增大，因?yàn)檐壽E數(shù)據(jù)中的一些位置點(diǎn)是冗余信息，但約簡率過大時(shí)，可能過濾了部分關(guān)鍵信息，會(huì)影響發(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ā)布干擾軌跡的問題，本文通過顯著點(diǎn)的判斷，先對軌跡數(shù)據(jù)集進(jìn)行了約簡，并結(jié)合k-匿名和差分隱私對約簡后的數(shù)據(jù)集泛化和加噪；通過改進(jìn)螢火蟲群優(yōu)化算法，基于加權(quán)距離評價(jià)指標(biāo)，尋找到的干擾軌跡既考慮到了距離誤差，又兼顧到了軌跡的相似性，因此安全性和可用性都更好。理論分析和實(shí)驗(yàn)結(jié)果驗(yàn)證，本文方法在確保軌跡隱私的前提下，提高了干擾軌跡可用性。