移動(dòng)云環(huán)境下實(shí)時(shí)協(xié)同圖形編輯一致性維護(hù)研究

高麗萍，高東方

1(上海理工大學(xué) 光電信息與計(jì)算機(jī)工程學(xué)院，上海 200093) 2(復(fù)旦大學(xué) 上海市數(shù)據(jù)科學(xué)重點(diǎn)實(shí)驗(yàn)室，上海 200093)

1 引 言

隨著云計(jì)算時(shí)代的到來，基于云的研究和應(yīng)用越來越熱，云計(jì)算具有高可靠性，高擴(kuò)展性等優(yōu)點(diǎn)，并且云計(jì)算能夠有效降低生產(chǎn)成本、營銷成本[1]，越來越多的企業(yè)開始使用云技術(shù).隨著云計(jì)算和移動(dòng)互聯(lián)網(wǎng)的發(fā)展，云計(jì)算與移動(dòng)互聯(lián)網(wǎng)的結(jié)合使得移動(dòng)云計(jì)算也成為一大研究熱點(diǎn).移動(dòng)云計(jì)算是在社會(huì)網(wǎng)絡(luò)，移動(dòng)計(jì)算，云計(jì)算融合的背景下產(chǎn)生的，移動(dòng)云計(jì)算依靠云端提供的存儲(chǔ)，計(jì)算，平臺(tái)等彈性資源，通過網(wǎng)絡(luò)向移動(dòng)用戶提供隨時(shí)隨地的服務(wù).移動(dòng)云計(jì)算能為移動(dòng)應(yīng)用提供穩(wěn)定可靠的服務(wù)，ServiceNow機(jī)構(gòu)的最新調(diào)查結(jié)果顯示，52%的企業(yè)愿意將自己的項(xiàng)目部署在云中*The 2016 Cloud ComputingTipping Points.http://cloudtweaks.com/2016/11/2016-cloud-computing-tipping-points/,2016..

隨著移動(dòng)互聯(lián)網(wǎng)的發(fā)展，人與人之間的聯(lián)系越來越緊密，人與人之間協(xié)同交互的需求也變得越來越強(qiáng)烈，協(xié)同工作正在從普通需求變成隨時(shí)隨地的必要需求，而且越來越多的用戶希望能夠借助移動(dòng)設(shè)備進(jìn)行協(xié)同交互.由于移動(dòng)設(shè)備所處網(wǎng)絡(luò)環(huán)境的復(fù)雜性和其本身計(jì)算資源的限制，設(shè)計(jì)跨平臺(tái)、可靠和穩(wěn)定的協(xié)同應(yīng)用是十分必要的.近年來協(xié)同系統(tǒng)領(lǐng)域的應(yīng)用多以在線服務(wù)的形式提供，比如在線文檔協(xié)作服務(wù)：Google Docs*Google Docs-Create and share your work online.http://docs.google.com/,2015.，Microsoft Office 365*Microsoft Office 365.https://office.live.com/,2016.；在線集成開發(fā)環(huán)境：Cloud9 IDE*Cloud9 IDE.https://c9.io/,2016；在線協(xié)同繪圖服務(wù)：ProcessOn*ProcessOn.https://www.processon.com/,2016.等.

2 相關(guān)工作

一致性維護(hù)技術(shù)是保證協(xié)同系統(tǒng)正確性的關(guān)鍵技術(shù)，操作轉(zhuǎn)換(OT)技術(shù)是一致性維護(hù)最常用的技術(shù).基于操作轉(zhuǎn)換技術(shù)的協(xié)同控制算法有很多，比如：GOT[7]，COT[8,9]，ABT[10]，ABST[19]等，然而這些算法的研究和設(shè)計(jì)都是基于點(diǎn)對(duì)點(diǎn)的分布式架構(gòu).而且，近些年來的研究中[2-6]，基于點(diǎn)對(duì)點(diǎn)的分布式架構(gòu)在協(xié)同系統(tǒng)的設(shè)計(jì)中依舊被廣泛采用.雖然基于點(diǎn)對(duì)點(diǎn)架構(gòu)的協(xié)同系統(tǒng)易于設(shè)計(jì)和實(shí)現(xiàn)，但是在移動(dòng)互聯(lián)網(wǎng)時(shí)代，這樣的架構(gòu)設(shè)計(jì)很難滿足移動(dòng)用戶協(xié)同交互的需求.

隨著移動(dòng)互聯(lián)網(wǎng)和云計(jì)算的發(fā)展，移動(dòng)云環(huán)境下協(xié)同應(yīng)用的研究已經(jīng)成為了一大熱點(diǎn)[11-15].Web應(yīng)用具有天然的跨平臺(tái)特性，云環(huán)境下采用Client/Server集中式架構(gòu)的Web協(xié)同應(yīng)用正在成為協(xié)同系統(tǒng)研究和設(shè)計(jì)的方向.在過去的研究中[7-10,19]，算法的設(shè)計(jì)和實(shí)現(xiàn)采用的是點(diǎn)對(duì)點(diǎn)的分布式架構(gòu)，這些算法并不能直接應(yīng)用在集中式架構(gòu)的云環(huán)境中.在基于操作轉(zhuǎn)換技術(shù)的協(xié)同控制算法中，Google Wave所采用的Jupiter[16]算法和Bin Shao等人提出的TIPS[17]協(xié)議是目前僅有的兩個(gè)支持集中式架構(gòu)的算法[20].然而，Jupiter算法并不是完美的，在一些特定的情景下算法并不能得到正確的結(jié)果.TIPS算法使用HTTP協(xié)議并經(jīng)過了正確性證明的同步協(xié)議，但是TIPS算法并不能達(dá)到嚴(yán)格意義上的實(shí)時(shí)協(xié)同.TIPS算法的實(shí)時(shí)性取決于客戶端設(shè)定的間隔時(shí)間τ，客戶端在每個(gè)τ時(shí)間結(jié)束時(shí)向服務(wù)器請(qǐng)求其他協(xié)同站點(diǎn)的操作，也既是客戶端用戶最快在τ時(shí)間后才能看見其他站點(diǎn)用戶的協(xié)同效果.并且τ值的設(shè)定存在困難和爭(zhēng)議，如果τ值設(shè)置的太大，系統(tǒng)的實(shí)時(shí)性就降低了；如果τ值設(shè)置的太小，客戶端向服務(wù)端的請(qǐng)求就越頻繁，系統(tǒng)負(fù)載就越大.并且由于云服務(wù)的分布式特點(diǎn)，Jupiter算法和TIPS算法都不能直接應(yīng)用在移動(dòng)云環(huán)境中.

圖1 HTTP協(xié)議與WebSocket協(xié)議使用過程對(duì)比Fig.1 Comparison of HTTP protocol and WebSocket protocol

采用WebSocket協(xié)議的Web的應(yīng)用已經(jīng)能夠?qū)崿F(xiàn)與服務(wù)端實(shí)時(shí)的全雙工通信[18].HTTP協(xié)議與WebSocket協(xié)議的對(duì)比如圖1所示.本文使用WebSocket協(xié)議代替HTTP協(xié)議并對(duì)TIPS算法進(jìn)行重新設(shè)計(jì)和改進(jìn)，使改進(jìn)后的TIPS算法能應(yīng)用于移動(dòng)云環(huán)境中.本文的后續(xù)工作安排如下：第三部分提出算法的設(shè)計(jì)與分析；第四部分研究算法在實(shí)時(shí)協(xié)同圖形編輯系統(tǒng)中的應(yīng)用；第五部分提出CloudDraw系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)；文章的總結(jié)與展望將在第六部分提出.

3 移動(dòng)云環(huán)境下實(shí)時(shí)協(xié)同算法的設(shè)計(jì)與分析

移動(dòng)云環(huán)境下的實(shí)時(shí)協(xié)同交互式應(yīng)用對(duì)傳統(tǒng)的采用點(diǎn)對(duì)點(diǎn)架構(gòu)的算法提出了新的挑戰(zhàn)，這些挑戰(zhàn)主要來自于以下方面的變化和特點(diǎn)：

1.架構(gòu)的變化：基于移動(dòng)云環(huán)境的應(yīng)用大都采用的是Client/Server集中式架構(gòu)，采用點(diǎn)對(duì)點(diǎn)分布式架構(gòu)的算法并不能應(yīng)用在移動(dòng)云環(huán)境下.因此，算法的設(shè)計(jì)要能滿足集中式架構(gòu)，并且算法要能保證服務(wù)端和客戶端共享數(shù)據(jù)的一致性.

2.客戶端的變化：傳統(tǒng)的協(xié)同應(yīng)用主要面向的是桌面環(huán)境，但在移動(dòng)云環(huán)境下移動(dòng)設(shè)備則是主要的應(yīng)用環(huán)境.算法在設(shè)計(jì)時(shí)必須考慮到移動(dòng)設(shè)備在電源、存儲(chǔ)、計(jì)算等資源方面的限制，因此算法應(yīng)當(dāng)設(shè)計(jì)的簡(jiǎn)單和高效.

3.移動(dòng)用戶動(dòng)態(tài)變化的特點(diǎn)：移動(dòng)用戶具有隨時(shí)加入、隨時(shí)離開的動(dòng)態(tài)特點(diǎn).算法的設(shè)計(jì)應(yīng)當(dāng)具有一定的健壯性，要能滿足移動(dòng)用戶動(dòng)態(tài)變化的特點(diǎn).

圖2 移動(dòng)用戶使用云服務(wù)進(jìn)行協(xié)同工作Fig.2 Collaborative work among mobile users by cloud service

4.服務(wù)端分布式特點(diǎn)：云服務(wù)是由多臺(tái)物理計(jì)算機(jī)提供的可靠服務(wù)，同一群組內(nèi)的不同用戶可以使用不同的計(jì)算機(jī)提供的服務(wù)，如圖2所示.因此，算法的設(shè)計(jì)應(yīng)當(dāng)考慮到數(shù)據(jù)分布式存儲(chǔ)的的特點(diǎn).

圖3 客戶端與服務(wù)端交互流程Fig.3 Process of interaction between client and server

本文采用WebSocket協(xié)議作為客戶端和服務(wù)器的通信協(xié)議.客戶端與服務(wù)器的交互過程如圖3所示，客戶端：本地生成的操作會(huì)立即執(zhí)行，執(zhí)行完畢后存儲(chǔ)在Tj中.客戶端收到服務(wù)器發(fā)送的數(shù)據(jù)后，經(jīng)過處理后將本地產(chǎn)生的操作序列Tj發(fā)送到服務(wù)器.相比TIPS，本研究中客戶端被動(dòng)的等待服務(wù)器推送的數(shù)據(jù)，客戶端無需設(shè)定間隔時(shí)間τ，無需在每個(gè)τ時(shí)間結(jié)束時(shí)向服務(wù)器發(fā)起請(qǐng)求，大大降低了客戶端的負(fù)載.RQj是接收隊(duì)列，用來保存從服務(wù)器接收的操作.服務(wù)端：RBCj負(fù)責(zé)存儲(chǔ)客戶端j發(fā)來的操作序列；RBSj存儲(chǔ)服務(wù)器j發(fā)送的操作集合，這些操作來自服務(wù)器j所服務(wù)的客戶端；SBCj中存儲(chǔ)的則是經(jīng)過服務(wù)器處理后即將發(fā)送到客戶端j的操作序列；SBSj存儲(chǔ)本服務(wù)器即將發(fā)送到服務(wù)器j的操作序列，這些操作來自于本服務(wù)器所服務(wù)的客戶端，算法的詳細(xì)設(shè)計(jì)會(huì)在下節(jié)給出.

3.1 客戶端算法設(shè)計(jì)

考慮到移動(dòng)設(shè)備資源受限的特點(diǎn)，客戶端算法應(yīng)設(shè)計(jì)的簡(jiǎn)單和高效.客戶端連接到云服務(wù)后直接從服務(wù)器獲取文檔副本，并初始化相關(guān)數(shù)據(jù)結(jié)構(gòu)，客戶端的兩個(gè)主要線程分別負(fù)責(zé)處理本地操作和遠(yuǎn)程數(shù)據(jù)，算法如Algorithm 1所示.

Algorithm1：ControlProcedureonClientj1． Initialization：2． Tj=[]；RQj=[]；3． getdocumentreplicafromServer4． Thread1：5． executealocaloperationo6． Tj=ERMerge(o，Tj)；7． Thread2：8． casesq：9． receivetheremoteoperationsequencesqfromServer10． RQj=RQj+sq；11． sq′=RQj；RQj=[]；12． executearemoteoperationsequencesq′13． sq′′=ITSQ(sq′，Tj)；14． executesq′′onlocaldocument15． Tj′=ITSQ(Tj，sq′)；16． sendtheTj′toServer17． casePUSH：18． sendthelocaloperationsequenceTjtoServerdirectly

在Algorithm 1中，Tj存儲(chǔ)本地生成的操作集合，需要注意的是這些操作的存放順序是滿足”effects relation”的關(guān)系，”effects relation”是ABT[10]理論中提出的概念，按”effects relation”排序的兩個(gè)操作序列在進(jìn)行操作轉(zhuǎn)換時(shí)能大大的提高轉(zhuǎn)換效率；RQj存儲(chǔ)服務(wù)端發(fā)來的操作.線程1負(fù)責(zé)本地操作的執(zhí)行：本地生成的操作o立即執(zhí)行，執(zhí)行后線程1將操作o加入到本地操作集合Tj中.ERMerge算法[17]的作用是將操作o保持”effects relation”的順序加入到Tj中.線程2負(fù)責(zé)接收并處理服務(wù)器發(fā)送的數(shù)據(jù)：當(dāng)客戶端接收到服務(wù)器發(fā)送操作序列sq時(shí)，客戶端將sq與本地執(zhí)行過的操作序列Tj進(jìn)行操作轉(zhuǎn)換，轉(zhuǎn)換后的結(jié)果則在本地立即執(zhí)行.之后，客戶端將操作序列Tj與sq進(jìn)行操作轉(zhuǎn)換后的結(jié)果發(fā)送到服務(wù)器.ITSQ算法的作用是對(duì)兩個(gè)操作序列做包含轉(zhuǎn)換[19].當(dāng)客戶端接收到服務(wù)器發(fā)送的”PUSH”字符串時(shí)，說明服務(wù)器當(dāng)前沒有接收到任何的操作序列，這時(shí)客戶端直接將本地執(zhí)行過的操作序列Tj發(fā)送到服務(wù)器即可.與TIPS算法相比，本算法采用WebSocket協(xié)議，并且客戶端未設(shè)定間隔時(shí)間τ.

3.2 服務(wù)端算法設(shè)計(jì)

服務(wù)端算法不僅要能適應(yīng)移動(dòng)用戶動(dòng)態(tài)變化的特點(diǎn)，而且應(yīng)當(dāng)是分布式的算法，服務(wù)端算法如Algorithm 2所示.服務(wù)端每隔τ時(shí)間向客戶端發(fā)送一次數(shù)據(jù)，τ是可以動(dòng)態(tài)配置的.如果當(dāng)前系統(tǒng)負(fù)載較大，τ可以設(shè)置為較小的值以減輕系統(tǒng)負(fù)載，相反τ可以設(shè)置為較大的值以提高系統(tǒng)的實(shí)時(shí)性，文章將在算法的分析中討論τ值對(duì)系統(tǒng)負(fù)載的影響.本文規(guī)定各個(gè)服務(wù)端擁有相同的τ，以保證服務(wù)端能提供整體一致的服務(wù).線程1負(fù)責(zé)將SBC存儲(chǔ)序列中的操作發(fā)送到客戶端，當(dāng)SBC中沒有操作時(shí)，服務(wù)端發(fā)送”PUSH”字符串到客戶端.線程2負(fù)責(zé)接收客戶端發(fā)來的操作，并將這些操作發(fā)送到其他服務(wù)端，目的是使服務(wù)端共享所有客戶端的數(shù)據(jù)，保證數(shù)據(jù)的一致性.隨后，服務(wù)端將客戶端發(fā)送的操作和其他服務(wù)端發(fā)送的操作進(jìn)行合并，并在本地文檔中執(zhí)行這些操作，之后將這些操作提取到發(fā)送隊(duì)列SBC中，準(zhǔn)備發(fā)送到相應(yīng)的客戶端.

Algorithm2：ControlProcedureonServerj1． Initialization：2． ?i：RBCi=[]；SBCi=[]；RBSi=[]；RBSi=[]；3． Thread1：4． senddatatoclient5． ?j：6． sqj=extractRemotes(SBCj，j)；7． ifsqjisnull：send“PUSH”toClientj；8． else：sendsqjtoClientj；SBCj=[]；9． Thread2：10． receiveoperationsequenceTjfromClientj11． RBCj=serializedMerge(RBCj，Tj)；12． ?i：SBSi=serializedMerge(SBSi，Tj)；13． sendtheoperationsequencetootherServer14． ?i：sendSBSitoServeri；SBSi=[]；15． msq=nwayMerge([RBC1，…，RBCn，RBS1，…，RBSn])；16． ?i：RBCi=[]；RBSi=[]；17． executemsgonlocaldocument18． ?i：SBCi=serializedMerge(SBCi，msq)；

extractRemotes算法的作用是從SBC中提取相應(yīng)的操作發(fā)送到客戶端；serializedMerge算法的作用是將兩個(gè)滿足依賴關(guān)系的操作序列合并成一個(gè)按”effects relation”排序的整體操作序列；nwayMerge算法的作用是合并n個(gè)按”effects relation”排序并且上下文相同的操作序列為一個(gè)整體操作序列.這些算法在過去的研究[17]中已經(jīng)給出，這不是本文研究的重點(diǎn).本研究將大部分的任務(wù)放到服務(wù)端來完成，服務(wù)端的算法相對(duì)復(fù)雜，這樣設(shè)計(jì)的目的是為了減輕客戶端的負(fù)載.服務(wù)端具有很好的可擴(kuò)展性，主要表現(xiàn)在以下兩點(diǎn)：

1)新加入的客戶端可以連接到云服務(wù)中任何一臺(tái)服務(wù)器，并獲取該服務(wù)器中的文檔副本.服務(wù)端通過RBC，SBC這些數(shù)據(jù)結(jié)構(gòu)來標(biāo)識(shí)對(duì)應(yīng)的客戶端數(shù)據(jù)，當(dāng)有客戶端加入或退出時(shí)，服務(wù)端只需要分配或撤銷對(duì)應(yīng)的RBC，SBC即可，滿足了客戶端動(dòng)態(tài)變化的特點(diǎn).

2)由于服務(wù)端共享所有客戶端的操作數(shù)據(jù)，當(dāng)有新的服務(wù)器加入時(shí)可以直接從相鄰的服務(wù)器獲取文檔副本和當(dāng)前客戶端的操作數(shù)據(jù).因此，服務(wù)端具有一定的可擴(kuò)展性.

3.3 算法效率分析

客戶端：客戶端算法中主要的耗時(shí)操作是ITSQ算法，如Algorithm 1第12、14行所示.本文對(duì)ITSQ算法在移動(dòng)設(shè)備中運(yùn)行耗時(shí)做了測(cè)試.硬件環(huán)境：擁有3G RAM，2.5 GHz高通801四核CPU的小米Note手機(jī)；運(yùn)行環(huán)境：Chrome 53.0.2785.124；操作系統(tǒng)：Android 6.0.1；開發(fā)語言：JavaScript.本文測(cè)試時(shí)設(shè)定操作序列T的長(zhǎng)度為10，隨著sq序列中操作數(shù)量的增加，ITSQ(sq,T)和ITSQ(T,sq)的運(yùn)行耗時(shí)情況如圖4所示.如圖4所示，當(dāng)sq序列中的操作數(shù)量超過10000時(shí)ITSQ(sq,T)算法的耗時(shí)會(huì)急劇上升.然而在實(shí)際的協(xié)同系統(tǒng)中，為了保證用戶的體驗(yàn)性協(xié)同系統(tǒng)內(nèi)用戶的數(shù)量是有一定限制的.試想：1000個(gè)用戶同時(shí)編輯一個(gè)文檔有何意義？因此，在實(shí)際情況下sq序列中的操作數(shù)量遠(yuǎn)沒有這么大.

圖4 移動(dòng)設(shè)備環(huán)境下ITSQ算法運(yùn)行分析Fig.4 Analysis of ITSQ algorithm in the environment of mobile device

服務(wù)端：服務(wù)端相對(duì)客戶端更加復(fù)雜.經(jīng)分析，τ值的設(shè)定對(duì)系統(tǒng)負(fù)載有較大的影響.本文測(cè)試了τ的不同取值對(duì)系統(tǒng)的影響.測(cè)試環(huán)境：同一局域網(wǎng)內(nèi)擁有4GB RAM、3.3GHz奔騰雙核CPU配置的三臺(tái)服務(wù)器.本文使用腳本程序來模擬客戶端，并設(shè)定每臺(tái)服務(wù)器服務(wù)于100個(gè)腳本程序且每個(gè)腳本程序每秒產(chǎn)生10個(gè)操作.本文使用算法執(zhí)行時(shí)間和服務(wù)端數(shù)據(jù)交換時(shí)間來衡量系統(tǒng)負(fù)載.經(jīng)測(cè)試，τ值對(duì)系統(tǒng)負(fù)載的影響如圖5所示.

圖5 不同τ值對(duì)系統(tǒng)負(fù)載的影響Fig.5 System load

如圖5所示，當(dāng)τ值大于1000ms時(shí)，系統(tǒng)負(fù)載開始明顯增大.這主要是因?yàn)樵讦訒r(shí)間內(nèi)客戶端產(chǎn)生了大量的操作數(shù)據(jù)，服務(wù)端之間的數(shù)據(jù)轉(zhuǎn)發(fā)以及數(shù)據(jù)的合并成為了主要耗時(shí)的操作.當(dāng)τ值很小時(shí)，系統(tǒng)負(fù)載不下降反而上升，是因?yàn)殡m然τ時(shí)間內(nèi)產(chǎn)生的操作數(shù)據(jù)不多，但是在單位時(shí)間內(nèi)服務(wù)端相互之間的請(qǐng)求次數(shù)過多，浪費(fèi)了大量的CPU資源.在本測(cè)試環(huán)境下τ取值大約在500ms時(shí)系統(tǒng)的整體負(fù)載最小.

相比TIPS算法，本算法的優(yōu)勢(shì)主要體現(xiàn)在以下兩個(gè)方面：

1)本文提出的客戶端算法移除了間隔時(shí)間τ，客戶端無需再每個(gè)τ時(shí)間結(jié)束時(shí)向服務(wù)器發(fā)出請(qǐng)求，大大降低了客戶端的負(fù)載.

2)本文提出的服務(wù)端算法能處理分布在其他服務(wù)端的數(shù)據(jù)，不僅對(duì)客戶端在擴(kuò)展性方面有較好的支持，而且服務(wù)端也有很強(qiáng)的可擴(kuò)展性.

4 算法在實(shí)時(shí)協(xié)同圖形編輯系統(tǒng)中的應(yīng)用

4.1 文檔模型定義

圖形編輯系統(tǒng)中繪圖文檔是二維空間，定義為PAINT={START,END,DOC},其中START和END分別是繪圖文檔的開始和結(jié)束坐標(biāo)，DOC是存儲(chǔ)圖形文檔中所有圖形對(duì)象的線性隊(duì)列.如圖6所示，擁有三個(gè)圖形對(duì)象的繪圖文檔表示為PAINT={(0,0),(100,100),{O1,O2,O3}}.

圖6 擁有三個(gè)圖形對(duì)象的圖形文檔Fig.6 Graphic document

圖形對(duì)象是基于對(duì)象的圖形編輯系統(tǒng)中最基本的單元，圖形對(duì)象可以是：線段、矩形、圓形、三角形等，這些對(duì)象擁有類型、填充色、透明度等屬性.因此，圖形對(duì)象定義為：obj= {TYPE,ATTR,Z-INDEX}.TYPE：圖形對(duì)象的類型，類型包括線段、矩形、圓形、三角形等.ATTR：該圖形對(duì)象所擁有的屬性對(duì)象.ATTR={FILL_COLOR,TRANS,POINTS}，為簡(jiǎn)化設(shè)計(jì)與分析，本文暫時(shí)只考慮了三種屬性類型.其中FILL_COLOR和TRANS分別表示該對(duì)象的填充顏色和透明度.POINTS表示該對(duì)象在圖形文檔中的坐標(biāo)數(shù)組.例如：可用兩個(gè)點(diǎn)表示一條線段，可用n個(gè)點(diǎn)表示一條曲線.Z-INDEX：圖形對(duì)象在DOC中存儲(chǔ)位置，新的圖形對(duì)象生成時(shí)，該對(duì)象的Z-INDEX值為當(dāng)前線性文檔DOC的長(zhǎng)度.

4.2 二維繪圖空間映射為線性結(jié)構(gòu)

圖形對(duì)象的Z-INDEX屬性表示該對(duì)象在線性文檔中的存儲(chǔ)位置，例如：用戶先后生成了三個(gè)圖形對(duì)象O1,O2,O3,則這三個(gè)對(duì)象一定是以O(shè)1,O2,O3的順序繪制在圖形文檔和存儲(chǔ)于線性文檔DOC中的，如圖7所示.只要保證線性文檔DOC的一致性，就能保證圖形對(duì)象在圖形文檔中繪制順序的一致性，從而保證了圖形文檔的一致性.

圖7 二維空間映射為線性結(jié)構(gòu)Fig.7 Mapping the two-dimension space to the linear structure

用戶對(duì)二維圖形文檔的操作可以轉(zhuǎn)化為對(duì)線性文檔DOC的操作，本文將圖形編輯操作轉(zhuǎn)化為線性編輯操作：create(OBJ)是在圖形文檔中創(chuàng)建了一個(gè)圖形對(duì)象的操作，相當(dāng)于insert(OBJ,OBJ.Z-INDEX)，既是在線性文檔DOC的OBJ.Z_INDEX位置插入了一個(gè)對(duì)象OBJ；remove(OBJ)是從圖形文檔中移除圖形對(duì)象OBJ的操作，相當(dāng)于delete(OBJ,OBJ.Z-INDEX)，既是刪除線性文檔DOC中位置為OBJ.Z-INDEX處的對(duì)象；change(OBJ,ATTR.name,old,new)是更新圖形對(duì)象OBJ的操作，相當(dāng)于update(OBJ,OBJ.Z-INDEX,ATTR.name,old,new)既是在線性文檔DOC中更新位置為OBJ.Z-INDEX處的對(duì)象.

4.3 一致性維護(hù)策略及算法的應(yīng)用

在過去的理論研究中[7-10]操作轉(zhuǎn)換技術(shù)是協(xié)同文本編輯系統(tǒng)中一致性維護(hù)最常用的技術(shù)，TIPS算法是在ABT[10]算法的基礎(chǔ)上改進(jìn)的適用于Web環(huán)境的協(xié)同文本編輯系統(tǒng)中一致性維護(hù)算法.本文通過將二維圖形空間映射為線性空間和將二維圖形編輯操作轉(zhuǎn)換為線性編輯操作，文章將協(xié)同圖形編輯系統(tǒng)的一致性維護(hù)問題轉(zhuǎn)化為了協(xié)同文本編輯系統(tǒng)的一致性維護(hù)問題.因此，基于操作轉(zhuǎn)換技術(shù)的協(xié)同控制算法就能很好的解決協(xié)同圖形編輯系統(tǒng)中一致性維護(hù)問題.本文借助TIPS理論中的相關(guān)算法來解決協(xié)同文本編輯系統(tǒng)中的一致性維護(hù)問題，通過本文提出的映射理論即能解決協(xié)同圖形編輯系統(tǒng)中的一致性維護(hù)問題.TIPS理論中關(guān)于協(xié)同文本編輯系統(tǒng)中一致性維護(hù)策略已經(jīng)在ABT[10]理論中得到了細(xì)致的研究和嚴(yán)謹(jǐn)?shù)淖C明，本文不再贅述.

在正確的使用基于操作轉(zhuǎn)換的控制算法處理實(shí)時(shí)協(xié)同圖形編輯系統(tǒng)中一致性維護(hù)問題之前，需要將二維的圖形編輯操作轉(zhuǎn)換成線性的文本編輯操作.控制算法如Algorithm 3所示.

Algorithm3：ControlproceduceoftheClient1． Initialization：2． DOC=[]；3． Thread1：3． handlelocalgraphicsoperationo4． o．Z?INDEX=DOC．length；5． o′=conversionOP(o)；6． handlethelocaloperationo′byAlgorithm17． Thread2：8． ifDOCischange：9． re?drawallgraphicsobjectonlocaldocument

如Algorithm 3，線程1的作用是將用戶生成的圖形編輯操作o轉(zhuǎn)換成線性的操作o′，注意操作o生成時(shí)其Z-INDEX屬性值為當(dāng)前DOC文檔的長(zhǎng)度，轉(zhuǎn)換后的線性操作o′由Algorithm 1處理.線程2的作用時(shí)監(jiān)控DOC文檔變化，當(dāng)DOC中有操作被改變時(shí)，重新將DOC中的圖形對(duì)象繪制到圖形文檔中，以呈現(xiàn)給用戶最新的視圖.

Algorithm4：conversionOP(o)：o′1． if(o．type==create)：2． o′．type=insert；3． elseif(o．type==remove)：4． o′．type=delete；5． else：6． o′．type=update；8． o′．obj=o．obj；9． o′．pos=o．obj．z?index；10． returno′；

二維圖形操作轉(zhuǎn)換為線性文本操作的算法如Algorithm 4所示.經(jīng)過本章的研究和嘗試，可以很好的將基于操作轉(zhuǎn)換技術(shù)的協(xié)同控制算法應(yīng)用于解決實(shí)時(shí)協(xié)同圖形編輯系統(tǒng)中一致性維護(hù)問題.

5 CloudDraw原型系統(tǒng)

為了驗(yàn)證本文提出的算法的正確性，文章開發(fā)了基于HTML5 WebSocket的實(shí)時(shí)協(xié)同圖形編輯系統(tǒng)：CloudDraw.CloudDraw是基于Web環(huán)境的集中式架構(gòu)的實(shí)時(shí)協(xié)同圖形編輯系統(tǒng).

客戶端：采用HTML5 WebSocket協(xié)議和JQuery EasyUI框架的Web App.基于HTML5的Web App具有開發(fā)成本低、更新速度快、跨平臺(tái)和終端等優(yōu)點(diǎn).CloudDraw系統(tǒng)客戶端繪圖面板如圖8(a)所示，繪圖界面包含三個(gè)部分：上方區(qū)域的Fill Color和Line Color選擇框可以分別設(shè)定圖形對(duì)象的填充色彩和線條色彩；左側(cè)區(qū)域的圖形按鈕可以設(shè)定當(dāng)前要繪制的圖形類型，可以選擇繪制線條、矩形、圓形等類型；右側(cè)區(qū)域是繪圖面板.用戶信息界面如圖8(b)所示，用戶信息界面展現(xiàn)了當(dāng)前系統(tǒng)在線的用戶，如圖所示當(dāng)前系統(tǒng)有兩個(gè)在線用戶.實(shí)時(shí)消息界面如圖8(c)所示，用戶可以在消息界面實(shí)時(shí)的看到系統(tǒng)產(chǎn)生的消息.

圖8 CloudDraw用戶界面Fig.8 User interface of CloudDraw

服務(wù)端：在同一局域網(wǎng)內(nèi)的三臺(tái)不同的服務(wù)器上來模擬云環(huán)境下的分布式服務(wù)，服務(wù)端網(wǎng)絡(luò)拓?fù)淙鐖D9所示.服務(wù)端程序采用Java 8語言和Eclipse J2EE工具開發(fā)，運(yùn)行在Tomcat 8.0應(yīng)用服務(wù)器環(huán)境中.

6 總結(jié)及展望

本文對(duì)TIPS算法進(jìn)行重新設(shè)計(jì)和改進(jìn)，將二維的繪圖空間映射為線性的結(jié)構(gòu)，并且將二維的圖形編輯操作轉(zhuǎn)換為線性的文本編輯操作.基于此，本文將改進(jìn)后的TIPS算法應(yīng)用于基于Web的實(shí)時(shí)協(xié)同圖形編輯系統(tǒng)中.根據(jù)本文的研究和嘗試得出以下結(jié)論：

1.通過將二維繪圖空間映射為線性結(jié)構(gòu)和將二維繪圖操作轉(zhuǎn)換為線性的操作，使得基于操作轉(zhuǎn)換的控制算法能很好的應(yīng)用于協(xié)同圖形編輯系統(tǒng)中.通過這種轉(zhuǎn)換可以將二維空間的一致性維護(hù)問題轉(zhuǎn)化為線性的一致性維護(hù)問題，大大降低了問題的復(fù)雜度.

2.移動(dòng)云環(huán)境下采用集中式架構(gòu)的實(shí)時(shí)協(xié)同系統(tǒng)的設(shè)計(jì)應(yīng)當(dāng)考慮到客戶端所在網(wǎng)絡(luò)的復(fù)雜性和自身計(jì)算資源的限制，客戶端的算法要盡量的簡(jiǎn)單，而且服務(wù)端應(yīng)具備一定的可擴(kuò)展性.基于HTML5的Web App具有開發(fā)效率高、開發(fā)成本低、跨平臺(tái)等優(yōu)點(diǎn).

圖9 服務(wù)端網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)Fig.9 Network topology of the server

在圖形編輯系統(tǒng)中Undo/Redo是非常重要的操作，能否將圖形編輯中的Undo/Redo操作轉(zhuǎn)換為文本編輯中的Undo/Redo操作和如何解決圖形編輯系統(tǒng)中用戶意愿一致性的問題，將是我們以后的工作重點(diǎn).

[1] Liu Yue.Overview of the cloud computing and research on the application of mobile cloud computimg[J].Information and Communications Technologies,2010,4(2):14-20.

[2] Fan Hong-fei,Sun Cheng-zheng.Supporting semantic conflict prevention in real-time collaborative programming environments[J].Acm Sigapp Applied Computing Review(SIGAPP),2012,12(2):39-52.

[3] Sun Cheng-zheng,Chen David.Consistency maintenance in real-time collaborative graphics editing systems[J].ACM Transactions on Computer-Human Interaction(TOCHI),2002,9(1):2181-2186.

[4] Claudia-Lavinia Ignat,Moira C.Norrie.Draw-together: graphical editor for collaborative drawing[C].Acm Conference on Computer Supported Cooperative Work(CSCW),2006:269-278.

[5] Song Hong-zhi,Qu Zhao-ming.Operational transformation algorithm with conflict detection and awareness methods for real-time collaborative editing in P2P environments[C].IEEE International Conference on Computer Science & Automation Engineering(CSAE),2011,17(5):571- 576.

[6] Li Rui-xuan,Yu Guang-can.P2P-based locking in?real-time?collaborative?editing systems [C].11th International Conference on Computer Supported Cooperative Work in Design(CSCW),2007:24- 29.

[7] Sun C,Jia X,Zhang Y,et al.Achieving convergence,causality preservation,and intention preservation in real-time cooperative editing systems[J].ACM Transactions on Computer-Human Interaction(TOCHI),1998,5(1):63-108.

[8] Sun D,Sun C.Operation context and context-based operational transformation [C].Acm Conference on Computer Supported Cooperative Work(CSCW),2006:279-288.

[9] Sun D,Sun C.Context-based operational transformation in distributed collaborative editing systems [J].IEEE Transactions on Parallel & Distributed Systems(TPDS),2009,20(10):1454-1470.

[10] Li D,Li R.An admissibility-based operational transformation framework for collaborative editing systems [C].Computer Supported Cooperative Work(CSCW),2010,19(1):1-43.

[11] Wang W H,Hao Y M,Cao Y H,et al.A cloud-based real-time mobile collaboration wiki system [C].Applied Mechanics & Materials,2013,441:928-931.

[12] Guetmi N，Mechaoui M D,et al.Mobile collaboration: a collaborative editing service in the cloud [C].30thAnnual ACM Symposium on Applied Computing(SAC),2015,(2): 509-512.

[13] Alshahwan F,Faisal M,Ansa G,et al.Security framework for RESTful mobile cloud computing Web services [J].Journal of Ambient Intelligence & Humanized Computing(JAIHC),2015,(1):1-11.

[14] Cheng X,Yu J.Designing of a mobile collaboration application for student collaborative group work: evidence from china [C].48thHawaii International Conference on System Sciences(HICSS),2015:544-551.

[15] Kovachev D,Nicolaescu P,Klamma R,et al.Mobile real-time collaboration for semantic multimedia [J].Mobile Networks and Applications(MONET),2014,19(5):635-648.

[16] Nichols D A,Curtis P,Dixon M,et al.High-latency,low-bandwidth windowing in the Jupiter collaboration system [C].Acm Symposium on User Interface & Software Technology(UIST),1995,46(2):111-120.

[17] Shao B,Li D,Lu T,et al.An operational transformation based synchronization protocol for web 2.0 applications [C].In Proceedings of the ACM 2011 Conference on Computer Supported Cooperative Work(CSCW),2011:563-572.

[18] Imre G,Mezei G,et al.Introduction to a Web socket benchmarking infrastructure[C].Zooming Innovation in Consumer Electronics International Conference (ZINC),2016: 84-87.

[19] Bin Shao,Du Li,et al.A fast operational transformation algorithm for mobile and asynchronous collaboration[J].Parallel & Distributed Systems IEEE Transactions on(TPDS),2010,21(12): 1707-1720.

[20] Xia Huan-huan.Research and application of adress space tran sformation key technique based on environment of mobile cloud[D].Shanghai:Fudan University,2014..

附中文參考文獻(xiàn)：

[1] 劉 越.云計(jì)算綜述與移動(dòng)云計(jì)算的應(yīng)用研究[J].信息通信技術(shù)，2010,4(2):14-20.

[20] 夏歡歡.移動(dòng)云環(huán)境下地址空間轉(zhuǎn)換關(guān)鍵技術(shù)研究及應(yīng)用[D].上海：復(fù)旦大學(xué)，2014.