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

康英來，范曉波

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

0 引言

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

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

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

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

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

1 模型與框架

遵循當(dāng)前網(wǎng)絡(luò)分析中的約定，本文將網(wǎng)絡(luò)的邏輯拓?fù)浯婢W(wǎng)絡(luò)實(shí)際拓?fù)洹＿壿嬐負(fù)淇捎蓤DG=(V，L)來表征，其中V為圖的頂點(diǎn)集合、L為圖的邊集合。網(wǎng)絡(luò)拓?fù)渲校旤c(diǎn)vi∈V可以表示物理拓?fù)涞闹鳈C(jī)或路由設(shè)備，而邊li∈L表示頂點(diǎn)之間的單個(gè)鏈路或多條鏈路。不失一般性，假設(shè)網(wǎng)絡(luò)中共有n條鏈路。

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

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

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

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

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

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

2 蟻群算法求解故障鏈路

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

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

蟻群算法的相關(guān)符號定義如下：

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

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

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

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

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

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

當(dāng)所有螞蟻?zhàn)咄耆虝r(shí)，此時(shí)表達(dá)式（3）中的條件y=R⊙x得到滿足，即完成搜索故障鏈路的一次迭代，在下一次迭代開始，更新每條網(wǎng)絡(luò)鏈路的信息素：

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

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

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

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

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

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

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

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

1.輸入網(wǎng)絡(luò)拓?fù)洹⒙酚删仃嘡，路徑測量y；

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

3.隨機(jī)放置螞蟻到各個(gè)探測點(diǎn)，按式（7）初始化各鏈路的信息素濃度；

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

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

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

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

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

3 仿真和性能分析

為了驗(yàn)證本文所提算法的有效性，在真實(shí)的網(wǎng)絡(luò)拓?fù)渖线M(jìn)行試驗(yàn)。網(wǎng)絡(luò)拓?fù)洳捎肦ocketfuel 項(xiàng)目[12]所測量的實(shí)際ISP 骨干網(wǎng)絡(luò)拓?fù)銩S1755。AS1755 是歐洲的骨干網(wǎng)絡(luò)（Ebone），總共含有163 個(gè)路由器和300 條鏈路。所有實(shí)驗(yàn)都是在MATLAB 上編碼完成。

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

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

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

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

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

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

圖2 不同算法進(jìn)行鏈路診斷時(shí)的精度

圖3 不同算法進(jìn)行鏈路診斷時(shí)的召回率

4 結(jié)語

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