论文部分内容阅读
在无线网络中,无线传输的广播特性以及网络拓扑的多跳性,使得无线网络中存在大量冗余报文,直接影响着无线网络的传输性能。近年来的研究表明,网络编码技术能够通过有效利用无线网络中的冗余报文,提升网络性能。然而,网络编码增加了额外计算开销,其性能增益通常受限于无线信道广播速率及无线节点的计算能力,同时还会受到无线节点移动性的影响。如何面向这些无线网络的关键特征,设计合理高效的网络编码方法是无线网络性能优化中的重要问题。针对上述问题,本文从适应无线信道广播速率限制的角度研究了多信道环境中网络编码方法,并从适应无线节点计算能力与移动性的角度分别对面向数据传送及面向数据广播的网络编码方法开展了研究。论文主要贡献包括以下三个方面:(1)针对多信道无线网络吞吐率性能优化,以OFDMA中继网络为应用背景,对适应无线信道广播速率的网络编码方法进行了探讨。首先以优化性能与负载为切入点,提出了用于支持编码感知的信道调度策略的全局方法和局部方法。进一步地,针对全局方法下的网络编码感知的信道调度问题,证明了该问题是NP难的且不存在多项式时间近似方案(polynomial time approximation scheme),并提出了一种具有低时间复杂度的启发式算法。针对局部方法下的网络编码感知的信道调度问题,证明了该问题是NP难的,并提出了一种多项式时间近似方案及一种具有1/2近似率的贪婪算法。仿真实验结果表明所提算法相比于无网络编码的机制,能够极大地提高网络吞吐率。(2)针对无线移动网络中数据传送性能优化,对具有常数复杂度的分块随机线性网络编码(简称分块码)方法进行了研究。首先证明了预编码(precoding)在分块码达到正码率中的不可或缺性。在预编码的前提下,对无重叠分块码的可达码率进行了紧(tight)的分析,并进一步地提出了采用扩展图(expander graph)生成重叠报文块的扩展分块码。通过基于树的分析以及扩展论证刻画了扩展分块码的可达码率,从而明确了扩展分块码是第一类具有非平凡性能保证的重叠分块码。数值分析结果显示扩展分块码性能接近最优,其可达码率极大地超出了无重叠分块码。此外,仿真实验结果表明,当输入报文个数有限时,扩展分块码相比于其他重叠分块码具有低得多的传输负载和解码错误概率。(3)针对无线移动网络中数据广播性能优化,提出了一种新颖的基于随机线性网络编码的广播协议。该协议将需要广播的消息分割成多个子消息,并将子消息以随机线性网络编码的方式进行传输。随机线性网络编码的应用使得无线节点易于收集有效信息,从而减轻了因一个或多个节点过晚接收到消息所致的时延瓶颈。与此同时,节点传输采用了随机调度机制,即每一个网络节点随机独立地使用无线信道。随机调度的使用能够在利用无线媒介广播特性的同时,有效应对并发传输所致的冲突问题。理论分析表明,该协议在任意的节点移动速度下,均能够达到渐进最优的广播时延。相反地,纯粹的随机调度策略在节点快速移动时不足以达到最优性。