（西北工業(yè)大學 計算機學院， 西安 710072）

摘 要：為了保證嵌入式實時計算系統(tǒng)的可靠性，提出了一種基于多智能體的嵌入式自主重構技術。首先描述了可重構MAS的組織結構，在此基礎上，通過對故障節(jié)點上的任務進行聚類劃分，采用基于任務聚類的合同網(wǎng)協(xié)商機制實現(xiàn)任務的再分配，提高系統(tǒng)的并行處理能力；同時，系統(tǒng)為上層用戶提供透明的通信機制，屏蔽節(jié)點重構對于任務通信的影響，保證對協(xié)作式多任務可重構支持。

關鍵詞：自主重構；任務聚類；合同網(wǎng)協(xié)商；任務間通信

中圖分類號：TP301文獻標志碼：A

文章編號：1001-3695(2009)04-1416-03

Self-reconfiguration in MAS based on contract net protocol of tasks clustered

SHENG Rui-qing，ZHOU Xing-she，ZHANG Kai-long，LIANG Ke

(College of Computer Science Engineering， Northwestern Polytechnical University， Xi’an 710072， China)

Abstract:In order to guarantee the reliability of the embedded real-time computation system， this paper presented an embedded self-reconfiguration technology based on multi-agent system. Firstly， it described the organizational structure of such reconfigurable MAS.Based on this， through the clustering partition of the tasks in fault node， this paper introduced a contract net consultation protocol based on the tasks clustered to achieve a re-distribution of tasks in order to improve system parallel processing ability. At the same time， the system provided the transparent correspondence mechanism for the upper formation user， shielding node reconfiguration for the communication tasks to ensure the collaborative support for reconfigurable multi-task.

Key words:self-reconfiguration; task clustered; contract net consultation; tasks communication

0 引言

在航空航天、軍事國防等安全關鍵領域，高可靠嵌入式實時計算系統(tǒng)日益得到廣泛應用。隨著該類安全關鍵系統(tǒng)（security critical system，SCS）智能化程度的不斷增強，其計算系統(tǒng)越來越多地采用復雜的嵌入分布實時計算系統(tǒng)架構，以得到更高的計算效能；但這也使得系統(tǒng)自身的可靠性保障受到更多的挑戰(zhàn)。近年來，系統(tǒng)自重構技術已經(jīng)成為提高該類復雜系統(tǒng)自主應用能力以及可靠性的一個重要途徑。

目前，可重構性在不同領域具有不同的含義和技術。硬件可重構技術在硬件邏輯單元中引入動態(tài)可配置機制，允許在不改動硬件設計的同時對硬件內部資源進行定制，實現(xiàn)快速的功能重構[1]；網(wǎng)絡重構是指在故障發(fā)生時，網(wǎng)絡系統(tǒng)能夠自動旁路掉失效或失去自愈能力的節(jié)點，恢復網(wǎng)路系統(tǒng)的通信等能力[2]；在移動機器人等領域，系統(tǒng)可重構則主要體現(xiàn)在環(huán)境或資源發(fā)生變化時，通過系統(tǒng)局部或整體的重構自主實現(xiàn)應用功能的重組[3]。

本文在對已有技術進行研究的基礎上，進一步結合多智能體（multi-agent system，MAS）技術與合同網(wǎng)機制，提出了基于任務聚類合同網(wǎng)的系統(tǒng)自主重構技術。重點研究了基于任務聚類算法的合同網(wǎng)協(xié)商機制及故障任務再分配方法，以提高并行處理能力，進而研究并設計了一種透明的通信機制，保證對協(xié)作式多任務可重構支持。

1 可重構MAS的組織結構

可重構MAS是在agent實體自治性、適應性、協(xié)作性等特點的基礎上進一步引入自重構機制，以根據(jù)外部環(huán)境及自身狀態(tài)的變化實現(xiàn)對系統(tǒng)結構、功能等的動態(tài)調整與組織，提高MAS的適應能力。該類系統(tǒng)中，每個處理節(jié)點至少包含兩個業(yè)務代理，即cooperator agent(CA)和inspect agent(IA)，如圖1(a)所示。IA主要是以主動探測模式對節(jié)點內任務進行故障監(jiān)測，依據(jù)任務應答來判斷是否出現(xiàn)異常；同時，IA通過響應中央控制節(jié)點（center control node，CCN）的狀態(tài)探測命令，向CCN提交節(jié)點當前狀態(tài)信息。CA的主要功能是協(xié)商和協(xié)作，并且通過動態(tài)查詢當前節(jié)點的位置信息實現(xiàn)通信透明的故障任務再次分配與遷移。

在初始時刻，可自重構的MAS選擇編號最小的節(jié)點作為CCN節(jié)點。該節(jié)點采用集中式任務分配方式將任務分配到各節(jié)點，同時廣播分配結果，使得每個節(jié)點上都擁有其他節(jié)點所承擔任務的記錄；同時，CCN節(jié)點還負責定期向其他節(jié)點發(fā)送狀態(tài)探測命令來判斷當前系統(tǒng)中各節(jié)點的狀態(tài)。節(jié)點的響應情況有兩類，即超時無應答和接收節(jié)點狀態(tài)信息。CCN在規(guī)定時間內未收到應答，此時節(jié)點可能失效，CCN可再次確認；若確認失效，則由CCN對該失效節(jié)點上的任務進行拍賣，如圖1(b)所示。節(jié)點Ni上的任務被劃分到Nk和Nj兩個節(jié)點，此時相當于利用這兩個節(jié)點虛構出節(jié)點Ni。對于后者， CNN接收到包含各節(jié)點當前狀態(tài)的信息包，依此判斷節(jié)點內部各任務的運行狀態(tài)，并以特定策略對故障的任務進行遷移和恢復。對于CCN節(jié)點失效問題，可以約定：當所有節(jié)點在規(guī)定時間內沒有收到CCN的探測命令以及反向探測失效時，可認定CCN節(jié)點出現(xiàn)故障，此時MAS中的其他節(jié)點嘗試發(fā)起CCN自動選舉功能。

2 基于聚類合同的協(xié)商

本文采用合同網(wǎng)協(xié)議(contract net protocol)來實現(xiàn)自主重構時的協(xié)同任務分配。合同網(wǎng)的基本思想是agent之間通過“招標—投標—中標”這一市場拍賣機制實現(xiàn)任務的委派和遷移，使整個MAS以較低的代價和較高的質量完成任務。

2.1 任務聚類算法

由于MAS中各節(jié)點上的任務彼此間具有一定的相關性，且在不同節(jié)點上運行時通信開銷也不相同，在對該類系統(tǒng)中某一故障節(jié)點進行重構時，需要對其上的任務進行聚類劃分，以減小并行處理時間。設某一時刻故障任務需要被遷移，屬于該聚類中的其他任務連同故障任務作為整體被拍賣；而當節(jié)點出現(xiàn)異常時，拍賣也是以節(jié)點中的若干個任務簇形式進行。

圖2所示的有向無環(huán)圖(directed acyclic graph，DAG)中，每個頂點表示一個任務，頂點的值表示任務的執(zhí)行時間；每條邊定義了任務間的優(yōu)先關系，其權值表示兩個任務在分布環(huán)境下的通信開銷。相比而言，處理機內部的任務通信開銷可歸約為0?？紤]到任務簇粒度的大小及其他任務全局執(zhí)行時間的影響，本文采用文獻[4]中所研究的DSC（dominant sequence clustering）啟發(fā)式聚類算法來進行任務簇的劃分，盡可能減少全局并行時間。

兩共邊任務可以形成一個聚類的條件是：先執(zhí)行任務后執(zhí)行任務的惟一前驅。兩個任務劃分到一個聚類后，通信開銷近似為0。若干頂點聚類后，通過更改這些頂點相鄰邊的權重為0而形成的圖稱為聚類圖(clustered DAG)。定義聚類圖中的關鍵路徑為圖中權重最大的路徑，該路徑上的任務執(zhí)行時間最長。因此，DSC算法本質的思想就是要進行一系列聚類操作，并在每一步操作執(zhí)行后都能使當前關鍵路徑長度減小。

依據(jù)DCS算法對圖2進行聚類劃分的結果如圖3所示。

聚類完成后，該節(jié)點上任務劃分為兩個任務簇{T1，T5}和{T2，T3，T4，T6}。在此基礎上可進一步使用分布協(xié)商機制來實現(xiàn)任務的動態(tài)分配。本文的分布協(xié)商過程中采用合同網(wǎng)技術。

2.2 基于合同網(wǎng)的動態(tài)任務分配機制

買賣合同是合同網(wǎng)協(xié)議中最基本的合同類型，拍賣過程中各節(jié)點通過買—賣關系來實現(xiàn)任務的重新分配[5]。合同網(wǎng)的協(xié)商過程通過招標、投標、標值評估、合同簽訂四個步驟，將任務簇分配給一個性能較優(yōu)的節(jié)點。

1)任務簇招標

招標是指節(jié)點將要分配出去的任務信息以特定協(xié)商機制向整個系統(tǒng)進行發(fā)布。設某一時刻，節(jié)點Ni上的IAi監(jiān)測并確認任務Tik出現(xiàn)異常，則將該任務當前狀態(tài)信息通知CAi。CAi分析并通過上述聚類算法計算出任務Tik所對應的聚類任務簇CSi(Tik)后，以廣播方式進行招標。招標通知除包含通信規(guī)約要求的內容外，還包括該任務簇中各任務執(zhí)行時間、相互關系以及投標截止期等。

2)節(jié)點效能評估與投標

在接收到招標通知后，各節(jié)點首先評估自身資源是否滿足任務簇CSi(Tik)的需求。設系統(tǒng)中的n個節(jié)點上共有m個任務需要執(zhí)行，且m>n。定義矩陣Fm×n。其中：

aij=1 Ti可在Nj上運行

0 否則

為表明任務對系統(tǒng)具有不同的影響程度，定義任務權重矩陣Km×n。其中：

kij=ki i=j

0否則

每個處理節(jié)點內可能采取了不同的容錯技術，包括單節(jié)點的硬件、軟件容錯，其對于部署在自身上的任務執(zhí)行時具有不同的可靠度，因此定義可靠度矩陣Rn×n。其中：

rij=ri i=j

0否則

依據(jù)上述三個矩陣可計算出每個任務分配至不同處理機節(jié)點后的效能矩陣Pm×n：

Pm×n=Km×m×Fm×n×Rn×n=

k10…0

0k2…0



00…km×

a11a12…a1n

a21a22…a2n



am1am2…amm×

r10…0

0r2…0



00…rn=

p11p12…pm1

p21p22…pm2



pm1pm2…pmm

對于節(jié)點Nj，依據(jù)矩陣P找出對應于自身任務集Sj(T)和招標任務簇CSi(Tik)中執(zhí)行各任務的效能值，則其效能函數(shù)Uj可表示為

Uj=Ti∈{Sj∪CSi}pij

為平衡各節(jié)點上的任務負載和當前節(jié)點的健康度，在效能計算中引入負載平衡約束和節(jié)點狀態(tài)約束，則其效能函數(shù)演變?yōu)楠?/p>

U′j=Uj+α×Lj×Uj+β×Hj×Uj

其中：α為任務負載影響因子；β為節(jié)點健康度影響因子；Lj為任務負載參數(shù)，為節(jié)點當前任務數(shù)量與節(jié)點所能執(zhí)行的任務數(shù)量的比值；Hj為節(jié)點健康度參數(shù)，為節(jié)點當前出現(xiàn)故障的任務數(shù)量與節(jié)點中全體任務數(shù)量的比值。

α、β值可依據(jù)系統(tǒng)對于負載或健康度關注程度進行動態(tài)調整。各節(jié)點返回的信息類型包括以下三類：a）接收整個任務簇，并告知效能值；b)可接受的部分任務集合以及效能值；c)該簇任務均不能在本節(jié)點上執(zhí)行。

3)評標與任務分配

投標截止期到來，招標節(jié)點Ni上的CAi接收各節(jié)點的反饋信息，分析消息內容，以決定將拍賣的任務簇轉交給其中哪些節(jié)點執(zhí)行。當有多個節(jié)點均可接收該簇任務時，在這些投標者中選擇競標價格最低的節(jié)點并轉交任務執(zhí)行權；當沒有單個節(jié)點能滿足該簇任務執(zhí)行需求，但多個節(jié)點可通過分工來承擔該任務簇時，CAi需要在這些節(jié)點中進行篩選，選擇出包含CSi(Tik)中所有任務的處理節(jié)點集合。該問題可由多種選擇背包問題算法來求解。

如果所有節(jié)點能執(zhí)行任務的集合為該任務簇集合的真子集時，表示該簇任務已無法進行有效遷移，此時考慮到任務間的強邏輯關系，可給出系統(tǒng)告警提示，認為該簇任務失效。

3 基于agent的任務間消息通信

節(jié)點上的任務由于故障被遷移后，與其他任務間的通信關系應保持不變，而彼此間的通信方式則可能發(fā)生變化。如圖4所示，位于節(jié)點N1上的任務T1被重新分配至節(jié)點N2后，T1與T3之間由外部網(wǎng)絡通信變化成節(jié)點內消息通信。為了保證應用的靈活性，需要設計一種透明的通信機制，以保證對協(xié)作式多任務可重構的支持。

3.1 通信模型形式化描述

如前所述，初始時刻，CNN節(jié)點采用集中任務分配方式對任務進行分配后，在各節(jié)點上形成了初始狀態(tài)下包含系統(tǒng)中全部任務的靜態(tài)配置表(static configuration table，SCT)，表明任務在系統(tǒng)啟動后最初的位置信息。

在系統(tǒng)運行過程中，各節(jié)點上的任務可能由于故障被遷移，在每一節(jié)點上，針對SCT中分配到其上的任務設定一動態(tài)遷移表(dynamic migration table，DMT)，用于表示當前時刻這些任務所在處理機節(jié)點信息。

假設節(jié)點Ni中有若干任務，則第k個任務在DMT中表項信息ψk可定義為

ψk={LTIDk，MNIDk，MTIDk}

其中：LTIDk為任務k在Ni節(jié)點上的ID標志號；MNIDk為任務k當前所在處理機節(jié)點號；MTIDk為任務k當前所在處理機節(jié)點上的ID標志號。

初始化時，DMT中所有任務的LTIDk 、MTIDk屬性相同，且MNIDk屬性均置為Ni。在任務發(fā)生遷移時，MTIDk、MNIDk屬性也隨之動態(tài)變化，且僅記錄最近一次遷移后任務所在的位置信息，使得任務多次遷移不會對遷移地查詢的復雜度產(chǎn)生影響，避免了循環(huán)查詢時可能導致的多米諾效應。

每個節(jié)點均維護各自的DMT，且CCN節(jié)點擁有其他各節(jié)點的DMT并隨各節(jié)點DMT變化進行動態(tài)更新，保證不會由于單點故障對系統(tǒng)性能造成影響。

3.2 可配置的任務通信機制

任務在進行通信時，僅需提供對方任務的ID標志信息，并連同待發(fā)送的消息內容遞交給本節(jié)點上的CA。具體的通信細節(jié)由各節(jié)點上的CA通過協(xié)商完成，上層用戶無須了解通信對方的具體位置。

如圖5所示，任務T1從節(jié)點N1被遷移至節(jié)點N2上，某一時刻，任務T2需要向T1發(fā)送消息。首先，T2將T1標志以及消息內容發(fā)送給本節(jié)點的CA1，此時CA1通過在本地的SCT中查詢任務T1被分配的處理機節(jié)點后，通知對方CA查詢自身DMT表獲取T1當前所在位置，進而決定最終目的地并發(fā)送消息。

若發(fā)送任務CA1監(jiān)測到接收方節(jié)點出現(xiàn)故障，則將該消息轉發(fā)給CNN節(jié)點，由CNN節(jié)點上的CA進行中轉。而當CCN出現(xiàn)故障時，其他節(jié)點需要將自身的TML信息再重新以廣播的形式告知CNN。因此，任務只需提供通信對方任務標志信息，由各節(jié)點上的CA結合SCT、DMT來將消息最終發(fā)送給接收方。這樣，在用戶看來，節(jié)點中的任務均未發(fā)生變化，可以使用統(tǒng)一的通信接口，使得任務位置變化對于通信透明。

4 結束語

本文主要研究了基于任務聚類合同網(wǎng)的自主重構技術，以聚類任務簇的形式對任務進行協(xié)商拍賣，有效地減少了節(jié)點的全局并行時間，并為上層用戶提供統(tǒng)一的通信接口，保證任務間通信對于節(jié)點重構的透明。在本文研究基礎上，將結合具體的應用場景構造效能函數(shù)，并考慮節(jié)點間的負載均衡等問題，使系統(tǒng)中多agent協(xié)商更具合理性。

參考文獻：

[1]李濤，楊愚魯，馬平，等.基于遺傳算法的可重構系統(tǒng)軟硬件劃分[J].計算機工程與應用，2007，43(26):56-58.

[2]竇麗華，肖楊.基于信息流的網(wǎng)絡動態(tài)重構方法[J]. 計算機工程，2007，33(12):131-133.

[3]陳勇，戴先中.基于移動機器人的可重構多智能體系統(tǒng)平臺的構建[J].東南大學學報：自然科學版，2003，33（Z1）:194-199.

[4]YANG Tao，GERASOULIS A.A fast static scheduling algorithm for DAGs on an unbounded number of processors[C]//Proc of IEEE Conference on Supercomputing.New York:ACM Press，1991:633-642.

[5]龍濤，朱華勇，沈林成.多UCAV協(xié)同中基于協(xié)商的分布式任務分配研究[J].宇航學報，2006，27(3):457-462.

［6］PONGPUNWATTANA A，RYSDYK R.Real-time planning for multiple autonomous vehicles in dynamic uncertain environments[J].Journal of Aerospace Computing， Information， and Communication，2004，1(12):580-604.

［7］陶麗，張自力.基于面向自治計算的agent系統(tǒng)動態(tài)重構模型[J].計算機科學，2007，34(5):147-151.