论文研究-基于网络编码的深空多径路由算法 .pdf

所需积分/C币:13 2019-08-16 16:28:15 446KB .PDF
收藏 收藏
举报

基于网络编码的深空多径路由算法,赵辉,梁花,为降低深空通信中长时延、高误码率、链路间歇中断对路由的影响,有效利用节点间的通信机会保证数据的可靠传输,提出一种基于网络
山国武技记文在 数据包头分组号编码系数编码数据 XXXXXⅩX XX XXXXXXX 图数据包格式 冗余因子:源节点采用网络编码后生成的个编码包与个原始包的比值定义为冗余 因子,即 越大表示生成的编码包越多,编码冗余越大,从而日的端成功译码的概率越大,但也 会导致网络資源消耗过多;反之过小,目的节点可能由于接收不到足够的编码包而无法止 确译出原始数据包。 中间节点:当中间节点接收到个编码包后,它首先判断该编码包是否与缓存中已有的 编码数据包线性无关。若无关,则放入缓存;否则,丢弃。假设节点的缓存中存在个 相同组标识的线性无关的数据包 ,从有限域 中随机选择个数生成局部 编码系数 ,对应的编码过程为∑此时,对应的编码系数为 ,和用新编码系数更新数据包结构中的编码系数后,继续向后发送。 中间节点通过这和再编码的方式将来自上一跳节点的信息进行编码组合后发往下一跳节点。 目的节点:目的节点接收并存储线性无关的编码包,提取岀编码向量构建全局编码矩阵。 当编码矩阵的秩人于或等于原始数据包饣数时,停止接收数据并开始译码。令目的端接收到 的数据包为′≥,则有 其中,′为全局编码系数。 译码过程 当接收端接收到个线性独立的数据包’,即收到的数据包对应的编码系数矩阵的秩 为时,可以通过高斯消元法解码,还原出原始数据包。由式可得源数据包译码结果如 下式所小 算法的原理 无线网络中,一般使用冗余传输和准确的路由算法两种方式保证数据的可靠传输ε在深 山国武技记文在 空网络中,行星节点运动的周期性从而网络拓扑是确知的,但网络中存在不可预测的链嵱中 断情况。针对上述随机线性编码在深空网络中存在的三个方面的问题, 主要包括四 部分:相交多径寻路、源节点编码、部分中间节点重编码、目的节点解码预判。其中源节点 编码主要采用随杋线性网络编码对数据包进行处理,然后将编码包从多条路径传输,使用路 径冗余和网络编码冗余提高数据传输的可靠性;多径寻路为源节点根据节点间预知的接触关 系选择多条相交路径进行数据传输,有效利用节点间接触机公;具有编码増益的中间节点对 接收的数据包进行重编码然后转发,而其它中间节点则采用直接转发的方式,减少中间节点 的数据处理量,降低编码算法复杂度的同时能避免中间节点处理的信息量过大而造成的网终 拥塞。岀日的节点接收到一定数量的数据包时进行解码预判,采取解码预判机制,将不能解 码出的数据包反馈给目的节点的上一跳节点集,上一节点集有目的地优先发送最有助于目的 节点解码出原始数据的编码包,使得目的节点尽快解码获得原始数据包,有效减少目的节点 的解码吋延,降低端到端传翰吋延 使用网络编码减少数据包的发送次数降低能耗, 利用路径冗余和网络编码冗余结合的方式提髙传输可靠性,该算法不仅实现数据可靠的传 输,而且能够节省数据冗余度和网络能量消耗。下面分别对多径寻路、部分中间节点重编码 目的节点解码预判机訇进行详细的阐述。 相交多径寻路 传统的无线网络多径路由按照多条路径之闩的关系可分为相交多径和不相交多径,现有 的多径路由算法大多采用不相交多径。相交多径允许各路径间的链路有公共部分,方面可 以避免为建立不相交路径而刻意选择性能较差的链路。另一方面相交多径能接收米自上一跳 所有节点的数据包,提高对冗余数据包的利用率。最后,在节点数目较少的深空网络,可能 不存在多条不相交路径。但相交多路径中公共节点处承受的信息量较大可能会造成拥塞,该 公共节点的尖效在相交多径中会造成多条路径失效。因此,如果能够通过采取一定的措施减 少公共节点处的信息量,相交路径的性能会更优且更适合深空通信环境。现有的减少中闫节 点信息量的方法主要通过限制中间节点接收的数据包个数,一旦接收到一定量的某一组数据 包,中间节点便不冉接收该组绲码包,控制冗余数据包数量。本章在狠制中间节点接收的数 据包个数的同时采用部分中间节点重编码的方法减少中间节点处理的数据信息量,因此木章 的多径均指相交多径传输。 当有数据要发送时,源节点根据网络拓扑状态信息,计算从源节点到目的节点满足容量 约束条件的最早到达路径,比较节点的剩余容量与包所需容量的大小,选择剩余 容量能传输数据包且最早到达目的节点的路径。在传统的网络中 算法主要利用当 前的网终拓扑计算最短径,而不考虑未来拓扑变化情况。深空通信环境中节点运动的周期性 和确定性使得节点能够获取任意时刻的位置信息,假定数据包到达某个特定节点的时刻是预 知的,且该预知的时刻可决定后续链路的。深空中节点稀疏,通信距离远,链路间歇中 断的特点,源端到日的端之闫可能不存在一条通路。 深空中节点根据狈知的接触信息和距离信息得到接触计划进而枃造接触图模型 ,其中 是深空中有限节点集;为节点间接触的集合,其 中接触是指深空网络中节点间可通信时间段。 表示在时刻节点和之间的接 触 分别为接触起始时刻和结束时刻, 为该接触时段内缓存的大小, +为该接触时段内计划的传输速率,为所传数据包的大小。 为接触的剩 山国武技记文在 余容量 为接钽的剩余时间; 等待时延:当时刻节点,←间接触的剩余容量不满足传输数据大小为的束时, 则必须等待下一次,间的接触,所需要的等待时延 。采用式分别计 算源节点和中间节点当前接触的剩余容量 比较剩余容量与的大小,当剩余容量满足 ≥ 或 ≥时, 等待时延 为,表明数据包在该接触内可传输完毕,否则需要等待下一可用接触方 能传输,该等待时延可能会非常大。 当有数据要发送时,源节点根据网络拓扑状态信息,采用对时变的 进行改进 的算法计算出一条从源节点到目的节点满足容量约束条件的最早到达路径作为参考路径。传 统的 算法主要利用当前网络拓扑计算最短径,而吋变的 算法会考虑木来网 络拓扑变化,代价函数是时变的。假定数据包到达某个特定节点的时刻是可预知的,可根据 该预知的时刻、等待时延和该接触内计划的传播时延计算数据包离开该节点的时刻 z=zrt,计算过程如式所示,仅源节点考虑节点的排队时延,其中 为节点冋数据包的传播时延 z=7+T 假设为源节点,为目的节点,数据包到达的时间是,由深空通信距离远,节 点稀疏,链跻间歇中断,源端到目的端之间可能不存在一条实时通路。源节点计算出的路径 表示为一系列接触的集合 其中 是这条最早到达路径上的节点。根据节点的容量约束关系确定节点离开特 定节点的时刻, 算法代价函数采用最早到达时间作为路径的选择标准,即链路代价 为本地排队时延,等待时延和传播时延之和。在源节点和中间节点采用的可用如下式 表示,其中 表示本地排队时延。 本文所提改进的 算法利用预知的网络拓扑信息,根椐包到达节点的时刻比较节 点剩余容量与包所需容量的大小,计算包离开节点的时刻,选择剩余容量能传输 数据包且最早到达日的节点的路径作为参考路径。源节点将参考路径存储在数据包的扩展块 中,能减少参考路径后续节点的计算复杂度,后续节点只需确认该节点的卜一跳节点是否为 参考路径中的卜一跳节点。若不是,则修改存储的路径为自身计算的节点,否则按照最早到 达路径转发包。参考路径衣示源节点根据自己的接触图计算的·条最短径,但是深空吋变的 网络拓扑使得这种源路由方式不能应对复杂的深空通信环境,必须采用分布式路由方法,中 山国武技记文在 间节点采用和源节点相同的算法计算下·珧节点,同吋需要采用必要的措施保证包在后续链 路的可靠传输。因此,计算岀的最短径是指·系列接触的集合。为了有效应对深空网络拓扑 的动态变化,本文采用相交多径传输机制,并采用上述方法构造出从源端到目的端的多条传 输路径,有效应对深空复杂的通信环境 部分中间节点重编码 深空网络拓扑是有向且循环的网络,为避免相交多径节点间链路出现的交叉或异向影响 网络编码的进行,需对该类情况作出有效处理。同时,为了遊免中间节点数据处理量过多出 现拥塞导致多条路径失效,本章采用部分中间节点重编码机制,只选择具有编码增益的节点 进行重编码,而对于无编码增益的中间节点则采用直接转发的方式进行转发。下面介绍相交 多径中节点是否重编码的情形。 在采用网络编码的情况下,节点的流岀量通常要小于节点的流入量。节点的编码增益为 单位时闾内因编码而减少的流量。令为单位时间Δ内流入节点的节点流,为其 流量(单位为比特), ,单位时间内流入节点和流出节点的总流量分别为: 和 因此,编码增益 可表小为; 相交多径中的等待死锁 相交多径中循环节点的网络拓扑如图所示,网终中节点和在两条不同的相交路 径上,是的上跳节点,同吋在另路径中是的下跳节点。根据中间节点的编 码规则,中间节点必须接收到所有的上一珧节点集的编码包才进行再编码,导致需要等 待的数据包,则需要等待的数据包,从而节点与之间出现等待死锁,经由 节点的路径失效。针对上述问题,本章在该类节点处不进行重编码,采用直接转发的方式向 下一跳节点集转发所接收到的数据包 图相交多径的等待死锁 相交多径中具有编码增益的中间节点 相交多径中具有编码增益的拓扑如图所示:节点为两条相交路径的公共节点,且 节点的上游节点数大于下游节点数,即两条不同的支流在节点处汇聚成·条。此时, 可通过在节点处将上游节点的数据包进行再编码,由于网络编码所生成的编码包比特数 不超过参与编码的最大数据包的比特数,从而消除编码数据包之间的相关性以及减轻下游链 路负载。因此,节点称为具有编码增益的节点。本文只对具有编码增益的中间节点所接收 到的数据包进行重编码,一方面降低编码算法的复杂度,减少间节点处理的数据量,防止 中间节点岀现网络拥塞而导致经过该节点的路径失效。另一方面,网络编码对节点的运算处 理能力和存储空间要求较高,该方法能够允许处理能丿不高及存储空间有限的中间节点也参 与到数据转发过程中,采用直接转发的方式,能减少中间节点由于缓存溢出导致的丢包,同 山国武技记文在 吋能有效减少中间节点编码所消耗的能量。 图具有编码增益的节点 解码预判机制 针对数据译码过稈中目的节点解码等待时间较长的问题,本文提出目的节点解码预判机 制。当口的节点接收到一定数量的数据包时,利用己解码的数据包将自己缓存中未解码的数 据包进行解码预判,将不能解码岀的数据包反馈给目的节点的上一砩节点集,上一跳节点集 优先发送最有利」目的节点解码的编码包,使得目的节点能及时解码岀原始数据包,减少数 据包端到端时延。卜面分析解码预判札制的优越性。 假如在时刻,目的节点接收到的编码包为 ,其中 的组成如下式所示, 表示原始数据包,∝表示第个编码包从有限域中随机选取的原始数据包的编 码系数。 C + + 生成的编码系数矩阵为: a CC 此时,若目的节点再收到编码包,且 a +a +a + a 则日的节点能译码出 。反之,若日的节点收到的编码包,且 此时,日的节点收到数据包后,不仅不能成功解码,而且由于数据包 的引入,需 要等待更长的时间才能译码成功。因此,采用目的节点解码预判机制,将有益于解码的编码 包优先发送给目的节点,降低端到端的解码时延,减少编码包占用网络资源的时问能间歇的 提扃编码包的成功投递率 仿真验证 为」验证路由算法的性能,并与传统多径算法进行比较。先定义后续需要用到的三个指 标 山国武技记文在 数据包成功投递率() 在数据包传输过程中,目的节点能否正确接收到预期数据包是不确定的。可以用 米评估数据传输的可靠性 值越大说明传输可靠性越高。此处,将其定义为第一次传 输结束,接收端接收并解码成功旳薮据包和源端发送的源数据包之比,如下式所示: 上式中,表小在目的端成功斛码得到的数据包个数,表小源端发出的数据包个数。 源节点冗余度 冗余包可以保证目的端尽可能多的接收数据包,从而提高传输可筚性。然而,过多的冗 余包公浪费网络资源导致网络拥塞。因此,可引入来评估可靠传输的开销,它是无用 数据包和源端发送的数据包的比值。此处,无用的数据包包括冗余数据包和线性相关的数据 包。的表达式如式所示: 其中,表示参与文件传输的所有节点个数 表示第个节点收到的无用数 据包个数, 表示第个节点发送的数据包个数。 平均端到端时延() 用来表小数据传输的时效性,数据包从产生到目的节点的正确接收所经历的时延, 代表目的端处接收到的所有数据的时延平均值。包括四个元素:等待时延、传输时 、编码时延 解码时延 。因此可得到如卜等式: 其中,表示第个数据包到达目的端的时延。 仿真模型和主要参数 仿真模型如卜图所示,椭圆轨道从内而外为:太阳、地球、火星以及处于行星节点前 后各°的,处的拉格朗日中继卫星,充分发挥拉格朗日点的中继作用,提供多条可 选路径,有效利用网络资源。轨道半径分别为星间实际距离 。其中天文单位为 太阳到地球的平均距离, 。火星采集到的科学数据发往地球,节点间确知 的接触关系如表所示,表示可通信路径的开始时间和结束时间。节点间的网络拓扑关系如 图所示,实线表示节点间的链路是永久可通信的,虚线则表示只在表所反映的时间段内间 歇可通信。本文通过与传统多径算法分別比较数据包的投递率,平均端到端传输时延、冗佘 度等参数与丢包率之间的变化关系,评佔路由算法的性能。传统多径路山使用链路不相 父的最短路径算法。发送速率为 每个数据包大小为 假设各路径的丢 包率均相等且丢包率的取值范围为: 文件大小为 仿真次取平均值。 山国武技记文在 图网络仿真模型 图节点间接触关系图 表节点间接触计划 仿真结果与分析 反映传统多径算法和 算法的数据包成功投递率()如图所示,随着值 的增大,两个算法的投递率性能曲线均有所下降,但是 由于采用了网络编码,接收 端只要接收到足够的编码包就能还原出原始数据包,容错能力比传统多径算法強。而传统多 径算法仅通过路径冗余保证数据的可靠传输,当网络中丟包率升高时,数据包发生错诶的概 率增大,算法的投递率大大降低。在丢包坐超过时,两个算法的投递率急剧下降,这是 因为目的节点不能收到足够多的正确的数据包。 山国武技记文在 普通多径 丟包率 图投递率和丢包率的关系 如图所示为冗余度和链路丟包率的关系。图中,随着链路丢包率的增加, 算 法和多径传输的值均呈上升趋势。链路质量越差, 算法的值小于多径传 输。另外,在相同值的情况下, 算法能使得更多的数据包以较大的投递率到 达目的节点。因此,可以得出结论:在可靠性要求比较高的深空网络中, 算法的性 能优于传统的多径传输方式 ± 些通多径 丢包率 图冗余度和丢包率的关系 图为端到端时延与丢包率的关系,从图中可以看出,随着丢包率的增人,传统多径算 法的端到端时延逐渐増大,而 的时延增长缓慢,这说明网络状态对 算法的 时延影响不大。在网络状况较好时, 的时延比传统多径大,此时多径传输过程中丢 包较少,而 算法需逐眺传输以及编解码过程,会带来较大的传输时延。随着丟包率 逐渐增加,传统多径传输吋延由于丢包重传导致吋延急剧增加,当丢包率大于吋,传统 多径的传输时延明显大于 这是因为传统多径的重传时延大于 的编解码时 延

...展开详情
试读 11P 论文研究-基于网络编码的深空多径路由算法 .pdf
立即下载 低至0.43元/次 身份认证VIP会员低至7折
    抢沙发
    一个资源只可评论一次,评论内容不能少于5个字
    • 至尊王者

      成功上传501个资源即可获取
    关注 私信 TA的资源
    上传资源赚积分,得勋章
    最新推荐
    论文研究-基于网络编码的深空多径路由算法 .pdf 13积分/C币 立即下载
    1/11
    论文研究-基于网络编码的深空多径路由算法 .pdf第1页
    论文研究-基于网络编码的深空多径路由算法 .pdf第2页
    论文研究-基于网络编码的深空多径路由算法 .pdf第3页
    论文研究-基于网络编码的深空多径路由算法 .pdf第4页

    试读已结束,剩余7页未读...

    13积分/C币 立即下载 >