一种基于物联网的分布式节点资源优化方法

摘要

本发明公开了一种基于物联网的分布式节点资源优化方法，包括如下步骤：步骤一、构建多目标优化模型；步骤二、采用基于NSGA‑III的物联网分布式节点资源优化策略求解算法进行求解多目标优化模型，得到最优策略；步骤三、采用最优策略对任务进行处理；步骤四、更新物联网中中心节点信息、边缘节点信息、任务需求信息；步骤五、根据更后的新物联网中中心节点信息、边缘节点信息、任务需求信息，重复步骤二继续执行。本发明通过对物联网节点任务的分配优化有效降低了边缘节点计算资源消耗总量、边缘节点存储资源消耗总量、边缘节点能源消耗总量、数据传输总量的总体资源消耗，达到了较优的资源利用率。

权利要求

1.一种基于物联网的分布式节点资源优化方法，其特征在于，包括如下步骤：步骤一、构建多目标优化模型，描述物联网中的中心节点信息、边缘节点信息和任务需求信息；其中每个任务都产生在边缘节点上；在边缘节点计算完成后的所有任务，都将计算结果传输至中心节点；

多目标优化模型如下所示：

其中 ， 为多目标 优化模型的目标 函数 ；min 表示取最小值 ；

 表示任务运行策略；

，

N表示中心节点数量，M表示边缘节点的数量，K表示任务的数量；

其中， 表示第i个任务的执行节点编号，是一个介于1至 的整数；当，说明第i个任务在中心节点 中执行；当 时，说明第i个任务在边缘节点 中执行；

表示边缘节点计算资源消耗总量， 表示边缘节点的存储资源消耗总量； 表示边缘节点能源消耗总量； 表示数据传输总量；

其中，M表示边缘节点的数量，K表示任务的数量，  表示执行第i个任务需要耗费的计算资源， 表示第j个任务的执行节点编号；

其中， 表示执行第i个任务需要耗费的存储资源；

表示执行第i个任务需要耗费的能量资源；

其中， 为系数； 表示第i个任务产生时所属的任务节点； 为一个常数系数； 表示两个节点之间的通信距离， 表示传输第i个任务时使用的通信资源；表示并集；

步骤二、求解多目标优化模型，得到最优策略；

步骤三、采用最优策略对任务进行处理；

步骤四、更新物联网中中心节点信息、边缘节点信息、任务需求信息；

步骤五、根据更后的新物联网中中心节点信息、边缘节点信息、任务需求信息，重复步骤二继续执行。

2.如权利要求1所述的基于物联网的分布式节点资源优化方法，其特征在于，所述任务需求信息即物联网数据处理任务的集合。

3.如权利要求1所述的基于物联网的分布式节点资源优化方法，其特征在于，所述中心节点信息包括中心节点的计算资源信息、存储资源信息、通信带宽信息和位置；所述边缘节点信息包括边缘节点的计算资源信息、存储资源信息、通信带宽信息和位置。

4.如权利要求1所述的基于物联网的分布式节点资源优化方法，其特征在于，所述 为

0到1之间的有理数。

5.如权利要求1所述的基于物联网的分布式节点资源优化方法，其特征在于，所述步骤二中，采用基于NSGA‑III的物联网分布式节点资源优化策略求解算法求解多目标优化模型，得到最优策略。

说明书

一种基于物联网的分布式节点资源优化方法

技术领域

[0001] 本发明涉及数据处理领域，特别涉及一种基于物联网的分布式节点资源优化方法。

背景技术

[0002] 物联网条件下，尤其是针对边缘计算场景，除了中心节点具备较强的计算和存储能力，其它每个边缘节点都具备一定的服务能力，包含有限的计算、存储和网络资源。这样中心节点和边缘节点一起组成了一个基于物联网的边缘计算分布式环境。

[0003] 基于物联网的边缘计算是一个典型的分布式环境，存在大量的应用任务，需要消耗一定的计算、存储和网络资源，充分利用好基于物联网的边缘计算分布式环境，完成这些任务主要存在以下问题，首先是每个边缘节点的资源不同，有的边缘节点能力强，而更多的边缘节点能力相对较弱，当任务来临时，如果全部按照最近节点来完成，必然会导致该节点无法完成相应任务，从而导致全局节点任务完成时间滞后，而如果按照能力强弱划分，那些离任务节点较远的、任务处理能力较强的任务往往需要较大的通信开销，也会导致全局节点任务完成时间滞后，因此，需要构建一种基于物联网的分布式节点资源优化方法，同时考虑边缘节点在分布式条件下任务能力（计算能力、存储能力、通信能力）、任务请求距离等因素，在完成任务的约束下，达到计算资源利用率、存储利用率、通信资源消耗率和任务完成时间达到综合最优。

[0004] NSGA‑III：即第三代基于参考点的非支配遗传算法，用于解决高维目标以及前沿解集均匀分布问题，避免所获得解集局部最优。

发明内容

[0005] 本发明的目的是克服现有技术的不足之外，本发明公开了一种基于物联网的分布式节点资源优化方法。

[0006] 为实现上述目的，本发明采用的技术方案如下：

[0007] 一种基于物联网的分布式节点资源优化方法，包括如下步骤：

[0008] 步骤一、构建多目标优化模型，描述物联网中的中心节点信息、边缘节点信息和任务需求信息；其中每个任务都产生在边缘节点上；在边缘节点计算完成后的所有任务都将计算结果传输至中心节点；

[0009] 多目标优化模型如下所示：

[0010]

[0011] 其中， 为多目标优化模型的目标函数；min（）表示取最小值； 表示任务运行策略；

[0012]

[0013]

[0014] N表示中心节点数量，M表示边缘节点的数量，K表示任务的数量；

[0015] 其中， 表示第i个任务的执行节点编号，是一个介于1至N+M的整数；当，说明第i个任务在中心节点 中执行；当 时，说明第i个任务在边缘节点 中执行；

[0016] 表示边缘节点计算资源消耗总量， 表示边缘节点的存储资源消耗总量； 表示边缘节点能源消耗总量； 表示数据传输总量；

[0017] 步骤二、求解多目标优化模型，得到最优策略；

[0018] 步骤三、采用最优策略对任务进行处理；

[0019] 步骤四、更新物联网中中心节点信息、边缘节点信息、任务需求信息；

[0020] 步骤五、根据更后的新物联网中中心节点信息、边缘节点信息、任务需求信息，重复步骤二继续执行。

[0021] 进一步的改进，所述任务需求信息即物联网数据处理任务的集合。

[0022] 进一步的改进，所述中心节点信息包括中心节点的计算资源信息、存储资源信息、通信带宽信息和位置；所述边缘节点信息包括边缘节点的计算资源信息、存储资源信息、通信带宽信息和位置。

[0023] 进一步的改进， ，其中

[0024] 其中，M表示边缘节点的数量，K表示任务的数量,  表示执行第i个任务需要耗费的计算资源， 表示第j个任务的执行节点编号；

[0025] 其中

[0026] 其中， 表示执行第i个任务需要耗费的存储资源；

[0027] 其中

[0028] 表示执行第i个任务需要耗费的能量资源；

[0029]

[0030]

[0031] 其中， 为系数； 表示第i个任务产生时所属的任务节点； 为一个常数系数； 表示两个节点之间的通信距离， 表示传输第i个任务时使用的通信资源；表示并集。

[0032] 进一步的改进，所述 为0到1之间的有理数。

[0033] 进一步的改进，所述步骤二中，采用基于NSGA‑III的物联网分布式节点资源优化策略求解算法求解多目标优化模型，得到最优策略。

[0034] 本发明优点：

[0035] 1、构建了一种基于物联网的分布式节点优化模型。通过形式化定义方式对非典型场景下的物联网节点进行建模，包括边缘节点、中心节点及任务运行策略。首次用数学方式描述了在边缘节点产生任务、综合调度中心节点和边缘节点资源运行完成任务的非典型物联网场景下的模型问题。

[0036] 2、与传统的物联网节点能耗优化模型不同的是，本发明首次综合考虑了中心节点和边缘节点的计算、存储和通信带宽问题的综合优化。传统的物联网节点优化往往只考虑传感器的剩余能量，而没有考虑传感器执行任务时的计算能力、存储能力和通信能力。当边缘节点数据处理任务发生时，如果计算、存储和通信能力有限，则无法完成任务，造成物理网的失效。本发明专利要综合考虑传感器节点能源、通信、计算、存储等因素，对传感器网络中的分布式节点任务执行策略进行求解，有选择的进行任务计算和传输，从而能够提高能源、通信、计算、存储的效率，增加网络寿命。

[0037] 3、不同于单一优化目标问题，本发明中将基于物理网的分布式节点资源优化问题建模成为了一个多目标优化问题，并引入了一种NSGA‑III多目标优化求解方法，使得多个因素（能源、通信、计算、存储等）在分布式节点优化时同时达到最优。

附图说明

[0038] 图1为本发明的整体流程示意图；

[0039] 图2为基于NSGA‑III的物联网分布式节点资源优化策略求解算法进行求解的流程示意图。

具体实施方式

[0040] 1 典型的物联网面临的问题：

[0041] 一个典型的物联网边缘分布式节点包含多个中心节点，具备较强的计算和存储能力。在每个中心节点附近，存在一部分边缘节点，每个边缘节点的计算与存储能力、网络带宽都有一定的限制。当边缘节点数据处理任务发生时，如果计算存储能力有限，需要上传到中心节点或者就近的其它边缘节点进行数据处理，而考虑到边缘节点本身存在通信带宽的限制，无法将所有任务都进行传输，而是要综合考虑通信、计算、存储等因素进行有选择的任务计算和传输。于是就存在一个需要解决的分布式资源节点多目标优化问题。

[0042] 2 问题定义与描述：

[0043] 首先给出如下定义，

[0044] 定义1:中心节点（Center Nodes，CN）。中心节点是物联网的中央处理节点，一般指包含较多计算、存储和通信资源的中心节点。

[0045] 假设一个物联网中存在N个中心节点 每个中心节点包含四类信息：计算资源信息、存储资源信息、通信带宽信息和位置，
其中
表示第i个中心节点包含的计算资源信息， 表示第i个中心节点包含的
存储资源信息， 表示第i个中心节点包含的通信资源信息， 表
示数据输出通信资源信息， 表示数据输入通信资源信息， 表示第
i个中心节点的位置信息， 表示纬度， 表示经度。为了便于模型的计算求解，这里的计算、存储、通信全部归一量化为标准范围实数值。

[0046] 定义2：边缘节点（Edge Nodes）。指物联网中处于边缘的计算和存储节点，一般包含较少的计算、存储和通信资源。

[0047] 边缘节点在物联网中一般指末端的传感器，虽然有一定的计算和处理能力，但是非常有限，可以处理一些简单的数据采集、分析任务，但是要尽可能的避免大量的数据读取操作，即使边缘节点产生了任务，在通信条件和时间约束允许的条件下，也需要尽可能的将这些任务转移到中心节点去进行计算。

[0048] 假设一个物联网中存在M个边缘节点 与中心节点类似，边缘节点同样包含了计算资源信息、存储资源信息、通信带宽信息和位置四类信息，同时，与中心节点不同的是，由于边缘节点一般部署在较为边缘的地方，采用的供电机制是电池，因此需要充分考虑其能源的利用情况，即总电量，因此边缘节点模型为：

[0049]

[0050] 其中 表示第i个边缘节点包含的计算资源信息， 表示第i个边缘节点包含的存储资源信息， 表示第i个中心节点包含的通信资源信
息， 表示数据输出通信资源信息， 表示数据输入通信资源信息，
表示第i个边缘节点的位置信息， 表示纬度， 表示经度。
代表边缘节点具备的能力信息。同样的，为了便于模型的计算求解，这里的计算、存储、通信以及能量都全部归一量化为标准范围实数值。

[0051] 定义3：物联网数据处理任务集合（Data Tasks，DT）。本文的物联网数据处理任务集合是指在某一个物联网运行过程中需要对数据进行处理的所有任务集合。

[0052] 其符号化描述如下：

[0053] 表示一个任务集合中K个相互独立的任务，每个任务完成需要耗费一定的存储、计算资源、能量，而将任务计算结果传输出去也需要耗费一定的通信资源。其中，
其中 表示执行第i个任务需要
耗费的计算资源 存储资源 能量资源 以及传输该
任务需要的通信资源 表示该任务产生时所属的任务节点，

[0054] 定义4：边缘任务运行策略。为了完成边缘计算中产生的任务，所采用的不同中心节点和边缘节点进行任务处理的方法称为边缘任务运行策略。

[0055] 边缘任务运行策略的数学定义如下：

[0056] 对于空间中存在的物联网，存在N个中心节点 M个边缘节点在某个特定时刻存在K个相互独立的任务 其
任务运行策略用 表示，其数学表达式如下：

[0057]

[0058]

[0059] 其中， 表示第i个任务的执行节点情况，需要说明的是， 是一个介于1至N+M的整数，用来表示该任务在哪个节点执行，本文中，当 ，说明该任务在中心节点中 执行；当 时，说明该任务在边缘节点 中执行。

[0060] 基于以上问题描述，该问题的多目标优化模型为：

[0061]

[0062] 其中 为该模型的目标函数。分布式节点资源优化均衡模型一共有4个目标函数，边缘节点计算资源消耗总量、边缘节点存储资源消耗总量、边缘节点能源消耗总量、数据传输总量。

[0063] （1）目标函数

[0064] 第一个目标函数是边缘节点计算资源消耗总量，由于主要考虑边缘节点的消耗情况，因此对于M个边缘节点 在任务执行策略下，边缘节点的计算资源消耗总量记为 。

[0065] ，其中

[0066] 第二个目标函数是边缘节点的存储资源消耗总量，记为 。与计算资源消耗总量类似, 因此对于M个边缘节点 在任务执行策略下，边缘节点的计算资源消耗总量。

[0067] 其中

[0068] 第三个目标函数是边缘节点能源消耗总量  ，

[0069] ，其中

[0070] 第四个目标函数是数据传输总量，记为 ，存在以下几个前提：

[0071] （1）由于每个任务的产生都是在边缘节点上的，因此如果该任务不在其产生的边缘节点上运行，将会产生任务的数据传出通信开销。

[0072] （2）在边缘节点计算完成后的所有任务，都需要将计算结果传输至中心节点，因此必然会产生任务结束后的数据传输通信开销。相对与任务本身所需要的数据而言，由于每次任务完成以后产生的结果数据一般比较小，并且每个任务的计算结果产生的数据量一致，因此本项目统一认定为一次任务完成以后的结果数据开销为一个常数。

[0073] （3）在中心节点计算的所有任务，带宽一般比较充足，因此不考虑其数据的输出通信开销。

[0074] 基于以上几点基本考虑，对数据传输总量目标函数定义如下：

[0075]

[0076]

[0077] 其中， 为两个节点之间的通信距离， 为系数，表示当边缘节点需要将任务传输到其它节点进行计算时跟距离相关的系数，一般定义为系数为正比例函数，表示距离越远，通信传输代价越大。

[0078] 综上，基于物联网的分布式节点优化问题模型建立如下：

[0079] 对于空间中存在的物联网，存在N个中心节点 M个边缘节点 K个相互独立的任务 在任务策略空间集合
下，其中
，多目标优化模型为：

[0080]

[0081] 从模型中可以看出，该问题属于典型的NP难问题（难以采用传统多项式解决方法求解）。因此，需要采用启发式的进化方法解决。

[0082] 3 求解算法

[0083] 本文提出基于多目标优化的方法解决物联网中的分布式节点优化均衡算法问题，其求解过程如下如图1所示：

[0084] 因此，基于物理网的分布式节点优化均衡算法的主要过程如下：

[0085] （1）首先构建多目标优化模型，描述物联网中的中心节点、边缘节点、任务需求等信息，将其建模到计算机中；

[0086] （2）其次是如图2所示，采用基于NSGA‑III的物联网分布式节点资源优化策略求解算法进行求解，得到最优策略；

[0087] （3）然后是将策略应用到物联网的任务执行过程中，对结果进行评估；

[0088] （4）更新物联网中中心节点、边缘节点、任务需求的描述模型信息，包括节点的总能量、带宽等情况信息；

[0089] （5）当任务需求更新时，重复第（2）步继续执行。

[0090] 4 实验结果

[0091] 本发明选取一个物联网局域网中的数据采集任务和预测的数据集合，该物联网部署在一个开放的广场环境中，用于监测行人流量以及计算预测未来的行人浏览，包含4中心节点，100个边缘节点，预测任务每一个小时随机产生于其中10个边缘节点，从而对物联网的分布式节点资源的使用进行优化。

[0092] 本发明所采用的实验背景为：电脑主要配置为：Pentium（R）Dual‑core 3.06 CPU，8G RAM内存。

[0093] 效果评估：本文对算法的性能评估采用的参数包括，在10轮、20轮任务产生完成后，边缘节点计算资源消耗总量（Total RC）、边缘节点存储资源消耗总量（Total CC）、边缘节点能源消耗总量（Total PC）、数据传输总量（Total TC）。

[0094] 对比传统的随机分配算法（Random）、最近距离分配算法（NearDist），本算法的计算结果如下表：

[0095] 需要说明的是，效果评估的参数都是越小越好。

[0096] 针对10轮任务产生后，各项性能评估参数结果：

[0097]

[0098] 针对20轮任务产生后，各项性能评估参数结果：

[0099]

[0100] 上述实施例仅为最佳例举，而并非是对本发明的实施方式的限定。