有向图在CBTC 系统中的应用

陈凌安

(上海自仪泰雷兹交通自动化系统有限公司)

0 引 言

根据IEEE 中的定义，CBTC 系统是一种不依赖于轨道电路的高精度的列车定位，双向连续、大容量的车－地数据通信和车载、地面安全功能处理器来实现列车连续自动控制的系统。因此，高精度的列车定位是实现CBTC 的基础。如何从CBTC 系统软件上，设计和管理列车的位置，以及其他与CBTC 功能相关的信号设备的位置等信息，是本文需要讨论的问题。

本文首先从有向图的理论，来分析城市轨道交通线路与有向图的相似性。然后，从城市轨道交通的静态信号设备和动态信号设备两个方面，来分析有向图的运用及重要作用，最后说明有向图理论在CBTC 系统中的实用性。

1 有向图理论

有向图是一个二元组＜V，E ＞，其中，V 是非空集合，称为顶点集。E 是V×V 的子集，称为弧集。如图1 所示，是典型的有线图的形式。

图1 有向图形式

因此，在有向图上可以用＜E，偏移量＞来表示图上任意一点的信息，并且任意点＜Ei，偏移量j ＞还具有唯一性的特点，不存在二义性的问题。

2 有向图理论在CBTC 中的应用

通过以上对有向图的理解，城市轨道交通线路类似于一个有向图，如图2 所示。通过引入有向图的概念，我们可以充分利用有向图中的数据结构和算法，来实现一些设备管理和搜索的算法，并可以将这些算法和数据结构运用到CBTC系统的软件中。

在图2 中，整个的轨道交通线路，以道岔和线路终端作为有向图的节点ni。节点nj和节点nk之间的线路或者道岔为有向图的边si。并且，si具有一定的方向性，在图中规定所有向左的方向定义为边的正方向。

通过以上方式，可以唯一得确定轨道上任何一点的位置，用(si，offset)来表示。

图2 线路拓扑结构图

2.1 静态设备的管理

静态数据是指其在城市轨道交通线路图中位置同定不变的数据类型，主要包括静态线路数据和线路拓扑数据。对于CBTC 来讲，静态设备主要包括以下内容:

(1)轨道线路

(2)信标

(3)站台

(4)区段

(5)信号机等。

如图3 所示，为上海某商用运营线路的部分设备布置图。采用有向图的方法来管理和搜索信号设备，是一种高效的方法。以定位信标transponderi为例，对于具体的信标来讲，transponderi∈sk，同时，

其中，sk的正方向相邻边为sn，sk的反方向相邻边为sm。

采用有向图的方法，可以借鉴图论的经典搜索算法来实现CBTC 系统中的信标搜索功能。这样，既提高了算法的效率，又合理地设计了信号设备的软件数据结构。同样，对于其他的静态信号设备，都可以采用这种方式来实现存储和管理。

2.2 动态设备的管理

对于CBTC 下的动态设备来讲，主要就是列车。由于CBTC 的实现依赖于高精度的列车定位，那么如何确定以及实时更新列车的位置，在CBTC 系统中是一个主要的问题。采用有向图的方法，可以很简洁地表示列车的位置信息。

图3 上海某商用运营线路部分信号设备平面布置图

假设列车所在的位置是traink(si，offsetm)，如果列车运行了distance，则更新后的列车位置计算，可以采用如图4 的算法来实现:

图4 更新列车位置算法

因此，采用有向图的方法，可以很方便地实现更新列车位置的算法，并且该算法还具有一定的通用性，比如说，可以运用到搜索一定区域范围内的信号设备信息等方面。

3 结 论

综上所述，通过将有向图理论应用到城市轨道交通的CBTC 系统中，可以解决如下的问题:

(1)CBTC 系统中的设备信息管理;(2)CBTC 系统中的软件算法优化;(3)为实现城市轨道交通信号系统的互联互通打好基础。

［1］ Rail transit vehicle interface standards committee. IEEE standard for communication－based train control performance and functional requirements.1999.