移动边缘网络中基于拍卖理论的资源分配研究-拍卖部分

参考链接

https://kns.cnki.net/kcms/detail/detail.aspx?dbcode=CMFD&dbname=CMFD202101&filename=1020431416.nh&uniplatform=NZKPT&v=UT0f0po-h11xOoQt8DUymsFxOq5Z-N-DAeJ2unOfnxZhGA_t_mfccrY7BCK19Bil

[1]刘奔. 移动边缘网络中基于拍卖理论的资源分配研究[D].南京邮电大学,2020.DOI:10.27251/d.cnki.gnjdc.2020.000298.

2 拍卖理论及移动边缘计算技术

目前很多学者通过求解优化问题来分配边缘网络资源，但是这种资源分配方式存在一些不足。一方面计算比较复杂，另一方面这种资源分配方式只考虑用户需求而没有考虑MEC运营商的利益。而利用拍卖理论可以有效的分配边缘服务器的资源，并保障MEC运营商的利益。

2.1 拍卖理论简介

拍卖机制的设计，即在非合作竞争环境下的一组稀缺资源的分配规则是我们研究的重点。

2.1.1 基础类型拍卖

在拍卖模型中，买家希望以尽可能低的价格获得被拍卖物品，而卖家则希望尽可能获得更多的利润。通过买家相互竞争，可以发现卖家资源的最大价值。如果在拍卖市场存在多个卖家，则卖家之间相互竞争，以获得出售资源机会。综上所述，拍卖其实是买卖双方的博弈，是不完全信息博弈的一个有效实例。

传统拍卖，主要包括英式拍卖、荷兰式拍卖、第一价格拍卖、次价密封拍卖。

英式拍卖：英式拍卖是目前为止应用最为广泛的拍卖。英式拍卖采用公开竞拍和提价拍卖的方式来进行拍卖。公开拍卖的特点就是买家之间是知道彼此的出价的。在拍卖的开始阶段，拍卖者会公布一个底价，然后在拍卖的过程中会确定出价最高者。在拍卖的过程中，买家之间相互竞争以获取被拍卖的物品。为了获取被拍卖物品，买家必须不断提高自己的出价，直至当前出价超过自己的心里预期估值，才会放弃出价。拍卖者为了掌握拍卖的节奏，会设置每次加价的最低幅度。此外，买家也不能提出很高的“跳跃式出价”。

荷兰式拍卖：荷兰式拍卖也是一种应用广泛的拍卖。荷兰式拍卖采用公开拍卖和减价拍卖的方式来进行拍卖。和英式拍卖一样，买家也是彼此知道出价的。在拍卖开始时，拍卖者会公布一个最高价格，如果有人接受，则拍卖结束，否则拍卖者隔一段时间后会降低拍卖品的价格。如果当前价格达到买家的心里预期附近时，买家很有可能会接受该价格，否则拍卖品就很有可能被其他的买家买走。从以上分析中可以得出，英式拍卖和荷兰式拍卖不同，这种拍卖形式更适合卖方市场。通过不断降低拍卖品价格，以达到买家的心里价格，获取了出售资源的机会。

第一价格密封拍卖：和以上两种拍卖不同，第一价格密封拍卖属于密封拍卖。在拍卖过程中，买家不会公开提交自己的出价，而是秘密将出价提交给拍卖者。因此，买家之间彼此不知道其相互的出价。 一般来讲，拍卖者会买家的出价进行排序，然后选择出价最高的买家作为胜者，并将资源分配给胜者，胜者需要支付其出价。值得注意的是，如果有多个物品被拍卖，那么则该拍卖方式被认为是“歧视性的”，因为胜者支付的费用不一样。拍卖过程以上两种情况分别讨论。 如果只有一件拍卖物品时，买家单独出价，并且出价最高的买家按照其报价获取被拍物品。 如果拍卖物品有多件时，拍卖者会根据买家提交的出价进行排序，根据出价的顺序依次为分 配资源，直至资源分配完为止，买家需要支付其报价。在歧视性拍卖中，买家提高出价可以增加获胜的概率，但是也降低了其获取的收益。在这种情况下，买家没有占优策略，买家的最大效益取决于其对其他买家的出价预期。

次价密封拍卖：次价密封拍卖也是属于密封拍卖。在拍卖过程中，买家不会公开提交自己的出价，而是秘密提交给拍卖者。拍卖者对买家的出价排序，并选择出价最高的买家作为胜者。但不同于第一价格密封拍卖，胜者只需要支付次高出价者提交的报价。换句话说，赢家支付的价格低于预期价格。因此，次价密封拍卖促使购买者真实地出价，这种拍卖达到了策略的正确性、激励的相容性或真实性。真实性是一种重要的属性，因为不具有这种属性的拍卖容易受到市场操纵，产生非常糟糕的结果。

2.1.2 双向拍卖

以上四种经典类型的拍卖都属于单向拍卖的范畴，因为在这些交易中卖方的数量为“1”，卖方掌握着市场中的稀缺资源，称为“资源优势方”；而最终的成交价格是由人数众多的买家决定，称为“信息优势方”。而双向拍卖[26]是一种多对多的市场机制，在拍卖市场中存在多个买家和多个卖家，该市场中买卖双方的关系有“资源优势方”和“信息优势方”转变成一种平等的供给和需求关系。不同于单向拍卖，双向拍卖有着许多优良的特点，即在供求信息不足、交易者数量较少的情况下，双向拍卖也能到达很高的市场效率并且迅速收敛到均衡点。因此，双向拍卖已经成为全球研究的一个热点，并广泛用于电力资源，网络资源等资源的交易。

双向拍卖市场由买家，卖家，拍卖者以及被拍物品四部分组成。在双向拍卖市场中，多个买家向拍卖者提交出价，多个卖家也会向拍卖者提交要价，拍卖者根据买卖双方的出价和要价匹配双方。如果拍卖交易成功，买家会获得所需的资源，卖家获得报酬。值得注意的是，由于买家对不同的卖家的资源有不同的估值，买家对多个卖家的出价也各不相同。此外，如果拍卖交易成功，买家也只能从对应的卖家那里获取资源，即买卖关系是一一对应的。

拍卖的主要流程：

1. 买方向拍卖者提交出价和希望获得的物品以及物品的数量，卖家向拍卖者提交要价和参加交易产品的数目。

2. 根据拍卖规则判断买卖双方的出价和要价是否合理，如果不合理则拒绝。

3. 根据拍卖规则，匹配买卖双方，确定交易的物品的数量，买家需要支付的费用以及卖家获得的收益。

4. 根据信息公布规则，向市场公布成功交易的信息，包括成交价格以及成交的资源数目。

5. 根据拍卖规则，确定交易是否终止。如果交易没有终止，则执行步骤（1），否则结束交易。

双向拍卖的基本思想是匹配买方的出价和卖方的要价，并将卖方的商品分配给买方，将买方的付款分配给卖方。在拍卖过程中，买家和卖家同时向拍卖者提交他们的出价和要价。

市场清算价格、均衡价格

双向拍卖可以按照拍卖的轮数是一次还是多次可以分为单轮双向拍卖和多轮双向拍卖。按照被拍卖物品是单一类型的物品还是多类型的物品，拍卖可以分为单物品拍卖和组合拍卖。

与传统的密封拍卖相比，组合拍卖具有很多的优点。但是组合拍卖的最大问题是赢家确定问题，这是一个NP-hard问题。

2.1.3 双向拍卖设计准则

良好的拍卖规则都满足一些通用的性质，其中最重要的一条就是保证买卖双方按照估值进行出价，且双方都没有动机提交虚假的出价以增加自身利益。

在双向拍卖市场中，假设买家的集合为 {1,2,3,…, }，卖家的集合为 {1,2,3,…,m}，买家的资源需求为S ，卖家拥有的资源数目分别为R，买家i对卖家单位资源的估值V。拍卖策略主要包括三方面的内容，匹配买家和卖家，确定买家需要支付的费用以及卖家获得的收益。

（a）匹配买家和卖家，并确定卖家需要分配给买家的资源数目，即确定资源分配关系。

（b）确定买家需要支付的费用P，其中p表示买家需要支付的费

（c）确定卖家获得的收益Q，其中q表示卖家获得的收益。

定义买家的收益为对资源的估值和实际支付费用的差值。如果买家i可以通过提交一个虚假的报价，可以提高其收益，则其就会进行谎报。因此，我们在设计拍卖机制时应该考虑这种情况，设计出一种只有在用户提交真实出价时其效益最大化的拍卖机制，鼓励用户提交真实估价。一个设计良好的拍卖算法应该满足真实性，个体合理性，预算平衡性和系统效率。

真实性：定义：无论其他参与者如何出价，当没有任何一个买家 n 或者卖家m可以通过提交虚假出价来提高自身效益时，则该双向拍卖满足真实性。

真实性也称为激励相容性，是保证拍卖效率和抵制市场操作的有效手段。否则，自私的投标者可以通过操纵他人的出价来操纵拍卖，从而使自己受益而损害他人。相对应的，真实的拍卖能保证当拍卖者提交真实估价时其效益最大。

个体合理性：定义：当买家支付的费用不超过其出价，卖家获得的收益不少于其要价，则该双向拍卖满足个体合理性。

个体合理性保证了投标人的效益是非负的，并激励买卖双方参与拍卖。

预算平衡性：定义：当拍卖者的收益是非负时，则该双向拍卖满足预算平衡性。如果拍卖者的收益约等于零时，则该双向拍卖满足较强的预算平衡性。其中，拍卖者的收益表示为买家支付的总费用减去支付给卖家的总费用。

预算平衡性保证了拍卖者愿意执行拍卖。

计算效率：

传统意义上，拍卖机制需要设计在多项式时间内执行结束。如果拍卖时间过长，则失去了拍卖的意义。

根据不可能定理可知，没有双向拍卖可以同时满足以上三个经济属性，同时最大化拍卖效率。由于实施拍卖必须具备这三个经济属性，因此设计应着重于先满足他们，然后最大化系统效率。

2.2 移动边缘计算技术简介

2.2.1 移动边缘计算的简单应用场景

随着 5G 的发展，催生了诸如人脸识别，增强现实、高清视频流等计算密集型应用和交互式游戏与实时全息投影等对时延要求比较高的应用。MEC可以为这种新兴的应用服务提供计算支持。

2.2.3 计算卸载模型

整个计算任务卸载的过程分为任务上传，任务云端执行和结果返回三个部分。只有在本地执行的花费和时延大于等于在云端执行的时候，用户才愿意将任务上传到 MEC 服务器上执行。

3 基于拍卖理论的多轮迭代资源分配算法

本章研究了如何分配计算资源和通信资源，使 MEC 运营商的利益最大化，提出了一种基于拍卖理论的多轮迭代资源分配算法。

3.1 研究背景

本文讨论了移动边缘计算(MEC)系统中资源分配的不同方法。MEC 是一种新的计算方式，其中服务器部署在网络的边缘，而不是在中心位置。本文讨论了 MEC 系统中资源分配的不同方法。第一种方法称为 MCC，它涉及到将任务上传到一个中央云。第二种方法称为 MEC，它涉及在网络边缘部署服务器。第三种方法是本文提出的一种新方法，称为多轮资源分配算法。该算法以拍卖理论为基础，是一种符合 MEC 激励结构的资源配置方法。

3.2 系统模型

本文考虑一个由N个用户设备（User Equipment，UE）， M个MEC服务器和一个拍卖者 组成的移动边缘网络。如图 3.1所示。

每个 UE 可以连接到它周围的基站，如表示潜在连接的虚线所示。每个 UE 都有多个计算任务，经过拍卖之后，UE 将最终将任务卸载到其中一个服务器上。假设 UE i具有 Ki个任务，并且 MEC 服务器属于不同的运营商。在这个拍卖交易过程中，计算资源和通信资源代表了两种商品的交易。作为买方的 UE 购买 MEC 运营商的计算资源和通信资源，只有当 UE 同时获得所需数量的计算资源和通信资源时，交易才能完成。在 UE 计算任务卸载之前，举行拍卖。在拍卖阶段，拍卖师从用户和 MEC 运营商那里收集出价信息，并基于拍卖理论执行多轮迭代资源分配算法。拍卖结束后，UE 将计算任务上传到指定的 MEC 服务器，MEC 服务器执行计算任务并返回结果。值得注意的是，每个 UE 将有一个估计为每个 MEC 服务器，这是私有的，UE 将使用这个估计来计算出价向量。为了使自身效益最大化，UE 将根据投标策略提交一个投标向量。作为卖方，MEC 运营商销售计算资源和通信资源。每个 MEC 运营商将根据自己的运营成本和其他因素制定自己的定价策略，以实现收入最大化。

3.3 基于拍卖理论的多轮迭代资源分配算法

本文提出了一种基于拍卖理论的多轮迭代资源分配算法。该算法主要包含如下步骤：首先为 UE 构建偏好列表，然后执行初始化资源分配策略，并最终执行资源分配调整策略。值得注意的是，UE根据偏好列表向拍卖者提交出价向量。在每一轮拍卖开始时，每个 UE根据偏好列表向拍卖者提交其所有计算任务的出价向量。如果拍卖者拒绝 UE 提交的出价向量，那么在下一轮拍卖开始时，UE会提交其偏好列表中的下一个出价向量。

首先，本文研究 UE对MEC服务器的偏好。一方面， UE更喜欢距离近的MEC服务器。距离 UE越近的服务器，UE的信道状况就越好，因此 UE的单位通信资源出价越高。另一方面，由于每个MEC服务器配置的计算资源各不相同，每个 UE 任务对计算资源的需求也各不相同，对计算需求大的任务希望在资源充足的 MEC 服务器上执行，其单位计算资源的出价也会越高。UE会综合考虑信道状况和MEC服务器的资源配置情况，构建偏好列表。

3.3.1 初始化资源分配策略

说明了拍卖师用来确定哪个MEC服务器将暂时接受哪个任务的算法的步骤。拍卖师首先按价格按降序对向量进行分类，然后消除所有不符合价格限制的所有内容，然后按照其余向量中出现的顺序分配计算和通信资源。

3.3.2 资源分配调整策略

资源分配调整策略的目的是调整初始资源分配，选出对 MEC 运营商估值更高的用户。如果 UEi收到失败信息，它会根据出价策略提交下一个出价向量。在拍卖者执行过初始化资源分配策略后，如果其在下一轮拍卖开始时接收到了用户的出价向量，那么其将会为对应的 MEC 服务器执行资源分配调整算法。与前一节类似，拍卖师首先选择目标服务器 j 的出价向量，对出价向量进行排序，筛选出不符合要求的出价向量，然后构造候选向量组 cjB。然后拍卖师决定 MEC 服务器 j 是否接受这些计算卸载请求。

主要步骤如下。如果 MEC 服务器能够满足要求，那么拍卖师将接受计算卸载请求的，否则拍卖者将会把出价向量b和列表里的出价向量相比较。只有如下两个要求被同时满足时，T 的计算卸载请求才会被接受。在列表中存在一组出价向量，他们的加权出价都比b的加权出价要低，并且这一组出价向量所占用的资源可以满足任务T的需求。

3.3.3 算法机制的研究

定义买家和卖家的效用函数。

• 买家（UE）的效用。 买家效用定义为UE i对任务的真实估值减去其支付给拍卖者的费用。如果存在一个卖家j接受了任务，则 UE 的收益为真实估值减去支付给拍卖者的费用 ，否则UE i的效用为零。
• 卖家（MEC 运营商）的效用。卖家完成任务的效用定义为拍卖者支付给卖家的费用减去卖家处理任务的成本。 如果卖家接受了任务，则卖家的效用拍卖者支付减去处理任务的成本 ，否则卖家的效用为零。

定理 3.1：基于拍卖理论的多轮迭代分配算法对卖家而言满足真实性。

证明：根据卖家的真实要价 $\alpha$ 可能小于均衡要价 $\alpha^*$ ，也可能大于等于均衡要价分别讨论。

1. 卖家的真实出价小于 $\alpha^*$ ，卖家有提高要价或者降低要价这两种策略。如果卖家提高要价，根据要价是否超过 $\alpha^*$ 分成两种情况。 第一，卖家的要价可能会超过 $\alpha^*$ ,根据资源分配算法的步骤可知，此时卖家会被剔除，其收益将会跌至零。 第二，卖家的要价没有超过 $\alpha^*$ ， 则卖家单位计算资源和单位通信资源的收益保持不变，卖家的收益不会改变。如果卖家降低要价，则卖家单位计算资源和单位通信资源的收益仍然保持不变，卖家的收益不会改变。所以，此时卖家没有动机改变自己的真实要价。

2. 如果卖家的真实要价大于等于 $\alpha^*$ ，卖家有提高要价和降低要价这两种策略。如果卖家提高要价，那么卖家依然被剔除出去，此时卖家效益依旧为零。如果卖家降低要价，此时有两种情况。第一，如果卖家要价仍然大于等于 $\alpha^*$ ，则卖家收益依旧为零。第二，如果卖家要价低于 $\alpha^*$ ，则此时卖家收益为负。所以，此时卖家没有动机改变自己的真实要价。

综上所述，基于拍卖理论的多轮迭代分配算法对卖家而言满足真实性。

定理 3.2：基于拍卖理论的多轮分配算法对买家而言满足真实性。

证明： 根据MEC服务器的资源是否被完全分配，分成两种情况。

根据买家的真实出价可能小于等于 b 或者大于b 这两种情况分别讨论。

Case 1：当MEC服务器的资源没有被完全分配

1）买家的真实出价小于等于b 。此时，买家有提高出价或者降低出价两种策略。 如果买家提高出价，此时存在两种情况，第一，买家出价仍然小于等于b ，此时买家的收益仍然为零；第二，买家的出价大于b 时，此时买家的收益为负。如果买家降低出价，买家的收益依旧为零。所以，当买家的出价小于等于b 时，买家没有动机提交虚假出价。

2）买家真实出价大于b 。其具体分析过程和 1）类似，因此省略分析内容。

Case 2：MEC服务器的资源被完全分配

当 MEC 服务器的资源被完全分配时，定义出价最高的失败用户出价向量为 b 。如果用户出价向量小于等于b时，则交易失败。如果用户出价向量大于b时，则交易成功。 此时买家的真实出价可能小于等于b 或者大于b 。具体的分析和 Case 1 类似，因此省略分析内容。

综上所述，基于拍卖理论的多轮分配算法对买家而言满足真实性。

定理 3.3：基于拍卖理论的多轮迭代分配算法满足个体合理性。

证明：如果边缘服务器接受了UE i的任务，则 UE i支付给拍卖者的单位计算资源和单位通信资源的加权费用为T ，等于UE i对 MEC 服务器资源的估值。因此，所提算法对买家满足个体合理性。拍卖者支付给卖家 j 的费用为大于拍卖者的要价，因此所提算法对卖家满足个体合理性。

综上所述，所提算法满足个体合理性。

定理 3.4：基于拍卖理论的多轮迭代分配算法满足预算平衡性。

证明：拍卖者的完成任务的收益为等于用户支付的费用减去支付给卖家的费用。拍卖者支付给卖家的费用小于买家支付给拍卖者费用。因此，所提算法满足预算平衡性。