无线网络中编码感知路由算法研究论文设计

　网络编码改变了传统通信方式，允许节点对接收的不同数据包进行编码转发，增加节点单次传输的数据量。研究证明网络编码能有效提高网络吞吐量。在无线多跳网络中，鉴于网络编码的优势，将网络编码技术与路由传输相结合，提高路由传输效率。但研究人员发现传统基于网络编码的路由算法并不能充分发挥网络编码的优势，其原因为网络性能的提升取决于网络中编码机会被利用的数量。因此，编码感知技术被提出，该技术能够主动探索无线多跳网络中的编码机会，将编码机会作为路由选择的衡量标准，从中选取编码机会较多的传输路径。

　本文将无线多跳网络中的编码感知路由算法为研究核心，充分了解编码感知路由算法的背景知识及意义，掌握编码感知原理并归纳总结现有编码感知路由算法的特征。在此基础上，本文的主要工作将从以下两个方面展开研究：

　无线多跳网络随着无线通信业务的普及，无线通信技术被广泛应用，给人们日常生活带来了便捷。传统无线通信依赖预设的网络设施，不能够满足移动性要求高的应用场景，例如军事作战、火灾现场、科研考察等相关工作。因此无线多跳网络(Wirless Multi-hop Network, WMN)在这些场景中得到广泛的应用。在无线多跳网络中，被人们所熟知地主要有无线自组织网络[1-2]、无线传感器网络[3-4]和无线网状网络[5-6]。这些网络有个共同地特点：网络组建不受外界限制，且能快速组建成一个完整地网络，每一个节点独立运行，互不干涉，且都具有报文转发能力，呈现出去中心化形式。相对于传统网络，无需对中心节点进行设置，使得网络更具灵活性。若该网络中的一个节点发生故障，通过调动其他节点迅速恢复通信，不会影响该网络的性能。尽管无线多跳网络易组织，移动性强，但相比有线网络存在如多径效应，信道冲突，信号衰落，通信盲区等局限，影响无线网络传输性能。

　与此同时，用户对无线网络业务通信质量要求越来越高，在网络服务多样化的时代，如何提高网络的吞吐量，确保网络传输的可靠性，充分利用网络资源等相关问题已成为当今研究的热点。网络编码[7](Network Coding)在此背景下应运而生，大量理论证明网络编码能够达到“最大流-最小割”容量。且网络编码技术在提升网络的吞吐量，改善负载均衡，减少传输能耗，增强网络健壮性等方面有明显的优势[8-10]。网络编码改变了传统路由通信的“存储--转发”模式，使得通信节点具有“编码--转发”的能力，通信节点可将接收的多个数据包编码，然后送

　至下游节点，下游节点通过缓存的数据包解码出原有数据包，有效减少了传输时间，减轻了各条数据流竞争干扰，提高了网络吞吐量。

　可以得出，网络编码技术在无线多跳网络中具有一定优势，越多的数据编码可获得更多的编码增益。因此，如何打破编码机会数量的限制，发现更多有效的编码机会，是目前重要的一个研究方向。研究发现，传统的基于网络编码的路由协议仅根据邻居节点缓存数据包的情况对接收的数据包进行被动的网络编码，不能够充分发挥网络编码优势[11-12]。因此简单地将网络编码和路由协议结合是不可取的。需要重新考虑网络编码和路由协议之间的合理设计。在 2006 年 Ni 等人第一次提出编码感知路由协议[13](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]提出一种基于网络编码的无线路由体系结构，编码机会实体(Coding Opportunity Entity, COPE)。其中给出了四种经典的单跳编码结构，包括链结构、“X”型结构、交叉结构和轮结构，通过机会侦听数据包来帮助编码包解码，并设计了一种链路质量度量(Link Qualify Metric, LQM)来选择高质量的转发节点。该方案的编码结构仅限于两跳范围之内，导致两跳以外的编码机会缺失。

　文献[18]指出 COPE 和 ROCX 存在编码机会利用不充分的问题，提出一种分布式编码感知路由(Distributed Coding Aware Routing, DCAR)，该方案将编码机会的搜索范围从两跳扩展到了多跳范围，给出了多跳网络编码条件(Multi-hop Network Coding Condition,MCC),有效增加了编码机会的数量。同时，DCAR 将节点队列

　缓存数据包的数量作为路由度量(Coding-aware Routing Metric)，选择合适的传输路径。

　文献[19]提出一种联合编码感知路由(Network Joint Coding Aware Routing, NJCAR)，允许编码节点的下游节点对编码包不一次性完全解码，可以通过分步对编码包进行解码，提高了编码包的解码效率，但计算复杂度较高。

　文献[20]针对现有编码条件不能准确的识别编码机会，提出一种通用的编码条件(General Network Coding Condition, GCC)和以免费搭载其他数据流为导向的路由度(Free-ride-oriented Routing Metric, FORM)，系统分析了可能的编码场景，并开发了一种编码图以实现条件，通过编码流选择过程来检测每个编码节点的编码能力，使得新数据流可以免费搭载现有的数据流，减少传输次数。

　文献[21]针对多流情况提出了一种分布式贪婪编码感知确定性路由(Distributed Greedy Coding-aware Deterministic Routing, DGCDR)，将多条数据流进行编码，同时考虑到多流编码可能存在干扰问题，通过增加额外的路由过程来检测编码机会的有效性，在一定程度上有效提高了网络吞吐量。

　文献[22]分析了 DCAR 类型的方案在检测更多编码机会时，可能存在网络负载不均衡，针对该缺点提出了一种约束编码感知路由机制(Constrained Coding-Aware Routing Scheme, CCAR)，通过约束编码条件检测良好的编码机会，根据定制的“路由+编码”发现过程计算输出队列长度，评估编码节点的状态。

　2.机会式编码感知路由 机会式编码感知路由发送数据前无需先确定传输路径，发送数据的每一个节点通过计算与各邻居节点之间编码机会概率，选择编码增益最大的节点作为下一跳接收节点，然后编码数据包并广播编码包至该邻居节点。

　文献[23]提出了典型的机会式编码感知路由机制(Coding-aware Opportunistic Routing Mechanism, CORE)，通过将逐跳机会转发和流间网络编码相结合，允许节点从邻居节点集中选择编码增益最大的节点作为下一跳节点，该方法总是具有最大的编码增益，从而提高了单次传输的数据量。机会式编码感知路由对动态网络更具有适应性，但机会式路由对下一跳的选择计算较为复杂，可能产生较多的计算开销。

　文献[24]提出一种基于队列状态和局部拓扑的增强型编码感知路由算法(An Enhanced Network Coding-aware Routing Algorithm based on Queue State and Local

　Topology, OQMCAR)，该方案考虑了节点编码数据包的队列状态，在每一次机会传输中，采用基于队列长度的阈值策略，对数据包进行有效的“传输或等待”决策，而不非现有的感知编码路由算法中使用的机会编码策略。

　文 献 [25] 提 出 一 种 高 效 的 基 于 网 络 编 码 的 背 压 调 度 算 法 (An Efficient Network-coding based Back-pressure Scheduling Algorithm, NBP)，背压调度被认为是无线多跳网络中有效的资源分配策略，该方案将背压调度与网络编码相结合，能够有效应对动态拓扑，确保传输的稳定性。

　文献[26]提出一种网络拥塞避免编码感知路由方案(Congestion-Avoidance Network Coding-Aware Routing, CANCAR)，该方案考虑了拥塞强度和数据流编码成功的实测信息，将编码不佳的数据流在网络瓶颈处重新路由，在变更过的路由路径上创造编码机会。能有效地将网络中负载最重的部分从编码最少的流量中释放出来，使得最大的负载节点处的编码流获得更高的编码增益。

　根据现有的按需式编码感知路由，大多数方案一味地追求探索更多的编码机会，而忽视编码机会的有效性。这与编码机会判断条件的不合理性有关，复杂网络中多条数据流进行编码在一定程度上能够增加编码机会的数量，但这些编码机会中可能存在一些因干扰而失效的编码机会，导致生成的编码包不可解，从而影响无线多跳网络的传输性能[27]。此外，按需式编码感知路由的数据传输是建立在可靠传输路径上，但在时变网络中按需式编码感知路由的稳定性容易受此影响[28]。因此，如何获得更多编码机会的同时确保编码机会的合理性，且有效应对网络拓扑变化提高传输效率，具有重要的研究价值。

　1.3 研究主要内容与目标 本章分析了网络编码与编码感知路由的特点，在现有研究成果基础上，对编码感知路由在无线多跳网络的应用进行深入的研究，主要以编码感知路由在多流环境中如何寻找更多编码机会，避免多流干扰提高编码包的解码率，提高编码感知路由在动态网络的适应性，减少数据包的传输时延和提高网络吞吐量为研究目标，提出了解决多流干扰的编码感知路由算法(Coding-aware Routing to Solve Multi-flow Interference, CRSMI)和一种基于背压策略的编码感知路由算法(Coding Aware Routing based on Back-pressure Strategy, BCAR)。

　本文主要研究的工作和创新具体如下：

　1、介绍了无线多跳网络的特点、网络编码的分类及不同类型编码感知路由的优缺点。详细阐明了基于网络编码技术的数据传输基本原理与编码感知路由技术的结构组成与实现机制，其中主要包括编码感知路由的分类和编码感知路由设计所需解决的关键问题。

　2、针对现有的编码感知路由，现有的大多数确定性编码感知路由的编码机会判断条件只考虑任意两条数据流之间的编码机会，忽略了多流之间的编码机会。但在多流情况下，当现有编码流与新数据流满足编码条件再次进行编码时，现有编码流和新数据流之间可能存在干扰，使得产生的编码包不能够解码。为防止多流干扰引起的错误编码导致系统性能下降，本文提出一种解决多流干扰的编码感知路由协议(CRSMI)，并定义了多流网络编码条件。在路由创建过程中收集多流的传输信息和流经节点的侦听信息，通过多流编码条件对收集的信息进行编码机会判断，筛选出有效的编码机会，确保生成的编码包可以在各自的目的节点完全解码。此外，在路由度量方面综合考虑了编码增益和链路质量等因素，选择最佳传输路径。

　3、针对现有的编码感知路由，经研究发现，大多数方案的设计侧重于固定的传输路径和静态数据流。以该方式设计的路由在一定程度上容易受到动态拓扑及动态数据流的影响。使得路由不断地进行路由发现过程，导致路由过度增加时延且不能稳定地传输数据，影响网络吞吐量。本文提出一种基于背压策略的编码感知路由算法(BCAR)，该算法通过将背压策略与网络编码相结合，根据网络状况对网络资源作出调度，综合考虑编码机会、队列梯度和队列中数据包的积压时间等因素，将数据包发送至编码机会较多且拥塞程度较低的节点，同时能够将队列中积压时间较长的数据包优先传输，以减少数据包在网络中的滞留时间。

　1.4 论文组织结构 本文内容组织结构如下：

　第一章引言。主要阐述网络编码与编码感知路由的研究背景及其意义。同时，总结了网络编码及编码感知路由的国内外研究现状，分析了按需式编码感知路由和机会式编码感知路由在无线多跳网络中的发展优势，最后介绍本文的主要研究内容与目标。

　第二章网络编码与编码感知路由相关介绍。具体阐述了网络编码原理及涉及的相关基础，并对现有编码感知路由方案进行详细分类总结，从数据来源、编码结构

　和感知时机三个方面进行分类，同时分析归纳了编码感知路由的编码条件和路由度量在无线多跳网络中的特点及优势。

　第三章解决多流干扰的编码感知路由算法研究。现有按需式编码感知路由的网络编码条件存在一些不合理性，容易受多流干扰的影响，导致产生的部分编码包不可解，针对该问题本文提出了解决多流干扰的编码感知路由算法，设计了一种多流网络编码条件，并给出了编码节点判断算法和路有度量的详细设计，具体介绍了整个方案的路由过程、传输步骤、实验仿真以及性能分析。

　第四章基于背压策略的编码感知路由算法研究。根据目前编码感知路由的研究现状，针对按需式编码感知路由在时变网络中鲁棒性不足等问题，提出基于背压策略的编码感知路由算法研究，介绍了传统背压策略的调度过程，通过编码感知路由结合背压策略的优势，给出了具体的链路选择步骤，最后具体介绍方案的仿真实验及性能分析。

　第五章结束语。对全文进行总结，并对后续相关研究工作进行介绍。

　第 2 章 相关基础 2.1 网络编码简介 2.1.1 网络编码原理 相关研究发现，传统传输模式的传输链路存在一定局限性，对传输的数据不进行任何操作也无任何额外信息增加，导致整个系统吞吐量不高。而网络编码技术能打破该局限，使得中继节点不仅保留传统的“存储-转发”功能，还允许中继节点拥有对数据编码组合的能力，中继节点按照相应的编码规则将不同数据编码后转发至下游节点，下游节点依据缓存信息将满足解码条件的编码包解码，从中恢复所需数据包。该技术能有效减少数据传输次数，节约了网络资源，提高了网络传输效率[29-31]。

　如图 2.1 所示，通过链式传输模型对比传统传输模式与基于网络编码的传输模式图。如图 2.1(a)所示，在传统传输模式中，时隙 t1 节点 S1 传输数据包 P1 到节点R，时隙 t2 节点 S2 传输数据包 P2 到节点 R，时隙 t3 节点 R 向节点 S2 发送数据包 P1，时隙 t4 节点 R 向节点 S1 发送数据包 P2，信宿端分别接收到请求包共需4 个传输时隙。图 2.1(b)所示，基于网络编码的传输模式中，在时隙 t3 时，节点R 将接收的数据包 P1 和 P2 进行编码，生成编码包 P1⊕P2 并同时发送至节点 S1

　和 S2 中，信宿端根据接收的编码包和已有数据包，可以译码出请求数据包，整个传输过程只需 3 个时隙，比传统传输模式节省了 1/4 传输时隙。

　由此可见，网络编码可为两条数据流创造一次编码机会，那么更多数据流交汇的通信情况，则存在的编码机会数量可能就会越多[21][32]。因此，在无线多跳网络中，为提高传输有效性，需增加编码机会的数量，而编码机会的数量某种程度上取决于数据流之间的拓扑关系，当数据流交汇较少时，编码机会也十分有限，从根本上限制了传输有效性的提升[33-34]。

　2.1.2 网络编码特点 网络编码技术一直以来得到广泛的关注，特别是网络编码技术特点与无线网络广播特性有很好的契合性，因此网络编码技术被应用到了无线网络不同的场景。网络编码利用数据包之间的关联性，通过增加编码节点的计算开销换取了传输链路的传输有效性。网络编码共有以下特点：

　1.增加网络吞吐量 在无线多跳网络中，当存在数据流相交时交叉节点可采用网络编码技术对接收到的数据包进行网络编码，将生成的编码包通过广播方式发送至各下游节点进行解码，这一编码转发过程增加了交叉节点单次传输的信息量。与传统通信相比，打破了传统通信单次传输容量的限制，使得系统的整体网络流量得到显著提升。因此，网络编码在增加网络吞吐量方面具有明显优势。

　2.增强网络通信的安全性 对于传统的网络通信，窃听者通过窃听目标节点传输的信息，造成节点传输的信息泄露。攻击者通过篡改或伪造的方式对网络通信造成污染，使得网络通信安全性降低。如图 2.2(a)所示，窃听者在每一次的传输过程中都能侦听到原始数据包，当传输重要信息时，传统传输模式具有严重的安全隐患。在图 2.2(b)中，源节点S 不再单独发送原始数据包，而是将原始数据包进行编码，窃听者窃听到的数据包为编码包，要想获得原始数据包，必须获得足够的数据包并且知道编码规则，否则窃听者无法从中获取原始数据包。同时，若攻击者想伪造数据对通信消息进行污染，由于节点对数据包的编码方式在不断的变化，当下游节点接收到伪造的数据包无法进行解码时，接收节点会将污染数据包丢弃，防止被污染的数据包继续向下扩散而造成不可挽回的局面。

　3.提高数据传输可靠性

　在无线网络中，数据的传输容易受到发送端的发送功率、信道衰落和多径效应的影响，导致部分数据包在传输的过程中无法正确到达目的端。为了提高数据传输的可靠性，通常将数据包以多路径传输方式进行传输，减少链路干扰对数据传输的影响。虽然该传输方式提高了传输可靠性，但也增加了发送端的发射功率。特别针对传感器网络，每个传感器需电源供给，传输次数的增多会导致传感器耗能加快，并且传感器的更换较为复杂，不利于传感器网络的稳定运行。网络编码技术在传感器网络的应用，编码节点能够将数据包进行线性或非线性编码，能有效减少节点数据包的传输次数，即便传输过程中出现丢包情况，节点可以通过缓存数据包对接收的编码包进行解码，从中恢复所需数据包，有效地改善数据传输的可靠性。

　2.2 编码感知路由技术概述 随着对网络编码研究不断的深入，一些学者发现传统的基于网络编码的传输方案仅被动等待编码机会，不能够主动寻找编码机会，使得网络中的编码机会不能被充分利用，不利于传输有效性的提高。将网络编码与具有感知能力的路由相结合，研究如何在传输数据的过程中主动探索并利用网络中编码机会现已成关注热点。

　编码感知路由在建立路由的过程中将编码机会作为路由选择的依据，主动选择具有编码机会多的链路作为传输链路，充分利用链路中的编码机会，使得系统性能进一步提升。如图 2.3 所示，假设存在两条数据流和，在图 2.3(a)中传统路由传输两条数据流分为两条路径，这两条路径不存在交叉节点，所以数据流和数据流之间不存在编码机会。在图 2.3(b)中，由于编码感知路由能够主动发现网络中潜在的编码机会，在传输数据流之前优先选取链路作为数据流的传输链路，当数据流和在节点 A 交汇时，节点 A 可以将不同流的数据包进行编码，再将编码包分别向节点 S 和 D 发送，能有效提升传输效率。

　随着编码感知路由研究不断的深入，现有的编码感知路由方案从数据来源、编码结构和感知时机三个方面深入。

　1.数据来源 根据参与编码数据来源的不同，可将现有的编码感知路由分为流内网络编码和流间网络编码。流内网络编码是指节点编码的不同数据包来自于同一条数据流。流间网络编码是指节点对来自不同数据流的数据包进行网络编码。两者的编码方式在本质上有所不同，在不同场景表现出各自的优势。

　对于流内网络编码，节点将同一条数据流中的数据进行合理分组，由表示，然后通过线性组合的方式对这些分组进行网络编码生成编码向量 Y，其中编码向量的编码系数 X 从有限域中随机选取，数据分组的编码过程见公式(2.1)和公式(2.2)。之后节点将编码包发送至目标节点，当目标节点接收的编码包为线性无关时，可将接收的编码包进行解码，解码过程见公式(2.3)。从公式可以看出，经过线性编码后的数据更具有安全性，同时也减少了节点传输数据的次数，增加了传输效率，但整体的计算开销较大，不适合在动态拓扑网络中执行。

　对于流间网络编码，网络中的节点接收来自不同数据流的数据包，根据编码条件将满足条件的数据包进行编码并以广播方式转发至下游节点，下游节点通过机会侦听或自身缓存的数据包来解码编码包。在大量数据流交叉通信的情况下，流间网络编码主要采用简单高效的异或编码(XOR)运算，有助于降低编解码过程的计算复杂度。在现有的编码感知路由中，多数方案主要研究数据流之间的编码机会，因此流间网络编码的应用较为广泛，其关注热点为如何在无线多跳网络中根据数据流的空间分布，寻找潜在的编码机会以提高编码增益。

　2.编码结构 为提高编码感知路由性能，需要解决如何提高编码机会数量这一根本问题，编码机会的形成取决于网络中各数据流的空间分布，因此数据流之间的拓扑关系直接影响编码机会是否存在。对于存在编码机会的数据流空间分布，将其称为编码结构。编码感知路由根据当前数据流形成的编码结构即可判断各数据流之间是否存在编码机会。当然，不同的编码结构能够发现不同范围内的的编码机会，很显然寻找编码机会的范围越大，则存在的编码增益可能就越多。通过对现有的编码感知路由研究现状分析，现介绍单跳编码结构、多跳编码结构和联合编码结构三种具有代表性的方案。

　相关符号解释，如表 2.1 所示。

　表 2.1 符号表 符号 定义 数据流 f 经过的的任一节点 c 节点 c 的邻居节点集合 数据流 f 上节点 c 的下一跳节点 数据流 f 上节点 c 的上一跳节点

　数据流 f 上节点 c 的下游节点集合 数据流 f 上节点 c 的上游节点集合 (1)单跳编码结构 文献[13]中给出了最原始、最简单的编码结构，单跳编码结构(Single-hop Coding Structure, SCS)。SCS 结构规定节点生成的编码包仅能一跳传输，必须在编码节点的下一跳节点中被立即解码，该编码结构的编码机会被限制在一跳范围内。根据节点有无侦听机制，SCS 编码结构可继续分为单跳无机会侦听编码结构(Single-hop Coding Structure without Opportunistic Overhear, SCS-O)和单跳有机会侦听编码结构(Single-hop Coding Structure with Opportunistic Overhear, SCS-W)。

　如图 2.4 为 SCS-O 结构，假定两条数据流，在中间节点处相交，节点和节点分别发送各自的数据包，至中间节点，节点将接收的数据包编码以广播方式发送至各目的节点，节点和节点根据自身发送的原始数据包对接收的编码包进行解码，从中恢复出各自所需的数据包。根据上述描述，SCS-O 结构可形式化的表示为：

　图 2.4 单跳无机会侦听编码结构 如图 2.5 为 SCS-W 结构，假定两条数据流 f1，f2 相交于节点 R，节点 S1 和节点S2 分别发送各自的数据包 P1，P2 至中间节点 R，节点 R 将接收的数据包编码以广播方式向各目的节点 D1，D2 发送，节点 D1 和节点 D2 通过机会侦听的方式侦听各自邻居节点发送的数据包，节点 D2 能够从节点 S1 中侦听到数据包 P1，节点 D1 能够从节点 S2 中侦听到数据包 P2，因此，各目的节点根据侦听到的数据包从编码包中恢复出所需数据包。根据上述描述，SCS-W 结构可形式化的表示为：

　图 2.5 单跳有机会侦听编码结构 (2)多跳编码结构 文献[18]给出了多跳编码结构(Multi-hop Coding Structure, MCS)，允许编码节点产生的编码包在两跳以外的节点进行解码，将编码机会的搜索扩展到两跳范围，相比 SCS 编码结构，MCS 能够寻找到更多的编码机会。如图 2.6 所示，假定有两条数据流 f1，f2 相交于节点 R，距离节点 R 两跳的下游节点 D2 接收到编码包P1⊕P2，节点 D2 通过机会侦听机制从节点 S1 侦听到数据包 P1，节点 D2 通过

　侦听到的 P1 数据包可以解码出数据包 P2。根据上述描述，MCS 结构可形式化的表示为：

　图 2.6 多跳编码结构 (3)联合编码结构 文献[19]给出了联合编码结构(Joint Coding Structure, JCS)，该编码结构不再要求编码包在下游节点一次性解码，而是根据下游节点侦听到全部原始数据包并且下游节点被认定为是解码过程中的一部分，将编码包在多个下游节点进行分步解码，从而提高编码包的解码率。如图 2.7 所示，三条数据流 f1，f2，f3 交汇于节点R1，每条数据流分别发送各自的数据包 P1，P2，P3 至节点 R1 进行网络编码操作，再将编码后的数据包 P1⊕P2⊕P3 转发到各自的下游节点进行解码。传统网络编码方式下，路径中，R1 的下游节点不能够接收到其余两个数据包，无法对编码包进行解码，所以不存在编码机会，下游节点对接收到的数据包进行缓存或丢弃。在联合解码结构下，节点 R2 通过侦听从邻居节点 S3 侦听到数据包 P3,节点 R1 将编码后的数据包转发到节点 R2 进行分步解码，得出新的编码包 P1⊕P2，节点 R2 再向下转发到节点 D2，节点 D2 通过侦听得到数据包 P1，可以继续解码得到自己所需的数据包 P2。根据上述描述，JCS 结构可形式化的表示为：

　图 2.7 联合编码结构 3.感知时机 对于现有的编码感知路由对编码机会的感知时机，可分为两类：按需式编码感知路由和机会式编码感知路由。

　按需式编码感知路由是指网络中的源节点节点与其他节点建立通信时，源节点发起路由发现过程，寻找一条可用的传输路径来发送数据。该类型路由的编码感知时机在路由发现过程中，其过程主要分为路由请求和路由应答两个阶段，源节点发送多个路由请求(Routing Request, RREQ)数据包向目的节点传输，RREQ 数据包每经过一个节点便将该节点信息和编码机会情况记录在 RREQ 数据包中，若中继节点重复接收 RREQ 数据包，则将其丢弃，防止形成环路。当多个 RREQ数据包到达目的节点时，目的节点根据 RREQ 数据包中记录的信息生成路由应答(Routing Reply, RREP)数据包，按照 RREQ 数据包的路径原路返回。源节点从多个 RREP 数据包获得多条传输路径，根据路由度量对多条路径进行筛选，从中选取编码增益最多的传输路径。该类型编码感知路由适合较为稳定的网络场景。

　机会式编码感知路由是指网络中的源节点发送数据前无需先与目的节点建立确定传输路径，源节点将邻居节点纳入节点转发集中，在确定节点转发集后，将数据发送至转发集中的各节点，根据编码机会带来的编码增益确定各节点的转发优先级。一般情况下，编码增益越高节点的转发优先级越大，则优先级最大的节点优先对数据包编码并转发。因此，机会式编码感知路由的编码感知时机在选择转发节点阶段，该类型路由适用于无线时变网络，其原因为无线信道的时变性和节点的移动性，导致无线网络中的传输链路质量不稳定，机会式编码感知路由能够根据网络的实时情况选择链路状况较好的来传输数据。

　2.3 路由度量定义 路由度量是用来衡量链路选择的一个指标，根据不同的网络场景，路由度量考虑不同的因素选择合适的传输路径。由此可见，路由度量的设计对路由策略有着至关重要的作用。现有主流的路由度量有以下几类：

　1.最小跳数 最小跳数(Minimun Hops, MH)是指源节点传输数据包至目的节点所经过节点最小数量。在选择路径时，路由决策会选择路径中节点个数最小的链路作为传输路径。该路由度量是从有线网络发展至无线网络，在传统路由中较为常见，其内部算法为熟知的 Dijksta 算法或线性规划算法，计算方便简单。

　2.期望传输次数 期望传输次数(Expected Transmission Count, ETX)是指源节点向目的节点发送数据总共需要的传输次数[35-36]。在实际无线多跳网络中，无线信道会因受到外界因素而产生丢包情况。因此，信道质量是需要考虑的重要因素。假定无线网络中任意两个节点之间的链路为，链路的丢包率为。当链路(a,b)经过 n 次尝试成功传输数据包的概率为 s(n)，其公式如下：

　那么链路成功传输数据包所需要的期望传输次数可表示为：

　由此可见，丢包率越小 ETX 的值越小，链路传输数据的效率就越高。因此在选择链路时，应选择预期传输次数最少的链路。

　3.期望传输时间 期望传输时间(Expected Transmission Time, ETT)是指源节点向目的节点发送数据包预期需要的传输时间[20]。该度量考虑预期传输次数的同时，还考虑了数据包的大小和信道速率，其公式如下：

　其中，S 表示为链路速率，B 表示数据包的大小。整条传输路径的期望传输时间为源节点到目的节点之间所有链路的期望传输时间之和。

　2.4 本章小结 本章主要介绍网路编码和编码感知路由技术等基础性知识。首先介绍了网络编码基本原理，并对比基于网络编码的传输模式和传统传输模式，总结了网络编码技术在无线传输中的优势。其次，介绍编码感知路由技术，并从数据来源、编码结构和感知时机三个方面对编码感知路由技术进行分类。最后，介绍了现有主流路由度量。

　第 3 章 解决多流干扰的编码感知路由算法研究 3.1 引言 编码机会是提高编码感知路由性能的最基本因素，编码机会形成于数据流之间的相互用，编码机会的数量由数据流之间的拓扑结构决定。因此，一种好的路由决策能够直接影响编码感知路由中网络编码的性能。根据相关研究发现，文献[18][37-39]所提方案多局限在讨论任意两条数据流之间的编码机会，忽略了多流之间的编码机会。当在多流环境下进行网络编码时，数据流之间相互作用较为复杂，容易产生干扰，由于编码条件的不完备性，使得新加入的数据流产生不可解的编码包，从而影响了新数据流的传输效率。

　针对上述问题，本文提出一种解决多流干扰的编码感知路由方案。为防止多流干扰导致伪编码机会的产生，需确保编码条件的正确性，该方案首先定义了多流网络编码条件，严格筛选网络中的编码机会，确保编码节点生产的编码包能够完全解码。其次，重新设计了路由发现过程中所发送的消息格式，用于收集必要信息，通过编码节点判断算法判断编码机会的有效性。此外，在路由度量方面综合考虑了编码增益和链路质量等因素选择最佳传输路径。

　3.2 现有编码感知路由存在的问题分析 对于现有的编码感知路由，大多数方案编码机会判断条件在两条流之间判断编码机会是可行的，但在大于两条流（多流）的某些场景下会存在所生成编码包在信宿解码失败的问题。以下通过两个示例进一步加以说明。

　引理 3.1 多跳编码条件[18]：MCS 结构下，有多条数据流，其中任意两条数据流相交于节点，在节点处的网络编码条件为：

　图 3.1 多流干扰示意图

　如图 3.1(a)所示，两条数据流在节点交汇，根据多跳编码条件，，并且，。，并且，。满足引理 1 条件，并且节点分别通过侦听能够获得用于解码的数据包。

　当多流情况下，如图 3.1(b)所示，新数据流出现，数据流交汇于节点，数据流同样能够满足引理 1，即，并且，。，并且，。节点对数据流发送的数据包进行编码生成编码包，发送至各自下游节点。但节点从节点侦听的数据包不能解码出原始数据包，节点所满足的编码机会为伪编码机会。可以看出数据流与之间存在干扰。

　对于编码感知路由，编码条件的正确性对编码机会的识别至关重要，所以本文将设计一个能够避免多流干扰的编码条件，并通过相应算法从潜在的编码机会中筛选出有效的编码机会，来提高节点的编码效率，从而提高路由传输性能。

　3.3 网络模型 本文采用的网络模型为多流多跳无线网络，如图 3.2 所示。该网络模型由多个节点组成，每条数据流的数据包由源节点发送到目的节点，并能够与其他数据流交叉通信，为了提高传输效率，交叉节点对来自不同数据流的数据包进行网络编码，将生成的编码包再广播，编码包是由多条流发送的原始数据包组成的。若网络中的下游节点能通过侦听获得足够的信息则可通过相互协作对编码包进行分步解码，直到目的节点能够从编码包中解码出原始数据包。如图 3.2 所示，假设存在三条数据流、和，各数据流所对应的数据包分别为、和，源节点、和分别发送数据包、和至中间节点处进行网络编码，再向下游节点()广播编码包。各下游节点通过侦听机制能够从其他流的上游节点()分别获取原始数据包，以协助完全解码。

　图 3.2 网络模型 3.3 解决多流干扰的编码感知路由设计 本文所提编码感知路由协议是一种确定性路由，源节点在发送数据包之前需预先知晓完整的传输路径，这一特性可使源节点筛选出能够实现最佳编码的传输路径。因此，CRSMI 协议设计主要包括编码机会条件判断、路由发现、路由度量和路由选择四部分。

　3.3.1 多流编码条件定义 在编码感知路由中，编码条件对路由的编码机会和编码增益有着至关重要的作用。为防止伪编码机会的产生，本方案提出了多流编码条件，在多跳编码条件的基础

　上添加了编码包能否完全解码的判定限制，用于评估交叉节点在多流情况下的编码机会。

　假设存在相交于节点，表示流中节点的上游节点集合，表示流上节点的下游节点集合，表示节点 a 的一跳邻居。假设，a 能够侦听到节点 b 发送的数据包。表示节点从节点 s 中侦听到的数据包，表示对各下游节点侦听到的数据包进行 XOR操作，即。表示 m 个原始数据包通过 XOR 生成的编码包，表示数据流的原始数据包。

　定理 3.1 多流网络编码条件：有多条数据流相交于节点，任意两条或多条数据流均能满足如下充分必要条件，则节点 c 能进行网络编码：

　充分性证明：多条数据流相交于节点时，满足定理 1 的节点必然满足引理 1 的编码条件，即多流能够在节点进行网络编码，充分性得证。

　必要性证明：假设有数据流能够在节点 c 处进行网络编码，则对于任意一条数据流，对其余数据流均存在下游节点能从编码包中恢复出原始数据包，那么节点可以通过侦听其余流发送的数据包，即，或数据流本身含有效原始数据包，即。若节点能够最终解码出原始数据包，必然满足，即定理 1 满足条件，必要性得证。

　引理 3.1 根据数据流之间的拓扑关系来判断编码机会，定理 3.1 条件(1)沿用了该拓扑关系判断交叉节点潜在编码机会，但该条件并不能判定潜在编码机会存在有效性，因多流之间会存在干扰，造成节点对编码机会误判，使得生成的编码包无法被解码。定理 1 的条件(2)通过添加限制，对具有潜在编码机会的节点再一次验证，判断在该节点产生的编码包能否在下游节点完全解码，从而确保编码机会的有效性。

　定义 3.1 多流干扰：若存在多条数据流相交于节点 c，当新数据流相交于节点，使得节点产生的编码包无法在节点完全解码出原始数据包。

　如图 3.1 所示，新流加入到现有流当中，在节点进行网络编码，由于侦听消息的不完备导致数据流的下游节点或目的节点无法解码出原始数据包，即数据流和之间存在干扰。相比图 3.3 中流的传输增加了一跳，使得目的节点能够侦听到发送的原始数据包，成功对编码包解码，即。

　图 3.3 多流无干扰图 3.3.2 路由发现

　路由发现过程是路由开启的第一阶段，源节点通过路由发现过程收集用于决策的有效信息，从而获得数据流的传输路径集。该过程主要可以分为路由请求阶段和路由应答阶段，接下来将对这两个阶段进行详细介绍：

　1．路由请求阶段 在无线多跳网络中，当某个源节点需要向目的节点发送数据时，首先查看本地路由表是否记录有到达指定节点的传输路径，若有对应的传输路径则直接传输，否则源节点通过广播方式发送路由请求 RREQ 数据包，当中继节点接收到 RREQ时，为避免路由产生循环，中继节点需要对 RREQ 进行重复检测，可根据 RREQ的 ID 检测是否存在重复接收，若 RREQ 曾经到达该中继节点，则将该 RREQ 丢弃。否则检查中继节点是否为 RREQ 的目的节点，如果中继节点不是 RREQ 目的地，中继节点将其地址附加到 RREQ 的路由记录并转发 RREQ，直至 RREQ到达目的节点。该 RREQ 的消息结构如图 3.4 所示。

　图 3.4 RREQ 消息结构 2．路由应答阶段 图 3.5 RREP 消息结构 当目的节点接收到 RREQ 数据包时，会根据其记录的消息生成对应的路由应答RREP 数据包，然后将 RREP 沿着 RREQ 所记录的路径以单播形式反方向传输至源节点。在传输的过程中，每当中继节点接收 RREP 时，RREP 会记录该节点的自身信息、流信息和邻居信息。RREP 主要的消息格式如图 3.5 所示，其中“中继节点信息”包含“中继 IP”和该节点输出数据包。“流信息”包括“流的数量”和“流的 ID”。“邻居信息”记录了该节点的“邻居数量”、“邻居 ID”和从邻居侦听到的数据包信息。当 RREP 数据包传回源节点时，源节点通过编码节点判断算法检测路径中每个交叉节点的编码机会，该算法的伪代码如表 3.1 所示。

　表 3.1 编码节点判断算法伪代码 源节点根据该算法得出的检测结果生成一张路由状态表，如表 3.2 所示。该表为图 3 中流路由应答后生成的路由状态表。从表 3.2 中可以看出，源节点到目的节点有三跳距离，该路径顺序为。每一个节点都对应着各自的邻居信息、流的状态和编码节点的判定结果。经过节点的数据流有两条，说明该节点具有潜在的编码机会，是否存在有效的编码机会需要根据收集的相关信息进一步判定，其中表

　3.2 中“编码节点”的状态为该节点根据收集的信息确认后的结果。可通过编码节点判断算法判断节点是否为存在有效编码机会的节点。

　如表 3.2 所示，流的 RREP 包记录的路径为。为源节点，“编码节点”域置为NULL。转到下一跳节点，经过该节点的数据流有，则，该节点为具有潜在编码机会的交叉节点。但需要进一步验证该编码机会的有效性，查看该节点所侦听到的数据包，若数据包的类型有编码包类型，可以预判出该节点在其他路由中的上游节点传输数据流的过程中可能产生编码包发送至节点，如果进一步编码可能会产生多流干扰。所以，通过查看节点发送的数据包类型和节点的下游节点侦听的数据包当中是否含有该节点发送的数据包。在多流情况下，该节点输出数据包的结果可分为两种形式：一种是原始数据包，表示为。若接收的是，说明在该节点处已进行了解码操作，在该节点处仅存储转发。另一种是编码包，表示为。若接收到的是，说明接收到的数据包没有进行完全解码或部分解码。RREP 记录的节点发送的数据包类型为，并且能够在节点侦听信息中检索到数据包，即可推断在传输数据流时，与数据流进行网络编码的数据包均能在下游节点侦听到，有助于完全编码，使得目的节点能够接收到，即节点存在有效的编码机会，“编码节点”域置为 T。同理，依次检测下一个中继节点。为目的节点，“编码节点”域置为NULL。

　路由发现过程的具体流程图如图 3.6 所示。

　图 3.6 路由发现流程图 3.3.3 路由度量 在路由发现过程之后，源节点根据 RREP 产生多条到达目的节点的路径。在选择路由路径的过程中，需要根据路由度量选择合适的传输路径。本文所采用的路由度量主要考虑了编码节点带来的编码增益和非理想状态下链路传输质量两种因素，从路径集中选取编码增益最多且链路质量最好的传输链路。

　1．编码增益 根据接收的多个 RREP 数据包可以得出可用路由集合 R，令为路由集合中的任意一条可用路由。对于任意路由由多条链路组成，设未采用网络编码的路由的总传输次数()为：

　其中，表示该路由源节点到目的节点的跳数，表示路由中第条链路，表示路由中第条链路在未采用网络编码情况下发送节点需传输数据包的个数。总传输计数为

　路径中的各节点传输数据包的传输次数之和。当路由中存在编码节点，那么所有编码节点传输数据包的总传输次数()为：

　其中，表示路由的编码节点，m 为编码节点的个数，表示路由中编码节点在未采用网络编码情况下需传输数据包的个数。对于编码节点，表示编码节点允许不同数据包编码在一起的个数。对于路由，编码节点所能带来的编码增益()为: 2．链路质量 传统方案中以最短距离作为路径选择的衡量指标，但在实际无线网络中，数据传输的质量受通信距离影响，当节点间的通信距离超出一定范围时，数据传输会产生丢包现象。因此，当源节点和目的节点确定的情况下，跳数越少的路径每跳链路的距离就越长，通常相应链路上丢包率可能会增加，从而影响整条路径的传输性能。如图 3.7 所示，节点向节点发送数据包，节点之间距离远，链路的丢包率可能偏高，而节点之间距离近，链路的丢包率相对较低。若按照跳数的数目来选择最佳路径，则会选择节点、和构成的路径，但该路径的丢包率可能较高。而选择节点和组成的路径，则路径传输质量相对较高。因此，按跳数选择路径并非最优[40]。

　图 3.7 链路质量示意图 根据上述分析，假定路径中的每条链路传输质量不同，那么整条路径成功传输一个数据包的总期望传输次数()为: 其中表示链路的丢包率，那么该链路成功传输一个数据包所需要的平均传输次数为。当传输个数据包的期望传输次数为：

　存在丢包情况下的路由编码增益为：

　对于路由，其路由度量 RM 为：

　3.3.4 路由选择 源节点经过路由发现过程可获得传输路径集，为了路由具有良好的传输效率，源节点需要从中选择最优的传输路径。该路由选择根据不同情况对传输路径逐步筛选，其具体步骤如下：

　步骤一：当 RM 都不等时，源节点选择 RM 值最小的传输路径。

　步骤二：当 RM 相等，总链路质量 L 不等时，源节点选择总链路质量最优的传输路径。

　步骤三：当 RM 相等，总链路质量 L 相等，跳数 hop 不等时，源节点选择跳数最短的传输路径。

　步骤四：当 RM、L 和 hop 都相等时，源节点任意选择其中一条传输路径。

　在该策略中，对每一个参数进行了逐层的筛选是为了确保选择结果的唯一性。该路由选择算法伪代码如下：

　3.4 仿真实验及结果分析 3.4.1 实验环境设置 本次实验的网络拓扑由 50 个节点构成，工作方式为混杂模式，设信道容量为200Kbit/s，数据流的平均速率为 50kbps。其中，传输的数据包大小为 1000B。本文将对COPE、DCAR、DGCDR以及本文提出的CRSMI方案进行仿真实验对比，比较性能指标为平均端到端时延、网络吞吐量和编码率，为减小实验误差，各性能参数最终值为多次运行结果的平均值。

　3.4.2 实验结果分析 端到端的平均时延定义为源端到目的端传输数据所需的平均时延。如图3.8...