网络拓扑结构十篇

网络拓扑结构篇1

P2P的四种拓扑结构

拓扑结构是指分布式系统中各个计算单元之间物理或逻辑的互联关系，结点之间的拓扑结构一直是确定系统类型的重要依据。目前互联网络中广泛使用集中式、层次式等拓扑结构。

Internet本身是世界上最大的非集中式互联网络，但是上世纪90年代所建立的一些网络应用系统却是完全的集中式系统，许多Web应用都是运行在集中式的服务器系统上。集中式拓扑结构系统目前面临着过量存储负载、DoS（Denial of Service，拒绝服务）攻击、网络带宽限制等一些难以解决的问题。P2P系统主要采用非集中式的拓扑结构，一般来说不存在上述这些难题。 根据结构关系可以将P2P系统细分为四种拓扑形式:

中心化拓扑（Centralized Topo-logy）;

全分布式非结构化拓扑（Decentra-lized Unstructured Topology）;

全分布式结构化拓扑（Decentra-lized Structured Topology，也称作DHT网络）;

半分布式拓扑（Partially Decentra-lized Topology）。

各种拓扑的结构特点

中心化拓扑

中心化拓扑最大的优点是维护简单，资源发现效率高。由于资源的发现依赖中心化的目录系统，发现算法灵活高效并能够实现复杂查询。该结构的最大问题与传统客户机/服务器结构类似，容易造成单点故障，易引起访问的“热点”现象和版权纠纷等相关问题，这是第一代P2P网络采用的结构模式，经典案例就是著名的MP3共享软件Napster。

Napster是最早出现的P2P系统之一，并在短期内迅速成长起来。它实质上并非是纯粹的P2P系统，而是通过一个中央索引服务器保存所有Napster用户上传的音乐文件索引和存放位置的信息，其工作原理如图1所示。当某个用户需要某个音乐文件时，首先连接到Napster中央索引服务器，在服务器上进行检索，服务器返回存有该文件的用户信息，再由请求者直接连到文件的所有者传输文件。Napster首先实现了文件查询与文件传输的分离，有效地节省了中央服务器的带宽消耗，减少了系统的文件传输延时。

图1 Napster的拓扑结构

然而，这种对等网络模型存在以下这些问题:

(1) 中央索引服务器的瘫痪容易导致整个网络的崩溃，因此可靠性和安全性较低。

(2) 随着网络规模的扩大，对中央索引服务器进行维护和更新的费用将急剧增加，所需成本较高。

(3) 中央索引服务器的存在常引起版权问题上的纠纷，服务提供商容易被追究法律责任。

综合上述优缺点，对小型网络而言，中心化拓扑模型在管理和控制方面占一定优势。但鉴于其存在的上述缺陷，该模型并不适合大型网络应用。

全分布式非结构化拓扑

全分布式非结构化拓扑的P2P网络是在重叠网络（Overlay Network）中采用了随机图的组织方式，结点度数服从Power-law规律（幂次法则），从而能够较快发现目的结点，面对网络的动态变化体现了较好的容错能力，因此具有较好的可用性。同时可以支持复杂查询，如带有规则表达式的多关键词查询和模糊查询等，采用这种拓扑结构最典型的案例便是Gnutella（音译为纽特拉）。准确地说，Gnutella不是特指某一款软件，而是指遵守Gnutella协议的网络以及客户端软件的统称。目前基于Gnutella网络的客户端软件非常多，著名的有Shareaza、LimeWire和BearShare等。

Gnutella和Napster最大的区别在于Gnutella是更加纯粹的P2P系统，因为它没有中央索引服务器，每台机器在Gnutella网络中是真正的对等关系，既是客户机同时又是服务器，所以被称为对等机(Servent，Server+Client的组合)。在文件检索方面，它与Napster也不相同。在Gnutella网络的发展初期，它主要采用基于完全随机图的Flooding搜索算法。图2 显示了Flooding的工作流程: 当一台计算机要下载一个文件，它首先以文件名或者关键字生成一个查询，并把这个查询发送给与它相连的所有计算机，这些计算机如果存在这个文件，则与查询的机器建立连接，如果不存在这个文件，则继续在自己相邻的计算机之间转发这个查询，直到找到文件为止。为了控制搜索消息不至于永远这样传递下去，一般通过TTL (Time To Live)的减值来控制查询的深度。

图2 Gnutella的拓扑结构和文件检索方法

但是，随着联网节点的不断增多，网络规模不断扩大，通过这种Flooding方式定位对等点的方法将造成网络流量急剧增加，从而导致网络中部分低带宽节点因网络资源过载而失效。所以在初期的Gnutella网络中，存在比较严重的分区和断链现象。也就是说，一个查询访问只能在网络的很小一部分进行，因此网络的可扩展性不好。所以，后来许多研究人员在Flooding的基础上作了许多改进，例如采用Random work 、Dynamic Query等方法。

由于非结构化网络将重叠网络认为是一个完全随机图，结点之间的链路没有遵循某些预先定义的拓扑来构建。这些系统一般不提供性能保证，但容错性好，支持复杂的查询，并受结点频繁加入和退出系统的影响小。但是查询的结果可能不完全，查询速度较慢，采用Flooding查询的系统对网络带宽的消耗非常大，并由此带来可扩展性差等问题。

全分布式结构化拓扑

全分布式结构化拓扑的P2P网络主要是采用分布式散列表（Distributed Hash Table, 简写成DHT）技术来组织网络中的结点。DHT是一个由广域范围大量结点共同维护的巨大散列表。散列表被分割成不连续的块，每个结点被分配给一个属于自己的散列块，并成为这个散列块的管理者。通过加密散列函数，一个对象的名字或关键词被映射为128位或160位的散列值。分布式散列表起源于SDDS（Scalable Distribute Data Structures）研究，Gribble等实现了一个高度可扩展和容错的SDDS集群。DHT类结构能够自适应结点的动态加入/退出，有着良好的可扩展性、鲁棒性、结点ID分配的均匀性和自组织能力。由于重叠网络采用了确定性拓扑结构，DHT可以提供精确的发现。只要目的结点存在于网络中，DHT总能发现它，发现的准确性得到了保证，最经典的案例是Tapestry、Pastry、Chord和CAN。

Tapestry 提供了一个分布式容错查找和路由基础平台，在此平台基础之上，可以开发各种P2P应用(OceanStore即是此平台上的一个应用)。Tapestry的思想来源于Plaxton。在Plaxton中，结点使用自己所知道的邻近结点表，按照目的ID来逐步传递消息。Tapestry基于Plaxton的思想，加入了容错机制，从而可适应P2P的动态变化的特点。OceanStore是以Tapestry为路由和查找基础设施的P2P平台。它是一个适合于全球数据存储的P2P应用系统。任何用户均可以加入OceanStore系统，或者共享自己的存储空间，或者使用该系统中的资源。通过使用复制和缓存技术，OceanStore可提高查找的效率。最近，Tapestry为适应P2P网络的动态特性，作了很多改进，增加了额外的机制实现了网络的软状态（soft state），并提供了自组织、鲁棒性、可扩展性和动态适应性，当网络高负载且有失效结点的时候性能有限降低，消除了对全局信息的依赖、根结点易失效和弹性差的问题。

Pastry 是微软研究院提出的可扩展的分布式对象定位和路由协议，可用于构建大规模的P2P系统。如图3 所示，在Pastry中，每个结点分配一个128位的结点标识符号(nodeID) ，所有的结点标识符形成了一个环形的nodeID空间，范围从0到2128 - 1 ，结点加入系统时通过散列结点IP地址在128位nodeID空间中随机分配。

图3 Pastry的消息路由

图4 Chord的拓扑形状

图5 半分布式拓扑结构 （网络中包含Super Node）

图6 KaZaa的软件界面 Chord

项目诞生于美国的麻省理工学院。它的目标是提供一个适合于P2P环境的分布式资源发现服务，通过使用DHT技术使得发现指定对象只需要维护O(logN)长度的路由表。在DHT技术中，网络结点按照一定的方式分配一个惟一结点标识符(Node ID) ，资源对象通过散列运算产生一个惟一的资源标识符(Object ID) ，且该资源将存储在结点ID与之相等或者相近的结点上。需要查找该资源时，采用同样的方法可定位到存储该资源的结点。因此，Chord的主要贡献是提出了一个分布式查找协议，该协议可将指定的关键字(Key) 映射到对应的结点(Node) 。从算法来看，Chord是相容散列算法的变体。

CAN(Content Addressable Networks) 项目采用多维的标识符空间来实现分布式散列算法。CAN将所有结点映射到一个n维的笛卡尔空间中，并为每个结点尽可能均匀地分配一块区域。CAN采用的散列函数通过对(key, value) 对中的key进行散列运算，得到笛卡尔空间中的一个点，并将(key, value) 对存储在拥有该点所在区域的结点内。CAN采用的路由算法相当直接和简单，知道目标点的坐标后，就将请求传给当前结点四邻中坐标最接近目标点的结点。CAN是一个具有良好可扩展性的系统，给定N个结点，系统维数为d，则路由路径长度为O(n1/d) ，每结点维护的路由表信息和网络规模无关为O(d) 。

DHT这类结构最大的问题是DHT的维护机制较为复杂，尤其是结点频繁加入/退出造成的网络波动（Churn）会极大增加DHT的维护代价。DHT所面临的另外一个问题是DHT仅支持精确关键词匹配查询，无法支持内容/语义等复杂查询。

半分布式拓扑结构

半分布式拓扑结构（有的文献亦称作混杂模式，英文表达为Hybrid Structure）吸取了中心化结构和全分布式非结构化拓扑的优点，选择性能较高（处理、存储、带宽等方面性能）的结点作为超级结点（英文表达为SuperNodes或者Hubs），在各个超级结点上存储了系统中其他部分结点的信息，发现算法仅在超级结点之间转发，超级结点再将查询请求转发给适当的叶子结点。半分布式结构也是一种层次式结构，超级结点之间构成一个高速转发层，超级结点和所负责的普通结点构成若干层次。采用这种结构的最典型的案例就是KaZaa。

KaZaa是当前世界最流行的几款P2P文件共享软件之一。根据CA公司统计，全球KaZaa的下载量超过2.5亿次。使用KaZaa软件进行文件传输消耗了互联网40%的带宽。KaZaa之所以如此成功，是因为它结合了Napster和Gnutella共同的优点。从结构上来说，它使用了Gnutella的全分布式结构，这样可以使系统更好地扩展，因为它无需中央索引服务器存储文件名，而是自动把性能好的机器当成SuperNode，它存储着离它最近的叶子节点的文件信息，这些SuperNode再连通起来形成一个Overlay Network. 由于SuperNode的索引功能，使搜索效率大大提高。

网络拓扑结构篇2

【关键词】拓扑结构；国际贸易；网络；经济；相关性

一、前言

随着科学技术的不断进步，我们已经步入了信息化时代，并且网络系统也越发的完善，有许多复杂的系统都能够通过网络来对其进行表示，比如：英特网、蛋白质网络以及食物链网络等等。国际贸易体系是由发达国家和发展中国家构成的典型复杂系统，目前已经有一百多个国家加入，各个国家之间的物质、资金以及信息进行持续的流动，随着信息时代的来临，全球经济一体化，世界贸易关系形成的相互影响，相互作用网络，在国际贸易体系当中任何国家的经济波动以及贸易政策的变动都将会直接或者间接对国际贸易网络中的一些别的国家产生一定影响，因为各个国家之间存在的一定的依赖性，这种影响一般说来不仅仅是局限于局部国家，而是能够凭借国际贸易网络而进行传播的，比如二十世纪九十年代的金融危急，就是一个很好的例子，几乎对世界上大部分国家的经济都造成了一定的影响，对此，我们不难看出国际贸易网络拓扑结构的演化研究分析的重要性。

二、构建国际贸易网络研究

在国际贸易网络的系统当中，每一个顶点就代表一个国家，国家和国家之间的贸易关系使用服务流动方有向边以及代表商品来对其进行表示，这样能够用有向网络来对国际贸易系统进行表示，网络不会依靠顶点的相应位置以及边的相关形态而体现出来的性质一般就被称之为网络拓扑性质，与之相对应的结构就被叫做网络拓扑结构。在国际贸易网络组织构建的过程当中，按照服务流向以及商品来对网络当中边的指向进行确定，出口和服务流出以及商品相对应，进口则对应于服务流入以及商品，假如在t年i国向g国出口货物或者是服务，那么在第t年网络快照就建立起了t到g的相应的边，其邻接矩阵具有非零原始aig（t）=1，如果t到g的没有相应的边存在的时候，那么aig（t）=0，在每一年国际贸易网络拓扑结构都会构成相应的国际贸易网络快照，并且每个国际贸易网络的快照都会呈现出较为特别的拓扑性质，这对于网络连通性以及动力学都有着十分巨大的影响，因为国际贸易网络有很多的拓扑性质没法用随即图范式对其进行诠释，随意需要选择恰当的测度指标将网络拓扑性质以及演变规律进行分析研究。

三、度的分布

顶点度具体就是指的和顶点相关联的条数，就有向网络来说，每一个顶点都会有与之相对应的入度以及出度，N（t）表示在t年世界上进行贸易国家的具体数量，国家i在t年入度以及出度和i国的出口以及向i国进口的国家数量相对应。根据西方学者对于世界贸易网络的研究，他们将其度分布成为带有幂指数形式的网络，这种网络也被叫做无标度网络，并且将真实的系统经由自组织而生成无标度网络有两个非常重要的关键性因素，分别是择优连接与增长性，在BA的模型当中，新增点择优连接，在整个网络当中需找连通度相对较大的顶点，并且网络中顶点连接数量就会呈现少数顶点拥有大量的连接，但是数量庞大的顶点只是具有非常少的连接，无标度完了度之间的关系以及累计度分布的关系表现在双对数坐标图中时为一条直线。下图（图一）给出了2012年国际贸易网络双对数坐标中累计出度的分布状况，其他一些年份的入度以及出度的累计度分布情况和其有很大的相似程度很高，从下图中我们不难看出，其图形仅仅是在中间局部度区域内呈现直线形式，由此可见国际贸易网络并非无标度网络。

图一：2013年累计出度分布的双对数坐标图（如下图）

在构建国际贸易系统的时候，发达国家往往因为经济实力雄厚，在贸易关系开展的过程当中往往出于优势地位，国家贸易关系数量和GDP的规模具有对应的关系，在调查研究中，贸易网络的构建是需要较大规模的交易关系促成的，一般都具有在全球贸易网络当中选择的优先权，所以2013年累计出度分布的双对数坐标图双对数坐标下会呈现一条直线，这就意味着其有着无标度网络的特点。就研究对象而言往往会选择国际贸易网络发展当中新增长顶点所代表的国家，都是经济规模相对较小的国家而言，其贸易商品也存在一定的局限性，大多都是属于基本商品，因为地理位置以及时间差所导致的运输成本增加，无标度网络在构建的过程当中的优先选择机制没法在国际贸易网络中得到最大化的体现，这部分国家往往主要是与周边的一些邻国进行贸易，并没法在全球贸易网络当中进行优先选择连接，对此，我们不难看出择优机制发挥的重要作用，但是这里需要注意的是无标度网络并不能够代表完整的国际贸易网络。

四、群聚性

一般来说，我们可以将群聚系数定义成对有ki条边的顶点i，群聚系数为Ci= 2niPki（ki-1），在这当中ni为i的ki个邻居间边数量，假设CI为零，顶点i邻居间没有连通，如果Ci为1，那么顶点i邻居间连通，高群聚性显示顶点周围邻居间连通性良好，把国际贸易网络中的度是k的顶点群聚系数取平均值获得C（k），具体表示如下

NP（k）是度为k的顶点数量。

图二：1970年度和群聚系数的示意图

图三：2005年度和群聚系数的示意图

通过上图（图二）（图三）当中C（k）和k之间的关系，我们不难看出，每一个网络快照当中，C（k）的趋势是伴随着度k的上升而不断的下降的，其顶点度k的多少，直接反映出国家的贸易联系范围的广泛性，一般说来，度数较少的国家，往往经济规模也相对较小，因为经济规模对其的约束，其在周边地区展开贸易关系的情况居多，对此，这些国家的贸易伙伴在上地域上相对较为集中，贸易合作伙伴间贸易的频率也更为频繁。另一方面度数相对较高的国家往往属于全球性的贸易大国，其贸易对象遍布全球，和贸易合作伙伴直接进行贸易的机会相对较少。从图中我们可以发现，散点在逐渐的集中，具有良好的一致性，这就表明各个国家在国际贸易格局中分工与地位日益明确，国际贸易网络总体呈现出一种协调有序的状态。

五、结束语

国际贸易网络具有一定的复杂性以及多元性，其拓扑结构的规律对系统发展规律以及贸易政策的制定都有着极其重要的影响，本文就国际贸易网络的拓扑结构演化进行了简要的探讨，希望能够给相关人员提供一些有用的参考。

参考文献：

[1]张勤，李海勇，马文杰等.入世十年来我国在国际贸易网络中的角色与地位演变轨迹[J].商业研究，2013，（5）：38-46.

[2]刘宝全.国际贸易网络的稳定性研究[J].经济视野，2013，（10）：300-301.

[3]赵从从（译）.联邦快递推出波音777货运服务 拓展国际贸易网络[J].邮政研究，2012，（4）：10-10.

[4]王维红.国际贸易网络中金融危机跨国传播研究：基于复杂网络理念[D].东华大学，2012.

网络拓扑结构篇3

1.1节点兴趣相似度

1.1.1节点的兴趣域向量空间模型(VectSpaceModel，VSM)[12]是指利用关键词及对应关键字的权值构成的向量来表示节点的兴趣模型，是信息获取领域经典的统计算法。本文采用VSM模型表示节点的兴趣，给每个节点建立一个关键字表(Keywdtable，KT)，KT表包含两部分关键字：本地资源关键字表(LocalResourceKeywd，LRK)，如果节点具有某种兴趣，那么该节点很可能存储反映该兴趣的文件或者文档，这就是本地资源，本地资源所包含的关键字隐含了该节点的兴趣；本地查询关键字表(LocalQueryKeywd，LQK)，如果节点对某种内容感兴趣，它収出的搜索请求中就会隐含这种关键字，每当节点収出搜索请求时就会更新LQK表，如果収出的查询消息中关键字不在LQK表中，则把关键字添加到LQK表中。

1.1.2兴趣相似度计算方法VSM模型表示的数据，通常用相似性函数计算两个特征矢量乊间的相似性。常用的计算方法一般有欧几里德距离、欧氏距离、夹角余弦等，本文采取夹角余弦算法计算节点间的兴趣相关度。

1.2完全二叉树二叉树是每个节点最多有两个子树的有序树。若一棵二叉树至多只有最下面的两层上的节点的度数可以小于2，幵且最下层上的节点都集中在该层最左边的若干位置上，则此二叉树成为完全二叉树(CompleteBinaryTree，CBT)。CBT树具有以下性质：(1)设CBT树的深度为h，除第h层外，其它各层(1~h1)的节点数都达到最大个数；(2)第h层所有的节点都连续集中在它的最左边，从左到右依次排布。即节点有右孩子节点必须有左孩子节点，不存在没有左孩子节点只有右孩子节点的情况；(3)约定根节点所在的层数为1，根节点编号为1。则CBT中编号为r的结点，其左子树编号为2r，右子树编号为2r1。

1.3CBT-BI根据CBT树结构特征，在采用CBT树构造非结构化P2P覆盖网络拓扑结构时，必须从CBT树的根节点开始构建，确定根节点的兴趣域D，其他节点按照兴趣相似度值大小在CBT树中按序排列。在整个构建过程中，需要保证整棵CBT树的完全性，最后生成的兴趣完全二叉树(CompletelyBinaryTreeBasedOnInterest，CBT-BI)满足：左孩子节点高于右孩子节点；上层节点高于下层节点。网络建立初期，节点都没有资源搜索记录，即LQK表为空，因此CBT-BI网络建立以节点的LRK表为依据。随着网络的収展，搜索请求次数增加，LQK表不断更新。每个周期时间T对KT表进行更新，KT表更新后再次和根节点的兴趣域进行相似度值计算，幵根据相似度值调节自己在CBT-BI网络中的位置。将网络中的节点分为超级节点(SuperNode)和普通节点(dinaryNode)，超级节点在选取时应该综合考虑带宽、信息处理能力、稳定度、在线时长、存储能力等，下面是节点性能评价权重表达式。其中，W表示节点的能力评分；N表示节点网络带宽；S表示节点的稳定程度；T表示节点的在线时间；C表示节点处理信息的能力；M表示节点的存储能力；a、b、c、d、e分别是各项指标的比重。选择节点能力评分W最高的若干个节点做为超级节点，且超级节点两两乊间的兴趣相似度值不能超过一定的阀值，否则选择其中性能更优的做为超级节点，另一节点则为普通节点。将超级节点设为CBT-BI树的根节点，根节点再向网络中的普通节点进行广播，广播信息中包含自身兴趣域向量集D，普通节点收到根节点的广播命令后计算与根节点的兴趣相似度值Sim幵按值进行排序，选择Sim值最大的根节点収送加入请求信息幵包含Sim值。根节点收到请求后，为该节点分配一个唯一的ID编号，CBT-BI树中节点的ID编号按照节点所在的位置唯一指定。约定根节点所在的层数为1，根节点ID编号为1，第二次层的第一个节点ID编号为2，则第N层第一个节点ID编号为12N，第二个节点ID编号为1(21)N，幵以此类推。由此可以确定每个节点的唯一编号ID幵且按照节点与根节点的兴趣相似度值大小反向排序，即兴趣相似度值大的节点其ID编号越小，离根节点的逻辑位置近，反乊兴趣相似度值小的节点其ID编号越大，离根节点的逻辑位置远。

1.3.1路由表信息超级节点作为一棵CBT-BI树的根节点，应该维护和存储整棵CBT-BI树的相关信息，为根节点定义了路由表：(1)ID编号：存储的是CBT-BI树中所有节点的ID编号。每个编号和节点位置相关且唯一；(2)兴趣域：记录整颗CBT-BI树的兴趣域。当资源查询请求不在CBT-BI树的兴趣域中但在该CBT-BI树中成功搜索到所需资源后更新他的兴趣域；(3)朋友节点表：维护和其他CBT-BI树根节点的逻辑链接。根据历史记录，成功在其他CBT-BI树中搜索到所需资源的加入到该朋友节点表中；(4)历史记录：保存该组的历史查询记录。普通节点的路由表：(1)ID表：本节点的唯一编号ID；(2)兴趣表：存储KT表以及节点与根节点的兴趣相似度值。每个周期T更新KT表幵重新计算其相似度值。

1.3.2节点加入新节点ip加入网络时，向网络中所有根节点収送包含节点本身兴趣的信息，与根节点计算兴趣相似度值()iSimp，获得根节点返回的()iSimp值后排序。选择()iSimp值最大的根节点収送加入请求幵包含()iSimp值信息。根节点收到ip的加入请求时按照()iSimp值在它的子树中进行排序，为其分配ID编号，将ip揑入到CBT-BI树中对应的位置，具体的节点加入过程如图1所示：假如新加入的节点ip的兴趣相似度值()iSimp满足以下：12()()()iSimpSimpSimp，则节点ip的在CBT-BI树中的位置应该在节点1p，2p的中间。根据CBT-BI树的性质，ip揑入到原有节点1p的右孩子节点即2p的位置，节点2p所在的层Level3中2p及后面所有节点的位置往右移一个，该层最后一个节点4p移动到下一层Level4的左边第一个节点5p的位置，以此类推。所有节点按照本规则重新在CBT-BI树中排序，始终保持所有节点相互连接幵满足CBT树的形态。

1.3.3节点退出非结构化P2P网络中的节点大量的加入与退出，节点的退出分为异常退出和本文讨论的正常退出两种情况。节点ip请求退出网络时向所在的CBT-BI树的根节点収送退出消息，根节点收到退出消息后删除ip的ID编号以及路由表中相关信息，幵且通知ip节点的后续节点进行补位操作，填补ip的空缺。节点退出的过程如图2所示：根节点收到节点ip的退出消息，向节点ip的右邻居节点1p及后续所有节点収送广播消息，位置均往前移动一个。节点ip所在的层Level3的节点1p,2p往左移一个，Level4的第一个节点3p移动到上层的最右边2p位置，4p则向左移一个位置，以此类推。所有节点按本规则重新在CBT-BI树中排序，始终保持所有节点相互连接满足CBT树的形态。节点每个周期时间T更新KT表，重新计算相似度值，相似度值改变的节点首先在CBT-BI树中退出再申请加入，保证CBT-BI树的实时更新。

1.4资源搜索在分布式搜索算法中，资源的搜索是沿着相连接的节点进行转収的。邻居收到消息后，首先检索本地资源是否满足搜索请求，将搜索成功的消息沿原路径返回给查询节点。否则，查询消息继续収送给邻居节点。资源搜索的深度由计数器(Time-To-Live，TTL)控制，消息每转収一次，TTL值就减1，当TTL减至0时，查询消息停止转収不再查询。在非结构化P2P网络中节点成功构建CBT-BI覆盖网络后，资源的搜索根据查询请求的兴趣倾向在对应的CBT-BI树中查询。分为两个阶段：第一阶段在查询消息兴趣倾向所对应的CBT-BI树中进行搜索，根据CBT-BI树结构的特点使用基于泛洪算法的双向路由算法；第二阶段在CBT-BI树中搜索失败后，根据CBT-BI树根节点的朋友节点表，在相互连接的兴趣树中再进行消息路由。当网络中某个节点収出一个查询请求Q时，将该查询请求看做一个关键词向量，记12Q(,,...,)qqqmwww，m为查询请求Q中关键词t的个数，qmw表示mt在查询请求Q中的权值。查询请求Q首先向网络中所有CBT-BI树的根节点収送包含关键词向量的广播消息，根节点收到广播消息后计算查询请求Q与根节点兴趣域的兴趣相似度值Sim(Q)幵返回给查询消息Q，查询请求Q按照Sim(Q)值大小排序，选择Sim(Q)值最大的根节点収送资源搜索请求。由于兴趣相似度更大的节点更可能含有彼此感兴趣的内容，查询消息Q在CBT-BI树搜索的第一阶段分为两步进行，第一步搜索CBT-BI树中兴趣相似度大于Sim(Q)的节点，第二步搜索兴趣相似度小于Sim(Q)的节点。在CBT-BI树中第一阶段的资源搜索算法描述如下：第1步首先在根节点和ip节点搜索本地资源，查找成功则返回结果，否则转至第2步；第2步选择邻居节点ID小于ip节点的ID，进行消息转収否则不转収；第3步收到查询消息的节点若均已被访问过，则跳转至第6步，否则转至第4步。第4步查询本地资源资源，成功则返回结果否则转至第5步；第5步判断TTL值，值为0则搜索结束，否则转至第2步；第6步选择邻居节点ID大于ip节点的ID，大于进行消息转収幵转至第7步，否则终止转収；第7步查询本地资源资源，成功则返回结果否则转至第8步；第8步判断TTL值，值为0则搜索结束，否则转至第6步；第一阶段资源搜索过程如图3所示，如()()iSimQSimp，则ip的ID编号収送给查询消息Q，再复制一个查询消息副本Q''''，查询消息Q先在ID编号小于ip的所有节点上查询，查询消息Q含ip的ID编号及TTL值。先在根节点和ip节点开始查询，若找不到则将消息转収至其关联节点，如第一次转収：R节点的关联节点以及ip节点的父节点如图中，第二次转収为收到查询消息的节点的关联节点如图中，所有转収的关联节点必须满足ID编号小于ip的ID编号，以此类推。若第一步资源搜索失败，则继续第二步的资源搜索，在Sim值小于Sim(Q)的节点间查询。如果第一阶段查询失败，则进行第二阶段的资源搜索，根节点将查询请求Q转収给朋友节点表中的根节点进行资源搜索。在整个搜索过程中，根节点的作用是与查询消息Q计算兴趣相似度值Sim(Q)幵判断其在CBT-BI树中的位置，在第二阶段搜索过程中，将查询消息Q转収给朋友节点表中的根节点。如前所述，仸一个拥有N个节点的CBT-BI网络拓扑，其深度不超过2(logN)1远小于N，因此只要TTL值选择适当，该双向资源算法可以搜索到整个CBT-BI网络。

2仿真分析

仿真实验采用PeerSim仿真模拟器[15]，在Java搭建平台上进行，PeerSim模拟P2Poverlay网络，幵支持结构化P2P网络和非结构化P2P网络的模拟。为增加仿真实验的真实性，非结构化P2P网络中的节点和资源分布都服从Zipf分布。网络中共产生20000个网络节点，每个模拟周期随机产生100次查询，所得数据通过以下三个衡量标准对改进的CBT-BI网络双向搜索算法、AVLNet网络[11]搜索算法以及RW算法比较，进行分析和验证。

2.1搜索成功率非结构化P2P网络中资源搜索成功率：图4为资源搜索成功率与搜索跳数TTL的关系，从图中可以看出，在TTL值相等的情况下，CBT-BI网络双向搜索算法的搜索成功率比AVLNet、RW算法有一定的优势。TTL为1时搜索成功率都比较低，而随着TTL值的不断增加，资源搜索的覆盖率越大，搜索成功率也随乊增加，TTL设为7时CBT-BI网络的搜索成功率达到90%以上。CBT-BI网络中所有兴趣相近的节点聚集在一起，双向搜索算法使搜索消息首先向兴趣相似度最近的节点进行查询转収，因此在TTL值相同的情况下，CBT-BI网络中搜索到资源的效率比盲目的在网络中查询转収搜索效率明显要高。

2.2消息冗余率网络中存在的消息数量会直接影响到网络的负载和节点的计算资源，在保证搜索成功率的前提下，减少搜索产生的消息数量是改善搜索性能的有效手段。实验结果如图5所示：图5为资源搜索过程中查询所产生消息总量的对比图，显示了在一个模拟周期中随着资源搜索次数的不断增大对应查询消息冗余率的变化情况，图中可以看出CBT-BI网络虽然随着搜索次数增加也在不断增长，但是其值相对比较低。当搜索次数为10时，查询算法产生的冗余消息都很少，可以忽略不计。随着搜索次数的增加，产生的消息冗余量不断增加，其中RW算法的消息冗余率增长最快，AVLNet网络搜索算法相对较慢。实验结果表明，CBT-BI网络在一定程度上可以减少消息冗余量，低系统的额外开销。

2.3平均路径长度平均路径长度是指搜索路径长度的平均值，是决定搜索过程中延时的直接因素。搜索过程中跳数越大，表明搜索路径越长，搜索延迟也会相应的增加，势必造成网络负载加大，所以搜索到所需资源的跳数越少越好。仿真实验结果如图6所示：仿真实验对比的是搜索次数相同的情况下平均路径长度的对比，以及随着搜索次数的增加平均路径长度的变化情况。从图6所示的实验结果可以看出，RW、AVLNet网络算法的平均路径长度一直“居高不下”，明显大于CBT-BI的平均路径长度，而随着搜索次数增加各网络的平均路径长度均保持在相对比较稳定的跳数范围内。在搜索次数达到40次以后，CBT-BI的平均路径长度维持在4跳左右，RW的平均路径长度维持在8左右，AVLNet的保持在7跳上下浮动，可以看到CBT-BI的平均路径长度有改善效果。由于平均路径长度是决定搜索中延时的直接因素，仿真实验可以看出，CBT-BI的平均搜索时间复杂度也相对的较小。

3总结

网络拓扑结构篇4

关键词：广域；继电保护；分层系统结构

中图分类号：TM77 文献标识码：A

现如今，随着科学技术的不断发展，使得智能电网技术得到了快速的提高。在现如今的电网运行中，传统的电力技术对电子信息技术、通信技术和计算机网络技智能技术进行了融合。高科技技术在电网建设中的应用越来越广泛，大大的促进了电力行业的综合发展。随着电网建设的发展越来越快，电力系统电网结构及运行方式复杂性增加，使得保护动作具有较长的延时性。在面对突发问题时，传统的后备保护方式将会影响到系统的稳定性，对电网的正常运行产生影响。广域继电保护的基础是将保护算法与分层系统结构相结合，实现安全可靠的网络通信。

一、广域继电保护的分层系统结构特征分析

作为电网运行保护的一种新型模式，广域继电保护是电力系统的新增业务，其分层系统结构一般按照层次的作用将保护网络分为三个层次，分别是接入层、汇聚层和核心层。在对广域继电保护分层系统进行设计时，对数字化变电站和电力通信的网络的设计起到了重要的作用。在实现广域继电保护功能的前提下，是不会影响电力通信网络中现有的业务功能。对于广域继电保护分层系统来说，其一般采取的模式为信息集中和区域集中决策相协调的策略，在分层系统中包含有变电站和调度中心，其中子站广域继电保护IED 被称为TCU，DCU则代表主站中的广域继电保护IED，MU代表为调度中心的广域继电保护IED。现如今，对广域继电保护的定义主要是针对相同电压等级线路进行的保护。一般情况下，在广域通信网络的结构层面可以得出。对于整个广域继电保护分层，其相同电压等级的结构一般分为三个层次，分别表示为核心层、汇聚层和接入层。在对广域继电保护通信结构进行创建时，可以看做是若干个含有主站的区域组合而成，每个区域中的主站是由变电站担任的，并把区域的主站组成汇聚层，对子站上的信息数据进行汇聚，并按照主站的区域进行划分。对于划分后的子站信息进行分析，确定其属于哪个主站区域，并将该区域中除了主站之外的变电站设置为子站。那么，作为对信息进行采集和上传的子站就构成了广域继电保护结构中接入层。而广域继电保护分层结构中的核心层则是由广域电网的调度中心MU组成的。

在对广域继电保护的分层结构进行了描述之后，我们已经对广域继电保护的三个分层结构有了一定的认识。在确定了接入层的子站之后，对于子站进行广域继电保护则是由信息采集单元和跳闸执行单元两个结构部分组成的。其中，信息采集单元主要是对启动原件进行判断以及测量保护线路段开关量和模拟量。在测量保护电路的模拟量时，其主要步骤是先对模拟量的测量值进行预处理，并根据与处理后的结果计算相应的权重值，最后将子站得到的预处理值和相应的权重值上传给区域中的主站，由主站对上传来的信息进行分析和处理。另一方面，子站广域继电保护的跳闸执行单元结构部分则是对主站传来的公职命令进行接收和执行，同时综合考虑本地后备保护的配合，最后得出相应的处理措施，对断路器跳合闸的开关进行控制，同时并将处理后的信息作为反馈传回给主站和核心层的调度中心。

在对广域继电保护中子站的结构层次进行了分析后，下面将对主站的继电保护层次进行分析。我们知道广域继电保护在主站中分为综合决策单元和信息采集单元，其中信息采集单元主要是处理主站中的TCU任务，对主站区域内的信息进行收集的同时，执行对核心层的调度中心下达的命令。继电保护层次的另一个组成部分是综合决策单元，是根据区域中子站上传的信息进行处理，包括广域继电保护运算等操作。区域内出现的故障问题进行处理后，将具体的处理措施下传给子站进行执行，对故障进行控制和处理。最后，广域继电保护系统的核心部分是调度中心，调度中心是整个继电保护系统的核心，通常是对各区域的继电保护情况进行监测，对全网实时拓扑结构、故障记录查询等的实施协调与监控，保证整个系统的正常稳定运行。

二、广域继电保护IED 接入变电站网络与电力通信网

（1）广域继电保护IED 接入变电站网络。将广域继电保护IED接入到变电网络去，需要把数字化变电网络的通信设计方案与其结合起来，在数字化变电站网络的通信方案确定之后，实现广域继电保护IED 接入变电站网络的配置。一般情况下，在数字化变电站通信中，全站统一网络与独立过程网络是两种应用较多的网络通信方案。其中，独立过程网络较容易实现，而全站统一网络是一种信息高度共享网络，相对于独立过程网络优势明显，是数字化变电站通信网络的最终选择方案。例如，针对于220kV的两电压等级的数字化变电站，在对此数字化变电站进行数字化拓扑结构建设时，通常是将广域继电保护进行接入。在数字变压器中按照电压分为高压侧和低压侧，针对于不同的电压分侧，采用的不同的拓扑结构。针对于变电站的低压侧一般采用间隔交换机来与间隔内的过程层设备进行连接，并与集中备用交换机相互作用。另一方面，针对于数字变电站的高压侧，通过间隔交换机与断路器以及间隔内的合并单元进行相互作用，建立起通信网络使间隔设备之间进行连接通信。与此同时，公共交换机使得跨间隔设备的过程层在高压侧相连，并在低压侧与另一交换机进行连接。

（2）广域继电保护IED 接入电力通信网。在与电力通信网的接入过程中，广域继电保护IED是将网络通信业务通过MSTP平台传输给电力通信网，期间传输的网络通信业务通过广域继电的方式进行保护。，将广域继电保护IED 接入电力通信网，也就是是指将传输的通信业务通过广域继电保护的方式，通过MSTP平台传给电力通信网。

（3）广域继电保护分层系统结构的网络拓扑设计。在对广域继电保护分层系统结构网络拓扑进行实现的过程中，一般首先是设计HVPLS网络拓扑结构，之后将以太网业务接入MSTP的设备之中，以太网接口业务一般包括调度数据网、综合数据网和继电保护数据网等业务，上述业务都是通过虚拟的独立网桥实现连接的。广域继电保护分层系统结构网络拓扑的实现方式通常是通过MSTP设备来实现的，在广域继电保护模式中，作为一种集中式的业务形式广域继电保护是对主站汇集到的信息进行保护，并将信息送到核心层，通过组网的形式实现网络通信传输结构形式。

结语

综上所述，要实现广域继电保护就需要配备高效稳定的通信网络，对于继电保护分层系统结构进行网络拓扑设计，有利于使得广域继电保护在电网运行和维护过程中迅速发展，并且可以促进电网的安全稳定发展，推动电力行业的快速、健康稳定的发展。

网络拓扑结构篇5

网络资源拓扑的发现是网络资源管理的核心功能之一，它可以定义为：将运行在各式各样异构的网络环境下的资源，主要是网络设备之间的连接关系与实际的运行状态通过一定的手段对其进行整理汇总，以统一的格式提交给网络管理系统，从而有效提高了管理复杂网络环境的效率。其中，如何构建全方位、直观的网络拓扑图在网络拓扑发现中是一个重要课题。当前存在的网络拓扑发现方法包括：（1）基于ICMP网络控制报文协议拓扑发现，由主机向路由器发送测试报文来发现网络拓扑结构。其特点是实现简单，但是发送过多的测试报文同时增加的网络的负载，容易造成链路阻塞，不适宜目前大型的网络环境。（2）基于ARP地址解析协议拓扑发现，通过主机向网络中广播目标地址的ARP请求来发现具体的网络拓扑，并加载在ARP缓存中。其特点是ARP缓存中网络地址都是有效唯一的，这大大提高了网络拓扑发现的效率；但是此方法的缺点也很明显，在网络纵深过大的环境下，由于ARP缓存储存的信息量是有限的，会产生ARP请求到达不了的“盲区”。所以满足不了动态异构的大型网络对网络拓扑发现的要求。

1SNMP协议在网络拓扑发现中的运用

SNMP协议在当前网络管理中起着至关重要的作用，越来越多的网络设备都支持该协议，SNMP协议的运行模式是：所有被网络管理系统所监管的网络设备将与网络运行相关的数据项通过Agent进程进行汇总处理，并提交给MIB管理信息库，由Manager管理终端与进程的交互，使用SNMP协议所规定的TRAP、GetRequest、GetRespones等指令来完成相应的网络信息查询和设置修改参数。

2网络拓扑发现算法描述

网络拓扑中各子网通过与之相连的路由器转发设备相互连接。这些通过网关相连的子网可能是同处在一个局域网之内的，也可能是分布在不同的局域网中，通过路由器的不同端口或者不同相连的路由器建立连接从而进行网络通信。因此网络拓扑结构被分割成了两个紧密相关的层次，一级网络拓扑结构与二级网络拓扑结构。我们把网络中各子网通过的路由器相连的整体连接状况称为一级网络拓扑结构；而在各子网内部的网络设备的连接情况称为二级网络拓扑结构。构造一级网络拓扑结构是通过查询路由信息表中的ipRouteNextHop（路由下一跳的ip地址）、ipRouteDes（t网络目的端的ip地址）和ipMask（路由掩码）等参数，从网络管理终端出发依次遍历整个网络中的路由设备。其中，需要除去可能出现在路由表中的设备本地ip地址，通过查询路由设备中ipForwarding参数值来判断该路由设备是否是子网间的外部网关，若ipForwarding值为1，表明此路由设备属于一级拓扑结构，反之则表明此路由设备属于二级拓扑结构。构造二级网络拓扑结构主要是通过查询子网内每台网络设备接口表ifTable中的Ifindex端口索引来判断同属一个子网内的路由器各端口连接的网络设备情况，路由器每个端口号与次端口连接的子网的子网号一一对应，并按照不同的端口号与子网掩码分别放入不同的路由队列中。基于SNMP协议的网络拓扑发现算法的基本流程包括如下步骤：（1）初始化路由队列Q；（2）通过Agent进程访问Q中的初始节点A，visited[A]=1，A为队列Q中的第一个元素；（3）由Agent进程向A的下一个邻接节点B发送查询数据包并等待节点B的反馈数据包，收到反馈后对其进行解析，通过MIB信息中的IpRouteType值来判断B是否与A处于同一个子网中；若IpRouteType的值为3，表明这两个节点是处在同一子网内；IpRouteType值为4时，表示路由器连接入另一个非本地子网中，需至少再经过一个路由器的转发；将所经过的路由信息添加至路由链表中，并记录A与B之间的连接关系。（4）如果B未被Agent进程访问，则visited[B]=B，节点B进入队列Q中，并将ipRouteNextHop参数无重复地放入连接队列，将ipRouteDest无重复地放入子网队列中；以此类推，直到遍历完所有节点。

3具体实现步骤

（1）网络设备由Agent进程收集有关的网络SNMP信息，将Community中公开的权限设置为可读，并设置Trap的告警信息指向网络管理系统；（2）网络管理系统通过使用SNMP协议中的GET指令来查询收集网络中各类设备的唯一标识码OID，来访问各网络设备的MIB变量信息，并对这些MIB信息进行统一的分类与整理完毕后，一起储存在数据库中；（3）后台通过使用JAVA语言编写统一的类和接口，方便同时访问不同关系的，存储网管系统所提供各类设备网络相关信息的数据库；（4）为了将存储在数据库中的网络信息链表以一种简单直观的图形方式呈献给用户，要求WEB服务器不仅可以取到数据库中的与网络设备相关的数据，而且当WEB服务器接收到绘图指令后，读取网络拓扑信息，查询拓扑信息表内的末端元素，根据算法的递归深度来判断此元素在拓扑结构中的具置；（5）由于网络环境的复杂多变性，对网络结构拓扑图产生了新的要求，网络拓扑需要在一定的时间段内刷新，用以实时发现更新后的网络拓扑，再对拓扑结构图进行相应的改动，而这个刷新的间隔时间的取值需适中，间隔时间太长会影响网络拓扑信息的实时准确性，会造成系统的负载过大，从而对网络管理造成不必要的负担。每次添加新的网络节点时，需要判断是否与已知存在的节点使用同一个路由器，避免路径的回路重复显现。

4结语

网络拓扑结构篇6

关键词：网络拓扑发现 STP SNMP ICMP

中图分类号：TP393 文献标识码：A 文章编号：1674-098X（2014）07（b）-0046-05

随着网络的不断发展与普及，网络的规模变得越来越大，网络的结构变得越来越复杂，对网络进行有效的管理和控制是保证网络处在正常高效运转的关键。但对网络进行有效的管理首先要获得网络的拓扑结构，而网络的结构复杂、节点数目繁多，靠人工统计往往是行不通的，而目前的网络拓扑发现技术又存在着一定的不足，所以研究更加有效的手段来得到网络的拓扑结构具有重大的意义。

1 网络拓扑发现算法研究

在网络拓扑发现技术方面，美国康奈尔大学的CNRG网络研究组、CAIDA组织的Skitter [1]和贝尔实验室在这方面都有了深入的研究，他们设计的算法及其技术都已经具有较好的应用，并且已经进行了商用。

在物理网络拓扑发现算法中，由于交换机转发数据具有透明性的特点，这就给物理层的拓扑结构发现带来了很大的困难。针对物理网络中的拓扑发现问题，中科院计算所的郑海提出了能依赖不完整的交换机AFT来发现物理网络拓扑的算法[2]，随后他们在此基础上进一步解决了子网中存在Hub的判定情况[3]，但存在的不足在于它们都不能准确判定链路是否为冗余链路。文献[4]和[5]给出了基于端口流量的拓扑发现算法，通过对端口流量数据的分析进而实现了网络拓扑发现，但是该方法的实际数据无法准确获得，并且获得的数据可能存在很大的误差，不具有实际的应用性。文献[6]和[7]中利用交换机地址转发表的数据构建了网络的拓扑结构，是一种数据链路层的拓扑结构发现方法，但是这种方法无法对哑交换机（不能通过SNMP协议访问的交换机）进行有效的发现。文献[8]和[9]同样给出了一种基于生成树协议（Spanning Tree Protocol，STP）的数据链路层网络拓扑发现算法，这种算法具有分析得到哑交换机的连接关系的能力，但是其缺点是无法发现交换机与主机的关系，并且要求交换机支持STP协议才能有效。

IETF于2000年推出物理拓扑MIB （Management Information Base）[10]，它IP网络的相关对象如图1所示。IETF试图去解决网络拓扑结构发现的问题，但是IETF并没有具体给出如何获取MIB的具体方法，只能通过一些通用的协议来获取MIB。

2 基于STP协议的网络拓扑发现算法

生成树协议（Spanning Tree Protocol，STP）的主要功能有两个：一是创建以某台交换机为跟的网络拓扑生成树，同时能够避免环路的产生。二是在网络拓扑发生改变时，能够达到收敛保护的目的。算法能够实现的基础在于网络中每台交换机都在Bridge MIB中保存了其交换域生成树的一部分，利用SNMP协议来获取MIB中的这些信息，再根据STP协议的特征，通过比较就可以得到整个网络拓扑结构。根据STP协议我们可以推导出以下八条结论[11-12]，这几条结论可以帮助我们判断各个端口的关系。

结论一：设交换机的根接口指定网桥为，指定接口为，由于能运行生成树协议的必须是交换机，所以必为交换机，且、通过接口、直连或通过集线器互连（设备级直连）。

结论二：处于转发状态的接口为所在网段内的其他网桥传播信息，所以必须存在连接。若无连接，它不会参与生成树算法，也就不可能有转发状态。

结论三：阻塞接口若无连接存在，则生成树协议不会令其阻塞，它一定是进行冗余备份的线路。所以若阻塞接口的指定网桥非本交换机，其上一定有连接存在。

结论四：对于设备级直连交换机、的两接口、，若，则、通过集线器连接，反之，接口、直连。其中表示交换机通过接口收到数据包的源MAC地址集，表示交换机通过接口收到数据包的源MAC地址集。

结论五：假设交换机接口的地址转发表中仅包含主机设备，若主机数目为1，则该接口与主机直连；若主机数目大于l，则该接口通过集线器连接主机群。

结论六：若交换机接口的地址转发表中无其他交换机的地址信息但包含路由器地址，则该接口与路由器直连。若交换机接口的地址转发表中无其他交换机和路由器的地址信息，则它与转发表中的主机设各级直连，通过结论五进行连接确认。

结论七：若的非根端口的指派网桥为（），且端口的状态是阻塞的，且的非根端口的指派端口与的指派端口相等，那么与直连，且该链路是备份链路。

结论八：满足规则1的2个端口与，不妨假定是根端口，是非根端口，若存在其他端口（）与满足规则1，那么、与之间必定存在集线器或哑交换机等不支持SNMP 的设备。

利用上述的八条结论，可以得出基于STP协议的拓扑发现算法：根据结论一，当发现未知的网桥时，它一定是哑交换机。以根交换机为源地址Ping哑交换机，利用结论二查找拓扑结构生成树的内容，如果其中包含哑交换机的MAC地址，则认为它们之间存在直接相连的关系。其中伪造根交换机为源地址的Ping数据包是为了满足生成树转发下行接口的完备性。STP发现算法利用网络OSI第二层连接信息生成网络拓扑图，按广度优先遍历、先主干后备份的顺序进行，算法流程如图2所示。

详细描述如下：

（1）对网络中所有的设备进行访问，对交换机进行识别并且存入临时链表A中。

（2）将链表A中的所有交换机IP逐个取出来，并通过SNMP协议访问同时记录根网桥MAC地址、本机的根接口、处于转发和阻塞接口的指定网桥MAC及其指定接口。

（3）对网络拓扑生成树进行广度优先遍历。根据STP协议可以得到交换区域的根网桥，而后将根网桥加入到FIFO（先进先出队列）的等待进一步检测的队列B中。

（4）从队列B中取出一个交换机放入链表C中。在临时链表A中找出根接口的指定交换机为的交换机信息逐一添入待检测队列B中。由结论一、三可知它们属于设备级直连，并从临时链表A中去除该交换机信息。

（5）重复4，直到队列B为空。

（6）判断添加交换机连接：查询链表C中每个交换机接口的指定网桥和指定接口，若存在相同的交换机，则说明它们与指定的网桥是相互连接的，但它们是通过集线器等连接设备相连的，否则为设备直连，修改指定网桥的指定接口类型。

（7）若在临时链表A中仍不为空，则说明存在网络中存在哑交换机，如果临时链表A为空，则跳转至10。

（8）在临时链表A中对每个交换机根接口的指定网桥进行查询，若该网桥不存在于临时链表A中，根据结论一，将该网桥加入待检测队列B中。并重复进行4、5、6步骤。

（9）处理哑交换机连接：在链表C中逆序查找除哑交换机自身所在分枝以外其他分枝的交换机接口转发状态，若其状态转发无连接并且其转发地址中包含该哑交换机的MAC地址，则对该接口与哑交换机之间的连接信息进行添加。

（10）处理冗余连接：判断每个交换机的阻塞接口查询它的指定网桥，将连接填入对应的接口信息区。

（11）向全网主机发送广播Ping包，对于处在设备直连状态的两台交换机，对直连两接口的地址转发表进行访问，并且根据结论四改写其接口信息。

（12）根据结论六对主机之间的连接和路由器之间连接进行添加。

STP拓扑发现算法具有以下四个方面的优点：

（1）能够对哑设备存在的情况进行处理。

在STP发现算法中，根据结论六利用交换机接口的指定网桥来发现哑交换机，并且利用了结论一和结论四处理接口连接集线器的情况。

（2）能够发现并对冗余连接进行处理。

在生成树算法中，它以阻塞某些接口来实现无环路转发。在STP发现算法中，通过查找比较接口状态，将那些处于阻塞状态的接口取出，为其与指定网桥添加连接，便能发现冗余连接。

（3）能够对网络拓扑结构的变化进行及时反映。

在运行STP协议的网络中，如果网络物理拓扑发生变化，算法会立即被触发，进而对整个网络的拓扑结构进行重新的绘制，所以在STP发现算法得出的物理拓扑始终是最新最完整的。但在其他算法中，对网络拓扑结构的绘制必须通过报文之间的交流来进行，如果存在两台或者几台设备由于某种原因很久没有发生通信，则会导致此设备不会被发现，网络拓扑结构绘制不完整。

（4）能够对多个子网的复杂环境网络拓扑结构进行有效的发现。

不同子网间的交换机即使直接相连，它们也是通过各自的网关交换信息，但它们必定都遵循生成STP协议以构造无环路交换域，所以利用STP发现算法可以发现这些相对比较复杂连接。

3 基于ICMP协议的网络拓扑发现算法

在ICMP协议中有Ping命令和Traceroute命令，这两种命令可以帮助我们获得网络的拓扑结构。

Ping命令往往用来检测一个节点是不是处在运行的状态或者是检测两个节点之间的时延（RTT）。Ping向所要检测的目的地址发送ICMP echo请求包，等待接收ICMP echo响应包，按照成功的次数及一些其他数据对网络的时延等一些性能进行评估。一般情况下Ping只关心网络上的源节点和目的节点，而不考虑网络的其他细节，同时也可以利用Ping的广播得到整个网络的主机状态。在文献[13]中给出了Ping的三类规则，利用这三类规则可以对某个IP地址所归属的网络或者是IP的有效性进行判断，具体如下：

（1）通过Ping的广播来判定IP地址所属子网。

递减猜测子网掩码的长度，对每个猜测的子网掩码构造广播地址，进行Ping操作，如果主机对构造的广播地址有回应则说明猜测的子网掩码是正确。给定一个IP地址，可利用本规则猜测该地址所属的子网掩码：

for（masklen=31； i> 7 ； i--） {

假定子网掩码的长度是masklen；

为IP地址和masklen构造主机号为全0和全1的直接广播地址；

ping这些广播地址；

如果多于两个主机对这两个ping都做出了响应，则返回masklen，否则继续；

}

（2）通过一组地址来判定该组地址所属子网。

已知地址集A中的IP地址同属于一个子网，对地址集A进行异或操作，找出第一个不为0的位，则该位及其后的各位都只能是主机号，而不可能是子网号。从而判断出子网掩码的长度（可能比实际子网掩码的位数长），而子网地址则可通过猜测得到的子网掩码做按位与运算得出。求取子网掩码的伪代码如下：

（3）判定在某个域中的有效IP地址。

已知一个子网空间的地址集B，推测已知的子网地址空间中有效的IP地址，其算法描述如下：

for（每个ping测试成功的地址）{

把此地址的后续N个地址加入到临时集合中；

if（地址以1，63，129或者193结尾） {

可能有其他的主机在这个空间中，把N个具有相同前缀的随机地址加入到临时集合中；

Traceroute命令可以发现源节点和目的节点之间的路由器。其原理是通过Traceroute命令向目的节点发送端口为65535的UDP报文，它们之间的路由器在转发该数据包之间会将其TTL值减1，如果当TTL值变为了0，则该路由器向源节点发送TTL-Expired ICMP的消息。Traceroute命令就是通过这个特性，将发送包的TTL值不断的增大，这样会使源节点到目的节点间这条路经上所有的路由器均会向源节点发送TTL-Expired ICMP包，这样就将此路径上的所有路由器进行发现。如图3所示，对一个目标设备发送的第一个数据包中TTL值为1，所以此报文在遇到两个节点之间第一个路由器R1时，就会向源节点发送TTL-Expired ICMP包，这样路由器R1就被发现了，R1就成了网络拓扑结构中的一部分。之后就将发送报文的TTL值不断增加1，一直加到发送的报文被目的节点所接收，就可以得到之间所有路由器节点。

通过上述方式我们可以构造出包含节点R1，R2，R3，…，Rn和连接关系（源主机，R1），（R1，R2），（R2，R3），…，（Rn，目标设备）拓扑结构来。由于基本所有的路由器都会向源节点发送TTL-Expired ICMP消息，所以一般情况下，通过Traceroute命令得出来的网络拓扑结构是比较准确的。

通过ICMP中的Ping和Traceroute命令的特性可以实现对网络拓扑结构的发现。

算法的主要步骤如下：

（1）首先在域内随机选取形式为（* .1）的地址同时将它们存在临时地址集A。

（2）然后每次从A中取出一个IP地址a通过步骤3进行判定，直到地址集A中没有IP地址可以取，绘制网络拓扑图。

（3）首先利用Ping命令判断该地址是否为有效地址，如果有效则将该地址存入地址集B中并且根据规则3将更多的地址加入地址集A中。而后有效地址a进一步执行Traceroute命令，会得到与其相连接的所有路由器的信息，然后利用规则2猜测地址a所属的子网地址。

算法流程如图4所示。

4 基于SNMP协议的网络拓扑发现算法

在一般的基于SNMP协议的拓扑发现方法中，网络中的每个设备都有路由表，路由表中的信息包含了网络拓扑结构的信息，路由表包括路由目的网络地址、网络的子网掩码、该路由的下一站IP地址、对应的端口索引和路由协议类型等信息。由于路由表中下一跳的节点一定是具有路由功能的节点，所以就可以在设定路由器开始，依次读取每台路由器的路由表，这样就可以逐个发现每台具有路由功能的节点，进而得出具有路由功能节点的拓扑结构。再根据路由表的本地接口的索引标识项，找到接口表中所对应的本地接口索引，由接口表的接口类型就可以判断其所在子网的类型，最终构建出整个网络的拓扑结构图。这种方法的拓扑发现过程和算法的优点在于其过程简单，运行速度快，发现效率高，对资源消耗比较小，因此，得到了大家的广泛应用。但是，该方法的不足也很明显，主要表现在以下五个方面：

（1）由于只是根据IP地址来发现设备，这样就无法发现网络中没有配置IP的网络设备。

（2）由于目前一个路由器往往具有不止一个IP地址，而此基于路由表的发现方法算法实际上就是基于IP地址的，所以一个具有多个IP地址的路由器会导致一台设备被算法当成了多台设备，与实际情况不符合。

（3）因为要对网络中所有设备进行检测，在网络规模比较大时可能导致算法执行时间较长，同时由于实际网络中情况比较复杂，存在网络时延等情况，可能导致发现的网络拓扑结构不准确。

（4）在路由表中本身存在大量的冗余信息，可能导致网络拓扑结构的不准确。

（5）根据该算法进行拓扑发现需要网络中所有的设备都支持SNMP协议。

因此，该方法一般用于骨干网络拓扑结构的发现，主要对网络的路由节点进行发现，对网络的整体情况进行绘制。可见，无论是基于STP的拓扑发现算法还是本节的拓扑发现算法都各有优缺点和局限性，在实际的应用中要根据具体的情况发挥出算法的功能。

本节在现有基于SNMP算法的基础上研究了一种基于SNMP的网络拓扑发现改进算法，经过实际网络管理系统的验证，能够有效发现管控网络的三级拓扑结构，即：骨干网路由、二级子网和三级子网拓扑结构。

这种算法的基本思想是在网络中路由器之间的链路是由其两端路由器的端口互联构成的，根据TCP/IP的编址原理，链路两端路由器端口的IP地址必然处于同一个子网中。因此，通过一个子网中已知的IP地址和这个IP地址的子网掩码即可计算出该子网中所有其他的IP地址。根据这种思路，从某个节点开始，访问其MIB库，得到该节点所有接口的IP地址和子网掩码，该节点称为种子节点。通过计算得到与每一接口在同一个子网内的其他IP地址。判断这些IP地址是否属于路由器信息，如果是则将此路由器信息记录到待检测路由设备链表，作为下一层发现的种子节点。并同时记录两个路由器问的链路信息到拓扑信息链表。重复以上步骤直到没有种子节点或者达到指定的发现层数，即可完成相应的拓扑发现过程。算法流程如图5所示。

详细描述如下：

（1）根据网络管理系统的IP掩码，使用路由跟踪的方法获取网管终端所在的默认路由器网关地址。访问该路由器获取ipAdderssTable地址表信息，将其编号加入AllRouters队列（元素包括路由器名、接口号、接口IP、接口号和接口IP等，其中接口号与接口IP的多少依据各个不同路由器而不同）和AccessRouters队列（待访问路由器，结构跟AllRouters类似）。

（2）从AccessRoutes取出一个元素设为当前处理的路由器Rx，依次访问Rx的路由表ipRouteTable表项，将目标子网信息编号无重复地放入子网队列Subnets（元素包括子网号，子网地址，掩码等）。

（3）判断路由器与子网连接关系：依次对Rx的ipRouteTable表项检查，如果ipRouteType项不为4，表示相应子网与Rx直接相连，下一跳地址ipNextHopIpAddress项为空。根据Rx的ipAddressTable信息确定Y端口与该子网Z相连接，将连接关系组（Rx，Y，Z）无重复地放入R-1inks-S队列（路由器接口与子网相连的接配对的二元组）。

（4）判断路由器之间的连接关系：如果ipRouteType为4，下一跳ipNextHopIpAddress地址有效，表明另一个路由器与Rx直接相连。根据ipNextHopIpAddress地址信息访问另一个路由器的ipAddressTable，判断AllRouters队列中是否己经存在该路由器信息，如不存在则把该路由器编号加入队列AllRouters和AccessRouters中。很容易确定Rx的Y端口与另一个路由器Ru的V端口直接连接。因此把元素（Rx，Y，Ru，V）无重复地放入队列R-links-R（路由器接口与路由器接口相连的二元组）中。

（5）把队列R-links-R进行去冗处理。因为在以上的算法实现中，有可能存相同的连接信息加入到队列中。例如：R1的2端口与R4的3端口直接相连，在算法实现过程中，可能同时在队列中加入了（R1，2，R4，3）和（R4，3，R1，2）的元素组，虽然它们在形式上不一样，但他们表示同一个连接信息。

（6）把Rx的元素组从AccessRouters中删除，如果AccessRouters不为空，转到（2），如果为空，程序中止。

算法运行结束以后，AllRouters包含了所有活动的路由器，子网队列Subnets包含了所有活动的子网，队列R-links-S和队列R-links-R的信息表示路由器与子网、路由器与路由器之间连接关系，最终可以准确而完整地把拓扑结构绘制出来。

5 结语

该文分析了网络拓扑技术的重要性，介绍了现有各类网络拓扑发现算法，并重点针对其不足进行了分析，根据现有网络拓扑发现算法的不足，根据实际，选取STP、SNMP和ICMP三个常用协议做为基础，提出了基于这三种常见协议的网络拓扑发现算法，同时提出了一种基于SNMP协议的拓扑发现改进算法，更好的解决了网络拓扑发现比较难以有效解决的问题。

参考文献

[1] K.C.Claffy D.McRobb.Measurement and Visualization of Internet Connectivity and Performance[EB/OL]. http：///Tools/Skitter， 2001.

[2] 郑海，张国清.物理网络拓扑发现算法的研究[J].计算机研究与发展，2002， 39（3）：264-268.

[3] 张国强，张国清，李仰耀.物理网络拓扑发现算法的研究和系统实现[J].小型微型计算机系统，2006，27（1）：12-16.

[4] 邱林，张建忠，吴功宜.基于端口流量的物理网络拓扑发现方法研究[J].计算机工程与应用，2002，38（22）：171-172.

[5] 陈艳秋，宋银濒，刁成嘉.利用端口流量分析解决物理网络拓扑发现问题[J].计算机工程与应用，2007，43（5）：150-152.

[6] Gobjuka.H， Breitbart.Y.Ethernet Topology Discovery for Networks with Incomplete Information[J]. IEEE INFOCOM，2007（8）：631-638.

[7] Uzair.U，Ahmad.HF，AIi.A，Suguri.H.An Efficient Algorithm for Ethernet Topology Discovery inLarge Multi-subnet Networks[J]. IEEE INFOCOM， 2007（4）：1-7.

[8] Farkas J，de Oliveira V.G， Salvador M.R， dos Santos G.C. Automatic Discovery of Physical Topology in Ethernet Networks [J].IEEE INFOCOM，2008，3：848-854.

[9] 曲朝阳，胡绪超.基于SNMP的网络拓扑发现与拓扑生成树的绘制[J].网络安全技术与应用，2007（3）：23-27.

[10] J Case，M Fedor，M Schoffstall.Simple Network Management Protocal [S].RFC1157，1999.

[11] 石玫.网络拓扑自主发现[D].中国人民信息工程大学，2007.

网络拓扑结构篇7

关键词:大规模IP网络;拓扑发现;SNMP

一、网络拓扑发现概述

(一)网络拓扑发现的概念

网络拓扑是指网络元素及其之间的连接关系。这里所讲的网络元素，既可以是路由器，也可以是交换机、网桥等，还可以是客户端、服务器，甚至是子网、AS等。这里所讲的网络，既可以指局域网，也可以是互联网，也可以是互联网的一部分。而网络拓扑发现，就是指发现并确定网络元素及其之间的连接关系。

(二)互联网的拓扑结构抽象

网络技术发展到今天，除非为某种特殊应用而专门设计的局部网络，以太网( Ethemet)已经成为事实上通用的网络组网方式，TCP/IP协议簇已经成为事实上的网络通讯协议标准。从概念上说，互联网可以看作是一个个小的局域网络通过互联(互连)而成的。但一方面，组成互联网基础的各个局域网络的拓扑结构本身可能很不相同，另一方面，各个局域网络的之间的互联(互连)关系也千差万别。因此，互联网的拓扑结构不可能用局域网三种基本的网络拓扑结构进行抽象。

二、网络拓扑发现的分类

(一)按照网络拓扑发现的对象进行分类

按照对象的不同对网络拓扑发现进行分类，可分为面向域内的网络拓扑发现和跨域的网络拓扑发现。

面向域内的拓扑发现，是指面向同一AS或者同一ISP、甚至更小规模的局部网络的拓扑发现技术。跨域的网络拓扑发现则是指面向不同AS(或ISP)网络的拓扑发现技术。二者的不同主要在于，面向域内的拓扑发现网络管理员一般具有对网络元素的管理和控制权，而跨域的拓扑发现网络管理员一般无法对域外的网络元素进行管理和控制。由于探测的对象不同，因此所适用的网络发现方法以及网络拓扑发现的目的等均有很大的不同。由于网络管理员不能对网络元素进行管理和控制，因此在一般情况下，跨域的网络拓扑发现比域内的网络拓扑发现困难得多。

(二)按照网络拓扑发现的方法进行分类

按照发现方法对网络拓扑发现进行分类，可分为主动式网络拓扑发现和被动式网络拓扑发现。

所谓主动式的网络拓扑发现，是指将一组精心设计的数据报注入被探测的网络，通过对网络反馈信息进行分析，得到网络的拓扑连接情况。例如，各种基于Traceroute的网络拓扑发现方法，就是典型的主动式网络拓扑发现。基于SNMP的网络拓扑发现，从原理上也应该归类为主动式的网络拓扑发现方法。由于主动式网络拓扑发现可以根据探测需要，由探测发起者对探测数据报进行专门设计，因此适用情形较广，可以探测网络范围可以很大，并且可通过提高注入数据包的科学性和合理性，不断提高网络拓扑探测的准确度。主动式网络拓扑探测的缺点主要是探测数据报将增大网络的负荷。在大规模多点探测中，甚至有可能导致网络性能的严重降低。在极端的情况下，由于注入数据报严重改变了网络负荷，甚至使探测到的网络拓扑与实际情况不相符。

而被动式的网络拓扑发现，则是指对网络元素间的数据进行侦听，通过对侦听得到的数据进行分析，进而得出网络的拓扑连接情况。例如，通过侦听路由器间的OSPF交换数据包来探测网络拓扑的方法，就是一种被动式的拓扑发现方法。被动式的网络拓扑发现方法不向网络注入数据包，因此对网络负荷的影响较小。但由于被侦听的只是局部网络，因此往往通过分析也只能得到局部网络的拓扑情况。另外，侦听得到的数据可能存在很多不真实的数据，如不能对数据进行有效的分析处理，有可能得到不真实的网络拓扑图。

(三)按照网络拓扑发现的粒度分类

根据粒度的不同，网络网拓扑发现大致可以分为粗粒度、中间粒度、细粒度三个级别。

粗粒度是一般指AS级别的拓扑发现。在粗粒度的拓扑图中，节点代表一个域，而边则代表域间的连接。中间粒度是指集群(路由器集簇)间的拓扑发现。在中间粒度的拓扑图中，节点代表单路由器或主机的特定集群，边则代表路由器或集群主机之间的连接。细粒度是指路由器级的拓扑发现。在细粒度的拓扑图中，节点代表路由器(子网或主机)，边代表路由器的连结。目前，面向Internet的拓扑发现的研究主要集中在AS级和路由器级两个方面。

三、基于SNMP的网络拓扑发现分析

(一)SNMP协议简介

SNMP C Simple Network Management Protocol)即简单网络管理协议，目前有SNMPvI、SNMPv2两个版本。SNMPvl于1990年开始，其规范文为RFC1157等。SNMPv2于1993年开始，RFC1441对SNMPv2进行了系统地介绍。目前，最新版本SNMPv3的规范文本为RFC2571。SNMP采用“管理者一”的模式，实现对网络设备的监视和控制。采用“轮询”与“陷阱”两种方式，实现管理进程与进程之间的信息交互，共定义了基本的5种报文:get-request操作:从进程处提取一个或多个参数值;get-next-request操作;从进程处提取一个或多个参数的下一个参数值;set-request操作:设置进程的一个或多个参数值;get-response操作:返回的一个或多个参数值。这个操作是由进程发出的。它是前面3种操作的响应操作;trap操作:进程主动发出的报文，通知管理进程有某些事情发生。

SNMP是一个应用层协议，尽管可以在传输层采用各种各样的协议，但是在SNMP中，用得最多的传输层协议还是UDP。另外，为了实现对网络的管理，SNMP又对其它两个必需的部分进行了定义。一个是管理信息库MIB(Management Information Base)，管理信息库包含所有进程的所有可被查询和修改的参数。RFC1213定义了第二版的MIB，叫做MIB-II。另外一部分是关于MIB的一套公用的结构和表示符号，叫做管理信息结构SIB( Structure of Management Information)，由RFC1155定义。

(二)基于SNMP的网络拓扑发现的基本原理

所有的网络设备维护一个MIB(管理信息库)，保存该设备上与网络运行相关的全部信息，并对管理工作站的SMMP查询进行响应。管理工作站通过发送请求信息，查询储存于网络路由设备中的管理信息库MIB中的相关信息，从中解析出网络拓扑相关的信息，就可以构画出整个网络的拓扑结构。从原理上看，基于SNMP的网络拓扑发现类似于图的广度优先搜索。

MIB中的路由表ipRouteTable定义了该设备的路由信息，其中与拓扑发现相关的表项有:ipRouteDest、ipRouteMask、ipRoutelf Index， ipRouteNextHop、ipRouteType等。ipRouteDest记录以该设备为起点可以到达的目的地址范围，ipRouteMask记录的是目的网络的子网掩码，ipRouteIf Index记录ipRouteDest所对应的接口索引号，ipRouteNextHop记录本接口所对应的下一跳网关地址或者直连子网的网关地址，ipRoute升pe记录ipRouteNextHop所表示的地址与该设备的连接关系。

(三)基于SNMP的网络拓扑发现的优缺点及适用范围

基于srrnrn的网络拓扑发现的优点是发现过程和算法简单，目标明确，发现效率高，系统和网络开销小。由于入nB的信息可以自动随着网络的状况更新，这样通过srrNrn获取的拓扑信息就总是反映网络最新的状况。另外，此方法除了可以实现网络层拓扑探测外，经过对入心B数据进行精心分析，还可以实现对链路层的拓扑发现。基于SNMP的网络拓扑发现的主要缺点是方法受到路由设备访问权限的限制。随着网络安全问题越来越受的人们的重视，因此采用此方法开展跨管理域的网络拓扑发现变得越来越困难。另外，除了标准的MIB信息外，有的厂家为自己的设备开发了专门的MIB，如果在拓扑自动发现程序中使用了这些MIB，其处理上就需要随厂家的不同而作特殊的处理。

参考文献

[1] 熊英，基于TCP/IP的网络拓扑发现方法的研究.湖北工业大学学报.2005

网络拓扑结构篇8

（郑州工业应用技术学院 信息工程学院，河南 新郑 451100）

摘 要：近年来，我国的计算机技术和互联网技术得到了飞速发展，同时对网络理论不断深入的研究工作，也大力推动着网络产业中建立在计算机网络拓扑基础之上的铺设技术使用价值的提升，方法模式的构建工作也取得了极大的改进，无论是在设备、技术还是思维方面，在计算机方法模式的帮助下都正在迅速的普及与推广.除了让当前的整体计算机网络架构结构保持持续性的优化与完善并让计算机用户的体验感得到稳步提升之外，拓扑技术在复杂网络理论的帮助下正在与网络实体收益之间建立起了良好的互动关系.

http://

关键词 ：网络理论；计算机网络；拓扑研究

中图分类号：TP393 文献标识码：A 文章编号：1673-260X（2015）01-0027-02

互联网用户的增长越发呈现出井喷趋势，然而以往有限的网络资源无法满足不断增长的互联网用户的需求，不仅如此，计算机网络技术拓扑作为运用最为广泛的网络基础架设构筑层面上的技术，还需要同时面对用户上网体验度差、过度负载的网络数据传输压力以及节点数据包等一系列问题的威胁，长此以往将会影响到计算机网络系统的有序运营.因此需要对网络拓扑技术相关的网络理论进行迅速的转换，让它们能够为计算机网络拓扑的发展提供良好的理论基础与技术支持.

1 当前复杂网络理论构筑的内涵与架构特征

1.1 当前复杂网络的内涵属性

在计算机领域，复杂网络是一个专有的术语，它特有的内涵指的是包含部分或全部的以下相对抽象的五个属性特征的网络构架，这五个属性特征分别为自组织、自相似、吸引子、无标度以及小世界.而网络系统模型和网络系统是构筑复杂网络理论的最为重要的组成部分，其中包括了网络系统模型中的结构稳定性、集合属性、形成机制和网络系统中的演化动力学、释放的演变规律以及演化的进阶这几个部分.在深入探究分析复杂网络理论的构筑过程中，幂律的度值、集团性和小世界是核心的三大研究要点.

1.2 复杂网络的架构特征

对于三大关键要点幂律的度值、集团性和小世界而言，小世界是一种概念的表述，而这一概念表述的对象正式抽象化的网络系统内的计算机，小世界的这一特性是通过交互连接无数各类相互联系的空间概念内的节点得以实现的，而复杂网络正是建立在由小世界构建出的基本单元之上.简而言之，借用小世界的单元进行基础元件的组建，然后相互连接各任意小世界单元的节点，复杂网络中数据信息流通依赖的网络纹线的路径通道正是这样形成的.

交互连接是集团性的发展走向.复杂网络是一个集合体，它混合了视域空间内部的各类子系统和小世界，相关子系统的集团性也包括在内.无论是复杂网络整体结构的再塑性还是兼容性，恰恰是网络内部各种单元个体之间的相互联系与交互作用下，能够让内容得到不断细化、功能得到大范围的拓展的.

视域是幂律的度值的涵盖内容，近年来逐渐呈现出多元化趋势.在复杂的网络系统中，节点和与节点相关的单位数量被称为度，作为主要概念名词的度所具备的是和存在于其他网络中单位小世界的同一级别的度发集团交互性.小世界的子系统中，度的具体体现是节数.节数在复杂网络系统中代表的是通过某一节点的各类路径中最短的一个的幂律的数量，相关节点的影响力正是通过节数得以表现的，不仅如此，在复杂网络中幂律度值的交互作用中，节数还扮演着数据包的角色.

2 计算机网络拓扑模型的主要特征和基本现状

2.1 计算机拓扑模型的主要特征

在复杂网络的众多具体表现形式中，计算机网络的主要载体是计算机群组.在对拓扑进行不断优化的过程中，其主要目标是最小化网络边数、让各个节点之间的平均距离得到最大限度的缩小，复杂网络的小世界网络构架为计算机网络系统将来的日趋复杂的发展趋势奠定了基础.鉴于计算机网络极其广阔的覆盖空间，要想保持计算机网络系统的高效稳定工作，则务必要对建立在复杂网络理论基础之上的网络拓扑技术进行迅速的转换适配与理论支持.在复杂网络的高聚集、边数少、小世界的特性的帮助下，计算机网络无论是在生长延伸还是优先连接上都获得了优势的规律性.其中，优先连接规律能够让计算机网络获得新的进入计算机网络规则创设的节点，同时优先连接那些连接数较大的节点，保证网络宽带资源的最大限度节约.

2.2 计算机拓扑模型适配构筑的基本现状

当前计算机网路拓扑理论应用逐步向着人性化、开放化的UI操作界面发展.互联网的高速普及，使得人们对快速上网业务以及网络数据传输速度的依赖性出现前所未有的爆棚式增长，人网一体的交互式体验成为了用户们关注的重点内容，为了满足当前用户的上网需求，与网络数据业务相关的服务正努力想向着高效性、贴心性和细节化发展，这一切都使得基于复杂网络理论的计算机网络拓扑技术面临着前所未有的挑战，它们要求拓扑技术能够以更高的效率满足现阶段计算机网络的发展需求.

除此之外，网络体验反馈的集约化和智能化也是是计算机拓扑模型适配构筑的基本现状之一.在层出不穷的计算机技术的推动下，专业化、复杂化成为了计算机网络拓扑理论应用的发展新趋势，这也要求计算机网络拓扑从业人员能够不断提高实际操作能力和专业水平.人工职能拓扑技术正是在这种大背景环境下诞生的，在它的辅助帮助下，计算机的网络网络修护和故障诊断效率得到了大幅度的提升，从而进一步促进了计算机网络技术的成本投入的降低，有效延伸了复杂网络中集团性的实践.

最后，网络应用管理集体生命维持是借助于计算机拓扑网络系统安全化的安全性和普及度上得以实现的，因此近年来网络技术研究的热点和重点内容都集中在建立在安全性基础之上的理论研究和开发应用上.当前IP城域网构筑架设的发展趋势之所以是SNMP协议，是由SNMP协议的众多优势决定的，诸如稳定性、高效性、及时性和廉价性等.尽管SNMPV1和SNMPV2是当前运用最为普遍的协议，但仍旧无法回避的是它们较差的可控性.因此，除了SNMP协议之外，人们在网页的基础上逐渐开发出了具备高度兼容性、友好性、移动性的软件系统，这类软件系统除了上述特性外，还具备高度统一性同时平台操作也更为便捷，自诞生之初，它便成为人们提供了另一个全新的嵌入式计算机拓扑网络技术平台.

3 计算机网络拓扑更新架设的途径步骤

在当前复杂网络的发展趋势推动下，计算机网络的拓扑建建模逐步转向优先连接和生长拓展这两大原则性网络拓扑规律.让适配语计算机网络拓扑性质的建模能够更加直接迅速的演化目的促使了优先连接和生长拓展这两个基本原则的诞生，不过就目前而言，建立在复杂网络基础之上的路由器级和自治域级是对计算机网路模型进行构件的主要方法手段.由于无论是在不一样的构架，还是不一样的规模，亦或不一样的层次下，计算机网络的拓扑特性的集团性在复杂网络下都呈现出高度的相似性，创设的计算机网络拓扑模型的适配网络延伸通常都在两个级别以上.

3.1 计算机拓扑网络细化改进的理论分析

第一步要做的是在计算机复杂网络中，假设有无数个各种各样的节点密密麻麻分布在这个模型系统中，为了连接网络中的各个节点，还需要假设一个时钟模块，它不仅能够保持均匀的速度进行运转，还具备离散特性.对于所有的节点而言，它们都是按照特定的时间轴进入网络系统模型的，也就是说这些节点进入系统的实际将呈现出在零点到某一特定的时间点的时间段内的随机分布状态.

一旦当节点进入系统之后，它们便要开始与信息源不断地进行信息的接收与发送，还需要根据接收到的信息源的信息进行及时的内容分析并迅速做出反馈，无论是传送消息的范围领域还是节点自身的重要程度都是节点发送和接收的信息应该包含的内容.在实际接收信息源发来的信息过程中，节点会根据信息源的重要性排名，决定要不要连接发送消息的节点，在节点的选择上，接收消息的节点往往会在相近有限度的信息源节点中进行随机选择，然后尝试着建立连接关系.

节点在计算机网络的初试阶段中，只有很少的一部分能够开展有效的活动.由于各个节点之间的度值都具有高度相似性，从而制约到了整个网络系统能够接收到的消息范围.而在网络系统随后的不断发展过程中，节点之间的信息接收范围也会随着节点度的增加的得到大幅提升，为了有效释放各个节点内部的数据源信息，节点会在系统内部进行高效的交互行为，在小世界范围区域内获胜的节点会在周边区域内建立起更大范围的象征性小世界，长此以往，最终只会剩下若干个大规模的聚集中心，并在计算机网络系统中形成结构稳固严密的计算机网络拓扑模型.

3.2 通过全新前沿技术更新延伸拓扑网络

当前最为有效的网络应用架设方法便是B/S网络管理结构和CORBA技术.其中，CORBA网络管理系统是二次构造后的CLIENT/SERVER架构，包含了提供网络服务的服务方和客户方，由于常常要借助于网关的转换进行网络管理信息的获取工作，它们经常被党所CORBA的抽象概念.B/S网络管理结构最出色指出在于简单便捷的运行维护，它能够任意介入IP城域网网络，因此可以让上网速度和及时体验得到大幅度改善，避免计算机拓扑网络面临的海量用户带来的巨大负载运行压力.

4 总结

综上所述，在整个网络系统中，基于复杂网络的计算机网络拓扑技术肩负着调节优化的重要责任，从而为网络系统的运作水平和用户体验的提升奠定良好基础，进而推动计算机领域开展更为深层次的拓扑理论构件的延伸和拓展，全面提升网络产业的市场竞争力，保障网络产业实际收益与用户体验消费的双丰收.

——————————

http://

参考文献：

〔1〕郭海鸥,李静.基于复杂网络理论的互联网病毒传播的控制技术分析[J].河南教育学院学报(自然科学版)，2010（2）：165-168.

〔2〕赵建新.复杂网络理论及其在计算机拓扑行为中的应用[J].计算机光盘软件与应用，2012（9）：46-52.

〔3〕季小芳,庄天舒.基于复杂网络理论的Internet拓扑节点特征分析[J].长春大学学报，2012（9）：46-48.

〔4〕李玲.基于复杂网络理论的计算机网络拓扑研究[J].电子技术与软件工程，2013（2）：16-17.

〔5〕雷霆,余镇危.基于复杂网络理论的计算机网络拓扑研究[J].计算机工程与应用，2013（8）：36-39.

〔6〕王翠莲.基于复杂网络理论的计算机网络拓扑研究[J].信息与电脑(理论版)，2013，09（10）：34-35.

〔7〕黄胜,陈臻.基于复杂网络理论的计算机网络拓扑研究[J].电脑知识与技术，2012，09（17）：62-63.

网络拓扑结构篇9

关键词:拓扑结构;总线型;环型;星型;访问控制方式

对于学习过一些计算机知识的人来说,“拓扑”这个词应该不算陌生,对于常见的三种标准的拓扑结构――总线型、星型和环型也都会有所了解。“拓扑(Topology)是几何学和图论中的基本概念,用于描述点、线、面之间的几何关系;计算机网络技术中借用拓扑的概念来描述节点之间的相互关系,从而确定节点在网络中的确切位置以及它与网络中其他节点之间的相对关系。”[1]大多数人对三种标准拓扑结构的认识都是从它们的物理布局开始的。正如名称表示的那样,总线型是网络的所有计算机都通过一条电缆线互相连接起来;环型是每台计算机都与相邻的两台计算机相连,构成一个封闭的环状;而星型是计算机通过各自的一条电缆与一台中央集线器相连。

但学习网络的拓扑结构不仅仅要明确它们的物理布局和简单记忆各自的优缺点,更主要的是了解各种拓扑结构中数据流动的方式。通过对各种拓扑结构中访问控制方式的深入认识,加强各类型的对比,从而进一步体会各种网络拓扑结构的优缺点。

下面是总线型、星型、环型三种标准拓扑结构中访问控制方式的相关内容以及自己的一些理解和看法。

1总线型

总线型拓扑结构也称点对点的拓扑结构,原因就是网络中的每台计算机均可以接收从某一节点传送到另一节点的数据。看似简单的数据传输方式却有许多值得思考的地方,例如某一时刻在共用的信道上,可以同时发送几个电子信号;如果某一时刻只能发送一个电子信号,那么怎样决定发送权等等。

总线型网络只有一条主电缆,该电缆仅能支持一个信道,所有计算机共享总线的全部容量。故而在某一时刻,只能有一台计算机发送电子信号。同时电缆线上的其他计算机均在监听传送中的信号,但只有那个地址与信号地址相匹配的计算机才能接收电缆上的信号,而具有其他地址的计算机对此信号不做反应。

总线型拓扑结构的网络一般采用分布式媒体访问控制方法。传统的总线型网络采取竞争的方式获得发送权,还有一种总线型网络在物理连接上是总线拓扑结构,而在逻辑结构上则采用令牌环。“‘令牌’是一种控制标志,由“空闲”与“忙”两种编码标志来实现。“‘逻辑结构采用令牌环’的实现是总线型网络中的各个工作站按一定顺序,如按接口地址大小,排列形成一个逻辑环。”[2]只有令牌持有者才能控制总线,才有发送信息的权力。总线网中令牌的传递与环型网中令牌的传递相似,但由于是逻辑成环,所以控制电路对于真正的环型网络稍显复杂。

总线网结构简单、布线容易、可靠性较高,易于扩充,但若主干电缆某处发生故障,整个网络将瘫痪,且发生故障时不易判断故障点。

2环型

环型拓扑中网络的所有节点都连接在一条首尾相接的封闭式通信线路上,整个网络既没有起点,也没有终点。在了解了总线型拓扑结构之后,我们不难想到环型拓扑就是把总线型拓扑中的首尾两节点连接在起来。

与总线型相同,环型网络在任一时刻最多也只能有一台计算机发送数据,并且也采用分布式媒体访问控制方法。环型网络中的“令牌机制”使每个节点获得数据发送权的机会均等。令牌处于空闲状态时沿着环型网络不停的循环传递。当一台计算机需要发送数据时,其本身的系统就会允许它在访问网络之前等待令牌的到来,一旦它截取令牌,该计算机就控制了整个网络。此时该计算机就会把令牌转换成一个数据帧,该帧被网上的计算机依次验证,直至达到目标计算机。目标计算机应答后会发送一个新的空的令牌,供其他需发送信息的计算机使用,进行新一轮的发送。[3]

环型网络控制简单、信道利用率高、通信电缆长度短,缺点是扩展潜力有限,以及同总线网相似的,任何一个节点发生故障都可能导致整个网络不能正常工作,且寻找故障点比较困难。

3星型

有人将星型拓扑结构形象地将比喻为一个由车轴和辐条所组成的车轮,车轴部分就是中央集线器hub。由此可以看出,星型拓扑结构的网络属于集中控制型网络,整个网络由中心节点执行集中式通行控制管理,各节点间的通信都要通过中心节点。因此,星形网采用集中式媒体访问控制方法。

星型拓扑也是通过竞争方式获得发送权。只是每一个要发送数据的节点都将要发送的数据发送中心节点,再由中心节点负责将数据送到目的节点。因此,中心节点相当复杂,而各个节点的通信处理负担都很小,只需要满足链路的简单通信要求。中央节点有三项主要功能:“当要求通信的站点发出通讯请求后,控制器要检查中央转接站是否有空闲的通路,被叫设备是否空闲,从而决定是否能建立双方的物理连接;在两台设备通信过程中要维持这一通路;当通信完成或者不成功要求拆线时,中央转接站应能拆除上述通道”。[4]

星型网络结构简单、容易实现、便于管理、连接点的故障容易监测和排除。但不难看出,中心结点是全网络的瓶颈,中心结点出现故障会导致整个网络的瘫痪。

参考文献:

[1] 倪玉兴.计算机网络技术基础第二章课件.2007

[2] 数字电视原理与实现

网络拓扑结构篇10

关键词：无线传感器网络；ZigBee；拓扑结构；监控与维护

中图分类号：TP393 文献标识码：A 文章编号：2095-1302(2012)04-0032-06

Topology monitoring and maintaining method for wireless sensor network

YU Xue-ting, CHEN Lan, LI Ying

( Institute of Microelectronics of Chinese Academy of Scieneces, Beijing 100029, China)

Abstract: This paper proposes a new wireless sensor network topology monitoring and maintenance methods based on ZigBee stack. An innovative scheme to monitor the network topology is designed in order to get a node's joining or losting information with the protocol stack’s own process, which uses leaf nodes' communication. The paper also designs a chain storage structure based on the associated list for maintaining dynamic network topology. Experiment on the actual office environment monitoring platform shows that the method costs small amount of data transfer, consumes little resources with easy operation, which is valuable to apply.

Key Words: Wireless Sensor Network; ZigBee; Topology; Monitoring and Maintenance

0 引 言

随着无线传感器网络技术在军事、工农业、城市管理、环境监控等各个领域的快速发展，作为系统基础组成部分的网络拓扑结构成为研究的一个重要方面。目前，国内外的科研机构在网络拓扑发现以及拓扑的监控和管理方面开展了大量的相关研究工作，但大多停留在理论和仿真层面，这些通过在高性能的PC机上搭建仿真模型来验证算法效果的研究，大多缺乏能够应用到实际系统的可行性案例。安徽财经大学的赵涛[1]，根据在聚合节点（sink）收集到网络内部节点报文接收或丢失的情况，通过发现网络中所有叶子节点到sink 节点的数据传输路径，来推测网络的逻辑拓扑。该方法计算比较复杂，120节点规模网络在主频为2.8 GHz的CPU主机上运行尚需9秒的时间，同时会受到节点资源、计算速度、实施条件等限制，因此，这种方法很难在实际应用中实现。德州仪器(TI)公司的官方网站也给出了一种获取网络拓扑结构的方法[2]，该方法采用发送网络发现命令的方式，并通过返回结果来确定网络拓扑结构。此法虽然能够在实际应用中实施，但需要定期向网络中的所有节点发送发现命令，因而数据消耗量巨大。

本文以Z-stack协议栈为基础，采用叶子节点通讯方式，并利用协议自身的运行流程，提出了一种轻量数据消耗、真正面向应用的拓扑监控方案，同时通过设计一种基于关联表的链式存储结构来实现对网络拓扑信息的维护，因而在解决网络监控与维护方面更具有实际应用价值。

1 Z-stack协议栈原理简介

作为ZigBee联盟的一个重要的组织成员，2007年，TI公司宣布推出业界领先的ZigBee协议栈Z-Stack。Z-Stack符合ZigBee 2006规范，能支持多种平台，其中包括本系统使用的、面向IEEE 802.15.4/ZigBee的CC2430片上系统解决方案[3]。

1.1 ZigBee协议栈的体系结构及信息传递流程

ZigBee协议栈的体系结构如图1所示，由图可见，ZigBee协议采用分层体系结构[3]，由物理层(PHY)、介质接入控制子层（MAC层）、网络层(NWK)和应用层(APL)组成。其中，应用层框架包括了应用支持子层(APS)、ZigBee设备对象(ZDO)及由制造商制定的应用对象。

在ZigBee网络中，信息或数据的传递将依照上述层次结构实现。上层发送的数据或指令按照应用层―网络层―MAC层―物理层的顺序，从上至下依次进行处理；底层返回的数据则按照物理层―MAC层―网络层―应用层的顺序，从下至上处理后返回给上层用户。每个层次负责发送到本层数据的分析和判断，并对于属于本层次的数据或指令做出相应的动作响应；对于不属于本层的数据，则按照规定格式打包后发送给上、下一层。

1.2 节点加入与失步流程

为了维护系统的正常运行，ZigBee协议栈还提供了一些必须的消息响应流程，其中包括节点加入网络和失步响应的流程。

节点加入流程[3]如图2所示。当子节点申请加入网络时，会启动加入流程。子节点的加入请求通过其NWK层、MAC层、PHY层传递给父节点；父节点收到加入通知消息后，又通过其PHY层、MAC层、NWK层将该情况上传给应用层，最后通过ZDO_JoinIndicationCB()函数的调用，得到子节点加入的消息。

图2 节点加入流程

节点失步流程[3]是指终端节点丢失其父节点的同步信号时，向上层报告的失步情况发生的流程。其具体流程如图3所示。

终端节点每隔一段时间就会开启与父节点的同步，当在设定时间内没有接收到父节点的同步信号时，就会产生失步指示信息，协议栈将该失步信息层层上传，最后通过调用ZDO_SyncIndicationCB()函数，将信息传达到应用层。

1.3 关联表

TI的Z-stack协议栈在全功能节点中可以维护associated

_devices_t结构的关联表，关联表中保存有与本节点直接关联（父子节点）的相关信息，包括关联节点的短地址、设备类型、连接状态等，基本上可以满足网络拓扑结构监控和维护的信息需求。

TI的ZigBee协议栈虽然可为用户开发提供强大支持，但是在网络监控和维护上并没有专用的接口。一方面，该协议栈只能发现节点加入网络，但是无法发现节点非主动性的丢失或退出，因而不具备网络拓扑监控的功能；另一方面，协议在每个全功能节点中都维护了与之关联设备的关联表，但是并没有维护整体网络的关联信息，因而无法掌控网络拓扑的全貌。鉴于协议栈在网络拓扑功能上的不足和缺陷，本文以协议基本流程为基础，提出一种实现整体网络拓扑监控和维护的方法，该方法可以满足一般系统对于拓扑结构的监控和维护需求。

2 网络拓扑结构监控

网络拓扑结构监控的主要目的是实现拓扑结构的建立和在结构发生变化时及时获取变化情况，其中最主要的是实现节点加入和退出事件的捕捉。节点加入事件的获取相对容易，可以通过加入节点主动上报等方式来获取；而节点丢失事件获取要复杂得多。现阶段，对节点丢失情况的监控多采用系统定期查询的手段[2]。采用查询方法时，其实时性与查询周期的长短直接相关：查询周期设置较长，拓扑变化反映时间增长，实时性变差；而查询周期设置较短，则传输数据量增大，占用系统资源，往往很难在二者之间找到平衡点。协议栈中数据或消息的传递是一个复杂的过程，为了尽可能地降低系统资源的占用、节约能耗，除了维护系统正常运行所必须的数据通讯外，还应尽量减少人为添加（应用层）的数据通讯量。因此，最好的办法就是利用协议自身的数据传递或者节点加入、失步等流程来实现相关信息的获取。

本文设计了一种基于网关――叶子节点通讯的节点丢失情况获取方法，该方法可以利用协议栈自身的运行流程，以较少的数据通讯量和简单的操作，实现网络中所有节点的丢失情况获取。

2.1节点加入事件的获取

通常情况下，节点加入事件多采用加入节点主动上报的方法来获取。该方法操作简单，但是需要人为地发送相关加入信息，会增加系统数据通讯量。由图2所示的节点加入流程可知，如果有子节点加入网络，加入的指示信息都会通过ZDO_JoinIndicationCB()函数的调用报告给父节点。即该函数的调用证明有子节点的加入事件。因此，本文通过在此函数中添加向应用程序报告的功能，即可通知用户子节点加入事件的发生。

2.2节点丢失信息的获取

由图3所示的流程可知，协议栈通过调用void ZDO_SyncIndicationCB( byte type, uint16 shortAddr )函数可实现失步情况的报告。该函数具有节点丢失的指示功能，并能够指示丢失节点与本节点的父子关系和短地址等。但在实际的应用中发现，该函数的调用是有条件限制的，具体实施条件如下：

父节点丢失：从失步报告流程可知，终端节点能够自动轮询发现其父节点同步信号的丢失，而无需人为添加任何触发条件，引发函数调用。但路由节点不支持与父节点的轮询机制，因而不能产生父节点丢失情况的报告。

子节点丢失：对于包括终端节点在内的所有类型节点的子节点丢失，在未加相应处理的情况下，协议栈都不会引发该函数的调用。

由实施条件可知，该函数的丢失指示并不适用于所有类型节点的丢失情况，因此，如果要得到除终端父节点外网络中所有节点的丢失情况，就需要人为加入其他处理，以触发ZDO_SyncIndicationCB()函数的调用，从而实现丢失事件的获取。

2.3 叶子节点通讯触发方法

通常采用的基于查询的网络发现机制都需要在所有节点间发送数据，因而增大系统的数据开销。这里以图4所示的拓扑结构为例，图中的叶子通讯需要进行14条数据的查询和14条数据的应答才能够完成一次节点丢失情况的获取。为了尽可能减少数据通讯和操作的复杂度，本文设计了一种基于网关――叶子节点通讯的节点丢失情况获取方法，以便用较少的数据通讯量和简单的操作来实现网络中所有节点的丢失情况获取。

研究发现，失步函数的触发可以通过加入数据通讯来实现。因为在数据发送的过程中，协议栈会开启数据发送流程，数据发送后则会自动检测接收方应答帧。这样，如果节点丢失，则发送节点无法接收到有效应答，进而引发节点失步指示函数的触发。

具体触发时，如果节点之间有数据通讯，发送数据节点则能够发现接收数据节点的丢失，从而引发void ZDO_SyncIndicationCB( byte type, uint16 shortAddr )函数的调用。

在同一条数据通路上的节点进行数据转发时，数据传递路径上的各个节点都会发现其父节点（数据由下而上）或者子节点（数据由上而下）的丢失，进而调用void ZDO_SyncIndicationCB( byte type, uint16 shortAddr )函数。如图4所示，如果网关发送数据到终端节点1，则在网关到终端节点1数据路径上的所有节点（网关、路由1、路由2、终端1）都能够发现其子节点的丢失；终端节点1发送数据到网关，则路径1上的所有节点都能发现其父节点的丢失。

该方法通过建立数据通路上起始节点和末端节点的数据通讯来实现整条路径上节点丢失情况的获取。其具体操作过程分为两个部分：其一是父节点丢失情况的获取。由前面提到的实施条件可知，终端节点无需任何人为操作就能够发现其父节点的丢失，而无需对此部分做特殊处理，因而只需对路由节点做出处理。而由路由叶子节点（如图4中路由节点2、4）向网关发送数据时，则可实现整条路径上所有节点丢失情况的获取。其二是子节点丢失情况的获取。子节点丢失的获取可以通过网关向叶子节点（图4中所有终端节点和路由4）发送数据的方法来覆盖整个网络中的所有节点，从而使全部节点都能够发现其子节点的丢失情况。

人为加入上述两部分数据通讯后，只要整个网络中有节点丢失，该丢失节点的父节点和子节点都会产生失步函数void ZDO_SyncIndicationCB( byte type, uint16 shortAddr )的调用，这样就可以简单地在该函数中添加向上层应用报告的功能，实现网络中节点丢失信息获取。并且数据通讯量由原来的28条减少到6条，从而大大减少了数据消耗和由此带来的系统资源占用。

3 网络拓扑结构与维护

Z-stack协议栈在全功能节点中只维护与本节点直接关联的节点信息的关联表，没有整体网络信息的存储功能。为了解决Z-stack关于网络全貌信息缺失的缺陷，结合本文提出的网络拓扑结构监控方法，设计一种拓扑结构维护的方法，在占用少量资源的情况下获取整个网络的拓扑信息，并将信息整合到网关节点中统一维护和管理，从而建立网络拓扑的管理办法，实现具有自组织、自适应能力的智能网络管理机制。

3.1管理模式

网络信息管理可采用搜集模式和监控模式相结合的方式。搜集模式通过发送指令搜集网络拓扑信息，赋予用户即时获取当前网络结构的能力；监控模式通过监控从网络组建起历史网络的结构变化，实现网络拓扑信息更新，从而整合为当前网络拓扑结构。

搜集模式在实现时，首先由网关设备广播一个命令来搜集设备信息；然后，收到广播信息的路由节点再按照一定的数据格式，由网关返回子节点关联信息；当网关收到各个路由节点的返回信息后，再将其组合为整个网络中的设备信息。

监控模式则是从网络形成起，网关节点就开始监控所有节点的状态；当路由节点检测到其子节点加入或者退出的时候，向网关上报该子节点的状态变化信息，而网关节点检测到子节点加入或者退出则不用上报，直接在网关内部处理；当网关接收到路由节点上报的状态信息后，就会删除或者增加该路由子节点的关联信息，同时更新整体网络结构。

3.2 网络拓扑存储结构

网关节点作为整个网络拓扑结构管理的中心，负责拓扑结构的添加、删除和更新，因此，必须在网关节点存储整体的网络拓扑结构信息。受网关资源的限制，本文采用分级动态链表的形式保存网络拓扑信息，以便以较少的资源占用实现拓扑信息的动态存储。本设计的网络拓扑存储结构如图5所示。

图5中，AssocListHead是装载路由节点头信息的数组，包含有该路由节点的长地址、短地址、父节点短地址和拥有的子节点数以及指向其子节点链表assoc_list的头指针；assoc_list链表中记载着这一路由下的子节点信息，包括子节点的短地址、长地址、类型、连接状态等。在该路由下每增加一个子节点，就会在assoc_list链表中添加一个节点信息，当节点离开时，又会将相对应的链表删除。这样，网关就可以方便地对当前网络中的所有节点的拓扑和相关信息进行查找、更新、维护。

3.3 网络维护方案

网络维护的实施要建立网络中所有类型节点间的区分与协作机制。区分是根据节点类型的不同、事件类型的不同做出区别处理；协作是在所有节点间建立连动响应机制，相互配合，并实现信息的汇聚和统一管理。具体的网络维护分为事件响应和信息维护两部分。

3.3.1 拓扑变化事件的响应

拓扑变化主要是指节点加入事件和节点退出事件。当节点加入事件是指节点加入网络时，其父节点负责将该子节点加入信息上报网关；节点退出事件则是指获取到的网络节点丢失信息的处理。处理可分为两种情况：一种是当传递来的type = 1时，即丢失节点为本节点的父节点时，开启网络加入流程，使节点可以重新加入网络，并恢复网络的正常运行；第二种情况是type = 0时，即本节点发现其中一子节点丢失。本方法对于长时间无法连接的子节点，将启动移除（LEAVE）流程，将该子节点从网络中删除，同时向网关节点报告子节点退出的消息。

需要注意的是：当子节点丢失时，有的时候是真正丢失了（长时间或永久无法连接），但更多的时候只是暂时地失去联系，随着子节点的重新加入申请，又可以加入网络，恢复正常的运行状态。因此，设计时需要将暂时失步和真正丢失这两种情况区分开，再分别做出合理的处理。

本文采用延时判断的方式，即当检测到失步现象发生后，先定时一段时间，再做判断：如果定时一段时间后，节点仍旧失去联系，则判定是真的丢失了节点，此时可通过NLME_LeaveReq移除子节点，同时上报网关节点丢失的消息；否则认为只是暂时的节点失步。 节点退出情况的处理流程如图6所示。

3.3.2 拓扑信息的维护

由网络各个路由上报的节点加入或退出的信息最终将在网关汇集，网关按照上报的节点加入、退出信息对网络拓扑存储关联表进行添加、删除、更新，以维护当前网络拓扑状态。其具体方法是先判断接收信息的种类，然后对节点加入信息和节点退出信息分别处理。对于加入信息，可核查是否是已经存在于网络中的点，如果是已经存在的，则更新存储的节点信息；如果是一个全新的点，则为该节点分配存储空间，并在对应的父节点下增添子节点分支。对于退出信息，同样核查是否是存在于网络中的点，如果该节点已经不存在了，则报错处理；如果是存在的点，则将该节点信息删除，并解除与其父节点的父子联系。

网关在接收到由父节点上报的节点加入消息时，还需要对加入子节点类型进行判断：如果是终端节点，则在其父节点的链表中更新或加入该子节点的相关信息；如果加入节点是路由节点，除了在该路由节点父节点的链表中加入该子节点信息外，还要添加该子路由关联头信息。图7所示是实现网络拓扑维护管理的示意图。

4 实验验证

本文的实验验证可在基于CC2430搭建的WSN开发平台上进行，该平台共使用5个终端节点、5个路由节点、1个网关和PC调试机。所有传感器节点自组织成无线网络，并将感知信息和拓扑信息汇报给网关节点，网关节点与PC机通过串口相连，操作人员可以通过上位机的调试软件对网络状态进行实时监控。图8所示是其上位机监控程序界面。该试验网络的节点布局示意图如图9所示。

实验时随机选取监控过程中两个时间点的网络拓扑结构监控过程示意图如图10所示。其中两个时间点在实验过程中上报的拓扑变化信息如表1所列。

从实验结果可以看出，一方面，父节点能够实时上报其子节点加入和丢失的网络变化情况；另一方面，子节点也能够及时检测出其父节点的丢失，并选择其他父节点重新申请加入网络。可见，本系统具有网络的自组织、自适应的动态网络监控与维护功能。

5 结 语

本文提出了一种通过终端与父节点间的失步信号来捕捉与基于叶子节点人为触发失步函数调用的方法，可以实现整个网络节点丢失情况的获取。其中，通过终端与父节点间失步信号来捕捉节点丢失信息的方法无需人为干预，能够通过协议自动实现，从而减少了查询的数据量和对其操作带来的系统资源占用；基于叶子节点的失步函数触发机制，只通过叶子节点与网关的数据传输，就能够完成整个线路上节点丢失情况的获取，在实际应用中，经常由终端上报数据，相当于终端自动完成数据线路上父节点丢失情况的发现，使该方法的实施更加简单。这两种方法的结合，能够以较小的数据通讯量、简单的操作和较小的系统资源占用来实现网络发现的功能，因而

具有较高的实际应用价值。

本文提出的网络拓扑维护方法具备网络拓扑的自组织、自适应功能，可满足无线传感器网络系统对于网络组织结构的动态性能要求。同时具备拓扑结构的存储功能，能以较少的系统资源保存整个网络的动态拓扑结构，十分方便网络的管理和控制。

参 考 文 献

[1] 赵涛. 基于数据聚合的无线传感器网络拓扑发现算法[J]. 计算机工程与应用，2011，47 (3)：17-19.

[2] Texas Instruments. Method for discovering network topology[EB/OL]. [2005-9-15]. 省略/.

[3] ZigBee Alliance. ZigBee specification[EB/OL]. [2006-12-1]. 省略/.

[4] EGAN D. The emergence of ZigBee in building automation and industrial control[J]. Computing&Control Engineering Journal, 2005, 16(2): 14-19.

[5] 李文仲，段朝玉. ZigBee2006无线网络与无线定位实战[M]. 北京：北京航空航天大学出版社，2008.

[6] HEINZALMAN W R, CHANDRAKASAN A, BALAKRISHNAN H. An application specific protocol architecture for wirelwss microsensor network[J]. IEEE Transactions on Wireless Communication, 2002, 1(4): 660-670.

[7] AKYLDIZ IF, SU W, SANKARASUBRAMANIAN Y. Wireless sensor networks: A survey[J]. Computer Networks, 2002, 38(4): 393-422.

[8] 申军，齐望东. 一种新的无线传感器网络拓扑发现算法[J]. 计算机应用研究，2009，26(5)：1868-1870.

[9] 臧传真，范玉顺. 面向监控和管理的无线传感器网络拓扑发现算法[J]. 计算机应用研究，2006，23(11): 230-233.

[10] GEORGEFF I. A distributed topology discovery algorithm for wireless sensor networks[D]. Perth: University of Western Australia, 2004.