一种面向工业污染排放监测的移动边缘计算资源分配方法

摘要

本发明提供一种面向工业污染排放监测的移动边缘计算资源分配方法，涉及无线通信技术领域，所述分配方法包括如下步骤：S1、采集工业物联网在监测工厂各种污染物排放时产生的有毒气体的信息，得到有毒气体数据，根据得到的有毒气体数据，使产生代价最大的气体得到较高的优先级，进而得到面向工业污染物排放监测的移动边缘计算系统的基本框架；S2、根据所述移动边缘计算系统结构的基本框架，对移动边缘计算资源分配进行数学建模，得到移动边缘计算资源分配数学模型；S3、对S2所得到的移动边缘计算资源分配数学模型进行求解。本发明部署了多种传感器及移动边缘计算系统，通过系统对传感器收集的具有优先级的数据进行处理大幅度提升了算法搜索效率。

说明书

技术领域

本发明涉及无线通信技术领域，尤其涉及一种面向工业污染排放监测的移动边缘计算资源分配方法。

背景技术

工业生产过程中超标排放的污染物会严重危害附近居民的人身安全，同时会对环境产生不可逆的严重后果或者产生巨大的经济损失，因此合理监测工业污染物排放在环境保护、安全生产及保护人民财产安全方面显得尤为重要。

传统污染物排放的监测主要依赖人工收取的污染物排放数据，然而这样的方式不仅效率低而且损害工人的身体健康，因此越来越多的工厂采用部署工业物联网的方式，通过部署不同类型的传感器收集数据，回传给移动数据中心处理后得到排放污染物的监测结果。然而，由于硬件设备条件的约束，导致其在处理大量计算业务时有较高的计算时延并且加速电池的能量消耗，降低用户的体验质量。因此，仅凭借移动端设备无法满足全部的污染物排放监测数据的处理。云计算的蓬勃发展给工业物联网获取的数据提供了新的处理方式，云处理器强大的数据处理性能使得数据处理耗时短，效率高。然而，将移动端需要进行计算的任务部署至云服务器虽然解决了因移动设备计算资源有限导致计算时延过高的问题，但是传输至距移动端较远的云服务器进行计算会面临网络负荷和通信链路传输时延增加以及通信链路带宽有限的问题。因此，如何合理的进行资源分配，即分配相应的任务到移动端及云端处理器，保证监测数据处理结果的实时性显得尤为重要。现存的资源分配问题多数以时效性为评价指标，资源分配方案中并未充分考虑被处理任务的优先级。综上所述，有待发明一种能充分考虑被处理任务的优先级的计算资源分配方法。

发明内容

本发明提供一种面向工业污染排放监测的移动边缘计算资源分配方法，解决了现有计算资源分配方法未充分考虑被处理任务的优先级的问题。

为达到以上目的，本发明采取的技术方案是：

一种面向工业污染排放监测的移动边缘计算资源分配方法，所述分配方法包括如下步骤：

S1、采集工业物联网在监测工厂各种污染物排放时产生的有毒气体的信息，得到有毒气体数据，根据得到的有毒气体数据，赋予每种气体以优先级，使产生代价最大的气体得到较高的优先级，进而得到面向工业污染物排放监测的移动边缘计算系统的基本框架；

S2、根据所述移动边缘计算系统结构的基本框架，对移动边缘计算资源分配进行数学建模，得到移动边缘计算资源分配数学模型；

S3、对S2所得到的移动边缘计算资源分配数学模型进行求解，获得移动边缘计算资源分配方案，根据该方案分配资源。

优选地，S3所述移动边缘计算资源分配方法包括：

S31、通过基于优先级与整数与小数混合的编码方法，根据S1确立的优先级将任务排序子问题和计算资源选择子问题编码；

S32、使用基于有向无环图的解码方法在每个任务之间的优先权级别限制下得到任务排序子问题以及计算资源分配子问题的可行解，进行解码，得到具体的任务排序策略和计算资源分配策略；

S33、对S32得到的具体的任务排序策略和计算资源分配策略进行适应度的计算、比较，用以进行资源分配策略评估；

S34、使用一种类差分的基于马尔科夫网的分组策略根据关联关系进行决策变量划分，包括结构学习和参数学习；

S35、对S34中的优良个体进行保留，采用新的种群更新策略作为下一次迭代的开始，循环S31～S35，直至算法收敛到预设阈值，或者达到最大迭代次数。

优选地，根据S34所述的结构学习来将决策变量/节点划分为父节点或子节点；划分父子节点需要评价每个节点之间的关联关系，节点关联关系的评估函数如下：

其中：U表示解的数量；w表示结构学习的归一化因子；

Ls(Y

优选地，S34所述参数学习中节点的联合概率密度公式为：

其中：Z表示参数学习的归一化因子；Ψ

优选地，S35所述更新策略中的更新公式为：

y

其中：C(1)表示柯西分布、p

优选地，S1中所述工厂各种污染物排放时产生的信息包括有毒气体的种类信息、排放数量信息、有毒气体泄漏位置信息。

优选地，S1中面向工业污染物排放监测的移动边缘计算系统的基本框架包括工业物联网区域、基站、边缘计算节点和云计算节点。

本发明的有益效果在于：

本发明部署了多种传感器及移动边缘计算系统，通过系统对传感器收集的具有优先级的数据进行处理，对于需要低时延处理的任务予以及时响应；

本发明通过在协同演化算法中引入基于马尔科夫网的分组策略，使分组的依据更清晰，分组效果更好；

本发明通过在解码过程中引入基于有向无环图的解码方法，充分考虑同一个区域内监测任务之间的优先级约束，保证所得到的资源分配方案均为可行解，大幅度提升了算法搜索效率；

本发明通过在领域中选择最优的个体，通过邻域最优个体改写传统的协同粒子群算法的更新策略，有效防止算法过早收敛于局部最优，增加算法的寻优能力。

附图说明

为了更清楚的说明本发明的实施例或现有技术的技术方案，下面将对实施例或现有技术描述中所需要使用的附图做一简单地介绍，显而易见地，下面描述中的附图仅仅是本发明的一些实施例，对于本领域普通技术人员来讲，在不付出创造性劳动的前提下，还可以根据这些附图获得其他的附图。

图1为本发明步骤图。

图2为本发明方法流程图。

图3为本发明基于有向无环图的解码示意图。

具体实施方式

需要说明的是，在不冲突的情况下，本发明中的实施例及实施例中的特征可以相互组合。下面将参考附图并结合实施例来详细说明本发明。

为使本发明实施例的目的、技术方案和优点更加清楚，下面将结合本发明实施例中的附图，对本发明实施例中的技术方案进行清楚、完整地描述，显然，所描述的实施例仅仅是本发明一部分实施例，而不是全部的实施例。以下对至少一个示例性实施例的描述实际上仅仅是说明性的，决不作为对本发明及其应用或使用的任何限制。基于本发明中的实施例，本领域普通技术人员在没有做出创造性劳动前提下所获得的所有其他实施例，都属于本发明保护的范围。

需要注意的是，这里所使用的术语仅是为了描述具体实施方式，而非意图限制根据本发明的示例性实施方式。如在这里所使用的，除非上下文另外明确指出，否则单数形式也意图包括复数形式，此外，还应当理解的是，当在本说明书中使用术语“包含”和/或“包括”时，其指明存在特征、步骤、操作、器件、组件和/或它们的组合。

除非另外具体说明，否则在这些实施例中阐述的部件和步骤的相对布置、数字表达式和数值不限制本发明的范围。同时，应当清楚，为了便于描述，附图中所示出的各个部分的尺寸并不是按照实际的比例关系绘制的。对于相关领域普通技术人员己知的技术、方法和设备可能不作详细讨论，但在适当情况下，所述技术、方法和设备应当被视为授权说明书的一部分。在这里示出和讨论的所有示例中，任何具体值应被解释为仅仅是示例性的，而不是作为限制。因此，示例性实施例的其它示例可以具有不同的值。应注意到：相似的标号和字母在下面的附图中表示类似项，因此，一旦某一项在一个附图中被定义，则在随后的附图中不需要对其进行进一步讨论。

在本发明的描述中，需要理解的是，方位词如“前、后、上、下、左、右”、“横向、竖向、垂直、水平”和“顶、底”等所指示的方位或位置关系通常是基于附图所示的方位或位置关系，仅是为了便于描述本发明和简化描述，在未作相反说明的情况下，这些方位词并不指示和暗示所指的装置或元件必须具有特定的方位或者以特定的方位构造和操作，因此不能理解为对本发明保护范围的限制：方位词“内、外”是指相对于各部件本身的轮廓的内外。

为了便于描述，在这里可以使用空间相对术语，如“在……之上”、“在……上方”、“在……上表面”、“上面的”等，用来描述如在图中所示的一个器件或特征与其他器件或特征的空间位置关系。应当理解的是，空间相对术语旨在包含除了器件在图中所描述的方位之外的在使用或操作中的不同方位。例如，如果附图中的器件被倒置，则描述为“在其他器件或构造上方”或“在其他器件或构造之上”的器件之后将被定位为“在其他器件或构造下方”或“在其位器件或构造之下”。因而，示例性术语“在……上方”可以包括“在……上方”和“在……下方”两种方位。该器件也可以其他不同方式定位(旋转90度或处于其他方位)，并且对这里所使用的空间相对描述作出相应解释。

此外，需要说明的是，使用“第一”、“第二”等词语来限定零部件，仅仅是为了便于对相应零部件进行区别，如没有另行声明，上述词语并没有特殊含义，因此不能理解为对本发明保护范围的限制。

本发明提供一种技术方案：一种面向工业污染排放监测的移动边缘计算资源分配方法，其步骤如图1所示，流程图如图2所示，所述分配方法包括如下步骤：

S1、通过对工业习惯以及工业产品的生产流程研究分析，搭建出面向工业污染物排放监测的移动边缘计算系统结构。工业物联网在监测工厂各种污染物排放时产生了多种多样需要被处理的数据，本发明对隶属于同一工业物联网区域内的每种污染物排放监测的顺序赋予了优先级，得到了系统基本框架。本系统中共包含四个部分，分别是：工业物联网区域，基站，边缘计算节点及云计算节点。

S2：根据S1得到的结构以及真实环境中所遇到的问题，对问题场景进行数学建模。

S21：移动边缘计算资源分配可建模为一个离散优化问题，具体可建模为一个0-1混合整型规划问题，包括任务序列和资源分配两个子问题。该系统的任务是将传感器采集到的数据由边缘计算节点或云计算节点，任务序列是根据任务的优先级对所有任务进行排序，资源分配则为排序任务选择合适的候选计算资源，本问题的目标函数设定为最小化所有任务最大响应时间。

S22：本问题模型需要考虑的约束包括：首先，每个任务都有一个候选计算资源集合，每个任务都仅可以由给定计算资源集合中的任意一个可用计算资源进行处理。然后，属于同一工业物联网的任务之间存在优先级约束，属于不同工业物联网的任务之间没有明确的优先级约束。其次，利用任意计算资源完成每一项任务的过程不可中断。最后，每种计算资源一次只能处理一个任务且每个任务只能被处理一次，不重复处理。

S3：算法设计：为了保证污染物排放监测结果的实时性，需合理地分配计算资源，本发明针对问题场景，提出了一种嵌入马尔科夫网协同演化的移动边缘计算资源分配方法(MarkovNetworkbased CooperativeEvolutionaryAlgorithm,MNCEA)，在种群的初始化、编解码、评估策略、分组策略以及更新策略等方面进行设计和优化。本发明方法流程图如图2所示，具体步骤如下：

S31编码机制：本方法提出一种基于优先级编码方法，编码值由保存两位小数的实数构成，其中整数部分从[1,m]中随机产生，m代表当前任务可用的计算资源个数，小数部分从[0,1]中随机产生。显而易见，该编码的小数部分代表了任务排序子问题，整数部分代表了当前任务的计算资源选择子问题。

S32解码机制：如S31所述，小数部分越大，代表该任务在整个系统中优先权越高，也需要被越早执行，整数部分则代表了所选择的计算资源下标。在决定任务排序时，需要充分考虑隶属于同一个工业物联网区域内的优先级约束，因此本方法使用基于有向无环图的解码方法，充分考虑任务之中的优先权限制，从而使解码后任务排序都是可行的，提高资源分配方法效率。基于有向无环图的解码方法如图3所示，具体步骤如下：首先设置候选集合及任务集合，初始状态时两个集合均为空集。首先将每个工业物联网区域内优先级最高的任务放到候选集合中，比较候选集合中任务的优先级，选出具有最高优先级的任务放到任务集合，并同时将与该任务隶属于同一工业物联网区域内的优先级次高的任务放到候选集合中，继续比较集合内任务的优先级，仍然选择优先级最高的任务放入任务集合中，重复上述过程直至候选集合为空集。

S33资源分配策略评估：根据编码的整数部分为排序后的任务分配计算资源，并将任务排序结果和资源分配结果相结合，得到执行全部污染物排放监测数据处理的完成时间，进而通过监测完成的总时间来评估解的优劣。

S34基于马尔科夫网的分组策略：决策变量划分会很大程度决定演化算法的性能，基于马尔科夫网的分组策略能够充分考虑决策变量潜在的关联关系，并根据关联关系进行决策变量划分，可以提高本发明方法找到最优移动边缘计算资源分配的效率。传统马尔科夫网结构学习方法复杂度高、时间成本高，不适用于对实时性要求较高的工业污染物排放监测场景，因此，本发明提出了一种类差分的马尔科夫网络结构方法，过程包括：结构学习和参数学习。

S341结构学习：网络结构的组成部分包括了节点和边，尽管马尔科夫网的边并不存在方向，但是我们仍然可以根据节点出现的顺序将节点划分父节点集合和子节点集合，本方法中决策变量即为节点。首先通过预处理获取一定数量的资源分配方案并获取其中的关键路径(决定资源分配方案最终完成时间的路径)。首先，通过统计预处理过程中节点出现在关键路径上的频率获得父节点集合，未划分为父节点的即划分到子节点集合中。然后，定义考虑决策变量潜在关联关系的评估函数，其目的为关联子节点与父节点，若关联的依据为评估函数值，子节点将与具有评估函数较大值的父节点关联。评估函数如公式(1)所示：

其中：U表示解的数量；w表示结构学习的归一化因子；Ls(Y

S342参数学习：通过S341获取网络结构后，需要进行参数学习。本方法使用基于最大团得到的多元势函数进行马尔科夫网的参数学习。由最大团分解和联合概率公式，可以得到决策变量的联合概率密度函数。由联合概率密度函数可以得到每一个决策变量的边缘概率密度(将每个父节点认为是一个边缘)，根据每个决策变量的边缘概率决定每个子节点归属于哪一个唯一父节点。联合概率密度公式为：

其中：Z表示参数学习的归一化因子；Ψ

S35更新策略：MNCEA采用协同粒子群算法作为基础协同演化算法，为了避免资源分配策略搜索过程陷入局部最优值，本发明改写了传统粒子群算法的粒子更新策略，引入了邻域最优值强化了最优资源分配策略的搜索方向，考虑邻域最优值的更新公式如公式(3)所示：

y

其中，C(1)表示柯西分布，其目的为防止算法过早收敛。p

实施例

针对现有移动边缘计算资源分配方法中未充分考虑任务的优先级约束，本发明提出了一种嵌入马尔科夫网协同演化的移动边缘计算资源分配方法，通过部署工业物联网及多种传感器获得的数据信息经过移动边缘计算系统处理，对信息的紧急程度进行分析，再由工业物联网系统决定是否要发出工业污染物排放超标警告，保证了监测结果的实时性，进而保证了周围环境、居民安全及避免造成重大经济损失。

本实测示例分别在两种不同规模的数据集上对发明方法进行了实测，数据集规模分别为常规规模：任务数量涵盖55-200个及大规模：任务数量涵盖200-300。通过设计实验，将MNCEA与现存主流算法进行对比，分别从与单个代理算法(HGA、HPSO、HDE)对比、与多个代理算法(CCGP、CCGA、MAPSO)对比以及与不同分组策略(Fixed、Random、DG)对比三个方面分析，并在常规数据集和大规模数据集上进行仿真实验，验证本发明方法的性能与优势，以及优势体现的原因。表1-表6分别展示了上述三类实测的结果，表中的*表示得到了较好解，可以看出本发明方法在两种数据集上均优于或与对比方法性能持平，在分组策略性能比较的实验中，可以看出本发明方法中的基于马尔科夫网的分组策略显著优于对比分组策略，这是因为本方法提出的分组策略在马尔科夫网的构建过程中充分的考虑了决策变量之间的关联关系，使得在有工业污染物排放监测过程中资源分配策略的寻优能力更强，效率更高，进而可以保证工业污染物排放监测结果的反馈更加及时。

表1：常规规模数据集上与单代理算法对比有效性验证

表2：常规规模数据集上与多代理算法对比有效性验证

表3：常规规规模数据集上与分组算法对比有效性验证

表4：大规规模数据集上与单代理算法对比有效性验证

表5：大规规模数据集上与多代理算法对比有效性验证

表6：大规规模数据集上与分组算法对比有效性验证

以上所述，仅为本发明较佳的具体实施方式，但本发明的保护范围并不局限于此，任何熟悉本技术领域的技术人员在本发明揭露的技术范围内，根据本发明的技术方案及其发明构思加以等同替换或改变，都应涵盖在本发明的保护范围之内。