潘華強， 向昕彥

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

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

潘華強， 向昕彥

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

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

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

0 引言

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

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

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

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

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

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

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

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

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

1.1 激勵機制工作過程

此激勵機制的工作過程分為以下3部分：

(1)每個節(jié)點共享文件并且設(shè)置所共享文件等級。

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

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

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

1.2 節(jié)點絕對供獻值評估

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

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

ξi=αφi-ψi

(1)

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

1.2.1 供給值

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

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

通過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都是一致性矩陣，因此不需要再對它們進行一致性檢查，也不用對它們的結(jié)果進行一致性檢查。故組合權(quán)值可以被看作表1中4個元素的權(quán)值。

于是，供給值的計算公式如下：

φ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 利益值

與計算供給值相比，計算利益值更加簡單，因為它只需考慮兩個因素：下載文件數(shù)量和下載文件大小。由于兩者同等重要，因此可以直接給出它們的權(quán)重值，如表2所示。

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

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

因此，利益值的計算公式如下：

ψi=0.5(ni_down+|Si_down|)

(5)

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

ξ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é)點物理特性評估

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

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

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

Γi= 0.28T_clocki+0.093Wi+0.051V_RAMi

+0.154S_RAMi+0.049S_HDi+0.373B_upi

(7)

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

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

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

(8)

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

(9)

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

(10)

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

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

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

(11)

從式(11)得出：

(12)

2 仿真及結(jié)果

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

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

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

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

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

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

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

3 結(jié)論

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

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

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

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

[8] 鄭曉健,付鐵威,李彤,等.一種新的基于訪問興趣相似性的P2P網(wǎng)絡(luò)模型[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

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

2015-08-27)

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

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