随着移动通信技术和定位技术的飞速发展,基于位置服务(Location-based service,LBS)在世界范围内得到了广泛应用,特别是最近几年各种商业的LBS产品不断涌现,丰富了用户的日常生活和娱乐同时也带动了周边行业的发展,已经在人们的日常应用中占据重要地位。然而在LBS给用户带来便利的同时,其中的隐私泄漏问题也逐渐显现,尤其是位置隐私泄漏问题一旦不能得到很好地解决,将极大地威胁用户的生命和财产安全。目前为止相关的研究者已经提出了多种位置隐私保护方法,来保护用户的位置隐私,其中研究最广泛的就是位置k-匿名。传统的位置k-匿名虽然能为用户的位置隐私提供一定的保护,但是也存在着缺陷,例如当生成的匿名区域内用户聚集到某一点时,用户的具体位置信息仍然会被锁定。为了解决该问题,在对用户位置隐私进行保护时,不仅要考虑位置k-匿名也要考虑位置l-多样性,即生成的匿名区域要包含l个不同的物理位置。目前针对这方面的研究较少,因此本文提出了一种基于聚类的隐私保护方案,可以很好的满足位置k-匿名与位置l-多样性,并通过实验验证了方案的优越性,具体内容如下:(1)总结了现有的位置隐私保护技术和系统结构,并重点介绍了位置k-匿名和位置l-多样性。(2)提出了一个基于聚类的隐私保护方案,该方案可以很好的满足位置k-匿名与位置l-多样性。方案包含的算法有基于聚类分析的匿名算法BAUC(Based-on analysis using clustering-algorithm)和基于离散网格单元的匿名算法BDGC(Based-on discrete grid cells)。BAUC算法首先利用基于密度聚类算法对历史用户位置数据进行分析,并使用B~+树索引分析后的结果,然后采用匿名区域分片思想为用户生成满足位置k-匿名与位置l-多样性的匿名区域。由于BAUC算法在使用之前需要事先获得所服务区域的真实用户位置数据,因此方案还包括了BDGC匿名算法。该算法用来在本方案初始阶段为用户提供位置匿名服务,并积累用户位置数据,算法主要基于网格划分的思想进行改进。另外本方案还包括了所提匿名算法对应的匿名查询处理方法。(3)实现了本文所提方案中的匿名算法,并对实验结果进行了分析。分析结果表明本文所提算法在多个评价指标上具有优势,进而验证了文中方案的优越性。