精确并行处理试验台上模拟DICAF现实效果

DICAF的主要贡献在于通过网络把全部车辆的路径计算任务分配给DICAF中的所有实体——车辆和DTMC来共同完成。因此，事实上，对于一个包含V辆车和D个DTMC的DICAF系统来说，共同参与计算的单元总数是V+D。为了理解DICAF的性能和不同因素对它的影响，我们首先要对DICAF建模，然后在一个并行处理试验台上进行仿真，该试验台是由配置松耦合并行处理器的工作站网络构成的，在试验台上进行的仿真非常类似于实际操作。为了能对一个拥有一定数量汽车的实际系统进行真实仿真，每个DTMC都表示成工作站，车辆则被模拟成任务，然后由工作站在DTMC指挥下来运行。当车辆沿着高速公路路段行驶时，它的计算就由控制该路段的DTMC中的工作站来进行。每辆车都表示成一个以消息形式从这个DTMC转移到下一个DTMC的进程。同时车辆信息用一个数据结构来表示，该数据结构的字段中存储了车辆的重要参数，这些字段包括推荐速度、实际速度、起点和终点。当车辆从当前的DTMC（A）行驶到另一个DTMC（B）时，A工作站中对应进程的重要参数就被压缩成消息传递给B工作站，并在B工作站中以一个进程的形式再次出现。因此，在仿真过程中车辆是以电子速度而不是物理速度移动的。对路段上的行驶过程来说，车辆路径的计算子任务由控制该路段的DTMC中的工作站来完成。因此，DICAF能够以比实际快很多倍的速度对高速公路系统进行模拟。

本章假定了一个典型高速公路系统是以网格形式组织的。DTMC安装在每个交叉口处，虽然看起来它应该可以控制最多4个方向的路段，即与最多4个路段连接，但在实际中它最多只可能控制位于它东、南两个方向的路段。对于安装在高速公路系统网格图底部的DTMC而言，是没有南向路段的。同样，对于安装在公路系统网格图最右端的DTMC来说，是没有东向路段的。因此，它们能控制的最大路段数是一致的。

每个DTMC都以下列数据结构表示它所控制的高速公路路段区间的重要信息：根据DTMC在网格中的位置，用第1个字段“index”存储DTMC的唯一标识符。而第2～5个字段与DTMC东面的高速公路路段区间相关，第6～9个字段与DTMC南面路段相关。对于东向路段，C.M.值以mile/h为单位存储到字段“eastCM”中。如果路段不存在，该字段会被赋值为-1。“eLastSent”存储的是某路段的最新C.M.值，该值刚刚被传递给了其他DTMC，“eSeq”指的是该值的序列号。字段“eCar”存储的是当前行驶在路段上的车辆数。最后4个字段southCM、sLastSent、sSeq和sCar分别与eastCM、eLastSent、eSeq和eCar相对应。

除此之外，每个DTMC都不断地为DICAF中所有其他路段更新C.M.值。这种更新是根据从其他DTMC中周期性接收到的泛洪消息而进行的。当一辆车与一个DTMC连接时，为了确定路径，它会下载一部分数据库。为提高内存的使用效率，每个DTMC都有一个规格为MAX_DTMC的指针矩阵，如下所示：

typedef struct DTMC*DTMC_PTR；

DTMC_PTR DTMC[MAX_DTMC]；

在初始化过程中，为了存储DICAF所模拟的高速公路系统中所有路段的C.M.值，会动态分配一些额外的内存。

DICAF使用两种消息类型：一种是将车辆信息封装起来，并模拟车辆从一个DTMC转到其下一个DTMC的过程，另一种是为路段传递更新了的C.M.值。被用来封装车辆信息的数据结构中，字段“origin”存储车辆出发地DTMC的标识符，而字段“dest”存储终点DTMC的标识符，车辆的唯一标识符存储在“id”中。该标识符由生成车辆的DTMC分配，是由DTMC标识符和该DTMC产生车辆的序列号组合而成的。字段“update”和“from”存储的信息用于指引接收DTMC更新关于C.M.的本地信息以及与路段有关的其他信息。如果车辆当前行驶路段属于该接收DTMC的管辖范围，就会被标上“update”标志。字段“from”是用来区分DT-MC的东向或南向路段是否需要更新的标志。字段“inserted”包含车辆进入该路段时间，字段“appSec（以s为单位）”和“appMSec（以ms为单位）”共同存储了车辆按计划应该出现的时间，即到达终点DTMC的时间。可以证明，它可以根据路段长度和车辆沿路段行驶的速度计算获得。字段“trvSec（以s为单位）”和“trvMsec（以ms为单位）”则共同存储了车辆从起点到达当前位置的实际累计行驶时间，字段“idealTrvSec（以s为单位）”和“idealTrvMSec（以ms为单位）”共同存储的是车辆从起点到终点需要的理想行驶时间，即理论上的最少运行时间。字段“speed”存储的是车辆沿当前路段行驶的速度，字段“prefSpeed”是指期望车速。

每个DTMC中的工作站的工作过程都在图6.5中以虚拟代码的形式表示出来。(www.xing528.com)

图6.5 DICAF中的“main”流程

在图6.5中，前两句是与初始化过程有关的。在初始化期间，DTMC中的工作站通过软件链路来相互连接，以使最后形成的网络能与实际路网相对应。此外，DTMC生成的车辆都拥有唯一的标识符和随机分配的终点。当期望车速为随机值时，服从正态分布。生成的车辆先放在DTMC的等待车辆列表中，并根据车辆进入路段或者沿着正确路段离开DTMC的时间先后顺序进行组织。DICAF仿真可以一直持续进行，直到仿真时间结束为止。仿真步骤分为以下几个阶段：第一阶段，读取输入的信息，并利用函数Process_Message进行处理，如图6.6所示。在这个函数中，根据获得的泛洪消息产生新的消息，即更新的C.M.值，在更新了本地数据库后，该消息就继续传递到其他DTMC中。如果输入的消息是一辆封装后的车辆，它在当前的DTMC中会以车辆-进程的形式重新出现，并被加入到等待离开的车辆清单里。第二阶段，检查等待离开的车辆清单，以确定某辆车在当前时间下是否必须离开DTMC。计算车辆路径，并以消息的形式封装起来，传递给下一个DTMC。同时，受影响的高速公路路段的C.M.值要被重新计算并传递给其他DT-MC，该过程一直持续到仿真过程终止为止。

图6.6 DICAF中的“process message”流程

图6.7中的伪代码详细说明了函数“check wait-to-leave list”的组织过程。在仿真期间，如果当前时间就是等待离开车辆清单中的某辆车离开DTMC的时间，首先会从清单中抽出该车，然后利用路网中最新的路段C.M.值确定该车的路径，接着就将该路径消息传递给所选路径上的下一个DTMC。对于某个给定的路段，车辆无论进入还是驶出这个路段，C.M.值都会发生变化，这就使清单中包含了两类车辆—①标记为“正常”的进入该路段的车辆；②正驶出该路段的“影子”车辆。由于只有DTMC的管辖者才能为路段维护C.M.值，影子车辆的进出能帮助确保C.M值在车辆完成该路段行驶任务后得到及时更新。

如果更新后的路段C.M.值与之前的值完全不同，DTMC的管辖者必须通过泛洪算法将信息传递给其他DTMC，对应的函数是“Update_segment”。在这个过程中，会给每条消息赋以一个序列号以避免重复传输。当消息从原DTMC传播到相邻的DTMC时，该DTMC使其序列号增大。当此条消息被另一个不同的DTMC接收时，只要该消息的序列号比上一个C.M.值对应的序列号更新，接受DTMC就会将此消息传递给与它相邻的DTMC。该算法以伪代码表示，如图6.8所示。

图6.7“Check wait-to-leave list”函数

图6.8 DICAF中“Update_segment”函数