基于抗毁性和最小费用的网络优化设计方法

李丹镝

(中国电子科技集团公司第五十四研究所，河北石家庄050081)

0 引言

通信网根据应用需求通常分为干线网和接入网。由于受到使用规模、使用环境和组网设备等因素的限制，在设计通信网络拓扑时，首先要对干线节点的布设进行优化，用以实现广域覆盖，同时要对接入网进行优化设计，以满足用户入网及业务流量的需求，最终的结果是保证使用时的业务需求。这就提出了如何合理、可靠、迅捷地进行通信网网络规划的问题。

通信网设计主要应用2个设计原则:①优化网络拓扑，求解目标为最小链路消耗和费用;② 受限资源约束，求解目标为网络的高抗毁性。以上2条设计原则是相互冲突的，要达到最小费用，最便捷的措施便是减少网络的冗余链路和备份链路，这会在一定程度上影响网络的抗毁性;另一方面提高网络抗毁性的主要措施便是增加冗余链路和备份链路，此措施会影响链路消耗增加费用。基于通信网的设计提出了一种在费用和抗毁性能之间综合考虑、优化折衷的设计方法，设计目标是具有一定抗毁性能的最小费用网络拓扑。

1 通信网络模型化基本原理

1.1 通信网络的模型化

通信网通常布设成栅格状或准栅格状，如图1所示［1］，用于覆盖相应的地域范围。在进行网络结构设计时，把实际的通信网利用图论理论来进行模型化，即把通信网表示为一个带有权值的图G，如图2所示，权值包括4个部分［V，E，M，L］。

图1 通信网网络结构

图2 通信网模型化

其中，V表示非空节点集合，用于抽象化网络节点;E表示边集合，用于抽象化节点间的有效链路;M与L存在映射关系，表示为M:E→N×N。L与E也存在映射关系，表示为L:E→Li(Li是标号的集合Li=a，b，c…)。

1.2 网络抗毁度定义

通信网完成特定任务的有效程度与其底层传送网的稳定性密切相关，同时稳定性又是影响网络抗毁性的主要因素。影响网络抗毁性的2个方面为［2］:① 在网络出现阻塞或异常流量分布时网络的承受能力;②由于自身设备故障和受敌方攻击时产生的物理故障。在进行网络设计时，需要定义一个精确估算网络抗毁性的量度。

从通信网的抗毁角度考虑，网络最差的情况是节点间完全分离。为了能够定量地分析、评估网络的抗毁性能，提出了节点抗毁因子(Node Invulnerability Factor，NIF)、链路抗毁因子(Link Invulnerability Factor，LIF)［3］，这 2 个因子用来表示网络从连通状态变为全分离状态的复杂程度。为了从局部来衡量一个节点或一条链路对网络抗毁性能的影响程度，定义了节点分割因子(NSI)和链路分割因子(LSI)来分别定义每个节点和链路对维持网络连通性贡献的量度。

1.2.1 NIF

NIF从节点角度来反映网络的稳定度，即平均必须去掉NIF个节点才能使网络处于完全分离状态。定义如下:

式中，NCFj为图G的第j个独立部分的节点抗毁因子;n为图G分离部分的个数;Ni为第i条分解路径所消除的节点数;P(Ni)为第i条分解路径出现的概率;D为各独立部分分解路径的总条数。

计算NIF，首先确定所有可能的关键割点集合(这些割点集合的消除可能导致网络的完全分离)。接下来计算每个分割序列出现的概率，最后利用此概率乘以这个序列中节点的数量产生一个值，即得到NIF。

1.2.2 LIF

LIF用来衡量各链路对于网络的整体连通性的影响程度，其计算公式如下:

式中，LIFi为图G的第i个分割部分的链路抗毁因子;Si为第i个分割中生成树的边数;S为图G的生成树所包含的边数;Ti为分割部分i的生成树数;Ei为分割部分i的边数;Ni为分割部分i的节点数;n为图G中分割部分数。

进行LIF计算时，首先要计算网络中各个部分的生成树数量，其次计算各分割部分中各链路对生成树的影响程度，最后确定各分割部分对总LIF的影响程度。

1.2.3 NSI

在网络设计过程中，只定义LIF和NIF并不能提供改善网络抗毁性的有效措施。为了解决此问题，提出了局部指标NSI和LSI，用来衡量各链路或节点对于网络连通性的影响程度。利用NSI和LSI可以判断各节点或链路对于网络抗毁性的重要程度，从而可以着手进行网络整体抗毁性的改善。

对于一个特定节点，在不同长度路径中的贡献的求和就可得到其节点分割因子:

式中，m为Ki(不同路径长度)的数量;Cni用来表示路径长度Ki且含节点n的分割路径占Ki所有路径的百分比;Wi为Ki的路径出现的概率;NSI(n)用来量度节点n对网络连通性的影响程度。

1.2.4 LSI

为了衡量各链路对于网络连通性的影响程度，计算此链路对生成树的影响程度，即包含该链路的生成树在总生成树中的比率。具体解释如下:

式中，Tj为含链路j的生成树数量;TS为生成树总量;LSI(j)定义了链路j对网络连通性的影响程度。

综上所述度，采用LIF和NIF从整体上度量网络抗毁性，采用LSI和NSI从局部评估各链路和节点对网络抗毁性的影响程度。通过分析可以发现，NSI值越大，则该节点对网络连通性的影响程度越大;LSI越大，则该链路对网络连通性的影响程度越大。

2 饱和割集算法

2.1 基本原理

割集是所有可将连通图变为分割图的链路集合［4］。如果割集中所有链路容量均与额定容量相等，则此割集为饱和割集。正常情况下，网络中有许多割集，随着业务量的不断加载，其中之一的割集首先处于饱和状态。如果去掉这些饱和链路，则会造成网络的分割。这种情况下如果想增加系统的总容量，只能增加单一链路容量或增加其他链路，这便是运用了饱和割集的基本原理［5］。

在实际网络运行过程中，可以统计得到各链路利用率，如果将利用率高的链路断掉，则会使网络分割成2个部分，这2个分割部分的总业务量非常接近于饱和割集链路的总流量。即

式中，NDi为分割部分i中节点数;Ke为节点对间的业务量;fi为割集链路的总流量。

综上可以看出，饱和割集即是网络总容量的极值。Ke的理论上限为:

式中，Sj为最小割集;S为割集。由于饱和割集的总流量与容量相近，利用式(6)有:

从式(7)可以得出结论，Ke值与理论上限非常接近;增加Ke的唯一途径是增加割集容量。

因此，在任一分割部分内部增加新链路并不能增加割集容量，从而也不会改善网络的吞吐量。所以，通过增加链路来提高网络吞吐量，必须考虑到连接2个分离部分的潜在链路。

2.2 算法流程

饱和割集法的主要流程如下:①修正网络后执行路由算法，产生新的链路流量;②确定饱和割集;③对网络吞吐量进行判断，若不满足指标要求，则执行ADD-ONLY算法，从而产生新的干线流量;④执行DELETE-ONLY算法，选择连接2个部分中费用最小的链路;⑤ 判断网络抗毁性能，若能够满足抗毁性指标，则停止运算，否则转到①。

2.3 饱和割集确定和消除

饱和割集体现了网络中流量最大的位置。如果不能够满足网络吞吐量要求，可增加最少费用链路，从而在饱和割集中去除业务量。

2.3.1 链路增加算法——ADD-ONLY

采用 ADD-ONLY 算法［6］来确定节点 K1、K2的位置。增加新链路要满足以下约束条件:连接2个分割部分且费用最小。假设所有链路容量相同，则满足此约束条件的将是最短链路。事实上启用最短链路对割集位置的改变很小，对吞吐量的改善也非常有限。

另一个可采用的方法是连接2个分割部分中业务最繁忙的“中心节点”。但是对于较大规模网络，割集与“中心节点”的距离较远，连接它们之间链路的费用极高。

DISTANCE2算法采用启发式算法来得到“中心节点”。在增加链路时，链路两端的节点与割集节点至少要相距2条链路。如果不可能的话(部分体积过小)，至少保留与割集节点邻接的节点(一个单位距离)。

2.3.2 链路删除算法——DELETE-ONLY

DELETE-ONLY算法的起始拓扑是高连通拓扑。当网络吞吐量大于指标要求时，每次迭代只需消除一条链路，从而达到吞吐量和总费用的要求。用Ei来表示链路利用率和费用，定义如下:

式中，di为链路i的费用;Ci为链路 i的容量;fi为链路i的流量;(Ci－fi)/Ci为相对的剩余容量。

删除节点的策略为:①每次去掉链路Ei值最大的一条，即去除的链路是最高费用、最低利用率的;②如果消除此链路产生了独立节点，则不消除此链路;③如果初始网络是K-连通的，则经过DELETEONLY算法后产生的网络也应是个K-连通的，否则不消除此链路;④如果Ei最大的链路存在于饱和割集中，则不消除此链路。

3 抗毁通信网设计原理

如前所述，网络的抗毁性和费用是相互制约的，同时在进行网络设计时又必须重点考虑这2个因素。分别设计了针对费用效益比、链路容量和网络抗毁性能的综合网络模型。

模型中已知节点的位置和节点间的业务量需求。设计最小费用连通网络是在满足初始条件的情况下使所有节点连通，这样问题就变成了如何求解全连通网络下最小权值和的生成树。这正是所要求的具有最佳费用效益比的初始连通网络拓扑结构。

在具体的通信网设计过程中链路权值可以具有多重含义，可用于表示两点间的距离、地形复杂度等。具体定义如下:

式中，dij为节点 i、j间的实际距离;Pij为节点 i、j间的地形复杂度;mij为节点i、j之间的业务量总和;α为调整因子。

首先得到全连通网络(具有边权值)，再利用如下算法寻找最佳费效比的生成树。

①选择节点i、j之间的连接，使其边权值尽可能小;

② 若已选定 e1，e2，…，ei+1，则能从 E{e1，e2，…，ei+1}({e1，e2，…，ei+1}的补集)中选项取 ei+1，使得W(ei+1)最小的权且满足G为无环路图。

③当第②步无解时则终止。

这样便得到了初始连通拓扑的生成树，其中边权同时考虑了业务量和费用的约束，初始连通拓扑包含了费用需求和业务量需求的双重因素。

网络设计应该是在初始连通网络拓扑的基础上，通过增加/删除链路来改善网络综合性能，下面提出增加/删除链路的原则。

如前所述，消除所有饱和的割边，将使网络分离成2个部分K1、K2，对这2个部分的所有节点组合计算下列值:

增加链路的原则是:选择AL(i，j)最大的一对链路节点间追加一条链路，这样不仅均衡了节点的抗毁性，同时也考虑了业务量需求、地形复杂度和实际距离等因素。

当网络达到一定的规模后，将产生许多冗余的资源，这些冗余的资源并不一定都是必要的，这时就要依据一定的原则删除一些链路，为每一条现存的链路定义一个称为链路冗余度LC的值，其定义如下:

式中，Wij为虚拟全连通网络下的边权值;LSI(i，j)为节点i至节点j的链路分割因子;Cij为链路容量;fij为在一定路由法则下链路上的流量;Cij－fij/Cij为相对剩余容量。删除一条链路的原则为:删除具有最大LC(i，j)值的链路。很明显:这样的删除原则必将删除那些对网络的抗毁性、承载的业务量和资源的节省等方面最没有贡献的链路。

利用上述原则，研究了一个网络设计的流程，其具体过程如下:

①输入干线节点的位置、每条干线的容量C和网络中所有节点对间的业务量;

②进行初始网络拓扑设计时，采用式(9)和最优生成树算法;

③确定所有节点对间的最短路径并在路径上加载业务，直到某条链路成为饱和链路;

④消除饱和链路，检查剩余网络的连通性。若为连通网络则以剩余容量为链路最大可用流量，剩余节点对间的业务量作为初始业务量，以剩余连通网络为初始网络，否则跳至步骤⑥;

⑤判断是否已分配完所有节点间的业务，若是则跳至步骤⑧，否则跳至步骤③;

⑥判断是否还有未分配的业务，若有则跳至步骤⑦，否则跳至步骤⑧;

⑦ 计算各节点的 NSI、Wij、AL(i，j)，寻找 AL(i，j)最大的节点对;在原拓朴上增加节点i’、j’间容量为C的链路，跳至步骤③;

⑧计算并判断NIF、LIF是否满足要求，若是则终止;否则计算现存各边的冗余度LC，从原始拓朴中去掉LC最大的链路;计算每个节点对的AL(i’，j’)，找到使 AL(i’，j’)最大的节点对 i’，j’;在原拓朴上上增加节点i’、j’间容量为C的链路。

4 结束语

上述提出了满足一定业务需求的抗毁网络设计概念，给出了抗毁网络设计、求解模型的主要流程。网络的性能并不是各设备性能的简单代数和，优化的网络设计模型可利用性能不佳的设备构建性能相对好的网络，特别是针对目前经费、技术受限情况进行网络优化设计研究其意义更加重大。通信网络设计与具体使用需求密切相关。因此文章的设计思路并不普适于所有网络，要根据具体情况加以具体分析和应用。

［1］SAKSENA V R.Topological Analysis of Packet Network［J］.IEEE Journal on Select Areas in Communications，1989，7(8):35 －38.

［2］COAN B A，LELAND W E，VECECHI M P.Using Distributed Topology Update and Preplanned Configuration to Achieve Trunk Network Survivability ［J］.IEEE Trans Relialibity，1991，40(4):404 －416.

［3］徐俊明.图论及其应用(第2版)［M］.合肥:中国科学技术大学出版社，2004:171－254.

［4］陈建国，姜 锋.通信网基于业务的抗毁性分析［J］.无线电通信技术，1998，24(3):18 －22.

［5］张中伟，陈建国.抗毁通信网络设计［J］.无线电通信技术，2000，26(2):32 －38.

［6］钟联炯，徐 锋.通信网络拓朴抗毁性算法［J］.火力与指挥控制，2003，28(6):113 －114.

［7］吕久明，张 于，杨晓静.军事通信网抗毁性能的神经网络方法研究［J］.电子对抗技术，2003，18(1):35－38.