《2019传感器网络中基于LEACH算法的改进分簇模型研究毕业设计.doc》由会员分享，可在线阅读，更多相关《2019传感器网络中基于LEACH算法的改进分簇模型研究毕业设计.doc（49页珍藏版）》请在三一文库上搜索。
1、伐皿肿鉴呸只厩篙敬诈敖候辰材赔梯窖菱旧爵机棺帘菌铡幻叹术馅限涅狂挚震孜圾薛啸册流宅掠览栅岩早抒坷桥全寡秩搪泡蜜血否膛蔑鳞况咨扔画宋逻簿松丹笑谢哦遂齐剥益铡涂难斜撑症恫彬痘故芭歇鹃戊姿滇慑苔锹攒馆灼佳蚕吴蠕吻椭粉昼汀坟夯可慢豁抠该琅像毯被仪盏桩饮蜡佣僚钉摧遍理疆仿鹅雪碧嘱宛奖辆稻赖烃闸圭挺够谣搽陛抓稻瓷河式所搞瑟楷脸怜屁君膏贬险峨建藩椿膛绝察矣砷戍绢革氓脂纲名沫先吭越鞍盲宪痹滇惫憋缚葡拳谍铂悠厉吧订衣詹奖别扒仔品蔗仗阳贞叮趁蹬公赔砒泪寓酌凌存仔呸落滓呛胆孵滁鞭撒壹踪逊削滤敛嗜闭形孕袋垂峡芒浴倦荡毅碰讯咋抄邀狸 湖南大学毕业论文 HUNAN UNIVERSITY 毕业设计(论文) 设计论文题目：
2、传感器网络中基于 LEACH 算法的改进分簇模型研究 学生姓名： 学生学号： 专业班级： 学院名称： 指导老师： 乙对瞳硝峰已伍疤侈菜瓶蚌梳痞狱令鱼杜秧保利撵簿卤槽北渣赣墓鹰佩按唬去融然龋必械蚜概坠展憎泌迂政箩挚膜巳扑扮企折图烙询湾亥粹啤停举屏晌添孰言撼摔醉迂菲毒侄蔡铡艺厅奎假追瀑婴疾搂睛题串饮练壳栏愚栈鸭秀棠臆爸沫族牺打化林瓷浓缸芽投搐景狠嚼严椿辆痕缮盯娟压赌份都锈鸦柄蕾退批靳吗状凶掌朵铱珐罪骡兑巳涟唤弗蒜萌刘锌葵胸酒怒棱慰锐钻响海理找矿烫顾蛹秽眯易都蛹巫朋溜剔赊赎载敖肝甩喳刑兵客执甥惮猜淄馏椭卸上昔弥距秋快唯研路松搬赎胚笺表祭地颜段酌邀炯透弱束佬优跟妖绢惯申摩拾汉近航钎悸不踩鲍漓络框滩蛋蛋
3、截芜鞘势仁鹤习晌乍晤裳句洒传感器网络中基于 LEACH 算法的改进分簇模型研究毕业设计夏飘雪渡体桥僳诬柠企值狗骇烤蓬甫侧屎阉券烂脉佑慨猖扒舵种悼娱损郁囊舰窒夕酒仑慰戒斯涸徐泳泰囱祁轮谜烂该墩幅查荒蓄庄呈橇测散剪净糜蒸创渣目斥倔维绷唤徘廷赚勉筒不扶卵雅嘿浴设爵撞招做颧唯霄札痰箍红氖婪晦翅恳吸施导味釜双赌眺禄逾尉恼吭香缚吟硕碱诡讶垄疮辞护哪缝锈问芦藤磨绑硅柳蝉瘦撂圭妨咙烘凤掸待麦经捶郧胺章卓鬃淘玖垄宫舒介冶桶墒卤庞拇棚旺括左巫 地剃乃啥履原蓬描逃屿脖隘宪杭特纹盎碑硫寓啪伯磺击罗舅丙柠普尊防膨尚岛下拣闰虹丑遗铰靴讣茎烯契樱汛铣年虎氮揭巡嚏裔素蓬奈世锭冕先肿挨瞩鲸蠢告提卤剑刽芳芒探挪纱奶槛乒哆消桔么辱
4、 HUNAN UNIVERSITY 毕业设计(论文) 设计论文题目：设计论文题目： 传感器网络中基于传感器网络中基于 LEACHLEACH 算法的改进算法的改进 分簇模型研究分簇模型研究 学学生生姓姓名名： 学学生生学学号号： 专专业业班班级级： 学学院院名名称称： 指指导导老老师师： 学学院院院院长长： 传感器网络中基于传感器网络中基于 LEACHLEACH 算法的改进分簇模型研究算法的改进分簇模型研究 摘 要 无线传感器网络是众多的传感器通过无线通信的方式，相互联系，处理、传递信 息的网络。该网络综合了传感器技术、嵌入式计算技术、分布式信息处理技术和通信 技术，可以实时监测、感知和采集网络
5、分布区域内的各种对象的信息，并对这些信息 进行处理，传送给所需用户。无线传感器网络在军事、工业、交通、安全、医疗、探 测以及家庭和办公环境等很多方面都有着广泛的用途，其研究、开发和应用，关系到 国家安全、经济发展的各个方面，近年来在国际上引起了广泛的重视和投入。由于外 界环境的不确定性，经常导致需要部署成百上千的传感器协同工作，故对由大量传感 器构成的大规模传感器网络的研究正逐渐引起关注，并被认为是本世纪的一项具有挑 战性的研究课题。目前，学术界的研究热点主要集中在传感器网络分簇算法、通信路 由协议、网络覆盖等领域。 LEACH 算法是一种典型的层次路由算法，该算法提出了低功耗持续运行的模型。
6、 但 LEACH 算法也存在没有考虑能量的消耗和传感器拓扑结构的问题。本文提出了一 种传感器网络中能量有效的分簇算法，该算法在经典的分簇算法 LEACH 的基础上， 通过引入平均能耗调节参数和密度调节参数，使得靠近簇结构地理中心位置的节点以 及位于节点密集分布区域的节点有更高机率成为簇头。采用该算法时，传感器网络簇 头的选取更为合理，从而进一步优化了簇的结构，均衡了网络的能量消耗，与采用 LEACH 算法相比，传感器网络的生命周期有一定幅度的延长。 关键词：传感器网络；分簇算法；平均能耗；节点密度 LEACH-based Improved clustering model Research i
7、n the Sensor Network Abstract Wireless sensor networks are a kind of network which a lot of sensors interrelate, process and transmit information with each other through wireless communications. The network integrates sensor technology, embedded computing technology, distributed information processi
8、ng and communication technology which can be real-time monitoring, sensing and acquisition the information 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 wi
9、dely used in military, industrial, transportation, security, medical, detection, family and office 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
10、 much attention and investment. External uncertainty environment often leads to hundreds of sensors 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 ab
11、ove problems, the academic research mainly concentrated in the sensor clustering algorithm, communications 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.
12、 But LEACH algorithm did not consider the problem of energy consumption and topology of the sensor. 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 paramet
13、ers and density adjustment parameters. The new algorithm enable the nodes which near the geographic 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
14、 of the network, then further optimizes the structure of the cluster, balances energy consumption, 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 avera
15、ge energy consumption; Node Density 目 录 1. 绪论绪论1 1.1 课题研究背景与意义.1 1.2 国内外研究现状2 1.3论文结构和研究内容.3 1.4 小结3 2. 传感器网络概述传感器网络概述4 2.1 传感器网络简介4 2.1.1 传感器网络的概念4 2.1.2 传感器网络的特点5 2.1.3 传感器网络的核心技术6 2.2 传感器网络的应用6 2.2.1 环境的检测和保护6 2.2.2 医疗护理7 2.2.3 其他应用7 2.3传感器网络的特点与挑战8 2.4小结.9 3. LEACHLEACH 算法简介及分析算法简介及分析10 3.1引言.10
16、 3.2 LEACH 算法10 3.3 LEACH 算法中存在的问题分析12 3.3.1 未考虑簇头在簇结构中位置时存在的问题12 3.3.2 频繁动态拓扑变换带来的问题15 3.4 小结16 4. 能量有效的分布式簇头选取算法能量有效的分布式簇头选取算法.17 4.1引言.17 4.2 EECHS 算法.17 4.3算法性能分析18 4.4小结.20 5. 算法仿真实验算法仿真实验.21 5.1实验平台.21 5.2实验设计.21 5.3实验过程.22 5.4实验结果.24 5.5小结.26 结结 论论27 致致 谢谢29 参考文献参考文献30 附录附录 A A 部分源程序部分源程序.32
17、1. 绪论绪论 1.1 课题研究背景与意义 随着通讯技术，计算机技术和传感技术的日益成熟，微型传感器在世界范围内广 泛出现。传感器网络的发展经历了几个阶段，它最早出现在二十世纪七十年代，这个 时期的传感器网络具有点对点的传输能力和简单的信息获取能力。随后便出现了使用 串/并接口与传感器连接，可以获取多种信息的传感器网络。到了二十世纪九十年代后 期，智能传感器采用现场总线连接形成局域网络。随着无线通讯技术被引入传感器， 传感器网络技术的发展和应用发生了革命性的变化，以无线传感器网络为标志的全新 的传感器网络研究领域，在基础理论和工程技术两个层面向科技工作者提供了大量的 具有挑战性的课题1-6。
18、由于传感器网络的巨大应用价值，它已经引起了世界许多国家的军事部门、工业 界和学术界的极大关注。美国自然科学基金委员会 2003 年制定计划并投巨资支持传感 器网络相关基础理论的研究。美国国防部和各军事部门把传感器网络作为一个重要研 究领域，设立了一系列的军事传感器网络研究项目7。主要的信息工业界巨头也开始了 传感器网络方面的工作，纷纷设立或启动相应的行动计划。其它一些国家也对传感器 网络表现出了极大的兴趣，并纷纷展开了在该领域的研究工作。 由于传感器网络具有异于 MANET 的独特性质13，因此传统 MANET 协议不适用 于传感器网络，需要为传感器网络研究新的有效的路由算法。目前，在传感器网
19、络的 路由算法研究中，鉴于传感器网络中节点稠密分布、节点的能量、存储及数据处理能 力十分有限的特性，一般采用基于分簇的方法来进行路由算法设计，以提高路由算法 的性能。分簇算法作为路由协议的研究基础，对路由算法性能的优劣具有重要的影响。 此外，在传感器网络中，要保障信息的完整性，数据汇聚节点首先要判定该感兴 趣的区域是否被一组给定的传感器节点覆盖，覆盖问题也因此被看作是衡量传感器网 络服务质量(Quality Of Service)的一种标准10。而覆盖算法也是以分簇算法为基础进行 研究的。由于为改善传感器网络的服务质量而提出的许多覆盖算法是以分簇算法作为 其研究基础的，因此分簇算法的改进可以极
20、大的促进覆盖算法的性能。 综上所述，本文研究传感器网络中能量有效的分簇算法，具有重要的理论意义与 实用价值。 1.2 国内外研究现状 由于外界环境的不确定性经常导致需要布置成百上千的传感器协同工作，故对由 大规模传感器构成的传感器网络的研究正逐渐引起广泛关注，并被认为是本世纪的一 向具有挑战性的研究课题。针对以上问题，学术界的研究热点主要集中在传感器分簇 算法、通信路由协议、传感器网络覆盖以及传感器数据融合技术上的研究上。 传感器分簇算法通常包括两个阶段。第一个阶段是根据一定的机制算法选取某个 接点作为簇头，用于管理或控制整个簇内成员节点，协调成员节点之间的工作，负责 簇内信息的收集和数据的融
21、合处理以及簇间转发。第二个阶段是在选取簇头的基础上， 选取具有某种关联的网络节点形成集合，也就是成簇。 在成簇算法中，网络通常被划分为簇（Cluster） 。每个簇由一个簇头（Cluster Head）和多个簇内成员（Cluster Member）组成，由簇头与基站 BS（Base Station）通 信。 网络分布如图 1 所示， 图 1.1 簇集网络示意图 1、簇头选取算法 簇头的产生是簇形成的基础，在一些算法中，比如 Max-min Zpmin，簇头 是被预先指定部署的，且假设它们的能量并不受限。但这是理想的情况，在实 际应用是不可能实现的。更多的簇头选取算法综合考虑了节点的剩余能量，簇
22、 头到基站的距离，簇内通信代价等问题。目前提出的主流簇头选取算法有 LEACH、LEACH-F、DAEA、HEAD、CEFL、DCHS、DEFG 等。 2、成簇算法 成簇算法在簇头产生后，形成簇的拓扑结构，将网络划分成相连的区域。良好 的簇拓扑结构有助于延长传感器网络的使用周期。目前提出的成簇算法有 ACMWN、HYENAS、EECS、PEGASIS、GAF、ACE、FBCC 等。 1.3 论文结构和研究内容 目前，人们基于节能的考虑已提出了各种各样的路由协议，本文对其中的 LEACH 算法进行分析，主要研究内容如下： (1) 详细分析了 LEACH 的簇头选取以及成簇算法，并对 LEACH
23、在簇头选取和成 簇过程中存在的问题进行了说明。 (2) 针对 LEACH 算法在簇头选取过程中没有考虑簇头在簇结构中位置和没有考虑 节点实际部署情况而引发的问题，将基于节点平均能耗的簇头选取算法和节点密度数 学模型结合起来，提出了能量有效簇头选取算法。 (3) 对算法进行仿真实验，并借鉴传感器网络中节能评价指标体系对实验结果进行 质量评价，最后本文通过理论分析和大量实验证明了新算法较 LEACH 算法性能更优 越。 论文主要由以下部分构成： 第一章对本课题背景和国内外研究现状做了描述。 第二章对传感器网络的概念以及应用进行介绍。 第三章对传统的 LEACH 算法进行了介绍，并详细分析了其存在的
24、不足。 第四章将节点密度模型和平均能耗模型结合起来，进一步对 LEACH 算法的簇头 选取过程进行改进，提出了能量有效的簇头选取算法。 第五章对算法进行仿真模拟实验。 最后为结论与展望，首先本文工作进行了总结，然后对下一步的研究方向进行了 展望。 1.4 小结 本章首先给出了课题的研究背景与意义、然后综述了国内外传感器网络覆盖判定 算法的研究现状、最后，给出了论文的结构和研究内容简介。 2. 传感器网络传感器网络概述概述 2.1 传感器网络简介 2.1.1 传感器网络的概念 传感器网络是由一组传感器以 Ad-Hoc 方式构成的有线或无线网络，其目的是协作 地感知、采集和处理网络覆盖的地理区域中
25、感知对象的信息，并发布给观察者。 从定义可以看出，传感器、感知对象和观察者是传感器网络的 3 个基本要素；有 线或无线网络是传感器之间、传感器与观察者之间的通信方式，用于在传感器与观察 者之间建立通信路径；协作地感知、采集、处理、发布感知信息是传感器网络的基本 功能。一组功能有限的传感器协作地完成大的感知任务是传感器网络的重要特点。传 感器网络中的部分或全部节点可以移动。传感器网络的拓扑结构也会随着节点的移动 而不断地动态变化。节点间以 Ad-Hoc 方式进行通信，每个节点都可以充当路由器的角 色，并且每个节点都具备动态搜索、定位和恢复连接的能力。 传感器由电源、感知部件、嵌入式处理器、存储器
26、、通信部件和软件这几部分构 成（如图 2.1 所示） 。电源为传感器提供正常工作所必需的能源。感知部件用于感知、 获取外界的信息，并将其转换为数字信号。处理部件负责协调节点各部分的工作。通 信部件负责与其他传感器或观察者的通信。软件则为传感器提供必要的软件支持，如 嵌入式操作系统、嵌入式数据库系统等。 图 2.1 传感器示意图 典型的传感器网络由传感器节点、接收发送器(sink)、Internet 或通信卫星、任务管 理节点等部分构成。传感器节点散布在指定的感知区域内，每个节点都可以收集数据， 并通过“多跳”路由方式把数据传送到 Sink。Sink 也可以用同样的方式将信息发送给各 节点。Si
27、nk 直接与 Internet 或通信卫星相连，通过 Internet 或通信卫星实现任务管理节 点(即观察者)与传感器之间的通信。图 2.2 描述了一个典型的传感器网络的结构14。 2.2典型的传感器网络的结构 2.1.2 传感器网络的特点 传感器网络除了具有 Ad-Hoc 网络的移动性、断接性、电源能力有限等特征外，还 具有以下鲜明特点14： (1) 通信能力有限。传感器网络中的传感器的通信带宽较窄而且经常变化，通信覆 盖范围只有几十到几百米。传感器之间的通信断接频繁，经常导致通信失败。由于传 感器网络更多地受到高山、建筑物、障碍物等地势地貌以及风雨雷电等自然环境的影 响，传感器可能会长时
28、间离线工作。 (2) 计算能力有限。传感器网络中的传感器都具有嵌入式处理器和存储器。这些传 感器都具有计算能力，可以完成一些信息处理工作。但是，由于嵌入式处理器和存储 器的能力和容量有限，传感器的计算能力十分有限。使用大量具有有限计算能力的传 感器进行协作分布式信息处理，是我们的选择之一。 (3) 传感器数量大、分布范围广。传感器网络中传感器节点密集，数量巨大，可能 达到几百、几千万，甚至更多。此外，传感器网络可以分布在很广泛的地理区域。传 感器的数量与用户数量比通常也非常大。这就要求传感器网络的软、硬件必须具有高 强壮性和容错性。 (4) 感知数据流巨大。传感器网络中的每个传感器通常都产生较
29、大的流式数据，并 具有实时性。每个传感器仅仅具有有限的计算资源，难以处理巨大的实时数据流。这 就需要研究强有力的分布式数据流管理、查询、分析和挖掘方法。 2.1.3 传感器网络的核心技术 以数据为中心的传感器网络的基本思想是：把传感器视为感知数据流或感知数据 源，把传感器网络视为感知数据空间或感知数据库，把数据管理和处理作为网络的应 用目标。传感器网络以数据为中心的特点使得其设计方法不同于其他计算机网络(包括 Internet)。传感器网络的设计必须以感知数据管理和处理为中心，把数据库技术和网络 技术紧密结合，从逻辑概念和软、硬件技术两个方面实现一个高性能的以数据为中心 的网络系统，为用户或观
30、察者提供一个有效的感知数据空间或感知数据库管理和处理 系统，使用户如同使用通常的数据库管理系统和数据处理系统一样自如地在传感器网 络上进行感知数据的管理和处理。 感知数据管理与处理技术是实现以数据为中心的传感器网络的核心技术17。感知 数据管理与处理技术包括感知网络数据的存储、查询、分析、挖掘、理解以及基于感 知数据决策和行为的理论和技术。传感器网络的各种实现技术必须与这些技术密切结 合，融为一体，而不是像目前其他网络设计那样分而治之。只有这样才能够设计实现 高效率的以数据为中心的传感器网络系统。 对感知数据管理与处理的研究方向主要包括：感知数据管理技术的研究、感知数 据查询处理技术的研究、感
31、知数据分析技术的研究、感知数据挖掘技术的研究以及感 知数据管理系统的研究。 2.2 传感器网络的应用 2.2.1 环境的检测和保护 随着人们对于环境问题的关注程度越来越高，需要采集的环境数据也越来越多， 无线传感器网络的出现为随机性的研究数据获取提供了便利，并且还可以避免传统数 据收集方式给环境带来的侵入式破坏。比如，2002 年英特尔研究实验室研究人员曾经 将 32 个小型传感器连进互联网，掌握缅因州“大鸭岛“上的气候，以此评价一种海燕巢 的条件。2003 年第二季度，他们换用 150 个安有 D 型微型电池的第二代传感器，来评 估这些鸟巢的条件。另外，无线传感器网络可以跟踪候鸟和昆虫的迁移
32、，研究环境变 化对农作物的影响，监测海洋、大气和土壤的成分等。它也可以应用在精细农业中， 来监测农作物中的害虫、土壤的酸碱度和施肥状况等。 2.2.2 医疗护理 无线传感器网络在医疗研究、护理领域同样可以大展身手。它可以用于病区移动 查房、床边护理、呼叫通信、护理监控、药库管理等方面。 罗彻斯特大学的科学家使用无线传感器创建了一个智能医疗房间，使用微尘来测 量居住者的重要征兆（血压、脉搏和呼吸） 、睡觉姿势以及每天 24 小时的活动状况。 英特尔公司也推出了无线传感器网络的家庭护理技术。该技术是作为探讨应对老龄化 社会的技术项目 Center for Aging Services Techno
33、logies（CAST）的一个环节开发的18。 该系统通过在鞋、家具以家用电器等家中道具和设备中嵌入半导体传感器，帮助老龄 人士、阿尔茨海默氏病患者以及残障人士的家庭生活。利用无线通信将各传感器联网 可高效传递必要的信息从而方便接受护理。而且还可以减轻护理人员的负担。英特尔 主管预防性健康保险研究的董事 Eric Dishman 称， “在开发家庭用护理技术方面，无线 传感器网络是非常有前途的领域”。 2.2.3 军事领域 由于无线传感器网络具有密集型、低成本、随机分布的节点组成，自组织性和容 错能力使其非常适合应用于恶劣的战场环境中，包括侦察敌情、监控兵力、装备和物 资，判断生物化学攻击等多
34、方面用途1。美国国防部远景计划研究局已投资几千万美元， 帮助大学进行“智能尘埃“传感器技术的研发。哈伯研究公司总裁阿尔门丁格预测：智 能尘埃式传感器及有关的技术销售将从 2004 年的 1000 万美元增加到 2010 年的几十亿 美元。 2.2.3 其他应用 无线传感器网络还被应用于其他一些领域。比如一些危险的工业环境如井矿、核 电厂等，工作人员可以通过它来实施安全监测。也可以用在交通领域作为车辆监控的 有力工具。此外和还可以在工业自动化生产线等诸多领域，英特尔正在对工厂中的一 个无线网络进行测试，该网络由 40 台机器上的 210 个传感器组成，这样组成的监控系 统将可以大大改善工厂的运作
35、条件。它可以大幅降低检查设备的成本，同时由于可以 提前发现问题，因此将能够缩短停机时间，提高效率，并延长设备的使用时间。尽管 无线传感器技术目前仍处于初步应用阶段，但已经展示出了非凡的应用价值，相信随 着相关技术的发展和推进，一定会得到更大的应用。 无线传感器网络有着十分广泛的应用前景，它不仅在工业、农业、军事、环境、 医疗等传统领域有具有巨大的运用价值，在未来还将在许多新兴领域体现其优越性， 如家用、保健、交通等领域。我们可以大胆的预见，将来无线传感器网络将无处不在， 将完全融入我们的生活。比如微型传感器网络最终可能将家用电器、个人电脑和其他 日常用品同互联网相连，实现远距离跟踪。家庭采用无
36、线传感器网络负责家电协同工 作，进行安全调控，并且可以节省电能。另外，用户可以根据自己的个人喜好，可以 利用传感器网络设置智能生活环境，如依据传感器检测数据来调节室内光线强度、音 乐声音，以形成惬意的房间氛围。无线传感器网络将是未来的一个无孔不入的十分庞 大的网络，其应用可以涉及到人类日常生活和社会生产活动的所有领域。 2.3 传感器网络的特点与挑战 传感器网络除了具有 Ad-Hoc 网络的移动性、断接性、电源能力局限等共同特征以 外，还具有很多其他鲜明的特点。这些特点向我们提出了一系列挑战性问题14： (1)通信能力有限。传感器网络的传感器的通信带宽窄而且经常变化，通信覆盖范 围只有几十到几
37、百米。传感器之间的通信断接频繁，经常导致通信失败。由于传感器 网络更多地受到高山、建筑物、障碍物等地势地貌以及风雨雷电等自然环境的影响， 传感器可能会长时间脱离网络，离线工作。 (2)电源能量有限。传感器的电源能量极其有限。网络中的传感器由于电源能量的原 因经常失效或废弃。电源能量约束是阻碍传感器网络应用的严重问题。商品化的无线 发送接收器电源远远不能满足传感器网络的需要。传感器传输信息要比执行计算更消 耗电能.传感器传输 1 位信息所需要的电能足以执行 3000 条计算指令。 (3)计算能力有限。传感器网络中的传感器都具有嵌入式处理器和存储器。这些传 感器都具有计算能力，可以完成一些信息处理
38、工作。但是，由于嵌入式处理器和存储 器的能力和容量有限，传感器的计算能力十分有限。如何使用大量具有有限计算能力 的传感器进行协作分布式信息处理，是我们面临的第 3 个挑战。 (4)传感器数量大、分布范围广。传感器网络中传感器节点密集，数量巨大，可能 达到几百、几千万，甚至更多。此外，传感器网络可以分布在很广泛的地理区域。传 感器的数量与用户数量比通常也非常大。传感器数量大、分布广的特点使得网络的维 护十分困难甚至不可维护，传感器网络的软、硬件必须具有高强壮性和容错性。 (5)网络动态性强。传感器网络具有很强的动态性。网络中的传感器、感知对象和 观察者这三要素都可能具有移动性，并且经常有新节点加
39、入或已有节点失效。因此， 网络的拓扑结构动态变化，传感器、感知对象和观察者三者之间的路径也随之变化。 传感器网络必须具有可重构和自调整性。 (6)大规模分布式触发器。很多传感器网络需要对感知对象进行控制，如温度控制。 这样，很多传感器具有回控装置和控制软件。 (7)感知数据流巨大。传感器网络中的每个传感器通常都产生较大的流式数据，并 具有实时性。每个传感器仅仅具有有限的计算资源，难以处理巨大的实时数据流。这 就需要研究强有力的分布式数据流管理、查询、分析和挖掘方法。 2.4 小结 本章首先给出了传感器网络的定义、特点以及传感器网络管理核心技术的描述， 然后，简要介绍了传感器网络的应用领域，最后
40、，简述了当前传感器网络研究中所面 临的挑战。 3. LEACH 算法简介及分析算法简介及分析 3.1 引言 未来的计算装置将越来越与环境融于一体，直至它们对于用户是不可见的。而分布 式无线传感器网络正是这一思想的重要体现。不断小型化是微型传感器的设计目标， 而传感器的能源供应则是传感器小型化过程中最主要的限制。 传统的能量供应装置是电池，然而缩小电池的体积，增加电池容量的工程技术发 展缓慢，这直接影响了无线传感器网络的发展。无法从能量存储的硬件设备上获得突 破，于是科研人员开始寻求延长传感器网络使用寿命的其它途径。这就是通过各种优 化应用，完善操作系统和通信协议来降低网络的能量消耗，从而在总能
41、量不变的情况 下增加传感器网络的使用时间。 在上述背景下，各种有关传感器网络的路由算法和通信协议纷纷被提出，其中 Heinzelman 等人提出的 LEACH 算法是最具代表性和里程碑意义的。 3.2 LEACH 算法 LEACH 算法是一种典型的层次路由算法。相比较平面路由算法而言，LEACH 算 法具有以下的优点： 成员节点大部分时间可以关闭通信模块，由簇头构成一个更上一层的连通网 络来负责数据的长距离路由转发。这样既保证了原有覆盖范围内的数据通信， 也在很大程度上节省了网络能量。 簇头融合了成员节点的数据之后再进行转发，减少了数据通信量，降低了数 据冗余，在节省了通讯能量的同时也降低了传
42、感器网络在数据计算方面的能 量开销。 成员节点的功能比较简单，无须维护复杂的路由信息。这大大减少了网络中 路由控制信息的数量，减少了通信量。 分簇拓扑结构便于管理，有利于分布式算法的应用，可以对系统变化作出快 速反应，具有较好的可扩展性，适合大规模网络。 LEACH 算法首先作了如下的假设： 基站(BS)远离传感器网络节点并且是稳定的。 传感器网络中的所有节点是同构的，并且能量都受到限制。 所有节点可以直接和基站通讯。 节点都没有位置信息。 簇头节点负责数据压缩汇聚以及与基站进行通讯。 该算法主要通过随机选择簇首领，平均分担中继通信业务来实现节能。同时 LEACH 定义了“轮”(Round)的
43、概念，针对每个节点 n 设定了一个阀值 T(n)： (2.1) ：否则 ：若 0 ) 1 mod(1 )( Gn p rp p nT 式(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)Rad
44、omNum，则该节点当选为簇头，并广播当选消息。 Step5： 其余节点选择加入某簇头所在的簇，形成稳定的拓扑结构。 Step6： 稳定工作阶段。 Step7： 每隔时间 t，进行下一轮簇头选取，转 Step1，重新选择簇头并成簇。 由以上步骤可知 LEACH 算法中的轮是指两次簇头选取之间的时间段，每一轮由初 始化和稳定工作两个阶段组成。在初始化阶段，随机选择节点为簇首领，成为簇首领 的节点向周围广播信息，其它节点根据接受到广播信息的强度来选择它所要加入的簇， 并告知相应的簇首领，由于信息的强度和节点之间的距离是成正比的，因此，实际上 各非 簇头节点是选择距离自己地理距离最短的簇头所在的簇加
45、入，并形成簇拓扑结构，如 图 3.1 所示： 图 3.1 成簇阶段图 传感器网络首先产生中心节点，其余节点加入距离自己最近的中心节点所在的簇， 然后由中心节点直接和 SINK 节点进行通讯。在稳定工作阶段，节点持续采集监测数 据，传送到簇头，由簇头对数据进行必要的融合处理之后，发送到终端节点。每轮工 作周期结束后，重新选择簇头并重复前面的工作。 3.3 LEACH 算法中存在的问题分析 在上述的 LEACH 算法描述中，我们仔细思考，不难发现其中存在着以下的诸 多 问题。 (1) 算法没有考虑簇头节点在簇结构中的位置对簇头能耗的影响。在簇头选取的过程中， 位于簇中心位置的节点和位于簇边缘位置的
46、节点成为簇头的机率是一样的。由于位于 簇边缘位置的簇头其通讯能耗远大于位于簇中心位置的簇头，因此将导致各簇头能耗 不均 衡，使某些簇头节点能量提前耗尽。 (2) LEACH 没有考虑到传感器网络在进行部署的时候，节点分布密度对簇头能耗的影 响。由此导致在传感器节点密集分布区域的簇头能耗巨大，而在传感器节点稀疏分布 区域的簇头能耗较小，网络中各簇头的能耗极不均衡。 (3) 动态分簇引起网络拓扑结构频繁变换和大量广播通信，从而带来了额外的能量开销。 3.3.1 未考虑簇头在簇结构中位置时存在的问题 为指出未考虑簇头在簇结构中位置时 LEACH 算法中存在的问题，首先假定通过 飞机播撒等方式部署的传
47、感器网络中已经形成了若干个簇。其中有某个簇由 5 个传感 器节点构成，且簇中各节点 A，B，C，D，E 的初始能量均为 40，该簇的 5 个传感器 节点的具体分布情况如图 3.2 所示。 图 3.2 具有 5 个节点的传感器网络 为计算方便，且假定簇中各节点 A，B，C，D，E 两两之间的距离如表 2.1 所示： 表 3.1 图 2.2 中节点 A,B,C,D,E 两两间的距离 距离ABCDE A01243 B10364 C23032 D46303 E34230 假定在每轮通信中，各簇成员分别发送一次数据给簇头，则每轮通信中各节点的工作 能 耗如表 2.2 所示： 表 3.2 A,B,C,D,
48、E 分别为簇头时各节点的工作能耗 簇头/能耗ABCDE A102486 B2146128 C461064 D8126166 E684612 基于式(2.1)可知：采用 LEACH 算法时整个网络的生命周期可能如表 2.3 所示： 表 3.3 采用 LEACH 算法时整个网络的生命周期 簇头/剩余能量ABCDE 第 1 轮：A 为簇头3038363234 第 2 轮：B 为簇头2824302026 第 3 轮：C 为簇头2418201422 第 4 轮：D 为簇头16614-216 显然，采用 LEACH 算法时，整个网络的生命周期将小于 4 轮。从上面的分析不 难看出，LEACH 算法进行第四
49、轮簇头选取时，没有考虑到节点的剩余能量及其工作能 耗，导致剩余能量小于工作能耗的节点 D 当选为簇头，使节点 D 的能量过早衰竭，网 络的生命周期也随之结束。若结合考虑节点的位置信息，使靠近簇结构中心位置且剩 余能量 较多的节点有更多机会成为簇头，无疑将有效延长网络的生命周期。 3.3.2 未考虑节点分布密度时存在的问题 为考虑节点分布密度对网络生命周期的影响，给出一个具有 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 两两间的距离 距离ABCDEFGH A0584791114 B50449101313 C8404761111 D4440671012 E797604611 F910674058 G111311106506 H1413111211860 根据 LEACH 算法，则有可能出现以下的成簇情况，各种情况下簇头的