移動社交網絡中的軌跡隱私PTPM保護方法

鄭振青，毋小省，王 輝，劉 琨，申自浩

(河南理工大學 計算機科學與技術學院，河南 焦作 454003)

1 概 述

近年來，隨著智能移動設備和移動應用的快速普及，為基于位置的服務(Location Based Service，LBS)[1，2]奠定了基礎.如今LBS服務已不僅僅應用于軍事，同時也廣泛應用于商業用戶.用戶使用移動設備(智能手機，平板等)通過位置服務查詢并獲取興趣點(points of interests，POIs)，在用戶使用位置服務帶來便利的同時，大量的位置信息在個人不知情的情況下被第三方收集、分析并加以利用.由于用戶移動軌跡中包含用戶眾多隱私信息，惡意攻擊者通過非法途徑獲取用戶的位置信息，進而推測出各類感興趣的事件和位置，造成用戶位置隱私泄露[3，4].因此在位置隱私保護中用戶軌跡隱私安全對用戶來說尤為重要.

為了保護軌跡隱私數據安全，在軌跡數據發布前，需使用適當的隱私保護技術對軌跡數據進行預處理[5].目前的軌跡隱私保護技術主要分為泛化法、抑制法和假數據法.1)泛化法，基于k匿名(k-anonymity)的方法是比較主流的泛化法.即對任意一條軌跡，至少需要k-1條其他軌跡被轉換成完全相同的匿名軌跡來構成一個匿名軌跡集合[6]，從而使惡意攻擊者無法對一個區域內的k個匿名用戶進行區分.該種方法在軌跡隱私保護中使用廣泛，并延伸出了不同的改進方法.2)抑制法，該方法在軌跡數據信息發布過程中，對敏感數據限制發布或經過轉換處理后發布，降低用戶數據的敏感性.3)假數據法，該方法生成用戶位置信息假數據并和真實數據進行混合，以此來降低用戶數據泄露的概率.但這些方法也有局限性，k匿名在連續位置查詢中安全性降低.抑制法抑制的點一旦過多，會影響發布數據的可用性，導致服務質量降低.假數據法易造成服務質量下降，查詢的準確度會受到一定的影響.另外惡意攻擊者利用已獲得的多個匿名數據，并根據掌握的相關背景知識有很大概率推測出移動用戶的隱私信息，攻擊者根據用戶發起的連續查詢位置信息，收集這些位置信息再重構出用戶軌跡，從而推測出用戶的工作地居住地甚至用戶的行為模式等敏感信息[7].

針對上述問題，本文提出一種個性化軌跡隱私保護方法(Personalized trajectory privacy protection method，PTPM)，主要貢獻如下：

1)在用戶移動端增加緩存區，緩存每次查詢得到的候選結果集，供用戶后續查詢使用.

2)在用戶和LBS服務器之間部署安全中心(Security Center，SC)和多匿名器，安全中心對用戶進行簽名注冊，并調配公私鑰對位置信息進行安全驗證.另外SC對同一用戶查詢信息進行拆分并發送給多匿名器，多匿名器對用戶信息進行隨機并發式k匿名，在安全性上有很大提升.

3)在LBS服務器端加入前綴樹，使用基于分簇數據融合隱私保護算法(Cluster-based Private Data Aggregation，CPDA)對數據庫位置信息進行加密保護，將位置信息經過加密處理生成密文，密文具有不可閱讀性，防止攻擊者非法入侵數據庫.并使用最優二叉樹算法查詢用戶POIs，提升用戶位置查詢效率.

2 相關工作

軌跡隱私保護方法中k匿名方法廣泛使用[8，9]，但是k匿名也存在如下缺點：1)在人群稀疏地區很難尋找k-1個匿名用戶來構建k匿名；2)k匿名方法一般只適用于查詢小范圍匿名域，若進行連續查詢，攻擊者通過分析多個連續的匿名區域中重復出現的用戶，從而可以鎖定并重構用戶的真實軌跡.

針對軌跡隱私中使用的匿名算法，國內外許多學者在傳統k匿名基礎上進行改進或創新，針對k匿名在連續查詢中的缺陷，文獻[10]提出了一種面向連續查詢的隱私保護方法.用戶與用戶之間通過移動設備附帶的無線功能進行短距離傳輸，從鄰近用戶的緩存信息中收集需要的信息，然后通過發布假的查詢信息與用戶的真實位置信息進行混淆.但是該方法在人群稀少地方增加了系統查詢時間.文獻[11]通過打亂路徑軌跡的順序性，然后在匿名區域進行匿名并隨機發送不同的軌跡給用戶，使惡意攻擊者無法重構用戶的真實軌跡，該方法可有效抵御惡意攻擊者的連續查詢攻擊.文獻[12]在基于位置服務查詢過程中，提出一種關于k匿名防止位置注入攻擊的隱私保護方法，它結合用戶的行為習慣建立可信的k匿名機制，使惡意攻擊者獲取真實用戶的概率僅為1/k.為了提升用戶的軌跡隱私安全性，文獻[13]針對用戶軌跡隱私保護方法Silent Cascade，提出一種新的軌跡隱私度量方法，文中引入了帶權無向圖，用來描述用戶的運動軌跡，并從信息熵的角度計算用戶的軌跡隱私水平.

基于點對點(peer to peer，P2P)的結構和基于可信第三方(fully-trusted third party，TTP)的中心服務器結構.他們大都有類似的模型對用戶的軌跡隱私進行保護，模型組成主要有3部分：用戶、第三方可信匿名器和LBS服務器.P2P結構中用戶與用戶之間相互可信，且用戶之間相互配合形成匿名域后再向LBS服務器發送位置請求[14]，該種方法中的點對點用戶并不能隨時保證每個地點有足夠的用戶來進行信息交互，而且匿名器負責處理所有用戶的位置信息和查詢內容，如果匿名器出現故障或被攻擊者攻破，對用戶軌跡隱私將會帶來嚴重的安全威脅.并且單個匿名器容易造成性能瓶頸.針對該種問題，文獻[15]提出了一種多匿名器保護方法，通過在用戶和LBS服務器之間部署多個匿名器，在連續查詢過程中，用戶分別隨機選擇不同的匿名器進行匿名.

軌跡隱私保護問題可以分為連續查詢中的軌跡隱私保護和數據發布中的軌跡隱私保護[16，17].多數文獻對軌跡隱私的保護采取的措施大都是針對數據傳輸過程中的保護，LBS是保存所有位置信息發布的終端設備，一旦被攻擊者攻破將泄露大量的位置隱私信息.為了防止攻擊者通過某些途徑鎖定LBS服務器中用戶的位置信息，在PTPM的LBS服務器端對位置信息使用CPDA進行加密保護，當需要查詢位置信息時通過SC調配公私鑰進行解密.

3 系統模型和相關定義

3.1 系統模型

PTPM軌跡隱私保護模型如圖1所示.

圖1 PTPM軌跡隱私保護模型

PTPM中包括用戶，安全中心SC，多匿名器和LBS服務器4類主要的實體模型.其具體的工作流程為：

1)用戶：用戶攜帶具有無線定位、無線通信功能的智能移動設備.將用戶所在的地理區域劃分成一個邊長為m的正方形二維平面，并將該區域劃分出g×g個網格單元.地理區域從左到右為x軸正方向，從下到上為y軸正方向.用戶緩存范圍為一個半徑為R的圓形區域.用戶發送位置查詢信息經過SC和多匿名器給LBS服務器，LBS服務器將查詢到的位置信息原路反饋給SC，SC規劃緩存區并發送給用戶，用戶接收位置信息使用移動設備緩存該區域，在該區域范圍內用戶不需要和LBS服務器交互.用戶移動設備定時向SC發送緩存區查詢，當用戶移動到緩存邊緣時繼續向LBS服務器發送查詢.

2)安全中心SC：安全中心為一個可信實體，主要負責存儲用戶移動端設定的隱私參數，并對位置信息進行加密.安全中心提前接收用戶發送的安全驗證并保存驗證信息.在用戶查詢位置信息時驗證用戶提前設定的隱私參數，并為用戶頒發數字證書PRu，PRu作為用戶的私鑰，另外安全中心給LBS服務器發送對應的公鑰PKu，公鑰與私鑰用于對位置信息加密解密.

3)多匿名器：多匿名器主要的作用是形成k匿名區域，以此來保證用戶位置信息數據在傳輸過程中的安全性.匿名器需要獲取用戶當前的位置信息，以便進行并發k匿名處理，SC將用戶查詢信息分為M份并隨機轉發給M個匿名器，每個匿名器對收到的位置信息片段單獨進行k匿名.

4)LBS服務器：LBS服務器能及時存儲和更新位置服務信息，使用前綴樹保存加密的位置信息，并為用戶提供各種位置數據服務.LBS服務器根據匿名器發送的匿名域范圍，查詢該區域內包含的POIs信息.另外LBS服務器根據用戶查詢興趣點，在數據庫查詢對應位置，將查詢到的位置信息使用公鑰加密經多匿名轉發給SC，SC規劃緩存區并發送給用戶，用戶移動端利用私鑰PRu對位置信息進行解密并求精.

3.2 相關定義

定義2.匿名緩存區.多匿名器形成的匿名區域由k個查詢點構成，用戶移動端緩存區需滿足以下條件，k-1個用戶的查詢點必須以查詢用戶為中心，設定最小半徑minr和最大半徑maxr.大于minr是為了保證匿名區的面積不能過小，若匿名區面積過小則匿名度不夠.小于maxr是為了保證匿名區的k個匿名成員不能過于分散，防止k匿名喪失對真實用戶查詢點的保護.

定義3.數據緩存隱私度量[18].根據信息熵對數據集的影響，基于緩存的隱私度量可表示為：

(1)

其中|Ecache|為緩存區域，|Eserver|表示向LBS服務器查詢的區域，g2表示劃分的網格數量，H(e)表示在查詢過程中查詢結果的不確定性.在用戶緩存區獲取過程中緩存區單元命中率可以表示為：

|Ecache|=ξ×(|Ecache|+|Eserver|)

(2)

將式(2)代入式(1)為：

(3)

從式(3)中可以看出，隱私度量值λ的大小和緩存區單元命中率ξ成正比，通過提高緩存命中率可以提高隱私度量值，準確獲取緩存區位置，可以減少用戶連續向LBS服務器查詢的次數，保障用戶軌跡隱私安全.

定義4.時間截點NT[19].匿名器搜索k-1個用戶進行k匿名時，如果在人群稀少的地方，在一定時間截點NT內搜索不到k-1個匿名用戶，則產生虛假位置來代替剩下難以搜索到的匿名用戶，用來限制匿名器在搜索k-1個匿名用戶上花費過多的時間.

定義5.虛假位置速度差spe.虛假位置與真實用戶在相同時間段內速度的差異性，在時刻ti-1和ti用戶對應的位置為posi-1和posi，相同時刻虛假位置對應的位置分別為fpi-1和fpi，則速度偏差為：

(4)

(5)

用Q表示用戶軌跡信息熵，用戶到達目的地總共查詢的次數為η.log2k為k匿名中最大信息熵，則Q定義為：

(6)

定義7.匿名前綴樹.定義tree=(ID，record，children，POI)，ID表示用戶標識，record為節點軌跡的位置記錄，children表示子節點，POI表示用戶查詢位置興趣點，前綴樹的構造、剪枝、重構等技術為可信第三方隱私保護模塊提供了可行性.

定義8.位置軌跡數據集.移動對象Ui的軌跡數據集URi由移動對象連續移動構成的時空序列L1→L2→…→Llengthi(1≤i≤n)，其中lengthi為數據集URi的長度，n為軌跡節點，用path來表示用戶的有序軌跡集.path={L1，L2，…，Ln}.

4 PTPM軌跡隱私保護方法

PTPM軌跡隱私保護過程，主要分為5個步驟，下面將分別進行介紹.

4.1 SC安全布局

1)用戶服務注冊：用戶首先使用移動設備向SC進行安全注冊，根據定義1，用戶身份標識ID和私鑰一起加密得到用戶驗證注冊信息DSC(IDk).SC接收用戶注冊信息保存在數據庫并向用戶發送私鑰PRu，同時SC生成公鑰PKu發送給LBS服務器.

2)用戶查詢認證：當用戶需要查詢POI時需要向SC驗證用戶注冊信息，用戶使用私鑰PRu對ID進行簽名得到SigPRu(ID)，SC通過SigPRu(ID)驗證用戶注冊信息DSC(IDk).驗證通過后，SC將SigPRu(ID)、用戶身份標識ID、以及用戶私鑰PRu一起進行加密，初步生成用戶位置請求消息DSC(IDk‖SigPRu(ID)‖PRu).

3)LBS服務器安全驗證：LBS服務器接收到DSC(IDk‖SigPRu(ID)‖PRu)后，使用PKu對請求信息進行驗證，驗證通過后對位置信息解密，查詢求精形成用戶POI信息.LBS結合PKu對查詢到的位置信息重新加密生成DSC(IDk‖SigPRu(ID)‖PRu‖PKu)，將該位置信息經過M個匿名器發送給SC，SC根據用戶查詢路徑，規劃緩存區并發送給用戶.

4.2 用戶移動端緩存查詢

用戶所在地理區域進行網格劃分.用戶緩存區定義為：

buffer←((locx1，locy1)，(locx2，locy2)，Gs，S)

(7)

(colummx，rowy)=([locxi-locx1]，[locyi-locy1])

(8)

其中：

(1≤i≤m，locx2-locx1≤

locxi-locx1，locy2-locy1≤locyi-locy1)

(9)

根據定義2，用戶查詢半徑R應滿足minr≤R≤maxr，并確定用戶端緩存查詢應局限在S區域范圍內，查詢的網格標識區限制在Gs地理區域內，如果能夠找到對應的(colummx，rowy)包含緩存區S，且滿足：

S≤columnx×rowy≤Gs，

(10)

則直接對候選結果集進行求精，并得到準確的用戶緩存區.如果未找到對應的緩存區，對該區域的網格標識區形成查詢集LOCh.

LOCh←{(columnx，rowy)}

1≤x≤m，1≤y≤m，1≤h≤σ

(11)

其中σ為移動軌跡緩存區需要緩存的次數.然后執行3.1節的2)生成用戶位置請求消息DSC(IDk‖SigPRu(ID)‖PRu).位置查詢緩存區最后需經SC重新規劃.一旦緩存區不滿足式(9)，需要重新查詢緩存區，根據定義3，分別將緩存區S、DSC(IDk‖SigPRu(ID)‖PRu)分別代入|Ecache|和|Eserver|，并根據式(3)可以判斷用戶緩存區查詢精度.

4.3 多匿名器位置匿名

(12)

通過隨機轉發機制將DLoc分為M份，每份都附帶有用戶唯一標識ID、當前位置信息等.隨機形成的M份子信息為：{(IDk1，DLoc1)，(IDk2，DLoc2)，…，(IDkM，DLocM)}.

根據定義6可知當Q越小，匿名度越高隱私保密程度越高.

4.4 LBS服務器位置信息加密與查詢

4.4.1 數據庫位置信息加密

用戶所查詢的POI信息以明文的形式保存在LBS數據庫中，為了保護LBS數據庫的數據安全，使用CPDA算法對數據庫中位置信息進行保護.根據定義7，前綴樹的節點record用來保存位置信息，葉子節點children用來表示路徑拐點位置信息.位置信息經過加密處理生成密文，具有不可閱讀性，防止攻擊者非法入侵數據庫獲取位置信息.當用戶需要查詢位置信息時又可以將密文經過解密處理，還原成明文.

數據在轉發前各節點需要對信息進行交換，節點A可表示為：

(13)

(14)

(15)

節點B和C將交換后的數據發給A，節點A構造一個滿秩的方程組ψ=G-1F，且：

F=[FA，FB，FC]

(16)

節點A包含所有的x，y，z和FA，FB，FC的值，經過上述公式的計算，得到加密位置數據信息，加密密文為(a+b+c).最后該加密軌跡匯總到數據庫等待LBS服務器后續位置信息解密和查詢.該算法在保證一定精確度的情況下，阻止外部節點竊取隱私信息.

4.4.2 位置信息查詢

為了提高用戶POI查詢精度和效率，本文引入最優二叉搜索樹算法進行搜索位置信息，根據定義8，path={L1，L2，…，Ln}，表示有序集path的二叉搜索樹利用二叉樹的節點來存儲有序集中的軌跡節點.在表示Path的二叉搜索樹中搜索一個興趣點POI時返回的結果有兩種形式：

1)在二叉搜索樹的內節點中找到L=Li；

2)在二叉搜索樹的葉節點中確定L∈(Li，Li+1).

設在第1種情形中找到元素L=Li的概率為bi；在第2種情形中確定L∈(Li，Li+1)的概率為ai.其中約定L0=-∞，Ln+1=+∞所以：

ai≥0，0≤i≤n；bj≥0，1≤j≤n；

(17)

(a0，b1，a1，…，bn，an)為軌跡path的存取概率分布.

在表示Path路徑的二叉搜索樹Tree中，設存儲位置興趣點Li的終點深度為ci；葉節點(Lj，Lj+1)的節點深度為dj則：

(18)

式(18)表示在二叉搜索樹Tree中進行一次搜索所需的平均比較次數.P為Tree中的平均路長，一般情況下，不同的二叉搜索樹的P是不相同的.

最優二叉搜索樹對于有序集Path及其存取概率分布(a0，b1，a1，…，bn，an)，在所有軌跡中根據用戶提供的興趣點POI，在所有有序集Path中能找到具有最小平均路長的軌跡.該方法能有效提升LBS服務器查詢效率.

LBS服務器查詢到對應的用戶POI，服務器通過公鑰PKu對查詢到的位置信息進行區域規劃并加密，形成用戶移動軌跡預測點UPath：

UPath=DSC(IDk‖QmPRu(ID)‖PRu‖PKu‖Path)

(19)

另外LBS服務器根據UPath查詢附近的興趣點網格集ρGrids并用匿名器公鑰PKu進行加密形成候選結果集LOCbuffer：

LOCbuffer←{ρGrids‖PKu}

(20)

4.5 用戶獲得查詢結果

用戶查詢POIs搜索算法如算法1所示：

算法1.用戶查詢POIs搜索算法：

輸入：{(IDk1，DLoc1)，(IDk2，DLoc2)，…(IDkM，DLocM)}

輸出：用戶興趣點POIs

1.for eachni≤M，{(IDk1，DLoc1)，(IDk2，DLoc2)，…(IDkM，DLocM)}∈DLoc；

2.for(S1，S2，…，SM)to(A1，A2，…，AM)；

3.definitionPath=(L1，L2，…，Ln)；

4.if(a0，b2，a1…，bn，an)為軌跡Path的存取概率分布；

5.search nodeUPathand searchLOCbuffer；

6.for update buffer to SC；

7.end forLOCh←{(colummx，rowy)}；

8.forUPathandLOCbufferto user；

9.user for thePRutoUPath；

10.Orientationpathfor user；

11.user getbuffer；

12.ifbufferbeyond equation(9)return to 1.

5 安全性分析

本節主要分析PTPM針對強攻擊者和弱攻擊者的抵御能力，并將多匿名器和LBS服務器視為強攻擊者，竊聽者視為弱攻擊者[20，21].

5.1 強攻擊模型與弱攻擊模型

1)強攻擊者攻擊模型

在PTPM中，強攻擊者可以從獲取的部分特定信息中推測出用戶的其他信息，在PTPM中多匿名器、LBS服務器可視為強攻擊者，如LBS數據庫因為某種原因將用戶敏感信息泄露給攻擊者；匿名器在用戶位置信息轉發過程中對用戶敏感信息進行分析，造成用戶位置信息泄露等情況.

2)弱攻擊者攻擊模型

在弱攻擊者攻擊模型中，惡意攻擊者對用戶個人信息掌握有限.在PTPM模型中弱攻擊通過竊聽用戶查詢信息，并利用相關背景知識對用戶位置信息進行分析，進而推斷獲取用戶的敏感信息.

5.2 抵御強攻擊者的連續查詢攻擊

用戶在第一次查詢位置信息時因為用戶端沒有緩存區，所以用戶需要發送查詢，查詢信息通過SC安全驗證后，利用多匿名器匿名再轉發給LBS服務器進行查詢，LBS服務器收到的查詢匿名域中至少包含k個用戶，強攻擊者能準確定位指定用戶的概率只有1/k.

在用戶軌跡的后續查詢過程中，用戶可以通過查詢緩存區直接得到查詢結果，此時用戶不需要與LBS服務器和多匿名器進行交互，因此在此期間強攻擊者將不能獲得用戶任何信息.所以PTPM能抵御強攻擊者的連續查詢攻擊.

5.3 抵御匿名器的攻擊

多匿名器主要負責對用戶位置信息進行匿名和轉發，在PTPM方法中用戶位置信息被隨機分割為多份，并隨機通過多匿名器進行轉發.單個匿名器試圖推斷用戶位置信息時，由于僅僅獲取的是部分位置信息片段，所以無法獲取用戶準確位置信息.即使多個匿名器共謀，由于用戶位置信息片段中含有標識ID和位置加密措施，沒有用戶的私鑰是無法獲取用戶當前位置信息的.

5.4 抵御LBS服務器的攻擊

LBS服務器管理用戶的查詢數據，在PTPM方法中用戶可以直接從緩存區獲取位置信息，在該過程中LBS服務器將無法獲取用戶的位置信息.另外在LBS數據庫中通過CPDA算法對位置信息進行加密處理，LBS服務器需要公私鑰配對才能查詢用戶的興趣點，在用戶多次查詢過程中由于匿名區的存在，LBS服務器很難將用戶多次的查詢結果進行匹配獲取用戶的軌跡信息.

5.5 抵御竊聽者的攻擊

用戶發送位置查詢信息通過SC加密后發送給匿名器，包括用戶簽名SigPRu(ID)、加密位置信息DSC(IDk‖SigPRu(ID)‖PRu)以及SC發布的安全證書等，這些信息中，由于私鑰掌握在用戶手中，且弱攻擊者掌握用戶信息有限，所以弱攻擊者無法得到用戶的精確位置.在多匿名器中位置信息被分為多份，弱攻擊者通過某些途徑得到部分片段也不能恢復用戶的精確位置信息.在LBS服務器端使用前綴樹將位置信息加密為密文，并利用最優二叉樹算法進行查詢，整個過程都需要公私鑰配對才能解密位置信息.弱攻擊者沒有對應公鑰也將無法獲得用戶的查詢信息.

6 實驗與結果分析

6.1 實驗數據及環境

本部分通過實驗驗證PTPM的實用性.本次實驗中的數據集來自Thomas Brinkhoff移動用戶軌跡生成器，使用德國奧爾登堡市交通網絡圖.實驗隨機生成10000個移動對象.實驗選取JERRY的移動軌跡作為實驗對象.多匿名器數量M=10～50個，表1為實驗參數.實驗通過Java編程實現，搭載Eclipse平臺.實驗環境為：Intel(R)Core(TM)i7-9750H CPU @2.6GHz，8.00GB內存，Microsoft Windows 10操作系統.

表1 實驗參數設置

實驗中移動交通網絡圖上生成的移動用戶分布情況如圖2所示.

圖2 實驗對象JERRY移動軌跡

實驗中選取移動用戶JERRY來測試安全模型的系統性能，包括緩存區的測試和安全性測試.圖2(a)、圖2(b)、圖2(c)分別為JERRY 3個時刻的位置查詢情況.

6.2 實驗參數變化對PTPM的影響

本節在實驗測試過程中改變緩存區半徑R、匿名度K、匿名器數量M和興趣點POIs等參數，分析對PTPM性能的影響.

如圖3所示，在R=1，POIs=10000時，通過改變匿名度K和匿名器數量M測試對PTPM性能的影響.由圖3可知系統時間開銷和通信開銷都隨著M和K值的增大而增大.M越大表示匿名器轉發的子信息越多，需要更多的匿名器轉發更多的數據，LBS服務器接收和查詢位置所需的時間和通信量就越大.另外K值越大匿名域就越大，匿名域內包含的匿名用戶就越多，相應的用戶通信量變大，系統需要更多的時間來處理用戶發送的位置信息.因此M或K越大，系統所需的時間開銷和通信開銷就越大.

圖3 匿名度及匿名器數量對PTPM性能的影響

如圖4所示，在M=20，POIs=10000時，通過改變緩存區半徑R和匿名度K測試對PTPM性能的影響.由圖4可知系統時間開銷和通信開銷都隨著R值和K值的增大而增大.因為R越大，用戶緩存區的用戶數量就越多，相應的發送位置查詢信息就越多，所以LBS服務器需要查詢的POIs就越多，系統需要更多的時間來處理和求精位置數據，相應的時間和通信開銷就越大.另外K值越大匿名域就越大，匿名域內包含的匿名用戶就越多，相應的用戶通信量變大，系統需要更多的時間來處理用戶發送的位置信息.因此，R值或K值越大，系統所需的時間開銷和通信開銷就越大.

圖4 緩存區半徑及匿名度對PTPM性能的影響

如圖5所示，在R=1，M=20時，通過改變興趣點POIs值和匿名度K值來測試對PTPM性能的影響.由圖5可知系統時間開銷和通信開銷都隨著POIs值和K值的增大而增大.在用戶查詢范圍內發送給LBS服務器的POIs越多，LBS服務器需要花費更多的時間來求精用戶的查詢興趣點，因此系統時間開銷越大.另外POIs越多在系統傳輸數據過程中，從LBS服務器到匿名器再到用戶相應的通信開銷也越大.另外K值越大匿名域就越大，匿名域內包含的匿名用戶就越多，相應的用戶通信量變大，系統需要更多的時間來處理用戶發送的位置信息.因此，POIs或K越大，系統所需的時間開銷和通信開銷就越大.

圖5 POIs及匿名度對PTPM性能的影響

6.3 LBS服務器安全性和查詢效率對比

由于LBS服務器中引入了前綴樹的概念，所以這里測試PTPM中的服務器與傳統LBS服務器進行對比，通過更改測試數據中的查詢點數量n，在僅使用一個匿名器的情況下，對比測試服務器查詢用戶查詢點所花費的系統時間.根據圖6(a)可知該PTPM中的服務器查詢效率是要優于傳統服務器的，主要原因是因為PTPM中LBS服務器利用最優二叉樹算法能最快且精確的找到最短的路徑軌跡.

通過對PTPM中LBS服務器和傳統LBS服務器進行位置查詢來測試保護程度，測試過程中人為模擬強攻擊者攻擊模型.在僅使用一個匿名器的情況下更改用戶查詢點數量n，測試使用同一條軌跡路徑.由圖6(b)分析，由于PTPM中LBS服務器包含公鑰PKu，并且LBS數據庫對位置信息進行CPDA加密保護，所以PTPM中LBS服務器安全性要優于傳統LBS服務器.

圖6 LBS服務器查詢效率與安全性對比

6.4 多匿名器與單匿名器性能對比

如圖7所示，實驗使用同一組數據測試多匿名器和單匿名器在轉發數據時的系統時間開銷對比，使用同一個用戶請求發送同樣的興趣點，測試數據經過多次測試取平均值.測試過程改變匿名度K來對比系統響應速度.

圖7 多匿名器和單匿名器性能對比

測試數據在測試之初不使用SC進行安全加密，在多匿名器的性能測試中，M個匿名器同時處理用戶發送的位置信息，并且多匿名器轉發的是用戶分割的子信息，在每個匿名器中單獨對子信息片段進行K匿名和轉發.相較于多匿名器，單個匿名器接收的是用戶發送的整個數據信息，在數據轉發過程中需要進行K匿名，信息轉發靈活性不足易造成性能瓶頸，特別是當轉發信息較多時容易產生延遲和擁堵.所以該PTPM中的多匿名器相較于傳統的單匿名器在數據轉發效率上有較大提升.

7 結束語

在軌跡隱私保護中，本文提出了一種軌跡隱私保護方法PTPM，通過在用戶移動端增加緩存區來減少和LBS服務器的信息交互，降低用戶位置隱私暴露的風險，同時提升了用戶位置查詢效率.在用戶和LBS服務器之間布置安全中心SC來獲取用戶的驗證信息，并產生公鑰和私鑰，通過配對來解密用戶的位置請求信息.安全性分析可知PTPM可有效阻止弱攻擊者監聽用戶隱私信息.另外多匿名器通過k匿名對用戶位置信息進行保護的同時，解決了單匿名器存在的安全隱患和性能不足問題.由于多匿名器對用戶進行并發式k匿名，能有效抵制匿名器、服務器監聽和竊聽者的攻擊.LBS服務器中引入前綴樹的概念，使用CPDA算法對數據庫位置信息進行明文加密，并通過最優二叉樹算法查詢位置信息.通過實驗驗證，該PTPM能有效提升用戶位置查詢效率并增強了用戶位置隱私的保護程度.由于該PTPM中增加了SC和多個匿名器，增加了系統維護難度，因此下一步的做法是優化安全算法，將安全中心算法移植到匿名器中.