基于改进烟花算法的以太网通信链路调度方法

基于改进烟花算法的以太网通信链路调度方法

技术领域

本发明设及一种基于改进烟花算法的以太网通信链路调度方法，属于以太网通信网络链路调度领域。

背景技术

随着列车通信网络结构体系的发展与兴起，轨道交通列车正向着高速，稳定，舒适化方向发展，对列车通信网络的实时性提出了更高的要求。工业以太网以其稳定性，可靠性，实时性成为了全球各国工业控制网络竞相研究的热点问题。但是目前的工业以太网技术采用的均是带有冲突检测的载波监听多路访问(CSMA/CD)技术，没有完备的延迟时间和通信响应，导致产生了工业以太网通信链路调度延时大和效率不高等问题，所以，如何合理的安排数据传输过程中的调度就显得尤为重要，使得实时周期消息序列能够在最短时间内完成队列调度，有效的降低网络时延，提高全局搜索效率。

发明内容

本发明所要解决的技术问题是针对现有工业以太网通信链路存在的调度时延大效率不高等问题，提供基于改进烟花算法的以太网通信链路调度方法，将改进的烟花算法用在以太网通信链路的调度上，建立以太网调度模型，设置约束条件及优化模型，与改进过选择策略及变异算子的烟花算法相结合，达到工业以太网通信链路节点间的传输时延降低，提高节点间链路数据通信的可靠性，在一定程度上保证链路通信的实时性的目的，从而解决上述问题。

基于此，有必要对现有烟花算法无法求解以太网通信链路调度问题，提出一种改进的基于烟花算法的以太网通信链路调度方法，该方法包括如下实施步骤：

步骤1：建立工业以太网通信链路调度模型，并设置约束条件及优化目标。参数设置并初始化种，采用离散机制进行实时周期数据任务的编码，令Li＝{τ1,τ2,…,τn},i∈N表示需要调度的任务数据序列，其中，发送端和接收端的任务调度序列均由泊松分布产生，i表示实时周期中的数据包的序号，τi表示任务的序列，通过烟花算法合理安排任务调度的序列，使工业以太网数据链路上的数据包达到时间达到最小值。

步骤2：设置烟花算法中的参数，包括任务数量N，带调度的任务数据Li，爆炸火花的数量Fi，爆炸幅度Ri，最大迭代次数I等。设从源主机到目的主机的通信链路中，烟花规模为20，维度为10，爆炸火花个数为40，爆炸半径为40，爆炸数目限制因子a＝0.3，b＝0.6，变异火花数为10，变量上下界为[-10,10]，最大迭代次数50次，调度任务数量10，源主机的信干噪比需求为8dB。设置iter＝1,迭代开始,其中i和N都是正整数。

步骤3：根据步骤1,2中的任务调度编码方法，初始化烟花的位置并且将烟花的位置转化成实时周期数据的调度序列。

步骤4：产生爆炸火花。并根据相关公式计算其爆炸数目，爆炸范围，公式具体介绍将如下文所示。

烟花算法的爆火花的数量和火花产生的爆炸半径如下式(1),(2)所示：

其中，Fi表示第i个烟花中产生的爆炸火花的数量，f则表示产生的所有爆炸火花的总个数，它是一个常数代表，Xmax表示最差的适应度值，f(Xi)表示第i个烟花的适应度值，ε是为了防止分母为0设置的一个常数值。Ri表示第i个烟花产生的爆炸幅度的范围，R表示最大的爆炸半径，Xmin表示最优烟花个体产生的适应度值。

为了有效的使烟花产生的每代都是高质量的火花，所以需要对爆炸产生的火花数量进行一定设置：

a和b是常数，取值范围为[0,1]，round是遵循四舍五入原理的函数。

步骤5：将超出可行域范围内的烟花粒子映射到可行域范围内。计算当前位置的烟花个体及其目标函数值，并统计当前最优位置及函数值。对于不在范围内的火花重新映射计算公式如下所示：

Xi,k＝XL-Bou,k+|Xi,k|％(XH-Bou,k-XL-Bou,k) (4)

XL-Bou,k和XH-Bou,k分别表示第k个维度中烟花的位置i矢量的可行解空间的上下界。

步骤6：计算变异维度，出变异系数最大的维度作为高斯变异维度，同时进行高斯变异，将高斯变异火花超出可行域范围内的火花映射到可行域范围，并统计爆炸火花，高斯变异火花，正常火花。

考虑到不同维度对于变异的渴望程度是不同的，本发明在此基础上提出了一种新的高斯变异算子，该方法通过引入变异系数来描述算子的变异程度，将变异系数最大的维度选取出来进行变异操作。

变异维度选取公式如下所示：

其中，i表示某一维度，n表示候选烟花的数量，VC表示变异系数，w表示烟花各个维度的标准差，α表示烟花维度上的均值。通过以上方式对将进行变异操作的维度进行选取，选择变异系数最大的烟花维度进行变异操作，变异系数越大，则表示离散程度越大。

步骤7：计算爆炸火花，高斯变异火花，正常火花的适应度值，并将三种火花作为下一代种候选个体进行筛选。将产生的火花种集合按照中位数锦标赛选择策略选择下一代烟花个体。具体过程如下所示：

(1)从总体中选择一定数量的烟花作为候选集参与下一代烟花的个体选择，候选集设置为K，个体总数为M。

(2)将每个候选集烟花个体的适应度值按照从升序的方式排列，取出适应度值的中位数Zn。

(3)将中位数对应的适应度值选出，将候选个体分为K1和K2两组。

(4)在(3)中的两组候选集中，每组随机选择M/2组候选个体，然后将每组中最优秀的个体作为下一代的爆炸中心。

步骤8：将优化完成后的烟花粒子中选择出适应度最小的N个火花作为下一代烟花个体，同时输出最优解，重复步骤3～7，直到达到最大迭代次数。

本发明较好的克服了传统烟花算法在全局搜索时间过长以及变异离散程度小等缺点，将工业以太网链路调度策略与本发明方法结合，有效的降低了节点间链路数据传输的传输时间，还加快了节点间链路数据传输的传输速率。

附图说明

图1为本发明的基于烟花算法的以太网通信链路调度方法流程图

图2为本发明的优化算法前后调度序列适应度与迭代次数关系对比图

图3为本发明的优化算法前后链路传输速率与迭代次数关系对比图

图4为本发明的优化算法前后源主机的信干燥比与迭代次数关系对比图

具体实施方案

本发明是基于改进烟花算法的以太网通信链路调度方法包括以太网链路实时周期数据通信过程模型及其调度优化算法。本发明中的系统模型是由一个源主机和三个目的主机组成的工业以太网网络，并对其进行了假设，使其能够满足本发明中的数据传输时延要求。针对源主机和目的主机之间的数据传输链路，发明中的待调度的数据类型为实时周期数据，源交换机发出的数据到达过程均遵从Poisson分布，终端交换机接受数据的过程也将服从泊松分布。在任务开始调度之前具有足够的时间对数据进行调度规划安排，缓冲区的长度足够大，能够容纳所有的传输序列流。调度顺序在实时周期数据基本周期内按照发明中优化的调度算法依次传输。而调度优化算法是根据改进后的烟花算法进行实时信息优化的，通过对约束条件及优化目标的设置，优化调度序列，对参数进行调整，同时改进选择策略和高斯变异维度使工业以太网通信链路节点间的传输时延降低，达到提高网络调度实时性的目的。

针对上述模型的分析与假设，将实时周期消息任务的调度转化为数学模型，则可表示成一个三元组来描述：

DPRT＝{D1,D2,……DN},i∈1,2,....N (6)

τi＝(Ti,Pi,deadi),i＝1,2,…N (7)

其中，DPRT表示实时周期数据任务的集合，由N个互相独立的实时周期任务组成。τi表示每一个实时周期任务，Ti表示当前任务的周期，Pi表示当前任务的最坏执行时间，deadi则是当前任务的截止期。

同时，由于待调度的数据类型为实时周期数据，源交换机发出的数据到达过程均遵从Poisson分布，且终端交换机接受数据的过程也将服从泊松分布。

数据包的发送过程满足如下：

链路传输速率取决于链路的信道状态与资源的分配策略，因此需满足如下条件：

其中，Cv(τi)表示数据链路的传输速率，θi表示保证目的主机能够实现可靠通信的信干燥比。用公式表示如下所示：

其中，sij是为了满足数据接收端主机的通信服务质量，在其能够从源主机的发送端接收到的二进制比特流中区分出数据帧的起始与终止，而对链路所设定的信道增益；δi是源主机端的发送功率。Ip是接收端引起的噪声干扰。N0是信道中的背景噪声。

本发明是针对工业以太网数据通信链路的实时周期数据进行调度，所以为了满足数据链路之间的通信服务质量，以加快传输速率，实现更可靠，更准确的信息传输为目的，设源主机的最低要求传输速率为数学表达式如下所示：

在时延方面，调度模型存在如下关系：

其中，Tp表示数据传输序列在队列中的离开时间，表示理想状态下的离开时间L(τi)为数据序列的长度。同时，在网络没有突发数据造成积压的情况下：

上式中，L(τi)max表示实时周期数据中的最大数据长度，B表示被分配的带宽。

所以，通过对实时周期数据传输的分析，本发明中基于改进烟花算法的工业以太网通信链路调度方法的适应度函数，可表示如下：

本发明的实时周期数据调度算法是将烟花算法运用到工业以太网通信链路调度优化的问题上，通过模拟自然烟花爆炸过程产生的烟花个体搜索出最优解，在烟花算法处理流程中，首先是编码设计，然后是初始体的设计。通过爆炸产生的烟花个体按照一定规则进行一代代进化，直到能满足上述的优化目标和约束条件则终止迭代，并由此得到最终解。通过改进烟花算法生成的通信链路调度序列过程流程图如图1所示，该方法包括如下实施步骤：

步骤1：建立工业以太网通信链路调度模型，并设置约束条件及优化目标。参数设置并初始化种，采用离散机制进行实时周期数据任务的编码，令Li＝{τ1,τ2,…,τn},i∈N表示需要调度的任务数据序列，其中，发送端和接收端的任务调度序列均由泊松分布产生，i表示实时周期中的数据包的序号，τi表示任务的序列，通过烟花算法合理安排任务调度的序列，使工业以太网数据链路上的数据包达到时间达到最小值。

步骤2：设置烟花算法中的参数，包括任务数量N，带调度的任务数据Li，爆炸火花的数量Fi，爆炸幅度Ri，最大迭代次数I等。设从源主机到目的主机的通信链路中，烟花规模为20，维度为10，爆炸火花个数为40，爆炸半径为40，爆炸数目限制因子a＝0.3，b＝0.6，变异火花数为10，变量上下界为[-10,10]，最大迭代次数50次，调度任务数量10，源主机的信干噪比需求为8dB。设置iter＝1,迭代开始,其中i和N都是正整数。

步骤3：根据步骤1,2中的任务调度编码方法，初始化烟花的位置并且将烟花的位置转化成实时周期数据的调度序列。

步骤4：产生爆炸火花。并根据相关公式计算其爆炸数目，爆炸范围，公式具体介绍将如下文所示。

步骤4-1：爆炸火花的数量按照公式进行计算，其中，Fi表示第i个烟花中产生的爆炸火花的数量，f则表示产生的所有爆炸火花的总个数，它是一个常数代表，Xmax表示最差的适应度值，f(Xi)表示第i个烟花的适应度值，ε是为了防止分母为0设置的一个常数值。

步骤4-2：爆炸火花的爆炸半径按照公式进行计算，Ri表示第i个烟花产生的爆炸幅度的范围，R表示最大的爆炸半径，Xmin表示最优烟花个体产生的适应度值。

步骤4-3：为了有效的使烟花产生的每代都是高质量的火花，所以需要对爆炸产生的火花数量进行一定设置：

其中，a和b是常数，取值范围为[0,1][12],round是遵循四舍五入原理的函数。

步骤5：将超出可行域范围内的烟花粒子映射到可行域范围内。计算当前位置的烟花个体及其目标函数值，并统计当前最优位置及函数值。对于那些不在范围内的火花重新映射按照公式Xi,k＝XL-Bou,k+|Xi,k|％(XH-Bou,k-XL-Bou,k)进行，其中XL-Bou,k和XH-Bou,k分别表示第k个维度中烟花的位置i矢量的可行解空间的上下界。

步骤6：计算变异维度，出变异系数最大的维度作为高斯变异维度，同时进行高斯变异，对高斯变异火花超出可行域范围内的火花映射到可行域范围，并统计爆炸火花，高斯变异火花，正常火花。

步骤6-1：考虑到不同维度对于变异的渴望程度是不同的，本发明在此基础上提出了一种新的高斯变异算子，该方法通过引入变异系数来描述算子的变异程度，将变异系数最大的维度选取出来进行变异操作。

变异维度选取按照公式进行操作，其中，i表示某一维度，n表示候选烟花的数量，VC表示变异系数，w表示烟花各个维度的标准差，α表示烟花维度上的均值。通过以上方式对将进行变异操作的维度进行选取，选择变异系数最大的烟花维度进行变异操作，变异系数越大，则表示离散程度越大。

步骤7：计算爆炸火花，高斯变异火花，正常火花的适应度值，并将三种火花作为下一代种候选个体进行筛选。将产生的火花种集合按照中位数锦标赛选择策略选择下一代烟花个体。具体过程如下所示：

步骤7-1：从总体中选择一定数量的烟花作为候选集参与下一代烟花的个体选择，候选集设置为K，个体总数为M。

步骤7-2：将每个候选集烟花个体的适应度值按照从升序的方式排列，取出适应度值的中位数Zn。

步骤7-3：将中位数对应的适应度值选出，将候选个体分为K1和K2两组。

步骤7-4：在步骤7-3：中的两组候选集中，每组随机选择M/2组候选个体，然后将每组中最优秀的个体作为下一代的爆炸中心。

步骤8：将优化完成后的烟花粒子中选择出适应度最小的N个火花作为下一代烟花个体，同时输出最优解，重复步骤3～7，直到达到最大迭代次数。

按照上述基本操作即可生成工业以太网通信链路实时周期数据调度的最优序列。

为了验证本发明基于改进烟花算法的以太网通信链路调度方法的有效性，在满足列车通信网络数据传输时延的要求下，设在一个源主机和三个目的主机组成的工业以太网网络中，烟花规模为20，维度为10，爆炸火花个数为40，爆炸半径为40，爆炸数目限制因子a＝0.3，b＝0.6，变异火花数为10，变量上下界为[-10,10]，最大迭代次数50次，调度任务数量10，源主机的信干噪比需求为8dB。设置iter＝1,迭代开始,其中i和N都是正整数。如图2所示，图中曲线分别是烟花算法(FWA)和基于锦标赛的选择策略的烟花算法(LoTFWA)以及改进后的烟花算法(CVFWA)。表示为每个算法获得的调度序列的适应度值与迭代次数的关系。可以看出，相比于烟花算法(FWA)和基于锦标赛选择策略的烟花算法(LoTFWA),本发明的改进烟花算法(CVFWA)具有更好的收敛性，有效的降低了网络中的传输时延。

图3显示了数据链路的传输速率与迭代次数之间的关系。可以看出，在保障链路数据正常通信的情况下，CVFWA算法相比于FWA算法和LoTFWA实现了更快的传输速率，有效的提高了链路数据通信的实时性能。图4显示了由各个算法获得的源主机的信干燥比与迭代次数之间的关系。可以看出，FWA算法的信干燥比不能够满足本文所设定的信干燥比值，所以源主机与目的主机之间的链路无法实现数据通信。LoTFWA虽然满足设定要求，但是效果没有CVFWA算法效果好，因此，CVFWA算法更满足本文所设定信干燥比参数的要求，实现节点之间可靠的通信。

可见本发明基于改进烟花算法的以太网通信链路调度方法的有效性，在满足列车通信网络数据传输时延的要求下，增加了对变异维度的选取，同时将选择策略改进为中位数锦标赛选择策略。在保障链路数据正常通信的情况下，本发明不仅有效的降低了节点间链路数据传输的传输时间，还加快了节点间链路数据传输的传输速率。提高了节点间链路数据通信的可靠性，在一定程度上保持了链路通信的实时性。