无线网络中编码感知路由算法的研究

网络编码改变了传统通信方式，允许节点对接收的不同数据包进行编码转发，增加节点单次传输的数据量。研究证明网络编码能有效提高网络吞吐量。在无线多跳网络中，鉴于网络编码的优势，将网络编码技术与路由传输相结合，提高路由传输效率。但研究人员发现传统基于网络编码的路由算法并不能充分发挥网络编码的优势，其原因为网络性能的提升取决于网络中编码机会被利用的数量。因此，编码感知技术被提出，该技术能够主动探索无线多跳网络中的编码机会，将编码机会作为路由选择的衡量标准，从中选取编码机会较多的传输路径。本文将无线多跳网络中的编码感知路由算法为研究核心，充分了解编码感知路由算法的背景知识及意义，掌握编码感知原理并归纳总结现有编码感知路由算法的特征。在此基础上，本文的主要工作将从以下两个方面展开研究：无线多跳网络随着无线通信业务的普及，无线通信技术被广泛应用，给人们日常生活带来了便捷。传统无线通信依赖预设的网络设施，不能够满足移动性要求高的应用场景，例如军事作战、火灾现场、科研考察等相关工作。因此无线多跳网络(WirlessMulti-hopNetwork,WMN)在这些场景中得到广泛的应用。在无线多跳网络中，被人们所熟知地主要有无线自组织网络[1-2]、无线传感器网络[3-4]和无线网状网络[5-6]。这些网络有个共同地特点：网络组建不受外界限制，且能快速组建成一个完整地网络，每一个节点独立运行，互不干涉，且都具有报文转发能力，呈现出去中心化形式。相对于传统网络，无需对中心节点进行设置，使得网络更具灵活性。若该网络中的一个节点发生故障，通过调动其他节点迅速恢复通信，不会影响该网络的性能。尽管无线多跳网络易组织，移动性强，但相比有线网络存在如多径效应，信道冲突，信号衰落，通信盲区等局限，影响无线网络传输性能。与此同时，用户对无线网络业务通信质量要求越来越高，在网络服务多样化的时代，如何提高网络的吞吐量，确保网络传输的可靠性，充分利用网络资源等相关问题已成为当今研究的热点。网络编码[7](NetworkCoding)在此背景下应运而生，大量理论证明网络编码能够达到“最大流-最小割”容量。且网络编码技术在提升网络的吞吐量，改善负载均衡，减少传输能耗，增强网络健壮性等方面有明显的优势[8-10]。网络编码改变了传统路由通信的“存储--转发”模式，使得通信节点具有“编码--转发”的能力，通信节点可将接收的多个数据包编码，然后送至下游节点，下游节点通过缓存的数据包解码出原有数据包，有效减少了传输时间，减轻了各条数据流竞争干扰，提高了网络吞吐量。可以得出，网络编码技术在无线多跳网络中具有一定优势，越多的数据编码可获得更多的编码增益。因此，如何打破编码机会数量的限制，发现更多有效的编码机会，是目前重要的一个研究方向。研究发现，传统的基于网络编码的路由协议仅根据邻居节点缓存数据包的情况对接收的数据包进行被动的网络编码，不能够充分发挥网络编码优势[11-12]。因此简单地将网络编码和路由协议结合是不可取的。需要重新考虑网络编码和路由协议之间的合理设计。在2006年Ni等人第一次提出编码感知路由协议[13](RoutingwithOpportunisticCodedexchange,ROCX)，将编码增益作为选择路由的标准，将主动寻找编码机会较多的节点作为转发节点，克服了传统路由对网络编码的限制。综上所述，编码感知路由能够发现无线多跳网络中的编码机会，在一定程度上能提升传输有效性。但在已有的编码感知路由方案中，大多数进强调增加编码机会，将编码机会作为路由衡量的唯一标准，导致部分编码机会无效，尤其在多流环境下，使得数据流之间干扰加剧，鲁棒性降低。因此，在寻找更多编码机会的同时，如何避免干扰来提升编码机会的有效性，有待继续深入研究。此外，在时变网络中研究如何提高路由的鲁棒性，在增加吞吐量的同时降低时延具有一定的实际意义。1.2国内外研究现状传统网络中，网络节点一般采用“存储—转发”模式处理数据，并认为数据在中继节点上不进行任何操作，仅作为转发器对数据的传输不带来任何增益。文献[7]中首次提出网络编码概念，网络编码的提出打破了传统传输模式，允许编码节点对所在链路上接收的多个数据包进行编码再转发到下游节点，该方式能有效减少传输数据包的次数，从而提高网络吞吐量。相关研究证明，在理想的条件下，网络编码可使通信传输达到最大流传输的理论上界[14]。文献[15]在此基础上提出了线性网路编码(LinearNetworkCoding，LNC)，其核心思想是网络中间节点对从各个链路中接收到的数据包进行编码操作，且从有限域上选取编码向量对数据进行加乘操作，然后转发编码包，目的节点根据无关向量从编码包中恢复所需数据包。文献[16]提出随机线性网络编码(RandomLinearNetworkCoding,RLNC)，该方法根据节点的输入输出信息之间的映射关系，从伽罗华域中随机选取编码系数对数据包进行编码，目的节点通过高斯方程从编码包中恢复所需要的数据包。文献[17]提出机会式网络编码(OpportunisticNetworkCoding,ONC)，机会式网络编码采用异或运算对两个或两个以上的数据包进行编码，编码系数为0或1，目的节点根据已接收的数据包和编码包进行解码。相比线性网络编码，机会式网络编码的编解码运算较为简单，如何选择有效编码包，减少数据包的传输次数是关键。早期网络编码相关研究假设在理想状态下进行。近年，一些学者将网络编码技术应用于无线多跳网络中，并将网络编码与路由协议相结合，以提高路由传输数据的性能。随着研究的不断深入，发现网络中的节点可以根据所在网络的拓扑结构以及周围邻居节点信息对自身网络编码能力作出预判，优先考虑具有网络编码能力的中继节点来传输数据，充分发挥网络编码的优势。因此，在路由创建过程中，需将节点是否具有编码能力作为路由选择的标准，对如何主动寻找网络编码机会，并综合考虑其他影响因素来提高路由性能是根本问题。现有编码感知路由协议中，主要可以分为两种类型路由：按需式编码感知路由和机会式编码感知路由。1.按需式编码感知路由按需式编码感知路由又名确定性路由，在该类路由中源节点发送数据之前，需要先执行路由发现过程，在此过程中通过将编码机会作为路由衡量的标准，选择编码机会较多的传输路径。确定传输路径后，源节点根据筛选出的传输路径发送数据包。文献[17]提出一种基于网络编码的无线路由体系结构，编码机会实体(CodingOpportunityEntity,COPE)。其中给出了四种经典的单跳编码结构，包括链结构、“X”型结构、交叉结构和轮结构，通过机会侦听数据包来帮助编码包解码，并设计了一种链路质量度量(LinkQualifyMetric,LQM)来选择高质量的转发节点。该方案的编码结构仅限于两跳范围之内，导致两跳以外的编码机会缺失。文献[18]指出COPE和ROCX存在编码机会利用不充分的问题，提出一种分布式编码感知路由(DistributedCodingAwareRouting,DCAR)，该方案将编码机会的搜索范围从两跳扩展到了多跳范围，给出了多跳网络编码条件(Multi-hopNetworkCodingCondition,MCC),有效增加了编码机会的数量。同时，DCAR将节点队列缓存数据包的数量作为路由度量(Coding-awareRoutingMetric)，选择合适的传输路径。文献[19]提出一种联合编码感知路由(NetworkJointCodingAwareRouting,NJCAR)，允许编码节点的下游节点对编码包不一次性完全解码，可以通过分步对编码包进行解码，提高了编码包的解码效率，但计算复杂度较高。文献[20]针对现有编码条件不能准确的识别编码机会，提出一种通用的编码条件(GeneralNetworkCodingCondition,GCC)和以免费搭载其他数据流为导向的路由度(Free-ride-orientedRoutingMetric,FORM)，系统分析了可能的编码场景，并开发了一种编码图以实现条件，通过编码流选择过程来检测每个编码节点的编码能力，使得新数据流可以免费搭载现有的数据流，减少传输次数。文献[21]针对多流情况提出了一种分布式贪婪编码感知确定性路由(DistributedGreedyCoding-awareDeterministicRouting,DGCDR)，将多条数据流进行编码，同时考虑到多流编码可能存在干扰问题，通过增加额外的路由过程来检测编码机会的有效性，在一定程度上有效提高了网络吞吐量。文献[22]分析了DCAR类型的方案在检测更多编码机会时，可能存在网络负载不均衡，针对该缺点提出了一种约束编码感知路由机制(ConstrainedCoding-AwareRoutingScheme,CCAR)，通过约束编码条件检测良好的编码机会，根据定制的“路由+编码”发现过程计算输出队列长度，评估编码节点的状态。2.机会式编码感知路由机会式编码感知路由发送数据前无需先确定传输路径，发送数据的每一个节点通过计算与各邻居节点之间编码机会概率，选择编码增益最大的节点作为下一跳接收节点，然后编码数据包并广播编码包至该邻居节点。文献[23]提出了典型的机会式编码感知路由机制(Coding-awareOpportunisticRoutingMechanism,CORE)，通过将逐跳机会转发和流间网络编码相结合，允许节点从邻居节点集中选择编码增益最大的节点作为下一跳节点，该方法总是具有最大的编码增益，从而提高了单次传输的数据量。机会式编码感知路由对动态网络更具有适应性，但机会式路由对下一跳的选择计算较为复杂，可能产生较多的计算开销。文献[24]提出一种基于队列状态和局部拓扑的增强型编码感知路由算法(AnEnhancedNetworkCoding-awareRoutingAlgorithmbasedonQueueStateandLocalTopology,OQMCAR)，该方案考虑了节点编码数据包的队列状态，在每一次机会传输中，采用基于队列长度的阈值策略，对数据包进行有效的“传输或等待”决策，而不非现有的感知编码路由算法中使用的机会编码策略。文献[25]提出一种高效的基于网络编码的背压调度算法(AnEfficientNetwork-codingbasedBack-pressureSchedulingAlgorithm,NBP)，背压调度被认为是无线多跳网络中有效的资源分配策略，该方案将背压调度与网络编码相结合，能够有效应对动态拓扑，确保传输的稳定性。文献[26]提出一种网络拥塞避免编码感知路由方案(Congestion-AvoidanceNetworkCoding-AwareRouting,CANCAR)，该方案考虑了拥塞强度和数据流编码成功的实测信息，将编码不佳的数据流在网络瓶颈处重新路由，在变更过的路由路径上创造编码机会。能有效地将网络中负载最重的部分从编码最少的流量中释放出来，使得最大的负载节点处的编码流获得更高的编码增益。根据现有的按需式编码感知路由，大多数方案一味地追求探索更多的编码机会，而忽视编码机会的有效性。这与编码机会判断条件的不合理性有关，复杂网络中多条数据流进行编码在一定程度上能够增加编码机会的数量，但这些编码机会中可能存在一些因干扰而失效的编码机会，导致生成的编码包不可解，从而影响无线多跳网络的传输性能[27]。此外，按需式编码感知路由的数据传输是建立在可靠传输路径上，但在时变网络中按需式编码感知路由的稳定性容易受此影响[28]。因此，如何获得更多编码机会的同时确保编码机会的合理性，且有效应对网络拓扑变化提高传输效率，具有重要的研究价值。1.3研究主要内容与目标本章分析了网络编码与编码感知路由的特点，在现有研究成果基础上，对编码感知路由在无线多跳网络的应用进行深入的研究，主要以编码感知路由在多流环境中如何寻找更多编码机会，避免多流干扰提高编码包的解码率，提高编码感知路由在动态网络的适应性，减少数据包的传输时延和提高网络吞吐量为研究目标，提出了解决多流干扰的编码感知路由算法(Coding-awareRoutingtoSolveMulti-flowInterference,CRSMI)和一种基于背压策略的编码感知路由算法(CodingAwareRoutingbasedonBack-pressureStrategy,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-hopCodingStructure,SCS)。SCS结构规定节点生成的编码包仅能一跳传输，必须在编码节点的下一跳节点中被立即解码，该编码结构的编码机会被限制在一跳范围内。根据节点有无侦听机制，SCS编码结构可继续分为单跳无机会侦听编码结构(Single-hopCodingStructurewithoutOpportunisticOverhear,SCS-O)和单跳有机会侦听编码结构(Single-hopCodingStructurewithOpportunisticOverhear,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-hopCodingStructure,MCS)，允许编码节点产生的编码包在两跳以外的节点进行解码，将编码机会的搜索扩展到两跳范围，相比SCS编码结构，MCS能够寻找到更多的编码机会。如图2.6所示，假定有两条数据流f1，f2相交于节点R，距离节点R两跳的下游节点D2接收到编码包P1⊕P2，节点D2通过机会侦听机制从节点S1侦听到数据包P1，节点D2通过侦听到的P1数据包可以解码出数据包P2。根据上述描述，MCS结构可形式化的表示为：图2.6多跳编码结构(3)联合编码结构文献[19]给出了联合编码结构(JointCodingStructure,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.感知时机对于现有的编码感知路由对编码机会的感知时机，可分为两类：按需式编码感知路由和机会式编码感知路由。按需式编码感知路由是指网络中的源节点节点与其他节点建立通信时，源节点发起路由发现过程，寻找一条可用的传输路径来发送数据。该类型路由的编码感知时机在路由发现过程中，其过程主要分为路由请求和路由应答两个阶段，源节点发送多个路由请求(RoutingRequest,RREQ)数据包向目的节点传输，RREQ数据包每经过一个节点便将该节点信息和编码机会情况记录在RREQ数据包中，若中继节点重复接收RREQ数据包，则将其丢弃，防止形成环路。当多个RREQ数据包到达目的节点时，目的节点根据RREQ数据包中记录的信息生成路由应答(RoutingReply,RREP)数据包，按照RREQ数据包的路径原路返回。源节点从多个RREP数据包获得多条传输路径，根据路由度量对多条路径进行筛选，从中选取编码增益最多的传输路径。该类型编码感知路由适合较为稳定的网络场景。机会式编码感知路由是指网络中的源节点发送数据前无需先与目的节点建立确定传输路径，源节点将邻居节点纳入节点转发集中，在确定节点转发集后，将数据发送至转发集中的各节点，根据编码机会带来的编码增益确定各节点的转发优先级。一般情况下，编码增益越高节点的转发优先级越大，则优先级最大的节点优先对数据包编码并转发。因此，机会式编码感知路由的编码感知时机在选择转发节点阶段，该类型路由适用于无线时变网络，其原因为无线信道的时变性和节点的移动性，导致无线网络中的传输链路质量不稳定，机会式编码感知路由能够根据网络的实时情况选择链路状况较好的来传输数据。2.3路由度量定义路由度量是用来衡量链路选择的一个指标，根据不同的网络场景，路由度量考虑不同的因素选择合适的传输路径。由此可见，路由度量的设计对路由策略有着至关重要的作用。现有主流的路由度量有以下几类：1.最小跳数最小跳数(MinimunHops,MH)是指源节点传输数据包至目的节点所经过节点最小数量。在选择路径时，路由决策会选择路径中节点个数最小的链路作为传输路径。该路由度量是从有线网络发展至无线网络，在传统路由中较为常见，其内部算法为熟知的Dijksta算法或线性规划算法，计算方便简单。2.期望传输次数期望传输次数(ExpectedTransmissionCount,ETX)是指源节点向目的节点发送数据总共需要的传输次数[35-36]。在实际无线多跳网络中，无线信道会因受到外界因素而产生丢包情况。因此，信道质量是需要考虑的重要因素。假定无线网络中任意两个节点之间的链路为，链路的丢包率为。当链路(a,b)经过n次尝试成功传输数据包的概率为s(n)，其公式如下：那么链路成功传输数据包所需要的期望传输次数可表示为：由此可见，丢包率越小ETX的值越小，链路传输数据的效率就越高。因此在选择链路时，应选择预期传输次数最少的链路。3.期望传输时间期望传输时间(ExpectedTransmissionTime,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.4RREQ消息结构2．路由应答阶段图3.5RREP消息结构当目的节点接收到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所示，四种方案整体的平均端到端时延随着数据流的数量增多而增大。当数据流的数量小于5时，CRSMI和DGCDR的平均端到端时延要高于其他两种方案，其因为该情况下数据流之间存在的编码机会较少，几乎不存在干扰问题，因此路由发现过程中的多流干扰检测会带来较多的基础时延。随着数据流条数的增加，CRSMI的传输时延逐渐低于其他三个方案。其因为编码机会随着数据流的增加而增多，多流之间干扰逐渐明显，本方案通过多流编码条件降低多流干扰，并选取链路质量最优且具有较高编码增益的路径传输数据包。DCAR和COPE在寻找编码机会时不能避免多流干扰问题，导致部分编码包不可解而被丢弃，使得传输时延增高。而DGCDR通过额外的路由过程来避免干扰，导致部分时延产生。图3.8端到端平均传输时延网络吞吐量定义为单位时间内目的端接收数据的总量。如图3.9所示，随着数据流的增加，CRSMI的网络吞吐量逐渐大于其他三种方案。因CRSMI根据多流编码条件（定理1）判断节点的编码机会，从中选取有效编码机会，能够确保编码节点产生的编码包在下游节点有效解码，避免多流干扰所造成的不可解编码包问题，有效提高网络吞吐量。如图8所示，CRSMI的传输时延优于DGCDR，因单位时间内能接收更多的数据包。相比DCAR和COPE，为增加编码机会忽略编码数据包的合理性，直接影响编码性能。图3.9端到端平均吞吐量图3.10不同丢包率的编码率与有效编码率如图3.10所示，四种方案在不同的丢包率下的编码率和有效编码率对比。其中，编码率定义为编码包数量与传输的所有数据包数量的比值，有效编码率为可解码编码包数量与传输的所有数据包数量的比值。如图3.10(a)所示，随着丢包率的增加，本方案编码率的总体趋势高于DCAR和COPE这两种方案，因本方案考虑了链路质量对系统性能的影响，在路由选择的过程中回避了链路质量较差的链路。在丢包率为2%的情况下，本方案的编码率相对于DCAR较低，但有效编码率高于DCAR。如图3.10(b)所示，因为DCAR筛选的编码机会存在失效问题，本方案在路由发现过程中，通过编码节点判断算法排除了部分伪编码机会。COPE将编码机会限制在两跳的范围之内，所以该方案的编码率较低。与DGCDR相比，CRSMI的编码率和有效编码率略低，其因为CRSMI在路由应答阶段后，源节点根据收集的信息只对编码机会进行判断检测，而DGCDR通过路由检测和路由确认两个阶段对编码机会进行实时验证，因此CRSMI在传输数据包时可能会受丢包影响，但总体差距不大。根据以上对时延和吞吐量的实验分析，CRSMI的整体系统性能相对其他三个方案有所提升。3.5本章小结本章分析了现有编码感知路由方案，发现其在寻找编码机会方面存在局限性，在多流场景下编码节点容易受到其他数据流的干扰，造成编码包不可解。为解决该问题，本文提出了介绍了解决多流干扰的编码感知路由方案。首先定义了多流编码条件，对多流之间的编码机会严格筛选，确保生成的编码能够完全解码。其次，根据所提的多流编码条件，设计了编码节点判断算法，利用路由发现过程收集的有效信息检测路径中交叉点的编码机会是否符合多流编码条件。在路由度量方面综合考虑了编码增益和链路质量等因素，通过路由选择算法逐步筛选路径。仿真实验结果表明，CRSMI相比其他方案，能有效避免多流干扰，提高了有效编码率。在多流环境下，本方案的吞吐量和传输时延皆有优势。第4章基于背压策略的编码感知路由算法研究4.1引言编码感知路由具有主动探索编码机会的特点，当路由中的节点发送数据包前通过将编码机会作为路径选择的标准，优先选取编码机会较多的路径，然后根据路有度量对多条传输路径进行考量，从中选择最佳的传输路径。经过研究发现，在现有的编码感知路由中，多数方案的设计倾向于固定的传输路径和静态数据流。对于这种“静态”设计的路由，将其称之为按需式路由。该类型路由在时变网络中容易受到拓扑结构和动态数据流的影响，导致按需式路由频繁的进行路由发现过程，从而增加了编码感知路由整体消耗的时延，降低了路由在时变网络的吞吐量。对于上述按需式编码感知路由在时变网络中健壮性不足等问题，文献[23][25][41-42]考虑了机会式路由可以增加编码感知路由在时变网络的灵活性。其中文献[9]介绍了一种背压调度策略，该策略是一种动态调度方法，根据无线多跳网络中的拥塞梯度，将数据包推入到拥塞较小的接收节点中，从而获得网络排队的稳定性。基于这一优点，本文试图将背压策略融入到编码感知路由当中，来提高编码感知路由的灵活性和吞吐量，同时考虑到原始背压策略仅根据两个节点队列梯度差作为数据流导向的标准，不能够满足时变网络对延迟性能的要求，所以本文对背压策略和编码感知路由结合的同时需要做进一步的改进。为了提高编码感知路由在时变网络的灵活性、吞吐量，减少路由传输数据包的时延，本文提出一种基于背压策略的编码感知路由算法BCAR，在做路由决策时，综合考虑了编码机会、队列梯度和队列中数据包的积压时间等因素，通过链路权值计算公式对这些因素进行计算，选择权值最大的链路来转发数据。该算法实现了编码感知路由在时变网络的稳定性的同时，提高了网络吞吐量并减少了数据包的传输时延。4.2问题描述在时变网络中，经常发生节点的接入和退出操作，有关静态设计的路由对该网络较为敏感。如图4.1(a)所示，节点A中无编码机会时，流的最佳传输路径为。当节点A存在无编码机会时，流选择与流编码来提高传输效率。但是，当节点A退出网络，不再转发数据时，对于静态路由将重新开启路由发现过程。因此，在时变网络中，侧重于静态设计的路由将频繁的开启路由发现过程，会加大路由的时间开销。对于路由而言，其鲁棒性是不可忽视的问题。图4.1问题描述示意图4.3系统模型对于一个无线多跳网络可以用表示，其中N表示网络的节点集合，L表示网络中的链路集合。网络中的节点可以是移动或是静止，节点间的通信为双向通信。在无线多跳网络中，数据包的传输可能需要中继节点的协助来完成，每一个节点都发挥着路由和调度的作用，且每个节点针对不同数据流都有独立的缓存队列。假定时隙时，节点向节点定向发送数据，节点与节点之间的链路由表示，令表示链路的传输速率，当时，说明节点与节点之间不存在链路。当链路传输数据流时，令其传输速率为。为了方便观察，本文主要涉及到的符号名称如表4.1所示表4.1符号表符号 定义 网络的节点集合中任意一个节点 时隙时，节点的缓存队列中数据流的缓存容量 时隙时，节点与节点之间数据流缓存容量的差值 时隙时，链路中数据流的传输速率 节点中队首数据包的入队时间 流编码进流的数据包的数量 时隙时，链路传输的编码流带来的总编码增益 时变网络中可调度链路集合 时变网络中可用传输速率集合4.4背压策略简介文献[43]中证明了背压策略在时变网络中为吞吐量最优的算法。该算法主要考虑节点队列中数据包的积压量和传输链路的传输速率。算法过程可以分为节点之间的积压差计算和最大权值链路选择。在无线多跳网络中，数据流的传输是根据节点间的积压差作为导向，从一个节点传输到另一个节点，相应的从第一个节点中删除并添加到另一个节点中。传统的背压算法执行过程可分为以下三个步骤：1．链路权值的计算在网络中任意一条路径，在时隙时，节点的队列积压为，节点的队列积压为，节点之间的队列积压差如公式(4.1)所示，其积压差为正整数。从所有的积压差中选择最大的积压差作为链路的权值，如公式(4.2)所示。2．可调度链路的选择链路的传输速率也是不可忽视的一部分，通过公式(3)进一步筛选，选择最优的传输路径。其中表示最优可调度路径，表示时变网络中时隙时可调度链路集合，表示时变网络中时隙时可用传输速率集合。3．数据传输根据步骤2得出的最优的传输路径，在时隙时，将数据流从节点a传输至节点b。从以上步骤可知，传统的背压策略路由发送数据包是根据两个节点之间队列积压的差值来做决定的。其优点有三个方面：(1)算法易操作，不受未知传输速率和未知拥塞状况的影响。(2)对于时变网络更具有鲁棒性。(3)可实现系统吞吐量的最大化。对于网络中存在拥塞程度高的节点，该算法能够有效避免这类节点，将数据包发往拥塞程度低的节点。所以，当网路负载程度较高时，有助于提高系统吞吐量。但当网络负载程度较低时，路由调度会因积压差值不够明显，不足以发挥背压策略的优势，导致路由传输过程较长，增加了数据包的传输时延。此外，在无线多跳网络中，传统路由通信模式为时刻允许节点仅能发送或接收一种类型的数据包，且该节点不能同时与其他节点通信[44]，这一模式使得系统吞吐量和传输时延的优化有一定的局限性。流间网络编码恰好能够解决这一问题，因为流间网络编码允许节点对不同数据流的数据包进行网络编码，将生成的编码广播出去，这样便能减少了不同数据流排队等待时延，从而提升系统吞吐量[45-46]。为了进一步提高系统性能，本章结合了背压策略和流间网络编码的优势，设计一种基于背压策略的编码感知路由算法，在传统背压策略的模型上作进一步优化，增强编码感知路由在时变网络中的鲁棒性，进一步提升系统吞吐量。4.5基于背压策略的编码感知路由算法设计在无线多跳网络中，为了增加单次传输的数据量，允许每个节点对接收各流的数据包做合理的网络编码。如图4.1所示，假定时刻，节点接收到节点发送的数据包，时隙时，节点若无网络编码操作，只向节点传输数据包，若发生网络编码操作，链路(a,c)、(a,d)和(a,e)发送的数据包可编码进链路(a,b)发送的数据包中，节点a通过广播形式向各接收节点发送编码包，在时刻的调度中，相比无网络编码，节点a的缓存队列可以释放更多的缓存空间。图4.2传输过程为了方便表示，假定链路(a,b)传输数据流，链路(a,c)传输数据流，链路(a,d)传输数据流，链路(a,e)传输数据流。根据背压策略可知，在节点a中时隙时，每条数据流对应的积压差为、、和。当发生网络编码时，将链路(a,c)中的数据流编码进编码进链路(a,b)发送数据流中，其编码增益可表示为，即节点a向节点b发送数据流的同时能够免费搭载数据流的数据包的个数。假定t时刻有多条数据流编码进链路(a,b)发送数据流中时，总的编码增益如公式(4.4)所示，其中表示数据流属于数据流集合。对于链路(a,b)，t时刻节点a总共可以释放的队列容量如公式(4.5)所示。在上述说明中，指定了图4.1中的节点a为编码节点，当多条数据流存在时，节点a不能一味地将所有数据流编码在一起，其原因为该操作会导致产生的编码包在部分节点中无法解码。本文采用编码机会图的形式对该问题进行优化，尽可能多的将存在编码机会的数据流编码在一起。在编码机会图中，如果存在完全子图，那么这个子图中的顶点(流)可以编码在一起。这个过程类似于寻找最大团问题，该问题是一个NP完全问题[18](Non-deterministicPolynomialcomplete,NP-complete)。经过研究证明，多流情况下，一个节点能够编码的流数很少，不足以影响到计算开销[47-48]。对于数据流之间编码机会的判断，通过机会侦听的方式侦听节点a的邻居节点中缓存数据包的情况，节点a根据侦听的信息判断数据流之间是否存在编码机会，然后临时生成一个矩阵，用于表示各数据之间的编码机会。具体编码机会判断过程如图4.2所示。图4.3编码机会判断过程时隙t时，假定节点a生成的临时矩阵为图4.3(a)，其中1表示两条数据流之间存在编码机会，0表示两条数据流之间不存在编码机会。为方便观看，将标识为1的两条数据流相连，最终结果如图4.3(b)所示。令表示能和数据流一起编码的数据流集合，根据图4.3(b)可知，，其中数据流可以和一起编码，或者和编码。具体和哪些数据流编码需要根据公式(4.4)计算出总编码增益，选择编码增益最大编码组合。总编码增益的伪代码见表4.2，由于一个节点能够编码的流数很少，所以最大团的数量几乎为1，则该算法的时间复杂度为(n)。图4.4编码节点a的编码机会图在网络负载较低或适中的环境下，传统背压策略路由传输时延收敛效率不容乐观[49-50]，因为背压策略传输的数据包在该网络环境下会长时间的游走，多次经过重复的传输路径，甚至会出现路由环路，直到路由中出现合适的数据积压梯度才能使数据包到达目的节点。因此，本方案考虑队列积压差的同时还考虑数据包在队列中最大积压时间，来减少数据包在网路中逗留时延。如图4.4所示，节点a中数据包的缓存数量分别为，节点b中缓存的数据量分别为。计算可知，节点a与节点b之间的数据积压差皆为3()，根据传统的背压策略，从中任选一种数据进行传输。为了减少数据包的逗留时延，节点记录队首数据入队时间，因为队列采用FIFO原则，队首数据为最早进入队列的数据。由此可见，图4.4中节点a数据的入队时间为3，数据的入队时间为5，而当前时刻为12，因此数据积压时间最长，应优先传输。图4.5数据包的入队时间令表示t时刻节点n中数据包P的最大积压时间，其中。表示数据包P的入队时间。那么，时隙t时节点n中数据包P的最大积压时间如公式(4.6)所示。当节点n中存在多条数据流时，需要一个专门的时间容器存储每一条数据流的入队时间，当某个数据流的入队时间发生变化时，可以对该数据流做指定修改。最大积压时间的伪代码如表4.3所示，该算法的时间复杂度为(n)。表4.3最大积压时间计算伪代码当节点选择链路准备发送数据前，需要综合考虑编码增益、队列积压差和个数据流的积压时长等因素来计算每条数据流在链路(a,b)的权重值，如公式(4.7)所示，时隙t时，节点a计算数据流在链路(a,b)的权重，通过考虑其他数据流与数据流c之间的编码增益，将存在编码机会的数据流编码在一起，节点a传输数据时尽可能多的释放队列空间，来减少传输次数，同时考虑不同数据流的积压时间，将积压时间作为一种优先级，若数据流c的积压时间较长，则促使数据流c优先传输，以减少传输时延。当节点a中的每一条数据流的权重值计算完毕时，从中选取权重最大的数据流，如公式(4.8)所示。最后，节点发送数据包需要可靠的可调度链路，基于上述最大的权重值，通过t时刻链路传输速率进一步筛选，如公式(4.9)所示。当链路传输速率和权重值的乘积之和越大，链路(a,b)被作为调度链路的可能性就越大。综上，BCAR方案伪代码如表4.4所示。在该算法中，第二个for循环与计算编码增益中的for循环属于同一个，对于积压差和积压时间运算皆为常数运算，不影响整个算法的时间复杂度，所以该算法的时间复杂度为(n2)。BCAR算法的具体过程如下：1．在时隙t时，任意节点a接收上一跳节点发送的数据包时，首先判断接收的数据包是否是编码包，若是编码包，则将其解码。然后判断接收节点是否为目的节点，若为目的节点，则对解码后的数据包或原始数据包向上层传输进行处理。否则直接存入缓存队列中。2．节点a收集所有邻居节点的信息，并针对每一个邻居节点b，计算节点a与节点b之间的每一条数据流的积压差、编码增益和积压时间。根据这些因素计算节点a与各邻居节点之间传输数据流的链路权重，求出权重最大的传输数据流的链路。3．通过链路速率与各链路的权重的乘积之和，求得可调度链路集合。从中选取调度机会最大的链路，然后将符合编码机会的数据包进行编码，通过选择的链路将编码包发送出去。同时，更新节点a中各数据流的入队时间，保证下一次的判断的正常进行。表4.4BCAR方案伪代码根据上述，网络中的每一个节点在不同时刻都将执行该过程，一个节点的接收与发送过程伴可通过节点队列的添加和删除过程来表示。对于任意节点a的动态变化公式如下：其中，表示t时刻，节点a向其他节点发送数据包的数量，发送数据包的数量最多为节点a的队列总容量。表示t时刻，节点a接收数据数据包的数量。表示t时刻，节点a产生新数据包的数量。4.6仿真结果与分析4.6.1场景设置本章将对DCAR协议和本文提出的BCAR协议进行仿真对比试验，然后对仿真实验数据进行统计，最后根据统计结果对各方案进行比较分析。为减小实验误差，各性能参数最终值为多次运行结果的平均值。本文的实验网络拓扑结构由20个节点构成，网络传输信道设置为200kbit/s，每个节点的缓存队列容量为100个数据包，传输的数据包大小为512bytes。本文将根据不同发包率的情况下，对比DCAR和BCAR之间的编码包个数、平均端到端传输时延和网络吞吐量等性能指标。4.6.2性能分析1．编码包数量编码包数量定义为在这个网络通信中，各流数据包参与编码生成编码包的个数。如图4.5所示，BCAR方案和DCAR方案整体的编码包数量随着发包率的增加而增大。本文提出的BCAR方案相比DCAR方案能够产生更多的编码包，其原因为BCAR允许每个节点发送数据之前