ＷＭＮ基于理性博弈的懲罰機(jī)制

摘要：在借鑒已有P2P網(wǎng)絡(luò)激勵(lì)機(jī)制的基礎(chǔ)上，結(jié)合WMN的特點(diǎn)，提出了一種基于理性博弈的懲罰機(jī)制，并構(gòu)建了該機(jī)制的有限自動(dòng)機(jī)模型。懲罰機(jī)制能有效地理性懲罰自私節(jié)點(diǎn)，威懾其放棄自私行為。仿真結(jié)果驗(yàn)證了機(jī)制的有效性。

關(guān)鍵詞：無(wú)線網(wǎng)狀網(wǎng)；對(duì)等網(wǎng)絡(luò)；理性博弈；懲罰機(jī)制

中圖分類號(hào)：TP301．6文獻(xiàn)標(biāo)志碼：A

文章編號(hào)：1001－3695(2008)01－0062－02

0引言

WMN以端到端的模式展開(kāi)，從網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)上可以看做是無(wú)線版、微縮版的Internet網(wǎng)。在Internet中，P2P技術(shù)充分利用分布在網(wǎng)絡(luò)中的各種資源，包括計(jì)算資源、帶寬資源、內(nèi)容資源等，降低了網(wǎng)絡(luò)用戶對(duì)網(wǎng)絡(luò)服務(wù)器資源消耗的需求，同時(shí)也為網(wǎng)絡(luò)用戶帶來(lái)巨大利益。近年來(lái)，移動(dòng)終端的計(jì)算處理能力、存儲(chǔ)容量和通信能力等都在不斷增長(zhǎng)。隨著這些設(shè)備在WMN中的大量使用，使得在WMN中實(shí)現(xiàn)P2P資源共享變得可能。

P2P技術(shù)的精神實(shí)質(zhì)是用戶相互合作、互惠互利，用戶共享自己資源的目的是為了可以使用別人的資源，從而實(shí)現(xiàn)雙贏。在正常情況下，如果用戶為越多的網(wǎng)絡(luò)用戶提供了共享服務(wù)，那么他越有可能獲得較多的利益回報(bào)。但是，在網(wǎng)絡(luò)中可能存在一些理性的自私用戶，總是試圖多使用別人的資源，少貢獻(xiàn)自己的資源。事實(shí)上，網(wǎng)絡(luò)中節(jié)點(diǎn)采取自私策略是為了贏得更多的利益。如果在網(wǎng)絡(luò)中有一種激勵(lì)策略，能使得節(jié)點(diǎn)采取自私策略將減少其所得利益，那么也就能有效地避免節(jié)點(diǎn)自私行為的產(chǎn)生，并保證交換中的公平性以維持網(wǎng)絡(luò)中P2P文件共享變得非常重要。

實(shí)驗(yàn)測(cè)算，在Gnutella中有25%的節(jié)點(diǎn)從來(lái)不共享數(shù)據(jù)給別人，只從別人那里下載數(shù)據(jù)，并且有大量的用戶（大約占30%）低報(bào)自己的帶寬以降低其他用戶下載其數(shù)據(jù)的意愿[1，2]。因此，在WMN中建立一套適合于P2P應(yīng)用的懲罰/激勵(lì)機(jī)制是非常必要的。建立懲罰/激勵(lì)機(jī)制的目的在于約束在沒(méi)有第三方集中管理的P2P網(wǎng)絡(luò)中的用戶行為，從而盡量保證網(wǎng)絡(luò)整體性能的最優(yōu)性及穩(wěn)定性。如何激勵(lì)網(wǎng)絡(luò)節(jié)點(diǎn)參與和共享自己的資源，P. Golle等人[3]提出了使用micro payment和virtual currency的方法來(lái)解決共享激勵(lì)問(wèn)題，并用博弈方法分析了這兩種方法的可行性。文獻(xiàn)[4]中提出的Fileteller系統(tǒng)也使用了micro payment方法解決激勵(lì)問(wèn)題，但使用支付的方法本身需要涉及到權(quán)威的第三方和安全身份認(rèn)證，這不切合WMN的環(huán)境。文獻(xiàn)[5，6]中提出的CFS系統(tǒng)和PAST系統(tǒng)則使用了存儲(chǔ)配額方法；Farsite[7]及Pastiche[8]則通過(guò)評(píng)估節(jié)點(diǎn)占用的存儲(chǔ)資源是否與其貢獻(xiàn)的存儲(chǔ)資源相當(dāng)?shù)姆椒▉?lái)構(gòu)建激勵(lì)機(jī)制。另外還有一些其他的激勵(lì)機(jī)制也被提出[9~11]。由于WMN拓?fù)浣Y(jié)構(gòu)易變、缺乏可信第三方等固有特點(diǎn)，使得這些針對(duì)傳統(tǒng)P2P網(wǎng)絡(luò)構(gòu)建的激勵(lì)機(jī)制不能應(yīng)用。為此，在結(jié)合WMN特點(diǎn)的基礎(chǔ)上，本文提出了一種基于理性博弈的懲罰機(jī)制，構(gòu)建了對(duì)應(yīng)的有限狀態(tài)機(jī)模型。

1理性博弈懲罰機(jī)制

一個(gè)節(jié)點(diǎn)面對(duì)網(wǎng)絡(luò)中其他節(jié)點(diǎn)的共享請(qǐng)求時(shí)，采取何種策略以最大化自己的利益，可以看做是一種博弈。由于無(wú)法預(yù)知節(jié)點(diǎn)何時(shí)退出網(wǎng)絡(luò)，該博弈沒(méi)有可識(shí)別的終點(diǎn)，是無(wú)限重復(fù)博弈。在WMN中，節(jié)點(diǎn)通過(guò)互相協(xié)作來(lái)維系整個(gè)網(wǎng)絡(luò)。在任何一個(gè)時(shí)刻，網(wǎng)絡(luò)中一個(gè)節(jié)點(diǎn)對(duì)于另一個(gè)節(jié)點(diǎn)可以有兩種策略選擇，即合作（C）或不合作（N）。在WMN中，節(jié)點(diǎn)不可能孤立所有其他節(jié)點(diǎn)，它必須選擇理性的博弈策略：通過(guò)降低非合作節(jié)點(diǎn)的既得利益，懲罰采取不合作策略的節(jié)點(diǎn)；以利益作為驅(qū)動(dòng)因素，加以懲罰的威懾作用，激勵(lì)節(jié)點(diǎn)采取合作策略。

考慮到WMN中節(jié)點(diǎn)由于彼此依賴而產(chǎn)生的協(xié)作性，本文采用n個(gè)周期的不合作作為懲罰，即若一個(gè)節(jié)點(diǎn)在某一次作用過(guò)程中采取了不合作策略，那么被拒絕請(qǐng)求節(jié)點(diǎn)對(duì)以后若干周期內(nèi)該節(jié)點(diǎn)的請(qǐng)求也采取不合作策略，而無(wú)論此時(shí)該節(jié)點(diǎn)采取何種策略，以達(dá)到懲罰的目的。在此基礎(chǔ)上，本文建立了理性博弈的有限狀態(tài)機(jī)模型。

1．1理性博弈

為了使理性博弈分析變得有意義，必須量化用戶收益和懲罰周期t。考慮囚徒困境階段博弈(表1)。

從圖2的統(tǒng)計(jì)數(shù)據(jù)可以看出，從仿真開(kāi)始到70 s左右的時(shí)間屬于路由收斂期；此后，70~150 s左右的時(shí)間段中，標(biāo)記為合作型的節(jié)點(diǎn)與被標(biāo)記為自私型的節(jié)點(diǎn)的請(qǐng)求成功率幾乎是相同的。因?yàn)楦鶕?jù)仿真初始設(shè)定，它們?cè)诖藭r(shí)間段內(nèi)都采用的是合作策略。隨后，從節(jié)點(diǎn)連接請(qǐng)求成功率的統(tǒng)計(jì)圖中可以看到，由于自私型節(jié)點(diǎn)采用了非合作策略而受到懲罰機(jī)制的懲罰，節(jié)點(diǎn)的連接請(qǐng)求成功率急劇下降；直到250 s左右時(shí)，部分節(jié)點(diǎn)的懲罰周期結(jié)束，請(qǐng)求成功率才略有回升。由于在仿真后期自私節(jié)點(diǎn)仍然采用的是非合作策略，請(qǐng)求成功率又開(kāi)始下降；直到330 s左右時(shí)，部分自私節(jié)點(diǎn)才又一次得到寬恕，使請(qǐng)求成功率得到提高，隨后又受到懲罰。由圖2的統(tǒng)計(jì)結(jié)果可以看出，合作型節(jié)點(diǎn)的連接成功率一直處于一個(gè)較為穩(wěn)定的范圍內(nèi)。與自私型節(jié)點(diǎn)的仿真結(jié)果比較表明，本文提出的理性博弈懲罰機(jī)制能有效地懲罰節(jié)點(diǎn)的自私行為，威懾節(jié)點(diǎn)采用合作策略。

參考文獻(xiàn)：

［1］ADAR E，HUBERMAN B A.Free riding on Gnutella，SSL－00－63[EB/OL].（2000）.http://firstmonday.org/issues/issue5 10/adar/index.html.

[2]SAROIU S，GUMMADI P K，GRIBBLE S.A measurement study of peer to peer file sharing systems[C]//Proc of Multimedia Compu ting and Networking (MMCN’02).San Jose:SPIE Press，2002.

[3]GOLLE P，LEYTON BROWN K，MIRONOV I，et al.Incentives for sharing in peer to peer networks[C]//Proc of the 3rd ACM Confe rence on Electronic Commerce.London:Springer Verlag，2001：264－267.

[4]IOANNIDIS J，IOANNIDIS S，KEROMYTIS A D，et al.Fileteller:pa ying and getting paid for file storage[C]//Proc of the 6th Annual Conference on Financial Cryptography.Bermuda:[s.n.]，2002:282－299.

[5]DABEK F，KAASHOEK M F，KARGER D，et al.Wide area cooperative storage with CFS[C]//Proc of the 18th ACM Symposium on Operating Systems Principles.New York:ACM Press，2001:202－215.

[6]ROWSTRON A，DRUSCHEL P.Storage management and caching in PAST， a large scale， persistent peer to peer storage utility[C]//Proc of the 18th ACM Symposium on Operating Systems Principles.New York:ACM Press，2001:188－201.

[7]ADYA A，BOLOSKY W J，CASTRO M.Farsite:federated，available， and reliable storage for an incompletely trusted environment [C]//Proc of the 5th Symposium on Operating Systems Design and Implementation.New York:ACM Press，2002:1－14.

[8]COX L P，MURRAY C D，NOBLE B D.Pastiche:making backup cheap and easy[C]//Proc of the 5th Symposium on Operating Systems Design and Implementation.New York:ACM Press，2002:285－298.

[9]MA R T B，LEE C M S，LUI J C S，et al.An incentive mechanism for P2P network [C]//Proc of the 24th International Conference on Distributed Computing Systems( ICDCS’04).Tokyo:[s.n.]，2004:516－523.

[10]FELDMAN M，LAI K，STOICA I，et al.Robust incentive techniques for peer to peer networks [C]//Proc of the 5th ACM Conference on Electronic Commerce.New York:ACM Press，2004:102－111.

[11]FEIGENBAUM J，SHENKER S.Distributed algorithmic mechanism design: recent results and future directions[C]//Proc of Discrete Algorithms and Methods for Mobile Computing and Communications.New York:ACM Press，2002:1－13.

[12]JOHNSON D B，MALTZ D A，HU YIH C.The dynamic source routing protocol for mobile Ad hoc networks(DSR)[R].[S.l.]:IETF MANET Working Group，2004.

“本文中所涉及到的圖表、注解、公式等內(nèi)容請(qǐng)以PDF格式閱讀原文”