（通信与信息系统专业论文）无线传感器网络中基于位置信息的路由算法研究.pdf

额 ：学位论文 摘要 集数据采集、处理及通信于一体的无线集成传感器网络以其低廉的价格、便利的部 霁方式聂褥到越_ 柬越泛靛搜掰，对 晕蕊器网络各令方嚣静曩驿究整痰为弱翦学术器j 鬻 活跃的课题。而路由算法问题怒传感器网络的关键问题之一，本文管重研究传感器刚络 中基于经置信惑熬踺由算法。 根据传感器网络所具有严格的能量限制，冗余的低速数据流和多对。的通信方式等 不弱予铸绞a dh o e 弼终豹特点，本文蓠先毙骏分捱了瑷青无线绩感嚣瓣络嚣一些典型 路山协议，在此基础卜提出了种结台数掘汇集技术和基于角度的多径路山算法，算法 中多个源节点蘑宠将监溅数提发送至慕、汇聚添节点，缀过数撼汇集意，览节点蝮汇聚 的数据识沿多祭路径发送到s i n k 节点。分析和实验结果表明新算法能有效节约节点能 量，具蠢良好的路由性黢。考感到基翦溅行躲些应鼹予传感器网络的鼹出算法都要求 所有节点处于工作状态，使得在探测区域内的许多耵点耗费了大量能量，基于此本文提 出一秘结合位毂信息进行密度捻制的节能路由葵法。算法选择一部分节点使其：l ：馋薅其 他节点休眠，并在合适的时刻唤醒其代替能量糍尽的节点，模拟实验结聚表明，算法在 网络节点分靠稠密时能够有效地提高网络性能。最后，本文提豳一静基予网格期 l l 线转 发的路由算法，其基本慰想是将整个网络划分为合适大小的网格，在每个网格内控制真 正工作的节点个数为l ，晦其他节点完全处于体眠状态弗在合邋的时刻苏醒查露其是否 应该处于工作、捩态。同时，工作节点采用b 样祭曲线 笮为数据转发轨迹进行报文转发， 理论分析和实验结果表明新的算法具有较好的性能，可以有效地延长网络的生存时问。 关键询：传惑器网络；路由；能耗平衡；多路径；刚格：密度控制：曲线路由 臆线传感器网络中鏊1 i 何置信息的路由算法研究 a b s t r a c t w ；r e l e s si n t e g r a t e ds e n s o rn e t w o r k s ，w h i c hi n c l u d ec o l l e c t i n m a n a g i n gd a t aa n d c o m m u n i c a t i o n ，a r eu s e dm o r ea n dm o r ew 试e l yf o fi t sl o wo o s t 鑫n dc o n v e n i e n td e p i o y m e n t ， n o w a d 秘”t h er e s e a r c hc o n c e m i n ge a c ha s p e c to fs e n s o rn e t w o r k si sf a i r l ya c t i v e r o u t i n gi s o n eo fm ek e yp r o b l e m si ns e n s o rn e t w o r k sa n dt h i st h e s i sm a i n l yf o c u s e so nt h er o u t i n g a l g o r 主t h 黼sb a s e do np 。s i t i o n 抽圭o m l a t i o n s e n s o rn e t w o r k sd i 鹏rf r o mt r a d t i o n a ln e t w o r k si ns e v e r a l 、张y s ：s e n s o rn e t w o r k sh a v e s e v e 诧e n e f g yc o n s 拄a i n t s ，r e d u n d a n tl o r a 把蕊a ，a n dm 鞠y 如一o n en o w s b a s e do n 氆e s e c h a r a c t e “s t i c s ，c h l st h e s i sn r s t l ya n a l y z e ss o m et y p i c a lr o u t i n gp r o t o c o l si nw i r e l e s ss e n s o r n e 觏。蠢s ，a n dt h e n 部 s 稻瑚a r dan e wr o h t i n ga l g o r i t h 玎1w h i c ht 酞e sa d v a n t a g co 腩o t ld a t a a g g r e g a t i o na n dr o u t i n ga n g l eb a s e dm u l t i p a t hr o u t i n g s i nt h ea l g o r i m m ，t 1 1 es o u r c en o d e s o n l ys e n dd 采am o n i o f 。莲t 。s o m ea g g 辩g a i es o u r c en o d e ，a n dt h e n 主h ea g g r e g a t en o d e c o n c e n ”a t e st h ei n f o r m a t i o ni tr e c e i v e da n ds e n d sac o n v e 曜e n tp a c k e tt ot h es i n kb y m u l i p 鑫t h 。t 羲e o r e l i c 张a l y s i sa n ds i 瑚u l a t i o n r e s 挂l t ss h o w 睡矗t 攮en e w 锺g o r i 氇激h e p s s a v i n gn o d e se n e r g ye m c i e n t l ya n dh a sg o o dr o u t i n gp e r f o r m a l l c e s c o n s i d e r i n gt h a tt | l e c u # e n t 羚u t i n g 建l g o f i 氇掰si ns e 赣s o r 建e t w o 吱sa 孵d e s 适n e d 铅r e s o l v eh o wt o 船v ee n e r g y w h e na l l1 1 0 d e sa r ew o r k i n g ，h o w e v e r ，e n e r g yo fn o d e sa r ew a s t e de n o r m o u s l y ，s oan e w 埘n ga l g o r i 谯搬c o m b i 稳 珏g 疆es 拄髓t 掰嚣o f 酾纛谢氆蠢e 璐i t y e o 躐li sp r 。筘s 礤法越s t h e s i s 1 en e wa l g o r i t h mj u s ts e l e c t ss o m en o d e st 0w o r ka n do t l l e r st os l e e pw h i c hw i l lb e w a k e n e 硅埝r e 争l a c ed e n o d e sa 圭a p 争p f ia _ 蹬t i 越e ，a 强l y s i s 鼹ds 濂珏l a 鼍主。扭糟s u 鹣 d e m o n s t r a t et h a tt h en e wa l g o r i t l l mp m l o n g st h et i m et ol i v ei ns o m em e a s u r e f i n a l ly ，t h j s t h 文sp r o p o san e wa l 斑h mw h i 馥鹏i n e s 饿蛾e t u 瓣o f 蟛硅w 浊飘苟e c t o 移b 矗s 醛 f o n v a r d i n ga l g o m m t h ea l g o r i t 胁c o n s t m c t st h cs u i t a b l eg r i d a tf i r s t ，t h e nc o n t m l st h e 躺m b e ro f w k i n gn o d et ob eo n l y 蛐e ，繇d 峨eo 谯嚣rn o d e sw i l lg 托擎w 甜蛄n g 跹d 幽蹿醢畦l t h er i g h tt i m et ow a k eu pt or 印l a c et h ed i e dw o r k i n gn o d e ，w o r k j n gn o d e sf o r w a r dd 砒aw i m t b fs u b s e q u e n n ht h e o r e t ；ca n 出y s i sa n ds i m u l 敷i o nr e s u l t sl n d i c 戤e 也a tt h en e wa l g 两如m a c h i e v e sl o a db a l a n c i n ga n dp m v i d e sb e t t e rn e t 、v o r kp 曲r n l a n c e k e y w o r d s ：s 。n s o rn e 铆o r k s ；r o u t i n g ；e n e 唱y e m c i e n t ；m u l t i p a m ；g r i d ；d e n s i t yc o m m l ； c u r v e b a s e df o u “n g 硕t 学侮论文 插图索亏| 冈1 1 传感器阐络节点的组成一2 图l ，2 传感器网络的体系结构一2 一 图2 1 扩散法的消息内璨闷题一8 一 图2 2 扩敞法的消息重凝问题一8 一 隅2 3d d 协议的路出艨理一9 - 圈2 4 传感节点定位系统原理图一1 0 一 蓠2 5g e r a 中的递鞠穗理裁两簿法一i o 一 图3 1a c 协议和d c 协议一1 3 - 圈3 2 傣惑器溺络豹事 辛半径缓型一 3 一 图3 3 传感器网络的随机源节点模型一1 3 - 强3 ，4 薅交角确定兹跨国节点鬃w v i 一 5 一 图3 5 动态路由构建和维护一1 5 - 鞫3 。6 器算法嬲络懿平臻寿螽魄鞍一2 l 图3 7 a d c 协泌_ f 的网络寿命，- 2 l 一 蠹3 ，8 鑫算法嘲络平均吞睦量懿魄较一2 2 一 图3 9 平均能耗比较一2 2 一 圈3 ，1 0 不嗣冗余疫下a d c 篓法霜要熬平均蹒数一2 2 图3 1 1 释算法网络健壮性的比较一2 2 一 圈4 稠密l 主瑷一2 5 一 图4 2 稀疏情况一2 5 一 阁4 3 网格构遗一2 7 * 图4 4 单个网格一2 7 一 露4 5 顶点比例隧半径鞠网硌边长的变化一3 l 一 阔4 6 顶点比例随节点半径和密度的变化一3 1 一 图4 7 节点比例随半径和密度的变化一3 l 一 图4 8 节点比例随半径和网格边长的变纯一3 1 一 圈4 9 平均路径长度随角度和半径的变化一3 2 一 图4 1 0 平均路径长度随角度和密度的变纯一3 2 一 阁4 1l 节点失效率随节点通信半径的变化。- 3 2 * 淘4 1 2 节点失散率随嗣络密度的变化一3 2 一 图5 1 节点冗余一3 5 - 图5 2g a f 虚撅阚格一3 5 一 图5 3t b f 转发模型一3 5 一 i i i 瓷线传惑器耐络中墓i 侮鬣信感钧路由舞法研究 斟5 。4 r 变 芝时，a p 变化趋势图， 圈5 5r 变化时，a p l 变化趋势蚓 懋5 6g 1 、转r a 下阏络中节点存活搴 图5 7g t b r a 下网络吞吐慑 图5 8 萤点失散比例隧r 的变化 图5 9 节点失效比例随n 的变化 。毒0 一 。- 4 0 ，4 l 。 4 l 。 。4 l + 湖南大学 学位论文原创性声明 本人郑煎声明：所呈交的论文是本人在导师的指导下独立进行研究所取 缮蛉疆究残祭。除了文中姆剐加以标注弓l 臻豹内容於，本论文不翘含经何其 他个人或集体已经发表或撰写的成果作品。对本文的研究做出重耍贡献的个 久和集体，均已奁文中良羁确方式标朝。奉久完全意谈弱本声鞠舱法律后巢 由本人承担。 作者签名： 弘鼙 日期：细步年， 层，目 学位论文版权使用授权书 本学位论文 乍者完全了解学校有关谦留、使瘸学位沧文的规定，同意学 校保鼷并向圈家有哭部门或机构送交论文的复印件和电子舨，允许论文被查 阅和借阅。本人授权湖南大学可以将本学位论文的全部或部分内容编入有关 数据摩进行检索，可以采填影印、缡印或扫糖等复到手段傈存秘汇编本学位 论文。 本学位谂文藩予 l 、保密口，在年解密后适用本授权书。 2 、不 ；i ；密硒。 ( 请在以上相应方框内打“”) 作者签名： 爵师签名： 彭蜀 霹麓：弦莎年f 胡， 墨 日期：州年f 。月l 日 硕十学何论文 1 1 引言 第1 章绪论 计算技术的发展需要与之相适应的计算模式，计算模式在2 0 世纪8 0 年代经历了从 主机计算( m 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 t i n g ) 的革命，极大地推动了计 算机技术和产业的发展，同时随着无线通信技术及微机械系统的发展也_ 孕育了一种全新 的计算模式，这就是普适计算( u b i q u i t o u sc o m p 嘶n g ) 。 普适计算最早源予1 9 8 8 年x e r o x 队r c 实验室计划。浚计划主持人m a r k w e i s e rr 1 9 9 1 年在s c i e n t i f i c a m e r i c a n 的“t h e c o m p u t e r f o r t h e2 l “c e n t i l r y ”中提出，普适 计算的基本思想是强调把计算机嵌入到环境或r 常工具中，让计算机本身从人们的视线 中消失，使人们注意的中心回归到要完成的任务本身。w e i s e r 的思想得到了广泛的关注， 许多相关的研究计划相继出台，如：d o n n o n t l a n 的i n v i s i b l ec o m p u t c r 吐c m u 的a u m n m i t 的0 x y g e np r o j e c t 【4 】以及欧盟的d i s a p p e a r i n gc o m p u t e 一等。针对普适计算的各个方 面，国内外的研究团体从不同的切入点进行了各有侧重的研究，如：清华大学侧重于智 能空间领域【6 】，而s t i c k en o t e s nc o n t e x tt o o l k i t 【8 1 等则侧重于察觉上下文计算 ( c o n t e x t a w a r ec o m p u t i n g ) 等等。 在普适计算思想的影响下，计算、通信和传感器3 项技术交叉应用，无线传感器网 络( w i r e l e s ss e n s o r n e t w o r k s ，简称w s n s ) 作为这3 项技术相结合的产物应运而生。它 是一种新的信息获取和处理网络，因其在一些诸如军事侦察、工业生产控制、森林火灾 监控、太空探索等高危或人难以接近的环境中所具有的独特优势，而得到了政府、军方、 跨国公司及研究人员的关注，也成为目前研究的一个热点。 1 2 无线传感器网络的体系结构及其应用 传感器网络是由大量体积小、成本低、具有无线通信、传感、数据处理的传感器节 点( s e n s o rn o d e ) 组成的，传感器节点一般由数据采集、数据处理、数据传输和电源四 部分组成，被监测物理信号的形式则决定了传感器的类型。其中，数据采集部分负责采 集被监测对象的原始数据，采集到的原始数据经过数据处理后，通过无线网络传输到一 个数据汇聚中心节点( s i l l l 【) ，s i i l k 再通过因特网或卫星传输到用户数据处理中心。处 理器通常选用嵌入式c p u ，如m o t o m l a 的6 8 h c l 6 ，a r m 公司的a r m 7 和i n t e l 的8 0 8 6 等。数据传输单元主要由低功耗、短距离的无线通信模块组成，比如r f m 公司的t r l 0 0 0 等例。因为需要进行较复杂的任务调度与管理，系统需要一个微型化的操作系统，u c b e r i l e y 为此专门丌发了t i n y o s ，同时，u c o s i i 和嵌入式l i n u x 等也是不错的选择。 图1 1 描述了传感器网络节点的组成，其中箭头的方向表示了数掘在节点中的流动方向 无线传感器嘲络中基j 二位置信息的路由辫法研究 扎 对j ：大巍搂白甏妁传感器两络，其一般豹系统模型l 虿以翻鹫1 2 籀述。大量俊感节 点通过飞 ，器散播、人 ：埋置和火箭弹射蒋方式被敞句到监测区域，以自组织形式构成 嗣络，运过多魏( m u l t i 一沁p s ) 中缵方式稳楚测数攥传羁s i 瞌节点( 接收节点) ，鼓终语 助长距离绒临时矬立的s i l l k 链路将整个区域内的数据通过i n t e m e t 、卫星婶方式传送到 远程中心送行集中处理。 图1 1 传感器网络节点的组成 图t 2 传感翳嘲络的体系结梅 随着微型传弛器技术、无线通信技术、微机电系统制造技术以及嵌入式技术的发展， 集感知、存健计葵秘通信能力于一体的无线集成传感器开始在军攀、环壤、健康、家庭 和其他商娥领域得到越来越广泛的应用。 军事领域的辫求是传感器嚼终褥以迅速发展和被广泛应用的搬动力餐，也是馋感器 嘲络最为熟型的一种应用。由于传感器网络是由大量稠密分布低成本的节点所组成的， 而且节点的自组织能力又使得整个网络具有一定的容错性不会由于某些节点的失效丽 崩溃，再加上其翁予快速部署的特点都使得传感器网络能适应恶劣的战场环境，能够有 效地监控冲突区域，侦察敞方兵力部署和地形，定位攻击跨标，详估毁伤效果， 贞察和 探溺核、生、纯攻击等，及时准确地将采集至各种信息，通过汇聚节点s i n k 传输到各 级指挥部门，为指挥决策提供及时准确地佑息。传感器网络最早在军事方面的应用来源 予美国先滋国防磷寇项哥揭d a r p a d e n s ea d v a n c e dr e s e a 鹅hp r o i e 髓sa g e n c y ) 豹一个 项目研究j 。此后，相关项目层出不穷，如：9 0 年代中期的l m i m ( 1 0 w - p o 屯r 谢懈l e s s i n e g r a 把d 舾e f os e n s o r s ) 项疆 1 2 】和1 9 9 s 年豹s 鞠s 狂项舀吲簿。 随着人们对于环境的网益关注，环境科学所涉及的范围越来越广泛，通过传统方式 采榘滠戆数据是一侔困难豹e 睾。传惑器阏络兔辩井蘧梳往熬磅究数据获取提供了方 便，比如，野生动物栖息地生态环境监控、森林火情监控、河道水文监测及水灾预警等。 a o e 毅州l 系统q ，魏有数季孛传感器束整测辫雨量、瀚拳承位鞠主壤承分，并依琵蓣测瀑发 j j i 的j 能性| l “。类似地，传感器 嘲络也可以应刷在精细农业中，以监测农作物中的害 虫、量壤故酸躐浚秘藏登状凝等。 硕十学何论文 在医疗 ：，通过在住院病人身上安装特殊用途的传感器节点，如心率和血压监测设 备，利用传感器网络，医生就可以实时掌握病人的病情，一旦发生危急情况可在第时 间及时处理i l 。还可以利用传感器网络长时间地收集人的生理数据，根掘这些数掘研制 新的药品。此外，在药物管理等诸多方面，它也有新颖而独特的应用。 这些研究为传感器网络的应用提供了范例，也展现了传感器网络巨大的应用价值， 目前国内外无论是政府、研究机构还是跨国公司都对传感器网络的研究投入了极大的关 注。美国自然科学基龠委员会2 0 0 3 年制定了传感器网络研究计划，美国国防部和军事 部门更是对传感器网络给予了高度重视，在上面提到的有关军事传感器系统的s e n s l t 项目下就有来自2 5 个研究机构的2 9 个研究项目在进行研究。而一些信息产业的跨国公 司，如：英特尔公司、微软公司等，也开始了传感器网络方面的研究。h 本、德圈、英 国等发达国家也对传感器网络表现出了极大的兴趣。我国在传感器网络方面的研究还相 对较少，但一些高校和研究机构已经积极开展了有关传感器网络方面的研究，如：国家 自然科学基会2 0 0 3 年资助的“基于能量高效的传感器网络协议研究”。 1 3 无线传感器网络的特点及研究热点 从1 2 的概述中，我们可以看出微型传感器技术和节点间的无线通信能力使得传感 器网络有着广阔应用前景的同时，也使得传感器网络具有与传统网络明显不同的特点 b ”珈】，概括起来主要有如下几点： ( 1 ) 网络内节点分布极其稠密。由于传感器网络节点的微型化，每个节点的通信和 传感半径很有限，一般为十几米范围之内，而且为了节能，传感器节点大部分时间处于 睡眠状态，所以往往通过铺设大量的传感节点来保证网络的质量，传感器网络的节点数 量和密度都要比a dh o c 网络高几个数量级，甚至达到每平方米上百个节点的密度。这 会带来一系列问题，如信号冲突、信息的存放传送路径的选择，大量节点之间如何协同 工作等。 ( 2 ) 传感节点的存储空间、计算能力和能量非常有限。传感节点的成本是传感器网 络应用中所必须考虑的，低成本使得传感节点只能使用价格低廉、可靠性较低的器件构 成。技术的进步会降低器件的成本，但就目前而言传感节点资源紧张的状况不会得到迅 速的缓解，而且这也使得节点抵抗外界攻击的能力较弱，如何提高传感器网络的安全性 是一个极为困难的问题； ( 3 ) 能耗是被首要考虑的因素。由于传感器网络的工作环境所限，节点散向之后， 其能源通常是无法更换的，而这和普通无线自主网a dh o c 网络是很不相同的，因此， 降低和平衡节点能耗，延长网络的生存时阳j 就成为传感器网络研究中的一个关键领域； ( 4 ) 节点绝大多数是静止的。一般意义上的传感器网络应用不要求节点其有移动性， 返降低了相当一部分有关控制通信量的丌销，也使得传感器嘲络可以应用些有特点的 路山算法，相比之下，m a n e t ( m o b ea dh o cn e t w o r k s ) 的关键就是解决山于节点的移 无线传感器捌络中基) 二位置信息的路由镩法研究 动性所带来的问题。 羁凌在为盘，搀感器嘲络弱 i ； 究大致经过了疆个除段。第l 除段主要镳萋巅蠲镞誊t 电技术设计小裂化的：博点没备，代表性的研究项目有w i n s 【2 l j 和s m a nd u s t ；列、于网络 奎身闽题懿关注秘磷究霹以谈为楚传感器婀终磷究的第2 除段，联瓣l 卜在城为无线弼终 研究领域的一个不小的热点。 从网络分层模型弱焦度分攒，每一层都毫纛簧结合簧感爨网络豹特点送行细致硬窕 的问题，就已有的研究而占，主要集中在网络层和链路层。在网络层重点讨论更加适合 予传感器网终的路由协议，本文捷在第二肇中详缨余绍嚣翦应用予无线赞感器网终的路 m 算法：考虑到蜂窝电话网络、a d ，h o c 和监牙技术这些当前主流的无线网络技术的m a c 协没均不逑合无线传感器网络，在链路屡主要设计菠的低功耗m a c 协议，目前几秘典 型的m a c 协议有s m a c s f 2 2 l ，基于c s m a 介质访问控制和t d m a f d m a 组合方案 【2 引。除了蚓终自身的问题以外，还毒许多关键阀题也引越了研究袭广泛的兴趣，主要集 中存如何从系统角度出发：爷省功耗以及与应用相关的共性技术。 4 本文所俸的主要王作 由子传感器阏络嚣嚣讴娃子研究阶段，在窝终豹各令菇面都窍许多技术难题德褥讨 论，本文只针对传感器网络在网络层中基予位置信息的路由算法进行研究。定位技术不 是奉文臻究赘重点。本文灵是应潮摄据定位技术可以褥剽节熹静像嚣信惑藤进行下一步 的讨论。本文主要工作归纳如下： 1 藤结蠛寄鹣应蠲予无线技感器羁终豹籍凌协议，遥行篱擎茨分类，对院了足耱 主要的路豳算法的特点，并在理论上进行了性能比较； 2 。钛多径鼹瞧的惑怒窭发，考虑至数据冗余闲遂，捷遗一秘带有数据汇集懿基予 角度的多径路由算法，分析结果袭明，算法一定程度上克服了数据冗余问题，多祭路径 的路峦逡撂方式鸯效地延长了网终毂生存瓣闻； 3 针对传感器网络节点稠密布置且节点能量有限的问题，本文提出一种结合网格 续构积密疲控制愚想验爨由算法，冀法选择逶当数量的王终繁点壤盏探测区域，避巍降 低数据冗余，而通过有效地划分网格也降低了密胰控制的难度。分析结果表明，新算法 在繁点密度较高鲍情况下，可以有效地程网辏内实现密度控制的隧的，降低同鞋工作的 节点数目； 4 。擞据3 的研究，必了进一步降低在密度控制阶段寻找控制点鲍难度，以及避免 算法巾完祷服务点失效时无其他柑点替代的情况，本文提出一种熬于网稽和曲线转发的 路山算法，算法拯网络划分为更力睢小的网格并限定网格内的工 乍节点个数为l ，工作 耵点之删基了：骱线进行数据转发。分析结果表明新的算法在节点檄其稠密的情况下，可 以火大殛k 网络的生存周期，算法采用旗予轨迹的数据转发方式大大简化了数据转发过 程，也其育一定朝安全住。 硕士学位论文 全文主要包含五个部分，各部分内容安排如下：第章绪论介绍无线传感器网络 的蜘关骛景以及本文所擞的工 乍；第章无线传感器燃终路由协汶穗关磷究i 謦包括 对现在流行的应用于无线传感器网络的路由协议的介绍蒂u 分类，以及掘此对几种媳型路 娃算法遴行的理论分板比较；第i 章无线传感器网络中基于角发的多镪路由箕法硪究 甑括基本的路由模型介绍，数据汇集算法和基于角度的路由算法描述，赫于角度的带自 数据汇集的多径路由构建以及理论分析和模拟实验结果；第四章无线传感器网络中基 于密度控制的路由算法包括密魔控带4 模型，网格构造算法，密魔控制实现算法以及路 幽算法描述，实验结果及分析等：第五露传感器网络中基于网格和曲线转发的路由算 法包括潮格模黧，曲线转发模辍以及路径构造算法，横拟实验结果和分析等；最后总 结全文。 ：! ：垒釜璧釜矍竺童塞 堡墼堡星竺坠皇兰鎏：i 耋 第2 章无线传感器网络路由协议相关研究工作 2 1 引言 如本文13 节的描述，传感器网络的这些与众不同的特点导敛r 传感器网络在网络 层上与传统网络有极大不同：无线传感器网络路出设计的重要目标是降低节点能源损 耗，提高网络生命周期；而传统的无线a dh o c 网络的路由协议设计的首要任务是移动 条件下高服务质量的提供。这些不同导致了传统的无线a dh o c 网络路由协议不能直接 用于无线传感器嗍络中，同时也吸引了众多的研究人员对其进行研究，并提出了许多新 颖的路由算法和思想。 本章首先剥现有的无线传感器网络路由协议按其实现方法的特点进行了分类，然后 对每种类别中的兆型协议进行了分析和比较，虽后展望了无线传感器网络中这些路由协 议未来的研究重点。 2 2 无线传感器网络的路由协议设计目标 由r 传感器网络具有小刊于传统a dh o c 网络的构成特性和应用特点，设计传感器 网络巾的路山i 办议应考虑一下几个方面的目标”0 52 日： 1 ) 低能耗：算法应尽可能节省节点的能量。由于通信的能量消耗一般都远大于计 算的能量消耗，因此应博可能减少通信开销。 2 ) 具有能量感知( e n e r g y a w a r c ) 功能：由于传感器网络通常工作在人们无法接近 的恶劣甚至危险的远程环境中，能源无法补充，因此算法应尽可能地使网络中所有节点 的能耗均衡，延长网络生存时间。 3 ) 鲁棒性：算法应具各自适应及容错性，无需人于涉即可自行适应各种应用环境。 4 ) 可伸缩性：出于传感器网络规模大且节点资源有限，因此算法应该是分布式的， 路由选择时只需依赖局部信息即可。 5 ) 低延时性：算法必须满足应用的低延时要求。 2 3 现有的无线传感器网络路由协议的分类 针对无线传感器网络路山i 办议的上述设计目标，人们设计了各种不同的路 ；i 算法， j 将它们大致分为四类：洪泛式路由协议，层次式路由协议，以数据为中心的路由协议， 以及基于位置信息的路出协议。 1 洪泛式蹄m 挑议”：这是。种传统的广播路由技术，在洪泛协议中，任意接收 剑消息分纰怕1 y 点以广橘形式日其所柏邻居点转发分组，直到消息分组达到目的节点或 剑消息分纰怕1 y 点以广橘形式日其所柏邻居点转发分组，直到消息分组达到目的节点或 硕十譬佗论文 者超时。洪泛山于不需要路【u 维护和网络拓扑结构，在某些节点失效时仍能进行有效踏 鑫显具蠢延l 童小襄分匆式戆特点。对于舞耀织懿转感嚣网络，洪泛式鼹| l 是秘鞍至瞧2 的实现方法，但容易带柬消息的“内爆”( i m p l o s i o n ) 和“重叠”( o v e r l a p ) ”“，f n j ”已没 蠢考虑熊源方露靛限割，具鸯“瓷溺盲点”( r e u k eb l i n d n e s s ) 瓣缺点。 2 层次式路由协议1 2 82 9 】：它的基本思想足利用传感节点划分为簇( c l u s t e r ) 的方刘： 来对网终进行层次划分，只有英中的簇头( c l u s t e 哇e 撼) 蠢负责鼹由的转发。在层次鼹 由协议中只有部分节点负责路由信息的转发，这种方式能满足传感器网络的可扩展忭， 蠢效的维持传感节点的能量消耗，从露延长网络生命周期。 3 以数据为中心的路由协议m 2 】：它提出对传感器网络中的数据阁特定的描述方 式命名，数摆传送基于数据查询并依赖数据命名，所有的数据透信都限制局部藏困内。 在这种协议中，s i n k 节点关心的不再是节点的地址，而燕具有某种特征的数据；丽且由 于协议对应的源节点一般有多个，且彼此| h 采集的原始数据可熊重复，为了减少通信开 销，节点在向s i n k 传输数据的过程中，进行数据会聚、合并处理，再转发到下一节点， 妊此达到节能的目的。 4 。基于位嚣信息的路由协议 i ：它和用节点的位镶信息，粑查询或者数据转发给 需要的地域，从而缩减数据的传送范围。实际上许多传感器网络的路由协议都假设节t 的位餮信惠为醴知，所以可以方便的利闱节点的位置信息将节点分为不嗣的域( r e g i o n ) 。 基于域j 款行数据传送能缩减传邀范围缓和中间节点，从而延长网络生命周期。 2 4 几种典型路由协议的分析 本节将对2 3 中提出的四凝路由协议中的几种具有代表性的典型协议进杼分析说 明。 2 4 1 扩散法( f i o o d i n g ) f 1 0 0 d i n 卫【27 】一种传统的网络通信路由协议。假设节点s 希望发送一数据包给节点d ， 镬臻f l d i n g 遴嚣臻由逡器时，节点s 蔫先逶遭嬲终将数握副本传送绘它夔每一个邻詹 节点，每一个邻居节点又将其倦输给各自的每一个邻居节点，除了刚刚给它们缴送数掘 剽本的繁点s 鳢。魏韭屯继续下去，壹到将数据传辕到基瓠节点d 舞止或嚣为该数撂敷设 定的生命期限变为零为止或者所有节点都已收到此数据副本为止。 泛洪路由实琨起寒魄较麓鼙，不霉溪为保持网络撼拎售息翻实瑰复杂的路鞋毒发残算 法而消耗计算资源，适用于健壮性要求高的场合。但足存在信息爆炸的问题，即出现一 个节点弼能想到一个数擐多个剡本的琰象( 如强2 1 职示) ：且会出现部分重叠瑷象( 如 图2 2 所示) ，如果处于嗣观测朋；境的两个卡h 邻同类传感器节点同时对一个时间做 反 应，二蠹采集的数据性质相同，数值钽近，那么，这嬲个萤点的邻骚节点将收到双份数 无线传感器网络中基f 仲黄信息的路由锋法研究 嘲副本；盲臼使用资源也是洪泛带来的个不良后果。 圈2 ， 扩散法的消息内爆问题圈2 2 扩散法的消息重豢问题 2 4 2 低功耗翻适应聚类路e l i 算法( l e c h ) l e a c h 牡鞋嫠第一个在无线传惑器两络中提出的层次式路出协议，是一种典攀的基 0 二单层簇的协议。其主要思想为在每个周期内通过一个概率函数随机选择簇头，l 士 簇头 米平稳分瞧中继邋信韭务以实理延长溺络生命周期的疆静。l e a c h 定义了“轮”( r o u n d ) 的概念，晦一轮由初始化和稳定工作两个阶段组成。 在稳始仡貔段，陡瓿选择节点作为簇头，成为簇头豹节点向溺围广獾信息，獒匏节 点根据接收到的各个簇头节点广播信号强度，选择信号强度最大的簇头节点加入，向其 发送残为萁戒曼熬数撬惫。簇影贼后，簇头节点袋臻t d 秘a 策瓣分配遥港捷爱投给簇 内节点。 在稳定工馋玲段，簇头节点开始接投簇瘫各节点采集簸溅静数据，然嚣采臻数据聚 合和数据压缩等技术进行汇聚，将整合后的数据传输给终端节点。下一轮工作周期将重 瓤选择簇头节点。 簇头的建立过程是：节点从0 到l 的随机数中任意选择一个数值，若当前轮中这个 数傻大予设定的瞬篷 ( n 见公式2 。1 ) ，粼该节患成为簇头节点。 r 即，2 可姜他”g 口， | o其他 。1 ， 其中p 为节点中成为簇头节点的百分比：，怒当前轮数；g 慰在最后的坳轮中未 袋为簇头节点豹节点集台。 l e a c h 具有能量感知功能，能均衡节点的能量消耗，提高网络的稳定性与生命周 粥；但算法中对簇头爵透过长溪嵩信号发射矗续号角户遴雩亍逶信的经设不切实际，困我 算法的实用性较差，而且动态分簇会带来拓扑变换和大量广播这样的额外开销。 2 4 3i 苣l l j | l 散( d ir e c t e dd i f f u 8 i o n ) d i 聪e l e dd i 瀚s i o n l 3 “3 ”跫盘r i n 等久专门为终感器翻终设诗豹路由策龉，与已有的 蹄由算法有着截然1 i 同的实现机制。它以数据为t 扣心考虑路山，即每传感器节点利用 集中约定的属性( 称之为兴趣) 对其采集的数搠命t _ ；，s i n k 节点通过在l 叫络中传播其感 兴趣的属性去访问数据，中间节点根据这种兴趣向具有相应属性的方向去收集数据，由 此建立路由。d d 采用基于消息驱动的数掘传播模式，闰2 _ 3 描述了d d 协议的基本i 。 作原理。首先，如图2 3 ( a ) 所示，s i n k 节点发出的兴趣查询在节点问扩散，最终遍历 全网，找到所有与兴趣匹配的监测数据。在s i n k 节点的兴趣扩散过程中，有一个称为 “梯度( g r a d i e n t ) ”的变量与兴趣扩散过程相联系，记录这种匹配情况，为节点以后的 路由提供信息。如图2 3 ( b ) 所示，传感节点通过与s i n k 节点的兴趣匹配，最终将会 在整个网络中为s i n k 节点的请求建立个i 右时的“梯度”场，从而使得匹配数据可以 沿“梯度”最大的方向中继返回s i n k 节点。最后，如图2 3 ( c ) 所示，数据在回传s i l l l ( 节点的过程中，算法将利用沿途的中间节点进行数掘汇聚处理，从而使得数据传输的通 信丌销减低，达到节能的目的。 5 “o 、n。“o i l ，i ，、r 、 、”。，文。“o o 。糍0 沁。 os 。艮。，、。 ( a ) 请求扩散( b ) 梯度场建立( c ) 数据传输 圈2 3d d 协议的路由原理 由于“梯度”场的建立采用了数据汇集思想，因此d d 比传统的以地址为中心的协 议更节能。此外，d d 具有可伸缩性和鲁棒性好的特点。其缺点是“梯度”场的建立过 程复杂；兴趣重传和路径选择需要维护s i n k 节点的兴趣：数据命名只能针对于特定的 应用预先进行：初始查询的扩散开销大；数据总是沿最短路径进行传输，没考虑均衡所 有节点的能量消耗，因此不具有能量感知的性质。 2 4 4 基于位置和能量感知的路由算法( g 队r ) 为了进一步提高网络拓扑的稳定性，研究人员提出了基于位置信息的路由协议， g e a r 口驯是一种充分考虑了能源有效性的基于位置的路由协议。 g e a r 算法提出既然传感器网络中的数据经常包含了位置属性信息，那么可以利用 这一信息，把在整个网络中扩散的信息传送到适当的位置区域中，其中，传感节点可以 利用g p s 定位装置通过卫星定位等方式来获知自己的地理坐标位置，如图2 4 所示。同 样g e a r 也采用了查询驱动数据传送模式。它传送数据分组到目标域中所有的节点的过 程包括两个阶段：目标域数据传送和域内数据传送。 在l j 标域数掘传送阶段，当节点接收到数据分组，它将邻接点同【1 标域的距离和它 自己与同标域的距离棚比较，若存在更小j i ! | ! 离，则选择i i 童小距离的邻接一i 作为下一跳1 ， 无线传感嚣网络中基r 位置信息的路出算法研究 点：若小存在更小距离，则认为存在“h o l e ”，节点将根掂邻居的最小花销来选择下一跳 书点。 在域内数据传送阶敬，算法将利用一种递归地理转发算法( r e c u r s i v eg e o g r a p h i c f o r w a f d i 矬g ) 象避 亍数搽分发。烈2 。5 绘出了g e a r 协议中的递蛔地理转发算法溅璎， 阁中假设目标区域是一个矩形区域，且节点n i 收到发送给目标区域的数攒包p ；m l j 此时， n i 梅首先发现自己在目劫i 区域之中，然露如图2 5 所示，n l 将生成4 个数握包p 的拷 唾 分澍转发到目标区域的4 个子区域，当予区域中的某个节点收到此数据包后，重复上述 过程，盥然最终所有目的节点均能收到源节点发送的数据包p 。 s 琳越i 脚：s 砒l t ：l 鼍： s “m n 露2 4 传蒜带点定位系统愿毽塑 2 5 对典型协议的比较研究 。 o 、o 。，( ： o o 、_ 一 ， 一 ( ) “+、；i ? q 。夕n i 霾2 。sg e 融中熬递归避壤裁自篝法 。 l e a c h ，d i f c c t e dd i 靠u s i o n 和g e a r 协议克服了f l o o d i n g 协议的一些固有缺陷，在设 计上充分考虑节患能量脊限往酌特点，注震能量搜用效率闯题，在一定稷度上延长了整 个网络的生命周期。但是这些协议都是针对特定的应用丽设计，在不同的环境表现出各 蠢的特截和饶势，困】l 逝不能绝对的判断哪种协议壤优。 我们分析了缚种协议的特点，对它们在路由优化、路由健壮性、信息处理等方露的 表现绘毒了一个练台魄较，其钵翔表2 1 所示。 裘2 1 熊型协诚综合比较 d i r e c t e d 比较参数 f 1 0 0 d i n g l e a c hg e a r d i f f u s i o n 臻函优诧g l 力茏无鸯无 网络生命周期不长长长长 路幽健壮睦好较好好较鳋 数据聚集 无有有无 元数据描述符无无有有 数攒发送授式 迄续连续查询瓤动森诒j 驱动 硕卜学传论文 2 6 小结 本章对近年来针对无线传感器网络提出的路“j 协议进行了研究，并根掘它们的原理 差 i 铡及实瑷方漶将它嬲分为靼个主要类别。 洪泛式路由协议直接将接收到消息的结点以广播形式转发数掘包给所有的邻结点， f l o 谢i n g 协议魑最古老藤经典酶洪泛式路盘按议。虹蜒骞兹鼹决其消憨鹣“内爆”寒“重 疆”以及“资源肖点”的问题是葳研究目标。层次式路幽协议通过将传感节点分成不同 的簇来菇效转发传感数撼，影响簇形成秘簇头节点通信的因素楚德褥硬究静闻题，贯终， 在簇内避行的数据融台和处理过程也值得探索。以数据为中心的路由协议中，基于属性 谯组的命名机制对复杂的查询柬滋是不够的，鹾鼹它随羲应用变化，因北赢效据准的数 据命名机制和查询信息的高效传送是未来研究的方向。繁于位置信息的路由协议利用节 点的位嚣信息采进行数搬发送，g e a r 是充分考虑了能源有效性的基于位置数路由协 议。如何智能地利用节点的位置信息来进行高能散的路幽是研究的重点。 无绂传感器阀络中基r 何置信息的路出弹法研究 第3 章无线传感器网络中基于角度的多径路由算法 3 1 引裔 考虑到传感器网络所县有的特点，目1 i f 流行的传感器网络路由协议着燕于节熊以延 长网络静生存时间。文献l 硐疆出了一种多路径路出算法，在算法中，多条路径被颚先掏 建好，算法维护几条不相交的路径以保证在主干路径失效时使用。尽管该方法对洪泛区 域进行