网络编码研究综述
小型微型计算机系统ＪｏｕｒｍｌｏｆＣｈｉｎｅｓｅＣｏｍｐｕｔｅｒＳｙｓｔｅｍｓ２００８年４月第４期Ｖ０１．２９Ｎｏ．４２００８
网络编码研究综述
陶少国，黄佳庆，杨宗凯，乔文博，熊志强
（华中科技大学电子与信息工程系智能互联网技术湖北省重点实验室．湖北武汉４３００７４）
Ｅ－呦ｍｔａｏｓｈａｏｇｕｏ＠ｇＴｍｉＩ．ｃｏｍ
摘要：网络编码是通信网络中信息处理和传输理论研究上的重大突破，其核心思想是允许网络节点对传输信息进行编码处理．运用网络编码能够提升网络吞吐量、均衡网络负载和提高网络带宽利用率等．本文介绍网络编码的基本原理以及主要优缺点，归纳了网络编码的主要实现算法和机制，总结了网络编码的几种典型应用，最后讨论了网络编码进一步的研究方向．
关键词：网络编码；随机网络编码，信息流；多播
中图分类号：ＴＰ３９３文献标识码：Ａ文章编号：ｌｏｏｏ—１２２０（２００８）０４一０５８３—１０
ＳｕｒＶｅｙｏｆＮｅｔｗｏｒｋＣｏｄｉｎｇ
ＴＡＯＳｈａｏ—ｇｕｏ，ＨＵＡＮＧＪｉａ—ｑｉｎｇ，ＹＡＮＧＺｏｎｇ也ａｉ，ＱＩＡ０Ｗｅｎ—ｂｏ，Ｘ１０ＮＧＺｈｉ－ｑｉａｎｇ
‘Ｈ曲ｅｉＸｅ，ｋｂ口阢ｔ。ｒ了毋Ｉ摊ｋｍｇ魄ｔＮ礅ｕ计耗Ｔｅｃ‰ｌｏ甜，ＴｋＤｅ争口ｒ弧嘲毋Ｅｌｔｃｔｒ帆｛ｃｓ口’ｌａｌｎｆｏｍｍｉ帆?Ｈ坼ｚ｝ｌｏ，ｌｇＵ强ｉ钟ｒ矗皓毋Ｓｄ肌艟积ａ７ｋ＾加，ｐ臣ｙ，Ｗｋ＾硎４３００７４，ｃ＾抽４）
Ａｂｓｔｒ卵ｔ：Ｎｅｔｗｏｒｋｃｏｄｉｎｇ，ｋｎｏｗｎａｓｏｎｅｏｆｔｈｅｍｏｓｔｉｍｐｏｒｔａｎｔｂｒｅａｋｔｈｒｏｕｇｈｓｏｎｔｈｅｔｈｅｏｒｙｏｆｉｎｆｏｒｍａｔｉｏｎｐｒｏｃｅｓｓｉｎｇａｎｄｔｒａｎｓｍｉｓｓｉｏｎ。ｉ８ｂａｓｅｄｏｎｔｈｅｍａｉｎｉｄｅａｔｈａｔｅｎｃｏｄｉｎｇａｎｄｄｅｃｏｄｉｎｇｏｐｅｒａｔｉｏｎｓａｒｅａｐｐｌｉｅｄｏｎｔｈｅｉｎｃｏｍｉｎｇｍｅｓｓａｇｅｓ
ｏｆ蚰ｉｎｔｅｒ—ｍｅｄｉａｔｅｎｏｄｅｔｏｐｒｏｄｕｃｅｃｏｄｅｄｏｕｔｇｏｉｎｇｏ耻ｓｂｅｆｏｒｅｆｏｒｗａｒｄｉｎｇ．ＮｅｔｗｏｒｋｃｏｄｉｎｇｈａｓｍａｎｙａｄｖａｎｔａｇｅｓｏＶｅｒｃｏｎＶｅｎｔｉｏｍＩｒｏｕｔ—ｉｎｇ?８ｕｃｈａｓｐｒｏｖｉｄｉｒｌｇｈｉｇｈｅｒｎｅｔｗｏｒｋｔｈｒｏｕｇｈｐｕｔ，ｕｓｉｎｇｂａｎｄｗｉｄｔｈｅｆｆｉｃｉｅｎｔｌｙａｎｄｂａＩａｎｃｉｎｇｔｈｅｔｒａｆｆｉｃ，ｅｔｃ．１ｎｔｈｉｓｐａｐｅｒ，ｗｅｐｒｅｓｅｎｔｔｈｅｂａｓｉｃｔｈｅｏｒｙａｎｄｍａｉｎａｄｖａｎｔａｇｅ８ａｎｄｄｉｓａｄｖａｎｔａｇｅｓｏｆｎｅｔｗｏｒｋｃｏｄｉｎｇ，ａｎｄｔｈｅｎｄｅｓｃｒｉｂｅｔｈｅｋｅｙａｌｇｏｒｉｔｈｍｓａｓｗｅＵａｓｇｉｖｉｎｇａｇｅｎｅｒａｌｒｅｖｉｅｗｏｆｓｏｍｅｔｙｐｉｃａｌｉｍｐｌｅｍｅｎｔａｔｉｏ∞ｏｆｎｅｔｗｏｆｋｃｏｄｉｎｇｉｎｄｅｔａｉｌ．Ｉｎｔｈｅｅｎｄ，ｔｈｅｄｉｒｅｃｔｉｏ∞ａｎｄｆｕ—ｔｕｒｅｗｏｒｋｓａｒｅｓｕｍｍａｒｉｚｅｄ．
Ｋｅｙｗｏｒｄｓ：ｎｅｔｗｏｒｋｃｏｄｉｎｇ；ｒａｎｄｏｍｎｅｔｗｏｒｋｃｏｄｉｎｇ’ｉｎｆｏｒｍａｔｉｏｎｎｏｗ；ｍｕｌｔｉｃａｓｔ
’
ｌ引言
传统的多播传输是通过构造多播树实现的．典型的多播树，如最小费的Ｓｔｅｉ地ｒ树，其构造过程一般是个ＮＰ完全问题［１］，因此大多数的近似算法［１４］，均不能使多播传输达到。最大流最小割”（ＭＡＸ—ＦＬ０ｗＭＩＮ－ｃＵＴ）定理［．］确定的最大理论传输容量．这主要是因为：现有通信网络中使用的路由机制认为网络中传输的信息是不能叠加的，只能进行存储和转发．然而，香港中文大学Ｒ．Ａｌｓｈｗｅｄｅ等在２０００年的ＩＥＥＥ信息论会刊上发表的一篇著名论文［５］，彻底推翻了这一结论．该文首次提出了网络编码（ＮｅｔｗｏｒｋＣｏｄｉｎｇ）的概念并从理论上证明：如果允许网络节点对传输的信息按照合适的方式进行编码处理（如模二加、有限域上的运算等），而非限于存储和转发，则基于该方式的网络多播总能够实现理论上的最大传输容量．网络节点对传输信息进行操作和处理的过程，就称为网络编码．
网络编码彻底改变了通信网络中信息处理和传输的方式，是信息理论研究领域的重大突破，已经引起学术界广泛关注和高度重视．国际许多著名大学和研究机构，国外许多著名大学，如普林斯顿大学旧、麻省理工大学【７］、瑞士ＥＰＦＬ学院‘ａ１等以及多家ＩＴ公司的研究中心，包括微软研究院口】、贝尔实验室‘＂］、ＡＴ８汀的香农信息实验室［１１］等都在积极开展对网络编码理论和应用的研究｝网络编码也逐渐引起了国内学术界的关注和重视，我国的清华大学（１２】、南京大学【ｌ副、西安电子科技大学［１‘］等对网络编码进行了探索．
本文将全面综述网络编码的研究现状，以期能更进一步推动国内对网络编码这一新兴网络技术的关注与研究．文章按如下方式组织：第２节介绍网络编码的基本概念与优缺点，第３节建立网络编码的原理模型，给出线性网络编码的数学描述；第４节归纳几种主要的线性网络编码构造算法，其中重点介绍多项式时间算法，一种实用的分布式网络编码方法：随机网络编码，将在第５节中提出；第６节总结网络编码的典型应用，包括无线网络，应用层多播，Ｐ２Ｐ文件共享等；文章的最后对网络编码的研究方向进行了展望．
２网络编码的基本概念和优缺点
２．１基本概念
Ｒ．Ａｌｓｈｗｅｄｅ等嘲以著名的“蝴蝶网络”（ＢｕｔｔｅｒｎｙＮｅｔ一
收稿日期；２００６．１１．２９基金项目：国家自然科学基金项目（６０５７２０４９）资助；华为公司科技基金项目（ＹＪＣＢ２００６０４９ＲＥ）资助．作者简介。陶少国，男，１９８０年生，博士研究生，研究方向为下一代网络关键技术，网络编码理论与应用；黄佳庆．男，１９７２年生，副教授，研究方向为网络编码．ＰｚＰ．多播；杨宗凯，男。１９６１年生，教授，博士生导师。研究方向为下一代网络，电子商务。远程教育；乔文博，男。１９８３年生，硕士研究生，研究方向为网络编码与Ｐ２Ｐ应用；熊志强，男，１９７９年生，博士研究生，研究方向为下一代网络关键技术，网络编码理论与应用．
小型微型计算机系统２００８年
ｗｏｒｋ）模型为例，阐述了网络编码的基本原理．如图１所示的。单信源二信宿”蝴蝶网络。设各链路容量为ｌ，ｓ是信源节点，Ｙ和Ｚ是信宿节点，其余为中间节点．根据“最大流最小割”定理，该多播的最大理论传输容量为２，即理论上信宿Ｙ和Ｚ能够同时收到信源ｓ发出的２个单位的信息，也就是说能同时收到ｂｌ和ｂ２．图１（ａ）表示的是传统的路由传输方式，节点ｗ执行存储和转发操作．假定ｗ转发信息ｂ１，则链路ＷＸ、ＸＹ和Ｘｚ上传输的信息均为ｂ１，虽然信宿Ｚ收到ｂｌ和ｂ２，但信宿Ｙ却只能收到ｂ１（同时收到一个多余的ｂ１），因此信宿Ｙ和Ｚ无法同时收到ｂｌ和ｂ２，该多播不能实现最大传输容量．
ｂ
ｂｌｂｌ。ｂ２ｂｌ’ｂｌ＋ｂ２ｂ１．ｂ２＋ｂ２
（ａ）（ｂ）
图ｌ“单信源二信宿”蝴蝶网络
Ｆｉｇ．１
Ｂｕｔｔｅｒｆｌｙ耻ｔｗｏｒｋｗｉｔｈｏ觥ｓｏｕｒｃｅａｎｄｔｗｏｓｉｎｋｓ图１（ｂ）表示的是网络编码方法，节点ｗ对输入的信息进行模二加操作，然后将操作结果６１０６２发送至输出链路ＷＸ，然后又通过链路ＸＹ和ｘＺ，最终达到信宿Ｙ和ｚ．Ｙ收到ｂ１和６１０６２后，通过译码操作６１０（６１０６２）就能解出ｂ２，因此，信宿Ｙ同时收到了ｂ１和ｂ２．同理，信宿Ｚ也同时收到ｂ１（通过译码操作６２０（６１０６２））和ｂ２．由此，基于网络编码的多播实现了理论上的最大传输容量．
可见，网络编码的核心思想是：具备编码条件的网络节点（比如该节点的入度至少为２，如图１中的节点ｗ就具备编码条件，节点Ｘ则不具备编码条件）对接收到的信息进行一定方式的处理（编码），然后传输给下一级的网络节点。收到消息的下一级节点如果具备编码条件，又对其接收的信息按照同样的方式进行处理和传输，如此反复，直到所有经过处理后的信息都汇聚到信宿节点为止．最后，在信宿节点，通过逆过程的操作（译码），即可译出信源发送的原始信息．网络编码是发生在域凡上的操作，如果域Ｂ无限大，则运用网络编码的多播传输能达到理论上的最大传输容量等于各信宿节点的最大流的最小值，即＾＝ｍｉｎｍａｘ胁（☆），ｔｉ∈丁．
２．２主要优缺点
网络编码提出的初衷是为使多播传输达到理论上的最大传输容量，从而能取得较路由多播更好的网络吞吐量．但随着研究的深入，网络编码其它方面的优点也体现出来，如均衡网络负载、提升带宽利用率等．如果将网络编码与其它应用相结合，则能提升该应用系统的相关性能．
Ｚ。２。ｌ提升网络吞吐量．
提升吞吐量是网络编码最主要的优点．无论是均匀链路还是非均匀链路，网络编码均能够获得更高的多播容量，而且对于节点平均度数越大，网络编码在网络吞吐量上的优势越明显［１副．从理论上可证明：如果ｎ为信源节点的符号空间，ＩｙＩ为通信网络中的节点数目，则对于每条链路都是单位容量的通信网络，基于阿络编码的多播的吞吐量是路由多播的ｎ（１０９Ｉ矿１）倍‘１削．
２．２．２均衡网络负载．
网络编码多播可有效利用除多播树路径外其它的网络链路，可将网络流量分布于更广泛的网络上，从而均衡网络负载．图２（ａ）所示的通信网络，其各链路容量为２．图２（ｂ）表示的是基于多播树的路由多播，为使各个信宿节点达到最大传输容量，该多播共使用ＳＵ、ＵＸ、ＵＹ、ＳＷ和ｗＺ等共５条链路，且每条链路上传输的可行流为２Ｉ图２（ｃ）表示的是基于网络编码的多播，假定信源节点Ｓ对发送至链路ＳＶ的信息进行模二加操作，则链路ＳＶ、Ｖｘ和Ｖｚ上传输的信息均为４０６，最终信宿Ｘ，Ｙ和ｚ均能同时收到ａ和ｂ．容易看出，图２（ｃ）所示的网络编码多播所用的传输链路为９条，比图２（ｂ）的多播树传输要多４条链路，即利用了更广泛的通信链路，因此均衡了网络负载．网络编码的这种特性，有助于解决网络拥塞等问题．
（ａ）（ｂ）（ｃ）
图２单源三接收网络
Ｆｉｇ．２０ｎｅｓｏｕｒｃｅａｎｄｔＩＩｒｅｅｓｉｎｋｓｎｅｔｗｏｒｋ
２。２．３提高带宽利用李．
提高网络带宽利用率是网络编码的另一个显著的优点．在图２（ｂ）中的路由多播中，为了使得信宿Ｘ，Ｙ和ｚ能够同时收到２个单位的信息，共使用了５条通信链路，每条链路传输可行流为２，因此其消耗的总带宽为：５×２＝１０．在图３（ｃ）表示的网络编码多播中，共使用了９条链路，每条链路传输可行流为１，其消耗总带宽为：９×ｌ＝９，因此带宽消耗节省了１０％，提高了网络带宽利用率．
此外，通过网络编码，可以抵抗网络链路和节点的非各态历经失败对网络链接的影响，提高网络链接的鲁棒性，减小网络管理的开销［１扎１副．如果用在无线网络中，还能节省传输能耗，增加传输的安全性等［１９’２。］Ｉ如果用在ＰｚＰ文件共享系统中，除了能够显著提高下载效率，还能有效应对节点动态加入和离开、链路失效和网络带宽吞噬等问题ｏ】．
虽然网络编码优点突出，但运用网络编码增加了计算的复杂性，而且网路节点需要缓存足够的输入信息，因此编码操作增加了传输时延和节点的额外的Ｉ／Ｏ、ｃＰＵ消耗．一些学者对网络编码的综合性能进行了初步的研究和探讨Ｃ２ｈ捌．统计数据表明，即使应用最有效的随机网络编码，其编码和译码的时间也不容忽视［２纠．此外，应用网络编码还存在同步问题，
４期陶少国等：网络编码研究综述５８５
这主要是由于信宿节点必须等待收到足够的编码信息，才能开始译码．同步问题给在实时系统中应用网络编码提出了挑战．
３网络编码的原理和模型
如果网络节点对传输的信息进行线性操作，则称为线性网络编码（ＬｉｎｅａｒＮｅｔｗｏｒｋＣｏｄｉｎｇ）ｆ否则称为非线性网络编码．如果网络节点对信息进行操作的系数是随机选取的，则称为随机网络编码；如果是通过算法确定出来的，则称为确定性网络编码．文献［２３］证明：在有限域Ｒ中，只要域足够大，则通过合适的线性网络编码，就能使多播传输达到最大的传输容量．目前，网络编码研究均限于有限域凡中的线性网络编码．
３．１线性网络编码
设Ｇ＝（ｙ，Ｅ）表示无环有向网络图（ＤｉｒｅｃｔｅｄＡｃ”ｌｉｃＧｒａｐｈ），其中ｙ为网络节点（顶点），Ｅ＝ｙ×ｙ为通信链路（边）．设Ｓ∈ｙ为信源节点，丁ｃｙ为信宿节点的集合，任一信宿卉∈丁．ＩｙＩ表示节点的数目，Ｊ引表示链路的数目．链路ｚ＝“。口）表示链路ｚ的起点为矩，终点为口。记做ｏ（ｚ）＝“，ｄ（ｚ）＝仉ｎ“）表示节点“的输入链路的集合，其模量ＩｒＪｏ）Ｉ称为节点砧的入度，简记为毋（“）；ｒ．ｏ）表示节点越的输出链路的集合，其模量ｌｒ．（“）Ｉ称为节点“的出度，简记为色ｏ）．这些符号能组合使用，如ｒ，（Ｄ０））表示链路￡的起点Ｄｏ）的输入链路（可直接称为ｆ的输入链路或父链路）．
信源ｓ发出的信息符号，链路＃∈Ｅ传输的信息，信宿节点ｘ，Ｙ，Ｚ接收的信息，均以向量的形式取之于有限域Ｒ，该向量称为信息流（ＩｎｆｏｒｍａｔｉｏｎＦｌｏｗ）．
定义ｌ（线性编码多播）．所谓线性编码多播（ＬｉｎｅａｒＣｏｄｅＭｕｌｔｉｃａｓｔ，简称ＬＣＭ），就是给无环有向网络Ｇ＝（ｙ，Ｅ）中每
个节点Ｘ∈矿赋予一个向量空间口（Ｘ），给每条链路。饯舯∈Ｅ赋予一个编码向量ｚ（盯），使得：
１）口（５）∈Ｑ，Ｑ为信源发出的足够大的域凡上＾维符号向量空间，
２）对于每条链路ＸＹ，均有ｚ，（Ｘｙ）∈口（ｘ），
３）对于任何非源节点集合多＝ｙ＼｛Ｓ）：
＜｛ｖ仃）Ｉ？∈９｝＞＝＜｛掣（Ｘｙ）ｌＸ式９，ｙ∈多）＞，其中＜?＞表示向量张成的空间．
ＬｃＭ提供了以信息流描述网络中信息传输和编码操作的统一方式．
定义２（本地编码向量）．在ＬＣＭ中，如果将链路ｆ∈Ｅ上传输的信息流当作是ｆ的输入链路ｎ（ＤＱ））上传输信息的线性组合，则该线性组合系数构成的向量称为链路。的本地编码向量（ＬｏｃａＩＣｏｄｉｎｇＶｅｃｔｏｒ）：
厶：ｎ（口（￡））一ｒ，ｉ＝Ｉｒ，（ｏ（＃））Ｉ
定义３（全局编码向量）．设６＝［６ｌ，６２，…，６｜］表示ＬＣＭ中信源Ｓ输出的Ｒ上的是维信息漉向量，如果将链路ｅ∈Ｅ上传输的信息流当作是信源向量６各元素的线性组合，则该线性组合系数构成的向量称为链路。的全局编码向量（Ｇｌｏｂ—ａＩＣｏｄｉｎｇＶｅｃｔｏｒ）：
毋：ｒ．（Ｓ）一ｐ，ｉ＝Ｉｒ＾岱）Ｉ
图３（ａ）表示的ＬｃＭ，信源发送的信息流为［６１，６２］．各链路对应的本地编码向量和全局编码向量分别如图３（ｂ）和图３（ｃ）．链路Ｔｗ传输信息流为ｂ１，ｕｗ传输信息流为ｂ２．链路ＷＸ上传输的信息流６１０６２可看作是Ｔｗ和ｕｗ上信息的线性组合，其组合系数均为ｌ，因此链路ｗＸ的本地编码向量为［１，１］，如图３（ｂ），另外，ｗｘ传输的信息６１０６２也可看作是信源ｓ发出信息流向量瞳１，６２］的元素ｂ１和ｂ２的线性组合，其线性组合系数也均为１，因此其全局编码向量为也［１，１］，如图３（ｃ）．
ｂｌ，ｂｌ＋ｂ２ｂｌ＋ｂ２ｊｂ２
（ａ）（ｂ）（ｃ）
图３本地编码向量和全局编码向量
Ｆｉｇ．３．ＬｏｃａｌｃｏｄｉｎｇｖｅｃｔｏｒａｎｄｇｌｏｂａｌｃｏｄｉｎｇＶｅｃｔｏｒ
本地编码向量表示的是链路上传输的信息流与该链路的输入链路传输的信息流之间的映射关系｝全局编码向量表示的是链路上传输的信息流与信源发送的信息流之间的映射关系．通过这两种向量，均可以构造出链路上传输的信息流向量，显然它们之间能够相互转化．若毋Ｑ），垂（Ａ）分别表示链路ｆ，Ａ∈ｒＪ（００））的全局编码向量，厶（加）表示链路户ｆ∈ｎ（口Ｑ））的局部编码向量，则有：
舒Ｑ）＝．。蒿…厶（卸）ｇ（参）
１ｃ‘Ｊ…’
３．２数学模型
设ＬｃＭ的最大理论传输容量为＾，信源节点ｓ发出的符号向量为６＝［６１，如＇．．?．６．］，则在信源Ｓ与每个信宿句∈？之间均能建立＾条不相交的路径簇，该路径簇记为（Ｓ，☆）．ｐ＝［例，佛，…，觑］丁表示路径簇（Ｓ，☆）上各路径的最后一条链路上传送的信息流的集合，胁矗，优矗’．．?，拼＆］ｒ是第；条链路的全局编码向量，则该链路传输的信息流可表示为：
∥＝ｍ矗６ｌ＋研毛如＋…＋拼矗“
对于信宿节点‘』的＾条输入链路，传输的信息流向量为：
臣习×卜
则信源发出的符号向量为矿一圻１卢．
如果尬满秩，则当收到路径簇（Ｓ，“）上＾个信息流向量Ｊ９＝［反，恁＇．．?，趣］ｒ后，信宿节点ｌｊ就能通过矿＝孵１夕译出信源发出的原始信息［６．，如＇．．?，以］．
定理ｌ（系统转移矩阵）．若ｙ表示信源发出的信息流向
５８６小型微型计算机系统２００８年
量，ｚ表示信宿节点收到的信息流向量，则ＬｃＭ系统可用ｚ＝ｙ×Ｍ表示．其中Ｍ＝月（Ｊ—Ｆ）－１Ｂｒ称为信宿ｆ对应的系统转移矩阵，，为Ｉ引×ｌＥｌ阶单位矩阵。Ａ、Ｆ和Ｂ分别为。信
源一输出链路”、“中间节点一输出链路”和信宿节点一输入链路”对应的系数转移矩阵．
文献［２４］运用离散随机过程的方法给出了ＬＣＭ系统中
转移矩阵％的构造过程，并证明，只要能够保证最终形成的转移矩阵％满秩，则对应的信宿节点通过ｙ＝ｚ×竹１就能准确译出信源发送的原始信息．
定理２（可行网络编码）．使所有信宿节点对应的转移矩阵Ｍ均满秩（ＦｕＩｌＲａｎｋ）的网络编码称为可行网络编码［２５］（ＦｅａｓｉｂｌｅＮｅｔｗｏｒｋＣｏｄｉｎｇ）．
４网络编码的构造算法
网络编码构造算法解决的主要问题是如何有效求得每条链路对应的编码向量，并运用该编码向量进行线性操作计算出链路上传输的信息向量．编码算法的复杂性是衡量网络编码能否有效实现的重要依据．典型的算法包括指数时间算法［ｚ引、多项式时间算法‘ｚ们和贪婪算法‘２３１等，其中因多项式时间算法具有较低的复杂性，因此具有重要的理论和应用价值．４．１指数时间算法
设Ｍ，Ｍ：，．．?，Ｍ…表示ＬｃＭ种各个信宿节点对应的系统转移矩阵，如果ｄｅｔ（Ｍ１）×ｄｅｔ（％）ｘ…×ｄｅｔ（Ｍ㈣）＝户≠Ｏ，则觚，№，…，Ｍ…均满秩，即所有的信宿节点均能成功译码．基于这种思想，文献［２５］在给出线性网络编码代数框架的同时提出了一种指数时间的网络编码构造算法：设导ｔ，亭ｚ’．．?，毛，行＝ＩＥＩ表示所有编码链路对应的编码向量，则必定存在函数关系：户＝，（｝ｌ，亭２，…，￡），并称使ｐ＝Ｏ的点（邑，岛，…，毛）的集合称为被“函数夕分割出来的代数簇”，因而算法的目标就是求得一个不位于“函数户分割出来的代数簇”上的点．对于“单信源行信宿”的无环有向网络，若ＬｃＭ的最大理论传输容量为＾，则在有限域ｎ（ｇ＝２脚，棚≥ｌｏｇｚ（挖＾＋１））中，通过指数时间算法总能求得各链路对应的编码向量，从而使各信宿节点能成功译码．然而该算法参变量的校验次数随着网络规模成指数增加．因此，该算法对于大规模的网络不够实用．４．２多项式时间算法
Ｐ．ｓａｎｄｅｒ等人提出另一个能够保证转移矩阵％＝以（，一Ｆ）叫矿满秩的集中式算法：多项式时间算法乜６］．该算法是线性网络编码的快速实现，其目标是在尽可能小的有限域Ｒ上快速地寻找编码向量．该算法首次将计算复杂性局限在多项式时间范围内，极大提高了网络编码的实用性．
如果ＬＣＭ的最大理论传输容量为＾，将信源ｓ和信宿ｆ∈丁之间建立的＾条无重合链路构成的路径簇（Ｓ，ｆ）记为，，对广上的链路按照拓扑排序，排序后的链路可表示为ｃ，，＃ｚ，…，“，然后依次求解各链路对应的线性操作系数向量昏，即全局编码向量．在求解系数向量时，必须保证对任意接收节点Ｉ∈丁存在一个包含＾条链路的集合ｃＩ，即是广中＾条路径上的最新构造出全局编码向量的ＪＩｌ条链路，一条路径上一条链路，且这＾条链路的全局编码向量Ｇ＝｛９０）ｌｅ∈Ｃ）是Ｆ＾的一个基．因此，当计算完成时，Ｇ∈ｒ，（ｔ），形成的Ｇ就是转移矩阵Ｍ，则信宿ｆ通过％就可以译出信源发出的信息向量．多项式时间算法的主要步骤包括：
１）构造信源Ｓ至各个信宿节点ｆ的路径簇（ｓ，ｔ）；
２）将路径簇上的链路按照拓扑排序；
３）依次寻找各个链路的全局编码向量，使得各路径簇（Ｓ，ｔ）上最新链路的编码向量能够形成一个基，以此确保最终形成的转移矩阵满秩．此步为多项式时间算法的核心和重点．多项式时间网络编码算法的时间复杂度为０（ＪＥＪ．１丁Ｊ＾２），最坏情况下为ｏ（ＩＥ｜．Ｉ丁Ｉ＾饥＋Ｉ丁ｌ２））．
４．３其它算法
ＬｃＭ能够实现的最大理论容量为各信宿节点的最大流的最小值‘朝，即＾＝ｍｉｎｍａｘ以仉ｃ，（矗），ｆｆ∈丁．然而，文献［２３］证明了一个更理想的多播容量上限：ＬＣＭ可以实现信宿节点各自的最大流，即珐一ｍａｘ露。埘（“），☆∈？，并称这样的线性编码多播为“通用ＬＣＭ”（ＧｅｎｅｒｉｃＬＣＭ）．显然“通用ＬＣＭ”可以实现多速率的网络编码，能够取得较ＬＣＭ更好的多播传输速率和网络吞吐量．文献［２３］给出了无环有向网络中实现“通用ＬＣＭ”的贪婪算法和启发式算法，但由于计算量大，实现过程过于复杂，因此并不实用．但该文作为对多速率网络编码的首次探索，仍具有重要的借鉴意义．
根据非源节点输入链路的编码向量形成的向量空间，线性网络编码分为线性多播（ＬｉｎｅａｒＭｕｌｔｉｃａｓｔ）、线性广播（Ｌｉｎ．
ｅａｒＢｒｏａｄｃａｓｔ）和线性扩散（ＬｉｎｅａｒＤｉｓｐｅｒｓｉｏｎ）［２７］．在线性网络编码中，每条链路。均存在一个对应的全局编码向量函，该
向量与信源发送的信息流向量（有限域凡上的＾维信息向量）的内积即为链路ｅ上传输的信息流．对于任何非信源节点丁，均存在一个由其输入链路ｃ的全局编码向量靠的集合构成的向量空间为ｎ＝＜｛函Ｉｃ∈ｒ』（丁）｝＞，该向量空间可分为如下３类：
（１）对于每个ｍａ】【以瑚（了１）≥＾的非源节点Ｔ，有ｄｉｍ
（ｙｒ）＝ＪＩｌＩ
（２）对于任意非源节点丁，有ｄｉｍ（ｎ）；ｍｉｎ｛＾，ｍａｘ胁（丁）），
（３）对于任意非源节点的集合多，有ｄｉｍ（＜Ｕ７．∈争％＞）＝ｍｉｎ｛＾，ｍａｘ胁（．多多））Ｉ
满足条件（１）、（２）、（３）的网络编码分别称为线性多播、线
性广播和线性扩散．显然条件（３）辛（２）寺（１），也就是说线性扩散是线性广播的特例，线性广播是线性多播的特例，但反之不成立．线性广播说明了通过增加信源发送的信息流向量的维数，可以提升传输速率｝线性扩散能保证信源节点以互补的形式发送信息流．文献［２７］给出了实现线性多播、线性广播和线性扩散的网络编码构造算法．
５网络编码的分布式实现：随机网络编码
虽然多项式时间算法能够有效地构造编码向量，确保信
宿节点成功译码，但由于它是集中式算法，需对网络拓扑结构
４期陶少国等：网络编码研究综述５８７
有全面的了解．因此，从实用的角度来看，多项式时间算法对拓扑结构动态变化或规模很大的网络，实用性并不强．Ｍ．Ｍｅｄａｒｄ提出了一种更一般的分布式网络编码的实现方法：随机网络编码（ＲａｎｄｏｍＮｅｔｗｏｒｋＣｏｄｉｎｇ，简称ＲＮＣ）嘲，该方法基于一种随机选择编码向量的策略：对于除了信宿节点外的所有中间节点，只要在一个足够大的有限域乃上随机选择它们输入链路到输出链路的映射，而且各节点映射关系的选取是相互独立的，就能以较高概率使各个信宿节点对应的系统转移矩阵Ｍ满秩，即各信宿节点能以较高的概率成功译码．图４表示的是随机网络编码，各个链路上的系数向量（全局编码向量）和信源发送的信息进行同步传输，各个系数向量亭。，岛，．．?，￡在有限域凡中随机选取，在通过编码节点时，系数向量根据随机选取的映射关系进行更新，最终的各信宿节点收到的输入信息将包含输入链路对应的全局编码向量和信源发送的信息流．
图４随机网络编码
Ｆｉｇ．４Ｒａｎｄｏｍｎｅｔｗｏｒｋｃｏｄｉｎｇ
定理３（ＲＮｃ译码成功率）．对于信源相互独立或线性相关的ＬＣＭ，所有节点的全局编码向量都在有限域Ｆｆ上独立均匀选取（某些节点的编码向量可固定，只要这些固定向量对整个系统的网络编码是可行的），则接收节点能以最小概率（１一ｄ向）’译出信源发送的信息，其中ｇ＞ｄ为编码符号域的大小，ｄ是信宿节点的数目，叩是随机选取编码系数的链路的数目．
在ＲＮＣ中，只要当编码符号域ｇ足够大，总可保证接收节点以较高概率成功译出信源发送的信息．理论上可证明：当符号域大小为ｇ＝２１６时，任何接收节点均可以至少以概率９９．６％成功译码啪】．文献［３０］指出，在实际应用环境中，符号域的大小为口＝２８就足够了．在采用ＲＮＣ的线性编码多播中，多个信源可以是独立的。也可以是线性相关的．对于线性相关的信源，ＲＮＣ可以起到信息压缩的作用．此外，ＲＮｃ是网络编码的分布式实现，无需事先获知整个网络的拓扑信息，尤其适用于拓扑结构动态变化或者大规模的网络．对于存在网络节点和链路失效的网络，ＲＮＣ可以利用整个网络的剩余容量来获得网络的最佳容量，从而提高多播传输的鲁棒性．与时间多项式算法总能保证成功译码不同，在ＲＮｃ中，虽然不能确保最终形成的系统转移矩阵脱满秩，但由于是随机选择编码向量，其复杂性与确定性算法相比要低得多，更易于实现，而且９９％以上的译码成功率在一般情况也足以满足需求．因此，随机网络编码具有重要的理论价值和应用价值，得到了广泛的关注和应用，如微软提出的Ｐ２Ｐ文件共享系统Ａｖａｌａｎｃｈｅ便是基于ＲＮＣ的典型应用‘”．
６网络编码的优化：最小代价网络编码
６．１网络编码复杂性的影响因素分析
由于网络编码涉及信息缓存和矩阵运算，其额外开销比传统路由传输要大，而且即使是最简单的随机网络编码，其编码和译码的时间也不能忽视［３“．因此，降低网络编码的复杂性，实现最小代价的网络编码（ＭｉＩｌｉｍｕｍ—ｃｏｓｔＮｅｔｗｏｒｋｃｏｄ—ｉｎｇ），对促进网络编码的大规模应用有重要的意义．影响网络编码实现复杂性的主要因素有：编码构造算法、编码操作数以及有限域的大小等．
６．１．１编码构造算法对网络编码复杂性的影响．
编码构造算法是网络编码实现的核心。其作用是在有限域内Ｒ内选取合适的线性运算系数，并对节点输入信息进行线性叠加，使得每个信宿节点收到编码信息后能够通过解矩阵方程而正确译码（如多项式时间算法）。或以较高概率成功译码（如ＲＮｃ）。寻找复杂性低的编码算法是网络编码研究领域永恒的主题．从最初的指数时间算法到集中式的多项式时间算法，再到分布式的ＲＮＣ，编码构造算法一直是网络编码研究的重点和难点之一．
６．１．２编码操作数对网络编码复杂性的影响．
在ＬＣＭ传输中，网络节点首先需要缓存足够的信息，然后选择编码变量并对缓存信息进行线性运算，最后再发送至该节点的输出链路．无论是缓存信息还是线性运算，频繁的编码操作会增加实现的代价（Ｉ／Ｏ和ｃＰｕ消耗）．比如在光网络（ＯｐｔｉｃａｌＮｅｔｗｏｒｋ）中，因为通信链路传输光信号，因此网络节点必须将先进行“光一电”转换，将收到的光信号转换为电信号，然后再利用网络编码，构造输出信息，最后进行逆过程的。电一光”转换，将编码信息以光信号的方式传送至输出链路．可见，在这种网络中，除了编码计算外，编码节点进行光电之间的转换也增加了编码的时延以及信息处理的复杂性．因此，如果能够在不影响多播效率的情况下，适当减少网络编码操作数，则能降低网络编码的实现复杂性．可从三个角度分析编码操作数：信息分组、编码链路和编码节点，其中从信息分组的角度减少其操作数目是降低编码操作复杂性最理想的方式，但是分析的难度较大，一般均从减少编码链路或者节点的数目来考虑．
６．１．３有限域大小对网络编码复杂性的影响．
网络编码是发生在有限域Ｂ上的运算，也就是说信源发送的信息，链路传输的信息，编码节点的运算准则等都与Ｒ有关，有限域大小是衡量网络编码方法好坏的重要因素之一．若有限域Ｒ的大小口＝２“（称研为域Ｒ的字母表长度），则每个节点口需要西ｏ）拼个存储单元来缓存来自输入链路的信息．显然优越大，则节点口所需缓存越多，系统的Ｉ／ｏ开销就越大，同时运算的复杂性也相应增加．但是如果ｇ过小，将
５８８小型微型计算机系统２００８年
会使译码成功率下降［２”．也就是说，域大小和译码成功率是并存的一对矛盾．因此，在保证足够的译码成功率的前提下，应尽量减少有限域的大小．
６．２基于简单网络的解决方案
直接分析一般拓扑结构网络的网络编码，并对其方案进行优化，将是非常困难的事情．一种可供借鉴的思想就是：将普通网络转化为某种易于表达，且各网络节点具有共同特征的“简单网络”．利用这种思想，文献［３１］提出了一种基于简单网络（ｓｉｍｐｌｅＮｅｔｗｏｒｋ）的最小代价网络编码解决方案．该方案实现的核心思想是将普通网络转化为所有节点度数（入度与出度之和）不超过３的简单网络．简单网络中参与网络编码的节点定义为口节点，通过求解口节点的数目，就能确定其所需的网络编码节点数．文献［３２］证明：如果ＬｃＭ的最大传输容量为．Ｉｌ，信宿节点数目为优，则：
（１）对于无环有向网络，其所需编码节点数上限为＾‰。，（２）对于有环有向网络，其所需编码节点数上限为（２Ｂ＋１）＾３ｍ２，其中Ｂ表示去环所需删除的最少链路数．
将普通网络转化为简单网络，其网络拓扑变得十分简单，但一个不容忽视的问题就是：简单网络的规模（节点数）比原普通网络却膨胀了许多，也就是说网络编码的代价被放大了，。简单网络”的最小代价并不等于原网络的最小代价．但是，将网络“简化”处理的思想在方法论上具有重要的借鉴意义，为最小代价的网络编码提供了研究方向．
６．３基于信息流分解的解决方案
信息流分解（ＩｎｆｏｒｍａｔｉｏｎＦｌｏｗＤｅｃｏｍｐｏｓｉｔｉｏｎ）模型从另一个角度对网络拓扑进行简化处理ｏ”．通过信息流分解，可将普通网络分解为一些具有共同特征的子树图．
信息流分解的基本原理是按照网络中信息流的特征和共性，将原网络节点划分为一系列的子树图，这些子树图中的节点拥有相同的编码向量，子树里面的节点的拓扑结构不影响整个系统的多播传输，因此每个子树可以当作一个节点来处理．将原网络转化为子树网络，大大简化了问题的复杂性．既然子树图中的节点共享相同的编码向量，如果ＬＣＭ的最大传输容量为＾，则原网络的每个信宿节点一定位于＾个不同的子树中，因此如果包含相同信宿节点的子树拥有不同的编码向量就能保证该信宿节点最终形成的转移矩阵满秩．由此，可以应用图顶点染色理论；若将每个子树用一种颜色表示，则只需将包含相同信宿节点的子树染成不同的颜色即可．应用该理论，文献［３４］指出：在信源节点为２，信宿节点数目为Ⅳ的ＬＣＭ中，则有限域大小ｑ≤√２Ⅳ一７／４＋１／２即可使信宿节点成功译码．
６．４基于最小代价函数的解决方案
借鉴路由多播的最小代价树，文献［３５］运用线性规划理论给出了网络编码系统的代价函数．假定多播速率为＾，＾（?）表示链路（ｉ，＿『）上信息传输的代价函数，勒表示网络编码多播系统中各个链路的实际传输速率。则网络编码系统的线性规划模型可表示为：
ｍｉｎ∑广（２村）
“．ｊ）∈￡’
时．锄≥ｚ】｝！ｆ）Ｖ（ｆ。Ｊ）∈Ｅ，ｆ∈丁
∑硝’一∑ｚ妒＝砰’Ｖｉ∈ｙ，ｆ∈丁
“ｌ（ｆ?Ｄ∈暑｝｛ｊｌ“?Ｊ）∈置｝
ｄｊ≥ｚ矿≥ｏＶ（ｉ，歹）∈Ｅ，ｆ∈丁
ｆ＾矿ｉ＝ｓ
其中：耐ｏ＝．｛ｏ
【一＾矿ｆ：丁
在上述模型的基础上，文献［３６］给出了基于线性代价函
数和凸代价函数的两种分布式算法，而且该算法能够兼容一般的路由多播．
此外，Ｋ．Ｂｈａｔｔａｄ从另外的角度描述了网络编码的代价问题［３７］：给ＬｃＭ中的每条传输链路一个相应的向量兄，该向量包含２Ｉ引一１个元素，每个元素表示由信宿节点集合Ｔ的幂集元素节点对应的流量之和．然后基于该向量给出信息流的链路约束（ＥｄｇｅＣｏｎｓｔｒａｉｎｔｓ）、路由约束（ＲｏｕｔｉｎｇＣｏ小ｓｔｒａｉｎｔｓ）和节点约束（ＮｏｄｅＣｏｎｓｔｒａｉｎｔｓ），由此可将网络编码转化为线性规划问题，但该文未给出线性规划的目标函数．
７网络编码的应用
网络编码虽然起源于多播传输，主要是为解决多播传输中的最大流问题。但是随着研究的不断深入，网络编码与其它技术的结合也越来越受到人们的关注．下面将以无线网络、应用层多播和Ｐ２Ｐ文件共享为例，总结网络编码的几静典型应
用?
ｔ
７．１无线网络
由于无线链路的不可靠性和物理层广播特性，应用网络编码，可以解决传统路由、跨层设计等技术无法解决的问题．具体来说，网络编码在无线网络中可以提高网络的吞吐量，尤其是多播吞吐量；可以减少数据包的传播次效，降低无线发送能耗；采用随机网络编码，即使网络部分节点或链路失效，最终在目的节点仍然能恢复原始数据，增强网络的容错性和鲁棒性｝无需复杂的加密算法，采用网络编码就可以提高网络的安全性等．文献［３８．４０］等对网络编码在无线自组织网络（ＷｉｒｅｌｅｓｓＡｄＨｏｃＮｅｔｗｏｒｋｓ）、无线传感器网络（ｗｉｒｅＩｅｓｓＳｅ璐ｏｒＮｅｔｗｏｒｋｓ）和无线网状网（ＷｉｒｅｌｅｓｓＭｅｓｈＮｅｔｗｏｒｋｓ）中的应用进行了探讨．
７．１．１网络编码在无线自组织网络中的应用．
Ｊ．Ｙｕａｎ提出了一种利用网络编码优化的流路由方法［‘副，以此来提升ＡｄＨｏｃ网络的多播吞吐量．该方法基于一种在网络层和物理层平衡链路带宽供需的跨层优化策略。由于网络编码增加网络的复杂性，Ｋｕｎｇ等把网络链路划分为两类：进入中间节点的链路和进入信宿节点的链路［柚］，只需要在进入中间节点的链路进行网络编码即可．而对进入信宿节点的链路，只用采用路由策略，这大大降低了网络编码的复杂性．Ｙ．Ｗｕ和Ｃｈｏｕ在ＡｄＨｏｃ多播方面提出了应用网络编码的最小化能量解决方法［．３】，使得传输每比特信息消耗的能量最小，从而节省ＡｄＨｏｃ多播传输的能耗．此外，还有一些学者研究了如何利用网络编码增加无线自组织网多播传输的鲁棒性问题［“］，如Ｃｈｅｎ等人研究在分布式天线系统和多入
４期陶少国等：网络编码研究综述５８９
多出系统（ＤＡＳ＿ＭＩＭＯ）中，引入网络编码的概念，经过理论推导和实验仿真，证明了无论有无辅助天线，网络编码都能提高网络的性能，尤其是减小系统丢包损耗．
７．１．２网络编码在无线传感器网络中的应用．
相对于ＡｄＨｏｃ网络，无线传感器网络密度较大，移动性不强，通常运行在无人值守的恶劣甚至危险的远程环境中，能源无法替代，设计有效的策略延长网络的生命周期成为无线传感器网络的核心问题．ＭＩＴ的Ｐｅｔｒｏｖｉｃ等人提出了一种结合网络编码的对无线信号不进行调制的策略［．钉，并证明：运用分布式随机网络编码，未经调制的无线信号能够达到经过调制的无线信号一样的吞吐量，这样就能节省大量因为模拟器件进行调制而消耗的能量和降低节点的成本．传感器网络需要把节点资源整合起来。实现一个可靠和健壮的网络，基于此种想法，文献［４６］提出了一种结合分布式源编码和网络编码的优化算法，目的是用来提高传感器网络的容错性和可靠性，同时对分布式源编码的压缩效率和鲁棒性进行了折中考虑．
７．１．３网络编码在无线网状网中的应用．
Ｋａｔｔｉ等提出的基于机会的网络编码方法（ＣＯＰＥ）ｎ７］首次研究了网络编码在无线环境中协议层面上的具体实现向题．在ｃＯＰＥ协议中，每个节点对传输媒体进行侦听，获得它的邻居节点的状态信息。决定进行编码的机会，并在本地的ＦＩＦＯ缓存结构内进行编码，然后进行基于机会的路由．ＣＯＰＥ协议要求每个节点利用本地信息各自决定哪些数据包需要进行编码以及如何进行编码．灵活的设计使得即使在网络交通需求未知或者网络流量剧增、或者发送／接收方动态变化的情况下，ＣＯＰＥ协议仍能有效的支持多路单播流．然而该协议需要节点存储数据包并进行编码，如果网络出现拥塞，可能就会耗费较多的节点存储空间．另外，文件共享是无线网状网的一种典型应用，为了评估网络编码对该应用的影响，Ｈａｍｆａ在理想化ＭＡＣ协议基础上开发了特定的仿真平台［３＂，分别比较了服务时间等性能在节点个数、盲转发（ＢｌｉｎｄＦ０ｒｗａｒｄｉｎｇ）和选择性转发（ｓｅｌｅｃｔｉｖｅＦｏｒｗａｒｄｉｎｇ）情况下的表现．实验结果表明应用网络编码得到的改进虽然不如在有线网络中显著，但仍能在很大程度上提高吞吐量、缩短服务时间．
７．２应用层多播
虽然网络层多播（ＮｅｔｗｏｒｋＬａｙｅｒＭｕｌｔｉｃａｓｔ）被认为是提供一到多或者多对多服务的最佳方式，但是由于技术上和非技术上的原因导致网络层多播并没有在目前的Ｉｎｔｅｒ肚ｔ上碍到广泛的实现．因此，出现了一种替代的解决方案就是：把多播服务从网络层转移到应用层作为应用层服务实现，即应用层多播（ＡｐｐｌｉｃａｔｉｏｎＬａｙｅｒＭｕｌｔｉｃａｓｔ）．网络层多播中的信息流由路由器转发，而在应用层多播中则由端主机转发，端主机具有一定的计算能力，这为网络编码提供了良好的应用环境．而且，应用层多播利用的覆盖网络的拓扑不如物理层那样固定，可以按需变化，这也恰好可以利用网络编码对动态网络适应性强的优势．
Ｙ．Ｚｈｕ给出了一个基于网络编码的应用层ＬＣＭ的完整实现Ｈ引，其实现过程主要包含两个步骤：
（１）首先构造包含所有覆盖节点的“基本图”（Ｒｕｄｉｍｅ加ｔａｒｙＧｒａｐｈ），然后在。基本图”的基础上构造“基本树”（Ｒｕｄｉ—ｍｅｎｔａｒｙＴｒｅｅ），最后通过基础树构造“２冗余网络多播图”．拓扑结构符合。２冗余网络多播图”（２一ＲｅｄｕｎｄａｎｔＮｅｔｗｏｒｋＭｕｌｔｉｃａｓｔＧｒａｐｈ）的覆盖网络，其所有覆盖节点的入度或出度均不超过２．
（２）由于“２冗余网络多播图”拓扑结构较为简单，可以方面的使用线性网络编码．
通过对网络层多播，普通应用层多播和应用层ＬＣＭ的各种传输性能进行了对比测试，结果表明应用层ＬＣＭ在网络吞吐量、资源利用率等方面的性能要优于网络层多播和普通应用层多播．但是在传输迟延和信息冗余等方面不够理想．大多数情况下，应用层ＬＣＭ较普通应用层多播，其吞吐量可以提升一倍．但是，Ｔ．Ｎａｄ通过实验证实［２２１，由于存在编码和译码的Ｉ／Ｏ和ＣＰＵ消耗，基于网络编码的应用层多播的传输容量往往无法达到预期．同时，该文提出了两种减少编码和译码时间的方法．一是将待编码的信息分组的数量恒定，该数量称为线性编码的度ｆ另一方面，线性运算仅仅采用简单的模二加，降低运算复杂性．
７．３Ｐ２Ｐ文件共享
据估计，截至目前为止，Ｐ２Ｐ应用占据了互联网上７０％以上的网络流量［．，】。特别是ＢＴ（ＢｉｔＴｏｒｒｅｎｔ的简称）的出现，使得Ｐ２Ｐ应用越来越广泛．但是由于人们对信息共享效率与下载速度的无止境追求，使得现有Ｐ２Ｐ越来越难以满足人们的需求，特别是由于ＢＴ容易造成带宽吞噬。使得网络环境变得拥塞不堪，而且由于存在。死档”，导致传输质量的下降．网络编码的出现，有助于从内部机制上改善Ｐ２Ｐ的传输效率，提升其性能．微软公司开发的基于网络编码的Ｐ２Ｐ文件共享系统Ａｖａｌａｎｃｈｅ表现出了较好的综合性能∞，最具代表性．
图５Ａｖａｌａｎｃｈｅ的原理
Ｆｉｇ．５Ｐｒｉｎｃｉｐｌｅｏｆａｖａｌａｎｃｈｅ
图５表示的是Ａｖａｌａｎｃｈｅ的工作原理．假设ｓｅｒｖｅｒ需要传输信息给ｃｌｉｅｎｔＡ，则首先将ｓｅｒｖｅｒ上的信息分解成＾个信息块，即Ｂ。，曰。，…，最，然后应用随机网络编码，随机选择系数ｃ１，ｃｚ，…，“，将线性网络编码后的信息Ｅｌ一日ｃｌ＋Ｂ２ｆ２＋…＋及“传送绘ｃｌｋｎｔＡ，假设ＣｌｉｅｎｔＡ又收到另外一个信息Ｅ２＝Ｂｌｆｌ’＋口２ｃ２’＋…＋Ｂ而’，该信息来自其它Ｐｅｅｒｓ或者ｓｅｒｖｅｒ．然后ＣｌｉｅｎｔＡ又随机选择编码系数ｃｌ”，ｆ２”，对Ｅｌ
５９０小型微型计算机系统２００８年
和Ｅｚ进行线性操作，将操作的结果Ｅ３＝Ｅ。ｆｌ”＋Ｅ砌”发送给ＣＩｉｅｎｔＢ，如此则ＣｌｉｅｎｔＢ又传送给其它的Ｐｅｅｒｓ．只要每一个Ｐｅｅｒ收到足够的信息，就可以通过解线性方程组译出原始信息．
文献［９］证实，如果所有的Ｐｅｅｒｓ都运用网络编码，则Ｐ２Ｐ系统的平均下载速率较仅仅在Ｓｅｒｖｅｒ进行网络编码提高了２０％～３０％，较不用网络编码时提高了２～３倍．而且，网络编码能够适应Ｐ２Ｐ系统的动态变化，如节点动态加入或离开等，使得Ｐｅｅｒｓ下载“死档”的概率大大降低．
但Ｍ．Ｗａｎｇ［２妇认为；依据Ａｖａｌａｎｃｈｅ给出的结论并没有足够的说服力，因为其忽略了网络编码运算对于ｃＰｕ和Ｉ／ｏ的消耗，而且没考虑有环链路带来的传输时延等问题．在ＡｖａＩａｎｃｈｅ的基础上，文献［２１］通过构建一个基于Ｃ＋＋真实Ｐ２Ｐ应用系统并反复试验说明：网络编码过程中的编码和译码时间不容忽视，实际情况下，运用网络编码并不能让Ｐ２Ｐ在传输性能上取得很大的提升．即便如此，Ａｖａｌａｎｃｈｅ是第一次将网络编码应用于Ｐ２Ｐ的原型系统，开创了将网络编码与Ｐ２Ｐ应用相结合的先河，具有很高的参考价值．文献［５０］也对网络编码在Ｐ２Ｐ中的应用作了进一步的研究．
７．４其它
网络编码也可用于传输的差错控制．在现有通信网络中，差错控制的方式是逐条链路进行纠错，因此某条链路的对错与其它链路无关，当这条链路出错时，别的链路没法帮助最终的信宿节点去纠正该错误．网络编码是针对网络系统进行的操作，因此通过合适的选择信源空间，可以纠正网络中几条链路上同时发生的错误，这种差错控制方式，称为基于网络编码的差错控制．Ｃａｉ和Ｙｅｕｎｇ提出了一种以网络编码为基础的新的纠错思想［５¨：当网络在某一时刻有几条链路上的信息发生错误时，只要错误链路数没有超出纠错范围，则最终信宿节点可以通过译码将错误纠正．
此外，通过网络编码可以预防链路失效对网络链接的影响，提高网络多播传输的鲁棒性［２引．文献［５２］从信息理论的框架出发分析了非各态历经链路失败恢复的网络管理问题，指出采用网络编码可以简化网络链路失败恢复管理开销，并给出了针对一条链路失败所需的子码的数目的上下界，但是未指出如何有效构造网络子码来进行基于接收节点的网络链路恢复．
８网络编码的研究方向
经过几年的快速发展，基于网络编码的新理论和新应用不断涌现，可以说，网络编码正给现有网络带来革命性的变化．但从研究的深度来看，仍处于探索阶段，还存在一些尚未解决的问题或者尚未探索的领域．在本文的最后，将根据目前的研究现状以及相关学者提出的预测，对网络编码的研究趋势进行展望．
８．１多源网络编码的研究
目前网络编码的研究基本上局限于单源多播（Ｓｉｎｇｌｅ—ｓｏｕｒｃｅＭｕｌｔｉｃａｓｔ），对于多源多播（Ｍｕｌｔｉ—ｓｏｕｒｃｅＭｕｌｔｉｃａｓｔ），特别是对于信源数目大于２的网络编码多播，研究不够充分．
文献［３３，５３］对２信源的网络编码进行了初步的研究，但没有推广到更一般情况下的多源多播．多源多播是普遍存在的，如多方会议、网络游戏、协同工作等都是多源多播技术在实际生活和工作中的体现，因此研究多源网络编码有重要的实际意义．
８．２非线性网络编码研究
虽然线性网络编码能够实现多播传输的理论最大流，并提出了几种实现ＬＣＭ的有效方法，如时间多项式算法和随机网络编码，但非线性网络编码的性能特征究竟如何，目前在这方面的研究还没有起步．一般而言，非线性编码无论是从系统建模，还是算法求解等方面，均表现出较高的要求和难度．非线性网络编码以及其延伸的应用也必然是未来的研究方向之一．
８．３网络编码的具体实现
现在已经提出了很多网络编码方法，有集中式线性网络编码、分布式随机网络编码，但是要在实际网络环境中实现网络编码，需要考虑诸如同步、线性独立的编码系数选择、开锖控制等问题．网络编码在实际网络环境（包括有线和无线）中如何实现是一个很迫切的问题，也是网络编码研究的最终目的和归宿．因此，网络编码的具体实现也是很有意义的研究方向．
８．４降低网络编码的复杂性
采用网络编码可以在很大程度上提高网络性能，但设计和实现上的复杂性也随之增加，如何在不显著增加网络开销的情况下，综合考虑效率和性能，如何实现最小代价的网络编码［３７１等问题是将来需要进行深入研究的方向．研究降低网络编码的复杂性，实现最小的代价的网络编码，具有重要的理论意义和实用价值．
８．５网络编码在安全方面的研究
网络的安全问题是近来的研究热点，而网络编码在安全方面的应用也吸引了一些敏锐研究者的目光［＊ｓ钉，可以预见，对无线网络编码在安全方面的研究会是将来的一个研究热点．
虽然已经对网络编码理论和应用进行了广泛的研究，并从理论模型上证实了运用网络编码能提升网络的性能，但验证的步骤或模拟的环境，大多基于若干假设或理想化的模型，与实际的应用环境还有一定的差距，由此得出的某些结论尚存局限性．此外，研究过程大多基于理论上定性的分析，缺乏定量的研究．因此，将网络编码应用于实际，构建基于网络编码实用系统，还有待更严格、更深入、更广泛地进行研究与实践．
综上所述，网络编码作为通信网络中信息处理和传输理论研究的重大突破，具有重要的理论价值和广阔的应用前景，已被认为是下一代网络关键技术之一．随着网络编码研究的不断深入，网络编码技术一定会从理论走向实用，而且其应用领域必定会越来越广泛．
Ｒｅｆｅｒｅｎｃｅｓ：
［１］ＲａｍａｎａｔｈａｎＳ．Ｍｕｌｔｉｃａｓｔｔ坤ｅｇｅｎｅｒａｔｉ咖ｉｎｎｅｔｗｏｒｋｓｗｉｔｈ
４期陶少国等：网络编码研究综述５９ｌ
ａｓｙｍｍｅｔｒｉｃｌｉｎｋｓ［Ｊ］．１ＥＥＥ／ＡｃＭＴｒａｎｓ，Ｎｅｔｗｏｒｋｉｎｇ。１９９６。４
（４）：５５８—５６８．
［２］Ｍｏｓｅｓｃｈａｒｉｋａｒｔｃｈｎｄｒａｃｈｅｋｕｒｉ。Ｔｏ－ｙａｔ
ｃｈｅｕｎｇ．ｅｔａ１．Ａｐ．ｐｒｏｘｉｆｎａｔｉｏｎａｌｇｏｒｉｔｈｍｓｆｏｒｄｉｒｅｃｔｅｄｓｔｅｉｎｅｒｐｒｏｂｌｅｍｓ［Ｃ］．ＮｉｎｔｈＡｎｎｕａＩＡＣＭ—ＳＩＡＭＳｙｍｐｏｓｉｕｍｏｎＤｉｓｃｒｅｔｅＡｌｇｏｒｉｔｈｍｓ（Ｓ０一ＤＡ１９９８）。１９９８，１９２．２００．
［３］Ｌｅｏｎｉｄｚｏｓｉｎ，ＳａｍｉｒＫｈｕｌＩｅｒ．Ｏｎｄｉｒｅｃｔｅｄｓｔｅｉ肿ｒｔｒｅｅｓ［ｃ］．１ｎｉ１３ｔｈＡｎｎｕａｌＡＣＭ?ＳＩＡＭＳｙｍｐｏｓｉｕｍｏｎＤｉｓｃｒｅｔｅＡｌｇｏｒｉｔｈ脚（ＳＯＤＡ２００Ｚ）。２００２。５９—６３．
［４］Ｂｏｌｌｏｂａ。Ｂ．Ｇｒａｐｈｔｈｅｏｒｙａｎｉｎｔｒｏｄｕｃｔｏｒｙｃｏｕｒｓｅ［Ｍ］．Ｎｅｗ
Ｙｏｒｋ
ｌＳｐｒｉｎｇｅｒ．Ｖｅｒｌａｇ，１９７９．
［５］ＲｕｄｏｌｆＡｈｌｓｗｅｄｅ，Ｎｉｎｇｃａｉ．ｓｈｕｏ－ＹｅｎＲｏｂｅｒｔＬｉ，ｅｔａＩ．Ｎｅｔ—ｗｏｒｋｉｎｆｏ咖ｔｉｏｎｆｌｏｗ［Ｊ］．１ＥＥＥＴｒａ地．Ｉｎｆｏｒｍ．Ｔｈｅｏｒｙ，２０００，４６（４）ｔ１２０４—１２１６．
［６］ＡｇａｒｗａｌＡ，ｃｈａｒｉｋａｒＭ．Ｏｎｔｈｅａｄｖａｎｔａｇｅｏｆ难ｔｗｏｒｋｃｏｄｉｎｇｆ∞ｉｍｐｒｏｖｉｎｇ他ｔｗｏｒｋｔｈｒｏｕｇｈｐｕｔ［Ｚ］．ＩＩｌｆｏｒ瑚ｔｉ∞ＴｈｅｏｒｙＷｏｒｋｓｈｏｐ，２００４．ＩＥＥＥ２４?２９Ｏｃｔ．２００４．２４７?２４９
［７］ＬｕｎＤ。ＲａｔｎａｈｒＮ，ＫｏｅｔｔｅｒＲ．ｅｔａ１．ＡｃｈｉｅｖｉｎｇｍｉｎｉｍｕＩｎ—ｃ∞ｔｍｕｌｔｉｃａｓｔｌ毫ｄｅｃｅｎｔｒａ“ｚｅｄａｐｐｒｏａｃｈｂａｓｅｄｏｎｎｅｔｗｏｒｋｃｏｄｉｎｇ［ｃ］．Ｉｎ：ＰｒｏｃｅｅｄｉｎｇｓｏｆＩＥＥＥｌＮＦＯＣＯＭ，Ｍａｒ。２００５．
［８］ＦｒａｇｏｕｌｉＣ。ｓｏｌｊａｎｉｎＥ．Ｄｅｃｅｎｔ阳ｌｉｚｅｄｎｅｔｗｏｒｋｃｏｄｉｎｇ［ｚ］．Ｉｎ．ｆｏｒｍａｔｉｏｎＴｈｅｏｒｙＷｏｒｋｓｈｏｐ，２００４．ＩＥＥＥ２４—２９０ｃｔ．２００４：３１０－３１４．
［９］ＧｋａｎｔｓｉｄｉｓＣ。ＲｏｄｒｉｇｕｅｚＰＲ．Ｎｅｔｗｏｒｋｃｏｄｉｎｇｆｏｒｌａｒｇｅｓｃａｌｅｃｏｎｔｅｎｔｄｉｓｔｒｉｂｕｔｉｏｎ［Ｚ］．Ｍｉｃｒ∞ｏｆｔＲｅｓｅａｒｃｈ．２００４．
［１０］Ｂｈａｄ阳Ｓ，ＳｈａｋｋｏｔｔａｉＳ，ＧｕｐｔａＰ．Ｍｉｎ?ｃｏｓｔ５ｅＩｆｉｓｈｍｕｌｔｉｃａ３ｔ耐ｔｈ耻ｔｗｏｒｋｃｏｄｉｎｇ［Ｃ］．１Ｉｌｌ４ｔｈＩｎｔｅｒｍｔｉｏ舵ｌＳｙｍｐｏｓｉｕｍｏｎＭｏｄｅｌｉＩｌｇａＩｌｄＯｐｔｉｍｉ始ｔｉｏｎｉｎＭｏｂｉＩｅ，ＡｄＨｏｃａＩｌｄＷｉｒｅｌｅｓｓＮｅｔｗｏｒｋｓ，０３一０６Ａｐｒｉｌ２００６ｌ１—８．
［１１］Ｂａｒｒ∞Ｊ，ｓｅｒｖｅｔｔｏＳＤ．Ａｃｏｄｉｎｇｔｈｅｏｒｅｍｆｏｒ耻ｔｗ口ｒｋｉｎｆｏｒ眦一ｔｉｏｎｎｏｗ耐ｔｈｃｏｒｒｅＩａｔｅｄ∞ｕｒｃｅｓ［Ｊ］．１ＥＥＥ
Ｉｎｔｅ瑚ｔｉｏｍｌＳｙｍ．ｐｏｓｉｕｍｏｎＩｎｆｏｒｍａｔｉｏｎＴｈｅｏｒｙ（１ＳＩＴ），２００５ｔ“７?１５１．
［１２］ＺｈａｎｇＪｉｎｇ－ｙａｏ，ＦａｎＰｉｎｇ?ｙｉ．Ｏｎｎｅｔｗｏｒｋｃｏｄｉｎｇｉｎ谢ｒｅｌｅｓｓａｄ—ｈｏｃ肥ｔｗｏｒｋｓ［Ｃ］．１Ｉｌｌ２ｎｄＩｎｔｅｒｍｔｉｏｎａｌＣｏｎｆｅｒｅｎｃｅｏｎｏｂｉｌｅＴｅｃｈ∞ｌｏｇｙ，Ａｐｐｌｉｃａｔｉｏ地ａＩｌｄＳｙｓｔｅｍｓ，１５—１７Ｎｏｖ．２００５１８．［１３］ｚｈａｏＪｉｎ，ＹａｎｇＦａｎ，ｚｈａｎｇＱｉａｎ，ｅｔａ１．Ｌ１０Ｎ；ｌａｙｅｒｅｄｏｖｅｒｌａｙｍｕｌｔｉｃａ３ｔ耐ｔｈ耻ｔＷｏｒｋｃｏｄｉｎｇ［Ｊ］．姬ＥＥＴｒａ∞ａｃｔｉｏ∞ｏｎＭｕｌ—ｔｉｍｅｄｉａ，Ｏｃｔ．２００６，８（５）：１０２１—１０３２．
［１４］ｃｈｉＫ，Ｙａｎｇｃ，ｗａｎｇｘ．Ｐｅｒｆｏｒｍｎｃｅｏｆｎｅｔｗｏｒｋｃｏｄｉｎｇｂａｓｅｄｍｕｌｔｉｃａｓｔ［Ｊ］．ＩＥＥＰｒｏｃｅｅｄｉｎｇｓｌＣｏｍｍ帅ｉｃａｔｉｏｎｓ，Ｊｕ舱，２００６，１５３（３）ｔ３９９—４０４．
［１５］ｗｕＹｕｎ眦ｎ，ｃｈｏｕＰｈｉＩｉｐ，ＪａｉｎＫａｍａｌ．Ａｃｏｍｐａｒｉｓｏｎｏｆ耻ｔ－ｗｏｒｋｃｏｄｉｎｇａｎｄｔｒ钾ｐａｃｋｉｎｇ［ｃ］．１ＥＥＥｈｔｅｍａｔｉｏ∞ｌｓｙｍｐｏ－８ｉｕｍ∞Ｉｎｆｏ啪ｔｉ∞Ｔｈｅｏｒｙ，２００４，１４３．
［１６］ＨｏＴ，ＫａｒｇｅｒＤ，ＭｅｄａｒｄＭ，ｅｔａ１．Ｔｈｅｂｅｎｅｆｉｔｓｏｆｃｏｄｉｎｇｏｖｅｒｒｏｕｔｉｎｇｉｎａ髓ｌｌｄｏｍｉｚｅｄｓｅｔｔｉｎｇ［ｃ］．ＩＥＥＥＩｎｔｅｒｍｔｉｏｍｌｓｙｍｐｏ．ｓｉｕｍｏｎＩｎｆｏ彻ａｔｉｏｎＴｈｅｏｒｙ，Ｙｏｋｏｈａｍａ，Ｊａｐａｎ，Ｊｕ耻，２００３．４４２．
［１７］ＨｏＴ阳ｃｅｙ，ＭｅｄａｒｄＭｕｒｉｅＩ?Ｋ∞ｔｔｅｒＲａｌｆ．Ａｎｉｎｆｏｒｍａｔｉｏｎ?ｔｈｅ．ｏｒｅｔｉｃｖｉｅｗｏｆ舱ｔｗｏｒｋｍａ∞ｇｅｍｅｎｔ［Ｊ］．ＩＥＥＥＴ拍ｎｓａｃｔｉｏ∞ｏｎｌｎｆｏｒＩｎａｔｉｏｎＴｈｅｏｒｙ。ＡｐｒｉＩ，２００５，５１（４）：１２９５－１３１２．
［１８］ＨｏＴ，ＬｅｏｎｇＢ，Ｙｕ—ＨａｎＣｈａｎｇｔｅｔａＩ．Ｎｅｔｗｏｒｋｍｏｎｉｔｏｒｉｎｇｉｎｍｕｌｔｉｃａｓｔｎｅｔｗｏｒｋｓｕｓｉｎｇ脯ｔ、∞ｒｋｃｏｄｉｒＩｇ［Ｃ］．ＩＥＥＥ１１１ｔｅｒ∞－
ｔｉｏｎａｌＳｙｍｐｏｓｉｕｍｏｎＩｎｆｏｒｍａｔｉｏｎＴｈｅｏｒｙ（ＩＳＩＴ）（１ＥＥＥＣａｔ．Ｎｏ．０５ＣＨ３７６８Ｃ），２００５，１９７７—１９８１．
［１９］ｗｕＹ。ＣｈｏｕＰＡ，ＺｈａｎｇＱ，ｅｔａ１．Ｎｅｔｗｏｒｋｐｌａｎｎｉｎｇｉｎｗｉｒｅ—Ｉｅｓｓａｄｈｏｃｎｅｔｗｏｒｋｓ：ａｃｒｏｓｓ—ｌａｙｅｒａｐｐｒｏａｃｈ［Ｊ］．１ＥＥＥＪ．Ｓｅｌ．
ＡｒｅａｓＣｏｍｍｕｎ．，２００５，２３（１）：１３６—１５０．
［２０］Ｙｕｎｎａｎｗｕ，Ｓｕｎ—ｙｕａｎＫｕｎｇ．Ｒｅｄｕｃｅｄ－ｃｏｍｐｌｅ】【ｉｔｙｎｅｔｗｏｒｋｃｏｄｉｎｇｆｏｒｍｕｌｔｉｃａｓｔｉｎｇｏｖｅｒａｄｈｏｃｎｅｔｗｏｒｋｓ［Ｃ］．ＩＥＥＥＩｎｔｅ卜
ｎａｔｉｏｎａｌＣＤｎｆｅｒｅｎｃｅｏｎＡｃｏｕｓｔｉｃｓ，Ｓｐｅｅｃｈ。ａｎｄＳｉｇｎａｌＰｒｏｃｅｓｓ－
ｉｎｇ，２００５．Ｐｒｏｃｅｅｄｉｎｇｓ．（ＩＣＡＳＳＰ’０５）．ＶｏＩｕｍｅ３，１８—２３
Ｍａｒｃｈ２００５．
［２１］Ｍｅａｗａｎｇ。ＢａｏｃｈｕｎＬｉ．ＨｏｗｐｒａｃｔｉｃａＩｉ８ｎｅｔｗｏｒｋｃｏｄｉｎｇ［ＥＢ／ＯＬ］．ｈｔｔｐ：／／ｗｗｗ．ｅｅｃｇ．ｔｏｒｏｎｔｏ．ｅｄｕ／～ｂｌｉ／ｐａｐｅｒｓ，２００６，１０．
［２２］ＴｏｍｉｓｌａｖＮａｄ．Ｐｒｏｂｌｅ脚ｗｉｔｈｎｅｔｗｏｒｋｃｏｄｉｎｇｉＩｌｏｖｅｒｌａｙｎｅｔ—ｗｏｒｋｓ［ＥＢ／ｏＬ］．ｈｔｔｐ｛／／ｚｏｏ．ｃ５．”ｌｅ．ｅｄｕ／ｃｌａｓ８ｅ８／ｃ３４９０／０４－０５ａ．２００６．１０．
［２３］Ｌｉｓ＿ＹＲ．ＹｅｕｎｇＲｗ．Ｌｉｎｅａｒｎｅｔｗｏｒｋｃｏｄｉｎｇ［Ｊ］．１ＥＥＥＴｎｎｓ．Ｉｎｆｏｒｍ．Ｔｈｅｏｒｙ。２０００．
［２４］ＫｏｅｔｅｒＲ，ＭｅｄａｒｄＭ．ＢｅｙｏｎｄｒｏｕｔｉＩｌｇｌａｎａｌｇｅｂｒａｉｃａｐｐｒ∞ｃｈｔｏ
脾ｔｗｏｒｋｃｏｄｉｎｇ［Ｃ］．Ｉｎ２００２ＩＥＥＥＩＩｌｆｏｃｏｍ，２００２．
［２５］Ｋ∞ｔｅｒＲ．ＭｅｄａｒｄＭ．Ａｎａｌｇｅｂｒａｉｃａｐｐｒｏａｃｈｔｏ舱ｔｗｏｒｋｃｏｄｉｎｇ
［Ｊ］．ＩＥＥＥ／ＡＣＭＴｒａ珊．Ｎｅｔｗｏｒｋｉｎｇ，２００３。１１（５）：７８２?７９５．［２６］ｓａｎｄｅｒｓＰ，ＥｇｎｅｒＳ，ＴｏｌｈｕｉｚｅｎＬ．Ｐｏｌｙｎｏｍｉａｌｔｉｍｅａｌｇｏｒｉｔｈｍ８ｆｏｒ肿ｔｗｏｒｋｉｎｆｏｍａｔｉｏｎｎｏｗ［ｃ］．ＩｎｌＰｆｏｃ．１５ｔｈＡＣＭＳｙｍｐｏ－
ｓｉｕｍｏｎＰａｒａｌｌｅｌＡｌｇｏｒｉｔｈｍｓａｎｄＡｒｃｈｉｔｅｃｔｕｒｅｓ，２００３．
［２７］ＹｅｕＩｌｇＲｗｔＬｉＳ－ＹＲ，ＣａｉＮ，ｅｔａ１．Ｎｅｔｗｏｒｋｃｏｄｉｎｇｔｈｅｏｒｙ
［Ｍ］．ＮｏｗＰｕｂｌｉｓｈｅｒｓＩｎｃ，２００６．
［ｚ８］ＨｏＴ，Ｋａ。ｇｅｒＤ。ＭｅｄａｒｄＭ，ｅｔａ１．Ｔｈｅｂｅｎｅｆｉｔｓｏｆｃｏｄｉｎｇｏｖｅｒｒｏｕｔｉｎｇｉｎａｒａｎｄｏｍｉ舱ｄｓｅｔｔｉｎｇ［Ｃ］．ＩＥＥＥＩｎｔｅｍａｔｉｏｎａｌＳｙｍｐｏ－８ｉｕｍ∞Ｉｎｆｏ咖ｔｉ∞Ｔｈｅｏｒｙ，Ｙｏｋｏｌｌａｍａ，Ｊａｐａｎｐ．４４２?Ｊｕｍ，
２００３．
［２９］ＨｏＴ，ＭｅｄａｒｄＭ。ｓｈｉＪ．ｅｔａ１．０ｎｎＩ，ｄｏＩＩｌｉｚｅｄｍｔｗｏｒｋｃｏｄｉｎｇ［Ｃ］．ＩＩｌｌＰｒｏｃｅｅｄｉｎｇｓｏｆ４１ｓｔＡ叻ｕａｌＡｌｌｅｒｔｏｎＣｏｎｆｅ陀ｎ∞ｏｎＣｏｍ舢ｎｋａｔｉｏｎ，Ｃｏｎ仃ｏｌ，ａｎｄＣｏｍｐｕｔ啦，ｏｃｔｏｂｅｒ２００３．
［３０］ＣｈｏｕＰＡ，ｗｕＹ，ＪａｉｎＫ．Ｐｒａｃｔｉｃａｌｎｅｔｗｏｒｋｃｏｄｉｎｇ［Ｃ］．ＡｌＩｅｒ＿ｔｏｎ（ｋｎｆｅｒｅｎｃｅｏｎｃｏｍｍｕｎｉｃａｔｉ∞，ｃｏｎｔｒ０１．ａｎｄ（ｂｍｐｕｔｉｎｇ，Ｍｏｎｔｉｃｅｌｌｏ，ＩＬ，Ｏｃｔｏｂｅｒ２０。２００３．
［３１］Ｊａｇｇｉｓ，ＣｈｏｕＰＡ，ＪａｉｎＫ．ＬｏｗｃｏｍｐＩｅｘｉｔｙａｌｇｅｂｒａｉｃｎｅｔｗｏｒｋ
ｃｏｄｅｓ［Ｃ］．ＩＩｌ：Ｐｒｏｃ．１ｓＩＴ。２００３．
［３２］ＬａｎｇｂｅｒｇＭｉｃｈａｅｌ，Ｓｐｒｉｎｔｓｏｎ，Ａｌｅｘａｎｄｅｒ，ｅｔａ１．ＴｈｅｅｎｃｏｄｉｎｇｃｏｍｐｌｅｘｉｔｙｏｆｎｅｔｗＤｒｋｃｏｄｉｎｇ［Ｊ］．ＩＥＥＥＴｒａ∞ａｃｔｉｏｎｓｏｎＩｎｆｏｒ—ｍａｔｉ∞Ｔｈｅｏｒｙ，Ｊｕｎｅ，２００６，５２（６）；２３８６—２３９７．
［３３］ＦｒａｇｏｕｌｉＣ，洲ｊａｎｉｎＥ．Ｉｎｆｏｒ舭ｔｉｏｎｎｏｗｄ∞ｏｍｐｏｓｉｔｉｏｎｆｏｒｎｅｔ—ｗｏｒｋｃｏｄｉｎｇ［Ｊ］．ＩｎｆｏｒｍａｔｉｏｎＴｈｅｏｒｙ，ＩＥＥＥＴｒａｎｓａｃｔｉｏ鹏，Ｍａｒｃｈ２００６．５２（３）：８２９—８４８。
［３４］ＦｒａｇｏｕＩｉＣ。ＳｏｌｊａＩｌｉｎＥ，ＳｈｏｋｒｏｌｌａｈｉＡ．Ｎｅｔｗｏｒｋｃｏｄｉｎｇａｓａｃｏｌｏｒｉｎｇｐｒｏｂｌｅｍ［Ｃ］．ｃＩＳｓ２００４，ＰｒｉｎｃｅｔｏｎＵｎｉＶｅｒｓｉｔｙ．
［３５］ＬｕｎＤ，ＭｅｄａｒｄＭ．ＨｏＴ，ｅｔｌａ．Ｎｅｔ、∞ｒｋｃｏｄｉｎｇ谢ｔｈａｃｏｓｔ
ｃｄｔｅｒｉｏｎ［Ｃ］．Ｉｎ：ＩｎｔｅｒｍｔｉｏｍｌｓｙｍｐｏｓｉｕｍｏｎｌｎｆｏｒｍａｔｉｏｎＴｈｅ＿ｏｒｙａｎｄｉｔ８ＡｐｐＩｉｃａｔｉｏｎｓ（ＩＳＩＴＡ），０ｃｔ．２００４．
［３６］ＸｉＹ，ＹｅｈＥＭ．Ｄｉｓｔｒｉｂｕｔｅｄａｌｇｏｒｉｔｈｍｓｆｏｒｍｉｎｉｍｕｍｃ∞ｔｍｕｌ—
ｔｉｃａｓｔｗｉｔｈ鹏ｔｗｏｒｋｃｏｄｉｎｇ［Ｃ］．ＩｎｌＰｒｏｃｅｅｄｉｎｇｓｏｆｔｈｅ４３ｒｄ
Ａ１ｌｅｒｔｏｎＡｎｎｕａＩＣｏｎｖｆｅｉｅｎｃｅｏｎｌｃｏｍｍｕｎｇｉｃａｔｉｏｎｌ，ｃｏｎｖｔｉｏｌ，ａｎＶｄＣｏｍｐｕｔｉｎｌｇＳｅｐｔ．２００５．
５９２
小型微型计算机系统２００８年
［３７］ＢｈａｔｔａｄＫ。ＲａｔｎａｈｒＮ，ＫｏｅｔｔｅｒＲ，ｅｔａＩ．Ｍｉｎｉｍａｌ腿ｔ、∞ｒｋｃｏｄ?
ｉｎｇｆｏｒｍｕｌｔｉｃａｓｔ［Ｃ］．ＩＥＥＥＩＩｌｔｅｒＭｔｉｏｍｌＳｙｍｐｏｓｉｕｍｏｎＩｎｆｏｒ－ｍａｔｉｏｎＴ｝ｌｅｏ搿（１ＳｌＴ）。２００５，１７３０一１７３４．
［３８］Ｄｅｂｓ，ＥｆｆｒｏｓＭ。ＨｏＴ，ｅｔａ１．ＮｅｔｗｏｒｋｃｏｄｉｎｇｆＤｒＷｉｒｅｌｅｓｓａｐ－
ｐｌｉｃａｔｉｏｎ５＃ａｂｒｉｅｆｔｕｔｏｒｉａＩ［ｃ］．ＩｎｌＰｒｏｃ．ｏｆ１ｗｗＡＮ，Ｌｏｎｄｏｎ．ＵＫ，Ｍａｙ２００５．
［３９］ＡｌＨａｍ阳Ａ．Ｂａ弛ｋａｔｃ，ＴｕｒＩｅｔｔｉＴ．Ｎｅｔｗｏｒｋｃｏｄｉｎｇｆｏｒｗｉｒｅ－ｌ∞ｓｍｅｓｈ册ｔｗｏｒｋｓｆａ∞ｓｅ８ｔｕｄ，，［ｃ］．ＩｎｌＩＥＥＥＩｌｌｔｅ瑚ｔｉｏｍｌＳｙｍｐｏｓｉｕｍｏｎａＷｏｒｌｄｏｆＷｉｒｅＩｅｓｓ。ＭｏｂｉｌｅａｎｄＭｕｌｔｉｍｅｄｉａＮｅｔｗｏｒｋｓ（ＷｏＷＭｏＭ）。Ｎｉａｇａｒａ．Ｆａｌｌｓ，Ｂｕｆｆａｌｏ．ＮＹ。ＵＳＡ，Ｊｕ鹏２６—２９２００６．
［４０］Ｙｕｎｎａｎｗｕ。Ｓｕｎ．ＹｕａｎＫｕｎｇ．Ｒｅｄｕｃｅｄ—ｃｏｍｐｌｅｘｉｔｙｍｔｗｏｒｋ
ｃｏｄｉｎｇｆｏｆｍｕｌｔｉ∞ｓｔｉｎｇｏｖｅｒａｄｈｏｃ雎ｔｗｏｒｋ８［Ｃ］．１ＥＥＥＩｎｔｅｒ．ｍｔｉｏｎａｌＣｏｎｆｅｒｅｎｃｅｏｎＡｃｏｕｓｔ证８，Ｓｐｅｅｃｈ，ａｎｄｓｉｇ他ｌｆ’ｏｃｅｓ和
ｉｎｇ（ＩＥＥＥＣａｔ．Ｎｏ．０５ＣＨ３７６２５），２００５，ｐｔ．３?ｐｉｉｉ／５０１—４Ｖ０１．３．
［４１］Ｆ托ｇｏｕｌｉｃ。ｗｉｄ眦ｒＪ．Ｂｏｕｄ优Ｊ—ＹＬ．Ａ耻ｔ啪ｒｋｃｏｄ啦ａｐ＿ｐｒｏａｃｈｔｏｅｎｅｒｇｙｅｆｆｉｃｉｅｎｔｂｒｏａｄｃａＢｔｉｎｇｌｆｒｏｍｔｈｅｏｒｙｔｏｐ强ｃｔｉｃｅ［Ｒ］．ＴｅｃｈｎｉｃａｌＲｅｐｏｒｔＬＣＡ—ＲＥＰＯＲＴ?２００５一００９。ａｃｃｅｐｔｅｄａｔｈｌｆｏｃｏｍ２００６，ＥＰＦＬ，Ｊｕｌｙ２００５．
［４２］Ｙ岫ｎＪｕｎ。Ｌ．ｚｏｎｇ?ｐｅｎｇ，Ｙｕｗｅｉ，ｅｔａ１．Ａｃｒｏｓｓ—ｌａｙｅｒｏｐｔ０ｍｉ孤ｔｉ仰ｆｎｍｅｗｏｆｋｆＤｒｍｕｌｔｉｃａｓｔｉｎｍｕｌｔｉ－ｈｏｐ霄ｉ”ｌｅｓｓｎｅｔ．帅ｒｋｓ［Ｃ］．ｈｔＰｒ∞．ｏｆＦＩｒｓｔＩｎｔｅｒｎａｔｉｏ雎ｌＣｏｎｆｅｆｅ眦ｅｏｆＷｉｒｅ．１ｅ３８Ｉｎｔｅｒ他ｔ（ＷＩＣＯＮ），Ｂｕｄａ阳ｓｔ?Ｈｕｎｇａｒｙ，２００５?４７?５４．
（Ｉｎｖｉｔｅｄ）
［４３］ｗｕＹ．ＣｈｏｕＰＡ，ＫｕｌｌｇＳ．Ｙ．Ｍｉｎｉｍｕｍ－ｅｍｒｇｙｍｕＩｔｉｃａｓｔ缸ｍｏｂｉｌｅａｄｈ∞ｍｔｗｏｒｋｓｕｓｉｎｇ耻ｔ、阳ｒｋｃｏｄｉｎｇ［Ｃ］．ＩＥＥＥＩｎｆｏ卜啪ｔｉ∞ＴｈｅｏｒｙＷｏｒｋｓｈｏｐ。ｏｃｔ．２００４．
［４４］ＣｈｅｎＹ，Ｋｉｓｈｏ坤Ｓ，ＬｉＪ．ｗｉｒｅｌｅ亭ｓｄｉｖｅｒｓｉｔｙｔｈｒ∞ｇｈｎｅｔｗｏｒｋ
ｃｏｄｉｎｇ［Ｃ］．ｂｌＰｒｏｃｅｅｄｉｎｇｏｆＩＥＥＥｗｉＭｌｅｓｓＣｏｍｍｕｎｉｃａｔｉｏ∞ａＩｌｄＮｅｔＷｏｒｋｉｎｇＣｏＩｌｆｅｒｅｎｃｅ（ＷＣＮＣ）?Ｌａｓｖｅｇａｓ?ＮＶ?Ｍａｒｃｈ．２００６．
［４５］Ｐｅｔｒｏ“ｃＤ．ＫａｎｍｎＲ．ＲａｂａｅｙＪ．Ｃｏｄｉｎｇｆｏｒｓｅｎｓｏｒ北ｔｗｏｒｋ摹ｕｓｉｎｇ
ｕｎｔｕｎｅｄｎｄｉｏｓ［Ｊ］．ＩＥＥＥ６ｔｈⅥｒｏｒｋｓｈｏｐｏｎＳｉｇｎａｌＰｒｏ－ｃｅｓｓｉ哩Ａｄ张ｎｃｅ５ｉｎＷｉ弛Ｉｅｓ８Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ５—８Ｊｕ腿２００５，
１０９３—１０９７．
［４６］ｚ｝ｌａｎｇｘ。ｗｉｃｋｅｒＳＢ．Ｒｏｂｕｓｔｎｅｓｓｖｓ．ｅｆｆｉｃｉｅｎｃｙｉｎｓｅｎ８０ｒｎｅｔ．Ｗｏｆｋｓ［Ｃ］．ＦｏｕｒｔｈＩｎｔｅ珊ｌｔｉｏｎ出Ｓｙｍｐｏｓｉｕｍｏｎｌｎｆｏｍａｔｉ∞ＰｒｏｃｅｓｓｉｎｇｉｎＳｅｎｓｏｒＮｅｔｗｏｒｋ８（ＩＰＳＮ），１５Ａｐ砌２００５，２２５—２３０．
［４７］Ｋａｔｔｉｓ，ＫａｔａｂｉＤ．Ｈｕｗ，ｅｔａＩ．Ｔｈｅｉｍｐｏｒｔａ撒ｅｏｆｂｅｉｎｇｏｐ．ｐｏｒｔｕｎｉｓｔｉｃｌｐｒａｃｔｉｃ“ｎｅｔｗｏｒｋｃｏｄｉｎｇｆｏｒ＿而ｒｅｌｅｓｓｅｎｖｉｒｏｎｍｅｎｔｓ［ｃ］．Ｉｌｌ＃Ｐｒ∞．４３ｒｄＡｎｎｕａｌＡｌｌｅｒｔｏｎｃｏｎｆｅｒｅｎｃｅ伽ｃｏ∞坊蚰ｉ一∞ｔｉｏｎ，ＣｏｎｔｒｏＩ，ａｎｄｃｏｍｐｕｔｉｎｇ，ｓｅｐｔ．２００５．
［４８］ｚｈｕＹｉｎｇ．ＬｉＢａｏ．ｃｈ岫，ＧｕｏＪｉａｎｇ．Ｍｕｌｔｋａｓｔ、而ｔｈ眦ｔｗｏｒｋｃｏｄｉｎｇｉｎａｐｐｌｉｃａｔｉｏｎ—Ｉａｙｅｒｏｖｅｒｌ鱼ｙ鹏ｔｗｏｆｋ。口］．ＳｅｌｅｃｔｅｄＡｒ∞ｓｉｎｃｏｍｍｕｎｉｃａｔｉｏ∞，ＩＥＥＥＪｏｕｒｍｌ，Ｊａｎ．２００４，２２（１）１１０７—１２０．［４９］ｃｏｈｅｎＢ．Ｉ眦ｅｎｔｉｖｅＢｂｕｉｌｄｒｏｂｕｓｔｎｅｓｓｉｎｂｉｔｔｏｒｒｅｎｔ［ｚ］．ＩｎＰ２ＰＥｃｏａｏｒｎｉｃｓＷｏｒｋｓｈｏｐ。Ｂｅｒｋｅｌｅｙ，ＣＡ．２００３．
［５０］ＤａｈＭｉｎｇｃｈｉｕＹｅｕｎｇ，ＪｉａｑｉｎｇＨｕａ唱Ｒｗ，ＢｉｎＦａｎ．ｃａｎ腿ｔ．ｗｏｒｋｃｏｄｉｎｇｈｅｌｐｉｎＰ２Ｐ耻ｔｗｏｒｋｓ［ｃ］．Ｍｏｄｅｌｉｎｇａ１１ｄＯｐｔｉｍｉ趵－ｔｉｏｎｉｎＭｏｂｉＩｅ。ＡｄＨｏｃａｎｄＷｉｒｅｌｅｓｓＮｅｔｗｏｒｋ８，２００６４ｔｈＩｌｌｔｅｒ－聃ｔｉｏ眦ｌＳｙｍＰｏｓｉｕｍＯｎ０３一０６Ａｐｒ订２００６，１—５．
［５１］ｃａｉＮ．Ｙｅ蚴ｇＲｗ．Ｎｅｔｗｏｒｋｃｏｄｉｎｇａｎｄｃｒｒｏｒｃｏｒｒ∞ｔｉｏｎ［Ｃ］．ＩｎｌＰｒｏｃ．ＩＴＷ２００２，２００２．１１９－１２２．
［５２］ＨｏＴ．ＭｅｄａｒｄＭ。Ｋ∞ｔ盯Ｒ．Ａｃｏｄｉｎｇｖｉｅｗｏｆ雠ｔｗｏｒｋ弛ｃｏｖ．ｅｒｙａｎｄ眦啦ｇｍｅｎｔｆｏｒｓｉｎｇＩｅ托ｃｅｉｖｅｒｃｏｍｍｕｎｉｃａｔｉｏｎ［ｃ］．ＣＩｓｓ２００２．
［５３］Ｆｒａｇｏｕｌｉｃ，ＳｏｌｊａｎｉｎＥ．ＳｕｂｔｒｅｅｄｅｃｏｍｐｏＢｉｔｉ∞ｆｏｒ地ｔｗｏｒｋｃｏｄ—ｉｎｇ［ｃ］。２００４ＩＥＥＥｈｔｅｒ强ｔｉｏｎａｌＳｙｍｐ∞ｉｕｍ∞ＩＴｌｆｏｒｍａｔｍＴｈｅｏｒｙ（１ＥＥＥｃａｔ．Ｎｏ．０４ＣＨ３７５２２），２００４?１４５．
［５４］ＨｏＴ，Ｌ∞ＩｌｇＢ．ＫｏｅｔｔｅｒＲ，ｅｔａＩ．Ｂｙ豫ｎｔｉ耻ｍｏｄｉｆｉｃａｔｂｎ
ｄｅｔ婚ｔｉｏｎｉｎｍｕＩｔｉｃａｓｔｎｅｔｗｏｒｋｓｕｓｉｆｌｇ拍ｎｄｏｍｉ豫ｄｎｅｔｗｏｒｋｃｏｄｉＩｌｇ［Ｃ］．ｈｌＩＥＥＥｈｌｔｅｒｎａｔｉ∞ａｌＳｙｍｐｏｓｉｕｍ∞ｌｎｆｏｒｍａｔｉ∞Ｔｈｅｏ珂（ＩＳＩＴ２００４），Ｊｕ眦２００４．
［５５］ＧｋａｎｔＢｉｄｉｓｃ，ＲｏｄｒｉｇｕｅｚＰ．ｃｏｏｐｅｒａｔｉｖｅｓｅｃｕｒｉｔｙｆｂｒｎｅｔ、∞ｒｋｃｏｄｉｎｇｆ．１ｅ
ｄｉ３ｔｒｉｂｕｔｉ∞［Ｃ］．ＩＩＩｌｌＥＥＥＩｎｆｏｃｏｍ２００６．
［５６］ＪａｉｎＫ．ｓｅｃｕｒｉｔｙｂａｓｅｄｏｎｎｅｔｗｏｒｋｔｏｐｏＩｏｇ，ｒａｇａｉｎ５ｔｔｈｅｗｉｒｅｔａｐ—ｐｉｎｇａｔｔａｃｋ［Ｃ］．ＩＥＥＥｗｉＭｌｅｓｓｃｏｍｍｕｎｉｃａｔｉｏｎ８。６８－７ｌ，Ｆｅｂ２００４．
网络编码研究综述
作者：陶少国， 黄佳庆， 杨宗凯， 乔文博， 熊志强， TAO Shao-guo， HUANG Jia-qing，YANG Zong-kai， QIAO Wen-bo， XIONG Zhi-qiang
作者单位：华中科技大学,电子与信息工程系,智能互联网技术湖北省重点实验室,湖北,武汉,430074
刊名：
小型微型计算机系统
英文刊名：JOURNAL OF CHINESE COMPUTER SYSTEMS
年，卷(期)：2008，29(4)
被引用次数：5次
参考文献(56条)
1.Ramanathan S Multicast tree generation in networks with asymmetric links 1996(04)
2.Moses Charikar.Chandra Chekuri.To-yat Cheung Approximation algorithms for directed Steiner problems 1998
3.Leonid Zosin.Samir Khuller On directed steiner trees 2002
4.Bollobas B Graph theory an introductory course 1979
5.Rudolf Ahlswede.Ning Cai.Shuo-Yen Robert Li Network information flow 2000(04)
6.Agarwal A.Charikar M On the advantage of network coding for improving network throughput 2004
7.Lun D.Ratnakar N.Koetter R Achieving minimum-cost multicast:a decentralized approach based on network coding 2005
8.Fragouli C.Soljanin E Decentralized network coding 2004
9.Gkantsidis C.Rodriguez P R Network coding for large scale content distribution 2004
10.Bhadra S.Shakkottai S.Gupta P Min-cost selfish multicast with network coding 2006
11.Barros J.Servetto S D A coding theorem for network information flow with correlated sources 2005
12.Zhang Jing-yao.Fan Ping-yi On network coding in wireless ad-hoc networks 2005
13.Zhao Jin.Yang Fan.Zhang Qian LION:layered overlay multicast with network coding 2006(05)
14.Chi K.Yang C.Wang X Performance of network coding based multicast 2006(03)
15.Wu Yunnan.Chou Philip.Jain Kamal A comparison of network coding and tree packing 2004
16.Ho T.Karger D.Medard M The benefits of coding over routing in a randomized setting 2003
17.Ho Tracey.Medard Muriel.Koetter Ralf An information-theoretic view of network management 2005(04)
18.Ho T.Leong B.Yu-Han Chang Network monitoring in multicast networks using network coding 2005
19.Wu Y.Chou P A.Zhang Q Network planning in wireless ad hoc networks:a cross-layer approach
2005(01)
20.Yunnan Wu.Sun-yuan Kung Reduced-complexity network coding for multicasting over ad hoc networks 2005
21.Mea Wang.Baochun Li How practical is network coding 2006
22.Tomislav Nad Problems with network coding in overlay networks 2006
23.Li S-Y R.Yeung R W Linear network coding 2000
24.Koeter R.Medard M Beyond routing:an algebraic approach to network coding 2002
25.Koeter R.Medard M An algebraic approach to network coding 2003(05)
26.Sanders P.Egner S.Tolhuizen L Polynomial time algorithms for network information flow 2003
27.Yeung R W.Li S-Y R.Cai N Network coding theory 2006
28.Ho T.Karger D.Medard M The benefits of coding over routing in a randomized setting 2003
29.Ho T.Medard M.Shi J On randomized network coding 2003
30.Chou P A.Wu Y.Jain K Practical network coding 2003
31.Jaggi S.Chou P A.Jain K Low complexity algebraic network codes 2003
https://www.wendangku.net/doc/ea10239558.html,ngberg Michael.Sprintson,Alexander The encoding complexity of network coding 2006(06)
33.Fragouli C.Soljanin E Information flow decomposition for network coding 2006(03)
34.Fragouli C.Soljanin E.Shokrollahi A Network coding as a coloring problem
35.Lun D.Medard M.Ho T Network coding with a cost criterion 2004
36.Xi Y.Yeh E M Distributed algorithms for minimum cost multicast with network coding 2005
37.Bhattad K.Ratnakar N.Koetter R Minimal network coding for multicast 2005
38.Deb S.Effros M.Ho T Network coding for wireless applications:a brief tutorial 2005
39.Al Hamra A.Barakat C.Turletti T Network coding for wireless mesh networks:a case study 2006
40.Yunnan Wu.Sun-Yuan Kung Reduced-complexity network coding for multicasting over ad hoc networks 2005
41.Fragouli C.Widmer J.Boudec J-Y L A network coding approach to energy efficient broadcasting:from theory to practice[Technical Report LCA-REPORT-2005-009] 2005
42.Yuan Jun.Li Zong-peng.Yu Wei A cross-layer optimization framework for multicast in multi-hop wireless networks 2005
43.Wu Y.Chou P A.Kung S-Y Minimum-energy multicast in mobile ad hoc networks using network coding 2004
44.Chen Y.Kishore S.Li J Wireless diversity through network coding 2006
45.Petrovic D.Kannan R.Rabaey J Coding for sensor networks using untuned radios 2005
46.Zhang X.Wicker S B Robustness vs.efficiency in sensor networks 2005
47.Katti S.Katabi D.Hu W The importance of being opportunistic:practical network coding for wireless environments 2005
48.Zhu Ying.Li Bao-chun.Guo Jiang Multicast with network coding in application-layer overlay networks 2004(01)
49.Cohen B Incentives build robustness in bittorrent 2003
50.Dah Ming.Chiu Yeung.Jiaqing Huang R W.Bin Fan Can network coding help in P2P networks 2006
51.Cai N.Yeung R W Network coding and error correction 2002
52.Ho T.Medard M.Koeter R A coding view of network recovery and managment for single receiver communication
53.Fragouli C.Soljanin E Subtree decomposition for network coding 2004
54.Ho T.Leong B.Koetter R Byzantine modification detection in multicast networks using randomized network coding 2004
55.Gkantsidis C.Rodriguez P Cooperative security for network coding file distribution
相似文献(10条)
1.期刊论文杨林.郑刚.马恒太基于随机网络编码的无线广播重传方案及性能分析-信号处理2010,26(1)
针对自动重复重传(ARQ)机制在无线广播系统中吞吐量性能不佳的缺陷,提出一种基于随机网络编码的广播重传方案RNC-ARQ.对于广播节点,采用随机线性码对所有丢失包进行编码组合重传.对于接收节点,当接收的编码包累积到一定数量后可通过解码操作恢复出原始数据.该方案可有效减少重传次数,改善无线广播的吞吐量性能.基于Gilbert-Elliott模型描述的突发错误信道,建立了信道状态和节点接收处理流程合并的多状态马尔可夫模型,并以此为基础推导了RNC-ARQ方案的吞吐量闭合解.最后,使用NS-2模拟器评估RNC-ARQ方案的性能,结果表明在突发差错信道下,基于随机网络编码重传方案的吞吐量优于传统的选择承传ARQ方案和基于异或编码的重传方案.
2.期刊论文王俊义.WANG Jun-yi随机网络编码对文件共享的增益-计算机工程与应用2009,45(4)
研究了在有冲突的无线Mesh网络中,相对于存储转发机制,随机网络编码对文件共享所带来的下栽时间或下裁成功率的增益,以及比特错误概率(Bit Error Ratio,BER)对随机网络编码性能的影响.仿真结果表明,当源节点数为1且随机放置时,在盲转发(Blind-Forward)节点协作方式下,随机网络编码能够将下载时间减少30%-40%.当源节点数为2且固定放置时,相对存储转发机制,在盲转发和选择性转发(Selective-Forward)节点协作方式下,采用随机网络编码均较大程度地减少了下载时间.
3.期刊论文高振国.赵蕴龙.蔡绍滨.赵金华.Gao Zhenguo.Zhao Yunlong.Cai Shaobin.Zhao Jinhua基于随机网络
编码的无线报文重传最优策略-北京航空航天大学学报2010,36(2)
网络编码技术为无线报文重传问题研究提供了新思路.分析并证明了完全无线报文重传问题最优策略所需重传报文数量等于节点请求报文数量的最大值;基于随机网络编码技术提出了最优重传策略RNCOPT(Random Network Coding based OP Timal Scheme),其编码系数从某选定有限域中随机选取(0除外);利用网络编码矩阵重新生成机制以保证100%解码成功率;描述了RNCOPT组合报文结构及发送节点操作过程.仿真表明:当接收节点数量为30而报文总数为30时,RNCOPT相对于传统非网络编码方案节省重传报文数量可达32%,而此时现有某典型策略CliqueNC却无明显效果.
4.期刊论文陈长英.杨秀红.宋栋.徐明.CHEN Chang-ying.YANG Xiu-hong.SONG Dong.XU Ming随机网络编码理论
及其在无线通信网络中的应用-信息技术与信息化2009,""(6)
随机网络编码理论是近些年刚刚兴起的崭新网络基础理论,与以路由为基础的传统网络理论相比它有很多独有的优势,这必将推动新一代网络通信系统的产生.本文首先介绍了随机网络编码理论的基本内容,包括它的定义、独有的特点和优势,然后分析了将它应用于无线通信网络需要解决的一些关键问题,最后展望了该理论的发展前景.
5.期刊论文王俊义.WANG Jun-yi网络编码在无线Mesh网络中的应用-计算机工程与应用2010,46(15)
论文研究了在有冲突的无线Mesh网络中,相对于存储转发机制,随机网络编码对文件共享所带来的下载时间的增益.仿真结果表明,当节点分别为移动和固定时,在盲转发(Blind-Forward)选择性转发(Selective-Forward)节点协作方式下,随机网络编码均较大地降低了文件下载的时间.论文对仿真结果进行了性能分析.
6.学位论文金烨随机网络编码在移动网络中的研究2010
网络编码是2000年由R.Ahlswede、N.Cai等人首次提出。其主要优点之一就是
使多播传输速率能达到上限值，即多播容量。而使用目前的多播传输方法，多播
传输速率往往是达不到这个上限值。另外，网络编码与其他技术相结合还可以从
多角度对网络进行优化，例如降低资源消耗、负载均衡、网络管理等。目前，大
多数的研究对象是多播网络，本文也是针对多播网络进行的分析研究，而网络编
码在非多播网络中的应用有待于更多的研究。
@@由于移动网络的时变性、不可靠性和间断性连接特点，使得在移动网络中应
用传统多径路由技术会产生报文乱序和报文丢失现象。本文采用理论分析和计算
机仿真的方法，对特定拓扑结构的移动网络进行了研究，提出了一种集成网络编
码的多播算法。理论分析表明，在同等多路径数目和报文丢失率条件下达到相等
的报文投递率，该方法的传输性能优于传统的多径路由方法。通过仿真实验，比
较了在不同的多路径数目、冗余因子和链路报文丢失率条件下两种方法的报文投
递性能，验证了理论分析的正确性，并指出采用集成网络编码的多播算法可显著
提高多径路由传输的可靠性，节省通信资源，并在一定报文丢失范围内提升多径
路由的容错能力。
@@关键词：移动网络 网络编码 多径路由 可靠性
7.期刊论文钦健.杨白薇.李鸥.QIN Jian.YANG Bai-wei.LI Ou基于WSN的随机网络编码跨层研究-计算机工程
2010,36(3)
基于无线传感器网络,提出一种跨层实现随机网络编码的方案,并在NS2平台上进行仿真.将网络编码方案与传统的几种传感器路由机制进行对比,分析编码与解码功能,将该方案应用于无线传感器网络中,对影响解码率的几个主要因素,如缓存队列长度、Sink节点的位置等进行了评估.
8.期刊论文李楠无线网络随机编码技术研究-光机电信息2010,27(6)
本文详细介绍了随机编码技术的提出、编码规则及评价,研究了随机编码技术得以在无线网络中实现的关键技术,并总结了随机编码技术相对于传统的以路由为基础的网络理论的特点和优势,为相关研究人员在该领域的研究工作提供一些理论依据.
9.期刊论文周业军.李晖.马建峰.ZHOU Ye-jun.LI Hui.MA Jian-feng一种防窃听的随机网络编码-西安电子科技
大学学报（自然科学版）2009,36(4)
针对应用随机网络编码进行文件传输时的安全问题,提出了一种防窃听的网络编码算法.应用该算法,窃听者得不到关于信源的任何有意义的信息,称之为弱安全.该算法通过舍弃少量带宽使得随机网络编码能以很高的概率达到弱安全性的要求.另外,当信源和信宿共享有秘密信道时,秘密信道编码算法达到弱安全性要求的概率为1,且能达到网络的最大流.该编码算法仅是在原随机编码体制的基础上对信源和信宿进行了改变,中间节点编码保持不变.
10.学位论文周业军防污染和防窃听的网络编码2009
近年来，网络编码越来越成为业界的研究热点。网络编码技术极大的提高了网络
的传输速率、吞吐量和可靠性，对路由器基础设施以及无线网状网络等都有重要意
义。但直接应用网络编码存在不可忽视的安全问题，主要包括污染和窃听两类问题，
其中污染主要由恶意节点和信道噪声引起，窃听是指攻击者通过窃听网络中的部分或
者全部信道来获取网络中传输的消息。这些安全问题很大程度上限制了其应用范围，
题，并设计了有效的安全网络编码体制，主要包括以下几个方面：
@@(1)提出了一种防窃听的网络编码算法。应用该算法，窃听者得不到关于信源任何有
意义的信息，称之为弱安全。该算法通过舍弃少量带宽使得随机网络编码能以很
高的概率达到弱安全的要求。另外，当信源和信宿共享有一个低速率秘密信道或
公钥加密体制时，设计了一种可以达到网络最大流的弱安全网络编码体制。应用
随机网络编码时，该编码体制防窃听的概率为1。
@@(2)现有的防窃听网络编码存在两方面的问题。首先，要达到信息论安全的防窃听目
的必须牺牲部分带宽，以致无法达到网络的最大流。其次，应用随机网络编码
时，编码安全的概率较低。文中设计了一种能同时达到网络的最大流和信息论安
全条件的网络编码体制。同时，该编码体制是一个确定性模型而非概率模型，
即：应用随机网络编码时，该编码体制信息论安全的概率为1。
@@(3)提出了一种验证消息完整性的同态签名体制。首先，取一些公开参数作为原始信
源消息每个信息包的Hash值，当在原始信息包中加入少量冗余时，其Hash值便
是取定的公开参数，省去Hash值的分发，很大程度上降低了该签名体制的通信开
销。其次，当网络拓扑简单且固定时，用一个所有节点所共享的随机数产生器来
产生编码向量，省去了编码向量的分发。当Hash值和编码向量的分发都省去时，
该种签名体制的通信开销是几乎可以忽略的。
@@(4)利用消息向量张成线性空间的思想，设计了一种概率模型下的防污染随机网络编
码算法。当信源和信宿共享有一个线性空间时，在信源消息中加入部分冗余，使
得新信源向量张成的空间与信源和信宿共享的空间正交，达到正确译码的目的。
@@(5)Koetter和Kschischang利用有限域上的线性多项式从线性空间的角度设计了一种
网络纠错编码体制，但其编码体制的通信开销较高(100％)，使其很难在现实中
应用。文中对其编码体制进行了改进，在其基础上设计了一种低通信开销的网络
纠错编码体制。该编码体制的通信开销与经典随机网络编码相同。另外，文中同
时考虑了窃听问题，并在此基础上设计了一种防污染和防窃听的网络编码体制。
@@关键词：网络编码，网络安全，污染，纠错，窃听
引证文献(5条)
1.郑伟平.齐德昱.向军.徐克付.韩海雯流媒体分发体系结构演化和关键技术进展综述[期刊论文]-小型微型计算机系统 2010(1)
2.张博.蔡药迪.张金.韩建网络编码基础技术及发展前景[期刊论文]-科技与生活 2009(3)
3.蒲保兴.杨路明.王伟平随机线性网络编码的一种差错控制方法[期刊论文]-小型微型计算机系统 2009(6)
4.石国筑网络编码研究[期刊论文]-科海故事博览·科教创新 2009(1)
5.王青山.王琦.郭清伟.干国政无线网络中基于共同邻居数目的编码算法[期刊论文]-小型微型计算机系统
2010(5)
本文链接：https://www.wendangku.net/doc/ea10239558.html,/Periodical_xxwxjsjxt200804002.aspx
授权使用：江苏大学图书馆(wfhyjs04)，授权号：d976adc0-22d9-419f-be94-9e0000af9ad9
下载时间：2010年9月29日