自组织网络演化中的连通性分析

开篇：润墨网以专业的文秘视角，为您筛选了一篇自组织网络演化中的连通性分析范文，如需获取更多写作素材，在线客服老师一对一协助。欢迎您的阅读与分享！

摘要：自组织网络的连通性是保证网络通信能力的根本。针对无中心的自组织网络，分析自组织演化行为过程中网络的连通性，重点阐述了真实网络拥有的局域特征以及自组织网络节点的择优邻居选择策略，对于网络连通性能的影响。经过理论分析和仿真模拟发现，在类Gossip机制的自组织模式下，网络的连通性被破坏的概率很大。

关键词：

自组织网络；连通性；Gossip

中图分类号： TP393

文献标识码：A

0引言

网络的连通性是指网络各个节点之间保持连通的能力，对于各种通信网络而言，网络的连通性是极其重要的。倘若网络整体连通性被破坏，或者说网络中出现分区，那么网络中消息的传递只能限于在连通的局部进行，而不能覆盖整个网络，网络的通信能力将受到极大的影响。

分析网络的连通性，可以分为几个层次：一是底层物理网络的连通性，主要指网络节点间是否存在可用的物理连接，这是保证网络连通的基础；另一个是上层逻辑网络的连通性，主要指存在可用物理连接的前提下，网络中的协议、拓扑结构等能否保证所有网络节点间的信息可达能力。由于通信网络的层次性特征，逻辑网络的连通性也可以从分多个层次来分析。

本文考虑的是自组织网络在执行演化行为的过程中网络的连通性分析，是逻辑网络连通性分析的一种。

1网络自组织演化过程

给定一个进行自组织的网络图G={V,E}，节点集合V={v1,v2,…}，任意节点vi上的邻居节点列表是一个集合LiV，边集合E受Li的影响，可表示为E={(vi,vj)|vi,vj∈Li}。网络自组织演化，通过周期性的改变Li，从而改变E，导致网络的拓扑结构发生变化。

Li的更新，是通过网络节点间采用类Gossip［1］转发方式进行的信息交互完成的。Li中的元素，不是随意变化的。Li只能通过合并邻居节点的邻居集合Lm,Lk,Ln,…来进行增加；同时为避免Li数据过于庞大，择优选择一部分连接质量较好的邻居（通常的方式，也有通过其他标准进行选择的），将较差的淘汰掉。一增一减两个过程使Li中元素保持在一定数量，所有节点的L更新一次，完成一个周期的自组织演化过程。自组织网络中没有集中的控制节点，每个节点只能获取自己和周围邻居节点的有限信息，通过这些有限的信息决定自己的行为，其中主要是邻居节点的选择。此类自组织过程中，并没有规则去刻意保证网络的连通性。

2连通性分析

2．1理想情况

首先考虑最一般的状况：

Scenario 1：假设网络节点间随机交换信息，随机进行邻居取舍。

对于节点总数|V(G)|=N，节点最大出度max|Li|=k的图G={V,E}，分析进行一个周期演化后，分裂出一个节点数为c(k

可见，大多数情况下Ps是一个很小的数，当N=1B000，c=10，k=5时，Ps=3.365×10－101。在Scenario 1下，这种自组织行为能以较大的概率保持网络的连通性。

2.2现实情况

但是实际应用情况并不如此，Scenario 1这种随机交换、随机选择的行为对于实际的网络应用而言并没有太大意义，这种随机的逻辑连接中存在很多不合理的长连接，会导致网络性能极大的下降。一般自组织过程都有优化网络的目的，所以在选择中执行的并不是Scenario 1这种随机行为，节点通常选择与之连接质量较好的节点作为邻居。这就导致自组织过程中对于网络连通性的保持下降了。所谓连接质量较好的节点，对于不同的应用有很多评价方式，本文暂以连接距离较短（传输延迟较小）为例，进行分析。

而且，实际的网络并不是随机网络，而是拥有很强的局域特征[2]（图 1），同属某个组织或团体的网络节点，形成相对集中的一个区域网络，之间拥有较短的连接，而通过相对较长的连接和外部网络相连，如图2所示。在类Gossip机制的自组织方式下，这种局域特征，对于网络连通性的保证，又产生了很大影响。

综合以上两点，考虑这样的情况：

Scenario 2：网络分布具有局域特征，网络节点和当前的邻居随机发生信息交换，选择连接较短的节点作为新的邻居。

在Scenario 2下，网络中存在一些内部联系比较紧密的区域，那么区域中的节点倾向于选择同属一个区域的节点作为邻居。在Scenario 2下，应重新考虑网络在自组织演化行为下发生分裂的概率。

假设网络G={V,E}中存在一个节点数量为a的小区域G′={V′,E′}，G′中的节点倾向于选择G′内部的节点作为邻居。假设初始网络状况下节点的邻居在整个网络内随机分布。

初始时，G′中节点的邻居节点，落在G′中的概率为

然后，网络自初始状况开始，以自组织演化行为进行邻居选择，由于局域特征和邻居选择的策略，原来G′中节点的邻居落在G′内部的仍然在G′内部，原来落在G′外部的，有a－1N－1的概率进入G′内部。经过1步演化行为过后，G′中节点的邻居落在G′中概率变为:

以此类推，有如下公式：

求解可得，经过n步演化行为后，

此时，G′中节点的邻居不在G′中的总数为:

在特定的网络中N、a、k可取特定值，而随着网络的演化n∞，在n足够大的情况下，LG－G′0。因此随着n的增加，G′的分裂是有可能。

3仿真分析

为了更好地结合理论分析结果说明问题，我们进行了自组织行为的仿真。

3.1系统仿真

仿真采用Brite网络拓扑生成器生成一个类似实际Internet的拓扑，将该拓扑导入Peersim仿真系统，在Peersim上进行基于Gossip的自组织行为的仿真。在P4 2.0GHz的计算机上运行了我们的仿真模型，仿真节点总数为N=1B000，每秒进行一步演化行为，按时间统计的仿真结果如图3所示。

图3的两幅图是当前时刻最大的连通网络中的节点数量占总节点数的百分比和时间的曲线。图3(a)中显示的是不同k取值下的曲线的比较，显然在仿真中都出现了网络分裂的状况，可见对于类似Internet这种存在局域特征的网络，在择优的自组织演化模式下，网络分裂的状况是可能出现的。

另外，由图3(a)可见k的取值对于保持网络的连通性有影响，k越大，越有利于保持全网连通。当k增大时，一方面网络分裂的幅度减小，另一方面，分裂的时间也滞后了。

而图3(b)显示的是选择最近邻居的择优策略和随机选取邻居的随机策略之间的比较，可以看出随机策略在仿真时间内很好的保证了全网连通，这是因为随机策略不受网络的局域特征的影响。

仿真结果显示，增大k值和使用随机策略有助于保持连通性。但是随机策略没有择优能力，实际意义不大，而k值也必须限制在一定范围内。k值大小一方面受节点存储容量限制，更重要的是Gossip协议是一种类洪泛的传输机制，太大的k值会造成转发的数据包以几何级数增加，导致网络拥塞。

3.2进一步的分析

综合以上理论分析和仿真结果，在采用随机自组织策略的情况下，使用类Gossip机制的自组织行为能以很大的概率保持演化中网络的连通性，而考虑了实际网络的局域特征和节点选择时的非随机行为后，网络的分区几乎无法避免。虽然很多复杂的自组织协议并不仅仅以最短的连接作为选择邻居的唯一标准[3]，并且同时引入了确定性选择和随机性选择。但是由于网络的局域特征，同一区域的网络节点在很多性质上都存在一定的共性，而自组织逻辑网络的演化本身又以优化逻辑网络连接为目的，这种择优策略的存在，并不能在自组织模式下完全保证网络的连通性。

产生分区的主要原因，就是网络中区域间的某些关键性的长连接被短连接替换掉了。但是由于自组织网络没有中心控制节点，不能全局掌控整个网络中的所有信息，而那种关键连接只有作为整个网络考虑时，才能够体现出它的重要性。因此无法确定地衡量连接在整个网络中的重要性，导致了可能出现的分区行为。使用类Gossip机制进行拓扑维护和信息传递的Gnutella[4]对等网络系统的早期版本中，存在较严重的断链和分区现象，除其控制协议的不足外，类Gossip机制的自组织演化行为本身对网络的连通性也会产生一定的破坏。

4结语

本文分析认为由于真实网络的局域特征和网络节点邻居的优化选择，使得自组织逻辑网络的演化过程中对于网络连通性的保障极大的下降了。而且网络的自组织是一个周期性、长期性的行为，出现网络分区的概率在反复的操作下会被放大。一旦网络中出现了逻辑分区，网络中信息的传递只能限于局部进行，在没有外在因素介入的前提下，网络连通性无法恢复，只能维持被割裂的状况。因此这种分区行为的危害很大。对于这种无中心的自组织逻辑网络，有必要以一定的手段保证演化过程中网络的连通性。

致谢在此,我们向为本文给予无私帮助的老师和同事表示感谢。

致谢在此,我们向对本文的工作给予支持和建议的同行，以及和我共同工作的老师和同事，表示感谢,他们对我研究中遇到的一些问题，提供无私的帮助。