实验台模拟RYNSORD：精确、实时、并行处理的结果

RYNSORD最重要的贡献就是把网络中所有火车的路径计算任务分配给系统的所有实体——火车和站点来完成。因此，在现实中，对于一个有N列火车和S个车站的铁路网，协调式计算引擎总数就是N+S。为了解RYNSORD的性能及不同因素对它的影响，我们首先对它进行模拟，然后在一个并行处理实验台上进行仿真，该实验台由配置有松散耦合并行处理器的工作站联网组成。结合实验台进行的仿真实际上与真实情况下的执行非常类似。为了模拟一个真实的系统，必须有一定数量的火车，而每个站点都用一个工作站表示，火车被模拟为任务，并由车站的基本工作站执行。当一列火车停在一个主站时，它的计算是由车站的基本工作站完成的，它与其他车站的通信也是通过这个车站进行的。当一列火车从当前车站（A）行驶到另一个车站（B）时，基本工作站将车站A的火车-任务进行封装，以消息的形式传送给车站B，并在车站B中重新显示为基本工作站的一项火车-任务。因此，火车在仿真中是以电子速度而不是物理速度移动的，而火车的计算和通信任务由主站的基本工作站执行。

尽管火车能以约120mile/h的速度运行，但是实验台的快速计算机能使仿真以比现实快很多倍的速度运行，这有助于对RYNSORD中不同参数值进行快速评估。仿真过程中的基本时间单位称为1个时间步长，它是仿真中火车移动的最佳分辨指标。任一火车的最小行驶距离被限制在1个时间步长内，同时，如果没有得到必要的预留批准，火车就需要在车站等待至少1个时间步长。在目前RYNSORD的实施过程中，实际运行的每个时间步长值设置为1min，主要是因为：①即使是最快的火车，在1min内的行驶距离也仅为2mile，明显小于50mile的最短轨道长度；②为处理后续N段轨道的预留，车站与火车之间所有必要的计算和电子通信都可以在1min内完成。一列火车可能需要几分钟才能驶过一条单轨，而信息的传播和计算只需大约10ms。RYNSORD允许火车异步地进入系统，即在不同的时间段内进入。除此之外，火车本身是独立的，因而它们的决策是异步执行的。而且，实验台是由具有不同时钟速度的异构工作站组成的。因此，为了保证系统中火车传播的一致性和准确性，RYNSORD要求每个站点和火车的时间步长值同步。例如，在RYNSORD模型中，尽管处理器和通信链路速度可能不同，但是Ta必须在Tb之前到达E。上述要求就可以确保Ta和Tb在实际时间12：01PM和12：05PM分别到达终点站E。RYNSORD的同步是利用空消息^[40，41]的一个异步分布式离散事件模拟技术来实现的，这里就不详细介绍了。

前面提到的假设，即与一个预留请求有关的所有的消息通信和决策的过程，都必须在一个时间步长内完成，有这样几层含义：如果车站A的一列火车Ta在时间步长t₁启动一个预留包，并将其传播到其他合适的车站（X，Y，Z，…），预留包就必须在该车站内进行处理，并且在车站A和车站（X，Y，Z，…）中的每个基本工作站的时间步长值增加到t₁+1之前返回到车站A的Ta中。为了实现这个目标，RYNSORD采用了一种特殊的同步节点，该节点与所有站点相连，它用于监测：对所有在车站外发出的预留请求的必要的通信和回应，是否能在允许的站点增加时间步长值之前完成。RYNSORD中这种特殊的同步节点是试验台上并行仿真的一个产物，在现实中并不存在。在一个实际的铁路网中，电子通信和计算需要10～100ms，这段时间内最快的火车也只行驶了18ft（1ft=0.3048m）的轨道。因此，在实际中，通信和计算基本都是瞬时完成的。

每个车站站点和特殊的同步节点的基本功能被分别封装在图5.4和图5.5所示的伪代码中。

图5.5 特殊的同步节点功能伪代码

RYNSORD需要交流4类消息：首先是要表示由火车启动和发出的“预留包”；第二是模拟火车从一个站到下一个站进行消息封装和传播过程；第三，如果一列火车提早到达轨道前端的车站，为了能比预定时间更早地行驶到下一段轨道，允许该火车和控制站点进行协商；第四是车站允许火车立即行驶在某段轨道上。假设预留包的传递没有任何延迟，即一旦一个车站收到预留包，就在同一步长时间内立即对其进行处理；最终被批准的预留包也要在同一步长时间内返回到始发站。在始发站，火车在初始化时是没有预留包的，然后，该火车产生并发送预留包，一旦收到已批准的预留包，火车就会选择预留包中的一个作为最佳选择，于是就有了自己的预留包。然而，这个预留包只适用于随后的N段轨道，而且火车必须不断重复这个过程直到它到达最终目的地。下面对组成预留包的5个字段进行解释。

预留包：

1）车站列表：完整的车站列表包括每个车站的车站编号、到达时间和离开时间。

2）状态：预留的状态——①预留，如果预留包沿着车站列表中的路线向前推进，就是在试图预留；②删除，如果预留删除包正在向前传播，就是在解除先前批准的预留；③接受，如果预留包返回到起始站就接受预留。

3）火车编号：火车的唯一编号。id=（起始站×100000）+火车被引入系统的时间。

4）火车速度：当原始请求不能得到满足，车站必须修改火车的预留时间时，就必须知道速度信息。利用速度信息计算通过轨道的行驶时间，用以确定下一个预留时间段。

5）预留编号：预留的唯一编号。

由于火车从一个站到下一个站可能需要很长的行驶时间，因此假设“火车包”不是瞬间传播的。事实上，每个火车包都已被盖上了时间戳值，这个值表示它预计到达终点站的时间步长。一旦收到一个火车包，站点就会将其存储在缓冲区，直到火车包的时间戳值等于车站的时间步长值时。然后假设火车已经到达站点，并启动下一步处理。一个火车包由6个字段组成，下面对其列举并详细说明。

火车包：

1）时间戳：火车预计到达接收站的时间。

2）火车编号：火车的唯一编号。编号=（起始站×100000）+火车被引入系统的时间。

3）起点：火车的始发站。

4）终点：火车的终点站。

5）路线：火车行驶轨道的顺序列表，该列表用于进行数据收集与分析。

6）预留：与这列火车有关的预留包。

由于火车可以要求取消先前批准的沿某条路线的轨道预留请求，所以当火车决定选择备用路线时，抵达车站的火车可能会发现其下一条要使用的轨道是空闲的。为了提高轨道的使用效率，在可能的情况下，应该允许火车沿着轨道继续行驶。为实现这个目标，当一列火车在它预定离开那个节点的时间之前到达该车站，它就会产生并传播一个“等待包”给这段轨道的管理车站。一旦收到等待包，对应的车站就会对火车进行排队。在每个时间步长内，车站检查轨道是否空闲，并说明轨道空闲的时间步长数（如Q）。然后，车站从排队的火车中选出一列（如果有的话）等待时间最长的火车，这列火车有可能在Q时间步长内成功通过该轨道。车站发送一个“许可包”给这列火车，允许它立即使用轨道，并从队列中删除对应的进入请求。这种等待包由4个字段组成，如下所示，而许可包只包含一个字段。

等待包：(www.xing528.com)

1）火车编号：火车唯一的编号。编号=（起始站×100000）+火车被引入系统的时间。

2）火车速度：计算火车通过下一段轨道的行驶时间时必须要知道火车速度。

3）等待开始时间：火车比预定离开时间早到达车站后的排队时间步长。

4）位置：火车等待的地方，轨道的头部或尾部处的车站。拥有该轨道的车站利用这个信息可以指引许可包的传递方向（必要时）。

许可包：

火车编号：火车唯一的编号。编号=（起始站×100000）+火车被引入系统的时间。

为了更好地理解RYNSORD中火车的分布式动态路径计算，以及不同参数对RYNSORD性能的影响，我们使用一个图形化终端来实现RYNSORD操作的可视化显示。该图形支持以下功能：

①开发和编辑铁路网。

②观看仿真运行的重复放映。

③在运行时，监测并与仿真互动。

④查看关于输入流量、结果和运行一次仿真时的实时表现的统计信息。

运行实时显示器也显示以下参数：

①火车的位置。

②在各个车站处理的预留累计数。

③在各个车站等待的火车数量。

④沿各个路段传播的预留累计数，按类型分为预留、删除、接受。

⑤已经传播到每段轨道的火车累计数。

图5.6是图形界面的一个截屏图，它详细显示了图5.8中有50个车站的铁路网络。在图5.6中，每个车站被标记为其名称的前三个字符，并赋予唯一编号。通过这个界面很容易增加或删除车站和路段，该图形程序还能自动、正确地重置RYNSORD以准确执行仿真。图5.7给出了一个实际模拟运行的屏幕截图。火车用圆圈表示，位于其行驶轨道的顶部，并通过它们各自对应的编号、起点和终点来区别。在实际模拟运行过程中，用户可以和任一车站相互通信，以获取所有需要的数据结构和信息，并可以在任一时间步长，从任一车站生成并将火车引进系统中。

图5.6 图形界面的一个截屏

图5.7 一个实际仿真运行结果的截屏