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

图1

Fig.1

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

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

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

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

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

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

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

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

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

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

图2

Fig.2

	Figure Option ViewDownloadNew Window
	图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

表1(Table 1)

表1 查询目标敏感度的条件概率表 Table 1 Conditional probability of query sensitivity query P( l/k|query) (高,中,低) 俱乐部 (0.6,0.4,0.0) 酒吧 (0.5,0.4,0.1) 医院 (0.4,0.3,0.3) 酒店 (0.3,0.3,0.4) 饭店 (0.3,0.4,0.3) 银行 (0.2,0.2,0.6) 学校 (0.0,0.1,0.9)

表1 查询目标敏感度的条件概率表 Table 1 Conditional probability of query sensitivity

表2

Table 2

表2(Table 2)

表2 车流量统计的条件概率表 Table 2 Conditional probability table of the count of vehicles 车流量 P( r_id|count) P(pos|count) P(time|count) P( v|count) (快速,主干,次干,支路) (基本,交叉,灯岗) (高峰,正常,稀少) (高,中,低) 饱和流 (0.1,0.4,0.4,0.1) (0.1,0,5,0.4) (0.8,0.2,0.0) (0.0,0.1,0.9) 稳定流 (0.2,0.4,0.3,0.1) (0.2,0.4,0.4) (0.7,0.3,0.0) (0.0,0.4,0.6) 自由流 (0.4,0.1,0.2,0.3) (0.5,0.2,0.3) (0.0,0.2,0.8) (0.7,0.2,0.1)

表2 车流量统计的条件概率表 Table 2 Conditional probability table of the count of vehicles

表3

Table 3

表3(Table 3)

表3 匿名请求、车流量统计、最小匿名区域、查询目标对应关系 Table 3 Corresponding relations of request,count,minA and query Q.k query count P(minA|Q. k) Q.k query count P(minA|Q. k) (小,中,大) (小,中,大) 2 饭店 自由流 (0.2,0.5,0.3) 8 医院 自由流 (0.1,0.3,0.7) 2 饭店 饱和流 (0.3,0.6,0.1) 3 银行 饱和流 (0.4,0.5,0.1) 5 饭店 稳定流 (0.1,0.5,0.4) 10 银行 稳定流 (0.2,0.4,0.4) 10 饭店 稳定流 (0.3,0.6,0.2) 5 酒吧 自由流 (0.2,0.4,0.4) 2 医院 自由流 (0.1,0.2,0.7) 12 酒吧 稳定流 (0.1,0.4,0.5) 6 医院 饱和流 (0.4,0.4,0.1)

表3 匿名请求、车流量统计、最小匿名区域、查询目标对应关系 Table 3 Corresponding relations of request,count,minA and query

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

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

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

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

式中: 表示子节点证据。

使用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

表4(Table 4)

表4 模拟实验数据集 Table 4 Experiment data set Q.k query ( r_id,pos) Q.time [ Amin, Amax] min A mean_time [2,25] 饭店 (10023,0.4) [10∶00,22∶00] [2,25] [0.5,5] [1,4] 8.62 [3,25] 酒店 (20154,0.2) [0∶00,24∶00] [3,25] [4,5] [2,7] 8.78 [6,25] 医院 (30059,0.1) [6∶00,17∶00] [4,25] [7,10] [3,10] 9.65 [6,25] 酒吧 (20236,0.7) [16∶00,4∶00] [5,25] [5,10] [6,10] 10.7 [11,25] 俱乐部 (30107,0.9) [0∶00,24∶00] [6,25] [5,20] [10,20] 11.78

表4 模拟实验数据集 Table 4 Experiment data set

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

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

图3

Fig.3

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

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

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

图4

Fig.4

	Figure Option ViewDownloadNew Window
	图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]。