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

2

经过大量实验，我们发现连续出现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]，Y_j = y[1..j]，其中x[1..i]表示源程序的第一个到第i个字节，y[1..j]表示目标程序的第一个到第j字节。用c[i,j]表示从X_i 到Y_j所用的最小的代价。由于所有的命令长度均相同，故每条命令代价都为1，c[i,j]也就是代表从X_i 到Y_j 所需的最小的命令数，求得最小的命令数，别且记录下其操作，我们就能得到最小的补丁文件。这样我们有以下几种情况：

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

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

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

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

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

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机上进行的。即界面中的生成补丁按钮。

图3.3 界面-生成补丁功能

2.3在LM3S1968上的实现

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

整体的流程为:

图3.4更新流程图

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

3.1 Deluge协议简介

Deluge协议是一