基于群体智能和遗传算法的WSNs能耗优化关键技术研究

罗剑

摘要：节点能耗是决定无线传感器网络（WSNs）生存期的重要参数，设计良好的网络通信协议可以很大程度上减少和平衡能量消耗。网络协议设计簇头和簇间路由的计算过程是多项式时间无法解答的NP问题，该文讨论了5种自然元启发算法，既4种群体智能算法和遗传算法应用于WSNs能耗优化的关键技术，给出了不同网络能量结构模型的簇间单跳和多跳场景的设计建议，旨在为搭建大规模WSNs网络提供参考和借鉴。

关键词：群体智能;遗传算法;WSNs;能耗优化;多目标优化

中图分类号：TP393        文献标识码：A

文章编号：1009-3044（2021）07-0190-02

Abstract： Node energy consumption is an important parameter to determine the lifetime of wireless sensor networks （WSNs）. A good network communication protocol can greatly reduce and balance energy consumption. The calculation process of cluster head and inter cluster routing in network protocol design is a NP problem that cannot be solved by polynomial time. This paper discusses five kinds of natural element heuristic algorithms， namely four kinds of swarm intelligence algorithm and genetic algorithm， which are the key technologies of energy consumption optimization of WSNs， and gives the design suggestions of single hop and multi hop scenarios between clusters with different network energy structure model. The purpose is to provide reference for building large-scale WSNs network.

Key words： Swarm intelligence; genetic algorithm; WSNs; energy consumption optimization; multi-objective optimization

群體智能 （Swarm Intelligence，SI）和遗传算法（Genetic Algorithm，GA）[1]都属于人工智能领域研究的范畴。SI是一类分散自组织系统的集体智能行为的总称，即基于个体群成员的聚集表现出独立的智能，适合求解优化问题，有助于实现多项式时间复杂度无法解决的NP问题。GA是模拟自然界生物进化过程与机制求解最优问题的一类自组织、自适应人工智能技术。通过编码组成初始群体后，遗传操作的任务是按照群体中个体的环境适应度对个体施加一定的操作，从而实现优胜劣汰的进化过程。

无线传感器网络（Wireless Sensor Networks， WSNs），是由随机投放在监测区域内的大量低成本且拥有传感、计算、数据处理和通信能力的微型传感器节点构成的多跳自组织网络。通过感知、收集和融合环境范围中目标对象的测量数据，将预处理后的消息发送回基站（Base Station， BS），扩展了人们洞悉和操控外部世界的能力。

许多WSNs应用中数目巨大分布广泛的传感器节点基于电池供电且难于补充能量， 存在严重的能量限制。减少和平衡节点能耗， 最大化网络生存期成为WSNs的首要设计目标。节点能耗与WSNs网络协议密切相关，设计良好的路由算法可以在很大程度上降低和平衡节点能耗，延长网络生存期。利用SI和GA等自然元启发智能算法实现WSNs路由协议对各类在网传感节点数据通信和计算处理的综合协调调度，优化网络能耗意义重大。

1 5种自然元启发算法

PSO算法[2]是由Kennedy和Eberhart在研究鸟类和鱼类的群体行为基础上于1995年提出的一种SI算法，模仿鸟群飞行觅食行为，通过鸟之间的集体协作使群体达到最优。传统PSO算法具有局部搜索能力较差，搜索精度不高，搜索性能对参数依赖，后期易震荡等缺点。通过引入惯性权重、调整加速系数、混合拓扑结构、结合GA算子等改进措施，可以增加局部搜索能力，获得更快的收敛速度和更好的求解精度。ABC算法[3]由土耳其学者Karaboga在2005年提出，基本思想受蜂群通过个体分工和信息交流，相互协作完成采蜜任务的启发，强调群体之间互相协作。FA算法[4]是2008年由剑桥学者Yang提出，自然界里的萤火虫总是会向着比较亮的萤火虫移动，吸引力的大小跟萤火虫自身亮度成正比关系，与萤火虫之间的距离成反比关系。该算法易“陷入局部最优”的固有缺陷，通过增加惯性权重、加强个体协作和信息共享、引入混沌策略、步长levy化、融合其他智能算法等方式可以改进收敛速度，避免早熟。GA是由Holland于1969年提出的一类模拟进化算法，强调群体的进化能力。GA具有易于并行、自组织、自适应、搜索过程无连续可导要求等优点，但是在初始解群分布不均匀时易趋于未成熟收敛，陷入局部次优，其原因在于GA中基于适应度的多样性保持策略没能保持群体的多样性。AIA算法[5]将被求解问题视为抗原，抗体对应问题解，从随机生成的初始抗体出发，采用选择、克隆超变异、变异等算子进行操作，产生优越于父代的子代。克隆选择算法（Clonal selection principle， CLONALG）是该类算法的典型代表。5种算法的特点如表1所示，分别模拟了生物种群适应自然的不同行为过程，目标在于以最小的计算代价获取无限地接近全局最优解。因为算法自身的局限性，在有限次迭代的探索中获取全局最优是一个概率问题，通常得到的是局部次优解。

2 WSNs能耗优化关键技术

WSNs分簇协议综合考虑节点发送、接收数据的固定能耗和跟随传输距离远近改变的发送端无线功放能耗，将网络划分为若干本地簇。每个簇中的簇头节点消耗额外能量负责接收簇成员数据并发往基站。分簇结构使得网络整体扩展性良好，相比节点与基站直接通信和节点间最小传输能量路由性能更优，已经成为WSNs路由算法的研究重心。分簇协议的两个核心问题是：①形成簇;②建立簇头和基站之间的数据多跳转发路径。小面积监测环境基站通信范围覆盖整个监测区域，簇头和基站不需要经过中继节点转发数据，只需要考虑“形成簇”，随后簇头与基站单跳通信;中等面积和大面积监测环境基站通信范围无法覆盖整个监测区域，簇头和基站通过中继节点转发数据，需要综合考虑上述2个问题。

2.1 建立基于节点剩余能量指标的WSNs数学模型和能耗模型

一阶无线电模型是WSNs的通用能耗模型，在该模型框架内定义了数据发送、接收、融合、计算、感知的能耗公式用来模拟网络真实能耗。将WSNs划分为节点初始能量相等的同构WSNs和节点初始能量不同的异构WSNs。借助于对节点剩余能量和分轮次（round）建簇的深入分析，把各种WSNs数学模型均映射到多级异构模型。WSNs节点通常情况下随机散布在监测区域内且静止不动，节点位置、节点度、与其他节点距离、与基站距离等指标随机分布。尽管同构WSNs节点的初始能量相等，采用的网络协议也意图保持每个轮次各个节点能耗一致，但是因为上述指标的差异，每轮各节点实际耗能不可能相同，故同构WSNs在本质上是异构WSNs的特例。在建立网络协议的过程中，只要充分考虑节点剩余能量，即能将同构和异构WSNs统一于多级能量异构WSNs数学模型。

2.2 簇间单跳路由场景的最优簇头数量

在本场景中成员节点与所在簇头、簇头与基站之间均是直接通信，链路跳数为2，网络拓扑结构相对固定，如图1所示。影响簇间单跳路由场景中最优簇头数量计算公式的因素包括基站相对监测区域的位置、主副簇头机制、控制包、自由空间模型和多路径衰减模型等，综合运用微积分、极坐标、概率分布等数学工具和概念，可以计算16种因素组合的最优簇头数量和一个轮次网络总能耗的数学公式，如表2所示。

2.3 簇间单跳路由场景中基于自然元启发的分簇算法

簇间单跳路由场景只需要考虑分簇过程，自然元启发智能算法搜索空间的一个粒子对应优化问题的一个解，既映射为监测区域内的全体簇头集合，解的质量由多目标适应度函数评估。PSO、ABC和FA三种SI算法分别将解称为粒子、萤火虫和蜜蜂对应的蜜源位置（以下统称粒子），通过粒子间的互相协作、学习和吸引，寻找更优的解。上述过程必须建立连续量的粒子到离散量的簇头集合的映射关系，当粒子代表的解的位置在连续空间内移动时，需要按照一定的规则找到对应的离散化的簇头集合。GA算法的解称为染色体，通过染色体的选择、交叉和变异操作不断进化，从而搜索解空间寻找更优解。CLONALG算法模拟人体免疫机理，引入抗体的选择、复制、克隆增值超变异、变异等操作保留和搜索优质抗体，快速寻找更优解。在算法实现过程中，如何确定Pareto多目标适应度函数及其权重系數是一个难点，对于算法的性能影响较大，还需要考虑簇头和基站距离对成簇规模的影响。

2.4 簇间多跳路由场景中基于自然元启发的分簇和路由算法

簇间多跳路由场景成员节点和簇头直接通信，簇头视距离基站远近选择0～n个中继节点转发数据到基站。在簇建立过程中与簇间单跳路由场景有三点不同的处理策略：①因为簇头和基站间的跳数无法事先确定，所以不可能形式化地数学推导最优簇头数量。为了生成动态数量的优选簇头集合，在染色体或抗体初始化时将全部节点纳入簇头的候选集合进行计算极大地增加了运算负载，并不可取。可以依据一定的过滤规则，有条件地确定簇头候选节点集合，该集合元素数量远小于全体节点数量。②靠近基站的簇头相比远离基站的簇头更有可能成为中继节点，因而能量消耗更快，极大地影响网络生存期，这种现象称为热区问题。可以通过不相等分簇和多跳路由组织网络，簇范围随着节点到基站距离的减小而减小，从而平衡簇头的簇内和簇间总负载。③随着监测面积的扩大，增加了簇头通信范围无法覆盖全部非簇头节点的概率，必须考虑在网节点的连通度指标。簇间路由算法中每个簇头拥有自己的下跳候选簇头集合，PSO、ABC和FA算法必须映射连续变化的粒子到离散化的下跳簇头，GA或CLONALG算法容易建立离散化的染色体或抗体到离散化的下跳簇头的映射关系。选择Pareto多目标适应度函数及其权重系数仍然极大地影响算法性能。分簇算法常见参数有：簇内通信距离、簇头与基站通信距离、节点剩余能量、节点度、簇头生存期、每轮总能耗、网络连通度、簇头占比、簇头剩余能量标准差等，路由算法常见参数有：下跳节点剩余能量、下跳节点距离、下跳节点与基站距离、沿路径每跳距离平方和、下跳节点度、最大跳数等。

3 总结

本文分析了5种自然元启发算法的优缺点，将其应用到WSNs能耗优化设计。利用节点剩余能量，可以将不同结构的WSNs统一于多级能量异构模型，从而计算单跳路由场景的最优簇头数量和分簇结果。对于簇间多跳路由场景的分簇和路由，必须综合选择Pareto多目标适应度函数及其权重系数，才能平衡节点能量消耗，延长网络生存期。

参考文献：

[1] 葛继科，邱玉辉，吴春明，等.遗传算法研究综述[J].计算机应用研究，2008，25（10）：2911-2916.

[2] 黄少荣.粒子群优化算法综述[J].计算机工程与设计，2009，30（8）：1977-1980.

[3] 秦全德，程适，李丽，等.人工蜂群算法研究综述[J].智能系统学报，2014，9（2）：127-135.

[4] 臧睿，李辉辉.基于标准萤火虫算法的改进与仿真应用[J].计算机科学，2016，43（S2）：113-116，132.

[5] 李茂军，罗安，童调生.人工免疫算法及其应用研究[J].控制理论与应用，2004，21（2）：153-157.

【通联编辑：代影】