（计算机软件与理论专业论文）无线自组网络mac层链路调度算法设计.pdf

硕士毕业论文( 刘恒昌) 中国科学技术大学汁算机系 摘要 随着通讯与汁算技术的不断发展，无线自组网络( 无线a dh o c 网络) 正在发 挥越来越重要的作用，其目标是使信息可以在“所有时间，所有地点”进行交互。 它跟目前的4 晕窝网络最大的区别在于，与蜂窝网络的集中式结构不同，无线自绷 网络采用一种松散的，自组织的结构，这种结构使得无线自组网络在许多应用l 。 有非常广阔的前景，例如端对端通信网络和传感器网络。 在无线a dh o c 网络设计中有许多重要问题，其中一个就是如何优化物理层， 数据链路层与网络层的资源( 带宽，时间片等) 分配算法，使得在满足刚络层传 输速率的同时可以减少整个网络的资源消耗。在t d m a 介质访问控制协议中，传 输过程被分为不同的离散时间片来完成，每个要传输数据包的链路分配一个特定 时间片。一个对7 f d m a 机制的有效改进方法是窄分t d m a 机制，它将无线节j ? 、i 之阳 的物理距离考虑在内，规定互相不干扰的通讯链路可以在相同的时间片内传输， 从而减少了网络所需时i 刈片的总量，从而提高了单位时间内可传输数据包的数 量，即提高了整个网络的吞吐量( t h r o u g h p u t ) 。于是，在目前t d m a 机制的无线 网络巾，一个非常重要的问题是，在空分t d m a 机制下，给定路由信息与网络负 载的条件，通过对m a c 层进行链路调度来最人化网络的吞吐量。 此问题的难点在于，由于其蕴含数学问题的复杂性，之前的研究- e # i j 对丁实 际规模的网络并不适用。绝大部分方法在网络中有2 0 3 0 个结点，1 0 0 2 0 0 条 链路时就需要花几天甚至更多的时间来寻找最优调度。而这在实际应用中是完全 不可行的。因此，非常有必要继续研究和探索这一领域的新理论和新方法。 木文通过运筹学中的规划理论对此问题进行建模，利用改进后的c o l u l l l r g e n e r a t i o n 方法对网络吞吐量进行优化。实验结果表明此方法在实际规模的网 络中也能在可控制时问内得到最优解；同时，文中还提出了一种简单易用的贪心 算法，并对这两种方法进行比较。此外，作为前述问题的延伸，本论文还深入地 探讨了吞吐量与延时( d e l a y ) 的组合优化问题，目的是设计更加有效而实用的算 法来推动s t d m a 机制在无线多媒体流中的应用。 奉论文中有特色的工作体现在如卜几个方面：1 利用s e tc o v e r i n g 规划与 c o u l i l r lg e n e r a t i o n 方法将有效地解决了实际规模网络中链路时间片分配问题； 2 有效改进c o h m ng e n e r a t i o n 方法的优化过程，使其收敛性大大改善，进一 步缩短了寻找最优调度所需时间；3 给出了一种适用于大规模网络的贪心算法， 并对两种方法进行比较；4 为吞吐量一延时组合优化问题指明了可行研究方向， 以拓展对这一研究领域的探索，促进s t d m a 机制在实际应用中的发展。 关键字：无线自组网络；空分t d m a 机制；链路调度；c o l u m ng e n e r a t i o n 方法 组合优化；模拟退火。 第2 页 硕l 毕业论文( 刘恒昌)中国科学技术大学计算机系 a b s t r a c t o v e rt h ep a s tf e wy e a r s ，w i r e l e s sn e t w o r k i n gt e c h n o o g ie sh a v em a d ev a s t f o r a y si no u rd a i1yl i v e s i nt h ist h e s is w ec o n s i d e rt h er e s o ur c e o p t i mjz a t i o np r o b e mt om a x i m i z et h en e t w o r kt h r o u g h p u tb ye f f i c i e n t ly u s i n g i ，h en e t w o r kc a p a c i t y ，w h e r em u l t i h o pf u n c t i o n a l i t ya n ds p a t i a i f d m a ( s t d m a ) a c c e s ss c h e m ea r eu s e d t h eo b j e c t i v eist of i n dt h em i n i m u l l f r a m el e n g t hwjt hg iv e nt r a f f i cd is t r i b u t i o n sa n dc o r r e s p o n d i n gr o l l t in g i n f o r m a t i o n b e c a u s eo ft h ec o m p e xs t r u c t u r eo ft h eu n d e r l yin g m a t h e m a t i c a lp r o b l e m ，p r e y i o u sw o r ka n da n a y s isb e c o m ei n t r a c t a b l ei f e r n e t w o r k so fr e a l is t i cs i z e s w ea d d r e s st h ep r o b l e mt h r o u g hm a t h e m a t i c a lp r o g r a r r 【f i 】in ga p p r o a c h ，d e v e l ( ) p t h el i n e a ri n t e g e rf o r m u f a t i o no p t i m i z i n gt h en e t w o r kt h r o u g h p u t ，a n d t h e ns h o wt h es i m il a r i t yb e t w e e nt h eo r i g i n a lp r o b l e ma n dt h eg r a p he d g e c o l o r i n gp r o b e mt h r o u g ht h ec o n f li c tg r a p hc o n c e p t w ep r o p o s eac o 】u m n g e n e r a t i o ns 0 1 u t i o na p p r o a c ha n dm a k es e v e r a le n h a n c e m e n t si no r d e rt o f a s t e ni t s c o n v e r g e n c e n u m e r i c a lr e s u t s d e m o n s t r a t et h a tt h e t h e o r e t i c a l1i m ito f t h et h r o u g h p ulc a nb ee f f i c i e n t l yc o m p u t e d r n e t w o r k so fr e a is t i cs iz e s a st h ee x t e n s i o no ft h i ss c h e d u lin gp r o b e m ，w ei n v e s t i g a t ed e e p ya b o u t t h ej o i n to p t i m i z a t i o no ft h r o u g h p ula n dd e l a yt i m ei ns t d m aw i r e l e s s n e t w o r k s i ti sm o t i r a t e d b y t h ew i r e l e s s m u lti m e d j as t r e a m in g a p p i c a t i o n sa n dm o r ec o m p u t a t i o n a l l yp r o h i b j t i v ef o rn e t w o r k so f r e a li s t i es i z e s w ed e f i n et h i sp r o b l e m c l e a r l ya n da n a ly z et h eu n d er lyin g m a t h e m a t i c a ls t r u c t u r ei no r d e rt og e tah e u r is t i cs o h t i o n 7 l h ep r o p o s e d m e t h o di sb a s e do nt h es i m u l a t e da n n e a li n ga p p r o a c h t h ec o n t r i b u t i o no fo u rw o r kjsf o u r f 0 1 d f i r s t l y w es h o w t h a t t h i s c e r t a i np r o b l e mc a nb ee f f i c i e n t l ys o v e db ys e tc o v e r i n gp r o g r a m m i n g f o r m u l a t i o nc o u p l e dw i t hac 0 1 u m ng e n e f a t i o na p p r o a c h s e c o n d l y ，w e p r e s e n ts e v e r a lp r a c t i c a te n h a n c e m e n t st or a s t e nt h ec o n v e r g e n c eo ft h e c o l u m ng e n e r a t i o np r o c e s sa n dt h e s ei m p r o v e m e n t sa r eh e u r i s t i ce n o u g ht o b ea p p li e di no t h e rc o r r e s p o n d i n gp r o b i e r o s t b ir d y ，ag r e e d ya l g o r li b m i sp r o p o s e d ，e v a l u a t e d ，a n dc o m p a r e dt 。t h eo p t i m i z a t i o nm e t h o d f ir l a l y ， t h et h r o u g h p u td e l a yj o i n to p t i m i z a t i o ni sd e e p l yi n v e s t i g a t e d k e y w o r d s ：1in ks c h e d u l i n g ，s t d m a ，w i r e l e s sn e t w o r k s ，m a t h e m a t i c a m o d e li n g ，c o u m ng e n e r a t i o n ，s i m u l a t e da n n e a li n g 第3 砥 。堡望、业堡兰! 型堕曼! 鬯型堂垫查查兰盐要! ! 墨 l序论 本章首先对本论文选题的原因和背景进行了总结和归纳。之后，介绍了全文 的研究目的和研究方案。然后我们对本论文的主要贡献进行介绍。最后是本论文 的结构安排。 近年来，无线通信技术得到了飞速的发展，移动电话和无线互联网用户激增， 无线网络变得无处不在 4 。目前主要有以下四种类型的无线网络，第一类是目 前应用最j 泛的蜂窝网( e e l l u l a rn e t w o r k s ) ，包括2 g 和正在酝酿推出的：3 g 。 它只在第一跳或者最后一跳是无线，也即使用无线接入。第二类是无线局域网 ( w j t e l e s sl o c a la r e an e t w o r k s ，w - i 。a n ) ，wl a n 是仅限于一跳范围的无线网 络，目前也作为蜂窝网之外的一种主要的无线接入手段。第三类是利用卫星链蹄 的卫星刚络( s a t e l l i t en e t w o r k s ) 。第四类，电即本文的研究对象，是移动自组 网( m o b i l ea d i l o cn e t w o r k s ，m a n e t ) 6 ，7 ，1 3 ，1 4 ，也称为无线自组网( w l r 。】( 2 s s a dh o cn e t w o r k s ) 。物理上，移动自组网由一些地理位置分散，可移动，共享无 线信道的节点( n o d e ) ，有时也称站点( s t a t i o n ) 组成。与其它类型的无线嘲络相 比，移动自组网的最显著特征就是没有一个固定的网络基础设施。整个网络完全 由移动节点构成，并在需要的时候动态创建。基= j 二无线信道利用率和节能方而的 考虑，一个节点可能不能直接与它的目的节点进行通信，而需要其它节点帮助转 发，通过多跳才喃达到目的节点。在移动自组网中，每个节点既是终端( 业务源) ， 又是路由器( 为其它节点转发分组) 。网络不依赖于某一个节点，随着节点的加入 和离j 一，网络自动进行相应的调节。因此，移动自组网具有较高的灵活性和抗毁 性，非常适合在敌对的环境( 战场，地震，咫风等等) 中应用：另外，由于无线局 域网的覆盖范围有限，最近也出现了一种将其扩展为多跳移动自组网的趋势。 a dh o c 网络又叫自组织网络、多跳网络，是种由一些带有无线收发装置 的移动节点组成的多跳临时自治系统。不同于有中心的集中式控制蜂窝移动通信 系统，a dh o c 网络是一种有特殊用途的对等式刚络，网络中各节点相互作为其 邻居节点的路由器，通过节点转发实现节点问通信。随着无线通信技术和移动终 端技术的发展，a dh o c 网络在军用和民用等领域的应用日益受到重视，这方丽 的研究不断展丌。由于a dh o c 网络自身的无线传输带宽受限、网络拓扑结构变 化频繁、信道传输质量较差、终端资源受限和分布式控制等特性，使得它与传统 第6 砸 2 0 0 6 5 9 碳士毕业论文( 刘恒昌)中田利学拙术人学汁算机系 的有线局域网、无线局域网以及蜂窝网络有很大的区别，目前，对它的研究主要 集中在以下几个方面 g ：有效的路由协 义、媒体接入控制( m a c ) 协议、能量消费 问题、安全性问题以及网络的q o s 机制。 开发良好的路由协议是建立a dh o c 网络的重要问题，同时也是目前的一个 研究热点和难点。传统的距离向量和链路状态路由咖议并不适用于拓扑结构高度 动态变化的a dh o c 网络。理想的a dh o c 网络的路由协议应浚具有以下性能：分 布式运行、无环路、按需运行、考虑安全性、高效地利用电池能量、支持单向链 路、维护多条路由。 a dh o c 网络的路由协议可以分为先应式路由协议和反应式路由协议两大类。 先应式路由协议通过连续地检测链路质量，时刻维护准确的网络拓扑和路山信 息。优点是发送报文时可以立即得到正确的路由。但先应式路由协议需要大量的 控制报文，丌销太大。它包括以下路由协议：d s d v ，c g s r ，w r p ，g s r ，f s r ， h s r 和z i i l s 等。反应式路由协议中的节点不用持续维护网络的拓扑结构。仅当 需要时，才查找相应的路由，这就节省了路由维护的开销，特别是当到络负荷不 是很重时，节省的开销更加可观。但查找路由会引入较大的时延，不适用于时延 敏感型应用。它包括以下路由协议：a o d v ，d s r ，t o r a ，a b r ，s s r 和c b r i ，等。 随着a dh o e 网络中多媒体应用的增加，丌发有q o s 保证的路由协议成了目前研 究的热点。 由于a dh o c 网络动态变化的网络拓扑结构以及无线信道自身的特点，在进 行数据传输时，必须使用特殊的介质接入控制子层。在有线网络应用的 c s m a c d ( 带冲突检测的载波侦听多重访问) 不适用于无线网络，因为无线网络中 存在隐藏终端( 隐终端) 的问题。目前已经提出了一些m a c 协议如：m a c a ，m a c a w ， f a m a ，d b t m a ，r i m a 和p a m a s 等协议。但是这些协议一般只适合那种网络规模 较小，移动性较弱的a dh o c 网络，并且前几个协议都没有涉及到如何节省a dh o c 网络中的能量消耗问题。 本论文考虑了另一种类型的m a c 层协议一一空分t d m a ( s p a t i a lt d m a ， s t d m a ) 。在t d m a 介质访问控制协议中，传输过程被分为不同的离散时间片米完 第7i l j j _ 埘! 士毕业论文( 刘恒昌)中田科学扯术大学汁辫：目【系 成，每个要传输数据包的链路分配一个特定时f , l 片。个对t d m a 机制的有效改 进方法是空分t d m a 机制，它将无线结点之刚的物理距离考虑在内，规定互相彳i 干扰的通讯链路可以在相同的时间片内传输，从而减少了网络所需时f h j 片的总 量，从而提高了单位时间内可传输数掘包的数量，即提高了整个网络的吞l j r 量 ( t hr o u g h p u t ) 。于是，在目前t d m a 机制的无线网络中，一个非常重要的问题是， 在空分t d m a 机制下，给定路由信息与网络负载的条件，通过对m a c 层进行链路 调度来最大化多跳网络吞吐量。此问题的难j ? 、l 在于，由于其蕴含数学问题的复杂 性，之前的研究工作列于实际规模的网络并不适用。绝大部分方法在嘲络r r l - 有 2 0 一3 0 个结点，1 0 0 2 0 0 条链路时就需要花几天甚至更多的时f h j 来寻找最优洲 度。而这在实际应用中是完全不可行的。本义通过运筹学中的规划理沦对此i f i j 越 进行建模，利用改进后的c o l u m ng e n e r a t i o i l 方法对州络吞吐量进行优化。实 验结果表明此方法在实际规模的网络中也能在可控制时i 司内得到最优解。此外， 本论文还深入地探讨了吞吐量与延时( d e l a y ) 的组合优化问题，作为前述问题的 延伸，意图设计更加有效的算法来适应s t d m a 机制在无线多媒体流中的应用。 本论文的主要贡献体现在两个方而：第一，根据调研，这是第一篇深入研究 此问题的文章，并且通过s e tc o v e r i n g 规划与c o l u m f ig e n e r a t jo n 方法将其有 效地解决；第二，提出了一些对c o l u m ng e n e r a t i o i l 方法的有效改进，使其收敛 性大大改善，进一步缩短了寻找最优调度所需时i i - j 。 现在介绍一下本论文的结构安排。第二章主要介绍了本论文的相关1 i 作， 包括a dh o c 网络的基本概念、特点以及当前研究的热点难点问题，并对a dh o c 网络中的路由机制做了一个综述：a dh o c 网络的m a c 协议研究所面临的i u 题以 及解决办法，并综述比较了当前存在的几种m a c 算法。 = 【= i 于s t d m a 技术固有的优 点，l 叮以把a dh o c 网络技术与s t d m a 接入技术结合起来进行研究，本文的主要 工作就是基于s t d m a 接入方式的无线a dh o c 网络m a c 协议的研究来优化网络性 能，此外还介绍了当前主要的吞吐量优化方案和延时优化方案。第三章主要描述 了最大化多跳网络吞吐量的m a c 层链路调度的解决方案。在第四章中，对第二章 讨论的问题做了进一步延伸与探讨，深入地分析了延时一吞吐量组合优化问题。 第五章对前几章的理论做了仿真分析。最后是全文总结与研究展望。 第8 “ 坝士辛业论殳【刘恒昌) 中国科学拙术犬半计算机乐 2相关工作 21a dh o c 网络综述 2 1 1a dh o c 网络含义 无线州络i 叮根据其结构分为有中心网络( i n f r a s tr l i c t u r en e t w o r k ) 和光叶_ f 心网络( i n f r a s t z u o t u r el e s sn e t w o r k ) 。在有巾心网络中，移动j _ | = | 户通过1 i ! i j 定 的基站进行通信，如商用移动通信系统。a dhc k ：网络是种无中心的网络。它 指廿勺是一种工作在无固定结构环境甲的白组织的无线移动网络，即m a n e 卜 m a n e 【 是自组织的，因为它几乎不需要手工配置和维护使网络内的1 ，点上作稚 起，一个m a n e t 完拿可以有能力不用在路由层配置而自发地形成m 络的结构，而 且，龉由层可以根捌节点的移动处理频繁的网络拓扑结构的重配置。n a n e t 网络 是移动的，即网络中的所有节点都可以完全自由地在空问中移动，存任f f 可时刎， 一个连接模式的建立只依赖于各个节点的位1 占干f l 它们收发器的覆盖范幽。只要书 点可以提供不同的网络接l _ l ，n a n f f t 就可以成为一个多种网络并存的异种网络。 a dh o c 网络因其灵活变化性，有着广阔的应用前景，因此t n t e r n e t 工稃工作组 ( i e t f ) 也成立了m a n e l l 工作小组，专门从事对于m a n e i 石卅究和标准化移动无线 网络中的性能优化问题。 图2 1 舭h o c 网络图例 如图2l 所示，在a dh 。c 网络中，既不需要一个固定的网络结构，也没有 第9 页 竺兰些堕二鉴型堡旦! 塑型兰丝查查堂生塑! ! 墨 专用的固定的基站或路由器作为网络的管理中心。网络中的每个节点都相当于 个移动的路由器，这些节点作为同等实体相互连接，实现信息包的转发，它们都 参与路由的发现和维护过程，从而构成了 个a dh o c 网络。与有中心网络相比 a d h o c 网络更坚固、更耐用，而且不需要提供固定的骨干设施，用户就可以伽 置和操作分组无线网。因此，a dh o c 网络主要应用在军事卜，以及一些紧急情 况，如受灾地区的通信、边远地区和勘撩等场合的通信。 在a dh o c 网络中，每个移动节点都有自己的无线收发器，使之可以存 定范围内弓其它节点通信，个节点也可同时配备几个收发装置，使得它可以连 接在固定网络上，成为与固定网络联系的一个接口。除非采用了间接通信机制， 否则一个节点是无法与在其通信范围之外的其它节l i 通信的。节点问的通信可以 通过一个节点链，链上的相邻节点是直接通信的，沿着这条链路数据就可以以“多 跳”的方式传输。因此所有节点都必须有能够路由和转发数据的能力。a d c 网络可以不需在路由层手工配置，而是白发的建立连接。而且，a dh 。cn m w r 具有的另一个优点就是具备当节点移动导致拓扑结构变化时重新配置路由的能 力。 2 i 2 a dh o c 网络起源 a dh o c 网络的起源可以追溯到1 9 6 8 年的a l o i i ai 删络和1 9 7 3 年d a r p a 丌始酬 究的分组无线电网络。i g e e 在开发 g e e 8 0 2 i1 标准时，将分组无线电劂络改称 为a dh o c 网络。a dh o c 来源于拉j 语序面上的意思是“为特定目的或场合的， 或“仅为这种情况的”。当时分组无线电网络已经用于大规模的军事和救援子j = 动 中，采用新的名字，i e e e 希望a dh o c 网络成为为特定目的而临叫组建并短期存 在的网络。需要指出的是，i e e e 8 0 2 1 1 标准定义的a dh o c 网络为仅由那些通过 无线媒质能够互相进行直接通信的站点组成f 1 1 网络，即独立的基本服务集 ( i b s s ) 。i b s s 没有接入点，为单跳a dh o c 网络，但是目前研究的a dh 。c 网络 通常是多跳的。1 9 9 7 年i e t f 成立了移动a dh o c 网络m a n e t ( m o b i l ea dh 。c n e t w o r k i n g ) 工作组，专门负责具有数百个节点的移动a dh o c 网络的算法的研究 和开发，并制定相应的标准。m a n e t 工作组的工作成绩斐然，已经制定了寸几个 i n l e i n e t 草案标准。 第1 0 砸 中国科学技术大学汁算机系 2 1 3 a dh o a 网络特点 a dh o c 网络和常见的有线固定网络、蜂窝无线网络以及无线局域网相比 具有以下特征： 1 ) 自组性。a dh o c 网络可以在任何时刻、任何地点构建，而不需要现有无线网 络环境下常用的基站等网络设施的支持，形成一个自治移动通信网络。 2 ) 动态网络拓扑结构。节点间通过无线信道连接形成一个任意的网状拓扑结构， 节点之间的连接由于节点的离丌和新节点的到达，以及节点的任意移动，加上无 线发送装置发送功率的变化、无线信道动态特性等综合因素影响下，可能导致网 络拓扑结构发生剧烈动态变化，而且这种变化是不可预测的。 3 ) 分布式控制。a dh o c 网络中所有的网络行为，包括拓扑结构的发现和消息的 传递，都必须由节点自己来完成。也就是说l 办议站功能必须集成在移动节点中， 不存在类似基站的集中刚络中心控制点，因而是一种分布式控制网络。 4 ) 安全保密性差。由于a dh o c 网络的自组性和分布式控制方式，导致易受到窃 听、拦截和拒绝服务等各种网络攻击。 5 ) 无线传输带宽受限。由于无线信道本身的物理特性，它所能提供的网络带宽相 刑有线信道要低得多。除此之外，考虑到竞争共享无线信道产生碰撞、信号衰减、 噪音干扰、信道间干扰等因索，节点可得到的实际带宽远远小于理论上的带宽值。 而且有单向无线信道的存在。 6 ) 网络的可扩展性受限。动态变化的拓扑结构使得具有不同子网地蚍的移动节点 可以同时处于一个a dh o c 网络中，子网技术所带来的可扩展性无法应用在a dh o c 网络环境中。 7 ) 终端资源受限。通常a dh o c 网络的终端都是依靠蓄电池等可耗尽能源供f 乜的 手持设备，其c p u 的处理能力和可用内存都受到严格的限制，因而在网络协议发 计时必须考虑如何节省信令开销和能源消耗。 8 ) 节点的通信距离受限。由于终端的能源受限导致发射功率的减小。因而网络中 的其他节点并不一定可以收到某节点发出的信弓。 9 ) 网络寿命短。a dh o c 网络通常是由于某个特定原因而创建的临时网络，使用 结束后，网络环境将会自动消失。因而a dh o c 网络的生存时f 刚相对于固定刚络 而言是短暂的。 第1 i 虹 硕上毕业论文( 刘恒昌)中国科学技术夫学汁算：机系 2 1 4 a dh o e 网络的应用 与蜂窝网络相比，无线a dh o c 网络具有不可比拟的优点。首先不需要到定 的基础设施( 如基站) ，无线a dh o c 网络可以被随时随地建立，可以在没有填它 通信设施，或者由于保密、费用、安全性等原因使一些设施不能被使用的情况下 使用。其次，a dh o c 网络不受固定拓扑结构的限制，具有很强的容错性和君棒 性。 无线a dh o c 网络具有j “阔的应用前景。军事行动和地震、水灾或偏远地区 的救援行动都是a dh o c 网络的传统应用领域。它也可以作为无线接入网，提供 迅速的组网能力。在本地范围内，笔记本和掌上型电脑可以采用a dh o c 的乃- 在会议中发布和共享信息。随着无线通信技术和移动终端技术的发展，a dh o c 网络在军用和民用等领域的应用曰益受到重视，这方丽的研究不断展丌。 2 1 5 国际研究机构 作为一项新颖的通信技术，无线a dh o c 网络受到国内外学术界广泛的关注。 目前，围际上在无线a di l o e 网络方面研究较为活跃的几个研究机构有： ( 1 ) 加州大学洛杉矶分校m a r i og e t a 教授所领导的“无线自适应移动性实验室” ( t h ew a m ( w i r e l e s sa d a p t i v em o b i lit v ) i 。a b ) 。研究方向包括a dh o c i 网络路“t 协议、多播协议、多跳网络q o s ，m a c 协议、功率控制、和蓝牙网络等。 ( h t t p ：w w w c s u c l ae d u n r l w i t e l e s s ) 。 ( 2 ) 康奈尔大学z y g m u n tj h a s s 教授所领导的“无线网络实验室”( w i r e le s s n e t w o r k sl a b o r a t o r y ，h t t p ：w n l e c e c o m e 1 e d u ) 。研究万向包括a di l o c 网络重构、m a c 协议、路由叭议、网络安全等。 ( 3 ) 伊利诺基大学u r h a n a c h a m p a i g n 分校n it i nv ad a y a 教授 ( h t t p ：w w w e r h e u i u c e d u 一n h v ) 所领导的a dh o e 网络研究小组( 现在伊利诺 大学u r b a n a c h a m p a i g n 分校e c e 系) 。研究方向包括a di l o c 网络的定m a c t o 议、 定向路由协议、和网络调度等。 ( 4 ) 马里兰大学s a t i s hk t r i p a t h i 教授所领导的“移动计算与多媒体实验室” ( t h em o b i l ec o m p u t i n ga n dm u l t i m e d i a 【，a b o r a t o r y ( m c m l ) ， h t t p ：w w w c s u m d e d u p r o j e c t s m c m l ) 。研究方向包括j i a y s t a r 网络路山协 议、q o s 等。 第12 页2 0 0 6 5 9 颂十毕业论文( 刘恒昌) 中国科学技术大学汁算机系 ( 5 ) 加州大学圣巴巴拉分校( 1 i g a b e c hm b e l d i n g r o g e r 教授所领导的“移d j 性管理和联网实验室”( t h em o b i l i t ym a n a g e m e n ta n dn e t w o r k in g ( m o m e n q l ) l a b ，h t t p ：m o m e n t e s u c s b e d u ) 。研究方向包括j i a y s t a r 网络路由协议、多 播协议、地址重构、安全性、q o s 、可伸缩性和适应性等。 ( 6 ) 加州大学圣克鲁兹分校j j o a r c i a l u n a a c e v e s 教授所领导的“计算机 通信研究小组”( t h ec o m p u t e rc o m m u n i c a t i o n s r e s e a r c hg r o u p h t t p ：w w w e s e u c s c e d u r e s e a r c h c c r g h o m c h t m l ) 。研究方| 司主要包括无线 网络的信道接入等。 2 1 6 a dh o c 网络当前研究的热点及难点 与传统的有线和蜂窝网络相比，a dh o c 网络没有基础设施，每个肯点都i j 能随时进入和离开网络，整个网络分和式运行。然而，传统网络中刘连接性和、i k 务传输的基本需求，在a dh o e 网络中也i 刊样需要得到满足。目前天于a dh o c 网络研究中的主要难点问题为路山协 义、服务质量、m a c 协议、能量消费、节，一、l 移动性管理、安全性问题。 1 路由协议 开发良好的路由协议是建立a dh o c 网络的重要问题，同时也是主要的研究 热点和难点。传统的距离向量和链路状态路由协议并不适用于拓扑结构高度动念 变化的a dh o e 网络。理想的a dh o c 网络的路由协议应该具有以f 性能：分g l i b 录a 路由表，从而能够构建一条从目的 节点到源节点的反向路由。当源端移动时，它会重新发起路由发现算法；如果中 间节点移动，那么与其相邻的节点会发现链路失效并向其下游节点发送链路失效 消息并一直传到源节点，而后源节点根据情况重新发起路由发现过程。n s 中，a ( ) d v 的实现组合d s r s d d s d v 协议。它既具有d s r 协议的路由发现和路由维护功能，同 时又使用了d s d v 采用的逐跳路由、序列号s h b e a c o n r 息。 d s r 是一种基于源路由的按需路由协议，它使用源路由算法而不是逐跳路由 的方法。d s r 主要包括两个过程：路由发现和路由维护。当节点s 向节点d 发送数据 时，它首先检查缓存是否存在末过期的到目的节j 瓤的路由，如果存在，则直接使 用可用的路由，否则启动路由发现过程。具体过程如下：源节点s 将使用洪泛法 发送路由请求消息( r r e q ) ，r r e q 包含源和目的节点地址以及唯一的标志号，中问 节点转发r r e q ，并附自己的节点标识。当r r e q 消息到达h f l j 节点d 或任何一个剑目 的节点路由的中间节点时 此时，r r e q “f 已一记录了从s 到d 或者中间节点的所经 过的节点标识) ，d 或陔中间节点将向s 发送路由应答消息( r r e p ) ，该消息中将包含 s 至t j d 的路由信息，并反转s 到d 的路由供r r e p 消息使用) 。此外，中间节点也司以 使用路由缓存技术( r o u t i n gc a c h e ) 来对协议作进一步优化。d s r 的优点：节点 仅需要维护与之通信的节点的路由，减少了协议升销；使用路由缓存技术减少 了路出发现的耗费；一次路由发现过程町能会产生多条到目的点的路由。d s r 的缺点：每个数据报文的头部都需要携带路由信息，数据包的额外丌销较大； 路由请求消息采用洪泛力一式，相邻节点路由要求消息n 可能发少传播冲突并 可能会产生重复广播：由于缓存，过期路由会影响路由选择的准确性。实现 的d s r 协议中，采用d s r 的节点与其它移动节点有些不同，在d s r 节t i 中，所有分 组被送到路由代理，路由信息可通过数据分组进行捎带确认。 t o r a 是一个基于链路反转方法的自适应的分布式路由算法，主要用于高速动 态的多跳无线网络作为个出源端发起的按需路由协议，它可以找到从源到一个目 的节点的多条路由。t o r a 的主要特点是：当拓扑发生改变时，控制消息只在拓扑 发生改变的局部范围传播。i * i 止c ，节点只需维护干闩邻节点的路由信息。协议由乏 第2 3m 顺= j _ = 毕业论文( 刘恒昌) 中国科学技术大学h 算。机系 部分构成：路由产生、路由维护和路由删除。初始化时，目的节点的高度( 即传 播序列号) 被置为o ，然后由源端广播一个含有目的节点i d 的q r y 分组，一个高度 不为0 的节点响应一个u p d 分组收到u p d 分组的节点的高度将比产生该u p d 分组的 节点的高度大l ，并且具有较大高度值的节点被规定为上游节点。通过这种方式 能够创建个从源到目的节点的一个有向无环路图( d a g r ) 。当节点移动时，路山需 要重建。在路由删除阶段t o r a 通过广播一个c i 。r 分纽来删除无效的路由。t o r a 存 在的一个问题是当多个节点同时进行选路和删除路由时会产生路由振荡现象。在 n s 中，每个节点为所有可能的目的节点运行一个分离的t o r a 进程。t o r a 运行在 i m e p ( i m e p ：i n t e r n e tm a n e te n c a p s u hc jo n p r o t o c o ) 之中，i m e p 主要用来提 供路由消息的可靠传送并可以向邻居节点通知链路的改变。 总的来讲，按需路由协议具有路由丌销小、存储丌销小和计算丌销小的特点， 更适合a dh o c 网络环境，优于表驱动路由协 义，也是研究的重点所在。在大量的 按需路由协议中，每种都有自己的特点和适用的范围，但缺少一种适合各种环境 的被广泛认可的按需路由协议，各个路由协议还有进一步提高的余地，下步发 展应该包括以卜几个方面： ( 1 ) 进一步提高性能，主要包括减小初始路由的时延、减小路由查找和维护”销、 提高网络扩展性、路由对主机的适应能力# 口q o s 路由等方面。 ( 2 ) 研究基于稳态的路由协议算法，增强路由的稳定性，具备较长寿命。k 寿命 的路由协议具有更强的抵抗节点移动性的能力，能减小通信中断和路由丌销，使 路由咖 义的性能得到大幅度提高。 ( 3 ) 多径路由协议是路由协议新的研究热点。 ( 4 ) 对多址通信的支持，a dh o c 在c s c w 等方面的应用需要通信的支持。 ( 5 ) 异构网络互联，例如实现a dh o c 移动网络和i n t e r n e t 及g s m c d m a 网络的互联 互通。 ( 6 ) 安全问题，由于移动通信的广播特点，使得非法主机可以很容易地窃取传输 信息，而且目前提出的路由协议还都没有考虑通信的安全问题。 硕卜毕业论文( 刘恒昌)中国科学技术大学汁算机系 2 3a dh o c 网络中的m a c 协议 2 3 1 a dh o c 网络m a c 协议简介 目前a dh o c 网络中较常使用的协议包括a l o h a 防议，t d m a 协议和c s m a 协 议。随机接入a l o h a 协议的基本原理如f ：它允许站点在任何时刻进行广播，如 果两个信号发生碰撞，那也没关系，各站点只需等待段随机时间后重试。c s m a 的基本原理如下：各站点在发送消息之前先监听媒体活动，如果当前没有其他消 息在传送，那么它将立即发送消息，否则它将随机等待一段时间。但是这种协议 只能消除部分冲突，如果两个( 或两个以上) 站点几乎同时想要发送消息的话，冲 突还是有可能发生。因而c s m a 的各种变形尝试通过减少冲突发生的次数来提高 效率。t d m a 协议的基本原理如下：采用同步通信技术，通过采用时分复用的方 法，不同的结点占用不同的时隙。这种方法能够在一定程度上保证信道接入的公 平性，但是需要确保时钟的同步、时隙的合理分配和调度。前者特别适合于传播 时延比较长的网络环境，如卫星通信；而在地面链路中，一般使用c s m a 和t d m a 接入协议来获得较高的信道利用率。它们基于这样一个假设：当一个站点在信道 上发送消息时，所有其它站点能够听到它的发送，并延迟自己的发送，即一跳共 享广播信道。但这个假设并不适用于a dh o c 网络，因为a dh o c 网络具有空间复 用特性，节点的通信范围受限，终端可以随意移动，并且节点之间的传播叫延不 可以忽略，所以a dh o c 网络中会产生隐终端和暴露终端等问题。这些问题会严 重影响信道接入协议的性能，必须设法解决，以便状得较高的信道利用率、较低 的时延和较好的公平性。 2 3 2a dh o c 网络m a c 协议中隐终端和暴露终端问题 2 3 2 1 隐终端和暴露终端的概念 由于a dh o c 网络节点的通信距离受限，一个节点发出的信号，只有位于它 传输范围之内的邻居节点可以收到，而此范围之外的其它节点将察觉不到，从而 会引起“隐终端”和“暴露终端”等问题。如图2 2 中所示，隐终端是指一个终 端位于接收者的通信范围之内，而在发送者的通信范围之外；暴露终端是指在发 送者的通信范围内而在接收者的通信范围之外的终端。 硕j j 毕业论文( 刘恒昌) 中国科学技术大学计算机系 图2 2 ( b ) ：a d h o c 网络中的暴露终端问题 2 3 2 2 隐终端和暴露终端的几种具体情况 ( 1 ) 隐发送终端：在图2 2 ( a ) 中，当a 向b 发送报文，同时c 也向b 发送报 文时，报文会在b 处发生冲突，此时称c 为隐发送终端。 ( 2 ) 隐接收终端：如图2 2 ( a ) ，当c 延迟发送时，如果d 向c 发送控制报文 请求发送时，因为c 要延迟发送，所以d 无法收到来自c 的应答，于是就超时重 发，从而浪费了带宽。这种情况被称为隐接收终端问题。 ( 3 ) 暴露发送终端：如图2 2 ( b ) ，b 向a 发送数据时，c 可以通过向d 发送 一个请求发送信号r t s 来通知d 它要发送数据，但来自d 的应答信号会与b 的数 据信号在c 处产生碰撞。c 听不到d 的回应，将重复发送r t s 。这种情况称为暴 露发送终端问题。 ( 4 ) 暴露接收终端：如图2 2 ( b ) ，当b 向a 发送数据时，如果d 想向c 发送 数据，它可以向c 发送一个请求发送信号，但此信号会与b 发送的数据信号在c 处发生冲突，c 听不到来自d 的清求报文，从而不会发送应答信号。d 收不到响 应，重发控制信号。这种情况称为暴露接收终端问题。 2 3 2 3解决隐终端和暴露终端的策略 对于隐发送终端问题，可以使用控制报文握手的方法加以解决。终端发送数 据之前首先要发送请求发送报文，只有听到相应的应答信号后才发