[發明專利]一種基于最優路徑選擇的網絡感知服務組合算法的方法

有效

• 申請號: 202010586754.5
• 申請日: 2020-06-24
• 公開（公告）號: CN111770020B
• 公開（公告）日: 2022-04-12
• 發明（設計）人: 余建;張武威;李增祿;肖香梅
• 申請（專利權）人: 三明學院
• 主分類號: H04L45/302
• 分類號: H04L45/302
• 代理公司: 廈門智慧呈睿知識產權代理事務所(普通合伙) 35222
• 代理人: 楊唯

1.一種基于最優路徑選擇的網絡感知服務組合算法的方法，其特征在于，包括如下步驟：

步驟一：輸入圖G(V,E,s,t,ω,W,c,C,H,K)以及參數ε；

步驟二：根據步驟一中的服務網絡圖路徑的節點約束，預先測減不滿足服務能力的拓撲節點；其中，判斷節點υ的服務能力不能滿足服務需求的條件為c_υC_h；

步驟三：根據步驟二中的被簡化的服務網絡圖重新計算每條邊的新權重，并設置搜索空間參數Δ；

步驟四：初始化(K-1)維路徑權值數組；

步驟五：使用動態規劃計算最優路徑，記錄路徑節點；其中，當u-υ為圖中一條邊時，則從節點s到節點υ的第一維最小權重路徑p一定經過某些中間節點u，當服務最優路徑選擇算法(OSP)通過搜索所有可能中間節點u與節點υ之間的邊，來獲得最小的第一維路徑權重d^υ[δ₂,L,δ_K]；如果當前記錄的第一維路徑權重d^υ[δ₂,L,δ_K]大于之前的記錄值d^υ[δ₂,L,δ_j-1,L,δ_K]，則繼承以前第一維最小路徑重；

步驟六：查找滿足用戶需求的最優服務組合路徑，

其中：一個服務組合方案，在某服務網絡中的一條路徑p，如果對于有c_v≥C_h和ω_k(p)≤W_k，其中υ∈S_h，1≤h≤H，1≤k≤K，那么路徑p是一個可行的服務組合方案，對于一個給定的圖G(V,E)，假設所有可行的服務組合方案記為{p^f}，那么對于其中任一個服務組合方案都存在一個最小值η_i∈(0,1]使得1≤k≤K，并且對于有c_v≥C_h，1≤h≤H，

并對其進行拓撲結構轉換：轉化過程中Sa和Sb保持不變，執行完Sa之后，就分別以p₁,p₂,L,p_n概率執行服務S₁,S₂,L,S_n，然后再執行Sb；t_i,c_i,r_i,th_i分別代表的響應時間、代價、可靠性和吞吐量，F_i(x)代表概率響應時間t的概率密度函數，P_i1(x)代表代價c的密度函數，P_i2(x)代表可靠性r的密度函數，P_i3(x)代表吞吐量th'的密度函數，P代表順序結構轉換后的服務S1n的值；如果路徑P滿足ω_k(p)≤W_k，2≤k≤K，則算法返回可行路徑p，否則返回無可行路徑提示，程序終止。

2.如權利要求1所述的一種基于最優路徑選擇的網絡感知服務組合算法的方法，其特征在于，步驟三中：去除步驟二中的節點后原始服務網絡圖就被直接轉化成一個更簡單的圖，用于求解QoS感知的服務組合問題的可行解，其中：z_i＝{(α,β)|α∈V,β∈E′}，其中E′表示關聯性節點的新權重集合。

3.如權利要求1所述的一種基于最優路徑選擇的網絡感知服務組合算法的方法，其特征在于，步驟四：其中數組d^υ[δ₂,L,δ_K]記錄從源節點s到任一中間節點υ的路徑p第一維參數最小權重(ω₁)，該路徑p滿足ω_k(p)≤δ_k，2≤k≤K；

數組p^υ[δ₂,L,δ_K]記錄路徑p上節點υ的前驅節點，該路徑p滿足ω₁(p)＝d^υ[δ₂,L,δ_K]，且ω_k(p)≤δ_k，2≤k≤K。