Research On Process Partition And Planning Methods In Migrating Workflows

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.