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

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

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

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

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

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