作者：江敏  張毅

    無線通信測試是整個無線通信工作中一個很重要的環(huán)節(jié)。

    本文以藍(lán)牙無線通信為例，用EFSM模型描述了其電話控制協(xié)議（TCS）。為了使測試?yán)ㄙM最小，本文采用了有效的算法生成最優(yōu)郵路，在此基礎(chǔ)上簡要介紹了測試?yán)拿枋黾皥?zhí)行。該項測試技術(shù)優(yōu)化了測試路由，因而，提高了一致性測試的效率。

    一、引言

    無線通信測試是無線通信項目工作中的其中一個重要環(huán)節(jié)。測試的目的就是通過各種相關(guān)手段對通信系統(tǒng)的功能進(jìn)行檢測和校驗，盡可能發(fā)現(xiàn)其中存在的問題，以便于在下一步工作中糾正錯誤，逐步完善系統(tǒng)功能。

    在無線測試的過程中，一致性測試是測試工作中一項非常重要的測試內(nèi)容。協(xié)議一致性測試在驗證協(xié)議實現(xiàn)的正確性，以及保證不同廠商開發(fā)的設(shè)備互連互通方面有著重要的作用。一致性測試是一種黑盒測試，IUT（被測實現(xiàn)）的源碼是未知的，測試者僅能控制和觀察IUT的某些接口；一致性測試的基本方法就是通過觀察協(xié)議規(guī)范和被測實現(xiàn)的輸入輸出來判定二者是否一致。根據(jù)協(xié)議規(guī)范生成一系列的測試?yán)⒃跍y試系統(tǒng)上運行這些測試?yán)噲D發(fā)現(xiàn)錯誤或者驗證其正確性。

    眾所周知，手工測試生成花費的代價過于昂貴，冗長的重復(fù)性工作，相當(dāng)于30%協(xié)議實現(xiàn)的時間，并且通常不能保證錯誤覆蓋[1]。為此，本文采用了有效的算法生成最優(yōu)測試路由，這樣可以大大減少測試錯誤。同時，可以簡化繁雜的測試工作，提高了一致性測試研究和實現(xiàn)的效率。不僅如此，其中所涉及的算法也有助于測試規(guī)程（或測試標(biāo)準(zhǔn)）的編寫。該項測試集的生成技術(shù)可以應(yīng)用于各種通信協(xié)議的一致性測試中。

    二、引理

    這樣，就可以把TCS的EFSM狀態(tài)用圖1表示。

    圖1  EFSM狀態(tài)圖

    三、測試序列算法

    對于一致性測試而言，我們所關(guān)心的問題就是協(xié)議規(guī)范M與協(xié)議實現(xiàn)Mˊ是否一致。

   （2）驗證所有變遷的算法[2]對于EFSM的描述圖G而言，根據(jù)基本假設(shè)可知，生成圖G的一條有向郵路，就可以驗證協(xié)議機(jī)的所有變遷及配置。因為G是最小的，沒有等價的配置節(jié)點，所以，回路的輸入序列可以作為各個狀態(tài)的UIO序列。這樣根據(jù)中國郵遞員問題[4]的求解方法得到下列最優(yōu)郵路的算法：

    第1步：對于，其中d-為入度，d+為出度。若所有的σi=0，則歐拉圖G*=G，轉(zhuǎn)第2步；否則轉(zhuǎn)第3步；

    第2步：生成的G*一條歐拉閉跡；

    第3步：令，用Floyd算法求出G的最短（，）路。S中的任意節(jié)點重復(fù)σi個，T中的任意節(jié)點重復(fù)σj個，進(jìn)而構(gòu)造S與T的賦權(quán)完全二部圖D；

    第4步：求出D中的最小權(quán)完美匹配H（用原始-對偶算法）；

    第5步：找出H中對應(yīng)的每條邊在G中的最短（，）路，把這些路上的邊都添加到G上，得到歐拉圖G*，轉(zhuǎn)第2步。

    求解有向郵路的算法還有線性規(guī)劃和網(wǎng)絡(luò)流算法等。

    四、測試集的生成

    測試序列是生成測試?yán)那疤岷突A(chǔ)。在經(jīng)過上述算法得出測試序列之后，接下來進(jìn)入測試?yán)纳呻A段。測試?yán)纳梢话憧煞譃閮深悾阂皇恰盁o遺漏”的測試?yán)桑斎隕FSM，產(chǎn)生測試?yán)ú⒉皇钦嬲臒o遺漏覆蓋，錯誤的覆蓋率大于某一值），自動化程度高；二是基于測試目的的測試?yán)詣由桑斎隕FSM和形式化的測試目的，輸出測試?yán)枰斯じ深A(yù)。測試集生成技術(shù)中另一個要害的部分是測試集的描述及實現(xiàn)，目前比較好的方法是TTCN（樹表結(jié)合符號）來描述測試?yán)FCN可用于所有實時系統(tǒng)各種通信端口上的測試規(guī)范，非凡是通信協(xié)議的一致性測試描述。雖然TTCN有很多優(yōu)點，但是實現(xiàn)TTCN編譯器是一個相當(dāng)浩大的工程。

    在選擇好測試?yán)杉夹g(shù)之后，可通過設(shè)計簡單的測試語言編譯器，并結(jié)合相關(guān)的開發(fā)工具（如：C、C++、java等），完成對測試集的描述及實現(xiàn)。

    五、結(jié)束語

    在無線測試的過程中，一致性測試是測試工作中一項非常重要的測試內(nèi)容。為了避免傳統(tǒng)的手工測試花費代價過高、工作重復(fù)性大等弊端，本文采用了有效的算法生成最優(yōu)測試路由，減少了測試錯誤。同時，簡化了繁雜的工作，提高了一致性測試研究和實現(xiàn)的效率。該項測試集的生成技術(shù)可以應(yīng)用于各種通信協(xié)議的一致性測試中。

    參考文獻(xiàn)

    [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]謝政，李建平.網(wǎng)絡(luò)算法與復(fù)雜性理論[M]，長沙：國防科大出版社，1995

    [4]盧開澄，盧華明.圖論及其應(yīng)用（第2版）[M]，北京：清華大學(xué)出版社，2005.1