基于改进蜂群算法及K均值聚类的WSN分簇路由算法

王海玲 杨俊杰

(上海电力大学电子与信息工程学院 上海 200090)

0 引 言

在当前“云大物移智”等现代信息技术和先进通信技术快速发展的背景下，无线传感器网络成为物联网发展的重要支撑技术。无线传感器网络(Wireless Sensor Network，WSN)是由部署在监控区域内的大量具有感知、计算和通信能力的传感节点所组成的网络[1]，因其具有低功耗、低成本、组网灵活等优点，被广泛应用于军事、医疗、电力、商业、环境等领域[2]。无线传感器网络中传感器节点使用电池供电，但其自身能量有限同时受节点部署环境影响，电池无法及时更换或进行能量补充，因此需要选择合适的路由算法降低网络能耗，延长网络的生存时间[3]。

在当前能量高效路由算法中，基于分簇的路由算法能够有效地延长网络生命周期，大多分簇路由算法都借鉴了LEACH[4](Low-Energy Adaptive Clustering Hierarchy)算法的思想，簇内普通节点负责感知、从周围环境中收集信息并发送给簇头，簇头负责将接收到的数据进行融合、传输及网络管理[5]。LEACH是一种典型的低功耗自适应聚类路由协议，网络每轮随机选举一定数量的簇头，选举出的簇头收集簇间数据并以单跳形式向基站传输数据，由于选举簇头时没有考虑节点的剩余能量，容易导致低能量节点过快地死亡。EAMMH[6](Energy Aware Multi-hop Multi-path Hierarchical)是对LEACH的改进之一，具有与LEACH相同的两个阶段，但选举出的簇头收集簇间数据以多跳和多路径形式向基站传输数据，解决了簇内节点能耗不平衡的问题。Fuzzy C-means[7]以簇内通信距离为目标将网络分簇。簇头选举时考虑簇内其他节点间的平均路径损耗与基站路径损耗及候选节点的剩余能量等。KUCR[8]使用K-Means算法对网络分簇，但由于K-Means对初始聚类中心敏感，容易使分簇结果陷入局部最优，簇头轮换时没有考虑簇头与其他节点的距离关系。

本文提出基于改进蜂群算法和K均值聚类的能量均衡路由(IABCKEB)算法。首先通过IABC-K(Improve ABC and K-Means)聚类算法对传感器节点进行均匀分簇，网络运行期间簇结构保持不变；然后在簇头选举时综合考虑传感器节点的剩余能量和综合距离，并根据网络状态实时调整其权重；最后建立簇间层次路由树确定最优通信路径进行数据传输。结果证明该路由算法有效地均衡网络能耗，明显地延长网络生命周期。

1 网络与能耗模型

1.1 网络模型

假定无线传感器网络具有如下性质：(1) 传感器节点随机部署在监测区域，位置固定；(2) 所有传感器节点初始能量固定且相等；(3) 传感器节点有唯一的ID，且都具有位置感知能力；(4) 传感器节点担任簇头时具有数据融合去除冗余能力；(5) 基站位于监测区域中心，基站能量无限。

1.2 能耗模型

本文使用一阶无线电模型[4]，当通信距离小于传输距离阈值时，使用自由空间信道模型，否则采用多路径衰减模型，εfs、εmp分别为两模型对应下的传输增益，Eelec为每比特数据在发送或接收时消耗的能量，EDA为节点融合每比特数据消耗的能量。节点发送k比特数据到距离d的接收节点，其所消耗的能量ETX(k,d)为：

(1)

节点接收k比特数据所消耗的能量ERX(k)为：

ERX(k)=kEelec

(2)

若节点为簇头，则经过距离d发送k比特数据所消耗的能量ETX(k,d)为：

(3)

传输距离阈值d0为：

(4)

2 算法设计

2.1 簇的形成

为了降低簇头与簇内节点通信的能量消耗，本文使用IABC-K算法对传感节点进行分簇，成簇结果均匀并优化了簇头与簇内节点间的距离。网络运行期间簇结构保持不变，避免了频繁成簇带来的额外能量消耗。簇内普通节点与簇头直接通信。

2.1.1最佳簇头个数

使用IABC-K算法对传感节点进行分簇前需要确定分簇个数，簇数太多会使数据传输路径较长，造成通信时延；簇数太少会使簇内节点距离大，簇内通信能耗高。因此，最佳簇头个数是与分簇算法相关的重要参数。为取得网络最佳性能，利用式(5)计算最佳簇头个数Kopt[9]。

(5)

式中：N为传感器节点总个数；A为传感器监测区域面积；L为传感器节点到基站的平均距离。

2.1.2原始的K-Means算法

K-Means算法是一种经典的聚类方法[10]，假设X=(x1,x2,…,xn)为聚类样本，xi为d维向量，k个节点的聚类中心记作K=(K1,K2,…,Kk)。

其目标函数S=(s1,s2,…,sk)为：

(6)

聚类中心坐标更新的公式为：

(7)

2.1.3人工蜂群(ABC)算法

人工蜂群(ABC)算法是模拟蜂群觅食行为的群体智能优化算法。ABC算法包括四个连续的阶段：初始阶段、雇佣阶段、跟随阶段和侦察阶段。蜂群中蜜蜂分为雇佣蜂、跟随蜂和侦察蜂三类，其目标是寻找高质量的蜜源[11]。

算法思想为：在初始阶段，首先在边界划定的范围内随机确定N个蜜源位置；在雇佣阶段，雇佣蜂发现蜜源并在各蜜源附近按式(8)搜索得到新蜜源，根据新旧蜜源的适应度值更新蜜源；在跟随阶段，跟随蜂按照式(9)计算概率选择要跟随的蜜源，并根据式(8)搜索得到新蜜源并选取较优蜜源；在侦察阶段，当雇佣蜂连续经过若干次没有更新蜜源，则该只雇佣蜂变成侦察蜂，并随机寻找新蜜源。

具体算法流程如图1所示。

图1 人工蜂群算法流程

领域搜索公式为：

vij=xij+rij(xij-xkj)k≠i,rij∈[-1，1]

j∈{1,2,…,d},k∈{1,2,…,K}

(8)

概率计算公式：

(9)

2.1.4基于改进人工蜂群的IABC-K算法

本文对ABC算法的适应度函数fitnessj做如下改进：

fitnessj=KNj/Jjj=1,2,…,k

(10)

式中:KNj为第j类内节点的个数。

算法思想是对IABC算法和K-Means聚类两者交替执行直到满足最大迭代次数，IABC-K算法的伪代码如算法1所示。

算法1IABC-K算法伪代码

1. Load dataset

2. Set the number of employed bees and follow bees, SetMCN,LimitandK

3. Generate the initial populationxj={x1,x2,…,xK}

4. Setcycleto 1

5.Repeat

6.FOREvaluate the fitness(fi) of the population by (11)

7.FOReach employed bee {

Produce new solutionviby (9)

Calculate the valuefi

Apply greedy selection process}

8. Calculate the probability valuespifor the solutions (xi) by (10)

9.FOReach follow bee {

Select a solutionxidepending onpi

Produce new solutionvi

Calculate the valuefi

Apply greedy selection process}

10.Ifthere is an abandoned solution for the scout

Thenreplace it with a new solution which will be randomly produced

11. Using the new solutionvi

Clustering on the dataset perform once K-means iterative

12. Memorize the best solution so far

13.cycle=cycle+1

14.Untilcycle=MCN

IABC-K算法提出新的适应度函数表示为簇内节点到簇中心平均距离的倒数，当适应度越大时，簇内节点平均距离越小，簇内节点通信能耗越小。IABC-K算法同时改善了K-Means全局搜索能力差的问题，使得分簇结果比较均匀，从而网络负载均衡。

2.2 簇头选举

网络能耗主要包括所有传感器节点数据接收的消耗、簇头通过单跳或多跳方式到基站的数据传输消耗以及其他簇头到基站的数据中继消耗[12]。为实现网络能耗均衡，簇头选举时综合考虑传感器节点的剩余能量和综合距离两个因子，并根据网络状态实时调整两个因子的权重。综合距离是指节点到基站的距离及节点与簇内其他节点之间的距离。

为实现网络负载均衡，应尽可能使剩余能量较高的节点担任簇头，剩余能量因子W(Ek)为:

(11)

传感器节点到基站的距离和节点与簇内其他节点之间的距离越小，数据传输的能耗也越小[13]。综合距离因子D(vk)的计算公式为：

(12)

式中：m为节点k所在簇的节点总个数；d(k,ME)为节点k到基站的距离；d(k,j)为节点k、j之间距离。

节点根据式(13)计算自身参量Wk-ch，选择簇内自身参量最大的节点为当前簇头：

Wk-ch=aW(Ek)+bD(vk)

(13)

式中：a、b为权重参数，且a+b=1。

(14)

式中：E0为节点初始能量，随着网络的运行，权重参数a逐渐增大，节点剩余能量成为选举簇头的关键，有利于网络负载均衡。

2.3 簇间通信

无线传感网络中传感器节点的发射能耗与发射距离成正比，当簇头与基站距离较远时，直接通信能耗较大，所以需要选择合适的中继簇头进行数据传输以减少簇间通信能耗[14]。本文采用文献[9]中建立簇间层次路由树方法,将下一跳节点的距离与剩余能量作为其是否当选为中继节点的标准，从而避免低能量簇头担任过多转发任务而过快死亡。

节点根据式(15)计算下一跳节点权值Wtr。

(15)

式中：E(t)、E(r)分别为发送数据簇头C(t)和接收数据簇头C(r)的剩余能量；ΔE(t)和ΔE(r)为计算出的能量消耗。

3 仿真与实验

3.1 仿真环境

本文使用Windows平台下的MATLAB R2014a软件对LEACH、EAMMH和IABCKEB三种算法进行了仿真实验，IABC-K算法中设置最大迭代次数MCN=100，控制参数Limit=20,聚类数目K=20。仿真实验在100 m×100 m的区域内随机部署100个传感器节点,基站位于区域中心(50 m,50 m)，设定传感器节点初始能量为0.1 J,数据包大小为4 000 bit，εfs为10 pJ/(bit·m2)，εmp为0.001 3 pJ/(bit·m4)，Eelec为50 nJ/bit，EDA为5 nJ/bit。

3.2 IABC-K分簇结果分析

在同一无线传感网络环境中，IABC-K算法、LEACH和K-Means算法的成簇结果如图2-图4所示。可以看出，LEACH使用随机选举簇头，普通节点再入簇的成簇方法，使得成簇大小不均匀；K-Means算法使用均匀分区的方法进行分簇，但容易出现局部最优，使得成簇结果大小不一，不均匀的分簇必然会导致网络负载不均衡[15]。IABC-K算法解决了K-Means算法出现局部最优的缺点，改进的ABC算法使得簇内节点平均距离较为合理，从而簇内节点通信能耗较小。结果证明IABC-K算法的成簇均匀性和簇间的通信距离更加合理。

图2 LEACH成簇

图3 K-means成簇

图4 IABC-K成簇

3.3 生命周期及网络能耗分析

网络生命周期是指网络开始运行到出现第一个死亡节点期间的运行轮数[16]。从图5可以看出，LEACH和EAMMH算法分别在第76轮和第95轮出现第一个死亡节点，本文所提出的IABCKEB算法在第219轮时出现死亡节点；LEACH和EAMMH算法中，节点在第250轮左右时全部死亡，在IABCKEB算法中，节点在第280轮左右全部死亡。

图5 生命周期对比

图5表明，相比LEACH和EAMMH算法，IABCKEB算法可以明显地延长网络的生命周期。因为IABCKEB使用了IABC-K算法使网络分簇更均匀；在选择簇头时考虑节点的综合距离也考虑节点的剩余能量，实现负载均衡；而且通过建立簇间层次路由树方法完成簇头与基站之间的通信，选择中继节点同时考虑下一跳节点距离与剩余能量，从而避免低能量簇头担任过多转发任务而过快死亡。

三种算法的网络剩余能量比较如图6所示。可以看出，在网络的整个运行过程中，IABCKEB的网络剩余能量始终是最高的，说明IABCKEB算法能明显地降低网络的能量消耗，这是因为IABC-K算法分簇均匀；簇头轮换降低簇内通信能耗；簇间通信通过最优路径进行数据传输，从而降低了网络能耗。

图6 网络剩余能量对比

4 结 语

无线传感器技术以低成本、可靠性高的特点成为物联网重要组成部分[17]。为了延长无线传感器网络的生命周期，本文提出基于能量均衡的IABCKEB路由算法。首先通过IABC-K聚类算法对传感器节点进行均匀分簇，网络运行期间簇结构保持不变；然后在簇头选举时综合考虑传感器节点的剩余能量和综合距离，并根据网络状态实时调整其权重；最后建立簇间层次路由树确定最优通信路径进行数据传输。仿真结果表明，IABCKEB路由算法能够有效均衡网络能耗，明显地延长网络生命周期。本文仅考虑电池能量有限的无线传感网络，接下来将进一步研究无线可充电传感网络的能量优化问题，以及充电设备的充电路径规划问题和大规模无线传感网络中多个充电设备的协同调度问题。