【作者】 杨公平；

【导师】 曾广周；

【作者基本信息】 山东大学 ， 计算机软件与理论， 2007， 博士

【摘要】 工作流是业务过程的全部或部分自动化，在此过程中，文档、信息或者任务按照一系列过程规则在不同的参与者之间流转，实现组织成员间的协调工作以期达到业务的总体目标。移动agent计算是一种全新的分布式计算模式。移动agent具有智能性，可以自身携带任务说明，在站点之间迁移，并利用当地资源执行一项或多项任务。因此，移动agent计算模式具有可以减少网络负载、支持网络断连的计算环境等许多优点，成为分布式计算研究的一个新热点。迁移工作流是将移动agent计算模式应用于工作流管理的一项新技术。按照曾广周教授提出的迁移工作流管理系统框架，构成迁移工作流管理系统的三要素是迁移实例、工作位置和迁移工作流管理引擎。迁移实例是以移动agent为计算范型的业务过程执行主体，多个迁移实例可以协作地完成一个业务过程。工作位置代表工作流的参与者，例如一个企业或机构。物理上，工作位置由停靠站服务器及其关联的工作机网络组成，其中，停靠站服务器是迁移实例的运行场所，工作机为迁移实例提供具体的工作流服务，包括计算服务、数据服务和人机交互服务等。迁移工作流管理引擎负责工作流过程定义、工作位置组织、迁移实例创建以及工作流监控等。通常，迁移工作流管理是发起工作流的那个企业或机构的工作流职责。与传统的工作流模型不同，迁移工作流是一个或多个迁移实例在不同的工作位置之间不断迁移并就地利用工作流服务完成任务的过程，因此，迁移工作流研究所要解决的关键问题之一是如何规划迁移实例的工作位置。本文把满足某个特定业务流程需求的所有工作位置的集合称作一个工作流域。如果工作流域可以在工作流启动之前确定，并且在工作流执行过程中域成员关系不再改变，则称这种组织方式为工作流域的静态组织模式。如果在工作流启动之前，仅可以确定工作流启动所需要的部分域成员关系，而剩余的域成员关系需要在工作流执行过程中通过其他手段添加，则称这种组织方式为工作流域的动态组织模式。迁移工作流模型是一个并行计算模型，它既允许同一个业务流程中的多个迁移实例并行执行，也允许一个企业或机构同时参与多个业务流程，不同的业务流程由隶属关系不同的迁移实例集合并行完成。这样，在某个时间段，就可能会有多个迁移实例到达同一个工作位置，并由此导致多个迁移实例对同一工作位置服务资源的竞争。无序竞争影响工作位置主机的稳定性，严重情况下可能导致迁移实例夭折，甚至整个迁移工作流系统失败。因此，迁移工作流模型研究所要解决的另一个关键问题是如何使工作位置对多迁移实例的服务有序和高效。本文把工作位置为迁移实例提供有序和高效服务的措施称作工作位置上的迁移实例调度机制。本文在国家自然科学基金项目的资助下，以曾广周教授提出的迁移工作流系统框架为基础，吸收其他领域的研究成果，在对工作流域组织模式分类的基础上，重点研究了工作流域组织模式的实现方法和工作位置上的迁移实例调度机制等问题，并在原型系统上对研究成果进行了验证。本文的主要工作包括：1．工作流域静态组织模式的实现方法研究。工作流域静态组织模式的实现可以抽象为一个借助结盟的工作流任务分配问题。工作流联盟一旦形成，就不仅可以确定允许迁移实例登陆的工作位置集合，而且可以基于业务流程逻辑和联盟成员提供的工作流服务为迁移实例制订旅行图。本文重点研究了一类基于能力置信度结盟的任务分配方法，其中，能力置信度指工作流组织者相信加盟者胜任工作流服务的程度。如果一个企业或机构相信自己有能力为业务流程的执行提供一项或多项服务，那么它就可以竞争工作流域中的某个角色。如果工作流组织者相信某个竞争者能够最佳胜任某项任务的工作流服务，那么该竞争者就会成为工作流域的一个成员。研究假定所有企业或机构都是理性的，竞争是合作型的。文中第2章给出了服务能力置信度的定义及其计算方法，设计了基于服务能力置信度的任务分配算法，并结合协同产品商务应用进行了验证研究。2．工作流域动态组织模式的实现方法研究。对于某些非结构化业务流程，例如ad hoc工作流，事前定义一个完整的业务过程说明是困难的，致使迁移实例缺乏完整的工作计划和旅行图。因此，与工作流域静态组织模式的实现不同，工作流域动态组织模式的实现可以抽象为一个迁移实例面向目标的旅行规划问题。本文重点研究了一类基于工作位置导航的迁移实例旅行规划方法，导航是工作位置根据自己关于业务过程的局部知识引导迁移实例执行任务的行为。迁移实例可以根据旅行建议在目标不变的前提下修订自己的工作计划，并选择相应的工作位置。文中第3章定义了导航索的概念，建立了迁移工作流导航模型，描述了基于导航的迁移实例任务执行过程，并结合协同产品商务应用进行了验证研究。3．工作位置上的迁移实例服务调度机制研究。工作位置是停靠站和工作机网络的复合体，它代表工作流参与企业或机构为业务流程中的一项或多项任务提供工作流服务。工作位置上以冲突消解和优化服务为目标的迁移实例管理，可以抽象为一个迁移实例服务调度问题。本文重点研究了一类迁移实例排队机制与工作机优选机制，其中，排队机制主要解决多个迁移实例在同一工作位置上使用同一工作流服务带来的稳定性与可靠性问题，工作机优选机制主要解决当有多台工作机能提供同一工作流服务时，如何选择更合适的工作机。文中第4章首先建立了单工作节点排队模型和复合工作节点排队模型，给出了模型实现方法，然后基于模糊决策原理，设计了工作机的优选算法，并结合协同产品商务应用进行了验证研究。4．迁移工作流状态监控方法研究。在迁移工作流管理系统中，迁移实例是任务执行主体并且不断地变化其物理位置。因此，迁移工作流状态监控的核心问题是迁移实例的状态监控，其中迁移实例位置追踪是必须解决的关键问题。本文重点研究了一类基于GSM网络通讯思想的迁移实例位置追踪方法，并针对迁移实例状态，设计了一种临时存储与永久存储相结合的运行日志管理策略。文中第5章设计了迁移实例的位置追踪方法，定义了迁移实例临时携带存储、迁移节点与创建节点永久存储相结合的日志存储策略，并给出了迁移实例运行日志存储、检索、验证等过程。本文工作的创新点主要体现在：1．提出了一种基于能力置信度结盟的任务分配方法。该方法视参与工作流的企业或机构为理性agent，把工作流域的静态组织问题映射为借助结盟的多agent任务分配问题，能力置信度通过业务操作ECA规则集合和agent服务能力ECA规则集合定义。如果理性agent相信自己有能力为操作A提供服务，则称agent关于A自信。如果理性agent X相信理性agent Y有能力为操作A提供服务，则称X关于Y信任。自信和信任统称为置信。由于自信和信任都是行为抉择者的心态元素，因此，基于能力置信度结盟的任务分配方法，较之假定agent具备完全能力的基于利益结盟的任务分配方法，例如协同博弈方法等，不仅可以细粒度地刻画行为者能力，而且可以揭示行为者基于能力解决问题的心智属性。2．提出了一种基于位置导航的迁移工作流执行方法。该方法假定迁移实例有明确的工作流目标，但缺乏完整的业务过程说明和迁移路线，因而需要借助工作位置提供的导航建议(导航索)，动态地规划任务并实施迁移。导航索是一类工作位置关于业务过程的局部知识，用有向图G=(V，E)表示，其中，顶点表示服务，每项服务对应一项具体的工作流任务并关联相应的服务位置，边表示服务间的偏序关系。与传统上通过建模提高工作流柔性的方法不同，导航机制利用分布在工作位置上的工作流知识提高迁移实例执行任务的灵活性。这种多知识源导航系统，不仅使得迁移实例可以在业务过程说明不完备的状态下启动工作流，易于处理工作流例外，而且使得工作流柔性不再完全依赖工作流设计者的先验知识，因而特别适合跨组织的非结构化工作流管理。3．提出了一种基于排队论的迁移实例服务冲突消解方法。该方法根据工作位置物理上由停靠站和工作机网络组成的特点，分别建立了单工作节点排队模型和复合工作节点排队模型。排队模型用迁移实例到达排队系统的时间分布和节点上每个服务台的服务时间分布共同刻画，并按照服务规则通过动态优先队列调度迁移实例。单工作节点排队指迁移实例在停靠站上的排队，复合工作节点排队指停靠站根据迁移实例需求派遣它到合适的工作机上排队。虽然排队是一种朴素的服务思想，但在移动计算领域，却鲜有研究，而对于工作流管理来说又特别重要，这是因为资源竞争会导致主机运行不稳定，严重时可能导致迁移实例夭折，甚至工作流失败。鉴于迁移工作流是一个新兴的工作流研究领域，无论是理论研究还是应用研究都还远未成熟，本文进一步的主要工作包括：1．基于多目标决策的工作流静态组织方法研究。当同时考虑自信、信任和成员利益分布时，借助结盟的任务分配是一个多目标决策问题。如何基于多目标决策实现工作流域的静态组织模式，是本研究进一步的努力方向之一。2．导航索语义及其辨识研究。在基于导航的迁移工作流执行方法中，导航索的质量直接决定着迁移工作流系统的可靠性和正确性。如何在更高的语义水平上描述、辨识和评价导航索，是本研究需要进一步解决的另一个问题。在上述工作的基础上，下一步还要在迁移工作流事务属性、多迁移实例协同工作、基于语义的服务发现和组合等方面继续开展工作。更多还原

【Abstract】 A workflow is the automation of procedures where documents, information or tasks are passed between participators according to a defined set of rules to achieve, or contribute to, an overall business goal.The mobile agent computing is a new distributed computing paradigm. A mobile agent is an intelligent entity that can carry the task specification, migrate between sites, and utilize local resources to execute one or more tasks. Since the mobile agent computing has many advantages, such as cutting down network overload and supporting unstable computing environment, it is becoming a hot topic in the distributed computing paradigm research.The migrating workflow management is an emerging technology that applies the mobile-agent computing paradigm to workflow management. According to the framework of the migrating workflow management system proposed by professor ZENG, there are three core elements in a migrating workflow management system: migrating instance, workplace and migrating workflow engine. A migrating instance is the business process executor, which is constructed from a defined mobile agent stereotype. The migrating instances cooperate with one another to accomplish a business process. Workplaces are delegates of the workflow participators, such as an enterprise or organization. A workplace is composed of an anchorage server and its connected workstation network. Migrating instances run on the anchorage server, and the workstations provide actual workflow services for migrating instances. The workflow services may include computing service, data service, human computer interaction service, and so on. The migrating workflow engine is responsible for workflow process definition, workplace organization, the creation of migrating instances and workflow monitoring. Generally speaking, it is the function of the enterprise or organization that triggers the workflow process to manage the migrating workflow. 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. The workplace layout is one of two key issues in the migrating workflow research. This thesis defines a concept of workflow domain, which is the sum of all workplaces that fulfills the requirements of a given business process. If a workflow domain is configured and fixed before the workflow startup, and the workflow membership does not change during workflow execution, it is named as a static organization workflow domain. If the workflow domain membership can be changed during workflow execution, it is called dynamic organization workflow domain.The other key issue in the migrating workflow research is how to keep the workplaces to offer efficient services in a well-ordered manner. This is called the migrating instance scheduling mechanism. The migrating workflow is a parallel computing model. It not only permits multiple migrating instances to execute on the same business process, but also does it allow an enterprise or organization to take part in multiple business processes. Each business process is executed by its set of migrating instances. As a result, multiple migrating instances may arrive at the same workplace at a time, which can cause two or more migrating instances to contest for the resources from a workplace. Anarchism in resource competition not only tampers with the workplace stability, but also results in abnormal execution of the migrating workflow system.This study is mainly supported by the National Natural Science Foundation of China under Grant No.60473123, based on the migrating workflow framework proposed by professor ZENG This thesis absorbs the research results of relevant fields, focuses on the implementation method of the workflow domain organization model and the scheduling mechanism of migrating instances in workplaces. The study has also built a prototype system to validate the conclusions. The main contributions of this thesis are described as follows:1. The static organization model of the workflow domains and its implementation. The static organization model implementation can be abstracted as the workflow task allocation mechanism through coalition formation. Once a workflow coalition is formed, the workflow creator can not only determine the set of workplaces on which a migrating instance may login, but also map out the travel schemes for those migrating instances based on the business process logical and workflow services provided by individual coalition members. The author has focused on a task-allocation based ability-confidence coalition, where the ability confidence is defined as the level of belief that a workflow creator trusts each coalition member on providing particular services. If an enterprise or organization believes itself have the ability to provide one or more services for certain business process, it can contest some role of the workflow domain. If the workflow creator believes a competitor is competent for a service task, it enlists such a competitor as members of workflow domain. Our research assumes that all enterprises or organizations are rational, and the contest is cooperative. Chapter 2 presents the service ability confidence definition and its calculation, and then develops a task allocation algorithm based on the ability confidence, which is validated in the environment of Collaborative Product Commerce.2. The dynamic organization model of workflow domains and its implementation. For some unstructured business process such as an ad-hoc workflow, it is impractical or unnecessary to define a complete business process description or construct a whole workflow domain for the business process. In contrast to the static model implementation, the dynamic model can be abstracted as a goal-oriented travel layout problem. The author has studied a workplace-navigation based travel layout method, where the navigation indicates travel suggestions for migrating instances provided by a workplace per its service ability comprehension of the workflow domain participators including it self. Following the navigation suggestions, a migrating instance can, without changing it goal, amend its work plan and choose its workplaces. Chapter 3 defines the concept of a navigation thread, creates the migrating workflow navigation model, and then develops a navigation-based migrating instance task execution algorithm. Chapter 2 also validates this research in the environment of Collaborative Product Commerce.3. The migrating instance scheduling mechanism within a workplace. A workplace is the integration of an anchorage server and its connected workstation network, where the anchorage server is the place for migrating instance execution, and the workstation is a workflow service executor. The workplace, as a delegate of the enterprise or organization attending the workflow, provides workflow services for one or more tasks in the business process. When more than one migrating instances login the same workplace, there may be resource contests. The migrating instance scheduling mechanism can be abstracted as a workflow service decision-making problem. This thesis emphasizes on a migrating instance queuing mechanism and workstation preferential choice mechanism. The queuing mechanism helps maintain the stabilization and reliability when many migrating instances utilize the same workflow service on the same workplace. And, the workstation preferential choice mechanism is used to choose the best suitable workstation when many workstations can provide the same workflow service. Chapter 4 first constructs the sole-work-node queuing model and the compound-work-node queuing model, proposes the implementation methods of these models, and then designs a workstation preferential choice algorithm. And finally, the above research is validated in the environment of Collaborative Product Commerce.4. The monitoring and management of migrating instances. In the migrating workflow system, the migrating instance is the mobile computing entity, which may lie in different physical places at different times. So the key issue of migrating instance monitoring and management is how to trace migrating instances. This thesis mainly studies a migrating instance tracing method based on GSM network principles, and designs a running log management policy that combines the dynamic transient storage and persistent storage. Chapter 5 defines the concept of migrating position trace, designs the migrating instance trace method and its log storage policy, and further discusses the procedures of log storage, search and validation.The main innovative contributions of this thesis are:1. The thesis proposes a task allocation method based on ability confidence coalition. This method takes attending enterprises or organizations as rational agents, maps the workflow domain static organization problem into a coalition-based multi-agent task allocation problem. The ability confidence is deduced from ECA role sets of business operation and agent service ability. If a rational agent believes it is capable to provide service for operation A, we say this agent is self-confident with operation A. If a rational agent X believes rational agent Y is capable to provide service for operation A, we say agent X trusts agent Y. We measure both self-confidence and trust as confidence. Because both the self-confidence and trust are mental elements of an action selection agent, compared with profit coalition based task allocation methods, such as the collaborative gaming, that sets absolute abilities to agents, the task allocation method based on ability confidence coalition not only provides a finer actor ability description, but also opens out the intelligence attribute of actors solving problem based on its ability.2. This thesis proposes a workplace-navigation based migrating workflow execution method. This method assumes that each migrating instance has its specific workflow goal, but it is lack of the whole business process description and migration route, so it needs navigation suggestions (a.k.a. navigation thread) provided by workplaces to layout tasks dynamically and help accomplish migration. A navigation thread is the workplace’s local knowledge about business processes. The navigation thread is described as a directional graph G=(V, E), with each vertex denotes a service, and each edge denotes the sequential relationship between two services. Note that, each service is corresponding to a concrete task and a workplace in which migrating instance use this service to execute the task. Compared with the traditional approach to improve workflow flexibility through workflow modeling optimization, our proposed navigation mechanism utilizes the workflow knowledge distributed in all workplaces to maximize the flexibility of migrating instance executing tasks. This multi-knowledge source navigation system enables migrating instances to start the workflow under the status of incomplete business process description, which makes it very easy to deal with workflow exception. What’s more, this navigation system also makes the workflow flexibility no longer absolutely relying on the foregoing knowledge of workflow designers, thus this method is very suitable to non-structural and inter-organizational workflow management.3. This thesis proposes the queuing-theory based migrating instance service collision resolution method. Considering that a workplace is physically composed of an anchorage server and its connected workstation network, the service collision resolution method establishes the queuing models for sole-work-nodes and compound-work-nodes respectively. Taking into account the time at which a migrating instance arrives at the workplace and the service time, these queuing models schedule migrating instances through a dynamic preferential queue according to service rules. The sole-work-node queuing indicates that migrating instances queue up at workplaces, and the compound-work-node queuing indicates that an anchorage server dispatches migrating instances to queue up at workstations. Although the queuing is a simple idea, it is rarely used in the mobile computing research. However, it is very important to the workflow management because resource contests may cause instability of work nodes, migrating instance abortion, or even the whole workflow failure.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 multi-goal decision-making based workflow static organization method. When all self-confidence, trust, and profit are considered at the same time in terms of coalition, the task allocation problem becomes a multi-goal decision-making problem. How to implement the workflow domain static organization model based on multi-goal decision-making, will be one of the topics justified for in-depth discussions.2. The navigation thread semantics and its judgment. The quality of the navigation thread directly dictates the reliability of a migrating workflow system and the validity of the navigation-based migrating workflow execution method. How to describe, distinguish, and evaluate the navigation thread at the higher level of semantics will be another future tasks to fulfill.Based on aforementioned work, research areas such as migrating workflow transaction attribution, multi migrating instance cooperation and semantics-based service detection and combination, should also be explored.更多还原