近些年来,随着通信技术以及手机等智能终端设备的发展,基于位置的服务(Location-Based Service,LBS)在人们生活中的应用也越来越广泛,但是在享受位置服务的过程中,用户需要将自己的位置信息发送给LBS服务器,因此用户也开始担心自己的隐私被泄露。所以人们希望在享受基于位置服务的时候,自己的隐私也能够得到保护。虽然目前已经有很多针对基于位置服务的隐私保护算法,但是其中大部分的算法都没有考虑到攻击者可能会利用边信息(例如位置的历史查询概率)来获取用户的位置隐私。本文针对这方面进行深入研究,主要工作如下:首先提出了一种位置假人生成算法(Dummies Generation Algorithm,DGA),DGA算法采用的是基于最大熵值的原则以及贪心策略来选择位置假人。考虑到攻击者有可能会利用地图上各个位置的历史查询概率来筛选用户可能的出现位置,DGA算法提出并证明了一种基于最大熵值的位置假人选择原则,并利用这种原则来选择位置假人,每次挑选位置假人的时候都尽量选择与用户真实位置的历史查询概率相等或者最接近的位置。这样最终选出的位置假人和真实位置都有着相似的历史查询概率,以达到混淆攻击者的目的。其次为了使得生成的位置假人不要过于集中在用户真实位置附近,本文提出了增强型位置假人生成算法(Enhanced-Dummies Generation Algorithm,E-DGA)。E-DGA算法不仅考虑了地图上各个位置的历史查询概率,同时也考虑到了各个位置假人的空间分布问题。在生成位置假人的时候基于最大熵原则并采用贪心策略选择与用户真实位置具有相似历史查询概率的位置假人,以达到混淆攻击者的目的。再次为了让位置假人分布的更均匀本文又提出了圆形位置假人生成算法(CircleDummies Generation Algorithm,C-DGA)。C-DGA算法首先依据用户真实位置生成一个圆形最小隐私区域,并找到每个k等分圆的半径延长线,然后在这些延长线上选择位置假人,而在选择位置假人的时候也是采用最大熵原则和贪心策略来做进一步的筛选。最终C-DGA算法生成的位置假人都均匀分布在一个圆形区域内,而且具有相似的历史查询概率。最后本文通过设计实验仿真对该算法进行了性能评估,实验仿真结果表明:DGA算法不仅能够保护用户的位置隐私不被泄露,而且还减少了生成位置假人的运行总时间;E-DGA算法能够达到与DGA算法同样的位置隐私保护级别,虽然其生成位置假人的总时间稍长于DGA算法,但是其在平均距离差方面的性能要优于DGA算法;C-DGA算法位置隐私保护级别与DGA算法和E-DGA算法相似,而且生成位置假人的总时间要比DGA算法和E-DGA算法短,C-DGA算法生成的位置假人空间分布更加均匀。