基于雙向拍賣(mài)的流媒體資源交易模型

薛楊上，李澤平，陳仁康

(貴州大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，貴州 貴陽(yáng) 550025)

0 引 言

目前互聯(lián)網(wǎng)難以在網(wǎng)絡(luò)資源有限的情況下，為大規(guī)模流媒體應(yīng)用提供高質(zhì)量的視頻服務(wù)。傳統(tǒng)的流媒體分發(fā)服務(wù)主要基于內(nèi)容分發(fā)網(wǎng)絡(luò)(content delivery network，CDN)或?qū)Φ染W(wǎng)絡(luò)(peer to peer，P2P)的架構(gòu)。CDN存在部署成本高、可擴(kuò)展性差、資源浪費(fèi)的問(wèn)題。P2P的可靠性差，不能保證服務(wù)質(zhì)量。而云計(jì)算彈性服務(wù)為視頻服務(wù)商帶來(lái)了新的解決方案。

根據(jù)Cisco白皮書(shū)[1]，視頻數(shù)據(jù)請(qǐng)求量在近幾年增速迅猛，2020年每月視頻數(shù)據(jù)量達(dá)到兩萬(wàn)PB以上。而且，在不同時(shí)間段，用戶訪問(wèn)人數(shù)差別較大，尤其是高峰期與低谷期的訪問(wèn)量差別尤為明顯。實(shí)際上，美國(guó)主流視頻服務(wù)商N(yùn)etflix早在2012年就已經(jīng)把基礎(chǔ)架構(gòu)遷移到Amazon云端服務(wù)器[2]。目前國(guó)內(nèi)云服務(wù)商阿里云[3]、騰訊云[4]等都提供了相應(yīng)的流媒體服務(wù)資源租賃方案。但是租賃方式比較單一，長(zhǎng)期按年、月租賃資源，短期則是通過(guò)劃分不同大小的虛擬機(jī)(virtual machine, VM)按小時(shí)租賃。而通過(guò)拍賣(mài)的方式進(jìn)行資源分配，可以使得資源提供商獲得更多的收益。

動(dòng)態(tài)資源交易(租賃)是服務(wù)商獲取資源的方式之一，資源以拍賣(mài)的方式進(jìn)行交易使視頻服務(wù)商能以低服務(wù)成本獲得更大的收益。通過(guò)引入經(jīng)濟(jì)學(xué)理論，進(jìn)行動(dòng)態(tài)資源交易(拍賣(mài))是近年來(lái)的研究熱點(diǎn)之一[5-8]。

1 相關(guān)工作

在云計(jì)算中，張?bào)K先等[6]提出基于組合拍賣(mài)的云計(jì)算虛擬資源分配和定價(jià)機(jī)制(VRAP)，用戶可以一次提出多資源需求，資源提供商可以獲得更大的收益。通過(guò)設(shè)計(jì)一種資源再分配策略來(lái)保證提供商收益的最大化。隨后，張?bào)K先等[7]嘗試使用機(jī)器學(xué)習(xí)方法進(jìn)行資源分配，提出了3種基于監(jiān)督學(xué)習(xí)的資源分配算法，價(jià)格機(jī)制采用的是VCG機(jī)制，該機(jī)制雖然能夠有效實(shí)現(xiàn)社會(huì)福利最大化，但計(jì)算量較大。Cheng等[8]提出一種云輔助視頻點(diǎn)播系統(tǒng)(CPA-VoD)，能夠有效緩解網(wǎng)絡(luò)壓力和降低視頻服務(wù)商的運(yùn)營(yíng)成本。Cui等[9]提出了一種多目標(biāo)優(yōu)化算法NSGA-II的最優(yōu)云租賃算法，使得請(qǐng)求者選擇最合適的云存儲(chǔ)服務(wù)器。上述研究雖然有效地利用了云資源進(jìn)行視頻服務(wù)，但研究重點(diǎn)側(cè)重于視頻流行度預(yù)測(cè)及資源緩存策略，而未考慮使用具體交易機(jī)制進(jìn)行服務(wù)資源的分配。Tang等[10]視頻流服務(wù)中以不同碼率視頻塊為交易資源，提出了單對(duì)象和多對(duì)象的多維拍賣(mài)機(jī)制，實(shí)驗(yàn)結(jié)果表明該機(jī)制有效提高了市場(chǎng)的收益。叢鑫等[11]基于拍賣(mài)機(jī)制提出一種企業(yè)級(jí)網(wǎng)絡(luò)最優(yōu)匹配資源分配(OMRA)策略。Baranwal等[12]提出了一種用于云資源采購(gòu)的多屬性組合反向拍賣(mài)機(jī)制，考慮價(jià)格以及非價(jià)格屬性，使用貪心算法來(lái)求解該模型，并在多項(xiàng)式時(shí)間內(nèi)獲得近似最優(yōu)解。諸葛斌等[5]在SDN中運(yùn)用拍賣(mài)模型，提出一種價(jià)格適應(yīng)協(xié)商算法，有效地解決SDN資源交易問(wèn)題。劉媛妮等[13]在群智感知網(wǎng)絡(luò)中提出了一種基于拍賣(mài)機(jī)制的激勵(lì)機(jī)制，有效地提高了任務(wù)完成率。

2 流媒體資源交易拍賣(mài)模型

2.1 問(wèn)題表述

在流媒體服務(wù)環(huán)境中，用戶請(qǐng)求量在緩存服務(wù)器能力范圍之內(nèi)時(shí)，服務(wù)器無(wú)需進(jìn)行擴(kuò)展，直接使用當(dāng)前服務(wù)器即可保證用戶請(qǐng)求。但在某個(gè)時(shí)段迎來(lái)視頻訪問(wèn)高峰期，用戶請(qǐng)求量突然增大，此時(shí)服務(wù)器無(wú)法承載如此多的用戶請(qǐng)求，就可以臨時(shí)租賃(空閑)服務(wù)器以滿足當(dāng)前用戶請(qǐng)求。

2.2 系統(tǒng)模型

流媒體資源拍賣(mài)交易模型如圖1所示，拍賣(mài)人(資源交易平臺(tái))每隔固定時(shí)間T組織一次拍賣(mài)。買(mǎi)賣(mài)雙方根據(jù)其自身的需求分別向拍賣(mài)人提交資源報(bào)價(jià)和資源要價(jià)的競(jìng)拍信息。若將買(mǎi)賣(mài)雙方所有需求全部發(fā)送到拍賣(mài)人會(huì)導(dǎo)致服務(wù)器運(yùn)行壓力過(guò)大，引入代理先把買(mǎi)賣(mài)雙方競(jìng)拍信息收集、整理、統(tǒng)一后提交到拍賣(mài)人。拍賣(mài)人在收到競(jìng)拍信息后，根據(jù)拍賣(mài)算法確定買(mǎi)賣(mài)成交的資源數(shù)量和成交價(jià)格。

圖1 流媒體資源拍賣(mài)模型

2.2.1 實(shí)體

(1)視頻服務(wù)商：作為資源的需求方，為了滿足其用戶對(duì)視頻資源的請(qǐng)求，動(dòng)態(tài)地租賃計(jì)算資源以服務(wù)用戶。

(2)資源提供商：作為資源的供給方，出售或租賃自己的計(jì)算資源獲取利潤(rùn)，以此增加自己的收益。

(3)代理：收集買(mǎi)賣(mài)雙方競(jìng)價(jià)信息，整理并發(fā)送給拍賣(mài)人。代理可有效緩解服務(wù)器的壓力，避免多個(gè)請(qǐng)求集中于單個(gè)服務(wù)器造成網(wǎng)絡(luò)瓶頸。

(4)拍賣(mài)人(資源交易平臺(tái))：收集買(mǎi)賣(mài)雙方競(jìng)價(jià)信息，按照交易流程和規(guī)則進(jìn)行最優(yōu)資源分配及交易價(jià)格的計(jì)算、發(fā)布最終交易結(jié)果等。

2.2.2 拍賣(mài)流程

拍賣(mài)流程如圖2所示，交易過(guò)程如下：

(1)買(mǎi)方向拍賣(mài)人提交資源需求信息；

(2)賣(mài)方向拍賣(mài)人提交資源供給信息；

(3)拍賣(mài)人收集買(mǎi)賣(mài)雙方提交的信息；

(4)收集信息完畢之后組織一次拍賣(mài)，并向參與者收取保證金；

(5)買(mǎi)賣(mài)雙方分別向拍賣(mài)人上交資源拍賣(mài)的保證金；

(6)拍賣(mài)人通過(guò)雙方競(jìng)價(jià)信息，計(jì)算得出匹配結(jié)果；

(7)向買(mǎi)賣(mài)雙方發(fā)布交易匹配的結(jié)果；

(8)根據(jù)結(jié)果，買(mǎi)賣(mài)雙方進(jìn)行資源交易，提供相應(yīng)的服務(wù)；

(9)拍賣(mài)人根據(jù)服務(wù)質(zhì)量，對(duì)買(mǎi)賣(mài)雙方進(jìn)行獎(jiǎng)懲記錄；

(10)從保證金中按比例扣取服務(wù)費(fèi)，然后退還各自參與者。

圖2 資源拍賣(mài)交易流程

2.3 符號(hào)定義

云計(jì)算中主要以不同類(lèi)型的VM為出售資源，即將多種資源捆綁為一臺(tái)VM進(jìn)行交易。為了提高買(mǎi)方的滿意度，更加細(xì)化資源種類(lèi)。將資源類(lèi)型分為CPU、內(nèi)存、外存(硬盤(pán))、帶寬。資源需求方可以準(zhǔn)確地請(qǐng)求所需的資源量，從而不必受到預(yù)定義的VM約束。受云計(jì)算資源服務(wù)啟發(fā)，構(gòu)建一種流媒體資源交易拍賣(mài)模型(streaming media resource transaction model，SMRTM)。為方便表述，表1給出后文所用的符號(hào)集。

表1 符號(hào)集

但是資源組合交易分配問(wèn)題為贏標(biāo)者選擇問(wèn)題(winner determination problem，WDP)，是一個(gè)NP-hard問(wèn)題[6,7,12,13]，為了降低算法的復(fù)雜度，將多種資源組合交易參數(shù)以加權(quán)的方式化為資源綜合指標(biāo)(滿意度)進(jìn)行交易。

3 流媒體資源交易算法

3.1 設(shè)計(jì)目標(biāo)

拍賣(mài)算法設(shè)計(jì)中存在5個(gè)重要屬性，而Kumar等[14]指出當(dāng)前沒(méi)有任何算法能夠保證同時(shí)滿足這些屬性，屬性分別如下：

3.1.1 激勵(lì)兼容(incentive compatible)

激勵(lì)兼容,又稱誠(chéng)實(shí)機(jī)制(truthfulness)?？杀ＷC每個(gè)競(jìng)拍者如實(shí)地出價(jià)，買(mǎi)賣(mài)雙方不能通過(guò)謊報(bào)競(jìng)拍信息以獲得更高的收益。對(duì)于買(mǎi)方i，當(dāng)前策略的效益大于其它策略的效益，即u(bi)≥u’(bi)。 同理，對(duì)于賣(mài)方j(luò)，u(sj)≥u’(sj)。 其中，u(bi) 是買(mǎi)方i的真實(shí)效用，u(sj) 是賣(mài)方j(luò)的真實(shí)效用，u’(bi) 是買(mǎi)方i的報(bào)告效用，u’(sj) 是賣(mài)方j(luò)的報(bào)告效用。

3.1.2 個(gè)體理性(individual rationality)

個(gè)體理性是每個(gè)競(jìng)拍人不會(huì)損失自己的利益。在拍賣(mài)的交易過(guò)程中，買(mǎi)方或賣(mài)方效用都不可能為負(fù)，即u(bi)≥0，u(sj)≥0。

3.1.3 預(yù)算平衡(budget balance)

預(yù)算平衡是為了確保交易市場(chǎng)的支出不超過(guò)收入，拍賣(mài)人不用通過(guò)補(bǔ)貼市場(chǎng)來(lái)促成買(mǎi)賣(mài)雙方進(jìn)行交易。即pi=pj，i∈n，j∈m， 其中pi是買(mǎi)方i成交價(jià)格，pj是賣(mài)方j(luò)成交價(jià)格。若pi-pj≥0，i∈n，j∈m， 則該機(jī)制是弱預(yù)算平衡。

3.1.4 系統(tǒng)效率(system efficiency)

參考經(jīng)濟(jì)學(xué)中的配置效率，可以通過(guò)社會(huì)福利和交易成功率來(lái)衡量系統(tǒng)效率。有效的拍賣(mài)算法可以使社會(huì)福利最大化，但交易成功率更符合實(shí)際需求，這樣可以使買(mǎi)方和賣(mài)方都能從中受益。

3.1.5 計(jì)算效率(computational efficiency)

如果可以在多項(xiàng)式時(shí)間內(nèi)計(jì)算出資源分配和價(jià)格支付的結(jié)果，則拍賣(mài)算法在計(jì)算上可行。

3.2 二分圖模型

叢鑫等[11]提出的最佳匹配拍賣(mài)算法，依據(jù)買(mǎi)賣(mài)雙方的價(jià)格差為權(quán)值，得到最大匹配。并且，改進(jìn)Kuhn-Munkres(KM)算法進(jìn)行二分圖最大權(quán)匹配。劉媛妮等[13]提出了一種基于逆向拍賣(mài)最大化用戶效用的模型以及基于二分圖的用戶匹配算法。在邊緣計(jì)算中，張守利等[15]提出了一種云端動(dòng)態(tài)集成的服務(wù)適配方法，優(yōu)化改進(jìn)二分圖最優(yōu)匹配KM算法并且結(jié)合排隊(duì)論增強(qiáng)實(shí)時(shí)性，最大縮短端服務(wù)平均適配請(qǐng)求響應(yīng)時(shí)間。吳劍云等[16]在電子中介交易提出了買(mǎi)賣(mài)雙方及中介滿意度最大的交易匹配模型，有效地實(shí)現(xiàn)了高效低成本的交易匹配。李雄一等[17]提出了考慮模糊語(yǔ)言的3種多屬性匹配決策方法，并構(gòu)建數(shù)學(xué)模型與對(duì)應(yīng)的求解算法。熊化峰等[18]根據(jù)屬性偏好系數(shù)，衡量買(mǎi)賣(mài)雙方的滿意度和偏好序。結(jié)合以上文獻(xiàn)，以最大資源綜合滿意度為目標(biāo)，實(shí)現(xiàn)市場(chǎng)社會(huì)福利最大化，基于二分圖設(shè)計(jì)了一種資源組合交易算法(resource portfolio trading algorithm，RPTA)。

3.2.1 資源偏好權(quán)重

在流媒體服務(wù)中，將流媒體多種資源根據(jù)買(mǎi)方偏好，設(shè)置不同的權(quán)重ωk，并根據(jù)權(quán)重計(jì)算出綜合滿意度。賣(mài)方根據(jù)買(mǎi)方所給出的權(quán)重計(jì)算出售資源的綜合達(dá)標(biāo)度。

為解決資源總體符合要求，但可能存在單個(gè)資源無(wú)法達(dá)到服務(wù)要求，導(dǎo)致無(wú)法服務(wù)。所以首先需要設(shè)定最低資源標(biāo)準(zhǔn)，設(shè)定資源等級(jí)，買(mǎi)賣(mài)雙方只有達(dá)到資源標(biāo)準(zhǔn)要求才能進(jìn)行資源綜合

0≤ωk≤1

(1)

(2)

買(mǎi)方滿意度bsi和賣(mài)方達(dá)標(biāo)度ssj計(jì)算如下

(3)

(4)

3.2.2 買(mǎi)賣(mài)交易匹配模型

通過(guò)將權(quán)匹配與滿意度結(jié)合，基于二分圖設(shè)計(jì)一種資源滿意度的最佳匹配算法，建立數(shù)學(xué)模型如下。

依據(jù)買(mǎi)方id序列和賣(mài)方id序列建立圖G=(V,E)。 其中，V={xi∪yj|xi∈X,yj∈Y}，X為買(mǎi)方集合，Y為賣(mài)方集合，E={(x,y)|xi∈X,yj∈Y,satis(xi,yj)≥0}，x,y∈E(G)。 滿意度satis(xi,yj) 表示買(mǎi)方xi和賣(mài)方y(tǒng)j的資源匹配權(quán)重，設(shè)買(mǎi)方xi資源滿意度為bsi，賣(mài)方y(tǒng)j的資源達(dá)標(biāo)度為ssj，則satis(xi,yj)=ssj-bsi。

滿意度優(yōu)先匹配算法，買(mǎi)方對(duì)資源需求優(yōu)于對(duì)價(jià)格的要求，以買(mǎi)方需求為目標(biāo)，兼顧賣(mài)方收益的同時(shí)，進(jìn)行最大滿意度匹配。

二分圖建模后，買(mǎi)賣(mài)雙方的匹配度計(jì)算可以轉(zhuǎn)化為運(yùn)用 KM算法對(duì)二分圖最大權(quán)匹配的求解。

由于KM算法對(duì)雙方節(jié)點(diǎn)數(shù)量有要求，通過(guò)增加節(jié)點(diǎn)的方式滿足算法運(yùn)行條件。若m>n，則在n點(diǎn)集中補(bǔ)充m-n個(gè)節(jié)點(diǎn)，并在對(duì)應(yīng)的邊上權(quán)賦值為0，相反則補(bǔ)充n-m個(gè)節(jié)點(diǎn)，以此保證二分圖中雙方節(jié)點(diǎn)數(shù)相等。匹配前后的結(jié)果如圖3所示。

圖3 買(mǎi)賣(mài)雙方匹配

3.3 資源組合交易算法

3.3.1 算法描述

算法1：RPTA

輸入：買(mǎi)方報(bào)價(jià)集BIDb，賣(mài)方要價(jià)集BIDs，權(quán)重ω，資源等級(jí)(rl，rm，rh)，價(jià)格浮動(dòng)閾值pf

輸出：匹配結(jié)果M

(1)if(BIDb.length()>BIDs.length())://賣(mài)方不足則補(bǔ)充

(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//將買(mǎi)方i從競(jìng)拍集中排除

(8)for(sjinBIDs):

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

(10)BID/sj//將賣(mài)方j(luò)從競(jìng)拍集中排除

(11)for(biinBIDb):

(12)switch(bi.resouces): //買(mǎi)方資源分級(jí)

(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): //賣(mài)方資源分級(jí)

(21)caserl:

(22)sj.level=low

(23)caserm:

(24)sj.level=median

(25)caserh:

(26)sj.level=high

(29)satis(xi,yj)=ssj-bsi//計(jì)算滿意度

(30)for(biinBIDb):

(31)for(sjinBIDs):

(32)if(pbi>psj) //買(mǎi)方報(bào)價(jià)>賣(mài)方要價(jià)(前提條件)

(33)pij=(pbi+psj)/2 //設(shè)定成交價(jià)

(34)if(bi.level==sj.level)： //同等級(jí)進(jìn)行邊連接

(35) 將bsi及ssj作為頂標(biāo)、 權(quán)值為satis(xi,yj)加入邊到二分圖G， 滿足條件l(xi)+l(yj)≥satis(xi,yj)

(36)else: 將bsi及ssj作為頂標(biāo)、 權(quán)值設(shè)定為0加入邊到二分圖G

(37)給定頂標(biāo)值：l(xi)=max(satis(xi,yj)),l(yj)=0， 形成新二分圖G’。

(38)計(jì)算初始匹配M。

(39)若X中頂點(diǎn)皆被M匹配， 則停止算法，M即為最大權(quán)完美匹配， 否則取G’中未被M匹配的頂點(diǎn)uu, 令SS={uu}，TT=?。

(40)若NG’(SS)?TT， 轉(zhuǎn)步驟(41)； 若NG’(SS)=TT， 則取

(41)選NG’(SS)-TT中頂點(diǎn)y， 若y已被M匹配， 且y,z∈M， 則SS=SS∪{z}，TT=TT∪{y}， 轉(zhuǎn)步驟(40)； 否則， 取Gl中一個(gè)M可增廣路P(uu,y)， 令M=(M-E(P))∪(E(P)-M)， 轉(zhuǎn)步驟(39)。 其中，NG’(SS)為G’中SS的相鄰頂點(diǎn)集。

(42)returnM

3.3.2 算法分析

(1)RPTA近似激勵(lì)兼容

由于算法側(cè)重考慮市場(chǎng)收益最大化，而不能保證參與者都是誠(chéng)實(shí)的，并非嚴(yán)格激勵(lì)兼容。

故為了防止買(mǎi)賣(mài)雙方謊報(bào)與資源不符的價(jià)格，以謀取自身更高的收益，RPTA設(shè)定拍賣(mài)人擁有資源單價(jià)uk表示第k種資源單位時(shí)間的單元保留價(jià)，資源標(biāo)準(zhǔn)價(jià)格為PS=u1r1+…+ukrk。 通過(guò)PS可以衡量買(mǎi)賣(mài)方報(bào)價(jià)的差距，從而近似判斷買(mǎi)方或賣(mài)方是否存在惡意競(jìng)價(jià)。

設(shè)定浮動(dòng)閾值pf，若買(mǎi)賣(mài)雙方報(bào)價(jià)若與標(biāo)準(zhǔn)價(jià)格相差超過(guò)浮動(dòng)閾值，則從競(jìng)價(jià)集合中排除該買(mǎi)方或賣(mài)方，即 |pbi-PS|≥pf或 |psj-PS|≥pf， 則BIDbi或BIDssj。

(2)RPTA滿足個(gè)體理性

在資源交易中，買(mǎi)賣(mài)雙方都不會(huì)使得自己虧本。即對(duì)買(mǎi)方來(lái)說(shuō)，滿足pbi≥pi。 而對(duì)于賣(mài)方，滿足psj≤pj， 則有u(bi)≥0，u(sj)≥0。

(3)RPTA滿足預(yù)算平衡

將買(mǎi)賣(mài)雙方的最終成交價(jià)設(shè)定為買(mǎi)方報(bào)價(jià)與賣(mài)方要價(jià)之和的一半，在資源市場(chǎng)中保證了支出不超過(guò)收入。即pi=pj=pij=(pbi+psj)/2。

(4)RPTA滿足系統(tǒng)有效

算法的目標(biāo)為最大化綜合滿意度，且買(mǎi)方報(bào)價(jià)必須大于等于賣(mài)方要價(jià)交易才能達(dá)成，即pbi≥psj，所以交易市場(chǎng)中總存在有效收益，保證了社會(huì)福利。而二分圖匹配的性質(zhì)，保證了買(mǎi)賣(mài)雙方的匹配率。

(5)RPTA滿足計(jì)算有效

首先，近似判斷買(mǎi)賣(mài)雙方是否誠(chéng)實(shí)，復(fù)雜度為N(n+m)， 然后進(jìn)行買(mǎi)賣(mài)方的篩選復(fù)雜度為N(n3+m3)， 再計(jì)算滿足資源要求的買(mǎi)賣(mài)雙方滿意度的復(fù)雜度為N(n+m)， 最后建立二分圖模型并運(yùn)行KM算法，找到最大滿意度匹配。復(fù)雜度為N(n3)。 所以，算法總復(fù)雜度為N(2(m+n+n3+m3))， 即在多項(xiàng)式時(shí)間內(nèi)可以計(jì)算出結(jié)果。

3.4 不同市場(chǎng)需求的匹配策略

根據(jù)不同市場(chǎng)需求，設(shè)定不同的交易匹配策略。

3.4.1 公平市場(chǎng)

隨機(jī)匹配策略：在滿足條件的買(mǎi)賣(mài)方中，隨機(jī)生成一組id進(jìn)行匹配。滿足條件的買(mǎi)賣(mài)雙方均有一定概率進(jìn)行匹配交易。在配對(duì)的買(mǎi)賣(mài)方中，以價(jià)格和滿意度為標(biāo)準(zhǔn)，即買(mǎi)方價(jià)格高于賣(mài)方且賣(mài)方的資源能夠達(dá)到買(mǎi)方的需求。

3.4.2 賣(mài)方市場(chǎng)

高低匹配策略：買(mǎi)方價(jià)格從高到低排序，賣(mài)方價(jià)格從低到高排序，賣(mài)方滿足買(mǎi)方需求且按照排序結(jié)果一一進(jìn)行配對(duì)。買(mǎi)賣(mài)雙方的價(jià)格差距大，故賣(mài)方的收益很高，則整個(gè)交易市場(chǎng)的收益也比較高，從而有利于賣(mài)方獲取更多的收益。

二分圖最大收益匹配策略：以買(mǎi)賣(mài)雙方的價(jià)格差作為權(quán)重，進(jìn)行二分圖最大權(quán)匹配，使得整個(gè)市場(chǎng)的交易剩余價(jià)值最大，賣(mài)方獲得的收益也較大。

3.4.3 買(mǎi)方市場(chǎng)

二分圖資源滿意度最大匹配策略：根據(jù)買(mǎi)方偏好，權(quán)設(shè)定為不同的類(lèi)型。通過(guò)帶權(quán)最大匹配求得買(mǎi)賣(mài)雙方屬性差最大?？紤]買(mǎi)方對(duì)資源綜合滿意度(性能)與價(jià)格兩方面。以買(mǎi)方的需求為主要目標(biāo)，滿足需求的賣(mài)方，買(mǎi)方從中選擇最優(yōu)進(jìn)行交易。

根據(jù)滿意度，設(shè)定權(quán)重進(jìn)行二分圖最大權(quán)匹配，可以滿足整個(gè)市場(chǎng)的滿意度收益最大，找到最佳匹配。以滿意度為目標(biāo)，有利于買(mǎi)方滿意度，資源服務(wù)質(zhì)量的提高。

4 算例說(shuō)明

4.1 參數(shù)設(shè)置

流媒體資源交易的參數(shù)沒(méi)有統(tǒng)一的規(guī)定，文中的流媒體交易參數(shù)包括CPU、內(nèi)存、外存(硬盤(pán))、帶寬。為了使得買(mǎi)賣(mài)雙方的資源能夠相互滿足且符合實(shí)際情況，將資源進(jìn)行資源等級(jí)劃分見(jiàn)表2。

表2 資源等級(jí)劃分

4.2 算法示例

4.2.1 競(jìng)拍信息

為方便說(shuō)明，設(shè)置5個(gè)買(mǎi)方和5個(gè)賣(mài)方進(jìn)行RPTA示例，買(mǎi)賣(mài)雙方數(shù)據(jù)競(jìng)拍信息見(jiàn)表3。

表3 交易者競(jìng)拍信息

4.2.2 運(yùn)行過(guò)程

首先，判斷是否存在惡意報(bào)價(jià)，設(shè)定資源單價(jià)u=[4,1,1,2]， 價(jià)格浮動(dòng)閾值pf=10， 計(jì)算PS，若超出pf則被排除到匹配列表之外，本次算例中賣(mài)方4報(bào)價(jià)超過(guò)了價(jià)格浮動(dòng)閾值，視為惡意競(jìng)價(jià)，則被排除到交易外。

其次，為確保賣(mài)方能夠保證買(mǎi)方的服務(wù)，同時(shí)使得交易資源更加接近，降低資源的浪費(fèi)，則進(jìn)行等級(jí)劃分。買(mǎi)方所有資源必須小于等于等級(jí)資源數(shù)量，否則資源服務(wù)不能被滿足，例如買(mǎi)方4，首先從最低等級(jí)進(jìn)行對(duì)比，幾乎所有資源都符合低等級(jí)，但外存為1.4>1，低等級(jí)無(wú)法滿足，所以買(mǎi)方被劃分到中等級(jí)。相反，賣(mài)方所有資源必須大于等于等級(jí)資源數(shù)量，否則無(wú)法服務(wù)，經(jīng)過(guò)資源劃分的結(jié)果見(jiàn)表4。

表4 交易者等級(jí)劃分

然后，分別設(shè)置對(duì)CPU、內(nèi)存、存儲(chǔ)、帶寬的權(quán)重ω=[0.2,0.1,0.3,0.4]， 以式(1)～式(4)計(jì)算綜合滿意度。

最后，將買(mǎi)方和賣(mài)方作為頂點(diǎn)建立二分圖模型，將綜合滿意度作為二分圖的權(quán)值，根據(jù)買(mǎi)賣(mài)雙方不同的對(duì)應(yīng)等級(jí)，將二分圖中對(duì)應(yīng)的邊進(jìn)行連接，邊連接完成之后，結(jié)合KM算法求最大權(quán)匹配。

初始化設(shè)置頂標(biāo)如圖4所示，買(mǎi)方頂標(biāo)設(shè)定為滿意度最大值，賣(mài)方頂標(biāo)初始化為0，圖中忽略了報(bào)價(jià)為0的邊。其中，由于買(mǎi)方3的價(jià)格達(dá)不到賣(mài)方報(bào)價(jià)則無(wú)法達(dá)成交易，而賣(mài)方4被排除，圖4中用虛線表示。

圖4 頂標(biāo)設(shè)定

4.2.3 算法評(píng)價(jià)指標(biāo)

(1)綜合滿意度

(5)

綜合滿意度為買(mǎi)方滿意度與賣(mài)方達(dá)標(biāo)度之差，如式(5)所示，滿意度是衡量買(mǎi)賣(mài)雙方資源需求或供給的指標(biāo)。

(2)匹配率

MR=M/(n+m)

(6)

匹配率為成功匹配的人數(shù)與總?cè)藬?shù)之比，如式(6)所示，匹配率可以得到市場(chǎng)中交易人數(shù)的占比，以此來(lái)衡量算法的有效性。

(3)社會(huì)福利

(7)

社會(huì)福利SW為所有買(mǎi)方和賣(mài)方的效用之和，如式(7)所示。買(mǎi)方i對(duì)資源組合的效用定義為u(bi)=pbi-pi， 同樣，賣(mài)方j(luò)效用為u(sj)=pj-psj， 其中，只有交易成功存在效益，否則為0。

4.2.4 匹配結(jié)果

x0頂標(biāo)為0.06，與邊上的權(quán)值相等，直接與y0成功匹配。x1與y0匹配，同理，x3匹配y1，但x3也對(duì)y1進(jìn)行了報(bào)價(jià)且資源滿意度大于x1，所以將x3匹配更大的權(quán)，與y1匹配。并且重新給x1尋找匹配，成功匹配y3。y1已經(jīng)被x3匹配，則x4不進(jìn)行匹配。最終，算法得到最大滿意度匹配結(jié)果如圖5所示。

圖5 匹配結(jié)果

將上文提到的幾種匹配策略進(jìn)行對(duì)比，得到匹配結(jié)果見(jiàn)表5。

表5 匹配結(jié)果

4.3 數(shù)值驗(yàn)證

采用Python語(yǔ)言進(jìn)行數(shù)值仿真，實(shí)驗(yàn)平臺(tái)如下:

計(jì)算機(jī)：CPU Intel Core i5-3470、內(nèi)存為16 GB、操作系統(tǒng)Windows 10專(zhuān)業(yè)版(64位)。

以均勻分布隨機(jī)生成買(mǎi)賣(mài)雙方的資源序列，資源數(shù)量范圍見(jiàn)表6，設(shè)置買(mǎi)賣(mài)雙方各100人、500人、1000人進(jìn)行仿真實(shí)驗(yàn)。

表6 資源范圍

以匹配率、資源滿意度、市場(chǎng)社會(huì)福利、計(jì)算效率4個(gè)方面進(jìn)行驗(yàn)證，如圖6所示。

4.3.1 綜合滿意度

圖6(a)表明幾次實(shí)驗(yàn)中，最大價(jià)格差匹配算法中滿意度明顯低于最大滿意度匹配算法得到的滿意度，由于沒(méi)有顧及資源滿意度，甚至可能出現(xiàn)滿意度為負(fù)的極端情況。說(shuō)明雖然達(dá)到了買(mǎi)賣(mài)雙方價(jià)格最優(yōu)匹配，市場(chǎng)的收益最大化，但賣(mài)方提供的資源質(zhì)量并不令買(mǎi)方感到滿意。

4.3.2 匹配率

圖6(b)表明此次交易匹配率，隨機(jī)匹配法的匹配率不高，而且多次實(shí)驗(yàn)結(jié)果表明匹配不穩(wěn)定，隨著不同實(shí)驗(yàn)不斷變化。高低匹配法匹配率也不高，由于排序后，買(mǎi)賣(mài)雙方的位置被固定，只能匹配到買(mǎi)方價(jià)格高于賣(mài)方價(jià)格的參與者。最大權(quán)二分圖匹配，由于其性質(zhì)，尋找最佳的匹配，匹配率較高且保證參數(shù)的權(quán)重最大。

圖6 RPTA算法衡量指標(biāo)

4.3.3 匹配結(jié)果

通過(guò)將買(mǎi)賣(mài)雙方的估值與實(shí)際的交易價(jià)格進(jìn)行對(duì)比，得到流媒體資源交易市場(chǎng)的社會(huì)福利。圖6(c)表明顯然，匹配人數(shù)越多，市場(chǎng)的盈利隨之越多。隨機(jī)匹配法和高低匹配法，由于匹配率較低，所以對(duì)應(yīng)的社會(huì)福利也較小。最大滿意度匹配和最大價(jià)格差匹配的匹配率高，計(jì)算得到的社會(huì)福利也較大。以價(jià)格為權(quán)重的匹配，側(cè)重于收益，可以從圖中看到社會(huì)福利明顯高于以滿意度為權(quán)重的匹配。

4.3.4 算法效率

最后，在更大規(guī)模人數(shù)下驗(yàn)證算法效率，生成買(mǎi)賣(mài)雙方各100人、1000人、10 000人進(jìn)行交易的情況，如圖6(d)所示。

隨機(jī)匹配法只需生成一對(duì)買(mǎi)賣(mài)方id列表，相應(yīng)進(jìn)行匹配，運(yùn)算時(shí)間非?？?，實(shí)驗(yàn)中都是ms級(jí)。

高低匹配法中需要將買(mǎi)賣(mài)雙方的價(jià)格進(jìn)行排序，需要一定的運(yùn)算時(shí)間，相比隨機(jī)匹配時(shí)間大約為3倍，但仍然是ms級(jí)。

只有在參評(píng)人數(shù)足夠多時(shí)，不同算法的差距才表現(xiàn)明顯。人數(shù)在1500時(shí)，算法差距并不大。設(shè)置人數(shù)2000時(shí)，算法就從1 ms時(shí)間增加到852 ms，當(dāng)買(mǎi)賣(mài)雙方人數(shù)達(dá)到20 000時(shí)，運(yùn)行時(shí)間就達(dá)到了3360 s，計(jì)算時(shí)間就更長(zhǎng)。

KM算法的時(shí)間復(fù)雜度為O(n3)，文獻(xiàn)[11]通過(guò)改進(jìn)后的復(fù)雜度為O(n2)與O(n3)之間，在一定程度上降低了算法運(yùn)行時(shí)間，但是總的時(shí)間復(fù)雜度還是O(n3)。

總的來(lái)說(shuō)，二分圖匹配可以提高買(mǎi)賣(mài)雙方的匹配率，但其計(jì)算復(fù)雜度較高，不適用于超大規(guī)模服務(wù)的應(yīng)用。

5 結(jié)束語(yǔ)

針對(duì)目前視頻服務(wù)商動(dòng)態(tài)服務(wù)的需求，實(shí)現(xiàn)視頻服務(wù)商的服務(wù)動(dòng)態(tài)擴(kuò)展，構(gòu)建了一種流媒體資源交易模型，并據(jù)此模型設(shè)計(jì)了一種基于二分圖交易匹配算法。在交易前，交易平臺(tái)對(duì)資源參數(shù)進(jìn)行篩選和分級(jí)，按照不同等級(jí)將買(mǎi)方和賣(mài)方分類(lèi)，再進(jìn)行最佳資源交易匹配。最后，通過(guò)數(shù)值仿真驗(yàn)證算法的有效性。

交易是以固定時(shí)間或市場(chǎng)需求進(jìn)行的，在交易中未考慮買(mǎi)方或賣(mài)方動(dòng)態(tài)加入的問(wèn)題。在后繼的工作中將考慮買(mǎi)賣(mài)方動(dòng)態(tài)加入資源市場(chǎng)的情況，以及如何利用機(jī)器學(xué)習(xí)方法實(shí)現(xiàn)更高效的資源交易處理。