（计算机软件与理论专业论文）一种基于leach的无线传感器网络路由算法.pdf

摘要 无线传感器网络由许多具有低功率无线收发装真的传感器节点组成，能够有 效地从不同环境监测收集周边坏境信息并传送到远处的基站进行处理。传感器节 点由电池提供能量，通常通过飞机布撒，人工布置等方式，大量部署在感知对象 内部或者附近。由于传感器节点的电池能量有限，因此节点的通信应有效的利用 能量，以延长网络的生命周期。l e a c h 协议是一种典型的能有效延长网络生命周 期的节能通信协议。在u z a c h 协议的基础上，本文提出了种新的适用于无线传 感器网络的低功耗聚类路由算法。该算法假设节点的地理位置已知，其特点是以 聚类的方式组织节点，聚类区域由基站划分并固定，聚类首领根据节点的能量值 动态选择并组织成路由树，由根节点与基站直接通信。最后，本文利用n s 2 仿真工 具对该算法进行了模拟仿真。实验结果显示，该算法的性能要优于l e a c h 。 关键词：无线传感器网络l e a c h网络生命周期聚类能量效率 a b s t r a c t w i r c l e s ss e n s o rn e t w o r kc o n s i s t i n go fal a r g en u i i l b c ro f 锄a l ls c n s o r sw i t h 1 0 w p o w e rt r a n s c e i v e rc a nb ea ne f 传c t i v et o o lf o rg a t l l e r i n gd a t ai nav 撕c t yo f e n v i r o n m c n t t h ec o l l e c t e dd a t am u s tb et r a n s m i t t e dt ot h eb a s es t a t i o nf o rf u r t h e r p m c e s s i n 舀a1 a r g en u m b e ro fs e n s o r s ，w h o s ee n e 唱ya r eo f f b r e db yb a t t e r y ，a r e d e p l o y e dt os e n s em ee n v i m m e n t s s i n c ean e t w o r kc o n s i s t so fs e n s o r sw i t hl i m i t e d b a t t e r ye n e r g y ，t h em e t l l o df o rd a t ag a t l l e r i n ga i l dm u t i n gm u s tb ee n e r g ye 瓶c i e n ti n o r d e rt op r o l o n gt h e1 i f e t i m eo ft h en c t w o r k l e a c hi sa ne l e g a n te n e r g ye f b c i e n t p m t o c 0 1t om a 】【i m i z et h el i f e t i m eo fs e n s o rn e t 、v o r k s t a r t i n gf 而mt h eb a s i ci d e ao f l e a c h ，m i sp a p e ri n t m d u c e da1 0 we n e r g yc l u s t e r _ b a s e dm u t i n ga l g o r i t h m ，w h i c hc a n b eu s e di nw i r e l e s ss e n s o rn e t w o r k t h i sa l g o r i l h mr e q u i r e sl o c a t i o ni n f o h n a t i o no f a l l n o d e s o f t h en e t w o r k i tc l u s t e r sn o d e si n t og r o u p t h ea r e a so f c l u s t e r i n ga r e d e t e m l i n e da n df i x e db yt h eb a s es t a t i o n t h ea l g o r i t h mi d t a t e sc l u s t e rh e a d s b a s e do n t h ee n c r g yo f n o d e s ，a n db u i l d sr o u t i n gt r e ea m o n gc l u s t c rh e a d s ，a m o n gw h i c ho n l yt h e m o tn o d ec o m m u n j c a t e st h eb a s es t a t i o nd i r e c t l y f i n a l l y ，m i sp a p e rs i m u l a t e dt h en e w a l g o r i 血mu s i n gn s 2 s i m u l a t i o nr e s u l t ss h o wm a tt h ea l g o r i s mp e r f o 矾sb e t t e rt h a l l i ，e a c h k e y w o r d s ： w i r e l e s ss e n s o rn e t w o r kl e a c hn e t w o r ki i f b t i m e c l u s t e r i g e n e r g y - e m c i e n t 创新性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研究 成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不 包含其他人已经发表或撰写过的研究成果；也不包含为获得西安电子科技大学或 其它教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做 的任何贡献均已在论文中做了明确的说明并表示了谢意。 申请学位沦文与资料若有不实之处，本人承担一切相关责任。 本人签名 靴搭。 日期甚趔：芝：型 关于论文使用授权的说明 本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：研究 生在校攻读学位期间论文工作的知识产权单位属西安电子科技大学。本人保证毕 业离校后，发表论文或使用论文工作成果时署名单位仍然为西安强子科技大学。 学校有权保留送交论文的复印件，允许查阅和借阅论文；学校可以公布论文的全 部或部分内容，可以允许采用影印、缩印或其它复制手段保存论文。( 保密的论文 在解密后遵守此规定) 本学位论文属于保密在一年解密后适用本授权书。 本人签名：嵩牲本人签名：肆竭熬 刷醴名。扩 日期丝：兰型 日期奢脚王：垮 第一章绪论 第一章绪论 1 1 引言 随着半导体技术和通信技术的发展，我们已经由p c 时代和网络时代，进入后 p c 时代。自m a r kw e i s e r 在1 9 9 1 年首次提出普适计算i l 】( u b i q u i t o u sc o m p u t i n g ) 思 想以来，普适计算作为2 l 世纪的计算模式，曰益受到人们的关注和重视。其中， 无线传感器网络技术是普适计算思想大系统中的个典型应用【孙。 无线传感器网络是当前国际上备受关注的、由多学科高度交叉的新兴前沿研 究热点领域。无线传感器网络能够通过各类集成化的微型传感器协作地实时监测、 感知和采集各种环境或监测对象的信息，通过嵌入式系统对信息进行处理，并通 过随机自组织无线通信网络以多跳中继方式将所感知信息传送到用户终端，从而 真正实现普适计算的理念【2 1 。无线传感器网络具有十分广阔的应用前景，在军事国 防、工农业、城市管理、生物医疗、环境监测、抢险救灾、防恐反恐、危险区域 远程控制等许多领域都有重要的科研价值和巨大实用价值，已经引起了世界许多 国家军界、学术界和工业界的高度重视，并成为进入2 0 0 0 年以来公认的新兴前沿 热点研究领域，被认为是将对二十一世纪产生巨大影响力的技术之【3 】。 在传感器网络中，传感器节点由电沲提供能量，通过飞机布撒，人工布置等 方式，大量部署在感知对象内部或者附近。这些节点通过自组织方式构成无线网 络，以协作的方式感知、采集和处理网络覆盖区域中特定的信息，可以实现对任 意地点信息在任意时间的采集。处理和分析。在很多情况下，传感器节点被配置 在野外的环境中，或者在偏僻的、难以接近的区域中，这样传感器网络必须在无 任何基础设施的环境中进行长期的自主的工作。同时，传感器节点的能量资源、 计算能力和带宽又都非常有限。这些决定了无线传感器网络协议栈各层的设计都 必须以能源有效性为首要的设计要素。 因此，无线传感器网络路由协议设计与传统的无线a dh o c 网络有很多不同， 无线传感器网络路由设计的重要目标是降低节点能源损耗，提高网络生命周期； 雨传统的无线a dh o c 网络的路由协议设计的首要任务是移动条件下高服务质量的 提供。这些不同导致了传统的无线a d h o c 网络路由协议不能直接用于无线传感器 网络中，许多颓的适用于无线传感器网络的路由协议得到提出，它的研究已经成 为无线传感器网络研究中的热点。这方面的技术也正是本文的研究重点。 一种基于l e a c h 的无线传感器网络路由算法 1 2 课题背景 1 2 1 无线传感器网络的研究现状 无线传感器网络的研究起始于2 0 世纪9 0 年代末期。由于无线传感器网络的巨 大应用价值，它已经引起了世界许多国家的军事部门、工业界和学术界的极大关 注。自2 0 0 0 年起，国际上开始出现一些有关传感器网络研究结果的报道，美国自 然科学基金委员会2 0 0 3 年制定了传感器网络研究计划，支持相关基础理论的研究。 美国国防部和各军事部门都对传感器网络给予了高度重视，把传感器网络作为一 个重要研究领域，设立了一系列的军事传感器网络研究项目。美国英特尔公司、 微软公司等信息业巨头也开始了传感器网络方面的研究工作。同本、德国、英国、 意大利等科技发达国家也对无线传感器网络表现出了极大兴趣，纷纷展开了该领 域的研究。但是，目前大部分的研究尚处于起步阶段，少数投入实用的商业产品 距离实际需求还相差甚远。 我国在传感器网络方面的研究工作还很少”1 ，目前，国内一些高等院校与研究 机构已积极开展无线传感器网络的相关研究工作，主要有清华、中科院软件所、 浙江大学、哈尔滨工业大学、中科院自动化所、中国人民大学等。目前国内研究 热点主要集中在穿戴式计算、上下文感知环境、智能教室等领域，在支持无线传 感器网络的无线通信网络技术的研究尚不多见。随着无线传感嚣网络应用的日益 发展与不断深入，支持无线传感器网络的无线通信网络技术、超微型嵌入式实时 操作系统等若干关键技术的研究将成为未来无线传感器网络应用的发展趋势和热 点。 1 2 2 无线传感器网络研究的热点问题和关键技术 无线传感器网络以应用为目标，其构建是一个庞大的系统工程，涉及到的研 究工作和需要解决的问题在每一个层面上都很多。对无线传感器网络系统结构及 界面接口技术的研究意义重大。如果我们把无线传感器网络按其功能抽象成五个 层次的话，将会包括基础层( 传感器集合) 、网络层( 通信网络) 、中间件层、 数据处理和管理层以及应用开发层i 2 j 。 其中，基础层以研究新型传感器和传感系统为核心，包括应用新的传感原理、 使用新的材料以及采用新的结构设计等，以降低能耗、提高敏感性、选择性、响 应速度、动态范围、准确度、稳定性以及在恶劣环境条件下工作的能力a 还包括 多通道传感器以及无线通信芯片的系统集成，以及嵌入式处理器的集成化。此外， 第一章绪论 还包括通过对嵌入式操作系统的研究。实现利用有效资源对整体系统进行高效率 的事件处理、能源管理、命令处理和工作描述。另外，超低能耗的传感器节点的 设计、各功能部件的接口及系统集成方法、与信号处理中心之间实现高速的通信 以保证决策人做出迅速及时的反应也是研究的重点内容。目前这代节点产品大 都采用各类通用芯片( 如普通八位微处理器，如a t m e g a l 2 8 l ，以及通用无线通信 模块c c l 0 0 0 等) 和元器件进行集成开发。而某些面向2 0 1 0 年的下一代节点将完 全采用s o c 方法，以真正实现微型化并大大降低节点成本。这方面代表性的项目 有非常有名的s m a ld u s 一。 网络层以通信网络为核心，实现传感器与传感器、传感器与用户之间的通信， 对传感器节点进行有效的控制和管理，支持多传感器协作完成大型感知任务。需 要展开的研究工作包括低能耗、高速率、长生命周期的无线传感器网络的随机自 组织通信协议、通信方式及自重构、自调整性；无线传感器网络的可扩展性、容 错性、可维护性及安全性、隐私性；无线传感器网络的特性( 有别于已有的互联 网和a dh o c 无线网络) ；适用于无线传感器网络的网络通信模式、支持无线传感 器网络通信的各种协议、时间同步、任务分配与协调控制以及相应的软硬件资源 等方面。 中间件层研究具有通用性能的标准中间层软件结构，负责无线传感器网络系 统的资源管理、动态环境分析，以及普适应用的开发支持，如应用功能改换、功 能扩展、系统升级、重复再利用等关键性能的实现。 数据处理和管理层以传感器数据管理与处理软件为核心，包括以数据为中心 的实时分布式数据流管理、查询及相关信息处理技术；支持感知数据的采集、存 储、查询、分析等各种数据管理和分析处理软件系统，新型统计算法、排除误差 信息的方法、对大型分布式传感器阵列的协同处理、图象识别方法等。 应用开发层由各种传感器网络应用软件组成。 显然，围绕实现网络整体低功耗运行，在基础层上针对传感器节点开展研究 工作是整体无线传感器网络研究的起点和基础。以上提到的网络节点中涉及到的 各项技术无疑是最为关键的一部分技术。此外，针对适合无线传感器网络特点、 支持无线传感器网络工作的网络协议这一关键技术的研究也是极为重要和追切 的，将会直接影响整体工作水平和实用化的进程。 1 2 3 关于无线传感器网络路由协议的研究 无线传感器网络与传统的无线网络相比有自己的特点。后者在高度移动的环 境中通过优化路由和资源管理策略最大化带宽的利用率，同时为用户提供一定的 服务质量保证。而在传感器网络中，除了少数节点需要移动以外，大部分节点都 4 一种基于l e a c h 的无线传感器网络路由算法 是静止的。在无线传感器网络的研究初期，人们一度认为，成熟的h l t e m e t 技术加 上a d h o c 路由机制对传感器网络的设计是足够充分的，但是深入的研究表明【6 】：传 感器网络有着与传统网络明显不同的技术要求。因此一些为自组织的a dh o c 网络 设计的协议和算法未必适合传感器网络的特点和应用的要求。例如，传感器网络 中的节点数量和分布密度远远超过以往a dh o c 网络中的节点数，大部分节点不像 a dh o c 节点一样快速移动，传感器节点出现故障的可能性要大于a dh o c 网络。出 于数目极大，传感器节点不一定具有全球唯一的标识等等。这些独特的要求和制 约因素为传感器网络的研究提出了新的技术问题。许多新的适用于无线传感器网 络的路由协议得到提出，它的研究已经成为无线传感器网络研究中的热点。 1 3 研究工作及论文的主要内容 论文课题来自于苏州中科集成电路设计中心的研发项目。该项目是中科院计 算所无线传感器网络项目的一个部分，其目标是构建无线传感器网络的硬件平台。 本文作者负责研发适用于无线传感器网络的路由算法。 本文在充分研究和分析已有的研究成果的基础上，提出了一种新的适用于无 线传感器网络的低功耗路由算法基于l e a c h 的固定聚类路由算法。该算法在 l e a c h 的基础上，对l e a c h 进行了改进，改进的主要目标是降低系统的能量消耗， 延长网络的生命周期，同时扩展l e a c h 的适用范围。最后，本文利用n s 2 仿真工 具对算法进行仿真实验，以评价算法的性能。 论文的第二章对无线传感器网络进行了概述，介绍了无线传感器网络的概念、 体系结构及特点。重点研究了无线传感器网络的路由协议，对现有的路由协议进 行了分类，并介绍了其中几种典型的路由协议。 第三章首先描述了在无线传感器网络中基于聚类的通信协议应该满足的几个 目标，在分析了l e a c h 的不足之后，着重阐述了基于l e a c h 的固定聚类路由算法 的设计思想。 第四章首先介绍了基于l e a c h 的固定聚类路由算法的网络模型、物理基础及 算法所做的假定条件，然后重点描述了基于l e a c h 的固定聚类路由算法的实现细 节。最后，本章给出了一种计算最优聚类首领数的方法，并利用数学方法得到了 基于l e a c h 的固定聚类路由算法的最优聚类首领数。 第五章首先介绍了n s 2 仿真工具，然后利用n s 2 对几种不同的路由算法进行了 模拟仿真。最后，对仿真实验的结果进行分析，来评价算法的性能。 第二章无线传感器网络概述 第二章无线传感器网络概述 2 1 无线传感器网络的概念 我们可以如下定义无线传感器网络：无线传感器网络是由一组传感器以a d h o c 方式构成的无线网络，其目的是协作地感知、采集和处理网络覆盖的地理区域 中感知对象的信息，并发布给观察者【7 】。 从上述定义可以看到，传感器、感知对象和观察者是传感器网络的3 个基本要 素；无线网络是传感器之间、传感器与观察者之间的通信方式，用于在传感器与 观察者之间建立通信路径；协作地感知、采集、处理、发布感知信息是传感器网 络的基本功能。一组功能有限的传感器协作地完成大的感知任务是传感器网络的 重要特点。传感嚣网络中的部分或全部节点可以移动。传感器网络的拓扑结构也 会随着节点的移动而不断地动态变化。节点间以a dh o c 方式进行通信，每个节点 都可以充当路由器的角色，并且每个节点都具备动态搜索、定位和恢复连接的能 力。下面，我们详细地来讨论传感器、感知对象和观察者。 传感器由电源、感知部件、嵌入式处理器、存储器、无线通信部件和软件这 几部分构成，如图2 2 所示i 引。电源为传感器提供正常工作所必需的能源。感知部 件用于感知、获取外界的信息，并将其转换为数字信号。处理部件负责协调节点 各部分的工作，如对感知部件获取的信息进行必要的处理、保存，控制感知部件 和电源的工作模式等。无线通信部件负责与其他传感器或观察者的通信。软件则 为传感器提供必要的软件支持，如嵌入式操作系统、嵌入式数据库系统等。观察 者是传感器网络的用户，是感知信息的接受和应用者。观察者可以是人，也可以 是计算机或其他设备。例如，军队指挥官可以是传感器网络的观察者：一个由飞 机携带的移动计算机也可以是传感器网络的观察者。一个传感器网络可以有多个 观察者。一个观察者也可以是多个传感器网络的用户。观察者可以主动地查询或 收集传感器网络的感知信息也可以被动地接收传感器网络发布的信息。观察者 将对感知信息进行观察、分析、挖掘、制定决策，或对感知对象采取相应的行动。 感知对象是观察者感兴趣的监测目标，也是传感器网络的感知对象，如坦克、军 队、动物、有害气体等。感知对象一般通过表示物理现象、化学现象或其他现象 的数字量来表征，如温度、湿度等。一个传感器网络可以感知网络分布区域内的 多个对象。一个对象也可以被多个传感器网络所感知。 6一种基于l e a c h 的无线传感器网络路由算法 2 2 无线传感器网络的体系结构 2 2 1 网络体系结构 在传感器网络中，节点通过飞机布撒，人工布置等方式【3 j ，大量部署在感知对 象内部或者附近。这些节点通过自组织方式构成无线网络，以协作的方式感知、 采集和处理网络覆盖区域中特定的信息，可以实现对任意地点信息在任意时间的 采集，处理和分析。这种以自组织形式构成的网络，通过多跳中继方式将数据传 回s i n k 节点( 接收发送器) ，最后借助s i l l l 【链路将整个区域内的数据传送到远程控 制中心进行集中处理。一个典型的传感器网络的体系结构包括分布式传感器节点 ( 群) 、s i n k 节点、互联网和用户界面等【8 】，如图2 1 所示。在传感器网络中绝大多 数的节点只有很小的发射范围，而s i n k 节点的发射能力较强，具有较高的电能，可 以把数据发回远程控制节点。 2 2 2 传感器节点组成 图2 1 传感器网络的体系结构 一个典型的传感器网络的体系构建包括分布式传感器节点( 群) 、接收发送 器、互联网和用户界面等。其中，传感器网络节点的基本组成和功能包括如下几 个单元8 】：传感单元( 由传感嚣和模数转换功能模块组成) 、处理单元( 由嵌入式 系统构成，包括c p u 、存储器、嵌入式操作系统等) 、通信单元( 由无线通信模 块组成) 、以及电源部分，如图2 2 所示。此外，可以选择的其它功能单元包括： 定位系统、移动系统以及电源自供电系统等。 第二章无线传感器网络概述 2 2 3s i n k 节点组成 图2 2 传感器节点组成 s i n k 节点的硬件部分主要由中央处理单元、存储单元、射频收发模块和g p r s 通信模块组成【s 】，如图2 3 所示。s j n k 节点的中央处理单元主要用来处理从传感器节 点采集到的数据以及完成一些控制功能。为了将采集到的数据传输给使用者，s i n l ( 节点还配有g p r s 通信单元，用户可以通过普通p c 和g p r s 手机终端来观测传感器 采集到的数据。s i n k 节点同时还配有与传感器节点相同的射频收发模块，用于接收 传感器节点发送的数据。 图2 3 无线传感器网络s i n k 节点结构 一种基于l e a c h 的无线传感器网络路由算法 2 3 无线传感器网络的特点 无线传感器网络除了具有a dh o c 网络的移动性、自组织性等共同特征以外， 还具有很多其他鲜明的特点。这些特点向我们提出了一系列挑战性问题”l ： ( 1 ) 电源能量有限 传感器的电源能量极其有限。网络中的传感器节点由于电源能量的原因经常 失效或废弃。电源能量的局限是阻碍传感器网络应用的严重问题。商品化的无线 发送接收器电源远远不能满足传感器网络的需要。传感器传输信息要比执行运算 消耗更多的电能，传感器传输1 位倍息所需要的电能足以执行3 0 0 0 条运算指令【4 。 如何在网络工作过程中节省能源，最大化网络的生命周期，是无线传感器网络重 要的研究课题之一。 ( 2 ) 通信能力有限 传感器的通信带宽窄而且经常变化，通信覆盖范围只有几十到几百米。传感 器之间的通信断接频繁，经常导致通信失败。由于传感器网络更多地受到高山、 建筑物、障碍物等地势地貌以及风雨雷电等自然环境的影响，传感器可能会长时 间脱离网络，离线工作。如何在有限通信能力的条件下高质量地完成感知信息的 处理与传输，是研究无线传感器网络必须要解决的问题。 ( 3 ) 计算能力有限 传感器网络中的传感器都具有嵌入式处理器和存储器。这些传感器都具有计 算能力，可以完成一些信息处理工作。但是，由于嵌入式处理器和存储器的能力 和容量有限，传感器的计算能力十分有限。 ( 4 ) 传感器数量大、分布范围广 传感器网络中，传感器节点密集，数量巨大，可能达到几百万、几千万，甚 至更多。此外，传感器网络可以分布在很广泛的地理区域。传感器数量大、分布 广的特点使得网络的维护十分困难甚至不可维护，传感器网络的软、硬件必须具 有高强壮性和容错性。 ( 5 ) 网络动态性强 传感器网络具有很强的动态性。网络中的传感器、感知对象和观察者这三要 素都可能具有移动性，并且经常育新节点加入或已有节点失效。因此，网络的拓 扑结构动态变化，传感器、感知对象和观察者三者之间的路径也随之变化。传感 器网络必须具有可重构性和自调整性。 ( 6 ) 感知数据流巨大 传感器网络中的每个传感器通常都产生较大的流式数据，并具有实时性。每 个传感器仅仅具有有限的计算资源，难以处理巨大的实时数据流。我们需要研究 第二章无线传感器网络概述 强有力的分布式数据流管理、查询、分析和挖掘方法。 ( 7 ) 大规模分布式触发器 很多传感器网络需要对感知对象进行控制，如温度控制。这样，很多传感器 具有回控装置和控制软件。我们称回控装置和控制软件为触发器。成千上万的动 态触发器的管理是我们面临的又一个挑战。 2 4 无线传感器网络路由协议研究 无线传感器网络路由协议的设计极负挑战性，它与传统的无线a dh o c 网络有 着许多不同的特色【9 】： ( 1 ) 无全局标识：传感节点数量庞大，维护全局标识需要大量的开销，因此 不同于传统的基于口的路由协议，在传感器网络中一般不采用全局标识； ( 2 ) 多对一通信：不同于传统网络的点对点通信，在传感器网络中几乎所有 的应用都要求多个源传感器节点将传感到的数据流传送至特定的s i n k ； ( 3 ) 数据冗余大：多个源传感器节点在许多场景下都有可能获得大量相似的 数据，因此传感器网络的冗余数据大； ( 4 ) 资源局限强：传感器节点的资源限制很大，发送功耗。板上能源，处理 能力和存储量都局限在很低的范围肉。 针对无线传感器网络中数据传送的特点和难题，许多新的路由协议得到了提 出。这些路由协议可以大致分为四类【9 】：洪泛式路由协议，以数据为中心的路由协 议，层次式路由协议，以及基于位置信息的路由协议。下面我们将简要介绍现有 的无线传感器网络路由协议，对每种类别中的典型协议进行分析和比较。 2 4 1 洪泛式路由协议 这种协议是一种古老的协议。它不需要维护网络的拓扑结构和路由计算，接 收到消息的节点以广播形式转发数据包给所有的邻节点。对于自组织的传感器网 络，洪泛式路由是一种较直接的实现方法，但容易带来消息的“内爆”( i m p l o s i o n ) 和“重叠”( o v e r l 印) ，而且它没有考虑能源方面的限制，具有“资源盲点” ( r e s o u r c eb i i n d n e s s ) 的缺点 10 1 。 2 4 2 以数据为中心的路由协议 这类协议与传统的基于地址的路由协议有很大的不同，它不再依赖特定的节 。一种基于l e a c h 的无线传感器网络路由算法 点，而是依赖于网络中的数据。它的基本思想是对传感器网络中的数据用特定的 描述方式命名，数据传送基于数据查询并依赖数据命名。s i i l l ( 节点向特定区域发出 查询，并等待该区域节点发回符合查询条件的数据，从而将所有的数据通信都限 制在局部范围内，极大地减少了网络中大量传送的重复冗余数据，降低了能量损 耗。 下面介绍定向扩散( d i r e c t e dd i f f u s i o n ) 。 d i r e c t e d d i f r u s i o n 】是以数据为中心的路由协议发展过程的里程碑。其他的以 数据为中心的路由协议都是基于定向扩散改进或者采用类似的关键思想来提出 的。 定向扩散模型是e s t r i n 等人专门为传感器网络设计的路由策略，与已有的路由 算法有着截然不同的实现机制。节点用一组属性值来命名它所生成的数据，比如 将温度传感器生成的数据命名为t y p e 爿e m p e r a i u r e ，j d - 1 2 ， t i m e s t a m d = 0 2 0 1 2 2 2 1 ：1 0 ：2 3 ，l o c a t i o n 一3 0 5 。s i n k 节点发出的查询业务也用属性的 组合表示，逐级扩散，最终遍历全网，找到所有匹配的原始数据。有一个称为“梯 度”的变量与整个业务请求的扩散过程褶联系，反欧了网络中间节点对匹配请求 条件的数据源的近似判断。更直接的方法是节点用一组标量值表示它的选择，值 越大意味着向该方向继续搜索获得匹配数据的可能性越大。这样的处理最终将会 在整个网络中为s i n k 节点的请求建立一个临时的“梯度”场。匹配数据可以沿“梯 度”最大的方向中继回s i n k 节点。 2 4 3 层次式路由协议 这类协议的基本思想是将传感器节点组织成聚类。每个聚类有个聚类首领。 聚类首领完成数据聚集和合成，并负责将数据传送给终端节点。数据从较低层次 的聚类逐层发送到高层次的聚类，直至终端节点。这种方式极大地减少了与终端 节点的通信量，从而有效地维持传感节点的能量消耗，延长网络生命周期。另外， 它还能很好地满足传感器网络的可扩展性，并减少网络延迟。 下面介绍低功耗自适应聚类路由协议( l e a c h ) 。 l e a c h l l 2 ，13 】是第一个在无线传感器网络中提出的层次式路由协议。其后的大 部分层次式路由协议都是在它的基础上发展而来的。 l e a c h 算法主要通过随机选择聚类首领，平均分担中继通信业务来实现a l e a c h 定义了“轮”( r o l h l d ) 的概念，每一轮由初始化和稳定工作两个阶段组成。 在初始化阶段，随机选择节点为聚类首领，成为聚类首领的节点向周围广播信息， 其他节点根据接受到广播信息的强度来选择它所要加入的聚类，并告知相应的聚 类首领。在稳定工作阶段，节点持续采集监测数据，传送到聚类首领，由聚类首 第二章无线传感器网络概述 领对数据进行必宴的融合处理之后，发送到终端节点。下一轮工作周期重新选择 聚类首领。 聚类首领的建立过程是：节点从0 到l 的随机数中任意选择一个数值若当 前轮中这个数值小于设定的阀值丁n ) ( 如下) ，则该节点成为聚类首领。 m ) ； 洳：兰 酢- 1 ) 、 ioo l h c l w i 靶 + k 一 其中p 为期望的聚类首领在所有传感节点中的百分比( 由系统预先指定) ： 是当前轮数：g 是在最后的1 j p 轮中未成为聚类首领的节点集。 下面介绍p e g a s i s ( p o w e re m c i e mg a t h e r i n gi ns e n s o ri n f o 珊a t i o ns y s t e m s ) 。 p e g a s i s 【1 4 】由u 、a c h 发展而来。p e g a s i s 的基本思想是节点发送能量递减的 测试信号，通过检测应答来确定离自己最近的相邻节点，然后以贪食蛇算法的方 式将所有节点组成一条链路，以便所有节点都仅与自己的相邻节点通信。数据从 一个节点发送到链路中相邻的另一个节点，并在每个节点完成数据聚集，最后数 据传送到达该链条一个指定的节点即首领节点。该首领节点在接收到两端的数据 后，将接收到的数据与自己的数据融合，将融合后的数据发送到终端节点。每个 节点轮流被指定为首领节点。每一轮仅有一个首领节点，即只有一个节点与终端 节点通信。 2 4 4 基于位置信息的路由协议 这类协议利用节点的位置信息，把查询或者数据转发给需要的地域，从而缩 减数据的传送范围。实际上许多传感器网络的路由协议都假设节点的位置信息为 已知，所以可以方便的利用节点的位置信息将节点分为不同的域( r e g i o n ) 。基于 域进行数据传送能缩减传送范围缓和中间节点，从而延长网络生命周期。 下面介绍g e a r ( g e o g r a p h i c a la n de n e r g y ，a w a r er o u t i n 曲。 g e a r 【1 5 】是充分考虑了能源有效性的基于位置的路由协议，它比其他的基于位 置的路由协议能更好的应用于无线传感器网络之中。 g e a r 算法提出既然传感器网络中的数据经常包含了位置属性信息，那么可以 利用这一信息，把在整个网络中扩散的信息传送到适当的位臀区域中。同样g e a r 也采用了查询驱动数据传送模式。它传送数据分组到目标域中所有的节点的过程 包括两个阶段：目标域数据传送和域内数据传送。 在目标域数据传送阶段，当节点接收到数据分组，它将邻接点同目标域的距 离和它自己与目标域的距离相比较，若存在更小距离，则选择最小距离的邻接点 作为下一跳节点；若不存在更小距离，则认为存在“h o l e ”，节点将根据邻居的最 2 一种基于l e a c h 的无线传感器网络路由算法 小花销来选择下一跳节点。 在域内数据传送阶段，可通过两种方式让数据在域内扩散：在域内宜接洪泛 和递归的目标域数据传送直到目标域剩下唯一的节点( 见图2 4 ) 。 o ooo 冒 o ；o o 呻 、q ! o i o 、b 一 图2 4 g e a r 中递归的目标域数据传送 第三章基于l e a c h 的固定聚类路由算法的设计思想 第三章基于l e a c h 的固定聚类路由算法的设计思想 3 1 引言 在无线传感器网络中，节点的能量资源、计算能力和带宽等资源都非常有限， 尤其是其有限的能量直接影响传感器网络的生命周期以及网络的信息质量。因此， 设计有效的策略，降低节点能源损耗，提高网络生命周期成为无线传感器网络的 核心问题。 无线传感器网络路由协议设计以能源有效性为首要的设计要素，它的主要设 计目标是能量有效性路径的建立，可靠数据转发机制的形成以及最长网络生命周 期的实现。 本文在l e a c h 算法的基础上，从节省能量、延长网络生命周期的角度对 l e a c h 算法进行了改进，提出了一种基于地理信息的、固定聚类区域的无线传感 器网络路由算法基于l e a c h 的固定聚类路由算法。该算法假设节点的地理位 置己知，其特点是以聚类的方式组织节点，聚类区域由b s 在网络初始阶段划分， 并在整个网络生命周期内固定不变。每个节点隶属于某个特定的聚类区域，聚类 区域内的聚类首领根据聚类内节点的当前能量值动态选择。所有的聚类首领根据 其能量值组织成路由树，由各棵路由树的根节点负责收集其它聚类首领的数据并 向b s 传送。仿真实验显示，基于l e a c h 的固定聚类路由算法具有良好的性能。 3 2 问题描述 本节将着重阐述基于聚类的通信协议应该满足的几个目标，并同时分析 l e a c h 存在的一些问题。针对这些目标和问题，本文对l e a c h 进行了改进，提出 了一种新的适用于无线传感器网络的低功耗聚类路由算法基于l e a c h 的固定 聚类路由算法。本文将在下一节详细阐述基于l e a c h 的固定聚类路由算法的设计 思想。 设计有效利用能量的路由协议的原则是使每轮数据收集的总能耗最小，同时 保证能量的损耗均匀分布在所有节点上。基于聚类的路由协议能有效利用能量， 延长网络的生命周期。在传感器网络中基于聚类的通信协议应该满足以下几个目 标： 4 一种基于l e a c h 的无线传感器网络路由算法 目标1 ：聚类的划分应该以各聚类的能耗最小为目的，聚类首领应较为均匀地 分布在网络中。 l e a c h 算法采用自组织、局部化的方法来划分聚类，聚类的形成完全是随机 的，不需要b s 的任何控制信息，节点之间也不需要进行额外的协商。由于聚类是 随机形成的，无法保证在每一轮中都能得到最优化的聚类划分方案。随机选取的 聚类首领可能相距很近，如图3 1 所示，t d 为聚类首领，b 、c 两节点相距很近， 它们接收成员的数据时，可能会由于电磁波的互相干扰导致数据的重发，引起不 必要的能量损耗。同时，这些随机选取的聚类首领，可能在网络或聚类的边缘， 如图3 1 所示1 1 ”。由于a 、c 在网络或聚类的边缘，成员与a 、c 的距离将较远， 从而势必增加通信能量的消耗。在网络覆盖区域很大的情况下，成员与聚类首领 间的通信能量急剧上升，能量损耗将相当可观。为此，需要寻找一种机制，使聚 类首领可以较均匀地分布在网络中，从而避免图3 1 出现的问题。 图3 1l e a c h 聚类示意 目标2 ：网络中节点之间的通信，包括聚类成员与首领的通信、聚类首领之间 的通信，应该避免远距离传输的高能量消耗，因此节点间的通信应该尽量在一定 的范围内进行。 在l e a c h 算法的初始化阶段，聚类首领选定后，成为聚类首领的节点将在整 个网络范围内向所有节点广播此消息。在网络覆盖区域很大的情况下，聚类首领 需要将广播消息发送到相当远的区域，这个过程将消耗聚类首领相当多的能量。 同时，所有其他节点接收此消息也将消耗一定的能量，而事实上对于多数未成为 聚类首领的节点而言，接收此消息的能量消耗是不必要的。为此，聚类首领可以 只向一定范围内的节点广播消息。这样，聚类首领只需要将广播消息发送到邻近 的区域，同时，接收此消息的节点也将被局限在这个范围内，避免了不必要的能 第三章基于l e a c h 的固定聚类路由算法的设计思想 量消耗。 目标3 ：应该尽量减小网络初始化阶段的头开销。 在l e a c h 算法的初始化阶段，所有节点都要进行判断，以决定是否成为聚类 首领。聚类首领选定后，节点要以自组织的方式形成聚类，这牵涉到系列的广 播和设置工作。在节点数目比较大、节点密集的情况下，由于所有节点都要参与， 从总体上看，整个系统发送的广播数量不容忽视。同时，第( 2 ) 点中描述的能量 耗损也是l e a c h 算法初始化阶段的头开销。可见，u ! a c h 算法的这种每轮固定聚 类首领之后再建立聚类的方法，头开销较大。 目标4 ：由于b s 与传感区域相距较远，节点与b s 的通信将是高能耗的。因此， 应该尽量减少网络中与b s 的通信量。这包括减少网络中与b s 直接通信的节点数目 和减少网络中传送给b s 的数据量。 l e a c h 算法以聚类的方式组织节点，由聚类首领负责与b s 直接通信，其他节 点只与聚类首领通信，从而在定程度上减少了网络中与b s 通信的节点数目。但 是，与p e g a s i s 相比( p e g a s i s 每轮仅由一个节点负贲将数据传送给b s ) ，由于 l e a c h 采用单跳通信的方式，聚类首领直接与b s 通信，与b s 通信的节点数目仍然 较多，从而加大了能量消耗。为此，需要进一步减少直接与b s 通信的节点数目。 在l e a c h 算法中，聚类首领收集完聚类内所有节点的数据后，将对数据进行 融合处理，从而减少了传送给b s 的数据量。但是，与p e g a s i s 相比( p e g a s i s 每 个节点都要进行一定的数据融合处理) ，l e a c h 所做的数据融合处理相对较少， 减少的数据量有限。 目标5 ：为了最大限度地延长网络生命周期，应该保证整个系统的能量损耗均 匀地分布在所有节点上。 在基于聚类的路由算法中，聚类首领消耗的能量要比非聚类首领节点所消耗 的要多的多。如果这些聚类首领在整个系统的生命周期内是事先确定和固定不变 的，那么它们将很快地用完它们有限的能量。一旦聚类首领用完了能量，那它将 不再工作，这样，所有属于这个聚类的非聚类首领节点也将失去和b s 通信的能力， 从而使这些节点失效( 尽管这些节点还有一定的剩余能量) 。为了避免太快地消 耗完某个节点的能量，l e a c h 算法采用随机轮换聚类首领的方法，将聚类首领的 能量消耗平均分担给所有节点。为此，可以采用与l e a c h 算法类似的方法，或者 对l e a c h 算法进行改进以得到更优化的方案，来实现系统内各节点的负载平衡。 目标6 ：个好的路由算法，应该具有较广的适用范围。 在l e a c h 算法中，聚类首领的选择采用式( 2 1 ) 中定义的阀值。这个阀值的计 算是基于以下两个假设的：网络中所有节点的初始能量一致，且每一轮每一个聚 类首领消耗的能量也是大体一致的。但是，在实际应用中，节点的初始能量很可 能不一致，同时在多数情况下，聚类首领消耗的能量并不一致。在这种情况下， 一种基于l e a c h 的无线传感器网络路由算法 式( 2 1 ) 不再适用。为此，需要对l e a c h 算法的聚类首领选择机制进行改进，以扩 展它的适用范围。 3 3 基于l e a c h 的固定聚类路由算法的基本思想 针对前面描述的一系列问题，本文提出了一种基于地理信息的、固定聚类区 域的低功耗聚类路由算法基于l e a c h 的固定聚类路由算法( 以下简称固定聚 类路由算法) 。该算法在l e a c h 算法的基础上，对l e a c h 进行了改进，改进的主 要目标是降低系统的能量消耗，延长网络的生命周期，同时扩展l e a c h 的适用范 围。 固定聚类路由算法也是以聚类的方式来组织节点，它的基本思想如下： ( 1 ) 通过划分并固定聚类区域，形成优化的聚类结构，同时减少初始化阶段 的头开销，并将节点间的通信局限在局部范围内。( 针对3 2 节中的目标1 ，2 ，3 ) ( 2 ) 通过动态选择聚类首领，使聚类内各节点平均分担通信业务，避免了单 一节点的快速失效。聚类首领的选择基于节点的当前能量值，扩展了l e a c h 的适 用范围。( 针对目标5 ，6 ) ( 3 ) 通过建立路由树，形成层次化聚类结构，从整体上实现各聚类区域的负 载平衡，同时减少网络中与b s 直接通信的节点数目。( 针对目标2 ，4 ，5 ) ( 4 ) 聚类内节点采用单跳的方式与聚类首领通信，降低了系统的能量消耗， 同时减少了传输延迟。 ( 5 ) 通过选择最优的聚类首领数q ，使整个系统的能量消耗尽可能地降到最 低，同时延长网络的生命周期。 3 3 1 划分并固定聚类区域 l e a c h 算法采用自组织、局部化的方法来划分聚类，聚类的形成完全是随机 的，不需要b s 的参与。同时，聚类结构不是固定不变的，每一轮都要重新组织聚 类。由于聚类是随机形成的，无法保证在每一轮中都能得到最优化的聚类划分方 案。同时，每一轮都要重新组织聚类，头开销较大。 与l e a c h 算法不同，在本文设计的固定聚类路由算法中，聚类区域采用集中 化的方法，由b s 划分。聚类区域的划分基于网络的最优聚类首领数q ( 由系统预 先指定) 以及网络中各节点的位置信息。b s 根据这些信息将传感网络覆盖的区域 平均分为q 个聚类区域，每个区域的面积大体相等，如图3 2 所示。聚类区域的划 分是在第一轮进行的，一旦划分完毕，在整个网络生命周期内将不再变动。为此， 第三章基于l e a c h 的固定聚类路由算法的设计思想 在接下来的时间内( 从第二轮开始) ，算法将是完全分布的，节点完全根据本地 信息