分布式输送系统节点路由控制算法设计＊

同济大学机械与能源工程学院 上海 201804

0 引言

在工业生产中，各类输送系统对生产效率的提高起着至关重要的作用。自动化仓储系统，物流配送中心和柔性制造系统等环境中的输送系统，具有由多通道及交叉节点构成的网络结构。随着工业自动化水平的上升，系统呈现大规模化和复杂化的趋势，控制难度越来越大。

以往对这类输送系统的控制多采用基于全局信息的集中式控制。由于输送系统随着规模的扩大控制器处理的信息量呈指数增长，在复杂的输送系统中，继续采用集中式策略将难以实现实时有效的控制。

借鉴计算机网络的分布式控制思想，提出基于节点主动控制的分布式输送系统模型[1]。与传统的输送系统相比，它的不同之处在于其控制主体为分布在网络中的节点而非中央计算机。与计算机网络相似，系统通过多个节点的动态路径选择来为输送实体规划最优路径。

模型的控制算法包括两部分：最优路径算法和防碰撞、冲突机制。

分布式网络最优路径规划问题作为网络关键问题之一，很多学者投入研究，提出了一系列相关协议。陈文平等[2]提出基于距离矢量的多下一跳路由信息协议，将最优路径上较大流量很好的分散，从而降低网络拥塞的风险。胡日新等[3]通过对RIP协议进行改进克服了原协议“坏消息传得慢”的缺点。

防碰撞、冲突机制是运输系统控制的关键问题之一，研究成果丰富。Rajotia S等[4]通过在网络系统中节点和弧上建立时间窗，指示它们的占用情况，并在这些时间窗的约束下规划最优路径以避免碰撞。Kim 和Tanchoco[5]对以上算法进行了优化，提出了短视策略，即某一时刻只考虑单一实体最佳运行路径，并考虑先前所有的时间窗设定，以此为依据选择下一条路径，降低了计算难度。

本文首先简述节点主动控制输送系统模型组成及运行原理，通过分析模型确定算法要达到的要求。然后提出本文设计的分布式控制算法。最后，通过面向对象仿真建模对算法性能进行验证。

1 分布式输送系统模型

1.1 模型组成

如图1所示，模型是一个网络结构，主要包括节点、弧、输送实体、中央管理机等。

图1 分布式输送系统控制模型

1）节点（node） 节点是本模型的核心组成，它不仅是作为多条弧交汇的物理存在，同时还是整个模型的控制主体。节点上的嵌入式设备集成了通信模块、RFID读写设备和控制器。使得节点能与其他节点和中央管理机进行信息交互，同时能读取输送实体上电子标签的信息，另外，它还能控制本节点和相连弧的动作。

2）弧（arc） 起着连接节点，传输实体的作用。在本模型中，弧均为双向弧（Bi-directional arc）,即在同一条弧中，实体的运输方向可以不同。

3）输送实体 指输送系统输送的对象，比如仓储系统的货物，生产线上的在制品等。本文输送系统模型中的运输实体贴有RFID电子标签。

4）中央管理机 负责模型中成员的管理，即时更新成员信息以及系统结构变化。

1.2 模型运行原理

分布式输送系统控制模型运作的基本思路是利用现代RFID技术动态地标识放到载货台上准备输送的单元式实体，并让运行时所经过的节点来选择需要传送的输送设备。

各模块化载货台将其空闲或忙碌状态通过AP访问点传送至管理计算机，确定任一时刻可供使用的载货台。货箱放上载货台后，计算机管理系统通过 RFID 读写设备往货箱上的RFID标签中动态地写入所需要传送的起始位置和目标位置等信息。当货箱被传输到下一个交叉节点时，交叉节点处嵌入式系统的RFID 读写设备和控制设备会获取货箱上的起始目的位置等信息，由此再利用网络路由技术，使用这些位置信息为该货箱选择下一条传送模块进行传送，并通过建立防碰撞、冲突机制避免碰撞和冲突。

2 基于距离矢量的多下一跳路由算法

2.1 节点路由表

模型中的节点需要获得所有其他节点的信息，这些信息包括达到某个节点的距离以及路径选择。这些信息在节点中用表来存储，称为节点路由表。

实体输送系统中节点的路由表包含目的节点、距离和下一跳节点等3个表项。其中，目的节点和下一跳节点都是用节点的Id地址来表示的，典型的节点路由表如2所示。

2.2 上游节点和下游节点

假设节点ni到节点nj的最短路径长度为。对于目的节点nk，ni到nk的最短路径长度为，nj到nk的最短路径长度为。如果为则称对于目的节点nk，ni是nj的下游节点，nj是ni的上游节点。上游节点和下游节点的概念是相对的，定下了目的节点之后，节点之间的上下游关系才能比较，两节点之间的上下游关系会随着目的节点的不同而改变。

图2 节点路由表

以图3为例，假设每两个相连节点之间的路径长度均为10，就目的节点n15而言，对于n7,根据计算，它到目的节点的最短路径长度为30，n11和n6到目的节点的最短路径长度分别为20和40，根据以上定义，n11为n7的下游节点，n6为n7的上游节点。更进一步，可以通过计算得出，n7的上游节点集合为{n1，n2，n3，n5，n6，n9，n13}，它的下游节点集合为 {n8，n11，n12}。

图3 上下游节点图例

2.3 算法描述

输送系统的节点通过路由表来存储系统中所有其他节点的信息，并且对于指定的目的节点而言，当前节点只存储下一跳为下游节点的信息。

输送系统运行之初，通过配置，节点路由表存储关于相邻节点的信息。

在之后一段时间之内（视系统复杂程度而定），所有的节点不断和相邻节点交换信息，交换的信息为节点所有的路由信息，即路由表。在交换的过程中，不断更新自己的路由表，直到所有的节点获得正确的路由信息。在这段时间之后，除非输送系统的结构发生变化，否则各节点之间不再交换路由信息。现对此交换过程中用到的距离向量算法描述为

假设网络节点集为N，节点i的邻居节点集为Ni，本文算法有两个输入：1）本地节点i接收自邻居节点k关于目的节点j的最优距离；2）邻居节点Id。

本地节点ni接收邻居节点nj的最优路由，读取它到目的节点nk(nk≠ni)的距离：

1 If (本地节点ni不含到目的节点nk的路由表项)

2 目的节点＝ ni；

3 最优下一跳＝ nj；

6 目的节点＝nk；

7 最优下一跳＝ nj；

8 次优下一跳=原下一跳节点；

11 目的节点=nk;

12 次优下一跳＝ nj；

15 ；//路由表不作变动

16 End if；

算法说明为

第1行到第4行 当节点ni收到节点nj到达目的节点nk的当前最优路由信息时，节点ni判断路由表中有没有到达目的节点nk的路由，如果没有，则将节点nj作为到达目的节点nk的最优下一跳节点，节点ni到目的节点nk的最优距离暂定为+。

第5行到第9行 如果路由表中已存在到达目的节点nk的路由，且则将节点nj作为最优下一跳节点，最优距离更新为，原路由表项作为次优路由信息存储在最优路由表项之后。

第10行到13行 如果路由表中已存在到达目的节点nk的路由，的话，说明获得新的下游节点nj，但非更优，令距离等于，下一跳为nj的新表项加入到最优表项之后，作为次优表项。

第14行到第16行 如果路由表中已存在到达目的节点nk的路由，且说明节点nj不是节点ni的下游节点，路由表不作变动。

3 基于动态时间窗交换的防碰撞、冲突机制

3.1 时间窗

当实体通过节点时，节点被实体占用一定的时间。为表征节点被占用的情况，引入时间窗的概念。

时间窗是一个时间区间，分为占用的（reserved）和空闲的（free）两种。在节点的占用的时间窗内，节点被指定的实体占用，而其他实体不得进入此节点。占用的时间窗用实体进入和离开此节点时刻之间的时间区间来表示。而空闲的时间窗则指示该节点在这个时间区间内，没有被实体占用，可供任何实体占用。一个简单的时间窗如图4所示，阴影部分表示占用时间窗，空白部分表示空闲时间窗，即时间区间[3，5]、[12，14]为占用时间窗，而时间区间[5，12]则为空闲时间窗。

图4 节点上时间窗

3.2 算法描述

在节点上设置缓冲区(buffer)，使实体能在缓冲区暂留而不占用节点。为了算法描述方便，假设实体在传送带上运行速度恒定，且传送带上没有实体时，传送带速度为零。

输送系统运行之初，所有节点时间窗均为空闲时间窗，可供任何实体占用。当一个节点向下一跳节点传输发送实体时，该节点要向其发送以下信息：传送起始时间tnow和传输速度v，下一跳节点根据这些信息和两节点之间路径长度L在本节点上新添一个时间窗，并把更新后的时间窗信息发送给所有邻居节点。具体算法步骤为

第一步：实体到达节点n1，节点n1读取实体的目的地址，查询路由表为该实体选择最优下一跳节点n2；

第二步：首先根据节点n1和节点n2之间传送带的方向来判断路径是否被占用，若传送带静止或者和实体拟传送的方向相同，则转入第三步，若传送带的方向和实体拟传送方向相反，则转入第四步；

第三步：节点n1根据到节点n2的路径长度、传送速度和当前的时间，为节点n2建立一个虚拟的时间窗，并把这个虚拟的时间窗与节点n2的实际时间窗进行对比，若两者占用的时间窗部分没有重叠，则把实体向节点n2传送，并向它发送相应的信息，节点n2根据这些信息在本节点上新添一个时间窗，并把更新后的时间窗发送给邻居节点。一个算法流程结束。反之，占用的时间窗部分有重叠，则转入第四步；

第四步：节点n1根据路由表查找是否有次优下一跳，若有，选择次优下一跳n3，令下一跳为次优下一跳,重复第二、第三步，若没有次优的下一跳，则把实体暂时存入叉道；

第五步：节点根据自己的时间窗，在本节点足够大的空白时间窗内（大于把实体从叉道调入节点的时间），定时（如每隔0.2 s）重复上述的判断（判断时要考虑把实体从叉道调出的时间），直到有可供传送的路径，把实体从叉道中调出，发送给相应节点，一个算法流程结束。

需要注意的是：防碰撞、冲突的算法是建立在节点路由表构建完成的基础之上的；实体一旦离开节点，在传送带上的传输速度不能为零，即实体不能静止地停留在传送带中。

4 算法性能仿真验证

为了验证本文所提出算法的性能，采用C++语言对分布式输送系统进行面向对象建模。在仿真程序中，可以构造任意输送系统，并加入任意数量的实体对算法性能进行验证。

通过一个具体的实例来对算法的综合性能进行验证。仿真实例图如5所示，其中大的方格表示节点，大方格右下角的小方格为节点缓冲区，连接两个节点的深色条形为传送带。

在图5所示的输送系统中，在A～L节点同时加入12个实体，目的地址分别为I、H、G、L、K、J、C、B、A、F、E、D。加入实体后，运行系统，输送系统的运行状态图如图6所示。

图5 算法性能验证图例

图6 输送系统运行状态图

通过实体在输送系统中的实际传输时间和理论最短时间比较，来评估输送系统的性能。首先，定义一个延迟比δ指标，即

式中：t理论为实体在输送系统中传输的理论最短时间，t实际为实体在输送系统中传输的实际时间。

对实例中实体传输时间和延迟比统计如表1，实体在传输过程中，成功避免碰撞。由表1可知，加入系统的12个实体中，延迟比最小的是2.5%，最大的是38.1%。平均延迟比为11.2%。

表1 节点运行时间表

从数据来看，所有的实体在输送过程中都存在一定的延时。但实际上，那些延迟时间较短的实体在输送过程中并没有在系统中滞留，它的延迟是在节点处转向造成的。

最大延迟比达38.1%，实体在系统中的滞留时间较长。造成节点滞留的原因是实体经过的路段太过拥挤，使得实体多次被存入缓冲区等待。由此可以得出结论，输送系统中同时传输的实体越多，造成实体输送的时延比将越大。输送单元理论、实际传输时间对比见图7，输送单元传输延迟率见图8。

图7 输送单元理论、实际传输时间对比

图8 输送单元传输延迟率

验证的结果显示，系统能有效避免输送系统中实体的碰撞，能以较小的时延把实体传输到目的节点，能达到较高的吞吐量水平。

5 结语

本文设计分布式路由控制算法能使系统中的实体在无碰撞、冲突的情况下以较小的时延到达目的节点，同时系统能达到较大的吞吐量水平。后续研究将是在节点或弧发生故障时，节点路由表进行相应的调整以实现网络的快速自愈，提高算法的稳健性。