（通信与信息系统专业论文）基于通信的列车控制系统的协议一致性测试研究.pdf

论文题目：基于通信的列车控制系统的协议一致性测试研究 专 业：通信与信息系统 硕 士 生：尹建平 (签名) 指导教师：卢建军 (签名) 摘 要 基于通信的列车控制(communications based train control，cbtc)系统，通信协议 是整个系统安全的基础，也是各子系统间可靠地进行数据通信的保证。为了保证网络中 各实体间能够可靠、 正确地通信， 必须根据通信协议规范对协议进行一致性测试。 因此， 对cbtc系统通信协议的一致性测试成为协议测试的研究重点。 本文在研究cbtc系统通信协议的规范和相关文档的基础上，进一步研究了一致性 测试技术的不同理论方法， 结合cbtc系统通信协议的特点， 采用 e uio(extended unique input/output sequences)算法和扩展有限状态机(extended finite state machine，efsm) 的建模方法，对cbtc系统通信协议的一致性测试进行了研究。 本文介绍了cbtc系统通信协议的基本原理；根据cbtc系统通信协议的特点以及 efsm建模方法，建立了cbtc通信协议的efsm模型；分析了fsm与efsm模型一致性 测试的序列生成算法；根据通信协议的需求及特点，提出了基于 e uio算法和efsm模型 的cbtc通信协议测试序列的生成算法， 并生成了cbtc通信协议的一致性测试序列； 最 后， 按照生成的测试序列， 对cbtc系统通信协议的被测实现(implementation under test， iut)进行一致性测试，并对测试结果进行分析，一致性结果判决表明协议实现达到了协 议规范的需求。 关 键 词：列车控制系统；协议一致性测试；扩展有限状态机； e uio 研究类型：应用研究 subject ：protocol conformance test research of communication based train control system specialty ：communication and information system name ：yin jian-ping (signature) instructor：lu jian-jun (signature) abstract in the communication based train control (cbtc) system, communication protocol is not only the foundation of the whole systems safety, but also the guarantee of data communicate reliably between subsystems. to make sure that these devices in network can communicate with each others reliably and correctly, we must execute conformance test according to their specifications. therefore, conformance test of cbtc communication protocol has become the research focus of the communication protocol testing. in this paper, on the basis of research cbtc communication protocol specifications and standards, lots of conformance testing technologies and theories have been studied, the extended uniqueinput/output sequences ( e uio) algorithm and the extended finite state machine(efsm) model have been applied on the cbtc communication protocol according to its characteristic. in this paper, firstly, the basic principle of cbtc communication protocol were expatiated. secondly, the cbtc communication protocol model was built according to the characteristic of cbtc communication protocol and the method based on efsm, then, test sequence generating algorithm of fsm and efsm model have been described particularly, and a test sequence generating algorithm for cbtc communication protocol have been proposed based on e uio algorithm and efsm model. using e uio algorithm, cbtc communication protocol conformance test sequence has been generated. at last, a simulation platform has been established according to the conformance test sequence. through the analysis of the result, the conformance adjudgement has indicated that the implementation under test (iut) can meet the requirements of cbtc communication protocol specification keywords: train control system protocol conformance testing; efsm e uio thesis : application research 1 综述 1 1 综述 1.1 选题背景及意义 传统的列车运行控制系统是基于轨道电路的列车控制(track circuit based train control，tbtc)系统。tbtc 系统是基于轨道电路来检测列车位置，并向列车发送控制 信息，该系统技术成熟，安全可靠，但轨道电路难以实现列车对地面的信息传送，由于 轨道电路存在功能和性能上的限制和缺陷， 使得 tbtc 系统成为限制铁路运输效率提高 的瓶颈。因此，在列车运行速度、列车车辆性能、线路工程质量都得到较大提高的前提 下，改善列车运行控制系统成为提升整个铁路系统运输效率的关键。 为了改善轨道电路存在的缺陷，提高列车的运输效率和运行安全，许多研究者提出 了大量的控制理念和方法。cbtc 系统是利用列车和地面间的双向数据通信设备，使地 面信号设备可以得到每一辆列车连续的位置信息，并据此计算出每一辆列车的运行授 权，动态更新并发送到列车，列车根据接收到的运行授权和自身的运行状态，计算出列 车运行的速度曲线，实现列车的安全防护4。cbtc 系统独立于轨道电路，采用高精度 的列车定位和连续、高速、双向的数据通信，通过车载和地面安全设备实现对列车的控 制，现已成为列车控制系统发展的方向，可满足铁路运输智能化、信息化和网络化的发 展需要。相比传统的基于轨道电路的列车控制系统，cbtc 系统更有利于线路能力的充 分发挥，更有利于缩短列车运行间隔。 通信协议是通信网络中各通信实体之间相互交换信息所必须遵守的一组规则， 在通 信网络及系统的发展过程中，通信协议一直处于核心地位。cbtc 系统通信协议是整个 系统安全的基础，也是各子系统间可靠地进行数据通信的保证。为了保证网络中各实体 间能够正确、可靠地通信，必须根据协议规范对 cbtc 系统的通信协议进行测试。 协议的一致性测试是指对具体的协议实现与相应协议标准或规范的一致性关系进 行检验的过程，协议的一致性测试是保证协议实现正常工作的前提，也是各类协议测试 工作的基础。但是，通信协议多是以自然语言描述的文本，并且通信协议的实现者对 cbtc 系统通信协议文本的不同理解和可选的协议属性，以及实现过程中的非形式化因 素都可能会导致不同的协议实现，甚至会导致错误的协议实现。因此，对 cbtc 系统通 信协议进行一致性测试，具有非常重要的实际意义和价值。 1.2 国内外发展现状 国外研究 cbtc 系统的时间较早，技术发展也比较快，典型的 cbtc 系统有：美国 的先进列车控制系统(advanced train conrtol system，atcs)、欧洲列车控制系统 西安科技大学硕士学位论文 2 (european train contorl sysetm，etcs)、日本的 carat、德国的 lzb 等。 目前，欧洲铁路运输管理系统(ertms)为高速铁路定义了一批新的规范，传统的基 于轨道电路的信号系统被无线信号所代替， 列车由地面设备通过无线信号来传输移动授 权信息进行管理。 etcs第2级和第3级规定了以gsm-r(gsm for railways)数字无线通信 系统作为列车控制信息及其相关信息的传输平台。 目前的协议测试已经不仅仅是产品开发研制过程中一个简单的检测支持过程，而且 是发展成为计算机网络技术的一个重要分支和协议工程学的一个重要组成部分， 对协议 测试技术的研究将直接影响到计算机网络技术的进步和世界网络市场的竞争与发展5。 因此很多国家都投入了大量的人力物力从事协议测试的研究工作。例如：英国的国家物 理实验室、法国的国家通信研究中心、德国的国家通信研究局、美国的国家标准化研究 局、美国的新罕布什尔大学互操作研究实验室、清华大学计算机科学与技术系的网络和 协议测试实验室以及中科院计算所的网络测试实验室等单位都在这个领域投入了大量 的研究力量。 在上世纪80年代早期，欧洲的一些研究机构致力于一致性测试方法的研究和测试系 统的建立。早期的研究工作主要考虑测试的结构、测试的语言、几种测试方法以及测试 序列的产生等。1991年iso/iec推出iso9646系列标准是协议测试领域中的一个重大进 展，它描述了一个通用的方法论，用以测试一个声称实现了某一osi协议的产品与相应 的协议标准的一致性17。它的诞生是协议一致性测试领域内的重要里程碑。在二十多年 间里，通信协议的一致性测试取得了很大的进展，国际上对协议测试的研究领域逐渐达 成共识，通信协议的一致性测试过程主要包括协议形式化描述、测试序列生成、测试序 列执行以及结果分析几个基本过程，其中，形式化描述和测试序列的自动生成是通信协 议一致性测试研究的热点。 我国对cbtc系统的通信协议也在进一步的开发与研究中。 1.3 基于通信的列车控制系统 1.3.1 cbtc 系统的概述 ieee 将 cbtc 定义为：是一种连续的自动控制系统，装载了独立于轨道电路的高 精度的列车定位装置、 连续高容量双向车地数字通信系统以及车载与轨旁处理器， cbtc 系统是利用列车和地面间的双向数据通信设备， 使地面信号设备可以得到每一列车连续 的位置信息，并据此计算出每一列车的运行授权，动态更新并发送到列车，列车根据接 收到的运行授权和自身的运行状态，计算出列车运行的速度曲线，实现列车的安全防护 4。相比传统的铁路信号系统制式，cbtc 系统更有利于线路能力的充分发挥，可以让 列车运行获得更短的时间间隔。 1 综述 3 通常 cbtc 系统主要由车载设备、地面设备、通信网络组成，如图 1.1 所示。车载 设备主要由车载控制器(vehicle on board controller，vobc)、测速定位设备以及车载 天线等组成；地面设备主要由区域控制器(zone controller，zc)、计算机联锁(computer interlocking，ci)、列车自动监督(automatic train supervision，ats)、数据库存储单元 (database storage unit，dsu)等组成。 骨干网络 中心列车自 动监控ats 数据存储 单元dsu 相邻区域 控制器zc 道岔、信号机、屏蔽 门psd、紧急按钮、 防淹门、应答器等 计算机 联锁ci 区域控 制器zc ap 区域控制中心 ap. . . 车载mr 车载设备 车地信息传输网络 地面设备 车载mr 车载控制 器vobc ap 图1.1 cbtc系统组成框图 cbtc 系统从的特点可以总结为以下几点3： 1、信息传输流量大、效率高、速度快，容易实现移动自动闭塞系统； 2、车载设备及地面设备均采用安全计算机，实时处理列车状态、控制命令，实现 连续的间隔控制、进路控制、速度防护、自动驾驶等； 3、可以实现车辆与控制中心的双向通信，大幅度提高了列车区间通过能力； 4、容易适应各种车型、不同车速、不同运量、不同牵引方式的列车，兼容性强； 5、设备集成度高，可减少地面设备，系统结构简单，并改善可靠性和可维修性， 减少全寿命周期成本； 6、信息可以叠加在既有信号系统上，便于既有线改造，可实现城市轨道交通的互 连互通； 7、可以将信息分类传输，集中发送和集中处理，提高调度中心工作效率。 西安科技大学硕士学位论文 4 1.3.2 cbtc 车地通信系统 cbtc 车地通信系统主要由车载通信单元、轨旁有线和无线三部分组成的数据通信 系统，如图 1.2 所示。 控制中心 无线接入点 无线接入点 外部接口 防火墙 车载 802.1802.1 车载 轨旁计算机 轨旁计算机 802.3802.3 802.3 图 1.2 cbtc 车地通信系统 (1)车载通信单元 列车上的无线系统包括两个完全冗余的车载通信单元，它们是轨旁 ap 的通信客户 端，分别安装在车头和车尾的车载设备机架内。车载通信单元的两个无线单元之间协同 工作，每个无线单元都与两个一组的车载天线相连，提高了通信稳定性。 (2)轨旁有线网络 轨旁有线部分应用 ieee802.3 以太网标准，由骨干网和接入网两部分组成。 轨旁无线接入点 ap 跟列车之间进行双向通信， 并通过多模光纤与接入交换机相连， 组成接入网。轨旁无线接入点 ap 包括一个或两个完全冗余的无线单元，并协同工作， 每个无线接入点 ap 通过光纤以太网，分别连接到相应的接入交换机，每个接入交换机 直接与其所属的骨干交换机连接，从而接入到骨干网。 (3)无线网络 无线网络主要由标准的无线局域网部件组成，应用 wlan 技术，遵循 ieee802.11 无线局域网标准。在实际应用中，利用 ap 的无线重叠覆盖和冗余的车载无线设备，可 以满足系统可靠性和安全性的要求。 1.3.3 cbtc 的通信协议 通信协议是通信网络中各种通信实体之间相互交换信息所必须遵守的一组规则， 在 通信网络及系统的发展过程中，通信协议一直处于核心地位。 1 综述 5 cbtc 系统最显著的特点是引入通信子系统，建立车地之间连续、双向、高速的通 信， 使 cbtc 系统地面设备和受控对象列车紧密地联结在一起， 因此， “车地通信系统” 是 cbtc 系统的基础，是整个系统的支柱之一，也是关键技术之一。可见，在这样一个 基于无线数据通信的列车运行控制系统中， 安全的地车通信协议是保证 cbtc 系统安全 的重要组成部分，在整个系统中有着至关重要的作用。 当前我国的(chinese train contorl sysetm，ctcs)技术标准正在制定过程中，对于 协议方面的规范还不太成熟。因此吸收和借鉴国外先进的技术，对我国 ctcs 的发展是 很重要的。 1.4 协议的一致性测试技术 1.4.1 协议的测试 (1)协议测试的概述 协议测试是协议工程学的一个重要分支， 是从软件测试的基础上发展而来的一种黑 盒功能测试，它依据协议的描述，对协议实现的外部可观察行为进行测试，而不涉及协 议实现的内部结构17。 协议的测试是通过实验对被测协议实现(iut)的行为特性进行测量，试图通过实验 找出系统错误的过程。在实际中，对一个系统进行无穷尽的测试是不现实的，所以测试 不能保证协议实现的完全正确性，即测试只能表明“错误存在，并不能证明“错误不 存在，这是协议测试的基本出发点。 协议二义性和模糊性问题的解决，以及在协议实现中潜在问题的发现，一方面，要 依靠协议验证和形式化描述技术的发展，另一方面，要依靠一致性、互操作性以及性能 测试等各种协议测试技术的完善。随着异构网络的迅猛发展，对协议测试理论和技术的 研究越来越重要，己成为国际上网络研究的热点之一。 (2)协议测试内容 协议测试主要研究内容包括测试组织、测试方法、测试生成、测试表示、测试管理、 测试执行和判决及测试结果分析等多个方面17： 测试组织是针对整个协议测试过程进行框架性的研究，明确测试过程中各个阶段 所应完成的功能； 测试方法是研究在被测系统提供不同的可访问程度时，组成测试系统的多个测试 器相对于被测系统的配置方法； 测试生成是从协议标准的描述中获得进行协议测试所需要的测试用例； 测试表示是通过寻找一种合适的语言或公式，以简洁、通用和结构化的方式来表 达协议测试所需要的测试用例； 西安科技大学硕士学位论文 6 测试管理是管理好由众多测试用例组成的庞大测试集，并依据实际被测系统的信 息对测试集进行选择； 测试执行和判决是测试过程中的重要阶段，解释测试用例的涵义以及如何作出测 试判决是它的研究内容，同时也是构造测试系统的理论基础； 测试结果分析是协议测试过程的最后一个阶段，这一阶段的研究目标是从测试结 果中生成测试报告并得出对被测协议实现的结论。 (3)协议测试分类 协议测试主要有三种12：一致性测试、互操作性测试和性能测试。 协议标准规定了协议实现所应具有的特定行为， 协议的一致性测试是指对具体的协 议实现与相应协议标准或规范的一致性关系进行检验的过程， 协议的一致性测试是保证 协议实现正常工作的前提，也是各类协议测试工作的基础。 单纯对一个协议实现进行协议的一致性测试， 并不能保证不同协议实现之间通信的 成功，还需要把协议实现放到一个实际的通信网络环境中进行测试。在这种测试中，要 检测一个协议实现与其它系统之间是否能够进行成功可靠的通信， 称为协议的互操作性 测试。 性能测试是通过自动化的测试工具，模拟多种正常、峰值以及异常负载条件来对系 统的各项性能指标进行测试，如吞吐量、响应时间、传输延迟等，并以此对系统的性能 做出评价。负载测试和压力测试都属于性能测试，两者可以结合进行。 一致性测试和互操作性测试都是黑盒测试， 而性能测试的目的是测试协议实现的各 项性能指标，并根据这些性能指标对协议实现的性能做出评价；一致性测试和性能测试 的测试对象都是一个协议实现，而互操作性测试的测试对象则是多个协议实现。 同样，三种测试之间是有联系的，一致性测试是互操作性测试和性能测试的基础， 只有协议实现满足了一致性测试的需求， 然后对它进行互操作性测试和性能测试才更有 意义；性能测试的结果对互操作性测试也有影响，只有性能匹配的协议实现之间才能更 好地进行互操作测试。 1.4.2 一致性测试 协议一致性测试的目的在于验证协议实现与相应的协议标准的一致性， 它只关心协 议实现呈现在外部的性能。协议的一致性测试作为各项协议测试工作的前提和基础，是 协议测试领域研究的重点。 协议的一致性测试过程主要分为四步：测试生成、测试实现、测试执行、测试判决， 如图1.3所示。 1 综述 7 协 议 标 准 测 试 执 行 测 试 判 决 协 议 实 现 抽 象 测 试 集 可 执 行测 试 集 实 现 过 程 测 试 过 程 一 致 性 判 定 图1.3 协议的一致性测试过程 测试生成： 从协议标准产生抽象测试集， 抽象测试集是独立于所有的协议实现的， 抽象测试集由多个用于不同测试目的的测试序列构成。 测试实现：由抽象测试集产生可执行的测试序列集，抽象测试集中的抽象测试序 列被转变为在一个实际的测试设备或测试系统上可执行的测试用例， 在转变为可执行测 试用例的过程中需要考虑测试环境与被测协议实现的具体情况。 测试执行：将可执行的测试序列集施加到被测网络协议上，并对iut的外部响应 行为进行观察，记录各条测试序列的执行结果。 测试判决：对测试执行的生成的结果进行验证和分析，得到一个有关iut相对于 协议标准一致性的判决，并给出协议一致性测试报告。 协议的一致性测试首先需要根据协议规范建立协议模型，然后根据协议模型，生成 相应的测试序列集，针对于具体的协议实现，选择合适的测试方法，将生成的测试序列 集转化为可执行的测试用例，最后将测试用例应用到被测协议实现上，观察激励反映， 得到验证结果。 1.5 本文结构安排 本文共分为六个章节。 第一章：综述。介绍了选题背景及研究意义、国内外发展现状、cbtc系统和协议 的一致性测试技术的发展。 第二章：cbtc系统通信协议的基本原理。从通信协议的角色定义、状态管理、建 立通信链路、结束通信过程等方面描述了通信协议的基本原理。 西安科技大学硕士学位论文 8 第三章：cbtc系统通信协议建模。介绍了状态机的一些基本概念、原理和特点， 建立了基于efsm的cbtc系统通信协议模型，包括发起方和跟随方的模型。 第四章：一致性测试序列的生成。介绍了两种常用的测试序列生成算法，分析了基 于 e uio的方法生成一致性测试序列的优点， 并采用 e uio算法生成了cbtc通信协议发起 方和跟随方的测试序列。 第五章： 测试与分析。 结合测试的实际情况， 搭建了一致性测试平台， 对生成的 e uio 测试序列进行测试，并对结果进行了分析，证明cbtc通信协议的实现与协议规范中的 要求相符合。 第六章：总结与展望。总结课题中主要研究成果，并且对需要进一步研究的工作行 了展望。 2 cbtc 通信协议的基本原理 9 2 cbtc 通信协议的基本原理 2.1 协议的安全防护 通信协议的安全防护措施， 是安全通信协议中最重要的部分， 在开放式传输的cbtc 系统中，可能会出现的报文错误主要包括报文的重复、丢失、乱序、插入、伪装、损坏 和延迟。 为了减少安全隐患， 最基本的安全防护措施就是要保证消息的实时性、 有序性、 真实性和完整性，并且针对不同的危险因素采取相应的措施进行安全防护。 下面就对这些安全防护措施进行简要说明。 (1)时间戳与序列号 时间戳是针对信息延时这一危险进行防护的， 一个实体接收到的信息的内容往往是 与时间相关的，不同用途的数据和时间的独立性是不一样的，在一般情况下，过时的数 据可能是无用的，甚至是有害的，可能会对用户构成潜在危险，因此，解决时间与信息 关系的方法就是在信息中加入时间戳。 序列号是针对信息的乱序这一危险行为进行防护的，它由一些连续的号码组成，加 入到发送端与接收端交换的每个消息中， 这样接收端可以检查发送端提供的消息的顺序 是否合法。 cbtc系统的时间精度并不要求很高，因此，各子系统可以用其运行周期作为时间 单位(百毫秒)，并且信息交换也是按照系统周期进行的，规范中将时间戳与序列号结合 使用， 使系统每运行一个周期后将序列号自增l， 这样不仅序列号的大小也可以体现信息 的时间特性，而且序列号的顺序可以体现信息的连续性，达到了超时和防护信息乱序的 双重作用。 (2)编码 在开放式传输系统中， 传输编码用于检测突发错误， 通过纠错技术提高传输的质量。 如循环冗余校验码校验(crc)，crc校验通常应用在硬件设备或是低层的通信协议。但 从安全的角度来讲，安全的相关进程不应该相信底层的传输编码，因此在安全相关数据 组帧时需要加入软件的crc校验。 (3)源标识与目的标识 cbtc系统的通信协议是个多端的通信过程，在使用接收到的信息之前，需要使用 合适的方法来检查信息的来源，对系统中每一个设备来讲，都定义了表示其身份的唯一 的标识信息，信息在传输的过程中包含一个唯一的源标识和唯一的目的标识，用户可以 根据消息中所包含的源标识确定消息是从预定的消息源发送的， 不需要与对方进行任何 对话。 西安科技大学硕士学位论文 10 (4)超时 在信息的周期性传输中， 接收信息时会检查两个消息之间的时间间隔是否超过事先 预订的最大时间， 若超过， 则认为信息的时效性没有得到保证， 就可能对系统产生危害。 通信的发送端在发送消息i的时候会启动计时器， 接收端收到消息i后会回应一个消 息i的确认消息j，如果发送端在预定时间内没有收到确认消息j，则认为出现错误。 cbtc系统通信协议安全传输系统采用上述安全防护措施，在一定程度上对系统起 到了安全防护作用，从而提高了系统的安全性，但系统安全性的提高往往是以系统可用 性降低为代价的，为了提高系统的可用性，整个cbtc系统的各子系统之间都通过冗余 的双网连接，这种双网冗余结构为协议提供一定可用性保障，同时，协议也对冗余双网 结构带来的重复信息进行了处理，以保证在应用处理时数据的唯一性。 2.2 协议的角色定义 在 cbtc 通信协议中，由于应用层的需求与技术规范的规定，通信的双方分为发起 方和跟随方，两个子系统之间的通信，首先都是由发起方向跟随方发送请求建链报文 rfc，跟随方没有权限请求发起链路并建立通信连接，这样就可以避免子系统间通信混 乱的情况。在 cbtc 系统中，每个子系统的角色是预先定义好的，如：车载 vobc 和 区域控制器 zc 之间进行信息交换，对于通信协议来说，车载 vobc 为发起方，区域控 制器 zc 为跟随方，由于 cbtc 系统中大容量的车地信息是通过无线来传输的，在整个 cbtc 系统通电之后，车载 vobc 需要与地面设备通信，那么此时车载 vobc 发送应 用信息，向区域控制器 zc 发送请求建链报文 rfc，在链路建立成功后，双方正常交换 数据，区域控制器 zc 不能主动向车载 vobc 请求建链。 总之， 用一句话来概括就是： 一条通信链路的双方不能同时既是发起方又是跟随方。 由上文的说明可以看出，通信的发起方和跟随方的状态管理、链路建立过程、链路 删除过程，都是不相同的，存在很大的区别，这就需要两种角色分别讨论，因此，在后 面对于 cbtc 通信协议的 efsm 建模， 以及一致性测试序列的生成算法都是将两种角色 分开来讨论的。 2.3 协议的状态管理 通信协议是由若干个事件驱动的实体组成的，这些实体间通过消息传送可以进行 相互通信，并且每个实体的特性可以描述成一系列响应外部和内部事件的动作。 在 cbtc 系统通信协议中，每条通信链路都是点对点的通信，都存在通信的发起 方与通信的跟随方这两种角色。虽然整个 cbtc 系统中有很多不同的平台和设备，但是 在通信协议中只划分为通信的发起方和通信的跟随方两类，与平台无关，下面都是将通 信的发起方与通信的跟随方分开讨论的。 2 cbtc 通信协议的基本原理 11 (1)状态：通信发起方与通信跟随方的状态定义分别如下表所示： 表表 2.1 发起方状态定义发起方状态定义 状态名称 描述 idle 默认的初始状态 wait 等待跟随方的连接确认 data 应用数据交换阶段 halt 通信中断状态 表表 2.2 跟随方跟随方状态定义状态定义 状态名称 描述 idle 默认的初始状态 data 应用数据交换阶段 halt 通信中断状态 (2)事件：事件是引起状态变迁的触发，通信的发送方与通信的跟随方相同。 表表 2.3 事件事件的的定义定义 事件 描述 rcv_data 收到应用数据 rcv_rfc 收到请求建链报文 rcv_ack 收到确认连接应答 rcv_ discon 收到删除链路命令 timeout_ack 接收 ack 的时间超时 timeout_data 接收 data 的时间超时 timeout_max 接收 data 的时间超过最大超时时间 (3)活动：活动是状态变迁发生后的动作，通信的发送方与通信的跟随方相同。 表表 2.4 活动活动的的定义定义 活动编描述 a_1 无操作 a_2 发送连接请求报文，并启动定时器 timeout_ack a_3 发送连接确认报文 a_4 发送数据报文 a_5 删除该连接的相关内容 a_6 重启接受超时 timeout_data 西安科技大学硕士学位论文 12 根据前面的状态的定义、事件的定义和活动的定义，从通信的发起方和通信的跟 随方可以描述出完整的 cbtc 系统通信协议的状态转换。 (4)状态转换表 a)通信发起方的状态转换表 表表 2.5 通信发起方通信发起方的的状态转换表状态转换表 活动 下一个状态 状态 idle wait data halt 事 件 rcv_data a_2 wait a_1 a_4 data a_2 wait rcv_rfc a_1 a_1 a_1 a_1 rcv_ack a_1 a_4 data a_1 a_1 rcv_ discon a_1 a_5 idle a_5 idle a_5 idle timeout_ack a_1 a_2 wait a_1 a_1 timeout_data a_1 a_1 a_1 halt a_1 timeout_max a_1 a_1 a_1 halt a_2 wait b)通信跟随方的状态转换表 表表 2.6 通信跟随方通信跟随方的的状态转换表状态转换表 活动 下一个状态 状态 idle data halt 事 件 rcv_data a_1 a_4 data a_4 wait rcv_rfc a_3 data a_1 a_3 data rcv_ack a_1 a_1 a_1 rcv_ discon a_1 a_5 idle a_5 idle 2 cbtc 通信协议的基本原理 13 表表 2.6(续续) 通信跟随方通信跟随方的的状态转换表状态转换表 活动 下一个状态 状态 idle data halt 事 件 timeout_ack a_1 a_1 a_1 timeout_data a_1 a_1 halt a_1 timeout_max a_1 a_1 halt a_5 idle 对整个 cbtc 系统通信协议来说，系统完成的就是以上这样的状态转换，对于不 同的设备或不同的平台，只是预先规定好通信链路的角色，即通信的发起方或是通信的 跟随方， 而对该设备的平台或应用来说， 完成的功能和协议的处理是一致的， 也就是说， 协议行为只跟其通信链路的角色有关，而与设备类型及平台无关。 2.4 协议的运行周期 在 cbtc 系统中，各子系统都是运行在自己支撑平台之上的，也就是说，应用层相 对于安全平台来说，只是软件调用而已。 根据列车和地面各设备之间进行数据交换的时间和容量、无线通信信道的情况、各 应用子系统处理数据的时间需求等，又由于 cbtc 系统的时间精度并不要求很高，因此 各子系统可以用其运行周期作为时间单位(百毫秒)， 而且信息交换是按照系统周期进行 的。目前，cbtc 系统中各子系统的运行周期都定为 200ms，也就是说，通信协议的运 行周期为 200ms。每个周期协议完成一次数据的接收、处理、发送、链路管理等工作。 在后面还将讨论到，由于通信协议周期的固定性，可以将一些时间问题转化为周期 问题，即用周期来代替时间。由于 cbtc 系统通信协议都是运行在子系统各自的平台上 的，而周期的控制又是由平台来处理，这样协议中只需要进行周期的相关计算即可。 2.5 链路的建立过程 通信协议对于应用层来说是透明的，也就是说，应用不会关心通信是否正常，链路 是否存在，如果要跟其它设备进行数据交换，应用它只需要把将要进行交换的数据按照 一定的格式转交给协议，至于应用层与对方设备之间是否存在链路，能否将数据发送出 去，应用都是不参与的。应用跟协议之间只存在一个接口，应用发送数据之前，只需要 填写加上目的标识即可。 西安科技大学硕士学位论文 14 发送rfc报文 发送应用数据data 回复ack报文 itimeout . . . 发送方 接收方 再次收到应用数据 收到应用数据 发送应用数据 t1时刻 启动计时器 t2时刻 图3.5 通信链路保持阶段超时 3.4 建立通信协议模型 由第2章可知， cbtc通信协议是分为通信发起方和通信跟随方两种不同的角色来表 述的，所以下边分开来讨论两种角色的efsm模型。 (1)通信发起方 在建模之前，先做如下定义：协议的输入及输出部分：data为应用数据、rfc为 建链命令、ack为连接确认报文、discon为链路删除命令。 wait condhalt idle t5 t8 t3t2 t7 t12 t6 t11 t10 t4t1 t9 图3.6 发起方efsm模型 西安科技大学硕士学位论文 24 1 ? !(,) () 0 ack ack data t rfc x p random x p 5 ?( ) !(, ) 1 0 ack y yx t data x p xx p 9 ? ! di s c on t 2 ? ,4 ! ,1 ack ackack p t pp 6 ?(,) 5 !(,) 1 0 d a t a y p p t d a t a x p xx p 10 ? ! discon t 3 ?,4 !(,) () 0 ack ack ack p t rfc x p random x p 7 ? ,5 !() 1 p t data x xx 11 ? , !1 pmax t pp 4 ? ! discon t 8 ? , ! pmax t 12 ? ,5 !(, ) 1 0 p t data x p xx p , , ack vpp x y为上下文变量集，其中： ack p表示等待跟随方回复ack报文的周 期数，p表示没有收到对方发来数据的周期数，x表示本方的序列号，y表示对方的序 列号，且 ack p、x，y均为整形变量，0,0,4 ack pmaxp，max表示允许没收到 数据的最大周期数。 通信发起方状态集s=idlewaitcondhalt，有四种状态：idle状态， 表示默认的链路初始状态；wait状态，表示等待跟随方的连接确认，也就是说，通信 发起方发送rfc报文后，等待跟随方回复ack时的状态；cond状态，表示应用数据交 换阶段，此状态是正常通信情况下的链路维持状态；halt状态，表示通信中断状态。 idle状态在模型中用双实线圈来表示，状态wait、cond、halt在模型中用单实线圈 来表示。 模型中的状态变迁集为 1212 ,.,tt tt。 由图14可以看到，前文所提到的正常建链、非正常建链、正常删除链路、超时保护 等在状态转换过程中都有明确的模型描述。 (2)通信跟随方 协议的输入及输出部分：data为应用数据、rfc为建链命令、ack为连接确认报 文、discon为删除链路命令。 3 建立 cbtc 通信协议模型 25 idle cond halt t7 t8 t2t3 t9 t5 t4t6 t1 图3.7 跟随方efsm模型 1 ? !(, ) () 0 rfc t ack x p random x p 4 ?,5 !() 1 p t d a t a x xx 7 ? ! discon t 2 ?( , ) 5 !(, ) 1 0 data y p p t data x p xx p 5 ?( , ) 5 !(, ) 1 0 data y p p t data x p xx p 8 ? , ! ,1 pmax t pp 3 ? ,5 !( ,) 1 1 p t data p x pp xx 6 ? ! discon t 9 ? , ! pmax t , vp x y是上下文变量集， 其中：p表示没有收到对方发来数据的周期数，x表 示本方序列号，y代表对方序列号。p、x、y均为整形变量，0,pmax，max为 允许没有收到数据的最大周期数。 通信跟随方状态集sidlecondhalt，有三种状态：idle状态，表示连 默认的链路初始状态；cond状态，表示应用数据交换阶段，此状态是正常通信情况下 的链路维持状态；halt状态，表示通信中断状态。idle状态在模型中用双实线圈来表 示，状态cond、halt在模型中用单实线圈来表示。 模型中的状态变迁集为 129 ,.,tt tt。 通信跟随方的状态模型与发起方模型比起来，没有wait状态，因为是在协议规范 中，通信跟随方发送连接确认报文ack后，就认为链路已经建立成功，所以通信跟随方 西安科技大学硕士学位论文 26 只需要用三个状态即可表示整个链路的情况。 由图15可以看到，前文所提到的正常建链、非正常建链、正常删除链路、非正常删 除链路、超时保护等在状态转换过程中都有明确的模型描述。 3.5 本章小结 本章根据cbtc系统通信协议的需求，把通信分为通信发起方和通信跟随方两个部 分；简单介绍了fsm和efsm的一些基本概念、原理和特点；最后，基于efsm建立了 cbtc系统通信协议的模型，包括通信发起方和通信跟随方的模型。 4 一致性测试序列的生成 27 4 一致性测试序列的生成 4.1 常用测试序列生成方法 测试序列的生成是协议一致性测试的基础，得到测试序列后，就可以根据具体的测 试方法，对测试序列进行实例化，从而实现测试执行和测试判决。 4.1.1 fsm 测试序列生成方法 对于协议测试来说，最佳的测试序列应满足下列条件20：(1)在测试序列路径最大 覆盖率的条件下，使测试序列最短。(2)不同的输入测试序列，其输出序列不同。 常见的基于 fsm 的测试序列生成方法主要有以下几种。 1、t 方法(transition tour method) 周游法。t 方法的基本思想是，假定一个有限状态机是强连通的，使测试输入序列 对应于 fsm 的状态迁移随机地产生，直至所有的状态迁移都被覆盖为止。该方法的优 点是算法简单，生成的测试序列长度也较短；该方法的缺点是测试输入序列中存在大量 的冗余，另外，该方法检错能力也较差，它只能检测转换是否存在，不能断定其转换后 的状态是否正确。 2、d 方法(distinguishing sequences) 区分序列法。d方法指的是应用区分序列(distinguishing sequence ，ds)的形式化测试 序列生成方法。ds序列是一个对iut的所有状态来说都相同的输入事件序列，即 ( )() ij ds sds s，,( ) ij s sv g。但是，在相同的ds序列下，iut各个状态的输出事件序 列并不相同。该方法的优点在于生成的测试序列错误检测能力强，能够比较全面地检测 出输出和转换错误；该方法的缺点在于生成的测试序列较长。在许多实际的协议fsm中 并不存在ds序列，因此，在这种情况下，d方法就无法采用了。 3、w 方法(charactering sequences) 特征序列法。w 方法是 d 方法的进一步扩展，用特征序列集 w 代替 ds 序列。对 有限状态机来说，w 序列总是存在的，因而 w 方法的优点具有良好的通用性；但是， 该方法的缺点也比较明显：该方法生成测试序列的整个过程冗长复杂，极大地妨碍了该 方法在实际中的应用。 4、u 方法(unique input/output sequences) 唯一输入输出序列法。u 方法的基本思想是采用唯一输入输出序列(unique input/outputse quences，uio)进行状态转换与末状态检测。d 方法和 w 方法对所有状态 都采用相同序列或序列集进行状态判定，而 u 方法则是用与各自状态相对应的 uio 序 西安科技大学硕士学位论文 28 列来进行状态判定。u 方法所得到的测试序列长度是后三种方法中最短的，而且该方法 的错误检测能力比较强，几乎可以适用于所有的有限状态机，因此，u 方法是基于 fsm 测试序列生成的最常用的方法，在实际的协议测试中，被大量采用。 5、其他方法 除了上面几种基本的测试序列生成算法之外，用于生成 fsm 模型一致性测试序列 的方法还有 suio、muio、ff、sw 等算法。 4.1.2 efsm 测试序列生成方法 由上节知道，目前基于fsm模型的状态验证序列生成已有相对成熟的方法，并且这 些方法对测试序列长度的优化、应用方面的扩展等问题也有比较深入的研究。 fsm模型不能描述通信协议的数据流部分， 而efsm模型允许出现数据变量和谓词， 因此基于efsm的模型既可以进行数据的流测试，也可以进行控制流的测试。由于变量 和谓词的存在，会导致