面向无线网络的高效网络编码方法研究

发布时间：2018-07-10 16:27

本文选题：确定网络编码 + 随机线性网络编码　；参考：《南京大学》2014年博士论文

【摘要】：在无线网络中,无线传输的广播特性以及网络拓扑的多跳性,使得无线网络中存在大量冗余报文,直接影响着无线网络的传输性能。近年来的研究表明,网络编码技术能够通过有效利用无线网络中的冗余报文,提升网络性能。然而,网络编码增加了额外计算开销,其性能增益通常受限于无线信道广播速率及无线节点的计算能力,同时还会受到无线节点移动性的影响。如何面向这些无线网络的关键特征,设计合理高效的网络编码方法是无线网络性能优化中的重要问题。针对上述问题,本文从适应无线信道广播速率限制的角度研究了多信道环境中网络编码方法,并从适应无线节点计算能力与移动性的角度分别对面向数据传送及面向数据广播的网络编码方法开展了研究。论文主要贡献包括以下三个方面： (1)针对多信道无线网络吞吐率性能优化,以OFDMA中继网络为应用背景,对适应无线信道广播速率的网络编码方法进行了探讨。首先以优化性能与负载为切入点,提出了用于支持编码感知的信道调度策略的全局方法和局部方法。进一步地,针对全局方法下的网络编码感知的信道调度问题,证明了该问题是NP难的且不存在多项式时间近似方案(polynomial time approximation scheme),并提出了一种具有低时间复杂度的启发式算法。针对局部方法下的网络编码感知的信道调度问题,证明了该问题是NP难的,并提出了一种多项式时间近似方案及一种具有1／2近似率的贪婪算法。仿真实验结果表明所提算法相比于无网络编码的机制,能够极大地提高网络吞吐率。 (2)针对无线移动网络中数据传送性能优化,对具有常数复杂度的分块随机线性网络编码(简称分块码)方法进行了研究。首先证明了预编码(precoding)在分块码达到正码率中的不可或缺性。在预编码的前提下,对无重叠分块码的可达码率进行了紧(tight)的分析,并进一步地提出了采用扩展图(expander graph)生成重叠报文块的扩展分块码。通过基于树的分析以及扩展论证刻画了扩展分块码的可达码率,从而明确了扩展分块码是第一类具有非平凡性能保证的重叠分块码。数值分析结果显示扩展分块码性能接近最优,其可达码率极大地超出了无重叠分块码。此外,仿真实验结果表明,当输入报文个数有限时,扩展分块码相比于其他重叠分块码具有低得多的传输负载和解码错误概率。 (3)针对无线移动网络中数据广播性能优化,提出了一种新颖的基于随机线性网络编码的广播协议。该协议将需要广播的消息分割成多个子消息,并将子消息以随机线性网络编码的方式进行传输。随机线性网络编码的应用使得无线节点易于收集有效信息,从而减轻了因一个或多个节点过晚接收到消息所致的时延瓶颈。与此同时,节点传输采用了随机调度机制,即每一个网络节点随机独立地使用无线信道。随机调度的使用能够在利用无线媒介广播特性的同时,有效应对并发传输所致的冲突问题。理论分析表明,该协议在任意的节点移动速度下,均能够达到渐进最优的广播时延。相反地,纯粹的随机调度策略在节点快速移动时不足以达到最优性。
[Abstract]:In wireless networks, the broadcast characteristics of wireless transmission and the multiple hops of the network topology make a large number of redundant packets in the wireless network, which directly affect the transmission performance of the wireless network. In recent years, the research shows that the network coding technology can effectively use redundant packets in the wireless network to improve the network performance. However, the network coding is made up. The code increases the extra computing overhead, and its performance gain is usually limited to the radio channel broadcasting rate and the computing power of the wireless nodes, but it will also be affected by the mobility of wireless nodes. How to design a reasonable and efficient network coding method is an important problem in the performance optimization of wireless networks for the key features of these wireless networks.
In view of the above problems, this paper studies the network coding method in the multi channel environment from the angle of radio channel broadcast rate restriction, and studies the network coding method for data transmission and data broadcasting from the angle of wireless node computing power and mobility. The main contributions of this paper include the following three Aspect:
(1) aiming at the performance optimization of multi channel wireless network throughput, the network coding method adapted to the radio channel broadcasting rate is discussed with the OFDMA relay network as the application background. First, the global method and local method for the channel scheduling strategy used to support the coding awareness are proposed. It is proved that the problem is NP difficult and no polynomial time approximation (polynomial time approximation scheme), and a heuristic algorithm with low time complexity is proposed to solve the problem of network coding aware channel scheduling under global method. It is clear that the problem is NP difficult, and a polynomial time approximation scheme and a greedy algorithm with 1 / 2 approximation are proposed. The simulation results show that the proposed algorithm can greatly improve the network throughput compared to the non network coding mechanism.
(2) aiming at the optimization of data transmission performance in wireless mobile network, the method of block random linear network coding (block code) with constant complexity is studied. First, it is proved that the precoding (precoding) is indispensable to the positive rate of block code. Under precoding, the reachable code rate for non overlapping block codes is achieved. The analysis of tight is carried out, and an extended block code that uses an extended graph (expander graph) to generate overlapping packet blocks is further proposed. By tree based analysis and extension argument, the reachable code rate of extended block codes is depicted. Thus, the extended block code is the first class of overlapping block codes with non trivial performance guarantee. The analysis results show that the performance of the extended block code is close to the optimal, and the reachable code rate is greatly beyond the non overlapping block code. In addition, the simulation results show that when the number of input messages is limited, the extended block code has a much lower transmission load and decoding error probability compared to the other overlapped block codes.
(3) in order to optimize the performance of data broadcasting in wireless mobile networks, a novel broadcast protocol based on random linear network coding is proposed. This protocol divides the messages needed to be divided into multiple sub messages and transmits submessages in a random linear network. The application of random linear network coding makes wireless nodes It is easy to collect effective information, thus reducing the delay bottleneck caused by the late reception of one or more nodes. At the same time, the node transmission adopts a random scheduling mechanism, that is, each network node uses the wireless channel randomly and independently. The use of random scheduling can have effect while using the radio characteristics of the wireless media. The theoretical analysis shows that the protocol can achieve progressive optimal broadcast delay under the moving speed of any node. On the contrary, the pure random scheduling strategy is not sufficient to achieve optimality when the node moves quickly.
【学位授予单位】：南京大学
【学位级别】：博士
【学位授予年份】：2014
【分类号】：TN92

【共引文献】