【作者】 唐斌；

【导师】 陆桑璐； 陈道蓄；

【作者基本信息】 南京大学 ， 计算机软件与理论， 2014， 博士

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

【Abstract】 Due to the broadcast nature of wireless medium as well as the multi-hop network topologies, there are a lot of redundant packets in wireless networks, which affect the network performance directly. In recent years, it has been shown that network coding can be used to enhance the performance of wireless networks by exploiting the redundant packets. However, network coding incurs extra computational cost, and its performance gain is usually limited by the broadcast rate of wireless channels as well as the computational capabilities of wireless nodes, and also affected by the mobility of wireless nodes. Therefore, network coding schemes should be designed and applied to meet the requirements of these characteristics of wireless networks.In this dissertation, we conduct a comprehensive study on the methods of efficient network coding in wireless networks considering the applications of network coding in multi-channel scenarios and for reliable data transmission and broadcast in wireless mobile networks. The contributions of this dissertation are summarized as follows:(1) We investigate the network coding methods subject to the broadcast rate constraint in OFDMA relay networks. Considering the tradeoff between performance and overhead, we propose two approaches, global approach (GA) and local approach (LA) for the support of coding-aware scheduling decision making. For the coding-aware multi-channel scheduling problem, we show it is NP-hard under both the GA model and the LA model. For the GA model, we also show that it does not admit any polynomial time approximation scheme (PTAS), and then propose a heuristic algorithm with low time complexity, while for the LA model, we present a PTAS and also introduce a practical greedy algorithm with an approximation ratio of1/2. Simulation results show that both proposed practical algorithms can achieve significant throughput improvement over a state-of-the-art noncoding scheme.(2) We investigate the methods for chunked random linear network codes (chunked codes) with a constant computational complexity for reliable data transmission in wireless mobile networks. We first highlight the importance of precoding for chunked codes to achieve non-vanishing rates, and then present a tight analysis on the achievable rates of non-overlapped chunked codes with precoding. We further introduce the first class of overlapped chunked codes with non-trivial performance guarantee, called expander chunked codes, which use expander graphs to form overlapped chunks, and then characterize their achievable rates using a tree-based analysis as well as some expander arguments. Numerical results reveal that expander chunked codes perform near-optimally, and achieve significantly higher rates than non-overlapped chunked codes. Also, simulation results show that for a finite number of input packets expander chunked codes incur much lower transmission overhead to recover the whole input packets than all other state-of-the-art chunked codes.(3) We investigate the methods of data broadcast with network coding in wireless mobile networks by proposing a novel random linear network coding based broadcast protocol name R2. In this protocol, the message to be broadcast is divided into multiple mini-messages, while the mini-messages are transmitted in a fashion of random linear network coding. The use of random linear network coding makes nodes easier to accumulate useful information and thus mitigates the bottleneck for completing the broadcast process due to the very late reception of the message by one or more nodes. Meanwhile, R2employs random scheduling, that is, each network node uses the wireless channel randomly and independently, which on one hand exploits the broadcast nature of wireless medium and on the other hand combats the interference due to concurrent transmissions efficiently. Theoretical analyses show that R2performs optimally in terms of broadcast latency in order sense, no matter how fast nodes move around the network. In contrast, the pure random scheduling strategy is insufficient to achieve the order-optimality when nodes move very fast.更多还原