移動用戶位置信息處理及保護模型PTID

王艷 張明 劉衛杰

【摘要】 本文在分析移動用戶位置信息產生機制、數據特點和安全隱患的基礎上，結合現有位置信息保護方法，提出了一種基于用戶差異性的位置信息保護模型，并對模型的先進性進行了驗證。

【關鍵詞】 位置信息 軌跡 保護方法 PTID

一、引言

隨著無線通信技術的不斷發展，位置信息在即時通信、智能監控等領域的應用越來越多，極大的提高了數據利用效能。位置信息的特性使得對其進行處理和保護的方法不同于傳統數據庫數據，特別是包含更多可挖掘內容的軌跡信息，因此對位置信息保護方法進行研究刻不容緩。

二、位置信息

2.1 定位技術分類

根據用戶位置信息獲取方式的不同和用戶對基于位置的服務需求的不同，將移動用戶大致分為三類：

1）使用衛星定位技術實現位置定位的用戶。包括手持衛星定位設備、車輛、飛行器和開啟衛星定位功能的智能移動終端等，特點是定位精度較高，但衛星信號易受云層、樹木、建筑物等遮蓋物的干擾。

2）使用移動運營基站實現位置定位的用戶。使用GSM、CDMA 等運營網絡實現定位的用戶，基站根據用戶與基站間的距離測算用戶位置，定位精度與用戶所在區域范圍內的基站數量有關，基站數量越多，定位精度越高。

3）使用其他定位技術的用戶。不使用衛星定位模塊、不與運營基站進行通信的設備也可以實現定位功能，其中一種方法是利用無線網絡來實現。每一個無線AP的MAC地址是全球唯一的，并且無線AP在短時間內一般不會大范圍移動，因此，服務器可以根據信號的強弱計算設備的位置。

2.2 位置信息特點

與傳統數據庫中的關系數據相比，移動用戶的位置信息具有一些新的特性。

1、位置信息具有不精確性。

（1）信息采集引起的不精確。當有高架、云層、樹木、建筑物等遮擋物時，衛星信號會受到干擾，甚至無法實現定位，從而導致位置信息偏差較大。

（2）網絡延遲引起的不精確。無論數據更新策略如何優化，數據傳輸和設備處理過程中的延遲是不可避免的，嚴重時還會產生傳輸和處理瓶頸，因此數據庫中的位置信息與用戶實際物理位置會存在一定的偏差。

2、位置信息具有較高的時效性。

使用位置服務的用戶在請求服務時一般都是在線等待結果，如果服務器不能在極短的時間內反饋正確的結果，不僅會失去服務意義，而且會導致用戶對應用服務失去信心。

3、位置信息的傳輸具有極高的隱蔽性。

按照用戶對基于位置服務需求的不同，位置信息的發出行為可分為主動和被動兩種類型。有基于位置服務需求的用戶會主動發出位置信息，并且用戶對這一行為是了解的；另外一類用戶并沒有服務需求，但其擁有的設備仍然向外發送位置信息，而用戶可能并不知道這種行為的發生。后一種情況可能是由設備系統設置引起的，也可能是因為用戶的過往行為引起的。無論哪種形式，設備一般會主動記憶用戶的初始選擇而執行，在后繼發送過程中不主動在人機交互界面提醒用戶，因此位置信息的發送行為都具有極高的隱蔽性。

4、位置信息具有更高的隱私性。

位置信息不僅包含何時、何地、何人等基本要素，同時還可能包含其他隱含內容，如運動參數、導航信息、使用目的、物理環境和系統屬性等。隨著數據挖掘技術的不斷發展，從隱含內容中挖掘用戶更多的隱私越來越容易，這就對位置信息的采集、處理和保護提出了更高的要求。

三、PTID保護模型

基于上述位置信息數據特點，本文提出一種基于用戶差異性的軌跡保護模型PTID（Protecting model of trajectory integrating the differences of sensitivity）。模型采用中心服務器結構，在數據處理環節采用（s，C，K）L匿名方法提高匿名度，在數據發布環節對數據進行局部抑制，在減小軌跡數據隱私泄露風險的同時最大程度的保證數據可用性。

3.1（s，C，K）L匿名

定義1 （s，C，K）L匿名 給定軌跡數據表T，敏感屬性集S， L-背景知識的子集q（0<|q|

1、|T（q） | ≥K；

2、 s∈S，Ro （s|T（q））≤C。

PTID保護模型大致包括兩個步驟：

（1）對軌跡數據表T中所有不符合（s，C，K）L匿名要求的序列進行確定。

（2）執行一系列全局和局部抑制，在最大限度保證數據可用性的同時對軌跡數據進行匿名。

3.2數據預處理

3.2.1相關定義

1）頻繁序列和最大頻繁序列

非空序列在軌跡數據表中出現的次數稱為序列支持度。

給定支持度閾值K（ K>0），若非空序列q在表中的支持度大于K，則稱q是頻繁序列。

給定支持度閾值K，若q在表中是頻繁序列，但q的子序列在表中不是頻繁序列，則稱q為最大頻繁序列。PTID提取最大頻繁序列代替提取頻繁子序列，極大的減少算法復雜度。

2）違和序列

軌跡數據表中不滿足 （s，C，K）L定義中任一或全部條件的非空序列稱違和數據。

設想，如果數據表中的所有違和序列均被抑制，則抑制后的數據滿足抵御身份連接攻擊和屬性連接攻擊的要求，即可能泄露隱私安全的因素均被剔除了。這種方法在理論上是可行的，實際上，按照違和序列的定義，違和序列的非空真子 集也是違和序列，違和序列的規模可能極大，由此產生計算瓶頸使得方法的可操作性不強，因此提出最小違和序列。

3）最小違和序列

如果違和序列q的任意非空子序列都不是違和序列，則稱q為最小違和序列，最小違和序列集的規模遠小于違和序列集的規模。經過證明，對表中所有最小違和序列進行抑制同樣可以滿足匿名要求，則對表進行（s，C，K）L匿名的工作轉化為對最小違和序列的確定和抑制。

3.2.2最小違和序列的抑制

尋找抑制最優解是一個NP難題，因此本文提出一種綜合考慮全局抑制和局部抑制的貪心函數S（p），尋找數據抑制和可用性之間的平衡。

S（p）=P（p）/（U（p）+1）

式中：

P（p）——通過抑制p而刪除掉的最小違和序列的數量；

U（p）——通過抑制p而丟失的實例數量。

經證明，全局抑制可以在滿足PTID要求的前提下不產生新的最小違和序列，但在局部抑制中，這一結論并不成立。

3.3 匿名算法

3.3.1算法

輸入：軌跡數據表T，閾值參數s，C ，K， L，最小違和序列序列m中的p。

輸出：滿足（s，c，k）l 要求的表T 。

1：生成最小違和序列集V（T）；

2：生成最大頻率序列MFS并構建最大頻率序列樹MFS-tree；

3：構建分數表S-table；

4：while S-table≠Φ do

5： 從MFS m中選擇分數最高的序列p；

6： if p 是由局部抑制得來的then

7： V<—滿足p∈m∧T（m） = T（m）的每個最小違和序列m；

8： 將p 從T（m）中刪除；

9： 抑制后，包含p的最小違和序列支持度若

10： else

11： V<—V（p）；

12： 對T中的p進行抑制；

13： 從MFS-tree中將包含p的MFS；

14： 如果 p和p 同在 V 中或同在一個MFS中，更新分數表；

15： V（T） = V（T） – V；

16：return 抑制后的數據表T；

四、抑制試驗和結果分析

采用微軟亞洲研究院的研究項目Geolife數據集中包含了歷經48000多個小時、120多萬公里的17621條軌跡記錄作為試驗數據，數據由178名志愿者在2007年 4月至2011年10月間的GPS信息組成。

4.1數據處理

試驗數據的處理主要包括以下內容：

1）排除軌跡中北京地區以外的少數軌跡特異點對實驗結果直觀性的影響，將這些特異點排除。

2）對數據表中的冗余數據進行刪除處理。

3）對原始軌跡敏感性和用戶查詢請求敏感性進行量化。

4）確定合理的采樣頻率。

5）對軌跡進行局部抑制，得到“安全”的軌跡數據。

4.2軌跡對比分析

圖1所示為抑制前后軌跡對比圖，（a）為原始軌跡路線圖，（b）為局部抑制后的軌跡。

從圖1中可以看出，全局抑制的數據丟失率較高，軌跡失真明顯，局部抑制保留了軌跡運動的整體特征，數據可用性較高，同時對用戶在停留區域內的關鍵信息進行了隱藏處理，較好的保護了用戶隱私。

五、結束語

文章從移動用戶分類和位置信息產生原理出發，在分析移動用戶位置信息特點的基礎上，提出了一種全新的基于用戶差異性的軌跡保護方法模型，并對比證明了模型的先進性，在下一步的研究工作中，要進一步完善模型結構，重點對軌跡的敏感性量化方法進行深入研究。

參 考 文 獻

[1] Ilarri S， Mena E， Illarramendi A. Location-dependent query processing： Where we are and where we are heading[J]. ACM Computing Surveys （CSUR）， 2010， 42（3）： 12.

[2] 霍崢，孟小峰，軌跡隱私保護技術研究.計算機學報，2011，34（10）.

[3] 霍崢，孟小峰，黃毅.PrivateCheckln 一種移動社交網絡中的軌跡隱私保護方法.計算機學報，2013，36（4）.[4] http：//research.microsoft.com/en-us/projects/geolife/.