（计算机应用技术专业论文）数据同步协议cpisync改进算法的研究与实现.pdf

摘要 i 数据同步协议 cpisync 改进算法的研究与实现 摘要 随着宽带化、分组化、融合和移动化成为网络的主流趋势，移动智能设备广泛普 及，人类可以在网络覆盖范围内的任何地点、任何时间方便地获取和处理信息，随时 随地远程访问和控制各种设备的愿望，正在成为现实，这也带来了数据一致性和共享 性的问题。为了满足这个需求，必须进行数据同步。 数据同步依赖于数据同步协议。由于移动设备的多样化，同步平台的差异性，设 计一个好的同步协议并非易事。几乎所有的移动设备在同步时都会受到多种因素的影 响，包括系统的开销，电池的消耗，同步程序的健壮性，以及所付出的经济代价，而 它们有限的计算能力，有限的存储空间，对于设计一个好的同步协议也是必须要重视 的因素。所以，针对特定的应用，一个高效的数据同步协议，显得尤为重要。 在当前常用的数据同步协议中，cpisync(characteristic polynomial interpolation synchronization的缩写)在衡量同步协议性能的五个可扩展性的指标上， 综合表现突出。 cpisync同步协议是基于代数的方法，来解决两个相似数据集合间的同步问题。 它传输 的数据量仅线性依赖于两个数据集合的对称差，而完全独立于集合的元素总和，有着 良好的通信复杂度，但在计算复杂度上有很大的缺陷，这也成为它被广泛应用的瓶颈。 我们利用数据集分块的思想对cpisync协议进行改进，设计了improved- cpisync算法。 该算法采用递归分块的方法，在保持原有算法良好的通信复杂度的基础上，减少了 cpisync立方级的大计算量，并且在仿真平台上实现了改进算法improved- cpisync，通 过对实验结果的比较和分析，证明了在计算复杂度和通信复杂度两个方面，改进算法 improved- cpisync实现了高效同步的目标。 关键词：数据同步，cpisync，improved- cpisync，计算复杂度，高效 数据同步协议 cpisync 改进算法的研究与实现 大摘要 随着宽带化、分组化、融合和移动化成为网络的主流趋势，移动智能设备广 泛普及，人类可以在网络覆盖范围内的任何地点、任何时间方便地获取和处理信 息，随时随地远程访问和控制各种设备的愿望，正在成为现实，这也带来了数据 一致性和共享性的问题。为了满足这个需求，必须进行数据同步。 数据同步依赖于数据同步协议。 由于移动设备的多样化， 同步平台的差异性， 设计一个好的同步协议并非易事。 几乎所有的移动设备在同步时都会受到多种因 素的影响，包括系统的开销，电池的消耗，同步程序的健壮性，以及所付出的经 济代价，而它们有限的计算能力，有限的存储空间，对于设计一个好的同步协议 也是必须要重视的因素。所以，针对特定的应用，一个高效的数据同步协议，显 得尤为重要。 在 当 前 常 用 的 数 据 同 步 协 议 中 ， 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 来说，改进了它立方级的计算量，同时 也保持了原有算法在通信复杂度方面的优势，性能结果令人满意，具有良好的 应用前景。 关键词：数据同步，cpisync，improved- cpisync，计算复杂度，高效 abstract ii improvement and implementation of data synchronization protocol cpisync abstract as broadband, grouping, fusion and mobilization become the major factors of modern network, mobile computing devices have been widely used. people are able to access their data and control their devices remotely without restriction of time and location. this requires data consistency and sharing. therefore, data synchronization is necessary. data synchronization depends on synchronization protocols. due to the diversity of mobile devices and platforms, it is difficult to design a good protocol. system cost, battery life, and robustness of programs are the factors to be considered when mobile devices are doing synchronization. additionally, the limited computing power and storage space are crucial to synchronization protocol design. consequently, efficient data synchronization protocols are particularly important in the network setting. among a number of popular and representative synchronization protocols, characteristic polynomial interpolation synchronization (cpisync) performs well regarding the five aspects of scalability performance for synchronization protocols. cpisync is based on an algebraic solution to the problem of synchronizing two similar sets of data. the communicational complexity of this scheme only depends on the number of differences between the two synchronizing sets, and is essentially independent of the overall number of elements in the sets. however, its weakness in computational complexity limits its network applications. we present a novel algorithm named improved- cpisync, which is based on the set partition scheme, to improve cpisync. this approach recursively partitions the data sets, which reduces the cubic computational complexity and keeps the good communicational complexity of cpisync at the same time. moreover, we implemented and tested improved- cpisync on the simulation platform. improved- cpisync has been experimentally proved to be efficient in the computational and communicational complexity when synchronizing. key words: data synchronization, cpisync, improved- cpisync, computational complexity, efficient abstract improvement and implementation of data synchronization protocol cpisync a b s t r a c t as broadband, grouping, fusion and mobilization become the major factors of modern network, mobile computing devices have been widely used. people are able to access their data and control their devices remotely without restriction of time and location. this requires data consistency and sharing. therefore, data synchronization is necessary. data synchronization depends on synchronization protocols. due to the diversity of mobile devices and platforms, it is difficult to design a good protocol. system cost, battery life, and robustness of programs are the factors to be considered when mobile devices are doing synchronization. additionally, the limited computing power and storage space are crucial to synchronization protocol design. consequently, efficient data synchronization protocols are particularly important in the network setting. among a number of popular and representative synchronization protocols, characteristic polynomial interpolation synchronization (cpisync) performs well regarding the five aspects of scalability performance for synchronization protocols. cpisync is based on an algebraic solution to the problem of synchronizing two similar sets of data. the communicational complexity of this scheme only depends on the number of differences between the two synchronizing sets, and is essentially independent of the overall number of elements in the sets. however, its weakness in computational complexity limits its network applications. we present a novel algorithm named improved- cpisync, which is based on the set partition scheme, to improve cpisync. this approach recursively partitions the data sets, which reduces the cubic computational complexity and keeps the good communicational complexity of cpisync at the same time. moreover, we implemented and tested improved- cpisync on the simulation platform. improved- cpisync has been experimentally proved to be efficient in the computational and communicational complexity when synchronizing. the main achievements of the thesis are as follows: (1)we have compared the scalability of several widely used synchonization protocals, such as palm hotsync, intellisync, syncml and cpisync. we concluded that cpsync outperformances other protocals regarding data transmission load, computation, network size, memory and robustness. (2) we have studied the principles of cpisync, including two cases with certain abstract and uncertain bounds. futhermore, we have proposed improved- cpisync algorithm which improves the protocal framework and its computational complexity. it is mathmatically proved that improved- cpisync can keep the good communicational complexity of cpisync. (3)we have implemented the improved- cpisync algorithm on a data cynchronization simulation platform. we have also simulated experiments of data synchronization between pda and pc, and discussed the influence of such factors as symmetric difference bounds and partition factor on the computational complexity and communicational complexity indexes as concerned. improved- cpisync has been experimentally proved to reduce the cubic computational complexity and to keep the good communicational complexity of cpisync at the same time, which has a satisfying performance and a wide application future. keywords: data synchronization, cpisync, improved- cpisync, computational complexity, efficient 论 文 独 创 性 声 明 本人声明所呈交的学位论文是我本人在导师指导下进行的研究工作及取得的研 究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已 经发表或撰写过的研究成果，也不包含为获得江苏科技大学或其它教育机构的学位或 证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作 了明确的说明并表示谢意。 学位论文作者签名： 日 期： 学 位 论 文 使 用 授 权 声 明 江苏科技大学有权保存本人所送交的学位论文的复印件和电子文稿，可以将学位 论文的全部或部分上网公布，有权向国家有关部门或机构送交并授权其保存、上网公 布本学位论文的复印件或电子文稿。本人电子文稿的内容和纸质论文的内容一致。除 在保密期内的保密论文外，允许论文被查阅和借阅。 研究生签名： 导师签名： 日 期： 日 期： 第一章 绪论 1 第一章 绪论 1 . 1 研究背景 随着全球信息化程度的提高，宽带化、分组化、融合( 包括产业融合、业务融合、 网络融合) 和移动化成为网络的主流趋势。人们在不自觉的情况下使用网络，就如同对 空气和水的使用一样，工作模式与生活模式都实现了数字化。计算机硬件技术也在快 速发展，微处理器的体积越来越小，速度越来越快，能源消耗越来越少，价格也越来 越低，这些因素使带微处理器的小型智能设备得到普及。此外，有线和无线带宽正在 呈指数倍增长，在各种智能设备间建立连接的带宽障碍逐步消除，人类可以在网络覆 盖范围内的任何地点、任何时间方便的获取、处理和发送信息，随时随地远程访问和 控制各种设备的愿望，正在一步步成为现实。 广泛普及的移动化网络和通讯设备在使人们能够随心所欲地获取和处理各种信息 的同时，也带来了数据一致性和共享性的问题。 ( 1 ) 对于个人用户而言，人们往往同时拥有着多个智能设备，包括移动电话、笔记 本电脑、掌上电脑、个人数字助理( pda) 和车载电脑，最终从空调、冰箱到智能电灯 开关的各种装置都将被包含在内。在这些移动智能设备之间共享着大量的信息。这些 移动智能设备与家中的 p c 设备进行连接， 人们无论身处何方都希望可以获得高质量的 音频和视频，这将给人们的家庭、休闲和娱乐带来根本的变革。由于移动信息设备之 间不具备自动同步的机制，用户将不得不亲自去维持信息之间的一致性。 ( 2 ) 对于企业用户而言，目前，企业的员工将不再被限制在固定的办公室中，带来 了移动办公的概念1，智能设备允许员工以无缝的方式随时随地访问自己的信息，除 了提高工作效率之外，跨区域的信息流动方式还可以提高客户的满意度，同时降低企 业的经营成本。在进行移动办公时就带来了数据同步的问题。一个简单的案例就是公 司项目的协同开发，工作中的企业员工由于移动网络不能保证实时在线，而不能保证 本地信息的实时更新，往往导致在陈旧的信息下进行后继工作，带来时间和精力的浪 费。 解决移动信息数据一致性和共享性问题就必须进行数据同步，所谓数据同步就是 指在不同的数据集合之间保持数据一致性的技术手段2。通过数据同步可以将移动设 备上数据的变化情况及时通知并影响对方，保证数据的一致性。比如，当用手机中的 名片管理软件修改了某客户的联系电话，或者用手机中的便签软件记录了客户提供的 重要信息，如何将这些改动及时地反映到工作用 pc 机以及其它终端设备上的操作就 叫做“同步操作” ，而进行“同步操作”后，各个终端上的信息保持一致，就处于“同 第一章 绪论 2 步状态” 。 时至今日，随着用户的需求越来越人性化、多媒体化、多样化，流媒体、音乐、 图片、游戏、电子杂志已成为移动数据的内容主流。而数据同步业务是一种支持两数 据源间进行数据同步的机制。但它们所需操作的数据一般不是数据库的全部，而往往 只是与之相关的极少量数据，对于同步更新问题，如果采取“全盘复制”的方法，不 仅浪费资金，而且浪费时间，况且，对于大型数据库，“全盘复制”的方法会造成通 信瓶颈，甚至无法实现。可以简单地认为在数据同步发生时，同步的双方必须完成两 个任务：将本方对数据源的修改发送给对方和根据对方发送的数据源修改记录修改本 方的数据源内容。如何确定同步双方的差异，达到高效的数据同步，满足日益增长的 数据同步需求，成为我们需要研究的内容。 1.2论文研究意义 “随时、随地、便捷”是人们永恒不变的追求。理想的模型是无论在家里、办公 室还是旅行途中，任何人在任何时间、任何地点都可以通过任何终端获得任何内容， 而且，用户的体验也将实现最大的一致性。 数据同步意味着保持不同终端数据的一致，如果能用最短的时间、最快的速度达 到这种一致性，那将给用户带来以下好处： 1 、及时更新信息 分布式系统通常包括多个结点，每个结点都持有一份该结点所需的数据的本地拷 贝2。同步技术可以在这些结点之间交换信息，使得每个结点更新到最新的数据。例 如，一个跨国公司拥有遍布全球的分布式网络。如果每个网络之间可以高效的互相同 步，则各地服务器就可以及时地获取最新的信息，因而也可以为分散的用户提供更好 的数据时效性和可用性。 2 、减少网络的数据流动 通过高效的同步，不再需要大批量、大规模的传输数据，只需要同步用户所关心 并且更新的数据，从而减少了网络数据的传输。 3 、确保数据的可靠性 虽然持有数据的移动设备不是一直连到网络上，却是值得信赖的，因为它的信息 是通过最近成功的同步获取的。例如，移动用户可以用移动设备连接到服务器下载最 新的信息，像行事历的条目；然后用户就可以断开与服务器的连接而在 pda 上仍然 持有有价值的、最新的、可靠的数据。 4 、交付有质量的服务 音频和视频的应用需要双方保持同步来传送有意义的信息。如果应用程序不能交 第一章 绪论 3 付最小的必要的质量服务，则业务中就不再需要它们3。例如，如果视频会议中声音 与图像失去同步，由于难以理解声音和图像就会显得毫无意义。 目前我们可以在一些相关资料中看到从不同角度对数据同步问题的广泛研究。 从数据库的角度4，coda 文件系统 ( coda file system) 56已经建立了关于离 线操作的概念，在这个概念中，主机能够独立的操作和同步，而且 coda 文件系统里 提出的通用模型与当前一些移动计算系统，包括一些 pda 所使用的模型相似。对于管 理分布式的数据库，需要一个完善的机制，来保证数据一致、解决更新冲突。当前已 经提出一些体系结构，比如 bayou 7，roam8，deno9等，来解决这些重要的问 题。 从信息论的角度4 10- 13，同步问题可以视作传统的纠错( error- correction) 问题来处 理14。同步主机不同的记录，即“错误” ，通过纠错码( error- correcting codes) 加以“纠 正” 15，达成一致。reed- solomon码14就提供了一个这样的很好应用，因为在一个固 定的有限域内，它的解码时间仅仅依赖于“错误”的数量。 从通信可扩展性的角度4，也是本课题所研究的角度，是一个相对较新的研究领 域，数据同步问题的解决，依赖于数据同步协议。数据同步协议的任务就是识别同步 端数据的改动，解决可能的冲突，并利用这些改动更新同步端的设备，达到数据的一 致。在一个特定的网络环境中，为移动设备设计一个好的同步协议并非易事。移动设 备往往处于低带宽的有线或无线网络中，此外，在 cpu、内存容量、电源消耗等方面 的有限条件，使得它们无法快速处理或传输大量的数据。所以，针对某个特定应用， 具有良好的可扩展性的高效的数据同步协议，显得尤为重要。 1.3论文的研究内容和主要工作 本课题研究的焦点主要是如何高效的在两个相似的数据集合之间进行数据同步。 数据同步可以说是一个“费时费力”的过程，消耗的时间、占用的网络带宽、计算量 以及能源耗费，都是我们必须要考虑的因素。特别是当两个数据集合间的元素大部分 相同，只有一小部分差异的时候，同步的高效性，显得更加重要。本文在广泛研究了 目前常见的数据同步协议如 palm hotsync 协议 16、intellisync17、syncml18和 cpisync19- 22的基础上，重点分析了 cpisync 数据同步协议，在保持了它良好的通信 复杂度的基础上，对它作了改进，提出并实现了 improved- cpisync 算法，弥补其在计 算复杂度上的缺陷。论文的主要研究内容包括以下几个方面： 1 、比较几个数据同步协议的性能及优、缺点： 论文从可扩展性的不同衡量尺度， 比较了 palm hotsync 协议、 intellisync、 syncml 和 cpisync 这几个数据同步协议的性能及优、缺点，分析了 cpisync 数据同步协议在 第一章 绪论 4 综合表现上的优势以及最大的不足之处。 2 、研究和设计 cpisync 数据同步协议的改进算法 improved- cpisync 算法： 在广泛研究了目前常见的数据同步协议，重点分析了 cpisync 数据同步协议的基 础上，研究和设计了其改进算法 improved- cpisync 算法，并从数学模型角度，讨论和 证明了 improved- cpisync 算法在保持良好通信复杂度的同时，弥补 cpisync 在计算复 杂度上的缺陷。 3 、构建算法仿真平台及对算法性能进行测试： 编程模拟了网络环境，设计了算法仿真平台，在仿真平台上实现了改进算法 improved- cpisync，并对其进行了性能测试，分析比较了测试结果，证明改进算法解 决了原算法的立方级计算量的问题。 1.4论文的组织安排 本文第一章为绪论，介绍了本文的研究背景、研究意义、研究内容和全文的组织 结构。 第二章首先对数据同步协议作了概述性的介绍，然后分别对 palm hotsync 协议、 intellisync、syncml和 cpisync 这几个数据同步协议从原理、特点上进行了阐述。在 此基础上进一步从数据传输量、计算量、网络大小、健壮性和存储空间这几个可扩展 性方面，对它们进行定性分析和比较，并总结出 cpisync 的突出的综合表现。 第三章研究了 cpisync 数据同步协议的基本思想，包括确定上限值的 cpisync 和 未确定上限值的 cpisync19- 22，并从协议的整体框架上分析了其在计算复杂度上的缺 陷。针对此问题，设计了改进 cpisync 同步协议的算法 improved- cpisync 算法，从数 学模型角度，讨论和证明了 improved- cpisync 算法在保持良好通信复杂度的同时，弥 补 cpisync 在计算复杂度上的缺陷。 第四章阐述了 improved- cpisync 算法仿真系统的设计和构建过程。包括仿真工具 和平台的介绍，仿真系统的总体设计以及详细设计，并给出了主要模块的一些重要的 函数原型以及功能描述。最后提供了在仿真平台上对算法进行测试得到的部分测试数 据，并分析比较了测试结果。 第五章为总结展望，简单对全文作了总结，也展望了今后下一步的研究方向。 第二章 数据同步协议及其扩展性分析 5 第二章 数据同步协议及其扩展性分析 2.1数据同步协议概述 数据同步协议的任务就是识别同步端数据的改动，解决可能的冲突，并利用这些 改动更新同步端的设备，达到数据的一致。在一个特定的网络环境中，为移动设备设 计一个好的同步协议并非易事。因为移动设备，比如 pda，往往处于低带宽的有线或 无线网络中，此外，在 cpu、内存容量、电源消耗等方面的有限条件，使得它们无法 快速处理或传输大量的数据。如图 2 . 1所示，如何保持移动设备间的数据一致，如何 保持移动设备和 pc 间的数据一致，如何保持 pc 和数据中心间的数据一致，如何高效 地、可靠地进行数据同步，都是我们必须要解决的重要问题。所以，针对某个特定应 用，具有良好的可扩展性的高效的数据同步协议，显得尤为重要。 移动设备 internet web服务器 数据中心 数据库 pc机 图 2 . 1 数据同步示意图 2.2几种典型的数据同步协议 目前常见的数据同步协议有 palm hotsync 协议、 intellisync、 syncml和 cpisync。 2.2.1 palm hotsync 协议 美国 palm 公司为了解决各种 palm pda 和桌面 pc 间的数据同步问题，提出了 hotsync 数据同步方案。安装有 palm 操作系统的 palm pda 或 palm pilots，实现了 hotsync 同步协议。hotsync 作为 pda 与 pcs 或者其他设备的数据同步程序的中间件 接口，提供了两种操作模式：slow sync 和 fast sync16。 fast sync：只有当手持 pda 与同一台 pc 同步时，才满足 fast sync 的条件。在这 种模式下， 采用状态标志位( status flags) 16来标记在上一次同步之后， 数据发生的变化。 当对某条记录进行增、删、改操作时，修改相对应的状态标志位并保存在数据库中。 用户发出同步请求时，手持设备把状态标志位发生变化的所有记录传输给 pc，pc 将 这些记录与自己的数据库的记录进行比较，分别作增、删、改操作，然后把同步结果 第二章 数据同步协议及其扩展性分析 6 返回给手持设备，所有的状态标志位重置。记录的比较等操作主要在 p c 端完成。所以 fast sync 的计算复杂度和通信复杂度都是比较好的，但多于两台设备要同步时，便不 能采用快速同步，其适用范围有限。 slow sync：当不满足 fast sync 的同步条件时，均可以采用 slow sync。在这种模 式下，手持设备把所有的数据记录都传输给 pc，pc 参照上次同步后的数据集备份， 确定哪些记录做了增、删、改操作，接下来过程类似于 fast sync。 图 2 . 2 描述了 slow sync 和 fast sync 间的区别。slow sync 把整个数据库从 pda 传输到 pc，而 fast sync 只传输上次同步后修改了的记录。slow sync 的通信复杂度和 计算复杂度随记录的数量线性增加。 原始日程表 早晨 9 点 约见王经理 早晨 10 点 员工会议 中午 12 点 与小吴吃饭 下午 4 点 约见访客 修改的 home 日程表 早晨9 点 约见王经理 早晨 10 点 员工会议 中午12 点 与小吴吃饭 下午 4 点 约见访客 修改的 pda日程表 早晨9 点 约见王经理 早晨 10 点 员工会议 中午 12点 与小张吃饭 下午 4 点 约见访客 修改的 home 日程表 早晨 9 点 约见王经理 早晨 10 点 员工会议 中午 12 点 与小吴吃饭 下午 4 点 约见访客 修改的 pda 日程表 早晨 9点 约见王经理 早晨 10 点 员工会议 中午 12点 与小张吃饭 下午 4 点 约见访客 slow sync fast sync modifications 图 2 . 2 slow sync 和 fast sync 的比较 图 2 . 3 展示了利用 frontline test equipment software 测试软件23得到的比较数据， 可以看到在记录的修改量基本保持不变的情况下， slow sync 的通信量随着记录的总数 量线性增加，而 fast sync 的通信量几乎保持不变，只与记录的修改量相关。 0 0.6 1.2 1.8 2.4 3 3.6 4.2 300600900120015001800 每个设备上记录的数量 传输的字节数 s l o w s y n c f a s t s y n c 5 10 图 2 . 3 slow sync 和 fast sync 的通信复杂度的比较( 以字节为单位) 第二章 数据同步协议及其扩展性分析 7 2.2.2 intellisync 美国 pumatech公司推出的 intellisync 同步技术采用了集中式的数据同步方案。在 intellisync 同步协议中，所有设备都与一个中心服务器同步17，每一次同步都可以看成 是 fast sync，所以 intellisync 的性能和图 2 . 3 中的 fast sync 相类似。 但由于它的网络拓扑结构是星型集中式，而用户的账户信息和安全设置信息都保 存在中心服务器上，所以一旦中心服务器发生故障或者拥塞，将会影响所有的同步用 户。可能会有人提出使用几个中心服务器，来解决这个问题，但又会产生同步不同服 务器的问题。通常，基于对等层（peer- to- peer）的分布式结构的数据同步在健壮性、 可扩展性方面，比集中式结构有更好的网络效率7- 9。 2.2.3 syncml 一批移动网络通信领域内的软硬件厂商包括 ericsson、ibm、lotus、matsushita、 motorola、nokia、openwave 和 starfish 在内的多家公司成立了 syncml initiative， 发布推广了一组被称为 syncml 的开放协议。它努力提供一个跨平台、多设备、开放 的、通用的数据同步标准。同步两端可以是任何一种类型，在任一种网络上面的设备。 这使得这个协议的应用领域很宽24- 27。 为了减少网络传输量，syncml 假定每个设备都要为网络上的其他每个设备的每 条记录保存信息修改标记( information modification flags) 18，因此，在pda 上修改一 条记录，不同于 fast sync 那样修改一组状态标记，而是要修改网络上其他每个设备的 一组状态标记。由此可见，syncml 对存储空间要求较高，这对嵌入式设备来说是一 个不利的因素。 而且 syncml这样基于 timestamp22的协议很难适应一个设备频繁增减 的动态网络环境，因为从网络中增加或减少设备，需要更新网络中的其他设备的相关 信息。 2.2.4 cpisync cpisync 同步技术( characteristic polynomial interpolation synchronization的缩写) 是针对数据同步领域同步不同设备上相似数据的情况提出的。它是基于代数方法用来 解决两个远端数据集合间的同步问题19- 2228。 cpisync 算法的一个特点是它能在一般对等层( peer- to- peer) 设置下，保持 fast sync 的通讯效率29。cpisync 同步传输的数据量线性依赖于两个数据集合的对称差， 而完全独立于集合的元素总和。不同于前面所介绍的协议，cpisync 不需要保存网络 上其他任何设备的任何状态信息，并且可以以 peer- to- peer 的方式操作。 cpisync 协议概述：cpisync 算法用整数集合的形式表示数据库的记录，一个整 数 i x 代表一条记录，这样数据集就可以用集合 123 s=x , x , x , n ,x 来表示，集合s的特 第二章 数据同步协议及其扩展性分析 8 征多项式1920- 2228定义为： ( )()()() 123s xzzxzxzx=() n zx 定义两集合的差, aabbba ssss= =，则有下面等式19- 2228： ( ) ( ) ( ) ( ) ( ) aa bb s s xzxz f z xzxz = ( 2 - 1 ) 等式( 2 - 1 ) 成立，因为分子、分母中两个集合共同的项可同时约去。如果两个集合 最多有m个不同元素，则等式( 2 - 1 ) 中的有理函数( )f z可通过m个样本取值点，利用 插值算法进行重构得到。 cpisync 算法的过程可描述如下： 同步的两端 a 和 b 分别计算它们的特征多项式( ) a s xz和( ) b s xz在m个样本点 的值（在一个选定的有限域内） 。 a 将它计算出来的数值传输给 b ，b 计算有理函数( )f z在m个样本点的值。 用插值算法重构有理函数 ( ) ( ) ( ) a b xz f z xz =的系数。 对被插值的函数的分子和分母因式分解，可得到两集合 a s 和 b s 的不同元素。 2.3数据同步协议的可扩展性分析 几乎所有的移动设备在同步时都会受到多种因素的影响， 包括同步时的系统开销， 电池的消耗，同步程序的健壮性和可靠性，以及在同步过程中所耗费的财力。所以一 个同步协议对这些问题解决得好与坏，直接影响着整个协议的可扩展性29。 pda 等移动设备在快速连接网络方面受到很大的限制，此外，它们有限的计算能 力，有限的存储空间对于设计一个好的同步协议也是必须要重视的因素3031。由于需 要在数据传输量、计算量、网络大小、健壮性、存储空间这五个方面对前面所介绍的 同步协议进行比较，所以我们采用能够在多个维度上比较两个或两个以上状态之间差 异的雷达图( radar diagrams) 的方法32进行定性分析，如图 2 . 4 所示。雷达图是一种直 观明显的图形方法，清晰的突出了不同协议的优、缺点。 第二章 数据同步协议及其扩展性分析 9 f a s t s y n c 0 1 2 3 4 5 数据传输量 网络大小 存储空间健壮性 计算量 s l o w s y n c 0 1 2 3 4 5 数据传输量 网络大小 存储空间健壮性 计算量 i n t e l l i s y n c 0 1 2 3 4 5 数据传输量 网络大小 存储空间健壮性 计算量 c p i s y n c 0 1 2 3 4 5 数据传输量 网络大小 存储空间健壮性 计算量 syncml 数据传输量 网络大小 存储空间健壮性 计算量 图 2 . 4 同步协议的可扩展性比较。比例取值越大，表现越好。 数据传输量：即同步设备间交换的数据量大小。这是衡量一个同步协议优劣的很 重要的可扩展性指标之一，因为它直接反映了同步所需要的时间，即通信复杂度。在 这一方面，cpisync 表现较好，它仅仅比信息论中的最少同步通信，多花费了很少的 一部分1920。 计算量：即数据同步协议对移动设备计算能力的要求，也反映了同步时设备所要 处理的数据量。这也是一个重要的衡量指标，因为通常，pda 等移动设备的计算能力 相对较差。在这一方面，slow sync 优势巨大，因为它几乎不需要计算，cpisync 计算 强度较大。 网络大小：即数据同步协议对网络中增加节点的适应能力，换句话说，也就是数 据同步协议所能够支持的同步设备数量。fast sync 在这一方面表现最差，因为它只允 许两台设备同步。syncml 同样不适用于大型的网络，因为每台设备需要保存网络上 第二章 数据同步协议及其扩展性分析 10 其他每台设备的同步信息。 intellisync 相对较好， 但由于它的星型集中式网络拓扑结构， 也无法很好的应用于大型的网络。 健壮性：即数据同步协议的健壮程度，这是任何一个多设备的同步协议所期望的 特点。在这里主要是指同步协议对