服務(wù)流程檢索技術(shù)研究

張 林，吳曉銘，王凌陽(yáng)

ZHANG Lin1,WU Xiaoming2,WANG Lingyang2

1.武漢大學(xué) 軟件工程國(guó)家重點(diǎn)實(shí)驗(yàn)室，武漢430072

2.武漢大學(xué) 計(jì)算機(jī)學(xué)院，武漢430072

1.State Key Lab of Software Engineering,Wuhan University,Wuhan 430072,China

2.College of Computer,Wuhan University,Wuhan 430072,China

1 引言

在工作流和服務(wù)計(jì)算領(lǐng)域，流程片段的重用研究具有很大的研究?jī)r(jià)值。許多研究關(guān)注于如何分割和描述流程片段。例如，Vanhatalo[1]提出一種將原流程片段分割成更小的單入單出（Single-Entry-Single-Exit，SESE）片段的模型。在文獻(xiàn)[2]中，為更好地描述和提取片段信息，將流程片段描述成不同的零碎知識(shí)。Schumm[3]詳細(xì)討論了使用流程片段庫(kù)和集成應(yīng)用的潛在影響。此外，一個(gè)全面的框架[4]關(guān)注于如何提取動(dòng)態(tài)、漸進(jìn)、上下文感知適應(yīng)的流程片段。但是這些方法沒(méi)有考慮提取流程片段的潛在信息，特別是如何提取一個(gè)超出人工提取能力的大流程片段信息。

事實(shí)上，任意粒度的服務(wù)流程片段[5-7]都有被重用的潛力，尤其是那些已被手動(dòng)編輯，且能夠直接運(yùn)行的流程片段，其作用甚至高于原子服務(wù)。例如，一個(gè)僅包含順序關(guān)系的簡(jiǎn)單服務(wù)流程S1 →S2 →S3，不僅能夠重用片 段S1 →S2 和S2 →S3，而且可以重用S1 →S2 →S3整個(gè)片段。

服務(wù)流程片段重用的目的是進(jìn)一步利用現(xiàn)有的流程片段，即盡可能挖掘出更多的可重用子流程片段，從而滿足新的服務(wù)組合需求。此外，服務(wù)重用并未考慮重復(fù)使用的對(duì)象是否為原子或組合服務(wù)。例如，圖1 展示了一個(gè)與旅游相關(guān)的服務(wù)流程實(shí)例，它包含5 個(gè)原子服務(wù)。若一個(gè)客戶旅行乘坐火車改乘船，利用現(xiàn)有技術(shù)，開發(fā)人員不得不手動(dòng)分析和重建全過(guò)程。盡管在上述組合服務(wù)中可以通過(guò)一個(gè)輪船訂票服務(wù)替換火車訂票服務(wù)，達(dá)到重用一些服務(wù)片段的目的，但是如果服務(wù)流程庫(kù)非常龐大，開發(fā)者很難找出哪些片段可以被重用。服務(wù)庫(kù)樣例如表1 所示。

圖1 一個(gè)服務(wù)流程樣例

表1 服務(wù)庫(kù)樣例

在不同的需求方面，為有效發(fā)現(xiàn)和重用服務(wù)流程片段，本文提出了一種新的索引機(jī)制（CLI）。由于其他流程關(guān)系可以被轉(zhuǎn)化為線性關(guān)系流程，所以本文中的流程都是具有線性關(guān)系的流程。首先，服務(wù)接口描述和服務(wù)之間依賴關(guān)系轉(zhuǎn)換成二進(jìn)制編碼的標(biāo)簽，圖2 給出對(duì)應(yīng)于圖1 轉(zhuǎn)換后的標(biāo)簽圖。在標(biāo)簽圖中所有頂點(diǎn)和邊組成服務(wù)標(biāo)簽樹（Service Label-tree，SL-tree），即每個(gè)流程對(duì)應(yīng)于一棵SL-tree。然后，在統(tǒng)一實(shí)現(xiàn)原子服務(wù)和組合服務(wù)的檢索時(shí)，本文提出了一種新穎的數(shù)據(jù)結(jié)構(gòu)，即服務(wù)標(biāo)簽合并樹（SLM-tree）。這樣，搜索的服務(wù)將不僅僅局限于原子服務(wù)。通過(guò)快速計(jì)算將絕對(duì)不相關(guān)的流程片段過(guò)濾掉，剩下可能相關(guān)的流程片段，之后采用傳統(tǒng)考慮服務(wù)依賴性的方法進(jìn)行匹配篩選。最后，擇優(yōu)選取檢索到的流程片段。

圖2 轉(zhuǎn)換成標(biāo)簽圖

2 CLI機(jī)制

本文僅關(guān)注于不同網(wǎng)絡(luò)服務(wù)的連接，而對(duì)于初始化服務(wù)流程并不重要的控制結(jié)構(gòu)如if 與while 等不會(huì)過(guò)多關(guān)注。因此，本文需要犧牲一定的準(zhǔn)確性來(lái)大幅提高服務(wù)流程片段的檢索效率。

在只考慮順序序列的情況下，流程可簡(jiǎn)化為一個(gè)有向圖，稱為Web 服務(wù)圖（Web Service-graph，WS-graph），其中每個(gè)頂點(diǎn)和每條邊分別對(duì)應(yīng)于Web 服務(wù)和連接服務(wù)之間的依賴關(guān)系。服務(wù)流程片段查詢類似于搜索限制寬泛的子圖匹配問(wèn)題。因此，服務(wù)流程片段查詢（SFF-query）只關(guān)注于服務(wù)的輸入和輸出參數(shù)以及它們之間的依賴關(guān)系。

在WS-graph中，某個(gè)流程片段P可以用Gp=(W,E)表示，其中W={w1,w2,…,wm}是頂點(diǎn)集合，E={＜wi,wj＞}={＜wi.out→wj.in＞}(i，j∈m)是邊集合。每個(gè)頂點(diǎn)表示一個(gè)服務(wù)，每條邊代表wi和wj之間依賴關(guān)系。一個(gè)SFF-query 可以用Gq=(W′，E′)表示，如果查詢成功，則要求對(duì)Gq中任意一條邊＜wx′，wy′＞，wx′的輸入和wy′的輸出必須分別包含于Gp中服務(wù)集合的輸入集和輸出集內(nèi)。

2.1 WS-graph 標(biāo)簽

為便于理解，假設(shè)每個(gè)Web服務(wù)只有一個(gè)操作。WSgraph 標(biāo)簽包括頂點(diǎn)標(biāo)簽vLab(w)和邊標(biāo)簽eLab(wiwj)，其中每個(gè)標(biāo)簽都對(duì)應(yīng)于一個(gè)二進(jìn)制串。Web 服務(wù)可以描述為wi=＜wi.in，wi.out＞，其中wi.in和wi.out分別表示服務(wù)的輸入和輸出參數(shù)集。由于可以通過(guò)本體映射、近義詞替換等將服務(wù)語(yǔ)義概念統(tǒng)一，之后采用合適的哈希函數(shù)，例如DJBHash 和PJWHash，可以將服務(wù)wi編碼成統(tǒng)一格式的二進(jìn)制位串。

給定服務(wù)w包含輸入?yún)?shù)集w.in={in1，in2，…，inp}和輸出參數(shù)集w.out={out1，out2，…，outq}。

vLab(w)定義如下：

eLab(wiwj)定義如下：

其中“|”表示或操作，“*”表示連接操作。對(duì)于任何服務(wù)的連接，連接服務(wù)的輸入?yún)?shù)必須完全滿足要求，但一些連接服務(wù)的輸出參數(shù)可以不使用。因此，在公式（2）中有q′=p≤q。

圖3 和圖4 分別顯示如何分配標(biāo)簽給圖1 中天氣服務(wù)以及旅行計(jì)劃服務(wù)和旅行估價(jià)服務(wù)之間的關(guān)系。

圖3 服務(wù)標(biāo)簽實(shí)例

2.2 服務(wù)標(biāo)簽合并樹

通過(guò)編碼Web 服務(wù)和不同服務(wù)之間的依賴關(guān)系，WS-graph 將被轉(zhuǎn)換成一個(gè)標(biāo)簽圖，稱為流程標(biāo)簽圖（Flow Label-graph，F(xiàn)L-graph）。本節(jié)將討論如何將這些標(biāo)簽組織成CLI。CLI 將提供更加便捷、高效的服務(wù)流程片段查詢，其過(guò)程僅僅使用有限的位運(yùn)算組織這些標(biāo)簽。

圖4 服務(wù)連接標(biāo)簽實(shí)例

對(duì)于服務(wù)流程片段查詢（SFF-query），查詢條件可以轉(zhuǎn)換成一個(gè)查詢標(biāo)簽圖（Query Label-graph，QL-graph），轉(zhuǎn)換過(guò)程類似于對(duì)WS-graph 轉(zhuǎn)化為FL-graph。因此要解決的本質(zhì)問(wèn)題是如何在FL-graph 中有效找到匹配的QL-graph。一個(gè)簡(jiǎn)單的算法如下：

步驟1對(duì)每個(gè)vi∈V（QL-graph），找到點(diǎn)集Ri={ui1，ui2，…，uin}滿足條件vi&uij=vi，uij∈V（FL-graph）以及uij∈Ri。其中“&”是二進(jìn)制與操作，V(*)是頂點(diǎn)集合。

步驟2通過(guò)依賴關(guān)系進(jìn)一步驗(yàn)證這些點(diǎn)集，最終選取一些相匹配的QL-graph。

在本文中，S-tree[8]是一種提供包含檢索功能的高度平衡樹。在S-tree 中，每一個(gè)中間結(jié)點(diǎn)是通過(guò)位與運(yùn)算疊加所有子標(biāo)簽而組成。因此，利用一棵S-tree 可以有效地完成第一步。然而，S-tree 不能支持累加服務(wù)之間的依賴關(guān)系。因此，本文提出一種新的索引結(jié)構(gòu)即服務(wù)標(biāo)簽樹（Service Label-tree，SL-tree），支持任意粒度的服務(wù)流程片段查詢。如圖5 所示，該圖對(duì)應(yīng)于圖1 例子的一棵SL-tree。

圖5 圖1 轉(zhuǎn)化為SL-tree

盡管可以通過(guò)SL-tree 搜索任意粒度的服務(wù)流程片段，但是仍然需要檢索大量SL-tree。因此，將所有SL-tree的根結(jié)點(diǎn)再通過(guò)一棵S-tree 進(jìn)行組織，以此進(jìn)一步提高搜索流程片段的效率，這棵S-tree 定義為服務(wù)標(biāo)簽合并樹（Service Label Merge-tree，SLM-tree）。此外，SLMtree 的葉結(jié)點(diǎn)可能是一個(gè)原子服務(wù)，但是組合服務(wù)必須有自邊，由此通過(guò)判定SLM-tree 中葉結(jié)點(diǎn)是否存在自邊，區(qū)分對(duì)待原子服務(wù)和組合服務(wù)的搜索。所以CLI 可以統(tǒng)一檢索這兩種類型服務(wù)。

3 檢索過(guò)程

本章將討論如何通過(guò)SLM-tree進(jìn)行服務(wù)片段查詢。具體策略是自頂向下通過(guò)SLM-tree 在一個(gè)龐大的服務(wù)流程存儲(chǔ)庫(kù)中過(guò)濾尋找一些候選集，并且按照一定策略從中擇優(yōu)選取。

3.1 片段檢索原理

在2.2節(jié)介紹過(guò)，一個(gè)SFF-query可以轉(zhuǎn)換為QL-graph，而SFF-query 可分為嚴(yán)格或非嚴(yán)格檢索。對(duì)于嚴(yán)格SFFquery，結(jié)果必須完全滿足查詢條件，它們可以直接被重復(fù)利用。與此相反，在非嚴(yán)格SFF-query 中，允許結(jié)果部分滿足查詢條件。由于篇幅所限，本文只介紹嚴(yán)格的SFF-query。

定義3.1對(duì)于一個(gè)FL-graphG*和一個(gè)QL-graphQ*，其 中G*，Q* 分 別 包 含Web 服 務(wù) 集 合W={w1，w2，…，wm}和U={u1，u2，…，un}，當(dāng)且僅當(dāng)以下條件成立時(shí)G*是滿足嚴(yán)格查詢Q*：

條件1對(duì)于任何ui∈U，存在wj∈W，使得vLab(wj).in&vLab(ui).in=vLab(wj).in并且vLab(wj).out&vLab(ui).out=vLab(wj).out。這意味著所有查詢條件的Web 服務(wù)是被包含在流程中。

條件2對(duì)Q*中的任何uiuj，在G*中，存在wiwj使得eLab(uiuj)&eLab(wiwj)=eLab(uiuj)，其中wiwj可能是一條被許多葉結(jié)點(diǎn)合成的邊。

利用SLM-tree 的特性，反復(fù)通過(guò)定義3.1 從上到下實(shí)現(xiàn)過(guò)濾操作。因?yàn)闃錉罱Y(jié)構(gòu)的每個(gè)分支都含有大量流程或原子服務(wù)，所以每一步操作都有可能過(guò)濾大量不相關(guān)結(jié)果。

3.2 使用SLM-tree

基于SLM-tree 創(chuàng)建的索引能夠統(tǒng)一實(shí)現(xiàn)原子和組合服務(wù)兩種查詢。事實(shí)上，原子服務(wù)查詢可以看成是僅包含一個(gè)服務(wù)的特殊SFF-query。因此，下文只詳細(xì)描述SFF-query 的步驟。

SFF-query 主要包含兩個(gè)步驟。第一步，查詢輸入標(biāo)簽和輸出標(biāo)簽分別與SLM-tree 的根結(jié)點(diǎn)標(biāo)簽做位與操作，判斷是否匹配。如果匹配不成功，快速排除即可。如果查詢條件與根結(jié)點(diǎn)或任何內(nèi)部結(jié)點(diǎn)匹配，由于在SLM-tree 中位或操作的模糊積累并不能表明查詢流程片段存在，所以只獲得流程片段的候選集，即許多SL-tree 根結(jié)點(diǎn)組成的集合。

在上一步的匹配過(guò)程中，為了快速篩選最不相關(guān)的流程片段，只考慮頂點(diǎn)的存在，而忽略頂點(diǎn)之間的依賴關(guān)系。在第二步中，將進(jìn)一步利用關(guān)系標(biāo)簽找到包含查詢流程片段的流程片段。如果第一步產(chǎn)生的候選集中某個(gè)流程片段與查詢條件中的頂點(diǎn)標(biāo)簽和邊標(biāo)簽任何一項(xiàng)不匹配，該流程片段將會(huì)被排除。

3.3 選取SFF

服務(wù)質(zhì)量（Quality of Service，QoS）代表Web 服務(wù)的許多非功能特性，例如響應(yīng)時(shí)間，吞吐量和可達(dá)性等。由于每一個(gè)服務(wù)質(zhì)量特性不盡相同，根據(jù)文獻(xiàn)[9]需要將它們歸一化到區(qū)間[0，1]，具體公式如下：

其中公式（3）表示正向?qū)傩詺w一公式，公式（4）表示負(fù)向?qū)傩詺w一公式，vi是第i維QoS 屬性值，v′i是歸一化后的結(jié)果。

現(xiàn)假設(shè)某流程片段P={s1，s2，…，sn}，該流程片段總體服務(wù)質(zhì)量為QoSp。針對(duì)不同QoS 屬性，QoSp的每一維屬性累加方法不相同，具體策略如表2。

表2 累加方法

為便于理解，現(xiàn)考慮二維屬性，例如響應(yīng)時(shí)間和價(jià)格。假設(shè)經(jīng)過(guò)索引機(jī)制CLI檢索出前7 個(gè)候選服務(wù)流程片段，如表3 所示。

表3 候選流程片段樣例

根據(jù)文獻(xiàn)[10-12]提出的紙帶模型，第一步需按照Skyline 點(diǎn)集合在Skyline 空間坐標(biāo)系中的位置將整個(gè)Skyline 空間坐標(biāo)系分成三個(gè)區(qū)域，分別為支配區(qū)域A，盲點(diǎn)區(qū)域B和被支配區(qū)域C。三個(gè)區(qū)域劃分事例如圖6所示，其中有7個(gè)服務(wù)片段被按照二維QoS映射至Skyline坐標(biāo)系中，Skyline集合為{SFF-3，SFF-4，SFF-6，SFF-7}。

圖6 基于紙帶的Skyline坐標(biāo)實(shí)例

（1）支配區(qū)域A。此區(qū)域位于Skyline 集合各點(diǎn)左連線的下部，包括連線部分，但不包括Skyline 上的各個(gè)服務(wù)片段點(diǎn)，為圖6 所示的淺藍(lán)色標(biāo)有區(qū)域A的部分。在算法運(yùn)行過(guò)程中，新服務(wù)片段按QoS 映射至此坐標(biāo)系時(shí)，若落到區(qū)域A，則新服務(wù)片段必然會(huì)支配已經(jīng)生成的Skyline 集合中某些數(shù)據(jù)點(diǎn)，亦即某些服務(wù)片段。此時(shí)在將新服務(wù)片段映射到坐標(biāo)系中的同時(shí)，需要從原Skyline 集合中刪除被新進(jìn)服務(wù)片段支配的服務(wù)片段。若無(wú)服務(wù)片段點(diǎn)位于支配區(qū)域A，則判斷為支配區(qū)域A的點(diǎn)必然為增加服務(wù)片段操作。

（2）盲點(diǎn)區(qū)域B。此區(qū)域位于Skyline 集合各點(diǎn)左連線的上部，右連線的下部，不包含左右連線，但包括Skyline 集合各點(diǎn)，為圖6 中標(biāo)有區(qū)域B的深藍(lán)色部分。因其不歸原Skyline 各點(diǎn)支配，也不支配原Skyline 中的元素，所以稱為盲點(diǎn)區(qū)域。若新進(jìn)服務(wù)片段與原Skyline無(wú)相互支配關(guān)系，則新進(jìn)服務(wù)片段直接加入到Skyline集合。如果為刪除服務(wù)片段操作，則刪除的服務(wù)片段必為Skyline點(diǎn)。

（3）被支配區(qū)域C。此區(qū)域位于Skyline 集合各點(diǎn)右連線的上部，包括連線上的各點(diǎn)，不包括Skyline 集合各點(diǎn)，為圖6 中淺黃色部分標(biāo)有C區(qū)域標(biāo)記的部分。此區(qū)域的各點(diǎn)被Skyline 支配，所以稱為被支配區(qū)域。如新進(jìn)服務(wù)片段位于此區(qū)域，并不影響原Skyline 各點(diǎn)，可直接將服務(wù)片段隱身進(jìn)空間坐標(biāo)系即可；若欲刪除部分位于此區(qū)域，亦不影響原Skyline，可直接將服務(wù)片段從空間坐標(biāo)系刪除即可。

將Skyline 集合中按單屬性進(jìn)行排序組織成屬性紙帶，在此以圖6 Skyline 空間坐標(biāo)系為例，建立此集合的二維紙帶模型，所需2 條紙帶分別為響應(yīng)時(shí)間紙帶和價(jià)格紙帶。其中響應(yīng)時(shí)間紙帶對(duì)應(yīng)坐標(biāo)系的豎軸表示服務(wù)片段的響應(yīng)時(shí)間，按從小到大排序；價(jià)格紙帶對(duì)應(yīng)坐標(biāo)系的橫軸表示服務(wù)片段的價(jià)格，按從大到小排序。圖6 Skyline 空間坐標(biāo)系中Skyline 集合形成的二維紙帶模型如圖7 所示。

圖7 紙帶模型實(shí)例

計(jì)算新增服務(wù)片段或欲刪除服務(wù)片段在所有紙帶中的位置，規(guī)則如下：

規(guī)則1若變動(dòng)服務(wù)片段SFF 在某一紙帶P的K編號(hào)服務(wù)片段和K+1 編號(hào)服務(wù)片段之間，規(guī)則定義SFF在紙帶P上的編號(hào)為K+0.5。

規(guī)則2若變動(dòng)服務(wù)片段SFF 在某一紙帶P有與其相等的編號(hào)K，此時(shí)編號(hào)為K的服務(wù)片段與服務(wù)片段SFF 在此維度上QoS 相等。規(guī)則定義SFF 在此紙帶P上的編號(hào)為K。

規(guī)則3若變動(dòng)服務(wù)片段SFF 在某一紙帶P在第一個(gè)服務(wù)片段之前，規(guī)則定義SFF 在此紙帶P上的編號(hào)為0.5。若在最后一個(gè)服務(wù)片段之后，算法定義SFF 在此紙帶P上的編號(hào)為N+0.5，其中N為此紙帶上服務(wù)片段的個(gè)數(shù)。

依據(jù)上述規(guī)則，假設(shè)現(xiàn)加入SFF-8 響應(yīng)時(shí)間屬性與SFF-7 相等，其價(jià)格屬性與SFF-4 相等。由于SFF-7 在響應(yīng)時(shí)間紙帶上的編號(hào)為1，根據(jù)規(guī)則2 得SFF-8 在響應(yīng)時(shí)間紙帶上的編號(hào)為1，同理可知在價(jià)格紙帶上SFF-8 的編號(hào)為3。

落入A支配區(qū)域的變化服務(wù)片段SFF 必然會(huì)支配某個(gè)或者某些原Skyline 集合中的服務(wù)片段，根據(jù)上示紙帶模型可知，如果SFF 支配原Skyline 集合中的SFF-X服務(wù)片段，可知在響應(yīng)時(shí)間和價(jià)格紙帶上的編號(hào)的值不大于SFF-X 服務(wù)片段在對(duì)應(yīng)紙帶上的值，并且在某一維度SFF 的編號(hào)小于SFF-X 的編號(hào)。從上述紙帶中可知在響應(yīng)時(shí)間紙帶上比SFF-8 差或相等集合為{SFF-3，SFF-4，SFF-6，SFF-7}，在價(jià)格紙帶上比SFF-8 差或相等的集合為{SFF-4，SFF-6，SFF-7}。當(dāng)兩個(gè)集合有交集時(shí)可知原Skyline中有被SFF-8支配的服務(wù)片段，所以SFF-8服務(wù)片段落至A支配區(qū)域，同理，可推出落入B盲點(diǎn)區(qū)域或者C被支配區(qū)域編碼的關(guān)系。

4 實(shí)驗(yàn)分析

本文中的索引CLI 和SFF-query 算法均采用C++實(shí)現(xiàn)。設(shè)計(jì)并開展了一系列評(píng)估準(zhǔn)確性和效率的實(shí)驗(yàn)，實(shí)驗(yàn)使用的個(gè)人電腦配置是CPU：2.8 GHz和內(nèi)存：4 GB。

通過(guò)CTG[13]生成了一個(gè)包含大約20 萬(wàn)個(gè)流程片段和1.05 億個(gè)原子服務(wù)的服務(wù)庫(kù)，每個(gè)流程片段包含100～300 個(gè)不等的隨機(jī)原子服務(wù)。此外，每個(gè)服務(wù)包含5～10個(gè)輸入或輸出參數(shù)。

CLI 的性能可能與許多參數(shù)有關(guān)，如在流程庫(kù)中流程的數(shù)量（Amount Process，AP）、原子服務(wù)的平均數(shù)目（Average Atomic Service，AAS）、每個(gè)流程之間服務(wù)的依賴關(guān)系（Process Relation，PR）、抽象服務(wù)平均數(shù)量（Average abstract Service，AS）、每次查詢條件依賴關(guān)系（Query Relation，QR）、標(biāo)簽編碼的長(zhǎng)度（Length Label，LL）和SLM-tree 中每個(gè)結(jié)點(diǎn)的孩子結(jié)點(diǎn)數(shù)量范圍（Number range of Children，NC）NC=[r1，r2]。r1 是SLM-tree 內(nèi)任意結(jié)點(diǎn)的孩子最小數(shù)目，r2 是任意結(jié)點(diǎn)的孩子最大數(shù)目。在本章中，通過(guò)改變上面不同參數(shù)進(jìn)行了一系列評(píng)估性能的實(shí)驗(yàn)，所有實(shí)驗(yàn)重復(fù)5 次，每一種情況取平均值。LL 是CLI 最重要的參數(shù)指標(biāo)之一，圖8 和圖9 分別顯示通過(guò)采用不同的LL 對(duì)效率和準(zhǔn)確性的影響，其中AP=500 KB，AAS=100 和NC=[8，16]。

圖8 不同LL 效率比較

圖9 不同LL 準(zhǔn)確性比較

如圖8 所示，查詢效率明顯隨LL的增加而提高，因?yàn)楦邔覵LM-tree 將明顯不相干的流程片段較早過(guò)濾掉，但是更大的LL消耗更多內(nèi)存，所以需要找到效率和內(nèi)存成本之間的平衡點(diǎn)。此外，當(dāng)LL＞240 時(shí)，所有曲線顯示突然發(fā)生強(qiáng)烈變化，現(xiàn)象出現(xiàn)原因是當(dāng)CLI 的規(guī)模大于可用內(nèi)存時(shí)，額外的I/O 操作降低了效率。

從圖9 可以看出，準(zhǔn)確性隨著標(biāo)簽長(zhǎng)度增加而提高。就像其他標(biāo)簽樹，如果LL很短，將節(jié)省大量?jī)?nèi)存空間，裝載更多的索引結(jié)點(diǎn)到內(nèi)存中。但是，同時(shí)也導(dǎo)致更多的服務(wù)或關(guān)系被映射到相同的標(biāo)簽中，短小的LL將導(dǎo)致標(biāo)簽重復(fù)，造成精度降低。此外，更復(fù)雜的查詢條件依賴于較長(zhǎng)的LL，因?yàn)樾枰嗟谋忍匚淮_保查詢標(biāo)簽的真實(shí)性?？偨Y(jié)圖8 和圖9 中實(shí)驗(yàn)結(jié)果，最終選擇LL=218，可以支持非常復(fù)雜的查詢，并且將被用于后續(xù)的實(shí)驗(yàn)中。

NC=[r1，r2]直接影響SLM-tree 深度，是另一個(gè)重要的參數(shù)指標(biāo)。較大的NC將獲得更高的查詢效率，然而這樣會(huì)導(dǎo)致大多數(shù)無(wú)用的結(jié)果不能被SLM-tree 的高層過(guò)濾掉。所以，有必要確定r1 和r2 的合適值以及它們之間的比率。如圖10 所示，當(dāng)AP=500 KB 和AAS=100 時(shí)，對(duì)所有AS來(lái)說(shuō)其效率更穩(wěn)定的比率為1∶2。此外，選擇圖10 中穩(wěn)定性最高的3 個(gè)不同NC的曲線，分析它們對(duì)于不同規(guī)模的流程不同表現(xiàn)。圖11 展示了它們效率與靈敏度之間的關(guān)系。雖然當(dāng)AP＜300 KB 時(shí)，r1=8 和r2=16 的曲線不是最高效率的曲線，但對(duì)更大規(guī)模流程顯示出更好的優(yōu)越性。最終，本文確定NC=[8，16]。

圖10 不同NC 穩(wěn)定性比較

圖11 不同NC 效率比較

5 結(jié)束語(yǔ)

在傳統(tǒng)服務(wù)計(jì)算研究領(lǐng)域[14-15]中，很少考慮服務(wù)流程的重用。但是，能夠最大努力地重用流程片段，不僅能夠提高服務(wù)組合的效率，而且對(duì)企業(yè)也可以節(jié)省人力和物力成本。本文提出了一種可變索引機(jī)制CLI，它能夠檢索任意粒度的流程片段，并達(dá)到重用的目的以滿足更復(fù)雜的業(yè)務(wù)需求。結(jié)合數(shù)字標(biāo)簽和編碼匹配技術(shù)，CLI 可以同時(shí)實(shí)現(xiàn)原子服務(wù)及組合服務(wù)的檢索。最后通過(guò)一系列的實(shí)驗(yàn)驗(yàn)證了方法的可行性和有效性。今后工作主要目標(biāo)是針對(duì)非嚴(yán)格SFF-query，進(jìn)一步提高流程片段的利用率。

[1] Vanhatalo J，V?lzer H，Leymann F.Faster and more focused control-flow analysis for business process models through sese decomposition[M].Berlin Heidelberg：Springer，2007.

[2] Eberle H，Unger T，Leymann F.Process fragments[M]//On the Move to Meaningful Internet Systems：OTM 2009.Berlin Heidelberg：Springer，2009：398-405.

[3] Schumm D，Karastoyanova D，Kopp O，et al.Process fragment libraries for easier and faster development of processbased applications[J].Journal of Systems Integration，2011，2（1）：39-55.

[4] Bucchiarone A，Marconi A，Pistore M，et al.Dynamic adaptation of fragment-based and context-aware business processes[C]//2012 IEEE 19th International Conference on Web Services（ICWS），2012：33-41.

[5] Granell C，Gould M，Gr?nmo R，et al.Improving reuse of web service compositions[M]//E-Commerce and Web Technologies.Berlin Heidelberg：Springer，2005：358-367.

[6] Sonntag M，Karastoyanova D，Leymann F.The missing features of workflow systems for scientific computations[C]//Software Engineering（Workshops），2010：209-216.

[7] Granell C，Ramos J F.An object-oriented approach to GI web service composition[C]//15th International Workshop on Database and Expert Systems Applications，2004：835-839.

[8] Deppisch，Uwe.S-tree：a dynamic balanced feature index for offline retrieval[C]//SIGIR，1986.

[9] Alrifai M，Skoutas D，Risse T.Selecting skyline services for QoS-based web service composition[C]//Proceedings of the 19th International Conference on World Wide Web，2010：11-20.

[10] 胡建強(qiáng)，李涓子，廖桂平.一種基于多維服務(wù)質(zhì)量的局部最優(yōu)服務(wù)選擇模型[J].計(jì)算機(jī)學(xué)報(bào)，2010，33（3）：526-534.

[11] Ma Y，Chen L，Hui J，et al.Cbbcm：clustering based automatic service composition[C]//2011 IEEE International Conference on Services Computing（SCC），2011：354-361.

[12] Kolb J，Kammerer K，Reichert M.Updatable process views for user-centered adaption of large process models[M]//Service-Oriented Computing.Berlin Heidelberg：Springer，2012：484-498.

[13] Zheng Z，Zhang Y，Lyu M R.Distributed qos evaluation for real-world web services[C]//2010 IEEE International Conference on Web Services（ICWS），2010：83-90.

[14] Yu T，Zhang Y，Lin K J.Efficient algorithms for Web services selection with end-to-end QoS constraints[J].ACM Transactions on the Web（TWEB），2007，1（1）.

[15] Yang J，Papazoglou M P.Service components for managing the life-cycle of service compositions[J].Information Systems，2004，29（2）：97-125.