0 引言

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

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

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

1 ATF

    ATF(Automation Test Framework)框架提供了豐富的腳本運行和管理接口。在自動拓撲映射模塊的支持下，實現(xiàn)了腳本開發(fā)的拓撲環(huán)境與執(zhí)行期實際物理組網(wǎng)環(huán)境無關(guān)。基于ATF框架的腳本主要由拓撲、測試床以及腳本這三類文件組成。其中測試床文件負責描述用戶的物理組網(wǎng)環(huán)境，拓撲文件用于描述邏輯拓撲環(huán)境，腳本文件用于完成實際測試步驟。而拓撲文件與測試床文件之間的映射關(guān)系則由自動拓撲映射模塊來完成。

1.1 ATF算法

    假設(shè)當前組網(wǎng)中存在物理設(shè)備M臺，邏輯拓撲中存在邏輯設(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)中找出滿足邏輯拓撲的設(shè)備及連接關(guān)系。

    首先根據(jù)設(shè)備類型和連接類型，找出各個邏輯設(shè)備的可選物理設(shè)備范圍，邏輯設(shè)備{N₁，N₂…N_n}分別在物理設(shè)備范圍{M₁，M₂…M_m}進行映射查找，得到{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²的矩陣，與目標邏輯拓撲N²矩陣進行C次匹配，排除重復(fù)的設(shè)備組合，檢查邏輯拓撲連接是否匹配其物理設(shè)備連接。算法復(fù)雜度：

1.2 ATF算法優(yōu)化

    ATF拓撲查找算法存在明顯的不足，沒有高效的排序依據(jù)，邏輯矩陣與物理矩陣中設(shè)備連接要進行一一匹配檢查，還需要考慮物理設(shè)備包含HUB和物理交換機時的情況，效率極低。所以在可選設(shè)備的判斷上，增加設(shè)備類型約束檢查，最大限度減小解空間，將輸出的矩陣范圍和邏輯設(shè)備列表進行排序，引入到智能云測試自動拓撲映射的算法實現(xiàn)上。

2 自動拓撲映射算法實現(xiàn)機制

2.1 智能云測試平臺

    智能云測試平臺以云為中心，將測試資源集中管理，按需動態(tài)分配，同時腳本集中在云端并發(fā)分布式執(zhí)行。拓撲占用過程為智能云測試后臺某任務(wù)根據(jù)其拓撲以及要運行的物理組網(wǎng)，向拓撲映射模塊發(fā)起占用請求。拓撲映射模塊在整個物理組網(wǎng)中空閑資源上查找符合指定拓撲的設(shè)備及端口，并修改其占用狀態(tài)。拓撲釋放過程為：任務(wù)執(zhí)行完畢后向拓撲映射模塊發(fā)起釋放請求，拓撲映射模塊根據(jù)其拓撲所映射的設(shè)備和端口來釋放相應(yīng)的物理設(shè)備及端口狀態(tài)。達到對物理資源統(tǒng)一協(xié)調(diào)，并對上層應(yīng)用透明的目的，在核心功能上通過調(diào)用自動拓撲映射核心算法提供的接口來進行處理。

2.2 自動拓撲映射核心算法

    設(shè)計上將拓撲映射算法的處理邏輯和數(shù)據(jù)分離。整體可分為三部分：輸入輸出部分、配置信息部分以及核心算法部分，如圖1。

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

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

2.3 核心算法初始化

    按照ATF拓撲映射算法，物理組網(wǎng)規(guī)模達到一定程度，如50臺設(shè)備的組網(wǎng)中獲取邏輯設(shè)備個數(shù)為8的拓撲，則其可能組合數(shù)是個天文數(shù)字，遍歷這些組合需要的時間耗費巨大，因此，需要一種更好的方式來完成算法。假設(shè)當前輸入的邏輯設(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è)備集合

    對于邏輯拓撲中的每個邏輯設(shè)備，在物理組網(wǎng)的物理設(shè)備中為其確定一個可選設(shè)備范圍。通過確定一系列規(guī)則對可選設(shè)備范圍進行過濾，從而縮小最終解空間。

    (1)邏輯拓撲中支持用戶設(shè)置某臺邏輯設(shè)備或者端口的映射結(jié)果。其可選設(shè)備范圍有且僅有一個。若其手工映射的物理設(shè)備不存在，意味著拓撲映射失??；

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

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

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

2.3.2 候選分組生成

    從每個可選設(shè)備物理設(shè)備集合中選取一個物理設(shè)備組成候選映射分組，并檢查該候選映射分組與邏輯拓撲是否能夠成功映射，映射失敗時重復(fù)上一動作取下一候選映射分組。假設(shè)DUT1為高位，DUT3為低位。對于示例邏輯拓撲所得到的可選設(shè)備集合，從低位變化，依次獲取的候選映射分組如圖6。

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

2.3.3 分組進位表

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

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

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

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

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

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

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

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

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

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

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

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

4 結(jié)束語

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

參考文獻

[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ā)現(xiàn)新算法及其實現(xiàn)[J].電子學(xué)報，2008（8）：1620-1625.

[6] 姜譽，方濱興，胡銘曾.多點探測Internet路由器級拓撲[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] 陳波，洪曉光.基于改進樹狀結(jié)構(gòu)的XML文檔簡單路徑查詢多線程實現(xiàn)[C].中國數(shù)據(jù)庫學(xué)術(shù)會議，2004：382-387.

作者信息:

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

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