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