移动平台下的结构性文档意图维护算法

王 丹,朱思征,高丽萍,王山山

1(上海理工大学 计算中心,上海 200093)2(上海理工大学 光电信息与计算机工程学院,上海 200093)

1 引 言

计算机产业的蓬勃发展,促进和影响着人们的日常工作和生活,网络的出现,让人们可以跨越地域、跨越文化,实现在线的、实时的交流.然而近年来,各个行业的工作规模日益增大,仅靠个人的单打独斗,很难高效高质量的胜任一项庞大的工作,为此,一种新的工作模式CSCW[1](计算机支持的协同工作：Computer Supported Cooperative Work)被提出.

协同工作概念的出现,大大改变了人们的工作方式,提高了工作效率,它支持人们在不同的地区,使用不同的设备,在同一时刻参与完成同一项工作.由此,产生了大量的支持协同工作的应用和系统[2-5],而在协同过程中伴随出现了一系列的冲突与一致性问题[2].后来,人们围绕冲突消解和一致性维护提出和改进了多种算法.一致性维护主要解决各协作用户间的本地文档存在差异的问题,最终使所有协作端能够拥有相同的编辑副本.而冲突消解,意在维护每一个协作用户的工作意图.目前一致性维护算法和方法以及系统已经设计和开发的相对成熟,而涉及到意图维护方面的内容相对较少,在协同工作中,如何能够在最大程度上公平公正的维护每一个协作用户的意图,是一件提升协同工作意义的重要工作.

近年来移动应用技术发展迅猛,移动设备、平台、应用层出不穷,传统的支持PC端的协同应用和算法也同样在顺应科技发展的潮流,逐步向移动端移植[6].移植过程中面临的网络、存储、设备差异化等问题,都是亟待解决的关键问题.

结构文档,我们可以简单理解为文本内容间存在等级结构的文档[7].例如我们在工作中常用的word文档编辑模板,标题、表格、图片等都有严格的样式和层级规定,其中标题的等级,能够清晰的体现文档中内容的结构关系.将结构文档加入到协同编辑工作中,利用结构化的方式存储,一方面能够将整体冲突细化到局部冲突,提升协作效率；另一方面,能够对不同等级的文档内容赋予编辑权限,尽可能的保证大部分协作用户的编辑意愿；再者,结构文档的存储方式,更能够适应移动终端,解决移动设备存储空间有限的问题.因此,如何在优化结构文档在移动端的存储方式,如何合理涉及用户编辑权限,最终提升协作效率,最大程度上满足协作用户的操作意愿,研究意义重大.

本文的结构如下：首先回顾之前的移动平台下基于局部复制的结构性文档协同编辑冲突消解算法,并针对本文提出的算法对文档结构、节点属性、节点类型、网络连接模式等定义；然后给出文档初始化、仲裁方式、权限转移等详细的算法描述；最后对核心算法部分进行复杂度分析,并结合实例梳理算法整体实现流程,验证其准确性；文章最后,介绍后续的研究方向和内容.

2 相关工作

1998年Sun[2]在最初的dOPT[1](distributed Operational Transformation)算法中提出的一致性维护模型CCI(Convergence Causality Intention)的基础上,补充了意愿维护的标准,强调了用户意愿在协同工作中的重要性.在维护一致性方面,最具代表性的算法大致分为两类,基于操作转换的OT算法(Operation Trans-formation)[1]和基于地址空间转换的AST算法(Address Space Transformation)[4].至今,围绕OT和AST技术衍生了众多并发控制算法,如GOTO[1]、SCOT4[8]、ABST[9]、TIBOT[10]等.同时这两类技术也被广泛应用在协同应用和系统的开发中,典型的如支持多用户协同编辑的分布式草图系统SketchPad和支持产品设计的协同系统Co-CAD[11].在意愿维护方面,针对不同类型的文档,提出了相应的冲突消解策略,如解决文本意愿冲突的多版本策略[12],和Ignat[13]提出的基于二维图形编辑的语义冲突消解策略.但这些研究多是基于全复制式架构[2],且站在状态乐观的角度,需保证网络连续,通讯顺畅,存储空间充足等环境,一旦文档规模变大,操作数量上涨,网络出现不稳定,缺少良好的应急处理机制,将导致策略失效,协同工作无法进行.而存储有限、网络不稳恰恰是移动端的特性所在.针对此问题,2014年Huanhuan Xia[17]等人提出了局部复制式架构,与全复制式架构相比,不仅节约存储空间,也节省了文档副本的更新时间,更加适用于移动终端；而后,Sun在2016年提出了CSOT[14](Cloud storage Operational Trans-formation)算法,首次将OT的一致性维护能力移植到云存储共享空间中,实现理想的并发操作效果合并,为基于云的协同技术发展奠定了基础.

在Huanhuan Xia及Sun的研究基础上,我们在之前的文章[7]中,提出了移动平台下基于局部复制的结构性文档协同编辑冲突消解算法,简称MCPS算法,初步的设计了结构性文档协同工作中可能出现的冲突消解算法,并提出了树活跃度(TLV： Tree liveness)和节点活跃度(NLV：Node liveness)两个概念,来动态的解决操作冲突,一定程度上客观的维护了协同用户的意图,但整个结构性文档的协同编辑设计仍需细化,例如如何控制用户的加入和退出,不同协同用户所具备的权限.在之前的意图维护算法中,多使用站点优先级对比,时间戳对比,版本控制等方法.本文在文献[7]中提出的活跃度基础上,更改网络连接模式,加入了标题和站点master属性,赋予用户权限,为了实现用户即来即走的特性,根据用户在共享文档中的编辑活跃度,设计了合理的权限转移控制机制,提出了移动平台下基于用户活跃度的结构性文档意图维护算法,简称MCPS2算法.

3 准备工作

3.1 MCPS算法回顾

在之前的文章中[7],我们分析了结构性文档在移动云平台下进行协同编辑时可能产生的一系列冲突,并对每种冲突设计了对应的消解方案,以解决协同编辑过程中各协作站点文档副本不一致的问题.同时,我们将各种冲突消解策略整合在一起,设计了一款基于局部复制的结构性文档协同编辑冲突消解算法,简称MCPS算法.该算法中主要包括表1中的几种冲突类型：

图1 结构文档StrTree和骨架树Fig.1 A figure introduces the structured document tree (StrTree) and skeleton tree

表1 冲突类型和说明Table 1 Illustration of conflict types

在图1中,我们给出了MCPS算法设计的节点属性中涉及的基本定义,其中虚线框中包含的节点集,也就是StrTree的子树,我们称它为协作站点可向服务器请求的骨架树(skeleton tree),详细的局部复制式架构副本请求策略可以参考文献[7].为了在最大程度上维护协作用户的意愿,我们提出了节点活跃度(NLV： Node liveness)和树活跃度(TLV： Tree liveness)的定义,动态记录和更新每个协作用户在各个标题节点和子树上的编辑活跃度,在产生编辑冲突时,对比冲突站点的活跃度,决定操作的优先执行顺序,相比以往的通过判定站点的优先级,时间戳等人为规定操作执行顺序的方式,此方法更为客观公平.本文将在之前提出的MCPS算法基础上,对通信方式、协同编辑流程、用户权限、文档定义、意愿维护等方面进行改进和细化,以提升算法在系统开发中的可用性.

3.2 网络连接模式

本文未沿用MCPS算法中以中央服务器为操作处理和数据转发的协同交互方式,而是选择使用P2P的连接方式,原因在于协同客户端间的传输粒度多为操作、操作集、标题集或部分文档,不涉及大文件的频繁传输,目前国内市场的移动终端应用技术发展迅猛,且网络带宽同时也在不断提升,先进的软硬件和网络现状,能够支撑P2P的网络连接模式.再者,P2P能使网络上的沟通变得容易,实现更为直接的共享和交互,在协同工作和分布计算方面大有用途.

图2 协作站点P2P连接方式Fig.2 P2P connection of collaborative sites

图2中,我们为每个协作团队,设置了一位master,协同工作开始时,master由结构文档协同编辑工作的发起人担任,一旦master在协同工作中退出,将在协作团队中根据成员活跃度,推选新的master,详细的选取流程将在算法设计中给出.

Master的主要工作,是在协同工作开始时,向各协作用户发起结构文档,同时具备合并结构文档的权限,在本系统中,文档合并是一个定时触发的进程,即在系统工作经历特定时间间隔后,请求然后自动合并各协同用户在该时间截点前的数据, 若非master的协作用户想要在本地合并结构性文档,需向当前的master站点提出请求,请求通过后才可合并.

图2中的协同工作由M1～M5(其中M1为 master)5个用户完成,图中的连接线代表各站点间网络互连,每个协作站点的结构文档只有标题整体架构一致,标题下的内容只有站点请求并通过才可同步.图中的连接线分为实线和虚线,实线代表协作站点间存在共同编辑的标题块,如M1和M2本地同时具有结构文档中的P3.1的编辑权限,虚线代表各站点间产生新标题或删除、修改标题时向其他站点广播的过程.

3.3 文档及节点定义

文档结构的定义沿用MCPS算法中的定义,主副本利用树形结构存储,树中的子父级关系代表标题节点的层级.

3.4 节点类型定义

节点类型包含以下两类,共4种：.

第一类：现实节点.

标题节点(TN：Title-Node)：客户端请求节点；

结构父节点(SPN：Str-Parent-Node)：客户端请求节点的父节点,且未被请求,为了维护副本树结构复制在客户端但不包含文本内容；

结构兄弟节点(SBN：Str-Brother-Node)：客户端请求节点的兄弟节点,且未被请求,为了维护副本树结构复制在客户端但不包含文本内容；

第二类：虚拟节点.

虚拟根节点(VRN：Virtual-Root-Node)：虚拟根节点为每一个一级标题的父节点,是在后台虚拟存储,为维护结构文档整体树型结构而存在,可以存储结构文档的文档名称,也可为空；

虚拟结构节点(VSN：Virtual-Str-Node )：虚拟节点的存在类似于虚拟根节点DOC,因为在非标准的结构文档中,不能保证每个标题节点的层级结构都是完整的,对于结构文档中散落的标题节点,我们自动为其创建父级虚拟结构节点,达到维护结构文档树型架构的目的.虚拟结构节点只在后台存储,并不显示在结构文档中.

3.5 节点属性定义

在之前文章对节点定义的基础上,我们新增了两个新的节点属性：

图3 节点属性定义Fig.3 Attributes of node

CE(Current Editors Numbers)：当前参与该标题节点下文档编辑的协同用户人数；

TC(Title Creator)：每一个标题节点中,记录该标题节点的创造人,以便后期的请求仲裁和文档合并工作使用；

所以最终我们对一个标题节点的定义可以表示为图3中的形式.

3.6 操作定义

1)Append(N)：本地增量式向节点集N中的每个节点的Title Creator请求数据；

2)Delete(id,site)：站点site删除标识符为id的节点；

3)InsertTitle ( parentId,id,site,data,name)：在父节点parentId的子节点尾部追加一个新的标题节点；

4)InsertTitleBefore (parentId,refId,id,site,data,name)：在父节点parentId的子节点队列中refId节点前插入一个标识符为id,标题内容为name,标题文本内容为data的节点；

5)UpdateName(id,newName,oldName,site)：更新标识符为id的节点标题名称oldName为newName.

6)UpdateData(id,newData,oldData,site)：更新标识符为id的标题下的内容oldData为newData.

4 MCPS2算法设计

4.1 结构文档初始化

在结构文档开始协同编辑工作开始时,首先给协同工作发起站点分配master权限,master客户端首先初始化提供的结构文档中的数据,即将每一个标题节点(文中提出的标题节点包括所有等级的节点,具体的等级关系通过节点属性中的参数关联)都被赋予第三部分提出的节点属性参数值.

算法1.ConstructDoc(Doc)： Str-Doc

1. M1←master

2. i ← 0,Str-Doc ←Doc

3.forall nodes in Str-Docdo

4. Str-Doc[i].TC ←M1

5. i←i+1

6.endfor

7. user M1 choose editing Nodes as index sequence N

8.forj← 0 to N.length-1do

9. Str-Doc[ N[j]].CE ←M1

10.endfor

11.returnStr-Doc

4.2 协作站点请求数据

在节点属性中我们设置了标题创始人参数TC,用来标记该标题节点是由哪一个协作站点新增,假设图2中,站点M2请求编辑的标题节点集为P=[p3.1,p4.1],标题节点p3.1和p4.1的TC属性均为M1,所以向M1站点发出数据请求,操作流程参见算法2；M1接收到请求后先判断请求的标题节点是否已达编辑人数上限,是则拒绝请求,否则等待该标题内协作用户的集体仲裁,且TC具有一票否决的权利,若TC通过,CE中的其他站点继续仲裁,仲裁阶段设置时间限制,超时默认自动放弃仲裁,请求判定标准为：通过用户在该节点的节点活跃度(NLV)之和与拒绝用户在该节点的节点活跃度之和进行比较,活跃度高者判定结果生效,仲裁逻辑详见算法3.

算法2.RequesetNodes(P)

1. for i←0 to P.length do

2. request for site of P[i].TC

3. end for

算法3.Arbitration(id)：n /*此站点为M,节点集为N */

1.fori←0 to N.lengthdo

2.if(N[i].id==id)then

3. n←N[i]

4.endif

5.endfor

6.if(n.CE.length>=MaxCE)then

7. post refuse to the request site

8. return n←null

9.else

10.if(site M agree)then

11.for(j←0 to n.CE.length)do

12. Ask for arbitration from collaborative sites in n.CE[j]

13.if(n.CE[j]agree)then

14. NLVa←n.CE[j].NLV

15.elseif (n.CE[j]refuse)then

16. NLVr←n.CE[j].NLV

17.else

18. j←j+1

19.endif

20.endfor

21.else

22. post refuse to the request site

23. return n←null

24.endif

25.endif

26. /*活跃度对比*/

27.if(NLVa>= NLVr)then

28. n.CE.add(M)

29. post node n to the request site

30.else

31. post refuse to the request site

32. n←null

33.endif

34. return n

请求站点接收到返回的标题节点后,在本地通过Append操作自动构建编辑副本,构建过程可参考文献[7]中的局部复制算法.

4.3 基本操作

任何协作站点想要插入新的标题节点,除了一级标题外的所有节点,都需要向父节点的TC请求插入权限,通过以后才可以插入新节点,并向所有协作站点发送此标题节点,保证各站点树形文档结构的一致.受篇幅所限,我们将InsertTitle和InsertTitleBefore两个操作的处理算法中类似的部分抽取出来进行描述.

算法4.Insert(parentId,id,site,data,name) /*请求站点为M,插入节点N*/

1. define n.id==parrentId

2.if(n.TC !=M)then

3. request authority from n.TC

4. switch the response of n.TC do

5.case“agree”

6. N.parentId←n.id

7. N.TC←M

8. N.CE.add(M)；

9.case“delay”

10. repeat “agree”；

11.case“otherwise”

12. break；

13.endsw

14.endsw

15.endif

同样,任何协作站点执行更新和删除节点操作时,需要向该节点的Title Creator 提出请求,请求通过才可执行.

4.4 文档合并

master在特定时间间隔合并文档,因为每个标题节点有且仅有一个标题创建者,所以合并过程为向所有站点请求这些站点各自创建的节点数据,若协作站点想要合并结构文档需向master提出请求,请求通过才可合并文档.

算法5.merge(M1,sites )： StrDoc /*请求站点为M1,sites为所有站点的集合*/

1.if(M1is not master)then

2. request for master

3.switchresponsedo

4.case“refuse”

5. break；

6.case“agree”

7. merge as master

8.endsw

9.else

10.for(i←0 to sites.length)do

11. request for sites[i]for nodes which node.TC is sites[i]

12. StrDoc.add(nodes)

13.endfor

14.endif

15. return StrDoc

4.5 master & TC 权限转移

协同编辑系统,支持协同用户的随时加入和随时退出,但在本文算法中,提出的节点包含了TC (Title Creator) 这一属性,在上侧算法中也涉及到向标题节点TC请求权限的操作,一旦在请求前,仲裁站点退出,那么请求将不会得到响应,最终导致此标题节点可以被任意修改；同样,在协同工作中的master也存在退出的可能,若退出后不推选出新的master,那么文档合并工作将停止,这些问题最终都将违背我们最大程度保护用户编辑意图的初衷.为了解决此问题,我们设计了支持master和TC退出,权限转移的算法.

master退出前需要先决定将权限转移给哪一个协作站点,站点选择的主要依据是：“在树型结构文档中活跃度最高,贡献最大的站点,将作为下一任master”,即在虚拟根节点DOC上的树活跃度TLV最高的站点被选为master.

算法6.masterChange(M1,Str)： M

1. sites←Str.DOC.CE

2. result←-1

3.ifmaster exsitthen

4.fori←0 to sites.lengthdo

5. result←Max(result ,Str.DOC.sites[i].TLV)

6.endfor

7.forj←0 to sites.lengthdo

8.if(Str.DOC.sites[j].TLV==result)then

9. M←sites[j]

10. break；

11.endif

12.endfor

13.endif

14. grant privilege to site M

站点M接收到master授权后,在本地首次合并结构文档,并向其他站点广播更新master站点信息.

同样任意站点退出时,查找此站点创建的标题节点,统计是否存在一个站点,参与编辑的标题节点数量最多,若存在且唯一,取此站点替代退出站点；若存在但不唯一,比较这些站点在结构文档副本的活跃度,活跃度最高的站点,取代退出站点,继承退出站点的所有权限；若不存在,说明没有其他站点参与这些标题节点的编辑工作,则master直接继承退出站点的所有权限.

算法7.TCChange(M1,StrCopy)： M /*M1为退出站点,StrCopy是M1本地结构文档副本*/

1.if(site M1exsit)then

2.fori←0toStrCopy.lengthdo

3.if(StrCopy[i].TC == M1)then

4. contact( StrCopy[i].CE ) as array CEs /* contact是合并所有站点CE产生新数组,产生新的数组CEs,CEs为对象数组,包含站点site和重复值count两个属性 */

5. count and duplicate CEs /*计算CEs中每个元素的重复值,并记录在count属性中,并删减重复元素*/

6.endif

7.endfor

8. select max elements in CEs as array L

9.switchL.length do

10.case“=1”

11. Grant privilege of M1to M which L[0].site

12. case ”>1”

13.for(j←0 to L.length)do

14. max(StrCopy[0].L[j].TLV)

15. index←j

16.endfor

17. Grant privilege of M1to M which L[index].site

18.case“<1”

19. Grant privilege of M1 to master

20.endsw

21.endif

站点M接收到M1授权后,向所有站点广播替换节点中TC和CE中的M1为M,由于篇幅所限,具体的替换流程,我们在后续文章中提出.

5 复杂度分析

结构文档初始化是结构文档创建者即master给标题节点中的TC、CE等属性赋值的过程,暂不涉及其他站点协作,假设初始结构文档中的节点个数为N,其中master请求参与协同编辑的节点个数为M,则标记节点TC的时间复杂度为O(N),请求节点后CE中新增站点信息的时间复杂度为O(M),由于M<=N,所以,当master创建一个新的结构文档协作任务时,整体的时间复杂度为O(N).

协作站点请求数据时,需等待TC站点的仲裁,在算法3中,在TC站点同一发送请求数据之后,需要向该节点CE中的所有的站点发出仲裁请求,通过站点的活跃度总和与拒绝站点的活跃度总和进行对比,我们假设请求的节点为n,在等待请求结果方面我们设置的最大延迟时间,假设为时长为delayTimes,则在最差的环境下,该节点操作站点数量达到上限S,且每个站点都要等到最大延迟时间才返回请求结果,那么请求时所需的时间复杂度为O(S), 并伴随n.CE.length *delayTimes时长的而延迟.

对于新增、插入、删除等基本操作,我们加入了权限控制,请求操作执行权限时时间复杂度为O(1),并伴随delayTimes时长的延迟.在之前的文章中,我们对整个并发控制过程的最坏时间复杂度进行了分析,可以抽象为O(N2),N为结构文档中的节点总数,最坏的情况下,假设此时有S个站点同时编辑一个节点并产生了冲突,且S为编辑人数上限, 则基本操作阶段,解决一个节点冲突的时间复杂度为T(N,S)=T(N2)+S*T(1)=O(N2),并伴随S*delayTimes时长的延迟.

在master切换阶段,要在其他站点中找到一个站点,它在结构文档也就是虚拟根节点DOC上的树活跃度最高,赋予它master权限,假设master退出后继续参与协同工作的站点个数为T,则此过程所需的时间复杂度O(T)；而在TC权限转移阶段,首先将退出站点的所有节点(节点个数为N)的CE合并为长数组CEs,时间复杂度为O(N)；利用数组处理算法(由于篇幅所限,本文不对此算法进行详细描述),求出CEs中每个数组元素的重复次数,若该数组中有且仅有一个重复次数最大额数组元素,那么他对应的站点将被赋予退出站点的所有权限,一般的处理算法时间复杂度为O(CEs.length2),最差情况下,所有节点的CE已达到最大编辑人数S,此时的时间复杂度为O((N*S)2)；若不唯一,则比较这些站点在该节点的节点活跃度,活跃度高者接替退出站点权限；若不存在,则直接授权给master；所以TC权限转移所需的时间复杂度可以表示为T(N,S)=O(N)+O((N*S)2)=O((N*S)2).

虽然在请求数据和仲裁等阶段都会出现不同程度时长的延迟,这也是与之前大部分意图维护算法的区别之处,但能够通过此方式尽可能的保护用户意愿,提升协同工作的意义,也是值得的.且后期能够通过网络带宽的提升、算法的优化等手段缩短延迟,最终达到更好的用户体验.

6 实例说明

如图4所示,包含两个协作站点M1和M2,其中M1作为master发起协同工作,并提供初始副本Str-Doc=[n1,n2,n3,n4,n5,n6,n7],在副本初始化过程中,M1作为Str-Doc中所有节点的创建人,那么这些节点中的TC属性都被标记为M1,而其中M1只申请编辑了节点n1和n2,则n1.CE=[M1],n2.CE=[M1].

M2请求执行O1=Request(n1,n6)：此时站点M2加入到协作任务中,并向master发起请求节点集N=[n1,n6](操作O1),因为n1和n6的TC都为M1,所以M1直接对O1操作进行仲裁,详细的操作流程如下：

Step1.M1接收到O1的请求节点操作后,先判断两个节点各自的CE中编辑用户数是否达到上限,未达到,接受M1的仲裁,M1同意发送节点数据给M2；

图4 M1 和M2站点请求节点Fig.4 Example of requesting nodes at M1 and M2

Step2.M1同意后,分别向n1和n6的CE中的用户发出集体仲裁请求,因为n1.CE= [M1],n2.CE=[],n1只有一个M1参与编辑,而n6暂时没有用户参与编辑,则默认仲裁通过；

Step3.仲裁通过后,M1在本地更改节点n1和n2属性,即n1.CE=[M1,M2],n6.CE=[M2].

Step4.根据局部复制原理,保证局部副本的树型存储结构,M1将返回节点集N′=[DOC,n1,n2,n6]给M2,其中n2只包含存储结构相关参数；

M2请求执行O2=InsertTitleBefore(n1,n5,n8,M2,data,name)：M2请求在n5前插入节点n8：

Step1.首先找到n5节点的父节点为n1,n1.TC=M1；

Step2.向M1发起插入请求；

Step3.M1拒绝请求,并反馈给M2；

Step4.O2变为废操作.

M2请求执行O3=InsertTitleBefore(n2,n6,n8,M2,data,name)：M2请求在n6前插入节点n8：

Step1.首先找到n6节点的父节点为n2,n2.TC=M1；

Step2.向M1发起插入请求；

Step3.M1同意请求,并向当前参与n2协同编辑的用户们n2.CE发起仲裁请求,即向M1请求,则默认通过；

Step4.M1在本地执行O3,Str-Doc=[n1,n2,n3,n4,n5,n6,n7,n8],n8.TC=[M2],n8.CE=[M2]并更新节点中的活跃度属性,我们只将几个有变动的节点对应的节点活跃度(NLV)和树活跃度(TLV)标记如图5所示.

图5 站点M1和M2的节点、树活跃度Fig.5 TLV and NLV of at M1 and M2

插入节点、删除节点以及编辑节点内部的data和name信息,都需要通过如上的基本请求→仲裁→执行流程,其中的仲裁过程是最能够实现意图维护意义的手段,为了更直观的体现活跃度在意图维护中的重要作用,我们加入新用户M3,各站点执行以下操作,详细的操作交互流程如图6所示.

M3： Append(N),N=[n1,n3,n4]；请求后M3站点存储的局部副本结构如图5所示.

M1： UpdateName(n1)；UpdateData(n1)；两个操作都只是改变节点内部的标题和内容,并没有改变文档副本的结构内容.

M2： Delete(n6)；InsertTitle(DOC,n9)；执行了删除和插入操作后会对副本的结构产生影响.

图6 站点M1、M2和M3操作执行流程Fig.6 Operations executed at M1 and M2 and M3

执行上述操作后,各节点在各站点的活跃度更新为图7中值.

上述的操作请求中,节点创建人TC和协同编辑用户群CE,均是一致通过,若在请求仲裁过程中,出现仲裁结果不一致,有的用户同意,有的用户拒绝,该如何处理？我们以M3发起的一个操作举例说明.

此时M3请求执行O9=UpdateName(n1),执行步骤如下：

Step1.n1.TC=M1,向站点M1发出O9请求；

Step2.M1接收到O9请求后,首先判断同意执行该操作；

Step3.查找n1.CE=[M1,M2,M3],继续向协同编辑节点n1的用户M2发起请求；

Step4.M2接收到请求后,拒绝执行O9操作；

Step5.仲裁阶段出现了意见不一致的情况,此时判断同意用户与拒绝用户在该节点上的节点活跃度总和.如图8所示,(n1.M1.NLV=2) > (n1.M2.NLV=0),即同意>拒绝,那么最后的仲裁结果为同意M3站点执行O9操作；

Step6.M2在本地执行O9操作,返回同意请求给M1；

Step7.M1接收后,在本地执行O9,返回同意请求给M3；

Step8.M3接收后,在本地执行O9.

在上述的操作仲裁过程中,我们充分使用了节点创建人权利优先,协同编辑用户活跃度高优先的原则,也就是谁对节点贡献越多,话语权越大,来综合判定一个操作是否能够执行,这在很大程度上保证了多用户的意愿.在一致性维护方面,图8中,分别给出了执行上述操作集后各站点最终的副本状态,从M1站点可以看出,站点M2和M3的局部副本都为M1局部副本的一部分,且文档的树形结构及节点间的父子兄弟关系都一致,说明一致性得到维护.

图8 站点M1、M2和M3最终副本状态Fig.8 Final Str-Doc at M1 、 M2 and M3

7 总结及展望

计算机技术与移动设备的迅猛发展,时刻影响着人们的工作和生活方式,移动办公,是当前也将成为未来主要的办公模式.协同办公概念的出现,可以视作办公模式改革的又一里程碑.如何将之前的协同技术和应用成功移植到移动端,并适应移动设备网络不稳、存储有限等约束条件,成为了亟待解决的关键问题.本文基于局部复制策略和用户活跃度,在之前的研究基础上,提出了移动平台下基于用户活跃度的结构性文档意图维护算法,利用P2P的网络连接模式构建协同工作网.创新的提出站点master,节点Title Creator属性,合理分配节点编辑、请求、新增权限,最大程度满足多用户的意愿.同时为了满足用户即来即走的需求,提出了权限转移动态控制机制,最终提升整个协同工作的的意义.

后续的研究工作包括：

1)优化算法执行效率,完善权限转移控制流程；

2)将MCPS2算法与MCPS算法结合,开发一款结构性文档协同编辑APP；

3)在应用中引入图像[15,16]、表格、文字等编辑内容.