任仲昊 耿雪冬 劉浩然

(山東科技大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院 山東 青島 266590)

0 引 言

在高速發(fā)展的當(dāng)今社會(huì)，隨著信息通信技術(shù)的不斷發(fā)展，智能設(shè)備的不斷更新?lián)Q代，人們?cè)谑褂帽憬莸幕ヂ?lián)網(wǎng)和網(wǎng)絡(luò)定位的同時(shí)，隱私泄露事件也時(shí)有發(fā)生，因此基于位置服務(wù)(LBS)已受到廣泛的關(guān)注[1-3]。因?yàn)橛脩敉ㄟ^(guò)智能定位設(shè)備向服務(wù)器發(fā)送請(qǐng)求消息，服務(wù)器若想提供位置服務(wù)，需要獲取用戶的詳細(xì)的位置信息和請(qǐng)求內(nèi)容，但這些信息容易被攻擊者獲取[4]，導(dǎo)致用戶的隱私泄露，這樣不僅限制了位置服務(wù)的發(fā)展，也影響了廣大人群的日常生活，因此，保護(hù)隱私是至關(guān)重要的。

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

在隱私保護(hù)中，隱私保護(hù)方法雖多樣，但是其隱私保護(hù)不能夠面面俱到，主要的缺陷在于以下幾個(gè)方面：在構(gòu)建匿名區(qū)域時(shí)，選擇使用K-匿名原則[7]，若當(dāng)時(shí)信息請(qǐng)求用戶處于人口稀少的區(qū)域，會(huì)導(dǎo)致匿名區(qū)域中大多為不存在的虛擬點(diǎn)；若處于極端的地形[8]，如湖泊、海洋等也十分容易暴露；匿名區(qū)域的中心是否為信息請(qǐng)求用戶也是一個(gè)值得關(guān)注的問(wèn)題，因?yàn)檎驹诠粽叩慕嵌壬希紫瓤紤]中心點(diǎn)是否為真實(shí)用戶；最后，在構(gòu)建軌跡時(shí)，若虛擬軌跡與真實(shí)軌跡的位置點(diǎn)個(gè)數(shù)或者移動(dòng)方向偏差過(guò)多也容易導(dǎo)致隱私泄露。

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

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

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

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

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

1 相關(guān)工作

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

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

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

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

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

2 基礎(chǔ)知識(shí)

2.1 基礎(chǔ)定義

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

(1)

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

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

(2)

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

(3)

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

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

(4)

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

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

(5)

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

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

(6)

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

2.2 相似用戶

本文為了能夠有效地保護(hù)真實(shí)用戶軌跡，避免構(gòu)建的虛擬軌跡被攻擊者所識(shí)破，提出相似用戶的概念，使用相似用戶代替真實(shí)用戶與其他位置點(diǎn)一起發(fā)送請(qǐng)求消息。為了能夠更加有效地保護(hù)信息請(qǐng)求用戶的隱私，該相似用戶也是真實(shí)存在的一名用戶，該方法的優(yōu)點(diǎn)在于，即使攻擊者獲取到真實(shí)用戶的相關(guān)信息，相似用戶也可以混淆攻擊者的視線，因?yàn)橄嗨朴脩舸嬲鎸?shí)用戶發(fā)送消息并且也是真實(shí)存在的用戶。為了能夠?qū)ふ业綕M足要求的相似用戶，本文給出了相關(guān)定義，通過(guò)定義3，計(jì)算軌跡初始化時(shí)間戳t0時(shí)刻得出相似用戶。

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

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

當(dāng)相似用戶代替真實(shí)用戶的請(qǐng)求消息時(shí)，此時(shí)就需要考慮相似用戶保護(hù)。本文認(rèn)為相似用戶依然是不會(huì)存在隱私泄露風(fēng)險(xiǎn)的，原因有兩點(diǎn)：(1) 攻擊者的攻擊是有指向性的，攻擊者會(huì)針對(duì)某一用戶進(jìn)行攻擊，專門對(duì)自己的目標(biāo)進(jìn)行信息收集，使用相關(guān)技術(shù)進(jìn)行推測(cè)，獲取用戶的相關(guān)信息，對(duì)額外的相似用戶不會(huì)進(jìn)行較多研究，因?yàn)橄嗨朴脩舨皇瞧湔嬲哪繕?biāo)。(2) 在形成軌跡時(shí)，只是在初始位置擁有真實(shí)的相似用戶，在接下來(lái)的構(gòu)建中，將會(huì)依照本文提出的波動(dòng)角度與波動(dòng)距離生成相似位置點(diǎn)，該點(diǎn)代替真實(shí)用戶發(fā)送消息，因此軌跡中真實(shí)用戶與相似用戶會(huì)進(jìn)行重新命名。

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

圖1 用戶相似度

2.3 波動(dòng)角度與波動(dòng)距離

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

圖2 波動(dòng)距離與波動(dòng)角度

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

在波動(dòng)距離方面，波動(dòng)距離是兩個(gè)時(shí)間戳之間真實(shí)用戶行動(dòng)軌跡的經(jīng)緯間距的變化。波動(dòng)距離的大小也是非常重要的，因?yàn)椴▌?dòng)距離過(guò)大，導(dǎo)致相似位置點(diǎn)的可取值范圍巨大，可能生成的相似位置與真實(shí)位置相似度不夠，若波動(dòng)距離過(guò)小，會(huì)導(dǎo)致相似位置與真實(shí)位置在定位有誤差的情況下可能是重合的。

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

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

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

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

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

RMC-匿名區(qū)域構(gòu)建步驟(以構(gòu)建200 m×150 m匿名區(qū)域?yàn)槔?：

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

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

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

步驟4按照規(guī)則在匿名區(qū)域?qū)ふ蚁嗨朴脩艉蜕商摂M位置點(diǎn)。

如圖3所示，圖中矩形的面積是通過(guò)與真實(shí)環(huán)境相結(jié)合共同確定的。在人口密集的區(qū)域，矩形的面積可以相對(duì)較小，因?yàn)槿丝诔砻?，若矩形的面積過(guò)大，導(dǎo)致虛擬位置點(diǎn)過(guò)于稀疏，攻擊者可以根據(jù)真實(shí)狀況排除虛擬位置點(diǎn)，反之亦然。

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

2.5 混合軌跡構(gòu)建方法SMTA

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

在獲取到相似位置后，若想要構(gòu)建n條混合軌跡，仍然需要生成n-1個(gè)虛擬位置點(diǎn)。虛擬位置點(diǎn)在上文中已詳細(xì)介紹，通過(guò)使用信息請(qǐng)求用戶為對(duì)角線交點(diǎn)的比例矩形生成虛擬位置點(diǎn)。在下一時(shí)刻，上一時(shí)刻的相似位置與虛擬位置和該時(shí)刻的其中任意一個(gè)的相似位置與虛擬位置點(diǎn)匹配相連，構(gòu)成存在相似位置與虛擬位置相結(jié)合的混合軌跡。

2.6 軌跡命名

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

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

3 算法設(shè)計(jì)

3.1 場(chǎng)景分析

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

圖4 場(chǎng)景應(yīng)用

通過(guò)應(yīng)用場(chǎng)景分析和綜合以往的隱私保護(hù)方法可知，本文的軌跡隱私保護(hù)方法TFR-resm可以分為三部分：

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

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

(3) 通過(guò)不同的時(shí)間戳和軌跡構(gòu)建方法SMTA，構(gòu)建混合軌跡。

3.2 確定波動(dòng)角度和波動(dòng)距離

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

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

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

(7)

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

(8)

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

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

3.3 相似位置尋找與虛擬位置點(diǎn)生成

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

算法1虛擬位置點(diǎn)算法

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

輸出：相似位置點(diǎn)集合S，虛擬位置點(diǎn)集合V。

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

2.t=0

3.P=KdTree(user,n)

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

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)計(jì)算可獲得波動(dòng)距離Δd和波動(dòng)角度Δθ

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

14.st∈S

15. End if

16. 重復(fù)生成虛擬位置點(diǎn)的步驟，在每一時(shí)刻都生成相似位置點(diǎn)集合V。

17. ReturnV,S

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

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

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

3.4 構(gòu)建混合軌跡

混合軌跡的構(gòu)建是本文的核心，構(gòu)建軌跡使用到諸多的元素。首先，為了使信息請(qǐng)求用戶隱私不泄露，使用相似點(diǎn)代替信息請(qǐng)求用戶，而相似位置點(diǎn)不是隨意生成的，需要一定的規(guī)則，這就是本文提出的波動(dòng)距離與波動(dòng)角度。其次，因?yàn)槲恢命c(diǎn)只有一個(gè)，但生成軌跡是多條，所以要生成虛擬位置點(diǎn)，虛擬位置點(diǎn)的生成也是受到一定原則約束，因?yàn)樯傻奶摂M位置點(diǎn)若與信息請(qǐng)求用戶相差甚遠(yuǎn)，則容易排除。最后，為了能夠更好地保護(hù)隱私，本文構(gòu)建軌跡時(shí)需要每條軌跡中既有相似位置點(diǎn)也需要有虛擬位置點(diǎn)，這樣避免攻擊者因?yàn)楂@取用戶的一些背景知識(shí)而排除過(guò)多的混合軌跡。

軌跡構(gòu)建過(guò)程(以構(gòu)建3條軌跡為例)：

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

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

3) 構(gòu)建其他位置點(diǎn)，假設(shè)當(dāng)前位置點(diǎn)的時(shí)間戳為t2，計(jì)算此時(shí)間與上一時(shí)間的距離，除此之外仍需要計(jì)算兩者之間的連線與水平線(規(guī)定一個(gè)正方向?yàn)樗骄€，如正東)之間的夾角?；旌宪壽Et2，位置點(diǎn)的生成：(1) 確定波動(dòng)距離；(2) 確定波動(dòng)角度。

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

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

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

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

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

圖5 混合軌跡的生成

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

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

輸出: 混合軌跡集合Tr。

1) 初始化Point集合為空

2) 由算法1得出相似位置點(diǎn)集合S與虛擬位置點(diǎn)集合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中獲取的相似位置點(diǎn)集合與虛擬位置點(diǎn)集合中選取各時(shí)刻的點(diǎn)，生成某一時(shí)間戳?xí)r刻的位置點(diǎn)集合，該集合包括一個(gè)相似位置點(diǎn)和多個(gè)虛擬位置點(diǎn)，其次，生成一個(gè)軌跡函數(shù)，通過(guò)調(diào)用n次該函數(shù)構(gòu)建完整的混合軌跡。

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

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

4 實(shí) 驗(yàn)

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

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

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

圖6 運(yùn)行時(shí)間對(duì)比

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

圖7 軌跡相似度

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

圖8 軌跡保護(hù)算法信息熵對(duì)比

5 結(jié) 語(yǔ)

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

隨著隱私保護(hù)數(shù)據(jù)量越來(lái)越大，本文接下來(lái)的研究工作的方向?yàn)榻档蛯ふ蚁嗨朴脩羯上嗨莆恢命c(diǎn)的復(fù)雜度和構(gòu)建混合軌跡的時(shí)間消耗，解決這些問(wèn)題將會(huì)使本文算法更加優(yōu)化。