物联网应用的分布式哈希自动配置和负载平衡方法

沙特国王大学学报Handfan：一种面向物联网应用的Brahim Djellabia，Mourad Amada，b，Abderrahmene Baadachea，ca阿尔及利亚Bejaia大学精确科学学院计算机科学系LaMOS研究单位b阿尔及利亚Bouira大学计算机科学系c阿尔及利亚阿尔及尔第一大学数学和计算机科学系阿提奇莱因福奥文章历史记录：2021年5月29日收到2022年1月19日修订2022年2月11日接受2022年3月7日在线发布保留字：点对点系统分布式哈希表物联网服务发现哈希函数负载平衡自动配置A B S T R A C T物联网（IoT）可以被定义为一个广泛的互联设备网络，使任何物理对象成为全球网络的一部分。一切事物都互连到互联网的机会导致许多其他挑战，诸如许多设备、指数生成的数据以及这些设备的有限资源容量（在存储容量、处理、能量和可访问性方面）。去中心化系统，尤其是点对点（P2P）系统可以满足物联网应用的要求。基于对等DHT的方法能够在对数成本内实现有效的搜索。然而，需要解决两个问题，以有效地适应资源受限的物联网系统。第一个技术差距是基于DHT的方法不处理网络可扩展性和资源分配，因此它们假设节点和密钥必须在同一空间中，因此，它们完全由散列函数的输出确定。第二个差距是，这种方法中的服务发现独立于节点为了应对这些限制，我们的方法通过以下方式从根本上解决了现有基于DHT的方法中以前的技术差距：首先，针对第一个问题，提出了一种基于几何角度的密钥和标识符映射机制，并将该机制应用于节点的自动配置。其次，它引入了一个定制的路由机制，在节点的处理能力的因素。我们考虑的跳数，路由表的大小，配置开销和负载分布作为性能指标。所提出的协议版权所有©2022作者。由爱思唯尔公司出版代表沙特国王大学这是一个开放的访问CC BY-NC-ND许可证下的文章（http://creativecommons.org/licenses/by-nc-nd/4.0/）。1. 介绍根据（Evans，2020）中的专家统计数据，思科IBSG（互联网业务解决方案集团）预测，到2023年底，约有300亿台设备连接到互联网。 这些设备采取卫星、传感器、家庭自动化设备或可穿戴对象的形式（Zhao等人，2004; Ashton，2009; Jia等人，2012年）。物联网为现有互联网带来了另一个连接维度（国际电信联盟，2015年），即，*通讯作者。沙特国王大学负责同行审查一切-通信维度（见图1）。此外，连接的普及设备能够生成大量数据，这些数据使得智能城市中的许多应用能够出现（Zanella等人，2014; Ding和Jiang，2018），医疗保健（Baker等人，2017年;Yan等人，2012），加密货币（Deshpande等人， 2018），以及最近的智能合约和供应链（Su et al.， 2018年）。这些无处不在的设备生成的大量数据可以被处理，分析，然后从实时决策中受益（Dhivya和Kumar，2018）。例如，物联网应用已广泛应用于医疗保健系统。它连接普通的医疗设备。这些设备可以连续测量患者身体参数。此外，它还可以立即从系统中的可用服务中获得我们认为，结构化的对等网络更适合于有效地支持服务发现。然而，这需要同时处理网络和受限设备限制。对等系统依赖于分布式哈希表https://doi.org/10.1016/j.jksuci.2022.02.0131319-1578/©2022作者。由爱思唯尔公司出版代表沙特国王大学这是一个在CC BY-NC-ND许可证下的开放获取文章（http://creativecommons.org/licenses/by-nc-nd/4.0/）。制作和主办：Elsevier可在ScienceDirect上获得目录列表沙特国王大学学报杂志首页：www.sciencedirect.comB. Djellabi，M.Amad和A.巴达凯沙特国王大学学报7687Fig. 1. 物联网引入的新维度（国际）电信联盟，2015年）图2。 支持服务发现的云IoT架构概述。（DHT）来执行具有高有效成本和负载平衡的搜索操作。基于DHT的方法的问题在于，路由过程成本和路由表大小是网络大小的函数。基于DHT的方法假设密钥和标识必须在相同的时间间隔内生成。而这个区间的范围完全由哈希函数的输出决定。因此，所有的路由度量将显着影响的类型哈希函数中使用的分布式哈希表。此外，在分布式哈希表覆盖的服务发现假设参与者具有平等的角色和相似的资源。但事实并非如此。物联网中的设备是异构的，并且具有不同的资源。我们的贡献提出了一个协议称为HandFan。它解决了可扩展性和灵活性的问题，提出了一种新的映射方法的基础上圆几何。该方法独立于散列方法处理两个路由度量。该映射方法还可以有效地实现设备的自动配置.负载平衡是通过在处理服务发现时考虑设备的处理能力来我们已经实现了我们提出的方法，支持物联网环境中的服务发现。我们比较了它的性能与当代的文学方法。通过分析和性能验证，得出了HandFan的优越性能，证实了HandFan在自动配置方面的本文的组织结构如下。下面的部分通过一个实际的sce- nario应用程序提供了问题陈述的概述。在第3节中，将HandFan与在对等系统中处理物联网应用的类似方法进行了比较。在第4节中，详细描述了我们的方法，随后在第5节中进行了伪代码和复杂度分析。实验、模拟和结果验证均在第6节中讨论。最后，对本文的工作进行了总结，并对今后的工作提出了展望.2. 问题陈述和应用场景服务发现是自动查找网络上的设备和服务的过程，这有助于减少配置工作。基于集中式或基于云的系统可以主要定义服务发现中涉及的三个组件（参见图2）：服务提供者、消费者和服务注册表。服务提供者向服务注册中心注册自己服务消费者从服务注册中心获得提供者的位置以及服务注册表，它是一个集中式数据库，包含所有服务提供商的所有位置。这种设计的问题是服务注册中心需要高度可用，这使得这种设计在处理可伸缩性和可用性时效率低下。作为一种应用场景，在智能医疗系统中，物联网医疗设备，如动态血糖监测仪（CGM）、连接式吸入器，甚至连接式血压监测仪，都可以自动收集血压、心率或体温等健康指标;而无需患者自己进行。从整个系统收集的数据可以被分析，以了解许多疾病。因此，可以设计一个分散的医疗保健系统来提供这样的服务，其中服务提供者和医疗设备是有机的，作为系统中的节点（见图1）。 3）。P2P系统已被证明更适合于多个分布式应用，最值得注意的是文件和服务共享、分布式计算以及最近的加密货币和供应链。这些应用充分利用了P2P系统的去中心化、资源共享、对称性、自治性和自组织性等特性。然而，这些系统提供的机会面临着技术差距，to their 其architectures架构.首先，基于DHT的方法主要依赖于散列函数来生成具有固定结果长度的标识符和密钥为了解释，如果我们使用sha-1函数，Sha-1产生160位的结果长度。散列键的结果肯定会在区间[0.0.2160]内，并且它必须被分配给同一区间内的一个节点。因此，网络大小N将为图三.支持服务发现的P2P物联网架构概述。B. Djellabi，M.Amad和A.巴达凯沙特国王大学学报7688-固定在2160。因此，路由表长度将固定为log（N），即160个条目。因此，实际上，不可能增加或减少路由表大小。此外，作者在（Xu等人，2004）说明了许多分散的基于DHT的系统，例如Chord（Stoica etal.，2001）、糕点（Stoica等人，2001），和Tapestry（Rowstron和Druschel，2001），展示了路由表大小和搜索成本之间的关系，在网络大小的函数（见图1）。 4）.第二个问题是基于DHT的方法、路由和服务发现完全独立于网络和节点能力。因此，基于DHT的逻辑过度处理节点而不考虑其资源的容量，这使得其无效并且不适合于资源受限的IoT系统。如前所述，HandFan选择通过以下方式来应对上述缺点：（1）由于性能测量紧密依赖于散列结果大小，因此通过增强映射方法，我们可以实现网络可扩展性和自动配置，（2）基于设备容量自主明智地重新调整处理容量我们从根本上解决以下两个问题：(i) 这样一个分布式系统如何能够独立于哈希方法灵活地扩展到任何网络？(ii) 如何在高可用性的情况下自主地明智地重新调整节点的处理能力3. 背景和相关工作为了在现有的方法中定位我们的工作，我们根据它们的架构对它们进行了广泛的分类。本节讨论了我们填补类似方法中的一些技术空白和限制的动机。在本节的最后，我们将展示我们的方法与其他方法的不同之处，特别是那些解决物联网应用程序中的服务发现使任何物体成为世界范围网络的一部分的机会带来了许多严峻的挑战。大量的设备、指数级生成的数据以及这些设备的有限资源容量（在存储容量、处理、能源和可访问性方面）。已经提出了不同的体系结构来处理这样的挑战：云计算被认为是与物联网应用集成以应对连接的智能设备的局限性的有前途的方法之一。在文献中已经引入了多种方法（Atlam等人，2018; Qureshi等人，2018年;安萨里，见图4。对等路由表大小和覆盖搜索成本之间的关系的图示（Xu等人， 2004年）。2018; Chen和Yu，2019; Qabil等人，2019; Botta等人，2016;Marosi等人，2018）作为基于云计算提高车辆应用性能和效率的车辆自组织网络 （ Atlam et al. ， 2018 年 ） 。 此 外 ， 已 经 提 出 了 导 航 即 服 务（NAVaaS）系统以在协作智能交通系统中提供定位服务（Qureshi等人，2018年）。这类方法已经证明了其性能。然而，这些平台专门用于以集中方式进行管理，使得这些方法在处理可伸缩性、可用性和设备自动配置时无效。基于DHT的方法：已经引入了基于DHT方法的结构化P2P系统（Baucas和Spacos，2020; Cherbal等人，2016年）。 然而，Chord（Stoica等人，2001）是显式地使用DHT在结构化P2P覆盖层中操作分布式查找的基于DHT的系统中的主导协议。在（Chaidee和Sugihara，2020）中，作者证明了Chord对固定度数覆盖的效率。Chord被认为是对数度叠加。其中节点分散在逻辑环为了详细说明，Chord中的覆盖构建在虚拟环或圆的顶部，其中标识符和密钥映射在[0.0.2m-1]的范围内;使用具有m位输出的散列函数SHA-1，覆盖中的每个标识符通过散列节点的IP地址和密钥通过散列资源本身获得。基本上，Chord通过使用一致性哈希在覆盖层上均匀分布键和标识符来支持负载平衡。关键点映射到圆中最近的标识符。托管节点将负责其标识符和其前身之间的值的键。路由过程基于称为指针表的路由表来处理。指针表维护一个log（N）条目，每个条目指向负责圆的一部分的节点。通过在每一步将搜索间隔减半来完成搜索，因此，可以以Log（N）的成本到达节点和键。糕点（Stoica等人，2001年）是另一个基于DHT的和弦系统。在Pastry中，路由过程通过将请求键发送到与该键在数字上更接近的节点来运行。因此，查询将以log2b N跳的成本到达。类似地，路由表由（log2b N）个条目和2b 1列构成。因此，每个条目指向一个节点，其节点ID在前n位中共享当前节点的ID;例如，对于给定的请求密钥k，节点首先验证密钥是否在其叶集的范围内。如果是，则将消息直接转发到目的地节点。否则，消息被转发到与密钥共享至少多一个数字的公共前缀的节点。另一种增强的架构被称为HPM（分层对等模型）的基础上的和弦以及。它已被详细介绍了沉等。（2004年）。此外，HPM旨在提高容错和自组织方面的性能。所提出的架构是由一组分层环。每个节点都由物理上接近的节点组成;因此，无论是物理上还是逻辑上，节点都是接近的。用于物联网的基于DHT的系统：在文献中已经提出了用于物联网应用的许多基于DHT的方法（Mourad等人，2012; Yean，2014; Fersi等人，2013年; Kristena和Camarillo，2013年;Lu等人，2009年）。这些方法之一是分布式控制系统（Fersi等人，2013），所谓的“命令邮箱”是允许异步地远程控制休眠传感器和致动器的资源。该系统将设备分类为三个部分：传感器/致动器，以及主设备，用于传感器和致动器的控制实体。RELOAD（Replena和Camarillo，2013）是另一种分布式方法，其重点是通过启用传感器的睡眠模式功能并增强资源定位和发现来节省电能。传感器创建一个DHT资源，并定期轮询它，以检查是否有新命令来自其主机。当一个新的传感器加入系统时，B. Djellabi，M.Amad和A.巴达凯沙特国王大学学报7689¼ ðÞr-rmaxmin设备或接纳对等体创建具有种类ID的新资源，并将命令存储在建议的CLIENT-ID-MATCH中。一旦创建了资源，传感器就可以进入睡眠模式以节省能量。类似地，在（Shukla和Gandhi，2021）中，已经实现了用于服务发现服务的信任框架，作者已经解决了基于DHT的物联网环境中的认证问题。IoT应用的范围查询（RQIOT）（Cullen等人，2014）提出了一种在分布式P2P系统中处理范围查询的有效方法。该方法基于一致性和保序散列算法处理存储管理和范围查询，实现数据的均匀分布，有效地执行范围 Djellabi et al. （2019）提出了一种基于Chord的多层架构，以支持多属性查询。例如，在一个实施例中，然而，ML-弦覆盖中的节点应当维护和处理多个路由表：指表和BP（桥接对等体），这对于IoT受限和异构设备而言被用 于 IoT 应 用的 P2P 中 的服 务发 现 ： 另一 个相 关 工作 ， 例如（Awad等人，2008; Jukic等人， 2018）引入了不同的服务发现解决方案。例如，Jukic等人（2018）的作者在基于DHT的覆盖之上引入了动态的抽象。它通过在DAG（有向无环图）中放置流操作符（如map、reduce、join和filter）来实现数据流每个运营商都在覆盖中的特定节点中占据一席之地，然而，所提出的设计的问题是，所有不同的节点，无论是路由器，全节点还是物联网设备，都被平等对待这些节点被映射到同一空间中的这意味着受限设备必须成为路由过程的一部分，并维护路由f并定期支持其更新，这在受限设备上产生更多的工作负载类似的方法已经在（Liu等人，2021; Shukla等人， 2021年）。第一个贡献介绍了一个位置感知的基于DHT的P2P架构使用一个专用的节点称为控制器。控制器节点以（NODEHASH ID>，NODE IP>）的形式存储覆盖中所有节点的散列映射;这使得能够对网络进行本地维护这种方法的问题是维护任务明确集中在控制器中。Shukla等人基于发布/订阅通信的替代方法。（2021年）已提出。该架构选择使用雾控制器的复制来开发容错。虽然这些方法已被广泛用于许多系统，项目，我们的方法不同于以往的工作，提出了一个灵活的和可扩展的P2P模型的基础上，一个新的映射定义解耦的哈希方法DHTs。相同的映射方法用于节点自动配置。此外，通过增强路由协议，我们的方法可以处理异构环境，以应付网络下表（见表1）概括了我们的方法与其他方法的4. 用于IoT服务发现的高效覆盖在本节中，我们将讨论问题陈述中提出的基本问题。第一，应对可扩展性挑战表1表格概括了我们的方法和其他方法之间的比较由哈希方法引起的DHT覆盖。我们提出了HandFan此外，我们揭示了路由算法，在建议的架构。第二个范围是处理由于节点的异构性而引起的工作负载不平衡我们介绍了我们的路由表和路由算法进行查找操作的覆盖的改进。这部分旨在实现节点之间的负载平衡功能，而不管其资源我们假设网络包含两种不同类型的节点角色，服务器节点和物联网设备节点。N表示网络网络中的每个节点由标识符id标识，并维护大小为M的指针表。4.1. 几何和标识符空间该几何描述了节点如何跨覆盖布置，以及节点或服务如何能够以确定性的方式到达以实现搜索操作的对数尺度复杂度大多数结构化P2P系统使用特定的哈希方法，如SHA-1或SHA-2，以获得唯一标识符（Chaidee和Sugihara，2020）。标识符和密钥的结果散列具有m位的固定长度（SHA-1产生m =160位）。这意味着可以在很大程度上支持总共2m个唯一标识符（N =2m）。一致性散列主要是通过在区间[0.2m-1]。因此，为了允许具有任意标识符的任何新节点或密钥正确地参与覆盖，网络大小应该是N =2m，而不管网络的实际大小，其大部分小于N。因此，所有路由度量都与N紧密相关，例如路由表大小和搜索成本。以SHA-1为例，处理和维护具有160个条目的路由表大小将导致物联网受限设备产生更多开销，从而影响网络可扩展性。我们提出的架构（我们称之为HandFan）的设计基于（N-gone）的凸正多边形（Alexander等人，2014年）。使用多边形的原因是以高度灵活性处理不同的网络大小。我们考虑N个顶点，正多边形（P）中的每个顶点对应于一个节点或关键标识符，多边形的所有顶点通过外接圆（C）虚拟连接。一个正多边形与增加边可以近似为一个圆（图。 5）。正在应用另一个首先，HandFan使用节点和密钥标识符的散列来获得随机散列值h_id（即，希德H U id，其中U id和h id表示散列值，并且网络中任何节点的唯一标识符。然后，在预定参数N的函数中缩放所获得的结果（h_id），所述预定参数N可以取任何值作为叠加上的配置超参数通过使用将任何值m从原始范围[rmax;rmin]映射到目标范围[tmax;tmin]的以下缩放函数m#m-rmin 最大值×最小值×最小值特征基于dhtHandFan方法扩展性受限于哈希函数的大小。可独立于哈希函数进行扩展。灵活性路由指针表基于所使用的散列函数而固定。路由指针表随网络规模的变化而变化。装载分布负载在整个网络中根据节点的容量分配负载B. Djellabi，M.Amad和A.巴达凯沙特国王大学学报7690.如下所示：id。图五. 16-gone（a）和1000-gone（b）多边形的插图。我们通过将hid从原始区间[0，N]映射到目标区间[0，2p]来获得最终id。因此，计算最终idhid2pN以这种方式，所有标识符都落在范围1/20：：2p]中，其中每个id被认为是（C）中的中心角。图6（a和b）中示出了两个示例，具有16和1000网络大小，分别示出了不同的N、16-gone（a）和1000-gone人们可以通过物联网应用程序加入系统，其中每个用户都应该有一个标识符来访问服务提供的任何服务。见图6。通过P2P架构的服务和用户的图示，具有20和45之间的id的所有用户将由节点45服务ver节点。服务器节点被视为应参与路由操作的唯一节点由于连接的IoT设备的显著数量，与服务器节点的总数Ns（即，Nd Ns），许多用户将连接到服务器节点。为了详细说明，对于任何给定的idu，该值落在区间[ids;ids：succ]中，（即，ids：succ≥idu≥ids;具有iden的用户tifieridu需要连接到其后继服务器节点ids：succ，标识符空间，换句话说，范围[ids;ids：succ]中的所有标识符都被认为是节点服务器ids：succ的成员（参见表2）。如图6所示。具有以下标识符的所有用户：id #20.001，#20.004和#31.115 都 在 该 范 围 内 （ Ansari ， 2018;Kalkan 和 Rasmussen ，2020）。此外，它们是具有id#45的唯一后继节点的成员。类似地，id为#141.001和id为#145.001的用户是服务器节点id为#151。值得注意的是，通过将Nd缩放到Ns，由于在第一映射阶段使用了一致的散列函数，所有生成的id将均匀地分布在覆盖图上。因此，N可以被设置为适合于任何网络大小。此外，路由表的大小被减少到log（ Ns）而不是log（Nu），使得覆盖管理可扩展并且对于任何网络大小都更灵活自动配置：数据流控制是管理两个节点之间数据传输速率的过程，以防止快速发送方压倒慢速接收方。 为了解释，我们假设节点Sn仅能够同时接收M个数据值[L. H]（参见图7），并且许多其他IoT设备动态地连接到该节点。如何在高度动态的网络中保持相同的速率，同时减少消息通信的开销？为了解决这个问题，可以应用相同的任何新加入的节点都可以从任何其他节点获取其参数，而无需返回Sn。在节点离开的情况下，其后继节点扩展数据值范围以覆盖离开节点留下的间隙，这可以无缝地发生而因此，减少配置消息的数量将减少带宽消耗并防止网络瓶颈问题。4.2. 路由协议基于我们在上一节中描述的定义的几何结构，路由表结构和路由算法应该解决任何路由协议中的基本概念。两者都需要将消息转发到目标节点。为了实现这一目标，我们将这一部分分为两个部分：第一，第二，节点查找的路由算法。标准路由指表：每个节点维护一个指表作为覆盖层上的路由表。指针表由m + 1个条目组成，其中m等于log（Ns）。每个条目由一个表2表概括了最常用的符号。符号定义网络大小和节点数iNs和Nd服务器节点M手指工作台路由表由m个条目Uid和hid唯一标识符和Uid的散列值是Handfanidu，ids最终用户标识符和最后服务器节点标识符ids：succ后继标识符Tan（a）角aCapacity-flag跟踪其处理能力NS.容量节点服务器容量当前节点服务器容量B. Djellabi，M.Amad和A.巴达凯沙特国王大学学报7691222222. Σ24见图7。 使用数据流控件自动配置说明。图8.第八条。圆上极角的分布被认为是指向四个节点的罗盘所分配的节点的标识符ID以及到达该节点所需如前所述，我们将每个标识符id处理为圆（C）上的中心角（α）标准路由表设计如下（表3）：对于给定的标识符（a），指针表中的第一个条目指向由两条切线（a）和Δ3p的交叉形成的另一个后继角（a1），表中的Δa列指示两个后继角之间的差，最后一列指示后继角的路由信息类似地，第二入口指向由两条切线（a1）和λ3pλ等相交而形成的其最近的后继者（a2）迭代地，指表中的第i个条目指向由两条切线（ai-1）和3p的交点形成的中心角（ai）：可以将表示角度（a-p）的另一条目（m + 1）添加到路由指表。增加一个条目将通过顺时针和逆时针路由来最小化搜索成本这种冗余使得路由表可以被视为指向四个节点或极角的罗盘表（参见图8），以将搜索范围从[0.0.2 p]减小到[0.0.2p]。[0.. . p]。路由过程：HandFan被认为是定位节点、资源和服务的确定性方法。这一部分讨论了基本的路由协议。任何节点都可以执行查找（k）操作，其中k是采用节点的标识符、服务或任何其他资源的形式的键。在我们的方法中，定位任何节点的主要机制与Chord非常相似。 例如，具有标识符alpha（a）的节点可以请求定位具有标识符beta（b）的另一节点。 节点alpha（a）将所述请求消息转发到所述最近极角，桌子如果beta（b）是alpha（a）的第一个后继者，在[a，successor（a）]范围内，它返回其后继者的地址;否则，另一个查找（k）操作将由for-表3一个标准指针表条目的图示2第i次Tan（ai-1）\Tan（3p）a[i]-a[i-1] Succ[ai].. .. ......你好。. . .MTan（am-1）\Tan（3p）a[m]-a[m-1] Succ[am]将所述请求消息转发到所述耙指表中最近的直接查找过程从一个节点到另一个节点迭代重复，直到更接近或确切地请求网络上的目标。如果具有标识符beta（b）的节点已经存在于网络上，则由查找操作返回的结果可以精确地是节点beta（b）的对应地址否则，将返回beta（b）的第一个后继者的相应地址。最后，当节点beta（b）没有连接到网络时，搜索过程返回null。虽然HandFan没有将优化搜索空间作为其第一目标，但是，通过使用路由指表上定义的极角，定位任何节点、资源或服务的搜索空间将减少到N。4.3. 高效的服务管理自组织是结构化P2P系统的主要设计目标之一。因此，尽管基于DHT的P2P系统保证了均匀分布，但它仍然不足以解决负载平衡问题，特别是在异构环境中的处理能力方面，这主要是真实情况。虽然基于DHT的方法提供了均匀分布，但工作负载不会在服务器节点之间均匀分布。这使得一些节点比其他节点负载更重，并且工作负载不归因于节点自定义路由指针表：我们引入了一个增强的路由表，可以在覆盖层上进行有效的服务管理我们保持与路由过程部分中介绍的架构相同的架构。我们在基本标准路由表中引入了一个新列（Flag-capacity）（参见表3）。也就是说，对于路由表中的每个条目（第i个条目），标志容量值（或Fc[第i个条目]）是指路由表中第i个条目 该属性的值是节点的初始容量和当前容量之间的差值（N S。Capacity-CN S。能力）。因此，该值指示路由表中每个后继路由器的剩余容量的当前状态标志容量以两种不同的方式服务于路由过程。首先，它指示节点上的剩余处理能力。也就是说，可以同时连接的IoT设备的最大数量。例如，图9中的节点#14可以同时服务多达30个IoT设备连接。第二，当其值为空或负（Flag-capacity [i] =0）时，它用作标志，这将被触发条目中心角Deltaa继任者1一0成功[1]2Tan（a1）\Tan（3p）a[2] - a[1]成功[a2]B. Djellabi，M.Amad和A.巴达凯沙特国王大学学报7692见图9。举例说明如何在一个典型的情况下进行查找服务（服务器节点），这很像chord节点见图11。示出了根据节点#165容量的定制路由的场景。每当服务器节点过载时。我们稍后讨论标志容量为0的情况。因此，由于路由表大小和搜索成本都保持不变，Flag_capacity在搜索成本和开销方面不会影响路由过程图10以示例详细描述了定制路由，我们假设在对IoT设备Uid的唯一标识符进行散列和缩放之后获得具有id#58.700的节点通过遵循上述服务发现过程，具有标识符id#58.700的节点应该由其后继者Succ（#58.700）服务，该后继者Succ（#58.700）是具有id#60的节点然而，节点#60仅具有#59.001、#59.400、#60.000已连接到#60。因此，节点#60将查找过程转发到具有足够容量的第一后继节点，节点#5。我们在这里注意到，该协议支持使用独立于服务细化过程自定义路由过程：与基于DHT的方法不同，其中节点被认为是相似的，并且不考虑容量变化，这不是实际情况。在HandFan中，处理工作负载根据服务器节点的容量分布即使当节点容量随时间变化时，异质性假设也被维持。见图10。说明了当服务器节点的容量完全消耗时的动态场景，以及连接的IoT设备如何转发到负载不足的服务器节点。上图中的插图。 11解释了Handfan如何通过考虑节点的处理能力来管 理 服 务 发 现 。 黑 色 圆 圈 表 示 基 本 路 由 ， 灰 色 散 列 圆 圈 表 示HandFan定制路由。每当新节点（节点#1）加入覆盖时，它就从圆上的任何服务器节点（比如节点#165）请求特定服务。服务请求基于HandFan定制路由完成。同样的事情发生在其他设备#2、#3、#4、#5上。所有四个节点都与#165一起进入完全P2P通信。对于最后一个节点#6，#165将过载，并且其标志容量将小于零（标志容量0），因此向其接收器触发消息以将其从定制路由暂时挂起，同时其从基本路由保持可用。这当节点离开时，从#165释放一定的资源容量，然后该节点可以返回Handfan路由。通过应用这种机制。节点将完全控制其资源。即使它的资源容量随着时间的推移而变化我们声称，这个过程使覆盖，以平衡负载根据节点的处理能力之间的所有服务器节点的路由指针表中的一个微小的变化为值得一提的是，通过将整个控制权授予节点本身，系统可能遭受搭便车问题。当任何新加入的节点，声明其容量小于零。这可以通过应用许多技术来缓解这些问题来解决（Kalkan和Rasmussen，2020; Harris，2018）。5. 伪码及其复杂性分析在本节中，我们将分两部分描述我们的贡献的主要算法。首先讨论了基于标准路由表的HandFan结构，然后讨论了基于自定义路由表的业务管理。表4概括了将在这些算法中使用的大多数符号。Matlab用于描述HandFan结构和PeerSim模拟器（Li和Venugopal，2013）来执行我们的模拟。5.1. 加入节点并离开在对HandFan的任何连接操作之前，要加入的节点运行一个初始化算法;在这个算法中，最终的标识符B. Djellabi，M.Amad和A.巴达凯沙特国王大学学报7693.联系我们2NS表4列表概括了最常用的符号及其定义。符号定义n请求者，nintermidate源节点和请求节点的标识符ntarget目标节点的标识符（target）hash（value）任何哈希函数都可以用来获取id两个角Standard_Table标准路由表Node. 节 点的容量属性（一）申请人的姓名或者名称;ni候选服务器节点尼岛 predecessor：n i的节点predecessor尼岛 successor：n i的节点后继见图12。在新节点插入的示范中，节点id #25被插入在两个节点#20和#26之间。通过在预定义参数Ns上缩放唯一节点的标识符来计算fier_id函数Standard_Table_Construction返回size_minstep值，表示虚拟圆中两个指针表通过运行函数Finger_table_node获得，该函数将指针表大小和标 准 路 由 指 针 表 作 为 输 入 其 中 一 种 引 导 机 制 （ Paganelli 和Parlanti，2012）可用于执行初始连接过程。 要加入的节点发出一个请求，以找到它的直接后继者（见图1）。 12），此操作成本最多（log Ns）。一旦找到该后继者，新加入的服务器节点将作为其找到的后继者的前趋者被连接，通过搜索所有入的继任者。在这种情况下，连接的成本是（log2 Ns）。我们注意到，更新节点的继承者和继承者上的路由信息到目前为止，初始化算法只描述了执行节点加入和查找所需的协议。但是，我们的方法已经扩展到处理服务管理。加入节点将其容量插入到指表中，并通知它的前身和后继者关于此更新。 该节点将启用两种路由模式：节点的查找和服务的细化。当一个服务器节点自愿离开系统时，它需要通知它的后继者和前任者更新它们的路由信息。如果节点意外离开应定期执行该过程，以保持所有手指表正确更新。算法1：用于加入节点的初始化算法函数Standard_Table_Construction（Ns，Uid，Standard_Table，size）1Uid =获取节点2hid= hash（Uid）获取Uid3hid2p//缩放隐藏在圆圈中的NN4最小步长=2p5Init_angle = 06Delta_a=（p）7迭代= 18While（Delta_a>= Minstep）//标准手指表9切线（Init_angle\ circle）10下一个_角度（切线\-R）11Delta_a=角度（切线，下一个角度）12初始角度=下一个角度13Standard_Table[i.1] = i14Standard_Table[i.2] = Next_Angle15迭代=迭代+116endWhile17return（id）18大小=迭代-119return（Size，Standard_Table）20端函数Finger_table_node（size，Standard_Table，Alpha）22node. Capacity = Capacity，//节点i = 124While（i =大小）25Finger_table_node[i.1] = i26Finger_table_node[i.2] = Standard_Table[i.2] + Alpha27Finger_table_node[i.3] =后继节点[i]28Finger_table_node[i.4] =容量29迭代=迭代+130增量（i）31endWhile32return（Finger_table）//返回finger表33端初始化算法（算法1）描述了在连接过程之前运行所需的两个主要功能第一个函数（Standard_Table _Construction）具有一个输入参数，其为网络大小N，并且主要返回以下参数：节点标识符（id）、标准路由表（Standard_Table）和标准表的大小（Size）。第1在算法的这一阶段，后继者及其处理尚未介绍。其余的行大多是对伪代码的注释在第二个函数（Finger_table_node）中，节点将连接标准路由指针表及其大小作为输入，然后返回基于标准路由表计算的节点指针表在第二个函数中（参见算法1），新节点将其容量插入到结构中，如第28行和第24行中的循环内所示。节点通过搜索每个条目的后继来维护其指针表。B. Djellabi，M.Amad和A.巴达凯沙特国王大学学报76944≤4.ωn1/4英寸算法2：查找过程算法函数Find_Next_node（nrequester，nintermidate，ntarget）1迭代=大小2Delta = 03While not（found）（迭代>=1）4int finds = finds_table[i. 2]-（ntarget）;5如果（delta =0）6n请求者= Finger_table_node[i.3]7发现= true8Endif9迭代=迭代-110If（iteration = 0）（未找到）11n目标=空12最后;13返回n目标函数functions_process（nrequester，nintermidate，ntarget，Size）15Size_Minstep（Node_Number）16Next_node = null17while（未找到）18Next_node= Find_Next_node（nrequester，nintermidate，ntarget）19如果（Next_node>null）20If（Next_node> ntarget）21Find_Next_node（nrequester，Next_node，idt）22其他23目标=下一个节点24Target_successor =后继节点（下一个节点）25发现= true26Endif27其他28目标零29发现= true30Endif31增量（跳数）32endwhile33return（target，target_successor）34notify（target）35return（hops_number）36端5.2. 节点和键查找我们讨论如何HandFan执行节点查找操作的基础上定义的几何。任何加入和离开操作都需要节点发现。查找过程在算法2中描述我们假设两种类型的节点：n个请求者和n个目标，其中n个请求者可以是新节点或已经连接的节点，n个目标是目的节点。每当n个请求者需要到达n个目标时，它使用其路由指针表来确定n个目标在哪个季度，然后它将请求转发到离目标节点最近的节点。最近的节点可以是最终目标或任何中间节点。中间节点重复相同的处理，直到到达n个目标，并将结果返回给n个请求者。最后一步返回目的地信息，如IP地址，除非在覆盖中不存在n个目标时返回null这种路由方案主要有两个优点：第一，研究空间将减少到N。其次，路由是在两个方向上应用，顺时针和逆时针，使查找更有效，而不是只有一个方向。事实证明，HandFan最多在log（N）中解析查找操作，在算法2中，每当节点接收到路由消息msg（n请求者，n中间者，n请求者 ） 时 ， n 请 求 者 、 n 中 间 者 和 n 目 标 是 源 、 中 间 和 目 标 节 点 函 数F