作者：郑晓敏
近年来，位置服务中隐私保护技术的研究主要从以下三个方面着手：假名技术、加密技术、基于位置的匿名方法。其中基于位置的匿名方法是使用最普遍的方法。该方法用包括该位置所在的一个区域来代替用户的真实位置发出查询，大大降低了用户位置信息被泄露的概率。同时在此基础上加上匿名时间限制来控制用户查询信息的匿名有效时间，从而从时间和空间上对匿名集区域进行了约束，更好地保护用户信息。
在LBS隐私保护领域中出现了基于算法和策略的保护机制。基于算法的保护机制是在请求用户和服务提供商之间通过设计算法来实现隐私保护，这也是目前大多数学者研究的主要方向；而基于策略保护机制是通过策略和约束规则决定股务提供商何时何地可以获得自己的位置信息。2002年，Langheinrich M首先提出基于策略的保护方法，文献[7-10]对该方法进行了更深一步的研究，但是该方法的缺点是查询用户必须时刻更新自己的策略，一旦查询用户忘记更新隐私策略，就会出现隐私泄露的风险。2003年，假名机制的提出可以更好地保护用户隐私，其思想是将空间划分成混合区域( mix zone)和应用区域（application zone），在混合区域内用户不发出任何请求，但是可以更改自己的ID，而在应用区域内，通过更换后的假名进行查询请求而不使用真实ID，这样就断开了同一个用户在不同时间连续两次服务请求之间的联系，假名机制的缺点是用户处在混合区域不能随时随地地享受服务。同年，在位置隐私保护中，G，utese。和Grunwald首次提出了K匿名模型，并且在此基础上提出基于四分树的隐私保护方法，其主要思想是对空间进行四叉树迭代划分，直到某次迭代划分后，查询用户所在的象限匿名条件不满足K匿名条件，则返回上一次迭代的结果作为用户的匿名区域。它虽然可以解决大量移动用户高效寻找匿名集问题，但是该方法是以假定用户拥有统一K匿名需求为前提，并且得到的匿名区域往往过大。针对这些问题，在2005年，Gedik和Liu提出了一种CliqueCloak（小集团）匿名方法，该算法中的每个用户均可以根据自身的情况定义不同的K匿名要求，通过逐个结合互为匿名团的用户来满足自己的K匿名要求，该方法的优点是可以满足不同用户的不同的匿名要求，但最大的缺点是只适合于K值很小的情况（如5—10），当K值较大时效果很差，实际用途不大。在K匿名方法的基础上，阚莹莹提出一种新的模型即多样化K匿名模型，该模型的主要贡献是对用户敏感属性进行分类，避免其分布不均衡，有效地保护了隐私。牛红卫提出了增强的匿名模型，并且在该模型基础上针对现有匿名空间查找算法冗余空间过大问题，提出了基于网格和密度的匿名空间查找算法，在用户分布密度最大的范围内寻找满足匿名模型的最小匿名空间，但是缺点是容易遭到中心位置攻击。为解决这些问题，Bamba等人提出邻接网格扩展匿名算法，典型的算法有Bottom-up cloaking算法、Top-down cloaking算法和Hybrid cloaking算法。这些算法允许用户自行定义隐私需求参数，实现个性化隐私保护，同时，该参数可以弥补仅有K匿名参数而引起的隐私泄露。但是这种方法查询服务质量还有待提高。
迄今为止，大多数隐私位置匿名算法匿名时间较长，匿名域较大，匿名不成功的可能性较高，并且对包含更多隐私信息的查询隐私没有做到更好的保护。本文提出LBS(P，L，K)匿名模型，并在此基础上，确定一种基于网格和假用户来划分空间位置的匿名算法，该算法建立在目前比较成熟的网格技术应用基础上，对空间进行网格划分，通过考虑用户的分布情况来寻找查询用户的邻域，同时生成假用户来发送假请求以满足LBS(P，L，K)匿名模型，实现对查询隐私保护的目的。
1网格和假用户匿名算法设计
1.1相关概念
定义l（K匿名）在所有用户匿名查询中，位置服务商按照某种策略得到包含查询用户在内的匿名区域R中至少包含K个不同用户位置，称此匿名满足K匿名。
定义2（敏感度）假设一个用户在某个时刻请求查询Q(id，g)中，为查询内容g设定敏感级别，将其数值化后的值为这个查询内容的敏感度，记作Sid。敏感度越大表示被保护的程度越高。
定义3（P敏感约束）假设匿名区域中所有匿名查询Q(id，g)中，查询内容g的敏感度为Sid的数目所占查询数目总数比例不超过Po其中，|(R，Sid)|为匿名区域R中查询内容的敏感度为Sid的查询数目。P为用户定义的参数(0<P<1)，满足P敏感约束的充分必要条件是当且仅当|(R，Sid)|/|(R)|≤P。
定义4（L覆盖性约束）在匿名区域中，查询内容的敏感度Sid不同值个数不小于L。
定义5( LBS(P，L，K)匿名模型）满足匿名模型定义1、定义3、定义4称为LBS(P,L，K)匿名模型。
定义6（相邻网格）用Si,j来表示当前用户所处网格的空间位置，则坐标为Si±1j或者Sij±1的网格为当前用户所在网格的相邻网格。
定义7（邻域）当前网格和其相邻网格集合构成当前网格的邻域，S '={Sxy|i-l≤x≤i+1,j-l≤x≤j+l}。
定义8（临时匿名区域）若空间S满足匿名要求，对S进行网格划分之后，用户u的邻域空间所包含的用户个数小于匿名要求，则称空间S是用户u的临时匿名区域。
1.2算法分析描述
本文算法分成两个阶段，第一阶段为网格区域扩充算法，第二阶段是假用户生成算法。网格区域扩充算法中，将整个空间S分为MxM的网格，每个网格单元用相应的坐标Sij表示。根据当前查询用户所在网格坐标可以计算出该用户的邻域空间S’和S'所对应的用户数目分布矩阵C，用Is表示空间内所对应的用户数目，若IS'I>K，则令S'=S，对划分网格进行迭代，直到若|s'|≤K为止，此时的空间S即为临时匿名空间。为防止匿名区域过大会降低用户服务质量，而过小则可能会遭遇中心位置攻击，故对匿名区域空间设置最小粒度Amin和最大粒度Amax。接下来对临时匿名空间S的冗余边缘进行删除，首先根据临时匿名空间S的用户数目分布矩阵删除用户数目最小的行或列，直到得到的匿名区域面积在(Amin，Amax)之间。在假用户生成阶段，首先计算临时匿名区域的用户数目矩阵，分别在用户数目最少的单元网格内生成一个假用户，判断是否满足敏感约束P和覆盖性约束条件L，重复此过程直至满足LSB(P,L，K)匿名模型。算法符号及其含义如表1所示。
算法伪代码如下。
第一阶段：
输入：隐私度参数K，应用空间S，匿名空间粒度Amin，Amax。
输出：最小匿名区域Smin。
Clocking(K,S,Amin,Amax)
Begin:
(1) while(|S|>K&&Area(S)≥Amin&&Area(S)≤Amax）
{
(2)Sm=S;
(3)根据定义7计算出S的邻域空间S'；
(4)S=S'；
(5)}//while
(6)Smin=Sm;mint i=l；
(7) while(|S|>K&&Area(S)≥Amin&&Area(S)≤Amax）
{
(8)根据用户分布数目矩阵查找Smin中用户数目最少的第i个边缘；
(9)Smin=Sm,in-Si；
( 10) i++；}//while
( 11) Return Smin
End
第二阶段：
输入：隐私度参数K，敏感约束P，覆盖性约束L。
输出：最小匿名区域Smin。
Generate_fake_users(K.P.L,Smin)
Begin:
(1)计算P'=max(|(R，Sid)|/|R|)，L'；//pr与L'为最小匿名区域中的敏感约束和覆盖性约束。
(2) int i=l：
(3) while( |S|<K IIP'>PIIL'>L){
(4)计算Smin的用户分布数目矩阵，据此查找用户数目最少的第i个边缘网格，在此网格内生成一个假用户和其查询内容的敏感度。
(5)计算P'=max(I(R,Sid)l/IRI),L'；
(6)i++：
(7)}//while
算法实例分析如下：
假设在时刻f，初始空间为S，用户4在该时刻发出查询五元组为（P，L，K，Amin,Amax），其中P=0.4，K=4，L=2，Amin=6，Amax=9。首先，对初始空间S划分为5x5的网格，用户u所在网格为第二行第三列，故其网格坐标为U2.3，根据定义7得到其邻域空间为[(1—4)，(2—5)]，根据用户数目分布矩阵C计算|S'|>4，则令S'=S迭代划分网格，直到Is'I≤4，则此时的S2即是临时匿名区域迭代过程。如表2所示，最终结果为二次迭代空间S2。
接下来由远及近依次删除用户数目最小的行或列，如图l所示，依次删除冗余边A，B，C，D，剩下的匿名区域为满足条件的最小匿名区域。
该时刻用户提交的部分查询信息如表3所示。
通过计算可得I(R，0)l/IRl=0.75>0.5，I(R，1)l/IRl=0<0.5，I（R,2）l/IRl=0.25<0.5，L，-3>2。由于I(R，0)l/IRI不满足条件，寻找满足用户数目最少的边缘网格，生成一个假用户u，其查询内容设置为“拘留所”，其敏感度为2，这样就可以满足LBS(P,L，K)匿名模型。
2模拟实验
本文实验仿真的硬件环境是INTEL CORE 13-4150 3.6 GHz处理器，4G内存， 编程环境是ECLIPSE+HIBERNATE+MICROSOFT SQL SERVER 2008,算法均使用Java语言编写。实验在产生用户位置坐标和LBS请求时，采用THOMAS BRINKHOFF基于路网的移动对象生成器来模拟生成5000个用户，以算法执行100次仿真的平均值作为本次实验的结果，同时参数Amin取值为一个单元格，Amax为9个单元格。
为平衡用户隐私保护和服务质量之间的关系，本文从匿名时间、匿名成功率、匿名代价等指标方面对基于网格和假用户匿名算法( Grid-fake users)进行验证，以讨论本文有效性。其中，匿名时间是触发提出查询请求到匿名成功所需要的时间，匿名成功率是指匿名成功的查询请求个数与所有查询请求个数的比值，其值越大则表示服务质量
越好，匿名代价用匿名空间的大小（即匿名空间的面积）来表示，相同匿名度条件下，匿名空间越小，则匿名代价就越低。
图2给出了基于网格和假用户匿名算法、Bottom-up匿名算法和Grid_divide算法的时间消耗随K值变化关系图。从图2可以看出，三种算法的匿名时间随K值的增加而不断增加，这是因为随K值的增加，每个查询用户需要更多的时间处理、等待才能匿名成功。同时与Bottom-up匿名算法、Grid-divide算法相比，基于网格和假用户匿名算法因参数上有更高的要求使得其时间消耗相对较高。
采用匿名区域面积来表示匿名代价。由图3可知匿名区域面积随K值的增加呈现递增趋势，这是因为K值的增加必然要求更多的用户，更大的空间来满足K匿名。在基于Grid_divide位置匿名算法中，若当前网格面积S≥Amin,只有该网格内的用户数量满足(P，L，K)模型时，才返回匿名区域，否则计算与当前网格相邻的四个单元格中的用户数目，选择数目最多的网格单元与该网格合并，作为该用户的匿名区域，面积设为S，递归循环该过程，直S≥Amin，并且满足K匿名模型。而本文提出的基于网格和假用户匿名算法是将用户密度考虑进去，对空间进行迭代，然后求得匿名区域，此时匿名区域已经确定，通过生成假用户和假请求来满足(P,L，K)模型，所以该算法比Grid-divide算法生成的匿名区域面积要小，实验结果如图3所示。
综上所述，相对于其他算法，新算法能够以牺牲较少的时间消耗来明显降低匿名代价，同时引入假用户来满足敏感约束P和覆盖性约束L条件，能够更好地保护用户隐私信息。
3结束语
针对位置服务隐私保护的大多数研究只考虑了位置隐私保护方面，而没有更好地保护查询隐私，本文提出了LBS(P，L，K)匿名模型，将匿名集中的查询接照敏感度进行分类，并使得每个匿名集中不同敏感度的查询所占比例不超过P，不同敏感度的个数不小于L，通过参数P和L来实现保护用户查询内容的目的。寻找匿名集是匿名模型要解决的关键问题，在此基础上，文章提出基于网格和假用户匿名算法，在用户分布数目最多的范围内来寻找满足隐私要求的最小匿名空间，解决了位置服务中匿名算法存在的匿名区域大问题。该算法在匿名区域面积最小的基础上，通过增加假用户，设置假请求来满足匿名模型，大大增加了攻击的难度。通过实验表明，改进后的算法匿名区域更小，相对匿名度更高，更有利于保护用户的位置隐私和查询隐私。
4摘要：
目前，大多数位置匿名算法会出现匿名区域较大、匿名时间较长、匿名不成功的可能性较高等问题，并且对包含更多隐私信息的查询隐私没有做到更好的保护。为解决这些问题，文章提出一种基于敏感度的个性化LBS( P,L,K)匿名模型，该模型在K匿名基础上，通过对查询内容设置不同的敏感度来满足P敏感约束和L覆盖性约束，达到保护查询隐私的目的，从而实现匿名隐私保护的个性化需求。同时，文章在该模型基础上提出基于网格和假用户匿名算法，该算法将整个匿名空间划分成mxn的网格，通过迭代寻找查询用户所在网格的邻域空间进而找到该用户的临时匿名空间，然后根据用户分布矩阵对临时匿名空间进行边缘剥离，直至满足用户面积约束条件。从对比实验结果可知，在满足用户个性化要求条件下，该方法匿名区域面积更小，从而提高了相对匿名度和用户的查询服务质量。
