【作者】 刘菲；

【导师】 曾广周；

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

【摘要】 迁移工作流是将移动计算技术应用于工作流管理的一项新技术。与传统的工作流模型不同,迁移工作流是一个或多个迁移实例在不同的工作位置之间不断迁移,并按照自身携带的工作流说明,就地利用工作流服务协同完成任务的过程。在迁移工作流系统中,工作位置是迁移实例的运行场所,它代表工作流参与者为迁移实例提供安全运行环境和本地工作流服务,工作流服务既可以是参与者的数据资源,也可以是参与者的业务活动或业务子过程。迁移实例是一个以移动agent为范型的智能计算体,它既可以执行良好定义的结构化业务流程,也可以处理不完善的工作流说明,后者不需要在工作流定义时为迁移实例规划所有的活动及其转移关系,也不需要在工作流定义中为迁移实例描述所有可达的工作位置、位置服务、服务规则和服务步骤。工作流说明可以首先基于业务过程的起始信息进行部分定义,然后通过迁移实例执行期间的服务发现、迁移决策及多迁移实例之间的协作进行过程扩展。因此,迁移工作流模型可以大大提高工作流系统对业务过程及其执行环境的动态适应性,特别适合那些因过程规则或执行环境多变而不能完整定义的跨地域、跨机构业务过程管理。因此,关于迁移工作流中的动态适应性研究,就是提出动态适应性方法并建立相应的工作机制,使迁移工作流系统能够在业务过程规则和工作流服务变化时,预测、修正、扩展或重构自己的工作流程,以保证具有不完善工作流说明特征的业务过程,在动态多变的工作流环境中仍然能够被正确执行。迁移工作流中的动态适应性包括多个方面,本文结合国家自然基金课题“面向目标的迁移工作流方法研究”,主要研究了迁移工作流中的过程动态适应性、服务动态适应性和运行环境动态适应性问题。迁移工作流过程动态适应性研究了迁移工作流系统面向目标的迁移决策能力,旨在通过服务发现和优化迁移路径,处理不完善的工作流说明。迁移工作流服务动态性适应性研究了面向目标和基于语义的工作流服务替换机制,旨在避免业务流程因服务不可用或发生变化而中断。迁移工作流运行环境动态适应性研究了迁移实例的协同感知和协同学习能力,旨在弥补迁移实例个体对运行环境变化认知的不足。本文完成的具体工作如下:1.迁移工作流过程动态适应性研究。在迁移工作流中,由于工作流说明的不完善,设计者在初始时没有为迁移实例规划好所有的工作位置,所以要求迁移工作流系统能够根据过程的变化对旅行图作出相应的调整与改变。迁移工作流过程包括业务活动依赖关系和迁移位置有序关系两个方面。迁移工作流系统支持运行中对活动规划(工作流说明)和工作位置规划(旅行图),则系统具有过程动态适应性。文中第三章提出了关于工作位置规划的迁移路径优化算法,该算法对基本遗传算法进行了改进,提出了具有改进的EAX算子和强化变异算子的改进的混合遗传算法,通过实验对比论证了该算法在路径规划方面的性能优于一般启发式方法。工作流引擎根据迁移决策方法动态调整工作位置,并以最优的方案利用资源完成任务,该方法可以通过实例得到验证。通过对迁移域中工作位置状态的判断,再结合优化算法可以实现对工作位置的合理访问,保证迁移实例能够有效地适应不完善的工作流说明,提高了处理业务流程自适应能力。2.迁移工作流服务动态适应性研究。工作位置为迁移实例提供运行时服务(例如迁入、迁出、安全保护等)和工作流服务(例如数据服务、工作项服务、自动调用服务等)。工作位置的逻辑故障异常主要指工作位置提供的工作流服务发生了变化、服务不能按照计划进行或不能产生预期的结果等。如果迁移工作流系统支持对工作位置的逻辑故障异常作出反应和处理,则具有服务动态适应性。关于解决工作位置的逻辑故障异常的方法,文中第四章提出一种服务本体替换机制,在系统运行期间可以动态替换、调整那些出现异常的服务。服务本体替换机制用本体描述工作流服务,若发生工作位置的逻辑故障异常则动态地发现可以替代的服务来执行;如果工作流在运行时,某服务出现服务删除、服务失效和服务操作超时异常等情况时,迁移实例可以使用新服务替换异常服务,保证流程的继续运行。在该机制基础上本文给出了实现方法。使用该机制,不仅可以实现服务发现的自动化还可以提高服务发现的效率。该机制使得工作流程具有变化性,为了调整现有的某个流程,不需要重新设计一个新流程,不仅对现有资源充分利用,更极大地提高了工作流效率。3.迁移工作流运行环境动态适应性研究。工作位置提供迁移实例的运行时环境。通过运行环境,迁移实例能够获取当前工作位置能够提供的服务列表,以及当前驻留在本工作位置的其他迁移实例的信息。工作位置物理故障异常是指位置主机崩溃、网络断连等。如果迁移工作流系统支持对工作位置物理故障异常作出反应和处理,则系统具有运行环境动态适应性。由于异常现象造成迁移实例在运行环境中感知到的信息是一些局部的不完全信息(不确定的工作位置和服务),因此文中第五章研究了在不确定环境下迁移实例的高效、动态和灵活的局部迁移路径规划算法。迁移实例利用从环境中得到的不完全信息进行初步规划,规划出自己针对当前环境的一个可行策略集,然后根据与其它迁移实例的协作以及自己初步规划的策略集进一步进行局部规划。迁移实例在动态运行环境下的规划使得迁移实例的可以适应运行环境下的多种变化,提高系统自适应能力。本文工作的创新点主要体现在:1.提出一种基于迁移路径优化算法的过程动态适应性方法。本文提出一种路径优化算法RMGA,该算法以TSP为数学模型,是一种具有改进的EAX算子和强化变异算子的混合遗传算法,其中一个城市代表一个工作位置。对TSP实例的试验结果可以证明,RMGA算法有更高的运行效率和实际应用价值。这种适应性方法可以对工作流过程进行改进和调整,使得系统具有灵活、动态地处理过程变更的能力。2.提出一种基于工作流服务本体替换机制的服务动态适应性方法。本文结合本体的概念提出迁移工作流服务本体替换机制,使工作流系统在无法得到预定义的服务或资源时,可以寻找可替代的服务或资源继续执行。该机制可以实现服务的自动发现和基于领域本体的服务的动态组合,在领域本体的支持下,以概念相似度为基础,计算服务之间的关联度,然后形成服务组合。3.提出一种基于局部迁移路径规划算法的运行环境动态适应性方法。本文以部分可观察的马尔可夫决策过程(POMDP)作为迁移路线的规划模型,提出一种局部迁移路径规划算法。通过求解不确定性的POMDP得到的近似最优策略,使得工作流系统可以对工作位置物理故障异常进行反应和处理,而不中断工作流的执行。同时给出多迁移实例的协作模型,在求解过程中可以通过多个迁移实例协作完成迁移路径的规划。本文的动态适应性方法在仿真实验中得到了充分的证明,但是迁移工作流动态适应性是一个复杂的问题,因此很多方面还需要改进。本文进一步的主要工作包括:1.迁移工作流过程适应性中过程变更时的正确性的验证,只是依靠过程定义中的验证工具对修改后模型进行验证,其粒度是不够的,在以后的工作中,要进行多层次划分,尽可能的用多层验证来确保变更后模型的正确性。2.为迁移工作流服务适应性方法解决理论上存在的问题,探讨迁移工作流服务变化的语义的和形式化表示方法等。下一步从应用实践中进行总结和归纳,制定出一个丰富全面的服务变化分类体系。3.从迁移工作流运行环境适应性实现的角度上,针对局部最小、反复路径等问题,还需要进一步的研究。下一步的工作将在路径规划算法上进一步改进。在上述研究工作的基础上,我们期望能够对本文中讨论的一些实现方法进行进一步的分析、比较和改进。更多还原

【Abstract】 The migrating workflow is an emerging technology that applies the mobile computing paradigm to workflow management. Different from the traditional workflow model, the migrating workflow is a process in which one or more migrating instances migrate continuously and utilize local workflow service to execute their tasks. In the migrating workflow system, workplace is the running location of migrating instances. It provides safe running environment and workflow services for migrating instances on behalf of the workflow participants. Workflow services are not only the data resources of the participants but also their business activity or business sub-process. A migrating instance is the business process executor, which is modeled from a defined mobile agent prototype. It not only executes well-defined structured business process, but also deals with incomplete workflow explanation. The workflow explanation need not plan all the activities, transfer relations and describe all the accessible workplace, place services, service rules and service steps for migrating instances. Incomplete workflow explanation may be partly defined based on the original information of business process, and be extended by the service finding, migrating decision-making and cooperation between migrating instances. Consequently the migrating workflow model can greatly enhance the dynamic adaptability of business process and executable environment. Especially, the model adapts to those incompletely defined business process management of multi-terrain, mlti-organization caused by the diverse process rules or executing environment.Accordingly, dynamic adaptability of migrating workflow provides the dynamic adaptable methods and establishes corresponding work mechanism for migrating instances and workplaces. It makes the migrating workflow system to forecast, modify and re-construct its flow when business process rules and workflow services are changed. Thus it ensures that the business process with incomplete explanation can be executed correctly in dynamic workflow environment.There are many aspects about dynamic adaptability of migrating workflow. This study is mainly supported by the National Natural Science Foundation of China under "Research on the methods of migrating workflow object oriented". The process dynamic adaptability, service dynamic adaptability and running environment dynamic adaptability of the migrating workflow are mainly discussed. Firstly, the process dynamic adaptability studies the decision-making ability of the migrating workflow system in order to discover and optimize migrating route and deal with incomplete workflow explanation. Secondly, the service dynamic adaptability focuses on the service substitution mechanism that is object and semantic oriented in order to avoid halt of the business process because of the unusable or changed services. Lastly, the running environment dynamic adaptability provides the cooperative apperceiving and learning method of migrating instances in order to make up the cognitive deficiency of environment. The main contributions of this thesis are described as follows:1. Research on process dynamic adaptability of migrating workflow. In the migrating workflow, because of the incomplete workflow explanation, all the workplaces that migrating instance needs are not planed at the beginning. So the system must adjust Itinerary graph according to the the change of the process. If the migrating workflow system is provide with the ability that may plan activities and workplaces during flow running, it has process dynamic adaptability. Chapter 3 presents an object-oriented migrating decision-making method. Improving on the basic genetic algorithm, this method provides an improved hybrid genetic algorithm with enhanced EAX operator and reinforcement mutation operator. Large experiments on TSP instances show that this method outperforms other heuristic methods in route plan. Based on this method, the migrating instance can dynamically adjust its workplaces and complete the task with the excellent use of resources. This method is validated in the environment of migrating workflow and shows that the workplace may be reasonable adjusted to enhance the self-adaptation ability of business process.2. Research on service dynamic adaptability of migrating workflow. The workplace provides running service (such as migraing in, migrating out, safety protection and so on) and workflow service (such as data service, automatically transfer service and so on). The workplace logic abnormity mainly denotes that the workflow service that the workplace provides is changed, is not carried through according to a plan or is not produced expected results. The workflow service dynamic is that when a service is not accessed casually another equivalent service may be found and substituted to complete the same task. Chapter 4 presents a service ontology substitution mechanism based on the description of ontology and provides a flexible migrating workflow system framework. When the migrating instance finds that the service is changed, it may find substituted service to execute. When service deletion, service invalidation, and service overtime or service abnormity appear, the migrating instance may substitute a new service for exceptional service to ensure the continuous execution of workflow. This mechanism makes the workflow changeable, namely that in order to adjust the existing flow it need not redesign a new work folw. Thus the resources can be made the best use and the workflow efficiency can be enhanced greatly.3. Research on running environment dynamic adaptability of migrating workflow. The workplace provides a running environment to the migrating instance, in which the migrating instance can obtain a service list that the current workplace may provide and the information about other instances that rest on the same workplace. If the migrating workflow system may response and deal with those abnormity brought by workplace physical fault, it poses the ruuning environment dynamic adaptability. Because above abnormity, in the running environment the migrating instance apperceives some partly incomplete information. Chapter 5 investigates a planning model and an efficient, dynamic and flexible method which makes the migrating instance to possess partly perceptive, competitively cooperative and self-learning abilities. The migrating instance makes use of this incomplete information to make an initial plan and obtains a feasible strategy set. Afterwards, the migrating instance obtains the recent information of its fellow. According to this information and its initial planned strategy set, the migrating instance makes incomplete global plan. The planning method of the migrating instance makes the migrating instance to adapt to multiform changes and enhances the self-adaptive ability of the system.The main innovative contributions of this thesis are:1. This thesis proposes a process dynamic adaptability method based on optimized planning algorithm of migrating rout. This method is based on the traveling salesman problem (TSP) model in which a city denotes a workplace, and then a hybrid genetic algorithm RMGA with improved EAX operator and reinforcement mutation operator is proposed. The core of RMGA lies in the using heterogeneous paring selection instead of random paring selection in EAX and the construction of reinforcement mutation operator, named RL-M, by modifying the Q-learning algorithm and applying it to those individuals generated from modified EAX. The experimental results show that RMGA outperformed the known genetic algorithm in the quality of solutions and the running time. Based on the heuristic transcendent knowledge, the system dynamically plans the migrate route using this method.2. This thesis proposes a service dynamic adaptability method based on workflow service substitution mechanism. This method incorporates knowledge ontology to provide a service ontology substitution mechanism. This mechanism makes the migrating instance to find substituted service or resource to continually execute when preconcerted service or resource cannot be obtained. This thesis also provides a method that can realize this mechanism in the migrating workflow model. The ontology substituting mechanism may realize automatic service-finding and the service dynamic combination based on domain ontology. Under the support of the domain ontology and the base of similarity measurement in ontology, the relevancy measurement between services is computed and service combination is formed.3. This thesis proposes a running environment dynamic adaptability method based on local planning algorithm of migrating route. In the running environment, the migrating instance apperceives incomplete information. So the environment may be modeled by partially observable Markov decision processes (POMDP). On this condition a local route planning algorithm algorithm is provided to solute such uncertain POMDP approximately optimal strategy. The certain limited historical information of the migrating instance is kept and incorporated with the belief state--probability distribution over all of the possible states to decide the optimal strategy. The validity of this method is validated through the simulation on the instance of migrating workflow.The dynamic adaptability of migrating workflow that this thesis proposes has been testified in emulational experiments. But the dynamic adaptability problem is complex, so there are many aspects to be improved. Since the migrating workflow is an emerging workflow research field, it is far from mature in both theory and applications. To further the study started in this thesis, the author proposes the following future works:1. The correctness validation in workflow process alteration only depends on the tool of process definition, but its granularity is insufficient. So multilayer partition and multilayer validation of the modified process model should be made to ensure its correctness.2. Some theoretical problems of service adaptability should be solved, such as the semantic and formalized methods of the migrating workflow service variety. Next, we should summarize and conclude from application practice in order to establish a general classified system about service variety. 3. From the point of view of the running environment adaptability implementation, the problems of local least path and repeat path should be further investigated. We should further improve on route planning algorithm.Based on above investigation work, we hope to make a further analysis, comparison and improvement.更多还原