电磁发射系统以太网拓扑结构建模优化*

2019-07-29江汉红许轶楠

国防科技大学学报 2019年4期

路遥，张晓，江汉红，吴优，许轶楠

(海军工程大学舰船综合电力技术国防科技重点实验室，湖北武汉 430033)

因为路径问题，网络拓扑结构优化具有多约束和多目标特点，是一个典型的NP难组合优化问题，难以在多项式时间内实现求解。目前针对拓扑结构优化的研究主要集中在算法求解上。文献[1]利用插值法来对遗传算法的输入进行初始化，对特定区域进行搜索，从而更好地实现寻找拓扑最小权值的目标，该方法对于简单的网络结构优化问题效果较好，对于复杂网络的拓扑优化效果不佳；文献[2]对局域网网络拓扑结构的平均时延和网络成本提出了具有双重准则设计问题的算法，该算法搜索速度更快，但实现过程也较为复杂。

电磁发射系统是一套通过能量存储、转换、释放，为目标对象提供所需附加动力的复杂系统。电磁发射系统以太网作为顶层闭环运控分系统的二级网络子系统，主要用于提供顶层分系统控制器下达指令数据与底层分系统控制器和IP部件上传波形数据的畅通渠道，实现全系统控制器的协同管理、闭环控制、设备维护、故障诊断、数据采集汇总与备份等功能。通过工业以太网交换机将全系统的控制器互联为一个复杂的网络化控制系统，有助于提高电磁发射系统的网络可靠性和易维护性，为将来电磁发射系统网络结构和功能的可拓展性提供可能，是实现电磁发射系统网络化控制的基础。

电磁发射系统以太网的主要性能指标为：链路为1000 Mbit/s单模光纤环网，光纤波长1310 nm，最大衰减≤0.4 dB/km；节点为工业以太网交换机，一个环上允许最多160台交换机，最大恢复时间5 ms/台，丢包率为0。全系统以太网中有底层分系统控制器和IP部件共113个，通过事件数据和状态数据两种类型与顶层闭环运控分系统进行通信。不同数据对网络的性能要求不同，事件数据对网络链路有较高的实时性、可靠性要求；状态数据对实时性的要求虽然没有事件数据的高，但是数据量较大，对于系统的状态分析和事后故障诊断具有重要作用，因此需要较高的带宽保证数据的完整性。总体上，电磁发射系统的网络流量兼具平稳性、周期突发性及较弱的长相关性等特点。目前网络拓扑结构方面的研究对象以通用网络及应用网络为主，电磁发射系统由于网络流量的特殊性，以太网拓扑结构优化直接采用上述方法存在着一定的局限性；另外，前人研究工作偏重基于硬件成本的物理拓扑结构优化，很少考虑对网络的逻辑拓扑进行软件优化。因此，有必要针对电磁发射系统以太网的物理拓扑结构和流量特性，建立拓扑结构优化的数学模型，提出有效的算法改进以太网的性能，降低系统的软成本。

1 生成树协议在电磁发射系统网络拓扑中的局限分析

电磁发射系统以太网是由工业以太网交换机采用环形拓扑结构组成的，交换机作为底层控制系统与顶层维护管理系统的中间层，具有存储、转发事件数据和状态数据的功能。为了防止环形结构导致的广播风暴的产生，交换机支持生成树协议(Spanning Tree Protocol, STP),通过生成树算法(Spanning Tree Algorithm, STA)生成一个无环的树形拓扑，以保证网络的正常运行。

STP由IEEE802.1D标准定义。当一个局域网内两个网络节点之间存在一条以上的通信路径时，STA会检测到环路的存在，并根据网桥ID(Bridge ID，BID)、路径开销(Path Cost，PC)和端口ID(Port ID，PID)参数来自动选择开销值最低的那条路径作为可使用的最优路径(称为主链路或活动链路)，而阻断其他的通信路径，将它们作为备用链路。当主链路正常工作时，备用链路处于逻辑阻断状态；当交换机侦测到主链路中出现故障时，将通过STA自动启用备用链路重构网络拓扑结构以保证网络的正常运行，提高网络的可靠性。

在电磁发射系统以太网的物理拓扑结构已经完全确定的情况下，通过交换机STP得到的最小生成树(Minimum Spanning Tree, MST)是唯一的，且具有最优性。然而这种生成树的最优性是交换机基于上述BID、PC、PID等几个参数值进行优化的，并没有结合系统中各个链路的实际流量状况，因此这样得到的MST拓扑通常情况下只具有最小开销，却可能导致部分节点和链路的负载过大，一旦发生堵塞，将会影响网络中关键链路的性能，无法使全系统运行在最佳状态，有必要结合各个链路的实际流量对拓扑结构进行进一步优化[3]。

2 电磁发射系统多环拓扑的多目标优化模型

以一个电磁发射系统以太网拓扑为例，通过对该网络的交换机和实际通信链路抽象化以后得到如图1所示的拓扑结构,图中节点代表布置于各个设备内的交换机，连线代表将交换机互连的光纤链路，底层控制器和IP部件反映为链路中流量的方向和大小。

图1 电磁发射系统以太网的实际拓扑结构Fig.1 Ethernet topology of electromagnetic launch system

图1中网络拓扑结构可看作一个无向连通图G=(V,E)。V={Va,Vb,…,Vw}为交换机节点的集合(未列出与交换机相连的底层控制器节点)，并且所有交换机均支持STP；E={E1,E2,…,E26}为通信链路的集合，其中实线表示逻辑通路，虚线表示通过STP算法生成的备用链路，每条链路的权重记为wi(i=1,2,…,26)。

由于交换机环网链路均为单模1310 nm波长的1000 Mbit/s的光纤连接，链路之间性能差异很小，所以在本系统中链路的权重完全由其流量决定，并且该系统中主要数据流量的大小和流向是确定的。通过在网络多个关键节点上对数据包的流量和流向进行抓包分析，可以得出所有两个交换机之间的数据流量，如表1所示。

表1 交换机节点间数据流量统计

经测得目前网络所有链路上的广播流量均小于1 kbit/s，所以表1中忽略了网络上的广播流量。对照图1和表1，优化前的链路流量(单位：kbit/s)拓扑如图2所示。

1)使网络链路的总流量(即平均流量)最小，使整个网络系统在较低的负载下工作，使网络工作更加安全稳定；

2)使网络中流量最大的链路流量最小，因为网络冲突率和网络带宽占用率呈指数关系，降低链路的最大流量对降低网络冲突率有显著效果。

设xi(i=1,2,…,26)是0-1型决策变量，xi=1表示边Ei为逻辑通路，xi=0表示边Ei为物理断路或逻辑断路，则该规划问题的数学模型可以表示为：

(1)

(2)

xi∈{0,1},i=1,2,…,26

(3)

图2 优化前的网络拓扑结构和链路流量Fig.2 Network topology and link traffic before optimization

其中：wi为链路xi上的总流量，作为该链路在目标函数中的权重；wmax为系统中所有链路的最大流量；k为最大流量wmax在目标函数中所占的额外权重，是对网络所有链路总流量最小和冲突率最小这两个优化目标的一个主观综合考量，取值范围0.2

从形式上来看，这个组合优化问题与最小生成树问题类似，是一个NP完全问题[4-6]，然而从优化目标和约束条件来看，其又与传统的最小生成树问题有所区别：其中每条链路上的流量权重是动态变化的，不同的解所对应的拓扑结构不同。当一条链路由通路变为备用链路时，原本流经该链路的数据流会选择其他链路到达接收节点，从而影响到该链路及相关的链路流量。而按照图论中经典的Prim算法或Kruskal算法对最小生成树问题进行求解时，需要固定每条边的权重，因此本文的最小生成树问题无法使用这些方法，需要考虑其他的算法。

3 基于遗传算法的电磁发射网络拓扑结构优化

遗传算法源自对生物种群系统对自然环境适应性进化过程的观察，通过模拟生物种群中个体的适者生存、交配繁殖、进化变异等自然行为对NP难问题进行求解。作为一种具有普适性的全局寻优随机搜索算法，遗传算法可以在较大的搜索区域内有效地获得比传统方法更优的最优解或次优解[7]。遗传算法可以定义为一个8元组：GA=(C,E,P0,M,Φ,Γ,Ψ,T)，其中C为基因编码规则，E为个体适应度评价函数，P0为初始种群，M为种群规模，Φ为选择算子，Γ为交叉算子，Ψ为变异算子，T为算法终止条件。

3.1 基于基因环的编码规则和个体适应度评价

个体中的每一个元素称为一个基因。为了将每一个网络状态以基因编码形式表示，同时满足编码规则的基本条件，将网络链路状态的基因编码采用决策变量xi来表示：C(x)=(x1x2…x26)，其中xi=1表示活动链路，xi=0表示备用链路或故障链路，这样第2节的数学模型仍可用来判断个体的合法性。

图1中所对应的个体用这种编码规则表示为(11011011011011111111111111)。除了表示正常的网络状态(个体)外，这种编码规则，对个体x=(11011011011011111111111111)，则表示与交换机Vj相连的两条链路均不连通，是一种网络故障状态，故可以用于网络链路状态监测。

个体适应度评价函数用来评价一个个体对目标函数的适应度，适应度高的个体在优胜劣汰选择中容易存活并产生下一代个体，适应度低的个体则容易被从种群中淘汰[8]。遗传算法中通常根据个体的适应度值来确定其在遗传操作中的存活概率，因此适应度函数要满足单值、连续、非负、最大化等性质要求。由于本模型是多目标最小值优化问题，需要对多个目标进行加权调整转换为最大值优化问题，将目标函数进行如下改造得到个体x的适应度函数：

(4)

式中，A为f(x)的一个保守估计值。

3.2 基于基因环的初始种群和种群规模

初始种群是遗传算法搜索过程的起始点，是一个由多个个体构成的集合，不同的初始群体的收敛速度可能有着较大的差别。遗传算法通过选择算子、交叉算子和变异算子只能保证低阶、短定义矩以及平均适应度高于种群平均适应度的模式在子代中呈指数级增长，但并不能确保算法收敛到最优个体。对于本文的算法要从理论上保证能够收敛到最优解，则必须保证种群中所有个体的基因集合(即基因池)等价于整个解空间的基因集合，即遗传算法的搜索空间能够覆盖整个解空间。

常规的二进制基因编码规则通过随机方法生成初始种群，非常容易实现完备的基因池[9]。然而本文的情况较为特殊，如果产生初始种群的方法不当，可能需要较大的种群数量才能实现完备的基因池；而且遗传算法的三个算子中，选择算子和交叉算子都不会产生新的基因，而变异算子发生的概率通常比较低，如果初始种群的基因池不完备，很难通过变异使得搜索过程完全覆盖解空间的基因池。因此考虑用基因环解决电磁发射系统以太网拓扑结构优化问题。基因环是由图1中若干构成环(单环或复环)的链路所代表的基因组构成。在遗传算法中，一个基因环作为一个整体进行交叉和变异操作，以避免非法解的产生。

因此在本文算法中，基因环是遗传操作中最小的基因单位。要满足种群基因池的完备性条件，需要先产生部分初始种群以覆盖整个解空间的个体集合，再随机产生其他个体直到满足预设的种群规模，这样产生的初始种群P0才能较好地符合多样性和完备性要求。考虑本文问题中解空间的规模并不大，种群规模M设为固定值51。

3.3 基于基因环的遗传操作

遗传操作是模拟生物基因的遗传过程，对群体的个体按照其适应度值进行交叉、变异、选择等操作[10]。遗传操作对于算法的收敛性和搜索速度等有着重要影响。相比于传统搜索算法的无向搜索，遗传操作的搜索是向最优解方向的随机扰动，效率相对较高。由于本文编码规则比较严格，遗传算子设计不当很容易产生非法个体，如何设计遗传算子十分重要。

3.3.1 交叉算子

交叉算子在遗传算法中起到核心作用，是一种把两个父代个体的部分结构加以替换重组而生成新个体的操作，但该操作不会产生新的基因。常用的二进制交叉算子有单点交叉、多点交叉、均匀交叉、匹配交叉、洗牌交叉等。考虑到本文中的基因编码方式，采用以一个基因环为单位的整环交叉，这样可以确保交叉后得到的都是合法的个体，而用其他交叉方法则容易产生非法个体。基因环交叉方法如下(以图1中Va,Vb,Vc,Vd,Ve组成的环为例)：

(110110)11011011111111111111+

(011110)11011011111111111111

↓

(011110)11011011111111111111+

(110110)11011011111111111111

交叉算子是影响遗传算法收敛性的主要因素。在不变异仅交叉的情况下，遗传算法可等效为有限吸收的马尔科夫过程，在适当的选择策略下，通过交叉可实现向最优解收敛。交叉概率pc是影响遗传算法行为和性能的关键参数，pc越大，新个体产生的速度就越快，但也会导致具有高适应度的个体结构很快就会被破坏；pc过小会使搜索过程减缓，降低搜索速度。为保证遗传算法的性能，可以采用如式(5)所示自适应交叉概率：

(5)

交叉算子步骤：

步骤1：对种群Pt-1内除历代最优个体外所有个体进行两两配对。

步骤2：遍历所有配对个体，按交叉概率确定配对个体是否进行交叉操作。

步骤3：若交叉则随机选择一个基因环进行交叉操作，否则转步骤4。

步骤4：遍历未结束则转步骤2，否则结束交叉操作，生成种群Pt1。

3.3.2 变异算子

变异算子是对群体中某些个体串的基因座上的基因值作变动的操作，一般作为遗传算法的辅助算子，该操作会改变当前群体内基因环的数量。常用的二进制变异算子有基本位变异、均匀变异、自适应概率变异等。相对于具有全局搜索能力的交叉算子，变异算子本身是一种局部随机搜索，使遗传算法具备兼顾全局和局部的均衡搜索能力，有利于保持种群多样性，防止出现非成熟收敛。一个有效的遗传算法设计应考虑变异算子和交叉算子的有效配合。

开始时增加变异率，结束时减少变异率可以改善搜索速度。当变异概率pm>0.5时，遗传算法就退化为随机搜索，失去了遗传算法一些重要的数学特性和搜索能力。本文选取pm=0.02，并使用如下谨慎变异算子以确保算法的有效性：

步骤1：遍历种群Pt1内除历代最优个体外的每个个体的每个非唯一的基因环，对选定的基因环以变异率与基因环长度相乘后的数值作为概率来确定是否进行变异操作。

步骤2：若满足概率则重新随机变异生成新的合法基因环，否则转步骤3。

步骤3：遍历未结束则转步骤1，否则结束变异操作，生成种群Pt2。

3.3.3 选择算子

选择算子也称为复制算子或再生算子，是一种从群体中选择优势个体、淘汰劣势个体的操作，该操作不会产生新的个体。常用的选择算子有轮赌盘选择算子、锦标赛选择算子、随机遍历抽样选择算子、局部选择算子等。

常用的选择算子由于选择的随机性，某些适应度高的个体可能被多次复制，在群体数目小的情况下容易产生早熟和欺骗现象。本文采用跨世代选择算子，即在迭代过程中将上世代种群和通过交叉产生的种群混合起来，按照式(6)的概率选择较优的个体，并使新种群中的个体均不重复，以保持种群中基因模式的多样性，能有效地改善遗传算法的行为，但相对的计算量也较大。

(6)

式中，fi为待选择个体的适应度值。

同时，在进化的每一代种群中指定一个个体用于记录历史最优个体(有多个最优个体时保存编号最小的)，该个体不参与遗传操作，这样可防止历史最优个体在最终代被小概率漏选，这也是本文中选择种群大小为奇数的原因。由于这种选择操作需在其他遗传操作之后，所以使用这种选择算子的遗传算法的流程也有所不同，需要在进行选择操作前重新计算新个体的适应度值。

选择算子步骤：

步骤1：将种群Pt2和Pt-1进行混合，并剔除其中相同的个体，生成轮赌盘种群PR。

步骤2：设xP∈PR为PR中最优个体，新种群Pt={xP}，PR=PR-{xP}。

步骤3：按轮赌盘方式从PR中随机选择个体xi，Pt=Pt+{xi}，PR=PR-{xi}。

步骤4：若Pt未达到预设种群大小则转步骤3，否则选择操作结束，生成种群Pt。

3.3.4 算法终止条件和算法流程

遗传算法的终止条件一般设为固定的终止代数，如果优化问题较为复杂，也可将终止条件设为最优个体的适应度超过某一阈值(达到预期目标就终止搜索过程)，或连续几代平均适应度增长低于某一阈值(算法已经收敛)等。本文算法中终止代数T设为50，算法流程如图3所示。

图3 算法流程图Fig.3 Flow chart of the algorithm

4 仿真测试与实际电磁发射系统验证

按照前文中所仿真参数选取种群规模为51，遗传代数为50，用MATLAB编写该遗传算法程序，通过仿真得到最优个体的趋势如图4所示。

图4 遗传算法趋势图Fig.4 Trend graph of the genetic algorithm

图4中最优个体为(10111011011111111110111111)，该网络结构的链路平均数据流量为4539 kbit/s，最大数据流量位于链路12处的17 914 kbit/s，其拓扑结构和链路流量(单位：kbit/s)如图5所示。

优化前后数据对比如表2所示，平均流量和最大流量有明显下降。优化后，系统的平均流量下降70.0%，最大流量下降10.0%。

根据仿真结果，对相应交换机的参数进行配置，将交换机Va与交换机Vc、交换机Vd与交换机Ve、交换机Vo与交换机Vp六处交换机相应端口的PC值配置为100，大于其他端口的默认PC值(1000 Mbit/s端口默认PC值为4，100 Mbit/s端口PC值为19，10 Mbit/s端口PC值为100；全系统交换机的端口只有1000 Mbit/s和100 Mbit/s两种，交换机间互连的端口是1000 Mbit/s，交换机与底层控制器连接的端口是100 Mbit/s)，这样通过交换机的生成树算法将使得全系统以太网的拓扑结构与图5一致。修改网络拓扑结构后，经过多次实验检验，网络状态运行良好，网络负载与模型的理论值相差不大。

5 结论

将电磁发射系统以太网拓扑结构抽象成无向连通图，建立了网络拓扑结构优化的多目标规划模型，提出基于基因环操作的遗传算法对模型进行求解，并用穷举法验证了仿真的有效性。优化后，系统的平均流量下降70.0%，最大流量下降10.0%。这种优化只需要对以太网交换机进行相关配置，不需要改变以太网系统的物理链路，不会