本发明公开了一种针对周期性数据流的规划调度方法、系统、设备和介质，方法包括：划分获取的周期性数据流集合中的数据流得到调度子集；判断所有调度子集是否可调度：若存在不可调度，重新划分数据流或者剔除不可调度的调度子集中的数据流；若均可调度，将每个数据流切分成若干子流，则每个调度子集中所有数据流的子流构成一个调度规划集合，再对每个调度规划集合进行约束建模和求解，根据求解结果求出时间规划调度参数，对数据流进行调度。本发明适配流量特征，解决周期性大流量和小流量通过网络时无法保证确定性传输的问题；最大化端口带宽利用率，同时适应更多流量数目和更大规模节点的网络，为其确定性传输规划提供保障。
1.一种针对周期性数据流的规划调度方法，其特征在于，包括如下步骤：S1：获取周期性数据流集合，对其中的数据流进行划分得到若干调度子集；
S2：依据可调度性的判定指标判断所有调度子集是否可调度，若是，执行步骤S3；否则，重新对数据流集合中的数据流进行划分或者剔除不可调度的调度子集中的数据流，并重新执行步骤S2；
S3：根据调度子集中的每个数据流的周期以及周期内的可分配时隙数将其切分成若干个子流，则每个调度子集中所有数据流的子流构成一个调度规划集合；
S4：对步骤S3中的每个调度规划集合进行约束建模和约束求解，求解得到每个子流在周期内的起始时间偏置，对数据流进行调度；
其中，对每个调度规划集合进行约束建模，模型如下：约束变量为：在数据流对应路径的每条链路上，数据流的每条子流在每个循环周期内的起始时间偏置；
边界约束：针对每条子流，其在每个循环周期内的起始时间偏置大于或等于该循环周期的起始值，其在每个循环周期内的结束时间小于或等于该循环周期的最晚截止时间，且同一循环周期内，每条子流的结束时间小于或等于下一条子流的起始时间偏置，子流在每个循环周期内的结束时间为在该循环周期内的起始时间偏置加上子流长度；
弥散度约束：针对每个循环周期，其中数据流的最后一条子流与第一条子流的起始时间偏置跨度小于或等于预设跨度值；
本地抖动延迟约束：针对每条子流，其在不同循环周期的起始时间偏置之间的时间差小于或等于预设的偏差抖动要求；
节点间时延和抖动约束：针对同一循环周期内的每条子流，其在相邻链路上的起始时间偏置之间的时间差大于或等于预设的时延和抖动要求；
端到端时延和抖动约束：针对每个循环周期，路径的接收节点接收数据流的最后一条子流的结束时间与发送节点发送数据流的第一条子流的起始时间偏置之间的差值小于或等于预设的系统业务实际需求的时延要求，所有循环周期中所述差值的最大值与所述差值的最小值之间的差小于或等于预设的系统业务实际需求的抖动要求；
冲突避免约束：针对每条链路，不同数据流的子流在同一时间段内不重叠；
端口带宽约束：所有数据流占用的带宽小于或等于端口带宽。
2.根据权利要求1所述的一种针对周期性数据流的规划调度方法，其特征在于，步骤S1中对周期性数据流集合中的数据流进行划分得到若干调度子集，包括如下步骤：S11：将源地址、目的地址以及路径相同的数据流归为初始类；
S12：如果初始类之间存在路径重叠，将存在路径重叠的初始类合并成一个调度子集，其他的不存在路径重叠的初始类各自作为一个调度子集；
S13：如果存在调度子集 、 和 ，其中 ， ，而，则将集合 和集合 从原调度子集中分离出来作为新的调度子集，其中， 表示空集。
3.根据权利要求1所述的一种针对周期性数据流的规划调度方法，其特征在于，步骤S2中，判定调度子集可调度的依据如下：其中， 为调度子集 的序号； 为调度子集 的可调度性判定指标； 和 分别表示调度子集 中的数据流 的周期内数据持续时间和周期， 表示数据流 的占用比；
若 ，则该调度子集 为可调度；否则该调度子集 为不可调度。
4.根据权利要求1所述的一种针对周期性数据流的规划调度方法，其特征在于，步骤S2中剔除不可调度的调度子集中的数据流时，若数据流存在优先级，则根据数据流的优先级进行剔除，即优先级低的数据流优先剔除；若所有数据流的优先级相同，或者根据优先级剔除数据流后的调度子集仍然不可调度，则根据用户自定义规则再进行剔除。
5.根据权利要求4所述的一种针对周期性数据流的规划调度方法，其特征在于，用户自定义规则为：根据调度子集中数据流的占用比进行剔除，即占用比大的数据流优先剔除。
6.根据权利要求1所述的一种针对周期性数据流的规划调度方法，其特征在于，步骤S3中将调度子集中的每个数据流切分成若干个子流，包括如下步骤：S31：对调度子集中的数据流按照周期进行升序列排列；
S32：计算超周期，即该调度子集中所有数据流的周期的最小公倍数；
S33：针对每条数据流构建从0到超周期之间的等差数列，等差数列的公差为对应数据流的周期；
按照升序合并所有等差数列，并去掉重复值，记录每个数据流的周期在合并后的等差数列中出现的位置编号；
S34：从小到大依次计算每条数据流在周期内的可分配时隙数；
S35：每条数据流的可分配时隙数除以位置编号得到该数据流周期内需要分割的平均可用时隙长度 ，则子流数量 ， 表示向上取整，其中 表示该数据流的周期内数据持续时间；
S36：根据子流数量 对每条数据流进行分割：如果 ，表示该数据流的子流就是自身，如果 ，则该数据流的前 个子流的长度相等，表示为 ，最后一个子流的长度为 ，为用户自定义或根据算法进行计算。
7.根据权利要求6所述的一种针对周期性数据流的规划调度方法，其特征在于，步骤S36中， ， 表示向下取整。
8.根据权利要求1所述的一种针对周期性数据流的规划调度方法，其特征在于，步骤S4中对每个调度规划集合进行约束建模，模型如下：约束变量：
其中， 表示在链路 上，数据流 的第j个子流 在第 个循环周期内的起始时间偏置；链路 属于数据流 的路径， 和 为链路 两端的节点；数据流 的循环周期数 ， 表示超周期， 表示数据流 的周期， ； ， 为调度子集 中数据流的数量；
其中， 表示数据流 的最晚截止时间； 表示子流 的长度；
其中， 是可调参数； 是数据流 的周期内数据持续时间；
其中， 包含单个节点对于子流的交换时间； 表示时钟同步精度；链路 和链路 为数据流 的路径中的相邻链路；
其中， 和 分别表示系统业务实际需求的时延和抖动要求； 表示路径中的最后一条链路； 表示路径中的第一条链路；
示链路 上的数据流集合，满足：其中， 为所有数据流的路经集合，数据流由发送节点 通过路径 到达接收节点 。
9.一种针对周期性数据流的规划调度系统，其特征在于，包括调度子集生成模块、可调度性判断模块、剔除模块、调度规划集合生成模块和约束求解模块，其中：调度子集生成模块：对获取的周期性数据流集合中的数据流进行划分得到若干调度子集；
可调度性判断模块：依据可调度性的判定指标判断调度子集是否可调度；
调度规划集合生成模块：将调度子集中的每个数据流切分成若干个子流，每个调度子集中所有的数据流的子流构成一个调度规划集合；
约束求解模块：对每个调度规划集合进行约束建模和约束求解，求解时间规划调度参数，对数据流进行调度；
其中，对每个调度规划集合进行约束建模，模型如下：约束变量为：在数据流对应路径的每条链路上，数据流的每条子流在每个循环周期内的起始时间偏置；
边界约束：针对每条子流，其在每个循环周期内的起始时间偏置大于或等于该循环周期的起始值，其在每个循环周期内的结束时间小于或等于该循环周期的最晚截止时间，且同一循环周期内，每条子流的结束时间小于或等于下一条子流的起始时间偏置，子流在每个循环周期内的结束时间为在该循环周期内的起始时间偏置加上子流长度；
弥散度约束：针对每个循环周期，其中数据流的最后一条子流与第一条子流的起始时间偏置跨度小于或等于预设跨度值；
本地抖动延迟约束：针对每条子流，其在不同循环周期的起始时间偏置之间的时间差小于或等于预设的偏差抖动要求；
节点间时延和抖动约束：针对同一循环周期内的每条子流，其在相邻链路上的起始时间偏置之间的时间差大于或等于预设的时延和抖动要求；
端到端时延和抖动约束：针对每个循环周期，路径的接收节点接收数据流的最后一条子流的结束时间与发送节点发送数据流的第一条子流的起始时间偏置之间的差值小于或等于预设的系统业务实际需求的时延要求，所有循环周期中所述差值的最大值与所述差值的最小值之间的差小于或等于预设的系统业务实际需求的抖动要求；
冲突避免约束：针对每条链路，不同数据流的子流在同一时间段内不重叠；
端口带宽约束：所有数据流占用的带宽小于或等于端口带宽。
10.根据权利要求9所述的一种针对周期性数据流的规划调度系统，其特征在于，调度规划集合生成模块包括排序模块、超周期计算模块、等差数列生成模块、位置编号计算模块、时隙计算模块、子流数量计算模块和分割模块，其中：排序模块：对调度子集中的数据流按照周期进行升序列排列；
超周期计算模块：计算超周期，即该调度子集中所有数据流的周期的最小公倍数；
等差数列生成模块：针对每条数据流构建从0到超周期之间的等差数列，等差数列的公差为对应数据流的周期；
位置编号计算模块：按照升序合并所有等差数列，并去掉重复值，记录每个数据流的周期在合并后的等差数列中出现的位置编号；
时隙计算模块：从小到大依次计算每条数据流在周期内的可分配时隙数；
子流数量计算模块：每条数据流的可分配时隙数除以位置编号得到该数据流周期内需要分割的平均可用时隙长度，该数据流的周期内数据持续时间除以平均可用时隙长度并向上取整得到子流数量；
11.一种针对周期性数据流的规划调度设备，包括处理器、存储器及存储在存储器上并可在处理器上运行的计算机程序，其特征在于，所述处理器执行所述程序时实现权利要求1～8中任意一项所述针对周期性数据流的规划调度方法。
12.一种计算机可读存储介质，其上存储有计算机程序，其特征在于，该程序被处理器执行时实现权利要求1～8中任意一项所述针对周期性数据流的规划调度方法。
针对周期性数据流的规划调度方法、系统、设备和介质
技术领域
[0001] 本发明属于实时调度网络技术领域，具体涉及一种针对周期性数据流的规划调度方法、系统、设备和介质。
背景技术
[0002] 一般按照业务性质，将通信数据流分为周期性（Periodic）数据流和非周期性（Aperiodic）数据流，其中非周期性数据流又分为有截止时间（deadline）的数据流，简称DA
流，和尽力而为（Best effort，BE）的数据流，简称BE流。周期性数据流是指传感器周期性的
产生数据，并通过由交换机互联的网络进行传输至数据处理端的数据流；或者指在网络中
存在对等节点，二者间进行通信的周期性数据流。使用四元组 表示周期性
数据流的参数，其中： 表示周期内数据流起始位置偏置，C表示周期内数据流持续时间，D
表示周期内数据流的最晚截止时间，T表示周期。DA流也可以用四元组表示，其中周期T可以
设定为无穷大。一般系统优先满足周期性数据流和DA流，剩余带宽分配给BE流，并且如果产
生碰撞或缓存不足，会优先考虑丢弃BE流数据。
[0003] 在工业网络中，数据实时传输是保证工业网络正常运转的基础保障之一。传统的工业网络由于发送的数据量很小，数据包大约500字节左右，并且所有数据包完整语义，通
过如Modbus、Profinet、EtherCAT、FlexRay、Can等工业总线协议进行数据传输，这些传输协
议涉及的场景带宽需求都较低。而随着AI和大数据的发展，工业网络逐渐朝着高带宽大流
量的方向发展，如来自高清摄像头的视频流，雷达探测的流量。因此如何保障在大流量冲击
的情况下，维持工业网络的实时性和确定性是个难题。最原始的方式主要是采用物理隔离、
独立组网的方式接入大流量业务，但是这种方式融合困难、成本高昂。随着工业网络的以太
化，网络带宽大大提升，因此寻求传统工业网络数据通信和高带宽数据流融合是一种重要
的趋势。
发明内容
[0004] 发明目的：针对现有技术中存在的问题，本发明公开了一种针对周期性数据流的规划调度方法、系统、设备和介质，考虑在以太网基础上基于规划方法保持实时性和确定
性，通过合理的规划，适配流量特征，解决周期性大流量和小流量通过网络时如何保证确定
性传输的问题。
[0005] 技术方案：本发明采用如下技术方案：一种针对周期性数据流的规划调度方法，其特征在于，包括如下步骤：
[0006] S1：获取周期性数据流集合，对其中的数据流进行划分得到若干调度子集；
[0007] S2：判断所有调度子集是否可调度，若是，执行步骤S3；否则，重新对数据流集合中的数据流进行划分或者剔除不可调度的调度子集中的数据流，并重新执行步骤S2；
[0008] S3：根据调度子集中的每个数据流的周期以及周期内的可分配时隙数将其切分成若干个子流，则每个调度子集中所有数据流的子流构成一个调度规划集合；
[0009] S4：对步骤S3中的每个调度规划集合进行约束建模和约束求解，求解得到每个子流在周期内的起始时间偏置，对数据流进行调度。
[0010] 优选地，步骤S1中对周期性数据流集合中的数据流进行划分得到若干调度子集，包括如下步骤：
[0011] S11：将源地址、目的地址以及路径相同的数据流归为初始类；
[0012] S12：如果初始类之间存在路径重叠，将存在路径重叠的初始类合并成一个调度子集，其他的不存在路径重叠的初始类各自作为一个调度子集；
[0013] S13：如果存在调度子集 、 和 ，其中 ， ，而 ，则将集合 和集合 从原调度子集中分离出来作为
新的调度子集，其中， 表示空集。
[0014] 优选地，步骤S2中，判定调度子集可调度的依据如下：
[0015]
[0016] 其中， 为调度子集 的序号； 为调度子集 的可调度性判定指标； 和分别表示调度子集 中的数据流 的周期内数据持续时间和周期， 表示数据流
的占用比；
[0017] 若 ，则该调度子集 为可调度；否则该调度子集 为不可调度。
[0018] 优选地，步骤S2中剔除不可调度的调度子集中的数据流时，若数据流存在优先级，则根据数据流的优先级进行剔除，即优先级低的数据流优先剔除；若所有数据流的优先级
相同，或者根据优先级剔除数据流后的调度子集仍然不可调度，则根据用户自定义规则再
进行剔除。
[0019] 优选地，用户自定义规则为：根据调度子集中数据流的占用比进行剔除，即占用比大的数据流优先剔除。
[0020] 优选地，步骤S3中将调度子集中的每个数据流切分成若干个子流，包括如下步骤：
[0021] S31：对调度子集中的数据流按照周期进行升序列排列；
[0022] S32：计算超周期，即该调度子集中所有数据流的周期的最小公倍数；
[0023] S33：针对每条数据流构建从0到超周期之间的等差数列，等差数列的公差为对应数据流的周期；
[0024] 按照升序合并所有等差数列，并去掉重复值，记录每个数据流的周期在合并后的等差数列中出现的位置编号；
[0025] S34：从小到大依次计算每条数据流在周期内的可分配时隙数；
[0026] S35：每条数据流的可分配时隙数除以位置编号得到该数据流周期内需要分割的平均可用时隙长度 ，则子流数量 ， 表示向上取整，其中 表示该数据流的周
期内数据持续时间；
[0027] S36：根据子流数量 对每条数据流进行分割：如果 ，表示该数据流的子流就是自身，如果 ，则该数据流的前 个子流的长度相等，表示为 ，最后一
个子流的长度为 ，为用户自定义或根据算法进行计算。
[0028] 优选地，步骤S36中， ， 表示向下取整。
[0029] 优选地，步骤S4中对每个调度规划集合进行约束建模，模型如下：
[0030] 约束变量：
[0031] 其中， 表示在链路 上，数据流 的第j个子流 在第个循环周期内的起始时间偏置；链路 属于数据流 的路径， 和 为链路
两端的节点；数据流 的循环周期数 ， 表示超周期， 表示数据
流 的周期， ； ， 为调度子集 中数据流的
数量； ， 为数据流 的子流数量；
[0032] 约束条件：
[0033] 边界约束：
[0034]
[0035]
[0036]
[0037] 其中， 表示数据流 的最晚截止时间； 表示子流 的长度；
[0038] 弥散度约束：
[0039]
[0040] 其中， 是可调参数； 是数据流 的周期内数据持续时间；
[0041] 本地抖动延迟约束：
[0042]
[0043] 其中， 表示数据流 在周期间的偏差抖动要求；
[0044] 节点间时延和抖动约束：
[0045]
[0046] 其中， 包含单个节点对于子流的交换时间； 表示时钟同步精度；链路 和链路 为数据流 的路径中的相邻链路；
[0047] 端到端时延和抖动约束：
[0048]
[0049]
[0050]
[0051]
[0052] 其中， 和 分别表示系统业务实际需求的时延和抖动要求； 表示路径中的最后一条链路； 表示路径中的第一条链路；
[0053] 冲突避免约束：
[0054] 针对 ， ， ，， ，
，满足：
[0055] 。
[0056] 一种针对周期性数据流的规划调度系统，其特征在于，包括调度子集生成模块、可调度性判断模块、剔除模块、调度规划集合生成模块和约束求解模块，其中：
[0057] 调度子集生成模块：对获取的周期性数据流集合中的数据流进行划分得到若干调度子集；
[0058] 可调度性判断模块：判断调度子集是否可调度；
[0059] 剔除模块：剔除不可调度的调度子集中的数据流；
[0060] 调度规划集合生成模块：将调度子集中的每个数据流切分成若干个子流，每个调度子集中所有的数据流的子流构成一个调度规划集合；
[0061] 约束求解模块：对每个调度规划集合进行约束建模和约束求解，求解时间规划调度参数，对数据流进行调度。
[0062] 优选地，调度规划集合生成模块包括排序模块、超周期计算模块、等差数列生成模块、位置编号计算模块、时隙计算模块、子流数量计算模块和分割模块，其中：
[0063] 排序模块：对调度子集中的数据流按照周期进行升序列排列；
[0064] 超周期计算模块：计算超周期，即该调度子集中所有数据流的周期的最小公倍数；
[0065] 等差数列生成模块：针对每条数据流构建从0到超周期之间的等差数列，等差数列的公差为对应数据流的周期；
[0066] 位置编号计算模块：按照升序合并所有等差数列，并去掉重复值，记录每个数据流的周期在合并后的等差数列中出现的位置编号；
[0067] 时隙计算模块：从小到大依次计算每条数据流在周期内的可分配时隙数；
[0068] 子流数量计算模块：每条数据流的可分配时隙数除以位置编号得到该数据流周期内需要分割的平均可用时隙长度，该数据流的周期内数据持续时间除以平均可用时隙长度
并向上取整得到子流数量；
[0069] 分割模块：根据子流数量对每条数据流进行分割。
[0070] 一种针对周期性数据流的规划调度设备，包括处理器、存储器及存储在存储器上并可在处理器上运行的计算机程序，其特征在于，所述处理器执行所述程序时实现任意一
项所述针对周期性数据流的规划调度方法。
[0071] 一种计算机可读存储介质，其上存储有计算机程序，其特征在于，该程序被处理器执行时实现任意一项所述针对周期性数据流的规划调度方法。
[0072] 有益效果：本发明具有如下有益效果：
[0073] 1、本发明主要解决周期性大流量和小流量通过网络时如何保证确定性传输的问题，通过合理的规划，本发明可以适配流量特征，根据流量特征即周期、数据大小等需求规
划可调度策略，自适应的在每一个交换机的控制端口控制时隙参数；
[0074] 2、本发明可以最小化基于预设规划调度技术的调度变量个数，同时最大化端口带宽利用率，通过本发明所述的规划调度方法可以适应更多流量数目和更大规模节点的网
络，为其提供确定性传输规划提供保障；
[0075] 3、本发明可以用于周期性大流量采集系统的网络确定性调度，如车载、工业用摄像头、激光雷达、毫米波雷达、周期性传感器设备等通过网络进行传输；同时可以用于周期
性小流量的网络确定性调度，如控制报文、监测报文等在同一网络中传输以保证其确定性。
附图说明
[0076] 图1为本发明的周期性数据流进行规划和确定性调度方法的流程图；
[0077] 图2为本发明的周期性数据流分割方法的流程图；
[0078] 图3为本发明的周期性数据调度传输模型；
[0079] 图4为本发明的一种实施例中的通信拓扑图。
具体实施方式
[0080] 下面结合附图对本发明作更进一步的说明。
[0081] 本发明提供一种针对周期性数据流的规划调度方法，适用于小流量和小流量之间、小流量和大流量之间以及大流量和大流量之间的规划调度问题，如图1所示，主要步骤
如下：
[0082] S1、对周期性数据流集合 进行划分，求出最小独立规划子集即调度子集 ，四元组 表示周期性数据流的参数，其中： 表示周期内
数据流的起始时间偏置，C表示周期内数据流持续时间，D表示周期内数据流的最晚截止时
间，T表示周期。
[0083] 划分时根据数据流集合中各数据流对应的源地址src_addr、目的地址src_addr以及路径path对这些数据流进行归类，具体操作步骤如下：
[0084] S11、首先将源地址src_addr、目的地址src_addr以及路径path相同的数据流归为初始类；
[0085] S12、如果初始类之间存在路径重叠，则将这些存在路径重叠的初始类中的数据流合并成一个调度子集，其他的不存在路径重叠的初始类各自作为一个调度子集；
[0086] S13、如果存在调度子集 、 和 ，其中 ， ，而 ，则需要将集合 和集合 从原调度子集中分离出来
作为新的调度子集，其中， 表示空集。
[0087] S2、针对每一个调度子集 进行初步可调度性判定，判定的依据如下：
[0088]
[0089] 其中， 为调度子集 的序号； 为调度子集 的可调度性判定指标； 和分别表示调度子集 中的数据流 的周期内数据持续时间和周期， 表示数据流
的占用比。
[0090] 若公式所示值为大于0且小于1，即 ，则该调度子集 被判定为潜在可调度；否则该调度子集 被判定为不可调度。
[0091] 如果调度子集 被判定为不可调度，则需要重新对数据流集合S进行划分后生成新的调度子集，或者根据需要剔除不可调度的调度子集 中的数据流，缩小调度子集规
模，然后再次进行判定。其中，剔除调度子集 中的数据流时，若数据流存在优先级，则根
据数据流的优先级进行剔除，即优先级低的数据流优先剔除；若所有数据流的优先级相同，
或者根据优先级剔除数据流后的调度子集仍然不可调度，则再根据用户自定义规则执行，
例如根据数据流的占用比进行剔除，即占用比大的数据流优先剔除。被剔除的数据流根据
业务需求进行处理。
[0092] S3、如图2所示，如果每个调度子集 都被判定为潜在可调度，则对每个调度子集中的数据流进行如下操作：
[0093] S31、将调度子集 中的数据流按照周期T进行升序列排列，并按照排列顺序分配标号 ，其中n为调度子集 中数据流的个数。
[0094] S32、根据流分割方法将数据流 切分成 个子流， 的求解过程如下：
[0095] 计算超周期，即调度子集 中所有数据流的周期的最小公倍数。
[0096] 针对每条数据流构建从0到超周期之间的等差数列，等差数列的公差为对应数据流的周期。
[0097] 按照升序合并所有等差数列，并去掉重复值，记录每个数据流的周期在合并后的等差数列中出现的位置编号，其中，等差数列中第一个数的位置编号为0。
[0098] 从小到大依次计算每条数据流在周期内的可分配时隙数，其中数据流 的可分配时隙数为 ， 和 分别为数据流 的周期内
数据流持续时间和周期。
[0099] 每条数据流的可分配时隙数除以位置编号得到该数据流周期内需要分割的平均可用时隙长度 ，则子流数量 ，这里的 表示向上取整。
[0100] 如果 ，表示数据流 的子流就是自身，如果 ，则前 个子流的长度相等，表示为 ，最后一个子流的长度为 ，其中 可以
是用户自定义，也可以根据算法进行计算，例如 ，这里的 表示向下取整。使用
表示数据流 的子流集合，其满足保序要求，则调度子集 中所
有数据流的子流构成一个调度规划集合。
[0101] S4、根据流量特征即周期、数据大小等需求规划可调度策略，对上述每个调度规划集合进行约束建模和约束求解，根据求解结果求出每个子流的时间规划调度参数 ，自适
应的在每一个交换机的控制端口控制时隙参数。
[0102] 通信网络由端节点集合 和交换节点集合 组成，对于发送节点 ，通过路径 发送给接收节点
，其中 ，路径上的节点对 构成节点 到 的链路，如
， 表示链路。对于所有的数据流 ，都有其对应的路
径，这些路径构成路径集合 。 中所有数据流的超周期为
，则针对数据流 的循环周期数为 。
表示在链路 上的数据流 ， 表示链路 上的数据流
的第j个子流 ； 表示子流 周期内的起始时间偏置；
表示对应子流 在第 个循环周期内的起
始时间偏置； 表示对应子流的长度。
[0103] 其中建立的约束模型如下：
[0104] 约束变量为：数据流在对应路径中所有链路上的、在超周期所包括的循环周期内的所有子流的起始时间偏置，即 。其中， 表示在链路
上，数据流 的第j个子流在第 个循环周期内的起始时间偏置，一般是可行解就可以；优
选最小值，取最小值的好处就是在系统触发时间靠前从而不会超过周期内数据流的最晚截
止时间D。
[0105] 约束条件：
[0106] 1、边界约束：每条子流要在周期内，即对每个 ，在第 个周期的取值范围为大于或等于该周期起始值 ，并且小于或等于该周期最晚截止时间减去
对应子流的长度 ，即：
[0107] 针 对 ， ， ，，满足：
[0108]
[0109]
[0110]
[0111] 2、弥散度约束：子流内的分散程度满足弥散程度约束，即每个周期内最后一个子流 和第一个子流 的时间跨度不建议隔得太远，即：
[0112]
[0113] 其中， 是可调参数，一般建议大于1；
[0114] 3、本地抖动延迟约束：同一个端口不同周期对应的子流间偏差不宜太大，以第1个循环周期的第 个子流 作为基准，后续周期 中对应子流
与 的偏差抖动小于或等于数据流 在周期间的偏差抖动要求
，即：
[0115]
[0116] 4、节点间时延和抖动约束：节点 的数据经过节点 交换传输到节点 ，链路到链路 的对应子流间保持相应的时延和抖动，即：
[0117]
[0118] 其中， 主要包含单个节点对于子流的交换时间， 表示时钟同步精度；
[0119] 5、端到端时延和抖动约束：接收节点完全接收最后一个子流 和发送节点开始发送第一个子流 的端到端时延和抖动约束，即：
[0120]
[0121]
[0122]
[0123]
[0124] 其中， 和 分别表示系统业务实际需求的时延和抖动要求；
[0125] 6、冲突避免约束：一个IPS子集内流要满足彼此不交叠的约束，此处我们以数据流和数据流 建立如下约束不等式，这里一般是在同一链路上的对比，且两个对应的循环
周期要交叠，才可以比较处于各自周期内的子流：
[0126] 针对 ， ， ，， ，
，满足：
[0127]
[0128] 其中， 表示与， 表示或；
[0129] 7、端口带宽约束：所有流占 用的带宽不能超过端口带宽 ，针对，， ， ， 表示链路
上的数据流集合，满足：
[0130]
[0131] 此约束在判断调度子集是否可调度时已进行判断，因此可省略。
[0132] 求解上述约束模型，若有解则说明可调度，得到调度时间规划；若无解则说明不可调度。
[0133] 传统方案中，数据流大小只能变成定长的packet或者frame进行调度，当数据流大小较大时，调度变量个数太大；而本发明所述约束模型中，变量个数依赖于数据流个数和数
据流流大小及周期，本发明将数据流大小和周期转化为子流个数进行调度，子流大小大于
甚至远大于packet或者frame，能最小化调度变量个数，也可以适应更多流量数目和更大规
模节点的网络。
实施例
[0134] 如图3所示，首先通过了解数据流集合 中所有通信数据流的传输路径，从而得到所有交换机输出端口（如图中（SW1，OP2），（SW2， OP1），（SW3，OP1））所
需要的承载数据流集合，通过路径回溯算法找到调度子集。
[0135] 本 实 施 例 中 的 通 信 拓 扑 图 如图 4 所 示 ，对 应 的 数 据 流 集 合，其中数据流 、 和 对应的路径信息为[b,1]‑[c,
0]‑[c,3]‑[d,0]‑[d,1]‑[g,0]；数据流 对应的路径信息为[o,1]‑[e,0]‑[e,1]‑[p,0]‑
[p,2]‑[f,0]‑[f,1]‑[g,0]；数据流 和 对应的路径信息为[a,1]‑[o,0]‑[o,1]‑[e,
0]‑[e, 1]‑[p,0]‑[p, 4]‑[r,0]。
[0136] 根据源地址、目的地址以及路径可以将数据流集合分为3个初始类，分别为 、 和
；其中，初始类 和 之间存在[e,0]‑[e,1]‑[p,0]‑[p,2]的路径重
叠，因此将 和 组成一个调度子集 ，不存在路径重叠的
初始类 作为一个调度子集 。
[0137] 数据流集合 S中的各个数据流对应的参数如下表1：
[0138] 表1
[0139]
[0140] 由此可以计算得到，调度子集 的可调度性判定指标：
[0141]
[0142] 调度子集 的可调度性判定指标：
[0143]
[0144] 因此，调度子集 和调度子集 均为潜在可调度，不需要对数据流集合S重新进行划分或者对调度子集 和调度子集 进行剔除数据流。
[0145] 以调度子集 为例，其中的数据流周期 ，， ，超周期为1200，针对每条数据流构建从0到超周期之间的等
差数列并将其合并后为：
[0146]
[0147] 因此，数据流 对应的位置编号为Index1=1，数据流 对应的位置编号为Index2=4，数据流 对应的位置编号为Index3=8。
[0148] 计算每条数据流的可分配时隙数，其中，数据流 的可分配时隙数，数据流 的可分配时隙数
，数据流 的可分配时隙数
；
[0149] 则可以得到：数据流 的平均可用时隙长度 ，数据流的平均可用时隙长度 ，数据流 的平均可用时隙长度
；
[0150] 进而得到：数据流 的子流数量 ，子流 的长度为 ；
[0151] 数据流 的子流数量 ，第一个子流 的长度为，第二个子流 的长度为
；
[0152] 数据流 的子流数量 ，前四个子流 、 、和 的长度分别为 ，第五个子流 的长度为
；
[0153] 综上所述，针对调度子集 ，其中每条数据流都有各自的子流，即 ， ， 。
[0154] 针对调度子集 对应的调度规划集合建立约束模型：超周期为1200，因此数据流 在超周期内一共有8个循环周期，数据流 在超周期内一共有2个循
环周期，数据流 在超周期内一共有1个循环周期，因此在数据流对应的路径中的每个链
路上有如下的待求解值：
[0155]
[0156]
[0157]
[0158] 约束条件如下：
[0159] 边界约束 ：
[0160] 针对数据流 ：
[0161] ，
[0162] ，
[0163] ，
[0164] ，
[0165] ，
[0166] ，
[0167] ，
[0168] ，
[0169] 针对数据流 ：
[0170] ， ，
[0171] ， ，
[0172] 针对数据流 ：
[0173] ， ，， ，
，
[0174] 弥散度约束：
[0175] 针对数据流 ：子流只有一个，天然满足该约束；
[0176] 针对数据流 ： ，
[0177] 其中， 是可调参数，一般建议大于 1；
[0178] 针对数据流 ： ， 是可调参数，一般建议大于 1；
[0179] 本地抖动延迟约束：
[0180] 针对数据流 ：
[0181]
[0182]
[0183] …
[0184]
[0185] 针对数据流 ：
[0186]
[0187]
[0188] 针对数据流 ：超周期内只有一个周期，天然满足该约束；
[0189] 节点间时延和抖动约束：
[0190] 数据流 对应的路径信息为[o,1]‑[e,0]‑[e,1]‑[p,0]‑[p,2]‑[f,0]‑[f,1]‑[g,0]，则对于子流 ，有：
[0191]
[0192]
[0193]
[0194] 数据流 对应的路径信息为[a,1]‑[o,0]‑[o,1]‑[e,0]‑[e,1]‑[p,0]‑[p,4]‑[r,0]，则对于子流 、 ，有：
[0195]
[0196]
[0197]
[0198] 数据流 对应的路径信息为[a,1]‑[o,0]‑[o,1]‑[e,0]‑[e,1]‑[p,0]‑[p,4]‑[r,0]，则对于子流 、 、 、 、 ，有：
[0199]
[0200]
[0201]
[0202] 端到端时延和抖动约束：
[0203] 数据流 从节点o到节点g的延迟：
[0204]
[0205] 抖动：
[0206]
[0207]
[0208]
[0209] 数据流 从节点a到节点r的延迟：
[0210]
[0211] 抖动：
[0212]
[0213]
[0214]
[0215] 数据流 从节点a到节点r的延迟：
[0216]
[0217] 抖动：超周期内只有一个周期，天然满足该约束；
[0218] 冲突避免约束：
[0219] 数据流 、 和 ，两两之间需要彼此错开：此处在同一链路上，比对子流数量可以 得到1*8*2*2+1*8*5*1+2*2*5*1=92个不等式 ，例如：由 于
表示数据流 的第三
个循环周期和数据流 的第一个循环周期彼此交叠，可以得到如下约束：
[0220]
[0221] 表示在链路 上，在第三个循环周期内的子流 和在第一个循环周期内的子流 之间彼此错开，其他子流依此类推。
[0222] 端口带宽约束：
[0223] 这个约束在判定初期已经使用，此处是为了约束完整性，即：
[0224]
[0225] 并非对于 的约束，可以删除。
[0226] 对上述约束进行求解，若有解则可以得到各个循环周期内的，各条链路上的，数据流 、 和 的各条子流的起始时间偏置，并按该起始时间偏置对数据流 、 和
进行调度；若无解，则数据流 、 和 不可调度。
[0227] 本发明还公开了一种针对周期性数据流的规划调度系统，包括调度子集生成模块、可调度性判断模块、剔除模块、调度规划集合生成模块和约束求解模块，其中：
[0228] 调度子集生成模块：对获取的周期性数据流集合中的数据流进行划分得到若干调度子集；
[0229] 可调度性判断模块：判断调度子集是否可调度；
[0230] 剔除模块：剔除不可调度的调度子集中的数据流；
[0231] 调度规划集合生成模块：将调度子集中的每个数据流切分成若干个子流，每个调度子集中所有的数据流的子流构成一个调度规划集合；
[0232] 约束求解模块：对每个调度规划集合进行约束建模和约束求解，求解时间规划调度参数，对数据流进行调度。
[0233] 其中，调度规划集合生成模块还包括排序模块、超周期计算模块、等差数列生成模块、位置编号计算模块、时隙计算模块、子流数量计算模块和分割模块：
[0234] 排序模块：对调度子集中的数据流按照周期进行升序列排列；
[0235] 超周期计算模块：计算超周期，即该调度子集中所有数据流的周期的最小公倍数；
[0236] 等差数列生成模块：针对每条数据流构建从0到超周期之间的等差数列，等差数列的公差为对应数据流的周期；
[0237] 位置编号计算模块：按照升序合并所有等差数列，并去掉重复值，记录每个数据流的周期在合并后的等差数列中出现的位置编号；
[0238] 时隙计算模块：从小到大依次计算每条数据流在周期内的可分配时隙数；
[0239] 子流数量计算模块：每条数据流的可分配时隙数除以位置编号得到该数据流周期内的平均可用时隙长度，该数据流的周期内数据持续时间除以平均可用时隙长度并向上取
整得到子流数量；
[0240] 分割模块：根据子流数量对每条数据流进行分割。
[0241] 本发明还公开了一种针对周期性数据流的规划调度设备，包括处理器、存储器及存储在存储器上并可在处理器上运行的计算机程序，所述处理器执行所述程序时实现所述
针对周期性数据流的规划调度方法。存储器可为各种类型的存储器，可为随机存储器、只读
存储器、闪存等。处理器可为各种类型的处理器，例如，中央处理器、微处理器、数字信号处
理器或图像处理器等。
[0242] 本发明还公开了一种计算机可读存储介质，其上存储有计算机程序，该程序被处理器执行时实现所述针对周期性数据流的规划调度方法。存储介质包括：U盘、移动硬盘、
ROM、RAM、磁碟或者光盘等各种可以存储程序代码的介质。
[0243] 以上所述仅是本发明的优选实施方式，应当指出：对于本技术领域的普通技术人员来说，在不脱离本发明原理的前提下，还可以做出若干改进和润饰，这些改进和润饰也应
视为本发明的保护范围。
