移动环境下基于掩护区域的最近邻居查询研究

卢秀芸，孙小培，朱玉全

(1. 江苏联合职业技术学院镇江分院 信息系，江苏 镇江 212016； 2. 镇江市第一人民医院 信息中心，江苏 镇江 212002； 3. 江苏大学 计算机科学与通信工程学院，江苏 镇江 212013)

移动环境下基于掩护区域的最近邻居查询研究

卢秀芸1，孙小培2，朱玉全3

(1. 江苏联合职业技术学院镇江分院 信息系，江苏 镇江 212016； 2. 镇江市第一人民医院 信息中心，江苏 镇江 212002； 3. 江苏大学 计算机科学与通信工程学院，江苏 镇江 212013)

针对移动环境下最近邻居空间查询的位置保护问题，提出基于掩护区域和移动方向的最近邻居空间查询(PSDNN)算法。PSDNN算法使用掩护区域替代掩护位置，结合移动用户的方向，从而在空间网络的最近邻居查询过程中有效保护移动用户的位置信息。实验结果表明，PSDNN算法的位置隐藏机制是可行的。

移动环境；位置保护；空间查询；位置服务

近年来，随着移动通信技术的迅速发展与广泛应用，基于位置的服务逐渐普及，用户的位置保护成为移动应用中的重要研究内容[1]。移动用户需要了解相关数据时，可以通过移动应用软件发出位置请求，如“找到最近的加油站”“找到最近的3家医院”等[2]。为了得到相关数据，请求查询时，用户不得不透露他们当前的位置。从服务提供商(Location Based Service Provider，LBSP)的服务器查询位置的记录，有可能促使其他用户收集历史位置，进而监测一些用户的行为，反过来侵入他们的隐私[3]。因而，移动用户进行最近邻居查询时隐私信息的保护成为移动应用中的一个关键问题。

文献[4]总结了移动环境下保护位置隐私技术所面临的挑战。针对备受关注的k-匿名算法，利用值得信赖的服务器收集用户的位置信息，执行隐藏程序，隐藏空间的边界由其他用户的位置来定义。但该算法涉及参数超过10个，查询工作量大，应用过于复杂，可行性较差。文献[5]提出了基于位置服务的同时不危及位置隐私的安全框架，但只考虑了自由空间环境，并不完全适用于现实环境。因此，本文提出一种改进的网络空间查询隐藏机制，为解决隐私保护的最近邻居查询提出新的算法，即通过掩护区域与移动用户的方向相结合来保护移动用户信息的最近邻查询算法(PSDNN算法)。实验结果表明，PSDNN算法具有可行性。

1 相关知识及定义

支持隐私保护的空间查询系统架构设计有3个主要实体：移动用户、位置的隐藏、基于位置的服务提供商[6]。用户在限定网络里移动，支持隐私策略，具体到要求保密每个用户的位置信息[7]。在此过程中，主要关注隐私策略中的3个参数：k-匿名程度、最小掩护区域Rmin，最小覆盖网络段Smin。基于保密功能，要求在不同的地点具有不同的时效性，用户可以随时更新隐私策略[8]。因为移动用户具有移动性、方向性，目标之间的最短网络距离取决于网络之间的连通性和移动用户的方向性，所以应根据连通性和方向性确定最邻近客户。

1)k-匿名程度。为了隐藏确切的位置，用户可以要求掩护区域涵盖k-1个最近邻居的位置。

2) 最小掩护区域Rmin。为了在用户高度密集的区域保持一个合理规模的掩护区域，用户决定可接受的最低规模。

3) 最小覆盖网络段Smin。移动用户在限定的空间里移动，为了避免定位跟踪，掩护区域必须包含最小数量的道路段。

4) 掩护位置。移动用户可以信任的中间代理人，掩护位置不断收到移动用户的位置更新，在将这些信息提供给基于位置的服务提供商之前，利用个人用户隐私策略来模糊它的确切位置到掩护区域(Area of Cloaked，Ac)。此外，在将查询提供给基于位置的服务提供商之前，掩护位置将查询用户的位置匿名映射到一个掩护区域。在查询中与用户身份相关的信息会在隐藏进程中被掩护位置移除。

5) 存储空间数据。存储空间数据可归类为公共数据和私有数据[9]。公共数据包括静态的信息，如医院、旅馆、加油站等的位置，也包括直接向公众开放的动态信息，如实时公交地点等。私有数据主要包括从掩护位置隐藏的移动用户位置。图1和图2分别为私有数据的公共查询和私有查询。

图1 私有数据的公共查询

图2 私有数据的私有查询

为了管理移动用户的位置，采用基于网格的金字塔数据结构[10]。金字塔结构的动态性是为了监测目前整个空间区域中每个单位空间的移动用户数。因此，可以有效地计算掩护区域的大小。在掩护区域的最小数量的道路段，移动用户的隐私可以得到较好的保护。

6) 近似类划分。移动用户是按照移动方向进行数据集划分的，划分为4类、8类、16类、32类等，区别在于间隔角度，4类划分是每隔90°为一类，8类是每隔45°为一类，16类是每隔22.5°为一类，32类是每隔11.25°为一类。以此类推，可以根据实际需要进行划分。算法MODD给出了划分为4类的近似划分过程。

算法MODD：移动对象数据近似划分MobileObjectDataDivision(S)

输入：S，待划分的数据集。

输出：T={S1，S2，…，Sk}，按照移动对象的速度和移动方向划分后的数据集。

If (S!=null) Then

For (EacheInS)

Switch(θ(e)′sangel)

Case 90°～180°： {S2=S2{e}; break;}

Case 180°～270°： {S3=S3{e}; break;}

Case 270°～360°： {S4=S4{e}; break;}

End For

End If

2 基于掩护区域和移动方向的空间近邻查询PSDNN

为了解决隐私保护的查询机制，着重研究最常见的最近邻居查询。

给定一个查询点q和一个对象数据集S，网络里k个最邻近查询就是数据集S存在k个基于网络距离最邻近q的对象。通过掩护区域隐藏后，基于位置的服务提供商只能得到掩护区域的用户位置。为了在掩护区域和空间网络得到包含查询结果的数据集，提出根据移动用户的移动方向扩大增量网络的基于掩护区域和移动方向的空间近邻查询(Privacy Protected Spatial Network Direction Nearest Neighbor Query，PSDNN)算法。移动方向的划分使用4类近似划分MODD算法。

PSDNN算法将掩护区域Ac与空间网络的所有交互点作为数据点集S，数据点集S由算法MODD近似划分为m类得出。如果T不为空，那么Ac至少包含一个网络段。这些网络段表示为Seg，在Ac里面的为Segi，在Ac外面的为Sego。依照网络扑拓，网络边缘在Ac内可以完全连接或有几个不同的组别。PSDNN算法为了得到检索的结果集，从所有的交叉点进行网络扩展。首先，对集合T中的点ti，用PSDNN算法获取ti所属划分类，找到通过ti的网络段PmPn，并且在这个段搜索所有的数据对象。与此同时，把端点Pm和Pn插入队列Q。如果在PmPn里搜索少于k个对象，PmPn的一个端点到ti的距离小于Dist (ti,nk)，nk是ti的第k个最邻近对象，端点Px邻近ti将从Q中扩展。对于没有访问的邻近点Px，PSDNN搜索PxPy，更新结果集，把Py到ti的距离插入Q。然后，集合Q中到ti距离最短的点出列。重复这个过程，直到k个最邻近ti的对象被找到，这k个对象更新至结果集Results。PSDNN重复这个过程，直到搜索了T中所有的点。

PSDNN算法如下：基于掩护区域和移动方向的空间近邻查询PSDNN(q，k，Ac，d)

输入：q，发出查询的移动客户；k，最邻近移动客户个数；Ac，掩护区域。

输出：符合移动客户q查询的结果Results。

InsertIntersectionPointsFromAc(S={t1，…，tm})

T={S1，S2，……，Sm}

InsertIntoFromAc(Results)

If (Sum(Ac))>=kThen

For(EachtiInT)

GetDirection(ti)

ExpandAcDist(ti,nk)

AddTo(Results)

Else

For(EachtiInT)

AddTo(Results) From (Pm,Pn)

Q={(Pm,Dist(Pm,ti)), (Pn,Dist(Pn,ti))}

While Dist(P,ti) < Dist(ti,nk)

AddTo(Results) From (Px,Py)

SortRemovingDuplicates(Results)

Return Results

3 模拟实验及分析

模拟实验中，机器配置为2.90 GHz的i7双核CPU，8 GB主存，500 G硬盘。模拟程序采用Microsoft Visual Studio 2010的VC#.Net语言编写。数据库方面，采用Microsoft SQL Server 2008，采用真实数据集[10]，Real Datasets for California Road Network，表CNodes(NodeID，Longitude，Latitude)，表CEdges(EdgeID，StartID，EndID，L2Distance)，表CPOIN(CategoryName，Longitude，Latitude)和表CPOI(Longitude，Latitude，CategoryID)。表CNode保存21048条位置信息，表CEdges保存21693条相连通的位置信息，表CPOIN保存105725条原始影响点(Point of Interest，POI)信息，表CPOI保存104770条经过转换的POI信息。影响参数有3个，分别为隐藏区域Ac，k值、POI，针对影响参数分别取不同范围的数值以观察实验结果。图3讨论了当Ac取2%～10%，PSDNN查询的结果集(Result Set，RS)和查询时间(Query Second，QS)的变化。图4讨论了当k值取3，5，7，10时，对PSDNN查询的结果集(RS)和查询时间(QS)产生的影响。图5讨论了当POI在200～800之间时，PSDNN查询的结果集(RS)和查询时间(QS)的变化。

模拟实验结果显示，PSDNN查询的结果集(RS)和查询时间(QS)主要受隐藏区域Ac，k值、POI的影响。

图3 Ac对PSDNN的RS和QS影响

图4 k值对PSDNN的RS和QS影响

图5 POI对PSDNN的RS和QS影响

1) 随着隐藏区域Ac的增加，Ac和更多的网络段相交，产生的候选结果集增大。结果集中包含Ac中所有的POI和搜索范围，由于PSDNN移除部分重复对象，因此PSDNN RS曲线增长幅度变小。

2) 随着最近邻居数值k的增加，结果集接近于线性增加，如当k=3时，结果集包含约4%的对象，当k=10时，结果集包含多于10%的对象；PSDNN查询时间接近于线性增加。

3) 随着POI的增加，PSDNN查询的结果集缓慢增加，查询时间明显变长。

4 结束语

隐私保护的空间查询是移动环境下的重要问题之一。本文提出改进的掩护位置的方法，给出基于掩护区域和移动方向的空间近邻查询PSDNN算法，主要目的是用掩护区域来隐藏移动用户的确切位置，模拟实验验证了此方法的有效性。由于PSDNN算法受一些参数的影响，因此需要进一步讨论各参数值选定的方法，使其更具有通用性。另外，需要扩展该算法以适应空间网络中其他私有保护查询处理的模型。

[1] SHIN K G, JU X, CHEN Z, et al. Privacy protection for users of location-based services[J].IEEE Wireless Communications,2012,19(1): 30-39.

[2] NUSSBAUM D, OMRAN MT, SACK J, et al. Techniques to protect privacy against inference attacks in location based services[C]//M General Chair-Ali, E General Chair-Hoel. Proceedings of the 3rd ACM SIGSPATIAL International Workshop on Geostreaming. New York:ACM, 2012:58-67.

[3] 黄毅,霍峥,孟小峰.CoPrivacy：一种用户协作无匿名区域的位置隐私保护方法[J].计算机学报,2011,34(10): 1976-1985.

[4] KHOSHGOZARAN A, SHAHABI C, SHIRANIMEHR H. Location privacy: going beyond K-anonymity，cloaking and anonymizers[J].Knowledge and Information Systems,2011,26(3):435-465.

[5] 周傲英,杨彬,金澈清,等.基于位置的服务：架构与进展[J].计算机学报,2011,34(7):1155-1171.

[6] CHOW CY, MOKBEL MF. Privacy in location-based services：a system architecture perspective[J]. Sigspatial Special,2009,1(2):23-27.

[7] WIGHTMAN P M, ZURBARAN M, RODRIGUEZ M,et al. MaPIR：mapping-based private information retrieval for location privacy in LBISs[J].IEEE Workshop on Network Security，2013,10(8):964-971.

[8] CROFT WL, WEI S, SACK J, et al. Location-based anonymization: comparison and evaluation of the Voronoi-based aggregation system[J]. International Journal of Geographical Information Science,2016(11):1-23.

[9] 陈伟,杨龙,于乐.数据融合中支持隐私保护的完整性动态验证算法[J].计算机科学,2013,40(7):84-88,120.

[10] YIU M L, JENSEN CS, HUANG X, et al. Space twist：managing the trade-offs among location privacy，query performance，and query accuracy in mobile services[J].IEEE International Conference on Data Engineering,2008,786(2):366-375.

[11] LI F F. Real datasets for spatial databases：road networks and points of interest[EB/OL].( 2009-09-05) [2016-05-06].http://www.cs.utah.edu/～lifeifei/SpatialDataset.htm.

〔责任编辑： 卢 蕊〕

Astudyonnearestneighborquerybasedoncloakedareasinmobileenvironment

LU Xiuyun1, SUN Xiaopei2, ZHU Yuquan3

(1. Information Departmeat，Zhenjiang Campus of Zhenjiang Joint Vocational and Technical College，Zhenjiang 212016，China ; 2. Information Center，Zhenjiang First People's Hospital，Zhenjiang 212002，China ; 3. School of Computer Science and Telecommunications Engineering，Jiangsu University，Zhenjiang 212013，China)

Privacy Protected Spatial Network Nearest Neighbor Query (PSDNN) algorithm was proposed for resolving the location protection problem on spatial networks query under mobile environment. The algorithm improves the method protecting user privacy by cover position and combined with the direction of the mobile users to protect location privacy of mobile users on the process of nearest neighbor queries on spatial networks. Experimental results show that PSDNN algorithm is feasible and effective.

mobile environment; location protection; spatial query; location-based service

2017-03-11

江苏省科技型中小企业技术创新基金(14C26213201047)

卢秀芸(1982—)，女，江苏镇江人，讲师，硕士，主要从事移动计算、数据库系统研究；孙小培(1983—)，女，河南许昌人，工程师，硕士，主要从事移动计算、数据库系统研究。

TN94

： A

：1008-8148(2017)03-0049-04