近年来，随着无线网络普及和智能终端技术的快速发展，智能终端成为流行的移动计算平台，支撑着跨地域工作人员随时随地进行灵活的移动办公和协作支持[1-3]．传统的运行于桌面上的实时协同编辑系统不断向基于智能终端的移动协同编辑系统转变[3]．然而，基于智能终端的移动协同编辑的相关研究面临若干技术难题．为了实现良好的交互性和响应性，通常采用全复制式体系结构，但是又给共享对象的一致性维护带来了挑战，该问题一直是分布式计算/协同计算领域关注的热点[4]．为了实现协同编辑中共享对象的一致性维护，协同编辑的一致性维护技术得到了深入的研究和探索．在协同编辑领域近年来的研究中，主流的一致性维护技术包括操作转换(operation transformation，OT)、地址空间转换(address space transformation，AST)和可交换复制式数据类型(commutative replicated data type，CRDT)．自第一个协同编辑系统GROVE被提出后[5]，OT技术不断发展，基于OT的一致性维护方法不断涌现[6]．一方面，OT技术支持的协同编辑对象越来越广泛，从纯文本到图形、图像、XML文件及复杂CAD模型；另一方面，OT技术的应用领域不断被拓展，从支持传统的桌面协同扩展到支持移动协同、移动办公等协同交互式应用[7]．AST技术[8]适合在广域网和移动网络环境下为用户提供流畅的协同交互体验，并不断应用到移动协同、异构协同等热点领域[9]．CRDT技术[10]可以支持不同粒度的文本对象[11-13]和复杂CAD模型的实时协同编辑[14-15]．虽然CRDT技术在桌面实时协同编辑中有重要的研究成果，但是将CRDT技术应用到移动协同编辑中，在支持用户离线操作、操作序列的转换和同步、离线和在线共享对象的一致性维护等诸多方面存在技术挑战．为了探索CRDT技术是否可以拓展到移动协同编辑中及测试将CRDT技术应用到移动协同编辑中的响应性和功耗，基于前期的研究工作[11]，提出了一种支持字符串操作的移动复制式可增长数组(mobile replicated growable array based supporting string，MRGASS)算法，可以支持移动用户的大量离线操作，自动实现操作序列的转换和操作效果的合并，维护了移动终端共享对象的一致性．1 基于CRDT的序列转换算法1.1　移动协同编辑框架图1为提出的移动协同编辑框架示意图，每个移动终端Ci (i=1，2，…，n)都维护相同的数据结构，包括locallog，locallog'，remotelog，log和DS．其中，locallog存储本地产生的操作序列，locallog'存储经过序列转换和操作效果合并后的待同步本地操作序列，remotelog存储接收到的远程操作序列，log存储已经执行本地和远程的操作序列．同步变量s用来表示移动终端状态．若信号量m=0，则执行本地操作序列；若m=1，则执行接收到的远程操作序列．10.13245/j.hust.220220.F001图1移动协同编辑框架示意图图2为移动终端共享文档副本DS结构示意图，包括用户视图层(view)和模型层(model)．模型层由哈希表(hash table，HT)和双链表(Lm)构成．HT存储用户插入或者删除的结点，Lm全序链接HT中用户插入或者删除结点．每个结点中存储用户插入或者删除的字符串．用户视图层包含一个双链表Lv，由Lm中所有可见结点链接而成，提供用户交互界面．例如，图2中Lm链接了用户插入的字符串，用“-”表示字符串的链接关系，Lm链接的字符串为“abc-defg-lmn-…-xyz”．其中，字符串“defg”为用户删除的字符串，在Lm中置为墓碑，用斜虚线表示．10.13245/j.hust.220220.F002图2DS结构示意图1.2　序列转换算法定义1 操作O．一个操作O是一个八元组〈type，pos，del_len，lor，tar_key，key_list，key，str〉，其中：type为O的操作类型，包括插入操作(insertion)和删除操作(deletion)；pos为Lm中的操作位置，在结点内部或者结点后；del_len为删除字符串长度；lor为一个整型变量，值为0或者1，0代表本地操作，1代表远程操作；tar_key为目标结点的标识符；key_list为多个目标结点的标识符，适用于删除操作；key为O的标识符；str为插入的字符串．基于上述定义，MRGASS算法的创新之处在于当本地操作集成时，自动对本地操作序列进行转换和操作效果合并，可以减少本地存储的操作日志，使移动设备在获得相同操作效果的同时执行更少的远程操作．该方案能节省移动设备的资源开销，使移动协同编辑系统获得更好的响应性．移动协同编辑的总体控制过程如算法1所示，包括移动设备的初始化(Initialization)、产生和集成本地操作序列(Gene_Inte_Local_Op)、操作序列的同步(Synchronization_Op)和集成远程操作序列(Inte_Remote_Op)．算法1 移动协同编辑控制算法输入 O，s，m，DS输出 Lm，LvInitialization：DS=Doc；locallog=NULL，locallog'=NULL，remotelog=NULL，log=NULL；s=0，m=0；Gene_Inte_Local_Op：IF s==0 && m==0 THENlocallog=Add(O，locallog)；FOR O IN locallog DOIntegrateLocal(O)；END FOREND IFSynchronization_Op：s=1；send locallog' to other mobile devices；receive remotelog from other mobile devices；s=0，m==1；Inte_Remote_Op：IF s==0 && m==1 THENFOR O IN remotelog DOIntegrateRemote(O)；END FOREND IFs==0，m==0．算法2给出了本地操作集成函数IntegrateLocal(O)[11]的执行过程，包括本地插入操作的集成和本地删除操作的集成．在本地插入操作集成中，当locallog'不为空时，取出最后一个操作On．如果O的目标操作是On，并且O插入字符串恰好在On插入的字符串后，那么调用合并插入函数MergeInsert(O，On)对插入操作的执行效果进行合并；否则，调用SingleInsert(O)函数执行本地简单插入操作．当locallog'为空时，调用SingleInsert(O)函数执行本地简单插入操作．算法2 IntegrateLocal(O)输入 O输出 locallog'IF O.type == insertionIF locallog'!=NULL THENget On from locallog；IF O.tar_key == On.key && O.pos = On.key.len THENOn'=MergeInsert(O，On)；remove On from locallog' and log；locallog'=Add(On'，locallog')，log=Add(On'，locallog')；ELSESingleInsert(O)；locallog'=Add(O，locallog')，log=Add(O，log)；END IFELSESingleInsert(O)；locallog'=Add(O，locallog')，log=Add(O，log)；END IFELSELocalDelete(O)；locallog'=Add(O，locallog')，log=Add(O，log)；END IF算法3给出了MergeInsert(O，On)函数的执行过程．首先，使用哈希函数找到On插入的目标结点Tar_Node，将O中待插入的字符串拼接Tar_Node的字符串后面；然后，更改Tar_Node的key中字符串长度和On的key中字符串长度；接着，更新On中存储的字符串，将操作O中存储的字符串拼接On存储的字符串后面；最后，生成新的合并后操作On'，用以更新待发送的本地操作日志．算法3 MergeInsert(O，On)输入 O，On输出 On'Tar_Node=hash(On.key)；Tar_Node.content.append(O.str)；Tar_Node.key.len+=O.key.len；On.key.len+=O.key.len；On.str.append(O.str)；On'=On．2 序列转换和效果合并示例图3为两个移动设备参与同一个协同编辑的场景示例．假设两个移动设备开始于相同的初始文档状态“ ”，当前的协同会话号为1，两个站点site1和site2的身份标识号(ID)大小为ID[site1]ID[site2]．Lv1为site1视图层的文档状态，Lv2为site2视图层的文档状态．为了描述各插入字符串的链接关系，用“-”链接插入的字符串．10.13245/j.hust.220220.F003图3两个移动设备参与同一个协同编辑的场景示例2.1　第一阶段站点site1产生本地操作O11=insert(null，0，“aa”，IDO11)和O12=insert(IDO11，0，“bb”，IDO12)，site2产生本地操作O21=insert(null，0，“cc”，IDO21)和O22=insert(IDO21，0，“dd”，IDO22)．操作的状态向量为：S(O11)=(1，0)，S(O12)=(2，0)，S(O21)=(0，1)，S(O22)=(0，2)．操作的ID为：IDO11=(1，1，1，0，2)，IDO12=(1，2，1，0，2)，IDO21=(1，1，2，0，2)，IDO22=(1，2，2，0，2)．在站点site1，O12插入的“bb”与O11插入的字“aa”合并，生成新操作O11'=insert(null，0，“aabb”，IDO11')，执行完O11'后，Lv1=“aabb”．接下来，将O11'发送给移动站点site2．在站点site2，O22插入的字符串“dd”与O21插入的字符串“cc”合并，生成新操作O21'=insert(null，0，“ccdd”，IDO21')，当执行完O21'后，Lv2=“ccdd”．接下来，将O21'发送给移动站点site1．2.2　第二阶段在站点site1，收到并执行完O21'后，Lv1=“ccdd-aabb”．然后产生操作O13=insert(IDO11'，3，“gg”，IDO13)和O14=insert(IDO13，0，“mm”，IDO14)．当执行O14时，O14插入的字符串“mm”在O13插入的字符串“gg”后面，执行合并插入操作，生成新操作O13'=insert(IDO11'，3，“ggmm”，IDO13')，此时Lv1=“ccdd-aab-ggmm-b”，O13'发送给移动站点site2．在站点site2，收到并执行O11'后，Lv2=“ccdd-aabb”．然后产生操作O23=insert(IDO21'，1，“hh”，IDO23)和O24=insert(IDO23，0，“nn”，IDO24)．当执行O24时，执行合并插入操作，生成新操作O23'=insert(IDO21'，1，“hhnn”，IDO23')，此时Lv2=“c-hhnn-cdd-aabb”，O23'发送给移动站点site1．2.3　第三阶段在site1中，收到并执行完O23'，Lv1=“c-hhnn-cdd-aab-ggmm-b”．在site2中，收到并执行完O13'，Lv2=“c-hhnn-cdd-aab-ggmm-b”．最终，site1和site2的文档状态Lv1=“c-hhnn-cdd-aab-ggmm-b”，Lv2=“c-hhnn-cdd-aab-ggmm-b”，因此，Lv1=Lv2，当协同会话处于静默状态时，两个移动站点的协同编辑文档副本收敛于相同状态．3 实验评估在Windows10操作系统，Intel Core i7-9750H CPU的机器上，Android Studio环境中，用JAVA语言实现了MRGASS算法、文献[11]中算法和ABTSO算法，并设计和开发了基于三种算法的移动协同编辑应用．选取两台相同配置的华为麒麟980手机，安装所开发的移动协同编辑应用程序，测试MRGASS算法、文献[11]中算法和ABTSO算法[16]在移动端的响应时间和功耗．参照文献[7]和[9]，基于开发的移动协同编辑应用程序，在移动协同编辑过程中获取产生的本地和远程操作集合，让三种算法执行这些操作集合，反复测试25次，记录每一次测量的响应时间和功耗，最后计算出平均的响应时间和功耗．3.1　响应时间图4为MRGASS算法和ABTSO算法执行一个本地插入操作和本地删除操作的时间对比，图中：n为操作执行个数；t为操作的响应时间．操作数量从1 000到10 000递增，插入操作占总操作数量的80%．由于ABTSO算法在执行删除操作时不支持字符串分裂，因此在实验测试中不考虑字符串分裂10.13245/j.hust.220220.F004图4MRGASS算法和ABTSO算法执行一个本地插入操作和本地删除操作的时间对比情况．从实验结果来看：随着操作数量的递增，MRGASS算法具有较好的计算性能．图5为MRGASS算法和ABTSO算法执行一个远程插入操作和远程删除操作的时间对比．操作数量从1 000到10 000递增，插入操作占总操作数量的80%，操作的冲突比例设置为80%．从实验结果来看：随着操作数量的递增，MRGASS算法具有较好的计算性能．10.13245/j.hust.220220.F005图5MRGASS算法和ABTSO算法执行一个远程插入操作和远程删除操作的时间对比图6为MRGASS算法和文献[11]中算法在移动端执行单个远程操作的响应时间对比．操作数量从3 000到30 000递增，插入操作占总操作数量的80%，插入操作的合并比例占60%，操作的冲突比例设置为20%．从实验结果来看：随着操作数量递增，MRGASS算法的性能更优．这是因为MRGASS算法对本地插入操作进行了操作效果的合并，生成数量更少的远程操作同步给其他移动终端，其他移动终端执行数量更少的远程操作就可以获得相同的操作效果．10.13245/j.hust.220220.F006图6MRGASS算法与文献[11]中算法在移动端执行单个远程操作的时间对比3.2　功耗图7为MRGASS算法和ABTSO算法执行不同数量的本地插入操作和本地删除操作的平均能耗对比，图中e为手机消耗的能量．操作数量从1 000到10 000递增，每次增加1 000，插入操作占总操作数量的80%．实验数据表明：MRGASS算法在执行相同数量的本地操作的平均能耗更低．10.13245/j.hust.220220.F007图7MRGASS算法和ABTSO算法执行不同数量的本地插入操作和本地删除操作的平均能耗对比图8为MRGASS算法和ABTSO算法执行不同数量的远程插入和远程删除操作的平均能耗对比．操作数量从1 000到10 000递增，每次增加1 000，插入操作占总操作数量的80%．实验结果表明：MRGASS算法在执行相同数量的远程操作的平均能耗更低．10.13245/j.hust.220220.F008图8执行不同数量的远程插入和远程删除操作的平均能耗对比图9为MRGASS算法和文献[11]中的算法执行不同数量远程操作的平均能耗对比．操作数量从3 000到30 000递增，每次增加3 000，插入操作占总操作数量的80%，合并插入操作比例为60%和90%．实验结果表明：MRGASS算法在合并插入操作比例为90%时执行相同数量远程操作的平均能耗最低，文献[11]中算法在执行相同数量远程操作的平均能耗最大．10.13245/j.hust.220220.F009图9MRGASS与文献[11]算法执行不同数量远程操作的平均能耗对比4 结语本研究提出了一种移动协同编辑中基于CRDT的操作序列转换MRGASS算法，可以集成移动用户产生的大量离线操作，自动实现本地操作序列的转换和操作效果合并，维护了移动终端共享对象的一致性，实验验证了所提算法在响应性和功耗方面优于典型的一致性维护方法．