張 洋,鄭云鵬

(長春工業(yè)大學(xué)人文信息學(xué)院,吉林 長春 130000)

1 引言

計算機在當前的工作、日常生活中應(yīng)用廣泛[1],隨著企業(yè)的生產(chǎn)、經(jīng)營等多任務(wù)的信息化,工作流管理系統(tǒng)得到了關(guān)注。工作流主要是指業(yè)務(wù)在計算機環(huán)境下進行自動化[2],其中包括工作流多終端引擎。多終端引擎的一個重要功能就是將業(yè)務(wù)內(nèi)的各項任務(wù)分發(fā)到合適的執(zhí)行者中,以此執(zhí)行任務(wù)。但多終端引擎也存在任務(wù)過多導(dǎo)致出現(xiàn)分配錯亂的問題。

為了解決這一問題,需要對多終端引擎任務(wù)分配方法進行研究。范澤軍[3]等人提出基于約束的空間眾包多階段任務(wù)分配方法,該方法首先對不同的目標進行優(yōu)化并對任務(wù)路徑集合進行獲取,將路徑起點及終點處對任務(wù)的參與者進行確立,根據(jù)上述流程,將任務(wù)分解成不同的子任務(wù),以此提升任務(wù)分配效率,該方法分解子任務(wù)時分解效果不明顯,但是存在分配效能低的問題。張濤[4]等人提出基于改進煙花算法的多目標多機器人任務(wù)分配方法,該方法優(yōu)先探討了目標排序方法,確立的目標選擇策略為了明確所提方法的性能是否最優(yōu),選取七個實例與其進行對比測試,并對所提方法與四種多目標算法進行比較分析,根據(jù)目標的解集質(zhì)量與覆蓋度,對任務(wù)進行規(guī)劃分配,實現(xiàn)任務(wù)分配方法,但是該方法進行對比測試時效果不明顯,導(dǎo)致任務(wù)在分配過程中分配時間長。陳俠[5]等人提出多UAV攻擊移動目標的協(xié)同任務(wù)分配與航跡規(guī)劃方法,該方法首先構(gòu)建了任務(wù)分配模型,采用蟻群算法對模型中的多個移動目標進行規(guī)劃,從中得出效費差最大的任務(wù)分配和規(guī)劃方案,但是該方法規(guī)范效果不完善,存在負載均衡度差的問題。

為了解決上述方法中存在的問題,提出基于群智感知計算的多終端引擎任務(wù)分配方法。

2 基于群智感知計算的多終端引擎數(shù)據(jù)采集

群智感知計算[6]的本質(zhì)是一種特殊的無線傳感網(wǎng)絡(luò),節(jié)點的移動性是它的主要特征。由于群智感知涉及的方面比較廣,其中有感知數(shù)據(jù)采集、數(shù)據(jù)分析和處理等。為了實現(xiàn)多終端引擎任務(wù)分配方法,首先需要采用群智感知計算方法對多終端引擎的狀態(tài)數(shù)據(jù)進行采集。

2.1 群智感知系統(tǒng)建模

多終端引擎中存在大部分冗余感知數(shù)據(jù),所以針對這些冗余感知數(shù)據(jù)對感知區(qū)域進行時空域劃分,根據(jù)劃分過程對建立模型,以達到降低多終端引擎節(jié)點數(shù)據(jù)采樣次數(shù)和冗余數(shù)據(jù)的目的,最終對處理的數(shù)據(jù)進行采集,實現(xiàn)基于群智感知計算的多終端引擎數(shù)據(jù)采集。

2.1.1 群智感知時空域劃分

多終端引擎通過群智感知計算進行數(shù)據(jù)采集及范圍感知,從中增強了時空數(shù)據(jù)的特征,為了便于更好的處理感知數(shù)據(jù),需要對時空域進行離散化[7]。

假設(shè)n個節(jié)點會組建成群智感知節(jié)點網(wǎng)絡(luò),那么它的集合就由U={u1,u2,u3,…,un}來描述。在感知區(qū)域中,這些節(jié)點以固定軌跡進行移動,根據(jù)移動的固定頻率對多終端引擎數(shù)據(jù)進行信息采集。在t時刻時,節(jié)點ui的位置標記為Loci(t),這時劃分的時空域流程如下所示:

1)將感知區(qū)域在空間域中劃分成相同的單元格,它的大小就是感知空間粒度。設(shè)置劃分的單元格為m個,那么感知區(qū)域標志為C={c1,c2,c3,…,cm}。

2)對節(jié)點感知時長進行劃分,取得感知周期Tsp,當開始進行感知周期時,節(jié)點會自行采樣,將數(shù)據(jù)輸送到遠程服務(wù)器中,為了便于建立感知系統(tǒng)模型,需要滿足于下述條件:

①通過多個感知周期r構(gòu)建成的覆蓋周期Tcp,即Tcp=rTsp。

②經(jīng)多個覆蓋周期組成的節(jié)點就是時間跨度。

滿足上述條件后,構(gòu)建出群智感知系統(tǒng)模型,這時感知節(jié)點時空域劃分如圖1所示。

圖1 感知空間域劃分

2.2 群智感知網(wǎng)絡(luò)相關(guān)概念

定義1:感知覆蓋。當感知周期更新時,有某個移動節(jié)點位置在單元格中,這時單元格已經(jīng)被覆蓋。將δj(Loci(t))標記為t時刻節(jié)點ui是否對單元格cj進行覆蓋,那么方程表達式定義為

δj(Loci(t))

(1)

式中,δj(Loci(t))=1時,標記為單元格cj被ui覆蓋;當δj(Loci(t))=0時,標記為沒有被覆蓋。and標記為連接詞,if標記為如果,otherwise標記為除此之外。在采樣過程中,單元格只需要被覆蓋一次,不需要重復(fù)覆蓋,而覆蓋周期就是感知粒度。

定義2:設(shè)置(1,2,3,…,d)為覆蓋周期,在(1,2,3,…,d)中節(jié)點集合U覆蓋單元格cj節(jié)點的總次數(shù)為

(2)

式中,CSDj(k)表示覆蓋總次數(shù)。

定義3:當?shù)趉個覆蓋周期存有一個單元格cj∈C時,它的覆蓋總次數(shù)要高于覆蓋因子ε(ε≥1),這說明單元格已經(jīng)被覆蓋,定義為:CSDj(k)≥ε,即充足感知覆蓋。

定義中,傳統(tǒng)無線網(wǎng)的K-覆蓋就是覆蓋因子[8]的范圍,它決定了數(shù)據(jù)的冗余程度。同理,當ε的取值越大時,冗余數(shù)據(jù)逐漸增多,產(chǎn)生的耗能影響越大。對相同單元格的ε感知數(shù)據(jù)進行融合后,就可以提升感知數(shù)據(jù)的精確度。

2.3 基于群智感知的多終端引擎狀態(tài)數(shù)據(jù)采集

基于上述分析,采用群智感知計算方法對多終端引擎數(shù)據(jù)進行采集,具體采集流程如下所示:

當覆蓋周期開始時,就需要通過節(jié)點對覆蓋感知表SCT進行清理,將其數(shù)據(jù)清空,cj被ui采樣前,應(yīng)優(yōu)先對SCT進行判斷,判斷在SCTi中是否存在與cj相對應(yīng)的元組,若元組內(nèi)有和覆蓋因子相同的采樣次數(shù),那么不進行采樣,若沒有,就進行采樣,同時對SCT進行更新。如果SCT沒有對應(yīng)的元組,就直接將小于cj、大于1的元組加入到SCT中;如果SCT具有對應(yīng)的元組,那么就將采樣后的單元格更新為ej+1,ej+1就是采集后的多終端引擎狀態(tài)數(shù)據(jù),以此完成多終端引擎狀態(tài)數(shù)據(jù)的采集。

3 多終端引擎任務(wù)分配

3.1 多終端引擎任務(wù)分配模型

多終端引擎是工作流系統(tǒng)的核心所在[9],它的主要任務(wù)在于內(nèi)部的任務(wù)分配器分配系統(tǒng)任務(wù),從而保證多終端引擎能夠?qū)崿F(xiàn)高效分配效率,那么多終端引擎任務(wù)分配器模型如圖2所示。

圖2 多終端引擎任務(wù)分配器模型

圖2中,如果多終端引擎任務(wù)的總數(shù)目標記為S,運行節(jié)點標記為K,而R={R1,R2,…,Rn}標記為用戶相關(guān)權(quán)限集合,任務(wù)集合通過W={W1,W2,…,Wn}來表示。當多終端引擎發(fā)出不同類型任務(wù)時,它的發(fā)送時間具有隨機性,可以對人員Ri處理任務(wù)Wj時對其進行處理,處理的平均時間標記為Ti,j。

任務(wù)分配器[10,11]在第x天分配任務(wù)時,需要對不同類型任務(wù)負載相對均衡度進行確立,同時還要在流程動態(tài)變化的基礎(chǔ)上,在規(guī)定時間內(nèi)以最快速度完成任務(wù)分配,因此采用任務(wù)分配算法對多終端引擎任務(wù)進行分配。

3.2 任務(wù)分配算法

依據(jù)任務(wù)分配算法[12]的主要原則給出分配算法的具體步驟,多終端引擎任務(wù)分配算法的主要流程如下所示:

1)首先在候選用戶集合中挑選出可以執(zhí)行任務(wù)的用戶,并對其角色進行匹配,依據(jù)待分配任務(wù)T對接受任務(wù)的用戶角色進行確立。由于用戶角色是動態(tài)變化的,可以將動態(tài)任務(wù)分配給具有多個任務(wù)角色的用戶。即,在可以完成任務(wù)T的具體角色集合JX中進行選取,從中獲取行的集合RJ。

2)技能匹配。用戶接受任務(wù)T時必須具備能夠完成該任務(wù)的技能,依據(jù)技能集合JT,在用戶集合RJ中選出RJ的所有用戶,取得集合RT,J。

3)相對局部負載LX和經(jīng)驗值EX需要在RT,J中進行確立,并權(quán)衡確立后的結(jié)果,從中選擇最優(yōu)用戶接收該任務(wù)。設(shè)置兩個權(quán)重系數(shù)a、b確定最佳用戶,這時的最佳用戶由RT來標記,從中得出:RT=aLX+bEX。式中,a,b均為大于0的常數(shù),同時a+b=1,RT的值標記為最佳用戶。

根據(jù)采集的多終端引擎狀態(tài)數(shù)據(jù),構(gòu)建出多終端引擎任務(wù)分配器模型,依據(jù)多終端引擎在執(zhí)行過程中的用戶狀態(tài)及負載運行狀況,采用任務(wù)分配算法將任務(wù)分配到負載低、經(jīng)驗高的用戶中,從而達到縮短任務(wù)執(zhí)行時間,并提高了分配效率,實現(xiàn)多終端引擎任務(wù)分配方法。

4 實驗與分析

為了驗證多終端引擎任務(wù)分配方法的整體有效性,需要對該方法進行實驗對比測試。

采用本文所提的基于群智感知計算的多終端引擎任務(wù)分配方法(方法1)、文獻[3]提出的基于約束的空間眾包多階段任務(wù)分配方法(方法2)和文獻[5]提出的多UAV攻擊移動目標的協(xié)同任務(wù)分配與航跡規(guī)劃(方法3)對多終端引擎任務(wù)分配方法進行測試對比。

為了驗證多終端引擎任務(wù)的分配效率,采用方法1、方法2和方法3分別對多終端引擎任務(wù)分配時間進行對比測試,設(shè)定多終端引擎任務(wù)數(shù)目為500個,對其進行分配,分配時間越短,說明分配速度越快,分配效率越高,具體測試結(jié)果如圖3所示。

圖3 多終端引擎任務(wù)分配時間測試

根據(jù)圖3中的數(shù)據(jù)發(fā)現(xiàn),三種方法隨著多終端引擎任務(wù)數(shù)目的增加,分配時間都呈現(xiàn)出上升趨勢。從總體來看,方法1的分配時間要低于方法2和方法3,由此可見方法1的分配速度最快,分配效率最高。而方法3整個測試過程中,分配時間最高,可知方法3的分配速度最慢,同時分配效率最低。

基于上述對多終端引擎任務(wù)分配的測試,驗證了方法1的分配時間速度快,在此基礎(chǔ)上利用三種方法分別對多終端引擎任務(wù)分配效能進行測試,分配效能越高,說明多終端引擎任務(wù)分配效果越好,完成任務(wù)的速度越快,測試結(jié)果如圖4所示。

圖4 多終端引擎任務(wù)分配效能測試

分析圖4中的數(shù)據(jù)可知,三種方法隨著任務(wù)數(shù)目的增加,分配效能都呈現(xiàn)出下降趨勢,在測試期間,方法1的分配效能要優(yōu)于方法2和方法3,同時運動軌跡下降速度較慢,可見方法1的分配效能最高,多終端引擎任務(wù)分配效果最好。

而方法2和方法3在初始測試時,分配效能一致,當任務(wù)數(shù)目逐步增加后,方法3的運動軌跡下降速度要比方法2的下降速度快,可見方法3是三種方法中分配效能最差的,同時它的多終端引擎任務(wù)分配效果低。

綜上所述,方法1的分配效能最高,這是因為方法1采集了多終端引擎任務(wù)狀態(tài)數(shù)據(jù),大大的提升了多終端引擎任務(wù)分配效果,進而降低了多終端引擎任務(wù)分配效能下降速度。

利用方法1、方法2和方法3分別對多終端引擎任務(wù)分配后的負載均衡度進行對比測試,負載均衡度越高,說明多終端引擎的穩(wěn)定性越強,測試結(jié)果如表1所示。

表1 不同方法的負載均衡度對比測試

根據(jù)表1中的數(shù)據(jù)發(fā)現(xiàn),在整體測試期間,方法1的負載均衡度始終保持最高,其次為方法2、方法3,這說明方法1的多終端引擎穩(wěn)定性最高,方法3的穩(wěn)定性最低。

5 結(jié)束語

傳統(tǒng)的多終端引擎任務(wù)存在時間長、分配效能低、負載均衡度差的問題。針對上述問題,提出基于群智感知計算的多終端引擎任務(wù)分配方法,該方法首先采用群智感知方法對多終端引擎狀態(tài)任務(wù)數(shù)據(jù)進行采集,根據(jù)采集的數(shù)據(jù)構(gòu)建出任務(wù)分配模型,利用任務(wù)分配算法對多終端引擎任務(wù)進行分配,從而實現(xiàn)多終端引擎任務(wù)分配方法。該方法對多終端引擎任務(wù)分配方法的有效性有著顯著的提升,在今后多終端引擎任務(wù)分配方法中占據(jù)著重要地位。