【《无线传感网络的拓扑结构控制算法与仿真研究》15000字（论文）】

摘要 I31470ABSTRACT II28136第1章绪论 2249671.1研究背景及意义 2107401.2国内外研究现状 330781.3本文主要研究内容和章节安排 31074第2章无线传感网络的体系结构及其拓扑控制介绍 538902.1无线传感网络定义 5265192.1.1无线传感网络组成 5139352.1.2无线传感网络特点 5136362.1.3无线传感网络性能指标 645302.1.4无线传感网络应用领域 7294922.2无线传感器网络拓扑控制技术 7216982.2.1拓扑控制技术的概念 7100612.2.2拓扑控制的特点 7280922.2.3拓扑控制结构 8136122.3本章小结 1020433第3章拓扑结构控制算法 11106123.1无线传感器网络拓扑控制算法介绍 11272683.2基于节点功率控制的拓扑算法 1175173.2.1CONNECT/BICONN算法 11171243.2.2AP算法 12306043.3基于层次划分的拓扑控制算法 1529583.3.1LEACH算法 1552573.3.2LEACH算法的改进算法 17229783.3.3HEED算法 1771773.4本章小结 1818445第4章仿真验证与分析 19126484.1LEACH算法流程： 1969984.2LEACH算法能耗模型： 20248324.3实验参数设置 20137984.4实验结果 21219074.4.1节点分布面积为300m*300m 2151174.4.2节点总数为200个 2531900第5章总结与展望 2988595.1工作总结 29283485.2展望 2930449参考文献 30绪论研究背景及意义无线传感器网络WSN(WirelessSensorNetworks)是一种借助无线通信技术将分布在各个地方的传感器节点进行统一组织运作的网络形式。它可以通过众多传感器节点来感知、收集和传输那些在网络覆盖地区内的对象所要求被监控的信息，再将这些信息传输到网络的拥有者手中。无线传感器网络容纳了很多种不同类型的传感器，通过它们可以探查到环境当中的各项数据并加以分析接下来会发生的事件。其应用领域也非常广，包含了:医疗、航空、工业等许多领域。进入21世纪以来，无线传感器网络在物联网、智能家居等很多方面都展示出了巨大的价值，因此获得了高度的关注并成为了如今的研究热门。WSN一般具有规模庞大、自组织性、能量有限、以数据为中心和动态性这几种特点。规模庞大指的是能够进行监测的范围很广并且传感器的节点数量很多；自组性指的是部署无线传感网络的时候可以不依赖已经设置好的基础设施而是通过其自组织能力来协调进而管理已有的配置；资源有限指的是通常情况下传感器节点都会被设置在较为恶劣的那些环境当中，而要进行人工维护或是补充节点能量便成为了十分困难的事情所以资源通常比较有限；以数据为中心是指数据存储的方式是根据内部的数据内容，而不是根据数据的来源或者数据获取的方式；动态性是指节点可以根据当前能量的消耗量来选择在网络中担任的角色。正是因为无线传感网内部的那些传感器节点的能量是有限的，所以能够解决能源消耗问题的方法一直都是物联网及其相关技术应用的重要问题。为了使正在运行的这段时间内功率消耗降低，我们就需要对网络拓扑结构进行改进。而这会对节点能耗的降低起到十分重要的作用。[3]降低部署网络的成本的基本要求是在监测点全部被覆盖的前提条件下通过拓扑结构来减少节点的数量。传感器节点更像是物联网的感知层这个身体的“感觉器官”。而由大量的传感器节点共同组建而成的无线传感器网络则更是物联网这个身体的“感觉神经末梢”。然而,感觉器官时不时的失灵使得物联网这个身体的“活动”收到了非常严重的阻碍。并且由于不同环境所造成的不同影响等因素，节点很容易出现提前死亡等差错，这就使得传感网络不是一尘不变的，而是再时时刻刻都会进行动态变化的。无线传感器网络的能耗降低能够使得网络生存的周期提升，而要降低能量消耗就需要应用到拓扑控制技术，拓扑技术对众多网络性能的优化，例如：传输时延的降低、网络覆盖的质量提升和对于通信的抗干扰能力的增强等等都能起到非常重要的作用。通过拓扑控制技术使得无限传感网络在保证能够正常覆盖及应用的前提条件下，根据无线传感网络自身的特点针对不同类型的应用环境通过变化为不同的网络结构来完成任务。因此，传感器网络通过自组性来协调控制各个节点而不需要固定的网络作为基础就可以在任意位置进行组网监测。所以，经过研究后设计出来的拓扑结构控制算法应当具有更加高效和稳定的性能，而它们也就具有非常重要的应用价值。国内外研究现状世界上第一个开始研究传感器网络领域的国家是美国。当时还是在上个世纪的美苏冷战时期。而美国当时在研究的传感器网络主要还是应用在了军事领域里。随着时代的发展，现代科技也在有条不紊地持续进步着，WSN逐渐开始在各种类型的领域里发光放热。近年来，无线传感器网络已经引起了各国的重视：相关国家都陆陆续续指定了政策，进行了相关的战略部署，比如：SmartDust项目、C4ISRT项目等等。从2002年开始，我国也在传感器网络领域中开展了诸多课题。最开始只是在学校里由老师同学们一起就WSN的应用前景开展了研究，近些年一些公司企业和研究所都加入到研究中。现阶段，无线传感器网络拓扑控制算法的研究已经成为了当下的热门。由于操作环境的多种多样，任务对无线传感器网络的应用要求也多种多样。所以在国内外便产生了诸多拓扑控制算法。例如：1）在功率控制的拓扑结构算法方面，比较经典的拓扑结构算法包含了LMA/LMN算法等等；在基于邻近图的拓扑结构控制算法的经典算法有RNG、DRNG等等。2）在层次型的拓扑控制算法方面，我们可以把层次型拓扑控制算法分为均匀分簇的拓扑控制算法与非均匀分簇的拓扑控制算法这两种：①通过均匀分簇来进行控制的拓扑控制算法：LEACH算法算是最经典的一种均匀分簇算法。②通过非均匀分簇来进行控制的拓扑控制算法：为了解决那些通过使用均匀分簇而导致的问题，人们研发出了使用非均匀分簇来控制的拓扑控制算法，最为典型的通过非均匀分簇来控制的算法有AP算法、USC算法等等。本文主要研究内容和章节安排本文依托于现在已有的无线传感网络的拓扑结构以及对拓扑结构进行控制的算法，来研究不同类型的算法对终端的用户的体验所产生的不同影响以此来改善已有算法并提升终端用户的服务体验。全文共分为5个部分：第一部分：绪论。介绍研究的技术背景和意义。介绍国内外研究现状。第二部分：介绍无线传感网络的体系结构及无线传感器网络拓扑控制的基本概念。第三部分：详细介绍几种不同类型的无线传感网络的拓扑结构控制算法。第四部分：建模并测量无线传感网络拓扑控制算法的结果，分析算法对终端用户造成的影响。第五部分：总结与展望。无线传感网络的体系结构及其拓扑控制介绍本章首先介绍了WSN的基本内容包含了WSN的构成、WSN所具有的特点、WSN中节点的性能指标以及对WSN适用的领域进行了介绍。其次，对何为WSN的拓扑控制技术进行了简单明了的说明与介绍。之后又介绍了拓扑控制算法的基本概念和几个特点，并为下一章介绍几种拓扑控制算法做一些铺垫。2.1无线传感网络定义2.1.1无线传感网络组成无线传感器网络的组成包含了三个模块。它们分别是传感器节点、传输网络和终端用户这3个模块。在这其中，传感器节点又是由供应能量的单元、采集数据的单元、处理数据的单元以及传输数据的单元这四种单元一同构成。采集数据的单元的目的就是为了采集那些在监测范围内部的物体所包含的信息并将这些信息转变成为信号；传输数据的单元的作用是进行信息的交流、发送或者接收那些被数据采集单元所采集到的数据信息；处理数据的单元的作用是管理所有节点在工作过程中所要用到的网络路由协议并根据目标给某些重要节点分配管理方面的任务以及对节点进行定位等等；供应能量的单元的作用就是给传感器节点补充消耗的能量，同时因为要缩减传感器节点的面积，通常情况下我们选择提供能量的方式是使用微型电池来补给能量。无线传感器网络当中的所有节点都可以被区分成两类节点，一类节点被称为汇聚节点而另一类节点被称为传感器节点。汇聚节点的作用类似于网关的作用，它们可以将传感器节点当中那些并不正确的数据删除并通过参考已知的相关数据来对将要发生的事件进行一个大致的判断。汇聚节点可以借助网络对用户节点发起通信，或是借助卫星直接对用户进行通信并且对接受到的数据进行分析和处理。传感网络是无线传感器网络中的重中之重，传感网络的作用是把从所有节点那里接收到的信息通过某一种特殊的方式收集起来，收集之后对这些信息进行一定量的计算与分析并且在分析过后将分析出来的结果汇聚到一个基站里，而基站内的结果会从卫星发送到用户端。2.1.2无线传感网络特点对比无线传感器网络与传统的传感器网络，我们可以发现无线传感器网络具有如下几种特点：无线传感器网络拥有相当自由的组合构建方法。没有任何一种外界的附加因素可以对无线网络传感器的构建起到限制作用。并且无论在什么时候什么地点，一个具有所有功能的无线网络传感器都可以被迅速地建成。而且在完成了无线网络传感器的建设工作之后，在无线传感器网络的内部会进行各种各样的维护修理与管理的工作。无线传感器网络的拓扑结构是具有着很强烈的不确定性的。无线传感器网络的拓扑结构在任何时候都是可以进行调整与改变的。传感器节点的数量在构成的网络拓扑结构中可以随时变大也可以随时变小，网络拓扑结构的分支可以随时增加和减少。无线传感器网络所使用的控制方式并不是由某一个点进行集中控制的。虽然整体上来讲，无线传感器网络确实是集中控制了基站节点与传感器节点。但是不同的传感器节点所使用的却并不是同一种的控制方法。不同的路由协议都是通过不同的网络终端内的主机分散开来运行，各个主机之间不会进行任何干涉行为。所以无线传感器网络很不容易被破坏殆尽。（4）无线传感器网络的安全保障却并不高。无线传感器网络是通过无线的方式进行信息的传递。所以在传送信息的过程当中，传感器网络的众多节点是很容易被入侵的，进而导致了原本安全的信息发生了泄露以及无线传感器网络会发生损坏。由于许多无线传感器网络的节点所处在的环境都是一些公开外放的环境当中，因此无线传感器网络的安全性并没有那么高。2.1.3无线传感网络性能指标2.1.3.1网络生存周期WSN网络停止工作的其中一个原因就是当死亡的节点数目超过了一个特定的个数。而这一段网络能够正常工作的时间长度就被定义为网络的生存周期。此外我们对WSN网络生存周期还有另外一种定义，那就是只有在网络被一定的覆盖率覆盖并且服务质量达到某一程度的时间才算有效。这一段有效时间就被称作是网络生存周期。[3]2.1.3.2覆盖率覆盖面积是指在WSN正常服务的前提下，WSN所覆盖的能够准确提供各项服务的最大面积。合理选择覆盖面积有助于分配无线网络资源并且增加无线网络资源的使用效率来完成所分配的任务。[3]2.1.3.3时延在发送端开始进行发送数据的操作到接收端接收完数据为止的这一段时间里，时延越短则系统约精确。2.1.3.4鲁棒性鲁棒性是由于WSN的环境并不稳定，经常会因为各种各样的理由导致节点发生死亡现象，所以在发生意外时重新建造拓扑结构使网络正常工作的性能。鲁棒性包括品质鲁棒性和稳定鲁棒性。一个控制系统能否在实际应用中起到作用的关键就是这个系统是否具有鲁棒性。2.1.4无线传感网络应用领域无线传感器网络拥有许多种类的传感器，这些传感器可以探测环境中的各种现象例如光强、噪声分贝、温度等等。随着科技的发展，无线传感器网络有着非常宽广的应用领域例如：军事领域、农业领域、建筑领域等等。军事领域：由于大规模构建无线传感器网络的成本低且部署的速度十分快，无线传感器网络在军事领域的应用在未来预防战争甚至是在战争当中都能起到巨大的作用。可以通过大量廉价的传感器来测量周边的湿度、声音、红外线等等参数，以此来实现对于敌军武器装备的监控以及定位，对于战场形势的评估等等功能。农业领域：可以利用大规模的传感器组网来监视植物的灌溉、土壤以及空气等因素的情况。我国做为一个农业大国，农作物的高产对于国民经济起到了至关重要的作用，因此在农业领域应用无线传感器网络是十分重要而且有意义的。建筑领域：无线传感器网络可以通过监视建筑物的修建环境、建筑物达到的高度、宽度等数值是否达标以及进行修建时对地震的提前预警等内容确保建筑顺利建成。[6]2.2无线传感器网络拓扑控制技术2.2.1拓扑控制技术的概念在确保无线传感网网络能够有效地运行的前提之下，根据无线传感器网络的各种特点，分析实际应用环境，拓扑控制可以控制节点的发射功率和其对于相邻的节点的选择，以此来形成更加高效、稳定的网络结构，使要完成的任务能够被顺利地完成。更加优秀的网络拓扑控制算法不单单可以提高无线传感网络的效率，更可以广大用户更加优质的体验。拓扑控制可以做到延长网络的生存时间，这是由于其能够有效地节省节点当中剩余的能量。所以拓扑控制技术是一项非常有现实意义的技术。2.2.2拓扑控制的特点1.连通和覆盖是拓扑结构至少应该要满足的最基本的两项要求。首先，最基本的需求是连通性。若只是一堆没有相互连接而只是一个个彼此孤立的传感器节点，那么显然无线传感器网络也无法存在，因此也没有办法达成目标。但是在某些特殊的情况下，连通并不需要达到百分之百的连通。若是在连通性这方面进行适当的让步，那么就可以节约能量来延长网络生存周期。其次，另一项基本要求就是要对所监测的区域进行完美地覆盖。这完美的覆盖便是进行监测、采集数据的基础。覆盖所能达到的程度代表了无线传感器网络在其监测区域内发生事件的概率。2.在设计拓扑控制算法时应当考虑到无线传感器网络的各种特点。例如长距离进行通信的能力并不是一般情况下节点所具备的能力。并且在节点分布范围大的情况下，相应的算法必须要让节点能够独自完成局部的拓扑构建，再通过组合各种局部拓扑来形成全局的连通的拓扑结构。3.不同应用场景的情况下应当有不同的拓扑控制算法来构建适合的网络拓扑结构不同的应用场景必然有着不同的要求，所以众多不同种类的拓扑控制算法就需要去应对这些形形色色的需求，因此在进行设计之时，拓扑控制技术就需要有多种多样的假设与目标。4.功率控制与邻居节点的选择是拓扑控制最基本的手段功率控制跟网络连通性的关系是非常紧密的。随着节点的发射功率不断增大，通信的半径也在逐渐增大，那么可以选择的邻居节点的数量也就越多，而连通性也就更加容易保证，但是这同时也意味着传感器网络有了更多能量的消耗，和更加强烈的通信干扰。反之，则节点的发射功率减小，通信的半径也就变小，同时可以选择的邻居节点的数量也在变少，想要保证连通性也就更加困难，但是相对来说也会降低节点的能量消耗与各个节点之间的干扰。当然，节点并没有要求一定要和所有的邻居节点全部建立起通信链路，所以对众多邻居节点我们可以适当选择舍弃一些邻居节点，以此来降低路由协议的开销。2.2.3拓扑控制结构WSN一般都包含了以下几类拓扑结构，它们分别是：星状拓扑结构(Startopology)、网状拓扑结构(Meshtopology)、混合状拓扑结构(Hybrid_networktopology)和簇树状拓扑结构(Cluster_treetopology)。下面介绍这几类拓扑结构的特点：1）星型拓扑星型结构包含了一个基站（BS）和许多传感器节点。基站与节点之间是通过单跳的形式进行信息的交换，显然这是WSN所有拓扑结构中最为简单的拓扑结构。在星型拓扑结构中基站与节点是可以交换信息的但是普通节点之间是不可以进行信息交换的。星型拓扑结构对于基站的要求较高，若是基站的可靠性高那么整个网络发生瘫痪的几率就低，但是若是基站的可靠性并不高那么网络就容易发生瘫痪，这也是星型拓扑结构的缺点所在。虽然星型结构的结构简单但是它形成的节点间距短，因此能耗就很低。所以，显然，星型拓扑结构可以用来监测范围不大的环境。2）网状拓扑在网状拓扑结构当中，所有的节点都具备数据交换传输的性能，它们可以通过单跳或是多跳的方式来传输数据。这就意味着即使是距离非常远的节点间也可以进行数据交换。所以在那些覆盖范围非常大的区域内，网状拓扑结构被广泛地应用了。因为节点可以通过多跳的方式进行数据通信，那么在多跳路径上的所有节点都需要有足够的能量维持多跳的持续进行，因此网状拓扑结构需要具有鲁棒性。在一些节点因为能量耗尽死亡时就需要别的节点立刻进行补救措施，这样才能让网络继续运行。而要让所有节点能够感知整个网络的情况并维持着收发信息的状态，这对于节点来说能量的消耗是非常大的。所以如果要监视的环境不是非常大范围且十分重要的环境那么高成本的网状拓扑显然不是你最好的选择。3）混合网络拓扑混合网络拓扑结构顾名思义是几种拓扑结构混合而成，集合了星型拓扑网络与网状托盘网络的优点，混合网络拓扑结构不仅仅能耗低、性能高、结构简单，同时覆盖的范围大、允许传输的节点之间的间隔距离也很远同时网络结构也较稳定。这样子的混合网络拓扑结构主体通常是以星型拓扑结构来分布传感器节点而路由器和中继器则是通过网状结构混合在星型结构之中。这样的网络结构当中若是有某个路由器或是中继器亦或是链路出现了问题那么其它的传感器节点依旧可以通过拓扑结构组成新的网络结构，从而继续工作而不会因为某个节点的问题使整个网络遇到麻烦。4）簇树网络拓扑与混合型网络结构不同的是，在簇树网络拓扑结构当中的节点并不能直接进行数据的交换和传输。在簇树网络拓扑结构当中，消息的传输是要经过协调器节点的，这个协调器节点起着中介的作用。在簇树网络拓扑中，占据主导地位的是全功能设备而次要地位类似于树上的叶子一般接入网络当中的是精简功能设备。通常情况下，网络与协调器节点是一对一的关系，而这个协调器节点通常是由全功能设备来担任，但是对于传感器节点来说，全功能设备与精简功能设备都可以担任。在簇树网络拓扑结构当中，整个网络的簇首是由网络的协调器节点来担任的，在所有节点都接受到簇首广播以后，所有节点都可以开始向簇首申请，申请加入到这个簇首节点的簇当中。申请过后由协调器节点进行判断，是否允许这个节点加入到簇中。这种结构的重中之重就是筛选簇首节点，若是簇首节点发生意外死亡那么整个网络就会重新开始簇首节点的选举并最终选出一个新的簇首节点来维持网络运行。2.3本章小结本章简要介绍了WSN的相关技术，其中包括WSN的组成结构、WSN的特点和性能指标并简要介绍了WSN应用领域。其次，对WSN拓扑控制技术进行了简单的介绍，包括了拓扑控制算法的概念、特点、控制方式及应用场景等等。为下一章介绍拓扑结构控制算法的介绍做铺垫。拓扑结构控制算法3.1无线传感器网络拓扑控制算法介绍现在这个阶段，无线传感器网络拓扑控制算法有两条研究的方向。一个研究方向是基于节点功率控制的传感器网络拓扑控制算法，另一给研究方向是基于层次划分的传感器网络拓扑控制算法。下面介绍这两种研究方向。第一种：基于节点功率控制的传感器网络拓扑控制算法是再确保网络连通并能正常运行的前提下，改变节点功率使节点的能量消耗降低。第二种：基于层次划分的传感器网络拓扑控制算法也可以被叫做分簇算法。它会选择一部分节点作为簇头节点。这些簇头节点会管理簇内的其它非簇头节点，同时它要融合数据并将数据转发出去。而簇内的非簇头节点再没有转发数据的任务的时候是可以进入休眠状态来减少能量的消耗的。但是簇头节点不可以进入休眠状态。3.2基于节点功率控制的拓扑算法功率控制拓扑算法的思路是通过调整节点的发射功率来动态地调整整个网络。在节点发射功率变化时，整个网络的覆盖范围、拓扑结构都会相应地产生变化。而覆盖范围和拓扑结构的变化可以引发节点能耗的变化，同时避免节点间的通信干扰。3.2.1CONNECT/BICONN算法CONNECT算法与BICONN算法都是功率控制型拓扑控制算法。它们的目的是降低每一个节点的最大发射功率。即把降低最大发射功率作为网络拓扑结构是否被优化的衡量标准。[7]CONNECT算法的描述如下：第一步：网络当中只包含了节点而没有包含节点间的连线。这样一来，节点本身就是连通分量。第二步：把节点间距进行非递减排序，根据这个排序来选择网络当中的每一条边，这个顺序也意味着节点的发射功率是在慢慢变大的。在连接被选择的边的时候若是这条边可以连接几个不同的节点也就是连接分量那么这几个连接分量可以合并成为一个连接分量；若是在连接时这条边连接了相同的连通分量，那么这条边可以被舍弃。随着边一条条的加入，回路逐渐产生了。随着回路的增多，网络当中的连通分量的个数在逐渐减小，直到连通分量上连着所有的节点。第三步：把没加入网络的节点对间的边定义为副作用边。通过调整副作用边可以减少节点的发送功率。BICONN算法通过使用贪婪技术把1连通的网络修改成2连通的网络，这与CONNECT算法相似。BICONN算法的数学表述如下：当要求的连通度是的时候,无线网络用来表示；传感器节点的集合用来表示；代表了到水平面的映射。在通信距离为时,所需要的最小的功率用来表示。每个节点达到最小的发射功率的范围为，最后导出的图就是图，它是一个连通图,并且的值最小，也就是最大发射功率的最小化操作。当要求的连通度是的时候,最小的功率函数用来表示，发射一个功率为的节点要求，这样导出来的图就是一个连通图，而增加一个，使使得导出的图形是2连通的图形，并且的值也是最小的。分析：CONNECT算法与BICONN算法这两个算法都是集中式的算法。集中式算法看重的是最小化最大发射功率。这就需要许许多多的信息例如网络拓扑的结构、每一条链路的状态变化以及每一个节点所在的位置。因为需要如此多的信息和计算，CONNECT算法和BICONN算法是不适合大规模的无线传感器网络。3.2.2AP算法AP算法（AffinityPropagationalgorithm）是一种并不需要有人监督就可以运作的效率较高且规模较大的数据聚类算法。AP算法适用于处理庞大的数据量。AP算法当中应用了近邻信息传播的思想，能够找到最好的聚类中心的集合，这使所有的节点到聚类中心的相似程度的和是最大的。算法通过把所有节点都拟定成为聚类中心，再通过这些节点的相似度矩阵来计算这些节点的责任性与可用性。在经历了一次次的迭代过程之后，有一组节点成为了聚类中心。在AP算法之中，样本和样本之间的相似度用来表示。它代表了样本适合成为样本的聚类中心的程度。通过公式3-3我们可以计算相似度矩阵。（3-3）如果，意味着样本成为样本聚类中心的概率大小，的值越大，样本成为样本聚类中心的机会也就越大；如果，相似度矩阵被称为偏向参数。在AP算法中我们通常把样本偏向参数设置为相同的数值。设定的偏向参数越大，那么样本当选聚类中心的可能也就越大，最后经过算法而生成的聚类中心的数目也就越多。反之，设定的偏向参数越小，样本当选聚类中心的可能也就越小，经过算法计算之后当选的聚类中心的数量也就越少。所以，偏向参数是可以决定经过算法产生的聚类中心数目的多少的。通过改变的大小，聚类中心的数目也就随之变化，以此来满足不同的任务所提出的需求。AP算法中传播的是样本之间的责任性与可用性。其中：是样本与样本的责任性，它代表了样本担任样本的聚类中心是否合适以及合适程度的深浅。代表了样本与样本之间的可用性，可用性意味着样本把样本当作聚类中心的合适度。AP算法一步步聚类的过程实际上也是责任性与可用性一次次迭代更新的过程，AP算法责任性与可用性的公式如下所示：（3-4）（3-5）根据公式3-6我们可以计算样本本身的可用性大小。（3-6）AP算法判断样本担任聚类中心的可能的依据是通过计算的责任性与可用性的和。若是和越大那么样本也就越可能成为聚类中心；反之则样本越不可能成为聚类中心。在经过一次次的更新迭代之后，AP算法的责任性与可用性逐渐稳定。在更新结束以后，样本与所有其它样本中使得值最大的那个样本进行比较。若是，那么样本就是聚类中心；而若，那么样本就是聚类中心。AP算法的步骤如下所示：（1）初始化根据各个样本点的位置，我们通过公式3-3来计算样本间的相似度，定义AP算法的偏向参数的数值，要求小于0。将责任性与可用性初始化。把责任性矩阵与可用性矩阵都置0。（2）迭代通过公式3-4与公式3-5来更新责任性矩阵和可用性矩阵；通过责任性与可用性，找到聚类中心。（3）确定聚类中心通过计算，来确定样本聚类中心的位置。再判断得到的这些聚类中心的数量是不是满足设定的要求，如果聚类中心的数量满足要求，那么聚类中心就可以确认下来，算法也就到此为止；若聚类中心的数量并没有达到要求，那么就修改，让责任性与可用性再进行迭代，一直到聚类中心的数目满足了要求为止。AP算法的流程图如图3-1所示。图3-1AP算法流程AP算法有如下几个优点：（1）AP算法并没有对相似度矩阵产生太高的要求。并没有要求相似度矩阵要具有某些特定的矩阵的特点。（2）一开始拟定的聚类中心并不是经过不断迭代更新后AP算法产生的那个聚类中心。在刚开始执行算法的时候，所有样本点都会被选成为聚类中心，而在经过算法对于责任性与可用性的不断迭代之后，最终的那些聚类中心才是真正的聚类中心的集合。（3）AP算法的误差平方和与其它算法相比的比较低的。（4）AP算法运行的时间复杂度比其它算法要低。虽然运行AP算法的时间比较长，但是与其它能够达到同样效果的聚类算法相比，其它算法需要的运行次数则明显比AP算法要高。这样看来，在时间复杂度这一方面，AP算法是比较优秀的。（5）AP算法的稳定性更加优秀。若偏向参数没有改变，又或者的偏向参数发生了变化但是聚类中心的个数没有发生变化，那么经过AP算法产生的聚类中心的集合是不会改变的。综上所述，AP算法又较高的稳定性，能较快地选举出聚类中心，且误差较低。因为AP算法的思想与传感器网络拓扑结构中的簇树拓扑结构相似。所以AP算法适用于无线传感器网络当中。3.3基于层次划分的拓扑控制算法层次划分的拓扑控制算法也可以被叫做分簇机制。3.3.1LEACH算法LEACH（Low-EnergyAdaptiveClusteringHierarchy）算法是一种典型的分层拓扑控制算法。LEACH算法会把节点分簇，再根据一定的概率选择簇头节点，把相邻的那些节点组成和一个簇。在这个簇内的节点会把它们探查到的数据发送到簇头处，再由簇头把数据融合了以后发送到基站处。LEACH算法让网络内部的所有节点都能等概率的成为簇头，以此来节约所有节点的平均能量并延长网络的生存寿命。 LEACH算法的基本思路就是在每轮的簇头选举的时候，节点能否担任簇头完全是由公式进行决定的。公式如下所示：(3-1)式中：——节点担任簇头节点所要达到的概率门限。 ——簇头数量在所有节点数量当中占有的百分比数。 ——簇头选举一共要进行的轮数。 ——在前r-1轮的选举当中都没有当选过簇头节点的节点的集合。所以就代表了本轮到目前为止的所有选举当中当选过簇头的节点数量。每轮都会选择百分之的节点担任簇头节点，在先前几轮当中已经成为过簇头的节点便不能再被选则成为簇头节点。在轮之后，网络中的所有节点基本上都成为过簇头节点，并且它们剩余的能量应当相差不多。这时进行簇首节点的重新选举，重组所有簇结构。簇头节点会发出消息宣布自己成为簇头节点，这时其它的节点在接收到簇头节点的消息之后，就会选择离自己最近、信号最强的那个簇首节点加入到它的簇中。LEACH算法的流程是先选举簇头节点，选举完成后簇头节点会发布消息通知其它节点自己成为了簇头节点。这时其它非簇头节点会选择加入距离自己最近的那个簇头节点所在的簇，当其它节点都加入到簇中以后簇头节点会产生一个TDMA调度消息，簇头节点通过这个调度信息来控制非簇头节点在特定的时间传输信息，而非簇头节点不在自己传输的时间内会进入休眠模式来节省自身剩余的能量。传输了一段时间之后簇头节点就会对它收集到的那些数据进行整合并把整合后的内容发送到基站处。因此簇头节点的能量消耗是很大的，所以LEACH算法并不适合长时间的任务。在传输一段时间后，网络里的所有节点都会停止发送数据来进行下一次的簇头选举。图3-2LEACH算法流程图通过了解LEACH算法的选举过程，我们可以分析出虽然网络中的所有节点都有同样的机会担任簇头节点的位置，但是在选举时并没有考虑节点的具体分布，这就容易导致簇头节点的分布不均匀同时使得网络的剩余能量分布也不均匀，从而使得剩余能量少的节点过早死亡，使网络的覆盖并不完整，降低了网络的生存周期。3.3.2LEACH算法的改进算法对于LEACH算法在选举簇头的时候并没有考虑到节点当前剩余的能量多少的问题，在LEACH的改进算法当中把节点当选簇头节点的概率门限定为：(3-2)式子当中的表示节点在第r轮簇头选举当中剩余的能量，单位为J。表示当前网络的总能量，单位为J。k表示簇头节点的数量。把式3-2代入到式3-1中的处，就可以算出在LEACH改进算法中算出的节点的概率门限T（）。3.3.3HEED算法HEED算法也是以LEACH算法为基础进行了改进。它的特点是在进行簇头选举的时候优先考虑节点剩余的能量，而不是随机地选取簇头，这就可以让有更多剩余能量的节点选举成为簇首。进而让节点的能量消耗平均起来，以防止出现部分节点提前死亡的情况。延长簇首的工作时间和生存时间。HEED算法的簇头选举公式如下所示：(3-3)这两种算法都是针对能量而言更加有效的分簇算法。但是，对簇头节点的分布情况却没有任何改变，还是容易导致簇内的节点到簇头的距离和簇头到基站的距离有长有短，很不均衡。若是能够选择那些能量高的节点作为簇头节点就可以提升无线传感器网络的整体性能。HEED算法就是这样进行选举工作的。因为传感器网络是面对现实中的具体事件的，所以在监测的范围内若是没有进行中的工作就可以选择休眠。这个休眠的机制在传感器检测范围内发生事件的时候会使传感器自动工作而在没有事件发生的时候可以节省能量。引入了这种休眠机制使得无线通信模块通常能够处于关闭的状态，而传感器模块却是需要一直保持运作。这样大幅降低了传感器节点的能量消耗。这种休眠机制只要解决了传感器节点在休眠状态及活动状态之间转换的问题就可以很方便的延长节点的寿命问题。而要实现这种机制就必须使用运行阶段的网络拓扑控制算法进行控制。3.4本章小结本章首先对无线传感器网络拓扑控制算法介绍，主要包含了基于节点攻率控制的传感器网络拓扑控制算法和基于层次划分的传感器网络拓扑控制算法。对于基于节点功率控制的拓扑算法本章主要介绍了CONNECT/BICONN算法以及大规模数据聚类算法AP算法。对于基于层次划分的拓扑控制算法，本章主要介绍了LEACH算法和它的改进算法及HEED算法。为下一章在复杂电力场景下的LEACH算法仿真奠定了基础。仿真验证与分析LEACH算法流程：LEACH算法主要的流程包括以下3个阶段。选举簇头阶段我们假定在LEACH当中所有节点的初始能量都是相同的，那么为了让网络当中的节点的能量消耗保持平衡我们要在每轮选举的时候一共选举P*N个簇头节点。P代表了要选举出来的簇头节点在所有节点当中占有的比例。而N代表了所有节点的个数。在网络里的每一个节点都随机产生一个取值范围为[0，1]的随机数，若这个随机数大于T()那么这个节点就可以成为簇头节点。反之则不能成为簇头节点，这样一来所有的节点都很公平的拥有成为簇头节点的机会而能量的消耗也能维持平衡，（2）成簇阶段当网络当中的某些节点满足随机数大于T()这个条件进而成为了簇头节点以后，它们会发出消息，告诉没有成为簇头节点的那些传感器节点它们是簇头节点。在所有非簇头节点接收到这个消息以后，每一个非簇头节点都开始计算自己与簇头节点之间的距离并根据各个距离选择离自己最近的簇头节点来加入它。簇头节点在接收到非簇头节点发来的申请后允许非簇头节点加入自己的簇。在LEACH算法当中，簇头是整个簇的控制中心，控制着簇内节点之间的数据传输。在成簇时同样要考虑成簇后的稳定阶段。LEACH算法中每个簇头节点都建立起TDMA调度。在非簇头节点加入簇时，整个TDMA调度就发到每一个节点那里，每个节点按照TDMA调度方案接受调度进而进入稳定状态。稳定状态阶段LEACH算法的稳定阶段可以被分成很多帧。每一个节点发送数据都有严格的规定，每个节点每帧都只能被允许在指定的一段时间之内发送数据。而在不发送数据的时间段内，这些非簇头节点会进入到休眠状态来减少能量的消耗，但是簇头节点必须一直保持着工作的状态不能进入休眠状态。那是因为簇头节点一收到簇内的节点传输过来的数据就要执行数据融合的功能再把处理完的数据传输到基站去。而每个节点的传输时间是严格规定的、是相互错开的，所以簇头节点并没有可以进行休眠的时间，也就导致簇头节点的能量消耗非常大。LEACH算法能耗模型：图4-1无线收发电路的能耗模型由这个模型可知，每1bit数据传输所要消耗的能量有两个组成部分，分别是发射电路的损耗和功放电路的损耗。模型中的发射电路的任务是对信息进行编码调制、滤波调制等。功放电路的任务则是要按照特定的功率把调制完成的信号传输出去。接收电路的功能则与发射电路相反，是进行信息的接受、解调与滤波。功放电路包含了两种传输模型，针对不同的情况会采用不同的传输模型。节点根据接受者与发送者之间的距离远和近来采取不同的模型。距离近的用自由空间模型来传输数据，距离远的则用多路径衰减模型来传输数据。同时由于选择的模型不同，节点功率放大器的系数也就不同。要发送Lbit数据所消耗的能量可以通过公式4-1进行计算。（4-1）其中：代表了发送L比特的数据并传输d距离的能量消耗。是为了接受L比特数据所要消耗的能量消耗。是电路处理一个bit的数据所要消耗的能量。是自由空间模型内功率放大器的系数。是多径衰减模型的功率放大器的系数。(4-2)指自由空间模型与多径衰减模型之间的临界距离。实验参数设置表4-1实验参数参数类型参数值节点分布区域100m*100m，200m*200m，300m*300m汇聚节点坐标（50,175）节点总数100，200，300传感器节点的初试能量0.5J电路处理数据消耗能量50nJ/bit节点成为簇首的最佳选择概率p0.05最大迭代次数1000发送放大器能耗10pJ/bit/发送放大器能耗0.013pJ/bit/数据包长度6400bit控制包长度200bit数据融合能量消耗5nJ/bit/signal实验结果4.4.1节点分布面积为300m*300m1）节点总数为100个时图4-2节点死亡情况图4-3节点分布情况2）节点总数为200个时图4-4节点死亡情况图4-5节点分布情况3）节点总数为300个时图4-6节点死亡情况图4-7节点分布情况通过分析节点的死亡情况（图4-2、图4-4、图4-6），我们可以得出在覆盖面积及其它条件不变的情况下，节点总数越多，节点开始出现死亡的轮数越靠后并且所有节点全部死亡的轮数也越靠后。同时节点死亡的速度从100个节点时所发生的极速衰减再缓慢衰减到300个节点时近似匀速衰减可以得出：节点数目越多，无线传感网络的生存时间越长。通过分析节点的分布情况（图4-3、图4-5、图4-7），我们可以得出节点数越多，簇首越多，所划分的区域也就越多。4.4.2节点总数为200个1）节点分布面积为300m*300m时图4-4节点死亡情况图4-5节点分布情况2）节点分布面积为200m*200m时图4-8节点死亡情况图4-9节点分布情况3）节点分布面积为100m*100m时图4-10节点死亡情况图4-11节点分布情况通过分析节点死亡情况（图4-4、图4-8、图4-10），我们可以发现面积越小，节点出现死亡的时间越晚，同时节点全部死亡的时间也越晚；面积越小的图像线条的斜率越大，这意味着面积越小，节点死亡的速度越快。通过分析节点的分布情况（图4-5、图4-9、图4-11），节点区域数量并没有太大改变。由此可见覆盖面积的大小对节点的分布情况影响不大。总结与展望工作总结无线传感器网络是继互联网之后的一个重大网络，它是多学科交叉的新兴研究领域，涉及计算机、计算机网络、传感器等多个领域。无线传感器网络的发展必将对人类的生活造成重大的影响。拓扑控制是无线传感器网络中的关键技术，能够有效地减少传感器节点能量消耗、延长网络生存时间，逐渐成为了无线传感器网络研究领域的研究热点之一。本文将重点放在了拓扑控制算法的研究方面，重点研究了层次型拓扑控制算法，主要研究内容如下：1）本文介绍了无线传感器网络的构成及特点、性能指标；无线传感器拓扑控制技术及拓扑结构的种类。2）本文介绍了基于节点功率控制和层次划分的拓扑控制算法，主要有CONNECT/BICONN算法、AP算法、LEACH算法及其改进型和HEED算法。3）用matlab对LEACH算法进行了仿真，对LEACH算法有了更深入的了解。展望拓扑控制算法是无线传感器网络研究领域的重要一环。本文对于拓扑控制算法的研究还不够全面和深入，提出的拓扑控制算法也没有经过实际应用的检验，今后还需要继续研究。（1）LEACH算法在簇头选择时，需要进行大量的运算，占用较多的存储空间和算法执行时间，怎样提高算法的执行效率，是下一步研究的重点。（2）提出算法考虑的都是静态的网络环境，这种网络环境相对比较简单，在实际应用中有着一定的局限性。在今后的工作中，将对算法在动态环境中的有效性进行验证，并研究如何提高算法在动态网络环境中的可靠性。（3）提出的算法通过基站进行相关信息的迭代计算并产生成簇信息，这种集中控制产生簇头的方式在较小规模的网络中，能够有效地发挥作用。但是，当无线传感器网络的规模变大，传感器节点的数量变多，将使基站集中控制产生簇头的方式变得越来越难，甚至失效。为了适应大规模无线传感器网络的应用，应提出新算法或者改进算法成为基于局部信息的分布式高效算法。希望未来能够有更高效、有更丰富适用场景的算法出现来便捷人们的生活让世界享受科技带来的便利。参考文献[1]马威风.无线传感器网络拓扑控制算法研究[D].长春理工大学,2018.[2]蒋国帅,程璞.基于无线传感器网络的拓扑控制算法[J].科技视界,2016(25):231+239.[3]李安莹.无线传感器网络拓扑控制技术的研究[D].沈阳理工大学,2016.[4]张先菊.无线传感器网络的拓扑控制技术研究[D].吉林大学,2015.[5]阳瑞琦.无线传感器网络分簇拓扑控制技术的研究[D].中南大学,2013.[6]王蕊.无线传感器网络拓扑控制技术研究[D].哈尔滨工程大学,2007.[7]杨军.无线传感器网络拓扑控制技术研究[D].江苏大学,2006.[8]田权,杨桥桥,陈宇.基于传感通信技术的电力物联网应用[J].农村电工,2021,29(03):37-38.[9]李云,周娴,尤肖虎,等.IMECN:一种新的无线传感器网络拓扑控制算法[J].电子学报,2010,38(001):48-53.[10]魏永红,李孝忠.分簇及局部优化的无线传感器网络拓扑控制算法[J].天津科技大学学报,2010,25(2):68-71.[11]赵学健,庄毅,欧阳键.一种适用于无线传感器网络的拓扑控制算法[J].计算机科学,2009.[12]刘林峰,金杉.OverviewofTopologyControlAlgorithmsinWirelessSensorNetworks无线传感器网络的拓扑控制算法综述[J].计算机科学,2008,35(003):6-12.[13]李德识,范创伟,陈健.一种功率可调的带状传感器网络拓扑控制方法:,CN102158938B[P].2014.[14]YANGMengning.无线传感器网络中改进的HEED分簇算法[J].重庆大学学报自然版:英文,2012.[15]张建辉.无线传感器网络拓扑控制研究[D].浙江大学,2008.[16]张学,陆桑璐,陈贵海,陈道蓄,谢立.无线传感器网络的拓扑控制[J].软件学报,2007(04):943-954.[17]余向阳.无线传感器网络研究