基于雙向拍賣的流媒體資源交易模型

薛楊上，李澤平，陳仁康

(貴州大學 計算機科學與技術學院，貴州 貴陽 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 結束語

針對目前視頻服務商動態服務的需求，實現視頻服務商的服務動態擴展，構建了一種流媒體資源交易模型，并據此模型設計了一種基于二分圖交易匹配算法。在交易前，交易平臺對資源參數進行篩選和分級，按照不同等級將買方和賣方分類，再進行最佳資源交易匹配。最后，通過數值仿真驗證算法的有效性。

交易是以固定時間或市場需求進行的，在交易中未考慮買方或賣方動態加入的問題。在后繼的工作中將考慮買賣方動態加入資源市場的情況，以及如何利用機器學習方法實現更高效的資源交易處理。