群体机器人程序更新系统的设计

陈晓松

0 引言

群体智能作为一个新兴领域，自20世纪80年代出现以来，受到了学术界和各行各业的广泛关注。如今，群体智能逐步从理论研究向工程应用过渡。相比较抽象的行为算法，群体实验越来越突显其重要性。

在功能调试过程中或需求发生改变时，使用者需要对机器人节点进行再编程。对于数量相当可观的群体来说，依靠人力频繁地对群体中所有节点逐个进行程序更新，将耗费巨大的时间成本。一种解决办法是采用无线通信的方式（群体机器人一般具有无线通信功能），将新程序文件发送给需要再编程的机器人节点，让节点进行自我更新。无线广播的程序更新方式具有避免人工插拔、方便并行烧录和在线更新程序等优点。

在无线传感网络领域，通过无线广播实现网络中批量节点程序更新的研究总结如下。

2003 年UC Berkeley公布了一种多跳无线传感器网络的数据分发技术[1]，其中提出的Deluge协议，很好地解决了可靠数据分发的问题。2010 年浙江大学的Wei Dong 提出以每个函数作为单元对程序进行更新的思路[2]。这种方法减少了通信量，但依赖于特定的编程语言和编译器，对于不同的软硬件平台一般不具有可移植性。

与无线传感网络相比，群体机器人[3]程序更新具有其特殊性，如群体布局范围有限，多数节点在相互的通信范围之内；群体实验中节点程序更新更加频繁，要求更新过程能迅速收敛等。

1 系统框架

系统分为两个部分，基站和待更新节点。基站根据待更新的目标程序和当前节点中运行的程序副本，生成补丁文件（即差异文件），并将文件广播出去；节点接收到完整的补丁文件后，对其解码，并进行自身程序的更新。更新完成后，节点向基站发送确认信号。实际通信中，使用可靠数据分发无线通信协议，确保所有节点都能快速地接收到完整正确的补丁文件。单个节点的更新过程，如图1所示：

图1 批量更新系统的工作流程

2 可靠数据分发协议

保证程序顺利更新，首先要确保所有节点得到完整正确的目标程序数据。这就要求在不可靠的MAC层之上，设计一个可靠的运输层数据分发协议。同时要提高通信效率和收敛速度。系统借鉴了 Deluge数据分发协议[4]并做了若干改进。

Deluge协议的设计初衷是用于进行较大规模的数据分发，比如大块数据传输和远程系统升级等。协议引入了复杂的控制信息，实现起来难度较高；同时，许多数据分发的应用场景提供Deluge 协议中的一些高级功能并不能明显提升网络性能，比如网络节点较少则不需要流水线数据分发，数据块较少则不需要分页等。基于以上原因，论文在提出若干常见应用场景假设的基础上，对Deluge 协议做了简化和补充。

改进1：取消分页，以一帧为单位进行空间多路传输。目标文件一般为补丁文件，即新旧程序的差值，文件较小(一般不超过5K)，不需要分页。

改进2：分为两阶段通信。第一阶段为“听取”阶段，由基站广播目标文件，所有节点只负责接收；第二阶段为“交流”阶段，运行原Deluge协议，所有节点相互学习直至数据完整。整个数据分发过程类似于讲课过程，第一阶段类似于上课听讲，第二阶段类似于课下讨论。在群体实验中，大部分节点都在基站的通信范围之内（这与Deluge协议假设的场景不同），因此，“听取”阶段可以一次完成大部分数据的接收，显著提高了分发效率，整个过程，如图2所示：

图2 数据分发两阶段通信示意图

改进3：在“交流”阶段增加了应答信息。应答信息只在已完成接收节点和基站之间使用，用于帮助基站统计已完成接收的节点，控制通信过程的收敛，其内容即为待确认节点的编号。应答信息寄存在Deluge协议MAINTAIN状态下节点的广播广告中，和广播一同发送和被接收。如图3所示：

图3 应答过程示意图

当某个已完成接收的节点接收到应答信息时，它将会把此信息合并到自己的广播中；当基站接收到应答信息时，它将把对应节点的状态设为“更新完成”。一旦所有节点都标记为“更新完成”或超时，基站将发送“重启”命令，宣告本次更新结束。

3 补丁文件

增量式程序更新方法[5]发送新旧程序之间的差异，即“补丁”，它包含程序更新所需要的全部信息。补丁文件一般比新目标程序小得多，因此传输效率更高。补丁文件要尽量小，以减轻通信压力；同时由于单个节点的资源有限，使用补丁进行更新的时间和空间开销要足够小。

3.1 使用补丁进行程序更新

首先定义了集成补丁文件的5种指令。节点根据这些指令进行程序更新，更新的基本单位是字节。指令定长，为2个字节，前3比特为指令标志，具体定义，如表1所示：

表1 指令定义

这里，通过一个示例说明更新指令是如何工作的，如表2所示：

表2 更新程序过程示例

我们用“命令_长度/数据”的格式代表指令，以便更清晰地进行描述。假设某个群体机器人收到了补丁文件中指令集合为第一列所示，原程序为“ABCDEF GHIJKLMOPQ RSTUVWXYZ”。

可以看出，实际上使用Delete和Insert两条指令就能够完成程序的更新，引入Replace和Copy指令是为了减小补丁的尺寸。

3.2 补丁生成方法

设i和j，m和n分别代表原程序A和目标程序B中的当前偏移地址和长度。使用各个更新指令的必要条件和代价，注意 Copy和 Delete指令表示的最长连续字节数为213-1=8191，如表3所示：

表3 指令的必要条件和代价

在明确了指令产生的必要条件以及每条指令的代价后，可以得出求解最小差异文件长度的递归式。用Cost[i,j]表示从原程序的1到i字节更新为新程序的1到j字节所需的最小代价。

为了避免递归求解带了的重复运算，可以使用动态规划的方法求解这个递归式，并记录指令序列。具体参考动态规划方法求解最小编辑距离问题[6]。

4 测试结果

在确认使用补丁进行程序更新无误的情况下，以分发数据长度和节点数目为变量对更新效率进行了测试。测试结果，如图4所示：

图4 通信实验结果

其中左右子图中的曲线分别显示节点个数和数据长度与更新所需时间的关系。完成更新所需时间随节点数目和数据长度增长而增长，但小于正比例增长关系。实际上，数据通信是影响更新速度的最大因素，其中第一阶段通信时间与数据长度相关，第二阶段通信受节点数目影响较大。更新的绝对时间还与具体的硬件相关。

5 总结

本文针对群体智能实验中群体机器人的再编程问题，提出了基于无线广播的高效可靠的批量节点程序更新方法。在无线传感网络领域相关研究的基础上，考虑了群体机器人的特点，提出并论述了两阶段数据分发协议和面向字节的最小程序补丁生成方法。系统在实际应用中体现出了高可靠性和高效率。驱动程序设计方案，较原来设计方案更加稳定。

[1]Adam Chlipala, Jonathan Hui, Gilman Tolle. [M]"Deluge: Data Dissemination for Network Reprogramming at Scale" ,2003.

[2]Wei Dong, Yunhao Liu, XiaofanWu Lin Gu and Chun Chen Elon: EnablingEfficient and Long-Term Reprogramming [M]forWireless Sensor Networks 2010.

[3]Gerardo Beni, “From Swarm Intelligence to Swarm Robotics”. [C]Lecture Notes in Computer Science, 2005, Volume 3342/2005, 1-9, DOI: 10.1007/978-3-540-30552-1_1

[4]Hui J. and Culler, D. "The dynamic behavior of a data dissemination protocol fornetwork programming at scale," in Proceedings of the 2nd international conference onEmbedded networked sensor systems. [J]ACM Press,2004, pp. 81-94

[5]Michiel Konstapel "Incremental software updates for wireless sensor networks"Master's Thesis [J]in Computer Science, May 24, 2006

[6]Levenshtein VI (1966)."Binary codes capable of correcting deletions, insertions, and reversals".[J]Soviet Physics Doklady 10: 707–10.