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

个优秀的可靠性数据分发协议，由加利福尼亚大学伯克利分校的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协议中可能无线传感器网络庞大，分布范围也较广，所以数据分发一旦启动，所有接收到数据的节点都参与到数据发送中来；而本设计中，网络充分利用了假设二中的节点分布条件，通常情况下，在第一轮发送结束后，相当大比例的节点就已经接收到了大部分的数据，而这个过程中因为只有数据基站在发送广播，网络中数据传输的效率是最高的。当然，这种节点分布条件不满足的情况也不会明显降低数据分发效率。

节点间交流阶段。

交流阶段参考了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_l<T_m,i<T_h。在每一个时间片i中，节点维护-个随机值r_i，r_i的值在T_m,i/2和T_m,i之间，r_i值的范围选取是为了解决短监听问题(short-listen problem)。

交流阶段中，节点拥有"维护"、"请求"和"发送"中的人一个状态。节点在"维护"状态广播广告并听取其他节点的广播；在请求