基于贪婪算法的树形WSN 低功耗路由算法

肖 剑，何志成，胡 欣，张 赞，袁 晔

（1.长安大学 电子与控制工程学院，陕西 西安 710064；2.长安大学 能源与电气工程学院，陕西 西安 710064；3.宁夏回族自治区无线电监测站，宁夏 银川 750001）

0 引 言

无线传感器网络主要由大量具备无线通信能力的传感器节点和少量基站组成，传感器节点对相关监测数据进行采集，然后将数据无线传输给基站以便数据的后续处理和分析，从而使无线传感器网络实现对某一片区域的实时监测。然而传感器节点大多被安装在人难以触及的地方，使得传感器节点难以维护，所以传感器节点大都由电池进行供电，而一旦电能耗尽，该传感器节点会立即失效。因此，如何在能量有限的情况下使尽可能多的传感器节点有尽可能长的生命周期已成为无线传感器网络技术领域的重要研究方向。

针对无线传感器网络存在的能耗问题，Heinzelman 等[1]提出了基于分簇路由协议的LEACH 算法，通过等概率随机选取簇首的方式使整个网络中各个节点的能耗尽可能均衡，进而使更多的节点有更长的生命周期。但是LEACH 算法在选取簇首时，没有考虑到节点的剩余能量、节点所处的位置以及节点密度，这就有可能使某些节点过快凋亡。Lindsey等[2]提出了PEGASIS 算法，该算法将网络中的节点逐个连接起来形成长链，然后沿着长链进行数据传输，最后再将数据传输给基站。刘伟强等[3]针对无线传感器网络中的PEGASIS协议进行了研究与改进，该算法以基站为圆心将无线传感器网络的监测区域分成若干个幅度相等的扇形区域，然后分别在每个扇区内形成通信树，数据先由通信树的树叶传输到树根，然后树根再传输给基站。该算法通过通信树的传输方式有效降低了节点的传输能耗，但是均匀划分扇区的策略可能导致某些扇区的节点都距离基站较远，使得这些扇区中节点的能量消耗过快。王海浪等[4]提出一种基于PEGASIS 的剩余能量距离分区（PEGASIS-REDP）协议，该算法在建立网络连接时对网络进行均匀分区并分别在每个分区中单独成链以降低传输链中差链的数量。该算法通过降低差链数量有效降低网络的能耗，但是仍然无法避免传输链上出现差链而导致部分节点能量消耗过快。胡中栋等[5]提出一种双层树型高能效多链路由算法，该算法在成链时使基站附近的节点不入链以降低分链和链头链的能耗，用启发式算法优化链的传输路径；选取主链头时综合考虑节点的剩余能量和节点与基站的距离，在选取分链头时综合考虑了节点的剩余能量和节点与相邻分链头的距离。但是分链之间的传输距离过长导致链头能量消耗过快。安葳鹏等[6]提出基于改进灰狼优化算法的无线传感器网络路由协议，该算法将无线传感器网络的监测区域进行分区，先以基站为圆心将区域划分为多个环带，然后在环带的基础上进行扇形划分以降低节点的远距离传输能耗，再分别在每个分区中单独成链，最后利用改进的灰狼优化算法选取簇首。然而该算法的分区方式可能导致部分扇区中节点过于分散，使得这些节点的能量消耗过快。

针对以上算法存在的问题，本文提出基于贪婪算法的树形WSN 低功耗路由算法，该算法引入树的概念，并通过贪婪算法形成树，然后基于传输距离最近原则进行树的融合，最后使所有树的根延伸到基站。

1 网络模型

1.1 系统模型

本文假定所有传感器节点随机分布在正方形区域内，并有以下设定：

（1）无线传感器网络由多个传感器节点和一个基站组成；

（2）基站的能量无限制；

（3）传感器节点和基站都是静止的，且它们的坐标都是已知的；

（4）每个节点都有唯一固定的ID 号；

（5）任意节点都能进行数据融合。

1.2 能耗模型

本文中网络的能耗模型采用与文献[4]相同的一阶无线电能耗模型。

发送L比特数据所消耗的能量计算公式为：

式中：Eelec为发射电路和接收电路的功耗；εfs为自由空间信道模型下放大器功率的放大倍数；εamp为多路径衰减模型下放大器功率的放大倍数；d为发送节点与接收节点之间的欧氏距离；为划分空间模型的阈值。

接收L比特数据所消耗的能量计算公式为：

对长度为L比特的数据包进行融合时消耗的能量Eda的计算公式为：

2 基于贪婪算法的树形WSN 低功耗路由算法

2.1 贪婪算法

贪婪算法（Greedy Algorithm）又称贪心算法，具有实现简单和时间复杂度低的特点[7-10]。它的基本思想是基于当前最优解做出选择，也就是在每一步选择时只考虑最有利的选择，而不会综合考虑多次选择对结果的影响，即只考虑眼前的最优选择[11-13]。

2.2 数据传输阶段

树上的节点分为三类，分别是树根节点、树干节点和叶节点。一棵树只有一个树根节点，树上所有节点的数据全都朝着树根节点的方向传输，树根节点负责接收数据、融合数据和发送数据；树上的叶节点是树的端点，只负责发送数据；除了树根节点和叶节点，树上其余的节点全都是树干节点，树干节点负责接收数据、融合数据和发送数据。因此，树根节点和树干节点的能耗相对较高，叶节点的能耗相对较低。

本文算法的数据传输阶段参考经典PEGASIS 算法[2]的方式，如图1 所示，在一棵树上有5 个节点，分别是A1、A2、A3、A4和A5。其中A5为树根节点，A2和A4为树干节点，A1和A3为叶节点。该树的数据传输方向是其他节点朝着节点A5的方向传输数据。在数据传输阶段，节点A1先将数据传输给节点A2，节点A2将接收到的数据与自身采集到的数据进行融合并得到一个相同长度的数据包；然后节点A2和节点A3将数据传输给节点A4，节点A4将接收到的数据与自身采集到的数据进行融合并得到一个相同长度的数据包；最后节点A4将数据传输给节点A5，节点A5将接收到的数据与自身采集到的数据进行融合并得到一个相同长度的数据包。

图1 数据传输过程

2.3 本文算法中的定义

定义1：若在路由协议下无线传感器网络中某两点（包括节点和基站）之间可直接传输数据，则将这两点之间直接传输数据的路径称为“可用路径”，网络中全部“可用路径”构成的集合称为“可用路径集合”，并用S表示。

定义2：任意点Ai（包括节点和基站）以及从点Ai出发沿集合S中的路径可以到达的全部点构成一棵树的全部点，一棵树的全部点和集合S中连接这些点的全部路径构成一棵树。

定义3：设树Vi中与树Vi外某一点Ai之间距离最近的点是Bi，则树Vi与Ai之间的距离等于Bi与Ai之间的距离。

2.4 基于贪婪算法形成树

基于贪婪算法，每个节点只能将数据传输给距离自身最近的点（包括节点和基站），此时集合S包含且仅包含每个节点到距离其自身最近的点（包括节点和基站）之间的路径，将数据传输给距离最近的点能够有效降低每个节点传输数据的能耗，通过这种方法使多个节点形成数据传输链，这种数据传输链就是树[14-15]。

在本文中，将树分为第一类树和第二类树，包含基站的树为第一类树，不包含基站的树为第二类树。在基于贪婪算法形成树后，如果在树中不存在两个节点使得这两个节点互为距离彼此最近的节点，那么理论上该树可以无限长并且能够延伸到基站，这类树就是第一类树，第一类树的树根为基站。如果在树中存在两个节点使得这两个节点互为距离彼此最近的节点，则该树上的其他节点都会朝着这两个节点的方向传输数据，因此该树有限长且不与基站相连，这类树就是第二类树。

2.5 树的融合

由于第二类树不与基站相连，第二类树上的节点无法沿集合S中的路径将数据传输给基站，因此需要将第二类树转化为第一类树。为了将第二类树转化为第一类树，需要对树进行融合。对树进行融合的步骤是重复执行如下步骤，直到第二类树的个数为零：找出与第二类树距离最近的点（包括节点和基站），若距离最近的点是基站，则将基站与该树中距离基站最近的节点之间直接传输数据的路径添加到集合S中，此时该树转化为第一类树；若距离最近的点是节点，则将该节点与该树中距离该节点最近的节点之间直接传输数据的路径添加到集合S中，此时两棵树融合成一棵树。

当第二类树的个数降为零时，则表示网络的数据传输路径确定下来，然后就可以进行数据传输了。进行数据传输时，只能沿集合S中的路径进行数据传输，并且总是朝着基站的方向进行数据传输。

2.6 能耗平衡

首先引入能量差额因子概念，节点Ai的能量差额因子Sub(Ai)的表达式为：

式中：N表示网络中存活节点个数；Ej表示第j个存活节点Aj的剩余能量。

将网络中的存活节点分为两类，能量差额因子大于阈值α的节点构成集合U1，其余节点构成集合U2。

为了避免某些节点能量消耗过快从而导致无线传感器网络的监测区域出现覆盖空洞，在形成树和融合树时做如下处理：

（1）在利用贪婪算法形成树时，为了使集合U1中的节点不成为树干节点以降低能耗，不考虑集合U1中的节点而只将集合U2中的节点连接形成树。在利用贪婪算法形成树之后，在集合U2中分别为集合U1中的每一个节点寻找一个距离最近的节点，并将集合U1中的节点和在集合U2中与它们距离最近的节点之间直接传输数据的路径添加至集合S中，使得集合U1中的节点都形成树的叶节点以降低这些节点的能耗，至此所有存活节点都形成树。

（2）在对树进行融合时，为了避免集合U1中的节点由叶节点变成树干节点从而增大能耗，在计算树与节点的距离时不考虑树内属于集合U1的节点（计算树与节点的距离时，假定树内属于集合U1的节点不存在），在寻找距离第二类树最近的节点时同样不考虑集合U1中的节点。

2.7 本文算法流程

本文算法的流程如下：

（1）计算每个存活节点的能量差额因子，然后根据能量差额因子将全部存活节点分为U1和U2两个集合；

（2）为每个存活节点寻找距离最近的存活节点；

（3）利用贪婪算法将集合U2中的节点连接形成树；

（4）将集合U1中的节点作为叶节点接入树；

（5）进行树的融合，直到第二类树的个数降为零；

（6）开始数据传输，首先是叶节点将数据传输给树干节点，然后树干节点沿着树干向数根节点（即基站）传输数据；

（7）本轮数据传输完成，并统计死亡节点ID 号，若节点未全部死亡，转向步骤（1）。

3 实验仿真及算法性能分析

3.1 仿真参数及性能指标

为分析算法的性能，本文利用MATLAB 对算法进行仿真，并将本文提出的算法与LEACH 算法[1]、PEGASIS 算法[2]和PEGASIS-REDP 算法[4]进行对比。

无线传感器网络的仿真模型：设定在400 m×400 m 正方形区域内随机分布100 个节点，在正方形区域的正中心有一个基站，本文算法中能量差额因子的阈值α取0.01 J。其他仿真参数见表1 所列。

表1 仿真参数

网络剩余总能量的变化情况反映了网络总体能量的消耗速度以及能量的利用率，而存活节点个数的变化情况反映了无线传感器网络的监测区域覆盖率和无线传感器网络的生命周期。因此本文用网络的剩余总能量和存活节点个数这两项指标来评估算法的性能。

3.2 树的形成和融合过程

传统PEGASIS 算法通过单链形式传输数据，导致传输链上差链较多从而使差链一端的节点能耗过高。本文算法首先利用贪婪算法形成树，然后对树进行融合直到第二类树的数量降为0，以避免差链的出现；同时引入能量均衡机制，避免剩余能量过低的节点接收数据和融合数据。网络中树的形成以及树的融合如图2 所示。

图2 树的形成和树的融合

3.3 网络存活节点个数对比

不同算法下存活节点数随轮数的变化情况如图3 所示。

图3 存活节点数随轮数的变化情况

根据图3 可知，本文算法下的网络中首个节点死亡时间相较于LEACH、PEGASIS 和PEGASIS-REDP 算法分别延长了89.1%、81.8%和68.3%。当有节点死亡后，就可能造成无线传感器网络监测区域的覆盖空洞，数据表明本文算法能够有效延长网络在监测区域无覆盖空洞时的工作时长。本文算法下的网络中全部节点死亡时间相较于LEACH、PEGASIS 和PEGASIS-REDP 分别延长了70.4%、27.1%和14.4%，表明本文算法能够有效延长网络的生命周期。

3.4 网络剩余总能量对比

不同算法下网络的剩余总能量随轮数的变化情况如图4所示。

图4 剩余总能量随轮数的变化情况

从图4 可以看出，本文算法下网络的剩余总能量始终高于LEACH、PEGASIS 和PEGASIS-REDP 算法，并且当网络剩余总能量为50%时，LEACH、PEGASIS、PEGASIS-REDP和本文算法下的网络分别运行了269 轮、446 轮、468 轮和549 轮。这表明相较于其他三种算法，本文算法的能量利用率更高。

4 结 语

本文针对PEGASIS 算法存在的问题，提出基于贪婪算法的树形WSN 低功耗路由算法，该算法引入树的概念，并利用贪婪算法将节点连接起来形成树；并且为了降低剩余能量过低的节点的能耗，在形成树时避开剩余能量过低的节点，形成树之后再将这些节点连接到树上，然后基于距离最近原则进行树的融合，直到所有树都以基站为树根。通过算法的仿真结果对比，表明本文所提出的算法在延长网络生命周期、平衡节点能耗和提高能量利用率方面都明显优于LEACH、PEGASIS 和PEGASIS-REDP 算法。