一種基于構件的設備軟件動態服務調度方法

林麗娜 孫光輝 唐晶

摘要：本文給出一種基于圖約束裝箱算法的構件調度策略生成算法，將構件動態部署和調度策略的生成描述成新的裝箱問題，將CPU看做箱子，構件看做物品。當兩個CPU之間有構件存在數據收發關系時，需要在CPU之間創建RapidIO數據鏈路。構件部署完成后，得到一張以CPU為頂點、RapidIO數據鏈路為邊的關系圖，需要在該圖滿足頂點容量、邊的度數等約束條件下，使得占用箱子數量最小，是一個復雜的NP完全問題。實驗表明，本文給出的基于圖約束裝箱算法的構件調度策略生成算法，能夠較好地解決大規模構件的動態部署問題。

Abstract： This paper presents a component scheduling strategy generation algorithm based on graph-constrained bin packing algorithm. The dynamic deployment of components and the generation of scheduling strategies are described as a new packing problem， the CPU is regarded as a box， and the component is regarded as an item. When there is a data receiving and sending relationship between two CPUs， a RapidIO data link needs to be created between the CPUs. After the component is deployed， a relationship graph with the CPU as the vertex and the RapidIO data link as the edge is obtained. The graph needs to meet the constraints of vertex capacity， edge degree and other constraints， so that the number of occupied boxes is minimized， which is a complex NP-complete problem. Experiments show that the component scheduling strategy generation algorithm based on graph-constrained bin packing algorithm presented in this paper can better solve the problem of dynamic deployment of large-scale components.

關鍵詞：構件;設備軟件;服務調度

Key words： component;equipment software;service scheduling

中圖分類號：TP311.52 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?文獻標識碼：A ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?文章編號：1006-4311（2020）30-0205-03

1 ?圖約束裝箱問題BPPR的形式化表達

結合嵌入式信息處理設備中的構件調度問題，將BPPR裝箱問題可描述如下：

采用RapidIO高速總線的嵌入式多CPU單元的信息處理裝備中，給定一組容量為W的箱子（CPU）B={b1，b2，…，bm}，和n個物品（構件）的序列L={a1，a2，…，an}，物品ai的體積（如：CPU、內存占用率）為wi（wi？燮W），要求將這些物品裝進若干箱子中，使得每個箱子中裝載的物品總體積不大于W，并使所用的箱子數目最小。

在通過求解裝箱問題來生成構件部署策略時，除了滿足經典裝箱問題所需要考慮的箱子容量和物品體積條件外，還需要滿足硬件環境中CPU的通信鏈路數量限制。因此，需要建立裝箱過程的圖約束條件。

給定一組待部署的構件，建立構件間通信關系的對稱鄰接矩陣A：

其中，aij表示構件i與構件j之間存在數據收發關系，如果它們被部署到不同的CPU之上，則需要在兩個CPU之間建立一條RapidIO通信鏈路。后面可通過鄰接矩陣A，對構件進行輔助搜索。

當構件部署到CPU單元后，以CPU為頂點，CPU之間的RapidIO通信鏈路為邊，便得到一張m個頂點的無向圖G=（B，E）。要求圖的所有頂點的“度”不大于數值c（c∈N*），即每個CPU所建立的RapidIO通道數目不大于c。

基于以上符號約定，將BPPR裝箱問題用線性規劃的方式描述如下：

其中，dk表示第k個CPU（頂點）的度，變量x，y是兩個二叉決策模型，其含義分別是：

可見，BPPR裝箱問題是一個雙目標優化問題，目標函數（1）是為了使所使用的CPU數量收斂到最小，目標函數（2）的目標是使所需要創建的RapidIO通道數量最小。約束公式（3）保證了單個構件被且僅被分配到一個CPU上。約束公式（4）保證了CPU資源能夠滿足其加載的所有構件的計算資源需求。約束公式（6）確保不會超過單個CPU的RapidIO通道限制。本文給出的BPPR模型為一維裝箱問題，實際上可以根據需要擴展到高維度裝箱問題，其原理相同。

2 ?BPPR裝箱問題求解

本文給出的BPPR裝箱問題求解方法，其特點是一種變權綜合目標函數求解算法，該算法包括兩個階段的計算，用以求解復雜的BPPR多目標優化問題。算法結合了廣度優先搜索技術以及可變權重的排序算法，稱為VWSOF（Variable Weight Synthesizing Objective Function）算法。第一階段，排序。通過可變組合系數法，依據物品的權重對構件進行降序排序;第二階段，改進的FFD搜索算法，對給定的構件序列，從降序序列中取出第一個未裝箱的物品，并采用廣度優先搜索算法從隊列中依次取出未分配物品，求解其最優裝箱策略。循環迭代上述兩個階段的計算過程，直到滿足收斂條件或達到預先設定的迭代次數。

VWSOF算法的主要流程如下：

第一步：參數初始化。根據BPPR裝箱問題的描述，初始化箱子和物品的參數，以及約束圖的相關參數。

第二步：采用可變組合系數法，為所有物品計算權重。變權目標函數定義如下：

公式（7）中的變量wi表示權重wi的歸一化值，變量表示ai在RapidIO數據傳輸方面的影響系數的歸一化數值。公式（8）中的變量j表示算法的第j次迭代。

第三步：根據最新的物品權重，對物品進行降序排列。

第四步：選擇一個待裝箱的物品。從排序好的物品序列中第一個尚未被裝箱的物品開始，以鄰接矩陣給出的物品間的連接關系為路徑，采用深度搜索算法BFS（Breadth First Search）搜索出下一個待裝箱的物品。

第五步：采用經典FFD算法對物品進行裝箱。在對物品進行裝箱求解時，出判斷物品總體積是否超過箱子容積外，還需要同時滿足公式（3）、（4）、（5）、（6）的約束條件。

第六步：重復執行步驟（四）、步驟（五），直到所有物品裝箱完成，并將裝箱結果記錄。若裝箱過程中有物品無法找到能夠滿足所有裝箱和圖約束條件的箱子來裝載，則返回步驟（二）。

第七步：重復執行步驟（二）到步驟（六）的過程，直到達到迭代次數。

第八步：選擇近似最優的裝箱策略。本文所設計的VWSOF算法對于多目標函數最優化問題最佳方案的判定方法是（算法1中的步驟6），根據ListOfSolution中各備選方案所對應的無向圖G=（B，E）的頂點數量m和邊的數量E兩個評價指標進行對比。具體方法是，采用熵權法根據每個方案si的兩個指標mi和邊的數量Ei的值對指標進行賦權，進而實現對比。對于待評價ListOfSolution中的u個裝箱方案，和v=2個評價指標，形成原始數據矩陣R=（rij）u×v：

其中，rij表示第j個指標下第i個待評價方案的評價值。則，本文的基于熵權法的最佳方案的判定方法具體實現步驟如下：

①計算第j個指標下第i個項目的指標值的比重pij：

至此，得到兩個評價指標的綜合權數，對每個方案進行加權評價，選出箱子和通道資源消耗最小的一組裝箱方案為問題的最佳方案。

3 ?實驗驗證

對VWSOF算法進行實驗驗證，設置主要的圖約束條件如下：

#define inDegree 4 ?//頂點的最大入度

#define outDegree 8 ?//頂點的最大出度

#define BucketVolume 1.0 //箱子的最大容量W

#define WeidgtControl 0.6 ?//物品權重wi取值空間（0，0.6]

其中，頂點最大入度為4，頂點最大出度為8，單個箱子的最大容量為1，單個物品權重取值為（0，0.6]之間的隨機數。動態生成一定數量的物品，分別采用BFD和VWSOF算法進行裝箱，得到實驗結果如表1。

如表1所示，傳統BFD算法由于在裝箱過程中只根據物品重量和箱子容量進行裝箱，因此很難滿足圖的邊約束條件。而本文VWSOF算法，通常可以計算出滿足圖約束條件的裝箱解。由于VWSOF算法相比BFD算法多計算了邊約束條件，因此所使用的箱子數量通常比后者多。另外，本文VWSOF算法在某些情況下也無法得到滿足約束條件的裝箱解，但是隨著迭代次數的增大，得到解的概率增大。

4 ?結論

本文給出一種基于圖約束裝箱算法的構件調度策略生成方法，滿足基于RapidIO高速總線的嵌入式信息處理設備下，對于大量具有復雜信息交互關系的服務構件的快速部署策略生成，并能夠充分滿足設備計算資源、RapidIO高速數據總線資源的合理利用與分配。

參考文獻：

[1]陳廷斌，魯艷霞，袁磊.面向動態服務的物聯網Web Services組合調度方法研究[J].情報雜志，2011，30（S2）：134-137.

[2]薄夢雅.時間序列數據壓縮算法研究[D].石家莊鐵道大學，2019.

[3]李偉，楊超宇，孟祥瑞.基于混合遺傳算法的多品種貨物裝箱問題研究[J].包裝與食品機械，2020，38（03）：51-56.