潘華強(qiáng)， 向昕彥

(武漢軟件工程職業(yè)學(xué)院，湖北 武漢 430205)

基于等級(jí)結(jié)構(gòu)的對(duì)等網(wǎng)絡(luò)激勵(lì)機(jī)制研究

潘華強(qiáng)， 向昕彥

(武漢軟件工程職業(yè)學(xué)院，湖北 武漢 430205)

搭便車行為對(duì)對(duì)等網(wǎng)絡(luò)造成嚴(yán)重負(fù)面影響。首先提出了一種基于等級(jí)概念的網(wǎng)絡(luò)激勵(lì)機(jī)制以抑制搭便車行為并解決公共悲劇問題。所提出的效用函數(shù)為公平性特別考慮了用戶的絕對(duì)貢獻(xiàn)值和物理特性，并根據(jù)層次分析法來(lái)計(jì)算它們的值。通過(guò)實(shí)驗(yàn)仿真證明了此種機(jī)制的有效性和實(shí)用性，并對(duì)此機(jī)制的發(fā)展給出了展望。

對(duì)等網(wǎng)絡(luò)；搭便車；激勵(lì)機(jī)制；等級(jí)結(jié)構(gòu)

0 引言

對(duì)等(peer-to-peer,簡(jiǎn)稱P2P)系統(tǒng)簡(jiǎn)單地定義為通過(guò)直接交換共享計(jì)算機(jī)資源和服務(wù)，不同PC用戶之間不經(jīng)過(guò)中繼設(shè)備直接交換數(shù)據(jù)或服務(wù)的技術(shù)，它允許互聯(lián)網(wǎng)用戶直接使用對(duì)方的文件，使得網(wǎng)絡(luò)上的溝通變得容易、更直接，真正地消除了中間商。

從計(jì)算模式上來(lái)說(shuō)，P2P打破了傳統(tǒng)的Client/Server(C/S) 模式[1]，在網(wǎng)絡(luò)中的每個(gè)節(jié)點(diǎn)的地位都是對(duì)等的。每個(gè)節(jié)點(diǎn)既充當(dāng)服務(wù)器，為其他節(jié)點(diǎn)提供服務(wù)，同時(shí)也享用其他節(jié)點(diǎn)提供的服務(wù)。

搭便車(free-riding)行為是對(duì)等網(wǎng)絡(luò)節(jié)點(diǎn)用戶具有自私心理作用下的一種結(jié)果。參考文獻(xiàn)[2]歸納出了如下搭便車的主要不良影響：

(1)對(duì)等網(wǎng)絡(luò)中在線節(jié)點(diǎn)越多，熱心節(jié)點(diǎn)的負(fù)擔(dān)越大，可能導(dǎo)致熱心節(jié)點(diǎn)因長(zhǎng)期過(guò)載而宕機(jī)或主動(dòng)退出；

(2)多數(shù)節(jié)點(diǎn)的搭便車行為會(huì)降低對(duì)等網(wǎng)絡(luò)的生命周期；

(3)如果搭便車現(xiàn)象過(guò)于嚴(yán)重，對(duì)等網(wǎng)絡(luò)將趨近于C/S通信模式。

為了抑制搭便車行為，本文提出了一種基于等級(jí)概念的激勵(lì)機(jī)制[3]，通過(guò)限制節(jié)點(diǎn)下載文件的權(quán)限來(lái)鼓勵(lì)節(jié)點(diǎn)多做貢獻(xiàn)。在此抑制機(jī)制中，每個(gè)節(jié)點(diǎn)都是獨(dú)立的，并且能夠通過(guò)計(jì)算自己分享文件的等級(jí)來(lái)控制它的服務(wù)節(jié)點(diǎn)數(shù)量，從而解決公共悲劇問題[4]。

1 基于等級(jí)結(jié)構(gòu)的搭便車行為抑制機(jī)制的提出

首先給出這種新的激勵(lì)機(jī)制在P2P網(wǎng)絡(luò)中的工作過(guò)程。

1.1 激勵(lì)機(jī)制工作過(guò)程

此激勵(lì)機(jī)制的工作過(guò)程分為以下3部分：

(1)每個(gè)節(jié)點(diǎn)共享文件并且設(shè)置所共享文件等級(jí)。

(2)系統(tǒng)中的用戶只能下載等于或低于自己等級(jí)的文件。

(3)當(dāng)用戶進(jìn)入系統(tǒng)時(shí)，系統(tǒng)就會(huì)自動(dòng)更新用戶的物理特性，而只要用戶一直待在系統(tǒng)中，每隔幾小時(shí)，系統(tǒng)就會(huì)更新它的絕對(duì)供給值，然后更新用戶的等級(jí)。此外，當(dāng)一個(gè)新用戶加入系統(tǒng)時(shí)，系統(tǒng)定義它的等級(jí)最低。

上述的過(guò)程說(shuō)明首先要計(jì)算出絕對(duì)貢獻(xiàn)值和物理特性值，然后根據(jù)它們得出新的效用函數(shù)，最后建立等級(jí)結(jié)構(gòu)并找出效用函數(shù)與等級(jí)之間的對(duì)應(yīng)關(guān)系。

1.2 節(jié)點(diǎn)絕對(duì)供獻(xiàn)值評(píng)估

一個(gè)節(jié)點(diǎn)在一段時(shí)間內(nèi)對(duì)系統(tǒng)所做的絕對(duì)供給涉及8個(gè)因素：節(jié)點(diǎn)共享文件的數(shù)量、節(jié)點(diǎn)已下載文件的數(shù)量、節(jié)點(diǎn)已上傳文件數(shù)量、節(jié)點(diǎn)已下載數(shù)據(jù)的大小、節(jié)點(diǎn)已上傳數(shù)據(jù)的大小、節(jié)點(diǎn)已上傳文件大小、文件被共享次數(shù)、節(jié)點(diǎn)登錄系統(tǒng)次數(shù)，即：ni_share、ni_down、ni_up、Si_share、Si_down、Si_up、ti、Logi。

節(jié)點(diǎn)的絕對(duì)貢獻(xiàn)值就是它的供給值(φi)與利益值(ψi)兩者之差，即：

ξi=αφi-ψi

(1)

其中，α是個(gè)變量系數(shù)。節(jié)點(diǎn)的供給值就是整個(gè)系統(tǒng)從此節(jié)點(diǎn)的得益，利益值就是節(jié)點(diǎn)從系統(tǒng)中的得益。

1.2.1 供給值

首先需要確定節(jié)點(diǎn)的供給值，本文用層次分析法(AHP)[5]來(lái)解決這個(gè)問題。在上面所提到的3個(gè)部分中，只有共享和上傳是與供給值有關(guān)的。共享又被分成兩個(gè)子部分：共享文件的總數(shù)量和總大小。

AHP的第二步就是通過(guò)成對(duì)比較得出優(yōu)先級(jí)別的過(guò)程。得出了3個(gè)成對(duì)比較矩陣(A,B1,B2)，A是C1、C2對(duì)于φ的相對(duì)重要性；B1、B2是C11、C12、C21、C22對(duì)于C1、C2的相對(duì)重要性。

通過(guò)Aw=λw, 能夠得到最大特征值以及A、B1和B2的特征向量：

λ(1)=2,w(1)=[0.125 0.875]T;

λ1(2)=2,w1(2)=[0.333 0.667 0 0]T;

λ2(2)=2,w2(2)=[0 0 0.333 0.667]T。

因此，組合權(quán)值為：

(2)

由于A、B1和B2都是一致性矩陣，因此不需要再對(duì)它們進(jìn)行一致性檢查，也不用對(duì)它們的結(jié)果進(jìn)行一致性檢查。故組合權(quán)值可以被看作表1中4個(gè)元素的權(quán)值。

于是，供給值的計(jì)算公式如下：

φi=0.042|ti|/TLogi+0.083〈Si_share,ti〉/TLogi

+0.292ni_up/Logi+0.583|Si_up|/Logi

(3)

(4)

1.2.2 利益值

與計(jì)算供給值相比，計(jì)算利益值更加簡(jiǎn)單，因?yàn)樗恍杩紤]兩個(gè)因素：下載文件數(shù)量和下載文件大小。由于兩者同等重要，因此可以直接給出它們的權(quán)重值，如表2所示。

表1 供給值因素的權(quán)重

表2 利益值因素權(quán)重

因此，利益值的計(jì)算公式如下：

ψi=0.5(ni_down+|Si_down|)

(5)

根據(jù)式(1)、式(3)和式(5), 本文得出了絕對(duì)貢獻(xiàn)值的計(jì)算公式：

ξi=αφi-ψi=α(0.042|ti|/TLogi+0.083〈Si_share,ti〉/TLogi+0.292ni_up/Logi+0.583|Si_up|/Logi)-0.5(ni_down+|Si_down|)

(6)

1.3 節(jié)點(diǎn)物理特性評(píng)估

很難完成節(jié)點(diǎn)物理特性的量化過(guò)程，因?yàn)樵撨^(guò)程受很多因素影響，為了簡(jiǎn)化這個(gè)問題，本文暫時(shí)只考慮影響用戶共享行為的幾個(gè)重要因素。在本文的估算模型中，只選出了以下6個(gè)因素： CPU的時(shí)鐘頻率和字長(zhǎng)、RAM的存儲(chǔ)大小和存儲(chǔ)速度、硬盤大小、上傳帶寬。

由于矩陣A′不是一致性矩陣，因此這部分中的結(jié)果還要做一致性檢測(cè)。CI是一致性指數(shù)，CR是一致性比率。

于是，得到了如下的物理特性估算公式：

Γi= 0.28T_clocki+0.093Wi+0.051V_RAMi

+0.154S_RAMi+0.049S_HDi+0.373B_upi

(7)

1.4 抑制機(jī)制的效用函數(shù)

效用函數(shù)[6]是用來(lái)衡量系統(tǒng)中的用戶對(duì)系統(tǒng)所做貢獻(xiàn)的，它是激勵(lì)機(jī)制設(shè)計(jì)的核心。在本文所提出的激勵(lì)機(jī)制中，將它定義為：

U(i,h)=U(i,h-T)+U(i,T)

(8)

其中，U(i,h-T)是節(jié)點(diǎn)i從它首次進(jìn)入系統(tǒng)到當(dāng)前的積累效用,U(i,T)則是當(dāng)下節(jié)點(diǎn)i創(chuàng)造的效用，它是絕對(duì)供給值與物理特性值的比值，即：

(9)

通過(guò)式(8)和式(9),本文得出了下面的效用函數(shù)：

(10)

1.5 等級(jí)結(jié)構(gòu)的建立

假設(shè)等級(jí)結(jié)構(gòu)中一共包含nrank級(jí),而nrank對(duì)于不同的系統(tǒng)和不同的時(shí)期都是不同的。鑒于本文提出的抑制機(jī)制與量化比較相似，且用戶需要自己設(shè)定共享文件等級(jí)，因此限定nrank≤9。

為了建立金字塔型結(jié)構(gòu)[7]，本文約定上層等級(jí)用戶數(shù)量約為下層用戶數(shù)量的2/3且第一級(jí)(最底層)用戶數(shù)量為μ·τ,τ是此級(jí)別用戶總量，μ是個(gè)參數(shù)，于是：

(11)

從式(11)得出：

(12)

2 仿真及結(jié)果

本文使用了BA模型[8]來(lái)構(gòu)建拓?fù)浣Y(jié)構(gòu)并且在機(jī)器上對(duì)P2P系統(tǒng)進(jìn)行了仿真。本文假設(shè)系統(tǒng)中分布著1 000份文件且這些文件的大小是隨機(jī)的。在仿真系統(tǒng)中每個(gè)節(jié)點(diǎn)都有自己的虛擬硬件和上傳帶寬，但是它們所共享文件數(shù)量則是隨機(jī)分配的。本文分別模擬了沒有控制機(jī)制的初始P2P系統(tǒng)和在基于等級(jí)概念的激勵(lì)機(jī)制控制下的P2P系統(tǒng)從5 000節(jié)點(diǎn)到14 000節(jié)點(diǎn)的增長(zhǎng)過(guò)程，并得到了一些比較數(shù)據(jù)，如圖1和圖2所示。

圖1 原始P2P系統(tǒng)與基于等級(jí)概率的激勵(lì)機(jī)制系統(tǒng)的搭便車者數(shù)量比較

圖2 兩種系統(tǒng)中搭便車行為的范圍比較

從圖1可以看出，在基于等級(jí)概念的激勵(lì)機(jī)制下的搭便車者數(shù)量隨著時(shí)間明顯減少，但是原始系統(tǒng)中的搭便車者數(shù)量卻是增加的。

在圖2中,仿真結(jié)果顯示在起初的10個(gè)時(shí)間段中，系統(tǒng)中的用戶數(shù)量以每段1 000的數(shù)量呈增長(zhǎng)趨勢(shì)，而搭便車者在所有用戶中的比例是在所提出的系統(tǒng)中呈下降趨勢(shì)的，但在原始P2P系統(tǒng)中則是上升的。

從圖1和圖2看到，基于等級(jí)概念的激勵(lì)機(jī)制確實(shí)使搭便車者數(shù)量減少了，從而證明此機(jī)制確實(shí)能有效抑制系統(tǒng)中的搭便車行為。

此外，圖1和圖2中的Incentive曲線并沒有降至0而是一直慢慢減少，這證明了本文提出的激勵(lì)機(jī)制雖然有效減少了搭便車行為，但是不能徹底消除系統(tǒng)中的搭便車行為。

3 結(jié)論

雖然本文提出了一種新的激勵(lì)機(jī)制來(lái)抑制系統(tǒng)中的搭便車行為和解決公共悲劇的問題，但許多方面還需要進(jìn)一步深入研究。在本文中，將新用戶的等級(jí)設(shè)為最低，雖然有效抑制了重新洗牌的問題，但卻使得新用戶的等級(jí)低于搭便車者。將會(huì)在未來(lái)的工作中解決這一問題。

[1] ANDROUTSELLIS-THEOTOKIS S， SPINELLIS D. A survey of peer-to-peer content distribution technologies[C]. ACM Computing Surveys, 2004, 36(4):335-371.[2] ADAR E, HUBERMAN B. Free riding on gnutella[J]. First Monday, 2000,5(10):134-139.

[3] HARDIN G. The tragedy of the commons[J]. Science, 1968, 162(3859):1243-1248.

[4] Yu Yijiao, Jin Hai. A survey on overcoming free riding in peer-to-peer networks[J]. Chinese Journal of Computers, 2008, 31(1):1-15.

[5] 郭劍峰,陳小波,陳瀟君,等.具有負(fù)載分享的P2P IPTV重迭網(wǎng)絡(luò)的設(shè)計(jì)[J].電子技術(shù)應(yīng)用,2014,40(1):107-110.

[6] 楊楷,汪斌強(qiáng),張震,等.基于多特征的P2P直播流識(shí)別方法[J].電子技術(shù)應(yīng)用,2014,40(2):125-127,131.

[7] 李淑霞.基于JXTA的P2P實(shí)例的研究與實(shí)現(xiàn)[J].微型機(jī)與應(yīng)用,2013,32(14):59-60,64.

[8] 鄭曉健,付鐵威,李彤,等.一種新的基于訪問興趣相似性的P2P網(wǎng)絡(luò)模型[J].微型機(jī)與應(yīng)用,2014,33(21):51-53.

Research on the incentive mechanism of P2P network based on hierarchical structure

Pan Huaqiang，Xiang Xinyan

(Wuhan Vocational College of Software and Engineering,Wuhan 430205,China)

Free-riding is a grave threat against P2P networks. This paper proposes a rank-based incentive mechanism to restrain the free-riding and solve the tragedy of the commons problem. The utility function in this paper takes the absolute contribution value and the physical performance into account for the fairness and their value are calculated by analytic hierarchy process. The simulations verifies that this mechanism is effective and practical.

peer-to-peer network;free-riding;incentive mechanism;rank structure

TP393

A

1674-7720(2016)02-0057-03

潘華強(qiáng)，向昕彥. 基于等級(jí)結(jié)構(gòu)的對(duì)等網(wǎng)絡(luò)激勵(lì)機(jī)制研究[J] .微型機(jī)與應(yīng)用，2016,35(2)：57-59.

2015-08-27)

潘華強(qiáng)(1983-)，通信作者，男，碩士，工程師，主要研究方向：對(duì)等網(wǎng)絡(luò)。E-mail:hzau0302@qq.com。

向昕彥(1973-)，男，碩士，高級(jí)工程師，主要研究方向：高校信息化。