潘華強(qiáng),, 向昕彥
(武漢軟件工程職業(yè)學(xué)院,,湖北 武漢 430205)
摘要:搭便車行為對對等網(wǎng)絡(luò)造成嚴(yán)重負(fù)面影響。首先提出了一種基于等級概念的網(wǎng)絡(luò)激勵機(jī)制以抑制搭便車行為并解決公共悲劇問題,。所提出的效用函數(shù)為公平性特別考慮了用戶的絕對貢獻(xiàn)值和物理特性,,并根據(jù)層次分析法來計(jì)算它們的值。通過實(shí)驗(yàn)仿真證明了此種機(jī)制的有效性和實(shí)用性,,并對此機(jī)制的發(fā)展給出了展望,。
關(guān)鍵詞:對等網(wǎng)絡(luò);搭便車,;激勵機(jī)制,;等級結(jié)構(gòu)
0引言
對等(peertopeer,簡稱P2P)系統(tǒng)簡單地定義為通過直接交換共享計(jì)算機(jī)資源和服務(wù),不同PC用戶之間不經(jīng)過中繼設(shè)備直接交換數(shù)據(jù)或服務(wù)的技術(shù),,它允許互聯(lián)網(wǎng)用戶直接使用對方的文件,,使得網(wǎng)絡(luò)上的溝通變得容易、更直接,,真正地消除了中間商,。
從計(jì)算模式上來說,P2P打破了傳統(tǒng)的Client/Server(C/S) 模式[1],,在網(wǎng)絡(luò)中的每個節(jié)點(diǎn)的地位都是對等的,。每個節(jié)點(diǎn)既充當(dāng)服務(wù)器,為其他節(jié)點(diǎn)提供服務(wù),,同時也享用其他節(jié)點(diǎn)提供的服務(wù),。
搭便車(freeriding)行為是對等網(wǎng)絡(luò)節(jié)點(diǎn)用戶具有自私心理作用下的一種結(jié)果。參考文獻(xiàn)[2]歸納出了如下搭便車的主要不良影響:
(1)對等網(wǎng)絡(luò)中在線節(jié)點(diǎn)越多,,熱心節(jié)點(diǎn)的負(fù)擔(dān)越大,,可能導(dǎo)致熱心節(jié)點(diǎn)因長期過載而宕機(jī)或主動退出;
(2)多數(shù)節(jié)點(diǎn)的搭便車行為會降低對等網(wǎng)絡(luò)的生命周期,;
(3)如果搭便車現(xiàn)象過于嚴(yán)重,,對等網(wǎng)絡(luò)將趨近于C/S通信模式。
為了抑制搭便車行為,,本文提出了一種基于等級概念的激勵機(jī)制[3],通過限制節(jié)點(diǎn)下載文件的權(quán)限來鼓勵節(jié)點(diǎn)多做貢獻(xiàn),。在此抑制機(jī)制中,,每個節(jié)點(diǎn)都是獨(dú)立的,,并且能夠通過計(jì)算自己分享文件的等級來控制它的服務(wù)節(jié)點(diǎn)數(shù)量,從而解決公共悲劇問題[4],。
1基于等級結(jié)構(gòu)的搭便車行為抑制機(jī)制的提出
首先給出這種新的激勵機(jī)制在P2P網(wǎng)絡(luò)中的工作過程,。
1.1激勵機(jī)制工作過程
此激勵機(jī)制的工作過程分為以下3部分:
(1)每個節(jié)點(diǎn)共享文件并且設(shè)置所共享文件等級,。
?。?)系統(tǒng)中的用戶只能下載等于或低于自己等級的文件。
?。?)當(dāng)用戶進(jìn)入系統(tǒng)時,,系統(tǒng)就會自動更新用戶的物理特性,而只要用戶一直待在系統(tǒng)中,,每隔幾小時,,系統(tǒng)就會更新它的絕對供給值,然后更新用戶的等級,。此外,,當(dāng)一個新用戶加入系統(tǒng)時,系統(tǒng)定義它的等級最低,。
上述的過程說明首先要計(jì)算出絕對貢獻(xiàn)值和物理特性值,,然后根據(jù)它們得出新的效用函數(shù),最后建立等級結(jié)構(gòu)并找出效用函數(shù)與等級之間的對應(yīng)關(guān)系,。
1.2節(jié)點(diǎn)絕對供獻(xiàn)值評估
一個節(jié)點(diǎn)在一段時間內(nèi)對系統(tǒng)所做的絕對供給涉及8個因素:節(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)的絕對貢獻(xiàn)值就是它的供給值(φi)與利益值(ψi)兩者之差,即:
ξi=αφi-ψi(1)
其中,α是個變量系數(shù),。節(jié)點(diǎn)的供給值就是整個系統(tǒng)從此節(jié)點(diǎn)的得益,,利益值就是節(jié)點(diǎn)從系統(tǒng)中的得益。
1.2.1供給值
首先需要確定節(jié)點(diǎn)的供給值,,本文用層次分析法(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)=[01250875]T;
λ1(2)=2, w1(2)=[0333066700]T;
λ2(2)=2, w2(2)=[0003330667]T,。
因此,組合權(quán)值為:
w=[w1(2), w2(2)]w(1)=0042
0083
0292
0583(2)
由于A,、B1和B2都是一致性矩陣,,因此不需要再對它們進(jìn)行一致性檢查,也不用對它們的結(jié)果進(jìn)行一致性檢查,。故組合權(quán)值可以被看作表1中4個元素的權(quán)值,。
于是,供給值的計(jì)算公式如下:
φi=0042|ti|/TLogi+0083〈Si_share,ti〉/TLogi
+0292ni_up/Logi+0583|Si_up|/Logi(3)
<Si_share, ti>=∑ni_sharef=1(si_f·ti_f)(4)
1.2.2利益值
與計(jì)算供給值相比,,計(jì)算利益值更加簡單,,因?yàn)樗恍杩紤]兩個因素:下載文件數(shù)量和下載文件大小。由于兩者同等重要,,因此可以直接給出它們的權(quán)重值,,如表2所示。
因此,,利益值的計(jì)算公式如下:
ψi=05(ni_down+|Si_down|)(5)
根據(jù)式(1),、式(3)和式(5), 本文得出了絕對貢獻(xiàn)值的計(jì)算公式:
ξi=αφi-ψi=α(0042|ti|/TLogi+0083〈Si_share,ti〉/TLogi+0292ni_up/Logi+0583|Si_up|/Logi)-05(ni_down+|Si_down|)(6)
1.3節(jié)點(diǎn)物理特性評估
很難完成節(jié)點(diǎn)物理特性的量化過程,因?yàn)樵撨^程受很多因素影響,,為了簡化這個問題,,本文暫時只考慮影響用戶共享行為的幾個重要因素,。在本文的估算模型中,只選出了以下6個因素: CPU的時鐘頻率和字長,、RAM的存儲大小和存儲速度,、硬盤大小,、上傳帶寬,。
由于矩陣A′不是一致性矩陣,因此這部分中的結(jié)果還要做一致性檢測,。CI是一致性指數(shù),,CR是一致性比率。
于是,,得到了如下的物理特性估算公式:
Γi=028T_clocki+0093Wi+0051V_RAMi
+0154S_RAMi+0049S_HDi+0373B_upi(7)
1.4抑制機(jī)制的效用函數(shù)
效用函數(shù)[6]是用來衡量系統(tǒng)中的用戶對系統(tǒng)所做貢獻(xiàn)的,,它是激勵機(jī)制設(shè)計(jì)的核心。在本文所提出的激勵機(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)造的效用,它是絕對供給值與物理特性值的比值,,即:
1.5等級結(jié)構(gòu)的建立
假設(shè)等級結(jié)構(gòu)中一共包含nrank級,而nrank對于不同的系統(tǒng)和不同的時期都是不同的,。鑒于本文提出的抑制機(jī)制與量化比較相似,且用戶需要自己設(shè)定共享文件等級,,因此限定nrank≤9,。
為了建立金字塔型結(jié)構(gòu)[7],本文約定上層等級用戶數(shù)量約為下層用戶數(shù)量的2/3且第一級(最底層)用戶數(shù)量為μ·τ,τ是此級別用戶總量,,μ是個參數(shù),,于是:
2仿真及結(jié)果
本文使用了BA模型[8]來構(gòu)建拓?fù)浣Y(jié)構(gòu)并且在機(jī)器上對P2P系統(tǒng)進(jìn)行了仿真。本文假設(shè)系統(tǒng)中分布著1 000份文件且這些文件的大小是隨機(jī)的,。在仿真系統(tǒng)中每個節(jié)點(diǎn)都有自己的虛擬硬件和上傳帶寬,,但是它們所共享文件數(shù)量則是隨機(jī)分配的。本文分別模擬了沒有控制機(jī)制的初始P2P系統(tǒng)和在基于等級概念的激勵機(jī)制控制下的P2P系統(tǒng)從5 000節(jié)點(diǎn)到14 000節(jié)點(diǎn)的增長過程,,并得到了一些比較數(shù)據(jù),,如圖1和圖2所示。
系統(tǒng)的搭便車者數(shù)量比較
從圖1可以看出,,在基于等級概念的激勵機(jī)制下的搭便車者數(shù)量隨著時間明顯減少,,但是原始系統(tǒng)中的搭便車者數(shù)量卻是增加的。
在圖2中,仿真結(jié)果顯示在起初的10個時間段中,,系統(tǒng)中的用戶數(shù)量以每段1 000的數(shù)量呈增長趨勢,,而搭便車者在所有用戶中的比例是在所提出的系統(tǒng)中呈下降趨勢的,但在原始P2P系統(tǒng)中則是上升的,。
從圖1和圖2看到,,基于等級概念的激勵機(jī)制確實(shí)使搭便車者數(shù)量減少了,從而證明此機(jī)制確實(shí)能有效抑制系統(tǒng)中的搭便車行為。
此外,,圖1和圖2中的Incentive曲線并沒有降至0而是一直慢慢減少,,這證明了本文提出的激勵機(jī)制雖然有效減少了搭便車行為,但是不能徹底消除系統(tǒng)中的搭便車行為,。
3結(jié)論
雖然本文提出了一種新的激勵機(jī)制來抑制系統(tǒng)中的搭便車行為和解決公共悲劇的問題,,但許多方面還需要進(jìn)一步深入研究。在本文中,,將新用戶的等級設(shè)為最低,,雖然有效抑制了重新洗牌的問題,但卻使得新用戶的等級低于搭便車者,。將會在未來的工作中解決這一問題,。
參考文獻(xiàn)
[1] ANDROUTSELLISTHEOTOKIS S,, SPINELLIS D. A survey of peertopeer content distribution technologies[C]. ACM Computing Surveys, 2004, 36(4):335371.
?。?] ADAR E, HUBERMAN B. Free riding on gnutella[J]. First Monday, 2000,5(10):134139.
[3] HARDIN G. The tragedy of the commons[J]. Science, 1968, 162(3859):12431248.
?。?] Yu Yijiao, Jin Hai. A survey on overcoming free riding in peertopeer networks[J]. Chinese Journal of Computers, 2008, 31(1):115.
?。?] 郭劍峰,陳小波,陳瀟君,等.具有負(fù)載分享的P2P IPTV重迭網(wǎng)絡(luò)的設(shè)計(jì)[J].電子技術(shù)應(yīng)用,2014,40(1):107110.
[6] 楊楷,汪斌強(qiáng),張震,等.基于多特征的P2P直播流識別方法[J].電子技術(shù)應(yīng)用,2014,40(2):125127,131.
?。?] 李淑霞.基于JXTA的P2P實(shí)例的研究與實(shí)現(xiàn)[J].微型機(jī)與應(yīng)用,2013,32(14):5960,64.
?。?] 鄭曉健,付鐵威,李彤,等.一種新的基于訪問興趣相似性的P2P網(wǎng)絡(luò)模型[J].微型機(jī)與應(yīng)用,2014,33(21):5153.