0 引言

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

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

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

1 ATF

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

1.1 ATF算法

    假設(shè)當(dāng)前組網(wǎng)中存在物理設(shè)備M臺,，邏輯拓?fù)渲写嬖谶壿嬙O(shè)備N臺,，物理設(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è)備類型和連接類型,，找出各個邏輯設(shè)備的可選物理設(shè)備范圍，邏輯設(shè)備{N₁,，N₂…N_n}分別在物理設(shè)備范圍{M₁,，M₂…M_m}進(jìn)行映射查找，得到{K₁,，K₂…K_n},。其中：K₁、K₂…K_n分別代表每個邏輯設(shè)備對應(yīng)的物理設(shè)備可選范圍個數(shù),，且K₁,、K₂…K_n必然小于等于M。算法復(fù)雜度：T(n)=O(M×N),；然后在K₁×K₂…K_n的組合內(nèi)遍歷,，對每個組合組成N²的矩陣，與目標(biāo)邏輯拓?fù)銷²矩陣進(jìn)行C次匹配,，排除重復(fù)的設(shè)備組合,，檢查邏輯拓?fù)溥B接是否匹配其物理設(shè)備連接。算法復(fù)雜度：

1.2 ATF算法優(yōu)化

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

2 自動拓?fù)溆成渌惴▽崿F(xiàn)機制

2.1 智能云測試平臺

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

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

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

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

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

2.3 核心算法初始化

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

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

2.3.1 可選設(shè)備集合

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

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

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

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

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

2.3.2 候選分組生成

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

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

2.3.3 分組進(jìn)位表

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

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

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

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

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

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

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

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

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

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

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

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

4 結(jié)束語

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

參考文獻(xiàn)

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

[2] 李喬，何棟梁,，王小林.云測試研究現(xiàn)狀綜述[J].現(xiàn)代計算機,，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的云測試平臺及其性能分析研究[J].軟件學(xué)報，2015（1）：6-10.

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

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

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

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

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

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

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

作者信息:

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

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