（计算机应用技术专业论文）传感器网络中基于自适应的路由算法研究.pdf

摘要 与传统无线网络相比，传感器网络节点分布稠密、易失效、节点资源有限、 难以获得全局信息，因此传统的路由算法并不适合传感器网络，必须针对传感器 网络的特性研究新的路由机制与算法。为此本文在无线传感器网络中研究了基于 自适应的路由算法，主要工作如下： 针对传感器节点能量及传输范围有限等特点，提出了一种基于延迟的自适应 洪泛路由算法，首先通过源节点在网内用较小的路由请求报文和路由回复报文来 建立路由，路由建立的过程中自适应地确定等待时间以使更优的路由请求报文得 到转发，然后源节点再沿着建立好的路径转发较大的数据报文。仿真实验表明新 算法较f l o o d i n g 节能，能较好的克服f l o o d i n g 算法中报文冗余度高、能耗大等不 足。 为了尽可能地延长节点的生存期限，提高网络的稳定性与路由性能，提出了 一种基于层次分析法的自适应分簇路由算法。该算法借鉴了建立梯度引导路由和 分簇思想，引入层次分析法建模以确定权值，利用若干权重因子的组合( 权重因子 的组合综合地反映了网络的当前状态) 来选取簇头并形成簇。分析和仿真实验表 明，该算法比传统的基于周期性分簇的l e a c h 算法更节能、并能更有效地均衡节 点能耗，延长网络生命周期。 在上述研究的基础上，提出了一种对位置敏感的自适应分簇路由算法。新算 法仍引入加权的方法自适应地决定何时分簇、以选取簇头；分簇完成后，簇固定 工作一段时间，簇头在簇内轮换，达到相应的条件后再重新分簇；由每轮的簇头 和s i n k 构建当前轮虚拟骨干网络；然后再针对该虚拟骨干网络建立路由。理论分 析和模拟结果表明新算法能有效增大网络吞吐量。 关键词：传感器网络；自适应路由算法；能耗；分簇 i l l a b s t r a c t s e n s o r n e t w o r k ， w h i c hc o n s i s t so ft h e c o n v e r g e n c e o f s e n s o r , m i c r o e l e c t r o m e c h a n i s ms y s t e ma n dn e t w o r kt e c h n o l o g i e s ，h a saw i d ea p p l i c a t i o n p r o s p e c ti nn a t i o n a ld e f e n s ea n de n v i r o n m e n t a lm o n i t o r i n ga n ds oo n y e tt h es h e e r n u m b e r so ft h e s es e n s o r sa n dt h ee x p e c t e dd y n a m i c si nt h e s ee n v i r o n m e n t sp r e s e n t u n i q u ec h a l l e n g e si nt h ed e s i g no fu n a t t e n d e da u t o n o m o u ss e n s o rn e t w o r k s t h e r e f o r e ， s e l f - a d p t i v er o u t i n ga l g o r i t h mi ss t u d i e di nt h i sp a p e r c o n s i d e r i n gt h el i m i t e de n e r g ya n dt r a n s m i s s i o nr a n g eo fs e n s o rn o d e si ns e n s o r n e t w o r k s ，a l li n n o v a t i v er o u t i n ga l g o r i t h mn a m e ds e l f - a d a p t i v ef l o o d i n gb a s e do n d e l a yi sp r o p o s e d i nt h i sa l g o r i t h m ，s o u r c e sd e l i v e rr o u t er e q u e s tp a c k e t s ( r r e q ) a n ds i n ka n s w e r sr o u t er e p l yp a c k e t s ( r r e p ) t ob u i l dr o u t e s i no r d e rn o tt om i s s o p t i m u mr o u t e sw i t ht h eb e s tm e t r i c s ，t h ea l g o r i t h mi st ow a i tas p e c i f i ca m o u n to f t i m et oe n s u r et h a ta l m o s tt h er r e qn e a rt h eb e s tm e t r i c si sr e c e i v e d a n dt h ew a i t i n g t i m ei sd e c i d e ds e l f - a d a p t i v e l y t h e nn o d e sw i l lt r a n m i tt h er r e qw i t ht h eb e s t m e t r i c s + a f t e rt h ep a c k e ta r r i v e sa ts i n k ，s i n ks e n d sr r e pt ol e to t h e rn o d e sk n o wt h e r o u t e s f i n a l l yd a t ap a c k e t sa r et r a n s m i t t e dt h r o u g ht h e m t h e o r e t i ca n a l y s i sa n d s i m u l a t i o nr e s u l t sp r o v ei t sm o r ee f f i c i e n ta n dm u c hb e t t e rt h a nf l o o d i n ga n di tb e t t e r s l o v e st h ep r o b l e mo fr e d u n d a n c yo f p a c k e t s ， f o rt h es a k eo fp r o l o n g i n gt h el i f e s p a no fn o d e sa n di m p r o v i n gt h ep e r f o r m a n c e o fs t a b l ea n dr o u t i n g ，as e l f - a d a p t i v er o u t i n ga l g o r i t h mb a s e do na n a l y t i ch i e r a r c h y p r o c e s s ( a h p ) i sp r o p o s e d 。t h en e wa l g o r i t h mi n d u c e sa h pt oc l u s t e rs e l f - a d a p t i v e l y , a n dt h e ni tm a k e sv i r t u a lb a c k b o n en e t w o r kb yc l u s t e r sa n ds i n k s a f t e rt h 鑫| i tc r e a t e s r o u t e si nt h ev i r t u a lb a c k b o n en e t w o r k a l s ot h e o r e t i ca n a l y s i sa n ds i m u l a t i o nr e s u l t s p r o v ei ti sm o r ee f f e c t i v et h a nl e a c h o nt h eb a s i so ft h ea b o v er e s e a r c h ，as e l f - a d a p t i v ec l u s t e r i n gr o u t i n ga l g o r i t h m s e n s i t i v et o p o s i t i o n i s p r o p o s e d i n t h i s a l g o r i t h m i ts e l e c t sc l u s t e r - h e a d sb y c o n s i d e r i n gt h ew o r k i n go r d e rs y n t h e t i c a l l yi n s t e a do fp e r i o d i c a l l y a n dc l u s t e ri s s t a b l e f o raw h i l eu n t i li to b t a i n sc e r t a i nc o n d i t i o n sw h o s ec l u s t e r - h e a dc h a n g e s i n c l u s t e r f u r t h e r m o r ed a t ai sf o r w a r d e dv i ar o u t e sb u i l da m o n gv i r t u a lb a c k b o n e n e t w o r k si n s t e a do fb e i n gs e n td i r e c t l yt os i n k sw h i c hm a yb ef a r a w a y t h e r e f o r ei t s u p p o r t sl o w e r - c l a s ss e n s o r sa n di ti sd i s t r i b u t e d ，l o wc o m p l e x i t ya n dc a nb a l a n c et h e e n e r g ye x p e n d i t u r ew h i c hw i l lr e n d e rt h et o t a le n e r g ye x p e n d i t u r el o w e ra n di n c r e a s e t h et h r o u g h p u t a l s ot h e o r e t i ca n a l y s i sa n ds i m u l a t i o nr e s u l t sp r o v ei ti se f f e c t i v ea n d s c a l a b l e 堡主堂垡量苎 k e y w o r d s ：s e n s o rn e t w o r k s ；s e l f - a d a p t i v er o u t i n ga l g o r i t h m ；e n e r g ye x p e n d i t u r e ； c l u s t e r i n g v 抟感器网络中熬予自适应静路由簿法垂野究 插图索引 图2 1d d 的实现机制。7 图3 。1 一阶无线电模型一1 4 一 嚣3 2 等待黪麓& ( m i l l is e c o n d s ) 一1 7 一 图3 3s f d 与f l o o d i n g 中网络稔溅到的事件总数- 1 8 图3 4s f d 与f l o o d i n g 传送一个数据报文的平均能耗( m j ) - 1 8 图4 1s c r aa h p 与l e a c h 中网络检测到的事件总数2 8 图4 2s c r aa h p 与l e a c h 传送一个数据报文的平均能耗( m j ) - 2 8 蛋4 3s c r aa h p 与l e a c 差繁一个夏亡节煮枣残豹轮次与总轮次瓣嚣分跑 ( ，) - 2 9 图5 ts c r ap o s 与l e a c h 中网络检测到的事件总数3 9 一 图5 2s c r ap o s 与l e a c h 传送一个数据报文的平均能耗( m j ) 一4 0 一 图5 。3s c r ap o s 与l e a c h 缡一个死亡节点出现的轮次与总轮次的酉分比 。) 。一。，。4 0 v i 附表索弓l 表2 1 常见的平面路由算法8 一 表2 2 常见的艨次路由算法，l o 表3 1s f d 缀文袭1 2 表3 2 对s f d 掇文及表格中各数攥域的说明1 2 表3 3s f d 中备节点需要维护的袋格，1 3 表3 4f l o o d i n g 和s f d 的实验参数1 7 表4 1s c r aa h p 报文表，2 2 表4 。2 对s c r aa h p 摄文及表掺孛各数据蠛戆说明。2 2 表4 3s c r aa h p 中各节点需要缭护的表格2 2 表4 4s c r aa h p 的实验参数2 7 表4 5l e a c h 的实验参数2 7 表5 1s c r ap o s 报文表。3 2 表5 。2s c r ap o s 孛各节点霉要缎护戆表辏3 2 表5 3 对s c r ap o s 摄文及表楱审各数据域懿说褥。3 3 - 表5 4s c r ap o s 的实验参数3 8 表5 5l e a c h 的实验参数3 8 v i l 湖南大学 学位论文原创性声明 本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所取 得的研究成果。除了文中特别加以标注引用的内容外，本论文不包含任何其 他个人或集体已经发表或撰写的成果作品。对本文的研究做出重要贡献的个 人和集体，均已在文中以明确方式标明。本人完全意识到本声明的法律后果 由本人承担。 作者签名： - t _ 磁 - 1 日期：蒯年3 月豳日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学 校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查 阅和借阅。本人授权湖南大学可以将本学位论文的全部或部分内容编入有关 数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位 论文。 本学位论文属于 1 、保密口，在年解密后适用本授权书。 2 、不保密圉。 ( 请在以上相应方框内打“4 ”) 作者签名： 导师签名： - t 么 赫 劫妇 月月 ) j ，) 年年 ，口o洲删 期期 乙弋 硕士学位论文 1 1 引言 第1 章绪论 随着半导体技术和通信技术的发展，人类己经由p c 时代和网络时代，进入后 p c 时代。自m a r kw e i s e r 在1 9 9 1 年于s c i e n t i f i ca m e r i c a n ) ) 的“t h ec o m p u t e rf o r t h e 2 1 s tc e n t u r y ”一文中首次提出普适计算( u b i q u i t o u sc o m p u t i n g ) 思想以来，普适计 算作为2 l 世纪的计算模式，日益受到人们的关注和重视【l 2 ，3 一】。普适计算的基本思 想是强调把计算机嵌入到环境或日常工具中，让计算机外在的形式从人们的视线 中消失，使人们注意的中心回归到要完成的任务本身 5 , 6 1 。w e i s e r 的思想得到了广 泛的关注，许多相关的研究计划相继出台，如：d o n n o r m a n 的i n v i s i b l e c o m p u t e r 【，j ， c m u 的a u r a l3 1 ，m i t 的o x y g e np r o j e c t 8 】以及欧盟的d i s a p p e a r i n gc o m p u t e r t g l 等。针 对普适计算的各个方面，国内外的研究团体从不同的切入点进行了各有侧重的研 究，如：清华大学侧重于智能空间领域【2 】，而s t i c k - e n o t e s 【l ，c o n t e x t t o o l k i t 1 等则侧重于察觉上下文计算( c o n t e x t a w a r ec o m p u t i n g ) 等等i l 。 随着无线通信技术和芯片技术的发展而出现的无线传感器网络是普适计算思 想的典型应用之一。它在军事侦察、工业生产控制、森林火灾监控、太空探索等 高危或人难以接近的环境中具有独特的应用优势。因此它引起了世界许多国家的 军事部门、工业界和学术界的极大关注，并已成为目前研究的一个热点领域【i ”。 1 2 传感器网络概述 无线传感器网络是一种无基础设施的无线网络，它综合了传感器技术、嵌入 式计算技术、分布式信息处理技术和无线通信技术，能够协作地实时监测、感知 和采集网络分布区域内的各种环境或监测对象的信息，并对这些数据进行处理， 获得详尽而准确的信息，传送到需要这些信息的用户 1 4 1 5 。对于大规模布置的传 感器网络，其一般的系统模型及节点组成分别如图1 1 、图1 2 所示。网络一般由 多个传感器节点( s e n s o rn o d e ) 和一个( 或几个) 汇集点( s i n k ) 组成，传感器节点收集 数据，对数据进行计算或融合后，经过单跳或多跳传输给s i n k i l “。 一方面，无线传感器网络被认为是2 1 世纪最重要的技术之一，它将会对人类 未来的生活方式产生巨大影响。麻省理工学院的技术评论杂志( t e c h n o l o g y r e v i e w ) 评出了对人类未来生活产生深远影响的十大新兴技术，无线传感器网络位 于这十种新技术之首【1 7 】。另一方面，m e m s 支持下的微型传感器技术和无线通信 能力为无线传感器网络赋予了广阔的应用前景，主要表现在军事、环境、医疗、 家庭和其他商业领域。当然，在空间探索和灾难拯救等特殊的领域，无线传感器 传感器网络中基于自适应的路由算法研究 网络也有其得天独厚的优势i l 。 无线传感器网络的研究起始于2 0 世纪9 0 年代末期，由于具有巨大的应用价值， 它己经引起了世界许多国家的军事界、工业界和学术界的极大关注。从2 0 0 0 年起， 国际上开始出现一些有关传感器网络研究的报道，美国自然科学基金委员会2 0 0 3 年制定了传感器网络研究计划，支持相关基础理论的研究。在美国自然科学基金 委员会的推动下，美国的加州大学伯克利分校、麻省理工学院、康奈尔大学、加 州大学洛杉矶分校等学校开始了传感器网络的基础理论和关键技术的研究。美国 国防部和各军事部门都对传感器网络高度重视，把传感器网络作为一个重要研究 领域，设立了一系列的军事传感器网络研究项目1 1 9 , 2 0 。美国英特尔公司、微软公 司等信息业巨头也开始了传感器网络方面的研究工作。日本、德国、英国、意大 利等科技发达国家也对无线传感器网络表现出了极大的兴趣，纷纷展开了该领域 的研究工作u “。 图1 1 传感器网络系统模型 我国在传感器网络方面的研究也日益增多，一些高校和研究机构已经积极开 展了相关的工作，如：国家自然科学基金2 0 0 3 年资助的“基于能量高效的传感器 网络协议研究【2 2 1 ，2 0 0 4 年，国家自然科学基金委员会又将传感器网络列于2 6 个 本年度资助的重大项目之一。 图1 2 传感器网络节点组成 硕士学位论文 1 3 传感器网络的特点及其主要路由算法 从1 2 的概述中，我们可以看出微型传感器技术和节点间的无线通信能力使得 传感器网络有着广阔应用前景的同时，也使传感器网络具有与传统网络明显不同 的特点1 2 3 以9 1 ，概括起来主要有如下几点： ( 1 ) 节点数量众多，分布密集。由于传感器网络通常工作在人难以接近或者危 险的区域内，为了对一个区域执行监测任务，往往有成千上万传感器节点空投到 该区域，外界的不确定性使得必须布置大量的传感节点并使之协同工作才能完成 信息收集等任务：同时利用节点之间高度连接性来保证系统的容错性和抗毁性。 ( 2 ) 传感器节点的存储空间、计算能力和能量非常有限。节点由于受价格、体 积和功耗的限制，其计算能力、程序空间和内存空间比普通的计算机功能要弱很 多。技术的进步会降低器件的成本，但就目前的现状而言传感器节点资源紧张的 状况还不会得到迅速的缓解。 ( 3 ) 电源容量有限，能耗是被首要考虑的因素。传感器网络特殊的应用领域 决定了节点散布之后，不能更换电池或给电池充电，一旦电池能量用完，这个节 点也就失去了作用( 死亡) 。因此，降低和平衡节点能耗，延长网络的生存时间 就成为传感器网络研究中的一个关键领域，在传感器网络设计过程中，任何技术 和协议的使用都要以节能为前提。 传感器网络的这些与众不同的特点导致了它在网络层上与传统网络的极大不 同，a d h o e 网络中常用的反应式或者预路由协议，如：d s r 30 1 、d s d v 【3 1 1 、a o d v 3 2 】 等均不适合于传感器网络这类节点资源有限的网络。 针对传感器网络的特质，很多研究人员对其进行了研究，并提出了一些新颖的 算法和思想。其 g o s s i p i n g i ”j 是对f l o o d i n g l 3 3 】的改进，前者中要发送数据的节点 在其邻居节点中随机的选择一个发送。s a r ”j 则依据每条路径上的能量资源和 q o s 要求来决策路由。为了避免因节点故障重新计算路由所带来的开销，s a r 采 用了多路径路由方案。随后研究人员提出了通过协商的传感器协议s p i n 【j ”，通过 发送描述传感器数据的信息，而不是发送所有的数据( 例如图象) 来节省能量。 以e s t r i n 等为代表的研究人员提出了以节点所拥有的数据而不是节点本身的标识 进行路由选择和数据转发的路由协议，典型协议如d d 3 5 】、g r a b 3 6 1 等。其基本思 想是：节点收集信息并发送和接收与“兴趣”匹配的信息，中间节点依据开始就已 建立的一个以接收节点为目标的“梯度场”转发报文。由于算法还可以在中间节点 进行数据汇集，因而可以进一步降低需要发送的数据量。但上述算法均属于集中 式算法，要求每个传感器节点维护全局性的网络状态信息，因此不具备良好的可 扩展性和可维护性【3 。”。另一方面，由于平面路由协议要求所有传感器节点均具有 路由功能，导致了节点因能量消耗过快而失效，因此使得网络拓扑结构经常发生 传感器网络中基于自适应的路由算法研究 变化，路由性能较低。 为了尽可能地延长节点的生存期限，提高网络的稳定性与路由性能，研究人 员提出了层次路由的思想，通过分层来达到网络的可扩展性，典型协议有 l e a c h 3 8 l 、t e e n 3 9 1 、p e g a s i s l 4 0 l 等，其中l e a c h 的基本思想是将网络划分为 簇，簇内节点的数据发送和接收由簇头负责，而簇头的选取算法使得簇内节点能 够轮流担任簇头以平衡每个节点的能耗。p e g a s i s 和t e e n 则是对l e a c h 的进 一步改进，p e g a s i s 将收集数据的节点组成一个链的方式实现数据汇集，汇聚之 后仅需一个节点和s i n k 直接通信。而t e e n 和l e a c h 的实现机制非常相似，只是 前者是响应型的，而后者属于主动型传感器网络。在t e e n 中定义了硬、软两个 门限值，以确定是否需要发送监测数据。但通常该类协议从一轮( r o u n d ) 到另一轮 的切换是周期性进行的与网络本身的工作状态关联性不大，没有结合考虑当前的 网络状态。 1 4 本文所做的主要工作 由于传感器网络目前正处于研究阶段，在网络的各个层面都有许多技术难题 值得讨论，本文针对传感器网络在网络层中基于自适应的路由算法进行研究。本 文主要工作归纳如下： 1 对传感器网络中的路由算法进行了分类，描述了两种主要的平面和分簇路 由算法的思想及特点。 2 对洪泛算法进行了研究，针对洪泛算法能耗过大、网络中报文冗余量过大 的缺点，提出了一种基于延迟的自适应洪泛路由算法。算法的主要思想是初始化 阶段后，源节点先在全网内用较小的路由请求报文( r o u t i n g r e q u e s t p a c k e t s ，r r e q ) 和路由回复报文( r o u t i n gr e p l yp a c k e t s ，r r e p ) 来建立路由，在建立路由的过程中 当有节点收到r r e q 后若它比上一跳节点离s i n k 更远或该报文的t t l 一1 = 0 则它 不转发r r e q 并丢弃该报文；否则节点先等待一段时间看是否有更优的来自同一 s o u r c e 的r r e q 到来，若有则转发更优的r r e q 直到s i n k 。s i n k 接收到r r e q 后 向最优路回复r r e p 。而后源节点再沿着建立好的路径转发较大的数据报文。 3 针对l e a c h 路由模型分簇时未结合考虑当前的网络状态的缺点，提出了 一种基于a h p 的自适应分簇路由算法。算法引入a h p 4 1 , 4 2 1 来确定权值，利用若干 权重因子的组合( 权重因子的组合综合地反映了网络的当前状态) 来选取簇头并形 成簇，故簇头的选取无需周期性的进行而是按需自适应的选取。新算法利用本轮 选出的簇头和s i n k 构建当前轮的虚拟骨干网络 4 3 , 4 4 】，再针对该虚拟骨干网络建立 路由。分析结果表明，算法在保留分簇算法优点的同时，能进一步的节约能量， 并能有效均衡节点能耗。 4 虽然基于a h p 的自适应分簇路由算法性能较l e a c h 有所提高，但算法中 分簇和重新选簇头总是一起进行的，故分簇时的开销还可以进一步的降低。为此， 零文提出了一种对彼置敏感盼自适应分簇路由模型，算法仍弓| 入a h p 建模，用基 于若干权熬因子的缀合来选取簇头并形成簇。簇形成后簇头在本簇内轮换，当达 爨援应懿条终螽孬繁藜分簇。分毒厅结巢表赘，舞法不双舆有较低静复杂瘦，瑟显 能有效地平衡节点熊耗，从而增大网络吞吐量。 全文燕要包含如下六个部分，各部分内容安排如下；第一章绪论介绍传感 器网络静襁关背景黻及本文掰徽豹工作；第二章禚关研究工作，包括黄感器稠络 中常见路幽算法研究，常见路由算法的思想，殿据此对传感器网络中的路由算法 送孬毂分撰魄较；繁三章绩感嚣网络枣基于慈迟鲍自适应洪泛爨杰箕法磷究，毽 括对新算法的具体描述，理论分析和实验分析；第四章传感器网络中基于层次分 析法的自邋应分簇路由算法研究，包括该算法的基本思想以及理论分析和模拟实 验结采；第五章簧懑器网络孛对链登敏感静骞逶应分簇貉出算法研究，毽褥算法 的基本思想、理论分析和模拟实验结聚；最后总结全文。 ：堡譬矍里丝塞董垂星重星墼些里塞鎏堡薹 2 1 引言 第2 章相关研究工作 无线传感器网络的路由协议目前是国内外研究的热点，各种路由协议在不同 的应用环境和性能评价指标下各有优缺点【。由于无线传感器网络的特殊性使得 需要针对其设计不同的路由算法。本文简要介绍其中一些典型的路由协议，分析 这些协议的基本原理以借鉴前人的设计思想，在结合无线传感器网络的特点基础 上设计出新的更合适的路由协议。 2 2 传感器网络路由算法分类 目前提出的传感器网络路由协议主要有两类：平面和层次路由协议。 2 2 1 平面路由算法 平面路由算法主要特点有：所需的信息域较小，一般仅需一跳( 1h o p ) 内的信 息；无需进行周期性的路由信息维护；复杂度较低。 表2 1 列出了一些传感器网络中的平面路由算法。其中： ( 1 ) 扩散法( f l o o d i n g ) 3 3 l ：扩散法是一种传统的网络通信路出协议。源节点 s o u r c e 将报文传送给它的每一个邻居节点，每一个邻居节点又将其传输给各自的 所有邻居节点。如此继续下去，直到将数据传输到汇集点s i n k 或为该报文所设定的 生命期限变为零为止。 ( 2 ) 闲聊法( g o s s i p i n g ) 1 3 3 1 ：g o s s i p i n g 是对f l o o d i n g 算法的一种改进，算法 中节点随机选取一个相邻节点转发它接收到的分组，而不是采用广播形式。这种 方法避免了消息的“内爆”现象，但有可能增加端到端的传输延时。 ( 3 ) s a r ( s e q u e n t i a la s s i g n m e n tr o u t i n g ) 1 3 4 j ：算法创建多颗树，每颗树的 树根都是s i n k 的一跳邻居。在算法的初始阶段，树从根节点开始，不断吸收新的 节点加入。在树延伸的过程中，将避免那些q o s 不好及能量已经消耗较多的节点。 初始阶段结束后，大多数节点都加入了某个树，各节点只需要知道自己的上一跳 邻居，以转发报文。在网络工作过程中，一些树可能由于中间节点能量耗尽而断 开，也可能有新的节点加入网络而使网络拓扑结构发生变化。所以网关周期性的 发起“重新建立路径”的命令，以保证网络的连通性和最优的服务质量。 ( 4 ) s p i nfs e n s o rp r o t o c o lf o ri n f o r m a t i o nv i an e g o t i a t i o n ) 3 7 1 ：算法用临时的 请求应答方式转发数据。s o u r c e 和收到数据的节点向其邻接点发广告报文a d v 表 示自己有数据要发送( a d v 中包括了对即将发送数据的描述) ；有兴趣的邻接点 发r e q 报文响应；而后发送节点将数据封装为d a t a 发送过去，如此转发直到s i n k 。 发r e q 报文响应；而后发送节点将数据封装为d a t a 发送过击，如此转发直到s i n k 。 硕士学位论文 算法通过使用节点间的协商制度和资源自适应机制，解决了f l o o d i n g 中存在的不 足之处，即为了避免出现扩散法的信息爆炸问题和部分重叠现象，传感器节点在传 送数据之前彼此进行协商，协商制度可确保传输有用数据。另外，节点间通过发送 源数据( 即描述传感器节点采集的数据属性的数据) 而不是采集的整个数据进行协 商。 ( 5 ) 定向扩散( d i r e c t e d d i f f u s i o n ，d d ) 1 3 5 1 ：该模型是e s t r i n 等人针对传感器 节点资源有限等特点设计的路由策略。其实现机制如下：s i n k 向所有传感器节点 发送兴趣( 兴趣是通过分配不同的属性值来表示不同任务的描述符) ，每个传感器 节点在收到兴趣后将其保存在各自的c a c h e 中。每个兴趣项包含一个时间标签 域和若干个梯度域。当一个兴趣传遍整个网络后，从s o u r c e 到s i n k 之间的梯度就 建立起来了，梯度反映了网络中节点对匹配请求条件的数据源的近似判断。一旦 s o u r c e 采集到兴趣所需的数据，那么它将沿着该兴趣的梯度路径传输数据到汇集 点或基站。 d d 中的网络梯度思想源自生物学中的蚂蚁种群模型。研究人员在实验过程中 发现，绝大多数盲蚂蚁在擦肩而过时通过彼此发送信息激素可找到一条从源点到 目标点的最短路径。透过这一现象，将其思想引用到网络中就产生了网络梯度的概 念。图2 1 描述了定向扩散模型的基本工作原理。 a 兴趣传播阶段b 初始梯度的建立c 数据沿增强路径传输 图2 1 d i ) 的实现机制 ( 6 ) 基于最小代价场的路由算法【4 5 】：算法开始之前，所有的节点都将自己的 代价设为无穷大。网关广播一个代价为0 的广告报文，其他节点接收到广告报文 后，如果报文中所表示的代价小于节点自己的代价，则使用这个新的代价作为自 己的代价，并将新的代价广播出去；反之，则丢弃该信息。最终每个节点都获得 了自己距离网关的最小代价，由此建立代价场，报文沿着最小代价路径向网关发 送。当报文被发送的时候它将附带源节点的最小代价，及从源节点到当前节点所 消耗的代价，一个邻居节点接收到报文，只有该报文已消耗的代价和自己的代价 之和等于源节点代价的时候，才转发这个报文。采用这种方法，节点不需要维持 任何的路径信息，就可以实现报文的最短路径发送。 传感器弼终串基于叁适应瓣鼹由算法研究 表2 1 常见的平面膝由算法 惠辣 童要愚恕 f l o o d i n g 收到数据的节点向所有邻膦节点广播掇文 g o s s i p i n g 收到数据的节点随机选取地选择一个邻节点转发报文 s a r 依据每条黠经上懿糍量资滚耱q o s 要求寒决策臻盘 s p i n根据临时的请求应答的方式转发数据 在所有节点中为s i n k 的请浆建立一个临越的“梯度”场；匹配数 蛰d 据沿“梯度”最大懿方囱孛继鞠s i n k 基于鼯小代价场每个节点获得了自己距离嘲关的最小代价后建立代价场，报文 鲢路由算法港着最小代价路径自疆关发送 2 2 2 层次路由算法 在屡次路由算法中，网络邋常被划分为簇( c l u s t e r ) ，每个簇由个簇头 ( c l u s t e r h e a d ) 帮多个簇成员( c l u s t e r - m e m b e r ) 经戒，诋一级霞络稳簇头是意一 级网络中的簇成员。在这种分级结构中，簇歇不仅负责簇内信息的收集和融合处 理，还负责簇间数据转发。层次路由协议中簇的形成通常是基于节点的能量和其 与簇头阉熬距离。必了延长整拿瓣终熬生存期，簇头节感嚣要周羯更凝。层次路 由的优点是便于管理，可以对系统交纯做出快速反应，能够提供高葳激的通信服 务，能廉利用率较高。但簇的维护开销较大。 表2 2 列出了一些经典的平面算法。 ( 1 ) l e a c h ( l o w - e n e r g ya d a p t i v ec l u s t e r i n gh i e r a r c h y ) f 3 8 1 ：该协议是枣 h e i n z e l m a n 等人提出的。协议将操作分为若干轮( r o u n d ) ，每轮包括创建阶段和 稳定运行阶段。在创建阶段，每个节点取一个介于0 和1 之间的随机数q 。若q 大 予门限燕荆刘该节淼残蔻簇头。 当节点 g 时门限值r f m ；j 一；否则t ( n ) = 0 。其中p 是簇头总 、。 i p r m o d ( 1 p ) 】 鼗占全部繁赢蒽数豹露分晓；r 怒姿藩熬轮次；g 是在爱逐二竣没有或必簇头款节 p 点集合。 丽爝，簇头向所肖节点广播邀一消息。依据接收信号舱强度，节点选择它所要 宓羹入麓缀，并告蠡稳疲翡簇头。程稳定工 睾除致，繁熹接绥采集整涎数撵，传绘本 簇簇头，簇头进行数据融合处理后将数据发遴至l j s i n k 。稳定工作阶段持续一段时 间后，熬个网络进入下一轮工作周期，重新选择簇头并分簇。 硕士学位论文 ( 2 ) t e e n ( t h f c s h o l ds e n s i t i v ee n e r g ye f f i c i e n ts e n s o m e t w o r kp r o t o c 0 1 ) f 3 9 】： t e e n 和l e a c h 的实现机制j 常相似，只是t e e n 中定义了硬、软两个门限值，以确 定是季需要发送簸涮数据。哭有当传薅器稔涌静信息超过了设定的门限时才向簇 头发送数据。当簸测数据第一次超过设定的硬门限时，繁点闵宅佟必鼗熬硬 1 限， 并在接着到来的时隙内发送它。在接下来的过程中，如果监测数据的变化幅度大 予软门限界定的范围，瑚节点传送最新采集的数据，并将它设寇为新的硬门限。 透过调节软门限傻蟾大小，可以在监测精发和系绞毙糍之阕取缮合理豹乎缀。当 检测的值超过了硬门槛，它被立刻发送出去；如果当前检测的值与上一次之差超 过了软门限，也被立刻发送出去。采弼这样的方法，可以髓视一些突发事件和热 点蟪区，减小网络内传辕戆摄文数量。 ( 3 ) p e g a s i s ( p o w e r e f f i c i e n tg a t l l e f i n gi ns e n s o ri n f o r m a t i o ns y s t e m s ) ； p e g a s i s 也是由l e a c h 发袋而来。它假定组成网络的传感器节点是同构且静止的， 繁点发送能蓬递竣豹溅试售号，遗过检测应签寒确定离蠡己凝运鹣魍邻带点。逶_ ；霪 这种方式使网络中的所有节点了解彼此的位置关系，进而每个节点依据自融的位 鬣选择要加入的簇。簇头参照位置关系优化出到s i n k 节点的礞佳链路。因为 p e g a s i s 孛每令繁轰都戬最小珐率发送数豢分维，并寿务 孛兜成必要懿数据激舍， 减小业务流疑，因此整个网络的功耗较小。但其缺点在于节点维护位置信息需要 额外的资源，而这一位置信息相港于传统网络中的拓扑信息。 ( 4 ) e s t r i n 等天掇遗了多瑟分簇算法一耱薪黧懿分簇安溪瓿糕p q 。工稼 在网络中的传感器节点处于不同的层，所处层次越高，传感器能覆盖的面积就越 大。开始时所有节点均在最低层，通过竞争获得提升商层的机会。在每个工作周 鬃结索蓐，态淫节点将援自己静获态蕊惑( 黧有秃子苇杰，珐率是否充足等) 决定楚 否让出簇头位置。 ( 5 ) y o u n i s 等人提出了基于三层体系结构的路由协议【4 “。与l e a c h 不同 静是，该诲议要求在掰络运行蘸崮葵赣露户将传懑器节熹翔分藏簇，并通知每个 麟头节点的i d 标识和簇内所分配苗点的位爨信息。簇内节点可以以感知、转发、 感知并转发、休眠这四种方式之一存在。簇头不受能量的限制，它可以监控节点 静能量变纯，决寇著维护抟感器静酉释状态，并秘蔫代侨函数襻为链貉成本，选 择最小成本的路镪作为节点与其通信的最优路径。 2 3 小结 本章将传感器网络中的路由算法分为两类：平面和层次的路由算法。随后， 零奉分季厅了涎类路枣冀法冬鑫瘊英毒懿特点：乎瑟鼹囊算法具考复杂发 毳，实瑷 简单的优点；而屡次路由算法则具有关键点数量占节点总数比例较低，节约能量 的特点。对传感器网络而言，能将上述两方面优点结合起来的路由算法才怒较理 垡壁登旦堑主茎王皂垩查盟堕虫墨鲨堡空 想的，本文在后面的章节中提出了一些相应的算法试图结合平面和层次路由策略 的优点。 表2 2 常见的层次路由算法 名称主要思想 操作分为若干轮( r o u n d ) ，每轮包括创建和稳定运行阶 l e a c h 段。创建阶段选簇头分簇，稳定运行阶段进行数据融合 和数据转发。周期性的重新选簇头分簇 t e e n 定义了硬、软两个门限值，以确定是否需要发送监测数据 节点发送能量递减的测试信号，通过检测应答来确定离 p e g a s i s 自己最近的相邻节点 多层分簇算法 工作在网络中的传感器节点处于不同的层。 基于三层体系结构利用代价函数作为链路成本，选择晟小成本的路径作为 的路由协议节点与其通信的最优路径 硕士学位论文 第3 章传感器网络中基于延迟的自适应洪泛路由算法 研究 3 1 引言 洪泛( f l o o d i n g ) 路由算法是一种经典的路由算法，由于其具有实现简单，容错 能力强等特点，无论在有线网络中还是在无线网络中都得到了广泛的应用。 基于传感节点的存储、计算能力及能量方面的限制，应用于传感器网络的路 由算法应实现简单，耗费资源少，以提高网络的生存时间。因此，由于实现简单， 洪泛算法在传感器网络中也得到了广泛应用。但是洪泛算法能耗过大的缺点又在 相当程度上抵消了其优势，使其不适合直接地应用于无线传感器网络。如果将洪 泛作为一种路由算法应用于传感器网络，需要解决其能耗过大、数据冗余量高问 题。如d d 、s p i n 、g o s s i p i n g 等算法都是f l o o d i n g 的改进算法( 详见第二章) 。本章 在介绍了洪泛路由模型之后，针对其缺点，提出了一种基于延迟的自适应洪泛路 由算法( s e l f - a d a p t i v ef l o o d i n gb a s e do i ld e l a y ，下文简称s f d ) ，并给出了复杂 度分析和实验结果分析，最后小结本章。 3 2 传统洪泛模型 在洪泛算法中，任一节点托接收到报文的动作可用如下伪代码描述。每个报 文都包含t t l ( 报文存活时间) 、d a t a ( 数据) 等内容。算法基本步骤如下： s t e p l ：s i n k 和其他节点广播自己的位置信息和序列号： s t e p 2 ：源节点广播报文； s t e p 3 ：若收到报文的节点为s i n k 则报文己传送到目的地；否则转s t e p 4 ：