王艷 張明 劉衛(wèi)杰

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

【關(guān)鍵詞】 位置信息 軌跡 保護方法 PTID

一、引言

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

二、位置信息

2.1 定位技術(shù)分類

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

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

2）使用移動運營基站實現(xiàn)位置定位的用戶。使用GSM、CDMA 等運營網(wǎng)絡(luò)實現(xiàn)定位的用戶，基站根據(jù)用戶與基站間的距離測算用戶位置，定位精度與用戶所在區(qū)域范圍內(nèi)的基站數(shù)量有關(guān)，基站數(shù)量越多，定位精度越高。

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

2.2 位置信息特點

與傳統(tǒng)數(shù)據(jù)庫中的關(guān)系數(shù)據(jù)相比，移動用戶的位置信息具有一些新的特性。

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

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

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

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

使用位置服務(wù)的用戶在請求服務(wù)時一般都是在線等待結(jié)果，如果服務(wù)器不能在極短的時間內(nèi)反饋正確的結(jié)果，不僅會失去服務(wù)意義，而且會導(dǎo)致用戶對應(yīng)用服務(wù)失去信心。

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

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

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

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

三、PTID保護模型

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

3.1（s，C，K）L匿名

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

1、|T（q） | ≥K；

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

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

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

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

3.2數(shù)據(jù)預(yù)處理

3.2.1相關(guān)定義

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

非空序列在軌跡數(shù)據(jù)表中出現(xiàn)的次數(shù)稱為序列支持度。

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

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

2）違和序列

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

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

3）最小違和序列

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

3.2.2最小違和序列的抑制

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

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

式中：

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

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

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

3.3 匿名算法

3.3.1算法

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

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

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

2：生成最大頻率序列MFS并構(gòu)建最大頻率序列樹MFS-tree；

3：構(gòu)建分數(shù)表S-table；

4：while S-table≠Φ do

5： 從MFS m中選擇分數(shù)最高的序列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中，更新分數(shù)表；

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

16：return 抑制后的數(shù)據(jù)表T；

四、抑制試驗和結(jié)果分析

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

4.1數(shù)據(jù)處理

試驗數(shù)據(jù)的處理主要包括以下內(nèi)容：

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

2）對數(shù)據(jù)表中的冗余數(shù)據(jù)進行刪除處理。

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

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

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

4.2軌跡對比分析

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

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

五、結(jié)束語

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

參 考 文 獻

[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] 霍崢，孟小峰，軌跡隱私保護技術(shù)研究.計算機學(xué)報，2011，34（10）.

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