（通信与信息系统专业论文）基于网络编码的视频传输技术研究.pdf

摘要 随着i n t e r n e t 和视频技术的不断发展，视频传输已经应用于人们生活和工作的 各个方面。由于视频在网络( 尤其是无线网络) 传输过程中，会受到时变带宽、 包延迟以及丢包的影响，所以需要建立有效和健壮的视频传输系统，在网络中进 行可靠的视频传输。 可分级视频编码( s v c ) 是一种具有分级功能且高效的视频编码方法。针对同 一视频内容，s v c 的分级特性决定了只需要对信源进行一次编码，即可满足不同 终端的需要；在具有一定丢包率或拥塞的网络中，s v c 可以使终端在收到部分码 流时依然能够恢复出具有一定失真的视频图像。因此，本文主要对可分级视频编 码的可靠性传输进行研究。 在传统的网络传输方式中，中继节点只用来执行存储转发的简单操作，而网 络编码使其具有对接收到的信息进行编码的功能，因此可以提高网络吞吐量，同 时还能改善网络的可靠性和防范攻击的能力。本文主要研究将网络编码应用于s v c 视频传输，解决或缓解网络丢包和带宽变化给视频传输带来的不利影响，通过研 究合理的网络编码方法来提高视频传输的可靠性以及鲁棒性。 本文详细讨论了网络编码基本原理及其发展和应用，对网络编码在多播方面 的应用进行了详细研究，简单介绍了s v c 码流的预处理算法，同时在s v c 视频传 输系统上，提出了利用网络编码进行视频传输的具体实现方案，完成了基于c 语 言的网络编码系统设计，和原有基于m a t l a b 的网络编码系统相比，提高了仿真效 率；并且结合一些视频码流预处理不同算法，进行了具体仿真，在相同网络结构 以及时延情况下，能够改善视频传输系统的重建视频质量。 关键词：网络编码s v c 打包算法视频传输 a b s t r a c t w i t ht h ed e v e l o p m e n to fi n t e m e ta n dv i d e ot e c h n i q u e ，v i d e ot r a n s m i s s i o nh a sb e e n a p p l i e di nm a n ya s p e c t so fp e o p l e sl i f ea n dw o r k 。b e c a u s ev i d e om a y b ea f f e c t e db y b a n d w i d t hc h a n g e ，p a c k e td e l a ya n dp a c k e tl o s si nn e t w o r kt r a n s m i s s i o n ( e s p e c i a l l y w i r e l e s sn e t w o r k ) ，w en e e dt oc o n s t r u c ta ne f f e c t i v ea n dr o b u s tv i d e ot r a n s m i s s i o n s y s t e mi no r d e r t ot r a n s m i tv i d e oc r e d i b i l i t y s c a l a b l ev i d e oc o d i n go f f e r st h ed e s i r e ds c a l a b l ef u n c t i o n a l i t ya n dc o d i n g e t i i c i e n c y f o rt h es a m ev i d e oc o n t e n t ，t h es c a l a b i l i t yo fs v c d e c i d e st h a tw eo n l yn e e d t oe n c o d es o u r c eo n c e ，a n dt h e nc a ns a t i s f yd i f f e r e n tt e r m i n a l s ；i nn e t w o r kw i t hs o m e p a c k e t sl o s so rc o n g e s t i o n ，s v cc a ns t i l lr e t r i e v et h ev i d e oi m a g e 诹t hs o m ed i s t o r t i o n s a tt e r m i n a l s t h u s ，w em a i n l yr e s e a r c ho nt r a n s m i s s i o nc r e d i b i l i t yo fs c a l a b l ev i d e o c o d i n g i nt r a d i t i o n a lw a yo fn e t w o r kt r a n s m i s s i o n , r e l a yn o d e sa l eo n l yu s e dt od ot h e s i m p l es t o r e a n d - f o r w a r do p e r a t i o n ，a n dn e t w o r kc o d i n gl e ti n t e r m e d i a t en o d e sh a v et h e a b i l i t yo fe n c o d i n gt h er e c e i v e dm e s s a g e s ，s oi tc a ne n h a n c en e t w o r kt h r o u g h p u t ，a n d i m p r o v et h ec r e d i b i l i t yo fn e t w o r ka n dt h ea b i l i t yo fd e f e n s e t h i sp a p e rm a i n l y r e s e a r c ho nu s i n gn e t w o r kc o d i n gt os v cv i d e ot r a n s m i s s i o n ，i no r d e rt os o l v eo r r e d u c et h eb a de f f e c to fp a c k e tl o s sa n db a n d w i d t hc h a n g e ，t h r o u g hr e s e a r c ho na r e a s o n a b l en e t w o r kc o d i n gm e t h o dt oe n h a n c et h ec r e d i b i l i t ya n dr o b u s t n e s so fv i d e o t r a n s m i s s i o n t l i sd i s s e r t a t i o np a r t i c u l a r l yd i s c u s s e st h eb a s ep r i n c i p l eo fn e t w o r kc o d i n ga n di t s a p p l i c a t i o n ，d e e p l ys t u d i e st h ea p p l i c a t i o no fn e t w o r kc o d i n gi nm u l t i c a s t ，a tt h es a m e t i m e ，s i m p l yi n t r o d u c e sp r e t r e a t m e n ta l g o r i t h m so fs v cc o d e s ，p r o p o s e sad e t a i l e d s c h e m et h a tu s i n gn e t w o r kc o d i n gf o rv i d e ot r a n s m i s s i o ni ns v cv i d e ot r a n s m i s s i o n s y s t e m ，c o m p l e t e sn e t w o r kc o d i n gs y s t e md e s i g nb a s e do ncl a n g u a g e c o m p a r i n gw i t h n e t w o r kc o d i n gs y s t e mb a s e do nm a t l a b ，t h ef o r m e re n h a n c e st h es i m u l a t i o ne f f i c i e n c y ； a n dt h es c h e m ec o m b i n e ss o m ed i f f e r e n ta l g o r i t h m so fv i d e oc o d e sp r e t r e a t m e n t ( s u c h a sp r i o r i t y , p a c k e t i z a t i o na l g o r i t h m ) t os i m u l a t e ，r e s u l t sp r o v et h a ti ti m p r o v e st h ev i d e o q u a l i t yu s e rr e c e i v e d0 1 1t h ec o n d i t i o no ft h es a m en e t w o r ka n dd e l a y k e yw o r d s ：n e t w o r kc o d i n g s v cp a c k t i z a t i o na l g o r i t h mv i d e ot r a n s m i s s i o n 创新性声明 本人声明所呈交的论文是我个人在导师的指导下进行的研究工作及取得的研 究成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中 不包含其它人已经发表或撰写过的研究成果；也不包含为获得西安电子科技大学 或其它教育机构的学位或证书而使用过的材料。与我一同工作的同志所做的任何 贡献均已在论文中做了明确的说明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切相关责任。 本人签名：杰亟固日期：迦f 殳：l2 皇 关于论文使用授权的说明 本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：研究 生在校攻读学位期间论文工作的知识产权单位属西安电子科技大学。本人保证毕 业离校后，发表论文或使用论文工作成果时署名单位仍然为西安电子科技大学。 学校有权保留送交论文的复印件，允许查阅和借阅论文；学校可以公布论文的全 部或部分内容，可以允许采用影印、缩印、或其它复制手段保存论文。( 保密的 论文在解密后遵守此规定) 本人签名：奎墼蠲 导师签名：豸查 日期：趔殳：! ：12 日期：卫f2 ：! ：! ! 第一章绪论 第一章绪论 1 1 引言 随着视频编码技术、网络基础结构的逐渐成熟和计算能力的快速提高，数字 视频( 诸如：视频会议，多媒体聊天，视频点播，i p t v ) 已经通过有线和无线的 i p 网络走进千家万户。在一般宽带网络，尤其无线网络中，视频传输受时变带宽、 包延迟以及丢包的影响。可分级视频编码标准【1 】【2 j 作为h 2 6 4 m p e g - 4 a v c 的延伸， 已经吸引很多学者对其灵活的可分级性和适应性在不同变化网络条件，网络应用 以及网络终端中研究。一个有效和健壮的s v c 传输系统是可以克服这些影响，从 而达到可靠视频传输的。 可分级视频编码( s v c ) 是一种具有分级功能且高效的视频编码方法。s v c 可 以把视频序列编码成由一个基本层和多个具有不同分级特性的增强层组成的码 流，其中基本层可以恢复出具有最低分辨率和最低质量的图像序列，而增强层可 以恢复出具有较高分辨率和较高质量的图像序列。s v c 提供的时域，空域和质量 域三种可分级方式，保证了终端可以从收到的s v c 码流中提取出满足一定目标码 率，帧率以及空间分辨率的码流，并恢复出具有不同码率、帧率或者分辨率的视 频图像。因此，s v c 是一种适用于网络视频传输的算法，具有日益广泛的应用前 景。随着宽带网络的发展和人们对视频内容需求的增加，在基于s v c 的视频系统 中，对同一视频内容，不同的终端可能需求更快的帧率，或更高的分辨率，或者 更佳的质量，s v c 的分级特性决定了只需要对信源进行一次编码，就可满足不同 终端的需要；在具有一定丢包率或拥塞的网络中，不同终端在一定的时间内可能 收不到全部码流，s v c 可以使终端在收到部分码流时恢复出具有一定失真的视频 图像，因为较低分辨率，帧率或质量的视频可以从较低层的码流中重建得到。 在实际应用中，同不可分级的h 2 6 4 a v c 类似，s v c 定义了视频编码层( v c l ) 和网络抽象层( n a l ) ，其中v c l 中包含了表示视频内容的句法元素，n a l 包含 v c l 和用于传输层的包头信息。 1 2 视频传输方法 目前，在h 2 6 4 s v c 标准的软件j s v m 中【3 1 ，默认的s v c 码流排序方法是以 g o p ( c r o u po f p i c t u r e ) 为单位按时域层排序的。每一个时域层包含一些空域层， 这些空域层又可能包含一个基本的s n r 层和几个增强的s n r 层。同时，s v c 在 2 基于网络编码的视频传输技术 网络中传输使用了n a l u 。当一个n a l u 丢失时，所有依赖此n a l u 的n a l u s 都要受到影响，有时它可能造成后边的s v c 比特流在接收端不能解码。因此，一 种合理的码流排序方法是s v c 视频码流传输的关键问题之一。 文章 4 】中提出一种基于质量层的排序算法。该算法假设第i 帧图像编码成d 层( 比如q c i f 层，c i f 层和4 c i f 层) ，每一层图像编码成基本层和质量层，其中 质量层的q p 为q ，计算每幅图像的码率函数r ( d ，i ，q ) 和失真函数d ( d ，i ，q ) ， 通过建立r d 曲线确定最优的质量层排序。该算法是基于图像帧的排序算法，没 有考虑不同层对整个g o p 率失真性能的影响。 在具有一定丢包率的实时系统中，前向纠错( f e c ) 方式下的数据包打包方案是 视频传输方案中研究的重点问题。文献 5 首先提出了优先编码传输的概念，它由 用户将压缩的多媒体码流分成不同的码段，并指定相应的优先级，然后使用r s 码 对不同优先级的码段施加不同强度f e c 冗余保护，但该方法并没有给出划分码段 和指定优先级的原则和算法。基于优先编码传输方法，文献【6 】中提出了两种基于 动态规划的打包方法，一种是适用于一般情况的复杂度为o ( n 2 l 2 ) 的算法，另一种 是适用于包丢失概率为单调减函数、失真一率曲线为凸函数的复杂度为o ( n l 2 ) 的 方法。它们在理论上是最优的，但占用存储器容量很大，速度最慢。随后，文献 7 】 提出了一种快速局部搜索打包算法，其复杂度为0 ( n l ) ，在运算速度大部分情况 下具有优势。然而，这些打包算法都不适用于基于s v c 码流的传输系统，无法有 效的对s v c 码流进行打包。 终端重建视频图像的质量受网络中信道丢包率的影响，当丢包率增大时，重 建图像质量会明显下降。现有的基于可分级视频编码的传输方法提供的码流排序 和打包方法不能满足网络视频系统的需求，为了保证s v c 视频流的服务质量，需 要一种行之有效的技术手段在视频系统中对码流进行有效的处理。 1 3 网络编码当前发展状况及未来展望 目前，国内外多所大学和研究机构都积极开展对网络编码理论及应用的研究， 形成了一个异常活跃的学术场面。在麻省理工学院( m i t ) 、南加州大学( u s c ) 、 多伦多大学( u t ) 、朗讯贝尔实验室( l u c e n tb e l ll a b ) 、微软研究院( m i c r o s o f t ) 等地都已经形成了有相当实力的科研队伍。在国内，除了网络编码的发源地香港 中文大学外，清华大学、北京大学、复旦大学、中国科学技术大学、北京邮电大 学、上海交通大学、西安电子科技大学等机构的研究人员也已经积极投入到网络 编码的研究中。 一些声名显赫的高科技企业，如微软、惠普和英特尔等都正在着手从事“网 络编码”的技术，该技术可以提高网络的吞吐量，改善从内容分发到无线网络等 第一章绪论 3 一系列网络技术的可扩展性和使用效率。网络编码可以在任何设备上工作，从路 由器到无线系统，或者全新形式的所谓网络编码器上工作。英特尔看到了这种技 术在扩展无线基站方面的潜力；微软已经在试验用网络编码来提高其内容分发系 统的效率；其他网络厂商，比如思科，正在研究网络编码能否作为一种区分不同 类型的流量，然后划分出优先等级，从而帮助提高网络容量的理论工具；和微软 一样，惠普也看到了网络编码对p 2 p 内容分发所带来的好处，惠普已经与麻省理 工学院展开了合作，并赞助后者在此领域的研究工作。 在网络基础设施中，网络编码的应用要比简单地帮助内容分发问题“更为棘 手”。网络编码必须证明自己能够获得较大的性能提升，才可能被基础设施厂商所 采用。比如网络编码必须能解决一个特殊问题，多播或许就是网络编码可以大显 身手的所在。不过目前多数企业还没有用到多播。 几年前，微软以网络编码作为核心技术开发出“雪崩”原型软件。“雪崩 对 于p 2 p 替补供需比的大规模内容分发而言，传送速度可高出b t2 0 3 0 。由于 p 2 p 通信占互联网带宽的6 0 以上，所以研究人员估计，未来十年网络编码技术 将会产生巨大影响，从计算机通信，无线通信到其他各类通信，都会广泛地采用 网络编码。麻省理工学院电子工程与计算科学系的助理教授、网络编码领域的主 要研究者之一m u r i e lm e d a r d 认为，网络编码尤其对路由器共享的基础设施( 如互 联网) 、p 2 p 内容分发以及无线网状网络特别有用。m e d a r d 和其他研究者指出，网 络编码具有极大地提高网络传输速度、改进所有通信系统可靠性的潜力，将会引 发下一代网络革命。不过，m e d a r d 也认为，网络运营商如何利用这种技术来实现 网络编码尚有待探索。因为它不同于m p l s 的流量工程( m p l s 是提高网络容量 和效率的另一种方法) ，m p l s 无须改变数据包中的数据；而只是给数据包增加一 些附属物，比如标签。目前的路由器和交换机系统只是去读数据包中的源地址和 目标地址的域，将输入和输出都映射到同一个节点上然后直接传输。它们不会综 合两个不同数据包的内容，更不会把输入映射到一个节点，把输出映射到另一个 节点。网络编码器或许不会彻底取代路由器，但其功能有可能会覆盖掉一部分路 由功能。而随着时间的推移，网络编码便有可能在其优势日益明显之后成为路由 操作的一个不可缺少的组成部分，从而彻底改变我们今天所知的路由技术。 英特尔也在期待网络编码能为其无线产品，尤其是为w i m a x 产品提供竞争 优势。英特尔的网络编码研究开始于2 0 0 6 年。研究部门的s a n d h u 表示，多跳中 继( m u l t i h o pr e l a y ) 由w i m a x 基站和中继基站完成，可以从网络编码获得 益处，因为后者扩展了基站的覆盖范围。中继基站负责对基站的回程，而网络编 码则可在端到端的基站一客户机的交互过程中实现双向中继。由于使冗余的分组路 由降至最低，从而提高了网络的效率。在此应用中，网络编码要比简单的双向中 继增加2 5 至u5 0 的吞吐量。因为在基站间执行异或操作可节省时间，在做端到 4 基于网络编码的视频传输技术 端双向通信是原来需要4 个时隙，而现在只需要3 个时隙，其中在一个时隙中实 际上是把两个数据包揉在一起发送出去的。但是w i m a x 并不像军用感应器网络， 它是集中式的。一个基站负责一个蜂窝小区，然后可能会架设几个中继基站进行 覆盖范围的扩展，这是w i m a x 网络的通用模式。英特尔正在探讨网络编码在o s i 参考模型中物理层上的适用性，以及它在m i m o 环境中与天线的相互影响。由于 物理层信息在向上进入m a c 层时有可能丢失，所以英特尔正在寻找捕捉物理层信 道信息的方法，以便实现更优化的网络编码。 当前，针对网络编码研究的各方向分为：网络信息论和多信源网络编码、网 络随机编码、网络卷积编码、网络纠错编码、网络安全编码。其意义在于：网络 编码作为提高网络通信有效性的重要手段，根植于信息论并与信息论有着紧密的 关系，因此有必要研究网络信息论这一重要方向；网络随机编码是解决对网络拓 扑结构未知情况下的编码问题，可根据网络的不同特性，设计适应各种实用网络 环境的不同的网络随机编码，以更大地提高网络的性能；网络卷积编码是一类重 要的网络编码，目前它是唯一能够应用在有环网络上有效解决时延问题的编码， 那么要在实际网络环境中应用网络编码，对网络卷积编码的深入研究是重要的一 个环节；网络纠错编码是网络传输可靠性的研究，深入研究网络纠错编码问题， 可以推动网络编码的实用化进程；随着网络犯罪及窃听的涌现，网络信息安全的 重要性越来越突出，因此网络安全编码学要进一步发展。 至于网络编码能否在互联网这种共享基础设施中最终取代路由器，也同样还 需要解决很多问题才行。比如说，客户必须知道，当信息在共享网络中不能够进 行混合的时候该如何实施网络编码；他们还需要注意网络编码在有线和无线基础 设施中的细微差别；而业界必须能够找出某种办法，当运营商把不同客户的不同 流量相互混合时，客户到底应该如何付费。将来我们还有很多问题继续去探索来 改变网络的各种途径，以便让网络成为人们生活中不可缺少的部分。 1 4 本文主要内容及章节安排 本文详细讨论了网络编码基本原理及其应用，对网络编码在多播方面的应用 进行了详细研究，主要研究了基于网络编码视频传输的实现和性能分析。在研究 了网络编码理论和s v c 码流结构的基础上，本文提出了利用网络编码进行视频传 输的具体实现方案，并且基于c 语言在p c 平台上实现了网络编码视频传输，详细 阐述了其具体实现过程。另外，在网络编码视频传输中进行了不同打包算法的性 能比较分析。 本文的章节安排如下： 第一章“绪论 主要介绍了视频传输方法及网络编码的当前发展及未来展望。 第一章绪论 5 第二章“网络编码原理及其应用介绍了网络编码的基本原理，发展历史及 其应用。 一 第三章“s v c 比特流的预处理”介绍了s v c 码流预处理方法，如排序、打包 算法。 第四章“基于网络编码的视频传输仿真 对于基于网络编码的视频传输系统 进行说明，并且分别进行模块介绍和模块之间的接口介绍。具体阐述仿真中所用 到的具体算法和流程，以及仿真结果的性能比较分析。 第二章网络编码原理及其应用 7 第二章网络编码原理及其应用 2 1 网络编码定义 网络编码【8 】，从广义上讲，是网络中的节点接收到的信息经过编码后再转发出 去的多点传送技术。多点传送，也称组播，是网络中的种重要的通信方式，即 当一个节点或几个节点同时向若干节点发送数据时，往往要借助其他节点的传递。 一般的传统网络，中继节点只对收到的信息做复制，放大和转发，这对于网络资 源有时候是一种浪费。网络编码打破了这种限制，它允许中继节点对接收到的信 息进行编码，并将接收到的多个数据包按照某种特定算法重新组合再发出去，目 标节点只需进行演绎还原就可以，这样就不必反复传输或者复制全部信息。因此， 网络编码技术可以大大提高网络的吞吐量和可靠性。鉴于网络编码潜在的优势和 特点，它将成为通信领域的一个新的研究热点。 2 2 网络编码的原理 2 2 1 网络编码的基础理论 网络结构形式分为无环网络( 即网络链路中没有回路) 和有环网络( 即网络 链路中有回路) 。在一般的环境中，源节点产生一个多点传送到某些目的节点的信 息管道。当通信网络是无环网络时，在所有节点的操作是每个信息从上一层节点 到下一层节点同步地、独立地编码和传送，每个信息的处理过程在管道中是独立 于连续信息的。此时，网络编码问题是独立于传播延迟的，传播延迟包括在信道 上的传输延迟和在节点上的处理延迟。另外，当网络包含环路时，连续信息的传 播和编码交织在一起，因此延迟的数量变成在网络编码中要考虑的部分。为了便 于简单说明网络编码理论，我们以下均采用无环网络情况。 网络编码简而言之是一种输入和输出的映射。将输入节点t 的各个通道上的 符号映射成t 的某一输出通道上的符号，这样的映射我们称之为局部编码映射， 也称本地编码映射；将原始信息映射为t 的输出通道上的符号，这种映射我们称 之为全局编码映射。局部编码映射与全局编码映射都必须满足本地编码映射【8 】，如 图2 1 所示。图2 1 中，记每个节点t ，其对应的通道为e o u t ( t ) ，局部编码映 射为t ，全局编码映射为z ，发送信息x = ( 6 1 ，b 2 ) 是i g f ( 2 ) 1 2 上的矢量，那么全局 编码映射：对于e = 傩，s r ，删，玎，无( 岛，6 2 ) = 6 1 ；对于e = o s ，s u ，u w ，u z ， 8 基于网络编码的视频传输技术 z ( 6 1 ，6 2 ) = 如；对于e = o s ，s u ，u w ，u z ，z ( 岛，b 2 ) = b 2 ；对于p = 麟，x y ，忍， z ( 6 l ，b 2 ) - - b , o 如。对应的局部编码映射：砖( 6 1 ，6 2 ) = ( 6 1 ) = 而( 2 j 1 ) ， 毛( 6 l ，6 2 ) = ( 岛) = 砭( 6 2 ) ，( 2 j l ，也) = 6 1o 6 2 。前者是对源信息x 的编码映射， 后者是对某节点的输入通道上的数据单元构成的矢量的编码映射。 2 2 2 线性网络编码 图2 1 网络编码原理 具有网络编码的信息传播物理实现受到信道上的传输延迟和节点上的数据处 理延迟的影响。目前，节点数据处理很可能是经过网络信息传送中总延迟的主要 因素。因此希望在一个网络编码过程中编码原理可以通过简单和快速的链路得以 应用，所以只涉及线性映射的网络编码是非常适合的。如果当前所有全局编码映 射和本地编码映射都是线性的，那么对应的网络编码称为线性网络编码。 维f 值的线性网络码，对于无环网络的每一对通道( d ，e ) 都存在一个局 部编码核( 1 0 c a le n c o d i n gk e r n e l ) 标量k d 。而对于节点t ，其局部编码核是 l i ( r ) l l o u t ( r ) j 的矩阵，表达为 k r = l k 如j 川咿如毗们) 式( 2 1 ) 其中d 表示进入t 的通道，e 表示流出t 的通道。矩阵的结构隐含了所考察的 通道的次序。 由于节点t 上的局部编码映射是线性的，那么对于该节点的输出通道e ，有 第二章网络编码原理及其应用 9 是厶的线性组合 无= 幻，。厶 d e l n ( t ) 式( 2 2 ) 其中e o u t ( t ) ，称为全局编码核【8 1 。 局部编码映射则可以表达为i i n ( t ) i 维的列矢量吃。每个输出符号表达为 厄( y ) = y 屯，其中y 是i 加( r ) | 维行矢量，表示节点t 在各个通道上收到的符号。 全局编码映射一般表达为维的行矢量z ，那么输出符号就可以用线性表达式： z ( x ) = 工z 式( 2 3 ) 这个线性表达式是可以递推的： z ( x ) = x z = x ，。厶= 幻，。 厶) d e l n ( t ) d e l n ( t ) 图2 2 线性网络编码 用图2 2 来说明线性编码核。如图，局部编码核： k 。= ( ：) ，巧= 杨= 如= ( tt ) ，勘= ( ：) ： 对应的全局编码核： ：) 1 0 基于网络编码的视频传输技术 f t = s i ，s 2 ，s 3 对千e = o s ，s t ，t 彬，t y 对于e = o s ，s u ，u 形，u z 对于e = w x ，x y ，x z 】，( p ) = 口铂+ b i n 2 图2 3 一个节点的线性简单编码原理 线性网络编码如图2 3 所示，其中s l ，s ，是，s 3 g f ( q ) ，m 2 是节点w 的 输入信息，y ( e ) = 哪+ b r n 2 ，( a ，b ) 是边e 的本地编码向量；】，( p ) = a s + p s 2 + r s 3 ， ( o c , 卢，7 ) 是边e 的全局编码矩阵。 2 2 3 最大流最小割定理 随着各种网络拓扑的日益复杂，传统的路由方式容易导致网络负载不平衡以 及网络资源有效利用率低。最大流最小割定理( m a x f l o wm i n c u t ) 【9 】【1 2 l 正是为 解决该问题的一种理论，它提供了一个可容许编码速率区域以及网络容量的范围。 假设s 是信源节点，d i ，i = l ，2 表示目的节点，则从s 到d i 之间的最大 流量( m a x f l o w ) 等于在这个通道上最4 , n ( m i n c u t ) 的容量值。 最大流最小割定理描述单信源问题的可容许编码速率区域，确定从一个源节 点到多个目的节点同时可以发送多少个信息是有效的。在文【9 有一种猜想：当且 仅当从源节点到目的节点的最大流的值大于或者等于信源的速率时，我们可以得 到可容许编码速率区域。对于一个目的节点的网络如图2 4 ，( a ) 表示了每条边的 容量。运用最大流最小割理论，从s 到t l 最大流的值是3 ，所以在( b ) 中的码流是 最大流。在( c ) 中，表示了怎样基于( b ) 中的最大流能从s 到t l 发送3 比特b l ，b 2 ，b 3 信息。对于两个目的节点的网络如图2 5 ，很容易从( a ) 中得出从s 到t l 和到t 2 的最 1j，j 1j 1 o 0 11 1 r。，l一_。l 夕 第二章网络编码原理及其应用 大流分别是5 和6 。所以才想认为可以同时发送5 比特b l ，b 2 ，b 3 ，b 4 ，b 5 ，信息到t l 和t 2 ，并且( b ) 展示了那样一种方案。注意到用这种方案，比特数仅需要在节点 被复制而获得最佳性。两个目的节点的另一种情况如图2 6 所示，由( a ) 可以容易 知道从s 到t l 和t 2 的最大流的值是2 ，所以那个猜想认为我们可以同时发送2 比特 b l ，b 2 信息到t l 和t 2 ，而且在( b ) 中表示了那样一种方案，“o 表示模2 加。在t l 上，b 2 能够从b l 和6 1o2 j 2 中恢复出来。相似地，6 1 在如也能都恢复出来。注意的是， 当多于一个目的节点时，我们不能再认为信息是一个实体，因为信息需要在节点 上被复制或改变。在这个图中，信息在节点3 被编码是不可避免的。当目的节点 大于2 个时，在最佳多点传送的方案中，一般是需要网络编码的。 ( a ) 图2 4 一个源节点一个目的节点的网络 b ( a )( b ) 图2 5 无编码的一个源节点两个目的节点的网络 3 1 2基于网络编码的视频传输技术 图2 6 有编码的一个源节点两个目的节点的网络 2 2 4 随机编码和解码 由于在某些实际网路中，节点可能不完全知道网络的拓扑结构，并且网络拓 扑也可能时刻变化着，所以随机编码为在这些网络中实现网络编码提供了一种可 能的方法。简而言之，网络随机编码和解码是解决对网络拓扑结构未知情况下的 编码和解码问题。 原始信息形式为：墨，是，其中s ，f 【1 ，m 代表一个信源s 中的元素；经 过编码后的形式为：m ，y 2 ，y m ；全局编码矩阵的形式为：( g f l 岛2 吕。) ， 其中随机变量吕，f ， 1 ，m 】可以设定为一个域上随机产生的整数；则随机编码的表 达式为： ( g f l g i 2 件以 l j 全局编码矩阵( g , j ) 可以是在该域上随机产生的整数矩阵。因此，随机编码 的表达式可写成： 睢挑 - 1 如果矩阵( 岛) 是可逆的，那么可以得到 式( 2 6 ) 第二章网络编码原理及其应用 1 3 警寸l i j 2 2 5 结合实际应用的网络编码理论 p h i l i pa c h o u 等人已经提出一种针对实际网络编码的分布式方案【l 引。这种 方案不需要图拓扑的集中知识，编码函数和译码函数，更加避免了通过网络时信 息同步的要求。网络编码的实际体系对于随机丢包和时延是健壮的；同时，由于 连接，分支，节点或者链接失败，拥塞等等，网络编码的实际体系对于网络拓扑 或容量的任何变化也是健壮的。他们并指出这种实际网络编码系统能够达到接近 理论的最佳性能。 首先，他们在文 1 3 】中提出了一种包格式。这种包格式可以不需要图拓扑的集 中知识，编码或者解码函数。这是实际网络编码方案的基础。 这样，在任一接收节点需要求逆码的全局编码向量能在到达包自身中找到。 这种方案能简单地实现，通过预先计划第i 个单元向量对应第i 个源向量 鼍，待l ，h ，并且在每一个节点与通常一样处理向量们。然后任何一个接收节点 都能够利用高斯消去法在接收到的h 或者更多的包里，恢复源向量五。 但是这个方案的代价是在每一个包里传送附加h 个符号的包头。不过这是合 理的：如果h 是5 0 ，域的大小是2 8 ，那么包头大约是3 。另一方面，这种方案的 好处是深远的。它获得了完全分散的能力：接受器在不知道网络拓扑或者编码函 数的情况下能够译码；甚至增删节点或者边，接收器也能够译码；在没有告知丢 包或失败的位置的情况下，有丢包或者节点，链路失败时，接收器能够译码；甚 至当本地编码向量是时变和随机选取的，接收器也能够译码。 2 3 网络编码发展历史 网络编码的基本概念是在1 9 9 7 年，由杨伟豪教授和张真教授发表的对于卫星 通信网络数据传输的文章【1 4 】中首次引入。2 0 0 0 年，r a h l s w e d e ，蔡宁，李硕彦 和杨伟豪发表在i e e e 上的文章 9 】中，网络编码得到全面发展。这是在网络编码方 面的第一篇文章。这篇文章介绍网络信息流的概念，以及把多点传送的问题( 在 、，8 2 式 、， ； 1 j j 1 ； “ u ；l-：o ，。一 g = 、， ) ) q ) ) ； n n ) ) 勺 “ “ ) ) 1 ； g g，一 1 4 基于网络编码的视频传输技术 一个图中从一个节点发送给一个节点子集) 与流问题联系起来；指出一个典型接 近最佳多点传送的方法( 用许多多点传送树) 不是最佳的；证明了在单源多播传 输中，利用网络编码可以使所有接收节点达到网络信息流的最大流界，而在很多 网络中采用路由的方式无法达到最大流界。这标志着网络编码理论的诞生，开创 了网络编码这一崭新的研究领域。 2 0 0 3 年，网络编码从理论向实际应用迈出了重大的一步。2 月李硕彦、杨伟 豪和蔡宁在i e e e 上发表了论文“l i n e a rn e t w o r kc o d i n g ，【”】并于2 0 0 5 年荣获i e e e 信息理论学会论文奖。该工作介绍了一种简单的在单信源多播通信中利用网络编 码达到最大流界的线性算法( 只是利用有限域上的加法和乘法) ，降低了编码的复 杂度，很具有启发性，为网络编码的实际应用奠定了基础。 然而，在实际的网络环境下，网络拓扑结构可能是动态的，即现有的用户( 节 点) 随时可能离去而新的用户可能加入通信。2 0 0 3 年6 月，由h o ，m e d a r d 等人编 写的 1 6 】发表之后，随机网络编码则正式诞生了。他们介绍了在网络中，对于健壮 的，分布式的传播和信息的压缩，一种新的随机网络编码方法，并且阐述了较基 于路由的方法的优点；对于无环无延迟的网络，就接收随机编码输出链路的数量， 给出了错误概率的界限。为了在动态拓扑的网络中应用网络编码，t h o ，r k o t t e r 、 m m e d a r d 和m e f f o r s 等人提出了分布式随机线性编码的方法f 1 7 j 。【1 9 】。其新颖之处 是网络中的节点并不需要知道网络拓扑结构，不用实现构造网络编码，而是在通 信过程中独立、随机地选取输入链路至输出链路的线性映射。该方法是分布式的， 利用冗余的网络容量来提高成功概率，对拓扑变化或链路失效具有鲁棒性。然而 这种随机编码带来了一定的包头开销和编码失败风险，这些问题还有待进一步解 决。 随着通信蓬勃发展的时候，随之而来通信网络中的犯罪行为和用户对隐私保 护要求增加，为保护用户的合法权利和涉及国家安全的各种机密，网络信息安全 的重要性越来越突出。以反窃取传输信息为目标的网络安全编码由蔡宁和杨伟豪 在文 2 0 】中研究。他们提出了窃听网络上的通信系统模型，为单信源网络构造了反 窃听的网络安全编码。这个通信模型由一个通信网络和一个窃听信道的子集系组 成，攻击者可能接入子集系中的任意一个子集里的全部信道获取这些信道上传输 的全部数据，但不能让他获得有关信源消息的任何信息。其后，j f e l d m a n 、t m a k i n 、c s t e i n 和r a s e r v e d i o 在文【2 1 】中用以构造网络安全编码的预编码矩阵， 指出了它与线性纠错编码之间的联系。近期，n c a i 和r w y e u n g 将他们的工作 推广到多信源网络乜羽，发现了一般窃听网络上通信系统安全编码的充分必要条件， 为这类网络安全编码走向应用奠定了基础。 2 0 0 6 年，r a y m o n dw y e u n g ，s h u o y e nr o b e r tl i ，n i n gc a i ，z h e nz h a n g 共同 编著的“网络编码理论，【8 j 出版。这本书可以说是网络编码理论方面的第一本教科 第二章网络编码原理及其应用 1 5 书。至此，网络编码理论方面已有了很大的发展，网络编码的原理也清晰呈现出 来。 2 4 网络编码应用 网络编码可以将现有的网络吞吐量提高一倍，同时还能改善网络的可靠性和 防范攻击的能力。网络编码技术更有可能会潜移默化地改变目前基于路由的网络 架构。鉴于网络编码无可比拟的优势，网络编码技术已经开始逐渐应用于通信的 各个方面。 2 4 1 网络编码在多播方面的应用 所谓多播，就是同时把信息传送给一组目标节点，按照和传统路由架构同样 的方式，网络编码就能大大改善网络的效率，我们可以获得网络多播速率的最大 流限，即网络资源利用的理论上限，通过传统的路由，复制并不一定能够获得最 大流限。此外通过网络编码我们可以取得节省网络带宽资源，平衡链路负载，优 化能量受限网络的能量消耗等好处。传统路由的多播在连接多个目标节点时需要 生成全部传送信息的多份拷贝，而网络编码则可通过编码处理，大大减轻这种传 输多份信息的压力。 2 4 1 1 利用网络编码进行多播的主要优势 网络编码多播的特点主要体现在3 个方面： ( 1 ) 节省带宽 运用多播技术分发信息常常能从本质上减少整个网络带宽的需求。与单播技 术( 点到点通信方式) 相比，当多个用户要求同一服务器提供同样信息时，使用 单播技术，带宽将随用户的增多而增加需求，而对于多播，由于在公用链路上传 递信息的一份拷贝，因此带宽的需求不会随用户数量的增加而增加。对于相同多 播速率的情况，网络编码多播与传统i p 多播比较，前者可以节省多播对网络带宽 资源的消耗。图2 7 中，信源s 要向接收节点发送两比特信息6 1 ，易。其中( a ) 采 用的是传统i p 多播，可看出链路( s ，3 ) 的容量为2 ，整个网络需要传送1 0 比特， 即占有的网络带宽为1 0 。但是( b ) 采用网络编码时，s 发送反ob 2 到节点3 ，节 点f ：可以从6 1 和岛。如得到6 2 ，如= 6 lo6 1o6 ，同样节点厶也可以从6 2 和岛o2 j 2 中 得到反。链路( s ，3 ) 的容量为l ，整个网络只需要传送9 比特，即消耗的总带宽 为9 。所以图( a ) 比( b ) 要多发1 比特数据，所以网络编码后节约了1 0 。 1 6 基于网络编码的视频传输技术 l + b 2 图2 7 网络节点的数据传输 ( 2 ) 降低服务器负载 单播实行点到点的通信模式，随着用户数目的增加，严重增加服务器的负担， 多播实现点对多点的通信，对多目的节点共享的链路只传送一次，这大大减少服 务器的负担，从而提高服务器的处理能力。 ( 3 ) 降低网络负载 当将相同的内容传送给多个用户时，多播能明显地减少带宽要求，带宽消耗 的降低等同于路由器上的负载降低。但是现有的i p 多播路由经常造成网络流量的 不均衡分布，现有的多播路由协议主要可分为基于核心的路由协议和基于信源的 多播路由协议。基于核心的路由协议经常造成流量过分集中于某一节点。而基于 信源的多播路由协议也会由于多个多播树的叠加，造成某一链路流量的过载，影 响网络的服务质量。基于网络编码的多播利用多条路径进行信息数据的传输，可 以平衡网络链路的负载。如图2 8 ，( a ) 图示一个通信网络，各边上的容量均为2 。 ( b ) 所示一种单会话组播树，可见组播的容量为2 ，即可以同时传输2 比特信息给 每个接收节点，信源向所有接收节点传送信息的实验方式体现在所有传输集中在5 条链路上，而网络中的其他链路没有得到充分利用，为空闲状态；而( c ) 是一种基 于网络编码的组播树，其容量为4 ，即可以同时传输4 比特信息给每个接收节点， 其实现方式使用了网络中的所有链路实现信息的传输，在信息传播中，均匀地分 布于整个网络。( b ) 中情况必然会引起所用链路上的拥塞