[發明專利]一種服務組合中基于閾值的動態成員服務選擇方法

無效

• 申請號: 200910089844.7
• 申請日: 2009-07-24
• 公開（公告）號: CN101616180A
• 公開（公告）日: 2009-12-30
• 發明（設計）人: 代桂平;王勇
• 申請（專利權）人: 北京工業大學
• 主分類號: H04L29/08
• 分類號: H04L29/08;G06N3/00
• 代理公司: 北京思海天達知識產權代理有限公司
• 代理人: 張 慧

1.一種服務組合中基于閾值的動態成員服務選擇方法，利用蟻群系統對于基于閾值 的動態成員服務進行選擇，其特征在于包括：利用成員服務和組合服務的信任程度、成員 服務和組合服務執行一次所使用的響應時間、以及成員服務和組合服務執行一次的費用， 利用蟻群系統和提供服務的上限閾值，將上述服務質量要求歸一化為蟻群系統有向圖中的 節點之間的距離；

所述的信任程度對于成員服務，采用執行成功率計算；對于組合服務來說，信任度采 用基于結構分析的方法計算；

所述的響應時間采用執行結束時間和執行開始時間的差值計算；對于組合服務，響應 時間采用基于結構分析的方法計算；

所述的費用，對于成員服務，由服務提供者制定；對于組合服務，采用基于結構分析 的方法計算；

1.1.模型建立；

組合服務中每一個具體服務都隸屬于某一個服務本體；

組合服務在執行時狀態轉移發生在具體服務之間，但是具體服務之間的狀態轉移需要 服從服務本體之間的執行約束；

信任感知的成員服務選擇問題轉換為在組合服務中尋找一條最優路徑；

1.2.成員服務選擇方法；

?對數學模型中多個優化目標進行歸一化處理，定義為有向圖中兩個節點之間的距離；

具有N個具體服務的組合服務模型中信息素的初始值τ_ij(0)定義為

τij(0)=10.5*N*Σi=0N-1Σj=0N-1dij/N2=2NΣi=0N-1Σj=0N-1dij]]>

d_ij為有向圖中節點i與節點j之間的距離，tr_i為第i個成員服務的信任度指標值，c_i為 第i個成員服務的費用指標值，ti_i為第i個成員服務的響應時間指標值，其中信任度為正 效應參數，而費用和響應時間為負效應參數，并分別滿足一定的約束，如 f＞Tr，g＜C，其中Tr，C，Ti分別為信任度、費用和響應時間的常數，N為組合服務 中具體服務的個數，M為螞蟻的個數，R為信息揮發系數且

1.2.1參數初始化：設循環次數N_s＝0，設置最大循環次數將M只螞蟻至于起始 服務上，初始化信息素初值τ_ij(0)，Δτ_ij(t)＝0；

1.2.2.N_s←N_s+1；

1.2.3?螞蟻數目k←k+1；

1.2.4.依據禁忌表在選定下一個具體服務s時更新規則更新禁忌表；

禁忌表在選定下一個具體服務s時更新，在更新時遵循以下3條規則：

規則一：s加入禁忌表；

規則二：與s同屬于一個服務本體的其他具體服務加入禁忌表；

規則三：從s出發不存在一條可達的執行路徑的具體服務加入禁忌表，從而消除死節 點；

依據狀態轉移規則選定下一個服務；

位于節點i的螞蟻依據下列規則來選擇節點j：

如果q≤Q₀，有

否則，有

其中之間的隨機數，之間的常數，ρ_ij(t)為轉移條件，為啟 發函數，α為信息啟發式因子，β為期望啟發式因子，allowed＝{S-tabu}，S為組合服 務中所包含的所有具體服務的集合，tabu為螞蟻搜索過程所產生的禁忌表，n為allowed中 包含的具體服務的數量；

1.2.5.若有服務未搜索到，轉至步驟1.2.4，否則轉至步驟1.2.6；

1.2.6.依據信息素局部更新規則更新信息素；

信息素采用如下的局部更新規則：

τ_ij(t+N)＝(1-R)*τ_ij(t)+R*τ_ij(0)

d_ij為有向圖中節點i與節點j之間的距離，tr_i為第i個成員服務的信任度指標值，c_i為 第i個成員服務的費用指標值，ti_i為第i個成員服務的響應時間指標值，其中信任度為正 效應參數，而費用和響應時間為負效應參數，并分別滿足一定的約束，如 f＞Tr，g＜C，其中Tr，C，Ti分別為信任度、費用和響應時間的常數，N為組合服務 中具體服務的個數，M為螞蟻的個數，R為信息揮發系數且

1.2.7.若k≤M，清空禁忌表，轉至1.2.3，否則轉至1.2.8；

1.2.8.依據信息素全局更新規則更新信息素；

在蟻群完成一次迭代時，信息素采用如下的全局更新規則：

τ_ij(t+N*M)＝(1-R)*τ_ij(t)+R*Δτ_ij(t)

其中Δτij(t)=Σk=0M-1Δτijk(t)]]>

N為組合服務中具體服務的個數，M為螞蟻的個數，R為信息揮發系數且L_k表示第k只螞蟻在本次迭代中所經過執行路徑的總長度；

1.2.9.若轉至步驟1.2.2，否則結束；

2.根據權利要求1所述的一種服務組合中基于閾值的動態成員服務選擇方法，其特 征在于基于提供服務的上限閾值的狀態轉移規則；

位于節點i的螞蟻依據下列規則來選擇節點j：

如果q≤Q₀，有

否則，有

其中之間的隨機數，之間的常數，ρ_ij(t)為轉移條件，為啟 發函數，α為信息啟發式因子，β為期望啟發式因子，allowed＝{S-tabu}，S為組合服 務中所包含的所有具體服務的集合，tabu為螞蟻搜索過程所產生的禁忌表，n為allowed中 包含的具體服務的數量。