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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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