基于博弈論的ALM協議改進算法

蔡媛媛，曹自平，張金婭

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

1 概 述

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

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

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

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

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

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

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

2 模型構建

2.1 囚徒困境模型

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

2.2 激勵制度

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

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

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

(1)

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

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

2.3 動態傳輸協議

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

(2)

(3)

(4)

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

當s節點或者Leader節點收到下級節點發來的數據請求之后，會將相似的數據請求分類并編號，隨后將同一類資源分段傳輸到不同的請求節點。數據分段的依據是以Costtrans公式為基礎的，開銷越小的節點會獲得越多越大的資源分段。

(5)

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

3 實驗仿真

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

圖1 控制開銷對比曲線

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

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

圖2 傳輸效率對比曲線

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

圖3 協議穩定性對比曲線

4 結束語

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

參考文獻：

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

[2] 劉期烈,劉茂松,李 云.基于博弈論的機會網絡激勵機制的研究[J].計算機應用研究,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] 衛萌菡.基于博弈論的無線多媒體網絡協作資源管理研究[D].成都:西南交通大學,2007.

[13] 姚 霖.基于博弈論的對等網絡節點自私性研究[D].濟南:山東大學,2012.

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

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

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