基于FSM模型的無線傳感器網絡數據收集協議測試

劉層層　楊紅麗

摘 要：在對無線傳感器網絡數據收集協議進行一致性測試時，生成的測試序列往往不夠簡捷高效。因此，提出了基于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