作者：江敏  張毅

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

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

    一、引言

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

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

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

    二、引理

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

    圖1  EFSM狀態(tài)圖

    三、測(cè)試序列算法

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

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

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

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

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

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

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

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

    四、測(cè)試集的生成

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

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

    五、結(jié)束語(yǔ)

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

    參考文獻(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]，長(zhǎng)沙：國(guó)防科大出版社，1995

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