异构无线传感器网络的分布式任务分配算法

沙特国王大学学报异构无线传感器网络TitusIssac，Salaja Silas，Elijah Blessing RajsinghKarunya Institute of Technology Sciences，Coimbatore，Tamil Nadu 641 114，India阿提奇莱因福奥文章历史记录：收到2019年2020年6月11日修订2020年6月21日接受2020年6月26日在线提供保留字：组织P系统无线传感器网络多目标问题任务分配决策支持系统并行计算可持续计算A B S T R A C T现代无线传感器应用采用异构无线传感器网络（HeWSN）来实现其多目标任务。构成HeWSN的现代无线节点在其能力、功能和应用方面更加通用。由于HeWSN固有的异构特性和能力，在动态对现有任务分配算法的研究表明：（1）现有的任务分配算法大多是为同构环境设计的;（2）大部分自然启发的算法是为集中式体系结构设计的。现有的任务分配算法在调度任务时会导致资源利用率低下以及网络资源的快速耗尽。本最后，需要一种新的、分布式的、异构的任务分配算法，该算法必须与现代传感器的能力、功能和应用相结合，以实现可持续的计算。在此基础上，提出了基于组织P系统的分布式异构无线传感器网络任务分配算法。所提出的方法的实验分析进行了自我评估，以及与相应的最近的基准算法在各种条件下，其性能指标进行了分析。©2020作者由爱思唯尔公司出版代表沙特国王大学这是一个开放的访问CC BY-NC-ND许可证下的文章（http://creativecommons.org/licenses/by-nc-nd/4.0/）。1. 介绍当代世界正在见证数字化技术的快速进步，通过将新的能力与最先进的小型化、制造和嵌入技术相结合（Munir等人，2014; Roozeboom等人，2013年）的报告。当前设备可以被广泛地分类为传统设备和智能设备。传统设备被设计为执行一组固定任务的独立设备。大多数传统设备都是手动启动的，而智能设备可以是自启动或远程启动的。智能设备中的致动基于机载定时器和传感器的反馈。因此，传感器等附件成为当今场景中不可避免的组成部分。除了感测能力之外，智能设备还可以具有处理、存储和通信能力。*通讯作者。电子邮件地址：titusissac@gmail.com（T. Issac）。沙特国王大学负责同行审查满足应用要求的能力（Zanella等人，2014; Su等人，2011; Issac等人，2019年）。与传统设备相比，上述能力使智能设备能够与其对应部分和其他智能设备进行处理、通信和协作现代智能设备能够执行各种复杂的应用程序。因此，多功能的下一代智能设备已经成为我们日常活动中必不可少的（Munir等人，2014;Su等人，2011年）。例如，（i）外科医生从远程位置使用智能设备对患者执行复杂的外科手术，或（ii）使用智能传感器的智能街道照明，描绘了智能设备在我们日常生活中的含义（Ballantyne，2002; Issac等人， 2020年）。一组 相互协 作的 无线智 能设备 组成了 一个 无线传 感器网 络（WSN）。无线传感器网络中的智能终端设备通常被称为节点。节点通常被定义为包括传感器、处理器、存储器和无线电部件的资源受限的无线微机电系统WSN应用的多个任务由节点执行（Pilloni等人，2014年）。以前，节点具有有限的传感、处理和存储能力，使其通用性较差。因此，遗留节点仅限于一组简单的应用程序，如自动化（家庭、楼宇、工业）、监控https://doi.org/10.1016/j.jksuci.2020.06.0081319-1578/©2020作者。由爱思唯尔公司出版代表沙特国王大学这是一篇基于CC BY-NC-ND许可证的开放获取文章（http://creativecommons.org/licenses/by-nc-nd/4.0/）。制作和主办：Elsevier可在ScienceDirect上获得目录列表沙特国王大学学报杂志首页：www.sciencedirect.com小行星3686 Issac等人 /沙特国王大学学报-计算机与信息科学34（2022）3685- 3702（环境、栖息地、野火）和跟踪应用（Sohraby等人，2007; Yick等人， 2008年）。相反，当代节点的固有多功能性质是由于多重感测、处理和通信能力（Munir等人，2014年）。显著的节点进步主要是由当代WSN应用的要求以及现代制造和嵌入技术驱动的（Munir等人，2014年）。已经使用现代WSN节点可视化了各种复杂的WSN应用（Munir等人，2014年）。与传统节点相比，多功能节点可能相对更昂贵。然而，一些多功能节点可以替代WSN应用中的大量传统节点WSN应用中的节点计数与部署、通信和所部署节点的维护的复杂性成正比（Patel等人，2007; Panja等人，2008年）。多功能节点具有节点数量少、部署方便、维护简单等优点，是无线传感器网络应用的理想一个无线传感器网络应用程序通过使用一个任务来完成它的任务分配算法（Titus等人，2016年）。该方法将无线传感器网络应用分解为多个不可分割的任务，并采用任务分配算法将其分配给理想的传感器节点。在最近的过去，无线传感器网络的应用往往局限于简单的，周期性的监测和跟踪应用，需要一个简单的静态任务分配算法。在静态任务分配方案中，任务在初始和重组阶段被预先分配给节点。静态任务分配对于简单的非关键应用程序是理想的。然而，任务关键型应用（如海啸、地震和滑坡监测）是基于随机偶发事件（Miorandi等人，2012年）。关键任务应用程序需要一个动态的按需任务分配算法，以满足动态的要求，如通信范围，移动性，能源需求，候选节点的可用性等。采用静态任务分配的关键任务应用程序将否定的动态和零星的基本关键任务应用程序的性质。为了克服静态任务分配算法的上述问题，需要按需动态任务分配算法。现有的任务分配算法大多是基于主要假设参与节点是同质的（Jin等人，2012; Xie和Qin，2008;Tian和Ekici，2015）。具有相似能力的节点集被认为是同质WSN（HoWSN），而具有不同能力的节点集被认为是异构WSN（HeWSN）。从文献中可以明显看出，在任务分配过程中，大多数HoWSN任务分配算法忽略了参与节点的属性，只考虑了剩余能量、等待时间和截止期限错过率等性能指标在HeWSN上采用HoWSN任务分配算法会由于节点属性的变化而增加任务失配率节点属性对HeWSN应用程序的任务有隐含的影响。节点的固有属性可以大致分类为传感器、处理器、存储和通信组件属性。传感器组件属性包括功率要求（SPR）、有效测量范围（SMR）、准确度（SAC）、精度（SPN）、分辨率（SRN）、响应时间（SRT）和灵敏度（SSY）（Carr和John，2002; Guide，n.d.; 布朗，北达科他州）. 上述节点属性在HoWSN中保持相同，但是参与节点的一个或多个属性可以在HeWSN中变化。现有的HeWSN任务分配算法在任务分配过程中忽略了节点的固有属性和能力，导致任务分配不均衡不成比例的任务分配会显著增加任务的截止期缺失率（DMR）和重复性，评估网络的性能和生命周期无线传感器网络的体系结构类型对任务分配起着至关重要的作用。集中式WSN倾向于（i）单点故障，（ii）可扩展性和（iii）鲁棒性（Pilloni等人， 2014年）。此外，它需要一个强大的簇头为每个集群。在集中式方法中，基站和簇头通常采用功能强大的启发式方法分布式无线传感器网络通过节点间的分布式计算克服了上述问题.一个无线传感器网络节点总是被假定为一个资源受限的设备，这将是理想的，采用分布式的任务分配算法的HeWSN。基于多准则的HeWSN任务分配问题总是被建模为非多项式（NP）完全问题，更好地称为NP完全问题（Mezei等人，2013年）的报告。然而，这项工作的目标是一个子集的无线传感器网络的任务分配问题。它是建模的任务分配在一个单跳的异构无线传感器网络，包括多功能的节点，其中不可分割的任务分配给节点。这个任务分配问题是一个多项式类问题，将在后面的章节中证明。总之，一个简单而强大的，动态的，启发式的，基于多准则的分布式任务分配算法HeWSN在分布式环境中是必要的。为此，提出了一种基于组织P系统的分布式任务分配算法（tPDTA）.实验分析表明，该系统是有效的。主要贡献如下：影响异构环境无线传感器网络的识别和讨论。首次提出了一种基于组织P系统（TPS）的异构无线传感器网络任务分配模型。tPDTA算法是一种动态、分布式、异构、近优的任务分配算法.该算法实现了无线传感器网络本文的其余部分组织如下。第2节提供了论文其余部分所需的材料。第三部分介绍了无线传感器网络任务分配算法的相关研究成果及其不足之处。并列举了影响任务分配算法的主要因素。第4节介绍了用于任务分配的组织P系统（TPS）的初步介绍。第5节讨论了建模实验模拟、自我评价方法和基准方法。第6节介绍了工作的性能计量分析。第7节最后总结了工作与未来的范围。2. 预赛第一部分讨论了传感器节点和任务的性质，以及它的简要描述和意义。2.1. 节点无线传感器节点是异构无线传感器网络（HeWSN）中的主要参与者，其在一个或多个属性和能力上与其他节点不同。节点包括以下组件：（i）传感器单元，（ii）处理单元，(iii) 存储单元，（iv）无线通信单元，和（v）电源单元。节点中的组件可以具有一个或多个单独的单元。节点的组件表示的单个表示如下。WSN包括一组节点，并且每个节点●●●●≤≤T. Issac等人/Journal of King Saud University- Computer and Information Sciences 34（2022）3685-37023687使用等式（1）数学地表示。目前，节点被赋予多功能能力。多功能的能力是通过多个节点组件实现的等式（2）表示具有其复合分量的节点符号WSN<$fNnidj1≤nid≤nmax;g1各种无线传感器网络任务分配算法，如已经提出了多次调整时间。然而，需要对现有的WSN任务分配算法进行调查，以确定其优点和缺点已经上升。3. 相关作品Nnid 1/4 fS;P;M;R;Bg现代无线传感器网络的应用越来越复杂，需要一种有效的任务分配算法。关于近期任务的在异构环境中，一个或多个单独的组件可以在节点中变化。为此，需要唯一地标识每个节点组件。传感器、处理器、存储器、无线电和电池由其唯一标识符0 sid0; 0pid0; 0mid0; 0rid0;和“bid”标识。各个节点组件的标识符范围如下：1≤sid≤smax;1≤pid≤pmax;1≤mid≤mmax;1≤rid≤rmax和1≤ bidbmax，其中变量“smax”、“pmax"、”mmax“、”rmax“和”bmax“分别表示节点的传感器、处理器、存储器、无线电和电池标识符的最大非零整数可变值。S/fSsidj1≤sid≤smax;g=3P¼. Ppidj1≤pid≤pmax;M¼ fMmidj1≤mid≤mmax;g≤5μ mR<$fRridj1≤rid≤rmax;g<$6B<$fBbidj1≤bid≤bmax;g<$7μ m节点的功能由节点组件的属性决定表1列出了重要的传感器节点属性及其描述。节点的传感器属性对诸如能量、时间和准确性的性能度量的影响在表2中列出。2.2. 任务任务是由传感器节点在给定实例处执行的不可分割的执行（Titus等人，2016年）。一个无线传感器网络应用程序被分解为多个任务，并由一个集合T表示T<$fTtidj1≤tid≤tmax;g≤8μ g无线传感器网络中的任务可以根据功能、性质和重复频率进行分类。每个任务都由一组任务属性表征。表3中列举了影响总体任务分配的任务的主要属性。2.3. 任务分配无线传感器网络中的任务分配是识别和分配任务给理想的传感器节点的过程。任务分配可大致分为以下几类。集中式/分散式任务分配（Yin等人，2017 b;Yang等人，2014年）。分类是基于任务分配算法的执行。集中式任务分配遵循多级分层架构。顶层节点通常被认为是强大的，任务分配执行和决策发生在领导节点（基站，簇头）。分布式方法坚持对等通信。分布式网络中的任务分配是通过对等节点之间的协商进行的。在本节中给出了来自文献的分配算法。此外，任务分配算法的兼容性分析，采用当代多功能异构传感器节点已在本节中进行。现有的任务分配算法对于HoWSN可能是理想的，然而，它不能应用于HeWSN（Jin等人，2012; Xie和Qin，2008; Tian和Ekici，2015）。此外，没有解决适应HeWSN环境的方法的可能性。改进的二进制粒子群优化（MBPSO），一种集中式静态任务分配算法，由Yang等人提出用于HeWSN（Yang等人，2014年）。使用“V”形家族函数将颗粒的位置编码为二进制矩阵。通过变异操作避免了局部极小值。然而，变异操作导致不可行解的生成显著增加，从而使计算过载升级。由于MBPSO是一种集中式算法，它需要一个强大的基站和簇头来执行。最近，研究人员Tkach等人研究了异质性，新分布式蜜蜂算法（HDBA）用于WSN中的多传感器分配（Tkach和Edan，2020）。每个节点被视为一只蜜蜂，并计算其效用函数。任务分配基于三个参数：（i）任务优先级，（ii）任务距离，和（iii）传感器HDBA采用轮选择规则，其中节点随机选择任务。传播的广播模式已被用来模拟蜜蜂的摇摆舞进行通信。未讨论大多数异质性因素。Niccolai等人提出了用于WSN的社会网络优化（SNO）的最优任务分配（Niccolai等人，2019年）。包含发送者标识符、时间戳、可见性值和成本值的称为post的通信消息用于通信。节点之间的通信通过两种方式进行，即：（i）朋友网络和（ii）信任网络。朋友网络被假定为最可信的，并且通信模式是双向的，而信任网络路径是通信模式是单向的并且被认为是弱的。两个主要的演变发生在SNO：（一）个人成长，（二）修改的朋友和信任网络。该方法的主要缺点是，无线传感器网络的异构性方面还没有得到广泛的讨论和考虑。Yin等人提出了用于分布式环境的基于自组织的协作任务分配（SOCTA）（Yin等人，2017年a）。在任务分配过程中考虑了节点的容量。基于先前的任务分配，创建节点列表其中一个主要假设是，这些任务是相互独立的。综合考虑了能量消耗和分布、截止期错过率、算法执行时间连续使用一组节点将导致节点的快速耗尽，从而导致网络的单点故障。分布式最优在线任务分配（DOOTA）方法由Yu等人提出，用于WSN中多跳簇的动态在线最优分配解决方案（Yu等人，2018年）。它采用二元决策理论，通过考虑感知、计算、通信和网络的能量消耗，最大化网络的●实际值小行星3688 Issac等人 /沙特国王大学学报-计算机与信息科学34（2022）3685- 3702表1节点属性。组件性能传感器●传感器类型：基于其功能● 传感器功率要求（SPR）（指南，未注明日期））：节点中的传感器在各种状态（诸如活动、睡眠状态）期间的功率需求。● 传感器有效测量范围（SMR）（Carr和John，2002年;指南，n.d. ）：节点中传感器的有效感测能力。测量范围介于测量范围下限（LMR）和测量范围上限（UMR）之间● 传感器精度（SAC）（Carr和John，2002年;指南，未注明））：实际值与感测值之间的最大差值。SAC可以用百分比表示，并通过以下公式计算。SAC1/4实际值-检测值× 100。● 传感器精度（SPN）（Carr和John，2002年;指南，n.d. ）：检测到的测量值的再现性程度。● 传感器响应时间（SRT）（Carr和John，2002）：输出变化所需的最大时间● 传感器分辨率（SRN）（Carr和John，2002年;指南，n.d. ）：传感器可测量的最低感测单位。● 传感器灵敏度（SSY）（Carr和John，2002）：传感器输出变化所需的最小可检测输入变化。处理器·处理器核心（Munir等人，2014年;多核处理器，n.d.）：中 央 处 理 器 内 部 的单个处理单元的 数 量 。● 并行操作：处理器执行多功能的能力可能是真的也可能是假的。● 快取记忆体：处理器内供快速存取的记忆体，以字节为单位● 处理器时钟速度：完成一个处理周期的速率以赫兹（Hz）为单位测量● 处理器理想工作温度：处理器组件的理想工作温度Memory·Memory Type（Hempstead等人，2008）：记忆存储设备的类型。● 内存存储大小（指南，未注明日期））：内存的最大存储大小。● 读取速度（指南，n.d. ）：从内存中读取数据的最大速率，以每秒位数为单位。● 写入速度（指南，n.d. ）：数据写入内存的最大速率，以每秒比特数为单位。● 理想工作温度（指南，n.d. ）：存储单元的理想工作温度无线●无线电类型（指南，未注明））：所采用的无线设备的类型（蓝牙、ZigBee、WIFI、NFC等）。● 无线标准：适用于无线设备的无线标准。● 带宽（指南，n.d. ）：在特定时间内，可以从网络中的一点传输到另一点的最大数据量。它是以每秒比特数来衡量的。● 通道（指南，无）：无线电类型提供的唯一频道数。● 通道带宽（指南，未注明））：无线电类型的最大单个信道带宽。● 传输速率（指南，n.d. ）：无线电组件的最大数据传输速率。它由每秒的数据位数来衡量● 接待率（指南，n.d. ）：无线电组件的最大数据接收速率。它由每秒的数据位数来衡量● 传输/接收的能量需求（指南，n.d. ）：发送和接收数据所需的总能量。它通常以焦耳为单位测量传输或接收的每一位数据。● 延迟：数据包往返目的地的往返时间（RTT）的最大延迟。蓄电池●电压（指南，未注明））：以伏特为单位测量的电极之间的最大电位差。● 电池容量（指南，n.d. ）：储存在电池中的总能量，以安培小时为● 电池理想工作温度（指南，n.d. ）：电池有效运行的理想工作温度● 充电能力（指南，n.d. ）：电池充电的能力。● 充电类型（指南，n.d. ）：充电模式的电源，如太阳能，无线.表2传感器特性的影响分析。属性WSN应用任务能源时间精度SPR✔SMR✔✔✔SAC✔SPN✔SRN✔SSYSRT✔✔治疗和睡眠。在任务分配过程中没有考虑传感器的特性，导致随后的任务期限比增加考虑的性能指标是算法执行时间，通信开销和网络寿命。Pilloni等人（Pilloni等人，2014）提出了任务分配协商（TAN）算法。TAN是一种分布式、启发式和动态的异构无线传感器网络任务分配算法TAN利用基于非合作博弈论的分布式随机算法（DSA）进行节点之间的协商，使用贪婪的八卦。TAN使用单跳通信执行集群内通信。不允许群集间通信。该任务模型采用有向无环图（DAG）建模，并带有任务优先约束。在智能城市场景和随机网络场景下模拟了所提出的工作考虑的性能指标是平均能耗和应用程序完成时间。在任务分配过程中未考虑节点属性Haung等人（Huang等人， 2019）调查了移动机器人在WSN中执行的任务。所考虑的任务大多分为（i）收集，（ii）交付和（iii）收集和交付的组合。讨论了各种应用的数学公式以及公开问题。Hamouda 在 研 究 文 章 中 贡 献 了 两 部 主 要 作 品 （ Hamouda ，2019）。(i)提出了一种基于生命周期感知的传感器节点选择算法（LA-SNSA表3任务属性表。任务属性● 任务标识符（Task identifier，tid）：WSN应用程序中使用的任务的唯一标识符（Ballantyne，2002）。● 任务优先级（TPY）：通过为每个任务分配1 ≤ TPY ≤ 5之间的数字优先级值来实现任务优先级;其中1是最大优先级，5是最小优先级（Xu等人，2007; Wang等人， 2015年）。● 任务抢占（TPE）：一个标志指示任务是否可以被中断（Xu等人， 2007年）。它被表示为布尔数据类型。● 任务能量需求（TED）：任务能量需求是成功执行任务所需的总能量 它以焦耳为单位测量（Zhu等人， 2007年）。● 任务期限（TDL）：任务期限是完成任务的最大允许持续时间，以秒为单位（Pilloni等人， 2014年）。● 任务完成时间（TCT）：完成任务的时间，包括任务执行时间、端到端延迟和等待时间（Chen等人， 2007年）。XðÞÞÞXT. Issac等人/Journal of King Saud University- Computer and Information Sciences 34（2022）3685-37023689为了实现该应用，（ii）提出了一种基于单解的Meta启发式改进的随机位攀登算法（k-MRBC），该算法使用转置算子来逃避局部最优，并提高了逃避局部最优的搜索性能。该工作仅限于考虑任务分配过程中的能耗和应用程序执行时间（make-span）因素。Guo等人（Guo等人，2019）提出了一种用于无线传感器致动器网络（WSAN）的非集中式任务分配算法，称为Min-Actor算法（MIA）。MIA同时解决了网络连接和任务分配问题。第一阶段是MIA构造两跳粗强连通域集（RCDS），通过将网络划分为多个簇来解决网络连通性问题。在构造聚类后，利用规则对RCDS第二阶段涉及实际任务分配过程（MIA-TA），包括两个阶段（i）任务发现和（ii）任务分配阶段。这项工作受到能量水平、执行成本和距离的限制。总之，大多数现有的无线传感器网络任务分配算法选择性地采用异构节点的属性和能力在任务分配过程中。影响HeWSN在任务分配期间，需要算法。3.1. HeWSN中影响任务分配的主要因素HeWSN中的节点有几个因素影响任务分配和讨论的主要因素列举如下。能力（Yu等人，2018; Frank和Omer，2005）：能力是节点成功执行任务的能力。该能力包括感测、计算和通信所感测的数据的能力感知能力：节点上的传感器受到感知限制。理想的传感由节点在其测量范围内执行测量范围由下测量范围（LMR）和上测量范围（UMR）界定，并且满足条件由等式（9）确定，其中LMRi≥LMRTtidUMRTtid ≤UM Ri≤9μm处理能力：处理能力是节点处理数据的能力（Munir等人， 2014年）。通信能力：传感器节点与所需传感器节点的通信能力●剩余能量（Misra和Vaish，2011）：剩余能量REi是以焦耳（J）为单位测量的节点“i”的剩余能量的量子可用性（Mahmud等人，2018）：如果节点准备好在给定实例处执行任务，则该节点被称为可用。Bootstrap time（BT）（Misra and Vaish，2011）：节点的Bootstrap Time（BT）是总的活动持续时间。BT周期是结束时间（ET活动）与 以及所有活动持续时间的开始时间（ST活动 .它在等式（10）中数学地表示，其中TmaxBTid¼ET activev e-ST activeve10分钟第四季等待时间（WT）（Jin等人，2012）：节点的等待时间（WT）是节点成功执行所有'x'个挂起的任务所需的任务执行时间（TET）的总和队列中的任务，以便随后分配该任务。它在等式（11）中表示。XWTid¼TETid;tid11min第四季位置（L）（Issac等人，2019; Frank and Omer，2005）：节点的精确位置是许多WSN应用的重要因素。某些特定位置的任务需要在指定的附近执行。距离（D）（Tkach和Edan，2020）：任务执行节点的任务执行之间的距离起着重要作用。它显著影响整体能耗（EC）、网络寿命（NL）和吞吐量（TH）。距离和上述性能度量之间的关系在以下等式中列举。D/EC2012年D/1=NL130D/1=TH14毫米总结了现有的无线传感器网络任务分配算法，分析了影响任务分配的主要因素。最近的趋势要求无线传感器网络应用程序采用一组异构节点来实现其不同的目标。同时，当代节点可以进行多感知、处理和通信。现有的任务分配算法部分地考虑了HeWSN的属性、功能和能力等因素。这些因素的部分消除会导致绩效的显著恶化和任务截止期错过率的显著上升。为此，需要设计一种新的基于多准则的HeWSN任务分配算法，该算法简单而强大，是动态的，启发式的，并行的和分布式的任务分配算法是必需的.4. 组织P系统启发的动态任务分配算法（tPDTA）4.1. 动机当代WSN应用涉及复合任务或多目标任务（Munir等人，2014;Roozeboom等人，2013年）的报告。目前的无线传感器网络的趋势，导致异构节点的合并。 一个HeWSN模型如图所示。 1，其中节点{N1，N2，.. . ，N13}在感测、处理和能量能力方面不同。与同构WSN任务分配算法不同，异构WSN（HeWSN）算法需要考虑节点的不同属性来进行有效的任务分配。然而，大多数现有的HeWSN算法在建模任务分配算法时没有HeWSN应用需要一种有效的算法来解决分布式环境中的多准则任务分配问题。无线传感器网络中的任务分配问题通常被归类为计算上的NP完全问题，因为每个无线传感器网络都将每个任务视为一组子任务，并且它的一个主要假设是顺序执行。任务分配算法需要找到一种有效的方法来分配任务的节点集。获得最优解的有效方法之一是使用强大的启发式算法（Mezei等人，2013年）的报告。受自然界的启发，人们提出了许多有效的启发式解决方案，以提供一个近似最优的解决方案来解决计算问题●●●●●●ðÞð×ÞðÞð×Þð×Þðð×Þþ ð Þþ ð×ÞÞðþ ð× ÞÞðþ ðþ ÞÞ ð× ðþ þ ÞÞ3690T. Issac等人 /沙特国王大学学报-计算机与信息科学34（2022）3685- 3702Fig. 1. 分布式WSN环境。线性时间中的难题下面列举了最近存在的用于解决WSNi. 蜜蜂群优化（HBCO）（Tkach和Edan，2020）ii. 粒子群优化（PSO）（Yang等人，2014; Issac等人， 2020年）iii. 遗传算法（GA）（Jin等人， 2012年）iv. 蚁群优化（ACO）（Jin等人，（ 2006年）上述软计算算法执行其独特的启发式功能，以帮助在线性时间内找到接近最优的然而，大多数软计算方法需要一组专用的、资源无约束的节点，如在集中式环境中进行有效实现。在异构的无线传感器网络应用中，专用资源独立节点的动态可用性总之，集中式方法存在可扩展性、专用节点要求等问题，这导致下一代WSN应用的主要方向转向分布式系统。大多数现有的任务分配算法已经建模的假设有大量的无线传感器节点在无线传感器网络。下一代无线传感器节点在单个节点中具有多种传感、处理和通信单个节点可以执行多个传统节点的角色（Roozeboom等人，2013;指南，未注明日期。）.下一代多功能节点也被称为宏节点，相对于传统的传感器节点成本更然而，一些宏节点，例如来自libelium的Waspmote，可以有效地替代大量的传感器节点，并且它可以被重新用于不同的WSN应用（Guide，n. d. ）. 由于其数量较少，因此可以精确地此外，采用宏节点而不是普通传统节点具有以下优点集，例如较低的网络带宽、通信和计算成本（Panja等人， 2008年）。使用较少节点的最初提议在（Panja等人，2008年）。对于初步调查，任务分配问题被建模为一个任务被分配给一个单一的宏节点，而不是一组遗留节点。模型化的任务分配问题可以在多项式时间内求解，并通过以下定理证明定理：由多个多功能传感器节点组成的单跳无线传感器网络的任务分配问题可以在多项式时间内求解。证明：一个异构的无线传感器网络有单跳通信之间的节点以及管理器节点假设分布式任务分配通过参与节点之间的协商进行，直到获得最优的任务分配策略。将整个任务分配问题划分为以下子阶段，以计算每个阶段中的个体计算复杂度：(i) 在管理器节点中生成任务：假设管理器节点生成最多“tmax”个假设每个任务都有管理器节点针对每个任务以广播模式向节点发出单独的任务请求（TR）。该阶段的最大计算复杂度将是用于发出最大任务请求的O tmax的(ii) 节点对任务请求的预处理：第二阶段包括每个节点分析任务请求（TR）查询，因为由于异构环境，所有节点可能不满足所有顺序地执行“q”任务标准分析，并且如果过程在任何“q”标准中失败，预处理阶段的最坏情况计算复杂度为O q tmax：(iii) 节点的后处理和任务确认的生成：任务确认由限定预处理阶段的节点生成。该阶段的计算复杂度将是O tmax的量级：所生成的任务分配器（TQ）在其对等体之间广播。(iv) 节点对任务限定符确认的处理：TQ的处理由节点执行，最坏的情况是所有节点交换任务限定符对象，每个节点都在处理它。这个场景的计算复杂度是O nmax tmax。(v) 由管理器节点生成的任务分配确认：具有最高TQ的节点将被管理器节点授予任务，并且如果所有节点都被授予任务，则最坏情况的计算将是O nmax tmax的量级。网络发送TA。该算法在管理器节点上的总复杂度将是O tmaxnmax因此，每个节点的复杂度都是O q。tmax tmax nmaxtmax。管理器和节点的总体计算复杂度为O tmax1的量级nmax和O tmaxq1nmax。算法的计算复杂度表示问题是多项式型问题。因此，它被证明是基于单跳的异构任务分配问题，使用一组多功能的节点可以在多项式时间内解决处理单个任务。组织P系统（TPS）是P系统中的先进计算模型之一，具有简单、动态、启发式的计算能力。它可以很容易地与分布式环境中的节点一起使用，并且能够解决任务分配问题（Liu等人，2015; Song等人，2017;Sosík，2019）。据作者为此，TPS最初建模解决多项式类型的无线传感器网络任务分配问题。4.2. 组织P系统（TPS）第一个TPS由Martã等人在2003年首次提出（Martín-Vide等人，2003年）。TPS模型是基于对细胞的处理.Σ0n002●f×g FGT. Issac等人/Journal of King Saud University- Computer and Information Sciences 34（2022）3685-37023691在下面的部分中详细描述了网格单元和过程之间的lular对象。据作者所知 ， 我 们 是 第 一 个 模 型 的 组 织 P 系 统 来 解 决 分 布 式H e W S N 的 任 务 分 配 问 题 。TPS由一组单元、其分子对象和规则组成。TPS由一组表示细胞和分子对象的符号和符号表示。目前，TPS的建模，以解决无线传感器网络的任务分配问题，采用一组符号和符号表示的细胞和分子对象的规则。4.2.1. 细胞TPS中的单元代表环境中的单个计算单元。无线传感器网络中的每个计算参与者，包括节点、网关都被看作是一个单元。单元格由符号[nid]nid表示，其中当参与者由于能量耗尽或被认为不适合操作而停止生活时，细胞也通过溶解细胞而停止存在。图2描绘了包括“nmax”个节点的所提出的分布式架构节点协同制作它是一个单一的组织。4.2.2. 分子物体将节点的属性和通信消息作为分子对象，放置在相应的参与者单元中。活组织由细胞组成，每个细胞都由膜和细胞物体包围。 表4中列出了用于WSN的TPS中的对象及其符号。表4符号描述表。符号对象描述传感器属性对象LMRi;j节点“j”中传感器“i”的下限测量范围节点“j”中传感器“i”的上限测量范围为A C i ; j节点“j”中传感器“i”的精度SPNi;j节点'j'中传感器'i'的精度S R T i ; j节点'j'节点“j”中第i个传感器的传感器类型通信消息对象任务“l”的CSlTAj;l节点'j'的 任务分配对象，用于任务'l'。TCj;l由管理器节点发出的任务“l”的节点“j”的任务分配确认对象。任务描述对象其中e0l0;是任务标识符，并且0l0;2f1;2：：zgTQ j;l是任务“l”的节点“j”的任务限定符对象。TR1任务分配请求对象，0l0;是任务标识符，0l0 2 f 1; 2：： zgTT任务令牌对象用作TDobject.TTLx;y'x'对象的生存时间，其中x2 fCk;Njg;其中k2 1≤p; j2 1≤ n;以及消息类型其中y2 fTRg表5进化进化规则-概述。规则类型操作约束通信规则<$ia;out]i<$ia;in]i●fag2V进化法则！½ia0]i●fa;a0g2V4.2.3. 规则这些规则确定了组织P系统（TPS）的核心功能。该规则的核心操作是基于分子对象的存在或不存在。一个活动或一组活动基于分子对象发生，并由规则定义进化通信规则同端口规则半个！Σ]iΣa0]i反港规则我的天！半个b0]i 半个a0]j● 1≤ i≤nmax● 1≤ j≤nmax● I●a;a2V● 1≤ i≤nmax● 1≤ j≤nmax这些规则被分类为细胞内或细胞间。细胞内的操作涉及分子物体从一种状态到另一种状态的进化。细胞间规则使用囊泡执行分子对象到其他细胞的运输。细胞中囊泡的数量与细胞中的节点数量成正比，4.3. 建模tPDTA● I●a;a0;b;b02伏;在通信范围内。所提出的基于TPS的任务分配利用经典通信和进化规则以及Song等人提出的进化通信规则的组合（Song等人，2017年）。表5列出了工作中使用的各种规则以及示例。通信规则涉及分子对象被吸收在细胞内（内）或发送到细胞外（外）。演化规则导致细胞内分子对象的演化。表5中描述了一个例子，其中当前状态下的分子对象在细胞内。进化的通讯规则涉及一个物体同时进化和转移到另一个细胞。它大致分为（i）同港规则和（ii）反港规则。同端口模式允许分子对象的进化和单向转移，而反端口涉及分子（a;b）在各种细胞中的同时进化和分子对象的双向转移图二. tPDTA系统结构。符号0P0表示该系统中组件的整体集合基于SueP系统的分布式任务分配算法（tPDTA），它由以下表达式表示PV;l1;· ··;lnmax;syn;iout=15mm其中：符号“V 0”是TPS中所有标识符的集合，● 符号l1;· ··;lnmax表示参与的HeWSN中的小区节点。● liii;wi;0;Ri i其中：其中Ui是节点“i”的标签标识符及其属性。wi;02Ui是属性的初始多集，单元格'i'中的消息Ri是规则的有限集合。syn1; 2;：：;nmax1; 2;：：;nmax表示小区之间的通信● ioutf 1; 2;：：;nmaxg表示需要结果的最终节点。4.3.1. 建模规则在HeWSN中解决任务分配问题的规则在表6中列举。规则R1、R2、R7和R9属于●O..ΣΣ.ΣJ;;;j;lg¼1gWTG小行星3692 Issac等人 /沙特国王大学学报-计算机与信息科学34（2022）3685- 3702规则R5和R6是通信规则，其余规则都是在进化规则下建模的。这些规则允许以非确定性的并行方式执行.4.3.2. 工作流整个任务分配工作流程如图3所示。具有最高能量的节点被指定为管理器节点（Nmgr）：它有助于（i）发起任务分配的过程和（ii）确认对节点的任务分配。在生成任务描述（TD）对象时，使用R2将TD最大化地分配给参与节点，以生成特定于节点的任务请求（TR）对象。使用规则R3，在满足条件时为TR对象生成条件满足（CS）对象.如果满足所有使用规则R6接收TQ的节点使用规则R7保留最大TQ值。在超时周期之后，保留其原始TQ的节点将通过使用R8向管理器节点发送任务分配（TA）对象的副本来满足任务分配。管理器节点分配任务的最佳节点使用任务确认（TC）对象表示任务分配使用R9。5. 实验分析和结果：针对分布式异构无线传感器网络（HeWSN）中的任务分配问题，提出了组织P系统分布式任务分配（tPDTA）算法。所提出的算法以及最近的任务分配算法的实验建模已经在下面讨论。5.1. 模拟算法实验分析分两个阶段进行：（一）自我评价和（二）基准评价。5.1.1. 自我评价自我评估阶段变体基于以下要求建模：（i）能量约束WSN