网络编码算法研究综述.doc资源-CSDN文库

版权申诉

文档资料

网络

110 浏览量 2022-05-08 13:11:02 上传评论收藏 495KB DOC 举报

资源推荐

资源详情

资源评论

网络编码算法研究综述

1. 引言

目前通信网络在各行各业已经显示出越来越重要的作用。但是与此同时由

于网络使用者数量的骤增和网络服务需求和网络传输质量的多样化使得如何对

网络进行优化从而最大限度地利用网络的现有资源成为当前研究者们所关注的

重要问题。

网络编码起源于网络中的多播(组播,multicast)问题。2000 年 Ahlswede

等根据网络信息流的概念在文献

[1]

中指出通过节点对数据包对来自不同链路的

数据包进行组合发送(编码)能够使得网络多播的容量确定性地达到最大流理论

的极限(该极限被称作网络多播的最大流限)，由于这一极限很难通过传统的多

播路由机制来达到，因此网络编码的优点非常明显，同时它也有相应的缺点。

其主要优点

[2]

是提升多播网络吞吐量、改善网络负载均衡、节省网络带宽

消耗、节省无线网络节点能量消耗、提高网络链路鲁棒性；主要缺点是因引入

编/解码而复杂性高、因中间节点可以编/解码而存在安全问题。

2.网络编码的基本概念与原理

2.1 网络编码的基本概念

下面通过文献

[1]

中给出的蝶形网络为例来阐述网络编码能够达到网络多播

的最大流限来描述网络编码的基本概念，如图 1 所示。图中所示的网络是一个

无差错的传输系统，不考虑时延和传输差错。其中源节点 S 准备将信息 a 和 b

发送到目的节点 t

和 t

，其余中间节点 r

到 r

均为路由节点。此外网络中的每

一条边的容量为 1，即每次只能传输一个信息。图 1(a)中显示了传统的网络多播

传输过程。由最大流最小割定理

[3]

很容易得出源节点 S 到两个目的节点 t

和 t

的

最大流分别为 2。但是由于在链路每次只能传输一个信息，因此待转发

的信息 a 和 b 中的一个必须在 r

处等待，从而目的节点 t

和 t

同时获得信息 a 和

b 的需求无法被满足。显然在该网络中传统的多播方式无法达到多播的最大流

限。而由于使用网络编码的多播方案允许节点进行编码，r

对 a 和 b 进行异或操

方案为“数据流内”编码，而某些非多播网络中的线性编码方案为“数据流间”编码。

2.2 网络编码的基本原理

1. 线性编码

在网络编码理论被提出之后，在一个网络中对信息进行怎样的操作才能够

使得网络多播达到上限成为首先被考虑的问题。Li、Yeung 和 Cai 三人首次在文

献

[5-6]

中提出网络编码的线性编码方案(linear network coding)，证明了在运算所选

取的有限域足够大的前提下，只需要对传输的信息进行线性操作即可确定

性地使得多播传输达到上限值。但是如何进行线性编码仍然是一个需要考虑的

问题。R.Koetter 和 M.Medard 首先给出了一种可应用于任意网络拓扑的线性编

码代数构造方式

[7-8]

。这种构造方式是已知整个网络的拓扑结构信息的情况下，

使用一个关系矩阵 M 来描述源节点的输入信息和接收节点所接收的信息之间的

关系：。其中矩阵 A 为源节点输入与边之间的关系矩阵，矩

阵 F 为网络中边与边之间的关系矩阵，矩阵 B 为边与目的节点输出之间的关系

矩阵。在这种方法中只要构造系统转移矩阵能够符合要求(矩阵满秩)则该矩阵

所表示的编码方案即可行。

与 R.Koetter 和 M.Medard 提出的线性编码的代数框架结构相对应，P.Sanders

等人基于图论提出了一种实现网络编码的多项式时间算法

[9-10]

。该方法同样需要

己知网络拓扑的情况下对网络进行编码，通过最大流最小割算法寻找完成网络

组播所需的路径来依次确定路径上各个路由节点的编码操作。这种方法有效地

避免了冗余边上的编码过程，不但将编码的构造进一步简化而且大大降低了编

码运算中基于的有限域的大小。

2. 随机编码

上面所提到的编码构造算法都是基于已知网络拓扑信息的确定性算法，在

应用中具有一定的局限性。针对这个问题研究者们又提出了不需网络拓扑信息

的随机网络编码算法

[11-12]

。在该算法中节点只需对来自不同链路的数据包进行

随机的线性组合处理即可(即节点输出是输入的随机线性组合，组合的系数从一

个有限域内随机选取)。研究表明随着接收节点数量与编码运算基于的有限域大

小的比值趋近于 0 时，该算法中接收节点能够成功解码的概率将趋近于 1。

总的来看，集中式的网络编码算法

[7-10]

需要根据全局拓扑状况来给每个节点

分配线性编码系数。虽然这些方法使得编码运算所需的有限域不会太大，但是

网络拓扑的变化将导致全部编码系数重新分配，因此可扩展性较差。虽然随机

网络编码算法具有良好的拓扑适应性，但是这种方法实现正确无误的传输具有

一定的概率性。

3. 非线性编码

线性编码已被证明可以确定性地达到任何一个多播网络的最大流限。但是

线性编码在非多播网络中的性能将会是怎样，并没有一个确切的答案。文献

[13]首先关注这一问题，证明了当编码运算基于的有限域为二元域时，存在着

没有线性编码方案的多播网络。文献

[13]

通过一个实例证明了同样限定编码域为

二元域时存在没有线性编码方案但有非线性编码方案的非多播网络，并首次探

讨了使用非线性函数进行编码的可能性。文献

[14]

进一步地指出即使编码域的增

加不足以使得所有非多播网络都存在线性编码方案。文献

[15]

将非线性编码分成

两类，证明了存在着一类与线性编码等价的非线性编码。由于在非多播网络中

构造达到其容量上限的编码方案非常复杂，因此对非线性编码的研究目前还处

于起步阶段。

上面介绍的三种编码方法是进行网络编码的三种基本方式和原理，所有的

网络编码实现都是以这三种编码方法来实现的。网络编码在应用研究方面主要

分为在大型网络和无线网络中研究模拟实现。

3．网络编码的构造算法

网络编码构造算法主要是解决如何有效求得每条链路对应的编码向量，并运

用该编码向量进行线性操作计算出链路上传输的信息向量，编码算法的发杂性

是衡量网络编码能否有效实现的重要依据。总的来说，典型的集中式算法主要

包括指数时间算法、多项式时间算法、贪婪算法等，其中因多项式时间有较低

的复杂性，因此具有重要的理论和应用价值。同时还有基于分布式实现的随机

算法 RNC。上述的典型算法都是网络编码应用的算法基础。

1. 指数时间算法

剩余18页未读，继续阅读

评论收藏

内容反馈

版权申诉

老帽爬新坡

粉丝: 79
资源: 2万+

网络编码算法研究综述.doc

蚁群算法研究综述.doc

中文分词算法研究综述.doc

Web搜索算法研究综述.doc

关联规则挖掘Apriori算法研究综述.doc

2023毕业设计文献综述.doc

路由算法大概综述.doc

加密算法文献综述.doc

蚁群算法文献综述.doc

42370中国网络游戏产业研究综述.doc

神经网络优化学习算法综述.doc

DS18B20 ROM编码的搜索算法.doc.doc

分布式无线传感器网络故障检测算法综述.doc

对图像的几何校正算法的综述.doc

关联规则挖掘的Apriori算法改进综述.doc

EKF模拟神经网络学习算法研究论文.doc

哈夫曼编码算法课程设计.doc

第七章-遗传算法应用举例.doc.docx

全国计算机等级考试二级Python真题及解析.docx

1000份ppt模版，PPT模板优秀PPT

导入证书可以解决”无法建立到信任根颁发机构的证书链"问题。

matlab批量读取excel表格数据并处理画图

OpenCv车辆识别训练模型

代码随想录知识星球精华-大厂面试八股文第二版v1.2.pdf

数学建模对乙醇偶合制备C4烯烃的问题研究

Vue-Element UI集成ECharts实现数据统计分析页代码部分(如果帮助到你，感谢关注点赞)

STM32F103C8T6中文数据手册

（头歌）计算机组成原理存储系统设计（HUST）1-7关答案

MATLAB深度学习入门实例（果树病虫害识别VGG19版）

（中文）半导体器件物理第三版课后习题答案，施敏著，

最新资源