基于P2P網(wǎng)絡(luò)節(jié)點(diǎn)上下文的任務(wù)分解和調(diào)度方法研究.pdf

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

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

3、。
　　 P2P技術(shù)實(shí)現(xiàn)了計算模式從主-從式向?qū)Φ仁降霓D(zhuǎn)變，網(wǎng)絡(luò)應(yīng)用的核心從中心服務(wù)器向邊緣計算設(shè)備擴(kuò)散，有效地解決了單點(diǎn)失效和負(fù)載均衡問題，大幅提升了網(wǎng)絡(luò)的整體計算能力。充分利用P2P網(wǎng)絡(luò)中的計算資源和計算能力，將工作流中那些運(yùn)算工作量大的活動予以分解，并將其調(diào)度到優(yōu)選節(jié)點(diǎn)上進(jìn)行分布式運(yùn)算，將會大幅提升可用計算資源的利用效率和工作流的整體執(zhí)行效率。因此，P2P網(wǎng)絡(luò)環(huán)境中的任務(wù)分解和調(diào)度(TaskPartitioningandS

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

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

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

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

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

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

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

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

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

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

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

15、 P2P網(wǎng)絡(luò)是在IP網(wǎng)絡(luò)或者其他物理網(wǎng)絡(luò)上的邏輯覆蓋網(wǎng)，其拓?fù)渑c物理網(wǎng)絡(luò)的實(shí)際拓?fù)洳⒉煌耆ヅ?，造成P2P網(wǎng)絡(luò)的路由實(shí)際上并不一定是最優(yōu)的路由，可以通過上下文對邏輯覆蓋網(wǎng)絡(luò)進(jìn)行優(yōu)化調(diào)整，使其路由信息更加優(yōu)化。
　　 2.P2P網(wǎng)絡(luò)上工作流運(yùn)行質(zhì)量監(jiān)督控制的優(yōu)化研究。
　　 P2P網(wǎng)絡(luò)中的工作流所處環(huán)境復(fù)雜、多變、異構(gòu)，如何實(shí)時監(jiān)控工作流的運(yùn)行情況，并根據(jù)節(jié)點(diǎn)上下文信息對其進(jìn)行自適應(yīng)的調(diào)度，將是保證P2P工作流穩(wěn)定運(yùn)行的