（计算机科学与技术专业论文）多信道多跳无线网络广播机制的研究.pdf

国防科学技术大学研究生院学位论文 摘要 近年来，多跳无线网络比如a dh o e 网络、传感器网络、m e s h 网络的研究成为 人们关注的热点。在多跳无线网络中，节点通信需要竞争有限的共享频谱资源， 并且随着路由跳数及网络密度的增加，这种竞争将更加明显并有可能导致网络容 量不足以满足用户的需求，这是构建大规模多跳无线网络亟需解决的问题。使用 多接口多信道技术，把节点的多个接口调制到不同的正交信道，节点在不同的信 道下可以并行地进行收发操作，这样可以有效地提高网络容量。多接口多信道技 术为网络协议的设计提出了全新的挑战 广播是多跳无线网络的一种重要操作，它不仅是许多无线应用中的重要通信 手段，还是单播路由协议中路由发现的基本方式以及维持多播路由的多播树和多 播关系的有效工具。在单信道多跳无线网络中，关于广播问题已经有了很多研究， 但在多信道多跳无线网络中，简单地使用已有的广播算法会造成额外的冗余、冲 突。本文将在多信道网络环境下研究广播问题，分别针对减少广播冗余、消减传 输冲突、提高广播容量提出了三种算法。通过将广播问题归结为接口扩展图中的 最小强连通支配集问题，我们提供了一种自剪枝策略用于减少广播冗余。通过比 较历史广播路径信息，我们使用邻居指定策略消除传输冲突。使用深度优先遍历 的策略，我们通过构造一棵无冲突的广播树进行广播调度达到提高广播容量的目 的。 本文还对n s 2 网络模拟器进行了扩展，增加了对多接口多信道模拟的支持。 并在此基础上针对不同条件对本文算法进行模拟，模拟结果证明了算法的有效性。 主题词：多信道，多跳，无线网络，广播，冗余 第i 页 国防科学技术人学研究生院学位论文 a b s t r a c t r e c e n ty e a r sh a v es e e n s i g n i f i c a n t i n t e r e s ti n u s i n gt h em u l t i - h o p w i r e l e s s n e t w o r k i n gp a r a d i g mf o rb u i l d i n ga dh o cn e t w o r k s ，s e n s o rn e t w o r k sa n dm e s hn e t w o r k s af u n d a m e n t a lo b s t a c l et ob u i l d i n gl a r g es c a l em u l t i - h o pn e t w o r k si st h ei n s u f f i c i e n t n e t w o r kc a p a c i t yw h e nr o u t el e n g t h sa n dn e t w o r kd e n s i t yi n c r e a s ed u et ot h el i m i t e d s p e c t r u ms h a r e di nt h en e i g h b o r h o o d t h eu s eo fm u l t i p l er a d i o sw h i c ht u n e dt o o r t h o g o n a lc h a n n e l sc a ns i g n i f i c a n t l yi m p r o v et h en e t w o r kc a p a c i t yb ye m p l o y i n g c o n c u r r e n tt r a n s m i s s i o n su n d e rd i f f e r e n tc h a n n e l s ，a n dt h a tm o t i v a t e st h ed e v e l o p m e n t o fn e wp r o t o c o l sf o rm u l t i - r a d i om u l t i c h a n n e ln e t w o r k s b r o a d c a s ti sa ni m p o r t a n to p e r a t i o ni nm u l t i - h o pw i r e l e s sn e t w o r k s i ti sn o to n l y a ni m p o r t a n tc o m m u n i c a t i o np a t t e r ni nm a n yw i r e l e s sa p p l i c a t i o n s ，b u ta l s ot h eb a s i c m e a n sf o rr o u t ed i s c o v e r yi nu n i c a s tr o u t i n ga n dau s e f u lt o o lt om a i n t a i nt h em u l t i c a s t m e m b e r s h i pa n dm u l t i c a s tt r e ei ns o m em u l t i c a s tr o u t i n gp r o t o c o l s m a n ya p p r o a c h e s h a v eb e e np r o p o s e df o rb r o a d c a s t i n gp r o b l e m s b u t t h e ya r en o te f f i c i e n ti nm u l t i r a d i o m u l t i c h a n n e ln e t w o r k s ，s i n c et h e yd on o tc o n s i d e ri t su n i q u ec h a r a c t e r i s t i c s i nt h i s p a p e r ，w es t u d yt h ee f f i c i e n tb r o a d c a s t i n gp r o b l e mu n d e rt h em u l t i r a d i om u l t i c h a n n e l a n dm u l t i h o pe n v i r o n m e n t w ep r o p o s e3a l g o r i t h m sw h i c hf o c u so nr e d u c i n gt h e r e d u n d a n tt r a f f i co fb r o a d c a s t i n g ，m i t i g a t i n gt h ec o l l i s i o np h e n o m e n o n ，a n di m p r o v i n g t h eb r o a d c a s t i n gc a p a c i t yr e s p e c t i v e l y b yr e d u c i n gt h eb r o a d c a s t i n gp r o b l e mi n t ot h e m i n i m a ls t r o n gc o n n e c t e dd o m i n a t i n gs e tp r o b l e mo fi n t e r f a c e e x t e n d e dg r a p h ，w e p r o p o s e a s e l f - p r u n i n ga p p r o a c h t or e d u c et h e r e d u n d a n c y u s i n g n e i g h b o r - d e s i g n a t i o na p p r o a c h ，w em i t i g a t et h ec o l l i s i o n sp r o b l e mb yc o m p a r i n gt h e b r o a d c a s tr o u t e sh i s t o r y w ea l s op r o p o s e dac o n f l i c t - f l e eb r o a d c a s ts c h e d u l es c h e m e ， w h i c ha i m sa ti m p r o v i n gt h et h r o u g h p u to ft h en e t w o r k s ，b yu s i n gd e p t h f i r s ts e a r c h t e c h n o l o g yt oc o n s t r u c tt h eb r o a d c a s tt r e e t oe v a l u a t et h e s ea l g o r i t h m s ，w ee x t e n dc u r r e n tn s 一2n e t w o r ks i m u l a t o rb ya d d i n g m u l t i i n t e r f a c es u p p o r tf o rt h em o b i l en o d e w ei m p l e m e n to u ra l g o r i t h m sa n de v a l u a t e t h e mu n d e rd i f f e r e n tc o n d i t i o n s s i m u l a t i o nr e s u l t ss h o wt h ee f f i c i e n c i e so fo u r a p p r o a c h e s k e yw o r d s ：m u l t i - c h a n n e l ， m u l t i h o p ，w i r e l e s sn e t w o r k ， b r o a d c a s t ， r e d u n d a c y 第i i 页 国防科学技术大学研究生院学位论文 图目录 图1 1 对比单信道和多信道的不同3 图2 1 抽象层次一9 图3 1 多信道下的本地广播15 图3 2 本地广播的贪婪算法过程1 5 图3 - 3 连通支配集与无线网络广播1 7 图3 4 基于连通支配集的广播17 图3 5 四个信道六个节点的多信道网络1 8 图3 6 减少冗余算法的问题描述2 0 图3 7 接口扩展图2 2 图3 8 静态的脚策略2 3 图3 9 动态m c s p 算法2 4 图3 1 0 冲突表示2 5 图3 1 1 七个节点三个信道的网络拓扑2 5 图3 1 2 集合关系表示2 6 图3 13 减少冲突的广播过程2 9 图3 1 4t o k e n 消息的操作3 3 图3 15a d o p t i o nn o t i c e 消息的操作3 3 图3 16u n av a i l a l ef o ra d o p t i o n 消息的操作一3 4 图3 17 调度过程示例3 5 图3 18 最终调度生成的广播树3 6 图3 1 9 ( a ) 转播节点数与网络密度的关系一3 6 图3 19 ( b ) 平均广播冗余与网络密度的关系一3 7 图4 1 分裂对象模型3 9 图4 2 单接口m o b i l e n o d e 的节点结构。4 0 图4 3 扩展后的m o b i l e n o d e 的结构一4 2 图4 4 广播协议a g e n t 的逻辑图。4 5 图4 5 第m 轮h e l l o 消息的格式4 6 图4 6 携带转播信息的广播消息格式4 7 图4 7 重复消息表4 8 图4 8 消息h e l l o 的格式4 8 图5 1 ( a ) d e l i v e r yr a t i o 和网络密度的关系5 l 第1 i i 页 国防科学技术大学研究乍院学位论文 图5 1 ( b ) a v e r a g ed e l i v e r yc o s t 和网络密度的关系5 2 图5 1 ( c ) a v e r a g ed e l i v e r yd e l a y 和网络密度的关系5 2 图5 2 ( a ) d e l i v e r yr a t i o 和接口数的关系5 3 图5 2 ( b ) a v e r a g ed e l i v e r yc o s t 和接口数的关系5 4 图5 2 ( c ) a v e r a g ed e l i v e r yd e l a y 和接口数的关系5 4 第i v 页 独创性声明 本人声明所呈交的学位论文是我本人在导师指导下进行的研究工作及取得的研 究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已 经发表和撰写过的研究成果，也不包含为获得国防科学技术大学或其它教育机构的学 位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文 中作了明确的说明并表示谢意。 学位论文题目：垒焦遒垒逃丞绫圈终亡搔狃剑鲍盟窒 学位论文作者签名：番盘西 日期：z 加罗年多月丘如 学位论文版权使用授权书 本人完全了解国防科学技术大学有关保留、使用学位论文的规定。本人授权国 防科学技术大学可以保留并向国家有关部门或机构送交论文的复印件和电子文档，允 许论文被查阅和借阅；可以将学位论文的全部或部分内容编入有关数据库进行检索， 可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。 ( 保密学位论文在解密后适用本授权书。) 学位论文作者签名： 笸! ! 鹭日期：加叼年多月丘i 一日 作者指导教师签名： 趁垒塑一 日期；加毋年f 月丛勺 国防科学技术大学研究牛院学位论文 第一章绪论 随着移动通信技术、计算机网络技术的不断进步，以及因特网的迅猛发展， 为用户提供包括访问因特网在内的各种信息服务已成为技术研究的一大热点。多 跳无线网络作为一种新型网络，与传统的无线网络必须首先访问接入点( a p ) y j 能 进行无线连接不同，在多跳无线网络中，每个节点都可以与一个或者多个对等节 点进行直接通信，因此得到了广泛的关注和应用。 然而随着应用范围的进一步扩大，最初设计的单接口单信道多跳无线网络网 络容量已经很难满足人们的需要，新的多跳无线网络即多接口多信道多跳无线网 络这种通过利用更多频谱资源获取更大网络带宽容量的多跳网络成为新一轮 研究的热点。 1 1 1 多跳无线网络简介 1 1 背景介绍 无线网络中，为了支持通信设备的漫游，一般采用无线通讯方式。根据通信 方式的不同，可以将无线网络划分为单跳( s i n g l e h o p ) 无线网络和多跳( m u l t i h o p ) 无线网络。任意两个通信节点之间可以直接进行无线通信，一个通信节点发出的 讯息可被所有其他通信节点接收到，此时系统称为单跳无线网络。当两个通信节 点不在彼此无线传输范围内时，允许通过中间设备实现通信的中继，这种网络称 为多跳网络。下文若不作特别声明，所讨论的网络环境均指多跳无线网络。尽管 单跳无线网络具有简单的特点，但是无线网络的特性要求支持多跳无线网络，其 理由为，首先网络中的节点可以漫游，这意味着节点可能移动到某些节点的传输 范围之外；第二，为提高无线网络链路带宽，需要采用高频无线电，而高频无线 传输范围小，很难保证单跳通信；第三，缩小无线传输范围可以降低通信设备的 功耗，同时提高无线传输介质的空分多路复用率，提高系统的通信容量。 多跳无线网络包括移动自组织网络( m a n e t ) 【、传感器网络【2 j 、m e s h 网 络【j j 等，主要有以下特点： 网络的自组性。多跳无线网络可以不依赖于现有的网络基础设施，比如基站等， 通过节点之间的自我组织，快速构建移动通信网络。 动态的网络拓扑。动态拓扑是多跳无线网络最显著的特点。由于用户终端的随 机移动、无线发信装置发送功率的变化、无线信道间的相互干扰以及地形等综 合因素的影响，网络的拓扑结构可能随时发生变化。 有限的无线传输带宽。多跳无线网络采用无线信道的物理特性决定了它所能提 第l 页 国防科学技术大学形 究牛院学位论文 供的网络带宽相刈自线网络低很多，再加上竞争共享信道所带来的碰撞、干扰、 信号干扰等因素的影响，不仅用户终端可得到的实际带宽远小于理论值，而且 也导致了无线链路质量的不稳定。 分布式的控制。多跳无线网络中用户终端的地位平等，不存在控制中心节点， 网络的路由协议通常采用分布式控制方式，因此比集中式网络具有更强的抗毁 性和健壮性。 多跳无线网络可以和8 0 2 1 l w l a n 、8 0 2 1 6 w m a n 以及3 g 等各种无线接入 技术相结合，实现家庭、社区、企业及城域网络等的多层次、多范围的无线应用， 主要的应用场合有： 没有方便可用的通信网络设施，如在海洋或敌方战场上； 现有通信设施遭到战争、自然灾害( 如地震、洪水、火灾) 等的破坏时； 需要临时快速建立一个通讯网络的场合； 作为生存性极强的后备网络； 图书馆、酒吧等场所。 1 1 2 多信道技术的引入 随着多跳无线网络的普及，尤其是多跳无线网络在民用领域的快速发展，人 们普遍希望通过这种网络获得更多的应用服务，比如因特网接入、视频点播等。 然而有研究【4 】表明，随着路由跳数的增加以及网络密度的增大，多跳无线网络网络 性能将会快速衰减，网络容量将不能满足人们日益增长的通讯需求。造成这种情 况主要有两个原因：一方面多跳无线网络采用共享信道通信，从而面临着传输干 扰问题，这包括同一条路径上不同节点之间的干扰和不同路径之间的干扰；另一 方面网络协议开销也会产生一定影响，比如，m a c 竞争、8 0 2 1 1 协议头、 8 0 2 1 1 a c k 、包传输错误等。 因此，如何提高多跳无线网络的网络容量成为当前十分重要的课题，目i ； 主 要的研究集中在提高现有协议效率和利用更多资源两个方面。 多接口多信道技术就是一种通过使用更多频谱资源改进网络容量的技术。这 种技术允许网络中每个通信节点装配多个无线电接口，每个接口可调制到不同的 信道。这样，在同一区域内使用不同信道的链路可以同时传输，并且单个结点亦 可同时进行收发操作，从而一定程度上有效地避免了信道冲突，提高了网络的吞 吐量。如图1 1 所示，单信道情况下，传输冲突造成两个传输不能同时发生，而多 信道技术下，使用不同的信道，这两次传输可以同时进行。 多信道技术的产生有着一定的必然性：首先，i e e e8 0 2 1 la 工作的5 g h z 频 段提供了1 2 个非重叠信道，而i e e e 8 0 2 1l b g 工作的2 4 g h z 频段则提供了3 个非 第2 页 国防科学技术大学研究乍院学位论文 重叠信道，这使得多信道技术的使用和研究有一定的技术基础；第二，通过使用 更多频谱资源，可以一定程度上改进当前频谱资源利用率低的现状，这也是国际 上动态频谱划分研究的热点问题；第三，多信道技术使用和多接口的引入，使得 在同一传输范围内使用不同的通信信道的操作可以同时进行，一个节点可以同时 进行收发操作，这将有利于改善网络通信延迟和传输冲突、碰撞等性能。 单信道 延迟 七一、 u 一藿蠢 传输 无冲突 图1 1 对比单信道和多信道的不同 1 1 3 多信道技术面临的问题 多无线电多信道多跳无线网络作为一种新型的网络，在设计和实现中还面临 许多新的问题和挑战。首先，单信道m a c 协议不能同时管理多个接口和信道，而 多信道m a c 协议需要解决信道分配、信道切换、信道同步、接口调度等一系列问 题。其次，多信道的使用还使网络连通性的概念发生了变化，因为处于传输范围 的两节点只有使用同一信道才能进行通讯，所以目前许多单信道协议已经不再适 合。具体来说主要的研究问题有以下几点： 信道同步。多信道环境下，发送方和接收方必须至少有一个共享的信道才可以 通信，信道同步就是使发送方预先知道接收方己监听某个信道，从而切换到该 信道。 信道分配。信道分配策略的困难之一就是连通性的约束，即传输范围内的节点 之间必须存在共享信道才能保持网络的连通性；同时信道分配策略又要满足干 扰约束条件，即为降低传输干扰，使共享同一信道的邻居节点的数目最小。显 然这二者之间存在一定的矛盾，合理的信道分配策略是解决这一矛盾的途径。 信道调度。在硬件代价比较低的理想情况下，为通信节点装配的接口( 天线) 的数目等同于网络中可用信道的数目，这是一种最优的选择。而实际情况中， 硬件代价依然昂贵，并且在相当长的一段时间内，这种情况不会改变，所以通 常为通信节点装配的接口数目要小于网络中可用信道的数目。在这种情况下， 第3 页 国防科学技术大学研究生院学位论文 合理地调度信道是提高信道利用率避免冲突的关键。 跨层次的路由技术。多信道技术使网络连通性的概念发生了变化，所以信道分 配状况会影响网络的拓扑结构，从而影响路由的选择；而反过来路由的选择影 响了网络负载，需要信道分配动态适应之。以m a c 层路由层联合设计的跨层 次协议设计技术是目前多信道技术研究的热点之一。 其中路由技术作为多跳无线网络的关键技术之一，也是多跳无线网络的研究 热点。通常路由问题主要是指点点路由，组播路由和广播路由三个基本的路由问 题。广播实现1 t o - a l l 通信，它不仅是许多无线应用中的重要通信手段，还是单播 路由协议中路由发现的基本方式以及维持多播路由的多播树和多播关系的有效工 具，因而必须为之寻求有效的解决方案。然而多接口多信道技术的使用为广播技 术提出了新的要求：一方面单信道网络的广播协议缺乏对接口和信道的有效管理， 简单地在多接口多信道网络中应用，会产生额外的冗余和冲突；另一方面多信道 网络中单个信道覆盖节点数目减少，又将有利于减少广播冗余，同时多信道的使 用可以避免了过多节点同时竞争一个信道，将有利于消除信道冲突，因而多信道 广播协议需要结合接口和信道的管理进行设计。 多无线电多信道技术的引入带来了机遇和挑战，本文的主要研究集中在多信 道广播算法的设计上。 1 2 本文工作 由于广播操作在多接口多信道多跳无线网络中的重要性，本文的主要工作集 中在广播技术的研究上，具体包括下面三个方面。 1 ) 深入分析多接口多信道多跳无线网络广播问题，分别从减少广播冗余、消除 传输冲突、提高网络吞吐量三个角度，设计了广播算法。 2 ) 在n s 2 网络模拟器上，扩展了对多信道多接口模拟环境的支持。当前的n s 2 版本不支持多信道多接口协议模拟，本文成功扩展了对多接口多信道的支持， 为多信道广播协议以及其它协议模拟提供了一个平台。 3 ) 将广播算法以协议的方式在n s 2 上模拟，通过对传输可靠性、传输的耗费以 及平均延迟的考察，对算法性能进行分析。 1 3 论文结构 本文共分七章。各章节的内容概述如下： 第一章为绪论，论述了本文的研究背景、研究目标以及研究的主要内容，并 介绍了在研究中所做的工作。最后给出了本论文的组织结构。 第4 页 国防科学技术大学研究生院学位论文 第二章为多接口多信道相关技术的研究。分别从多接口多信道m a c 协议、路 由技术、广播技术三个方面简单介绍了当i j 多接口多信道技术的主要研究内容和 已取得的成果。 第三章为多信道广播算法的设计。首先分析了多信道无线网络本地广播和全 局广播面临的基本问题，然后针对不同的研究目的设计了具体算法。我们将广播 问题归结为接口扩展图的最小强连通支配集问题，使用自剪枝的策略达到减少冗 余的目的；通过比较历史转播信息，我们使用邻居指定策略消减传输冲突。使用 深度优先遍历的策略，我们通过构造一棵无冲突的广播树进行广播调度达到提高 广播容量的目的。 第四章分别从扩展的思路和方法上重点介绍了对n s 一2 网络模拟器的多接口扩 展，而后介绍了在此基础上的广播协议简单实现，为第五章性能评测提供了基础。 第五章对以算法为基础的广播协议性能进行分析。 第六章对本文的工作进行了总结，并对下一步的工作进行展望。 最后是致谢和参考文献。 第5 页 国防科学技术大学研究生院学位论文 第二章相关技术的研究 本章主要从以下几个方面介绍多信道技术当前的研究现状： 多信道m a c 协议的研究 多信道路由技术的研究 多跳无线网络广播技术的研究 2 1 多信道m a c 协议的研究 多信道m a c 协议是将信道的分配、调度与介质访问联合设计考虑的一种技 术。因此，与单信道m a c 协议不同，多信道m a c 协议除了决定何时发送分组报 文以外，还要作出使用哪条信道传输的决定。在本节，首先介绍多信道环境下介 质访问控制的研究的重点，而后介绍当前多信道m a c 协议所作的一些工作。 2 1 1 多信道环境下m a c 协议的研究 2 1 1 1 信道分配策略 在多信道网络中，信道分配策略的优劣是网络能否获得高效的信道利用率的 关键。最理想情况下最优的信道使用是将网络的负载平均地分配到各个信道上， 而显然这不可能成为现实，但是优秀的信道分配策略将能够有效地提高信道的使 用效率。 当前信道分配策略可以划分为静态信道分配策略、动态信道分配策略和混合 式信道分配策略三种。 1 ) 静态分配策略：静态分配策吲6 】【7 】是指为每一个接口分配一个固定的信道。这 种分配固定不变或者保持一个相对较长的时间间隔才会发生改变( 相对较长 的时间间隔是指对于信道的切换延迟和分组的传输时间来说的) 。具体来说， 静态分配策略又可以划分为两种：一是公共信道分配策略【6 】。这种策略把所有 节点的接口映射到一个公共的信道集。对于这种策略，如果节点接口数目远 小于网络中可用信道的数目，就必然会造成信道资源的浪费。二是多样化的 信道分配策略【_ 7 1 。与公共信道分配策略不同，节点的接口可以映射到不同的信 道集合。这种策略可能会造成网络连通性的下降和某一些路由的步数可能增 长。当网络中信道切换延迟比较大或者可用信道数目等同于节点接口数目时， 静态信道分配策略是一种理想的策略。这种策略下，节点通信之前不需要进 行信道同步。 2 )动态信道分配策略。动态的信道分配策略允许节点的每个接口被分配给网络 第6 页 国防科学技术大学研究生院学位论文 中的任意一个可用信道，并且在通信过程中，允许接口频繁地从一个信道切 换到另外一个信道。这种策略适合于信道切换延迟比较小的情况，它能够使 用整个网络中的所有信道。但是，这要求两个节点通信前，必须进行信道同 步。 3 ) 混合型信道分配策略。动态信道分配策略，需要解决信道同步问题，这需要 解决包括时钟同步等一系列的问题，难度比较大。混合型策略则是将节点的 一部分接口按照公共接口分配策略或者多样化信道分配策略进行分配，其余 的接口针对网络中剩余的信道使用动态分配策略。文章【8 】给出的就是混合型策 略，它将节点的接口划分为固定接口( 公共接口分配策略) 和可变接口，信 道同步转变为发送端的接口信道和接收端的固定接口信道的同步，这无疑能 够降低信道同步的开销。 2 1 1 2 信道同步问题 在使用动态信道分配策略和混合型信道分配策略的时候，信道同步成为必须 要解决的问题。信道同步是指当两个节点之间相互通信的时候，必须在某个时刻 使两个节点之间至少存在一对接口装配在同一条信道上。信道同步也是单信道 m a c 协议，比如i e e e8 0 2 1 1d c f 等，不能直接使用在多信道环境下的主要原因 之一。 目前主要有三种策略用于解决信道同步问题： 1 )明确信道切换的原则，节点的信道切换信息能够被邻居节点或者网络中的所 有节点获得。例如，节点a 的接口在信道2 和信道3 之间每隔l o o m s 切换一 次，这个规律被它的邻居节点b 获得，那么节点b 需要和节点a 通信时，就 可以通过这个规律，在某个时刻选择信道2 或者信道3 ，而不需要通过和节点 a 进行匹配。但是很显然，这种策略需要严格的时钟同步，而在无线网络中 所有节点时钟同步也是一件十分复杂的工作。 2 ) 协商型的策略。这种策略允许节点的接口被分配给任意的信道，但是网络中 所有节点必须遵循一个原则，即周期性地节点的某个接口( 或者某几个接口) 都要在同一个信道上停留一段时间。在这个时间段内，节点协商什么时候通 信，使用哪个信道。很显然这种策略也有时钟同步的要求。 3 ) 网络中的每个节点都可以按照自己的切换原则调度信道切换，但是每次接口 信道发生变化，都需要通知邻居节点这次变化。这样每个节点对自己能够直 接通信的节点的信道使用情况明了，不再需要另行的匹配和严格的时钟同步。 但是显然这种策略网络通信的代价十分昂贵，适合于接口信道切换不是十分 频繁的网络。 2 1 1 3 信道调度问题 第7 页 国防科学技术大学研究生院学能论文 多信道环境下，节点向多个邻居节点发送报义，可能需要经过不的信道。 具体使用哪个信道发送，就是信道调度策略研究的问题。信道调度对于网络的吞 吐量、平均分组延迟以及延迟的变化有着很大的影响，目前主要有以下几种策略： 固定的调度策略。这是一种最简单的调度策略，它要求节点的接口对所有信道 周期性地切换。每切换到一个信道，有分组通信请求就进行操作，没有则进行 切换。显然这种策略，没有考虑网络中的具体负载情况，容易造成某个网络中 的分组延迟过高，同时信道的利用率也不高。 基于分组的调度。这种调度是通过对接口队列中的分组将要使用的信道进行比 较，选择高速信道优先调度。这种策略可能造成低速信道的分组延迟过高甚至 饿死。 先到先服务策略。这种策略对于信道按照先到先服务的原则进行调度，但是最 坏的情况下，节点每发送一个分组就需要进行一次信道的切换，无疑将会增加 平均分组延迟，影响网络的性能。 等待受限的调度。给每个信道分配一个等待时间。接口在某个信道直到超过等 待时间时进行切换，切换到等待时间较长的信道工作。这样一方面可以使高速 信道优先工作，另一方面可以避免低速信道延迟过大或者饿死。 2 1 2 多信道m a c 协议研究现状 目前国内外多信道m a c 协议的研究，按照同步方式得不同主要可以分为四 类： 第一类是使用专用控制信道的多信道m a c 协议【9 】【1 0 】i l l 】。这类协议要求节点至 少装配两个以上的无线电接口，并且要将其中一个接口固定到一个公共控制信道。 这类协议的优点是可以保证节点在分组交换的同时监听控制信息，易于同步。缺 点是协议效率受限于控制信道的冲突和用于数据交换的信道的数目。 第二类是使用公共跳转策略的多信道m a c 协议【l l j 【1 2 1 【1 3 1 【1 4 】。这类协议要求接 口在各个信道之间周期性地切换，直到达成传输约定后暂停切换，直到完成数据 传输才继续切换。这种m a c 协议的优点是可以使用了更多的信道用于数据交换， 缺点是频繁的切换会造成同步的困难和链路传输延时的增加。 第三类是使用时分策略的多信道m a c 协议【1 5 】【1 6 】【17 1 。这类协议一般只使用一 个接口，将单位时钟划分为控制段和数据段的序列。在控制段，接口切换到控制 信道，为数据段的数据传输发送控制报文达成约定。在数据段，接口按照约定切 换到数据交换信道进行数据传输。 第四类是使用并行聚合策略的多信道m a c 协议f 1 8 】f 1 9 】。这类协议中，所有信 道都既是控制信道又是传输信道，多个节点可以同时在不同的信道上达成传输约 第8 页 国防科学技术大学研究生院学位论文 定并完成传输。使用这类协议信道的利用率比较高，但是同样面临着严峻的同步 问题。 2 2 多信道路由技术的研究 路由技术是多跳无线网络研究的热点之一，它通常可划分为多个子问题，包 括基本路由问题、q o s 路由问题、不同通信模式下的路由问题、路由中的安全问 题等。其中基本路由问题包括广播路由、点点路由和组播路由等。当前多信道路 由技术研究的主要是路由的基本问题，研究的根本目标是提高网络的吞吐率。 与单信道不同，由于多信道技术的特殊性，高效的多信道路由不仅仅是为节 点选择通信路径的问题，还要考虑信道调度的问题。上节已经提到信道调度是属 于m a c 协议设计需要考虑的问题，因此一个完备的多信道路由协议需要同m a c 协议相结合，跨层次的路由协议设计是多信道路由技术研究的重点。 2 2 1 跨层次的协议设计 在单信道路由协议设计中，路由长度、信号强度、稳定性、期望传输时间等 作为研究主要的参考目标。而在多信道路由协议设计中，网络容量以及网络负载 平衡成为协议设计另外的研究目标。 多信道环境下，网络负载平衡是指网络负载( 流量) 能够均匀地分布在各个 信道上。在实际过程中，由于各种条件的限制，完全的负载平衡很难做到，但是 一定的平衡是可以通过控制实现的。 u s e r u s e r s p a c ed a e m o n ： a p p l i c a t i o n s r o u t i n e ，l m e r t h c em e m t l i y i i ( 、p i 裟蒜高 il p i i if li n kl a y e r ：i n t e r t h c em a n a g e m e n t l i n t c r i h c c | i n t c r l h c c 图2 1 抽象层次 u , i e r s p a c e k e m e l - - - - - - - - - - d a t ap a t h 一一一一( ：o n t r o lp a t h 跨层次的路由协议设计就是以平衡负载、提高网络吞吐率为目标进行设计的。 以负载平衡为目标，负载的变化会使信道的使用优先发生变化，进而影响信道的 第9 页 国防科学技术大学研究生院学位论文 分配调度。信道分配发生变化会造成例络的拓扑改变，拓扑的改变进面会造成路 由选择的变化。路由选择将会很大程度上影响网络负载，因此会造成网络负载的 变化。这是一个相互影响，相互制约的过程。跨层次的路由协议设计就是要将通 信路径的选择和m a c 层信道分配、切换相结合，动态进行控制以达到平衡负载、 提高网络吞吐率的目的。 目前多信道路由与m a c 协议的跨层次设计的一种典型实现是通过在网络层 和物理层之间构建一个逻辑层次，称为链路层或者接口管理层弘j ，如图2 1 所示。 这个逻辑层次主要实现的功能是实现对信道的分配、调度以及信道切换的管理等。 抽象出接口管理层能够简化跨层次交互，减少跨层次协议设计的复杂性，使接口 和信道的管理对上层协议透明，避免上层协议直接参予到物理层的管理中。 2 2 2 路由标尺的设计 单信道下的路由技术不能为多信道所用，关键在于标尺设计没有针对多信道 的网络特性。以a o d v 和d s r 协议为例，两者都是以最小路由路径长度为设计目 标，但是它们不能区分节点传输使用的信道，不能对信道的使用有效地控制。提 高网络吞吐量，需要尽可能地充分利用多个信道以减少路由路径中的信道冲突， 这就是路由尺度设计的第一个目标路由中的信道多样性。另外对于允许信道动态 切换的多信道网络来说，路由标尺的确立还应该考虑信道切换带来的影响。过多 的切换将增加网络分组传输的延迟，会对网络性能造成伤害。 因此，合理全面的多信道路由标尺应该兼顾链路质量、信道多样性等多个方 面，设计多信道路由标尺也成为多信道路由技术研究的重点和难点之一。下面介 绍几种研究比较多的路由标尺。 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 ) 2 0 】。e t x 的最早是在单接口单信道网 络中针对单播提出，它引入探测消息( p r o bp a c k e t ) 的概念，考虑链路质量的 因素对路由的影响。 w c e t t ( w e i g h t e dc u m u l a t i v ee x p e c t e dt r a n s m i s s i o n t i m e ) 1 6 1 ow c e t t 是 专门为多接口多信道无线网络设计的一种路由标尺。它由反映链路质量的期望 传输时间之和( c e t t ) 、反映信道多样性的信道切换丌销( b e t t ) 以及随即 因子1 3 三部分构成，具体表示如下： m 叩玎= ( 1 一) c e t t + 雎玎 m c r ( m u l t i c h a n n e lr o u t e ) 【5 】【8 】。m c r 路由标尺是在w c e t t 路由标尺上 改进而来，它最突出的贡献在于将转播信道的选取同信道的负载平衡联系起 来，提出了将网络负载均匀分配在各个信道上的方法。 第1 0 页 国防科学技术大学研究生院学位论文 2 3 多信道广播技术的研究 多信道广播技术尚处于研究当中，目前还没有专门为多接口多信道多跳无线 网络设计的广播协议。最简单的广播途径是泛洪，它不需要网络节点维护与路由 相关的状态信息，协议开销小。泛洪不只可用于广播通信，还可用来传递单播消 息或组播消息以获得高可靠性。多接口多信道泛洪的基本思想是：在广播过程中， 当节点首次收到一个广播消息时，将此消息的拷贝放入每个信道队列中进行转播。 使用多信道泛洪广播技术，将会使网络中充斥大量传输冗余和信道碰撞，尤其信 道数目较多时，会造成网络吞吐性能会急剧下降。 在下面两节中分别重点介绍单信道广播技术和多信道的广播技术。 2 3 1 单信道广播技术 单信道广播技术的研究主要是解决泛洪广播带来的“广播风暴”问题。广播 风暴【2 l j 是指单信道泛洪带来的大量的广播冗余，将会造成大量的带宽竞争、冲突。 因此解决广播风暴问题，最根本的是减少广播冗余。目前单信道技术下减少广播 冗余主要有下面几种方法。 第一种是基于泛洪的广播策略。尽管泛洪广播具有较大的网络开销，但它亦 具有简单、易实现的优点，因而基于泛洪的基础上提出改进办法是研究中的重要 途径。下面给出两种研究策略。 基于概率的方法【2 l j l 2 2 。当节点收到非重复广播报文时，以概率p 转发该报文， 以概率1 - p 丢弃该报文，其中p 值的选取受到网络度数、节点度数等因素的影 响，选取策略的好坏是决定算法优劣的关键。这类算法简单有效，具有良好的 可扩展性和容错性，但是转发概率p 的确定策略以及广播可靠性的确保是其瓶 颈，有待解决。 基于覆盖范围的方法l z 。作为转发节点的接收节点的覆盖范围应当与发送节点 覆盖范围重合越少越好。研究表明，接收节点距离发送节点越远，其重复覆盖 越少；位于发送节点覆盖边缘的接收节点重复覆盖范围最小，只占整个覆盖范 围的3 3 。因此该类策略的目标是选择距离发送节点较远的节点作为转发节 点。但是很明显这类策略仅仅考虑了传输范围，而没有考虑非重复范围内的节 点数目，性能受到拓扑变化的影响很大。 第二种是基于簇的广播技术【2 1 1 1 2 3 1 。泛洪协议可以直接应用于平坦结构的无限 网络，面对具有层次结构的网络，可以利用簇和层次结构更有效的实现广播。以 基于簇的网络为例，假定网络具有两个层次，即簇首和簇成员两级。假定簇的半 径为l ，即每个簇成员均可与簇首直接相连。当一个节点发送广播消息时，若它是 第1 1 页 国防科学技术大学研究乍院学f ：论文 簇成员，则将消息传递给簇首。簇首通过无线广播的方式将消息传播给簇内的所 有节点，同时通过点点传输或广播的方式将消息传输给相邻簇的簇首。相邻簇首 收到非重复广播消息以后，采取同样的广播和转发操作。因而这种途径减小了广 播的丌销，尤其适合于网络节点较为稠密的场合。 第三种是基于连通支配集的广播技术【2 4 j 【2 5 】【2 6 】【2 7 】【2 8 】【2 9 】。单信道无线网络中全局 广播问题可归结为最小连通支配集问题。根据构造方式的不同，具体又可分为邻 居指定和自剪枝两种。如果一个节点是否是转播节点，由邻居转播节点来确定， 这就是邻居指定策略；如果节点根据邻居拓扑信息，决定自己是否转发广播，这 就是自剪枝策略。通常来说，邻居指定策略的计算开销大，获取信息更加全面， 连通支配集更小；自剪枝策略直观便于理解，同时也能有效地减少转发节点的数 目。基于连通支配集地广播技术可以有效地减少冗余，消除一定程度的碰撞、冲 突，对于稠密节点环境效果更好。 2 3 2 多信道广播技术 单信道广播技术不能直接应用于多信道广播中，主要有两方面原因：一方面 多信道广播技术不仅仅需要选择转播节点，同时需要为转播节点选择转播信道， 这在单信道广播技术中是没有考虑的；另一方面，多信道技术可以通过对转发信 道的选取或者调度达到有效提高网络的广播容量，这在单信道广播技术中更没有 涉及。因此研究新的多信道广播技术成为必然。 目前，关于多