基于网络编码和链路相关性的多包洪泛协议
第 1 章 绪论
1.1 研究背景和意义
1.1.1 无线传感器网络概述
无线传感器网络是由部署在观测环境中的传感器节点通过无线通信技术实现的一种多跳自组织的网络系统，能够实时有效地获知网络监控区域内的各种环境对象信息，同时对其进行处理，从而获得详尽而准确的信息。无线传感器网络技术被认为是信息感知和采集的一场革命，作为信息世界和室内世界的新兴媒介，正在逐渐改变人类与自然界的交互方式，在环保、民生和军事等各个领域都具有重大的应用价值。
典型无线传感器网络体系结构包括传感器节点、汇聚节点(Sin节点)、互联网、基础网络（Inter或卫星）以及用户交互的管理节点。在无线传感器网络中，传感器节点首先通过人工或借助飞机等方式部署，接着对采集到的信息进行传输或处理，最后再传送到汇聚节点。当管理节点和网络节点的距离较远时，可通过卫星，互联网或移动通信网等途径汇聚到网络服务器。图1.1所示为无线传感器网络的体系结构图。这样就实现了物理世界的信息采集和处理，同时用户还可以通过浏览器、手机等方式来对传感器网络进行配置和管理。
1.2 研究动机和主要工作
近年来，无线传感器网络得到广泛的应用，包括目标追踪，基础设施的保护[12]和科学探索。在无线传感器网络的应用中，洪泛协议担当重要的角色，它支持多种高层的协议和应用。但是，现有的洪泛协议大多只关注单包问题的解决，多包洪泛问题只是被当作多个独立的单包问题，并没有充分利用数据包之间存在的内在联系，阻碍了性能的提高。
无线传感器网络中的多包洪泛算法需考虑三个主要问题：（1）无线网络的广播特性；（2）数据包之间的联系；（3）链路相关性的存在。
本文在无线网络广播传输的基础上，提出结合网络编码和链路相关性的多包洪泛算法(OppCode)。网络编码作为解决多包洪泛问题的有效手段，允许中继节点对接收到的多个数据包先编码再转发，这种方式充分利用数据包之间的联系，实现多包之间的协作，从而提高传输的有效性。同时，链路相关性作为另一种有效的手段，有利于减少洪泛产生的冗余 ACs，从而减少网络的总传输次数。而无线网络广播传输的本质，为网络编码和链路相关性的实现提供基础。
本文深入研究网络编码和链路相关性的实现机制。文献中，基于无线网络的广播特性，网络编码已应用于无线网络，通过中继节点的信息融合增大网络吞吐率，提高了算法的性能。文献[首次提出机会编码的概念，利用简易的异或编码实现性能的极大提高，但是并没有给出实现的具体方案。而链路相关性现象也已在文献中进行研究和验证，主要提出针对单包问题的解决方案，利用链路相关性实现多包问题面临挑战和难点。
第 2 章 基于网络编码的多包洪泛算法
2.1 网络编码研究
2.1.1 网络编码概述
网络编码是一种有效的信息技术，在通信等领域具有巨大的应用价值。它的核心思想是中继节点收到多个信道的信息后先对其进行线性或非线性处理，然后再转发给其它节点。传统的网络通信采用存储转发的方式，即中继通信节点只负责路由，而不对接收的数据包做处理。在这种方式中，中继节点通过输入流接收数据包并存贮在本地，同时数据包的拷贝通过输出流转发到下跳节点。当该中继节点的有多个目标节点时，节点发送数据包的拷贝给每个输出流。而在节点的转发过程中，中继节点不允许处理数据。然而，网络编码的提出彻底颠覆了这种传统的观点。网络编码理论最早由 R Ahlswede 等人提出，它允许中继节点融合多个数据流来达到传输最大流，从本质上推翻了传统的网络通信方式。网络编码的提出引起广泛的关注，成为业界研究的热点。
网路编码作为一种新兴的通信传输技术，在提高网络吞吐量、减少网络时延，降低网络能耗及增强网络健壮性方面都表现出极大的优势。网络编码的主要表现方式是通过增加单次传输的数据量来增加传输效率，其显著的优势也已被应用到文件存储，网络安全，Ad Hoc网络，无线传感器网络等领域。特别地，随着无线通信技术的发展，无线通信的方式被越来越多的人接受，但同时对传输质量和效率的要求也逐渐提高。如何提高无线通信的传输质量，保障信息传输的可靠性，以及提高资源利用率已成为无线通信领域研究的热点。另外，由于无线传输的广播特性和允许网络节点处理信息的方式，使得网络编码成为解决网络通信的重要手段。目前，网络编码已成功应用于网络传输技术，成为提高网络传输性能的有效手段，其在网络通信的重要作用也受到学术界的认可。
2.2 机会编码研究
2.2.1 机会编码概述
机会网络编码在文献中被明确提出，成为一种实用的无线网络编码机制，为网络编码的实际应用提供了基础。
机会编码利用无线网络的广播特性，监听所有邻居节点的广播，当节点侦听到编码机会时进行网络编码，并在接收节点处进行相应地解码操作。文献提出机会编码的 COPE 体系，将简易的网络编码应用于 MESH 网络，实现了网络吞吐性能的提高。继COPE 之后出现了大量的对机会编码的研究，从机会网络编码的研究中可以总结出机会编码的两个基本特性：
机会性：节点对于邻居节点的监听和编码都是机会的，只有监听到编码机会时才进行编码和转发。
本地化：邻居节点之间传输的数据包被称为本地包。而本地化指的是节点之间的监听，编码和译码都是发生在相邻节点之间的，这称为单跳机会网络编码。多跳机会网络编码是发生在直接邻居之外，即不相邻的多跳节点之间，这种方式相对复杂但是也增加了网络的编码机会。
第 3章 利用链路相关性的多包洪泛算法.................... 20
3.1 链路相关性研究 ............................. 20
3.1.1 链路相关性概述 ................ 20
第 4章 基于网路编码和链路相关性的多包洪泛算法.............. 30
4.1 算法概述 ..................... 30
4.2 算法设计 .................... 31
第 5章 OppCode算法的实现和评估 .................. 38
5.1 OppCode 仿真实现............... 38
第 5 章 OppCode算法的实现和评估
5.1 OppCode 仿真实现
5.1.1 环境设置及衡量指标
OppCode 算法的仿真实现是基于 OMNeT4.1 平台完成的。OMNET 是一款开源的多协议离散事件仿真工具，在无线传感器网络中有着重要的地位。它可应用于无线通信网络的建模，同时具有完善的图形化界面接口。
仿真中，1000×1000 平方米的空间里随机布置了 250个传感器节点，节点之间的通信范围是 155 米。网络初始化阶段的时间设置为 20 秒，其间节点只广播消息包，用于邻居信息的维护。
为了验证 OppCode算法的有效性，与如下几种洪泛算法进行了分析和比较：
CF方案：提出集体 ACs 机制来改进洪泛算法。
OppCode-R: 它的工作方式和 OppCode 类似，唯一的不同是 OppCode-R 随机地从所有的编码可能中选择编码包。
Oracle：它的工作方式也和 OppCode 类似，但 Oracle 中每个节点都确切地知道其邻居节点包含的数据包，则 Oracle中不需要返回 ACs确认信息。 实验中衡量算法性能的指标如下：
（1） 可靠性：可靠性通过网络中已覆盖节点所占的百分比来衡量。
（2） 传输负载：传输负载指节点总传输次数，不包含初始化阶段的消息包传输。
（3） 网络时延：网络时延指从源节点开始洪泛到洪泛结束的时间间隔。
（4） 负载均衡：负载均衡用节点传输次数的平均差来表示，用来衡量节点广播次数分布的均衡性。
第 6 章 总结和展望
6.1 总结
本文对无线传感器网络中的洪泛问题进行了深入的研究和总结，由于无线传感器网络中能量受限，改进和优化洪泛算法是传感器领域研究的热点。但是现有的主要工作都集中在单包问题的研究，多包洪泛算法方面的研究较少。
本文查阅大量的文献，发现多包洪泛广泛应用在空中编程等项目中，但缺少有效的多包洪泛算法。多包洪泛时，现有的方式只把它当成多个单包洪泛问题，存在性能的降低。为利用包和包之间的内在联系，增加单次传输的网络吞吐率，将网络编码应用于多包洪泛算法。网络编码允许中继节点收到广播包后先对其进行编码再转发，这种方式有效地提高了传输吞吐率。另外，无线传感器网络的链路之间存在一定的相关性，这已在大量的研究中得到验证和应用。链路相关性现象的有效利用可以减少网络中存在的冗余 ACs，继而进一步降低能耗。
为实现多包洪泛算法，本文对网络编码进行了广泛而深入地研究，提出基于聚合编码增益的机会编码决策，采用机会监听、机会编码的方式实现贪婪式的洪泛算法。另外，对链路相关性现象也进行了研究，提出集体 ACs机制的实现。
结合机会编码和集体 ACs 机制，本文提出了基于网络编码和链路相关性的多包洪泛算法（OppCode）。在本文的第四章详细描述了 OppCode 的主要设计和实现方案，并且通过大量的实验验证了算法的有效性。本文分别在 OMNET4.1仿真环境和TinyOs系统上实现该方案，实验结果表明 OppCode在可靠性、网络传输负载、时延和网络负载性方面表现出巨大的性能优势。
参考文献（略）