基于双向拍卖的流媒体资源交易模型

薛杨上，李泽平，陈仁康

(贵州大学 计算机科学与技术学院，贵州 贵阳 550025)

0 引 言

目前互联网难以在网络资源有限的情况下，为大规模流媒体应用提供高质量的视频服务。传统的流媒体分发服务主要基于内容分发网络(content delivery network，CDN)或对等网络(peer to peer，P2P)的架构。CDN存在部署成本高、可扩展性差、资源浪费的问题。P2P的可靠性差，不能保证服务质量。而云计算弹性服务为视频服务商带来了新的解决方案。

根据Cisco白皮书[1]，视频数据请求量在近几年增速迅猛，2020年每月视频数据量达到两万PB以上。而且，在不同时间段，用户访问人数差别较大，尤其是高峰期与低谷期的访问量差别尤为明显。实际上，美国主流视频服务商Netflix早在2012年就已经把基础架构迁移到Amazon云端服务器[2]。目前国内云服务商阿里云[3]、腾讯云[4]等都提供了相应的流媒体服务资源租赁方案。但是租赁方式比较单一，长期按年、月租赁资源，短期则是通过划分不同大小的虚拟机(virtual machine, VM)按小时租赁。而通过拍卖的方式进行资源分配，可以使得资源提供商获得更多的收益。

动态资源交易(租赁)是服务商获取资源的方式之一，资源以拍卖的方式进行交易使视频服务商能以低服务成本获得更大的收益。通过引入经济学理论，进行动态资源交易(拍卖)是近年来的研究热点之一[5-8]。

1 相关工作

在云计算中，张骥先等[6]提出基于组合拍卖的云计算虚拟资源分配和定价机制(VRAP)，用户可以一次提出多资源需求，资源提供商可以获得更大的收益。通过设计一种资源再分配策略来保证提供商收益的最大化。随后，张骥先等[7]尝试使用机器学习方法进行资源分配，提出了3种基于监督学习的资源分配算法，价格机制采用的是VCG机制，该机制虽然能够有效实现社会福利最大化，但计算量较大。Cheng等[8]提出一种云辅助视频点播系统(CPA-VoD)，能够有效缓解网络压力和降低视频服务商的运营成本。Cui等[9]提出了一种多目标优化算法NSGA-II的最优云租赁算法，使得请求者选择最合适的云存储服务器。上述研究虽然有效地利用了云资源进行视频服务，但研究重点侧重于视频流行度预测及资源缓存策略，而未考虑使用具体交易机制进行服务资源的分配。Tang等[10]视频流服务中以不同码率视频块为交易资源，提出了单对象和多对象的多维拍卖机制，实验结果表明该机制有效提高了市场的收益。丛鑫等[11]基于拍卖机制提出一种企业级网络最优匹配资源分配(OMRA)策略。Baranwal等[12]提出了一种用于云资源采购的多属性组合反向拍卖机制，考虑价格以及非价格属性，使用贪心算法来求解该模型，并在多项式时间内获得近似最优解。诸葛斌等[5]在SDN中运用拍卖模型，提出一种价格适应协商算法，有效地解决SDN资源交易问题。刘媛妮等[13]在群智感知网络中提出了一种基于拍卖机制的激励机制，有效地提高了任务完成率。

2 流媒体资源交易拍卖模型

2.1 问题表述

在流媒体服务环境中，用户请求量在缓存服务器能力范围之内时，服务器无需进行扩展，直接使用当前服务器即可保证用户请求。但在某个时段迎来视频访问高峰期，用户请求量突然增大，此时服务器无法承载如此多的用户请求，就可以临时租赁(空闲)服务器以满足当前用户请求。

2.2 系统模型

流媒体资源拍卖交易模型如图1所示，拍卖人(资源交易平台)每隔固定时间T组织一次拍卖。买卖双方根据其自身的需求分别向拍卖人提交资源报价和资源要价的竞拍信息。若将买卖双方所有需求全部发送到拍卖人会导致服务器运行压力过大，引入代理先把买卖双方竞拍信息收集、整理、统一后提交到拍卖人。拍卖人在收到竞拍信息后，根据拍卖算法确定买卖成交的资源数量和成交价格。

图1 流媒体资源拍卖模型

2.2.1 实体

(1)视频服务商：作为资源的需求方，为了满足其用户对视频资源的请求，动态地租赁计算资源以服务用户。

(2)资源提供商：作为资源的供给方，出售或租赁自己的计算资源获取利润，以此增加自己的收益。

(3)代理：收集买卖双方竞价信息，整理并发送给拍卖人。代理可有效缓解服务器的压力，避免多个请求集中于单个服务器造成网络瓶颈。

(4)拍卖人(资源交易平台)：收集买卖双方竞价信息，按照交易流程和规则进行最优资源分配及交易价格的计算、发布最终交易结果等。

2.2.2 拍卖流程

拍卖流程如图2所示，交易过程如下：

(1)买方向拍卖人提交资源需求信息；

(2)卖方向拍卖人提交资源供给信息；

(3)拍卖人收集买卖双方提交的信息；

(4)收集信息完毕之后组织一次拍卖，并向参与者收取保证金；

(5)买卖双方分别向拍卖人上交资源拍卖的保证金；

(6)拍卖人通过双方竞价信息，计算得出匹配结果；

(7)向买卖双方发布交易匹配的结果；

(8)根据结果，买卖双方进行资源交易，提供相应的服务；

(9)拍卖人根据服务质量，对买卖双方进行奖惩记录；

(10)从保证金中按比例扣取服务费，然后退还各自参与者。

图2 资源拍卖交易流程

2.3 符号定义

云计算中主要以不同类型的VM为出售资源，即将多种资源捆绑为一台VM进行交易。为了提高买方的满意度，更加细化资源种类。将资源类型分为CPU、内存、外存(硬盘)、带宽。资源需求方可以准确地请求所需的资源量，从而不必受到预定义的VM约束。受云计算资源服务启发，构建一种流媒体资源交易拍卖模型(streaming media resource transaction model，SMRTM)。为方便表述，表1给出后文所用的符号集。

表1 符号集

但是资源组合交易分配问题为赢标者选择问题(winner determination problem，WDP)，是一个NP-hard问题[6,7,12,13]，为了降低算法的复杂度，将多种资源组合交易参数以加权的方式化为资源综合指标(满意度)进行交易。

3 流媒体资源交易算法

3.1 设计目标

拍卖算法设计中存在5个重要属性，而Kumar等[14]指出当前没有任何算法能够保证同时满足这些属性，属性分别如下：

3.1.1 激励兼容(incentive compatible)

激励兼容,又称诚实机制(truthfulness)。可保证每个竞拍者如实地出价，买卖双方不能通过谎报竞拍信息以获得更高的收益。对于买方i，当前策略的效益大于其它策略的效益，即u(bi)≥u’(bi)。 同理，对于卖方j，u(sj)≥u’(sj)。 其中，u(bi) 是买方i的真实效用，u(sj) 是卖方j的真实效用，u’(bi) 是买方i的报告效用，u’(sj) 是卖方j的报告效用。

3.1.2 个体理性(individual rationality)

个体理性是每个竞拍人不会损失自己的利益。在拍卖的交易过程中，买方或卖方效用都不可能为负，即u(bi)≥0，u(sj)≥0。

3.1.3 预算平衡(budget balance)

预算平衡是为了确保交易市场的支出不超过收入，拍卖人不用通过补贴市场来促成买卖双方进行交易。即pi=pj，i∈n，j∈m， 其中pi是买方i成交价格，pj是卖方j成交价格。若pi-pj≥0，i∈n，j∈m， 则该机制是弱预算平衡。

3.1.4 系统效率(system efficiency)

参考经济学中的配置效率，可以通过社会福利和交易成功率来衡量系统效率。有效的拍卖算法可以使社会福利最大化，但交易成功率更符合实际需求，这样可以使买方和卖方都能从中受益。

3.1.5 计算效率(computational efficiency)

如果可以在多项式时间内计算出资源分配和价格支付的结果，则拍卖算法在计算上可行。

3.2 二分图模型

丛鑫等[11]提出的最佳匹配拍卖算法，依据买卖双方的价格差为权值，得到最大匹配。并且，改进Kuhn-Munkres(KM)算法进行二分图最大权匹配。刘媛妮等[13]提出了一种基于逆向拍卖最大化用户效用的模型以及基于二分图的用户匹配算法。在边缘计算中，张守利等[15]提出了一种云端动态集成的服务适配方法，优化改进二分图最优匹配KM算法并且结合排队论增强实时性，最大缩短端服务平均适配请求响应时间。吴剑云等[16]在电子中介交易提出了买卖双方及中介满意度最大的交易匹配模型，有效地实现了高效低成本的交易匹配。李雄一等[17]提出了考虑模糊语言的3种多属性匹配决策方法，并构建数学模型与对应的求解算法。熊化峰等[18]根据属性偏好系数，衡量买卖双方的满意度和偏好序。结合以上文献，以最大资源综合满意度为目标，实现市场社会福利最大化，基于二分图设计了一种资源组合交易算法(resource portfolio trading algorithm，RPTA)。

3.2.1 资源偏好权重

在流媒体服务中，将流媒体多种资源根据买方偏好，设置不同的权重ωk，并根据权重计算出综合满意度。卖方根据买方所给出的权重计算出售资源的综合达标度。

为解决资源总体符合要求，但可能存在单个资源无法达到服务要求，导致无法服务。所以首先需要设定最低资源标准，设定资源等级，买卖双方只有达到资源标准要求才能进行资源综合

0≤ωk≤1

(1)

(2)

买方满意度bsi和卖方达标度ssj计算如下

(3)

(4)

3.2.2 买卖交易匹配模型

通过将权匹配与满意度结合，基于二分图设计一种资源满意度的最佳匹配算法，建立数学模型如下。

依据买方id序列和卖方id序列建立图G=(V,E)。 其中，V={xi∪yj|xi∈X,yj∈Y}，X为买方集合，Y为卖方集合，E={(x,y)|xi∈X,yj∈Y,satis(xi,yj)≥0}，x,y∈E(G)。 满意度satis(xi,yj) 表示买方xi和卖方yj的资源匹配权重，设买方xi资源满意度为bsi，卖方yj的资源达标度为ssj，则satis(xi,yj)=ssj-bsi。

满意度优先匹配算法，买方对资源需求优于对价格的要求，以买方需求为目标，兼顾卖方收益的同时，进行最大满意度匹配。

二分图建模后，买卖双方的匹配度计算可以转化为运用 KM算法对二分图最大权匹配的求解。

由于KM算法对双方节点数量有要求，通过增加节点的方式满足算法运行条件。若m>n，则在n点集中补充m-n个节点，并在对应的边上权赋值为0，相反则补充n-m个节点，以此保证二分图中双方节点数相等。匹配前后的结果如图3所示。

图3 买卖双方匹配

3.3 资源组合交易算法

3.3.1 算法描述

算法1：RPTA

输入：买方报价集BIDb，卖方要价集BIDs，权重ω，资源等级(rl，rm，rh)，价格浮动阈值pf

输出：匹配结果M

(1)if(BIDb.length()>BIDs.length())://卖方不足则补充

(2)BIDs.add(BIDb.length()-BIDs.length())

(3)elseif(BIDb.length()

(4)BIDb.add(BIDs.length()-BIDb.length())

(5)for(biinBIDb):

(6)if(|pbi-PS|≥pf):

(7)BIDb/bi//将买方i从竞拍集中排除

(8)for(sjinBIDs):

(9)if(|psj-PS|≥pf):

(10)BID/sj//将卖方j从竞拍集中排除

(11)for(biinBIDb):

(12)switch(bi.resouces): //买方资源分级

(13)caserl:

(14)bi.level=low

(15)caserm:

(16)bi.level=median

(17)caserh:

(18)bi.level=high

(19)for(sjinBIDs):

(20)switch(sj.resouces): //卖方资源分级

(21)caserl:

(22)sj.level=low

(23)caserm:

(24)sj.level=median

(25)caserh:

(26)sj.level=high

(29)satis(xi,yj)=ssj-bsi//计算满意度

(30)for(biinBIDb):

(31)for(sjinBIDs):

(32)if(pbi>psj) //买方报价>卖方要价(前提条件)

(33)pij=(pbi+psj)/2 //设定成交价

(34)if(bi.level==sj.level)： //同等级进行边连接

(35) 将bsi及ssj作为顶标、 权值为satis(xi,yj)加入边到二分图G， 满足条件l(xi)+l(yj)≥satis(xi,yj)

(36)else: 将bsi及ssj作为顶标、 权值设定为0加入边到二分图G

(37)给定顶标值：l(xi)=max(satis(xi,yj)),l(yj)=0， 形成新二分图G’。

(38)计算初始匹配M。

(39)若X中顶点皆被M匹配， 则停止算法，M即为最大权完美匹配， 否则取G’中未被M匹配的顶点uu, 令SS={uu}，TT=∅。

(40)若NG’(SS)⊃TT， 转步骤(41)； 若NG’(SS)=TT， 则取

(41)选NG’(SS)-TT中顶点y， 若y已被M匹配， 且y,z∈M， 则SS=SS∪{z}，TT=TT∪{y}， 转步骤(40)； 否则， 取Gl中一个M可增广路P(uu,y)， 令M=(M-E(P))∪(E(P)-M)， 转步骤(39)。 其中，NG’(SS)为G’中SS的相邻顶点集。

(42)returnM

3.3.2 算法分析

(1)RPTA近似激励兼容

由于算法侧重考虑市场收益最大化，而不能保证参与者都是诚实的，并非严格激励兼容。

故为了防止买卖双方谎报与资源不符的价格，以谋取自身更高的收益，RPTA设定拍卖人拥有资源单价uk表示第k种资源单位时间的单元保留价，资源标准价格为PS=u1r1+…+ukrk。 通过PS可以衡量买卖方报价的差距，从而近似判断买方或卖方是否存在恶意竞价。

设定浮动阈值pf，若买卖双方报价若与标准价格相差超过浮动阈值，则从竞价集合中排除该买方或卖方，即 |pbi-PS|≥pf或 |psj-PS|≥pf， 则BIDbi或BIDssj。

(2)RPTA满足个体理性

在资源交易中，买卖双方都不会使得自己亏本。即对买方来说，满足pbi≥pi。 而对于卖方，满足psj≤pj， 则有u(bi)≥0，u(sj)≥0。

(3)RPTA满足预算平衡

将买卖双方的最终成交价设定为买方报价与卖方要价之和的一半，在资源市场中保证了支出不超过收入。即pi=pj=pij=(pbi+psj)/2。

(4)RPTA满足系统有效

算法的目标为最大化综合满意度，且买方报价必须大于等于卖方要价交易才能达成，即pbi≥psj，所以交易市场中总存在有效收益，保证了社会福利。而二分图匹配的性质，保证了买卖双方的匹配率。

(5)RPTA满足计算有效

首先，近似判断买卖双方是否诚实，复杂度为N(n+m)， 然后进行买卖方的筛选复杂度为N(n3+m3)， 再计算满足资源要求的买卖双方满意度的复杂度为N(n+m)， 最后建立二分图模型并运行KM算法，找到最大满意度匹配。复杂度为N(n3)。 所以，算法总复杂度为N(2(m+n+n3+m3))， 即在多项式时间内可以计算出结果。

3.4 不同市场需求的匹配策略

根据不同市场需求，设定不同的交易匹配策略。

3.4.1 公平市场

随机匹配策略：在满足条件的买卖方中，随机生成一组id进行匹配。满足条件的买卖双方均有一定概率进行匹配交易。在配对的买卖方中，以价格和满意度为标准，即买方价格高于卖方且卖方的资源能够达到买方的需求。

3.4.2 卖方市场

高低匹配策略：买方价格从高到低排序，卖方价格从低到高排序，卖方满足买方需求且按照排序结果一一进行配对。买卖双方的价格差距大，故卖方的收益很高，则整个交易市场的收益也比较高，从而有利于卖方获取更多的收益。

二分图最大收益匹配策略：以买卖双方的价格差作为权重，进行二分图最大权匹配，使得整个市场的交易剩余价值最大，卖方获得的收益也较大。

3.4.3 买方市场

二分图资源满意度最大匹配策略：根据买方偏好，权设定为不同的类型。通过带权最大匹配求得买卖双方属性差最大。考虑买方对资源综合满意度(性能)与价格两方面。以买方的需求为主要目标，满足需求的卖方，买方从中选择最优进行交易。

根据满意度，设定权重进行二分图最大权匹配，可以满足整个市场的满意度收益最大，找到最佳匹配。以满意度为目标，有利于买方满意度，资源服务质量的提高。

4 算例说明

4.1 参数设置

流媒体资源交易的参数没有统一的规定，文中的流媒体交易参数包括CPU、内存、外存(硬盘)、带宽。为了使得买卖双方的资源能够相互满足且符合实际情况，将资源进行资源等级划分见表2。

表2 资源等级划分

4.2 算法示例

4.2.1 竞拍信息

为方便说明，设置5个买方和5个卖方进行RPTA示例，买卖双方数据竞拍信息见表3。

表3 交易者竞拍信息

4.2.2 运行过程

首先，判断是否存在恶意报价，设定资源单价u=[4,1,1,2]， 价格浮动阈值pf=10， 计算PS，若超出pf则被排除到匹配列表之外，本次算例中卖方4报价超过了价格浮动阈值，视为恶意竞价，则被排除到交易外。

其次，为确保卖方能够保证买方的服务，同时使得交易资源更加接近，降低资源的浪费，则进行等级划分。买方所有资源必须小于等于等级资源数量，否则资源服务不能被满足，例如买方4，首先从最低等级进行对比，几乎所有资源都符合低等级，但外存为1.4>1，低等级无法满足，所以买方被划分到中等级。相反，卖方所有资源必须大于等于等级资源数量，否则无法服务，经过资源划分的结果见表4。

表4 交易者等级划分

然后，分别设置对CPU、内存、存储、带宽的权重ω=[0.2,0.1,0.3,0.4]， 以式(1)～式(4)计算综合满意度。

最后，将买方和卖方作为顶点建立二分图模型，将综合满意度作为二分图的权值，根据买卖双方不同的对应等级，将二分图中对应的边进行连接，边连接完成之后，结合KM算法求最大权匹配。

初始化设置顶标如图4所示，买方顶标设定为满意度最大值，卖方顶标初始化为0，图中忽略了报价为0的边。其中，由于买方3的价格达不到卖方报价则无法达成交易，而卖方4被排除，图4中用虚线表示。

图4 顶标设定

4.2.3 算法评价指标

(1)综合满意度

(5)

综合满意度为买方满意度与卖方达标度之差，如式(5)所示，满意度是衡量买卖双方资源需求或供给的指标。

(2)匹配率

MR=M/(n+m)

(6)

匹配率为成功匹配的人数与总人数之比，如式(6)所示，匹配率可以得到市场中交易人数的占比，以此来衡量算法的有效性。

(3)社会福利

(7)

社会福利SW为所有买方和卖方的效用之和，如式(7)所示。买方i对资源组合的效用定义为u(bi)=pbi-pi， 同样，卖方j效用为u(sj)=pj-psj， 其中，只有交易成功存在效益，否则为0。

4.2.4 匹配结果

x0顶标为0.06，与边上的权值相等，直接与y0成功匹配。x1与y0匹配，同理，x3匹配y1，但x3也对y1进行了报价且资源满意度大于x1，所以将x3匹配更大的权，与y1匹配。并且重新给x1寻找匹配，成功匹配y3。y1已经被x3匹配，则x4不进行匹配。最终，算法得到最大满意度匹配结果如图5所示。

图5 匹配结果

将上文提到的几种匹配策略进行对比，得到匹配结果见表5。

表5 匹配结果

4.3 数值验证

采用Python语言进行数值仿真，实验平台如下:

计算机：CPU Intel Core i5-3470、内存为16 GB、操作系统Windows 10专业版(64位)。

以均匀分布随机生成买卖双方的资源序列，资源数量范围见表6，设置买卖双方各100人、500人、1000人进行仿真实验。

表6 资源范围

以匹配率、资源满意度、市场社会福利、计算效率4个方面进行验证，如图6所示。

4.3.1 综合满意度

图6(a)表明几次实验中，最大价格差匹配算法中满意度明显低于最大满意度匹配算法得到的满意度，由于没有顾及资源满意度，甚至可能出现满意度为负的极端情况。说明虽然达到了买卖双方价格最优匹配，市场的收益最大化，但卖方提供的资源质量并不令买方感到满意。

4.3.2 匹配率

图6(b)表明此次交易匹配率，随机匹配法的匹配率不高，而且多次实验结果表明匹配不稳定，随着不同实验不断变化。高低匹配法匹配率也不高，由于排序后，买卖双方的位置被固定，只能匹配到买方价格高于卖方价格的参与者。最大权二分图匹配，由于其性质，寻找最佳的匹配，匹配率较高且保证参数的权重最大。

图6 RPTA算法衡量指标

4.3.3 匹配结果

通过将买卖双方的估值与实际的交易价格进行对比，得到流媒体资源交易市场的社会福利。图6(c)表明显然，匹配人数越多，市场的盈利随之越多。随机匹配法和高低匹配法，由于匹配率较低，所以对应的社会福利也较小。最大满意度匹配和最大价格差匹配的匹配率高，计算得到的社会福利也较大。以价格为权重的匹配，侧重于收益，可以从图中看到社会福利明显高于以满意度为权重的匹配。

4.3.4 算法效率

最后，在更大规模人数下验证算法效率，生成买卖双方各100人、1000人、10 000人进行交易的情况，如图6(d)所示。

随机匹配法只需生成一对买卖方id列表，相应进行匹配，运算时间非常快，实验中都是ms级。

高低匹配法中需要将买卖双方的价格进行排序，需要一定的运算时间，相比随机匹配时间大约为3倍，但仍然是ms级。

只有在参评人数足够多时，不同算法的差距才表现明显。人数在1500时，算法差距并不大。设置人数2000时，算法就从1 ms时间增加到852 ms，当买卖双方人数达到20 000时，运行时间就达到了3360 s，计算时间就更长。

KM算法的时间复杂度为O(n3)，文献[11]通过改进后的复杂度为O(n2)与O(n3)之间，在一定程度上降低了算法运行时间，但是总的时间复杂度还是O(n3)。

总的来说，二分图匹配可以提高买卖双方的匹配率，但其计算复杂度较高，不适用于超大规模服务的应用。

5 结束语

针对目前视频服务商动态服务的需求，实现视频服务商的服务动态扩展，构建了一种流媒体资源交易模型，并据此模型设计了一种基于二分图交易匹配算法。在交易前，交易平台对资源参数进行筛选和分级，按照不同等级将买方和卖方分类，再进行最佳资源交易匹配。最后，通过数值仿真验证算法的有效性。

交易是以固定时间或市场需求进行的，在交易中未考虑买方或卖方动态加入的问题。在后继的工作中将考虑买卖方动态加入资源市场的情况，以及如何利用机器学习方法实现更高效的资源交易处理。