容遲網(wǎng)絡(luò)中基于演化博弈的合作行為

本文格式為Word版，下載可任意編輯——容遲網(wǎng)絡(luò)中基于演化博弈的合作行為

方案得以提出[2-7]。

其中，文獻(xiàn)[2]提出了合作行為促進(jìn)算法“針鋒相對”（TitForTat，TFT）。在該算法中，若本輪博弈對手采用背叛策略，那么在下一輪博弈節(jié)令點(diǎn)會(huì)采取背叛策略來報(bào)復(fù)對方；反之，那么以合作的方式賦予回報(bào)。

文獻(xiàn)[3]提出了基于信貸機(jī)制的DTN節(jié)點(diǎn)合作行為促進(jìn)機(jī)制。在該算法中，每當(dāng)節(jié)點(diǎn)作為中繼輔助轉(zhuǎn)發(fā)一條消息后，都可以得到相應(yīng)的報(bào)酬，而這些報(bào)酬可以在后期用來支付其他節(jié)點(diǎn)同自身合作的薪酬。

文獻(xiàn)[4]提出的合作聲譽(yù)（CollaborativeReputation，CORE）方案是基于節(jié)點(diǎn)聲譽(yù)的合作促進(jìn)機(jī)制，在該聲譽(yù)機(jī)制中，節(jié)點(diǎn)的合作與背叛行為會(huì)被其他節(jié)點(diǎn)評價(jià)：

節(jié)點(diǎn)容許合作就會(huì)獲得較好的聲譽(yù)；反之，那么會(huì)得到不好的聲譽(yù)。

這些聲譽(yù)不好的節(jié)點(diǎn)會(huì)被標(biāo)注自私的記號，然后在網(wǎng)絡(luò)中被逐步孤立。除了考慮轉(zhuǎn)發(fā)次數(shù)之外，文獻(xiàn)[5]還在信譽(yù)中考慮了消息轉(zhuǎn)發(fā)的告成率。為了獲得良好的信譽(yù)，節(jié)點(diǎn)需要不斷為其他節(jié)點(diǎn)供給忠誠守信的轉(zhuǎn)發(fā)服務(wù)，同時(shí)，忠誠節(jié)點(diǎn)也將優(yōu)先獲得服務(wù)。

文獻(xiàn)[6]從節(jié)點(diǎn)效用以及轉(zhuǎn)發(fā)消息價(jià)格兩方面因素啟程，提出了基于價(jià)格效用比的節(jié)點(diǎn)合作鼓舞機(jī)制，并針對以價(jià)格效用比為權(quán)值的有向圖，采用Dijkstra算法求解時(shí)延較短且價(jià)格效用較低的最優(yōu)路徑，該機(jī)制在確定程度上促進(jìn)了節(jié)點(diǎn)合作。

此外，文獻(xiàn)[7]結(jié)合網(wǎng)絡(luò)資源受限的特點(diǎn)，綜合考慮節(jié)點(diǎn)自身資源、擁有的虛擬貨幣以及消息屬性等因素對消息舉行定價(jià)，提出了基于買賣模型的節(jié)點(diǎn)鼓舞措施，既促進(jìn)了節(jié)點(diǎn)之間的合作，又制止了盲目合作導(dǎo)致網(wǎng)路性能退化的問題。

然而，需要指出的是，上述方案雖然針對節(jié)點(diǎn)的合作行為開展研究，但通常需要中央操縱節(jié)點(diǎn)對網(wǎng)絡(luò)舉行調(diào)配，實(shí)現(xiàn)起來較為繁雜；同時(shí)，均假設(shè)節(jié)點(diǎn)是完全理性的個(gè)體。DTN中節(jié)點(diǎn)消息的傳輸主要依靠節(jié)點(diǎn)間相互運(yùn)動(dòng)形成的通信機(jī)遇，不存在中央操縱節(jié)點(diǎn)。此外，就決策行為而言，要求節(jié)點(diǎn)完全理性較為困難，節(jié)點(diǎn)的理性程度通常對比有限且有犯錯(cuò)誤的可能，因此，這些合作機(jī)制的效果將會(huì)大打折扣。目前，演化博弈理論被認(rèn)為是研究分布式網(wǎng)絡(luò)中的有限理性節(jié)點(diǎn)合作行為的有效工具[8]。在演化過程中，節(jié)點(diǎn)不斷與周邊鄰居舉行博弈以更新自身的合作行為，不需要中央節(jié)點(diǎn)舉行操縱。由于更新規(guī)矩對于節(jié)點(diǎn)合作行為的涌現(xiàn)尤為重要，因此，一些基于演化博弈的更新規(guī)矩得以提出。Liu等[9]基于囚徒窘境模型提出了一種精心的策略更新規(guī)矩，在舉行策略選擇時(shí)采用隨機(jī)費(fèi)米（Fermi）規(guī)矩，并在概率選擇函數(shù)中引入精心因子。Li等[10]根據(jù)節(jié)點(diǎn)理性程度的不一致將節(jié)點(diǎn)分為遲鈍與敏銳兩類，在策略更新時(shí)分別采取不同的更新規(guī)矩。雖然已有的更新規(guī)矩在確定程度上促成了有限理性節(jié)點(diǎn)的合作行為，但是未考慮節(jié)點(diǎn)的社會(huì)屬性。節(jié)點(diǎn)設(shè)備的攜帶者通常為具有社會(huì)關(guān)系的人或者個(gè)體，相應(yīng)地，節(jié)點(diǎn)將會(huì)表現(xiàn)出確定的社會(huì)屬性。因此，在舉行策略更新時(shí)需要考慮節(jié)點(diǎn)的社會(huì)關(guān)系，這才貼近真實(shí)網(wǎng)絡(luò)中的行為傳播模式。此外，現(xiàn)有的節(jié)點(diǎn)合作行為促進(jìn)方案主要基于虛擬的網(wǎng)絡(luò)拓?fù)洳季郑簧婕罢鎸?shí)的動(dòng)態(tài)網(wǎng)絡(luò)；同時(shí)，這些合作機(jī)制未能有效地結(jié)合路由算法來議論網(wǎng)絡(luò)的性能。盡管文獻(xiàn)[11]基于實(shí)際的車載自組織網(wǎng)絡(luò)議論了節(jié)點(diǎn)行為的演化，也涉及到了路由算法，但同樣疏忽了鄰居節(jié)點(diǎn)的社會(huì)屬性對于合作行為涌現(xiàn)的重要作用。

為了制止現(xiàn)有研究工作的缺乏，將演化博弈引入DTN中，同時(shí)考慮節(jié)點(diǎn)社會(huì)屬性的影響，在囚徒窘境博弈模型的前提下設(shè)計(jì)基于社會(huì)權(quán)威性的策略更新規(guī)矩，并基于真實(shí)的動(dòng)態(tài)網(wǎng)絡(luò)拓?fù)洳季峙e行仿真測驗(yàn)，比較了所提出的策略更新規(guī)矩與隨機(jī)費(fèi)米規(guī)矩對合作行為的影響。進(jìn)一步地，在采用相遇與傳遞歷史的概率路由協(xié)議（ProbabilisticRoutingProtocolusingHistoryofEncountersandTransitivity，PROPHET）[12]的根基上，分析節(jié)點(diǎn)合作行為對網(wǎng)絡(luò)性能的影響。仿真結(jié)果說明，所提出的策略更新規(guī)矩能夠較好地促進(jìn)合作行為的涌現(xiàn)；同時(shí)，合作率的提高使得網(wǎng)絡(luò)中更多的節(jié)點(diǎn)容許扶助其他節(jié)點(diǎn)轉(zhuǎn)發(fā)消息，從而提升消息交付率等重要的網(wǎng)絡(luò)性能指標(biāo)。

2系統(tǒng)模型

網(wǎng)絡(luò)布局、博弈模型以及更新規(guī)矩是演化博弈的三大要素。

2.1網(wǎng)絡(luò)布局

現(xiàn)有涉及網(wǎng)絡(luò)合作行為的研究工作主要基于虛擬的規(guī)矩格子網(wǎng)絡(luò)或者靜態(tài)的無標(biāo)度網(wǎng)絡(luò)。與傳統(tǒng)的網(wǎng)絡(luò)布局不同，為了貼近真實(shí)的場景，本文主要使用三種真實(shí)的動(dòng)態(tài)網(wǎng)絡(luò)拓?fù)洳季?，即麻省理工學(xué)院（MassachusettsInstituteofTechnology，MIT）測驗(yàn)數(shù)據(jù)[13]、2022年計(jì)算機(jī)通信國際會(huì)議Infocom06數(shù)據(jù)[14]以及輪滑網(wǎng)（RollerbladingNetwork，RollerNet）數(shù)據(jù)[15]。

1）MIT數(shù)據(jù)來源于麻省理工學(xué)院多個(gè)持有智能手機(jī)Nokia6600的師生在9個(gè)月里的通信記錄，最終97個(gè)設(shè)備間的接觸信息被記錄。

2）Infocom06數(shù)據(jù)記錄了2022年計(jì)算機(jī)通信國際會(huì)議上78個(gè)參會(huì)人員攜帶的藍(lán)牙設(shè)備以及20個(gè)靜止設(shè)備之間持續(xù)3d的接觸信息。其中，20個(gè)靜止設(shè)備僅僅用來轉(zhuǎn)發(fā)消息，78個(gè)藍(lán)牙設(shè)備用于產(chǎn)生、轉(zhuǎn)發(fā)與接收消息。

3）RollerNet數(shù)據(jù)來源于2022年法國巴黎的一次集體活動(dòng)，大約2500個(gè)人參與了此次活動(dòng)。但是最終數(shù)據(jù)僅記錄了62個(gè)攜帶iMote設(shè)備的節(jié)點(diǎn)與1050個(gè)藍(lán)牙設(shè)備在3h的接觸信息。

2.2囚徒窘境博弈模型

常見的研究合作行為的演化博弈模型為囚徒窘境博弈。其主要思想是博弈僅僅發(fā)生在節(jié)點(diǎn)和它的鄰居之間，將具有連接關(guān)系的一對節(jié)點(diǎn)作為博弈的參與者，初始階段各個(gè)節(jié)點(diǎn)以確定的概率Pint選擇合作或者背叛。在每輪博弈中，各個(gè)節(jié)點(diǎn)依次與周邊的全體鄰居舉行博弈獲取收益，最終的收益為每次博弈的累積收益。若兩個(gè)節(jié)點(diǎn)都采取合作策略C，那么兩個(gè)節(jié)點(diǎn)均得到R的收益；若兩個(gè)節(jié)點(diǎn)都采取背叛策略D，那么兩個(gè)節(jié)點(diǎn)分別得到P的收益；若其中一個(gè)節(jié)點(diǎn)合作、另外一個(gè)背叛，那么合將得到收益S，背叛者得到收益T。對應(yīng)的博弈收益矩陣給出如下：

2.4基于社會(huì)權(quán)威性的更新規(guī)矩

在DTN中，節(jié)點(diǎn)設(shè)備的攜帶者通常為具有社會(huì)關(guān)系的人或者個(gè)體，相應(yīng)地，節(jié)點(diǎn)的行為更新也將表現(xiàn)出確定的社會(huì)特征，譬如：節(jié)點(diǎn)在舉行策略更新時(shí)通常更傾向于學(xué)習(xí)與模仿較為權(quán)威的鄰居節(jié)點(diǎn)的行為。在社交網(wǎng)絡(luò)分析中，通常采用“度中心性（DegreeCentrality，DC）”[16]來衡量節(jié)點(diǎn)在網(wǎng)絡(luò)中的重要性。在包含N個(gè)節(jié)點(diǎn)的網(wǎng)絡(luò)中，有Ki個(gè)鄰居的節(jié)點(diǎn)i的歸一化度中心性為：

3.2性能評價(jià)指標(biāo)

為了議論不同更新規(guī)矩對于網(wǎng)絡(luò)性能的影響，評價(jià)指標(biāo)如下：

1）合作率：定義為網(wǎng)絡(luò)中最終合作節(jié)點(diǎn)占整個(gè)網(wǎng)絡(luò)節(jié)點(diǎn)的百分比。合作率越高，意味著網(wǎng)絡(luò)中更多的節(jié)點(diǎn)可以為其他節(jié)點(diǎn)攜帶轉(zhuǎn)發(fā)消息。

2）交付率：定義為網(wǎng)絡(luò)中告成轉(zhuǎn)發(fā)的消息數(shù)與產(chǎn)生的總消息數(shù)的比值。較高的消息交付率意味著網(wǎng)絡(luò)中更多的消息能夠告成到達(dá)目的節(jié)點(diǎn)，這是評價(jià)路由算法性能優(yōu)劣的最重要指標(biāo)。

3）消息平均跳數(shù)：定義為消息轉(zhuǎn)發(fā)需要的總跳數(shù)與告成轉(zhuǎn)發(fā)的消息數(shù)的比值。消息的平均跳數(shù)越高，意味著告成轉(zhuǎn)發(fā)一條消息需要越多的中間節(jié)點(diǎn)輔助，這在確定程度上對應(yīng)著更多的網(wǎng)絡(luò)資源的需求。

4）網(wǎng)絡(luò)開銷：定義為告成轉(zhuǎn)發(fā)一條消息平均需要的消息副本數(shù)。網(wǎng)絡(luò)開銷是衡量網(wǎng)絡(luò)帶寬效率的一項(xiàng)指標(biāo)，開銷越大意味著消息副本越多，由于節(jié)點(diǎn)的存儲資源有限極易造成網(wǎng)絡(luò)傳輸性能的下降。

4測驗(yàn)結(jié)果與分析

采用機(jī)遇網(wǎng)絡(luò)環(huán)境（OpportunisticNetworkEnvironment，ONE）仿真器[19]在三種不同網(wǎng)絡(luò)拓?fù)洳季种斜容^了囚徒窘境模型下的兩種不同策略更新規(guī)矩對網(wǎng)絡(luò)合作行為的影響。進(jìn)一步地，基于PORPHET算法議論更新規(guī)矩對于網(wǎng)絡(luò)整體性能的影響。

4.1仿真參數(shù)配置

囚徒窘境模型中，參數(shù)的設(shè)置類似文獻(xiàn)[9]，取R=1，S=-1，T=1.5，P=0。在費(fèi)米更新規(guī)矩中，噪聲系數(shù)k=05，網(wǎng)絡(luò)初始合作率Pint=70%；此外，在PROPHET算法中，每隔200～300s產(chǎn)生一條消息，消息的大小為500kb～1Mb，節(jié)點(diǎn)的存儲空間均為10Mb；同時(shí)考慮到各個(gè)網(wǎng)絡(luò)對應(yīng)著不同的仿真時(shí)長，對于仿真時(shí)間較長的網(wǎng)絡(luò)，理應(yīng)允許更加寬松的消息生存時(shí)間。因此，對應(yīng)的仿真參數(shù)設(shè)置如表1所示。

4.2仿真結(jié)果

4.2.1三種網(wǎng)絡(luò)布局下的合作率

圖1給出了三種網(wǎng)絡(luò)拓?fù)湎碌木W(wǎng)絡(luò)合作率，此處的random代表隨機(jī)費(fèi)米更新規(guī)矩，maxdegree對應(yīng)著基于社會(huì)權(quán)威性的策略更新規(guī)矩。從圖1中可以看出，在不同的網(wǎng)絡(luò)布局下，maxdegree的合作率均優(yōu)于random。這是由于合作行為對比輕易在權(quán)威性較高的節(jié)點(diǎn)間傳播，相應(yīng)地，基于社會(huì)權(quán)威性選擇節(jié)點(diǎn)舉行策略更新，能夠使網(wǎng)絡(luò)達(dá)成較高的合作率。

4.2.2三種網(wǎng)絡(luò)布局下的交付率

圖2給出了三種網(wǎng)絡(luò)布局下的交付率。從圖2中可以看出，在不同的網(wǎng)絡(luò)布局下，maxdegree的交付率均高于random。這是由于采用社會(huì)權(quán)威的更新規(guī)矩后，maxdegree的網(wǎng)絡(luò)合作率遠(yuǎn)遠(yuǎn)高于random，網(wǎng)絡(luò)中有更多的節(jié)點(diǎn)容許扶助其他節(jié)點(diǎn)轉(zhuǎn)發(fā)消息，因此，更多的消息在生存周期內(nèi)被攜帶轉(zhuǎn)發(fā)，最終交付至目的節(jié)點(diǎn)，網(wǎng)絡(luò)的交付率隨之得到提升。

4.2.3三種網(wǎng)絡(luò)布局下的消息平均跳數(shù)

圖3給出了三種網(wǎng)絡(luò)布局下的消息平均跳數(shù)。從圖3中可以看出，MIT和RollerNet網(wǎng)絡(luò)布局下maxdegree的消息平均跳數(shù)均少于random。這是由于選擇社會(huì)權(quán)威性較高的節(jié)點(diǎn)舉行模仿學(xué)習(xí)后，網(wǎng)絡(luò)合作率的提升使得網(wǎng)絡(luò)中更多節(jié)點(diǎn)容許扶助轉(zhuǎn)發(fā)消息，大片面的消息經(jīng)過較少的中間節(jié)點(diǎn)便能告成到達(dá)目的節(jié)點(diǎn)，從而消息的轉(zhuǎn)發(fā)跳數(shù)將裁減；同時(shí)，由于Infocom06的網(wǎng)絡(luò)布局較密集，在該網(wǎng)絡(luò)中兩種更新規(guī)矩對應(yīng)的消息平均跳數(shù)相差不大。

4.2.4三種網(wǎng)絡(luò)布局下的網(wǎng)絡(luò)開銷

圖4給出了三種網(wǎng)絡(luò)拓?fù)洳季窒碌木W(wǎng)絡(luò)開銷。從圖4中可以看出，MIT網(wǎng)絡(luò)布局下maxdegree的開銷明顯低于random，而Infocom06與RollerNet網(wǎng)絡(luò)布局下maxdegree的開銷略高于random?？紤]到網(wǎng)絡(luò)合作率以及交付率是衡量網(wǎng)絡(luò)整體性能的重要指標(biāo)，既然這些指標(biāo)已經(jīng)得到較好的提升，因此，可以說明基于社會(huì)權(quán)威性的更新規(guī)矩優(yōu)于隨機(jī)的費(fèi)米更新規(guī)矩。

5結(jié)語

本文考慮DTN節(jié)點(diǎn)的社會(huì)屬性，在囚徒窘境博弈模型中，結(jié)合度中心性議論了節(jié)點(diǎn)的社會(huì)權(quán)威性，并提出了基于節(jié)點(diǎn)社會(huì)權(quán)威性的策略更新規(guī)矩。進(jìn)一步地，在三種真實(shí)的動(dòng)態(tài)網(wǎng)絡(luò)拓?fù)洳季种蟹抡鎸Ρ攘嘶谏鐣?huì)權(quán)威性的