薛楊上，李澤平，陳仁康

(貴州大學(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白皮書[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ò)拍賣的方式進(jìn)行資源分配，可以使得資源提供商獲得更多的收益。

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

1 相關(guān)工作

在云計(jì)算中，張?bào)K先等[6]提出基于組合拍賣的云計(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ì)象的多維拍賣機(jī)制，實(shí)驗(yàn)結(jié)果表明該機(jī)制有效提高了市場(chǎng)的收益。叢鑫等[11]基于拍賣機(jī)制提出一種企業(yè)級(jí)網(wǎng)絡(luò)最優(yōu)匹配資源分配(OMRA)策略。Baranwal等[12]提出了一種用于云資源采購(gòu)的多屬性組合反向拍賣機(jī)制，考慮價(jià)格以及非價(jià)格屬性，使用貪心算法來(lái)求解該模型，并在多項(xiàng)式時(shí)間內(nèi)獲得近似最優(yōu)解。諸葛斌等[5]在SDN中運(yùn)用拍賣模型，提出一種價(jià)格適應(yīng)協(xié)商算法，有效地解決SDN資源交易問(wèn)題。劉媛妮等[13]在群智感知網(wǎng)絡(luò)中提出了一種基于拍賣機(jī)制的激勵(lì)機(jī)制，有效地提高了任務(wù)完成率。

2 流媒體資源交易拍賣模型

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)模型

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

圖1 流媒體資源拍賣模型

2.2.1 實(shí)體

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

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

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

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

2.2.2 拍賣流程

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

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

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

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

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

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

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

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

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

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

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

圖2 資源拍賣交易流程

2.3 符號(hào)定義

云計(jì)算中主要以不同類型的VM為出售資源，即將多種資源捆綁為一臺(tái)VM進(jìn)行交易。為了提高買方的滿意度，更加細(xì)化資源種類。將資源類型分為CPU、內(nèi)存、外存(硬盤)、帶寬。資源需求方可以準(zhǔn)確地請(qǐng)求所需的資源量，從而不必受到預(yù)定義的VM約束。受云計(jì)算資源服務(wù)啟發(fā)，構(gòu)建一種流媒體資源交易拍賣模型(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)

拍賣算法設(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à)，買賣雙方不能通過(guò)謊報(bào)競(jìng)拍信息以獲得更高的收益。對(duì)于買方i，當(dāng)前策略的效益大于其它策略的效益，即u(bi)≥u’(bi)。 同理，對(duì)于賣方j(luò)，u(sj)≥u’(sj)。 其中，u(bi) 是買方i的真實(shí)效用，u(sj) 是賣方j(luò)的真實(shí)效用，u’(bi) 是買方i的報(bào)告效用，u’(sj) 是賣方j(luò)的報(bào)告效用。

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

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

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

預(yù)算平衡是為了確保交易市場(chǎng)的支出不超過(guò)收入，拍賣人不用通過(guò)補(bǔ)貼市場(chǎng)來(lái)促成買賣雙方進(jìn)行交易。即pi=pj，i∈n，j∈m， 其中pi是買方i成交價(jià)格，pj是賣方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)效率。有效的拍賣算法可以使社會(huì)福利最大化，但交易成功率更符合實(shí)際需求，這樣可以使買方和賣方都能從中受益。

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

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

3.2 二分圖模型

叢鑫等[11]提出的最佳匹配拍賣算法，依據(jù)買賣雙方的價(jià)格差為權(quán)值，得到最大匹配。并且，改進(jìn)Kuhn-Munkres(KM)算法進(jìn)行二分圖最大權(quán)匹配。劉媛妮等[13]提出了一種基于逆向拍賣最大化用戶效用的模型以及基于二分圖的用戶匹配算法。在邊緣計(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]在電子中介交易提出了買賣雙方及中介滿意度最大的交易匹配模型，有效地實(shí)現(xiàn)了高效低成本的交易匹配。李雄一等[17]提出了考慮模糊語(yǔ)言的3種多屬性匹配決策方法，并構(gòu)建數(shù)學(xué)模型與對(duì)應(yīng)的求解算法。熊化峰等[18]根據(jù)屬性偏好系數(shù)，衡量買賣雙方的滿意度和偏好序。結(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ù)買方偏好，設(shè)置不同的權(quán)重ωk，并根據(jù)權(quán)重計(jì)算出綜合滿意度。賣方根據(jù)買方所給出的權(quán)重計(jì)算出售資源的綜合達(dá)標(biāo)度。

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

0≤ωk≤1

(1)

(2)

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

(3)

(4)

3.2.2 買賣交易匹配模型

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

依據(jù)買方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和賣方y(tǒng)j的資源匹配權(quán)重，設(shè)買方xi資源滿意度為bsi，賣方y(tǒng)j的資源達(dá)標(biāo)度為ssj，則satis(xi,yj)=ssj-bsi。

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

二分圖建模后，買賣雙方的匹配度計(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 買賣雙方匹配

3.3 資源組合交易算法

3.3.1 算法描述

算法1：RPTA

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

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

(1)if(BIDb.length()>BIDs.length())://賣方不足則補(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//將買方i從競(jìng)拍集中排除

(8)for(sjinBIDs):

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

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

(11)for(biinBIDb):

(12)switch(bi.resouces): //買方資源分級(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): //賣方資源分級(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) //買方報(bào)價(jià)>賣方要價(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ì)兼容。

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

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

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

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

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

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

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

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

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

首先，近似判斷買賣雙方是否誠(chéng)實(shí)，復(fù)雜度為N(n+m)， 然后進(jìn)行買賣方的篩選復(fù)雜度為N(n3+m3)， 再計(jì)算滿足資源要求的買賣雙方滿意度的復(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ī)匹配策略：在滿足條件的買賣方中，隨機(jī)生成一組id進(jìn)行匹配。滿足條件的買賣雙方均有一定概率進(jìn)行匹配交易。在配對(duì)的買賣方中，以價(jià)格和滿意度為標(biāo)準(zhǔn)，即買方價(jià)格高于賣方且賣方的資源能夠達(dá)到買方的需求。

3.4.2 賣方市場(chǎng)

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

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

3.4.3 買方市場(chǎng)

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

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

4 算例說(shuō)明

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

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

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

4.2 算法示例

4.2.1 競(jìng)拍信息

為方便說(shuō)明，設(shè)置5個(gè)買方和5個(gè)賣方進(jìn)行RPTA示例，買賣雙方數(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則被排除到匹配列表之外，本次算例中賣方4報(bào)價(jià)超過(guò)了價(jià)格浮動(dòng)閾值，視為惡意競(jìng)價(jià)，則被排除到交易外。

其次，為確保賣方能夠保證買方的服務(wù)，同時(shí)使得交易資源更加接近，降低資源的浪費(fèi)，則進(jìn)行等級(jí)劃分。買方所有資源必須小于等于等級(jí)資源數(shù)量，否則資源服務(wù)不能被滿足，例如買方4，首先從最低等級(jí)進(jìn)行對(duì)比，幾乎所有資源都符合低等級(jí)，但外存為1.4>1，低等級(jí)無(wú)法滿足，所以買方被劃分到中等級(jí)。相反，賣方所有資源必須大于等于等級(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ì)算綜合滿意度。

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

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

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

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

(1)綜合滿意度

(5)

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

(2)匹配率

MR=M/(n+m)

(6)

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

(3)社會(huì)福利

(7)

社會(huì)福利SW為所有買方和賣方的效用之和，如式(7)所示。買方i對(duì)資源組合的效用定義為u(bi)=pbi-pi， 同樣，賣方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專業(yè)版(64位)。

以均勻分布隨機(jī)生成買賣雙方的資源序列，資源數(shù)量范圍見(jiàn)表6，設(shè)置買賣雙方各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á)到了買賣雙方價(jià)格最優(yōu)匹配，市場(chǎng)的收益最大化，但賣方提供的資源質(zhì)量并不令買方感到滿意。

4.3.2 匹配率

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

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

4.3.3 匹配結(jié)果

通過(guò)將買賣雙方的估值與實(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)證算法效率，生成買賣雙方各100人、1000人、10 000人進(jìn)行交易的情況，如圖6(d)所示。

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

高低匹配法中需要將買賣雙方的價(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)買賣雙方人數(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ō)，二分圖匹配可以提高買賣雙方的匹配率，但其計(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í)將買方和賣方分類，再進(jìn)行最佳資源交易匹配。最后，通過(guò)數(shù)值仿真驗(yàn)證算法的有效性。

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