基于Rsync算法的增量网络编程

许 宏

(淮阴工学院，江苏淮安223003)

0 引言

随着智能终端在各个领域的广泛应用，智能终端软件的维护变得日益重要。因此，智能终端软件的更新逐渐成为智能终端实际应用的一个重要问题。当智能终端安装数量较多，或安装位置不方便的情况下，采用人工更新方式会花费较大的人力和物力。

网络及通信技术的飞速发展，Internet越来越普及到人们的日常生活中，人们对Internet的需求也越来越大，Internet所带来的好处也越来越得到体现，使许多的信息家电、智能仪表等非PC智能终端接入到互联网成为可能，从而实现网络化、智能化的集中管理。智能终端投入实际环境中运行后，一部分在软件开发过程中无法充分测试的错误便会暴露出来;在智能终端的运行期内，用户也往往会对智能终端软件提出新的功能要求和性能要求。增量网络编程可以通过远程通信的方式实现智能的自动更新，有效降低了更新和维护成本。

1 增量网络编程原理

增量网络编程主要分为三个步骤:编码、分发和解码。在编码阶段，主控系统只读入程序代码并将每一行都保存在一个队列中，并准备分发的代码包［1］。

在分发阶段，主控系统将程序代码以数据包的格式发送，智能终端将接收到的数据包存放在外部闪存中。由于网络编程模块以用户级别运行，无法直接将程序代码写入程序存储区，所以将其存放在外部闪存，同时智能终端请求主控系统重新传送丢失的数据包。

写入到外部闪存的代码包与初始的程序代码具有相同的格式，在解码阶段，智能终端只要验证程序映像并调用BootLoader将程序代码保存在程序存储区。BootLoader是在系统内核运行之前运行的一段小程序。通过这段小程序，可以初始化硬件设备、建立内存空间的映射图，从而将系统的软硬件环境带到一个合适的状态，以便为最终调用系统内核准备好正确的环境。BootLoader具有向程序存储区的用户应用程序部分写入数据的权限。然后重新启动系统，执行最新建立的应用程序。

图1 增量网络编程过程

为了设计一个增量网络程序编程机制，需要考虑许多影响系统性能的因素。由于网络编程时间与更新的数据量成正比，同时数据量也决定了传输数据的网络成本，因此尽可能地降低更新的数据量可以缩短网络编程的时间，降低使用成本。程序代码存储在外部闪存，而外部闪存的访问速度要远远低于片上存储器，为了获得更好的性能，应该尽可能减少访问外部闪存。由于智能终端的处理能力有限，应该将大部分处理放在主控系统执行，而智能终端只处理最基本的操作［2］。

在外部闪存中，划分两块存储区域，一块用于以前的程序映像，另一块用于存储将要建立的新映像(图2)。其优点在于可以提供相同的内存映射并最小限度的影响BootLoader代码的重写。通过对BootLoader的修改，使其可以从由网络编程模块传递的基地址处读取程序代码。

图2 存储器组织结构

2 基于Rsync算法的增量网络编程

2.1 增量代码的产生

对于增量网络编程，通常使用的方法为:主控系统将程序映像文件分割为尺寸固定的块，并比较以前版本和最新版本相应的块来获得改变的程序块(图3)，将其称为固定块比较。当程序代码映像移位时，固定块比较无法找到相同的程序块，因而该方法的效率不高。为此，采用Rsync算法［3］来产生增量并重建代码映像。Rsync算法最初主要用于通过低带宽网络在两个设备间进行二进制代码的更新。

图3 通过固定块比较产生增量代码

Rsync算法可以找出最新版本程序中哪些部分和原有程序中某个部分匹配，这部分的内容就不需要通过网络传输，需要的只是对原有程序相应部分的引用，而新程序中无法匹配的部分就只能逐字传输。智能终端根据对原有程序的部分引用和逐字传输的内容来构造出新程序的一个副本。假设主控系统α的最新版本程序为Fnew，智能终端β的原有程序为Fold，算法的步骤为:

(1)智能终端β将文件Fold分成互不重叠、尺寸固定的一系列数据块，块的尺寸为S字节，S∈［500，1000］，最后一个数据块可能少于S字节;

(2)智能终端β计算所有数据块的校验和:32位的滚动弱检验和Ri以及128位的MD4强检验和Mi，记为hi＜Ri，Mi＞。建立哈希表，对于每一对校验值，以滚动校验和为关键值进行哈希排序，并将哈希表传送给主控系统α;

(3)主控系统α在文件Fnew中为所有长度为S字节的数据块(这些数据块对于文件头的位移量可以是任意的，不只是S的倍数)计算滚动校验和并与哈希表中的hi＜Ri，Mi＞中的Ri比较，发现与Ri相匹配的数据块，再计算其强校验和与Mi比较，如果强校验和相等，说明这两个数据块相同，记录该数据块的索引，即hash指示值，继续比较下一个数据块;如果不相等，说明这两个数据块不同，则记录该数据块第一个字节，然后向后移动一个偏移量，继续比较，直到文件末尾;

(4)比较完成后，智能终端β收到主控系统α包含差异内容和hash指示值的数据流，更新Fold，生成Fnew。

Rsync算法在新文件上进行滑动查找，移动一个字节或一个块长。它能实现快速查找，很大部分要归功于采用了滚动校验和。

图4 差异增量的产生

2.2 智能终端程序的重构

为了实现智能终端程序的更新，主控系统一般采用两种操作来描述差异:Copy(CMD_COPY_BLOCK)和Download(CMD_DOWNLOAD_BLOCK)。在增量更新中，主控系统给每个匹配的模块发送Copy报文，当智能终端接收后，就将该数据块从原有的映像中复制到当前的映像［4］。对每个不匹配的模块，主控系统发送一个或多个下载报文。

每个复制报文的数据尺寸为SREC行尺寸的倍数，而下载报文的数据尺寸为任意数值。当下载报文的尺寸大于一个SREC行(16字节)时，主控系统将其分为多个片段。

如果程序的结构没有改变时，程序映像的重构比较简单。智能终端只需要写入下载模块及执行复制操作。当程序映像发生偏移时，情况就会变得复杂。假设模块从原有的映像中偏移了k位，并且k不是SREC行的整数倍［5］。这就导致数据块横跨两个SREC行，需要两次SREC行写入。为此可以采取下面的方法来解决:

当下载的数据块小于SREC行时，智能终端按照一行SREC写入，而不填充其他的数据。这时，将SREC行的尺寸设为实际的数据长度(图5)。复制数据块时，从SREC行的起始位置进行复制。这样可以确保将每行数据块复制到一个SREC行，同时将SREC行的SREC地址域改为在新映像中的偏移地址。

为能实现智能终端程序的自动更新，我们对Rsync算法进行了改进，当智能终端收到一个复制消息时，网络编程模块立即编译执行，无须将其放入队列中。由于没有保存脚本命令，所以当有消息丢失时，网络编程模块必须检查重构的程序映像。因为不知道丢失的复制或下载消息是否导致丢失错误，所以每次丢失记录都要发送重传请求，而这将额外花费大量的时间。

为此，在智能终端中，将所有的脚本命令保存在队列中，并检查所有包含脚本命令的数据包是否丢失，当智能终端接收到解码消息后，就对脚本信息进行解码。

图5 新程序映像重构

2.3 改进的Rsync算法

为了发送脚本命令，主控系统将每个脚本命令嵌入到CMD_DOWNLOADING消息中，而嵌入消息保存在外部闪存中，CID代表在脚本队列中，SREC行的数量。为了使复制脚本与其他消息类型区别，在 SREC类型域使用了特殊数值。在SREC规定中，该域只允许使用几个数值(0，1，2，3，5，7，8和9)，在这里使用10来代表一个嵌入的复制消息。这样既可以使其具有与其他类型的数据相同的存储方式，又能够确保正确的解释复制命令。

图6 CMD_DOWNLOADING格式

由于外部闪存有足够的空间，使用外部闪存来存储脚本命令，为此，将外部闪存分为三个部分:以前程序映像、新程序映像及脚本队列。

主控系统以“下载”(CMD_DOWNLOADING)消息发送脚本，智能终端将这些脚本保存在脚本队列中。当主控系统查询任何丢失脚本命令时，智能终端扫描该脚本队列。如果智能终端发现丢失记录，则请求重新发送。主控系统响应该请求，重新发送丢失的信息。智能终端接收到解码命令后，开始对脚本进行解码，分别将嵌入在脚本命令中的下载或复制命令提取出来，并对命令进行相应的解释(图7)。

3 实验结果分析

在实验环境下，综合各方面的因素，按照前面设计的算法，实现了增量更新系统。实验时，一个主控端同时对三个智能终端进行更新，结果表明改进后的增量网络编程，通过Rsync算法产生两个程序的映像差异，再将差异部分传输给智能终端，达到快速地对智能终端编程的目的。以远程通信的方式实现智能的自动更新。

图7 解码脚本命令

4 结束语

本文以智能终端的增量网络编程为基础，对Rsync算法进行了改进，实现智能终端的自动更新，而且改进后的算法没有涉及任何具体的程序代码，具有很好的移植性。

［1］Linda Wills.An open platform for recongurable control.IEEE Control Systems Magazine［J］.2001(6):34 －36.

［2］Rahul Kapur，Tom Yeh，Ujjwal Lahoti.Differential Wireless Reprogramming of Sensor Networks［J］.UCLA CS213 Project Report，2003(12):23 －25.

［3］Andrew Tridgell.Efficient Algorithms for Sorting and Synchronization［D］.Canberra:Australian National University，1999.

［4］Adam Chlipala，Jonathan Hui，Gilman Tolle.Deluge:Data Dissemination in Multi－ Hop Sensor Networks［J］.UC Berkeley CS294 －1 Project Report，2003(12):5 －9.

［5］SOURCE A.SANs sharing storage to infinity and beyond［J］.Electronic Design，2004，52(9):16 － 19.

［6］全勇，杨杰，邓志鹏.基于增量余弦RBF网络的惯性导航初始对准［J］.上海交通大学学报，2002，36(12):35－38.