《无线网络中编码感知路由算法的研究.docx》由会员分享，可在线阅读，更多相关《无线网络中编码感知路由算法的研究.docx（34页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、网络编码改变了传统通信方式，允许节点对接收的不同数据包进行编码转发，增加节点单次传输的数据量。研究证明网络编码能有效提高网络吞吐量。在无线多跳网络中，鉴于网络编码的优势，将网络编码技术与路由传输相结合，提高路由传输效率。但研究人员发现传统基于网络编码的路由算法并不能充分发挥网络编码的优势，其原因为网络性能的提升取决于网络中编码机会被利用的数量。因此，编码感知技术被提出，该技术能够主动探索无线多跳网络中的编码机会，将编码机会作为路由选择的衡量标准，从中选取编码机会较多的传输路径。本文将无线多跳网络中的编码感知路由算法为研究核心，充分了解编码感知路由算法的背景知识及意义，掌握编码感知原理并归纳总结
2、现有编码感知路由算法的特征。在此基础上，本文的主要工作将从以下两个方面展开研究：无线多跳网络随着无线通信业务的普及，无线通信技术被广泛应用，给人们日常生活带来了便捷。传统无线通信依赖预设的网络设施，不能够满足移动性要求高的应用场景，例如军事作战、火灾现场、科研考察等相关工作。因此无线多跳网络(Wirless Multi-hop Network, WMN)在这些场景中得到广泛的应用。在无线多跳网络中，被人们所熟知地主要有无线自组织网络1-2、无线传感器网络3-4和无线网状网络5-6。这些网络有个共同地特点：网络组建不受外界限制，且能快速组建成一个完整地网络，每一个节点独立运行，互不干涉，且都具有
3、报文转发能力，呈现出去中心化形式。相对于传统网络，无需对中心节点进行设置，使得网络更具灵活性。若该网络中的一个节点发生故障，通过调动其他节点迅速恢复通信，不会影响该网络的性能。尽管无线多跳网络易组织，移动性强，但相比有线网络存在如多径效应，信道冲突，信号衰落，通信盲区等局限，影响无线网络传输性能。与此同时，用户对无线网络业务通信质量要求越来越高，在网络服务多样化的时代，如何提高网络的吞吐量，确保网络传输的可靠性，充分利用网络资源等相关问题已成为当今研究的热点。网络编码7(Network Coding)在此背景下应运而生，大量理论证明网络编码能够达到“最大流-最小割”容量。且网络编码技术在提升网
4、络的吞吐量，改善负载均衡，减少传输能耗，增强网络健壮性等方面有明显的优势8-10。网络编码改变了传统路由通信的“存储-转发”模式，使得通信节点具有“编码-转发”的能力，通信节点可将接收的多个数据包编码，然后送至下游节点，下游节点通过缓存的数据包解码出原有数据包，有效减少了传输时间，减轻了各条数据流竞争干扰，提高了网络吞吐量。可以得出，网络编码技术在无线多跳网络中具有一定优势，越多的数据编码可获得更多的编码增益。因此，如何打破编码机会数量的限制，发现更多有效的编码机会，是目前重要的一个研究方向。研究发现，传统的基于网络编码的路由协议仅根据邻居节点缓存数据包的情况对接收的数据包进行被动的网络编码，
5、不能够充分发挥网络编码优势11-12。因此简单地将网络编码和路由协议结合是不可取的。需要重新考虑网络编码和路由协议之间的合理设计。在2006年Ni等人第一次提出编码感知路由协议13(Routing with Opportunistic Coded exchange, ROCX)，将编码增益作为选择路由的标准，将主动寻找编码机会较多的节点作为转发节点，克服了传统路由对网络编码的限制。综上所述，编码感知路由能够发现无线多跳网络中的编码机会，在一定程度上能提升传输有效性。但在已有的编码感知路由方案中，大多数进强调增加编码机会，将编码机会作为路由衡量的唯一标准，导致部分编码机会无效，尤其在多流环境下，
6、使得数据流之间干扰加剧，鲁棒性降低。因此，在寻找更多编码机会的同时，如何避免干扰来提升编码机会的有效性，有待继续深入研究。此外，在时变网络中研究如何提高路由的鲁棒性，在增加吞吐量的同时降低时延具有一定的实际意义。1.2 国内外研究现状传统网络中，网络节点一般采用“存储转发”模式处理数据，并认为数据在中继节点上不进行任何操作，仅作为转发器对数据的传输不带来任何增益。文献7中首次提出网络编码概念，网络编码的提出打破了传统传输模式，允许编码节点对所在链路上接收的多个数据包进行编码再转发到下游节点，该方式能有效减少传输数据包的次数，从而提高网络吞吐量。相关研究证明，在理想的条件下，网络编码可使通信传输
7、达到最大流传输的理论上界14。文献15在此基础上提出了线性网路编码(Linear Network Coding，LNC)，其核心思想是网络中间节点对从各个链路中接收到的数据包进行编码操作，且从有限域上选取编码向量对数据进行加乘操作，然后转发编码包，目的节点根据无关向量从编码包中恢复所需数据包。文献16提出随机线性网络编码(Random Linear Network Coding, RLNC)，该方法根据节点的输入输出信息之间的映射关系，从伽罗华域中随机选取编码系数对数据包进行编码，目的节点通过高斯方程从编码包中恢复所需要的数据包。文献17提出机会式网络编码(Opportunistic Netw
8、ork Coding, ONC)，机会式网络编码采用异或运算对两个或两个以上的数据包进行编码，编码系数为0或1，目的节点根据已接收的数据包和编码包进行解码。相比线性网络编码，机会式网络编码的编解码运算较为简单，如何选择有效编码包，减少数据包的传输次数是关键。早期网络编码相关研究假设在理想状态下进行。近年，一些学者将网络编码技术应用于无线多跳网络中，并将网络编码与路由协议相结合，以提高路由传输数据的性能。随着研究的不断深入，发现网络中的节点可以根据所在网络的拓扑结构以及周围邻居节点信息对自身网络编码能力作出预判，优先考虑具有网络编码能力的中继节点来传输数据，充分发挥网络编码的优势。因此，在路由创
9、建过程中，需将节点是否具有编码能力作为路由选择的标准，对如何主动寻找网络编码机会，并综合考虑其他影响因素来提高路由性能是根本问题。现有编码感知路由协议中，主要可以分为两种类型路由：按需式编码感知路由和机会式编码感知路由。1.按需式编码感知路由按需式编码感知路由又名确定性路由，在该类路由中源节点发送数据之前，需要先执行路由发现过程，在此过程中通过将编码机会作为路由衡量的标准，选择编码机会较多的传输路径。确定传输路径后，源节点根据筛选出的传输路径发送数据包。文献17提出一种基于网络编码的无线路由体系结构，编码机会实体(CodingOpportunity Entity, COPE)。其中给出了四种经
10、典的单跳编码结构，包括链结构、“X”型结构、交叉结构和轮结构，通过机会侦听数据包来帮助编码包解码，并设计了一种链路质量度量(Link Qualify Metric, LQM)来选择高质量的转发节点。该方案的编码结构仅限于两跳范围之内，导致两跳以外的编码机会缺失。文献18指出COPE和ROCX存在编码机会利用不充分的问题，提出一种分布式编码感知路由(Distributed Coding Aware Routing, DCAR)，该方案将编码机会的搜索范围从两跳扩展到了多跳范围，给出了多跳网络编码条件(Multi-hop Network Coding Condition,MCC),有效增加了编码机
11、会的数量。同时，DCAR将节点队列缓存数据包的数量作为路由度量(Coding-aware Routing Metric)，选择合适的传输路径。文献19提出一种联合编码感知路由(Network Joint Coding Aware Routing, NJCAR)，允许编码节点的下游节点对编码包不一次性完全解码，可以通过分步对编码包进行解码，提高了编码包的解码效率，但计算复杂度较高。文献20针对现有编码条件不能准确的识别编码机会，提出一种通用的编码条件(General Network Coding Condition, GCC)和以免费搭载其他数据流为导向的路由度(Free-ride-orient
12、ed Routing Metric, FORM)，系统分析了可能的编码场景，并开发了一种编码图以实现条件，通过编码流选择过程来检测每个编码节点的编码能力，使得新数据流可以免费搭载现有的数据流，减少传输次数。文献21针对多流情况提出了一种分布式贪婪编码感知确定性路由(Distributed Greedy Coding-aware Deterministic Routing, DGCDR)，将多条数据流进行编码，同时考虑到多流编码可能存在干扰问题，通过增加额外的路由过程来检测编码机会的有效性，在一定程度上有效提高了网络吞吐量。文献22分析了DCAR类型的方案在检测更多编码机会时，可能存在网络负载不
13、均衡，针对该缺点提出了一种约束编码感知路由机制(Constrained Coding-Aware Routing Scheme, CCAR)，通过约束编码条件检测良好的编码机会，根据定制的“路由+编码”发现过程计算输出队列长度，评估编码节点的状态。2.机会式编码感知路由机会式编码感知路由发送数据前无需先确定传输路径，发送数据的每一个节点通过计算与各邻居节点之间编码机会概率，选择编码增益最大的节点作为下一跳接收节点，然后编码数据包并广播编码包至该邻居节点。文献23提出了典型的机会式编码感知路由机制(Coding-aware Opportunistic Routing Mechanism, COR
14、E)，通过将逐跳机会转发和流间网络编码相结合，允许节点从邻居节点集中选择编码增益最大的节点作为下一跳节点，该方法总是具有最大的编码增益，从而提高了单次传输的数据量。机会式编码感知路由对动态网络更具有适应性，但机会式路由对下一跳的选择计算较为复杂，可能产生较多的计算开销。文献24提出一种基于队列状态和局部拓扑的增强型编码感知路由算法(An Enhanced Network Coding-aware Routing Algorithm based on Queue State and Local Topology, OQMCAR)，该方案考虑了节点编码数据包的队列状态，在每一次机会传输中，采用基于
15、队列长度的阈值策略，对数据包进行有效的“传输或等待”决策，而不非现有的感知编码路由算法中使用的机会编码策略。文献25提出一种高效的基于网络编码的背压调度算法(An Efficient Network-coding based Back-pressure Scheduling Algorithm, NBP)，背压调度被认为是无线多跳网络中有效的资源分配策略，该方案将背压调度与网络编码相结合，能够有效应对动态拓扑，确保传输的稳定性。文献26提出一种网络拥塞避免编码感知路由方案(Congestion-Avoidance Network Coding-Aware Routing, CANCAR)，该方
16、案考虑了拥塞强度和数据流编码成功的实测信息，将编码不佳的数据流在网络瓶颈处重新路由，在变更过的路由路径上创造编码机会。能有效地将网络中负载最重的部分从编码最少的流量中释放出来，使得最大的负载节点处的编码流获得更高的编码增益。根据现有的按需式编码感知路由，大多数方案一味地追求探索更多的编码机会，而忽视编码机会的有效性。这与编码机会判断条件的不合理性有关，复杂网络中多条数据流进行编码在一定程度上能够增加编码机会的数量，但这些编码机会中可能存在一些因干扰而失效的编码机会，导致生成的编码包不可解，从而影响无线多跳网络的传输性能27。此外，按需式编码感知路由的数据传输是建立在可靠传输路径上，但在时变网络
17、中按需式编码感知路由的稳定性容易受此影响28。因此，如何获得更多编码机会的同时确保编码机会的合理性，且有效应对网络拓扑变化提高传输效率，具有重要的研究价值。1.3 研究主要内容与目标本章分析了网络编码与编码感知路由的特点，在现有研究成果基础上，对编码感知路由在无线多跳网络的应用进行深入的研究，主要以编码感知路由在多流环境中如何寻找更多编码机会，避免多流干扰提高编码包的解码率，提高编码感知路由在动态网络的适应性，减少数据包的传输时延和提高网络吞吐量为研究目标，提出了解决多流干扰的编码感知路由算法(Coding-aware Routing to Solve Multi-flow Interfere
18、nce, CRSMI)和一种基于背压策略的编码感知路由算法(Coding Aware Routing based on Back-pressure Strategy, BCAR)。本文主要研究的工作和创新具体如下：1、介绍了无线多跳网络的特点、网络编码的分类及不同类型编码感知路由的优缺点。详细阐明了基于网络编码技术的数据传输基本原理与编码感知路由技术的结构组成与实现机制，其中主要包括编码感知路由的分类和编码感知路由设计所需解决的关键问题。2、针对现有的编码感知路由，现有的大多数确定性编码感知路由的编码机会判断条件只考虑任意两条数据流之间的编码机会，忽略了多流之间的编码机会。但在多流情况下，当现
19、有编码流与新数据流满足编码条件再次进行编码时，现有编码流和新数据流之间可能存在干扰，使得产生的编码包不能够解码。为防止多流干扰引起的错误编码导致系统性能下降，本文提出一种解决多流干扰的编码感知路由协议(CRSMI)，并定义了多流网络编码条件。在路由创建过程中收集多流的传输信息和流经节点的侦听信息，通过多流编码条件对收集的信息进行编码机会判断，筛选出有效的编码机会，确保生成的编码包可以在各自的目的节点完全解码。此外，在路由度量方面综合考虑了编码增益和链路质量等因素，选择最佳传输路径。3、针对现有的编码感知路由，经研究发现，大多数方案的设计侧重于固定的传输路径和静态数据流。以该方式设计的路由在一定
20、程度上容易受到动态拓扑及动态数据流的影响。使得路由不断地进行路由发现过程，导致路由过度增加时延且不能稳定地传输数据，影响网络吞吐量。本文提出一种基于背压策略的编码感知路由算法(BCAR)，该算法通过将背压策略与网络编码相结合，根据网络状况对网络资源作出调度，综合考虑编码机会、队列梯度和队列中数据包的积压时间等因素，将数据包发送至编码机会较多且拥塞程度较低的节点，同时能够将队列中积压时间较长的数据包优先传输，以减少数据包在网络中的滞留时间。1.4 论文组织结构本文内容组织结构如下：第一章引言。主要阐述网络编码与编码感知路由的研究背景及其意义。同时，总结了网络编码及编码感知路由的国内外研究现状，分
21、析了按需式编码感知路由和机会式编码感知路由在无线多跳网络中的发展优势，最后介绍本文的主要研究内容与目标。第二章网络编码与编码感知路由相关介绍。具体阐述了网络编码原理及涉及的相关基础，并对现有编码感知路由方案进行详细分类总结，从数据来源、编码结构和感知时机三个方面进行分类，同时分析归纳了编码感知路由的编码条件和路由度量在无线多跳网络中的特点及优势。第三章解决多流干扰的编码感知路由算法研究。现有按需式编码感知路由的网络编码条件存在一些不合理性，容易受多流干扰的影响，导致产生的部分编码包不可解，针对该问题本文提出了解决多流干扰的编码感知路由算法，设计了一种多流网络编码条件，并给出了编码节点判断算法和
22、路有度量的详细设计，具体介绍了整个方案的路由过程、传输步骤、实验仿真以及性能分析。第四章基于背压策略的编码感知路由算法研究。根据目前编码感知路由的研究现状，针对按需式编码感知路由在时变网络中鲁棒性不足等问题，提出基于背压策略的编码感知路由算法研究，介绍了传统背压策略的调度过程，通过编码感知路由结合背压策略的优势，给出了具体的链路选择步骤，最后具体介绍方案的仿真实验及性能分析。第五章结束语。对全文进行总结，并对后续相关研究工作进行介绍。第2章 相关基础2.1 网络编码简介2.1.1 网络编码原理相关研究发现，传统传输模式的传输链路存在一定局限性，对传输的数据不进行任何操作也无任何额外信息增加，导
23、致整个系统吞吐量不高。而网络编码技术能打破该局限，使得中继节点不仅保留传统的“存储-转发”功能，还允许中继节点拥有对数据编码组合的能力，中继节点按照相应的编码规则将不同数据编码后转发至下游节点，下游节点依据缓存信息将满足解码条件的编码包解码，从中恢复所需数据包。该技术能有效减少数据传输次数，节约了网络资源，提高了网络传输效率29-31。如图2.1所示，通过链式传输模型对比传统传输模式与基于网络编码的传输模式图。如图2.1(a)所示，在传统传输模式中，时隙t1节点S1传输数据包P1到节点R，时隙t2节点S2传输数据包P2到节点R，时隙t3节点R向节点S2发送数据包P1，时隙t4节点R向节点S1发
24、送数据包P2，信宿端分别接收到请求包共需4个传输时隙。图2.1(b)所示，基于网络编码的传输模式中，在时隙t3时，节点R将接收的数据包P1和P2进行编码，生成编码包P1P2并同时发送至节点S1和S2中，信宿端根据接收的编码包和已有数据包，可以译码出请求数据包，整个传输过程只需3个时隙，比传统传输模式节省了1/4传输时隙。由此可见，网络编码可为两条数据流创造一次编码机会，那么更多数据流交汇的通信情况，则存在的编码机会数量可能就会越多2132。因此，在无线多跳网络中，为提高传输有效性，需增加编码机会的数量，而编码机会的数量某种程度上取决于数据流之间的拓扑关系，当数据流交汇较少时，编码机会也十分有限
25、，从根本上限制了传输有效性的提升33-34。2.1.2 网络编码特点网络编码技术一直以来得到广泛的关注，特别是网络编码技术特点与无线网络广播特性有很好的契合性，因此网络编码技术被应用到了无线网络不同的场景。网络编码利用数据包之间的关联性，通过增加编码节点的计算开销换取了传输链路的传输有效性。网络编码共有以下特点：1.增加网络吞吐量在无线多跳网络中，当存在数据流相交时交叉节点可采用网络编码技术对接收到的数据包进行网络编码，将生成的编码包通过广播方式发送至各下游节点进行解码，这一编码转发过程增加了交叉节点单次传输的信息量。与传统通信相比，打破了传统通信单次传输容量的限制，使得系统的整体网络流量得到
26、显著提升。因此，网络编码在增加网络吞吐量方面具有明显优势。2.增强网络通信的安全性对于传统的网络通信，窃听者通过窃听目标节点传输的信息，造成节点传输的信息泄露。攻击者通过篡改或伪造的方式对网络通信造成污染，使得网络通信安全性降低。如图2.2(a)所示，窃听者在每一次的传输过程中都能侦听到原始数据包，当传输重要信息时，传统传输模式具有严重的安全隐患。在图2.2(b)中，源节点S不再单独发送原始数据包，而是将原始数据包进行编码，窃听者窃听到的数据包为编码包，要想获得原始数据包，必须获得足够的数据包并且知道编码规则，否则窃听者无法从中获取原始数据包。同时，若攻击者想伪造数据对通信消息进行污染，由于节
27、点对数据包的编码方式在不断的变化，当下游节点接收到伪造的数据包无法进行解码时，接收节点会将污染数据包丢弃，防止被污染的数据包继续向下扩散而造成不可挽回的局面。3.提高数据传输可靠性在无线网络中，数据的传输容易受到发送端的发送功率、信道衰落和多径效应的影响，导致部分数据包在传输的过程中无法正确到达目的端。为了提高数据传输的可靠性，通常将数据包以多路径传输方式进行传输，减少链路干扰对数据传输的影响。虽然该传输方式提高了传输可靠性，但也增加了发送端的发射功率。特别针对传感器网络，每个传感器需电源供给，传输次数的增多会导致传感器耗能加快，并且传感器的更换较为复杂，不利于传感器网络的稳定运行。网络编码技
28、术在传感器网络的应用，编码节点能够将数据包进行线性或非线性编码，能有效减少节点数据包的传输次数，即便传输过程中出现丢包情况，节点可以通过缓存数据包对接收的编码包进行解码，从中恢复所需数据包，有效地改善数据传输的可靠性。2.2 编码感知路由技术概述随着对网络编码研究不断的深入，一些学者发现传统的基于网络编码的传输方案仅被动等待编码机会，不能够主动寻找编码机会，使得网络中的编码机会不能被充分利用，不利于传输有效性的提高。将网络编码与具有感知能力的路由相结合，研究如何在传输数据的过程中主动探索并利用网络中编码机会现已成关注热点。编码感知路由在建立路由的过程中将编码机会作为路由选择的依据，主动选择具有
29、编码机会多的链路作为传输链路，充分利用链路中的编码机会，使得系统性能进一步提升。如图2.3所示，假设存在两条数据流和，在图2.3(a)中传统路由传输两条数据流分为两条路径，这两条路径不存在交叉节点，所以数据流和数据流之间不存在编码机会。在图2.3(b)中，由于编码感知路由能够主动发现网络中潜在的编码机会，在传输数据流之前优先选取链路作为数据流的传输链路，当数据流和在节点A交汇时，节点A可以将不同流的数据包进行编码，再将编码包分别向节点S和D发送，能有效提升传输效率。随着编码感知路由研究不断的深入，现有的编码感知路由方案从数据来源、编码结构和感知时机三个方面深入。1.数据来源根据参与编码数据来源
30、的不同，可将现有的编码感知路由分为流内网络编码和流间网络编码。流内网络编码是指节点编码的不同数据包来自于同一条数据流。流间网络编码是指节点对来自不同数据流的数据包进行网络编码。两者的编码方式在本质上有所不同，在不同场景表现出各自的优势。对于流内网络编码，节点将同一条数据流中的数据进行合理分组，由表示，然后通过线性组合的方式对这些分组进行网络编码生成编码向量Y，其中编码向量的编码系数X从有限域中随机选取，数据分组的编码过程见公式(2.1)和公式(2.2)。之后节点将编码包发送至目标节点，当目标节点接收的编码包为线性无关时，可将接收的编码包进行解码，解码过程见公式(2.3)。从公式可以看出，经过线
31、性编码后的数据更具有安全性，同时也减少了节点传输数据的次数，增加了传输效率，但整体的计算开销较大，不适合在动态拓扑网络中执行。对于流间网络编码，网络中的节点接收来自不同数据流的数据包，根据编码条件将满足条件的数据包进行编码并以广播方式转发至下游节点，下游节点通过机会侦听或自身缓存的数据包来解码编码包。在大量数据流交叉通信的情况下，流间网络编码主要采用简单高效的异或编码(XOR)运算，有助于降低编解码过程的计算复杂度。在现有的编码感知路由中，多数方案主要研究数据流之间的编码机会，因此流间网络编码的应用较为广泛，其关注热点为如何在无线多跳网络中根据数据流的空间分布，寻找潜在的编码机会以提高编码增益
32、。2.编码结构为提高编码感知路由性能，需要解决如何提高编码机会数量这一根本问题，编码机会的形成取决于网络中各数据流的空间分布，因此数据流之间的拓扑关系直接影响编码机会是否存在。对于存在编码机会的数据流空间分布，将其称为编码结构。编码感知路由根据当前数据流形成的编码结构即可判断各数据流之间是否存在编码机会。当然，不同的编码结构能够发现不同范围内的的编码机会，很显然寻找编码机会的范围越大，则存在的编码增益可能就越多。通过对现有的编码感知路由研究现状分析，现介绍单跳编码结构、多跳编码结构和联合编码结构三种具有代表性的方案。相关符号解释，如表2.1所示。表2.1 符号表符号定义数据流f经过的的任一节点
33、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
34、-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至中间
35、节点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能够寻找到更多的编码
36、机会。如图2.6所示，假定有两条数据流f1，f2相交于节点R，距离节点R两跳的下游节点D2接收到编码包P1P2，节点D2通过机会侦听机制从节点S1侦听到数据包P1，节点D2通过侦听到的P1数据包可以解码出数据包P2。根据上述描述，MCS结构可形式化的表示为：图2.6 多跳编码结构(3)联合编码结构文献19给出了联合编码结构(Joint Coding Structure, JCS)，该编码结构不再要求编码包在下游节点一次性解码，而是根据下游节点侦听到全部原始数据包并且下游节点被认定为是解码过程中的一部分，将编码包在多个下游节点进行分步解码，从而提高编码包的解码率。如图2.7所示，三条数据流f1，
37、f2，f3交汇于节点R1，每条数据流分别发送各自的数据包P1，P2，P3至节点R1进行网络编码操作，再将编码后的数据包P1P2P3转发到各自的下游节点进行解码。传统网络编码方式下，路径中，R1的下游节点不能够接收到其余两个数据包，无法对编码包进行解码，所以不存在编码机会，下游节点对接收到的数据包进行缓存或丢弃。在联合解码结构下，节点R2通过侦听从邻居节点S3侦听到数据包P3,节点R1将编码后的数据包转发到节点R2进行分步解码，得出新的编码包P1P2，节点R2再向下转发到节点D2，节点D2通过侦听得到数据包P1，可以继续解码得到自己所需的数据包P2。根据上述描述，JCS结构可形式化的表示为：图2
38、.7 联合编码结构3.感知时机对于现有的编码感知路由对编码机会的感知时机，可分为两类：按需式编码感知路由和机会式编码感知路由。按需式编码感知路由是指网络中的源节点节点与其他节点建立通信时，源节点发起路由发现过程，寻找一条可用的传输路径来发送数据。该类型路由的编码感知时机在路由发现过程中，其过程主要分为路由请求和路由应答两个阶段，源节点发送多个路由请求(Routing Request, RREQ)数据包向目的节点传输，RREQ数据包每经过一个节点便将该节点信息和编码机会情况记录在RREQ数据包中，若中继节点重复接收RREQ数据包，则将其丢弃，防止形成环路。当多个RREQ数据包到达目的节点时，目的
39、节点根据RREQ数据包中记录的信息生成路由应答(Routing Reply, RREP)数据包，按照RREQ数据包的路径原路返回。源节点从多个RREP数据包获得多条传输路径，根据路由度量对多条路径进行筛选，从中选取编码增益最多的传输路径。该类型编码感知路由适合较为稳定的网络场景。机会式编码感知路由是指网络中的源节点发送数据前无需先与目的节点建立确定传输路径，源节点将邻居节点纳入节点转发集中，在确定节点转发集后，将数据发送至转发集中的各节点，根据编码机会带来的编码增益确定各节点的转发优先级。一般情况下，编码增益越高节点的转发优先级越大，则优先级最大的节点优先对数据包编码并转发。因此，机会式编码感
40、知路由的编码感知时机在选择转发节点阶段，该类型路由适用于无线时变网络，其原因为无线信道的时变性和节点的移动性，导致无线网络中的传输链路质量不稳定，机会式编码感知路由能够根据网络的实时情况选择链路状况较好的来传输数据。2.3 路由度量定义路由度量是用来衡量链路选择的一个指标，根据不同的网络场景，路由度量考虑不同的因素选择合适的传输路径。由此可见，路由度量的设计对路由策略有着至关重要的作用。现有主流的路由度量有以下几类：1.最小跳数最小跳数(Minimun Hops, MH)是指源节点传输数据包至目的节点所经过节点最小数量。在选择路径时，路由决策会选择路径中节点个数最小的链路作为传输路径。该路由度
41、量是从有线网络发展至无线网络，在传统路由中较为常见，其内部算法为熟知的Dijksta算法或线性规划算法，计算方便简单。2.期望传输次数期望传输次数(Expected Transmission Count, ETX)是指源节点向目的节点发送数据总共需要的传输次数35-36。在实际无线多跳网络中，无线信道会因受到外界因素而产生丢包情况。因此，信道质量是需要考虑的重要因素。假定无线网络中任意两个节点之间的链路为，链路的丢包率为。当链路(a,b)经过n次尝试成功传输数据包的概率为s(n)，其公式如下：那么链路成功传输数据包所需要的期望传输次数可表示为：由此可见，丢包率越小ETX的值越小，链路传输数据的
42、效率就越高。因此在选择链路时，应选择预期传输次数最少的链路。3.期望传输时间期望传输时间(Expected Transmission Time, ETT)是指源节点向目的节点发送数据包预期需要的传输时间20。该度量考虑预期传输次数的同时，还考虑了数据包的大小和信道速率，其公式如下：其中，S表示为链路速率，B表示数据包的大小。整条传输路径的期望传输时间为源节点到目的节点之间所有链路的期望传输时间之和。2.4 本章小结本章主要介绍网路编码和编码感知路由技术等基础性知识。首先介绍了网络编码基本原理，并对比基于网络编码的传输模式和传统传输模式，总结了网络编码技术在无线传输中的优势。其次，介绍编码感知路
43、由技术，并从数据来源、编码结构和感知时机三个方面对编码感知路由技术进行分类。最后，介绍了现有主流路由度量。第3章 解决多流干扰的编码感知路由算法研究3.1 引言编码机会是提高编码感知路由性能的最基本因素，编码机会形成于数据流之间的相互用，编码机会的数量由数据流之间的拓扑结构决定。因此，一种好的路由决策能够直接影响编码感知路由中网络编码的性能。根据相关研究发现，文献1837-39所提方案多局限在讨论任意两条数据流之间的编码机会，忽略了多流之间的编码机会。当在多流环境下进行网络编码时，数据流之间相互作用较为复杂，容易产生干扰，由于编码条件的不完备性，使得新加入的数据流产生不可解的编码包，从而影响了
44、新数据流的传输效率。针对上述问题，本文提出一种解决多流干扰的编码感知路由方案。为防止多流干扰导致伪编码机会的产生，需确保编码条件的正确性，该方案首先定义了多流网络编码条件，严格筛选网络中的编码机会，确保编码节点生产的编码包能够完全解码。其次，重新设计了路由发现过程中所发送的消息格式，用于收集必要信息，通过编码节点判断算法判断编码机会的有效性。此外，在路由度量方面综合考虑了编码增益和链路质量等因素选择最佳传输路径。3.2 现有编码感知路由存在的问题分析对于现有的编码感知路由，大多数方案编码机会判断条件在两条流之间判断编码机会是可行的，但在大于两条流（多流）的某些场景下会存在所生成编码包在信宿解码
45、失败的问题。以下通过两个示例进一步加以说明。引理 3.1 多跳编码条件18：MCS结构下，有多条数据流，其中任意两条数据流相交于节点，在节点处的网络编码条件为：图3.1 多流干扰示意图如图3.1(a)所示，两条数据流在节点交汇，根据多跳编码条件，并且，。，并且，。满足引理1条件，并且节点分别通过侦听能够获得用于解码的数据包。当多流情况下，如图3.1(b)所示，新数据流出现，数据流交汇于节点，数据流同样能够满足引理1，即，并且，。，并且，。节点对数据流发送的数据包进行编码生成编码包，发送至各自下游节点。但节点从节点侦听的数据包不能解码出原始数据包，节点所满足的编码机会为伪编码机会。可以看出数据流
46、与之间存在干扰。对于编码感知路由，编码条件的正确性对编码机会的识别至关重要，所以本文将设计一个能够避免多流干扰的编码条件，并通过相应算法从潜在的编码机会中筛选出有效的编码机会，来提高节点的编码效率，从而提高路由传输性能。3.3 网络模型本文采用的网络模型为多流多跳无线网络，如图3.2所示。该网络模型由多个节点组成，每条数据流的数据包由源节点发送到目的节点，并能够与其他数据流交叉通信，为了提高传输效率，交叉节点对来自不同数据流的数据包进行网络编码，将生成的编码包再广播，编码包是由多条流发送的原始数据包组成的。若网络中的下游节点能通过侦听获得足够的信息则可通过相互协作对编码包进行分步解码，直到目的
47、节点能够从编码包中解码出原始数据包。如图3.2所示，假设存在三条数据流、和，各数据流所对应的数据包分别为、和，源节点、和分别发送数据包、和至中间节点处进行网络编码，再向下游节点()广播编码包。各下游节点通过侦听机制能够从其他流的上游节点()分别获取原始数据包，以协助完全解码。图3.2 网络模型3.3 解决多流干扰的编码感知路由设计本文所提编码感知路由协议是一种确定性路由，源节点在发送数据包之前需预先知晓完整的传输路径，这一特性可使源节点筛选出能够实现最佳编码的传输路径。因此，CRSMI协议设计主要包括编码机会条件判断、路由发现、路由度量和路由选择四部分。3.3.1 多流编码条件定义在编码感知路
48、由中，编码条件对路由的编码机会和编码增益有着至关重要的作用。为防止伪编码机会的产生，本方案提出了多流编码条件，在多跳编码条件的基础上添加了编码包能否完全解码的判定限制，用于评估交叉节点在多流情况下的编码机会。假设存在相交于节点，表示流中节点的上游节点集合，表示流上节点的下游节点集合，表示节点a的一跳邻居。假设，a能够侦听到节点b发送的数据包。表示节点从节点s中侦听到的数据包，表示对各下游节点侦听到的数据包进行XOR操作，即。表示m个原始数据包通过XOR生成的编码包，表示数据流的原始数据包。定理 3.1 多流网络编码条件：有多条数据流相交于节点，任意两条或多条数据流均能满足如下充分必要条件，则节点c能进行网络编码：充分性证明：多条数据流相交于节点时，满足定理1的节点必然满足引理1的编码条件，即多流能够在节点进行网络编码，充分性得证。必要性证明：假设有数据流能够在节点c处进行网络编码，则对于任意一条数据流，对其余数据流均存在下游节点能从编码包中恢复出原始数据包，那么节点可以通过侦听其余流发送的数据包，即，或数据流本身含有效原始数据包，即。若节点能够最终解码出原始数据包，必然满足，即定理1满足条件，必要性得证。引理3.1根据数据流之间的拓扑关系来判断编码机会，定理3.1条件(1)沿用了该拓扑关系判断交叉节点潜在编码机会，