论文摘要
当今社会,无线网络已经深入到日常生活的每个角落,它影响并改变了人们的生活方式。为了把数据从一个节点传输到另一个节点,无线网络需要路由协议。路由协议的主要功能是,在网络中寻找和维护数据传递的路径,它对无线网络的信息分发与共享是举足轻重的。网络编码是本世纪初出现的一项新的信息技术,能极大地提高网络的吞吐量和可靠性。它改变了传统路由协议中节点的“接收——转发”这一特点,使节点既有“接收——转发”功能,同时还具有编码功能,即让节点把来自不同流的多个数据包编码成一个编码包,然后再发送出去,这样,可以减少数据包的发送次数,提高带宽的利用率,增大网络的吞吐量。网络编码的这一特点以及无线网络信道的广播特性,启发研究人员将网络编码应用于无线网络的路由协议中,以提高路由协议的吞吐量,降低时延。把网络编码应用于无线网络,其工作机制与传统的无线网络路由机制有明显的不同,主要表现在：除了需要考虑传统的路由协议涉及的数据包传输速率、时延、吞吐量、丢包率等因素之外,还要考虑最佳网络编码方案因素。本文利用无线链路的广播特性研究基于网络编码的无线网络路由算法。研究不同于传统无线路由的网络编码感知路由机制及其关键问题；重点研究无线链路不可靠性,以及无线网络节点的能量、带宽等的受限性等因素对网络编码的影响；并给出理论层面和应用层面的解决方案。本文的主要工作和成果如下：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等路由算法,对降低无线网络的传输时延,提高吞吐量、以及降低能耗具有重要的理论与应用价值。