CN116389277B 一种无等待时间敏感网络流量混合调度方法 （桂林电子科技大学）

(19)国家知识产权局(12)发明专利GO6N3/006(2023.01)(特殊普通合伙)45134一种无等待时间敏感网络流量混合调度方法息创建初始种群；S5评估所述初始种群中的个所述下一代初始种群进行遗传操作后返回步骤群21.一种无等待时间敏感网络流量混合调度方法，其特征在于，包括以下步骤：S2利用所述TSN网络拓扑信息生成网络节点邻接链表计算所述TT流集合中TT流的所有S3基于所述TT流集合生成TT流索引信息；S4基于所述可行路由集合和所述TT流索引信息创建初始种群；S5评估所述初始种群中的个体，选择下一代初始种群；S6判断评估过程是否终止，若终止，则输出门控列表，若没终止，则对所述下一代初始种群进行遗传操作后返回步骤S5;所述基于所述可行路由集合和所述TT流索引信息创建初始种群，包括：S41设定所述TT流集合的长度，得到设定长度；S42初始化长度为所述设定长度的路由数组和初始发送时间数组构成的遗传算法个S43基于所述TT流索引信息为TT流随机从所述可行路由集合中选择一条路由，得到路由索引值，将所述路由索引值保存在初始化后的遗传算法个体的所述初始发送时间数组中每条TT流对应的位置；S44对所有TT流利用广度优先搜索算法分组，每个分组中按照TT流的周期升序排序；S45将每个所述分组中第一条TT流的发送时间设为0,保存到初始化后的遗传算法个体的所述路由数组中的对应位置，为每个分组中其他TT流随机设置一个发送时间，保存到初始化后的遗传算法个体的路由数组中的对应位置，得到种群个体；S46重复步骤S42至S45,直至生成100个所述种群个体，得到初始种群。2.如权利要求1所述的无等待时间敏感网络流量混合调度方法，其特征在于，所述TSN网络拓扑信息包括网络节点和链路集合；所述网络节点包括TSN交换机节点和端系统节点；所述TSN交换机节点包括交换机处理时延和多个网口；所述端系统节点包括端系统处理时延和1个网口；所述链路集合的每条链路连接两个网口，相连的两个节点之间包含两条逻辑链路，方向相反。3.如权利要求2所述的无等待时间敏感网络流量混合调度方法，其特征在于，所述利用所述TSN网络拓扑信息生成网络节点邻接链表计算所述TT流集合中TT流的所S21记录所述TSN网络拓扑信息的相邻节点，得到网络节点邻接链表；S22使用深度优先搜索算法在所述网络节点邻接链表中从所述TT流集合的源节点开始搜索，将所有经过的节点保存到一个路径列表中；S23在深度优先搜索过程中，当遇到所述TT流集合的目地节点时，将路径列表保存下S24遍历完所述网络节点邻接链表后，所有从所述源节点到所述目的节点的路由都保存在路径列表中，至此得到TT流的所有可行路由信息，得到可行路由集合。4.如权利要求3所述的无等待时间敏感网络流量混合调度方法，其特征在于，3所述基于所述TT流集合生成TT流索引信息，包括：S31初始化索引值；S33将所述TT流标识和初始化后的索引值之间的映射关系记录在位置索引中；S34将初始化后的索引值加1后与下一所述TT流标识之间的映射关系记录在位置索引S35重复步骤S34,直至完成所有所述TT流标识与对应的索引值之间的映射关系的记5.如权利要求4所述的无等待时间敏感网络流量混合调度方法，其特征在于，所述评估所述初始种群中的个体，选择下一代初始种群，包括：S51计算链路集合中每条链路的基础周期，将所述基础周期定义为通过当前链路的所有实时同步流周期的最小公倍数，如果当前链路只有循环流通过，则链路基础周期为通过当前链路的循环流中周期最小的循环流的周期；S52根据所述初始种群中的个体的路由方案选择以及初始发送时间数组，计算实时同步流的传输时隙，并将所述传输时隙保存在链路和时隙对应关系中；S53判断所述实时同步流到达目的节点的时间是否满足截止时间要求；S54判断调度所述链路和时隙对应关系中的所述传输时隙是否存在冲突；S55利用时隙映射和复用策略尝试调度循环流，在调度过程中判断是否破坏已有调度，S56迭代步骤S51至S55,从接受的个体中选取部分个体作为下一代初始种群。6.如权利要求5所述的无等待时间敏感网络流量混合调度方法，其特征在于，所述判断评估过程是否终止，若终止，则输出门控列表，若没终止，则对所述下一代初始种群进行遗传操作后返回步骤S5,包括：判断迭代的次数是否达到设定次数，若达到所述设定次数，则根据所述链路和时隙对应关系中的信息推导出所有链路的门控列表，若没有达到所述设定次数，则对所述下一代初始种群进行遗传操作后返回步骤S5。4技术领域[0001]本发明涉及网络通信技术领域，尤其涉及一种无等待时间敏感网络流量混合调度方法。背景技术[0002]当前社会信息化高速发展，工业互联网实现了人、机、物全要素的互联互通。已有的实时通信协议彼此兼容性差且需要专用的设备，成本高；传统以太网技术扩展性强，价格适度，但缺乏有效的实时控制。时间敏感网络(Time-SensitiveNetwork,TSN)基于IEEE802.1Q的一系列扩展协议为以太网增加了传输的实时性和确定性，但是需要用户自行规划时间敏感(Time-Triggered,TT)流的传输。工业互联网中流量按照优先级可以划分为8类，优先级从0到7依次递增。其中实时同步流(优先级为6)和循环流(优先级为5)一般将时间感知整形器(Time-AwareShaper,TAS)作为传输选择算法，利用TT流的特征生成门控列表(GateControlList,GCL),然后利用GCL控制网口(NetworkInterfaceCard,NIC)传输队列的传输行为。工业互联网中TT流调度的关键在于如何生成合理的GCL,GCL长度和数据帧的缓存时间都应该尽可能短。[0003]现有TSN调度算法没有很好的考虑流量类型以及TT流周期和长度取值范围，TT流周期在100微秒到20毫秒范围内，长度一般不超过以太网最大传输单元(MaxmiumTransmitUnit,MTU),传统方案假设长度超过MTU,需要复杂的约束规格，而实时流和循环流的数据帧通常很短小，不需要考虑数据帧分片传输。同时，这些调度规划算法适用的业务场景也各有确定性差，传输实时性和确定性高的方案GCL又过长，降低了TT流的传输效果。发明内容[0004]本发明的目的在于提供一种无等待时间敏感网络流量混合调度方法，旨在解决现有的调度算法降低了TT流的传输效果的问题。[0005]为实现上述目的，本发明提供了一种无等待时间敏感网络流量混合调度方法，包括以下步骤：[0007]S2利用所述TSN网络拓扑信息生成网络节点邻接链表计算所述TT流集合中TT流的所有可行路由，得到可行路由集合；[0008]S3基于所述TT流集合生成TT流索引信息；[0009]S4基于所述可行路由集合和所述TT流索引信息创建初始种群；[0010]S5评估所述初始种群中的个体，选择下一代初始种群；[0011]S6判断评估过程是否终止，若终止，则输出门初始种群进行遗传操作后返回步骤S5。[0012]其中，所述TSN网络拓扑信息包括网络节点和链路集合；5[0013]所述网络节点包括TSN交换机节点和端系统节点；[0014]所述TSN交换机节点包括交换机处理时延和多个NIC;[0015]所述端系统节点包括端系统处理时延和1个NIC;[0016]所述链路集合的每条链路连接两个NIC,相连的两个节点之间包含两条逻辑链路，方向相反。[0017]其中，所述利用所述TSN网络拓扑信息生成网络节点邻接链表计算所述TT流集合[0018]S21记录所述TSN网络拓扑信息的相邻节点，得到网络节点邻接链表；[0019]S22使用深度优先搜索算法在所网络节点述邻接链表中从所述TT流集合的源节点开始搜索，将所有经过的节点保存到一个路径列表中；[0020]S23在深度优先搜索过程中，当遇到所述TT流集合的目地节点时，将路径列表保存[0021]S24遍历完所述网络节点邻接链表后，所有从所述源节点到所述目的节点的路由都保存在路径列表中，至此得到TT流的所有可行路由信息，得到可行路由集合。[0025]S33将所述TT流标识和初始化后的索引值之间的映射关系记录在位置索引中；[0026]S34将初始化后的索引值加1后与下一所述TT流标识之间的映射关系记录在位置索引中；[0027]S35重复步骤S34,直至完成所有所述TT流标识与对应的索引值之间的映射关系的[0028]其中，所述基于所述可行路由集合和所述TT流索[0030]S42初始化长度为所述设定长度的路由数组和初始发送时间数组构成的遗传算法[0031]S43基于所述TT流索引信息为TT流随机从所述可行路由集合中选择一条路由，得到路由索引值，将所述路由索引值保存在初始化后的遗传算法个体的所述初始发送时间数组中每条TT流对应的位置；[0032]S44对所有TT流利用广度优先搜索算法分组，每个分组中按照TT流的周期升序排[0033]S45将每个所述分组中第一条TT流的发送时间设为0,保存到初始化后的遗传算法个体的所述路由数组中的对应位置，为每个分组中其他TT流随机设置一个发送时间，保存到初始化后的遗传算法个体的路由数组中的对应位置，得到种群个体；[0034]S46重复步骤S42至S45,直至生成100个所述种群个体，得到初始种群。[0036]S51计算所述链路集合中每条链路的基础周期(BasePeriod,BP),将所述基础周期定义为通过当前链路的所有实时同步流周期的最小公倍数，如果当前链路只有循环流通过，则链路周期为通过当前链路的循环流中周期最小的循环流的周期；6[0037]S52根据所述初始种群中的个体的路由方案选择以及初始发送时间数组，计算实时同步流的传输时隙，并将所述传输时隙保存在链路和时隙对应关系中；[0038]S53判断所述实时同步流到达目的节点的时间是否满足截止时间要求；[0039]S54判断调度所述链路和时隙对应关系中的所述传输时隙是否存在冲突；[0040]S55利用时隙映射和复用策略尝试调度循环流，在调度过程中判断是否破坏已有[0041]S56迭代步骤S51至S55,从接受的个体中选取部分个体作为下一代初始种群。下一代初始种群进行遗传操作后返回步骤S5,包括：[0043]判断迭代的次数是否达到设定次数，若达到所述设定次数，则根据所述链路和时隙对应关系中的信息推导出所有链路的门控列表，若没有达到所述设定次数，则对所述下一代初始种群进行遗传操作后返回步骤S5。[0044]本发明的一种无等待时间敏感网络流量混合调度方法，通过S1输入TSN网络拓扑信息和TT流集合；S2利用所述TSN网络拓扑信息生成网络节点邻接链表计算所述TT流集合于所述可行路由集合和所述TT流索引信息创建初始种群；S5评估所述初始种群中的个体，所述下一代初始种群进行遗传操作后返回步骤S5,本发明能够在缩短GCL的同时保证解的质量，确保TT流传输的实时性和确定性。解决了现有的调度算法降低了TT流的传输效果的附图说明[0045]为了更清楚地说明本发明实施例或现有技术中的技术方案，下面将对实施例或现有技术描述中所需要使用的附图作简单地介绍，显而易见地，下面描述中的附图仅仅是本发明的一些实施例，对于本领域普通技术人员来讲，在不付出创造性劳动的前提下，还可以根据这些附图获得其他的附图。[0046]图1是本发明提供的一种无等待时间敏感网络流量混合调度方法的步骤图。[0049]图4是门控列表及发送信息存储结构示意图。[0050]图5是本发明提供的一种无等待时间敏感网络流量混合调度方法的流程图。具体实施方式[0051]下面详细描述本发明的实施例，所述实施例的示例在附图中示出，其中自始至终相同或类似的标号表示相同或类似的元件或具有相同或类似功能的元件。下面通过参考附图描述的实施例是示例性的，旨在用于解释本发明，而不能理解为对本发明的限制。[0052]请参阅图1至图5,本发明提供一种无等待时间敏感网络流量混合调度方法，包括以下步骤：7[0054]具体的，所述TSN网络拓扑信息包括网络节点和链路集合；所述网络节点包括TSN交换机节点和端系统节点；所述TSN交换机节点包括处理时延和多个NIC;所述端系统节点包括处理时延和1个NIC;所述链路集合的每条链路连接两个NIC,相连的两个节点之间包含两条逻辑链路，方向相反。[0055]S2利用所述TSN网络拓扑信息生成网络节点邻接链表计算所述TT流集合中TT流的所有可行路由，得到可行路由集合；[0056]具体方式为：[0057]S21记录所述TSN网络拓扑信息的相邻节点，得到网络节点邻接链表；[0058]S22使用深度优先搜索算法在所述网络节点邻接链表中从每条所述TT流的源节点开始搜索，将所有经过的节点保存到一个路径列表中；[0059]S23在深度优先搜索过程中，当遇到所述TT流的目地节点时，将路径列表保存下来，并回溯到前一个节点；[0060]S24遍历完所述网络节点邻接链表后，所有从所述源节点到所述目的节点的路由都保存在路径列表中，至此得到TT流的所有可行路由信息，得到可行路由集合。[0061]S3基于所述TT流集合生成TT流索引信息；[0062]具体方式为：[0063]S31初始化索引值；[0064]具体的，初始化索引值pos为0。[0065]S32遍历所述TT流集合中的每条TT流，得到多个TT流标识；[0066]S33将所述TT流标识和初始化后的索引值之间的映射关系记录在SP中；[0067]具体的，将TT流标识id和索引值pos之间的映射关系记录在SP中。[0068]S34将初始化后的索引值加1后与下一所述TT流标识之间的映射关系记录在SP中；[0069]S35重复步骤S34,直至完成所有所述TT流标识与对应的索引值之间的映射关系的记录，得到TT流索引信息。[0070]S4基于所述可行路由集合和所述TT流索引信息创建初始种群；[0071]具体方式为：[0072]S41设定所述TT流集合的长度，得到设定长度；[0073]具体的，设TT流集合S长度为S.len。[0074]S42初始化长度为所述设定长度的路由数组和初始发送时间数组构成的遗传算法个体；[0075]具体的，初始化两个长度为S.len的数组Φ和9构成遗传算法的个体，两个数组中所有元素初始值均设为0。[0076]S43基于所述TT流索引信息为TT流随机从所述可行路由集合中选择一条路由，得到路由索引值，将所述路由索引值保存在初始化后的遗传算法个体的所述初始发送时间数组中每条TT流对应的位置；[0077]具体的，为9中的元素赋值，利用SP中的映射关系为每个id对应的TT流随机从其可行路由集合R,中选择一条路由，将路由索引值保存在9中每条TT流对应的位置。[0078]S44对所有TT流利用广度优先搜索算法分组，每个分组中按照TT流的周期升序排8[0079]S45将每个所述分组中第一条TT流的发送时间设为0,保存到初始化后的遗传算法个体的所述路由数组中的对应位置，为每个分组中其他TT流随机设置一个发送时间，保存到初始化后的遗传算法个体的路由数组中的对应位置，得到种群个体；[0080]S46重复步骤S42至S45,直至生成100个所述种群个体，得到初始种群。[0081]S5评估所述初始种群中的个体，选择下一代初始种群；[0083]S51计算所述链路集合中每条链路的BP,将所述BP定义为通过当前链路的所有实时同步流周期的最小公倍数，如果当前链路只有循环流通过，则链路周期为通过当前链路的循环流中周期最小的循环流的周期；[0084]S52根据所述初始种群中的个体的路由方案选择以及初始发送时间数组，计算实时同步流的传输时隙，并将所述传输时隙保存在链路和时隙对应关系中；[0085]具体的，根据路由方案选择数组和初始发送时间数组，计算实时同步流的传输时隙，实时同步流在每条路由链路上发送/转发次数等于链路基础周期与实时同步流周期的商，在源节点时，每次的发送时间等于发送时间、源节点处理时延以及相应倍数的周期的和，在其他路由节点上第一次转发时间等于上一跳的发送时间、发送时延、传播时延、当前节点的处理时延之和，其他次数的转发时间等于第一次转发时间与相应倍数的周期的和；计算过程中将所述传输时隙和TT流发送/转发信息保存在链路和时隙对应关系中，所述传输时隙包括时隙开始时间点，时隙结束时间点，时隙门控值，所述门控值用8个表示开/关状态的标识符组成，所述TT流发送/转发信息包括发送/转发开始时间点，发送/转发结束时间[0086]S53判断所述实时同步流到达目的节点的时间是否满足截止时间要求；[0087]S54判断调度所述LTS中的所述传输时隙是否存在冲突；[0088]S55利用时隙映射和复用策略尝试调度循环流，在调度过程中判断是否破坏已有[0089]具体的，利用时隙映射和复用策略尝试调度循环流，所述时隙映射和复用策略，循环流在其所有路由节点上发送/转发的次数等于组周期与循环流周期的商，所述组周期的值等于分组内所有TT流周期的最小公倍数，计算每次发送/转发时间都要判断是否破坏已有调度，如果破坏已有调度，则拒绝当前个体，没有破坏已有调度的前提下将发送/转发时间与链路基础周期做模运算来完成映射，结果作为时隙开始时间，时隙结束时间等于开始时间与TT流发送时延之和，将时隙和已保存的时隙做比较，得出排队时延，排队时延不为0时更新时隙开始和结束时间并保存，如果前一时隙的结束时间和后一时隙的开始时间之差等于以太网帧间距，则合并两个时隙，如果通过模运算映射后得到的时隙信息已经存在，则表明可以进行复用，将TT流发送/转发信息添加到时隙信息中。[0090]S56迭代步骤S51至S55,从接受的个体中选取部分个体作为下一代初始种群。[0091]S6判断评估过程是否终止，若终止，则输出门控列表，若没终止，则对所述下一代初始种群进行遗传操作后返回步骤S5。[0092]具体的，判断迭代的次数是否达到设定次数，若达到所述设定次数，则根据所述LTS中的信息推导出所有链路的门控列表，若没有达到所述设定次数，则对所述下一代初始种群进行遗传操作后返回步骤S5。9[0093]对所述下一代初始种群进行遗传操作的实现方法步骤如下：[0094]变异操作：对于一个选中的变异个体，首先为该个体的路由选择方案数组9R进行变异操作，为9中每个元素增加一个随机数，形成新的路由选择方案，其次将TT流重新分组，最后将每个分组内周期最小的TT流发送时间设置为0,其余TT流的发送时间累加一个随机数作为新的发送时间。[0095]交叉操作：对于选定的两个亲本个体P₁和P₂,以及后代个体offspring,首先生成两个随机的介于0到1之间的系数λ和δ,其次生成offspring的路由选择数组9R,P₁和P₂的路由选择数组相同位置的元素分别乘以交叉系数λ和(1-λ)并将结果累加作为offspring的路由选择数组9对应位置的元素，然后对offspring的TT流重新分组，最后将每个分组内周期最小的TT流发送时间设置为0,P₁和P₂的发送时间数组①相同位置的元素分别乘以交叉系数δ和(1-δ)并累加，结果作为offspring的发送时间数组①对应位置的元素。[0097]本发明提供了一种基于基础周期的时隙映射与复用机制和无等待调度的时间敏符号说明链路，三个元素分别表示链路源节点处理时延，链路传播时延，链路速链路[pa,P₆]的源节点的排队时延TT流属性集，依次表示流标识，发送时间，周期，长度，优先级，源节点，目的节点M流s,的第j个属性，S;到S;₆依次表示流s,的标识，第一帧发送时间，周期，帧长，优先级，源节点，目的节点RR流s的第m条路由链路BP,对于[Pa,P₆]=R;”,有Tl2ID等价于T,”S流s的第a个数据帧在链路[Pa,P₆]的源节点相对于TIP,AJ的发送时间流在S内的位置索引①DG链路和TT流的映射关系链路和时隙对应关系全局变量：S,SP,R,全局变量在整个计算中一旦赋值后就不再改变，用于快速索引一些信息；中间结果：D,G,LS,LTS,中间变量和个体是一一对应的，每个个体都有其特有的中间变量，中间结果随着个体的创建而创建，随着个体的消亡而消亡。状态数组v,空路由r,空的路由集合R,跳数记录h,计算完所有的TT流的路由后第7行返回6get_routes(src,dest,v,r,R,h)4ifsrc=dest7fori←0to(adj[src].len-1)8ifvaj[seu=false9get_routes(adj[src][i],dest,v,r,R,h)11合S中的位置是一一对应的，如图2中索引部分所示，索引中每个元素记录流s;在S中的位置。R和初始发送时间。首先为每条流s随机选择一个路由索引，索引值不应该大于其可行路~4行遍历SP,然后遍历每条TT流的路由，将用到了相同链路的流存储在LS中，LS是一个状态的变量v;为false;算法第7行初始化分组标识gid为0,第8到第22行开始利用广度优先应位置的值设置为0,规定每个分组中周期最小的流在组周期的0时刻发送。为其他TT流设208.push(s.)21Q.enque(s.)的最小公倍数作为链路的BP,如果链路只有循环流通过，则BP就是周期最小的循环流的周[0109](2)根据初始发送时间和路由选择方案利用公式(1)计算实时同步流在每一跳的[0113]时隙的开始和结束时间分别是s,P„PJφmodT,和(sPP.φ+S×Pat)modT,'m,门控状态流在组周期内发送G/Si,2次，根据公式(2)获取到当前网口的发送时间8Pφ,第5至9行为行检查时隙的开始和结束时间，因为每个分组内周期最小的流在BP内第一帧发送时间为0,所以不允许任意一个时隙的开始时间和结束始遍历链路对应的时隙集合I,第14行获取一个元素s;_time_slot,第15行计算d和d’,d是s;_transmit_interval和s;_tim两个时隙开始时间较小的值，s;_time_slot的时隙结束时间更新为两个时隙结束时间较大transmit_interval对应的开始结束时间。最后第30至32行，将s;_time_slot和s;_transmit_interval添加到LTS中，将输入：分组D中循环流构成的数组S',分组D的组周期G,LTS;输出：true或false,分别表示可调度与不可调度，在可调度的情况下调度方案将会保存在LTS中。2)forj←0ton4)fork←0to(G₆/S;₂-1)5)t.←s6)t.←sP7)t.←(sP.PJφ+S₃8)s;_time_slot←(t,t,"00100000">11)returnfalse13)for1←0toI.len-115)getdandd'ofs,_time_slotands,_time_slot17)s;_time_slot←[++/],update18)ifd'≤d20)fors;_transmit_interval∈LTS[R,m]Is,_tine_slot]21)ifs,breaksupscheduledstreams22)returnfalse23)ifS;4=627)compares,_transmit_intervalwitht.28)gotbackwardoffsetofs,withδafiercomparison29)updatet,,to,te,s;_time_31)LTS[R;,I[s,_time_slot].push(LTS[R,mIIs,_time_slo32)LTS[R;].erase(s,_time_slo34)LTS[R;I[s,_time_slot].push(s_transmit_interval)判断终止条件：(1)判断种群迭代次数，迭代次数默认为50,如果达到设定次数，根据LTS中的时隙信息推导出每条链路的GCL,两个时隙之间间隔的GCL表项用的门控状态设体重新进