嵌入式多节点的无线批量程序更新系统设计(一)

　　一 总体设计和平台简介

　　项目旨在实现多ARM节点通过无线通信完成对批量节点的程序烧录，如图2.1所示。系统分为上位机、发射接收模块和待烧录节点三个部分，上位机通过ID号选择待烧录节点并通过无线模块向下广播烧录数据，各被选择节点通过无线模块接收烧录数据检查无误后存储。上位机软件设定待烧录节点的ID、烧录文件目录、发送数据包大小、发送速率等参数后将数据打包传送到基站，基站通过无线发射模块广播数据。 

　　整体思想是利用已有的代码和目标代码进行比较。将两者的差异通过无线网络(802.15.4)广播出去。在每个接受节点根据收到的差异文件(也就是补丁文件patch)，对原有代码进行修改(patching的过程)以达到更新程序的目的。

　　总体上来说本项目有两大难点，涉及到巧妙的算法设计。

　　1、如何用尽可能少的字节数，来表示不同代码之间的差异?

　　2、如何确保可靠性传输?

　　关于问题1，我们知道要待传输的字节数越少，对通信的要求越低。更新程序的效率也会更高。而且少的字节数也意味着丢更少的包。关于问题2，由于我们是要对代码进行修正，所以一个字节的错误可能就会造成整个程序的崩溃。这对嵌入式程序，特别是运行在成千上万个节点上的程序是不可接受的，必须保证100%的正确接受。除此两大难点(也是关键点)之外，还有一些别的附加要求。如果满足了能够提高系统的持久性。分别是：

　　1、使用尽可能小的RAM。因为嵌入式芯片的RAM普遍珍贵。

　　2、消耗尽可能少的能量。

　　3、更新速度尽可能的快。

　　项目使用的硬件平台是我们自制的智能小车eMouse 。平台采用 TI公司32位Stellaris LM3S1968微处理器，工作频率为50MHz，内含256 KB单周期Flash和64 KB单周期SRAM，flash支持可由用户管理的块保护和数据编程;板上Zigbee模块通过串口与CPU通信，模块仅提供MAC层服务，CPU与模块间以MAC帧的形式通过串口传递数据。eMouse外观如图2.2所示。

　　项目开发系统环境为Ubuntu9.04，程序编译和下载工具分别为开源的sourcery G++和Openocd，用户界面采用java语言编写。

　　以下章节将对系统设计作详尽的论述。

　　二 程序更新设计与实现

　　一些传统的更新方法注重代码本身的特点。比如以函数为基本的更新单位。在每个节点上运行一个动态链接器，将新的函数重新链接到原程序。其实代码本身可以将其视为一串二进制的文本文件。代码的更新即是从一串旧的文本更新为一串新的文本。

　　为此我们定义了一系列基本的更新操作命令，以及两个辅助的索引指针：in_index以及out_index。in_index代表输入文件当前的索引值，而out_index代表输出文件当前的索引值。

　　基本的命令如下：

　　Copy:将in_index所指的字节复制到out_index处，并且in_index和out_index分别加1。

　　Replace A:将当前out_index所指的字节用A来替换，并且in_index和out_index分别加1。

　　Delete:in_index加1,out_index不变。实际为删除in_index所指的字节

　　Insert A:在当前out_index处插入A，in_index不变,out_index加1。

　　Kill:表示删除in_index后所有的原程序代码。

　　其中包含了如下的子问题：

　　2.1 命令的表示

　　通过上面所说的基本命令的组合，我们可以表示出从一个旧文件到一个新文件的过程。随之带来了一个问题。这些命令应该如何表示才能尽可能的降低补丁文件(命令的组合)的大小?

　　有几个需要注意的地方：

　　如果有连续的Copy命令，我们可以将其合并成一条命令，只要在Copy后加上表示长度的Length参数即可。

　　同理，如果有连续的Delete命令，也可以将其合并成一条命令，只要在Delete后加上表示长度的Length参数即可。

　　如果可以利用Replace命令，就不要用Delete和Insert命令的组合。这其实是另一重要的子问题:如何根据这些命令产生尽可能少补丁文件?

　　有五条基本命令，这样为了区别这五条命令，至少需要3个比特。

　　由于大多数情况下，更新的大多数是程序的参数。也就是说Copy命令的数目远远大于其他命令。我们定义这5条命令如下表所示：

表3.1

　　经过大量实验，我们发现连续出现Copy的情况最多，因此Copy命令操作码只有1位，即只要是最左端比特为1，则此命令为Copy命令。这样Copy的操作数为15个比特，一次能表示复制32768个字节。同理，Delete的格式同Copy时相同的，只不过其操作码较长，操作数只有13位，最多能代表删除8192个字节。实际上这也完全够用了。

　　Replace和Insert操作码的有效位为最左端三位，紧跟着5个比特是保留位，当前还没有用到。操作数的长度为一个字节，表示当前要替换的或者要插入的新值。

　　Kill命令操作码为左端3个比特，剩下的15个比特都是保留位。操作数的长度为一个字节，表示删除的起始索引。

　　综上可以看出，指令的格式都是定长的——2个字节。定长的代价是会浪费一定的比特。造成实际生成的补丁文件略大(由于Insert，Replace和Kill的保留位)。但正如MIPS处理器，定长的规定使得整个指令集简洁有序。虽然产生的指令条数要比X86系列的CISC机要多，但简洁的特性总是让人喜欢的。

　　2.2 命令的产生

　　这是最有挑战性的问题，如何根据前面定义的基本命令，产生尽可能小的操作指令集(补丁文件)?仔细观察发现，其实此问题包含了一个最优子结构，也就是说，我们可以用动态规划的算法来解决这个问题，保证产生的补丁文件是最小的。

　　假设原程序的长度为m个字节，目标程序的长度为n个字节。定义= x[1..i]，Yj = y[1..j]，其中x[1..i]表示源程序的第一个到第i个字节，y[1..j]表示目标程序的第一个到第j字节。用c[i,j]表示从Xi 到Yj所用的最小的代价。由于所有的命令长度均相同，故每条命令代价都为1，c[i,j]也就是代表从Xi 到Yj 所需的最小的命令数，求得最小的命令数，别且记录下其操作，我们就能得到最小的补丁文件。这样我们有以下几种情况：

　　如果最后的操作为Copy，则一定有x[i] = y[j]。原问题包含将Xi-1 转化到Yj-1的子问题。c[i,j] = c[i-1,j-1]+1

　　如果最后的操作为Replace，则一定有x[i] != y[j]。原问题包含将Xi-1 转化到Yj-1的子问题。c[i,j] = c[i-1,j-1]+1

　　如果最后的操作为 Delete，则没有什么必须满足的条件。原问题包含将Xi-1 转化到Yj的子问题。c[i,j] = c[i-1,j]+1

　　如果最后的操作为 Insert，也没有什么必须满足的条件。原问题包含将Xi 转化到Yj-1的子问题。c[i,j] = c[i,j-1]+1

　　如果最后的操作为Kill。由于Kill表示删除源程序所有剩余的字节。Kill只能出现在最后一个操作上。即完成Kill后就已经使得Xm 转化为了Yn。

　　c[m,n] = min(c[i,n]) + 1, 0<= i<= m

　　这样所有的情况都已经包含在内。对于每一个i,j我们可以求得最c[i,j]

　　公式从上到下依次代表了Copy,Replace,Delete,Insert和Kill这五种情况。

　　整体的伪代码如代码3.1所示：注意，我们不仅求得每一个c[i,j]而且记录下了与其相应的操作.op[i,j]这个数组中的每个元素为一个结构体，包含操作数以及操作码。

　　代码3.1得到c[i,j]以及op[i,j]

　　这样，我们得到了c[m,n]以及操作表。下面就是要求得操作序列。根据之前生成的操作表，采用一个递归的方法得出最小代价的操作序列。伪代码如代码3.2所示：

　　代码3.2生成最小代价的操作序列

　　这样，我们得到在定长命令下，最小的补丁文件。以上都是在PC机上进行的。即界面中的生成补丁按钮。

　　2.3在LM3S1968上的实现

　　在PC机上的部分比较容易实现(生成patch文件)。但在LM3S1968这个嵌入式芯片上进行代码的替换就不是很简单了。首先我们要确定各个文件的位置。这里为了简单起见，将flash的0x0000到0x3000处，设为更新服务程序区，初始化必要的硬件(通信、flash等),等待基站发送的命令来更新程序或者直接将控制转移给应用程序程序，本部分的程序在启动后首先运行。如果检测0x4000处为合法的应用程序，则将控制权转交给它，每个应用程序在接受到了“等待接受”命令后，又将控制权转移给更新服务程序，等待从基站发来的其他命令。需要注意的是在将控制权转移到应用程序时，中断向量表的位置，栈指针，是两个要小心设置的量。否则会造成整个系统的崩溃。而且本部分只能用汇编语言写，具体可以参见bl_start_gcc.S。0x3000到0x7000处为应用程序区，存放待运行的程序。0x7000以后存放这从主机发来的Patch文件。

　　整体的流程为:

　　三 可靠数据分发协议的设计与实现

　　3.1 Deluge协议简介

　　Deluge协议是一个优秀的可靠性数据分发协议，由加利福尼亚大学伯克利分校的David Culler等人在2004年提出的，首先在TinyOS1.1.8操作系统上实现。协议的设计初衷是用来进行较大规模的数据分发，比如大块数据传输和远程系统升级等。

　　在Deluge协议中，采用了协商式交互策略(ADV-REQ-DATA)来实现受控泛洪。而整个网络由状态机来控制数据的分发，网络中每个节点都处在MAINTAIN、RX和TX三种状态的其中一种，并且遵循该种状态下的一系列动作规则。在Deluge协议中，把将要分发的目标文件(Sobj)划分为固定大小的程序包(Spkt)，由N个程序包(Spkt)组成一个程序页(Spage)。Deluge协议对整个目标文件数据的划分如图4.1所示。基于这种数据结构，Deluge协议支持空间多路技术以提高数据传输的速度，在协议中的具体实现是流水线传输(Pipelining)。

　　Deluge协议引入了复杂的控制信息，而目前很多无线传感器网络应用中的节点都不能支持像TinyOS这样的操作系统，因此实现起来难度较高;同时，许多数据分发的应用场景提供Deluge协议中的一些高级功能并不能明显提升网络性能，比如网络节点较少则不需要流水线数据分发，数据块较少则不需要分页机制等。基于以上原因，本设计在提出若干常见应用场景假设的基础上对Deluge协议做了简化和补充。