（通信与信息系统专业论文）面向异构网络的网络编码技术研究.pdf

， ： 0l ， ， 旷 r e s e a r c ho nn e t w o r kc o d i n gf o r h e t e r o g e n e o u sn e t w o r k s d i s s e r t a t i o n s u b m i t t e dt ob e i ji n gu n i v e r s i t yo fp o s t sa n dt e l e c o m m u n i c a t i o n s f o rt h ed e g r e eo f d o c t o ro fp h i l o s o p h y i nc o m m u n i c a t i o na n di n f o r m a t i o ns y s t e m s b y s ij i n g j i n g s u p e r v i s o r ：p r o f c a ia n n i o c t o b e r16 m ，2 0 0 9 弦0 yf、， 矗， “ t 广 ， l 01 一j 独创性( 或创新性) 声明 本人声明所呈交的论文是本人在导师指导下进行的研究工作及取得的研究 成果。尽我所知，除了文巾特别加以标注和致谢中所罗列的内容以外，论文中不 包含其它人已经发表或撰写过的研究成果，也不包含为获得北京邮电大学或其它 教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任 何贡献均已在论文中作了明确的说明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切相关责任。 本人签名：鲻 关于论文使用授权的说明 学位论文作者完全了解北京邮电大学有关保留和使用学位论文的规定，即： 研究生在校攻读学位期间论文工作的知识产权单位属北京邮电大学。学校有权保 留并向国家有关部门或机构送交论文的复印件和磁盘，允许学位论文被查阅和借 阅；学校可以公布学位论文的全部或部分内容，可以允许采用影印、缩印或其它 复制手段保存、汇编学位论文。( 保密的学位论文在解密后遵守此规定) 保密论文注释：本学位论文属于保密在年解密后适用本授权书。非保密论 文注释：本学位论文不属于保密范围，适用本授权书。 本人签名：舅 导师签名： 日期：型! ：! ! ! 日期：递f 壁一。区 o ，- y f ，、 1 ， ， i ? 0 北京邮电大学博士学位论文摘要 面向异构网络的网络编码技术研究 摘要 网络编码是对传统路由机制的革命性突破，其核心思想是允许网 络中的节点对传输的信息进行处理和操作，而不再仅限于存储和转 发。网络编码能显著提高网络传输性能，具有重要的理论价值和广阔 的应用前景。异构性是通信网络的固有特性，网络各部分资源的不均 匀以及端系统处理能力的差异是异构性存在的根源。因此，如何基于 网络编码为异构网络设计高效的信息传输方案是一个非常有意义的 研究课题。本文正是面向这一课题，研究适用于异构网络的网络编码 技术，从而实现异构网络上的高效信息传输。 本文的主要研究工作包括： 针对恒定速率分层组播网络编码存在的问题，本文研究速率可调 的分层组播网络编码方案。推导出了实现分层组播网络编码速率最优 分配的必要条件；并提出了一种以最大化网络总吞吐量为目标的分层 组播网络编码速率的优化选择算法。基于本算法实现的分层组播网络 编码能够获得比现有方案更高的网络总吞吐量。此外，为了使本算法 同样适用于具有较高异构性的大规模网络，本文还提出了一种基于遗 传算法的优化问题求解方案。此方案能够以较高的时间效率求解出分 层组播的最优速率分配。 针对组播内网络编码对适用网络的限制，本文根据信源分层编码 严格的等级化结构提出了一种基于组播间网络编码的多速率信息传 输方案层间等级组播。本文将层间等级组播中各链路编码类型的 优化选择问题划归成了一个o 一1 规划问题，并提出了一种启发式的层 间编码类型优化选择算法。理论证明和实验结果均表明本文构建的层 间等级组播能够获得高于分层组播的网络总吞吐量。 为了避免求解复杂的多组播资源优化分配问题，本文转而研究利 用单一线性网络编码会话在异构网络中实现多速率信息传输的可行 性。本文从理论上研究了基于随机网络编码传输采用特殊方式打包的 信源分层编码数据的广播方案，推导出了在异构网络中利用单一线性 广播网络编码会话实现多速率信息传输的成功概率。 上述推导表明由于线性网络编码无法保证接收端解码空间的维 构建方案。在采用本方案的网络中，无论是信源发送速率发生变化还 是网络中某些链路发生故障，网络中任意节点上的编码操作均无需改 变。 最后，本文还研究了线性网络编码在p 2 p 流媒体传输网络和无线 传感器网络中的应用。设计了分层随机线性网络编码与层间等级随机 线性网络编码在p 2 p 流媒体传输网络中的应用方案，利用它们的局部 解码能力来保证网络节点播放的流畅性。基于网络编码研究了无线传 感器网络生存时间的最大化，设计了符合无线网络中能量消耗实际情 况的能耗测量模型，实现了无线传感器网络中能量资源的优化分配。 关键词：线性网络编码，异构网络，多速率，变速率，分层编码 u f ” k 譬 f 咎 北京邮电大学博士学位论文a b s t r a c t r e s e a r c ho nn e t w o r kc o d i n gf o r h e t e r o g e n e o u sn e t w o r k s a b s t r a c t n e t w o r kc o d i n g ，w h i c hg e n e r a l i z e st r a d i t i o n a ls t o r e - a n d f o r w a r db y a ll o w i n gi n t e r m e d i a t en e t w o r kn o d e st o g e n e r a t e n e wp a c k e t s b y p e r f o r m i n ga l g e b r a i co p e r a t i o n s o n i n c o m i n gp a c k e t s ，h a ss h o w n a d v a n t a g e si nm a n ya r e a so fc o m m u n i c a t i o na n dn e t w o r k i n g f r o mt h e b e g i n n i n g ，m o s t e f f o r t sa r e p a i d o nt h er e s e a r c ho n s i n g l e r a t e t r a n s m i s s i o ns c h e m e sw i t hn e t w o r kc o d i n g h o w e v e r , n e t w o r k sa r e h e t e r o g e n e o u si ng e n e r a l s i n g l e r a t et r a n s m i s s i o nc o u l dn o tf u l l yu t i l i z e t h en e t w o r kb a n d w i d t hr e s o u r c et os e r v es i n kn o d e so fd i f f e r e n t c a p a c i t i e s t od e s i g ne f f i c i e n tt r a n s m i s s i o ns t r a t e g i e sb a s e do nn e t w o r k c o d i n g f o rh e t e r o g e n e o u sn e t w o r k si sam e a n i n g f u lb u tc h a l l e n g i n g s u b j e c t t h i sd i s s e r t a t i o nm a i n l yr e s e a r c h e sn e t w o r kc o d i n gt h e o r ya n d t e c h n o l o g yt or e a l i z ee f f i c i e n tm u l t i r a t et r a n s m i s s i o na n dv a r i a b l e - r a t e t r a n s m i s s i o ni nh e t e r o g e n e o u sn e t w o r k s t h ew o r ki nt h ed i s s e r t a t i o nc a nb es u m m a r i z e da sf o l l o w s ： i nm o s te x i s t i n gl a y e r e dm u l t i c a s ts c h e m e s ，t h er a t eo fe a c hl i n e a r m u l t i c a s ts e s s i o ni sg i v e n o n l yt h em u l t i c a s ts u b g r a p h sa r eo p t i m i z e d t h u s ，t h em a x i m a la g g r e g a t et h r o u g h p u ta c h i e v e di sa f f e c t e db yt h eg i v e n m u l t i c a s tr a t e s i nt h i sd i s s e r t a t i o n ，w er e s e a r c ht h el a y e r e dm u l t i c a s t s c h e m ew i t ho p t i m a l s e l e c t a b l em u l t i c a s tr a t e s w ed e d u c et h en e c e s s a r y c o n d i t i o nf o ro p t i m a lr a t e ss e l e c t i o n ，a n dp r o p o s ea no p t i m a l - r a t e - s e l e c t s c h e m ef o rl a y e r e dm u l t i c a s tt om a x i m i z et h ea g g r e g a t et h r o u g h p u t m o r e o v e r , t oa p p l yt h i ss c h e m ei nh i g h l yh e t e r o g e n e o u sn e t w o r k s ，w e p r o p o s e ag e n e t i ca l g o r i t h m ( g a ) b a s e dm e t h o dt os o l v eo u r o p t i m i z a t i o np r o b l e m s i m u l a t i o nr e s u l t s d e m o n s t r a t et h a tc o m b i n i n g w i t ht h i sg a - b a s e dm e t h o do u ro p t i m i z a t i o ns c h e m ec o u l ds e l e c tt h e o p t i m a lr a t e sf o rl a y e r e dm u l t i c a s te f f i c i e n t l y si n c et h el a y e r e dm u l t i c a s tb a s e do ni n t r a s e s s i o nn e t w o r kc o d i n gm u s t a c h i e v e si t so w nm a x f l o wv a l u e h o w e v e r , i tm a y h a p p e na tt h e s es i n k s t h a tt h ei n d e p e n d e n tn e t w o r kc o d e ds y m b o l sr e c e i v e da r ec o m p l e t e l y u n d e c o d a b l e f a c i n gt h i sp r o b l e m ，w ep r o p o s ean e wt y p eo fl i n e a r n e t w o r kc o d ei nt h i sd i s s e r t a t i o n - - t h es t r i c tl i n e a rn e t w o r kc o d e w b r e s e a r c ht h ec o n s t r u c t i o na l g o r i t h mf o rt h es t r i c tl i n e a rd i s p e r s i o n t h e t r a n s i t i o nr e l a t i o n s h i pf r o mt h eg e n e r a ll i n e a rd i s p e r s i o nt ot h es t r i c t l i n e a rd i s p e r s i o n ，a n dt h e a d v a n t a g e sp r e s e n t e db yt h e s t r i c tl i n e a r n e t w o r kc o d e sw h e na p p l i e di nh e t e r o g e n e o u sn e t w o r k s 。舱a l s op r o p o s e t h es t a t i cs t r i c tl i n e a rn e t w o r kc o d e sf o rn e t w o r k sw i t hl i n kf a i l u r e s m o r e o v e r , b a s e do ns t r i c tl i n e a rn e t w o r kc o d e so rs t a t i cs t r i c tl i n e a r n e t w o r kc o d e s ，w ep r o p o s eas p e c i a lk i n do fh i e r a r c h i c a lt r a n s m i s s i o n s c h e m e sf o rh e t e r o g e n e o u sn e t w o r k s ，w h i c hc a ns o l v et h eu n d e c o d a b l e i v j k 譬 、 ， 北京邮电大学博士学位论文 a b s t r a c t p r o b l e mi n h e r e n ti nt h eg e n e r a ll i n e a rn e t w o r kc o d e sa n di n d e e dr e a l i z e m u l t i - r a t et r a n s m i s s i o nw i t has i n g l en e t w o r kc o d es e s s i o n s p e c i a l l y , t h e s c h e m er e a l i z e dw i t hs t a t i cs t r i c tl i n e a rn e t w o r kc o d e si sa l s or o b u s tt ot h e l i n kf a i l u r e ss u f f e r e di nt h en e t w o r k m o s tw o r k si nn e t w o r kc o d i n gt od a t ef o c u s e do nt h ef i x e d r a t el i n e a r n e t w o r kc o d e s h o w e v e r , i np r a c t i c a ln e t w o r k s t h es o u r c em a yt r a n s m i t m e s s a g e sa td i f f e r e n tr a t e si nd i f f e r e n tp e r i o d sa c c o r d i n gt ot h ec o n t e n t a n dp r o p e r t i e so ft h eg e n e r a t e dd a t a h e n c e ，v a r i a b l e r a t el i n e a rn e t w o r k c o d e ss h o u l db ec o n s t r u c t e d w h i c hi sr e f e r r e dt oa st h e1 i n e a rn e t w o r k c o d e sc o n s t r u c t e do nac o m m o nn e t w o r kt h a tc a ns u p p o r tar a n g eo f p o s s i b l et r a n s m i s s i o nr a t e so ft h es o u r c e f e we f f o r t sh a v eb e e np a i do n t h i ss u b j e c t h o w e v e r , t h i sd i s s e r t a t i o ni n v e s t i g a t e st h eu n i f i e df r a m e w o r k a n de f f i c i e n tc o n s t r u c t i o ns c h e m e sf o rv a r i a b l e r a t el i n e a rn e t w o r kc o d e s w bp r o v et h ee x i s t e n c eo fe a c ht y p eo fv a r i a b l e r a t el i n e a rn e t w o r kc o d e s w h i c hh a v et h es a m el o c a le n c o d i n gk e r n e la te v e r yn o n s o u r c en o d e a n d p r o p o s ea ne f f i c i e n ts c h e m et or e a l i z ev a r i a b l e r a t el i n e a rn e t w o r kc o d e s w i t has i n g l ef i x e d r a t es t r i c tl i n e a rn e t w o r kc o d es e s s i o n t h u s e v e r y n o d ei nt h en e t w o r k ，i n c l u d i n gt h es o u r c en o d e ，n e e d st os t o r eo n l yo n e l o c a le n c o d i n gk e r n e lt os u p p o r tar a n g eo f p o s s i b l et r a n s m i s s i o nr a t e so f t h es o u r c e 0 u rc o n s t r u c t e dv a r i a b l e r a t el i n e a rn e t w o r kc o d e sc a na l s o r e a l i z em u l t i r a t et r a n s m i s s i o nu n d e re a c hp o s s i b l es o u r c er a t e i f c o m b i n e dw i t ht h e s p e c i a lp a c k e t i z a t i o ns t r a t e g yd e s i g n e d i nt h i s d i s s e r t a t i o n m o r e o v e r , w ep r o p o s et h ee f f i c i e n tc o n s t r u c t i o ns c h e m ef o r v a r i a b l e r a t es t a t i cl i n e a rn e t w o r kc o d e s i ft h i ss c h e m ei sa p p l i e d o n m a t t e rw h a tt h es o u r c er a t ei sa n dw h e r el i n kf a i l u r e sh a p p e n t h e o p e r a t i o np e r f o r m e do ne a c hn o d ei nt h en e t w o r kr e m a i n su n c h a n g e d 。 a tl a s t ，t h i sd i s s e r t a t i o ni n v e s t i g a t e st h ea p p l i c a t i o no fl i n e a rn e t w o r k c o d e si nt w os p e c i a lk i n d so fh e t e r o g e n e o u sn e t w o r k s ：p 2 ps t r e a m i n g n e t w o r k sa n dw i r e l e s ss e n s o rn e t w o r k s o no n eh a n d ，w ed e s i g nt h e s c h e m e st oa p p l yl a y e r e dr a n d o ml i n e a rn e t w o r kc o d ea n di n t e r - l a y e r h i e r a r c h i c a lr a n d o ml i n e a rn e t w o r kc o d ei np 2 ps t r e a m i n gn e t w o r kt o p r o v i d et h ep a r t i a ld e c i d a b i l i t yf o rl o w b a n d w i d t hp e e r st h e ng u a r a n t e e t h ec o n t i n u o u sd e c o d i n ga n ds m o o t hp l a y b a c k o nt h eo t h e rh a n d ，w e i n v e s t i g a t et h ep r o b l e mo fl i f e t i m em a x i m i z a t i o nf o rw i r e l e s ss e n s o r v oi 北京邮电大学博士学位论文a b s t r a c t n e t w o r k sw i t ht h ea s s i s t a n c eo fn e t w o r kc o d i n g w ep r o p o s ean e w h y p e r g r a p hm o d e lt h a ta c c o r d sw i t ht h eb r o a d c a s tn a t u r eo fw i r e l e s s s e n s o rn e t w o r k sa n dal i n e a rp r i c i n gm o d e lf o rt h eb r o a d c a s tl i n k s s i m u l a t i o n sd e m o n s t r a t et h a to u re n e r g ym e a s u r e m e n tm o d e li sm o r e p r e c i s et h a nt h ep o i n t - t o - p o i n to n e m o r e o v e r , n e t w o r kc o d i n gd o e sh a v e t h ee f f e c to f p r o l o n g i n gt h en e t w o r kl i f e t i m ei no u ro p t i m i z a t i o np r o b l e m k e yw o r d s ：l i n e a rn e t w o r k c o d e s ，h e t e r o g e n e o u sn e t w o r k s ， m u l t i r a t e ，v a r i a b l e - r a t e ，l a y e r e dc o d i n g 蠢 等 k 寸 北京邮电大学博士学位论文目录 目录 摘要i a b s t r a c t i i i 第一章绪论1 1 1 选题背景1 1 2 网络编码的研究现状2 1 3 本文的主要研究内容及组织结构4 1 3 1 研究内容4 1 3 2 组织结构6 第二章线性网络编码的基本理论8 2 1 网络模型8 2 2 线性网络编码的基本理论8 2 2 1 线性网络编码的定义8 2 2 2 线性网络编码的构造1 0 2 3 静态线件网络编码的基本理论”1 2 2 3 1 静态线性网络编码的定义1 2 2 3 2 静态线性网络编码的构造1 4 第三章速率可调的分层组播网络编码”1 6 3 1 分层组播网络编码1 6 3 2 速率可调的分层组播优化问题1 8 3 2 1 网络模型1 8 3 2 2 问题描述1 9 3 3 一利分层组播速率的优化选择方案2 0 3 4 基于遗传算法的求解方案”2 4 3 4 1 实现过程2 5 3 4 2 复杂度分析2 8 3 5 仿真实验“2 8 3 5 1 本章优化问题的性能分析2 8 3 5 2 基于遗传算法的优化问题求解方案的性能分析2 9 3 6 本章小结”31 第四章基于层间网络编码的等级组播“3 3 4 1 组播间线性网络编码的研究现状3 3 4 2 层间等级随机线性网络编码一3 4 4 3 层间等级组播一3 4 4 3 1 网络模型及符号表示3 5 4 3 2 层间等级组播的实现3 5 4 4 层间等级组播巾i h r l n c 类型的优化选择3 6 4 5 确定最优编码类型的启发式算法3 8 v i i 北京邮电大学博士学位论文目录 4 6 层间等级组播与分层组播的比较3 9 4 7 仿真实验及性能分析一4 0 4 8 本章小结4 4 第五章基于线性广播网络编码的分层数据传输4 5 5 1 一种特殊的信源数据打包方案一4 5 5 2 基于随机网络编码的数据包传输4 7 5 3 成功概率分析4 8 5 4 本章小结5 2 第六章严格线性网络编码5 4 6 1 严格线性网络编码的定义5 4 6 2 严格线性网络编码的构造5 5 6 3 线性网络编码与严格线性网络编码的转换关系5 8 6 4 基于严格线性广播的多速率信息传输6 4 6 5 严格线性散播在可扩展的异构网络上的应用优势6 6 6 6 静态严格线性网络编码”6 9 6 6 1 静态严格线性网络编码的定义6 9 6 6 2 静态严格线性网络编码的构造7 1 6 6 3 基于静态严格线性广播的鲁棒性多速率信息传输7 3 6 7 本章小结”7 7 第七章变速率线性网络编码的构建7 9 7 1 线性网络编码及静态线性网络编码的统一定义8 0 7 2 变速率线性网络编码的统一框架8 l 7 3 基于严格线性网络编码的变速率线性网络编码的构建8 7 7 4 变速率静态线件网络编码的统一框架”9 l 7 5 基于静态严格线性网络编码的变速率静态线性网络编码的构建9 4 7 6 本章小结9 7 第八章线性网络编码在特殊异构网络中的应用9 9 8 1 分层网络编码与层间等级网络编码在p 2 p 实时流媒体传输网络中的应用9 9 8 1 1 随机网络编码在p 2 p 网络中的应用1 0 0 8 1 2 分层随机网络编码在p 2 p 网络巾的应用1 0 1 8 1 3 层间等级随机网络编码在p 2 p 网络中的应用1 0 2 8 1 4 仿真实验10 4 8 2 基于线性网络编码的无线传感器网络生存时间最大化”1 0 7 8 2 1 一利- 基于超图的网络模型“10 8 8 2 2 基于超弧的线性加权能耗测量模型1 0 9 8 2 3 最大无冲突了图一1 1 0 8 2 4 优化问题的数学表述ll l 8 2 5 仿真实验l l3 8 3 本章小结l l5 第九章总结与展望1 1 7 t - ， 旷 北京邮电大学博士学位论文目录 9 1 本文研究工作总结11 7 9 2 未来工作展望1 19 参考文献1 2 1 致谢13 0 攻读博士学位期间发表的学术论文1 3 l i x ， ， _ 邮电大学博士学位论文目录 x i 簟 。， _ 北京邮电大学博士学位论文第一章绪论 1 1 选题背景 第一章绪论 随着计算机网络与通信技术的不断发展，通信网络与人们工作和生活的联系 越来越紧密，人们对网络服务的多样化和服务质量提出了越来越高的要求。在现 有的网络条件下，如何更有效地利用网络资源实现更高质量的数据传输已成为通 信领域中最重要的研究课题之一。 组播( m u l t i c a s t ) 是一种单信源节点同时向多个信宿发送信息的有效的信息传 输方式，被广泛应用于多媒体会议、远程教育以及数据分发等领域。然而，仅允 许节点进行存储转发( s t o r i n ga n df o r w a r d i n g ) 操作的组播通信无法确保信息传输 速率达到最大流最小割定理( m i n c u tm a x f l o wt h e o r e m ) l 】所确定的信源和信宿 间的最大流量。 2 0 0 0 年，a h l s w e d e 掣2 j 首次提出了网络编码理论( n e t w o r kc o d i n g ，n c ) 。其 核心思想是网络节点可以对从多条输入链路上接收到的数据进行一定的线性或 非线性处理( 编码) ，然后再发送出去，节点起着编码器或信号处理器的作用。 a h l s w e d e 等严格证明了在单信源多信宿的通信网络中，基于网络编码的组播能 够实现网络组播速率的理论上限。这一结论推翻了在网络中间节点上对传输数据 进行加工处理不会带来任何收益这一传统观点。 网络编码彻底改变了通信网络中信息处理和信息传输的方式，被认为是进入 2 l 世纪后信息处理和信息传输研究领域中最重要的理论成果之一。与传统的基 于存储和转发的路由传输机制相比，网络编码能显著改善网络性能，如提升网络 吞吐量、节约传输带宽和均衡网络负载等。此外，网络编码在提高网络通信的鲁 棒性、普适性、安全性等方面也具有很大优势。 现有的网络编码研究工作多是建立在单速率组播的基础上的，即信源以相同 的速率发送数据到所有信宿。然而，异构性是i n t e r n e t 网络的固有特性，网络各 部分资源的不均匀以及端系统处理能力的差异是这种异构性存在的根源，并且随 着越来越多不同利，类的网络接入i n t e r n e t ，i n t e m e t 的规模不断扩大，异构性问题 将更加突出。在这一前提下，若按照组播传统意义上的单速率机制的做法，则发 送速率由接收带宽最低的信宿决定。这会使得网络中的所有信宿无论接收能力如 何都要受瓶颈信宿速率的影响，显然带来了接收者之间的严重的不公平性问题。 因此，如何基于网络编码设计高效的信息传输方案、如何适应信宿的异构性， 使他们获得与其实际接收能力和需求相匹配的接收质量，以保证网络资源的充分 活跃情况。 概括起来，近年来网络编码的研究成果主要体现在以下几个方面： 1 网络编码基础理论的研究。 主要研究网络编码的数学模型，并从理论上探讨网络编码对于网络性能的改 善。2 0 0 3 年，l i 等【3 j 考虑到线性编码的简单性和实用性，提出了线性网络编码 ( l i n e a r n e t w o r kc o d i n g ，l n c ) ，并证明了线性网络编码能够在单信源网络中达到 组播速率的理论上限。此工作为网络编码的实际应用奠定了基础。网络编码还衍 生出了一些新理论的研究，如网络卷积编码【4 9 】，多信源网络编码【1 仉1 5 1 等。这些 研究成果为进一步发展和应用网络编码提供了理论支撑。 2 网络编码的构造算法 网络编码的构造算法是在实际网络巾部署和应用网络编码的基础。目前，研 究主要集中于线性网络编码的构造。算法主要分为确定性构造算法和随机构造算 法两大类。2 0 0 2 年，k o e a e r 等i l6 j 将有限域上的多项式法用到网络编码的研究 中，提出了基于代数结构的线性网络编码构造算法。这利算法是一种指数时间算 法，其算法复杂度较大。2 0 0 3 年，s a n d e r s 等和j a g g i 等同时提出了一种线 性网络编码的多项式时间构造算法。与第一种算法相比，此算法复杂度大大降低。 随后，h o 等1 2 0 ，2 1j 提出了随机网络编码，拓展了网络编码的应用场景，使其不再 局限于确定的网络拓扑结构和集中式的构造算法。 2 北京邮电大学博士学位论文 第一章绪论 3 网络编码的优化部署 在保证网络编码提升网络性能的前提下，降低网络运行成本和代价，对于在 实际网络中部署和应用网络编码具有重要意义。许多学者对此展开了研究【2 2 铷】。 l u i l 等1 23 j 提出了在组播网络中建立最小费用组播网络编码的问题，并将其作为一 个线性规划问题来研究。l e e 等1 2 4 】研究了为分布式信源网络联合编码实现最小 费用的编码子图划分问题。k i m 等【2 5 , 2 6 基于遗传算法研究如何实现最小费用网络 编码的问题。此外，网络编码提出的初衷是为了实现较基于存储与转发的路由机 制更好的数据传输性能，但由于节点执行编码操作需要消耗额外的计算资源，因 此学者们也关注于如何在保证网络传输性能的前提下，最小化网络中执行网络编 码操作的节点数或次数2 7 圆】。k i m 等川还研究了如何在网络运行成本最小与编 码代价最小之间进行折衷。 4 网络纠错编码和网络安全编码 c a i 和y e u n 9 1 3 1 d 2 j 提出了基于网络编码的网络纠错编码的概念，用以纠正篡 改和调换数据包所造成的错误。在此基础上，他们把纠错编码理论中的重要结果， 如h a m m i n g 界，s i n g l e t o n 界等，推广到网络纠错编码的研究中，构造了最优的 网络纠错编码。此后，z h a n g 等【3 孓3 6 l 研究了网络纠错编码的译码算法。利用网络 纠错编码，当信息在网络中传播时，若某一时刻有几条链路上传输的符号发生错 误，只要错误数没有超出纠错范围，终端接收节点通过恰当的译码可恢复出正确 的信息，而不需要信息重传。 在研究网络纠错编码理论的同时，学者们也开始关注有关网络编码的安全问 题【3 7 m 】。c a i 和y e u n g 3 7 1 提出了以反窃取传输信息为目标的网络安全编码。他们 提出了窃听网络上的通信系统模型，为单信源网络构造了反窃听的网络安伞编 码。其后，c a 和y e u n g 3 8 l 还将他们的工作推广到多信源网络，发现了一般窃听 网络上通信系统安全编码的充分必要条件，为这类网络安全编码走向应用奠定了 基础。此外，学者们还研究了存在拜占庭敌手的网络安伞编码问题【4 3 , 4 4 】，以及基 于网络编码的签名算法【4 5 , 4 6 】。 5 网络编码理论在实际网络上的应用 2 0 0 3 年，c h o u 等1 47 j 考虑了网络编码在实际应用巾的问题，设计了适用于实 际网络的网络编码信息传输方案。自此，研究者们广泛展开了将网络编码理论应 用于各类实际网络的研究。 p 2 p ( p e e r - t o p e e r ) 是在i n t e m e t 环境下新兴的一种内容分发模型。内容分发协 议一直是p 2 p 应用系统的研究热点。近年来，研究者们基于网络编码设计p 2 p 内 容分发协议，获得了节省带宽资源、提高系统抗毁性和可扩展性等优势1 4 8 5 们。 a v a l a n c h e 算法1 48 】表明，若在大规模内容分发网络中利用网络编码，则其获得的 网上传输率要比不利用网络编码时提高2 0 3 0 。此外，网络编码还能提高系统 北京邮电大学博士学位论文第一章绪论 的鲁棒性，有效解决“稀少块”的问题。w a n g 等1 5 0 j 通过实验证明了在p 2 p 实时 流媒体传输网络中应用网络编码具有明显优势。 无线网络的物理层广播特性和业务流的双向性非常适合使用网络编码。网络 编码在无线网络中的研究热点主要集中于物理层网络编码【5 卜5 3 j 、基于网络编码的 协作方案设计5 4 , 5 5 】、跨层优化【5 6 5 引、以及无线网络中应用网络编码的协议【5 9 , 6 0 】 等。此外，将网络编码应用于无线自组织网络( w i r e l e s sa d