（计算机应用技术专业论文）基于网络编码的无线网络可靠路由算法.pdf

浙江工业大学硕士学位论文 基于网络编码的无线网络可靠路由算法 摘要 无线网络技术是当今世界最热门的技术之一，得到广泛应用。随着无线通信技术发展 及功能强大的无线终端设备的普及，无线网络的应用领域日益拓广，涉及军事、民用等诸 多方面。相应地，对无线网络的相关技术的深入研究和探讨势在必行。 路由技术是无线网络研究的重点问题之一。至今，一些学者根据不同的网络环境和应 用场合及要求提出了许多行之有效的路由算法，如能量有效路由、实时路由、安全路由等 等。与有线网络不同，在无线网络中，数据包是通过无线信道进行传递的，数据包的传递 过程会受到环境变化、无线信道受干扰、节点失效等因素的影响，从而造成数据包的丢 失，因此在无线网络中保证信息传递的可靠性显得十分重要。本文研究不可靠无线网络中 进行可靠数据传递的问题，着重研究在网络编码( n e t w o r kc o d i n g ) 支持下的可靠数据传 递问题。 网络编码是近年来通信领域的重大突破，其基本思想是网络节点不仅参与数据转发， 还参与数据的处理，使得在使用了网络编码之后，整体数据的还原并不依赖于单个具体数 据包。也就是说，只要确保足够数量的数据包到达目的节点，即使在数据传递过程中丢失 部分数据包，也不会影响目的节点对整体数据的成功还原。本文基于网络编码思想，提出 一种免重传路由算法，这种算法以最小化单位比特有效数据的能耗为目标，给出最优化的 数学模型，并用遗传算法进行求解。此外，进行数值实验以分析各种参数对算法能耗的影 响，并将本文提出的免重传路由算法与最可靠路径优先及最短路径优先等路由算法进行对 比。本文的研究成果可以应用于包括i e e e8 0 2 1 l ，i e e e 8 0 2 1 5 ，i e e e8 0 2 1 6 在内的各种无 线网络。 关键词：无线网络，路由，网络编码，遗传算法 浙江工业大学硕士学位论文 r e l i a b l er o u t i n g a l g o r i t h m sb a s e do hn e t w o r kc o d i n g i nw i r e l e s sn e t w o r k s a b s t r a c t t o d a y , w i r e l e s sn e t w o r ki so n eo ft h em o s tp o p u l a rt e c h n o l o g i e sa n dh a v eb e e nw i d e l y a p p l i e d w i t ht h ed e v e l o p m e n to fw i r e l e s sc o m m u n i c a t i o n sa n dw i r e l e s sd e v i c e s 谢t hp o w e r f u l f u n c t i o n s ，a p p l i c a t i o n so fw i r e l e s sn e t w o r k sa r el a r g e l ye x t e n d e dt ol a r g e ra r e a s ，i n c l u d i n g m i l i t a r ya n dc i v i l i a no n e s a sar e s u l t ，i ti si n d i s p e n s a b l ef o ru st om a k ea r d u o u se f f o r t si nt h e a r e a sr e l e v a n tt ow i r e l e s sn e t w o r k s r o u t i n gt e c h n o l o g yi so n eo ft h ek e yi s s u e si nt h es t u d yo fw i r e l e s sn e t w o r k s of a r , a n u m b e ro fe f f e c t i v er o u t i n ga l g o r i t h m sw e r ep r o p o s e db a s e do nv a r i o u se n v i r o n m e n t sa n d a p p l i c a t i o n sa n dr e q u i r e m e n t s ，e g ，e n e r g ye f f i c i e n tr o u t i n g ，r e a lt i m er o u t i n g ，s e c u r er o u t i n ge r e u n l i k et r a d i t i o n a lw i r e dn e t w o r k ，b e c a u s ew i r e l e s sn e t w o r kt r a n s m i ti n f o r m a t i o nt h r o u g ht h e w i r e l e s sc h a n n e l ，s u b j e c tt oe n v i r o n m e n t a lc h a n g e ，r a d i oc h a n n e li n t e r f e r e n c e ，n o d ef a i l u r e sa n d o t h e rf a c t o r s ，r e s u l t i n gi np a c k e tl o s si nw i r e l e s sn e t w o r k ，s oi ti si m p o r t a n tt oe n s u r ep a c k e t sb e t r a n s m i t t e dr e l i a b l y t h i sd i s s e r t a t i o ns t u d yr e l i a b l ed a t at r a n s f e ri s s u e si nl o s s yw i r e l e s sn e t w o r k ， f o c u s i n go nt h er e l i a b l ed a t ad e l i v e r yp r o b l e m ss u p p o r t e db yn e t w o r kc o d i n g ( n c ) n e t w o r kc o d i n gi sam a j o rb r e a k t h r o u g hi nt h ef i e l do fc o m m u n i c a t i o n si nr e c e n ty e a r s ，t h e b a s i ci d e ao fn e t w o r kc o d i n gi st h a tn o d e si nn e t w o r kn o to n l yf o r w a r dd a t ap a c k e t st h a tt h e y h a v er e c e i v e d ，b u ta l s oi n v o l v e di nd a t ap r o c e s s i n g w n e t w o r kc o d i n g ，t h eo r i g i n a ld a t a r e c o v e rd o e sn o td e p e n do nas i n g l es p e c i f i cd a t ap a c k e t i no t h e rw o r d s ，a sl o n ga st oe n s u r et h a t as u f f i c i e n tn u m b e ro fd a t ap a c k e t sr e a c ht h ed e s t i n a t i o nn o d e ，e v e nw h e ns e v e r a l p a c k e t sw e r e l o s ti nt h ep r o c e s so fd a t at r a n s m i s s i o n ，i tw i l ln o ta f f e c tt h ed e s t i n a t i o nn o d et or e c o v e ro r i g i n a l d a t as u c c e s s f u l l y b a s e do nn e t w o r kc o d i n g ，ar e t r a n s m i s s i o n - f r e er o u t i n g ( r f r ) a l g o r i t h mi s p r o p o s e di nt h i sd i s s e r t a t i o n , i nw h i c ha no p t i m i z a t i o nm o d e lt h a tm i n i m i z e se n e r g yc o s tp e rb i t o fu s e f u ld a t ai sp r e s e n t e da n ds o l v e db yg e n e t i ca l g o r i t h m s i na d d i t i o n ，n u m e r i ce x p e r i m e n t s a r ec o n d u c t e dt oi n v e s t i g a t et h ei m p a c t so fv a r i o u sp a r a m e t e r so ne n e r g yc o s t so ft h er f r ， m o r e o v e rw ec o m p a r et h er f rw i t hr o u t i n ga l g o r i t h m so fm a x i m u mr e l i a b l ep a t hf i r s t ( m r p f ) a n ds h o r t e s tp a t hf i r s t ( s p f ) t h i sr e s e a r c hc a r lb ea p p l i e dv a r i o u sw i r e l e s sn e t w o r k si n c l u d i n g i e e e8 0 2 1 1 i e e e8 0 2 1 5a n di e e e8 0 2 1 6 - i i - 浙江工业大学硕士学位论文 k e yw o r d s ：w i r e l e s sn e t w o r k ，r o u t i n g ，n e t w o r kc o d i n g ，g e n e t i ca l g o r i t h m 浙江工业大学 学位论文原创性声明 本人郑重声明：所提交的学位论文是本人在导师的指导下，独立进行研究工作 所取得的研究成果。除文中已经加以标注引用的内容外，本论文不包含其他个人或 集体已经发表或撰写过的研究成果，也不含为获得浙江工业大学或其它教育机构的 学位证书而使用过的材料。对本文的研究作出重要贡献的个人和集体，均已在文中 以明确方式标明。本人承担本声明的法律责任。 作者答名：幸中日翌干m 诉 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学校保留 并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。本 人授权浙江工业大学可以将本学位论文的全部或部分内容编入有关数据库进行检 索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。 本学位论文属于 1 、保密口，在年解密后适用本授权书。 2 、不保密回。 ( 请在以上相应方框内打“”) 作者签名： 导师签名： 日期 日期 年，7 月刁日 年jy 月杉日 浙江工业大学硕士学位论文 第一章绪论 无线网络的节点以无线通信方式进行数据传递。近十年来，随着无线通信技术和便携 设备的飞速发展，无线网络在军事、医疗、家庭等各个方面得到十分广泛的应用，并逐步 进入人们生活的各个领域。不同于传统的有线网络，无线网络在可扩展性、可移动性等方 面均有着显著的优势，可作为传统有线网络的有益补充。然而，无线网络在安全性、可靠 性、吞吐量等方面存在着许多不足。为了更好地使用无线网络，近年来很多应用于不同场 合和要求的路由算法被提出来，其中，利用无线信道的特性以保证数据传递的可靠性路由 算法在无线网络中显得格外重要，有着广阔的应用前景。 1 1无线网络及其路由技术 1 1 1 无线网络简介及分类 自从1 8 9 6 年g u g l i e l m om a r c o n i 发明了无线电【1 】以来，无线通信因其便捷、灵活等特点 逐步进入了人们的视界。特别是近十年来，由于无线通信技术迅猛发展以及手提电脑、个 人数字助理( p d a s ，p e r s o n a ld i g i t a la s s i s t a n t s ) 、移动电话等相关无线设备日新月异，无线 网络得到了飞速发展，并且已广泛应用于军事、医疗、野外搜救、公共交通等各个领域。 例如：我们可以在机场、咖啡吧、图书馆等地通过无线网络浏览i n t e r n e t 、收发电子邮件等， 可以利用无线传感器网络监测环境、探取情报等等，利用车载全球定位系统( g p s ，g l o b a l p o s i t i o n i n gs y s t e m ) 浏览地图并进行定位等等。 在传统的蜂窝网络的基础上，一种被称为无线接入点( a p ，w i r e l e s sa c c e s sp o i n t ) 的 硬件设备正被越来越多的使用【2 】，便携设备可以通过接入点访问i n t e m e t 。 目前，存在着各种各样不同的无线网络，我们可以根据一些不同的方法( 如根据网络 结构或通信范围) 对其进行分类。 根据网络结构分类 浙江工业大学硕士学位论文 ( 1 ) 基于基础设施网( i n f r a s t r u c t u r e b a s e dn e t w o r k s ) 所谓基于基础设施的网络指的是在预先架设完成的基础设施( 如基站、路由器等) 之 上形成的无线网络。网络的运行要依赖于这些基础设施。例如，传统的蜂窝网络就是典型 的基于基础设施的无线网络，它是由公共交换电话网( p s t n ，p u b l i c s w i t c h e dt e l e p h o n e n e t w o r k ) 、移动交换中心( m s c s ，m o b i l es w i t c h i n gc e n t e r s ) 、基站以及移动终端所组成的。 ( 2 ) 无基础设施网( i n f r a s t r u c t u r e l e s sn e t w o r k s ) 所谓无基础设施网是指无线设备节点通过相互协调组成的一种动态无线网络，网络的 形成事先并没有相应的基础设施( 如基站、路由器等) 。在无基础设施无线网络中，节点 可以作为中继节点协助其他节点进行数据传递。典型的无基础设施无线网有移动自组织网 络( m m 怔t s ，m o b i l ea dh o en e t w o r k s ) 和无线传感器网( w s n s ，w i r e l e s ss e n s o rn e t w o r k s ) 。 由于无基础设施网在灵活性、实用性等很多方面有其显而易见的优势，使得该类网络有广 泛的应用场合及巨大的研究价值。由于该类网络为动态结构且非常复杂，使得它成为国内 外学者的研究热点，本文的研究主要也是针对该类网络。 根据通信范围分类 和传统的有线网络类似，无线网络也可以根据无线通信可涉及的范围大小进行分类。 ( 1 ) 无线广域网( 懒n s ，w i r e l e s sw i d e a r e an e t w o r k s ) 无线广域网是一类基于基础设施的无线网络，移动终端用户通过基础设施能和遥远的 网络建立联系。这种联系可以跨域很长的地理位置，例如城市之间或国家之间。典型的无 线广域网有蜂窝网络、卫星网络等等。 ( 2 ) 无线城域网( w m a n s ，w i r e l e s sm e t r o p o l i t a n a r e an e t w o r k s ) 无线城域网也是一种基于基础设施的无线网络，其允许用户在城市范围内的多个位置 建立无线宽带连接而省去了铺设光纤或电缆的昂贵费用。无线电波和红外线均可用来在无 线城域网中传输数据。i e e e ( t h eu s i n s t i t u t eo f e l e c t r i c a la n de l e c t r o n i c se n g i n e e r s ) 也为 支持无线城域网的使用和发展制定了无线宽带接入标准i e e e8 0 2 1 6 。 ( 3 ) 无线局域网( w l a n s w i r e l e s sl o c a l a r e an e t w o r k s ) 无线局域网是指用户在一个局部区域建立的无线网络，通常该局部区域指的是公司内、 校园建筑内或类似于机场的公共场所等连接范围在1 0 0 米内的无线网络。无线局域网既可 以是基于基础设施的网络也可以是无基础设施的网络，典型的无线局域网包括i e e e8 0 2 1 1 ( 也称为w i f i ) 和h i p e r l a n 2 等。 ( 4 ) 无线个域网( w p a n s ，w i r e l e s sp e r s o n a l a r e an e t w o r k s ) 浙江工业大学硕士学位论文 无线个域网下，用户使用个人数字助理、蜂窝电话或手提电脑等个人无线设备与其它 的个人无线设备相互直接通信。无线个域网是种无基础设施的网络，其连接范围大致在 1 0 米以内。蓝牙( b l u e t o o t h ) 和红外线是无线个域网的主要两种类型。无线个域网的运用 往往有复杂度低、低耗能登特点，而且能与i e e e 8 0 2 1 1 网络兼容。 作为无基础设施的无线网络，移动自组织网络( m a n e t s ) 和无线传感器网络( w s n s ) 因其具有极高的应用价值和复杂的网络结构，正成为无线网络领域中研究的重点。 移动自组织网络【2 】是一种没有预定基础设施支撑的自组织可重构的多跳无线网络，每 个节点既为主机又是传递其它节点数据的路由节点，在该网络中，网络的拓扑、信道的环 境、业务的模式随节点的状态而动态改变。由于自组织网络的低配置和快速布置等特点， 其经常应用于军事冲突、自然或人为灾难、紧急医学状况等场合。移动自组织网络具有如 下显著特点： ( 1 )网络拓扑结构动态变化：移动自组织网络中，用户终端的移动具有很大的随机 性，加上无线发射装置发送功率的变化，无线信道间的互相干扰以及地形等综合因素的影 响，网络的拓扑结构可能随时发生变化，而且这种变化的方式和速度难以预测。 ( 2 )采用分布式控制方式：在移动自组织网络中，不设专门的控制中心，把网络的 控制功能分散配置到各节点，网络的建立和调整是通过各节点的有机配合实现的。即移动 自组织网络均衡了网中各节点的特殊性和重要性，从控制能力上看，各节点没有重要和次 要之分，从而可防止一旦控制中心被破坏而引起全网瘫痪的危险，提高了网络的抗毁性。 ( 3 ) 具有自组织性：移动自组织网络不依赖基础设施的支持，网中各节点能相互协 调的遵循一种自组织原则，自动探测网络的拓扑信息，自动选择传输路由，自动进行控制， 把网中所有节点组成一个有机整体。即使网络发生动态变化或某些节点严重受损时，仍可 迅速调整其拓扑结构以保持必要的通信能力。 ( 4 )多跳通信：由于通信距离受限，移动自组织网络内的节点间的通信往往是借助 其他节点的中继转发而实现的，即要经过多跳。与普通网络中的多跳不同，自组网多跳是 由普通节点，而不是由控制中心完成的。 ( 5 ) 节点的处理能力和能源受限：移动自组织网络中的节点通常具有轻便灵巧，便 于携带的特点，但它们以电池这样的易耗尽能源作为电源，并且c p u 性能较低、内存较小， 这就给应用程序的设计和开发带来一定难度。 ( 6 )信道质量较差：移动自组织网络采用无线传输技术作为物理层通信手段。无线 信道由于其本身的物理特性，如衰减大、干扰大、多路径效应等，信道质量比有线信道差 浙江工业大学硕士学位论文 得多。并且由于多个节点分布式竞争使用信道，使得每个节点实际使用的带宽远小于物理 层提供的最大传输速率。 ( 7 )安全性面临挑战：移动自组织网络由于采用无线信道、分布式控制等技术，更 容易受到被动窃听、主动入侵、拒绝服务、剥夺“睡眠”、信息阻塞、信息假冒等各种方 式的攻击。由于终端电源有限，移动自组织网络无法实现复杂的加密算法，增加了被窃密 的可能性。移动自组织网络由节点自身充当路由器，不存在服务器等网络设施，也不存在 网络边界的概念，这使得自组网中的安全问题非常复杂，传统网络中的安全策略和机制不 再适用。 由于移动自组织网络的特殊性使得其在体系结构、网络组织、协议设计等方面都与现 有的无线通信系统( 如蜂窝移动通信系统和无线局域网) 有着显著的区别。 无线传感器网络是一种特殊的无线网络，由部署在观测环境附近大量的廉价的微型传 感器节点组成，并通过无线通信方式形成的一个多跳的自组织网络系统，其将监测数据汇 集到基站( s i n k ) ，目的是协作地感知、采集和处理网络覆盖区域中感知对象的信息，并发 送给观察者( s i n k ) 。传感器、感知对象和观察者构成了传感器网络的三个要素【2 】。作为一 种无处不在的感知技术，无线传感器网络已经广泛应用于各个领域。 虽然无线传感器网络对于不同的应用场合有不同的特点，但是它具有以下共同特性 【5 3 】： ( 1 ) 服务类型：传统通信网络提供的服务类型是将信息从一个位置传输到另一个位置。 而对于传感器网络来说，这并不是最终目的，需要进一步指定任务的有用信息与或作用。 因此相互之间的时空范围，具体地理位置，或者时间间隔之类的概念变得尤为重要。 ( 2 ) 服务质量：与网络的服务类型密切相关的是服务质量。在有些特殊的应用场景， 有限的延迟时间、足够的带宽等服务质量必须在特定的条件下满足。 ( 3 ) 容错性：由于节点能量的耗尽、节点损坏、节点之间通信不对称等可能使网络正 常进行通信，可以使网络容许在节点出现异常时，网络还能够继续正常运行。 ( 4 ) 寿命：网络的使用寿命往往与服务质量是矛盾的，投入更多的能量可以提高服务 质量但是减少了工作寿命。网络寿命取决于具体应用，一般来说是把第一个节点失效的时 间作为网络寿命。有些认为5 0 的节点失效或者所有节点失效时间定义为网络寿命。 ( 5 ) 可观测性：由于一个w s n 可能包括大量的节点，所以采用的结构和协议必须能够 观测这些节点。 ( 6 ) 较宽的密度变化范围：在w s n 当中，每单位面积的节点数目( 网络密度) 变化比较大。 浙江工业大学硕士学位论文 应用不同，节点密度也不同。在整个网络，密度往往是不统一的，这就需要协议能够适应 这种变化。 ( 7 ) 可编程性：节点能够处理消息，而且节点能够对任务的变更做出相应的反应，因 此这些节点应该是可以编程的。 ( 8 ) 可维护性：当w s n 自身发生变化时，系统能够适应新的状况。从这一点来讲，网 络可以自我修复，同时网络可以与外部维护机制作用。 1 1 2 无线网络的路由技术 如前所述，无线网络( 包括移动自组织网络和无线传感器网络等) 1 具有广阔的应用前 景，吸引了越来越多网络研究人员的关注。由于无线网络自身的特点及电源、发射功率小 等限制，网络中的节点需要其它节点的协助将数据传递到目的节点，即网络通信呈现为多 跳的形式，因此，路由对无线网络有效运行是必不可少的。同时，根据不同的网络环境和 不同的系统需求，网络的路由表和路由协议的设计成了无线网络的关键和研究热点。 常见的无线网络路由技术有以下几类：传统路由技术、以吞吐量为目标的路由技术、 以能量有效性为目标的路由技术和以实时性等为目标的q o s 路由技术，等等。 1 1 2 1 传统路由技术 所谓传统的无线网络路由技术是指在较早期提出的针对于无线自组织网络或无线传感 器网络的经典、简单的路由算法。 f l o o d i n g 7 协j , s l f f t i g o s s i p i n g 8 协议。这是两个最为经典和简单的无线网络路由协议， 可应用到无线网络中。在f l o o d i n g 协议中，节点产生或收到数据后向所有邻节点广播，数 据包直到过期或到达目的地才停止传播。该协议具有严重缺陷：内爆节点几乎同时从 邻节点收到多份相同数据、交叠节点先后收到监控同一区域的多个节点发送的几乎相 同的数据、资源利用盲目节点不考虑自身资源限制，在任何情况下都转发数据。 g o s s i p i n g 协议是舜j f l o o d i n g 协议的改进，节点将产生或收到的数据随机转发，避免了内爆， 但增加了时延。这两个协议不需要维护路由信息，也不需要任何算法，虽然简单易实现， 但扩展性很差。 s p i n ( s e n s o rp r o t o c o l sf o ri n f o r m a t i o nv i an e g o t i a t i o n ) 9 也是一个经典、简单的路由协议， 在文章以下部分，如无特别指出，无线网络均指移动自组织网络和无线传感器网络 一5 - 浙江工业大学硕士学位论文 它是第一个基于数据的路由协议。该协议以抽象的元数据对数据进行命名，命名方式没有 统一标准。节点产生或收到数据后，为避免盲目传播，用包含元数据的a d v 消息向邻节点 通告，需要数据的邻节点用r e q 消息提出请求，数据通过d a t a 消息发送到请求节点。与 f l o o d i n g 7 和g o s s i p i n g 8 协议相比，能够很好地解决先前两个协议所带来的信息爆炸、 信息重复和资源浪费等问题，有效地节约了能量。d i r e c t e dd i f f u s i o n 协议【1 5 1 是一个重要的 基于数据的i 查询驱动的传统路由协议。为建立路由，s i n k 点通过洪泛方式广播包含属性 列表、上报间隔、持续时间、地理区域等信息的查询请求i m e r e s t ( 该过程本质上是设置一 个监测任务) 。沿途节点按需对各i n t e r e s t 进行缓存与合并，并根据i n t e r e s t 计算、创建包含数 据上报率、下一跳等信息的梯度( g r a d i e n t ) ，从而建立多条指向s i n k 点的路径。i n t e r e s t 中的 地理区域内节点则按要求启动监测任务，并周期性地上报数据，途中各节点可对数据进行 缓存与聚合。s i n k 点可在数据传输过程中通过对某条路径发送上报间隔更小或更大的 i n t e r e s t ，以增强或减弱数据上报率。 1 1 2 2 以网络吞吐量为目标的路由技术 由于无线网络通过无线电波、红外线等无线介质进行数据传输，与传统的光纤、电缆 等有线介质比较在传输带宽上存在很大的不足，尤其在长距离传输中，该缺陷更为突现， 所以相对于有线网络，无线网络在提高网络的吞吐量上有更迫切的要求和更高的研究价 值。通过一定路由技术来使无线网络满足所需的吞吐量是无线网络路由技术研究的一个重 要方向。 a g u a y o 等人针对于多跳无线网络提出一种e t x ( e x p e c t e dt r a n s m i s s i o nc o u n t ) 方案 4 】， 该方案通过最小化使数据能成功传递到目的节点的总的数据包数的期望值来提高网络的 吞吐量，e t x 路由方案也同时考虑了无线链路的失效概率。l u c i a n 等人针对于p 2 p 无线网络 提出了一种“c u r v e b a l l 路由算法【5 】，在该路由算法中，作者通过将节点看作为布置于曲 面球体表面的方式，计算出较优的数据传递的路径，从而平衡网络流量，避免拥塞以提高 网络的吞吐量。 1 1 2 3 以能量有效性为目标的路由技术 当便携设备能够在“任何地点、任何时间”被布置使用并形成无线网络时，无线网络 才能体现出最大的利用价值。由于网络节点通常由电池提供能源，能量非常有限，而且通 常不可替换，所以如何进行能量控制是当今无线网络中的主要挑战【6 】。以下是部分典型的 6 浙江工业大学硕士学位论文 能量有效路由算法，主要涉及的是针对无线传感器网络的能量有效路由，本文以平面路由 与分层路由分别阐述。 ( 1 ) 平面路由 平面路由中所有节点具有相同的地位和功能，节点间协同工作完成感知任务。平面路 由的优点是结构简单、鲁棒性较好。 s h a h 等人提出了能量感知路由协议 1 6 】，该协议的目的主要在于改善d i r e c t e dd i f f u s i o n 协议 1 5 】的耗能情况，采用地理位置和数据类型( 即节点类型) 标识节点。与d i r e c t e d d i f f u s i o n 1 5 相比，该协议虽然存在多条路径，但只选用一条，能够有效节约能源4 0 以上， 随机选择路由方式平衡了通信量。其缺点是，s i n k 点需要周期性以洪泛方式广播维护路由 信息，需要进行节点间收发开销和剩余能量测量，根据概率随机选择一条路径导致其可靠 性不如d i r e c t e dd i f f u s i o n 协议 1 5 1 。 c h a n g 等人提出了最大化生存时间路由协议 1 7 】，该协议与s h a h 等人的思想 1 6 1 有相似 之处，认为最小化传输能量并不完全适合于无线传感器网络类的无线网络，必须考虑网络 的生存时间。它根据节点剩余能量与链路发送数据能量要求定义代价函数，该协议最重要 的贡献在于：利用网络流建模，采用线性规划方法来解决最大生存时间问题。 平面路由的最大缺点在于：网络中无管理节点，缺乏对通信资源的优化管理，自组织 协同工作算法复杂，对网络动态变化的反应速度较慢等 1 0 】。 ( 2 ) 网络分层路由 分层路由又称分簇路由( c l u s t e r - b a s e dr o u t i n g ) ，在分簇路由协议中，网络通常被划分 为簇( c l u s t e r ) 。所谓簇，就是具有某种关联的网络节点集合。每个簇由一个簇头( c l u s t e rh e a d ) 和多个簇内成员( c l u s t e rm e m b e r ) 组成，低一级网络的簇头是高一级网络中的簇内成员，由 最高层的簇头将数据发送到汇聚节点。一般分簇路由算法大致可以划分为以下三个步骤： 簇头的产生、簇的形成以及簇间的数据传递。 l e a c h 1 l 】协议是为无线传感器网络设计的一种低功耗自适应分层路由协议。其基本 思想是：通过等概率地随机循环选择簇头，将整个网络的能量负载平均分配到每个传感器 节点，从而达到降低网络能量耗费、延长网络生存周期的目的。在h e e d ( h y b r i d e n e r g y e f f i c i e n td i s t r i b u t e dc l u s t e r i n g ) 1 2 1 = 簇头的选择主要依据主、次两个参数。主参数依 赖于剩余能量，用于随机选取初始簇头集合。具有较多剩余能量的节点将有较大的概率暂 时成为簇头，而最终该节点是否是簇头取决于剩余能量是否比周围节点多，次参数依赖于 簇内通信代价，用于确定落在多个簇范围内的节点最终属于哪个簇，以及平衡簇头之间的 浙江工业大学硕士学位论文 负载。在这基础之上，为了平衡各个簇之间的能量消耗，又相继提出了一些非均匀分簇算 法，具有代表性的是e e c s ( e n e r g ye f f i c i e n tc l u s t e r i n gs c h e m e ) j 1 3 其主要思想是通过一个消 耗函数，该函数根据与基站的距离设置不同的簇头的簇半径，从而形成不同尺寸的簇，用 于平衡簇头将数据传递到基站所产生的簇间的能量差异。 分簇路由机制具有以下几个优点 1 4 1 ： a ) 成员节点大部分时间可以关闭通信模块，由簇头构成一个更上一层的连通网络来 负责数据的长距离路由转发。这样既保证了原有覆盖范围内的数据通信，也在很 大程度上节省了网络能量，且降低了节点之间的无线通信干扰； b ) 簇头融合了成员节点的数据之后再进行转发，减少了数据通信量，从而节省了网 络能量； c ) 成员节点的功能比较简单，无须维护复杂的路由信息。这大大减少了网络中路由 控制信息的数量，减少了通信量； d ) 分簇拓扑结构便于管理，有利于分布式算法的应用，可以对系统变化作出快速反 应，具有较好的可扩展性，适合大规模网络； e ) 与平面路由相比，更容易克服传感器节点移动带来的问题。 1 1 2 4 以实时性等为目标的o o s 路由技术 无线网络己广泛应用于军事、民用等各个领域，在一些特定的应用领域和场合，对网 络的实时性等网络的服务质量( q o s ，q u a l i t yo f s e r v i c e ) 方面有着特殊的要求。相应的，一些 针对于提高网络q o s 的路由技术也被提出来。相对于传统有线网络，无线网络在如何保证 网络的服务质量上有着更大的挑战【1 9 】。 s a r 1 8 协议是第一个在无线传感器网络中保证q o s 的主动路由协议。s i n k 点的所有一 跳邻居节点都以自己为根创建生成树，在创建生成树过程中考虑节点的时延、丢包率等q o s 参数以及最大数据传输能力，各个节点从而反向建立了至l j s i n k 点的具有不同q o s 参数的多条 路径，节点发送数据时选择一条或多条路径进行传输。该协议能够提供q o s 保证，但缺点 是节点中的大量冗余路由信息耗费了存储资源，且路由信息维护、节, 点q o s 参数与能耗信 息的更新均需较大开销。 洪泛( f l o o d i n g ) 技术也是一种能提供网络服务质量的有效技术【2 0 】，其能通过在整个 网络中洪泛广播路由搜索信息寻找满足q o s 要求的路径。在该种技术中，中继节点转发接 收到的满足q o s 要求的路由搜索信息，直到目的节点接收到一个搜索信息时，则一条满足 8 浙江工业大学硕士学位论文 q o s 的路径建立。在【2 1 】 2 2 】提出的路由算法中，作者使用了该技术建立了相应的q o s 要求 的路由。 1 2 网络编码及其应用 网络编码( n e t w o r kc o d i n g ) 【2 3 技术自从被提出后，就得到了研究人员的足够重视， 当网络编码被应用到无线网络环境后，在网络的吞吐量、可靠性等很多方面都得到了很高 的收益。 1 2 1网络编码的提出及基本思想 在组播通信的网络中，采用传统路由的方法无法确保信息传输速率达到最大流最小割 定理所确定的信源和信宿间的最大流量。针对组播通信网络中存在的这一局限，2 0 0 0 年， a h l s w e d e 等人 2 3 】发表了一篇题为“网络信息流”的文章，为提高组播网络的传输流量展 现了一个新的方向。他们从信息论的角度出发，证明了在单点对多点的组播通信网络中， 通过在节点进行编码的方式可使信息传输速率达到网络的最大流量。从此以后，研究人员 对网络编码引起了广泛的兴趣，并在网络的相关理论和实际应用中都产生了深刻的影响。 通过网络编码，网络中的节点不仅可以参与数据的发送与接收，还可以根据具体的情 况对数据进行编码操作，摆脱了以往对于数据流类似物流进行传送的理念。在网络编码这 种技术下，网络的吞吐量、可靠性、安全性以及能耗等方面较传统技术都有了很大的提升 余地。近期对于网络编码的研究主要在移动自组织网络( m o b i l ea dh o cn e t w o r k s ) 、无线 传感器网络( w i r e l e s ss e n s o rn e t w o r k s ) 以及无线网状网络( w i r e l e s sm e s hn e t w o r k s ) 等 无线网络中。 以下是网络编码简单的一个例子： 浙江工业大学硕士学位论文 一睾 ( a ) 传统模式( b ) 网络编码模式 图1 1 网络编码例子 如图1 1 所示，在传统模式中，如果节点a 通过中间节点r 将数据分组a 发送到节点b ， 节点b 通过中间节点r 将数据分组b 发送至节点a ，则完成所有的工作需要4 次数据分组在链 路上的传递过程，其中数据分组a 的传递有a 专r ，r 专b 两次，数据分组b 有b - - ) r ，r 专a 的 两次传递。在网络编码模式中，当中间节点r 在接收到分别来自于节点a 和b 的数据分组a 、 b 后，首先将a 和b 作“异或( x o r ) 处理，然后将处理后的结果进行广播发送，当节点a 和b 接收到来自节点r 的广播数据后，再与各自原有的数据包作“异或( x o r ) 处理，就 能得到各自所需的结果。在使用了网络编码后，完成数据分组羽b 的传递，在增加了一定 量的运算下，只用了3 次链路传递，从而大大减少了发送次数，提高了网络的吞吐量。可 以看到，无线网络编码充分利用了广播作为无线通信固有的内在特性以及数据流和普通物 流的本质区别，提高了网络的吞吐量。 1 2 2 网络编码的应用与发展 考虑到线性方式编码的简单性和实用性，l i ，y e u n g 和c a i 等人提出了线性网络编码 2 4 】， 并构造了使得组播网络达到最大流量的线性编码方式，证明了线性网络编码的最优性。这 一工作奠定了线性网络编码的理论和应用基础，引起了更多人对网络编码的注意和研究。 网络编码思想突破了传统数据传输类似物流形式的模式，带来了针对不同网络场景和 应用的许多潜在优点： 首先，与传统的路由方式进行数据传输相比，网络编码可大大提高网络的信息传输的 流量，这也是y e t m g 提出网络编码的主要意图。如，在有向图网络中，【5 5 】一文利用网络编 码提高了网络的数据流量，文献 5 6 1 1 5 7 1 通过网络拓扑图仿真也表明编码可有效地提高组播 网络的流量：在无向图网络中，文献 5 4 】证明了网络编码比传统的路由最多能提高两倍的 浙江工业大学硕士学位论文 网络数据流量。 以下是网络编码提高网络吞吐量的经典的例子 2 4 1 = s 1 s 2 s l s 2 r 1 r 2 r 1 ( a ) 传统路由( b ) 网络编码路由 图1 2 网络编码提高吞吐量 图l 一2 所示的蝴蝶网络是网络编码实现多播最大容量的经典例子。如图所示，源节点s 1 和s 2 分别组播1 比特数据a 和b 到目的节点r l 和i 匕，假设各链路的容量为1 。图1 - 2 ( a ) 中采用 的是传统路由方法，即节点c 一次只能传送l 比特到节点d ，节点d 也只能传送1 比特到节点 e 和f ，为了使棚b 均能到达r l 和r 2 ，节点c 和d 之间的链路不得不使用了两次，平均速率 是l 比特单位时间；图1 2 ( b ) 采用网络编码方法，节点c 对输入信息流进行编码，将编码的 结果a 和b 的异或值( 记为aob ) 传送到节点d ，再传送给节点e 和f 。节点e 根据自身已收到的 信息a 和a o b ，可以通过a o ( a o b ) = b 的方法解码出b 。同样，节点f 也能解码出完整的信息， 这样所能达到的平均速率是2 比特单位时间。在本例中，采用网络编码使得每条链路只使 用了一次，这样既使得网络负载比较均衡，又节省了传输次数，同时减小了网络时延，增 大了网络吞吐量。 其次，网络编码可增加网络通信的鲁棒性( r o b u s t n e s s ) 。由于经过网络编码后的数据包 具有同等的重要性，因此只要当信宿接收到了足够多的编码后的数据包，就可以利用这些 数据包正确地还原出所需的原始数据。这样，当部分节点处于休眠或“死亡 状态而停止 发送消息时，或者当网络中有部分的数据包丢失的情况下，只要有足够的节点和通信链路 保证有足够多的数据包到达信宿，网络通信仍可正常进行。 还有，网络编码可充分利用网络上的信道，使数据传输普适化( u n i v e r s a l ) 。直观地说， 浙江工业大学硕士学位论文 在单个信源的组播网络中进行适当的编码，可使每一个节点从信源节点所收到的信息量达 到信源节点到该点的最大流。这给我们带来的好处包括：在构造网络编码时不需知道信息 接收者在网络中的具体位置；即使在从信源到某一节点的最大流量小于信源的信息率的情 况下，在该节点的用户也可以收到信源所产生的消息的部分信息，这样此用户就可以利用 这部分信息对信源消息作满足一定条件的编码或译码。 最后，当网络编码应用于无线通讯网络时 2 7 】【3 0 5 8 】【5 9 】( 6 0 】【6 1 】【6 2 】，不仅可以提高信 息传输率，节约传输所需能量，而且可以使节点之间在所需能量方面进行平衡( t r a d e o f f ) 6 1 1 1 6 2 1 。值得指出的是，在文献 6 3 1 q b 提出了一个在无线a dh o c 组播网络上求得最小能量 编码的多项式时间算法，然而，构造这种组播网络的路由算法所用的最小能量组播树 ( m i n i m u m e n e r g ym u l t i c a s tt r e e ) 构造是n i p 难问题。 综上，网络编码可广泛地应用在各种实际网络上，并可带来传统路由方式无法实现的 效益。 1 2 3 网络编码的热点研究领域 自从网络编码提出之后，网络编码在很多领域都得到了深入研究。“等人在组播网络 中证明了利用线性网络编码能够达到理论