基于贝叶斯网络的路网位置匿名区域估计
蔡朝晖1,2, 张健沛1, 杨静1
1.哈尔滨工程大学 计算机科学与技术学院,哈尔滨 150001
2.大庆师范学院 计算机科学与信息技术学院,黑龙江 大庆 163712

蔡朝晖(1968),女,副教授,博士研究生.研究方向:数据挖掘,隐私保护.E-mail:dq_caizhaohui@163.com

摘要

基于道路网络模型,结合路网数据,通过贝叶斯网络证据相关推理的概率计算,并利用最大似然理论确定最小匿名区域估计,提出了一种基于贝叶斯网络的路网位置匿名区域估计方法。仿真实验结果表明,该方法可为基于位置服务中的隐私保护提供适时、适度的匿名区域建议,提高了匿名时间和匿名精度,从而从整体上提高服务质量。该方法还可以利用已知路网数据,进行客观推理,为个性化匿名需求提供合理建议,解决了移动用户查询中较多的不确定性问题。

关键词: 人工智能; 位置隐私保护; 查询敏感度; 贝叶斯网络推理; 个性化隐私需求; 最小匿名区域估计
中图分类号:TP309 文献标志码:A 文章编号:1671-5497(2014)2-454-5
Anonymous area estimation method of path data based on Bayesian network
CAI Zhao-hui1,2, ZHANG Jian-pei1, YANG Jing1
1.CollegeofComputerScienceandTechnology,HarbinEngineeringUniversity,Harbin 150001,China
2.CollegeofComputerScienceandInformationTechnology,DaqingNormalUniversity,Daqing 163712,China
Abstract

In this paper, an anonymous area estimation method of path data based on Bayesian network is proposed. This method is based on the path network model, combined with road network data, and the maximum likelihood theory is used to determine the minimum anonymous region estimation. Simulation results show that the proposed anonymous area estimation method can provide timely and proper anonymous region suggestion for the privacy protection based on the position service, thus, the service quality in terms of anonymous time and precision. The proposed method also makes use of the known path data for objective reasoning and providing reasonable suggestion to individuation anonymous demands, which solves the major uncertainty problems in the mobile user queries.

Keyword: artificial intelligence; location privacy protection; query sensitivity; Bayesian network; personal privacy requirements; anonymous area estimation
引言

随着传感定位技术和无线通信技术的发展,基于位置的服务(location_based service,LBS)技术得到了广泛应用。典型的LBS应用包括基于位置的紧急救援服务、基于位置的信息查询服务、基于位置的公共信息或广告服务等。但是,在享受基于位置的服务时,人们同时也意识到了自己的隐私受到了威胁[ 1]。使用基于位置服务的隐私威胁主要有位置隐私泄露[ 2]和查询隐私泄露[ 3]

位置隐私保护[ 4]需要隐藏用户精确位置,称作位置匿名。在LBS中,位置匿名处理要求经过某种手段处理用户的位置,使得个体位置无法识别,从而达到保护用户位置的目的。文献[5]首次提出的位置K-匿名模型(Location K-anonymity model),是将信息发布的 k-匿名技术用到位置匿名中,也是位置匿名处理中使用最多的模型。相比于位置隐私保护而言,对查询隐私保护[ 6, 7]的要求则复杂很多:首先,保护查询隐私需要研究查询内容的语义[ 8],以防止同性质查询攻击[ 7];其次,为了防止位置连接攻击,需要研究连续查询请求[ 6]或背景分析攻击下的连续位置隐私保护[ 9]和查询内容的多样化需求[ 7, 10]等。文献[2]把K-匿名的隐私需求度、用户的时间容忍度、空间容忍度设置为个性需求参数,首次提出了位置匿名的个性化模型。

目前,基于道路网络的位置隐私保护[ 9, 11, 12]主要集中在匿名算法优化和连续查询轨迹保护等方面,对于个性化需求建议的研究不多。考虑到道路网络中的位置匿名区域的大小,会直接受到查询时间、所在路段特征及交通流量等概率性因素的影响,本文构建了基于位置匿名过程中相关条件的联合概率推理结构——最小匿名区域估计的贝叶斯网络,旨在根据道路网络的已知数据和相关先验信息来确定当前查询的最小匿名区域估计。由于需要结合路网数据做计算,所以,此方法目前适用于中心匿名器结构,即使用可信第三方的匿名结构。

1 模型的建立
1.1 推理过程框图

根据查询请求构建的推理过程如图1所示:

图1 结合道路网络数据的匿名区域确定过程框图Fig.1 Process chart of Anonymous area estimation

参照相应定义,图1符号记法及说明如下:

①查询目标为用户查询目标内容或名称,记为query。

②匿名度需求为匿名参数 是指用户希望匿名区域内查询目标的差异度。

③时间/空间需求为用户个性化需求参数的时间容忍度和空间容忍度,分别用符号 Tmax和[ Amin, Amax]表示。

④运行速度为移动用户的当前速度矢量,其中方向记为+/-,速度值记为 v

⑤系统时间time为用户提交查询的时间。

⑥当前位置为移动用户查询时刻GPS定位坐标( x, y),最终转换表示为道路标识和道路相对位置( r_id,pos),其中GPS定位正常误差为30~50 m。

⑦道路特征为道路分类、是否单行等数据信息,通过对应的 r_id与相关的路网信息相关联。

1.2 贝叶斯网络结构及参数条件概率表

根据上述推理过程框图,构造匿名区域估计的贝叶斯网络如图2所示:

图2 匿名区域估计的贝叶斯网络Fig.2 Bayesian network for Anonymous area estimation

图中确定了各相关变量及其状态集。这些变量包含了连续型节点和离散型节点,其中的连续型分布变量(如时间time、道路相对位置pos)等,需要转换成由若干离散区间构成的离散分布。具体如下:

①道路编号 r_id的特征信息分为:快速路、主干路、次干路、支路。

②道路相对位置pos的特征信息分为:基本路段、交叉口路段、灯岗路段。在实际应用中,快速路与其他类型道路的路段划分方法不全相同。

③查询时间time的特征信息分为:高峰时段、正常时段、车流稀少时段。

④运行速度 的特征信息分为:高速、中速、低速;正向记为+,反向记为-。

⑤路段数据是车流量统计count,其特征信息分为:饱和流、稳定流、自由流。

⑥用户个性需求之多样化参数

⑦查询目标query的特征信息按其语义敏感度分为:高、中、低。例如:“肿瘤医院”、“中医院”、“眼科医院”都视为同一敏感度级别:“医院”。本文使用 值越大查询敏感度越高。

⑧用户个性需求的匿名参数

⑨在当前查询匿名成功条件下(即区域minA中包含其所要求的 个用户),最小匿名区域minA的特征信息参照查询所在道路长度分为:大(minA> len( r_id))、中(0.5 len( r_id) len( r_id))、小(0 len( r_id))。

根据专家经验和推理规则,构造条件概率(表1~表3):

表1 查询目标敏感度的条件概率表 Table 1 Conditional probability of query sensitivity
表2 车流量统计的条件概率表 Table 2 Conditional probability table of the count of vehicles
表3 匿名请求、车流量统计、最小匿名区域、查询目标对应关系 Table 3 Corresponding relations of request,count,minA and query
1.3 区域估计推理过程

为简化计算复杂度,忽略对较弱的相关证据节点的依赖,图2中min A节点的相关证据推理过程如下:

①计算第二层第2、3节点的概率分布:

②由第一层第1个节点的概率分布

联立(1)~(3)式,推导可得:

式中: 表示子节点证据。

2 区域匿名建议及效果分析
2.1 实验环境及数据

使用VC++编程环境模拟道路网络[ 13]查询和匿名环境(编写基于路网的中心匿名器匿名算法[ 7, 11]),选择匿名成功可能性较高的查询(正常以上时段、次干路以上路段),选定5种不同敏感度级别的查询目标。本实验采用Brinkhoff Data Generator数据发生器。

实验输入数据主要分两部分:用户输入数据,GPS定位数据。

(1)随机批量输入查询请求Q,个性化参数值如下:

查询位置匿名需求:数据类型为int,系统默认值为1,测试值范围[2,25];

查询目标多样化需求:数据类型为int,系统默认值为1,测试值范围[2, k];

查询时间容忍度:数据类型为float,系统默认值为40,测试范围[1,40];单位为秒(s);

查询空间容忍度:数据类型为float,系统默认值为[0,20],测试范围(0,20],单位为千米(km)。

(2)查询请求Q的GPS传感器定位数据输入如下:

所在路段编号:首位编码1~4分别表示快速路、主干路、次干路、支路,数据类型为char,测试范围为[10000,40000];

路段相对位置:数据类型为float,测试范围为[0,0.99];

系统时间:数据类型为float,测试范围为[0,23.59]。

实验输出数据有两个:最小匿名区域min A、平均匿名时间mean_time,具体参见表4:

表4 模拟实验数据集 Table 4 Experiment data set
2.2 实验结果及分析

(1)不同敏感度查询的最小匿名区域对比

图3可知,位置匿名需求 值达到[10,20]时,最小匿名区域会有一个跳跃,说明在大多数情况(正常的时间和路段)下,一定时间间隔(平均匿名时间)内,查询请求数量可以达到10和20之间,匿名请求如果在15以下,按最小匿名区域(min A)建议,匿名器基本上可以满足其个性化隐私需求,即匿名请求成功率比较高。

图3 不同敏感度查询的最小匿名区域对比图Fig.3 Comparation of minimum anonymous areas to different sensitivities

(2)不同敏感度查询的匿名时间对比

对于多样化需求参数 来表示查询目标的敏感度需求。由图4:

图4 不同敏感度查询的匿名时间对比图Fig.4 Comparation of anonymous time to different sensitivities

在值的0.5处跳跃比较大,说明敏感度在1/2以内的查询目标隐私需求成功率高,即请求响应时间比较快。综合两个对比结果,在一般情况下,本文提出的最小匿名区域建议,对于位置匿名需求小于15、敏感度需求小于1/2的查询请求,其匿名时间在[2,11]范围之间,是一个正常的匿名时间范围[ 7];而对于匿名需求大于15、敏感度大于1/2的查询请求,其匿名时间主要分布在[12,16]范围内,匿名效率明显高于正常[ 7]的匿名时间范围[15,20]。

3 结束语

提出的基于贝叶斯网络的最小匿名区域估计方法为基于位置服务中的位置隐私保护提供了适时、适度的匿名区域建议,提高了匿名时间和匿名精度,从而整体上提高了服务质量。利用可获得的已知路网数据,进行客观推理,为个性化匿名需求提供合理建议,也解决了移动用户查询中较多的不确定性问题。

The authors have declared that no competing interests exist.

参考文献
[1] Authorities: GPS system used to stalk womanhttp: //www. usatoday. com/ tech/new/2002-12-30-gps-stalker_x. htm, 2002. [本文引用:1]
[2] Gedik B, Liu L. Location privacy in mobile systems: a personalized anonymization model[C]∥Proceedings of the 25th IEEE International Conference on Distributed Computing Systems, Columbus: IEEE Computer Society, 2005: 620-629. [本文引用:1]
[3] Chow C, Mokbel M F. Enabling private continuous queries for revealed user locations[C]∥Proceedings of the 10th International Conference on Advances in Spatial and Temporal Databases. Boston: Springer, 2007: 258-275. [本文引用:1]
[4] Mokbel M F. Privacy in location-based services: state-of-the-art and research directions[C]∥Proceedings of 8th International Conference on Mobile Data Management, Mannheim, 2007: 228. [本文引用:1]
[5] Gruteser M, Grunwald D. Anonymous usage of location-based services through spatial and temporal cloaking[C]∥Proceedings of the International Conference on Mobile Systems, Applications, and Services, Scan Francisco, 2003: 163-168. [本文引用:1]
[6] Gabriel Ghinita, Panos Kalnis, Ali Khoshgozaran, et al. Private queries in location based services: anonymizers are not necessary[C]∥Proceedings of the 2008 ACM SIGMOD International Conference on Management of Data, SIGMOD, 2008: 121-132. [本文引用:2]
[7] Xiao Z, Xu J, Meng X F. P-sensitivity: a semantic privacy-protection model for location-based services[C]∥Proceedings of PALMS2008, China, 2008: 47-54. [本文引用:6]
[8] Gedik Bugra, Liu Ling. Protecting location privacy with personalized k-anonymity: architecture and algorithms[J]. IEEE Transactions on Mobile Computing, 2008, 7(1): 1-18. [本文引用:1] [JCR: 2.395]
[9] Baik Hoh, Marco Gruteser. Protecting location privacy through path confusion[C]∥Proceedings of the First International Conference on Security and Privacy for Emerging Areas in Communications Networks, Athens, 2005: 194-205. [本文引用:2]
[10] Machanavajjhala A, Gehrke J, Kifer D. L-diversity: privacy beyond K-anonymity[C]∥Proceedings of 22nd International Conference on Data Engineering, Atlanta, 2006: 24-35. [本文引用:1]
[11] Wang Ting, Liu Ling. Privacy-aware mobile services over road networks[C]∥Proceedings of the VLDB Endowment, Lyon, 2009, 2(1): 1042-1053. [本文引用:2]
[12] Chow C, Mokbel M F, Bao J, et al. Query-aware location anonymization for road networks[J]. GeoInformatica, 2011, 15(3): 571-607. [本文引用:1] [JCR: 1.0]
[13] Li Fei-fei, Cheng Di-han, Marios Hadjieleftheriou, et al. On trip planning queries in spatial databases[C]∥Proceedings of 9th International Symposium, SSTD 2005. Berlin: Springer, 2005: 273-290. [本文引用:1]