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

徐小龍，劉笑笑

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

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

徐小龍，劉笑笑

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

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

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

1 引言

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

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

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

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

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

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

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

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

2 相關(guān)工作

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

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

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

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

3.1 混合式架構(gòu)

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

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

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

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

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

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

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

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

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

圖2 SOD樹

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

1)移動終端綜合能力值C的確定

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

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

表1 隨機選取的10對樣本

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

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

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

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

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

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

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

① 將SOD中的各移動終端按綜合能力值C降序排列并依次編號。

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

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

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

1)同步方式

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Step7同時，SyncServer向WB中的B3發(fā)送同步數(shù)據(jù)請求，B3收到請求信息后與鄰近的移動終端組成SOD并且按照CDDS構(gòu)造SOD樹。假設(shè)B3被選為SMT，則將SOD中未同步過的移動終端同步版本號信息((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不一致的移動終端將舍棄本次同步數(shù)據(jù)。然后，B2、B3和B4按照服務(wù)器優(yōu)先的原則進行沖突處理并更新到本地數(shù)據(jù)集，各移動終端同步成功后保存各自LastVersionID為 1，并按照SOD樹路徑逆向逐跳返回同步結(jié)果到SyncServer。

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

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

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

4 增量捕獲策略

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

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

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

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

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

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

3)定義一個向量來記錄本移動終端的唯一編號和上次同步版本號，作為本次能否進行同步和本次同步版本號的依據(jù)。

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

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

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

4.2 凈增量處理

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

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

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

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

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

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

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

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

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

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

表2 操作類型

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

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

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

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

其中，OP表示對元組的一次操作。

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

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

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

5 實驗驗證與性能分析

5.1 實驗環(huán)境

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

表4 實驗平臺的軟件硬件配置參數(shù)

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

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

5.2 實驗結(jié)果與性能分析

實驗1ICSTC、Trigger和Snapshot時間開銷對比。

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

圖6 ICSTC、Trigger和Snapshot時間開銷對比

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

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

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

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

實驗開展了3輪：第1輪將12個移動終端分配到1個SOD中；第2輪將12個移動終端平均分配到2個SOD中；第3輪將12個移動終端平均分配到 4個 SOD中，分別通過實驗驗證 CDSM和HDSM的同步成功率。

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

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

圖8 CDSM和HDSM同步成功率對比

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

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

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

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

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

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

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

圖10 CDSM和HDSM的CPU使用率對比

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

圖11 CDSM和HDSM的RAM使用率對比

6 結(jié)束語

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

[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

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

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

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

劉笑笑（1988-），男，江蘇宿遷人，南京郵電大學(xué)碩士生，主要研究方向為移動計算與數(shù)據(jù)同步技術(shù)等。