[發(fā)明專利]關(guān)鍵字驅(qū)動(dòng)的Web服務(wù)自動(dòng)組合方法

有效

• 申請(qǐng)?zhí)枺?/td>: 201910003351.0
• 申請(qǐng)日: 2019-01-03
• 公開（公告）號(hào): CN109688014B
• 公開（公告）日: 2022-04-08
• 發(fā)明（設(shè)計(jì)）人: 張蕾;俞東進(jìn);孫笑笑;侯文杰;應(yīng)鈺柯
• 申請(qǐng)（專利權(quán)）人: 杭州電子科技大學(xué)
• 主分類號(hào): H04L41/5054
• 分類號(hào): H04L41/5054;H04L67/02;H04L41/142
• 代理公司: 杭州君度專利代理事務(wù)所(特殊普通合伙) 33240
• 代理人: 朱月芬

1.關(guān)鍵字驅(qū)動(dòng)的Web服務(wù)自動(dòng)組合方法，其特征在于，包括如下步驟：

步驟(1).輸入Web服務(wù)庫(kù)W、語(yǔ)義本體Ont以及基于關(guān)鍵字的Web服務(wù)組合請(qǐng)求R＝{I_R，O_R，K_R，Q_R}；其中I_R表示用戶提供的初始輸入；O_R表示用戶期待的最終輸出；K_R＝{k₁，k₂，...，k_n}是用戶查詢的關(guān)鍵字的集合，n≥1，表示W(wǎng)eb服務(wù)組合方案中應(yīng)包含的關(guān)鍵服務(wù)功能；Web服務(wù)庫(kù)W中的每個(gè)Web服務(wù)都有相應(yīng)的關(guān)鍵字，關(guān)鍵字從服務(wù)描述文件中獲取，用以描述服務(wù)的功能信息；Q_R表示特定關(guān)鍵字之間的執(zhí)行順序；

步驟(2).根據(jù)I_R、O_R以及語(yǔ)義本體Ont對(duì)服務(wù)之間的輸入輸出參數(shù)進(jìn)行語(yǔ)義匹配，將離散的Web服務(wù)逐層連接，構(gòu)建服務(wù)初始匹配圖G_I＝(V，E)；其中V＝S∪P是節(jié)點(diǎn)的集合，S表示W(wǎng)eb服務(wù)節(jié)點(diǎn)集合，P表示數(shù)據(jù)傳輸過(guò)程中的I/O參數(shù)節(jié)點(diǎn)集合；S＝S_R∪{s_o，s_d}，其中S_R表示服務(wù)初始匹配圖中包含的Web服務(wù)節(jié)點(diǎn)；s_o、s_d是兩個(gè)特殊的虛擬服務(wù)節(jié)點(diǎn)，分別對(duì)應(yīng)于服務(wù)初始匹配圖中的頭尾節(jié)點(diǎn)；s_o不包含任何輸入，它的輸出是I_R；s_d不包含任何輸出，它的輸入是O_R；E＝SP∪PS是有向邊的集合，表示服務(wù)節(jié)點(diǎn)與I/O參數(shù)節(jié)點(diǎn)之間的依賴關(guān)系；

步驟(3).對(duì)服務(wù)初始匹配圖進(jìn)行預(yù)處理，預(yù)處理過(guò)程包括檢測(cè)并去除死鎖、合并等效橋接服務(wù)、去除冗余服務(wù)節(jié)點(diǎn)；

步驟(4).為服務(wù)初始匹配圖中的每個(gè)Web服務(wù)節(jié)點(diǎn)構(gòu)建索引L_NP以記錄每個(gè)服務(wù)的必經(jīng)前驅(qū)關(guān)鍵字節(jié)點(diǎn)集合；構(gòu)建索引M_ND以記錄每個(gè)服務(wù)節(jié)點(diǎn)與頭節(jié)點(diǎn)s_o之間的最短距離及最短路徑上包含的服務(wù)集合；

步驟(5).在服務(wù)初始匹配圖中運(yùn)行DP-DFS啟發(fā)式關(guān)鍵字搜索算法來(lái)生成最終的最優(yōu)服務(wù)組合G_F；

DP-DFS啟發(fā)式關(guān)鍵字搜索算法的具體執(zhí)行過(guò)程如下：

1)從初始匹配圖的尾節(jié)點(diǎn)sd開始，逆向進(jìn)行關(guān)鍵字搜索；將s_d的每個(gè)輸入?yún)?shù)添加到棧In_un中；初始化鍵值對(duì)集合K_selk，v，其中k表示某個(gè)待查詢的關(guān)鍵字，v表示關(guān)鍵字對(duì)應(yīng)的服務(wù)節(jié)點(diǎn)；初始化最優(yōu)服務(wù)組合G_F服務(wù)個(gè)數(shù)的上限值upper-bound為無(wú)窮大；初始化當(dāng)前部分解決方案G_P＝In_un，S_sel，K_sel，L_NS并將其添加到棧T_ps中，其中S_sel和K_sel分別表示部分解決方案中已包含的服務(wù)集合和關(guān)鍵字集合，L_NS是為部分解決方案中每一個(gè)尚未處理的服務(wù)節(jié)點(diǎn)構(gòu)建的索引，用來(lái)記錄服務(wù)節(jié)點(diǎn)的必經(jīng)后繼關(guān)鍵字節(jié)點(diǎn)，其中尚未處理的服務(wù)節(jié)點(diǎn)表示仍含有未匹配輸入的服務(wù)；

2)從棧T_ps中彈出一個(gè)待擴(kuò)展的部分解決方案進(jìn)行如下判斷：首先，根據(jù)以下預(yù)測(cè)函數(shù)計(jì)算其最小服務(wù)個(gè)數(shù)值f(G_P)：

f(G_P)＝g(G_P)+h(G_P)

其中，g(G_P)表示部分解決方案中已包含的服務(wù)節(jié)點(diǎn)個(gè)數(shù)；h(G_P)表示從當(dāng)前部分解決方案擴(kuò)展到完整解決方案的啟發(fā)式預(yù)估最小成本，最小成本為包含的最小節(jié)點(diǎn)個(gè)數(shù)；若f(G_P)大于upper-bound，則返回步驟2)；若當(dāng)前部分解決方案沒(méi)有未解決的輸入?yún)?shù)且它包含了所有查詢關(guān)鍵字，則將其作為當(dāng)前的最優(yōu)服務(wù)組合方案G_F并更新upper-bound值為該組合方案中包含的服務(wù)個(gè)數(shù)，返回步驟2)；

3)從In_un中取出一個(gè)未解決的輸入?yún)?shù)i，并獲取與i連接的所有前驅(qū)服務(wù)節(jié)點(diǎn)作為它的候選服務(wù)節(jié)點(diǎn)集合CANDIDATE(i)；

4)對(duì)i的每一個(gè)候選服務(wù)節(jié)點(diǎn)進(jìn)行如下操作：若該候選服務(wù)節(jié)點(diǎn)的前驅(qū)必經(jīng)關(guān)鍵字已包含在當(dāng)前部分解決方案中，或者該候選服務(wù)節(jié)點(diǎn)的前驅(qū)必經(jīng)關(guān)鍵字與部分解決方案中已有關(guān)鍵字之間不符合時(shí)序要求，或者選擇該候選服務(wù)節(jié)點(diǎn)會(huì)造成循環(huán)，則從CANDIDATE(i)中移除該服務(wù)節(jié)點(diǎn)；所述的候選服務(wù)節(jié)點(diǎn)的前驅(qū)必經(jīng)關(guān)鍵字由索引L_NP得出；

5)在CANDIDATE(i)剩余的服務(wù)節(jié)點(diǎn)中選擇與頭節(jié)點(diǎn)s_o之間的最短距離最大的服務(wù)節(jié)點(diǎn)s進(jìn)行如下操作：生成當(dāng)前部分解決方案的副本并將該候選服務(wù)節(jié)點(diǎn)添加進(jìn)來(lái)；更新相關(guān)變量In_un、S_sel、K_sel以及L_NS；將新生成的部分解決方案壓入棧T_ps中；

6)重復(fù)步驟5)，直到CANDIDATE(i)中不存在未被處理的服務(wù)節(jié)點(diǎn)；

7)重復(fù)步驟2)～步驟6)，直到T_ps中不包含任何待擴(kuò)展的部分解決方案；

8)輸出此時(shí)的最優(yōu)服務(wù)組合方案G_F。