移动用户位置信息处理及保护模型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/.