蔡媛媛，曹自平，張金婭

(南京郵電大學(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ā)生利益沖突時(shí)可能出現(xiàn)的行為選擇，是一組有助于解決交互決策問題的建模工具[2]。其三大要素包括：參與者、行為策略以及收益[3]。在ALM中參與者是指加入到組播樹中的節(jié)點(diǎn)主機(jī)[4]，其目的是為了獲取資源，而資源轉(zhuǎn)發(fā)則是為其他主機(jī)服務(wù)，因而出現(xiàn)了主機(jī)在追求自身收益最大化時(shí)與因整體收益而不得不讓渡自身收益的矛盾。行為策略，是參與者出于理性而做出的應(yīng)對策略。節(jié)點(diǎn)主機(jī)在面對最大化自身收益時(shí)，常因?yàn)閰f(xié)議漏洞或非法行為而使自身策略獲得額外收益，即用戶自私性行為[5]。當(dāng)組播樹中有部分節(jié)點(diǎn)采用自私行為時(shí)，不僅會影響到其他正常節(jié)點(diǎn)主機(jī)的收益，還可能引起整個(gè)組播樹的振蕩，明顯降低組播樹的傳輸效率。因此制定一種合理的組播協(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)行行為決策時(shí)，其目的非常明確—最大限度地滿足自身收益的最大化，但是這種自私行為破壞了網(wǎng)絡(luò)的全局利益。在ALM中，目前采用的博弈論思想的主要應(yīng)用場景有以下兩種：

數(shù)據(jù)收集階段：主機(jī)節(jié)點(diǎn)為了在形成虛鏈路時(shí)在組播樹中獲得更優(yōu)勢的地位，會采用諸如距離欺騙、吞吐量欺騙、中繼代價(jià)欺騙等欺騙行為[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%時(shí)，整個(gè)組播樹的會話質(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ù)請求的報(bào)文，此時(shí)收到數(shù)據(jù)請求報(bào)文的主機(jī)節(jié)點(diǎn)則會發(fā)送相應(yīng)報(bào)文給請求節(jié)點(diǎn)，如果此時(shí)存在著激勵機(jī)制，那么被請求節(jié)點(diǎn)則可以獲得相應(yīng)的轉(zhuǎn)發(fā)收益。Tan等在激勵機(jī)制的基礎(chǔ)上，利用每一個(gè)主機(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é)模型：兩個(gè)囚徒為了追求各自利益最大化而兩敗俱傷。囚徒困境實(shí)際上是個(gè)人利益和集體利益的矛盾體現(xiàn)，每一個(gè)體利益最大的總和并不代表著集體利益的最有效分配，在ALM中每一個(gè)參與傳輸?shù)墓?jié)點(diǎn)都是一個(gè)獨(dú)立個(gè)體，在其做出利己行為時(shí)，對于個(gè)體而言是理智行為，但對于全局拓?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)會通報(bào)給中心節(jié)點(diǎn)虛假信息，以提高自己在組播樹中的有利位置，如距離欺騙，即在自私節(jié)點(diǎn)向Leader節(jié)點(diǎn)發(fā)送自身參數(shù)時(shí)，一般是跳數(shù)(Hop)，修改自身與Leader節(jié)點(diǎn)之間的Hop為0，而與其子節(jié)點(diǎn)發(fā)送參數(shù)時(shí)，在延時(shí)參數(shù)加上一個(gè)隨機(jī)數(shù)，降低自身作為父節(jié)點(diǎn)的可能性，從而在組播樹中最大化地接收資源并最小化地作為中繼節(jié)點(diǎn)傳輸資源。Mathy等通過模擬實(shí)驗(yàn)得知，存在大量距離欺騙的組播樹的穩(wěn)定性遠(yuǎn)小于只存在少量距離欺騙的組播樹[11]。Li等的后續(xù)實(shí)驗(yàn)進(jìn)一步表明，在某些情況下存在距離欺騙的組播樹，會使得整個(gè)拓?fù)渲?0%以上的虛鏈路發(fā)生變化[12]。

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

在此給出激勵制度的選擇依據(jù)，按照多勞多得的原則，一個(gè)節(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)行資源請求時(shí)，Leader節(jié)點(diǎn)將優(yōu)先向其傳輸，同時(shí)兄弟節(jié)點(diǎn)也會優(yōu)先向其進(jìn)行資源交換。當(dāng)其他節(jié)點(diǎn)進(jìn)行資源請求時(shí)，也會優(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只是就單個(gè)節(jié)點(diǎn)的轉(zhuǎn)發(fā)數(shù)據(jù)和獲取資源而言，將市場思維引入之后，每一個(gè)節(jié)點(diǎn)在索取資源時(shí)，可以充分利用自身已有的貢獻(xiàn)值，將自己的貢獻(xiàn)值作為價(jià)碼出售給擁有資源的節(jié)點(diǎn)，此時(shí)資源擁有者可以根據(jù)自身情況選擇一個(gè)最合適的節(jié)點(diǎn)進(jìn)行傳輸。

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

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

(2)

(3)

(4)

在這里定義概念活性(Activetrans)，考慮資源(Src)與時(shí)間(Time)作為參考度量，且用其比值的形式出現(xiàn)，Activetrans越大，節(jié)點(diǎn)的活性越高，同時(shí)穩(wěn)定性也越強(qiáng)。如果一個(gè)節(jié)點(diǎn)的資源占比越高，其被選為候選資源節(jié)點(diǎn)的可能性應(yīng)當(dāng)是提升的，但是也確定此節(jié)點(diǎn)擁有資源皆為本次傳輸所得，于是還考慮將此節(jié)點(diǎn)所在整個(gè)拓?fù)渲械臅r(shí)間作為參考對象，以其處在的時(shí)間與整個(gè)拓?fù)渌嬖跁r(shí)間的比值為表現(xiàn)形式。式中的0<α,β<1，作為參數(shù)權(quán)重出現(xiàn)，也保可證Activetrans是一個(gè)真分?jǐn)?shù)。只有在資源和時(shí)間的比重達(dá)到最優(yōu)時(shí)，才可能選出最穩(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)系時(shí)，如果計(jì)算得到的Costtrans值比Leader節(jié)點(diǎn)與s節(jié)點(diǎn)之間的Costtrans小，則使用這條路徑進(jìn)行資源傳輸，如果沒有，則將這條路徑放入備用的資源路徑數(shù)據(jù)庫，以便在下次通信時(shí)可快速地形成鄰接關(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)定性這三個(gè)定向指標(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算法加入了報(bào)文分割和節(jié)點(diǎn)資源列表。在資源請求時(shí)，請求節(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ù)時(shí)，將請求資源分段分別發(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ù)淠Ｐ?，每個(gè)節(jié)點(diǎn)所需維護(hù)的節(jié)點(diǎn)關(guān)系較少，同時(shí)由于此協(xié)議在數(shù)據(jù)傳輸時(shí)采用了動態(tài)分布式傳輸方式，就同一個(gè)資源而言，每個(gè)授信節(jié)點(diǎn)只需傳輸其中的一部分，同時(shí)這些授信節(jié)點(diǎn)的可靠性是相對較高的，因此其傳輸成功率與效率會明顯提高。

圖2 傳輸效率對比曲線

圖3顯示T-M協(xié)議的穩(wěn)定性高于NICE協(xié)議，因?yàn)門-M協(xié)議采用的分布式傳輸方式在其中一個(gè)節(jié)點(diǎn)失效后，會有后備節(jié)點(diǎn)接替，且在選取資源節(jié)點(diǎn)時(shí)采用了較為復(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)性，各個(gè)數(shù)據(jù)鏈路之間的帶寬、延時(shí)等差異較大，因此通過綜合考量節(jié)點(diǎn)貢獻(xiàn)值、跳數(shù)、帶寬、延時(shí)等，將博弈原理加入到組播算法當(dāng)中。雖然此算法在控制開銷方面相比CPBM、NICE協(xié)議要大，但是在傳輸效率和穩(wěn)定性方面有所提升，在目前終端處理能力大幅度提升的情況下，提高數(shù)據(jù)的傳輸準(zhǔn)確率，才是更為緊要的課題[16]。

參考文獻(xiàn)：

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

[2] 劉期烈,劉茂松,李 云.基于博弈論的機(jī)會網(wǎng)絡(luò)激勵機(jī)制的研究[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ì)算機(jī)應(yīng)用,2009,29(11):2884-2886.

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

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