移动感知数据替换预取策略对基于位置的移动服务的保护和提升

沙特国王大学学报MAD-RAPPEL：移动感知数据替换和预取策略扎根LBSAjay K.Udai Shanker？Gupta GuptaCSE部门，M.M.M.U.T.，Korakhpur 273010，India阿提奇莱因福奥文章历史记录：收到2020年2020年5月13日修订2020年5月14日接受2020年5月20日网上发售保留字：基于位置的服务移动系统中的安全、隐私授权应用服务A B S T R A C T移动设备的功能正在不断升级，以通过允许使用上下文感知数据来向寻求基于位置的信息的移动用户提供服务质量。为了保护个人提出了一种基于空间k-匿名的移动感知数据替换预取策略MAD-RAPPEL。它通过在缓存替换和预取中形成隐藏区域来增强用户隐私缓存替换和失效模块通过移动性马尔可夫模型对移动用户的轨迹的应用，使用下一个位置预测算法。采用客户-服务器排队模型对系统进行仿真实验，以考察MAD-RAPPEL的性能。通过仿真得到的结果表明，所提出的MAD-RAPPEL最大限度地减少了LBS的开销相比，已经存在的现有的LBS。©2020作者由爱思唯尔公司出版代表沙特国王大学这是一个开放的访问CC BY-NC-ND许可证下的文章（http://creativecommons.org/licenses/by-nc-nd/4.0/）。1. 介绍基于位置的服务是一种无处不在的基于计算的服务，其通过将设备位置通过GPS显式地集成或隐含地集成在查询中与其他相关信息来有效地向所有用户提供巨大价值的服务。基于更新策略，任何上下文感知系统中的查询可以分为两种类型，即，常规查询和连续查询。如果移动客户端改变其位置，则常规查询结果不会随时间自动更新;而在连续查询中，移动客户端仅发送一次查询，并且然后如果随着客户端移动到不同区域而发生位置的任何更新，则服务器将自动通知移动客户端的位置和/或新的查询结果虽然GPS提供了有效的户外定位，但它可能不适合无线设备的位置识别，因为很少有手持设备没有内置GPS接收器。为了解决这个问题，Sukaphat（Sukaphat，2011）开发了一个LBS框架*通讯作者。电子邮件地址：ajay25g@gmail.com（A.K. Gupta）。沙特国王大学负责同行审查Android Cell Identifier API。在该LBS框架中，位置监视机制作为后台操作来执行，并且其在周期内周期性地执行该信息的传输。GIS服务开始在手持设备上扩展GeoFairy（Sun等人， 2017）是一个LBS实现，为用户提供实时地理空间细节。移动应用程序的一个很好的例子，可以帮助用户查看，跟踪，解释和模拟GeoPackage格式的Google地图和OpenLayers上的数据（Zhang等人， 2016年）。LBS正在经历多个根本性的困难，如低质量的连接，稀缺的地理基础设施，有限的容量和定期断开到网络。 LBS缓存几乎没有解决上述缺陷。在原始LBS实现中，如果查询的数据项不在移动用户的缓存中，则查询分析器必须接受具有其位置的设备请求并处理它们以返回查询结果。以前提出的策略的缺点是，它们很容易泄漏有关用户的敏感细节，如用户位置和相关数据，以获得商业利益给不受信任的第三方。解决LBS隐私问题有不同的策略。包括Cloaking在内的可信第三方通常被认为已经利用了LBS的隐私策略，其中圆圈用于匿名用户位置。这也降低了兴趣点（POI）的服务质量（QoS）。因此，当应用LBS以提高缓存性能来改善消费者隐私时，应该解决这些问题。为了聪明和乐观，设备https://doi.org/10.1016/j.jksuci.2020.05.0071319-1578/©2020作者。由爱思唯尔公司出版代表沙特国王大学这是一篇基于CC BY-NC-ND许可证的开放获取文章（http://creativecommons.org/licenses/by-nc-nd/4.0/）。制作和主办：Elsevier可在ScienceDirect上获得目录列表沙特国王大学学报杂志首页：www.sciencedirect.comA.K. 古普塔，美国Shanker/沙特国王大学学报3455也需要能够预测潜在的背景。设备确定未来位置的能力用于缓存的预取（Ilayaraja，2016）。这有助于减少查询分析器显式交互的需要，实际上提高了消费者的安全性。在以前的许多政策中，都存在隐私和服务效率的权衡。LBS牺牲了用户隐私，以满足移动客户端发出的查询的最大POI。此外，在先前的策略中显示出高系统开销（处理和通信成本）。为了应对上述挑战，进一步的研究旨在设计多级缓存，以防止未经授权的访问客户端机密信息的隐形区域公式。目的是为了更好地保护用户隐私，空间k-匿名和预取。简单地一个接一个地布置算法将影响系统性能。由于一个人不可能在一次尝试中解决所有的问题，我们只选择了几种方法来提高LBS的性能。为了解决上述LBS问题，我们使用CEMP替换-无效来进行缓存替换-无效和预取，并使用空间k-匿名（PSKA）来保护用户的信息。上述策略利用n阶移动性马尔可夫模型来预测移动用户的下一个位置。移动用户的下一个位置的预测被用于无效替换和PSKA。缓存、预取和空间k-匿名方案的整体框架有助于用户我们的研究考虑了多用户缓存数据项的成本估计在Anonymizer缓存替换更好的缓存命中率和降低开销。因此，将建议的模块集成到一个框架中，导致系统性能的提高与最小的开销。论文的提纲安排如下。的过去工作的调查和问题陈述在第2中定义。LBS架构、假设和建议的策略描述将在第3节中讨论。我们模拟的主要发现的细节在第4节中给出。最后第5节给出了本文的结论，并列出了该领域未来研究的范围。2. 相关工作由于位置服务中对象的移动性，使得其具有网络频繁断网、带宽不足、本地资源有限等特点，近年来人们对位置服务做了然而，仍然存在许多挑战。缓存用于处理其中的一些缺点。为了使访问成本最小化和信息可访问性增强，系统应该具有客户端缓存功能。为了降低访问成本并提高信息质量，程序应该具有客户端缓存功能。在系统约束条件下，移动数据库系统（MDS）使用缓存替换机制来处理存储的 还实施了不同的 替换缓存策略 （ Gupta 和 Shanker ，2018），以处理MDS中缓存空间可用性较早的高速缓存替换方案（例如，最不常用、最近最少使用和当前最少使用-K）的访问顺序指示时间局部性（He等人，2016年），这对LBS来说是不现实的。替换协议从移动客户端的高速缓存中选择一些标准进行清除或替换。替换策略模型包括作为先前访问的位置点和在这些点上的访问时间的序列的输入，并且其提供预期的下一位置和相关联的访问时间作为输出。当前的时空缓存替换策略是Man-曼哈顿（Dar等人，1999）、PAID（Zheng等人，2002）和MARS（Lai等人，2004年）。曼哈顿更换政策（Dar等人，1999）是计算Manhat-tan距离的传统替换策略之一，即，移动消费者当前位置与缓存数据对象的原始位置之间的距离。在这种方法下，具有最大曼哈顿距离的数据对象被从缓存中驱逐。曼哈顿策略存在一个很大的缺陷，即移动客户端的临时访问位置和移动路径没有被包含在缓存数据项回收的决策中。MARS战略解决了数据对象的更新问题，同时采取步骤替换它们。与此相反，没有数据项的更新记录随着PAID策略而演变。存在另一种用于移除高速缓存的策略，称为Furniture Away Replacement（FAR）（Ren等人，2000），其首先替换客户端从其合法有效范围字段移开的那些数据项。该策略允许驱逐系列依赖于客户端到数据项有效范围引用点的距离。这种方法的缺点是它不能识别移动客户端预取用于在使用之前预加载内容。内容缓存主要处理客户端已经请求的数据项。预取的基本原理是基于客户端与服务器的通信，使用各种机器学习和优化方法（Gupta和Shanker，2020; Gupta，2020;Gupta和Shanker，2020）来确定未来内容的预期需求。预取系统由四个重要的组成部分，即PF引擎，预测引擎，在线数据库，和缓存。一般的预取过程涉及一组定义明确的步骤。移动客户端通过PF引擎向服务器发出主动请求。该数据请求被发送到预测引擎，预测引擎处理该数据请求并将相关查询转发到在线数据库。然后，该查询由在线数据库处理，并将结果数据发送到服务器，服务器进而将相应的响应传递给移动用户。最后，移动客户端将数据发送到PF引擎，并更新其缓存数据。预取引擎考虑许多变量，如用户操作、位置和日志数据，以预测要预取的内容。为了获得客户端的访问行为，大多数预取算法分析日志数据，并根据兴趣度对要预取的元素进行排序。为了提高系统在断开连接时的可用性，可以将预取和空间索引技术与LBS相结合。兴趣点（POI）信息（Al-Molegi等人，2018; Al Molegi等人，2018）预 先 存储在用户的缓存中。取决对他们的首选项，服务用户已分组为各种簇类别，使得代理可以有效地预取对象。Yin等人（Yin等人，2002）提出了一种基于值系统的自适应预取算法，为每个数据对象分配一个值。取决于所分配的兴趣、现有剩余功率水平、访问时间、升级速度数据大小，设备可以确定预取成本并且动态地改变预取的决定。Hu等人（Hu等人，2003）提出了一种具有自适应预取滑动的缓存策略。在该策略中，根据使用缓存空间的缓存数据项执行动态修改。预取精度的提高是提高自适应性的关键因素。自适应性是预取策略的主要关注点，特别是在资源容量（即能量、空间和缓存）受限的移动计算环境中。预取方案在没有适当规划的策略的情况下可能招致不必要的资源成本（Yin等人，2002; Drakatos等人，2009年; Pallis例如，2008年）。许多研究人员提出了有效开发预取策略的方法。Jiang 和Kleinrock（Jiang and Kleinrock，1998）建议的研究工作涉及系统资源的有效利用。在他们的方法中，预取行为被动态修改3456A.K. 古普塔，美国Shanker/沙特国王大学学报这取决于连接的效率。在（Wyatt等人，2005年），提出了一种侧重于策略和代理的预取方法。数据挖掘、机器学习（Li等人，2008; Ahmad等人， 2017）、模式识别（Monreale等人，2009; Giannotti等人，2007）和统计推断是具有类似目标的各种领域，并且可以用于发现和解释数据中的模式以获得有用的结论。监督学习和无监督学习（Wyatt et al.，Wyatt andChoudhury，2005）是两类机器学习技术。第一种方法使用标记有正确答案的历史数据来训练模型，以便将来可以将其应用于分类（预测目的）。第二类机器学习，即，无监督学习不使用先前的数据来训练模型，即，它没有任何带有标记的正确答案的历史数据;相反，它试图发现数据中的模式。最近，终端平台上的缓存也继续吸引人们的研究兴趣。研究人员正试图解决缓存的关键问题例如，"缓存在哪里？”（Rao等人，2016; Zheng等人，2017年，“什么是缓存？”（Wang等人，2017年，“如何进行缓存？”（Akon等人，2013; Drakatos等人，xxxx）。自适应功能的目的是通过预取模块的自动化来提高效率。Drakatos等人（Drakatos等人，2009）提出了一种用于依赖于位置和移动的高速缓存预取的预测方案。提出的移动方案集中在小区是能够检测用户的行为和预测的潜在位置的用户。基于与问题特征（先前应用记录）相结合的预期未来位置，设备将更可靠地预取数据对象。然而，这方面的细节在该计划中没有讨论。这通过评估用户的当前未来位置（基于移动预测）、相关联的查询背景数据和预定义的用户期望简档来工作。它估计了消费者未来需求的可能性。然而，由于不同的因素，用户的偏好在整个运行时会动态地改变.相比之下，规则和客户偏好的预定义分析（Chen，2005）是满足未知情况的一个重要方面，除非消费者可以相应地为所有可想象的场景明确指定几个特定要求。在某些情况下，一个人不能可靠地描述他或她对事件的概率。对消费者预期的分析是提高预测方案准确性的主要因素之一。作为性能改善，总体适应性是经常增加是由于资源费用减少。然而，目前的工作（Burklen等人，2006;Choi等人，2005; Del Prete和Capra，2010）没有理解用户对动态的需求。对于用户来说，在所有可能的情况下手动调整特定的口味几乎是不切实际的。程序在运行时不仅要依靠以前的应用数据，还要考虑用户的实际环境，自主地确定用户的选择。为了解决这个障碍，我们目前的方法旨在使用上下文感知的方法来自动预测消费者在运行时的行为。有不同的方案来保护LBS用户位置的匿名性。当前的位置安全解决方案可以分为四组，包括匿名策略、隐私策略、监管策略和混淆。Zhang等人在（Zhang等人，2018年9月）提出了通过统一网格进行缓存，以更好地保护用户隐私。但是由于同时查询的限制，系统中的查询开销变得非常大。Niu等人（Niu等人，2014）建议在高速缓存中的一对伪位置选择，用于更好的用户位置保密性，但是该系统具有其不适用于连续查询的缺点。在低消费人口的地方，在先前建议的依赖于空间隐身的隐私保护策略的版本中，制定的隐身区域大小可能会大得多。伪装区域大小与QoS成反比。在用户密度较低的情况下，制定大的伪装区域可能会降低QoS或经常导致拒绝服务。用户密度可能很小，因为设施很少使用，而且它们位于偏远地区。空间隐身策略可以与k-匿名相结合，以解决匿名策略的限制个人位置跟踪由于其操作的性质而可能侵犯隐私。k-分集和l-分集是最常见的解决方案。然而，这些方法也可能损害个人的隐私，因为它们更多地关注如何保护固定区域，并且周围区域仍然可以公开关于该区域的细节。Yuan Tian et al. （Tian等人， 2012）首次介绍了在基于位置的服务中实现马尔可夫的功能。他们还建议将密码学的隐私保护与连续马尔可夫链相结合以提高可靠性，这不仅提高了基于位置的数据的准确性，而且还保证了位置细节的保密性，从而产生可信赖的位置服务器和服务提供商侧。在（Tian等人，2019），Yuan Tian等人介绍了一种云的设备位置隐私预保护方法，以保持消费者轨迹的完整性。对用户的移动行为进行了评估，并提出了扩展受限领域以满足消费者隐私标准的政策 还在（Tian等人， 2020），Yuan Tian et al. 提出了一种用于随机位置隐私安全的边计算方法隐形方案将用户的确切位置转换为隐形位置，以满足在该区域获得k个用户的预定义概率该方案确实保护了精确的位置细节免受攻击。高系统开销（处理和通信成本）在以前的策略中显示。为了应对上述挑战，进一步的研究旨在设计多级缓存，以防止未经授权的访问客户端机密信息的隐形区域制定。在以前的许多政策中，存在着价格和服务效率的3. MAD-RAPPEL-使用空间k匿名的移动性感知数据替换和预取策略enrooted lbs在移动客户端采用缓存进一步提高了系统的性能和可用性。鉴于上述挑战，我们使用了类似于SPMC-CRP（Gupta andShanker，2017）的基于n阶移动性马尔可夫模型的缓存替换模块和类似于CELPB （ Guptaand Shanker ， 2018 ）方案 的失效模块 SPMC-CRP和CELPB方案的下一个位置预测模块被n阶移动性马尔可夫模型所取代我们的研究考虑了多个用户缓存数据项的成本估计，以更好的缓存命中率和降低开销的Ancuberizer缓存替换。3.1. 系统架构在这里，一个名为Ancriminizer的中介是由Query Analyser和用户之间Anastroizer掩盖了智能手机用户的精确位置。尽管在这个模型中，Ancriminizer是最终的设备输出瓶颈，因为所有的用户查询都要经过Ancriminizer。该策略采用预取和空间k-匿名技术，通过A.K. 古普塔，美国Shanker/沙特国王大学学报3457使用从Ancartizer获得的伪装区域，因此不会受到Query Analyser推理攻击。该框架的设计包括查询分析器、智能手机客户端和匿名器。分析器匿名器选择满足k-匿名性参数的小区。分析查询的可能性，以在k个小区中选择一个小区作为隐藏区域。如果在k个小区中的每一个小区中存在很少的用户，则发送消息的特定用户的可能性将至多为1/k。Ancuri-zer具有来自类似单元中的相同消费者的查询的背景Query Analyser表示基于位置的应用程序，该应用程序链接到Anonymizer获取的相应隐藏区域。移动网络应用程序在相互合作的基础上与附近的其他智能手机设备一起它具有计算能力、全球定位、数据存储以及与社区中其他智能手机设备连接的能力除了内容缓存（通过缓存替换和失效）之外，LBS还增加了预取模块，以增强用户体验并优化缓存访问。预取引擎会考虑许多变量，例如用户操作、位置和日志数据，以预测要预取的内容。获取访问行为在客户端，大多数预取算法都是通过分析日志数据，对需要预取的元素进行度量和排序，兴趣的程度。代理PF优于服务器PF和客户端PF，因为对不同客户端和服务器的共同兴趣的分析在客户端之间共享预取内容，但是不能分析针对所有客户端的给定数据项的共同请求。在本文中，客户端、代理（anonymi- zer）和查询分析器缓存空间的一部分被保留用于预取。LBS在除了预留用于预取的缓存空间之外的缓存空间中应用替换和无效过程。在这里，我们有基于马尔可夫模型的算法，用于在预留的预取空间中预取热数据项。3.2. 假设移动用户被认为是可信的，并透露他们的真实位置。没有对等节点将有害信息传输到网络的接触范围内的相邻客户端LBS具有加密系统，例如散列和密码系统，以保持传输数据的保密性和有效性建议的立法从移动用户的角度移动客户可以在高、中、低隐私标准之间进行选择这里使用了一个理想的标准，这取决于操作水平和隐私交换。如果阈值高，则LBS可能侵犯用户隐私并且满足智能电话用户建议的MAD-RAPPEL实现了PSKA方案，通过在LBS系统中创建隐身区域来增强隐私提出了一种多级缓存机制，系统假设用于下一个位置计算的完整轨迹（移动历史）信息被假设存储在服务器上而不是客户端上。服务器每隔一定的时间间隔发送存储在服务器上的移动单元全轨迹中路径中介数最大的信息，以达到缓存失效和替换的目的。针对LBS面临的挑战，设计了集成的缓存替换、失效和预取策略。接下来的位置预测模块采用了不同的数据挖掘方法。SPMC的下一个位置预测模块-用于缓存替换的CRP和用于无效的CELPB方案（Zheng et al.，2002）已被n阶移动性马尔可夫模型所取代。如果移动用户在发出查询后到达新位置由于在蜂窝区域中直到响应被返回的数据访问延迟，因此在这种情况下，有效性检查是期望的。给定数据项的几何形状或区域的有效性由有效范围表示（Gupta和Shanker，2017）。建议的MAD-RAPPEL参考架构和查询分析器内部架构如图1和图2所示. 2分别。3.3. 基于马尔可夫模型的下一个位置估计下一个位置的预测可以用于找到未来某些用户访问的下一个可能性。为了预测下一步去哪里，马尔可夫模型使用最后访问过的位置的轨迹。所考虑的图案的测量长度在顺序中是已知的。包含在模式中的最近位置访问的数量被称为马尔可夫预测器的阶数。马尔可夫预测器（Hazan and Shabtai，2017）是一种马尔可夫模型。此顺序用于定义上次访问的位置数用于下一个位置预测。马尔可夫模型存储所有模式的下一个位置概率。这些概率是根据用户访问位置的模式和/或其频率计算的。在（Al Molegi等人，2018），作者提出了一个经典的n阶马尔可夫链，以在智能手机环境中发现感兴趣的区域。他们评价了一个马尔可夫预测器，该预测器通过置信度估计的方式进行优化。马尔可夫技术本质上是一种完全没有记忆的技术。马尔可夫模型可以是自主的或受控的。国家的下一次分配完全取决于当前的国家。一个自治的马尔可夫过程会自己进化，在受控马尔可夫过程的情况下，人们可以对一个影响结果的系统施加动作。个体移动行为可以使用移动性马尔可夫链建模为离散随机过程，其中一个状态到另一个状态的转换依赖于过去的状态和状态转换概率分布。为了反映有向非循环图，每个节点中的马尔可夫过程对应于一个状态，标记为边的概率权重对应于这些状态之间的转移概率。边缘是POI之间的过渡，分配有关联的概率权重以执行过渡。移动性的马尔可夫模型可以表述如下。1. 状态集合S= {s 1，. . sn}用于根据重要性的顺序来表示POI的频繁集合。这些状态被附加上语义标签，如“家”、“办公室”、“路”等，这可以直接从移动性马尔可夫模型推导出来。2. 用箭头表示的一组转换ti， j用于表示状态si到状态sj的移动性概率。 这组转移可以用转移概率矩阵Pn×n来定义，其中n代表移动性马尔可夫链中的一些参与状态。用户请求的下一个位置预测问题直接影响到Web服务器缓存的性能和延迟。存在各种方式来处理用户的位置历史的列表并且确定用户将在哪个下一位置处进行数据项请求以使得其可以被预取。一种方法是通过使用关联规则进行序列模式挖掘。另一种方法是为一个地区的消费者流动性的范例构建一个模型，作为马尔可夫过程。在用户请求数据项期间访问的位置由下式描绘：所述状态和边表示在来自给定用户的移动日志中计算的状态之间的转换概率。行进到新位置的用户概率取决于用户的当前状态和先前n个状态的序列。这些状态分别用一阶马尔可夫模型和n阶马尔可夫模型表示.利用马尔可夫3458A.K. 古普塔，美国Shanker/沙特国王大学学报I>令Z是迄今为止用户访问的位置的量MMMFig. 1.建议的基于位置的服务框架的体系结构。图二、查询分析器的详细架构描述快速地增加了存储器需求，而低阶马尔可夫模型不能准确地预测用户的后续请求。隐马尔可夫模型（HMM）可以通过人的运动历史来检验。然而，该模型不能预测新的位置点请求，因为它们基于过去访问的位置请求数据。在这里，我们提出了一种基于马尔可夫模型的预取算法，用于基于个人的访问模型的下一次访问预测，该访问模型跟踪对数据的前n次访问。这里，1阶马尔可夫模型链（1-MMC）仅对应于单个POI; n阶马尔可夫模型链（n-MMC）表示n个过去访问的POI的链。 在我们的测试中，轨迹数据集分为两部分即评估（或测试）集和准备（或训练）集。测试集用于产生n-MMC，测试集用于确定预测器的精度。最后，基于训练的n-MMC，还测量用户在基于马尔可夫模型的下一个位置预测中，第一步是从移动用户的密集GPS轨迹中提取停留点GPS轨迹定义见第3节定义1如果两个轨迹点A（xi，yi，ti）B（xi +1，yi+1，ti+1）满足以下两个条件，则称它们位于同一停留区域内。地区算法1示出了从用户移动区域提取POI的过程它是从轨迹停留点中提取的，其中停留点的计数达到某个频率限制即最小停留计数（minCs）。算法1使用DBSCAN过程提取用户兴趣点。DBSCAN程序使用半正矢公式来估计停留点之间的距离。算法1的输入参数由三元组（x，y，t）中的停留点移动性迹线（T）、最小集群停留计数（minC_s）和扩展集群的局部半径（Eps）组成算法1的输出是用户LBS应用算法3，根据构造的n阶马尔可夫移动链或转移概率矩阵直接计算用户的下一个位置为了从兴趣点的轨迹最终序列计算马尔可夫模型初始概率矩阵，我们从用户访问的轨迹序列评估序列的一致性概率。给定当前状态T1，进入状态T2的概率为条件概率Prob（T2|T1）。ProbPi1jPi是在Pi之后获得Pi+1的条件概率。序列发生的可能性计算如下。如果<你不介意的话！Pi1>Pqxi≤Dr þ ðxiþ1-xiÞProbPi1jPiþ频率计<具有n个过去访问过的位置的状态，由Tn = P，Pm z-（n- 1）z-qti1-ti2≤Tr停留点的位置应为位于同一停留点内的所有轨迹点的平均纬度和经度（n-2），. . ，Pz>.然后，在n阶马尔可夫模型中，在n个位置点的集合访问Tn之后到达下一个位置pi的概率计算如下。n<频率！P i> P区在下一步骤中，从这些停留点提取POIPOI是分布密度高的区域ProbPijTmMfrequencyTn> n<22A.K. 古普塔，美国Shanker/沙特国王大学学报3459算法1：发现POI集群//移动轨迹T的踪迹的预处理输入：移动轨迹（T）的轨迹由停留点（x，y，t）组成Eps是扩张星系团的局部半径（Eps）开始将所有停留点p∈ T设置为未访问对于来自all_client的每个移动客户端，对于每个点如果p∈噪声或聚类，则继续;否则如果num（Neighbor_Eps（p））minCs，则//使用函数Neighbor_Eps（p）计算点p在局部半径Eps内的邻域将p标记为噪声其他将p标记为新的中心并将其添加到新的聚类C，然后将Neighbor_Eps（p）的所有p个添加到POI聚类C对于每个未访问的q∈ Neighbor_Eps（p），Neighbor_Eps（q）if num（Neighbor_Eps（q））>minCs然后获取Neighbor_Eps（q）将点取消标记到POI集群C中端端End if端为每个用户如果是普通日和连续POI考虑任何POI和设定时间=第一个POI时间端End if返回POI群集C端算法2：n阶移动马尔可夫链构造.输入：由停留点（x，y，t）组成的移动轨迹（T）的轨迹POI群集合并宽度（Cw）先前持有位置的计数（n）最小群集停留计数（minCs）Eps是扩张星系团的局部半径（Eps）开始在移动轨迹（T）的跟踪上应用发现POI聚类算法（算法1）以发现最重要的聚类合并公共点共享群集通过合并位于Cw语义距离内的POI聚类得到C列表对于C列表中的每个群集C，测量C端按密度降序对C列表对于C列表中的每个群集Ci，对于pi，在移动性马尔可夫转移概率矩阵端对于每个POI，如果POI和群集Ci中心之间的距离宽度小于半径i，则在FIFO中用Ci和n-1个先前位置改变当前位置用Ci和n-1个先前位置端否则结束在迹线m上标记端删除带有“未识别”标记的痕迹。将连续的公共标签移动轨迹替换为一个模式。计算每对马尔可夫链状态之间的所有转移概率返回计算的n阶马尔可夫转移概率矩阵3460A.K. 古普塔，美国Shanker/沙特国王大学学报我我P≥ ≥JC¼þ算法3：Next_POI_Location_Prediction。输入：n阶转移概率矩阵客户端移动历史T：pt1→pt2→···→ptm，开始在具有n个先前访问过的位置的n阶转移概率矩阵中找到行X pt 1 →pt 2 →···→pt m返回对应于行X矩阵中具有最大转移概率的列的POI。端在n阶马尔可夫模型中采用后剪枝步骤，对马尔可夫模型状态中的异常状态进行剪枝。这种修剪的结果具有更高的预测精度，对存储空间的需求更少。每当客户端向应用程序提交一个查询时，首先会查看数据库缓存、邻居缓存和解析器缓存。如果查询的响应在其中任何一个中可用，则它将直接返回给移动用户;否则，此查询将重定向到Ancriminizer。实际上，Ancherizer将互联网设备的轨迹的多功能性n阶马尔可夫模型扩展到依赖于各种参数的下一个位置预测，即，特定系统之间转换的概率和水平。预取和空间k-匿名性然后被扩展以使用移动用户的输入来塑造隐身区域，即，单元缓存贡献率、位置、数据新鲜度。查询分析器接收具有隐藏区域的POI查询查询分析器根据使用单元缓存贡献率、设备新鲜度，甚至可能的下一个位置，Ancriminizer制定了消费者期望的隐藏区域。在该方法中，Anastrizer选择满足k-匿名性参数的小区。分析查询的可能性以在k个单元中选择单元，一个隐形区域缓存中第j个对象在单元i中查询的可能性由Pj定义。假设，第j个对象最后所用的周期访问是t1，当前设备时间是t，并且最近访问的加权由α定义以近似似然性。对现有的当前访问概率的更新可以被示意性地定义如下。PJ一1-a我tc-tl j查询分析器具有关于特定单元格Pi（M i 1）的查询概率的信息如果有k个单元格，则每个单元格中至少有一个用户，因此提交直接负责的请求的可能性最多为1/k。PSKA的战略是在MAD-RAPPEL中使用的，从Ancriminizer获得的隐藏区域中保护接收者的确切位置，因此不会受到某些Query Analyser推理攻击。3.4. 形成隐身区通过 使用缓存 贡献率和 具有数据 新鲜度 的预期下 一个位置 ，Ancriminator选择遵循k-匿名要求的k个单元。然后，它从具有最大查询可能性的k个小区中选择隐藏区域。该设备具有M× M网格的矩形服务区域，其中每个单元具有特定的标识符（ci，rj）和相同的维度。该设备实现了共享软件缓存方案依赖于签名补充树结构的合作缓存，类似于（Lubbe et al.，2011年，我们在战略上。在此模型中，假定Ancestizer和客户端都是隐式可信的，在图3（a）中，并公开了它们实际位置。当网络中有一些假用户时，如图3（b）所示，可以将假位置与假查询一起插入。因此，位置暴露的概率远高于1/k。LBS的实现假设小区内的点密度指示该小区内的查询可以被客户端查询的概率。我们认为提交查询的人可以移动到单元格中的任何位置。在伪装区域中，我们选择具有与移动消费者小区类似的查询概率的其他小区。在这种情况下，攻击者无法从参与小区的社区中推断出隐身区域中的相关历史信息。在LBS实现中，让具有查询POI的小区标识符集合表示为Iq，并且与用户的高速缓存匹配的小区标识符来自设备的相邻高速缓存的匹配单元标识符由In表示。发起查询的人的位置由Du表示。最佳水平阈值（h）取决于图三.基于位置的服务支持4-Anciliity。我A.K. 古普塔，美国Shanker/沙特国王大学学报3461≤--T2XuX≥2见图4。 隐身区设计流程图。服务标准和隐私之间的权衡在（0h 1）之间。在该阈值的高值上，消费者匿名性降低并且满足更多智能手机应用程序所要求的POI。最小小区标识符计数（k）等于<$（Iq）/h<$（Ic）<$（In），其中，<$（）是小区标识符计数函数。建议的MAD-RAPPEL中的PSKA功能遵守图1中所示流程图给出的步骤。 四、掩蔽区域制定技术选择具有最高缓存贡献率的单元。假设P1是第i个单元中t是任何单元中的数据缓存周期，并且缓存数据的寿命由T表示，则单元的新鲜度（F）可以由下面给出的等式描述。F1-st其中T不缓存贡献率k-i3¼Pi1/1M×M其中，Pi11/1缓存中的任何数据都将在其生命周期结束后过期程序需要在数据过期后更新分配的缓存数据，以提高设备缓存影响率的效率假设，图五、矩形区域内缓存数据项有效作用域分布3462A.K. 古普塔，美国Shanker/沙特国王大学学报uu-uu乌鲁河D我最小值r;最小值sSILi我Pi：ApuvspuvdipuvX表1模拟参数初始值。参数描述初始值参数描述初始值尺寸_矩形服务区域大小10000米 * 10000米Zipf访问偏度变量，Zipf访问分布0.5Dr轨迹预处理距离阈值2地铁Tr轨迹预处理时间阈值2分钟CWPOI集群合并宽度五港铁N国家数量，即Number在流动10马尔可夫链minCs最短群集停留时间计数4EPSEpplane是局部半径用于扩展群集20地铁C_尺寸_比率缓存与数据库大小百分之十区间预测预测区域计算时间240.0秒间隔最小速度最低客户端速度10名议员最大速度最大客户端速度20名议员Smin数据项最小大小64字节SMax最大大小的数据项1024字节带宽下降下行带宽144 kbps带宽增加上行信道4字节信道N轨迹数据集计数3465M细胞计数1000-10,000兴趣点_兴趣点兴趣点计数10,000Theta（h）阈值0.1-1.0查询间隔平均过渡时间60.0秒Α不断考虑0.70下一查询评估最新概率访问R查询范围0.5公里配置最小值最低置信百分之五十超级矿山最小值阈值支持百分之三十联系我们对数据项的单个值进行不同位置220O异常值变化K匿名度10至50通过下面的等式，所选择的k-所提出的成本函数与PPRRP（Kumar等人， 2008年）。如果数据元素1k-NXumi30ust21在实地重新审查的可能性更大。的数据项的成本取决于大小，并与平均数据新鲜度1/4k -数字1/3k1/1@1-T2A访问概率，有效范围，以及反向比例-根据对象大小和有效范围参考点的距离具有对缓存的最大贡献率的单元（Cd）具有最低的数据新鲜度是由Ancestrizer选择的，用于对公式进行掩蔽。用户的当前位置。对于客户端缓存，客户端当前位置被用于成本计算，而对于Ancestrizer缓存，在具有最高配置的小区中移动的每个移动用户的位置被用于成本计算。第三次世界大战C ¼最大值1/1Pk-Numi3qt2P×k-i3考虑到这一点在后一种情况下，重置成本是为每个移动用户计算的隐形成本之和地区替换策略的目的是识别具有最小可以从客户端和Anchorizer中删除的错误成本81：Probi：Avsdi：kiifvsdspredReg1Ki缓存 替换机制可以正式定义为如下：D0vsdi：Si：liifvsdiRpred Reg日0X1Xdi2Sdi2SProbi表示匿名中访问i个数据项的可能性objSize> dnewi;j 定义为Avsdi。无效，无效，和预取策略使用了基于马尔可夫模型的算法，用于预测客户端下一个位置的算法，如图1中所定义的见图6。 用户和解析器2费用¼我ymizer的缓存。 概率i初始值为0。 有效范围区域发现S;使得Min@成本为1000美元，附加的1吨A.K. 古普塔，美国Shanker/沙特国王大学学报3463见图7。 服务器开销比较。见图8。 不同细胞数对缺氧程度的影响（M）。图9.第九条。POI和隐藏区域大小对查询处理时间的影响3464A.K. 古普塔，美国Shanker/沙特国王大学学报..×..我们的分部。通过获取预测的下一个位置的知识，它可以找到预测的客户端下一个位置到数据项有效范围参考点之间的距离该策略根据用户移动日志的相似该策略涉及精确的下一个位置预测被用于数据项成本计算，这与以前的策略相比，极大地提高了缓存命中率。在更换政策中，Dvsdi是有效的范围到用户当前位置的距离。对于未来查询数据对象（di），客户端的可能下一位置由Lam =（Lxam，Lyam）表示，并且第i个数据项有效范围的参考点由Li =（Lxi，Lyi）表示。DvsdiLam-Li ¼qLxam-Lxi2Lyam-Lyi2第i个数据项有效范围的参考点与预测区域中心之间的距离用D0 vsvdi表示。D0vsdiLp-LiqLxp-Lxi2-Lyi2Vm表示客户端m的速度 li表示第i个数据项的平均更新速率。ki表示第i个数据项的平均查询速率客户端m在查询发出时的当前位置由Lm =（Lxm，Lym）给出。查询发出时 第i个数据项有效范围的引用点（Drakatos例如， 2009）由L i=（L Xi，L yi）给出。所提出的策略修改了在计算中考虑时间和空间项的成本函数查询速率与更新速率之比的比例表示为ki/li。4. 绩效评估该数据集包括182人，18，670条轨迹，累积距离约为1000米。1200，000 km的累积周期为48，000+小时。在轨迹中，点对于实验的情况，我们随机挑选了3465个独立的序列。我们保留了移动轨迹，轨迹中点的长度在10到15个位置之间。在我们的模拟中，具有指定细节的PC花费至少16分钟并且最多154分钟来使用具有不同数量的状态的n阶移动性马尔可夫模型来用户的查询数据项的日志可以用于各种位置特定资源的实验，例如医疗24x7，消防站，警察，血库，电影，ATM，餐馆，医院等。在日志或更正式的事务文件中，每个记录都被假定为查询。事务可以查询多个缓存对象对于该实验，已经考虑了足够数量的客户端收集到的事务文件必须经过预处理，然后才能用于实验模拟。数据的预处理方法删除无效或冗余请求，添加相关变量，并标记缓存的文件属性。在我们的工作中，一个Zipf样分布（与参数Z