网络拓扑结构范文1
关键词 网络拓扑 应用 计算机网络计算机网络是现代通信技术与计算机技术相结合的产物。所谓计算机网络，就是把分布在不同地理区域的计算机与专门的外部设备用通信线路互连起来，从而使众多的计算机相互之间可以进行信息的传递，共享彼此的硬件、软件、数据信息等资源。
网络拓扑结构就是指用传输媒体把计算机等各种设备互相连接起来的物理布局，是指互连过程中构成的几何形状，它能表示出网络服务器、工作站的网络配置和互相之间的连接。网络拓扑结构可按形状分类，分别有：星型、环型、总线型、树型、总线/星型和网状型拓扑结构。
1 星型拓扑结构
如果把网络中的计算机终端看成每一个结点的话，星型拓扑结构的布局与其他拓扑结构的不一样，它由中央结点和周围结点相连而组成。结构是以中央结点为中心，周围有各结点，这些结点与中央结点相连接，形成一个星形方式。中央结点与各结点通过点对点方式连接，中央结点执行集中式通信控制策略，所以相对来讲中央结点在整个网络系统中承担了相当繁重的任务，系统对中央结点的配置就会有相当高的要求，通常情况为了保证网络通讯的正常，会另外配置一台一模一样的计算机作为中央结点的备份。最常见的星型拓扑结构如图1所示。
如果按星型拓扑结构来进行组网，网络中任何两个结点计算机要进行通信都必须通过中央结点来进行控制。那么能成为中央结点的这台计算机必须具有以下三个方面的主要功能：（1）对要进行通信的双方进行通信可能性的判断，并为双方建立通信物理连接；（2）保证双方通信过程中这一通路完全畅通；（3）在通信结束或通信不成功时，可以及时拆除通道。
星型拓扑结构作为最早使用的一种网络构成方式，目前也算是使用率最高且使用面最广的一种组网方式。综合地说，星型拓扑结构具有以下特点：（1）网络结构相对简单，集中控制易于维护，容易实现组网；（2）网络延迟时间短，传输误码率低；（3）网络共享能力较差，通信线路利用率不高，中央节点负担过重；（4）可同时连双绞线、同轴电缆及光纤等多种媒介。
2 环型拓扑结构
一般情况下我们把环形拓扑结构中的计算机称为环路接口，环形网中各环路接口采取首尾相连的方式，形成闭合环形通信线路，数据会沿着一个方向在这个环路上进行传输。位于这个环路上任何结点所发送的请求如果被通过就可以向环路发送信息。深入分析这条环线的特点，由于位于这条环线上的结点计算机公用，所以只要其中一个结点发送的信息都会经过环中所有的环路接口。发送的信息流中含有的目的地址与环上某环路接口地址相符时，此信息就被该目的结点的环路接口所接收，信息到此不会自动消失，而是会继续传至下面所有的环路接口，直至传回到发送该信息的环路接口结点为止。目前使用的环形网中的数据可以进行单向和双向传输。最常见的环形拓扑结构如图2所示：
环形网的特点是：（1）信息依靠两个相邻的环路接口沿固定方向传送；（2）某个结点都有自举控制的功能；（3）由于信息会经过环路上的所有环路接口，当环路过多时就会影响数据传输效率，网络响应时间变长；（4）一环扣一环的连接方式会让其中一个环路接口的故障造成整个网络的瘫痪，增加维护难度；（5）由于环路是封闭的，所以扩充不方便。
环形网也是微机局域网常用拓扑结构之一，适合信息处理系统和工厂自动化系统。1985年IBM公司推出的令牌环形网（IBM Token Ring）是其典范。在FDDI得以应用推广后，这种结构也广泛得到采用。
3 总线拓扑结构
总线拓扑结构是用一条电缆把所有节点计算机相互之间以线性方式连接起来的布局方式，这条重要的电缆也就是总线，位于总线上的各个结点计算机地位相等。最常见的总线形拓扑结构如图3所示：
在采用总线拓扑结构构建的网络中，所有网上计算机都通过相应的硬件接口直接连在这条总线上，任何一个结点发出的信息都会沿着这条总线同时向两个方向进行传播，位于这条总线中任何一个结点计算机都能够接收信息，但只有目的结点才会从总线上把需要的信息拷贝下来。由于信息的传播方式是同时向四周传播，类似于广播电台的功能，所以我们又把总线式网络称为广播式网络。总线的负荷能力较强，但不能超出它的负荷范围；另外还要注意总线不能无限制延长，而且在这条总线上的结点数量也是有限的。
总线拓扑结构的特点主要有：（1）结构简单，数据入网灵活，便于扩充；（2）不需要中央结点，不会因为一个结点的故障而影响其他结点数据的传输，故可靠性高，网络响应速度快；（3）所需设备少、电缆或其他连接媒体相对价格低，安装也很方便；（4）由于发送信息的方式采用的是广播式的工作方式，所以共享资源能力强。
为了解决干扰问题，我们在总线两端连接端结器，主要为了与总线进行阻抗匹配，最大限度吸收传送端部的能量，避免信号反射回总线时产生不必要的干扰。
4 树形拓扑结构
树形结构它是在总线网的基础上把整个电缆连接成树型，树枝分层每个分支点都有一台计算机（如图4）。树形网采用分层控制，沿着这棵树的结构可以很迅速地找到相应的分支和结点路径进行信息广播。树形拓扑结构具有一些优势。具有布局灵活，可扩展性好的特点，而且其容错能力较强，当页结点出现故障时，不会影响其他分支结，这一优点为工作提供了不少便利。但还是明白的是：除了叶节点及其相连的线路外，其他部分的工作还是会受影响的。
5 总线/星型拓扑结构
总线/星型拓扑结构就是总线型和星型的一种组合方式，内层的网络采用总线型，用一条或多条总线把计算机等设备连接起来，每一组以总线方式相连的小网络又呈星型分布。总线材料一般采用同轴电缆，星型传输媒体可使用价格比较便宜的双绞线。采用这种总线/星型拓扑结构，既解决了总线型拓扑结构连接用户数量上的限制，又解决了星型拓扑结构在传输距离上的限制，很好地吸收了两者的优点，又弥补了双方的缺点。
网络拓扑结构范文2
关键词：基于Web的网络管理；SNMP协议；拓扑结构；拓扑图构造与显示
中图分类号：TP393.07
随着网络技术和互联网的不断发展，互联网的网络连接结构变得日益复杂。那么就需要有能够对网络进行配置、监控网络性能的良好的网络管理系统来管理网络，从而使得互联网络能够安全、可靠、稳定地运行。
1 主要的网络拓扑发现方法
1.1 基于ICMP协议的网络拓扑探测方法
ICMP（Internet Control Message Protocol）协议作为IP协议的一部分，它是一种差错报告机制，可以用来向目标主机或设备请求或者报告各种网络信息。在基于ICMP协议的拓扑发现中，用到回送请求（Echo Request）和回送应答（Echo Reply）这两种报文。该种方法主要是利用ICMP协议原理，结合使用ping命令和traceroute命令来实现。通过ping目标主机或设备进行探测，如果能够收到目标的回送应答报文，则可以判断目标存在且是活动的，并记录其IP地址和子网掩码。通过traceroute命令向目标主机或设备发送不同TTL值的ICMP报文，根据报文所经过的路由器发回的回送应答报文，可以确定出从源主机到目标的路由信息。根据得到的这些信息，并使用发现算法和拓扑结构的构造方法得到拓扑图。
该种基于ICMP协议的网络拓扑结构的发现方法可以应用在几乎所有的网络中，因为使用TCP/lP协议的网络主机和设备都支持ICMP协议，这种方法的优点是检测简单、快速和可靠。但是这种方法向网络中的设备发出了大量的探测报文，这样会给网络增加负载，并且也不是所有的目标设备都会回送应答报文，因此发现的效率也并不高。这种方法适用于局域网内的拓扑发现。
1.2 基于SNMP协议的网络拓扑发现
SNMP网络管理体系结构主要由三部分组成：管理信息结构、SNMP协议和管理信息库MIB。其中MIB定义了可以通过网络管理协议访问的被管理对象的集合，它描述了网络主机或设备的重要信息。简单网络管理协议SNMP（Simple Network Management Protocol）是由Internet体系结构委员会所制定的，是因特网中应用最广泛的网络管理协议，目前大多数网络设备如交换机、路由器等都支持该协议，它使用的传输层协议是面向无连接的UDP协议，无需建立专门的连接，因此这样就会降低网络通信的开销和负载。
基于SNMP协议的拓扑发现方法的思想就是通过SNMP协议从网络主机、交换机、网桥、路由器等网络设备中的MIB信息库中获取设备和路由信息，其中主要用到的对象有组对象system、interfaces、ip组和两个表对象ipAddrTable、ipRouteTable。从指定的网关路由器开始，采用深度或广度遍历对网络中的设备进行逐个遍历，通过读取其MIB库中的信息，确定其设备类型及连接关系。具体来说就是，如果发现的目标设备中的简单对象ipForwarding=1且system组中的字段sysService=7，则可判断该目标是路由器；如果ipForwarding=2且sysService=3，则可判断该目标是交换机或网桥；如果两者都不是则可判断目标是主机。如果是路由器，继续查询其MIB中的interfaces组和表ipAddrTable可以获得路由器的接口信息，然后查询表ipRouteTable中的变量ipRouteType，若ipRouteType=4，则判断该端口相连接的是路由器，并根据其中的ipRouteNextHop来确定下一个发现的路由设备；若ipRouteType=3，则判断该端口相连接的是子网。
综上所述，该算法的优点是系统和网络的开销少、搜索过程和算法简单，发现效率高。虽然现在的大多数主机和设备都支持这个协议，但是也有设备并未启动SNMP服务，另外，有的网络设备中的MIB信息库并不可以随意访问的。因此该方法也有一定的局限性。
2 网络层的拓扑结构发现算法的改进
2.1 算法的改进思想
本算法综合了上述两种方法的优缺点，对使用SNMP协议的设备的发现进行了规模限制，设置了一个待访问的路由器总数的阈值，遍历每一个路由器时，判断一下已遍历的路由器数目是否小于此阈值，如果是则继续访问下一个路由器，否则算法退出。对于基于ICMP协议的拓扑发现中，防火墙或者网络设备可能会丢弃收到的报文，所以发送方可能会接收不到被探测设备的响应报文，因此就不能保证发现的绝对准确性。通过分析TCP/IP协议可知，可以采用向被探测设备发送错误报文的方法来解决这个问题，但是也并不是所有的错误报文目标设备都会响应。
2.2 算法的描述
具体算法描述如下：
（1）初始化待搜索路由器队列、待搜素的IP地址队列、支持SNMP协议的路由器队列、不支持SNMP协议的路由器队列、子网地址队列、连接关系队列。并设置要访问的路由器总数的阈值为N，初始化计数变量n=0。
（2）从待搜素的IP地址队列中取出一个地址，若n++N，则算法结束。
（3）取得该IP地址所属的子网地址及其缺省路由器地址，将其加入待搜索的路由器队列。
（4）若待访问的路由器队列不为空，从待访问的路由器队列中取出一个地址探测，若其支持SNMP协议，将该路由器添加到支持SNMP路由器队列，执行步骤（5）。若其不支持SNMP协议，将该路由器加入到不支持SNMP队列，采用通用协议算法进行发现。
（5）对其包含的IP地址进行SNMP探测。访问其MIB信息库，使用前面所讲述的方法来判断出设备的类型及连接关系，将发现的路由器、子网及其连接关系添加到相应的队列。
（6）重复步骤（4），直到待搜索的路由器队列为空，重复步骤（2），若待搜素IP地址队列为空，则算法结束。
3 拓扑图的构造与显示
通过网络拓扑发现算法确定了网络设备的分布及其连接关系之后，就要构造出拓扑图以直观的方式将网络设备的位置分布以及它们之间的连接关系显示出来。在显示页面上，按照一定的规律来分布显示出拓扑结构，其中使用不同的结点来分别表示不同的网络设备，以结点间的连线来表示设备之间的连接关系。
要确定网络设备在拓扑结构图中的位置，就要计算出路由器、子网在图形界面中的显示位置的信息，即结点的坐标（x，y）。对于网络层拓扑图的构造，首先将指定的网关路由器（记为R）放置在显示页面的某一个固定位置，可以选择正中心的位置点，坐标记为（x0、y0），将在一定范围内发现的与该路由器相连的所有的路由器和子网的总数记为n。而后将其中与之相连的子网分布在以（x0，y0）为圆心，r=（n×c）÷2π（其中c为常数，其中c的取值可以根据网络的规模来设定）为半径的圆周上；将与之相连的路由器分布在以（x0，y0）为圆心，2r为半径的圆周上，这些路由器和子网交叉均匀分布，并记录下每个路由器所处的象限。从这里可以看出当n值增大时，r值也会增大，这样取半径的目的是在路由器数量较多时，让圆的半径大一些，便于结点图标布局合理，尽量避免重叠。那么这种情况下，与路由器R相连的子网结点在界面上的显示位置的坐标就可以通过如下的公式计算出来：x=r×cos（（2π÷n）×i）+x0，y=r×sin（（2π÷n）×i）+y0；路由器结点的坐标可以通过如下公式得出：x=2r×cos（（2π÷n）×i）+x0，y=2r×sin（（2π÷n）×i）+y0。
然后再采用广度优先的方式将与路由器R相连的所有路由器（记为R1、R2、…Rn）的连接拓扑图分别构造与显示出来，以R1为例来说，将与之相连的所有路由器和子网的个数记为n，R1的坐标记为（x0，y0），r=（n×c）÷（2π）（其中c为常数），分以下三种情况讨论：
（1）如果R1在以路由器R为圆心的圆周的第一象限时，将与之相连的子网均匀分布在以（x0，y0）为圆心，r为半径的圆周的二、三、四象限内，各个子网结点在页面上的位置的坐标（x，y）可以通过如下公式计算出来：x=r×cos（（3π÷2n1）×i+π/2）+x0，y=r×sin（（3π÷2n1）×i+π/2）+y0，其中n1为子网总数；将与之相连的所有路由器均匀分布在以（x0，y0）为圆心，2r为半径的圆周的第一象限内，各个路由器结点的坐标可以通过如下公式计算出来：x=2r×cos（（π÷2n2）×i）+x0，y=2r×sin（（π÷2n2）×i）+y0（n2为路由器总数）。
（2）如果R1在以路由器R为圆心的圆周的第三象限时，将与之相连的子网均匀分布在以（x0，y0）为圆心，r为半径的圆周的一、二、四象限内，各个子网结点在页面上的显示位置的坐标（x，y）可以通过如下公式计算出来：x=r×cosθ+x0，y=r×sinθ+y0，θ=（3π÷2n1）×i（n1为子网总数），其中当π≤θ≤3π/2时，θ=（3π÷2n1）×i+π/2；将与之相连的路由器分布在以（x0，y0）为圆心，2r为半径的圆周的第三象限内，各个路由器结点的坐标可以通过如下公式计算出来：x=2r×cos（（π÷2n2）×i+π）+x0，y=2r×sin（（π÷2n2）×i+π）+y0（n2为路由器总数）。
（3）如果R1在以路由器R为圆心的圆周的第四象限时，将与之相连的子网均匀分布在以（x0，y0）为圆心，r为半径的圆周的一、二、三象限内，各个子网结点在界面上的显示位置的坐标（x，y）可以通过如下公式计算出来：x=r×cos（（3π÷2n1）×i）+x0，y=r×sin（（3π÷2n1）×i）+y0（n1为子网总数）；将与之相连的路由器分布在以（x0，y0）为圆心，2r为半径的圆周的第四象限内，各个路由器结点的坐标可以通过如下公式计算出来：x=2r×cos（（π÷2n2）×i+3π/2）+x0，y=2r×sin（（π÷2n2）×i+3π/2）+y0（n2为路由器总数）。
用同样的方法将其它路由器的拓扑图分别构造出来，然后再采用广度优先的策略将下一层路由器的拓扑结构给构造出来，其它的以此类推，重复此工程即可。通过实验表明，对于一个园区网内部的网络管理系统来说，这种网络拓扑结构图形构造和显示方法，具有一定的可行性和有效性。
4 结束语
计算机网络的拓扑结构对网络管理是非常重要的，准确的网络拓扑结构信息对于网络的管理和监控及诊断网络故障具有重要意义。本文对现在主要的网络逻辑拓扑发现算法进行了比较分析，对于存在的问题提出了改进的办法。实验结果表明，该改进算法能够比较准确地发现网络拓扑结构的信息，提出的拓扑图构造和显示方法也具有一定的可行性和现实意义。
参考文献：
[1]谢希仁.计算机网络[M].北京：电子工业出版社，2008.
[2]夏海涛，詹志强.新一代网络管理技术[M].北京：北京邮电大学出版社，2010.
[3]李文，王智立.网络管理原理与技术[M].北京：人民邮电出版社，2008.
[4]杨立波.网络拓扑发现技术研究[J].科技探索，2011（09）：90.
网络拓扑结构范文3
关键词：故障诊断；进化神经网络；激活函数
中图分类号：TP18 文献标识码：A 文章编号：1009-3044(2012)36-8765-04
1 概述
电力变压器是电力系统中的重要设备，其当前的工作状态直接影响着整个电力系统的运行。为了使变压器始终处于良好的状态，严密监视并尽早发现变压器的任何异常就显得非常重要。变压器的故障诊断就是根据变压器故障的征兆，确定故障的性质或部位。近年来，人工智能理论的不断完善及其在故障诊断中的成功应用，为变压器故障诊断技术的发展开拓了新的途径。该文介绍了一个我们研制的电力智能变压器诊断系统，这是一个功能完善并实用的系统，结合了基于专家系统和神经网络的多种诊断方法。结合该系统的神经网络诊断部分的研制，该文将着重论述诊断神经网络的拓扑结构优化设计问题。
2 基于经验的诊断网络拓扑结构优化设计
2.1系统设计思想
在目前变压器故障诊断的研究中采用最多的是BP网络，系统采样的数据集可以分为训练集和测试集两部分，前者用于网络的训练，后者用于测试训练好的网络。通常两者独立采样以保证数据的无关性，使测试结果更能反映网络的泛化能力。我们运用两种准则来比较测试集的目标集与仿真输出集的接近程度以评价网络性能：均方误差准则和误判率准则。该文采用经典的k子集交叉检验法来评价网络的性能，数据集划分为训练集和测试集以兼顾网络的分类精度和网络的推广能力。另外，测试集和训练集的划分带有随机性，再加上k次评价，这样的结果比较稳定，网络训练好坏的影响大大降低，可以充分反映神经网络在这个数据集上的性能。该文在借鉴前人经验的基础上，结合具体应用，通过实际试验，用上述方法设计了一个性能良好的变压器诊断网络，该网络具有分类精度高并且推广能力强的特点。
2.2基于经验的神经网络拓扑结构的设计
我们选择的是标准的单隐层前馈网络结构，对单隐层的前馈神经网络来说，其VC维为MN+NP，其中M，N，P分别为输入层、隐层、输出层的神经元数。由于M，P和例子数都是已知的，因此设置误差上限e后就可以估算出N。
激活函数的选择方面，该文选择了tanh作为函数隐层激活函数。而输出层激活函数则选择sigmoid函数。训练算法的选择方面，由于标准BP算法训练速度很慢，选择带动量与学习率调整的改进BP算法作为我们对网络进行评价时的训练算法。
在此基础上，通过隶属函数求出实验数据相对于注意值的隶属度，以其作为神经网络的输入。我们使用的隶属函数如下所示的Sigmoid函数，其中x表示属性的原始值，xa表示注意值。
2.3实验方法和结果分析
实验使用的数据是“智能化变压器诊断系统”所带的一个在线诊断数据集。此数据集共107个实例，输入属性10项，输出属性12项。因此有： M=10， P=12，m=107由ln(m/d)>0 m/d>1 m>(M+P)*N 107>22*N N
3 基于进化神经网络的优化方法
3.1进化神经网络的算法流程
进化算法的思想来源于自然界的物种进化规则，它是一种基于群体的随机搜索算法。该文采用C++和Matlab混合编程的方法实现了该算法，其算法流程如图3所示。我们用面向对象的开发方法实现遗传算法,程序的主体是两个类：CGA和CChromosome。前者实现遗传算法的运行流程,后者实现染色体（个体）的编码和遗传操作细节，并通过统一的接口把功能提供给前者。这种设计把遗传算法的操作流程抽象出来，独立于遗传算法的编码和算子的具体实现。
诊断的精度是很高的，20个诊断实例中失误2个，正确率达到了90％，并且是在网络的训练数据还有缺陷的情况下。这个诊断精度已经接近于变压器专家的水平，可见，经过针对变压器故障诊断特点进行优化设计的神经网络的应用价值是极具潜力的。
4 结论
该文研究了神经网络在电力变压器诊断中的应用，给出了变压器故障诊断的神经网络模型，根据诊断模型，在前人经验的基础上，设计了单隐层的变压器诊断网络，并给出了网络的评价方法。在matlab上建立了实验环境，通过实验给出了神经网络模块的最佳隐节点数。在此基础上，设计了基于遗传算法的网络结构进化算法，并用C++和matlab实现了这个算法。实验表明诊断效果良好，并与前面的实验的结果进行比较，表明了进化算法的良好性能。
参考文献:
[1] 架尚敏,戴国忠.利用结构信息的故障诊断方法[J].计算机学报,2005,28(5):801-808.
[2] Ying Mingsheng. Knowledge transformation and fusion in diagnostic systems[J]. Artificial Intelligence,2005(163):1-453.
[3] 李占山,姜云飞,王涛.基于模型的诊断问题分解及其算法[J].计算机学报 2003,26(9):1177-1182.
[4] 陈荣,姜云飞.含约束的基于模型的诊断系统[J].计算机学报,2001(24):127-135.
[5] 架尚敏,戴国忠.利用结构信息的故障诊断方法[J].计算机学报,2005,28(5):801-808.
[6] V. Duraisany, N. Devarajan, D. Somasundareswari, et al. Neural fuzzy schemes fro fault detection in power transformer[J]. Applied Soft computing,2007,7(2):534-539.
[7] Leung Frank H F. Tuning of the structure and parameters of a neural network using an improved genetic algorithm[J]. IEEE Trans. On Neural Networks, 2003,14(1):79-81.
[8] Thang K.F., Aggarwal R.K., Esp D.G., McGrail A.J. Statistical and neural network analysis of dissolved gases in power transformers Dielectric Materials[C]. Measurements and Application on Eighth International Conference 2000(IEE Conf.Publ.No.473),2000:324-329.
网络拓扑结构范文4
常见的直接网络拓扑有Mesh／Torus、Flat－tenedButterfly、Dragonfly等。Mesh／Torus网络拓扑（k－ary，n－cube）（如图1和图2所示）是一个n维网格，每一维上有k个节点，相邻节点之间有通道相连，其节点规模为kn。Mesh／Torus网络拓扑结构具有较优良的特性。Mesh／Torus网络拓扑结构十分简单，具有高度的规则性，易于布局布线，便于实际部署，也具有很好的扩展性。Mesh／To－rus网络拓扑结构具有广泛的应用，比如64个节点的Tilera［5］、TRIPS［6］处理器、RAW处理器［7］，还有英特尔Teraflops［8］，都是采用2－DMesh网络拓扑结构。但是，随着节点规模的扩大，其劣势就表现出来了。这主要体现在网络直径增大、吞吐率下降等。Mesh／Torus网络拓扑是早期提出的经典网络拓扑，由于其结构简单、性能较好一直沿用至今。为了满足日益增长的性能要求和节点规模增大的情况，KimJ等人［9］于2007年提出了Flat－tenedButterfly（如图3所示）网络拓扑结构，这种结构利用高阶（High－radix）路由器［10］将每个路由节点与之同维的所有路由器节点相连，这样每一维上的跳数就变成了1。一个n维、每一维规模为k的FlattenedButterfly（k－ary，n－cube）网络拓扑上的数据包的路由跳数最多为n跳。FlattenedBut－terfly网络中的每个高阶路由器能连接多个计算终端（p），整个网络能够连接总共p×kn个终端。KimJ的实验表明，FlattenedButterfly丰富的链路特性使得网络性能得到提升，但是物理开销的增加也是巨大的。2009年KimJ又相继提出层次化［11］的Dragonfly（如图4所示）拓扑结构［12］。Dragonfly网络拓扑可以分为三层。在最底层，每个路由器节点连接p个计算终端。在中间层，也就是在局部组内，每个路由器与组内a－1个路由器相连。在最高层，每个局部组内总共b×a跳全局通道与其余局部组进行相连。Dragonfly拓扑结构实际上是基于光通信技术的发展提出的。对于链路较长的全局通道，采用光纤通信来代替电信号通信，这样可以大大降低全局通信的延时，局部组内由于距离较短，仍然采用电信号通信。为了更好地进行均衡负载，将参数p和b取同值，将a取为2p或者2b。Dragonfly拓扑结构能够获得比较好的性能，如延时相对较低、跳步数较短。但是，同时也可以看到，Dragonfly网络拓扑具有很差的扩展性，全局通道的延时仍然会较大。实际中应用Dragonfly拓扑结构的系统有Cray［13］和IBM的PERCS［14］。
常见的间接网络有FatTree［15］、Butterfly等。FatTree（如图5所示）是一种是应用很广泛的间接网络拓扑结构。最早由LeisersonCE于1985年提出，当时提出的FatTree是一个标准的Bina－ryTree结构，树的每个叶子节点连接p个计算终端，每个叶子节点又有p条链路连接其父亲节点，越高层的节点所连接的链路数就越多，也就显得越来越“fat”。由于每一路由器节点的开关规模差异较大，不利于实际应用，后来经过不断发展变化，形成了每级节点开关规模一致的FatTree结构。FatTree网络拓扑结构中间路由器较多，链路非常丰富，能够使网络获得比较好的性能，其缺点是开销较大、成本较高。Butterfly（如图6所示）网络拓扑结构是一种经典间接网络结构，对于确定的终端数N和开关度为2k的Butterfly具有最短的网络直径logkN＋1，虽然有此优点，但是其缺点也是很明显的。首先Butterfly网络具有很差的路径多样性，对于每一个从源节点到目的节点的数据包，其路由路径是唯一的；其次Butterfly级与级之间的链路较长，这会增加电信号传送链路的延时。对于第一个缺点，可以对Butterfly网络拓扑结构做一些改变，比如增加级数来解决这一问题。在间接拓扑网络中使用Butterfly的有BBNButterfly［16］等。为了应对节点规模扩大的情况，要对网络拓扑的结构做一些调整。对于直接网络，扩展的方式有两种方式。第一种方式是扩展每一维上的路由节点规模。第二种方式是扩展网络拓扑的维数。第一种方式简单，每个路由器节点的端口数不会改变，易于部署，但是其缺点是随着跳数的增大，吞吐率等性能会急剧下降，在节点数较大的情况下一般不采用这种扩展方式。第二种扩展网络维数的方法是一个可行的方法，它会使网络拓扑节点的基数增大，但数据包在网络中的跳数增加缓慢。通过实验发现，在相同节点规模下，维数较大的网络拓扑的性能要优于低维的网络拓扑性能。比如To－fu结构就是采用6－D的Mesh来解决这一问题的。但是，增加维数会给实际部署带来较大难度，维数越大，难度也变得越大。对于间接网络拓扑结构，其扩展的方法是增加间接网络拓扑的级数，这种方式能够给系统带来比较好的性能，具有广泛的应用，比如Tianhe－2就是采用FatTree这种间接网络结构来实现的。但是，间接网络的弊端是物理开销太大。随着终端规模的增大，级数会变大，中间路由节点会急剧增多。RobertoP等人［4］在2012年提出了一种新型混合拓扑结构，这种新型的混合拓扑结构（Hybridtopology，后续内容的图表中将这种拓扑结构简称为“HD”）是结合了直接网络和间接网络的优点而提出的。本文将这种新型混合网络拓扑结构的参数表示为（k－ary，n－direct，m－indirect，p－c）。k代表每一维的节点数，n代表网络的维数，m代表间接网络的级数，p代表每个路由节点所连接的终端数，若网络节点所连接的终端数为1，则该参数可缺省。如图7所示为这种新型混合拓扑结构。每一维上的节点布局类似于Mesh／Torus网络，只是相邻节点之间并没有链路相连，而是通过每一维所在的间接网络进行相连。每个间接网络的级数m视每一维的节点规模而定，比如k值较小，间接网络的级数可以小到仅仅为1，也就是说每一维上的间接网络就是一个Crossbar。如果k值较大，间接网络可以为m级的FatTree网络。每个直接网络的节点可以连接多于一个的计算终端。计算终端连接数为p的混合拓扑结构网络所连接的终端规模为p×kn。这种新型混合拓扑结构有一些比较好的静态特性。相对于直接网络，新型混合拓扑结构的直径要比普通直接网络的直径小很多。在网络拓扑规模比较小的情况下，间接网络可以为一个交叉开关Crossbar，其网络直径仅为2n（n表示网络拓扑维数），而普通直接网络拓扑结构，比如Torus，其网络直径为k／2×logkN。同等节点规模下网络直径的减小能够减小网络的延时，提升吞吐率。另外一方面，规模比较小的间接网络（FatTree），其层数要比同等节点规模的FatTree要小很多，整个混合网络拓扑的路由节点数、链路数要比完全间接网络小很多，因此其开销会比完全间接网络小。文献［4］对这种新型的混合网络拓扑与传统的直接网络、间接网络性能进行了比较，得出的结果是新型混合拓扑结构的吞吐率性能要优于Mesh／Torus、FatTree等网络，但比FlattenedButterfly要差。
2新型混合拓扑结构的优化
新型混合拓扑结构Hybrid的每一维上均由以FatTree为代表的间接网络相连接，这实际上可以将规模为（k－ary，n－direct，m－indirect，p－c）的混合拓扑结构看成由规模为（k1／m－ary，m×logkp＋m×n－tree）的FatTree网络分解为n×kn－1个规模为（k1／m－ary，m－tree）的FatTree，然后将这些FatTree的叶节点组成直接网络。这样做的好处是可以降低FatTree的级数，减小数据包路由的跳数。但是，当每一维上的节点规模增大时，间接网络（FatTree）的级数仍然较高。本文提出一种解决的方法，就是每一维上的节点由多个间接网络相连接。本文提出的改进优化的混合拓扑结构（Hy－brid－Ytopology，后续内容的图表中将简称为“HY”）是将Hybrid网络每一维上的间接网络由原来的单个间接网络改造成多个间接网络。这些间接网络的叶节点的链路相间地与Hybrid网络同一维上的节点相连接，Hybrid网络同一维上的节点若连接着不同的间接网络，则将这些节点用链路连接起来。
2.1Hybrid－Y拓扑结构描述Hybrid－Y拓扑网络结构每一维上的间接网络和Hybrid拓扑网络结构的间接网络一样，可以是一个简单的Crossbar或者多级FatTree。Hy－brid－Y拓扑网络结构和Hybrid拓扑网络结构的差异体现在两个方面：（1）间接网络与每一维节点的连接方式不同。Hybrid网络拓扑结构的间接网络叶节点（或者Crossbar）的链路依次分别与同维直接网络的节点相连接。Hybrid－Y拓扑网络结构的s个间接网络的叶节点的链路相互交替地与同维直接网络的节点相连接。（2）直接网络中节点之间的连接方式不同。Hybrid网络拓扑结构的直接网络节点之间没有链路连接，Hybrid－Y网络拓扑结构直接网络某一维中的节点若连接着不同的间接网络，就将这些节点用链路连接起来。下面引入如表1的参数来描述这个改进优化的混合拓扑结构。描述拓扑结构表达式的参数之间需要满足一定的条件。对于某一维上的直接网络连接的间接网络，参数k和参数s、m需要满足这样的条件：s×lm＝k，其中l代表间接网络，也就是FatTree每个叶节点所连接的终端数。对于给定的k值，参数s、m都是可以发生相应改变的。即便是参数s指定了，也就是每一维上的间接网络的个数确定了，间接网络的级数m也可能会有变化。若m取值为1，那么间接网络是一个规模为（k／s）×（k／s）的Crossbar；若m取大于1的值，则间接网络是一个FatTree，这个FatTree网络在m值给定后也就确定了。如图8是这种改进拓扑结构的一个实例。这个图中的直接网络每一维上由两个间接网络相连接。直接网络上的节点00连接间接网络00－0，节点01连接间接网络00－1，节点00与节点01连接着不同的间接网络，因此有一条链路连接节点00与节点01。同样，节点02也有一条链路与节点03相连。注意，节点01与节点02虽然连接着不同的间接网络，但是这两个节点之间并不用链路连接，这是因为这两个节点已经与它们相邻的连接着不同间接网络的节点相连了。
2.2Hybrid－Y网络路由策略在Hybrid－Y拓扑结构上主要采用了两种路由算法：维序路由和自适应路由。为了突出Hy－brid－Y拓扑结构的分析研究，本文将不对间接网络内部的路由进行分析，在后续所讲的维序路由和自适应路由，其间接网络都是文献［18］中使用的针对FatTree的基本自适应路由算法。Hybrid－Y网络拓扑的维序路由算法可以分为两个阶段。第一个阶段为跨维。在n维的Hy－brid－Y网络上执行维序路由算法首先要从数据包的源节点所在的维路由到目的节点所在的维。为了更好地描述这一过程，我们将数据包从某一维路由到另外一维这两维所决定的平面依据节点序号的递增方向划分为x轴方向和y轴方向。维序路由算法在执行跨维路由计算时统一执行先x轴方向后y轴方向或者先y轴方向后x轴方向。执行的x轴或者y轴方向确定后，具体沿着哪一条路径从一维跨到另外一维取决于直接网络每一维上的路由策略了，也就是第二阶段了。第二阶段为维内路由。简单来说，维内路由就是数据包如何从同一维上的一个节点路由到另外一个节点，这个过程是Hybrid－Y网络拓扑维序路由算法的关键步骤，它决定着网络的数据包路由跳数和延时。本文在实现这一过程时采用下面的策略。源节点和目的节点只有可能是直接网络中的节点，消息包所在的当前节点有可能是直接网络中的节点也有可能是间接网络中的节点。情景1源节点、当前节点s和目的节点d均是直接网络中的节点。（1）若当前节点s和目的节点d相邻且有链路连接，则数据包直接从当前节点路由到目的节点，如图9a所示；（2）如当前节点s和目的节点d不相邻，但是当前节点s和目的节点d连接着相同的间接网络，则数据包从当前节点s路由到其所连接的间接网络，如图9b所示；（3）若当前节点s和目的节点d不相邻，且连接着不同的间接网络，则数据包从当前节点s路由到与节点s有链路相连并且连接着与目的节点d相同间接网络的节点，如图9c所示。路由算法执行上面三个步骤就可以将数据包在同一维上从当前节点路由到目的节点。策略（3）的做法能够保证网络的流量相对均衡，不至于都去争抢直接网络中相邻节点之间的链路而导致直接网络节点之间链路的拥塞。（1）数据包从当前节点在间接网络内执行基本自适应路由算法朝着目的节点d的方向路由。情景2只有一种策略情形，这是因为情景2是依赖于情景1的，情景1中策略（3）的执行能够保证情景2只有唯一一种路由策略。至于间接网络内部的路由，这里不加以分析。对于Hybrid－Y网络拓扑的自适应路由算法，其路由执行过程也可以分为与维序路由算法类似的两个阶段：跨维阶段和维内路由阶段，但是每个阶段有所不同。在跨维阶段，自适应路由算法的不同点在于能够动态选择x轴方向或者y轴方向，其判断的依据是x轴方向和y轴方向链路通道的拥塞情况。路由算法将数据包沿着x和y方向链路通道中拥塞状况较好的方向路由。在维内路由阶段，其不同点体现在情景1中的策略（3）。维序路由算法中策略（3）的做法是为了保证网络流量的相对均衡，减小拥塞情况，但自适应路由算法将依据直接网络相邻节点链路拥塞情况与所连接的间接网络链路通道拥塞情况相比较，选择拥塞情况较小的链路通道路由，从而能够考虑到网络中链路通道的实际拥塞情况，避开拥塞较严重的链路通道，从而能够改善网络性能。对于自适应路由可能存在的死锁问题，根据路由路径的选择，可从两个方面分析：（1）路由路径经过间接网络。在这种情况下，由于间接网络是FatTree，所以不会发生死锁。（2）路由路径不经过间接网络。出现这种可能的唯一情形如图10a所示，节点a、b、c和d分别有链路相连接。当这些节点之间的数据包路由路径构成相关环时，就有可能发生死锁。为了避免这种情形的发生，使用虚通道的分配来避免死锁。如图10b所示，节点a、b、c和d之间的物理通道被划分为两个虚通道，分别标记为虚通道0和虚通道1。为了打破相关环路，当节点a、b、c和d之间的数据包的原地址编号和目的地址编号是升序时，使用虚通道0，当数据包的原地址编号和目的地址编号是降序时，使用虚通道1。分配虚通道后，图10a中的路径相关环就不存在了，也就避免了死锁的发生。
3性能评估
本文将改进的混合拓扑结构（Hybrid－Y）与新型混合拓扑结构（Hybrid）、FatTree、Mesh、To－rus、FlattenedButterfly进行比较。我们的模拟工具是时钟精确模拟器Booksim2．0［19］，混合拓扑结构的间接网络都是基于FatTree的网络。模拟的时候，数据包packet的尺寸都取10个flit，模拟的流量模式为均衡模式uniform，路由算法采用维序路由，网络维数均为2－D。此外，在节点规模较大的情况下（本文指节点数为1024），对FatTree网络和混合拓扑结构以及改进优化的混合拓扑结构在worst－case流量模式下进行性能的比较。
3.1模拟实验结果分析图11是在均衡流量模式下，64个节点规模的网络吞吐率模拟结果。从这个图中可以看出，FlattenedButterfly取得了最低的延时和最高的吞吐率，然后依次是改进的混合拓扑结构Hybrid－Y和新型混合拓扑结构Hybrid，结果显示最差的是Torus和Mesh。当网络节点规模增加到256个时，如图12a所示，结果显示FlattenedButterfly仍然能够获得最低的延时和最高的吞吐率，但这些都是建立在较高的开销基础之上的。改进的混合拓扑结构Hybrid－Y（间接网络级数大于1）获得了次之的吞吐率。同时注意到，间接网络级数大于1的混合拓扑结构Hybrid－Y的基本延时要比新型混合拓扑结构Hybrid（这里指间接网络级数小于4）高，从图12b的模拟跳步数可以看出，间接网络级数为3的混合拓扑结构Hybrid－Y的跳步数是10．5，新型混合拓扑结构Hybrid的平均跳步数分别为4．75和7．75。混合拓扑结构Hybrid－Y（间接网络级数大于1的情况）的基本延时要比新型混合拓扑结构Hybrid（这里指间接网络级数小于4）高的原因是线头阻塞效应（Head－Of－LineBloc－king）［20］。Mesh和Torus仍旧是表现最差的网络拓扑，这也说明了Mesh和Torus的2－D结构不适合作为大规模互连网络的拓扑结构。将节点规模增加到1024，如图13所示，能够得到类似的结论。FatTree网络在大规模节点的巨型机系统具有广泛的应用。如图14所示，在流量模式为worst－case的情况下，混合拓扑结构和改进优化的混合拓扑结构均获得了比FatTree更好的吞吐率。对于新型混合拓扑结构Hybrid与改进优化混合拓扑结构Hybrid－Y，在间接网络级数相近的情况下（图示中Hybrid的间接网络级数为5，Hy－brid－Y间接网络级数为4），改进优化的Hybrid－Y网络拥有更好的网络性能。对于维数高于2－D的情形能够得到类似的结果。
3.2性能开销比的比较和分析比较不同拓扑结构网络的指标有很多，比如平均和最大跳步数、对分带宽［21］、网络链路数量和交叉开关规模等。为了更好地将改进的混合拓扑结构Hybrid－Y和新型混合拓扑结构Hybrid进行比较，这里采用文献［1］中提出的网络开销评价指标，即链路（Links）数量、交叉开关（Switches）数量和交叉开关单元（SwitchingElements）规模。网络拓扑的硬件开销比较将采用交叉开关单元规模作为指标。网络的性能评价指标采用基本延时和吞吐率。基本延时和交叉开关单元规模的乘积越低，表示网络拓扑性能就越好；吞吐率和交叉开关单元规模的比值越高，表示网络拓扑的性能就越好。表2列出了这两种混合拓扑结构的链路数、开关单元规模、交叉开关数的计算式。表3列出了Hybrid－Y网络拓扑和Hybrid网络拓扑模拟实验的相关参数，包括基本延时（也称为0负载延时）、吞吐率（Throughput）、链路数、开关单元、交叉开关（Switches），以及性能比较的参数“吞吐率／开关单元”、“基本延时×开关单元”。当节点规模为64时，间接网络为Crossbar（间接网络级数为1）的新型混合拓扑结构Hybrid的基本延时要比间接网络同为Crossbar的改进的混合拓扑结构Hybrid－Y的基本延时要小，这是因为改进的混合拓扑结构Hybrid－Y的直接网络中每一维上有两个Crossbar，而新型混合拓扑结构Hy－brid只有一个Crossbar，因此Hybrid－Y网络中数据包的平均跳步数（Hop）要比Hybrid网络的大。但是，Hybrid－Y网络的吞吐率要比Hybrid网络的高，其原因是其线头阻塞（Head－Of－LineBlocking）效应较之要弱。对于间接网络级数大于1（即多级FatTree）的情形，Hybrid－Y网络与Hybrid网络的“吞吐率／开关单元”性能指标几乎持平，但是Hybrid－Y网络“基本延时×开关单元”性能指标要优于Hybrid。当节点规模增大到256时，间接网络为Cross－bar的Hybrid－Y网络的上述两项性能指标要明显优于Hybrid，分别提升了92％和37．8％。同时注意到，间接网络级数为3的Hybrid－Y网络的上述两项性能指标介于间接网络分别为2和4的Hy－brid网络。若继续将节点规模增大，达到1024时，从表3中可以观察到，间接网络为Crossbar或者多级FatTree的Hybrid－Y网络拓扑的两项性能指标比Hybrid网络拓扑的均要好。从上述的模拟结果分析可以得出这样的结论，Hybrid－Y网络的性能与物理开销和Hybrid网络相比，特别是在较大规模情况下，Hybrid－Y网络的性能与物理开销要优于Hybrid网络。在实际应用的时候，可以根据应用的需求寻求合适的参数配置，使得Hybrid－Y网络的优势更加突出。
4结束语
网络拓扑结构范文5
关键词: 自组网；拓扑控制；干扰；网络吞吐率
中图分类号:TP 393.03 文献标志码:A 文章编号:1672-8513(2011)05-0372-09
Research on the Interference-Optimized Topology Control Algorithms in Ad Hoc Networks
WANG Dong，CAI Xiaoli, LI Xiaohong
(College of Information Science and Engineering, Hunan University, Changsha 410082, China)
Abstract: Ad Hoc interference is one of the main causes influencing the network throughput rate. This paper summarizes and analyzes the existing topology control research achievements in the Ad Hoc network domain. By the computer simulation experiment, the paper compares several typical interference topological optimization control algorithms, and also points out the current characteristics of the interference topological optimization control algorithm. From the viewpoint of the topological control, the necessity to control the network bottleneck node number, the sparse balance and the bottleneck nodes are discussed. The research shows that through the optimization of sparse nodes between interference and through the bottleneck nodes in the network control reduced the number of the nodes in the bottleneck, not only optimizing the network interference, but also, to a certain extent, improving the existing routing algorithm.
Key words: Ad Hoc network；topology control；interference；throughput
Ad Hoc网络是由一组自治无线节点组成的支持多跳的自组织网络系统，由于自组织所具有的特性，无须基础设施，易于部署，因而在无线通信领域发挥着重大作用.
Ad Hoc网络中所有能量有限节点需要竞争共享的有限无线信道进行数据传输，有限能量与有限信道给Ad Hoc网络性能的提升带来一系列问题.在Ad Hoc网络中，若所有节点采用最大传输功率进行通信，那么随之形成的网络存在着两大问题：首先，能量有效性.邻居节点之间的通信往往不需要借助最大传输功率即可完成通信，由于传输功率以两点间距离的path loss指数方式增长［1］，因此近距离的传输采用低传输功率能在很大程度上节约网络节点的能耗开销；其次，干扰增加.最大传输功率一方面会增加网络节点的覆盖范围，从而增加位于覆盖范围内受干扰节点的数目，另一方面对于扰节点来说，随着干扰节点功率的增加，其所受到的干扰信号也越强.由此增加的干扰在很大程度上影响了网络吞吐率.因此，如何适当选取网络节点传输功率，从而降低网络干扰，提升网络传输性能，对于Ad Hoc网络来说是至关重要的.由于Ad Hoc网络使用共享的无线信道传输信息，其复杂的无线传输环境引入了一系列新问题，例如干扰.无线自组网中的干扰即网络中不同信号源的信号经过信道衰落后在同一接收机进行叠加，将严重影响接收机区分有效信息的能力，导致网络中冲突和重传的增加［2］.干扰严重影响网络传输能力及性能，降低干扰可减少网络冲突和重传，提升网络吞吐率及降低网络延迟［2-4］.
拓扑控制作为Ad Hoc网络中重要的研究领域之一，主要是通过控制网络中节点的传输功率使得最终生成的网络拓扑结构满足所需的性质，以降低节点的能量开销，延长网络生命周期，减小网络干扰，提高吞吐率，同时令网络具备一定的健壮性［5-7］.目前关于拓扑控制的研究往往通过图形学、随机过程、博弈论等各种方法学为网络设计合理的拓扑，并且通过控制节点的传输功率实现最终的拓扑结构.早期的拓扑控制算法大都借鉴于计算几何学中的一些经典邻近图，主要通过稀疏化来对网络干扰进行优化，以提升网络性能；鉴于此类拓扑控制算法大都为集中式算法，在很大程度上不能为现实网络所用，因此出现了分布式的拓扑控制算法.在这类算法中，大都采用局部优化策略，通过局部稀疏化构造的全网拓扑来达到优化网络干扰，提升网络性能的目的.至此，稀疏化作为网络干扰的优化途径之一，被广大学者接受并运用在各类优化策略中，直到2004年Burkhart［3］指出，现有的稀疏化方法并未明确地定量地证明其对网络干扰进行了优化，并给出了网络干扰模型与定量描述，第1次提出了干扰度的概念，并为后续学者接受，由此发展了新一代基于干扰度的干扰优化拓扑控制算法.
当前Ad Hoc网络中拓扑控制的研究开展得如火如荼，针对该领域现有成果的综合评述中并未针对干扰优化方面进行分析评价，因此本文通过选取干扰优化拓扑控制工作中一些较为重要的算法进行分析比对，以对当前工作进行总结分析，阐述各算法的性能及有待解决的问题并给出建议.本文在第1节首先对Ad Hoc网络进行建模，其次在第2节按照时间顺序发展对现有干扰优化拓扑控制算法进行分类并对典型算法进行了分析，接着在第3节对介绍的拓扑控制算法进行了模拟，并进行了拓扑特性分析，其中对基于干扰度的干扰优化拓扑控制算法进行了干扰特性分析，通过实验分析总结了现有干扰优化拓扑控制算法设计中尚未考虑到的欠缺点，本文最后在第4节探讨了今后应研究的问题，指明了下一步研究的重点和难点.
1 Ad Hoc网络模型
本文用无向图G=(V,E)表示Ad Hoc网络，G中的节点分布在二维平面内.V={v1,v2,…,vn}是拓扑图中节点的集合，n为网络节点个数.E={e1,e2,…,em}是拓扑图中边集合，m是网络中边条数.网络中所有节点都具有相同的最大传输半径Rmax，任意节点u的传输半径Ru是该节点到其最远邻居节点v的距离，其中u,v∈V.集合N(u)为网络中节点u在最大传输半径Rmax范围内的节点集合，相邻边集e(u)为以节点u为端点的边的集合.D(u, d(u,v))表示以节点u为中心，以节点u至节点v的欧几里德距离d(u,v)为传输半径的一个圆.
拓扑图中，若节点u的传输半径Ru大于其到节点v的欧几里德距离d(u,v)时，记做uv，由于本文采用双向化拓扑结构，若uv或vu成立，则认为节点对(u,v)互连，记做：u v.拓扑图G中，若存在路径p=(w0=u,w1,…wm-1,wm=v)，则称节点对(u，v)可达，记做u v，其中，节点对(wj，wj+1)满足wj wj+1，j=0,1,…,m-1，wk∈VL，k=0,1,…,m，若存在u v，v w，则u w成立.若拓扑图G中任意节点对(x,y)，x,y∈V都满足x y，则称图G连通，记为Connected(G)，反之则称图G不连通，记为UnConnected(G).SPu,v(G)为拓扑图G中满足u v的最短路径.
2 干扰优化拓扑控制算法的分类
我们根据时间顺序发展将已有干扰优化拓扑控制算法分为基于计算几何学、基于分布式信息和基于干扰度3类.
2.1 基于计算几何学的干扰优化拓扑控制算法
早期的拓扑控制研究主要关注于拓扑图的生成.其基本思路如下：首先，网络中所有节点生成UDG图(网络中所有节点通信半径都设置为最大传输半径时所形成的拓扑图)，然后，每个节点根据不同的邻近图规则选取逻辑邻居并将传输半径设置为覆盖所有逻辑邻居节点.很多计算几何学中的经典邻近图被借鉴用在拓扑控制算法中，例如MST(Minimum Spanning Tree)，RNG(Relative Neighborhood Graph)［8］ ，GG(Gabriel Graph)［9］和DTG(Delaunay Triangulation Graph)［10］等.
MST构造的拓扑图为1棵包含所有n个节点的树并满足边权值之和最小.在计算几何学中能够通过Prim［11］和Kruskal［12］算法构建MST，对应算法时间复杂度为O(mlog n)，MST的构造需要全局知识.对于同一个UDG图，生成的MST不唯一且满足任意点对之间的路径数恒为一.RNG［8］是由PM Lankford于1969年提出，构造的拓扑图不存在节点w，满足max{d(u,w), d(v,w)}
以上拓扑控制算法都是通过借鉴经典邻近图结构构建满足单一特性的稀疏图，以达到优化网络干扰，提升网络传输性能的目的［14］.早期的干扰优化拓扑控制算法是以追求优化图形的单一属性为目的，并没有将实际可行性列入考虑.因此该阶段大部分拓扑控制算法都需要节点获取全局网络知识作为前提以获取全局最优，对应的计算复杂度对于能源有限的Ad Hoc网络来说也是不现实的.
2.2 基于分布式信息的干扰优化拓扑控制算法
早期的拓扑研究主要是借由邻近图结构，将邻近图特性灌输到无线自组网中，并没有从Ad Hoc网络本身特点及性质出发，因此带来实际可行性方面的问题.于是，新的拓扑控制算法开始着眼于分布式获取所需信息，强调算法可分布式异步进行.同基于邻近图结构的拓扑控制算法相比，新的拓扑控制算法更为简洁且具有更强的实际可行性.本文接下来将介绍3个比较经典的分布式算法：LMST［15］、CBTC［16］以及KNeigh［17］.
2.2.1 LMST算法
LMST是基于节点位置信息的分布式拓扑控制算法，其基本思想是网络中每个节点只收集自己最大传输范围内的邻居节点信息以构建局部的最小生成树，得到本地的局部拓扑结构；然后，每个节点设置其传输功率为到达其最近一跳邻居所需的最小功率.整个网络拓扑由网络中所有节点的本地局部拓扑组成，作者通过反证法证明了LMST算法构造的拓扑图能够在原网络连通的前提下保证连通性.
与之前基于计算几何学的拓扑控制算法不同，LMST算法为一个分布式算法，因此LMST算法的第1步为信息交换：网络中每个节点通过在其最大传输功率范围内周期性广播Hello消息来获取邻居节点信息，Hello信息中包含该节点的id和地理位置，通过在数据通道或者单独的控制通道中周期性发送Hello消息，网络中所有节点能够获取到自己所需信息；信息交换步骤完成后，节点能够通过第1步所获取的邻居信息来独立异步地执行MST算法，构建自己最大传输范围内的MST，此步骤为局部拓扑的生成过程；节点设置其发射功率为到达所有邻居节点最小发射功率的最大值，这一步为LMST算法的最后一个步骤.
LMST算法有如下性质：
1) 连通性：该性质已通过反证法在文献［15］中得到了证明.LMST算法能够在降低节点发射功率的同时保证网络连通性；
2) 分布式：LMST算法中，每个节点都基于Hello消息所搜集到的信息来构造自己的拓扑结构并确定最终传输功率.这一点对于Ad hoc网络来说是非常重要的；
3) 链路双向性：LMST算法生成的拓扑图中所有链路都是双向的；
4) 有限节点度：LMST算法能保证所构建的拓扑结构中节点度有限(文献［15］证明节点的度不大于6).
2.2.2 CBTC算法
文献［16］提出了一种利用信号角度到达技术获得邻居角度信息的分布式拓扑控制算法(CBTC).同以往的拓扑控制算法不同，CBTC(Cone Based Topology Control)不需要节点收集位置信息，不需要GPS支持，而是基于角度约束，利用方向信息使得网络中的每个节点找到最小的传输功率Pmin，该功率确保以各节点为中心，角度为α的每个扇形区域都存在可以接收到Pmin的节点.已有文献证明，当α≤5π/6时，网络连通.CBTC算法是第1个实现了多项属性优化的分布式拓扑控制算法，满足在度有界前提下的energy spanner.
CBTC算法中，每个节点u试图在以节点u为中心的每个扇形区域α内，找到至少1个邻居节点以保证网络连通.节点u首先以最小传输功率来广播Hello信息并收集其他节点广播的Hello信息以便后续计算.如果以节点u为中心的任意一个扇形区域内不存在邻居节点，那么，节点u则增加传输功率进行新一轮广播直到满足任意扇形区域α中至少有1个邻居节点或者达到了节点u的最大传输功率时，CBTC算法结束.
CBTC算法有如下性质：
1) 连通性：若UDG图连通，那么当α≤5π/6时，CBTC算法生成的拓扑图连通；
2) 分布式：CBTC算法中，每个节点都基于Hello消息所搜集到的信息来计算自己的适当传输功率；
3) 链路双向性：CBTC算法生成的拓扑图中所有链路都是双向的.
2.2.3 K-Neigh算法
K-Neigh算法通过对邻居个数进行限制以达到优化网络传输性能的目的.在K-Neigh算法被提出之前，已有学者［18］提出Ad Hoc网络的性能同时受节点传输功率、节点分布以及节点密度等因素影响，网络性能与传输功率覆盖范围内的节点数量、平均路径长度等拓扑结构性能参数有紧密关系.在此基础上，文献［19］指出最小邻居数k和网络连通的关系，并证明了k∈O(log n)是满足拓扑图高概率连通的充要条件，其中n是网络中节点的个数.在已有理论基础上，文献［17］提出了一种简单易行的基于邻居个数的拓扑控制算法K-Neigh.
同以往拓扑控制算法不同，K-Neigh算法基于概率连通，作者通过大规模仿真实验获得最少邻居个数k与网络连通的关系：当网络节点数n在50至500之间时，取最小邻居数k为9时能保证Ad Hoc网络的连通概率接近1；当网络节点数n在50至500之间，取最小邻居数k为6时能保证Ad Hoc网络的连通概率接近95%.
当最小邻居数k值确定以后，K-Neigh算法非常简单明了.其基本思想是调整网络中节点的传输功率以保证网络中每个节点的邻居数小于等于给定的k值.K-Neigh算法不需要获取邻居节点的位置信息或者方向信息，通过采用物理层能量检测技术和距离估计机制［20］，我们能够在不增加额外开销的前提下获得邻居节点之间的距离信息以完成K-Neigh算法.同时，文献中的仿真实验表明K-Neigh算法在能耗和节点度等性能上都有所提升.因此，K-Neigh算法简单且实用.
2.3 基于干扰度的干扰优化拓扑控制算法
由于稀疏拓扑具有稀疏性、节点度数低等特性，因此人们普遍认为稀疏化也意味着低网络干扰.因此，大量拓扑控制算法通常利用稀疏化达到优化干扰的目的，而很少考虑明确定义干扰以度量节点间干扰以及网络干扰.然而，Burkhart［3］揭示稀疏性与低网络干扰之间并没有确定的关系，即，一个具有低节点度(稀疏化)的算法并不能确保其最终的拓扑结构是低干扰的，该问题在文献［3］中通过指数节点链得到了证明.证明了稀疏性不等同于低干扰以后，Burkhart提出关于干扰的定义，并建立对应的干扰模型.
文献［3］首先介绍了链路干扰模型，该模型认为，节点的所有邻居都会对该节点产生干扰，并定义链路的干扰值为两端正在通信的节点覆盖范围内的所有邻居节点数目.例如网络中节点u向节点v发送信息，这时候u会选择一个发送半径r，此时u会影响以自己为圆心，|u,v|为半径的圆覆盖区域内的所有节点，即Cov (u)={w∈V |w is covered by D(u,Ru )}，其中D(u, Ru)表示以u为中心，以节点u的传输半径为半径的1个圆.边e(u,v)的覆盖范围就是以u和v分别为圆心r为半径的1个并集，即Cov (u,v)={w∈V|w is covered by D(u,|u,v|)}∪{w∈V |w is covered by D(v,|v, u|)} | .链路e(u,v)的干扰度为被节点u和v的传输所影响的网络节点个数，定义网络干扰度为网络中链路所具有的最大覆盖范围.
作为拓扑控制研究的一项开创性工作，Burhart对于边覆盖和干扰度的合理定义为后续学者广泛接受.链路干扰模型被广泛采用，有学者［21］基于链路干扰模型，针对数据转发的端到端投递特征，提出了对应的路径干扰模型，定义数据投递路径的干扰值为组成此路径上所有链路的干扰度之和，定义网络干扰度为平均路径干扰度.
本节接下来将根据以上介绍的干扰模型，介绍对应的干扰策略.基于链路干扰模型，Burkhart提出了链路干扰最小的干扰优化拓扑控制算法LIFE(Low Interference Forest Establisher)；基于路径干扰模型，Johansson［4］提出了路径干扰最小的干扰优化拓扑控制算法API(Average Path Interference).
2.3.1 LIFE算法
Burkhart［3］认为片面减少网络中链路的数量、长度以及节点度不一定能保证节点之间的干扰降低，以往拓扑控制算法所采用的经典邻近图结构都不能完成干扰最优化，因此基于所提出的链路干扰模型，提出了一种致力于降低节点信道之间干扰的算法LIFE.从构造上看，LIFE类似于典型的MST邻近图结构.不同于经典MST算法，LIFE采用链路干扰度而不是节点对间的欧几里德距离作为权重，其中链路干扰度e(u,v)实际上等同于以边长|uv|为半径、圆心分别为u和v的两圆覆盖范围并集内的覆盖值，即LIFE是一个以链路覆盖值作为权重的连接网络n个节点的MST.
LIFE算法有如下性质：
1) 集中式：LIFE算法实现需要全局位置知识，为一个集中式算法.LIFE的提出是拓扑控制领域的一项开创性工作.LIFE中关于干扰的定义，为后续研究者提供可贵的研究参考；
2) 连通性：若UDG图连通，那么LIFE算法生成的拓扑图连通；
3) 最小干扰度：由LIFE算法生成的拓扑图是一个具有最小干扰度的树(该点在文献［3］中得到了证明)；
4) 链路双向性：LIFE算法生成的拓扑图中所有链路都是双向的.
2.3.2 API算法
由于Ad Hoc网络为一个多跳无线网，因此网络中主机还需承担起数据转发的责任，因此Ad hoc网络的数据传输实际为一个端到端的多跳传输过程.Burkhart提出的链路干扰模型能很好地描述能直接相互通信的节点对之间的干扰情况，然而定义网络干扰为网络中最大链路干扰度，只能反映网络的局部状况，或者说反映网络最差干扰情况的链路.假设2个网络，其中一个网络分布不匀，只有一部分区域为高干扰区，其余区域都为低干扰区，另外一个网络则分布均匀，但是都为高干扰区，依据Burkhart定义的网络干扰度量，则这2个网络的干扰状况一样.然而，文献［4］指出，网络干扰情况通过链路干扰度来衡量是比较片面的，因此在链路干扰模型基础上，建立路径干扰模型，并给出了致力于降低网络路径干扰的干扰优化算法API(Average Path Interference).
API算法主要由2步组成，第1步是在UDG图基础上构建GG图；第2步为干扰优化，通过在GG图基础上删除干扰度过大的边来完成.
首先，构建GG图：
For each node u:
1. Broadcast a hello message with maximum signal strength.
2. For each received hello message:
2a. Denote the received signal strength from v as Prec
2b. Evaluate the distance d from node u to neighbor v, using the signal degradation model.
2c. Calculate energy cost c(u,v) needed for sending a message from u to v based on cost function.
2d. Respond to v with the energy cost value.
3. Wait until all neighbors responds to u with c(v,u),where v is the neighbor.
4. Broadcast to every neighbor the value of c(v,u) for every neighbor v.
5. For each neighbor v:
Activate link(u,v) if no node w exists
such that c(u,w)+ c(w,v) ≤ c(u,v)
第2步，在构建好的GG图上移除具有高干扰度的链路：
For each node u:
For each neighbor v:
If there exists a node w such that
Cov(u,w) + Cov(w,v) < Cov(u,v)
Mark (u,w) and (w,v) to retain.
Otherwise, mark (u,v) to retain.
Remove all unmarked links.
3 拓扑结构分析
本节主要采用实验模拟来对上节介绍的拓扑控制算法进行拓扑特性分析.在模拟实验中，首先在给定区域中随机分布n个节点，每个节点以设定的最大传输半径构建UDG图，若该UDG图连通，则在该UDG图上实现本章介绍的9种代表性拓扑控制算法：MST，RNG，GG，DTG，LMST，CBTC，K-Neigh，LIFE和API.其中CBTC中取参数α为5π/6，即2个邻居之间的角度值，K-Neigh中选参数k为9，即邻居个数取值.
3.1 拓扑控制算法的模拟
通过在一个1000m×1000m的区域中随机分布50个最大传输半径为250m的节点，首先生成UDG拓扑图，若UDG连通，则根据以上介绍的9种拓扑控制算法生成对应的网络拓扑图见图1.
通过图1可知，以上干扰优化拓扑控制算法都是在原有的UDG拓扑上进行稀疏化以达到优化干扰，提升网络性能的目的.然而，通过观察以上10幅图可知拓扑结构稀疏化增加了网络瓶颈节点数量.为了考察这些拓扑控制算法在稀疏化的同时对网络瓶颈节点带来的影响，下一节将详细分析以上给出的9种算法所生成拓扑结构的特性.
3.2 拓扑控制算法的特性分析
通过对整个拓扑控制发展过程的研究，发现拓扑控制都是在原有的UDG网络上进行稀疏化即缩减网络节点半径以达到优化干扰，提升网络性能的目的.目前普遍观点认为：网络拓扑结构稀疏化可以优化网络干扰，提升网络性能.然而网络拓扑结构的稀疏化也会不可避免地带来网络瓶颈节点问题，网络中瓶颈节点的个数会随着网络密度的增加而减少.通过仿真实验和分析，我们将研究网络中瓶颈节点的个数是否会随着网络密度的增加而减少.这是本文研究在干扰优化拓扑控制算法中加入瓶颈节点考虑的动机.
本节首先从节点度和节点传输范围2方面来考察干扰优化拓扑控制对网络拓扑的提升，然后从瓶颈节点产生率来考察由于干扰优化拓扑控制所带来的稀疏化对网络拓扑带来的潜在性能影响.
考察当网络节点数从50以10为增量递增到160的时候，所生成的拓扑图在节点度、节点传输半径、网络瓶颈节点生成率以及网络瓶颈节点数量4个方面进行比较分析.节点随机分布在1000m×1000m的方形区域中，节点设置最大传输半径为250m.在不同网络密度下随机生成1000幅连通图，再在对应连通UDG图上运行以上9种拓扑控制算法，最后对每种算法所生成的拓扑结构进行性能参数计算并取平均值.
3.2.1 节点度
在无线自组网中，从单个节点角度来说，希望保持通信的邻居数越少越好，因为这样一来，较少的邻居节点意味着较少的数据转发量，能够降低节点能耗，延长节点生存期，然而从整个网络来说，则希望每个节点的通信邻居数保持在适中水平.通过图2(a)可知，UDG图中节点度是随着网络密度的增加而持续增加的，这是因为在UDG中，节点的传输半径不随网络节点密度变化而变化，其传输半径固定为最大传输半径，即250m，那么随着网络密度增加，节点周边的邻居节点密度也随之增加，因此在维持半径不变的情况下，网络中节点度持续增加.节点度的增加一方面能够使得网络更为稳健，任意一段链路的失效不会使得网络不连通，然而另一方面，节点度增加也增加了网络干扰，正如在本章开头所介绍的，节点度增加一方面表示节点的覆盖范围增加，从而位于覆盖范围内的受干扰节点数也随之增加，另一方面对于扰节点来说，其所受到的干扰信号也增强.由此，增加网络密度而随之增加的网络干扰在很大程度上影响了网络吞吐率.可以看到，在图2(a)中，RNG，GG，DT，MST，LMST，CBTC，K-Neigh，LIFE和API这9种拓扑控制算法都很好地将网络节点度控制在均衡水平，其生成的拓扑的节点度变化不明显，并且节点度数都较小，处于10以下，对应的拓扑结构较稀疏，说明拓扑控制算法能够有效控制网络节点的度，能够优化网络中节点间干扰.
3.2.2 节点传输半径
节点传输半径为该节点与其相距最远的邻居节点的欧几里德距离.在无线自组网中，无线传播模型采用自由空间模型，则对应的节点传输半径与其发送功率成平方比递增，随着半径的增加，节点所需要的发射功率也要增加.由图2(b)可以看出，随着网络密度的增加，只有UDG算法的半径维持不变，其余拓扑控制算法所生成的拓扑图中节点半径都随着网络密度增加而降低，这说明拓扑控制算法能够在网络密度增加的时候降低平均节点半径，使得其覆盖范围内的节点数目不随着网络密度增加而增加，优化网络中节点间干扰.
3.2.3 网络瓶颈节点
本文中的瓶颈节点是指其失效能够使得网络不连通的节点，本节中的瓶颈节点生成概率为1次模拟拓扑中出现瓶颈节点的数目与网络节点数目的百分比，我们采用1000次模拟的平均值.
拓扑控制算法主要通过降低网络中节点至某适合水平，以构造一个较稀疏的网络拓扑，达到优化节点间干扰，提升网络性能的目的.随着网络结构稀疏化，不可避免地会带来瓶颈节点的问题.众所周知，网络中瓶颈节点的个数会随着网络密度的增加而降低，瓶颈节点生成概率也将随着网络密度的增加而降低.然而，通过图2(c)和图2(d)，我们将说明在现有的干扰优化拓扑控制算法中加入瓶颈节点考虑是必不可少的.
图2(c)给出的是在1000次仿真下各算法所生成的拓扑结构中存在的平均瓶颈节点个数.可以看到，随着网络密度的增加，除了UDG和个别拓扑控制算法所生成的拓扑中瓶颈节点个数并未增加，大部分拓扑控制算法所生成的拓扑结构中瓶颈节点个数都相应增加了，与此同时，该结果与图2(d)中所展示的1000次仿真下各算法所生成的拓扑结构中存在的平均瓶颈节点生成概率的结果相对应：除了UDG和个别拓扑控制算法所生成的拓扑中瓶颈节点生成概率有所减少，大部分拓扑控制算法所生成的拓扑结构中瓶颈节点生成概率都不变，甚至还有随着密度增加概率增加的情况.
1） 在所有模拟实验中，都是以UDG为连通图作为前提.因此，UDG拓扑中的瓶颈节点数目都为0，对应的瓶颈节点生成概率也为0；
2） 像MST，LMST还有LIFE，都是采用典型MST几何结构，所生成拓扑结构特征与网络密度并无太大关系，综合图2(a)我们可以看到，MST和LIFE都保持节点度为1，这就说明随着网络密度增加，MST和LIFE拓扑结构中的节点都会缩短其传输半径以维持节点度为1，从全网络来看，瓶颈节点个数是会逐渐增加的，因为密度只是影响了节点半径，未对节点度产生影响，所以瓶颈节点会随着网络密度的增加而增加，而瓶颈节点生成概率将保持在一个平稳状态，如图2(d)所示，而LMST作为MST算法的分布式实现，是在节点的最大传输范围内构建MST树并保留最近一跳，其局部拓扑也保留了MST结构的特征，节点度不变，从全局来看，密度的增加也只是影响了网络中的节点半径，因此瓶颈节点会随着网络密度的增加而增加，对应的瓶颈节点生成概率也保持在一个平稳状态，如图2(d)所示；
3） 其余的拓扑控制算法，都是以维持一个稳定的局部拓扑作为目的，网络密度的增加只是对其局部拓扑的规模产生了影响，例如节点半径，但是对应的局部拓扑结构并不会产生变化，在这种情况下，网络密度增加只会缩短局部拓扑中的节点半径，不会改变对应的节点度［21］，因此对应的瓶颈节点的数目也会随之增加，由于未对产生瓶颈节点的因素有影响，因此瓶颈节点生成概率将维持在一个平稳状态.
4 结语
稀疏化作为优化网络性能的途径已被广泛认同.然而，稀疏化导致网络中出现此类节点：其邻居集可划分为2个或多个不相交的非空集合，并且任一集合中的任一节点不属于其他集合中任一节点的邻居集，当这些不同节点集中的节点需要相互通信时，只能通过该节点的中继，此类节点称为瓶颈节点.由于瓶颈节点需要利用有限的无线信道资源为网络中大部分数据通信提供转发服务，其经常成为网络性能提升的瓶颈，减少网络瓶颈节点数量能够提升网络性能.然而，由于节点自由分布以及局部信息的限制，导致瓶颈节点在Ad Hoc网络中的检测成为一个亟待解决的难题.为了舒缓瓶颈节点处的转发压力，已有很多学者从负载感知路由提出了对应的解决方法.路由算法是基于当前网络拓扑结构，通过对应的路由策略选取已建立的链路来完成路由搭建，因此可以说，拓扑结构在一定程度上会影响路由算法的有效性［6,22］.
现有的拓扑控制算法通过稀疏化在优化网络性能的同时也增加了网络中瓶颈节点的数量，而瓶颈节点数量的增加则需通过路由算法来提升网络性能.由于路由算法有效性在一定程度上依赖于当前网络拓扑，因此如何从拓扑控制角度来控制网络瓶颈节点数目，权衡稀疏化与瓶颈节点成为一个难点.基于以上分析，本文认为较优的拓扑控制算法应当分成拓扑稀疏化与瓶颈节点控制这2步，一方面通过稀疏化优化节点对间干扰，另一方面则通过瓶颈节点控制降低网络中瓶颈节点个数，不仅优化网络干扰，并且从一定程度上提升现有的路由算法效率.现有的大部分干扰优化拓扑控制研究并未对此点进行深入探讨.
参考文献:
［1］MHATRE V P, ROSENBERG C P. MAZUMDAR R R . On the capacity of ad hoc networks under random packet losses［J］.IEEE Transactions on Information Theory, 2009,55(6):2 494-2 498.
［2］张信明,刘琼,代仕芳,等.移动Ad Hoc网络通信量相关干扰感知路由协议［J］.软件学报,2009,20(10):2 721-2 728.
［3］BURKHART M, RICKENBACH P V, WATTENHOFER R, et al. Does Topology control reduce interference?［C］//Proceedings of the 5th ACM international symposium on Mobile ad hoc networking and computing. Roppongi Hills,Tokyo,Japan:ACM,2004:24-26.
［4］JOHANSSON T, CARR-MOTYCKOV L. Reducing interference in ad hoc networks through topology control［C］//Proceedings of 3rd ACM Joint Workshop on Foundations of Mobile Computing,Cologne,Germany:ACM,2005:17-23.
［5］SANTI P. Topology control in wireless ad hoc and sensor networks［J］. ACM Computing Surveys.2005, 37(2):164-194.
［6］RAJARAMAN R. Topology control and routing in ad hoc networks: a survey［J］. ACM SIGACT News.2002:60-73.
［7］ZHAO LIANG, LLOYD E L, RAVI S S. Topology control in constant rate mobile ad hoc networks［J］.Wireless Networks,2010,16(2):467-480.
［8］TOUSSAINT G T. The relative neighborhood graph of a finite planar set ［J］. Pattern Recognition,1980,12(4):261-268.
［9］GABRIEL K R, SOKAL R R. A new statistical approach to geographic variation analysis ［J］. Systematic Zoology,1969,18:259-278.
［10］GAO J, GUIBAS L, HERSHBERGER J, et al. Geometric spanner for routing in mobile networks［C］// Proceedings of the 2nd Acm Symposium On Mobile Ad Hoc Networking & Computing (Mobihoc’01). Long Beach: ACM,2001：4555.
［11］PRIM R C. Shortest connection networks and generalization ［J］. Bell System Tech, 1957, 36:1 389-1 401.
［12］KRUSKAL J B. On the shortest spanning subtree of a graph and the traveling salesman problem［C］//Proceedings of the American Mathematical Society, 1956,7(1):48-50.
［13］AURENHAMMER F. Voronoi diagrams―A survey of a fundamental geometric data structure［J］. ACM Computing Surveys,1991,23(3):345-405.
［14］路纲,周明天,牛新征,等.无线网络邻近图综述［J］.软件学报,2008,19(4):888-911
［15］LI N, HOU J C, SHA L. Design and analysis of an mst-based topology control algorithm［C］// Proc IEEE INFOCOM′03. San Francisco,2003:1 702-1 712.
［16］LI Li, HALPERN J Y, BAHL P, et al. A cone-based distributed topology-control algorithm for wireless multi-hop networks. IEEE/ACM Transactions on Networking,2005,13(1):147-159.
［17］BLOUGH D M, LEONCINI M, RESTA G, et al. The k-neigh protocol for symmetric topology control in ad hoc networks［C］// ACM MobiHoc.Anapolis:ACM,2003, 1-3.
［18］OGIER R, LEWIS M, TEMPLIN F. Topology dissemination based on reverse-path forwarding［R］. MANET Internet Draft,2003.
［19］LIU L, LI B. Mobile grid: capacity-aware topology control in mobile ad hoc networks［C］// 11th International Conference on Computer Communications and Networks. Miami,2002:570-574.
［20］XUE F, KUMAR P R. The number of neighbors needed for connectivity of wireless networks ［J］. Wireless Networks,2004,10(2):169-181.
［21］王东. 节点密度对优化Ad Hoc网络生存期的影响的研究［J］.云南民族大学学报:自然科学版,2010,19（4）:235-240.
［22］JIA Lujun, RAJARAMAN R, SCHEIDELER C. On local algorithms for topology control and routing in ad hoc networks［C］//Proceedings of the 15th annual ACM symposium Parallel algorithms and architectures. California, 2003:220-229.
收稿日期:2011-05-20.
网络拓扑结构范文6
随着计算机网络的飞速发展，传统的网络模型已经很难对计算机网络拓扑特性做出客观的描述和研究。针对这个现象，复杂网络理论的产生和应用，为计算机网络的拓扑发展带来了新的平台和思路。对于复杂网络理论在计算机网络拓扑中的分析已经成为计算机网络领域研究的重要课题。
二、复杂网络和计算机网络拓扑的基本理论
（一）复杂网络理论的含义及其复杂性
复杂网络是指具有内部相似、自行组织、吸引因子、小区域、无标度中的一部分或者全部的网络。其复杂性主要体现在以下六个方面：①结构的复杂性，表现在网络的节点数量较大。②节点的多样性，网络中的所有组成部分，代表的各种事物均为复杂网络理论中的节点。③连接的多样性，指的是网络中节点的连接方式不一致。④动力学的复杂性，指的是节点之间的复杂性，能够产生多样的结构特征。⑤网络结构的变化性，指的是网络节点之间消失和连接产生就像网页随时断开和连接一样，使得网络结构不断的发生变化。⑥多重复杂性的融合，指的是上述所有复杂性的结合表现出的复杂性。此外，复杂网络理论有小世界、集团集聚程度更加密集和幂律的度及介数涵盖的范围不断扩大等三种特性。
（二）计算机网络拓扑技术及分类
计算机网络拓扑最早是由瑞士数学家欧拉在1736年提出的，主要是用于连接计算机网络和传输不同设备之间数据的一种方式。不同的网络设计要选择适合的网络拓扑方式，在网络拓扑结构中，拓扑技术是以图像的方式来表示多种设备之间的相互关系。计算机网络拓扑的主要类型有星行结构、环形结构、总线型结构、混合拓扑结构、分布式结构等。由于计算机的分布和数据传输电缆的布置存在很大的差异性，每一种网络拓扑结构都有其相应的优缺点，因此在计算机网络拓扑形式的使用上，要具体问题具体分析。
三、复杂网络理论在计算机网络拓扑中的具体应用分析
（一）计算机网络的同步行为现象分析
这主要是指计算机各个网络节点之间的同步行为，在复杂网络理论中，网络节点之间的同步是较为常见的一种现象，主要是受网络拓扑和各节点之间的动力学性质决定的。但是值得注意的是，这种同步行为并不都是有益的，如由多个路由器发出路由信息的网络，其同步行为包括了发出同一种路由信息和同时不发送信息，这就很有可能会使得网络出现拥挤或者瘫痪的现象。从计算机网络技术的发展来看，人们采取避免计算机网络出现同步行为的措施并没能完全奏效，经常会出现一种同步行为结束，另一种同步行为又产生的现象。因此，如何有效杜绝计算机网络的同步行为现象仍然是人们研究的课题。
（二）计算机网络拓扑行为的演化模型
计算机网络拓扑行为的演化模型由复杂网络演化模型逐步转变为了局部演化模型，这两种演化模型都是从路由器和自治域两个不同的层次来描述计算机网络的拓扑结构的。从路由器上看，各个路由器相当于各个网络节点，而路由器之间的物理连接相当于边。从自治域上看，在边界网关协议的基础上，如果两个自治域之间对等连接的话，就说明这两个节点之间是有一条边相连的。复杂网络演化模型演化出的结果很大程度上出现富者更富，穷着更穷的现象，即那些新加入的用户会倾向于那些品牌好、质量好、连接数量多的网络服务商。该模型遵循的偏好连接原则是基于整个网络上的，与优先考虑连接到本地区的服务器或路由器的实际不符。而局部演化模型的偏好连接倾向性是在局部信息的基础上形成的，一定程度上克服了复杂网络演化模型的缺陷。
（三）计算机网络脆弱性和鲁棒性的动力学模型
1.计算机网络的鲁棒性。计算机网络的原始功能是保证军事资料的安全性，这样的保证就是所谓的鲁棒性。鲁棒性是指在计算机网络中的某个区域或节点中出现问题或故障时，不会扩散到整个计算机网络系统，计算机还能保持正常的运行。相关研究表明，一般在一个网络系统中，只要有百分之二十左右的正常区域和政策阶段就能够保障计算机网络的正常运行。
2.计算机网络的脆弱性。虽然计算机网络有鲁棒性的动力学模型，但是一旦计算机网络系统中的重要区域或节点受到破坏时，整个计算机网络将会异常脆弱。更有甚者，如果计算机网络中一小部分的中心阶段被破坏后，整个网络就会陷入瘫痪的境地，计算机网络也无法保障正常运行。
（四）计算机网络病毒扩散模型和病毒防治的方法
网络安全影响了计算机网络的日常运行，而影响网络安全的因素主要是病毒的袭击和扩散。因此，复杂网络理论在计算机网络拓扑中的应用，应该采取有效的措施来抑制计算机网络病毒的扩散，减少病毒的传播，避免病毒对计算机网络损害后带来的计算机网络安全问题。复杂网络理论开始应用于计算机网络拓扑行为中时，人们开始以复杂网络为基础不断研究和探索出新的防御病毒的方法，且取得了一定的进展。比如在规则网络中，人们经过研究发现计算机网络病毒只有在小世界中才能轻易的传播，在复杂网络理论里，计算机网络感染病毒的可能性较小，一旦感染的话，网络系统将会受到大面积病毒的袭击，这对预防计算机病毒的入侵技术而言是一大挑战。防御计算机网络病毒工作的开展，必须建立一个科学系统的防御病毒扩散模型，模型需要遵循的原则有网络的拓扑结构形式、知晓病毒的传播原理、网络拓扑结构形式和知晓病毒传播原理之间的关系和作用。此外，在计算机网络病毒扩散模型的构建和病毒防治的过程中，要格外注重预防网络病毒的产生和传播的速度，通过网络的拓扑结构和复杂网络理论来做好计算机网络的抗病毒工作。
