（电路与系统专业论文）无线ad+hoc网络中路由与定位问题的研究.pdf

中文俩要 无线a dh o e 网络是指一组无线移动节点组成的多跳的临时性的无基础设 施支持的无中心网络，在军用和民用方面部具有广泛的应用前景。无线a dh o c 网络的多跳和自组织特性使得路由问题成为a dh o c 网络里面的一个关键问 题，而网络节点的移动、节点资源受限等特点给路由算法的设计增加了难度。 另外，无线a dh o c 网络中的定位问题，无论对于提高网络路由协议的性能， 还是对于开发基于无线a dh o c 网络的新业务，都具有非常重要的意义。因此， 本文主要针对无线a dh o c 网络中的路由问题和定位问题进行了研究。 针对无线a dh o c 网络中节点电源的容量限制，提出了一种利用单向链路 的能源节省路由算法。该算法充分利用网络中存在的单向链路，通过让能源 较多的节点承担较多的传输任务的方式为数掘流选择最佳路由，有效地延长 了网络的生存时问。我们对无线a dh o c 网络路由算法设计中能源节省与路由 效率之间的关系进行了分析，分析结果表明，二者之间为t r a d e o f f 关系。 针对无线a dh o c 网络中节点移动导致路由协议性能下降的问题，提出了 一种基于链路持久性的路由机制，该机制可以估计出相邻节点之阳j 无线链路 的生存时间，并以此选取稳定路由。研究结果表明，该机制能够有效地提高 路由协议在节点移动性较强的情况下的性能。 提出了一种无线a dh o c 网络中基于地理分区的路由算法。该算法把无线 a dh o c 网络覆盖的地理区域划分成多个大小和形状一致的互不重叠的分区， 并通过区问路由简化了路由算法的复杂度。最后通过仿真验证了该算法的性 能。 提出了一种无线a dh o c 网络中的节点位置推测算法，该算法利用部分节 点的已知位置和节点间的距离，推测出其余节点的位置。通过计算机仿真， 证明本算法能够准确地推测出节点的位簧，而且算法简单实用，计算量小。 提出了一种无线传感器网中的目标定位算法，通过追踪目标的运动轨迹 来获取在无线传感器网监视区域中移动目标的位置。该算法有效地减少了目 标定位过程中传输的消息数量，节省了网络资源，增强了资源受限的无线传 感器网的实用性。 关键词：无线a dh o c 网络，路由算法，定位算法 a b s t r a c t aw i r e l e s sa dh o cn e t w o r ki sat e m p o r a ln e t w o r kf o r m e db yac o l l e c t i o no f w i r e l e s sm o b i l en o d e sw i t h o u tt h ea i do fa n ye x i s t i n gn e t w o r ki n f r a s t r u c t u r eo r c e n t r a l i z e da d m i n i s t r a t i o n w i r e l e s sa dh o cn e t w o r k ss h o wag o o da p p l i c a t i o n p r o s p e c t i nb o t hm i l i t a r ya n dc i v i lu s e t h er o u t i n gp r o b l e mi sc r i t i c a lt o t h e f u n c t i o n i n go f w i r e l e s sa dh o cn e t w o r k sb e c a u s et h en e t w o r ki sm u l t i h o pa n d s e l f - o r g a n i z e d n o d e s m o b i l i t ya n dl i m i t e dr e s o u r c e sm a k e i td i f f i c u l tt od e s i g n r o u t i n ga l g o r i t h m s f o rw i r e l e s sa dh o c n e t w o r k s p o s i t i o n i n gp r o b l e m i s i m p o r t a n tb e c a u s et h en o d e sp o s i t i o n i n f o r m a t i o nc a nb eu s e dt o i m p r o v et h e p e r f o r m a n c eo f t h er o u t i n gp r o t o c o l sa n dt op r o v i d en e ws e r v i c e si nw i r e l e s sa d h o cn e t w o r k s t h i sd i s s e r t a t i o n m a i n l y f o c u s e so nt h er e s e a r c ho fr o u t i n g a l g o r i t h m sa n dp o s i t i o n i n ga l g o r i t h m si nw i r e l e s sa dh o c n e t w o r k s a n e n e r g y c o n s e r v i n gr o u t i n ga l g o r i t h m w i t hu n i d i r e c t i o n a ll i n k s i s p r o p o s e do nt h eg r o u n dt h a te a c hn o d ei nw i r e l e s sa dh o cn e t w o r k h a sal i m i t e d b a t t e r yp o w e rs u p p l y i no r d e rt om a x i m i z et h en e t w o r kl i f e t i m e ，t h i sa l g o r i t h m t a k e sf u l l a d v a n t a g eo fu n i d i r e c t i o n a l l i n k sa n ds e l e c t st h eo p t i m a lr o u t e sb y a s s i g n i n gt r a f f i ci np r o p o r t i o nt on o d e s e n e r g y s i m u l a t i o nr e s u l t ss h o w t h a tt h i s a l g o r i t h mi s e f f i c i e n t w ea n a l y z et h er e l a t i o n s h i pb e t w e e ne n e r g yc o n s e r v a t i o n a n dr o u t i n ge f f i c i e n c y ，t h ea n a l y s i sr e s u l t ss h o wt h a tt h e r ei sat r a d e o f fb e t w e e n t h e m t h ep e r f o r m a n c eo ft h e r o u t i n gp r o t o c o l sd e g r a d e sr a p i d l yd u et o n o d e s m o b i l i t y t os o l v et h i s ，w ep r o p o s e al i n k p e r d u r a b i l i t yb a s e dr o u t i n gs c h e m ef o r w i r e l e s sa dh o cn e t w o r k s t h i ss c h e m ec a ne s t i m a t el i n kl i v i n gt i m ea n dh e n c e c h o o s e sas t a b l er o u t eb a s e do ni t t h es i m u l a t i o nr e s u l t ss h o wt h a tt h i ss c h e m e c a ne f f e c t i v e l yi m p r o v et h ep e r f o r m a n c eo ft h er o u t i n g p r o t o c o l si nt h ec o n d i t i o n t h a tn o d e s m o b i l i t yi sh i g h a g e o g r a p h i cz o n eb a s e dr o u t i n ga l g o r i t h mf o rw i r e l e s sa dh o cn e t w o r k si s p r o p o s e d t h ef i e l dc o v e r e dw i t hw i r e l e s sa dh o cn e t w o r k si sd i v i d e di n t om a n y n o n o v e r l a p p i n gz o n e st h a th a v et h es a m es i z ea n ds h a p e r o u t i n gb e t w e e nz o n e s i i i su s e dt or e d u c et h ec o m p l e x i t yo ft h e a l g o r i t h m t h ep e r f o r m a n c eo ft h i s a l g o r i t h mi se v a l u a t e db y s i m u l a t i o n a p o s i t i o n i n ga l g o r i t h mi sp r o p o s e dt os p e c u l a t ea b o u tt h ep o s i t i o n so f a l l n o d e sb yu s i n gt h ef o r e g o n ep o s i t i o n so f p a r t i a ln o d e sa n dt h ed i s t a n c e sb e t w e e n n o d e si nw i r e l e s sa dh o cn e t w o r k s t h ec o m p u t a t i o n a lr e s u l t ss h o wt h a tt h i s a l g o r i t h mc a na c c u r a t e l ys p e c u l a t ea b o u tt h ep o s i t i o n so f a l ln o d e s i na d d i t i o nt o t h a t ，t h ec o m p l e x i t yo ft h ea l g o r i t h mi sl o w at r a c k i n g - b a s e d t a r g e tl o c a t i n ga l g o r i t h m i s p r o p o s e d t h i sa l g o r i t h m l o c a t e sas p e c i f i e dt a r g e tm o v i n gi na g e o g r a p h i c a lr e g i o nu n d e r s u r v e i l l a n c eo fa w i r e l e s ss e n s o rn e t w o r k b yt r a c k i n g t h et r a i lo ft h e t a r g e t t h i sa l g o r i t h m e f f e c t i v e l y r e d u c e st h e m e s s a g et r a n s m i s s i o n s ，c o n s e r v e sr e s o u r c e s ，a n d c o n s e q u e n t l y e n h a n c e st h e p r a c t i c a b i l i t y o fr e s o u r c e l i m i t e dw i r e l e s ss e n s o r n e t w o r k s k e yw o r d s ：w i r e l e s sa dh o en e t w o r k ，r o u t i n ga l g o r i t h m s ，p o s i t i o n i n ga l g o r i t h m s 第一章绪论 第一章绪论 1 1 无线a dh o c 网络技术 近些年来，无线通信网络无论在技术上，还是在商业上都获得了飞速的 发展，并且已经在世界范围内被广泛地应用。无线通信网络由于能快速、灵 活、方便地支持用户的移动性而使它成为个人通信和 n t e m e t 发展的方向， 而且也只有通过无线通信网络才能实现“任何人在任何时间、任何地点与任 何人进行任何种类的信息交换”的理想的通信目标。 我们经常提及的无线通信网络一般都是有中心的，要基于预设的基础设 施彳能运行。例如，g s m ( g l o b a ls y s t e m m o b i l e c o m m u n i c a t i o n ) i “、 c d m a ( c o d ed i v i s i o nm u l t i p l ea c c e s s ) 口j 等蜂窝移动通信系统要有基站的支 持；无线局域网一般也工作在有a p 接入点和有线骨干网的模式下。但对于 有些特殊场合来说，有中心的移动网络并不能胜任。比如，战场上部队快速 展丌和推进，地震或水灾后的营救等。这些场合的通信不能依赖于任何预设 的基础设施，而需要一种能够临时快速自动组网的移动网络。无线a dh o c 网 络可以满足这样的需求。 1 1 1a dh o c 网络的概念及特点 a dh o c 一词来源于拉丁语，是“特别或专门”的意思。这里提出的“a dh o c 网络”所指的就是一种特定的无线网络结构，强调的是多跳、自组织、无中 心的概念，比较正规的表述为：无线a dh o c 网络是指一组无线移动节点组成 的多跳的临时性的无基础设施支持的无中心网络3 】【4 】。在a dh o c 网络中，节 点具有报文转发能力，节点问的通信可能要经过多个中间节点的转发。即经 过多跳( m u l t i h o p ) ，这是a dh o c 网络与其他移动网络的最根本区别。节点 通过分层的网络协议和分稚式算法相互协调，实现了网络的自动组织和运 行。因此它也被称为多跳无线网( m u l t i h o pw i r e l e s sn e t w o r k ) 、自组织网 络( s e l f - o r g a n i z e dn e t w o r k ) 或无基础设施的网络( i n f r a s t r u c t u r e l e s s n e t w o r k ) 。 与普通的移动网络和固定网络相比，a dh o e 网络具有以下特点： 第一章绪论 1 无中心：a dh o c 网络没有严格的控制中，t l , 。所有节点的地位平等，即 是一个对等式网络。节点可以随时加入和离开网络。任何节点的故障 不会影口i 自整个网络的运行，具有很强的抗毁性。 2 自组织：a dh o c 网络相对常规通信网络而言，最大的区别就是可以在 任何时刻、任何地点不需要现有信息基础网络设施( 包括有线和无线 网络) 的支持，快速构建起一个移动通信网络。这也是个人通信的一 种体现形式。 3 多跳路由：当节点要与其覆盖范围之外的节点进行通信时，需要中间 节点的多跳转发。与固定网络的多跳不同，a dh o c 网络中的多跳路由 是由普通的网络节点完成的，而不是由专用的路由设备( 如路出器 完成的。网络中的每一个网络节点扮演着多个角色，它们可以是服务 器、终端，也可以是路由器。 4 动态变化的网络拓扑结构：网络的拓扑结构是指从网络层角度来看， 物理网络的逻辑视图。a dh o c 网络中，移动用户终端可以以任意速度 和任意方式在网中移动，加上无线发送装置发送功率的变化、无线信 道问的互相干扰因素、地形等综合因素的影响，移动终端问通过无线 信道形成的网络拓扑结构随时可能发生变化，而且变化的方式和速度 都是不可预测的，具体的体现就是拓扑结构中代表移动终端顶点的增 加或消失。代表无线信道的有向边的增加和消失，网络拓扑结构的分 割和合并等等。而对于常规网络而言。网络拓扑结构则表现较为稳定。 5 移动终端的局限性：a dh o e 网络中。用户终端通常以p d a 、掌上型电 脑或手持式电脑为主要形式。相对于台式机而言，在带来移动性、灵 巧、轻便等好处的同时，其固有的特性，例如依靠电池这样的可耗尽 能源提供电源( 车载终端的电源相对丽言较有保障) 、内存较小、c p u 性能较低等，给a dh o e 网络环境下的网络协议和应用程序设计丌发带 来一定的难度。 6 存在单向的无线信道：a dh o e 网络采用无线信道通信，由于地形环境 或发射功率等因素影l 响可能产生单向无线信道。在常规网络中，节点 间通常基于双向的有线或无线信道进行通信。这些单向信道为常规路 一2 一 第一章绪论 由协议带来三个严重的影l 晌：认知的单向性、路由单向性和汇点不可 达 ”。 7 有限的无线传输带宽：由于a dh o c 网络采用无线传输技术作为底层通 信手段，而由于无线信道本身的物理特性，它所能提供的网络带宽相 对有线信道要低得多。除此之外，考虑到竞争共享无线信道产生的碰 撞、信号衰减、噪音干扰、信道间干扰等多种因素，移动终端可得到 的实际带宽远远小于理论上的最大带宽值。 8 安全性差：a dh o c 网络是一种特殊的无线网络，由于采用无线信道、 有限电源、分布式控制等技术和方式，所以更加容易受到被动窃听、 主动入侵、拒绝服务、剥夺“睡眠”( 终端无法进入睡眠模式) 、伪 造等各种网络攻击。 9 网络的可扩展性不强：在目前i n t e r n e t 环境下，由于采用了子网 ( s u b n e t ) 等技术，从而使得目前的i n t e r n e t 具有较强的网络可扩展 性。但是动态变化的拓扑结构使得具有不同子网地址的移动终端可能 同时处于一个a dh o c 网络中，因而子网技术所带来的可扩展性无法应 用在a dh o c 网络环境中。 1 1 2a dh o c 网络的发展历程 a dh o c 技术起源于2 0 世纪7 0 年代，它是在美国国防部高级研究计划局 ( d a r p a ) 资助研究的“战地无线分组数据网( p r n e t ) 6 1 ”项目中产生的 一种新型网络技术。d a r p a 当时所提出的是一种军用无线分组数据通信网 络。后来，d a r p a 又于1 9 8 3 年和1 9 9 4 年分别资助进行了抗毁自适应网络 ( s u r v i v a b l e a d a p t i v en e t w o r k 。s u r a n ) f 7 】和全球移动信息系统( g l o b a l i n f o r m a t i o ns y s t e m s ，g l o m o ) 【b 1 两个项目的研究，以便能够建立某些特殊环 境或紧急情况下的无线通信网络。a dh o c 技术就是吸取了p r n e t 、s u r a n 以及g l o m o 等项目的组网思想，而产生的一种新型的网络结构技术。美国军 方一直在研究军方的a dh o c 网络技术，后来由陆续资助了s i n c g a r ss i pi p 网络、联合战术无线系统( j t r s ) 1 0 1 等项目。 随着移动通信和移动终端技术的高速发展，a dh o c 技术不仅在军事领域 巾得到了充分的发展，而且也在民用移动通信中得到了应用。典型的系统有 第一章绪论 加拿大最早研究的业余分组无线网( t a p r ) ，图书馆自动化无线电网络 等。因特删任务工作组( i e t f ) 于1 9 9 6 年成立了m a n e t ( m o b i l ea dh o c n e t w o r k s ) 工作组，专门研究a dh o c 网络环境下基于i p 协议的路由协议规 范和接口设计f ”。这使得a dh o c 网络的设计思路也出传统的单一技术体系过 渡到基于i p 的多技术体系，从而导致该网络更具有开放型、适应性、灵活性， 提高了丌发速度。随着配备有无线收发设备的高性能移动终端的降价和将要 随之而来的普及性，加上人们对于个人通信需求的同益增长，使得无线a dh o c 网络的研究重新丌始得到国内外研究人员的重视。特别是从1 9 9 8 年以来， 无论是国内还是国外，各科研团体对无线a dh o c 网络的研究不断升温，尤其 是在网络层的路由协议方面，其研究工作己经取得了很大的进展。 1 1 3a dh o c 网络的应用领域 出于a dh o c 网络的特殊性，它的应用领域与普通的通信网络有着显著的 区别。它适合被用于无法或不便预先铺设网络设施的场合、需快速自动组网 的场合等。针对a dh o c 网络的研究是因军事应用而发起的，因此，军事应用 仍是a dh o c 网络的主要应用领域，但是民用方面，a dh o c 网络也有非常广阔 的应用前景。它的应用场合主要有： 1 军事应用：军事应用是a dh o e 网络技术的主要应用领域。因其特有的 无需架设网络设施、可快速展开、抗毁性强等特点，它是数字战场通 信【”4 1 的酋选技术。a dh o c 网络技术已经成为美军战术互联网的核 心技术，美军的近期数字电台和无线互联网控制器等主要通信装备都 使用了a dh o c 网络技术。 2 传感器网络( s e n s o rn e t w o r k ) 1 15 1 1 1 6 1 ：传感器网络是a dh o c 网络技术 的另一大应用领域。对于很多应用场合来说传感器网络只能使用无线 通信技术。而考虑到体积和节能等因素，传感器的发射功率不可能很 大。使用a dh o e 网络实现多跳的远距离通信是非常实用的解决方法。 分散在各处的传感器组成a dh o c 网络，可以实现传感器之问和与数据 中心之间的通信。这在环境监测等领域具有非常广阔的应用前景。 3 紧急事故和l 临时场合：在发生了地震、水灾、强热带风暴或遭受其他 灾难打击后，固定的通信网络设施( 如有线通信网络、蜂窝移动通信 笙二童望笙 刚络的基站等网络设施、卫星通信地球站以及微波接力站等) 可能因 被摧毁而无法f 常工作，这时就需要不依赖任何固定基础设施又能快 速伽设的无线a dh o c 网络技术。类似地，处于边远或偏僻野外地区时， 同样无法依赖固定或预设的网络设施进行通信。a dh o c 网络技术的独 立组网能力和自组织特点，是这些场合通信的最佳选择。 4 个人通信：个人局域网( p e r s o n a la r e an e t w o r k ，p a n ) l i “是a dh o c 网络技术的另一应用领域。不仅可用于实现p d a 、手机、手提龟脑等 个人电子通信设备之间的通信，还可用于个人局域网之间的多跳通 信。蓝牙技术中的超网( s c a t t e r n e t ) 就是一个典型的例子。 5 与移动通信系统的结合：在实际应用中，a dh o e 网络除了可以单独组 网实现局部的通信外，它带可以作为术端子网通过接入点接入其他的 固定或移动通信网络，与a dh o e 网络以外的主机进行通信。a dh o c 网络可以与蜂窝移动通信系统相结合，利用移动台的多跳转发能力扩 大蜂窝移动通信系统的覆盖范围、均衡相邻小区的业务、提高小区边 缘的数据速率等。在a dh o c 网络中，无线移动a dh o c 网络( w m a n e t ) 被认为是下一代移动通信系统解决方案中最有希望被采用的末端网 络。 1 2 论文的目的与意义 如前所述，无线a dh o c 有着广泛而有价值的应用领域，比如在军事方面 的应用能够提高军队的国防战备水平；在抢险救灾领域的应用有助于挽救人 民的生命财产；而在个人通信和接入网等方面的应用则具有良好的商业前 景。鼠此，对a dh o e 网络技术的研究既有重要的社会意义又蕴含着潜在的经 济价值。 根据前面的介绍，无线a dh o c 网络具有丰富而鲜明的特点，这些特点也 引入了很多复杂的问题，比如路由问题、安全问题以及q o s 问题等。尤其是 路山选择问题是a dh o e 网络构建时所要着重考虑的一个问题，已经得到学术 界、工业界和政府机构的广泛重视。路由协议作为影响网络性能的一个重要 因素，是确保a dh o e 网络正常运行的关键。对该领域进行深入而广泛的研究 第一章绪论 将为a dh o c 网络的应用提供重要的科学依据。 a dh o c 网络的许多特点加大了路由协议的设计难度。比如动态变化的网 络拓扑结构要求路由协议具有快速适应拓扑变化的能力；电池供电的移动终 端要求路由协议尽量节省能源：单向信道的存在要求路出协议支持单向键 路；等等。同时，a dh o c 网络的这些特点也给路由协议和路由算法的研究者 提供了更为广阔的研究空问。 无线a dh o c 网络无中心、自组织的特性增加了网络的不确定性，从而提 高了路由协议设计的复杂度。如果在设计路由协议时能够获得网络节点的位 置，将大大降低a dh o c 网络的不确定性，进而可以简化路由协议的设计和提 高路由协议的性能：同时，还可以给a dh o c 网络开发基于节点位置的新业务， 比如目标追踪和定位等。因此，无线a dh o c 网络中的定位算法也是一个非常 有价值的研究方向。 本文以提高a dh o c 网络的性能为目的，着重于a dh o c 网络中的路由和定 位问题的研究，试图设计出性箍更好的路出和定位算法。 1 3 相关工作与本文的主要工作 传统的路由协议分为距离矢量和链路状态两种方式。距离矢量协议如 r i p 【l ”，基于最短路由的分布式b e l l m a n f o r d ( d b f ) 算法，各节点保持到 网络中所有结点的距离估计，并且周期性的向它的邻节点广播它到网络中各 目的节点的晟小距离估计。这秘方法所需要的存储量小。节点不需要知道全 网的拓扑结构，拓扑更新中交换的数据量小，缺点是d b f 算法收敛速度慢， 需要大量的消息响应拓扑的变化，易形成闭环【1 8 】。美国的d a r p a 的p r n e t t 6 】 使用的就是一种距离矢量算法。链路状态协议( 如o s p f i 博】) 要求每个节点 知道全网的拓扑信息并保留到网络中所有节点的最短路由树，利用广播更新 来保持每个节点对网络状态的连续监测，需要大量的存储和通信开销，但是 算法收敛速度快，不容易形成闭环，适合于拓扑变化较慢的网络结构。这些 传统的路由算法由于不适应高速的网络拓扑变化而不能在无线a dh o c 网络中 有效工作【l ”。无线a dh o c 网络中的路由协议通常假定拓扑的变化速率既不是 太高以至于只能使洪泛法路由策略成为了唯一的选择，也不是太低以至于使 一6 一 第一章绪论 用传统路由协议就可以有效工作。从拓扑结构方面考虑无线a dh o c 网络中 的路由协议按照路由建立和保持方式来分更为合适。 主动路出协议通常改进现有的d b f 路由算法以供动态拓扑中使用。 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 ) t 2 0 l 算法改进了d b f 算法，利用 序列号标定路由信息的先后顺序，从而防止了闭环现象：它还缓解了不稳定 路由的传播时间，从而减少了路由表的反复波动以及相同序列号路由的重复 传播数目。w a p ( w i r e l e s sr o u t i n gp r o t o c 0 1 ) 圳运用了至目的节点各链路的路 出搜索算法来区分不同的路由并防止了临时闭环的出现。文献 2 2 的方法可 以发现并保持群结构，边界节点连接各群并使用传统的距离矢量路由协议。 c g s r ( c l u s t e r h e a dg a t e w a ys w i t c hr o u t i n g ) 协议1 2 3 1 基于分群结构，采用d s d v 协议作为基本的路由策略只不过源节点到目的结点的业务是经过群首一阿关 的模式进行中转。这些方法中，每个节点或边界节点需要保持到网络中目的 节点的路由。其他同类的路由协议还有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 ) 协 议 2 4 1 、f s r ( f i s h e y e s t a t e r o u t i n g ) 协议【2 5 2 6 1 和z r p ( z o n er o u t i n g p r o t o c 0 1 ) t 2 7 ( 2 9 j r 2 9 “3 0 i 。 源节点发起的按需路由协议根据按需进行路由发现的原理，仅当节点有 数据要发给某一目的节点时才寻找到陔目的节点的路由。d s r ( d y n a m i c s o u r s er o u t i n g ) 协议1 3 l ”2 1 1 3 3 】1 3 4 1 是用广播方式来传播路由查找控制分组，每 一个中转路由查找分组的节点将其地址加入到该分组的列表中。当路由查找 分组到达目的结点时，分组中就包括了完整的路由信息：节点将这种方式发 现的路由或者当邻节点问通信时听到的路由信息记录在存储器中，并根掘数 据分组中的源指定路出进行中转。l m r ( l i g h t w e i g h tm o b i l er o u t i n g ) 协议【3 5 j 在需要路由的时候采用洪泛式广播路由查询，如果收到这一路由查询的节点 存在到达所要求的目的节点的路由，该节点就回应该满足要求的路由否则， 它仅仅中转这个路由的查询；这个方法使用链路状态来创建路由并防止闭环 情况，当拓扑变化时进行路由擦除。a b r ( a s s o c i a t i v i t y 。b a s e dr o u t i n g ) 协 议f 3 6 脚1 同样使用广播查询来寻找满意的路由，不过最佳的路由是由目的节点 根掘中转节点的稳定性和最短路径准则来选择的。所谓中转节点的稳定性， 就是节点很可能静止多长时间不移动，这种方法同样在拓扑变化引起路由失 第一章绪论 效时使用路由擦除的做法。除此之外，此类路出协议还有a o d v ( a dh o c o n d e m a n dd i s t a n c ev e c t o rr o u t i n g1 协议1 3 8 1 、s s a ( s i g n a ls t a b i l i t y b a s e d a d a p t i v er o u t i n g ) 忉、议【”l 和t o r a ( t e m p o r a l l y o r d e r e d r o u t i n g a i g o r i t h m ) 1 4 0 州1 。 文献 4 2 证明，利用网络节点的位置信息，可以大幅度提高路由协议的性 能，其它研究人员也提出了各种不同的基于位置的路由协议【4 3 】【4 4 1 4 5 1 4 6 i t 4 7 】【4 8 。 在这些基于位置的路由协议中，每个节点维护着一个位置表，该表包含了网 络中所有其它节点的位置信息和接收到位置信息的时间。数据发送节点使用 位罱表罩的节点位罱信息来提高发送数据分组的效率。但是，这些文献只是 假定网络中的节点知道自己的位置，实际并没有讨论如何计算出节点的位 置。因此，设计合适的节点定位算法，是这一类路由协议存在的基础。 本文主要针对无线a dh o c 网络中的路出和定位问题进行了研究，论文的 主要工作为： 1 针对无线a dh o c 网络中节点电源的容量限制，提出了一种利用单向链 路的能源节省路由算法。该算法充分利用网络中存在的单向链路，通过让能 源较多的节点承担较多的传输任务的方式为数据流选择最佳路由，以延长网 络的生存时间。仿真结果证明了该算法的有效性，以及单向链路对于能源节 省具有较高的价值。 2 分析了无线a dh o c 网络路由算法设计中能源节省与路由效率之间的关 系。以一个选定的无线信号传播模型为基础，分别定义了能源节省与路由效 率的数学测量函数，并分析了两个数学测量函数之间的关系。分析结果表明， 二者之间相互成反比依赖关系，或称之为权衡关系( t r a d e o f f 】。 3 针对无线a dh o e 网络中节点移动导致路由协议性能下降的问题，提出 了一种基于链路持久性的路出机制，该机制根搌相对运动模型估计出任意两 个相邻节点之间无线链路的生存时问，并以此生存时阳j 作为选路标准。通过 选择生存时问较长的路径，减少了路径失效的频率，提高了路由协议的分组 递交率。把该机制应用于d s d v 和d s r 协议中，并通过实验仿真验证了该 机制的有效性。 4 提出了一种无线a dh o c 网络中基于地理分区的路由算法。该算法把无 一8 一 第一章绪论 线a dh o c 网络覆盖的地理区域划分成多个大小和形状一致的互不重叠的分 区，并通过区间路由简化了路由算法的复杂度。最后通过仿真验证了该算法 的性能。 5 为了在无线a dh o c 网络上开展基于位置的服务，以及提高无线a dh o c 网络的路由协议性能，有必要使网络节点知道自己的位置。提出了一种无线 a dh o c 网络中的节点位置推测算法，该算法利用部分节点的已知位置和节点 f n j 的距离，推测出其余节点的位置。通过计算机仿真，证明本算法能够准确 地推测出节点的位置，而且算法简单实用，计算量小。 6 提出了一种无线传感器网中的目标定位算法，用以获取在无线传感器 网监视下的地理区域中移动目标的位置。该算法首先找到一个曾监测到目标 的节点，然后利用相邻节点间的本地消息跟踪目标的运动轨迹。我们实现了 该算法并与优化的洪泛定位算法进行了比较，仿真结果表明，该算法有效地 减少了目标定位过程中传输的消息数量，节省了网络带宽，降低了节点能源 的消耗，从而增强了节点资源受限的无线传感器网的实用性。 在内容的安排上，整个论文总共分为七章。第一章为绪论：第二章针对 无线a dh o c 网络中节点电源的容量限制，提出并仿真了一种利用单向链路的 能源节省路由算法。然后分析了无线a dh o c 网络路由算法设计中能源节省与 路由效率之间的关系g 第三章针对无线a dh o c 网络中节点移动导致路由协议 性能下降的问题，提出了一种基于链路持久性的路由机制，通过把该机制应 用于经典的路由协议，提高了路由协议的性能：第四章提出了一种无线a dh o c 网络中基于地理分区的路由算法。该算法把无线a dh o e 网络覆盖的地理区域 划分成多个大小和形状一致的互不重叠的分区，并通过区间路由简化了路由 算法的复杂度；第五章设计了一种无线a dh o c 网络中的节点位置推测算法， 该算法能够利用部分节点的已知位罱和节点间的距离，推测出其余节点的位 置：第六章提出了一种无线传感器网中的目标定位算法，用以获取在无线传 感器网监视下的地理区域中移动目标的位罱；第七章对全文进行了总结。 一9 一 第一章绪论 j-j-，-_一 参考文献 1 m o er a h n e m a o v e r v i e w o ft h eg s ms y s t e ma n d p r o t o c o l a r c h i t e c t u r e i e e e c o m m t u d c a t i o n sm a g a z i n e ，a p r i l1 9 9 3 ( 2 【3 】 【4 】 【5 ( 6 8 】 【9 f 1 0 】 【1 1 【1 2 】 ( 1 3 】 1 4 【1 5 】 【1 6 】 f 1 7 】 k y o u n g 1 1 k i m ，h a n d b o o ko fc d m as y s t e md e s i g n ，e n g i n e e r i n ga n do p t i m i z a t i o n ， p r e n t i c eh a l lp t r ，1 9 9 9 h t t p ：l w w wi e t f o r g h t m lc h a r t e r s m a n e t - c h a r t e r h t m l ，2 0 0 3 - 0 5 - 0 6 c o r s o ns ，m a c k e rj m o b i l ea dh o cn e t w o r k i n g ：r o u t i n gp r o t o c o lp e r f o r m a n c ei s s u e s a n de v a l u a t i o nc o n s i d e r a t i o n s e b o l h t t p ：w w w i e t f o r g r f c r f e 2 5 0 1t x t ，j a n1 9 9 9 p r a k a s hru n i d i r e c t i o n a ll i n k sp r o v ec o s t l yi nw i r e l e s sa d - h o cn e t w o r k s a d i m a c s w o r k s h o po nm o b i l en e t w o r k sa n dc o m p u t e r s c ，s e a t t l e ，a u g1 9 9 9 ，l 5 - 2 2 jj u b i na n dj d t o n l o w , “t h ed a r p a p a c k e tr a d i on e t w o r kp r o t o c o l s ，”p r o ci e e e ，v o l 7 5 ，d o 】，j a n 1 9 7 8 ，p p 2 1 3 2 gl a u e r , a d v a n c e dp r o t o c o l sf o rt h es u r a n p a c k e tr a d i on e t w o r k p r o e o ft h es h a p e p a c k e tr a d i os y m p o s i u m ( 1 9 8 9 ) b m l e i n e r , r j r u t ha n dar s a s t r y , “g o a l sa n dc h a l l e n g e so ft h ed a r p ag l o m o p r o g r a m ，”i e e e p e r s o n a lc o m n m u d e c ，1 9 9 6 ，p p 3 4 4 3 i t ti n d u s t r i e s a e r o s p a c e c o m m u n i c a t i o n sd i v i s i o n ( i i na c d ) ，“s i n c g a r ss i pi p n e t w o r ks y s t e ms o f t w a r ei m p l e m e n t a t i o no f m i l s t d 1 8 8 2 2 0 a ”f e b 1 9 9 7 j o i n tt a c t i c a lr a d i os y s t e m j t r s h t t p ：j t r sa r m y m i l l f i n k e c r ，“t p r sq u a r t e r l yr e p o r t 。”t e x a sp a c k e tr a d i os o c i e t y , f e b 19 9 2 j o n e s 。g gk n e z e k ，m h a t a ，“p a c k e tr a d i o p r o s r ，e c t s f o re d u c a t i o n a ld a t a c o n u n u n i c a t i o n s ，i np r o c e e d i n g so f t h en i n t hi n t e r n a t i o n a lc o n f e r e n c eo nt e c h n o l o g yi n e d u c a t i o n ，p a r i s ，f r a n c e ，1 9 9 2 r i c a r d os a n c h e z