英语原文共 19 页
探索复杂网络容易失败的因素
Arles Rodracute;ıguez1,2, Jonatan Gacute;omez1, Ada Diaconescu3
- ALIFE Research Group, Universidad Nacional de Colombia
- Fundaciacute;on Universitaria Konrad Lorenz
- Telecom ParisTech, LTCI CNRS Paris, France
arlese.rodriguezp@konradlorenz.edu.co, jgomezpe@unal.edu.co,
ada.diaconescu@telecom-paristech.fr
摘要：在传感器网络和物联网（IOT）以及服务器场、集群和云中的数据复制中，分布式数据收集和同步至关重要。一般来说，这样的系统由一组相互连接的组件组成，这些组件相互合作和协调以完成一项集体任务，同时在本地执行并容易出现故障。因此，一个重要的挑战是如何定义高效和健壮的大规模、分布式和易故障平台中的数据收集和同步算法。本文对其在具有不同的拓扑结构（晶格、小世界、社区和scalefree）和不同的代理故障率复杂网络中的性能和不同多智能体算法的健壮性进行了研究。代理从随机位置开始，并探索网络以收集托管在每个节点中的本地数据。他们的探测算法决定了他们覆盖未探测区域的速度 收集新数据的节点，以及它们与其他代理的会面频率，以交换补充数据并加快进程。 两个探索研究了一种随机算法和一种使用stigmergy模型的算法 （我们提议的）。实验结果显示了网络拓扑结构代理故障率影响数据收集和同步，以及基于stigmergy的方法如何提高性能和成功大多数情况下的费率。我们相信这些结果提供了对各种分散算法在不同网络中的适用性日益成为现代信息核心的环境以及通信技术（ICT）系统。
1介绍
传感器网络、服务器场和云由许多通过（复杂）网络互连的组件（如服务器、进程、机器人）组成。他们合作并协调他们的行动，以实现一些总体目标，可能共享共同的资源，并且在最终用户看来是一个单一的系统[1]。这里的一个重要研究领域涉及通过这种复杂网络互连的快速分布式进程如何实现集体目标（例如数据收集、同步或处理）；以及复杂网络的特定拓扑特性如何影响这种性能[2-5]。这些方面是安全通信[4]、数据库中的日志记录和机器复制[6]以及传感器网络中的信息处理和协商一致[7]的关键。这里的一个特殊挑战是从网络组件中收集数据，既作为独立目标，例如在传感器网络中，也作为数据同步的基本任务。本文主要研究复杂网络中的分散数据采集。必须在这里解决重要的挑战，因为网络组件只能在本地工作，可能会意外失败。
以前的工作[8,9]研究了基于易失效代理的数据收集技术。分析方法包括随机行走、Lrsquo;evy行走和stigmergy。为了收集本地信息并与其他代理共享（他们可以满足），代理们基于选定的算法探索了一个目标空间。[9]介绍从分布式源收集信息的代理，这些代理可能会失败和/或提供不可靠的信息，将集体信息定义为代理单独收集的信息集合。[10]展示了如何通过有利于探索新路径和与其他代理交换新信息的算法加速数据收集。它还显示了有利于探索和更快地收集数据的机制如何比那些专注于增加代理间通信的机制更能抵抗失败。最后，它展示了stigmergy和信息素蒸发如何帮助探索新的路径，同时也允许重新探索以前的路径，以便从故障相关的数据丢失中恢复。
在本文中，我们研究了复杂网络中的数据收集问题（而不是以前研究过的均匀空间中的数据收集问题）。这是一个重要的区别，因为所探索的网络拓扑结构在探索、收集和交换信息时对代理的性能有重大影响[11]。和以前一样，代理可能会以不同的速度失败；但是我们假设准确的数据收集——即当代理可用时，他们的信息是可靠的（与[9]相反，并且是对的）。我们研究了两种运动算法——随机和stigmergy。这与[8]中定义的相似；因为L#39;evy步行不适用于非定向空间，如网络。目标是分析代理性能（即收集所有网络数据的速度）和鲁棒性（即在代理失败时如何完成任务）如何依赖于所采用的探测技术、网络拓扑结构和失败率。
本文的其余部分组织如下。第2节介绍了复杂网络中的数据收集问题、所研究的网络拓扑结构以及代理程序的设计。第3节详细介绍了分析的运动算法，第4节介绍了实验设置并讨论了获得的结果。结论和未来的工作见第5节。
2复杂网络中的数据采集问题
所研究的问题可以总结如下。代理必须探索复杂网络（模拟），以便收集网络顶点中存在的所需数据。代理在基于预定义算法的互联顶点之间移动（第3节），从每个访问的顶点收集数据，并与在同一顶点上遇到的任何代理交换数据。此外，代理可以使用概率pf随着时间的推移而失败。目的是让至少一个代理从整个网络收集所有数据。感兴趣的参数是任务完成的速度和存在代理故障时的成功率，这取决于网络拓扑、代理运动算法和故障概率。
代理的实现基于[10]。每个代理都配备了一组感知信息素P=信息素、数据、当前节点、邻居、消息，其中信息素是RN中的向量，值在[0,1]中，表示代理附近的信息素数量（即与当前位置相邻的顶点）[12]；数据是代理当前顶点中要收集的信息；邻居是代理当前顶点中要收集的信息。返回同一顶点中代理的ID；msg存储来自其他代理的消息；loc返回代理的位置（顶点名称）。每个代理还可以执行一组操作actions=move（vertex）、collect、send（msg）、recv where move（vertex）将代理移动到顶点位置；从代理的当前位置收集感测数据并将其存储在本地内存中；send和recv启用与其他代理的信息交换。
模拟时间是通过离散轮来定义的。在每一轮中，每个代理：感知其本地环境（例如本地数据、共存代理和相邻顶点）；决定操作（例如收集和交换数据，选择要移动到的相邻顶点）；并执行实际操作[13,14]。当至少一个代理完成探索（即收集所有数据）或所有代理失败时，模拟结束。环境是需要探索的复杂网络。
简言之，复杂网络由大量互联节点组成，这些节点具有非平凡的拓扑性质，即既不是纯规则的，也不是完全随机的；不像格和随机网络。典型特征包括节点之间的相对小距离、高聚类或幂律度分布（即重尾分布）[2]。对复杂网络的更正式的定义是很难提供的；研究人员将重点放在特定的拓扑度量和产生具有独特特性拓扑的节点互连规则的种类上[11]。
本文将一个复杂网络定义为一个顶点集为V，边集为E:G=（V，E）的图G。概率规则定义了在构造图时顶点相互连接的方式[2,11]。因此，使用不同的互连规则可以生成具有不同拓扑结构的复杂网络。在本文中，我们评估了文献中确定的主要网络拓扑类型，即小世界、无尺度和社区网络（讨论如下）。此外，我们还使用更规则的拓扑进行比较，例如森林中心和辐条、晶格、线和圆。
2.1小世界网络
一个小世界网络是由一个常规网络（在节点互连方面）开始，然后以随机方式重新布线其中的一些连接而生成的[15]。这种类型的网络具有任何网络节点之间相对较短的路径，即使在非常大的网络中也是如此。在本文中，我们使用具有不同参数的Watts-Strogaz模型[3,16]来生成小世界网络。我们从一个规则的环格网络开始，每个顶点有n个顶点和k个边，然后用概率beta;重新连接每个边。beta;参数决定最终网络的规则性：beta;=0生成一个规则网络，beta;=1是一个随机网络，在值之间是一个小世界网络[15](图1）。
图1小世界网络：n=100，k=4，a）beta;=0.3，b）beta;=0.5，c）beta;=0.9
2.2无标度网络
无标度网络的特点是度分布遵循一个称为幂律的数学函数[17]。度分布是整个网络上节点度的概率分布[18]；其中节点度是其链接数。幂律分布意味着节点度数可能因规模大小而不同，因此与平均度数相比，少数节点（称为集线器）具有不成比例的链接数。真正无标度网络的显著例子包括WWW、电子邮件或蛋白质交互网络。它们对意外故障具有很高的抵抗力，但更容易受到目标节点攻击[19]。
无标度网络可以从sn节点和eta;连接开始得到。在每个步骤中，都会添加一个新节点，并通过eta;链接连接到现有节点，这是基于优先连接（即，更可能连接到更高级别的节点）[20]。即，连接到现有节点的概率定义为，其中ki是节点i的阶数[16,21,22]。该过程重复步骤次[11]。图2描述了不同的配置，显示了连接数量如何随着eta的增加而增加。
2.3社区网络
社区网络的特点是，节点可以分配给内部高度互联的不同组或集群，并且属于不同组的节点之间的连接相对较少[23]。在本文中，使用n个集群参数生成社区网络来定义
图2无标度网络：Sn＝4，＝97步，eta;= 1），b），c）eta;=eta;= 2，4
网络中的组数，并在不同组的节点之间添加单个连接。每个组都被生成为一个小世界网络（有自己的k、beta;和n=m/n集群，其中m是网络中的节点数）。图3显示了一个社区网络，其中有四个组通过一个中心节点（随机选择）或一个由从不同组（也随机选择）中选择的节点对形成的圆连接。
图3 a）社区中心，b）社区圈网络：n个集群=4，beta;=0.5，度=4，m=100
2.4森林轮毂和辐条
森林中心轮辐网络基于中心轮辐（或星型）配置，所有节点围绕中心节点（中心）连接（轮辐）；然后通过连接成对的此类星型结构形成森林。这种类型的网络确保了高可用性和可靠的计算服务，因为它允许扩展单个云实例[24]。在本文中，我们生成了4个由25个节点组成的中心轮辐集群，如图4所示。
图4 森林中心和辐条
2.5线、圆和格
实验设计包括格点、线和圆拓扑。使用这些拓扑进行实验的目的是测试所选算法的开发和探索特性，这些算法具有更大的直径（线），以及长路径长度（线和圆）和规则连接（晶格）。图5显示了应用于实验的配置，每个实验都有100个节点。
图5 线、圆、格
3代理运动算法和故障
在选择了代表不同拓扑结构的不同类型的复杂网络之后，我们的目标是建立并分析确定的运动策略如何影响未访问顶点的探索、遇到其他代理以及在完成任务时给出的鲁棒性，即使代理容易失败；因为所有这些都很重要。用于数据收集。
每个代理实现一个算法，该算法确定如何从环境中感知数据，以及如何选择动作（如运动）和与其他代理通信。代理程序伪代码列在算法1中。代理故障也在本程序中定义，并以故障概率pf产生，例如，pf=0.1意味着代理平均每10发中有1发失效。
基于感知，代理根据两个可能的运动过程选择要移动的下一个顶点：随机的（探索性的）；以及基于信息素的（改进新路径和代理遭遇的利用的）（反过来增强集体探索）。
|
算法1代理程序 |
|
|
1: Percept p 2: Action action 3: round larr; 0 4: while Agent.status 6= Fail do 5: lambda; larr; U[0,1] |
. uniform random number |
|
6: if lambda; lt; pf then 7: Agent.status larr; Fail 8: break 9: end if 10: p larr; environment.sense() 11: Agent.move(motionAlgorithm(p)) 12: if Agent.hasNeighbors(p.location) then 13: end if 14: round larr; round 1 15: end while |
Agent.exchange(p.neighbors) |
当执行随机漫游时，代理将从当前顶点附近的一组顶点中随机选择其移动方向。利用均匀分布的伪随机发生器生成随机序列。
当执行基于信息素的移
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
