基于进化计算的工业无线传感器网络调度优化研究

沙特国王大学学报基于进化计算的工业无线传感器网络调度优化Gandeva Bayu Satryaa，Soo Young Shinb，a印度尼西亚Telkom大学应用科学学院b大韩民国Kumoh国立技术学院信息技术融合工程系阿提奇莱因福奥文章历史记录：收到2019年2019年12月10日修订2020年1月28日接受在线预订2020年保留字：进化规划遗传算法工业无线传感器网络（IWSN）物联网（IoT）ISA 100.11a超帧调度A B S T R A C T工业无线传感器领域由于物联网（IoT）而经历了范式的转变，物联网是一种蓬勃发展的技术，在短距离和固定无线传感方面一直处于领先地位工业无线传感器网络调度中的一个问题是如何最小化故障时间。提出了一种基于进化算法的车间调度优化方法，即粒子群优化算法（PSO）、正交学习PSO、遗传算法（GA）和改进遗传算法。此外，我们评估了当代的方法，截止日期单调调度，ISA 100.11a协议。使用该标准作为案例研究意味着所提出的72个模拟是面向对象的，在时隙和无线传感器节点的数量有许多变化仿真结果表明，使用遗传算法和改进的遗传算法可以提高性能的闲置，错过截止日期，内存消耗，和处理时间相比，其他元启发式算法。文中给出了©2020作者（S）。由爱思唯尔公司出版代表沙特国王大学这是一个开放的访问CC BY-NC-ND许可证下的文章（http://creativecommons.org/licenses/by-nc-nd/4.0/）。1. 介绍IoT是在工业无线系统中快速增长的创新范例（Xu等人，2014; Bi等人， 2014年）。例如，物联网在智能工厂场景中的实施使智能自动化生产系统能够通过无线传感器节点（WSNs）进行跟踪，输出可以被监控，并且随后的未来生产优化成为可能。工业无线传感器网络由数百个传感器节点（SN）组成，相邻的SN可以获取相同的数据（Costa和Amaral，2012）。工业无线传感器网络（IWSN）技术的成功应用使得无线技术的功能和效率得以提高。无线技术的进步也促进了IWSN协议的发展，如ZigBee、WirelessHART（Ferrari等人， 2013年）、*通讯作者。电 子 邮件 地 址 ： gbs@telkomuniversity.ac.id（ G.B.Satrya ），wdragon@kumoh.ac. kr（S.Y. Shin）。沙特国王大学负责同行审查制作和主办：Elsevier用于工业自动化-过程自动化的无线网络（WIA-PA）（Zheng等人，2017年; Liang等人， 和ISA 100.11a（Rezha和Shin，2013年）。 本研究采用ISA 100.11a协议，其优点在于，当应用于现场时，它通过为通信过程提供安全和鲁棒的协议来满足工业需求（Rezha等人，2015年）。然而，之前的研究表明，ISA 100.11a仍然需要一些改进，例如优化某些设备的时间分配、延迟限制和最小化丢包（Standard，2009）。在 ISA 100.11a 中 ， 物 理 层 和 较 低 数 据 链 路 层 使 用 IEEE802.15.4，而较高数据链路层实现时分多址（TDMA）（Costa和Amaral，2012;Saputra和Shin，2014; Rezha等人，2015年）。基于IEEE 802.15.4，ISA 100.11a可以在信标启用或非信标启用模式下操作在信标使能的网络中，协调器发送周期性信标，该周期性信标包含允许网络节点同步它们的通信的信息以及关于不同网络节点的待决数据的信息。所有的时隙一起形成了所谓的时隙（Standard，2009）。近年来，特别是在IWSN调度问题的研究集中在各个方面。IETF创建了6TiSCH工作组以标准化IEEE 802.15.4e TSCH网络中的调度（请求评论RFC 7554）。在这个RFC中，作者讨论了九个问题和目标之一（Watteynehttps://doi.org/10.1016/j.jksuci.2020.01.0141319-1578/©2020作者。由爱思唯尔公司出版代表沙特国王大学这是一篇基于CC BY-NC-ND许可证的开放获取文章（http://creativecommons.org/licenses/by-nc-nd/4.0/）。可在ScienceDirect上获得目录列表沙特国王大学学报杂志首页：www.sciencedirect.comG.B. Satrya，S.Y.Shin/ Journal of King Saud University707例 如 ， 2015 ） ， 其 中 调 度 机 制 可 以 被 设 想 并 且 可 以 在 IEEE802.15.4e. Saifullah 等人（2010 ）提出了基于分支定界技术的WirelessHART网络的有效可扩展性测试，该技术提供了实时流的端到端延迟的安全且合理紧的上界。Duquennoy等人（2015）提出了通过自主调度的TSCH（Orchestra）的鲁棒网状网络，其允许为不同的业务平面提供一组时隙，并且以这样的方式定义时隙，使得它们可以随着低功率（RPL）拓扑的路由协议的发展而自动Xu等人提出了一种用于子网络的可选轮询时隙分配方法，以最大化WSN上通信的可靠性和完整性（Xu等人， 2014年）。Saputra和Shin（2014）提出了截止日期单调调度（DMS），其通过使用离线调度规则来减少开销而不降低网络性能，其中所有任务都被假设为具有静态优先级。同样的研究人员还表明，DMS只能减少信标的数量，并使用模拟来表明，它可以优化错过的最后期限为有限的持续时间为500毫秒。在我们的研究中，我们表明，DMS（Saputra和Shin，2014年）的方法，优化调度仍然有一个错过的最后期限为500-750毫秒。我们解决的问题是时隙优化的调度，避免错过的最后期限，并使用进化算法（EA）的IWSN方案的将遗传算法与调度策略相结合，提出了一种改进的遗传算法，利用最短截止期为遗传算法提供输入进行时隙调度。一旦最短的截止日期检索使用排序，我们增强了时隙使用遗传算法的过程，即选择，交叉和变异，以提供最佳的后代（解决方案）。在实践中，GA直接评估每个解决方案的候选人通过其缺陷时间，并计算相应的适应值。然后，通过使用面向对象的模拟，我们比较了最早期限优先（EDF ）（Liu和Layland，1973），DMS（Saputra和Shin，2014），PSO（Shi和Eberhart，1999），OLPSO（Zhan等人，2011）、GA和MGA，其具有持续时间和SN的变化。我们的贡献如下：1. 我们证明了DMS算法的缺点，它遵循ISA 100.11a的网络模型和系统模型。2. 我们提出了一个优化遗传算法优化的无线传感器网络的配置。3. 我们定义的算法，转换TDMA的遗传学形式（基因型和表型）的基础上，并模拟它基于面向对象的编程。4. 我们评估并证明了GA和MGA优于现有的基准技术（EDF，DMS，PSO和OLPSO）。本文的其余部分组织如下。第2节回顾相关文献。第3节讨论了基于ISA 100.11a标准使用GA的拟议系统的设计。第4节给出了一个案例研究和模拟结果。第五部分是分析和讨论。最后，第6节提供了结论，并提出了未来的工作从本文产生的2. 文献综述2.1. ISA 100.11aDewanta等人（2012），提出了在ISA 100.11a的指定时隙上的消息调度以满足实时属性。设计了一个可容纳周期性实时（PRT）消息、非周期性实时（报警）消息和非实时（NRT）消息的报警器。这种方法是通过采用一个UART和多个UART来容纳PRT消息，而不忽略NRT和报警消息。然而，结果表明，使用这种消息调度技术需要更多的信标在系统中，并增加了开销。与Nhon和Kim的方法不同的是，Nhon和Kim的方法涉及两种新的共享时间消息调度方法-大量ISA 100.11a标准，以增强实时性能，即流量感知消息调度（TAMS）和竞争窗口大小调整（CWSA）（Nhon和Kim，2015）。仿真结果表明，这两种方法在成功概率和端到端延迟方面提供了性能改进然而，这项研究的结果只能应用于星型拓扑结构和有限的模拟时间此 外 ， Yasari 等 人 提 出 了 一 种 灵 活 的 在 线 多 目 标 优 化 框 架（FOMOF），该框架通过使用ISA100.11a的共享时隙来执行，并通过基于多目标遗传的约束优化来进行（Yasari等人， 2017年）。该工作考虑了具有35个端节点和一个网关的ISA100.11a目标函数的构建是为了保持高数量的节点和组中某些权重比的最小差异采用反馈和前馈模式对仿真模型进行了实证验证实验结果表明，该算法能够以较小的平均时延和最大的节点数实现对一定QoS水平的良好跟踪另一个结果表明，网络中的最高节点总数增加了数据包传输的延迟。2.2. 基于人工智能经典的目标覆盖方法假设环境是完全已知的，每个目标只被一个传感器覆盖。然而，目标可能需要由多于一个传感器覆盖。它被称为K覆盖问题。Elhoseny等人提出了一种基于遗传算法（GA）的K-覆盖模型，用于延长WSN寿命（Elhoseny等人，2017年）。与传统的方法相比，该方法能够提高无线传感器网络此外，我们提出的方法提供了一个框架，可以在静态和移动环境中使用，以延长网络的生命周期在K-覆盖模型。Harizan和Kuila研究了一种改进的基于遗传算法（GA）的无线传感器网络调度（Harizan和Kuila，2019）。给出了一种有效染色体的表示，并证明了在交叉和变异操作后，有效染色体的产生。该适应度函数以选择最少SN数、全覆盖率、连通性和所选SN的能量水平4个相互冲突的目标获得。这项工作引入了一种新的变异操作，以获得更好的性能和更快的收敛速度，建议基于遗传算法的方法。它还制定了线性规划的调度问题。通过使用不同的网络场景，所提出的方案进行了仿真与不同的SN和目标点的数量和网络长度。最近，还有其他研究成功地应用了GA，例如，使用GA进行拓扑控制的无监督学习方法（Chang等人，2018年），通过将非排序遗传算法2（NSGA2）算法与局部搜索算法相结合来放置静态传感器和继电器以监测特定位置（Perez，2018年），以及通过在WSN中使用GA进行结构健康监测来联合优化传感器放置，路由和流量分配（Elsersy等人，2016年）。与使用GA作为基础的五项研究类似，这项研究也是708G.B. Satrya，S.Y.Shin/ Journal of King Saud University←←ðÞ设计使用GA应用ISA 100.11a在优化的数据包调度的多个传感器具有不同的优先级和最后期限作为最重要的属性。3. 设计拓扑和算法3.1. 网络模型与问题识别我们提出的方案是（Saputra和Shin，2014）中提出的方案的改进。在网络建模方面，先前研究（Saputra和Shin，2014）的结果仅针对多达100个SN进行了测试。我们的研究集中在一个单一的通道，并采用了星型网络拓扑结构，如图所示。1.一、每个无线传感器节点代表不同的传感器和表1中提供的信息。我们的目标是解决的主要问题是每个无线传感器节点的周期性传输和节点产生的最后期限，由于不可预测的突发性的流量。在本研究中的问题识别有一定的参数和他们的值在这里给出复制的IWSN流量。这些参数是：rM表示释放时间，cM表示计算时间，dM表示截止时间，tM表示周期时间。如Saputra和Shin（2014）所述，我们还采用了IWSN标准，即ISA 100.11a作为样本案例研究。表1列出了网络拓扑中每个节点的详细信息.该场景首先在网关上生成数据流量，网关充当定期向网络发送信标的协调器我们假设Mn是周期性消息对于每个节点，Mn1/4 =Mn nB;Mn1;Mn2;Mn3;. ;M n10。MnB是发送信标的网关的广播消息。Mn1是一个用于节点1的odic消息。在本案例研究中，信标在计算最后期限时被赋予最高优先级。简而言之，我们在计算条件表达式时将信标作为最高优先级。3.2. 审查Saputra和Shin（2014）中的DMS方法DMS用于减少信标的数量，表1IWSN调度的仿真参数。节点r Mn （毫秒）c Mn （毫秒）d Mn （毫秒）t Mn （毫秒）信标01010250节点1102020150节点220208080节点33030100100节点440105050基于此结果（如表2所示），DMS不适用于可重复调度测试。因此，DMS不适合应用于实时情况。在IWSN特别是ISA 100.11a上，这样的系统可能每天24小时运行。本文提出的解决方案使用遗传算法结合DMS构建一个更智能的IWSN。3.3. 该算法根据《自然和人工系统的适应》一书的建议在此基础上，我们尝试通过添加DMS算法来修改遗传算法，以帮助解决IWSN调度问题。算法1给出了我们提出的并行调度MGA的设计流程图. 二、我们在人口建立之初就实施了DMS。DMS的最佳结果（按最小截止日期排序）用作GA的输入（算法1步骤6）。遗传算法的修改，以确保最好的人口是从最好的父母在生物过程中获得。预期这有助于基于适应度函数在调度期间优化时隙和错过的最后期限（如算法1，步骤7到14中所示）。评估过程包括三个步骤，例如，选择（步骤10）、交叉（步骤11）和变异（步骤12）。算法1中使用的符号如下。Pg是第g个种群指数，I是从DMS获得的个体，Sg是指数g中个体幸存者的集合，以及Og是指数g中的后代个体的集合。对使用消息调度的方法的改进，Dewanta等人（2012年）。先前的场景（Saputra和Shin，2014）仅对一个时隙有效，其中一个时隙由25个时隙（ts）组成，并且1个ts = 10 ms。表2给出了三个超帧，Mn3在第二个和第三个超帧之间延迟。根据表1中的数据，节点3具有30 ms的计算时间和100 ms的截止时间。因此，节点3应该在ts-52或ts-53执行。Ts-54是节点3的第五周期（后续周期的分配如表2所示，节点3只执行了两次，而在一个周期内应该执行三次。总之，节点3在第二次试验（ts-52和ts-53）中延迟。Fig. 1. IWSN的网络模型ISA调度1：INITIALISE g 1;d生成计数器的初始化2：初始化Pg←P初始化;d生成第一个种群的个体3：转换（Pg）;d计算适应度值4：转换I转换DMS计划;d将DMS转化为表型基因型5：REPLACEPg←ReplaceWorstIndividualPg;I;d替换为新个体（I）6：计算（Pg）;d计算适应值7：while！完成的d满足终止标准8：g←g1d增量生成计数器9：Sg←SelectPg-1;Nd选择过程幸存者10：Og←SelectPg-1;Pg-1：Count-Nd后代的选择11：Og←交叉验证Og交叉验证过程，使用单点交叉12：Og←MutationOgdMutation过程，使用随机mutator13：Pg←SgOgd根据幸存者和后代创建新种群14：苯甲酸酯（Pg）;15：结束时G.B. Satrya，S.Y.Shin/ Journal of King Saud University709联系我们1TDF;Tdf>0ð Þ表2模拟多达三个超帧; Oka Shin错误。时隙号[1].. .[四十三][第四十四届][45个][46个][47个][48个][49个][50个][五十一][五十二][五十三][54].. .[第七十五章]执行节点0个.. .224311340223 4信标0节点10个.. ... .110节点2.. .2222节点3.. .33..3节点4错过的最后期限空闲总缺陷时间.. .节点38（80 ms）160 Ms444不是e：符号。，意味着存在错过的最后期限。图二. MGA流程图。基于网络模型，本文对遗传算法中的术语进行了详细的解释。一个IWSN将代表一个个体，而多个IWSN将代表人口。GA配置的更多细节将在第4节中解释。由于本文中使用的ISA 100.11a，一个个体的染色体代表一个超帧，例如，25 ts，每个ts为10 ms染色体的结构分为基因型和表型。每个基因型由基因组成，每个基因代表一个基因的信息。IWSN即，rMn;dMn;tMn，和cMn。然而，GA将经常表1. 个体被表示为整数。每个基因中的整数除了信标，基因的长度和基因序列的位置也标志着执行。对于信标（B）= 0的时隙，基因长度等于4，即，在第一个槽处，并且可以在等级0到3之间的每个基因上填充的可能值被声明为节点0用于索引0，节点1用于索引1，等等。图3.第三章。3.3.2. 适应度函数适应度函数是提供用于计算一个（或多个）基因型的质量的函数。此功能的作用是以表示应当描述最优收敛速率的群体要求的适应度。人口必须进行调整，以符合评价职能规定的标准。每个可行解都可以用问题的适应度值来表征。在这种情况下，我们的目标是优化调度。我们定义的最佳时间表一样，最短的缺陷时间（Tdf），这是空闲时间（Tid）和迟到时间（Tlt）的总和。遗传表示不适用于信标，因为根据IEEE 802.15.4上的数据传输的要求，信标在同步阶段被分配了特定的优先级（标准，2009）。基于等式如果缺陷时间等于0，则为1，即，在没有空闲时间和错过的最后期限，然后在方程的健身值二等于一。适应度的期望值是在每个时隙中没有延迟或空闲时间。Tdf¼TidTlt1因此，fitness值为重复这三个过程（选择，交叉，变异）取决于f T（1;Tdf¼023.3.1.遗传表示构建GA的第一阶段是决定种群的遗传它涉及基因型和表型的设计。自动化解决问题的第一步是决定如何指定可能的解决方案，并以一种使它们能够被计算机操纵的方式存储。 我们将在原始问题背景中形成可能的解决方案的对象称为表型，而它们的编码，即EA中的个体，称为基因型。在许多情况下，将有许多选项，并实现适当的表示是最具挑战性的障碍，以克服在设计遗传算法。在本案例研究中，我们使用整数表示，如图5所示，我们还定义了图图4示出了当使用GA时作为适应度值的“缺陷时间”计算的实现。基于等式（1），其计算错过的最后期限值，考虑不同的参数，诸如用于释放时间的rMn、用于最后期限时间的dMn、用于周期性时间的tMn以及用于计算时间的cMn（如在表1中）。在本研究中，我们根据定理计算这些错过的截止日期图三.的代表对某些信息的当前最佳适应值。710G.B. Satrya，S.Y.Shin/ Journal of King Saud University8-Jj j j j-我-¼¼见图4。 计算缺陷时间的流程图。在Saputra和Shin（2014）和Audsley等人（1991）中提出的，其指出，只有当它符合Mn：cMn6dMn时，才能调度调度。N和B符号是要执行的节点，而bea-con，分别。完成时间是系统执行节点所需的总时间。基于（Dewanta等人，2012），网关使用信标的时隙来向所有节点通知时隙占用，如图3所示。在图4中更详细地解释了缺陷时间的计算。首先，我们设置i= 0且slot = 1。第二，如果信标已准备好并且尚未完成执行，则在当前时隙上执行信标。第三，如果第i个基因处的节点准备就绪并且尚未完成执行，则在当前时隙上执行该节点并递增i。第四，否则，将当前时隙设置为空闲。第五，检查节点上是否存在延迟。第六，增加时隙。第七，如果所有基因都已执行，则结束该过程。否则，再次进入第二步3.3.3. 编码基因型基于在个体表示中呈现的情况，如果存在个体，例如，0 0 1 3，则所得到的时间表如图1所示。 五、3.3.4. 重组交叉通常被称为交叉，其动机是生物类比。基于pc的交叉率，应用了交叉算子.假设两个选定的父母和两个后代产生的重组概率为2具有Pc的双亲;换句话说，复制概率为1Pc的双亲。交叉表示可以使用一点交叉、n点交叉和均匀交叉（Eiben等人，2003年），所有这些都在这个系统上进行了测试。染色体维持重组过程的可能性是基于已经预先确定的交换的3.3.5. 突变突变过程发生在通过选择将随机突变的染色体的重组过程之后，在随机确定染色体中的突变点之后基于预定的突变概率pm计算突变染色体的数目。的位置图五. 表型基因型的表示。通过生成1和总基因之间的随机整数来选择突变基因。如果生成的随机数小于可变突变率Pm ，则它选择该位置作为要突变的子染色体（Eiben等人， 2003年）。例如，如果pm设置为10%，则这将是将被突变的总基因的预期百分比。3.3.6. 终止条件遗传算法和其他进化算法是随机的，大多数情况下不能保证可以实现最优值。因此，可能存在从未达到最优解的情况，在这种情况下，算法将不会终止（Eiben等人，2003年）。因此，我们必须使用适当的设计，并预测这些条件是否会发生，并指定一个条件下，该算法将被终止。在我们的系统中，如果在另外1,000个迭代周期之后适应度值没有再次增加，则4. 案例研究和模拟在本节中，我们将重点介绍使用Java实现的GA和MGA。我们还比较了所有的算法与EDF作为另一个代表性的例子，一个非元启发式方法。我们使用的GA的配置是基于表1中的参数规范和图1中的拓扑结构。1.一、表3中列出的术语在第3.3节中解释EA分类是通过与50个粒子的离散PSO进行比较来评估的离散PSO是传统PSO（ShiandEberhart，1999）的改进版本. 在迭代时间t期间，从先前速度到新速度的更新3 .第三章。然后，新位置由先前位置和新速度之和确定，公式为四、tvit1-vit-1c1r1PospBest-Post1最佳2r2位置g最佳-位置t-1最佳3位置Post¼vtPost-14其中，t：迭代m：最大迭代（1000）c：常数（c12;c2 2）r：随机值（0-1）表3遗传算法配置。参数值GA群体大小50代数1000次迭代选择方法锦标赛/截断后代分数0.4交叉方法单点交叉（0. 2）多点交叉（0. 2/ 2突变方法高斯突变器（0.00001最大表型年龄无表型年龄G.B. Satrya，S.Y.Shin/ Journal of King Saud University711模Pos：位置pBest：每次迭代的gBest：整体迭代在更 全面的比较 中， 我们 使用 了 PSO家族的最 新发 展 OLPSO（Zhan等人，2011年; Li等人， 2015年）。在OLPSO中引入了正交试验设计（OED）机制.OED的过程取代了传统PSO中的学习过程，计算如下：vid¼.1-d双曲坐标-1双 曲坐标rd双曲坐标-xi d5其中，当前粒子Xi在其个人最佳位置Pi和其邻域的最佳位置Pn之间向量Po仅存储Pi和Pn的索引，而不是真实位置值的副本也就是说，pod仅表示第d维由Pi或Pn引导。OLPSO模拟仍然使用50个粒子和1000次迭代。这些模拟使用Java（Jacobson和Kanber，2015 ）运行，JDK1.8.0_151作为其开发的实现。对于EA和遗传编程库，我们使用Jenet- ics（jenetics.io），而对于编程编辑器，我们使用Windows的NetBeans8.2 64位版本我们建立的模拟使用时隙号的变化即，100，200，500。在节点数量方面，我们使用一个节点作为信标并将无线传感器网络的数目改变为4、7、10和100个节点。表2（DMS审查）提供了使用四个SN和一个信标的测试结果。我们证明了DMS公司未能在第三季度处理错过的最后期限。该表包含10和100 SN的选定样本结果。本实验的完整结果见第5节。4.1. 10个节点图图6和图7显示了72个测试场景中两个场景的测试结果。该实验使用一个信标，10个WSNs和500 ts（或5000 ms）。本测试还使用了第IV-A节中提供的描述，并增加了节点数量。这个测试的目的是确定在何种程度上GA可以成功地优化调度。如前所述，SN的参数，如释放时间、计算时间、截止时间和周期时间是随机生成的。简而言之，GA和MGA能够处理任何数量的传感器数据，条件是继续监控为GA指定的适应度值和参数（参见见图6。仿真：OLPSO，500时隙，10节点。见图7。 模拟：MGA，500时隙，10节点。712G.B. Satrya，S.Y.Shin/ Journal of King Saud University表3）。这种方法有利于发现一个更优的解决方案，遗传算法，这是一种随机算法。术语随机是指个体的出现无法预测的随机发生（Eiben等人，2003年）;然而，当从整个观察的分布来衡量时，它通常遵循一种模式。从这一点开始，它需要精确的个体选择，变异和交叉。然而，使用10个SN的实验表明，从使用OLPSO得到的结果是次优比从EDF，DMS，PSO，GA，和MGA得到的。 如在（Zhan等人，2011年; Li等人， 2015），p 〇 d是由P i的组合组成的引导向量，Pn。在每一代中，粒子i更新其速度和位置，第10节据作者所4.2. 100个节点图图8和图9呈现了具有足够大数量的传感器的案例研究的结果，即，100个SN。我们在100 ts、200 ts和500 ts类别中测试了此本小节描述了我们从200 ts中获得的结果，100个SN。OLPSO和MGA的结果分别如图8和图9在该场景下进行的基于100个SN的大规模实验中，OLPSO的性能与10个SN场景下的性能几乎相同此外，它提供了进一步的证据，OLPSO是不太适合ISA 100.11a上的并行调度这归因于OLPSO的特征，其与传统PSO一样是基于向量的，而这种情况是基于TDMA的（基于离散的）。虽然OEM算法是为了解决局部最优问题而提出的，但在这种情况下，OLPSO算法仍然会产生过早覆盖，表明存在一些空闲时隙。图9显示MGA更适合于这种组合和离散的底盘。在第1节的解释之后，PSO，OLPSO，GA和MGA都是元启发式算法，但具有不同的搜索空间解决方案。在每个迭代步骤中，MGA总是找到一个最优的解决方案，因为三个组件（选择，变异和交叉）。OLPSO算法使用遵循适应值方向的粒子和速度。然而，对于这种IWSN上的时隙优化的情况下，OLPSO经常被阻止发现全局最优解，如前所述，并清楚地显示了空闲时间的结果。见图8。仿真：OLPSO，200时隙，100节点。见图9。 模拟：MGA，200时隙，100节点。G.B. Satrya，S.Y.Shin/ Journal of King Saud University7135. 结果和总结5.1. 缺陷时间PSO和OLPSO建模在这里由一群的50个par-random初始化与人口的随机解决方案的候选人。每个粒子的位置由位置矢量表示，速度由速度矢量表示对于适应度值，我们用c1和c2作为正常数，指的是自我识别成分的系数，c2作为正常数，指的是社会成分的系数。在72个场景下，PSO和OLPSO的结果优于DMS的结果，但比GA的结果要差。这是因为PSO和OLPSO搜索“全局最小值”的过程遗传算法基于自然基因选择和重组，从种群中寻找最佳解这两个过程中的后者是随机的。缺陷时间的计算结果是通过对种群中的一些最佳候选者进行交叉和变异来获得的。结果取决于交叉概率（pc）和变异率（pm）的大小。简而言之，缺陷时间的值密切依赖于指定和用于GA和MGA的属性。表3列出了我们通过实验获得的IWSN案例研究的最佳配置。5.2. 内存消耗和处理时间图 10和11分别比较了内存消耗和处理时间。可以看出，相比之下，EDF和DMS表现出更低的内存消耗和更高的稳定性，考虑到它们的低内存消耗和更短的处理时间。这是因为EDF和DMS是非元启发式算法。内存消耗和处理时间对应用进化计算方法进行IWSN调度的影响，PSO、OLPSO、GA和MGA在以下段落中进行解释。如图 10，给出了72个场景的案例研究，GA和MGA与PSO 和OLPSO相比，具有更少的内存消耗。据作者所知，GA和MGA的内存消耗较低的原因有三个首先，PSO和GA在产生新种群时遵循不同的方法：PSO的计算基于速度和方向，而GA使用交叉和变异。其次，在PSO和GA中生成新解（后代）的过程是基于适应值的，如第三节所述见图11。模拟结果总结：处理时间。最后，经过仔细检查，可以看出，PSO总是将其当前最佳解与前一个进行比较，并保留两者中更优的，而在GA中，没有存储过程。遗传算法直接执行交叉和变异过程的基因，其中适应度低。该处理时间在算法开始时计算，直到算法完成，并且在所有12个预定义场景中执行 如可见于图 11、GA和MGA比PSO和OLPSO需要更少的处理时间。缩短处理时间的主要原因如下。首先，因为OLPSO使用基于向量的优化，如果一个或多个邻居假设第i个解决方案（甚至过早）是最好的，这通常被称为陷入局部最优。其次，这个案例研究证明了OLPSO总是产生齐次解（如图所示）。 8）;几代缺陷时间是指几个时隙中的相同值。最后，PSO和OLPSO的方程在搜索过程中有更详细的参数，但作者认为这一特点不适合在离散情况下实现综上所述，遗传算法和MGA所需的处理时间是小于所需的粒子群算法和OLPSO的IWSN中的并行调度。5.3. 算法验证表4中有12种不同类型的数据场景，每种都分别用PSO、OLPSO、GA和MGA进行了测试。在（Yang等人，2013）第9章，特别地，据说属于元算法的所有算法将为正在执行的每个算法产生不同的解决方案。因此，为了确保验证见图10。 模拟结果总结：内存消耗。在所有这些有效的启发式算法中，迭代必须重复10到100次。在本文中，使用Yang等人（2013）推荐的10次重复。它旨在确保找到全局最小值的高成功率，并且不会偶然遇到适合度值的报告。几个测试被用来验证这四个EA。对于每个测试，我们还计算了测量值的平均值和标准差（r）迭代方法不用于EDF和DMS，因为它们是非元启发式方法，在它们的计算中使用优先级分配策略（Liu和Layland，1973;Audsley等人，1991年）。在DMS和EDF上使用迭代计算将产生相同的值，在Meta启发式算法上反之亦然。从表4中可以看出，EDF和DMS无法解决两种情况下的缺陷时间，例如：通过增加TS的数量和增加SN。这项研究显示了四个新的候选EA算法的IWSN，例如：常规离散PSO、OLPSO、常规离散GA和MGA。714G.B. Satrya，S.Y.Shin/ Journal of King Saud University表4情景模拟结果。没有TsSNS缺陷时间（ms）EDF（Liu和Layland，1973）DMS（Saputra和Shin，2014年）PSO（Shi和Eberhart，1999年）OLPSO（Zhan等人，（2011年）GAMGA110042220218022142199210020102100730903330332134572764227931001067705080639169405071489841001008497085070829618329579688797035200447204520483452374366406262007719071208025838860544882720010148501159016071167281246310901820010018405018422018074518223617467517442795004118001136013673145551187610432105007171901830022977240021735514015115001039480290204418246203362662826312500100481130481640475533480237471593465529对每个算法进行重复以检查它们的拟合值。它出现了GA和MGA优于现有的基准EA算法。5.4. 讨论基于前面的三个分析，即缺陷时间（即：空闲时间、延迟时间）、内存消耗、处理时间等方面的性能进行了分析，得出EA算法可以应用于TDMA情况下，是无线传感器网络超帧调度对于缺陷时间，MGA在时隙的使用中提供了最优的结果，并且可以在所有网络拓扑和场景中减少错过截止日期的价值。这是因为GA可以重复选择最佳候选（选择，变异和交叉）。而对于4到10个节点的内存消耗，MGA显示最佳内存使用量小于300 MB，而PSO可以达到550 MB。对于100个节点类别，即使内存使用达到350 MB，MGA仍然可以提供比OLPSO更有吸引力的结果PSO家族产生更大的内存消耗，因为每次最佳候选的比较总是被保存。对于10节点以下的处理时间，遗传算法和多遗传算法的处理时间相对小于10 ms，而粒子群算法和最优粒子群算法的处理时间最长可达20 ms。此外，对于上述10个节点类别的场景，与PSO和OLPSO相比，GA和MGA仍然产生更好的测试结果，其中它达到90 ms（100个节点场景）。此外，我们还提出了最佳配置的变异和交叉阶段。6. 结论这项研究表明，使用所提出的方法来解决超帧调度中的DMS问题。作为一种替代解决方案和增强目前的方法，我们建议使用遗传算法在无线传感器网络超帧调度优化。提出了一种基于遗传算法和多重遗传算法的遗传算法，并与粒子群优化算法和最优粒子群优化算法进行了性能比较，作为进化算法的对比研究在这项研究中测试的72个场景表明，PSO和OLPSO不适合离散的情况。PSO和OLPSO更适合于连续的情况。然而，在这项研究中，PSO和OLPSO的配置已被修改，以更适合于离散的情况。在IWSN中的时间-批量优化，在这项研究中使用，是一个离散的情况下的一个例子。本研究还建议设置GA属性的配置。我们的结论是，MGA的优化性能的缺陷时间，内存消耗，超帧调度在IWSN中的处理时间，特别是在ISA 100.11a中，是优越的。这一结果支持了遗传算法可以解决无线传感器网络中的调度问题的理论。确认这项工作得到了韩国教育科学技术部资助的韩国国家研究基金会（NRF）优先研究中心计划的支持（2018R1A6A1A03024003）。引用Audsley ， N. ， Burns ， A. ， 理 查 森 ， M. ， Wellings ， A. ， 1991. Hard real timescheduling ： The deadline-monotonic approach ， IFAC Proceedings 24 （ 2 ）（1991）127https：//doi.org/10.1016/S1474-6670（17）51283-5.Bi，Z.，Xu，L.D.，Wang，C.，中国地质大学，2014.面向现代制造业的企业物联网系统。IEEETrans.Industr.Inf.10（2），1537-1546。https://doi.org/10.1109/TII.2014.2300338.张，Y.，Yuan，X.，李，B.，尼亚托，D.，Al-Dhahir，N.，2018.基于无监督学习和遗传算法的高能效超密集无线传感器网络拓扑控制。IEEE通信Lett. 22（11），2370-2373。https://doi.org/10.1109/LCOMM.2018.2870886网站。科 斯 塔 ， 硕 士 ， Amaral ， J.L. ， 2012. 无 线 工 业 自 动 化 标 准 分 析 ： Isa-100.11 a 和wirelesshart，InTech Magazine.Dewanta，F.，Rezha，F.P.，金，D.-美国，2012. isa100专用时隙上的消息调度方法。11a，见：信息和通信技术融合。在：（ICTC），2012年国际会议，IEEE，pp。466- 471Duquennoy ， S. ， Al Nahas ， B. ， Landsiedel ， O. ， Watteyne ， T. ， 2015 年 。Orchestra：通过自主调度tsch的鲁棒网状网络。在：第13届ACM嵌入式网络传感器系统会议论文集，SenSys '15。ACM，New York，NY，US