[發明專利]關鍵字驅動的Web服務自動組合方法

有效

• 申請號: 201910003351.0
• 申請日: 2019-01-03
• 公開（公告）號: CN109688014B
• 公開（公告）日: 2022-04-08
• 發明（設計）人: 張蕾;俞東進;孫笑笑;侯文杰;應鈺柯
• 申請（專利權）人: 杭州電子科技大學
• 主分類號: H04L41/5054
• 分類號: H04L41/5054;H04L67/02;H04L41/142
• 代理公司: 杭州君度專利代理事務所(特殊普通合伙) 33240
• 代理人: 朱月芬

1.關鍵字驅動的Web服務自動組合方法，其特征在于，包括如下步驟：

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

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

步驟(3).對服務初始匹配圖進行預處理，預處理過程包括檢測并去除死鎖、合并等效橋接服務、去除冗余服務節點；

步驟(4).為服務初始匹配圖中的每個Web服務節點構建索引L_NP以記錄每個服務的必經前驅關鍵字節點集合；構建索引M_ND以記錄每個服務節點與頭節點s_o之間的最短距離及最短路徑上包含的服務集合；

步驟(5).在服務初始匹配圖中運行DP-DFS啟發式關鍵字搜索算法來生成最終的最優服務組合G_F；

DP-DFS啟發式關鍵字搜索算法的具體執行過程如下：

1)從初始匹配圖的尾節點sd開始，逆向進行關鍵字搜索；將s_d的每個輸入參數添加到棧In_un中；初始化鍵值對集合K_selk，v，其中k表示某個待查詢的關鍵字，v表示關鍵字對應的服務節點；初始化最優服務組合G_F服務個數的上限值upper-bound為無窮大；初始化當前部分解決方案G_P＝In_un，S_sel，K_sel，L_NS并將其添加到棧T_ps中，其中S_sel和K_sel分別表示部分解決方案中已包含的服務集合和關鍵字集合，L_NS是為部分解決方案中每一個尚未處理的服務節點構建的索引，用來記錄服務節點的必經后繼關鍵字節點，其中尚未處理的服務節點表示仍含有未匹配輸入的服務；

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

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

其中，g(G_P)表示部分解決方案中已包含的服務節點個數；h(G_P)表示從當前部分解決方案擴展到完整解決方案的啟發式預估最小成本，最小成本為包含的最小節點個數；若f(G_P)大于upper-bound，則返回步驟2)；若當前部分解決方案沒有未解決的輸入參數且它包含了所有查詢關鍵字，則將其作為當前的最優服務組合方案G_F并更新upper-bound值為該組合方案中包含的服務個數，返回步驟2)；

3)從In_un中取出一個未解決的輸入參數i，并獲取與i連接的所有前驅服務節點作為它的候選服務節點集合CANDIDATE(i)；

4)對i的每一個候選服務節點進行如下操作：若該候選服務節點的前驅必經關鍵字已包含在當前部分解決方案中，或者該候選服務節點的前驅必經關鍵字與部分解決方案中已有關鍵字之間不符合時序要求，或者選擇該候選服務節點會造成循環，則從CANDIDATE(i)中移除該服務節點；所述的候選服務節點的前驅必經關鍵字由索引L_NP得出；

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

6)重復步驟5)，直到CANDIDATE(i)中不存在未被處理的服務節點；

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

8)輸出此時的最優服務組合方案G_F。