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

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

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

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

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

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

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

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

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

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

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

為了制止現(xiàn)有研究工作的缺乏，將演化博弈引入DTN中，同時考慮節(jié)點社會屬性的影響，在囚徒窘境博弈模型的前提下設(shè)計基于社會權(quán)威性的策略更新規(guī)矩，并基于真實的動態(tài)網(wǎng)絡(luò)拓?fù)洳季峙e行仿真測驗，比較了所提出的策略更新規(guī)矩與隨機費米規(guī)矩對合作行為的影響。進一步地，在采用相遇與傳遞歷史的概率路由協(xié)議（ProbabilisticRoutingProtocolusingHistoryofEncountersandTransitivity，PROPHET）[12]的根基上，分析節(jié)點合作行為對網(wǎng)絡(luò)性能的影響。仿真結(jié)果說明，所提出的策略更新規(guī)矩能夠較好地促進合作行為的涌現(xiàn)；同時，合作率的提高使得網(wǎng)絡(luò)中更多的節(jié)點容許扶助其他節(jié)點轉(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ò)布局不同，為了貼近真實的場景，本文主要使用三種真實的動態(tài)網(wǎng)絡(luò)拓?fù)洳季郑绰槭±砉W(xué)院（MassachusettsInstituteofTechnology，MIT）測驗數(shù)據(jù)[13]、2022年計算機通信國際會議Infocom06數(shù)據(jù)[14]以及輪滑網(wǎng)（RollerbladingNetwork，RollerNet）數(shù)據(jù)[15]。

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

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

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

2.2囚徒窘境博弈模型

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

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

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

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

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

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

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

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

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

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

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

4.1仿真參數(shù)配置

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

4.2仿真結(jié)果

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

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

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

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

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

圖3給出了三種網(wǎng)絡(luò)布局下的消息平均跳數(shù)。從圖3中可以看出，MIT和RollerNet網(wǎng)絡(luò)布局下maxdegree的消息平均跳數(shù)均少于random。這是由于選擇社會權(quán)威性較高的節(jié)點舉行模仿學(xué)習(xí)后，網(wǎng)絡(luò)合作率的提升使得網(wǎng)絡(luò)中更多節(jié)點容許扶助轉(zhuǎn)發(fā)消息，大片面的消息經(jīng)過較少的中間節(jié)點便能告成到達目的節(jié)點，從而消息的轉(zhuǎn)發(fā)跳數(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)得到較好的提升，因此，可以說明基于社會權(quán)威性的更新規(guī)矩優(yōu)于隨機的費米更新規(guī)矩。

5結(jié)語

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