（计算机应用技术专业论文）无线自组织网的网络编码技术.pdf

南京i | i i ；l 【1 人学坝i j i j | = 。， 生学位论文摘要 摘要 通常认为，中f n j 节点所进行的数据处理对数据传输过程本身并不会带来任何好处：然 而，2 0 0 0 年，a h l s w e d e 等人在i e e e 信息论会刊上发表了题为( ( n e t w o r ki n f o r m a t i o nf l o w ) ) 的论文，彻底推翻了上述结论，从理论上证明了在中间节点应用网络编码技术可以提高数 据传输速率。 网络编码是一个信息编码理沦，是一种在网络中维持最大信息流量的方法。网络编码 的核心概念是允许在媒介网络：肯点上整合数据，继而转发；它的基本思想是网络：节点不仅 参与数掘转发，还参与数据处理。本文通过对自组织网络中随机线性编码技术进行分析和 研究，提出了可以应用于无线白组织环境下的无线随机线性编码算法一一w r l c ，并在理 论推导的基础上应用n s 模拟器对算法进行了仿真验证。在基于无线信道的多播模型中， w r l c 算法通过在中间节点对数据进行随机线性处理，进而传输多个数据报文的组合，从 某种程度上提高了信息传输速率。研究和仿真结果表明，通过在中间节点使用w r l c 算法， 数据传输速率提高了约3 0 ；并且，当请求相同信息节点的数量增加时，数据的传输速率 也相应增加；直至节点数量达到某个阈值后，数据传输速率将不再增加。 关键词：自组织网络、无线m e s h 网、网络编码、随机线性编码 南京| | i | ；l u 人学f i | ；l j 了生学位论义a b s ”a c t a b s t r a c t i ti ss a i dt h a td a t am a n a g e m e n ta tm e d i a nn o d e sw o u l dn o td oaf a v o rt od a t at r a n s p o r t a t i o n p r o c e s s h o w e v e r , a h l s w e d ep u b l i s h e dap a p e rn a m e dn e t w o r ki n f o l 。m a t i o nf l o wo ni e e ei n 2 0 0 0 ，w h i c hp r o v e dt h a tt h ea b o v ec o n c l u s i o nw a sc o m p l e t e l yw r o n g a h l s w e d ep r o v e dt h a t n e t w o r kc o d i n gc o u l dr a i s ed a t ar a t e ，b u ti tw a sl i m i t e dt ot h e o r yl e v e la tt h a tt i m e n e t w o r kc o d i n g ，a ni n f o r m a t i o nc o d i n gt h e o r y , i sam e t h o dw h i c hc a nm a i n t a i nt h em a x i - m u mi n f o r m a t i o nf l o wi nt h en e t w o r k s i t sk e r n e lc o n c e p t i o ni st oa l l o wd a t am i x t u r ea tn e t w o r k m e d i a nn o d e s ，w h i c hm e a n st h em e d i a nn o d e sn o to n l yt a k ep a r ti nd a t ar e t r a n s p o r t a t i o n ，b u ta l s o i nd a t ap r o c e s s i nt h i sp a p e r , i tf i r s ta n a l y z e st h er a n d o ml i n e a r c o d i n gt e c h n o l o g yi n s e l f - o r g a n i z e dn e t w o r k ，a n dt h e np r o p o s e san e wa l g o r i t t u nn a m e dw r l c - - w i r e l e s sr a n d o m l i n e a rc o d i n gb a s e do nw i r e l e s ss e l f - o r g a n i z e dn e t w o r k ，f i n a l l yg i v e si t ss i m u l a t i o nw i t hn s 一2 w r l cs u p p o r t sd a t al i n e a rp r o c e s s i n ga tm e d ia nn o d e sa n dt h e nt r a n s p o r t sac o m b i n a t i o no f m u l t i p l ed a t am e s s a g e s ，w h i c hr a i s e si n f o r m a t i o nd a t ar a t et os o m ee x t e n t t h es i m u l a t i o np r 6 e s t h a ta p p l y i n gw r l ca tm e d i a nn o d e sd u r i n gd a t at r a n s p o r t a t i o nc o u l dr a i s ed a t ar a t eb y3 0 ： m e a n w h i l e ，w i t ht h eg r o w i n gn u m b e ro fn o d e si nt h ev e r yn e t w o r k ，d a t ar a t ec a ng r o wu pa c c o r d i n g l yu n t i lt h en u m b e ro fn o d e se q u a l st oc e r t a i nm a x i m u mv a l u e k e y w o r d s ：s o n ，w m n ，n e t w o r kc o d i n g ，r a n d o ml i n e a rc o d i n g 南京i | | i f i u 人学坝l j 圳究生学位论爻 缩略语 缩略语 缩略词英文全称中文翻译 a c k a c k n o w l e d g e应答 a o d va d h o cd e m a n dd i s t a n c ev e c t o rr o u t i n g 白适应调制编码 a pa c c e s sp o i n t 接入点 b g p b o u n d a r yg a t e w a yp r o t o c o l边界网天协议 b s ab a s i cs e r v i c ea r e a 基本服务区 b s sb a s i cs e r v i c es e t 基本服务组 c s m ac a r r i e rs e n s em u l t i p l ea c c e s s 载波监听多路接入 c t sc l e a rt os e n d 清空输山窗口 d d nd a t ad i s t r i b u t e dn e t w o r k s 数字分组网 d s d vd e s t i n a t i o ns e q u e n c e dd i s t r i b u t e dv e c t o r 目标序5 , j j t e 离久苗算法 d s r d y n a m i cs o u r c er o u t i n g动态源路由算法 f rf r a m er e l a y 帧中继 g s mg l o b a ls y s t e mf o rm o b i l ec o m m u n i c a t i o n s 全球移动通信系统 i e e ei n s t i t u t eo fe l e c t r i c a la n de l e c t r o n i ce n g i n e e r s 电气电子i ：程师协会 i e t fi n t e r n e te n g i n e e r i n gt a s kf o r c e 冈特网l ：群任务宝l i m si pm u l t i m e d i as y s t e m i p 多媒体子系统 i pi n t e r n e tp r o t o c o l 互联网协议 l t ui n t e m a t i o n a 】t e l e c o mu n i o n 国际电信联盟 l c ml i n e a rc o d i n gm u l t i c a s t 线性多播编码 m a cm e d i aa c c e s sc o n t r o l 媒体访问控制 m a n e tm o b i l ea d h o cn e t w o r k s 移动白组织网络 m cm e s hc l i e n t s 网状客户机 m rm e s hr o u t e r s 网状路由器 m v r o i pm o b i l ev o i c eo v e ri p 移动v r o i p n cn e t w o r kc o d i n g 网络编码 o l s r o p t i m i z e dl i n ks t a t er o u t i n g优化链路状态路由算法 o s p f o p e ns h o r t e s tp a t hf i r s t开放最短路仔优先协议 p m pp o i n tt om u l t i p o i n t 点对多点 p 2 pp e e r t op e e r 对等网络 q o sq u a l i t yo fs e r v i c e 服务质昔 5 2 南京l l l | ：i u 人学f 研i j 研究生学位论文缩略语 缩略词英文全称 中文翻译 r f l dr a d i of r e q u e n c yi d e n t i f i c a t i o n 射频标识 r i p r o u t i n gi n f o r m a t i o np r o t o c o l信启，路由协议 r l cr a n d o ml i n e a rc o d i n g 随机线性编码 r m sr a n d o mm e s s a g es e n d 随机报文分发 i 玎s r e a d yt os e n d发送请求 s o h os i n a i lo 踊c eh o m eo f f i c e 小掣办公室平家庭办公室 s o n s e l f - o r g a n i z e dn e t w o r k s 白组织网络 s s ss u b s c r i b e rs t a t i o n s 川户站 t b r p f t o p o l o g yb r o a d c a s tb a s e do nr e v e r s ep a t hf o r 基丁拓扑j “橘的反向路径转 w a r d i n g 发算法 t o r a t e m p o r a l l yo r d e r e dr o u t i n ga l g o r i t h m临时顺序路由算法 u w bu l t r aw i d e1 3 ；a n d 超宽带 v o i pv o i c eo v e ri p i p 语音业务 v p n v i r t u a lp r i v a t en e t w o r k s 虚拟专川网 w i f iw i r e l e s sf i d e l i t y 无线相容性认i 止 w l a nw i r e l e s sl o c a la r e an e t w o r k s 无线局域网 w m a nw i r e l e s sm e t r o p o l i t a na r e an e t w o r k s 无线城域网 w m nw i r e l e s sm e s hn e t w o r k s 无线网状网 5 3 南京邮电大学学位论文独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究 工作及取得的研究成果。尽我所知，除了文中特别加以标注和致谢的 地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包 含为获得南京邮电大学或其它教育机构的学位或证书而使用过的材 料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了 明确的说明并表示了谢意。 研究生签名： 查壁整日期：型：竺 南京邮电大学学位论文使用授权声明 南京邮电大学、中国科学技术信息研究所、国家图书馆有权保留 本人所送交学位论文的复印件和电子文档，可以采用影印、缩印或其 他复制手段保存论文。本人电子文档的内容和纸质论文的内容相一 致。除在保密期内的保密论文外，允许论文被查阅和借阅，可以公布 ( 包括刊登) 论文的全部或部分内容。论文的公布( 包括刊登) 授权 南京邮电大学研究生部办理。 研究生签名： 至垃丝塑导师签 南京f j | l ；l u 人学顺i ：t i jr , 咒生学位论文第一章白i 1 1 织川络及je 关趾技术 第一章自组织网络及其关键技术 随着通信技术的快速发展和人们对通信智能性要求的提高，自组织网络成为网络技术 发展的重要方向之一。本章对自组织网络技术的发展历程和发展趋势进行了介绍，并重点 介绍了自组织网络的网状模型；之后对自组织网络中的网络编码技术进行了阐述，并提出 了基于无线自组织网络的一种新型编码算法。 1 1 自组织网络 自组织网络( s o n ，s e l f - o r g a n i z e dn e t w o r k s ) 是具有自动配置、自动发现、自动组织 等特性的多跳网络。自组织网络的自动配置和自动发现特性使得w i f i ( w i r e l e s sf i d e l i t y ) 设备在组网的时候对用户是透明的。在网络拓扑变动或链路断丌的情形下，白组织网络的 自动愈合和自动组织的特性在很大程度上增强了移动a dh o c 网络( m a n e t ，m o b i l e a dh o c n e t w o r k ) 的健壮性。同时，自组织网络能够优化带宽使用率，其多跳路由技术扩展了网 络的覆盖范围，基于i p ( i n t e m e tp r o t o c 0 1 ) 层的自组织网络技术可支持多种无线或( 和) 有线接口。 1 1 1 自组织网络的核心特征 自组织网络原来特指无线自组织网络，即a dh o c 网络，随着p 2 p ( p e e rt op e e r ) 等具 有明显自组织特性网络的出现，自组织网络的概念逐渐宽泛化。它不但包括通常所指的无 线自组织网络，而且包括具有自组织特性的p 2 p 网络和i p 网络。通过与其他技术的交叉 与融合，在提及自组织网络的时候还会涉及r f i d ( r a d i of r e q u e n c yi d ) 网络、网格技术 在占 寸。 自组织网络具有无中心化和节点对等的特性。在a dh o c 网络中，所有节点的地位平等， 无需设置任何的中心控制节点，不依赖固定的网络设施。网络节点既是终端也是路由器。 当某个节点要与其覆盖范围之外的节点进行通信时，需要中间节点的多跳转发。 同时，自组织网络中的节点能够适应网络的动态变化，快速检测其他节点的存在和探 测其他节点等。网络节点通过分布式算法来协调彼此之间的行为，无需人工干预或任何其 他预置的网络设施，可在任何时刻任何地方快速展丌并自动组网。鉴于网络的分布式特征 及节点的冗余性，故而不存在单点故障，任何节点的故障都不会影响整个网络的运行，具 有很强的抗毁性和健壮性。 1 南京邮电人学硕1 ：研究生学位论文第章自组织网络及其关键技术 无线自组织网络通常指移动自组织网络【l 】，m a n e t 是一种不同于传统无线通信网络的 技术。传统的无线蜂窝通信网络需要固定的网络设备( 如基站的支持) 来进行数据转发和 用户服务控制。m a n e t 不需要固定设备支持，各节点( 用户终端) 自行组网，通信时由 其他用户节点进行数据的转发。m a n e t 突破了传统无线蜂窝网络的地理局限性，能够更 加快速、便捷、高效的部署，适合于一些紧急场合的通信需要( 如单兵通信系统) 。但是， 无线自组织网络存在网络带宽受限、对实时业务支持较差、安全性不高等弊端。 1 1 2 自组织网络的研究热点 由于自组织网络具有很好的网络特性，近年来，业界对自组织网络极其关注，研究的 重点和热点主要集中在以下几个方面： m a c ( m e d i aa c c e s sc o n t r 0 1 ) 协议的研究1 2 1 在自组织网络中，多个节点共享同一无线信道，节点发送分组具有随机性；为了减少 碰撞，必须由m a c 协议来建立共享信道的访问机制。高效的m a c 层协议是自组织网络 的一个研究热点。目前最常见的m a c 层协议有载波监听多路接入( c s m a ，c a r r i e rs e n s e m u l t i p l ea c c e s s ) 以及i e e e8 0 2 1 1 中基于r t s ( r e q u e s tt os e n d ) 、c t s ( c l e a rt os e n d ) 、 a c k ( a c k n o w l e d g e m e n t ) 的协议等。 路由协议的研究p i 自组织网络能够降低节点能耗、减少带宽消耗、适应拓扑快速变化，而现有的i p 路由 协议，如路由信息协议( r i p ，r o u t i n gi n f o r m a t i o np r o t o c 0 1 ) 、边界网关协议( b g p ，b o u n d a r y g a t e w a yp r o t o c 0 1 ) 、开放最短路径优先协议( o s p f ，o p e ns h o r t e s tp a t hf i r s t ) 等，都不能 满足需求。目前i e t f ( i n t e r n a t i o n a le n g i n e e r i n g & t e c h n o l o g y f o r c e ) 的m a n e t 工作组对路 由协议的研究成果主要有a o d v ( a d h o cd e m a n dd i s t a n c ev e c t o rr o u t i n g ，基于a dh o c 的距离矢量路由算法) 、t o r a ( t e m p o r a l l yo r d e r e dr o u t i n g a l g o r i t h m ，临时顺序路由算法) 、 d s r ( d y n a m i cs o u r c er o u t i n g ，动态源路由算法) 、o l s r ( o p t i m i z e dl i n ks t a t er o u t i n g ， 优化的链路状态路由算法) 、t b r p f ( t o p o l o g yb r o a d c a s tb a s e do nr e v e r s ep a t hf o r w a r d i n g ， 基于拓扑广播的反向路径转发算法) 、d s d v ( d e s t i n a t i o ns e q u e n c e dd i s t r i b u t e dv e c t o r ，目 标序列距离矢量算法) 等。 自组织网络安全保障机制的研列4 j 。 自组织网络具有开放的网络结构，节点共享资源，网络拓扑支持动态变化，这决定了 自组织网络极易受到主动或被动的攻击，只能为用户提供较差的安全性能。自组织网络的 安全威胁主要有拒绝服务攻击、禁止“睡眠”攻击、被动窃听、数据篡改和重发、伪造身 2 南京邮电大学硕上研究生学位论文第一章自组织m 络及其关键技术 份取得信任等。 针对这些安全威胁，传统网络的安全解决方案不能适应自组织网络的特定环境，不能 直接用于自组织网络。目前关于自组织网络的安全性研究主要集中在无中心环境下节点间 信任关系的建立与维护、安全选路机制等。 与现有网络融合模式的研究 自组织网络作为一个独立的网络形态而存在，但是随着自组织网络技术的逐步成熟和 应用范围的日趋扩大，与现有有线网络的互通乃至接入i n t e m e t 是对自组织网络的一个发 展要求。未来的自组织网络需要与i p 网络互通，需要与3 g 、4 g t 5 1 、u w b ( u l t r aw i d eb a n d ) 6 1 等无线网络融合，需要与r f i d 技术相衔接i 刀，这是一个不可避免的发展趋势。 1 2 自组织网络的网状拓扑 w m n ( w i r e l e s sm e s hn e t w o r k ，无线m e s h 网) 是在m a n e t 基础上发展起来的多跳 无线网络，作为一种新型的无线接入技术，w m n 以其大容量、高速率、覆盖范围广等优 点成为宽带接入的有效手段，它充分融合了m a n e t 的多跳性以及w l a n ( w i r e l e s sl o c a l a r e an e t w o r k ) 的高速数据传输等优点，主要包括t 先期投入低、渐进部署、易维护、健 壮、可靠服务覆盖，配备无线网卡的节点可以直接( 没有无线网卡的可以通过以太网等) 连接到无线网状路由器f 8 l 【1 5j 。w m n 有助于实现任何时间、任何地点、总在线的理想状态， w m n 对很多应用来说是一项非常有前途的无线技术，比如宽带家居网络、小区网络、企 业网络和楼宇自动化等，为“最后一公里”的接入问题提供了一个优化的解决方案。 1 2 1 无线网状网w i n 随着无线技术的发展和日趋成熟，无线网络从最初支持单一无绳电话的模拟蜂窝网， 发展到今天能支持尽可能多的接入设备的无线网状网w m n ，网络形态也可能由“以有线 为主发展到“以无线为主有线为辅”。无线网络不是用来取代有线网络的，而是用来弥 补有线网络的不足，以达到网络延伸的目的。目前，有线网络技术已经发展的比较完善， 鉴于无线网络具有常规网络无可比拟的优点，近几年业内关注和研究的热点主要集中在 w l a n 的传输速率及安全保证、m a n e t 的路由技术及q o s ( q u a l i t yo f s e r v i c e ) 机制上。 无线局域网是计算机网络与无线通信技术相结合的产物，它通常由无线网卡、无线接 入点a p ( a c c e s sp o i n t ) 、计算机等相关设备组成：采用单元结构，将整个系统分成许多单 元，每个单元称为一个基本服务组b s s ( b a s i cs e r v i c es e t ) 。一个无线局域网可由一个基 本服务区b s a ( b a s i cs e r v i c ea r e a ) 组成，一个b s a 通常包含若干个单元，这些单元通过 a p 与某骨干网相连。骨干网可以是有线网络，也可以是无线网络1 9 j 1 1 0 i 【1 6 l 。 3 南京邮电人学硕七研究生学位论文第一章自组织网络及其关键技术 m a n e t 出现之初是指一种小型无线局域网，这种小型无线局域网的节点之间不需要 经过基站或其他管理控制设备就可以直接实现点对点的通信；当两个通信节点之间由于功 率或其他原因导致无法实现链路直接连接时，网内其他节点可以帮助中继信号，以实现网 络内各节点的相互通信。m a n e t 是由移动节点和它们之间的无线连接组成的临时无线移 动网络，没有基站和交换中心，它的运行不依赖于任何预设的固定网络设施，节点可以随 意移动，可以在没有或不便利用现有的网络基础设施的情况下提供一种通信支撑环境1 1 1 1 。 无线局域网使用无线传输介质，取消了导线的桎梏，能提供流动的工作站；但是由于 设备价格高、数据传输速率低、信息安全和授权要求等方面的限制，无线局域网的使用仍 然很少。m a n e t 能够为快速、频繁移动的节点提供良好的支持，在军事或特殊应用场合 发挥了很好的作用；但现实生活中网络节点通常具有相对静止的特性，m a n e t 技术略显 过犹不及。 1 2 2w m n 的应用架构 无线网状网是由无线设备构成的自组织网络，它将每个设备看作一个路由节点，无需 基础设施的支持；w m n 由节点组成，节点分成网状路由器m r ( m e s hr o u t e r ) 和网状客 户机m c ( m e s hc l i e n t ) ，每个节点都可以转发分组。w m n 可以动态自组织和自配置，节 点自动建立与维护网状连接；网状路由器的网关网桥功能可支持w m n 与其他无线网络 如蜂窝网、无线传感器网、w i f i 、w i m a x 、w i m e d i a 的集成。从w m n 的角度重新思考 现有无线网络，特别是i e e e8 0 2 1 l 网络、移动自组织网络、无线传感器网络及i e e e8 0 2 1 6 网络i 。2 1 1 1 3 1 等，将是网络性能优化的一个切入点。 目前，w m n 的网络架构主要有三种：基于终端设备的网络结构( 也称为平面结构) j 基于基础设施的网络结构( 也称为多级结构) 以及混合网络结构。在平面结构中，节点的 地位平等，节点既是客户端也是路由器，既能享受服务也能转发分组；理想状态下，网内 任意两个节点可以直接通信，但是考虑到无线信号的衰减和干扰，这种网络通常规模相对 较小，适合类似w l a n 的应用。在多级结构中，底层节点仅为客户端，上层为路由节点， 这种网络的规模相对较大，适合组建无线城域网w m a n ( w i r e l e s sm e t r o p o l i t a na r e a n e t w o r k ) 1 7j i l 3 1 ；但是底层节点不可直接通信，要与其他节点的通信必须通过上层路由节点 的转发。混合网络结构是平面结构和多级结构的结合，网络的整体架构类似于多级结构， 底层节点的互连方式类似于平面结构：“聚簇”技术针对混合结构中底层节点进行网络优 化，它的主导思想是“簇内节点直接通信，簇间通信需经过簇头转发”1 5j 。混合网络结构 如图1 1 所示。 4 南京i | f i ；i u 人学坝i j f j j i = 究生学位论文第一章白 儿织i - j _ ? r 戍j l 关键披术 图1 1w m n 的混合网络结构 从图1 1 中可以看出，w m n 的底层( 物理层) 终端用户以p 2 p 方式组网，实现任意节 点i 、日j 的互连互通，也就是通常意义上的自组织网；其上为由网状路由器和网关组成的网络 层，负责不同区域i 日j 通信的路由和转发；最终w m n 需通过骨干网中a p 接入i n t e r n e t 。为 了便于管理，通常将底层节点进行分簇，簇内节点为对等的通信实体；簇问通信需要经过 “簇头”转发，“簇头”是通过选举算法获得的簇内性能最优的节点，一般而言，它不是 固定不变的。对于物理层的网状拓扑，根据最优化理论，并非任意节点问都存在“直接连 接”爿。是最优的；为了避免不必要的冗余，在w m n 中引入优化的聚簇拓扑，以局部网状 最优进而获得全网的较优，是值得探讨的问题 1 4 】【1 7 】。 1 3 自组织网络中的网络编码技术 网络编码( n e t w o r kc o d i n g ) 是一个信息编码理论，是一种在网络中维持最大信息流量 的方法。网络编码的核心概念是允许在媒介网络节点上整合数据，进而转发。接收者通过 查看这些分组，应用特定的算法推导得出初始化时的分组信息。网络编码是近年来通信领 域的重大突破，其基本思想是网络节点不仅仅参与数据转发，还参与数据处理，从而大幅 度提高网络性能【1 8 】【l9 1 。 网络编码作为一种新型技术在宽带无线自组织网络中有很好的应用。通过网络编码， 中间节点可以将接收到的信息在编码后发送出去，从而提高网络的吞吐量和健壮性。为了 不对现有网络软硬件设备和相关协议进行很大修改，可以选择在高层实现网络编码。无线 传感器网络( w s n ，w i r e l e s ss e n s o rn e t w o r k ) 、无线m e s h 网等无线自组织网络都可以使 用网络编码技术来提高多跳链路的传输性能。目前，网络编码的研究热点主要集中在网络 编码节点选取方案、网络编码算法设计、网络编码复杂度分析、网络编码性能分析、网络 编码与系统安全性分析以及网络编码在无线分布式网络中的应用等方面。 5 南京i l l l ：l 【1 人学坝l ：4 i j f j ( 生学位论文第一章白组织i 叫络使jc 关键技术 本文在分析自组织网网络编码的基础上，针对网状架构的无线自组织网，提出了一种 新的网络编码技术一一无线随机线性编码技术( w r l c ，w i r e l e s sr a n d o ml i n e a rc o d i n g ) 。 第二章主要对现有的自组织网网络编码技术进行了分析，第三章对w r l c 算法进行了建模 和推理，第四章基于具体的数据模型分析了仿真结果，第五章从理论和仿真的角度对全文 进行了总结并证明了w r l c 算法可以在很大程度上提高网络的吞吐量和健壮性。 南京邮电大学硕士研究生学位论文 第二章自组织网中的网络编码技术 第二章自组织网中的网络编码技术 网络编码已经被证明是可以逼近网络容量理论传输极限的有效方法，已经被国际学术 界认定为解决网络问题的重要手段。目前，具有确定拓扑的有线网络中的线性编码受到广 泛关注；同时，基于无线网络的编码技术也日渐成熟，尤其是自组织网络上的网络编码技 术。本章将着重讨论自组织网络中的线性编码技术，本文网络编码的基本模型是基于文献 1 9 2 1 的。 2 1 网络编码的理论模型 a h l s w e d 一9 1 最早证明了，当信号域趋于无穷时，网络编码可使信源节点与任意信宿节 点以接近最小割的理论速率进行信息多播。l i t 2 0 1 证明了，有限信号域中的线性编码是进行 多播的有效形式。k o e t t e r 、m e d a r d i2 1 1 提出了一种网络编码的代数框架，作为随机网络以及 鲁棒网络的一种拓展，它证明了在具有时延的有环网络中，以时不变策略获得“最大流最 小割”的极限值是可行的；同时给出了多播问题的代数特性以及在该编码方案下的过渡矩 阵。s a n d e r s 和j a g g i t 3 2j 解决了无环图在无时延的单源多播模型下的并发独立问题，并在不 同的域值下取得了近似的极限值；同时，给出了子图信息流方案的集中式定义算法和随机 多项式算法。f r a g o u l i 和s o l i j a n i n l 2 2 1 给出了两信源或多信源下信息流的一个严格上限。 r a s a l al e h m a n 、l e h m a n 和f e d e r d 副给出了编码域大小的下限，后者还针对具体的信源和信 宿流给出了不同冲突数量下信息流的特定上限。d o u g h e r t y l 3 4 1 给出了多播网络中的二进制线 性编码方案和无限域字母编码方案。r a s a l al e h m a n 、l e h m a n 、m e d a r d 以及r i i s i ”1 都强调 了非广播模型下编码方案对向量的要求。文献【3 2 、文献【2 6 】 3 3 分别描述了随机线性网络 编码以及非随机网络编码的不同应用协议以及实验环境。 设( g ，s ) 表示通信网络，其中g 为有限域上的有向图，s 是g 中唯一入度。为零的节点 ( 又称作源点) ，其余节点称作汇点。g 中的有向边称作信道( c h a n n e l ) ，假设信道为无噪 信道，并且在单位的时间内传输单位信息量( 即，l b i t s ) 。任意两个节点x 、】，间多个信 道信息量的叠加称作x 到】，的最大信息传输量( c a p a c i t y ) ，换言之，每个信道具有单位信 息量。 假设某a dh o c 网络中包含网关节点、a p 以及终端节点，拓扑如图1 1 所示。其中，网 以节点i 为头的弧的数目称为 7 的入度，以p 7 为尾的弧的数目称为1 7 的出度。 7 南京i f | | ；i u 人学顺i j f i j 究生学位论爻 第一二章白f i t 织h 中的m 络编码技术 关节点可看作信源节点j ，网关s 能够输出有限量的信息，并以多跳形式组播剑j 删络中的 其他分组节点；网络中的每个a p 节点都可充当中i 、日j 节点来转发所接收到的信息；终端节 点可以作为汇点，s 输出的信息能够在汇点处被完整还原。在整个通信过程中，汇点是否 能接收到完整信息，接收到完整信息的速率如何，将是研究的重点。图2 1 是上述a dh o c 网络的抽象模型，其中源点s 为网关节点，丁、u 、为a p 节点，x 、y 、z 是终端节 点。 图2 1 通信网络( g ，s ) 在图2 1 所示的通信网络中，丁、u 、形为对等a p 节点，x 、y 、z 为对等终端节 点，每个节点都可转发收到的分组。源点s 欲将两比特的信息6 f 、6 2 传输给】，、z ，需要经 过a p 节点转发。为了强化终端节点具有终端和类服务器的双重功能，在此假设终端节点x 具有与a p 相同的转发特性。假设信道s r 、r 肜、吖传输b l ，信道s u 、u w 、u z 传输岛， 信道w x 、x y 、x z 传输异或信息6 l06 。节点】，通过岛、b l06 解码得到抚，节点z 通 过6 、b j06 解码得到b l 。这罩假设编解码的策略是预先定义的，如高斯消去法等。不难 看出，如果不使用网络编码技术，该通信网络将不可能在单位时i 自j 内同时广播两比特的信 息，这主要是基于信道的伪“并发”特性，也就是浣，在同一时刻，单一信道只能发送( 或 接收) 特定的信息分组。在应用网络编码技术后，节点形对岛、岛进行线性编码，发送b l0 6 ， 至x ，x 广播6 io6 至y 、z ，l ，、z 经过解码计算获得b l 、良。 从某种意义上讲，简单的数据复制可以看作是网络编码的特殊形式。由信息论可知， 非源节点发送的信息流( f l o w ) 总量不超过其接收的信息总量。相应的，通信网络遵循如 下定律，非源节点集发送的信息分组是其接收到的多个信息的特定组合。这就是著名的“信 息流定律”。信息的组合方式可以是线性的，也可以是非线性的；可以是预定义的，也可 r 南京邮电大学硕士研究生学位论文 第二章自组织网中的网络编码技术 以是随机组合的。不同的组合方式对应不同的编码技术。在应用网络编码技术后，我们可 以推断，源点到汇点的信息速率随着编码集容量的扩大而不断增长：“信息流定律 给出 了信息速率的上限。 在通信网络( g ，s ) 中，源点s 到非源节点7 的“流即为s 、丁间忙用信道的容量总和。 某信道被称为忙用信道( b u s yc h a n n e l ) ，当且仅当： 1 ) 由这些忙用信道定义的子网是无环网络，也就是说，忙用信道间不可能形成有向环； 2 ) 除s 、丁之外，对每一个节点而言，接收忙用信道( i n c o m i n g b u s yc h a n n e l s ) 的数量等 于发送忙用信道( o u t g o i n gb u s yc h a n n e l s ) 的数量； 3 ) s 的发送忙用信道数量等于r 的接收忙用信道数量。 通信网络( g ，s ) 中源点到非源节点丁的“割记为节点集c ，其中c 包含s 而不包含丁。 如果x c ，y 诺c ，那么信道x y 属于“割”c 。一个“割 中的信道数量称为“割值”。 对任意的非源节点7 1 ，源点与非源节点7 间最小“割值 2 等于m a x f l o w ( t ) 。也就是说， 在通信网络中，任何包含源点和汇点的网络中都存在最大流和最小割，并且最大流的值等 于最小割的容量。这就是“最大流最小割定理 。 通信网络( g ，s ) 中的线性编码y 就是一个对向量或向量空间的分配过程。v 为每个节点 x 分配一个向量空间v ( x ) ，同时也为每个信道x y 分配一个向量v ( x r ) ，当且仅当： 1 ) v ( s ) = q ； 2 ) 对任意信道删都满足y ( 胛) v ( x ) ； 3 ) 对任意非源节点集舻，满足 _ ： 4 ) 丁上所有的发送忙用信道向量是7 1 上所有的接收忙用信道向量的线性组合。 由此可知，3 ) 指明p 中任意节点7 所对应的v ( y ) 组成的节点向量空间，与矽中所有心 对应的信道向量v ( x y ) 具有相同的线性空间，其中x 舻，y 甚矽。2 ) 、3 ) 说明了分配给每 个删的信道向量v ( a y ) 是q 上的某d 维列向量。将3 ) 应用于单个非源节点丁，可以得到 丁的所有接收信道向量v ( x t ) 组成的线性空间v ( t ) ；这表明，通信网络中的线性编码是由 特定的信道向量决定的。4 ) 也被称作“单节点信息流定律”，该定律适用于任何单一节点， 但对由满足该定律的单一节点组成的集合并不总是成立。 有了上述理论基础，接下来将详细描述如何对网络中传输的信息进行线性编码y 。首 2 对所有的t 满足m a x f l o w ( t ) = d ，我们用q 表示无限域中的一个确定的d 维向量空间。信息单元被看作是该域中的 一个符号，换言之，该域中的一个符号可在一个单位时间内由一个信道进行传输。对通信网络( g ，s ) 中的任意非源节点t ， 由源点到t 的流的最人容量用m a x f l o w , ( t ) 或m a x f l o w ( t ) 表示。 9 南京| | | | j l u 人学f i ! j | i j f j 究生学位论文铺二章白组织h 中的j - j 络编码技术 先，将源点s 传输的信息编码为d 维列向量，称为信息向量( i n f o r m a t i o nv e c t o r ) 。经过线 性编码l ，后，信道x y 中传输的数据流即为信息向量( 单行向量) 与列向量v ( x y ) 的矩阵乘 积。在这种编码方式下，向量v ( x y ) 在信道x y 的线性编码中起着核心作用。作为线性编 码的直接结果，节点的发送信道向量是其接收信道向量的线性组合。因此，节点x 发送 信道中传输的数据是其接收信道传输信息的线性组合。 实例2 1 ：为了形象理解线性编码i ，本例给出了两比特信息( 甄，b 2 ) 的多播线性编码。 网络模型如图2 1 所示，通信网络包含信源节点s ，中问转发节点t 、u 、w 、x ，终端 目的节点y 、z 。假设信息b l 、6 2 由源点s 发出，汇点为y 、z 。对线性编码l ，做如下定 义： v c 跚叫吲叫盯，= y c s u ，= v c u ，= v c u 乙，= ( ：) ， v c 麟阳c 邪悯x z = ( ： 。 信道中传输的数据即为行向量( 6 l6 2 ) 与线性编码y 分配给信道列向量的矩阵乘积。信道 w x 传输的数据是6 j + b 2 ，当q = g f ( 2 ) 时。，向量6 | + 也简化为异或值6 lb 2 。如图2 2 所 示。 ( a ) 图2 2线性编码y 实例 3 只龠柯限个几袭的域称为何限域( f i n i t ef i e l d ) 。有限域也称为g a l o i s 域( g a l o i sf i e l d ) 。含有q 个7 i 案的白i 限域通常 记为f 。e 名。g f ( q ) 。1 ：文中的g f ( 2 ) 新c f f f i 2 个7 i 索的何限域。 1 0 南京i | i i jl 也人学坝i ：f o v j c 生! 学似沦爻笫二章白组织m 中的h 络编鹏技术 如图2 2 ( a ) 所示，信息向量( 6 。6 2 ) 在信道s r 中传输的向量为( 翻如) ( ：) = 6 i ，在信道s u 中传输的向量为( 由节点接收撕、6 2 后，在信道膨中传输的向量为 ( 6 i 如) ( ：) = 岛+ 6 2 。具体编码传输如图2 2 ( b ) 所示。假设信息向量的传输需要一个单位时f 日j ， 那么，应用网络编码后，y 、z 接收6 i 、b 2 的时问t 为t = 2 a s r + 2 a 肿+ j 肼+ y = 6 a 。 如果不使用网络编码，y 、z 接收6 i 、b 2 的时i 日jt 为r _ 2 a s r + 2 a r 缈+ 2 a 心+ 2 a r = 8 a 。 由此可见，使用网络编码技术可使信息传输时i 日j 降低约2 5 ，由此获得的信息传输速率的 提升约为3 3 。 如果l ，是通信网络中的线性编码，所有节点t 满足d i m ( v ( t ) ) m a x 1 t o w ( t ) 。这是因为， 对源点s 与非源节点ti 日j 的任意割c ，有 y (