基于分布式工作流的時間管理模型

1、一種Web服務(wù)關(guān)聯(lián)圖的構(gòu)造方法,覃事剛1，劉建勛2，秦祖澤1,,1.湖南電氣職業(yè)技術(shù)學(xué)院汽車工程系1, 湖南 湘潭 411101;2.湖南科技大學(xué) 知識處理與網(wǎng)絡(luò)化制造湖南省普通高等學(xué)校重點(diǎn)實驗室2，湖南 湘潭 411201,,提綱,問題提出,,,,問題提出,,,很多Web服務(wù)之間存在聯(lián)系,,問題提出,,,互聯(lián)網(wǎng)上的Web服務(wù),Web Services Implicit Relationship Graph, WSIRG,,挑戰(zhàn),如

2、何搜集互聯(lián)網(wǎng)上的Web服務(wù),如何挖掘出這些Web服務(wù)中存在的調(diào)用關(guān)系,(本論文解決的主要問題),,提綱,,論文思路,,一個Web服務(wù)是一個三元組ws(N,Im,Om)，其中N是服務(wù)名，Im是該服務(wù)的所有操作（Operation）的輸入消息（input message）集合{ imsg1,imsg2,…,imsgm }，Om是所有操作的輸出消息（output message）集合{ omsg1, omsg2,…,omsgm }。,給定一個

3、Web服務(wù)集U＝。其中W表示服務(wù)名稱的集合{ws1,ws2,ws3,ws4, ws5，……}，M表示W(wǎng)中的所有Web服務(wù)對應(yīng)的消息的集合{m1,m2,m3,m4,m5，……}，?為W中元素與M 中元素的對應(yīng)關(guān)系，若存在且 r=1，則m是ws的輸入消息；若存在邊且r=-1，則m是ws輸出（返回）消息；若不存在邊且r=0，則m不是ws的消息（message）。,,,論文思路,給定一個Web服務(wù)集U={ws1,ws2,ws3,ws4,ws5}

4、，該集合U對應(yīng)的消息集合MSGset= inMSGset? outMSGset ={m1,m2,m3,m4,m5}，其Web服務(wù)與消息之間的分配關(guān)系如圖所示,這樣做具有下優(yōu)點(diǎn)： i) 可以建立Web服務(wù)集與輸入/輸出消息集之間的二元關(guān)系, 用以揭示W(wǎng)eb服務(wù)間的潛在調(diào)用關(guān)系； ii) 可以可視化的方式直觀的表達(dá)這種調(diào)用關(guān)系。,將給定的Web服務(wù)集U=分解為兩個二元組：Ui=和Uo=。其中, Ui表示W(wǎng)eb服務(wù)

5、集與輸入消息之間的二元關(guān)系， Uo表示W(wǎng)eb服務(wù)集與輸出消息之間的二元關(guān)系；,,提綱,,相關(guān)算法——子項集F構(gòu)造算法及分析,子項:iP1({m1,m2,m3},{ws4})，iP2({m3,m5},{ws1})， iP3({m2,m4},{ws5})，iP4({m1,m3},{ws3,ws4})，iP5({m1,m2},{ws2,ws4})，iP6({m1},{ws2,ws3,ws4})，iP7({m2},{ws2,ws4,ws5})

6、，iP8({m3},{ws1,ws3,ws4}),在給定Web服務(wù)與消息二元關(guān)系上的子項集F的構(gòu)建,P1 ?P2 （公式9）=( A1, B1) ? (A2, B2)=( A1? A2, B1 ? B2)=P3 (A3, B3) (服務(wù)集擴(kuò)展運(yùn)算，其中 P3 ? U 且滿足f(A3)=B3) P1?P2

7、 （公式10）=( A1, B1) ? (A2, B2)=( A1,? A2, B1? B2)= P3 (A3, B3)(消息集擴(kuò)展運(yùn)算，其中P3 ? U且滿足k(B3)= A3),相關(guān)算法——子項集F構(gòu)造算法及分析,其基本思想是：在已存在的分組集合中，對所有的分組兩兩做服務(wù)對象集擴(kuò)展運(yùn)算或是消息集擴(kuò)展運(yùn)算，生成新的分組并添加到分組集合續(xù)繼參與相應(yīng)的擴(kuò)展運(yùn)算，直到所有分組均滿足f(A)=B的條件時結(jié)束。其中，初

8、始分組集={({w1},f({w2})),({w1},f({w2})),……, ({w|W|},f({w|W|}))}。,,,相關(guān)算法——子項集F構(gòu)造算法及分析,,在如圖5所示的函數(shù)ConstructF中，初始集合中的元素個數(shù)|?|=|W|=n，對任意一子項(Ai,Bi)，滿足|Ai|=1，|Bi|=|B|-1,即任意的兩個ei，其相對應(yīng)Bi集合中，有且只有|Bi|-1個消息元素msg? Bi相同，此時該算法的時間復(fù)雜度處于最壞情況。那

9、么，把某個 (A0,B0)且|A0|=1擴(kuò)展成(A’,B’)且|A’|=|A|-1需要執(zhí)行f(n-1)時間，依次對每個ei進(jìn)行擴(kuò)展的總的執(zhí)行的時間為f(n(n-1))時間，因此該算法的時間復(fù)雜度為：O(f(n(n-1))=O(n2)。,,相關(guān)算法——WSIRG的構(gòu)造算法及分析,,在這個算法中，函數(shù)執(zhí)行時間由三部分組成：構(gòu)造輸入子項集時間、構(gòu)造輸出子項集時間和 Fo×Fi所用時間。構(gòu)造輸入/輸出子項集時間已經(jīng)知道均為O(n2)，

10、而Fo×Fi執(zhí)行時間取決于|Fi|和|Fo|，在最壞的情況下，有|Fo|=| W*|和|Fi|=| W*|，假設(shè)| W |=n，| W*|=n(n+1)/2，則有Fo×Fi執(zhí)行時間= [n(n+1)/2]*[ n(n+1)/2]，因此該算法的時間復(fù)雜度為：O(n4)。,,提綱,試驗 (一),,可以看出， 在服務(wù)總數(shù)比較小的兩種邏輯結(jié)構(gòu)的構(gòu)建時間幾乎差不多，但隨著服務(wù)總數(shù)的增多，WSIRG的構(gòu)建時間明顯小于WSG的時間

11、,體現(xiàn)了新方法的優(yōu)勢。,試驗(二),基于WSG的服務(wù)發(fā)現(xiàn)方法和基于WSIRG的服務(wù)方法的服務(wù)發(fā)現(xiàn)時間的對比結(jié)果如圖所示?？煽闯觯?基于WSIRG的服務(wù)發(fā)現(xiàn)響應(yīng)時間相對較少，并隨著服務(wù)總數(shù)越來越多，服務(wù)發(fā)現(xiàn)的速度相對越來越快，優(yōu)勢明顯。,,結(jié)果分析,從以上的實驗結(jié)果可以看出，新方法存在以下優(yōu)勢：WSIRG與基于斷言關(guān)系的WSG的構(gòu)建方法相比，WSIRG優(yōu)勢比較明顯，這主要是在WSIRG的頂點(diǎn)不是單個的Web服務(wù)，而是同類的Web服務(wù)集，在

12、構(gòu)造WSIRG時，先對給定的Web服務(wù)集進(jìn)行分類劃分為不同的頂點(diǎn)集，然后再構(gòu)造成WSIRG，雖然，在理論上WSIRG的構(gòu)造算法在最壞情況下的復(fù)雜度為O(n4)，但在實際情況中幾乎不可能出現(xiàn)或是接近最壞情況，實驗證明亦是如此，因此，對給定的Web服務(wù)集，其WSIRG的頂點(diǎn)數(shù)遠(yuǎn)少于WSG的頂點(diǎn)數(shù)，所以，在服務(wù)發(fā)現(xiàn)響應(yīng)的時間上基于WSIRG的服務(wù)發(fā)現(xiàn)也占有很大的優(yōu)勢，隨著服務(wù)數(shù)量越多，優(yōu)勢越明顯。同時，也發(fā)現(xiàn)基于WSIRG的服務(wù)發(fā)現(xiàn)實驗過程中

13、，返回的結(jié)果比較多，包含的輸入/輸出消息等參數(shù)信息比較的明確，能很好的為服務(wù)組合提供數(shù)據(jù)參考。,,本文小結(jié),為了完成Web服務(wù)間自適應(yīng)調(diào)用關(guān)聯(lián)的問題，從服務(wù)間的邏輯調(diào)用關(guān)系出發(fā)，提出一種Web服務(wù)隱式邏輯關(guān)聯(lián)圖的構(gòu)造方法。在該方法中，Web服務(wù)被簡化為三元組，給定的Web服務(wù)集對應(yīng)的三元關(guān)系集可分解為兩個簡單的二元關(guān)系：輸出子項集和輸入子項集，服務(wù)鏈?zhǔn)禽敵鲎禹椉洼斎胱禹椉B接運(yùn)算的結(jié)果，構(gòu)成Web服務(wù)關(guān)聯(lián)圖的邊。本文并給出了子項集的構(gòu)