作者：江敏  張毅

    無線通信測試是整個無線通信工作中一個很重要的環節。

    本文以藍牙無線通信為例，用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