ad hoc網(wǎng)絡(luò)尋路階段的合作激勵(lì)機(jī)制研究new

1、稿件編號(hào)：076271Adhoc網(wǎng)絡(luò)尋路階段的合作激勵(lì)機(jī)制研究網(wǎng)絡(luò)尋路階段的合作激勵(lì)機(jī)制研究黃蕾，劉立祥（中國(guó)科學(xué)院軟件研究所綜合信息系統(tǒng)技術(shù)國(guó)家級(jí)重點(diǎn)實(shí)驗(yàn)室，北京，100080）摘要：摘要：如何激勵(lì)屬于不同利益最大化實(shí)體的自私節(jié)點(diǎn)合作是當(dāng)前Adhoc網(wǎng)絡(luò)研究中的一個(gè)熱點(diǎn)問(wèn)題?，F(xiàn)有的自私節(jié)點(diǎn)檢測(cè)和激勵(lì)機(jī)制主要針對(duì)數(shù)據(jù)傳輸階段，不能適應(yīng)尋路階段的特點(diǎn)。本文基于鄰居節(jié)點(diǎn)中繼和生成的路由請(qǐng)求包之間的統(tǒng)計(jì)關(guān)系，提出了一種適用于按需路由協(xié)議尋路階

2、段的自私行為檢測(cè)和懲罰機(jī)制，并利用博弈論工具將其建模為噪聲環(huán)境下的重復(fù)囚徒困境博弈，對(duì)算法激勵(lì)合作的有效性進(jìn)行分析。理論分析和仿真結(jié)果顯示，本算法能夠有效地懲罰尋路中的自私行為，促進(jìn)節(jié)點(diǎn)合作。關(guān)鍵詞：關(guān)鍵詞：Adhoc網(wǎng)絡(luò)，路由，自私檢測(cè)，合作激勵(lì)，博弈論StudyoncooperationstimulationmechanisminroutediscoveryofadhocwksHuangLeiLiuLixiang(NationalK

3、eyLabatyofIntegratedInfmationSystemTechnologyInstituteofSoftwareChineseAcademyofSciencesBeijing100080)Abstract:Howtostimulateselfishnodeswhichbelongtodifferentutilitymaximizingentitiestocooperateisahottopicinadhocwkresea

4、rchcommunity.Currentmechanismsproposedsofarfocusmainlyondetectingselfishbehavistimulatingcooperationindatafwardingstage.Theyarenotapplicableinroutediscoverystage.Basedonstatisticsrelationshipofrouterequestpacketsrelayedg

5、eneratedbyaneighbnodethispaperproposedanalgithmtodetectpunishtheselfishnessinroutediscoverystagefondemroutingprotocols.Thealgithmwasmodeledwiththetoolofgametheyastherepeatedprisonerdilemmainnoisyenvironmentitseffectivene

6、sstostimulatecooperationwasanalyzedwiththemodel.Theeticanalysissimulationresultsshowedthatourschemecouldpunishtheselfishnessinroutediscoveryeffectivelythusstimulatenodestocooperate.Keywd:Adhocwkroutingselfishnessdetectio

7、ncooperationstimulationgamethey1引言引言Adhoc網(wǎng)絡(luò)由一組移動(dòng)或固定的無(wú)線節(jié)點(diǎn)組成，信息交流等網(wǎng)絡(luò)關(guān)鍵任務(wù)的實(shí)現(xiàn)需要各節(jié)點(diǎn)之間的相互協(xié)作，這種合作性也是現(xiàn)有諸多路由協(xié)議設(shè)計(jì)的一個(gè)基本假設(shè)前提。但是當(dāng)節(jié)點(diǎn)屬于不同實(shí)體時(shí)，其合作性缺乏內(nèi)在的保證，理性節(jié)點(diǎn)更傾向于采取能夠使得自身利益最大化的行動(dòng)，而不是完全遵從協(xié)議。由于無(wú)線傳輸需要耗費(fèi)大量的能量，因此理性的自私節(jié)點(diǎn)會(huì)盡量避免為其他節(jié)點(diǎn)中繼數(shù)據(jù)，從而導(dǎo)致網(wǎng)絡(luò)性

8、能下降，合作用戶利益受損。Adhoc網(wǎng)絡(luò)中自私節(jié)點(diǎn)的激勵(lì)機(jī)制是當(dāng)前的一個(gè)研究熱點(diǎn)，提出的解決方案可分為三種類(lèi)型[1]：基于信用的方法（creditbasedmethod），基于聲譽(yù)的方法（reputationbasedmethod），和博弈論方法（gametheymethod）。基于信用的方法一般建立在虛擬貨幣機(jī)制的基礎(chǔ)上，通過(guò)精心設(shè)計(jì)的支付方式，使得節(jié)點(diǎn)只有在合作的時(shí)候才能使自己的利益最大化[24]。這種方法的缺陷在于作為其基礎(chǔ)的虛擬

9、貨幣管理系統(tǒng)，或者需要抗篡改硬件的支持[2]，或者需要集中的支付服務(wù)[4]，尚未有令人滿意的解決方案；基于聲譽(yù)的方法記錄節(jié)點(diǎn)的過(guò)往行為，綜合直接觀察結(jié)果和第三方信息形成對(duì)節(jié)點(diǎn)合作性的判斷，對(duì)不合作的自私節(jié)點(diǎn)以拒絕服務(wù)的方式進(jìn)行懲罰，從而達(dá)到促進(jìn)合作的目的[58]。目前聲譽(yù)系統(tǒng)采用基于Watchdog[8]的隱式響應(yīng)或基于ACK的顯式響應(yīng)作為監(jiān)測(cè)的主要方式，[1][910]等文獻(xiàn)指出現(xiàn)有監(jiān)測(cè)機(jī)制的不準(zhǔn)確性是聲譽(yù)系統(tǒng)應(yīng)用的主要障礙；博弈激勵(lì)

10、機(jī)制大多建立在“針?shù)h相對(duì)（TFT）”策略及其變種的基礎(chǔ)上，目前提出的方案多是各節(jié)點(diǎn)根據(jù)自己數(shù)據(jù)傳輸?shù)某晒β蕘?lái)調(diào)整為網(wǎng)絡(luò)中其它節(jié)點(diǎn)中繼分組的概率[1113]。這類(lèi)文獻(xiàn)重在納什均衡的證明，使用了較強(qiáng)的假設(shè)條件，距離實(shí)際應(yīng)用尚有一段距離。上述文獻(xiàn)提出的激勵(lì)機(jī)制大多是針對(duì)數(shù)據(jù)傳輸階段節(jié)點(diǎn)的自私行為而設(shè)計(jì)的，一個(gè)基本假設(shè)是節(jié)點(diǎn)稿件編號(hào)：076271的統(tǒng)計(jì)范圍為REQs1的那些記錄。30和10節(jié)點(diǎn)場(chǎng)景下ξ的分布如圖1所示?？梢钥闯?，兩個(gè)場(chǎng)景中ξTh