基于FSM模型的無(wú)線傳感器網(wǎng)絡(luò)數(shù)據(jù)收集協(xié)議測(cè)試

劉層層　楊紅麗

摘 要：在對(duì)無(wú)線傳感器網(wǎng)絡(luò)數(shù)據(jù)收集協(xié)議進(jìn)行一致性測(cè)試時(shí)，生成的測(cè)試序列往往不夠簡(jiǎn)捷高效。因此，提出了基于FSM模型的無(wú)線傳感器網(wǎng)絡(luò)數(shù)據(jù)收集協(xié)議測(cè)試方法。采用FSM模型描述數(shù)據(jù)收集協(xié)議規(guī)范，在FSM模型的基礎(chǔ)上利用UIO算法生成測(cè)試序列。研究發(fā)現(xiàn)：UIO算法生成的測(cè)試序列較長(zhǎng)，現(xiàn)有基于UIO的改進(jìn)算法生成的測(cè)試序列較短，但不適用于所有協(xié)議，為此進(jìn)行了優(yōu)化，使得優(yōu)化后的算法具有更好的適用性。為了闡明方法的有效性，對(duì)一個(gè)工業(yè)界無(wú)線抄表數(shù)據(jù)收集協(xié)議WM2RP進(jìn)行建模與測(cè)試序列生成，并搭建測(cè)試環(huán)境進(jìn)行了實(shí)際測(cè)試。

關(guān)鍵詞：無(wú)線傳感器網(wǎng)絡(luò)；數(shù)據(jù)收集協(xié)議；FSM模型；測(cè)試序列生成；UIO算法

DOI：10.11907/rjdk.171437

中圖分類號(hào)：TP306 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：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 引言

無(wú)線傳感器網(wǎng)絡(luò)廣泛應(yīng)用于各個(gè)領(lǐng)域的數(shù)據(jù)收集系統(tǒng)，設(shè)計(jì)并實(shí)現(xiàn)可靠的數(shù)據(jù)收集協(xié)議以保證此類系統(tǒng)的正常運(yùn)作成為亟待解決的問題之一[1]。協(xié)議測(cè)試是檢驗(yàn)協(xié)議可靠性與正確性的一種有效方式，主要包括一致性測(cè)試、互操作性測(cè)試、可靠性測(cè)試、健壯性測(cè)試。其中一致性測(cè)試是協(xié)議測(cè)試的基礎(chǔ)，作用是檢測(cè)協(xié)議的實(shí)現(xiàn)是否符合協(xié)議規(guī)范。測(cè)試序列是一致性測(cè)試中的核心部分，好的測(cè)試序列可以增加準(zhǔn)確性，提高一致性測(cè)試效率[2]。如何生成合適的測(cè)試序列，是一致性測(cè)試中需要解決的關(guān)鍵問題。測(cè)試序列可以從協(xié)議模型中得到，常見的協(xié)議抽象模型主要有Petri網(wǎng)、進(jìn)程代數(shù)、有限狀態(tài)機(jī)等。其中應(yīng)用最廣泛的是有限狀態(tài)機(jī)FSM模型[3]，很多測(cè)試序列的生成算法都在其基礎(chǔ)上進(jìn)行處理的[4，5]。

基于FSM模型的測(cè)試序列生成方法有很多，應(yīng)用最廣泛的是UIO方法[6，7]。目前基于UIO的測(cè)試序列生成方法已有很多研究成果[8-10]。雖然UIO方法已經(jīng)被應(yīng)用于一致性測(cè)試序列的生成[11，12]，然而，相關(guān)研究工作仍處于理論探討階段，在工業(yè)界還未得到廣泛應(yīng)用。

本文研究UIO方法在企業(yè)真實(shí)數(shù)據(jù)收集協(xié)議測(cè)試中的應(yīng)用，對(duì)文獻(xiàn)[10]中基于UIO的改進(jìn)算法進(jìn)行優(yōu)化，使得優(yōu)化后的算法具有更好的適用性。

1 WM2RP數(shù)據(jù)收集協(xié)議概述

WM2RP數(shù)據(jù)收集協(xié)議已被成功應(yīng)用于無(wú)線抄表系統(tǒng)，用于小區(qū)居民燃?xì)獗頂?shù)據(jù)的采集。使用WM2RP協(xié)議的小區(qū)抄表系統(tǒng)體系結(jié)構(gòu)見圖1，協(xié)議中節(jié)點(diǎn)分為四類。

（1）服務(wù)器。服務(wù)器通常部署在燃?xì)夤?，作為遠(yuǎn)程管理中心，通過GPRS方式與集中器通信，收集集中器發(fā)送的數(shù)據(jù)。由于它與集中器的通信不屬于WSNs路由協(xié)議范疇，因此本文不將其作為研究?jī)?nèi)容。

（2）集中器。集中器也稱為基站，一個(gè)小區(qū)只有一個(gè)，采集整個(gè)小區(qū)的數(shù)據(jù)，并且將數(shù)據(jù)通過GPRS傳輸給遠(yuǎn)程服務(wù)器。

（3）中繼器。表節(jié)點(diǎn)的無(wú)線傳播范圍有限，如果表節(jié)點(diǎn)與集中器的距離超過了表節(jié)點(diǎn)的傳播距離，就需要中繼器輔助傳遞信號(hào)到集中器。中繼器與表節(jié)點(diǎn)相同，但是中繼器只有路由的功能，其安裝位置隨意。

（4）表節(jié)點(diǎn)。表節(jié)點(diǎn)安裝在用戶的廚房或其它方便的地方，表節(jié)點(diǎn)具有監(jiān)測(cè)燃?xì)馐褂昧?、路由的功能?/p>

在對(duì)用戶燃?xì)獗磉M(jìn)行數(shù)據(jù)收集時(shí)，系統(tǒng)管理人員要先在服務(wù)器上進(jìn)行一定的設(shè)置，然后服務(wù)器通過GPRS方式與基站進(jìn)行通信，發(fā)送抄表命令。基站收到抄表命令后，開始收集數(shù)據(jù)并向第一級(jí)表節(jié)點(diǎn)發(fā)送命令。該命令沿著協(xié)議鏈路從第一級(jí)表節(jié)點(diǎn)一直傳送到最后一級(jí)表節(jié)點(diǎn)（葉子節(jié)點(diǎn)），葉子節(jié)點(diǎn)檢測(cè)到自己是最后一級(jí)表節(jié)點(diǎn)，將收集到的數(shù)據(jù)向上一級(jí)表節(jié)點(diǎn)返回。數(shù)據(jù)以相反的方向沿著協(xié)議鏈路從葉子節(jié)點(diǎn)一直返回到第一級(jí)表節(jié)點(diǎn)，再由第一級(jí)表節(jié)點(diǎn)將數(shù)據(jù)返回給基站，最后基站通過 GPRS 方式將數(shù)據(jù)返回給服務(wù)器[1]。endprint

2 UIO方法的不足及優(yōu)化

由于UIO方法是基于有限狀態(tài)機(jī)FSM模型的測(cè)試序列生成方法，因此首先介紹FSM模型，然后介紹UIO序列生成方法及UIO方法的不足，最后介紹優(yōu)化后的測(cè)試序列生成方法。

2.1 FSM模型

有限狀態(tài)機(jī)模型FSM主要用于表示有限多個(gè)狀態(tài)與這些狀態(tài)之間的輸入輸出情況，一個(gè)確定的有限狀態(tài)機(jī)是一種初始化、確定的米利機(jī)（Mealy machine），它在形式上被定義為一個(gè)6元組M=（S，I，O，δ，λ，s0）[3]，其中：S={s0，s1，…，sn}是狀態(tài)的有限非空集合；I={i0，i1，…，im}是輸入符號(hào)的有限非空集合；O={o0，o1，…，or}是輸出符號(hào)的有限非空集合；δ：S× I →S 是狀態(tài)遷移函數(shù)；λ∶S× I →O 是輸出函數(shù)；s0∈S 是初始狀態(tài)。

可以用有向圖G=（V，E）表示FSM。其中V={v1，v2，…，vn}是非空頂點(diǎn)集合，與FSM的有限非空狀態(tài)集合S相對(duì)應(yīng)；E= {（vi，vk；il/om）|vi，vk∈V，il∈I，om∈O}是有向邊的集合，與FSM遷移的集合相對(duì)應(yīng)；（vi，vk；il/om）∈E表示FSM上一條從狀態(tài)vi 到狀態(tài)vk 的遷移，il和om 分別是這條遷移上的輸入與輸出事件。圖2是一個(gè)FSM的有向圖。

2.2 UIO序列生成方法

UIO方法的思想是，首先為FSM的每一個(gè)狀態(tài)生成一個(gè)識(shí)別序列，該識(shí)別序列可以區(qū)分每一個(gè)狀態(tài)，稱之為唯一輸入輸出UIO（Unique Input/Output）序列，然后根據(jù)該識(shí)別序列構(gòu)造測(cè)試序列。UIO序列生成方法如下：

（1）建立所有的邊與輸入輸出集的關(guān)系。

（2）求出FSM模型中每個(gè)狀態(tài)長(zhǎng)度為1的輸入輸出序列。

（3）檢查它們的唯一性。若唯一，此狀態(tài)的UIO序列就找到了；若不唯一，則繼續(xù)找此狀態(tài)的UIO序列，轉(zhuǎn)（4）。

（4）對(duì)還沒找到UIO序列的狀態(tài)，根據(jù)其長(zhǎng)度為K的輸入輸出序列，繼續(xù)求出長(zhǎng)度為K+1的輸入輸出序列，檢查它們是否唯一，直到每個(gè)狀態(tài)都找到UIO序列或者長(zhǎng)度超過2n2，n代表模型中狀態(tài)的個(gè)數(shù)。以圖2的FSM為例，表1為圖2所示FSM各個(gè)狀態(tài)的UIO序列。

2.3 UIO方法的不足

UIO方法中每測(cè)試一個(gè)遷移之前，都需要用重置信息將被測(cè)設(shè)備置于初始狀態(tài)，這樣會(huì)產(chǎn)生一些冗余。另外，F(xiàn)SM中每個(gè)狀態(tài)可能有多個(gè)最短的UIO序列，UIO方法中只要找到一個(gè)符合要求的，就繼續(xù)求另一狀態(tài)的UIO序列，這樣隨機(jī)得到的UIO序列可能只是局部最優(yōu)解，而不是整體最優(yōu)解，造成測(cè)試序列過長(zhǎng)。

文獻(xiàn)[10]根據(jù)上述不足對(duì)算法進(jìn)行了改進(jìn)，改進(jìn)后的算法縮短了測(cè)試序列的長(zhǎng)度，但不適用于本文研究的WM2RP協(xié)議。其中，生成偽圖后只檢查偽圖的對(duì)稱性，若對(duì)稱則不再進(jìn)行擴(kuò)展，然而，對(duì)稱的偽圖不一定存在歐拉回路，對(duì)稱且強(qiáng)連通的偽圖則一定存在一條歐拉回路。

2.4 優(yōu)化后的測(cè)試序列生成方法

根據(jù)上述不足，在文獻(xiàn)[10]算法基礎(chǔ)上進(jìn)行優(yōu)化，除了對(duì)稱性還需要檢查偽圖的強(qiáng)連通性。優(yōu)化后的測(cè)試序列生成算法步驟如下：

（1）首先得到FSM模型中各個(gè)狀態(tài)的所有最短UIO序列。利用上文UIO序列生成方法，求出每個(gè)狀態(tài)的所有最短UIO序列。

（2）設(shè)IUT的FSM模型用有向圖G=（V，E）表示，其中V={v1，v2，...，vn}為FSM的狀態(tài)集合，E={（vi，vj；ik/om）|vi，vj∈V，ik∈I，om∈O}為FSM的遷移集合。對(duì)于每個(gè)狀態(tài)遷移（vi，vj；ik/om）都構(gòu)造一個(gè)相應(yīng)的偽遷移，即測(cè)試序列e（vi，vj；ik/om）={ik/om，UIO（vj）}，其中vi為該測(cè)試序列的起始狀態(tài)，vj為執(zhí)行ik/om后的狀態(tài)，UIO（vj）為利用UIO序列生成方法所找到的狀態(tài)vj的UIO序列，vl為施加特征序列UIO（vj）后的結(jié)束狀態(tài)，也是該測(cè)試序列的終止?fàn)顟B(tài)。即對(duì)G圖中的每一個(gè)狀態(tài)遷移（vi，vj；ik/om）生成一個(gè)對(duì)應(yīng)G圖中的偽遷移e（vi，vj，vl；ik/om）={ik/om，UIO（vj）}。偽圖G=（ V，E），其中V不變，為FSM的狀態(tài)集合，E為偽遷移的集合，E={ e（vi，vj，vl；ik/om） |vi，vj，vl∈V，ik∈I，om∈O }。利用每個(gè)狀態(tài)的多個(gè)UIO序列，在為每一個(gè)遷移生成偽遷移時(shí)決定采用哪一個(gè)UIO序列，從而使得生成的偽圖在進(jìn)行對(duì)稱擴(kuò)展前盡可能地連通且對(duì)稱。

在圖論中，歐拉遍歷是指正好經(jīng)過圖中每條邊一次的一個(gè)序列，歐拉回路是指從一個(gè)頂點(diǎn)出發(fā)最終又回到此頂點(diǎn)的歐拉遍歷。相關(guān)定理如下：

定理1[13] 一個(gè)有向圖G存在一條歐拉回路的充要條件是圖G強(qiáng)連通且對(duì)稱。

（3）檢查G′是否對(duì)稱。若G′仍然不對(duì)稱，則對(duì)其進(jìn)行對(duì)稱擴(kuò)展，添加若干條取自于E的邊，使G′對(duì)稱。

（4）檢查G′是否強(qiáng)連通。如果不是強(qiáng)連通，則對(duì)其進(jìn)行擴(kuò)展，添加若干條取自E的邊，使G′變成歐拉圖G*。

（5）從G*圖中構(gòu)造以初始狀態(tài)為起點(diǎn)的歐拉遍歷，所得到的序列即為最后生成的測(cè)試序列。

3 WM2RP協(xié)議建模

根據(jù)上文對(duì)WM2RP協(xié)議的概述，筆者依據(jù)規(guī)范中不同類型節(jié)點(diǎn)的行為對(duì)各類節(jié)點(diǎn)建立FSM模型，其中中繼器的行為除了不能收集數(shù)據(jù)以外，電腦與中間表節(jié)點(diǎn)的行為基本相同。將中繼器與中間表節(jié)點(diǎn)作為同一類節(jié)點(diǎn)進(jìn)行建模，最終建立了3種類型的模型：基站模型（Base Station Model，Mbs）、中間節(jié)點(diǎn)模型（Inter Node Model，Min）與葉子節(jié)點(diǎn)模型（Leaf Node Model，Mln）。

3.1 基站FSM模型

根據(jù)協(xié)議中基站的行為抽象出FSM模型（見圖3）：Mbs=（S，I，O，δ，λ，s0）endprint

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

（2） 式（2）中：s0為初始狀態(tài)，此時(shí)基站正等待被喚醒或者初始化；s1為等待接收下一級(jí)節(jié)點(diǎn)的ACK確認(rèn)回復(fù)狀態(tài)，此時(shí)基站已收到服務(wù)器端發(fā)來(lái)的抄表命令，并向下一級(jí)節(jié)點(diǎn)發(fā)送了抄表命令，正在等待接收下一級(jí)節(jié)點(diǎn)的ACK確認(rèn)回復(fù)；s2為等待接收下一級(jí)節(jié)點(diǎn)發(fā)送的數(shù)據(jù)狀態(tài)，此時(shí)基站已經(jīng)收到了下一級(jí)節(jié)點(diǎn)發(fā)送的ACK確認(rèn)回復(fù)，正在等待接收下一級(jí)節(jié)點(diǎn)發(fā)送過來(lái)的數(shù)據(jù)。I={i0，i1，i2}

（3） 式（3）中：i0為收到服務(wù)器端發(fā)送過來(lái)的抄表命令；i1為收到下一級(jí)節(jié)點(diǎn)發(fā)送過來(lái)的ACK確認(rèn)回復(fù)；i2為收到下一級(jí)節(jié)點(diǎn)發(fā)送過來(lái)的數(shù)據(jù)。O={o0，o1}

（4） 式（4）中：o0為向下一級(jí)節(jié)點(diǎn)發(fā)送抄表命令；o1為回復(fù)收到數(shù)據(jù)的ACK，并將數(shù)據(jù)發(fā)送給服務(wù)器端。δ∶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為初始狀態(tài)。

被測(cè)設(shè)備作為基站工作時(shí)會(huì)在以上3個(gè)狀態(tài)之間進(jìn)行轉(zhuǎn)換，共有3個(gè)狀態(tài)轉(zhuǎn)移，每個(gè)狀態(tài)轉(zhuǎn)移都有相應(yīng)的觸發(fā)條件或輸入輸出。說明如下：①T0（i0/o0）：服務(wù)器端通過GPRS向被測(cè)設(shè)備發(fā)送抄表命令，被測(cè)設(shè)備收到抄表命令，同時(shí)向下一級(jí)節(jié)點(diǎn)發(fā)送抄表命令，且消息中應(yīng)帶有下一級(jí)節(jié)點(diǎn)的地址，此時(shí)被測(cè)設(shè)備將由初始狀態(tài)，轉(zhuǎn)換為等待下一級(jí)節(jié)點(diǎn)發(fā)送收到抄表命令的ACK確認(rèn)回復(fù)狀態(tài)；②T1（i1/-）：下一級(jí)節(jié)點(diǎn)向被測(cè)設(shè)備發(fā)送收到抄表命令的ACK確認(rèn)回復(fù)，被測(cè)設(shè)備收到回復(fù)，此時(shí)被測(cè)設(shè)備將由等待接收下一級(jí)節(jié)點(diǎn)的ACK確認(rèn)回復(fù)狀態(tài)，轉(zhuǎn)換為等待接收下一級(jí)節(jié)點(diǎn)發(fā)送的數(shù)據(jù)狀態(tài)；③T2（i2/o1）：下一級(jí)節(jié)點(diǎn)將收集到的數(shù)據(jù)發(fā)送給被測(cè)設(shè)備，被測(cè)設(shè)備收到數(shù)據(jù)，向下一級(jí)節(jié)點(diǎn)回復(fù)收到數(shù)據(jù)的ACK，并將收到的數(shù)據(jù)通過GPRS發(fā)送給服務(wù)器端，此時(shí)被測(cè)設(shè)備由等待接收下一級(jí)節(jié)點(diǎn)發(fā)送的數(shù)據(jù)狀態(tài)轉(zhuǎn)換為初始狀態(tài)。

3.2 中間節(jié)點(diǎn)FSM模型

根據(jù)中間節(jié)點(diǎn)抽象出來(lái)的FSM模型為Min=（S，I，O，δ，λ，s0），如圖4所示。

被測(cè)設(shè)備作為中間節(jié)點(diǎn)工作時(shí)會(huì)在以上4個(gè)狀態(tài)之間進(jìn)行轉(zhuǎn)換，共有4個(gè)狀態(tài)轉(zhuǎn)移，每個(gè)狀態(tài)轉(zhuǎn)移都有相應(yīng)的觸發(fā)條件或輸入輸出，說明如下：①T0（i0/o0）：被測(cè)設(shè)備的上一級(jí)節(jié)點(diǎn)向被測(cè)設(shè)備發(fā)送抄表命令，被測(cè)設(shè)備收到抄表命令，向上一級(jí)節(jié)點(diǎn)回復(fù)收到命令的ACK，同時(shí)向下一級(jí)節(jié)點(diǎn)發(fā)送抄表命令，且消息中應(yīng)帶有下一級(jí)節(jié)點(diǎn)的地址，此時(shí)被測(cè)設(shè)備將由初始狀態(tài)，轉(zhuǎn)換為等待下一級(jí)節(jié)點(diǎn)發(fā)送收到抄表命令的ACK確認(rèn)回復(fù)狀態(tài)；②T1（i1/-）：下一級(jí)節(jié)點(diǎn)向被測(cè)設(shè)備發(fā)送收到抄表命令的ACK確認(rèn)回復(fù)，被測(cè)設(shè)備收到回復(fù)，此時(shí)被測(cè)設(shè)備將由等待接收下一級(jí)節(jié)點(diǎn)的ACK確認(rèn)回復(fù)狀態(tài)，轉(zhuǎn)換為收集數(shù)據(jù)并等待接收下一級(jí)節(jié)點(diǎn)發(fā)送數(shù)據(jù)的狀態(tài)；③T2（i2/o1）：下一級(jí)節(jié)點(diǎn)將收集到的數(shù)據(jù)發(fā)送給被測(cè)設(shè)備，被測(cè)設(shè)備收到數(shù)據(jù)，向下一級(jí)節(jié)點(diǎn)回復(fù)收到數(shù)據(jù)的ACK，并將接收到的數(shù)據(jù)與自己收集到的數(shù)據(jù)融合在一起，發(fā)送給上一級(jí)節(jié)點(diǎn)，此時(shí)被測(cè)設(shè)備由等待接收下一級(jí)節(jié)點(diǎn)發(fā)送數(shù)據(jù)的狀態(tài)，轉(zhuǎn)換為等待接收上一級(jí)節(jié)點(diǎn)收到數(shù)據(jù)的ACK確認(rèn)回復(fù)狀態(tài)；④T3（i3/-）：上一級(jí)節(jié)點(diǎn)收到被測(cè)設(shè)備發(fā)送過來(lái)的數(shù)據(jù)，向被測(cè)設(shè)備回復(fù)收到數(shù)據(jù)的ACK，被測(cè)設(shè)備收到回復(fù)，同時(shí)由等待接收上一級(jí)節(jié)點(diǎn)收到數(shù)據(jù)的ACK確認(rèn)回復(fù)狀態(tài)，轉(zhuǎn)換為初始狀態(tài)。

3.3 葉子節(jié)點(diǎn)FSM模型

根據(jù)葉子節(jié)點(diǎn)抽象出來(lái)的FSM模型為Mln=（S，I，O，δ，λ，s0），如圖5所示。

被測(cè)設(shè)備作為葉子節(jié)點(diǎn)工作時(shí)會(huì)在圖5所示3個(gè)狀態(tài)之間進(jìn)行轉(zhuǎn)換，共有3個(gè)狀態(tài)轉(zhuǎn)移，每個(gè)狀態(tài)轉(zhuǎn)移都有相應(yīng)的觸發(fā)條件或輸入輸出，說明如下：①T0（i0/o0）：被測(cè)設(shè)備的上一級(jí)鄰節(jié)點(diǎn)向被測(cè)設(shè)備發(fā)送抄表命令，被測(cè)設(shè)備收到抄表命令并向上一級(jí)鄰節(jié)點(diǎn)回復(fù)收到命令的ACK，此時(shí)被測(cè)設(shè)備將由初始狀態(tài)，轉(zhuǎn)換為收集數(shù)據(jù)并等待向上一級(jí)節(jié)點(diǎn)發(fā)送數(shù)據(jù)狀態(tài)；②T1（-/o1）：被測(cè)設(shè)備將收集到的數(shù)據(jù)發(fā)送給上一級(jí)節(jié)點(diǎn)，此時(shí)被測(cè)設(shè)備將由收集數(shù)據(jù)并等待向上一級(jí)節(jié)點(diǎn)發(fā)送數(shù)據(jù)狀態(tài)，轉(zhuǎn)換為向上一級(jí)節(jié)點(diǎn)發(fā)送數(shù)據(jù)完成狀態(tài)；③T2（i1/-）：上一級(jí)節(jié)點(diǎn)收到被測(cè)設(shè)備發(fā)送的數(shù)據(jù)，向被測(cè)設(shè)備回復(fù)收到數(shù)據(jù)的ACK，被測(cè)設(shè)備收到回復(fù)，由向上一級(jí)節(jié)點(diǎn)發(fā)送數(shù)據(jù)完成狀態(tài)，轉(zhuǎn)換為初始狀態(tài)。

4 測(cè)試序列生成

上文已經(jīng)建立了WM2RP協(xié)議各類型節(jié)點(diǎn)的FSM模型，根據(jù)優(yōu)化后的測(cè)試序列生成算法，可以得到WM2RP協(xié)議各類型節(jié)點(diǎn)的測(cè)試序列。步驟如下：

（1）首先得到WM2RP協(xié)議各類型節(jié)點(diǎn)的FSM模型中各個(gè)狀態(tài)的所有最短UIO序列。表2為WM2RP協(xié)議FSM模型各個(gè)狀態(tài)的UIO序列。

（2）利用各個(gè)狀態(tài)的多UIO序列，為每一個(gè)遷移生成偽遷移。由表2可知，WM2RP協(xié)議中FSM模型的各個(gè)狀態(tài)均只有一個(gè)UIO序列，因此不需要較多UIO的 序列。表3為WM2RP協(xié)議FSM模型中各個(gè)遷移的偽遷移。

以中間節(jié)點(diǎn)的FSM模型為例，根據(jù)表3中的偽遷移，可得到中間節(jié)點(diǎn)的偽圖G′，圖6為中間節(jié)點(diǎn)的偽圖G′。

（3）檢查中間節(jié)點(diǎn)的偽圖G′是否對(duì)稱。由圖6可以看出，G′是對(duì)稱的，因此不需要進(jìn)行對(duì)稱擴(kuò)展。

（4）檢查中間節(jié)點(diǎn)的偽圖G′是否強(qiáng)連通。由圖6可以看出，G′不是強(qiáng)連通的，因此需要對(duì)其進(jìn)行擴(kuò)展，添加若干條取自于圖4的邊。圖7為圖6擴(kuò)展后生成的中間節(jié)點(diǎn)的歐拉圖G*。圖7中虛線表示取自于圖4的邊，其上的數(shù)值表示該邊在對(duì)稱擴(kuò)展中用到的次數(shù)。

（5）從圖7中間節(jié)點(diǎn)模型的歐拉圖G*中構(gòu)造以初始狀態(tài)S0為起點(diǎn)的歐拉遍歷，所得到的序列即為中間節(jié)點(diǎn)的測(cè)試序列。中間節(jié)點(diǎn)的最終測(cè)試序列如下：i0/o0，i1/-，i2/o1，i3/-，i0/o0，i1/-，i2/o1，i3/-，i0/o0，i1/-，i2/o1，i3/-?？梢钥闯觯瑴y(cè)試序列的長(zhǎng)度為12。endprint

同樣地，根據(jù)該算法可以生成基站測(cè)試序列如下：i0/o0，i1/-，i2/o1，i0/o0，i1/-，i2/o1。測(cè)試序列的長(zhǎng)度為6。葉子節(jié)點(diǎn)測(cè)試序列如下：i0/o0，-/o1，i1/-，i0/o0，-/o1，i1/-。測(cè)試序列的長(zhǎng)度為6。

5 測(cè)試執(zhí)行

5.1 測(cè)試平臺(tái)搭建

校內(nèi)實(shí)驗(yàn)室不具備企業(yè)對(duì)路由協(xié)議進(jìn)行實(shí)際測(cè)試所需的硬件設(shè)備，為了能夠利用生成的測(cè)試用例對(duì)協(xié)議的具體實(shí)現(xiàn)進(jìn)行測(cè)試，在合作公司已有燃?xì)獬硐到y(tǒng)的基礎(chǔ)上開發(fā)了一個(gè)測(cè)試程序，該測(cè)試程序包括集中器程序與表節(jié)點(diǎn)程序兩個(gè)部分。

在搭建的測(cè)試環(huán)境中，公司燃?xì)獬硐到y(tǒng)就是服務(wù)器，它作為遠(yuǎn)程管理中心，可以給集中器發(fā)送抄表命令，集中器程序可以與服務(wù)器以及表節(jié)點(diǎn)程序進(jìn)行通信。集中器程序通過設(shè)置服務(wù)器地址與服務(wù)器端口號(hào)，與服務(wù)器建立連接，表節(jié)點(diǎn)程序通過設(shè)置表編號(hào)與端口號(hào)，與集中器或其它表節(jié)點(diǎn)建立連接。每一個(gè)表節(jié)點(diǎn)程序是一個(gè)進(jìn)程，需要多少個(gè)表節(jié)點(diǎn)，就要打開多少個(gè)表節(jié)點(diǎn)程序。

5.2 測(cè)試執(zhí)行與結(jié)果分析

上文中，已測(cè)試環(huán)境已搭建完成并且建立了連接，接下來(lái)將登錄燃?xì)庾詣?dòng)抄表系統(tǒng)，進(jìn)入遠(yuǎn)程民用抄表界面。點(diǎn)擊發(fā)送命令，服務(wù)器開始向集中器發(fā)送抄表命令進(jìn)行數(shù)據(jù)收集。

將生成測(cè)試序列中的輸入應(yīng)用到協(xié)議實(shí)現(xiàn)，會(huì)產(chǎn)生一個(gè)實(shí)際輸出，與測(cè)試序列中預(yù)期的輸出相比，看是否一致。上文也得到了各類節(jié)點(diǎn)的測(cè)試序列，以基站為例，由基站模型得到的輸入序列為：i0，i1，i2，i0，i1，i2 ，對(duì)應(yīng)的預(yù)期輸出序列為：o0，-，o1，o0，-，o1，由測(cè)試結(jié)果對(duì)應(yīng)相應(yīng)的序列可以得到實(shí)際輸出的序列為：o0，-，o1，o0，-，o1?；镜念A(yù)期輸出與實(shí)際輸出一致，證明基站的實(shí)現(xiàn)與規(guī)范是一致的。

用相同的方法對(duì)中間節(jié)點(diǎn)程序與葉子節(jié)點(diǎn)程序進(jìn)行測(cè)試，它們的實(shí)現(xiàn)和規(guī)范也是一致的。表4為各類型節(jié)點(diǎn)程序的測(cè)試結(jié)果分析。

6 結(jié)語(yǔ)

本文將UIO方法應(yīng)用于無(wú)線傳感器網(wǎng)絡(luò)數(shù)據(jù)收集協(xié)議WM2RP的一致性測(cè)試，并在應(yīng)用過程中對(duì)現(xiàn)有基于UIO的算法進(jìn)行了優(yōu)化，使之具有更好的適用性。

參考文獻(xiàn)：

[1] 王非，楊紅麗，秦勝潮，等.基于時(shí)間自動(dòng)機(jī)模型的無(wú)線傳感器網(wǎng)絡(luò)數(shù)據(jù)收集協(xié)議測(cè)試用例生成[J].計(jì)算機(jī)應(yīng)用，2015，35（4）：1164-1168.

[2] 李強(qiáng)，余祥，齊建業(yè)，等.協(xié)議一致性測(cè)試研究進(jìn)展[J].西南科技大學(xué)學(xué)報(bào)，2013，28（4）：85-92.

[3] 蔣宗禮.形式語(yǔ)言與自動(dòng)機(jī)理論教學(xué)參考書[M].北京：清華大學(xué)出版社，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] 劉攀，繆淮扣，曾紅衛(wèi)，等.基于FSM的測(cè)試?yán)碚摗⒎椒霸u(píng)估[J].計(jì)算機(jī)學(xué)報(bào)，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] 黎中文，張來(lái)順，何焱.基于FSM的測(cè)試序列生成方法研究[J].計(jì)算機(jī)應(yīng)用研究，2011，28（9）：3368-3371.

[10] 陳濤，潘雪增，陳健，等.基于FSM的協(xié)議相符性測(cè)試序列生成算法研究[J].計(jì)算機(jī)工程與應(yīng)用，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鄰居發(fā)現(xiàn)協(xié)議的一致性測(cè)試序列生成[J].信號(hào)處理，2013，29（12）：1670-1676.

（責(zé)任編輯：何 麗）endprint