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

蔡媛媛，曹自平，張金婭

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

1 概 述

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

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

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

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

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

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

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

2 模型構(gòu)建

2.1 囚徒困境模型

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

2.2 激勵制度

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

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

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

(1)

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

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

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

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

(2)

(3)

(4)

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

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

(5)

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

3 實(shí)驗(yàn)仿真

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

圖1 控制開銷對比曲線

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

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

圖2 傳輸效率對比曲線

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

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

4 結(jié)束語

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

參考文獻(xiàn)：

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

[2] 劉期烈,劉茂松,李 云.基于博弈論的機(jī)會網(wǎng)絡(luò)激勵機(jī)制的研究[J].計算機(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é)點(diǎn)自私性研究[D].濟(jì)南:山東大學(xué),2012.

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

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

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