0 引言

    隨著自動(dòng)化測(cè)試^[1]技術(shù)的不斷發(fā)展，第四代自動(dòng)化測(cè)試技術(shù)云測(cè)試^[2]應(yīng)運(yùn)而生，這就是智能云測(cè)試平臺(tái)^[3，4]。其平臺(tái)要求將測(cè)試資源進(jìn)行集中化管理，面對(duì)多個(gè)測(cè)試小組進(jìn)行資源共享，以提高資源利用率。同時(shí)，引進(jìn)測(cè)試任務(wù)機(jī)制來(lái)分配資源、監(jiān)控測(cè)試進(jìn)度以及發(fā)布結(jié)果。智能云測(cè)試平臺(tái)強(qiáng)調(diào)資源的集中化管理，由此對(duì)于自動(dòng)拓?fù)溆成?/a>算法^[5]的方法提出了更高的要求。

    拓?fù)洳檎宜惴?sup>[6，7]的實(shí)現(xiàn)就是在給定的物理組網(wǎng)中，查找滿足邏輯拓?fù)渲兴枋龅脑O(shè)備和連接關(guān)系的物理設(shè)備及其連接的映射關(guān)系。一般情況下，測(cè)試床都有各個(gè)測(cè)試小組自行組件，根據(jù)其被測(cè)設(shè)備的特點(diǎn)來(lái)單獨(dú)搭建網(wǎng)絡(luò)。測(cè)試床的規(guī)模一般都是4～5臺(tái)，最大規(guī)模一般也不超過(guò)10臺(tái)設(shè)備，算法擴(kuò)展性及保密性比較差，整體效率較低，設(shè)備數(shù)量增加時(shí)耗時(shí)較長(zhǎng)，得到的可選設(shè)備范圍過(guò)大，不支持測(cè)試床中包含物理交換機(jī)的組網(wǎng)。

    智能云測(cè)試平臺(tái)引入后，自動(dòng)化拓?fù)溆成渌惴ɑ趥鹘y(tǒng)ATF框架^[8-11]，主要從設(shè)備可選范圍、設(shè)備的排序和連接映射的處理表等方面進(jìn)行探討，優(yōu)化該算法的實(shí)現(xiàn)，使云平臺(tái)測(cè)試效率進(jìn)一步得到提升。

1 ATF

    ATF(Automation Test Framework)框架提供了豐富的腳本運(yùn)行和管理接口。在自動(dòng)拓?fù)溆成淠K的支持下，實(shí)現(xiàn)了腳本開(kāi)發(fā)的拓?fù)洵h(huán)境與執(zhí)行期實(shí)際物理組網(wǎng)環(huán)境無(wú)關(guān)?；贏TF框架的腳本主要由拓?fù)?、測(cè)試床以及腳本這三類(lèi)文件組成。其中測(cè)試床文件負(fù)責(zé)描述用戶的物理組網(wǎng)環(huán)境，拓?fù)湮募糜诿枋鲞壿嬐負(fù)洵h(huán)境，腳本文件用于完成實(shí)際測(cè)試步驟。而拓?fù)湮募c測(cè)試床文件之間的映射關(guān)系則由自動(dòng)拓?fù)溆成淠K來(lái)完成。

1.1 ATF算法

    假設(shè)當(dāng)前組網(wǎng)中存在物理設(shè)備M臺(tái)，邏輯拓?fù)渲写嬖谶壿嬙O(shè)備N(xiāo)臺(tái)，物理設(shè)備的連接關(guān)系分別為{M₁，M₂}、{M₁，M₃}…{M_n，M_m}，總連接數(shù)為m；邏輯設(shè)備連接關(guān)系分別為{N₁，N₂}、{N₁，N₃}…總連接數(shù)為n；從組網(wǎng)中找出滿足邏輯拓?fù)涞脑O(shè)備及連接關(guān)系。

    首先根據(jù)設(shè)備類(lèi)型和連接類(lèi)型，找出各個(gè)邏輯設(shè)備的可選物理設(shè)備范圍，邏輯設(shè)備{N₁，N₂…N_n}分別在物理設(shè)備范圍{M₁，M₂…M_m}進(jìn)行映射查找，得到{K₁，K₂…K_n}。其中：K₁、K₂…K_n分別代表每個(gè)邏輯設(shè)備對(duì)應(yīng)的物理設(shè)備可選范圍個(gè)數(shù)，且K₁、K₂…K_n必然小于等于M。算法復(fù)雜度：T(n)=O(M×N)；然后在K₁×K₂…K_n的組合內(nèi)遍歷，對(duì)每個(gè)組合組成N²的矩陣，與目標(biāo)邏輯拓?fù)銷(xiāo)²矩陣進(jìn)行C次匹配，排除重復(fù)的設(shè)備組合，檢查邏輯拓?fù)溥B接是否匹配其物理設(shè)備連接。算法復(fù)雜度：

1.2 ATF算法優(yōu)化

    ATF拓?fù)洳檎宜惴ù嬖诿黠@的不足，沒(méi)有高效的排序依據(jù)，邏輯矩陣與物理矩陣中設(shè)備連接要進(jìn)行一一匹配檢查，還需要考慮物理設(shè)備包含HUB和物理交換機(jī)時(shí)的情況，效率極低。所以在可選設(shè)備的判斷上，增加設(shè)備類(lèi)型約束檢查，最大限度減小解空間，將輸出的矩陣范圍和邏輯設(shè)備列表進(jìn)行排序，引入到智能云測(cè)試自動(dòng)拓?fù)溆成涞乃惴▽?shí)現(xiàn)上。

2 自動(dòng)拓?fù)溆成渌惴▽?shí)現(xiàn)機(jī)制

2.1 智能云測(cè)試平臺(tái)

    智能云測(cè)試平臺(tái)以云為中心，將測(cè)試資源集中管理，按需動(dòng)態(tài)分配，同時(shí)腳本集中在云端并發(fā)分布式執(zhí)行。拓?fù)湔加眠^(guò)程為智能云測(cè)試后臺(tái)某任務(wù)根據(jù)其拓?fù)湟约耙\(yùn)行的物理組網(wǎng)，向拓?fù)溆成淠K發(fā)起占用請(qǐng)求。拓?fù)溆成淠K在整個(gè)物理組網(wǎng)中空閑資源上查找符合指定拓?fù)涞脑O(shè)備及端口，并修改其占用狀態(tài)。拓?fù)溽尫胚^(guò)程為：任務(wù)執(zhí)行完畢后向拓?fù)溆成淠K發(fā)起釋放請(qǐng)求，拓?fù)溆成淠K根據(jù)其拓?fù)渌成涞脑O(shè)備和端口來(lái)釋放相應(yīng)的物理設(shè)備及端口狀態(tài)。達(dá)到對(duì)物理資源統(tǒng)一協(xié)調(diào)，并對(duì)上層應(yīng)用透明的目的，在核心功能上通過(guò)調(diào)用自動(dòng)拓?fù)溆成浜诵乃惴ㄌ峁┑慕涌趤?lái)進(jìn)行處理。

2.2 自動(dòng)拓?fù)溆成浜诵乃惴?/strong>

    設(shè)計(jì)上將拓?fù)溆成渌惴ǖ奶幚磉壿嫼蛿?shù)據(jù)分離。整體可分為三部分：輸入輸出部分、配置信息部分以及核心算法部分，如圖1。

    數(shù)據(jù)部分采用XML結(jié)構(gòu)^[12]來(lái)封裝，以便后續(xù)擴(kuò)展。輸入部分包括邏輯拓?fù)浜蜏y(cè)試床，輸出部分主要是涵蓋了設(shè)備及其接口的映射結(jié)果。配置信息主要包括設(shè)備類(lèi)型樹(shù)、接口映射表等信息。核心算法邏輯如圖2所示。

    物理設(shè)備類(lèi)型必須與邏輯設(shè)備類(lèi)型相匹配。由于當(dāng)前設(shè)備類(lèi)型種類(lèi)繁多，為便于擴(kuò)展，將設(shè)備類(lèi)型定義成XML樹(shù)型結(jié)構(gòu)，同時(shí)封裝外圍接口來(lái)對(duì)其進(jìn)行訪問(wèn)。對(duì)于接口來(lái)說(shuō)，存在接口類(lèi)型以及封裝類(lèi)型的映射規(guī)則。同樣的，將接口類(lèi)型以及封裝類(lèi)型定義成XML結(jié)構(gòu)，同時(shí)封裝接口來(lái)對(duì)其進(jìn)行訪問(wèn)。邏輯拓?fù)浜蜏y(cè)試床信息都是對(duì)組網(wǎng)的結(jié)構(gòu)描述，主要包括設(shè)備屬性和連接屬性。組網(wǎng)信息同樣采用XML結(jié)構(gòu)來(lái)描述，并作為核心算法的輸入，設(shè)備節(jié)點(diǎn)由XML標(biāo)簽進(jìn)行封裝，包含基本屬性和訪問(wèn)屬性?xún)纱蟛糠??；緦傩杂蛴糜诿枋鲈O(shè)備基本屬性，用于拓?fù)溆成渌惴?，訪問(wèn)屬性主要用于記錄該設(shè)備的訪問(wèn)地址、用戶密碼等信息。該域并不用于拓?fù)溆成渌惴?，但該部分?jǐn)?shù)據(jù)使得執(zhí)行機(jī)能夠識(shí)別本組網(wǎng)結(jié)構(gòu)，以實(shí)現(xiàn)自動(dòng)地打開(kāi)組網(wǎng)內(nèi)包含的各類(lèi)設(shè)備，連接節(jié)點(diǎn)用于記錄組網(wǎng)中的所有鏈接。對(duì)于邏輯拓?fù)鋪?lái)說(shuō)，只包含普通P2P連接以及Hub連接，而對(duì)于物理測(cè)試床來(lái)說(shuō)，該部分還可描述基于連接設(shè)備的連接。

2.3 核心算法初始化

    按照ATF拓?fù)溆成渌惴ǎ锢斫M網(wǎng)規(guī)模達(dá)到一定程度，如50臺(tái)設(shè)備的組網(wǎng)中獲取邏輯設(shè)備個(gè)數(shù)為8的拓?fù)洌瑒t其可能組合數(shù)是個(gè)天文數(shù)字，遍歷這些組合需要的時(shí)間耗費(fèi)巨大，因此，需要一種更好的方式來(lái)完成算法。假設(shè)當(dāng)前輸入的邏輯設(shè)備包括3臺(tái)設(shè)備，分別為DUT1、DUT2、DUT3，設(shè)備之間存在4條連接，對(duì)應(yīng)的邏輯組網(wǎng)如圖3所示。

    輸入的物理測(cè)試床由6臺(tái)設(shè)備組成，其中包含一臺(tái)物理交換機(jī)作為連接設(shè)備。在物理組網(wǎng)中，存在5臺(tái)設(shè)備DEV1、DEV2、DEV3、DEV4、DEV5，其設(shè)備類(lèi)型相同。其中DEV1、DEV2、DEV3分別兩兩相連，DEV2、DEV3、DEV4、DEV5分別與物理交換機(jī)設(shè)備連接，其對(duì)應(yīng)的組網(wǎng)圖如圖4所示。

2.3.1 可選設(shè)備集合

    對(duì)于邏輯拓?fù)渲械拿總€(gè)邏輯設(shè)備，在物理組網(wǎng)的物理設(shè)備中為其確定一個(gè)可選設(shè)備范圍。通過(guò)確定一系列規(guī)則對(duì)可選設(shè)備范圍進(jìn)行過(guò)濾，從而縮小最終解空間。

    (1)邏輯拓?fù)渲兄С钟脩粼O(shè)置某臺(tái)邏輯設(shè)備或者端口的映射結(jié)果。其可選設(shè)備范圍有且僅有一個(gè)。若其手工映射的物理設(shè)備不存在，意味著拓?fù)溆成涫。?/p>

    (2)設(shè)備類(lèi)型是過(guò)濾設(shè)備集合的最佳條件之一。在智能云測(cè)試系統(tǒng)設(shè)備類(lèi)型豐富，根據(jù)不同邏輯拓?fù)渲兄付ǖ脑O(shè)備類(lèi)型，可以縮小其可選設(shè)備集合名單；

    (3)由于連接關(guān)系映射要求接口個(gè)數(shù)，能夠滿足映射的物理設(shè)備有效接口個(gè)數(shù)至少大于等于邏輯設(shè)備接口個(gè)數(shù)；

    (4)測(cè)試床中的物理設(shè)備還包含若干其他屬性，如是否雙主控設(shè)備等。所有邏輯設(shè)備的可選設(shè)備集合確定后，意味著本次拓?fù)溆成涞慕饪臻g范圍確定。假設(shè)DEV1～DEV5的設(shè)備類(lèi)型相同均能夠與其邏輯設(shè)備類(lèi)型相匹配。SW設(shè)備類(lèi)型不能匹配，直接過(guò)濾。所以其可選設(shè)備集合為DUT1：{DEV2，DEV3}；DUT2：{DEV2，DEV3}；DUT3：{DEV1，DEV2，DEV3，DEV4，DEV5}。物理組網(wǎng)的設(shè)備進(jìn)行編號(hào)，從0開(kāi)始分別代表DEV1、DEV2、DEV3、DEV4、DEV5，最終得到的邏輯拓?fù)淇蛇x設(shè)備集合如圖5。

2.3.2 候選分組生成

    從每個(gè)可選設(shè)備物理設(shè)備集合中選取一個(gè)物理設(shè)備組成候選映射分組，并檢查該候選映射分組與邏輯拓?fù)涫欠衲軌虺晒τ成?，映射失敗時(shí)重復(fù)上一動(dòng)作取下一候選映射分組。假設(shè)DUT1為高位，DUT3為低位。對(duì)于示例邏輯拓?fù)渌玫降目蛇x設(shè)備集合，從低位變化，依次獲取的候選映射分組如圖6。

    由拓?fù)溆成浣Y(jié)果發(fā)現(xiàn)候選映射組合中含有重復(fù)設(shè)備的組合，顯然不能滿足條件。在實(shí)踐中采用進(jìn)位表的方式來(lái)實(shí)現(xiàn)對(duì)重復(fù)分組的高效過(guò)濾，減少對(duì)映射組合的處理。

2.3.3 分組進(jìn)位表

    構(gòu)造一個(gè)N2的表，表中每個(gè)元素采用數(shù)字編號(hào)，其中N為邏輯設(shè)備個(gè)數(shù)。對(duì)于邏輯設(shè)備，包含兩列內(nèi)容，分別為當(dāng)前行的進(jìn)位標(biāo)記和當(dāng)前行的最大進(jìn)位閾值。當(dāng)前行的最大進(jìn)位標(biāo)記默認(rèn)為0，最大進(jìn)位閾值為對(duì)應(yīng)可選設(shè)備集合大小。對(duì)于邏輯拓?fù)洌瑑?nèi)容見(jiàn)表1。

    定義低位從行末即行2開(kāi)始，從低位開(kāi)始讀取進(jìn)位表，首次取到{0  0  0}，對(duì)應(yīng)的候選設(shè)備組合為{1  1  0}。分析發(fā)現(xiàn)該組合存在重復(fù)設(shè)備，從低位開(kāi)始遍歷該組合，找到最低位的重復(fù)設(shè)備編號(hào)，由于1和1的重復(fù)設(shè)備的分組均無(wú)效，而是直接對(duì)當(dāng)前最低重復(fù)為行1進(jìn)行進(jìn)位，得到如表2的進(jìn)位表。

    讀取該進(jìn)位表{0  1  0}，其對(duì)應(yīng)的候選設(shè)備組合為{1  2  0}。經(jīng)分析，該組合非重復(fù)組合，系統(tǒng)可以確定該分組為合法映射分組，并進(jìn)行后續(xù)連接映射處理。若該組合連接映射失敗，繼續(xù)從進(jìn)位表的最低位向右偏移，得到的進(jìn)位表見(jiàn)表3。

    讀取當(dāng)前進(jìn)位表得到{1  1  0}，對(duì)應(yīng)的候選設(shè)備組合為{1  2  1}。分析發(fā)現(xiàn)該組合存在重復(fù)設(shè)備，對(duì)行2進(jìn)行遞增，并持續(xù)向上傳遞。同時(shí)進(jìn)位后的地位需要清零。

    與最初的候選設(shè)備分組相比，引入進(jìn)位表后，系統(tǒng)處理的候選設(shè)備列表如圖7所示。

    圖7中，雙刪除線組合為進(jìn)位表直接進(jìn)位過(guò)濾，不需要進(jìn)入重復(fù)設(shè)備分析階段。最終進(jìn)入連接映射階段設(shè)備分組數(shù)量為6，達(dá)到此階段，對(duì)于設(shè)備映射的分析基本結(jié)束。若候選設(shè)備分組不存在時(shí)，可直接返回拓?fù)溆成涫　?nbsp;

3 進(jìn)位表優(yōu)化分析

    當(dāng)P2P連接映射失敗時(shí)，必然是某個(gè)邏輯設(shè)備組間的連接無(wú)法在對(duì)應(yīng)的物理P2P連接矩陣(實(shí)踐中分別為邏輯拓?fù)浜臀锢頊y(cè)試床建立P2P連接矩陣，矩陣中的元素代表每組設(shè)備間的連接個(gè)數(shù)，系統(tǒng)只需要每個(gè)候選設(shè)備分組來(lái)構(gòu)造一個(gè)物理P2P連接矩陣)中得到映射結(jié)果，從而導(dǎo)致P2P映射失敗。當(dāng)候選設(shè)備組合映射失敗時(shí)，正常情況下是從最低位后取下一候選設(shè)備組合，若P2P映射失敗的設(shè)備組不包含最低位邏輯設(shè)備，后續(xù)的若干個(gè)候選設(shè)備組合仍然會(huì)在P2P連接映射階段失敗，此時(shí)會(huì)包含大量重復(fù)計(jì)算過(guò)程。在P2P連接映射失敗后，記錄當(dāng)前映射失敗的設(shè)備組，并找到其對(duì)應(yīng)的進(jìn)位表的最低位所在行。若該行非實(shí)際最低位，則直接從該行位置進(jìn)位。

    假設(shè)邏輯設(shè)備組DUT1和DUT2間的兩條連接分別為Serial連接和Ethernet連接；而物理設(shè)備組DEV2和DEV3間的連接為Ethernet連接，假設(shè)當(dāng)前取到組合{0  1  0}，即對(duì)應(yīng)的候選設(shè)備分組為{1  2  0}。此時(shí)的進(jìn)位表內(nèi)容見(jiàn)表4。

    進(jìn)入P2P連接映射階段，對(duì){1  2  0}分組構(gòu)建連接矩陣進(jìn)行P2P連接映射。發(fā)現(xiàn)邏輯設(shè)備組(DUT1，DUT2)間的連接映射失敗，個(gè)數(shù)吻合但連接類(lèi)型不匹配。此時(shí)檢查該設(shè)備組的最低位設(shè)備DUT2對(duì)應(yīng)進(jìn)位表的行1，此時(shí)直接對(duì)行1進(jìn)行進(jìn)位檢查。此時(shí)的進(jìn)位表內(nèi)容如表5所示。

    引入P2P連接失敗進(jìn)位后，系統(tǒng)處理的候選設(shè)備分組列表如圖8所示。

    以上列表中深色背景加刪除線的部分會(huì)直接通過(guò)進(jìn)位法跳過(guò)，再次縮小解空間。本優(yōu)化方法在邏輯拓?fù)渲写嬖诙鄺l連接或者非以太鏈路的情況極為有效。所以根據(jù)連接進(jìn)行進(jìn)位的實(shí)質(zhì)是提前將設(shè)備組間連接映射失敗的情況找出，才能通過(guò)進(jìn)位過(guò)濾掉大批與其相關(guān)的候選設(shè)備組合。設(shè)計(jì)邏輯設(shè)備進(jìn)位表的行順序時(shí)，應(yīng)該盡量將連接個(gè)數(shù)多以及存在非以太網(wǎng)連接的設(shè)備放到前面，以便構(gòu)造P2P連接矩陣時(shí)能夠盡快從較高位找出映射失敗的設(shè)備組。

4 結(jié)束語(yǔ)

    本文給出了智能云測(cè)試系統(tǒng)自動(dòng)拓?fù)溆成渌惴▽?shí)現(xiàn)的方法，該方法應(yīng)用到實(shí)際的智能云測(cè)試系統(tǒng)中，極大縮小了設(shè)備映射的解空間和占用到設(shè)備所用的時(shí)間，時(shí)間復(fù)雜度明顯降低，對(duì)核心算法邏輯結(jié)構(gòu)的每部分進(jìn)行了優(yōu)化，支持測(cè)試床中包含物理交換機(jī)的組網(wǎng)。其中進(jìn)位表的優(yōu)化的方法更為容易理解，使智能云測(cè)試系統(tǒng)中測(cè)試設(shè)備得到充分利用，提升了整體的測(cè)試效率和可靠性。但在實(shí)際的應(yīng)用中還存在不足之處，腳本調(diào)試的過(guò)程中修改拓?fù)浜?，占用測(cè)試床時(shí)自動(dòng)拓?fù)溆成洳荒莒`活映射到新的設(shè)備，下一步將進(jìn)行研究和改進(jìn)。

參考文獻(xiàn)

[1] 柏瑩.基于NET平臺(tái)下Web自動(dòng)化測(cè)試的研究與設(shè)計(jì)[D].西安：西安電子科技大學(xué)，2013.

[2] 李喬，何棟梁，王小林.云測(cè)試研究現(xiàn)狀綜述[J].現(xiàn)代計(jì)算機(jī)，2011（23）：25-30.

[3] LEAH R K，OSSI T，KARI S.Testing in the Cloud：Exploring the practice[J].IEEE Software，2012，29(2)：46-51.

[4] 丁小盼，周浩，賀珊，等.基于OpenStack的云測(cè)試平臺(tái)及其性能分析研究[J].軟件學(xué)報(bào)，2015（1）：6-10.

[5] 陳福，楊家海，楊揚(yáng).網(wǎng)絡(luò)拓?fù)浒l(fā)現(xiàn)新算法及其實(shí)現(xiàn)[J].電子學(xué)報(bào)，2008（8）：1620-1625.

[6] 姜譽(yù)，方濱興，胡銘曾.多點(diǎn)探測(cè)Internet路由器級(jí)拓?fù)鋄J].電信科學(xué)，2004（9）：12-17.

[7] 姚杰，程光鈞，李浩，等.基于數(shù)據(jù)驅(qū)動(dòng)自動(dòng)化測(cè)試框架研究和實(shí)現(xiàn)[J].工業(yè)控制計(jì)算機(jī)，2013，26(7)：67-69.

[8] 朱菊，王志堅(jiān)，楊雪，等.基于數(shù)據(jù)驅(qū)動(dòng)的軟件自動(dòng)化測(cè)試框架[J].計(jì)算機(jī)技術(shù)與發(fā)展，2006，16(5)：68-70.

[9] 接卉，蘭雨晴，駱沛，等.一種關(guān)鍵字驅(qū)動(dòng)的自動(dòng)化測(cè)試框架[J].計(jì)算機(jī)應(yīng)用研究，2009，26(3)：927-929.

[10] 張磊，王曉軍.基于STAF框架下的自動(dòng)化測(cè)試[J].計(jì)算機(jī)技術(shù)與發(fā)展，2010，3（3）：117-119.

[11] 陳波，洪曉光.基于改進(jìn)樹(shù)狀結(jié)構(gòu)的XML文檔簡(jiǎn)單路徑查詢(xún)多線程實(shí)現(xiàn)[C].中國(guó)數(shù)據(jù)庫(kù)學(xué)術(shù)會(huì)議，2004：382-387.

作者信息:

王  亮1，韓連鋼2，謝錫海1

(1.西安郵電大學(xué) 通信與信息工程學(xué)院，陜西 西安710061；2.西安航天動(dòng)力技術(shù)研究所，陜西 西安710025）