刘层层　杨红丽

摘 要：在对无线传感器网络数据收集协议进行一致性测试时，生成的测试序列往往不够简捷高效。因此，提出了基于FSM模型的无线传感器网络数据收集协议测试方法。采用FSM模型描述数据收集协议规范，在FSM模型的基础上利用UIO算法生成测试序列。研究发现：UIO算法生成的测试序列较长，现有基于UIO的改进算法生成的测试序列较短，但不适用于所有协议，为此进行了优化，使得优化后的算法具有更好的适用性。为了阐明方法的有效性，对一个工业界无线抄表数据收集协议WM2RP进行建模与测试序列生成，并搭建测试环境进行了实际测试。

关键词：无线传感器网络；数据收集协议；FSM模型；测试序列生成；UIO算法

DOI：10.11907/rjdk.171437

中图分类号：TP306 文献标识码：A 文章编号：1672-7800（2017）009-0014-05

Abstract：In the conformance testing of data gathering protocol for Wireless Sensor Network， the test sequences generated is often not simple and efficient. So a testing method of data gathering protocol for WSN based on FSM model was proposed. We used the FSM model to describe the data gathering protocol specification， based on the FSM model， UIO algorithm was used to generate the test sequence. It was found that the test sequence generated by UIO algorithm was long. The improved UIO-based algorithm generated a shorter test sequence but did not apply to all protocols. Then， the algorithm was optimized on the basis of the existing improved algorithm， so that the optimized algorithm had better applicability. The effectiveness of the method was proved by modeling and test sequences generating for a wireless meter reading data gathering protocol in industry. Besides， the test environment for the actual test was built.

Key Words：wireless sensor network； data gathering protocol； FSM model； test sequence generation； UIO algorithm

0 引言

無线传感器网络广泛应用于各个领域的数据收集系统，设计并实现可靠的数据收集协议以保证此类系统的正常运作成为亟待解决的问题之一[1]。协议测试是检验协议可靠性与正确性的一种有效方式，主要包括一致性测试、互操作性测试、可靠性测试、健壮性测试。其中一致性测试是协议测试的基础，作用是检测协议的实现是否符合协议规范。测试序列是一致性测试中的核心部分，好的测试序列可以增加准确性，提高一致性测试效率[2]。如何生成合适的测试序列，是一致性测试中需要解决的关键问题。测试序列可以从协议模型中得到，常见的协议抽象模型主要有Petri网、进程代数、有限状态机等。其中应用最广泛的是有限状态机FSM模型[3]，很多测试序列的生成算法都在其基础上进行处理的[4，5]。

基于FSM模型的测试序列生成方法有很多，应用最广泛的是UIO方法[6，7]。目前基于UIO的测试序列生成方法已有很多研究成果[8-10]。虽然UIO方法已经被应用于一致性测试序列的生成[11，12]，然而，相关研究工作仍处于理论探讨阶段，在工业界还未得到广泛应用。

本文研究UIO方法在企业真实数据收集协议测试中的应用，对文献[10]中基于UIO的改进算法进行优化，使得优化后的算法具有更好的适用性。

1 WM2RP数据收集协议概述

WM2RP数据收集协议已被成功应用于无线抄表系统，用于小区居民燃气表数据的采集。使用WM2RP协议的小区抄表系统体系结构见图1，协议中节点分为四类。

（1）服务器。服务器通常部署在燃气公司，作为远程管理中心，通过GPRS方式与集中器通信，收集集中器发送的数据。由于它与集中器的通信不属于WSNs路由协议范畴，因此本文不将其作为研究内容。

（2）集中器。集中器也称为基站，一个小区只有一个，采集整个小区的数据，并且将数据通过GPRS传输给远程服务器。

（3）中继器。表节点的无线传播范围有限，如果表节点与集中器的距离超过了表节点的传播距离，就需要中继器辅助传递信号到集中器。中继器与表节点相同，但是中继器只有路由的功能，其安装位置随意。

（4）表节点。表节点安装在用户的厨房或其它方便的地方，表节点具有监测燃气使用量、路由的功能。

在对用户燃气表进行数据收集时，系统管理人员要先在服务器上进行一定的设置，然后服务器通过GPRS方式与基站进行通信，发送抄表命令。基站收到抄表命令后，开始收集数据并向第一级表节点发送命令。该命令沿着协议链路从第一级表节点一直传送到最后一级表节点（叶子节点），叶子节点检测到自己是最后一级表节点，将收集到的数据向上一级表节点返回。数据以相反的方向沿着协议链路从叶子节点一直返回到第一级表节点，再由第一级表节点将数据返回给基站，最后基站通过 GPRS 方式将数据返回给服务器[1]。endprint

2 UIO方法的不足及优化

由于UIO方法是基于有限状态机FSM模型的测试序列生成方法，因此首先介绍FSM模型，然后介绍UIO序列生成方法及UIO方法的不足，最后介绍优化后的测试序列生成方法。

2.1 FSM模型

有限状态机模型FSM主要用于表示有限多个状态与这些状态之间的输入输出情况，一个确定的有限状态机是一种初始化、确定的米利机（Mealy machine），它在形式上被定义为一个6元组M=（S，I，O，δ，λ，s0）[3]，其中：S={s0，s1，…，sn}是状态的有限非空集合；I={i0，i1，…，im}是输入符号的有限非空集合；O={o0，o1，…，or}是输出符号的有限非空集合；δ：S× I →S 是状态迁移函数；λ∶S× I →O 是输出函数；s0∈S 是初始状态。

可以用有向图G=（V，E）表示FSM。其中V={v1，v2，…，vn}是非空顶点集合，与FSM的有限非空状态集合S相对应；E= {（vi，vk；il/om）|vi，vk∈V，il∈I，om∈O}是有向边的集合，与FSM迁移的集合相对应；（vi，vk；il/om）∈E表示FSM上一条从状态vi 到状态vk 的迁移，il和om 分别是这条迁移上的输入与输出事件。图2是一个FSM的有向图。

2.2 UIO序列生成方法

UIO方法的思想是，首先为FSM的每一个状态生成一个识别序列，该识别序列可以区分每一个状态，称之为唯一输入输出UIO（Unique Input/Output）序列，然后根据该识别序列构造测试序列。UIO序列生成方法如下：

（1）建立所有的边与输入输出集的关系。

（2）求出FSM模型中每个状态长度为1的输入输出序列。

（3）检查它们的唯一性。若唯一，此状态的UIO序列就找到了；若不唯一，则继续找此状态的UIO序列，转（4）。

（4）对还没找到UIO序列的状态，根据其长度为K的输入输出序列，继续求出长度为K+1的输入输出序列，检查它们是否唯一，直到每个状态都找到UIO序列或者长度超过2n2，n代表模型中状态的个数。以图2的FSM为例，表1为图2所示FSM各个状态的UIO序列。

2.3 UIO方法的不足

UIO方法中每测试一个迁移之前，都需要用重置信息将被测设备置于初始状态，这样会产生一些冗余。另外，FSM中每个状态可能有多个最短的UIO序列，UIO方法中只要找到一个符合要求的，就继续求另一状态的UIO序列，这样随机得到的UIO序列可能只是局部最优解，而不是整体最优解，造成测试序列过长。

文献[10]根据上述不足对算法进行了改进，改进后的算法缩短了测试序列的长度，但不适用于本文研究的WM2RP协议。其中，生成伪图后只检查伪图的对称性，若对称则不再进行扩展，然而，对称的伪图不一定存在欧拉回路，对称且强连通的伪图则一定存在一条欧拉回路。

2.4 优化后的测试序列生成方法

根據上述不足，在文献[10]算法基础上进行优化，除了对称性还需要检查伪图的强连通性。优化后的测试序列生成算法步骤如下：

（1）首先得到FSM模型中各个状态的所有最短UIO序列。利用上文UIO序列生成方法，求出每个状态的所有最短UIO序列。

（2）设IUT的FSM模型用有向图G=（V，E）表示，其中V={v1，v2，...，vn}为FSM的状态集合，E={（vi，vj；ik/om）|vi，vj∈V，ik∈I，om∈O}为FSM的迁移集合。对于每个状态迁移（vi，vj；ik/om）都构造一个相应的伪迁移，即测试序列e（vi，vj；ik/om）={ik/om，UIO（vj）}，其中vi为该测试序列的起始状态，vj为执行ik/om后的状态，UIO（vj）为利用UIO序列生成方法所找到的状态vj的UIO序列，vl为施加特征序列UIO（vj）后的结束状态，也是该测试序列的终止状态。即对G图中的每一个状态迁移（vi，vj；ik/om）生成一个对应G图中的伪迁移e（vi，vj，vl；ik/om）={ik/om，UIO（vj）}。伪图G=（ V，E），其中V不变，为FSM的状态集合，E为伪迁移的集合，E={ e（vi，vj，vl；ik/om） |vi，vj，vl∈V，ik∈I，om∈O }。利用每个状态的多个UIO序列，在为每一个迁移生成伪迁移时决定采用哪一个UIO序列，从而使得生成的伪图在进行对称扩展前尽可能地连通且对称。

在图论中，欧拉遍历是指正好经过图中每条边一次的一个序列，欧拉回路是指从一个顶点出发最终又回到此顶点的欧拉遍历。相关定理如下：

定理1[13] 一个有向图G存在一条欧拉回路的充要条件是图G强连通且对称。

（3）检查G′是否对称。若G′仍然不对称，则对其进行对称扩展，添加若干条取自于E的边，使G′对称。

（4）检查G′是否强连通。如果不是强连通，则对其进行扩展，添加若干条取自E的边，使G′变成欧拉图G*。

（5）从G*图中构造以初始状态为起点的欧拉遍历，所得到的序列即为最后生成的测试序列。

3 WM2RP协议建模

根据上文对WM2RP协议的概述，笔者依据规范中不同类型节点的行为对各类节点建立FSM模型，其中中继器的行为除了不能收集数据以外，电脑与中间表节点的行为基本相同。将中继器与中间表节点作为同一类节点进行建模，最终建立了3种类型的模型：基站模型（Base Station Model，Mbs）、中间节点模型（Inter Node Model，Min）与叶子节点模型（Leaf Node Model，Mln）。

3.1 基站FSM模型

根据协议中基站的行为抽象出FSM模型（见图3）：Mbs=（S，I，O，δ，λ，s0）endprint

（1） 其中：S={s0，s1，s2}

（2） 式（2）中：s0为初始状态，此时基站正等待被唤醒或者初始化；s1为等待接收下一级节点的ACK确认回复状态，此时基站已收到服务器端发来的抄表命令，并向下一级节点发送了抄表命令，正在等待接收下一级节点的ACK确认回复；s2为等待接收下一级节点发送的数据状态，此时基站已经收到了下一级节点发送的ACK确认回复，正在等待接收下一级节点发送过来的数据。I={i0，i1，i2}

（3） 式（3）中：i0为收到服务器端发送过来的抄表命令；i1为收到下一级节点发送过来的ACK确认回复；i2为收到下一级节点发送过来的数据。O={o0，o1}

（4） 式（4）中：o0为向下一级节点发送抄表命令；o1为回复收到数据的ACK，并将数据发送给服务器端。δ∶S× I →S

（5） 式（5）中：δ（s0，i0）=s1；δ（s1，i1）=s2；δ（s2，i2）=s0λ∶S× I →O

（6） 式（6）中：λ（s0，i0）=o0；λ（s2，i2）=o1；s0为初始状态。

被测设备作为基站工作时会在以上3个状态之间进行转换，共有3个状态转移，每个状态转移都有相应的触发条件或输入输出。说明如下：①T0（i0/o0）：服务器端通过GPRS向被测设备发送抄表命令，被测设备收到抄表命令，同时向下一级节点发送抄表命令，且消息中应带有下一级节点的地址，此时被测设备将由初始状态，转换为等待下一级节点发送收到抄表命令的ACK确认回复状态；②T1（i1/-）：下一级节点向被测设备发送收到抄表命令的ACK确认回复，被测设备收到回复，此时被测设备将由等待接收下一级节点的ACK确认回复状态，转换为等待接收下一级节点发送的数据状态；③T2（i2/o1）：下一级节点将收集到的数据发送给被测设备，被测设备收到数据，向下一级节点回复收到数据的ACK，并将收到的数据通过GPRS发送给服务器端，此时被测设备由等待接收下一级节点发送的数据状态转换为初始状态。

3.2 中间节点FSM模型

根据中间节点抽象出来的FSM模型为Min=（S，I，O，δ，λ，s0），如图4所示。

被测设备作为中间节点工作时会在以上4个状态之间进行转换，共有4个状态转移，每个状态转移都有相应的触发条件或输入输出，说明如下：①T0（i0/o0）：被测设备的上一级节点向被测设备发送抄表命令，被测设备收到抄表命令，向上一级节点回复收到命令的ACK，同时向下一级节点发送抄表命令，且消息中应带有下一级节点的地址，此时被测设备将由初始状态，转换为等待下一级节点发送收到抄表命令的ACK确认回复状态；②T1（i1/-）：下一级节点向被测设备发送收到抄表命令的ACK确认回复，被测设备收到回复，此时被测设备将由等待接收下一级节点的ACK确认回复状态，转换为收集数据并等待接收下一级节点发送数据的状态；③T2（i2/o1）：下一级节点将收集到的数据发送给被测设备，被测设备收到数据，向下一级节点回复收到数据的ACK，并将接收到的数据与自己收集到的数据融合在一起，发送给上一级节点，此时被测设备由等待接收下一级节点发送数据的状态，转换为等待接收上一级节点收到数据的ACK确认回复状态；④T3（i3/-）：上一级节点收到被测设备发送过来的数据，向被测设备回复收到数据的ACK，被测设备收到回复，同时由等待接收上一级节点收到数据的ACK确认回复状态，转换为初始状态。

3.3 叶子节点FSM模型

根据叶子节点抽象出来的FSM模型为Mln=（S，I，O，δ，λ，s0），如图5所示。

被测设备作为叶子节点工作时会在图5所示3个状态之间进行转换，共有3个状态转移，每个状态转移都有相应的触发条件或输入输出，说明如下：①T0（i0/o0）：被测设备的上一级邻节点向被测设备发送抄表命令，被测设备收到抄表命令并向上一级邻节点回复收到命令的ACK，此时被测设备将由初始状态，转换为收集数据并等待向上一级节点发送数据状态；②T1（-/o1）：被测设备将收集到的数据发送给上一级节点，此时被测设备将由收集数据并等待向上一级节点发送数据状态，转换为向上一级节点发送数据完成状态；③T2（i1/-）：上一级节点收到被测设备发送的数据，向被测设备回复收到数据的ACK，被测设备收到回复，由向上一级节点发送数据完成状态，转换为初始状态。

4 测试序列生成

上文已经建立了WM2RP协议各类型节点的FSM模型，根据优化后的测试序列生成算法，可以得到WM2RP协议各类型节点的测试序列。步骤如下：

（1）首先得到WM2RP协议各类型节点的FSM模型中各个状态的所有最短UIO序列。表2为WM2RP协议FSM模型各个状态的UIO序列。

（2）利用各个状态的多UIO序列，为每一个迁移生成伪迁移。由表2可知，WM2RP协议中FSM模型的各个状态均只有一个UIO序列，因此不需要较多UIO的 序列。表3为WM2RP协议FSM模型中各个迁移的伪迁移。

以中间节点的FSM模型为例，根据表3中的伪迁移，可得到中间节点的伪图G′，图6为中间节点的伪图G′。

（3）检查中间节点的伪图G′是否對称。由图6可以看出，G′是对称的，因此不需要进行对称扩展。

（4）检查中间节点的伪图G′是否强连通。由图6可以看出，G′不是强连通的，因此需要对其进行扩展，添加若干条取自于图4的边。图7为图6扩展后生成的中间节点的欧拉图G*。图7中虚线表示取自于图4的边，其上的数值表示该边在对称扩展中用到的次数。

（5）从图7中间节点模型的欧拉图G*中构造以初始状态S0为起点的欧拉遍历，所得到的序列即为中间节点的测试序列。中间节点的最终测试序列如下：i0/o0，i1/-，i2/o1，i3/-，i0/o0，i1/-，i2/o1，i3/-，i0/o0，i1/-，i2/o1，i3/-。可以看出，测试序列的长度为12。endprint

同样地，根据该算法可以生成基站测试序列如下：i0/o0，i1/-，i2/o1，i0/o0，i1/-，i2/o1。测试序列的长度为6。叶子节点测试序列如下：i0/o0，-/o1，i1/-，i0/o0，-/o1，i1/-。测试序列的长度为6。

5 测试执行

5.1 测试平台搭建

校内实验室不具备企业对路由协议进行实际测试所需的硬件设备，为了能够利用生成的测试用例对协议的具体实现进行测试，在合作公司已有燃气抄表系统的基础上开发了一个测试程序，该测试程序包括集中器程序与表节点程序两个部分。

在搭建的测试环境中，公司燃气抄表系统就是服务器，它作为远程管理中心，可以给集中器发送抄表命令，集中器程序可以与服务器以及表节点程序进行通信。集中器程序通过设置服务器地址与服务器端口号，与服务器建立连接，表节点程序通过设置表编号与端口号，与集中器或其它表节点建立连接。每一个表节点程序是一个进程，需要多少个表节点，就要打开多少个表节点程序。

5.2 测试执行与结果分析

上文中，已测试环境已搭建完成并且建立了连接，接下来将登录燃气自动抄表系统，进入远程民用抄表界面。点击发送命令，服务器开始向集中器发送抄表命令进行数据收集。

将生成测试序列中的输入应用到协议实现，会产生一个实际输出，与测试序列中预期的输出相比，看是否一致。上文也得到了各类节点的测试序列，以基站为例，由基站模型得到的输入序列为：i0，i1，i2，i0，i1，i2 ，对应的预期输出序列为：o0，-，o1，o0，-，o1，由测试结果对应相应的序列可以得到实际输出的序列为：o0，-，o1，o0，-，o1。基站的预期输出与实际输出一致，证明基站的实现与规范是一致的。

用相同的方法对中间节点程序与叶子节点程序进行测试，它们的实现和规范也是一致的。表4为各类型节点程序的测试结果分析。

6 结语

本文将UIO方法应用于无线传感器网络数据收集协议WM2RP的一致性测试，并在应用过程中对现有基于UIO的算法进行了优化，使之具有更好的适用性。

参考文献：

[1] 王非，杨红丽，秦胜潮，等.基于时间自动机模型的无线传感器网络数据收集协议测试用例生成[J].计算机应用，2015，35（4）：1164-1168.

[2] 李强，余祥，齐建业，等.协议一致性测试研究进展[J].西南科技大学学报，2013，28（4）：85-92.

[3] 蒋宗礼.形式语言与自动机理论教学参考书[M].北京：清华大学出版社，2007.

[4] DOROFEEVA R， EL-FAKIH K， MAAG S， et al. FSM-based conformance testing methods： a survey annotated with experimental evaluation [J]. Information & Software Technology， 2010，52（12）：1286-1297.

[5] PINHEIRO A C， SIMAO A， AMBROSIO A M. FSM-based test case generation methods applied to test the communication software on board the ITASAT university satellite： a case study [J]. Journal of Aerospace Technology & Management， 2014， 6（4）：447-461.

[6] 刘攀，缪淮扣，曾红卫，等.基于FSM的测试理论、方法及评估[J].计算机学报，2011，34（6）：965-984.

[7] SABNANI K， DAHBURA A. A protocol test generation procedure [J]. Computer Networks and ISDN Systems， 1988，15（4）：285-297.

[8] TANG J， HUANG X， QIAN J， et al. A FSM-based test sequence generation method for RPL conformance testing [C]. Green Computing and Communications，2013：591-597.

[9] 黎中文，张来顺，何焱.基于FSM的测试序列生成方法研究[J].计算机应用研究，2011，28（9）：3368-3371.

[10] 陈涛，潘雪增，陈健，等.基于FSM的协议相符性测试序列生成算法研究[J].计算机工程与應用，2010（6）：60-62.

[11] DERDERIAN K， HIERONS R M， HARMAN M， et al. Automated unique input output sequence generation for conformance testing of FSMs [J]. The Computer Journal， 2006，49（3）：331-344.

[12] 陈守宁，郑宝玉，李璟，等.IPv6邻居发现协议的一致性测试序列生成[J].信号处理，2013，29（12）：1670-1676.

（责任编辑：何 丽）endprint