DARYN算法：智能运输系统中的分配过程

通过对集中式算法的分析，我们知道要使用调度程序计算每列火车的路线的主要原因，是因为在某个瞬间可能有两列或更多的火车需要使用同一条轨道。如果由完全独立的非协同的计算单元进行计算，就可能导致火车相撞。DARYN提出一种试图消除碰撞的解决方案，其原理是在以必要的最小同步并行执行算法的自然实体中分配整个决策进程时，要求所有的决策保持一致性。这种情况下，才能最大限度地利用并行处理的优势。这个“自然实体”指的是在系统中确实存在的物理实体。

在DARYN算法中，会将决策过程分配给系统中已嵌入处理器的站台和机车。每列火车和每个车站都同时独立地执行自己的决策子任务，只要服从必要的同步，并不断保持一致性，那么整个系统的执行速度就会更快。与机车相关联的处理器处理整个网络的轨道布局。由于轨道实际布局改变的频率非常低，因此把车载计算机储存的这些信息作为其初始化的一部分是实际可行的。本书假设车载计算机总是存有整个轨道的布局，尽管存储量看起来似乎很大，但是只需要使用32GB（还在不断增加）以上的U盘就可以很容易且经济地满足这个要求。假定大部分轨道布局是稳定的，当轨道布局由于故障、日常维修或其他情况产生微小的变化时，火车很容易就可以从邻近的站台计算机读取到这个变化。根据这一变化，火车R_i上的车载计算机TC_i重新评估费用函数，为R_i再确定一条优化路线。为了实现这个目标，车载计算机还必须和专门控制轨道的站内计算机相互联系，因为每条轨道都由一个独立的车站计算机专门控制，所以一个站附近的轨道实际上都由这台车站计算机控制。

初始化阶段，每条轨道都是空的，每列火车停在始发站，火车的运行路线还没有确定。初始化后，每列火车完全了解整个网络的布局状况，包括轨道的位置和占用轨道的列车位置，并且每台车站计算机也都知道自己控制的轨道的情况。火车R_i通过评估费用函数确定了自己的最佳路线后，向控制该最佳路线上第一条轨道的车站计算机发出一条请求信息。该请求以消息的形式，由R_i发送到当前站S_j，如果S_j是R_i需要使用的这条轨道的管理者，它会对所有这样的同类请求进行检查，根据先到先得的原则和优先权情况，制定解决方案。也就是说，是由车站来决定所有要求使用某条轨道的火车可以进入该轨道的最小时间。只有和最小时间对应的那条请求会被批准，其他的都会被拒绝。对原始请求的回应由S_j传给R_i。如果S_j不是火车要求使用的那条轨道的管理者，请求会被重新发送给正确的车站计算机S_k，S_k发出的回应通过S_j返回到R_i。当火车R_i使用某条轨道的请求获得批准时，火车就会沿该轨道向它的最优路径子集中的下一站前进。但是，如果请求被拒绝，车载计算机必须重新评估次优路线，并且为申请新路线上的第一条轨道而重复上述过程。如果一列火车的轨道请求在始发站或任意一个中间站被一再拒绝，车载计算机还是得不断发出请求（这很可能是一个潜在的问题），直到火车获准占用下一条轨道，它才能从它当前所在的车站开出。这样才可以保证决策的绝对一致性。当火车到达下一站时，它又重复同样的协商过程。这里，每个车站的计算机都有两个功能：①接受或拒绝列车占用它所控制的轨道的请求；②帮助火车向相应的车站计算机发送路线请求，并反向回应。这个过程一直持续到所有火车都到达目的地为止。

因此，在DARYN中，车载计算机只有当火车停靠在站台时才能发出请求。可以想象，车载计算机与车站计算机通过光学、红外线或其他方式互联互通，火车一进站，该通信过程就会启动。由于火车可以高达200km/h的最大速度行驶，而一般车站的长度为200m，所以站台与列车之间最小接触时间约为3.6s，它至少是火车与站台的数字计算机协商所需的CPU时间（毫秒）的几倍。因此，大多数情况下，火车与车站计算机在协商过程中甚至不用真正地停在站台。此外，一旦原来计算的最佳路线中某条轨道的使用请求被拒绝，车载计算机必须在火车驶出站台范围之前重新计算出一条新的最佳路线。从逻辑上讲，有人可能会赞成在火车起动之前，允许它请求为其预留最佳路线中两条或更多的连续轨道。虽然这种做法可能对制定有效的长期规划更有利，但是也可能会由于太早保留轨道，或者由于轨道被过早锁定，而影响到其他火车的最优路径计算，从而导致系统的整体性能降低。因此，DARYN算法只考虑未来，并要求只有立即要使用的轨道才能预留。此外，虽然一般情况下费用函数的性质会比较复杂，但在本章中，我们假定了一个简单的费用函数，即如果每条轨道的使用成本相同，在它上面行驶的每列火车就有相同的优先权。假设火车网络的坐标是一个X-Y坐标，其中一列火车要在X（水平）和Y（垂直）方向上分别移动M和N个单位，费用函数就会强制火车在M和N值较大的那个方向上先移动。当M=N时，任意选择X或Y方向都可以。

DARYN算法中的一个必要条件是每个车站和火车都要配备有与一个绝对标准时钟同步的时钟。在初始化时，所有时钟都必须同步重置为0。这样就确保了所有请求、回应和决策在时间上的一致性。(www.xing528.com)

图4.3的网络是DARYN算法的一个例子。在图4.3中，A～D的车站通过轨道T₁～T₄连接。假设A的车站计算机控制轨道T₁和T₄，而B和D的站台计算机分别控制轨道T₂、T₃。而C的站台计算机不控制任何轨道。车站计算机之间通过沿着轨道铺设的通信线路进行通信。假设，在某个时刻，系统内有4列火车R₁、R₂、R₃和R₄。火车R₁和R₂分别在t=0和t=5时到达站A，且它们都要开往C。火车R₃和R₄分别在t=0和t=5时到达站C，且它们都要开往A。DARYN中，假设火车R₁、R₃、R₂和R₄确定它们的最佳路线分别为{T₄，T₃}、{T₂，T₁}、{T₁，T₂}和{T₃，T₄}。因此，R₁请求站台计算机A预留轨道T₄，同时R₃通过站台计算机C传送预留轨道T₂的信息给站计算机B。这两个请求都获准，然后火车将会沿各自预定的轨道移动。假定轨道的长度和火车的速度是：R₁以t=7个单位时间到达站D，R₃以t=4个单位时间到达站B。在t=4时，R₃会发出一个请求，而且会收到来自站台计算机A关于轨道T₁的批准信息。假定列车R₃在t=6时到达A。那么在t=5时，列车R₂向A发出一个T₁轨道的请求会被拒绝。然后R₂会重新评估自己的路线，假定它决定向A发出请求占用轨道T₄，而轨道T₄又会一直被占用直到t=7时，因此请求还是会被拒绝。列车R₂就可能重回其第一选择，重新向节点A请求T₁轨道。这个过程一直持续到t=6，此时A批准R₂的请求。然后，R₂会在t=8时经由T₁轨道到B。类似的，在t=5时，列车R₄向D发出一个请求T₃轨道的信息，然后请求被批准。因此，R₄通过T₃向D移动，然后会在t=8时到达D。同时，列车R₁在t=7时到达D，并且向D发出请求轨道T₃的信息，这个请求被拒绝。由于R₁没有选择，它不得不在节点D等待，直到在t=8时获得D发出的可用轨道T₃的批准。这个过程一直持续到4列火车都到达目的地为止。可以看出路线决策是由各自的车载计算机决定的，而轨道分配是由站台计算机执行的，因此，该算法的处理能力会明显高于传统算法。

图4.3 DARYN算法示意图

决策的计算过程相当复杂，由于DARYN将决策任务分发到铁路网的每一个物理实体（机车及车站）中，并在各自独立的处理器上进行计算，所以整体数据处理能力会大大高于在单处理器上执行的传统算法。此外，在DARYN算法中，火车和所在车站之间的通信速度是最快的，而和邻近车站之间的通信是最差的。因此，DARYN算法的总通信时间会远低于每列火车和轨道都将信息发送到固定的调度计算机的传统算法。最后，随着火车和轨道数量的增加，该系统规模也会增加，计算的要求和计算引擎的数量也会随之增加，但是DARYN算法中总CPU时间的增长速度很可能会比相应的传统算法要慢得多，这体现了DARYN算法的极佳性能。