（计算机科学与技术专业论文）基于拓扑管理的无线传感器网络路由算法研究.pdf

硕士学位论文：基于拓扑管理的无线传感器网络路由算法研究 摘要 级观计算机和通信网络进入人类社会的历史，人类经历了主机计算模式 ( m a i n f r 硼ec 0 p u t i n g ) 时代和桌面计算模式( d e s k t o pc o p u t i n g ) 时代，计算 范例开始跨入普适计算模式时代( u b i q u i t o u s p e r v a s i v ec o p u t i n g ) 。 在普适计算环境中，无线网络传感器( w i r e l e s sn e t w o r k e ds e n s o r s w s n ) 将 会得到大量应用。无线网络传感器集传感器、控制器、计算能力、通信能力于一 身，具有尺寸小、功耗低、并发操作密集、控制层次有限、面向具体应用设计等 区别于传统计算设备的典型特性。这些特性使其系统软件的设计工作充满了挑 战。 无线传感器网络作为普适计算环境一种新型数据采集的技术手段，在未来具 有无限光明的应用前景。目前，传感器网络许多相关技术内容仍然处于探索阶段， 比如：网络协议设计、能源管理、数据传输安全性和可靠性等问题。本文从解决 传感器网路路由协议算法角度进行探讨，作了一些有益的尝试。本文的主要工作 是研究基于无线传感器网络拓扑管理的路由算法研究及应用：设计基于最佳邻居 节点的无线传感器网络拓扑算法( b e s tn e i g h b o rb a s c dr i o p o l o g y a l g o r i t h i n ，】n b t a ) ，在b n b t a 的基础上设计了混合式无线传感器网络路由协议 ( h y m dr o u t i n gp m 幻c o lf o i 。w l e 鹳s 吼s o rn e t w o p w s n ) ，并研究h r p 唱n 在启发式侦听协议( h e l l r i s t i cl 立s t e n m ga c c o 蚰血gp m 眦o l m l 心) 测算无线传感 器网络中的活跃节点数目的应用。 关键字：普适计算，无线传感器网络，拓扑管理，路由算法，混合式路由，无线传感 器网络大小 a b s t i a c t 1 n e c 伽p u t l p gp a r a d i 鲫h a sc h a n g e d f r o mt h em a i n f r a e c o m p u t i n g p a r a d l 聃a n dt h ed e 站t o pc o m p u t i n g p a r a d i g i n t ot h ep e r v a s i v ec o p u t i n g p a r a d l 鲫an e wt y p eo fe m b e d d e dd e v i c e sc a l l e dw i r e l e s ss e n s o rn e t 哟r k s 吡1 c nc 0 趣b l n eal o w - p o w e r m i c r o c o n t r 0 1 l e r ( m c u ) ，s e v e r a ls t o r a g ed e v i c e s 。 as e to 士c o 衄u i l l c a t i o nd e v i c e sa n ds e n s o r sh a v eb e c o m ea g r e a tc h o i c ei n t h ep e r y a s i v ec o 皿p u t i n gp a r a d i g m b a s i n go nt h ed e v e l o p 珥e n to ft h e 鲫b e d d e ds y s t 鲫t e c h n 0 1 0 9 ya n dt h e p 号r v a s l v ec o m p u t i n gt e c h n o l o g y ， t h i st h e s i sf i r s t l ya n a l y z e st h e t y p i e a l c n a r a c t e r l s t l c sa n dt h eo r g a n i z a t i o no ft h ew i r e l e s ss e n s o rn e t w o r k sa 1 1 d l n v e s t l g a t e st h ea f f e c t i o nw h i c hi sb r o u g h ti n t ot h ec o n s t r u c t i o no ft h e s y s t e ms o f t 帆r er u n n i n go nt h e s ew i r e l e s ss e n s o rn e t w o r kd e v i c e sd u et o t h e i rt y p i c a lc h a r a c t e r i s t i c s 1n l st h e s l sp r o p o s e s ad i s t r i b u t e dt o p 0 1 0 9 y m a i l a g e e n ta l g o r i t l 】m ( b n b t a ) b a s e d0 nt h ec o n s t n 王c t i o no faf o r e s tf r o mt h et o p o l o g yo ft h e n e t w o r k a n dw e s t u d yt h ee f f e c to ft h et o p o l o g y 皿a n a g e 皿e 丑t t h e p e r f o r m a n c eo aw i r e l e 8 ss e n s o rn e t w o r kr o u t i n gp r o t o c 0 1 瞰p w sn 职p w s n 1 sa b a n d w i d t h e f f i c i e n tl o w d e l a yh y b r i dr o u t i n gp r o t o c 0 if o r 订r e i e s s s e n s o rn e t w 0 r k s i t i sah y b r i ds c h e ec o m b i n i n gr e a c t i v ea n d p r o a c t i v e a p p r o a c h e s an e wa r c h i t e c 车u r et h a t s e p a r a t e st o p o l o g yc r e a t i o nf r o m r o u t ed e t e 珊i n a t i o ni s d e s i g n e d t h i sa r c h i t e c t u r eo p t i 皿i z e s r o u t i n g p e r 士。蛐a n c ea c c o r d i n gt ot w 6c r i t e r i a ：n e t w o r k p r o p e r t i e sa n da p p l i c a t i o n r e q u l r e 珂e n t s r o p o l o g yc r e a t i 。ng e 玎e r a t e sa l o g i c a ls t r u c t u r e酊蚀 r e s p e c tt on e t w o r kp r o p e r t i e s ， a n dt h er o u t i n gp r o t o c o l d i s c o v e r sa n d m a i n t a l n sp a t h st os a t i s f ya p p l i c a t i o nr e q u i r e m e n t s o n ea p p i i c a t i o ni s d e s i g n e dt ot e s t i f yt h er o u t i n ga l g o r i t h 置e y 帕r d 岛：p e r y a s i v e c o m p u ti n g ，w i r el e s s s e n s o r n e t w o r k s ，t o p o l o g y m a n a g e m e n t ， r o u t i n ga l g o r i t h m ，h y b r i dr o u t i n gp r o t o c 0 1 ， n e t w o r ks i z e 硕士学位论文：基于拓扑管理的无线传感器网络路由算法研究 1 研究背景 1 _ 1 无线传感器阿络概况 纵观计算机和通信网络进入人类社会的历史，计算模式已经经历了主机计算 ( l a i n f r 锄ec o m p u t i n g ) 时代，现在正处在桌面计算( d e s k t o pc o m p u ti n g ) 时 代，未来的计算会是何种模式? 1 9 9 1 年，美国m w e i s e r 博士首次提出了 “u b i q u i t o u sc o p u t i n g ”的概念，对普适计算的思想进行了初步的阐述，开始 了人类向未来计算机时代探索的进程。i 蹦也在1 9 9 9 年创造了 “p e r v a s i v ec o p u t i n g ”这个名词。无论是“u b i q u i t o u sc o 皿p u t i n g ”或是 “p e r v a s i v ec o p u t i n g ”，他们把无所不在的计算，也就是“普适计算”的概念 引入到我们的视野。普适计算作为计算领域的第三波已经悄悄向我们走来。 在普适计算环境中，无线网络传感器( w i r e l e s sn e t w o r k e ds e n s o r s w s n ) 将 会得到大量应用。无线网络传感器集传感器、控制器、计算能力、通信能力于一 身，具有尺寸小、功耗低、并发操作密集、控制层次有限、面向具体应用设计等 区别于传统计算设备的典型特性。这些特性使其系统软件的设计工作充满了挑 战。 无线传感器网络( w i r e l e s ss e n s o rn e t w o r k w s n ) 是集信息采集、信息传 输、信息处理于一体的综合性智能信息系统。无线传感器网络通过各类集成化的 微型传感器协作进行实时感知、采集和监测各类感兴趣的研究信息和应用信息， 由嵌入式系统对信息进行处理，并通过随机自组织的无线通信网络以多跳中继方 式将信息传输到用户终端，从而实现“无处不在的计算”的普适计算理念。 无线传感器网络是多学科高度交叉的新兴前沿研究，它综合了嵌入式计算技 术、传感器技术、现代网络及无线通信技术、分布式信息处理技术等前沿技术。 无线传感器网络采用系统发展研究模式。它融合了先进微电子技术、系统芯片 s o c 设计技术、现代信息通讯技术、计算机网络技术，以实现系统多功能化、微 型化、系统化、集成化和网络化。无线传感器网络因为受先天硬件条件极其缺乏 的制约，在研究设计过程中尤其注重超低功耗设计。 硕士学位论文：基于拓补管理的无线传礴器网络路由算法研究 无线传感网络可以长期在无入干预的状态下工作，因此在套行各业均具有广 阔的应用前景。美国国际科学应用公司正在为美国国防部和国土安全部开发一个 无线传感器网络来检查、监测可疑行为和危险货物，并把警报发回指挥中心，以 帮助保护美国领土、桥梁、电厂和船只等重点区域和重点设施的系统。世界第二 大独立油品公司英国石油公司用无线传感器取代了网络中粗大而又笨重的有线 传感器。替换工作完成后，公司的华盛顿炼油厂的监控检测成本从每次数千美元 下降到每次数百美元。惠普公司正在美国田纳西州试验通过无线传感器网络改进 公司的物流管理办法。该试验性无线传感器网络由小型影音传感器组成，并与无 线射频识别技术相结合，以确保存货摆放位置正确。 无线传感器网络目前是在国际范围内广为关注的新兴前沿研究热点。无线传 感器网络技术极有可能发展成为一个新的数十亿美元规模的高科技市场。由美国 军方资助的学术研究机构和一些创业公司正在分头开展研究，跨国公司和全球最 大的i t 供应商们也已经将无线传感器网络列入研发计划。 1 2 无线传感器网络特性分析 在无线传感器网络环境中，通过飞机撒点、人工散布等方式将大量传感器节 点部署在感知对象内部或者四周。网络节点通过自组织方式完成两络拓扑。网络 节点之间以协作的方式感知、采集和处理网络覆盖区域的感兴趣的信息。无线传 感器网络可以在任意时刻采集、处理任意地点的特定信息。在无线传感器网络中 绝大多数节点的通信能力都很有限，咖墩节点的电能相对较高，发射能力因而 强一些，可以把数据发回远程控制节点。无线传感器网络以多跳中继方式将数据 传回s i n k 节点，最后借助s i n l 【链路将数据传送到远程控制中心进行集中处理。 硕士学位论文：基于拓扑管理的无线传感器网络路由算法研究 图1 1 无线传感器网络体系结构 无线传瘤器冈络应用设计所面临的挽战。 有限的资源：由于受到小尺寸、低造价和低功耗等限制，无线网络传感器的 物理资源很有限。尽管目前仍然是以平方厘米来衡量无线网络传感器的尺寸的， 但现在业内已经制造出尺寸小于5 平方毫米的网络传感器了。臼新月异的技术未 必能够突破这资源的局限性：根据m o o r e 定律，器件的尺寸和造价会以一定的速 度降低，但在功能未必会有新的突破。 电源能量有限：无线网络传感器的电源能量极其有限。无线网络中的传感器经 常由于电源能量的原因失效或废弃。电源能量的约束是阻碍无线传感器网络应用 发展的主要因素之一。在网络工作过程中如何节省能源，最大化网络的生命周期， 是无线传感器网络应用设计所面临的重大挑战之一。 计算能力有限：无线传感器网络中的传感器都具有嵌入式处理器和存储器它 们具备一定的计算能力，可以完成一些信息处理工作。然而，受尺寸和造价等因素 的限制，嵌入式处理器和存储器的能力和容量有限，因而计算能力十分有限。在 无线传感器网络应用设计中需要解决如何使用大量具有有限计算能力的传感器 进行协作分布式信息处理的问题。 由传感器跟环境的交互来驱动：无限网络传感器的驱动方式和传统的通用计 算机不同。和传统的通用计算机不一样，网络传感器是用作数据采集和现场环境 控制的，系统由传感器跟环境的交互来驱动。网络传感器的用途决定了在设计过 程中要注意以下两点：第一，网络传感器不是由和人的交互驱动的，也不是由批 处理驱动的，网络传感器基本上是由事件驱动的，并且会根据环境的变化做出相 应的反应。第二，事件的到达和数据的处理是并发活动，这需要设计一个恰当的 方法来进行并发控制，否则这种并发控制很容易导致竞争情况等潜在b u g 。 硕士学位论文：基于拓扑管理的无线传感器网络路由算法研究 传感器数：l 大、分布范凰广t 无线传感器网络中传感器节点分布密集、数量 巨大，或许可能达到几百万、几千万甚至更多。无线传感器网络适用于广泛的行 业广泛的地理区域，其用户数量非常可观。无线传感器数量大、分布广的特点使 得无线传感器网络的维护十分困难，甚至是不可维护的。因此，无线传感器网络 应用设计过程中必须确保软、硬件都有高强壮性和高容错性，必须保证应用设计 是可扩展的。 巨大的感知数据流：无线传感器网络中，每个传感器都有可能产生较大的实 时性流式数据。但是传感器的计算资源非常有限，难以处理大量的实时数据流。 因此在无线传感器网络应用设计的过程中需要注重分布式的数据流分析、查询和 挖掘等方法的研究。 网络动态性强：无线传感器网络中的传感器、感知对象和观察者这三要素都 可能具有移动性。网络中经常会出现新节点加入或者已有节点失效的现象。因此， 网络的拓扑结构是动态变化着的。传感器、感知对象和观察者三者之间的路径也 随之发生变化。因此无线传感器网络应用设计必须具备可重构、自适应和可扩展 等特性。 无线传感器网络应用设计的性能评估参照t 豫终生命周期t 无线传感器网络的生命周期是指从网络启动到网络无法再为 观察者提供需要的信息为止所持续的时间。无线传感器网络生命周期受软硬件等 各方面因素的影响。在无线传感器网络应用设计过程中，必须充分考虑能源有效 性，最大化网络的生命周期。 网络传输时间延迟：无线传感器网络的延迟时间是指从观察者发出请求到其 接收到回复信息所经历的时间。无线传感器网络时间延迟与其具体应用密切相关， 并直接影响无线传感器网络的适用性和应用范围。 网络寤知精度：无线传感器网络的感知精度是指观察者接收到的感知信息的 精度。感知精度受传感器精度、信息处理方法、网络通信协议等各方面因素的影 响和制约。网络感知精度、网络时间延迟和网络能量消耗之间具有密切的关系。 在无线传感器网络应用设计中，需要权衡这三方面的平衡。 网络可扩展性：无线传感器网络可扩展性具体体现在传感器数量、网络覆盖 硕士学位论文：基于拓扑管理的无线传感器网络路由算法研究 区域、网络生命周期、网络时间延迟和网络感知精度等方面可扩展的极限。 网络容错性；无线传感器网络中，传感器常常会因为周围环境干扰或电源耗 尽等原因失效。受环境以及无线传感器网络自身特性等各方面因素的制约，物理 地维护或替换失效传感器的可操作性通常很低，从经济效益角度看也不很合理。 因此，无线传感器网络应用设计过程中必须充分考虑软硬件的高容错性，以保障 系统的高健壮性。 能源使用效率：无线传感器网络的能源使用效率是指该网络在一定的能源条 件限制下能够处理的请求数量。目前，传感器网络的能源有效性还没有被模型化 和量化，需要进行进一步的研究。 1 3 研究现状和发展趋势 无线传感器网络是新一代的传感器网络，具有非常广泛的应用前景，其发展 和应用将会给人类的生活和生产的各个领域带来深远影响。发达国家非常重视无 线传感器网络的发展，m e e 正在努力推进无线传感器网络的应用和发展，波士 顿大学( b o s t o n u m v e r s i t y ) 还于最近创办了传感器网络协会 ( s e n s o rn e n o r kc o n s o m u m ) ，期望能促进传感器联网技术开发。除了波士顿大 学，该协会还包括b p 、霍尼韦尔( h 0 n e y w e ) 、h i e t c os y s t e m s 、 m v e n s y s 、 l _ 3c o m m u n i c a t i o n s 、m i 玎髓i l i a ln e t 、r a d i a n s e 、s e n s i c a s ts y s t e m s 及 t e x 廿o ns y s t e i i l s 。 国际上有关传感器网络的研究工作主要集中在经济发达的欧美地区。目前主 要的一些研究工程包括加州大学伯克利分校的传感器网络系统“s m a nd u s t ”、美 国麻省理工大学( m r r ) 的传感器网络研究项目“u 枷p s ”，以及美国r o c k w e l l 研究中心和加州大学洛杉矶分校合作的w 玳s ( 舭蟠h l t e g 眦e dn e t w o r k s e n s o r s ) 等等。 加州大学伯克利分校的传感器网络系统“s m a r td u s t ”由美国国防部高级研 究规划署( d a r l ) a ) 和h i t e l 公司等多家机构和基金组织资助，其目的是建立一 个分布式、可扩展的传感器网络。研究组研制的传感器节点一一m o t e 已经被5 0 0 多个研究机构采纳用作试验平台，其中与d n b o w 公司合作，已经推出一系列 传感器节点商品。加州大学伯克利分校研制的1 h y 0 s 操作系统和相关应用是开 硕士学位论文：基于拓扑管理的无线传感器网络路由算法研究 放源代码的，这对我们研究和开发传感嚣网络提供了一个极好的参考平台。 美国麻省理工大学( m r r ) 的传感器网络研究项目被命名为“u 怂佃s ”。该 项目的研究目标是为实现自适应的能量感知分布式微传感器开发一个框架。它研 究的重点放在信号、能量调节、通信以及协作等方面。它希望提供一个能量高效 和可扩展的传感器网络应用的解决方案，而不是特地关注某个具体的应用。 美国r o c k w e 研究中心和加州大学洛杉矶分校合作的w 埘s ( w h l e s s h l t e 蓼a t e dn e t w o r ks e i l s o r s ) 起步较早，其研究对象是在战场环境下使用的传感 器网络。南加州州立大学的s c a d d s ( s c a l a b l ec 0 0 f d ：m a t i o na r c l l i t e c t u r e sf 缸 d e 印l yd i s 仃i b u t e ds y s t e l i i s ) 项目来源于美国d a r p ：a 的s e r i s o rh l f o n n 撕o n t e c h n o l o g y ( s e n s m 工程，主要研究传感器网络的通信协议栈。其它的研究机构 包括：麻省理工学院、p r i n c c t o n 大学、r o c h e s t e r 大学、n o 棚a 大学以及意大利、 英国、德国的一些大学和研究机构等都对网络传感器各方面技术展开研究。 传感器网络的研究采用系统发展模式，必须融合现代先进的微电子技术、纳 米材料技术、微细加工技术、系统s o c ( s y s t e m o n c h i p ) 芯片设计技术、现代 信息通讯技术、计算机网络技术等融合，以实现微型化、集成化、多功能化及系 统化、网络化，特别是实现传感器网络特有的超低功耗系统设计。 美国的技术评论杂志在论述未来新兴十大技术时，更是将无线传感器网 络列为第一项未来新兴技术，商业周刊预测的未来四大新技术中，无线传感 器网络也列入其中。可以预计，无线传感器网络的广泛是一种必然趋势，它的出 现将会给人类社会带来极大的变革。 l - 4 本文工作 在无线传感器网络环境中，网络节点能量很有限，并且许多时候网络节点暴 露在极其恶劣的环境中，因此无线传感器网络节点的个体寿命很脆弱。另一方面， 为了延长网络节点的个体寿命和网络的整体寿命，网络节点的硬件设计和软件设 计都会考虑在网络运行活跃程度低的时间段内让网络节点切换到休眠节能状态。 所以，在无线传感器网络的成千上万个网络节点中，并不是所有的网络节点都是 处于活跃状态的，有些网络节点可能已经失效，有些网络节点可能正处于休眠节 能状态。因此，在研究和应用过程中，无线传感器网络被认为是由频繁发送或者 硕士学位论文：基于拓扑管理的无线传感器阿络路由算法研究 转发消息的活跃节点组成的。 普适计算是一门新兴的跨领域学科，它的发展势必要借助当今其他相关的成 熟技术。本文从普适计算带来的问题与挑战入手，分析无线传感器网络路由技术 在支持普适计算方面的技术基础，并在此之上提出了支持普适计算的基于拓扑管 理的混合式无线传感器网络路由协议( h y b 咖r o u 6 n gp r o t o c o lf o rw i f e l e s s s e n s o rn e t 、v o r k f 如i p w s n ) o 本文先提出了无线传感器网络拓扑算法e s t n e i g h b o rb a s e dt o p o l o g ya 1 9 0 r i t h l 棚n b t a ) 。并在b n b t a 的基础上设计了混合 式无线传感器网络路由协议( 坞黼dr o u 曲gp r o t o c o lf o rw i r e l e s s s e n s o r n e m o 懒p w s n ) 。在该路由协议的基础上，设计了启发式侦听协议( h e u r i s t i c “s t e l l j n g a c c o u n 垃1 1 9 p r o t o c 0 姻l a p ) 测算无线传感器网络中的活跃节点数目。 硕士学位论文；基于拓扑管理的无线传感器阿络路由算法研究 2 现有无限传感器网络路由协议研究 2 1 与路由设计相关的无线传瘳器网络特性 过去多年以来，无线传感器网络在数据收集和处理方面的协同工作和协作管 理采集活动的潜在应用价值受到越来越多的关注。但传感器节点自身能量供应和 带宽资源很有限，因此，寻找提高能量利用率、延长网络寿命的技术是非常必要 的。传感器节点自身的资源限制以及部署大量传感器节点的典型方式给传感器网 络管理和设计带来诸多挑战，因此，通信协议栈的所有层次实现能量感知是必要 的。比如，在网络层就很有必要寻找能效高的路由发现策略和将数据转播到s i l l k 节点的路由方法并尽可能实现网络寿命最大化。 传感器网络有着一些区别于传统无线网络的固有特征，因此，传统的无线网 络路由算法不能简单地移植到传感器网络上使用，而必须根据传感器网络自身特 点设计合适的路由算法。首先，传感器节点数量众多而维护节点d 开销很大， 因此在部署大规模无线传感器网络时建立节点统一寻址策略几乎是不可能的。因 此，不能简单地直接将传统的基于口地址寻址的路由协议应用于无线传感器网 络。此外，由于以多跳方式部署传感器节点。要求系统自主形成互连并以共同协 作的方式完成指定的任务，而且无线传感器网络操作常常是在无人监视的情况下 进行的。这些无线传感器网络需具各自我组织能力。况且在无线传感器网络中， 获取数据比了解采集该数据的源节点d 号更为重要，从这一点看，建立统一寻 址策略也是不必要的。其次，几乎所有的无线传感器网络应用都要求从多个源节 点采集的数据最终流向某个s i 呔节点，源与目标节点间呈现多对一的关系，这 不同于传统通信网络的数据流传输模式，比如：组播方式( 一对多关系) 或对等 模式( 一对一关系) 。再次，无线传感器网络节点严格受其自身能量、计算处理 能力、存储容量和带宽资源等诸多因素约束，因此，必须要求这些节点有效管理 利用资源以延长网络生命周期。再其次，无线传感器网络是面向特定应用定制的， 无线传感器网络设计随具体应用需求变化而变化。比如：军事上低时延精确战场 监控应用设计上不同于周期性野生动植物生态环境监测任务，前者要求采集的数 硕士学位论文：基于拓扑管理的无线传感器网络路由算法研究 据精确度高，传输速率快，数据安全，传输连续，实时性强；后者对数据精度要 求低，间歇性传输，传输速率慢。最后，无线传感器网络中，通常有多个节点采 集同一现象的数据，数据冗余的可能性很大。如果合理利用这些冗余信息，路由 算法可以改善能量和带宽的利用率。而且，用户通常都是按照某些查询属性提出 数据请求的，即基于属性寻址。从这个意义上来说，无线传感器网络是以数据为 中心的。基于属性的寻址方法是由一组属性值对( a t 旺i b u 协v a h l e p a i r ) 查询组成 的。譬如如果查询某个房间温度大于4 5 摄氏度的火情预警事件，那么，只有那 些采集的温度数据大于4 5 摄氏度的传感器节点才会作出响应，并报告它们采集 的温度读数，其它节点则可以没有任何动作。 无线传感器网络固有的这些特征决定了它与传统网络的差距。该领域的研究 人员为此提出了许多解决传感器网络路由协议问题的新算法。无线传感器网络中 由于能量限制和节点状态改变引起频繁的不可预测的拓扑变化。所以在无线传感 器网络中发现和维持路由信息是个重要问题。为了降低能耗，目前文献中提到的 路由技术都采用了一些传统无线网络的路由策略，同时结合运用一些无线传感器 网络专用的处理技术，比如：数据聚集和网内处理、聚类、不同的节点角色分配 和以数据为中心的方法等。按网络结构可以分成平面、层次化和基于位置信息三 类路由技术。在平面路由协议中，所有节点角色相同。而层次化协议目标是：形 成多个类以便类头节点可以聚集数据，减少数据传输量，从而节约能量。基于位 置信息的路由协议利用位置信息转发数据到指定区域而不是整个网络。这些协议 也可根据协议操作的不同，分成多路径、查询、协商、q o s 和相关性等路由技术。 按照源节点到目标节点路径发现方式的不同，路由协议也可分成三类：主动式 ( p r o a c 叽e ) 、反应式( r e a c t i v e ) 和混合式( h y 蚰d ) 。主动式协议要求在路由数据 前所有路径已计算妥当，可以让发送出去的数据包立刻到达目标节点，不会有任 何时延，但是这种协议必须周期性广播信息以保持路径的时效性，所以相当浪费 网络带宽和能量，但是若要降低广播所造成的带宽浪费，就要拉长每次广播的间 隔时间，这又将会造成路由表不能及时正确反映网络拓扑变化情况；丽反应式协 议只在需要使用路径时才计算路径，其最大好处是带宽的使用量较小，只是数据 包传输平均时延较长。混合式协议组合运用前两类协议的思想，希望能充分利用 这两类协议的优点。 硕士学位论文：基于拓扑管理的无线传感器网络路由算法研究 2 2 现有的无限传感器网络路由协议 1 9 8 8 年“普适计算”模式的出现，伴随着微电子机械工程技术、通信技术和 c m o s 半导体技术等的不断成熟，传感器网络因此诞生，并成为一个新的热点研 究学科。经过各国研究人员多年的努力，传感器网络路由协议算法已有相当多的 积淀，按照网络结构路由协议算法划分成平面路由、层次化路由和基于位置信息 的路由三大类别；按协议操作规则可将其分成协商路由、多路径路由、q o s 路由、 查询路由和相关路由五大类。 1 平面路由协议 在平面多跳无线传感器网络中，平面路由协议通常要求每个节点扮演相同角 色，多个传感器节点协同执行数据采集任务。这种情况下产生了以数据为中心的 路由方法：即s i n k 节点对某一特定区域发送查询指令，等待该区域内的传感器节 点返回采集的数据。由于数据通过查询请求而产生，所以基于属性命名方法对描 述数据特性是必要的手段。以数据为中心的路由策略研究表明：通过多节点协同 操作和消除冗余数据可以节约能量，例如：s p 矾和定向扩散( 血t e dd i 舶s i o n ) 。 这两种协议推动了其它以数据为中心的路由协议的设计工作。 s p 矾( s e n s o rp m t o c o l sf b rh 曲咖a t i 伽v i an e g o t i a t i o n ) ：w h e i n z e l i n a i l 等人 提出了一类自适应的s p 确路由协议，该协议假定网络中所有节点都是潜在的s i n k 节点，每一个节点可给网络中的其它节点传播信息。这支持用户查询某一节点即 可获得所需的信息。s p 矾协议类利用相邻节点拥有类似数据的特点，所以只需 要发送其它节点不拥有的数据。此外，s p 协议类还运用数据协商策略和资源 自适应算法。运行s p 矾协议的节点各分配一个高级数据描述符用来完整描述它 们收集的数据，这个高级数据描述符称为元数据( m e t a 司a 诅) ，在任何数据发送 前执行元数据协商，这样确保没有冗余信息在网络中传输。元数据格式的语义是 针对特定应用定义的而不是在s p 烈中定义。比如：如果多个传感器节点覆盖了 某一已知区域，这些节点可能运用它们唯的d 号来报告元数据。此外，s p 矾 协议有权访问每个节点的当前能量水平，根据节点剩余能量水平调整协议运行方 式。这些协议以连续流数据传输模式工作，即使用户没有请求任何数据，也会在 整个网络发布信息。 s p n 协议类通过协商和资源自适应策略解决了扩散法( n o o d i n g ) 之不足。 硕士学位论文：基于拓扑管理的无线传感器同络路由算法研究 根据以下两个基本思想设计这类协议： 第一，各节点利用元数据进行协商，通过发送描述某一现象的传感数据而不 是监测到该现象的节点所采集的所有数据，减少数据传输量，从而可以高效操作 并且节约能量； 第二，改进传统的一些路由协议存在的缺陷。例如：扩散法祁基于闲聊的路 由协议，由于多传感器节点重叠覆盖监测区域，从而出现传送额外的不必要的多 个数据复本现象，因而造成能量和带宽浪费。扩散法的缺陷还在于信息爆炸问题， 即出现一个节点可能得到一个数据多个复本的现象，这个现象由多个节点将同一 数据复本发送给同一个节点引起。当两个相邻节点采集同一片区域时，将会给同 一个邻居节点发送数据包。另一缺陷是资源利用盲目性，指不加考虑节点能量有 限性特点而消耗大量能量，节点无法根据自身当前能量水平适当调整其活动状 态。 s p 矾协议的元数据协商策略解决了扩散法存在的典型问题，因而改善了能 效，节约了能量。s p 矾是一个三阶段的路由协议，节点可以使用三类数据包进 行通信：a d v 、r e q 和d a r a 。a d v 用于广播新数据，r e q 用于请求数据，d 触r a 才是包含用户所需的数据的数据包。当一个运行s p 矾协议的节点获得了它愿意 共享的新数据，协议开始运作，通过对邻居节点广播包含元数据的a d v 数据包， 让其所有邻居节点了解它拥有的数据。如果一个邻居节点对此数据感兴趣，它发 送i u q 数据包给对方，对方再将d 触f a 数据包发送给该邻居节点。收到数据的节 点和它的邻居节点重复同样的过程，结果，整个传感器网络中对该数据感兴趣的 节点都将收到一份数据复本。 s p 玳协议类优点之一在于将网络拓扑动态性这一复杂问题简化处理，节点不 需保存全局拓扑信息，只需了解并保存其单跳邻居节点的路由信息，所以保存的 信息量少，拓扑变化不会引起路由数据新的开销；优点之二在于s p 科协议类比 扩散法节约更多能量，元数据协商机制可以消除大量冗余信息。然而，s p 矾协 议类的数据广播机制不能保证数据传播到目标节点。 定向扩散( d i r e c t e dd i f n l s i o n ) ：c h l t 姐a 9 0 n 、i w a t 等人为传感器网络提出一种 新的数据采集通信模型，称为定向扩散。作为一种以数据为中心( d c ， d a t a c e n 缸i c ) 和应用感知的通信模型，定向扩散协议要求传感器节点产生的所有 硕士学位论文：基于拓扑管理的无线传感器网络路由算法研究 数据均以属性值对( a t i b u t e v a i u ep a i r s ) 命名。d c 模型的主要思想是通过将来 自不同源节点的数据聚集再重新路由达到消除冗余和最大程度降低数据传输量 的目的，因而，可节约网络能量和延长系统寿命。不像传统的端对端路由协议， d c 路由策略能找到从多个源节点到单一目标节点的路径，并进行网内聚合冗余 数据的操作。 在定向扩散通信模型中，多传感器节点一旦探测到事件，创建各自邻居节点 集合的梯度信息。s i l l k 节点通过广播嗜好( h 衄r e 8 t s ) 请求数据。所谓嗜好，指 用自然语言或高级语言描述了一个要求网络完成的查询任务。嗜好通过网络逐跳 扩散，每个节点在接收到嗜好后又将其广播给各自的邻居节点。一旦嗜好通过网 络传播到每一节点，建立梯度用于收集满足请求节点查询的数据，即s h l k 节点通 过散布嗜好查询数据，中间节点传播这些嗜好，收到嗜好的每个节点沿着向其发 送嗜好的节点建立梯度。这个过程持续到从源节点到s i l l k 节点之间梯度建立为 止。般地说，一个梯度详细说明了一个属性值和一个方向。沿着不同邻居节点 方向梯度强度可能不同，导致形成不同的信息流路径。一开始环路暂不作检查， 随后考虑将其移除。当嗜好按照某一局部规则符合梯度时，形成传播信息流的多 条路径，接着加强最佳路径以避免进一步扩散。为减少数据传输量和通信成本， 数据在路由过程中逐跳聚集。其目标是从源节点到s i 呔节点间找到一条好的聚集 树来获得所需的数据。当s i m 【节点收到来自源节点的数据后，它周期性刷新和 重发嗜好，因为嗜好不能保证可靠传输到整个网络，所以刷新和重发过程是必要 的。 运行定向扩散协议的所有传感器节点都是应用感知的，采用以经验为根据选 择路径和缓冲技术以及网内处理数据方法支持数据扩散，可以减少数据传输量， 节约能量。缓冲技术可提高效率、健壮性和多节点协商的伸缩性。是数据扩散模 型的精髓。定向扩散通信模型的另一用途是自主传播传感器网络某一区域的重要 事件。这类信息搜索方式仅适用于持续不变的查询。这对一次性查询服务不适用， 因为不值得仅仅为这一次查询而建立查询梯度。 运用于定向扩散通信模型的数据聚集方法性能受诸多因素影响：网络中源节 点位置，源节点个数和网络通信拓扑结构。为了调查这些因素影响情况，b h a s k a r 蹦s h n a m a c h a r i 等提出了两种源节点放置模型，这两种模型称为e r 模型( e v e i l t 硕士学位论文：基于拓扑管理的无线传感器网络路由算法研究 r a d i u s ) 和r s 模型( r 卸d o ms o u r c e s ) 。在e r 模型中，网络监控区域中的一个点 定义为一个事件位置，这可能对应于一辆汽车或传感器节点跟踪的其它现象。距 离事件小于等于s 该值称为感知事件的半径) 的所有非s i l l k 节点类的节点都看 作是数据源节点。源节点个数约为ns 2 n ，n 为单位面积的节点数。在r s 模型中， 各个源节点并不需要聚在一起。在这两种源节点放置模型中，对于给定的能量预 算，较多的源节点可连到s 硼( 节点。另外，按照依赖于具体应用的能耗标准，每 一个模型执行效果均较好。总之，关于所观测现象的动态性，用于定向扩散模型 的聚集策略所产生的能量节约量可转化为提供更好的网络健壮性。 定向扩散通信模型在两方面区别于s p 玳协议：第一，由于s i i l k 节点通过扩散 一些任务给传感器节点，要求其执行查询指令，所以，定向扩散协议按需产生数 据查询。而在s p 矾中，传感器广播用户所需数据的信息，从而允许感兴趣的节 点去查询那个数据；第二，定向扩散协议中所有通信是邻居节点之间进行的，每 个节点具备执行数据聚集和缓存的能力。相对s p 玳协议而言，定向扩散协议在 移动应用环境中适应能力较弱。此外，定向扩散通信模型可能不适用于要求持续 给s i n k 节点发送数据的应用，即可能不适用于连续流数据传输模型应用。而且， 查询和数据匹配工作可能需要额外的开销。 2 层次化路由协议 层次化或聚类路由策略，最早在有线网络中提出，是一种伸缩性好和通信效 率高的路由技术。因此，层次化路由概念也适用于传感器网络实现高能效的路由 技术。在层次化结构中，高能量传感器节点用于处理和发送信息，而低能量节点 用于执行对监控对象周围的数据采集工作。这意味着创建类和为类头节点分配特 定任务可为系统伸缩性、寿命和能效贡献极大好处。层次化路由通过执行数据聚 集和融合减少传输到s i i l l 【节点的数据量，降低类内各节点能耗，是一种有效改善 能量效率的解决方法。层次化路由主要由两个层次构成：一个层次用于创建类， 选择类头节点，另一个层次用于聚集和处理数据，路由数据。然而，这类路由方 法多数技术不关心路由，而是关心与多跳路由功能无关的一些问题，比如：哪个 节点负责处理和聚集数据，什么时候发送聚集后的数据，以及通信信道分配等内 容。 l e a c h ( l 0 we n 哪a d a p d v ec l 璐锄n gh i 鲫叽血y ) ：w - h e i n z e l m n 等人为 硕士学位论文：基于衔扑管理的无线传感器网络路由算法研究 传感器网络引入的一种层次化聚类路由算法，是一种采用分布式类形成技术的聚 类路由协议。l e a c h 随机选择若干传感器节点充当类头节点( c h s ， c l u s t e r - h e a d s ) ，让所有节点轮流充当类头节点以均匀承担能量开销。在l e a c h 协议中，类头节点将隶属于该类所有非类头节点( n o n c h s ，n o n c l u 辩阱h e a d s ) 采集的数据进行聚集处理，然后将聚集后的数据包发送到s i i l l 【节点减少传输数据 量。l e a c h 协议运用1 d m a c d m a 的m a c 协议减少类间和类内通信碰撞问题。 然而，由于数据聚集是集中的而且是周期性执行的，所以，这个协议适用于持续 性监测的传感器网络应用中。一个用户可能并不要求马上获得所需的所有数据， 所以，在这种情况下，周期性数据传输除可能耗尽节点有限的能量外，是没有必 要的做法。经过一定时间时隔后，类头角色须随机轮换以便传感器网络各节点的 能耗均匀。基于w h e i n z e l m a n 提出的仿真模型计算得出，仅需要节点总数的5 充当类头节点。l e a c h 协议操作分成两个阶段：聚类阶段( s e t l l pp h a ) 和稳定 状态阶段( s t e a d ys t a t ep h a s e ) 。在聚类阶段，建立类，选定类头节点。在稳定状 态阶段，才实际发生数据传输到s i n k 节点的现象。为了使能耗最小化，稳定状态 阶段持续的时间比聚类阶段长。聚类阶段和就绪阶段所持续的时间总和称为一个 回合或一轮( m l l n d ) 。 3 基于位置信息的路由协议 这类路由协议，传感器节点依靠位置信息进行寻址。邻居节点间的距离 可根据到来的信号强度进行估算。邻居节点的相对坐标通过节点间信息交换 4 _ 5 ，4 1 】来获得。换句话说，如果节点装配了小型低功率g p s 接收器 3 】，节点利 用g p s 通过直接与卫星通信可得到节点位置信息。为节约能量，若无状况出现， 一些基于位置信息的策略要求节点进入睡眠状态。让尽可能多的节点睡眠，可节 约更多的网络能量。 g a f ( g e 0 舯p h i ca d a p 晰ef i d e t y ) ：g a f 算法是一种为移动a dh o c 网络设计 的能量感知的基于位置的路由算法，同样对传感器网络也是适用的。该算法思想 是：网络覆盖范围首先被划分成若干个固定区域，形成一个虚拟网格：在每个区 域内，节点彼此协同充当不同角色，比如，一个区域内选举产生一个节点在一段 时间内保持清醒，接着其它节点进入睡眠；在该区域这个节点代表其它节点负责