《无线传感器网络分簇算法研究毕业设计.doc》由会员分享，可在线阅读，更多相关《无线传感器网络分簇算法研究毕业设计.doc（51页珍藏版）》请在三一办公上搜索。
1、装订线 本科生毕业论文（设计） 题目：无线传感器网络分簇算法研究 系 部 计算机科学与技术 学科门类 工 科 专 业 计算机科学与技术 学 号 0810110013 姓 名 指导教师 2012 年 5 月 15 日无线传感器网络分簇算法研究摘 要无线传感器网络是大量传感器节点以自组织和多跳的方式构成的无线网络。传感器节点一般都被安置在野外甚至是人们无法到达的地方，只能靠自带的电池供电，网络节点的能量极其有限，因此所有的信息处理策略都必须考虑到尽可能地降低节点能耗。分簇算法是将无线传感器网络分成若干个簇，每个簇选出一个簇头，簇头作为本地基站将簇内节点传给它的数据进行融合后再传给基站，因而大大降低
2、了节点消耗的能量，延长了网络寿命。本文阐述典型的无线传感器网络，着重对LEACH算法进行分析。在windows系统中搭建NS2无线传感器网络模拟平台，并对LEACH算法进行仿真模拟，观察此算法的运行过程，分析LEACH算法的优缺点，论证了LEACH算法的可行性与高效性。关键词：无线传感器网络 LEACH算法 NS2 分簇ABSTRACTThe wireless sensor network consists of a large number of sensor nodes in the way of self-organizing and multi-hop. Sensor nodes ar
3、e generally placed in the wild, or even in the place where people cannot reach. It can only rely on the built-in battery-powered. Network node energy is extremely limited, so all of the information processing strategies must take reducing node power consumption into account as much as possible. Clus
4、tering algorithm is to divide wireless sensor network into several clusters, then elect a cluster head from each cluster. The cluster head functions as a local base station, integrating the data which the cluster node has passed to it and then pass the result to the base station. Thus, the node ener
5、gy consumption is reduced greatly, this can help to prolong the lifetime of the network.This paper elaborates a typical wireless sensor network, it focuses on analyzing the LEACH algorithm. Setting up a NS2 wireless sensor network simulation platform in the windows system and doing the LEACH algorit
6、hm simulation to observe the running of this algorithm; besides, analyzing the advantages and disadvantages of LEACH algorithm and demonstrating the feasibility and efficiency of the LEACH algorithm.Key words: wireless sensor networks LEACH algorithm NS2 clustering目 录第1章 绪论11.1 课题研究背景与意义11.2 国内外研究现状
7、11.3 本文研究内容21.4 本文组织结构2第2章 无线传感器网络概述32.1 无线传感器网络基本概念32.1.1 无线传感器网络体系结构32.1.2 传感器网络的特征32.2 无线传感器网络的应用32.3 无线传感器的关键技术4第3章 无线传感器网络拓扑控制63.1 拓扑控制概述63.2 功率控制73.2.1 概述73.2.2 基于节点度的算法73.2.3 基于邻近图的算法83.3 层次型拓扑结构控制103.3.1 LEACH算法103.3.2 GAF算法10第4章 LEACH算法协议124.1 LEACH算法原理124.2 LEACH算法的分析与实现124.3 LEACH算法的特点134
8、.4 算法中存在的问题分析及改进134.4.1 算法中的问题134.4.2 LEACH算法的改进13第5章 LEACH算法仿真165.1 NS2仿真软件165.1.1 NS2仿真软件概述165.1.2 NS2扩展功能175.1.3 NS2软件构成175.1.4 使用方法185.2 LEACH算法仿真195.2.1 LEACH算法实现195.2.2 核心代码分析255.2.3 NSG2可视化工具介绍305.2.4 LEACH算法仿真结果分析31第6章 结论34致 谢35参考文献36附 录37第1章 绪论1.1 课题研究背景与意义传感器网络节点的能量极其有限，所有的信息处理策略都必须考虑到尽可能地
9、降低节点能耗，以便延长网络和整个系统的寿命。将传感器节点组织成簇的形式能有效减少网络的能量消耗，许多能量有效的路由协议都是在簇结构的基础上进行设计的。分簇算法也可以用于执行数据融合，将无线传感器感测的大量数据组合成少量有意义的信息集合。在簇结构下，算法只在一个簇范围内执行而不需要等待控制消息传遍整个网络。在大型网络中，这一特点使得局部化算法比在整个全局结构中执行的中心化算法具有更好的扩展性。同时，分簇算法的研究对于信息广播和数据查询也非常有用，簇头可以在簇内协助广播消息和搜集用户需要的数据。无线传感器网络是新兴的下一代传感器网络。最早的代表性论述出现在 1999 年，题为“传感器走向无线时代”
10、。随后在美国的移动计算和网络国际会议上，提出了无线传感器网络是下一个世纪面临的发展机遇。2003年，美国技术评论 杂志论述未来新兴十大技术时，无线传感器网络被列为第一项未来新兴技术。同年，美国商业周刊未来技术专版，论述四大新技术时，无线传感器网络也列人其中。美国今日防务杂志更认为无线传感器网络的应用和发展，将引起 一场划时代的军事技术革命和未来战争的变革。2004年(IEEE Spectrum)杂志发表一期专集：传感器的国度，论述无线传感器网络的发展和可能的广泛应用。可以预计，无线传感器网络的发展和广泛应用，将对人们的社会生活、产业变革带来极大的影响和产生巨大的推动1。1.2 国内外研究现状无
11、线传感器网络是从传感器网络开始的，第一代传感器网络出现在 20世纪70年代。使用具有简单信息信号获取能力的传统传感器，采用点对点传输、连接传感控制器构成传感器网络；第二代传感器网络，具有获取多种信息信号的综合能力，采用串、并接口(如Rs-232、RS-485)与传感控制器相联，构成有综合多种信息的传感器网络；第三代传感器网络出现 在20世纪90年代后期和本世纪初，用具有智能获取多种信息信号的传感器，采用现场总线连接传感控制器，构成局域网络，成为智能化传感器网络；第四代传感器网络正在研究开发，目前成形并大量投入使用的产品还没有出现用大量的具有多功能多信息信号获取能力的传感器，采用自组织无线接入网
12、络，与传感器网络控制器连接，构成无线传感器网络。20世纪90年代在美国发端了现代意义的无线传感器网络技术。随后，该技术被一些重要机构预测为将改变世界的重要新技术，相关研究工作在各主要发达国家轰轰烈烈地开展起来。我国现代意义的无线传感器网络及其应用研究几乎与发达国家同步启动，首次正式出现于1999年中国科学院知识创新工程试点领域方向研究的“信息与自动化领域研究报告”中，最为该领域提出的五个重大项目之一。随着知识创新工程试点工作的深入，2001年中国科学院依托上海微系统所成立微系统研究与发展中心，旨在引领中国科学院内部的相关工作。为系统研究与发展中心在无线传感器网络方向上陆续部署了若干重大研究项目
13、和方向性项目，参加单位包括上海微系统所、声学所、微电子所、半导体所、电子所、软件以及中国科技大学等10余个研究所和高校。进过几年的努力，初步建立了传感器网络系统的研究平台，在无线智能传感器网络通信技术、微型传感器、传感器端机、移动基站和应用系统等方面取得了很大进展。2004年9月相关成果在北京尽心了大规模外场演出，部分成果已在实际工程系统中应用2。1.3 本文研究内容在满足网络覆盖度和连通度的前提下，通过功率控制和骨干网节点选择，剔除节点之间不必要的通信链路，形成一个数据转发的优化网络结构。功率控制机制调节网络中每个节点的发射功率，在满足网络连通度的前提下，均衡节点的单跳可达邻居数目。层次型拓
14、扑控制利用分簇机制，让一些节点作为簇头节点，由簇头节点形成一个处理并转发数据的骨干网，其他非骨干网节点可以暂时关闭通信模块，进入休眠转台以节省能量。本次设计主要研究的问题是：（1）影响整个网络的生存时间的因素；（2）减小结点间通信干扰、提高网络通信效率的方法；（3）如何弥补节点失效的影响。31.4 本文组织结构本文分为6章，第1章主要介绍了课题研究的目的、意义和国内外的发展状况；第2章是介绍无线传感器网络的体系结构、特征、关键技术和应用等相关概念；第3章介绍了无线传感器网络的拓扑控制的基本概念，并用两个算法加以举例；第4章对LEACH协议进行详细阐述，如算法的原理、特点、存在的问题以及改进方法
15、；第5章介绍在NS2平台上对LEACH算法进行仿真的步骤、过程以及对仿真过程中所得结果进行分析；第6章对全文进行总结。第2章 无线传感器网络概述2.1 无线传感器网络基本概念2.1.1 无线传感器网络体系结构传感器网络系统通常包括传感器节点、汇聚节点和管理节点。大量传感器节点部署在检测区域内或者附近，能够通过自组织方式构成网络。传感器节点检测的数据沿着其他传感器节点逐跳地进行传输，在传输过程中检测数据可能被多个节点处理，经过多跳后路由到汇聚节点，最后通过互联网或者卫星到达管理节点。用户通过管理节点对传感器网络进行配置和管理，发布监测任务以及收集监测数据。大量的传感器节点将探测数据，通过汇聚节点
16、经其它网络发送给了用户。在这个定义中，传感器网络实现了数据采集、处理和传输的三种功能，而这正对应着现代信息技术的三大基础技术，即传感器技术、计算机技术和通信技术。如下图所示：图2-1无线传感器网络组织结构图2.1.2 传感器网络的特征（1）大规模网络 ；（2）自组织网络 ；（3）动态性网络；（4）可靠的网络；（5）应用相关的网络；（6）以数据为中心的网络。42.2 无线传感器网络的应用传感器网络的应用前景非常广阔，能够广泛应用于军事、环境监测和预报、健康护理、智能家居、建筑物状态监测、复杂机械监控、城市交通、空间探索、大型车间和仓库管理，以及机场、大型工业园区的安全监测等领域。随着传感器网络的
17、深入研究和广泛应用，传感器网络将逐渐深入到人类生活的各个领域。（1）军事应用：传感器网络具有可快速部署、可自组织、隐蔽性强和高容错性的特点，因此非常适合在军事上应用。利用传感器网络能够实现对敌军兵力和装备的监控、战场的实时监控、目标的定位、战场评估、核攻击和生物化学攻击的检测和搜索等功能。（2）环境观测和预报系统：随着人们对于环境的日益关注，环境科学所涉及的范围越来越广泛。传感器网络在环境研究方面可用于监视农作物灌溉情况、土壤空气情况、牲畜和家禽的环境状况和大面积的地标监测等，可用于行星探测、气象和地理研究、洪水泛滥等，还可以通过跟踪鸟类、小型动物和昆虫进行群复杂度的研究等。（3）医疗护理：传
18、感器网络在医疗系统和健康护理方面的应用包括监测人体的各种生理数据，跟踪和监控医院内医生和患者的行动，医院的药物管理等。如果在住院病人身上安装特殊用途的传感器节点，如心率和血压监测设备，医生利用传感器网络就可以随时了解被监护病人的病情，发现异常能够迅速抢救。（4）智能家居：传感器网络能够应用在家居中。在家电和家具中嵌入传感器节点，通过无线网络与Internet连接在一起，将会为人们提供更加舒适、方便和更具人性化的智能家居环境。利用远程监控系统，可完成对家电的远程控制，例如可以在回家之前半小时打开空调，这样回家的时候就可以直接享受适合的室温，也可以遥控电饭锅、微波炉、电冰箱、电话机、电视机、录像机
19、、电脑等家电，按照自己的意愿完成相应的煮饭、烧菜、查收电话留言、选择录制电视和电台节目以及下载网上资料到电脑中等工作，也可以通过图像传感设备随时监控家庭安全情况5。2.3 无线传感器的关键技术（1）网络拓扑控制：传感器网络拓扑控制目前主要的研究问题是在满足网络覆盖度和连通度的前提下，通过功率控制和骨干网节点选择，删除节点之间不必要的无线通信链路，生产一个高效的数据转发的网络拓扑结构。拓扑控制可以分为节点功率控制和层次型拓扑结构形成两个方面。功率控制方面目前已经提出了COMPOW，LINT/LILT，CBTC，LMST，RNG，DRNG和DLSS等算法，层次型拓扑控制目前提出了TopDisc，G
20、AF，LEACH和HEED等算法。 （2）网络协议：由于传感器网络节点的硬件资源有限和拓扑结构的动态变化，网络协议不能太复杂但又要高效。目前研究的重点是网络层协议和数据链路层协议。网络层的路由协议决定检测信息的传输路径，目前提出了多种类型的协议，如多个能量感知的路由协议，定向扩散和谣传路由等基于查询的路由协议，GEAR和GEM等基于地理位置的路由协议，SPEED和ReInForM等支持的QoS的路由协议。数据链路层的介质访问控制用来构建底层的基础结构，控制传感器节点的通信过程和工作模式。目前提出了S-MAC、T-MAC和Sift等基于竞争的MAC协议，DEANA、TRAMA、DMAC和周期性调
21、度等时分复用的MAC协议等。（3）时间同步：时间同步是需要协同工作的传感器网络系统的一个关键机制。Jeremy Elson和Kay Romer在2002年8月的HotNets-I国际会议上首次提出并阐述了无线传感器网络中的时间同步机制的研究课题，在传感器网络研究领域引起了关注。目前已提出了多个时间同步机制，其中RBS、TINY/MINI-SYNC和TPSN被认为是三个基本的同步机制。（4）定位技术：位置信息是传感器节点采集数据中不可缺少的部分，没有位置信息的检测消息通常毫无意义。确定事件发生的位置或采集数据的节点位置是传感器网络最基本的功能之一。目前的定位技术有基于距离的定位，如基于TOA的定
22、位、基于AOA的定位、基于RSSI的定位等；和与距离无关的定位算法，如质心算法、DV-Hop算法、APIT算法等等6。第3章 无线传感器网络拓扑控制3.1 拓扑控制概述拓扑控制技术是无线传感器网络中最重要的技术之一。在由无线传感器网络生成的网络拓扑中，可以直接通信的两个结点之间存在一条拓扑边。如果没有拓扑控制，所有结点都会以最大无线传输功率工作。在这种情况下，一方面，结点有限的能量将被通信部件快速消耗，降低了网络的生命周期。同时，网络中每个结点的无线信号将覆盖大量其他结点，造成无线信号冲突频繁，影响结点的无线通信质量，降低网络的吞吐率。另一方面，在生成的网络拓扑中将存在大量的边，从而导致网络拓
23、扑信息量大，路由计算复杂，浪费了宝贵的计算资源。因此，需要研究无线传感器网络中的拓扑控制问题，在维持拓扑的某些全局性质的前提下，通过调整结点的发送功率来延长网络生命周期，提高网络吞吐量，降低网络干扰，节约结点资源。（1）应满足的性质：拓扑控制算法的目标是通过控制结点的传输范围使生成的网络拓扑满足一定的性质，以延长网络生命周期，降低网络干扰，提高吞吐率。拓扑控制算法的目标是通过控制结点的传输范围使生成的网络拓扑满足一定的性质，以延长网络生命周期，降低网络干扰，提高吞吐率。一般假设结点分布在二维平面上，所有结点都是同构的，都使用无向天线。以有向图建模无线传感器网络，如果结点i的传输功率Pi大于从结
24、点i到结点j需要的传输功率Pij，则结点i到结点j之间有一条有向边。所有结点都以最大功率工作时所生成的拓扑称为UDG图(Unit Disk Graph)。一般假设结点分布在二维平面上，所有结点都是同构的，都使用无向天线。以有向图建模无线传感器网络，如果结点i的传输功率Pi大于从结点i到结点j需要的传输功率Pij，则结点i到结点j之间有一条有向边。所有结点都以最大功率工作时所生成的拓扑称为UDG图(Unit Disk Graph)。（2）研究方法：目前对拓扑控制的研究可以分为两大类。一类是计算几何方法，以某些几何结构为基础构建网络的拓扑，以满足某些性质。另一类是概率分析方法，在结点按照某种概率密
25、度分布情况下，计算使拓扑以大概率满足某些性质时结点所需的最小传输功率和最小邻居个数。计算几何方法：该方法常使用的几何结构有如下几种：最小生成树(MST) 网络拓扑是以结点间的欧式距离为度量的最小生成树。结点的传输半径设为与该结点相邻的最长边的长度。以MST为拓扑的网络能保证网络的连通性。由于在分布式环境下构造MST开销巨大，一种折中的方法是结点采用局部MST方法设置传输范围。GG图(Gabriel Graph) 在传输功率正比传输距离的平方时，GG图是最节能的拓扑。MST是GG图的子图，GG图也满足连通性。RNG图(Relative Neighbor Graph) 其稀疏程度在MST和GG图之
26、间，连通性也在MST和GG图之间，优于MST，冲突干扰优于GG图，是两者的折中。RNG图易于用分布式算法构造。DT图(Delaunay Triangulation) UDG与DT图的交集称为UDel图(Unit Delaunay Triangulation)。UDel图是稀疏的平面图，适合于地理路由协议、节能、简化路由计算，以及降低干扰，因此十分适合作为无线底层拓扑7。3.2 功率控制3.2.1 概述无线自组织网络中的功率控制问题是指分布式系统中的节点在无线通信过程中选择最恰当的功率级发送分组，以此达到优化网络应用相关性能的目的。由于节点发射功率级的选择对网络多方面的性能均会产生影响，因此，网
27、络中的节点采用多大的功率级发送分组是一个非常复杂并具有挑战性的课题。功率控制对无线自组织网络的性能影响显著，主要表现在以下5个方面：（1）功率控制对网络能量有效性的影响；（2）功率控制对网络连通性和拓扑结构的影响；（3）功率控制对网络平均竞争强度的影响；（4）功率控制对网络容量的影响；（5）功率控制对网络实时性的影响8。3.2.2 基于节点度的算法一个节点的度数是指所有距离该节点一跳的邻居节点的数目。基于节点度算法的核心思想是给定节点度的上限和下限需求，动态调整节点的发射功率，使得节点的度数落在上限和下限之间。基于节点度的算法利用局部信息来调整相邻节点间的连通性，从而保证了整个网络的连通性，同
28、时保证节点间的链路具有一定的冗余性和可扩展性。下面是两种典型的基于节点度的算法。本地平均算法LMA(local mean algorithm)和本地邻居平均算法LMN(local mean of neighbors algorithm)是两种周期性动态调整节点发射功率的算法。它们之间的区别在于计算节点度的策略不同。（1）本地平均算法本地平均算法LMA具体步骤如下：开始时所有节点都有相同的发射功率TransPower，每个节点定期广播一个包含自己ID的LifeMsg消息。如果节点接收到LifeMsg消息，发送一个LifeAckMsg应答消息。该消息中包含所应答的LifeMsg消息中的结点ID。每
29、个节点在下一次发送LifeMsg时，首先检查已经收到的LifeAckMsg消息，利用这些消息统计出自己的邻居数NodeResp。如果NodeResp小于邻居数下限NodeMinThresh，那么节点在这轮发送中将增大发射功率，但发射功率不能超过发射功率的Bmax倍，如式：TransPower=minBmaxTransPower ，Ainc(NodeMinThresh- NodeResp) TransPower 同理，如果NodeResp大于邻居节点数上限，那么节点将减小发射功率，用式子TransPower=maxBminTransPower，Adec(1-( NodeResp-NodeMaxT
30、hresh)TransPower表示，其中的Bmax、Bmin、Ainc和Adec是四个可调参数，它们会影响功率调节的精度和范围。（2）本地邻居平均算法本地邻居平均算法LMN与本地平均算法LMA类似，唯一的区别是在邻居数NodeResp的计算方法上。在LMN算法中，每个节点发送LifeAckMsg消息时，将自己的邻居数放入消息中，发送LifeMsg消息的节点在收集完所有的LifeAckMsg消息后，将所有邻居的邻居数求平均值并作为自己的邻居数。这两种算法都缺少严格的理论推导。通过计算机仿真结果确定：这两种算法的收敛性和网络的连通性是可以保证的，它们通过少量的局部信息达到了一定程度的优化效果。这
31、两种算法对无线传感器节点的要求不高，不需要严格的时钟同步。但算法还存在一些明显不完善的地方，例如，需要进一步研究合理的邻居节点判断条件，从邻居节点得到的消息是否根据信号的强弱给予不同的权重等9。3.2.3 基于邻近图的算法（1）邻近图图可以用G=(V,E)的形式表示，其中V代表图中顶点的集合，E代表图中边的集合。E中的元素可以表示为l=(u,v)，其中u,vV。所谓由一个图G=(V,E)导出的邻近图G=(V,E)是指：对于任意一个节点vV，给定其邻居的判定条件q，E中满足q的边(u,v)属于E。经典的邻近图模型有RNG（relative neighborhood graph）、GG(Gabri
32、el graph)、YG(yao graph)以及MST(minimum spanning tree)等。基于邻近图的功率控制算法是指：所有节点都使用最大功率发射时形成的拓扑图为图G，按照一定的规则q求出该图的邻近图G，最后G中每个节点以自己所邻接的最远通信节点来确定发射功率。这是一种解决功率分配问题的近似解法。考虑到传感器网络中两个节点形成的边是有向的，为了避免形成单向边，一般在运用基于邻近图的算法形成网络拓扑之后，还需要进行节点之间边的增删，以使最后得到的网络拓扑是双向连通的。在传感器网络中，基于邻近图的算法的作用是使节点确定自己的邻居集合，调整适当的发射功率，从而在建立起一个连通的网络同
33、时，达到节省能力的目的。在已有的传感器网络拓扑算法中，基于邻近图的算法还不多，比较完善的有DRNG算法和DLSS算法。（2）DRNG算法和DLSS算法DRNG（directed relative neighborhood graph）算法和DLSS（directed local spanning subgraph）算法是两种以邻近图的观点考虑拓扑问题的算法，它们是较早的针对节点发送功率不一致问题提出的拓扑解决方案。这两种算法以经典邻近图RNG、LMST等理论为基础，全面考虑了网络的连通性和双向连通性问题。在DRNG算法中，其确定了节点邻居集合。其没有给出算法的详细步骤，但给出了确定的标准。假设
34、u,v满足d(u,v)=r,r为节点u的通信距离，当不存在另一节点p同时满足w(u,p)w(w,v),w(p,v)w(u,v)和d(p,v)=r时，节点v就被选为节点u的邻居节点。如下图所示：图3-1 DRNG算法模型图不论是在DRNG算法中还是在DLSS算法中，节点都需要知道一些必要信息，所以在拓扑形成之前有一个信息收集阶段。在这个阶段中，每个节点以自己的最大发射功率广播HELLO消息，该消息中至少要包括自己的ID和自己所在的位置。这个阶段完成后，每个节点通过接受到的HELLO消息确定自己可达的邻居集合。DRNG和DLSS算法着重考虑网络的连通性，充分利用邻近图的理论，考虑到传感器网络的特点
35、，它们是同类算法中的典型算法，以原始网络拓扑双向连通为前提，保证优化后的拓扑也是双向连通的。下图是DRNG算法和DLSS算法优化拓扑结构的例子，其中图a是每个节点以最大功率发射形成的原始拓扑结构，图b是经过DRNG算法优化后的拓扑结构，图c是经过DLSS算法优化后的拓扑结构。可以看出，无论是DRNG算法还是DLSS算法，都使得网络拓扑图中边的数量明显减少，降低了节点的发射功率，同时减少了节点间的通信干扰。最大功率连通图 DRNG算法优化图 DLSS算法优化图图3-2 三种算法网络拓扑图对比除了以上提到的两种功率分配算法，还有一些贪心算法，如CONNECT算法和FPA/VPA算法等，但它们对网络
36、和节点要求相对苛刻，这里不再一一举例。3.3 层次型拓扑结构控制3.3.1 LEACH算法为了提高整个网络的的生存时间，将功耗均衡的分配到网络中的每个节点，麻省理工学院的Wendi Rabiner Heinzelman等人提出了一种低功耗的自适应路由协议LEACH协议(Low-Energy Adaptive ClusteriingHierarchy)。在LEACH协议中，每个传感节点都有机会充当簇头节点，簇头节点的选择主要依据网络中所需要的簇头节点个数与到目前为止每个节点已经充当簇头节点的次数来判定的。网络中每个节点在01之间随机选择一个数，如果选择的数小于规定阀值T(n)，则该节点就充当簇首
37、节点。T(n)的计算如下： （3-1）上式中，p表示在无线网络中簇头节点所占的百分比，r为当前循环次数，G是在前1/p轮中未充当过簇头节点的集合。LEACH算法通过设置T(n)值，以保证每个节点在1/p轮内都有机会充当一次簇头节点，从而平衡了节点的能量消耗。簇头节点确定之后，簇头节点通过广播告知整个网络自己已经成为簇头节点，簇头节点在广播过程中采用CSMA MAC协议来避免冲突。这时，网络中的非簇头节点可以根据接收到的信号强度来决定自己要从属于哪个簇，选择信号强度最强的源节点作为自己的簇头节点，并告知相关的簇头节点，自己则成为簇内组员10。3.3.2 GAF算法GAF（geographical
38、 adaptive fidelity）算法是以节点地理位置为依据的分簇算法。该算法把监测区域划分成虚拟单元格，将节点按照位置信息划入相应的单元格；在每个单元格中定期选举产生一个簇头节点，只有簇头节点保持活动，其他节点进入休眠状态。GAF是ad hoc网络中提出的一种路由算法，将其引入传感器网络，是因为它的虚拟单元格思想为分簇机制提供了新思路。GAF算法的执行过程包括两个阶段。第一阶段是虚拟单元格的划分。根据节点的位置信息和通信半径，将网络区域划分成若干虚拟单元格，保证相邻单元格中的任意两个节点都能够直接通信。假设节点已知整个检测区域的位置信息和本身的位置信息，节点可以通过计算得知自己属于哪个单
39、元格。假设所有节点的通信半径为R，网络区域划分为边长为r的正方形虚拟单元格，为了保证相邻两个单元格内的任意两个节点能够直接通信，需要满足如下关系式： （3-2）所以从分组转发的角度来看，属于同一单元格的节点可以认为是等价的，每个单元格只需要选出一个节点保持活动状态。GAF算法的第二阶段是虚拟单元格中簇头节点的选择。节点周期性地进入睡眠和工作状态，从睡眠状态唤醒之后与本单元内其他节点交换信息，以确定自己是否需要成为簇头节点。每个节点可以处于发现、活动以及睡眠三种状态，如图所示：图3-3 GAF算法状态转换图第4章 LEACH算法协议4.1 LEACH算法原理LEACH来源于Wendi Rabin
40、er Heinzelman, Anantha Chandrakasan, 和Hari Balakrishnan三人在2000年Proceedings of the 33rd Hawaii International Conference on System Sciences上的一篇文章Energy-Efficient Communication Protocol forWireless Microsensor Networks。 LEACH全称是“低功耗自适应集簇分层型协议” (Low Energy Adaptive Clustering Hierarchy)。该算法基本思想是：以循环的方式随
41、机选择簇头节点，将整个网络的能量负载平均分配到每个传感器节点中，从而达到降低网络能源消耗、提高网络整体生存时间的目的。仿真表明，与一般的平面多跳路由协议和静态分层算法相比，LEACH可以将网络生命周期延长15%。4.2 LEACH算法的分析与实现LEACH在运行过程中不断的循环执行簇的重构过程，每个簇重构过程可以用回合的概念来描述。每个回合可以分成两个阶段：簇的建立阶段和传输数据的稳定阶段。为了节省资源开销，稳定阶段的持续时间要大于建立阶段的持续时间。簇的建立过程可分成4个阶段：簇头节点的选择、簇头节点的广播、簇头节点的建立和调度机制的生成。簇头节点的选择依据网络中所需要的簇头节点总数和迄今为
42、止每个节点已成为簇头节点的次数来决定。具体的选择办法是：每个传感器节点随机选择0-1之间的一个值。如果选定的值小于某一个阀值，那么这个节点成为簇头节点。选定簇头节点后，通过广播告知整个网络。网络中的其他节点根据接收信息的信号强度决定从属的簇，并通知相应的簇头节点，完成簇的建立。最后，簇头节点采用TDMA方式为簇中每个节点分配向其传递数据的时间点。稳定阶段中，传感器节点将采集的数据传送到簇头节点。簇头节点对簇中所有节点所采集的数据进行信息融合后再传送给汇聚节点，这是一种叫少通信业务量的合理工作模型。稳定阶段持续一段时间后，网络重新进入簇的建立阶段，进行下一回合的簇重构，不断循环，每个簇采用不同的
43、CDMA代码进行通信来减少其他簇内节点的干扰。其中阀值，T(n)按照下列公式计算： （4-1）式中：P为节点成为簇头节点的百分数，r为当前轮数，G为在最近的1/p轮中未当选簇头的节点集合。簇头节点选定后，广播自己成为簇头的消息，节点根据接收到的消息的强度决定加入哪个簇，并告知相应的簇头，完成簇的建立过程。然后，簇头节点采用TDMA的方式，为簇内成员分配传送数据的时隙。在稳定阶段，传感器节点将采集的数据传送到簇头节点。簇头节点对采集的数据进行数据融合后再将信息传送给汇聚节点，汇聚节点将数据传送给监控中心来进行数据的处理。稳定阶段持续一段时间后，网络重新进入簇的建立阶段，进行下一轮的簇重建，不断循
44、环。4.3 LEACH算法的特点（1）为了减少传送到汇聚节点的信息数量，簇首节点负责融合来自蔟内不同源节点所产生的数据，并将融合后的数据发送到汇聚点。 （2）LEACH采用基于TDMA/CDMA的MAC层机制来减少蔟内和蔟间的冲突。（3）由于数据采集是集中的和周期性的，因此该协议非常适合于要求连续监控的应用系统。（4）对于终端使用者来说，由于它并不需要立即得到所有的数据，因此协议不需要周期性的传输数据，这样可以达到限制传感器节点能量消耗的目的。（5）在给定的时间间隔后，协议重新选举簇首节点，以保证无线传感器网络获取同意的能量分布11。4.4 算法中存在的问题分析及改进4.4.1 算法中的问题（
45、1）刚开始假设每个节点能量相同，在现实环境中很难做到；（2）每个节点成为簇首节点的概率相同，这样可能导致一些高能量节点没机会成为簇首节点，而一些低能量节点成为簇首节点。一旦这些低能量节点成为簇首节点，将会很快耗尽其能量；（3）LEACH协议不能保证簇头在每个区域都分布均匀，虽然统计上面是均匀的，但是由于簇头产生带有极大的随机性，有些区域可能簇头数会较多；（4）簇首节点在通信过程中采用单跳与基站通信，这样就会导致较远的簇首节点能量消耗过大，而过早死亡，影响整个网络的性能；（5）整个网络节点在两跳范围内，这样不符合大规模网络需求12。4.4.2 LEACH算法的改进（1）根据节点初始能量不同改进：
46、根据整个网络中节点能量的初始不同，Georgios Smaragdakis等人提出了一种改进行分簇算法SEP算法(a Stable Election Proto-col for clustered heterogeneous)，先把整个网络分成两类节点，能量较高的节点称为高能量节点，能量低的称为正常节点。可以看出，高能量节点成为簇首节点的机会大于低能量节点。相对于LEACH算法，充分利用了整个网络的功耗。为整个网络簇首节点的概率，Pnrm为正常节点成为簇首节点的概率，Padv为高能量节点成为簇首节点的概率。r为当前循环次数，G1是在前1/p轮中正常节点未充当过簇头节点的集合。G2是在前1/p轮
47、中高能量节点未充当过簇头节点的集合。m为网络中高能量节点的比例。a为高能量节点高于正常节点能量部分。在参考文献中，作者对SEp算法进行再次改进，利用整个网络节点的平均能量与节点当前能量的比值来限制节点成为簇首节点的概率，两类节点成为簇首节点概率如下式所示。 （4-2）可以看出进一步限制的低能量节点成为簇首节点的概率13。（2）根据节点剩余能量的不同而改进：M.J.Handy等人提出了DCHS(Deterministic Clus-ter-Head Selection)算法，根据LEACH算法中的T(n)计算不足之处，对其进行改进，如下式所示。 （4-3）式中En_current表示节点当前的能量，En_max表示节点初始的能量。由改进后的算法可以看出，当前节点能
