基于模因算法的电磁干扰下无线热点优化部署算法.pdf

第 21 卷 第 7 期 电 力 信 息 与 通 信 技 术 Vol.21 No.7 2023 年 7 月 Electric Power Information and Communication Technology Jul.2023 中图分类号：TN925 文献标志码：A 文章编号：2095-641X(2023)07-082-06 DOI：10.16543/j.2095-641x.electric.power.ict.2023.07.11 著录格式：张浩，张鹍，张勇，等基于模因算法的电磁干扰下无线热点优化部署算法J电力信息与通信技术，2023，21(7)：82-87 基于模因算法的电磁干扰下无线热点 优化部署算法 张浩1鹍，张2，张勇2，毕晓伟1，付振霄1，李菁竹1（1国网山东省电力公司经济技术研究院，山东省 济南市 250021；2国网山东省电力公司，山东省 济南市 250001）Optimal Deployment Algorithm of Wireless Hot Spots under Electromagnetic Interference Based on Memetic Algorithms ZHANG Hao1,ZHANG Kun2,ZHANG Yong2,BI Xiaowei1,FU Zhenxiao1,LI Jingzhu1(1.Economic&Technology Research Institute,State Grid Shandong Electric Power Company,Jinan 250021,Shandong Province,China;2.State Grid Shandong Electric Power Company,Jinan 250001,Shandong Province,China)摘要：随着智能电网的发展，越来越多的智能电网终端部署到电力传输网络中。考虑到智能终端的部署数量及部署的分散性，采用无线传输方式的智能终端通信方式成为一种新的选择和解决方案。但是无线通信容易受到电磁干扰，影响无线传输稳定性。为提升无线传输稳定性，在变电站等强电磁干扰下，需要加大无线热点的部署密度。在终端用户处没有强电磁干扰，为降低部署成本，可降低无线热点的部署密度。为应对电磁干扰环境，文章基于模因算法，提出了一种自适应无线热点优化部署算法。算法针对不同的电磁干扰环境，可自主调整无线热点的部署密度。该算法的提出可降低无线热点部署成本，同时确保电磁干扰下的无线通信稳定性，提升无线通信质量，并通过仿真结果进行了验证。关键词：无线热点；通信覆盖范围；智能电网；电磁干扰；模因算法 ABSTRACT:With the development of smart grid,more and more smart grid terminals are deployed in the power transmission network.Considering the number and dispersion of intelligent terminal deployment,the wireless transmission method of intelligent terminal communication has become a new choice and solution.However,wireless communication is vulnerable to electromagnetic interference,which affects the stability of wireless transmission.In order to improve the stability of wireless transmission,it is necessary to increase the deployment density of wireless hot spots under strong electromagnetic interference such as substation.There is no strong electromagnetic interference at the end user.In order to reduce the deployment cost,the deployment density of wireless hotspots can be reduced.To deal with various electromagnetic interference environments,this paper proposes an adaptive wireless hotspot optimization deployment algorithm based on memetic algorithms.The algorithm can automatically adjust the deployment density of the wireless hotspots according to different electromagnetic interference environments.The proposed algorithm can reduce the deployment cost of wireless hotspots,ensure the stability of wireless communication under electromagnetic interference,and improve the quality of wireless communication.The simulation results show that the scheme can cover the required communication range with fewer wireless hotspots.KEY WORDS:wireless hotspot;communication coverage;smart grid;electromagnetic interference;memetic algorithms 0 引言 在智能电网的设计中，随着智能终端数量的增多及物理位置的分散，无线通信成为较好的通信选择，其中无线热点的优化部署成为智能电网无线通信的关键问题之一。为了提高无线通信网络的 基金项目：国网山东省电力公司科技项目“可信 Wi-Fi 技术在电力系统应用研究”(5206002000QP)。可靠性，抵抗电网设备带来的电磁干扰问题，研究人员对一些问题进行了研究，如功率管理1、路由协议2、覆盖控制3-4。覆盖控制的主要研究是确保在电磁干扰环境下实现无线网络的正常通信，同时尽可能减少冗余热点，优化无线热点部署的位置和密度。研究电磁干扰下无线热点部署问题，对于减少智能电网冗余终端数量、稳定无线网络通信质量至关重要，可为实现智能电网的稳定及应用提供第 21 卷 第 7 期 电 力 信 息 与 通 信 技 术 83 支撑。为简化研究问题，本文将智能电网看作一个无线传感网络。在考虑无线传感网络的覆盖控制时，多关注 k 覆盖问题3-4。k 覆盖意味着每个点都在 k个或更多传感热点的感测范围内，k 的值由无线传感器网络所承载的应用功能决定5。为了实现以最少的无线热点保持最大的覆盖区域，由热点调度算法6-8选择的冗余无线热点应该进入非活动模式(睡眠模式)以保留电池功率。如果一个活动热点耗尽其能量，则需要立即唤醒一个或多个非活动热点来替换即将死亡的热点，这些热点调度算法保证尽可能长时间的 100%感知覆盖。选择最小数量的无线热点覆盖所有的兴趣点(point of interest，POI)的问题属于 NP 完全问题(non-deterministic polynomial-complet problem，NPC)9，也称集合覆盖问题(set covering problem，SCP)10-11。模因算法(memetic algorithms，MAs)是基于群体的启发式搜索方法，用于搜索问题的最优解12。相较于遗传算法，MAs 算法借鉴了本地搜索的思想，并将该思想和遗传算法进行融合。基于文献13提出的模因概念，多智能体可采用一个或多个特定问题的启发式搜索改进遗传算子生成的解，如交叉和变异。本文基于 MAs 算法，研究在电磁干扰环境下，无线传感网络中的无线热点部署问题。为降低部署成本，考虑一个无线热点网络的1-覆盖问题。本文的主要贡献包括：1）提出了一种电磁干扰下的无线传感网耗能模型，该模型考虑了电磁干扰对于无线热点的耗能影响；2）结合耗能模型，提出了一种自适应无线热点优化部署算法。算法可降低无线热点的部署密度，有效抵抗电磁干扰。仿真结果表明，该方法可有效延长无线传感网络的运行周期，提高无线通信稳定性，确保电磁干扰下的无线通信质量。1 数学模型 在本文中，假设所有的无线热点在部署后都是固定的，具有相同的通信容量、感测范围和数据处理能力。每个热点的位置是先验已知的，热点的覆盖区域被假定为具有半径 r 的圆形区域。智能电网终端是无线通信数据产生的地方，如图 1 所示，每个智能电网终端可被多个无线热点覆盖。如果智能电网终端位于某个无线热点的感测范围 r 内，则可实现双方之间的无线通信。图 1 无线覆盖示意 Fig.1 Wireless coverage diagram 1.1 无线覆盖模型 给定的目标区域 Rtarget是xyLLm2的二维平面。Rtarget中 的 一 组 无 线 热 点 被 定 义 为12,.,iNc c ccC，其中,iiiicxy r，1,iN，N 是部署的无线热点的总数。无线热点的坐标和传感半径分别为,iix y和 r。分布在区域 R 上的一组POI 定义为12,.,Mp ppP，其中jp位于,iix y，1,jM，M 是 POI 的个数。此外引入了一个二进制变量,i jR来表示ic是否能够覆盖jp，,i jR定义为：222,1,if()()0,otherwiseijijsi jxxyyrR(1)如果jp和ic之间的距离小于r，则jp被ic覆盖，可检测到在兴趣点产生的事件信号。jp可能同时被 v 个传感器热点覆盖。对于特定的jp，如果它 被v个 传 感 器 热 点(vN)覆 盖，则jp的1,2,.,jjv jRRR的并集可以使用布尔代数的基本运算进行计算：1,2,1,2,.1.jjv jjjv jRRRRRR (2)式中：,i jR是,i jR的布尔逆；“”表示布尔交。1.2 耗能模型 在无线传感网中，能耗主要分为两部分，即无线热点间通信耗能、热点自身的计算耗能。由于热点间的耗能远大于自身计算耗能，本文考虑无线热点间的通信耗能，忽略其他操作耗能。无线热点间的通信耗能包括发射热点的发射耗能和通信接收热点的接收耗能，其中发射耗能包括传输电路耗能和信号放大器耗能两部分。电磁干扰因素对于无线通信的质量影响较大，这和无线通信的耗能有相近的影响效果。本文将电磁干扰因素量化为对于智能终端无线通信的能耗，84 张浩等：基于模因算法的电磁干扰下无线热点优化部署算法 Vol.21 No.7 量化过程通过电磁干扰因子实现。Yoon 等人给出了在无电磁干扰下的耗能模型14，基于该模型本文引入了电磁干扰因子，将耗能模型扩展至电磁干扰环境下，对环境的建模有更好的匹配度。为简化模型，将电磁干扰的影响定义为对传输耗能的影响，且体现在信号放大器耗能部分。针对无线传感器网络的电磁干扰，按照其干扰源的不同可以分为同构电磁干扰和异构电磁干扰。同构电磁干扰主要是因为在同一无线传感器网络中，热点部署过于密集，无线通信中 MAC 协议所采取的CSMA/CA带来的传输时延及多径传播中产生的路由耦合。本文提出的热点部署方案在保证覆盖率的前提下，存活热点尽可能地分布在各自覆盖区内，有效降低了同构电磁干扰的影响，所以本文所考虑的电磁干扰是异构电磁干扰。定义 1 信号放大器耗能 EA。假设信号放大器耗能为 EA，则有Aamp=EEk d，其中2,)；d 为信号传输距离；Eamp表示信号放大器放大 1 bit数据的耗散能量。电磁干扰因子由电磁干扰能量决定，电磁干扰强的区域，值变大，相同的无线传输距离会导致更多的无线耗能，从而影响无线热点的覆盖范围。在无干扰情况下，=2，在全频段干扰阻塞情况下，可将设定为无穷大，以表征无线通信数据无法传输，通信失败。为简化描述，本文将电磁干扰能量简化为干扰源的数量。取值越大，干扰能力越强，则 越大，存在正向影响。结合仿真结果，当1,10，=3是一个合理的取值。电磁干扰下的无线传感网耗能模型如图 2 所示，图中：t-elecE表示发射电路发送 1 bit 数据的耗散能量；r-elecE表示接收电路接收 1 bit 数据的耗散能量。图 2 电磁干扰下的无线传感网耗能模型 Fig.2 Energy consumption model of wireless sensor network under electromagnetic interference 1.3 集合覆盖问题 SCP 是 NP-Complete 困难问题之一，在文献9中首次定义。本文将此定义应用于热点调度优化，用以表征无线热点能效管理覆盖范围的问题。SCP是寻找一组代价最小的热点，使每个 POI 至少被一个热点覆盖。本文考虑的 SCP 可用数学方法表述：优化模型：min1,iiigxiN (3)受制于：,1i jiiRx,1,jM且0,1ix,1,iN(4)式中：gi是激活每个热点的成本；xi是关键的决策变量，需要预先设定(例如，1 个用于激活，0 个用于失活)。式(3)中的目标函数最小化了需要激活的热点总数。文中假设激活每个热点的成本是相同的(即 gi=1)。式(4)中描述的约束规定每个 pj必须被至少一个热点覆盖。当网络被激活时，使用式(3)和(4)中描述的优化模型是关键，该模型可提高网络的能量效率。2 基于 MAs 的无线热点部署方案 基于 MAs 算法，本文提出了一种可抵抗电磁干扰的无线热点部署方案。方案的主要思想是遗传进化。进化过程在遗传算法操作中进行，包括选择、交叉和变异。每个个体代表一个具有相应适应值的解，该适应值从适应度函数导出；本地局部搜索在完成遗传算法操作后，利用局部搜索进一步提高解的优度，这样就产生了一个新的优越个体群体，新群体中的个体更接近全局最优解。如果找到最优解，进化过程将被终止，同时输出最优的热点部署位置。具体算法流程如图 3 所示。图 3 算法流程 Fig.3 The process of algorithm 第 21 卷 第 7 期 电 力 信 息 与 通 信 技 术 85 2.1 遗传进化中的表征 对于 MAs 算法，设计一个专注于给定问题的基因表达是关键步骤，良好的遗传表示可提高种族进化性能。为实现无线热点的覆盖优化，需要将热点的调度转换为遗传表示。热点的最优调度用于在特定时间激活无线传感器网络中的睡眠热点，在不影响热点覆盖的前提下可有效在延长网络寿命。基因的数值设定采用 0 表示传感器热点未激活，1 表示传感器热点已激活。覆盖优化的遗传基因表述如图 4 所示。图中，表示个体(染色体)的数量；等位基因,i j表示染色体 i 中传感器热点jc 的状态，每条染色体的长度为N。由于不同的种群大小导致不同的种群多样性，使用适当的种群大小至关重要。Eiben 等人15指出，可通过创新的方式控制最佳种群规模16，遗传算法的种群规模作为变量之一。图 4 遗传基因表述 Fig.4 Genetic gene expression 2.2 适应性 适应度函数是一种衡量特定染色体优劣的指标。本文所提方案的目标是使用更少的传感器热点实现最佳的覆盖，将主动传感器热点的调度作为该算法的适应度函数。对于每个热点，提出一个覆盖向量表示兴趣点的覆盖。根据无线覆盖模型，一个特定热点 ci(icC)的覆盖向量可以定义为,1,2,.,iiii MRRRG。类似的，传感器热点jc 覆盖向量由,1,2,.,jjjj MRRRG表示，其中ij。本文使用二元模型表示给定的兴趣点是否被传感器热点覆盖。将布尔运算应用于向量间的计算，通过执行 Gi和 Gj之间的布尔并集计算ic和jc 的合成覆盖向量：,1,1,2,2,(),.,ijijijiji Mj MccRRRRRRGG (5)式中 表示合成覆盖向量，用于确定每个 POI 是否被ic、jc 覆盖。2.3 基因操作 遗传算法操作包括选择、交叉和变异。本文采用锦标赛选择策略寻求每一代的最佳适应度。锦标赛选择在随机选择的个人中运行锦标赛，选择获胜者进行交叉。在锦标赛选择过程中，从群体中随机选择10 条染色体，选择精英染色体作为父染色体 1。选择第二好的染色体作为亲本 2 号染色体。2 个选定的父染色体将通过杂交繁殖后代的新染色体。为保持种群的多样性，确定一个合适的交叉率是很重要的。交叉率 Rc指定通过交叉从 2 个选择的染色体产生 2 个新染色体的概率。对于交叉任务，本文使用单点交叉。变异是一种遗传算子，帮助整个遗传算法防止种群陷入局部最优解，它改变任何可能的等位基因的一个或多个值，新的个体可被添加到原始基因库中。遗传算法操作的变异通常发生在交叉之后。突变率 Rm规定改变等位基因的原始值的概率。Rm被设置为一个低值，可防止搜索过程变成一个暴力的过程。通过交叉和变异的迭代操作，最终的后代平均具有较高的适应度。在进化过程中，可通过将参数附加到个体优化交叉率和突变率。为了简化研究，将它们都设置为固定值。有关遗传算法的详细描述，请参考文献17。2.4 本地搜索及遗传终止 本文采用文献18所提出的局部搜索策略，与传统 GAs 不同，该算法通过执行局部搜索过程可获得较快的收敛速度。在遗传过程中，当进化过程的最优解对于下一代不变时，进化过程终止。3 仿真分析 算法验证实验基于 MATLAB 平台进行。假设无线传输网的物理覆盖范围为一个大小 100 m100 m 的区域，其中均匀分布 400 个智能电网终端，如图 5 和图 6 所示。其中每一个终端均需要被无线热点覆盖，物理覆盖范围：x 轴 0100 m，y 轴 0100 m，超出范围表示边沿无线热点的传感范围。无线传感网络中使用的参数见表 1 所列。图 5 模拟网络中无线热点的初始部署(均匀方案，=3)Fig.5 Initial deployment of wireless hotspots in analog networks(=3)86 张浩等：基于模因算法的电磁干扰下无线热点优化部署算法 Vol.21 No.7 注：蓝色圈代表感知范围。图 6 应用优化部署算法后的无线热点部署 Fig.6 Wireless hotspot deployment after application of optimized deployment algorithm 表 1 无线传感网络参数 Table 1 Parameters used in sample network 参数 取值 r 17.65 m 1 20 Rc 0.5 Rm 0.07 Et-elec 50 nJ/bit Er-elec 50 nJ/bit Eamp 100 pJ/bit/m2 3 110 3.1 热点优化 对于统一部署的模拟场景，为节省耗费的能力，不再部署冗余热点。图 5 显示了无线热点和相应覆盖范围的初始部署方案，各无线热点为均匀部署，用以覆盖全部的区域。图 6 显示了在应用最优调度算法后，可用无线热点的覆盖范围。在这种模拟情况下，只需要激活 3.16%的热点就可以覆盖所有终端。3.2 无线通信质量 电磁干扰能降低无线传感器网络的稳定性，进一步降低无线通信质量，这主要体现在对数据包的传输时延、数据包接收率的影响上。本文选择传输时延和接收率作为主要的网络质量测试指标，研究均匀部署方案和本文所用优化部署方案对于抗电磁干扰的能力。无线传感器网络环境采用表 1 所示参数。仿真软件采用 NS2，干扰源采用软件内置模块，无线通信实验方案参数见表 2 所列，无线通信芯片采用 CC2420。表 2 无线通信实验方案参数 Table 2 Parameters of wireless communication experiment scheme 参数 参数值 发射功率/dBm 10 协议 802.15.4 网络带宽/MHz 4 工作频带/GHz 2.5 数据速率/kbps 250 码片速率 2 M Chip/s 3.2.1 传输时延 在线热点采用每间隔 1 s 的方式向所覆盖终端发送数据包，并记录每个终端在接收到相应数量的数据包所需要的时间，取均值作为无线传感网络的平均传输时延。设定干扰源数量为 1，传输时延选取从接收到第五个数据包开始，对比如图 7 所示。通过实验可以得到如下结论，在电磁干扰情况下，均匀部署方案因为热点密集度高、传输距离短，在数据包数量较少时，平均时延更少。但是随着数据包数量的增多，MAC 协议的 CSMA/CA 引起的冲突效应加剧。优化方案因为所需热点少、部署密集度低，可以有效缓解 CSMA/CA 的冲突效应，降低路由耦合影响。随着数据包数量的增多，相比均匀部署方案，本文所提出的优化方案对于传输时延的提升更为明显。平均时延/s 图 7 传输时延对比 Fig.7 Transmission delay comparison 3.2.2 丢包率 在线热点采用每间隔 1 s 的方式向所覆盖终端发送数据包，每个在线热点在 100 s 内统计丢包率，并取均值作为无线传感网络的平均丢包率，丢包率对比如图 8 所示。在有电磁干扰的情况下，伴随干扰源数量的增多，均匀部署方案的丢包率下降情况更为明显，从 1 个干扰源下的 9%，增加至 10 个干扰源情况下的 87%。本文所提优化部署方案，通过增加冗余热点，在 1 个干扰源情况下的丢包率仅为6%，在 10 个干扰源情况下的丢包率仅为 43%。这第 21 卷 第 7 期 电 力 信 息 与 通 信 技 术 87 表明本文所提优化方案能够有效降低丢包率，提升无线通信质量。图 8 丢包率对比 Fig.8 Packet loss rate comparison 3.2.3 网络生命周期分析 针对相同的物理覆盖范围，在初始阶段部署相同的无线热点数量。对于均匀部署方案，每个无线热点均应处于存活状态。优化方案在模拟情况下，只需要 3.16%的热点就可实现 1-覆盖，其余 96.84%的热点均可设定为休眠状态。一旦存活状态的无线热点能量耗尽，可激活休眠状态的无线热点，延长网络的生命周期。4 结语 本文提出了一种基于 MAs 算法的无线热点部署算法，该算法可用于电磁干扰下无线热点的优化部署。实验结果表明，在电磁干扰情况下，算法可有效减少活跃无线热点的数量，相同的覆盖区域需要的存活无线热点数量减少，有效提升了无线传感网络的通信质量，延长网络生命周期。考虑到电磁干扰的来源多样性，在后续的工作中可通过引入不同的干扰模型，使算法具有更好的应用价值。参考文献 1 田新越，李翔宇无线传感器网络节点任务调度与功耗管理算法研究J传感器与微系统，2016，35(2)：9-11 TIAN Xinyue，LI XiangyuResearch on task scheduling and power consumption management algorithm for wireless sensor networks nodeJTransducer and Microsystem Technologies，2016，35(2)：9-11(in Chinese)2 周颖无线传感网中高能效数据汇聚关键算法研究D南京：南京邮电大学，2020 3 LI Qiangyi，LIU NingzhongCoverage optimization algorithm based on control nodes position in wireless sensor networksJ International Journal of Communication Systems，2022，35(5)：1-20 4 ZHANG Ye Coverage optimization and simulation of wireless sensor networks based on particle swarm optimizationJInternational journal of wireless information networks，2020，27(2)：307-316 5 THANGAVEL G，RAJARAJESWARI P A novel genetic algorithm with db4 lifting for optimal sensor node placementsJInternational arab journal of information technology，2022，19(5)：802-811 6 PRIYADARSHI R，GUPTA BArea coverage optimization in three-dimensional wireless sensor networkJWireless Personal Communications，2021，117(2)：843-865 7 ROY S，MAZUMDAR N，PAMULA RAn energy and coverage sensitive approach to hierarchical data collection for mobile sink based wireless sensor networksJJournal of Ambient Intelligence and Humanized Computing，2021，12(1)：1267-1291 8 PALLAVI R，SRINIVAS B C，PRAKASH G CAn efficient approach to preserve the network connectivity for prolonged lifespan of wireless sensor networks by cautiously removing the crossing edges using COLSJInternational Journal of Wireless and Mobile Computing，2020，18(3)：215-220 9 DASKIN M SNetwork and discrete location:models，algorithms，and applicationsMNew York:Wiley，1995：78-81 10 SMITH L A，HICKS V New computational approaches for the power dominating set problem:Set covering and the neighborhoods of zero forcing fortsJNetworks，2022，79(2)：202-219 11 MA Chaofan，LIANG Wei，ZHENG MengDelay constrained relay node placement in two-tiered wireless sensor networks:A set-covering-based algorithmJJournal of Network and Computer Applications，2017，93(1)：76-90 12 AJAM L，NODEHLI A，MOHAMADI H A new approach to solving target coverage problem in wireless sensor networks using an effective hybrid genetic algorithm and tabu searchJJournal of Intelligent and Fuzzy Systems，2022，42(6)：6245-6255 13 DAWKINS RThe selfish geneMCambridge:Oxford University Press，1976：203-215 14 YOON Y，KIM Y H Maximizing the coverage of sensor deployments using a memetic algorithm and fast coverage estimationJIEEE Transactions on Cybernetics，2022，52(7)：6531-6542 15 EIBEN A E，HINTERDING R，MICHALEWICZ ZParameter control in evolutionary algorithmsJ IEEE Transactions on Evolutionary Computation，1999，3(2)：124-141 16 MICHALEWICZ ZGenetic algorithms+data structures=evolution programsM3rd edBerlin：Springer，1996：201-211 17 GOLDBERG D EGenetic algorithms in search，optimization，and machine learningMReading：Addison-Wesley Publish，1989：101-107 18 JIANG J A，CHEN C P，CHUANG C L，et alCoCMA：energy-efficient coverage control in cluster-based wireless sensor networks using a memetic algorithmJSensors，2009，9(6)：4918-4940 张浩 收稿日期：2022-06-10。作者简介：张浩(1985)，男，高级工程师，从事通信网规划及通信新技术研究工作；张鹍(1987)，男，高级工程师，从事通信管理工作；张勇(1971)，男，高级工程师，通信作者，从事通信及网络安全管理工作，；毕晓伟(1984)，女，高级工程师，从事通信网规划工作；付振霄(1991)，男，工程师，从事通信规划工作；李菁竹(1987)，女，高级工程师，从事智能化规划工作。（责任编辑 张京娜）