基于博弈論的ALM協(xié)議改進算法

蔡媛媛，曹自平，張金婭

(南京郵電大學(xué) 通信與信息工程學(xué)院，江蘇 南京 210003)

1 概 述

目前的傳統(tǒng)網(wǎng)絡(luò)配置技術(shù)已經(jīng)受到來自軟件定義網(wǎng)絡(luò)的沖擊，只有不斷地突破自我才是一項技術(shù)可以長久存在的根本。傳統(tǒng)ALM協(xié)議(NICE和CPBM)在網(wǎng)絡(luò)拓撲的構(gòu)建上進行了較為深入的研究[1]，但在用戶自私性方面存在著諸多空缺,就其數(shù)據(jù)傳輸過程的考量是相對比較薄弱的，因此文中主要針對網(wǎng)絡(luò)拓撲構(gòu)建下的數(shù)據(jù)傳輸過程進行考量，綜合考率了多方面因素，引入博弈論的思想以及改進傳統(tǒng)ALM協(xié)議算法，目的則在于通過市場的激勵機制來控制用戶的自私性行為。

博弈論提供了當利益代表者之間發(fā)生利益沖突時可能出現(xiàn)的行為選擇，是一組有助于解決交互決策問題的建模工具[2]。其三大要素包括：參與者、行為策略以及收益[3]。在ALM中參與者是指加入到組播樹中的節(jié)點主機[4]，其目的是為了獲取資源，而資源轉(zhuǎn)發(fā)則是為其他主機服務(wù)，因而出現(xiàn)了主機在追求自身收益最大化時與因整體收益而不得不讓渡自身收益的矛盾。行為策略，是參與者出于理性而做出的應(yīng)對策略。節(jié)點主機在面對最大化自身收益時，常因為協(xié)議漏洞或非法行為而使自身策略獲得額外收益，即用戶自私性行為[5]。當組播樹中有部分節(jié)點采用自私行為時，不僅會影響到其他正常節(jié)點主機的收益，還可能引起整個組播樹的振蕩，明顯降低組播樹的傳輸效率。因此制定一種合理的組播協(xié)議，規(guī)范組播節(jié)點行為是十分必要的。收益，是指行為策略對應(yīng)的結(jié)果。節(jié)點主機的收益是指合理獲取數(shù)據(jù)，并盡可能合理地使節(jié)點自愿將自身性能貢獻出來，從而達到整體收益的最大化。

在ALM中當主機節(jié)點進行行為決策時，其目的非常明確—最大限度地滿足自身收益的最大化，但是這種自私行為破壞了網(wǎng)絡(luò)的全局利益。在ALM中，目前采用的博弈論思想的主要應(yīng)用場景有以下兩種：

數(shù)據(jù)收集階段：主機節(jié)點為了在形成虛鏈路時在組播樹中獲得更優(yōu)勢的地位，會采用諸如距離欺騙、吞吐量欺騙、中繼代價欺騙等欺騙行為[6]。而激勵機制的出現(xiàn)則是為了克服主機節(jié)點進行吞吐量欺騙行為而采用的方法。

在ALM模型當中，存在自私節(jié)點通過吞吐量欺騙的方式，既占據(jù)了近源節(jié)點的有利位置，又有效減少了轉(zhuǎn)發(fā)數(shù)據(jù)所帶來的自身資源消耗。有實驗結(jié)果表明，當主機節(jié)點之間的合作率低于30%時，整個組播樹的會話質(zhì)量會變得相當差，組播之間的會話近乎不可用[7]。Habib等針對主機節(jié)點吞吐量欺騙的行為，采用一種基于分區(qū)服務(wù)的鼓勵用戶貢獻轉(zhuǎn)發(fā)的資源激勵機制[8]，有研究表明在引入該機制后，ALM會話的總體性能有明顯提升，然而該種激勵機制存在的弊病是當主機節(jié)點得到了自身傳輸所需的服務(wù)質(zhì)量后便沒有任何理由再驅(qū)使其進行轉(zhuǎn)發(fā)行為，因而存在明顯的局限性。Yuen等根據(jù)博弈論中的VCG機制，提出了一種基于補償?shù)募钪贫萚9]，較為有效地解決了主機節(jié)點的吞吐量欺騙問題。

數(shù)據(jù)結(jié)構(gòu)構(gòu)造階段：在此階段，就網(wǎng)狀結(jié)構(gòu)而言，節(jié)點會選用其相鄰的節(jié)點作為數(shù)據(jù)請求的目標；就樹狀結(jié)構(gòu)而言，節(jié)點會向其父節(jié)點發(fā)送數(shù)據(jù)請求的報文，此時收到數(shù)據(jù)請求報文的主機節(jié)點則會發(fā)送相應(yīng)報文給請求節(jié)點，如果此時存在著激勵機制，那么被請求節(jié)點則可以獲得相應(yīng)的轉(zhuǎn)發(fā)收益。Tan等在激勵機制的基礎(chǔ)上，利用每一個主機節(jié)點通過轉(zhuǎn)發(fā)數(shù)據(jù)和請求數(shù)據(jù)所獲得的總收益，并引入了市場機制[10]。

研究表明，在激勵機制的基礎(chǔ)上引入市場機制以后，可以明顯促進主機節(jié)點之間的良性競爭。

2 模型構(gòu)建

2.1 囚徒困境模型

囚徒困境是博弈論中著名的數(shù)學(xué)模型：兩個囚徒為了追求各自利益最大化而兩敗俱傷。囚徒困境實際上是個人利益和集體利益的矛盾體現(xiàn)，每一個體利益最大的總和并不代表著集體利益的最有效分配，在ALM中每一個參與傳輸?shù)墓?jié)點都是一個獨立個體，在其做出利己行為時，對于個體而言是理智行為，但對于全局拓撲來講并不是最優(yōu)結(jié)果。事實上，在實際拓撲中如果有用戶產(chǎn)生自私行為，所造成的影響是十分惡劣的。有數(shù)據(jù)表明，在部分節(jié)點進行了自私行為之后組播樹中有50%的虛鏈路發(fā)生了變化，嚴重影響了組播樹的穩(wěn)定。

2.2 激勵制度

在節(jié)點信息收集階段自私節(jié)點會通報給中心節(jié)點虛假信息，以提高自己在組播樹中的有利位置，如距離欺騙，即在自私節(jié)點向Leader節(jié)點發(fā)送自身參數(shù)時，一般是跳數(shù)(Hop)，修改自身與Leader節(jié)點之間的Hop為0，而與其子節(jié)點發(fā)送參數(shù)時，在延時參數(shù)加上一個隨機數(shù)，降低自身作為父節(jié)點的可能性，從而在組播樹中最大化地接收資源并最小化地作為中繼節(jié)點傳輸資源。Mathy等通過模擬實驗得知，存在大量距離欺騙的組播樹的穩(wěn)定性遠小于只存在少量距離欺騙的組播樹[11]。Li等的后續(xù)實驗進一步表明，在某些情況下存在距離欺騙的組播樹，會使得整個拓撲中50%以上的虛鏈路發(fā)生變化[12]。

自私用戶進行距離欺騙是為了在組播樹中得到更有利的位置，即更快更好地接收資源的同時利用更少的自身資源進行他人數(shù)據(jù)的轉(zhuǎn)發(fā)。可利用大多情況下閑置的個人計算機，當節(jié)點每轉(zhuǎn)發(fā)一次數(shù)據(jù)時，會得到相應(yīng)的獎勵，獎勵會在Leader節(jié)點處保留，當此節(jié)點加入到組播樹中時，由于之前的優(yōu)良記錄，將會得到一個有利的位置。相反，如果此節(jié)點存在著不良記錄，如距離欺騙等行為，其可信性將會在Leader節(jié)點處受到質(zhì)疑，即使其自身擁有優(yōu)良的參數(shù)，也很難得到一個有利位置。

在此給出激勵制度的選擇依據(jù)，按照多勞多得的原則，一個節(jié)點i的貢獻值(Contri)由兩部分組成：一是自身轉(zhuǎn)發(fā)的積累值(Fori)，二是自身請求其他節(jié)點進行數(shù)據(jù)轉(zhuǎn)發(fā)的支付值(Payi)，與節(jié)點i所處的域的半徑為Dij，則節(jié)點i的貢獻為：

(1)

Leader節(jié)點將會根據(jù)Contri判斷節(jié)點i的行為表現(xiàn)，Contri越高說明節(jié)點的貢獻越多。當此節(jié)點進行資源請求時，Leader節(jié)點將優(yōu)先向其傳輸，同時兄弟節(jié)點也會優(yōu)先向其進行資源交換。當其他節(jié)點進行資源請求時，也會優(yōu)先選擇貢獻值高的節(jié)點進行資源接受[13]。

引入激勵機制后，節(jié)點之間的數(shù)據(jù)傳輸已然變成了有償服務(wù)，通過進一步借鑒貨幣在市場中的作用，引入貨幣機制。在方才定義的任意節(jié)點i的Contri只是就單個節(jié)點的轉(zhuǎn)發(fā)數(shù)據(jù)和獲取資源而言，將市場思維引入之后，每一個節(jié)點在索取資源時，可以充分利用自身已有的貢獻值，將自己的貢獻值作為價碼出售給擁有資源的節(jié)點，此時資源擁有者可以根據(jù)自身情況選擇一個最合適的節(jié)點進行傳輸。

2.3 動態(tài)傳輸協(xié)議

文中選用六個參數(shù)來進行資源節(jié)點的選擇。第一個參數(shù)是帶寬，即發(fā)出資源請求的節(jié)點到達目的節(jié)點直接所經(jīng)過的路由器中帶塊最小的值。第二個參數(shù)是時延，即在整個傳輸路徑上經(jīng)過所有路由器的時延的總和。第三個參數(shù)是節(jié)點資源擁有量，即擁有資源節(jié)點所擁有請求者所需資源的數(shù)量。資源擁有的多可能是因為在整個拓撲當中停留的時間長，或者其節(jié)點傳輸速度較快，二者皆是理想的資源節(jié)點的屬性[14]。第四個參數(shù)是節(jié)點存在時間，即資源節(jié)點在整個拓撲中存在的時長。一般認為在此環(huán)境中停留時間越長的節(jié)點在接下來的時間內(nèi)退出的可能性越小，其穩(wěn)定性就會越高。第五個參數(shù)為跳數(shù)，如果主機之間經(jīng)過路由器跳數(shù)越少，可以粗略認為這條鏈路上的時延越短，網(wǎng)絡(luò)抖動越小，丟包率越低。第六個參數(shù)為貢獻值。

(2)

(3)

(4)

在這里定義概念活性(Activetrans)，考慮資源(Src)與時間(Time)作為參考度量，且用其比值的形式出現(xiàn)，Activetrans越大，節(jié)點的活性越高，同時穩(wěn)定性也越強。如果一個節(jié)點的資源占比越高，其被選為候選資源節(jié)點的可能性應(yīng)當是提升的，但是也確定此節(jié)點擁有資源皆為本次傳輸所得，于是還考慮將此節(jié)點所在整個拓撲中的時間作為參考對象，以其處在的時間與整個拓撲所存在時間的比值為表現(xiàn)形式。式中的0<α,β<1，作為參數(shù)權(quán)重出現(xiàn)，也保可證Activetrans是一個真分數(shù)。只有在資源和時間的比重達到最優(yōu)時，才可能選出最穩(wěn)定且活性最高的節(jié)點進行資源傳輸。

當s節(jié)點或者Leader節(jié)點收到下級節(jié)點發(fā)來的數(shù)據(jù)請求之后，會將相似的數(shù)據(jù)請求分類并編號，隨后將同一類資源分段傳輸?shù)讲煌恼埱蠊?jié)點。數(shù)據(jù)分段的依據(jù)是以Costtrans公式為基礎(chǔ)的，開銷越小的節(jié)點會獲得越多越大的資源分段。

(5)

當同層中Leader節(jié)點之間形成鄰居關(guān)系時，如果計算得到的Costtrans值比Leader節(jié)點與s節(jié)點之間的Costtrans小，則使用這條路徑進行資源傳輸，如果沒有，則將這條路徑放入備用的資源路徑數(shù)據(jù)庫，以便在下次通信時可快速地形成鄰接關(guān)系，也起到了鏈路備份的作用。同層的Member節(jié)點之間的數(shù)據(jù)請求與傳輸也是類似的。

3 實驗仿真

采用Myns進行仿真[15]，與文中提出的T-M模型進行對比的模型為NICE，通過對控制開銷、平均數(shù)據(jù)傳輸率、協(xié)議穩(wěn)定性這三個定向指標的仿真模擬，實驗中的節(jié)點數(shù)從100開始，并且以線性方式增長。旨在觀察在網(wǎng)絡(luò)拓撲變復(fù)雜，組成員變多的情況下兩種協(xié)議之間的優(yōu)劣。

圖1 控制開銷對比曲線

圖1表明T-M算法的控制開銷高于NICE算法，這是因為T-M算法加入了報文分割和節(jié)點資源列表。在資源請求時，請求節(jié)點會與周圍的節(jié)點進行資源占比、節(jié)點活躍度等參數(shù)的交互，選取它認為最安全的節(jié)點進行數(shù)據(jù)請求，這樣雖然增加了節(jié)點控制開銷，但提升了節(jié)點間資源傳輸?shù)姆€(wěn)定性；在節(jié)點請求數(shù)據(jù)時，將請求資源分段分別發(fā)送給基于本片段資源的最優(yōu)節(jié)點，以提高資源傳輸成功率。

圖2清楚地顯示出T-M協(xié)議的傳出效率高于NICE協(xié)議。因為隨著拓撲中節(jié)點數(shù)的不斷增加，T-M協(xié)議因采用的是樹網(wǎng)混合型結(jié)構(gòu)的拓撲模型，每個節(jié)點所需維護的節(jié)點關(guān)系較少，同時由于此協(xié)議在數(shù)據(jù)傳輸時采用了動態(tài)分布式傳輸方式，就同一個資源而言，每個授信節(jié)點只需傳輸其中的一部分，同時這些授信節(jié)點的可靠性是相對較高的，因此其傳輸成功率與效率會明顯提高。

圖2 傳輸效率對比曲線

圖3顯示T-M協(xié)議的穩(wěn)定性高于NICE協(xié)議，因為T-M協(xié)議采用的分布式傳輸方式在其中一個節(jié)點失效后，會有后備節(jié)點接替，且在選取資源節(jié)點時采用了較為復(fù)雜但更為有效和穩(wěn)定的選取規(guī)則，保證了資源節(jié)點的穩(wěn)定性，也提高了協(xié)議的穩(wěn)定性。

圖3 協(xié)議穩(wěn)定性對比曲線

4 結(jié)束語

該協(xié)議針對傳統(tǒng)的ALM協(xié)議進行改進，傳統(tǒng)的ALM協(xié)議，如NICE、CPBM，在數(shù)據(jù)傳輸過程中主要以跳數(shù)(Hop)為單一參考，然而由于網(wǎng)絡(luò)結(jié)構(gòu)的異構(gòu)性，各個數(shù)據(jù)鏈路之間的帶寬、延時等差異較大，因此通過綜合考量節(jié)點貢獻值、跳數(shù)、帶寬、延時等，將博弈原理加入到組播算法當中。雖然此算法在控制開銷方面相比CPBM、NICE協(xié)議要大，但是在傳輸效率和穩(wěn)定性方面有所提升，在目前終端處理能力大幅度提升的情況下，提高數(shù)據(jù)的傳輸準確率，才是更為緊要的課題[16]。

參考文獻：

[1] 葉保留,李春洪,姚 鍵,等.應(yīng)用層組播研究進展[J].計算機科學(xué),2005,32(6):6-10.

[2] 劉期烈,劉茂松,李 云.基于博弈論的機會網(wǎng)絡(luò)激勵機制的研究[J].計算機應(yīng)用研究,2015,32(7):2128-2132.

[3] FELDMAN M, PAPADIMITRIOU C, CHUANG J,et al.Free-riding and whitewashing in peer-to-peer systems[C]//ACM SIGCOMM workshop on practice and theory of incentives in networked systems.[s.l.]:ACM,2004:228-236.

[4] BURAGOHAIN C,AGRAWAL D,SURI S.A game theoretic framework for incentives in P2P systems[C]//Proceedings of the third international conference on peer-to-peer computing.[s.l.]:IEEE,2003:48-56.

[5] LIU Zhengye, SHEN Yanming, ROSS K W,et al.Layer P2P:using layered video chunks in P2P live streaming[J].IEEE Transactions on Multimedia,2009,11(7):1340-1352.

[6] MA R T B,LEE S C M,LUI J C S,et al.Incentive and service differentiation in P2P networks:a game theoretic approach[J].IEEE/ACM Transactions on Networking,2006,14(5):978-991.

[7] BASAR T,SRIKANT R.Revenue-maximizing pricing and capacity expansion in a many-users regime[C]//Joint conference of the IEEE computer and communications societies.New York,NY,USA:IEEE,2002.

[8] SENTINELLI A,MARFIA G,GERLA M,et al.Will IPTV ride the peer-to-peer stream? [peer-to-peer multimedia streaming][J].IEEE Communications Magazine,2007,45(6):86-92.

[9] HABIB A,CHUANG J.Service differentiated peer selection:an incentive mechanism for peer-to-peer media streaming[J].IEEE Transactions on Multimedia,2006,8(3):610-621.

[10] TAN G,JARVIS S A.A payment-based incentive and service differentiation mechanism for peer-to-peer streaming broadcast[C]//IEEE international workshop on quality of service.New Haven,CT,USA:IEEE,2006:41-50.

[11] MA R T B,LEE S C M,LUI J C S,et al.An incentive mechanism for P2P networks[C]//International conference on distributed computing systems.[s.l.]:IEEE,2004:516-523.

[12] 衛(wèi)萌菡.基于博弈論的無線多媒體網(wǎng)絡(luò)協(xié)作資源管理研究[D].成都:西南交通大學(xué),2007.

[13] 姚 霖.基于博弈論的對等網(wǎng)絡(luò)節(jié)點自私性研究[D].濟南:山東大學(xué),2012.

[14] 許建真,馬彩玲,謝川川.基于節(jié)點綜合性能的總線型應(yīng)用層組播模型[J].計算機應(yīng)用,2009,29(11):2884-2886.

[15] 徐 超,張祖平.應(yīng)用層組播協(xié)議仿真研究[J].計算機工程與應(yīng)用,2006,42(1):112-114.

[16] 蘇金樹,曹繼軍,張博鋒.應(yīng)用層組播穩(wěn)定性提高技術(shù)綜述[J].計算機學(xué)報,2009,32(3):576-590.