一种虚拟服务资源的多分配任务的选择方法

陈为兵，王忠群

（安徽工程大学 计算机与信息学院，安徽 芜湖 241000）

随着服务计算技术的发展，面向服务的企业作为一种新的业务模式受到广泛关注［1－7］.越来越多的服务需要多个组织提供的虚拟服务资源来支持完成，使得网络成为一个机－机乃至人－机协同动作的平台.虚拟服务资源的概念可以延伸到包括软件、硬件、人力、物理设备乃至环境等各种支持服务属性的要素［3］.服务质量（QoS）是衡量虚拟服务资源选择的一个重要方面，包括执行时间、费用、可用性及可靠性等.

目前，对于服务组合方面相关研究较多.企业间的主观信任关系对服务选择起决定性作用，文献［2］提出了一种基于信任关系的业务服务选择方法.对于用户来说个性化服务是服务需求的趋势，文献［3］提出一种面向个性化需求的虚拟服务资源整合方法，把服务资源以多维度分类树的方式进行描述.文献［4］提出了一种基于声誉的推荐方法，给出具有高声誉值的推荐信息源.文献［5］提出了一个考虑资源置信度的跨企业项目伙伴选择模型，提出了两个优化算法分别对速度和最优率进行优化.文献［6］提出了一种支持服务应用关联的服务选择方法，展现了关联服务对选择过程的影响.

然而，上述文献都未考虑到虚拟服务资源中的资源数量受限问题，如硬件、人力资源、物理设备等资源数量有限，其可用性伴随用户数量而波动.服务提供商在提供虚拟服务资源时存在瓶颈问题，需要同时提供给多个用户的多个子任务使用.资源的可用性是可信性的一个重要方面，本文对服务资源进行分类，加入置信度概念，综合考虑项目QoS指标、信任度及费用等参数，对服务资源运用遗传算法求解，最后验证方法的可行性和有效性.

1 问题描述和有关符号定义

假设某企业（主企业）有一个由多子任务构成的项目，其部分工作流程需对外招标，由其他外包企业协助完成.工作流程分为子任务1、子任务2、…、子任务i、…、子任务n，当项目进行到子任务i时，主企业要对外包企业提供的资源进行评估.对硬件、人力、物理设备等服务资源进行分类：一类是可同时向外提供多任务节点资源（M），另一类是提供单任务节点资源（N）.从信任度角度看，存在外包企业同时投标多个子任务的情况，在选择子任务i的服务资源时，由于在同一时刻提供M资源的外包企业同时也在提供资源给其他子任务，我们对于它的信任度也会相应有所降低，所以在考虑用户对M资源的信任度时，有必要在原信任度上乘以一个信任因子pk，这样更能准确地刻画资源的随机性.首先，我们给出3个假设：①假设项目可以独立分为多个子任务；②假设各子任务之间的交接时间为0；③假设每个子任务只能由一个外包企业来提供服务资源.

为便于表述，给出如下符号：i为项目流程中每个子任务的序号，i＝1，2，3，…，I；j为兄弟企业提供给子任务i相对应的资源集群里服务资源的序号，j＝1，2，3，…，Ji；Xij为0－1决策变量，当Xi，jj＝1时就表示资源集群里j资源被子任务i所征用，相反Xi，j＝0，i＝1，2，3，…，I，j＝1，2，3，…，Ji；Ci，j为资源集群i中资源j运行一次的费用成本；ti，j为资源集群i中资源j运行一次的时间成本；ai，j为资源集群i中资源j的可用性；ri，j为资源集群i中资源j在运行中的可靠性；hi，j为用户对资源集群i中资源j的信任度；α为置信水平，α∈ ［0，1］；pk为信任因子，p∈ ［0，1］，k＝1，2，3，…，Ki；Ci为用户对子任务i开销费用的期望上限值；Ti为用户对子任务i运行时间的期望上限值；Ai为用户对子任务i的期望可用性下限值；Ri为用户对子任务i的期望可靠性下限值；Hi为用户对子任务i期望信任度下限值；Yi为用户对配置后资源i的信任度下限值；C0为用户对整个工作流程运行一次所产生总费用的上限值；T0为用户对整个工作流程运行一次所需总时间的上限值；Y0为用户对整个工作流程运行一次配置后资源信任度的下限值.

2 基于多任务服务资源选择模型的建立

本文综合考虑QoS指标、信任度、费用3个参数作为决策因数，对有关硬件、人力、物理设备等服务资源进行选择，将流程总执行时间、总执行费用作为规划目标.此处QoS指标包括：任务执行时间、费用、可用性和可靠性，pk为因外包企业提供给其他子任务资源而降低目前子任务资源信任度的一个惩罚因数.假设某外包企业能同时提供给k（k＝1，2，3，…，Ki）个子任务的资源l，那么用户对此l资源的信任度就会在原有基础上有所降低.设，k＝1，2，3，…，Ki，x1∈ ［0，1］，x1为用户对资源l划分后第一个起点.不难理解当k＝1时，x1＝0；当k≠1时，x1≠0，x1的取值如表1所示.

表1 x1取值与k之间的对应关系

资源服务选择模型定义如下：

在上述式子中，式（1）表示所有工作流程总运行费用和总运行时间分别与用户期望的总运行费用和总运行时间的差值依字典序达最小；式（2）表示所有工作流程总运行费用、总运行时间和配置后资源信任度与用户期望值的差值；式（3）表示用户对每个子任务所需资源的信任度在置信水平a上不低于用户的期望值；式（4）、（5）表示完成每个子任务时，对所选资源的费用和时间都不高于用户的期望值；式（6）、（7）表示完成每个子任务时，对所选资源的可用性、可靠性都不低于用户的期望值；式（8）为0－1决策变量，表示每个子任务只能由一个外包企业来承担；式（9）为数据关系表达式.

在业务流程中除了顺序结构外，还有并行、选择和循环结构，下面给出各结构的时间和费用计算方法.

③选择结构中，假设业务流程由I个子任务组成，每个子任务i被选择的概率为，总时间

④循环结构中，假设业务流程由I个子任务顺序组成，此流程的循环概率为γ，总时间T＝

3 模型求解

由于此问题不是线性问题，我们采用遗传算法对上述模型进行求解.其算法思想是将每一个配置后的业务流程编码为一个染色体，通过染色体之间的选择、交叉和变异产生出具有更高适应度值的染色体，重复上述步骤直到满足具体要求，最终得到一个染色体集，此染色体集是在解空间寻求的解集.具体步骤：①编码.对流程涉及到的每个资源进行编号，每个资源是一个基因，一个染色体是一串基因的组合.②产生初始种群.随机产生N个个体组成初始种群，每个染色体称为一个个体，N个个体构成了一个种群.假设现在的代数g1＝0，假设种群规模为W，开始时染色体上面的基因在［1，W］随机选取随机排列而成.③计算适应度值.评估种群中所有个体的目标值，再评估每个个体的适应度值，此处适应度值函数f＝100D＋c＋10D＋t＋D＋y.④种群进化.对于选择算子，采用轮盘赌的方式进行；对于交叉算子，采用双点交叉进行；对于变异算子，以一定概率丢失某个基因，再在［1，W］随机产生一个基因来代替它.⑤终止检验.满足条件停止运算，最终种群解是我们需要的解集，代数g1＝g1＋1，否则继续执行.

4 仿真实验与分析

实验以摩托车装配流水线过程来示例.摩托车装配过程分为发动机装配（子任务S1），部件装配（子任务S2），车架装配（子任务S3），成车装配（子任务S4），产品测试（子任务S5）和包装下线（子任务S6），前3个节点是并行结构，后3个节点是顺序结构，总体形成一个顺序结构，制造流程结构如图1所示.

假设6个服务提供商ABCDEF，其提供资源与子任务Si间的对应关系如表2所示.

图1 摩托车制造流程结构图

表2 提供资源与子任务Si对应关系

参数设置：A ＝22，B＝18，C＝10，D ＝20，E＝14，F＝6.

用VC＋＋6.0变成实现遗传算法，交叉概率设为0.6，变异概率设为0.2，种群规模设为90.实验的硬件平台由Intel（R）Core（TM）i3－3220 3.30GHz和4.00GB内存组成的PC机.实验设置2组用户的资源需求来说明多分配方式在资源选择中的作用，服务资源参数设置如表3所示.

第1组表示不考虑资源的多分配任务作业，服务提供商在提供资源时按照S1S2S3S4S5S6的序列顺序提供，第2组表示服务提供商可以多分配资源任务，不同用户资源需求的选择方案如表4所示.从表4可看出，配置信任因子之后的选择方案不同于之前的选择方案，这是由于服务提供商在多分配任务之后造成给用户的信任度降低的结果，分配方式越多pk值的平均值就越小，给用户的信任度就越低，被后续子任务选择的概率也就越小.上述结果说明虚拟服务资源多分配任务算法的可行性和有效性.

表3 服务资源参数设置

表4 不同用户资源需求的选择方案

5 结束语

随着企业运营业务的全球化，基于Web环境的虚拟服务资源选择已成为企业外包过程中必不可少的一个环节.多层次多角度的分析资源，对于资源选择的研究有着十分重要的意义.本文将服务提供商分为两类，对提供多任务的服务资源设置了信任因子，运用遗传算法对模型进行了求解，并用实例验证该算法的可行性和有效性.但在上述过程中未考虑到资源释放问题，在占用资源一定时间后，子任务会释放资源，下一步工作将对此进行研究.

［1］ 张建良，范玉顺.面向服务的企业与业务生态系统［J］.计算机集成制造系统，2010，16（8）：1 751－1 759.

［2］ 李素粉，范玉顺.基于信任关系的业务服务选择方法［J］.计算机集成制造系统，2011，17（10）：2 278－2 285.

［3］ 初佃辉，王显志，王忠杰，等.面向个性化需求的服务资源整合方法［J］.计算机学报，2011，34（12）：2 370－2 380.

［4］ 潘静，徐锋，吕建.面向可信服务选取的基于声誉的推荐者发现方法［J］.软件学报，2010，21（2）：388－400.

［5］ 徐汉川，徐晓飞，何霆，等.考虑资源置信度的跨企业项目伙伴选择方法［J］.计算机集成制造系统，2010，16（7）：1 480－1 486.

［6］ 李素粉，范玉顺，李秀.支持服务应用关联的服务选择方法［J］.计算机集成制造系统，2012，18（3）：645－653.

［7］ Skopik F，Schall D，Dustdar S.Modeling and mining of dynamic trust in complex service－oriented systems［J］.information system，2010，35：735－757.