英语原文共 7 页，剩余内容已隐藏，支付完成后下载完整资料

分散同步技术实现的可扩展、可靠的定位服务

摘要：对于一个定位服务计算系统来说，一个关键问题就是为可扩展、可靠的定位服务预留的空间。这篇论文展示了名为Reliable GeoGrid的分散服务计算框架，该框架基于地理位置感知涂层网络，它能够确保可扩展可靠的移动端信息传递服务的正常运作。Reliable GeoGrid具有两种特征：1. 我们开发了一种分布式复制框架，目标是在分散渗透式的计算环境下满足可扩展可靠的定位需求。我们的复制操作基于异构节点网络，它实现了基于捷径的优化策略，它提高了系统在节点、网络崩溃情况下的稳定性。2. 我们实现了一种动态平衡加载技术，该技术利用服务中复制过程的容量来衡量非预期的节点和网络崩溃。我们把节点异常、网络波动和每个节点的改变都考虑在内。根据我们实验性评估，在热点区域高速移动的情况下和在单一节点或者网络崩溃的情况下，Reliable GeoGrid框架可以改变服务的工作节点。

第一章 简介

随着移动设备及其组件价格的不断下降，在分散渗透式的计算环境下满足可扩展可靠的定位需求的分布式复制框架的需求越来越强。和集中式的客户端-服务器框架不同，分散式管理和定位服务预留技术在近年来得到了很多关注，它在所属者的低消耗、固有的可扩展性和凝聚能力是获得各方面关注的原因。

大多数在分散式计算服务的调查研究都关注非结构性的涂层网络例如Skype和BitTorren， 和结构性的涂层网络。部署的覆盖网络上进行的测量表明，节点的特性，如可用性，容量和连通性，呈现高度偏斜分布，这种内在的动态显著的变化，甚至失效，以覆盖系统所提供的服务。例如，一个节点突然崩溃可能导致系统延迟输出或者返回不一致的结果。进一步来说，持续增加的移动设备使用人数和移动定位服务的多样性表明用户的兴趣和在路中的行为模式一直在改变，从而产生移动热点服务需求和动态计算工作。因此对于定位服务来说，一个重要的技术挑战就是开发一个具有可扩展性和可靠性的中层架构。它构建在常规的动态涂层网络之上，适用于精确的定位服务和信息传递。可扩展性意味着定位服务网络需要提供平衡有效的加载策略以适应不断增长的用户人群和热点地区的服务需求。可靠性意味着在节点或者网络出现意外的情况下，定位服务网络依然可靠。

在这篇论文中我们展示了名为Reliable GeoGrid – 一个分散式地理定位涂层服务框架，它致力于实现可扩展的可靠的定位服务。这篇论文的贡献主要有以下两点：1. 我们设计了分散式复制网络，它保证了在工作节点不断变化的情况下，依旧提供可靠的定位服务。我们的复制框架可以保证单一结点崩溃和多节点崩溃情况下系统的可靠性，它能保证用户持续获得定位服务，消除系统在任务运行过程产生的中断。2. 我们展示了一种基于复制的平衡加载技术，它利用一个参数化的效用函数，将服务运行过程中相关因素考虑在内，去控制和衡量节点计算时的变动。我们的试验评估表明Reliable GeoGrid框架在高速移动的热点地区是高度可扩展的，并且在单一结点崩溃和多节点崩溃的情况下是高度可靠的。

第二章 系统概述

Reliable GeoGrid包括一个计算节点网络。节点包括个人电脑或者具有极大容量的服务器。这个系统由4个核心组件组成：顶层管理模块、路由模块、复制模块、平衡加载模块。

顶层管理模块：

所有的节点由二维地理坐标空间中的点表示，与物理世界中的坐标系统一一对应。在任何时间点，网络中的N个节点将动态地将整个GeoGrid坐标空间分解成N个互不相交的矩形，每个节点通过整个坐标下的地理信息管理自己的矩形区域，同时处理映射到该区域的信息请求。图1展示了一个二维的地理坐标空间分解成17个GeoGrid节点的效果（简而言之，我们用相同的数字表示节点以及它管理的区域。）

GeoGrid逐渐架构完成。它由一个管理整个区域的GeoGrid节点开始。每当节点p加入这个系统，它首先通过类似于GPS服务的手段获取地理坐标然后通过引导服务器得到一系列的GeoGrid现存节点。通过从这个坐标列表中随机选择一个入口节点，节点p开始加入请求。这个加入请求转送到节点q，q的区域中包括新的节点。节点q管理的区域被一分为二，一半由q管理另一半由p管理。除了邻接表，Reliable GeoGrid节点还保存一个复制表用于恢复容量，一个路由表以便更快在巨大的网络中搜寻路径。用户无论使用有线网络或者无线网络都可以连接到GeoGrid节点从而得到定位服务。

在最初GeoGrid的原型设计中，每个节点都配备了足够的容量用于上传定位请求，搜寻路径，处理定位请求，最终将结果反馈给用户。例如，一位出租车司机的请求如下：在接下来的一个小时内，每隔10分钟向我发送5英里内的交通状况。我们假设定位信息源如电子眼，加油站，餐馆等等在GeoGrid服务网络之外。

路由协议模块：

GeoGrid网络的路由是通过二维坐标中起点节点和终点节点所连接的直线确定的。一个路由请求开始于起始节点到最邻近节点，设q是最接近终点(x,y)的节点。如果(x,y)在所选择的路由节点q的控制区域之内，那么q就是这个请求的控制节点，否则，q重复执行以下步骤直到请求到达覆盖了(x,y)的节点。例如，在图1中，一个路由节点由节点7初始化最终由节点3覆盖，其中通过了节点12,2,4,6最终到达3 。

Reliable GeoGrid的另外两个组件是复制模块和平衡加载模块，它们利用复制保证了定位服务的可扩展性和可靠性。由于篇幅的限制，文章剩余的部分将关注这两个模块。

每个定位请求只处理一次并且一旦它安装到系统中，它就是只读的并且失效之前一直被保存。接下来的分布式复制系统多选复制主机复制所有的路径请求并且所有的复制主机都有相同的只读的服务请求，即使在给定时段只有一个处理节点处理请求。在Reliable GeoGrid中，每个定位请求有一个起始节点，一个归属节点和一个处理节点。我们把接受移动用户定位请求的节点称为这个服务的起始节点。每个定位服务将会定位到终点节点，这个节点所在的区域包括它的地理坐标或者离散区域的中心坐标。这个终点节点被称作这个请求的所属节点，这个请求还会找到一个复制节点去处理这个请求，作为处理节点。当一个处理节点意外崩溃，一个新的复制节点就会被选择成为处理节点。

第三章 复制和复制管理

GeoGrid复制机制遵循着以下两条原则。首先，我们想通过创建和维持一个常数个所有服务的副本来控制复制管理时的消耗。第二，这些复制节点应该从近点和远点中同时选取，只有这样我才能利用Reliable GeoGrid固有的地理接近性去减少恢复过程中的消耗同时增加系统对网络崩溃的抵抗能力。

A 崩溃模式和风险分析：

一个崩溃被定义为在没有明确告知的情况下和Reliable GeoGrid服务网络突然断开。在实际应用中，这种突发状况可能由以下几点造成：计算机节点崩溃，网络连接问题，不合适的软件终端。Reliable GeoGrid网络支持崩溃停止假设并且通过心跳信息可以侦测到崩溃的节点。崩溃停止假设意味着节点不再工作并且无论何时崩溃发生，内存中的内容都会消失，但是节点不会由于崩溃产生对系统的错误动作。

有两种在涂层网络中最容易产生的崩溃：单一结点崩溃和多节点崩溃。单一节点崩溃意味着在崩溃停止假设的前提下一个节点独立崩溃。如果在节点一级没有可靠性措施的情况下，单一结点崩溃可能产生服务终端或者服务状态信息的永久丢失。多节点崩溃意味着在IP网络分片之下，涂层网络也分片，在一个分片组件中的节点和其他节点分离，所有不同分片网络中的组件无法交互信息从而导致延时和致命的错误。我们推行的是更高一层的错误防范机制，它能够容许多节点崩溃，这对于一个长时间运行的大规模系统来说至关重要。

B 基准复制模式

为了理解影响复制模块效率的内在因素，我们分析了两种基本的复制模式：邻接复制模式和随机复制模式，每种模式都在一定程度上对节点崩溃有一定的抵抗能力，但是都在这个方面存在缺点，在开销上也有不同。

随机复制方法

随机复制在分布式系统中被广泛使用。给定一个归属节点和复制特征rf，随机复制模式会使用哈希函数H随机选择rf个节点作为其复制主机。图2展示了节点14随机选择6个节点作为其复制主机。由于随机复制经常离主节点很远，随机复制对单一节点崩溃和多节点崩溃都具有一定的天然抵抗能力。然而这个方法会产生大量的复制保存开销。首先就网络和地理接近性来说，随机复制主机会离归属节点很远。因此这个方法会在通信和同步过程中产生大量开销。其次，如果复制主机崩溃，在寻找新的归属节点的过程中会产生巨大的开销。

临近复制方法

这种方式将副本置于归属节点的最邻近节点和相对临近的节点上，因为会出现邻接节点数目不足以完成复制任务的情况。复制特征rf定义为作为临近复制主机的数目，它代表服务需要的冗余程度。如果rf相对较小，那么相对的邻接节点的数目就可以满足复制需求。在rf相对较大的情况下，邻接节点的数目就无法满足需求，我们从相对临近的节点中选择复制主机。正如图3所示，节点14的复制主机由两部分组成：它的邻接节点8,13,16,17和节点4和15 。通过在归属节点周围选择复制主机，这个方法会减少同步和搜索方面的开销。但是，在多节点崩溃的情况下这种方式的抵御能力相对较弱。举个例子来说，当网络分片产生时，如果一个管理节点和它的邻接复制主机在同一个网段，那么在这个网段之外的节点就无法通过管理节点和复制节点到达此处从而使服务中断。

C 邻接捷径复制方式

设计Reliable GeoGrid的复制方式是为了提供长期的定位服务并且增强系统的分片承受能力。通过这些对象的指导，我们开发了一种混合的复制模式，即把邻接复制和捷径复制结合起来。前者强调的是复制应该可以尽快回复并且在节点动态变化以及高吞吐量的情况下，复制开销尽量小。后者则充分利用捷径的节点到达距离当前节点较远的GeoGrid区域，这种方式可以增强系统对于网络崩溃的抵御能力，接下来我们会描述我们的复制算法，它选择邻接节点和捷径节点作为副本囤积的目的地。最后将展示Reliable GeoGrid复制方式是如何在节点崩溃时动态维持rf个副本。

捷径简介

和真实世界中的捷径一样，路由捷径减少了空间消耗，通过保存更多的路由信息例如到其他更大区域的捷径，时间冗余会减少，这些路由入口就可以当做接下来路由需求的捷径。为了构建捷径和GeoGrid中每个节点管理的矩形区域，整个地理空间被虚拟分成一系列更大的区域，从而每个区域是以前区域的一般大小，互不重叠，称为捷径区域。因此每个节点不仅存储了它的邻接节点也存储了更多的捷径节点。

节点p的捷径由列表Lplt;s1,s2,hellip;,smgt;存储，表示为ShortcutList(p)。m是节点p捷径列表中捷径节点的数目。每个捷径si代表地理空间中占1/2^i大小的区域。p的捷径区域互补重叠。

在GeoGrid系统中，节点的捷径列表的长度可能不同。列表长度Lp的确切长度由p管理的区域R的相对大小决定。当区域R的大小为整个区域大小的1/2^m时，捷径列表Lp的长度就为m。这就使p的捷径列表的包含了整个地理区域，由等式 １/２＾ｍ　＝１导出。基于以上的分析，我们就能估算每个节点捷径列表的长度。在有Ｎ个区域的GeoGrid系统中，每个区域是整个区域大小的１／Ｎ，假设区域被平均分配，捷径列表的长度为Ｏ。图４中节点１４保存了到节点１的捷径。如果节点１４需要到节点９，它可以直接到节点１再转向节点９。这种路由方式和正常的路由方式经过８,４,６,１０相比，有效减少了开销。

捷径构建和维持

捷径的构建需要一个拓扑结构构建算法。当一个新的节点ｐ加入，然后现存区域Ｌ分解成以前的一半时，新节点ｐ的捷径列表按照以下两步构建：首先新节点继承以前区域Ｌ的归属节点的捷径列表。然后检验其中的节点，辨识出非邻接节点。新的节点ｐ将把这些节点加入自己的捷径列表，并且把他们从邻接表中删除。例如图５中，从３个节点的系统开始，节点１,２，３将他们的捷径列表初始化为空表。如图６所示，当节点４加入节点２的区域时，该区域一分为二，４继承了２的临接列表，节点１不是新节点４的邻接点，绝对邻接关系建立，如图６中的点画点所示。节点４把没有把和节点１的连接删除，而是把它加到自己的捷径列表中。接下来在图７中，当节点５加入分割４的区域，他继承了节点４到节点１的连接。节点６同时继承了节点５的捷径列表并且整合了到节点２的绝对连接。在图８中，当节点９加入分割节点３的区域，节点６最终获取指向Ｌ１，Ｌ２，Ｌ３，Ｌ４的指针。邻接表的保存和捷径列表的保存方式大致相同。心跳信号用于检测节点崩溃。

复制特征ｒｆ

给定一个地点询问要求ＬＱ，节点ｐ是ＬＱ的归属节点或者管理节点。ＬＱ将会被以下集合中的节点保存。

这个集合被称作节点ｐ的复制列表，记作ReplicationList(p)。当地点询问ｌｑ被其归属节点收到，它就被复制到ｐ的复制列表中。复制列表的长度被定义为复制特征ｒｆ，在系统初始化时就产生并且根据崩溃率，系统吞吐量和时延动态调整。把ｒｆ设置太高会使得复制开销十分巨大。这个代价会由于移动终端在热点地区的快速移动变得更大。另一个重要的设计考虑是保持每个节点ｐ邻接复制和捷径复制的比率相对稳定。由于捷径节点通常离节点ｐ相对较远，设置有效的复制主机数目十分重要。在ｒｆ较大的情况下，邻接表和捷径列表的数目总和不能满足复制需求。我们将邻接表扩展成相对邻接表，如图４所示，ｒｆ＝６时最少邻接复制为５０％，节点１４选择３个邻接点和３个捷径点完成复制列表。

当节点在周期心跳信息的辅助下加入或者离开网络时，动态复制管理模块为每个节点保存ｒｆ份副本。由于篇幅有限，我们推荐读者去阅读参考文献５获取更多的细节。

第四章　平衡加载复制

对于精确定位可扩展服务来说，一个重要的挑战就是在处理不断变化热点区域时的系统级容量问题。在Reliable GeoGrid系统中，

剩余内容已隐藏，支付完成后下载完整资料

资料编号：[153415]，资料为PDF文档或Word文档，PDF文档可免费转换为Word