当前工作流管理中，业务流程执行的可靠性是一个不容忽视的重要问题，然而，现有的研究在解决多主体协调并发执行过程中的主体夭折问题存在不足。基于迁移工作流模型，提出一种多迁移实例的可靠执行模型，模型可以实现不同层次上的执行主体监测与故障诊断和处理；同时设计守护实例具有可移动、可复制以及自动退出等特点，有效提高了检测准确性和监控效率。实验表明，模型具有高可靠性和低开销以及可扩展性等技术优势，特别适合当前跨机构环境中多主体的并发执行。卢朝霞:多主体业务流程的可靠执行模型2012,48(26)3多迁移实例业务流程执行模型定义4一个守护M=(MonD,Type, ParentMon,3.1模型描述Childmons, Monlistlink,SM,MC),其中:基于上述分析,多迁移实例执行的业务流程有Monad是守护实例名字如下特点:(1)多层次并发性,业务流程分为机构间Type是守护实例类型,有两种: OutMan和In发生和机构内发生两个层次,派遣不同类型的迁移lon, OutMan表示机构间守护,监控Omi类型迁移实实例分别执行,层内迁移实例也有可能根据任务执例的执行,nMon是机构内守护,实现对Mi的守护行的需要派生新的迁移实例,从而形成不同层次的执行。迁移实例并发执行同一工作流的形式;(2)动态性,ParentMon记录其前驱守护的信息,包括其名迁移实例具有自主执行能力,它可以根据需要创建,字、地址以及类型等,对 OutMan来说是其创建者而并在完成任务后退出因此执行同一业务流程的迁对 InMon来说就是委托者所属的那个 OutMan,称此移实例的数目、位置、状态、关系都是动态变化的。 OutMan为委托守护。针对上述特点,本研究对不同层次的迁移实例派造Childmons记录其后锉守的信息,如果是 OutMan,相应的守护实例,保障其可靠执行,从而形成一种多则为其产生的子守护,如果是mMon,此项为空。执行实例和守护实例并存的执行树模型:迁移工作Monlistlink是指向其守护列表 Montlist的指流执行模型 METM(a monitor and Execution Tree针,守护列表中存放的是所守护的迁移实例的有关or Migrating- work llow)。其定义如下:信息,如名字、版本号、创建者、迁移历史路径以及存定义2一个METM是一个四元组,METM=活时钟,如果是 Inmon,还会包含当前参与 atomic ac(wid, Mon set,Mtre, MISet,R&S),其中tion的信息栈ACS等。wid是迁移工作流唯一标识。SM={p,Tol,s}是守护实例的状态机,包括其当Mon set=={M,M,…,M-}是所有守护实例的前所处的位置p,其生命周期Tol,以及其当前状态s集合。MC是M的工作机,实现新守护实例的派遣、守Mte为守护实例之间的关系树(见定义3)。护实例之间的协调、守护列表的维护、迁移实例存活MISe={ OMiSet,MSet}是所有迁移实例的集状态检测。合, OMiSet是所有机构间迁移实例的集合, IMiSet是一个迁移工作流在执行期间,可能产生多个Out所有机构内迁移实例的集合。Mon,这些 Outman按照创建关系可生成一棵树,其R&S-Mrea,mfMm, Abordisp是管理规则与根为M,每个OuMm负责一个或多个OM存活状策略,其中, Mela守护实例维护机制,如守护实例的态的监控,个OMi的执行过程就是不断地在各个创建移动退出等, InfoMan信息管理机制,如状态机构间迁移并请求服务的过程,当OM迁移到某个信息的获取、检测与维护, BordIsm迁移实例天折处机构H的停靠站上请求服务时,H为其创建执行服务理机制等。的IMi列表:{Mi,IM,…,IMin},同时创建一个In定义3守护实例之间的关系可以描述为一棵跨Mon守护这些迁移实例。mMon在执行过程中可以越两个层次的树:Mre它描述了迁移工作流wd在一直驻留在停靠站上,也可以迁移到守护对象所在运行的某一时刻T,所有守护实例之间的关系,这种的某个子网络的ever上进行本地化监控。当服务关系满足以下条件:执行完后,所有为此服务而创建的迁移实例退出,I(1)有且仅有一个节点M,在关系Mtee下无前Mon完成任务,通知OuMn后退出。如图3为在工驱,称为守护实例树的根,M守护MI;作流执行的某一时刻T,所有守护实例间的关系。(2)除节点M外, Mtree中每一个节点N都有且D OutMan仅有一个前驱P∈ Monset,P守护的迁移实例中有/。 InFor且仅有一个是N守护的迁移实例的父实例(父子关跨机构层创建关系委托关系系)或源迁移实例(委托关系);(3)Mrcc中任一节点N,如果N有后继节点Q,则Q守护的迁移实例必是N守护的迁移实例中某个的子迁移实例(父子关系)或副本迁移实例(委托机构内层关系)。图3T时刻所有守护实例之间的关系图2012,48(26)Computer Engineering and Applications计算机工程与应用32守护执行过程描述①如果MI为OMi,则向M所在停靠站发送连接下面以OMi为例描述其守护执行过程信号,如果成功,说明通信链路正常,MI夭折,转(4);每个OMⅰ在创建时随身携带其守护实例M的否则,说明链路中断,M所在网络有可能被分割,不地址,每隔一定的时间 timeout,OMi向M发送“ alive”能确定M的存活状态,则M等待直至收到MI发来消息,确认自己的存活状态;同时OM还具有一个生的下一个“aive”消息(M冇活)或 timetolive时间耗存能量值 timctolivc,它可以设置为随时间或经过的(判定M天折,转(4)节点数递减,当 timetolive减到0,OMi要向M请求补②2如果MI为M,则直接可判断M夭折,转(4)。充能量值,同时将自己的有关历史信息交M保存。(4)M根据设定的夭折处理策略,做相应处理在守护实例M一端,每次收到OM的“aive”消如可以恢复迁移实例,也可以不恢复,下面是恢复迁息,将启动一次 timeout计时;同时,如果M收到OMi移实例的处理发来的补充能量请求,首先检查OM的合法性,如果①根据M的历史记录进行恢复,创建M继续合法,则赋予其最大的 timetolive值,使OM继续完成完成余下的任务。余下的任务;如图4描述了对守护信息的处理。②2向上层守护发送消息,包含(MI,M,M'),上层守护将消息转发至Ml,实现其子迁移实例的版本MessageHandler(Msg mes)更新。omi=mes.from;/提取消息发送者③向MI的子迁移实例的守护发送 updateMIMsg,wite实现父迁移实例的版本更新。/根据消息类型做不同处理④检查MI对应的 atomic action栈,如果栈不空{case“aive”:γ*发确认消息同时启动相应omi则弹出栈顶,即(MI,A11,(MI,MI2),通知MI和的 Timeout计时*send(omi, Okmsg);MIl2取消活动A11;继续弹出栈顶元素,通知MIx和startTimer(omi, Timeout);Ml2取消活动A1,直至栈空为止。case¨ ttIrequest’/*验证此申请的有效性并发确认消息赋予omi最大 Timetolive值5模型特性分析与性能评价validCheck(omi)5.1模型特性分析setTTL(omi, Timetolive)上述模型满足以下两个性质:scnd(omi, ttlAsigMsg)break性质1机构内迁移实例夭折可在 timeou时间内检测到图4守护消息处理算法模型采用一种非常简单的检测机制,由迁移实例每隔 timeout的时间向监控者发送"“ alive"消息,同4一个例子迁移实例夭折监测与处理过程时守护为每个迁移实例计时。因为网络为可靠连假设迁移实例MI,其父迁移实例为MI,其子迁接,即如果” alive”消息被发出,则守护一定可以收到移实例分别为MI,MI2,MI3,其守护实例为M,如果如果超时,则守护可判断迁移实例夭折。MI参与 atomic action(为MM时),则活动名为A1,嵌性质2机构间迁移实例夭折最长可在 timetolive套活动名为A11,共同参与A1的迁移实例还有MI,时间内解决MI2,共同参与A11的迁移实例还有MI,M2。假设如果网络连接不可靠,则当 timeout超时,守护不底层通信是基于有连接的通信协议如TCP,跨机构间能判断迁移实例天折,囚为有可能链路中断造成网终连接不可靠,机构内网络为可靠连接¨ alive”消息无法发出,此时守护会首先测试与迁移实(1)M每隔时间 timeout向M发送“ alive”消息,例所在主机的链路是否畅通,如果杨通,则可判断为如果是OMi,同时每隔 I timetolive向M申请生存能量。迁移实例天折,合则判断迁移实例为不可知状态,对(2)如果M参与活动AM发 EenterActionMsg,此情况的处理,模型为避免造成重复执行,采用乐观则相应的M将(MI,A1,(MI1,MI3))入栈ACS,当MⅠ的办法,不立即使用新迁移实例替换夭折的,而是假进入A11,向M发送 cntcrActionMsg,(MI,A1l,定迁移实例并未夭折,继续等待 timetolive的时间,如(MI,MI2)入栈ACS。果在此过程中,链路恢复收到迁移实例发来的” alive”(3)守护者M每隔一定的时间检查其守护对象消息,则恢复正常监控状态;合则判定迁移实例巳天timeout值,如果为0,则根据Ⅶ的类型做相应的处理:折,执行夭折处理,此时即使M存活,也会因申请不卢朝霞:多主体业务流程的可靠执行模型2012,48(26)到生存能量而夭折,因此不会发生两个迁移实例执行程度越高,需要的守护的数目越少,守护的维护开行同一任务的情况销越小,较前三种方法,METM方法对高并发性有更因此,守护可以准确地检测到迁移实例的执行好的支持。失败,并在·定时间内得到处理,且可以保证执行的假设迁移实例的生命周期为T,“live”消息的发exactly once”特性,避免二次执行导致的系统状态送周期为t,生命能量周期为tl,参与的 atomic action的不一致。个数为a个,平均每条消息的传送开销:METM模型5,2性能评价为C1,CE模型为C2,RD模型为C3,假设传送同样为了验证模型的有效性和效率,在已开发的迁的信息,则不同模型下产生的平均通信开销为:移工作流平台上对其进行了模拟实验。实验在不同TT凊况下执行模拟的测试流程,在执行过程中通过预METM2(2)t Itl设的参数或者人为干预仿真环境下的异常事件或状E=n,C2(+x+2a)(3)态,观察并记录流程执行情况,如图5为在不同情况其中,n为执行同一业务流程的迁移实例总数。下工作量执行的故障率比较。实验显示,无任何异1.C2(T,T⊥2a)+(4)常处理(None)情况下故障率最高,其次为加载迁移RD实例异常处理(EH)的情况,加载守护实例(METM)其中,r为物理上存在的域的数目的情况下模型故璋率明显下降。METM是跟踪监测,但不能保证是在同一个局域网内,而RD方法完全在局域网内的监控,因此0.30NoneC3≤C1≤C2,实验仿真设计在不同执行规模下,由守0.25EH护向其辖域内的守护对象发送通知消息,假设通信0.20可靠,并且不会发生执行主体夭折的情况,统计每种四0.15执行模式下产生的平均通信量,可以得到如图6所示的结果实验表明MEM模型能够动态调节通信产4生的开销,而且通过分担对迁移实例的监测任务使0.05每个守护的通信量控制在合理的范围内,不致造成性能瓶颈。2030MI数量250图5工作流执行故障率比较一一METM200RD通过与其他技术的比较考察了守护实例的维护trcE1≤0和通信开销。现有的移动主体执行守护机制的可分100为如下几种类型:(1) Centralized(CE):集中式的,每个业务流程分0配一个守护,NOM=1。0(2) Fully-Distributed(FD):完全分布式的,每个MI数量移动主体有m(m≥1个守护。如果执行一个业务流图6不同方法通信开销比较程的迁移实例共n个,则其守护总数NOM=mn。结论(3) Region- based- Distributed(RD):基于域的分以迁移工作流为背景,提出一种多执行主体执布式,每个物理划分的域设置一个守护,即其守护的行业务流稈的可靠执行模型,模型针对迁移实例的数目是固定的。NOM=C(C为域的数目)。运行环境与执行特点,实现不同层次上的监测与故(4)MEIM模型:假设迁移实例总数为n个,每个障诊断和处理;同时模型设计的守护执行模式,有迁移实例最多可派牛或克隆d个子迁移实例则守护效提高了执行效率和检测准确性,降低了监测带来的数目为:的通信及管理等额外开销。初步实验表明,模型具f()=2+d+a2+…+d0%0+(1)有高可靠性和低开销以及可扩展性等技术优势,适固定式(1)中的n的值,∫(ω的值随d值的变化合当前跨机构环境中多主休的并发执行。下一步的而变化,d越人,∫(ad)越小,说明迁移实例的并发执研究将进一步考虑环境的复杂性和动态性,完善算102012,48(26)Computer Engineering and Applications计算机工程与应用法,并将设计更多的实验案例,做深入的定量分析,tomation Engineering( CSAE), 2011: 53-57进一步完善和改进模型。[6 Zeghache L, Badache N Optimistic replication approachfor transactional mobile agent fault tolerance[C]proc参考文献:of llth acis International Conference on Software En-[1 Georgakopoulos D, Hornick M, Sheth A. An overview ofgineering, Artificial Intelligence, Networking and ParallelDistributed Computing, SNPD2010, 2010: 193-198workflow management: from process modeling to workflow automation infrastructure. Distributed and Parallel[7 Jamali M A J, Shabestar H E.A new approach for a faultDatabases. 1995.3:119-153tolerant mobile agent system[ C]/Proc of 12th ACIS In-[2 Kotb Y T, Beauchemin SS, Barron J L Workflow nets forternational Conference on Software Engineering, Artificialmultiagent cooperation[J]. IEEE Transactions on AutomaIntelligence, Networking and Parallel/Distributed Computingtion Science and Engineering, 2012. 9(1): 198-203(SNPD),2011:133-138[3 Czarnul P, Matuszek M, Wojcik M, et al. Beesy Bees-efficient8 Nichols J, Demirkan H, Goul M. Autonomic workflow exand reliable execution of service-based workflow applicution in the grid JJ. IEEE Transactions on Systemscations for Beesy Cluster using distributed agents[ Cl/Man, and Cybernetics, Part C: Applications and ReviewsProc of the International Multiconference on Computer2006,36(3):353-364Science and Information Technology, IMCSIT 2010, [9] Xiang Zhuo-yuan, Pan Tian-hen. Research on flexibility2010:173-180.of the workflow reference model[C]/ Proc of 2nd Inter4 Cichocki A, Rusinkiewicz M Providing transactional prop-national Workshop on Knowledge Discovery and Dataerties for migrating workflows]. Mobile Networks andMining,2009:422-427.Applications, 2004, 9: 473-480[10]孙鑫,陈秋双基于移动 Agent技术的虚拟企业协调机制叮5] Singh A, Juneja D), Sharma a KAdaptive and automated计算机工程与应用,2007,43(2):209-212fault- tolerance for multi- agent systcms]/ Proc of Ieee[I]曾广周,党姸基于移动计算范型的迁移工作流硏究计International Conference on Computer Science and Au算机学报,203,26(10)1:1343-1349上接4页Transactions on Mobile Computing, 2009. 8(12): 1705-1717[4] Avis D.A survey of heuristics for the weighted matching6结束语problem[J] Networks, 1983, 13(4): 475-493无线环境下的节点链路调度是无线多媒体传感[S] Preis r linear time/2- approximation algorithm for max器网络面临的关键技术问题之∵:(1)多跳干扰下寻imum weighted matching in general graphs[C]/Symposium找最优的调度计算复杂;(2)集中式调度算法分布式on Theoretical Aspects of Computer Science, 1999实现难度大:(3)网络规模扩大时,已知分布式调度6] Hocpman J H Simplc distributed weighted matchings[Z算法性能下降明显。本文根据节点的分布密度提出2004分区链路调度,根据节点的分布密度,将网络划分为7] Dimakis A, Walrand J.Sufficient conditions for stability of不同的区域,在不同的区域使用不同的调度算法,使longest-queue-first scheduling: second-order properties using得分布式调度算法的性能下降问题得到有效的控fluid limits[J. Advances in Applied Probability, 2006, 382):505-521制。本文评估了不同负载下调度算法的队列总长度[8 Joo C, Shroff N B Local greedy approximation for scheduling以及平均调度时延。实验数据显示,所提算法要优in multi-hop wireless networks[. IEEE Transactions on于纯分布式调度算法。Mobile computing, 2011: 1-14[9 Riga N, Matta I, Bestavros A DIP: density inference protocol参考文献:for wireless sensor networks and its application to den[1 Akyildiz I F, Melodia T, Chowdury K R Wireless multisity-uinbiased statistics, BUCS-TR-2004-023[R]. Bostonmedia sensor networks: a survey[J]. Wireless Communica-Boston University, 2004tions,IEEE,2007,14(6):32-39[10 Gupta A, Lin X, Srikant R Low-complexity distributed2 Almeida J, Grilo A, Pereira PR Multimedia data transportscheduling algorithms for wireless networks[J]. Analysisfor wireless sensor networks[C]//Next Generation Internet2009,17(6):1846-1859Networks. 2009: 1-8[ll De Couto D, Aguayo D, Bicket J, et al. High-throughput3 Krishnaswamy D Robust routing and scheduling in wirelesspath metric for multi-hop wireless routing[ C]/Proceedingsmesh networks under dynamic traffic conditions[] IEEEof mobicom. 2003