一种调度信息物理系统的任务执行节点选择方法

1.本发明属于智能调度领域，具体涉及一种调度信息物理系统的任务执行节点选择方法。


背景技术：

2.面对复杂多变的井下环境，矿山运输调度信息物理系统需要满足调度设备任务协调、机车位置实时定位等不同时间尺度和处理精度的要求。因此，矿山运输调度信息物理系统需要依靠先进的通讯技术和控制技术才能实现多样化的功能。在实际矿山机车运输调度控制过程中，通过矿山运输调度信息物理系统物理层的大量感知器对机车行驶过程中产生的各种状态数据和机车位置数据进行采集，通过分析感知数据对机车行驶过程进行实时监控和分析，通过控制指令对系统中的各种类型的执行器进行行为调整和改变。在这个过程中，信息的实时处理场景包括井下机车位置定位、设备故障预测、井下环境监控、设备行为控制等，这就要求系统对感知数据进行快速计算分析、实时控制，及时优化调整。


技术实现要素：

3.针对现有技术中存在的上述技术问题，本发明提出了一种调度信息物理系统的任务执行节点选择方法，设计合理，克服了现有技术的不足，具有良好的效果。
4.为了实现上述目的，本发明采用如下技术方案：
5.一种调度信息物理系统的任务执行节点选择方法，采用云端计算节点以及边缘端计算节点，具体包括如下步骤：
6.步骤1：将实时处理场景抽象为信息物理系统计算任务，构建机车运输调度信息物理系统的任务执行时间成本模型，包括任务传输时间成本模型、任务等待时间成本模型和任务计算时间成本模型；
7.步骤2：基于信息熵，对计算云端计算节点和边缘端计算节点中控制器的cpu利用率和链路带宽使用率进行动态描述；
8.步骤3：增加惩罚函数，将任务执行目标转化为数学中的最优化问题；
9.步骤4：通过最优执行节点选择算法调度计算任务执行节点和时间，给所有的计算任务都能分配合理的计算资源使其在最短时间内得到处理，实现计算任务的实时处理。
10.优选地，步骤1中，实时处理场景包括煤矿井下机车实时位置分析、机车路径切换分析、机车行驶状态分析和人的行为控制；将这些实时处理场景抽象为单个信息物理系统计算任务；每个任务的执行周期分为“请求-调度-计算-控制-动作”5个阶段。
11.优选地，在任务传输时间成本模型中，任务数据从信息物理系统产生后必然会经过边缘端计算节点的控制器调度至云端计算节点或者在边缘端计算节点进行数据计算，考虑两种情况下的时间计算成本，具体表示为公式(1.5)所示：
12.13.其中，为计算任务在边缘端计算节点的控制器计算时的传输时间成本，为计算任务在云端计算节点的控制器计算时的传输时间成本；
14.计算任务在边缘端计算节点的控制器和云端计算节点的控制器计算分析时，数据在传输链路上花费时间，该传输时间成本由式(1.6)、(1.7)决定：
[0015][0016][0017]
式(1.6)中，为信息物理系统与边缘端计算节点的控制器之间数据传输链路的剩余带宽；式(1.7)中，为边缘端计算节点的控制器到云端计算节点的控制器之间数据传输链路的剩余带宽；其中，数据传输链路剩余带宽为传输链路两端数据接受和发送链路剩余带宽的最小值；
[0018]
数据传输链路剩余带宽大小求取公式为：
[0019][0020]
式(1.8)中，b
bw_all
为边缘端计算节点的控制器或者云端计算节点的控制器的最大链路传输带宽；d(t)为t时刻的累积数据量；t
data_gap
为统计数据积累量的间隔时间；
[0021]
所以任务被调度到边缘端计算节点的控制器或云端计算节点的控制器执行计算时，在此过程中任务数据传输时间成本表示为公式(1.9)所示：
[0022][0023]
其中，为计算任务在边缘端计算节点的控制器计算时的传输时间成本，为计算任务在云端计算节点的控制器计算时的传输时间成本，布尔量ii表示计算任务的执行地点ii＝{0,1}，当计算任务在边缘端执行时ii＝1；当计算任务在云端执行时ii＝0。
[0024]
优选地，任务等待时间成本模型中，根据基于优先级的执行规则，被调度任务的完成时间随着其他高优先级线程数量的增加而增加，在任务等待时间成本方面，由于边缘端节点和云端计算节点在计算能力上差异显著，任务的等待时间成本应分别考虑这两种执行地点，如式(1.10)所示：
[0025][0026]
式(3.10)中，为任务在边缘端计算节点的控制器进行计算的任务等待时间成本，为任务在云端计算节点的控制器进行计算的任务等待时间成本；
[0027]
在边缘端计算节点，执行数据量小、执行时间短的实时控制任务；调度至边缘计算节点的控制器中的计算任务，其等待时间成本用式(1.11)表示：
[0028][0029]
式(1.11)中，ne为边缘端计算节点的控制器上需要计算的其他线程数；为边
缘端计算节点的控制器上其他每个线程执行时间；表示这些线程在边缘端计算节点的控制器上占用的cpu使用率；为边缘端计算节点的控制器一个标准线程执行的时间；为边缘端计算节点的控制器一个标准线程占用的cpu使用率；
[0030]
在云端计算节点，执行数据量大、实时性相对要求不高的低优先级计算任务；调度至云端计算节点的控制器中计算任务等待时间成本用式(1.12)表示：
[0031][0032]
式(3.12)，nc为云端计算节点的控制器上需要计算的其他线程数；为云端计算节点的控制器上其他每个线程执行时间；表示这些线程在云端计算节点的控制器上占用的cpu使用率；为云端计算节点的控制器一个标准线程执行的时间；为云端计算节点的控制器一个标准线程占用的cpu使用率；
[0033]
所以当任务调度到边缘端计算节点的控制器或云端计算节点的控制器上计算分析时，任务等待时间成本由式(1.13)表示：
[0034][0035]
优选地，任务计算时间成本模型中，在任务计算时间成本方面，由于边缘端节点和云端计算节点的计算能力差异显著，因此需要考虑这两种场景下的任务执行时间成本，如式(1.14)所示；
[0036][0037]
式(1.14)中，为任务在边缘端计算节点的控制器上计算的时间成本，为任务在云端计算节点的控制器上计算的时间成本；
[0038]
考虑到边缘端计算节点的控制器或云端计算节点的控制器计算能力的差异，以及边缘端所有计算节点的控制器型号统一，采用ue和uc分别表示边缘端计算节点的控制器和云端计算节点的控制器的指令执行速度，以及表示标准任务在边缘端计算节点的控制器和云端计算节点的控制器上执行所需的指令周期数；调度至边缘端计算节点的控制器和云端计算节点的控制器的任务计算时间成本分别用式(1.15)、(1.16)计算：
[0039][0040][0041]
通过计算任务的cpu使用率，也能够确定其计算时间成本；具体地，当一个计算任务被调度到边缘端计算节点的控制器或云端计算节点的控制器中计算时，其任务计算时间成本分别由式(1.17)、(1.18)给出：
[0042][0043]
[0044]
式(1.17)中，为任务被调度到边缘端计算节点的控制器时任务cpu使用率；式(1.18)中，为任务被调度到云端计算节点的控制器时任务cpu使用率；
[0045]
所以任务被调度到边缘端计算节点的控制器或云端计算节点的控制器计算分析时，任务计算时间成本表示为公式(1.19)所示：
[0046][0047]
优选地，步骤2中，为了描述信息传输过程中信息的不确定性对系统时延的影响，采用信息熵公式对其进行量化分析，如式(1.20)所示：
[0048][0049]
式(1.20)中，nk表示信息发生类型的总数，pk表示第k种信息产生的概率；
[0050]
所有边缘端计算节点的控制器与云端计算节点的控制器之间的最大传输带宽相同，信息物理系统的控制器与边缘端计算节点的控制器之间的最大传输带宽也相同；因此，在计算链路带宽剩余大小的熵时，将使用链路带宽剩余大小与最大传输带宽的比值作为统计参数；
[0051][0052]
式(1.21)中，r
bw
表示链路带宽剩余率；
[0053]
在使用式(1.21)进行计算时，同一类型的数据会被当作不同类型的信息来处理，为确保同一类型中的数据处于相同的数值区间，进行以下处理：
[0054]
将0至1的数值范围分成若干个区段，将得到的cpu使用率和链路带宽剩余率的四舍五入数据归类到相应的区段中，以此近似处理彼此接近的数据为相同类型的信息；然后，在同一时间段内，对每个边缘端计算节点的控制器和云端计算节点的控制器的cpu使用率和链路带宽剩余率进行连续记录；当接收到具有一定优先级和数据规模的计算任务时，边缘端计算节点的控制器会计算分析当前的cpu使用率和链路带宽剩余率的信息熵，以判断该计算任务是否应该调度到边缘端计算节点或云端计算节点；
[0055]
在获得一系列近似的cpu使用率和链路带宽剩余率数据后，计算这些数据在各个区段内的概率分布；采用式(1.22)来计算每个区段内的数据出现次数，并用于后续的信息熵计算，式(1.22)如下：
[0056][0057]
式(1.22)中，pk为第n
all
个分区的概率值；numk为数据在第k个分区中出现的次数；num
sum
为数据统计总数；
[0058]
在计算出每个分区数据出现的概率后，利用式(1.20)计算该分区数据的信息熵。
[0059]
优选地，步骤3中，采用sigmoid函数作为惩罚函数，表达式为：
[0060][0061]
修改后的惩罚函数由式(1.26)给出，该惩罚函数考虑信息熵和内存资源对任务执
行时间成本的影响；
[0062][0063]
式(1.26)中，a、b为惩罚函数的参数，a＞0，b＞0；
[0064]
将式(1.26)中x替换为cpu使用率的信息熵、链路带宽剩余率信息熵或者内存使用率，惩罚函数中a＝9，信息熵的惩罚函数参数b＝10，内存使用率的惩罚函数参数b＝100，构建基于信息熵的任务执行时间成本优化函数，如式(1.27)所示：
[0065][0066]
式(1.27)中，为边缘端计算节点的控制器内存使用率；为归一化后边缘端链路剩余带宽率信息熵；为归一化后云端链路剩余带宽率信息熵；为归一化后边缘端计算节点的控制器中等待执行线程所需要的cpu使用率信息熵；为归一化后云端计算节点的控制器中等待执行的线程所需要的cpu使用率信息熵。
[0067]
优选地，步骤4中，计算任务传入边缘端计算节点后，通过式(1.27)求取任务在边缘端计算节点和云端计算节点的任务执行等价时延，便于计算任务选择合适节点计算分析；
[0068]
利用上述模型，能够生成矿山运输调度信息物理系统中任务调度问题的目标函数，该函数在保证每个任务满足特定时间约束的同时，寻求最小化任务执行时间成本，如式(1.25)所示；
[0069]
min t
r,i
ꢀꢀ
(1.28)
[0070]
s.t.
[0071]
ue＜＜ucꢀꢀ
(1.29)
[0072]
t
r,i
＜t
θ,i
ꢀꢀ
(1.30)
[0073]
i＝{0,1}
ꢀꢀ
(1.31)
[0074]bbw
＜b
bw_all
ꢀꢀ
(1.32)
[0075]
sto
in
+sto
out
＜sto
all
ꢀꢀ
(1.33)
[0076]
该目标函数受到多个约束，式(1.29)为云端计算节点比边缘端计算节点具有更高的计算能力；式(1.30)为任务执行时间应满足一定的时间约束；式(1.31)为任务只能在边
缘端计算节点或云端计算节点上计算分析；式(1.32)为任务传输带宽应该小于传输链路的总带宽；式(1.32)为任务执行所需的内存应小于边缘端计算节点的控制器或者云端计算节点的控制器的最大链路传输带宽的总内存；
[0077]
以计算任务最小化时延为目标，基于信息熵的最优执行节点选择方法为：
[0078][0079]
s.t.
[0080][0081]
其中，表示计算任务选择在在边缘端计算节点计算时任务执行时间；表示计算任务选择在在云端计算节点计算时任务执行时间；s
c，i
表示计算任务在边缘端或者云端计算节点的控制器上占用的cpu使用率；s
c，n
表示其他线程在边缘端或者云端计算节点的控制器上占用的cpu使用率；s
s，i
表示计算任务在边缘端或者云端计算节点的控制器上占用的内存使用率；s
s，n
表示其他线程在边缘端或者云端计算节点的控制器上占用的内存使用率。
[0082]
本发明所带来的有益技术效果：
[0083]
本发明方法可以减低计算任务处理时延，缓解了云端计算中的计算负载和带宽压力。
附图说明
[0084]
图1为cps计算任务执行流程图；
[0085]
图2为基于优先级调度下线程执行流程图。
具体实施方式
[0086]
下面结合附图以及具体实施方式对本发明作进一步详细说明：
[0087]
如图1所示，本发明方法通过选择合适的任务执行节点来实现机车运输调度信息物理系统的任务快速计算分析，具体包括如下步骤：
[0088]
步骤1：将机车运输调度信息物理系统实时处理场景抽象为cps(cyber-physical systems，信息物理系统)计算任务，构建机车运输调度信息物理系统任务执行时间成本模型，包括任务传输时间成本模型、任务等待时间成本模型、任务计算时间成本模型。
[0089]
将实时处理场景下的煤矿井下机车实时位置分析、机车路径切换分析、机车行驶状态分析和人的行为控制抽象为单个cps计算任务。每个任务的执行周期可以分为“请求-调度-计算-控制-动作”5个阶段。图1展示了一个采矿运输调度cps计算任务的执行过程，包括任务请求、任务调度、任务计算、反馈控制和动作执行五个步骤。从图1中可以看出，在任务请求发出后，边缘端计算节点将首先做出任务调度决策，以确定任务计算将在哪里计算分析，即在云端计算节点或在边缘端计算节点；然后，基于反馈结果驱动相应动作。只有在这五个阶段保证极低的延迟，才能达到任务实时响应，才能实现系统实时性能。
[0090]
矿山运输cps中的实时任务调度模型主要是通过一定的任务调度策略实现任务执
行时间最小的优化目标。主要针对云边协同下计算任务的数据流动路径和消耗成本进行研究，并且可以通过如下数学表达式来描述：
[0091]
假设在某一时刻有一个cps单元设备请求的cps计算任务，计算任务定义为taski＝{di,t
r,i
,t
θ,i
,s
c,i
,s
s.i
,ii}，di表示任务期间数据传输的大小；t
r,i
表示任务的实际执行时间，t
θ,i
表示任务的最大延迟容忍极限，s
c,i
表示任务执行期间使用的计算资源，s
s,i
表示任务执行期间使用的存储资源；布尔量ii表示计算任务的执行地点，ii＝{0,1}，当计算任务在边缘端执行时ii＝1；当计算任务在云端执行时ii＝0。
[0092]
对于基于云边协同计算的矿山运输cps实时任务调度模型，任务执行时间成本即任务执行所消耗的时间主要由三部分组成：传输时间成本、计算时间成本和等待时间成本。传输时间成本是指任务数据传输所消耗的时间；计算时间成本是指控制器中数据计算分析所消耗的时间；而等待时间成本是指在控制器中等待其他任务完成时所消耗的时间。如式(1.1)所示：
[0093]
t
r,i
＝t
tran,i
+t
wait,i
+t
calc,i
ꢀꢀ
(1.1)
[0094]
式(1.1)中，t
tran,i
为任务传输时间成本；t
wait,i
为任务等待时间成本；t
calc,i
为任务计算时间成本。
[0095]
任务能够在控制器执行的条件为：
[0096]
(s
c,i
≤s
c,idle
)∪(s
s,i
≤s
s,idle
)
ꢀꢀ
(1.2)
[0097]
式(1.1)中，s
c,idle
和s
s,idle
分别表示控制器中的可用存储和计算资源。
[0098]
上述约束保证了计算任务能够在可用资源范围内在控制器中执行。当内部存储资源不足以满足计算任务的所需的存储资源，就会使用外部存储，对任务计算速度造成显著影响，因此，内存不足被认为是影响任务计算分析速度的显著因素。在实际应用中，简单地通过检查任务在调度的控制器中计算时的cpu利用率或内存利用率是否为100％来是否满足式(1.2)的执行条件。
[0099]
计算任务在控制器上所需计算和存储资源定义为：
[0100][0101][0102]
式(1.3)中，r
cpu,i
为任务在执行过程中占用的cpu比率。
[0103]
式(1.4)中，sto
in,i
为任务在控制器中占用的内部存储大小；sto
out,i
为任务在控制器中占用的外部存储大小；sto
all
为控制器的总内存大小。
[0104]
任务传输时间成本模型
[0105]
任务传输时间成本模型中，任务数据从信息物理系统产生后必然会经过边缘端计算节点的控制器调度至云端计算节点或者在边缘端计算节点进行数据计算，考虑两种情况下的时间计算成本，具体表示为公式(1.5)所示：
[0106][0107]
其中，为计算任务在边缘端控制器计算时的传输时间成本，为计算任务
在云端计算节点的控制器计算时的传输时间成本；
[0108]
由于计算后的需要反馈的结果数据量远小于原始数据量，所以忽略反馈控制过程所需要的时间，计算任务在边缘端计算节点的控制器和云端计算节点的控制器计算分析时，数据在传输链路上花费时间，该传输时间成本由式(1.6)、(1.7)决定：
[0109][0110][0111]
式(1.6)中，为信息物理系统与边缘端计算节点的控制器之间数据传输链路的剩余带宽；式(1.7)中，为边缘端计算节点的控制器到云端计算节点的控制器之间数据传输链路的剩余带宽；其中，数据传输链路剩余带宽为传输链路两端数据接受和发送链路剩余带宽的最小值；
[0112]
数据传输链路剩余带宽大小求取公式为：
[0113][0114]
式(1.8)中，b
bw_all
为边缘端计算节点的控制器还是云端计算节点的控制器的最大链路传输带宽；d(t)为t时刻的累积数据量；t
data_gap
为统计数据积累量的间隔时间；
[0115]
所以任务被调度到边缘端计算节点的控制器或云端计算节点的控制器执行计算时，在此过程中任务数据传输时间成本表示为公式(1.9)所示：
[0116][0117]
其中，为计算任务在边缘端控制器计算时的传输时间成本，为计算任务在云端计算节点的控制器计算时的传输时间成本，布尔量ii表示计算任务的执行地点ii＝{0,1}，当计算任务在边缘端执行时ii＝1；当计算任务在云端执行时ii＝0
[0118]
任务等待时间成本模型
[0119]
在边缘端计算节点的控制器或云端计算节点的控制器的操作系统中，线程基于优先级调度，当并发线程在边缘端计算节点的控制器或云端计算节点的控制器上运行时，高优先级的实时控制任务会抢占低优先级任务。这种现象在边缘端计算节点的控制器中更为突出，如图2所示。
[0120]
任务等待时间成本模型中，根据基于优先级的执行规则，被调度任务的完成时间随着其他高优先级线程数量的增加而增加，在任务等待时间成本方面，由于边缘端节点和云端计算节点在计算能力上差异显著，任务的等待时间成本应分别考虑这两种执行地点，如式(1.10)所示：
[0121][0122]
式(3.10)中，为任务在边缘端计算节点的控制器进行计算的任务等待时间成本，为任务在云端计算节点的控制器进行计算的任务等待时间成本；
[0123]
在边缘端计算节点，主要执行数据量小、执行时间短的实时控制任务；调度至边缘
计算节点的控制器中的计算任务，其等待时间成本用式(1.11)表示：
[0124][0125]
式(1.11)中，ne为边缘端计算节点的控制器上需要计算的其他线程数；为边缘端计算节点的控制器上其他每个线程执行时间；表示这些线程在边缘端计算节点的控制器上占用的cpu使用率；为边缘端计算节点的控制器一个标准线程执行的时间；为边缘端计算节点的控制器一个标准线程占用的cpu使用率；
[0126]
在云端计算节点，主要执行数据量大、实时性相对要求不高的低优先级计算任务；调度至云端计算节点的控制器中计算任务等待时间成本用式(1.12)表示：
[0127][0128]
式(3.12)，nc为云端计算节点的控制器上需要计算的其他线程数；为云端计算节点的控制器上其他每个线程执行时间；表示这些线程在云端计算节点的控制器上占用的cpu使用率；为云端计算节点的控制器一个标准线程执行的时间；为云端计算节点的控制器一个标准线程占用的cpu使用率；
[0129]
所以当任务调度到边缘端计算节点的控制器或云端计算节点的控制器上计算分析时，任务等待时间成本由式(1.13)表示：
[0130][0131]
任务计算时间成本模型
[0132]
任务计算时间成本模型中，在任务计算时间成本方面，由于边缘端节点和云端计算节点的计算能力差异显著，因此需要考虑这两种场景下的任务执行时间成本，如式(1.14)所示；
[0133][0134]
式(1.14)中，为任务在边缘端计算节点的控制器上计算的时间成本，为任务在云端计算节点的控制器上计算的时间成本；
[0135]
考虑到边缘端计算节点的控制器或云端计算节点的控制器计算能力的差异，以及边缘端所有计算节点的控制器型号统一，采用ue和uc分别表示边缘端计算节点的控制器和云端计算节点的控制器的指令执行速度，以及表示标准任务在边缘端计算节点的控制器和云端计算节点的控制器上执行所需的指令周期数；调度至边缘端计算节点的控制器和云端计算节点的控制器的任务计算时间成本分别用式(1.15)、(1.16)计算：
[0136][0137][0138]
通过计算任务的cpu使用率，也能够确定其计算时间成本；具体地，当一个计算任
务被调度到边缘端计算节点的控制器或云端计算节点的控制器中计算时，其任务计算时间成本分别由式(1.17)、(1.18)给出：
[0139][0140][0141]
式(1.17)中，为任务被调度到边缘端计算节点的控制器时任务cpu使用率；式(1.18)中，为任务被调度到云端计算节点的控制器时任务cpu使用率；
[0142]
所以任务被调度到边缘端计算节点的控制器或云端计算节点的控制器计算分析时，任务计算时间成本表示为公式(1.19)所示：
[0143][0144]
步骤2：基于信息熵对计算节点中控制器cpu利用率和链路带宽使用率进行动态描述；
[0145]
在步骤1中，讨论了任务在边缘端和云端计算节点上执行的时间成本模型，该模型考虑了计算任务执行时资源状态的变化；然而，在实际应用中，cpu使用率和链路带宽剩余大小变化频繁，为了避免在cpu使用率波动较大时在边缘端和云端计算节点上分析和计算任务，防止可能出现无法满足任务时延极限的情况，需要考虑控制器的cpu使用率变化对任务执行时间的影响；同时，为了反映边计算节点和云计算节点中链路带宽剩余大小的动态变化对计算任务执行延迟的影响，并获得最优的计算节点，通过信息论中的信息熵来描述控制器cpu使用率和链路带宽剩余大小对计算任务执行延迟的影响。
[0146]
为了描述信息传输过程中信息的不确定性对系统时延的影响，采用信息熵公式对其进行量化分析，如式(1.20)所示：
[0147][0148]
式(1.20)中，nk表示信息发生类型的总数，pk表示第k种信息产生的概率；本技术中，对数的底数取值为2。
[0149]
由于链路带宽剩余大小并不像cpu使用率那样是无量纲的，需要对其进行比例化处理。所有边缘端计算节点的控制器与云端计算节点的控制器之间的最大传输带宽相同，信息物理系统的控制器与边缘端计算节点的控制器之间的最大传输带宽也相同；因此，在计算链路带宽剩余大小的熵时，将使用链路带宽剩余大小与最大传输带宽的比值作为统计参数；
[0150][0151]
式(1.21)中，r
bw
表示链路带宽剩余率；
[0152]
在实际应用中，同一类型的数据在传输过程中可能存在微小的大小差异，即使数值接近，在使用式(1.21)进行计算时，同一类型的数据会被当作不同类型的信息来处理，为确保同一类型中的数据处于相同的数值区间，进行以下处理：
[0153]
将0至1的数值范围分成若干个区段，将得到的cpu使用率和链路带宽剩余率的四舍五入数据归类到相应的区段中，以此近似处理彼此接近的数据为相同类型的信息；然后，在同一时间段内，对每个边缘端计算节点的控制器和云端计算节点的控制器的cpu使用率和链路带宽剩余率进行连续记录；当接收到具有一定优先级和数据规模的计算任务时，边缘端计算节点的控制器会计算分析当前的cpu使用率和链路带宽剩余率的信息熵，以判断该计算任务是否应该调度到边缘端计算节点或云端计算节点；
[0154]
在获得一系列近似的cpu使用率和链路带宽剩余率数据后，计算这些数据在各个区段内的概率分布；采用式(1.22)来计算每个区段内的数据出现次数，并用于后续的信息熵计算，式(1.22)如下：
[0155][0156]
式(1.22)中，pk为第n
all
个分区的概率值；numk为数据在第k个分区中出现的次数；num
sum
为数据统计总数；
[0157]
在计算出每个分区数据出现的概率后，利用式(1.20)计算该分区数据的信息熵。
[0158]
规定log0＝0。
[0159]
因此，控制器cpu使用率和链路带宽剩余率信息熵计算算法，如算法3.1所示。
[0160]
算法3.1：控制器cpu使用率与链路剩余带宽率的信息熵计算算法
[0161]
输入：控制器cpu使用率与链路剩余带宽率的数值大小序列x＝{x1,x2,...,xn}
[0162]
输出：信息熵h
[0163]
step0：初始化区段分区中数值个数，numk＝0；
[0164]
step1：初始化区段分区概率分布，pk＝0；
[0165]
step2：初始化信息熵值，h＝0；
[0166]
step3：将控制器cpu使用率与链路剩余带宽率的数值大小序列中的数据xk进行近似处理；
[0167]
step4：将与xk对应的分区数值加1；
[0168]
step5：计算每一分区的概率值pk；
[0169]
step6：检测分区概率值pk，第1个至第100个分区；
[0170]
若pk＞0，则h＝h-p
k logpk；
[0171]
若pk＝0，则h＝h-0。
[0172]
由于计算后得出的cpu使用率与链路带宽剩余率信息熵值并非全部在0到1内，为方便下一步的计算分析，通过下式(3.23)对计算出来的信息熵进行归一化处理。
[0173][0174]
其中，n
all
代表数值分区总数量，归一化原理为，每个分区概率值相等时为系统信息熵最大的时候，如式(1.24)：
[0175][0176]
步骤3：为体现信息熵和内存资源对任务执行时延的影响，增加惩罚函数，将任务执行目标转化为数学中的最优化问题。
[0177]
上述内容只考虑了计算资源对任务执行时间成本的影响，没有考虑存储资源；然而，在边缘端控制器中可能存在内存资源不足的情况，这是存储资源会显著影响任务的执行时间成本，由于云端计算中心具有高计算能力和大存储资源的特点，忽略存储资源对云端任务执行时延的影响。
[0178]
同时为能够体现信息熵与任务执行时间成本的关系以及体现存储资源对执行任务时延的影响，引入惩罚函数，在信息熵混乱程度较大时和内存资源达到临界阈值时激活惩罚函数来增加任务执行时间成本，采用sigmoid函数作为惩罚函数，表达式为：
[0179][0180]
修改后的惩罚函数由式(1.26)给出，该惩罚函数考虑信息熵和内存资源对任务执行时间成本的影响；
[0181][0182]
为了优化任务执行时间成本，需要考虑每个cps计算任务的数据传输时间成本、计算时间成本和等待时间成本，同时为体现cpu使用率、链路带宽剩余大小变化以及内存资源的影响，在信息混乱程度较高、内存不足的情况下具有10倍的等价时延，式(1.26)中，a、b为惩罚函数的参数，a＞0，b＞0；
[0183]
将式(1.26)中x替换为cpu使用率的信息熵、链路带宽剩余率信息熵或者内存使用率，惩罚函数中a＝9，信息熵的惩罚函数参数b＝10，内存使用率的惩罚函数参数b＝100，构建基于信息熵的任务执行时间成本优化函数，如式(1.27)所示：
[0184][0185]
式(1.27)中，为边缘端计算节点的控制器内存使用率；为归一化后边缘端链路剩余带宽率信息熵；为归一化后云端链路剩余带宽率信息熵；为归一化后边缘端计算节点的控制器中等待执行线程所需要的cpu使用率信息熵；为归一化后云端计算节点的控制器中等待执行的线程所需要的cpu使用率信息熵。
[0186]
步骤4：通过最优执行节点选择算法调度计算任务执行节点和时间，目的是给所有的计算任务都能分配合理的计算资源使其在最短时间内得到处理，实现计算任务实时处理。
[0187]
计算任务传入边缘端计算节点后，通过式(1.27)求取任务在边缘端计算节点和云
端计算节点的任务执行等价时延，便于计算任务选择合适节点计算分析；
[0188]
利用上述模型，能够生成矿山运输调度信息物理系统中任务调度问题的目标函数，该函数在保证每个任务满足特定时间约束的同时，寻求最小化任务执行时间成本，如式(1.25)所示；
[0189]
min t
r,i
ꢀꢀ
(1.28)
[0190]
s.t.
[0191]
ue＜＜ucꢀꢀ
(1.29)
[0192]
t
r,i
＜t
θ,i
ꢀꢀ
(1.30)
[0193]
i＝{0,1}
ꢀꢀ
(1.31)
[0194]bbw
＜b
bw_all
ꢀꢀ
(1.32)
[0195]
sto
in
+sto
out
＜sto
all
ꢀꢀ
(1.33)
[0196]
该目标函数受到多个约束，式(1.29)为云端计算节点比边缘端计算节点具有更高的计算能力；式(1.30)为任务执行时间应满足一定的时间约束；式(1.31)为任务只能在边缘端计算节点或云端计算节点上计算分析；式(1.32)为任务传输带宽应该小于传输链路的总带宽；式(1.32)为任务执行所需的内存应小于边缘端计算节点的控制器还是云端计算节点的控制器的最大链路传输带宽的总内存；
[0197]
以计算任务最小化时延为目标，基于信息熵的最优执行节点选择方法为：
[0198][0199]
s.t.
[0200][0201]
其中，表示计算任务选择在在边缘端计算节点计算时任务执行时间；表示计算任务选择在在云端计算节点计算时任务执行时间；s
c，i
表示计算任务在边缘端或者云端计算节点的控制器上占用的cpu使用率；s
c，n
表示其他线程在边缘端或者云端计算节点的控制器上占用的cpu使用率；s
c，i
表示计算任务在边缘端或者云端计算节点的控制器上占用的内存使用率；s
s，n
表示其他线程在边缘端或者云端计算节点的控制器上占用的内存使用率。
[0202]
当然，上述说明并非是对本发明的限制，本发明也并不仅限于上述举例，本技术领域的技术人员在本发明的实质范围内所做出的变化、改型、添加或替换，也应属于本发明的保护范围。

技术特征：
1.一种调度信息物理系统的任务执行节点选择方法，其特征在于：采用云端计算节点以及边缘端计算节点，具体包括如下步骤：步骤1：将实时处理场景抽象为信息物理系统计算任务，构建机车运输调度信息物理系统的任务执行时间成本模型，包括任务传输时间成本模型、任务等待时间成本模型和任务计算时间成本模型；步骤2：基于信息熵，对计算云端计算节点和边缘端计算节点中控制器的cpu利用率和链路带宽使用率进行动态描述；步骤3：增加惩罚函数，将任务执行目标转化为数学中的最优化问题；步骤4：通过最优执行节点选择算法调度计算任务执行节点和时间，给所有的计算任务都能分配合理的计算资源使其在最短时间内得到处理，实现计算任务的实时处理。2.根据权利要求1所述的调度信息物理系统的任务执行节点选择方法，其特征在于：步骤1中，实时处理场景包括煤矿井下机车实时位置分析、机车路径切换分析、机车行驶状态分析和人的行为控制；将这些实时处理场景抽象为单个信息物理系统计算任务；每个任务的执行周期分为“请求-调度-计算-控制-动作”5个阶段。3.根据权利要求1所述的调度信息物理系统的任务执行节点选择方法，其特征在于：在任务传输时间成本模型中，任务数据从信息物理系统产生后必然会经过边缘端计算节点的控制器调度至云端计算节点或者在边缘端计算节点进行数据计算，考虑两种情况下的时间计算成本，具体表示为公式(1.5)所示：其中，为计算任务在边缘端计算节点的控制器计算时的传输时间成本，为计算任务在云端计算节点的控制器计算时的传输时间成本；计算任务在边缘端计算节点的控制器和云端计算节点的控制器计算分析时，数据在传输链路上花费时间，该传输时间成本由式(1.6)、(1.7)决定：输链路上花费时间，该传输时间成本由式(1.6)、(1.7)决定：式(1.6)中，为信息物理系统与边缘端计算节点的控制器之间数据传输链路的剩余带宽；式(1.7)中，为边缘端计算节点的控制器到云端计算节点的控制器之间数据传输链路的剩余带宽；其中，数据传输链路剩余带宽为传输链路两端数据接受和发送链路剩余带宽的最小值；数据传输链路剩余带宽大小求取公式为：式(1.8)中，b
bw_all
为边缘端计算节点的控制器或者云端计算节点的控制器的最大链路传输带宽；d(t)为t时刻的累积数据量；t
data_gap
为统计数据积累量的间隔时间；所以任务被调度到边缘端计算节点的控制器或云端计算节点的控制器执行计算时，在
此过程中任务数据传输时间成本表示为公式(1.9)所示：其中，为计算任务在边缘端计算节点的控制器计算时的传输时间成本，为计算任务在云端计算节点的控制器计算时的传输时间成本，布尔量i
i
表示计算任务的执行地点i
i
＝{0,1}，当计算任务在边缘端执行时i
i
＝1；当计算任务在云端执行时i
i
＝0。4.根据权利要求1所述的调度信息物理系统的任务执行节点选择方法，其特征在于：任务等待时间成本模型中，根据基于优先级的执行规则，被调度任务的完成时间随着其他高优先级线程数量的增加而增加，在任务等待时间成本方面，由于边缘端节点和云端计算节点在计算能力上差异显著，任务的等待时间成本应分别考虑这两种执行地点，如式(1.10)所示：式(3.10)中，为任务在边缘端计算节点的控制器进行计算的任务等待时间成本，为任务在云端计算节点的控制器进行计算的任务等待时间成本；在边缘端计算节点，执行数据量小、执行时间短的实时控制任务；调度至边缘计算节点的控制器中的计算任务，其等待时间成本用式(1.11)表示：式(1.11)中，n
e
为边缘端计算节点的控制器上需要计算的其他线程数；为边缘端计算节点的控制器上其他每个线程执行时间；表示这些线程在边缘端计算节点的控制器上占用的cpu使用率；为边缘端计算节点的控制器一个标准线程执行的时间；为边缘端计算节点的控制器一个标准线程占用的cpu使用率；在云端计算节点，执行数据量大、实时性相对要求不高的低优先级计算任务；调度至云端计算节点的控制器中计算任务等待时间成本用式(1.12)表示：式(3.12)，n
c
为云端计算节点的控制器上需要计算的其他线程数；为云端计算节点的控制器上其他每个线程执行时间；表示这些线程在云端计算节点的控制器上占用的cpu使用率；为云端计算节点的控制器一个标准线程执行的时间；为云端计算节点的控制器一个标准线程占用的cpu使用率；所以当任务调度到边缘端计算节点的控制器或云端计算节点的控制器上计算分析时，任务等待时间成本由式(1.13)表示：5.根据权利要求1所述的调度信息物理系统的任务执行节点选择方法，其特征在于：任务计算时间成本模型中，在任务计算时间成本方面，由于边缘端节点和云端计算节点的计算能力差异显著，因此需要考虑这两种场景下的任务执行时间成本，如式(1.14)所示；
式(1.14)中，为任务在边缘端计算节点的控制器上计算的时间成本，为任务在云端计算节点的控制器上计算的时间成本；考虑到边缘端计算节点的控制器或云端计算节点的控制器计算能力的差异，以及边缘端所有计算节点的控制器型号统一，采用u
e
和u
c
分别表示边缘端计算节点的控制器和云端计算节点的控制器的指令执行速度，以及表示标准任务在边缘端计算节点的控制器和云端计算节点的控制器上执行所需的指令周期数；调度至边缘端计算节点的控制器和云端计算节点的控制器的任务计算时间成本分别用式(1.15)、(1.16)计算：云端计算节点的控制器的任务计算时间成本分别用式(1.15)、(1.16)计算：通过计算任务的cpu使用率，也能够确定其计算时间成本；具体地，当一个计算任务被调度到边缘端计算节点的控制器或云端计算节点的控制器中计算时，其任务计算时间成本分别由式(1.17)、(1.18)给出：分别由式(1.17)、(1.18)给出：式(1.17)中，为任务被调度到边缘端计算节点的控制器时任务cpu使用率；式(1.18)中，为任务被调度到云端计算节点的控制器时任务cpu使用率；所以任务被调度到边缘端计算节点的控制器或云端计算节点的控制器计算分析时，任务计算时间成本表示为公式(1.19)所示：6.根据权利要求1所述的调度信息物理系统的任务执行节点选择方法，其特征在于：步骤2中，为了描述信息传输过程中信息的不确定性对系统时延的影响，采用信息熵公式对其进行量化分析，如式(1.20)所示：式(1.20)中，n
k
表示信息发生类型的总数，p
k
表示第k种信息产生的概率；所有边缘端计算节点的控制器与云端计算节点的控制器之间的最大传输带宽相同，信息物理系统的控制器与边缘端计算节点的控制器之间的最大传输带宽也相同；因此，在计算链路带宽剩余大小的熵时，将使用链路带宽剩余大小与最大传输带宽的比值作为统计参数；
式(1.21)中，r
bw
表示链路带宽剩余率；在使用式(1.21)进行计算时，同一类型的数据会被当作不同类型的信息来处理，为确保同一类型中的数据处于相同的数值区间，进行以下处理：将0至1的数值范围分成若干个区段，将得到的cpu使用率和链路带宽剩余率的四舍五入数据归类到相应的区段中，以此近似处理彼此接近的数据为相同类型的信息；然后，在同一时间段内，对每个边缘端计算节点的控制器和云端计算节点的控制器的cpu使用率和链路带宽剩余率进行连续记录；当接收到具有一定优先级和数据规模的计算任务时，边缘端计算节点的控制器会计算分析当前的cpu使用率和链路带宽剩余率的信息熵，以判断该计算任务是否应该调度到边缘端计算节点或云端计算节点；在获得一系列近似的cpu使用率和链路带宽剩余率数据后，计算这些数据在各个区段内的概率分布；采用式(1.22)来计算每个区段内的数据出现次数，并用于后续的信息熵计算，式(1.22)如下：式(1.22)中，p
k
为第n
all
个分区的概率值；num
k
为数据在第k个分区中出现的次数；num
sum
为数据统计总数；在计算出每个分区数据出现的概率后，利用式(1.20)计算该分区数据的信息熵。7.根据权利要求1所述的调度信息物理系统的任务执行节点选择方法，其特征在于：步骤3中，采用sigmoid函数作为惩罚函数，表达式为：修改后的惩罚函数由式(1.26)给出，该惩罚函数考虑信息熵和内存资源对任务执行时间成本的影响；式(1.26)中，a、b为惩罚函数的参数，a＞0，b＞0；将式(1.26)中x替换为cpu使用率的信息熵、链路带宽剩余率信息熵或者内存使用率，惩罚函数中a＝9，信息熵的惩罚函数参数b＝10，内存使用率的惩罚函数参数b＝100，构建基于信息熵的任务执行时间成本优化函数，如式(1.27)所示：
式(1.27)中，为边缘端计算节点的控制器内存使用率；为归一化后边缘端链路剩余带宽率信息熵；为归一化后云端链路剩余带宽率信息熵；为归一化后边缘端计算节点的控制器中等待执行线程所需要的cpu使用率信息熵；为归一化后云端计算节点的控制器中等待执行的线程所需要的cpu使用率信息熵。8.根据权利要求1所述的调度信息物理系统的任务执行节点选择方法，其特征在于：步骤4中，计算任务传入边缘端计算节点后，通过式(1.27)求取任务在边缘端计算节点和云端计算节点的任务执行等价时延，便于计算任务选择合适节点计算分析；利用上述模型，能够生成矿山运输调度信息物理系统中任务调度问题的目标函数，该函数在保证每个任务满足特定时间约束的同时，寻求最小化任务执行时间成本，如式(1.25)所示；mint
r,i
ꢀꢀ
(1.28)s.t.u
e
＜＜u
c
ꢀꢀꢀ
(1.29)t
r,i
＜t
θ,i
ꢀꢀ
(1.30)i＝{0,1}
ꢀꢀ
(1.31)b
bw
＜b
bw_all
ꢀꢀꢀ
(1.32)sto
in
+sto
out
＜sto
all
ꢀꢀ
(1.33)该目标函数受到多个约束，式(1.29)为云端计算节点比边缘端计算节点具有更高的计算能力；式(1.30)为任务执行时间应满足一定的时间约束；式(1.31)为任务只能在边缘端计算节点或云端计算节点上计算分析；式(1.32)为任务传输带宽应该小于传输链路的总带宽；式(1.32)为任务执行所需的内存应小于边缘端计算节点的控制器或者云端计算节点的控制器的最大链路传输带宽的总内存；以计算任务最小化时延为目标，基于信息熵的最优执行节点选择方法为：s.t.
其中，表示计算任务选择在在边缘端计算节点计算时任务执行时间；表示计算任务选择在在云端计算节点计算时任务执行时间；s
c，i
表示计算任务在边缘端或者云端计算节点的控制器上占用的cpu使用率；s
c，n
表示其他线程在边缘端或者云端计算节点的控制器上占用的cpu使用率；s
c，i
表示计算任务在边缘端或者云端计算节点的控制器上占用的内存使用率；s
s，n
表示其他线程在边缘端或者云端计算节点的控制器上占用的内存使用率。

技术总结
本发明公开了一种调度信息物理系统的任务执行节点选择方法，属于智能调度领域，具体包括如下步骤：将实时处理场景抽象为信息物理系统计算任务，构建机车运输调度信息物理系统的任务执行时间成本模型，包括任务传输时间成本模型、任务等待时间成本模型和任务计算时间成本模型；基于信息熵，对计算云端计算节点和边缘端计算节点中控制器的CPU利用率和链路带宽使用率进行动态描述；增加惩罚函数，将任务执行目标转化为数学中的最优化问题；通过最优执行节点选择算法调度计算任务执行节点和时间，给所有的计算任务都能分配合理的计算资源使其在最短时间内得到处理，实现计算任务的实时处理。时处理。时处理。


技术研发人员：宋永亮 裴计田 侯典东 杨澎 孙鹏 张世男 李文宏 马金羽
受保护的技术使用者：山东科技大学
技术研发日：2023.04.26
技术公布日：2023/8/9