數(shù)據(jù)同步協(xié)議CPISync改進(jìn)算法的研究與實現(xiàn).pdf

1、江蘇科技大學(xué)碩士學(xué)位論文數(shù)據(jù)同步協(xié)議CPISync改進(jìn)算法的研究與實現(xiàn)姓名：周蕓熠申請學(xué)位級別：碩士專業(yè)：計算機(jī)應(yīng)用技術(shù)指導(dǎo)教師：劉鎮(zhèn)20080318數(shù)據(jù)同步協(xié)議CPISync改進(jìn)算法的研究與實現(xiàn)大摘要隨著寬帶化、分組化、融合和移動化成為網(wǎng)絡(luò)的主流趨勢，移動智能設(shè)備廣泛普及，人類可以在網(wǎng)絡(luò)覆蓋范圍內(nèi)的任何地點、任何時間方便地獲取和處理信息，隨時隨地遠(yuǎn)程訪問和控制各種設(shè)備的愿望，正在成為現(xiàn)實，這也帶來了數(shù)據(jù)一致性和共享性的問題。為了滿足這

2、個需求，必須進(jìn)行數(shù)據(jù)同步。數(shù)據(jù)同步依賴于數(shù)據(jù)同步協(xié)議。由于移動設(shè)備的多樣化，同步平臺的差異性，設(shè)計一個好的同步協(xié)議并非易事。幾乎所有的移動設(shè)備在同步時都會受到多種因素的影響，包括系統(tǒng)的開銷，電池的消耗，同步程序的健壯性，以及所付出的經(jīng)濟(jì)代價，而它們有限的計算能力，有限的存儲空間，對于設(shè)計一個好的同步協(xié)議也是必須要重視的因素。所以，針對特定的應(yīng)用，一個高效的數(shù)據(jù)同步協(xié)議，顯得尤為重要。在當(dāng)前常用的數(shù)據(jù)同步協(xié)議中，CPISync(acter

3、isticPolynomialInterpolationSynchronization的縮寫)在衡量同步協(xié)議性能的五個可擴(kuò)展性的指標(biāo)上，綜合表現(xiàn)突出。CPISync同步協(xié)議是基于代數(shù)的方法，來解決兩個相似數(shù)據(jù)集合間的同步問題。它傳輸?shù)臄?shù)據(jù)量僅線性依賴于兩個數(shù)據(jù)集合的對稱差，而完全獨立于集合的元素總和，有著良好的通信復(fù)雜度，但在計算復(fù)雜度上有很大的缺陷，這也成為它被廣泛應(yīng)用的瓶頸。我們利用數(shù)據(jù)集分塊的思想對CPISync協(xié)議進(jìn)行改進(jìn)，設(shè)計

4、了ImprovedCPISync算法。該算法采用遞歸分塊的方法，在保持原有算法良好的通信復(fù)雜度的基礎(chǔ)上，減少了CPISync立方級的大計算量，并且在仿真平臺上實現(xiàn)了改進(jìn)算法ImprovedCPISync，通過對實驗結(jié)果的比較和分析，證明了在計算復(fù)雜度和通信復(fù)雜度兩個方面，改進(jìn)算法ImprovedCPISync實現(xiàn)了高效同步的目標(biāo)。論文的主要成果如下：(1)從可擴(kuò)展性的角度分析比較了PalmHotSync、Intellisync、Sync

5、ML和CPISync這幾個常見數(shù)據(jù)同步協(xié)議，在數(shù)據(jù)傳輸量、計算量、網(wǎng)絡(luò)大小，存儲空間和健壯性這五個方面的性能及它們的優(yōu)、缺點，并總結(jié)出CPISync的突出的綜合表現(xiàn)。(2)研究了CPISync數(shù)據(jù)同步協(xié)議的基本思想，包括確定上限值的CPISync和未確定上限值的CPISync，并從協(xié)議的整體框架上分析了其在計算復(fù)雜度上的缺陷。針對此問題，創(chuàng)新提出和設(shè)計了改進(jìn)CPISync同步協(xié)議的算法ImprovedCPISync算法，從數(shù)學(xué)模型角度，