基于移动汇聚节点和分簇的改进节能路由算法

刘天琪　张宁博　姬聪敏　上官国庆

【摘要】为了缓解“能量空洞”现象，本文提出了一种基于移动汇聚节点的节能路由算法，在现有节能路由算法的基础上对汇聚节点的运动轨迹和簇头与汇聚节点的连接方式进行改进，增加了网络的覆盖率。为了平衡无线传感器网络中的节点能量，本文令剩余能量最大的节点成为簇头节点。根据节点间距离的不同，本文分情况讨论了节点的能量消耗，最终使用弗洛伊德算法得到了耗能最小的簇头与汇聚节点的路由。从仿真实验可以看出，本算法能够有效地延长网络周期，减缓死亡节点的出现。

【关键词】移动汇聚节点;无线传感网

物联网技术在近几年已经成为信息技术的重要组成部分，而无线传感网（简称WSN）则是物联网技术中的核心部分，因此对于无线传感网络中的路由协议和路由算法的研究也成为了热门问题。

无线传感网由许多个传感器节点组成，可以根据不同的要求监测不同的数据，例如温度、湿度等，传感器可以将这些数据发送给网络内的汇聚节点，再由汇聚节点转发给用户或其他设备。传统路由协议的无线传感网中，汇聚节点是固定的，如图1中的红色点所示，蓝色的点表示网络中的簇头节点，黑色的点表示普通节点。其中簇头节点不仅要接收来自普通节点的信息，还要将信息转发给汇聚节点，能量消耗过快，从而大大降低了这些节点的生命周期，这些节点被称为热节点，这种现象被称为“能量空洞”，有碍于无线传感网的正常工作。

为了缓解上述“能量空洞”现象，本文提出了一种基于移动汇聚节点的策略，避免长距离通信消耗大量能量，同时增大了网络的覆盖率。

1. 算法概述

本文规定移动汇聚节点的运动轨迹是既定的，可以根据网络部署的时间推算汇聚节点的位置。根据网络部署环境的需求，本文人为地将网络划分为N个相等的部分，一个部分为一个簇，每个簇内只有一个簇头节点。在选取簇头时，为了保持网络的能量均衡，每轮都只选择剩余能量最高的节点作为簇头节点。同时为了扩大信息接收的范围，本文令汇聚节点以圆形轨迹在网络内运动，且轨迹半径为网络半径的一半。

成簇以后，每个簇的簇头要与汇聚节点进行通信，此时会出现与汇聚节点较远的簇头节点，为减少能量消耗，本文首先选择与汇聚节点较近的簇头节点作为链头，其他簇头节点通过弗洛伊德算法计算到链头耗能最小的路由，最终通过链头与汇聚节点相连。

2. 算法模型

2.1 网络模型

本文规定无线传感网络为圆形，该圆形区域的半径为R，内含n个传感器节点，这些传感器节点都完全相同且不能移动。汇聚节点的运动轨迹为与该网络同圆心的圆形，且轨迹半径r为该网络半径的一半，即：

汇聚节点的初始位置为轨迹上的随机位置。

2.2 移动汇聚节点

无线传感网的圆形边缘记为O，移动汇聚节点的移动轨迹记为o，汇聚节点的移动速度，即线速度记为v，规定其在该网络中按逆时针移动。当汇聚节点经过ΔT的时间间隔后，根据线速度公式和圆的特性，有：

其中表示时间内汇聚节点移动的弧形长度，表示时间内汇聚节点在O上变化的角度。

2.3 分簇和簇头的选取

本文将整个网络均分为N个等面积的扇形，每个扇形中的传感器节点构成一个簇，因此在网络中共有N个簇，一个簇有一个簇头节点。本文假设N=6，（如图2）则有：

如图2所示，蓝色直线分出的6个相等扇形区域就是6个簇，按逆时针进行标号，每个簇都有一个簇头节点，簇内的普通节点会把数据发送给簇头节点。在选簇头时，本文首先随机选择每个簇的簇头作為候选簇头节点nh，根据剩余能量的大小令其他节点与该节点进行簇头节点的竞争，如果在同一个簇内，节点ni比nh的剩余能量大，则ni节点成为新的候选簇头，经过一轮比较，最后本簇内剩余能量最高的节点成为簇头节点ni。在图2中，有粉色圈的节点就是簇头节点。

2.4 能量消耗

簇内节点与簇头节点的通信需要消耗能量，本文只考虑传输数据所消耗的能量。传输数据所消耗的能量与距离有很大的关系，若（xi，yi）是传感器节点ni的坐标，（xi，yj）是传感器节点nj的坐标，则这两个节点之间的距离公式为：

传输数据分为两种情况，分别是普通节点与簇头节点直接通信，普通节点与簇头节点间接通信。

（1）普通节点与簇头节点直接通信

首先计算普通节点与簇头节点的距离D（ni，nl），将其与距离阈值do进行比较，若D（ni，nl）小于距离阈值do，则采用自由空间模型，反之则采用双径传播模型计算能量的消耗。因此普通节点与簇头节点直接通信时的能量消耗公式为：

其中Ele表示射频能耗系数，Data表示发送和接受的数据长度，表示自由空间模型的功率放大电路能耗系数，表示双径传播模型的功率放大电路能耗系数。

（2）普通节点与簇头节点间接通信

当某些普通节点与簇头节点距离较远时，可以采用令其与其他普通节点通信的方式来间接传输数据。普通节点ni选择其他节点nj，ni先将数据发送给nj，再由nj将数据转发给汇聚节点nl，此时的能量消耗分为三部分，ni发送数据给nj，nj发送数据给nl，nj接收数据。发送数据的能量消耗公式如公式（4）所示，接收数据的能量消耗公式为：

最后，经过多轮数据传输，若有节点能量消耗为0，则认为该节点死亡，不参与后面的通信过程。

2.5 连接簇头

汇聚节点是移动的，因此不可避免地会出现与汇聚节点较远的簇头节点，若令所有簇头与汇聚节点直接通信，则会导致簇头节点死亡过快，出现“能量空洞”。对于长距离通信的现象，可以令所有簇头都与和汇聚节点最近的簇头通信，使用弗洛伊德算法选择能耗最小的路由，再由这个最近的簇头节点传输数据给汇聚节点，这个距汇聚节点最近的簇头节点称为链头节点。簇头连接的具体步骤如下：

（1）计算每个簇头与汇聚节点的距离，选出与汇聚节点距离最近的链头节点;

（2）计算簇头节点传输数据的耗能情况;

（3）使用弗洛伊德算法，得到耗能量最小的每个其他簇头与的路由，并记录路由的路径;

（4）更新簇头节点的剩余能量;

（5）连接簇头和链头节点，最后连接汇聚节点与链头节点，至此完成所有通信网络的部署。

3. 仿真实验

本文使用MATLAB对上述算法进行仿真实验，假设该网络中的传感器节点数n=100，区域半径r=50，汇聚节点的轨迹半径r=25，传输的数据大小为5bit。

图3是运行结果中的其中一张图，粉色圈表示簇头节点，蓝色圈表示该节点已经死亡，红色五角星表示链头节点，红色实心点表示汇聚节点的初始位置，黄色圈表示汇聚节点现在的位置。

由于设备的运行速度有限，本文将每轮传输数据的时间间隔ΔT增大，节点的初始能量减小以减少传输数据的轮数。在相同的环境下，通过多次运行，本文比较了本算法和传统LEACH算法出现死亡节点的平均轮次，在大约50轮的时候LEACH算法出现了死亡节点，而本算法在75轮才出现死亡节点，由此可以证明本算法能够较好地延长网络生命周期。

参考文献：

[1]吴瑞睿，刘洁琳.无线传感器网络综述[J].科技创新与应用，2018，000（014）：65-66.

[2]王施雨，刘唐.基于数据引流的无线传感器网络能量空洞避免研究[J].四川师范大学学报：自然科学版，2019，42（01）：138-146.