【作者】 田贤忠；

【导师】 朱艺华；

【作者基本信息】 浙江工业大学 ， 控制理论与控制工程， 2013， 博士

【摘要】 当今社会,无线网络已经深入到日常生活的每个角落,它影响并改变了人们的生活方式。为了把数据从一个节点传输到另一个节点,无线网络需要路由协议。路由协议的主要功能是,在网络中寻找和维护数据传递的路径,它对无线网络的信息分发与共享是举足轻重的。网络编码是本世纪初出现的一项新的信息技术,能极大地提高网络的吞吐量和可靠性。它改变了传统路由协议中节点的“接收——转发”这一特点,使节点既有“接收——转发”功能,同时还具有编码功能,即让节点把来自不同流的多个数据包编码成一个编码包,然后再发送出去,这样,可以减少数据包的发送次数,提高带宽的利用率,增大网络的吞吐量。网络编码的这一特点以及无线网络信道的广播特性,启发研究人员将网络编码应用于无线网络的路由协议中,以提高路由协议的吞吐量,降低时延。把网络编码应用于无线网络,其工作机制与传统的无线网络路由机制有明显的不同,主要表现在：除了需要考虑传统的路由协议涉及的数据包传输速率、时延、吞吐量、丢包率等因素之外,还要考虑最佳网络编码方案因素。本文利用无线链路的广播特性研究基于网络编码的无线网络路由算法。研究不同于传统无线路由的网络编码感知路由机制及其关键问题；重点研究无线链路不可靠性,以及无线网络节点的能量、带宽等的受限性等因素对网络编码的影响；并给出理论层面和应用层面的解决方案。本文的主要工作和成果如下：1)研究了基于网络编码的低时延路由问题。针对网络编码可以提高网络吞吐率从而降低数据传输时延的特点,提出了一种编码感知增益的低时延路由协议——CGAR (Coding Gain Aware Routing)。CGAR的要点是,让节点把要传输的数据包分成两部分,其中一部分使用剩余的空闲信道传输,而将另一部分与来自一些流的已有数据包进行网络编码而被捎带走,共享经过该节点的其它数据流所占据的信道,从而提高带宽的使用率,增大吞吐量,降低数据传输时延。文中引入编码图,把流的编码问题转化成图中找最小完全子图的问题,并证明了编码图中多条流可以编码的条件,给出了简化编码图的方法。针对多条不同速率的数据流不能直接编码的问题,研究用分流的方法进行编码,并给出了编码增益的贪婪算法用于计算网络编码的增益。CGAR以传输一个数据包的时延为路由选择度量,它充分考虑编码机会和剩余空闲信道以及数据丢包率对网络时延的影响。仿真实验证明,CGAR比DCAR和COPE等国际著名的基于网络编码的路由算法具有更低的传输时延。2)研究了基于网络编码的节能路由问题。在无线网络中,虽然降低发射功率可以减小数据传输的能耗,但会导致链路可靠性降低,增加链路的误码率和丢包率,从而增加数据包的重发次数,这会消耗更多的能量。针对这个问题,本文提出一种基于网络编码与功率控制的节能路由算法——NCPCR (Network Coding and Power Control based Routing)。考虑到节点的发射功率和数据包的发送次数是节点能耗的主要因素,NCPCR通过功率控制与网络编码来降低发射功率与减小发送次数,并权衡两者以最大限度地降低传输能耗。NCPCR还考虑了解码节点因侦听数据包失败对解码成功率造成的影响,计算出解码节点成功侦听到发送节点发送的数据包的条件概率,并在此基础上提出编码节点的节能编码条件。仿真实验表明NCPCR比DCAR和COPE具有更低的能耗。3)研究了基于流内与流间网络编码的高吞吐量可靠路由问题。针对流间网络编码能提高网络吞吐量,以及流内网络编码能提高网络可靠性的特点,本文提出了一种基于流内与流间网络编码的无线路由算法——I2NCR (Intra-flow and Inter-flow Network Coding Based Wireless Routing)。I2NCR首先用改进的流间网络编码策略INCS(Improved Inter-flow Network Coding Scheme)寻找一条尽可能多的编码机会的固定路由,使路由具有更高的网络吞吐量；然后每一跳数据传输利用流内网络编码的局部机会路由方法LOR (Local Opportunistic Routing)。I2NCR可以在保证数据包可靠传输的同时,提高吞吐量；INCS解决了编码包多播时因多条链路丢包率不同而造成的数据包的重复发送问题,减小了数据包的传输次数,从而提高网络的吞吐量。LOR利用无线信道的广播特性,启用ETX (Expected Transmission Count)值更小的辅助节点转发丢失的数据包,从而在保证数据包可靠传输的情况下,减小了数据包的重传次数。理论分析和仿真实验都表明I2NCR比传统的固定路由和非网络编码路由具有更小的数据包传输次数,更大的网络吞吐量。本文所提出的CGAR、NCPCR和I2NCR等路由算法,对降低无线网络的传输时延,提高吞吐量、以及降低能耗具有重要的理论与应用价值。更多还原

【Abstract】 Nowadays, wireless network has been deep into every corner in our daily life, which influences and changes people’s way of life. In order to send data from one node to another node, wireless network needs routing protocol. The main function of the routing protocol is to find and maintain the transmitting path of data in networks, which plays a decisive role in information dissemination and sharing for wireless networks.Network coding is a new information technology emerged at the beginning of this century. It can greatly improve the network throughput and reliability. It changes the characteristic of receiving-forwarding of the traditional routing protocol, and makes the node have both receiving-forwarding and encoding functions. That is, it lets node encode several packets from different flows into a coded packet to be transmitted so that the number of packet transmissions is reduced, bandwidth utilization and the throughput of network are improved. The characteristic of network coding and the broadcasting nature of wireless channel inspire researchers to apply network coding in wireless network routing protocol so as to improve the routing throughput and lower delay.The mechanism in the network coding based routing for wireless network is quite different from that in the traditional routing. The difference mainly exists in that, in addition to consider the packet transmission rate, delay, throughput, packet loss rate, and other factors which the traditional routing protocols cover, of the optimal network coding scheme should be taken into account. In this dissertation, we study the algorithms based on network coding for wireless network using the broadcast nature of wireless links and investigate the coding-aware routing mechanism, which is different from traditional ones, and its key issues. We mainly focus on the influences of such factors as wireless link unreliability, limited energy and, bandwidth on network coding. In addition, we present the theoretical solutions and its applications. The main work and achievements are as follows:1) The low delay routing problem based on network coding is proposed. We present a coding gain aware low delay routing (CGAR), which is derived from the characteristic of network coding being able to improve network throughput and reduce data transmission delay. The main idea underlying CGAR is that, it lets the node separate data into two parts and one of the parts is transmited using available channel while the other is network coded with the packet from other flows and shares the channel occupied by these flows, improving bandwidth usage and the throughput and reducing data transmission delay. In this dissertation, via introducing coding graph, the problem of encoding the flows is changed into the one to find the least number of complete subgraph in a coding graph. In addition, the coding condition for the multiple flows in the coding graph to be coded is proved and the method of simplifying the coding graph is given. To remedy the problem that the flows with different data rates can not be coded directly, we code them using the method of split-flow and present the greedy algorithm to calculate network coding gain. CGAR takes the delay of transmitting one package as routing metric, which considers the impacts of coding opportunity, available channel, packet loss rate on delay. Simulation experiments show that CGAR has lower transmission delay compared with the DCAR and COPE, the two famous routing algorithms around the world.2) The energy-efficient routing based on network coding is investigated. In wireless network, lowering node transmitting power can reduce the energy consumption, but it possibly decreases link reliability and increases the link bit error rate as well as packet loss rate, which may increase the number of packet retransmissions and consume more energy. To solve this problem, we present an energy efficient routing algorithm based on network coding and power control for lossy networks (NCPCR). Noting that energy consumed by the node depends on its transmitting power and the number of data packet transmissions, the proposed NCPCR reduces transmitting power via power control and reduces transmission number by network coding, and it also balances them to reduce energy consumption as far as possible. NCPCR takes into account the decoding failure resulting from the failure of decoding node overhearing and computes the condition probability of decoding node overhearing the data transmitted by other nodes, and on this basis, the efficient coding condition for the coding node is presented. Simulation experiments show that NCPCR consumes less energy than DCAR and COPE.3) The routing with high throughput and reliability based on intra-flow and inter-flow network coding is studied. By making advantage of the propery that inter-flow network coding can improve the throughput of network and intra-flow network coding can improve reliability of network, we present an algorithm of intra-flow and inter-flow network coding based routing for wireless networks (I2NCR). First, I2NCR uses the improved inter-flow network coding scheme (INCS) to find a fixed routing with as much coding opportunity as possible, making higher throughput. Then, the intra-flow network coding and local opportunistic routing (LOR) is applied in the transmission of each hop. I2NCR can improve throughput while ensuring reliable transmissions of the data packets. INCS overcomes the problem of data retransmissions caused by the different loss rates among multiple links when coding packets are multicast, and it also reduces the number of packet transmissions so as to greatly improve network throughput. LOR reduces the number of retransmissions while guaranteeing the reliable transmission of the data packet using broadcast nature of the channel and letting the node with less expected transmission count (ETX) foreward data. Theoretic analysis and simulation experiments indicate that I2NCR has less number of packet transmissions and higher throughput than the traditional fixed routing and non-network coding routing.The proposed routing algorithms, including CGAR, NCPCR, and I2NCR, are significant in reducing packet delay, improving network throughput, and reducing energy consumption.更多还原