基于多边形隐匿区域的LBS系统

曹 伍，徐 葎，刘玉葆，印 鉴

（中山大学 计算机系，广州 510006）

0 引 言

随着社会经济的发展，人类的活动范围不断扩大，地理区域的扩展给人们出行带来极大的不便．在这样的情况下，基于位置服务（LBS）应运而生，为人们提供各种各样的位置服务．比如，基于LBS，驾驶员可以查找离自己最近的加油站．随着位置探测设备（例如便携式电话、GPS、RFID等）的广泛使用，使得基于位置的服务日益受到人们的关注．文献［1］介绍了LBS系统的架构和各个组成部分的关键技术以及LBS的研究进展．然而LBS在为用户带来便利的同时，也威胁着用户的隐私安全．因为LBS需要以用户的位置信息作为输入，在用户向服务器发送位置信息时，也意味着用户的位置隐私有可能被LBS服务供应商恶意利用，如通过位置信息推断用户的工作地点、行为习惯等．因此，出于用户对位置隐私保护的需求，相关的研究也陆续出现：文献［2］提出了一种面向公路网络的位置隐私保护方法；文献［3］提出了一种用户协作无匿名区域的位置隐私保护方法；基于很多匿名算法不能适用于连续查询的情况，文献［4］提出了一种适用于连续查询的贪心匿名算法．

随着数据库技术、网络技术的发展，人们在LBS的隐私保护上不断提出新的方法，如Casper［5］、TinyCasper［6］、PRIVE［7］等．此外，文献［8］提出了一种有效的隐私保护关联规则挖掘方法，提高了对隐私数据的保护程度和挖掘结果的准确性；文献［9］是关于邻域隐私保护的论文，研究了在云端的最短距离计算，用以防止外包图来自邻域的攻击；文献［10］介绍了位置大数据的概念以及位置大数据的隐私威胁．通常来说，这些隐私保护技术首先把地图划分为网格状，每个用户可以自由设置自己的隐私要求，包括隐匿区域的大小和K－Anonymity参数．其中，隐匿区域大小是指用户需要把自己的点坐标转换的区域面积；而K－Anonymity参数用来描述用户所处的隐匿区域至少覆盖的在线用户数．接着，根据用户的位置信息以及隐私要求，位置匿名器将用户映射到对应的网格中，并将该网格作为用户的隐匿区域传送给LBS服务器．最后服务器根据网格的位置信息来处理用户的服务请求．因此，服务器只知道用户所属的网格而不是具体位置，且该网格内有至少K个用户，恶意攻击无法辨别个体的身份，从而保护了用户的位置隐私．

已有方法和系统从不同角度解决了LBS隐私保护中具有挑战的问题，然而也存在着一些不足：①网格形状的隐匿区域在某些地形下存在过多的无效区域，如某用户位于沙漠中的公路上，最佳的隐藏区域应该是条带状的公路区域，而使用网格状的隐匿区域会导致无效区域的出现并增加服务器的计算开销或者无效的返回结果．②仅靠隐私参数的设置而自动生成的隐匿区域无法完整地表达用户的查询意图．一般来说，用户总是希望自己位于隐匿的中心附近，但由于网格是预先划分好的，无法随意平移，因此当用户位于某个网格边缘时，该方法无法达到预期的效果．③位置数据的精度损失太大．位置数据精度对LBS供应商非常有用，因为位置数据经过数据挖掘后可以获得许多具有价值的信息，如哪个区域查询的酒店次数最多、哪里最需要加油站等．在LBS的实际应用中，用户的需求趋向于隐匿区域和实际的地形、城市布局相吻合，如用户希望隐藏于某条街道或者某个大厦内．这种相吻合的隐匿区域最大程度地保留了数据精度，同时也满足了用户的隐私要求，是隐私安全程度和数据精度之间的最佳平衡点．然而网格状的划分并不考虑地形、城市布局等因素，因此所生成的矩形隐匿区域也就导致了位置数据精度的降低．

针对已有系统的不足，本文根据文献［11］和文献［12］中的理论，设计和实现了一种基于多边形隐匿区域的LBS系统．本文余下部分组织如下：第1节是系统目标；第2节是系统设计；第3节是系统实现；第4节是系统性能测试；第5节是全文的总结．

1 系统目标

本系统的设计目标是在保护用户位置隐私的同时，尽量保留位置数据的精度，并提供良好的服务质量，即兼顾位置隐私安全、数据精度和服务质量3个方面．

1．1 隐私安全

保护用户的位置隐私，是设计LBS系统的首要原则．本系统将使用“Location Cloaking”和“K－Anonymity”作为主要的隐私保护技术，从位置信息和身份信息两方面进行保护．

（1）Location Cloaking

Location Cloaking的原理是将准确的点坐标信息进行Cloaking处理，泛化为包含该点的一个区域，即对应的隐匿区域．在使用LBS时，仅向服务商提供用户对应的区域．该区域的大小可以由用户根据自己的隐私需求来设定，以调整其位置的隐匿程度．

（2）K－Anonymity

K－Anonymity是指在一个数据集中，任何一个条记录都至少和其他K－1（K≥2）条记录不可区别，K越大，则安全程度越高．在这样的数据集中，用户能处于真正的匿名状态，避免隐私泄露的侵扰．本系统不仅采用用户点位置的隐匿区域泛化，还要求泛化区域中的用户数量超过阈值K，从而保证用户的隐私安全．

由于进行K－Anonymity处理需要收集大量的用户位置信息，因此，需要引入可信的第三方中间件．一般来说，用户先将位置信息发送给中间件，让中间件来生成隐匿区域；然后，再由中间件向服务器转发用户的服务请求．但是，如果中间件不可信或者受到黑客攻击而泄露数据，则用户的隐私安全可能会受到威胁．因此，本系统使用双重位置隐私保护，将Location Cloaking和K－Anonymity两个保护技术分开，分别在客户端和中间件中执行，从而进一步保证了用户的位置隐私安全．

1．2 数据精度

数据精度是平衡用户隐私要求与服务质量的重要因素．适当的位置数据精度在LBS中可谓至关重要．本系统采用Location Cloaking方法对用户位置进行泛化，因此，隐匿区域的大小则是衡量位置数据精度的依据．隐匿区域越大，精度越低；反之区域越小，则精度越高．在实际应用中，最理想的精度平衡点是隐匿区域恰好满足用户的隐私要求，如用户希望隐藏于某个公园中，则隐匿区域刚好是包围该公园的多边形；用户希望隐藏于某条街道中，则隐匿区域刚好是沿着该街道的条带状．这样，数据精度不仅满足了用户隐私要求，且最大程度地保留了位置数据精度．因此，本系统将采用自定义的方式，让用户自己指定多边形隐匿区域，如在移动终端设备屏幕上勾画隐匿区域的轮廓．

1．3 服务质量

LBS的服务质量包括服务响应时间和服务结果的有效性．服务响应时间是指从用户发出服务请求，到接收服务返回结果之间的时间．如果服务响应时间太长，会严重影响用户的体验．服务结果的有效性则是指返回的结果是否正确、有效结果的比例等．如果LBS返回很多不相关的结果，不仅会增加服务器的运算和网络的负担，而且用户也难以从中获取有用的信息，导致服务质量的降低．

2 系统设计

本系统的架构如图1所示，包括客户端、中间件和服务器3个层次．客户端包括台式计算机、笔记本电脑、手机、GPS等移动设备，它提出基于位置隐私保护的查询请求．中间件位于客户端和服务器端之间，并与存储用户位置信息的移动数据库进行交互．服务器处理来自客户端的基于位置隐私保护的服务请求．一般地，在隐私保护的LBS系统中，传统的基于点的位置查询算法已经不能适用，需要设计新的算法来支持基于隐匿区域的位置查询．如在传统的LBS中，原来的用户位置是一个精确的查询点，利用最邻近查询算法可以找出一个准确的答案，比如离用户最近的加油站等．但是，在隐私保护的LBS中，当用户位置是一个区域的时候，服务器不知道用户具体在哪个点中，有可能会产生很多个结果，这就需要设计一种高效的基于隐匿区域的最邻近查询算法．不过，已有系统采用的查询算法大都是基于圆形或矩形之类的简单隐匿区域，无法支持本系统的多边形隐匿区域．针对这点，我们提出了一种基于多边形隐匿区域的查询算法P－RNN［11］（Polygon－Range Nearest Neighbor）．本系统将采用该算法来支持基于多边形隐匿区域的隐私保护查询．

图1 LBS系统架构Fig．1 Framework of LBS system

为了同时支持Location Cloaking和K－Anonymity两种位置隐私保护技术，进一步保证用户的隐私安全，本系统将使用双重位置保护方法，分别在客户端和中间件进行一次位置保护．如图2所示，在客户端，通过Location Cloaking方法生成隐匿区域CR（Cloaking Region）；而在中间件层，则根据CR和K－Anonymity的参数K生成KCR（K－Anonymity Cloaking Region）．

图2 LBS系统的序列UMLFig．2 Sequential UML of LBS system

（1）客户端

客户端是用户进行LBS操作的人机交互层，它结合MapInfo格式的电子地图，安装在手机、笔记本电脑、GPS等移动终端设备上．客户端软件支持电子地图的缩放、移动和定位操作，并且提供用户自定义隐匿区域功能．用户可以通过触摸屏、鼠标等方式在移动终端设备的屏幕上绘制所需要的隐匿区域CR，并选择相应的查询服务类型，如最邻近查询等；然后与K－Anonymity参数一起发送给LBS中间件．当查询完成，返回结果集时，客户端会根据用户的准确位置对结果进行筛选，只有符合查询要求的结果才会显示到电子地图中．LBS客户端处理流程如图3所示．

图3 LBS客户端流程图Fig．3 Diagram of LBS dient

（2）中间件

中间件作为一个可信的第三方平台，位于客户端和服务器之间，主要是使用K－Anonymity方法对用户的CR进行进一步处理．为此，中间件需要收集用户大量的CR信息，且由于用户是处于不断移动的状态，其CR会经常改变，如进行第二次查询时用户重新绘制了CR等．本系统在中间件内部建立一个移动数据库，用于保存移动用户的CR位置信息，并利用R－Tree等空间索引结构对数据库进行索引，加速用户位置的更新，提供快速查找某区域内用户信息的功能．在移动数据库的帮助下，中间件就可以根据用户的CR以及K－Anonymity参数生成KCR，然后把KCR作为用户新的位置信息，连同服务请求一起，转发给LBS服务器．

（3）服务器

LBS服务器负责处理客户端提出的用户LBS请求．其内部包含一个位置信息数据库，用于存储查询目标（如加油站、酒店等）的地理位置相关信息．当接收到用户的查询请求时，服务器调用相应的查询算法进行处理，并根据用户的KCR计算出该次查询的结果区域RR（Result Region）．RR保证无论用户位于KCR的任何一点上，其查询的正确结果都位于RR内．因此服务器从地理信息数据库中找出所有位于RR内的对象，作为结果集返回给用户．LBS服务器端的处理流程如图4所示．

图4 LBS服务器端流程图Fig．4 Diagram of LBS server

为了加快最邻近查询的速度，保证LBS服务的有效性，系统为服务器端的查询处理器设计了一种基于多边形隐匿区域的最邻近查询算法：P－RNN．P－RNN算法的主要思路是对于一个多边形区域R的最邻近查询，计算一个结果区域RR［11－12］，使得R中每个点的最邻近目标都位于RR中，且RR尽可能小，查询的结果就是RR中所有目标的集合．其中最大的困难是如何计算RR，为此算法使用点、线、面逐层扩展的方式来进行计算．

3 系统实现

系统的客户端、中间件和服务器3个部分作为3个独立子系统，分别使用．Net平台中的WPF（Windows Presentation Foundation）实现，其中电子地图的部分使用了MapXtreme 2008提供的编程控件．实验所用的地图是广东省的MapInfo格式电子地图，包含了32个图层．

3．1 客户端

图5 客户端操作过程Fig．5 Operating procedure in client

客户端是LBS系统进行人机交互的界面．其通过简单的操作，为用户提供快捷的LBS．图5演示了操作流程：①首先要使用LBS，必须先输入经过注册的用户名，图5例子中所使用的用户名是“Lisya”．②点击“Login”按钮，客户端则与服务器进行连接，并验证用户的有效性．③用户需要设置查询的类型，包括最邻近查询和全局查询两种：第一，如果用户选择的是“Nearest”最邻近查询，则还需要输入参数M，表示要查询最邻近的M个目标；第二，如果用户选择的是“All”，则表示查询所有目标．此外，为了达到K－Anonymity的隐私保护效果，用户还需要输入K－Anonymity的参数K以传递给中间件位置隐匿器，从而将自己隐藏在一个至少有K个用户的区域中．④通过电子地图的移动和缩放操作，用户在地图上进行浏览，以显示绘制自定义隐匿区域时的合适视图．⑤在左侧的电子地图处，通过鼠标或者触控方式，结合电子地图中的地形位置信息，绘制所需要的多边形隐匿区域．图5（a）电子地图中的绿色图钉是用户现在所处的准确位置，红色的不规则多边形是用户所绘制的隐匿区域．⑥在搜索栏输入查询关键词，如要搜索最邻近的酒店，则输入“酒店”．最后按下按钮“Search Map”，则用户的LBS请求将经过中间件发送给服务器．⑦如图5（b）所示，当客户端接收到LBS的服务结果后，会在结果栏中显示，如例子中搜索“医院”关键词后，服务返回5个和“医院”相关的结果，并在结果栏中显示出来．用户通过电子地图可以查询查询目标的位置分布（图5（b）中的红色图钉）．用户若需要进一步了解相关结果的信息，还可以通过图5（b）中的“第7部分”对目标进行定位．

3．2 中间件

中间件的主要功能是在隐匿区域的基础上，为用户生成一个具有K－Anonymity性质的隐匿区域．以图6为例，在用户Lisya发送LBS请求前，用户的在线情况如图6（a）所示．当请求发送给中间件后，移动数据库记录下Lisya的位置，并对Lisya所在区域放大后得到图6（b）．可见Lisya处于一个较繁华的地方，附近有很多其他用户，如User039、User040、User053等．由于Lisya的K－Anonymity参数为5，中间件通过使用贪心策略，合并扩展耗费最小的另外4个用户区域作为Lisya的KCR．图6（c）中的蓝色区域就是Lisya与User039、User040、User041、User053进行合并得到的KCR．在生成KCR后，中间件就为用户转发LBS请求给服务器．

3．3 服务器

服务器在接收到中间件转发的LBS请求后，调用基于多边形隐匿位置的查询算法处理相关请求．把图6（c）中Lisya所在位置缩小后，得到图7．本算法根据Lisya的位置以及请求参数，为Lisya生成一个结果区域RR，区域内有很多医院，其中包含了满足Lisya要求的前5个最邻近的医院，但是不知道具体是哪5个．最后服务器将深绿色区域内的所有医院都返回给Lisya，让Lisya的客户端程序自动筛选（如图5（b）所示）．至此，一次LBS请求的处理完成．

4 系统性能测试

我们对系统性能进行了评估，收集了1 000个LBS的测试数据，其中用户的多边形隐匿区域的平均顶点个数为16个，平均K－Anonymity参数是3，网络平均延迟为20 ms．实验分别对数据传输、KCR生成以及P－RNN算法等部分进行了测试，结果如表1所示．

图6 中间件KCR生成过程Fig．6 Generating procedure of KCR middleware

图7 LBS请求处理Fig．7 Answer of LBS request

表1 系统各部分测试Tab．1 Tests on each part of system

图8 LBS系统各部分用时百分比Fig．8 Percentages of each part of LBS system

与大多数网络应用一样，系统中数据传输部分耗费时间最多，成为性能的主要瓶颈．如图8所示，网络耗费占了整个LBS过程的65%，其中客户端与中间件之间、中间件与服务器之间的数据传输量较小，主要是多边形隐匿区域以及服务请求参数的传输，它们的耗费时间大部分用于建立TCP网络连接．而服务器与客户端之间是以搜索结果中的位置信息为传输对象，传输量较大，耗时较多，传输耗费时间与搜索结果集的大小成正相关．KCR的生成相对于网络数据传输来说，所耗费的时间比较小，原因是中间件使用了R－Tree空间索引，加速了邻近用户的查找．同样是使用了索引进行加速的查询处理算法则耗费较高，主要是因为查询算法需要对每个顶点进行一次点最邻近查询操作．在本实验中，平均每次查询算法都要进行16次点最邻近查询．当KCR的多边形顶点个数增多时，算法所耗费的时间也将按比例增加．与已有的矩形隐匿区域相比，这是多边形隐匿区域的缺点，同时多边形隐匿区域也有着矩形隐匿区域无法替代的优点．在查询算法生成结果区域RR后，服务器需要获取RR中的所有查询目标，RR越大，目标数量也越多．因此这部分消耗时间与RR的大小成正相关．总体来看，本系统能够有效支持基于多边形隐匿区域的LBS查询．

5 总 结

本文针对已有隐私保护的LBS系统的不足，设计和实现了一个基于多边形隐匿区域的LBS系统．该系统采用客户端、中间件与服务器3层结构，在客户端和中间件分别进行一次位置泛化，对用户的位置隐私进行双重保护．其中，客户端支持自定义的隐匿区域，服务器端则支持处理基于多边形隐匿区域的查询处理．最后，对系统性能进行了测试，结果表明了系统的有效性．

［1］周傲英，杨彬，金澈清，马强．基于位置的服务：架构与进展［J］．计算机学报，2011，34（7）：1155－1171．

［2］薛姣，刘向宇，杨晓春，等．一种面向公路网络的位置隐私保护方法［J］．计算机学报，2011，34（5）：865－878。

［3］黄毅，霍峥，孟小峰．CoPrivacy：一种用户协作无匿名区域的位置隐私保护方法［J］．计算机学报，2011，34（10）：1977－1985。

［4］潘晓，郝兴，孟小峰．基于位置服务中的连续查询隐私保护研究［J］．计算机研究与发展，2011，47（1）：121－129．

［5］MOKBEL M F，CHOW C，AREF W G．The new casper：Query processing for location services without compromising privacy［C］／／Proceedings of the 32nd Internationl Conference on Very Large Date Bases．ACM，2006：763－774．

［6］CHOW C Y，MOKBEL M F，HE T．Tinycasper：A privacy－preserving aggregate location monitoring system in wireless sensor networks［C］／／Proceedings of the 2008 ACM SIGMOD Internationl Conference on Management of Date．ACM，2008：1307－1310．

［7］GHINITA G，KALNIS P，SKIADOPOULOS S．PRIVE：Anonymous location－based queries in distributed moblile systems［C］／／Proceedings of the 16th International Conference on World Wide Web．ACM，2007：371－380．

［8］张鹏，童云海，唐世渭，等．一种有效的隐私保护关联规则挖掘方法［J］．软件学报，2006，17（08）：1164－1774．

［9］GAO J，YU J X，JIN R M，et al．Neighborhood－privacy protected shortest distance computing in cloud［C］／／Proceedings of the 2011 ACM SIGMOD Internationl Conference on Management of Date．ACM，2011：409－420．

［10］王璐，孟小峰．位置大数据隐私保护研究综述［J］．软件学报，2014，25（4）：693－712．

［11］LIU Y，CHEN X，LI Z，et al．An efficient method for privacy preserving location queries［J］．Frontiers of Computer Science，2012，6（4）：409－420．

［12］陈修伟．基于多边形隐匿区域的定位服务研究［D］．广州：中山大学，2010．