基于蟻群算法的測試向量生成研究

康 鵬，金 婕，嚴 偉

（1 上海工程技術大學 電子電氣工程學院，上海 201620；2 北京大學 軟件與微電子學院，北京 102600）

0 引 言

隨著電路板集成度和元器件復雜度呈現指數式增長，對其可控性、可測性和可觀察性的要求越來越高，而對實踐中電路板的測試要求也更加嚴格。傳統的電路板故障檢測方法都是以功能測試為出發點，步驟復雜，測試時間長，很難精確定位到故障點。為針對電子系統故障診斷的難點提供全面可靠的故障診斷方案，聯合測試行動組（JTAG）提出了一套邊界掃描體系結構標準化可測試性技術。邊界掃描技術對待測電路發送測試向量，獲取測試響應，通過測試向量和測試響應分析診斷電路故障。因此，在邊界掃描的板級測試中，測試向量集的優劣直接影響故障檢測的效果。如何生成高質量的測試向量集是當今邊界掃描技術重點關注的問題。

近些年來，學者們提出了一系列的測試向量生成算法。如，改良計數算法MCSA、等權值抗誤判算法、極小權值-極大相異性算法等等。這些算法建立在無限制故障模型的基礎上，雖然有不錯的故障誤判率和故障混淆率，但是未能結合電路板的結構信息，難以實現最佳的測試效果。結構測試算法（Structural Test）通過分析電路板的結構和工藝信息，建立有限制故障模型，使得測試向量在具備完備故障診斷能力的前提下獲得更小的緊湊性指標。基于近鄰網絡排序集的測試向量優化算法，雖然可以極大地優化測試向量集的緊湊性和完備性，但是受制于近鄰網絡排序集難以獲取的特點，無法應用于工程實踐。為此，本文提出一種有限制短路故障模型和蟻群算法相結合的測試向量生成策略。首先，結合PCB電路板的結構特征、元器件特性和工藝建立有限制短路故障模型，分析各網絡間發生短路故障的概率。然后將問題轉換成圖論中最小點覆蓋的問題，利用蟻群算法尋找最小覆蓋點，結合網絡近鄰關系矩陣生成優化的測試矩陣，最后通過實驗分析了該方法的有效性，最終生成的測試矩陣在保證完備性的情況下，具有較好的緊湊性。

1 有限制短路故障模型

對于包含個網絡電路板的無限制故障模型，任意2個網絡之間都會發生故障，故障類型分為固定邏輯故障和橋接短路故障。假定一個5網絡的電路，研究時基于無限制故障模型的思想，可得到的拓撲結構如圖1（a）所示。然而PCB板上的短路故障大多發生在元件管腳（焊點）、導線、過孔等之間，并且與其在PCB板的分布情況密切相關。因此，不同的2個網絡之間發生短路的幾率也是不相同的。另有研究表明，元器件管腳的焊點之間發生短路的幾率和焊點之間的物理位置，可以用指數衰減函數來進行描述，對此可表示為：

其中，P、P表示電路板中的2個節點；表示節點之間的最短距離；表示兩節點距離；表示兩節點出現短路故障時的最大間距；表示距離最小的2個節點間出現短路故障的機率，1；表示衰減系數，1。

網絡是由導線連接元器件管腳（焊點）構成的，對于一個有個網絡的電路板，若n、n是其中的2個子網絡，則n和n之間發生短路的可能性關系的數學表達式可寫為：

將式（2）簡化成式（3）：

由式（3）計算出不同網絡之間發生短路的幾率。當小于閾值時，這2個網絡不會發生故障。基于此理論，對于同一個5網絡的電路板，結合電路板的結構信息，就可以計算出各網絡之間發生短路故障的可能性。通過比較和閾值，可以將無限制的短路故障模型拓撲圖簡化成如圖1（b）所示的模型圖。

圖1 網絡短路故障關系拓撲模型Fig.1 Network short-circuit fault relationship topology model

2 蟻群算法

2.1 問題描述

邊界掃描測試給每個網絡賦予一個測試向量，通過采集并分析測試響應，即可推斷出故障位置。在圖1（b）中，如果能找到一個網絡子集使得圖中所有的邊至少有一個端點在該子集中，那么由該網絡子集組成的測試向量矩陣就可以診斷所有的短路故障。因此，可以采用求解圖論最小點覆蓋問題生成測試矩陣。

2.2 蟻群算法求解最小點覆蓋

首先通過比較網絡之間的短路幾率和閾值的大小，確定對應邊的權值，將無限制短路故障模型拓撲圖G＝（，E）化簡成有限制短路故障模型拓撲圖（，），求有限制短路故障模型的最小點覆蓋問題。根據蟻群算法的螞蟻搜索原理，確定連接函數，函數定義式見式（4）：

根據式（4）定義動態啟發函數η，由此推得：

其中，ω表示頂點的權值。

其中，表示啟發式因子，該值越大，螞蟻選擇這個頂點的可能性越大，該值過小容易陷入局部最優解；表示期望啟發因子；是標準參數；是隨機變量，01。

螞蟻在行走時會釋放“信息素”，在最小點覆蓋問題中，螞蟻從一個頂點轉移到另一個頂點是沒有關聯的，因此在螞蟻選擇新的頂點時需要進行更新局部信息素τ，推得的數學定義公式為：

對于子集是否為全局最優解可用式（8）來判斷：

當全部螞蟻群完成所有路徑后，全局信息素會進行更新，推導得到的數學公式可寫為：

算法終止的條件是所有的螞蟻結束循環，輸出，選擇不同的初始點，可以得到不同的覆蓋集，比較得出最小點的覆蓋集。

3 測試向量生成

為驗證基于有限制短路故障模型和蟻群算法相結合的測試向量生成策略的可行性，方案流程如圖2所式，以PCB電路板網絡數23為例進行驗證，通過Protel DXP軟件獲取電路板的結構信息網表，由式（3）計算各網絡之間的短路可能性，通過閾值確定網絡之間的權值，建立網絡近鄰關系如圖3所示，并將其轉變成布爾關系矩陣式，利用矩陣構造初始測試矩陣。與的數學定義公式分別如下：

圖2 蟻群算法求解測試矩陣流程圖Fig.2 Flowchart of solving the test matrix by the ant colony algorithm

圖3 網絡關系拓撲圖Fig.3 Network relationship topological diagram

在初始測試矩陣中，“”代表了無效測試信息，第個列向量代表圖3中n網絡的測試向量，其測試向量中的第位用“1”表示。從圖3中可知，網絡與網絡存在短路的可能，因此初始測試矩陣第一列中第2位屬于有效的測試位，用“0”表示；然而在初始測試矩陣中第二列的第一位也用于檢測網絡與網絡是否短路，造成了測試信息的冗余，需要利用蟻群算法求出最小點覆蓋集，計算結果見表1。根據最小點覆蓋集，對初始測試矩陣進行優化，選取初始測試矩陣中相關列向量，組成新的測試向量矩陣，最后還需確定矩陣中“”元素的具體值。為了滿足檢測固定邏輯故障的要求，最終確定“”值時，需要確保測試矩陣中沒有全“0”或全“1”的行向量，一般通過合理的設定“”的值或增加列向量來滿足測試要求。最終可求得測試矩陣：

表1 蟻群算法求解結果Tab.1 Ant colony algorithm solution results

4 性能分析

在生成的測試向量中，如果存在n和n短路故障特征向量與n無故障網絡的測試響應相同，那么在對電路板進行測試時，就無法判斷n和n網絡之間是否存在故障，即故障征兆誤判。此外，在測試向量中同樣會出現n和n短路故障特征向量與n和n短路故障特征向量相同的情況，這樣也會造成故障無法定位，即故障征兆混淆。

本文提出的測試向量生成方法，有效地結合電路板的結構信息，計算n和n網絡之間出現短路故障的機率，若n和n網絡之間不存在短路可能，就可降低故障誤判率和故障混淆率。為分析本文測試向量生成方法的性能，采用等權值算法、極小權值極大權值相異性算法和本文的算法，依據不同網絡數的電路板進行了仿真實驗。傳統測試矩陣生成算法與本文算法結果對比見表2。

表2 傳統測試矩陣生成算法與本文算法結果比較Tab.2 Comparison of the traditional test matrix generation algorithms and the results of this algorithm

從表2中可以看出，在不同值條件下，本文提出的測試矩陣生成算法，在保證測試完備性指標和緊湊性指標的前提下，具有較低的故障征兆誤判率和故障征兆混淆率。

5 結束語

本文在建立有限制短路故障模型的基礎上，引入蟻群算法，能夠快速、高效地獲取被測電路板的最小網絡覆蓋集，以此生成測試矩陣。實驗結果表明，在閾值假定的前提下，該方法生成的測試矩陣能在保證測試完備性指標的同時擁有良好的緊湊性指標，具有較強的應用價值。