通信網(wǎng)banner.jpg)
相關(guān)專題：
一、引言
無線通信測試是無線通信項(xiàng)目工作中的其中一個(gè)重要環(huán)節(jié)。測試的目的就是通過各種相關(guān)手段對(duì)通信系統(tǒng)的功能進(jìn)行檢測和校驗(yàn)，盡可能發(fā)現(xiàn)其中存在的問題，以便于在下一步工作中糾正錯(cuò)誤，逐步完善系統(tǒng)功能。
在無線測試的過程中，一致性測試是測試工作中一項(xiàng)非常重要的測試內(nèi)容。協(xié)議一致性測試在驗(yàn)證協(xié)議實(shí)現(xiàn)的正確性，以及保證不同廠商開發(fā)的設(shè)備互連互通方面有著重要的作用。一致性測試是一種黑盒測試，IUT（被測實(shí)現(xiàn)）的源碼是未知的，測試者僅能控制和觀察IUT的某些接口；一致性測試的基本方法就是通過觀察協(xié)議規(guī)范和被測實(shí)現(xiàn)的輸入輸出來判斷二者是否一致。根據(jù)協(xié)議規(guī)范生成一系列的測試?yán)�，并在測試系統(tǒng)上運(yùn)行這些測試?yán)�，試圖發(fā)現(xiàn)錯(cuò)誤或者驗(yàn)證其正確性。
眾所周知，手工測試生成花費(fèi)的代價(jià)過于昂貴，冗長的重復(fù)性工作，相當(dāng)于30%協(xié)議實(shí)現(xiàn)的時(shí)間，并且通常不能保證錯(cuò)誤覆蓋[1]。為此，本文采用了有效的算法生成最優(yōu)測試路由，這樣可以大大減少測試錯(cuò)誤。同時(shí)，可以簡化繁雜的測試工作，提高了一致性測試研究和實(shí)現(xiàn)的效率。不僅如此，其中所涉及的算法也有助于測試規(guī)程（或測試標(biāo)準(zhǔn)）的編寫。該項(xiàng)測試集的生成技術(shù)可以應(yīng)用于各種通信協(xié)議的一致性測試中。
二、引理
在此，以藍(lán)牙協(xié)議中電話控制協(xié)議TCS為例，研究其信令測試集的生成技術(shù)。該協(xié)議（包括控制和數(shù)據(jù)）可以用一個(gè)EFSM（擴(kuò)展有限狀態(tài)機(jī)）[1]模型來描述，具體描述如下：M=（I，O，S，
，T，），其中，I表示輸入的信令消息集，O表示輸出的信令消息集，S為狀態(tài)集，為協(xié)議所包含變量集，T為變遷集，且，
，t=（st，qt，at，ot，Pt，At）其中st，qt，at和ot分別表示當(dāng)前狀態(tài)，下一個(gè)狀態(tài)，輸入和輸出。Pt（）表示當(dāng)前協(xié)議變量對(duì)應(yīng)的斷言，At（）表示當(dāng)前協(xié)議變量對(duì)應(yīng)的動(dòng)作。 對(duì)于一個(gè)給定的EFSM，把每一個(gè)狀態(tài)S和與之有關(guān)的協(xié)議變量值
當(dāng)成一個(gè)配置（Con-figuration）節(jié)點(diǎn)。我們所關(guān)心的就是初始配置到其他配置的轉(zhuǎn)換。因此，可以用如下一個(gè)連通的有向圖來描述EFSM： G=
當(dāng)作一個(gè)配置來考察，所以，E的描述為
其中
為當(dāng)前配置節(jié)點(diǎn)，為變遷的下一個(gè)配置節(jié)點(diǎn)。W為變遷所對(duì)應(yīng)的費(fèi)用權(quán)值（與變遷的時(shí)間有關(guān)），用來
表示。 這樣，就可以把TCS的EFSM狀態(tài)用圖1表示。
三、測試序列算法
對(duì)于一致性測試而言，我們所關(guān)心的問題就是協(xié)議規(guī)范M與協(xié)議實(shí)現(xiàn)Mˊ是否一致。
�。�1）驗(yàn)證單個(gè)變遷：
，對(duì)于處于狀態(tài)Si的Mˊ輸入ai，檢查輸出oi與協(xié)議規(guī)范M所描述oi是否一致，并驗(yàn)證Mˊ變遷后是否轉(zhuǎn)移到sj； �。�2）驗(yàn)證所有變遷：Mˊ檢查中所有的變遷及狀態(tài)，完成整個(gè)協(xié)議機(jī)Mˊ的測試。
基本假設(shè)：協(xié)議描述（狀態(tài)機(jī)）是輸入完全的、確定的、最小化的和強(qiáng)聯(lián)通的。協(xié)議描述最小化即是要求協(xié)議中沒有冗余的配置（或狀態(tài)）。一個(gè)協(xié)議狀態(tài)機(jī)復(fù)位后進(jìn)入一個(gè)初始配置，如TCS協(xié)議EFSM在藍(lán)牙終端開機(jī)后進(jìn)入空閑模式
。到任何其他配置都是可達(dá)的，而其他配置到一般來說也是可達(dá)的。若
到不可達(dá)，則可增加一個(gè)變遷（，；rj/null），其中rj是使配置復(fù)位到初始配置的操作，且輸出為空。這樣協(xié)議機(jī)就變成強(qiáng)聯(lián)通的了，即說明了假設(shè)的合理性。 測試序列算法如下：
�。�1）驗(yàn)證單個(gè)變遷的算法：設(shè)欲驗(yàn)證的變遷為
第1步：生成一個(gè)到
的Homing序列（用Dijkstra最短路算法[3]），使EFSM從初始配置變遷到第2步：輸入ai，檢查輸出是否與oi一致；
第3步：輸入
的UIO序列，檢查對(duì)應(yīng)的輸出序列，判斷EFSM變遷后的配置是否為（2）驗(yàn)證所有變遷的算法[2] 對(duì)于EFSM的描述圖G而言，根據(jù)基本假設(shè)可知，生成圖G的一條有向郵路，就可以驗(yàn)證協(xié)議機(jī)的所有變遷及配置。因?yàn)镚是最小的，沒有等價(jià)的配置節(jié)點(diǎn)，所以，回路的輸入序列可以作為各個(gè)狀態(tài)的UIO序列。這樣根據(jù)中國郵遞員問題[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ò)流算法等。
四、測試集的生成
測試序列是生成測試?yán)那疤岷突A(chǔ)。在經(jīng)過上述算法得出測試序列之后，接下來進(jìn)入測試?yán)纳呻A段。測試?yán)纳梢话憧煞譃閮深悾阂皇恰盁o遺漏”的測試?yán)�，輸入EFSM，產(chǎn)生測試?yán)ú⒉皇钦嬲臒o遺漏覆蓋，錯(cuò)誤的覆蓋率大于某一值），自動(dòng)化程度高；二是基于測試目的的測試?yán)詣?dòng)生成，輸入EFSM和形式化的測試目的，輸出測試?yán)�，需要人工干預(yù)。測試集生成技術(shù)中另一個(gè)關(guān)鍵的部分是測試集的描述及實(shí)現(xiàn)，目前比較好的方法是TTCN（樹表結(jié)合符號(hào)）來描述測試?yán)FCN可用于所有實(shí)時(shí)系統(tǒng)各種通信端口上的測試規(guī)范，特別是通信協(xié)議的一致性測試描述。雖然TTCN有很多優(yōu)點(diǎn)，但是實(shí)現(xiàn)TTCN編譯器是一個(gè)相當(dāng)浩大的工程。
在選擇好測試?yán)杉夹g(shù)之后，可通過設(shè)計(jì)簡單的測試語言編譯器，并結(jié)合相關(guān)的開發(fā)工具（如：C、C+ +、Java等），完成對(duì)測試集的描述及實(shí)現(xiàn)。
五、結(jié)束語
在無線測試的過程中，一致性測試是測試工作中一項(xiàng)非常重要的測試內(nèi)容。為了避免傳統(tǒng)的手工測試花費(fèi)代價(jià)過高、工作重復(fù)性大等弊端，本文采用了有效的算法生成最優(yōu)測試路由，減少了測試錯(cuò)誤。同時(shí)，簡化了繁雜的工作，提高了一致性測試研究和實(shí)現(xiàn)的效率。該項(xiàng)測試集的生成技術(shù)可以應(yīng)用于各種通信協(xié)議的一致性測試中。
參考文獻(xiàn)
[1] David Lee and Mihalis Yannakakis，Principles and Methods of Testing Finite State Machines[J]——A Survey，Proceedings of the IEEE，Vol.84 No.8，1996.8
[2] Alfred V.Aho，Anton T.Dahbura，David Lee 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
