一种低能量优先的选举分级多路径非均匀分簇方法

摘要

一种低能量优先的选举分级多路径非均匀分簇方法，包括簇首选举阶段，所述簇首选举阶段根据参选节点到基站的最小跳数将参选节点分级，每个参选节点综合剩余能量、路径优劣参数参与竞选；对每个参选节点建立潜在竞争节点集，簇首选举过程，每个参选节点发送确认信息来确认是否进入竞选，若在规定阈值时间中没有收到回应，对应参选节点退出竞选；当某个参选节点赢得选举后，向剩余参选节点发送完成信息，剩余参选节点退出选举；竞选结束后，选择通信代价最小的簇首并通知对应簇首，然后进入数据传输阶段，且簇内通信采用单跳通信。本发明降低无线传感器网络中普通节点的能量消耗，提升网络的生命周期。

说明书

技术领域

本发明属于无线传感器技术领域，具体涉及一种低能量优先的选举分级多路径非均匀分簇方法。

背景技术

当前，物联网、云计算、大数据、CPS等新一代信息集成技术在各个领域中的应用逐渐广泛，其中不乏城市建设、国防、环境监测管理、农业、医疗等重要领域。其作为上述应用的基础，无线传感器网络在上述信息集成过程中扮演重要角色。无线传感器网络由部署在网络域中的空间随机分布的自治无线节点组成，能够收集各类感知数据，如噪声、温湿度、光照强度等，并最终传输到汇节点。无线传感器网络全场景应用决定了它需要面对各类极端环境。事实上，在这些环境中更换传感器节点常常是困难且昂贵的。通常在这些情况下，传感器节点需要连续长时间工作，续航无法得到保障，同时其庞大的节点数量也使得人工维护和逐一优化无线传感器网络不再现实。为此，这些严格的限制，即低内存，低处理能力和低电池电量的传感器已经吸引了人们的注意，也正是如此，开发能量效率高、生命周期持久的WSN路由协议是一个十分迫切的问题。

根据WSN的逻辑结构，可以将路由协议分为平面路由协议和层次路由协议。在平面路由协议中，泛洪(Flooding)路由协议最为经典，接受到信息的节点以广播的形式将信息给传递给所有的邻居节点，虽然对WSN没有拓扑结构的要求，且健壮性高，但是存在信息内爆、资源消耗大等问题，虽然基于它之上有SPIN、Gossiping等路由协议的改进，但是资源使用效率低下的问题始终没有很好地解决。该问题的核心便是所有节点的关系平等，从而使得节点的路由过于繁杂，并没有一条明确的信息传播路由。

而层次路由协议中将节点进行集群分簇便很好地解决了这一问题。其中经典的LEACH运用了数据压缩技术以及分簇动态路由，使得压缩后的数据沿着特定的路由传播，极大地提高了资源的利用效率。虽然层次路由协议相比于平面路由协议有了较大改进，但是其仍存在诸多急需解决的问题，比如靠近基站的“热区”问题，如何合理地选取簇首等。除此之外，还有能量路由协议以及基于查询的路由协议等.

目前，许多成熟的路由协议已经有了的广泛应用，但是这些路由协议或多或少均存在一些未考虑到的问题。比如，层次路由算法中未考虑“木桶效应”，即未对低能量节点做出保护策略，从而使这些节点过早死亡。其次在成簇阶段，对节点采用了固定不变的竞争半径以及不充分的竞选参数。因此为了解决上面两个问题，深入WSN微观层面进行优化是迫切需要的。最后，现有技术对WSN中多跳的研究仍不够完善，虽然意识到了多跳对网络资源的浪费，但是对于多跳的优化过于粗糙，并未考虑到多跳的双面性。在分析传统路由协议的多跳传输模式后发现:在传统的多跳路由中，中继节点耗费大量能量用于转发其他节点数据。且在多跳路由中中继节点数量越多，对整体网络来说，大量能量用于转发重复数据的情况就越严重，但是从另一方面来说，多跳通信能减缓远离基站节点的死亡时间，从而延长网络的生命周期。因此，合理地平衡多跳对网络总体能量以及网络中节点的能量对延长WSN生命周期具有重要意义。

发明内容

为此，本发明提供一种低能量优先的选举分级多路径非均匀分簇方法，以解决现有协议不可能完全均衡所有节点的能耗，负载过重的节点耗能速度过快，导致能量偏低，从而影响网络生命周期问题。

为了实现上述目的，本发明提供如下技术方案：一种低能量优先的选举分级多路径非均匀分簇方法，包括簇首选举阶段，所述簇首选举阶段根据参选节点到基站的最小跳数将参选节点分级，每个参选节点综合剩余能量、路径优劣参数参与竞选；

对每个参选节点建立潜在竞争节点集，簇首选举过程，每个参选节点发送确认信息来确认是否进入竞选，若在规定阈值时间中没有收到回应，对应参选节点退出竞选；

当某个参选节点赢得选举后，向剩余参选节点发送完成信息，剩余参选节点退出选举；

竞选结束后，选择通信代价最小的簇首并通知对应簇首，然后进入数据传输阶段，且簇内通信采用单跳通信。

作为低能量优先的选举分级多路径非均匀分簇方法的优选方案，竞选簇首之前还包括，初始化WSN网络，参选节点确定自己的邻居节点以及自己层级；

当所有参选节点初始化完成后，参选节点开始更新竞争半径，接着再更新自己的竞争参数，然后进入簇首选举阶段。

作为低能量优先的选举分级多路径非均匀分簇方法的优选方案，参选节点采用随拓扑变化的竞争半径，参选节点竞争半径与承担的负载成正相关变化；

将参选节点的剩余能量与自身和当前的邻居节点集中的元素个数的比值作为邻居平均可得能量。

作为低能量优先的选举分级多路径非均匀分簇方法的优选方案，每次选举时参选节点均会更新邻居平均可得能量及更新历史最大邻居平均可得能量；

从参选节点以往的历史时期确定现在的竞争半径，并将得到的结果作为标准化平均邻居可得能量；

将得到的标准化平均邻居可得能量采用余弦偏移模型进行变换，得到簇的竞争半径公式。

作为低能量优先的选举分级多路径非均匀分簇方法的优选方案，簇的竞争半径由参选节点所处层级、标准化平均邻居可得能量以及剩余能量共同确定；

预设一个阈值层数，当大于阈值层数时改变竞争半径。

作为低能量优先的选举分级多路径非均匀分簇方法的优选方案，预设参选节点的二维竞选参数，将参选节点的剩余能量作为簇首竞选的第一参数；同时将衡量参选节点路由优劣的路由优劣参数作为簇首竞选的第二参数；

预设实际前进距离，一条路由的实际前进距离为发送端到基站的距离与接收端到基站的距离之差。

作为低能量优先的选举分级多路径非均匀分簇方法的优选方案，如果有节点A的通信内节点C在节点A到基站S的连线上，将节点C称为相距d

作为低能量优先的选举分级多路径非均匀分簇方法的优选方案，每个节点根据自己的剩余能量获得相应的票数，在投票开始时，所有层级大于1的参选节点广播Vote_msg，Vote_msg包括节点的适应度值、竞争半径以及层级；

当节点S

作为低能量优先的选举分级多路径非均匀分簇方法的优选方案，二维竞选参数的比较逻辑为：

i)当节点s

ii)当节点s

iii)若比较节点的二维竞选参数均相同，节点ID小的节点赢得竞选；

iv)若不满足i、ii、iii，节点s

作为低能量优先的选举分级多路径非均匀分簇方法的优选方案，将簇首I所有小于信道阈值d

簇内采用单跳通信，簇间选择轮替多跳通信。

本发明具有如下优点：在簇首选举阶段，为了提高WSN的生命周期，同时针对WSN生命周期中发生的拓扑变化，赋予每个节点自适应变化的二维竞争参数以及竞争半径；本发明根据WSN节点生存状况进行自适应调整分簇，能使簇首对WSN环境的适应度更高，同时拥有更灵活的负载承受策略，防止节点因负载过大而提早死亡；本发明提出在多跳中均衡网络资源浪费以及节点能耗的问题，并给出轮替多跳的通信方案；仿真结果表明，与LEACH、HEED以及EEUC传统路由算法相比，本发明在性能上获得了改进。在网络稳定期阶段，算法生命周期延长了80％，而在整个WSN生命周期中算法生存期间节点性能保存较高且提升了约43.7％。

附图说明

为了更清楚地说明本发明的实施方式或现有技术中的技术方案，下面将对实施方式或现有技术描述中所需要使用的附图作简单地介绍。显而易见地，下面描述中的附图仅仅是示例性的，对于本领域普通技术人员来讲，在不付出创造性劳动的前提下，还可以根据提供的附图引伸获得其他的实施附图。

图1为本发明实施例提供的低能量优先的选举分级多路径非均匀分簇方法中随拓扑变化的竞争半径示意图；

图2为本发明实施例提供的低能量优先的选举分级多路径非均匀分簇方法中实际前进距离示意图；

图3为本发明实施例提供的低能量优先的选举分级多路径非均匀分簇方法中轮替多跳示意图。

具体实施方式

以下由特定的具体实施例说明本发明的实施方式，熟悉此技术的人士可由本说明书所揭露的内容轻易地了解本发明的其他优点及功效，显然，所描述的实施例是本发明一部分实施例，而不是全部的实施例。基于本发明中的实施例，本领域普通技术人员在没有做出创造性劳动前提下所获得的所有其他实施例，都属于本发明保护的范围。

本发明实施例中，考虑一个由N个随机部署的传感器节点形成的网络，其应用场景为周期性的数据收集。用s

在此基础上，假设：WSN中的传感器节点同构，通信半径为R

能量消耗考虑三个方面，一是无线通信时发送数据的能量消耗；二是无线通信时接受数据时的能量消耗；三是融合数据时的能量消耗。同时采用现有技术中简化的能量模型，将每l比特数据传输距离d所需要的能耗表示如下：

接受每l比特数据的能耗为：

E

上两式中，E

本实施例中，融合每l比特数据的能耗为：

E

式(4)中，E

本实施例中，将整个半径为M的圆形监测区域R分为K(R＝Kr,r为环间距也为通信半径)个均匀间隔的同心圆环区域,圆环的中心为基站(Sink)。第i个环区域可以表示为：

其中，节点s

本实施例中，给出一种保护低能量节点的路由算法。该算法寻求对节点进行差异化考虑从而延长网络的生命周期。路由算法根据WSN网络状况进行自适应调整节点分簇条件，并在分簇时对低能量节点采取一定的保护措施，旨在平衡同一环中节点能量，以防有低能量节点过早死亡。

在算法开始，需要初始化WSN网络。在这个阶段，节点s

在传统技术中，每个簇首的竞争半径在一开始就已经确定，并在节点的生命周期中都不会发生改变。然而这种机制并未考虑到随着WSN中节点的死亡，每个节点周围的邻居节点个数也会发生变化。如果节点竞争半径保持不变，容易造成低能量区域的节点群簇首负载过大，从而导致过早死亡。对此改进的机制便是关注每个节点的周围的情况来决定其竞争半径。参见图1，在本发明中，采用随拓扑变化的竞争半径。节点竞争半径与其可承担的负载成正相关变化。

结合现有技术，可以得到一种等间距环形划分的分簇方法。同一环中簇半径相等，且与基站的距离成正相关,如式(7)所示。

一个节点竞争半径的大小应该与该节点所能承受的负载上限有关，即与节点的能量水平与其周围网络的拓扑环境有关。因此命名一个邻居平均可得能量的参数来作为节点可承受负载的情况。

具体的，将节点s

AvgNeiE

并且将节点s

HisAvgNeiE

而后每次选举时节点s

HisAvgNeiE

若单纯只靠这一个参数来衡量节点在各个时期的竞争半径并不准确，因此需要将这个参数与HisAvgNeiE

再将得到的节点s

簇的竞争半径r

本实施例中，簇首扮演了融合和转发一个区域内所有节点数据的重要角色，除了需要有较高的电池能量之外，所拥有的路由也需要足够优秀。传统的路由算法通常将节点的剩余能量作为簇首的竞争参数，虽然选出的簇首是剩余能量最多的，但其路由指标未必是最优秀的。

本发明定义了一个二维竞选参数CP

本实施例中，定义了实际前进距离，即一条路由的实际前进距离(Actual forwarddistance，AFD)为发送端s

AFD＝d

具体的，AFD为通过这一条路由转发的数据实际上与基站缩短的距离。如图2所示，节点s

EECR＝AFD/E

可知，在距下一跳的距离相同时，EECR越大，该路由越优秀。但因为不同传输距离d

本实施例中，在设计之初着重考虑了低能量节点，因此采用了投票的策略，并希望低能量节点具有更大的比重，以选出对于大多数低能量更加亲和的簇首，来尽可能延长更多低能量节点的寿命。

而参选节点的簇首竞选参数是作为投票节点的参考依据。

令s

每个节点根据自己的剩余能量E

Votes

投票过程的伪代码如算法1所示。在投票开始时，所有层级大于1的节点s

下面阐述竞争选取簇首的算法。算法2给出了任意节点s

i)当s

ii)当s

iii)若比较节点的二维竞选参数均相同，那么节点ID小的节点赢得竞选，如II(20-23)。

iv)若不满足i、ii、iii，那么节点s

当节点赢得选举，并且向其他节点发送FINAL_CH信息。一个节点s

至于竞选结束后，收纳簇节点的过程与现有技术相似，普通节点选择通信代价最小的簇首并通知该簇首。该过程结束后便进入数据传输阶段，其中簇内通信采用单跳通信。

之前传统的多跳路由协议多跳也能极大程度地节省远距离节点在通信方面的能耗，但并未考虑到多跳导致中继节点重复转发相同的数据，造成了整体网络中能量浪费的事实。在本节中根据上一节证明的结论对传统多跳从平衡网络资源以及节点能耗的角度进行了改进，从而提出了轮替多跳的方案。

参见图3，轮替多跳传输是将簇首I所有小于信道阈值d

ComIns

其中d

如图3所示，假设节点I所有小于信道阈值d

若是将这三种通信方式以一种规律结合起来，并称这一种规律为ι

Optimization formula for alternating multiple hops(FALM)

可得目标公式1：

其中E

通常路由协议，簇首只与簇首通信，存在中继的簇首能耗损耗过快的问题。多路径传输的优势，在于能够平衡WSN网络中的能耗。而本发明提出轮替多跳与多路径传输结合后变形的簇首s

本发明将节点s

λ

其中，DATA

如果节点s

本实施例中，能量均衡多路径路由的第一个目标函数如下:

目标公式2：

其中，θ

其中对目标公式1、2进行融合，得轮替多跳下的能量平衡寿命最大化路由问题公式(Energy balance life maximization routing problem for alternate multi-hop,EB-FALM)，即目标公式3：

其中，

根据EB-FALM公式，能够知道最大化最小生命周期的节点以及最小化整个WSN中传输能耗是优化的重点部分。从微观上分析，节点的传输能耗受两个因素影响：1、与下一跳节点的距离；2、交互的数据量大小。簇首节点(CH)作为一个簇团内所有数据的交汇点并且需要将大量的数据传输至其下一跳，簇首节点消耗的能量比簇成员节点多上许多，因此它的寿命会短于其它节点。同时，在目标公式3后半部分，也从宏观上对整个WSN的网络传输以及网络浪费的能耗进行了考虑。

一条路由上中继节点越多，除了对第一个发送数据的节点有利之外，对路由中的任何一个中继节点来说，其能耗均会远超寻常，属于一种网络能量的浪费，因此从整个网络上来说这并不利于延长WSN生命周期。而对此提出的轮替多跳的通信方案，节点在权衡自己的能耗以及网络的能耗后选出合理的下一跳节点，在保证节点自身寿命的前提下延长网络的生命周期。

本实施例中，簇内采用单跳通信，只有在簇间才会选择轮替多跳通信，且因为簇首轮替多跳时，它当前轮替的下一跳都处于同一层级，并不会出现层级不同的情况，即延迟相同，且根据实验，任一节点多跳次数不会多于4次，延迟少于标准多跳的算法。

对于本发明的技术方案仿真结果表明，与LEACH、HEED以及EEUC传统路由算法相比，本发明在性能上获得了改进。在网络稳定期阶段，算法生命周期延长了80％，而在整个WSN生命周期中算法生存期间节点性能保存较高且提升了约43.7％。

虽然，上文中已经用一般性说明及具体实施例对本发明作了详尽的描述，但在本发明基础上，可以对之作一些修改或改进，这对本领域技术人员而言是显而易见的。因此，在不偏离本发明精神的基础上所做的这些修改或改进，均属于本发明要求保护的范围。