基于编码机会路由的高效无线Mesh网络传输技术

摘要

作为一种低成本、高覆盖范围且方便部署的Internet接入方案，无线Mesh网络通常需要承载大量高吞吐率、高可靠的应用业务。但无线传输的易错性、信道质量的时变性，以及Mesh网络的多跳转发架构，均导致该网络容易遭受吞吐有限、可靠性低下等问题。
　　机会路由和网络编码是解决这一问题的有力工具。机会路由利用无线广播所带来的多用户分集优势，每个旁听到报文的节点都有机会承担转发任务，从而提高一次传输的成功概率。网络编码则容许网络中间节点对接收到的报文进行混合编码，以便有效地利用公共链路，提高系统吞吐。而且，若随机选取编码系数（即随机网络编码），还能获得无比率纠删码的良好特性。结合二者优势，编码机会路由(Network Coding-based OpportunisticRouting，简称NCOR)应运而生，成为一种在链路有损的无线Mesh网络中提供高吞吐率、可靠传输的有效方案。本论文旨在研究NCOR的关键设计因素，并围绕其“机会传输”和“网络编码”特性，提出新的算法和协议，为无线Mesh网络提供高效、公平的高吞吐率可靠传输服务。研究内容和成果包括以下三个层次。
　　1.在网络层，研究了最小成本NCOR路由构建问题。与传统路由不同，给定源目节点，NCOR不用预先指定明确的转发路径，只需要选择哪些节点参与机会转发。参与节点通过广播链路连接形成网状传输路径，每个节点独立地执行随机网络编码并将编码报文广播到下游节点，因而节点之间的转发任务分配也会直接影响传输效率。因此，如何选择候选转发节点集合(Candidate Forwarder Set，简称CFS)，以及如何在这些节点之间分配转发任务，是实际部署NCOR时所要面临的基本问题。现有工作通常独立地处理这两个问题，难以保证整体最优性。本论文扩展传统的最优路由概念，将这两个问题融合在一个最小成本框架(MIC-NCOR)中，联合求解最佳的CFS和转发任务分配。在MIC-NCOR的最优子结构的基础上，根据动态规划思想，推导出能够完全分布式实现的MIC-NCOR算法，并给予严格的正确性证明。仿真结果表明，论文提出的成本模型能更准确反映NCOR路径的实际传输成本，且MIC-NCOR算法相比现有的启发式方法有显著的性能增益。
　　2.在MAC层，研究了机会广播信道接入问题。NCOR的网状路径由广播链路拼接而成，因此广播MAC的表现对于发挥多用户分集优势、进而提高NCOR的整体性能有重要影响。而NCOR的编码机会转发特性也为广播MAC的设计带来了更多的灵活性:首先，在机会转发机制下，不需要等待所有广播邻居进入就绪（准备好接收）状态。越多的邻居就绪，广播信道的多用户分集优势就越显著（机会转发的交付概率越高），但同时引入的接入延迟也会更大，因此，需要在接入延迟和广播信道的交付能力之间做出权衡。其次，随机网络编码的纠删能力也免除了对MAC的可靠性要求。据此，我们提出以最大化平均有效速率为目标的机会广播信道接入问题，并使用最优停止理论推导出具有简单阈值形式的信道接入策略N*。在此基础上，通过简单扩展IEEE802.11 DCF，设计出执行N*策略的机会广播信道接入控制协议O-BCast。仿真结果表明，O-BCast能够显著提高NCOR的端到端吞吐率，而且具有网络负载自适应的良好特性。
　　3.在传输层，研究了NCOR的拥塞控制问题。无线Mesh网络由多用户共享，需要承载大量突发性的高吞吐率业务，需要拥塞控制机制来保证NCOR高效、公平的运作。NCOR的传输路径呈网状，在高负载、高丢包率的无线Mesh网络中，如果仍然依赖聚合层次的端到端拥塞控制方法(如TCP)，容易造成网络资源利用不充分和拥塞响应滞后等问题。因此，论文基于逐跳控制思想，设计了全新的NCOR拥塞控制协议HCC。HCC精确衡量节点的拥塞程度，并以公平性为原则计算各个业务流的拥塞反馈。当接收到来自网状路径上多个下游邻居的差异化拥塞反馈时，采用折中策略进行速率调整:若所有拥塞反馈均指示要求增速或降速，节点按照所有反馈的均值调整报文发送速率;若部分反馈要求降速、部分要求增速，节点维持发送速率不变而由下游邻居调整各自的接收速率。这种策略既能够有效减轻拥塞节点的负载，又能充分利用网状路径中轻载节点的转发能力以发挥NCOR的机会传输优势。仿真实验显示，在高负载高丢包率的无线Mesh网络中，HCC相比端到端方法在吞吐、传输成本、延时以及公平性等方面具有显著的性能优势。
　　基于上述三方面的建模优化和协议设计工作，论文最后设计了一个完整的NCOR系统。仿真实验表明，在三者共同作用下，该NCOR系统的性能相比独自作用时得到进一步提升。本工作对于理解和应用NCOR这种新型的传输机制，具有重要的理论意义和实际应用价值。

目录

声明

摘要

插图目录

表格目录

第1章 绪论

1．1 课题背景

1．2 论文主要研究内容和目标

1．3 论文特色与贡献

1．4 论文组织结构

第2章 编码机会路由综述

2．1 机会路由介绍

2．1．1 机会路由的概念和优势

2．1．2 机会路由设计的挑战和局限性

2．2 网络编码介绍

2．1 网络编码的概念与性能优势

2．2．2 网络编码方法分类

2．2．3 实用的随机网络编码方法

2．2．4 无线网络中的网络编码应用

2．3 编码机会路由(NCOR)

2．3．1 网络模型

2．3．2 NCOR的基本过程

2．3．3 NCOR的关键设计因素和相关工作

2．3．4 NCOR相关研究的局限性和论文研究动机

2．4 本章小节

第3章 最小成本编码机会路由计算

3．1 引言

3．2 相关工作

3．3 问题描述

3．3．1 NCOR路径及其成本

3．3．2 NCOR路径成本的分解

3．3．3 最小成本NCOR问题的形式化

3．4 寻找最小成本NCOR路径

3．4．1 最小成本NCOR问题的最优子结构和无环条件

3．4．2 最小成本NCOR算法

3．5 仿真实验

3．5．1 实验设置

3．5．2 仿真结果

3．6 本章小节

第4章 机会广播信道接入

4．1 引言

4．2 系统模型与问题提出

4．2．1 系统模型

4．2．2 平均有效速率最优的机会广播信道接入问题

4．3 基于最优停止理论的机会广播信道接入策略

4．4 数值结果

4．5 O-BCast协议设计

4．5．1 O-BCast控制帧格式

4．5．2 状态探测机制

4．5．3 超边的性能统计与N*阈值计算

4．5．4 机会广播信道接入控制

4．6 仿真试验与讨论

4．6．1 实验环境与参数设置

4．6．2 结果和讨论

4．7 本章小结

第5章 编码机会路由的逐跳拥塞控制

5．1 引言

5．2 相关工作

5．2．1 NCOR的拥塞控制

5．2．2 无线网络中的逐跳拥塞控制

5．3 系统模型与拥塞控制挑战

5．3．1 系统模型

5．3．2 NCOR拥塞控制的挑战

5．4 HCC协议设计

5．4．1 HCC概述

5．4．2 HCC拥塞控制规则

5．4．3 HCC参数设置讨论

5．5 HCC协议实现

5．5．1 速率测量

5．5．2 HCC拥塞控制过程

5．6 性能评价

5．6．1 实验设置

5．6．2 实验结果

5．8 本章小节

第6章 综合性能评价

6．1 引言

6．2 NCOR系统设计与实现

6．2．1 NCOR系统的总体设计

6．2．2 实现细节

6．3 综合实验与性能评价

6．3．1 实验设置

6．3．2 实验结果与讨论

6．4 本章小结

第7章 总结与展望

7．1 本文的主要工作和结论

7．2 进一步的研究工作

参考文献

致谢

攻读博士期间论文发表情况

攻读博士期间曾参与的相关科研项目