[發明專利]一種基于k2

有效

• 申請號: 201710414226.X
• 申請日: 2017-06-05
• 公開（公告）號: CN107248930B
• 公開（公告）日: 2020-07-28
• 發明（設計）人: 董榮勝;武先強;古天龍
• 申請（專利權）人: 桂林電子科技大學
• 主分類號: H04L12/24
• 分類號: H04L12/24;H04L29/08
• 代理公司: 桂林市持衡專利商標事務所有限公司 45107
• 代理人: 陳躍琳

本發明公開一種基于k²?MDD的Web服務組合方法，首先根據k²樹的規則對Web服務組合問題依賴圖的頂點進行編碼，然后依據頂點編碼對邊進行編碼，接著根據邊編碼構造多值決策圖結構，得到k²?MDD結構，最后對所得的k²?MDD結構采用符號決策圖的邏輯操作進行圖的基本操作。通過對Web服務組合問題的關系依賴圖用k²?MDD結構存儲表示，實現對Web服務組合問題的關系依賴圖進行高效、緊湊地表示從而大大減少了頂點的存儲空間，減小了搜索空間。

技術領域

本發明涉及大規模圖數據存儲與Web服務技術領域，具體涉及一種基于 k²-MDD的Web服務組合方法。

背景技術

Web服務組合是一種能夠通過組合多個功能簡單的Web服務來完成一項復雜任務的有效方式。但面對當前大規模的Web服務，如何快速的組合出滿足用戶功能性需求的Web服務組合結果是富有挑戰性的問題。近些年來，Web 服務組合問題逐步成為Web服務研究領域的熱點。基于圖模型的方法是解決服務組合問題的主要方法之一，因為圖模型表示大量的多種可能的服務組合需要大量的空間，所以利用壓縮圖表示服務組合依賴圖被提出。多值決策圖 (Multi-valued Decision Diagram，MDD)適用于描述多值變量，并且能夠實現空間或者變量組合的隱式表示與搜索，使得所表示的結構更為緊湊，頂點得到明顯的減少。

關于服務組合問題已經有相當多的研究，其中，M.Kuzu等提出利用規劃方法解決服務組合問題。規劃選擇適當的服務并確定它們的順序以達到目標。為了解決一個服務組合問題，規劃算法應該首先構造一個送初始狀態到目標狀態的搜索圖，然后通過后向搜索找到一個解決方案的路徑。在大規模的服務的數量和組合下，規劃算法受到搜索空間的限制，可能無法找到解決方案。為了對圖數據進行緊湊表示，在傳統的鄰接矩陣表示法的基礎上，Brisaboa 等于2009年提出了基于k²樹(k²-tree)的方法，樹中的每一層對應于鄰接矩陣或分塊子矩陣的分塊子矩陣，頂點對應于鄰接矩陣的分塊子矩陣，生成的 k²樹使用兩個位向量T和L來存儲，該方法不僅能夠緊湊表示鄰接矩陣，而且能實現鄰接頂點的正向或逆向高效查詢操作。為了應對這個挑戰，可以使用壓縮圖來表示Web服務組合問題，Li等人使用Brisaboa提出的k²樹結構來解決該問題。雖然使用k²樹的結構來存儲表示Web服務組合，使得結構更為緊湊，頂點數得到顯著的減少，但是在對大規模Web服務組合問題表示時仍具有一定的局限性。施佺等給出了k²樹表示方法的兩種優化技術：啟發式深度優先頂點重排序和自適應修正k，使得所表示的結構更為緊湊，頂點得到明顯的減少。

不論是k²樹還是施佺優化過的k²樹，在對大規模Web服務組合問題表示時仍具有一定的局限性，具體表現在：

1)當圖的規模變大時，圖內部本身就會存在大量的同構子圖。同樣的，當按照k²樹的思想把鄰接矩陣進行劃分后，也存在大量的相同的子矩陣。這就造成了k²樹內也存在大量的同構子樹。

2)k²樹僅對稀疏圖有效，當圖變的稠密時，由于鄰接矩陣內可被壓縮的 0頂點變少，因此k²樹緊湊性也會變低。

3)k²樹未涉及動態圖(需要添加或刪除頂點、邊以及子圖等的圖)的表示與操作。

目前的k²樹的圖數據緊湊表示方法對上述圖的結構特性尚缺乏必要的考慮，在緊湊性上仍有較大的改善空間。針對基于k²樹Web服務組合目前存在的問題，有必要對其進行進一步的優化與改進，以得到一種更為緊湊的結構表示方法使得進一步減少Web服務組合問題的頂點存儲空間。

發明內容