基于擴展合同網(wǎng)的協(xié)同故障診斷任務分配研究

陳 波 朱坤博 杜秀麗 王運明

1(大連大學信息工程學院 遼寧 大連 116622)2( 遼寧省通信網(wǎng)絡與信息處理重點實驗室 遼寧 大連 116622)3(南京理工大學 江蘇 南京 210094)

基于擴展合同網(wǎng)的協(xié)同故障診斷任務分配研究

陳 波1,2朱坤博1,2杜秀麗1,2王運明3

1(大連大學信息工程學院 遼寧 大連 116622)2( 遼寧省通信網(wǎng)絡與信息處理重點實驗室 遼寧 大連 116622)3(南京理工大學 江蘇 南京 210094)

任務分配作為協(xié)同故障診斷技術的重要環(huán)節(jié)，任務分配機制的優(yōu)劣直接影響到診斷效率和準確性。針對現(xiàn)有合同網(wǎng)協(xié)議存在分配效率低、任務量大時易造成單節(jié)點過于忙碌等問題，提出一種基于擴展合同網(wǎng)的協(xié)同故障診斷任務分配機制。首先利用Hash算法建立子故障任務與對應分配路徑的分配知識庫，為任務分配提供動態(tài)分配經(jīng)驗；其次將Dijkstra算法與合同網(wǎng)協(xié)議相結(jié)合，通過權衡故障診斷能力與路徑權值來選擇“性價比”高的任務分配節(jié)點。算法仿真表明，擴展合同網(wǎng)任務分配算法減少了通信量、提高了分配效率。

任務分配 協(xié)同故障診斷 擴展合同網(wǎng) Dijkstra算法

0 引 言

協(xié)同故障診斷技術實施的主要步驟為數(shù)據(jù)采集、任務分解、任務分配、決策融合。其中任務分配策略需要考慮任務之間的耦合性、分配過程的動態(tài)性，是協(xié)同故障診斷的一個難點。現(xiàn)有的任務分配算法主要包括蟻群算法[1]、粒子群優(yōu)化算法[2-4]、合同網(wǎng)算法等，其中由于合同網(wǎng)算法在任務分配過程中動態(tài)性和可擴展性表現(xiàn)較佳，從而得到了廣泛的應用。但合同網(wǎng)有其天生的缺陷如在反復的協(xié)商過程中會增大通信量，產(chǎn)生大量的冗余信息，易造成網(wǎng)絡擁塞,承包商不能根據(jù)自己的規(guī)劃和能力來主動獲取任務等。針對合同網(wǎng)存在的缺陷國內(nèi)外專家學者也對其提出了改進，如文獻[5]提出根據(jù)診斷任務的相似范例推理和閾值規(guī)則的合同網(wǎng)改進算法，增強了合同網(wǎng)初始發(fā)布信息的目的性，減少了協(xié)商過程；文獻[6]提出基于改進合同網(wǎng)協(xié)議的Agent動態(tài)分配算法，實現(xiàn)了對不確定環(huán)境中動態(tài)變化的任務分配方法；文獻[7]提出一種基于拍賣機制的改進合同網(wǎng)協(xié)商策略，通過Agent間的自主競爭來實現(xiàn)任務的動態(tài)分配，從而降低管理者獲取和更新其他Agent知識的難度。

但在現(xiàn)有的改進合同網(wǎng)協(xié)議中，沒有考慮到如何權衡分配過程中消耗的資源與節(jié)點的執(zhí)行能力，導致任務量大時資源消耗過大且使得執(zhí)行能力強的節(jié)點過于忙碌。本文采用Hash算法來實現(xiàn)對子故障任務分配知識庫的快速存取，提出將Dijkstra算法與合同網(wǎng)協(xié)議相結(jié)合解決如何選取合適的任務分配節(jié)點問題。

1 協(xié)同故障診斷模型與數(shù)學描述

1.1 協(xié)同故障診斷模型

對于不同的協(xié)同故障診斷模型，可以采用不同的任務分配策略。典型的故障診斷模型有集中式和完全分布式，集中式診斷模型由一個中心節(jié)點來控制及協(xié)調(diào)各個節(jié)點之間的任務分配，但隨著網(wǎng)絡規(guī)模、節(jié)點個數(shù)的增加，會導致通信量迅猛增加，以至于通信延遲、網(wǎng)絡擁塞情況嚴重。完全分布式診斷模型由地位和作用完全平等的節(jié)點組成，組網(wǎng)簡單、靈活，各個節(jié)點獨立地進行數(shù)據(jù)采集和診斷維護，但是完全分布式診斷模型中每個節(jié)點都要存儲整個系統(tǒng)中其他節(jié)點的信息，由于系統(tǒng)中節(jié)點往往是動態(tài)變化的，隨著節(jié)點個數(shù)增多，各個節(jié)點用于存儲和處理其他節(jié)點消耗的資源和負載都會增加，導致其資源利用率低、可擴展性差。本文結(jié)合傳統(tǒng)的集中式和完全分布式診斷模型構(gòu)建了一種分布式分群的協(xié)同故障診斷模型，如圖1所示。該模型資源利用率高、可擴展性好、可以有效減少網(wǎng)絡擁塞的情況。

圖1 故障診斷模型

此診斷模型以群為單位，每個群由一個群首節(jié)點和若干成員節(jié)點組成，群首節(jié)點負責管理群內(nèi)所有節(jié)點，并且負責存儲和處理其他群首節(jié)點的信息，減少了節(jié)點間的通信量，克服了集中式和完全分布式診斷模型的缺陷。該故障診斷模型將故障診斷分為群內(nèi)和群間協(xié)同故障診斷。群內(nèi)故障診斷主要由群首節(jié)點直接對群內(nèi)各個節(jié)點進行檢測，若發(fā)現(xiàn)群內(nèi)某節(jié)點發(fā)生故障，并不會將故障信息發(fā)布到整個診斷網(wǎng)絡中，而是首先在群內(nèi)組織協(xié)同診斷，以減少不必要的交互通信。但由于群內(nèi)節(jié)點能力有限，對于無法解決的復雜故障，就由群首節(jié)點聯(lián)合其他群首節(jié)點形成共同的診斷知識空間，進行協(xié)同診斷。

1.2 任務分配數(shù)學描述

2 基于擴展合同網(wǎng)的任務分配

2.1 基于Hash算法的任務分配知識庫

為了節(jié)約合同網(wǎng)任務分配時間，將子故障任務集經(jīng)過合同網(wǎng)協(xié)議分配得到的每個子故障任務與對應的分配路徑存入任務分配知識庫。每次分配任務時首先在分配知識庫中查找是否有對應的分配路徑，如果存在則可以按已有的分配路徑直接分配，否則利用合同網(wǎng)協(xié)議來分配任務。這樣可以減少協(xié)商過程、降低通信量，從而大大節(jié)約分配時間。

本文采用Hash算法實現(xiàn)任務分配知識庫的快速查找與存儲。Hash算法是一種用于實現(xiàn)快速查找、插入、刪除的技術，理想的Hash表只不過是一個包含有關鍵值的數(shù)組，它根據(jù)關鍵值直接訪問數(shù)據(jù)結(jié)構(gòu)。在實際的應用中它的查找和插入性能是極好的,其平均時間算法復雜度為o(1)。Hash算法的數(shù)學描述為：key=hash(x),其中x表示要插入表的實際信息，key為所得到的關鍵碼值。但不同的x可能會得到相同的key值，即hash(x1)=hash(x2),x1≠x2，我們稱這種現(xiàn)象稱為沖突。由上面描述可知，一個Hash算法效率的高低主要取決于Hash函數(shù)和解決沖突方法的選取。為了盡量減少沖突，本文選取以下Hash函數(shù)：

(1)

其中x為待插入的實際信息，size為實際信息的長度，tablesize為Hash表的大小，該散列函數(shù)涉及所有的實際信息的字符，假如x中包含的三個字符，則所得的關鍵字為key=(x[0]*20+x[1]×21+x[2]×22)%tablesize，它將實際信息的計算結(jié)果限定在一定的范圍。并且對于像″abcd、bacd、dcba″等，這種所用字符完全相同，但順序不同的信息，通過該Hash函數(shù)處理后會得到不同的關鍵碼值，可以很大程度上減少沖突。雖然該散列函數(shù)就表分布而言未必是最佳的，但其構(gòu)造簡單、執(zhí)行速度快，可以用該散列函數(shù)節(jié)省的時間來補償由此帶來的對均勻分布造成的輕微干擾，體現(xiàn)了一種“以空間換時間”的思想。

其算法流程如下所示：

1) 將復雜故障分解成故障子任務集；

2) 分別查找各個子故障任務在Hash表中是否已經(jīng)存在對應的分配方案；

3) 若有，則按照對應的分配方案進行任務分配；

4) 否則，利用合同網(wǎng)協(xié)議分配子故障任務，并且將子故障任務對應的分配方案插入Hash表；

5) 查詢子故障任務是否分配完畢，若是則整個任務分配結(jié)束，否則跳轉(zhuǎn)到2)繼續(xù)進行子故障任務分配。

2.2 合同網(wǎng)與Dijkstra結(jié)合的任務分配策略

協(xié)同故障診斷將復雜的故障分解成若干子故障任務，將不同的子故障任務分配給相應診斷節(jié)點，其中每一個子故障任務的分配都需要消耗一定的時間和資源。考慮下面這樣一個問題，假設有兩個診斷節(jié)點A和B，它們對子故障T的診斷能力為AT和BT，故障節(jié)點到它們的權重分別為WA和WB(可以指分配時間長短、距離大小等)。對于解決子故障T所需要的診斷能力為NT，若AT>BT>NT,即診斷節(jié)點A和B都有能力解決子故障T，并且節(jié)點A大于節(jié)點B的診斷能力。但是WA?WB，選取診斷節(jié)點A所消耗的診斷資源遠大于診斷節(jié)點B。若采用現(xiàn)有的合同網(wǎng)協(xié)議，由于診斷節(jié)點A大于診斷節(jié)點B的能力，則會選擇診斷節(jié)點A發(fā)布子故障任務。若子故障集包含的故障信息量很大，這樣會使任務分配效率大為下降。本文提出將Dijkstra算法與合同網(wǎng)協(xié)議相結(jié)合權衡節(jié)點診斷能力與路徑權值，選擇出合適的診斷節(jié)點發(fā)布子故障任務。

Dijkstra算法是解決帶權重單源最短路徑問題的經(jīng)典算法。其基本算法思路為：有n個頂點{vi,vk,…,vs,vj}，假設存在從節(jié)點i到節(jié)點j的最短路徑(vi,vk,…,vs,vj)，其中vj的前一個結(jié)點為vs，那么(vi,vk,…,vs)也必定是i到s的最短路徑。為了獲得節(jié)點間的最短路徑，Dijkstra算法按階段進行，在每個階段選擇一個頂點，求出它在所有未知頂點中具有的最小權值，然后依次向下一個節(jié)點擴散。比如起始節(jié)點vi，選擇與它直接鄰居的節(jié)點中的權值最小的節(jié)點vk,根據(jù)這種思路就可以得到從vi到vk鄰居頂點vx的最短路徑為：

disk[x]=min{disk[x],dist[k]+matrix[k][x]}

(2)

其中dist[k]表示頂點vi到vk的距離，matrix[k][x]表示頂點vk到頂點vx的直接相鄰距離。就這樣依次更新到源頂點的最小值，直到所有的頂點全部遍歷完。

與Dijkstra算法結(jié)合的合同網(wǎng)協(xié)議描述如下：

1) 首先根據(jù)Dijkstra算法計算出故障節(jié)點距離各診斷節(jié)點agent={a1,a2,…,am}的最小路徑權值。

2) 故障節(jié)點分配子故障任務集task={t1,t2,…,tn}，每個子故障任務首先在故障分配經(jīng)驗庫中查找是否有該子故障任務對應的分配方案。

3) 若有則直接按照已有的分配方案分配該子任務，完成后查看子任務集中是否還有子任務，若有跳轉(zhuǎn)到2)繼續(xù)執(zhí)行，否則任務分配結(jié)束。

5) 故障節(jié)點根據(jù)各個診斷節(jié)點返回的標書，提取出各個診斷節(jié)點的對子故障的解決能力,并結(jié)合1)中計算出的距離各個節(jié)點的路徑權值，根據(jù)下面的公式計算結(jié)果來選擇哪個診斷節(jié)點是最終的中標者。

(3)

6) 選擇node中最大值對應的診斷節(jié)點發(fā)布該子故障任務，并將該子故障任務與其對應的分配方案存入分配知識庫。

7) 查看task={t1,t2,…,tn}中是否還有未分配的子任務，若有跳轉(zhuǎn)到2)繼續(xù)執(zhí)行，否則整個任務分配結(jié)束。

3 仿真分析與比較

基于上述算法設計，擬建立如圖2的仿真平臺進行驗證。該仿真環(huán)境由7個節(jié)點組成，其中各個節(jié)點之間的數(shù)值為權重，可以用其表示消耗資源的多少等。

圖2 仿真網(wǎng)絡結(jié)構(gòu)

根據(jù)圖2的網(wǎng)絡結(jié)構(gòu)，假設a1為故障節(jié)點，用S表示已經(jīng)計算出最小權值的節(jié)點集合，U是未計算的節(jié)點集合。

1) 將節(jié)點a1加入集合S中，此時S={a1(0)},U={a2(∞),a3(3),a4(∞),a5(4),a6(∞),a7(∞)}。其中a3(3)表示診斷節(jié)點a3到故障節(jié)點a1的權值為3。

2) 操作1)之后，U中節(jié)點a3到故障節(jié)點a1的權值最小，則將a3加入到集合S中，同時更新U中各個節(jié)點的權值。如節(jié)點a6，在將a3加入到集合S前的權值為∞，但加入之后更新為a6到a1的權值為9=(a6,a3)+(a3,a1)。此時S={a1(0),a3(3)},U={a2(23),a4(∞),a5(4),a6(9),a7(∞)}。

3) 操作2)之后，U中節(jié)點a5到故障節(jié)點a1的權值最小，因此將a5加入到集合S中，同時更新U中各個節(jié)點的權值。仍然拿節(jié)點a6來說，將a5加入到集合S之前權值為9，但加入之后更新為a6到a1的權值為6=(a6,a5)+(a5,a1)，而此時S={a1(0),a3(3),a5(4)},U={a2(23),a4(∞),a6(6),a7(12)}，依次類推計算出a1到其他診斷節(jié)點的最小權值如表1所示。此算法的總運行時間主要依賴于利用遍歷節(jié)點來更新集合S和U，操作集合S和U也需遍歷節(jié)點，則其算法時間復雜度為o(n2)。

表1 a1到各個診斷節(jié)點的最小權值

為了更便于記錄故障節(jié)點發(fā)布子故障任務到各個診斷節(jié)點所消耗的時間資源，本文采取在各個診斷節(jié)點上加延時函數(shù)，其延時時間與權值相對應，如故障節(jié)點a1與診斷節(jié)點a2之間的權值為13，則就設定診斷節(jié)點a2上的延時值為1.3s。

假設由故障節(jié)點a1發(fā)布一個包含12個子故障的任務集，各個診斷節(jié)點對這12個子故障的解決能力評估如表2所示，只有當值大于60時才能解決故障，值越大表示解決程度越好，但相應消耗的資源可能越多。

表2 診斷節(jié)點能力評估值

續(xù)表2

將擴展合同網(wǎng)算法程序安裝到各個診斷節(jié)點計算機，并根據(jù)表1和表2提供的數(shù)據(jù)運行程序。故障節(jié)點a1反復對12個子故障任務分配20次，統(tǒng)計每個子故障任務分配完成的時間并求取平均值，根據(jù)求得的平均值得出仿真結(jié)果，并與傳統(tǒng)合同網(wǎng)協(xié)議的仿真結(jié)果進行比較。如圖3所示，可以看出擴展后的合同網(wǎng)任務分配完成時間明顯優(yōu)于傳統(tǒng)合同網(wǎng)，而且對于各個子故障的分配完成時間波動較小。反觀傳統(tǒng)合同網(wǎng)分配完成時間波動較大，這容易造成由于某個子故障分配完成時間較長而影響到整個子故障任務集的分配效率。

圖3 子故障任務分配完成時間對比

根據(jù)以上實驗，統(tǒng)計傳統(tǒng)合同網(wǎng)分配路徑與擴展合同網(wǎng)分配路徑如表3所示。結(jié)合圖2可以看出傳統(tǒng)合同網(wǎng)協(xié)議每次總是選擇診斷能力最強的診斷節(jié)點，并沒有考慮其他因素的影響。這不僅導致了分配效率的下降，而且容易造成某些能力較強的診斷節(jié)點過于忙碌。擴展合同網(wǎng)協(xié)議在收到符合條件的診斷節(jié)點的標書后，根據(jù)式(3)與對應的權值相結(jié)合選擇出合適的診斷節(jié)點分配任務，緩解了某些診斷能力較強節(jié)點的壓力、提高了分配效率。

表3 任務分配路徑

續(xù)表3

為了進一步驗證擴展合同網(wǎng)在大量信息情況下的性能，逐漸增加子故障任務個數(shù)及每個子故障任務的信息量，得到仿真結(jié)果如圖4所示，由圖可以看出傳統(tǒng)合同網(wǎng)任務分配完成時間長，且隨著子故障任務數(shù)目的增加，完成時間增加的速度非常快。對于擴展后的合同網(wǎng)不僅任務分配完成時間短，而且隨著子故障任務數(shù)目的增加，分配完成時間增加速度慢。

圖4 任務分配完成時間對比

4 結(jié) 語

本文針對協(xié)同故障診斷中的任務分配方法進行研究，在現(xiàn)有合同網(wǎng)協(xié)議的基礎上，采用Hash算法實現(xiàn)子故障任務分配知識庫，提出了將合同網(wǎng)協(xié)議與Dijkstra算法相結(jié)合選擇“性價比”高的分配節(jié)點。由仿真結(jié)果可以看出擴展合同網(wǎng)縮短了任務分配完成時間，提高了分配效率，有效地克服了傳統(tǒng)合同網(wǎng)分配效率低、易造成單節(jié)點過于忙碌的缺陷。

[1] 蘇菲,陳巖,沈林成.基于蟻群算法的無人機協(xié)同多任務分配[J].航空學報,2008,29(S1):184-191.

[2] Shima T,Rasmussen S J,Sparks A G,et al.Multiple task assignments for cooperating uninhabited aerial vehicles using genetic algorithms[J].Computers & Operations Research,2006,33(11):3252-3269.

[3] 國博,王社偉,陶軍.基于改進粒子群算法的多無人機任務分配研究[J].計算機仿真,2009,26(7):62-64,153.

[4] 李煒,張偉.基于粒子群算法的多無人機任務分配方法[J].控制與決策,2010,25(9):1359-1363,1368.

[5] 劉建輝.擴展合同網(wǎng)方法在遠程協(xié)同診斷中的應用[J].計算機測量與控制,2008,16(4):457-460.

[6] 劉科,郭小和,周繼強,等.基于multi-agent的多任務分配問題研究[J].計算機應用研究,2014,31(7):1980-1984,1988.

[7] 劉俊,曹斌,譚丹丹.基于拍賣機制的改進合同網(wǎng)協(xié)商策略[J].計算機應用,2007,27(2):494-496.

[8] 裘杭萍,覃垚,胡汭,等.多Agent系統(tǒng)中基于改進合同網(wǎng)模型的任務分配研究[J].計算機科學,2012,39(6A):279-282.

[9] Deng Y.Task allocation and path planning for acoustic networks of AUVs[D].Boca Raton,FL,USA:School of Graduate,Florida Atlantic University,2010.

[10] 肖玉杰,李杰,劉方.基于合同網(wǎng)的分布式動態(tài)任務分配算法[J].艦船科學技術,2015,37(3):113-118.

[11] 樂陽,龔健雅.Dijkstra最短路徑算法的一種高效率實現(xiàn)[J].武漢大學學報(信息科學版),1999,24(3):209-212.

[12] Mark Allen Weiss.數(shù)據(jù)結(jié)構(gòu)與算法分析—C語言描述[M].馮舜璽,譯.2版.北京:機械工業(yè)出版社,2005.

[13] Wang Y,Liao X,Xiao D,et al.One-way hash function construction based on 2D coupled map lattices[J].Information Sciences,2008,178(5):1391-140.

RESEARCH ON TASK ALLOCATION OF COOPERATIVE FAULT DIAGNOSIS BASED ON EXTENDED CONTRACT NET

Chen Bo1,2Zhu Kunbo1,2Du Xiuli1,2Wang Yunming3

1(CollegeofInformationEngineering,DalianUniversity,Dalian116622,Liaoning,China)2(KeyLaboratoryofCommunicationsNetworkandInformationProcessing,Dalian116622,Liaoning,China)3(NanjingUniversityofScienceandTechnology,Nanjing210094,Jiangsu,China)

Task allocation is an important part of collaborative fault diagnosis technology, whether the task allocation mechanism is good or not directly affects the efficiency and accuracy of the diagnosis. For existing contract net protocol, the low allocation efficiency and the huge task load could easily lead to the problem such as over-busy single node. Thus, a task allocation mechanism of collaborative fault diagnosis is proposed based on extended contract net. Firstly, using Hash algorithm to establish allocated knowledge base which links sub fault tasks with the corresponding distribution path, providing expert distribution experiences for task allocation. Then, combining the Dijkstra algorithm with the contract net protocol, the task allocation node of high ″cost-effective″ is chosen by balancing the capability of fault diagnosis and the path weight. Simulation results show that the extended contract net task allocation algorithm reduces the traffic and improve the allocation efficiency.

Task allocation Collaborative fault diagnosis Extended contract net Dijkstra algorithm

2015-12-08。遼寧省優(yōu)秀人才基金項目(LR2013056)。陳波，教授，主研領域：遠程協(xié)同故障診斷及CSCW理論研究，工程實踐和教學。朱坤博，碩士。杜秀麗，教授。王運明，博士。

TP3

A

10.3969/j.issn.1000-386x.2017.02.050