随着移动互联网技术、GPS定位技术的蓬勃发展以及智能设备和社交网络的普及应用,基于位置的服务（LBS,Location-based Services）也开始成为了人们生活中的一个重要应用。LBS使得用户的日常生活变得十分灵活和方便,但与此同时,长时间使用LBS也会对用户的隐私数据安全带来潜在的隐私泄露隐患。当用户根据自己的需求向LBS服务器提出查询信息的请求时,要将个人的身份、位置、兴趣等隐私信息一起发送到LBS服务器,如果这些信息被不受信任或恶意的LBS服务器泄露,攻击者可以利用链式攻击模型将用户的身份作为主键,然后再将收集到的位置隐私信息、兴趣爱好等与用户的身份进行链接,还可以推断出用户更多的私人信息。因此,LBS中位置隐私保护越来越重要,并受到信息安全领域专家和研究者的高度重视。目前,国内外学者对位置隐私保护提出较多的保护技术,传统技术如K-匿名技术、密码学技术等。但K-匿名技术无法防止属性公开,也无法抵抗同质攻击模型和背景知识攻击模型。密码学技术在计算和通信上花费较高。德沃柯等人提出的差分隐私技术解决了以上两种传统技术的缺陷,首先,差分隐私技术[14]可以抵抗背景知识攻击模型;其次,差分隐私技术是建立在数学基础上实现的,不仅能够灵活地使用数学工具,而且此技术还能量化评估隐私保护程度;最后,差分隐私技术通过对隐私预算参数进行合理地设置,当对用户位置信息数据库中增加一条数据记录或者删除一条数据记录时,用户最终的查询结果与未进行操作时的查询结果相比并不会发生太大的变化,从而使得攻击者无法进行分辨到底是增加或者删除了哪条数据记录。基于差分隐私技术和马尔可夫模型,本文对用户位置隐私数据的保护进行了研究,主要工作如下:（1）由于n-阶马尔可夫模型不仅具有低时间复杂度和预测准确度高的优势,而且,用户即将进入的下一个位置不仅仅与用户当前所在位置有关,还与用户以往的所有历史位置相关,历史位置数量越多,预测的精准度越准确。因此,本文采用n-阶马尔可夫模型对用户即将进入的下一个位置进行预测,并提出基于马尔可夫模型的位置预测算法（LPBMM,Location Prediction Based on Markov Model）;而且用户的行动轨迹具有马尔可夫过程的特性,因此,本文采用n-阶马尔可夫模型对轨迹中的位置节点计算位置敏感度,提出基于n-阶马尔可夫模型的位置敏感度算法（LSBMM,Location Sensitivity algorithm Based on n-order Markov Model）。（2）针对已知用户的一组连续位置,首先,利用LPBMM算法对用户的下一个位置进行预测;其次,根据位置数据的特点和检索难度构建位置隐私树（LPT,Location Privacy Tree）结构,对LPT预测值最大的两个节点合理的分配隐私预算,并且添加拉普拉斯噪声以保护位置隐私,基于差分隐私技术,提出了位置保护算法（LPBDP,Location Protection algorithm Based on Differential Privacy）。将该算法与其余两种算法进行比较,实验结果表明,LPBDP算法有效地提高了数据可用性和隐私保护程度。（3）针对已知用户的多组连续位置,首先,利用LSBMM算法计算位置节点的敏感度,因为敏感度的大小就决定了其隐私保护程度的大小,敏感度越大,说明该位置对于用户来说越重要;其次,因为有一些位置敏感度较低,也就意味着对于用户来说该位置不是很重要,对其分配隐私预算意义不大。为了避免该问题,本文对敏感度阈值进行了设计,对符合位置的敏感度及敏感度阈值要求的位置数据分配合理的隐私预算,从而对位置数据添加拉普拉斯噪声进行保护,并对添加拉普拉斯噪声之后的位置数据构建噪音前缀树（PT,Prefix Tree）。为了更好地保证数据的可用性,对PT中的位置数据通过滤波器进行处理,经过滤波器处理的优势是过滤掉多余的噪声提高数据的可用性且时间复杂度降低,基于差分隐私技术,提出了相应的轨迹保护算法（TPBDP,Trajectory Protection algorithm Based on Differential Privacy）。将该算法与其余两种算法进行比较,实验结果表明,TPBDP算法有效地提高了数据可用性和隐私保护程度。本文针对用户不同位置数量的情况,针对每种情况分别提出相应的位置隐私保护方法,所提位置隐私保护方法有效避免了攻击者通过数据挖掘、地理拓扑结构等方法分析用户敏感信息的风险。理论分析和仿真实验结果表明,本文所提方法在保证用户位置隐私得到保护的前提下,其数据可用性较高,且算法运行时所消耗的时间较少。