论文部分内容阅读
随着宽带化、分组化、融合和移动化成为网络的主流趋势,移动智能设备广泛普及,人类可以在网络覆盖范围内的任何地点、任何时间方便地获取和处理信息,随时随地远程访问和控制各种设备的愿望,正在成为现实,这也带来了数据一致性和共享性的问题。为了满足这个需求,必须进行数据同步。
数据同步依赖于数据同步协议。由于移动设备的多样化,同步平台的差异性,设计一个好的同步协议并非易事。几乎所有的移动设备在同步时都会受到多种因素的影响,包括系统的开销,电池的消耗,同步程序的健壮性,以及所付出的经济代价,而它们有限的计算能力,有限的存储空间,对于设计一个好的同步协议也是必须要重视的因素。所以,针对特定的应用,一个高效的数据同步协议,显得尤为重要。
在当前常用的数据同步协议中,CPISync(Characteristic Polynomial Interpolation Synchronization的缩写)在衡量同步协议性能的五个可扩展性的指标上,综合表现突出。CPISync同步协议是基于代数的方法,来解决两个相似数据集合间的同步问题。它传输的数据量仅线性依赖于两个数据集合的对称差,而完全独立于集合的元素总和,有着良好的通信复杂度,但在计算复杂度上有很大的缺陷,这也成为它被广泛应用的瓶颈。我们利用数据集分块的思想对CPISync协议进行改进,设计了Improved-CPISync算法。该算法采用递归分块的方法,在保持原有算法良好的通信复杂度的基础上,减少了CPISync立方级的大计算量,并且在仿真平台上实现了改进算法Improved-CPISync,通过对实验结果的比较和分析,证明了在计算复杂度和通信复杂度两个方面,改进算法Improved-CPISync实现了高效同步的目标。论文的主要成果如下:
(1)从可扩展性的角度分析比较了Palm HotSync、Intellisync、SyncML和CPISync这几个常见数据同步协议,在数据传输量、计算量、网络大小,存储空间和健壮性这五个方面的性能及它们的优、缺点,并总结出CPISync的突出的综合表现。
(2)研究了CPISync数据同步协议的基本思想,包括确定上限值的CPISync和未确定上限值的CPISync,并从协议的整体框架上分析了其在计算复杂度上的缺陷。针对此问题,创新提出和设计了改进CPISync同步协议的算法Improved-CPISync算法,从数学模型角度,讨论和证明了Improved-CPISync算法在保持良好通信复杂度的同时,弥补了CPISync在计算复杂度上的缺陷。
(3)构建了仿真平台,设计了数据同步的仿真系统,在仿真系统中,实现了Improved-CPISync算法,并且模拟了PDA和PC在Improved-CPISync算法下进行数据同步。分析和讨论了一些因素,如对称差的上限值、分块因子等,对我们所关注的两项指标:计算复杂度和通信复杂度的影响。仿真实验充分说明了,Improved-CPISync算法相对于CPISync来说,改进了它立方级的计算量,同时也保持了原有算法在通信复杂度方面的优势,性能结果令人满意,具有良好的应用前景。