1 引言

淤地坝作为坝区资源开发利用和经济建设的基础工程, 在黄土高原水土保持中的地位尤为显著^[1]. 同时也存在相应的溃坝风险, 因溃坝事件导致的水土流失、生态破坏时有发生, 严重的溃坝事件会危害坝区居民生命安全. 目前淤地坝在信息化管理、险情预测方面, 存在数据利用率低、数据记录方式落后等问题. 为解决这些问题, 坝区远程监测、实时评估等在线实时监测模式逐渐成为淤地坝防护的研究热点.

在5G、物联网技术高速发展的背景下, 采用“云-边-端”方式实现对淤地坝的实时监测、传输、处理和风险预警, 具有重要意义. 通过部署在坝区的水尺、雨量计、视频等传感器采集数据, 并经过边缘节点预处理后上传至云端统一管理和风险评估与预警. 近几年, 有学者通过结合坝区传感数据建立淤地坝溃坝模型, 将采集数据作为参数输入溃坝风险模型进行预警^[2], 实现对所覆盖坝区的24小时智能监测. 然而, 通常情况下淤地坝基础溃坝模型计算复杂度较高, 也会是否在汛期而进一步提升. 同时由于淤地坝数量多、分布广, 一般按照行政区划进行管理, 因此采用“云-边-端”方式可以有效保证监测与预警任务执行的实时性.

本文考虑了实际场景中各因素对计算任务完成时间的影响, 建立了相应的数学模型, 并利用模拟退火(Simulated Annealing, SA)算法能够快速提供一个较为精确的近似解^[3], 对淤地坝的计算任务调度问题进行求解.

2 相关研究 2.1 淤地坝安全问题研究

顾艳玲等^[4]基于熵理论将不同赋权方法进行有机集成, 明确了坝体安全评估特征值权重指标, 并通过最大化模型参数香农熵, 保证估计结果的相对稳健. 黄黎明等^[5]基于工程风险清单、风险搜集、大数据风险分析三方面并结合物联网技术建立质量风险管理框架, 得到以物联网技术实现水利工程风险管理的重要经验. 王乃欣等^[6]利用3Ds Max等建模技术对淤地坝溃坝进行仿真, 为研究溃坝时的救灾抢险、应急管理做出了重要的参考依据. 黄肖^[7]利用MIKE软件建立了一套关于坝系布局与洪水关系的预测模型, 实现模拟研究洪水作用下淤地坝的调控作用. 李平等^[8]将现有判断水库群发溢洪方法与贝叶斯网络有机结合, 并根据场景特征增加了上下游水坝溃坝关系因子, 建立了完整的贝叶斯溢洪评估网络.

2.2 边缘计算任务调度研究

Seid等^[9]提出了一种基于无人机的F-RAN体系结构新方向, 该结构采用分布式强化学习(DRL)算法对边缘设备进行学习, 有效提高了计算任务卸载效率, 并优化了计算资源分配. Liu等 ^[10]建立了一种基于优化边缘服务器资源的分配算法, 提高了移动边缘计算架构的计算资源利用率. Zhou等^[11]通过模拟退火算法解决了D2D资源分配成本高的问题, 在资源分配组合中引入模拟退火算法, 有效降低资源分配成本和任务平均计算时间. Liao等^[12]提出了一种有效的低复杂度启发式算法, 可以在可接受水平内保证边缘计算网络的计算资源保持, 降低时间成本并最大化用户任务卸载量. Anousha等^[13]对传统Min-Min调度算法进行改进, 充分利用原算法在策略制定速度上的优点, 并避免原算法负载均衡性能不足、任务执行时间跨度高的缺点, 最终改善传统Min-Min算法性能.

对淤地坝进行实时监测, 并将其数据作为参数输入至溃坝模型, 由此产生淤地坝计算任务. 为提高淤地坝风险预警的时效性, 需要对计算任务进行合理调度, 缩短计算任务完成时间. 各淤地坝计算任务卸载位置的精确求解属于整数线性规划中的NP难问题. 此类问题虽存在精确最优解, 但计算量极大, 耗时极长.

通常分布式的边缘计算具有高隐私、低成本、易部署等优势, 但其计算资源、存储容量都有所限制. 在边缘计算中, 由于其计算资源受到限制, 从单一角度出发的应用计算切分模式将变得不可实施. 多用户模式情景下, 网络资源和服务器资源的竞争十分普遍. 此时计算任务卸载决策需要结合边缘计算资源分配决策^[14], 通过减少应用完成时间的方式, 提高系统整体服务水平^[15].

3 边缘计算场景下协作式任务调度策略

面向淤地坝监测任务调度策略实现思路如图1所示, 分为3个步骤: 信息获取、建立任务完成时间模型、模拟退火算法求最优解.

(1)信息获取. 该过程为任务调度服务器收集节点产生的计算任务信息和边缘服务器计算资源信息. 其中计算任务信息包括: 计算任务总量、所有任务的计算量、传输计算任务的数据量; 边缘服务器信息包括: 服务器计算能力、基站与节点间的通信带宽、服务器数量.

(2)建立任务完成时间模型. 建立任务完成时间模型, 并代入任务信息与服务器信息, 计算所有任务在某个边缘服务器上的完成时间, 该服务器的运行时间即为完成卸载至此的所有计算任务时间.

(3)模拟退火算法规划卸载位置. 随机分配计算任务至服务器上, 根据任务完成时间模型计算每一个服务器的运行时间, 并取服务器中最大完成时间作为系统任务完成时间. 降低算法温度, 同时对任务分配位置进行随机调整, 计算新分配方式下的任务完成时间, 并依据Metropolis接受准则接受新解. 重复迭代直至达到终止条件, 输出任务最优分配位置.

模拟退火算法(SA)由Metropoils准则和退火过程两部分组成^[16]. 前者实现了SA算法如何在处于局部最优解时发生概率突跳并最终获得全局最优解, 是算法的基础; 后者则是SA算法寻找最优解的迭代过程. Metropoils准则是一种以概率接收新解, 而不是以完全确定规则的重要采样方法. 得益于Metropoils准则, SA算法可跳出局部最优解, 并寻找全局最优解.

4 任务完成时间模型

坝系包括多个坝区, 每个坝区采集节点都会定时产生一个计算量不同的计算任务, 坝系周边有若干个计算能力不同的边缘服务器与坝区连接. 该场景下, 所有节点产生的计算任务地位平等, 所有计算任务信息、边缘服务器计算能力信息可知. 其变量标识如表1所示.

计算任务由坝区节点卸载至连接的边缘服务器上进行计算, 任务完成时间共分为3个部分: 任务数据传输时间、任务平均等待时间、任务在边缘服务器上的执行时间、计算结果由边缘服务器向中心服务器上传时间. 任务完成时间模型如下.

(1)任务数据传输时间 $t_i^{\rm trans}$ : 由采集节点与服务器连接基站间的无线数据传输速率 ${B_j}$ , 及任务传输数据大小 ${d_i}$ 决定, 如式(1):

${{t}}_i^{\rm trans} = \frac{{{d_i}}}{{{B_j}}}$

(1)

(2)考虑到每个边缘服务器的计算资源是有限的, 任务量较多的时候会出现任务卸载等待及拒绝现象. 接下来, 分析任务卸载时的平均等待时间和卸载成功率.

假设, 任务到达率为 $\lambda $ , 将M/M/s/N/∞多服务器排队模型^[17]运用于任务卸载中, 卸载任务到达边缘计算服务器后以 队列的形式保存, 遵循先到达先服务的准则. 系统负荷水平ρ如式(2):

$\rho = \frac{\lambda }{{s \cdot \mu }}$

(2)

记P_i 表示排队系统的状态概率, 其中, $0 \le i \le N + s$ , 如式(3):

${P_i} = \left\{ \begin{aligned} & {\frac{{{{(s \cdot \rho )}^i}}}{{i!}} \cdot {P_0},\;0 \le i < s}\\& {{\frac{{{{(s \cdot \rho )}^i}}}{{(s!) \cdot {s^{(i - s)}}}} \cdot {P_0},\;s \le i < N + s}} \end{aligned} \right.$

(3)

根据正则性条件, 如式(4):

$\sum\limits_{i = 0}^{N + s} {{P_i}} = 1$

(4)

在ρ≠1的情况下, 计算出状态概率P₀, 如式(5):

${P_0} = \dfrac{1}{{\displaystyle \sum\limits_{i = 0}^{s - 1} {\dfrac{1}{{i!}} \cdot {{\left( {\dfrac{\lambda }{\mu }} \right)}^i} + \dfrac{1}{{s!}} \cdot \dfrac{1}{{1 - \rho }} \cdot {{\left( {\dfrac{\lambda }{\mu }} \right)}^s} \cdot \left( {1 - {\rho ^{(N - s + 1)}}} \right)} }}$

(5)

根据 P₀ 进一步计算得到队列中等待处理的任务的平均队长 $\overline {{L_q}} $ 和平均等待时间 $\overline {{t_{\rm wait}}}$ , 如式(6)、式(7), 其中平均等待时间根据排队论^[18]计算得到, 该参数表示从任务到达边缘计算服务器到被成功处理所需的平均等待时间.

$\begin{split} \overline {{L_q}} = &\frac{{{{\left(\dfrac{\lambda }{\mu }\right)}^s} \cdot \rho \cdot {P_0}}}{{(s!) \cdot {{(1 - \rho )}^2}}} \cdot \\& \left[ {1 - {\rho ^{(N - s + 1)}} - (1 - \rho ) \cdot (N - s + 1) \cdot {\rho ^{(N - s)}}} \right] \end{split}$

(6)

$\overline {{t_{\rm wait}}} = \frac{{\overline {{L_q}} }}{\lambda }$

(7)

(3)计算任务执行时间 $t_i^{\rm job}$ : 由任务计算量 ${c_i}$ , 及边缘计算服务器的计算能力 $f_j^E$ 决定, 如式(8):

${{t}}_i^{{\rm{job}}} = \frac{{{{{c}}_i}}}{{{{f}}_{{j}}^{{E}}}}$

(8)

(4)结果上传中心服务器时间: 由于边缘服务器所连接的坝区基站功率极大, 上传结果数据量相对较小, 因此选择对该部分时间忽略不计.

(5)任务完成时间: 由任务数据传输时间 $t_i^{\rm trans}$ 、任务平均等待时间 $\overline {{t_{\rm wait}}}$ 和计算任务执行时间 $t_i^{\rm job}$ 共同组成, 如式(9):

$t_i^{\rm total} = \left(\frac{{{d_i}}}{{{B_j}}} + \frac{{\overline {{L_q}} }}{\lambda } + \frac{{{c_i}}}{{f_{{l^i}}^E}}\right)$

(9)

其中, ${l^i}$ 表示计算任务 $Tas{k_i}$ 的卸载位置, ${l^i}$ ∈{1, 2,···,M}, ${l^i}$ =M即表示计算任务 ${T_i}$ 在编号为M的边缘服务器执行计算, 则任意一个边缘服务器完成卸载任务的总时间如式(10):

$t_j^{ES} = \sum\limits_{i \in {O_{{l^i}}}} {t_i^{\rm total}} = \sum\limits_{i \in {O_{{l^i}}}} {\left( {\frac{{{d_i}}}{{{B_j}}} + \frac{{\overline {{L_q}} }}{\lambda } + \frac{{{c_i}}}{{f_{{l^i}}^E}}} \right)} $

(10)

那么系统任务完成时间为所有服务器中的最长运行时间, 如式(11):

$ \left\{\begin{split} & {\rm max}\left({t}_{1}^{ES},{t}_{2}^{ES},\cdots,{t}_{M}^{ES}\right)\\& =\mathrm{max}\left({\displaystyle \sum _{i\in {O}_{1}}\left(\frac{{d}_{i}}{{B}_{j}}+\frac{\overline{{L}_{q}}}{\lambda }+\frac{{c}_{i}}{{f}_{1}^{E}}\right)},{\displaystyle \sum _{i\in {O}_{2}}\left(\frac{{d}_{i}}{{B}_{j}}+\frac{\overline{{L}_{q}}}{\lambda }+\frac{{c}_{i}}{{f}_{2}^{E}}\right)},\cdots,\right.\\& \;\;\;\left.{\displaystyle \sum _{i\in {O}_{M}}\left(\frac{{d}_{i}}{{B}_{j}}+\frac{\overline{{L}_{q}}}{\lambda }+\frac{{c}_{i}}{{f}_{M}^{E}}\right)}\right) \\& {\rm{s.t.}}\;{i \in [1, Num]},\;{{\sum\limits_{j = 1}^M {{O_j} = Num,\;j \in [1, M]} }}\\[-12pt] \end{split}\right. $

(11)

其中, i∈ ${O_j}$ 表示在编号为j的边缘服务器上运行的所有计算任务.

任务卸载成功率表示为任务被边缘计算服务器成功处理并接受服务的概率, 如式(12):

${P_{\rm success}} = 1 - \dfrac{{{{\left(\dfrac{\lambda }{\mu }\right)}^N} \cdot {P_0}}}{{(s!) \cdot {\lambda ^{(N - s)}}}}$

(12)

为最小化计算任务完成时间, 将原问题转化为有约束的目标函数如式(13):

$ \left\{ \begin{split} & {t_{\rm target}} = \min (\max (t_1^{ES},t_2^{ES},\cdots,t_M^{ES})) \\& {\rm{ s.t.}}\;\; C:{P_{\rm success}} \ge P_{\rm success}^{\rm{*}} \end{split} \right.$

(13)

其中, 约束 $C$ 要求任务的卸载成功率超过目标约束值 $P_{\rm success}^*$ .

5 基于模拟退火算法的任务卸载方法

基于SA算法最优化计算任务卸载位置, 即求目标函数(13)最优解的过程. 设置算法初始温度 ${T_0}$ 、终止温度 ${T_{\rm fin}}$ 、温度衰减系数 $\alpha $ 以及每个温度下的迭代次数 $\;\beta $ . 并假设存在n个淤地坝同时产生一个计算信息不同的计算任务, 生成任务计算量矩阵 ${C_{\rm task}}$ 与传输数据量矩阵 ${D_{\rm data}}$ , 分别如式(14)、式(15)所示.

${{{C}}_{{\rm{task}}}} = {[{c_1}\; \; {c_2}\; \; \cdots\; \; {c_i}\; \; \cdots\; \; {c_n}]^{\rm{T}}}\; \; ,i = 1,2,\cdots,n$

(14)

${{{D}}_{{\rm{data}}}} = {[{{{d}}_1}\; \; {{{d}}_2}\; \; \cdots \; \; {{{d}}_i}\; \; \cdots \; \; {{{d}}_n}]^{\rm{T}}}\; \; ,i = 1,2,\cdots,n$

(15)

结合式(1)、式(8)生成数据传输时间模型矩阵 ${A_{\rm trans}}$ 、任务执行时间模型矩阵 ${A_{\rm jobs}}$ , 如式(16)、式(17)所示.

$ {{A}}_{\rm{trans}}=\left[\begin{array}{cccc}\dfrac{1}{{{b}}_{1}}& 0& 0& 0\\ 0& \dfrac{1}{{{b}}_{2}}& 0& 0\\ 0& 0& \cdots& 0\\ 0& 0& 0& \dfrac{1}{{{b}}_{{m}}}\end{array}\right], i=1,2,\cdots,m$

(16)

$ {{A}}_{\rm{jobs}}=\left[\begin{array}{cccc}\dfrac{1}{{f}_{1}^{E}}& 0& 0& 0\\ 0& \dfrac{1}{{{f}}_{{2}}^{{E}}}& 0& 0\\ 0& 0& \cdots& 0\\ 0& 0& 0& \dfrac{1}{{f}_{m}^{E}}\end{array}\right], i=1,2,\cdots,m$

(17)

通过随机函数生成一个n×m的0-1矩阵记为初始解向量矩阵 ${Z_{\rm old}}$ , 其中定义解向量矩阵 ${Z_{\rm old}} = {({{\textit{z}}_{ij}})_{n \times m}}$ , ${{\textit{z}}_{ij}} \in \{ 0,1\}$ , $\displaystyle \sum\limits_{i = 1}^m {{{\textit{z}}_{aj}}} = 1$ , 其形式如式(14), 向量矩阵Z表示所有设备的计算方式及任务卸载位置. 解向量 $j=1,2,3, \cdots,m$ 表示计算任务是否选择在边缘计算服务器1,2,···,m上执行. ${{\textit{z}}_{ij}}$ =0表示计算任务 ${T_i}$ 不会选择该方式执行, ${{\textit{z}}_{ij}}$ =1表示计算任务 ${T_i}$ 选择该计算方式执行计算.

$ {Z}=\left[\begin{array}{ccccc}1& 0& 0& 0& 0\\ 0& 1& 0& 0& 0\\ 0& 0& 0& 0& 0\\ 0& 0& 0& 1& 1\\ 0& 0& 1& 0& 0\end{array}\right], {\textit{z}}_{ij}\in \{0,1\},{\displaystyle \sum _{j=1}^{M}{\textit{z}}_{aj}=1}$

(18)

式(18)表示任务1在编号为1的边缘服务器上运行, 任务2在编号为2的边缘服务器上运行, 任务3在编号为5的边缘服务器上运行, 任务4、5在编号为4的边缘服务器上运行.

结合线性代数相关内容与式(11), 获取完成时间跨度矩阵 ${T_{\rm time}}$ , 如式(19).

$ \begin{split} {{{T}}_{\rm time}} & ={D_{\rm data}}*{Z_{\rm old}}*{A_{\rm trans}} + {C_{\rm task}}*{Z_{\rm old}}*{A_{\rm jobs}} \\& = {\left[ {{{t}}_1^{ES}\;\;{{t}}_2^{ES}\;\;\cdots\;\;{{t}}_{{i}}^{ES}\;\;\cdots\;\;{{t}}_{{M}}^{ES}} \right]^{{T}}},i \in \{ 1,2,\cdots,M\} \end{split} $

(19)

其中, $t_i^{ES}$ , 表示第i个服务器完成卸载至此所有任务的运行时间, 令 ${T_{\rm time}}$ 矩阵中最大值 $t_{\max }^{ES}$ 为系统任务完成时间 ${t_{\rm old}}$ . 同时随机交换原解向量矩阵 ${Z_{\rm old}}$ 中3个元素的位置, 生成新的解向量矩阵 ${Z_{\rm new}}$ , 并计算该解矩阵下的任务完成时间 ${t_{\rm new}}$ . 并求出完成时间跨度差, 如式(20).

$\Delta {{t}} = {{{t}}_{\rm new}} - {t_{\rm old}}$

(20)

若Δt<0, 则一定接受新解 ${Z_{\rm new}}$ , 若Δt>0, 以Metropoils准则接受新解 ${Z_{\rm new}}$ , 如式(18)接受新解 ${Z_{\rm new}}$ . 判断此次迭代是否达到该温度下迭代次数上限, 若没有达到次数上限, 则重复进行位置交换与完成时间; 若达到该温度下的迭代次数上限, 则降低算法温度, 如式(21).

${{{T}}_0} = {{{T}}_0}{{*}}\alpha $

(21)

判断是否达到规定的最低温度; 若未达到最低温度则降低当前温度, 重置迭代次数, 并重复上述迭代过程, 若达到规定的最低温度, 则输出当前解向量矩阵, 算法结束. 如图2所示, 表示一次迭代过程.

6 实验仿真与结果分析 6.1 性能评价标准

利用模拟退火算法建立计算任务调度策略的主要目的为降低计算任务完成时间即任务执行时间跨度, 使得系统的风险预警更具备时效性. 此外, 为综合评定算法性能, 增加任务总执行时间、计算任务调度策略制定时间以及系统负载均衡共同作为算法性能评价标准.

各指标的物理意义分别如下:

(1)任务执行时间跨度: 即系统第一个任务开始至最后一个任务完成的时间跨度.

(2)任务总执行时间: 即所有任务在边缘服务器上的执行时间总和.

(3)计算任务调度策略制定时间: 即任务调度服务器收集到计算任务信息后, 制定所有计算任务卸载位置的总时间.

(4)系统负载均衡: 评价一个网格计算平台是否分配均衡, 本文将采用各个节点的标准方差进行评价. 其评价公式如式(22), 其中M表示边缘服务器个数, ${X_i}$ 表示第i个边缘服务器被调用的次数, $\overline {{X_i}} $ 表示所有边缘服务器平均被调用的次数, σ表示系统负载标准方差, 其值越小, 表明系统负载越均衡.

$ \sigma =\sqrt{\frac{{\displaystyle \sum _{{i}=1}^{{M}}({{X}}_{{i}}-\overline{{X}}{)}^{2}}}{{M}}}$

(22)

6.2 结果分析

实验中设置计算任务量 ${c_i}$ 在区间[5, 20]随机生成, 传输数据量 ${d_i}$ 在区间[10, 50]随机生成. 边缘服务器的计算能力在区间[2, 3]随机生成, 节点与边缘服务器的通信带宽 ${B_j}$ =1000. SA算法初始温度 ${T_0}$ =200, 终止温度 ${T_{\min }}$ =3, 每个温度下的迭代次数为30, 冷却率取α=0.99.

(1)不同任务数量下, SA算法与Min-Min算法的性能比较

为研究两种算法在任务数量不同时的性能差异. 实验边缘服务器数量设置为50, 任务数量在区间[100, 1000]以100递增取值, 共计10组实验, 每组实验重复10次取平均值. 图3的4个子图分别表示两种算法在不同任务数量下的4种评价指标性能差异.

由图3(a)、图3(b)可知, 采用SA算法进行任务调度, 可有效降低系统任务执行时间跨度、任务执行时间总和, 且当计算任务量越小, SA算法求出的解越接近精确解. 其原因是算法初始化后, 迭代次数将被确定, 解矩阵越小, SA算法越接近穷举法, 因此算法的时间性能越好. 由图3(c)可知, 为降低任务执行时间跨度, SA算法将会为计算能力较强的服务器分配更多的计算任务, 因此其算法的负载均衡性能会有所损失. 由图3(d)可知, 虽然SA算法存在较为明显的时间性能优势, 但其任务调度策略制定时间相比于Min-Min算法也会增加, 且利用SA算法的制定调度决策的时间将呈现线性增加, 贴合SA算法的时间复杂度O(kl(n)), 其中k为每个温度下的迭代次数, l(n)为问题规模的多项式函数.

(2)不同服务器数量下, SA算法与Min-Min算法的性能比较

为研究两种算法在边缘服务器数量不同时的性能差异. 实验边缘服务器数量在区间[30, 100]以10递增取值, 共计8组实验, 每组实验重复10次取平均值. 图4(a)至图4(d)分别表示两种算法在不同服务器数量下的4种评价指标性能差异.

由图4(a)可知, 增加参与计算的边缘服务器可有效降低两种算法的任务执行时间跨度, 且边缘服务器的数量越多, SA算法的性能优势将越明显, 其原因为: 在增加边缘服务器数量时, 虽然两种算法均会降低任务完成时间跨度, 但由于SA算法更加精确, 因此下降趋势较Min-Min算法更加明显. 由图4(b)可知, 当参与计算的服务器增加时, Min-Min算法将会分配给计算能力较差的服务器分配计算任务, 因此任务执行时间总和将会增长. 通过图4(c)可知, 增加服务器数量会改善系统整体的负载均衡性能, 但本文采用SA算法制定任务调度策略的目的是降低任务执行时间跨度, 势必会提高计算能力较强服务器的负载, 因此系统负载均衡性能将会有所不足. 由图4(d)可知, 增加边缘服务器数量将会扩大SA算法解矩阵规模, 提高SA算法时间复杂度, 导致求解时间增加.

7 结论与展望

针对淤地坝监测与预警系统时效性问题, 设计了基于模拟退火的多个边缘计算服务器相互协作任务调度方法. 根据任务调度分析, 建立任务完成时间模型. 并说明了在淤地坝计算任务的执行没有优先级时, 应用模拟退火算法制定调度策略可以达到该场景下降低完成时间跨度的任务调度目的, 并给出了调度优化问题的解决步骤. 最后通过仿真实验, 验证了基于模拟退火的调度方法符合场景需求, 可以达到预期的效果.