1.一种时间敏感网络中路径选择和门控调度的联合优化方法,其特征在于:包括以下步骤:S1:集中式网络配置模块CNC发现时间敏感网络TSN网络拓扑,并将TSN网络拓扑抽象为网络有向图;
S2:终端设备通过用户配置协议向集中式用户配置模块CUC发送TSN连接请求,CUC将所述连接请求通过用户网络接口UNI发送到CNC;
S3:CNC收到路径选择的需求时,执行融合路径选择与门控调度算法选出K条最短路径作为备选路径;步骤S3中所述选出K条最短路径作为备选路径,具体为:采用K最短路径算法KSP,对于所有ESi,ES′i∈H,基于它们的最短路径递增排序,通过输入网络有向图G、发送端ESi、接收端ES′i和路径的条数K,输出K条路径集pK,然后将路径集pK作为步骤S4的输入;具体执行步骤如下:S31:输入网络有向图G、发送端ESi、接收端ES′i和备选路径数K;
S32:CNC使用融合路径选择与门控调度算法求出ESi到ES′i的最短路径,并记为pn(n=
1):
pn=ESi→BRa→BRb→…→BRn→ES′i
S33:判断n是否小于等于K,且仍有候选路径存在,如果存在执行S34,否则表示找到K条备选路径;
S34:在求出pn的基础上,根据偏离点和Dijkstra算法求出pn+1,把位于pn上除去接收端ES′i的每个节点分别看作偏离点,共有x个;将每个偏离点记为BRi(i=1,2,...,x);
S35:开始遍历偏离点,从BRi(i=0)开始遍历每一个偏离点,并对每一个偏离点求BRi到接收端ES′i的最短路径;
S36:将pn上从起点到BRi的路径加上求得的BRi到接收端ES′i的最短路径作为求pn+1的候选路径,放到候选路径列表U中;
S37:偏离点遍历结束;
S38:判断此时候选路径列表U是否为空;
S39:如果此时候选路径列表U不为空,则遍历完偏离点后,找出B中权值最小的路径即为所求的pn+1,将该路径从U中移除,并放入备选路径列表L中,在求得pn+1的基础之上,当n+1≤K时,继续执行步骤S33‑S38,否则表示找到K条备选路径;
S310:若候选路径列表U为空,则表示已经找到了K条备选路径,最后确定路径集合为Pk={p1,p2,…,pn,pk}∈Psd,Psd表示从ESi到ES′i的路径集合;
S4:CNC将步骤S3中选出的K条备选路径利用路径关键度ηk来选择出m条优选路径;步骤S4具体包括:路径pk的跳数HC为除发送端和接收端之外的路径pk的TSN交换机数量(用pk.HC表示),定义如下:pk.HC=len(pk)‑2 (1)
路径pk的剩余带宽SBW为其所有组成链路中的剩余带宽的最小值,假设pk={ESi,BR1,BR2,…,BRn,ES′i},令S=len(pk)‑2,路径pk的剩余带宽SBW由如下公式表示:路径pk的端到端时延DL为其链路时延 之和,表示为;
函数Δ(HC,SBW,DL)用于映射其路径关键度ηk为一个介于0和1之间的值;在所有备选路径集pk中,选择ηk最大的路径作为路径选择阶段的输入路径;对于路径pk∈Psd,ηk表示如下:ω1+ω2+ω3=1 (5)
其中 SBWmax表示所有路径pk∈Psd中的最大值SBW;HCmin是所有pk∈Psd中最小的HC,DLmin是所有pk∈Psd中最小的DL;ηk的值越大则表示网络的跳数越小,剩余带宽越大,网络延迟越小;
通过以上方式计算每一条路径pk的路径关键度ηk的值,选取前m条ηk值最大的路径作为优选路径,并存入优选路径集Rant中;
S5:CNC将步骤S4中选出的m条优选路径作为路径选择阶段的输入,根据TSN流量类型的特征,基于链路传输的代价和信息素更新的方式为一对发送端到接收端的TT流找到一条最优的传输路径,并将该条路径存入路径信息表ω中,同时为非TT流找到合适的传输路径;所述步骤S5中,基于蚁群算法找到最优传输路径,具体包括以下步骤:S51:先设置初始化参数,从预选路径阶段输出融合路径选择和门控调度算法的初始路径表Rant;设置蚂蚁禁忌表Rb,算法最大循环次数Ncyc,蚂蚁的最大数量Nant,信息素总量Q;
S52:判断流量类型,根据TT流和非TT流分别设置影响因子α和β,链路权重因子δ和ε,信息素挥发系数ρ,信息素增量Δτ;蚂蚁置于发送端,并将发送端存入Rb中;
S53:循环次数ncyc=ncyc+1;
S54:蚂蚁数量nant=nant+1;
S55:蚂蚁根据公式(6)选择下一个节点:
其中,P(BRi,BRj)表示蚂蚁a从节点BRi到BRj的传输概率,allowa表示从节点到下一个节点的集合,α越大,信息素的指导作用越强,β越大,蚂蚁决策受路径距离信息影响越大,贪婪当前效果;δ和ε为权重因子且δ+ε=1,0<δ<1,0<ε<1,δ和ε的取值根据当前流量类型而定,当数据流为TT流时,δ的取值小于ε;τ(BRi,BRj)表示链路(BRi,BRj)的信息素数量;μ(BRi,BRj)表示节点选择的启发因子; 表示链路(BRi,BRj)的剩余带宽; 表示链路(BRi,BRj)的延迟;
S56:判断是否到达接收端,如果未达到接收端,返回S55;如果到达接收端,将该蚂蚁的走过的路径存入路径表Rte中,将该路径节点存入禁忌表Rb中,避免与下一只蚂蚁的路径产生交叉,然后跳转至S57;
S57:判断nant是否等于Nant,如果nant<Nant,则返回S54,如果nant=Nant,从Rte中选取传输代价TV最小的路径作为该次循环得出的最优路径存入最佳路径集合R中,跳转至S58;
S58:判断ncyc是否等于Ncyc,如果ncyc≠Ncyc,返回S53,根据公式(8)更新链路中的信息素,清空Rb;如果ncyc=Ncyc,则跳转到S59;
ρ表示信息素的挥发系数,0<p<1,τ(BRi,BRj)表示链路(BRi,BRj)的信息素数量,Δτ(BRi,BRj)表示链路(BRi,BRj)的信息素增量;
Δτ(BRi,BRj)取值根据TSN数据流类型而确定,其表达式如下所示:Q表示信息素的总数量, 表示链路(BRi,BRj)的传输延迟,路径选择系数的表达式如下所示:
S59:根据TSN流量类型,分别输出TT流和非TT流的最优传输路径;如果是TT流fi,从路径集合R中选择延迟最小的路径作为最优路径,可表示为 如果是非TT流f′i,从路径集合R中选择N非TT流条路径作为输出最优解,并且进行转发;
S6:CNC遍历是否存在还没有被计算发送端和接收端的路径,如果有则返回执行步骤S3‑S6,并将计算的每对发送端到接收端TT流的最优路径存到路径信息表ω中,如果没有则执行步骤S7;
S7:将步骤S6中计算出的TT流量的最优传输路径信息表ω作为输入,设置流量传输约束条件,为每一对终端设备的TT流最优传输路径配置门控列表;
S8:CNC将计算的结果封装为门控调度表,并配置到TSN交换机,再将流量传输计算结果通过CUC发送到TSN终端设备。
2.根据权利要求1所述的时间敏感网络中路径选择和门控调度的联合优化方法,其特征在于:步骤S1具体包括:CNC根据链路发现协议LLDP来发现TSN网络拓扑,并通过网络建模方法将TSN网络拓扑抽象为网络有向图;
TSN的网络拓扑表示为有向图G=(V,E),其中V是TSN网络中的节点集合,其中S是TSN交换机的集合,H是终端设备的集合;E是边集合,是一组二元组,表示TSN网络中的所有链接,使得E≡{(BRi,BRj)|BRi,BRj∈V,BRi≠BRj并且BRi和BRj之间存在联系},其中(BRi,BRj)表示交换机BRi和交换机BRj之间的链路;
与每个链路(BRi,BRj)∈E相关联的是由元组(b,ld)表示的测量值列表,其中 是链路(BRi,BRj)的剩余带宽; 是链路延迟,由 和 组成; 是有界的;
把从发送端开始,按照一定要求传输到接收端的有序数据序列称为流,将所有的TSN流的集合记为F;对于不同类型的流,其中的主要参数包括TSN流的传输路径Ri、TSN流的端到端时延Di、TSN流的传输周期Ti和TSN流的大小Si;每个TSN流Fi表示为四元组Fi≡(Ri,Di,Ti,Si);
对于发送端ESi和接收端ES′i,中间经过的交换机BR1,BR2,…,BRn共有n个节点,将其第i对发送端到接收端的路径表示为Ri={ESi,BR1,BR2,…,BRn,ES′i},每个帧的最大长度为以太网的最大传输单元MTU。
3.根据权利要求1所述的时间敏感网络中路径选择和门控调度的联合优化方法,其特征在于:步骤S2具体包括:终端设备通过用户配置协议将备选路径数K、路径关键度ηk选出的优选路径数量m、算法最大循环次数Ncyc、蚂蚁的最大数量Nant、信息素总量Q、TSN流的周期Ti、大小Si和时延Di发送给CUC,CUC将连接请求通过用户网络接口UNI发送到CNC。
4.根据权利要求1所述的时间敏感网络中路径选择和门控调度的联合优化方法,其特征在于:步骤S7中,门控列表的循环周期GC表示为:GC=lcm(T) (11)
其中,lcm表示最小公倍数,T为所有数据流的周期,
T={f0.T0,f1.T1,...,fn.Tn}
其中fn.Tn表示流fn的周期Tn;
假设流fi∈F的每个后续帧出现的时间距离始终等于Ti,TT流fi在(BRi,BRj)上传输偏移量为 存储的队列ID为 (BRi,BRj)∈E,则流fi在链路(BRi,BRj)上的传输任意数据帧所用的时间 表示为:
根据GCL的传输规则,对时隙长度LOS进行分析,最大的时隙长度为:MAX(LOS)=GCD(T) (13)
即LOS的最大值为数据流周期的最大公约数;
最小的时隙长度为:
其中,LOG是传输队列的长度, 即队列资源全部被占用时,最后1 byte发送到链路上所花费的时间;
传输路径为{ESi,BR1,BR2,…,BRn,ES′i},交换机BRn的GCL循环开始时间 的计算公式如下:表示发送端发送第一个数据帧的发送时间, 表示流fi在链路(ESi,BR1)上的传输任意数据帧所用的时间, 表示BRi中的处理延迟, 表示BRi中的传输延迟, 表示流fi在链路(BRj‑1,BRj)上的传输任意数据帧所用的时间,synPre表示两个节点设备的时间同步最大差值;
一个交换机到下一个交换机之间的时延D的表达式如下:
表示BRn中的处理延迟, 表示BRn‑1中的传输延迟, 表示(BRn‑1,BRn)中的传播延迟;
端到端的时延约束表示为:
帧约束表示为:
链接约束表示为:
无传输持续时间的帧隔离约束表示为:
其中,
带有传输持续时间的帧隔离约束表示为:
流量传输约束表示为:
优化目标为:
引入辅助变量 表示任何流的端到端延迟与其周期之比,要求该变量的值在[0,1]中即表示调度为最优;
通过将以上的约束条件进行建模并使用求解器求解,根据每一对终端设备中TT流的最优传输路径 计算出TT流量传输路径上交换机的门控列表。