（控制理论与控制工程专业论文）无线网状网络的路由算法研究(1).pdf

摘要 摘要 无线网状网络( w i r e l e s sm e s hn e t w o r k s ，w m n s ) 在家庭宽带网、企业网、 城域网、楼宇自动化以及智能交通系统中都有着广泛的应用前景并已经成为下一 代无线网络的研究热点。 其中采用何种策略进行路由选择以使网络吞吐量最大成为目前研究的关键问 题。本文分析了现有的无线网状网络路由选择策略，并在此基础上综合考虑了跳 数、信道质量、链路间的多信道必然干扰以及潜在干扰，提出了一种新的路由尺 度。仿真表明，该方法能够显著地提高网络吞吐量。 关键词：无线网状网络无线自组织网络路由协议路由尺度网络吞吐量 w i r e l e s sm e s hn e t w o r k s ( w m n s ) i sap r o m i s i n gw i r e l e s st e c h n o l o g yf o rn u m e r o u s a p p l i c a t i o n s ，e g b r o a d b a n dh o m en e t w o r k i n g ，e n t e r p r i s en e t w o r k i n g ，m e t r o p o l i t a na r e a n e t w o r k s ，b u i l d i n ga u t o m a t i o na n di n t e l l i g e n c et r a n s p o r t a t i o ns y s t e m se t c i th a s b e c o m i n gar e s e a r c hh o t s p o tf o rt h en e x tg e n e r a t i o nw i r e l e s sn e t w o r k s b a s e do nt h ec h a r a c t e r i s t i c so fw m n s ，t h er o u t i n gs e l e c t i o ns t r a t e g i e sa d o p t e dt o m a x i m i z et h en e t w o r kt h r o u g h p u th a sb e c o m eak e yi s s u eo fw m n s b a s e do nt h e a n a l y s i so fe x i s t i n gw m n s m u t i n ga l g o r i t h m ，an e wr o u t i n gm e t r i ci sp r o p o s e dw h i c h i n t e g r a t e st h ec o n s i d e r a t i o no ft h eh o pc o u n t s ，q u a l i t i e so fc h a n n e l ，t h ei n e v i t a b l ea n d p o t e n t i a lm u l t i - c h a n n e li n t e r f e r e n c ea m o n g l i n k s i ti sd e m o n s t r a t e di nt h es i m u l a t i o n t h a tt h ea l g o r i t h mc a ni m p r o v et h en e t w o r kt h r o u g h p u tg r e a t l y , k e y w o r d ：w i r e l e s sm e s hn e t w o r k s w i r e l e s s a dh o cn e t w o r k s r o u t i n gp r o t o c o l r o u t i n gm e t r i cn e t w o r k t h r o u g h p u t 独创性声明 y 8 5 8 6 5 0 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研究 成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不 包含其他人已经发表或撰写过的研究成果；也不包含为获得西安电子科技大学或 其它教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做 的任何贡献均已在论文中做了明确的说明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切相关责任。 本人签名 日期 ：2 0 0 c j ，。 关于论文使用授权的说明 本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：研究 生在校攻读学位期间论文工作的知识产权单位属西安电子科技大学。本人保证毕 业离校后，发表论文或使用论文工作成果时署名单位仍然为西安屯子科技大学。 学校有权保留送交论文的复印件，允许查阅和借阅论文；学校可以公布论文的全 部或部分内容，可以允许采用影印、缩印或其它复制手段保存论文。 本人签名：日期兰：! ! ! 导师签名：么查! ! 垂匕日期竺竺! ：2 第一章绪论 第一章绪论 1 1 课题背景 1 9 9 7 年，美国d a r p a 开始组织战场鲁棒战术移动通信系统的研发。在投入 大量资金、持续6 年多的研发之后，有关移动a dh o c 网络的一些理论与技术问题 得以解决，从而彻底改变了过去构建无线网络的规则。d a r p a 的目标是：无传统 的通信基础设置；采用多跳转发的传输机制；宽带数据数率传输：端到端的i p 支 持；除了数据业务以外，还要支持话音和视频业务；内置定位系统( 非g p s 系统) ； 能支持高达2 5 0 英里，j 、时的车辆移动速度等。特别是近几年，美国通过一些大型 国防项目，攻克了a dh o e 网络的一些关键技术，其中，t 持有了其中的核心的 自主知识产权技术。可是，除了战术无线通信以外，真正的商业应用在那里? 这是 业界一直困惑的一个问题。2 0 0 0 年初，丌t 将专有技术转让给了美国 m e s h n e t w o r k s ，用于商业化产品的开发，至此，a dh o e 网络的商业化进程开始显 现。2 0 0 2 年，i n t e l 开始关注并认可a dh o c 网络技术，m e s h n e t w o r k s 和t r o p o s 等 公司开始相继开发出适用于商业应用的相关产品。这些产品和方案主要定位于移 动性较小或静止的a dh o e 网络无线网状网络( w i r e l e s sm e s hn e t w o r k s ， w m n s ) 。于是，无线m e s h 网络的概念得到人们的关注。w m n s 是无线自组织网 络( a dh o e ) 的一种特殊形态，它的早期研究均源于移动a dh o e 网络的研究与开 发。 近年来，w l a n 依其所具有的巨大数据传输速率在接入领域中得到了迅速发 展，但w i a n 最主要的一个不足之处是其接入点的覆盖范围较为有限，若要在一 个相对较大的区域提供无线覆盖，就需要在该地区内配置多个接入点，因而增加 了建设基于w l a n 的公共宽带网的成本。虽然人们对此提出了一些解决方法，如 通过多种无线技术的共存来提高无线的覆盖和位置的适应性等等，但这些方法中 大多是以增加接入点或降低网络运行效率为代价。于是人们把目光转向了无线网 状网络，希望通过这种全新的网络结构来克服传统无线网络中所存在的固有缺点， 实现无线宽带领域中的一次变革。它是一种高容量高速率的分布式网络，不同于 传统的无线网络，可以看成是一种w l a n 和a dh o e 网络的融合，且发挥了两者 的优势，作为一种可以解决“最后一公里”瓶颈问题的新型网络结构。 本文基于国家自然科学基金项目：无线移动自组织网络多信道m a c 层协议研 究( 6 0 5 7 2 1 4 5 ) 以及陕西省自然科学基金项目：基于无线自组织网络的智能交通 系统。对现有的无线网状网络路由协议进行了分析，并解决了通过改进路由尺度 算法来提高网络吞吐量的问题。 2 无线网状网络的路由算法研究 1 2 研究意义 无线网状网络是由网状路由器( m e s hr o u t e r ) 和网状终端( m e s hc l i e n t ) 这两 种网络实体组成的1 1 1 。其中网状路由器一般情况下是固定的并且组成了整个无线网 状网络的骨干网，它们具有路由及数据转发的功能，并且担任着连接无线网络和 有线网络( 如i n t e r n e t ) 以及使用不同无线协议( 如8 0 2 1 1 ，8 0 2 1 5 ，8 0 2 1 6 ) 的无 线网络之间的网关和桥接功能。网状终端可以是静止的或是移动的，它同样具备 路由及数据转发的功能，但是不具备网关功能，它既是业务的使用者也是业务的 提供者。终端节点可以通过其它相邻终端节点或路由器以多跳的方式实现骨干网 的接入，从而增强了网络的覆盖能力。w m n s 可以看成是一种特殊的w l a n ，除 移动性较低外，w m n s 本质上是一种a dh o e 网络。目前主要观点认为，w m n s 是一种由无线连路连接路由器和终端设备的静态无线网络，是i n t e m e t 的无线版本。 作为一种新型网络结构形态，w m n s 结构已经被纳入到8 0 2 1 6 ，8 0 2 1 6 e ，8 0 2 1 1 s ， 等标准中。w m n s 作为一种新型的应用网络，因其自身特点以及在家庭、企业和 公共场所等诸多领域的广阔的应用前景【“，因此具有重要的理论意义和实际意义。 ( 1 )家庭宽带网 传统的w l a n 应用于家庭宽带网的主要问题是盲区问题，为了解决这个问题， 通常需要部署多个a p 并且要精确的测量摆放这些a p 的位置。但是这种方法花费 昂贵，所以对于家用来说是不切合实际的。而w m n s 的一个重要用处就是用于建 立家庭无线网络。家庭式无线网状联网可以连接台式p c 机、笔记本、d v d 播放 器、游戏控制台，以及其他各种消费类电子设备，而不需要复杂的布线和安装过 程。在家庭w m n s 中，各种家用电器既是网上的用户，也作为网络基础设施的组 成部分为其他设备提供接入服务。当家用电器增多时，这种组网方式可以提供更 多的容量和更大的覆盖范围。w m n s 应用家庭环境中的另外一个关键好处是它能 够支持带宽高度集中的应用，如高清晰度视频等。 ( 2 )企业网 目前。企业的无线通信系统大都采用传统的蜂窝电话式无线链路或w l a n ， 但是a p 之间的连接仍然是通过有线的方式，这无疑还需要布线等工作，从而增大 了网络建造成本。此外通过增加a p 数量，只能提高局部吞吐量，但是对于链路失 败的鲁棒性和网络拥塞控制毫无用处。w m n s 则不同，它允许网络用户共享带宽， 消除了目前单跳网络的瓶颈，并且能够实现网络负载的动态平衡。w m n s 可以用 于小型办公环境，也可以应用于大规模企业场所( 比如多个写字楼之间的通信) 。 在无线网状网络中增加或调整a p 也比有线a p 更容易、配置更灵活、安装和使用 第一章绪论 3 成本更低。尤其是对于那些需要经常移动接入点的企业，无线网状技术的多跳结 构和配置灵活将非常有利于网络拓朴结构的调整和升级。 ( 3 ) 学校 校园无线网络与大型无线企业网非常类似，但也有自己的不同特点。一是校 园w l a n 的规模巨大，不仅地域范围大，用户多，而且通信量也大，因为与一般 企业用户相比学生会更多地使用多媒体；二是网络覆盖的要求高，网络必须能够 实现室内、室外、礼堂、宿舍、图书馆、公共场所等之间的无缝漫游；三是负载 平衡非常重要，由于学生经常要集中活动，当学生同时在某个位置使用网络时就 可能发生通信拥塞现象。解决这些问题的传统作法是在室内高密度地安装a p ，而 在室外安装的a p 数量则很少。但由于校园网的用户需求变化较大，有可能经常需 要增加新的a p 或调整a p 的部署位置。这会带来很大的成本增加。而使用w m n s 方式组网，不仅易于实现网络的结构升级和调整，而且能够实现室外和室内之间 的无缝漫游。 ( 4 )医院 w m n s 还为像医院这样的公共场所提供了一种理想的联网方案。由于医院建 筑物的构造密集而又复杂，一些区域还要防止电磁辐射，因此是安装无线网络难 度最大的领域之一。医院的网络有两个主要的特点。一是布线比较困难：在传统的 组网方式中，需要在建筑物上穿墙凿洞才能布线，这显然不利于网络拓朴结构的 变化。二是对网络的健壮性要求很高：如果医院里有重要的活动( 如手术) ，网络 任何可能的故障都将会带来灾难性的后果。采用无线m e s h 组网则是解决这些阀题 的理想方案。如果要对医院无线网络拓扑进行调整，只需要移动现有的网状节点 的位置或安装新的网状节点就可以了，过程非常简单，安装新的网状节点也非常 方便。而无线网状网络的健壮性和高带宽也使它更适合于在医院中部署。 ( 5 ) 旅游休闲场所 w m n s 非常适合于在那些地理位置偏远布线困难或经济上不合算，而又需要 为用户提供宽带无线i n t e m e t 访问的地方，如旅游场所、度假村、汽车旅馆等。 w m n s 能够以最低的成本为这些场所提供宽带服务。 ( 6 ) 交通运输系统 通过在汽车，轮船，火车，站台等地方安置网状路由器或网状终端，基于网状 网络的交通系统可以为乘客和驾驶员提供各种各样的服务，比如乘客信息服务， 安全监视，道路交通信息，气象信息，驾驶员通信服务等。但是这种应用给网状 无线网状网络的路由算法研究 网络的设计提出了新的挑战，因为交通工具一般都是以比较高的速度运动，所以 在设计的时候要充分考虑移动性对网络性能的影响。 ( 7 )楼宇自动化 通过在楼宇内布置无线网状节点，可以轻松的实现诸如电源开关，灯，电梯， 空调，报警器等各种设施的控制和监视。目前采用的有线方式不但造价高，并且 布线复杂、可扩展性差。所以采用无线网状网络，是个很好的解决方案。 ( 8 ) 快速部署和临时安装 对于那些需要快速部署或临时安装的地方，如展览会、交易会、灾难救援等， 无线网状网络无疑是最经济有效的组网方法。比如，如果需要临时在某个地方开 几天会议或办几天展览，使用无线网状网络技术来组网可以将成本降到最低。 1 3w m n s 的关键技术问题 无线网状网络的几个关键技术问题需进一步研究解决，这些问题包括： ( 1 ) 天线技术 为了进一步提高传输速率和性能，一些新的带宽传输调制技术比如o f d m ， u w b 已经开始应用到实际中了。无线网状网络中一个重要的问题就是天线的使 用，因为每个节点必须和各个方向上的多个节点通信，很简单的一种方式就是采 用全向天线，但是这样覆盖范围有限，并会带来干扰，导致频谱利用率下降，网 络容量减小，所以不建议采用全向天线。目前很多的新的天线技术已经浮出水面， 为w m n s 天线技术提供了很多解决方案。这些新的技术主要包括：方向天线，智 能天线，多输入多输出系统( m i m 0 ) ，可重配置天线，频率感知天线，软天线等。 尽管其中很多技术仍处于起步阶段，但是预期将被以后无线网络广泛应用。 ( 2 )媒体接入控制技术 为了更好的利用新的物理层技术带来的优势，高层协议特别是m a c 层协议应 该更好的被设计以充分发挥整个系统的性能。无线网状网络m a c 层协议与传统的 无线网络有很大的区别，主要表现在：无线网状网络的m a c 层协议设计时要考虑 多跳方式下的通信，从而存在隐藏终端、暴露终端等问题；无线网状网络是一种 多点对多点的分布式的通信网络，网络中没有控制中心用于协调节点问的通信， 所以m a c 层协议必须保证所有节点能够协同工作；节点移动性对m a c 性能的影 第一章绪论 响；因为无线网状网络中节点的特点，那些负责连接支持不同无线协议的网状路 由器的m a c 层必须要保证能够使得支持8 0 2 1 1 ，8 0 2 1 6 ，8 0 2 1 5 等协议的节点无 缝的工作。目前国外对m a c 层的研究主要集中在如何提高系统容量，吞吐量以及 公平性等方面上，此外很多论文都是针对多信道或多网卡的m a c 层设计。 ( 3 ) 路由选择技术 w m n s 另外一个很重要的问题是路由选择，例如从节点a 到节点b ，可以经 过不同的用户站中转，存在多条路径，于是选择哪条路径就成为一个关键问题， 这将直接影响系统的性能。而且，当节点增加或是减少时，无线m e s h 网络的拓扑 结构会发生变化，路由选择问题变得更加复杂。采用无线m e s h 还会带来“隐藏终 端”问题，这些都需要进一步研究解决。对于a dh o e 网络和w m n s ，目前还没有 正式的路由协议标准。这两种网络的路由协议既有相同点又有区别，在路由协议 的设计上，要根据具体情况进行专门的设计。 ( 4 ) 动态带宽分配技术及o o s 保障 宽带无线接入系统的频谱资源有限，因此必须使信道资源尽可能被充分利用。 在i e e e8 0 2 1 6 标准中规定的点到多点( p m p ) 宽带无线接入网络中采用了动态按 需时分多址分配d a m at d m a 方式，在这种网络中资源的管理和分配由基站负 责。而在i e e e8 0 2 1 6 a 标准中规定，对于基于无线m e s h 技术的宽带接入网络，带 宽的分配可以采用集中调度方式，或者采用分布调度方式。如果采用集中调度方 式，由m e s hb s 节点收集所有m e s hs s 节点的资源请求信息，分别为它们分配一 定数量的带宽资源。如果采用分布调度方式，包括m e s hb s 和m e s hs s 在内的所 有节点应该相互协调，充分利用资源。任何一个节点发送数据时，不能和两跳以 内的邻近区域的其它节点发送的数据产生碰撞。不同于a dh o e 网络，w m n s 主要 应用在宽带服务中，所以除了端到端延时和公平性等性能参数需要保证外，还有 满足很多其他q o s 参数。 1 - 4 文章结构 在第二章中，根据无线网状网络的体系结构分类，分别进行了介绍；其次针对 无线网状网络的优点和不足分别进彳亍了分析；最后介绍了无线网状网络和无线自 组织网络的不同以及无线自组织网络的特点。 在第三章中，首先介绍了无线网状网络路由协议研究的意义以及应具备的特 点；其次根据无线网状网络的单信道和多信道路由协议的分类法则，分别对现有 无线网状网络的路由算法研究 的路由协议进行了介绍和分析，在单信道路由协议中根据先应式，反应式和混合 式的分类方式分别介绍，在多信道路由协议中，根据单网卡和多网卡的分类分别 进行分析；最后介绍了路由协议的跨层设计。 在第四章中，根据问题的引出，详细介绍本文作者提出的一种全新的多信道无 线网状网络路由算法- - w c e t y r ，并且对该算法进行了仿真以及对仿真结果进行 了分析。 在第五章中，对全文进行总结，并对今后工作做了展望。 第二章无线网状网络体系结构及其特点 第二章无线网状网络体系结构及其特点 2 1w m n s 的体系结构 按照体系结构划分，无线网状网络可以分为三种，分别为：主干网结构 ( b a c k b o n ew m n s ) ，终端组网结构( c l i e n t sw m n s ) 和混台结构( h y b r i dw m n s ) f 1 】。 ( 1 )主干网结构 网络中的网状路由器互连构成了骨干网络。这些路由器分为两种，一种是具有 网关功能的，它负责连接终端节点，实现终端节点的网络接入( 如图2 1 所示，路 由器负责各个传感器节点，p d a ，笔记本电脑，有线终端，手机等设备的网络接 入) ，并且能够实现符合不同标准网络通讯协议子网之间的互联( 如图2 1 所示， 通过具有网关功能的路由器，无线局域网，传感器网络，蜂窝通信网等网络可以 互联) ，同时部分具有网关功能的路由器还负责连接i n t e r a c t 网络，使得网络中各 个节点能够访问 n t e r n e t 资源。另一种路由器是不具备网关功能的，它们只负责数 据的转发。主干网结构的无线网状网络是目前应用最广泛的一种体系结构，网状 路由器一般被部署在屋顶或者较高建筑物上，它的射频器件一般分为两类，分别 适用于与终端用户连接发送半径较短的射频器件以及用于骨干节点之间数据传输 的，发送半径较大的射频器件( 如方向天线) 。 图2 1 主干网结构无线网状网络 无线网状网络的路由算法研究 ( 2 ) 终端自组网结构 终端自组网结构无线网状网络是由对等( p e e r - t o p e e r ) 终端节点组成的网络， 如图2 2 所示。网络中节点通过自组织，自配置方式组网，为终端用户提供端到端 ( e n d t o e n d ) 的服务，因此在这种结构中，是不需要网状路由器的。当源节点发 送数据包给目的节点时，数据包通过多跳的方式传送，中间节点负责路由和数据 的转发，其功能相当于路由器。实际上这种组网结构等同于a d h o e 网络。 ( 3 ) 混合结构 混合结构无线网状网络，如图2 3 所示，它是主干网结构和终端自组网的结合。 网状终端可以通过网状路由器的方式实现网络的接入，也可以通过其它网状终端 接入网络。混合结构无线网状网络拥有更广的应用范围和更好的适应性。比如在 紧急救援行动中，救援人员随身携带的网状终端可以i 临时组网，相互之间进行通 信，并且能够将救援行动中的重要数据通过i n t e r n e t 发送到总部。 2 2 1w m n s 的优点 图2 2 终端组网结构_ j e 线网状网络 2 2w m n s 的优点和不足 ( 1 ) 自愈性：w m n s 可以提供完全的端到端的多重冗余路由，这就意味着如果 最近的节点出现故障或者受到干扰，数据包将自动路由到备用路径继续进行传输， 整个网络的运行不会受到影响。若由于某种原因某个链路失效，网络能自动地更 换路由。 ( 2 ) 可靠性：在m e s h 网络结构中为了提高链路质量，可通过增加中间节点， 第二章无线网状网络体系结构及其特点 即缩短节点之间的距离来实现( 2 】。 图2 3 混合结构无线网状网络 ( 3 ) 自配置能力：w m n s 是一种自组织网络，不需要或很少需要人工配制网络， 因而，网络能够自动判断并更新网络相关配置【3 。 ( 4 ) 非视距传输：利用无线m e s h 技术可以很容易实现n l o s 配置，因此在室 外和公共场所有着广泛的应用前景。与发射台有直接视距的用户先接收无线信号， 然后再将接收到的信号转发给非直接视距的用户。按照这种方式，信号能够自动 选择最佳路径不断从一个用户跳转到另一个用户，并晟终到达无直接视距的目标 用户。这样，具有直接视距的用户实际上为没有直接视距的邻近用户提供了无线 宽带访问功能。无线m e s h 网络能够非视距传输的特性大大扩展了无线宽带的应用 领域和覆盖范围。 ( 5 ) 网状节点的类型决定其移动性及对能耗的需求：网状路由器通常是静止的 或是慢速移动的并通过有线电源进行供电，所以它对能耗的要求并不严格。而网 状终端通常是移动的，并通过电池供电，所以能源效率高的协议对于网状终端是 非常重要的。 ( 6 ) 支持多种网络接入：w m n s 即支持i n t e m e t 接入同时又支持对等通信，同时 还支持使用不同通信协议网络之间的通信。 2 2 2w m n s 的不足 ( 1 ) 分散管理问题：由于w m n s 的分散性，很难实现像有线网络那样的集中 无线刚状网络的路曲算法研究 管理，即使对于低移动性的w m n s ，网络配置和管理仍然是一个不易解决的问题。 ( 2 )共存干扰问题：对于非许可证频段的w m n s 必然存在与其他共存网络的 无限干扰问题。 ( 3 ) 安全问题：与w l a n 的单跳机制相比，无线m e s h 网络的多跳机制决定了 用户通信要经过更多的节点。而数据通信经过的节点越多，安全问题就越变得不 容忽视。尽管有线网络中使用的各种安全技术，如虚拟专用网( v p n ) 、s s 坍l s 同样可以用来解决无线m e s h 的安全问题。但正如i n t e r n e t 一样，无线m e s h 网络 的安全是一个不容忽视的问题。 ( 4 ) 互操作性：目前影响无线m e s h 技术迅速普及的一个重要障碍就是互操作 性。正如任何一种新兴的网络技术刚出现时一样，无线m e s h 网络现在还没有一个 统一的技术标准，用户现在要么就只能使用某一个厂商的无线m e s h 产品，要么面 临如何与各种不同类型的嵌入式无线设备接口的问题，这个问题目前是影响无线 m e s h 技术推广使用最重要的原因。鉴于此，目前一些公司正在开发能够适应不同 无线环境的可配置的无线网络设备，互操作性有望得到一定程度的解决。但要想 彻底解决互操作性问题，最终还需要业界制定统一的无线m e s h 技术标准。 ( 5 )通信延迟；既然在m e s h 网络中数据通过中间节点进行多跳转发，每一跳 至少都会带来一些延迟，随着无线m e s h 网络规模的扩大，跳接越多，积累的总延 迟就会越大。一些对通信延迟要求高的应用，如话音或流媒体应用等，可能面临 无法接受的延迟过长的问题。目前解决这一问题主要是通过增加m e s h 节点以及合 适的网络协议。随着多无线m e s h 节点技术的出现这一问题将得到最终解决。 2 3 w m n s 与a d h o c 网络的区别 a dh o c 技术起源于2 0 世纪7 0 年代的美国军事领域，当时所提出的网络是一 种服务于军方的无线分组网络，实现基于该种网络的数据通信。随着移动通信和 移动终端技术的高速发展，a dh o c 网络不但在军事领域中得到了充分的发展，而 且也在民用移动通信中得到了应用；尤其是在一些特殊的工作环境中，比如所在 的工作场地没有、或者不能使用已有的网络通信基础设施时，就需要利用a dh o c 技术完成通信网络的立即部署，满足用户对移动数据通信的需求，实现用户之间 的通信及协同工作。a dh o c 网络是一种不同于现有网络的特殊无线网络，强调无 中心接入、多跳路由；移动终端节点不仅具有主机的功能，还具有路由器的功能。 与其他通信网络相比，a dh o c 网络具有以下特征； ( 1 ) 网络的自组织性：a d h o c 网络相对常规通信网络而言，最大的区别就是可 以不需要硬件基础网络设施的支持，在任何时刻、任何地点快速构建起一个移动 第二章无线网状网络体系结构及其特点 通信网络。它的建立不依赖于现有的网络通信设旋，具有自组织性； ( 2 )动态的网络拓扑结构：在a dh o c 网络中，网络中的节点可以在网络中随 意移动。节点的移动会导致节点之间的链路增加或消失，节点之间的关系不断发 生变化。在自组网中，节点可能同时还是路由器，因此，移动会使网络拓扑结构 不断发生变化，而且变化的方式和速度都是不可预测的； ( 3 ) 分布式的网络：在a dh o e 网络中没有中心控制节点，节点通过分布式协 议互联。一旦网络的某个或某些节点发生故障，其余的节点仍然能够正常工作， 增强了网络健壮性； ( 4 ) 有限的无线传输带宽：a dh o e 网络中的节点是通过无线信道进行数据传输 的，无线信道本身的物理特性使得网络的网络带宽相对有线网络要低的多；另外， 无线信道竞争时所产生的信号衰落、碰撞、阻塞、噪声干扰等因素使得移动终端 可得到的实际带宽远远小于理论中的最大带宽值； ( 5 ) 移动终端的有限性：a d h o c 网络中的移动用户终端内存小、c p u 处理能力 低、所带电源有限使得a dh o c 网络的设计更加困难； ( 6 )安全性差：a dh o e 网络是一种无线方式的分布式结构，所以更加容易被窃 听、入侵、网络攻击和拒绝服务等；不过a dh o c 网络的分布式特性相对于集中式 的网络具有一定的抗毁性； ( 7 ) 生存时间短：a dh o c 网络主要用于临时的通信需求，相对与有线网络，它 的生存时间一般比较短。 a dh o c 网络设计中的一个关键问题是开发能够在两个节点之问提供高质量高 效率通信的路由协议。网络节点的移动性使得网络拓扑结构不断变化，传统的基 于因特网的路由协议无法适应这些特性，需要有专门的应用于a dh o c 网络的路由 协议，根据前文对a dh o e 网络结构和特点的阐述，设计的路由协议必须满足以下 的条件： ( 1 ) 必须对网络拓扑结构动态变化具有快速应变的能力，并且尽量避免路由环 路的发生。 ( 2 ) 必须高效地利用有限的带宽资源，尽可能减少不必要的开销。 ( 3 ) 实施多跳通信的中间转接次数也是有限的，一般不要超过3 次。 ( 4 ) 必须尽可能减少发射时间和发射的数据量，减少能耗。 w m n s 与a d h o c 网络均是多跳无线网络。a d h o c 网络中的移动节点都兼有独 立路由和主机功能，不存在类似于基站的网络中心控制点，节点地位平等，采用 分布式控制方式。w m n 把a dh o c 网络技术应用到移动节点中同时又使移动节点 可通过连接到其它网络( 如i n t e m e t ) ，因此可以把w m n 看成是a dh o c 网络技术 的另一种版本。但w m n 与移动a dh o c 网络的业务模式不同，对于前者，节点的 主要业务是来往于因特网网关的业务，而对于后者，节点的主要业务是任意节点 无线网状网络的路由算法研究 对之间的业务流。虽然人们对a dh o c 网络的研究已经有相当长的时间，但是主要 还是在理论上，而且主要应用在军事上，还未进行大规模的商用。无线网状网络 和无线自组织网络( a dh o cw i r e l e s sn e t w o r k s ) 都是采用多跳方式接入网络并进行 通信的，但是二者又有着很大的不同，主要表现在： ( 1 ) 无线网状网络中骨干网节点通常是静止的，终端节点可以是静止或是缓慢 移动的，因而其网络拓扑变化相对缓慢，而无线自组织网络因节点的移动性，其 网络拓扑变化较快： ( 2 ) 无线网状网络能够比无线自组织网络提供更大的覆盖范围： ( 3 ) 无线网状网络能够通过网状路由器的网关功能整合各种现存的无线标准 和技术，而无线自组织网络能够同时兼容的无线标准相对单一； ( 4 ) 无线网状网络的通信一般都发生在终端节点到能够连接有线网的网关之 间，而无线自组织网络的是任意两个节点之间的通信； ( 5 ) 无线网状网络的路由器不依赖能耗，而无线自组织网络的节点一般是通过 电池供电，所以能耗成为其设计的关键因素。 第三章无线网状网络路由协议的分析 第三章无线网状网络路由协议的分析 在上一章中，主要介绍了w m n s 的特点和应用，以及和无线自组织网络的区 别。在路由协议的设计上，无线网状网络和无线自组织网络既有共同点又要根据 具体情况进行专门的设计，从而w m n s 的路由协议可以借鉴a d h o c 网络的路由协 议。本章将分析w m n s 路由协议的特点和设计要素，并对目前比较流行的无线网 状网络路由协议进行介绍和分析。 3 1w m n s 路由协议的特点 因为无线网状网络和a dh o c 网络具有很多共同特点，所以很多为a dh o c 网络 设计的路由协议可以应用于无线网状网络，比如m i c r o s o f tm e s hn e t w o r k s 是基于 d s r 协议的改进版本l q s r 协议。但是无线网状网络的路由协议研究仍然是一个 热点，这是因为： ( 1 ) 为了进一步改善路由的性能，需要采用新的路由衡量尺度来进行路由的选 择； ( 2 ) 现有的路由协议在可扩展性上都具有局限性； ( 3 ) 传统的网络体系结构各个层次之间都是相互透明的，只是通过层问的接口 传递服务数据单元( s d u ) ，但是很多论文表明采用跨层设计能够进一步提高路由 协议的性能，所以无线网状网络路由协议的跨层设计成为一个研究热点； ( 4 ) 无线网状网络的能耗需求以及节点的移动性和无限自组织网络有很大的 不同：网状路由器移动性非常低并且不依赖能耗限制，而网状终端通常具有一定 的移动性，并且需要节能效率高的路由协议。 根据无线自组织网络路由协议以及无线网状网络的特点，一个理想的无线网 状网络路由协议应该具备以下特点： ( 1 ) 根据多路由尺度进行路由选择。很多传统的无线网络路由协议都是基于最 少跳数路由算法进行路由的选择，但是在很多情况下，只采用最少跳数来进行路 由选择并不能选出最优的路由，尤其是在多信道环境下。为了使得网络吞吐量最 大，采用何种路由尺度选择策略成为无线网状网络研究的一个关键性问题，这也 正是本文的核心工作。 ( 2 ) 差错容忍性佳。当一条链路失败后，路由协议应该能够立刻选取另外一条 路由，以防止服务的中断。 ( 3 ) 负载平衡。无线网状网络的目标之一就是让所有的终端用户共享网络的资 源。当网络中部分链路产生了拥塞，那么之后的数据就不应该再流经这部分链路， 以防止拥塞的加重。通过一些路由尺度参数，比如r t t ( r o u n dt r i pt i m e ) 可以用 无线网状网络的路由算法研究 于反映一条路经的拥塞程度。 ( 4 ) 可扩展性好。随着网络规模的扩大，无线网络路由的建立需要更长的时间 并且端到端的延时更大。此外，即使路由建立起来后，由于中闯节点的移动或损 坏，会导致路由的失效，所以可扩展性也是无线网状网络的一个关键性问题。 ( 5 )自适应的路由协议。因为无线网状网络的网状路由器和网状终端在移动件 以及对能耗的要求上的不同，所以网状路由器路由协议设计比网状终端路由协议 简单。因此路由协议应该能够根据节点性质的不同，采取不同的策略。 ( 6 ) 对单向发非对称链路的支持。根据无线链路的特点，在实际情况下上行链 路和下行链路一般都是非对称的，甚至有的时候链路是单向的。而现有的大多数 路由协议都是基于链路对称的假设。 3 2 单信道w m n s 路由协议的分析 目前单信道a dh o c w m n s 路由协议大致可咀分为先应式路由协议、反应式路 由拂议和混合式路由协议3 种 4 1 ，本节将分别介绍分析。 3 2 1 先应式路由协议 先应式( p r o a e t i v e ) 路由协议又被称为表驱动( t a b l e d r i v e n ) 路由协议，是 种纂于表格的路由协议 5 1 。在这种路由协议中，每个节点维护一或多张表格，这些 表格包含到达网络中其它所有节点的路由信息。当检测到网络拓扑结构发生变化 时，节点在网络中发送更新消息。收到更新消息的节点更新自己的表格，以维护 一致的、及时的、准确的路由信息。不同的先应式路由协议的区别在于拓扑更新 消息在网络中传播的方式和需要存储的表的类型和数量。 先应式路由协议不断地检测网络拓扑和链路质量的变化根据变化更新路出 表，所以路由表可以准确地反映网络的拓扑结构。图3 1 是现有的部分先应式路由 表，所以路由表可以准确地反映网络的拓扑结构。图3 1 是现有的部分先应式路由 协议。 图3 1 先应式路由协议 第三章无线网状网络路由协议的分析 ( 1 ) d s d v 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 a n c ev e c t o r ) 7 l 路由协议是一种无环路距 离向量路由协议，它是传统的b e l l m a nf o r d 路由协议的改进。它需要每个节点周 期的广播其路由更新信息。d s d v 和传统的距离矢量协议相比，其最大的优势是 它能够保证避免路由回环。在这种算法当中，每一个节点维护一张包括网内所有 可能目的地和到它们的路由跳数的路由表。每一条记录带有一定的序列号标记， 该序列号是由目标节点分配的。这一序列号使得移动节点可以区分过时的路由和 最新的路由，从而可以避免路由环的形成。 根据路由信息更新机制的不同，d s d v 协议分为d s d v 。s q ( s e q u e n c en u m b e r ) 协议和s i m p l yd s d v 协议。d s d v - s q ：当收到一条新的路由，如果此路由具有 新的s q ( 即路由序列号) 的时候，则发送路由更新信息，这种方式下网络开销比 较大。s i m p l yd s d v ：仅仅当收到的新路由中含有新的信息时，才发送路由更新信 息，这种方式下网络开销相对前一种比较小。d s d v s q 虽然会增加网络的开销， 但是却可以及时的使路由信息得到更新，不过对于网络拓扑变化相对缓慢的无线 网状网络来说，d s d v - s q 是不适合的。 ( 2 )w r p w r p ( w i r e l e s s r o u t i n g p r o t o c 0 1 ) i s 】也是一种距离向量路由协议，每个节点包 含距离表、路由表、链路权值表和消息重传表四张表。其中距离表记录通过其每 个邻节点到达任意目的节点的跳数以及每个目的节点前一跳节点；路由表记录到 达目的节点的距离，通过最短路径选择算法得到的目的节点的前一跳节点以及后 一跳节点，路由表更新标志位：链路权值表记录通过任一邻节点转发数据所需花 费；消息重传表中的每一条记录包含了更新信息的序列号，一个重传计数标志， 是否响应确认信息的标志量，以及更新报文中的更新信息。 移动节点通过更新信息的传送来通知其它节点链路的改变。更新信息仅仅在 相邻节点间传递，并且包含一串更新信息：目的地址、路径权值以及目的地址的 前一个节点。当一个节点收到其他邻居节点发来的更新信息，更改自己的表信息 并向发送节点发送确认，同时将更新信息向其他邻居节点转发。当一个节点在一 定的时间期限内没有数据要发送时，它必须发送“h e l l o ”数据包到其他节点，以 表明链路仍然可达。否则，其他节点将视为到该节点的连接中断，继而发出错误 的更新信息。当其他节点接收到新的节点发出的“h e l l o ”数据的时候，便将新节 点的信息加入自己的路由表，并向该新节点转发自己的路由表信息。但是该方法 周期性的发送”h e l l o ”信息浪费了网络带宽，并且每个节点要维护四张表，从而也 从一定程度上增加了网络的负担。 无线网状网络的路由算法研究 图3 2 说明了当网络中链路失效的时候，w r p 协议是如何更新路由表的。其 中每条链路边上所显示的数字为链路权值即链路消耗，括号中的内容为到达目的 节点j 所需的消耗以及目的节点的前一跳节点，如图3 2 ( a ) 所示，节点b 路由 表的一项为( 2 ，k ) ，其含义是根据最短路径算法，b 节点到j 节点的路径总消耗 为2 ，到达目的节点j 的前一跳节点为k ，其他节点括号中内容含义相同。当k j 链路失效后，节点k 和j 将分别发送更新信息给它们的邻节点，这里我们以k 节点为例，如图3 2 ( b ) 所示，此时k 节点到达j 节点的路径权值设为无穷大。 当b ，i 节点收到了来自k 节点的路由更新信息后，它们将分别更新其距离表，并 且根据最短路径算法重新选择一条到达目的节点j 的路径。比如节点i 将选择i j ， 其链路消耗为1 0 ，目的节点前一跳节点为其自身。之后b 和j 将发送更新信息给 其邻节点，如图3 2 ( c ) 所示。当节点k 收到更新信息后，更新距离表并选择一 条最佳路由，并发送更新信息，如图3 2 ( d ) 所示，当节点b 和i 收到来自k 的 更新信息后，因为更新序列号相同，所以不会对它们的路由表产生任何影响。 丁 k k ( 0 j )( 0 。j ) 南二一 ( 1 墨) ( a ) ( i n f m 姆，) 图3 2w r p 协议路由表的更新 ( b ) ( 3 )g s r g s r ( g l o b a ls t a t er o u t i n g ) 9 】是一种基于网络拓扑结构的链路状态路由协议， 它周期性的与邻节点交换链路状态信息，从而避免路由信息泛洪给网络带来的负 担。在g s r 协议中每个节点存储邻居列表、拓扑表、下一跳表和距离表四张表格。 邻居列表记录着个节点所有的邻居节点。对于每个目的节点，拓扑表记录链路状 乏 豢 第三章无线网状网络路由协议的分析 态信息以及这个信息的时间戳；下一跳表记录包发往目的节点的下一跳节点：距 离表记录了到每一个目的节点的最少跳数。 当一个节点受到了路由消息，并且这个消息的序列号比原有的新，那么它将更 新其拓扑表。之后重组其路由表并广播给其邻居节点。 ( 4 )f s r f s r ( f i s h e y es t a t er o u t i n g ) b o l l “j 对g s r 进行了改进。相对g s r ，f s r 的更 新消息只包含附近节点的信息而不是所有节点的，同时链路状态表中的不同条目 的更新周期也不尽相同，从而显著地减小了更新消息的大小。与邻近节点的信息 交换远远频繁于距离远的节点，所以每个节点能够及时地获得邻近节点的准确消 息，并且消息的详细程度和准确度随着与该节点距离的增加而减小。尽管源节点 没有距离较远的目的节点的准确信息，但是当数据包距离目的节点越近那么路由 信息越准确，所以数据包能够被正确的发送至目的节点。f s r 的优点在于适用于 大规模的以及高速移动的网络环境中，但是因为该协议只能获取小范围内准确的 路由和链路信息，而无线网状网络的通信流量主要发生在网关链路上，从而远离 网关的节点不能及时地察觉到该网关的负载情况，从而有可能进一步加重拥塞。 ( 5 ) h s r h s r ( h i e r a r c h i c a ls t a t er o u t i n g ) 【1 2 j 是一种用于分级网络的路由协议。高级的 节点保存它所有子孙节点的位置信息。沿着从最高级的根节点到最低级的叶节点 的路径为节点分配逻辑序列地址。序列地址指示了节点的位置，可以简单地使用 序列地址进行寻址。网络还配备了位置管理服务器来实现物理地址到逻辑序列地 址的映射。h s r 与c g s r 的区别在于h s r 可以是多于2 层的簇结构，低层次的各 个簇首节点可以组成新的簇，并且从中选出簇首作为更高层簇的簇首。但是二者 的簇首节点的选取是相同的。 分级结构路由协议的优点主要有：减少了大多数节点路由表的大小；能够