基于P2P網絡節(jié)點上下文的任務分解和調度方法研究.pdf

1、工作流是集成業(yè)務活動并使其能夠自動化或半自動化完成的一類計算機協(xié)同工作技術，是計算機科學、自動控制科學、管理科學、先進制造等多學科領域共同關注與研究的熱點問題之一，其核心是通過業(yè)務流程的執(zhí)行，協(xié)同網絡中分布的計算資源和業(yè)務行為，并可進一步引申為對網絡計算能力的挖掘。
　　 在通信、金融、保險、氣象、地震、測繪、勘探、經濟運行統(tǒng)計、科學計算、數據挖掘、經營分析等海量數據處理或者復雜業(yè)務流程處理的工作流執(zhí)行過程中，工作流執(zhí)行效率是個

2、頗受關注的普遍問題。以通信行業(yè)為例，在通信計費系統(tǒng)中，中等省份的月話單數量約為40億-50億條，每月底全省集中計費和出賬工作量非常大，按照上述計算規(guī)模，在多臺高性能服務器計算環(huán)境中進行處理，僅僅“計費”活動需要約6小時左右，完成話單采集、話單格式化、話單查重、計費、賬務處理等整個工作流程大約需要48小時左右。這一問題帶來的直接影響就是工作流執(zhí)行耗時過長、對IT基礎設施投資的需求過大。因此，研究提高工作流執(zhí)行效率的方法，具有普遍的現實意義

3、。
　　 P2P技術實現了計算模式從主-從式向對等式的轉變，網絡應用的核心從中心服務器向邊緣計算設備擴散，有效地解決了單點失效和負載均衡問題，大幅提升了網絡的整體計算能力。充分利用P2P網絡中的計算資源和計算能力，將工作流中那些運算工作量大的活動予以分解，并將其調度到優(yōu)選節(jié)點上進行分布式運算，將會大幅提升可用計算資源的利用效率和工作流的整體執(zhí)行效率。因此，P2P網絡環(huán)境中的任務分解和調度(TaskPartitioningandS

4、cheduling，TPS)是工作流研究的一個核心問題。
　　 P2P網絡環(huán)境中的任務分解和調度問題有如下特點:①P2P網絡中各節(jié)點的計算資源、通信能力、負載狀況和網絡拓撲結構是動態(tài)變化的;②由第一個特點決定了無法在事前準確計算每個節(jié)點的任務處理時間，因此將工作流執(zhí)行時間作為任務調度目標將比較困難;③結構化的、去中心化的P2P網絡節(jié)點信息的局部可視化。一種較好的解決方案是使工作流管理系統(tǒng)具有感知P2P網絡節(jié)點上下文的能力，即研究

5、解決基于P2P網絡節(jié)點上下文的任務分解和調度問題(ContextBasedTaskPartitioningandScheduling，CB-TPS)。CB-TPS問題可以分解為如下三個子問題:①任務分解問題，即將工作量大的、復雜的活動分解為工作量小的、簡單的細粒度任務集，以達到降低單個任務運算量的目的;②任務調度問題，即把分解后的子任務分配到適當的節(jié)點上運行，以實現工作流執(zhí)行效率全局最優(yōu)的目標;③執(zhí)行結果合成問題，即將各個子任務的執(zhí)行結

6、果進行合并，使之等價于任務分解前的工作流活動的執(zhí)行結果。
　　 本文重點研究了去中心結構化P2P網絡環(huán)境中的任務分解和調度方法，主要工作包括:
　　 1、基于P2P網絡節(jié)點上下文的任務分解與調度(CB-TPS)問題求解模型。
　　 本文將P2P網絡節(jié)點上下文引入工作流管理，使工作流管理系統(tǒng)能夠感知P2P網絡環(huán)境，并根據節(jié)點上下文動態(tài)地完成任務分解和調度，以實現最優(yōu)的運行效果。CB-TPS問題求解模型的基本思想是:

7、首先通過節(jié)點上下文信息獲得計算節(jié)點的計算能力和通信能力，然后據節(jié)點處理能力進行任務分解與調度。任務分解包括兩種方式:基于數據劃分的任務分解和基于功能劃分的任務分解。使用數據劃分方法進行任務分解時，首先根據獲得的節(jié)點上下文信息推算節(jié)點的計算能力，然后根據節(jié)點計算能力分配與之能力匹配的任務。使用功能劃分方法進行任務分解時，先使用獲得的節(jié)點上下文信息測算任務處理效率，再根據測算效率分配任務。本文第2章在引入節(jié)點上下文和工作流有窮狀態(tài)自動機的基

8、礎上，定義了上下文影響權重因子和節(jié)點計算能力評價指數，給出了權重因子和節(jié)點處理能力的計算方法，建立了CB-TPS問題求解模型。
　　 2、基于功能劃分的的任務分解與調度方法。
　　 基于功能劃分的任務分解方法，本質上是將工作流的特定活動，按照業(yè)務邏輯進行功能細分，即將其拆分為一組偏序連接的任務子流程，其中，每個任務對應一項特定的業(yè)務功能。分解后的任務子流程調度問題，可以通過執(zhí)行路徑規(guī)劃求解，例如列表調度、任務復制調度、遺

9、傳算法、粒子群方法、蟻群算法等。本文第3章在定義任務分解算子的基礎上，建立了一種基于工作流有窮狀態(tài)自動機的任務分解方法;在定義節(jié)點處理能力評價指數的基礎上，通過對蟻群算法的優(yōu)化改進，建立了一種蟻群任務調度算法。實驗結果表明，改進的蟻群任務調度算法，不但能夠解決工作流執(zhí)行時間等參數難于估算的問題，而且能提高任務調度的動態(tài)適應性。
　　 3、基于數據劃分的任務分解與調度算法。
　　 基于數據劃分的任務分解方法，本質上是將工作

10、流的特定活動，根據被處理數據對象的細粒度劃分，分解為一組可以并行執(zhí)行的任務。數據劃分的粒度越小，能夠參與計算的P2P網絡節(jié)點越多，工作流的效率提升效果越明顯。本文第4章在定義數據劃分的橫切模式和縱切模式的基礎上，基于各個數據子集中的索引字段值不能有交集的劃分原則，建立了一種基于數據劃分的任務分解方法;在CAN網絡基礎上，改進了洪泛和K隨機漫步資源搜索算法。實驗結果表明，改進的洪泛和K隨機漫步算法能夠快速地完成設定數量的計算節(jié)點的搜索，并

11、在資源搜索的同時獲得候選節(jié)點的處理能力。在任務調度時，工作流管理系統(tǒng)首先從候選計算節(jié)點中優(yōu)選一定數量的節(jié)點作為任務節(jié)點，然后根據這些節(jié)點的處理能力確定每個節(jié)點的任務分配強度，依據任務分配強度劃分數據并調度到相應節(jié)點上予以處理。
　　 所有子任務執(zhí)行完成后，結果合成就是將各個子任務的執(zhí)行結果進行直接合并。由于在任務分解時遵循了數據分解的不相交原則，所以執(zhí)行結果的直接合并與任務分解前的執(zhí)行結果是等價的。本文第4章給出了結果合成方法和

12、等價性證明。
　　 本文工作的創(chuàng)新點主要體現在:
　　 1、建立了一種基于P2P網絡節(jié)點本體和工作流有窮狀態(tài)自動機的任務分解與調度問題求解模型。
　　 較之鍵值對、標記語言等方法，本體可以更好地表達P2P網絡節(jié)點上下文的語義和節(jié)點的動態(tài)變化;較之WF-Net和PetriNet，工作流有窮狀態(tài)自動機可以更加靈活地表示P2P網絡中的不確定事件，動態(tài)地描述工作流的動態(tài)分拆和組裝過程。因此，基于節(jié)點本體和自動機的任務分解

13、與調度問題求解模型具有良好的P2P網絡環(huán)境適應性。
　　 2、提出了一種基于節(jié)點上下文和功能劃分的任務調度蟻群算法。
　　 改進的蟻群算法以節(jié)點處理能力指標為啟發(fā)因子，以任務執(zhí)行代價的倒數作為螞蟻經過路徑所留下的信息素濃度，既體現了基于節(jié)點上下文進行任務調度的自適應特點，又可以更好地引導調度算法向處理能力強、任務執(zhí)行代價低的節(jié)點傾斜，加速向最優(yōu)解的收斂。
　　 3、提出了一種基于節(jié)點資源快速搜索和數據劃分的任務調

14、度方法。
　　 改進的洪泛和K隨機漫步資源搜索算法，能夠快速地完成設定數量的計算節(jié)點的搜索，并基于上下文完成節(jié)點處理能力的評價;數據劃分的不相交原則可以保證數據子集的獨立性，節(jié)點處理能力評價能夠保證將任務分配到處理能力最強的節(jié)點集上，提升任務調度和執(zhí)行效率。
　　 P2P網絡環(huán)境中的工作流分解與調度是一個涉及面很廣的研究課題，本文進一步的工作主要包括:
　　 1.基于上下文的P2P覆蓋網構造優(yōu)化研究。
　　

15、 P2P網絡是在IP網絡或者其他物理網絡上的邏輯覆蓋網，其拓撲與物理網絡的實際拓撲并不完全匹配，造成P2P網絡的路由實際上并不一定是最優(yōu)的路由，可以通過上下文對邏輯覆蓋網絡進行優(yōu)化調整，使其路由信息更加優(yōu)化。
　　 2.P2P網絡上工作流運行質量監(jiān)督控制的優(yōu)化研究。
　　 P2P網絡中的工作流所處環(huán)境復雜、多變、異構，如何實時監(jiān)控工作流的運行情況，并根據節(jié)點上下文信息對其進行自適應的調度，將是保證P2P工作流穩(wěn)定運行的