P2P工作流系統(tǒng)中的資源搜索及負(fù)載均衡優(yōu)化研究.pdf

1、工作流是一類集成業(yè)務(wù)活動(dòng)并使其能夠自動(dòng)化或半自動(dòng)化完成的計(jì)算機(jī)支持的協(xié)同工作技術(shù)，是計(jì)算機(jī)科學(xué)、自動(dòng)控制科學(xué)、管理科學(xué)和先進(jìn)制造等多學(xué)科領(lǐng)域共同關(guān)注與研究的熱點(diǎn)問題之一，其核心是通過業(yè)務(wù)流程，協(xié)同網(wǎng)絡(luò)中分布的計(jì)算資源和業(yè)務(wù)行為，并可進(jìn)一步引申為對網(wǎng)絡(luò)計(jì)算能力的挖掘。
　　 基于對等計(jì)算范型構(gòu)造的工作流系統(tǒng)稱為P2P工作流系統(tǒng)。它將工作流模型中的邏輯關(guān)系映射到一個(gè)活動(dòng)及其轉(zhuǎn)移規(guī)則的集合，使活動(dòng)所在節(jié)點(diǎn)不經(jīng)過中心化工作流引擎，而直接

2、與其邏輯前驅(qū)節(jié)點(diǎn)和后繼節(jié)點(diǎn)進(jìn)行通信和數(shù)據(jù)交換，從而將控制流和數(shù)據(jù)流分布到每一個(gè)任務(wù)執(zhí)行節(jié)點(diǎn)上，并在工作流網(wǎng)絡(luò)上展現(xiàn)為自組織的工作流程，體現(xiàn)了工作流的分布特質(zhì)。P2P工作流是一種去中心化的計(jì)算模式，消除了集中式工作流系統(tǒng)中那些由中心化控制結(jié)構(gòu)造成的性能瓶頸，為大規(guī)模業(yè)務(wù)過程協(xié)同提供了一種具有高度柔性、可擴(kuò)展性和容錯(cuò)能力的計(jì)算技術(shù)，被認(rèn)為是工作流研究和應(yīng)用領(lǐng)域最具戰(zhàn)略意義的方向之一。
　　 中心化工作流引擎的消除，使得對等點(diǎn)之間主要

3、以自組織的方式形成工作流網(wǎng)絡(luò)的控制結(jié)構(gòu)，而支撐這種自治體制的核心即高效的對等點(diǎn)協(xié)同策略。因此，對等點(diǎn)之間的協(xié)同效率是決定P2P工作流系統(tǒng)性能的關(guān)鍵因素。在實(shí)際業(yè)務(wù)流程運(yùn)行過程中，協(xié)同效率主要體現(xiàn)為工作流實(shí)例(Workflow Instance，WI)在系統(tǒng)中的運(yùn)行時(shí)間。從這個(gè)角度考慮，基于最短運(yùn)行時(shí)間的WI的最優(yōu)執(zhí)行路徑規(guī)劃(The Optimal Path Planning，OPP)成為了制約P2P工作流系統(tǒng)性能優(yōu)化的關(guān)鍵問題。在沒有

4、調(diào)度中心且網(wǎng)絡(luò)拓?fù)浼皡?shù)動(dòng)態(tài)變化的對等網(wǎng)環(huán)境中，OPP問題體現(xiàn)出三個(gè)明顯的特點(diǎn)：1.網(wǎng)絡(luò)中各節(jié)點(diǎn)的計(jì)算資源、負(fù)載狀況、通信帶寬和網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)動(dòng)態(tài)變化；2.節(jié)點(diǎn)信息的局部可視化：3.執(zhí)行路徑的強(qiáng)指向性。
　　 具有上述特點(diǎn)的OPP問題標(biāo)識(shí)了一類全新的路徑規(guī)劃問題，稱為分布式最優(yōu)路徑規(guī)劃問題(Distributed Optimal Path Planning，D-OPP)，即在大規(guī)模動(dòng)態(tài)網(wǎng)絡(luò)中，根據(jù)局部信息求解具有最小執(zhí)行時(shí)間的全

5、局最優(yōu)路徑的問題。由于D-OPP問題的局部可視性和強(qiáng)指向性，WI的運(yùn)行時(shí)間主要由任務(wù)的執(zhí)行時(shí)間(TaskExecution Time，TET)和對執(zhí)行節(jié)點(diǎn)的搜索時(shí)間(Peer Sesearch Time，PST)構(gòu)成。因此，對路徑執(zhí)行時(shí)間的優(yōu)化問題就可以被分解為兩個(gè)子問題：1.去中心化P2P工作流網(wǎng)絡(luò)中的資源搜索問題，即對擁有所需計(jì)算資源的執(zhí)行節(jié)點(diǎn)集合的搜索問題，以實(shí)現(xiàn)搜索時(shí)間最小化為目的；2.去中心化動(dòng)態(tài)負(fù)載均衡問題，即在最短時(shí)間內(nèi)實(shí)

6、現(xiàn)去中心化的實(shí)時(shí)任務(wù)調(diào)度，以找到具有最小任務(wù)執(zhí)行時(shí)間的節(jié)點(diǎn)，并形成優(yōu)化的負(fù)載分布為目的。上述兩個(gè)子問題在工作流程各個(gè)執(zhí)行步中的最優(yōu)解的組合，最終將擬合出D-OPP問題的全局最優(yōu)解。
　　 本文重點(diǎn)研究了P2P工作流系統(tǒng)中的去中心化資源搜索和動(dòng)態(tài)負(fù)載均衡的優(yōu)化問題，其成果不僅使P2P工作流系統(tǒng)同時(shí)具備靈活的架構(gòu)和優(yōu)異的執(zhí)行效率，而且在更普遍意義上為分布式計(jì)算資源的整合以及分布式計(jì)算模式的大范圍部署提供了有力的支持。本文的主要工作包

7、括：
　　 1.分布式最優(yōu)路徑規(guī)劃問題(D-OPP)的形式化描述和分析。
　　 P2P工作流的主要特征在于完全分布的控制結(jié)構(gòu)，可理解為工作流實(shí)例基于服務(wù)聚類，在各服務(wù)集之間依據(jù)局部邏輯約束自治的跳轉(zhuǎn)過程。因此，D-OPP問題本質(zhì)上具有層次性特征，包括服務(wù)集之間和服務(wù)集內(nèi)部兩個(gè)層次，分別對應(yīng)去中心化資源搜索問題和去中心化動(dòng)態(tài)負(fù)載均衡問題。本文第二章從服務(wù)聚類的角度給出了P2P工作流系統(tǒng)的體系結(jié)構(gòu)，并在此基礎(chǔ)上，利用Mark

8、ov鏈對D-OPP問題進(jìn)行形式化建模與分析，給出了問題最優(yōu)解的總體結(jié)構(gòu)，即最優(yōu)的去中心化資源搜索和負(fù)載均衡算法。
　　 2.去中心化動(dòng)態(tài)P2P工作流資源搜索網(wǎng)絡(luò)研究。針對D-OPP問題的第一個(gè)子目標(biāo)，研究去中心化資源搜索問題，給出具有最小搜索步數(shù)的最優(yōu)解。
　　 去中心化資源搜索問題要求在沒有路由中心的P2P網(wǎng)絡(luò)環(huán)境中快速定位當(dāng)前工作流程所需的服務(wù)集。對于P2P網(wǎng)絡(luò)，結(jié)構(gòu)化P2P方法較非結(jié)構(gòu)化P2P方法具有更優(yōu)的路由效率

9、，因此，本文將結(jié)構(gòu)化P2P的設(shè)計(jì)引入工作流系統(tǒng)，在P2P工作流的域間層次中，通過構(gòu)建結(jié)構(gòu)化P2P網(wǎng)絡(luò)組織各服務(wù)集合，實(shí)現(xiàn)最優(yōu)的搜索效率。本文第三章分別提出了服務(wù)尋址網(wǎng)絡(luò)(Services Addressed Network，SAN)和基于邏輯映射碼(Logic Mapping Coding，LMC)的生成圖定位網(wǎng)絡(luò)(Spanning Graph Location Network，SGLN)。SAN可看作多層CAN網(wǎng)絡(luò)的疊加，較之當(dāng)前代表

10、性的P2P工作流網(wǎng)絡(luò)，它有效提高了搜索效率，降低了路由帶寬，獲得了100％的路由精度；SGLN根據(jù)。LMC將工作流程映射為P2P網(wǎng)絡(luò)拓?fù)洌峁┝薕(1)的最優(yōu)路由時(shí)間復(fù)雜度，并且沒有引入任何的額外路由負(fù)載以及冗余拓?fù)浣Y(jié)構(gòu)，同時(shí)具有多通道的并行處理能力以及較小的空間復(fù)雜度，給出了D-OPP中去中心化資源搜索問題的最優(yōu)解。本文通過算法和實(shí)例分析給出了SAN和SGLN網(wǎng)絡(luò)的時(shí)間和空間復(fù)雜度以及構(gòu)建過程，并與典型的結(jié)構(gòu)化P2P網(wǎng)絡(luò)和工作流系統(tǒng)進(jìn)

11、行了對比分析。
　　 3.P2P工作負(fù)載均衡網(wǎng)絡(luò)研究。
　　 對于去中心化動(dòng)態(tài)負(fù)載均衡問題的解決，有兩個(gè)關(guān)鍵點(diǎn)：(1)具有能夠?qū)崟r(shí)表達(dá)系統(tǒng)負(fù)載狀況的基礎(chǔ)P2P網(wǎng)絡(luò)；(2)構(gòu)建在基礎(chǔ)P2P網(wǎng)絡(luò)之上的最優(yōu)隨機(jī)負(fù)載分配算法。工作負(fù)載均衡網(wǎng)絡(luò)為高效的去中心化動(dòng)態(tài)負(fù)載均衡，提供基礎(chǔ)P2P網(wǎng)絡(luò)支持，同時(shí)實(shí)現(xiàn)對SGLN和SAN各層子網(wǎng)的鏈接，即作為服務(wù)集合域內(nèi)拓?fù)涞慕M織形式。本文第四章提出一種P2P隨機(jī)網(wǎng)絡(luò)，稱為工作負(fù)載均衡網(wǎng)絡(luò)(Wo

12、rkloadBalancing Network，WBN)，實(shí)現(xiàn)了通過隨機(jī)網(wǎng)絡(luò)拓?fù)溆成涔?jié)點(diǎn)的負(fù)載處理能力，當(dāng)節(jié)點(diǎn)負(fù)載狀況發(fā)生變化時(shí)網(wǎng)絡(luò)拓?fù)浔３址€(wěn)定。大量仿真實(shí)驗(yàn)表明，WBN網(wǎng)絡(luò)展現(xiàn)出三個(gè)特性：(1)拓?fù)浣Y(jié)構(gòu)的能力相關(guān)性；(2)高度的能力聚集特性；(3)獨(dú)立于系統(tǒng)規(guī)模的小網(wǎng)絡(luò)直徑。這些特性為去中心化負(fù)載分配快速收斂到全局最優(yōu)提供了直接的支持。
　　 4.去中心化動(dòng)態(tài)負(fù)載均衡算法研究。針對D-OPP問題的第二個(gè)子目標(biāo)，研究中心化動(dòng)態(tài)負(fù)

13、載分配問題，給出具有最小收斂步數(shù)的最優(yōu)解。
　　 去中心化動(dòng)態(tài)負(fù)載分配問題主要通過構(gòu)造在基礎(chǔ)P2P網(wǎng)絡(luò)上的隨機(jī)負(fù)載分配算法解決，要求：(1)在沒有調(diào)度中心的P2P網(wǎng)絡(luò)環(huán)境中實(shí)現(xiàn)；(2)快速收斂；(3)以大概率收斂到具有最短執(zhí)行時(shí)間的最優(yōu)執(zhí)行節(jié)點(diǎn)。本文第五章基于WBN網(wǎng)絡(luò)，提出一種啟發(fā)式隨機(jī)采樣算法(Heuristic Randomized Sampling algorithm，HRSalgorithm)，稱為WBN算法，給出了D

14、-OPP中去中心化動(dòng)態(tài)負(fù)載分配問題的最優(yōu)解。在WBN網(wǎng)絡(luò)上，WBN算法以節(jié)點(diǎn)負(fù)載比例為基礎(chǔ)構(gòu)造啟發(fā)因子，通過始終隨機(jī)采樣具有更小負(fù)載比的節(jié)點(diǎn)，實(shí)現(xiàn)負(fù)載的實(shí)時(shí)分配。大量仿真實(shí)驗(yàn)表明WBN算法可以概率1將當(dāng)前負(fù)載分配到最優(yōu)執(zhí)行節(jié)點(diǎn)上，使其獲得最快的實(shí)時(shí)完成時(shí)間；而總體上形成正比于節(jié)點(diǎn)負(fù)載處理能力的最優(yōu)負(fù)載分布，使系統(tǒng)在運(yùn)行周期內(nèi)獲得最小的總負(fù)載處理時(shí)間；并且負(fù)載分配的期望采樣步數(shù)，獨(dú)立于系統(tǒng)規(guī)模和負(fù)載狀態(tài)，相對穩(wěn)定在4～4.5步，這一性能已

15、逼近最優(yōu)的中心化負(fù)載均衡。
　　 5.拓?fù)錈o關(guān)的非結(jié)構(gòu)化路徑規(guī)劃算法研究。
　　 對于D-OPP問題，SGLN網(wǎng)絡(luò)和WBN算法兩者都是通過構(gòu)造特定拓?fù)浣Y(jié)構(gòu)支持最優(yōu)性能的實(shí)現(xiàn)，若對于任意的網(wǎng)絡(luò)拓?fù)?，目前已有的非結(jié)構(gòu)化搜索和分配算法很難達(dá)到最優(yōu)性能。因此，需要一種拓?fù)錈o關(guān)的非結(jié)構(gòu)化路徑規(guī)劃方法作為對D-OPP問題最優(yōu)解的補(bǔ)充，并且具有以下特點(diǎn)：(1)去中心化方法；(2)不需要維護(hù)特定拓?fù)浣Y(jié)構(gòu)；(3)具有優(yōu)化的路徑規(guī)劃性能。路

16、徑規(guī)劃實(shí)質(zhì)上是將路由代價(jià)轉(zhuǎn)化為其他形式的構(gòu)造代價(jià)，從而從規(guī)劃的角度看實(shí)現(xiàn)了優(yōu)化。因此，在不能轉(zhuǎn)化為拓?fù)錁?gòu)造代價(jià)的情況下，本文采用反向過程，即資源的主動(dòng)發(fā)布過程，作為轉(zhuǎn)化形式實(shí)現(xiàn)D-OPP問題的優(yōu)化。本文第六章提出一種隨機(jī)令牌發(fā)布(Randomized Token Distribution，RTD)算法，以大概率在較小隨機(jī)采樣步數(shù)內(nèi)將令牌發(fā)布到需求程度較高的服務(wù)請求節(jié)點(diǎn)，實(shí)現(xiàn)了在不需要特征拓?fù)浣Y(jié)構(gòu)支持的情況下，使服務(wù)請求節(jié)點(diǎn)對目標(biāo)節(jié)點(diǎn)的一

17、步可達(dá)。本文通過大量仿真實(shí)驗(yàn)驗(yàn)證并支持了RTD算法的性能。
　　 6.分布式路徑規(guī)劃問題(D-OPP)的最優(yōu)解。
　　 SGLN網(wǎng)絡(luò)給出了D-OPP中去中心化資源搜索問題的最優(yōu)解，WBN算法給出了D-OPP中去中心化動(dòng)態(tài)負(fù)載均衡問題的最優(yōu)解，兩者結(jié)合給出了D-OPP最優(yōu)化問題的完整解，使得從當(dāng)前執(zhí)行節(jié)點(diǎn)只需經(jīng)過大約5跳就可以找到下一個(gè)最優(yōu)執(zhí)行節(jié)點(diǎn)(SGLN網(wǎng)絡(luò)1跳，WBN網(wǎng)絡(luò)4跳)。而SAN網(wǎng)絡(luò)和拓?fù)錈o關(guān)的RTD算法可作

18、為對最優(yōu)解的有效補(bǔ)充。
　　 本文工作的創(chuàng)新點(diǎn)主要體現(xiàn)在：
　　 1.提出了一種稱為服務(wù)尋址網(wǎng)絡(luò)(SAN)的結(jié)構(gòu)化P2P網(wǎng)絡(luò)，支持優(yōu)化的去中心化動(dòng)態(tài)域間資源搜索。
　　 較已有的P2P網(wǎng)絡(luò)，SAN可以為工作流系統(tǒng)提供更高的搜索效率，獲得100％的路由精度，降低路由的通信帶寬，適用于節(jié)點(diǎn)數(shù)目多且動(dòng)態(tài)變化范圍大的系統(tǒng)。
　　 2.提出了一種稱為生成圖定位網(wǎng)絡(luò)(SGLN)的結(jié)構(gòu)化P2P網(wǎng)絡(luò)，給出了基于SGLN的

19、去中心化資源搜索問題的最優(yōu)解。
　　 SGLN基于LMC將工作流程映射為P2P網(wǎng)絡(luò)拓?fù)?，提供了O(1)的最優(yōu)路由時(shí)間復(fù)雜度，沒有引入任何的額外路由負(fù)載以及冗余拓?fù)浣Y(jié)構(gòu)，同時(shí)具有多通道的并行處理能力以及較小的空間復(fù)雜度。
　　 3.提出一種稱為工作負(fù)載均衡網(wǎng)絡(luò)(WBN)的動(dòng)態(tài)隨機(jī)網(wǎng)絡(luò)，構(gòu)建了一種稱為WBN的啟發(fā)式隨機(jī)采樣算法，給出了基于WBN算法的去中心化動(dòng)態(tài)負(fù)載分配問題的最優(yōu)解。
　　 WBN網(wǎng)絡(luò)有效支持負(fù)載分配

20、快速收斂到全局最優(yōu)。WBN算法可以概率1在去中心化環(huán)境下將當(dāng)前負(fù)載分配到最優(yōu)執(zhí)行節(jié)點(diǎn)，總體上形成正比于節(jié)點(diǎn)負(fù)載處理能力的最優(yōu)負(fù)載分布，并且負(fù)載分配的期望采樣步數(shù)，獨(dú)立于系統(tǒng)規(guī)模及負(fù)載狀態(tài)，相對穩(wěn)定在4～4.5步。
　　 4.提出了一種隨機(jī)令牌發(fā)布(RTD)算法，在不需要特征拓?fù)浣Y(jié)構(gòu)支持的情況下，給出了D-OPP問題的一個(gè)滿意解。
　　 RTD算法可以較大概率，在較短期望采樣步數(shù)(主要分布在5步左右)內(nèi)，以一定的覆蓋比例將

21、令牌發(fā)布到需求程度較高的服務(wù)請求節(jié)點(diǎn)，實(shí)現(xiàn)了服務(wù)請求節(jié)點(diǎn)對最終執(zhí)行節(jié)點(diǎn)的一步可達(dá)以及優(yōu)化的負(fù)載分布。
　　 P2P工作流是一個(gè)涉及面很廣的研究課題，本文進(jìn)一步的工作主要包括：
　　 在線調(diào)度問題研究。當(dāng)節(jié)點(diǎn)需要保存大量緩存數(shù)據(jù)時(shí)，在有限的存儲(chǔ)空間中，對索引數(shù)據(jù)的選擇策略可明顯影響節(jié)點(diǎn)數(shù)據(jù)索引的效果，即在線調(diào)度問題。對于本文所有的搜索算法，可通過建立搜索對象的本地索引，提高搜索性能和系統(tǒng)的容錯(cuò)能力。
　　 物理拓?fù)?/p>