基于遺傳算法的動(dòng)態(tài)軌跡匿名算法*

賈俊杰，秦海濤

(西北師范大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院,甘肅 蘭州 730070)

1 引言

無(wú)線(xiàn)定位技術(shù)的不斷發(fā)展和移動(dòng)智能終端設(shè)備的不斷普及，使得基于位置的服務(wù)LBS(Location-Based Services)[1]成為了一個(gè)新興產(chǎn)業(yè)。移動(dòng)對(duì)象在獲得多樣化位置服務(wù)的同時(shí)也面臨著諸多隱私信息暴露的風(fēng)險(xiǎn)。例如，移動(dòng)對(duì)象為獲得更好的位置服務(wù)需要向位置服務(wù)器發(fā)送自身的精確位置信息，這些位置信息將會(huì)被位置服務(wù)器以日志的形式記錄下來(lái)，一旦攻擊者以某種方式獲得移動(dòng)對(duì)象的軌跡數(shù)據(jù)，對(duì)其進(jìn)行分析便可從中推斷出與移動(dòng)對(duì)象相關(guān)的隱私信息，例如工作單位、收入情況和興趣愛(ài)好等。攻擊者進(jìn)一步通過(guò)其他關(guān)聯(lián)信息還可能獲得移動(dòng)對(duì)象的社交關(guān)系，這就為移動(dòng)對(duì)象的安全造成了極大的隱患。

近年來(lái)，為解決移動(dòng)對(duì)象的軌跡隱私保護(hù)問(wèn)題，已有許多方法被相繼提出。其中，軌跡K-匿名技術(shù)[1]的使用最為廣泛。軌跡K-匿名技術(shù)采用K-匿名原理[2,3]，將軌跡信息與移動(dòng)對(duì)象之間1∶1的關(guān)系轉(zhuǎn)換為1∶K的關(guān)系，從而達(dá)到保護(hù)移動(dòng)對(duì)象隱私信息的目的[4]。Gruteser等[5]最先將K-匿名技術(shù)應(yīng)用于位置隱私保護(hù)服務(wù)中，用一個(gè)包含至少K-1個(gè)移動(dòng)對(duì)象的匿名區(qū)域代替移動(dòng)對(duì)象的精確位置發(fā)送給位置服務(wù)器，使得攻擊者從匿名數(shù)據(jù)集中識(shí)別出真實(shí)移動(dòng)對(duì)象的概率不大于1/K。該方法在一定程度上保護(hù)了移動(dòng)對(duì)象的隱私信息，但不能滿(mǎn)足移動(dòng)對(duì)象的個(gè)性化隱私需求。針對(duì)此問(wèn)題，文獻(xiàn)[6]提出一種個(gè)性化隱私保護(hù)軌跡發(fā)布算法。該算法采用貪心聚類(lèi)的等價(jià)類(lèi)劃分思想對(duì)含有不同隱私需求的軌跡集合進(jìn)行個(gè)性化處理，在一定條件下滿(mǎn)足了移動(dòng)對(duì)象的個(gè)性化隱私需求，但卻忽略了二次聚類(lèi)攻擊依然會(huì)導(dǎo)致移動(dòng)對(duì)象隱私信息泄露的問(wèn)題。因此，文獻(xiàn)[7]提出了一種基于聚類(lèi)雜交的隱私保護(hù)軌跡數(shù)據(jù)發(fā)布算法。該算法采用聚類(lèi)雜交策略，對(duì)聚類(lèi)分組后先進(jìn)行組間雜交，再進(jìn)行組內(nèi)擾亂，從而達(dá)到預(yù)防二次聚類(lèi)攻擊的目的。但是，因軌跡進(jìn)行聚類(lèi)雜交時(shí)存在一定的隨機(jī)性，會(huì)產(chǎn)生一些隨機(jī)軌跡，攻擊者通過(guò)已掌握的背景知識(shí)，便可以從匿名集中輕易識(shí)別出這些軌跡。針對(duì)文獻(xiàn)[7]的問(wèn)題，文獻(xiàn)[8]提出一種基于移動(dòng)對(duì)象真實(shí)軌跡的虛假軌跡生成方法。該方法采用聚類(lèi)，選擇出具有相同行為模式的軌跡構(gòu)建虛假軌跡，解決軌跡隨機(jī)性問(wèn)題，并通過(guò)構(gòu)建馬爾科夫模型減小背景知識(shí)對(duì)軌跡隱私的影響。文獻(xiàn)[8]方法在一定程度上解決了軌跡隨機(jī)性問(wèn)題以及減小背景知識(shí)對(duì)隱私保護(hù)的影響，但卻不能對(duì)移動(dòng)對(duì)象的動(dòng)態(tài)移動(dòng)軌跡進(jìn)行隱私保護(hù)。

現(xiàn)有的動(dòng)態(tài)軌跡匿名算法大多從移動(dòng)對(duì)象的單個(gè)軌跡出發(fā)進(jìn)行軌跡隱私保護(hù)，在尋找最優(yōu)解的過(guò)程中容易陷入局部最優(yōu)。而且在進(jìn)行軌跡匿名時(shí)大多采用隨機(jī)方法來(lái)生成虛假軌跡，使得生成的虛假軌跡具有一定的隨機(jī)性。針對(duì)此問(wèn)題，基于遺傳算法GA(Genetic Algorithm)具有搜索全局最優(yōu)解的特性，本文提出基于遺傳算法的動(dòng)態(tài)軌跡匿名算法，利用遺傳算法對(duì)當(dāng)前時(shí)間段內(nèi)的歷史軌跡建立軌跡行為模式，通過(guò)該模式對(duì)移動(dòng)對(duì)象進(jìn)行軌跡預(yù)測(cè)，根據(jù)軌跡K-匿名技術(shù)對(duì)預(yù)測(cè)軌跡進(jìn)行虛假軌跡生成，以達(dá)到匿名的效果。在軌跡預(yù)測(cè)階段，根據(jù)預(yù)測(cè)軌跡實(shí)時(shí)更新軌跡行為模式，提高軌跡預(yù)測(cè)的準(zhǔn)確性，在一定程度上避免了隨機(jī)軌跡的出現(xiàn)，在對(duì)移動(dòng)對(duì)象軌跡隱私保護(hù)的同時(shí)保證匿名數(shù)據(jù)的發(fā)布質(zhì)量。

2 相關(guān)技術(shù)

2.1 軌跡

由于軌跡數(shù)據(jù)在時(shí)間、空間上的特殊性，所以對(duì)移動(dòng)對(duì)象軌跡數(shù)據(jù)進(jìn)行軌跡預(yù)測(cè)或者隱私保護(hù)，大多是在時(shí)空模型上進(jìn)行的。通過(guò)對(duì)移動(dòng)對(duì)象的軌跡數(shù)據(jù)進(jìn)行分析、挖掘，從而對(duì)移動(dòng)對(duì)象周期性規(guī)律或?qū)崟r(shí)運(yùn)行軌跡進(jìn)行預(yù)測(cè)以獲得移動(dòng)對(duì)象的相關(guān)個(gè)體信息[9,10]。

一般情況下，移動(dòng)對(duì)象的軌跡T可以表示為T(mén)={(x1,y1,t1)，(x2,y2,t2),…,(xn,yn,tn)}，其中,(xn,yn,tn)表示在tn時(shí)刻移動(dòng)對(duì)象的地理信息(xn,yn)。而移動(dòng)對(duì)象的軌跡又可以分為靜態(tài)軌跡和動(dòng)態(tài)軌跡。

(1)靜態(tài)軌跡是指移動(dòng)對(duì)象已經(jīng)停止運(yùn)行后，收集到的軌跡數(shù)據(jù)，即移動(dòng)對(duì)象的歷史軌跡。一般由第三方服務(wù)器或者移動(dòng)對(duì)象通過(guò)收集、篩選后發(fā)布給相關(guān)研究機(jī)構(gòu)。

(2)動(dòng)態(tài)軌跡是指移動(dòng)對(duì)象正在運(yùn)行且不斷增加新的位置序列的增量更新軌跡。一般是由移動(dòng)對(duì)象通過(guò)移動(dòng)終端設(shè)備向第三方服務(wù)器實(shí)時(shí)提供自身的位置信息，并獲得相應(yīng)的位置服務(wù)過(guò)程中發(fā)布的。

2.2 軌跡K-匿名

現(xiàn)有的軌跡K-匿名技術(shù)[1]采用K-匿名原理[2,3]，將移動(dòng)對(duì)象與軌跡之間的1∶1關(guān)系轉(zhuǎn)換為一條軌跡信息與多個(gè)移動(dòng)對(duì)象之間的1∶K關(guān)系。經(jīng)軌跡K-匿名處理后的匿名數(shù)據(jù)表，每個(gè)匿名組中每條軌跡與其他至少K-1條軌跡不可區(qū)分，從而降低移動(dòng)對(duì)象隱私泄露的概率，提高數(shù)據(jù)安全性。

2.3 遺傳算法

軌跡數(shù)據(jù)是一種多特性、多變量共存的數(shù)據(jù)，因此對(duì)軌跡數(shù)據(jù)進(jìn)行隱私保護(hù)時(shí)需要在多個(gè)變量中尋求一個(gè)最優(yōu)解，而通用性強(qiáng)、魯棒性高的遺傳算法正好可以解決軌跡匿名尋求多變量最優(yōu)解這一問(wèn)題[11]。遺傳算法是通過(guò)模擬自然界中生物的遺傳進(jìn)化過(guò)程并采用適者生存思想來(lái)搜索最優(yōu)解的算法[11]。算法搜索全局最優(yōu)解的過(guò)程是一個(gè)不斷迭代的過(guò)程，每一次迭代相當(dāng)于生物進(jìn)化中的一次循環(huán)，直到滿(mǎn)足算法的終止條件為止。但是，遺傳算法在其搜索過(guò)程中采用隨機(jī)搜索方法，因此通過(guò)遺傳算法得出的搜索結(jié)果存在一定的不確定性。通過(guò)一些相應(yīng)的改進(jìn)方法，可以有效地改善遺傳算法的局限性，在可控范圍的代價(jià)之內(nèi)取得最優(yōu)解[11]。

在遺傳算法中，問(wèn)題的每一個(gè)有效解被稱(chēng)為一條“染色體”，染色體的具體形式是一個(gè)使用特定編碼方式生成的編碼序列，編碼序列中的每一個(gè)編碼單元稱(chēng)為“基因”。在本文中，遺傳算法的染色體就是移動(dòng)對(duì)象的軌跡，基因則是移動(dòng)對(duì)象軌跡中的位置點(diǎn)。

3 動(dòng)態(tài)軌跡隱私保護(hù)

3.1 軌跡行為模式

移動(dòng)對(duì)象的習(xí)慣性軌跡運(yùn)動(dòng)模式具有群體特征[12]，通過(guò)對(duì)移動(dòng)對(duì)象的歷史軌跡數(shù)據(jù)進(jìn)行分析和挖掘便可從中獲得移動(dòng)對(duì)象的軌跡行為模式，這種模式在一定程度上反映了移動(dòng)對(duì)象在當(dāng)前時(shí)間段的出行規(guī)律。例如，通過(guò)提取Thomas Brinkhoffs生成器[13]模擬生成的某移動(dòng)對(duì)象在一個(gè)月內(nèi)的軌跡數(shù)據(jù)，提取字段包括：移動(dòng)對(duì)象ID、日期、軌跡起止時(shí)間、軌跡數(shù)據(jù)和語(yǔ)義數(shù)據(jù)，得到該移動(dòng)對(duì)象的歷史軌跡數(shù)據(jù)，如表1所示。

Table 1 Example of trajectory data of moving object 表1 移動(dòng)對(duì)象軌跡數(shù)據(jù)示例

在對(duì)移動(dòng)對(duì)象的歷史軌跡數(shù)據(jù)進(jìn)行軌跡行為模式構(gòu)建時(shí)，為使得模式盡可能符合軌跡群體的特征，降低冗余數(shù)據(jù)對(duì)模式的影響，需要先對(duì)歷史軌跡數(shù)據(jù)進(jìn)行預(yù)處理。

(1)數(shù)據(jù)預(yù)處理。

為了建立遺傳算法的初始種群，首先，從移動(dòng)對(duì)象的歷史信息中選擇某一段時(shí)間內(nèi)的軌跡；其次，利用混合編碼方式[14]將所選歷史軌跡進(jìn)行編碼。例如表1中移動(dòng)對(duì)象1在時(shí)間段0821～0825(起始時(shí)間ti=01:00，結(jié)束時(shí)間tn=07:00)的一條軌跡T={(3,4),(2,2),(4,3),(5,4),(3,1),(5,6)}，由于位置屬性是整數(shù)，采用混合編碼后得到軌跡編碼序列F=(1,2,3,4,5,6)。

(2)軌跡行為模式構(gòu)建。

在本文中，利用遺傳算法尋找全局最優(yōu)解的特性，對(duì)移動(dòng)對(duì)象的軌跡行為模式進(jìn)行構(gòu)建時(shí)，首先將某一固定時(shí)間段內(nèi)的歷史軌跡信息作為初始種群；其次從歷史軌跡中選擇出滿(mǎn)足適應(yīng)度策略的最優(yōu)相似軌跡進(jìn)行選擇、交叉、變異操作，迭代此過(guò)程直到選擇出軌跡片段重復(fù)率最大的n條軌跡(n≥1)，這n條軌跡在一定程度上反映了移動(dòng)對(duì)象在該歷史時(shí)間段內(nèi)的出行規(guī)律，即軌跡行為模式。令Ti表示第i條軌跡，Tij表示第i條軌跡中第j個(gè)位置。軌跡行為模式構(gòu)建過(guò)程如下所示：

(1)將移動(dòng)對(duì)象固定歷史時(shí)間段內(nèi)的軌跡數(shù)據(jù)進(jìn)行編碼作為染色體，生成初始種群，其中基因表示軌跡中的位置點(diǎn)。

(2)適應(yīng)度策略。在本文中，若軌跡Tr和軌跡Ts的軌跡片段重復(fù)的概率大于閾值τ，則認(rèn)為軌跡Tr和Ts相似，這樣的相似軌跡即為所選擇個(gè)體。

(3)選擇。通過(guò)輪盤(pán)賭方式選擇群體中滿(mǎn)足適應(yīng)策略的父代個(gè)體。

(4)交叉。利用交叉算子形成新的子代個(gè)體，并按照適應(yīng)度策略進(jìn)行篩選。

(5)變異。利用變異算子形成新的子代個(gè)體，并按照適應(yīng)度策略進(jìn)行篩選。

(6)重復(fù)(3)～(5)，直到收斂得到最優(yōu)個(gè)體，即代表移動(dòng)對(duì)象行為規(guī)律的軌跡。

例如，根據(jù)表1，設(shè)定重復(fù)概率閾值τ≤3，利用算法得到最終軌跡T1={(3,4),(2,2),(4,3),(5,4),(3,1),(5,6)}，T2={(3,2),(4,1),(2,3),(1,4),(2,1),(5,2)}，T3={(2,2),(5,2),(1,3),(4,3),(5,4),(5,1)}，T4={(1,4),(3,2),(4,1),(3,1),(5,1),(4,2)}，T5={(5,1),(1,4),(2,3),(1,4),(5,1),(2,6)}，進(jìn)行軌跡網(wǎng)構(gòu)建后得到如圖1所示的軌跡網(wǎng)狀結(jié)構(gòu)，該軌跡網(wǎng)表示固定時(shí)間段內(nèi)的所有頻繁軌跡片段(邊)，除了起止時(shí)間，軌跡片段之間不考慮時(shí)序。

Figure 1 network圖1 軌跡網(wǎng)

為了得到移動(dòng)對(duì)象軌跡行為模式，通過(guò)位置點(diǎn)所體現(xiàn)的語(yǔ)義信息，將圖1轉(zhuǎn)換為軌跡語(yǔ)義[15]網(wǎng)絡(luò)，如圖2所示，各位置點(diǎn)對(duì)應(yīng)的語(yǔ)義在移動(dòng)對(duì)象軌跡(如表1所示)中出現(xiàn)的頻數(shù)如表2所示。

Figure 2 Trajectory semantic network圖2 軌跡語(yǔ)義網(wǎng)絡(luò)

Table 2 Semantic frequency table

設(shè)定軌跡語(yǔ)義頻數(shù)閾值3≤ρ≤5，得到移動(dòng)對(duì)象在當(dāng)前時(shí)間段內(nèi)的軌跡語(yǔ)義網(wǎng)絡(luò)如圖3所示。

Figure 3 Trajectory semantic network (3≤ρ≤5)圖3 軌跡語(yǔ)義網(wǎng)絡(luò)(3≤ρ≤5)

根據(jù)圖3得到移動(dòng)對(duì)象在該時(shí)間段內(nèi)的軌跡行為模式為(超市，醫(yī)院，工作單位，星巴克，加油站，醫(yī)院，超市，家)，“超市”和“家”分別為起止時(shí)間移動(dòng)對(duì)象的位置語(yǔ)義，則圖1中的軌跡為該軌跡行為模式所蘊(yùn)含的軌跡。假設(shè)軌跡T1，T2，T3為移動(dòng)對(duì)象在某一時(shí)間段內(nèi)的3條軌跡，則可以把它們按時(shí)序歸為一個(gè)軌跡組TRi，軌跡行為模式構(gòu)建如算法1所示。

算法1移動(dòng)對(duì)象軌跡行為模式構(gòu)建(Modeal_Tra)

輸入：移動(dòng)對(duì)象歷史軌跡數(shù)據(jù)D={T1,T2,…,Tn}。

輸出：移動(dòng)對(duì)象軌跡行為模式T。

1.按時(shí)間順序?qū)進(jìn)行分組，得到m個(gè)軌跡組Dt={TR1,TR2,TR3,…,TRm};

2.T=?;

3.for(i=1 tom)

4.{

5. 初始化第i個(gè)軌跡組TRi：Initialize(TRi);

6. 根據(jù)遺傳算法選擇TRi中滿(mǎn)足適應(yīng)度策略的父代軌跡組TR′i：Fitness(TR′i);

7. 當(dāng)存在不滿(mǎn)足適應(yīng)度策略的軌跡TRi-TR′i時(shí)

8. {進(jìn)行交叉、變異：GA-operation(TRi-TR′i);

9. 選擇滿(mǎn)足適應(yīng)度策略的子代：Fitness(TR″i);

10. 將父代與子代合并，即TR′i+ =TR″i;}

11. 從TR′i中選擇出一條最優(yōu)個(gè)體T′i作為該軌跡組TRi的行為模式;

12.T+=T′i;

13.}

14.返回T。

3.2 動(dòng)態(tài)軌跡預(yù)測(cè)

移動(dòng)對(duì)象的動(dòng)態(tài)軌跡是依賴(lài)于當(dāng)前軌跡或位置點(diǎn)而實(shí)時(shí)變化的，對(duì)下一時(shí)段軌跡進(jìn)行預(yù)測(cè)具有一定的現(xiàn)實(shí)意義。針對(duì)預(yù)測(cè)出的下一時(shí)段軌跡中的敏感信息進(jìn)行有效保護(hù)可避免移動(dòng)對(duì)象的隱私泄露，而軌跡的敏感信息一般蘊(yùn)含在軌跡的語(yǔ)義信息中。

軌跡預(yù)測(cè)過(guò)程就是根據(jù)當(dāng)前移動(dòng)對(duì)象已走的軌跡語(yǔ)義信息，去預(yù)測(cè)下一時(shí)段軌跡語(yǔ)義，利用下一時(shí)段軌跡語(yǔ)義可預(yù)測(cè)出軌跡行為模式中所蘊(yùn)含的軌跡。再將新增的預(yù)測(cè)軌跡加入歷史軌跡中，重新利用遺傳算法更新軌跡行為模式。文獻(xiàn)[8,16]將歷史軌跡信息作為背景知識(shí)，缺少對(duì)背景知識(shí)的動(dòng)態(tài)更新。本文算法通過(guò)實(shí)時(shí)動(dòng)態(tài)更新軌跡行為模式，不斷地充實(shí)背景知識(shí)，可提高軌跡預(yù)測(cè)的準(zhǔn)確性。

假設(shè)移動(dòng)對(duì)象1某時(shí)間段的軌跡行為模式如圖3所示，其所蘊(yùn)含的軌跡如圖1所示，該時(shí)間段移動(dòng)對(duì)象已走軌跡為{(2,2),(4,3),(5,4),(3,1)}，根據(jù)軌跡模式可以預(yù)測(cè)移動(dòng)對(duì)象下一時(shí)段軌跡語(yǔ)義為(工作單位，醫(yī)院，超市)，根據(jù)圖1可知該軌跡語(yǔ)義所蘊(yùn)含的軌跡為T(mén)1={(3,1)，(4,1)，(2,3)，(4,3)，(5,1)}，T2={(3,1)，(5,4)，(4,3)，(2,2)}，T3={(3,1)，(5,1)，(4,3)，(2,3)，(4,1)}，移動(dòng)對(duì)象的預(yù)測(cè)軌跡如圖4所示。

Figure 4 Trajectory prediction圖4 軌跡預(yù)測(cè)

對(duì)移動(dòng)對(duì)象的動(dòng)態(tài)軌跡進(jìn)行預(yù)測(cè)時(shí)，一般會(huì)采用均方根誤差RMSE判定移動(dòng)對(duì)象真實(shí)軌跡點(diǎn)與預(yù)測(cè)軌跡點(diǎn)之間的誤差[9]，如式(1)所示：

(1)

其中，(xi,yi)為移動(dòng)對(duì)象的真實(shí)位置，(x′i,y′i)為移動(dòng)對(duì)象的預(yù)測(cè)位置，k表示軌跡中的位置點(diǎn)個(gè)數(shù)。

3.3 隱私保護(hù)

軌跡隱私是一種特殊的個(gè)體隱私，是指移動(dòng)對(duì)象運(yùn)行的軌跡本身就包含有敏感信息或者由軌跡信息可推導(dǎo)出與移動(dòng)對(duì)象相關(guān)的個(gè)體隱私[1]。假設(shè)移動(dòng)對(duì)象軌跡行為模式發(fā)生泄漏，攻擊者結(jié)合背景知識(shí)可對(duì)其接下來(lái)的行為軌跡進(jìn)行預(yù)測(cè)，進(jìn)而可能推斷移動(dòng)對(duì)象軌跡隱私。因此，要保證預(yù)測(cè)軌跡中的敏感位置不被泄露，進(jìn)而保證軌跡模式中的敏感語(yǔ)義信息不被泄露。

表1中移動(dòng)對(duì)象位置點(diǎn)(4,3)和(4,1)對(duì)應(yīng)的語(yǔ)義信息為醫(yī)院，攻擊者一旦獲得該信息后，通過(guò)事先獲知移動(dòng)對(duì)象有不舒服的表現(xiàn)，便可大概率推斷出該移動(dòng)對(duì)象生病的信息，因此，“醫(yī)院”作為敏感信息需要對(duì)其所蘊(yùn)含的敏感位置所處的軌跡進(jìn)行隱匿。

本文在對(duì)移動(dòng)對(duì)象的動(dòng)態(tài)軌跡進(jìn)行隱私保護(hù)時(shí)，根據(jù)預(yù)測(cè)軌跡間的最大距離為帶寬，按照軌跡K-匿名的方式從該帶寬內(nèi)選擇K條軌跡，使得預(yù)測(cè)軌跡被識(shí)別出的概率不大于1/K，以達(dá)到隱匿真實(shí)動(dòng)態(tài)軌跡的目的。

軌跡間的距離如式(2)所示：

(2)

其中，(xi,yi)為移動(dòng)對(duì)象的坐標(biāo)點(diǎn)，t1,t2表示對(duì)應(yīng)時(shí)刻，Dis為位置點(diǎn)間的距離。

如圖5所示，假設(shè)K=3,根據(jù)軌跡行為模式，在一定帶寬內(nèi)選擇K-1=2條軌跡，形成軌跡3-匿名組。

Figure 5 Trajectory 3-anonymous圖5 軌跡3-匿名

4 基于遺傳算法的動(dòng)態(tài)軌跡匿名算法

4.1 算法描述

為防止移動(dòng)對(duì)象動(dòng)態(tài)運(yùn)行軌跡泄露導(dǎo)致的自身隱私泄露問(wèn)題，本文提出基于遺傳算法的動(dòng)態(tài)軌跡匿名算法，隨著移動(dòng)對(duì)象的動(dòng)態(tài)移動(dòng)，將預(yù)測(cè)軌跡實(shí)時(shí)加入初始軌跡種群，反復(fù)執(zhí)行下面3個(gè)步驟：

(1)以移動(dòng)對(duì)象的真實(shí)歷史軌跡信息為基礎(chǔ)，通過(guò)遺傳算法從歷史軌跡信息中選擇出移動(dòng)對(duì)象的軌跡行為模式；

(2)通過(guò)軌跡行為模式預(yù)測(cè)當(dāng)前移動(dòng)對(duì)象的下一時(shí)段軌跡，將預(yù)測(cè)軌跡加入初始種群；

(3)對(duì)預(yù)測(cè)出的軌跡利用軌跡K-匿名技術(shù)隱匿軌跡，以達(dá)到隱匿移動(dòng)對(duì)象實(shí)時(shí)位置或?qū)崟r(shí)運(yùn)行軌跡的目的。

算法2移動(dòng)對(duì)象的動(dòng)態(tài)軌跡匿名(Hidden_Tra)算法

輸入：歷史軌跡數(shù)據(jù)集D={T1,T2,…,Tn},動(dòng)態(tài)更新的軌跡數(shù)據(jù)Tg。

輸出：滿(mǎn)足軌跡K-匿名的軌跡數(shù)據(jù)D′。

1.D′←?;

2.將Tg加入到D中；

3.調(diào)用Modeal_Tra(D)返回軌跡行為模式T;

4.if(T包含敏感信息)

5. 根據(jù)遺傳算法從D中選擇出與T相似的K-1條軌跡并將T加入到D′中;

6.else不進(jìn)行隱匿，即D′ =D;

7.endif

8.返回D′。

4.2 準(zhǔn)確性度量

為檢測(cè)本文算法的性能，結(jié)合軌跡相似度[17]和匹配查詢(xún)結(jié)果來(lái)對(duì)預(yù)測(cè)軌跡進(jìn)行準(zhǔn)確性和隱匿效果的評(píng)價(jià)。軌跡相似度主要衡量移動(dòng)對(duì)象的真實(shí)軌跡與預(yù)測(cè)軌跡之間的差異性，用于算法中軌跡預(yù)測(cè)階段。匹配查詢(xún)結(jié)果主要衡量移動(dòng)對(duì)象的真實(shí)軌跡從匿名集中被識(shí)別出的概率，用于軌跡匿名階段。

定義1(軌跡相似度) 預(yù)測(cè)軌跡T′內(nèi)的任意位置點(diǎn)s，計(jì)算與s對(duì)應(yīng)的真實(shí)軌跡T內(nèi)的位置點(diǎn)的距離Dis，若Dis<φ(φ為軌跡相似距離閾值)且該2條軌跡的軌跡片段重復(fù)的概率大于閾值τ，則稱(chēng)預(yù)測(cè)軌跡T′與真實(shí)軌跡T相似。

定義2(匹配查詢(xún)結(jié)果) 匿名表內(nèi)任一軌跡記錄Ts，計(jì)算Ts到真實(shí)軌跡T的軌跡距離Dis，若Dis大于相似距離閾值ξ，并且重合位置點(diǎn)個(gè)數(shù)小于給定閾值，則認(rèn)為該匿名軌跡存在隱私泄露。

由于本文采用先對(duì)移動(dòng)對(duì)象的軌跡進(jìn)行預(yù)測(cè)，然后再對(duì)預(yù)測(cè)的軌跡進(jìn)行隱私保護(hù)的策略，所以需要結(jié)合軌跡相似度和匹配查詢(xún)結(jié)果來(lái)對(duì)軌跡匿名的不同階段進(jìn)行數(shù)據(jù)評(píng)價(jià)。

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

本節(jié)將從軌跡命中率、軌跡誤差率、隱私保護(hù)有效性、軌跡相似度和匿名數(shù)據(jù)質(zhì)量幾個(gè)角度出發(fā)，對(duì)本文算法進(jìn)行驗(yàn)證。通過(guò)軌跡命中率和軌跡誤差率來(lái)評(píng)測(cè)本文算法預(yù)測(cè)軌跡的有效性。隱私保護(hù)有效性和軌跡相似度用來(lái)評(píng)測(cè)經(jīng)過(guò)本文算法進(jìn)行軌跡隱匿后的移動(dòng)對(duì)象隱私信息泄露的概率。匿名數(shù)據(jù)質(zhì)量用來(lái)衡量發(fā)布的匿名數(shù)據(jù)的有效性。

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

實(shí)驗(yàn)采用的數(shù)據(jù)由Thomas Brinkhoffs生成器[13]模擬德國(guó)奧爾登堡地圖生成。本文選取50 km×50 km區(qū)域內(nèi)1 000個(gè)時(shí)間片內(nèi)的10 000條軌跡構(gòu)成實(shí)驗(yàn)數(shù)據(jù)集，其軌跡中相鄰軌跡點(diǎn)間的時(shí)間差為20 min。表3為實(shí)驗(yàn)數(shù)據(jù)集參數(shù)。

實(shí)驗(yàn)環(huán)境為Intel i5 3.4 GHz，4 GB內(nèi)存，Windows 64位操作系統(tǒng)，算法由eclipse 8.1和Matlab 2016a編寫(xiě)。

Table 3 Experimental parameter setting表3 實(shí)驗(yàn)參數(shù)設(shè)置

5.2 軌跡命中率

軌跡命中率指通過(guò)算法預(yù)測(cè)出的預(yù)測(cè)軌跡與移動(dòng)對(duì)象真實(shí)運(yùn)行軌跡匹配度達(dá)到一定閾值的次數(shù)。作為衡量一個(gè)軌跡預(yù)測(cè)算法準(zhǔn)確性的標(biāo)準(zhǔn)，通常命中率越高，則表示該軌跡預(yù)測(cè)算法準(zhǔn)確性越好。在本文中，選擇相同時(shí)間段內(nèi)具有相同背景信息的3 500條軌跡作為初始軌跡數(shù)據(jù)集，選擇文獻(xiàn)[9,10]中的算法作為參考，并與本文算法做對(duì)比實(shí)驗(yàn)。實(shí)驗(yàn)結(jié)果如圖6所示。

Figure 6 Trajectory hit rate圖6 軌跡命中率

如圖6所示，隨著軌跡數(shù)目的不斷增加，3種算法對(duì)移動(dòng)對(duì)象的真實(shí)軌跡運(yùn)行的命中率也呈現(xiàn)出不同的變化效果。在軌跡數(shù)目為0～1000時(shí)，本文的軌跡預(yù)測(cè)算法的軌跡命中率相比于其它2種算法的更高，這是因?yàn)楸疚乃惴ㄊ且砸苿?dòng)對(duì)象的歷史運(yùn)行軌跡為基礎(chǔ)，并結(jié)合遺傳算法尋找全局最優(yōu)解的特性可以較為快速地從軌跡數(shù)據(jù)集中預(yù)測(cè)出移動(dòng)對(duì)象將要到達(dá)的軌跡位置點(diǎn)。但是，在起始區(qū)間內(nèi)，由于起始區(qū)間內(nèi)的軌跡數(shù)目較少，軌跡預(yù)測(cè)時(shí)的初始種群就會(huì)比較小，所以本文算法相比于文獻(xiàn)[9,10]中的算法的軌跡命中率就低一些。軌跡數(shù)目達(dá)到一定值時(shí)，移動(dòng)對(duì)象歷史軌跡之間的關(guān)聯(lián)性也在逐漸增加，軌跡命中率也會(huì)出現(xiàn)一個(gè)短暫的下降趨勢(shì)。隨著軌跡數(shù)目逐漸增加，本文算法會(huì)結(jié)合移動(dòng)對(duì)象軌跡之間的關(guān)聯(lián)性，調(diào)整歷史軌跡劃分規(guī)則，從而提高預(yù)測(cè)軌跡命中真實(shí)運(yùn)行軌跡的概率。

5.3 軌跡相似度

軌跡相似度主要是用來(lái)評(píng)判移動(dòng)對(duì)象真實(shí)運(yùn)行軌跡與算法生成的軌跡之間的差異性。為驗(yàn)證不同算法在相同條件下的移動(dòng)對(duì)象預(yù)測(cè)軌跡、通過(guò)算法生成的匿名軌跡與真實(shí)運(yùn)行軌跡之間的相似度，將本文算法與文獻(xiàn)[9，10，16]中的算法進(jìn)行對(duì)比。

首先，將從預(yù)測(cè)軌跡與移動(dòng)對(duì)象真實(shí)運(yùn)行軌跡這個(gè)角度出發(fā)，驗(yàn)證不同軌跡預(yù)測(cè)算法在相同時(shí)間段內(nèi)預(yù)測(cè)軌跡之間的差異性，結(jié)果如圖7所示。

Figure 7 Similarity of predicted trajectory圖7 預(yù)測(cè)軌跡相似度

從圖7中可以看出，相比于其他3種算法，本文算法預(yù)測(cè)出的預(yù)測(cè)軌跡與移動(dòng)對(duì)象真實(shí)運(yùn)行軌跡的相似度較高。這是因?yàn)楸疚乃惴ú捎昧诉z傳算法尋找全局最優(yōu)解的特性，可以快速?gòu)囊苿?dòng)對(duì)象歷史軌跡數(shù)據(jù)集中得到軌跡行為模式，從而預(yù)測(cè)出當(dāng)前時(shí)間段內(nèi)移動(dòng)對(duì)象將要到達(dá)的位置點(diǎn)，并根據(jù)移動(dòng)對(duì)象實(shí)時(shí)新增的軌跡位置點(diǎn)動(dòng)態(tài)更新移動(dòng)對(duì)象的軌跡行為模式，進(jìn)一步提高預(yù)測(cè)軌跡與移動(dòng)對(duì)象真實(shí)運(yùn)行軌跡之間的相似性。而文獻(xiàn)[9,10,16]中的算法卻沒(méi)有考慮移動(dòng)對(duì)象實(shí)時(shí)新增位置點(diǎn)這一因素對(duì)預(yù)測(cè)軌跡的影響，從而使得預(yù)測(cè)出的預(yù)測(cè)軌跡與移動(dòng)對(duì)象真實(shí)運(yùn)行軌跡之間的相似性較低。

將本文算法與文獻(xiàn)[8,16]中的算法進(jìn)行實(shí)驗(yàn)對(duì)比，在設(shè)定相同軌跡數(shù)目、長(zhǎng)度和隱私需求的情況下，評(píng)測(cè)不同算法生成的匿名軌跡與真實(shí)運(yùn)行軌跡之間的相似度，結(jié)果如圖8所示。

Figure 8 Similarity between anonymous trajectory and real trajectory圖8 匿名軌跡與真實(shí)軌跡相似度

如圖8所示，比較不同算法在相同匿名條件下生成的匿名軌跡與真實(shí)軌跡之間的相似性，本文算法在起始階段生成的匿名軌跡與移動(dòng)對(duì)象真實(shí)軌跡相似性較低，這是因?yàn)樵谲壽E數(shù)目為200～800時(shí)，軌跡數(shù)目較少，遺傳算法進(jìn)行匿名軌跡構(gòu)建時(shí)的初始種群較小，因此本文算法的相似性較小，但隨著軌跡數(shù)目的不斷增加，初始種群不斷增大，相似性也逐漸上升。而當(dāng)軌跡數(shù)目達(dá)到一定閾值時(shí)，本文算法相比于其他幾種算法呈現(xiàn)出一定的優(yōu)勢(shì)，這是因?yàn)槲墨I(xiàn)[8,16]中的算法大多先對(duì)移動(dòng)對(duì)象的歷史軌跡進(jìn)行聚類(lèi)，然后進(jìn)行匿名軌跡構(gòu)建，沒(méi)有考慮對(duì)歷史軌跡信息的實(shí)時(shí)更新。

5.4 軌跡數(shù)據(jù)質(zhì)量

在軌跡數(shù)據(jù)發(fā)布中，既要保護(hù)移動(dòng)對(duì)象的隱私信息不被泄露，又要保證通過(guò)算法匿名后的匿名數(shù)據(jù)集具有一定的可用性。根據(jù)這一特性，本文在對(duì)匿名數(shù)據(jù)集的數(shù)據(jù)質(zhì)量進(jìn)行評(píng)估時(shí)分為軌跡隱私泄露概率和匿名數(shù)據(jù)質(zhì)量2部分，在評(píng)測(cè)軌跡數(shù)據(jù)質(zhì)量?jī)?yōu)劣時(shí)，本文選擇文獻(xiàn)[16,18]中的算法來(lái)做對(duì)比實(shí)驗(yàn)。

(1)軌跡隱私泄露。

通過(guò)軌跡隱私泄露概率對(duì)不同算法生成的匿名軌跡進(jìn)行驗(yàn)證，實(shí)驗(yàn)結(jié)果如圖9所示。

Figure 9 Disclosure probability of trajectory privacy圖9 軌跡隱私泄露概率

如圖9所示，在K值相同且具有相同背景知識(shí)的軌跡匿名數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果中，本文算法相較于其它2種算法的軌跡隱私泄露概率較低。這是由于本文算法在進(jìn)行軌跡隱匿時(shí)，依據(jù)移動(dòng)對(duì)象軌跡行為模式，提前對(duì)移動(dòng)對(duì)象的動(dòng)態(tài)軌跡進(jìn)行了預(yù)測(cè)，同時(shí)充分考慮了移動(dòng)對(duì)象軌跡動(dòng)態(tài)更新位置點(diǎn)這一因素對(duì)生成匿名軌跡的影響，提高了對(duì)預(yù)測(cè)軌跡匿名的具體指向，使得生成的匿名軌跡概化程度更好，降低了移動(dòng)對(duì)象軌跡隱私泄露的風(fēng)險(xiǎn)。

(2)匿名數(shù)據(jù)質(zhì)量。

對(duì)軌跡數(shù)據(jù)進(jìn)行匿名后的匿名數(shù)據(jù)集可用性越高，則證明該匿名數(shù)據(jù)集的數(shù)據(jù)質(zhì)量越好[1]。為評(píng)估不同算法生成的匿名數(shù)據(jù)集的可用性，隨機(jī)選擇匿名數(shù)據(jù)集中的N條軌跡，在設(shè)定同一K值的前提下，比較其匿名數(shù)據(jù)集的可用性。實(shí)驗(yàn)結(jié)果如圖10所示。

Figure 10 Anonymous data quality圖10 匿名數(shù)據(jù)質(zhì)量

如圖10所示，在同一匿名條件下，隨著軌跡數(shù)目的不斷增加，經(jīng)過(guò)匿名后的匿名數(shù)據(jù)集的數(shù)據(jù)質(zhì)量也在逐漸提高，相比于文獻(xiàn)[16,18]中的算法，本文算法的匿名數(shù)據(jù)質(zhì)量相對(duì)較高，這是因?yàn)槲墨I(xiàn)[16,18]中的算法是以移動(dòng)對(duì)象的歷史軌跡信息為基礎(chǔ)，沒(méi)有考慮移動(dòng)對(duì)象的軌跡動(dòng)態(tài)更新這一因素對(duì)數(shù)據(jù)質(zhì)量的影響。而本文算法在進(jìn)行匿名軌跡構(gòu)建時(shí)，充分考慮了動(dòng)態(tài)軌跡實(shí)時(shí)更新這一因素對(duì)數(shù)據(jù)質(zhì)量的影響，并結(jié)合與其相關(guān)的軌跡語(yǔ)義信息，進(jìn)行軌跡K-匿名，這樣既保護(hù)了移動(dòng)對(duì)象的軌跡隱私信息，又保證了匿名數(shù)據(jù)集具有較高的可用性。

6 結(jié)束語(yǔ)

針對(duì)現(xiàn)有的動(dòng)態(tài)軌跡隱私保護(hù)算法在對(duì)移動(dòng)對(duì)象的動(dòng)態(tài)軌跡進(jìn)行隱私保護(hù)時(shí)，大多采用先對(duì)移動(dòng)對(duì)象的歷史軌跡進(jìn)行聚類(lèi)，而后進(jìn)行軌跡隱匿，但沒(méi)有考慮實(shí)時(shí)增加的新位置或者新軌跡對(duì)動(dòng)態(tài)軌跡的影響問(wèn)題，本文提出了一種基于遺傳算法的動(dòng)態(tài)軌跡匿名算法。該算法利用遺傳算法對(duì)移動(dòng)對(duì)象的軌跡行為模式進(jìn)行構(gòu)建，以該行為模式為基礎(chǔ)，對(duì)移動(dòng)對(duì)象的動(dòng)態(tài)軌跡進(jìn)行預(yù)測(cè)，通過(guò)軌跡K-匿名技術(shù)生成匿名軌跡對(duì)預(yù)測(cè)軌跡進(jìn)行隱匿，從而達(dá)到保護(hù)移動(dòng)對(duì)象動(dòng)態(tài)軌跡隱私信息的目的。該算法在一定程度上解決了移動(dòng)對(duì)象動(dòng)態(tài)軌跡隱私泄露的問(wèn)題，但因遺傳算法中初始種群選擇這一因素的影響，依然會(huì)導(dǎo)致本文算法在算法效率上有所欠缺，這將是下一步亟待解決的問(wèn)題。