WSN中基于粒子群最优算法的LEACH的改进路由

崔亚楠,韦 炜, 胡艳华

(1.广西科技大学鹿山学院,广西 柳州 545616；2.广西柳州钢铁集团有限公司,广西 柳州 545000)

0 引 言

无线传感网络(Wireless Sensor Networks, WSNs)在战场勘察、康复医疗、野外环境监测等应用中得到广泛使用。在这些应用环境中部署大量的传感节点，使传感节点实时感测环境数据，然后再传输至数据管理中心，进而实现对环境监控的目的。然而，由于节点能量供给的有限性，节点能耗是影响WSNs数据收集效率、制约网络生存时间的关键因素。一旦节点能量耗尽，就无法感测环境数据，形成了覆盖空洞，也缩短了网络生存时间[1-4]。

因此，提高网络能量利用率是WSNs的研究热点。目前，簇间路由被认为是拓延WSNs网络寿命有效方案。在基于簇的拓扑结构中，节点依据各自的条件和特性，承担不同角色。每个簇内产生一个簇首。多数节点成为簇内成员节点，而少数节点成为簇首。簇首收集簇内成员节点的感测数据，然后再传输至基站(Base Station, BS)。

基于簇网络结构有利于数据传输，减少能耗，也提高了网络生存时间。然而，由于簇首需要收集簇内成员节点数据，再向基站BS传输，使得簇首的能耗过大。因此，如何产生簇首以及簇形成成为研究热点。

低功耗自适应集簇分层 (Low Energy Adaptive Clustering Hierarchy，LEACH)[5]是典型的簇间路由。但LEACH路由仅从随机角度产生簇首，未考虑到节点能耗的差异性，也不适用于异构网络。由于没有从平衡网络能耗的角度产生簇首，LEACH路由缩短了网络生存时间。此外，Qing等[6]提出分布式能效的簇间路由(Distributed energy-efficient clustering，DEEC)。DEEC路由考虑了两级能量结构，但它在选择簇首时只考虑了节点的剩余能量，并没有考虑距离以及节点簇首比例的优化问题。为此，Kang等[7]对DEEC路由进行改进，并提出(Developed DEEC, DDEEC)路由。DDEEC路由通过动态改变产生簇首的标准，平衡网络能耗。

本文以LEACH路由为基础，首先分析了它的不足，再提出基于粒子群最优的LEACH改进路 由(Particle Swarm Optimal-based Improved LEACH, PSO-I)。PSO-I路由先从能耗角度推导最优的簇首比例，然后再利用粒子群算法产生簇首，优化簇的产生过程。仿真数据表明，提出的PSO-I路由能够有效地降低能耗，延长了网络生存时间。

1 问题描述

(1)

其中p表示簇首比例，p越大，网络内簇首数越多，节点成为簇首的概率就越大。而r为当前运行轮数，G为上一轮(r-1)未能成为簇首的节点集[8]。从式(1)可知，上一轮已成为簇首的节点不参与本轮的簇首选择，其目的在于平衡节点能量。

尽管LEACH路由考虑能量平衡问题，但仍存在一些不足：

(1)阈值并没有考虑到节点的剩余能量。如果节点剩余能量较少，一旦成为簇首，它的能量将很快消耗殆尽，这直接影响了网络寿命；

(2)LEACH路由中簇首比例p是固定，并没有依据考虑到网络能量分布信息；

(3)在设置阈值时，并没有考虑节点间的距离信息。如果距离过大，数据传输跳数将增加，加大了能量消耗。

为此，本文以LEACH路由为基础，并对其阈值进行修正，同时考虑异构传感网络，即节点初始能量存在差异。

2 系统模型

2.1 网络时间

PSO-I路由将网络时间划分等间隔的轮[9]，每一轮又划分为初始和数据传输阶段，如图1所示。

图1 网络时间

初始阶段，节点竞争成为簇首，并形成簇；而数据传输阶段，节点在自己的时隙内将感测数据传输至簇首。

2.2 能量模型

PSO-I路由引用如图2所示的能耗模型[10]。节点能耗主要来自发送电路、功率放大电路和接收电路。图2给出，传输m比特数据的能耗流程图。当传输m比特数据、传输距离为d时，所消耗的能量：

(2)

当接收m比特数据所消耗的能量Erv(m,d)=mEelec。

图2 能量消耗模型

3 PSO-I路由

3.1 簇首比例的优化

(3)

其中EDA为数据融合时所消耗的能量。而dToBS为簇首离信宿的欧式距离。

每一轮节点所消耗的能量：

(4)

其中dToCH表示簇首与普通节点间的平均欧式距离。假定节点为泊松分布，任意节点与它的簇首间的平均欧式距离的平方如式(5)所示：

(5)

因此，每一轮所消耗的能量Ecluster等于簇首所消耗的能量与节点所消耗的能量之和，如式(6)所示：

(6)

最终，网络在一轮内所消耗的能量Eround=MEcluster等于簇数与每一轮所消耗的能量乘积，如式(7)所示：

Eround=MEcluster

(7)

为了降低能量消耗，产生最优的簇首比例，对式(7)求导，并令其等于零，可得最优的簇首比例Mopt：

(8)

3.2 适度函数

依据式(8)形成n=NMopt个簇，这n个簇可形成簇集合CH={CH1,CH2,…,CHi,…,CHn}。为了选择更适合的节点作为簇首[12]，先定义适度函数，其包含了节点的剩余能量和节点密度信息。

首先，计算相对剩余能量率，其定义如式(9)所示：

(9)

除了考虑节点剩余能量外，还考虑节点的密度因子。节点密度反映了节点周围的节点数。周围节点是指节点最大通信范围R内的邻居节点。当周围节点距离小于R，则该节点就属于自己的邻居节点，如式(10)所示：

(10)

将通信范围R内节点数与簇首数之比定义为节点密度因子，如式(11)所示：

(11)

最终，可形成适度函数，其定义如式(12)所示：

(12)

3.3 基于改进粒子群的簇首选择算法

粒子群算法能够通过群体中个体之间的协作和信息寻找最优解。由于收敛速度快、高效，粒子群算法被广泛应用于解决实际问题[13]。为此，PSO-I路由利用粒子群算法产生簇首，具体过程如下：

(1)初始化

先产生一定数量的粒子，且每个粒子代表需要求解问题的初始解。假定有κ个粒子数，每个粒子的速度矢量和位置矢量分别如式(13)和式(14)所示：

ϑi=[ϑi1,ϑi2,…,ϑid]

(13)

xi=[xi1,xi2,…,xid]

(14)

利用速度和位置矢量表示每个粒子的状态，且d表示矢量维数。

(2) 粒子的适度值估计

依据式(12)计算每个粒子的适度值，并记录每个个体的最优解(局部)Pi=[pi1,pi2,…,pid]和全局最优解Pg=[pg1,pg2,…,pgd]。

(4)状态更新

每个粒子分别依据式(15)和式(16)更新自己的速度和位置：

(15)

(16)

其中r1、r2为随机常数，且r1、r2∈[ϑmin,ϑmax]。而c1、c2为加速因子。ω表示惯性权重因子。为了保证在搜索过程中不陷入局部最优，对ω进行更新改进：

(17)

其中ωmin、ωmax分别最小、最大的惯性权重因子。Kmax表示最大迭代次数，而k为当前的迭代次数。

3.4 簇形成过程

一旦成为簇首，就向周围节点广播Join消息。收到Join信息后，非簇首节点就选择最近的簇加入，进而成为该簇的成员。

4 性能仿真

4.1 仿真参数及性能指标

为了更好地分析PSO-I协议的性能，利用MATLAB建立仿真平台，并选择LEACH和DDEEC路由作为参照，比较它们的性能。假定网络内有100个节点随机分布于100 m×100 m区域内。具体的仿真参数如表1所示。每次实验独立重复100次，取平均值作为最终的实验数据。

表1 仿真参数

此外，选择网络生存时间、稳定时长以及基站成功接收的数据包数三个指标评估协议。网络生存时间是指网络内最后一个失效节点所发生的轮数；稳定时长是指网络内第一个失效节点所发生的轮数。

4.2 数据分析

(1)稳定时长和网络生存时间

图3显示了LEACH、DDEEC和PSO-I路由的网络生存时间和稳定时长。表2列举了10次实验数据。依图3可知，提出的PSO-I路由的稳定时长最长，达到1717轮，而LEACH、DDEEC路由的稳定时长分别为969、1355。原因在于：PSO-I路由利用粒子群改进算法优化产生簇首，减少了能量消耗，并平衡了网络能耗，进而延长稳定时长。此外，从图3可知，PSO-I路由的网络寿命最长，远高于LEACH路由。

图3 稳定时长和网络生存时间

(2)能量消耗

图4显示了在网络总体能量消耗至50%时，各路由所运行到的轮数。从图4的数据可知，在能量下降至50%时，PSO-I路由平均已运行了1082轮，而LEACH和DDEEC路由平均运行了477、478轮。

图4 能量消耗至50%时的运行轮数

此外，图5显示运行至1000轮时网络的剩余能量了，当各路由运行至1000轮时，PSO-I路由所剩下的能量远高于LEACH和DDEEC路由，能量利用率分别比LEACH和DDEEC路由提高了47.0%、36.6%。例如，在运行至1000轮时，PSO-I路由只消耗了22.0 J的能量，而LEACH和DDEEC路由消耗的能量分别达到48.6 J、47.5 J。

图5 运行1000轮后所消耗的能量

通过仿真数据不难发现，PSO-I路由能够有效地提高网络利用率，平衡能量消耗，延长网络生存时间。这主要归结于：PSO-I路由在每一轮总是试图选择最优的节点作为簇首，平衡节点间能耗。

5 结 语

针对WSNs的簇间路由，提出基于粒子群的LEACH改进算法PSO-I。PSO-I路由通过优化簇首比例, 平衡网络能耗，再充分利用粒子群算法在处理群体与人体关系的优势，选择最优的节点作为簇首。仿真结构表明，提出的PSO-I路由降低节点能耗，延长了网络寿命。