基于BSDiff的改进远程增量更新方案

陈迪荣，包晓安，杜 鹏，胡逸飞，苏鸿斌

(浙江理工大学 信息学院，浙江 杭州 310018)

物联网被视为继计算机、互联网之后信息技术产业发展的第三次革命[1-2]。基于物联网技术的智能可穿戴设备、智能家居、智能传感器等应用越来越成熟[3-5]，相应的应用端业务的更新和迭代也越来越频繁。由于终端设备数量庞大且布设范围广，为了更好地维护相应的设备，远程在线更新固件的功能十分重要[6]。传统的远程固件更新通常采用全量更新的方式。这种更新方式往往需要长时间占用网络带宽，同时还可能会出现丢包、断连等情况，不仅增加流量资费，还增加终端设备功耗[7]。因此，减少更新传输的数据量，提高升级的效率是物联网终端设备远程更新需要解决的关键问题。

文献[8]基于LWM2M 协议对物联网云平台进行优化，提高了远程更新的通用性、可靠性和稳定性。文献[9]针对无法主动进行联网更新的终端设备，提出了通过与终端设备相连的主控设备进行邮递式升级的方案。但是该方案没有对接云平台，在批量作业中缺乏灵活性。文献[10]通过改进BSDiff算法生成的补丁文件格式，提高了终端打补丁的效率。文献[11]在文献[10]改进的补丁文件的基础上，将BSDiff 算法中的并行解压过程替换为串行解压，并减小了申请的辅助空间，提出了一种节约内存的增量更新算法。文献[12]设计了一套安全备份和校验机制，保证远程升级过程中数据传输完整可靠，并使用差异文件减少升级的流量消耗。目前，除了软件升级方面，增量更新还被广泛应用于数据同步、云存储、蛋白质序列比较等场景[13-14]。

以上研究从远程更新平台设计、终端设备升级过程以及增量更新的应用进行了分析。由以上分析可知，通过增量更新的方式可以有效减少传输的数据量，提高终端设备更新的效率。本文以减少需要传输的更新数据量为核心思想，对更新服务端的固件管理方案进行优化，采用改进的BSDiff差分算法即时生成新旧固件的增量更新文件，减少需要传输的更新数据量，进而提升了终端设备远程更新的效率。

1 算法分析

1.1 BSDiff差分算法

可执行文件之间的差异复杂，源文件中的微小更改可能会在整个可执行文件中造成重大更改。BSDiff差分算法的提出针对可执行文件更新前后变动的两个重要规律[6，15]：(1)在一个可执行文件中，不受修改直接影响的那一部分，差异通常很小，修改后的地址可能仅改变其最低有效的一个或两个字节；(2)更新后的代码和数据会有较大的位置变动，但这种变动大多为整块的移动，即某一块位置中代码内的指针地址变动均会有相同的位移值。因此相同源代码对应的两个代码块中，大部分内容字节差为0，而少部分需要更新的地址位移数据又存在大量相同的位移值。如图1所示，截取的是V3和V4这两个功能一致的相邻版本固件通过Beyond Compare3软件进行差异对比后的部分内容，可以看到大部分的字节差异为0，这样的字节差异字符串就具有高度可压缩特性。

图1 Beyond Compare3差异比较结果

基于以上特性，通过BSDiff差分算法即可生成高度压缩的补丁包，其具体步骤如下：

步骤1读取旧文件，使用后缀排序或者哈希算法生成字符串索引；

步骤2使用该索引遍历新文件，生成差异文件和新增文件；

步骤3将差异文件和新增文件以及必要的索引控制信息进行压缩，生成补丁包。

步骤1是目前增量更新算法的瓶颈部分。BSDiff算法采用了qSufSort后缀数组算法来进行索引的生成。该算法的基本思想是，后缀的后缀是字符串中后缀的前缀，并且已经在后缀数组的另一个区域中部分排序。因此，不再使用已经比较过的字符，而是使用现有的部分结果。该算法时间复杂度为O(nlogn)，空间复杂度为O(n)。算法伪代码如下[16]：

def qSufSort(T)

Sort suffixes Si according to their first character into SA

Init additional arraysVandL

h:= 1

while(-L[0]!=n):

Sort suffixes Si in unsorted groups in SA byV[i+h]

Mark borders of Aleft，Amiddle and Aright

Calculate new groups

UpdateVandL

h=h·2

1.2 DivSufSort后缀数组构造算法

后缀数组的有效构造是一个研究热点，目前已经有许多优秀的后缀数组构造算法，其中DivSufSort是目前实践上速度最快的后缀数组构造算法[16]，其理论时间复杂度为O(nlogn)。此外，还有时间复杂度为O(n)的SAIS算法。DivSufSort与SAIS算法都是基于诱导排序的后缀数组构造算法，但是DivSufSort更快。其主要原因可以归为两点[17-18]：首先，SAIS算法通过递归的方式对初始后缀进行排序，而DivSufSort采用了实际运行时更快的字符串排序和类似前缀倍增的方式，同时还采用了重复检测等方法，进一步减少了运行时间；其次，在SAIS算法中，已被初步排序的后缀在之后的诱导过程会被移动，而在DivSufSort算法中则保持不动。这使得DivSufSort算法在第一阶段的诱导过程中可以更快。Google对以上后缀数组构造算法进行了运行时间以及内存空间占用上的对比，对比结果如下表所示。

综合表1、表2可知，在运行时间上，DivSufSort表现明显优于qSufSort，平均提升了61.10%。而在内存空间占用上，DivSufSort的表现仅次于SAIS。相较于qSufSort，DivSufSort平均减少了约35.51%的内存空间占用。

表1 运行时间对比

表2 内存空间占用对比

2 远程增量更新方案设计

为了提高终端设备远程更新的效率，本文以减少需要传输的更新数据量为核心思想，采用远程下发增量更新包的方式进行终端设备的更新。远程增量更新方案以BSDiff差分算法为核心，可以生成高度压缩的增量更新包，有效减少传输的时间和数据量。此外，选用性能更高的DivSufSort后缀数组构造算法还可对BSDiff差分算法进行改进，以提高差分算法的运行效率。远程增量更新系统整体框图如图2所示。首先，在增量更新服务平台进行终端设备固件版本号的比对；然后在增量更新服务平台运行改进的BSDiff差分算法，生成新旧版本固件之间的增量更新包；最后，终端设备通过物联网无线传输网络请求增量更新包数据，终端设备执行BSPatch程序构造完整的更新包。校验通过后，终端设备执行升级程序。

图2 增量更新方案整体框图

2.1 改进的BSDiff差分算法

改进BSDiff差分算法生成补丁包的具体步骤与原先的BSDiff差分算法相同，其主要区别在于使用DivSufSort后缀数组构造算法对步骤1中生成旧文件的字符串索引的过程进行了改进。具体分为3个阶段[16]：

(1)对旧文件进行一次扫描，确定所有后缀的类型，并计算相应的c0和(c0，c1)的桶边界；

(2)对所有B*后缀进行排序，并将它们放置在SA中的正确位置。首先必须对B*子字符串进行排序。然后，使用排序后的B*子字符串的等级对相应的B*后缀进行排序；

(3)对SA进行两次扫描，以得出所有剩余后缀的正确位置，从而得到字符串索引。首先从右向左扫描以诱导所有B后缀，然后从左向右扫描以诱导所有A后缀。

2.2 远程更新服务平台分析

远程更新服务平台主要实现远程更新的管理控制功能，包括固件包的管理、版本控制以及更新数据下发等。传统的全量更新方案一般只需要在更新服务平台保留一个最新版本的固件包。这种方案使得更新服务平台的控制逻辑变得较为简单，但是由于每次更新都需要向终端设备发送整个固件包，这就导致终端设备需要长时间连续的与更新服务平台进行数据通信，终端设备耗电量大，更新效率低。当同一时段请求更新的设备过多，还会对更新服务平台造成较大的压力。

传统的增量更新方案需要在更新服务平台进行增量更新包的集中管理，当终端设备进行邻近版本更新时，只需发送一个相应的包。由于这些增量更新包通常是高度压缩的，可以有效减少更新时传输的数据量。但是当设备需要跨越多个版本进行更新时，更新服务平台则需要多次发送补丁包，这使得终端设备的更新效率有所降低。

2.3 改进的增量更新服务平台

与传统远程更新服务平台方案不同，本文设计的增量更新服务平台需要保留用户上传的每一个版本的固件包，这是因为无法保证所有的终端设备都已经及时升级到最新版本，而增量更新包需要通过对比新旧两个版本的固件才能生成。虽然这会消耗更新服务平台更多的存储空间，但是这使得终端设备可以更加方便地进行版本回退以及跨版本更新等操作，给终端设备地更新带来了更多的灵活性。在增量更新包的生成上，根据终端设备的版本查询请求，在更新服务平台即时地生成增量更新包。增量更新包的生成基于BSDiff差分算法，并且使用运行效率更高的DivSufSort后缀数组算法对其进行优化，提高增量更新包生成的效率。同时，新生成的增量更新包还需要在更新服务平台保留一段时间，以便提供给有相同更新需求的终端设备使用，提高更新服务平台的效率。

3 实验及结果分析

本文实验的终端设备选用乐鑫科技的ESP8266物联网芯片，更新服务平台则搭建在云端，操作系统为Linux，版本为Ubuntu16.04，实验样本的具体数据如表3所示。其中V1为功能实现的初始版本，V2在V1的基础上增加了新功能并在整体上进行了完善，V3、V4针对一些运行时出现的问题进行了修复，其中V4为最终版本。从V1到V4，代码差异逐版本减小。

表3 增量更新测试文件

3.1 评价指标

本文以差分过程耗费的时间和传输数据压缩率分别作为差分算法和远程增量更新系统的主要评价指标。定义压缩率Rcmp的计算方法如下

Rcmp=(Nnew-Ndate)/Nnew×100%

(1)

式中，Nnew为目标更新版本固件包的总字节数；Ndate为传输数据的总字节数；压缩率Rcmp表示相较于全量更新，通过增量更新可以减少的传输数据量的程度。压缩率越大，表示增量更新系统性能越高，传输时间、设备功耗以及网络流量开销越少。

3.2 实验设计与分析

实验通过在Linux命令行运行BSDiff差分算法来仿真更新服务端进行差分运算并获取指定更新包的过程，通过运行time指令来获取BSDiff算法运行的准确时间。

在实验开始前，先将终端固件手动烧写成V1版本，并根据实验场景在服务端上传指定的更新包。然后，触发终端设备更新指令，使用http协议向服务端请求指定更新包。终端设备接收完成后，校验更新包，校验通过则进入更新流程。最后，通过查看终端设备日志确认版本是否更新。

实验设计了终端设备邻近版本更新与跨版本更新两种场景，分别对比了全量更新方案、传统的增量更新方案以及本文设计的优化增量更新方案在这两种场景下的表现，实验结果如表4和表5所示。

表4 邻近版本升级

表5 跨版本升级

在邻近版本更新时，相较于全量更新方案，改进的增量更新方案的数据压缩率与传统的增量更新方案相同，平均能达到96.80%的压缩率。但是，改进的方案传输的数据量平均多了10 Byte。这是由于BSDiff差分算法在处理某些文件时间过长，因此对BSDiff差分算法中查找最大相似字符串的过程进行了改进。

在跨版本升级的场景下，改进的增量更新方案的数据压缩率平均达到了95.09%。对比传统的增量更新方案，改进增量更新方案的整体数据压缩率平均提高了2.07%，并且从代码差异最小到最大的版本变更情景中，提高的压缩率从1.19%上升到了3.3%，说明改进的增量更新方案在跨版本升级时，随着版本之间的代码差异增大，其优势也随之增加。这是由于传统的增量更新方案在跨版本升级时需要发送多次patch包，导致重复发送了部分相同的差异字段与索引控制信息，而改进方案只需要发送一次。

此外，实验针对不同大小的文件，对BSDiff与改进BSDiff差分算法的差分性能进行了比较，结果如图3以及表6所示。改进BSDiff差分算法在生成增量更新包时，其平均处理时间比原先的BSDiff差分算法平均减少了31.19%，同时，对于原先导致BSDiff算法长时间运行的特殊测试用例，即最后一组数据所示的情况，改进BSDiff算法也能进行高效处理。

表6 差分算法运行时间

图3 差分算法性能比较

从实验结果与分析可知，本文所提出的改进增量更新方案可以高效地对需要传输的更新数据进行压缩，从而提高远程更新的效率，达到节省终端设备功耗的目的。在跨版本更新时，也可以有效减少需要传输的数据量，并且版本之间代码差异越大，其效果就越明显。此外，改进BSDiff差分算法在运行时间上，相较于原先的BSDiff差分算法也有较大提升，整体上可以将差分运算的时间控制在秒级，达到了预期结果。

4 结束语

本文研究了物联网终端设备的远程增量更新方案，综合考虑了传统全量更新方案需要传输的数据量大但是更新过程简单，以及传统增量更新方案传输的数据量小但是跨版本更新性能弱的特点，对两种方案的优缺点进行了整合和改进，提出以改进的BSDiff差分算法来减少更新需要传输的数据量，同时优化更新服务平台的固件管理方案，从而达到节省传输流量，提高终端设备更新效率的目的。本文对方案进行了仿真验证，并取得了预期结果。使用BSDiff差分算法进行终端设备的远程增量更新可以有效减少需要数据量，提高终端设备的更新效率。但大量的物联网终端设备内存小，资源有限，而运行BSPatch构建新版本固件时内存消耗大，因此在保持较高压缩率的同时减小终端设备的内存消耗也是一个重要的研究课题。