基于動(dòng)態(tài)合同網(wǎng)的Agent任務(wù)分配算法

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

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

中圖分類號(hào)：TP393 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2014）05-0919-03

1 概述

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

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

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

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

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

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

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

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

2.1注冊(cè)Agent性能庫(kù)

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

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

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

2.2 Agent信息素

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

當(dāng)管理Agent有一個(gè)任務(wù)i要進(jìn)行分配時(shí)，將會(huì)有若干個(gè)執(zhí)行代理可以執(zhí)行，所以就引出了最優(yōu)問題。為了讓任務(wù)分配趨于最佳合理狀態(tài)，引入了螞蟻的信息素，并將蟻群算法中的轉(zhuǎn)移概率公式改進(jìn)為所需的代理i執(zhí)行任務(wù)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時(shí)刻，代理i執(zhí)行完任務(wù)j后，在所有執(zhí)行代理中的執(zhí)行效果優(yōu)劣概率；[τ（i，j）]為t時(shí)刻代理i執(zhí)行任務(wù)j的信息素值；capable為能夠執(zhí)行任務(wù)j的代理的集合；[T（i，j）]為t時(shí)刻代理i執(zhí)行任務(wù)j的執(zhí)行時(shí)間的倒數(shù)，即：

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

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

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

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

圖3 輪轉(zhuǎn)賭法

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

當(dāng)任務(wù)完成后，會(huì)執(zhí)行對(duì)執(zhí)行任務(wù)的Agent信息素進(jìn)行更新，更新的公式為：

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

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

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

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

2.3 算法描述

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

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

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

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

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

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

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

2.4 算法的效率

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

3 仿真分析

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

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

圖4 仿真結(jié)果

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

4 總結(jié)

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

參考文獻(xiàn)：

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

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

[3] 龍濤，沈林成，朱華勇，等.面向協(xié)同任務(wù)的多UCAV分布式任務(wù)分配與協(xié)調(diào)技術(shù).自動(dòng)化學(xué)報(bào)，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] 劉剛，何麟書.雙賭輪選擇遺傳算法. 北京航空航天大學(xué)學(xué)報(bào)，2005，31（8）：930-933.