相关专题：
一、引言
无线通信测试是无线通信项目工作中的其中一个重要环节。测试的目的就是通过各种相关手段对通信系统的功能进行检测和校验，尽可能发现其中存在的问题，以便于在下一步工作中纠正错误，逐步完善系统功能。
在无线测试的过程中，一致性测试是测试工作中一项非常重要的测试内容。协议一致性测试在验证协议实现的正确性，以及保证不同厂商开发的设备互连互通方面有着重要的作用。一致性测试是一种黑盒测试，IUT（被测实现）的源码是未知的，测试者仅能控制和观察IUT的某些接口；一致性测试的基本方法就是通过观察协议规范和被测实现的输入输出来判断二者是否一致。根据协议规范生成一系列的测试例，并在测试系统上运行这些测试例，试图发现错误或者验证其正确性。
众所周知，手工测试生成花费的代价过于昂贵，冗长的重复性工作，相当于30%协议实现的时间，并且通常不能保证错误覆盖[1]。为此，本文采用了有效的算法生成最优测试路由，这样可以大大减少测试错误。同时，可以简化繁杂的测试工作，提高了一致性测试研究和实现的效率。不仅如此，其中所涉及的算法也有助于测试规程（或测试标准）的编写。该项测试集的生成技术可以应用于各种通信协议的一致性测试中。
二、引理
在此，以蓝牙协议中电话控制协议TCS为例，研究其信令测试集的生成技术。该协议（包括控制和数据）可以用一个EFSM（扩展有限状态机）[1]模型来描述，具体描述如下：M=（I，O，S，
，T，），其中，I表示输入的信令消息集，O表示输出的信令消息集，S为状态集，为协议所包含变量集，T为变迁集，且，
，t=（st，qt，at，ot，Pt，At）其中st，qt，at和ot分别表示当前状态，下一个状态，输入和输出。Pt（）表示当前协议变量对应的断言，At（）表示当前协议变量对应的动作。 对于一个给定的EFSM，把每一个状态S和与之有关的协议变量值
当成一个配置（Con-figuration）节点。我们所关心的就是初始配置到其他配置的转换。因此，可以用如下一个连通的有向图来描述EFSM： G=
当作一个配置来考察，所以，E的描述为
其中
为当前配置节点，为变迁的下一个配置节点。W为变迁所对应的费用权值（与变迁的时间有关），用来
表示。 这样，就可以把TCS的EFSM状态用图1表示。
三、测试序列算法
对于一致性测试而言，我们所关心的问题就是协议规范M与协议实现Mˊ是否一致。
（1）验证单个变迁：
，对于处于状态Si的Mˊ输入ai，检查输出oi与协议规范M所描述oi是否一致，并验证Mˊ变迁后是否转移到sj； （2）验证所有变迁：Mˊ检查中所有的变迁及状态，完成整个协议机Mˊ的测试。
基本假设：协议描述（状态机）是输入完全的、确定的、最小化的和强联通的。协议描述最小化即是要求协议中没有冗余的配置（或状态）。一个协议状态机复位后进入一个初始配置，如TCS协议EFSM在蓝牙终端开机后进入空闲模式
。到任何其他配置都是可达的，而其他配置到一般来说也是可达的。若
到不可达，则可增加一个变迁（，；rj/null），其中rj是使配置复位到初始配置的操作，且输出为空。这样协议机就变成强联通的了，即说明了假设的合理性。 测试序列算法如下：
（1）验证单个变迁的算法：设欲验证的变迁为
第1步：生成一个到
的Homing序列（用Dijkstra最短路算法[3]），使EFSM从初始配置变迁到第2步：输入ai，检查输出是否与oi一致；
第3步：输入
的UIO序列，检查对应的输出序列，判断EFSM变迁后的配置是否为（2）验证所有变迁的算法[2] 对于EFSM的描述图G而言，根据基本假设可知，生成图G的一条有向邮路，就可以验证协议机的所有变迁及配置。因为G是最小的，没有等价的配置节点，所以，回路的输入序列可以作为各个状态的UIO序列。这样根据中国邮递员问题[4]的求解方法得到下列最优邮路的算法：
第1步：对于
，其中d-为入度，d+为出度。若所有的σi=0，则欧拉图G*=G，转第2步；否则转第3步； 第2步：生成的G*一条欧拉闭迹；
第3步：令
，用Floyd算法求出G的最短（，）路。S中的任意节点重复σi个，T中的任意节点重复σj个，进而构造S与T的赋权完全二部图D； 第4步：求出D中的最小权完美匹配H（用原始-对偶算法）；
第5步：找出H中对应的每条边在G中的最短（
，）路，把这些路上的边都添加到G上，得到欧拉图G*，转第2步。 求解有向邮路的算法还有线性规划和网络流算法等。
四、测试集的生成
测试序列是生成测试例的前提和基础。在经过上述算法得出测试序列之后，接下来进入测试例的生成阶段。测试例的生成一般可分为两类：一是“无遗漏”的测试例生成，输入EFSM，产生测试例（并不是真正的无遗漏覆盖，错误的覆盖率大于某一值），自动化程度高；二是基于测试目的的测试例自动生成，输入EFSM和形式化的测试目的，输出测试例，需要人工干预。测试集生成技术中另一个关键的部分是测试集的描述及实现，目前比较好的方法是TTCN（树表结合符号）来描述测试例。TFCN可用于所有实时系统各种通信端口上的测试规范，特别是通信协议的一致性测试描述。虽然TTCN有很多优点，但是实现TTCN编译器是一个相当浩大的工程。
在选择好测试例生成技术之后，可通过设计简单的测试语言编译器，并结合相关的开发工具（如：C、C+ +、Java等），完成对测试集的描述及实现。
五、结束语
在无线测试的过程中，一致性测试是测试工作中一项非常重要的测试内容。为了避免传统的手工测试花费代价过高、工作重复性大等弊端，本文采用了有效的算法生成最优测试路由，减少了测试错误。同时，简化了繁杂的工作，提高了一致性测试研究和实现的效率。该项测试集的生成技术可以应用于各种通信协议的一致性测试中。
参考文献
[1] David Lee and Mihalis Yannakakis，Principles and Methods of Testing Finite State Machines[J]——A Survey，Proceedings of the IEEE，Vol.84 No.8，1996.8
[2] Alfred V.Aho，Anton T.Dahbura，David Lee and M.Umit Uyar，An Optimization Technique for Protocol Conformance Test Generation Based on UIO Sequences and Rural Chinese Postman Tours[J]，IEEE Transactions on communications，Vol.39 No.11，1991.11
[3] 谢政，李建平.网络算法与复杂性理论[M]，长沙：国防科大出版社，1995
[4] 卢开澄，卢华明.图论及其应用（第2版）[M]，北京：清华大学出版社，2005.1
