（信号与信息处理专业论文）基于定向天线的wsn+分簇路由算法研究.pdf

独 创 性 声 明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作 及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地方 外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含为 获得电子科技大学或其它教育机构的学位或证书而使用过的材料。与 我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的 说明并表示谢意。 签名： 日期： 年 月 日 关于论文使用授权的说明 本学位论文作者完全了解电子科技大学有关保留、使用学位论文 的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁盘， 允许论文被查阅和借阅。本人授权电子科技大学可以将学位论文的全 部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描 等复制手段保存、汇编学位论文。 （保密的学位论文在解密后应遵守此规定） 签名： 导师签名： 日期： 年 月 摘 要 i 摘 要 无线传感器网络，以下简称 wsn（wireless sensor network） 。wsn 由大量 的具有感应，计算和无线通信功能的节点构成。在 wsn 中节点使用不可更换和 修复的电池， 所以在wsn的路由算法设计中， 电池能量的有效利用 （energy-aware） 是一个至关重要的因素。 本文针对 wsn 的网络结构特点和能量消耗特性， 首先分析了 wsn 路由算法 设计中的关键因素，介绍了在众多 wsn 路由算法中具有代表性的一些协议和算 法，并且分析了它们的优劣。在众多的路由协议中，具有代表性的算法是定向传 播和分簇路由。定向传播基本思想是节点感应数据然后定向地朝着基站方向传输 从而达到尽量避免在网内无方向的传播的目的，分簇路由的基本思想是网络中节 点根据地理位置临近程度和能量消耗情况形成不同的簇群，其中簇成员负责感应 数据，簇头负责收集和处理节点数据然后传输给基站。这两种算法都为 wsn 带 来了很大的能量节省，但是这两种路由算法各具有优缺点，并且由于两种路由协 议的网络架构机制不同。所以后续研究中，这两种思想没有同时在一个单一的路 由算法中实现。在以往 wsn 路由算法设计中，全向天线是唯一的选择，这也是 这两种路由思想无法同时实现的另一个原因。本文基于多级分簇的概念，利用定 向天线能给 wsn 网络带来了能量节省和定向高效传播的优势，设计了一种新的 wsn 多级分簇路由算法-cbda（cluster-based routing algorithm with directional antenna utilization for wireless sensor network） 。本文介绍了定向天线的选用以及 天线的特性， 接着在 ns-2 系统中实现了可以满足 cbda 算法需求的定向天线类。 本文在 ns-2 系统中实现了 wsn 的 leach（low-energy adaptive clustering hierarchy）算法和 cbda 算法，并且对 leach 和 cbda 算法在能量有效性方面 进行了仿真和比较。 仿真结果显示， 在同样网络配置和网络性能的条件下， cbda 比 leach 让 wsn 网络寿命延长了 20%左右，出现节点死亡时间延后了 30%左 右。 关键词关键词: 无线传感器网络，定向天线，天线角度，覆盖程度，网络分簇 abstract ii abstract wsn （wireless sensor network） consists of many nodes with antenna which have the abilities of sensing, computing，and communicating. the nodes in wsn use the battery which can not be replaced or charged. so the energy efficiency is one of the main concerns that affect wsn performance in the routing algorithm designation. in this dissertation, the characteristic of wsn routing designation is introduced. based on the analysis of these characteristics, key technology and difficulty in wsn routing algorithm designation is illustrated. next, some typical routing algorithms in wsn are introduced with the analysis of their pros and cons and classified according to three network structures. in former wsn routing algorithms, two typical algorithms bring great improvement to saving energy consumption, which are directional diffusion algorithm and cluster based algorithm. the basic idea of directional diffusion is that useful data gathered by node is transmitted to the base station in a fixed direction, while the basic idea of cluster based algorithm is to form clusters in the network based on nodes location and energy status. in former algorithm, the omni-antenna is the only option which is also a key reason for the fact that directional diffusion algorithm and cluster based algorithm are impossible to be implemented together. in this dissertation, directional antenna is introduced in the wsn routing algorithm designation, and based on hierarchy clustering concept and usage of directional antenna which brings in the advantage of energy saving and effective transmission in a fixed direction, a new wsn clustering algorithm is introduced: cbda. then ns-2 system is briefly introduced in this dissertation. the ns-2 implementations of leach and cbda are realized with simulation results showing that, compared to leach，cbda algorithm can prolong the life span of wsn by 20% and postpone the time point when first node begin to die （running out of power）by 30%. key words： wireless sensor network， directional antenna， antenna angle， overlap extension，cluster 目 录 iii 目录 第一章第一章 绪论绪论 . 1 第二章第二章 wsn 的路由协议的路由协议 . 4 2.1 平面路由协议 . 4 2.1.1 基于协商的传感器信息收集路由协议家族 . 5 2.1.2 定向传播路由算法 . 6 2.1.3 两种基于定向传播的路由协议 . 6 2.1.4 具有信息驱动的节点查询的定向限制路由协议 . 7 2.1.5 基于能量分布的路由协议 . 8 2.1.6 具有随机步进的路由协议 . 8 2.2 分簇路由协议 . 8 2.2.1 自适应分簇路由协议 . 9 2.2.2 具有高效能量利用的传感器信息收集系统的路由算法 . 11 2.2.3 基于门限算法的高效能量路由协议 . 11 2.2.4 最小能量开销路由协议 . 12 2.2.5 自组织路由协议 . 12 2.2.6 虚拟网格架构路由协议 . 13 2.2.7 分簇能量高效利用的路由协议 . 13 2.2.8 两级的数据扩散路由算法 . 14 2.3 基于定位信息的路由协议 . 15 2.3.1 高精度的地理自适应路由协议 . 15 2.3.2 基于地理信息的高效能量利用路由协议 . 16 2.3.3 只在天线发射距离中发送包的地理距离路由协议 . 17 第第三章三章 定向天线在定向天线在 ns-2 中的实现中的实现. 19 3.1 定向天线和全向天线的比较 . 19 3.1.1 定向天线的基本概念 . 19 目 录 iv 3.1.2 全向天线和定向天线的比较 . 20 3.1.3 全向天线和定向天线在 wsn 中的优劣 . 22 3.2 定向天线的控制原理 . 22 3.3 定向天线在 ns-2 中的实现 . 23 3.3.1 定向天线在 ns-2 中功能函数 . 23 3.3.2 定向天线的构建和与 otcl 对象的绑定 . 27 3.4 本章小节 . 29 第四章第四章 基于定向天线的基于定向天线的 wsn 分簇路由算法分簇路由算法 . 30 4.1 cbda 简介 . 30 4.2 cbda 网络初始化 . 30 4.3 cbda 网络稳定阶段 . 32 4.4 cbda 算法的簇头轮换策略 . 34 4.5 cbda 算法的复杂度分析 . 36 4.6 cbda 算法的扩展性 . 36 第五章第五章 cbda 算法在算法在 ns-2 中仿真实现和性能分析中仿真实现和性能分析 . 39 5.1 ns-2 仿真系统简介 . 39 5.1.1 ns-2 的简介和原理 . 39 5.1.2 离散事件模拟器 . 39 5.1.3 ns-2 的网络构件库 . 40 5.1.4 ns-2 的分裂对象模型 . 40 5.1.5 ns-2 的基本仿真流程 . 42 5.2 cbda 算法在 n-2 系统中的实现 . 43 5.2.1 leach 协议的实现 . 43 5.2.2 cbda 协议的实现 . 44 5.3 wsn 网络在 ns-2 系统中环境的搭建 . 45 5.4 leach 和 cbda 算法仿真结果和比较 . 47 5.4.1 较小规模 wsn 网络的仿真结果 . 48 5.4.2 较大规模 wsn 网络的仿真结果 . 51 5.5 本章小结 . 55 第六章第六章 结束语结束语 . 57 目 录 v 致致 谢谢 . 58 参考文献参考文献 . 59 个人简历个人简历 . 61 攻读硕士学位期间的研究成果攻读硕士学位期间的研究成果 . 61 第一章 绪论 1 第一章 绪论 1998 年， 加州大学洛杉矶分校研究中心在美国国防部高等研究计划局支持下 进行的无线集成传感器网络项目是传感器网络研究的开端，它主要目的是为嵌入 仪器，设备和环境中的传感器，执行机构和处理器构建一个分布式的网络环境， 提供 internet 的访问能力。之后，又相继出现了一些新的演示系统，比如智能尘 埃，它主要强调利用 mems（micro-electro-mechanical systems）技术设计微型化 的传感器节点1，总体积约 100 立方毫米的节点完全可恶意像灰尘一样悬浮在空 气中，伯克利加州大学在类似硬币大小的节点中配置了温度，湿度，压力，磁场 等多种传感器，在车辆跟踪动物学家关于水鸟活动的研究中都非常成功。nasa 的 jpl （jet propulsion lab） 研制的传感器网络是为将来的火星探测进行技术准 备的，目前正在佛罗里达宇航中心周围的环境监测项目中进行测试和完善。 在民用方面，intel 和 microsoft 等大公司也开始关注传感器网络方面研究工 作。比如，2002 年 10 月 24 日，intel 公司发布了“基于微型传感器网络的新型计 算发展规则” 。今后 intel 将致力于预防医学，环境探测，森林灭火乃至海底模块 调查，行星探查等领域的应用。 在国内，一些大学和研究机构的研究人员已经在关注这一全新的网络技术， 近几年来国内无线传感器网络的研究进展十分迅速，取得相当丰富的研究成果， 在国内外顶级刊物上都可以看见国人优秀的论文。但是这个领域的研究从总体上 还处于一个起步的阶段，已有的研究工作正在为该领域提出越来越多需要解决的 问题。 而比起别的无线网络， 甚至是与之相近的 ad hoc 网络， wsn （wireless sensor network）中路由协议的设计在以下的六个方面更具有挑战性。 1）大量的无线节点无法分配统一的 id，否则通信开销过大。比起在 ad hoc 网络是以节点之间通信为主要目的，wsn 是以数据的获取和查询为重点2。 2） wsn 在绝大多数应用中都是要求数据从多个源节点向基站或者特点的网 关汇聚，而实际上每个节点并不是像 ad hoc 网络中节点一样是数据通信的终端。 3）每个节点能量 3 、储存、计算、通信资源都非常有限，所以不能仅仅从 网络通信的可靠性出发，而使得网络中存在大量的冗余数据造成无谓节点的能量 电子科技大学硕士学位论文 2 消耗，最终引起网络寿命的缩短。 4）和 ad hoc 的节点可以自由移动的情况不一样 4 ，wsn 中的节点在大部 分应用中一经分布就不再移动，网络拓扑的变化只会因为节点的死亡而引起。并 且 wsn 网络拓扑形成一般不是人为精确控制，而是通过飞机布撒形成。 5） 由于 wsn 的数据收集都是基于区域的， 所以位置信息在 wsn 中很重要。 得知节点位置信息可以减小网络中寻呼的开销。 6）由于 wsn 中许多节点可能监视同一片区域，所以数据的冗余和重复发生 的非常频繁，这就需要路由协议拒绝传输一部分数据来提高能量和带宽利用率。 通常 wsn 是基于数据属性的网络，这样的网络一般包含一系列的数值查询表。 比如当湿度超过 90的时候，节点就收集数据然后开始汇报。 7）最后也是最重要的一点，一般 ad hoc 网络中的节点的电池是可以人为更 新和修复的，所以不会出现节点的死亡而引起网络性能的下降的情况。但是在 wsn 网络中， 节点的电池是无法人为更换和修复的， 所以节点的死亡意味着网络 性能的下降。所以在 wsn 的路由算法设计中能量有效利用是至关重要的。 本文的研究任务首先是针对 wsn 网络中节点无法分配统一 id 的情况，采用 分簇路由的方式使得基站对网络的拓扑管理更透明。其次由于 wsn 网络的绝大 部分应用中节点都是处于低移动甚至是静止状态，所以本文假设所有节点都处于 静止状态，从而减轻了路由能量的消耗。接着由于 wsn 网络中节点是以收集信 息为主要目的，本文对数据的定向发送进行了研究。最后，wsn 中节点使用不可 能更换和修复的电池，所以在保证通信质量的情况下，本文对减少能量的开销特 别是通信能量的开销进行了研究和算法设计， 这也是本文提出的 cbda 算法的最 重要设计目标。 根据以上的分析和研究，本文中 cbda 算法主要的设计思路是在保证通信质 量的情况下，利用定向天线的优势，结合两种有效的路由思路设计 cbda 这种在 分簇基础上网络中数据定向传播的路由协议。cbda 协议的主要思想是网络中节 点使用定向天线，在获知基站方位以后朝向基站方向定向的辐射。正是由于节点 都定向辐射，算法利用这个特点来对网络进行分簇。相对基站距离近的节点可以 处于相对基站距离远的一些节点的有效辐射范围中，然后根据这些近距离节点同 时被远节点有效辐射的程度来形成网络中的簇群。簇头根据簇成员情况被分为不 同级别的簇头。 本文的关键技术第一是定向天线在 ns-2 系统中的实现。本文通过在 ns-2 中 编写定向天线类这种 c+类，然后将其绑定到 otcl 类从而可以被用户调用。第 第一章 绪论 3 二是 cbda 算法在 ns-2 系统中的实现。 实现的方法是在 ns-2 中编写 tcl 语言， 然后在脚本语言中实例化相应的类 （包括已实现的定向天线类） ， 根据算法思路建 立起整个运行于 cbda 算法之上的无线传感器网络，最后通过仿真模拟运行网 络，然后得到 trace 文件用来分析网络的能量消耗情况。cbda 在也有一定的 网络局限，cbda 算法可以使网络中节点能量消耗更均匀，延长网络的寿命，并 且灵活地实用于不同规模网络， 但是 cbda 不太适用于具有多个基站或者基站处 于网络节点中的无线传感器网络，并且由于本算法基于节点具有低移动性设计， 所以它不使用于节点具有很高移动性的网络。cbda 因为引入了对覆盖程度计算 统计以及其他判定门限判定的算法，所以对节点的运算能力和存储能力提出更高 的要求。 电子科技大学硕士学位论文 4 第二章 wsn 的路由协议 本章主要介绍了一些典型的 wsn 路由协议或算法。一般来说，根据网络架 构 wsn 路由算法可以分为平面路由算法（flat-based routing） ，分簇路由算法 （hierarchical-based routing） ，基于地理信息的路由算法（location-based routing） 。 在第一类算法中，所有节点都觉有相同的计算，通信能力并且实现相同的网络功 能和任务。第二类算法中，节点会担任不同的角色完成不同的网络任务。最后一 类算法中，节点的地理位置被融合在网络传输的数据中，通过这种方式来对网络 的路由选择和数据处理产生相应的影响。但是所有的无线传感器网络都具有以下 的基本模型： 汇聚节点 监测区域 固定或移动基站 互联网或终端用户 图 2-1 传感器系统模型 2.1 平面路由协议 这类协议是一种多跳的，平面选路的路由协议，其中所有的节点具有同样的 功能和任务，协同起来收集数据并且直接向基站传输。由于网络中具有大量的节 第二章 wsn 的路由协议 5 点，所以网络给每一个节点统一分配 id 是不可能的。网络是以数据收集为目的， 基站向特定区域发送查询信息，网络基于数据属性对节点取名来有效的收集被查 询的信息。下面介绍几种典型的平面路由协议。 2.1.1 基于协商的传感器信息收集路由协议家族 heinemann 提出了 spin 5 ，6 （sensor protocol for information via negotiation） 家族协议，这个协议族把各个节点的信息散布到网络中每一个节点，使得每一个 节点都是潜在的基站 ， 这样使得用户可以通过访问任一个节点来收集到所需的信 息。 spin 协议应用了数据协商 （data-negotiation） 和源自适应 （resource-adaptive） 算法。 节点通过发送对于数据属性的描述而不是数据本身来达到节省能量的目的， 比如图像信息，节点首先判断新接收到的图像信息是否和上一次接收的图像信息 有无变化再决定是否发送。 传统的泛洪算法在广播信息时带来了很多重复数据造成网络能量带宽的浪 费。gossiping 算法通过发送包到一个任意节点而不是盲目的广播，但是这样仍然 存在数据传输延迟太大的问题。而 spin 协议族为自己收集的信息命名来完全的 描述数据属性并且在传输数据前进行协商，避免了泛洪的浪费以及 gossiping 的 延迟问题。 spin 中数据分为三种，adv、req 和 dat。adv 用来广播新数据的属性， req 用来请求接收新的数据，data 则是实际传输的数据包。当节点发现接收到 的 adv 中包含了新数据属性，就向发送 adv 的邻居节点发送 req 请求数据， 相应邻居节点把 data 发送出来。 spin 协议家族中有许多成员， 其中最重要的两个是 spin-1 和 spin-2。 这两 个协议都在传输数据前进行筛选来保证只传输有效信息，并且两个都有自己的资 源管理器。 spin-2 是 spin-1 的扩展， 它在 spin-1 的基础上采用了能量知晓的门 限策略: 当节点能量富裕时，使用 spin-1 协议，当节点能量开始处于一个低门限 的时候，节点只在自己确认能量不被消耗到低门限的时候才参与协议。这两个协 议实用于节点具有一定的移动性的网络。 简单介绍一下这个协议家族中别的成员。 spin-bc（broadcast channel ） ：设计为来广播信道。 spin-pp（point to point） ：用于点到点的通信。 电子科技大学硕士学位论文 6 spin-rl（return loss） ：当信道有噪音时，在 spin-pp 基础上来计算损失信 道。 spin 协议家族的优点是网络拓扑的改变是区域性的， 因为每个节点只知道距 离自己一跳远的邻居。spin 比起泛洪和 gossiping，能更好地节省能量和消除 冗余信息，而缺点是它无法保证关键数据的准确传递。 2.1.2 定向传播路由算法 intanagonwiwat 提出了定向传播算法 7 （directed diffusion） 。此算法基于数 据属性，用属性-数据这对值来描述网络中产生的数据，通过判定数据属性来减小 对因为传输冗余数据来带来的网络开销。其基本算法思想如下: 第一阶段，节点检测事件，并且在邻居节点中创建相应的信息等级 （information gradients） ，基站广播用户需要的数据属性。每个节点在收到数据属 性后向自己的邻居广播。节点收到这个属性后请求广播，建立以一个到能感应这 类数据的源节点的链路，链路中分为不同的信息等级。这个过程一直持续到从源 节点到 bs 都建立起事件等级。每个等级都特定描述了一个属性值和一个方向。 不同的邻居群有不同的等级，表明了不同数量的信息流。 第二阶段，当事件因子符合基站发出的兴趣以后，相应的信息流通过多条路 径到达基站。最好的那些路径被赋予高的权值。所有的广播信息为了减少数据的 冗余，数据在通向基站的路径上被融合。最后找到一最优的路径来把这些融合的 数据传给基站，基站在开始接受数据的时候继续发送广播来更新这些路由信息。 定向传播算法比起 spin 家族有两个优势。第一，通过基站广播兴趣，保证 重要事件的收集。 第二， 定向传播算法中节点都只和邻居节点通信， 不需要像 spin 那样维护一个全网络的拓扑信息。但是定向传播算法不适应于那些要求从源节点 到基站连续传输数据的网络，因为它只在有查询时传输数据。并且此算法在匹配 数据和查询的时候会在节点上产生额外的通信开销。 除了这两个著名的协议还有以下的平面路由协议。 2.1.3 两种基于定向传播的路由协议 谣传路由算法谣传路由算法8（rumor routing）是基于定向传播的改进协议，主要用于当 地理选路不可能实现时使用。它的主要思路是，只向能够监测到相应事件的源节 第二章 wsn 的路由协议 7 点发送查询信息，而不是向整个网络泛洪这个查询信息。此算法引入了代理 （agent） ，代理是一种长时间存在的数据包。当以一个节点探测到一个事件，就 把这个事件加入到本地的事件表里面去，然后产生一个代理包。这个代理包在网 络中不断的被转发，来告诉远节点本地节点希望监视哪些事件。当一个节点为一 个事件发出查询信息时，那些知道能传输此事件的路由细节的节点可以根据本地 事件表然后对查询节点发出回复。这样在查询时不需要泛洪查询信息，从而不会 引起网络能量的过大开销。仿真结果显示谣传路由算法比起定向传播大大的减小 了网络能量的开销。但是谣传路由算法只适合那些事件种类很少的网络，否则当 节点维护的事件表过大时，节点计算储存开销大大的增加并且会带来引起网络通 信增大的后果。 基于梯度的路由协议基于梯度的路由协议9（gradient-based routing）也是基于定向传播的改进协 议，它主要思想是节点记录下传输事件从基站到自身的跳数，以最小的跳数作为 自己到基站的高度，自己和邻居节点高度差认为是链路上的梯度。网络总是用具 有最大梯度的链路来传输数据包。仿真结果表明，gbr 比起定向传播算法进一步 降低了网络整体能量的消耗。但是此算法中位于具有最高梯度差的链路上的节点 会更快的死亡， 而且重新形成新的具有最高梯度的链路给网络中很大的重组开销。 2.1.4 具有信息驱动的节点查询的定向限制路由协议 具有信息驱动的节点查询的定向限制路由协议10被分为两部分：信息驱动的 节点查询 idsq （information-driven sensor querying） ，和非定向路由 cadr （constrained anisotropic diffusion routing） ，cadr 用于形成基本的定向路由， 它的基本思想是网络在查询节点和路由数据的基础上用最小的延迟和带宽来获得 最大的信息权值。cadr 根据一组信息判据来决定来决定哪个节点得到被查询的 数据，这个方式是通过只激活在事件附近的节点，传输动态的路由数据来实现。 cadr 和定向路由最大的区别就在于考虑通信开销的信息权重，信息的权重通过 节点分析本地信息和用户需求来得到。在 idsq 中发出查询的节点决定了那个节 点可以提供最重要的信息以及具有更少的通信开销， 但是 idsq 并不指定在 wsn 路由路径。idsq 是一种优化算法。仿真结果显示，这个协议比起定向路由协议 更具优势，以及更容易找到最临近事件的节点，因此会对网路的寿命有一定的提 高。 电子科技大学硕士学位论文 8 2.1.5 基于能量分布的路由协议 基于能量分布的路由协议11（energy-aware routing）比起定向传播算法使得 网络中节点同时维护多条路径而不是仅仅强化一条最优的路径，然后通过某种概 率来选择其中的一条路径而，这个概率由路径上能量消耗决定。这样每条路径上 节点的能量不会很快的被耗尽，并且高能量消耗的路径被自动禁止。此协议的最 终目的就是使得网络的寿命最长。仿真结果表明此协议比起定向传播路由，节省 了 21.5%的网络能量，并且使网络的寿命延长了 44%。 这个路由协议的缺点在于，由于网络要求收集位置信息和建立起地址分配机 制，所以在路由建立阶段比起定向传播算法消耗了更多的能量。 2.1.6 具有随机步进的路由协议 具有随机步进的路由协议12（routing protocol with random walks）目的在于 通过建立多条路由来达到静态意义上的负载平衡。这个协议是只针对大型的，移 动性非常小的 wsn 而设计。此协议假设每一个节点都可以随机的关闭和激活， 并且没一个节点都有一个独特的标识，所有节点都是集中的分布在网格的交点附 近。当需要找到一条从源节点到目的节点的路径时，通过定位信息或者交点坐标 来结算出节点之间的距离。 节点距离的计算则通过著名的bellman-ford算法实现。 由于不需要确切的定位信息， 所以每个节点都具有离另一个节点的最近距离概率。 协议通过算法来适当的操纵这个概率来达到静态的负载平衡。每个节点只需要维 护很少的状态信息，任何一对节点每次的路由都不相同。 这个协议最大的缺点就是对于网络拓扑的前提条件时非常苛刻，所以在真正 的应用中非常的受限。 2.2 分簇路由协议 分簇路由协议用于 wsn 主要是为了达到节省网络能量的目的，在分簇路由 算法中，能量级别高的节点作为头节点来处理和传送信息，而能量级别低的节点 则负责完成感应数据和向头节点发送信息的功能。正是由于分簇思想的引入，网 络中节点完成不同的任务，使得网络的寿命，稳定程度，和效率都大大的提高。 第二章 wsn 的路由协议 9 然而在分簇路由协议中，技术重点不是路由本身，而是哪个节点在什么时候成为 头节点。 下面根据提出时间的先后来介绍一下 wsn 中主要的分簇路由协议: 2.2.1 自适应分簇路由协议 自适应分簇路由协议13（low-energy adaptive clustering hierarchy） ，应用这 个协议的网络首先随机选择一些节点成为头节点，头节点主要功能是融合簇内节 点传来的信息， 然后把数据发送给基站， leach 在簇内使用 tdma （time division multiple access）方式在簇外使用 cdma（code division multiple access）方式来 避免内外信道的冲突。然后别的非头节点轮流成为头节点从而达到网络中各节点 能量的平均消耗的目的。并且在实验仿真中，只有 5的节点会成为头节点。 由于在无线传感器网络中数据都是集中收集和处理的，所以 leach 协议非 常适用于需要连续监控的无线传感器网络。 leach 的实现分为建立阶段和稳定阶段。 建立阶段， 网络中的节点簇开始形成， 随后一小部分节点会被选择为头节点。 在这个阶段中，每个成员节点变成为头节点的概率 p，p 对于每个节点是一个随 机分布在 0 和 1 之间的数。如果这个值小于一个门限值 t(n)这个节点就成为这一 轮的头节点，这个门限值计算公式为t(n)=p/(1-p(rmod(1/p) if n g 。 其中 g 代表在前 1/轮中没有成为头节点的节点数目。 每个新产生的头节点 就向网络发出广播宣告，接受到这些宣告的非头节点根据宣告信号的强弱来决定 自己将加入哪个簇。当所有簇完全形成以后，每个头节点给自己簇内的节点分配 一个 tdam 中的时隙，然后把这个分配信息发布到簇内. 在头检点之间，不同的 头节点使用不同的 cdma 伪码来避免头节点之间的干扰. 稳定阶段，成员节点把信息传送给头节点，头结点对数据进行压缩和融合， 然后发送给基站。在经过一段特定的时间后，系统回到建立阶段并重新确立新的 簇和新的头节点。 下图为无线传感器网络 leach 模型。 电子科技大学硕士学位论文 10 监测区域 基站 成员节点簇头 图 2-2 无线传感器网络 leach 模型 leach 虽然能延长网络的寿命，但是此协议中有很多不合理的假设，比如 leach 认为所有的节点都有足够的能量来直接和基站通信，支持所有的 mac 协议，所以 leach 的使用范围不广。而且动态进行头节点更换会产生过多的通 信开销。最后 leach 认为每个节点完全一样，所以它也不适用于节点资源状况 相差较大的无线传感器网络。 表 2-1 显示了 spin，定向传播算法和 leach 算法在最佳选路性能，网络寿 命长短，对资源属性的敏感程度，是否使用元数据这四个方面进行了一个定性的 比较。 第二章 wsn 的路由协议 11 表 2-1 spin，定向传播算法和 leach 的比较 spin directed diffusion leach 最佳选路 否 是 否 网络寿命 好 好 很好 资源属性知晓 是 是 是 元数据使用 是 是 否 2.2.2 具有高效能量利用的传感器信息收集系统的路由算法 pegasis 14 （power-efficient gathering in sensor information systems） ， 此协 议是基于 leach 协议。它主要的思想是为了延长网络寿命，节点只和最临近自 己的邻居节点通信，然后这些临近的节点轮流和基站通信，在每个节点都和基站 通信一次以后，新的一轮又开始，这样一直循环下去。 pegasis 主要目的是一，在 leach 基础上进一步延长网络寿命。二，由于 节点间通信只局限在邻居之间，所以减少了信道开销和避免了簇间通信开销。 节点根据信号的强度来确定邻居节点的距离，并且相应的调整发送信号的强 度使得只有特定的节点可以收到信息。 虽然 pegasis 避免了簇信息通信开销，但是节点仍然需要知道它邻居节点 的能量状况来决定选路，拓扑调整会带来巨大的通信开销。而且，pegasis 的算 法会让远距离的节点和基站之间有很大的通信延迟。 2.2.3 基于门限算法的高效能量路由协议 这个协议和 spin 一样是一个协议家属，有两个协议成员15 ，16：tee