【作者】 周进怡；

【导师】 夏树涛；

【作者基本信息】 清华大学 ， 计算机科学与技术， 2013， 博士

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

【Abstract】 Wireless network coding is an important part of the network coding technology,and the localized opportunistic network coding is one of the most simple and practicalbranches of the wireless network coding. To address the basic problem of the through-put performance of the wireless opportunistic network coding, this thesis focuses on thethroughput performance optimization, and systematically conducts theory and applica-tion research from the following three levels: theory framework, scheduling algorithmand system improvement. The main research contents and contributions of this thesis areas follows:Firstly, by studying the classical problem of maximum multi-commodity flow, wepropose a theory framework for computing the maximum throughput of any given multi-ple unicast flows supported by a multihop wireless network with any given opportunisticnetwork coding setting. In this framework, we show that determining the capacity regionof a multihop wireless network with opportunistic network coding is an NP-hard prob-lem, and thus develop a greedy heuristic algorithm to determine a capacity subregion.We also show that finding an optimal schedule in a multihop wireless network with op-portunistic network coding is NP-hard, and thus develop a polynomial algorithm to findan approximate schedule with constant approximation bound. A numerical analysis ispresented to demonstrate the efciencies of the algorithms based on the framework.Secondly, we focus on the network coding schedule under the real physical inter-ference model, and develop a scheduling algorithm with constant approximation bound.Since that it is the first time to investigate the network coding schedule under the physi-cal interference model, we define several scheduling optimization problems for diferentwireless network coding scenarios. The MIMS problem, as one of these scheduling opti-mization problems, applies to the opportunistic network coding scenario. We then devel-op a polynomial algorithm with constant approximation bound for the MIMS problem.This thesis initially explores the research field of network coding schedule under the realphysical interference model, providing a reference for subsequent research.Finally, we investigate the problem of decoding bufer in opportunistic network cod-ing systems, and introduce a mechanism for decoding bufer management. In a practicalopportunistic network coding system, limited decoding bufer may result in the loss of coding opportunities, as well as the reduction of the throughput gain brought by net-work coding. Based on the flow characteristics of those decoding packets, we introducea mechanism called decoding bufer management (DBM) in practical opportunistic net-work coding systems, which consisting of the decoding bufer filtering function and thepacket information distributing function. The simulation results show that, DBM cangreatly improve the utilization level of decoding bufer while reducing the bandwidthoverhead, and provide more coding opportunities than the traditional COPE method whendecoding bufer is limited.更多还原