1. 引言
近年来,随着虚拟化技术的成熟和分布式框架的普及,通用算力云化已经成为当下网络服务不可逆转的趋势 [1] 。在云原生环境下,云计算资源作为一种商品进行交易拍卖,云资源使用方按照需求,向云资源拥有方进行购买。
云资源的实质是云计算资源共享池,其中的资源包括网络资源、服务器资源、应用软件资源、服务资源等。共享池中的云资源具有低成本、高效率、安全可靠、实时互联等特点,为当今社会的发展提供了诸多便利 [2] 。现如今,云资源网络分配是采用提供商为用户提供“按需付费”的服务。而双向拍卖机制,作为一种高效的资源分配方法,曾在诸多有关分配的领域中得到利用。在云资源分配的模型中,有边缘服务器、多个客户和服务提供商,也有与双向拍卖模型基本相同的分配方式。因此本文设计了一种基于双向拍卖和折中算法的云资源分配协议,能在保证可靠性的前提下,提高云资源分配的有效性。
2. 相关工作
2.1. 云原生网络和边缘计算
基于云原生技术的端到端服务化架构是打造6 G网络全场景适应能力的必要技术手段 [3] ;实现6 G云网融合,高效可靠的边缘计算技术必不可少;边缘计算是将计算、存储、通信等任务分配到网络边缘的计算模式。它强调在用户终端附近执行数据处理过程,将计算资源移到离用户更近的地方,从网络的核心移到边缘,以最小化回程延迟,达到降低延迟、减少能耗、保护用户隐私等目的 [4] 。
网络孪生于1993年提出,又称连体网络,用以实现云边端的数字孪生等应用。网络孪生作为一种既具有物理网络实体,又拥有虚拟孪生体的网络系统,其物理网络实体能够与虚拟孪生体进行实时交互映射。它是人、机、物在云原生网络中的移动代理、传输代理、安全代理以及数据代理,是部署和运行在边缘云和核心云上的一种基础性服务,也是每个用户上网的唯一入口。网络孪生解决了安全问题、传输问题和移动问题。考虑到云资源分配的安全性问题,本文提出的云资源分配模型是基于边缘计算,且建立在云原生网络条件下的模型。
2.2. 双向拍卖
云环境下,云资源客户从动态虚拟化的资源池中向云资源提供方按需索取计算能力、存储能力或者虚拟机服务等功能。云资源市场中有着多个云资源提供方和多个云资源客户,这与双向拍卖模型中的商品提供者和顾客基本相同,因此本文选择使用双向拍卖模型来模拟云环境中云资源的分配问题。
目前,许多研究人员在云计算环境下分析了云资源的分配优化问题,取得了较好的进展。例如,文献 [5] 提出了一种兼顾买卖双方利益的双向拍卖资源分配算法,此种分配算法考虑了云资源提供方和使用方双方共同的利益,鼓励了双方在公平公正的前提下进行竞购资源。文献 [6] 结合了经济学知识,提出了利用细胞膜优化算法给出最优的资源分配方案。文献 [7] 提出了一种改进的周期性双向拍卖模型,采用分段拟合的方法来确定买卖双方的满意度,有效提高了更多云资源使用者的满意度。受以上文献的启发,本文提出一种基于双向拍卖和折中优化算法的云资源分配方案。
3. 基于双向拍卖的云资源分配协议
3.1. 资源分配框架
针对网络边缘的云资源分配问题,本文提出使用双向拍卖机制建立资源分配模型。在该模型中,共含有3种角色:拥有云资源的销售者、请求云资源的消费者以及云资源分配代理;三者分别代表边缘服务器(Edge Server, ES)、客户(Client, CL)、服务提供商(Service Provider, SP)。为了保障信息安全及实现个人数字资产确权,在资源拍卖与分配过程中,ES与CL皆由其网络孪生作为代理完成全部工作;简省起见,在下文中不再强调是ES与CL的网络孪生代理在代替其行使功能。
对于可分配的云资源数量,本文采用块状能力描述,如图1所示,首先使用连续性能曲线刻画客户在任务开始时间到任务结束时间内对资源需求的变化,然后利用离散化的方法统计出这段时间内需要的能力块数量 [5] 。
Figure 1. The description of resource blocks
图1. 块状资源描述
分配机制具体流程如下:
1) ES和CL向SP发送标的;
2) SP协调所有ES和CL按照拍卖规则进行双向拍卖;
3) SP根据拍卖确定的成交价使用折中优化算法得到云资源分配方案;
4) SP将云资源分配结果通知所有ES和CL,并按此方案分配云资源。
具体分配流程如图2所示。
Figure 2. The flowchart of cloud resource allocation
图2. 云资源分配流程图
3.2. 基于双向拍卖的资源定价
3.2.1. 买卖双方标的
当ES有资源需要出售时,便生成一个边缘服务器标的提交给SP。边缘服务器标的表示为五元组
e, CP
e, AP
e, BP
e, TQ
e>。其中ID
e是每个ES的网络孪生代理的唯一身份标识。CP
e是资源成本价,表示ES对于出售资源所能接受的单位资源块价格的最低价。AP
e是
ES对资源的期望价。BP
e是边缘服务器投标价,初始值等于期望价,在拍卖过程中逐步更新。TQ
e是
ES待出售资源的总量。
当CL有资源需求时,便生成一个客户标的提交给SP。客户标的表示为五元组
c, CP
c, OP
c, BP
c, TQ
c>。其中,ID
c是每个CL的网络孪生代理唯一的身份标识。CP
c是客户预算,表示
CL对于购买资源所能接受的单位资源价格的最高价。OP
c是
CL对资源的期望价。BP
c是客户投标价,其初始值等于期望价,在拍卖过程中逐步更新。TQ
c是
CL计划购买资源的总量。
3.2.2. 资源定价
1) 投标价更新规则
每轮拍卖结束后,未能成交的ES在不低于保留价的前提下降低其在下一轮拍卖中的投标价。
计算方法如公式(1)所示:
(1)
其中,
是ES的上一轮投标价,
是ES的新投标价。在新一轮拍卖中ES将以
参与拍卖。
相应地,未能成交的CL在不高于保留价的前提下提高其在下一轮拍卖中的投标价。计算方法如公式(2)所示。
(2)
其中,
是CL的上一轮投标价,
是CL的新投标价。在新一轮拍卖中CL将以
参与拍卖。
2) 信用度评估
在拍卖过程中,有些用户为了自身的利益,不遵守市场价格的真实规则、虚假出价从而导致拍卖模型的可靠性大大降低,为了解决这一问题,本文引入了用户信用度的概念。
每轮拍卖结束后,SP根据边缘服务器的拍卖成交率对边缘服务器信用度进行迭代更新。计算方法如公式(3)所示。
(3)
代表的是第k次拍卖结束后边缘服务器i的信用度值,根据本次匹配结果来进行更新。
是一
个变量因子,本文中取值为
,是为了削减上次信用度值对本次信用度值更新的影响。
代表的是边缘服务器i在第k次拍卖中的总匹配数量,
代表的是第k次拍卖中所有边缘服务器的总匹配数量。
相应地,每轮拍卖结束后,SP根据客户的拍卖成交率对客户信用度进行更新迭代。计算方法如公式(4)所示。
(4)
代表的是第k次拍卖结束后客户j的信用度值,根据本次匹配结果来进行更新。
代表的是客户j在第k次拍卖中的总匹配数量,
代表的是第k次拍卖中所有客户总匹配数量。
在初始化信用度时,由于用户初次参与拍卖,拍卖商对用户缺乏认知,则取“平均”为初始值,设定其初始信用度值为0.5。即初始化信用度
,
。若用户不是初次参与拍卖,则将其上轮拍卖结束更新后的信用度值作为本次拍卖的初始值。
随着拍卖逐轮进行,用户信用度会随之累加更新。若用户诚实地参加拍卖,那么它会维持一定的成交率,其信用度会随市场波动而波动变化;若虚假出价,则该用户的拍卖成交率会不停下降,其信用度也将持续降低,代表其可靠性降低。
3) 确定成交价
在每轮拍卖中,若ES投标价不高于CL投标价,该ES与该CL可以确定一个成交价。本文采用信用度机制确定成交价。计算方法如公式(5)所示。
(5)
其中,信用度高的用户对成交价的确定起更大作用,从而保障可靠性。
成交价确定之后,就存储在m × n阶的价格矩阵P中。其中,m表示参与拍卖的ES数量,n表示参与拍卖的CL数量,
表示第i个ES与第j个CL之间的成交价。
4) 拍卖结束条件
在以下4个条件中,只要有1个条件满足,则SP结束本次拍卖:
a) 达到最大拍卖轮数;
b) 参与拍卖的ES数量变为0;
c) 参与拍卖的CL数量变为0;
d) 参与拍卖的ES投标价和CL投标价均更新到保留价且ES投标价最小值大于CL投标价最大值。
3.2.3. 拍卖流程
当有资源买卖需求时,ES与CL向SP发送标的;在SP的协调下,ES与CL按照拍卖规则开始进行拍卖。
拍卖流程描述如下:
1) SP将ES按边缘服务器投标价升序排列,将CL按客户投标价降序排列,分别构成ES队列和CL队列。
2) ES中的第一个用户与CL中的所有用户依次匹配,按3.2.2.的3)中方法确定成交价;ES中的第二个用户与CL中的所有用户依次匹配,确定成交价;……;ES中的最后一个用户与CL中的所有用户依次匹配,确定成交价。所有成交价存储在价格矩阵P中。
3) 本轮拍卖中未确定成交价的ES和CL按3.2.2.的1)中方法更新投标价。
4) 未更新投标价的ES和CL选择是否继续拍卖,若选择继续,则不做任何操作;否则,将此ES或CL从ES队列或CL队列中移除。
5) 检查是否到达拍卖结束条件,若未到达结束条件,则进行下一轮拍卖,转步骤 1);否则,拍卖结束,输出价格矩阵P。
3.3. 基于折中优化的云资源分配算法
拍卖结束后,可能面临以下两种情况:
CL的作业任务量较大,需要多个ES的资源共同完成,同时与多个ES拍卖成功并确定成交价;
ES拥有的资源数量较大,同时与多个CL拍卖成功并确定了成交价。
此时需要合理有效的方案进行资源分配。本文根据云资源定价,提出使用折中算法得到最佳资源分配方案,该方案用m × n的矩阵Q来表示,其中
表示第i个ES分配给第j个CL的资源数量。
资源数量以能力块作为衡量,最小单位为1。
折中算法的主要思想是:从第1个客户到最后一个客户正序分配能力块,再从最后一个客户到第1个客户倒序分配能力块,进行若干次循环后采取能力块选择客户的方式分配能力块,但为了避免每个剩余能力块都选择相同客户,当某一能力块选择某一客户时去除该客户,也就是意味着,其余能力块只能在其他剩余客户中进行选择 [8] 。
3.3.1. 理论模型建立
一次分配中,对每个客户最多分配1个能力块;首先将成交价最低的能力块依次从第1个客户到第K个客户进行分配。每个能力块能且仅能选择一个客户;然后,在分配完一轮能力块后,如果该能力块仍有剩余,继续将该成交价最低的能力块按倒序从最后一个客户到第1个客户进行分配;若该能力块无剩余,则将剩余能力块中成交价最低的能力块按倒序从最后一个客户到第一个客户分配;如此按成交价递增的顺序依次分配其他能力块;在进行完若干次循环后剩余的能力块进入下一轮拍卖,当可利用能力块集合为空或客户集合为空时算法结束。具体步骤如下:
1) 初始化,构建客户集
,供选择能力块集
,能力块分配矩阵Q = 0;客户集与能力块集都按升序排序。
2) 对客户
分配使其获利最大(成交价最低)的能力块,即
,
,
(6)
3) 若依然剩下能力块,再按
顺序分配使其获利最大的能力块,即
,
,
(7)
4) 经过若干次2)、3)两步的循环后,从剩余能力块集合中选择能够使其获利最大的客户,即
,
,
(8)
5) 不断重复步骤4),直至能力块集合或客户集合为空;
6) 得到分配矩阵
,算法结束。
表示能力块的分配情况;
则表示该能力块n已被分配给特定客户k。
3.3.2. 衡量指标
本文采用2个指标来评价分配方案,即成交价满意度、资源成交率,分别代表着分配方案在可靠性与高效性方面的性能。综合2个指标的值得出目标值,以此衡量分配方案的优劣。
1) 成交价满意度
ES对成交价的满意度由资源成交价与其期望价的比值决定;CL对成交价的满意度由其期望价与资源成交价的比值决定。系统的成交价满意度是所有ES和所有CL的成交价满意度的平均值,计算方法如公式(9)~公式(11)所示。
(9)
(10)
(11)
其中,
是第
个ES的成交价满意度,
是第
个CL的成交价满意度,
表示第i个ES对资源的期望价,
表示第j个CL对资源的期望价。
成交价满意度越高,资源成交价与期望价越接近,用户越能以自己满意的价格出售或购买资源。
2) 资源成交率
ES的成交率是其售出资源量占待售资源总量的比例,CL的成交率是其购买资源量占欲购买资源总量的比例。系统的成交率是所有ES和所有CL的成交率的平均值,计算方法如公式(12)~公式(14)所示。
(12)
(13)
(14)
其中,
是第i个ES的成交率,
是第j个CL的成交率,
表示第i个ES待出售的资源总量,
表示第j个CL欲购买的资源总量。
资源成交率越高,用户的需求就越能够得到满足,即资源分配效率越高 [5] 。
3) 目标值
本文通过引入目标值G(Q)来综合衡量资源分配方案的优劣,计算方法如公式(15)所示。
(15)
其中,
、
表示2个指标各自的权重,
。G(Q)越大,资源分配方案越好;G(Q)越小,资源分配方案越差。
4. 协议性能对比分析
4.1. 信用度评估模型对比分析
在信用度评估中,为了削减上次信用度值对本次信用度值更新的影响,本文取变量因子
;其中k为用户参与拍卖的轮次,可见随参与竞拍的次数增加,用户上一轮信用度
对本轮信用度的影响逐渐降低,本轮竞拍成交率
所占权重逐渐升高;本文所用模型与文献 [9] 对比如图3所示:
Figure 3. The comparison of variable factor α
图3. 变量因子α对比
从图3可以看出,当拍卖轮次大于1时,本文采用的模型相关系数下降速度大于文献 [9] 中的相关系数下降速度,充分降低了突发情况对信用度模型的影响,大大增加模型的稳定性与可靠性。
4.2. 资源分配模型算例分析
为了更直观地了解本文提出的基于双向拍卖和折中算法的云资源分配模型,本节给出了一个在四个边缘服务器和三个客户的情况下的示例。资源分配过程如下:
步骤1有待售资源的ES与需要资源的CL生成双方标的发送给SP。表1、表2分别为买卖双方标的,相应的初始数据均为随机生成。
Table 1. The target of edge servers
表1. 边缘服务器标的
步骤2在SP的组织下,进行第一轮拍卖,K = 1,得到成功的匹配对{(ES1, CL1) (ES1, CL2) (ES2, CL1) (ES2, CL2)},计算得到信用度
,
,
,
,确定相应成交价并用折中算法进行资源分配,进而得到成交价矩阵和分配矩阵:
步骤3将出售完所有资源的ES与得到所需资源的CL从队列中移除,队列中其他用户按规则更新投标价,如表3、表4所示。
Table 3. The target of edge servers for the second auction
表3. 第二轮边缘服务器投标价标的
Table 4. The target of clients for the second auction
表4. 第二轮客户投标价标的
步骤4在SP组织下,买卖双方按照更新的投标价进行新一轮拍卖,K = 2,得到成功的匹配对{(ES2, CL1) (ES2, CL3) (ES3, CL1) (ES4, CL1)},更新用户信用度:
,
,
,
,
。确定相应成交价并用折中算法进行资源分配,进而得到成交价矩阵和分配矩阵:
步骤5将出售完所有资源的ES与得到所需资源的CL从队列中移除,队列中其他用户按规则更新投标价,如表5、表6所示。
Table 5. The target of edge servers for the third auction
表5. 第三轮边缘服务器投标价标的
Table 6. The target of clients for the third auction
表6. 第三轮客户投标价标的
步骤6在SP组织下,买卖双方按照更新的投标价进行新一轮拍卖,K = 3,得到成功的匹配对{(ES3,
CL3) (ES4, CL3)},更新用户信用度:
,
,
。确定相应成交价并用折中算法进行资源分配,进而得到成交价矩阵和分配矩阵:
步骤7根据得到的成交价矩阵及分配矩阵,按照公式(9)~(11)计算成交价满意度Sat = 0.99;按照公式(12)~(14)计算成交率Rate = 0.92;取β = γ = 0.5,计算得到目标值G(Q) = 0.995。由此可见,本文提出的方案具有良好的性能,有利于云资源分配的有效性与可靠性。
5. 总结
随着空天地海一体化的6G网络建设正如火如荼地展开,要实现第六代移动通信网络深度覆盖、超高可靠低时延、强安全及内生安全等要求,以“云”来建设网络已是大势所趋 [10] 。在云原生网络中,骨干网由边缘云和核心云来构建,用户通过接入边缘云从而接入网络,在网络边缘势必面临资源分配问题。
本文基于双向拍卖模型,提出一种云资源分配机制。在该机制中,资源拥有者与消费者公平地参与到云资源市场中,通过双向拍卖确定资源成交价,以参与者的信用度保障定价机制的可靠性和稳定性;同时基于云资源定价,使用折中算法对成交的云资源进行合理高效的分配。算例分析表明,本文机制是可行且有效的,可以满足买卖双方的需求,并具有较高的效率和安全性。
基金项目
国家大学生创新创业训练计划项目(202310004159)。