（信号与信息处理专业论文）网络编码算法与协议设计.pdf

i j0a口，。，i r e s e a r c ho na l g o 砒t h m sa n d p r o t o c o l so fn e t w o r kc o d i n g b ys o n g y am a s u p e r v i s o r ：p r o f z h e n g m i n gh u ad i s s e r ，r i o n p r e s e n t e dt ot h ef i a c u i t yo f b e l j i n gu n i v e r s i t yo fp o s t s t e l e c o m m u n i c a n o n s i nc a n d i d a c yf o r t h ed e g r e e o fd o c t o r0 f p h i l o s o p h y r e c o m m e n d e df o ra c c e p t a n c eb y s c h o o lo fc o m p u t e r 独创性( 或创新性) 声明 本人声明所呈交的论文是本人在导师指导下进行的研究工作及取得的研究 成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中 不包含其他人已经发表或撰写过的研究成果，也不包含为获得北京邮电大学或 其他教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所 做的任何贡献均已在论文中作了明确的说明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切相关责任。 本人签名：当翌圭缅蔓f t 期：丝! ! ：盟。 关于论文使用授权的说明 学位论文作者完全了解北京邮电大学有关保留和使用学位论文的规定，即： 研究生在校攻读学位期间论文工作的知识产权单位属北京邮电大学。学校有权 保留并向国家有关部门或机构送交论文的复印件和磁盘，允许学位论文被查阅 和借阅；学校可以公布学位论文的全部或部分内容，可以允许采用影印、缩印 或其它复制手段保存、汇编学位论文。( 保密的学位论文在解密后遵守此规定) 保密论文注释：本学位论文属于保密在一年解密后适用本授权书。非保密 论文注释：本学位论文不属于保密范围，适用本授权书。 本人签名：鱼堑生塑坠 导师张础接导师签名：丝垒鲻盥 同期：竺! 竺：! ：! 三 日期：印坠望 北京邮电大学博士学位论文摘要 网络编码算法与协议设计 摘要 网络编码是近年来通信领域的一项重大突破。网络编码的思想建立 在网络信息流的基础之上，通过允许网络节点对来自不同链路的信息进 行编码组合，使其既能实现传统路由的存储转发功能，又能实现对信息 的处理，这样可以大幅度提高网络性能。网络编码的初衷是为使多播传 输达到理论上的最大传输容量，从而取得较路由更好的网络吞吐量。随 着研究的深入，网络编码的研究已拓广到无线网络、p 2 p 内容分发、分布 式存储、网络安全等多个应用领域。固定速率网络编码的性质已经得到 广泛的研究，在流量动态变化的真实网络中，具有可变速率的网络编码 技术具有重要的研究意义。 量子通信是量子信息的核心内容之一，它为信息的安全传输提供了 新的方法。量子通信无论是在理论上还是实验上都取得了大量的研究成 果，有广阔的发展和应用前景。量子通信网络是当前国际上热门的研究 课题之一。当量子通信的整体网络已经实现，将网络编码理论应用到量 子通信领域以提高量子网络的整体性能有重要的研究意义。但是，相对 于经典网络编码而言，量子网络编码的研究才刚刚起步。蝶形网络虽然 简单，却代表了有瓶颈信道的网络的性质，它的解决方案可以触发对一 般网络解决方案的研究。此外，量子克隆作为量子网络编码技术的重要 组成要素，将对量子网络编码的研究起到很大的推动作用。 本论文对网络编码算法与协议设计进行了研究。内容涉及经典网络 编码和量子网络编码。具体包括三个方面：变速率线性网络编码算法的 设计，蝶形网络上量子网络编码协议的设计，量子辅助克隆协议的设计。 论文对研究过程中取得的成果进行了详细阐述，其中主要创新工作简要 归纳如下： 1 针对单信源无圈的经典通信网络，分别研究了四类变速率的线性 网络编码。一方面，通过简单清晰的证明，得到如果编码基域足够大， 变速率的线性g e n e r i c 、散布、广播可以在不改变非源节点局部编码核的 北京邮电大学博士学位论文摘要 情况下有效实现。同时，给出了同一个网络中不同维数的线性g e n e r i c 、 散布、广播的有效实现算法。这些算法的优点是在整个会话过程中每个 非源节点只需要存储一个局部编码核，从而大大节省了存储空间，有利 于硬件上的实现。另一方面，通过例子说明变速率线性多播在上述条件 下未必能够实现。将这种研究方法应用到有链路失败情形，可以得到变 速率静态网络编码的类似结论。 针对单信源有圈的经典通信网络，分别研究了四类变速率的卷积网 络编码。得到变速率的卷积g e n e r i c 、散布、广播可以在不改变非源节点 局部编码核的情况下有效实现，而变速率卷积多播在上述条件下未必能 够实现。 2 经典网络编码能有效节省带宽，针对有瓶颈信道的量子通信网 络，有效地利用量子网络资源同样具有重要的研究意义。利用量子特有 的纠缠资源，设计了一个有效的需求传输协议，以实现在蝶形网络上交 叉传送两个两级量子态。详细地讲，当仅两个发送方之间共享两个非最 大纠缠的量子比特对，在本文提出的协议下，两个接收方都能以一定概 率保真度为1 地重建初始态，并且在瓶颈信道上节省了1 经典比特的通 信：这意味着我们的协议比没有使用网络编码的协议更有效。此外，这 个协议被推广到传输两个多方纠缠态的情形。 3 研究在不增加量子非局域资源的情形下，以高概率实现未知态完 美复制的辅助克隆方案。设计了新的协议来实现未知两粒子纠缠态的辅 助克隆。协议包含两个步骤：第一步需要通常的隐形传态；第二步，构 造一组新的相互正交的基向量。在制备方的帮助下，基于这组基执行投 影测量，可以产生初始态的完美复制。与以前的协议相比，它们在发送 方处产生未知态和它的正交补态，本文提出的协议确定性地产生未知态 本身。另一方面，设计了另一个经由非最大纠缠态作为量子信道的辅助 克隆协议。仅未知态的完美复制以一定概率产生。 使用类似的研究方法，分别设计了粒子纠缠态的确定性辅助克隆 协议和三粒子g h z 类态以1 2 成功概率实现完美复制的辅助克隆协议。 关键词：变速率线性网络编码量子网络编码量子克隆 i i 北京邮电大学博士学位论文 r e s e a r c h o na l g o r i t h m sa n dp r o t o c o l s o fn e t w o r kc o d i n g a b s t r a c t n e t w o r k c o d i n g i so n eo ft h em o s t i m p o r t a n tb r e a k t h r o u g h s i n c o m m u n i c a t i o nf i e l d sr e c e n t l y t h em a i ni d e ao fn e t w o r kc o d i n gi st h a ti n c o m m u n i c a t i o nn e t w o r k s ，i n t e r m e d i a t en o d e sa r ea l l o w e dt on o t o n l y s t o r e - f o r w a r db u ta l s op r o c e s st h ei n c o m i n gi n d e p e n d e n ti n f o r m a t i o nf l o w s n e t w o r kc o d i n gh a sb e e np r o v e da sa n e l e g a n ta n dn o v e lt e c h n i q u et o i m p r o v en e t w o r kp e r f o r m a n c e n e t w o r kc o d i n gi sf i r s tp r o p o s e dt oe n a b l e m u l t i c a s tt r a n s m i s s i o nt oa b t a i nt h et h e o r e t i c a lm a x i m u mt r a n s m i s s i o n c a p a c i t y , s oa st oa c h i e v eb e t t e rn e t w o r kt h r o u g h p u tt h a nc o n v e n t i o n a lr o u t i n g w i t hf u r t h e rd e v e l o p i n g ，n e t w o r kc o d i n gh a sb e e ne x p a n d e dt ow i r e l e s s n e t w o r k ，p 2 pc o n t e n td i s t r i b u t i o n ，d i s t r i b u t e ds t o r a g e ，n e t w o r ks e c u r i t y ，a n d o t h e ra p p l i c a t i o n s t h e r eh a sb e e nm u c hi n v e s t i g a t i o ni n t ov a r i o u sp r o p e r t i e s o fn e t w o r kc o d i n gw i t haf i x e dr a t e n e t w o r kc o d i n gw i t hv a r i a b l e r a t e t e c h n o l o g yh a si m p o r t a n tr e s e a r c hs i g n i f i c a n c es i n c ei n f o r m a t i o nf l o w sa r e d y n a m i ci nt h er e a ln e t w o r k q u a n t u mc o m m u n i c a t i o np r o v i d e san e ww a yf o rt r a n s m i t t i n gm e s s a g e s e c u r e l na n di so n eo ft h ei m p o r t a n tp a r t si nq u a n t u mi n f o r m a t i o n q u a n t u m c o m m u n i c a t i o nh a sm a d eag r e a td e a lo fa c h i e v e m e n t sb o t hi nt h e o r ya n d e x p e r i m e n t sa n dh a sb r o a dp r o s p e c t sf o rd e v e l o p m e n ta n da p p l i c a t i o n c u r r e n t l y , q u a n t u mc o m m u n i c a t i o nn e t w o r ki so n eo fh o tr e s e a r c ht o p i c si n t h ei n t e r n a t i o n a lc o m m u n i t y t h e r e f o r e ，i m p r o v i n gt h eo v e r a l lp e r f o r m a n c ei s e s s e n t i a lw h e naq u a n t u mc o m m u n i c a t i o nn e t w o r kb e c o m e sr e l i z e d h o w e v e r , t h er e s e a r c h o fq u a n t u mn e t w o r kc o d i n gh a sj u s t b e g u n a l t h o u g ht h e b u t t e r f l yn e t w o r ki so n l yas p e c i f i ce x a m p l eo fn e t w o r kc o d i n g ，i tr e p r e s e n t s t h ep r o p e r t i e so fn e t w o r k sw i t hb o t t l e n e c k s ，s ot h a ti t ss o l u t i o ng i v e sat r i g g e r f o ram o r eg e n e r a ls o l u t i o n i na d d i t i o n ，q u a n t u mc l o n i n g ，a sa ni m p o r t a n t i i i 北京邮电大学博士学位论文 e l e m e n to fq u a n t u mn e t w o r kc o d i n gt e c h n o l o g y , p l a y sa g r e a tr o l e i n p r o m o t i n gt h er e s e a r c ho nq u a n t u m n e t w o r kc o d i n g t h ed i s s e r t a t i o nm a i n l yf o c u s e so nt h ea l g o r i t h m sa n dp r o t o c o l so f n e t w o kc o d i n g t h ec o n t e n to ft h i sd i s s e r t a t i o nr e l a t e st oc l a s s i c a la n d q u a n t u mn e t w o r kc o d i n g ，s p e c i f i c a l l yi n c l u d i n gt h r e ea s p e c t s ：a l g o r i t h m sf o r v a r i a b l e - r a t el i n e a rn e t w o r kc o d i n g ，p r o t o c o l so fq u a n t u mn e t w o r kc o d i n g o v e rt h eb u t t e r f l yn e t w o r k ，a n dp r o t o c o l sf o rc l o n i n ga nu n k n o w nq u a n t u m s t a t ew i t ha s s i s t a n c e t h ep r i n c i p a lc o n t r i b u t i o n so ft h ew o r kp r e s e n t e di nt h ep a p e ra r e ： 1 o v e ras i n g l e s o u r c ea c y c l i cc l a s s i c a lc o m m u n i c a t i o nn e t w o r k ，f o u r t y p e so 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 sa r ei n v e s t i g a t e d o nt h eo n eh a n d ， b ys i m p l ea n dc l e a rp r o o f s ，i ti sf o u n dt h a tv a r i a b l e r a t eg e n e r i c ，d i s p e r s i o n a n db r o a d c a s tc a nb ei m p l e m e n t e dw i t h o u tc h a n g i n gt h el o c a le n c o d i n g k e r n e l so ft h en o n s o u r c en o d e si ft h ef i e l di sl a r g ee n o u g h a tt h es a m et i m e i t s u p p l i e s e f f i c i e n t a l g o r i t h m s f o rv a r i a b l e r a t eg e n e r i c ，d i s p e r s i o na n d b r o a d c a s to nt h es a m en e t w o r k t h e s es c h e m e sh a v et h ea d v a n t a g et h a te a c h n o n s o u r c en o d ei s r e q u i r e dt os t o r eo n l yo n ec o p yo ft h el o c a le n c o d i n g k e r n e lw i t h i nas e s s i o n o nt h eo t h e rh a n d ，i ti ss h o w nb ya ne x a m p l et h a t v a r i a b l e r a t em u l t i c a s tm a yn o ta l w a y sb ei m p l e m e n t e du n d e rt h ea b o v e c o n d i t i o n m o r e o v e r , a p p l y i n gt h i sa p p r o a c ht oan e t w o r kw i t hl i n kf a i l u r e ， o n e c a no b t a i ns i m i l a rr e s u l t sf o rv a r i a b l e - r a t es t a t i cn e t w o r kc o d i n g o v e ras i n g l e - s o u r c ec y c l i cc l a s s i c a lc o m m u n i c a t i o nn e t w o r k ，f o u r t y p e so fv a r i a b l e r a t e c o n v o l u t i o n a ln e t w o r kc o d e sa r ei n v e s t i g a t e d i ti s f o u n dt h a tv a r i a b l e r a t ec o n v o l u t i o n a lg e n e r i c ，d i s p e r s i o na n db r o a d c a s tc a n b e i m p l e m e n t e dw i t h o u tc h a n g i n g t h el o c a le n c o d i n gk e r n e l so ft h e n o n s o u r c en o d e s h o w e v e r , i ti sa l s os h o w nt h a tv a r i a b l e r a t ec o n v o l u t i o n a l m u l t i c a s tm a yn o ta l w a y sb ei m p l e m e n t e du n d e rt h ea b o v ec o n d i t i o n 2 c l a s s i c a ln e t w o r kc o d i n gc a ns a v eb a n d w i d t h f o raq u a n t u m c o m m u n i c a t i o nn e t w o r kw i t hb o t t l e n e c kc h a n n e l s ，e f f i c i e n tu s eo fq u a n t u m n e t w o r kr e s o u r c e si sa l s oe s s e n t i a l o n ep r o t o c o li sp r o p o s e dt ot r a n m i tt w o 2 一l e v e l q u a n t u m s t a t e s c r o s s l y o v e rt h e b u t t e r f l y n e t w o r kw i t ht w o i v 北京邮电大学博士学位论文 n o n - m a x i m a l l ye n t a n g l e dq u b i tp a i r ss h a r e do n l yb e t w e e nt w os e n d e r s i ti s s h o w nt h a tb o t ho ft h er e c e i v e r sc a nr e e s t a b l i s ht h ei n i t i a ls t a t e sw i t hu n i t f i d e l i t ya n dap r o b a b i l i t yl e s st h a no n e a n do n ec l a s s i c a lb i tc o m m u n i c a t i o n c a nb es a v e da tt h eb o t t l e n e c kc h a n n e l i tm e a n st h a tt h ep r o p o s e dp r o t o c o li s m o r ee f f i c i e n tt h a ni t sw i t h o u tn e t w o r kc o d i n g m o r e o v e r , t h i sp r o t o c o li s g e n e r a l i z e d t ot h ec a s eo ft r a n s m i t t i n gt w om u l t i p a r t i t ee n t a n g l e ds t a t e s 3 a s s i s t e d c l o n es c h e m e sa r ei n v e s t i g a t e dt op r o d u c et h ep e r f e c tc o p y o fa nu n k n o w ns t a t ew i t hah i g hp r o b a b i l i t yw i t h o u ti n c r e a s i n gt h eq u a n t u m n o n - l o c a lr e s o u r c e s an o v e lp r o c o t o li s p r o p o s e dt oc l o n e a nu n k n o w n t w o - p a r t i c l ee n t a n g l e ds t a t e n ef i r s ts t a g eo ft h ep r o t o c o lr e q u i r e su s u a l t e l e p o r t a t i o n i nt h es e c o n ds t a g eo ft h ep r o t o c o l ，an o v e ls e to fm u t u a l l y o r t h o g o n a lb a s i sv e c t o r si sc o n s t r u c t e d w i t ht h ea s s i s t a n c eo ft h ep r e p a r e r t h r o u g hap r o j e c t i v em e a s u r e m e n tu n d e rt h i sb a s i s ，t h ep e r f e c tc o p yo fa n o r i g i n a ls t a t ec a nb ep r o d u c e d c o m p a r i n gw i t ht h ep r e v i o u sp r o t o c o l sw h i c h p r o d u c et h eu n k n o w ns t a t ea n di t so r t h o g o n a lc o m p l e m e n ta t t h es i t eo ft h e s e n d e r , t h ep r o p o s e dp r o t o c o lg e n e r a t e st h eu n k n o w ns t a t ed e t e r m i n i s t i c a l l y o nt h eo t h e rh a n d ，a n o t h e rp r o t o c o li sa l s op u tf o r w o r dv i an o n m a x i m a l e n t a n g l e m e n ta st h eq u a n t u m c h a n n e l t h ef a i t h f u lc o p yo fa nu n k n o w ns t a t e c a nb eo b t a i n e dw i t hac e r t a i np r o b a b i l i t y 一 u s i n gt h es i m i l a rm e t h o d ，w ep r o p o s ea nd e t e r m i n i s t i ca s s i s t e d c l o n e p r o t o c o lf o ra nn - p a r t i c l ee n t a n g l e ds t a t ea n da na s s i s t e d c l o n ep r o t o c o lf o ra t h r e e p a r t i c l e g h zc l a s s s t a t ew i t ht h es u c c e s s f u l p r o b a b i l i t y 1 2 ， r e s p e c t i v e l y k e yw o r d s ：v a r i a b l e r a t el i n e a rn e t w o r kc o d i n g q u a n t u mn e t w o r k c o d i n gq u a n t u mc l o n e v 北京邮电大学博士学位论文目录 第一章 1 1 1 2 1 3 第二章 2 1 2 2 2 3 2 4 2 5 第三章 3 1 3 2 3 3 3 4 第四章 4 1 4 2 4 3 4 4 目录 绪论；1 研究意义1 研究现状3 论文安排及主要研究成果7 网络编码概述9 端对端的网络通信模型及最大流最小割定理9 网络编码的基本原理1 0 单信源线性网络编码一无圈网络。1 2 2 3 1 线性网络编码1 2 2 3 2 达到最大流界的线性网络编码1 3 2 3 3 静态网络编码1 4 单信源线性网络编码一有圈网络1 6 本章小结1 8 变速率线性网络编码算法的设计1 9 引言1 9 无圈网络中变速率线性网络编码的统一结论2 0 3 2 1 线性网络编码的统一框架2 0 3 2 2 有效实现算法2 1 3 2 3 应用举例2 6 3 2 4 变速率静态网络编码2 7 有圈网络中变速率卷积网络编码的统一结论2 8 3 3 1 预备知识2 8 3 3 2 有效实现算法3 0 3 3 3 应用举例3 5 本章小结3 7 蝶形网络上量子网络编码协议的设计3 8 引言3 8 量子信息理论4 0 4 2 1 量子态4 0 4 2 2 演化4 1 4 2 3 ；9 1 0 量4 2 4 2 4 量子纠缠4 4 4 2 5 量子隐形传态4 4 蝶形网络上x q q 量子网络编码协议。4 7 蝶形网络上m - q u d i t 量子态的概率性量子网络编码5 0 4 4 12 级量子态的传输协议。5 0 北京邮电大学博士学位论文 目录 4 4 2m - q u d i t 量子态的传输协议5 2 4 4 3 讨论。5 5 4 5 本章小结5 6 第五章 5 1 5 2 5 3 5 4 5 5 量子辅助克隆协议的设计：5 7 引言5 7 未知两粒子纠缠态的忠实辅助克隆5 8 5 2 1 经由最大纠缠态的确定性辅助克隆协议5 9 5 2 2 经由非最大纠缠态的辅助克隆协议6 1 5 2 3 小结。6 3 未知粒子纠缠态的确定性辅助克隆“ 5 3 1 未知三方纠缠态的确定性辅助克隆协议6 5 5 3 2 未知量子比特纠缠态的确定性辅助克隆协议6 8 5 3 3 讨论7 0 未知三粒子g h z 类态的辅助克隆7 1 5 4 1 未知三量子比特纠缠态的辅助克隆协议7 2 5 4 2 讨论7 5 本章小结7 6 第六章总结与展望7 7 6 1 本论文研究工作的总结7 7 6 2 研究工作的展望7 8 参考文献7 9 致谢8 8 攻读博士学位期间的成果8 9 攻读博士学位期间参与的科研项目9 1 北京邮电大学博士学位论文第一章绪论 1 1 研究意义 第一章绪论 随着信息时代的不断发展，各种通信网络与人们工作生活的各个方面结合越来越 紧密。与此同时，由于用户数量的激增，网络服务的多样化以及对网络传输质量的要 求也不断提高，如何提高现有网络资源的利用率，优化网络，己成为当今网络通信研 究的重要课题之一。 香农在1 9 5 6 年的论文an o t eo nt h em a x i m u mf l o wt h r o u g han e t w o r k ) ) 中指出： “通信网络端对端的最大信息流，是由网络有向图的最d , 害- u 决定”。传统的通信网络传 送数据的方式是存储转发，即中间节点扮演着转发器的角色，只负责路由而不对数据 做任何处理。但目前传统路由器的存储转发模式难以达到香农最大流最小割定理规定 的理论上限。2 0 0 0 年，a h l s w e d e 等基于网络信息流的概念，首次提出了网络编码 ( n e t w o r kc o d i n g ) 的思想【1 1 ，即允许网络节点对来自不同链路的信息进行编码组合，使 其既能实现存储一转发功能又能实现对信息的处理，这样可以提高传输效率从而达到 网络多播的最大流传输的理论上限。 网络编码彻底改变了通信网络中信息处理和传输的方式，推翻了在中间节点对传 输的数据进行加工不会有任何收益的传统观念，是信息理论研究领域的重大突破。继 网络编码的概念【1 】提出之后，出现了一批重要的研究成果，它们为网络编码的发展奠 定了坚实的理论基础。为了使网络编码理论进入实际应用，必须解决其软件和硬件的 复杂性问题，为此，李硕彦，杨伟豪，蔡宁共同发表了另一篇著名论文“l i n e a rn e t w o r k c o d i n g ”f 2 】，该文证明了在单信源多信宿的情况下，通过线性网络编码就可以达到网 络多播的最大流限。由于该论文的杰出贡献，它获得了2 0 0 5 年i e e e 电机及电子工 程师学会信息理论学会的最佳论文奖，这是三十余年来亚洲国家首次获得此奖。随后 m i t 的m 6 d a r d 教授等阐明了网络编码的代数框架，并证明了存在满足多播容量的线 性时不变编码，为网络编码这一新技术建立了严密的理论基础【3 j 。j a g g i 等给出了构 造线性网络多播的多项式时间算法【4 j ；h o 等提出了随机网络编码，并证明了通过随 机线性网络编码能以极大概率达到网络多播的最大流限1 5 ，6 j 。随机网络编码的提出拓 宽了网络编码的适用范围，使得网络编码不再局限于确定的网络拓扑和集中式的算 北京邮电大学博士学位论文第一章绪论 法。c a i 等利用分布式网络编码来纠正整个网络中的差错【7 1 ，并论述了网络编码在安 全方面的应用【8 j ，为网络编码增加了新的应用领域。 一方面，网络编码代表了一种协同工作的理念，这使得它的应用不仅局限于增加 多播的网络容量，而且，网络编码与其它技术相结合还可以从多种角度对网络进行优 化，例如降低能耗、网络管理、交叉层设计，纠错【9 - 1 1 j ，信息安全【1 2 】等。另一方面， 为了发挥网络编码的应用价值，如何降低相关运算复杂度，提高鲁棒性，并达到分布 式实现等课题都吸引了众多的研究者。与之相应的更为合理有效的容量和复杂性分析 方法也在不断改进之中。 网络编码是理论和应用价值都很大的国际热点课题。国外多所著名大学，如普林 斯顿大学、麻省理工大学、瑞士e p f l 学院等以及多家i t 研究机构，包括微软研究院、 贝尔实验室、a t & t 的香农信息实验室等都在积极开展对网络编码理论和应用的研究； 网络编码也逐渐引起了国内学术界的关注和重视，我国有多所大学已经对网络编码进 行了探索。国家自然基金已经资助了多项网络编码项目，国家“8 6 3 项目也以灵活 的形式实现了网络编码项目零的突破。到目前为止，网络编码的相关研究成果，主要 发表在诸如i e e et r a n s i n f o r m t h e o r y 、l e e e a c mt r a n s n e t w o r k i n g 等国际著名学术 刊物和诸如i s i t 、i n f o c o m 等信息论和网络理论界的国际顶级学术会议上。相关成 果呈现出逐年增多的趋势。 量子力学的新发展为信息科学的发展注入了新的活力，量子力学的奇妙特性为信 息科学提供了崭新的原理和方法。诞生于2 0 世纪7 0 年代的量子信息论主要包括量子 通信和量子计算两个内容，它是结合量子力学、信息理论和计算机科学的- - 1 7 工f 在迅 速崛起、日臻成熟的新兴交叉学科。它不仅有广阔的发展和应用前景，而且也有助于 推动量子力学本身基础问题的研究发展。作为量子信息领域中最重要的研究方向之一 的量子通信与目前成熟的经典通信技术相比，具有巨大的优越性，如：保密性强、大 容量、远距离传输等特点。量子通信不仅在军事、国防等领域具有重要的作用，而且 会极大地促进国民经济的发展。 量子通信网络是当前国际上热门的研究课题之一，欧洲、北美和日本投入了大量 的人力物力进行研究，并提出了多种网络拓扑结构和寻址方式。2 0 0 4 年6 月3 日， 世界上第一个量子通信网络在美国马萨诸塞州剑桥城正式投入运行。2 0 0 7 年中科院 量子信息重点实验室，利用自主创新的量子路由器，在北京网通公司商用通信网络上 完成了四用户量子密码通信网络的测试运行，并确保了网络通信的安全。这次实验的 成功为量子因特网的发展奠定了基础。在目前的技术条件下，能用它扩建成拥有数百 2 北京邮电大学博士学位论文 第一 个用户的量子通信网络。2 0 0 8 年，潘建伟教授的科研团队成功研制了基于诱骗态的 光纤量子通信原型系统，成功组建了世界上首个3 节点链状光量子电话网。基于此 网，又建成了世界上首个5 节点的星型量子通信网络，首次实现了实时语音量子保密 通信。这一成果在同类产品中位居国际先进水平，标志着中国在城域量子网络关键技 术方面已经达到了产业化要求。2 0 0 9 年，中国科大中科院量子信息重点实验室郭光 灿院士和韩正甫教授带领的团队，与芜湖市人民政府合作，在该市建成了世界上第一 个“量子政务网”。融合了国际上现有的三种组网技术，首次设计出了具有多层次、旨 在满足不同用户需求的多功能量子保密通信网络，通过该网络可以完成任意两点之间 的绝对保密的通信，不仅可以实现保密声音、文件及动态图象的绝对安全通信，还能 满足通信量巨大的视频保密会议和大量公文保密传输的需求。同年，在国际上4 1 个 研究所和业界机构的努力下，研究人员共同协作联合建造了世界最大的量子密钥分布 网络，成功实现了量子加密的信息在8 节点m e s h 网络上的安全传送。这一结果完全 打破了以往的所有纪录，使量子网络安全通信系统向实用化又迈出了一大步。基于量 子通信网络的实验和建设的实际发展需求，理论研究当一个量子通信的整体网络已经 实现，如何解决量子网络中的瓶颈问题、有效利用网络资源具有重要的研究意义。 网络编码理论和应用在经典通信领域取得了大量的研究成果，借鉴这些研究成 果，结合量子信息的特有属性，将网络编码思想用于量子通信领域以提高量子网络的 整体性能，将有很大理论和应用价值。运用量子信息理论、图论、经典网络编码等多 学科相交叉的理论和工具，围绕量子信息理论和经典网络编码的原理和方法，对量子 网络编码开展深入研究将有重要的意义。量子网络编码的相关研究成果已经发表在 p h y i c a lr e v i e w a 等著名刊物上，并且已经丌始引起研究者的关注。 总之，网络编码具有重要的理论价值和广阔的应用前景，已被认为是下一代网络 关键技术之一。由于网络编码能为通信网络提供很大的性能增益，它已成为网络信息 领域备受关注的一项课题，其研究呈现出多元化的趋势，并f 试图转向实用化。随着 研究的不断深入，网络编码技术一定会从理论走向实用，而且其应用领域必定会越来 越广泛。 1 2 研究现状 经典网络编码 网络编码思想突破了传统数据传输的模式，在提高网络吞吐量、均衡网络负载、 3 北京邮电大学博士学位论文 第一章绪论 提高带宽利用率、增加网络的鲁棒性( r o b u s t n e s s ) 和自适应性( a d a p t a b i l i t y ) 等方面带来 了许多潜在的优点。多播( m u l