基于帶寬優(yōu)化分配和Shapley值的網(wǎng)絡(luò)收益*

石 峰， 吳艷平

(1. 太原大學(xué) 計算中心， 太原 030032； 2. 長春職業(yè)技術(shù)學(xué)院 信息技術(shù)分院， 長春 130033)

盡管信息時代已經(jīng)邁入了千家萬戶，但互聯(lián)網(wǎng)業(yè)務(wù)和流量仍在不斷地發(fā)展和增長.互聯(lián)網(wǎng)業(yè)務(wù)不僅傾向于數(shù)量的增加，而且對質(zhì)量的要求也在明顯提高[1-3].此外，新興技術(shù)如物聯(lián)網(wǎng)、遠(yuǎn)程監(jiān)控和云計算也需要大量具有實時性要求的流量和全球網(wǎng)站的互連，因此，除了具有QoS性能的網(wǎng)絡(luò)外，這些服務(wù)還需要一種端到端的QoS來連接各種多樣化的載體網(wǎng)絡(luò)[4-6].如今的電信市場主要集中在流量服務(wù)方面，為了滿足客戶期望，電信公司被迫在容量上進(jìn)行大量投資，而這些投資如果不能獲得足夠的回報，就無法維持可持續(xù)的經(jīng)營.在這種情況下，現(xiàn)存的互聯(lián)網(wǎng)商業(yè)規(guī)則可能無法為域間互連網(wǎng)絡(luò)中價值鏈(主要包括網(wǎng)絡(luò)應(yīng)用提供商和網(wǎng)絡(luò)服務(wù)提供商等)的所有參與者提供一個可持續(xù)發(fā)展的經(jīng)濟(jì)效益.事實上，現(xiàn)存的對等協(xié)議規(guī)則并不知道全部域的QoS性能，而且多數(shù)是以流量對稱為前提，這使不斷發(fā)展和高質(zhì)量要求的服務(wù)不能得到滿足.此外，對于絕大多數(shù)互聯(lián)網(wǎng)連接來說，最常見的定價方式是月費率(即按月定價付費)，而其他的參與者如應(yīng)用提供商APs或頂層供應(yīng)商(over the top providers，OTTs)獲得的收益是按每消耗的帶寬為基礎(chǔ)的，這依賴于現(xiàn)有網(wǎng)絡(luò)基礎(chǔ)設(shè)施上的服務(wù)，從而造成網(wǎng)絡(luò)提供商不能獲得足夠的報酬[7].已有許多互聯(lián)網(wǎng)公司和學(xué)術(shù)機(jī)構(gòu)在積極研究和分析未來的發(fā)展趨勢，以期得到滿足端到端的需求和各種可操作的商業(yè)模式.自治系統(tǒng)(autonomous systems，ASs)聯(lián)盟或聯(lián)合體的出現(xiàn)，作為一個新興架構(gòu)為其提供服務(wù)[8].

已有文獻(xiàn)提出采用網(wǎng)絡(luò)帶寬拍賣來解決帶寬分配問題.這些研究多數(shù)是尋求投標(biāo)機(jī)制本身而忽略帶寬的有效分配.文獻(xiàn)[9]提出了一種適應(yīng)于P2P網(wǎng)絡(luò)分布式特性的帶寬拍賣分配機(jī)制.該機(jī)制通過上載帶寬支付方式，迫使自私請求節(jié)點選擇合適的帶寬需求，使得整個P2P網(wǎng)絡(luò)中的節(jié)點良性競爭帶寬資源，避免了“公共地悲劇”發(fā)生，且?guī)挿峙渌惴ㄔ谫Y源節(jié)點和請求節(jié)點并行執(zhí)行.文獻(xiàn)[10-13]基于Vickrey-Clark-Groves(VCG)機(jī)制提出了在多輪喊價中挑選出第一和第二最高喊價，然后依次淘汰，最終確定出最高喊價的方法.這些競價機(jī)制一方面僅集中在喊價高低，目標(biāo)是利益最大化，而忽視網(wǎng)絡(luò)服務(wù)質(zhì)量；另一方面，這些機(jī)制多數(shù)需要集中式計算，其中有些還假設(shè)特定的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，或假設(shè)買方知道網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu).文獻(xiàn)[14]提出了采用第一價格拍賣.在這種拍賣中，盡管目標(biāo)也是尋求收益最大化，但其實現(xiàn)的復(fù)雜性要遠(yuǎn)低于第二價格和多輪競價拍賣機(jī)制.

針對以上方法的不足，本文在文獻(xiàn)[14]第一價格拍賣機(jī)制的基礎(chǔ)上，一方面，考慮多域聯(lián)合情形而不是單域情形，即ASs以一種合作的方式協(xié)同工作來出售端到端質(zhì)量確保的比特管道.比特管道不一定要出售給最終用戶，而是出售給中間參與者如代理商或OTTs，中間參與者將通過質(zhì)量保證路徑把比特管道轉(zhuǎn)售給最終用戶，不但使得端到端的質(zhì)量參數(shù)得到保證，而且還能使整個聯(lián)盟的收益最大化.另一方面，在考慮端到端的QoS約束和容量約束條件下，提出了一種基于Shapley值的收益分享激勵機(jī)制，激勵聯(lián)盟中的ASs出售更多優(yōu)質(zhì)的服務(wù)，從而增加整個聯(lián)盟收益和其自身的收益分享.仿真結(jié)果表明，本文提出的多域聯(lián)合情形下的帶寬分配算法和基于Shapley值的收益分享激勵機(jī)制，不但能夠?qū)崿F(xiàn)端到端QoS約束下的帶寬優(yōu)化分配，而且能實現(xiàn)整個多域聯(lián)盟的總收益最大化，并激勵各個AS提供更多優(yōu)質(zhì)服務(wù)而獲得更多收益分享.

1 基于帶寬優(yōu)化分配的收益最大化

考慮幾個ASs協(xié)同工作，以一個多域質(zhì)量保證路徑來出售容量(比特流)，稱這種質(zhì)量保證路徑為QoS管道或路徑.在這種情況下，每個AS按此方法出售的專用容量是其已部署容量的一部分，也就是說，每個AS有其自身的基礎(chǔ)設(shè)施，可以決定將它們的多大容量提供給聯(lián)盟.

對于每個QoS管道來說，如果有一組用戶/買家愿意獲得管道上的一部分帶寬，把該組用戶/買家愿意為每個數(shù)量的帶寬支付的金額總數(shù)稱為效用函數(shù).本文目標(biāo)就是在實現(xiàn)端到端QoS約束條件下，使整個聯(lián)盟的收益最大化.一般而言，這種情況下的端到端QoS約束條件就是端到端的延遲約束(即端到端的最大可容許延遲).為了定量化描述這種情況，把聯(lián)盟中的每個AS用n來表示，等效容量為cn，全部節(jié)點集用N來表示，可用的管道是集合S中的管道，表示為s，對路徑s上的延遲約束用Ds來表示.假設(shè)聯(lián)盟內(nèi)的路由固定且為單路徑，把這些路由表示為N×S大小的矩陣R，其中，符號·表示集合的基數(shù)，如果管道j*的路由穿過節(jié)點i*，則Ri*，j*等于1，否則為0，用r(s)表示管道s的路由.分配給管道s的帶寬(即出售給與管道s相關(guān)聯(lián)的買家的流量數(shù)量)表示為as，與每個管道s相關(guān)聯(lián)的效用函數(shù)表示為Us(as)，通常情況下，Us(as)是帶寬的一個嚴(yán)格的凹函數(shù).

QoS管道是由入口和出口點以及最大延遲來確定的，這意味著2個QoS管道被視為是不同的，盡管2個管道完全共享相同的物理路徑，但具有不同的延遲界限.

出售給全部路徑的流量(即帶寬)數(shù)量必須滿足由聯(lián)盟預(yù)計的收益是最大化的，同時還要滿足QoS約束條件，故該問題可表示為帶寬分配問題.

問題1：

(1)

(2)

式中，λ={λs}s∈S為拉格朗日乘子向量.

(3)

(4)

式中：[·]+=max{0，·}；γs和αs為步長大小.

更新式(3)、(4)是在一個管道(也把這個管道稱為源)的每個邊緣路由器上迭代執(zhí)行.每個源通過路由r(s)發(fā)送一個λs和as的初始值，每個節(jié)點接收到全部值并計算延遲和延遲的導(dǎo)數(shù)乘上它所接收到的λs的總和，并發(fā)送給源，全部這些值用2個和累加并返回到源.因此，在每次迭代中只需要把2個值發(fā)送并返回到源，一旦源接收到這些值，就對λs和as的值進(jìn)行更新.

1.1 多域網(wǎng)絡(luò)帶寬拍賣

將本文算法應(yīng)用于多域帶寬拍賣模型，把每個管道與出售的服務(wù)關(guān)聯(lián)起來，這些服務(wù)有確定的帶寬σs和延遲Ds，通過同一管道的網(wǎng)絡(luò)帶寬拍賣出售.本文采用第一價格拍賣機(jī)制，即獲勝用戶獲得投標(biāo)的數(shù)量.

(5)

在第一價格拍賣機(jī)制下，尋找到使得這些投標(biāo)可以接受的資源分配判決，以使整個聯(lián)盟的收益最大化，同時使每個路由的延遲小于給定的延遲約束值.對于每個服務(wù)s來說，全部投標(biāo)都是針對相同的帶寬和延遲約束，故最優(yōu)解就是每個服務(wù)可接受的最高出價.定義一個變量ψs，k，如果對服務(wù)s的第k個投標(biāo)被接受，則ψs，k等于1，否則為0；定義一個變量ms為對于服務(wù)s可接受的出價數(shù)量，可得

(6)

可接受的ms個投標(biāo)將得到一個總的接受率，即帶寬as，且as=σsms.因此，每個服務(wù)的效用就可以定義為

(7)

式(7)為as的離散值，本文通過線性插值將其擴(kuò)展為as的一個分段線性凹函數(shù)，則最優(yōu)化問題可表示為問題2：

(8)

可知問題2與問題1唯一的差別在于加入了一個整數(shù)約束.一方面，本文采用求解問題1最優(yōu)解的方法和過程來求解實例模型的問題2；另一方面，由于整數(shù)規(guī)劃是NP-hard的，因此，采用凸松弛以及舍入來滿足這個整數(shù)約束，可以通過在兩個連續(xù)的整數(shù)值之間得到一個跳變結(jié)果來使效用函數(shù)非嚴(yán)格的凹特性妥協(xié)于算法的收斂性.為了避免震蕩，還可以采用近點優(yōu)化法來得到一個嚴(yán)格的凹函數(shù)作為目標(biāo)，而不改變所要得到的解的點.為了出售服務(wù)，以周期性的方式重復(fù)上述過程，在每個周期時間T內(nèi)收集全部投標(biāo)并分配帶寬，得到滿足整數(shù)約束的問題2的最優(yōu)解即為最大化收益.

1.2 拍賣實例性能仿真

圖1為算法應(yīng)用實例的性能仿真結(jié)果.圖1a為拓?fù)浣Y(jié)構(gòu)，本文在網(wǎng)絡(luò)仿真平臺J-Sim環(huán)境中進(jìn)行仿真，J-Sim網(wǎng)絡(luò)仿真環(huán)境可以很容易地建立網(wǎng)絡(luò)拓?fù)?、?jié)點結(jié)構(gòu)和通訊行為，從而實現(xiàn)網(wǎng)絡(luò)仿真，達(dá)到評價網(wǎng)絡(luò)算法的目的.拓?fù)浣Y(jié)構(gòu)中有4個AS聯(lián)合提供2個服務(wù)，對于2個服務(wù)來說，有12個買家給出喊價；每個AS的等效容量(帶寬)為40，服務(wù)1的延遲界限(即延遲約束)D1=2.8，服務(wù)2的延遲界限D(zhuǎn)2=0.25，2個服務(wù)提供的帶寬數(shù)量均為80.圖1b為對于每個服務(wù)仿真所得到的效用函數(shù).延遲約束小的(D2=0.25，意味著QoS性能更好)服務(wù)2獲得了更高的喊價，說明在這種端到端QoS約束條件下，本文提出的多域網(wǎng)絡(luò)帶寬拍賣模型在保證更好QoS性能的優(yōu)化帶寬分配下還能獲得較高的拍賣價格，說明本文提出的算法是可行和有效的.圖1c為仿真得到的2個服務(wù)對于算法收斂所需要的迭代過程中帶寬as的變化情況.獲得更多收益的服務(wù)2可以得到更多的可接受帶寬.圖1d為仿真得到的每個服務(wù)所預(yù)計的收益變化情況.具有較好端到端QoS約束條件(D2=0.25)下的帶寬分配服務(wù)2的預(yù)期收益要遠(yuǎn)遠(yuǎn)高于較差端到端QoS約束條件(D1=2.8)下的帶寬分配服務(wù)1的預(yù)期收益.

2 基于Shapley值激勵的收益分享

對于互聯(lián)網(wǎng)服務(wù)來說，傳統(tǒng)的對等支付可能并不適合這類有質(zhì)量保證的服務(wù)，因此，基于某種公平原則來實現(xiàn)收益分享變得十分重要.在理想情況下，每個AS的預(yù)計收益應(yīng)當(dāng)與其提供給聯(lián)盟的利潤成正比，而那些提供端到端QoS性能下降或出現(xiàn)瓶頸的AS，或在某種程度上限制其收益，或鼓勵增加提供給聯(lián)盟的資源.

2.1 Shapley值

Shapley值是由LloydShapley在1952年提出，該方法能夠?qū)崿F(xiàn)一個聯(lián)合體或聯(lián)盟的收益分享，因其良好的性能而被廣泛應(yīng)用于各種研究中.

一個具有可轉(zhuǎn)移效用的聯(lián)盟博弈可表示為(M，v)，其中，M是玩家(成員)的一個有限集合，v∈2M→R為與每個聯(lián)盟Q?M相關(guān)的價值函數(shù)，即成員可以在聯(lián)盟之間分配到一個有真正價值的報酬v(Q).

給定一個博弈G=(M，v)，稱x={xi}(?i∈M)為報酬向量，xi代表玩家i∈M所得到的大聯(lián)盟M的報酬份額.一個預(yù)歸集是報酬向量的集合，滿足全部xi的總和等于v(M).一個虛擬玩家對聯(lián)盟的貢獻(xiàn)與其想獲得的報酬是相同的，采用這些定義，引入對稱性(即對任意的v，如果i和j對任意聯(lián)盟的貢獻(xiàn)相同，則xi=xj)、虛擬玩家(即對任意的v，如果i是一個虛擬玩家，則xi=v({i}))和可加性的概念，則Shapley值的定義如下所示.

圖1 算法應(yīng)用實例的性能仿真結(jié)果Fig.1 Performance simulation results foralgorithm application examples

定義1Shapley值.給定一個聯(lián)盟博弈(M，v)，存在一個唯一的預(yù)歸集φ(M，v)滿足對稱性、虛擬玩家和可加性，就把它稱為Shapley值.對于玩家i來說，φ(M，v)可定義為

[v(Q∪{i})-v(Q)]

(9)

2.2 收益分享

為了分享收益，設(shè)博弈中的玩家是聯(lián)盟中N個AS的集合，假設(shè)對于每個服務(wù)來說，投標(biāo)各自服從連續(xù)概率分布，把發(fā)生在一定時間內(nèi)拍賣的效用函數(shù)用該時間內(nèi)全部效用的平均值來表示，即

(10)

一般情況下，式(10)是as的一個嚴(yán)格的凹函數(shù).假設(shè)每個AS的延遲函數(shù)在考慮的時間段內(nèi)保持不變，則對于每個子聯(lián)盟Q?N來說，價值函數(shù)v就可以作為問題3的解.

問題3：

(11)

式中，SQ為由Q能夠提供的服務(wù)的集合.一旦聯(lián)盟收集到全部收益，在帶寬分配階段，收益就在全部AS之間按Shapley值的比例進(jìn)行分享.

定理2提高容量的激勵機(jī)制.令(N，v，c)為一個聯(lián)盟博弈，N個節(jié)點集代表博弈者，c表示N中全部節(jié)點的等效容量，v是由問題3定義的價值函數(shù).如果增加節(jié)點i的容量，i∈N，則分享系數(shù)φi將不會減少.令c*為當(dāng)i的容量增加時全部節(jié)點的容量，則φi(N，v，c*)≥φi(N，v，c)，φi(N，v，c)給定博弈(N，v)和容量c中節(jié)點i的Shapley值.

根據(jù)Shapley值的定義，則有

v(Q，c*)]

(12)

式中：K為常數(shù)；v(Q，c*)為當(dāng)容量給定為c*時子聯(lián)盟Q的價值函數(shù).由于除i外(不考慮i的容量)任何聯(lián)盟的價值函數(shù)是相同的，通過減去i的分享系數(shù)，則有

v(Q∪{i}，c)]

(13)

事實上，v是問題3的解，是具有凸約束條件的凹函數(shù)的最大化值.通過增加容量，就會得到更大的或相等的解.

定理2表明，如果節(jié)點i增加其容量，則分享系數(shù)就會增加或保持不變，在所考慮的時間段內(nèi)，聯(lián)盟所預(yù)計的總收益也不會減少.因此，如果節(jié)點i的容量增加，那么聯(lián)盟可以分配更多的帶寬(使收益增加)，或者可以分配相同數(shù)量的帶寬(使收益保持不變).

2.3 分享機(jī)制性能仿真

為了體現(xiàn)基于Shapley值激勵的收益分享機(jī)制的有效性，本文采用圖2a所示的拓?fù)浣Y(jié)構(gòu)，并與采用一般Shapley值的聯(lián)盟博弈算法進(jìn)行比較.3個AS的容量以及延遲函數(shù)都是相同的，買家對各個AS的出價是隨機(jī)的，故每個AS獲得的收益是不同的.圖2b為對于3個AS在本文提出的基于Shapley值激勵的收益分享機(jī)制和采用一般Shapley值的聯(lián)盟博弈算法得到的累計收益.本文提出的基于Shapley值激勵的收益分享機(jī)制對于每個AS來說，其累計收益始終要高于采用一般Shapley值的聯(lián)盟博弈算法得到的累計收益，3個AS的平均累計收益增加了約28%，說明本文提出的收益分享機(jī)制能夠激勵聯(lián)盟中各個AS增加其容量，從而不僅增加整個聯(lián)盟的累計總收益，而且各個AS的累計收益也明顯增加，說明本文提出的收益分享機(jī)制是可行且可操作的.

圖2 不同收益分享機(jī)制下的累計收益比較Fig.2 Comparison in cumulative income underdifferent income sharing mechanisms

3 結(jié) 論

本文提出了一種基于帶寬優(yōu)化分配的收益最大化算法和基于Shapley值激勵的收益分享機(jī)制，分析了具有QoS約束的網(wǎng)絡(luò)帶寬分配問題，并以基于網(wǎng)絡(luò)帶寬拍賣應(yīng)用為實例，將聯(lián)盟博弈理論和Shapley值用于聯(lián)盟收益分享，既能使整個聯(lián)盟收益最大化，又能增加整個聯(lián)盟的收益和其自身的收益分享.

參考文獻(xiàn)(References)：

[1] Trestian R，Ormond O，Muntean G M.Performance evaluation of MADM-based methods for network selection in a multimedia wireless environment [J].Wireless Networks，2015，21(5)：1-19.

[2]蒲斌，崔夢天，趙海軍.基于二階段的3D虛擬世界客戶分配方法 [J].計算機(jī)工程，2016，42(1)：109-115.

(PU Bin，CUI Meng-tian，ZHAO Hai-jun.Client allocation approach in 3D virtual world based on two-stage [J].Computer Engineering，2016，42(1)：109-115.)

[3] 王晗，吳心筱，賈云得.使用異構(gòu)互聯(lián)網(wǎng)圖像組的視頻標(biāo)注 [J].計算機(jī)學(xué)報，2013，36(10)：2062-2069.

(WANG Han，WU Xin-xiao，JIA Yun-de.Video annotation by using heterogeneous multiple image groups on the web [J].Chinese Journal of Computer，2013，36(10)：2062-2069.)

[4] Douville R，Pouyllau H，Lonsethagen H.ETICS：QoS-enabled interconnection for future internet services [J].Frontiers in Psychology，2013，5(7)：640.

[5] 段華瓊，唐賓徽.基于線性多尺度模型的計算機(jī)網(wǎng)絡(luò)數(shù)據(jù)流量預(yù)測 [J].沈陽工業(yè)大學(xué)學(xué)報，2017，39(3)：322-327.

(DUAN Hua-qiong，TANG Bin-hui.Prediction of data flow in computer network based on linear multi-scale model [J].Journal of Shenyang University of Technology，2017，39(3)：322-327.)

[6] 王思秀，郭文強(qiáng)，于凱，等.異構(gòu)網(wǎng)絡(luò)中支持終端直通的聯(lián)合模式資源復(fù)用算法 [J].沈陽工業(yè)大學(xué)學(xué)報，2017，39(4)：422-427.

(WANG Si-xiu，GUO Wen-qiang，YU Kai，et al.A resource reuse algorithm for device-to-device communication based on combination mode in heterogeneous networks [J].Journal of Shenyang University of Technology，2017，39(4)：422-427.)

[7] Ma R T B，Chiu D M，Lui J C S，et al.Internet economics：the use of shapley value for ISP settlement [J].IEEE/ACM Transactions on Networking，2010，18(3)：775-787.

[8] Courcoubetis C，Dramitinos M，Stamoulis G D，et al.Inter-carrier interconnection services：QoS，economics and business issues [J].Computers & Communications，2011，34(17)：779-784.

[9] 張云鶴，朱艷琴，紀(jì)其進(jìn).基于拍賣的 P2P 內(nèi)容分發(fā)網(wǎng)絡(luò)帶寬分配機(jī)制 [J].通信學(xué)報，2013，34(4)：99-105.

(ZHANG Yun-he，ZHU Yan-qin，JI Qi-jin.Auction based bandwidth allocation mechanism for P2P content distribution networks [J].Journal on Communications，2013，34(4)：99-105.)

[10]劉志新，申妍燕，關(guān)新平.一種基于VCG拍賣的分布式網(wǎng)絡(luò)資源分配機(jī)制 [J].電子學(xué)報，2010，38(8)：1929-1934.

(LIU Zhi-xin，SHEN Yan-yan，GUAN Xin-ping.A VCG-auction based distributed mechanism for network resource allocation [J].Acta Electronica Sinica，2010，38(8)：1929-1934.)

[11]Vohra R V.Combinatorial auctions [J].Handbook of Game Theory with Economic Applications，2015，4(1)：455-476.

[12]Shin K，Jung J Y，Lee J R.Resource allocation and pricing mechanisms for wireless multimedia service：auction and bargaining models [J].Journal of Internet Technology，2013，14(7)：1093-1103.

[13]Canzian L，Xiao Y，Zorzi M，et al.Game theoretic design of MAC protocols：pricing and intervention in slotted-Aloha [J].IEEE Transactions on Communication，2013，63(11)：4287-4303.

[14]Belzarena P，Paganini F，F(xiàn)erragut A.Optimizing revenue for bandwidth auctions over networks with time reservations [J].Computer Networks，2011，55(9)：2289-2302.