网络编码改变了传统通信方式，允许节点对接收的不同数据包进行编码转发，增加节点单次传输的数据量。研究证明网络编码能有效提高网络吞吐量。在无线多跳网络中，鉴于网络编码的优势，将网络编码技术与路由传输相结合，提高路由传输效率。但研究人员发现传统基于网络编码的路由算法并不能充分发挥网络编码的优势，其原因为网络性能的提升取决于网络中编码机会被利用的数量。因此，编码感知技术被提出，该技术能够主动探索无线多跳网络中的编码机会，将编码机会作为路由选择的衡量标准，从中选取编码机会较多的传输路径。本文将无线多跳网络中的编码感知路由算法为研究核心，充分了解编码感知路由算法的背景知识及意义，掌握编码感知原理并归纳总结现有编码感知路由算法的特征。在此基础上，本文的主要工作将从以下两个方面展开研究：无线多跳网络随着无线通信业务的普及，无线通信技术被广泛应用，给人们日常生活带来了便捷。传统无线通信依赖预设的网络设施，不能够满足移动性要求高的应用场景，例如军事作战、火灾现场、科研考察等相关工作。因此无线多跳网络(Wirless Multi-hop Network,WMN)在这些场景中得到广泛的应用。在无线多跳网络中，被人们所熟知地主要有无线自组织网络[1-2]、无线传感器网络[34]和无线网状网络[5-6]。这些网络有个共同地特点：网络组建不受外界限制，且能快速组建成一个完整地网络，每一个节点独立运行，互不干涉，且都具有报文转发能力，呈现出去中心化形式。相对于传统网络，无需对中心节点进行设置，使得网络更具灵活性。若该网络中的一个节点发生故障，通过调动其他节点迅速恢复通信，不会影响该网络的性能。尽管无线多跳网络易组织，移动性强，但相比有线网络存在如多径效应，信道冲突，信号衰落，通信盲区等局限，影响无线网络传输性能。与此同时，用户对无线网络业务通信质量要求越来越高，在网络服务多样化的时代，如何提高网络的吞吐量，确保网络传输的可靠性，充分利用网络资源等相关问题已成为当今研究的热点。网络编码[7]Network Coding)在此背景下应运而生，大量理论证明网络编码能够达到“最大流-最小割”容量。且网络编码技术在提升网络的吞吐量，改善负载均衡，减少传输能耗，增强网络健壮性等方面有明显的优势[8-10]。网络编码改变了传统路由通信的“存储-转发”模式，使得通信节点具有“编码-转发”的能力，通信节点可将接收的多个数据包编码，然后送至下游节点，下游节点通过缓存的数据包解码出原有数据包，有效减少了传输时间，减轻了各条数据流竞争干扰，提高了网络吞吐量。可以得出，网络编码技术在无线多跳网络中具有一定优势，越多的数据编码可获得更多的编码增益。因此，如何打破编码机会数量的限制，发现更多有效的编码机会，是目前重要的一个研究方向。研究发现，传统的基于网络编码的路由协议仅根据邻居节点缓存数据包的情况对接收的数据包进行被动的网络编码，不能够充分发挥网络编码优势[11-12]。因此简单地将网络编码和路由协议结合是不可取的。需要重新考虑网络编码和路由协议之间的合理设计。在2006年N等人第一次提出编码感知路由协议[l3](Routing with Opportunistic Coded exchange,ROCX),将编码增益作为选择路由的标准，将主动寻找编码机会较多的节点作为转发节点，克服了传统路由对网络编码的限制。综上所述，编码感知路由能够发现无线多跳网络中的编码机会，在一定程度上能提升传输有效性。但在已有的编码感知路由方案中，大多数进强调增加编码机会，将编码机会作为路由衡量的唯一标准，导致部分编码机会无效，尤其在多流环境下，使得数据流之间干扰加剧，鲁棒性降低。因此，在寻找更多编码机会的同时，如何避免干扰来提升编码机会的有效性，有待继续深入研究。此外，在时变网络中研究如何提高路由的鲁棒性，在增加吞吐量的同时降低时延具有一定的实际意义。1.2国内外研究现状传统网络中，网络节点一般采用“存储一转发”模式处理数据，并认为数据在中继节点上不进行任何操作，仅作为转发器对数据的传输不带来任何增益。文献[7]中首次提出网络编码概念，网络编码的提出打破了传统传输模式，允许编码节点对所在链路上接收的多个数据包进行编码再转发到下游节点，该方式能有效减少传输数据包的次数，从而提高网络吞吐量。相关研究证明，在理想的条件下，网络编码可使通信传输达到最大流传输的理论上界[14]。文献[15]在此基础上提出了线性网路编码(Linear Network Coding,LNC),其核心思想是网络中间节点对从各个链路中接收到的数据包进行编码操作，且从有限域上选取编码向量对数据进行加乘操作，然后转发编码包，目的节点根据无关向量从编码包中恢复所需数据包。文献[16提出随机线性网络编码(Random Linear Network Coding,RLNC,该方法根据节点的输入输出信息之间的映射关系，从伽罗华域中随机选取编码系数对数据包进行编码，目的节点通过高斯方程从编码包中恢复所需要的数据包。文献[17刀提出机会式网络编码(Opportunistic Network Coding,.ONC),机会式网络编码采用异或运算对两个或两个以上的数据包进行编码，编码系数为0或1，目的节点根据已接收的数据包和编码包进行解码。相比线性网络编码，机会式网络编码的编解码运算较为简单，如何选择有效编码包，减少数据包的传输次数是关键。早期网络编码相关研究假设在理想状态下进行。近年，一些学者将网络编码技术应用于无线多跳网络中，并将网络编码与路由协议相结合，以提高路由传输数据的性能。随着研究的不断深入，发现网络中的节点可以根据所在网络的拓扑结构以及周围邻居节点信息对自身网络编码能力作出预判，优先考虑具有网络编码能力的中继节点来传输数据，充分发挥网络编码的优势。因此，在路由创建过程中，需将节点是否具有编码能力作为路由选择的标准，对如何主动寻找网络编码机会，并综合考虑其他影响因素来提高路由性能是根本问题。现有编码感知路由协议中，主要可以分为两种类型路由：按需式编码感知路由和机会式编码感知路由。1.按需式编码感知路由按需式编码感知路由又名确定性路由，在该类路由中源节点发送数据之前，需要先执行路由发现过程，在此过程中通过将编码机会作为路由衡量的标准，选择编码机会较多的传输路径。确定传输路径后，源节点根据筛选出的传输路径发送数据包。文献[17刀提出一种基于网络编码的无线路由体系结构，编码机会实体(CodingOpportunity Entity,COPE)。其中给出了四种经典的单跳编码结构，包括链结构、“X”型结构、交叉结构和轮结构，通过机会侦听数据包来帮助编码包解码，并设计了一种链路质量度量(Link Qualify Metric,LQM)来选择高质量的转发节点。该方案的编码结构仅限于两跳范围之内，导致两跳以外的编码机会缺失。文献[18]指出COPE和ROCX存在编码机会利用不充分的问题，提出一种分布式编码感知路由(Distributed Coding Aware Routing,DCAR),该方案将编码机会的搜索范围从两跳扩展到了多跳范围，给出了多跳网络编码条件Muli-hop NetworkCoding Condition,MCC),有效增加了编码机会的数量。同时，DCAR将节点队列