移動(dòng)用戶位置信息處理及保護(hù)模型PTID

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

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

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

一、引言

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

二、位置信息

2.1 定位技術(shù)分類

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

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

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

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

2.2 位置信息特點(diǎn)

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

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

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

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

2、位置信息具有較高的時(shí)效性。

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

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

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

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

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

三、PTID保護(hù)模型

基于上述位置信息數(shù)據(jù)特點(diǎn)，本文提出一種基于用戶差異性的軌跡保護(hù)模型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é)對(duì)數(shù)據(jù)進(jìn)行局部抑制，在減小軌跡數(shù)據(jù)隱私泄露風(fēng)險(xiǎn)的同時(shí)最大程度的保證數(shù)據(jù)可用性。

3.1（s，C，K）L匿名

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

1、|T（q） | ≥K；

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

PTID保護(hù)模型大致包括兩個(gè)步驟：

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

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

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ù)滿足抵御身份連接攻擊和屬性連接攻擊的要求，即可能泄露隱私安全的因素均被剔除了。這種方法在理論上是可行的，實(shí)際上，按照違和序列的定義，違和序列的非空真子 集也是違和序列，違和序列的規(guī)模可能極大，由此產(chǎn)生計(jì)算瓶頸使得方法的可操作性不強(qiáng)，因此提出最小違和序列。

3）最小違和序列

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

3.2.2最小違和序列的抑制

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

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

式中：

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

U（p）——通過抑制p而丟失的實(shí)例數(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)建分?jǐn)?shù)表S-table；

4：while S-table≠Φ do

5： 從MFS m中選擇分?jǐn)?shù)最高的序列p；

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

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

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

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

10： else

11： V<—V（p）；

12： 對(duì)T中的p進(jìn)行抑制；

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

14： 如果 p和p 同在 V 中或同在一個(gè)MFS中，更新分?jǐn)?shù)表；

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

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

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

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

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

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

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

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

3）對(duì)原始軌跡敏感性和用戶查詢請(qǐng)求敏感性進(jìn)行量化。

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

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

4.2軌跡對(duì)比分析

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

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

五、結(jié)束語(yǔ)

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

參 考 文 獻(xiàn)

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

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