WSNs 中基于鸡群优化算法选择簇头的簇路由*

张 洋，杨守良

（1.重庆幼儿师范高等专科学校儿童智能科学与技术系，重庆 404047；2.重庆文理学院电子电气工程学院，重庆 402160）

0 引言

物联网的发展促进了无线传感网络（Wireless Sensor Networks，WSNs）［1-2］在各领域中的应用。WSNs 由微型、低功耗的传感节点组成，这些传感节点具有数据感知、数据处理和通信能力。传感节点先感知环境数据，再通过多跳通信将数据传输至基站。

然而，节点资源受限，包括数据处理能力、存储空间、通信范围以及能量容量，阻碍了基于WSNs 应用的拓展。尤其节点能量受限，极大地限制了WSNs应用。通常，节点是由电池供电，电池的使用时间较短，当节点电池耗尽，也不便更换电池。因此，一旦电池耗尽，节点就相当于失效，无法继续工作。

感测数据、传输数据等操作均消耗能量，其中传输数据消耗了节点的大部分能量。为此，控制节点传输的数据量，可延缓节点的能耗速度。而簇技术是减少节点传输数据量的有效手段。

因此，基于簇的WSNs 被广泛研究。簇技术就是将网络内节点划分多个群。每个群称为一个簇，每个簇又产生一个簇头。簇头负责收集簇内节点所感测的数据，图1 给出典型的簇结构。

图1 WSNs 的簇结构

作为簇技术的代表，低功耗自适应簇路由（Low Energy Adaptive Clustering Hierarchy，LEACH）技术得到广泛应用［3］。LEACH 采用随机方式选择簇头，这不利于簇头的均匀分布，使节点间的能耗不均衡。

簇头的选择策略是簇技术的关键，其也成为簇技术领域的研究热点。研究人员试图利用智能算法提高选择簇头的效率，平衡了网络能耗。例如，文献［4］将粒子群优化算法（Particle Swarm Optimization，PSO）应用于LEACH，通过PSO 策略产生新的簇，进而平衡网络能耗。类似地，文献［5］将猴子搜索算法（Monkey Search，MS）应用于LEACH，形成LEACHMS 路由。

此外，文献［6］提出基于蛙跳和萤火虫算法的簇路由（Shuffled Frog-Leaping and Firefly Algorithm，SFFA）。SFFA 利用节点到基站的距离、节点剩余能量以及簇间距离等信息择优选择簇头。

鸡群优化算法（Chicken Swarm Optimization，CSO）也广泛应用于WSNs。例如，文献［7］利用CSO算法构建簇头与基站间最优的数据传输路径。文献［8］也利用CSO 算法解决WSNs 的定位问题。

为此，受上述方案的启发，将CSO 算法应用于WSNs，并提出基于鸡群优化算法选择簇头的簇路由（Chicken Swarm Optimization-based Cluster Head Selecting Clustering Routing，CSO-CHS）。CSO-CHS 路由通过CSO 算法选择最优的节点作为簇头，减少能耗，延长网络寿命。仿真结果表明，提出的CSO-CHS 路由有效地缓解了节点能耗，延长了网络寿命。

1 系统模型

1.1 网络模型

1.2 能量模型

传输数据消耗了节点大部分能量。为此，本文只考虑传输数据和接收数据的能耗，引用文献［9］的能耗模型，如图2 所示。

图2 能耗模型

1.3 CSO 算法概述

CSO 算法中存在多个鸡群。每个鸡群中个体有3 类角色：起支配作用的公鸡（称为群主）、母鸡（群成员）和小鸡（群成员）。公鸡是群的决策者，地位最高，而母鸡和小鸡属弱势群体。母鸡跟着公鸡觅食，小鸡跟着其母亲觅食［10］。

CSO 算法是利用鸡适度值将鸡个体进行等级制度划分。具有高适度值的鸡成为公鸡，适度值较低的鸡为小鸡，其余的为母鸡。

在每一轮内，鸡群个体角色不变。每次迭代更新一次，即重新计算各只鸡个体的适度值，进而更新鸡群个体角色，图3 给出CSO 算法的执行过程，其中，t 表示迭代次数、tmax为最大的迭代次数。

图3 CSO 算法的执行流程

每只鸡的位置对应优化问题的解。而不同角色的鸡个体采用不同的位置更新策略。用矩阵X 表示鸡的位置。

2 CSO-CHS 路由

CSO-CHS 路由是从网络能耗的角度，选择簇头，并结合CSO 算法产生最优的簇头，平衡网络能耗，延长网络寿命。构建适度函数是执行CSO 算法的关键。为此，CSO-CHS 路由先依据网络能耗，构建适度函数，再根据适度函数，择优选择鸡群中各只鸡个体的角色，进而形成最优的簇。

2.1 基于能耗感知的目标函数

CSO-CHS 路由旨在通过选择最优的簇头，最小化传输数据的能耗，实现延长网络寿命的目的。换而言之，CSO-CHS 路由的目标函数就是最大化网络寿命。

引用文献［12］的定义，将网络内第1 个失效节点出现的时间作为网络寿命，即将网络内节点最短的网络寿命作为整个网络寿命，如式（6）所示：

这两部分均与簇头的选择有关。依式（7）可知，eCH与所选择的簇头直接相关。不同节点作为簇头，簇头离簇头距离不同（dtoBS不同）以及DCH值也将不同。此外，由式（8）可知，不同节点作为簇头，簇成员离簇头的距离也发生变化，则簇成员向簇头传输数据所消耗的能量也会发生变化。

结合式（9），可计算在一轮内k 个簇所消耗的总能量Etotal：

式（11）是一个优化方程。因此，利用全局优化的鸡群算法迭代寻优特性，求解最优的簇头［10］。

2.2 基于CSO 算法的簇头选择

CSO-CHS 路由旨在延长网络寿命，最小化网络能耗。用二值变量表述个体。变量的下标表述个体ID 号；变量的值表述该个体是否为簇头，若值为1，表示簇头。反之，表示簇成员。

为此，先利用sigmoid 函数将每只鸡个体的值转换为二值变量，其转换过程如式（12）：

1）先初始化矩阵X。矩阵X 内元素随机赋予0或1 的值；

2）计算矩阵X 内每一行的个体适度值；

3）依据适度值，按下降序值对所有个体进行排序；

4）依据个体的适度值，将矩阵X 内的元素划分为3 个群（公鸡、母鸡和小鸡）；

5）再分别依式（3）～式（5）更新公鸡、母鸡和小鸡的位置；

6）利用式（12）将它们的值转化为二值变量。然后，寻找不可用的解。即检测矩阵X 中第1 行1的个数，如果1 的个数小于k，则随机选择将零更换成1；

7）再计算矩阵X 中每一行的适度值，将具有最大适度值记为xbest；

8）重复步骤2）至步骤7），直到达到最大的迭代次数tmax。

图4 最优解xbest示例

2.3 簇形成

一旦选择了最优的簇头，基站就将这些簇头信息向网络内传输。收到消息后，节点就检测消息内是否包含自己的ID 号，如果有，说明自己被选择为簇头。成为簇头后，簇头就广播通告消息。

非簇头节点可能收到来自多个簇头传输的消息。为了减少非簇节点的能耗，非簇节点将第一时间收到消息的发送节点（簇头）作为自己簇头。具体而言，非簇头节点一旦收到消息ADV_CH，非簇头节点就向发送节点回复加入消息JOIN_CH，并不再接收其他簇头发送的ADV_CH。

消息JOIN_CH 包含非簇头节点的ID 号以及能量信息。一旦收到JOIN_CH 消息，簇头就从中提取节点ID 号，并将其作为自己的簇成员。

3 性能分析

3.1 仿真环境

利用MATLABR2016b 建立仿真平台。在100 m×100 m 区域内均匀部署100 个节点，节点的初始能量为0.5 J。具体的仿真参数如下页表1 所示。

表1 仿真参数

此外，选择SFFA、LEACH-MS、LEACH-PSO 作为参照。原因在于：它们都是采用智能算法选择簇头。SFFA 路由采用蛙跳和萤火虫算法；LEACH-MS路由采用猴子搜索算法；LEACH-PSO 路由采用粒子群优化算法。本文提出的CSO-CHS 路由采用鸡群优化算法产生簇头，与SFFA、LEACH-MS、LEACH-PSO 存在可比性。

对比分析它们的CSO-CHS 路由性能。选择3个场景：1）基站位于区域中心，网络区域大小为1002m2；2）网络区域大小为1002m2，基站在右上角（Top Right Corner，TRC）、右边界线中间（Right Boundary in the Middle，RBM）、区域中心（Regional Center，RC）；3）基站位于区域中心，网络区域大小为1002m2、1502m2、2002m2。

3.2 场景1

在本次场景下，分析CSO-CHS 路由的网络寿命和能耗。图5 给出SFFA、LEACH-MS、LEACHPSO 和CSO-CHS 路由的网络寿命。从图5 可知，相比于SFFA、LEACH-MS、LEACH-PSO，提出的CSOCHS 路由的网络寿命分别提高了约19 豫、77 豫、80 豫。这说明CSO-CHS 路由有效地平衡了网络能耗，缓解了节点的能耗。

图5 网络寿命

图6 给出了平均每一轮所消耗的能量。从图6可知，相比于SFFA、LEACH-MS、LEACH-PSO 路由，CSO-CHS 路由有效地控制每一轮所消耗的能量。例如，LEACH-PSO 路由在执行到600 轮时，其能耗就高达0.474 J，而CSO-CHS 算法即使执行到900 轮时其能耗也低于0.4 J。

图6 平均每轮所消耗的能量

3.3 场景2

本次实验分析基站所在位置对网络寿命的影响，如图7 所示。从图可知，相比SFFA、LEACH-PSO和LEACH-MS，提出的CSO-CHS 路由有效地延缓了第1 个失效节点出现的时间。此外，基站的位置对各算法的网络寿命也存在一定的影响。相比于TRC 和RBM，基站位于RC 时的能耗最低。原因在于：当基站在区域中心，所有簇头向基站传输数据的总路径得到有效控制，这就减少了能耗。

图7 基站的不同位置对网络寿命的影响

3.4 场景3

本次场景分析网络尺寸对网络寿命的影响，网络尺寸分别为1002m2、1502m2、2002m2。

下页图8 描绘了各算法在不同网络尺寸下的网络寿命。从图8 可知，网络尺寸的增加，降低了网络寿命。原因在于：网络尺寸的增加，扩大了网络拓扑结构，拉长了节点间距离，这就使得节点需要更多能量传输数据。

图8 网络尺寸对网络寿命的影响

4 结论

簇是缓解WSNs 的网络能耗有效技术。然而，选择簇头并构建簇是簇技术的关键。据此，本文运用CSO 算法选择簇头。从能量角度构建CSO 算法中的目标函数，再利用CSO 求解，选择最优的节点作为簇头，进而平衡了网络能耗，延长了网络寿命。仿真结果表明，提出的CSO-CHS 路由缓解了节点能耗，延长了网络寿命。