传感器网络中基于leach算法的改进分簇模型研究毕业(论文)设计论文.doc

《传感器网络中基于leach算法的改进分簇模型研究毕业(论文)设计论文.doc》由会员分享，可在线阅读，更多相关《传感器网络中基于leach算法的改进分簇模型研究毕业(论文)设计论文.doc（47页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、湖南大学毕业论文 HUNAN UNIVERSITY毕业设计(论文)设计论文题目：传感器网络中基于LEACH算法的改进分簇模型研究学生姓名：学生学号：专业班级：学院名称：指导老师：学院院长：湖南大学毕业论文 第 42 页传感器网络中基于LEACH算法的改进分簇模型研究摘 要无线传感器网络是众多的传感器通过无线通信的方式，相互联系，处理、传递信息的网络。该网络综合了传感器技术、嵌入式计算技术、分布式信息处理技术和通信技术，可以实时监测、感知和采集网络分布区域内的各种对象的信息，并对这些信息进行处理，传送给所需用户。无线传感器网络在军事、工业、交通、安全、医疗、探测以及家庭和办公环境等很多方面都有着

2、广泛的用途，其研究、开发和应用，关系到国家安全、经济发展的各个方面，近年来在国际上引起了广泛的重视和投入。由于外界环境的不确定性，经常导致需要部署成百上千的传感器协同工作，故对由大量传感器构成的大规模传感器网络的研究正逐渐引起关注，并被认为是本世纪的一项具有挑战性的研究课题。目前，学术界的研究热点主要集中在传感器网络分簇算法、通信路由协议、网络覆盖等领域。LEACH算法是一种典型的层次路由算法，该算法提出了低功耗持续运行的模型。但LEACH算法也存在没有考虑能量的消耗和传感器拓扑结构的问题。本文提出了一种传感器网络中能量有效的分簇算法，该算法在经典的分簇算法LEACH的基础上，通过引入平均能耗

3、调节参数和密度调节参数，使得靠近簇结构地理中心位置的节点以及位于节点密集分布区域的节点有更高机率成为簇头。采用该算法时，传感器网络簇头的选取更为合理，从而进一步优化了簇的结构，均衡了网络的能量消耗，与采用LEACH算法相比，传感器网络的生命周期有一定幅度的延长。 关键词：传感器网络；分簇算法；平均能耗；节点密度LEACH-based Improved clustering model Research in the Sensor NetworkAbstractWireless sensor networks are a kind of network which a lot of sensor

4、s interrelate, process and transmit information with each other through wireless communications. The network integrates sensor technology, embedded computing technology, distributed information processing and communication technology which can be real-time monitoring, sensing and acquisition the inf

5、ormation of various environmental monitoring or targeting object within regional of distribution networks. Such information will be processed and transmitted to the user. Wireless sensor networks are widely used in military, industrial, transportation, security, medical, detection, family and office

6、 environment. The research, development and application of it relates to national security, economic development and other important fields. In recent years the wireless sensor networks have been caused much attention and investment. External uncertainty environment often leads to hundreds of sensor

7、s shall be deploymented to work together, so the large-scale sensor networks research is gradually aroused widespread interest and considered a challenging research topic of this century. Against the above problems, the academic research mainly concentrated in the sensor clustering algorithm, commun

8、ications routing protocols, network coverage and sensor data fusion technology.LEACH algorithm is a typical level routing algorithm. This algorithm put forward a continued operation of low-power model. But LEACH algorithm did not consider the problem of energy consumption and topology of the sensor.

9、 This paper presents an energy efficient clustering algorithm in sensor network. On the basis of the classical LEACH algorithm, through the introduction of average energy consumption adjustable parameters and density adjustment parameters. The new algorithm enable the nodes which near the geographic

10、 center of the cluster structure or in the node-intensive region has a higher probability to be a cluster head. And it also takes into account both the choice of the cluster heads location and the size of the network, then further optimizes the structure of the cluster, balances energy consumption,

11、elects more reasonable cluster head which makes the life cycle of sensor networks has a larger extension on the basis of in LEACH algorithm.Key Words: Sensor networks; Clustering Algorithms; The average energy consumption; Node Density目 录1. 绪论11.1 课题研究背景与意义11.2 国内外研究现状21.3论文结构和研究内容31.4 小结32. 传感器网络概述

12、42.1 传感器网络简介42.1.1 传感器网络的概念42.1.2 传感器网络的特点52.1.3 传感器网络的核心技术62.2 传感器网络的应用62.2.1 环境的检测和保护62.2.2 医疗护理72.2.3 其他应用72.3传感器网络的特点与挑战82.4小结93. LEACH算法简介及分析103.1引言103.2 LEACH算法103.3 LEACH算法中存在的问题分析123.3.1 未考虑簇头在簇结构中位置时存在的问题123.3.2 频繁动态拓扑变换带来的问题153.4 小结164. 能量有效的分布式簇头选取算法174.1引言174.2 EECHS算法174.3算法性能分析184.4小结2

13、05. 算法仿真实验215.1实验平台215.2实验设计215.3实验过程225.4实验结果245.5小结26结 论27致 谢29参考文献30附录A 部分源程序321. 绪论1.1 课题研究背景与意义随着通讯技术，计算机技术和传感技术的日益成熟，微型传感器在世界范围内广泛出现。传感器网络的发展经历了几个阶段，它最早出现在二十世纪七十年代，这个时期的传感器网络具有点对点的传输能力和简单的信息获取能力。随后便出现了使用串/并接口与传感器连接，可以获取多种信息的传感器网络。到了二十世纪九十年代后期，智能传感器采用现场总线连接形成局域网络。随着无线通讯技术被引入传感器，传感器网络技术的发展和应用发生了

14、革命性的变化，以无线传感器网络为标志的全新的传感器网络研究领域，在基础理论和工程技术两个层面向科技工作者提供了大量的具有挑战性的课题1-6。由于传感器网络的巨大应用价值，它已经引起了世界许多国家的军事部门、工业界和学术界的极大关注。美国自然科学基金委员会2003年制定计划并投巨资支持传感器网络相关基础理论的研究。美国国防部和各军事部门把传感器网络作为一个重要研究领域，设立了一系列的军事传感器网络研究项目7。主要的信息工业界巨头也开始了传感器网络方面的工作，纷纷设立或启动相应的行动计划。其它一些国家也对传感器网络表现出了极大的兴趣，并纷纷展开了在该领域的研究工作。由于传感器网络具有异于MANET

15、的独特性质13，因此传统MANET协议不适用于传感器网络，需要为传感器网络研究新的有效的路由算法。目前，在传感器网络的路由算法研究中，鉴于传感器网络中节点稠密分布、节点的能量、存储及数据处理能力十分有限的特性，一般采用基于分簇的方法来进行路由算法设计，以提高路由算法的性能。分簇算法作为路由协议的研究基础，对路由算法性能的优劣具有重要的影响。此外，在传感器网络中，要保障信息的完整性，数据汇聚节点首先要判定该感兴趣的区域是否被一组给定的传感器节点覆盖，覆盖问题也因此被看作是衡量传感器网络服务质量(Quality Of Service)的一种标准10。而覆盖算法也是以分簇算法为基础进行研究的。由于为

16、改善传感器网络的服务质量而提出的许多覆盖算法是以分簇算法作为其研究基础的，因此分簇算法的改进可以极大的促进覆盖算法的性能。综上所述，本文研究传感器网络中能量有效的分簇算法，具有重要的理论意义与实用价值。1.2 国内外研究现状由于外界环境的不确定性经常导致需要布置成百上千的传感器协同工作，故对由大规模传感器构成的传感器网络的研究正逐渐引起广泛关注，并被认为是本世纪的一向具有挑战性的研究课题。针对以上问题，学术界的研究热点主要集中在传感器分簇算法、通信路由协议、传感器网络覆盖以及传感器数据融合技术上的研究上。传感器分簇算法通常包括两个阶段。第一个阶段是根据一定的机制算法选取某个接点作为簇头，用于管

17、理或控制整个簇内成员节点，协调成员节点之间的工作，负责簇内信息的收集和数据的融合处理以及簇间转发。第二个阶段是在选取簇头的基础上，选取具有某种关联的网络节点形成集合，也就是成簇。在成簇算法中，网络通常被划分为簇（Cluster）。每个簇由一个簇头（Cluster Head）和多个簇内成员（Cluster Member）组成，由簇头与基站BS（Base Station）通信。网络分布如图1所示，图1.1簇集网络示意图1、 簇头选取算法 簇头的产生是簇形成的基础，在一些算法中，比如Max-min Zpmin，簇头是被预先指定部署的，且假设它们的能量并不受限。但这是理想的情况，在实际应用是不可能实现

18、的。更多的簇头选取算法综合考虑了节点的剩余能量，簇头到基站的距离，簇内通信代价等问题。目前提出的主流簇头选取算法有LEACH、LEACH-F、DAEA、HEAD、CEFL、DCHS、DEFG等。2、 成簇算法成簇算法在簇头产生后，形成簇的拓扑结构，将网络划分成相连的区域。良好的簇拓扑结构有助于延长传感器网络的使用周期。目前提出的成簇算法有ACMWN、HYENAS、EECS、PEGASIS、GAF、ACE、FBCC等。1.3 论文结构和研究内容目前，人们基于节能的考虑已提出了各种各样的路由协议，本文对其中的LEACH算法进行分析，主要研究内容如下：(1) 详细分析了LEACH的簇头选取以及成簇算

19、法，并对LEACH在簇头选取和成簇过程中存在的问题进行了说明。(2) 针对LEACH算法在簇头选取过程中没有考虑簇头在簇结构中位置和没有考虑节点实际部署情况而引发的问题，将基于节点平均能耗的簇头选取算法和节点密度数学模型结合起来，提出了能量有效簇头选取算法。(3) 对算法进行仿真实验，并借鉴传感器网络中节能评价指标体系对实验结果进行质量评价，最后本文通过理论分析和大量实验证明了新算法较LEACH算法性能更优越。论文主要由以下部分构成：第一章对本课题背景和国内外研究现状做了描述。第二章对传感器网络的概念以及应用进行介绍。第三章对传统的LEACH算法进行了介绍，并详细分析了其存在的不足。第四章将节

20、点密度模型和平均能耗模型结合起来，进一步对LEACH算法的簇头选取过程进行改进，提出了能量有效的簇头选取算法。第五章对算法进行仿真模拟实验。最后为结论与展望，首先本文工作进行了总结，然后对下一步的研究方向进行了展望。1.4 小结本章首先给出了课题的研究背景与意义、然后综述了国内外传感器网络覆盖判定算法的研究现状、最后，给出了论文的结构和研究内容简介。2. 传感器网络概述2.1 传感器网络简介2.1.1 传感器网络的概念传感器网络是由一组传感器以Ad-Hoc方式构成的有线或无线网络，其目的是协作地感知、采集和处理网络覆盖的地理区域中感知对象的信息，并发布给观察者。从定义可以看出，传感器、感知对象

21、和观察者是传感器网络的3个基本要素；有线或无线网络是传感器之间、传感器与观察者之间的通信方式，用于在传感器与观察者之间建立通信路径；协作地感知、采集、处理、发布感知信息是传感器网络的基本功能。一组功能有限的传感器协作地完成大的感知任务是传感器网络的重要特点。传感器网络中的部分或全部节点可以移动。传感器网络的拓扑结构也会随着节点的移动而不断地动态变化。节点间以Ad-Hoc方式进行通信，每个节点都可以充当路由器的角色，并且每个节点都具备动态搜索、定位和恢复连接的能力。传感器由电源、感知部件、嵌入式处理器、存储器、通信部件和软件这几部分构成（如图2.1所示）。电源为传感器提供正常工作所必需的能源。感

22、知部件用于感知、获取外界的信息，并将其转换为数字信号。处理部件负责协调节点各部分的工作。通信部件负责与其他传感器或观察者的通信。软件则为传感器提供必要的软件支持，如嵌入式操作系统、嵌入式数据库系统等。图2.1 传感器示意图典型的传感器网络由传感器节点、接收发送器(sink)、Internet或通信卫星、任务管理节点等部分构成。传感器节点散布在指定的感知区域内，每个节点都可以收集数据，并通过“多跳”路由方式把数据传送到Sink。Sink也可以用同样的方式将信息发送给各节点。Sink直接与Internet或通信卫星相连，通过Internet或通信卫星实现任务管理节点(即观察者)与传感器之间的通信。

23、图2.2描述了一个典型的传感器网络的结构14。2.2典型的传感器网络的结构2.1.2 传感器网络的特点传感器网络除了具有Ad-Hoc网络的移动性、断接性、电源能力有限等特征外，还具有以下鲜明特点14：(1) 通信能力有限。传感器网络中的传感器的通信带宽较窄而且经常变化，通信覆盖范围只有几十到几百米。传感器之间的通信断接频繁，经常导致通信失败。由于传感器网络更多地受到高山、建筑物、障碍物等地势地貌以及风雨雷电等自然环境的影响，传感器可能会长时间离线工作。(2) 计算能力有限。传感器网络中的传感器都具有嵌入式处理器和存储器。这些传感器都具有计算能力，可以完成一些信息处理工作。但是，由于嵌入式处理器

24、和存储器的能力和容量有限，传感器的计算能力十分有限。使用大量具有有限计算能力的传感器进行协作分布式信息处理，是我们的选择之一。(3) 传感器数量大、分布范围广。传感器网络中传感器节点密集，数量巨大，可能达到几百、几千万，甚至更多。此外，传感器网络可以分布在很广泛的地理区域。传感器的数量与用户数量比通常也非常大。这就要求传感器网络的软、硬件必须具有高强壮性和容错性。(4) 感知数据流巨大。传感器网络中的每个传感器通常都产生较大的流式数据，并具有实时性。每个传感器仅仅具有有限的计算资源，难以处理巨大的实时数据流。这就需要研究强有力的分布式数据流管理、查询、分析和挖掘方法。2.1.3 传感器网络的核

25、心技术以数据为中心的传感器网络的基本思想是：把传感器视为感知数据流或感知数据源，把传感器网络视为感知数据空间或感知数据库，把数据管理和处理作为网络的应用目标。传感器网络以数据为中心的特点使得其设计方法不同于其他计算机网络(包括Internet)。传感器网络的设计必须以感知数据管理和处理为中心，把数据库技术和网络技术紧密结合，从逻辑概念和软、硬件技术两个方面实现一个高性能的以数据为中心的网络系统，为用户或观察者提供一个有效的感知数据空间或感知数据库管理和处理系统，使用户如同使用通常的数据库管理系统和数据处理系统一样自如地在传感器网络上进行感知数据的管理和处理。感知数据管理与处理技术是实现以数据为

26、中心的传感器网络的核心技术17。感知数据管理与处理技术包括感知网络数据的存储、查询、分析、挖掘、理解以及基于感知数据决策和行为的理论和技术。传感器网络的各种实现技术必须与这些技术密切结合，融为一体，而不是像目前其他网络设计那样分而治之。只有这样才能够设计实现高效率的以数据为中心的传感器网络系统。对感知数据管理与处理的研究方向主要包括：感知数据管理技术的研究、感知数据查询处理技术的研究、感知数据分析技术的研究、感知数据挖掘技术的研究以及感知数据管理系统的研究。2.2 传感器网络的应用2.2.1 环境的检测和保护随着人们对于环境问题的关注程度越来越高，需要采集的环境数据也越来越多，无线传感器网络的

27、出现为随机性的研究数据获取提供了便利，并且还可以避免传统数据收集方式给环境带来的侵入式破坏。比如，2002年英特尔研究实验室研究人员曾经将32个小型传感器连进互联网，掌握缅因州大鸭岛上的气候，以此评价一种海燕巢的条件。2003年第二季度，他们换用150个安有D型微型电池的第二代传感器，来评估这些鸟巢的条件。另外，无线传感器网络可以跟踪候鸟和昆虫的迁移，研究环境变化对农作物的影响，监测海洋、大气和土壤的成分等。它也可以应用在精细农业中，来监测农作物中的害虫、土壤的酸碱度和施肥状况等。2.2.2 医疗护理无线传感器网络在医疗研究、护理领域同样可以大展身手。它可以用于病区移动查房、床边护理、呼叫通信

28、、护理监控、药库管理等方面。罗彻斯特大学的科学家使用无线传感器创建了一个智能医疗房间，使用微尘来测量居住者的重要征兆（血压、脉搏和呼吸）、睡觉姿势以及每天24小时的活动状况。英特尔公司也推出了无线传感器网络的家庭护理技术。该技术是作为探讨应对老龄化社会的技术项目Center for Aging Services Technologies（CAST）的一个环节开发的18。该系统通过在鞋、家具以家用电器等家中道具和设备中嵌入半导体传感器，帮助老龄人士、阿尔茨海默氏病患者以及残障人士的家庭生活。利用无线通信将各传感器联网可高效传递必要的信息从而方便接受护理。而且还可以减轻护理人员的负担。英特尔主管预

29、防性健康保险研究的董事Eric Dishman称，“在开发家庭用护理技术方面，无线传感器网络是非常有前途的领域”。2.2.3 军事领域由于无线传感器网络具有密集型、低成本、随机分布的节点组成，自组织性和容错能力使其非常适合应用于恶劣的战场环境中，包括侦察敌情、监控兵力、装备和物资，判断生物化学攻击等多方面用途1。美国国防部远景计划研究局已投资几千万美元，帮助大学进行智能尘埃传感器技术的研发。哈伯研究公司总裁阿尔门丁格预测：智能尘埃式传感器及有关的技术销售将从2004年的1000万美元增加到2010年的几十亿美元。 2.2.3 其他应用无线传感器网络还被应用于其他一些领域。比如一些危险的工业环境

30、如井矿、核电厂等，工作人员可以通过它来实施安全监测。也可以用在交通领域作为车辆监控的有力工具。此外和还可以在工业自动化生产线等诸多领域，英特尔正在对工厂中的一个无线网络进行测试，该网络由40台机器上的210个传感器组成，这样组成的监控系统将可以大大改善工厂的运作条件。它可以大幅降低检查设备的成本，同时由于可以提前发现问题，因此将能够缩短停机时间，提高效率，并延长设备的使用时间。尽管无线传感器技术目前仍处于初步应用阶段，但已经展示出了非凡的应用价值，相信随着相关技术的发展和推进，一定会得到更大的应用。无线传感器网络有着十分广泛的应用前景，它不仅在工业、农业、军事、环境、医疗等传统领域有具有巨大的

31、运用价值，在未来还将在许多新兴领域体现其优越性，如家用、保健、交通等领域。我们可以大胆的预见，将来无线传感器网络将无处不在，将完全融入我们的生活。比如微型传感器网络最终可能将家用电器、个人电脑和其他日常用品同互联网相连，实现远距离跟踪。家庭采用无线传感器网络负责家电协同工作，进行安全调控，并且可以节省电能。另外，用户可以根据自己的个人喜好，可以利用传感器网络设置智能生活环境，如依据传感器检测数据来调节室内光线强度、音乐声音，以形成惬意的房间氛围。无线传感器网络将是未来的一个无孔不入的十分庞大的网络，其应用可以涉及到人类日常生活和社会生产活动的所有领域。2.3传感器网络的特点与挑战传感器网络除了

32、具有Ad-Hoc网络的移动性、断接性、电源能力局限等共同特征以外，还具有很多其他鲜明的特点。这些特点向我们提出了一系列挑战性问题14：(1)通信能力有限。传感器网络的传感器的通信带宽窄而且经常变化，通信覆盖范围只有几十到几百米。传感器之间的通信断接频繁，经常导致通信失败。由于传感器网络更多地受到高山、建筑物、障碍物等地势地貌以及风雨雷电等自然环境的影响，传感器可能会长时间脱离网络，离线工作。 (2)电源能量有限。传感器的电源能量极其有限。网络中的传感器由于电源能量的原因经常失效或废弃。电源能量约束是阻碍传感器网络应用的严重问题。商品化的无线发送接收器电源远远不能满足传感器网络的需要。传感器传输

33、信息要比执行计算更消耗电能.传感器传输1位信息所需要的电能足以执行3000条计算指令。(3)计算能力有限。传感器网络中的传感器都具有嵌入式处理器和存储器。这些传感器都具有计算能力，可以完成一些信息处理工作。但是，由于嵌入式处理器和存储器的能力和容量有限，传感器的计算能力十分有限。如何使用大量具有有限计算能力的传感器进行协作分布式信息处理，是我们面临的第3个挑战。(4)传感器数量大、分布范围广。传感器网络中传感器节点密集，数量巨大，可能达到几百、几千万，甚至更多。此外，传感器网络可以分布在很广泛的地理区域。传感器的数量与用户数量比通常也非常大。传感器数量大、分布广的特点使得网络的维护十分困难甚至

34、不可维护，传感器网络的软、硬件必须具有高强壮性和容错性。(5)网络动态性强。传感器网络具有很强的动态性。网络中的传感器、感知对象和观察者这三要素都可能具有移动性，并且经常有新节点加入或已有节点失效。因此，网络的拓扑结构动态变化，传感器、感知对象和观察者三者之间的路径也随之变化。传感器网络必须具有可重构和自调整性。(6)大规模分布式触发器。很多传感器网络需要对感知对象进行控制，如温度控制。这样，很多传感器具有回控装置和控制软件。(7)感知数据流巨大。传感器网络中的每个传感器通常都产生较大的流式数据，并具有实时性。每个传感器仅仅具有有限的计算资源，难以处理巨大的实时数据流。这就需要研究强有力的分布

35、式数据流管理、查询、分析和挖掘方法。2.4小结本章首先给出了传感器网络的定义、特点以及传感器网络管理核心技术的描述，然后，简要介绍了传感器网络的应用领域，最后，简述了当前传感器网络研究中所面临的挑战。3. LEACH算法简介及分析3.1引言未来的计算装置将越来越与环境融于一体，直至它们对于用户是不可见的。而分布式无线传感器网络正是这一思想的重要体现。不断小型化是微型传感器的设计目标，而传感器的能源供应则是传感器小型化过程中最主要的限制。 传统的能量供应装置是电池，然而缩小电池的体积，增加电池容量的工程技术发展缓慢，这直接影响了无线传感器网络的发展。无法从能量存储的硬件设备上获得突破，于是科研人

36、员开始寻求延长传感器网络使用寿命的其它途径。这就是通过各种优化应用，完善操作系统和通信协议来降低网络的能量消耗，从而在总能量不变的情况下增加传感器网络的使用时间。在上述背景下，各种有关传感器网络的路由算法和通信协议纷纷被提出，其中 Heinzelman 等人提出的LEACH算法是最具代表性和里程碑意义的。3.2 LEACH算法 LEACH算法是一种典型的层次路由算法。相比较平面路由算法而言，LEACH算法具有以下的优点： 成员节点大部分时间可以关闭通信模块，由簇头构成一个更上一层的连通网络来负责数据的长距离路由转发。这样既保证了原有覆盖范围内的数据通信，也在很大程度上节省了网络能量。 簇头融合

37、了成员节点的数据之后再进行转发，减少了数据通信量，降低了数据冗余，在节省了通讯能量的同时也降低了传感器网络在数据计算方面的能量开销。 成员节点的功能比较简单，无须维护复杂的路由信息。这大大减少了网络中路由控制信息的数量，减少了通信量。 分簇拓扑结构便于管理，有利于分布式算法的应用，可以对系统变化作出快速反应，具有较好的可扩展性，适合大规模网络。 LEACH算法首先作了如下的假设： 基站(BS)远离传感器网络节点并且是稳定的。 传感器网络中的所有节点是同构的，并且能量都受到限制。 所有节点可以直接和基站通讯。 节点都没有位置信息。 簇头节点负责数据压缩汇聚以及与基站进行通讯。 该算法主要通过随机

38、选择簇首领，平均分担中继通信业务来实现节能。同时LEACH 定义了“轮”(Round)的概念，针对每个节点n设定了一个阀值T(n)： (2.1)式(2.1)中p表示簇头节点占网络节点总数的百分比，r表示重新挑选簇头节点的轮数，G表示网络中最近1/p轮未当选簇头的节点的集合。并根据该阀值从候选节点中挑选簇头，具体的步骤： Step1： 若传感器节点NiG，则对于每个Ni独立运算(2.1)式，获得阀值T(n)。Step2： 若Ni不属于G，则根据(2.1)式，T(n)为零。Step3： Ni产生一个01之间的随机数RadomNum。Step4： 若T(n)RadomNum，则该节点当选为簇头，并广

39、播当选消息。Step5： 其余节点选择加入某簇头所在的簇，形成稳定的拓扑结构。Step6： 稳定工作阶段。Step7： 每隔时间t，进行下一轮簇头选取，转Step1，重新选择簇头并成簇。 由以上步骤可知LEACH算法中的轮是指两次簇头选取之间的时间段，每一轮由初始化和稳定工作两个阶段组成。在初始化阶段，随机选择节点为簇首领，成为簇首领的节点向周围广播信息，其它节点根据接受到广播信息的强度来选择它所要加入的簇，并告知相应的簇首领，由于信息的强度和节点之间的距离是成正比的，因此，实际上各非簇头节点是选择距离自己地理距离最短的簇头所在的簇加入，并形成簇拓扑结构，如图3.1所示：图3.1 成簇阶段图

40、传感器网络首先产生中心节点，其余节点加入距离自己最近的中心节点所在的簇，然后由中心节点直接和SINK节点进行通讯。在稳定工作阶段，节点持续采集监测数据，传送到簇头，由簇头对数据进行必要的融合处理之后，发送到终端节点。每轮工作周期结束后，重新选择簇头并重复前面的工作。3.3 LEACH算法中存在的问题分析 在上述的LEACH算法描述中，我们仔细思考，不难发现其中存在着以下的诸多问题。(1) 算法没有考虑簇头节点在簇结构中的位置对簇头能耗的影响。在簇头选取的过程中，位于簇中心位置的节点和位于簇边缘位置的节点成为簇头的机率是一样的。由于位于簇边缘位置的簇头其通讯能耗远大于位于簇中心位置的簇头，因此将

41、导致各簇头能耗不均衡，使某些簇头节点能量提前耗尽。 (2) LEACH没有考虑到传感器网络在进行部署的时候，节点分布密度对簇头能耗的影响。由此导致在传感器节点密集分布区域的簇头能耗巨大，而在传感器节点稀疏分布区域的簇头能耗较小，网络中各簇头的能耗极不均衡。(3) 动态分簇引起网络拓扑结构频繁变换和大量广播通信，从而带来了额外的能量开销。3.3.1 未考虑簇头在簇结构中位置时存在的问题为指出未考虑簇头在簇结构中位置时LEACH算法中存在的问题，首先假定通过飞机播撒等方式部署的传感器网络中已经形成了若干个簇。其中有某个簇由5个传感器节点构成，且簇中各节点A，B，C，D，E的初始能量均为40，该簇的

42、5个传感器节点的具体分布情况如图3.2所示。图3.2 具有5个节点的传感器网络为计算方便，且假定簇中各节点A，B，C，D，E两两之间的距离如表2.1所示：表3.1 图2.2中节点A,B,C,D,E两两间的距离距离ABCDEA01243B10364C23032D46303E34230假定在每轮通信中，各簇成员分别发送一次数据给簇头，则每轮通信中各节点的工作能耗如表2.2所示： 表3.2 A,B,C,D,E分别为簇头时各节点的工作能耗簇头/能耗ABCDEA102486B2146128C461064D8126166E684612基于式(2.1)可知：采用LEACH算法时整个网络的生命周期可能如表2.

43、3所示：表3.3 采用LEACH算法时整个网络的生命周期簇头/剩余能量ABCDE第1轮：A为簇头3038363234第2轮：B为簇头2824302026第3轮：C为簇头2418201422第4轮：D为簇头16614-216显然，采用LEACH算法时，整个网络的生命周期将小于4轮。从上面的分析不难看出，LEACH算法进行第四轮簇头选取时，没有考虑到节点的剩余能量及其工作能耗，导致剩余能量小于工作能耗的节点D当选为簇头，使节点D的能量过早衰竭，网络的生命周期也随之结束。若结合考虑节点的位置信息，使靠近簇结构中心位置且剩余能量较多的节点有更多机会成为簇头，无疑将有效延长网络的生命周期。3.3.2 未

44、考虑节点分布密度时存在的问题为考虑节点分布密度对网络生命周期的影响，给出一个具有8个节点的传感器络，如图2.3所示。图3.3 具有8个节点的传感器网络 假定各节点的初始能量均为20，各节点簇内通讯半径为10。其中D，F，H三个节点为最近1/p轮未当选簇头的节点。网络中各节点A，B，C，D，E，F，G，H两两之间的距离如表2.4所示：表3.4 图2.3中节点A,B,C,D,E,F,G,H两两间的距离距离ABCDEFGHA0584791114B50449101313C8404761111D4440671012E797604611F910674058G111311106506H14131112118

45、60根据LEACH算法，则有可能出现以下的成簇情况，各种情况下簇头的能量消耗如表2.5所示。由表2.5知，显然在第2种情形下，即当D，F当选为簇头时，簇头节点的工作能耗最接近均衡。因此，应尽可能使密集分布区域中的节点比稀疏分布区域中的节点具有更大当选为簇头的概率(即让D，F当选为簇头的概率最大化)，使得密集分布区域比稀疏分布区域产生更多簇头，并且每个簇中成员节点数目大致相同，各簇头的工作能耗也相对均衡。表3.5 图2.3中节点当选簇头的能耗情况序号簇头选取情形簇头簇成员当选簇头工作能耗1F当选为簇头FA，B，C，D，E，G，H492D，F均当选为簇头DA，B，C12FE，G，H173D，H均当选为簇头DA，B，C，E，F25HG64F，H均当选为簇头FA，B，C，D，E，G49H无05D，F，H均当选为簇头DA，B，C12FE，G9H无03.3.3 频繁动态拓扑变换带来的问题由于传感器网络在使用LEACH算法的时候存在轮的概念，并且每轮结束后，都要重新产生新的簇头节点，然后围绕这些簇头再产生新的簇。这使得传感器网络的拓扑结构是动态变化的，并且为了维持这种拓扑结构的动态性，必须要耗费大量的能量进行计算和通讯。下面对LEACH算法每轮动态成簇耗费的能量和簇结构稳定阶段