【作者】 程杰；

【导师】 曾广周；

【作者基本信息】 山东大学 ， 计算机应用技术， 2011， 博士

【摘要】 迁移工作流是一类基于移动agent技术的工作流管理范型。在迁移工作流模型中,迁移实例是任务的执行主体,工作位置是迁移实例的运行场所。迁移实例携带任务、目标和数据在分布的工作位置之间迁移,利用工作位置所提供的服务执行任务并接受服务结果,无需每一步都通过中心工作流引擎来交换数据,从而将集中在中心引擎上的控制逻辑分散到各迁移实例；迁移实例在执行任务过程中,能够根据环境的变化自治地决策迁移动作,当发现当前的工作位置不能满足其执行要求时,迁移实例将迁移到另一个能满足其要求的工作位置上继续执行；除迁移时间外,迁移实例的工作过程无需依赖网络连接。因此,迁移工作流模型大大提高了工作流系统适应动态环境的灵活性,特别适合那些执行环境动态多变和需要大量调用远程服务的分布式业务并发处理过程。迁移工作流技术的实质是利用迁移实例的群体智能实现工作流的整体执行目标,其核心是多迁移实例路径规划问题,即确定如何对任务进行有效分配,并根据执行环境生成满足执行目标的位置序列。按照智能规划思想,迁移实例的路径规划主要包括过程分解、个体路径规划和群体路径规划三个关键步骤。过程分解的目标是生成符合迁移实例执行特征,且覆盖整个任务集的过程分支的集合,每个过程分支包含任务序列与执行目标；基于过程分解结果,迁移实例个体路径规划将给出在动态不确定的执行环境下,采用何种方法选择工作位置来执行所分配的任务序列并达到预期的执行目标；群体路径规划基于个体路径规划,同时要考虑迁移实例之间的群体协作,即：迁移实例为实现群体目标而进行的个体目标协调,包括迁移实例之间组织结构、冲突消解策略以及通信协议等。本文基于山东大学移动计算实验室自行研发的迁移工作流管理系统框架,结合国家自然科学基金课题“面向目标的迁移工作流方法研究”,对迁移工作流执行系统的两个关键问题：业务过程分解和迁移实例路径规划进行了系统的研究,内容涵盖：基于极大覆盖子树的工作流过程域分解、面向多层次主从结构的业务过程并行分解、过程分支的静态规划、面向不确定执行环境的迁移实例个体在线路径规划和多迁移实例部分全局路径规划,并在原型系统平台上对上述工作进行了验证和分析。本文工作的主要研究内容包括：1.面向迁移实例群体协作的迁移工作流过程分解方法研究。不同于基于RPC(Remote Procedure Call)的工作流过程分解,迁移工作流过程分解的目的是服务于迁移实例对业务过程的协同规划与执行,由于任务之间的关系决定了迁移实例之间的角色定位,因而业务过程的分解需要考虑任务分配后迁移实例的组织结构和协作方式。本文将迁移工作流过程分解划分为两个步骤：域分解和并行分解。域分解面向大规模业务过程,分解的目的是为了降低直接并行分解以及迁移实例群体协作的高复杂性。针对域分解,本文提出一种基于极大覆盖子树的过程分解算法。并行分解面向迁移实例的群体规划,将业务过程逐层分解为一组具有主从关联的过程分支的集合,其分解方法是按任务粒度求解过程图的关键路径,然后逐层分离以关键路径遍历的过程分支,按树型结构形成过程分支之间的主从支配关系,并使之转化为迁移实例之间的协作关系。本文针对服务质量约束的工作流执行系统,分别给出了业务过程结构分解的算法和服务质量约束的分配算法,并对所生成的过程分支给出一种静态路径规划离散粒子群优化算法。2.面向不确定执行环境的迁移实例个体在线路径规划方法研究。对于不确定的执行环境,迁移实例在工作过程中难以做出一个整体的路径规划,只能根据当前执行环境的状况采取阶段性寻优的规划方式。本文基于Markov决策过程(Markov Decision Process, MDP)建模时间约束的迁移实例个体在线路径规划,以任务划分执行阶段,以剩余执行时间、时间临界度、时间偏移度和规划深度为状态变量,在每个执行阶段,迁移实例根据当前环境的动态性确定一个规划窗口,在当前规划窗口内求解满足约束的最优迁移路径。由于规划深度(规划窗口的大小)取决于执行环境的不确定程度,因而需要一种对执行环境不确定性的度量方法。本文借鉴信息熵的概念,提出一种通过周期采样计算工作位置服务质量稳定性熵和服务数量稳定性熵的方法,并基于工作位置的服务稳定性来度量执行环境的不确定性,然后根据环境的不确定性设置规划深度。实验表明,该方法既具有良好的动态环境适应性,又兼顾了整体路径规划的长远性。3.面向群体协作的迁移实例部分全局路径规划方法及其体系结构研究。在大规模迁移工作流管理系统中,业务过程通常由多个迁移实例协同完成。由于个体路径规划仅关注迁移实例自身目标的优化实现,缺少迁移实例之间的通信与协商,因而不能保证生成路径的全局最优性。本文基于部分可观察Markov决策过程(Partially Observable Markov Decision Process, POMDP)建模多迁移实例部分全局路径规划,提出一种迁移实例部分全局规划两层体系结构,将群体路径规划问题划分为协作层和个体规划层,其中,协作层面向群体协作,关注迁移实例的组织方式、冲突消解策略以及迁移实例之间的通信协商,其目标是通过协商确定个体规划的执行目标,而不需要考虑对每个任务的规划细节；个体规划层则针对协作层制定的个体执行目标,关注该目标的实现方法,而无需考虑群体协作问题。在个体规划层,采用个体在线路径规划方法；在协作层,本文给出了一种迁移实例的树型组织结构,基于该结构提出了一种迁移实例的协作通信协议以及服务冲突和目标冲突的消解策略与实现方法。这种分层规划的思想有效地简化了迁移实例群体规划的复杂性,为多智能体的协同计算在工作流技术中的应用提供一种有价值的探索。本文工作的创新点主要体现在：1.提出了一种基于多层次主从结构的结构化业务过程并行分解方法。不同于中心化WfMC模型的分解,迁移工作流过程分解的核心是如何支持非中心化的迁移实例有序协作。本文提出的基于多层次主从结构的迁移工作流过程并行分解方法,以树型结构表示过程分支之间的主从关系,以过程分支中的同步任务为协作关键点。因为在任务指派之后,过程分解树可以等价地映射为迁移实例组织树,所以,迁移实例可以基于过程分支之间的主从关系和协作关键点实现按需协商,使协作有序。与不区分主从关系的分解方法相比,树形结构表示的主从关系能够提供更加清晰的协作线索,有效支持迁移实例之间的自主协作。2.提出了一种基于MDP和不确定执行环境的迁移实例在线路径规划方法。不同于已知全局环境的路径规划方法,迁移实例在线路径规划的核心是如何度量执行环境的不确定性并采取相应的行为策略。本文提出的基于MDP和不确定执行环境的迁移实例在线路径规划方法,以服务稳定性熵度量执行环境的不确定性,以规划窗口为行为策略,与基于贪心策略的一步规划方法相比,基于环境不确定性度量的规划窗口方法,既具有对不确定性执行环境的动态适应性,又兼顾了整体规划的长远性。3.提出了一种基于POMDP的多迁移实例部分全局路径规划方法。除业务过程分解方法必须支持迁移实例有序协作外,迁移实例群体规划的另一个目标是如何简化群体规划的复杂度,提高业务过程的执行效率。本文提出的基于POMDP的迁移实例部分全局路径规划方法,以同步任务划分全局规划的执行阶段,以基于同步任务划分的任务帧为个体规划单元,全局规划实现目标在协作迁移实例之间的分配,部分规划实现迁移实例基于任务帧和目标分配的路径构建。与不分层的群体规划方法相比,由协作层和个体规划层组成的体系结构可以有效降低迁移实例群体路径规划的实现复杂度,提高个体规划在实现方法上的灵活性。本文所提出的迁移工作流过程分解与规划方法在仿真实验和应用实例中已得到验证,但迁移工作流的群体规划是一个复杂的问题,还有很多值得探索和改进的方面,进一步的研究工作包括：1.业务过程在线分解与任务合并方法。对于复杂和多变的执行环境,单纯的事前分解可能使过程分支粒度的适应性不够,因此,如何支持迁移实例对业务过程的在线分解与任务合并具有非常实际的意义。在以后的研究中,应考虑将过程分解纳入迁移实例在线路径规划中,以实现动态执行环境下的业务过程按需分解。2.非结构化业务过程分解与群体路径规划方法。本文以结构化业务过程为研究对象,而非结构化业务过程分解与群体路径规划问题还需要在本文基础上做进一步的研究,下一步的工作将包括对非结构化业务过程并行分解算法的改进和群体规划体系结构的扩展等。更多还原

【Abstract】 Migrating workflow is a workflow management paradigm based on mobile agent technology. In a migrating workflow system, a migrating instance(MI) acts as the task executer. It catches the task list and data with an execution objective, migrates from one workplace to another, utilizes the service provided by the workplaces and accepts the service results, without needing to exchange data with the workflow management engine. By this way, the control flow that concentrated in the center engine can be decentralized to the migrating instances. During the execution period, a migrating instance will determine its routing path according to the dynamic execution environment. When the migrating instance finds that the current workplace can not meet its requirements to execute the task, it will migrate to another available workplace and go on. Except for migrating time, the migrating instance does not depend on the reliability of network connection. Therefore, migrating workflow model greatly improves the adaptability to the dynamic execution environment. Especially, the model adapts to those concurrent processes of distributed business that need large number of remote procedure call (RPC) in a changeful execution environment.The essence of migrating workflow model is to utilize the swarm intelligence of migrating instances to achieve the overall workflow execution goal. The key issue is the migrating instance path planning, which is to assign the tasks to the migrating instances and plan the optimal actions according to the specific execution environment so as to achieve the execution objective. According to the planning idea of AI, the path planning of migrating instances mainly consists of three key issues: process partition, individual path planning and group planning with multi migrating instance cooperation. The purpose of process partition is to separate a workflow process into a set of sub-processes, each sub-process with a sequence of tasks and an expected goal will be assigned to a migrating instance. Based on the results of process partition, the individual path planning is to select a most suitable workplace sequence for the sub-process so as to reach its individual goal in a dynamic and uncertain environment. Based on the individual planning, the group planning will take into account the group cooperation among the migrating instances for the workflow global goal, which includes the organizational structure of migrating instances, communication protocols and conflict resolution strategies.Supported by the National Natural Science Foundation of China "Research on the methods of goal-oriented migrating workflow", this thesis focuses on two issues: process partition and path planning based on the migrating workflow system framework proposed by the Mobile Computing Laboratory of Shandong University, which includes:process fragmentation based on the domain-cover sub-tree, process parallel partition method with a master-slave structure, static task planning for sub-processes, migrating instance individual planning with uncertain environment, and partial global planning. The study has been proved and analyzed on a prototype migrating workflow platform.The main contributions of this work are described as follows.1. Research on workflow process partition method for multi-leveled master-slave cooperation of the migrating instances.Different from the RPC based workflow process fragmentation methods, the objective of process partition in a migrating workflow is to cater for the migrating instance group planning. Since the relations among the migrating instances are based on the relations between the sub-processes they catch, the collaboration relations among the migrating instances have been taken into account before partitioning. The process partition in this work consists of two steps, which are domain fragmentation and parallel partition. The former aims at large workflow process, with the purpose of reducing the high complexity of parallel partition and migrating instance group cooperation. This thesis proposes a maximum sub-tree based method which fragments a workflow process into a set of domain-processes. Each domain-process with a relative independent domain attribute will be parallel partitioned in the next step. The parallel partition is to divide a process or a domain-process into a set of task-sequences with master-slave relations among them. The main idea of parallel partition is that, repeatedly search for the critical path of DAG (or sub-DAGs) of the process, and then separate the obtained critical path from the DAG and the remained sub-DAGs until the process has been completely partitioned. The master-slave relations among the sub-processes generated by the parallel partition will become the relations among migrating instances. In order to meet the quality of service (QoS) constrain, this thesis studies not only the structure partition but also the QoS allocation methods, and presents a discrete particle swarm optimization algorithm for sub-process static path planning.2. Research on migrating instance individual path planning in uncertain execution environments.Since the execution environment is changeful and uncertain, it is hard for a migrating instance to make a long term planning. A feasible way is to take a periodic optimizing planning according to the specific environment. This thesis models the individual path planning problem with Markov decision process (MDP), which segments the stages by tasks and define the execution state variables as remain deadline, time offset and planning step length. In each stage, the migrating instance determines a planning window according to dynamic environment and searches for the optimal routing path which meets the QoS constraints. Since the planning step length depends on the uncertainty of execution environment, it is possible to give a measurement method for the uncertainty of execution environment. Thus we reference the concept of entropy and present an approach to calculate the stability entropy of a workplace by periodic sampling the change of the quality of service and quantity of service. Based on the stability entropy of the available workplaces, the uncertainty of the execution environment can be measured, which enable the migrating instance to set the planning step length in each stage. The experiment results prove that the proposed approach achieves the satisfactory trade-off between the adaptability to the environment and execution performance.3. Research on partial global path planning for migrating instance group cooperation.The objective of migrating instance individual path planning is to optimize its execution performance without considering the execution of its partners’. However, due to lack of the group cooperation, the migrating instance plans its routing path based only on the observations about environment by itself and care only about the objective of its own. So the planning strategy can be optimal for the migrating instance itself, but not for the global workflow. This thesis models the migrating instances group planning as a partially observable Markov decision process (POMDP), and proposes a partial global planning architecture that divides the group planning problem into two layers:cooperation layer and individual planning layer. The cooperation layer focuses on group cooperation, which includes the organization structure of migrating instances, conflict resolution principle and communication protocols. The goal of cooperation layer is to determine the individual planning objective for each task frame and does not have to handle the details of task planning. The individual planning layer focuses on the implementation of the objective obtained by the cooperation layer and does not have to care about the group cooperation. For the cooperation layer, we propose an MI cooperative organization based on tree structure. Based on this structure, we also put forward a set of communication protocols between the MIs, as well as the resolution principles and methods of service conflicts and objective conflicts. The two-layer partial global planning architecture provides a way to simplify the complexity of group planning problem, which offers a valuable resolution of multi-agent collaborative computing in the workflow management applications.The main innovative contributions of this thesis are summarized as follows.1. This thesis proposes a process parallel partition method with a multi-leveled master-slave structure.Different from the process partition methods in a centralized workflow with WfMC model, the objective of process partition in a migrating workflow is to support the orderly cooperation among the migrating instances. The parallel partition method proposed in this thesis fragments a process into a set of task-sequences, in which the synchronization tasks are served as the cooperation ports. The master-slave relations among the task-sequences are expressed as a partition tree which can be equivalently mapped into an organization tree of migrating instances after task assignment. Based on the master-slave relations and cooperation ports, the migrating instances can achieve on-demand consultation and orderly cooperation. Compared with the partition approaches without master-slave relations, the partition tree makes the cooperation relations more clearly and thus can support the autonomous cooperation of migrating instances.2. This thesis presents online path planning method for migrating instances based on MDP and uncertain execution environments.Different from the path planning approaches with global execution environments, the key idea of the online path planning method proposed in this thesis is to measure the uncertainty of the execution environment and take actions according to this measurement. Referencing the concept of entropy, this thesis presents an approach to measure the uncertainty of the execution environment and enable a migrating instance to make actions within a planning window that is set based on the execution environment. So compared with the one-step greedy planning strategies, our method can find a way to achieve the satisfactory trade-off between the adaptability to the execution environment and the overall execution performance of the migrating workflow.3. This thesis proposes a POMDP based method for migrating instances partial global path planning and puts forward a group planning architecture.In addition to the process partition method that must support the group cooperation of migrating instances, the other objective of group planning is to improve the execution efficiency of the workflow process. The partial global path planning method proposed in this thesis is modeled based on POMDP, which segments the global planning stages by the synchronization tasks and makes the individual planning within a task frame. Task frames are generated by dividing a task-sequence with synchronization tasks. The group planning assigns the workflow overall goal to the migrating instances and the individual planning focuses on the implementation of the partial goal obtained in the group planning. Compared with non-layered group planning methods, the architecture with cooperation layer and individual planning layer can effectively reduce the complexity of migrating instances group planning and improve the flexibility of individual planning methods.The migrating workflow process partition and planning methods proposed in this thesis have been testified in simulation experiments and application cases. However, the migrating instances group planning is a complex problem, so there are still many aspects to be improved. To further the research started in this thesis, we propose the following future works:1. Methods to online process partition and task clustering. In a complex and changeful environment, a workflow process depends only on the pre-partitioning before execution, the adaptability of the partition granularity is insufficient. So the study of online process partitioning and task clustering will be practically useful. In the future work, we suggest adopting the process partition into the migrating instance online path planning so that a process can be dynamically partitioned on-demand.2. Process partition and planning methods for unstructured workflows. This work is based on structured workflow, so there are still research aspects to be further studied in unstructured workflows, such as unstructured process parallel partition and group path planning. We should further improve on the process partition algorithm and the architecture of migrating instances group planning.更多还原