基于蟻群算法的網(wǎng)絡層析故障鏈路診斷*

康英來，范曉波

（中國電子科技網(wǎng)絡信息安全有限公司，四川 成都 610000）

0 引言

故障鏈路會帶來網(wǎng)絡服務的中斷，定位網(wǎng)絡中的故障鏈路非常重要，將有助于網(wǎng)絡工程師和因特網(wǎng)服務提供商（Internet Service Provider，ISP）監(jiān)視網(wǎng)絡性能，并提供與客戶約定的服務水平協(xié)議（Service Level Agreement，SLA）相匹配的網(wǎng)絡服務。很多原因都可能導致鏈路故障，除了物理鏈路故障之外，一些如路由器配置錯誤等“軟”錯誤也會導致鏈路連接失敗[1]。

為了定位網(wǎng)絡中的故障鏈路，最直接的方法是在網(wǎng)絡內部節(jié)點部署探針監(jiān)測鏈路性能參數(shù)。然而，出于安全或商業(yè)因素考慮，內部節(jié)點通常是不協(xié)作的，使得直接監(jiān)測變得不可行[2]。近年來，一種叫作網(wǎng)絡層析成像（Network Tomography）的技術[1-4]廣泛應用于鏈路故障診斷中。該技術在網(wǎng)絡邊緣節(jié)點發(fā)送探測包，通過探測包的行為推斷網(wǎng)絡中的鏈路狀態(tài)。由于網(wǎng)絡層析成像僅利用節(jié)點的轉發(fā)行為，不需要內部節(jié)點的合作，因此相對直接測量它具有更廣泛的應用場景。

采用網(wǎng)絡層析技術識別故障鏈路的思路最早由Padmanabhan 和A Coates 等人[2-3]提出。這種框架首先選擇某些邊緣節(jié)點作為探測點，探測點與探測點之間形成探測路徑，然后在探測路徑上發(fā)送探測包。假設網(wǎng)絡中存在一些故障鏈路，顯然經(jīng)過故障鏈路的探測包是不可達的。通常0表示正常（非故障）鏈路，1表示故障鏈路，因而鏈路的狀態(tài)是布爾型的。類似地，探測路徑的狀態(tài)也是布爾型的（即1 表示路徑不可達，0 表示路徑正常）。故障鏈路診斷的目的是從路徑的狀態(tài)推斷鏈路的狀態(tài)，這可建模為一個優(yōu)化問題，即找出最小的鏈路失效集，以解釋探測路徑的狀態(tài)。

然而，這個優(yōu)化問題是多項式復雜程度的非確定性（Nondeterministic Polynomial，NP）完全的[5]。當前文獻廣泛采用貪婪式算法求解。文獻[5]提出一種基于因子圖-和積方法來估計先驗概率；基于同樣的思想，文獻[6]提出一種類似的方法CLINK，聯(lián)立多個路徑狀態(tài)方程估計鏈路故障的先驗概率。然而，由于先驗概率的估計需要長時間的路徑測量，會影響鏈路推斷的實時性。文獻[7]提出了一種線性規(guī)劃（Linear Programming，LP）松弛方法來定位網(wǎng)絡中故障的鏈路，實驗驗證該方法在某些情況下精度較高。文獻[8]提出一種迭代算法TOMO 方法，在每次迭代中選擇失效路徑經(jīng)過最多次數(shù)的鏈路當作故障鏈路。該方法易于實現(xiàn)，容易擴展至大規(guī)模網(wǎng)絡。

不同于上述鏈路故障定位方法，本文提出一種基于蟻群算法的網(wǎng)絡層析故障鏈路診斷框架。蟻群算法最初用來解決旅行商問題（Traveling Salesman Problem，TSP）[9]，后來被引進用來分析普遍意義上的優(yōu)化問題。受它在解決NP 完全問題時具有優(yōu)良解特性的啟發(fā)，本文首次將其引入到網(wǎng)絡故障鏈路診斷。

1 模型與框架

遵循當前網(wǎng)絡分析中的約定，本文將網(wǎng)絡的邏輯拓撲代替網(wǎng)絡實際拓撲。邏輯拓撲可由圖G=(V，L)來表征，其中V為圖的頂點集合、L為圖的邊集合。網(wǎng)絡拓撲中，頂點vi∈V可以表示物理拓撲的主機或路由設備，而邊li∈L表示頂點之間的單個鏈路或多條鏈路。不失一般性，假設網(wǎng)絡中共有n條鏈路。

為了監(jiān)測網(wǎng)絡中的鏈路狀態(tài)，從頂點集合V中選擇一部分節(jié)點S?V（通常為邊緣節(jié)點）作為探測點，探測點與探測點之間形成探測路徑，然后在探測路徑上發(fā)送探測包。令布爾變量yl表示路徑pl的狀態(tài)，布爾變量xk表示鏈路ek的狀態(tài)。此外，約定對于路徑和鏈路均用0 代表正常，用1 代表不可達或故障。顯然，經(jīng)過故障鏈路的探測包始終是不可達的。因此，對于探測路徑pl，有式（1）成立：

其中“∨”表示布爾代數(shù)中的OR 操作，rlk也是布爾變量，表示pl是否經(jīng)過鏈路ek（當且僅當路徑pl經(jīng)過鏈路，rlk取值為1，否則為0）。式（1）的含義顯而易見，即當路徑經(jīng)過任意一條故障鏈路時，則路徑不可達。

假設網(wǎng)絡中共有m條探測路徑。由于對于每條探測路徑都有類似等式（1）成立，為了簡便起見，將m個等式寫成矩陣形式，即有[7]：

式（2）中的每一項都由式（1）確定。其中，y=(y1，y2，…，ym)為m維向量，代表m條探測路徑的狀態(tài)；x=(x1，x2，…，xn)為n維向量，代表n條鏈路的狀態(tài)；R=[rlk]為一個m×n的矩陣；⊙為布爾矩陣中的相乘操作。由于網(wǎng)絡中的路由相對固定，因此鏈路故障診斷便建模為給定布爾向量y和布爾矩陣R，求解布爾向量x。

在實際網(wǎng)絡中，根據(jù)探測路徑不能完全確定鏈路狀態(tài)，式（2）存在多個解。為了得到x的值，轉而求解如下優(yōu)化表達式[6-7]：

然而，求解式（3）是NP 完全的。由于鏈路或路徑的狀態(tài)是布爾型的，式（3）是一個典型的0-1規(guī)劃問題，或者是一個組合優(yōu)化問題。本文嘗試利用蟻群算法求解式（3）得到網(wǎng)絡鏈路狀態(tài)。值得注意的是，不同于將蟻群算法運用到網(wǎng)絡路由尋優(yōu)[10]，本文不是網(wǎng)絡尋路問題，而是將其建模為解決故障鏈路診斷中的優(yōu)化問題。

2 蟻群算法求解故障鏈路

蟻群算法是根據(jù)蟻群覓食行為而得來的一種算法，具有分布計算、信息正反饋（通過信息素）和啟發(fā)式搜索的特征。蟻群算法首次用來解決旅行商問題[9]，后來被引進用來分析普遍意義上的優(yōu)化問題，特別是在解決組合優(yōu)化問題中具有獨特的優(yōu)勢[11]。本文將其引入到網(wǎng)絡故障鏈路診斷框架。

在定位網(wǎng)絡故障鏈路時，首先將螞蟻隨機放置到網(wǎng)絡的各個探測點，然后螞蟻在網(wǎng)絡中進行隨機行走，行走的路線不應違背式（2），即只能在不可達路徑對應的鏈路上行走，螞蟻會在沿途釋放出一種叫做信息素的物質，這種物質會影響后來的螞蟻路線，指導其以較大概率選擇信息素較多的鏈路。如此迭代，最終使得優(yōu)化表達式（3）的優(yōu)化目標變小，從而解決本文的故障鏈路求解問題。

蟻群算法的相關符號定義如下：

Na：螞蟻數(shù)量，螞蟻數(shù)量不宜過大和過小，如果太大則信息素分布太均勻，反之易陷入局部最優(yōu)點，根據(jù)文獻[9]的建議，螞蟻數(shù)量約為網(wǎng)絡節(jié)點數(shù)量的1.5 倍；

Nb：網(wǎng)絡節(jié)點數(shù)；

Q：信息素常數(shù)，表示螞蟻遍歷一次所釋放的信息素總量，值越大，則螞蟻受到信息素選擇鏈路的影響越大，收斂越快，但也容易收斂至局部最優(yōu)點；

τij(t)：在t時刻，網(wǎng)絡節(jié)點i和網(wǎng)絡節(jié)點j之間的信息素濃度（節(jié)點i、j構成網(wǎng)絡里的一條鏈路）；

螞蟻在運動過程中，其運動路線受鏈路上信息素濃度的影響，具體來說，在t時刻，螞蟻k的轉移概率為：

其中α為信息素濃度的指數(shù)參數(shù)；allowk表示螞蟻當前位置下一個可行的網(wǎng)絡鏈路，它需要符合優(yōu)化表達式（3）的優(yōu)化條件，即只能在不可達路徑對應的鏈路上行走，且不包含已經(jīng)經(jīng)過的鏈路。需要注意，在經(jīng)典的蟻群算法中，轉移概率還和啟發(fā)函數(shù)有關。由于在優(yōu)化目標（3）中，所有鏈路權重一樣，因此問題中不應有啟發(fā)函數(shù)。

當所有螞蟻走完全程時，此時表達式（3）中的條件y=R⊙x得到滿足，即完成搜索故障鏈路的一次迭代，在下一次迭代開始，更新每條網(wǎng)絡鏈路的信息素：

每只螞蟻由于走過路徑不一樣，在鏈路上留下的信息素的量也不一樣。經(jīng)過的鏈路數(shù)越少，即表達式（3）的優(yōu)化目標越小，此時應在經(jīng)過的鏈路上留下較多的信息素，以指導后來的螞蟻以較大概率選擇這些鏈路。螞蟻k在網(wǎng)絡節(jié)點i和網(wǎng)絡節(jié)點j之間留下的信息素數(shù)量為：

其中Lk為螞蟻k在本次迭代中經(jīng)過的鏈路數(shù)目。由此可見，若經(jīng)過的鏈路數(shù)目越少（即||x||1的值越?。?，留下的信息素越多，后來的螞蟻更有可能經(jīng)過這些鏈路。

蟻群算法求解故障鏈路的算法流程是在式（4）～式（6）之間迭代，直到滿足最大迭代次數(shù)或狀態(tài)改變少于預設閾值，然后將當前鏈路的信息度濃度按降序排序，逐步選擇排序靠前的鏈路直到滿足式（3）中的優(yōu)化條件，此時所選的鏈路便是算法診斷的故障鏈路。

注意和傳統(tǒng)的蟻群算法相比，求解故障鏈路的蟻群算法在初始放置點和可行路徑上都受約束。蟻群的初始放置點只能放在探測點上，且所有螞蟻必須在不可達路徑對應的鏈路上行走。同樣，一次迭代過程中螞蟻不需要回到最初出發(fā)點，只需其行走的路徑滿足表達式（2）即可。

傳統(tǒng)的蟻群算法在迭代開始前，在所有鏈路上的信息素相等。為了使得算法更快收斂，本文在上述蟻群算法上做如下改進。

在初始時刻，鏈路上的信息素和經(jīng)過該鏈路的不可達路徑數(shù)成正比，即：

其中，nij為經(jīng)過節(jié)點i和節(jié)點j的不可達路徑數(shù)目，c為預設的常數(shù)。通過式（7）設置鏈路的初始濃度后，螞蟻將傾向于選擇被多條不可達路徑經(jīng)過的鏈路。這顯然和優(yōu)化表達式的優(yōu)化目標一致，從而加速算法的收斂。

綜上所述，本文蟻群算法求解故障鏈路的算法流程如下：

1.輸入網(wǎng)絡拓撲、路由矩陣R，路徑測量y；

2.初始化蟻群算法各個參數(shù)；

3.隨機放置螞蟻到各個探測點，按式（7）初始化各鏈路的信息素濃度；

4.對于每只螞蟻，根據(jù)式（4）不斷選擇下一個網(wǎng)絡節(jié)點直到滿足條件（2）；

5.根據(jù)式（5）更新信息素；

6.根據(jù)式（6）更新轉移概率；

7.重復步驟3～步驟6，直到滿足最大迭代次數(shù)；

8.輸出鏈路狀態(tài)x，其中狀態(tài)為1 的鏈路即為故障鏈路。

3 仿真和性能分析

為了驗證本文所提算法的有效性，在真實的網(wǎng)絡拓撲上進行試驗。網(wǎng)絡拓撲采用Rocketfuel 項目[12]所測量的實際ISP 骨干網(wǎng)絡拓撲AS1755。AS1755 是歐洲的骨干網(wǎng)絡（Ebone），總共含有163 個路由器和300 條鏈路。所有實驗都是在MATLAB 上編碼完成。

試驗假設網(wǎng)絡中故障鏈路占比為q，q值表示網(wǎng)絡所遭受的故障級別。實驗仿真在不同的故障級別下算法的性能，設定q從0%到25%。為了診斷網(wǎng)絡中的故障鏈路，設置網(wǎng)絡中度為1 的邊緣節(jié)點為探測節(jié)點，然后在探測節(jié)點間按照最短路徑路由建立探測路徑，由此可建立布爾矩陣R。在探測路徑上發(fā)送探測包，并記錄探測路徑的狀態(tài)，由此可得路徑測量向量y。根據(jù)算法流程表1，即可獲得網(wǎng)絡中的故障鏈路集合。

實驗首先分析了在求解故障鏈路時，改進前的蟻群算法和優(yōu)化初始信息素改進后算法的收斂速度。為了判斷是否收斂，將當次得到的鏈路狀態(tài)和上次迭代得到的鏈路狀態(tài)進行比較。若連續(xù)5 次迭代的鏈路狀態(tài)均一樣，則判定算法已經(jīng)收斂。實驗結果如圖1 所示，可以看出，在定位網(wǎng)絡故障鏈路時，若采用所有鏈路上的信息素相等的初始條件，算法要在150 次后才開始收斂；而采用式（7）改進后的蟻群算法，迭代100 次左右就進入收斂狀態(tài)，從而能夠大幅度減少算法運行時間。

圖1 改進前和改進后的蟻群算法在鏈路故障定位中的收斂速度

同樣地，將本文提出的算法和其他故障鏈路診斷算法進行了比較。由于TOMO 算法[8]簡單易實現(xiàn)且能取得較好結果，它廣泛運用于鏈路故障診斷中。本文采用精度（Precision）和召回率（Recall）兩個性能指標和TOMO 進行比較。精度是預測正確的故障鏈路數(shù)占預測故障鏈路總數(shù)的比例；召回率為預測正確的故障鏈路數(shù)占實際故障鏈路數(shù)的比例。兩者計算如下：

其中，TP為被判定為故障鏈路，而事實上也是故障鏈路的數(shù)目；FP為被判定為故障鏈路，但事實上是正常鏈路的數(shù)目；FN為被判定為正常鏈路，但事實上是故障鏈路的數(shù)目。

實驗結果如圖2 和圖3 所示，分別表示不同算法進行鏈路診斷時的精度和召回率。可以看出，本文方法在性能上相比TOMO 算法有一定改進，尤其是在診斷精度上，且當網(wǎng)絡中故障鏈路較多時，這種優(yōu)勢逐漸明顯。TOMO 方法在迭代時選擇失效路徑經(jīng)過最多次數(shù)的鏈路當作故障鏈路，這種選擇有可能會誤判一些正常鏈路，且這種選擇是不可逆的。本文蟻群算法在選擇時是一種概率選擇，本次迭代的錯誤診斷有可能在下次迭代中被蟻群“修正”。事實上，本文可以在TOMO 算法基礎上進行蟻群算法迭代，即將TOMO 算法的運行結果作為蟻群算法的初始狀態(tài)，從而改進網(wǎng)絡層析中故障鏈路的診斷精度。

圖2 不同算法進行鏈路診斷時的精度

圖3 不同算法進行鏈路診斷時的召回率

4 結語

本文提出了一種新的網(wǎng)絡故障鏈路診斷方法。首先將故障鏈路診斷問題建模成一個0-1 規(guī)劃問題，由于該問題是NP 難的，本文利用蟻群算法在解決組合優(yōu)化問題中獨特的優(yōu)勢，提出基于蟻群算法的故障鏈路診斷方法。不同于傳統(tǒng)的蟻群算法，求解故障鏈路時蟻群在初始放置點和可行路徑上都受約束。本文利用故障鏈路求解中優(yōu)化目標的特性，對蟻群算法的初始信息素濃度進行優(yōu)化，以加快算法的收斂速度。在網(wǎng)絡拓撲中的仿真結果表明，本文算法在故障鏈路檢測中具有較好的精度和召回率。