移動(dòng)平臺(tái)下實(shí)時(shí)協(xié)同關(guān)聯(lián)圖文檔模型一致性維護(hù)算法研究

高麗萍，張 鑫

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

1 引 言

移動(dòng)計(jì)算是隨著移動(dòng)通信、互聯(lián)網(wǎng)、數(shù)據(jù)庫(kù)、分布式計(jì)算等技術(shù)的發(fā)展而興起的新技術(shù)，它使得計(jì)算機(jī)或其他信息智能終端設(shè)備在無(wú)線環(huán)境下實(shí)現(xiàn)數(shù)據(jù)傳輸及資源共享.伴隨著移動(dòng)計(jì)算的迅速發(fā)展，將其與計(jì)算機(jī)支持的協(xié)同工作(Computer Supported Cooperative Work，CSCW)結(jié)合，是當(dāng)下研究的熱門領(lǐng)域之一.移動(dòng)協(xié)同計(jì)算利用移動(dòng)計(jì)算靈活性高的特點(diǎn)，將傳統(tǒng)PC端工作移植到移動(dòng)端上來(lái)，使得人們可以隨時(shí)隨地協(xié)同辦公，從而可以大大提高工作的效率.

計(jì)算機(jī)支持的協(xié)同工作(CSCW)是指多個(gè)在地域上分散的用戶在同一時(shí)間并發(fā)地對(duì)共享的同一文檔進(jìn)行編輯.它強(qiáng)調(diào)的是人與人之間的交互，對(duì)交互過(guò)程中的響應(yīng)性和并行性有較高的要求，同時(shí)近年來(lái)在網(wǎng)絡(luò)穩(wěn)定P2P環(huán)境下設(shè)計(jì)的一致性維護(hù)算法，很好地保證了協(xié)同工作用戶實(shí)時(shí)畫面的一致性.但是隨著移動(dòng)互聯(lián)網(wǎng)的發(fā)展，越來(lái)越多的人們希望能夠在移動(dòng)設(shè)備上實(shí)現(xiàn)協(xié)同工作.

移動(dòng)協(xié)同工作的網(wǎng)絡(luò)環(huán)境，大多數(shù)情況下沒有基于點(diǎn)對(duì)點(diǎn)方式的協(xié)同應(yīng)用來(lái)的穩(wěn)定，有時(shí)由于網(wǎng)絡(luò)的不穩(wěn)定性造成某些操作無(wú)法成功廣播給系統(tǒng)內(nèi)其他協(xié)同站點(diǎn)，導(dǎo)致站點(diǎn)內(nèi)與丟失操作具有因果關(guān)聯(lián)關(guān)系的操作無(wú)法順利執(zhí)行.針對(duì)移動(dòng)網(wǎng)絡(luò)的不穩(wěn)定性，本文在移動(dòng)通信C/S架構(gòu)的基礎(chǔ)上，對(duì)傳統(tǒng)操作轉(zhuǎn)換算法(Operation Transformation，OT)進(jìn)行改進(jìn)，設(shè)計(jì)了移動(dòng)協(xié)同環(huán)境下并發(fā)控制算法.與傳統(tǒng)OT算法不同，該算法中客戶端與服務(wù)器端協(xié)同工作，客戶端本地操作立即執(zhí)行的同時(shí)，增加了丟失操作的檢測(cè)與重發(fā)請(qǐng)求；而服務(wù)器不僅完成基本的遠(yuǎn)程操作轉(zhuǎn)發(fā)廣播任務(wù)，還增設(shè)了操作重發(fā)請(qǐng)求的處理機(jī)制，用于處理缺失操作站點(diǎn)所發(fā)出的操作重發(fā)請(qǐng)求.該做法類似于在服務(wù)器端加入操作緩存機(jī)制，從而保證了各站點(diǎn)順利執(zhí)行.并在以上機(jī)制基礎(chǔ)上，針對(duì)實(shí)時(shí)協(xié)同圖形編輯系統(tǒng)下對(duì)象關(guān)聯(lián)的特點(diǎn)，在OT基礎(chǔ)上增加了位移(Move)操作，關(guān)聯(lián)操作(Relate)和關(guān)聯(lián)解除操作(Relieve)的定義，根據(jù)實(shí)際需求，將某些圖形對(duì)象之間的位置關(guān)系給與一定的關(guān)聯(lián)關(guān)系定義，使得關(guān)聯(lián)對(duì)象之間的位置能夠?qū)崿F(xiàn)聯(lián)動(dòng).并針對(duì)這些關(guān)系和操作之間的并發(fā)關(guān)系，定義沖突關(guān)系，設(shè)計(jì)相應(yīng)的沖突消解函數(shù)以保證圖形文檔的收斂性.

本文主要針對(duì)移動(dòng)平臺(tái)下實(shí)時(shí)協(xié)同關(guān)聯(lián)圖文檔的一致性維護(hù)算法展開研究.本文組織結(jié)構(gòu)如下：第二部分介紹了研究背景及相關(guān)工作；第三部分提出了實(shí)時(shí)協(xié)同圖形編輯中的一致性維護(hù)策略及給出實(shí)例證明；第四部分設(shè)計(jì)了移動(dòng)協(xié)同環(huán)境下的一致性控制算法；第五部分對(duì)以上改進(jìn)的控制算法和轉(zhuǎn)換函數(shù)進(jìn)行了模擬仿真實(shí)驗(yàn)并給出了實(shí)驗(yàn)分析；第六部分為了進(jìn)一步驗(yàn)證算法正確性與有效性，在Android平臺(tái)下開發(fā)了移動(dòng)協(xié)同圖形編輯系統(tǒng)Co-Paint；第七部分為全文的總結(jié)及展望.

2 相關(guān)工作

一致性維護(hù)是實(shí)時(shí)協(xié)同編輯系統(tǒng)中重要的研究課題，一致性維護(hù)技術(shù)是保證系統(tǒng)正確進(jìn)行的關(guān)鍵技術(shù).近年來(lái)，最常用的一致性維護(hù)技術(shù)主要分為兩大類：基于操作轉(zhuǎn)換[8，11-13](Operation Transformation，OT)技術(shù)和基于地址空間轉(zhuǎn)換[5](Address Space Transformation，AST)技術(shù).理論研究方面，基于前者的實(shí)時(shí)協(xié)同編輯并發(fā)控制算法較多，包括Ellis和Gibbs在文獻(xiàn)[1]中提出的dOPT算法，Sun和Ellis在文獻(xiàn)[2]提出的GOT和GOTO算法，以及Sun在文獻(xiàn)[3]提出的COT算法等；操作轉(zhuǎn)換算法在保證CCI特性及不影響當(dāng)前工作繼續(xù)的前提下，從操作本身出發(fā)，根據(jù)并發(fā)操作的執(zhí)行效果，修改自身操作位置參數(shù)，達(dá)到保持文檔一致性的目的.而基于AST[10]算法與前者最大的特點(diǎn)是從文檔狀態(tài)出發(fā)，將文檔的狀態(tài)地址空間回溯到操作產(chǎn)生時(shí)的狀態(tài)，在這個(gè)狀態(tài)下，我們可以直接找到操作的執(zhí)行位置，從而維護(hù)文檔的一致性.

目前為止，基于AST技術(shù)區(qū)別于基于OT技術(shù)的地方在于無(wú)法支持對(duì)非線性結(jié)構(gòu)文檔維護(hù)一致性，而OT技術(shù)則能夠很好地解決分布式協(xié)同非線性文檔的一致性問題.例如Sun等人在文獻(xiàn)[7]中提出基于OT技術(shù)采用多版本技術(shù)解決2D文檔模型下垂直交叉的沖突，維護(hù)了2D文檔一致性；Agustina等在文獻(xiàn)[9]中基于OT技術(shù)設(shè)計(jì)了合理的控制和轉(zhuǎn)換函數(shù)，從而有效地解決了3D系統(tǒng)中關(guān)聯(lián)圖文檔模型的關(guān)聯(lián)沖突問題；Chengzheng Sun等在文獻(xiàn)[6]中設(shè)計(jì)了基于字符串操作的轉(zhuǎn)換函數(shù)，有效保證了包含字符串操作的協(xié)同系統(tǒng)對(duì)于一致性的需求；另外，Chengzheng Sun等在文獻(xiàn)[15]中創(chuàng)新地提出了云存儲(chǔ)操作轉(zhuǎn)換函數(shù)(Cloud Storage Operational Transformation，CSOT)，實(shí)現(xiàn)了云存儲(chǔ)系統(tǒng)中實(shí)時(shí)同步共享樹形文檔結(jié)構(gòu)的收斂性.

協(xié)同圖形編輯環(huán)境涵蓋的圖形對(duì)象操作類型是多元化的，在某一些應(yīng)用場(chǎng)景內(nèi)需要維護(hù)圖形對(duì)象之間的位置關(guān)系，根據(jù)實(shí)際需求某些圖形對(duì)象的聯(lián)動(dòng)，故本文在三個(gè)基本圖形操作創(chuàng)建(Create)、刪除(Delete)、更新(Update)基礎(chǔ)上，提出了關(guān)聯(lián)操作(Relate)、關(guān)聯(lián)解除操作(Relieve)和位移操作(Move)，同時(shí)為了避免不同操作類型間引起的并發(fā)導(dǎo)致各系統(tǒng)站點(diǎn)文檔狀態(tài)的不一致性，設(shè)計(jì)合理的一致性維護(hù)操作轉(zhuǎn)換函數(shù)，從而保證各用戶圖形文檔滿足CCI模型.在協(xié)同處理時(shí)被映射成線性結(jié)構(gòu)文檔是不合適的，所以本文改進(jìn)OT算法來(lái)支持圖形文檔的一致性維護(hù).

同時(shí)伴隨移動(dòng)互聯(lián)網(wǎng)和移動(dòng)智能終端的快速發(fā)展，協(xié)同圖形編輯應(yīng)用于移動(dòng)平臺(tái)下是十分具有挑戰(zhàn)和意義的.我們所熟悉的傳統(tǒng)一致性控制算法是在網(wǎng)絡(luò)信號(hào)狀態(tài)良好的P2P協(xié)同系統(tǒng)中設(shè)計(jì)而來(lái)，而移動(dòng)終端設(shè)備采用無(wú)線通信方式，顯然網(wǎng)絡(luò)信號(hào)沒有P2P網(wǎng)絡(luò)下的穩(wěn)定高，可能會(huì)造成部分操作數(shù)據(jù)，無(wú)法成功被其他移動(dòng)設(shè)備接收，從而導(dǎo)致該移動(dòng)站點(diǎn)與丟失操作有因果關(guān)聯(lián)關(guān)系的后續(xù)操作將無(wú)法順利執(zhí)行，至此本文選擇對(duì)基于操作上下文的操作轉(zhuǎn)換控制算法進(jìn)行改進(jìn)，設(shè)計(jì)了移動(dòng)協(xié)同網(wǎng)絡(luò)不穩(wěn)定環(huán)境下一致性控制算法，并將其應(yīng)用到移動(dòng)協(xié)同圖形編輯系統(tǒng)中.

3 實(shí)時(shí)協(xié)同圖形對(duì)象編輯下的一致性維護(hù)

3.1 圖形對(duì)象

圖形對(duì)象被定義為五元組：Obj=(Gid，s，(x，y)，t，d[k]).其中Gid=(i，j)是該圖形對(duì)象的唯一標(biāo)識(shí)，i表示產(chǎn)生對(duì)象的站點(diǎn)標(biāo)識(shí)，j表示站點(diǎn)i產(chǎn)生的第j個(gè)圖形對(duì)象；s表示圖形對(duì)象的類型(矩形、圓形等)；(x，y)表示圖形對(duì)象中心對(duì)稱點(diǎn)在圖形文檔隱含坐標(biāo)系中的位置，x為橫坐標(biāo)，y為縱坐標(biāo)；t表示產(chǎn)生該矩形對(duì)象時(shí)站點(diǎn)瞬時(shí)時(shí)間；d[k]表示位置屬性關(guān)聯(lián)于該圖形對(duì)象的圖形對(duì)象集合，其中d[m]=(i，j)，0mk.

3.2 基本操作類型

本文在新建、刪除、更新操作的基礎(chǔ)上增加了關(guān)聯(lián)操作、關(guān)聯(lián)解除操作及位移操作三種操作類型.

1)Create(Obj)：創(chuàng)建一個(gè)圖形對(duì)象；

2)Delete(Obj)：刪除一個(gè)圖形對(duì)象，同時(shí)解除Obj與所有關(guān)聯(lián)關(guān)聯(lián)對(duì)象和被關(guān)聯(lián)關(guān)聯(lián)對(duì)象之間的關(guān)聯(lián)關(guān)聯(lián)關(guān)系；

3)Update(Obj)：更新一個(gè)圖形對(duì)象的屬性，比如顏色等

4)Relate(Obj1，Obj2)：關(guān)聯(lián)操作；使得Obj1位置屬性關(guān)聯(lián)于Obj2，即Obj2.d[k++]=Obj1.Gid；

5)Relieve(Obj1，Obj2)：關(guān)聯(lián)解除操作；使得Obj1位置屬性與Obj2無(wú)關(guān)，從Obj2.d[k]中找到Obj1標(biāo)識(shí)并刪除；

6)Move(Obj，d，p)：位移操作；對(duì)象Obj按方向d位移p個(gè)參數(shù)，其中d為上(up)、下(down)、左(left)、右(right)任意方向；同時(shí)將所有位置關(guān)聯(lián)關(guān)聯(lián)于Obj的對(duì)象都移動(dòng)相同的參數(shù)；

3.3 關(guān)聯(lián)圖文檔模型

屬性2.一個(gè)圖形對(duì)象只可以直接關(guān)聯(lián)于一個(gè)對(duì)象，但一個(gè)對(duì)象可以被多個(gè)對(duì)象關(guān)聯(lián)，與定義1不矛盾.

圖1 圖形對(duì)象關(guān)聯(lián)圖模型Fig.1 Assoicated graph model

3.4 并發(fā)操作沖突檢測(cè)

定義2.并發(fā)沖突操作

如果操作O1和O2滿足以下幾個(gè)條件：1)O1||O2；2)O1和O2作用于同一個(gè)關(guān)聯(lián)圖模型中；3)O1和O2以不同順序執(zhí)行會(huì)出現(xiàn)圖形文檔的不一致性，那么O1和O2是并發(fā)沖突操作.

定義3.并發(fā)兼容操作

根據(jù)定義2，如果操作O1和O2是非并發(fā)沖突操作，那么O1和O2就是兼容操作.

3.5 一致性轉(zhuǎn)換函數(shù)

非線性模型的協(xié)同圖形編輯系統(tǒng)中，并發(fā)操作O1和O2可能是兼容操作，也可能是沖突操作.如果是兼容操作，則O1相對(duì)于O2進(jìn)行操作轉(zhuǎn)換時(shí)O1本身不需要做出改變，轉(zhuǎn)換得到的O1′只改變了上下文狀態(tài)；如果是沖突操作，需要通過(guò)OT技術(shù)改變操作參數(shù)實(shí)現(xiàn)一致性維護(hù)，顯然已有OT無(wú)法完全解決圖形編輯中的沖突問題，圖形對(duì)象編輯中出現(xiàn)的并發(fā)沖突因并發(fā)操作類型不同而不同.

表1 并發(fā)操作類型Table 1 Types of operation conflicts

如表1所示，本文的圖形編輯系統(tǒng)涉及6種操作類型，共6種可能存在的并發(fā)沖突操作類型需要做操作轉(zhuǎn)換處理，打勾表示并發(fā)操作O1和O2如果滿足一定條件，O1需要針對(duì)O2做操作轉(zhuǎn)換.因此本小節(jié)根據(jù)產(chǎn)生沖突類型，分別設(shè)計(jì)合理的操作轉(zhuǎn)換函數(shù)，從而維護(hù)圖形文檔的一致性.

1)覆蓋沖突

Algorithm1.CoverOT

CoverOT(O1，O2){

if(O1.Obj1.tO2.Obj2.t){

ShowOrder(Obj1，Obj2)；

}

}

2)關(guān)聯(lián)操作與位移操作沖突

假設(shè)站點(diǎn)S1和S2分別產(chǎn)生Relate()操作O1和Move()操作O2，且O1與O2并發(fā)，進(jìn)行操作轉(zhuǎn)換實(shí)現(xiàn)一致性.如果O2目標(biāo)對(duì)象Obj2是O1的被關(guān)聯(lián)對(duì)象，那么O2針對(duì)O1進(jìn)行轉(zhuǎn)換時(shí)無(wú)需特殊處理，O1相對(duì)O2進(jìn)行轉(zhuǎn)換時(shí)，轉(zhuǎn)換后的O1′先完成初始的Relate(Obj1，Obj2)操作，再繼續(xù)對(duì)Obj1和所有位置關(guān)聯(lián)于Obj1的對(duì)象進(jìn)行各執(zhí)行一次操作，位移大小等價(jià)于Obj2位移參數(shù)，轉(zhuǎn)換后的O1′遇到并發(fā)操作Ox，如果發(fā)現(xiàn)位移后的Obj1與Ox目標(biāo)對(duì)象Obj3出現(xiàn)覆蓋沖突，則需繼續(xù)利用CoverOT(Obj1，Obj3)函數(shù)；如果O2目標(biāo)對(duì)象Obj2是O1中被關(guān)聯(lián)對(duì)象或都不是，那么O1相對(duì)于O2和O2相對(duì)于O1進(jìn)行轉(zhuǎn)換時(shí)，操作本身都無(wú)需進(jìn)行特殊處理.具體轉(zhuǎn)換函數(shù)如算法2所示.

Algorithm2.RelateAndMoveOT

RelateAndMoveOT(O1，O2){

if(O1.Obj[1]==Obj2){

O1′=O1+Move(O1.Obj[0]+O1.Obj[0].d[k])；

}

}

3)關(guān)聯(lián)操作與刪除操作沖突

假設(shè)站點(diǎn)S1和S2分別產(chǎn)生Relate()操作O1和Delete()操作O2，且O1與O2并發(fā)，進(jìn)行操作轉(zhuǎn)換維護(hù)文檔一致性.如果O2目標(biāo)對(duì)象Obj2是O1的被關(guān)聯(lián)對(duì)象，O1相對(duì)于O2進(jìn)行轉(zhuǎn)換，轉(zhuǎn)換后的O1′置空；而O2相對(duì)于O1進(jìn)行轉(zhuǎn)換，轉(zhuǎn)換后的O2′無(wú)需特殊的改變，同時(shí)解除了Obj2與所有關(guān)聯(lián)對(duì)象和被關(guān)聯(lián)對(duì)象之間的關(guān)聯(lián)關(guān)系，保持文檔一致性；同理，如果Obj2是O1的關(guān)聯(lián)對(duì)象，那么O1相對(duì)于O2進(jìn)行轉(zhuǎn)換，轉(zhuǎn)換后的O1′置空；如果O2目標(biāo)對(duì)象Obj2不是O1目標(biāo)對(duì)象其中一，那么O1相對(duì)于O2和O2相對(duì)于O1進(jìn)行轉(zhuǎn)換時(shí)，操作本身都無(wú)需進(jìn)行特殊處理.具體轉(zhuǎn)換函數(shù)如算法3所示.

Algorithm3.RelateAndDelete

RelateAndDelete(O1，O2){

if(O1.Obj[1]==Obj2||O1.Obj[0]=Obj2){

O1′=NULL；

}

}

4)關(guān)聯(lián)解除與位移操作沖突

假設(shè)站點(diǎn)S1和S2分別產(chǎn)生Relieve()操作O1和Move()操作O2，且O1與O2并發(fā).如果O2目標(biāo)對(duì)象Obj2是O1的被關(guān)聯(lián)對(duì)象，O1相對(duì)于O2進(jìn)行轉(zhuǎn)換，轉(zhuǎn)換后的O1′先完成初始Relieve(Obj1，Obj2)操作，再對(duì)Obj1執(zhí)行Move操作，位移方向?yàn)镺bj2的逆方向，位移大小與O2中一樣，相當(dāng)于將Obj1退回到原來(lái)位置；如果O2目標(biāo)對(duì)象Obj2是O1中關(guān)聯(lián)對(duì)象或都不是，那么O1相對(duì)于O2和O2相對(duì)于O1進(jìn)行轉(zhuǎn)換時(shí)，操作本身都無(wú)需進(jìn)行特殊處理.具體轉(zhuǎn)換函數(shù)如算法4所示.

Algorithm4.RelieveAndMove

RelieveAndMove(O1，O2){

if(O1.Obj[1]==Obj2){

O1′=O1+Move(Obj1)；

}

}

5)關(guān)聯(lián)解除與刪除操作沖突

假設(shè)站點(diǎn)S1和S2分別產(chǎn)生Relieve()操作O1和Delete()操作O2，且O1與O2并發(fā).如果O2目標(biāo)對(duì)象Obj2是O1的被關(guān)聯(lián)對(duì)象或關(guān)聯(lián)對(duì)象，那么O1在S2中執(zhí)行時(shí)，Obj2已經(jīng)在S2中不存在了，O1在S1中就失去了意義，所以O(shè)1相對(duì)于O2進(jìn)行轉(zhuǎn)換，轉(zhuǎn)換后的O1′直接置空，而O2相對(duì)O1轉(zhuǎn)換時(shí)，無(wú)需特殊處理；如果都不是，那么O1相對(duì)于O2和O2相對(duì)于O1進(jìn)行轉(zhuǎn)換時(shí)，操作本身都無(wú)需進(jìn)行特殊處理.具體轉(zhuǎn)換函數(shù)如算法5所示.

Algorithm5.RelieveAndDelete

RelieveAndDelete(O1，O2){

if(O1.Obj[0]==Obj2O1.Obj[1]==Obj2){

O1′=NULL；

}

}

6)關(guān)聯(lián)模糊沖突

假設(shè)站點(diǎn)S1和S2分別產(chǎn)生Relate()操作O1和Relate()操作O2，且O1與O2并發(fā).如果O1和O2關(guān)聯(lián)對(duì)象非同一目標(biāo)，不會(huì)發(fā)生沖突現(xiàn)象；相反如果O1和O2關(guān)聯(lián)對(duì)象是同一目標(biāo)，需進(jìn)一步判斷被關(guān)聯(lián)對(duì)象，如果被關(guān)聯(lián)對(duì)象是相同的，那么O1和O2是重復(fù)操作，自動(dòng)忽略下一個(gè)；如果被關(guān)聯(lián)對(duì)象是不同目標(biāo)，會(huì)造成模糊關(guān)聯(lián)現(xiàn)象，需要進(jìn)行操作轉(zhuǎn)換維護(hù)文檔一致性.約定當(dāng)發(fā)生關(guān)聯(lián)模糊沖突時(shí)，如果被關(guān)聯(lián)對(duì)象為同一站點(diǎn)產(chǎn)生時(shí)，有效連接對(duì)象為產(chǎn)生時(shí)間較早的；如果被關(guān)聯(lián)對(duì)象為不同站點(diǎn)產(chǎn)生時(shí)，有效連接對(duì)象為站點(diǎn)標(biāo)識(shí)符較小的.當(dāng)某一個(gè)圖形的有效關(guān)聯(lián)對(duì)象發(fā)生改變時(shí)，需要一并回滾其所有與原關(guān)聯(lián)對(duì)象的移動(dòng)操作，接著將其關(guān)聯(lián)于新關(guān)聯(lián)對(duì)象.具體轉(zhuǎn)換函數(shù)如算法6所示.

Algorithm6.RelateObscureOT

RelateObscureOT(O1，O2){

if(O1.Obj[0]==O2.Obj[0]){

if(O1.Obj[1]≠O2.Obj[1]){

if(O1.Obj[1].Gid.i=O2.Obj[1].Gid.i){

if(O1.Obj[1].Gid.j

Relieve(O2.Obj[0]，O2.Obj[1])；

Rollback(O2.Obj[0].position)；

EO1=O1；

}else{

EO1=NULL；

}

}else if(O1.Obj[1].Gid.i< O2.Obj[1].Gid.i){

Relieve(O2.Obj[0]，O2.Obj[1])；

Rollback(O2.Obj[0].position)；

EO1=O1；

}else{

EO1=NULL；

}

}

}

}

3.6 實(shí)例分析

本小節(jié)著重介紹一個(gè)以COT為并發(fā)控制算法的綜合性案例，描述上一小節(jié)中的轉(zhuǎn)換函數(shù)是如何維護(hù)關(guān)聯(lián)圖模型下圖形文檔的一致性的.

圖2 站點(diǎn)操作時(shí)序圖Fig.2 Operation sequence diagram

站點(diǎn)S1的操作執(zhí)行順序?yàn)镺1、O2、O4、O3、O5.O1是本地操作，立即執(zhí)行，文檔DS更新為{O1}；O2到達(dá)S1，C(O2)?DS但C(O2)≠DS，所以O(shè)2需要與DS-C(O2)中的操作依次做操作轉(zhuǎn)換，轉(zhuǎn)換得到的EO2=NULL；同理，O4、O3、O5到達(dá)S1，轉(zhuǎn)換后得到的EO4=O4、EO3=O3、EO5=NULL，最終執(zhí)行后的圖形文檔關(guān)聯(lián)圖如圖3(b)所示.

圖3 協(xié)同工作前后系統(tǒng)圖形文檔關(guān)聯(lián)圖Fig.3 Associated graph model

站點(diǎn)S2的操作執(zhí)行順序?yàn)镺2、O4、O3、O5、O1.O2、O4是本地操作，立即執(zhí)行；按照COT算法，O3、O5、O1轉(zhuǎn)換后的執(zhí)行形式分別為EO3=O3、EO5=NULL、EO1=Relate(Obj1，Obj2)+Move(Obj1，right，3)，最終圖形文檔狀態(tài)與站點(diǎn)S1一致.

站點(diǎn)S3的操作執(zhí)行順序?yàn)镺3、O1、O5、O2、O4.站點(diǎn)O3、O5是本地操作，立即執(zhí)行.同上，O1、O2、O4轉(zhuǎn)換后的執(zhí)行形式分別為EO1=Relate(Obj1，Obj2)+Move(Obj1，right，3)、EO2=NULL、EO4=O4，最終結(jié)果與站點(diǎn)S1、S2都一樣.

綜上所述，3.4小節(jié)設(shè)計(jì)的圖形對(duì)象一致性維護(hù)策略是正確可行的.

4 移動(dòng)平臺(tái)下一致性控制算法

第三節(jié)所研究的協(xié)同圖形編輯系統(tǒng)一致性維護(hù)技術(shù)，本文想將其應(yīng)用于移動(dòng)平臺(tái)下.但是相比于P2P網(wǎng)絡(luò)，移動(dòng)協(xié)同環(huán)境采用的是Client/Server通訊架構(gòu)，系統(tǒng)中心增加了一臺(tái)或多臺(tái)服務(wù)器用于移動(dòng)客戶端之間數(shù)據(jù)資源的通訊.并且移動(dòng)環(huán)境下無(wú)線通訊信號(hào)肯定沒有有線網(wǎng)絡(luò)下的穩(wěn)定，可能會(huì)導(dǎo)致高延遲和數(shù)據(jù)丟包的情況.根據(jù)以上分析，在網(wǎng)絡(luò)狀態(tài)穩(wěn)定的P2P環(huán)境下所設(shè)計(jì)的傳統(tǒng)控制算法顯然無(wú)法正確適用于移動(dòng)協(xié)同環(huán)境中.所以，針對(duì)移動(dòng)網(wǎng)絡(luò)狀態(tài)不穩(wěn)定的情況，本文該小節(jié)對(duì)P2P通訊架構(gòu)下所設(shè)計(jì)的傳統(tǒng)基于操作上下文(Context-Based Operation Transformation，COT)控制算法提出改進(jìn).在移動(dòng)通信C/S架構(gòu)的基礎(chǔ)上，提出待接收操作檢測(cè)與重發(fā)機(jī)制，利用服務(wù)器完成遠(yuǎn)程操作的廣播，同時(shí)增加丟失操作重發(fā)請(qǐng)求的處理，從而使得各個(gè)移動(dòng)協(xié)同站點(diǎn)中操作順利的執(zhí)行.

4.1 客戶端控制算法設(shè)計(jì)

傳統(tǒng)COT算法中，操作O的執(zhí)行必須要滿足一定的因果關(guān)聯(lián)關(guān)系，但是由于移動(dòng)網(wǎng)絡(luò)不穩(wěn)定特性的存在，會(huì)導(dǎo)致某些操作無(wú)法正確到達(dá)目標(biāo)站點(diǎn)，同時(shí)迫使站點(diǎn)中與這些未成功到達(dá)操作滿足關(guān)聯(lián)關(guān)系的操作無(wú)法順利執(zhí)行，最終系統(tǒng)會(huì)出現(xiàn)崩潰現(xiàn)象.基于此，本文在客戶端中加入向服務(wù)器發(fā)送待接收操作重發(fā)機(jī)制，保證系統(tǒng)正常，從而維護(hù)站點(diǎn)文檔狀態(tài)的一致性.客戶端控制算法流程如算法7所示.線程1負(fù)責(zé)本地操作立即執(zhí)行，線程2處理站點(diǎn)接收到的遠(yuǎn)程操作，線程3對(duì)待接收操作序列(Waited to Received Operations List，WROL)中操作的執(zhí)行重發(fā)請(qǐng)求，線程4負(fù)責(zé)處理服務(wù)器端發(fā)來(lái)的重發(fā)請(qǐng)求.

Algorithm7.ControlMethodOnClient

Thread 1：

execute local operation O；

DS=DS° O；

send O to Server；

Thread 2：

if(O?DS‖O?WEOL){

Throw(O)；

break；

}else if(O?WROL){

WROL=WROL-O；

}

MCOT(O)；

Thread 3：

Repeat until WROL={}：

Remove Oxfrom WROL；

ResendRequest O to Server；

Thread 4：

find O at Site I，and send it to Server.

線程1負(fù)責(zé)本地操作O立即執(zhí)行，執(zhí)行結(jié)束將O更新到站點(diǎn)文檔狀態(tài)中，然后將O發(fā)給服務(wù)器，由服務(wù)器完成操作轉(zhuǎn)發(fā)任務(wù)；線程2負(fù)責(zé)處理遠(yuǎn)程接收操作O，由于待接收操作檢測(cè)與重發(fā)機(jī)制，會(huì)導(dǎo)致客戶端多次收到相同操作.為了避免客戶端重復(fù)執(zhí)行已有操作O，首先判斷O是否是重復(fù)操作.如果站點(diǎn)文檔狀態(tài)(Ducoment State，DS)或等待執(zhí)行操作隊(duì)列中(Waited to Execute Operations List，WEOL)包含O，說(shuō)明操作O重復(fù)則拋棄；如果不是重復(fù)，但屬于待接收操作，則將其從待接收操作集合中刪除，并調(diào)用客戶端服務(wù)層執(zhí)行相關(guān)MCOT算法.MCOT具體過(guò)程如算法8所示.線程3負(fù)責(zé)依次對(duì)WROL中操作發(fā)送重發(fā)請(qǐng)求，直到WROL為空為止.線程4負(fù)責(zé)處理服務(wù)器發(fā)來(lái)的操作重發(fā)請(qǐng)求，在本地歷史序列中找到相應(yīng)操作，并將其發(fā)送給服務(wù)器.客戶端相關(guān)算法：

Algorithm8.MCOT

MCOT(O){

if(C(O)?DS){

EO=transform(O，DS-C(O))；

Excute(EO)；

DS=DS∪{org(EO)}；

}else{

WEOL=WEOL° O；

WRO=C(O)-(DS∩C(O))；

WROL=WROL° WRO；

}

}

MCOT算法是對(duì)傳統(tǒng)COT算法的改進(jìn)，主要針對(duì)移動(dòng)網(wǎng)絡(luò)不穩(wěn)定導(dǎo)致操作不滿足因果關(guān)聯(lián)關(guān)系而無(wú)法順利執(zhí)行的情況.首先判斷操作O是否滿足執(zhí)行因果關(guān)聯(lián)關(guān)系，即C(O)是否包含于DS，如果滿足則執(zhí)行流程與COT類似；反之，如果不滿足，說(shuō)明O不滿足因果關(guān)聯(lián)關(guān)系，則O進(jìn)入等待執(zhí)行隊(duì)列(WEOL)，接下來(lái)找出與O滿足關(guān)聯(lián)關(guān)系的丟失操作，并將其加入待接收操作隊(duì)列中，依次向服務(wù)器端發(fā)出操作重發(fā)請(qǐng)求.

4.2 服務(wù)器端控制算法設(shè)計(jì)

在移動(dòng)協(xié)同環(huán)境網(wǎng)絡(luò)狀況不穩(wěn)定情況下，服務(wù)器不僅扮演操作轉(zhuǎn)發(fā)的角色，而且在本文提出的操作檢測(cè)與重發(fā)機(jī)制中負(fù)責(zé)處理重發(fā)操作請(qǐng)求的關(guān)鍵任務(wù).線程1完成操作的轉(zhuǎn)發(fā)任務(wù)；線程2完成操作請(qǐng)求重發(fā)的處理，排除網(wǎng)絡(luò)高延遲原因?qū)е耂i未收到來(lái)自站點(diǎn)Sj的待接收操作O，那么目標(biāo)站點(diǎn)未收到O的原因主要有兩個(gè)：其一，服務(wù)器往Si發(fā)送O時(shí)發(fā)生數(shù)據(jù)丟包；其二，數(shù)據(jù)丟包發(fā)生在Sj和服務(wù)器通訊期間，也就是說(shuō)明服務(wù)器端操作緩存中不存在O.

Algorithm9.ControlMethodOnServer

Thread 1：

if(O∈HB){

Throw(O)；

}else{

Transmit(O)；

HB(i)=HB(i)° O；

}

Thread 2；

Repeat until WRSOL={}：

Remove Oxfrom WRSOL；

if(Ox∈HB){

SendRequest(Ox，Ox.Did)；

}else{

SendRequest(OX.Gid.，Ox)；

}

線程1負(fù)責(zé)操作的轉(zhuǎn)發(fā)任務(wù)，為了避免重復(fù)轉(zhuǎn)發(fā)重發(fā)操作，首先判斷來(lái)自站點(diǎn)Si操作O是否存在于服務(wù)器端對(duì)應(yīng)的歷史轉(zhuǎn)發(fā)操作緩存隊(duì)列HBi中，如果不存在，那么在完成操作O轉(zhuǎn)發(fā)的任務(wù)之后，將O加入到服務(wù)器端Si對(duì)應(yīng)的HB(i)中.線程2負(fù)責(zé)處理操作重發(fā)請(qǐng)求，依次對(duì)等待重發(fā)操作序列中(Waited to Resend Operations List，WRSOL)操作O完成重發(fā)，先判斷O是否存在于服務(wù)器HB中，如果在，說(shuō)明操作O重發(fā)由上述原因一導(dǎo)致，則將服務(wù)器端O重新向重發(fā)請(qǐng)求目標(biāo)站點(diǎn)發(fā)送；如果不在，說(shuō)明問題出現(xiàn)在上述原因二，此時(shí)操作O的產(chǎn)生站點(diǎn)發(fā)出對(duì)應(yīng)操作重發(fā)請(qǐng)求，Ox重新加入到WRSOL中.如此循環(huán)重發(fā)WROL中操作，當(dāng)服務(wù)器收到待接收操作，立即向操作重發(fā)請(qǐng)求目標(biāo)站點(diǎn)發(fā)送.

5 實(shí)驗(yàn)分析

大多數(shù)情況下，人們?cè)谝苿?dòng)網(wǎng)路環(huán)境中辦公、娛樂會(huì)感覺更加方便、輕松.那么移動(dòng)協(xié)同交互式應(yīng)用是否具有實(shí)際應(yīng)用價(jià)值呢？本小節(jié)為了驗(yàn)證以上移動(dòng)環(huán)境下一致性控制算法的有效性，采用Android Studio(AS)和Eclipse作為實(shí)驗(yàn)平臺(tái)，模擬測(cè)試仿真原型系統(tǒng).其中AS開發(fā)移動(dòng)客戶端頁(yè)面模塊，Eclipse開發(fā)客戶端后臺(tái)服務(wù)層(Web Service)模塊和服務(wù)器端業(yè)務(wù)模塊，而移動(dòng)客戶端通過(guò)RESTful調(diào)用服務(wù)層，服務(wù)器業(yè)務(wù)模塊采用Netty完成業(yè)務(wù)監(jiān)聽和實(shí)現(xiàn).

實(shí)驗(yàn)1.系統(tǒng)中用戶間消息傳輸與響應(yīng)的快慢，直接影響了人們?cè)趨f(xié)同交互式應(yīng)用的辦公效率和用戶體驗(yàn)，從而側(cè)面影響了整個(gè)控制算法的效率和協(xié)同系統(tǒng)應(yīng)用時(shí)間.從網(wǎng)絡(luò)通訊架構(gòu)角度出發(fā)，傳統(tǒng)對(duì)等(Peer to Peer，P2P)通訊是一種組網(wǎng)或網(wǎng)絡(luò)形式，參與者既是資源提供者又是獲取者，參與者之間直接通信無(wú)需中間實(shí)體；而移動(dòng)通訊采用中心式架構(gòu)，利用中心服務(wù)器完成消息的接收與轉(zhuǎn)發(fā)，那么通訊架構(gòu)的變化是否會(huì)對(duì)系統(tǒng)效率產(chǎn)生影響？設(shè)定P2P通訊和移動(dòng)通訊網(wǎng)絡(luò)信號(hào)狀態(tài)都良好的前提下，本文分別對(duì)P2P和移動(dòng)網(wǎng)絡(luò)，每次均設(shè)定相同的協(xié)同站點(diǎn)數(shù)和各站點(diǎn)本地操作數(shù)量(假設(shè)每個(gè)站點(diǎn)本地操作數(shù)量為100)的情況下，分別測(cè)試統(tǒng)計(jì)了兩個(gè)網(wǎng)絡(luò)通訊環(huán)境下每次所有站點(diǎn)執(zhí)行完操作后系統(tǒng)整體運(yùn)行消耗時(shí)間，測(cè)試結(jié)果如圖4所示(橫坐標(biāo)表示協(xié)同站點(diǎn)數(shù)，縱坐標(biāo)表示系統(tǒng)運(yùn)行開始至所有協(xié)同站點(diǎn)實(shí)現(xiàn)各圖形編輯畫面一致性所消耗時(shí)間).

分析圖4結(jié)果可得，在以上假設(shè)的實(shí)驗(yàn)情況下，P2P網(wǎng)絡(luò)與移動(dòng)網(wǎng)絡(luò)下協(xié)同系統(tǒng)總運(yùn)行時(shí)間相差很小，且微弱的時(shí)間差對(duì)用戶實(shí)際使用影響不明顯，所以我們可以得到通訊架構(gòu)的變化對(duì)系統(tǒng)效率影響不大.

實(shí)驗(yàn)2.移動(dòng)網(wǎng)絡(luò)信號(hào)強(qiáng)度的高低，直接影響著移動(dòng)端一致性控制算法的效率及整個(gè)移動(dòng)協(xié)同工作系統(tǒng)中工作完成時(shí)間.本文對(duì)移動(dòng)網(wǎng)絡(luò)信號(hào)穩(wěn)定性的高低致使整個(gè)系統(tǒng)運(yùn)行耗時(shí)做了相關(guān)測(cè)試，移動(dòng)端與服務(wù)器端采用Wifi通信，兩者間操作發(fā)送的成功率q模擬移動(dòng)網(wǎng)絡(luò)信號(hào)，q越高說(shuō)明信號(hào)強(qiáng)度越高.本文測(cè)試時(shí)設(shè)定移動(dòng)協(xié)同站點(diǎn)分別為10、15、20，每個(gè)移動(dòng)站點(diǎn)本地操作數(shù)量為100，發(fā)送成功率q按10%步長(zhǎng)從100%依次遞減，q每設(shè)定一個(gè)值測(cè)試多次系統(tǒng)一致性維護(hù)運(yùn)行時(shí)間并求其平均值，測(cè)試結(jié)果如圖5所示(橫坐標(biāo)表示站點(diǎn)操作發(fā)送成功率，縱坐標(biāo)表示移動(dòng)通訊架構(gòu)下系統(tǒng)一致性維護(hù)運(yùn)行時(shí)間).

圖4 系統(tǒng)一致性維護(hù)運(yùn)行時(shí)間與系統(tǒng)協(xié)同站點(diǎn)數(shù)關(guān)系圖Fig.4 Diagram about time of consistency maintenance and coordinate site number圖5 移動(dòng)通訊架構(gòu)下系統(tǒng)一致性維護(hù)運(yùn)行時(shí)間與操作發(fā)送成功率關(guān)系圖Fig.5 Diagram about time of consistency maintenance and success rate of operation

分析圖5結(jié)果可得，橫向比較相同系統(tǒng)站點(diǎn)數(shù)隨著移動(dòng)網(wǎng)絡(luò)信號(hào)強(qiáng)度的降低，系統(tǒng)運(yùn)行時(shí)間逐漸增加；當(dāng)發(fā)送成功率q低于40%時(shí)，系統(tǒng)運(yùn)行時(shí)間明顯增加，考慮到生活中在移動(dòng)信號(hào)極弱甚是無(wú)網(wǎng)絡(luò)狀態(tài)情況下瀏覽網(wǎng)頁(yè)效率都是很低的，顯然不適合移動(dòng)辦公，純屬浪費(fèi)計(jì)算資源.縱向比較相同發(fā)送成功率隨著移動(dòng)站點(diǎn)數(shù)的增加，系統(tǒng)運(yùn)行逐漸增加，顯然合適的協(xié)同辦公人數(shù)也是移動(dòng)系統(tǒng)工作考慮因素，試想1000人協(xié)同編輯共享文檔具有多大意義呢？

綜上所述，本文所提出的控制算法在大多數(shù)移動(dòng)網(wǎng)絡(luò)環(huán)境中是具有可行性的，從而能夠保證各協(xié)同站點(diǎn)副本的一致性.

6 Co-Paint原型系統(tǒng)

為了驗(yàn)證移動(dòng)協(xié)同環(huán)境下一致性控制算法和圖形并發(fā)操作轉(zhuǎn)換函數(shù)的可行性與正確性，本文開發(fā)了Android平臺(tái)下移動(dòng)協(xié)同圖形編輯系統(tǒng)Co-Paint.Co-Paint實(shí)現(xiàn)了基本操作(創(chuàng)建、刪除)和創(chuàng)新操作(關(guān)聯(lián)、關(guān)聯(lián)解除、位移)之間的協(xié)同工作處理.該系統(tǒng)采用Android Studio集成開發(fā)工具進(jìn)行開發(fā)，且支持Wifi和GSM兩種通信方式.

本文在多臺(tái)移動(dòng)設(shè)備上安裝了Co-Paint原形系統(tǒng)，每臺(tái)設(shè)備共同接入同一臺(tái)服務(wù)器，并選擇同一個(gè)圖形文檔或空文檔開始協(xié)同工作，實(shí)時(shí)編輯畫面如圖6(a)所示，屏幕左側(cè)為圖形選擇、關(guān)聯(lián)、關(guān)聯(lián)解除和畫面清空操作，屏幕下方為圖形位移操作(上、下、左、右)，而屏幕上方為群組用戶界面和實(shí)時(shí)聊天界面的切換按鈕，其屏幕畫面分別如圖6(b)和圖6(c)所示，前者可以看到當(dāng)前系統(tǒng)中在線用戶人數(shù)及相關(guān)信息，后者則可以看到其它在線用戶實(shí)時(shí)消息，進(jìn)一步保證工作的順利可靠進(jìn)行.

圖6 Co-Paint原型系統(tǒng)圖Fig.6 Diagram of Co-Paint prototype system

7 總結(jié)與展望

本文根據(jù)移動(dòng)網(wǎng)絡(luò)不穩(wěn)定這一特點(diǎn)，對(duì)P2P網(wǎng)絡(luò)下設(shè)計(jì)的傳統(tǒng)COT算法進(jìn)行改進(jìn)，提出待接收操作檢測(cè)與重發(fā)機(jī)制，并因此分別設(shè)計(jì)了服務(wù)器端和客戶端控制算法，從而保證了協(xié)同操作執(zhí)行的因果依賴關(guān)系，使得改進(jìn)后的控制算法能夠適用于網(wǎng)絡(luò)不穩(wěn)定的移動(dòng)協(xié)同計(jì)算中.基于圖形對(duì)象位置之間會(huì)存在一定關(guān)聯(lián)關(guān)系，提出了Relate和Relieve操作，以及Move操作，本文針對(duì)實(shí)時(shí)協(xié)同圖形編輯中會(huì)出現(xiàn)的并發(fā)操作沖突作出了相關(guān)研究，根據(jù)不同操作類型間產(chǎn)生的不同并發(fā)操作沖突類型，分別設(shè)計(jì)了合理的沖突消解轉(zhuǎn)換函數(shù)，從而很好地維護(hù)了圖形文檔的一致性.與此同時(shí)，為了驗(yàn)證算法可行性，開發(fā)了Android平臺(tái)下的移動(dòng)協(xié)同圖形編輯系統(tǒng)Co-Paint，有效實(shí)現(xiàn)了多用戶間的協(xié)同工作.

移動(dòng)端的存儲(chǔ)、計(jì)算能力等與PC機(jī)仍然有很大差距，可以從以上角度思考，是否可以進(jìn)一步設(shè)計(jì)出合適的移動(dòng)環(huán)境下一致性并發(fā)控制算法，甚至可以考慮設(shè)計(jì)網(wǎng)絡(luò)斷開與恢復(fù)情況下的控制算法；同時(shí)圖形編輯中遠(yuǎn)遠(yuǎn)不止這些基本操作，能否將其它基于圖形對(duì)象操作合理地加入進(jìn)來(lái)，例如Undo/Redo操作等，并設(shè)計(jì)相關(guān)合理的轉(zhuǎn)換函數(shù)維護(hù)文檔一致性，以上方面是我們以后工作進(jìn)一步研究的重點(diǎn).