迁移工作流是一类基于移动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.非结构化业务过程分解与群体路径规划方法。本文以结构化业务过程为研究对象,而非结构化业务过程分解与群体路径规划问题还需要在本文基础上做进一步的研究,下一步的工作将包括对非结构化业务过程并行分解算法的改进和群体规划体系结构的扩展等。