基于預測位置的移動用戶位置隱私保護研究

李曉會+余建橋

摘要：近年來，位置隱私保護技術成為學術界研究的熱點。文章提出一種基于預測位置的位置隱私保護方案。該方案當用戶運行速度較高時采用預測位置作為用戶查詢的位置信息，以解決高速運動時由于查詢時間引起的查詢結果與需求結果不符的問題。實驗表明，預測位置模型適用于用戶運動速度不同的情況，抗攻擊能力更強，服務質量更好。

關鍵詞：預測位置；位置隱私；基于位置的服務；k-匿名；移動用戶

中圖分類號：TP301 文獻標識碼：A 章編號：1009-3044（2016）25-0022-04

Abstract： The location privacy protection technology has aroused general interest in recent years. This paper puts forward a location privacy protection scheme that bases on users predicted location. When a user is in high-speed operation， it takes the predicted location as the user current location， so as to solving the problem of inconsistent between the provided information and the demanded information， which is resulted from the different query time. The experiments show that the predicted location model is suitable for the situations with different users speed. At the same time， it has higher anti-attack capability and better service quality.

Key words： predicted location； location privacy； location-based services； K-anonymity； mobile users

1 概述

隨著具有GPS定位的移動設備的普及與發(fā)展，使得基于位置的服務[1]（Location Based Service， LBS）得到很大發(fā)展。LBS需要用戶發(fā)送位置信息給LBS服務提供商來獲得各種服務[2，3]。移動用戶查詢中由于位置頻繁變換，使LBS不間斷追蹤用戶當前位置，導致用戶位置信息越來越多地暴露給LBS服務提供商。如果攻擊者得到這些位置信息，會推斷出用戶敏感信息，造成用戶隱私泄露，因此提供LBS服務時保護用戶的位置隱私至關重要。

為了解決位置隱私保護問題，許多位置匿名方法已經(jīng)被提出[4-6]. 這些方法分為基于可信匿名服務器[5，7-11]和基于移動設備[12]的兩種結構。目前使用比較多的是基于可信匿名服務器結構。匿名服務器將用戶發(fā)送的確切位置泛化為匿名區(qū)域，使攻擊者不能確定用戶真實位置來保護用戶位置隱私。然而這些方法大多根據(jù)用戶發(fā)出查詢時位置構造匿名區(qū)域，沒有考慮移動用戶的運動性引起的位置變動，造成服務器返回結果偏離用戶實際需求。

在假設用戶不處于路口區(qū)域且運動速度超過設定值情況下，使用用戶經(jīng)過平均響應時間預測到達的位置作為用戶位置信息來構造匿名區(qū)域，最大程度降低由查詢響應時間引起的位置變動。

2 位置匿名系統(tǒng)結構

2.1 位置匿名

近年來，針對LBS用戶的位置隱私保護，已經(jīng)有許多位置匿名技術被提出[4]。其中最常用的是空間隱匿[4，6，8-10]和假位置[13]技術?？臻g隱匿技術大多使用位置k-匿名模型，該模型由Gruteser M[4]等人首次提出。其基本思想是當用戶提出位置服務請求時，將用戶的精確位置替換成一個覆蓋其他k-1個用戶的空間區(qū)域，使服務請求用戶不能與其他k-1個用戶區(qū)分開來。由于該文獻k值是系統(tǒng)設定不符合位置隱私個性化需求及沒有考慮位置k-匿名帶來的中心攻擊問題，所以文獻[5]，[6]分別提出可自行定制的k-匿名模型和使用盡可能小的網(wǎng)格構建盡可能小的匿名空間區(qū)域模型。但文獻[6]沒有考慮用戶的移動性，文獻[5]也僅適用于用戶移動速度較慢的情況。為此，文獻[7]在文獻[5]的基礎上提出一種基于V-grid模型的位置隱私保護方法。文獻[8]針對文獻[6]提出一種隨機匿名的位置隱私保護方法。

但以上文獻大多采用用戶查詢時所在位置構造匿名區(qū)域，未考慮用戶的移動性給位置隱私帶來的影響.文獻[7]雖然引入用戶的移動速度，但選用的與前一次更新位置的差值時間不符合移動用戶真實查詢響應時間。移動用戶高速運動時具有短時間行駛長位移特點，使現(xiàn)有位置匿名方法存在由查詢響應時間引起查詢結果與需求結果不符問題，需要選用更符合移動用戶運動規(guī)律的位置來構造匿名區(qū)域。

2.2 位置匿名系統(tǒng)結構

由于基于移動設備的兩層結構需要客戶端具備較高性能，因此目前位置匿名中使用比較多的是三層中心服務器結構。三層中心服務器結構包括移動客戶端（mobile client， MC）、位置匿名服務器（location anonymous server， LAs）、LBS服務器（LBS server， LBSs）三部分，如圖1所示。MC與LAs之間的通信經(jīng)過加密認證，對攻擊者來說是完全保密的；LAs與LBSs之間的通信是半可信的，攻擊者可能竊聽、截取通信信息[8]。

3 基于預測位置的位置隱私保護模型

3.1 系統(tǒng)結構

不同的位置隱私保護技術需要不同的系統(tǒng)結構，目前位置k-匿名技術多采用中心服務器結構，另外考慮到移動用戶與LBS服務器之間的通信帶寬非常有限，傳輸大的結果集時需要花費較高的響應時間，不能滿足LBS的實時性。因此采用三層中心服務器結構。

3.2 基于預測位置模型

預測位置模型（PLM）中LAs維護一份存儲用戶基本信息的用戶信息表，每個用戶對應表中一條記錄，當用戶首次連接LAs時，LAs為用戶新建一條記錄。LAs同時存儲空間區(qū)域內各路口位置信息，用IS表示路口的集合，，li表示第i個路口位置。由于用戶行至路口時速度可能都會有較大變化，不適于根據(jù)速度來計算預測位置，因此我們將路口位置li處理為半徑內的圓形區(qū)域CR，路口區(qū)域，在IR中采用用戶真實位置作為其位置信息。

為了計算方便，首先將空間區(qū)域劃分成大小相等的網(wǎng)格，Gi，j表示i行j列的網(wǎng)格，某一網(wǎng)格或幾個相鄰網(wǎng)格的面積構成網(wǎng)格區(qū)域（grid region， GR），與網(wǎng)格區(qū)域相鄰的網(wǎng)格的集合構建相鄰網(wǎng)格集（grid set， GS）。如下圖圖2所示，若當前用戶所在網(wǎng)格為G3，3，則 GR={G3，3}， GS={G2，3， G3，2， G3，4， G4，3}。若 G4，3 與 G3，3合并，那么GR={G3，3， G4，3}， GS={G2，3， G3，2， G3，4， G4，2， G4，4， G5，3}。

3.3 相關定義

定義1平均響應時間T。用戶的查詢響應時間是用戶發(fā)出查詢請求到接收到服務器響應之間的時間，用表示。，其中t1表示LAs對用戶位置進行匿名時間，t2表示LBSs查詢得出RCS的時間，t3表示LAs對RCS進行篩選結果的時間，表示三方的通信時間。平均響應時間為用戶之前查詢時間的平均值，用T表示，。當移動用戶向LAs發(fā)送查詢請求信息時會將此前統(tǒng)計的平均響應時間T一起打包發(fā)送給LAs。

定義 2真實位置&預測位置。真實位置是t時用戶當前所在位置，用表示；預測位置是指LAs根據(jù)用戶當前速度預測經(jīng)過平均響應時間T后到達的位置，用表示。預測位置的計算公式可表示為：

（1）式中v表示用戶當前移動速度，T為用戶發(fā)送的平均響應時間。

定義 3位置信息。位置信息是LAs存儲的用戶位置，用LI表示。LAs對用戶位置進行位置匿名時，根據(jù)服務器存儲的用戶位置信息構造匿名區(qū)域。首先LAs將用戶發(fā)來的真實位置進行存儲，其次判斷用戶是否在路口及是否超過設定速度值決定用戶預測位置的計算與存儲，最后根據(jù)存儲的位置信息表中預測位置是否為空判斷取真實位置亦或預測位置作為用戶位置信息。

定義 4位置信息可靠度。位置信息可靠度是位置信息距離用戶收到服務器響應時所在位置的遠近程度，以R表示，公式如下：

其中p為系統(tǒng)設定的距離收到服務器響應時所在位置的半徑長度，根據(jù)城市環(huán)境和公路環(huán)境的不同取值不同。px為查詢時預測的位置距離服務器響應時真實所在位置的距離長度。對R的計算根據(jù)px值不同分兩種情況：當時將R設為0，當時按公式計算，R值越大表示位置信息可靠度越高，其中px值可用兩點間歐氏距離表示。

4 基于預測位置的位置匿名保護算法

4.1 位置匿名保護算法

在使用預測位置模型（PLM）后，用戶的匿名區(qū)域搜索算法為：

4.2 抗攻擊性能分析

假設有一個請求LBS的移動用戶u，經(jīng)過位置匿名后匿名區(qū)域內用戶為{u，u1，u2，……，uk-1}，則攻擊者猜測該請求為真實用戶u請求的概率為1/k。

采用基于預測位置模型（PLM）算法后，由于攻擊者猜測的位置也有可能為用戶的預測位置，所以攻擊者猜測出用戶u的真實位置的概率為1/（2k），小于沒有采用基于預測位置模型算法時的概率，因此可以說采用基于預測位置模型算法后對抵抗攻擊者攻擊有明顯效果。

攻擊者可以利用各種信息獲得匿名區(qū)域及區(qū)域內用戶數(shù)，對以往的若攻擊者知曉某一區(qū)域內只有一個用戶，則可判斷該請求為用戶所發(fā)，在PLM模型中卻不能。因為該區(qū)域有可能是根據(jù)區(qū)域外某用戶的預測位置構造的，真實的提出請求用戶并未在匿名區(qū)域內，加大攻擊者攻擊難度。

5 實驗結果與分析

5.1 實驗環(huán)境及參數(shù)

實驗環(huán)境為Windows 7操作系統(tǒng)，處理器為intel i5-3470，主頻為3.2GHz，內存空間為4G。實驗使用Thomas Brinkhoff [14]開發(fā)的基于網(wǎng)絡的移動對象生成器隨機生成移動結點作為評估對象，模擬它們在德國古登堡市地圖上的行駛。

在實驗模型中，選定15*15km2作為實驗區(qū)域，并將其劃分為50*50的網(wǎng)格形狀，路網(wǎng)移動對象生成器生成隨機分布的5000個移動用戶，并從這些移動對象中隨機產(chǎn)生500個查詢請求用戶。實驗中令匿名值k改變，而其他參數(shù)取默認值并且保持不變，分別對速度為10m/s和20m/s的用戶進行實驗。實驗參數(shù)的范圍及默認值如表2所示。

5.2 結果分析

通過實現(xiàn)PLM模型算法及文獻[7]中V-grid模型算法的空間匿名，比較兩種模型隱私算法的位置信息可靠度、匿名成功率來查看PLM模型算法的有效性。

圖3為移動用戶不同行駛速度下的位置信息可靠度。當用戶低速v=10m/s行駛時，PLM算法與V-grid算法都采用用戶的當前位置構造匿名區(qū)域，因此位置信息可靠度相差不大。從圖3（b）看到RLM模型算法相比V-grid模型有更高的位置信息可靠度。這是因為匿名值k越大，一般而言需構造的匿名區(qū)域也越大，查詢響應時間也更長。當用戶以高速v=20m/s行駛時，由于V-grid算法根據(jù)當前時間與最近一次更新位置時間差值計算用戶位置，因此時間上會與真實查詢響應時間有偏差。而PLM中用戶設定匿名值k后平均查詢響應時間與真實查詢響應時間偏差不大，因此PLM的位置信息可靠度要高于V-grid算法。

通過對比可以知道，在用戶運行速度較快的情況下，預測位置模型可以產(chǎn)生很好的隱私保護效果。而當用戶速度不高時，PLM模型算法與V-grid模型算法性能相差不大。

圖4為不同速度情況下隨著匿名值k的增長匿名成功率的變化。一方面從（a）（b）兩圖看到，隨著匿名值的增大，兩種算法的匿名成功率都呈下降趨勢。這是因為當匿名值k增大，匿名服務器需要尋找更多的用戶構建匿名區(qū)域，而有時區(qū)域內或許沒有足夠多的請求用戶，從而導致匿名成功率下降。另一方面通過觀察（a）（b）兩圖，PLM算法相比V-grid算法匿名成功率相對更高。這是因為PLM采用的平均響應時間比V-grid采用的與上一次更新時間的差值更接近真實查詢時間，但由于同樣存在偏差，因此兩算法匿名成功率相比效果不是很明顯。

6 結束語

位置隱私保護的研究對于基于位置的服務的廣泛應用有著十分重要的意義。針對高速運動的用戶提出一種基于預測位置的位置隱私保護方法，以保護用戶的查詢質量。理論仿真證明，在隱私保護度較高的條件下，PLM算法與V-grid方法相比，在位置信息可靠度和匿名成功率上都有一定優(yōu)勢，因此在用戶運動速度較高的情況下，基于預測位置的位置隱私保護方法具有較好的隱私保護性能。

參考文獻：

[1] 周傲英， 楊彬， 金澈清，等. 基于位置的服務：架構與進展[J]. 計算機學報， 2011，24（7）：1155-1171.

[2] Krumm J. A survey of computational location privacy[J]. Personal & Ubiquitous Computing， 2009， 13（6）： 391-399.

[3] Jiao X， Yu L X， Yang X C， et al. A Location Privacy Preserving Approach on Road Network[J]. Chinese Journal of Computers， 2011， 34（5）：865-878.

[4] Gruteser M， Grunwald D. Anonymous Usage of Location-Based Services Through Spatial and Temporal Cloaking[C]// International Conference on Mobile Systems， 2003： 31-42.

[5] Mokbel M F， Chow C Y， Aref W G. The new Casper： query processing for location services without compromising privacy[C]// International Conference on Very Large Data Bases. VLDB Endowment， 2006： 763-774.

[6] Kalnis P， Ghinita G， Mouratidis K， et al. Preventing Location-Based Identity Inference in Anonymous Spatial Queries[J]. Knowledge & Data Engineering IEEE Transactions on， 2007， 19（12）： 1719-1733.

[7] 司超， 徐紅云. 基于V-grid模型的位置隱私保護方法[J]. 計算機工程， 2012， 38（12）： 276-278.

[8] Yang S， Ma C. Random anonymity method for location privacy protection[J]. Harbin Gongcheng Daxue Xuebao/journal of Harbin Engineering University， 2015， 36（3）： 374-378.

[9] Song D， Sim J， Park K， et al. A privacy-preserving continuous location monitoring system for location-based services[J]. International Journal of Distributed Sensor Networks， 2015， 11（2）： 1-10.

[10] Kim Y K， Hossain A， Hossain A A， et al. Hilbert-order based spatial cloaking algorithm in road network[J]. Concurrency & Computation Practice & Experience， 2013， 25（1）： 143–158.

[11] Cao W， Lv X U， Liu Y B， et al. The LBS system based on polygonal cloaking region[J]. 2015.

[12] Jung K， Jo S， Park S. A game theoretic approach for collaborative caching techniques in privacy preserving location-based services[C]// International Conference on Big Data & Smart Computing. IEEE， 2015： 59-62.

[13] Niu B， Li Q， Zhu X， et al. Enhancing privacy through caching in location-based services[C]// Computer Communications. IEEE， 2015： 1017-1025.

[14] Brinkhoff T. A Framework for Generating Network-Based Moving Objects[J]. Geoinformatica， 2002， 6（2）： 153-180.