摘要：隨著應急指揮網(wǎng)絡系統(tǒng)規(guī)模不斷增加，網(wǎng)絡故障診斷逐漸成為應急指揮網(wǎng)絡系統(tǒng)的關鍵。針對域間協(xié)同故障診斷中的任務分配問題，提出了基于改進合同網(wǎng)的Agent動態(tài)任務分配算法，建立了Agent性能庫，使管理者根據(jù)所注冊Agent的性能進行發(fā)標，同時，為每個執(zhí)行Agent完成某項任務建立相應的信息素，實驗結果表明，該算法有效地避免了網(wǎng)絡的擁塞，提高了任務分解的效率。

關鍵詞：協(xié)同網(wǎng)絡故障診斷；任務分配；合同網(wǎng)算法；蟻群算法

中圖分類號：TP393 文獻標識碼：A 文章編號：1009-3044（2014）05-0919-03

1 概述

隨著應急指揮網(wǎng)絡系統(tǒng)復雜程度不斷提高，系統(tǒng)規(guī)模將越來越大。這就造成應急指揮系統(tǒng)中網(wǎng)絡的規(guī)模越來越大，功能越來越復雜，加之網(wǎng)絡攻擊技術與計算機病毒，使得網(wǎng)絡故障的發(fā)生是不可避免的，而且發(fā)生的概率會越來越大，網(wǎng)絡故障診斷逐漸成為應急指揮系統(tǒng)的關鍵。目前采用的故障診斷技術及方法無法滿足應急指揮系統(tǒng)故障測試與診斷的要求。這時就需要協(xié)同故障診斷技術為網(wǎng)絡系統(tǒng)提供更完備的綜合保障支持。協(xié)同故障診斷技術包括任務分解，任務分配和決策融合等環(huán)節(jié)[1]。該文重點研究了其中的任務分配，提出了基于改進合同網(wǎng)的Agent動態(tài)任務分配算法，有效地避免了網(wǎng)絡的擁塞，提高了協(xié)同故障診斷效率。

2 動態(tài)合同網(wǎng)算法

本文將管理Agent替代合同網(wǎng)算法的管理者，將執(zhí)行Agent替代合同網(wǎng)算法的承包商完成合同網(wǎng)算法在Multi-Agent協(xié)同故障診斷中的應用，如圖1所示。

圖1 合同網(wǎng)在MAS中的應用

傳統(tǒng)合同網(wǎng)在MAS中的直接應用缺點較多，該文根據(jù)傳統(tǒng)合同網(wǎng)算法的缺點提出了一下幾點改進：

1） 減小管理Agent發(fā)標量。建立Agent性能庫，使管理者根據(jù)所注冊Agent的性能進行發(fā)標，避免了管理Agent廣播標書帶來的通信擁塞。

2） 與蟻群算法相結合。為每個執(zhí)行Agent完成某項任務建立相應的信息素，這樣就可以形成正反饋，管理Agent就可以根據(jù)前期經(jīng)驗進行任務分配。

3） 任務結果評估。傳統(tǒng)合同網(wǎng)算法沒有任務結果評估，該文將任務結果評估納入到合同網(wǎng)算法中來，實現(xiàn)了系統(tǒng)的反饋。

2.1注冊Agent性能庫

管理者對每個注冊Agent的能力都有一個數(shù)據(jù)庫，例如Agent i執(zhí)行任務j的能力為[Cap（i，j）]。有能力執(zhí)行任務的Agent將其初始能力值設為1，沒有能力執(zhí)行任務的Agent將其初始能力值設為0，這樣就以數(shù)據(jù)庫中的表的形式建立了Agent性能庫。

設置性能庫的本質是為了讓管理者能夠將任務分配給能夠勝任的承包商執(zhí)行，以減少資源耗費。所以有了注冊承包商性能庫，就可以根據(jù)性能庫分發(fā)任務，這樣就避免了傳統(tǒng)合同網(wǎng)算法使用廣播帶來的通信量大的問題，有效避免的通信擁塞。

在合同網(wǎng)算法里，沒有絕對的管理者，也沒有絕對的承包商，它們之間是相互轉化的，所以每一個有注冊承包商的管理者都有性能庫，而且性能庫分為兩部分：一部分為管理部分；另一部分為執(zhí)行部分（執(zhí)行部分只有自己的性能），如圖2所示。

2.2 Agent信息素

傳統(tǒng)合同網(wǎng)算法在競標階段執(zhí)行Agent只要發(fā)現(xiàn)自己符合任務要求就會向管理Agent發(fā)送競標標書，而且管理Agent會對每一個標書進行評估，這樣就會導致管理Agent的負載過大，影響整個系統(tǒng)的效率。該文從減小執(zhí)行Agent投送競標標書的數(shù)量的角度出發(fā)，提高了執(zhí)行Agent的自主性和競爭性，引入蟻群算法的螞蟻信息素，對可執(zhí)行任務的Agent進行進一步的尋優(yōu)。

當管理Agent有一個任務i要進行分配時，將會有若干個執(zhí)行代理可以執(zhí)行，所以就引出了最優(yōu)問題。為了讓任務分配趨于最佳合理狀態(tài)，引入了螞蟻的信息素，并將蟻群算法中的轉移概率公式改進為所需的代理i執(zhí)行任務j的效果概率公式，如下式。

[P ij（t）= [τij（t）]α×[Tij（t）]βZ? capable[τzj（t）]α×[Tzj（t）]β T（i，j） ≠N 0 Otherwise] （1）

其中[P ij（t）]表示t時刻，代理i執(zhí)行完任務j后，在所有執(zhí)行代理中的執(zhí)行效果優(yōu)劣概率；[τ（i，j）]為t時刻代理i執(zhí)行任務j的信息素值；capable為能夠執(zhí)行任務j的代理的集合；[T（i，j）]為t時刻代理i執(zhí)行任務j的執(zhí)行時間的倒數(shù)，即：

[T（i，j）=1Tc+Td] （2）

其中[Tc]為任務的完成時間；[Td]為代理i到代理j的延遲時間，單位毫秒（ms）。

依據(jù)以上公式（1）算出每一個執(zhí)行Agent執(zhí)行任務j的完成優(yōu)劣的概率，概率越大，該Agent完成任務j的效果就越好。所以本文根據(jù)[P ij（t）]的大小選擇概率大的執(zhí)行任務j，這樣既保證了任務的完成質量和效率，又減小了系統(tǒng)的通信量和負載。

針對算法中信息素和參數(shù)是動態(tài)的這一特點，為了保證全局尋優(yōu)，該文利用輪轉賭法選擇出來的Agent執(zhí)行任務。輪轉賭法是模仿輪盤轉動進行選擇[5]，如圖3所示，將各Agent執(zhí)行任務完成的優(yōu)劣概率在賭輪上劃分成扇形區(qū)域，然后轉動輪盤，使其隨機轉動。當輪盤停止轉動時，指針所指向的扇區(qū)就是所要選擇執(zhí)行任務的Agent。所以完成優(yōu)劣概率大，被選中的幾率就大。被選中的概率與完成優(yōu)劣概率成正比。

圖3 輪轉賭法

利用上述的輪轉賭法可以選擇完成能力優(yōu)秀的Agent來執(zhí)行任務j，顯著提高了任務完成的效率。如果通過輪轉賭法選擇的Agent沒有完成任務，那么會繼續(xù)通過輪轉賭法選擇Agent執(zhí)行任務，直到任務完成為止。

當任務完成后，會執(zhí)行對執(zhí)行任務的Agent信息素進行更新，更新的公式為：

[τij（t+Δ t） = 1-ρ τij（t） + τij（Δ t）] （3）

[τij（Δ t）=Q（Tc+Td）] （4）

其中[τij（t+Δ t）]為[（t+Δ t）]時刻Agent i完成任務j的信息素值；[τij（Δ t）]表示完成任務的Agent信息素增量，初始時刻[τij（Δ t）=0]；[ρ（0≤ρ<1）]為信息素揮發(fā)系數(shù)，[（1-ρ）]表示信息素的殘留因子；Q為常量，表示螞蟻所釋放的信息素量為Q。

根據(jù)上述公式可以將信息素更新，這樣就可以將完成能力優(yōu)秀的Agent找出，并且也可以根據(jù)信息素的大小來判定執(zhí)行Agent執(zhí)行某一任務的效率。

2.3 算法描述

1） 算法的初始化階段，將所有數(shù)據(jù)進行初始化，包括[τ0]，ρ，Q，[Td]。

2） 定期測試網(wǎng)絡延遲，以此來更新延遲時間[Tc]；更新注冊Agent性能庫的性能參數(shù)[Cap（i，j）]，管理Agent下的注冊Agent會定期上報更新其性能參數(shù)[Cap（i，j）]。

3） 管理代理根據(jù)注冊Agent性能庫來確定能執(zhí)行任務的執(zhí)行Agent。

4） 利用公式（1）計算已選Agent的完成概率，然后進行排序。

5） 利用輪轉賭法在可選執(zhí)行Agent中選擇要執(zhí)行任務的Agent，并在可選執(zhí)行Agent表中去除，然后向執(zhí)行Agent下發(fā)標書。如果執(zhí)行Agent投標則跳到6），否則重復本步驟。

6） 管理Agent接受到投標的執(zhí)行Agent分發(fā)任務，然后等待執(zhí)行結果。

7） 執(zhí)行Agent執(zhí)行完任務后，上報管理Agent，并更新完成時間[Td]，并更新信息素[τij（t） ]。

2.4 算法的效率

假設一個Multi-Agent系統(tǒng)由管理Agent和n個執(zhí)行Agent組成。傳統(tǒng)的合同網(wǎng)采用廣播式發(fā)送標書，則Agent之間進行一次通信所需要的時間設為[Tm]，管理者Agent的評估時間設為[Tp]，Agent完成任務的時間設為[Tc]。則傳統(tǒng)合同網(wǎng)總的時間耗費為[T1=3Tm+nTc+Tp]。而改進后的評估時間[Tj]，因為能力庫的建立只對由能力完成任務的Agent進行評估，所以將會大大減少評估的時間，雖然需要計算完成優(yōu)劣的概率，但是相較于評估標書減少，對評估時間的影響極小。設改進后算法參加評估的Agent的數(shù)量為[αn （0<α<1）]，則[αn Tj

3 仿真分析

本文根據(jù)協(xié)同故障診斷的需求搭建了如下的仿真環(huán)境。該仿真環(huán)境共有10臺計算機。其中由1臺管理Agent計算機，1臺交換機，10臺執(zhí)行Agent計算機。其中5臺安裝Linux，5臺安裝Windows XP。參數(shù)的設置為：a=1，b=5，r=0.1，Q=1000，tij（0）=1，[Td=500]。

將仿真平臺的所有電腦安裝上帶有專家系統(tǒng)的Agent，并建立為每個Agent建立能力數(shù)據(jù)庫和信息素數(shù)據(jù)庫。給予管理Agent 一個由20個任務（例如：鏈路診斷，網(wǎng)卡故障診斷，交換機端口診斷等）組成的復雜任務，在這20個任務中有執(zhí)行Agent可以執(zhí)行有的不可以，每臺電腦的執(zhí)行時間也不同。最后按照傳統(tǒng)合同網(wǎng)算法和動態(tài)合同網(wǎng)算法進行任務分配，對20個任務進行30次分配，仿真結果如圖4所示。

圖4 仿真結果

從圖中可以看出，改進后的合同網(wǎng)算法完成任務的總時間明顯小于傳統(tǒng)合同網(wǎng)算法，提高了任務分解的效率；改進后合同網(wǎng)算法的完成總時間波動性較小，增加了任務分解的穩(wěn)定性。反觀傳統(tǒng)合同網(wǎng)算法完成任務總時間較大，且有較大的波動性，算法的效率較低。

4 總結

針對域間協(xié)同故障診斷中傳統(tǒng)MAS任務分配算法的不足和傳統(tǒng)合同網(wǎng)算法的缺點，提出了動態(tài)合同網(wǎng)算法，提高了算法的效率，仿真結果表明，該算法有效地避免了網(wǎng)絡的擁塞，提高了協(xié)同故障診斷效率。但是，協(xié)同故障診斷中任務的決策融合研究的較少，將是下一步研究的重點。

參考文獻：

[1] 王爽.遠程協(xié)同故障診斷任務執(zhí)行路徑規(guī)劃[J]. 計算機測量與控制，2011，19（8）：1814-1816.

[2] 楊件，李文立，洪春宇.基于閾值和可用度的合同網(wǎng)協(xié)議改進方案研究.計算機集成制造系統(tǒng)， 2009，15（5）：1016-1022.

[3] 龍濤，沈林成，朱華勇，等.面向協(xié)同任務的多UCAV分布式任務分配與協(xié)調技術.自動化學報，2007，33（7）：731-737.

[4] Guo Shao-sheng， Meng You-xin. An improved entropy-based ant colony optimization algorithm， 2010 International Conference on Computer Application and System Modeling， Proceedings，2010， 15：1548-1550.

[5] 劉剛，何麟書.雙賭輪選擇遺傳算法. 北京航空航天大學學報，2005，31（8）：930-933.