一种基于匿名区域变换的位置隐私保护方法

肖燕芳，徐红云

(华南理工大学计算机科学与工程学院，广州 510006)

1 概述

位置探查设备的快速发展开拓了一个新的研究领域——基于位置的服务。目前，基于位置的服务中的隐私保护是研究的热点问题，移动互联网提供基于位置的服务，如查询基于当前位置的感兴趣的点，此类服务都是基于k近邻(k Nearest Neighbors, kNN)查询[1-2]，即查询距离用户位置最近的 k个可能目标。用户在获取此类基于位置的服务时，总是希望自己的位置不被暴露，即位置隐私得到保护。实际上，享受服务与隐私保护是一对矛盾：高效的服务需要提供精确的位置；好的隐私保护策略需要使用户的位置信息尽量模糊化。近年来，许多研究者致力于在高效的位置服务和位置隐私保护之间寻求一个平衡点，即在最少暴露用户位置的前提下，获得最好的位置服务，让暴露的位置处于可控的状态[3]。

针对位置隐私保护问题，国内外提出了很多解决方案，如匿名[4]、假名[5]、假地址[6]、路径混淆[7]、k-匿名[8-9]等，这些方案大体可以划分为空间区域混淆和假位置 2种技术。其中，k-匿名[8-9]和路径混淆[7]都是空间区域混淆技术，采用该技术实现位置匿名主要存在以下问题：

(1)利用率低

在k-匿名查询中，用户选取服务器返回的k个查询结果中的一个，利用率为 1/k，用户需要的隐私度越高，利用率越低；在 kNN查询中，服务器需要返回混淆区域中每个节点的k个最近邻查询结果，服务器处理开销和通信开销将增加 k倍，利用率进一步降低。

(2)查询处理开销和通信开销大

用户发送给服务器的k个节点进行查询请求，服务器将k个节点的查询结果返回给用户，用户从众多的结果集中查找到自己所需要的结果，此过程造成过多不必要的查询处理开销和通信开销。

利用假位置技术，用户不发送自己的准确位置，而是基于一个假位置来获取基于位置的服务，从而保护用户的位置隐私。这类位置隐私保护方法的主要缺点是通信开销大。如典型的使用假位置技术的SpaceTwist[6]，采用TCP包的数目来衡量通信开销，查询服务过程为每次返回一定大小(设定为 β bit)的TCP包，其中包含 m个目标节点的信息，当返回的TCP包里包含满足用户查询请求的目标节点时，算法终止。假设满足算法终止的第 n个 TCP包里的第1个节点是满足算法终止的目标节点，则包中其余m－1个节点是无用信息，增加了不必要的开销，随着β的增大，通信开销将增加。

针对这些问题，本文提出一种基于匿名区域变换的位置隐私保护方法，通过采用匿名区域变换方法实现位置匿名，在实现位置隐私保护的同时，降低通信开销和查询处理开销，提高查询效率。

2 位置隐私模型

本文基于中心服务器结构的位置隐私模型展开研究，该模型的结构如图1所示。

图1 位置隐私模型

模型主要包括3个部分：

(1)终端用户，即使用便携式设备进行 kNN范围查询的人，便携式设备包括 PDA(Personal Digital Assistant)、笔记本、全球定位系统(Global Positioning System, GPS)、手机等，其特点是存储能力和处理能力有限。

(2)位置匿名服务器，主要包括：1)位置匿名模块，用于将位置信息进行匿名；2)数据存储模块，存储的数据包括用户查询请求信息和服务器返回结果集；3)共享存储模块，用于实现位置匿名信息与服务器返回结果集的完全共享。

(3)位置访问服务器，包括提供kNN查询以及其他位置服务的 Internet服务提供商(Internet Service Provider, ISP)。

3 隐私攻击模型

本文假定攻击者具有如下特征：(1)攻击者具有足够大的存储空间和强大的计算能力，能够截获位置匿名服务器发送到位置访问服务器的相关信息，以及服务器返回给位置匿名服务器的查询结果集。(2)攻击者不能篡改数据包的内容，也不能毁坏位置匿名服务器，仅能监听位置匿名服务器与位置访问服务器间的通信数据。

4 匿名区域变换法

基于上述位置隐私模型和隐私攻击模型，本文提出了一种基于匿名区域变换的位置隐私保护方法ART(Anonymous Region Transformation)。

4.1 预备知识

在移动位置服务中，用户所在位置周围的移动节点分布可以分为2种情况：(1)均匀分布，如图2所示，用户 A周围 2个矩形区域内节点数大致相同；(2)非均匀分布，如图3所示，用户A周围2个矩形区域内节点数相差较大。

图2 节点均匀分布情况

图3 节点非均匀分布情况

针对以上2种节点分布情况，位置匿名服务器采用匿名区域变换法生成匿名区域时，匿名区域中移动节点数目差别较大，本文主要研究均匀分布的情况。算法中所用到的参数定义如下：

定义1 用户发出的查询请求File表示为：

File=(L,Key,Range)

其中，L=(x, y)是用户的位置信息，x表示位置的经度；y表示位置的纬度；Key是查询关键字；Range是查询范围参数。

定义 2 位置匿名服务器向位置访问服务器发出的匿名区域查询请求File’表示为：

File’=(L’, Key, Range’)

其中，L’是经过匿名处理后的匿名区域；Key是用户查询的关键字；Range’是匿名区域内匿名节点的查找范围。

4.2 位置匿名与邻近节点处理

匿名区域变换即采用变换的方法，确定位置隐私用户的匿名区域。图4为匿名区域变换示意图。

图4 匿名区域变换示意图

对于图4，确定用户q的匿名区域的方法如下：在平面直角坐标系下，用户q的位置标示为A，将A所在位置设置为原点，在距离 A点任意方向(α∈[0°,360°])的 k米处任取一点 O，锚点 q’的位置标示为 O点所在位置，过点O作线段NF，使NF=2NO。以NF为边，作正方形BCFN，该正方形即为用户q的匿名区域。为了实现对查询用户q的位置匿名，经过以上的匿名区域变换后，对用户的范围查询即可转换成对匿名区域BCFN内移动节点的范围查询。例如，用户提出“查找距离我R千米的加油站的位置”，其中，L是用户的位置信息；Key是查询关键字“加油站”；Range是查询范围参数“R千米”，位置匿名服务器选取距离用户 k千米的 O点作为锚点，生成匿名区域BCFN，通过BCFN内移动节点“查询距离我n千米的加油站的位置”实现，位置匿名服务器查询请求File’中，L’是经过匿名处理后的匿名区域BCFN，Key为用户范围查找的关键字“加油站”，Range’是匿名区域中匿名节点的查找范围“n千米”。位置访问服务器处理查询请求 File’(L’,Key, Range’)，并将查询结果发送给位置匿名服务器，位置匿名服务器对结果集进行邻近节点处理，精确提炼出用户q的范围查询结果，返回给用户q。

ART方法实现位置隐私查询的步骤如下：

(1)定位用户q的地理位置坐标，即点A的坐标。

(2)在距离 A点 dist(q, q’)处找一锚点 q’，即点 O的位置坐标，其中，dist(q, q’)表示用户 q与锚点 q’的距离。

(3)以A为圆心、以AO为半径作圆。

(4)根据给定的角度 α，作出与圆相交于点 O的线段。

(5)根据匿名需求，生成边长为s的特定大小的匿名区域BCFN，区域BCFN内节点表示为 q1, q2,… ,qn。

(6)位置匿名服务器向位置访问服务器分别发送节点 q1, q2,… ,qn的范围查询服务请求。

(7)位置访问服务器向位置匿名服务器返回节点q1, q2,… ,qn的范围查询结果。

(8)位置匿名服务器检索位置访问服务器返回的查询结果，从中选取恰当的查询结果返回给用户。

在4.2节方法中，匿名区域变换算法涉及到参数Range、dist(q, q’)、Range’，参数 Range、dist(q, q’)、Range’的选取分3种情况，当匿名区域内的移动节点正好位于q’时，3种情况分别如图5～图7所示，其中，Range、dist(q, q’)和 Range’分别表示为 AQ、AO、OP；匿名区域的边长为s。

图5 Range’

图6 Range’=dist(q, q’)的情况

图7 Range’=dist(q, q’)+Range 的情况

第 1种情况为 Range’

第 2种情况为 Range’=dist(q, q’)，即匿名区域内移动节点的查找范围半径OP等于用户q与匿名区域内移动节点 q’的距离 AO，此时，匿名区域移动内节点查询范围恰好包含查询用户q的位置，返回的结果集包含大部分用户查询所需结果。

第 3 种情况为 Range’=dist(q, q’)+Range，即匿名区域内移动节点查找范围半径OP覆盖查询用户q的查找范围半径 AQ，此情况下能够很好地实现位置匿名，提供良好的服务质量。

综上所述，Range’的有效选取范围为：Range’∈{dist(q, q’),dist(q, q’)+Range}

其中，q表示用户所在位置；q’表示匿名区域内移动节点的位置。

用户进行服务请求的查询范围 Range由用户定义，匿名区域内移动节点查询范围Range’由用户与移动节点间的距离dist（ q,q′）和用户实际查找范围Range决定。位置匿名服务器执行匿名算法，选取锚点 q’，直观地，当用户 q距离锚点 q’近时，Range’的选取范围小，此时查询处理开销较低，隐私保护力度也降低。q’的选取由用户的匿名需求决定。

5 算法性能分析

本节从查准率、查询开销、匿名性3个方面来衡量本文算法的性能。其中，查准率用来衡量服务器的服务质量，采用用户查询结果所占实际用户查询结果的比例来表示；查询开销即用户采用匿名区域变换算法所用时间开销和通信开销；匿名性用攻击者所能推断的用户隐私区域大小来衡量。

5.1 查准率

定义 3 对任意Node∈CR(匿名区域)进行范围查询，假设Node1, Node2,… ,N oden进行范围查询返回的区域分别为C1, C2,… ,Cn，则位置访问服务器返回的结果集为：

设C内目标集合为Objectc，则：

设点A所在位置的用户q范围查询区域为CA，则CA内目标集合为：

采用本文的位置匿名方法处理后，服务器能够提供的服务质量 Q可以用用户范围查询结果集与经过位置匿名后的匿名节点查询返回的结果集之比表示：

由式(1)可以看出，当所选匿名区域包含用户的查询请求区域时，用户的查准率能够达到 100%，但通信开销增加；当所选匿名区域与用户查询区域相交时，通过位置匿名中间件的处理，通信开销少，能够实现良好的查准率。

5.2 查询开销

用户请求服务开销主要包括以下3个方面：

(1)位置匿名服务器根据用户的隐私需求进行匿名处理时需要时间开销，匿名处理时间与用户的隐私要求和周围节点密集度有关，当密集度高时，处理时间长，反之，处理时间短。

(2)位置访问服务器响应匿名处理后的查询请求需要时间开销，将查询结果返回给位置匿名服务器需要通信带宽开销。

(3)位置匿名服务器对查询结果集进行优化处理，选择与用户邻近匿名区域中的节点相对应的查询结果，剔除掉远离用户的其他节点对应的查询结果需要时间开销。

假设匿名处理时间为ψ(q)，服务器处理时间为ω，通信时间开销为 T，查询结果优化时间为 ε，则总的查询服务开销Cost为：

通过查询结果集的邻近节点处理，返回给用户的节点集只包含邻近用户的查询结果，减少了位置匿名服务器与位置访问服务器间的通信量、时间开销T以及用户检索自己所需查询结果的时间 ε，因此，减少了总的查询开销Cost，提高了查询效率。

5.3 匿名性

因为攻击者能截获匿名处理后的查询请求File’(L’, Key, Range’)以及位置访问服务器返回给位置匿名服务器的查询结果集，所以攻击者能够获知位置匿名查询范围Range’和匿名区域大小s2。攻击者将匿名区域内的节点进行范围查询所覆盖区域作为用户的可能位置，从而推断出用户所在的区域为：

攻击者能够推断出用户可能所在位置为距离匿名区域内节点 dist（ q, q′） 范围内的节点位置，因此，攻击者推断出用户所在的区域为：

由4.2节知，算法中Range’的有效取值范围为：

因此，攻击者推断出用户所在的区域范围为：

定义隐私度T为区域Ψ内所有节点与真实查询用户q的平均距离。

位置匿名服务器根据用户的隐私需求定义隐私度T，而攻击者无从获知。用户进行服务请求的查询范围为Range2，攻击者推断出的用户所在区域范围由式(5)给出。

当隐私度 T值增大时，dist（ q, q′）增大，而攻击者推断用户所在区域范围增大，攻击者推断用户真实位置的难度增加，从而能够为用户提供更好的位置隐私保护。

6 实验评估

算法采用Java编程语言实现，实验环境为2.2 GHz的 Intel双核 CPU，1 GB内存。操作系统平台是Microsoft Windows XP Professional。

6.1 参数设置和实验结果分析

实验数据采用 Thomas Brinkhoff的 Networkbased Generator of Moving Object[10]随机生成的Oldenburg市的空间数据集，分别研究节点密集度和锚点距离 dist（ q, q′）对匿名区域变换算法ART性能的影响，针对不同参数，比较ART与Cloaking Region 算法和 SpaceTwist算法在通信开销和匿名性方面的优劣。其中，节点数 N 分别取 1 000、2 000、3 000、4 000、5 000、6 000、7 000、8 000、9 000、10 000、80 000、120 000、160 000，用户离锚点距离 dist(q, q’)分别取50 m、100 m、150 m、200 m、250 m、300 m。

图8给出匿名区域内用户数目N及用户离锚点的距离 dist（ q, q′） 对查准率的影响。从中可以看出，随着区域内用户数目的增加，查准率提高，误差减小。随着 dist（ q, q′） 值的增大，误差率增加，查准率降低。这是因为区域内用户数目增加，节点密集度增加，采用匿名区域变换算法的匿名区域内节点数目增加，所以发送到位置访问服务器端进行查询服务请求的节点数目 q1, q2,… ,qn中的n值增加，供位置匿名服务器进行邻近节点处理的节点返回值接近用户的实际查询结果。当 dist（ q, q′） 值小时，距离用户越近的节点的查询结果越接近用户所需要的查询结果，所以，随着 dist（ q, q′）的减小，距离用户越近的节点的结果越精确，误差率降低，查准率增加。系。当 dist（ q, q′） 一定时，随着用户数目的增加，请求服务的通信开销增加，但当节点密集度继续增大时，通信开销增加很少。由4.2节可知，这是因为服务器需要处理的匿名区域内节点数目增加到一定程度时，将获得匿名区域内任意位置上的范围查询结果，即使再增加查询，也不能产生新的查询结果，从而使通信开销增加得很少。

图8 匿名区域内节点数目及dist(q, q’)对查准率的影响

图9显示了用户数目与通信时间开销之间的关

图9 节点数目与通信时间开销之间的关系

6.2 与CR算法的比较

表1给出采用ART算法和CR(Cloaking Region)算法时 dist（ q, q′） 对查准率的影响。实验结果表明，ART的查准率与 dist（ q, q′） 密切相关，而 dist（ q, q′） 对CR算法的影响较小，不论 dist（ q, q′） 取值多少，CR算法的查准率趋近1。ART算法与CR算法相比，查准率略低。在表2中，CR算法和ART算法均采用匿名区域方法，受节点密集度的影响，当节点分布密集时，匿名区域内节点数目增多，所需查询请求节点数增加，两者通信开销增加。受节点分布影响，当q周围节点密集度大于q’周围节点密集度时，CR算法的时间开销大于ART 算法，反之，CR算法时间开销小于ART算法。实验结果显示，ART算法通信开销略小于CR算法，这是因为ART算法采用了邻近节点处理的方法，减少了总的通信时间开销。

表1 不同 dist(q, q’)下2种算法的查准率

表2 不同节点数目下2种算法的通信时间开销 s

6.3 与SpaceTwist算法的比较

图10显示了 dist（ q, q′）=200 m时，ART算法和SpaceTwist算法的通信开销比较结果。结果显示，在特定空间节点数目下，ART算法的通信时间开销略优于SpaceTwist算法。

图10 dist(q, q’)一定时2种算法通信时间开销对比

图11是节点数为160 000时 dist（ q, q′）对 2种算法通信时间开销的影响，实验结果表明，d ist（ q, q′） 值的改变几乎不会影响通信时间开销。

图11 不同dist(q, q’)下2种算法通信时间开销比较

图12显示了当 dist（ q, q′）改变时，SpaceTwist算法的查准率优于ART算法。这是因为SpaceTwist采用客户-服务器体系结构，不断向位置访问服务器请求最近POI (Point of Interest)，直到出现满足用户的请求结果，算法结束，此算法处理过程虽能够实现良好的查准率，但不断地向服务器发送请求导致通信开销太大。由4.1节可知，当式(1)中匿名区域内节点查询的目标集合 ObjectC包含用户q范围查询的结果区域CA中的目标时，ART算法也能达到较高查准率。

图12 ART与SpaceTwist的查准率比较

7 结束语

以往的位置隐私保护方法普遍采用包含用户位置的匿名区域代替用户真实位置进行查询处理，造成位置隐私度不高和通信开销大。本文提出一种用户真实位置不包含在匿名区域中的方法实现位置隐私保护，在离用户一定距离处选一锚点生成匿名区域，由匿名区域内移动用户发起到服务器的服务请求，经过位置匿名服务器对返回结果集进行邻近节点处理，提高了位置隐私度，降低了通信开销，优化了查询结果。由于用户的真实位置不包含在匿名区域内，因此提高了用户的抗攻击能力。理论分析和实验结果表明，匿名区域变换方法能够保证在较低的通信开销下提供较好的位置隐私保护。但本文方法只适用于用户周围节点分布均匀的情况，之后将对用户周围节点分布不均匀的情况展开研究。

[1]Roussopoulos N, Kelley S, Vincent F.Nearest Neighbor Queries[C]//Proceedings of ACM SIGMOD International Conference on Management of Data.[S.l.]: ACM Press,1995: 71-79.

[2]Hjaltason G R, Samet H.Distance Browsing in Spatial Databases[J].ACM Transactions on Database Systems,1999, 24(2): 265-318.

[3]潘 晓, 肖 珍, 孟小峰.位置隐私研究综述[J].计算机科学与探索, 2007, 1(3): 268-281.

[4]Shankar P, Ganapathy V, Iftode L.Privately Querying Location Based Services with SybilQuery[C]//Proceedings of the 11th ACM International Conference on Ubiquitous Computing.Orlando, USA: ACM Press, 2009.

[5]Cornelius C, Kapadia A, Kotz D, et al.AnonySense:Privacy Aware People Centric Sensing[EB/OL].[2011-05-23].http://www.cs.indiana.edu/～kapadia/papers/anonysense_mobisys08.pdf.

[6]Yiu Man-Lung, Jensen C S, Huang Xuegang, et al.SpaceTwist: Managing the Trade-offs Among Location Privacy, Query Performance, and Query Accuracy in Mobile Services[C]//Proceedings of the 24th International Conference on Data Engineering.[S.l.]: IEEE Press, 2008:366-375.

[7]Meyerowitz J, Choudhury R R.Hiding Stars with Fireworks: Location Privacy Through Camouflage[C]//Proceedings of ACM Special Interest Group on Mobility of Systems, Users, Data and Computing.Beijing, China:[s.n.], 2009: 345-356.

[8]Gruteser M, Grunwald D.Anonymous Usage of Locationbased Services Through Spatial and Temporal Cloaking[C]//Proceedings of the International Conference on Mobile Systems, Applications, and Services.New York,USA: ACM Press, 2003: 163-168.

[9]Samarati P, Sweeney L.Protecting Privacy When Disclosing Information: k-anonymity and Its Enforcement Through Generalization and Suppression[R]. SRI Computer Science Laboratory, Tech.Rep.: SRI-CLS-98-04, 1998.

[10]Brink H T.A Framework for Generating Network Based Moving Objects[J].GeoInformatica, 2002, 6(2): 153-180.