无线传感器网络论文正文.doc

第一章 无线传感器网络1.1 研究背景与意义在当代大多数信息技术领域中，作为基础的传感器技术取得了飞快的发展，在获取信息方面是一种很重要的方式。它作为基础知识出现在物联网等一些新兴概念中，随着现代传感器技术的发展，人们获取信息数据的技术的方式由过去单一化逐渐的朝微型化和网络的转变，带来了无线传感器网络的迅猛发展。 近年来，随着技术水平的大规模提高，无线传感器网络的应用条件越来越成熟，应用范围也越来越广。例如在环境监测中，可以用于监测大气成分、温度、湿度、亮度、压力、噪声等; 在医疗方面，在病人身上安置传感器，可以随时远程监控病人病情; 在工业控制中，许多大型设备需要监控关键部件的技术参数;在科学研究领域，传感器网络提供了一种新型的研究手段，可以应用在地震、火山活动过程、生态系统微观行为的观察等研究中;在军事领域，传感器网络可应用在战场监测及武器装备试验中，也可以用于对军用物资的管理; 传感器网络与农业结合，对农作物和环境进行监测，根据实际情况调整水分、肥料和杀虫剂的使用量，可以达到低耗费、低污染、高产出的目的;在交通控制领域，车辆若装有传感器，可以监测车辆位置、速度、道路状况和车辆密度等信息，有助于司机了解路况。此外，无线传感器网络在智能家居、智能办公环境等方而也大有用武之地。因此，无线传感器网络的研究与开发成为近年来信息领域的研究热点1。1.2 无线传感器网络1.2.1 无线传感器网络的基本概念1WSN 概述无线传感器网络是由分布在一定范围内的大量传感器节点组成，各节点之间多以无线多跳无中心方式连接，并且能够协作地感知、采集和处理网络覆盖区域内目标对象的信息，并将相应信息返回给观察者。从上述定义可以看到，传感器、感知对象和观察者是传感器网络的 3 个基本要素；无线网络是传感器之间、传感器与观察者之间的通信方式，用于在传感器与观察者之间建立通信路径；协作地感知、采集、处理、发布感知信息是传感器网络的基本功能。一组功能有限的传感器协作地完成大的感知任务是传感器网络的重要特点。传感器网络中的部分或全部节点可以移动。传感器网络的拓扑结构也会随着节点的移动而不断地动态变化。节点间以 AdHoc 方式进行通信，每个节点都可以充当路由器的角色，并且每个节点都具备动态搜索、定位和恢复连接的能力。传感器由电源、感知部件、嵌入式处理器、存储器、无线通信部件和软件这几部分构成，电源为传感器提供正常工作所必需的能源。感知部件用于感知、获取外界的信息，并将其转换为数字信号。处理部件负责协调节点各部分的工作，如对感知部件获取的信息进行必要的处理、保存，控制感知部件和电源的工作模式等。无线通信部件负责与其他传感器或观察者的通信。软件则为传感器提供必要的软件支持，如嵌入式操作系统、嵌入式数据库管理系统等。观察者是传感器网络的用户，是感知信息的接收者和应用者。观察者可以是人，也可以是计算机或其他设备。例如，军队指挥官可以是传感器网络的观察者；一个由飞机携带的移动计算机也可以是传感器网络的观察者。一个传感器网络可以有多个观察者。一个观察者也可以是多个传感器网络的用户。观察者可以主动地查询或收集传感器网络的感知信息，也可以被动地接收传感器网络发布的信息。观察者将对感知信息进行观察、分析、挖掘、制定决策，或对感知对象采取相应的行动。感知对象是观察者感兴趣的监测目标，也是传感器网络的感知对象，如坦克、军队、动物、有害气体等2。感知对象一般通过表示物理现象、化学现象或其他现象的数字量来表征，如温度、湿度等。一个传感器网络可以感知网络分布区域内的多个对象。一个对象也可以被多个传感器网络所感知。2WSN 特点 从路由的方面来看，无线传感器网络既不同于传统因特网和蜂窝移动网，也不同于移动自组网(MANET，Mobile Adhoc Network)。无线传感器网络主要特点如下：1) 微型传感器价格低廉。 适合大规模应用，微型传感器集成了多种功能 ，如无线通信、数据采集、数据处理等，并且微型传感器体积小，适合隐蔽安装，也被称为智能尘埃。2) 节点资源有限。节点微型化导致了节点硬件资源有限。节点通常由电池供电，一般情况下 5 号电池供电，半年左右就需要更换，所以节点的能源是受限的，一旦电池能量耗尽，节点便无法继续提供服务。3) 节点数目众多。为了能够捕获精确信息，需要在目标区域放置大量节点 ，以防出现盲区，数目众多的节点可以给网络提供冗余，保证了网络的健壮性，不会因为某个节点出现差错，导致工作异常。4) 动态拓扑。因为无线传感器工作时，受到多种外界环境因素的制约和干扰 ，某些节点可能会随时终止工作, 节点本身也可能是移动的，所以无线传感器网络的拓扑不是一成不变的, 而是处在变化中。5) 自组织网络。在现实的应用中，节点安放的位置可能无法预先精确定位 ，相邻情况也无法准确估计, 这就要求节点能够自组网络，自动进行配置及通信，相互协调工作，对不断变化的网络拓扑做出响应。6) 多跳路由。因为无线节点的功率都比较小，为了节省电力，信号覆盖范围往往很有限，不可能覆盖整个网络，信号的对外传输需要相邻的节点来完成，这就要求网络中的节点还要担负路由的工作，要参与信号的转发，每个节点都要担负中继的角色，信号往往经过多个网络中节点接力传输后才能到达汇聚点3。1.2.2 无线传感器网络体系结构无线传感器网络一般包括传感器节点、sink 汇聚节点和任务管理节点，这些节点可以通过人工、机械、飞行器抛撒等方式随机部署到监测区域内，一般的无线传感器网络的结构如图 1-1所示。 图1-1 无线传感器网络的体系结构 Fig.1-1 The system architecture of WSN 无线传感器网络根据需要和应用环境的不同，其结构可能会做出相应的调整。在传感器节点部署好以后，传感器节点会以自组织的形式构成无线网络，通过多跳中继的方式将采集到的数据发送给 sink 汇聚节点，同时，sink 汇聚节点也可以同样的方式将信息发送给各个传感器节点。最终，借助于长距离通信或 internet，sink 节点将监测区域内的感知数据发送给远端的任务管理节点。3网络拓扑结构 在 WSN 中，主要可以分为二种结构。分别为平面结构和分层网络结构。当区域内的节点数量偏小时，基本采用平面拓扑方式。相反，当网络规模很大，节点数目众多，此时应采用分层网络结构4。(1) 平面结构存在于平面结构的网络中的节点都是完全相同。在规定的通信范围内，它们可以和任意节点进行通信，有的节点能量耗尽不能工作，网络受其影响较小，可以看出平面结构的容错性较高。为保证区域内的节点都可以正常的接收发送数据，因此每个节点都要存储详细的路由信息，显然能量利用率很低。(2) 分层结构在分层结构的网络中的节点有三种存在方式。一个完整网络是有许多的簇组成，而每个簇都含有一个簇头节点和普通成员节点，而传感器节点和通信节点又构成了普通成员节点。这里的普通节点功能单一，没有较为复杂的工作任务，减少了路由记录的过程，扩展性很强。但其也存在不足，因为执行分簇路由算法，因而在能量消耗上和网络运行的稳定程度上都存在一定困难。1.2.3无线传感器网络的关键技术 无线传感器网络具有广泛的应用前景，已经成为信息领域研究的一个热点问题。由于它具有鲜明的多学科交叉特点，从关键技术的研究来看，研究的热点和难点主要集中在以下几个方面： (1) MAC 层协议。无线传感器网络的 MAC 层协议必须达到如下两个目标：一是创建网络基础设施，为节点间的通讯建立链路；一是传感器节点间公平地共享通信资源。由于节点的能量限制和数量巨大，而且无线信道存在单向性和广播性等特点，如何设计有效的媒体访问控制策略，减少通信冲突，节省能量就成了 MAC 层协议研究的主要内容。 (2) 路由协议。它是无线传感器网络的一个核心问题。传感器节点能量有限，设计的路由协议不能太复杂，可以尝试以数据为中心，或者利用节点的位置信息进行路由，同时还需要考虑数据融合等操作，传统的无线网络路由协议不再适合或不完全适合于无线传感器网络。 (3) 时空约束。无线传感器网络是应用相关的网络，必须使用时间和空间信息对所感知的事件进行刻画，而传感器节点通常又基于空间关系决定其所采取的动作，同时，时间对协议的运行也有显著的影响。因此该网络具有时间和空间约束。 (4) 网络安全。无线传感器网络部署在真实的物理空间，缺少专门的维护，安全受到严峻的挑战。该网络可能受到非法用户入侵、节点遭到俘获、路由欺诈等构成的安全威胁。因此，如何保证网络在执行秘密任务时产生可靠的数据就成了必须在设计网络时考虑的问题。 (5) 能源感知计算。节能是传感器网络设计中不可回避的一个核心问题，主要包括节点能源管理、网络内能源优化和自适应能源计算。对于传感器节点，需要实现计算、通信和存储相互协调的能源管理；对于整个网络，需要考虑通信的分布、动态的拓扑管理、计算与通信的权衡以及如何减少通信中不必要的额外开销。 (6) 数据的融合与管理。无线传感器网络的很多应用（如目标跟踪、识别），需要多个传感器节点相互交换获取的多种数据信息协同处理才能完成。对于能量有限的传感器网络而言，如何选择参与协作的节点，根据资源消耗和应用需要均衡信息分布，是非常重要的问题。尤其当节点部署密集时，感知信息高度冗余，而网络带宽有限，高效的数据融合算法就显得至关重要5。1.3本文主要内容及安排本文研究的主要内容：首先，对无线传感器网络的概念、特点、体系结构及关键技术等进行介绍与研究，接着根据 WSN 的拓扑结构，主要研究它的路由协议，再对其中的一些典型的协议进行分析与比较。其次，分析几种协议的优缺点，选择 LEACH 协议作为研究重点，深入研究分析 LEACH 协议的优缺点等，介绍在LEACH 基础上改进的经典算法。 最后，以前面的研究分析作为基础，在 LEACH 算法的模式上进行改进，详细阐述改进协议的关键点、网络模型、能量模型、改进技术，并将改进后的算法与 LEACH 协议及一些经典算法进行仿真，分析相关仿真实验结果。本文的主要工作是通过对 LEACH 协议的研究分析，针对不足之处，进行部分改进，改进了簇头选取方式、规范了成簇范围等，并用 MATLAB 语言进行仿真实验，仿真结果表明经过改进的协议优于 LEACH 协议。安排如下：第 1 章介绍本论文研究背景和目的，无线传感器网络进行了概述，介绍了无线传感器网络体系结构和特点，分析了无线传感器网络的关键技术，制定出本论文的研究内容及论文安排。第2章重点分析无线传感器网络传统的路由算法，讲述了路由协议的种类，简单介绍各类别中的典型算法，对算法优点及不足加以说明，并进行做表比较。重点介绍LEACH算法过程，并对LEACH算法进行深入的分析研究。第3章在 LEACH 算法基础上，提出存在问题和改进方法，分别在簇头选取、簇形成和簇间通信进行研究与部分改进，描述具体算法。并且对改进算法通过 MATLAB 语言进行仿真，并在多方面性能上与三种典型协议进行分析与比较，评价改进算法的效果。第 4 章对本文的研究与改进做一个总结，并阐述 WSN 路由协议的发展趋势及未来研究方向。 第二章 无线传感器网络的路由协议2.1无线传感器网络路由协议概述 无线传感器网络作为一种无线多跳的自组织网络，其信道不稳定、信道间干扰、节点的移动性和实效性等特点，使得传统互联网路由协议不再适应于无线传感器网络。在 WSN 中，路由协议是至关重要的，由于 WSN 网络节点的能量有限、数据传递采用多跳路径，大多数节点不能与网关直接通信并且节点分布的位置是未知的，这些都导致无法继续沿用传统路由协议。网络的性能及工作效率的高低，这些都和路由协议的设计紧密相连，它不仅是网络中传感器节点传递消息的桥梁，也是网络层的关键部分。路由协议所起的作用就是将搜集到的数据从传感器节点发送到监测节点。其中有两个关键点：一是目标节点和监测节点之间的数据传输路径；二是数据被分成若干个组按照对应的路径准确转发。传输路径是十分重要的，可以让个网络得到有效利用，并且达到了均匀分布网络流量6。2.2路由协议分类2.2.1平面路由协议平面型路由协议中，各节点地位平等，而层次型路由协议中，需要有若干个节点充当簇首，负责集中处理簇内成员的数据，并将加工后的数据与相邻的簇首交互通信。本节将介绍一些典型的路由协议。1.洪泛协议和流言协议 这两个协议是最为经典和简单的传统网络路由协议，可以应用到WSN中。洪泛协议中，节点产生或收到数据后向所有邻节点广播信息，直到数据报文过期或者到达目的地才停止传播。该协议存在的缺点是：内爆，节点几乎同时从邻节点收到多份相同的数据。交叠，节点先后收到监控同一区域的多个节点发送的几乎相同的数据。资源利用盲目，节点不考虑自身资源限制，在任何情况下都转发数据。流言协议则是对洪泛协议的改进，节点不再以广播的形式发送数据，而是随机选取一个邻节点转发，这样就有效避免了内爆问题，但是增加了信息时延。2.基于信息协商的路由协议（SPIN）SPIN是一种经典的以数据为中心的路由协议。图2-1展示了SPIN取路由的建立和数据传输过程。SPIN中，节点使用三种类型的消息ADV、REQ和D八TA进行通信，ADV用于广播该节点有新数据，REQ用来请求数据，DATA用来封装数据信息。协议的具体过程分3步：节点产生或收到数据后，用包含原数据的ADV消息向邻接点通告，为避免盲目传播，需要数据的邻居节点用REQ消息提出请求，数据通过DATA消息发送到请求节点。SPIN协议采用ADV消息减轻了内爆问题，并通过数据命名解决了消息交叠问题。该协议自身也存在一些缺点，比如当产生或收到的数据节点的所有邻接点都不需要该数据时，数据将不能继续转发，以致较远节点无法收到数据，特别是当网络中sink节点数目比较少时，这个问题将更加严重7。 图2-1 SPIN路由的建立和数据传输 Fig.2-1 The establishment and data transmission of the SPIN routing 3.定向扩散协议（DD）DD定向扩散模型是Estrin等人提出的，与已有的路由算法有着截然不同的实现机制的路由策略。节点用一组属性值来命名其生成的数据，Sink用属性的组合表示节点发出的查询业务，逐级扩散，最终遍历全网，找到所有匹配的原始数据。“梯度”变量与整个业务请求的扩散过程相联系，反映了网络中间节点对匹配请求条件的数据源的近似判断。更直接的方法是节点用一组标量值表示它的选择，值越大意味着向该方向继续搜索获得匹配数据的可能性越大，这样的处理最终将会在整个网络中为Sink节点的请求建立一个临时的“梯度”场，匹配数据可以沿“梯度”最大的方向中继回Sink节点。图2-2描述了定向扩散模型的工作原理5。 图2-2 定向扩散路由原理 Fig.2-2 Routing principle of directional diffusion 2.2.2分层路由协议 除了平面路由协议，同时还存在分层结构的层次路由协议。层次路由协议又称分簇路由协议，就是采用簇的概念对传感器节点进行层次上的具体划分。若干个距离相近的节点构成一个簇，而每一个簇会从中选出一个簇头节点。同一网络中簇与簇之间是可以进行网关上的通信。1.低能耗自适应分层协议（LEACH）在 LEACH 算法中，首先进行建立阶段的簇头选择部分。在 WSN 中的全部节点都可以担任本轮中簇的簇头节点，但是簇头节点由谁担任需要标准衡量的：首先判断每一个节点是否在过去的操作中担任过簇头节点，簇头节点需要没有担任簇头的剩余节点中选出。每个节点不可以重复担任簇头节点，除非全部节点都已经担任过簇头节点；其次，取决于整个网络选取簇头节点的个数与全部节点总数的比值，此值在算法执行之前已经设置完毕，这两方面共同决定簇头节点的产生。在初始阶段 WSN 内的每一个节点都会随机生成一个 0 到 1 之间的数，如果阈值 T (n)大于生成的数值，那么此节点在本轮将担任簇头节点。 T (n)的计算公式如下：公式（2-1） 这里，P 表示簇头节点与网络区域内节点总数之间的商；r 表示当前所处的轮数；G 代表在过去一轮中没有担任过簇头的剩余节点的集合。当簇头节点被选出时，它们会向网络中的每一个普通节点发送公告消息。此时网络中的普通节点接到此轮选出所有簇头节点发出的公告消息，它们判断接收信号的强弱并且结合最小耗能原则，选择信号最强的簇头节点作为自己本轮的簇头并向其发送确认消息，确定加入该簇。成为簇内成员后，都有自己的工作时间表，按照 TDMA 开始进入数据传输阶段。当这一轮所有的节点都发送完数据后，簇头节点开始处理数据，因为基站较远，传输耗能较多，需对收到的全部数据进行融合、压缩处理，将优化好的信息以最小的能量传递给基站。至此一轮全部完成，整个网络将进入下一轮操作，开始再次选取簇头节点8。2.传感器系统中能量有效的汇聚算法（PEGASIS） PEGASIS(Power-Efficient Gathering in Sensor Information Systems)协议是在LEACH 路由算法的基础上进行改进的，首先在当前网络中选择一个节点作为链首并建立一条相对最优的链路，链首节点将数据处理后的综合信息发送给基站(BS)。由于链首节点的承载大量负担，所以 PEGASIS 算法采用网络中全部存在的节点，让它们轮流担任链首节点进而使整个网络能量达到相对的均衡。此算法可以有效地延长网络的生命周期，节点只需跟最邻近的节点进行通信。当网络内所有节点都与链首数据传送后，全部的节点会进行新一轮的轮流交替工作。图2-3所示，PEGASIS 算法数据传输过程，这里的传输使用令牌(Token)，首先确定链首，这里 C 2被定为链首，将 Token 沿着链路传给 C 0, C 0将自己的信息传递给C1 ，而 C1 将接到 C 0的信息和自己的信息进行处理，将有效数据传送给 C 2。另一侧同样过程，Token 发送到 C 4， C 4将信息传给 C 3， C 3将自己和 C 4的信息进行处理后发送给链首 C 2。此时 C 2将收集的数据融合整理后传送给 BS。 图2-3 PEGASIA数据传输链的形成 Fig 2-3 The formation of PEGASIA data transmission chain 由于这种通信机制可以使网络能量均匀的分布到每一个节点成员，并且每个节点都是以功率的最小值进行数据传递，因此能量得到有效地利用，运用PEGASIS 协议时网络的生命周期比运用 LEACH 协议时延长近一倍左右9。2.2.3 路由协议的比较 在WSN中采用平面路由算法，其中所有的传感器节点都要有公平对待，其执行的任务和所起的作用是一样的。当在WSN中采用层次式路由协议时，节点有两部，分为簇头节点和成员节点，簇头节点先集中成员节点采集到的信息然后对其进行融合，将最终结果发送到基站，Ifn成员节点的任务只是将自己采集到的数据完整的传送给相应的簇头节点。层次式路由协议不在同一平面，簇头节点和成员节点在整个过程中各自的任务和所起到的作用是有很大区别的。层次式路相对平面路由存在很多优势，概括为以下几点: (1)能量方面，虽然平面路由已经在节能上做了大量改进，但其基本思想还是先找到一条或者几条综合方面较优的路径，然后通过这些路径完成任务，导致节点的能量损耗方面不是很均匀。层次路由协议采用动态构造，因而消耗能量比较少并且其能量消耗分布较均匀，能有效的延长网络寿命，平衡网络负载； (2)开销，平面路由是通过竞争来安排时间顺序，层次路由则是预先确定的，层次路由减少参与WSN路由算法计算节点数量，减少交换路由信息所需通信的一系列开销以及维修保护路由表需要的内存开销； (3)分层路由协议的思想是形成预先特定簇型的模式，通过选举方式产生一个相对稳定的子网络，减少了WSN拓扑结构的变化及其对路由协议所产生的影响； (4)每个簇头节点对其相应簇内的普通节点进行管理，方便快捷将处理过的数据信息地向基站传送，如能量情况、安全问题、是否出现事故等。另外地方基站也可以通过簇头节点有效地向被监测网络中的普通节点下发命令，这是平面路由无法比拟的。 总体来说，判断一个WSN其路由协议的好坏，主要从节能方面、网络生命周期长短、传输推迟时间、可延展性等主要性能指标。同时，也观察到WSN路由协议之间差别很大，网络中不存在一个通用的路由协议14。 表2-1 无线传感器网络中典型路由协议比较 Tab.2-1 Comparison of typical routing protocol2.3 LEACH路由算法描述1. 簇头选取 在 LEACH 算法中，首先进行建立阶段的簇头选择部分，在 WSN 中的全部节点都可以担任本轮中的簇头节点，但是簇头节点由谁担任是存在衡量标准的。首先，判断每一个节点是否在过去的操作中担任过簇头节点，簇头节点需要未担任簇头的剩余节点中选出。每个节点不可以重复担任簇头节点，除非全部节点都已经担任过簇头节点；其次，取决于整个网络选取簇头节点的个数与全部节点总数的比值，此值在算法执行之前已经设置完毕，这两方面共同决定簇头节点的产生。在初始阶段 WSN 内的每一个节点都会随机生成一个 0 到 1 之间的数，如果阈值 T (n)大于生成的数值，那么此节点在本轮将担任簇头节点。T（n）的计算公式如公式(2-1)。2. 簇形成阶段当簇头节点被选出时，它们会向网络中的每一个节点发送公告消息。此时，网络中的普通节点接到此轮选出的所有簇头节点发出的公告消息，它们判断接收信号的强弱并且结合最小耗能原则，选择信号最强的簇头节点作为本轮自己的簇头并向其发送确认消息，确定加入该簇。当普通节点的确认消息都发送完毕后，簇头节点得到了自己簇内成员名单，由此生成一个 TDMA(Time Division Multiple Access)时间表，这是簇头节点制定的通信时间顺序表，每个成员在属于自己的时间段进行信息交流，在不属于自己的时隙内则不进行工作，节省节点能量。3.数据传输阶段此时簇内成员都有自己的工作时间表，按照 TDMA 开始进入数据传输阶段。普通节点不间断的收集者数据，以最小耗能原则在规定的时间段内将信息传递到其所属簇头节点，完成传递后发送器处于关闭状态，节省能源。而簇头节点则需一直工作接收簇内成员的发送的消息。当这一轮所有的节点都发送完数据后，簇头节点开始整理数据，因为距基站较远，传输时耗能较多，所以需对全部数据进行融合、压缩处理，将优化好的信息以最小的能量传递给基站。至此一轮全部完成，整个网络将进行下一轮操作，开始再次选取簇头节点。这里簇头不仅向基站传递信息，更要将接到数据进行一系列处理，较其它普通节点耗相比能量消耗的速度很快。LEACH 算法避免了这种问题的出现，使 WSN内的所有节点都有机会担当簇头节点，把网络负载均与的分给每个节点，这样减少了通信过程的能量损耗。2.4 LEACH路由算法的优缺点LEACH 算法是一个提高能量利用率的分簇路由协议，与以前的传统路由相比存在以下一些优点：(1) 运用分层结构。选取簇头，优化簇内节点发送的数据，将高质量数据传送给基站，同时基站也可以向簇头及簇内普通节点传递消息。(2) 簇内存在多个成员节点，簇的结构稳定，采用簇头与簇内成员之间直接对话，个别节点的改变不会影响网络的整体变化，对路由协议的影响较小。(3) LEACH 算法运用了 TDMA 时间顺序表减少了簇内节点之间的通信堵塞；(4) 除了簇头节点需要实时工作以外，其它成员节点平时可以关闭通信器件，节约能量。 LEACH 算法的上述优点对网络生命周期上有显著改善，但依然存在一些问题：(1) LEACH 算法对簇头数目没有明确限制，只要符合要求就可以当选簇头，不能保证簇规模的合理性，同样也降低了 LEACH 协议的性能。(2) LEACH 算法的簇头选取采用随机轮换制产生，没有考虑能量问题。WSN中的节点当选簇头概率是完全相同的，因而有些节点耗损能量较多的情况下，还是有被选中担任簇头节点的机会，这样的节点能量比其它普通节点失效快，影响了网络寿命。(3) LEACH 算法不能确定簇头节点分布位置，不能保证簇头的均匀分布。当某一区域存在过多簇头或过于集中，它们相邻较近，则收到的数据产生冗余，浪费了节点的能量；当某一区域簇头数较少或分布区域边缘，那么节点与簇头之间信息传递则会浪费许多能量，这样不利于 WSN 的负载均衡。(4) LEACH 算法允许 WSN 内的节点间以及节点与基站(BS)之间采用单跳方式直接进行信息交流。这样势必会引起网络通信渠道的堵塞，通信量大大增加，因而耗能加大，网络的扩展方面受到制约，在大规模网络里效果不佳10。本章详细介绍在 WSN 中的重要部分路由协议，讲述了路由协议的种类，简单介绍各种类别中的典型算法，对算法优点及不足分别说明，最后对几种算法多方面性能进行列表比较，阐述 WSN 中路由协议现存问题及需改进地方。并选出LEACH 协议为代表，详细介绍 LEACH 路由协议的整体思路，包括了体系结构、物理模型、三个主要阶段(簇头选取、簇形成及数据传输)、LEACH 算法优点与存在不足。 第三章 LEACH 路由算法研究31 基本思想综合LEACH算法的不足，主要从簇的形态、成簇的方法、簇首节点的选择依据3个方面对LEACH算法进行改进。在LEACH算法中，由于簇的建立过程中会产生一部分头开销，如果能够减少这部分头开销，那么就可以使网络中的能量更多地消耗在数据传输上。改进后的算法采用固定分簇的方式，即初始阶段时，将簇分好，之后簇内的节点就不再变化了；同时，为了使能量消耗均衡地分散在所有节点上，需要在各个簇内轮换簇首。簇首节点在无线传感网络中具有重要的位置，簇首节点消耗的能量远远高于一般传感器节点。簇首节点消耗的能量包括簇首与簇内节点通信、簇首和Sink节点通信所消耗的能量；相对离Sink节点距离近的簇首节点来说，离Sink节点距离远的簇首节点由于传送距离较大而消耗的能量要高得多。改进后的算法采用不均匀分簇的方法(如图3-1所示)，即靠近Sink节点的簇的半径较大，而远离Sink节点的簇的半径较小，这样离Sink节点距离近的簇首节点在簇内消耗的能量大于离Sink节点距离远的簇首节点在簇内消耗的能量，使得各个簇首节点消耗的能量接近相同，从而均衡了簇首节点能量的消耗。 簇首节点的选择需考虑的是簇内的能量消耗最小化，以及动态选择簇首节点以避免单个簇首节点的能量耗尽。基于簇内耗能最小化与簇首耗能最大这两点考虑，采用以节点剩余能量多少为主要依据来选择簇首节点的方式11。 图3-1 不均匀分簇 Fig 3-1 Not even clumps3.2 算法细节在网络部署阶段 ，汇聚点在网络内以相同的发送功率广播一个信号。传感器节点在接收到此信号后，根据接收信号的强度计算它到汇聚点的近似距离 。预先设定阈值T，传感器节点生成 0 到 1 之间的随机数 ，如果该随机数小于阈值T，则该节点被选为候选簇首节点，参与竞选最终簇首.如果随机数大于阈值，则该节点进入休眠状态 ，直到簇首竞选过程结束。令为任意一个候选簇首 ，根据自身到汇聚点的距离信息计算它的竞争区域 ，区域的半径记作R。算法需要控制竞争半径的取值范围，且随着候选簇首到汇聚点距离的增大, 其竞争半径应随之减小。设定候选簇首的竞争半径的最大取值为，距离汇聚点最远的节点的竞争半径为（1-c)其中c为控制取值范围的参数, 在 01之间取值。候选簇首Si确定竞争 半径的计算公式如下 ：公式（3-1） 式中 是候选簇首到汇聚点sink最远的距离；是候选簇首到汇聚点 sink最近的距离; d(,sink) 是任意候选簇首Si到汇聚点的距离。竞争半径与节点到汇聚点的距离呈线性递减关系.当 c取 12时 ，竞争半径的取值范围为(12 ，)。每个候选簇首维护一个邻簇首集合，任意候选簇首si的邻簇首集合si,定义为：在邻簇首集合中，根据各节点当前的剩余能量高低选择最终簇首12。 图3-2候选簇首的竞争区域 Fig3-2 Candidate cluster head of compete region 在竞争的过程中，若候选簇首Si宣布其竞选获胜，则在Si 的竞争半径R内所有候选簇首均不能成为最终簇,首需要退出竞选过程。如图2所示,S1和S2不能同时成为最终簇首,S3和S4可以同时成为最终簇首。竞争过程中每个节点均以同样的功率发送广播消息，为了节约能量 ，同时确保节点能够和邻簇首集合 内的所有节点正常通信,选取这个广播半径为。所有候选簇首首先广播竞 争消息，包括节点的ID、竞争半径尺和节点的当前剩余能量EN； 根据接收信号的强度计算其他候选簇首到该节点的近似距离,如果节点Sj到该节点的距离小于该节点的竞争半径或者小于Sj的竞争半径,则将Sj节点加入该节点的邻簇首集合，这样构建就完成了。在邻簇首集合 中，节点需要等待其邻簇首集合中所有能量比它大的节点先作出决策，然后才能确定自身是否担任簇首。选择剩余能量最大的候选簇首节点作为最终簇首，最终簇首广播 获胜消息以通知它的邻簇首，如果节点Sj收到获胜消息，但是Sj属于最终簇首的邻簇首集 合范围内，那么节点Sj不参加竞选 ，广播退出竞争 的消息 ，最终簇首节点收到Sj退出消息后,将 Sj节点从最终簇首的邻簇首集合中除去13。最终簇首产生后,原来未参与竞选的节点从睡眠状态唤醒，接着最终簇首以同样的功率向全网广播其竞选获胜的消息。普通节点按照簇内通信代价最小的原则(也就是选择接收信号强度最大的簇首节点），发送加入信息以通知该簇首加入该簇。当簇首节点收到了来自成员节点的加入消息后,基于成员节点的数目，产生一个TDMA 时隙表，簇首节点给每个成员都分配一个特定的通信时隙，成员节点只能在其特定的时隙内与簇首节点进行通信。簇一旦形成，数据传输便可开始。当节点持续采集监测数据时，在其相应时隙，使用最小能量传给簇首节点 。在不发送数据时，关闭节点以节约能量。簇首节点必须保持其接收器一直打开，以接收簇内不同节点的数据。当所有数据接收完毕后,簇首节点进行必要的数据 融合处理，将多个数据融合成一个数据 ，然后发送给基站 。簇形成以后便固定不变，当簇首节点低于某一个门限值时，在簇内重新选择簇首节点，以簇内剩余能量最多的节点为簇首节点。3.3算法分析及仿真通过仿真实验比较改进后的算法B-LEACH、LEACH算法和LEACH-C算法。实验仿真系统由100个节点组成，节点随机分布在( X=0，Y=0)和(X =l00，Y=100)的正方形区域内，每个节点的初始能量为2J。仿真模型参照文献14中LEACH算法创始人WendiBHeinzelman提出的仿真模型 。系统中存活节点数目随时间的变化图，如图3-3所示。从图3-3中可以看出,在相同的时间内采用B-LEACH算法的网络系统存活的节点数目多于采用LEACH算法和LEACH-C算法的 网络系统。这是因为改进后的算法考虑了节点的剩余能量，选择能量剩余多的节点为簇首，更好地平衡了网络负载。 图3-3 系统存活节点的数目 Fig 3-3 The number of the system live nodes基站接收到的数据量随时间变化图，如图 3-4所示。可以看出基站接收到的数据随时间的变化而增加，采用B-LEACH算法网络中的基站接收到的数据量远远大于采用LEACH算法和LEACH-C算法网络中的基站接收到的数据量。这是因为改进后的算法BLEACH采 用了固定分簇的成簇方式，大大节省了LEACH算法中重复成簇所带来的开销，有效地节省了能耗，使更多的能量被用来传递数据15。 图3-4 基站接收到的数据量 Fig 3-4 The receive data of base station 基站接收数据量随网络能耗的变化图，如图3-5所示 。在相同的能耗下，与LEACH算法和LEACH-C算法相比，改进后的B-LEACH算法能够传递更多的数据，说明B-LEACH算法具有更高的能量使用效率16。 图3-5 基站接收数据量与能耗的关系 Fig3-5 The relationship between receiving data and energy consumption 第四章 总结与展望4.1工作内容总结 随着无线通信、传感器等技术的发展与进步，而 WSN 也应时而生，成为一门新兴技术。本文首先简单介绍 WSN 的概述、发展进程和当前研究的情况，其次详细介绍了 WSN 路由协议及其分类，将经典算法分别阐述。然后着重研究分析分簇路由算法和其代表LEACH算法，对其设计思想和优缺点进行研究与分析。针对 LEACH 算法的不足，本文继续沿用 LEACH 算法的“轮”的理念，将网络工作工程分成建立过程和稳定过程。结合 FCMC 算法思想，提出一种改进算法：(1) 在簇头最佳个数方面，虽然将 FCM 算法应用于 LEACH 算法中的簇头选取和簇形成阶段，但是系统必须预先给定最佳簇头个数，如果没有这一初始条件，将无法进行。所以 FCM 算法对初始化要求很严格，通过反复迭代实现，易导致局部极小值，所以不能准确求出整体最优解。为了解决最佳个数问题和 FCM聚类求解更加准确对 FCM 算法进行部分改进。(2) 在簇形成方面,首轮采用改进的 FCM 进行簇头选取和簇的形成，然后当第一轮结束后，节点的能量已经发生了变化，由于输出数据的大小以及距离簇头的远近都决定了节点的剩余能量已经完全不同。簇头节点由于始终保持接收器开放状态，而且处理后的数据要传递到基站，这些能量的消耗远远大于普通节点的耗能。由于本算法使用 FCM 算法进行固定分簇，所以在以后过程中只需要合理的选出各个簇内相应的簇头节点，不需要每轮就构造簇，所以在建簇方面节约能量。这种方法综合考虑了运用到的节点可用能量、基站距离以及节点度的关系，用以共同完成簇形成过程。(3) 改变了簇间通信方式。在 LEACH 算法中，簇头将数据通过单跳的方式传递给基站，但是由于基站距离监测区域很远，簇头节点本身就耗能大，如果通过单跳方式是会消耗很多能量。而 FCMC 算法采用簇间多跳模式，当前簇头节点将自己的数据传递给离自己最近的簇头，并且此簇头比当前簇头节点离基站距离更短，接到其它簇头发来数据的簇头将收到的信息与自己的数据进行融合，然后再次寻找合适簇头节点进行传递，直到将数据传到基站，簇间通信完成。但是当簇头找不到比自己更合适的其它簇头时，它就把数据自己传到基站。这里没有考虑到簇头剩余能量问题，有的簇头剩余能量不足以进行数据处理，有的簇头离基站较近，剩余能量低，不能承担把其他数据传送给基站的任务，这些都会严重影响网络生命时间。改进簇间传递算法，这里将单挑和多跳共同应用到簇间通信中去,采用了单跳与多跳相结合的办法，帮助簇头节点选择出更合理的路径，将数据传递给基站。最后采用 MATLAB 算法对改进算法和 LEACH、LEACH-C、B-LEACH 共三种算法进行仿真，选择从几种性能较全面的分析比较改进算法，仿真结果表明本文提出的改进算法相对于其它三种算法而言，可以较好的将网络负载将均衡的分配到网络节点上，提高能量利用率，从而延长了网络的生命周期。4.2发展与展望网络分簇路由算法，虽然在提高能量利用率、延长网络生存时间实验方面表现良好，但在具体的应用环境中，路由设计需要更多地考虑许多应用相关的设计目标，比如通信时延、网络安全、QOS问题等;(2)本文算法设计假设的网络环境都是针对静态传感器网络的，对于网络拓扑结构动态变化的应用环境，算法还需进一步完善;(3)本文的研究都是基于理想情况的，忽略了许多实际的问题，接下来的工作需要考虑网络的实际因素，并采用网络仿真工具进行进一步的仿真，以验证改进的路由算法是否正确有效。 限于个人能力水平，在算法设计上，本人可能忽略一些问题和因素，在下一步学习工作过程中，本人将进一步充实自己，多学习，多总结，进一步完善现有算法。袁节膅薂羄肅蒃薁蚃芀荿薀螆肃芅蕿袈芈膁蚈羀肁蒀蚇蚀袄莆蚇螂肀莂蚆羅袂芈蚅蚄膈膄蚄螇羁蒂蚃衿膆莈蚂羁罿芄螁蚁膄膀螁螃羇葿螀袅膃蒅蝿肈羆莁螈螇芁芇莄袀肄膃莄羂艿蒂莃蚂肂莈蒂螄芈芄蒁袆肀膀蒀罿袃薈葿螈聿蒄葿袁羁莀蒈羃膇芆蒇蚃羀膂蒆螅膅蒁薅袇羈莇薄罿膄芃薃虿羆艿薃袁节膅薂羄肅蒃薁蚃芀荿薀螆肃芅蕿袈芈膁蚈羀肁蒀蚇蚀袄莆蚇螂肀莂蚆羅袂芈蚅蚄膈膄蚄螇羁蒂蚃衿膆莈蚂羁罿芄螁蚁膄膀螁螃羇葿螀袅膃蒅蝿肈羆莁螈螇芁芇莄袀肄膃莄羂艿蒂莃蚂肂莈蒂螄芈芄蒁袆肀膀蒀罿袃薈葿螈聿蒄葿袁羁莀蒈羃膇芆蒇蚃羀膂蒆螅膅蒁薅袇羈莇袄芈蒇袇螀芇蕿蚀聿芆艿蒃肅芅蒁螈羁芄薃薁袆芃芃螆螂芃莅蕿肁节蒈螅羇莁薀薈袃莀艿螃蝿荿莂薆膈莈薄袁肄莇蚆蚄羀莇莆袀袆羃蒈蚂螂羂薁袈肀肁芀蚁羆肁莃袆袂肀薅虿袈聿蚇蒂膇肈莇螇肃肇葿薀罿肆薂螆袅肅芁薈螁膅莃螄聿膄蒆薇羅膃蚈螂羁膂莈蚅袇膁蒀袀螃膀薂蚃肂腿节衿羈腿莄蚂袄芈蒇袇螀芇蕿蚀聿芆艿蒃肅芅蒁螈羁芄薃薁袆芃芃螆螂芃莅蕿肁节蒈螅羇莁薀薈袃莀艿螃蝿荿莂薆膈莈薄袁肄莇蚆蚄羀莇莆袀袆羃蒈蚂螂羂薁袈肀肁芀蚁羆肁莃袆袂肀薅虿袈聿蚇蒂膇肈莇螇肃肇葿薀罿肆薂螆袅肅芁薈螁膅莃螄聿膄蒆薇羅膃蚈螂羁膂莈蚅袇膁蒀袀螃膀薂蚃肂腿节衿羈腿莄蚂袄芈蒇袇螀芇蕿蚀聿芆艿蒃肅芅蒁螈羁芄薃薁袆芃芃螆螂芃莅蕿肁节蒈螅羇莁薀薈袃莀艿螃蝿荿莂薆膈莈薄袁肄莇蚆蚄羀莇莆袀袆羃蒈蚂螂羂薁袈肀肁芀蚁羆肁莃袆袂肀薅虿袈聿蚇蒂膇肈莇螇肃肇葿薀罿肆薂螆袅肅芁薈螁膅莃螄聿膄蒆薇羅膃蚈螂羁膂莈蚅袇膁蒀袀螃膀薂蚃肂腿节衿羈腿莄蚂袄芈蒇袇螀芇蕿蚀聿芆艿蒃肅芅蒁螈羁芄薃薁袆芃芃螆螂芃莅蕿肁节蒈螅羇莁薀薈袃莀艿螃蝿荿莂薆膈莈薄袁肄莇蚆蚄羀莇莆袀袆羃蒈蚂螂羂薁袈肀肁芀蚁羆肁莃袆袂肀薅虿袈聿蚇蒂膇肈莇螇肃肇葿薀罿肆薂螆袅肅芁薈螁膅莃螄聿膄蒆薇羅膃蚈螂羁膂莈蚅袇膁蒀袀螃膀薂蚃肂腿节衿羈腿莄蚂袄芈蒇袇螀芇蕿蚀聿芆艿蒃肅芅蒁螈羁芄薃薁袆芃芃螆螂芃莅蕿肁节蒈螅羇莁薀薈袃莀艿螃蝿荿莂薆膈莈薄袁肄莇蚆蚄羀莇莆袀袆羃蒈蚂螂羂薁袈肀肁芀蚁羆肁莃袆袂肀薅虿袈聿蚇蒂膇肈莇螇肃肇葿薀罿肆薂螆袅肅芁薈螁膅莃螄聿膄蒆薇羅膃蚈螂羁膂莈蚅袇膁蒀袀螃膀薂蚃肂腿节衿羈腿莄蚂袄芈蒇袇螀芇蕿蚀聿芆