戴華,林杰
(同濟大學經濟與管理學院,上海 200092)
社會系統MAS分布仿真中的Agent優化調度算法
戴華,林杰
(同濟大學經濟與管理學院,上海 200092)
針對分布式多Agent系統在復雜社會系統仿真應用中的運算特性,設計了一個基于分布式結構的Agent調度框架并提出了Agent的動態優化調度算法.該算法綜合考慮了仿真過程中仿真節點運算負載和Agent通信結構的變化,通過優化Agent的調度和分配實現各仿真節點負載的動態均衡以及多Agent系統中跨節點全局通信量的減少.仿真實驗分析表明提出的算法能夠有效提高此類仿真應用的運算性能以及減少仿真執行的時間.
多Agent系統;復雜系統;分布式仿真;調度優化
隨著計算機技術的發展和廣泛應用,在許多復雜社會系統(如制造系統,供應鏈系統等)的分析和研究中,利用計算機進行建模與仿真是廣泛使用的一類分析方法和技術[1-3].特別是當前流行的基于Agent的微觀仿真建模方法,成為了研究復雜社會系統的重要方法之一[4,5].多Agent系統(MAS)能夠對復雜社會系統中的各個對象實體進行有效的定義以及功能特性上的模擬,并在計算機系統中進行仿真實驗,通過實驗的數據和評估指標對系統運作和性能進行直觀的量化分析和評價,具有很好的可重復性、可試驗性、可擴展性等優點.
為適應復雜和更大規模仿真應用的需要,分布式的仿真運行架構成為必然的選擇.對于基于分布式多Agent系統的仿真應用而言,大量參與仿真的Agent由于仿真過程中運算量的可變性和不可預知性,極易會造成局部某些仿真節點的運算負載過重,從而影響整個仿真運算的效率甚至使仿真過程崩潰.同時,在分布式環境下Agent之間的動態消息通信也會帶來大量冗余的網絡通信量而影響仿真的執行時間和效率[6,7].因此在有限的計算資源條件下,實施較大規模的系統仿真實驗時,平衡運算節點的負載并減少節點間冗余的消息通信成為提高此類系統仿真運算效率和性能的關鍵.在傳統分布式計算的負載均衡調度問題中,主要是針對計算任務如何在運算節點間進行合理有效地調度和分配[8,9],而基于Agent的分布式仿真中,Agent作為運算的基本單元和載體,負載的平衡過程主要依賴于Agent在各個仿真節點之間的調度和分配.此外,在基于Agent的系統仿真中,參與仿真的Agent都是基于某個特定功能和結構進行劃分,并不是同質的計算單元,在仿真過程中不能將一個Agent的計算任務簡單分配給另一個Agent.同時,復雜社會系統的仿真過程往往是基于離散事件驅動,仿真Agent之間有復雜的邏輯關聯,Agent的行為會受到其他某些Agent的影響,在不破壞各個事件邏輯執行序列的情況下進行Agent的動態調度也是一個復雜的過程.在已有的相關研究中.如將Agent視為獨立且相互關聯的計算單元,通過對Agent計算任務的進行合理調配實現任務的高效執行[10,11].此外,基于某些設定的計分規則來對Agent的移動和調度進行判斷的方法[12]被設計出來以解決局部計算資源的過載問題,文獻[6,7,13,14]針對MAS中Agent的消息通信特性,提出了在相關應用中減小和優化MAS消息通信的一些方法.經濟市場領域中資源分配的博弈機制也被用于解決和實現MAS負載動態均衡問題[15].
與傳統的并行與分布式計算或仿真過程相比,基于多Agent系統的社會系統仿真具有自身的一些特性.如上所述,目前提出的一些方法中,或是不完全適合基于Agent的社會系統仿真中的負載均衡與調度,如基于任務分配和調度的方式;或是在Agent的分配和遷移上沒有充分考慮到Agent之間通信交互的關聯性和動態性,此外,普遍采用固定的負載監測閾值來作為負載調度的依據,對仿真過程中復雜多變負載狀態缺乏靈敏性而影響實施調度的效果,因此已有的一些方法不能很好地解決此類并行分布式仿真應用的負載均衡和調度問題.本文針對此類仿真的運算特性,綜合考慮了Agent之間的通信結構和各仿真節點負載的動態變化,提出了實施動態負載調度的框架及相關的Agent優化調度算法來提高分布式仿真運算的效率和性能.仿真實驗的結果表明,所提出的算法在總體負載均衡性和仿真運行的時間上均有較好的表現.
2.1 Agent調度優化問題
在基于分布式Agent的仿真運算中,大量Agent散布在不同分布式主機節點上,Agent以消息交互的方式進行通信和協作,Agent之間的消息通信因Agent所處節點位置的不同,包括節點內部的消息通信和跨節點的消息通信,通過Agent在節點之間的遷移能夠實現這兩種消息通信的轉換.由于跨節點的消息通信在處理時間的消耗上要遠大于內部的消息通信處理,因此一個最優的Agent調度分配既要保證各個仿真節點不因為過載造成仿真失效,又要最大限度地減少Agent系統中跨節點的全局網絡消息通信量,即系統通信負載.式(1)定義和描述了一個最優的Agent調度分配應滿足的條件,其中σ表示所有節點運算負載的均方差,Φ表示MAS中跨節點的Agent通信總量,α是權重系數,Wk表示任意某個節點的運算負載量,表示所有節點的平均負載量,Th是設定的節點負載上限閾值,Cij是任意兩個不同節點Hi,Hj之間的通信量,m表示分布式仿真節點的數量.

求解滿足上述條件的Agent分布是一個典型的NP問題,同時由于仿真運行中節點負載和Agent交互是動態可變的,特別在Agent數量相對較多時,在解空間中求解一個全局最優調度方案需要消耗大量的計算時間,因此無法有效地滿足系統仿真過程中動態實時調度的要求.為了在動態調度過程中能實時地做出合理的Agent調度和分配,本文通過周期性監測及調度優化的方法,利用各周期時間點相應的節點負載狀態與Agent之間的通信結構來實時地給出一個局部優化的Agent調度和分配方案,實現動態的Agent通信優化和節點負載均衡,以此提高系統運算效率并加快仿真執行時間.
2.2 基于分布式MAS的社會系統仿真特性
與其他分布式計算系統類似,基于MAS的社會系統分布式仿真也是一個分布式計算過程.但由于社會系統的運作特性,其仿真運算有如下特點:1)由于社會系統自身結構和功能的復雜性,仿真運算過程中的負載和Agent之間的通信結構模式較一般運算有更高的隨機性和動態性;2)社會系統仿真模型中,參與仿真運行的Agent往往是具有特定功能和角色的實體,運算任務在Agent之間不具備一般的傳遞性;3)在基于離散事件驅動的社會系統的仿真過程中,Agent的調度和遷移需要協調和維護整個仿真過程的時間同步和各個并發事件的邏輯順序.
針對上述運算特性,在本文設計的Agent動態優化調度算法中,進行了以下前提條件的假設:1)仿真Agent在計算資源使用權限上是一致的且其運算不依賴于某個特定的仿真節點;2)Agent之間跨節點的消息交互時間遠大于在節點內部的通信;3)Agent在不同節點之間移動的代價是相同的.
3.1 調度框架
本文設計了一個層次化的分布式Agent調度框架來實現對仿真Agent的動態調度和分配,圖1給出了調度框架的基本結構,其中全局負載調度Agent(GLSA)是進行全局調度和控制的Agent,區域負載調度Agent(DLSA)是分布在各個仿真節點上負責對應節點區域調度操作的Agent.GLSA與各DLSA共同構成了層次化的調度控制結構,分散在各節點的DLSA執行與所在節點相關的Agent調度與分配操作,GLSA則在更高的層面對全局調度進行協調,該結構模式有效地分解了實施調度控制操作的運算任務,充分發揮了分布式計算的優點.在系統運行過程中,GLSA以及分散的DLSA均常駐于對應的仿真節點上,其他參與仿真的Agent則根據設計的調度分配算法在各仿真節點之間進行動態地調度.

圖1 Agent層次調度框架Fig.1The level scheduling framework for agent
在需要進行Agent調度操作時,提出的算法通過選擇一個最佳Agent組的方式來實施Agent在相應節點的調度遷移,算法定義的Agent組是包含若干Agent的一個集合,組中Agent的選取充分考慮了當前Agent之間的通信關聯和聚集性.相比于提出的對Agent進行逐個單獨選取并遷移的調度方式,基于選取最佳Agent組的調度方式不僅能快速有效地降低過載節點的負載,還能避免逐個調度方法中由于未充分考慮Agent之間的通信結構和關聯性而增加額外的跨節點通信量的情況,從而利用Agent的優化調度最大限度地減少MAS中的全局網絡通信量.框架中動態調度的實現主要包括兩個過程,一個是在仿真過程中對節點負載進行周期性監測與控制;另一個是發生節點運算過載后進行Agent的優化分配和調度,該過程包括對過載節點中最佳遷移Agent組的選取及Agent組向目標節點的遷移. 3.2負載動態監測和調度控制
負載動態監測過程通過設定的某個周期時間對節點的負載狀態進行監控,當某個周期監測點發生節點負載超過特定閾值時,將執行相應的Agent優化調度操作,此時仿真的邏輯時間推進將暫停,直至整個調度過程完成;反之仿真過程將不會停止.為了能更好的實現各個節點負載的均衡調度以提高節點的計算效率,本文運用了可變閾值的監測方法,并利用式(2)給出了可變閾值的定義.其中Th(t)表示在監測周期時間點t的負載閾值,(t)表示所有節點在t時間點的平均負載值,λ是時序相關的負載平均值的比重系數,γ是負載閾值的調節系數,主要是控制可承受的負載擾動范圍.

下面的算法給出了GLSA和各DLSA共同實施負載監測和控制操作的描述.
步驟1在監測時間周期時間點t,GLSA接收來自各個DLSA發送來的節點負載值Wi(t);
步驟3將各個仿真節點按當前負載量的從大到小排列得到負載狀態隊列Q,判斷Q中是否有節點負載值大于當前的Th(t),如果成立轉入步驟4,否則轉入步驟7;
步驟4掛起當前的仿真推進進程,并向超過當前負載閾值的仿真節點的DLSA發送負載調度信息和當前負載狀態隊列Q;
步驟5結合當前負載狀態隊列Q,過載節點的DLSA選擇相應的遷移Agent組和遷移目標節點,并將組中的Agent遷移進行遷移,實現負載的均衡調度;
步驟6繼續當前仿真運算進程;
步驟7在下一個監測周期返回步驟1.
3.3 Agent優化分配與調度
如上所述,提出的算法在實施Agent優化調度時,采用了基于Agent組的分配和調度方式.Agent組的選擇則由Agent之間的通信關聯度來確定.Agent之間的消息交互是MAS運行的基礎和引起系統通信量變化的因素,因此本文中通過Agent之間的消息交互數量來度量Agent之間的關聯程度和Agent內部及外部的通信量大小.在式(3)中利用Agent的消息量定義并量化了在兩個節點之間遷移某個Agent組引起的全局通信量變化指標,其中mij表示任意兩個Agent,ai,aj之間的消息通信量,G表示某個包含若干Agent的備選Agent組,Ai和Aj分別表示對應節點當前包含的Agent集合.

由式(3)的定義可知,為盡量減少跨節點的Agent通信量,在選擇要遷移的Agent組時,其Δ(G)數值越大,則表明該組越適合作為實施調度遷移的Agent組.因此式(3)可以作為選定最佳遷移Agent組的判定指標.在下面的算法中給出了當需要進行負載調度操作時,在對應過載節點中DLSA進行目標遷移節點和最佳遷移Agent組選擇的算法步驟:
步驟1利用過載節點(Hi)當前的負載量(Wi),通過公式OutNum=「(Wi-Th)Ni/Wi」來量化需遷移的Agent數量;
步驟2在當前節點負載狀態隊列Q中,選取隊尾負載最小且未被選擇過的節點(Hj)作為調度遷移的目標節點,并結合Hj當前的負載量Wj用公式InNum=「(Th-Wj)Nj/Wj」計算Hj可容納的Agent數量;
步驟3從當前過載節點Hi中選取某個未被遍歷過的Agent(ai),并將ai放入備選遷移Agent組G′中;
步驟4將與ai關聯的所有Agent放入一個臨時Agent集合T中;
步驟6將ak從S中取出,并加入G′中,同時將與ak存在通信關聯的且不在G′中的Agent放入臨時集合T中;
步驟7判斷G′中的Agent數量是否小于min(InNum,OutNum),若是則轉入步驟5,否則將本次得到的備選組G′放入一個備選組的集合S中;
步驟8如果Hi中的Agent遍歷未完成,則轉入步驟3;
步驟9在備選組集合S中查找具有最大Δ(G)值的備選組,并將該組選定為遷移到Hj的Agent組G,并得到本次優化調度的Agent組與目標節點的組合〈G,Hj〉;
步驟10若遷移組G中累計的Agent的數量小于OutNum,則返回步驟2.
算法在Agent組中成員Agent的選取上利用了Agent之間的通信關聯性以及動態交互結構,通過當前的負載狀態隊列信息,并結合定義的InNum和OutNum來量化平衡各節點負載時所需調度的Agent數量,將隊首過載節點中的Agent以優化分組的形式向負載相對較輕的隊尾節點進行調度遷移.
3.4 算法性能分析
在上述算法實現中,對目標遷移節點的選擇主要根據負載狀態隊列來實現,求解并實現隊列的排序計算時間主要取決于主機的數量,其時間復雜度為O(m2).在最佳Agent組的生成和選擇上,設ρ=n/m表示節點的Agent平均密度,其中n,m分別是Agent總數和節點數.可知過載節點中選取Agent組的大小為(1-Th/Wi)ρ,確定最佳Agent組需要對該節點的所有Agent(數量為ρ)進行遍歷,所以組選擇過程的時間復雜度為O(ρ2).
4.1 實驗平臺
為了驗證所提出算法在基于MAS的社會系統分布式仿真應用中的有效性,本文利用面向Agent的編程工具組件JADE開發了一個實驗平臺,該平臺用于實施基于多Agent的供應鏈場景模型的運作過程仿真,同時實驗平臺利用設計的GLSA及DLSA來實現層次化的動態調度算法,其中實現算法所涉及的Agent基本功能屬性如消息交互以及遷移等都繼承JADE組件提供的底層功能接口.在平臺中有五種類型的仿真Agent來構建供應鏈仿真模型,其中包括生產制造Agent,生產計劃Agent,庫存Agent,運輸Agent以及運輸計劃Agent.在實驗分析中,用于實施仿真實驗的不同規模和結構的供應鏈場景MAS模型都由繼承這五種Agent類型的若干仿真Agent構成.
在供應鏈場景的MAS模型中包括了由仿真Agent組成的若干供應商、生產商以及分銷商,模型的仿真過程是基于離散事件驅動,模擬供應鏈場景模型完成一定數量的產品訂單的過程.在仿真時各分銷商給出一定數量的訂貨量需求,模型在訂單驅動下開始運作,各生產商利用供應商提供的原材料根據自身的生產線進行產品生產,原材料及產品在供應商、生產商及分銷商之間運輸,當各個分銷商的訂貨量滿足后仿真過程結束.仿真過程中參與仿真的Agent根據各自的角色功能自適應地交互和協作,各仿真Agent的事件活動運用保守時間管理機制來推進,直至完成設定的模型場景任務.在這個過程中,由于仿真邏輯時間的推進以及仿真Agent各自運行狀態,Agent之間的相互通信關系和運算負載都會動態地變化.
4.2 仿真實驗的環境和參數設定
在仿真實驗中利用十臺互聯的主機組成分布式仿真節點實施仿真分析實驗,其中一臺機器作為中心控制節點,其他主機作為仿真運行節點.在仿真監測中,節點的負載狀態利用公式Wi=βUc+(1-β)Um,0<β<1度量,其中Uc和Um分別是主機的CPU和內存的使用率,β為兩者之間的權重系數.根據仿真實驗環境和不同仿真模型,在表1中給出了實驗中實施調度算法所設定的各個參數值,其中監測間隔周期根據仿真規模在30~60s之間進行調整.

表1 實驗參數設定Table 1Parameters in experiments
4.3 實驗對比分析
實驗分析主要從負載均衡性能和仿真執行時間的消耗兩個方面,對所提出的優化調度算法進行檢驗.實驗中引入了靜態Agent均勻分布方法作為參照方法與所提出算法進行對比分析.參照方法在仿真執行前將所有仿真Agent隨機地平均分配到不同節點上,且仿真過程中不進行Agent的動態調度.由式(2)中對負載均方差的定義可知,負載值均方差σ的數值越小,說明在仿真過程中各節點的計算負載具有較好的均衡性和較小的波動,計算資源的綜合利用率就越高,同時節點的過載風險也相應降低,因此σ值可作為分布式節點綜合運算性能的一個有效指標.在圖2中將本文提出的算法(PA)和引入的參照方法(RA)在負載均衡性能方面進行了對比.
圖2(a)給出了在上述兩種情形下,同一仿真模型的仿真運行過程中各節點的負載值均方差σ隨監測周期時間點變化的σ值.從圖中可以看到,在整個仿真運行過程中使用提出的動態調度算法后得到的σ值總體上要低于作為對比的參照方法,且該數值的波動也相對較小.此外,在圖2(b)中給出了在兩種情形下,針對不同Agent規模(NAgent)的仿真模型,對應的整個仿真過程中得到所有σ值的平均值(σav)變化.圖中σav的變化趨勢表明,隨著仿真Agent規模的增加,在整個仿真過程中兩種情況下的σav都呈逐步下降趨勢,但在PA情形下的σav總體上低于RA情形下的數值,這說明實施了提出的優化調度算法有更好的全局負載均衡性.

圖2 負載均衡性能分析Fig.2 The analysis of load balancing performance
圖3對上述兩種情況下的仿真運行時間進行了對比分析,圖中給出了在不同Agent仿真規模NAgent下提出算法(PA)與參照方法(RA)的仿真執行時間的比值η(η=TPA:TRA)變化趨勢.在Agent規模較小時,兩者的執行時間比值接近且約大于1,表明此時兩者的仿真時間消耗比較接近,但PA情形下的時間消耗稍多,這是由于在動態調度算法中對Agent組選取和遷移操作會產生額外的時間消耗,執行優化調度后減少的時間消耗無法從總體上抵消算法產生的時間消耗.但隨著仿真Agent規模的增大及相互通信增多,所提出算法在仿真執行時間上的占比開始逐漸減少,圖中可以看到PA與RA的仿真執行時間比值η呈逐步下降趨勢.這表明在相對較大的Agent規模下,優化調度后減少的時間消耗逐漸彌補了調度過程本身產生的時間消耗,并使總的仿真時間得到有效降低.因此運用提出的動態優化調度算法在總的執行時間上也有明顯的改善.

圖3 仿真時間比值η(η=TPA:TRA)與Agent規模NAgent的關系Fig.3The relationship between simulation time-ratio η(η=TPA:TRA)and Agent scale NAgent
基于多Agent系統的計算機仿真方法在社會系統分析和研究中越來越普遍,提高此類仿真應用的分析能力和運算效率變得十分重要.本文針對基于多Agent系統的分布式仿真運算特性,提出了一個優化Agent分配的動態調度算法實現各仿真節點的負載均衡以及全局通信結構的優化.該算法綜合考慮了仿真過程中仿真節點的負載狀態和MAS通信結構的動態變化,設計了相應的可變負載閾值監測和基于Agent組選擇和遷移的優化調度方法.通過仿真實驗對比分析,提出的方法在仿真運行時間和負載均衡性能上均要優于作為實驗對比的靜態Agent隨機均勻分配的方法.文中提出的方法對于相關的基于分布式多Agent的仿真和運算系統也有一定的借鑒性.此外,當前算法設計中對一些相關前提條件進了簡化和限定,如Agent運算依附性、Agent遷移代價以及異質跨網段環境等,同時,Agent遷移機制設計與優化對于提升MAS運算的執行性能也有著一定影響,在今后的研究工作中,將會進一步考慮這些相關因素對算法進行改進和完善.
[1]盛昭瀚,張維.管理科學研究中的計算實驗方法[J].管理科學學報,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]劉曉平,唐益明,鄭利平.復雜系統與復雜系統仿真研究綜述[J].系統仿真學報,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的仿真系統建模[J].系統工程學報,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系統研究綜述[J].復雜系統與復雜性科學,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,Fan 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系統,系統仿真與建模等,Email:dh_myemail@126.com;
2013-11-14;
2014-09-04.
國家自然科學基金資助項目(71071114);教育部社科支撐資助項目(11YJC630216);上海市重點學科建設資助項目(B310).
林杰(1967-),男,四川渠縣人,教授,博士生導師,研究方向:信息管理與信息系統,供應鏈管理,決策支持系統等,Email:linjie@tongji.edu.cn.