随着宽带化、分组化、融合和移动化成为网络的主流趋势，移动智能设备广泛普及，人类可以在网络覆盖范围内的任何地点、任何时间方便地获取和处理信息，随时随地远程访问和控制各种设备的愿望，正在成为现实，这也带来了数据一致性和共享性的问题。为了满足这个需求，必须进行数据同步。 数据同步依赖于数据同步协议。由于移动设备的多样化，同步平台的差异性，设计一个好的同步协议并非易事。几乎所有的移动设备在同步时都会受到多种因素的影响，包括系统的开销，电池的消耗，同步程序的健壮性，以及所付出的经济代价，而它们有限的计算能力，有限的存储空间，对于设计一个好的同步协议也是必须要重视的因素。所以，针对特定的应用，一个高效的数据同步协议，显得尤为重要。 在当前常用的数据同步协议中，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来说，改进了它立方级的计算量，同时也保持了原有算法在通信复杂度方面的优势，性能结果令人满意，具有良好的应用前景。