TFR-resm:一種基于可變區(qū)域相似點的新型軌跡隱私保護方法

任仲昊 耿雪冬 劉浩然

(山東科技大學計算機科學與工程學院 山東 青島 266590)

0 引 言

在高速發(fā)展的當今社會，隨著信息通信技術的不斷發(fā)展，智能設備的不斷更新?lián)Q代，人們在使用便捷的互聯(lián)網(wǎng)和網(wǎng)絡定位的同時，隱私泄露事件也時有發(fā)生，因此基于位置服務(LBS)已受到廣泛的關注[1-3]。因為用戶通過智能定位設備向服務器發(fā)送請求消息，服務器若想提供位置服務，需要獲取用戶的詳細的位置信息和請求內(nèi)容，但這些信息容易被攻擊者獲取[4]，導致用戶的隱私泄露，這樣不僅限制了位置服務的發(fā)展，也影響了廣大人群的日常生活，因此，保護隱私是至關重要的。

隱私保護主要分為位置隱私保護與軌跡隱私保護。位置隱私保護主要針對當前位置點進行隱私保護，而軌跡隱私保護，顧名思義，是針對用戶移動軌跡[5]中的請求信息進行有效的保護。本文方法主要是通過用戶之間的協(xié)作，構建K-匿名區(qū)域生成假軌跡[6]，進而完成真實用戶的偽裝，達到隱私保護的目的。

在隱私保護中，隱私保護方法雖多樣，但是其隱私保護不能夠面面俱到，主要的缺陷在于以下幾個方面：在構建匿名區(qū)域時，選擇使用K-匿名原則[7]，若當時信息請求用戶處于人口稀少的區(qū)域，會導致匿名區(qū)域中大多為不存在的虛擬點；若處于極端的地形[8]，如湖泊、海洋等也十分容易暴露；匿名區(qū)域的中心是否為信息請求用戶也是一個值得關注的問題，因為站在攻擊者的角度上，首先考慮中心點是否為真實用戶；最后，在構建軌跡時，若虛擬軌跡與真實軌跡的位置點個數(shù)或者移動方向偏差過多也容易導致隱私泄露。

基于以上的問題，TFR-resm(Two-dimensional Fluctuates in Range-Resemblance)方法在軌跡隱私保護上的創(chuàng)新主要體現(xiàn)在以下幾個方面：

(1) 避免直接使用信息請求用戶參與信息的發(fā)送，本文將使用相似用戶代替信息請求用戶發(fā)送消息，有效地降低隱私泄露的概率，即使攻擊者在掌握相關背景知識的情況下，依然不會找到真實的用戶，因為真實的用戶不存在于請求信息壓縮包中。

(2) 虛擬位置生成是絕大多數(shù)隱私保護方法都需要用到的技術。生成虛擬位置就需要劃定匿名區(qū)域，本文提出除去匿名區(qū)域中心的RMC-匿名區(qū)域法，該方法可以有效地解決信息請求用戶為匿名區(qū)域中心的問題。

(3) 為了能夠構建與真實軌跡相似度高的隱私混合軌跡，本文提出波動距離與波動角度，波動距離用于限制真實軌跡和混合軌跡在行動過程中的距離差，波動角度使得真實軌跡與混合軌跡在一定方向上高度一致，使得真實軌跡與混合軌跡相似度高。

(4) 在軌跡方面，本文使用相似用戶與虛擬用戶相結合的方法構建混合軌跡，在構建軌跡時，本文提出一種新的SMTA方法用來構建混合軌跡，該方法的優(yōu)勢在于能夠構建與真實用戶相似度高的混合軌跡。

1 相關工作

目前，軌跡隱私保護技術[9]主要分為泛化法、抑制法、假數(shù)據(jù)法三類。泛化法的軌跡隱私保護技術指將軌跡上所有的采樣點都泛化為對應的匿名區(qū)域，以達到隱私保護的目的。抑制法的軌跡隱私保護技術是指根據(jù)具體情況有條件地發(fā)布軌跡數(shù)據(jù)，并且不發(fā)布軌跡上的某些敏感隱私或頻繁訪問的位置以實現(xiàn)隱私保護。假數(shù)據(jù)的軌跡隱私保護技術是指通過添加假軌跡對原始數(shù)據(jù)進行干擾，同時又要保證被干擾的軌跡數(shù)據(jù)的某些統(tǒng)計屬性不發(fā)生嚴重失真。近些年，這些方法與技術在隱私保護方面得到了廣泛的應用。

文獻[10]提出了軌跡(k,e)-匿名模型來抵抗軌跡相似攻擊，該算法以軌跡斜率為敏感值進行構建軌跡，不同軌跡為一個等價類和要求不同軌跡的斜率至少是e。從安全角度看，該算法得到的軌跡(k,e)-匿名模型更能抵抗軌跡相似攻擊。但由于約束增強，導致信息損失略大。文獻[11]提出了一種基于道路網(wǎng)絡下分段假軌跡的軌跡隱私保護方法，該方法生成了不同時間內(nèi)真實軌跡采樣位置的偽位置，并在不同時間間隔內(nèi)生成分段偽軌跡。其劣勢在于路網(wǎng)非常復雜，攻擊者可能結合路段和背景知識威脅到用戶的隱私。文獻[12]提出一種基于緩存的用戶合作隱私保護方法，移動用戶先在合作用戶緩存中查找查詢內(nèi)容，當尋找失敗時才通過協(xié)作的方式向 LSP 發(fā)出查詢。但是LBS擁有不確定性，它不會一直保持可信任狀態(tài)。

文獻[13]提出了一種基于離線環(huán)境中原始跟蹤和已發(fā)布跟蹤之間相互信息的位置跟蹤隱私度量，并在給定的實用約束條件下，給出了最小化跟蹤級隱私泄漏的最優(yōu)位置跟蹤發(fā)布問題。還提出了一個隱私度量來捕獲在線設置中的跟蹤隱私泄漏，其實現(xiàn)的難點在于計算方面有較高的難度。文獻[14]提出了一種新的基于環(huán)境的位置隱私度量方法，并提出了一種隨機模型，該模型能夠捕捉到用戶路徑上的空間變化，缺點是不適用于多用戶和多任務。

文獻[15]提出了一種新的思想，針對軌跡隱私問題，基于用戶行為模式、軌跡相似度等背景信息增加了實時流量監(jiān)控。根據(jù)k匿名的思想，提出了一種結合交通條件保護軌跡隱私的方法。該文的劣勢體現(xiàn)在位置服務，還沒有有效的方法來衡量軌跡隱私保護的程度。

針對以上諸多的隱私保護問題，本文提出使用相似位置代替信息請求用戶發(fā)送請求消息，并且同時按照規(guī)則生成相關的虛擬位置點，滿足構建虛擬軌跡的數(shù)量。在構建軌跡時，真實用戶不在任何軌跡內(nèi)，這樣不容易被攻擊者獲取想要的信息。在每一時刻根據(jù)本文提出的波動角度與波動距離，尋找與真實用戶高度相似的相似位置，使得生成軌跡時，不容易被攻擊者排除，軌跡的每個時間點相似和虛擬點是隨機的，這就導致相似位置與虛擬位置點構造隱私軌跡。

2 基礎知識

2.1 基礎定義

定義1對于已知的地球表面上兩個經(jīng)緯度點，考慮地球橢圓形的外貌，兩點之間的實際距離記為SD，即經(jīng)緯間距，距離計算公式為：

(1)

式中：(Lung1,Lat1)表示A點經(jīng)緯度；(Lung2,Lat2)表示B點經(jīng)緯度；a=Lat1-Lat2為兩點緯度之差；b=Lung1-Lung2為兩點經(jīng)度之差；6 378.137為地球半徑，單位為km。

定義2假設在t時刻位置點為A(Lung1,Lat1)，在t+1時刻位置點為B(Lung2,Lat2)，此時B在緯度Lat2上的投影為B′(Lung2,Lat1)，存在夾角為∠BAB′，該夾角即位置點夾角，計算公式為：

(2)

定義3用p定義一個用戶的集合，其中包括位置點(Lung,Lat)、年齡age、性別gender和其他屬性，則用戶的信息集合記為p{(Lung,Lat),age,gender}。此時假設周圍存在的用戶，從中選擇相似位置點的方法記為相似度，公式為：

(3)

式中：P為兩個用戶在位置點上的距離S與權重ω1的乘積ω1×S；A為兩個用戶在年齡上的差值與權重的乘積ω2×(age1-age2)；G為兩個用戶在性別上與權重的乘積，同性別為0×ω3，否則為1×ω3；省略點表示其他相關的用戶特征；u為特征向量的個數(shù)。

計算相似度時，計算距離大小與年齡的參數(shù)，距離會起決定性作用，所以需要對數(shù)據(jù)規(guī)范化處理，使用最大-最小歸一化對原始數(shù)據(jù)進行線性變換使其規(guī)約在0～1之間。轉換函數(shù)如下：

(4)

式中：X為要歸一化的數(shù)據(jù)；Xmax為全體樣本數(shù)據(jù)的最大值；Xmin為全體樣本數(shù)據(jù)的最小值。

定義4假設真實軌跡與虛假軌跡一共有k條，第ti→ti+1時刻，真實軌跡的經(jīng)緯距離為disti，虛擬軌跡第j條軌跡的經(jīng)緯距離為distij，則軌跡距離差與兩線段角度θi表示相似度，即軌跡相似度，公式為：

(5)

s.t.Dist=max(disti,distij)

定義5信息熵[16-17]是跟所有可能性有關系的，每個可能事件的發(fā)生都有個概率。信息熵就是發(fā)生一個事件我們得到的信息量大小。在數(shù)學上，信息熵其實是信息量的期望，其公式如下：

(6)

式中：p(xi)代表隨機事件xi的概率。

2.2 相似用戶

本文為了能夠有效地保護真實用戶軌跡，避免構建的虛擬軌跡被攻擊者所識破，提出相似用戶的概念，使用相似用戶代替真實用戶與其他位置點一起發(fā)送請求消息。為了能夠更加有效地保護信息請求用戶的隱私，該相似用戶也是真實存在的一名用戶，該方法的優(yōu)點在于，即使攻擊者獲取到真實用戶的相關信息，相似用戶也可以混淆攻擊者的視線，因為相似用戶代替真實用戶發(fā)送消息并且也是真實存在的用戶。為了能夠尋找到滿足要求的相似用戶，本文給出了相關定義，通過定義3，計算軌跡初始化時間戳t0時刻得出相似用戶。

相似用戶的數(shù)據(jù)特征獲取方法一般來說有兩種，一種是當用戶使用某服務軟件或平臺時，搜索當前用戶周圍存在的真實用戶，搜索到的真實用戶即注冊使用過該服務的用戶，可以通過簡單的操作獲取基本特征信息(可參考WeChat、QQ等)；另一種是通過信任第三方(TTP)獲取用戶數(shù)據(jù)，TTP的數(shù)據(jù)收集模塊[18]可以獲取所有用戶的軌跡信息，可以輕易得到周圍用戶的特征信息。

相似用戶與真實用戶在各特征數(shù)據(jù)上需要高度一致，為了實現(xiàn)該目的，當使用數(shù)據(jù)時，首先要對數(shù)據(jù)進行處理，本文使用PCA降維技術和bridge線性回歸法，除去與本文實驗不相關的特征數(shù)據(jù)，并使用定義3計算相似性。假設真實用戶為男性，發(fā)送的信息請求為尋找男士單身俱樂部，若此時的相似用戶為女性，在性別上就不符合現(xiàn)實情況。攻擊者通過其相關手段獲取到用戶需要發(fā)送的信息，當選擇的相似用戶為女性時，該相似用戶起不到有效的保護作用。

當相似用戶代替真實用戶的請求消息時，此時就需要考慮相似用戶保護。本文認為相似用戶依然是不會存在隱私泄露風險的，原因有兩點：(1) 攻擊者的攻擊是有指向性的，攻擊者會針對某一用戶進行攻擊，專門對自己的目標進行信息收集，使用相關技術進行推測，獲取用戶的相關信息，對額外的相似用戶不會進行較多研究，因為相似用戶不是其真正的目標。(2) 在形成軌跡時，只是在初始位置擁有真實的相似用戶，在接下來的構建中，將會依照本文提出的波動角度與波動距離生成相似位置點，該點代替真實用戶發(fā)送消息，因此軌跡中真實用戶與相似用戶會進行重新命名。

假設當前為軌跡初始化階段，如圖1所示，當信息請求用戶發(fā)送消息時，開始搜索周圍存在的真實用戶，并使用本文定義的用戶相似度，得出圖1結論，可以看出用戶fen Cheng的相似度高于其他存在的真實用戶，則使用該用戶代替真實用戶發(fā)送消息。

圖1 用戶相似度

2.3 波動角度與波動距離

本文構建軌跡的核心問題就是如何在初始化時間戳后尋找后繼的相似位置點，只有相似位置點足夠滿足要求才能更好地保護信息請求用戶的隱私。因此，如圖2所示，若想構建與真實軌跡高度相似的軌跡[19]，準確的波動距離與波動角度是非常有必要的。波動距離和波動角度的計算可以概括為三步。第一步，依照本文提出的規(guī)則尋找相似位置點，如圖2所示。第二步，計算真實用戶在相鄰兩個時間戳所移動的軌跡和緯度形成的夾角。第三步，給與相似位置點和真實用戶相同的移動距離和移動角度，并加入波動距離與波動角度，使得形成扇形環(huán)區(qū)域，該區(qū)域為下一相似位置點的生成區(qū)域。

圖2 波動距離與波動角度

在波動角度方面，由本文的定義可知，當前時間點(假設不是初始時刻)的信息請求用戶與其前一時刻信息請求位置連線，然后與其當前點坐標(x,y)中y緯度形成夾角θ，再對當前位置點對緯度映射，形成直角三角形，可以輕易地得出當前夾角θ的大小。一個合適的波動夾角是非常重要的，如果夾角過大，則混合軌跡方向與真實用戶軌跡方向偏差過大；若夾角過小，可能會出現(xiàn)軌跡重合問題。

在波動距離方面，波動距離是兩個時間戳之間真實用戶行動軌跡的經(jīng)緯間距的變化。波動距離的大小也是非常重要的，因為波動距離過大，導致相似位置點的可取值范圍巨大，可能生成的相似位置與真實位置相似度不夠，若波動距離過小，會導致相似位置與真實位置在定位有誤差的情況下可能是重合的。

除此之外，在考慮到真實用戶每次行進距離是沒有規(guī)則并且長度是不一樣的，因此在計算波動距離與波動角度時，需要對其進行不斷的更新。因此本文對波動距離與波動夾角形成的扇形環(huán)面積定義大小，根據(jù)真實情況，將通過設定面積的大小和真實移動距離與角度不斷地更新波動角度與波動距離，達到本文的目的。

2.4 虛擬點與RMC-匿名區(qū)域

由于代替信息請求用戶發(fā)送消息的相似位置點只有一個，并且本文方法中，信息請求用戶是不存在于混合軌跡中，因此若不加入其他虛擬點，軌跡的數(shù)目只有一條。此時若加入虛擬位置點[20]，優(yōu)點不僅在于軌跡數(shù)量的增加，而且每條軌跡是相似位置點與虛擬位置點的組合，就會產(chǎn)生多種與真實軌跡相似的混合軌跡。

虛擬位置點的生成需要按照一定的規(guī)則，假設虛擬位置點生成的位置與信息請求用戶距離較大，攻擊者通過對目標收集的數(shù)據(jù)可以輕易地排除此虛假位置點，因此，虛擬位置點的生成也是非常重要的。本文選取真實用戶位置點所在的區(qū)域，在區(qū)域內(nèi)生成包括真實用戶和相似用戶在內(nèi)的矩形區(qū)域，該矩形區(qū)域記為虛擬位置點生成的區(qū)域，在矩形內(nèi)部隨機生成所需數(shù)量的虛擬點。

為了能夠有效地避免真實信息請求用戶為矩形匿名區(qū)域中心，本文提出新的匿名區(qū)域構建方法，即RMC-匿名區(qū)域法。首先需要通過以真實用戶為中心構建匿名區(qū)域，在構建完成匿名區(qū)域后，設定一個圓為矩形匿名區(qū)域的中心，然后向任意方向移動矩形匿名區(qū)域，使其中心的信息請求用戶落在矩形內(nèi)圓的范圍外，此時再按照上述的虛擬位置生成方法生成所需的虛擬位置點。

RMC-匿名區(qū)域構建步驟(以構建200 m×150 m匿名區(qū)域為例)：

步驟1以當前信息請求用戶的經(jīng)緯坐標為中心構建200 m×150 m的匿名區(qū)域空間。

步驟2根據(jù)匿名區(qū)域大小設定內(nèi)在圓的大小，建議面積大于匿名區(qū)域的四分之一。

步驟3保持內(nèi)在圓與匿名區(qū)域矩形相對位置不變，移動匿名區(qū)域，使得信息請求用戶落在圓外矩形內(nèi)，即內(nèi)在圓與矩形匿名區(qū)域相異的區(qū)間。

步驟4按照規(guī)則在匿名區(qū)域尋找相似用戶和生成虛擬位置點。

如圖3所示，圖中矩形的面積是通過與真實環(huán)境相結合共同確定的。在人口密集的區(qū)域，矩形的面積可以相對較小，因為人口稠密，若矩形的面積過大，導致虛擬位置點過于稀疏，攻擊者可以根據(jù)真實狀況排除虛擬位置點，反之亦然。

圖3 矩形匿名區(qū)域

2.5 混合軌跡構建方法SMTA

本文將由相似用戶與虛擬位置點一同構成的隱私軌跡稱為混合軌跡。在構建混合軌跡時，首先要做的是尋找相似位置，相似位置是構建軌跡最為重要的一步。在本文中，為了能夠找到與信息請求用戶足夠相似的相似用戶，提出用來尋找相似位置點的相似度，相似度不僅考慮到用戶的當前位置，而且為了與真實用戶能夠高度相似，還考慮到用戶的其他特征信息(如性別、年齡等)，用此尋找高度相似的相似位置。

在獲取到相似位置后，若想要構建n條混合軌跡，仍然需要生成n-1個虛擬位置點。虛擬位置點在上文中已詳細介紹，通過使用信息請求用戶為對角線交點的比例矩形生成虛擬位置點。在下一時刻，上一時刻的相似位置與虛擬位置和該時刻的其中任意一個的相似位置與虛擬位置點匹配相連，構成存在相似位置與虛擬位置相結合的混合軌跡。

2.6 軌跡命名

隱私軌跡中，為了保護軌跡不被輕易獲取，需要對真實用戶賦予假名操作，以避免攻擊者直接獲取到真實用戶的有關信息，這些是軌跡隱私保護中常用的技術，也是保護軌跡隱私的一個常識，但本文有所不同。

在本文的隱私保護中，隱私軌跡中是不存在信息請求用戶的，原因在于相似位置是信息請求用戶的替代位置，但仍需要對每一條軌跡賦予名字。本文構建一個詞袋，當在初始時刻尋找到相似位置點與構建虛擬位置點后，從詞袋中隨機取出一個名字賦予給每一個相似位置點和虛擬位置點，并且在本文實現(xiàn)對每一條軌跡命名時從詞袋中不放回地取出任意名字，避免出現(xiàn)軌跡名字相同的情況。通過賦予名字后，整條軌跡中所有的點都統(tǒng)一使用初始時間戳的名字，達到保護隱私的目的。

3 算法設計

3.1 場景分析

在軌跡隱私保護方法中，算法應該切合實際的應用場景。如圖4所示，本文假設張某外出旅行尋找加油站，首先在不知道加油站具體位置時，通過智能設備向服務器發(fā)送消息請求。其次，消息通過基站傳輸，當收到信息請求用戶的消息時，此時為了保護信息請求用戶張某的個人位置等信息不被泄露，使用本文提出的TDR-resm算法對張某的請求信息進行隱私保護，然后將其發(fā)送至LBS，LBS將接收的請求信息在數(shù)據(jù)庫中找到對應的應答，將消息返回。最終通過基站，用戶接收到自己請求的加油站位置。

圖4 場景應用

通過應用場景分析和綜合以往的隱私保護方法可知，本文的軌跡隱私保護方法TFR-resm可以分為三部分：

(1) 構建RMC-匿名區(qū)域，尋找相似位置點，生成虛擬位置點。

(2) 在構建好的匿名區(qū)域內(nèi)尋找相似用戶，代替其發(fā)送信息請求消息。

(3) 通過不同的時間戳和軌跡構建方法SMTA，構建混合軌跡。

3.2 確定波動角度和波動距離

由于原有的隱私軌跡保護的方法與技術不能夠有效地保護軌跡隱私，在眾多教授學者的不斷努力下，通過不同方式的創(chuàng)新改進隱私保護方法，使其能夠高效地保護隱私。本文經(jīng)過研究閱讀前人的工作，提出一種保護軌跡隱私的創(chuàng)新方法，而該方法的主要創(chuàng)新體現(xiàn)在尋找相似位置，波動角度與波動距離是尋找相似位置點的重要方法。

在現(xiàn)實生活中，信息請求用戶的運動軌跡在每一時刻是不同的(例如方向、速度等)，并且進行信息請求的時間差也是有所差距的，因此若固定的波動距離與角度將會導致扇形環(huán)面積差值過大，相似位置點與信息請求用戶的相似度變低。

本文為了改進這一問題，將先設定扇形環(huán)的面積(該面積的大小根據(jù)請求用戶真實情況設定)，通過面積不斷地調節(jié)每一時間戳的波動距離與波動角度。由于需要距離與角度兩個參數(shù)，我們通過扇形環(huán)的弧長公式與面積公式求出該參數(shù)：

(7)

式中：l是弧長；θ是真實用戶相鄰點與當前緯度扇形圓心角；R是真實用戶兩時間戳距離，視為扇形半徑。為了能夠更好地得出波動距離與波動角度，本文將扇形環(huán)面積近似為等腰梯形，則計算公式為：

(8)

式中：R為真實用戶相鄰時間戳的真實距離；θ為真實用戶相鄰點與緯度夾角；ΔR為波動距離；Δθ為波動角度；h為等腰梯形高；S為人工設置的扇形環(huán)面積。

在構建軌跡時，扇形環(huán)的面積是已知的常量，用戶可以根據(jù)當前位置的真實情況進行設定，假若在人口密集的區(qū)域，可以給扇形環(huán)面積設置小的值，這樣可以生成更有效的相似位置。反之，人口稀疏區(qū)域可以設置大的值。

3.3 相似位置尋找與虛擬位置點生成

在軌跡構建中本文使用到相似位置點與虛擬位置點，混合軌跡是由若干相似位置點和虛擬位置點組成。接下來本文將詳細講述如何計算生成相似位置點與虛擬位置點。相似位置點與虛擬位置點的生成是按照本文提出的算法公式得出，相似位置點是由相似度并通過計算每一時間戳的波動距離與波動角度確定相似位置點的生成區(qū)域而生成的。而虛擬位置點是按照矩形匿名區(qū)域的規(guī)則生成的，具體如算法1中所示。

算法1虛擬位置點算法

輸入：信息請求用戶user(x,y)，軌跡數(shù)量k，矩形面積Q。

輸出：相似位置點集合S，虛擬位置點集合V。

1. 初始化S,V為空集合

2.t=0

3.P=KdTree(user,n)

4. 根據(jù)式(3)，計算求得集合P中n個近鄰點中與信息請求用戶最相似的點S0,S0為相似位置點的初始值。

5.la/lb=C

6.Q=la*lb

7. Foriinrange(k) do

8.v=random(user(Δx,Δy))

9.v∈V

10. End for

11. Ift>0 do

12. 由式(8)計算可獲得波動距離Δd和波動角度Δθ

13.st=random(area(Δθ,Δd))

14.st∈S

15. End if

16. 重復生成虛擬位置點的步驟，在每一時刻都生成相似位置點集合V。

17. ReturnV,S

由算法1可知，生成相似位置點和虛擬位置點時，為了快捷地尋找相似用戶，避免遍歷整個數(shù)據(jù)集，首先，通過使用KdTree算法求得相近的n個用戶，再通過式(3)，得出其中最優(yōu)的相似用戶。其次，通過矩形匿名區(qū)域生成虛擬位置點。當初始化后，使用式(8)計算波動距離與波動角度，得出其他時刻的相似位置點，并且同時生成虛擬位置點，這樣就可得到軌跡在該時刻的相似位置點和虛擬位置點集合。

定理1算法1的時間復雜度為O(nlogn)。

證明1在算法1中主要的工作為軌跡初始化時尋找相似用戶，本文尋找近鄰的方法為KdTree算法，因此該算法的時間復雜度體現(xiàn)在KdTree算法上。通過分析KdTree算法可知算法1的時間復雜度，由于KdTree的結構為二叉樹，本文通過分析二叉樹的特征結合KdTree的特點能夠得出算法的復雜度，記為O(nlogn)，在此處logn底數(shù)取值為2，因此算法1的復雜度為O(nlogn)。

3.4 構建混合軌跡

混合軌跡的構建是本文的核心，構建軌跡使用到諸多的元素。首先，為了使信息請求用戶隱私不泄露，使用相似點代替信息請求用戶，而相似位置點不是隨意生成的，需要一定的規(guī)則，這就是本文提出的波動距離與波動角度。其次，因為位置點只有一個，但生成軌跡是多條，所以要生成虛擬位置點，虛擬位置點的生成也是受到一定原則約束，因為生成的虛擬位置點若與信息請求用戶相差甚遠，則容易排除。最后，為了能夠更好地保護隱私，本文構建軌跡時需要每條軌跡中既有相似位置點也需要有虛擬位置點，這樣避免攻擊者因為獲取用戶的一些背景知識而排除過多的混合軌跡。

軌跡構建過程(以構建3條軌跡為例)：

1) 初始位置生成，在真實用戶初始位置點的周圍一定范圍內(nèi)并且綜合相似度度量尋找一個相似位置與2個虛假位置。

2) 為了防止每條混合軌跡中n個位置點發(fā)送信息請求時ID相異，在生成初始位置后將對每條混合軌跡賦予一個新的代號，其整條軌跡從始至終使用它。

3) 構建其他位置點，假設當前位置點的時間戳為t2，計算此時間與上一時間的距離，除此之外仍需要計算兩者之間的連線與水平線(規(guī)定一個正方向為水平線，如正東)之間的夾角?；旌宪壽Et2，位置點的生成：(1) 確定波動距離；(2) 確定波動角度。

4) 假設此時已經(jīng)確定波動距離與波動角度，而且真實位置點與水平線的夾角為θ1，兩點之間的距離為d1?；旌宪壽E生成t2位置點，以混合軌跡的t1的位置點畫出與水平線夾角θ2，距離為d2的扇形環(huán)，從環(huán)中隨機選擇一個位置點，記為混合軌跡t2時刻的相似位置點。

5) 除步驟4)生成的虛擬位置點外，每一時間戳都會生成一個相似位置點，將會隨機從3個混合軌跡中選取一條軌跡，將此相似位置點加入該軌跡，方法如步驟6)。

6) 若算法選擇該條混合軌跡在t3時刻為相似位置點，則直接連接t2與t3時刻位置點，若下一時刻為虛擬位置點，則如步驟4)，否則如步驟6)。

7) 循環(huán)步驟4)-步驟6)，直至軌跡構建結束。

如圖5所示，圖中有3條軌跡，在矩陣中相似位置點和虛擬位置共有3個，在T1時刻，無論是相似位置點還是虛擬位置點都將隨機地匹配下一時刻T2中的任意類型點，遞歸生成混合軌跡，可以看出，生成的混合軌跡與真實用戶的軌跡相似度高，并且真實用戶不在混合軌跡中，可以有效地保護真實用戶不被攻擊。

圖5 混合軌跡的生成

算法2生成混合軌跡的算法

輸入：相似位置點集合S，虛擬位置點集合V，軌跡數(shù)量k，軌跡位置點數(shù)n。

輸出: 混合軌跡集合Tr。

1) 初始化Point集合為空

2) 由算法1得出相似位置點集合S與虛擬位置點集合V

3) Fori,jinzip(S,V) do

4)Point.extend(i,j)

5) End for

6)Tr={}

7) Deftrack():

8) Foriinrange(k)do

9)Tri,0=random(Point0)

10)Point0.pop(tri,0)

11) End for

12) End def

13) Foriinrange(n)do

14)track()

15) End for

16) ReturnTr

從算法2可知，首先，從算法1中獲取的相似位置點集合與虛擬位置點集合中選取各時刻的點，生成某一時間戳時刻的位置點集合，該集合包括一個相似位置點和多個虛擬位置點，其次，生成一個軌跡函數(shù)，通過調用n次該函數(shù)構建完整的混合軌跡。

定理2算法2的時間復雜度為O(k×n)。

證明2在混合軌跡構建中，組合虛擬位置點與相似位置點，需要遍歷軌跡中每一個時刻，假若混合軌跡中共有n個點，則該方法的復雜度為O(n)。在軌跡構造函數(shù)中未使用復雜度較高的方法或函數(shù)，復雜度為O(k)，最后在生成最終軌跡時，通過循環(huán)n次完成，所以算法2的時間復雜度為O(k×n)。

4 實 驗

本文使用的數(shù)據(jù)是gowalla數(shù)據(jù)集[21]，該數(shù)據(jù)集由微軟研究院發(fā)布。其收集了182個用戶從2007年4月到2012年8月的軌跡數(shù)據(jù)，數(shù)據(jù)按照嚴格的時間序列，生成了17 621條軌跡，共有48 000多小時的記錄。記錄了用戶的工作地點和戶外活動等。該數(shù)據(jù)集是用來進行用戶相似度估算、隱私保護、戶外推薦和數(shù)據(jù)挖掘的切合數(shù)據(jù)。

本文的實驗語言為Python，與語言相對應的軟件IDE為PyCharm64位Python3.6版本。IDE的運行環(huán)境為：Windows7 64位操作系統(tǒng)，處理器：Pentium(R) Dual-core CPU E5500 2.80 GHz。實驗將與假軌跡生成法[22]VR-track和軌跡旋轉法[23]ROT-track進行比較，進而體現(xiàn)本文算法的有效性和可行性。

如圖6，本文算法的時間耗時比虛擬軌跡法略高，比旋轉軌跡法低。因為在虛擬軌跡法中，虛擬軌跡的構建是尋找該時刻的查詢點，以兩點的距離建立誤差范圍，在誤差范圍內(nèi)構建匿名區(qū)域，生成滿足匿名等級的虛擬位置點的數(shù)量，而混合軌跡法與其相比，需要遍歷尋找相似位置點，在找到相似位置點后，為了能夠生成與真實軌跡足夠相似的混合軌跡，仍要計算本文提出的相似角度與相似距離，因此耗時要長。由圖6可以得出旋轉軌跡法比其他方法耗時都要長，原因主要有三方面，即選取最優(yōu)旋轉點、計算平移位置、考慮真實地形。

圖6 運行時間對比

在軌跡隱私保護中，軌跡的構建主要有兩點。即虛擬軌跡的方向和與真實軌跡之間的距離。有定義4，本文結合軌跡方向和軌跡距離的相似程度度量構建的虛擬軌跡與真實軌跡的相似度。如圖7所示，本文的混合軌跡比虛擬軌跡和旋轉軌跡與真實用戶的軌跡更加相似。虛擬軌跡使用的構建方法未能夠嚴格要求虛擬軌跡的方向，并且構建虛擬位置點的環(huán)狀區(qū)域過于廣泛，導致相似度低。在旋轉軌跡中，其優(yōu)勢在于軌跡是旋轉生成的，軌跡的形狀大小是與真實用戶軌跡完全一致，但是由于相同的軌跡不能夠在同一位置，為了避免軌跡重合需要對軌跡旋轉和平移，導致旋轉軌跡與真實用戶軌跡不能夠高度相似。

圖7 軌跡相似度

軌跡隱私匿名度主要是使用信息熵進行量化，熵值代表著不穩(wěn)定性，在隱私保護中，熵值越大代表軌跡隱私保護的效果越佳。如圖8所示，旋轉軌跡算法的信息熵最低，假設攻擊者得到的背景知識能夠解讀到用戶在某一時刻的真實請求信息位置點，攻擊者可以由此判斷出哪一條軌跡最貼近真實軌跡，出現(xiàn)該問題的原因在于，旋轉軌跡法中平移和旋轉導致生成的軌跡點與真實用戶位置點的地理位置有較大的偏差，容易被排除。本文使用了相似位置代替真實用戶發(fā)送消息，并且虛假位置是按照嚴格的生成方式生成，與真實用戶在地理位置有相似優(yōu)勢，即使攻擊者推測出真實用戶的真實位置的模糊區(qū)域，但由于相似位置代替真實用戶，仍然有效干擾攻擊者判斷，達到有效保護用戶隱私的目的。最后，虛假軌跡法中，軌跡的行進方向與真實軌跡相差較大，雖然能夠保護用戶的隱私，但是不能像本文算法一樣有效。通過對信息熵的分析，可以看出在匿名度低時，效率提高了5%，在匿名度高時，效率提高了15%左右，隨著匿名度的逐漸提高，效率差逐漸平緩。

圖8 軌跡保護算法信息熵對比

5 結 語

本文針對用戶軌跡隱私中軌跡容易暴露問題，提出一種構建虛擬軌跡的新方法。在該方法中，第一步是尋找與真實信息請求用戶相似度高的相似用戶代替其構建軌跡，并且同時按照生成規(guī)則生成多個虛擬位置點，在下一時刻，相似位置點與虛擬點隨機組合，如此循環(huán)構成相似位置點與虛擬位置并存的混合軌跡，并且給每條軌跡使用同一假名，完全達到軌跡隱私保護的目的。在實驗中，通過運行時間、軌跡相似度、匿名度的對比，體現(xiàn)出本文算法對軌跡隱私保護、抵制攻擊者的攻擊具有高效用。

隨著隱私保護數(shù)據(jù)量越來越大，本文接下來的研究工作的方向為降低尋找相似用戶生成相似位置點的復雜度和構建混合軌跡的時間消耗，解決這些問題將會使本文算法更加優(yōu)化。