21世纪,是一个信息技术高速发展的时代,日新月异的信息技术使人们的生活也发生了极大的变化,包括教育、医疗、购物等方方面面。在信息时代,GPS定位技术的发展与通信设备的普及,使人们的出行越来越便捷,无论是查询兴趣点还是选取最短路径,我们都可以节省很多时间,因此位置服务的受欢迎程度与日俱增。但位置服务是把双刃剑,在给人们带来便捷的同时也带来了威胁,当用户享受位置服务时,信息传输的过程中可能会造成位置隐私的泄露,进而给用户带来利益损失,因此,位置隐私保护开始被关注。为了位置服务与隐私保护两者兼顾,学者们提出了各种位置隐私保护技术,其中最常见的是k-anonymity模型。但是,现有的位置隐私保护技术很少考虑到路网等真实环境,而且用户对算法的查询精度和性能等方面存在不满,因此,本文在前人的基础上提出了基于Voronoi图的路网k-匿名位置隐私保护方法。该算法考虑到路网的结构以及实时的路网数据情况,采用有第三方服务器的中心匿名结构,对用户的位置数据进行了两次处理,路网交叉点视为维诺图单元的基点,利用维诺图将路网分割成维诺图单元,在客户端用户将基点视为锚点并代替用户的真实位置,将处理后的位置发送给第三方服务器,第三方服务器在Voronoi单元中查找至少k个用户,满足k-匿名模型的条件,当用户稀少时生成相应数量的哑元,完成对用户位置的模糊化处理。实验结果表明,该算法不仅能够有效地保护位置隐私,而且查询的整个过程中没有发送真实位置,可以防止攻击者的链路攻击,在服务质量方面也具有高效性。但在基于Voronoi图的路网k-匿名位置隐私保护方法中,用锚点代替用户的真实位置,因此查询精度较低,为了提高这一性能,在该算法的基础上提出了基于路网的Geohash位置隐私保护方法(G-Voronoi)。G-Voronoi匿名算法在客户端用Geohash编码代替用户的真实位置,用户可以根据自己的喜好选择编码长度。将Geohash编码发送给第三方服务器进行匿名处理,利用Geohash编码的特点查找最近邻,然后用Voronoi图单元对最近邻用户进行剪枝,解决Geohash编码存在突变性的缺点,最后判断匿名区域中用户的数量是否满足k-匿名,决定生成哑元的数量。最后,将Voronoi图算法与G-Voronoi匿名算法进行对比,通过实验证明G-Voronoi匿名算法不仅保留了原算法的优点,而且在服务质量、精确度有所提高,而且G-Voronoi算法将二维的空间坐标转换为一维编码,因此在查找最近邻时不必在使用欧式距离的浮点计算,直接利用前缀树对字符串查询,相同前缀越长两者的距离越近,缩短了匿名过程花费的时间。