基于生物地理学优化的分簇算法

党梦丽，张书奎

(苏州大学 计算机科学与技术学院，江苏 苏州 215006)

0 引 言

随着5G移动通信技术、软件定义网络、移动边缘计算等新兴技术的发展和深入研究，当今生活中，大多数应用都需要传感设备从环境中收集数据，这使得移动传感器网络(mobile sensor networks，MSNs)的应用提升到一个新的高度[1-4]。传感器被嵌入到各种设备和物体中，如手机、手环、衣物[5]、自行车、汽车等，用于收集应用所需的有关信息。MWSN在自动驾驶、水下导航、健康检测、疫情追踪与防控等应用中起着重要作用。但各种各样的用户设备会产生大量高可变的数据[6]。同时，节点故障和移动等因素会使网络拓扑发生改变，如何有效组织网络中传感器节点间的通信，在保证数据传输稳定性的同时延长网络生命周期是MSNs的关键问题。

负载均衡技术可以通过均衡节点间的能量消耗，以避免节点过早死亡，从而达到延长网络生命周期的作用。考虑到网络中设备的多样性，文献[7]提出了SEP算法，该算法引入了异构网络的思想，根据节点的初始能量不同划分节点类型，该方法有效延长了网络的稳定周期。随着群体智能优化算法的发展，近年来有研究学者利用群智能优化算法来解决簇头选择问题。比如PSO[5,8,13]、生物地理学算法(BBO)[9,10,12]、GA[11]等通过对网络中的多个指标的综合优化，提高簇结构的合理性，达到均衡节点能量消耗和延长网络生命周期的目的。为更好优化簇结构，文献[12]提出了一个基于K-means和BBO的异构无线传感器网络下的混合分簇算法，为获得具有较高质量的栖息地，将K-means用于BBO种群初始化阶段，然后利用BBO进行分簇，该方法减少了节点能量消耗。Morteza等[13]提出了一个混合PSO与和声搜索算法(HAS)的能量高效分簇路由算法，其在提升网络覆盖、数据包传输和延长网络生命周期方面表现出良好性能。

基于以上分析，本文提出基于BBO来优化MSN分簇的集中式分簇算法。该算法通过选择具有较好特性的节点初始栖息地，提高算法的收敛速度。并采用余弦迁移模型来进一步提升算法的探索效率。最后，通过重新定义目标函数，来优化簇结构。其有效减少节点能量消耗，平衡了网络负载，从而延长了网络生命周期。

1 系统模型

1.1 网络模型

假设网络中有N个节点随机分布在检测区域内，基站位于区域中心。如图1所示，节点之间动态成簇，簇内和簇间以单跳方式通信。同时，本文基于3层异构网络，网络中的节点根据初始能量不同，分为3类节点，即普通节点、中级节点和高级节点。

图1 不同时刻网络动态聚簇

1.2 能量模型

本文采用与文献[7,9]相同的能量消耗模型，对于相距为d的两节点间传输L比特数据，发送端的能量消耗见式(1)

(1)

其中，Eelec为射频能耗系数，表示每发送或接收1比特数据所消耗的能量，εfs、εmp分别为自由空间传播模型和多路衰减模型中放大功率所需要的能量，d0为自由空间模型和多路径衰减模型的临界距离，即

(2)

相应地，传感器节点接收同样大小的数据包需要消耗的能量由式(3)所示

Erx=k*Eelec

(3)

2 基于BBO算法求解MWSN分簇问题

在应用BBO算法求解MSN分簇问题的过程中，由基站通过CABBO算法以集中的方式控制选择簇头节点。该协议主要分为3个阶段，如图2所示，在信息收集阶段，基站发送信息请求数据包，网络中的所有节点把自身到基站的距离、剩余能量和邻居节点个数信息发送到基站；然后，基站计算网络当前平均剩余能量、平均邻居个数、节点到基站的最大距离；在簇建立阶段，基站执行CABBO算法，将相关参数输入到算法中，获取最优簇头集并广播簇头信息。节点根据簇头状态信息确定自己的角色，普通节点发送请求信息，选择最近簇头。簇形成后进入数据传输阶段，簇成员节点发送数据信息到簇头，簇头节点将数据汇聚后发送到基站。

图2 本协议整体流程

2.1 BBO算法

Dan Simon[14]受生物地理学启发提出了生物地理学优化算法(biogeography-based optimization，BBO)，该模型根据现实世界中物种的产生与灭绝，以及在栖息地间的迁移，最终达到平衡状态的自然规律，所形成的一种新型的智能优化算法。其中，BBO算法包含初始化、迁移和突变3个步骤。

(1)初始化：首先，将问题的每个解集看作“栖息地”(Habitat)，随机生成N个栖息地，1个栖息地供一个种群生存，每个栖息地包含D维解向量(suitability index variable，SIV)。

(2)迁移：为避免算法陷于局部最优，通过迁移操作实现栖息地间的信息交换，增大BBO算法的寻优范围，从而改变现有解决方案。迁移算子则是根据迁入率λ和迁出率μ随机选择迁移解决方案，从选定的栖息地解决方案中替换需要迁出的物种。其迁移模型为线性迁移模型，如下所示

(4)

(5)

其中，I为最大迁入率，E为最大迁出率，S代表栖息地当前物种数量，Smax代表最大物种数量。

(3)变异：变异算子通过产生的随机值来探索比当前更好的解决方案。通过突变，可能会使其变为更好的方案。栖息地的突变概率用Ms表示，定义如下

(6)

其中，Mmax为最大突变率，Ps表示栖息地容纳物种数量为S时的概率，即对于给定问题预先存在的可能性Pmax为栖息地容纳最大物种数量的概率。

2.2 CABBO算法

为提高BBO在分簇算法中的适应性，以及算法的收敛速度和性能。本部分主要并从以下3个方面提高改进BBO算法在MSN分簇方面的适应性。

(1)针对基于BBO的分簇算法初始化栖息地种群，存在的探索效率低问题，本文通过考虑节点剩余能量、邻节点个数、与基站距离等因素，选择具有较好特性的节点来提高初始栖息地的质量，以提高算法的探索效率和收敛速度。

(2)为保证网络的有效连接，适应网络的动态变化，通过权衡节点能量消耗与负载均衡，综合考虑簇紧凑度、簇头分离程度、节点能量消耗和能量均衡因子，重新定义目标函数，以优化簇结构和网络拓扑，使簇头分布更加合理。

(3)在迁移阶段，我们引入余弦迁移模型来进一步提升算法的探索效率。

2.2.1 簇头概率函数

簇头节点承担着数据汇聚与传输工作，为提高网络动态连接的稳定性，需要选择具有较好特性的节点来充当簇头。簇头节点需要消耗较多能量，因此，能量因素起着重要作用，通过提高剩余能量高的节点成为簇头的概率，可以增强簇结构的稳定性。同时，节点的邻居节点个数(节点度)是评定节点汇聚和转发能力的有效指标，而节点与基站的距离则影响着数据传输的成本。因此，通过综合这3个因素来确定节点成为簇头的概率，用psi表示节点si成为簇头的可能性，定义如下

(7)

其中，p为初始设定的节点成为簇头的概率，Esi、Nsi、Dsi分别为节点si的当前剩余能量、邻居个数、到基站的距离；Eave、Nave、MaxD分别为网络当前平均剩余能量、平均邻居个数、节点到基站的最大距离。α1、α2、α3为权重因子，α1+α2+α3=1。 通过实验仿真，当α1=0.5、α2=0.25、α3=0.25时，选出的候选节点具有较好的特性。

2.2.2 目标函数

为使得优化后的网络拓扑可以提高节点能量利用率与数据传输率，保证簇结构的合理性。本文综合考虑簇紧凑度Comp、 簇分离程度Sep、 总能量消耗和能量均衡因素来定义目标函数。簇紧密度反映了簇内距离，即簇内成员节点到簇头节点的距离

(8)

其中，CHs表示簇个数，sj表示在第i个簇Ci中的第i个成员节点，CHi表示第i个簇Ci的簇头节点。簇分离程度则反映了簇头之间的距离，其定义如下

(9)

其中，CHi、CHj分别表示簇Ci、Cj的簇头节点。总能量消耗反映了簇头节点的总能量消耗和非簇头节点的总能量消耗。其中，簇头节点能量消耗包含接收来自簇成员节点数据的能量消耗，融合数据的能量消耗，以及将数据传输到基站的能量消耗。非簇头节点的能量消耗包含将数据发送到簇头的能量消耗

TotalE=Energynon-CHs+EnergyCHs

(10)

另外，保持节点间的能量均衡也是设计路由协议需要考虑的关键因素，它直接影响网路的有效工作时间。因此，在目标函数中加入能量平衡因子，可以有效评估栖息地的适宜值，使划分的簇更加合理，其定义如下

(11)

其中，Eave为网络当前平均剩余能量，Nalive为网络当前存活节点个数，Esi为节点si当前的剩余能量。目标函数定义如下

F=β1*Comp/Sep+β2*TotalE+β3*EB

(12)

其中，β1、β2、β3为权重因子，β1+β2+β3=1。 通过仿真实验和观察，当β1=0.3、β2=0.3、β3=0.4时，所提出算法具有更好的性能。最小化Comp可以减小簇内通信能耗，最大化Sep可以使簇头分布更加均匀，进一步减少通信能耗；同时，EB值越小则节点负载越均衡。因此，目标函数的值越小，分簇方案越好。选择目标函数的倒数作为栖息地的适应度函数，BBO算法通过该适应度函数评估每个栖息地的适宜性指数HSI，根据HSI保留最佳的解决方案。

2.2.3 迁移模型

BBO算法根据线性迁移模型计算迁入率和迁出率，通过将较优解中的元素替换较差解中的元素，以实现解决方案的探索。但线性迁移模型过于简单，存在适应性不足、探索效率低的问题，有关学者根据现实世界中种群的分布情况，提出了不同的迁移模型改进算法，比如二次迁移模型、余弦迁移模型、指数迁移模型等。其中余弦迁移模型更接近自然规律，可以有效提高BBO算法的优化性能[15]。因此，本文采用该迁移模型，迁入率λ和迁出率μ的计算分别如下所示

(13)

(14)

对于每一个解决方案Hi， 在迁移过程中，根据式(13)、式(14)分别计算其节点si的迁入率λi和迁出率μi， 根据λi确定是否进行迁入操作栖息地迁移过程中，若发生迁入，则根据轮盘赌法选择迁出的位和栖息地Hj， 在Hi要迁入的位用Hj的相应位进行替换。

2.3 基于CABBO的分簇算法

2.3.1 算法流程

(1)编码与种群初始化

BBO迁移策略类似于GA和进化策略的全局重组方法，但又有所不同。在进化方法中通过重组多个父代以形成一个后代，全局重组用于创造新的解，而BBO迁移用于改变现有解，其迁移过程如图3所示。进化策略中的全局重组是一个再生的过程，而BBO中的迁移是一个适应性的过程，它用来改变已存在的栖息地。

图3 栖息地的迁移过程

在初始化阶段，一个栖息地代表分簇问题的一个解决方案，其由一组传感器节点组成，包括簇头节点、普通节点和死亡节点。也就是说，一个栖息地的大小等于网络中节点个数。对每个栖息地的解向量进行二进制编码，我们用0代表普通节点，用1表示簇头节点，而死亡节点则用-1表示。图3举例展示了栖息地种群初始化情况，在图4中考虑了11个节点，其中节点1，3，7，8，10为簇头节点，其它节点为普通节点。

图4 种群初始化示例

为提高解决方案的质量，同时增强算法的探索能力，通过选择具有较好特性的节点来初始化栖息地编码。根据式(7)计算节点si成为簇头的概率pi。 如果节点si的状态不是-1，则随机产生一个 (0,1) 间的值randi。 若其小于pi， 则该节点初始状态为1，否则初始化为0。栖息地种群具体初始化过程如算法1所示。

算法1：基于BBO的栖息地种群初始化

(1)输出：M×N的矩阵(M为解决方案个数，N为节点总数)

(2) For each solution in population do

(3) For each feature in solution do

(4) %根据式(7)计算每个节点的pi

(5) Ifrandi

(6) feature=1;

(7) Else

(8) feature=0;

(9) end if

(10) end for

(11) end for

(2)迁移操作

对于每一个解决方案Hi， 在迁移过程中，根据式(13)、式(14)分别计算其节点si的迁入率λi和迁出率μi， 根据λi确定是否进行迁入操作，若发生迁入，则根据轮盘赌法选择迁出的位和栖息地Hj， 在Hi要迁入的位用Hj的相应位进行替换。

(3)突变操作

通过突变来提升解决方案(栖息地)的多样性，以求得比目前更好的解决方案。该过程与迁移操作相似，对于每一个解决方案Hi中的节点si， 通过生成一个随机数r∈(0,1)， 如果r的值小于最大突变概率，则执行突变。然后在栖息地中选择随机位置并改变其值，即如果所选位置的值为0，则将其替换为1，如果为1，则将其替换为0。

2.3.2 基于CABBO的分簇算法流程图

在CABBO求解分簇问题的过程中，栖息地表示可行解，每个栖息地通过最大化其的适应度值，以得到合理的分簇方案。其中，适应度值为目标函数的倒数，目标函数值由式(12)进行计算，CABBO算法的具体流程如图5所示。

图5 CABBO算法流程

3 实验仿真

3.1 参数设置

我们利用Matlab2016进行实验仿真，仿真计算机配置为2.9 GHz Intel Core i5，8 GB内存，64位Windows 10。仿真区域设定为100×100平方米的正方形区域，基站位于区域中心，传感器节点被随机、均匀地分布在目标区域内。我们考虑了网络的异构性，根据初始能量分为两种类型节点，分别为高级节点和普通节点。其中，普通节点的初始能量为0.5 J，高级节点的初始能量为1 J，具体的实验参数见表1。

表1 仿真参数设置

3.2 仿真结果分析

本文将CABBO算法与SEP算法[8]、BEECP[11]以及EEWC[11]进行比较，并从5个方面进行分析，以验证所提出算法的有效性。

不同算法的死亡节点变化情况如图6所示，可以看到CABBO算法推迟了第一个节点死亡时间。表2列举了不同算法下死亡节点对应的轮数信息。CABBO算法在第1398轮出现第一个死亡节点，当网络出现10%的死亡节点，所提出算法发生在第1591轮，SEP、BEECP和EEWC分别发生在第1162轮、第1193轮和1261轮。CABBO在第2475轮网络所提出算法有90%的节点死亡，相对于其它算法，其有效地推迟了节点死亡时间。

图6 每轮死亡节点个数

表2 对比死亡节点

从图7我们可以更加直观地观察到不同算法下节点死亡时间的变化幅度。可以看到CABBO算法在推迟50%～70%节点死亡时间上效果显著。同时，表3展示了相对于其它3个算法，CABBO算法在网络稳定周期和生命周期方面的性能提升率。与SEP、BEECP和EEWC相比，CABBO在稳定周期方面分别提升了50.48%、25.38%和21.24%，在90%节点死亡时间上分别推迟了69.86%、26.08%和12.14%。

图7 死亡时间统计

表3 对比稳定周期和网络生命周期

该结果也表明所提出算法在提升网络稳定周期和生命周期方面表现优异。这是因为CABBO算法考虑了节点剩余能量、邻居节点个数以及到基站距离对成簇的影响，优化簇头选择，降低了能量较小的节点成为簇头的可能性，增强了网络的连通性。同时，通过考虑了利用适应值函数评估分簇方案，使得簇头在网络中的分布更加合理，从而减缓了节点死亡时间。

网络剩余能量是分析协议好坏的重要性能指标之一[15]。从图8中我们可以看到，所提出算法的曲线相对平滑，这意味着节点之间的负载更加均衡。同时，通过表4我们可以更加清晰地观察到，4个算法的网络剩余能量随时间变化情况。在第一轮后，SEP、BEECP、EEWC、CABBO算法中网络总剩余能量均为54.96 J，200轮后，4个算法网络剩余总能量为46.59 J，47.74 J，48.27 J和49.78 J。可以看到CABBO算法的总剩余能量高于其它算法。这是因为LEACH和SEP是通过阈值公式随机选择簇头节点，簇结构不合理使节点能量消耗过大。BEECP算法在选择簇头时考虑了簇内紧凑度和簇分离程度，有效降低了节点传输数据的能量消耗，从而减少了网络能量消耗。EEWC算法不仅考虑了这两个因素，同时考虑了簇头数目对分簇的影响，进一步减少了节点能量消耗。而本文提出的CABBO算法在选择簇头时考虑了节点剩余能量、节点邻居个数以及到基站的距离。同时，通过加入能量均衡因子，使节点负载更加均衡，提高了网络能量利用率。

图8 网络剩余能量

图9展示了4个算法下的网络吞吐量，即节点发送到基站的总包数。因为CABBO算法有效延长了网络的生命周

表4 对比剩余能量

图9 吞吐量对比

期，通过考虑节点能量、邻居节点个数因素，增强了网络的连通性和汇聚能力，从而极大提高了网络吞吐量，这意味着网络具有更好的性能。

图10展示了不同算法的簇头变化情况，其中，基于BBO的BEECP算法的簇头数目变化幅度较大，而所提出算法可以保证每轮簇头数目在一个小范围内浮动，呈现出一种较为平稳的状态。有效解决了基于BBO的分簇算法中簇头数目变化较大的问题，稳定的簇头数目使得区域内簇的规模相对均匀稳定，提高了网络的稳定性。

图10 每轮簇头个数

4 结束语

本文提出了一个基于BBO优化的MSN分簇算法，首先，从优化初始化栖息地质量的角度进行考虑，选择具有较好特性的节点生成分簇初始解。同时，采用余弦迁移模型改进传统BBO算法，有效提高算法的探索能力和收敛速度。再者，通过定义新的适应度函数，CABBO算法形成的簇结构可以使网络负载更加均衡。与SEP、BEECP和EEWC算法相比，CABBO算法在一定程度上提高了网络生命周期和吞吐量。同时，CABBO算法提高了BBO在分簇算法中的适应性，有效解决了簇头数目变化幅度较大的问题，增强了网络的稳定性。