能量异构无线传感器网络分簇路由算法研究

张铭悦，陈桂芬，王鹤霏

（长春理工大学 电子信息工程学院，长春 130022）

物联网技术被誉为当今伟大的技术之一，它的应用主要与三项关键技术密不可分。其中一项关键技术—无线传感器网络相当于“触手”，针对无处不在的信息流进行感知，并将获得的信息进行处理。传感器节点可以分布在森林、会议室、患者身体等特殊区域。可以实现对多种实时动态数据的采集。之后，来自传感器的数据传递给实时接收设备，通过互联网传递给用户［1］。随着社会的发展需要，数据产生的途径也更加多样化，现今有效的数据收集手段也很有限，传感器的发展仍然重要。

无线传感器网络（WSN）由多个传感器节点组成，这些节点分布在各个需要收集数据的区域，每个节点的通信方式、计算和感知能力都是相同的［2］。无线传感器网络适用于栖息地监测，建筑监测和森林监测等领域，在生物科学、生物医学等重要领域中扮演着重要的角色［3］。无线传感器网络收集的信息量很大，在电池、传感器以及附近的能量消耗速度较快。能量的不均匀消耗会导致网络寿命的缩短。分簇算法的出现大大延长了网络的生命周期，并节约了很多能量［4］。

早期对无线传感器网络的研究主要集中在同构网络上，但现实环境下，同构网络的作用并不好，相对而言，异构网络的发展更具有现实意义。异构无线传感器网络分为节点能量异构网络、计算能量异构网络、链路异构网络、网络协议异构网络等［5］。

胡中栋、伍华林等人［6］提出了MEECR算法，该算法优化DEEC算法的方式是将节点位置与剩余能量引入簇头选举机制，通过改进选举阈值公式，优化网络性能。Raju Pal等人［7］提出的BEECP是将BBO算法（Biogeography-based optimi⁃zation）引入到异构网络中，用于找出传感器节点的最佳组合，达到降低能耗的作用。Jin-Shyan Lee等人［8］提出了一种基于三层结构的半分布式分簇方法，实现了上下层的簇头选择，有效提高了网络死亡生命周期。Saini P等人［9］提出了EDEEC算法，该算法在异构无线传感器网络中原有的两种节点的基础上，加入了超级节点，增加了网络的异构性和能量水平。Nematollahi P等人［10］提出了SEDC算法（Simple Energyefficient Data Collecting protocol），该算法是通过设置能量阈值，让能量不符合要求的节点不参与簇头的选举，使得簇头选举更加准确快速。Dutt S等人［11］提出了一种簇头能量受限的算法CREEP，该算法通过修改双层异构网络中的簇头选择阈值，来克服原算法在簇头上的限制。Vançin等人［12］提出了一种基于三层异构分簇的分布式节能路由算法TBSDEEC，该算法考虑了能量消耗模型中，阈值平衡采样的影响，通过设置两种不同的应用场景，来设置参数。

上述针对异构网络算法的改进，不仅仅从网络本身的异构性进行考虑，还有参数和算法的结构。应用场景也是优化异构网络性能的重要考虑因素。

1 DEEC算法

异构网络的研究起步晚于同构网络，为了更好的理解异构网络，首先，介绍一下同构网络的研究状况。

大部分适用于同构网络的算法均可改进为适用于异构网络的算法。DEEC算法就是从LEACH算法改进而来的。这种改进同构网络算法方式，使得其实用价值得到提高。同构网络与异构网络的区别主要体现在两个方面：参数设置的不同和协议的混合应用。参数的设置可以随着环境的变化而变化，协议的不同，则需要特殊技术，将其融和在一起，共同对网络发挥作用。

DEEC算法主要目的是将剩余能量更多的节点选做簇头，节约网络能量，使其利用率提高。该算法主要应用于二级能量异构无线传感器网络。

（1）簇的建立阶段

两种节点的区别直观体现在初始能量的差异上，普通节点的初始能量为E0，那么高级节点的初始能量是E0（1+α）。α为高级节点多于普通节点的能量倍数。由于存在两种不同的节点，对两种节点的概率值Pi的设置也不同，如公式（1）所示：

其中，Popt表示期望簇头比例；Ei(r)表示节点在r轮剩余的能量值；Pi表示节点在轮中当选为簇头节点的平均概率节点。

在节点的剩余能量不一致的情况下，剩余能量高的节点将有更大的概率当选簇头。表示网络节点在第r轮的平均能量值，如下：

在第r轮，用当前节点的能量与网络平均能量做比值，可以得到：

由公式（3）可以看出节点当选簇头的概率是根据能量比值决定的，节点的剩余能量越多，节点当选簇头的概率越大。

假设每轮的能量消耗Eround是相同的，并且节点能耗均匀，可以估算出网络的生命周期为：

其中，Etotal为全网节点初始的总能量；Eround为每一轮全网所消耗的总能量。

由于节点能耗均匀，每轮消耗的能量都几乎相同，于是得到第r轮节点的平均能量------E(r)为：

簇头选举阈值函数T(n)的表达式为：

选举出的簇头将会向一定范围内的节点广播信息，同时普通节点在接收到入簇指令后，通过选择最近的簇头，进行入簇。

多级异构网络由二级异构网络推广而来，将其带入到公式（3）中，得到：

其中，αi为多于E0的能量倍数。

网络的全部节点数如公式（9）所示，Ii表示节点的基本轮转周期，节点成为簇头的周期为：

当Ei(r)＞，则ni＜Ii，通过上述理论分析，节点能量越高，当选簇头的概率就会越大。

（2）稳定传输阶段

经过筛选的簇头将簇内成员收集来的信息进行整理，并将融合的数据以单跳的方式传输数据到Sink节点。

2 仿真模型

2.1 系统的能量模型

系统的能量采用无线电模型。该模型的功能的实现取决于d0的设置。发送数据能耗ETx(l,d)表达式为：

接收数据能耗ERx(l)表达式为：

数据融合能耗Em表达式为：

其中，l为数据包长度；Eelec为发射电路的能量；εfs和εmp为功率放大器的能耗；EDA为单位数据融合能耗；N为簇内成员节点数；若d＞d0，则为多径衰减模型：反之为自由空间模型。

2.2 系统的网络模型

为了搭建合理的仿真环境，做出如下假设：

（1）在 100×100的矩形区域中，设置 Sink节点在网络的中心。

（2）所有的节点的标识号都是唯一的且不会中途发生改变。

（3）所有的节点都是固定不动的，相对的，其坐标也是固定的。

（4）所有节点的硬件配置都是相同的，节点具有的各方面能力都是相同的，并且会按照设置好的通信速率发送数据。

（5）普通节点仅仅负责采集和向簇头发送数据，簇头的主要功能是存储、融合、发送数据，并将融合好的数据发送到Sink节点。

（6）通信链路的能量消耗是相同的，且不分主动被动。

（7）假设Sink节点不会死亡并且能量消耗为0。

2.3 算法分析

DEEC是一种基于LEACH并适用于多级能量异构网络的分布式高能效分簇路由算法。DEEC算法并未考虑网络中簇头分布不均、簇头产生数目不稳定等问题。针对上述问题，目前的解决算法多种多样，主要差别是参数的改进和算法结构的优化。

通过上述理论分析，DEEC算法的簇首选举考虑了剩余能量，使得簇头选择更加合理。由于簇头与Sink节点是采用单跳通信的，而在实际应用中，网络的规模都偏大，这种机制使得该算法不适用于大规模网络，并且DEEC算法的簇头选举仅仅考虑了剩余能量，对于其它影响因素，比如节点之间的距离，可能存在簇头选择不合理的情况，加快节点死亡。

CREEP算法在簇首选举中的概率Pi进行改进，主要将节点距离与平均距离的比值引入到Pi上，该算法同DEEC算法，也考虑了能量因素，但CREEP算法在多跳路径的选择中，并未设置合理的参数来限制下一跳的选择，因此会出现路径选择不合理的情况。

3 DEEC-BD算法概述

DEEC-BD算法主要包括两个方面：

（1）针对簇头选举概率Pi进行改进，在考虑剩余节点能量的同时，引入节点距离因子。根据距离的不同选择不同的距离因子，可以灵活的调整簇头选举概率。

（2）设置路径质量Q(r)，通过对比每条路径的路径质量参数，选择合适的下一跳，缓冲簇头的压力，适当的延长网络的生命周期。

3.1 距离因子

距离因子的形式根据距离阈值产生的，本文设置的距离阈值为D0：

式中，davg为全部节点距Sink节点距离的平均值。

当di≥davg时，Pi概率如下：

式中，di为节点到Sink节点的距离；dmax为节点到Sink节点的最大距离。由本式可知，节点距Sink的距离越小，被选为簇头的概率相对更大，反之，则更小。

当di＜davg时，Pi概率如下：

如上所述，剩余能量较大、距离Sink节点较近的节点，在簇头选举机制中，增大了被选为簇头的概率。距离Sink节点较远的节点，在数据传输过程中，会耗费更多的能量，从而影响网络的综合性能。DEEC-BD算法的簇头选举机制，通过设置距离阈值，减少分布在区域边缘节点被选做簇头的概率，也减少了由于能量消耗过快而快速死亡的簇头，即在相同轮数内，网络能耗减少的同时，网络的可用节点数量能够显著增加。

3.2 路径质量

利用单跳的形式将数据传输给Sink节点是分簇算法的默认方式，但是单跳传输会使得簇头更快死亡，影响网络的生命周期，数据的传输量也会受到影响，因此，多跳机制可以减轻在数据传输过程中簇头的负担，并能够适当的延长网络的生命周期。

多跳机制中下一跳的选择是重中之重，本文引入路径质量参数，使得簇头向Sink节点传输数据的时间延长。

网络的使用范围，与算法本身的可扩展性息息相关。根据对上述算法的分析，引入了路径质量参数Q(r)，该参数考虑了簇头剩余能量和簇头到Sink节点距离，根据这个参数选择最优路径，在能量消耗较少的情况下，传输大量数据。

式中，Di为簇头到Sink节点的距离；Dmax为簇头到Sink节点的最大距离。

3.3 DEEC-BD算法流程

（1）部署节点、设置基本参数。

（2）计算距离阈值D0，根据di与D0之间的关系，选择合适的Pi形式，依据改进的簇头选举阈值函数计算出该节点簇头选举的阈值，选择合适的簇头。

（3）该步骤是成簇的最终阶段，其主要将那些并未成为簇头的节点，根据感知的信号强弱，寻找距离自己最近的节点，然后入簇。然后，把从各个区域收集来的数据，发送到簇头。

（4）簇头则将簇内节点收集的数据进行融合，利用改进的多跳机制，根据路径质量参数，选择合适路径，将数据传输到Sink节点。

（5）网络开始新的一轮，重复上述步骤，直到全部节点都死亡。

4 仿真结果分析

在仿真分析中，本文主要针对多级能量异构网络，在死亡节点数（生命周期）、数据传输量和能量消耗三个方面。实验环境设置见1.2、1.3节。

针对Q(r)中的权值α和β的取值，经过仿真，结果如表1所示。

表1 α、β的取值

图1 权值取值对比图

根据图1所示，可以得到α和β的最优取值，仿真参数如表2所示。

表2 仿真参数

4.1 网络死亡节点数

网络的死亡节点数表示全网死亡节点随网络运行而变化，是一项重要的指标，能够直观的显示网络生命周期的长短。

由图2可以得出DEEC-BD算法的节点死亡速度要比DEEC算法的节点速度慢，DEEC-BD算法节点全部死亡为3 251轮，CREEP算法节点全部死亡为2 364轮，即生命周期延长了37.5%。DEEC算法节点全部死亡为1 794轮，即生命周期延长了79%。

图2 网络死亡节点数对比

4.2 网络数据传输量

数据传输量的大小，是衡量无线传感器网络性能是否优越的重要指标，如今，数据呈“爆炸式”增长，传输数据量的大小，决定了数据分析的准确率和应用途径，能够使功能的实现更加有效。

图3 网络数据传输量对比

图3显示的是DEEC算法、DECH算法与DEEC-BD算法的数据传输量。经计算，DEECBD算法的数据传输相较于CREEP算法，多传输了41.5%的数据。相较于DEEC算法，多传输了4.5倍的数据。

4.3 网络能量消耗

尽可能的节约能量，对于各个研究都是永恒的目标，无线传感器网络的能量由于硬件的限制，节点的能量不可能存在无限大的情况。减少能量的消耗，可以使得网络的数据传输更加持久。

图4 网络能量消耗对比

图4显示的是DEEC-BD算法、DEEC算法与CREEP算法的能量消耗进行对比，经过计算，本文的提出算法相较于CREEP算法的能量消耗低于16.7%，相较于DEEC算法能量消耗低于52%。

5 结语

本文研究的DEEC-BD算法在原算法的基础上，引入了距离因子和路径质量两个参数。原DEEC算法本身仅仅考虑了剩余能量与网络节点平均能量的比值，而距离因子的引用可以尽量避免那些距离较远的节点当选为簇头，从而影响网络的性能。簇头与Sink节点之间的数据传输形式是单跳的，这种传播数据的方式，针对大范围网络是行不通的，即网络的扩展性能将受到极大的影响。CREEP算法虽然数据传输是多跳机制，如果仅仅把传输方式改成多跳，并不加条件限制，那么路径的选择就是任意的，在这种情况下，会出现路径选择不合理，加快节点的死亡，引入路径质量是十分有效的约束条件，可以选择参数较大的簇头，作为下一跳。通过改进簇头选举机制和数据传输机制，DEEC-BD算法的性能要优于DEEC算法和CREEP算法的性能。