1、无线传感器网络分簇算法研究本科毕业设计 本科生毕业论文（设计） 题目：无线传感器网络分簇算法研究 毕业设计（论文）原创性声明和使用授权说明原创性声明本人郑重承诺：所呈交的毕业设计（论文），是我个人在指导教师的指导下进行的研究工作及取得的成果。尽我所知，除文中特别加以标注和致谢的地方外，不包含其他人或组织已经发表或公布过的研究成果，也不包含我为获得 及其它教育机构的学位或学历而使用过的材料。对本研究提供过帮助和做出过贡献的个人或集体，均已在文中作了明确的说明并表示了谢意。作 者 签 名： 日 期： 指导教师签名： 日期： 使用授权说明本人完全了解 大学关于收集、保存、使用毕业设计（论文）的规定，
2、即：按照学校要求提交毕业设计（论文）的印刷本和电子版本；学校有权保存毕业设计（论文）的印刷本和电子版，并提供目录检索与阅览服务；学校可以采用影印、缩印、数字化或其它复制手段保存论文；在不以赢利为目的前提下，学校可以公布论文的部分或全部内容。作者签名： 日 期： 学位论文原创性声明本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所取得的研究成果。除了文中特别加以标注引用的内容外，本论文不包含任何其他个人或集体已经发表或撰写的成果作品。对本文的研究做出重要贡献的个人和集体，均已在文中以明确方式标明。本人完全意识到本声明的法律后果由本人承担。作者签名： 日期： 年 月 日学位论文版权使用授
3、权书本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。本人授权 大学可以将本学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。涉密论文按学校规定处理。作者签名： 日期： 年 月 日导师签名： 日期： 年 月 日无线传感器网络分簇算法研究摘 要无线传感器网络是大量传感器节点以自组织和多跳的方式构成的无线网络。传感器节点一般都被安置在野外甚至是人们无法到达的地方，只能靠自带的电池供电，网络节点的能量极其有限，因此所有的信息处理策略都必须考虑到尽可能地降低节点
4、能耗。分簇算法是将无线传感器网络分成若干个簇，每个簇选出一个簇头，簇头作为本地基站将簇内节点传给它的数据进行融合后再传给基站，因而大大降低了节点消耗的能量，延长了网络寿命。本文阐述典型的无线传感器网络，着重对LEACH算法进行分析。在windows系统中搭建NS2无线传感器网络模拟平台，并对LEACH算法进行仿真模拟，观察此算法的运行过程，分析LEACH算法的优缺点，论证了LEACH算法的可行性与高效性。关键词：无线传感器网络 LEACH算法 NS2 分簇ABSTRACTThe wireless sensor network consists of a large number of sens
5、or nodes in the way of self-organizing and multi-hop. Sensor nodes are 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 r
6、educing node power consumption into account as much as possible. Clustering 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
7、 it and then pass the result to the base station. Thus, the node energy 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
8、simulation platform in the windows system and doing the LEACH algorithm 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 netwo
9、rks LEACH algorithm NS2 clustering第1章 绪论1.1 课题研究背景与意义传感器网络节点的能量极其有限，所有的信息处理策略都必须考虑到尽可能地降低节点能耗，以便延长网络和整个系统的寿命。将传感器节点组织成簇的形式能有效减少网络的能量消耗，许多能量有效的路由协议都是在簇结构的基础上进行设计的。分簇算法也可以用于执行数据融合，将无线传感器感测的大量数据组合成少量有意义的信息集合。在簇结构下，算法只在一个簇范围内执行而不需要等待控制消息传遍整个网络。在大型网络中，这一特点使得局部化算法比在整个全局结构中执行的中心化算法具有更好的扩展性。同时，分簇算法的研究对于信息广播
10、和数据查询也非常有用，簇头可以在簇内协助广播消息和搜集用户需要的数据。无线传感器网络是新兴的下一代传感器网络。最早的代表性论述出现在 1999 年，题为“传感器走向无线时代”。随后在美国的移动计算和网络国际会议上，提出了无线传感器网络是下一个世纪面临的发展机遇。2003年，美国技术评论 杂志论述未来新兴十大技术时，无线传感器网络被列为第一项未来新兴技术。同年，美国商业周刊未来技术专版，论述四大新技术时，无线传感器网络也列人其中。美国今日防务杂志更认为无线传感器网络的应用和发展，将引起 一场划时代的军事技术革命和未来战争的变革。2004年(IEEE Spectrum)杂志发表一期专集：传感器的国
11、度，论述无线传感器网络的发展和可能的广泛应用。可以预计，无线传感器网络的发展和广泛应用，将对人们的社会生活、产业变革带来极大的影响和产生巨大的推动1。1.2 国内外研究现状无线传感器网络是从传感器网络开始的，第一代传感器网络出现在 20世纪70年代。使用具有简单信息信号获取能力的传统传感器，采用点对点传输、连接传感控制器构成传感器网络；第二代传感器网络，具有获取多种信息信号的综合能力，采用串、并接口(如Rs-232、RS-485)与传感控制器相联，构成有综合多种信息的传感器网络；第三代传感器网络出现 在20世纪90年代后期和本世纪初，用具有智能获取多种信息信号的传感器，采用现场总线连接传感控制
12、器，构成局域网络，成为智能化传感器网络；第四代传感器网络正在研究开发，目前成形并大量投入使用的产品还没有出现用大量的具有多功能多信息信号获取能力的传感器，采用自组织无线接入网络，与传感器网络控制器连接，构成无线传感器网络。20世纪90年代在美国发端了现代意义的无线传感器网络技术。随后，该技术被一些重要机构预测为将改变世界的重要新技术，相关研究工作在各主要发达国家轰轰烈烈地开展起来。我国现代意义的无线传感器网络及其应用研究几乎与发达国家同步启动，首次正式出现于1999年中国科学院知识创新工程试点领域方向研究的“信息与自动化领域研究报告”中，最为该领域提出的五个重大项目之一。随着知识创新工程试点工
13、作的深入，2001年中国科学院依托上海微系统所成立微系统研究与发展中心，旨在引领中国科学院内部的相关工作。为系统研究与发展中心在无线传感器网络方向上陆续部署了若干重大研究项目和方向性项目，参加单位包括上海微系统所、声学所、微电子所、半导体所、电子所、软件以及中国科技大学等10余个研究所和高校。进过几年的努力，初步建立了传感器网络系统的研究平台，在无线智能传感器网络通信技术、微型传感器、传感器端机、移动基站和应用系统等方面取得了很大进展。2004年9月相关成果在北京尽心了大规模外场演出，部分成果已在实际工程系统中应用2。1.3 本文研究内容在满足网络覆盖度和连通度的前提下，通过功率控制和骨干网节
14、点选择，剔除节点之间不必要的通信链路，形成一个数据转发的优化网络结构。功率控制机制调节网络中每个节点的发射功率，在满足网络连通度的前提下，均衡节点的单跳可达邻居数目。层次型拓扑控制利用分簇机制，让一些节点作为簇头节点，由簇头节点形成一个处理并转发数据的骨干网，其他非骨干网节点可以暂时关闭通信模块，进入休眠转台以节省能量。本次设计主要研究的问题是：（1）影响整个网络的生存时间的因素；（2）减小结点间通信干扰、提高网络通信效率的方法；（3）如何弥补节点失效的影响。31.4 本文组织结构本文分为6章，第1章主要介绍了课题研究的目的、意义和国内外的发展状况；第2章是介绍无线传感器网络的体系结构、特征、
15、关键技术和应用等相关概念；第3章介绍了无线传感器网络的拓扑控制的基本概念，并用两个算法加以举例；第4章对LEACH协议进行详细阐述，如算法的原理、特点、存在的问题以及改进方法；第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）环境观测和预报系统：随着人们对于环境的日益关注，环境科学所涉及的范围越来越广泛。传感器网络在环境研究方面可用于监视农作物灌溉情况、
18、土壤空气情况、牲畜和家禽的环境状况和大面积的地标监测等，可用于行星探测、气象和地理研究、洪水泛滥等，还可以通过跟踪鸟类、小型动物和昆虫进行群复杂度的研究等。（3）医疗护理：传感器网络在医疗系统和健康护理方面的应用包括监测人体的各种生理数据，跟踪和监控医院内医生和患者的行动，医院的药物管理等。如果在住院病人身上安装特殊用途的传感器节点，如心率和血压监测设备，医生利用传感器网络就可以随时了解被监护病人的病情，发现异常能够迅速抢救。（4）智能家居：传感器网络能够应用在家居中。在家电和家具中嵌入传感器节点，通过无线网络与Internet连接在一起，将会为人们提供更加舒适、方便和更具人性化的智能家居环境
19、。利用远程监控系统，可完成对家电的远程控制，例如可以在回家之前半小时打开空调，这样回家的时候就可以直接享受适合的室温，也可以遥控电饭锅、微波炉、电冰箱、电话机、电视机、录像机、电脑等家电，按照自己的意愿完成相应的煮饭、烧菜、查收电话留言、选择录制电视和电台节目以及下载网上资料到电脑中等工作，也可以通过图像传感设备随时监控家庭安全情况5。2.3 无线传感器的关键技术（1）网络拓扑控制：传感器网络拓扑控制目前主要的研究问题是在满足网络覆盖度和连通度的前提下，通过功率控制和骨干网节点选择，删除节点之间不必要的无线通信链路，生产一个高效的数据转发的网络拓扑结构。拓扑控制可以分为节点功率控制和层次型拓扑
20、结构形成两个方面。功率控制方面目前已经提出了COMPOW，LINT/LILT，CBTC，LMST，RNG，DRNG和DLSS等算法，层次型拓扑控制目前提出了TopDisc，GAF，LEACH和HEED等算法。 （2）网络协议：由于传感器网络节点的硬件资源有限和拓扑结构的动态变化，网络协议不能太复杂但又要高效。目前研究的重点是网络层协议和数据链路层协议。网络层的路由协议决定检测信息的传输路径，目前提出了多种类型的协议，如多个能量感知的路由协议，定向扩散和谣传路由等基于查询的路由协议，GEAR和GEM等基于地理位置的路由协议，SPEED和ReInForM等支持的QoS的路由协议。数据链路层的介质访
21、问控制用来构建底层的基础结构，控制传感器节点的通信过程和工作模式。目前提出了S-MAC、T-MAC和Sift等基于竞争的MAC协议，DEANA、TRAMA、DMAC和周期性调度等时分复用的MAC协议等。（3）时间同步：时间同步是需要协同工作的传感器网络系统的一个关键机制。Jeremy Elson和Kay Romer在2002年8月的HotNets-I国际会议上首次提出并阐述了无线传感器网络中的时间同步机制的研究课题，在传感器网络研究领域引起了关注。目前已提出了多个时间同步机制，其中RBS、TINY/MINI-SYNC和TPSN被认为是三个基本的同步机制。（4）定位技术：位置信息是传感器节点采集
22、数据中不可缺少的部分，没有位置信息的检测消息通常毫无意义。确定事件发生的位置或采集数据的节点位置是传感器网络最基本的功能之一。目前的定位技术有基于距离的定位，如基于TOA的定位、基于AOA的定位、基于RSSI的定位等；和与距离无关的定位算法，如质心算法、DV-Hop算法、APIT算法等等6。第3章 无线传感器网络拓扑控制3.1 拓扑控制概述拓扑控制技术是无线传感器网络中最重要的技术之一。在由无线传感器网络生成的网络拓扑中，可以直接通信的两个结点之间存在一条拓扑边。如果没有拓扑控制，所有结点都会以最大无线传输功率工作。在这种情况下，一方面，结点有限的能量将被通信部件快速消耗，降低了网络的生命周期
23、。同时，网络中每个结点的无线信号将覆盖大量其他结点，造成无线信号冲突频繁，影响结点的无线通信质量，降低网络的吞吐率。另一方面，在生成的网络拓扑中将存在大量的边，从而导致网络拓扑信息量大，路由计算复杂，浪费了宝贵的计算资源。因此，需要研究无线传感器网络中的拓扑控制问题，在维持拓扑的某些全局性质的前提下，通过调整结点的发送功率来延长网络生命周期，提高网络吞吐量，降低网络干扰，节约结点资源。（1）应满足的性质：拓扑控制算法的目标是通过控制结点的传输范围使生成的网络拓扑满足一定的性质，以延长网络生命周期，降低网络干扰，提高吞吐率。拓扑控制算法的目标是通过控制结点的传输范围使生成的网络拓扑满足一定的性质
24、，以延长网络生命周期，降低网络干扰，提高吞吐率。一般假设结点分布在二维平面上，所有结点都是同构的，都使用无向天线。以有向图建模无线传感器网络，如果结点i的传输功率Pi大于从结点i到结点j需要的传输功率Pij，则结点i到结点j之间有一条有向边。所有结点都以最大功率工作时所生成的拓扑称为UDG图(Unit Disk Graph)。一般假设结点分布在二维平面上，所有结点都是同构的，都使用无向天线。以有向图建模无线传感器网络，如果结点i的传输功率Pi大于从结点i到结点j需要的传输功率Pij，则结点i到结点j之间有一条有向边。所有结点都以最大功率工作时所生成的拓扑称为UDG图(Unit Disk Gra
25、ph)。（2）研究方法：目前对拓扑控制的研究可以分为两大类。一类是计算几何方法，以某些几何结构为基础构建网络的拓扑，以满足某些性质。另一类是概率分析方法，在结点按照某种概率密度分布情况下，计算使拓扑以大概率满足某些性质时结点所需的最小传输功率和最小邻居个数。计算几何方法：该方法常使用的几何结构有如下几种：最小生成树(MST) 网络拓扑是以结点间的欧式距离为度量的最小生成树。结点的传输半径设为与该结点相邻的最长边的长度。以MST为拓扑的网络能保证网络的连通性。由于在分布式环境下构造MST开销巨大，一种折中的方法是结点采用局部MST方法设置传输范围。GG图(Gabriel Graph) 在传输功率
26、正比传输距离的平方时，GG图是最节能的拓扑。MST是GG图的子图，GG图也满足连通性。RNG图(Relative Neighbor Graph) 其稀疏程度在MST和GG图之间，连通性也在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，每个节
29、点定期广播一个包含自己ID的LifeMsg消息。如果节点接收到LifeMsg消息，发送一个LifeAckMsg应答消息。该消息中包含所应答的LifeMsg消息中的结点ID。每个节点在下一次发送LifeMsg时，首先检查已经收到的LifeAckMsg消息，利用这些消息统计出自己的邻居数NodeResp。如果NodeResp小于邻居数下限NodeMinThresh，那么节点在这轮发送中将增大发射功率，但发射功率不能超过发射功率的Bmax倍，如式：TransPower=minBmaxTransPower ，Ainc(NodeMinThresh- NodeResp) TransPower 同理，如果N
30、odeResp大于邻居节点数上限，那么节点将减小发射功率，用式子TransPower=maxBminTransPower，Adec(1-( NodeResp-NodeMaxThresh)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)是指：对于
32、任意一个节点vV，给定其邻居的判定条件q，E中满足q的边(u,v)属于E。经典的邻近图模型有RNG（relative neighborhood graph）、GG(Gabriel graph)、YG(yao graph)以及MST(minimum spanning tree)等。基于邻近图的功率控制算法是指：所有节点都使用最大功率发射时形成的拓扑图为图G，按照一定的规则q求出该图的邻近图G，最后G中每个节点以自己所邻接的最远通信节点来确定发射功率。这是一种解决功率分配问题的近似解法。考虑到传感器网络中两个节点形成的边是有向的，为了避免形成单向边，一般在运用基于邻近图的算法形成网络拓扑之后，还需要进行节点之间边的增删，以使最后得到的网络拓扑是双向连通的。在传感器网
