遷移工作流過程分解及其規(guī)劃方法研究.pdf

1、遷移工作流是一類基于移動agent技術(shù)的工作流管理范型。在遷移工作流模型中，遷移實例是任務(wù)的執(zhí)行主體，工作位置是遷移實例的運行場所。遷移實例攜帶任務(wù)、目標和數(shù)據(jù)在分布的工作位置之間遷移，利用工作位置所提供的服務(wù)執(zhí)行任務(wù)并接受服務(wù)結(jié)果，無需每一步都通過中心工作流引擎來交換數(shù)據(jù)，從而將集中在中心引擎上的控制邏輯分散到各遷移實例；遷移實例在執(zhí)行任務(wù)過程中，能夠根據(jù)環(huán)境的變化自治地決策遷移動作，當發(fā)現(xiàn)當前的工作位置不能滿足其執(zhí)行要求時，遷移實例

2、將遷移到另一個能滿足其要求的工作位置上繼續(xù)執(zhí)行：除遷移時間外，遷移實例的工作過程無需依賴網(wǎng)絡(luò)連接。因此，遷移工作流模型大大提高了工作流系統(tǒng)適應動態(tài)環(huán)境的靈活性，特別適合那些執(zhí)行環(huán)境動態(tài)多變和需要大量調(diào)用遠程服務(wù)的分布式業(yè)務(wù)并發(fā)處理過程。
　　 遷移工作流技術(shù)的實質(zhì)是利用遷移實例的群體智能實現(xiàn)工作流的整體執(zhí)行目標，其核心是多遷移實例路徑規(guī)劃問題，即確定如何對任務(wù)進行有效分配，并根據(jù)執(zhí)行環(huán)境生成滿足執(zhí)行目標的位置序列。按照智能規(guī)劃思

3、想，遷移實例的路徑規(guī)劃主要包括過程分解、個體路徑規(guī)劃和群體路徑規(guī)劃三個關(guān)鍵步驟。過程分解的目標是生成符合遷移實例執(zhí)行特征，且覆蓋整個任務(wù)集的過程分支的集合，每個過程分支包含任務(wù)序列與執(zhí)行目標；基于過程分解結(jié)果，遷移實例個體路徑規(guī)劃將給出在動態(tài)不確定的執(zhí)行環(huán)境下，采用何種方法選擇工作位置來執(zhí)行所分配的任務(wù)序列并達到預期的執(zhí)行目標；群體路徑規(guī)劃基于個體路徑規(guī)劃，同時要考慮遷移實例之間的群體協(xié)作，即：遷移實例為實現(xiàn)群體目標而進行的個體目標協(xié)調(diào)

4、，包括遷移實例之間組織結(jié)構(gòu)、沖突消解策略以及通信協(xié)議等。
　　 本文基于山東大學移動計算實驗室自行研發(fā)的遷移工作流管理系統(tǒng)框架，結(jié)合國家自然科學基金課題“面向目標的遷移工作流方法研究”，對遷移工作流執(zhí)行系統(tǒng)的兩個關(guān)鍵問題：業(yè)務(wù)過程分解和遷移實例路徑規(guī)劃進行了系統(tǒng)的研究，內(nèi)容涵蓋：基于極大覆蓋子樹的工作流過程域分解、面向多層次主從結(jié)構(gòu)的業(yè)務(wù)過程并行分解、過程分支的靜態(tài)規(guī)劃、面向不確定執(zhí)行環(huán)境的遷移實例個體在線路徑規(guī)劃和多遷移實例部

5、分全局路徑規(guī)劃，并在原型系統(tǒng)平臺上對上述工作進行了驗證和分析。
　　 本文工作的主要研究內(nèi)容包括：
　　 1.面向遷移實例群體協(xié)作的遷移工作流過程分解方法研究。
　　 不同于基于RPC(Remote Procedure Call)的工作流過程分解，遷移工作流過程分解的目的是服務(wù)于遷移實例對業(yè)務(wù)過程的協(xié)同規(guī)劃與執(zhí)行，由于任務(wù)之間的關(guān)系決定了遷移實例之間的角色定位，因而業(yè)務(wù)過程的分解需要考慮任務(wù)分配后遷移實例的組織結(jié)

6、構(gòu)和協(xié)作方式。本文將遷移工作流過程分解劃分為兩個步驟：域分解和并行分解。域分解面向大規(guī)模業(yè)務(wù)過程，分解的目的是為了降低直接并行分解以及遷移實例群體協(xié)作的高復雜性。針對域分解，本文提出一種基于極大覆蓋子樹的過程分解算法。并行分解面向遷移實例的群體規(guī)劃，將業(yè)務(wù)過程逐層分解為一組具有主從關(guān)聯(lián)的過程分支的集合，其分解方法是按任務(wù)粒度求解過程圖的關(guān)鍵路徑，然后逐層分離以關(guān)鍵路徑遍歷的過程分支，按樹型結(jié)構(gòu)形成過程分支之間的主從支配關(guān)系，并使之轉(zhuǎn)化為

7、遷移實例之間的協(xié)作關(guān)系。本文針對服務(wù)質(zhì)量約束的工作流執(zhí)行系統(tǒng)，分別給出了業(yè)務(wù)過程結(jié)構(gòu)分解的算法和服務(wù)質(zhì)量約束的分配算法，并對所生成的過程分支給出一種靜態(tài)路徑規(guī)劃離散粒子群優(yōu)化算法。
　　 2.面向不確定執(zhí)行環(huán)境的遷移實例個體在線路徑規(guī)劃方法研究。
　　 對于不確定的執(zhí)行環(huán)境，遷移實例在工作過程中難以做出一個整體的路徑規(guī)劃，只能根據(jù)當前執(zhí)行環(huán)境的狀況采取階段性尋優(yōu)的規(guī)劃方式。本文基于Markov決策過程(Markov：De

8、cision Process，MDP)建模時間約束的遷移實例個體在線路徑規(guī)劃，以任務(wù)劃分執(zhí)行階段，以剩余執(zhí)行時間、時間臨界度、時間偏移度和規(guī)劃深度為狀態(tài)變量，在每個執(zhí)行階段，遷移實例根據(jù)當前環(huán)境的動態(tài)性確定一個規(guī)劃窗口，在當前規(guī)劃窗口內(nèi)求解滿足約束的最優(yōu)遷移路徑。由于規(guī)劃深度(規(guī)劃窗口的大小)取決于執(zhí)行環(huán)境的不確定程度，因而需要一種對執(zhí)行環(huán)境不確定性的度量方法。本文借鑒信息熵的概念，提出一種通過周期采樣計算工作位置服務(wù)質(zhì)量穩(wěn)定性熵和服務(wù)

9、數(shù)量穩(wěn)定性熵的方法，并基于工作位置的服務(wù)穩(wěn)定性來度量執(zhí)行環(huán)境的不確定性，然后根據(jù)環(huán)境的不確定性設(shè)置規(guī)劃深度。實驗表明，該方法既具有良好的動態(tài)環(huán)境適應性，又兼顧了整體路徑規(guī)劃的長遠性。
　　 3.面向群體協(xié)作的遷移實例部分全局路徑規(guī)劃方法及其體系結(jié)構(gòu)研究。
　　 在大規(guī)模遷移工作流管理系統(tǒng)中，業(yè)務(wù)過程通常由多個遷移實例協(xié)同完成。由于個體路徑規(guī)劃僅關(guān)注遷移實例自身目標的優(yōu)化實現(xiàn)，缺少遷移實例之間的通信與協(xié)商，因而不能保證生成

10、路徑的全局最優(yōu)性。本文基于部分可觀察Markov決策過程(Partidally Observable Markov Decision Process，POMDP)建模多遷移實例部分全局路徑規(guī)劃，提出一種遷移實例部分全局規(guī)劃兩層體系結(jié)構(gòu)，將群體路徑規(guī)劃問題劃分為協(xié)作層和個體規(guī)劃層，其中，協(xié)作層面向群體協(xié)作，關(guān)注遷移實例的組織方式、沖突消解策略以及遷移實例之間的通信協(xié)商，其目標是通過協(xié)商確定個體規(guī)劃的執(zhí)行目標，而不需要考慮對每個任務(wù)的規(guī)劃細

11、節(jié)；個體規(guī)劃層則針對協(xié)作層制定的個體執(zhí)行目標，關(guān)注該目標的實現(xiàn)方法，而無需考慮群體協(xié)作問題。在個體規(guī)劃層，采用個體在線路徑規(guī)劃方法；在協(xié)作層，本文給出了一種遷移實例的樹型組織結(jié)構(gòu)，基于該結(jié)構(gòu)提出了一種遷移實例的協(xié)作通信協(xié)議以及服務(wù)沖突和目標沖突的消解策略與實現(xiàn)方法。這種分層規(guī)劃的思想有效地簡化了遷移實例群體規(guī)劃的復雜性，為多智能體的協(xié)同計算在工作流技術(shù)中的應用提供一種有價值的探索。
　　 本文工作的創(chuàng)新點主要體現(xiàn)在：
　　

12、 1.提出了一種基于多層次主從結(jié)構(gòu)的結(jié)構(gòu)化業(yè)務(wù)過程并行分解方法。
　　 不同于中心化WfMC模型的分解，遷移工作流過程分解的核心是如何支持非中心化的遷移實例有序協(xié)作。本文提出的基于多層次主從結(jié)構(gòu)的遷移工作流過程并行分解方法，以樹型結(jié)構(gòu)表示過程分支之間的主從關(guān)系，以過程分支中的同步任務(wù)為協(xié)作關(guān)鍵點。因為在任務(wù)指派之后，過程分解樹可以等價地映射為遷移實例組織樹，所以，遷移實例可以基于過程分支之間的主從關(guān)系和協(xié)作關(guān)鍵點實現(xiàn)按需協(xié)商，

13、使協(xié)作有序。與不區(qū)分主從關(guān)系的分解方法相比，樹形結(jié)構(gòu)表示的主從關(guān)系能夠提供更加清晰的協(xié)作線索，有效支持遷移實例之間的自主協(xié)作。
　　 2.提出了一種基于MDP和不確定執(zhí)行環(huán)境的遷移實例在線路徑規(guī)劃方法。
　　 不同于已知全局環(huán)境的路徑規(guī)劃方法，遷移實例在線路徑規(guī)劃的核心是如何度量執(zhí)行環(huán)境的不確定性并采取相應的行為策略。本文提出的基于MDP和不確定執(zhí)行環(huán)境的遷移實例在線路徑規(guī)劃方法，以服務(wù)穩(wěn)定性熵度量執(zhí)行環(huán)境的不確定性，以

14、規(guī)劃窗口為行為策略，與基于貪心策略的一步規(guī)劃方法相比，基于環(huán)境不確定性度量的規(guī)劃窗口方法，既具有對不確定性執(zhí)行環(huán)境的動態(tài)適應性，又兼顧了整體規(guī)劃的長遠性。
　　 3.提出了一種基于POMDP的多遷移實例部分全局路徑規(guī)劃方法。
　　 除業(yè)務(wù)過程分解方法必須支持遷移實例有序協(xié)作外，遷移實例群體規(guī)劃的另一個目標是如何簡化群體規(guī)劃的復雜度，提高業(yè)務(wù)過程的執(zhí)行效率。本文提出的基于POMDP的遷移實例部分全局路徑規(guī)劃方法，以同步任務(wù)

15、劃分全局規(guī)劃的執(zhí)行階段，以基于同步任務(wù)劃分的任務(wù)幀為個體規(guī)劃單元，全局規(guī)劃實現(xiàn)目標在協(xié)作遷移實例之間的分配，部分規(guī)劃實現(xiàn)遷移實例基于任務(wù)幀和目標分配的路徑構(gòu)建。與不分層的群體規(guī)劃方法相比，由協(xié)作層和個體規(guī)劃層組成的體系結(jié)構(gòu)可以有效降低遷移實例群體路徑規(guī)劃的實現(xiàn)復雜度，提高個體規(guī)劃在實現(xiàn)方法上的靈活性。
　　 本文所提出的遷移工作流過程分解與規(guī)劃方法在仿真實驗和應用實例中已得到驗證，但遷移工作流的群體規(guī)劃是一個復雜的問題，還有很多

16、值得探索和改進的方面，進一步的研究工作包括：
　　 1.業(yè)務(wù)過程在線分解與任務(wù)合并方法。對于復雜和多變的執(zhí)行環(huán)境，單純的事前分解可能使過程分支粒度的適應性不夠，因此，如何支持遷移實例對業(yè)務(wù)過程的在線分解與任務(wù)合并具有非常實際的意義。在以后的研究中，應考慮將過程分解納入遷移實例在線路徑規(guī)劃中，以實現(xiàn)動態(tài)執(zhí)行環(huán)境下的業(yè)務(wù)過程按需分解。
　　 2.非結(jié)構(gòu)化業(yè)務(wù)過程分解與群體路徑規(guī)劃方法。本文以結(jié)構(gòu)化業(yè)務(wù)過程為研究對象，而非結(jié)構(gòu)