列控系统RBC 测试序列优化生成方法

齐凡瑞，李 强，2

（1.兰州交通大学自动化与电气工程学院，兰州 730070；2.甘肃省工业交通自动化工程技术研究中心，兰州 730070）

无线闭塞中心（Radio Block Center ，RBC）作为CTCS-3（Chinese Train Control System Level 3）级列控系统的地面核心设备之一，是基于故障—安全计算机平台的信号处理系统，为了保证RBC 的安全性、可靠性和实用性，必须在开通前进行相关测试.目前，RBC 系统测试周期长，不稳定因素多，且测试序列的生成都是由专家根据需求规范和测试大纲手动编写，容易出现测试数据遗漏、错误和重复等问题，并且测试项的安全性和可用性也不能保证.近年来，基于模型的测试方法成为新一代铁路系统测试方法，它能在保证系统安全性的同时有效提高测试效率、节约测试成本.

在测试案例的生成方面，文献［1］提出了一种端口标记的时间输入输出自动机LpTIOA，应用Cover 工具实现CTCS-3 级车载系统LpTIOA 模型的测试套自动生成，解决了CTCS-3 级列控系统测试中存在的需要多个端口协同测试的问题，但该方法生成的测试用例抽象层次高，执行测试案例时还需对抽象测试案例中的数据进行具象化.文献［2］提出一种领域无关覆盖准则的测试用例生成算法，利用Cover 工具生成模式转换测试用例套，从而实现自动生成覆盖全部车载模式转换规则的测试用例，但该方法无法描述系统的并发行为，且不具有时序性；在测试序列的优化方面，文献［3］将列控系统车载设备测试序列优化生成问题转换为求解一个具有多重弧有向图的中国邮路问题，利用Edmons-Johnson 算法和LINGO 建模工具对中国邮路问题进行求解，但该方法优化过程复杂，往往需要二次优化.文献［4］将车载设备模式转换转化为一个旅行商问题（Traveling Salesman Problem，TSP）问题，提出一种基于SA 优化IC 算法的测试序列优化算法，实现了测试序列优化生成.

本文作者依据CTCS-3 级列控系统技术规范构造功能场景模型［5］，从功能场景模型中提取功能特征［6］，利用CPN 对RBC 单电台切换场景进行形式化建模，从生成的模型可得到状态空间可达图和XML 文件，应用路径搜索算法可以得到初始的测试案例.采用M-ACO 算法对测试序列进行优化生成，以期为高效完成测试工作，保障列控系统的安全性提供参考.

1 模型构建及验证

1.1 有色Petri 网

有色Petri 网是一种基于Petri 网的高级网系统，它具有更严谨的数学定义，能够直观地描述系统并发行为，可用于列控系统RBC 系统描述和验证，有色Petri 网的形式化定义如下

1）SSC是测试案例开始状态有限子集、SEC是测试案例结束状态有限子集；

2）IIC是测试案例输入接口有限子集、OOC是测试案例输出接口有限子集；

3）IMC是测试案例输入消息有限子集、OMC是测试案例输出消息有限子集；

注意：SSC，SEC，IIC，OIC，IMC，OMC均不能为空.

定义3 全节点覆盖标准：生成的测试序列执行时保证覆盖状态空间可达图中所有节点至少一次，其中每个节点代表一个测试案例.

本次建模采用CPN Tools 工具，CPN Tools 工具是一种用于CPN 建模的计算机仿真软件，能够对系统行为进行动态仿真，支持可视化的建模方式和层次化的建模方法，适用于构建大型复杂网络模型.CPN Tools 还可以对模型的状态特征和性能进行分析，检验模型的正确性.

1.2 RBC 切换场景建模

由于单套RBC 处理性能的约束，通常一套RBC 无法管理一整条线的所有设备，所以一般每条线都会配备多套RBC.为了保证列车能够不降速通过RBC 边界，相邻的RBC 以接力的方式不间断地为车载设备提供行车许可.在RBC 切换过程中，相邻RBC 范围内的进路信息不再由联锁提供，而是由相邻的RBC 提供.移交RBC 根据来自接收RBC 的进路授权信息，采用行车许可生成技术为车载设备生成覆盖接收RBC 管辖范围的行车许可；接收RBC 根据来自移交RBC 的列车信息为车载设备预分配进路.RBC 移交分为车载两部GSMR 无线电台都正常和只有一部电台正常的两种情况，本次讨论第二种，具体情况如图1 所示.

图1 RBC 切换原理示意图Fig.1 Schematic diagram of RBC switching principle

单电台RBC 切换CPN 顶层模型如图2 所示，该图主要模拟了移交RBC、车载设备和接收RBC 之间的信息交互过程，切换过程具体如下：

1）在只有一部车载电台正常工作的情况下，列车使用该电台与RBC1 通信（“RBC1Normal”）；

2）当列车到达预告应答器时（“ReachLTA”），车载设备向RBC1 发送位置报告；

3）RBC1 收到位置报告后，向车载设备发送RBC 切换命令（“SendHandoverOrd”）和向RBC2 发送移交列车参数信息和进路请求信息（“Send-RouteReq”）［9］；

4）RBC2 收到信息后将它控制范围内的进路信息 发 送 给RBC1［10］，注意 当RBC2 控 制 范 围 内的 进路状态改变时，应将更新信息及时发送给RBC1（“SendRouteInf”）；

5）列车通过预告应答器后（“PassLTATrain-Normal”），车载设备向RBC1 发送位置报告（“Next-State”），RBC1 收到信息后向车载设备发送切换命令（“StartHandover”）；

6）列车收到切换命令后车载设备开始呼叫RBC2，呼叫成功后与RBC2 建立通信会话［11］；列车继续向前行驶，在到达切换边界前车载设备接收来自RBC1 和RBC2 的 混 合MA（“ReceiveMixMA”）并发送位置报告（“Handover”）；

7）当列车最大安全端越过切换边界后（“MaxsafefrondPassBou”），列车向两个RBC 发送位置报告，RBC2 收到信息后向RBC1 下发接管命令，此后车载设备只接收RBC1 的终止会话消息，其他消息都不接收（“StopReceiveRBC1Inf”）；

8）当列车最小安全端越过切换边界后（“MinsaferearPassBou”），车载设备向RBC1 发送请求中断连接信息；

9）RBC1 中断与列车的连接并将其从RBC1 的列车清单中删除（“StopRBC1Link”）；车载设备收到RBC1 的中断安全连接命令后切断与RBC1 的连接，车载设备根据RBC1 先前下达的切换命令呼叫RBC2，呼叫成功后与RBC2 建立安全连接［12］；

10）RBC2 生成行车许可并发送给车载设备（“ReceiveRBC2MA”），监控列车运行，至此完成RBC 单电台情况下的切换（“RBC2Normal”）.

由于在RBC 单电台切换过程中，为使列车不减速越过移交边界，RBC1 提供的行车许可至少在RBC2 管辖范围延长一个40 s 正常行驶距离+完整制动距离的长度，CPN Tools 可以通过设置“delay函数”来模拟该延时，所以在“ReachLTA”中设置400 个时间单位的延时来模拟该时间.

图2 RBC 切换CPN 顶层模型Fig.2 RBC switching top-level CPN model

1.3 模型验证

对RBC 切换模型执行ASK-CTL 公式后的验证结果为“There is no loop terminal！”和“No Deadlock Markings！”，根据以上信息结合状态空间报告可知该模型是正确的.在CPN 建模后，可生成该模型的状态空间可达图，具体如图3 所示，图3 已删除冗余节点，为最精简模型.由于RBC 建模原理主要是从系统具体功能处理以及信息交换的角度去建立的，因此将RBC 所处状态看作库所，RBC 信息处理过程看作变迁，有向弧看作信息流动过程，一条变迁发生则表明完成某项功能的条件触发，根据变迁的代码段判断该动作是否发生，若是，则一条测试案例生成.在CPN 建模完成后，找到具有输入信息和输出信息的库所SSC、SEC，其对应的开始状态节点和结束状态节点IIC、IOC，后应用路径搜索算法找到从开始状态节点到结束状态节点之间的所有路径，得到该路径节点的特征库所信息和特征token 信息PSC*，PEC*，TSC*，TEC*，最后找到以始集库所为始端的输出弧的变量名，以变量名为输入消息ID，根据输入消息ID补充该条消息里的相关变量及变量值得到IMC，同理得到OMC，随之生成一条测试案例，由该方法生成的测试案例必须满足定义3 中的的覆盖度标准，路径搜索算法的软件实现如下.

图3 RBC 切换状态空间可达图Fig.3 Reachability graph of RBC switching state space

按照测试案例的开始状态节点和结束状态节点的状态信息，将各测试案例串联起来生成初始测试序列.但是直接串联生成的测试序列冗余度大，造成测试时间过长，进而影响测试安全，因此还需要对测试序列进行优化.

2 测试序列优化算法

传统蚁群算法（ACO）是一种启发式智能搜索算法，它描述的是一种最优路径寻找方法，具体定义见文献［13］，列控系统测试序列优化生成问题可以转化为一个旅行商问题（Traveling Salesman Problem，TSP）求解问题，TSP 问题中每一个城市可以看作是一个节点，则t时刻蚂蚁由节点i向节点j转移的概率为

式中：α为信息素启发因子，表示蚂蚁在移动过程中路径上残留信息素的浓度［14］；β为期望启发因子，表示蚂蚁选择路径的相对重要程度；allowedk表示蚂蚁k在行走时允许转移的点；τij(t)表示信息素浓度函数；s为目标节点.启发函数表达式为

式中：dij（i，j=1，2，3，…，n）表示节点i到节点j之间的距离［15］，蚂蚁在各节点中移动时，用禁忌表来放置已被选择过的城市，当蚂蚁完成一次遍历节点搜索后，对应的禁忌表被清空，为下一次探索做准备.随着时间推移，节点上的信息素会随之改变，经过ns 后节点（i，j）上的信息素浓度更新式为

式中：∆τij(t)表示节点i到节点j之间的信息素总量；m为迭代次数；ρ为信息素挥发因子，其值在0 到1 之间是为了避免路径上轨迹量无限增加.令初始τij(0)=c，∆τij(0)=0，由于该模型信息素更新为完成一次遍历后的全局更新，因此节点信息素模型的更新式为

式中：Q为蚂蚁完成一次搜寻后留下的信息素浓度大小之和；Lk表示蚂蚁在遍历完所有节点后的路径长度，传统蚁群算法作为一种启发式优化搜索算法，具有很强的稳定性和可扩展性，由于自身的正反馈原理机制使得算法能很快地寻找出最优解，它的全局搜索、正反馈、鲁棒性、分布式计算等特点体现出了求解复杂问题的优越性，然而它的缺点也很明显，一是容易陷入局部最优，二是易发生停滞［16］.

为了克服以上两个缺点，实现测试序列优化生成，对传统蚁群算法中的信息素挥发因子ρ和节点信息素模型∆τij进行改进，ρ的大小在一定程度上反映了所走路径的信息素含量，ρ值不能设置的太大或是太小，因为设置太大虽然能够加快算法的收敛程度，但会使得蚂蚁还未走过的节点上信息素挥发过快；设置太小易陷入当前局部最优，使得蚂蚁不能寻找更多的点；此外，如果将ρ设置成一个固定的值就会导致该算法搜索度降低.基于以上考量，对ρ值进行更改使其符合高斯分布，这是因为在前期蚂蚁主要根据信息素的含量选择节点路径，这时将ρ设置的小一点有助于提高模型的全局搜索能力；中期时各个节点上的信息素含量逐渐变成一个定值，将ρ设置的大一点可以增大解空间、提高搜索程度；后期节点相对较少，将ρ设置的小一点以便加快信息素的导向功能.改进后的信息素挥发因子公式如下

式中：μ为迭代完成后蚂蚁的搜索期望；σ为一次迭代完成后，遍历路径的最优路径与最差路径信息素的方差.

所有蚂蚁在一次迭代完成后将更新节点上留下的信息素含量，然而蚂蚁在走过的各个节点上留下的信息素权重不同，有些节点权重占比大.基于此，对节点信息素模型引入路段权重因子vij，从而克服传统蚁群算法易发生停滞，加快算法收敛，改进后的公式如下

3 测试序列优化生成与合理性验证

3.1 测试序列优化生成

基于M-ACO 的列控系统RBC 测试序列优化生成方法总体框架如图5 所示，主要包括以下3 部分：

1）根据《CTCS-3 级列控系统技术规范》提取功能特征，构建基于CPN 的单电台RBC 切换模型，并采用ASK-CTL 公式对CPN 建模进行验证，得到状态空间可达图和XML 文件，再应用路径搜索算法生成满足全节点覆盖的测试案例［17］；

2）测试案例生成后，根据测试案例的开始条件和结束条件将测试案例串联成测试序列，采用MACO 生成优化后的测试序列；

3）生成XML 格式的优化测试序列文档.

根据1.2 节中的RBC 的CPN 顶层模型，可以将RBC 切换分为4 个场景，对应到状态空间可达图中即得到4 个变迁场景的输入、输出节点，具体如表1所示，由于节点1、2、3、4 是4 个必须经过的节点，所以合并为一个节点A，为了满足全节点覆盖，相邻场景的两个节点之间会有重叠.在表1 中，由状态空间可达图可知场景1 有2 条路径，即场景1 生成了2 个测试案例，分别是：/12345/12346/，不同路径用“//”隔 开，以此 类推，场景2 有4 条路径，场景3 有3 条 路径，场景4 有10 条路径，可以按照测试案例开始条件与结束条件直接将测试案例串联成测试序列，但是这些测试序列中包含大量冗余测试案例，造成了测试效率低下.基于此，在C++平台上开发基于MACO 算法的测试序列自动生成软件，得到各场景的测试案例数如表2 所示，由此可知应用M-ACO算法共生成8 条测试序列，在此基础上满足重复测试案例数最少，实现了测试序列的优化生成.最终利用CPN Tools 自带的XML 保存功能得到测试序列XML 文档，如下

图5 测试序列生成方法总体框架Fig.5 Overall framework diagram of test sequence generation method

表1 输入输出节点表Tab.1 Input and output nodes

表2 优化路径表Tab.2 Optimized paths

3.2 对比分析

本文应用M-ACO 算法共生成了8 条测试序列，涵盖了《CTCS-3 级列控系统测试案例》［18］中与RBC 单电台切换的所有测试案例以及车载设备测试案例中与RBC 相关的测试案例，《TB/T 3535—2018 无线闭塞中心测试规范》中RBC 单电台切换测试内容为单电台移交，测试方法及预期结果如下：

车载设备行车许可延伸至移交边界；

移交RBC 发送移交预告，启动与接收RBC 移交流程；

移交RBC 收到接收RBC 对移交预告的应答后，发送授权相关信息请求；

接收RBC 根据授权相关信息请求，发送授权相关信息；

移交RBC 根据进路授权信息向车载设备发送信息包【3】（配置参数），并要求车载设备确认（M_ASK=1）；

车载设备最大安全前端越过移交边界；

车载设备向RBC 发送消息【ETCS-136】（位置报告）；

移交RBC 向接收RBC 发送移交通告；接收RBC 向移交RBC 发送接管职责；

车载设备最小安全末端越过移交边界；

车载设备向RBC 发送消息【ETCS-136】（位置报告）；

移交RBC 收到位置报告后，向车载设备发送包 含 信 息 包【ETCS-42】（Q_RBC=0）的 消 息【ETCS-24】；

（通信会话管理），断开与列车的通信；车载设备呼叫接收RBC 建立通信连接；

车载设备获得接收RBC 内的行车许可，以完全监控模式运行.

测试目的：RBC 应能处理单电台车载设备移交.测试前提：RBC 状态正常并且已被TSRS 初始化，单电台已完全监控模式在移交RBC 中运行.应用本文算法生成的测试序列包含了该规范中提到的所有步骤，证明了本文算法的正确性.令场景1的测试案例一/1 2 3 4 6/为a1，测试案例二/1 2 3 4 5/为a2；场景2 的测试案例一/8 9 11 13 15/为b1，场景2 的测试案例二/8 9 11 14 15/为b2，场景2 的测试案例三/8 10 12 14 15/为b3，场景2 的测试案例四/8 10 11 13 15/为b4；场景3 的测试案例一/16 17 20 21 23/为c1；场景4 的测试案例一/24 27 30 33 34/为d1，生成的测试序列见表3.

表3 生成的测试序列Tab.3 Generated test sequence

表4 将本文算法与传统蚁群算法（ACO）算法和序列优选算法（SPS）算法进行对比，由于SPS 算法与启发式算法不同，没有迭代次数的概念，因此这里只进行测试效果（测试利用率、测试时间和消耗内存）的对比，结果显示基于M-ACO 算法的测试序列优化方法生成的测试序列总数和测试项数相对较少，且其测试利用率（测试利用率为实际用到的测试项数占总测试项数的百分比）明显高于其他两种算法，在较短的时间内生成满足要求的测试序列，但消耗的内存反而更低，能够有效提高测试效率，减少冗余项.

表4 不同算法的结果对比Tab.4 Comparison of the results of different algorithms

4 结论

1）提出了一种基于M-ACO 算法的测试序列优化生成方法，首先对RBC 切换场景进行CPN 形式化建模，并采用ASK-CTL 逻辑公式对模型进行验证，之后生成该模型的状态空间可达图，应用路径搜索算法生成测试案例，各测试案例串联生成测试序列.

2）由于列控系统测试序列优化问题可以转换为一个TSP 问题，可以应用M-ACO 算法进行求解，直至找出最优序列，最终生成XML 格式的测试序列.

3）本文算法生成的测试案例与《CTCS-3 级列控系统测试案例》中与单电台RBC 切换相关的测试案例进行比较，结果证明应用本算法生成的测试序列都包含在规范中，验证了该算法的正确性和完备性，同时又将该算法和SPS 算法及ACO 算法相比，证明了该算法能够有效提高测试效率，简化测试步骤，实现测试过程自动化.