作者：江敏; 张毅
无线通信测试是整个无线通信工作中一个很重要的环节。
本文以蓝牙无线通信为例，用EFSM模型描述了其电话控制协议（TCS）。为了使测试例花费最小，本文采用了有效的算法生成最优邮路，在此基础上简要介绍了测试例的描述及执行。该项测试技术优化了测试路由，因而，提高了一致性测试的效率。
一、引言
无线通信测试是无线通信项目工作中的其中一个重要环节。测试的目的就是通过各种相关手段对通信系统的功能进行检测和校验，尽可能发现其中存在的问题，以便于在下一步工作中纠正错误，逐步完善系统功能。
在无线测试的过程中，一致性测试是测试工作中一项非常重要的测试内容。协议一致性测试在验证协议实现的正确性，以及保证不同厂商开发的设备互连互通方面有着重要的作用。一致性测试是一种黑盒测试，IUT（被测实现）的源码是未知的，测试者仅能控制和观察IUT的某些接口；一致性测试的基本方法就是通过观察协议规范和被测实现的输入输出来判定二者是否一致。根据协议规范生成一系列的测试例，并在测试系统上运行这些测试例，试图发现错误或者验证其正确性。
众所周知，手工测试生成花费的代价过于昂贵，冗长的重复性工作，相当于30%协议实现的时间，并且通常不能保证错误覆盖[1]。为此，本文采用了有效的算法生成最优测试路由，这样可以大大减少测试错误。同时，可以简化繁杂的测试工作，提高了一致性测试研究和实现的效率。不仅如此，其中所涉及的算法也有助于测试规程（或测试标准）的编写。该项测试集的生成技术可以应用于各种通信协议的一致性测试中。
二、引理
这样，就可以把TCS的EFSM状态用图1表示。
图1; EFSM状态图
三、测试序列算法
对于一致性测试而言，我们所关心的问题就是协议规范M与协议实现Mˊ是否一致。
;（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]DavidLeeandMihalis Yannakakis，Principles and Methods of Testing Finite State Machines[J]——A Survey，Proceedings of the IEEE，Vol.84 No.8，1996.8
[2]AlfredV.Aho，AntonT.Dahbura，DavidLee 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
