一种工业互联网平台下的路由策略设计

武帆， 王聪慧

(陕西工业职业技术学院 电气工程学院，陕西 咸阳 712000)

0 引言

传统的工业企业中，工业网络组网、信息化建设存在很多问题，由于各个设备的协议标准并不统一，导致工业应用之间无法互相通信，网络信息流受限[1]。随着5G技术在我国的商业化，使得将互联网引入工业网络中成为现实。5G通信的高带宽、低时延、高可靠和广连接特性也为工业互联网[2]的无线传输和应用提供了可能。然而，传统互联网中的路由策略基本为尽力而为的策略，不可避免的出现了如丢包、传输时延增大等问题[3]，这在工业网络中是不能被接受的，工业互联网要求网络传输应具有可靠性、实时性和优先性[4]，例如需要对生产现场某设备发送一个控制指令信息，如果延时很长，则会对工业生产造成不可预测的后果。因此我们需要对工业互联网下的路由策略进行设计改进，降低时延，保证优先性[5]。

背压算法[6]是一种分布式自适应的路由调度算法，能较好地控制网络拥塞，提高网络吞吐量，在网络高负载情况下表现良好。但背压算法在低负载情况下时延较大[7]，且无法满足工业互联网中数据包分优先等级传输的要求。为此，本文提出了一种改进的背压算法，优化算法中的积压差计算方式，在链路权值中加入优先级函数，使得数据传输时延有效降低，高优先级数据更快到达目的节点。最后进行仿真实验，仿真结果表明本算法能够改善低负荷情况下的时延较大的问题，同时使数据传输具有优先性，满足实际工业互联网的路由转发需求。

1 背压算法分析

1.1 背压算法描述

背压策略是由文献[8]提出，用于路由路径选择的算法，该算法用背压值来决定数据分发的路径。背压值越大，说明结点积压的数据包越多，故给与其更大的转发机会。

设在一个多跳网络中，有V个结点，L条链路，链路都为双向通信，用无向图G=(V,L)来表示。网络中有J个源节点和目标节点不尽相同的单播信息流数据，在工业互联网中通常为指令数据，由各个工业单元发出，定义为Data={d1,d2,…dj}。时间被分割为多个时隙，在任意时隙上我们可知网络中每个节点的各个数据包的积压情况。

首先计算积压差。(Vp,Vq)∈L为一条路径，指结点Vq为结点Vp的相邻结点，Vf为网络某信息流df的终点结点，计算结点Vp和结点Vq之间的信息流数据包的队列的积压差，且规定积压差的值为非负数，如式(1)。

(1)

然后计算路径权重。路径(Vp,Vq)上可能有多个数据流需要传输，计算出每个数据流在该路径上的积压差，然后取其中的最大值为路径(Vp,Vq)上的权重值，计算方法如式(2)。

(2)

最后进行调度策略的选择。计算出各条路径的背压差，再结合每条路径的传输速率λVp,Vq，完成最优调度策略优化，最优传输路径集合σ(t)如式(3)。

(3)

其中，Π表示可用来调度且互不干扰的路经集合；σ表示路径调度集合。在该时隙，路径(Vp,Vq)在路由调度策略下将最优种类的数据包dpq(t)从结点Vp传输到结点Vq。

1.2 算法分析

背压算法在多个传输信息需要通过信道时，优先让等待时间差较大的数据包传输。计算的积压差越大，数据应优先发送，从而实现传输效率的最优化。然而当网络刚开始传输数据时，整个网络中的负载都比较小，计算出的积压差很小，导致调度策略不容易选择下一转发结点，有可能出现积压差相等无法选择路径只能随机发送的情况[9]。这时调度策略的时延会大大增加。如图1所示。

图1 网络轻负荷状态下结点积压差

以图1中网络状态为例，网络中传输一种dk数据流，各个节点在图中用圆来表示结点，圆外的数字表示该数据流在本结点所对应的队列长度，各条链路上的传输速率相同。以a结点传输数据包为例，e结点为数据流目的节点，可以看到，a结点与相邻任意节点的积压差都为0，背压策略无法提供合适的方案，数据包只能随机选择结点进行发送。因此，当网络规模较大且负载较小时，背压算法的效果较差，网络性能下降，出现较大传输转发时延，有待优化。

在工业互联网平台下，数据的重要性并不一样。例如，一条指令数据操作一个机械臂抓取货物，与一条报表数据上传给上位数据中心，这两条数据流在转发时，如果指令数据发生比较大的时延，可能会对工业生产带来较大的损失和安全问题；相反，类似上述的报表数据这种不是特别重要的信息数据流发生一定的滞后和延迟，则不会特别影响整体的工业研发与生产。因此，对于工业互联网路由的数据转发和性能优化，设计数据优先级是有必要的。

2 路由方案设计

2.1 设计思路

背压算法是基于两个相邻结点的积压差来进行调度，只考虑了一跳内。图1中a结点向e结点发送数据，可以考虑加入一跳之外的一些信息来修正积压差，使得数据能够更加倾向于向目的结点进行转发，从而改善积压差较小时算法时延较大的问题。

为了实现上述功能，我们尝试使用当前结点到目的结点的最小跳数作为修正量对积压差进行修正，使得数据流偏向于目的结点进行转发。在图1中，a结点与c、d、b、f、g、x、y、z结点的积压差都为0，加入距离目的结点的最小跳数之后的修正量值为式(4)—式(6)。

(4)

(5)

(6)

积压差修正，a点与b-d的积压差相同，如式(7)。

(7)

a点与f、g的积压差相同为式(8)。

(8)

a点与x、y、z的积压差相同为式(9)。

(9)

因此b、c、d点的积压差最大，数据流向这3个结点进行转发。

然而当几个相邻结点到达目的结点的跳数也相同时，这样的优化又失去了作用，如上述分析中的b、c、d点的修正积压差相同，路由只能在这3个结点中随机选择一个进行数据包转发。考虑加入各个转发结点的其他所有信息流的数据转发队列长的均值，因为这个均值可以反映该结点上待转发数据的多少，如果该值较大，说明此结点上拥塞的数据包较多，最好不选择该结点转发。故我们可将各个结点所能容纳的最大队列MaxLength与各个信息流数据的队列均值求差，即式(10)。

(10)

将此值加入到积压差中，再次修正积压差。

对积压差进行修正后，计算路径的权值。在计算权值时，考虑为其乘以优先级函数，如果数据优先级较高，则其乘积越大，计算出的背压越大，优先转发的几率越高。

2.2 目标修正函数与优先函数

根据上小节分析，我们引入了目标修正(Target Refinement, TR)函数，其作用是调整各个结点间计算出的背压算法的积压差值，使得信息数据包向着目的结点转发，且选择转发传输压力较小的结点进行跳转。

(11)

TR函数的表达式为式(12)。

(12)

对积压差修正完成后，开始计算链路的背压。在式(2)中加入重要数据包优先(Important Packet First, IPF)函数，用来加大优先级较高的数据流的背压，加快其转发的速率，降低其时延。加入IPF函数后，路径背压算式变为式(13)。

(13)

IPF函数的形式为式(14)。

IPFdf(t)=ηdf(t)·e-ρdf(t)

(14)

式中，ρdf(t)为数据流df的优先级，数值越小优先级越高，从数据报文中解析得到该值；ηdf(t)为优先系数，根据网络的不同而定，以确保高优先级数据的背压足够大。

2.3 转发策略的工作流程

在每个时隙的开始，我们就可以计算出每个结点上的各个数据流队列长度的均值，由于上个时隙只转发了一个数据包，因此只需对上个时隙计算出的值进行修正，然后计算原始队列差值，再根据上文式(11)和式(12)计算TR函数修正过的积压差值，再从数据流中取出数据包的优先等级，计算IPF函数，得到路径背压差。根据各条路径上的速率，找到权值最大的路径进行数据包传输，如图2所示。

图2 提出路由策略的工作流程图

在计算TR函数时，到目的结点的跳数可以在网络拓扑组建完成之时就计算出来，算法中需要用到某个结点到另一结点的跳数时直接使用即可。因此，无论TR函数还是IPF函数，其计算的时间复杂度都是在常数复杂度O(1)上，因此并不增加原始背压算法的时间复杂度。

3 仿真测试分析

为比较原背压策略与提出的工业互联网平台的路由优化策略的性能，我们进行了实验仿真。仿真平台使用MATLAB 2017b。

实验采用了GEANT网络拓扑结构，如图3所示。设置网络结点20个，待传输数据150种，不同结点之间的跳数在组网时已预先计算完成。各个结点在每个时隙根据请求速率进行数据包转发。考虑做两组对比实验：原始背压算法和改进后的算法在数据流优先级相同时的性能对比，以及原始算法同一数据在不同优先级情况下的性能对比。其网络参数全部保持一致，如表1所示。

图3 仿真网络拓扑图

表1 仿真参数

我们采用数据转发的时延大小作为算法性能比较的量化指标。首先定义时延和总时延的概念。时延指某个数据从发送结点到接收结点所需要花费的时长，总时延指各种数据从其发送结点到接收结点的时长总和。

设置仿真时间为200个时隙，调整请求速率，在第一组对比试验中记录总时延作为比较指标，进行5次实验取平均值；在第二组实验中固定请求速率，调整4个数据内容的优先级，对比这4组数据的发送时延与原始算法时延的关系。

仿真结果如图4和图5所示。在仿真测试中可以看到，当所有数据流优先级相同时，改进的路由策略在总时延上比原方案降低了21%，最大降低了39.5%，优化效果比较明显。在给4组数据分别给与从高到低的四个优先级后，发现最低优先级数据比原算法转发时延大了36%，而最高优先级的数据转发时延比原始算法中时延减少了54%，转发时延大大减小。

图4 优化效果对比

图5 不同优先级优先级数据转发时延对比

实验结果可以看出，设计的路由策略是有效的，引入TR函数和IPF函数后可以达到降低网络时延和快速发送优先数据包的效果。

4 总结

针对工业互联网平台下对路由策略的低时延、优先性的要求进行了分析，提出了一种改进的背压路由转发算法，引入TR函数修正积压差使在网络低负荷状态下时延较大的问题得到了一定改善，并设计IPF函数调整背压使高优先级数据快速通过链路。仿真实验对改进前后的路由策略进行了对比，结果显示优化后的路由策略在时延上和转发优先性上有一定的优势。