徐小龍，劉笑笑

（南京郵電大學(xué)計(jì)算機(jī)學(xué)院，江蘇 南京 210003）

面向移動(dòng)計(jì)算環(huán)境的混合式數(shù)據(jù)同步機(jī)制

徐小龍，劉笑笑

（南京郵電大學(xué)計(jì)算機(jī)學(xué)院，江蘇 南京 210003）

提出混合式數(shù)據(jù)同步機(jī)制，有機(jī)融合集中式和ad hoc架構(gòu)，設(shè)置自組織域(SOD,self-organization domain)，減少了同步數(shù)據(jù)通信量和數(shù)據(jù)同步服務(wù)器負(fù)載；提出基于節(jié)點(diǎn)能力值的數(shù)據(jù)分發(fā)策略，根據(jù)移動(dòng)終端綜合處理能力值來建立 SOD樹分發(fā)路徑，實(shí)現(xiàn)同步數(shù)據(jù)的高效分發(fā)；還提出了基于軌跡變更的增量捕獲策略，采用觸發(fā)器捕獲操作日志，用凈化方法合并操作日志得到凈增量數(shù)據(jù)。實(shí)驗(yàn)結(jié)果表明，混合式數(shù)據(jù)同步機(jī)制能更好地維護(hù)移動(dòng)計(jì)算環(huán)境中數(shù)據(jù)的一致性，縮短同步響應(yīng)時(shí)間，減少同步數(shù)據(jù)通信量，降低同步服務(wù)器負(fù)載。

移動(dòng)計(jì)算；數(shù)據(jù)同步；混合式架構(gòu)；同步；增量捕獲

1 引言

隨著各類無線通信技術(shù)的發(fā)展與普及，移動(dòng)網(wǎng)絡(luò)也日趨復(fù)雜。與固定的有線網(wǎng)絡(luò)相比，移動(dòng)網(wǎng)絡(luò)的復(fù)雜性、動(dòng)態(tài)性、弱連接性以及通信延遲與帶寬相對(duì)有限等特征使移動(dòng)計(jì)算環(huán)境中的數(shù)據(jù)同步機(jī)制效率難以提升，也難以實(shí)現(xiàn)高效數(shù)據(jù)的一致性。移動(dòng)網(wǎng)絡(luò)需要容忍移動(dòng)終端的非持久性連接和非實(shí)時(shí)數(shù)據(jù)通信，為了滿足移動(dòng)環(huán)境下對(duì)業(yè)務(wù)數(shù)據(jù)的可靠處理需求，移動(dòng)計(jì)算系統(tǒng)需要允許用戶在離線情況下處理數(shù)據(jù)，需要支持多數(shù)據(jù)副本的分布式存儲(chǔ)機(jī)制[1]。目前的分布式存儲(chǔ)機(jī)制中普遍采用樂觀復(fù)制(optimistic replication)[2]方法來保障業(yè)務(wù)數(shù)據(jù)的可用性和控制業(yè)務(wù)數(shù)據(jù)的一致性，以實(shí)現(xiàn)業(yè)務(wù)數(shù)據(jù)的最終一致性[3～6]。

近年來，國(guó)內(nèi)外學(xué)者就移動(dòng)計(jì)算環(huán)境中數(shù)據(jù)同步問題展開了一系列研究工作。目前的數(shù)據(jù)同步系統(tǒng)常采用集中式架構(gòu)[4]和ad hoc架構(gòu)[5]。在基于集中式架構(gòu)的數(shù)據(jù)同步系統(tǒng)中的同步服務(wù)器上保存主數(shù)據(jù)集，各移動(dòng)終端上保存主數(shù)據(jù)集的部分或全部數(shù)據(jù)；每次發(fā)起的數(shù)據(jù)同步過程都由同步服務(wù)器控制并執(zhí)行，各移動(dòng)終端之間不可直接通信，只能通過同步服務(wù)器間接通信；當(dāng)移動(dòng)終端在線或者條件允許的情況下，將自己的數(shù)據(jù)同步到同步服務(wù)器，由同步服務(wù)器分別同步到其他移動(dòng)終端。與此同時(shí)，同步服務(wù)器還擔(dān)負(fù)著沖突檢測(cè)與處理、同步事務(wù)回滾等職責(zé)?；赼d hoc架構(gòu)的同步系統(tǒng)通常將移動(dòng)終端按照地域、業(yè)務(wù)邏輯等因素劃分為一個(gè)個(gè)工作組，每個(gè)工作組同步或異步地完成同一個(gè)任務(wù)，分享文件及信息。

典型的移動(dòng)數(shù)據(jù)同步技術(shù)包括 Microsoft的遠(yuǎn)程數(shù)據(jù)庫(kù)訪問(RDA,remote data access)[7]技術(shù)、合并復(fù)制技術(shù)(MRT,merge replication technology)[8]以及 SyncML initiative的同步標(biāo)記語言(SyncML,synchronization mark up language)[9～12]等。這些移動(dòng)數(shù)據(jù)同步方案一般采用傳統(tǒng)集中式架構(gòu)，難以滿足大規(guī)模復(fù)雜移動(dòng)計(jì)算系統(tǒng)的性能需求，需要另行尋找解決方法。為了更好地輔助各移動(dòng)終端傳輸數(shù)據(jù)，提高系統(tǒng)的數(shù)據(jù)同步性能，有研究者提出了超級(jí)節(jié)點(diǎn)模型(SPM,super-peer model)[13]、基于樹型結(jié)構(gòu)的SCOPE系統(tǒng)[14]、基于2層結(jié)構(gòu)的OceanStore系統(tǒng)[15]、混合樹結(jié)構(gòu)[16]等。為了減少同步數(shù)據(jù)量，提高同步效率，降低同步對(duì)移動(dòng)網(wǎng)絡(luò)帶寬的需求，移動(dòng)計(jì)算系統(tǒng)通常采用增量捕獲策略(increment capture strategy)[17]，每次數(shù)據(jù)同步時(shí)只交換修改過的數(shù)據(jù)。典型的增量數(shù)據(jù)捕獲方法有快照法(snapshot)[18,19]、觸發(fā)器法(trigger)[20]、日志法(log)[21]和時(shí)間戳法(timestamp)[22]等。

移動(dòng)數(shù)據(jù)同步方案存在以下一些問題需要解決：基于傳統(tǒng)集中式架構(gòu)的數(shù)據(jù)同步機(jī)制使服務(wù)器系統(tǒng)負(fù)載和通信量將呈線性上升趨勢(shì)，容易形成系統(tǒng)的性能瓶頸；移動(dòng)網(wǎng)絡(luò)的弱連接性增加了數(shù)據(jù)同步失敗的可能性，從而導(dǎo)致業(yè)務(wù)數(shù)據(jù)的不一致；基于純粹ad hoc架構(gòu)的數(shù)據(jù)同步方案[23,24]將全部的數(shù)據(jù)同步交由移動(dòng)終端完成，增加移動(dòng)終端的系統(tǒng)開銷和電力消耗，還容易影響同步系統(tǒng)性能，延長(zhǎng)同步響應(yīng)時(shí)間，增大同步失敗概率；現(xiàn)有的增量數(shù)據(jù)捕獲方法面向穩(wěn)定的分布式計(jì)算環(huán)境，并不適應(yīng)移動(dòng)計(jì)算環(huán)境，簡(jiǎn)單移植容易導(dǎo)致低效率、高開銷，如Log法需要數(shù)據(jù)庫(kù)有日志機(jī)制和操作日志權(quán)限、Timestamp法要求更改數(shù)據(jù)集結(jié)構(gòu)等。

針對(duì)上述問題，本文對(duì)移動(dòng)計(jì)算系統(tǒng)中的數(shù)據(jù)同步機(jī)制展開一系列研究，主要貢獻(xiàn)包括以下3個(gè)方面。

1)本文提出了一種混合式數(shù)據(jù)同步機(jī)制(HDSM,hybrid data synchronization mechanism)，將集中式架構(gòu)和 ad hoc架構(gòu)有機(jī)融合為基于自組織域(SOD,self-organization domain)的混合式體系架構(gòu)，HDSM以 SOD為單位來管理同步進(jìn)程，并且將部分同步處理邏輯分配到移動(dòng)終端，減輕同步服務(wù)器負(fù)載的同時(shí)適當(dāng)提升各移動(dòng)終端的自主控制權(quán)，同時(shí)將同步數(shù)據(jù)通信量局域化在 SOD內(nèi)部，降低了通信開銷，縮短同步響應(yīng)時(shí)間。

2)為了縮短同步響應(yīng)時(shí)間，加快SOD中同步數(shù)據(jù)的分發(fā)速度，本文提出了一種基于節(jié)點(diǎn)能力值的數(shù)據(jù)分發(fā)策略(CDDS,capacity-value-based data distribution strategy)，通過構(gòu)建SOD樹，參考基于ad hoc架構(gòu)的移動(dòng)終端同步數(shù)據(jù)的分發(fā)方法[14～16]，按照SOD樹的數(shù)據(jù)傳輸路徑，實(shí)現(xiàn)了SOD內(nèi)各移動(dòng)終端間的高效數(shù)據(jù)同步。

3)本文提出了一種基于軌跡變更的增量捕獲策略(ICSTC,increment capture strategy based on track change)，采用觸發(fā)器捕獲操作日志，記錄數(shù)據(jù)集的操作變化過程，并采用凈化方法合并操作日志，實(shí)現(xiàn)凈增量的捕獲和整個(gè)操作變化過程的記錄，以及在發(fā)生意外終止、嚴(yán)重超時(shí)等影響數(shù)據(jù)最終一致性時(shí)回滾，從而有效減少同步數(shù)據(jù)通信量和同步響應(yīng)時(shí)間。

2 相關(guān)工作

移動(dòng)計(jì)算系統(tǒng)維護(hù)數(shù)據(jù)各副本一致性一般采用樂觀復(fù)制方法[2]，系統(tǒng)中多個(gè)節(jié)點(diǎn)中的數(shù)據(jù)副本都可以獨(dú)立進(jìn)行更新,允許各個(gè)節(jié)點(diǎn)的數(shù)據(jù)處理完成之后再進(jìn)行一致性控制；所有的更新信息會(huì)寫在一個(gè)更新事務(wù)中，通過同步協(xié)議傳送到系統(tǒng)的其他節(jié)點(diǎn)，經(jīng)過同步后數(shù)據(jù)最終達(dá)到一致。采用樂觀復(fù)制方法能夠減少網(wǎng)絡(luò)通信量，降低同步失敗所需要的開銷；其缺點(diǎn)是當(dāng)有多個(gè)移動(dòng)終端對(duì)同一數(shù)據(jù)修改并且提交同步請(qǐng)求時(shí)會(huì)發(fā)生數(shù)據(jù)沖突。

RDA[7]是面向移動(dòng)計(jì)算環(huán)境的集中式架構(gòu)同步模型，其數(shù)據(jù)同步進(jìn)程包含push和pull這2種操作。pull操作將數(shù)據(jù)服務(wù)器中的數(shù)據(jù)集下載到移動(dòng)終端上；push操作將本地?cái)?shù)據(jù)集的增量信息或者整個(gè)數(shù)據(jù)集提交至遠(yuǎn)程數(shù)據(jù)服務(wù)器中。同一時(shí)間只能是push或pull操作，并且一次只能操作一個(gè)數(shù)據(jù)集；當(dāng)執(zhí)行pull操作的時(shí)候傳輸整個(gè)數(shù)據(jù)集而非增量數(shù)據(jù)，增加了同步數(shù)據(jù)通信量，延長(zhǎng)了整個(gè)系統(tǒng)的同步響應(yīng)時(shí)間，與此同時(shí)還增加了移動(dòng)終端的存儲(chǔ)空間。MRT[8]主要針對(duì)同步時(shí)會(huì)產(chǎn)生數(shù)據(jù)沖突的移動(dòng)應(yīng)用程序，允許分別在移動(dòng)終端和同步服務(wù)器上自行更新數(shù)據(jù)，之后移動(dòng)終端和同步服務(wù)器之間可以雙向交換數(shù)據(jù)增量進(jìn)行數(shù)據(jù)同步。SyncML[9～12]由數(shù)據(jù)同步協(xié)議、數(shù)據(jù)表示協(xié)議和傳輸綁定協(xié)議 3部分組成，它是基于擴(kuò)展標(biāo)記語言(XML,extensible mark up language)，具有平臺(tái)無關(guān)性、行業(yè)通用性和開放性等特征，為不同網(wǎng)絡(luò)、平臺(tái)及設(shè)備間的遠(yuǎn)程數(shù)據(jù)同步提供了統(tǒng)一的、規(guī)范的數(shù)據(jù)同步協(xié)議。

增量同步方法[17]減少了同步通信流量，但是如何獲取數(shù)據(jù)增量信息成為新的難題。已存在數(shù)據(jù)同步機(jī)制中增量數(shù)據(jù)捕獲方法有 Snapshot[18,19]、Trigger[20]、Log[21]、Timestamp[22]等，它們各有優(yōu)缺點(diǎn)。 Snapshot取數(shù)據(jù)集的新舊快照進(jìn)行對(duì)比以提取信息增量，這一方法適用面較廣，但對(duì)存儲(chǔ)空間要求較高，隨著數(shù)據(jù)元組的增多，對(duì)比檢測(cè)算法易成為系統(tǒng)的性能瓶頸。Trigger利用觸發(fā)器捕獲增量數(shù)據(jù)，增量捕獲效率高，但只應(yīng)用于設(shè)有觸發(fā)器機(jī)制的數(shù)據(jù)管理系統(tǒng)中，而且當(dāng)數(shù)據(jù)集中有大量數(shù)據(jù)進(jìn)行操作時(shí)，觸發(fā)器對(duì)系統(tǒng)的性能影響較大。Log采用分析數(shù)據(jù)庫(kù)自身帶有的操作日志來提取增量，不增加系統(tǒng)額外開銷，效率高，但數(shù)據(jù)庫(kù)和管理系統(tǒng)對(duì)日志的訪問一般都有嚴(yán)格的權(quán)限限制；此外，數(shù)據(jù)管理系統(tǒng)的日志格式大都各不相同，導(dǎo)致日志法的使用受到諸多限制。Timestamp在元組中設(shè)置一個(gè)時(shí)間戳字段，同步時(shí)將大于上次同步時(shí)間的所有字段提取出來即可獲取增量，簡(jiǎn)單易實(shí)現(xiàn)，但此方法要求改變業(yè)務(wù)數(shù)據(jù)集的結(jié)構(gòu)，并且難以捕獲刪除操作，限制了其適用范圍。

3 混合式數(shù)據(jù)同步機(jī)制

3.1 混合式架構(gòu)

本文提出的 HDSM 所采用的混合式架構(gòu)由移動(dòng)終端(MT,mobile terminal)及其移動(dòng)數(shù)據(jù)系統(tǒng)、無線接入點(diǎn)(AP,access point)、同步數(shù)據(jù)服務(wù)器（SyncServer）和主數(shù)據(jù)庫(kù)（SyncDB）構(gòu)成，如圖1所示。

定義 1自組織域(SOD,self-organization domain)。若干地理位置鄰近且能夠通過某種無線通信方式相互通信的移動(dòng)終端，為了更好地完成各自的任務(wù)而自動(dòng)組織到一起，以協(xié)作方式工作的移動(dòng)終端群稱為自組織域。

HDSM 的混合式架構(gòu)是將集中式架構(gòu)和 ad hoc架構(gòu)有機(jī)融合，以 SOD為移動(dòng)終端自組織單位，SOD中的各個(gè)移動(dòng)終端通過服務(wù)性移動(dòng)終端（SMT,service mobile terminal）與同步服務(wù)器進(jìn)行數(shù)據(jù)同步，服務(wù)性移動(dòng)終端接收并向 SOD內(nèi)部的其他移動(dòng)終端轉(zhuǎn)發(fā)同步數(shù)據(jù)。

在HDSM中，當(dāng)某個(gè)移動(dòng)終端接收到同步服務(wù)器發(fā)來的同步請(qǐng)求時(shí)，首先利用無線通信技術(shù)（如藍(lán)牙、紅外線或Wi-Fi等）檢測(cè)鄰近區(qū)域內(nèi)是否存在著有同樣需求的其他移動(dòng)終端。若存在，則在同步服務(wù)器的協(xié)助下，移動(dòng)終端以協(xié)作方式從基站下載同步數(shù)據(jù)并自主地形成SOD。

圖1 混合式網(wǎng)絡(luò)架構(gòu)

同步服務(wù)器以 SOD為單位來進(jìn)行同步，當(dāng)進(jìn)行數(shù)據(jù)同步時(shí)，同步服務(wù)器并不需要與每一個(gè)移動(dòng)終端都直接進(jìn)行數(shù)據(jù)同步，而是僅與 SOD中的服務(wù)性移動(dòng)終端進(jìn)行直接的數(shù)據(jù)同步，其他移動(dòng)終端只需要從服務(wù)性移動(dòng)終端獲得同步數(shù)據(jù)即可。當(dāng)移動(dòng)終端加入同步系統(tǒng)時(shí)，只是加入到地域鄰近的SOD中，所以移動(dòng)終端的加入不會(huì)給同步服務(wù)器造成負(fù)擔(dān)。

3.2 基于節(jié)點(diǎn)能力值的數(shù)據(jù)分發(fā)策略

由于移動(dòng)終端處理能力有限，當(dāng)同步數(shù)據(jù)在SOD內(nèi)部進(jìn)行轉(zhuǎn)發(fā)時(shí)應(yīng)在保證其有效轉(zhuǎn)發(fā)的同時(shí)盡量減少各移動(dòng)終端轉(zhuǎn)發(fā)的次數(shù)，尤其是CPU、內(nèi)存、電量等性能較差的移動(dòng)終端。圍繞HDSM，本文設(shè)計(jì)一種基于節(jié)點(diǎn)能力值的數(shù)據(jù)分發(fā)策略CDDS，拋棄傳統(tǒng)多播式的一對(duì)多數(shù)據(jù)分發(fā)機(jī)制，提高同步數(shù)據(jù)傳輸效率的同時(shí)保證同步質(zhì)量。

將一個(gè)擁有n個(gè)移動(dòng)終端的SOD表示成一棵完全二叉樹T( V)，如圖2所示。其中，表示移動(dòng)終端集合。本文為完全二叉樹的每個(gè)節(jié)點(diǎn)賦予一個(gè)權(quán)值ω，那么 SOD表示成的一棵帶權(quán)完全二叉樹則為以此完全二叉樹為同步數(shù)據(jù)的轉(zhuǎn)發(fā)路徑，則每條路徑上的同步數(shù)據(jù)被轉(zhuǎn)發(fā)的次數(shù)最大不超過而每個(gè)移動(dòng)終端轉(zhuǎn)發(fā)同步數(shù)據(jù)的次數(shù)不超過完全二叉樹的度，位于葉子的移動(dòng)終端則不需要轉(zhuǎn)發(fā)同步數(shù)據(jù)，從最大程度上減少了同步數(shù)據(jù)在 SOD內(nèi)部的轉(zhuǎn)發(fā)次數(shù)，減少了數(shù)據(jù)傳輸延遲，降低了數(shù)據(jù)轉(zhuǎn)發(fā)失敗的風(fēng)險(xiǎn)。

圖2 SOD樹

構(gòu)建SOD樹，首先是由SOD內(nèi)部的所有移動(dòng)終端通過選舉法[25]產(chǎn)生協(xié)調(diào)者(coordinator)，然后由協(xié)調(diào)者協(xié)調(diào)SOD內(nèi)部各移動(dòng)終端來構(gòu)建SOD樹和確定服務(wù)性移動(dòng)終端，具體方法如下。

1)移動(dòng)終端綜合能力值C的確定

移動(dòng)終端綜合能力值主要取決于自身的 CPU利用率和RAM利用率

其中，NCPU表示CPU的核數(shù)，CPU核數(shù)越多，表示其并行處理能力越強(qiáng)；和分別表示CPU和RAM的平均利用率，和顯示了移動(dòng)終端所運(yùn)行的程序消耗CPU和RAM資源的程度。α和β分別為CPU和RAM的剩余利用率對(duì)于確定移動(dòng)終端綜合能力值C而設(shè)置的權(quán)值，分別反映了運(yùn)行某程序?qū)υ撘苿?dòng)終端 CPU和 RAM 的要求。下面確定α和β的值，若移動(dòng)終端隨機(jī)選取最近限定時(shí)間區(qū)間的10對(duì)樣本值，如表1所示。

表1 隨機(jī)選取的10對(duì)樣本

其中，P?表示移動(dòng)終端最近限定時(shí)間區(qū)間內(nèi) CPU和RAM利用率比值的平均值，它同時(shí)顯示了最近限定時(shí)間區(qū)間內(nèi)該移動(dòng)終端運(yùn)行時(shí)所消耗 CPU和RAM 的比率，以此確定α和β的值。利用式(2)～式(6)可以得到式(1)中的參數(shù)，再根據(jù)式(1)即可求出移動(dòng)終端綜合能力值C。

2)服務(wù)性移動(dòng)終端的確定

由于服務(wù)性移動(dòng)終端負(fù)責(zé)與同步服務(wù)器通信、接收同步數(shù)據(jù)并轉(zhuǎn)發(fā)給其他移動(dòng)終端，需要與 AP通信，所以服務(wù)性移動(dòng)終端不僅要有較強(qiáng)的綜合處理能力，而且要有較強(qiáng)的通信能力。

定義 2服務(wù)指數(shù)。用來衡量移動(dòng)終端服務(wù)能力的大小，用E表示。

服務(wù)性移動(dòng)終端的確定首先由協(xié)調(diào)者獲取 SOD內(nèi)部各移動(dòng)終端接收AP的信號(hào)強(qiáng)度結(jié)合各移動(dòng)終端綜合能力值計(jì)算出各個(gè)移動(dòng)終端的服務(wù)指數(shù)公式如下

3)SOD樹的構(gòu)建

以移動(dòng)終端的綜合能力值 Ci( i=1,2,… ,n)作為權(quán)值ωi，則帶權(quán)SOD樹的構(gòu)建流程如下。

① 將SOD中的各移動(dòng)終端按綜合能力值C降序排列并依次編號(hào)。

② 取SMT為根節(jié)點(diǎn)，同時(shí)有序地將各個(gè)節(jié)點(diǎn)按照樹的層次遍歷順序從上到下、從左到右逐層建立成完全二叉樹。

③ 將建立好的完全二叉樹的各個(gè)節(jié)點(diǎn)按層次遍歷順序保存在一維數(shù)組（設(shè)為數(shù)組H）中，便于隨機(jī)讀取左右孩子節(jié)點(diǎn)信息。

3.3 數(shù)據(jù)同步模型

1)同步方式

基于本文混合式架構(gòu)，在數(shù)據(jù)同步過程中根據(jù)同步數(shù)據(jù)的流向分為以下3種同步方式。

① 移動(dòng)終端→同步服務(wù)器，移動(dòng)終端向同步服務(wù)器發(fā)起數(shù)據(jù)同步。移動(dòng)終端將自己的同步數(shù)據(jù)發(fā)送給同步服務(wù)器，同步服務(wù)器解決數(shù)據(jù)沖突并合并，更新本地?cái)?shù)據(jù)。

② 同步服務(wù)器→移動(dòng)終端，同步服務(wù)器向移動(dòng)終端發(fā)起數(shù)據(jù)同步。同步服務(wù)器將自己的同步數(shù)據(jù)發(fā)送給未更新過的移動(dòng)終端。

③ 移動(dòng)終端→移動(dòng)終端，移動(dòng)終端之間相互轉(zhuǎn)發(fā)同步數(shù)據(jù)。位于SOD中的移動(dòng)終端按照CDDS轉(zhuǎn)發(fā)同步數(shù)據(jù)。

同步數(shù)據(jù)流向如圖3所示。

圖3 同步數(shù)據(jù)流向

2)數(shù)據(jù)操作模型

對(duì)數(shù)據(jù)集的數(shù)據(jù)操作類型(Operation Type)可以分為 3 種：A（新增）、M（修改）、D（刪除）。Operation(OperationType,Data)來表示一條數(shù)據(jù)記錄的更新操作，Data表示操作記錄對(duì)象。

①Operation(A,Data)：表示增加一條記錄。

②Operation(M,Data)：表示修改一條記錄。

③Operation(D,Data)：表示刪除一條記錄。

在數(shù)據(jù)同步的過程中，為了判斷移動(dòng)終端與同步服務(wù)器是否處于數(shù)據(jù)一致狀態(tài)，需要給每次同步操作設(shè)置一個(gè)同步標(biāo)志來唯一標(biāo)記同步活動(dòng)，本文用同步版本號(hào)(VersionID)表示，同步版本號(hào)成為同步機(jī)制的關(guān)鍵。由此，可定義一次同步操作為一次同步版本的更新，用同步版本矢量 SyncVector(Operation,VerionID)表示，其中，VerionID與Operation是一對(duì)多的關(guān)系，即在一次同步版本更新中可以有多個(gè)更新操作。

為了保證同步操作的正常進(jìn)行，移動(dòng)終端和同步服務(wù)器需要同時(shí)保存上次同步版本號(hào)LastVersionID。當(dāng)發(fā)起同步的時(shí)候，首先比較LastVersionID，若相等則說明上次同步操作成功，數(shù)據(jù)處于一致狀態(tài)，可以進(jìn)行數(shù)據(jù)同步；若不等則說明上次同步操作失敗，本次同步操作終止或者轉(zhuǎn)向其他解決方法。同步版本號(hào)有效地保證了移動(dòng)終端和同步服務(wù)器數(shù)據(jù)的一致性。

數(shù)據(jù)同步處理模型如圖4所示。本文提出的同步處理模型與傳統(tǒng)的同步處理模型不同之處是移動(dòng)終端不僅與同步服務(wù)器進(jìn)行同步，還需與其他移動(dòng)終端進(jìn)行同步操作，從而實(shí)現(xiàn)了同步功能轉(zhuǎn)移，減少了同步服務(wù)器的負(fù)擔(dān)。

圖4 移動(dòng)數(shù)據(jù)同步模型

移動(dòng)終端組成模塊包括：操作日志捕獲模塊，負(fù)責(zé)捕獲操作記錄的變化過程，并記入操作日志；操作日志凈化模塊，負(fù)責(zé)讀出操作日志的內(nèi)容，凈化合并，消除冗余記錄數(shù)據(jù)；同步處理服務(wù)模塊，負(fù)責(zé)同步請(qǐng)求與響應(yīng)、同步數(shù)據(jù)發(fā)送與接收、沖突處理與合并等；同步數(shù)據(jù)存儲(chǔ)與轉(zhuǎn)發(fā)模塊，負(fù)責(zé)存儲(chǔ)與轉(zhuǎn)發(fā)同步服務(wù)器或其他移動(dòng)終端發(fā)來的同步數(shù)據(jù)。

同步服務(wù)器組成模塊包括：主同步處理服務(wù)模塊，負(fù)責(zé)處理同步請(qǐng)求隊(duì)列、數(shù)據(jù)沖突處理與合并、ID映射處理、數(shù)據(jù)回滾等；同步數(shù)據(jù)轉(zhuǎn)發(fā)模塊，負(fù)責(zé)向移動(dòng)終端轉(zhuǎn)發(fā)同步數(shù)據(jù)。

基于同步處理模型，同步處理過程中遵循以下原則。

① 當(dāng)一次同步更新成功完成后VersionID自增1，并且將本次同步版本號(hào)賦值給上次同步版本號(hào)，即LastVersionID=VersionID。

② 為了減少同步?jīng)_突的情況，移動(dòng)終端登錄后立即檢測(cè)同步服務(wù)器端同步更新情況，若服務(wù)器端的相關(guān)數(shù)據(jù)有更新則立刻發(fā)起同步并更新到本地。

③ 移動(dòng)終端在發(fā)起并成功完成一次同步后可按需刪除本地操作日志，而同步服務(wù)器需保存每個(gè)版本的同步數(shù)據(jù)(即同步版本矢量)，直到同步系統(tǒng)中所有移動(dòng)終端的相關(guān)數(shù)據(jù)都達(dá)到一致狀態(tài)才可刪除。

④ SOD中的服務(wù)性移動(dòng)終端接收到同步數(shù)據(jù)后按照 CDDS轉(zhuǎn)發(fā)給其他移動(dòng)終端，同時(shí)根據(jù)LastVersionID判斷是否進(jìn)行同步操作并按照 SOD樹路徑逆向逐跳返回同步結(jié)果。

⑤ SOD中各移動(dòng)終端接收到同步數(shù)據(jù)后進(jìn)行沖突檢測(cè)并以服務(wù)器優(yōu)先的原則更新本地?cái)?shù)據(jù)。

3.4 典型應(yīng)用場(chǎng)景

根據(jù)以上同步模型和原則，本文以一個(gè)典型應(yīng)用場(chǎng)景來進(jìn)一步詳細(xì)描述同步流程?，F(xiàn)有WA和WB這2個(gè)SOD，其中，WA中有A1、A2、A3這3個(gè)移動(dòng)終端，WB中有B1、B2、B3、B4這4個(gè)移動(dòng)終端，同步服務(wù)器和移動(dòng)終端的所有數(shù)據(jù)都處于一致狀態(tài)，并且上次同步版本號(hào)LastVersionID都為0?，F(xiàn)在A1新增一個(gè)數(shù)據(jù)集X，并且要將此信息同步到SyncServer以及其他移動(dòng)終端。具體同步流程如下。

Step1A1增加一個(gè)數(shù)據(jù)集X并請(qǐng)求同步，則A1的同步版本號(hào)增 1，即VersionID-A1=LastVersionID-A1+1=1。A1向 SyncServer發(fā)送同步請(qǐng)求消息(VersionID-A1=1，LastVersionID-A1=0)。SyncServer接收到后從本地?cái)?shù)據(jù)集中取出與A1最近一次同步的版本號(hào)(LastVersionID-A1=0)，與之比較發(fā)現(xiàn)相等，并 且VersionID-A1＞LastVersionID-A1。 于 是SyncServer允許A1的同步請(qǐng)求并且向A1請(qǐng)求同步版本矢量。

Step2A1收到 SyncServer的請(qǐng)求后，發(fā)送本次同步版本矢量 SyncVector-A1(Operation,1)給SyncServer。

Step3SyncServer收到同步版本矢量后更新本地?cái)?shù)據(jù)，完成數(shù)據(jù)同步并且保存版本矢量?jī)?nèi)容到本地。此時(shí)SyncServer上的LastVersionID-A1增1，即為1。

Step4同時(shí)，移動(dòng)終端B1增加一個(gè)數(shù)據(jù)集Y并請(qǐng)求同步，則B1的同步版本號(hào)增1，即VersionID-B1=LastVersionID-B1+1=1。B1向 SyncServer發(fā)送版本同步請(qǐng)求消息 (VersionID-B1=1，LastVersionID-B1=0)。SyncServer接收到后從本地?cái)?shù)據(jù)集中取出與B1最近一次同步的版本號(hào)（LastVersionID-B1=0），與之相比較發(fā)現(xiàn)相等，并且VersionID-B1＞LastVersionID-B1。于是SyncServer允許B1的同步請(qǐng)求并且向B1請(qǐng)求同步版本矢量。

Step5B1收到 SyncServer的請(qǐng)求后，發(fā)送本次同步版本矢量 SyncVector-B1(Operation,1)給SyncServer。

Step6SyncServer收到B1的同步版本矢量。由于A1在B1之前已完成與SyncServer同步，所以SyncServer比較同步版本矢量 SyncVector-B1(Operation,1)和SyncVector-A1(Operation,1)，并進(jìn)行沖突檢測(cè)與合并，之后更新本地?cái)?shù)據(jù)。此時(shí)將SyncServer上的LastVersionID-B1加 1，即為 1。SyncServer根據(jù)需要將合并后的同步數(shù)據(jù)發(fā)送給A1和B1，A1和B1再次更新本地?cái)?shù)據(jù)或者回滾同步數(shù)據(jù)。

Step7同時(shí)，SyncServer向WB中的B3發(fā)送同步數(shù)據(jù)請(qǐng)求，B3收到請(qǐng)求信息后與鄰近的移動(dòng)終端組成SOD并且按照CDDS構(gòu)造SOD樹。假設(shè)B3被選為SMT，則將SOD中未同步過的移動(dòng)終端同步版本號(hào)信息((VersionID-B2=1,LastVersionID-B2=0),(VersionID-B3=1,LastVersionID-B3=0),(VersionID-B4=1,LastVersionID-B4=0))發(fā)送到 SyncServer。SyncServer判斷B2和B4的LastVersionID是否正確，并且將判斷結(jié)果和同步數(shù)據(jù)發(fā)送給B3。B3接收到數(shù)據(jù)后首先按照CDDS將同步數(shù)據(jù)分發(fā)到B2和B4。同步數(shù)據(jù)在SOD分發(fā)的過程中，根據(jù)判斷結(jié)果，SyncServer判定LastVersionID不一致的移動(dòng)終端將舍棄本次同步數(shù)據(jù)。然后，B2、B3和B4按照服務(wù)器優(yōu)先的原則進(jìn)行沖突處理并更新到本地?cái)?shù)據(jù)集，各移動(dòng)終端同步成功后保存各自LastVersionID為 1，并按照SOD樹路徑逆向逐跳返回同步結(jié)果到SyncServer。

Step8WA中其他各移動(dòng)終端同樣以 Step7的方式更新同步數(shù)據(jù)并向 SyncServer返回同步結(jié)果。

Step9SyncServer接收到各移動(dòng)終端的同步結(jié)果后更新本地各移動(dòng)終端的LastVersionID，至此各移動(dòng)終端和SyncServer的同步版本號(hào)均為1，成功完成本次同步。

當(dāng)移動(dòng)終端A1和B1與SyncServer同步成功后，可刪除本地操作日志，只需要在SyncServer上保存相應(yīng)的同步版本矢量即可；當(dāng)同步系統(tǒng)中所有移動(dòng)終端即A1、A2、A3、B1、B2、B3、B4都完成同步并使系統(tǒng)處于一致狀態(tài)時(shí)，則可以將 SyncServer上保存的同步版本矢量刪除，并且將各移動(dòng)終端的LastVersionID置0。這樣做可以避免移動(dòng)終端或者SyncServer保存大量的同步數(shù)據(jù)，浪費(fèi)存儲(chǔ)空間。

4 增量捕獲策略

4.1 數(shù)據(jù)變更軌跡捕獲

本文提出了基于軌跡變更的增量捕獲策略ICSTC來捕獲增量數(shù)據(jù)，以適應(yīng)移動(dòng)計(jì)算環(huán)境中移動(dòng)終端寫操作頻次較低的特點(diǎn)。ICSTC分為2個(gè)步驟：1)采用觸發(fā)器捕獲數(shù)據(jù)變更軌跡，如圖 5所示；2)對(duì)捕獲到的數(shù)據(jù)變更軌跡進(jìn)行凈增量處理。

圖5 觸發(fā)器捕獲增量

ICSTC策略包括以下內(nèi)容。

1)在操作數(shù)據(jù)集上定義3個(gè)觸發(fā)器，分別是新增觸發(fā)器、修改觸發(fā)器和刪除觸發(fā)器，這些觸發(fā)器用來捕獲數(shù)據(jù)變更軌跡即記錄的變化過程。

2)設(shè)置操作日志來記錄數(shù)據(jù)變更軌跡。操作日志除了擁有操作數(shù)據(jù)集的所有字段外，還包括“操作類型”和“同步版本號(hào)”字段，“操作類型”取A、M、D這3種類型之一，“同步版本號(hào)”為上次同步版本號(hào)加1，用以標(biāo)識(shí)本次同步版本號(hào)。

3)定義一個(gè)向量來記錄本移動(dòng)終端的唯一編號(hào)和上次同步版本號(hào)，作為本次能否進(jìn)行同步和本次同步版本號(hào)的依據(jù)。

4)當(dāng)操作數(shù)據(jù)集數(shù)據(jù)有變動(dòng)的時(shí)候即可觸發(fā)對(duì)應(yīng)的觸發(fā)器，將數(shù)據(jù)變更軌跡記錄在操作日志中，并標(biāo)明操作類型和本次同步版本號(hào)。

5)當(dāng)發(fā)起本次同步時(shí)，根據(jù)本次同步版本號(hào)從操作日志中取出本次全部數(shù)據(jù)變更軌跡，經(jīng)過凈增量處理后傳送到同步服務(wù)器。

由于操作日志中的數(shù)據(jù)記錄逐漸增多，隨著系統(tǒng)的運(yùn)行必然會(huì)累積大量的冗余數(shù)據(jù)（即已經(jīng)同步過的數(shù)據(jù)），這樣不利于數(shù)據(jù)查詢和維護(hù)等操作，給數(shù)據(jù)庫(kù)服務(wù)器帶來更大的性能開銷。所以，當(dāng)確定移動(dòng)終端與同步服務(wù)器同步成功后，即可將本地操作日志清除。

4.2 凈增量處理

由于移動(dòng)環(huán)境的弱連接特點(diǎn)和移動(dòng)同步的需要，對(duì)增量數(shù)據(jù)進(jìn)行凈增量處理。

定義 3凈增量處理。指將作用在操作數(shù)據(jù)集上的一系列操作等價(jià)合并，壓縮操作步驟，使操作序列在壓縮后的操作作用下和原始操作作用下的最終狀態(tài)是一致的。

凈增量處理不僅能減少增量數(shù)據(jù)實(shí)際大小，減少數(shù)據(jù)傳輸時(shí)間，而且可以減少同步服務(wù)器對(duì)數(shù)據(jù)的加載維護(hù)時(shí)間，使整個(gè)同步過程更加穩(wěn)定、高效。

為了更好地表達(dá)關(guān)系型數(shù)據(jù)庫(kù)中各種操作變化過程及其結(jié)果關(guān)系，本文引入關(guān)系集合的概念，則一張表的關(guān)系可以用關(guān)系集合R來表示，表中元組就是關(guān)系集合中的元素。若一張表中有n個(gè)元組，則表示為關(guān)系集合其中，r1,r2,… ,rn代表元組。

定義4操作函數(shù)。關(guān)系集合X經(jīng)過一系列操作后變成X′，本文可以描述為X經(jīng)過函數(shù)Ψ(X)作用后變成X′，即記函數(shù)Ψ為X到X′的一個(gè)操作函數(shù)。由操作函數(shù)的定義和增量的定義可知，操作日志中某一元組的一系列操作即為該元組的一個(gè)操作函數(shù)。

定義 5等價(jià)操作函數(shù)。對(duì)于關(guān)系集合A，在操作函數(shù) f1的作用下得到A′,即 f1( A)A′=，若有另一操作函數(shù) f2使 f2(A)=A′，則操作函數(shù) f1和 f2相對(duì)于A即為等價(jià)操作函數(shù)，記作 f1( A)～f2(A)。

定義6最優(yōu)等價(jià)操作函數(shù)。與f1等價(jià)的操作函數(shù)并不唯一，若f2是f1所有等價(jià)操作函數(shù)中操作步驟最少的，則f2是f1的最優(yōu)等價(jià)操作函數(shù)。

對(duì)增量數(shù)據(jù)進(jìn)行凈增量處理是根據(jù)f1( X)X′=找到其最優(yōu)等價(jià)操作函數(shù)f?使

對(duì)數(shù)據(jù)集的一系列操作本質(zhì)上是對(duì)各個(gè)元組的操作。操作日志用關(guān)系集合L表示，對(duì)操作數(shù)據(jù)集中第i個(gè)元組的操作集合用來表示，所以操作日志關(guān)系集合可表示為由此，對(duì)關(guān)系集合L的凈化處理，可以轉(zhuǎn)化為對(duì)每一個(gè)元組的操作集合Li的凈化處理，即

在關(guān)系型數(shù)據(jù)庫(kù)中，對(duì)同一元組的任何操作序列都可以分解為以下幾種操作類型，如表2所示。

表2 操作類型

例如，一個(gè)元組經(jīng)過一系列操作“新增—修改—修改—?jiǎng)h除”，則可由表2中基本操作類型“1-2-2-3”組合成；也可以由復(fù)合操作類型“5-7-8”組合成。

由定義3可知，對(duì)操作日志的凈化就是對(duì)操作數(shù)據(jù)集中每一個(gè)元組的操作序列的壓縮。首先將操作日志中的操作序列按照元組分組，再將各個(gè)元組的一系列操作全部拆分為基本操作類型和復(fù)合操作類型，最后合并運(yùn)算。運(yùn)算規(guī)則如表 3所示。

表3 同一元組操作合并運(yùn)算規(guī)則

表3中“/”表示不存在此種合并操作，NULL表示操作合并結(jié)果為空，運(yùn)算規(guī)則可以描述如下。

其中，OP表示對(duì)元組的一次操作。

對(duì)于操作日志關(guān)系集合L中對(duì)操作數(shù)據(jù)集第i個(gè)元組的操作集合 Li(1 ≤ i≤ n,i ∈N)，假設(shè)表示對(duì)第i個(gè)元組的第k次操作類型是Γ，結(jié)果是?k，則元組的操作序列集合可以分為5個(gè)類型，分別采用以下5種凈化公式。

根據(jù)對(duì)元組的操作序列類型，在式(12)～式(16)中采用相應(yīng)的凈化公式即可求得此元組的凈化結(jié)果。所以對(duì)操作日志關(guān)系集合的最優(yōu)等價(jià)操作函數(shù)為

在得到操作日志后，即可用式(17)凈化操作日志，去除冗余記錄，得到凈增量同步數(shù)據(jù)，以減少同步過程中所需要傳輸?shù)耐綌?shù)據(jù)量，縮短同步響應(yīng)時(shí)間。

5 實(shí)驗(yàn)驗(yàn)證與性能分析

5.1 實(shí)驗(yàn)環(huán)境

為了驗(yàn)證本文提出的混合式移動(dòng)數(shù)據(jù)同步機(jī)制及相關(guān)策略的性能，本文在實(shí)際的網(wǎng)絡(luò)環(huán)境中構(gòu)建了實(shí)驗(yàn)平臺(tái)，展開了一系列實(shí)驗(yàn)驗(yàn)證，并與基于集中式架構(gòu)的移動(dòng)數(shù)據(jù)同步技術(shù)等進(jìn)行了對(duì)比分析各項(xiàng)性能指標(biāo)。實(shí)驗(yàn)平臺(tái)的軟件硬件配置參數(shù)如表4所示。

表4 實(shí)驗(yàn)平臺(tái)的軟件硬件配置參數(shù)

本文采用5 000條數(shù)據(jù)記錄進(jìn)行實(shí)驗(yàn)，并用變化記錄數(shù)比率(PCT,percentage of changed tuples)作為橫坐標(biāo)值來觀察各項(xiàng)性能指標(biāo)。

式(18)中m表示變化的記錄數(shù)，包括經(jīng)過增加、修改、刪除操作的記錄數(shù)，n表示記錄總數(shù)。

5.2 實(shí)驗(yàn)結(jié)果與性能分析

實(shí)驗(yàn)1ICSTC、Trigger和Snapshot時(shí)間開銷對(duì)比。

如圖6所示，ICSTC和Trigger時(shí)間開銷相近，均遠(yuǎn)小于 Snapshot。隨著 PCT的增加，ICSTC和Trigger的時(shí)間開銷均緩慢增長(zhǎng)，而Snapshot時(shí)間開銷呈波動(dòng)變化，且變化幅度較小。由此可以看出，Snapshot時(shí)間開銷與增量數(shù)據(jù)大小無關(guān)，而只與記錄總數(shù)（即總數(shù)據(jù)量）有關(guān)，且時(shí)間開銷較大，時(shí)間復(fù)雜度為O(n2)。Snapshot需要一張快照表來保存快照信息。Trigger方法利用觸發(fā)器捕獲變化記錄的關(guān)鍵字及其操作類型并保存在一張數(shù)據(jù)表中，然后根據(jù)關(guān)鍵字獲取變化記錄的最終狀態(tài)，忽略記錄的操作過程，其時(shí)間復(fù)雜度為O(n)。Trigger將新增和修改這2個(gè)操作狀態(tài)都記錄為修改狀態(tài)，當(dāng)同步服務(wù)器處理增量數(shù)據(jù)的時(shí)候必須區(qū)分這2種操作狀態(tài)，增加了同步機(jī)制的復(fù)雜性。ICSTC利用觸發(fā)器捕獲變化記錄的操作日志并且通過凈化算法得到凈增量，策略簡(jiǎn)單易行且效率高，其時(shí)間復(fù)雜度為O(n)。ICSTC同樣需要額外的空間來保存操作日志。

圖6 ICSTC、Trigger和Snapshot時(shí)間開銷對(duì)比

實(shí)驗(yàn) 2混合式、集中式架構(gòu)的數(shù)據(jù)同步機(jī)制同步響應(yīng)時(shí)間對(duì)比。

實(shí)驗(yàn)開展了3輪：第1輪將12個(gè)移動(dòng)終端分配到1個(gè)SOD中；第2輪將12個(gè)移動(dòng)終端平均分配到2個(gè)SOD中；第3輪將12個(gè)移動(dòng)終端平均分配到4個(gè)SOD中。通過實(shí)驗(yàn)對(duì)比測(cè)試HDSM和基于集中式架構(gòu)的數(shù)據(jù)同步機(jī)制（CDSM,centralized data synchronization mechanism）的同步響應(yīng)時(shí)間的變化情況。

如圖 7所示，HDSM-R1、HDSM-R2、HDSM-R3分別代表第1輪、第2輪和第3輪的同步響應(yīng)時(shí)間的變化情況。隨著 PCT的增加，HDSM 和CDSM 的同步響應(yīng)時(shí)間均線性遞增。其中，HDSM-R2、HDSM-R3和CDSM的同步響應(yīng)時(shí)間相差不大，且相對(duì)穩(wěn)定，而 HDSM-R1的同步響應(yīng)時(shí)間相對(duì)較長(zhǎng)。在HDSM-R1中，一個(gè)SOD中有12個(gè)移動(dòng)終端，構(gòu)成的SOD樹分為4層，按照CDDS分發(fā)數(shù)據(jù)無疑增加了SOD內(nèi)部同步數(shù)據(jù)轉(zhuǎn)發(fā)次數(shù)和移動(dòng)終端的負(fù)擔(dān)。由于移動(dòng)終端能力的限制，SOD內(nèi)部移動(dòng)終端數(shù)不宜過多，否則將影響同步響應(yīng)時(shí)間；SOD內(nèi)部移動(dòng)終端數(shù)應(yīng)根據(jù)具體應(yīng)用場(chǎng)景、用戶需求和移動(dòng)終端能力來靈活確定最佳數(shù)量。由 HDSM-R2、HDSM-R3和CDSM可知，HDSM同步響應(yīng)時(shí)間比CDSM同步響應(yīng)時(shí)間略微長(zhǎng)點(diǎn)，最大不超過 2 s，且隨著PCT的增加，HDSM同步響應(yīng)時(shí)間有短于CDSM同步響應(yīng)時(shí)間的趨勢(shì)。

實(shí)驗(yàn) 3混合式、集中式架構(gòu)數(shù)據(jù)同步機(jī)制的同步成功率對(duì)比。

實(shí)驗(yàn)開展了3輪：第1輪將12個(gè)移動(dòng)終端分配到1個(gè)SOD中；第2輪將12個(gè)移動(dòng)終端平均分配到2個(gè)SOD中；第3輪將12個(gè)移動(dòng)終端平均分配到 4個(gè) SOD中，分別通過實(shí)驗(yàn)驗(yàn)證 CDSM和HDSM的同步成功率。

圖7 HDSM和CDSM同步響應(yīng)時(shí)間對(duì)比

如圖 8 所示，HDSM-R1、HDSM-R2和HDSM-R3分別代表HDSM第1輪、第2輪和第3輪實(shí)驗(yàn)中的同步成功率的變化情況。CDSM和HDSM的同步成功率隨著PCT的增大均有下降的趨勢(shì)，即同步數(shù)據(jù)增量的增大直接延長(zhǎng)了系統(tǒng)同步響應(yīng)時(shí)間，從而增加了系統(tǒng)同步成功的不確定因素，直接導(dǎo)致了系統(tǒng)同步成功率的下降，其中，HDSM-R1和CDSM下降的最為明顯，且下降波形幅度變化較大。在HDSM-R1中，雖然 SOD數(shù)量少能減輕同步服務(wù)器的開銷，但是在移動(dòng)終端總數(shù)一定的情況下，SOD個(gè)數(shù)的減少將增加SOD內(nèi)部移動(dòng)終端的數(shù)量。本文提出的CDDS按照SOD樹路徑轉(zhuǎn)發(fā)并逆向逐跳返回結(jié)果，需要限制SOD內(nèi)部移動(dòng)終端總數(shù)，否則將延長(zhǎng)同步數(shù)據(jù)在SOD內(nèi)部轉(zhuǎn)發(fā)的時(shí)間，從而影響整個(gè)系統(tǒng)的性能。HDSM-R2和 HDSM-R3的同步成功率下降幅度較小且相對(duì)穩(wěn)定，再結(jié)合HDSM-R1來看，證實(shí)了CDDS對(duì)SOD內(nèi)部移動(dòng)終端數(shù)量的限制要求。由HDSM-R2、HDSM-R3和CDSM曲線可以看出當(dāng)SOD內(nèi)部移動(dòng)終端數(shù)恰當(dāng)時(shí)，HDSM的同步成功率比CDSM高且穩(wěn)定。

圖8 CDSM和HDSM同步成功率對(duì)比

實(shí)驗(yàn) 4混合式、集中式架構(gòu)的數(shù)據(jù)同步機(jī)制同步數(shù)據(jù)通信量對(duì)比。

實(shí)驗(yàn)開展了2輪：第1輪將12個(gè)移動(dòng)終端隨機(jī)分配到2個(gè)SOD中；第2輪將12個(gè)移動(dòng)終端隨機(jī)分配到4個(gè)SOD中，分別測(cè)試HDSM與CDSM同步數(shù)據(jù)通信量。

如圖9所示，HDSM-R1和HDSM-R2分別代表第1輪和第2輪同步數(shù)據(jù)通信量變化情況。HDSM同步數(shù)據(jù)通信量和 CDSM 同步數(shù)據(jù)通信量都隨著PCT的增大而逐漸增多，但CDSM同步數(shù)據(jù)通信量遠(yuǎn)大于 HDSM 同步數(shù)據(jù)通信量。由 HDSM-R1和HDSM-R2的通信量可知，當(dāng)移動(dòng)終端總數(shù)一定時(shí)，SOD數(shù)量越少，則同步數(shù)據(jù)通信量越少，同步服務(wù)器的開銷也越小。但 SOD個(gè)數(shù)減少的同時(shí)，SOD內(nèi)部移動(dòng)終端數(shù)增多，容易影響 SOD內(nèi)部同步數(shù)據(jù)的傳輸時(shí)間，從而影響整個(gè)同步進(jìn)程的同步響應(yīng)時(shí)間。在實(shí)際應(yīng)用中，移動(dòng)終端所處的 SOD數(shù)量可由移動(dòng)終端相對(duì)位置確定。實(shí)驗(yàn)結(jié)果表明HDSM比CDSM能更好地降低同步數(shù)據(jù)通信量。

圖9 CDSM和HDSM同步數(shù)據(jù)通信量對(duì)比

實(shí)驗(yàn) 5混合式、集中式架構(gòu)數(shù)據(jù)同步機(jī)制的CPU和RAM開銷對(duì)比。

本實(shí)驗(yàn)以 PCT為 50%的數(shù)據(jù)集作為實(shí)驗(yàn)數(shù)據(jù)集，同時(shí)將12個(gè)移動(dòng)終端隨機(jī)分配到4個(gè)SOD中，以同步服務(wù)器啟動(dòng)時(shí)刻為零時(shí)刻，分別測(cè)出CDSM和HDSM在整個(gè)數(shù)據(jù)同步過程中的CPU和RAM的使用率。

如圖 10所示，同步進(jìn)程啟動(dòng)時(shí)刻是 2.5 s，CDSM和HDSM的同步進(jìn)程結(jié)束時(shí)刻分別是12 s和11.5 s。從結(jié)束時(shí)間來看，CDSM和HDSM同步響應(yīng)時(shí)間相差不大。同步服務(wù)器啟動(dòng)時(shí)，CPU消耗較高，隨后下降為相對(duì)平穩(wěn)狀態(tài)。當(dāng)同步進(jìn)程啟動(dòng)后，HDSM的CPU利用率整體上要小于CDSM且波動(dòng)幅度相對(duì)平穩(wěn)，在整個(gè)同步進(jìn)程中，HDSM比CDSM節(jié)省同步服務(wù)器的CPU開銷。

圖10 CDSM和HDSM的CPU使用率對(duì)比

如圖11所示，在同步進(jìn)程中，CDSM和HDSM對(duì)RAM資源的消耗相近，都在50%～55%范圍內(nèi)。CDSM和HDSM的RAM使用率都幾乎成直線，說明兩者在整個(gè)系統(tǒng)同步進(jìn)程中對(duì)內(nèi)存的使用均比較穩(wěn)定。

圖11 CDSM和HDSM的RAM使用率對(duì)比

6 結(jié)束語

本文面向移動(dòng)計(jì)算環(huán)境提出了一種混合式數(shù)據(jù)同步機(jī)制HDSM，以SOD為單位來管理同步進(jìn)程，還提出了配套的數(shù)據(jù)分發(fā)策略CDDS和增量捕獲策略ICSTC，不僅實(shí)現(xiàn)高效的數(shù)據(jù)同步，維護(hù)移動(dòng)數(shù)據(jù)的一致性，而且節(jié)省了數(shù)據(jù)同步通信量，減少同步通信費(fèi)用，降低同步服務(wù)器開銷。HDSM的真正實(shí)際應(yīng)用還需要進(jìn)一步解決以下問題：1)數(shù)據(jù)沖突處理，HDSM沒有給出移動(dòng)數(shù)據(jù)同步過程中出現(xiàn)的數(shù)據(jù)沖突處理策略，該策略也是移動(dòng)數(shù)據(jù)同步機(jī)制中的一個(gè)重要研究方向；2)單用戶多終端，HDSM 在處理數(shù)據(jù)同步時(shí)沒有將單用戶多終端考慮在內(nèi)，而在移動(dòng)計(jì)算和移動(dòng)終端日益普及的今天，HDSM必須要考慮這個(gè)問題，以進(jìn)一步提高系統(tǒng)性能；3)移動(dòng)終端數(shù)量限制，HDSM對(duì)于SOD內(nèi)部移動(dòng)終端數(shù)量有限制，數(shù)量的增長(zhǎng)將影響同步響應(yīng)時(shí)間，后續(xù)需要進(jìn)一步優(yōu)化算法和結(jié)構(gòu)，在SOD中容納更多的移動(dòng)終端，提升機(jī)制性能。

[1]LI D W,HUANG W J,HU J H,et al. A distributed redundant real-time data storage mechanism[J]. Journal of Shanghai Jiaotong University,2014,48(7): 948- 952.

[2]BOUAJJANI A,ENEA C,HAMZA J. Verifying eventual consistency of optimistic replication systems[C]//The 41st Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages. San Diego,CA,c2014: 285- 296.

[3]YAN F,RISKA A,SMIRNI E. Fast eventual consistency with performance guarantees for distributed storage[C]//The 32nd International Conference on Distributed Computing Systems Workshops. Macau,c2012: 23-28.

[4]FENG J L,QIAO X Q ,LI Y. The research of synchronization and consistency of data in mobile environment[C]//The 2nd IEEE International Conference on Cloud Computing and Intelligent Systems.Hangzhou,c2012: 869-874.

[5]CHANG B J,CHEN C S,LIANG Y H,et al. A distributed ad hoc network based on increasing reliability and scalability for internet applications[C]//The 2006 International Conference on Wireless Communications and Mobile Computing. New York,c2006: 1453-1458.

[6]MAO H X,HUANG K,SHU X L. Research of cloud storage and data consistency strategies based on replica redundant technology[C]//The 2014 International Conference on Computer,Intelligent Computing and Education Technology. Hong Kong,c2014: 1053-1056.

[7]ITANI Z,DIAB H,ARTAIL H. Efficient pull based replication and synchronization for mobile databases[C]//The 2005 International Conference on Pervasive Services. IEEE,c2005: 401-404.

[8]AJILA S A,AL-ASAAD A. Mobile databases-synchronization amp;conflict resolution strategies using SQL server[C]//The 2011 IEEE International Conference on Information Reuse and Integration. Las Vegas,c2011: 487-489.

[9]PASCUAL V S,XHAFA F. Evaluation of contact synchronization algorithms for the Android platform[J]. Mathematical and Computer Modelling,2013,57(11): 2895-2903.

[10]HAO Y J,YAN C. Design and implementation of Android contacts synchronization system based the SyncML protocol[C]//The 5th International Conference on Intelligent Networking and Collaborative Systems. Xian,c2013: 747-750.

[11]LIN S,LI Y,HE J,et al. Synchronization research of data based on SyncML and Huffman Coding[J]. Information Technology and Industrial Engineering (Set),2013,48: 241-247.

[12]LI J,LI J. Data synchronization protocol in mobile computing environment using SyncML and Huffman coding[C]//The 2012 International Conference on Wavelet Active Media Technology and Information Processing. Chengdu,c2012: 260-262.

[13]XHAFA F. Data replication and synchronization in ad hoc collaborative systems[C]//The 26th IEEE International Conference on Advanced Information Networking and Applications. Fukuoka,c2012.

[14]CHEN X,REN S,WANG H,et al. Scope: scalable consistency maintenance in structured ad hoc systems[C]//INFOCOM 2005. San Diego,CA,c2005: 1502-1513.

[15]KUBIATOWICZ J,BINDEL D,CHEN Y,et al. Oceanstore: an architecture for global-scale persistent storage[J]. ACM Sigplan Notices,2000,35(11): 190-201.

[16]LI Z,XIE G,LI Z. Efficient and scalable consistency maintenance for heterogeneous peer-to-peer systems[J]. IEEE Transactions on Parallel and Distributed Systems,2008,19(12): 1695-1708.

[17]YU C,TAN G,YU Y. Make driver agent more reserved: an aim-based incremental data synchronization policy[C]//The 9th IEEE International Conference on Mobile ad hoc and Sensor Networks. Dalian,c2013: 198-205.

[18]ARDEKANI M S,SUTRA P,SHAPIRO M,et al. On the scalability of snapshot isolation: Euro-par 2013 parallel processing [M]. Berlin:Springer Berlin Heidelberg,2013.

[19]WANG W J. Conservative snapshot-based actor garbage collection for distributed mobile actor systems[J]. Telecommunication Systems,2013,52(2): 647-660.

[20]YANG G. Data synchronization for integration systems based on trigger[C]//The 2nd IEEE International Conference on Signal Processing Systems. Dalian,c2010:310-312.

[21]HU Y,DESSLOCH S. Extracting deltas from column oriented NoSQL databases for different incremental applications and diverse data targets[J]. Data amp; Knowledge Engineering,2014,93: 42-59.

[22]YUN Z,MU Z,FULING B. A tiered replication model in embedded database based mobile geospatial information service[C]//The 4th IEEE International Conference on Wireless Communications,Networking and Mobile Computing. Dalian,c2008: 1-4.

[23]HU Y,FENG M,BHUYAN L N. A balanced consistency maintenance protocol for structured ad hoc systems[C]//INFOCOM 2010. San Diego,CA,c2010: 1-5.

[24]DAFEI Y,BIN C,ZHOU H,et al. Replication strategy in peer-to-peer geospatial data grid[C]//The 2007 IEEE International Geoscience and Remote Sensing Symposium. Barcelona,c2007: 5013-5016.

[25]CHEN J,FAN J,SUN Y. Data dissemination and query in mobile social networks[M]. Berlin: Springer,2012.

Hybrid data synchronization mechanism for mobile computing

XU Xiao-long,LIU Xiao-xiao

(College of Computer,Nanjing University of Posts and Telecommunications,Nanjing 210003,China)

The hybrid data synchronization mechanism (HDSM)was proposed,which integrates centralized architecture and ad hoc architecture together,and a series of self-organization domains (SOD)were built as to cut down the traffic of synchronization data and lighten the load of synchronization server. The capacity-value-based data distribution strategy was proposed,which establishes data distribution paths of SOD tree based on the comprehensive processing capacity of mobile nodes to implement the high-efficient data transmission. The increment capture strategy based on track changes was proposed,which captures operation logs with triggers and obtains pure increment data by purification. The experimental results show that HDSM can make maintenance of data consistency better in mobile computing environment and shorten the response time of synchronization,and reduce the traffic of data synchronization and the load of synchronization server.

mobile computing,data synchronization,hybrid architecture,synchronization,increment capture

s:The National Natural Science Foundation of China (No.61472192),Special Fund for Fast Sharing of Science Paper in Net Era by CSTD (No.2013116),The Natural Science Fund of Higher Education of Jiangsu Province (No.14KJB520014)

TP393

A

2015-02-08；

2016-07-27

國(guó)家自然科學(xué)基金資助項(xiàng)目(No.61472192)；教育部科技發(fā)展中心網(wǎng)絡(luò)時(shí)代的科技論文快速共享專項(xiàng)研究基金資助項(xiàng)目(No.2013116)；江蘇省高校自然科學(xué)研究計(jì)劃基金資助項(xiàng)目(No.14KJB520014)

10.11959/j.issn.1000-436x.2016150

徐小龍（1977-），男，江蘇鹽城人，博士，南京郵電大學(xué)教授，主要研究方向?yàn)橛?jì)算機(jī)軟件、網(wǎng)絡(luò)計(jì)算、信息安全、agent技術(shù)等。

劉笑笑（1988-），男，江蘇宿遷人，南京郵電大學(xué)碩士生，主要研究方向?yàn)橐苿?dòng)計(jì)算與數(shù)據(jù)同步技術(shù)等。