近年来,空间定位技术与移动通信技术迎来了快速的发展,促进了许多提供基于位置服务（location-based service,LBS）的应用的出现。然而,有许多研究表明,LBS服务可能会暴露用户的隐私信息,攻击者可以通过用户的位置信息实现对其敏感隐私信息的推断。针对LBS服务中的安全问题,人们开展了广泛的研究工作,其中常见的位置隐私保护技术包括基于加密的技术、基于虚假位置的技术、基于匿名区域的技术以及基于用户协作的技术。基于加密的技术安全性最高,但现实可行性差。基于虚假位置的技术实现简单,但安全性无法得到保证。基于匿名区域的技术以及基于用户协作的技术都能保证一定安全性,但基于匿名区域的技术往往需要引入可信第三方,基于用户协作的技术中服务质量受用户分布密度影响较大。为了解决位置隐私保护中的k近邻查询问题,SpaceTwist方案提出用户选择一个虚假位置作为锚点,然后通过增量近邻算法实现准确的k近邻查询,不暴露真实的位置信息。不过,SpaceTwist方案无法保证K匿名安全性,也没有解决其中锚点的选取问题。本文将结合上述位置隐私保护技术,对SpaceTwist方案进行分析与优化,主要的工作内容如下:1.通过对SpaceTwist方案的主体算法,即增量近邻查询算法的讨论,分析SpaceTwist方案的安全性保护程度,给出了在特殊情况下用户可能位置所形成攻击区域Ω的表达式,以及一般情况下通用的攻击算法,并进一步指出增量近邻查询算法中各参数取值对SpaceTwist方案安全性的影响。2.为优化POI查询效率,结合R树提出一种能实现高效查询的SpaceTwist方案,服务器将预构造R树对POI空间数据进行存储,在具体查询时,调用分支定界算法对R树进行深度优先遍历,就可完成k近邻结果的索引。本文在不同规模的合成数据集上进行了仿真实验,与基于普通索引方法的SpaceTwist方案相比,该方法具有更高的查询效率,查询响应时间更小,并且POI数据规模越大,其优势越明显。3.针对SpaceTwist方案无法实现K匿名以及未解决锚点选取的问题,提出了一种名为轻量级K匿名 INN 算法（lightweight K-anonymity incremental nearest neighbor,LKINN）的位置隐私保护方案,能够以较低的计算代价实现INN算法的K匿名化。LKINN基于混合式位置隐私保护架构,对系统中的所有成员都只做半可信的安全性假设。仿真实验结果表明,LKINN能够杜绝半可信用户对正常用户隐私的窃取,并且拥有更短的查询响应时间以及更低的通信成本。