异构无线传感器网络中一种高效簇头选取方法

1、异构无线传感器网络中一种高效簇头选取方法摘要众所周知，传统的传感器节点一般使用非循环利用的电池，可以提供的能量不够充足，所以如何维持网络长时间处于活动状态是无线传感器网络中最关键的问题。实际上，由于网络在运行过程中节点能量的不均匀消耗使得出现节点异构的问题，异构性将会使整个网络变得极其不稳定。传感器网络中的簇为动态的，主要是由邻近的传感器节点连接而成，其中存在一个簇头节点，负责将周围的节点数据接收过来并进行聚合。由于目前物联网的大量普及，所以设计新的路由协议来延长传感器网络寿命迫在眉睫。本文在原有的基础上提出改进了可以稳定簇头的选举协议，简称P-SEP，主要原理是经过消耗平衡能量来使无线网络中

2、首个死亡节点的寿命有所延长。P-SEP考虑两级异构节点，即高级节点和正常节点。这两种类型的节点都有可能被选为簇头，分别利用不同的策略在高级节点和正常节点之间进行簇头选举。仿真实验表明在相同参数设置下P-SEP比SEP更好地平衡了网络中的能量，延长了稳定期和网络寿命。 关键词：无线传感器网络 寿命 稳定期 高效 簇头 聚类 能耗IIIAn efficient cluster head selection method in heterogeneous wireless sensor networksABSTRACTAs we all know, conventional sensor nodes

3、 generally use non-recyclable batteries, which can provide insufficient energy. Therefore,how to prolong the network lifetime is a key issue in wireless sensor networks. In fact,the entire network is extremely unstable due to the heterogeneous energy consumption of nodes. In wireless sensor networks

4、,a cluster is dynamically composed of adjacent sensor nodes. And there is a cluster head which receive and aggregate the datas from surrounding nodes.Because of the popularity of the Internet of Things now,we should design a new routing protocol to prolong the wireless network lifetime. In this text

5、, This paper proposes an improved election protocol, p-sep for short, which can stabilize cluster heads on the basis of the original one. The main principle is to prolong the life of the first dead node in the wireless network by consuming equilibrium energy. Two-level heterogeneity of nodes,advance

6、d nodes and normal nodes is considered in P-SEP. Both types of nodes are likely to be selected as cluster heads. And different stategies are used to select cluster head between the advanced nodes and the normal nodes. Simulation experiments show that P-SEP is better than SEP in balancing the network

7、 energy and prolonging the stability period and network lifetime under the same parameters. Key words: Wireless sensor network Lifetime Stable period Efficient Cluster head Clustering Energy consumption目录第一章 绪论21.1 研究目的与意义21.2 国内外研究现状21.3 论文主要内容和组织结构3第二章 基于分簇的无线传感器网络路由协议52.1 LEACH协议62.2 LEACH-C和LEAC

8、H-F协议72.3 DCHS协议82.4 CONCH协议92.5 SEP协议102.6 M-SEP协议11第三章 延长稳定期的簇头选举算法133.1 网络模型及问题描述133.1.1 网络部署模型133.1.2 能量消耗模型143.1.3 问题描述163.2 延长稳定期的簇头选举算法163.2.1 算法描述163.2.2 算法实施流程213.2.3 算法性能分析28第四章 实验设计与分析304.1 实验环境及参数设置304.2 延长稳定期的簇头选举算法实验结果314.2.1 高级节点和正常节点的能量差异系数的影响314.2.2 网络中总节点数的影响324.2.3 高级节点占总结点的百分比数的影

9、响334.2.4 与其它算法比较34第五章 结束语40参考文献41第1章 绪论1.1 研究目的与意义无线传感网络，其主要构成部分是许多处于静态或者动态的传感器，这些传感器可以组织多种连接方式，从而构成无线传感网络。该网络具备感知采集信息、整理分析数据、传输结果等功能，可以接收并处理网络覆盖范围内的信息，经过加工处理再将信息返回至该网络的使用者。无线传感器网络以其先进的技术与概念，处于行业与时代的前沿，目前，传感器网络技术及其相关应用技术已经作为21世纪最重要的科学成果之一。大众可以借助此项技术更为方便地去感受网络世界，也大大拓展了网络技术领域所涉及的范围，进一步提高了人们发现世界，认识世界，改

10、造世界的能力。目前传感器节点趋向于集成化与微型化，节点能量一般使用非循环利用的电池，可以提供的能量不够充足，此外因为条件约束电池不能进行更换，也就是说整个网络寿命就取决于传感器节点的可以使用的能量。因此如何优化网络能耗，怎样尽可能地提高网络的生命周期是传感器网络路由协议设计要考虑的重要因素。根据已有研究，现在许多国家已经具备了比较成熟的无线传感器网络路由协议，主要有以下两种类型：层次路由协议与平面路由协议。其中，层次路由协议中创造性地引出了一些新的想法：聚类就是把指定的节点当做簇头，再将这个簇头作为中心节点把数据信息传输到基站。由于聚类方法，这种协议可以显著提高通信效率与能量利用率，因此成为研

11、究开发新的协议的基础。LEACH作为首个引用分簇理念的层次路由协议，网络中任意一个传感器节点都有相同的概率被选为簇头，可以使用分别让每个节点当簇头的办法来使平衡各节点的能量消耗接近平衡，然而由于随机选取簇头的方法引发了能量黑洞问题。近几年来，降低节点能耗、平衡负载能量和延长网络生命周期一直是人们研究中的关注重点。综上，设计高能效、能量负载均衡路由协议至关重要。本文就以如何高效的选举出一些节点作为簇头为研究工作的主要目标。结合已有的层次路由协议，综合考量平衡系统的能量消耗与增大网络生命周期等因素，提出高效的簇头选举协议。1.2 国内外研究现状作为本世纪最受追捧的研究课题之一，无线传感器网络在上世

12、纪末被美国商业周刊提名为新世纪的重大研究技术1。首先从国外研究来看：最早的现代传感器网络研究起源于1980年美国国防部高级研究计划署DARPA开展的分布式传感器网络DSN项目2。本世纪之初，英特尔公司美国发布了基于传感器网络技术的信息技术发展的系列相关规划，在自此以来，该公司就一直在大力开发研究微型传感器网络在临床医学、交通、海底环境监测等方面的应用。2008年第一届欧洲“无线传感器网络论坛”提出了要研究一种用来控制机器人或者能够参与事故救援的智能传感器3,4。近年来，美国众多高等院校都陆续着手对无线传感器网络领域的研究,例如：麻省理工学院林肯实验室对低飞航空器的声学追踪实施测试床的研发5。国

13、内对于无线传感器领域的研究对比国外较迟，04年在中国召开的青年计算机科技论坛活动，是国内首次关于该技术领域的专题报告会。06年国家发布国家中长期科学与技术发展规划纲要，纲要中提到两项与传感器网络相关的技术，分别为智能感知技术与自组织网络技术。2010年的远景规划和“十二五”都将其列为重点扶持的信息产业。除此之外，国内许多研究机构包括中央科技院、北京大学与复旦大学等都开展了传感器网络领域方面的研究。LEACH层次路由协议作为首个引用分簇理念的算法6。但是由于该协议自身的随机性问题容易导致簇头节点数量和位置分布不够合理，所以学者们研究了很多新的路由协议来改变这一弊端，例如：LEACH-C协议7，D

14、CHS协议8等。最新的路由协议中或多或少也存在某些因素的制约，目前国内仍在继续探索开发传感器网络的路由协议。1.3 论文主要内容和组织结构在本文中，我们从能效和寿命出发，引入了比较新颖的簇头选举协议：延长稳定期的稳定选举协议。实际传感器网络中由于运行时能量消耗不均匀或是由于应用场合要求传感器节点承担不同角色造成网络异构，所以我们考虑进节点的异构特性来设计新的算法，把网络节点划分成高级与正常节点，两种类型的节点在初始能量上有所不同，即能量异构。本文的主要内容如下：1. 文章对相关工作做了详细的介绍。提出路由协议的分类，并着重研究了基于分簇理念的路由协议。并对每一种分簇协议的优缺点进行总结。为新算

15、法的提出做好前提工作。2. 针对已有协议的缺点，如能耗不均、寿命不长等提出新的簇头选取协议：延长稳定期的稳定选举协议P-SEP。P-SEP算法主要贡献如下：（1）在每轮循环中随机选取簇头；（2）针对不同类型节点选择不同的阈值，来避免低能量节点在下一轮中被选为簇头；（3）考虑与簇头相关联的节点，优化簇头之间的距离；（4）不同类型的节点被选为簇头的过程中不考虑优先级，只要满足该节点的能量大于零、随机数小于阈值、最近轮中未被当选为簇头这三个条件就可以被选为簇头；（5）P-SEP考虑每个节点的平均能量来提高能效。3. 运用Matlab软件对本文所述算法开展仿真实验，与已有的理论协议：稳定选举协议（SE

16、P）在结果上进行对比，得出P-SEP协议能更能均衡网络中所有节点的能耗，做到最大化网络生命周期。本文的组织结构：第一章绪论。主要介绍了研究无线传感器网络的课题背景与研究意义，并对国内外研究现状进行简要阐述。最后大致说明了论文的结构框架与研究内容。第二章根据基于分簇理念的层次路由协议，对三种比较经典的层次路由协议展开叙述，着重说明了每种路由协议的簇头选举过程以及优缺点。为提出新的簇头选举算法提供理论支撑。第三章延长稳定期的簇头选举算法。介绍了选举簇头的详细过程，在很大程度上解决了无线传感网络中节点能量消耗不平衡这一问题。第四章实验设计与分析。将第三章提出的算法在Matlab平台上实现，并将结果与

17、稳定选举协议SEP的结果进行对比得出P-SEP优于现有协议的结论。第五章总结。主要对本文的研究成果进行概括说明。第2章 基于分簇的无线传感器网络路由协议根据传感器网络结构不同，路由协议包括平面路由协议和层次路由协议：平面路由协议适用于所有节点在路由时具有平等地位的情况下，而层次路由则是依据分簇的理论与方法将节点实行层次划分，（又称分簇路由），层次路由的结构如图1，首先簇内的成员节点主要负责将数据的采集结果发送至对应的簇头，簇头的作用则是将所有成员节收集的数据进行汇总融合，最后将汇总结果发送至基站。成员节点与簇头以及簇头与基站之间大都是直接进行通信，部分节点也可以选用多条路由途径进行通信。簇成员

18、基站簇头簇图1 层次路由的结构分簇路由协议的优点：1. 簇头能进行数据融合。处于同一簇内的成员节点因为距离相近，成员节点的数据采集结果很可能出现重复，在簇头进行数据融合能够得到最高的效率。2. 每簇的成员节点发挥的作用比较简单，通过节点传输到的数据可被簇头直接接收，从而极大程度上节省了由于维护路由信息所需的能量消耗。3. 分簇路由中的簇头能够对簇内成员的行为：加入或退出，迅速作出反应，提高了网络效率。根据图2，簇的路由协议包括两个阶段：设置阶段与稳态阶段。设置阶段用于选取簇头并形成簇，稳态阶段节点在分配的时间里将感知的数据传送到相应的簇头，簇头将所有节点采集的数据进行融合，整理后传输至基站。由

19、此分簇路由的设计步骤有三部分：（1）簇头的选取：簇头选取得当，将会节省不少能耗。所以在选举簇头时需要考虑以下因素：剩余能量、相邻节点数、节点拓扑信息、到基站的距离等。（2）簇的形成：确定好簇头后，其他非簇头节点要选取各自的簇头，并成为其成员节点。最终网络会被划分成为很多节点集群（每一集群簇头和以都包括簇头以及其所有成员节点）。簇形成阶段要考虑：簇包括的节点规模与范围、簇头之间是否负载均衡。（3）簇的路由：在簇形成之后，每个成员节点便可以向簇头传输所采集到的信息，将所有节点采集的数据进行融合，整理后传输至基站，传输方式包括单跳与多跳。CH簇形成一轮稳态阶段时间轴设置阶段图2 分簇路由的操作时间图

20、综上，形成簇和簇路由的关键是选取合适的簇头，所以如何选取恰当的簇头，尽可能延长无线传感网络的寿命，是本文研究的重要之处。下面我们向大家展开叙述三种比较典型的路由协议：2.1 LEACH协议孙中皋在2011年的无线传感器网络能量高效路由协议研究一文中提到基于分簇的层次路由协议LEACH（低能量自适应聚类层次结构）9。这是最早的层次路由之一，之后的许多改进协议都是基于LEACH上进行研究的。为避免簇头因负载过重而过早失效，LEACH主要是以轮次的方法，根据周期随机地选出簇头。文献9中描述了LEACH协议的具体过程：1 簇头选取无线传感网络中的每一节点都产生一个随机数，且都处于0,1区间，然后通过公

21、式(2.1)计算出第r轮次中的一个阈值T(n),并将生成的数字和T(n)对比，若节点的随机数比阈值低，则该节点可以作为簇头（CH）。(2.1)公式2.1中，p代表当选为簇头的概率（即簇头占节点总数的概率），r代表轮次，G代表最近1/p轮中没有当选簇头的节点集合，在最近的1/p轮中，还未当选簇头的节点才有概率在本轮中当选簇头。2 簇形成选取簇头后，簇头便会向整个无线传感器网络中传递信息，非簇头节点会根据接收信号的强度大小，选择信号强度最大的簇头，加入其中成为其成员节点。3 簇的路由簇形成之后，成员节点与簇头以及簇头与基站之间大都是直接进行数据传输，簇内的成员节点主要负责将数据的采集结果发送至对应

22、的簇头，簇头将所有成员节收集的数据进行融合，最后将汇总结果发送至基站。LEACH路由协议的优点：随机选取簇头的方式避免簇头节点过早死亡，进一步延长了传感器网络的寿命，采用单跳通信传输延迟小。缺点：该选取簇头的方法未将节点的剩余能量予以考虑；每轮通过随机数选取的簇头在数量和位置上都有很大的随机性；p值的确定困难，即无法确定网络中最佳簇头个数；容易产生能量黑洞；可扩展性差。2.2 LEACH-C和LEACH-F协议LEACH-C与LEACH-F协议均在LEACH协议的基础上加以改进的10，都是利用集中式算法来选取簇头。LEACH-C协议的开展过程：分簇前，无线传感器网络里的全部节点都需要向基站提供

23、位置与剩余能量信息，基站凭借接收的全部节点数据，分析获得所有节点的平均能量，候选簇头节点可以从剩余能量高于平均能量的节点中选取，随后按照节点与簇头距离最小的准则在候选簇头节点集中选出最符合条件的簇头，基站将分簇信息广播至全网。LEACH-C协议优点：簇头选择综合分析了整个网络的信息，选取的簇头数量稳定、簇头位置分布合理；考虑了节点的剩余能量因素。缺点：由于选簇头之前，基站需要收集并处理全网的数据信息，所以增大了网络开销。LEACH-F协议的开展过程：与上述协议原理相似，不同之处为：一旦簇结构形成，就不能再改变，在每轮循环中各节点轮流当选簇头。LEACH-F协议的优点：每轮循环前不需要提前构造簇

24、结构，从而节省了簇形成阶段发送控制信息的无关消耗。缺点：由于簇结构没有发生变动，导致节点没有办法选取与距离最近的簇头通信，从而增大了成员节点发送数据到簇头所产生的能耗。2.3 DCHS协议针对LEACH协议存在的缺陷：随机选取簇头，未将节点的剩余能量纳入研究，Handy M,Haase M,Timmermann D提出了改进算法，称为具有确定性簇头选择的低能量自适应聚类层次结构（LEACH-DCHS）8。该具有确定性簇头选择的LEACH协议在1中的作者也提到了。LEACH-DCHS将节点的剩余能量予以考虑，并引入了剩余能量因子，在选取簇头计算阈值时使用了不同于公式(2.1)的计算方法：（如公式

25、2.2）选取节点生成的随机数小于该阈值T(n)的节点作为簇头(2.2)其中代表节点的剩余能量，代表节点初始能量，p含义为节点当选成簇头的概率（即簇头占节点总数的概率），r代表轮次，G代表最近1/p轮中没有当选簇头的节点集合，在簇形成和簇的路由阶段是和LEACH方法是一致的。在T(n)中看到Ecurrent节点剩余能量会随着轮数的增加而下降，那样阈值T(n)会变得越来越小，则节点当选为簇头的希望也会随之变小，这样会造成选取出的簇头数量减少，从而无线传感网络的生命周期也会缩短，所以在2,3中对阈值T(n)做了进一步的改进：(2.3)式2.3中代表某节点连续没有当选簇头的频次，在节点成为簇头时，变为

26、0。2.4 CONCH协议对于LEACH协议里簇头数量不足，簇头位置分布不合理等问题，尽管DCHS协议中拟对节点剩余能量进行研究来对存在问题进行改进，但仍存在簇头数目无法维持在簇头数的最优值附近很小的范围内。所以提出了一种新的协议：基于最优分簇数目的分布式分簇算法（CONCH）9。该算法的核心是将簇头选举过程分成两步：首先利用LEACH的方法选举举出临时簇头，并且保证临时簇头的数目大于最优簇头数。然后根据节点的到基站的距离和节点的剩余能量从临时簇头里选出最优簇头。由此可以使簇头的数目变得相对合理和簇头位置分布变得相对均匀。CONCH协议的工作过程：1. 选举临时簇头，保证临时簇头数目大于最优簇

27、数。簇头选取方式与LEACH协议相差不大，若节点的生成随机数小于阈值，就被选为临时簇头。阈值T计算公式：(2.4)其中p为被选为簇头的概率，r为当前循环的轮数，G为最近1/p轮中未被选为簇头的节点集合，然而这里的p不是LEACH中的p，公式(2.4)中,目的是为了使得选举出的临时簇头数目大于。2. 从个临时簇头中选举出个最优的簇头：将临时簇头节点按照距离基站的距离由小到大进行排序，得到一个序列。计算，以为步长对排序序列进行步搜索，每步中只选择剩余能量最大的那个临时簇头作为最终的最优簇头，因此最后能够得到个簇头。剩下的个临时簇头被自动归为普通节点。3. 簇形成：每个非簇头节点根据最短距离加入到相

28、应的簇。4. 簇路由：非簇头节点在分配的时隙内将l比特数据发送到簇头，簇头将接收到的数据与自身数据融合之后发送给基站。CONCH协议的优点：避免随机性导致的低能量节点被选为簇头；簇头均匀分布在网络中，而且数量相对来说很稳定；网络中的能耗更加均匀地分布在所有节点上。2.5 SEP协议SEP协议是第一个用于异构的簇头选取协议，除了节点初始能量不同之外和同构网络类似的。Smaragdakis G,Matta I,Bestavros A在a stable election protocol for clustered heterogeneous wireless sensor networks一文中提

29、出了一种用于异构传感器网络中的簇头选取方法11：首先定义n为网络中的节点总个数，m为高能量节点即高级节点占所有节点的百分比数，所以高级节点的数量是mn，低能量节点即正常节点的个数为n(1-m)。定义Popt为网络中节点被选为簇头的概率值，那么nPopt就是网络中平均一轮中的簇头数量。由于节点的初始能量异质使得节点的能量水平不同，为了能够延长稳定期，使得每轮中的能量消耗做到最低，就要让高级节点比正常节点更加频繁地成为簇头。所以就不能像LEACH那样对所有的节点设置相同的选举概率和阈值，要分别对高级节点和正常节点设置选举概率和阈值。权重系数等于每个节点的初始能量与正常节点初始能量的比值。对于正常节

30、点的阈值计算：(2.5)(2.6)其中Pnrm是正常节点的加权概率，a是高级节点和正常节点之间的附加能量因子，G是可以成为CH的正常节点集。只对正常节点起作用，这个阈值公式保证每个正常节点每轮次就要成为一次簇头。我们称这个轮次为异构网络的时期，也叫异构时期。高级节点的阈值计算如下：(2.7)(2.8)其中Padv是高级节点的加权概率，G是可以成为CH的高级节点集。只对高级节点起作用，这个阈值公式保证每个高级节点每轮就要成为簇头次，即每轮就要成为一次簇头。我们称这个轮次为子时期，显然一个时期（异构时期）包括个子时期。2.6 M-SEP协议由于SEP只考虑了两级节点的概率值，所以Singh D,P

31、anda CK在Performance analysis of modified stable election protocol in heterogeneous wsn一文中提出了新算法M-SEP12，该算法在SEP的基础上考虑了网络中的能量问题。所以正常节点和高级节点被选为簇头的阈值更改为：(2.9)其中，M是可以成为CH的正常节点的集合，Eavg（r）是整个网络的平均能量，Ecurrent（n）是节点n的当前能量值。(2.10)(2.11)其中，M是可以成为CH的高级节点的集合(2.12)第3章 延长稳定期的簇头选举算法3.1 网络模型及问题描述3.1.1 网络部署模型假设在大小为的矩

32、形网络区域内，均匀分布个传感器节点，这节点定期将检测的对象信息发送给基站。对网络的设定如下：(1) 节点在初始能量上异构，分为两级能量异构：高级节点和正常节点。设区域中总结点数为n，初始化时高级节点比正常节点多配备一定的能量，用来表示高级节点和正常节点之间的能量差异系数。设为正常节点的初始能量，则高级节点的初始能量为。并设高级节点占总结点数的百分比为m，因此网络中高级节点数为mn，正常节点数为n(1-m)。(2) 所有的节点和基站的位置保持不变。(3) 高级节点的位置是提前设置好的，正常节点的位置随机分布。基站的位置为了方便，放置于区域的中心位置。(4) 节点具备与基站一跳通信的能力，知道基站

33、的位置信息。(5) 节点能根据接收信号的强弱估算和发送方之间的距离，并能根据距离远近自适应的调节自身的发送功率。(6) 网络周期性的采集数据。在每一轮中，所有的非簇头成员都要向对应的簇头发送l比特的数据，簇头将所有簇内成员数据以及自身数据融合成l比特在发送给基站。(7) 设r为网络运行的轮数，每一轮都由设置阶段和稳态阶段构成。如图3为满足上述网络设定的100个节点初始分布图，其中表示基站，表示高级节点，表示正常节点。图3 节点初始分布图3.1.2 能量消耗模型集群中的节点为了将感知的信息发送到簇头，簇头为了将自身和其成员数据融合之后发送到基站，都需要考虑每个节点的无线电耗散的能量。所以该节就描

34、述了传感器网络中的每个节点在发送或接收数据时的能量消耗。如图4的无线电能量耗散模型，该模型由发送电路、放大电路和接收电路组成。发送电路发送放大器L比特数据包接收电路d图4 无线电能量耗散模型在这里我们定义和分别为网络中发送器和接收器电路消耗的能量，而且每个节点都具有在距离d上发送L个比特消息的可接受的信噪比(SNR)。发送器在距离d上发送L比特消息时消耗的能量为：(3.1)其中Eelec是发送器传输每比特数据到接收器所消耗的能量，d是发送器到接收器之间的距离，和取决于我们使用的发送器放大模型，当时使用由表示的自由空间（fs）（d2为功率耗散系数），当dd0时使用由表示的多径衰落（mp）（d4为

35、功率耗散系数）。(3.2) 接收器消耗的能量公式为：(3.3)除了以上的节点在发送或接收数据时需要消耗能量，簇头节点在融合自身和其成员节点发送来的数据时也需要消耗能量4，其能量公式为：(3.4)其中M为集群中成员的数量，为簇头融合单个成员节点发来数据的能量消耗。3.1.3 问题描述层次路由具有高效、扩展性好和网络延时小等优点，以最大化网络的生命周期为目标。分簇路由协议中最重要也是最关键的一步就是簇头的选取，在关于无线传感器网络的研究中，提出了很多基于分簇的簇头选取机制，但仍存在很多问题：(1) 分布式分簇算法中的随机选举簇头，导致簇头数目和位置分布都不够合理。典型的LEACH协议，很容易造成网

36、络中能耗不均衡的问题。(2) 集中式分簇算法中，例如，LEACH-C和LEACH-F协议。虽然较好的改善了分布式分簇算法中的簇头选举的随机性问题，但是由于需要收集全网的信息，增大了网络开销。(3) 分布式分簇算法中属性权重问题，为了解决簇头选举的随机性问题，有的协议例如DCHS协议将节点的剩余能量等多个属性因子引入到阈值计算中去，但是对这些属性进行综合时由于通常采取主观经验的方法确定各属性因子的权重系数，这种方式适应能力很差。(4) 负载均衡问题：无线传感器网络中的分簇路由中的数据流量分布极其不均匀，距离基站越近，承载的数据量越大，节点的能耗越高。所以这些节点往往最先死亡，造成网络路径不通，从

37、而影响网络的运行时间。因此，为了延长网络的运行时间，设计算法时必须要考虑能量均衡的问题。(5) 距离与能耗问题：网络中任意两个节点之间传输数据消耗的能量与传输距离的平方成正比，传输距离越大，消耗的能量越大，所以在设计簇头选举协议时要考虑数据包的传输距离，非簇头成员到簇头成员的距离以及簇头到基站的距离如何做到平衡使得总的传输消耗尽可能最小。3.2 延长稳定期的簇头选举算法3.2.1 算法描述1. 最佳簇数的选择延长稳定期的簇头选举算法P-SEP协议，在选簇头之前首先进行最佳簇头数量的计算，这是每个时期每轮中能量消耗能够降到最低并且使得能量消耗均匀分布在网络中的所有传感器节点上的重要前提。如何计算

38、最佳簇数也就是簇头数量，就要用到传感器网络中经典的能量消耗模型以及数学中的微分公式。这里我们使用3.1.2节的能量消耗模型并进行计算分析。最佳簇数计算基于3.1.1节的网络模型，并且假设区域中所有节点到Sink的距离小于等于。由3.1.2节的公式(3.1)、(3.3)和(3.4)得出一轮中某一个簇头节点消耗的总能量，包括接收簇内成员数据消耗的能量、数据聚合消耗的能量以及发送数据消耗的能量。(3.5)其中k为簇数，为簇头到Sink的距离值。对于非簇头节点，由公式(3.1)计算该节点发送数据消耗的能量：(3.6)其中为非簇头节点到所属簇头的距离。由于基于的网络模型中提到区域中所有节点均匀分布，所以

39、有如下公式：(3.7)(3.8)其中为节点分布的函数。每轮中一个簇消耗的总能量为：(3.9)所以网络中总消耗是：(3.10)最后将对k进行微分并等于零，就可以得到最佳簇数即最佳簇头数量：(3.11)其中只与网络中总的节点数量n有关，所以我们在设置完网络区域中传感器节点总数之后就可以通过公式(3.11)计算出最佳簇头数量，这对于下一步寻找簇头来说是很关键的。如果没有以最佳簇头数量计算公式结果去选择簇头就会出现网络中每轮中的能量消耗较于最佳方式选择增大，这不利于延长网络寿命和增长稳定期的目标。计算出最佳簇数之后便也可以计算出最佳选举概率:(3.12)2. 高级节点的分布高级节点手动配置其位置，首先

40、算出理论上平均分配高级节点，平均一个多少平方米需要有一个高级节点，并且保证，其中i表示每个内分布有多少个高级节点。这样就不会出现由于高级节点随机分布而导致部分高级节点分布地很紧密。高级节点分布过于密集就会出现能耗消耗不平衡从而达不到延长稳定期的目的。3. 加权概率由公式(3.12)即可计算出最佳簇头选取概率，即一个节点具有的概率成为簇头。任意一个节点在一个时期内只能被选为一次当簇头。异构网络（高级节点和正常节点）可以转化成一个具有个正常节点的同构网络，因为两个网络的总能量都是。所以我们可以得到正常节点的加权概率：(3.13)因此异构网络中一个时期内每轮中簇头的平均数量不仅可以用表示，还可以用表

41、示。高级节点的加权概率为：(3.14)其中为高级节点的初始能量，等于。为第r轮中所有节点的平均能量,的计算公式如下：(3.15)其中是第r轮中节点Nj的能量。4. 用阈值选择簇头我们用和分别来表示正常节点和高级节点在第r轮中被选为簇头的阈值。阈值与加权概率密不可分。正常节点的阈值表达式如下：(3.16)其中只适用于正常节点，是该时期最近轮中未被选为簇头的正常节点集合，所以任意一个正常节点都是每轮就要变成簇头，即每轮就要成为一次簇头。是第r轮中从第一个节点到第i个节点之间所有活动节点的平均值，的计算公式如下：(3.17)同理对于高级节点阈值计算如下：(3.18)其中只适用于高级节点，是最近轮中未

42、被选为簇头的高级节点集合，所以任意一个高级节点将每轮次就要成为簇头一次。5. 距离计算在我们研究的算法中仍然采用单跳路由方式，在完成簇头选取之后，就是如何成簇的问题了，首先非簇头节点选择距离自己最近的簇头并将数据直接以单跳形式发送到簇头，然后所有的簇头发送融合之后的数据到基站。计算每个非簇头节点到基站的距离：(3.19)计算每个非簇头节点到所有簇头的最短距离：(3.20)其中和分别是基站和簇头的笛卡尔坐标，然后从公式(3.19)和(3.20)中得到最小的距离就是非簇头节点发送数据到目的节点的距离值：(3.21)从公式(3.19)、(3.20)和(3.21)可知所有的非簇头节点通过找到距离它自己

43、最近的簇头（或基站），然后将数据直接传送到簇头（或基站）。6. 能量消耗P-SEP算法采用3.1.2节的能量消耗模型，簇内成员发送信息到簇头，簇头接收来自其簇内成员发送来的数据以及簇头将聚合后的数据信息发送到基站，这些过程都需要消耗能量。用公式(3.1)和(3.3)就可以很轻松的计算出上述过程中消耗的能量，在计算出每个节点消耗的能量之后就要及时更新节点的能量。对于非簇头节点，由于只在发送数据到簇头的过程中消耗能量，所以更新之后的能量为：(3.22)对于簇头节点不仅在接收来自簇内成员发送来的数据的过程中消耗能量，而且在将自身和簇内成员数据聚合后的数据发送到基站的过程中也需要消耗能量，所以簇头更新

44、之后的能量为：(3.23)其中是第r轮中第i个节点的当前能量。3.2.2 算法实施流程1. 部署网络：生成由n=100个节点和一个Sink节点构成的网络。图5即为网络构建的算法流程图。图5 网络部署流程图在构建网络模型时，最先给定网络参数：传感器节点总数n=100、网络区域的大小xm=100,ym=100、高级节点占节点总数的百分数m=0.1。其次就是对n个节点进行编号，将编号为i=1:10:100的定为高级节点，高级节点的位置坐标手动配置，正常节点的坐标用rand函数随机生成，Sink节点的位置为了方便起见，定为网络区域的中心。最后，利用plot函数画出100个节点以及Sink节点，并将10

45、0个节点的坐标数据保存到txt文件中去，这样做是为了避免每次测试的时候都要重新随机生成节点位置，保证每次测试时都使用的同一个网络部署模型。2. 网络初始化：对全部网络参数进行初始化操作，并从.txt文件中读取100个节点的位置信息。图6即为网络初始化流程图。图6 网络初始化流程图在完成网络部署之后，重新建一个m文件，将.txt文件中的数据读入到工作区中，这样我们就可以方便使用节点位置数据。初始化网络参数：xm=100,ym=100,n=100,p=0.1,m=0.1,a=1,rmax=4999,E0=0.5,Eelec=50*0.000000001,Efs=10*0.000000000001,

46、Emp=0.0013*0.000000000001,EDA=5*0.000000001。写一个循环将n个节点都进行初始化：坐标初始化和能量初始化。从节点编号i=1开始，满足i=100的条件之后，从txt文件中读取i节点的坐标信息赋给字段S(i).xd和字段S(i).yd。将节点i的G字段全部初始化为0，即S(i).G=0，意为节点i还未被选为簇头过；将节点i的type字段全部初始化为N，即S(i).type=N，意为节点i为非簇头节点。然后就需要判断该节点i是否是高级节点，如果是，则将该节点的能量初始化为E0*(1+a)，ENERGY字段初始化为1；如果不是，则将该节点的能量初始化为E0，EN

47、ERGY字段初始化为0。这里的ENERGY字段只是用来区别高级节点和正常节点的，ENERGY=1表示高级节点，ENERGY=0表示正常节点。知道i=101不再满足条件i0，就要根据最短距离优先选择距离该节点最近的簇头，由于在簇头选取阶段已经选择出簇头数目并进行了编号，所以这里用一个for循环从c=1到c=cluster-1结束，找到距离最近的簇头，并记下来该簇头的序号以及节点i到最近的簇头的距离。接下来就是根据距离计算节点i发送数据到簇头的能耗ETX，簇头min_cluster的接收节点i发来的数据消耗的能量ERX和融合节点i发来的数据消耗的能量EDA。P- SEP伪代码如下：输入：n,rma

48、x,输出:;1. 设置高级节点位置，正常节点随机分布2. for r=1 to rmax do3. ;4. 用公式(3.13)、(3.14)和(3.15)计算5. for i=1 to n do6. 用公式(3.16)、(3.17)和(3.18)计算7. 8. for j=1 to i do9. if (distanceds) then10. ,即正常节点被选为簇头11. 用公式(3.19)、(3.1)和(3.22)计算该节点到基站的距离、发送 数据到基站消耗的能量以及更新剩余能量12. end if13. end for14. end if15. 16. ,即高级节点被选为簇头17. 用公式

49、(3.19)、(3.1)和(3.22)计算该节点到基站的距离、发送 数据到基站消耗的能量以及更新剩余能量18. end if19. end for20. for i=1 to n do21. 22. 用公式(3.21)、(3.1)和(3.22)计算出非簇头节点的最短距离和发送数据到所属簇头或基站时消耗的能量，并更新剩余能量23. 用公式(3.3)和(3.4)计算每个非簇头所属的簇头节点接收和聚合来自簇内节点消耗的能量,并更新簇头节点的剩余能量24. end if25. end for26. end for3.2.3算法性能分析评估簇头选举协议好坏的性能指标如下：l 稳定期：第一个节点死亡之前的

50、时间间隔。l 不稳定期：第一个节点死亡到最后一个节点死亡之间的时间间隔。l 网络生命周期：从网络运行开始到最后一个节点死亡之间的时间间隔。l 每轮簇头数量：每轮被选举成为簇头的数目。l 每轮活动（总数、高级和正常）节点的数量：每轮中各种类型的剩余能量不为零的节点总数量。理论上分析我们的算法优于基础算法稳定选举协议-SEP的几点理由：1. P-SEP在SEP基础上考虑了节点自身的剩余能量，使得高级节点更加频繁的成为簇头，平衡能量消耗，延长了网络的稳定期。2. 在阈值选择上，由于正常节点的能量阈值在SEP算法基础上乘了一个因子，即该节点之前所有活动节点的平均能量值，随着网络的运行，能量在消耗减少，

51、所以必然是在减小，所以P-SEP算法的对于正常节点的阈值在随着网络的运行不断减小，所以被选为簇头的概率也在不断的减小，这符合平衡能量消耗，使得网络能运行更多轮的理想预期。3. 同样的对于高级节点的阈值选择，是在SEP算法基础上乘了一个因子，即2中正常节点中因子的倒数，很好理解，随着网络的运行，肯定在减小，所以增大，所以对于高级节点来说，阈值随着网路的运行在不断增大，因此高级节点被选为簇头的概率增大，同样符合使得网络能耗平衡，维持网络运行更多轮的理想。4. 关于距离计算，SEP算法和我们的算法均是考虑单跳传输数据，而在新的算法中通过计算最短距离来选择簇头，然而也不是每个节点都选择簇头当中继站，若

52、某节点直接到基站的距离比到任意一个所选出的簇头的距离都要小，则直接传输到基站，所以在节点传输数据途径上也会节省能量。5. 在正常节点被选为簇头时，除了要满足基本条件：最近1/pnrm未被选为簇头过、能量值大于0、生成的随机数小于等于阈值，还要满足该节点与相关节点之间的距离得当，以此来保证簇头在位置上分布均匀合理，这样才能平衡网络中所有节点的能耗，做到最大化网络周期。第4章 实验设计与分析4.1 实验环境及参数设置实验环境：我们主要是在Matlab仿真环境中利用Matlab语言和函数库中函数完成算法的实现过程，并将我们的算法与稳定选举协议-SEP的结果进行对比得出结论。参数设置：我们在的矩形区域中模拟无线传感器网络。其中