第一作者：Chen Yu（南京大学计算机软件新技术国家重点实验室）

通信作者：Zhang Sheng（南京大学计算机软件新技术国家重点实验室），Jin Yibo（南京大学计算机软件新技术国家重点实验室）

摘要：

基于众包的动态调度算法，用于优化视频分析任务中工作人员和资源配置的选择，从而提升平台的整体利润

众包平台的核心balance

众包平台面临的挑战

众包将手动注释，图像标记等任务分发给各种移动用户（worker）来执行，并且给worker发放奖励，奖励取决于worker执行结果的质量。但这种规划常常面临以下这些挑战：

image-20241212155508794

图为计算传输的能耗波动图，但我认为用户计算任务的时间会比较长（可能至少1min？）总之应该不是按几秒来算的，图中尤其是传输产生的能耗可以发现其均值较为稳定，所以worker执行任务的时间都是几秒几秒的吗，如果不是那有必要考虑这些吗

现有的方法要么没有考虑动态可用性，要么缺少任务配置与利润的联合优化，要么缺少配置和worker的联合优化

问题设置

时间

将众包系统按时槽（Time Slot）进行划分并记为$\mathcal{T}={1,...,T}$，并且每个Slot划分为多个阶段（Epoch）$\mathcal{J}^t$ 在每个时槽$t$的阶段$j$中可用的worker被记为 $\mathcal{N}_j^t$

任务划分

在每个时槽都有需要完成的任务集合，记为$\mathcal{M}^t={s_1^t,s_2^t,...,s^t_{M_t}}$，共$M_t$

由于视频分析的任务通常比较大，因此作者将任务分为多个子任务以匹配移动设备的运行环境。每个任务$s^t_m$划分的子任务集合记为 $\mathcal{K_m^t={s_{m,k}^t|k=1,2,...,K_m^t}}$，共$K_m^t$（子任务是平台划分的吗？）

worker任务分配

每个worker假定只配一个CNN model，在worker被选定的时候会同时确定该worker上（所有）CNN的输入分辨率 $r_i$，假设所有待分析视频的原本分辨率都很大，则$r_i$是经过下采样以适配worker运行环境后的分辨率。子任务$x^t_{m,k}$是否分配给worker $n$记为$x^t_{m,k,n}$，并且子任务选择的帧率为 $f_{m,k}^t$。

任务完成精度

针对任务的完成精度，作者通过先前的研究和自己的实验发现，精度与分辨率和帧率的关系可以被建模为凹函数（Concave Function），并且分辨率和帧率对于精度的影响是独立的，因此针对$t$ slot $j$ epoch 的子任务$s_{m,k}^t$，其任务完成得精度可以按照如下公式计算
$$
a_{m,k}^t=\epsilon_m^t(\sum_{n=1}^{|\mathcal{N_j^t}|}x_{m,k,n}^tr_n)\phi_m^t(f_{m,k}^t)
$$
这里$\epsilon_m^t(resolution)$和$\phi_m^t(frame\ rate)$就分别是分辨率和帧率对应的凹函数，将worker的分辨率求和并应用$\epsilon_m^t$凹函数，后由于帧率和分辨率是单独影响，所以这里直接让帧率应用$\phi_m^t$凹函数后相乘*（这里有一个疑问就是，给某个子任务分配的worker越多，带入到凹函数$\epsilon_m^t$中的数值就会越大，是不是应该先将分配的worker的分辨率先求和呢）*

因此可以简单求和取平均计算得到所有任务的整体平均准确率
$$
a^t=\frac{\sum_{m=1}^{M^t}\sum_{k=1}^{K_m^t}a^t_{m,k}}{|M^t||K_m^t|}
$$

worker能量消耗

worker消耗的能耗前文主要讲了有传输能耗和计算能耗

所以总能耗$e_n^t$就是计算能耗$e_n^{c,t}$和传输能耗$e_n^{d,t}$之和，且公式里的bit传输消耗系数$\gamma_{m,n}^t$和每帧计算消耗系数$\mu_{m,n}^t$是随机的*（随机的？）*

众包利润

用凹函数（Concave Function）$G_m^t(a)$来建模收入函数*（为什么是凹函数）*，这里$a$就是任务$s_m^t$的完成精度。所以在时槽t内获取的来自任务发布者的奖励公式为：
$$
I^t=\sum_{m=1}^{M^t}\sum_{k=1}^{K_m^t}G_m^t(a_{m,k}^t).
$$
也就是所有子任务精度带入凹函数中求和的结果

在移动众包中，worker获得的酬劳主要取决于其能源消耗，设$\omega_n$是worker n定价的单位能量消耗的费用，则时槽$t$内众包平台支出的总费用为：
$$
O^t=\sum_{j=1}^{|\mathcal{J^t}|}\sum_{n=1}^{|\mathcal{N_j^t}|}\omega_ne_n^t
$$
也就是worker $n$ 在时槽$t$上的总能耗，然后对worker $n$和时槽t的所有epoch求和*（这里需要注意epoch在之前计算中都是怎么被考虑的）*。最后，平台的利润就是简单的：
$$
U^t = I^t - O^t
$$

问题建模

$$
\mathbb{P}1\ \ :\underset{x,f}{max}\ \underset{T\to+\infin}{lim}\ \frac{1}{T}\sum{t=0}^TU^t \
\texttt{最大化无限时间长度上的平均利润，可控变量为分配变量x和选择给每个子任务的帧率}\
s.t.\ \ x_{m,k,n}^t={0,1},\ \forall t,m,k,n \
\texttt{分配变量x是bool变量} \
\sum_{j=1}^{|\mathcal{J}^t|}\sum_{n=1}^{|\mathcal{N}j^t|}x{m,k,n}^t=1,\ \forall t,m,k \
\texttt{时槽t epoch j的每个子任务只分配给一个worker} \
1\le f_{m,k}^t \le F_m^t, \forall t,m,k \
\texttt{众包平台选择的帧率必须小于视频的原始帧率} \
\underset{T\to +\infin}{lim}\ \frac{1}{T}\sum_{t=0}^T a^t \ge A^{min}. \
\texttt{所有任务整体平均准确率长期来看需要稳定在某阈值之上} \
$$

由于需要保证长期准确率高于阈值，则需要分析不同时槽$t$的worker选择$x$和帧率选择$f$（也很难根据经验预测），因此：

李雅普诺夫优化

为什么采用

李亚普诺夫优化的关键优势之一是能够在每个时间周期做出决策，而不需要全局信息或对整个问题进行精确求解。这对于解决具有复杂约束的动态优化问题非常有用。通过这种方法，系统能够在不需要大量计算和全局信息的情况下，基于当前状态做出实时的近似最优决策。

队列积压函数

定义虚拟精度亏损队列，队列初始积压$q(0) = 0$，$q(t)$代表在时槽$t$偏离目标精度的程度，积压函数变化公式：
$$
q(t+1)=[q(t)+A^{min}-a^t]^+ \
[·]^+代表max(·,0),因此还可以得到 \
q(t+1) \le q(t) + A^{min} - a^t \
A^{min}是设定需要长期保证的准确率，a^t是当前时槽达到的平均准确率 \
$$
，如果为了追求利润，平台大大降低worker的消耗，就会导致任务完成精度很低，精度损失很大，导致队列积压$q(t)$增大。为了约束长期不偏离目标精度，定义二次李亚普诺夫函数
$$
L(q(t))=\frac{1}{2}(q(t))^2
$$
，代表队列积压程度。为了保持队列的稳定性，需要不断将$L(q(t))$的值压低。

李亚普诺夫漂移

定义单时槽$t$的李雅普诺夫漂移（Drift）：
$$
\begin{aligned}
\Delta(q(t)) &= \mathbb{E}[L(q(t+1))-L(q(t))|q(t)] \
&\le \frac{1}{2}\mathbb{E}[(q(t)+A^{min}-a^t)^2-q^2(t)|q(t)]\
&(带入积压函数变化公式) \
&= \frac{1}{2}(A^{min}-a^t)^2+q(t)\mathbb{E}[(A^{min}-a^t)|q(t)] \
&(展开得到) \
&\le B+q(t)\mathbb{E}[(A^{min}-a^t)|q(t)], \
&更换常数
\end{aligned}
$$
B的定义为$B = \frac{1}{2}(A^{min}-a^{min})^2$，是常数，$a^{min}$代表所有时槽的平均精度中最低的那个*（历史经验数据吗）*。

将李雅普诺夫漂移加入到众包利润的优化函数中，定义带惩罚项的优化目标为
$$
\Delta(q(t))-V·\mathbb{E}[U^t|q(t)],
$$
这里的$V$是正参数，用来调节分析精度的提升和众包利润之间的balance，在论文中有具体证明$V$的线性变化会引起队列积压量的线性变化。

将$\Delta(q(t))$展开得到
$$
\Delta(q(t))-V·\mathbb{E}[U^t|q(t)] \le \
B+q(t)\mathbb{E}[A^{min}-a^t|q(t)]-V·\mathbb{E}[U^t|q(t)]
$$
与其直接最小化带惩罚项的优化目标，我们选择最小化这个优化目标的上界，也就是：
$$
\mathbb{P}2:\underset{x,f}{max}\ \ q(t)·a^t+V·U^t \
s.t.还是前文中的s.t.但不包括最后的长期准确度平均需要大于A^{min} \
因为准确度的要求已经被加入到了优化目标中 \
当积压量q(t)较大时，则需要更加注意对于平均准确率a^t的优化 \
$$
现在对于新问题的求解就只需要当前状态的输入就可以了。将$\mathbb{P}2$展开有：
$$
\mathbb{P}2:\underset{x,f}{max}\sum{m=1}^{M^t}\sum{k=1}^{K_m^t}H^t(m,k)\
=\sum{m=1}^{M^t}\sum_{k=1}^{K_m^t}\left{ \frac{q(t)a_{m,k}^t}{|M^t||K^t_m|}+V[G_m^t(a_{m,k}^t)-\sum_{j=1}^{|\mathcal{J}^t|}\sum_{n=1}^{|\mathcal{N}j^t|}C{m,k,n}]\right}, \
左边将a^t展开为了所有子任务的求和平均\
右边将U^t展开为了任务精度报酬-支付工资\
$$
其中$C_{m,k,n}$可以继续展开为
$$
C_{m,k,n}=\omega_n(\mu_{m,n}^tx_{m,k,n}^tf_{m,k}^t+\gamma_{m,n}^t\alpha(x_{m,k,n}^t r_n)^2f_{m,k}^t)
$$
当worker的选择$x$固定后，可以独立地对每个子任务设置使用的帧率$f_{m,k}^t$，使得每个子任务的最大的$H^t(m,k)$相加得到目标函数整体的最大值。如何求解呢，在固定worker的选择后，定义集合
$$
\mathcal{F}{m,k}^t={f{m,k}^t|\partial H^t(m,k)/\partial f_{m,k}^t=0},
$$
也就是最优解的帧率集合，解得
$$
f_{m,k}^t=\underset{f_{m,k}^t\in \mathcal{F}^t_{m,k}∪{1,F_m^t}}{arg\ max}H^t(m,k)
$$

在确定worker的分配以后，$\mathbb{P}2$就可以对每个子任务单独计算了，我们假定$H^t(m,k)$的值为$z{m,k}^t$，展开$H^t(m,k)$中的$a^t$得到类似回报函数的表达式
$$
z_{m,k}^t(n,f_{m,f}^t)=\frac{q(t)\epsilon_m^t(r_n)\phi_m^t(f_{m,k}^t)}{|M^t||K_m^t|}+V[G_m^t(a_{m,k}^t)-\omega_n(\mu_{m,n}^tf_{m,k}^t+C_n^d\gamma_{m,n}^t\alpha(r_n)^2f_{m,k}^t)] \
由于每个子任务只会分配给某一个worker\
所以a^t的展开式中的r_n求和项就变成对应worker的r_n了
$$
由于$z_{m,k}^t(n,f_{m,f}^t)$的值依赖于$\mu_{m,n}^t$和$\gamma_{m,n}^t$，因此采用多臂赌博机算法

多臂赌博机

为什么采用

多臂赌博机（Multi-Armed Bandit, MAB）方法是一种用于在不确定环境中进行决策的经典算法框架，特别适合处理探索和利用之间的权衡问题。由于两个随机变量$\mu_{m,n}^t$和$\gamma_{m,n}^t$是随机的或动态变化的，因此需要通过一种机制来动态学习这些值，多臂赌博机的核心目标正是通过不断尝试不同的探索，并在获得反馈后调整选择策略，从而在不确定性条件下找到最优解。

算法流程

image-20241223174449258

  1. 输入任务帧率限制$F_m^t$，最小精度$A^{min}$，能耗定价$\omega_n$，准确率回报函数$G_m^t$

  2. 从未完成的子任务集合$\mathcal{L}m^t$中选择一个子任务$s{m,k}^t$，表示即将对该任务进行分配

  3. 对worker状态进行检查，如果存在新的worker $\bar n$，则直接将任务分发给$\bar n$并且将观察到的$\bar n$的传输能耗随机变量和计算能耗随机变量 $\widetilde\mu_{m,\bar n}^t$和 $\widetilde\gamma_{m,\bar n}^t$赋值给$\bar n$的 $\bar \mu_{m,\bar n}^t$和 $\bar \gamma_{m,\bar n}^t$，同时将该worker已完成任务数 $\theta_{m,\bar n}^t$设为1（也就是老虎机被玩的次数）并且更新所有已完成的任务数（也就是全局玩老虎机的次数）

  4. 如果所有worker都已经有随机变量的记录了，则计算让$z_{m,k}^t$最大化的$\bar n$和$\bar f$。

    由于之前提到了优化目标已经是最大化$z_{m,k}^t$，因此这里可以将$z_{m,n}^t$视作reward。这里还需要加上置信度上界，也就是式子中的$\sqrt{\frac{2\ ln\ \mu^t_{m,n}}{\theta_{m,n}^t}}$。它是对不确定性的度量，当某个worker选择的次数越多，那么它的$\theta_{m,n}^t$就会越大，使得不确定性减小；同样的，当其他worker不断被选择，那么式中的$\mu_{m,n}^t$就会越大，使得不确定性增大。自然对数是对于时间推移的模拟，也就是随着时间增大，对不确定性的影响将会越来越小。因此，具有较低reward的worker和已经被选择了更多次的worker就会更不容易被选中。

    将子任务分配给选出的worker $\bar n$，并且得到那个子任务下worker $\bar n$的传输能耗和计算能耗的随机变量 $\widetilde\mu_{m,\bar n}^t$和 $\bar \gamma_{m,\bar n}^t$，随后按照比例对worker 的$\bar \mu_{m,\bar n}^t$和 $\bar \gamma_{m,\bar n}^t$进行更新，比例如下：
    $$
    \bar \mu_{m,\bar n}^t \leftarrow \frac{\bar \mu_{m,\bar n}^t\theta_{m,\bar n}^t+\widetilde \mu_{m,\bar n}^t}{\theta_{m,\bar n}^t+1} \
    \bar \gamma_{m,\bar n}^t \leftarrow \frac{\bar \gamma_{m,\bar n}^t\theta_{m,\bar n}^t+\widetilde \gamma_{m,\bar n}^t}{\theta_{m,\bar n}^t+1} \
    $$
    最后更新该worker被选择的次数 $\theta_{m,\bar n}^t \leftarrow \theta_{m,\bar n}^t +1$

  5. 输出子任务$s_{m,k}^t$的选择策略以及对应的reward $z_{m,k}^t(\bar \mu_{m,\bar n}^t,\bar \gamma_{m,\bar n}^t)$。

实验部分

实验设置

数据集来自AI City Datasets 2019的视频，使用YOLOv3进行视频分析并且与其他算法进行对比，输入帧的大小包括360p，540p，720p，840p，960p，1080p，原始帧率30fps

worker的可用性模拟来自于Users Active Time Prediction数据集，并且将worker的计算能耗设定为 $N(5,0.5)$ 焦耳每帧， 传输能耗设定为 $N(5,0.5) \times 10^{-6}$ 焦耳，并且设置 $\alpha = 1$，$\omega_n ∼ U\ (0,1)$。

作者将自己的算法和4种备选方案进行对比，分别是：

实验结果

动态调整的帧率和分辨率

image-20241224011518610

在测试样例中一共包含两个视频分析任务，他们的前20时槽和后20时槽的分析目标大小不同，因此需要采用变化的分辨率，并且前后目标运动的速度也不一样，因此帧率也需要进行动态的调整。（大目标采用低分辨率，慢运动速度采用低帧率）

参数影响

image-20241224012113400

图$a$展示的是$V$（精度和利润balance中对于利润的重视程度）对于队列积压平衡的影响，可以看到$V$越大，就越需要更大的时间进行平衡，$V$减小，则会更加注意完成的准确性，使得队列更容易趋于稳定。

图$b$展示的是$A^{min}$（众包平台承诺的准确度标准）对于队列积压平衡的影响，可以看到$A^{min}$较高时，就更容易造成队列积压，因此最终收敛值就很大，$A^{min}$较小时，则容易满足精度约束从而造成更少的积压，因此最终收敛值就很小。

图$c,d$展示的是在不同worker数目和子任务数目下LOL与其他两种对比算法的利润和精确度区别。可以发现LOL表现类似于两种版本的平均体，并且相比于利润优先的版本，LOL基本可以保证精度领先的情况下获取到相同的利润。

子任务选择上的性能对比

image-20241224014933826

图$a$展示了worker不同的variance（也就是计算能耗和传输能耗分布的方差值）下选择到次优（非最优）worker的概率（模型对于每个worker都已经执行过了一次子任务后）。可以发现当方差为0时，赌博机学习到的是精准的能耗随机变量，因此总是能够选出最优的worker，方差非0时选择次优worker的概率也会随着LOL的学习次数急剧下降。

图$b,c$展示了不同worker和子任务数目，给子任务选择worker来获取更高的Goal Value的场景下，相比于探索优先和保守策略，LOL都有巨大的优势（平均提升68%）。

和原始赌博机算法的对比

image-20241224020700240

这里引入了worker可用性的变动，在15，30 Epoch 的时候最优worker会离开，并且加入新的最优worker。由于原始的赌博机算法在出现worker（也就是赌博机）变动的时候会重启，而作者的赌博机保留了worker对于随机变量和完成任务的记录，因此LOL相比LOL-M很快就能找到最优的工人并且得到更高的目标函数值。

作者工作

整个问题属于非线性整数规划，考虑了视频的资源质量权衡和工人的动态可用性，将长期时间对精度的约束使用李雅普诺夫优化方法转化为子任务最优化问题，并且使用波动多臂老虎机来学习预测资源使用的随机性，根据worker的动态可用性和配置以最小资源消耗将任务进行分配，实现平台长期的利润最大化。