（计算机科学与技术专业论文）多源网络编码无条件安全认证码研究.pdf

独创性声明 本人声明，所呈交的论文是本人在导师指导下进行的研究工作 及取得的研究成果。尽我所知，除了文中特别加以标注和致谢的地 方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包 含为获得武汉理工大学或其他教育机构的学位或证书而使用过的材 料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作 了明确的说明并表示了谢意。 l。 签名：扬磁日期：丝! ! 三! 学位论文使用授权书 本人完全了解武汉理工大学有关保留、使用学位论文的规定， 即学校有权保留并向国家有关部门或机构送交论文的复印件和电子 版，允许论文被查阅和借阅。本人授权武汉理工大学可以将本学位 论文的全部内容编入有关数据库进行检索，可以采用影印、缩印或 其他复制手段保存或汇编本学位论文。同时授权经武汉理工大学认 可的国家有关机构或论文数据库使用或收录本学位论文，并向社会 公众提供信息服务。 ( 保密的论文在解密后应遵守此规定) 研究生( 签名) ：盎涩导师( 签名) ：塑逛兰日期：鲤 ：文了。 摘要 自网络编码理论提出后，网络编码以其可以增加网络带宽利用率、增强 网络健壮性等优点被广泛研究和应用。然而，网络编码很容易受到污染攻击。 在科技发展日益飞速的今天，安全性就显得格外重要。对于网络编码，在实 现网络资源利用率最大化的同时，也要保证网络中报文的安全传输和转发。 对于安全网络编码的研究，大部分是基于单源网络编码的情形，即网络中只 有一个源结点。众所周知，在实际的网络中，多个源结点的情形更加普遍。 因此多源网络编码的研究就更有价值和意义。 本文提出了一种新的适用于多源网络编码的无条件安全认证码 ( u n c o n d i t i o n a l l ys e c u r ea u t h e n t i c a t i o nc o d ef o rm u l t i - s o u r c en e t w o r kc o d i n g ， 即可记为u s a c m u l s n c ) ，与之前很多基于数学难题计算性假设的安全网络编 码不同的是，u s a c m u l s n c 机制是基于信息论强度，即对有无限计算资源的 攻击是健壮的，是无条件安全的；同时该机制是适用于多源网络编码情形。 通过对其进行效率和安全性分析，可以得知它对网络外部攻击者和网络内部 、矗1 个共谋者都是健壮的。在多源网络编码中，采用该认证码，在无需解码的 情况下，中继结点可以证实报文完整性和包的来源性，检测和丢弃认证失败 的包，从而防止污染攻击，实现安全网络编码。 本文的创新点主要体现在以下三个方面： ( 1 ) 首次提出了一种适用于多源网络编码情形的无条件安全认证码机制 ( u s a c m u l s n c 机制) ，与以往基于计算性假设的安全网络编码认证机制不同， 本机制是基于信息论强度，从而来保证网络编码过程中报文的完整性和真实 性。 ( 2 ) 在文中对该机制进行了效率分析和安全性分析，知晓该认证机制对网 络外部或是内部攻击都具有很强的健壮性，有效抵御污染攻击，实现报文的 安全传输和转发。 ( 3 ) 在文中将该机制与其他安全认证机制进行了比较分析，得出该机制不 仅支持多源网络编码情形，并且由于它是基于信息论强度，所以对于拥有无 限计算资源的攻击是免疫的，即能抵御穷举攻击。 关键字：网络编码，污染攻击，多源，认证码 a b s t r a c t s i n c et h en e t w o r kc o d i n gt h e o r yw a sp r o p o s e d ，i th a sb e e nw i d e l yd i s c u s s e d a n da p p l i e df o rt h ea d v a n t a g e so fi m p r o v i n gt h r o u g h p u t ，i n c r e a s i n gr e l i a b i l i t y h o w e v e r , n e t w o r kc o d i n gi sv u l n e r a b l et op o l l u t i o na t t a c k s n o w a d a y s ，a st h e r a p i dd e v e l o p m e n to ft e c h n o l o g y , s e c u r i t yi s o fg r e a ti m p o r t a n c e f o rn e t w o r k c o d i n g ，t oa c h i e v et h eg o a lo fm a x i m i z a t i o no ft h en e t w o r k r e s o u r c e su t i l i z a t i o n ，i t a l s on e e d st og u a r a n t e et h em e s s a g e st r a n s m i s s i o na n df o r w a r d i n gs e c u r e l y t ot h e r e s e a r c ho fs e c u r en e t w o r kc o d i n g ，m o s ts c h e m e sa r eb a s e do nt h es i t u a t i o no f s i n g l es o u r c en o d e ，n a m e l yt h e r ei so n l yo n e s o u r c en o d e ：w h i l e ，a si tk n o w nt oa l l ， t h ec o n d i t i o no fm u l t i s o u r c en o d e si sm o r ew i d e s p r e a di na c t u a ln e t w o r k s oi ti s v e r yv a l u a b l ea n dm e a n i n g f u lt os t u d yt h em u l t i - s o u r c en e t w o r kc o d i n g t h i sp a p e rp r o p o s e dan o v e lu n c o n d i t i o n a l l ys e c u r ea u t h e n t i c a t i o nc o d ei n m u l t i s o u r c en e t w o r kc o d i n g ( u s a c m u l s n c ) ，w i t ht h ed i f f e r e n c eo fp r e v i o u s s e c u r en e t w o r k c o d i n g s c h e m e st h a tb a s e do nm a t h e m a t i c sp r o b l e m so f c o m p u t a t i o n a lh y p o t h e s i s ，o u rs c h e m e r e l i e so nt h e o r e t i cs t r e n g t h ，i no t h e rw o r d s ， i ti sr o b u s ta g a i n s ta na t t a c k e rt h a th a su n l i m i t e dc o m p u t a t i o n a lr e s o u r c e s ，n a m e l y , i ti su n c o n d i t i o n a l l ys e c u r e ；b e s i d e s ，t h es c h e m ei sa p p r o p r i a t ef o rt h es i t u a t i o no f m u l t i s o u r c en e t w o r kc o d i n g i tc a nm a k eac o n c l u s i o nt h a tt h em e t h o di sr o b u s t a g a i n s ta t t a c k se i t h e rf r o mo u t s i d e r s o rc o a l i t i o no fk - 1i n s i d e r sb yt h ea n a l y s i so f e f f i c i e n c ya n ds e c u r i t y i nm u l t i - s o u r c en e t w o r kc o d i n g ，u s i n gt h i sa u t h e n t i c a t i o n c o d e ，i n t e r m e d i a t en o d e sc a nv e r i f yt h ei n t e g r i t ya n do r i g i no ft h em e s s a g e s r e c e i v e dw i t h o u th a v i n gt od e c o d e ，a n dd e t e c ta n dd i s c a r dt h em e s s a g e st h a tf a i l t h ev e r i f i c a t i o n ，b yt h i sw a y , t h ep o l l u t i o na t t a c k sa r ea v o i d e d ，s oa st oe n s u r e s e c u r en e t w o r kc o d i n g t h ei n n o v a t i o no ft h i sp a p e ri si nt h ef o l l o w i n gt h r e ea s p e c t s ： ( 1 ) p r o p o s e da n o v e lu n c o n d i t i o n a l l ys e c u r ea u t h e n t i c a t i o nc o d e ，a n dt h ec o d e c a nb eu s e di nt h es i t u a t i o no fm u l t i - s o u r c en e t w o r kc o d i n g ，a n di tc a ng u a r a n t e e t h ei n t e g r i t ya n da u t h e n t i c i t yo ft h em e s s a g e si nn e t w o r kc o d i n gp r o c e d u r e ( 2 ) i no u rp a p e r , w em a k ea na n a l y s i sa b o u tt h ee f f i c i e n c ya n ds e c u r i t yo ft h e s c h e m e w ek n o wt h a ti ti sr o b u s ta g a i n s ta t t a c k se i t h e rf r o mo u t s i d e r so ri n s i d e r s ， b e s i d e s ，i t c a nr e s i s t p o l l u t i o na t t a c k s ，a n da c h i e v e t h e g o a l o fm e s s a g e s t r a n s m i s s i o na n df o r w a r d i n gs e c u r e l y 1 1 ( 3 ) i nt h i sp a p e rw em a k eac o m p a r a t i v ea n a l y s i sb e t w e e no u rs c h e m ea n d o t h e rs e c u r ea u t h e n t i c a t i o ns c h e m e s ，w ec a ns e et h a to u rm e t h o dn o to n l yc a nb e u s e di nm u l t i - s o u r c en e t w o r kc o d i n gs i t u a t i o n ，b u ta l s oi ti si m m u n et ot h ea t t a c k s t h a th a v eu n l i m i t e dc o m p u t a t i o n a lr e s o u r c e s ，i no t h e rw o r d s ，i tc a nk e e po u t s a v a g ea t t a c k k e y w o r d s ：n e t w o r kc o d i n g ，p o l l u t i o na t t a c k ，m u l t i s o u r c e ，a u t h e n t i c a t i o n c o d e i i i 目录 摘要1 a b s t r a c t i i 第1 章绪论1 1 1 弓i 言1 1 2 研究背景及意义2 1 2 1 研究背景。2 1 2 2 研究的意义。2 1 3 本论文的研究目的和主要的工作3 1 3 1 本论文的研究目的3 1 - 3 2 本论文的主要工作3 1 3 3 本论文的结构3 第2 章背景知识。5 2 1 网络编码简介5 2 1 1 网络编码的产生5 2 1 2 网络编码的特点8 2 1 3 网络编码的应用1 0 2 2 安全网络编码1 6 2 2 1 安全网络编码的产生1 6 2 2 2 安全网络编码的研究1 8 2 2 3 安全网络编码研究面临的问题1 9 2 3 无条件安全认证码2 0 第3 章多源网络编码无条件安全认证码2 2 3 1 多源网络编码模型2 2 3 2 多源网络编码无条件安全认证码机制2 3 3 3 认证机制的参数设置2 6 3 4 认证机制的流程图2 6 第4 章多源网络编码无条件安全认证码机制分析2 8 4 1 认证机制的效率分析2 8 4 2 认证机制的安全性分析3 0 4 2 1 相关引理介绍3 0 4 2 2 个恶意中继结点的情形3 9 4 2 3 一组恶意中继结点的情形4 2 4 2 4d 、结。4 5 4 2 5 分析比较4 5 第5 章结论4 7 5 1 总! ；占4 7 5 2 展望4 7 参考文献4 9 致谢! ；：； 攻读硕士期间公开发表的论文5 4 武汉理工大学硕士学位论文 1 1 引言 第1 章绪论 随着科技的发展和时代的进步，在信息化今天，人们越来越多的从网络 上获取和利用所需的资源，对网络的依赖程度也越来越高，这就对网络的性 能和安全提出了更高的要求。然而，在实际中，网络性能并没有达到最优， 即网络资源没有得到最大化利用，或是网络中资源的传输没有实现安全保证。 因此，在追求效率和时间的当今，网络性能的优化就成为一个重要问题，通 过提高网络的吞吐量和健壮性，来保证网络资源利用率最大化和安全性，从 而来更好的为人们服务。 在传统的通信网络中，信息传输是由源结点发出数据包，经过中继结点 的转发从而到达目的结点，在这个过程中，网络中的中继结点对所接收到的 数据只有存储和转发两种方式，中继结点不需要进行其他的数据处理。这种 方式使得网络中信息的传输彼此独立化，网络中资源的利用率很低。直到 a h l s w c d c 等人【1 l 提出网络编码这一理念，即在网络报文传输过程中，中继结点 不再仅仅是对接收到的报文进行存储和转发，还可以对接收到的报文进行编 码组合，然后将编码后的报文传输到目的结点，而目的结点通过相应的解码 算法来得到原报文。l i 等人【2 】指出采用线性网络编码，在多播网络情况下，可 以达到网络吞吐量的最大化，从而可以极大的提高网络的传输速率，充分使 用网络中的链路资源。 然而，由于网络编码允许中继结点对所接收到的报文进行编码组合，因 而对恶意包注入的污染攻击抵抗力很差，恶意包可能来自恶意的中继结点对 接收到的报文的修改，也有可能来自于恶意结点或是虚假的源结点。因为中 继结点对收到的报文进行编码组合，这其实改变了报文传输的方式，因此一 旦网络中某个报文被恶意结点篡改，导致的结果是该报文经过中继结点编码 后，污染整个网络，使得目的结点不能恢复源报文。因此，在使用网络编码 的同时，对报文进行来源性和安全性检测就显得格外重要。 武汉理工大学硕士学位论文 1 2 研究背景及意义 1 2 1 研究背景 自网络编码理论产生后，网络中报文的传输广泛采用网络编码，因为采 用网络编码理论后，不仅可以让网络系统的资源利用率得到提高，而且还有 很多好处：比如增强网络的健壮性，减少网络中报文的传输次数，减少网络 中的拥塞情况。而在当今社会，在追求资源最大化利用的同时，也要保证资 源的安全性，因此对于网络编码来说，在提高网络吞吐量的基础上，也要保 证网络中报文的安全传输，防止受到污染攻击。 基于此，安全网络编码被越来越广泛的研究和应用，因为它实现了性能 和安全这两个指标。对于安全网络编码的设计，主要有两种思路，一种是基 于密码学理论，即数学难题假设，这种设计思路是一种有条件安全，即对于 穷举攻击是脆弱的；另一种思路是基于信息论强度，即无条件安全，该思想 对暴力破解是健壮的。同时，对于安全网络编码的研究，一般都只是针对单 源情形，即网络中只有一个源结点，而对多源情形研究得很少，而我们知道， 多源情形在现实中更加普遍，所以研究多源情形的安全网络编码是一件很有 意义的事。 对于多源情形的安全网络编码研究，现有的成果很少，并且这些设计方 案主要是基于密码学假设，即依赖数学难题很难破解，这种设计思路对于穷 举攻击不是免疫的，因而对于网络中报文的存储和转发不能保证无条件安全。 而在网络编码过程中，报文的传输如果得不到安全性保证，就会受到污染攻 击，目的结点得不到源结点的真实信息，从而导致网络报文传输的失败。所 以，对于安全网络编码的研究和设计，不仅要实现多个源结点的情形，同时 还要保证网络中报文传输的无条件安全，就显得十分迫切。 1 2 2 研究的意义 由于网络编码在网络数据包传输方面具有很强的优势，因此网络编码越 来越受到人们的研究和重视，然而一些针对网络编码的攻击也随之产生，其 中最主要的攻击是污染攻击。由于网络编码允许中继结点对收到的报文进行 编码组合，攻击结点正是利用这一特性，在报文传输的过程中对报文进行篡 改和伪造，如果中继结点不及时发现和阻止这些报文的传输，这些污染的报 文就会和其它的报文编码结合，从而来污染整个网络，这样的后果就是目的 结点不能恢复源结点发送的报文信息。所以，在追求网络性能的同时，也要 2 武汉理工大学硕士学位论文 保证网络中报文传输的安全性，即安全网络编码的研究显得很重要。而目前 针对安全网络编码的研究，主要是假设网络中只有一个源结点的情形，而在 实际情况中，多个源结点的情形更加普遍。然而，人们却很少研究多个源结 点的网络编码系统的安全网络编码情形。同时，对于多源网络编码的研究， 如何防止污染攻击，实现安全网络编码，保证报文传输的正确性并且对于穷 举攻击是健壮的，即实现无条件安全，这些都是值得考虑的问题。在科技进 步日益飞速发展的今天，在实现网络中资源利用率最大化的同时，安全性越 来越显得尤其重要，因此，研究多个源结点情形的安全网络编码就是一件很 有意义的事。 1 3 本论文的研究目的和主要的工作 1 3 1 本论文的研究目的 通过对当前网络编码特点的研究，了解网络编码过程中遇到的安全问题， 在保证网络性能和安全性的基础上，来设计一种多源安全网络编码，采用基 于信息论强度的思路，采用认证码机制来实现无条件安全，即通过设计一种 适用于多源情况下的无条件安全认证码，来让网络的性能和安全得到实现。 1 3 2 本论文的主要工作 本文所做的具体工作如下： 1 在适用于单源网络编码情况下的无条件安全认证码机制上，对其进行 扩展，提出了一种适用于多源网络编码情况下的无条件安全认证码机制 ( u s a c - m u l s n c ) 。 2 对该认证机制进行了效率分析，主要是分析其在传输过程中的代价， 计算上的代价以及存储上的代价；同时，还对该机制进行了安全性分析，得 出它对网络中外部和内部攻击都是健壮的。 3 对该认证机制与其它安全网络编码机制进行了比较分析，得出其不仅 支持多源网络编码情形，并且对于暴力破解是免疫的。 1 3 3 本论文的结构 本文的第2 章将给出相关背景知识，介绍了网络编码理论的产生以及网络 编码的特点，同时还阐述了安全网络编码的相关研究以及无条件安全认证码 技术理论。第3 章则是在介绍多源网络编码模型的基础上，提出了适用于多源 3 武汉理工大学硕士学位论文 情况下的无条件安全认证码机制。第4 章则是对该认证机制进行了效率分析和 安全性分析，通过举例得出该认证机制对于网络中外部或是内部攻击都是健 壮的。最后第5 章则是全文的总结。 4 武汉理工大学硕士学位论文 2 1 网络编码简介 第2 章背景知识 2 1 1 网络编码的产生 在传统的网络通信传输过程中，信息从源结点出发经过中继结点后最后 到达目的结点，在这个过程中，中继结点对所接收的报文只进行存储和转发， 不进行其它编码操作，这样使得报文在传输时彼此独立化，使得网络资源没 有得到充分利用。然而，a h l s w e d e 等人【1 】阐述了一种新的方法来实现网络中数 据包的传输，这一新的方法即为网络编码。该理论允许中继结点对所接收到 的报文按照某一种方式进行编码组合后再将组合后的报文转发出去，在采用 相应的解码算法的情况下，目的结点可以通过解线性方程组来恢复源结点所 发送的报文信息。通过使用这种方式，在多播网络情况下，可以使得网络资 源得到最大化利用，同时通过使用网络编码，可以减少网络拥塞，节省带宽， 提高传输效率。同时，l i 等人1 2 】指出采用线性网络编码，在多播网络情况下， 可以达到网络吞吐量的最大化，从而可以极大的提高网络的传输速率，充分 使用网络中的链路资源。这一理论的提出，从本质上改变了传统信息传输方 式，是通信网络领域中的一个重要转折点。 自网络编码理论被提出后，传统网络中数据包的处理和转发方式在使用 网络编码理论后得到很大改变，并且使用网络编码后能提高网络中资源的利 用率，所以这一理论的提出引起人们高度重视，网络编码也被广泛的研究和 应用，国外许多大学和研究机构对网络编码理论开展广泛的研究和讨论，国 内学术界也加大了对网络编码理论的关注。在对网络编码研究过程中发现， 如何设计合适并且有效的网络编码形式是一件很有意义的事。在现今对网络 编码研究的基础上，有两种思路来设计网络编码方式，一是代数构造方式的 网络编码形式，这一想法是i 由k o e t t e r 和m e d a r d 等人【3 j 设计的，在这种思路中， 数据包发送者和数据包接收者之间的联系用一个矩阵来表示，但这一设计思 路需要知道整个网络的分布情形，即网络拓扑结构需要被提前得知。在得知 网络拓扑结构以及发送者和接收者之间的联系的前提下，通过寻找最优的矩 5 武汉理：【= 大学硕士学位论文 阵来设计所需要的网络编码。二是多项式构造方式的网络编码形式，这一想 法是s a n d e r s 等人【4 】设计的，与之前采用寻求最优矩阵来设计网络编码方式 相比，在这种思路中，根据网络传输定理，即最大流最小割算法来寻找网络 中数据包在各个结点间传输的所有路径，在得知传输路径的基础上再来确定 网络中每一个结点为实现网络编码所要进行的操作，通过这种方式就可以设 计出合适的网络编码形式，与寻找最优矩阵的思路相比，这种思路将网络编 码的设计方式简单化，当然，这种思路也需要知晓网络的整个分布情况，由 于这一思路简化了网络编码的设计，因而这一思路得到广泛应用。l i ，y e u n g 和c a i 2 】在文中阐述了如下结论，在网络数据包传输中，要想得到网络的最大 传输速率，通过采用线性网络编码就可以满足这一条件，在采用线性网络编 码后，网络编码系统中的每一个接收者都可以以最大流来转发数据包，从而 实现了网络的最大速率传输。对于采用网络编码网络来传输数据包后，目的 结点一般是通过解线性方程组来得到源结点所发送的报文信息，而k o e t t e r 等 人【3 】采取另一种方案来设计网络编码，具体的思路是用求解多元多项式的方法 来代替求解线性方程组的方式，通过这种替代后，采用求解多项式的方法可 以简化网络编码的设计过程。由于之前阐述的设计网络编码的方式需要知晓 网络的拓扑情况，因而有一定的局限性。对于不知道网络拓扑情况的时候， 如何设计网络编码来实现网络中数据包的传输和转发也就显得很有必要。而 h o 等人【5 1 给出了解决方案，具体的设计思路是采用随机选取编码系数来实现 网络编码，这些编码系数都是在一个有限域上取得，采用这种设计方案，即 使不知道整个网络的分布情况，也可以实现网络编码，从而可以更有效的传 输和转发数据包。对于具体采用多项式构造方式来设计网络编码，最早阐述 相关原理和实现机制的是p s a n d e r s 4 】l = j j a g g i 6 j 等人，在文中他们阐述了在知 晓网络拓扑结构的情形下，通过相应的算法，用编码向量来标记每个编码结 点，这样在网络数据包传输的过程中，每个接收结点都可以得知上一个转发 结点的编码信息，从而通过求解多项式就可以得到源结点所发送的信息，实 现网络编码传输。做类似工作的也有j a g g i 等人1 7 l ，他们也对通过多项式构造 方式来设计网络编码也进行了研究和讨论。通过c h o u 等人1 8 j 的阐述，我们知 道，与传统数据传输方式相比，采用网络编码传输数据信息能提高网络的吞 吐量，并且可以减少中继结点的转发次数，减少网络时延，优化网络传输性 能。f r a g o u l i 等j l l 9 】贝i j 对网络编码的研究和讨论做了如下工作，分析了网络编 6 武汉理：i ：大学硕士学位论文 码的构造过程，阐述了采用网络编码后的优点以及在介绍了网络编码相关理 论基础上描述了网络编码在实际中的应用问题。 虽然网络编码有了很具体的实现方式，之前阐述的两种设计网络编码的 方式都是基于知晓网络拓扑结构的情形，以来确定网络中各个编码结点对所 接收报文的编码方式，这使得网络编码的应用存在一定的局限性，在一定程 度上限制了网络编码理论进_ 步的发展，无法适用于动态网络或是无线网络 情况。为了解决这一难题，在不知晓网络拓扑信息的情况下，让网络编码更 好的应用于网络数据信息传输中，新的设计方案随之诞生，分别是分布式网 络编码以及随机网络编码。在分布式网络编码机制中，为了在不知晓网络拓 扑信息的情况下来实现网络编码，采取的方法是在通过标记所传输的报文在 编码结点处的操作，这样使得目的结点在接收所传输的数据包后，通过观察 这些标记信息，可以知晓具体的编码操作，使得即使不知道网络的拓扑信息， 也可以实现网络编码，从而根据这些信息来恢复源结点所发送的报文信息。 这样做的优点是在不知晓网络拓扑结构的情况下实现了网络编码传输，而这 种机制的不足之处就是由于要在传输过程中为每个数据包标记相关编码信 息，使得网络传输延时增大，增加网络负载，降低网络资源传输速度，从而 影响网络性能。而对于随机网络编码，具体思路是网络中接收结点对报文进 行组合的编码系数是在一个有限域上随机选取的，在有限域足够大的前提下， 采用随机网络编码来实现网络中数据包的传输，目的结点可以通过在有限域 内取值来求解相关的线性方程组，从而恢复源结点所发送的报文信息。由于 采用随机网络编码后，网络的拓扑结构是否被知晓也就显得不那么重要，基 于这种优势随机网络编码被人们广泛的研究。h o 等人l 1 0 j 在文中采用了随机网 络编码机制，在该机制中介绍了随机网络编码机制的具体过程，指出在一个 有限域内通过选取随机编码系数，目的结点在有限域内通过求解相关的线性 方程组来恢复源结点所发送的报文信息，从而来实现随机网络编码。之前对 于随机网络编码理论的研究和讨论仅是停留于理论上，而第一次真正将随机 网络编码理论应用到实际中的是c h o u 等人【1 1 】在文中提出的方案。h o 等人1 1 2 1 在研究随机网络编码理论的基础上进行了进一步的扩展和深化，探讨了随机 线性网络编码的相关理论以及具体的实现机制，并且阐述了随机线性网络编 码理论的适用情形，指出了随机线性网络编码所具备的优点。自此，网络编 码被人们广泛的研究和讨论，网络编码理论也在不断丰富和完善。 7 武汉理工大学硕士学位论文 2 1 2 网络编码的特点 由于网络编码允许中继结点对所接收的报文信息进行编码，通过编码后 再转发出去，目的结点则进行相应的解码即可恢复发送结点所发送的报文信 息。网络编码的使用有诸多好处，比如可以提高网络资源的利用率，均衡网 络负载，提高网络吞吐量等诸多特点，分别阐述如下： 传统网络传输网络编码 图1图2 图2 1 传统网络传输与网络编码对比 ( 1 )提高了网络吞吐量：从图1 可以看出，在传统网络传输中，从结 点v 3 至u v 4 、v 4 到t 1 、v 4 到t 2 需要传输两次才能将报文a 和b 成功 发送至目的结点，在图2 中，经过网络编码后，v 4 转发a + b 至l j t l 和t 2 ，t l 根据接收到的a 和a + b ，通过高斯消元法来得到a 和b ，即 v 3 到v 4 、v 4 到t 1 、v 4 到t 2 只用转发一次就完成了原来需要两次 传输的任务。根据最大流最小割定理，网络编码可以实现网络的 最大流传输速率，在网络信息传输过程中，对于一个多个发送结 点和多个接收结点而言，若只考虑一个接收结点时，该接收结点 端会有一个传输速率，使用网络编码后，在所有接收结点受到从 中继结点转发过来的信息后，每个接收端都会保持原来的传输速 率，网络中结点的数量越多，网络编码提高网络的吞吐量优势越 8 武汉理工大学硕士学位论文 ( 2 ) ( 3 ) ( 4 ) ( 5 ) ( 6 ) 明显。 均衡网络负载：从图1 可以看出，在传统的网络信息传输过程中， 除了v 3 到v 4 要传输两次外，其它结点传输都只需要一次；而在 图2 中所有结点转发信息都只需要一次，网络负载得到均衡，使 用网络编码后可以充分利用网络中的链路资源，使流量在网络中 均匀分布，从而可以避免网络拥塞，提高链路资源利用率。 提高了带宽利用率：从图1 可以看出，除了v 3 到v 4 要传输两次才 能使目的结点得n a 和b ，而在图2 中，目的结点得到a 和b 只需要 进行一次传输，使用网络编码后使用了更小的网络资源，从而提 高了带宽的利用率。 提高了网络健壮性：使用网络编码后，网络中存储和转发的数据 包具有同样的重要性，接收结点只要收到足够的数据包就可以进 行解码，提高网络的健壮性，同时，若源结点在发送数据包时采 取措施，发送的是编码后的报文，并且不在同一条链路发送，那 么对于窃听者而言，在进行链路窃听时，由于窃听到的只是编码 后的包，无法破解得到源结点发送的报文信息，只要攻击者没有 获得足够的线性无关的消息，攻击者就不能得到源结点所发送的 报文信息，从而可以防止网络窃听。另外，使用网络编码后还可 以改善网络中的时延以及包丢失问题，对于传统的信息传输，提 高数据传输效率主要有两种方式：自动请求重传以及前向纠错检 测，采用自动请求重传机制，虽然可以提高网络的传输效率，但 却增加了网络时延；采用前向纠错机制，虽然也可以降低网络时 延，但却使网络信息传输速率得到降低。但采用网络编码，由于 网络编码允许中继结点对所接收的报文信息先进行编码组合后 再转发出去，这样就可以在时延和速率方面达到最优。 增强网络安全性：由于采用网络编码后，结点传输的报文信息不 再是原来的单一报文信息，而是经过编码组合后的报文信息，这 样就使得在网络中传输的信息更加分散，一定程度上将报文信息 进行隐藏，对于窃听攻击有很强的免疫力，从而使网络信息安全 传输得到保证。 增加了计算复杂度：由于网络编码允许中继结点对所接收到的报 文信息进行编码组合，因此，在中继结点处需要对所接收到的信 9 武汉理工大学硕士学位论文 息进行缓存，然后通过一定的处理，通过某种算法组合后再转发 出去，目的结点接收到报文信息后再通过相应的解码算法来恢复 源结点所发送的报文信息，这样就增加了网络运算的复杂度，如 果相应的编码算法很复杂，则解码的运算量也就更大，因此需要 考虑网络编码增益与使用编码算法的平衡问题。 2 1 3 网络编码的应用 由于网络编码有如此优势，因而网络编码被广泛的研究和应用。g k a n t s i d i s 等人【1 3 】在p 2 p 的文件分发网络中，采用了网络编码。源将一个大的文件划分为 多个块，发送的数据包为原始文件分块后的线性组合。而结点发送的数据包 也为接收到的数据包的随机线性组合，这样在很大程度上提高了文件传输效 率和网络的健壮性，能够面对服务器结点离开系统的极端情况。m a 1 4 】也将网 络编码技术应用到内容分发系统中。d i m a k i s 等人【1 5 】在分布式文件存储中同样 采用了网络编码技术，在使用网络编码后，通过存储开销的一些增加，一个 新的结点只需要很小代价即可重新产生它的编码数据。这在结点频繁失败的 情形时很有用。n i k o l a o s 1 6 l 考虑了一些网络编码的理论的与实际的问题。作者 展现了一个集中化的简单有效的网络编码设计算法，并且研究了网络编码的 字母表大小问题。y e u n g 等人1 1 7 】在书中从信息论的角度详细描述了网络编码的 相关理论。f r a g o u l i 等a t l 8 】在书中对网络编码进行了详细的说明，包括一些最 自然的问题，如网络编码怎样工作，收益如何，怎样设计以及开销等等。文 献【1 9 l 对网络编码的基本问题以及网络编码的热点进行了论述。 研究表明，网络编码除了能够提高系统的容量外，在如下方面也有很广 泛的应用前景，具体为：在数据压缩【2 0 j 方面，通过使用网络编码，可以减少 数据的压缩量。在负载均衡【2 1 】方面，采用网络编码理论后，通过前面的分析 可以知道，使用网络编码可以均衡网络的负载。同时使用网络编码还可以降 低结点能量消耗【2 2 1 ，因为使用网络编码后可以减少网络中数据包的传输次数， 这样就可以降低结点传输数据包信息的能量，这一点在无线网络中体现得更 加明显。使用网络编码也可以减少传播延时、提高网络健壮性l z 3 l ，这些在前 面的分析中也已提及，并且网络编码也可以运用到信息安全1 2 4 j 等方面，通过 使用网络编码机制来保证信息的安全传输。总之，网络编码有着重要的应用 前景。同时，网络编码在信息传输上有着很多的优势，作为一种提高系统性 能的方法，有很多的应用场合，主要是体现在无线网络、p 2 p 系统、网络安全 1 0 武汉理工大学硕士学位论文 保证以及分布式文件存储等方面。对于p 2 p 系统，使用网络编码，由于可以提 高网络中信息的传输效率，减少网络拥塞，因为可以加速信息下载时间；对 于无线网络，由于在无线网络中，每个结点所存储的能量是有限的，在无线 网络传输数据的过程中，每个结点不管是存储和转发数据包都要消耗相应的 能量，而使用网络编码，由于其可以增加网络的吞吐量，提高网络传输效率， 因此对于无线网络来说，使用网络编码可以增大网络中信息的流量，提高宽 带受限的无线网络吞吐量，此外，网络编码还适用于无线自组网以及无线传 感器网络，通过使用网络编码，都可以实现网络性能的提高，下面具体介绍 网络编码的主要应用领域和相关情况。 ( 1 ) p 2 p 网络 众所周知，p 2 p 是近些年来最流行的下载方式【2 引，将网络编码与p 2 p 结合 起来，可以更快的提高下载速度。在p 2 p 系统中，要找个最优的信息传输和下 载路径十分困难，因为这要求事先知道底层网络的拓扑结构，而如果采用随 机网络编码，由之前的阐述了可以知道，在不知晓网络拓扑的情形下也可以 实现网络编码，采用该机制与p 2 p 下载相结合，就可以实现下载速率的提高， 从而使得文件的下载时间减少【2 5 1 。同时，由于网络编码过程中传输的是组合 后数据包信息，即传输的数据信息具有多样性，这样使得即使某些结点下载 离开或是服务器离线，都不会对下载产生很大的影响，因为只要接收到足够 多的数据包，都可以通过相应的解码算法来恢复所要下载的信息。在p 2 p 下载 中使用随机网络编码技术可以加速资源的下载。具体机制为：假设服务器给 用户么发送文件，首先服务器将文件均匀分成刀份，分别记为筋，z ：，通 过采用随机网络编码，随机的选取系数c l ，c 2 9 , * o9 ，对每个文件小块进行编码 后得到日一c l x l + c 2 觞+ + 巳，然后将e 1 发送给彳，同样的道理，么也可以 得到从其他结点或服务器传来的易，若记e 2 6 l 筋+ b z x ：+ + 氏，即对于4 而言，再随机选取系数c l ，c 2 通过类似的原理组合后可以发送至下一个结点， 以此类推，通过这样的机制来实现网络编码与p 2 p 系统的结合。这样，只要一 个结点接收到了足够多的数据信息，就可以通过利用高斯消元法解线性方程 组来得到原始信息。在p 2 p 系统采用网络编码，数据块下载的调度开销变小， 网络分块实现均匀化，有效的较少了网络拥塞的情形，同时，网络编码能够 适应p 2 p 系统的动态变化，使系统具有更强的健壮性，因此，网络编码在p 2 p 系统中得到广泛应用。对于网络编码与p 2 p 系统的具体结合机制如下图1 2 5 j 所 武汉理工大学硕士学位论文 不： 图2 2 网络编码与p 2 p 系统的结合机制 ( 2 ) 无线网络 由于无线网络【2 6 l 的广播特性，而网络编码又适合于多播环境，使得网络 编码的使用更加具有可行性，通过使用网络编码，可以更好的为无线环境下 数据包信息的传输服务。通过之前对网络编码的特点分析可知，采用网络编 码后不仅可以使得网络中数据包的传输和转发减少，同时还可以使得无线网 络中结点存储和转发所需的能量降低，进而来提高网络的整体性能。在无线 网络中，在使用随机网络编码的情况下，由于随机网络编码的特性，即使无 线网络中某些结点不能进行存储和转发，也不会影响整个网络的性能，因为 随机网络编码中编码系数的选取是在一个足够大的有限域内随机选取的，只 要有限域足够大，目的结点仍可以通过在有限域内取值来解相关线性方程组 来得到源结点所发送的数据包信息，通过这样，网络的容错性得到提高。 ( 3 ) 网络安全 在传统的信息传输过程中，网络安全【2 7 l 主要是通过数据加密、哈希函数、 消息认证以及数字签名来实现数据的安全传输。对于采用数据加密和哈希函 数机制而言，在实现数据安全传输的同时，会使得计算复杂性变大，从而使 得传输效率变低。对于数字签名机制，它是在所要传输的报文上附加一段数 据标识，是一种认证机制，它使得消息的产生者可以添加一个起签名作用的 1 2 武汉理工大学硕士学位论文 码字，通过计算消息的散列值并用产生者的私钥加密散列值来生成签名，通 过签名保证了所传输消息的来源真实性和完整性。保存数字签名的拷贝是可 行的，而用数字签名来保证网络安全，会使得计算复杂习惯比较大，进而使 得网络性能降低。对于消息认证，它是用来验证消息完整性的一种机制或服 务，消息认证确保所收到的数据确实和发送时的一样，即没有修改、插入、 删除或重放，并且发送方声称的身份是真实有效的。消息认证就是所接收到 消息的来源性，并且具有抗抵赖性的功能，用这种机制虽然可以实现网络的 安全传输，但不足之处就是会增大消息的冗余。基于此，需要寻找一些安全 高效的数据传输方式来保证网络安全，而将网络编码理论应用到网络安全领 域，可以得到很