一种基于构件的设备软件动态服务调度方法

林丽娜 孙光辉 唐晶

摘要：本文给出一种基于图约束装箱算法的构件调度策略生成算法，将构件动态部署和调度策略的生成描述成新的装箱问题，将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.