学位论文 > 优秀研究生学位论文题录展示

无线网络中的机会网络编码技术研究

作　者: 周进怡
导　师: 夏树涛
学　校: 清华大学
专　业: 计算机科学与技术
关键词: 多跳无线网络机会网络编码最大多流调度算法吞吐性能优化
分类号: TN92
类　型: 博士论文
年　份: 2013年
下　载: 44次
引　用: 0次
阅　读: 论文下载

内容摘要

无线网络编码是网络编码技术研究的一个重要方向，而具有本地化特性的机会网络编码则是无线网络编码技术领域中一个简单实用的分支。针对无线机会网络编码吞吐性能优化的基础性问题，本文从理论框架、调度算法和应用改良三个层次系统性地展开了理论和应用研究，主要的研究内容和贡献包括：1通过研究无线网络编码的最大多流问题，提出了一套理论框架，解决了在任意机会网络编码设置下的任意无线网络拓扑中，计算任意多个单播流所能达到的最大吞吐的难题。在这个理论框架中，针对确定无线机会网络编码容量区域的NP难问题，提出了一种贪婪启发式算法，能够高效地确定无线机会网络编码的一个近似容量区域。此外，针对在无线机会网络编码中寻求最优调度的NP难问题，提出了一种多项式复杂度的调度算法，并且论证了该算法具有常数近似界保障。实验结果和数学分析表明，基于本文所提出的理论框架，上述两种算法都具有很好的性能，所取得的最大吞吐数值结果能够逼近最优值。2通过研究物理干扰模型下无线网络编码的调度问题，提出了一个有常数界保障的近似算法。与传统物理干扰模型下的单播/多播调度不同，无线网络编码的调度可能会对多个接收节点产生不同的干扰要求，因此本文首先针对不同的无线网络编码场景提出了不同的调度优化问题。其中，针对适用于无线机会网络编码调度的MIMS优化问题，提出了一个近似调度算法，并且通过严格的数学证明论证了这个算法具有常数近似界保障。本文初步探索了在真实的物理干扰模型下支持网络编码的调度问题，为后续的研究提供了参考。3通过研究无线机会网络编码系统的译码缓存问题，提出了一套实用的译码缓存管理机制。在实际的无线机会网络编码系统中，有限的译码缓存条件可能引起编码机会流失而降低网络编码的吞吐增益。本文基于译码分组的流量特性，提出了一种由译码缓存过滤功能和分组信息分发功能组成的译码缓存管理机制DBM。仿真结果表明，DBM能够极大的提高译码缓存利用率、降低带宽开销，并且在译码缓存受限的情况下，比传统的COPE方法拥有更多的编码机会，确保网络编码的吞吐增益真正可达。

全文目录

摘要  3-4
Abstract  4-9
第1章引言  9-16
  1.1 研究背景  9-11
  1.2 本文的研究内容  11-13
  1.3 本文的主要贡献  13-14
  1.4 本文的章节组织  14-16
第2章相关研究综述  16-35
  2.1 本章引言  16
  2.2 网络编码基本原理  16-19
  2.3 网络编码与线性网络编码  19-24
    2.3.1 网络编码的数学描述  19-20
    2.3.2 线性网络编码的数学描述  20-24
  2.4 无线网络编码  24-27
    2.4.1 无线网络编码的基本原理  24-26
    2.4.2 无线网络编码的研究与发展  26-27
  2.5 机会网络编码  27-34
    2.5.1 COPE机会网络编码  27-30
    2.5.2 机会网络编码的研究与发展  30-31
    2.5.3 机会网络编码的关键问题  31-34
  2.6 本章小结  34-35
第3章无线机会网络编码的最大多流问题  35-65
  3.1 本章引言  35-38
  3.2 数学模型  38-42
    3.2.1 假设和定义  38
    3.2.2 协议干扰模型  38
    3.2.3 无线网络的模型  38-39
    3.2.4 无线网络的容量区域  39-40
    3.2.5 无线网络的最大多流  40-42
  3.3 机会网络编码条件下的最大多流  42-49
    3.3.1 机会网络编码条件  42
    3.3.2 机会网络编码条件下的稀疏链路冲突图  42-44
    3.3.3 机会网络编码条件下的网络模型  44-45
    3.3.4 机会网络编码条件下的容量区域  45-47
    3.3.5 机会网络编码条件下的最大多流  47-49
  3.4 机会网络编码条件下的容量区域分析  49-53
    3.4.1 评估链路的使用率水平  50-51
    3.4.2 确定一个超边集  51
    3.4.3 搜集独立集  51-53
  3.5 机会网络编码条件下的近似调度算法  53-56
  3.6 性能分析  56-62
    3.6.1 试验环境  56-58
    3.6.2 最大化机会编码机制  58-61
    3.6.3 COPE机会编码机制  61-62
  3.7 相关讨论  62-64
  3.8 本章小结  64-65
第4章物理干扰模型下的网络编码调度算法  65-84
  4.1 本章引言  65-68
  4.2 数学模型  68-71
    4.2.1 功率分配问题  68-69
    4.2.2 无网络编码的单播发射  69-70
    4.2.3 网络编码条件下的多播发射  70-71
  4.3 物理干扰模型下的容量区域  71-73
  4.4 物理干扰模型下的近似算法  73-81
    4.4.1 算法的描述  73-74
    4.4.2 算法的正确性  74-77
    4.4.3 算法的近似界  77-81
  4.5 相关讨论  81-83
  4.6 本章小结  83-84
第5章无线机会网络编码系统的译码缓存管理  84-97
  5.1 本章引言  84-85
  5.2 译码缓冲  85-87
  5.3 译码缓存过滤功能  87-90
    5.3.1 无效的译码分组  87-88
    5.3.2 过滤无效的译码分组  88-90
  5.4 分组信息分发功能  90-92
  5.5 性能评价  92-96
  5.6 本章小结  96-97
第6章总结与展望  97-102
  6.1 研究工作总结  97-98
  6.2 研究展望  98-102
参考文献  102-108
致谢  108-110
个人简历、在学期间发表的学术论文与研究成果  110-111

无线网络中的机会网络编码技术研究

内容摘要

全文目录

相似论文