基于自适应权重的无线传感器网络动态成簇算法

薛晶晶，雷文礼*，徐 翔

(1.延安大学 物理与电子信息学院；2.陕西省能源大数据智能处理省市共建实验室； 3.延安大学 宣传部，陕西 延安 716000)

无线传感器网络(WSN)由一组传感器节点按照拓扑协议和一定的通信方式组成，已广泛应用于环境监测、军事、医疗测量和功能障碍诊断等领域[1-4]。由于节点体积小，存储能力有限，因此，更有效的拓扑控制协议是设计WSN延长寿命、提高能源效率、改善负载平衡和覆盖范围的关键因素。最新研究表明，成簇能够有效减少能量消耗，因此本文提出了用于WSN的节能动态成簇算法。簇头选择剩余能量最大、通信能耗最小的节点担任。在信息传输过程中，簇内节点采用单跳传输，簇头节点根据与基站(BS)的距离选择多跳传输或单跳传输。仿真结果表明，相比低功耗自适应集簇分层型协议(LEACH)，该算法能有效节省能量消耗，延长网络寿命。

研究表明，已有大量路由协议被应用在无线传感器网络，但多数是静态网络。如图1所示，网络协议被分为四类：分层协议、数据处理协议、网络流量和服务质量协议、位置追踪协议[5-9]。以上协议能够很好地解决静态网络应用问题，但对于动态网络，目标轨迹的不断改变，需要协议评估是否需要改变簇的状态[10-13]。静态网络无法满足相应需求，因此本文提出了基于自适应权重的动态成簇算法(以下简称EEDCA)。该算法将网络分成正六边形网格，并将节点通过泰森多边形图(Voronoi)分成一定数量的簇，每个簇剩余能量最多的节点被选为簇头。在信息传输过程中，簇内节点采用单跳传输，簇头节点根据距基站的距离选择多跳传输或单跳传输。仿真结果表明，该算法可以更好地平衡节点能耗，提高能源效率，延长网络寿命。

1 EEDCA算法分析

本文提出新的路由协议，首先对网络系统设置如下：1)N个传感器节点分布在M*M的区域内；2)所有传感器节点固定不动；3)所有传感器节点材质和性能均相同，初始能量也相同；4)基站可以布置在网部内部或外部，并有足够的能量；5)每个节点都有唯一的ID。

图1 路由协议分类

1.1 簇的形成

在监测环境中，传感器节点通常以随机方式部署，这可能会导致网络重叠，有效的解决方法是将监控区域划分为正多边形网格。本文采用正六边形网格，对于同一个监控区域，网络被划分为一个六边形网格，这将花费最少的节点数，实现最大的区域覆盖，同时转发的数据量也减少，网络总体通信能耗也相应降低。簇的形成过程如下：首先网络初始化阶段部分节点处于工作状态，其他节点休眠[14-15]，然后利用Voronoi图建立节点覆盖模型。Voronoi图的主要目的是划分监控区域以保证最大覆盖，并将划分的区域分成小簇，通过改变簇头而不改变覆盖区域来保持最长的使用时间。Voronoi图的形成如图2所示。

图2 六边形划分及簇的形成(★表示簇头节点)

1.2 簇头的选择

1.2.1 网络能量模型

本文基于一阶射频能量消耗模型推导出数据包传输和接收过程中能量消耗的方程。该模型包括自由空间模型和多路径衰减模型，模型采用d2和d4来表示发送端和接收端通信时因为距离引起的传输能量的消耗。因此当使用无线模型在距离dij之间传输k位的消息时，能量消耗如(1)式所示，(2)式表示节点接收k位数据包消耗的能量。

ETX(k,d)=eelec×k+eamp×k×dij，

(1)

ERX=eelec×k。

(2)

其中eelec表示每发送或接收1 bit数据所消耗的能量，eamp表示发送放大器处理Eb/N0数据所消耗的能量。实验表明，数据传输会消耗更多的能量，并且传输距离越长，能量消耗越多。因此在路由协议的设计过程中，应尽快减小传输距离和数据包大小，并在簇头和簇内节点间采用自由空间模型，基站和簇头间采用多路径模型，这样能有效延长网络使用寿命。节点i和j之间通信能量消耗方程为(3)式，该方程表明，传输距离不同，计算方式不同。

(3)

其中d0表示距离阈值，当超过该阈值时采用多路衰减模型来传输，低于时信号传输使用自由空间模型，Ecurt为某些节点的当前能量。Einit/Ecurt的值越大，能量消耗速度越快。

1.2.2 簇头选择

1)为每个节点设置ID，i=1，2……N。

2)Si表示某个簇，权重计算如(4)式所示。该公式既能计算簇内节点权重值也能计算簇整体权重值。通过比较，选择簇内最小权重的节点担任簇头。

(4)

3)节点和基站的通信能量消耗采用(5)式计算，公式如下：

(5)

2 数据通信

网络使用过程中，节点要与节点、簇头、基站等进行通信。数据传输中，簇头作为中间枢纽能量消耗速率快，同时，当传输距离较远时，该类节点因能量耗损完而失效。因此，本文采用分时复用的方式进行传输。

图3 单线网络

ETX(l,d)=ETX_elec(l)+ETX_amp(l,d)=

(6)

(7)

ERX(l)=ERX_elec(l)=lEelec，

(8)

网络总体能量消耗如(9)式所示，其中α为数据传输跳数[17]。

Etot=α(ETX+ERX)=

(9)

3 EEDCA算法流程

EEDCA算法详细步骤描述如下：

1)部署基站，并按照正六边形来划分监测环境；

2)按照Voronoi图来划分节点；

3)初始化各个节点的参数，并计算节点剩余能量和当前传输中消耗能量值；

4)比较每轮节点剩余能量以及数据传输能量消耗值，选择剩余能量最多，耗能最小的节点担任簇头；

5)当节点在簇头通信范围内时，该节点被选择为簇内成员；

6)簇内成员节点采集监测环境信息，并传输给簇头节点，簇头节点判断自身和基站的距离以及剩余能量，并选择单跳传输或多跳传输。

4 仿真实验及结果分析

4.1 仿真环境

本文采用Matlab仿真来分析算法性能。实验环境如下：本文采用100 m×100 m的正方形区域进行仿真，并用正六边形进行划分，节点按照Voronoi图来部署，如图2所示。实验仿真参数[18]如表1所示。

表1 仿真参数表

4.2 仿真结果及分析

为了验证本文算法的有效性，将提出的EEDCA算法与LEACH协议在同等仿真环境中进行了比较。

图4给出了基站位于(50，50)的位置，网络部署60个节点时，随着仿真的进行，网络中出现第一个节点死亡(FND)、一半节点死亡(HND)、最后一个节点死亡(LND)的运行轮数。从图4中可以看出，EEDCA算法第一个节点死亡、一半节点死亡、最后一个节点死亡的运行轮数分别为810、1725、2415，而LEACH算法的运行轮数分别为243、1150、1732。通过比较第一个节点死亡和最后一个节点死亡的运行轮数，EEDCA算法能够稳定运行的时间大于LEACH协议近70%。同时，EEDCA算法节点死亡速率较小，从而能够有效延长网络生命周期。这表明LEACH协议适用性较小，多个节点反复担任簇头，能量过度消耗而失效。所以EEDCA算法对不同节点分时复用，并按照正六边形以及Voronoi图部署节点，从而获得了比LEACH更长的稳定周期和生命周期。

图4 不同数量节点死亡运行轮数

图5给出了基站位于(-50，100)，网络部署60个节点时，网络中出现第一个节点死亡、一半节点死亡、最后一个节点死亡的运行轮数。从图5可以看出，EEDCA和LEACH算法出现第一个节点的死亡轮数分别是165、110，一半节点死亡的轮数分别是371、280，最后一个节点死亡的轮数分别是515、303。网络生命周期分别提高了约33%、24%、40%。图4和图5相比较，基站的位置发生变化后，网络的生命周期明显下降，因此，在网络部署过程中，基站位置至关重要，合理的部署能够有效延长网络寿命。同时进一步的比较，表明本文算法能够有效延长网络工作周期。

图5 不同数量节点死亡运行轮数

图6 节点存活数与网络运行轮数

图6基站位于(50，50)，节点数为100，给出了网络运行轮数和节点存活关系。从图中可以看出，EEDCA下降速率较慢，EEDCA和LEACH算法最后一个节点的运行轮数分别为2360和1780。这表明该算法能够有效延长网络生命周期，同等环境下运行时间更长。

5 结论

本文提出了一种自适应权重的无线传感器网络动态成簇算法(EEDCA)。在该算法中，利用正六边形划分网络，同时簇的形成按照Voronoi图来实现，簇头选择剩余能量以及通信能耗权重最小的节点担任，从而有效延长了部分节点的寿命。数据传输采用分时复用的方式，即簇内单跳传输，簇头和基站选择多跳传输，均衡了节点的能量消耗，提高了能量使用效率。通过仿真并与LEACH算法对比分析，EEDCA算法高效运行周期和网络使用寿命都提高了20%以上，这表明本文算法具有更好的性能，对应用环境的适应性和可扩展性更好。