戴華，林杰

（同濟(jì)大學(xué)經(jīng)濟(jì)與管理學(xué)院，上海 200092）

社會(huì)系統(tǒng)MAS分布仿真中的Agent優(yōu)化調(diào)度算法

戴華，林杰

（同濟(jì)大學(xué)經(jīng)濟(jì)與管理學(xué)院，上海 200092）

針對分布式多Agent系統(tǒng)在復(fù)雜社會(huì)系統(tǒng)仿真應(yīng)用中的運(yùn)算特性，設(shè)計(jì)了一個(gè)基于分布式結(jié)構(gòu)的Agent調(diào)度框架并提出了Agent的動(dòng)態(tài)優(yōu)化調(diào)度算法.該算法綜合考慮了仿真過程中仿真節(jié)點(diǎn)運(yùn)算負(fù)載和Agent通信結(jié)構(gòu)的變化，通過優(yōu)化Agent的調(diào)度和分配實(shí)現(xiàn)各仿真節(jié)點(diǎn)負(fù)載的動(dòng)態(tài)均衡以及多Agent系統(tǒng)中跨節(jié)點(diǎn)全局通信量的減少.仿真實(shí)驗(yàn)分析表明提出的算法能夠有效提高此類仿真應(yīng)用的運(yùn)算性能以及減少仿真執(zhí)行的時(shí)間.

多Agent系統(tǒng)；復(fù)雜系統(tǒng)；分布式仿真；調(diào)度優(yōu)化

1 引言

隨著計(jì)算機(jī)技術(shù)的發(fā)展和廣泛應(yīng)用，在許多復(fù)雜社會(huì)系統(tǒng)（如制造系統(tǒng)，供應(yīng)鏈系統(tǒng)等）的分析和研究中，利用計(jì)算機(jī)進(jìn)行建模與仿真是廣泛使用的一類分析方法和技術(shù)［1-3］.特別是當(dāng)前流行的基于Agent的微觀仿真建模方法，成為了研究復(fù)雜社會(huì)系統(tǒng)的重要方法之一［4，5］.多Agent系統(tǒng)（MAS）能夠?qū)?fù)雜社會(huì)系統(tǒng)中的各個(gè)對象實(shí)體進(jìn)行有效的定義以及功能特性上的模擬，并在計(jì)算機(jī)系統(tǒng)中進(jìn)行仿真實(shí)驗(yàn)，通過實(shí)驗(yàn)的數(shù)據(jù)和評估指標(biāo)對系統(tǒng)運(yùn)作和性能進(jìn)行直觀的量化分析和評價(jià)，具有很好的可重復(fù)性、可試驗(yàn)性、可擴(kuò)展性等優(yōu)點(diǎn).

為適應(yīng)復(fù)雜和更大規(guī)模仿真應(yīng)用的需要，分布式的仿真運(yùn)行架構(gòu)成為必然的選擇.對于基于分布式多Agent系統(tǒng)的仿真應(yīng)用而言，大量參與仿真的Agent由于仿真過程中運(yùn)算量的可變性和不可預(yù)知性，極易會(huì)造成局部某些仿真節(jié)點(diǎn)的運(yùn)算負(fù)載過重，從而影響整個(gè)仿真運(yùn)算的效率甚至使仿真過程崩潰.同時(shí)，在分布式環(huán)境下Agent之間的動(dòng)態(tài)消息通信也會(huì)帶來大量冗余的網(wǎng)絡(luò)通信量而影響仿真的執(zhí)行時(shí)間和效率［6，7］.因此在有限的計(jì)算資源條件下，實(shí)施較大規(guī)模的系統(tǒng)仿真實(shí)驗(yàn)時(shí)，平衡運(yùn)算節(jié)點(diǎn)的負(fù)載并減少節(jié)點(diǎn)間冗余的消息通信成為提高此類系統(tǒng)仿真運(yùn)算效率和性能的關(guān)鍵.在傳統(tǒng)分布式計(jì)算的負(fù)載均衡調(diào)度問題中，主要是針對計(jì)算任務(wù)如何在運(yùn)算節(jié)點(diǎn)間進(jìn)行合理有效地調(diào)度和分配［8，9］，而基于Agent的分布式仿真中，Agent作為運(yùn)算的基本單元和載體，負(fù)載的平衡過程主要依賴于Agent在各個(gè)仿真節(jié)點(diǎn)之間的調(diào)度和分配.此外，在基于Agent的系統(tǒng)仿真中，參與仿真的Agent都是基于某個(gè)特定功能和結(jié)構(gòu)進(jìn)行劃分，并不是同質(zhì)的計(jì)算單元，在仿真過程中不能將一個(gè)Agent的計(jì)算任務(wù)簡單分配給另一個(gè)Agent.同時(shí)，復(fù)雜社會(huì)系統(tǒng)的仿真過程往往是基于離散事件驅(qū)動(dòng)，仿真Agent之間有復(fù)雜的邏輯關(guān)聯(lián)，Agent的行為會(huì)受到其他某些Agent的影響，在不破壞各個(gè)事件邏輯執(zhí)行序列的情況下進(jìn)行Agent的動(dòng)態(tài)調(diào)度也是一個(gè)復(fù)雜的過程.在已有的相關(guān)研究中.如將Agent視為獨(dú)立且相互關(guān)聯(lián)的計(jì)算單元，通過對Agent計(jì)算任務(wù)的進(jìn)行合理調(diào)配實(shí)現(xiàn)任務(wù)的高效執(zhí)行［10，11］.此外，基于某些設(shè)定的計(jì)分規(guī)則來對Agent的移動(dòng)和調(diào)度進(jìn)行判斷的方法［12］被設(shè)計(jì)出來以解決局部計(jì)算資源的過載問題，文獻(xiàn)［6，7，13，14］針對MAS中Agent的消息通信特性，提出了在相關(guān)應(yīng)用中減小和優(yōu)化MAS消息通信的一些方法.經(jīng)濟(jì)市場領(lǐng)域中資源分配的博弈機(jī)制也被用于解決和實(shí)現(xiàn)MAS負(fù)載動(dòng)態(tài)均衡問題［15］.

與傳統(tǒng)的并行與分布式計(jì)算或仿真過程相比，基于多Agent系統(tǒng)的社會(huì)系統(tǒng)仿真具有自身的一些特性.如上所述，目前提出的一些方法中，或是不完全適合基于Agent的社會(huì)系統(tǒng)仿真中的負(fù)載均衡與調(diào)度，如基于任務(wù)分配和調(diào)度的方式；或是在Agent的分配和遷移上沒有充分考慮到Agent之間通信交互的關(guān)聯(lián)性和動(dòng)態(tài)性，此外，普遍采用固定的負(fù)載監(jiān)測閾值來作為負(fù)載調(diào)度的依據(jù)，對仿真過程中復(fù)雜多變負(fù)載狀態(tài)缺乏靈敏性而影響實(shí)施調(diào)度的效果，因此已有的一些方法不能很好地解決此類并行分布式仿真應(yīng)用的負(fù)載均衡和調(diào)度問題.本文針對此類仿真的運(yùn)算特性，綜合考慮了Agent之間的通信結(jié)構(gòu)和各仿真節(jié)點(diǎn)負(fù)載的動(dòng)態(tài)變化，提出了實(shí)施動(dòng)態(tài)負(fù)載調(diào)度的框架及相關(guān)的Agent優(yōu)化調(diào)度算法來提高分布式仿真運(yùn)算的效率和性能.仿真實(shí)驗(yàn)的結(jié)果表明，所提出的算法在總體負(fù)載均衡性和仿真運(yùn)行的時(shí)間上均有較好的表現(xiàn).

2 問題描述

2.1 Agent調(diào)度優(yōu)化問題

在基于分布式Agent的仿真運(yùn)算中，大量Agent散布在不同分布式主機(jī)節(jié)點(diǎn)上，Agent以消息交互的方式進(jìn)行通信和協(xié)作，Agent之間的消息通信因Agent所處節(jié)點(diǎn)位置的不同，包括節(jié)點(diǎn)內(nèi)部的消息通信和跨節(jié)點(diǎn)的消息通信，通過Agent在節(jié)點(diǎn)之間的遷移能夠?qū)崿F(xiàn)這兩種消息通信的轉(zhuǎn)換.由于跨節(jié)點(diǎn)的消息通信在處理時(shí)間的消耗上要遠(yuǎn)大于內(nèi)部的消息通信處理，因此一個(gè)最優(yōu)的Agent調(diào)度分配既要保證各個(gè)仿真節(jié)點(diǎn)不因?yàn)檫^載造成仿真失效，又要最大限度地減少Agent系統(tǒng)中跨節(jié)點(diǎn)的全局網(wǎng)絡(luò)消息通信量，即系統(tǒng)通信負(fù)載.式（1）定義和描述了一個(gè)最優(yōu)的Agent調(diào)度分配應(yīng)滿足的條件，其中σ表示所有節(jié)點(diǎn)運(yùn)算負(fù)載的均方差，Φ表示MAS中跨節(jié)點(diǎn)的Agent通信總量，α是權(quán)重系數(shù)，Wk表示任意某個(gè)節(jié)點(diǎn)的運(yùn)算負(fù)載量，表示所有節(jié)點(diǎn)的平均負(fù)載量，Th是設(shè)定的節(jié)點(diǎn)負(fù)載上限閾值，Cij是任意兩個(gè)不同節(jié)點(diǎn)Hi，Hj之間的通信量，m表示分布式仿真節(jié)點(diǎn)的數(shù)量.

求解滿足上述條件的Agent分布是一個(gè)典型的NP問題，同時(shí)由于仿真運(yùn)行中節(jié)點(diǎn)負(fù)載和Agent交互是動(dòng)態(tài)可變的，特別在Agent數(shù)量相對較多時(shí)，在解空間中求解一個(gè)全局最優(yōu)調(diào)度方案需要消耗大量的計(jì)算時(shí)間，因此無法有效地滿足系統(tǒng)仿真過程中動(dòng)態(tài)實(shí)時(shí)調(diào)度的要求.為了在動(dòng)態(tài)調(diào)度過程中能實(shí)時(shí)地做出合理的Agent調(diào)度和分配，本文通過周期性監(jiān)測及調(diào)度優(yōu)化的方法，利用各周期時(shí)間點(diǎn)相應(yīng)的節(jié)點(diǎn)負(fù)載狀態(tài)與Agent之間的通信結(jié)構(gòu)來實(shí)時(shí)地給出一個(gè)局部優(yōu)化的Agent調(diào)度和分配方案，實(shí)現(xiàn)動(dòng)態(tài)的Agent通信優(yōu)化和節(jié)點(diǎn)負(fù)載均衡，以此提高系統(tǒng)運(yùn)算效率并加快仿真執(zhí)行時(shí)間.

2.2 基于分布式MAS的社會(huì)系統(tǒng)仿真特性

與其他分布式計(jì)算系統(tǒng)類似，基于MAS的社會(huì)系統(tǒng)分布式仿真也是一個(gè)分布式計(jì)算過程.但由于社會(huì)系統(tǒng)的運(yùn)作特性，其仿真運(yùn)算有如下特點(diǎn)：1）由于社會(huì)系統(tǒng)自身結(jié)構(gòu)和功能的復(fù)雜性，仿真運(yùn)算過程中的負(fù)載和Agent之間的通信結(jié)構(gòu)模式較一般運(yùn)算有更高的隨機(jī)性和動(dòng)態(tài)性；2）社會(huì)系統(tǒng)仿真模型中，參與仿真運(yùn)行的Agent往往是具有特定功能和角色的實(shí)體，運(yùn)算任務(wù)在Agent之間不具備一般的傳遞性；3）在基于離散事件驅(qū)動(dòng)的社會(huì)系統(tǒng)的仿真過程中，Agent的調(diào)度和遷移需要協(xié)調(diào)和維護(hù)整個(gè)仿真過程的時(shí)間同步和各個(gè)并發(fā)事件的邏輯順序.

針對上述運(yùn)算特性，在本文設(shè)計(jì)的Agent動(dòng)態(tài)優(yōu)化調(diào)度算法中，進(jìn)行了以下前提條件的假設(shè)：1）仿真Agent在計(jì)算資源使用權(quán)限上是一致的且其運(yùn)算不依賴于某個(gè)特定的仿真節(jié)點(diǎn)；2）Agent之間跨節(jié)點(diǎn)的消息交互時(shí)間遠(yuǎn)大于在節(jié)點(diǎn)內(nèi)部的通信；3）Agent在不同節(jié)點(diǎn)之間移動(dòng)的代價(jià)是相同的.

3 動(dòng)態(tài)負(fù)載均衡調(diào)度算法

3.1 調(diào)度框架

本文設(shè)計(jì)了一個(gè)層次化的分布式Agent調(diào)度框架來實(shí)現(xiàn)對仿真Agent的動(dòng)態(tài)調(diào)度和分配，圖1給出了調(diào)度框架的基本結(jié)構(gòu)，其中全局負(fù)載調(diào)度Agent（GLSA）是進(jìn)行全局調(diào)度和控制的Agent，區(qū)域負(fù)載調(diào)度Agent（DLSA）是分布在各個(gè)仿真節(jié)點(diǎn)上負(fù)責(zé)對應(yīng)節(jié)點(diǎn)區(qū)域調(diào)度操作的Agent.GLSA與各DLSA共同構(gòu)成了層次化的調(diào)度控制結(jié)構(gòu)，分散在各節(jié)點(diǎn)的DLSA執(zhí)行與所在節(jié)點(diǎn)相關(guān)的Agent調(diào)度與分配操作，GLSA則在更高的層面對全局調(diào)度進(jìn)行協(xié)調(diào)，該結(jié)構(gòu)模式有效地分解了實(shí)施調(diào)度控制操作的運(yùn)算任務(wù)，充分發(fā)揮了分布式計(jì)算的優(yōu)點(diǎn).在系統(tǒng)運(yùn)行過程中，GLSA以及分散的DLSA均常駐于對應(yīng)的仿真節(jié)點(diǎn)上，其他參與仿真的Agent則根據(jù)設(shè)計(jì)的調(diào)度分配算法在各仿真節(jié)點(diǎn)之間進(jìn)行動(dòng)態(tài)地調(diào)度.

圖1 Agent層次調(diào)度框架Fig.1The level scheduling framework for agent

在需要進(jìn)行Agent調(diào)度操作時(shí)，提出的算法通過選擇一個(gè)最佳Agent組的方式來實(shí)施Agent在相應(yīng)節(jié)點(diǎn)的調(diào)度遷移，算法定義的Agent組是包含若干Agent的一個(gè)集合，組中Agent的選取充分考慮了當(dāng)前Agent之間的通信關(guān)聯(lián)和聚集性.相比于提出的對Agent進(jìn)行逐個(gè)單獨(dú)選取并遷移的調(diào)度方式，基于選取最佳Agent組的調(diào)度方式不僅能快速有效地降低過載節(jié)點(diǎn)的負(fù)載，還能避免逐個(gè)調(diào)度方法中由于未充分考慮Agent之間的通信結(jié)構(gòu)和關(guān)聯(lián)性而增加額外的跨節(jié)點(diǎn)通信量的情況，從而利用Agent的優(yōu)化調(diào)度最大限度地減少M(fèi)AS中的全局網(wǎng)絡(luò)通信量.框架中動(dòng)態(tài)調(diào)度的實(shí)現(xiàn)主要包括兩個(gè)過程，一個(gè)是在仿真過程中對節(jié)點(diǎn)負(fù)載進(jìn)行周期性監(jiān)測與控制；另一個(gè)是發(fā)生節(jié)點(diǎn)運(yùn)算過載后進(jìn)行Agent的優(yōu)化分配和調(diào)度，該過程包括對過載節(jié)點(diǎn)中最佳遷移Agent組的選取及Agent組向目標(biāo)節(jié)點(diǎn)的遷移. 3.2負(fù)載動(dòng)態(tài)監(jiān)測和調(diào)度控制

負(fù)載動(dòng)態(tài)監(jiān)測過程通過設(shè)定的某個(gè)周期時(shí)間對節(jié)點(diǎn)的負(fù)載狀態(tài)進(jìn)行監(jiān)控，當(dāng)某個(gè)周期監(jiān)測點(diǎn)發(fā)生節(jié)點(diǎn)負(fù)載超過特定閾值時(shí)，將執(zhí)行相應(yīng)的Agent優(yōu)化調(diào)度操作，此時(shí)仿真的邏輯時(shí)間推進(jìn)將暫停，直至整個(gè)調(diào)度過程完成；反之仿真過程將不會(huì)停止.為了能更好的實(shí)現(xiàn)各個(gè)節(jié)點(diǎn)負(fù)載的均衡調(diào)度以提高節(jié)點(diǎn)的計(jì)算效率，本文運(yùn)用了可變閾值的監(jiān)測方法，并利用式（2）給出了可變閾值的定義.其中Th（t）表示在監(jiān)測周期時(shí)間點(diǎn)t的負(fù)載閾值，（t）表示所有節(jié)點(diǎn)在t時(shí)間點(diǎn)的平均負(fù)載值，λ是時(shí)序相關(guān)的負(fù)載平均值的比重系數(shù)，γ是負(fù)載閾值的調(diào)節(jié)系數(shù)，主要是控制可承受的負(fù)載擾動(dòng)范圍.

下面的算法給出了GLSA和各DLSA共同實(shí)施負(fù)載監(jiān)測和控制操作的描述.

步驟1在監(jiān)測時(shí)間周期時(shí)間點(diǎn)t，GLSA接收來自各個(gè)DLSA發(fā)送來的節(jié)點(diǎn)負(fù)載值Wi（t）；

步驟3將各個(gè)仿真節(jié)點(diǎn)按當(dāng)前負(fù)載量的從大到小排列得到負(fù)載狀態(tài)隊(duì)列Q，判斷Q中是否有節(jié)點(diǎn)負(fù)載值大于當(dāng)前的Th（t），如果成立轉(zhuǎn)入步驟4，否則轉(zhuǎn)入步驟7；

步驟4掛起當(dāng)前的仿真推進(jìn)進(jìn)程，并向超過當(dāng)前負(fù)載閾值的仿真節(jié)點(diǎn)的DLSA發(fā)送負(fù)載調(diào)度信息和當(dāng)前負(fù)載狀態(tài)隊(duì)列Q；

步驟5結(jié)合當(dāng)前負(fù)載狀態(tài)隊(duì)列Q，過載節(jié)點(diǎn)的DLSA選擇相應(yīng)的遷移Agent組和遷移目標(biāo)節(jié)點(diǎn)，并將組中的Agent遷移進(jìn)行遷移，實(shí)現(xiàn)負(fù)載的均衡調(diào)度；

步驟6繼續(xù)當(dāng)前仿真運(yùn)算進(jìn)程；

步驟7在下一個(gè)監(jiān)測周期返回步驟1.

3.3 Agent優(yōu)化分配與調(diào)度

如上所述，提出的算法在實(shí)施Agent優(yōu)化調(diào)度時(shí)，采用了基于Agent組的分配和調(diào)度方式.Agent組的選擇則由Agent之間的通信關(guān)聯(lián)度來確定.Agent之間的消息交互是MAS運(yùn)行的基礎(chǔ)和引起系統(tǒng)通信量變化的因素，因此本文中通過Agent之間的消息交互數(shù)量來度量Agent之間的關(guān)聯(lián)程度和Agent內(nèi)部及外部的通信量大小.在式（3）中利用Agent的消息量定義并量化了在兩個(gè)節(jié)點(diǎn)之間遷移某個(gè)Agent組引起的全局通信量變化指標(biāo)，其中mij表示任意兩個(gè)Agent，ai,aj之間的消息通信量，G表示某個(gè)包含若干Agent的備選Agent組，Ai和Aj分別表示對應(yīng)節(jié)點(diǎn)當(dāng)前包含的Agent集合.

由式（3）的定義可知，為盡量減少跨節(jié)點(diǎn)的Agent通信量，在選擇要遷移的Agent組時(shí)，其Δ（G）數(shù)值越大，則表明該組越適合作為實(shí)施調(diào)度遷移的Agent組.因此式（3）可以作為選定最佳遷移Agent組的判定指標(biāo).在下面的算法中給出了當(dāng)需要進(jìn)行負(fù)載調(diào)度操作時(shí)，在對應(yīng)過載節(jié)點(diǎn)中DLSA進(jìn)行目標(biāo)遷移節(jié)點(diǎn)和最佳遷移Agent組選擇的算法步驟：

步驟1利用過載節(jié)點(diǎn)（Hi）當(dāng)前的負(fù)載量（Wi），通過公式OutNum=「（Wi-Th）Ni/Wi」來量化需遷移的Agent數(shù)量；

步驟2在當(dāng)前節(jié)點(diǎn)負(fù)載狀態(tài)隊(duì)列Q中，選取隊(duì)尾負(fù)載最小且未被選擇過的節(jié)點(diǎn)（Hj）作為調(diào)度遷移的目標(biāo)節(jié)點(diǎn)，并結(jié)合Hj當(dāng)前的負(fù)載量Wj用公式InNum=「（Th-Wj）Nj/Wj」計(jì)算Hj可容納的Agent數(shù)量；

步驟3從當(dāng)前過載節(jié)點(diǎn)Hi中選取某個(gè)未被遍歷過的Agent（ai），并將ai放入備選遷移Agent組G′中；

步驟4將與ai關(guān)聯(lián)的所有Agent放入一個(gè)臨時(shí)Agent集合T中；

步驟6將ak從S中取出，并加入G′中，同時(shí)將與ak存在通信關(guān)聯(lián)的且不在G′中的Agent放入臨時(shí)集合T中；

步驟7判斷G′中的Agent數(shù)量是否小于min（InNum,OutNum），若是則轉(zhuǎn)入步驟5，否則將本次得到的備選組G′放入一個(gè)備選組的集合S中；

步驟8如果Hi中的Agent遍歷未完成，則轉(zhuǎn)入步驟3；

步驟9在備選組集合S中查找具有最大Δ（G）值的備選組，并將該組選定為遷移到Hj的Agent組G，并得到本次優(yōu)化調(diào)度的Agent組與目標(biāo)節(jié)點(diǎn)的組合〈G,Hj〉；

步驟10若遷移組G中累計(jì)的Agent的數(shù)量小于OutNum，則返回步驟2.

算法在Agent組中成員Agent的選取上利用了Agent之間的通信關(guān)聯(lián)性以及動(dòng)態(tài)交互結(jié)構(gòu)，通過當(dāng)前的負(fù)載狀態(tài)隊(duì)列信息，并結(jié)合定義的InNum和OutNum來量化平衡各節(jié)點(diǎn)負(fù)載時(shí)所需調(diào)度的Agent數(shù)量，將隊(duì)首過載節(jié)點(diǎn)中的Agent以優(yōu)化分組的形式向負(fù)載相對較輕的隊(duì)尾節(jié)點(diǎn)進(jìn)行調(diào)度遷移.

3.4 算法性能分析

在上述算法實(shí)現(xiàn)中，對目標(biāo)遷移節(jié)點(diǎn)的選擇主要根據(jù)負(fù)載狀態(tài)隊(duì)列來實(shí)現(xiàn)，求解并實(shí)現(xiàn)隊(duì)列的排序計(jì)算時(shí)間主要取決于主機(jī)的數(shù)量，其時(shí)間復(fù)雜度為O（m2）.在最佳Agent組的生成和選擇上，設(shè)ρ=n/m表示節(jié)點(diǎn)的Agent平均密度，其中n,m分別是Agent總數(shù)和節(jié)點(diǎn)數(shù).可知過載節(jié)點(diǎn)中選取Agent組的大小為（1-Th/Wi）ρ，確定最佳Agent組需要對該節(jié)點(diǎn)的所有Agent（數(shù)量為ρ）進(jìn)行遍歷，所以組選擇過程的時(shí)間復(fù)雜度為O（ρ2）.

4 實(shí)驗(yàn)分析

4.1 實(shí)驗(yàn)平臺(tái)

為了驗(yàn)證所提出算法在基于MAS的社會(huì)系統(tǒng)分布式仿真應(yīng)用中的有效性，本文利用面向Agent的編程工具組件JADE開發(fā)了一個(gè)實(shí)驗(yàn)平臺(tái)，該平臺(tái)用于實(shí)施基于多Agent的供應(yīng)鏈場景模型的運(yùn)作過程仿真，同時(shí)實(shí)驗(yàn)平臺(tái)利用設(shè)計(jì)的GLSA及DLSA來實(shí)現(xiàn)層次化的動(dòng)態(tài)調(diào)度算法，其中實(shí)現(xiàn)算法所涉及的Agent基本功能屬性如消息交互以及遷移等都繼承JADE組件提供的底層功能接口.在平臺(tái)中有五種類型的仿真Agent來構(gòu)建供應(yīng)鏈仿真模型，其中包括生產(chǎn)制造Agent，生產(chǎn)計(jì)劃Agent，庫存Agent，運(yùn)輸Agent以及運(yùn)輸計(jì)劃Agent.在實(shí)驗(yàn)分析中，用于實(shí)施仿真實(shí)驗(yàn)的不同規(guī)模和結(jié)構(gòu)的供應(yīng)鏈場景MAS模型都由繼承這五種Agent類型的若干仿真Agent構(gòu)成.

在供應(yīng)鏈場景的MAS模型中包括了由仿真Agent組成的若干供應(yīng)商、生產(chǎn)商以及分銷商，模型的仿真過程是基于離散事件驅(qū)動(dòng)，模擬供應(yīng)鏈場景模型完成一定數(shù)量的產(chǎn)品訂單的過程.在仿真時(shí)各分銷商給出一定數(shù)量的訂貨量需求，模型在訂單驅(qū)動(dòng)下開始運(yùn)作，各生產(chǎn)商利用供應(yīng)商提供的原材料根據(jù)自身的生產(chǎn)線進(jìn)行產(chǎn)品生產(chǎn)，原材料及產(chǎn)品在供應(yīng)商、生產(chǎn)商及分銷商之間運(yùn)輸，當(dāng)各個(gè)分銷商的訂貨量滿足后仿真過程結(jié)束.仿真過程中參與仿真的Agent根據(jù)各自的角色功能自適應(yīng)地交互和協(xié)作，各仿真Agent的事件活動(dòng)運(yùn)用保守時(shí)間管理機(jī)制來推進(jìn)，直至完成設(shè)定的模型場景任務(wù).在這個(gè)過程中，由于仿真邏輯時(shí)間的推進(jìn)以及仿真Agent各自運(yùn)行狀態(tài)，Agent之間的相互通信關(guān)系和運(yùn)算負(fù)載都會(huì)動(dòng)態(tài)地變化.

4.2 仿真實(shí)驗(yàn)的環(huán)境和參數(shù)設(shè)定

在仿真實(shí)驗(yàn)中利用十臺(tái)互聯(lián)的主機(jī)組成分布式仿真節(jié)點(diǎn)實(shí)施仿真分析實(shí)驗(yàn)，其中一臺(tái)機(jī)器作為中心控制節(jié)點(diǎn)，其他主機(jī)作為仿真運(yùn)行節(jié)點(diǎn).在仿真監(jiān)測中，節(jié)點(diǎn)的負(fù)載狀態(tài)利用公式Wi=βUc+（1-β）Um,0＜β＜1度量，其中Uc和Um分別是主機(jī)的CPU和內(nèi)存的使用率，β為兩者之間的權(quán)重系數(shù).根據(jù)仿真實(shí)驗(yàn)環(huán)境和不同仿真模型，在表1中給出了實(shí)驗(yàn)中實(shí)施調(diào)度算法所設(shè)定的各個(gè)參數(shù)值，其中監(jiān)測間隔周期根據(jù)仿真規(guī)模在30～60s之間進(jìn)行調(diào)整.

表1 實(shí)驗(yàn)參數(shù)設(shè)定Table 1Parameters in experiments

4.3 實(shí)驗(yàn)對比分析

實(shí)驗(yàn)分析主要從負(fù)載均衡性能和仿真執(zhí)行時(shí)間的消耗兩個(gè)方面，對所提出的優(yōu)化調(diào)度算法進(jìn)行檢驗(yàn).實(shí)驗(yàn)中引入了靜態(tài)Agent均勻分布方法作為參照方法與所提出算法進(jìn)行對比分析.參照方法在仿真執(zhí)行前將所有仿真Agent隨機(jī)地平均分配到不同節(jié)點(diǎn)上，且仿真過程中不進(jìn)行Agent的動(dòng)態(tài)調(diào)度.由式（2）中對負(fù)載均方差的定義可知，負(fù)載值均方差σ的數(shù)值越小，說明在仿真過程中各節(jié)點(diǎn)的計(jì)算負(fù)載具有較好的均衡性和較小的波動(dòng)，計(jì)算資源的綜合利用率就越高，同時(shí)節(jié)點(diǎn)的過載風(fēng)險(xiǎn)也相應(yīng)降低，因此σ值可作為分布式節(jié)點(diǎn)綜合運(yùn)算性能的一個(gè)有效指標(biāo).在圖2中將本文提出的算法（PA）和引入的參照方法（RA）在負(fù)載均衡性能方面進(jìn)行了對比.

圖2（a）給出了在上述兩種情形下，同一仿真模型的仿真運(yùn)行過程中各節(jié)點(diǎn)的負(fù)載值均方差σ隨監(jiān)測周期時(shí)間點(diǎn)變化的σ值.從圖中可以看到，在整個(gè)仿真運(yùn)行過程中使用提出的動(dòng)態(tài)調(diào)度算法后得到的σ值總體上要低于作為對比的參照方法，且該數(shù)值的波動(dòng)也相對較小.此外，在圖2（b）中給出了在兩種情形下，針對不同Agent規(guī)模（NAgent）的仿真模型，對應(yīng)的整個(gè)仿真過程中得到所有σ值的平均值（σav）變化.圖中σav的變化趨勢表明，隨著仿真Agent規(guī)模的增加，在整個(gè)仿真過程中兩種情況下的σav都呈逐步下降趨勢，但在PA情形下的σav總體上低于RA情形下的數(shù)值，這說明實(shí)施了提出的優(yōu)化調(diào)度算法有更好的全局負(fù)載均衡性.

圖2 負(fù)載均衡性能分析Fig.2 The analysis of load balancing performance

圖3對上述兩種情況下的仿真運(yùn)行時(shí)間進(jìn)行了對比分析，圖中給出了在不同Agent仿真規(guī)模NAgent下提出算法（PA）與參照方法（RA）的仿真執(zhí)行時(shí)間的比值η（η=TPA：TRA）變化趨勢.在Agent規(guī)模較小時(shí)，兩者的執(zhí)行時(shí)間比值接近且約大于1，表明此時(shí)兩者的仿真時(shí)間消耗比較接近，但PA情形下的時(shí)間消耗稍多，這是由于在動(dòng)態(tài)調(diào)度算法中對Agent組選取和遷移操作會(huì)產(chǎn)生額外的時(shí)間消耗，執(zhí)行優(yōu)化調(diào)度后減少的時(shí)間消耗無法從總體上抵消算法產(chǎn)生的時(shí)間消耗.但隨著仿真Agent規(guī)模的增大及相互通信增多，所提出算法在仿真執(zhí)行時(shí)間上的占比開始逐漸減少，圖中可以看到PA與RA的仿真執(zhí)行時(shí)間比值η呈逐步下降趨勢.這表明在相對較大的Agent規(guī)模下，優(yōu)化調(diào)度后減少的時(shí)間消耗逐漸彌補(bǔ)了調(diào)度過程本身產(chǎn)生的時(shí)間消耗，并使總的仿真時(shí)間得到有效降低.因此運(yùn)用提出的動(dòng)態(tài)優(yōu)化調(diào)度算法在總的執(zhí)行時(shí)間上也有明顯的改善.

圖3 仿真時(shí)間比值η（η=TPA：TRA）與Agent規(guī)模NAgent的關(guān)系Fig.3The relationship between simulation time-ratio η（η=TPA：TRA）and Agent scale NAgent

5 結(jié)束語

基于多Agent系統(tǒng)的計(jì)算機(jī)仿真方法在社會(huì)系統(tǒng)分析和研究中越來越普遍，提高此類仿真應(yīng)用的分析能力和運(yùn)算效率變得十分重要.本文針對基于多Agent系統(tǒng)的分布式仿真運(yùn)算特性，提出了一個(gè)優(yōu)化Agent分配的動(dòng)態(tài)調(diào)度算法實(shí)現(xiàn)各仿真節(jié)點(diǎn)的負(fù)載均衡以及全局通信結(jié)構(gòu)的優(yōu)化.該算法綜合考慮了仿真過程中仿真節(jié)點(diǎn)的負(fù)載狀態(tài)和MAS通信結(jié)構(gòu)的動(dòng)態(tài)變化，設(shè)計(jì)了相應(yīng)的可變負(fù)載閾值監(jiān)測和基于Agent組選擇和遷移的優(yōu)化調(diào)度方法.通過仿真實(shí)驗(yàn)對比分析，提出的方法在仿真運(yùn)行時(shí)間和負(fù)載均衡性能上均要優(yōu)于作為實(shí)驗(yàn)對比的靜態(tài)Agent隨機(jī)均勻分配的方法.文中提出的方法對于相關(guān)的基于分布式多Agent的仿真和運(yùn)算系統(tǒng)也有一定的借鑒性.此外，當(dāng)前算法設(shè)計(jì)中對一些相關(guān)前提條件進(jìn)了簡化和限定，如Agent運(yùn)算依附性、Agent遷移代價(jià)以及異質(zhì)跨網(wǎng)段環(huán)境等，同時(shí)，Agent遷移機(jī)制設(shè)計(jì)與優(yōu)化對于提升MAS運(yùn)算的執(zhí)行性能也有著一定影響，在今后的研究工作中，將會(huì)進(jìn)一步考慮這些相關(guān)因素對算法進(jìn)行改進(jìn)和完善.

［1］盛昭瀚，張維.管理科學(xué)研究中的計(jì)算實(shí)驗(yàn)方法［J］.管理科學(xué)學(xué)報(bào)，2011，14（5）：1-10.

Sheng Zhaohan，Zhang Wei.Computational experiments in management science and research［J］.Journal of Management Sciences in China，2011，14（5）：1-10.（in Chinese）

［2］劉曉平，唐益明，鄭利平.復(fù)雜系統(tǒng)與復(fù)雜系統(tǒng)仿真研究綜述［J］.系統(tǒng)仿真學(xué)報(bào)，2008，20（23）：6303-6315.

Liu Xiaoping，Tang Yiming，Zheng Liping.Survey of complex system and complex system simulation［J］.Journal of System Simulation，2008，20（23）：6303-6315.（in Chinese）

［3］Lee J H，Kim C O.Multi-agent systems applications in manufacturing systems and supply chain management：A review paper［J］. International Journal of Production Research，2008，46（1）：233-265.

［4］李英，馬壽峰.基于Agent的仿真系統(tǒng)建模［J］.系統(tǒng)工程學(xué)報(bào)，2006，21（3）：225-231.

Li Ying，Ma Shoufeng.Modeling of agent-based simulation system［J］.Journal of Systems Engineering，2006，21（3）：225-231.（inChinese）

［5］張少蘋，戴鋒，王成志，等.多Agent系統(tǒng)研究綜述［J］.復(fù)雜系統(tǒng)與復(fù)雜性科學(xué)，2011，8（4）：1-8.

Zhang Shaoping，Dai Feng，WangChengzhi，et al.Summary on research ofmulti-agentsystem［J］.ComplexSyatemsand Complexity Science，2011，8（4）：1-8.（in Chinese）

［6］Boukerche A，Das S K.Reducing null messages overhead through load balancing in conservative distributed simulation systems［J］. Journal of Parallel and Distributed Computing，2004，64（3）：330-344.

［7］Jang M W，Agha G.Adaptive agent allocation for massively multi-agent applications［C］//Ishida T，Gasser L，Nakashima H.Massively Multi-Agent Systems I.Berlin，Heidelberg：Springer，2005：25-39.

［8］GrosuD，ChronopoulosAT.Noncooperativeloadbalancingindistributedsystems［J］.JournalofParallelandDistributedComputing，2005，65（9）：1022-1034.

［9］Zhang Z，F(xiàn)an W.Web server load balancing：A queueing analysis［J］.European Journal of Operational Research，2008，186（2）：681-693.

［10］Oguara T，Chen D，Theodoropoulos G K，et al.An adaptive load management mechanism for distributed simulation of multiagent systems［C］//Proceedings of the 9th IEEE International Symposium on Distributed Simulation and Real-Time Applications，Montreal.Canada，2005：179-186.

［11］Ha B H，Bae J，Park Y T，et al.Development of process execution rules for workload balancing on agents［J］.Data&Knowledge Engineering，2006，56（1）：64-84.

［12］Chow K P，Kwok Y K.On load balancing for distributed multi-agent computing［J］.IEEE Transactions on Parallel and Distributed Systems，2002，13（8）：787-801.

［13］De Grande R E，Boukerche A.Dynamic partitioning of distributed virtual simulations for reducing communication load［C］//Haptic Audio visual Environments and Games，2009（HAVE 2009）.IEEE International Workshop on，IEEE，2009：176-181.

［14］Gonzalez-Pardo A，Varona P，Camacho D.Optimal message interchange in a self-organizing multi-agent system［C］//Proceedings of the 4th International Symposium on Intelligent Distributed Computing.Tangier，Morocco，2010，315：131-141.

［15］Ham M J，Agha G.Market-based coordination strategies for large-scale multi-agent systems［J］.System and Information Sciences Notes，2007，2（1）：126-131.

Algorithm for Agent optimal dispatching in MAS distributed simulations of social system

Dai Hua，Lin Jie

（School of Economy&Management，Tongji University，Shanghai 200092，China）

Accordingtothespecificcomputationalcharacteristicsofagent-basedapplicationsincomplexsocial systems，a distributed agent scheduling architecture is designed and algorithms for dynamic agent scheduling optimization are proposed.The algorithm takes into account the variation of both computation and communication during the simulation process，which implements the dynamic load balancing of each simulation node and the decrease of the overall agent communication that crosses nodes by means of optimizing the agent distribution and scheduling.The experimental results indicate that the proposed algorithms can effectively improve the computational performance and shorten the run-time of such simulation applications.

multi-Agent system（MAS）；complex system；distributed simulation；scheduling optimization

TP391.9

A

1000-5781（2015）06-0844-08

10.13383/j.cnki.jse.2015.06.012

戴華（1981-），男，湖南澧縣人，博士生，研究方向：分布式多Agent系統(tǒng)，系統(tǒng)仿真與建模等，Email：dh_myemail@126.com；

2013-11-14；

2014-09-04.

國家自然科學(xué)基金資助項(xiàng)目（71071114）；教育部社科支撐資助項(xiàng)目（11YJC630216）；上海市重點(diǎn)學(xué)科建設(shè)資助項(xiàng)目（B310）.

林杰（1967-），男，四川渠縣人，教授，博士生導(dǎo)師，研究方向：信息管理與信息系統(tǒng)，供應(yīng)鏈管理，決策支持系統(tǒng)等，Email：linjie@#edu.cn.