Handscript of 《Auction-Based VM Allocation...》

Gao, Guoju, et al. "Auction-based VM allocation for deadline-sensitive tasks in distributed edge cloud." IEEE Transactions on Services Computing (2019).

我们形式化了三层边缘云结构中对期限敏感的任务的竞争性虚拟机资源分配问题，并提出了基于拍卖的虚拟机资源分配（AVA）机制，该机制主要由贪婪中标选择算法和支付确定算法组成.
我们证明了AVA的中标选择问题是NP难问题。我们首先去除最后期限约束，然后将三层边缘云结构转换为两层边缘云结构。在此基础上，提出了一种贪婪中标选择算法，并进一步分析了其近似比。
我们还设计了一个真实支付判定算法。然后，我们证明了AVA机制具有真实性、个体合理性和计算效率。
我们对真实轨迹进行了广泛的模拟，以评估所提出的 AVA 机制的性能。结果表明，AVA不仅比对比算法取得了更好的社会福利性能，而且保证了真实性、个体理性和计算效率。

模型 & 问题描述

三个身份

ECN（CC）
platform
users

三方交互

当移动用户希望租用虚拟机资源来运行其对期限敏感的云计算应用程序时，它首先会生成一个请求，然后将请求提交给平台。该请求由用户的最大可容忍延迟（即截止日期）、所需的 VM 资源量和输入数据量组成。

我们使用$r_i = \{T_i,A_i,I_i\}$来表示第 i 个移动用户的请求，其中 T_i、A_i 和 I_i 表示截止日期、VM 资源总量和输入数据量。此外，所有请求的集合用 R 表示。 \[ r_i = \{T_i,A_i,I_i\} \]
平台会定期收集每个ECN的状态信息，然后公示给提交请求的移动用户。状态信息包括几个主要参数：VM资源容量、带宽、租用VM资源的单位成本和向CC传输数据的单位成本。

这里，ECN的带宽包括与CC相关的带宽和与移动用户相关的带宽。

\[ s_j=\{L_j,c_j^v,c_j^t,b_j^上,b_j^下\} \]

我们用$s_j=\{L_j,c_j^v,c_j^t,b_j^上,b_j^下\}$表示第 j 个 ECN 的状态信息，其中 L_j 表示 ECN (s_j) 的 VM 资源容量。$c_j^v$和$c_j^t$表示 VM 资源的单位成本、分别为向CC传输数据的单位成本。$b_j^上$表示VM to CC的带宽，而$b_j^下$表示s_j和用户之间的带宽。所有 ECN 的集合用 S 表示。此外，我们让 $c^v_0$表示 CC 中 VM 资源的单位成本。这里，$c^v_0$ 远小于$ c^v_j$（对于S中的所有$s_j$）。
然后，移动用户根据状态信息对ecn进行不同的取值。同时，移动用户确定每个ECN的出价。对于每个请求r_i，我们使用$b_{ij}$和$v_{ij}$分别表示第i个移动用户对第j个ECN的出价和估值。所有出价的集合由B表示。移动用户将向平台发送他们的出价。

注意：

这里的b_ij是用户为了得到ECN的资源锁支付的金额，v_ij是用户在进行使用时对于这些资源的真实评估值，这个值只有用户自身知道，用户可能会操纵b_ij，导致平台和ECN获得更少的奖励，所以整个Model要满足移动用户不会操纵其出价
该平台根据收到的来自移动用户的出价和请求，确定拍卖的获胜者，为获胜者做出调度决策，并计算相应的付款。
注意：
- 每个请求只能分配给一个ECN
- 每个ECN在容量和期限限制下可以服务多个请求
- 中标：首先上传的ECN，然后ECN要么自己完成任务，要么上传CC
移动用户将输入数据上传到 ECN 以运行他们的云计算应用程序，然后支付相应的奖励。根据中标的调度决策，ECN决定将一些任务上传到CC并支付CC

为了方便处理，我们只允许一个用户在一个拍卖环节内发送一个请求（如果有多个请求的需求，可以等价为多个虚拟用户）我们使用d_ij来表示请求与ECN之间的延迟，计算公式如下： \[ d_{ij}=\left\{ \begin{aligned} &\frac{I_i}{b_j^下}；&(r_i \to s_j)\\ &\frac{I_i}{b_j^下}+\frac{I_i}{b_j^上}；&(r_i \to s_j \to CC) \end{aligned} \right. \] 上式表明ECN可以单独完成任务，并不需要进行上传；下式表示ECN无法单独完成任务，需要CC的参与；$I_i$指的是输入数据量+输出数据量。所以$d_{ij}$包括了从ECN(CC)下载数据到user的延迟。

中标选择问题WBS

我们定义$\Phi$为WBS问题的解集，称为中标集$b_{ij} \in \Phi$
$\Phi^E$为ECN可以单独解决的中标集合
$\Phi^C$表示需要上传到CC的中标集合
$\Phi^C \bigcap \Phi^E = \oslash$
$\Phi^C \bigcup \Phi^E = \Phi$

中标的总估值 - 总成本 \[ \sum_{b_{ij} \in \Phi^E}(v_{ij}-A_i·c_j^v) + \sum_{b_{ij} \in \Phi^C}(v_{ij}-A_i·(c_j^t+c_0^v) ) \]

$A_i·c_j^v $ 表示ECN节点s_j执行请求r_i的花费
$A_i·(c_j^t+c_0^v)$表示请求传输到CC以及CC计算的成本

\[ max \sum_{b_{ij} \in \Phi^E}(v_{ij}-A_i·c_j^v) + \sum_{b_{ij} \in \Phi^C}(v_{ij}-A_i·(c_j^t+c_0^v) ) \] 方程4可以等价为： \[ max \sum_{b_{ij} \in \Phi^E}(b_{ij}-A_i·c_j^v) + \sum_{b_{ij} \in \Phi^C}(b_{ij}-A_i·(c_j^t+c_0^v) ) \]

PD问题

PD问题是确定每次中标的付款，使整个拍卖模型满足真实性和个体理性

Truthfulness

定义$p_{ij}(b_{ij})$为由拍卖机制的支付计算算法确定的相应支付

用户对真实出价和不真实出价的报酬率分别为$v_{ij}-p_{ij}(v_{ij})$，$v_{ij}-p_{ij}(b_{ij})$ \[ v_{ij}-p_{ij}(v_{ij}) > v_{ij}-p_{ij}(b_{ij}) \] 拍卖机制的真实性可以确保每个用户报告其真实估值，因为不真实的出价将导致更糟糕的回报。

Individual Reationality

user的支付不应该超过其对应的估计值，即$v_{ij} > p_{ij}(b_{ij})$

在这里，每个移动用户的真实估值必须涵盖其相应的支付。

Efficiency

具有计算效率的算法比具有高计算复杂度的最优算法==更重要==

AVA 机制

证明是NP-Hard问题

假设只有一个ECN。并且该ECN无法上传CC，公式限制如下： \[ max \sum_{b_{i1} \in \Phi^E}(b_{i1}-A_i·c_1^v) \] \[ \sum_{b_{i1} \in \Phi^E}A_i <L_1 \]

这个可以直接映射到0-1背包问题，所以最简单的情况就是NP难问题，复杂情况一定是NP难问题。

WBS问题的基础解

First Phase

由于上传CC的传输耗时肯定高于上传ECN的耗时，所以我们将上传ECN为good传输延迟，而CC为bad传输延迟，根据T_i与两个传输延时的关系，我们可以更新$B$、$S$集合

我们将移除那些不能满足ddl限制的bid，并且添加一些虚拟bids和ECNs，如果这个ddl比bad传输延迟要大。主要有以下三种情况

如果$ddl < good$，就删除这个bid，因为无论如何不能满足截止时间约束
如果$good < ddl < bad$，我们不做处理
如果$ddl > bad$，我们就会创建一个虚拟的ECN($s_{j*}$)和虚拟的投标($b_{ij*}$) \[ s_{j*}=\{L_{j*}=A_i，c_{j*}^v=c_j^t+c_o^v，c_{j*}^t = b_{j*}^上= b_{j*}^下 = 0\} \] 新添加的ECN，资源容量 = 请求i所需要的容量，VM资源成本为一开始的上传CC成本+CC中的VM资源成本，虚拟的上传CC成本 = 0，带宽都为0。

在这里，生成虚拟ECN和bid的过程意味着从边缘云计算场景中删除CC，并将三层边缘云结构转换为两层结构。

Second Phase

我们集中讨论了具有容量限制的WBS问题。我们首先将中标选择建模为一个带有0-1背包约束的n对1加权二部图匹配问题。由于容量限制，该问题是NP难问题，因此我们采用贪婪策略来确定最大匹配，其总权重约为最大。

建立图： \[ G = \{R,\widehat{S},\varepsilon:\widehat{B}\} \]

$R$和$\widehat{S}$是两个独立的点集；
$\varepsilon$指的是图中的边，其中包含了边$<r_i,s_j>$
$\widehat{B}$是$b_{ij}$的集合，每一个bid对应一个边
对于每一个请求r，其需要的资源容量就是背包问题中每个物品的重量
每一个s的VM资源容量就相当于背包的大小
每一条边都有自己的权重，即weight（每个资源的social welfare） \[ w_{ij} = \frac{b_{ij}}{A_i} - c_j^v \]

每一个unit的需求得到的利益（目标函数÷$A_i$）

由于我们在前文已经将虚拟的ECN和bid放入，将CC排除，所以$\Phi^C = \oslash$，$\Phi^E = \Phi$

WBS目标函数转换如下： \[ max \sum_{b_{ij} \in \Phi}(b_{ij}-A_i·c_j^v) \]

第二步，就是在图的基础上，我们贪婪的选择一些边来形成具有近似最大权重的G的最大匹配：在每一轮中，我们选择权重最大的边。由以下两种情况：

$A_i < L_j$：即ECN的剩余容量大于该请求所需要的VM容量。
1. 我们就要将相应的$b_{ij}$放到最后的解决方案$\Phi$中；
2. 同时要从$R$中删除该请求节点$r_i$，并且在图中的$\varepsilon$中删除所有与$r_i$有关的边；
3. 更新顶点$s_j$的$L_j = L_j - A_i$
$A_i>L_j$：删除边$<r_i,s_j>$，继续寻找下一个最大的权重

直到$R$、$\widehat{B}$、$\varepsilon$为空，最后得到$\Phi$就是最终解，如果$b_{ij} \in \Phi$则说明投标成功。

得到中标集后，在对每一个中标进行调度，是让ECN完成还是让CC完成

PD问题基础解

Critical Payment

对投标$b_{ij}$的付款$p_{ij(b_{ij})}$为临界值，如果用户宣布的投标小于该临界值，则一定不会中标。

为了能确定$b_{ij}$的critical payment，我们首先要确定$b_{ij}$的代替投标（当我们从$\widehat{B}$中删除$b_{ij}$的时候，它将取代其成为中标）

步骤如下：

我们首先删除$<r_i,s_j>$的边，来获得一个没有$b_{ij}$的新加权二分图
为了方便，我们使用$\varepsilon_{-ij}$来表示更新后的边，$G_{-ij}$来表示新的二分图
利用之前的算法重新再找最大的权重边，获得中标；$\Phi_{-ij}$表示新的分配解决问题方案。$b_{ij}$的备选bid一定在$\Phi_{-ij}$内

现在有两种情况：

需求$r_i$被分配到了其他的ECN$s_{j'}$
ECN已经拥有了很多的需求，导致没有过多的资源提供给$r_i$

对于备选中标，我们假设$b_{ij'}$为是$r_i$的相关赢家；$b_{i_1j},b_{i_2j}...$为ECN$s_j$接受到的赢家

对于第一种情况，$b_{ij'}$是$b_{ij}$的候选

对于第二种情况，我们可以找到ECN的critical payment，表示为$b_{i_{min}j}$ \[ b_{i_{min}j} = min\{ w_{i_1j},w_{i_2j}...:L_j-\sum_{w_{i_{x}j}-w_{i_{y}j}}A_{i_{x}} \geq A_i\} \] $s_j$总是选择权重相对较大的请求，直到它没有足够的剩余容量来满足请求$r_i$。因此，$b_{i_{min}j}$投标正是$b_{ij}$的另一个备选投标。

此外，如果$w_{ij'}\geq w_{i_{min}j}$，$b_{ij'}$将成为$b_{ij}$的替代出价。否则，如果$w_{ij'}< w_{i_{min}j}$，$b_{ij}$的备选投标将为$b_{i_{min}j}$。 \[ p_{ij}(b_{ij})=A_i·(C_j^v+max\{w_{ij'},w_{i_{min}j}\}) \]