基于Wp测试用例约简集的无线传感器网络系统测试方法

摘要

基于Wp测试用例约简集的无线传感器网络系统测试方法属于无线传感器网络系统的通信协议设计验证和系统测试。其特征在于，依次含有以下步骤：利用Wp方法处理计算机仿真系统有限状态机模型M

说明书

技术领域

本发明属于软件系统测试领域，尤其涉及无线传感器网络系统的通信协议设计验证和系 统测试。

背景技术

无线传感器网络是由部署在监测区域内大量的廉价微型传感器节点组成，通过无线通信 方式形成的一个多跳的自组织的网络系统，其目的是协作地感知、采集和处理网络覆盖区域 中被感知对象的信息，并发送给观察者。无线传感器网络系统在开发部署过程中，相关人员 由于自身局限性并没有完全理解协议规则或者软件及硬件环境的不兼容等因素，都会使系统 出现问题，所以需要对无线传感器网络系统进行全面可靠的测试以及时发现系统缺陷。目前 阶段，对系统进行测试的测试用例大都为人工编写，易对某些重要的测试环节遗漏，同时较 多的测试用例使得实际测试工作量繁重，所以一种可靠规模较小的测试方案，在实际测试中 具有重要意义。

基于有限状态机模型的一致性测试是一种黑盒测试，其目的是检查运行通信协议的系统 与协议标准的符合程度。目前基于有限状态机的测试序列生成算法已经比较成熟。在众多的 测试算法中，Wp方法是一种经典有效的测试用例生成方法，具有较高的故障检测能力，利 用该方法进行无线传感器网络系统测试能够得到完备的测试用例集。但该方法生成的测试用 例集规模较大，数量较多，在实际测试中会导致大量的人力资源消耗。本发明利用集合覆盖 贪心算法，通过构造需求集实现了对Wp方法测试用例集的约简，能够在保证Wp原始测试 用例集错误检测能力不受影响的前提下，对原始测试用例集进行有效的约简，提高无线传感 器网络系统的实际测试效率。

在协议的一致性测试中，常使用有限状态机模型描述协议规范，有限状态机模型一般分 为两种，Moore机和Mealy机。如果一个有限状态机模型不将状态转换与任何操作关联在一 起，则称作Moore机。如果有限状态机模型将每一个状态转换都与操作关联在一起，则称 作Mealy机，在本发明中只考虑Mealy机。

一个有限状态机模型M是一个六元组(Q，X，Y，q₀，δ，O)，其中：

Q是有限个状态的集合。

X是一个有限的输入符号集合，称为输入字符集，所述输入字符集中的每一个输入符号 对应实际的输入操作符号，起到控制状态转换的作用。

Y是一个有限的输出符号的集合，称为输出字符集，是所述输入操作符号对状态进行转 换控制时的输出信号。

q₀∈Q，是有限状态机模型的初始状态。

δ：Q×X→Q′，δ是状态转换函数，表示所述的输入符号集X使当前状态集合Q转换为下 一个状态集合Q′。δ(q_i，s₁)＝q_j，表示输入字符串s₁使当前状态q_i转换为下一个状态q_j， 其中q_i∈Q，q_j∈Q，s₁为输入符号集X中的l个输入字符构成的输入字符串，l为非负整数。

O：Q×X→Y，O是输出函数，表示所述的输入符号集X使当前状态集合Q发生转换时产 生输出符号集合Y。O(q_i，s₂)＝O(q_i，a₁)·O(δ(q_i，a₂)，a₃a₄...a_l)＝Y，表示长度为l的 输入字符串s₂使当前状态q_i发生转换时产生的一个输出字符集Y，其中q_i∈Q，s₂＝ (a₁a₂a₃...a_l)，a₁a₂a₃...a_l均属于输入字符集X。

在本发明中使用结构(q_i，q_j，x/y)表示一个状态到下一个状态的转换，其中q_i∈Q， q_j∈Q，x∈X，y∈Y，δ(q_i，x)＝q_j，O(q_i，x)＝y，其含义为当有限状态机模型处于q_i状 态时，对其输入字符x，有限状态机模型将转入状态q_j，同时输出符号y。有限状态机模型在 输入空序列的情况下，将产生空输出，同时仍处于原来的状态，使用符号ε表示空输入序列， null表示空输出，该转换表示为(q_i，q_i，ε/null)。

Wp方法，又称部分W方法，是由Fujiwara等人提出的，是一种经典的系统测试方法， 具有较高的故障检测能力。利用Wp方法生成测试用例集，有限状态机模型M应满足一些 前提，其中包括：

(1)M是确定的。

对于任意确定的输入字符x∈X，在M的任意状态q_i输入所述字符x时，q_i最多只存在一 个后继状态，则称M是确定的。

(2)M是完全定义的。

对于模型M，从它的每一个状态出发，对每一个输入符号x∈X都存在一个转换，则M 是完全定义的。

(3)M是最小的。

若M中的存在两个状态q_i、q_j，对于任意l个输入字符构成的输入字符串s都产生相同 的输出，则称状态q_i、q_j等价。若M中不存在这样的状态对，则称M是最小的。

(4)M能够准确的重置到初始状态，在重置操作中产生输出null。

假设设计规范中有限状态机模型M含n(n＞0)个状态，而实际运行的待测系统的最多 包含m(m＞0)个状态。下面是Wp算法的总体流程：

Begin of Wp

步骤(1)，计算M的转换覆盖集P、状态覆盖集S、特征集W、等价特征集W_i。

步骤(2)，测试子集T₁＝S·I[m-n]·W。

步骤(3)，设ψ是M的所有等价特征集组成的集合，ψ＝{W₀，W₁，W₂，...，W_n}， W₀为q₀等价特征集，W₁为q₁等价特征集，以此类推。

步骤(4)，设R＝{r₁，r₂，...，r_k}是所有属于转换覆盖集P但不属于状态覆盖集S的输 入字符串的集合，即R＝P-S。另外，如果r_i∈R，则δ(q₀，r_i)＝q_i。

步骤(5)，测试子集其中r_i∈R，δ(q₀，r_i)＝q_i， δ(q_i，u)＝q₁，W₁是状态q₁的状态等价集，W₁∈ψ。

步骤(6)，合并T₁和T₂得到测试集T。

End of Wp

其中，转换覆盖集P定义如下：

设q_i、q_j为M中的任意两个状态，i≠j，P由形如s、x的输入字符串组成，其中 δ(q₀，s)＝q_j，δ(q₀，x)＝q_j，空字符ε也属于P。

状态覆盖集S是一个有穷非空集合，其中的每一个元素都是若干输入字符组成的输入字 符串。对于任意q_i∈Q，存在r∈S，满足δ(q₀，r)＝q_i，其中r为输入字符串。很容易看出， 状态覆盖集是转换覆盖集P的子集，且不唯一。

特征集W是一个输入字符串的有限集合，这些输入串能够区分出M中任意两个状态的 行为。假设q_i和q_j是Q中的两个状态，那么特征集W中存在一个输入串s，使得O(q_i， s)≠O(q_j，s)，其中s是若干输入字符组成的输入字符串。

等价特征集与M中的每一个状态相对应。假设q_i是Q中的任一状态，状态q_i等价集表示 成W_i，并具备以下特性：

(a)1≤i≤n，其中n为M的状态数目。

(b)对于任何j，w，1≤j≤n，j≠i，w∈W_i，有O(q_i，w)≠O(q_j，w)。

(c)不存在W_i的子集满足(b)。

I[m-n]表示如下的集合运算表达式：

(a)当m＜n时，I[m-n]＝X。

(b)当m＝n时，I[m-n]＝I[0]＝ε。

(c)当m＞n时，I[m-n]＝{ε}∪X¹∪X²…∪X^m-n-1∪X^m-n。

其中，X为有限状态机模型输入符号集合。X¹＝X，X²＝X·X，以此类推，符号″·″ 代表连接运算，本发明所有涉及到该符号处，均表示连接运算。

由上述描述可知，用Wp方法生成的测试集T是两个测试子集T₁和T₂的并集，这两个子 集的功能是不同的。测试子集T₁用于检测实现I是否包含了M中的所有状态并检测部分转换 的实现是否正确；T₂用于测试M中定义的其余转换是否在待测的实际系统中得到了正确的 实现，即判断所检测转换的输出和即将跳转的下一个状态是否与M中的定义相一致。

集合覆盖贪心算法(GREEDY_SET_COVER)是一种经典的求解最小子集问题的算法，该 算法重复在集合中选择一条测试用例S，覆盖集合G中最多且未被覆盖的需求，直到G中所 有的需求都被覆盖为止。本发明利用GREEDY_SET_COVER算法对测试集进行约简，得到Wp 的测试用例约简集。将GREEDY_SET_COVER算法设置为三元函数，函数完整原型如下：

其中，第一个参数为待约简的测试集，第二个参数G为覆盖需求集，第三个参数 isCover_Func设置为谓词函数，函数的返回值为约简后的测试序列的集合。本发明中 GREEDY_SET_COVER算法流程大致如下：

Begin of GREEDY_SET_COVER

步骤(1)，U＝G

步骤(2)，

步骤(3)，

步骤(4)，选择当前最佳序列使得CovedSet最大，其中 CovedSet＝SetCovered(S，U，isCover_Func)

步骤(5)，U＝U-CovedSet

步骤(6)，C＝C∪{S}

步骤(7)，return C

End of GREEDY_SET_COVER

其中，函数SetCovered(S，U，isCover_Func)根据谓词函数isCover_Func返回集合U中 被序列S覆盖的元素组成的集合。而在本发明中会使用到两种谓词函数：

(1)bool isCover_Prefix(Sequence1，Sequence2)

该函数判断Sequence2是否为Sequence1的前缀，若是，即说明Sequence1覆盖 Sequence2，则返回true，否则返回false。特殊情况下，若Sequence1与Sequence2相等， 同样返回true。

(2)bool isCover_SubSeq(Sequence1，Sequence2)

该函数判断Sequence2是否为Sequence1的子串，若是，即说明Sequence1覆盖 Sequence2，则返回true，否则返回false。特殊情况下，若Sequence1与Sequence2相等， 同样返回true。

覆盖需求集G的构造是使用GREEDY_SET_COVER算法进行Wp方法测试集约简的关键。 本发明首先分别针对Wp方法生成的测试子集T₁和测试子集T₂，构造不同的覆盖需求集，利 用GREEDY_SET_COVER算法对其进行约简，得到约简后的测试集T′₁和T′₂。然后再次构造另一 覆盖需求集，对T′₁∪T′₂进行约简，得到最终的约简测试集T。覆盖需求集构造内容将在本发 明的发明内容部分进行介绍。

发明内容

本发明目的在于提出一种基于Wp方法生成的测试用例约简集对无线传感器网络系统 进行测试的方法，该方法能够在保证Wp原始测试用例集错误检测能力不受影响的前提下， 对原始测试用例集进行有效的约简，提高无线传感器网络系统的实际测试效率。

本发明特征在于，是一种无线传感器网络系统通信协议设计验证和系统测试的方法，依 次含有以下步骤：

步骤(1)，按以下步骤首先利用Wp方法处理计算机仿真系统有限状态机模型M₁生成 测试用例集合，然后构造覆盖需求集合，利用集合覆盖贪心算法对得到测试用例集进行约简， 得到Wp方法测试用例约简集。

步骤(1.1)，将所述的计算机仿真系统有限状态机模型M₁用(Q，X，Y，q₀，δ，O)这 个六元组表示，其中，

有限状态集合Q包含：空闲状态、发送状态和接收状态三个状态，分别用q₀，q₁，q₂表 示。其中空闲状态q₀为初始状态。为简便起见，假设计算机仿真系统有限状态机模型状态数 为n，实际系统的状态数为m，且m＝n。

M₁有两种输入符号，分别为控制信号A和控制信号B，即输入字符集X＝{A，B}。

M₁有两种输出符号，分别为二进制的0和1，即输出字符集Y＝{0，1}。

状态转移函数δ包括：

δ(q₀，A)＝q₁，δ(q₀，B)＝q₂，δ(q₁，A)＝q₀，

δ(q₁，B)＝q₂，δ(q₂，A)＝q₁，δ(q₂，B)＝q₀。

其中，δ(q₀，A)＝q₁表示在空闲状态q₀下，输入控制信号A，使计算机仿真系统有限 状态机模型M₁从空闲状态q₀转换到发送状态q₁，其余类推。

输出符号O包括：

O(q₀，A)＝1，O(q₀，B)＝1，O(q₁，A)＝0，

O(q₁，B)＝1，O(q₂，A)＝0，O(q₂，B)＝1。

O(q₂，B)＝1表示接收状态q₂下，输入控制信号B，输出1，其余类推，根据所述的有 限状态机模型M₁六元组得到所述计算机仿真系统有限状态机模型。

步骤(1.2)，由Wp方法得到计算机仿真系统有限状态机模型M₁测试用例约简所需要 的集合：

转换覆盖集P＝{ε，A，AA，AB，B，BA，BB}。

状态覆盖集S＝{ε，A，AB}。

特征集W＝{A，AA}。

等价特征集W₀＝{A}、W₁＝{A，AA}、W₂＝{A，AA}。

测试用例子集T₁＝{A，AA，AAA，ABA，ABAA}。

测试用例子集T₂＝{AAA，BA，BAA，BAAA，BBA}。

约简前的测试用例集合：

T″＝T₁∪T₂＝{A，AA，AAA，ABA，ABAA，BA，BAA，BAAA，BBA}。

步骤(1.3)，对计算机仿真系统有限状态机模型M₁的各个转换设置唯一的转换标识。 如下表1所示：

表1

转换 转换标识 (q₀，q₁，A/1) t₁(q₀，q₂，B/1) t₂(q₁，q₀，A/0) t₃(q₁，q₂，B/1) t₄(q₂，q₁，A/0) t₅(q₂，q₀，B/1) t₆

将步骤(1.2)中得到的每个集合转换成由转换标识构成的对应集合。

$T_1^{\mathrm{id}}=\{t_1,t_1{t}_3,t_1{t}_3{t}_1,t_1{t}_4{t}_5,t_1{t}_4{t}_5{t}_3\}.$

$T_2^{\mathrm{id}}=\{t_1{t}_3{t}_1,t_2{t}_5,t_2{t}_5{t}_3,t_2{t}_5{t}_3{t}_1\}.$

S^id＝{ε，t₁，t₁t₄}。

P^id＝{ε，t₁，t₁t₃，t₁t₄，t₂，t₂t₅，t₂t₆}。

R^id＝{t₁t₃，t₂，t₂t₅，t₂t₆}。

$W_0^{\mathrm{id}}\left(q_0\right)=\left\{t_1\right\},W_1^{\mathrm{id}}\left(q_1\right)=\{t_3,t_3{t}_1\},W_2^{\mathrm{id}}\left(q_2\right)=\{t_5,t_5{t}_3\}.$

其中，

Wp测试集子集合T₁中的每条测试序列分别从初始状态出发，将其依次经过的每 个转换用对应的转换标识替代，得到的替代后转换标识序列所构成的集合。

Wp测试集子集合T₂中的每条测试序列分别从初始状态出发，将其依次经过的每 个转换用对应的转换标识替代，得到的替代后转换标识序列所构成的集合。

S^id：表示状态覆盖集S中的每条测试序列分别从初始状态出发，将其依次经过的每个转 换用对应的转换标识替代，得到的替代后转换标识序列所构成的集合。

P^id：表示转换覆盖集P中的每条测试序列分别从初始状态出发，将其依次经过的每个转 换用对应的转换标识替代，得到的替代后转换标识序列所构成的集合。

R^id：表示P^id与S^id的差集，即R^id＝P^id-S^id。

表示等价特征集W_i中的每条测试序列分别从状态q_j出发，将其依次经过的每 个转换用对应的转换标识替代，得到的替代后转换标识序列所构成的集合，其中q_j∈Q。

步骤(1.4)，对集合进行约简。

(1)构造集合T₁的覆盖需求集则

Req(T₁)＝{t₁，t₁t₃，t₁t₃t₁，t₁t₄t₅，t₁t₄t_5t3}。

(2)使用谓词函数isCover_Prefix，令约简后的为T′₁，则

$\left(\begin{array}{c}{T}_1^{\prime }=\mathrm{GREEDY}\_\mathrm{SET}\_\mathrm{COVER}(T_1^{\mathrm{id}},\mathrm{Req}\left(T_1\right),\mathrm{isCover}\_\mathrm{Prefix})\\ =\{t_1{t}_3{t}_1,t_1{t}_4{t}_5{t}_3\}\end{array}\right)$

步骤(1.5)，对集合进行约简。

(1)构造集合T₂的覆盖需求集：

●当m≠n时，

$\mathrm{Req}\left(T_2\right)=\underset{\mathrm{seq}\in R^{\mathrm{id}}}{\cup }\mathrm{Last}\left(\mathrm{seq}\right)·I^{\mathrm{id}}[m-n]\left(q\right)·W_u^{\mathrm{id}}$

其中，

q＝Tail(Last(seq))。

u＝Tail(t)，其中t＝Last(s)，s∈I^id[m-n](q)。

I^id[m-n](q)：表示对于所有seq∈I[m-n]，seq在状态q∈Q处出发，将其依次经 过的每个转换用对应的转换标识替代，得到的替代后转换标识序列所构成的集合。

Tail(t)：表示转换t的尾状态。

Last(seq)：表示转换标识序列seq的最后一项转换标识。

●当m＝n时，I^id[m-n](q)为空集，此时

$\mathrm{Req}\left(T_2\right)=\underset{\mathrm{seq}\in R^{\mathrm{id}}}{\cup }\mathrm{Last}\left(\mathrm{seq}\right)·W_q^{\mathrm{id}}$

其中，q＝Tail(Last(seq))。

在此处按照之前步骤(1.1)中的假设m＝n，则

$\left(\begin{array}{c}\mathrm{Req}\left(T_2\right)=\{t_3·W_0^{\mathrm{id}}\left(q_0\right)\cup t_2·W_2^{\mathrm{id}}\left(q_2\right)\cup t_5·W_1^{\mathrm{id}}\left(q_1\right)\cup t_6·W_0^{\mathrm{id}}\left(q_0\right)\\ =\left\{\right\{t_3{t}_1\}\cup \{t_2{t}_5,t_2{t}_5{t}_3\}\cup \{t_5{t}_3,t_5{t}_3{t}_1\}\cup \{t_6{t}_1\left\}\right\}\\ =\{t_3{t}_1,t_2{t}_5,t_2{t}_5{t}_3,t_5{t}_3,t_5{t}_3{t}_1,t_6{t}_1\}\end{array}\right)$

(2)使用谓词函数isCover_SubSeq，令约简后的为T′₂，则

$\left(\begin{array}{c}{T}_2^{\prime }=\mathrm{GREEDY}\_\mathrm{SET}\_\mathrm{COVER}(T_2^{\mathrm{id}},\mathrm{Req}\left(T_2\right),\mathrm{isCover}\_\mathrm{SubSeq})\\ =\{t_2{t}_5{t}_3{t}_1,t_2{t}_6{t}_1\},\end{array}\right)$

步骤(1.6)，对T′₁∪T′₂进行约简。

(1)构造集合T′₁∪T′₂的覆盖需求集Req(T′₁∪T′₂)＝T′₁∪T′₂，则

Req(T′₁∪T′₂)＝{t₁t₃t₁，t₁t₄t₅t₃，t₂t₅t₃t₁，t₂t₆t₁}，

(2)使用谓词函数isCover_Prefix，令约简后的T′₁∪T′₂为T′，则

T′＝GREEDY_SET_COVER(T′₁∪T′₂，Req(T′₁∪T′₂)，isCover_Prefix)

＝{t₁t₃t₁，t₁t₄t₅t₃，t₂t₅t₃t₁，t₂t₆t₁}，

步骤(1.7)，将步骤(1.6)得到的测试用例集T′中各转换序列中的转换标识替换为对 应转换的输入符号，得到最终的测试用例集：

T＝{AAA，ABAA，BAAA，BBA}。

步骤(2)，生成所述无线传感器网络系统。其中包括：中央控制器、受控于所述中央控 制器的分别表示空闲、发送和接收三种状态的状态转换指示灯L₀、L₁和L₂，分别表示无线传 感器故障、网络传输故障的故障指示灯E₁和E₂、分布式无线传感器网络，三者共同组成了 无线传感器网络系统。其中，中央控制器包括控制器和以主程序流程框图描述的通信协议设 计软件。

步骤(3)，按以下步骤利用步骤(1)中所述流程处理根据无线传感器网络系统所描述 的无线传感器网络系统有限状态机模型M₂，得到Wp测试用例约简集。

步骤(3.1)，对于所述的无线传感器网络系统通信协议设计规范而言，有限状态机模型 M₂＝(Q，X，Y，q₀，δ，O)，其中，

有限状态集合Q包含空闲状态、发送状态和接收状态，空闲状态表示系统处于初始状态， 发送状态表示系统处于发送传感器数据状态，接收状态表示系统处于接收传感器数据状态。 三个状态分别用q₀，q₁和q₂表示，即Q＝{q₀，q₁，q₂}。

输入字符集X包括两个控制操作。其中一个是代表传输控制操作的输入操作集合A，也 称传感器控制信号，A＝{a₁，a₂，a₃}，其中，

a₁表示执行输入操作a₁，在空闲状态q₀输出1信号，使系统从空闲状态q₀转向发送状 态q₁，否则发出0信号，表示不转换，用a₁/1表示使系统从空闲状态q₀向发送状态q₁转换 的状态转换控制符号。

a₂表示执行输入操作a₂，在发送状态输出1信号，使系统从发送状态q₁转向接收状态q₂， 否则发出0信号，表示不转换，用a₂/1表示使系统从发送状态q₁向接收状态q₂转换的状态 转换控制符号。

a₃表示执行输入操作a₃，在接收状态输出1信号，使系统从接收状态q₂转向空闲状态q₀， 否则发出0信号，表示不转换。用a₃/1表示使状态从接收状态q₂向空闲状态q₀转换的状态 转换控制符号。

另一个是代表故障控制操作的输入操作集合B，B＝{b₁，b₂，b₃}，其中，

b₁：在空闲状态q₀，执行输入操作b₁，输出1信号，表示故障已排除，使系统从空闲状 态q₀转换为状态q₂进入接收状态，否则输出0信号，故障未排除，状态不发生转换，用b₁/1 表示使系统从空闲状态q₀转换为接收状态q₂的状态转换控制符号。

b₂：在接收状态q₂，执行输入操作b₂，输出1信号，表示出现数据网络传输故障，需要 重传，使系统从接收状态q₂转换为发送状态q₁，红色状态指示灯由L₂变为L₁，否则输出0 信号，不需要重传数据。用b₂/1表示使系统从接收状态q₂转换为发送状态q₁的状态转换控 制符号。

b₃：在发送状态q₁，执行输入操作b₃，输出1信号，表示出现无线传感器故障，使发送 状态q₁转换为空闲状态q₀，红色状态指示灯由L₁变为L₀，停止发送，否则输出0信号，表 示正常。用b₃/1表示使系统从发送状态q₁转换为空闲状态q₀的状态转换控制符号。

输出字符集Y包括二进制码1和0，其中1表示存在状态发生转换或传输出现故障。0 表示不存在以上情形。

状态转移函数δ包括：

δ(q₀，a₁)＝q₁，δ(q₀，a₂)＝q₀，δ(q₀，a₃)＝q₀，

δ(q₀，b₁)＝q₂，δ(q₀，b₂)＝q₀，δ(q₀，b₃)＝q₀，

δ(q₁，a₁)＝q₁，δ(q₁，a₂)＝q₂，δ(q₁，a₃)＝q₁，

δ(q₁，b₁)＝q₁，δ(q₁，b₂)＝q₁，δ(q₁，b₃)＝q₀，

δ(q₂，a₁)＝q₂，δ(q₂，a₂)＝q₂，δ(q₂，a₃)＝q₀，

δ(q₂，b₁)＝q₂，δ(q₂，b₂)＝q₁，δ(q₂，b₃)＝q₂。

其中，δ(q₁，b₃)＝q₀表示在发送状态q₁执行输入操作b₃，使无线传感器网络系统有限 状态机模型M₂由发送状态q₁转移为空闲状态q₀，表示出现无线传感器故障，其余类推。

输出符号O包括：

O(q₀，a₁)＝1，O(q₀，a₂)＝0，O(q₀，a₃)＝0，

O(q₀，b₁)＝1，O(q₀，b₂)＝0，O(q₀，b₃)＝0，

O(q₁，a₁)＝0，O(q₁，a₂)＝1，O(q₁，a₃)＝0，

O(q₁，b₁)＝0，O(q₁，b₂)＝0，O(q₁，b₃)＝1，

O(q₂，a₁)＝0，O(q₂，a₂)＝0，O(q₂，a₃)＝1，

O(q₂，b₁)＝0，O(q₂，b₂)＝1，O(q₂，b₃)＝0。

O(q₀，b₁)＝1表示在空闲状态q₀，执行输入操作b₁，输出1信号，表示故障已排除， 无线传感器网络系统有限状态机模型M₂由空闲状态q₀回到接收状态q₂，其余类推。

根据所述六元组有限状态机模型得到所述无线传感器网络系统有限状态机模型。

步骤(3.2)，由Wp方法得到无线传感器网络系统有限状态机模型M₂测试用例约简所 需要的集合：

转换覆盖集P＝{ε，a₂，a₃，b₂，b₃，a₁b₃，b₁a₃，a₁a₂a₃，b₁b₂b₃，a₁，a₁a₁，a₁b₁，a₁b₂， a₁a₃，b₁b₂，b₁b₂a₁，b₁b₂a₃，b₁b₂b₁，b₁b₂b₂，a₁a₂b₂，b₁，a₁a₂，b₁a₁，b₁a₂，b₁b₁，b₁b₃，b₁b₂a₂， a₁a₂a₁，a₁a₂a₂，a₁a₂b₁，a₁a₂b₃}。

状态覆盖集S＝{ε，a₁，b₁}。

特征集W＝{a₁，a₂，a₃}。

等价特征集W₀＝{a₁}，W₁＝{a₂}，W₃＝{a₃}。

第一部分测试用例集合：

T₁＝{a₁，a₂，a₃，a₁a₁，a₁a₂，a₁a₃，b₁a₁，b₁a₂，b₁a₃}。

第二部分测试用例集合：

T₂＝{a₂a₁，a₃a₁，b₂a₁，b₃a₁，a₁b₃a₁，b₁a₃a₁，a₁a₂a₃a₁，b₁b₂b₃a₁，a₁a₁a₂，a₁b₁a₂，a₁b₂a₂， a₁a₃a₂，b₁b₂a₂，b₁b₂a₁a₂，b₁b₂a₃a₂，b₁b₂b₁a₂，b₁b₂b₂a₂，a₁a₂b₂a₂，a₁a₂a₃，b₁a₁a₃，b₁a₂a₃， b₁b₁a₃，b₁b₃a₃，b₁b₂a₂a₃，a₁a₂a₁a₃，a₁a₂a₂a₃，a₁a₂b₁a₃，a₁a₂b₃a₃}。

约简前的测试用例集合：

T″＝T₁∪T₂＝{a₁，a₂，a₃，a₁a₁，a₁a₂，a₁a₃，b₁a₁，b₁a₂，b₁a₃，a₂a₁，a₃a₁，b₂a₁，b₃a₁， a₁b₃a₁，b₁a₃a₁，a₁a₂a₃a₁，b₁b₂b₃a₁，a₁a₁a₂，a₁b₁a₂，a₁b₂a₂，a₁a₃a₂，b₁b₂a₂，b₁b₂a₁a₂，b₁b₂a₃a₂， b₁b₂b₁a₂，b₁b₂b₂a₂，a₁a₂b₂a₂，a₁a₂a₃，b₁a₁a₃，b₁a₂a₃，b₁b₁a₃，b₁b₃a₃，b₁b₂a₂a₃，a₁a₂a₁a₃， a₁a₂a₂a₃，a₁a₂b₁a₃，a₁a₂b₃a₃}。

步骤(3.3)，对无线传感器网络系统有限状态机模型M₂的各个转换设置唯一的转换标 识。如下表2所示：

表2

转换 转换标识 (q₀，q₀，a₂/0) t₁(q₀，q₀，a₃/0) t₂(q₀，q₀，b₂/0) t₃(q₀，q₀，b₃/0) t₄(q₀，q₁，a₁/1) t₅(q₀，q₂，b₁/1) t₆(q₁，q₁，a₁/0) t₇(q₁，q₁，a₃/0) t₈(q₁，q₁，b₁/0) t₉(q_`1，q₁，b₂/0) t₁₀(q₁，q₀，b₃/1) t₁₁(q₁，q₂，a₂/1) t₁₂(q₂，q₂，a₁/0) t₁₃(q₂，q₂，a₂/0) t₁₄(q₂，q₂，b₁/0) t₁₅(q₂，q₂，b₃/0) t₁₆(q₂，q₀，a₃/1) t₁₇(q₂，q₀，b₂/1) t₁₈

将步骤(1.2)中得到的每个集合转换成由转换标识构成的对应集合。其中，

$T_1^{\mathrm{id}}=\{t_5,t_1,t_2,t_5{t}_7,t_5{t}_{12},t_5{t}_8,t_6{t}_{13},t_6{t}_{14},t_6{t}_{17}\}.$

$\left(\begin{array}{c}{T}_2^{\mathrm{id}}=\{t_1{t}_5,t_2{t}_5,t_3{t}_5,t_4{t}_5,t_5{t}_{11}{t}_5,t_6{t}_{17}{t}_5,t_5{t}_{12}{t}_{17}{t}_5,t_{11}{t}_{18}{t}_5,t_5{t}_7{t}_{12},t_5{t}_9{t}_{12},t_5{t}_{10}{t}_{12},\\ t_5{t}_8{t}_{12},t_6{t}_{18}{t}_{12},t_6{t}_{18}{t}_7{t}_{12},t_6{t}_{18}{t}_8{t}_{12},t_6{t}_{18}{t}_9{t}_{12},t_6{t}_{18}{t}_{10}{t}_{12},t_5{t}_{12}{t}_{18}{t}_{12},t_5{t}_{12}{t}_{17},t_6{t}_{13}{t}_{17},t_6{t}_{14}{t}_{17},\\ t_6{t}_{15}{t}_{17},t_6{t}_{16}{t}_{17},t_6{t}_{18}{t}_{12}{t}_{17},t_5{t}_{12}{t}_{13}{t}_{17},t_5{t}_{12}{t}_{14}{t}_{17},t_5{t}_{12}{t}_{15}{t}_{17},t_5{t}_{12}{t}_{16}{t}_{17}\}.\end{array}\right)$

S^id＝{ε，t₅，t₆}。

P^id＝{ε，t₁，t₂，t₃，t₄，t₅t₁₁，t₆t₁₇，t₅t₁₂t₁₇，t₆t₁₂t₁₁，t₅，t₅t₇，t₅t₉，t₅t₁₀，t₅t₈，t₆t₁₈， t₆t₁₈t₇，t₆t₁₈t₈，t₆t₁₈t₉，t₆t₁₈t₁₀，t₅t₁₂t₁₈，t₆，t₅t₁₂，t₆t₁₃，t₆t₁₄，t₆t₁₅，t₆t₁₆，t₆t₁₈t₁₂，t₅t₁₂t₁₃， t₅t₁₂t₁₄，t₅t₁₂t₁₅，t₅t₁₂t₁₆}。

R^id＝{t₁，t₂，t₃，t₄，t₅t₁₁，t₆t₁₇，t₅t₁₂t₁₇，t₆t₁₂t₁₁，t₅t₇，t₅t₉，t₅t₁₀，t₅t₈，t₆t₁₈，t₆t₁₈t₇， t₆t₁₈t₈，t₆t₁₈t₉，t₆t₁₈t₁₀，t₅t₁₂t₁₈，t₅t₁₂，t₆t₁₃，t₆t₁₄，t₆t₁₅，t₆t₁₆，t₆t₁₈t₁₂，t₅t₁₂t₁₃，t₅t₁₂t₁₄，t₅t₁₂t₁₅， t₅t₁₂t₁₆}。

$W_0^{\mathrm{id}}\left(q_0\right)=\left\{t_5\right\},W_1^{\mathrm{id}}\left(q_1\right)=\left\{t_{12}\right\},W_2^{\mathrm{id}}\left(q_2\right)=\left\{t_{17}\right\}.$

步骤(3.4)，对集合进行约简。

(1)构造集合的覆盖需求集则

Req(T₁)＝{t₅，t₁，t₂，t₅t₇，t₅t₁₂，t₅t₈，t₆t₁₃，t₆t₁₄，t₆t₁₇}。

(2)使用谓词函数isCover_Prefix，令约简后的为T′₁，则

$\left(\begin{array}{c}{T}_1^{\prime }=\mathrm{GREEDY}\_\mathrm{SET}\_\mathrm{COVER}(T_1^{\mathrm{id}},\mathrm{Req}\left(T_1\right),\mathrm{isCover}\_\mathrm{Prefix})\\ =\{t_1,t_2,t_5{t}_7,t_5{t}_{12},t_5{t}_8,t_6{t}_{13},t_6{t}_{14},t_6{t}_{17}\}.\end{array}\right)$

步骤(3.5)，对集合进行约简。

(1)构造集合的覆盖需求集的计算如下：

$\left(\begin{array}{c}\mathrm{Req}\left(T_2\right)=\{t_1·W_0^{\mathrm{id}}\left(q_0\right)\cup t_2·W_0^{\mathrm{id}}\left(q_0\right)\cup t_3·W_0^{\mathrm{id}}\left(q_0\right)\cup t_4·W_0^{\mathrm{id}}\left(q_0\right)\cup \\ t_{11}·W_0^{\mathrm{id}}\left(q_0\right)\cup t_{17}·W_0^{\mathrm{id}}\left(q_0\right)\cup t_7·W_1^{\mathrm{id}}\left(q_1\right)\cup t_9·W_1^{\mathrm{id}}\left(q_1\right)\cup \\ t_{10}{W}_1^{\mathrm{id}}\left(q_1\right)\cup t_8·W_1^{\mathrm{id}}\left(q_1\right)\cup t_{12}·W_2^{\mathrm{id}}\left(q_2\right)\cup t_{13}·W_2^{\mathrm{id}}\left(q_2\right)\cup \\ t_{14}·W_2^{\mathrm{id}}\left(q_2\right)\cup t_{15}·W_2^{\mathrm{id}}\left(q_2\right)\cup t_{16}·W_2^{\mathrm{id}}\left(q_2\right)\}\\ =\{t_1{t}_5\cup t_2·t_5\cup t_3{t}_5\cup t_4{t}_5\cup t_{11}{t}_5\cup t_{17}{t}_5{\cup t}_7{t}_{12}\cup \\ t_9{t}_{12}\cup t_{10}{t}_{12}\cup t_8{t}_{12}{\cup t}_{12}{t}_{17}\cup t_{13}{t}_{17}\cup t_{14}{t}_{17}\cup \\ t_{15}{t}_{17}\cup t_{16}{t}_{17}\}\\ =\{t_1{t}_5,t_2{t}_5,t_3{t}_5,t_4{t}_5,t_{11}{t}_5,t_{17}{t}_5,t_7{t}_{12},t_9{t}_{12},t_{10}{t}_{12},t_8{t}_{12},t_{12}{t}_{17},\\ t_{13}{t}_{17},t_{14}{t}_{17},t_{15}{t}_{17},t_6{t}_{17}\}.\end{array}\right)$

(2)使用谓词函数isCover_SubSeq，令约简后的为T′₂，则

$\left(\begin{array}{c}{T}_2^{\prime }=\mathrm{GREEDY}\_\mathrm{SET}\_\mathrm{COVER}(T_2^{\mathrm{id}},\mathrm{Req}\left(T_2\right),\mathrm{isCover}\_\mathrm{SubSeq})\\ =\{t_1{t}_5,t_2{t}_5,t_3{t}_5,t_4{t}_5,t_5{t}_{11}{t}_5,t_5{t}_{12}{t}_{17}{t}_5,t_5{t}_7{t}_{12},t_6{t}_{18}{t}_9{t}_{12},t_5{t}_{10}{t}_{12},t_5{t}_8{t}_{12},t_6{t}_{13}{t}_{17},\\ t_6{t}_{14}{t}_{17},t_6{t}_{15}{t}_{17},t_6{t}_{16}{t}_{17}\}.\end{array}\right)$

步骤(3.6)，对T′₁∪T′₂进行约简。

(1)构造集合T′₁∪T′₂的覆盖需求集Req(T′₁∪T′₂)＝T′₁∪T′₂，则

Req(T′₁∪T′₂)＝{t₁，t₂，t₅t₇，t₅t₁₂，t₅t₈，t₆t₁₃，t₆t₁₄，t₆t₁₇，t₁t₅，t₂t₅，t₃t₅，t₄t₅，t₅t₁₁t₅， t₅t₁₂t₁₇t₅，t₅t₇t₁₂，t₆t₁₈t₉t₁₂，t₅t₁₀t₁₂，t₅t₈t₁₂，t₆t₁₃t₁₇，t₆t₁₄t₁₇，t₆t₁₅t₁₇， t₆t₁₆t₁₇}。

(2)使用谓词函数isCover_Prefix，令约简后的T′₁∪T′₂为T′，则

T′＝GREEDY_SET_COVER(T′₁∪T′₂，Req(T′₁∪T′₂)，isCover_Prefix)

＝{t₆t₁₇，t₁t₅，t₂t₅，t₃t₅，t₄t₅，t₅t₁₁t₅，t₅t₁₂t₁₇t₅，t₅t₇t₁₂，t₆t₁₈t₉t₁₂，t₅t₁₀t₁₂，t₅t₈t₁₂， t₆t₁₃t₁₇，t₆t₁₄t₁₇，t₆t₁₅t₁₇，t₆t₁₆t₁₇}。

步骤(3.7)，将步骤(3.6)中得到的测试用例集T′中各转换序列中的转换标识替换为 对应转换中的输入操作，得到最终的测试用例集：

T＝{b₁a₃，a₂a₁，a₃a₁，b₂a₁，b₃a₁，a₁b₃a₁，a₁a₂a₃a₁，a₁a₁a₂，b₁b₂b₁a₂，a₁b₂a₂，a₁a₃a₂， b₁a₁a₃，b₁a₂a₃，b₁b₁a₃，b₁b₃a₃}。

步骤(4)，按系统所处当时的状态，依次进行系统测试，步骤如下：

步骤(4.1)，系统在线状态为空闲状态q₀。

步骤(4.1.1)，判断输入字符串为A或B。若输入字符串A，执行步骤(4.1.2)，否则执 行步骤(4.1.3)。

步骤(4.1.2)，判断状态转换控制信号是否为a₁/1。若为a₁/1，则转换为发送状态q₁。 否则不发生转换。

步骤(4.1.3)，判断状态转换控制信号是否为b₁/1。若为b₁/1，则转换为接收状态q₂。 否则不发生转换。

步骤(4.2)，系统在线状态为发送状态q₁。

步骤(4.2.1)，判断输入字符串为A或B。若输入字符串A，执行步骤(4.2.2)，否则执 行步骤(4.2.3)。

步骤(4.2.2)，判断状态转换控制信号是否为a₂/1。若为a₂/1，则转换为接收状态q₂。 否则不发生转换。

步骤(4.2.3)，判断状态转换控制信号是否为b₃/1。若为b₃/1，则E₁灯亮，无线传感器 同时转换为空闲状态q₀。否则不发生转换。

步骤(4.3)，系统在线状态为接收状态q₂。

步骤(4.3.1)，判断输入字符串为A或B。若输入字符串A，执行步骤(4.3.2)。若输入 字符串B，执行步骤(4.3.3)。

步骤(4.3.2)，判断状态转换控制信号是否为a₃/1。若为a₃/1，则转换为空闲状态q₀。 否则不发生转换。

步骤(4.3.3)，判断状态转换控制信号是否为b₂/1。若为b₂/1，则E₂灯亮，无线传感器 同时转换为发送状态q₀。否则不发生转换。

步骤(4.4)，接着用步骤(3.7)生成的约简后的测试用例集T中15条测试用例去测试 无线传感器网络系统，若全部测试通过，则表明无线传感器网络系统实现正确。否则，则表 明系统中存在故障。

本发明的效果在于，在保证Wp方法原有测试能力不变的情况下，对Wp方法生成的测 试用例集进行约简，对比在步骤(3.2)中约简前的测试用例集合T″含有37条测试用例，107 个输入操作，而约简后的测试用例集合T含有15条测试用例，42个输入操作，可见本发明 对Wp生成的原始测试用例集约简的效果明显，极大的提高了无线传感器网络系统的实际测 试效率。

附图说明

图1为发明流程示意图。

图2为计算机仿真系统有限状态机模型。

图3为无线传感器网络系统的有限状态机模型。

图4为发送状态运行程序流程图。

图5为接收状态运行程序流程图。

图6为空闲状态运行程序流程图。

具体实施方式

下面结合计算机仿真有限状态机模型对本发明的内容做进一步的详细阐述。

步骤(1)，描述计算机仿真系统有限状态机模型。对于所述的计算机仿真系统有限状态 机模型M₁＝(Q，X，Y，q₀，δ，O)而言，其中，

有限状态集合Q包含：空闲状态、发送状态和接收状态三个状态，分别用q₀，q₁，q₂表 示。其中空闲状态q₀为初始状态。为简便起见，假设计算机仿真系统有限状态机模型与实际 系统具有相同的状态数。

M₁有两种输入符号，分别为控制信号A和控制信号B，即输入字符集X＝{A，B}。

M₁有两种输出符号，分别为二进制的0和1，即输出字符集Y＝{0，1}。

状态转移函数δ包括：

δ(q₀，A)＝q₁，δ(q₀，B)＝q₂，δ(q₁，A)＝q₀，

δ(q₁，B)＝q₂，δ(q₂，A)＝q₁，δ(q₂，B)＝q₀。

其中，δ(q₀，A)＝q₁表示在空闲状态q₀下，输入控制信号A，使计算机仿真系统有限状 态机模型M₁从空闲状态q₀转换到发送状态q₁，其余类推。

输出符号O包括：

O(q₀，A)＝1，O(q₀，B)＝1，O(q₁，A)＝0，

O(q₁，B)＝1，O(q₂，A)＝0，O(q₂，B)＝1。

O(q₂，B)＝1表示接收状态q₂下，输入控制信号B，输出1，其余类推，根据所述的有 限状态机模型M₁六元组得到所述计算机仿真系统有限状态机模型。

步骤(2)，由Wp方法得到计算机仿真系统有限状态机模型M₁测试用例约简所需要的 集合：

转换覆盖集P＝{ε，A，AA，AB，B，BA，BB}。

状态覆盖集S＝{ε，A，AB}。

特征集W＝{A，AA}。

等价特征集W₀＝{A}、W₁＝{A，AA}、W₂＝{A，AA}。

测试用例子集T₁＝{A，AA，AAA，ABA，ABAA}。

测试用例子集T₂＝{AAA，BA，BAA，BAAA，BBA}。

约简前的测试用例集合：

T″＝T₁∪T₂＝{A，AA，AAA，ABA，ABAA，BA，BAA，BAAA，BBA}。

由此根据约简前的测试用例集合T″得出约简前的测试方案，约简前测试方案共包括9 条测试用例，如下表3所示：

表3

步骤(3)，对计算机仿真系统有限状态机模型M₁的各个转换设置唯一的转换标识，设 定以下转换与转换标识的对应关系：

转换(q₀，q₁，A/1)的转换标识为t₁，转换(q₀，q₂，B/1)的转换标识为t₂。

转换(q₁，q₀，A/0)的转换标识为t₃，转换(q₁，q₂，B/1)的转换标识为t₄。

转换(q₂，q₁，A/0)的转换标识为t₅，转换(q₂，q₀，B/1)的转换标识为t₆。

将步骤(1.2)中得到的每个集合转换成由转换标识构成的对应集合。其中，

$T_1^{\mathrm{id}}=\{t_1,t_1{t}_3,t_1{t}_3{t}_1,t_1{t}_4{t}_5,t_1{t}_4{t}_5{t}_3\}.$

$T_2^{\mathrm{id}}=\{t_1{t}_3{t}_1,t_2{t}_5,t_2{t}_5{t}_3,t_2{t}_5{t}_3{t}_1\}.$

S^id＝{ε，t₁，t₁t₄}。

P^id＝{ε，t₁，t₁t₃，t₁t₄，t₂，t₂t₅，t₂t₆}。

R^id＝{t₁t₃，t₂，t₂t₅，t₂t₆}。

$W_0^{\mathrm{id}}\left(q_0\right)=\left\{t_1\right\},W_1^{\mathrm{id}}\left(q_1\right)=\{t_3,t_3{t}_1\},W_2^{\mathrm{id}}\left(q_2\right)=\{t_5,t_5{t}_3\}.$

步骤(4)，对集合进行约简。

(1)构造集合的覆盖需求集则

Req(T₁)＝{t₁，t₁t₃，t₁t₃t₁，t₁t₄t₅，t₁t₄t₅t₃}。

(2)使用谓词函数isCover_Prefix，令约简后的为T′₁，则

$\left(\begin{array}{c}{T}_1^{\prime }=\mathrm{GREEDY}\_\mathrm{SET}\_\mathrm{COVER}(T_1^{\mathrm{id}},\mathrm{Req}\left(T_1\right),\mathrm{isCover}\_\mathrm{Prefix})\\ =\{t_1{t}_3{t}_1,t_1{t}_4{t}_5{t}_3\}\end{array}\right)$

步骤(5)，对集合进行约简。

(1)构造集合的覆盖需求集的计算如下：

$\left(\begin{array}{c}\mathrm{Req}\left(T_2\right)=\{t_3·W_0^{\mathrm{id}}\left(q_0\right)\cup t_2·W_2^{\mathrm{id}}\left(q_2\right)\cup t_5·W_1^{\mathrm{id}}\left(q_1\right)\cup t_6·W_0^{\mathrm{id}}\left(q_0\right)\\ =\left\{\right\{t_3{t}_1\}\cup \{t_2{t}_5,t_2{t}_5{t}_3\}\cup \{t_5{t}_3,t_5{t}_3{t}_1\}\cup \{t_6{t}_1\left\}\right\}\\ =\{t_3{t}_1,t_2{t}_5,t_2{t}_5{t}_3,t_5{t}_3,t_5{t}_3{t}_1,t_6{t}_1\},\end{array}\right)$

(2)使用谓词函数isCover_SubSeq，令约简后的为T′₂，则

$\left(\begin{array}{c}{T}_2^{\prime }=\mathrm{GREEDY}\_\mathrm{SET}\_\mathrm{COVER}(T_2^{\mathrm{id}},\mathrm{Req}\left(T_2\right),\mathrm{isCover}\_\mathrm{SubSeq})\\ =\{t_2{t}_5{t}_3{t}_1,t_2{t}_6{t}_1\},\end{array}\right)$

步骤(6)，对T′₁∪T′₂进行约简。

(1)构造集合T′₁∪T′₂的覆盖需求集Req(T′₁∪T′₂)＝T′₁∪T′₂，则

Req(T′₁∪T′₂)＝{t₁t₃t₁，t₁t₄t₅t₃，t₂t₅t₃t₁，t₂t₆t₁}，

(2)使用谓词函数isCov_Prefix，令约简后的T′₁∪T′₂为T′，则

T′＝GREEDY_SET_COVER(T′₁∪T′₂，Req(T′₁∪T′₂)，isCover_Prefix)

＝{t₁t₃t₁，t₁t₄t₅t₃，t₂t₅t₃t₁，t₂t₆t₁}，

步骤(7)，将步骤(6)中得到的测试用例集T′中各转换序列中的转换标识替换为对应 转换的输入字符，得到最终的测试用例集，

T＝{AAA，ABAA，BAAA，BBA}。

由此根据约简后的测试用例集合T，得出约简后的测试方案共包括4条测试用例，如下 表4所示：

表4

对比表3所示的约简前测试方案和表4所示的约简后的测试方案能够得出如下结果，如 下表5所示：

表5

  测试用例数量 测试用例总长度 约简前 9 25 约简后 4 14

通过对比发现，在本实施方式的计算机仿真系统有限状态机模型M₁测试中，测试用例 序列数量由约简前的9条，降低至约简后的4条。同时测试用例序列中输入操作数由约简前 的25次操作，降低至约简后的14次操作，约简效果明显，同时本发明会保持Wp方法原有 的检测能力，将本发明用于无线传感器网络系统测试，使实际工作效率得到了极大地提高。