嵌入式多节点的无线批量程序更新体系规划

一 总体规划和渠道简介

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

图2.1 多节点无线批量烧录暗示

全体思维是运用已有的代码和方针代码进行比较。将两者的差异通过无线网络(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所示。

图2.2 硬件渠道eMouse

项目开发体系环境为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	1	15	2
Delete	000	13	2
Replace	001XXXXX	8	2
Insert	010XXXXX	8	2
Kill	011XXXXX	8	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 所需的最小的指令数，求得最小的指令数，别且记载下其操作，咱们就能得到最小的补丁文件。这样咱们有以下几种情况：

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

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

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

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

5. 假如最终的操作为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协议是一个优异的牢靠性数据分发协议，由加利福尼亚大学伯克利分校的David Culler等人在2004年提出的，首要在TinyOS1.1.8操作体系上完结。协议的规划初衷是用来进行较大规划的数据分发，比方大块数据传输和长途体系升级等。

在Deluge协议中，选用了洽谈式交互战略（ADV-REQ-DATA）来完结受控泛洪。而整个网络由情况机来操控数据的分发，网络中每个节点都处在MAINTAIN、RX和TX三种情况的其间一种，而且遵从该种情况下的一系列动作规矩。在Deluge协议中，把行将分发的方针文件(Sobj)区别为固定巨细的程序包(Spkt)，由N个程序包(Spkt)组成一个程序页(Spage)。Deluge协议对整个方针文件数据的区别如图4.1所示。依据这种数据结构，Deluge协议支撑空间多路技能以进步数据传输的速度，在协议中的详细完结是流水线传输（Pipelining）。

图4.1 Deluge协议中分发数据的结构

Deluge协议引进了杂乱的操控信息，而现在许多无线传感器网络运用中的节点都不能支撑像TinyOS这样的操作体系，因而完结起来难度较高；一起，许多数据分发的运用场景供给Deluge协议中的一些高档功用并不能显着进步网络功用，比方网络节点较少则不需求流水线数据分发，数据块较少则不需求分页机制等。依据以上原因，本规划在提出若干常见运用场景假定的基础上对Deluge协议做了简化和弥补。

3.2 牢靠数据分发协议的规划

在论说详细的规划思路之前，先提出以下运用场景的假定。

假定一：网络节点不支撑高档的操作体系。能够理解为有必要考虑节点处理和通讯才能有限，而且通讯协议要从底层（如MAC层）完结。

假定二：大部分待烧录节点散布在数据基站的通讯规模之内。能够理解为通讯协议不需求完结杂乱的多跳通讯和流水线，能够充分运用数据基站榜首次数据播送，这一点下文会详细论说。

依据以上两点假定，牢靠性数据分发协议的详细规划如下。

考虑到不同渠道的无线收发模块供给的服务接口和通讯质量的差异以及程序更新对网络牢靠性的要求，通讯协议挑选在网络层完结牢靠数据分发的机制，协议只需求硬件渠道在MAC层供给收发数据帧的运用接口即可。协议中，数据分发分为两个阶段：榜首轮发送阶段和节点间沟通阶段。图4.2为两个阶段通讯办法暗示图。

图4.2 数据分发两阶段通讯办法暗示图

（实线代表发送完好数据文件，虚线表明发送数据页）

1、榜首轮发送阶段。

数据基站（如PC）在接纳节点预备好后不间断播送数据帧，直至数据发送完毕；接纳节点极力接纳数据，并记载自己已有数据帧的id信息，期间不向源节点发送反应信息。

在原始的Deluge协议中没有这一阶段，因为Deluge协议中或许无线传感器网络巨大，散布规模也较广，所以数据分发一旦发动，一切接纳到数据的节点都参加到数据发送中来；而本规划中，网络充分运用了假定二中的节点散布条件，通常情况下，在榜首轮发送完毕后，恰当大比例的节点就现已接纳到了大部分的数据，而这个进程中因为只要数据基站在发送播送，网络中数据传输的功率是最高的。当然，这种节点散布条件不满意的情况也不会显着下降数据分发功率。

1. 节点间沟通阶段。

沟通阶段参阅了trickle算法的“polite gossip”战略，一切节点（包含数据基站）都参加到沟通中去。每个节点的沟通的意图都是相同的，行将自己具有的数据包发送给需求的节点和恳求并接纳自己需求的数据包。

第2阶段是确保牢靠性的要害，协议中让源节点也参加到沟通中来，这是为了防止网络情况极差以致在榜首轮发送完毕之后一切节点接纳数据的总和都不构成完好数据文件的极点情况。这一步中，节点长期处于“保护”情况标志数据分发完毕。

节点首要播送广告，每一个广告包含一个摘要(φ)，摘要(φ)由两部分组成：(1)本节点的IP标识v。(2)本节点的最大可用页号p，即φ(v,p)。可用页号p的界说：页p所包含的包被节点悉数接纳，称页p完结。页p被完结而且它之前的一切的页(0,p)也被节点悉数接纳，称页p可用。节点通过广告来了解对方具有的数据信息，继而向比自己数据更齐备的节点发送数据页恳求。协议中将时刻分红时刻片(round)，在每一个时刻片中，节点来决议是否播送一个广告。假定时刻片的长度由T_m,i来表明，它的上下界由T_l和T_h来表明，则有取T_lT_m,iT_h。在每一个时刻片i中，节点保护—个随机值r_i，r_i的值在T_m,i/2和T_m,i之间，r_i值的规模选取是为了处理短监听问题(short—listen problem)。

沟通阶段中，节点具有“保护”、“恳求”和“发送”中的人一个情况。节点在“保护”情况播送广告并听取其他节点的播送；在恳求阶段向其他节点发送数据页恳求，并接纳对方发来的数据；在发送情况播送被恳求的数据页。图4.3为情况转化暗示图。首要的沟通规矩如下。

（1）“保护”情况规矩

M1: 假定时刻片i的开端时刻为t_i，节点在t_i+r_i的时刻段内，若接纳不到广告φ=φ，则播送广告φ；若收到与φ纷歧致的广告（包含φ=φ、广告帧和数据帧等），则调整时刻片为T_l，并当即从头开端时刻片；若接纳到广告φ=φ，则调整时刻片为min(2*T_m,i ,T_h )。

M2: 节点在收到广告φ(v,p)中p大于本身的最大可用页p时，转向“恳求”情况，向节点v发送数据页恳求；节点收到恳求帧，则转向“发送”情况，播送被恳求数据页。

规矩1能操控冗余广告的发送，节省网络资源，而且依据网络情况动态调整时刻片长度，从而是网络资源得到有用的运用。

规矩2完结从“保护”情况到“恳求”和“发送”情况的转化。

（2）“恳求”情况规矩：

M3：若节点在向源节点宣布数据页恳求后节点在时刻t（t为自界说时刻长度，是经验值，依据网络情况而定）内没有收到数据，则再次发送恳求，若累计恳求次数大于k（k为自界说次数），则以为恳求失利，回来“保护”情况；若节点接纳到数据页，则在接纳完毕后回来“保护”情况。

规矩3中考虑到网络的质量要素，界说了等候时刻t和最大恳求次数k。

（3）“发送”情况规矩：

M4：节点进入“发送”情况当即播送被恳求的数据页，播送完毕后回来“保护”情况。

规矩4中要留意的是，节点以播送的办法发送数据，这意味着处于“恳求”情况的节点能够接纳任何节点（不必定是它恳求的指定节点）发送的契合其需求的数据包，这也是协议中防止网络冗余的一个表现。

图4.3 牢靠数据分发沟通阶段节点情况转化暗示图

以上是本规划中牢靠数据分发协议的悉数内容，本文鄙人一节中将详细论说协议的软件规划完结。

3.3 牢靠数据分发协议的软件规划完结

协议的软件规划在网络层完结，涉及到MAC层接口的调用。本节先简略介绍本规划试验渠道上网络模块供给的MAC层运用接口，然后详细论说软件的规划和完结。

3.3.1 MAC层接口简介

首要做两点阐明。

榜首，规划中运用的MAC层接口不供给肯定牢靠的网络通讯。一方面是因为规划运用试验室克己的硬件渠道首要用于做集体试验，而集体试验不需求牢靠的网络通讯，所以渠道的通讯模块也没有能完结牢靠通讯的机制；另一方面要求MAC层供给牢靠通讯也不是必要的。

第二，网络层只运用了MAC层供给的数据帧发送和数据帧接纳两个接口，网络层的帧结构包含在MAC数据帧的数据域中。

从榜首点能够看到，协议在网络层完结牢靠数据传输的机制，下降了对MAC层通讯质量的要求，而第二点阐明协议只是需求MAC层供给两个最根本的运用接口。本规划中的牢靠数据分发协议对底层通讯的要求很低，具有较好的鲁棒性和可移植性。

本规划试验渠道上供给的MAC层数据帧发送指令结构如图4.4所示，其间区域3为数据域，包含网络层的帧结构，别的节点在MAC层以播送的办法通讯，所以指令中不包含源节点和意图节点的地址信息。MAC层接纳到数据帧后，将数据域分离出来存储到接纳缓存区；发送数据时，将发送缓存区中的数据加上MAC层数据帧的头部和尾部并发送出去，网络层只关怀发送和接纳缓冲区中的数据。这儿规矩以下章节中说到的各种帧结构均指网络层帧结构。

图4.4 MAC层接口数据帧发送指令

3.3.2 牢靠数据分发协议的数据结构规划

网络层数据要通过缓存，解析再到存储或许履行三步操作，而且不同品种的帧要差异处理，因而一个好的数据结构规划方案对简化数据处理操作和进步数据处理功率对错常有必要的。图4.5为网络层数据流图，数据帧的流向为：

1. 从MAC层读入后放入原始数据缓冲区；

2. 经解析后得到帧结构；

3. 将帧结构作相关处理后仅提取页号（p）、帧号（id）和数据（data）放到写flash缓冲区；

4. 写flash。

留意以上是数据帧的流向，除数据帧以外的其他类型帧（如恳求帧，完毕帧等）只履行第（1）、（2）步操作。下面侧重论说图中每个阶段涉及到的数据结构。

图4.5 网络层数据流图

1. 缓冲区Deluge_buf

Deluge_buf是一个环形缓冲区，用于缓存原始的网络层数据。缓冲区实践上是由一个环形链表、两个指针和一个整数组成。链表的每个节点用于存储实践数据，节点数目依据需求而定；一个tail指针和一个head指针，别离指链表的读出点和写入点，履行一次读出或写入操作后，tail或head指针都向前移动一次，整数的作用是核算当时链表上可用节点的数目。Deluge_buf结构体界说如下：

struct Deluge_buf {

struct data_entry queue_data[QUEUE_LENGTH]; // The data of current queue

uint8 recv_num;

uint8 queue_head;

uint8 queue_tail;

};

值得留意的是结构体data_entry中Payload项的组成在不同类型的帧中是不同的，比方数据帧中Payload包含页号p、帧号id和数据data以及数据长度data_len，而广告帧中只包含p和id，因而解析办法要依据type值来区别。

1. 帧结构DelugeData

如图五所示，DelugeData界说了帧类型（type）等六个数据项，规划中依据不同的帧类型规矩了各个数据项的意义，详细界说如表4.1所示，“—”表明该数据项在帧中没有界说。

表4.1 DelugeData中数据项意义的界说

数据项 帧类型	type	v	p	id	data	data_len
数据帧	DATA	版别号	页号	帧号	数据	数据长度
完毕帧	END	版别号	页号	帧号	—	—
广告帧	ADV	版别号	页号	源节点标识	—	—
恳求帧	REQ	版别号	页号	方针节点标识	—	—
指令帧	CMD	指令参数	—	—	—	—

3、缓冲区Flash_buf

因为写flash操作比网络传输慢得多，为了防止写flash拖慢整个数据分发速度，树立缓冲区Flash_buf用于缓存预备好的数据。Flash_buf也是一个环形缓冲区，原理和Deluge_buf相同。缓冲区的节点包含p、id、data三个数据项和指针域next，其间data是要写入flash的数据，p和id用于核算待写入的flash地址。

3.3.3 牢靠数据分发协议的软件架构规划

牢靠数据分发协议的软件构架规划包含发送端和接纳端两块内容。发送端软件运转在数据基站上，分为两个阶段，榜首阶段告诉节点接连地发送整个文件，第二阶段运转情况机参加到节点的沟通中去；接纳端软件运转在待烧录节点上，榜首个阶段尽或许多的接纳基站发送来的数据，第二阶参加节点间评论。因为发送端榜首阶段软件比较简略，第二阶段和接纳端相同，所以这儿只要点介绍接纳端的软件构架规划。

榜首阶段：

程序完结初始化后进入预备接纳情况，当数据帧到来时将数据提取出来写到flash相应的地址（地址由页号p和帧号id核算得到），并将该帧标记为“完结帧”；若接纳到完毕帧，则记载完毕帧的页号p_max和帧号id_max并进入第二阶段；若接纳到其他类型帧则直接进入第二阶段。榜首阶段的软件流程图如图4.6所示。

图4.6 接纳端软件榜首阶段流程图

第二阶段：

完结榜首轮接纳后，程序运转ADV-REQ-DATA情况机，和其他节点沟通，完善或协助其他节点完善数据文件。情况机分为MAINTAIN（保护）、RX（恳求）和TX（发送）三个情况，程序首要进入MAINTAIN情况。MAINTAIN情况下，程序监听广告帧和恳求帧并在恰当机遇发送广告，依据协议规矩，程序或许跳转到RX情况或TX情况进行数据帧恳求和发送操作，操作完结后回来MAINTAIN情况。程序中界说一个最长期t_max，假如MAINTAIN情况持续时刻超越t_max，则以为整个数据分发进程完毕，程序查看自己接纳到的数据是否齐备后退出。第二阶段的软件流程图如图4.7所示。

图4.7 接纳端软件第二阶段流程图

四 体系测验

本测验将用三个程序作为用例，以测验体系的可用性。三个程序别离为：

Led.bin完结简略的跑马灯；

GoAhead.bin 三辆小车将一向向前方走，即便碰到障碍物也不中止；

RandomWalk.bin 三辆小车将进行随机行走，而且碰到障碍物后会进行壁障，转弯。

首要咱们将批量更新跑马灯的程序，然后咱们来看GoAhead.bin，如图5.1所示。完好的程序镜像巨细为3340Bytes

图5.1 GoAhead.bin的巨细

当时在节点上现已运转了Led.bin,咱们将运用Led.bin和GoAhead.bin进行比较，生成patch.bin文件，即补丁文件。

图5.2生成的patch.bin文件

咱们看到，生成的patch.bin文件只是是原程序GoAhead.bin的1/3巨细！图5.3是patch.bin代表的指令（截取一部分）。

图5.3 patch.bin代表的指令

下面从GoAhead.bin 生成 RandomWalk.bin，RandomWalk.bin的巨细如图5.4所示：

图5.4 Randomalk.bin

图5.5从生成的patch.bin文件的巨细能够看到，其为RandomWalk的大约1/3。但有个值得留意的当地是，RandomWalk.bin比GoAhead.bin大了1000多个字节。添加的着1000多个字节是占patch.bin的首要内容。可见发送patch.bin比较适合于批改部分变量或许函数的时分。假如是单纯的添加功用，比较适合于发送完好的镜像文件。

图5.5 patch.bin文件

五 总结

测验结果表明，本规划完结了牢靠性无线批量嵌入式节点程序更新，烧录出错率低；更新功率高；不依赖操作体系，具有很好的可移植性，项目总体上完结了规划的方针。另一方面因为时刻约束，体系依然存在一些缺乏。以下是规划中几点需求优化的当地和相应的改善定见。

1. 体系在Linux环境下进行了开发和运用，没有开发Windows版别。项目组预备鄙人一阶段把体系移植到Windows渠道上。

2. 没有完结程序的动态更新，即每次更新前都要将正在运转的程序关掉，强制节点进入预备情况。能够分配一个专用线程用于程序更新，一起为了防止更新对正在运转的程序形成影响，需求在更新进程中引进动态链接技能