一種基于重復(fù)博弈的可容錯(cuò)的ad hoc網(wǎng)絡(luò)節(jié)點(diǎn)合作策略

譚　冕，何世彪，宋　波，楊　剛，張　暉

(1.重慶通信學(xué)院，重慶 400035；2.后勤工程學(xué)院，重慶 401331)

?

一種基于重復(fù)博弈的可容錯(cuò)的ad hoc網(wǎng)絡(luò)節(jié)點(diǎn)合作策略

譚冕1，2，何世彪1，宋波1，楊剛1，張暉1

(1.重慶通信學(xué)院，重慶 400035；2.后勤工程學(xué)院，重慶 401331)

摘要：針對(duì)無(wú)線ad hoc網(wǎng)絡(luò)中節(jié)點(diǎn)在數(shù)據(jù)轉(zhuǎn)發(fā)階段可能的自私行為，利用博弈理論從靜態(tài)進(jìn)行分析，以相鄰節(jié)點(diǎn)對(duì)為研究對(duì)象，在重復(fù)博弈的情況下分析了針?shù)h相對(duì)策略的脆弱性，提出了一種改進(jìn)的針?shù)h相對(duì)策略，在理論上證明了改進(jìn)策略的激勵(lì)性。改進(jìn)策略可以容忍一定程度的網(wǎng)絡(luò)故障，并在故障發(fā)生后使節(jié)點(diǎn)重新回到合作狀態(tài)。仿真結(jié)果證明，改進(jìn)策略對(duì)網(wǎng)絡(luò)故障的容忍度較好，有效地促使節(jié)點(diǎn)合作，得到較高的網(wǎng)絡(luò)收益，同時(shí)也降低了自私節(jié)點(diǎn)的收益。

關(guān)鍵詞：無(wú)線ad hoc網(wǎng)絡(luò)；完美信息博弈；針?shù)h相對(duì)；自私節(jié)點(diǎn)；網(wǎng)絡(luò)故障

0引言

無(wú)線ad hoc網(wǎng)絡(luò)具有無(wú)中心、自組織、多跳等特點(diǎn)，數(shù)據(jù)的傳遞需要節(jié)點(diǎn)之間的合作才能保證成功。通常，理性的節(jié)點(diǎn)受到自身資源的限制，可能采取損害網(wǎng)絡(luò)性能的行為。顯而易見(jiàn)，即便只存在少量自私節(jié)點(diǎn)的無(wú)線自組網(wǎng)系統(tǒng)，也會(huì)極大降低網(wǎng)絡(luò)的整體性能。

對(duì)抑制節(jié)點(diǎn)的自私性，文獻(xiàn)[1]提出了嚴(yán)厲針?shù)h相對(duì)策略并分別用靜態(tài)和動(dòng)態(tài)博弈對(duì)節(jié)點(diǎn)的自私行為進(jìn)行建模，從群體的角度出發(fā)，用演化博弈模型解釋節(jié)點(diǎn)由于畏懼懲罰從自私行為轉(zhuǎn)向合作行為的過(guò)程。文獻(xiàn)[2]提出了一種基于重復(fù)博弈并通過(guò)激勵(lì)節(jié)點(diǎn)參與數(shù)據(jù)的轉(zhuǎn)發(fā)過(guò)程，進(jìn)而保證全局的高收益。通過(guò)仿真證明，文獻(xiàn)中的懲罰機(jī)制可以對(duì)節(jié)點(diǎn)起到激勵(lì)作用，并且通過(guò)對(duì)穩(wěn)定性的分析可以證明機(jī)制的有效性。文獻(xiàn)[3]提出了一種增強(qiáng)的基于信譽(yù)值的針?shù)h相對(duì)模型，經(jīng)過(guò)仿真證明可以鼓勵(lì)理性的節(jié)點(diǎn)參加合作，而不是只依靠懲罰措施。文獻(xiàn)[4]運(yùn)用博弈論的方法分析了網(wǎng)絡(luò)中自私節(jié)點(diǎn)之間的相互作用，并將合作的過(guò)程建模為進(jìn)行無(wú)限重復(fù)的博弈過(guò)程，用最差行為的針?shù)h相對(duì)(worst behavior tit-for-tat，WBTFT)策略來(lái)監(jiān)視其它節(jié)點(diǎn)的行為，對(duì)表現(xiàn)最差的節(jié)點(diǎn)采取措施。由于理性的節(jié)點(diǎn)恐懼懲罰措施，故策略有效地促使節(jié)點(diǎn)合作。文獻(xiàn)[5]構(gòu)建了一種基于P2P(peer to peer)網(wǎng)絡(luò)環(huán)境的增強(qiáng)的針?shù)h相對(duì)(enhancing tit-for-tat，ETFT)策略，節(jié)點(diǎn)通過(guò)執(zhí)行嚴(yán)格的針?shù)h相對(duì)策略懲罰自私節(jié)點(diǎn)。文獻(xiàn)[6-8]介紹了后文的對(duì)比策略，這些策略通過(guò)降低自私節(jié)點(diǎn)收益的角度抑制節(jié)點(diǎn)的自私性，維護(hù)網(wǎng)絡(luò)性能。

上述研究都是基于網(wǎng)絡(luò)無(wú)故障的情況，如果網(wǎng)絡(luò)故障引起了節(jié)點(diǎn)數(shù)據(jù)傳輸?shù)氖?，相鄰?jié)點(diǎn)間相互懲罰，會(huì)使它們進(jìn)入不穩(wěn)定的狀態(tài)，進(jìn)而降低網(wǎng)絡(luò)性能。為此本文對(duì)針?shù)h相對(duì)(tit-for-tat, TFT)策略進(jìn)行分析，提出一種能夠容忍不頻發(fā)的網(wǎng)絡(luò)故障和降低自私節(jié)點(diǎn)收益的改進(jìn)策略，在內(nèi)容上擁有判斷期和懲罰期，并在懲罰期結(jié)束后寬恕自私節(jié)點(diǎn)，盡可能地維護(hù)網(wǎng)絡(luò)的穩(wěn)定。

1系統(tǒng)模型

本文將著重研究相鄰節(jié)點(diǎn)間的關(guān)系，如果網(wǎng)絡(luò)中所有相鄰節(jié)點(diǎn)都處于合作狀態(tài)[7]，那么建立的網(wǎng)絡(luò)也處于合作的狀態(tài)，現(xiàn)做如下假設(shè)。

1)系統(tǒng)時(shí)間是由一系列的離散時(shí)隙t構(gòu)成，時(shí)隙的長(zhǎng)度足夠完成數(shù)據(jù)的傳輸，且時(shí)隙內(nèi)的路由和連接性不變。

2)當(dāng)前網(wǎng)絡(luò)中存在N個(gè)理性的節(jié)點(diǎn)，每個(gè)時(shí)隙各節(jié)點(diǎn)都要給它的相鄰節(jié)點(diǎn)發(fā)送一定數(shù)據(jù)，也要為其轉(zhuǎn)發(fā)一定的數(shù)據(jù)。

3) 所有的數(shù)據(jù)長(zhǎng)度一樣。如圖1所示，如果源節(jié)點(diǎn)i發(fā)給目的節(jié)點(diǎn)r的數(shù)據(jù)被鄰居節(jié)點(diǎn)j轉(zhuǎn)發(fā)，那么節(jié)點(diǎn)i就會(huì)得到b的收益，由于節(jié)點(diǎn)j轉(zhuǎn)發(fā)節(jié)點(diǎn)i的數(shù)據(jù)就會(huì)有-c的收益(其中b，c大于0，且b>c)。當(dāng)相鄰的節(jié)點(diǎn)對(duì)(i,j)進(jìn)行博弈時(shí)，若都選擇合作策略(即節(jié)點(diǎn)雙方的數(shù)據(jù)都被對(duì)方轉(zhuǎn)發(fā))，則收益為(b-c)。若都選擇不合作策略，則收益為0。當(dāng)節(jié)點(diǎn)i選擇合作策略，而節(jié)點(diǎn)j選擇不合作策略，可知節(jié)點(diǎn)i獲得-c的收益，而節(jié)點(diǎn)j獲得b的收益。

4)網(wǎng)絡(luò)是靜態(tài)的，因?yàn)榭疾斓氖窍噜徆?jié)點(diǎn)對(duì)的關(guān)系，所以網(wǎng)絡(luò)的動(dòng)態(tài)與否并不影響本文的研究。具體分析如下：假設(shè)網(wǎng)絡(luò)是動(dòng)態(tài)的，t1時(shí)隙相鄰節(jié)點(diǎn)對(duì)(i,j)處于各自的通信范圍內(nèi)，t2時(shí)隙不在通信范圍內(nèi)，t3時(shí)隙又處于通信范圍內(nèi)。但對(duì)節(jié)點(diǎn)i,j而言，它們的收益僅取決于彼此之間數(shù)據(jù)的交互。節(jié)點(diǎn)雙方的歷史策略都會(huì)被保存，并不會(huì)因?yàn)楣?jié)點(diǎn)的離開(kāi)與否而重新計(jì)算。為分析方便起見(jiàn)，特假設(shè)網(wǎng)絡(luò)是靜止的。

圖1　節(jié)點(diǎn)轉(zhuǎn)發(fā)模型Fig.1　Forwarding node model

2重復(fù)博弈的節(jié)點(diǎn)收益

由于單階段博弈的納什均衡解不理想，故引入重復(fù)博弈概念。節(jié)點(diǎn)歷史行為會(huì)對(duì)后續(xù)的博弈階段造成影響，所以相鄰節(jié)點(diǎn)對(duì)的多次交互將不是相互獨(dú)立的單階段博弈，而形成重復(fù)策略轉(zhuǎn)發(fā)博弈。

(1)

本文假設(shè)每個(gè)時(shí)隙相鄰節(jié)點(diǎn)之間都會(huì)完成一次數(shù)據(jù)交互，故按照時(shí)隙計(jì)算節(jié)點(diǎn)的收益。

當(dāng)相鄰節(jié)點(diǎn)完全合作，則節(jié)點(diǎn)i的收益為

(2)

3改進(jìn)的針?shù)h相對(duì)策略

3.1針?shù)h相對(duì)策略的脆弱性分析

針?shù)h相對(duì)策略是一個(gè)用于解決囚徒困境的有效策略，會(huì)根據(jù)博弈對(duì)手的策略來(lái)制定自己下一步的策略。

TFT策略的模型為

(3)

由于網(wǎng)絡(luò)存在的各種故障問(wèn)題而導(dǎo)致中繼節(jié)點(diǎn)轉(zhuǎn)發(fā)數(shù)據(jù)出現(xiàn)丟包現(xiàn)象，或由于節(jié)點(diǎn)的理性而選擇不合作策略，這將會(huì)影響節(jié)點(diǎn)之間的合作。例如節(jié)點(diǎn)i在第2個(gè)時(shí)隙出現(xiàn)了不合作，如(4)式所示，節(jié)點(diǎn)策略如同交替的數(shù)列一般，可能會(huì)引起網(wǎng)絡(luò)的混亂。其中C代表合作，D代表不合作。

(4)

如果節(jié)點(diǎn)i在第3個(gè)時(shí)隙又出現(xiàn)了不合作，那么節(jié)點(diǎn)之間就陷入了死循環(huán)，并大幅度降低節(jié)點(diǎn)的收益，對(duì)網(wǎng)絡(luò)造成極大的危害，具體如(5)式所示。

(5)

3.2MTTFT策略的描述

盡管TFT策略對(duì)自私節(jié)點(diǎn)有一定的威懾性，但其容錯(cuò)性較差，很可能因?yàn)楣收系脑蛴绊懙焦?jié)點(diǎn)的判斷，甚至對(duì)網(wǎng)絡(luò)造成不良影響。為改變這種情況，本文提出改良的可容錯(cuò)的針?shù)h相對(duì)(mend-tolerancetit-for-tat，MTTFT)策略，其具有一定的寬容性。執(zhí)行流程如下。

1)初始期：節(jié)點(diǎn)一開(kāi)始都是合作的狀態(tài)。

2)判斷期：期間內(nèi)需要回顧相應(yīng)節(jié)點(diǎn)的歷史策略記錄[9]。當(dāng)節(jié)點(diǎn)i的合作次數(shù)比不合作次數(shù)要多，則被認(rèn)為具有合作性。鄰居節(jié)點(diǎn)j選擇合作策略，否則節(jié)點(diǎn)j選擇不合作策略。

3)懲罰期：節(jié)點(diǎn)執(zhí)行Thd個(gè)時(shí)隙的TFT策略，并在策略開(kāi)始時(shí)選擇合作態(tài)度。

4)遺忘期：懲罰時(shí)期結(jié)束后，節(jié)點(diǎn)遺忘掉對(duì)方博弈節(jié)點(diǎn)的不合作行為，重新返回階段1)。

根據(jù)上述期間的描述，策略的寬容性主要體現(xiàn)在判斷期和遺忘期，它們的結(jié)合是對(duì)TFT策略容錯(cuò)性較差的改進(jìn)。

其偽代碼如下

begin

parametersinitialization；

forttoTdo

獲得當(dāng)前節(jié)點(diǎn)序號(hào)n；

forntoNdo

得到鄰居節(jié)點(diǎn)數(shù)nb并編號(hào)；

fornntonbdo

當(dāng)前鄰居節(jié)點(diǎn)序號(hào)nn；

獲得獲取鄰居節(jié)點(diǎn)之前時(shí)刻與當(dāng)前節(jié)點(diǎn)的合作狀態(tài)lstates；

ifdec=1then

if前k個(gè)時(shí)刻合作次數(shù)大于k/2then

階段計(jì)時(shí)器加1如果節(jié)點(diǎn)發(fā)生故障或者節(jié)點(diǎn)是自私節(jié)點(diǎn)且產(chǎn)生自私行為則不轉(zhuǎn)發(fā)，否則轉(zhuǎn)發(fā)；

else

進(jìn)入TFT階段，dec=2，清空階段計(jì)時(shí)器，若當(dāng)前節(jié)點(diǎn)發(fā)生了故障則不轉(zhuǎn)發(fā)，否則轉(zhuǎn)發(fā)；

endif

endif

ifdec=2then

if階段計(jì)時(shí)器th>=Thdthen

dec=1且清空階段計(jì)時(shí)器，節(jié)點(diǎn)發(fā)生了故障則不轉(zhuǎn)發(fā)，否則轉(zhuǎn)發(fā)；

else

階段計(jì)時(shí)器加1，節(jié)點(diǎn)發(fā)生故障或者自私行為或鄰居節(jié)點(diǎn)上個(gè)時(shí)隙不轉(zhuǎn)發(fā)則不轉(zhuǎn)發(fā)，否則轉(zhuǎn)發(fā)；

endif

endif

endfor

更新對(duì)當(dāng)前鄰居節(jié)點(diǎn)的合作狀態(tài)state；

endfor

計(jì)算網(wǎng)絡(luò)中各個(gè)節(jié)點(diǎn)的收益；

endfor

end

3.3改進(jìn)策略的激勵(lì)性

1)定理1(納什定理)：無(wú)論是混合策略還是純策略，每個(gè)有限的策略形式博弈都具有納什均衡。

此定理說(shuō)明所有有限策略空間的策略式博弈都有納什均衡的存在。由上述定理可知MTTFT策略存在納什均衡，證明見(jiàn)文獻(xiàn)[10]。

2)MTTFT策略中，在沒(méi)有網(wǎng)絡(luò)故障的存在，2個(gè)正常的節(jié)點(diǎn)由于沒(méi)有外在的激勵(lì)可以改變狀態(tài)，初始的合作狀態(tài)將會(huì)維持下去。

3)當(dāng)2個(gè)相鄰節(jié)點(diǎn)同時(shí)出現(xiàn)網(wǎng)絡(luò)故障的時(shí)候，由于進(jìn)入懲罰期節(jié)點(diǎn)的第一個(gè)時(shí)隙都被設(shè)置為合作的態(tài)度，并且同時(shí)處于針?shù)h相對(duì)的策略，那么節(jié)點(diǎn)雙方始終采取合作的態(tài)度直到懲罰期結(jié)束。即使在懲罰期仍有故障發(fā)生的時(shí)候，由于遺忘期的存在，在懲罰期間結(jié)束后雙方會(huì)恢復(fù)到初始合作狀態(tài)。

4)當(dāng)不考慮網(wǎng)絡(luò)故障時(shí)，僅討論自私節(jié)點(diǎn)利用策略的寬容性獲取額外利益的情況。假設(shè)k為奇數(shù)，即是說(shuō)自私節(jié)點(diǎn)最多可以采取(k+1)/2次的不合作行為就會(huì)進(jìn)入懲罰期，且當(dāng)自私節(jié)點(diǎn)了解策略并意圖取得最大收益時(shí)，必然是合作行為和自私行為交替出現(xiàn)。此時(shí)若連續(xù)2個(gè)自私行為出現(xiàn)的話，節(jié)點(diǎn)將進(jìn)入懲罰期，若需維持判斷期，誠(chéng)實(shí)節(jié)點(diǎn)的收益為

(6)

如果Uj≥0，那么節(jié)點(diǎn)的收益可以接受，故有(7)式成立：

(7)

5)當(dāng)節(jié)點(diǎn)進(jìn)入懲罰期的時(shí)候，可以用定理2說(shuō)明其穩(wěn)定性。

定理2[11]在無(wú)限重復(fù)的博弈中，如果一個(gè)自私節(jié)點(diǎn)不能通過(guò)單次的不合作行為來(lái)增加自身的效益(用U1SD表示)，那么它多次的不合作行為也不能增加其效益(用UnSD表示)，UC表示節(jié)點(diǎn)合作產(chǎn)生的效益，有

(8)

通過(guò)判斷背叛節(jié)點(diǎn)采取單次背叛行為的收益是否比合作的收益大，可知一個(gè)節(jié)點(diǎn)是否有偏離懲罰期策略的動(dòng)機(jī)。

根據(jù)前文假設(shè)，節(jié)點(diǎn)i單次背叛行為所獲得的利益為

(9)

根據(jù)(2)式，節(jié)點(diǎn)i合作所獲得的收益為

(10)

(11)

所以有

(12)

所以，理性的節(jié)點(diǎn)在爭(zhēng)鋒相對(duì)策略期間合作獲得的收益大于背離該策略，沒(méi)有單方面改變自身策略的動(dòng)機(jī)。綜上有MTTFT策略收斂，并趨向于一個(gè)穩(wěn)態(tài)，從而整個(gè)重復(fù)博弈處于納什均衡狀態(tài)。

4仿真分析

4.1對(duì)比策略

為更好地分析改進(jìn)策略，將以下5種策略作為對(duì)比策略。

1)針?shù)h相對(duì)策略(TFT)：前文已有相關(guān)介紹，不再贅述。

2)理想合作策略(IDEAL)：所有節(jié)點(diǎn)在任何時(shí)刻都會(huì)采取合作的態(tài)度，在仿真實(shí)驗(yàn)2中引入，觀察網(wǎng)絡(luò)中節(jié)點(diǎn)階段收益可能得到的理想最大值。在仿真實(shí)驗(yàn)4中引入，作為MTTFT策略對(duì)自私節(jié)點(diǎn)的懲罰的對(duì)比策略。

3)冷酷觸發(fā)策略(grimtrigger,GT)：在博弈中常用的觸發(fā)策略，GT策略將會(huì)孤立網(wǎng)絡(luò)中的自私節(jié)點(diǎn)，并極大地打擊存在的自私行為。當(dāng)與節(jié)點(diǎn)j博弈的節(jié)點(diǎn)i在第二個(gè)時(shí)隙選擇了不合作，那么節(jié)點(diǎn)j在余下的時(shí)隙都會(huì)選擇不合作。其表現(xiàn)為

(13)

4)慷慨的針?shù)h相對(duì)策略(generoustit-for-tat,GTFT)：在遭受背叛的時(shí)候，會(huì)有一個(gè)容忍時(shí)間，在容忍期之后會(huì)對(duì)背叛節(jié)點(diǎn)實(shí)施一段時(shí)間的TFT策略作為懲罰，懲罰期間結(jié)束之后選擇遺忘背叛行為，重新選擇合作。

5)寬恕的針?shù)h相對(duì)策略(tit-for-tatwithforgiveness,TFTF)：是在經(jīng)歷對(duì)方的一個(gè)不合作行為后，節(jié)點(diǎn)以一個(gè)小概率m(0

對(duì)比策略與改進(jìn)策略在相同的網(wǎng)絡(luò)環(huán)境中實(shí)現(xiàn)，并對(duì)網(wǎng)絡(luò)節(jié)點(diǎn)收益數(shù)值進(jìn)行比較。

4.2仿真實(shí)驗(yàn)及分析

理論分析后，將用仿真實(shí)驗(yàn)驗(yàn)證MTTFT策略的性質(zhì)。仿真實(shí)驗(yàn)共分為4組，分別考察故障率、網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)目、節(jié)點(diǎn)的自私性對(duì)網(wǎng)絡(luò)節(jié)點(diǎn)收益的影響。

本小節(jié)中的階段總收益為網(wǎng)絡(luò)中所有節(jié)點(diǎn)當(dāng)前時(shí)隙的收益之和。網(wǎng)絡(luò)總收益是將階段總收益代入(1)式進(jìn)行加權(quán)求和得到。節(jié)點(diǎn)的平均收益為當(dāng)前類(lèi)型的節(jié)點(diǎn)收益求和再除以當(dāng)前類(lèi)型的節(jié)點(diǎn)數(shù)。

仿真參數(shù)如下所示：b=8，c=2，Rm=100，Re=20，N=50，k=5，Thd=10，Th=20，m=0.1，δ=0.9，仿真語(yǔ)言為MATLAB。仿真實(shí)驗(yàn)的參數(shù)部分來(lái)自于文獻(xiàn)[12]，仿真場(chǎng)景設(shè)置為100m×100m及網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)為50等。b，c，δ等數(shù)值的取值需要滿足文中3.3節(jié)中的激勵(lì)證明條件和系統(tǒng)模型中的條件③，并參考了文獻(xiàn)[13]和文獻(xiàn)[14]的相關(guān)內(nèi)容。例如若滿足(7)式、(12)式，則b，c，δ的取值在這個(gè)范圍內(nèi)即可，具體賦值也可為b=6，c=2，δ=0.8。m，Thd等數(shù)值主要從文獻(xiàn)[15]中得到，檢測(cè)概率P=1來(lái)自文獻(xiàn)[16]。

需要說(shuō)明的是，為研究方便起見(jiàn)特假設(shè)只要節(jié)點(diǎn)出現(xiàn)不合作行為，就一定會(huì)被鄰居節(jié)點(diǎn)發(fā)現(xiàn)，即檢測(cè)率P=1。仿真實(shí)驗(yàn)1，2，3的網(wǎng)絡(luò)節(jié)點(diǎn)都是誠(chéng)實(shí)節(jié)點(diǎn)，網(wǎng)絡(luò)存在故障。仿真實(shí)驗(yàn)4的網(wǎng)絡(luò)節(jié)點(diǎn)既有自私節(jié)點(diǎn)也有誠(chéng)實(shí)節(jié)點(diǎn)，不考慮網(wǎng)絡(luò)故障。

實(shí)驗(yàn)1考察各種策略隨著故障率的變化，各自網(wǎng)絡(luò)總收益的對(duì)比。

此時(shí)故障率為1%到5%，T=500，統(tǒng)計(jì)五種策略在T個(gè)時(shí)隙內(nèi)的總收益。其結(jié)果如圖2所示，可知不同故障情況下執(zhí)行MTTFT策略和GTFT策略的節(jié)點(diǎn)仍可以保持良好的收益，而TFTF策略、TFT策略和GT策略會(huì)受到故障帶來(lái)的較大影響，尤其是GT策略。

圖2　各種策略在不同故障率下的總收益對(duì)比Fig.2　Total payoff comparison of various strategiesunder different failure rates

實(shí)驗(yàn)2考察不同策略下，故障率的變化對(duì)節(jié)點(diǎn)階段總收益的影響。

圖4　故障率為5%時(shí)策略的階段總收益對(duì)比Fig.4　Stage payoff comparison of various strategiesunder 5% failure rates

我們選擇一個(gè)較小故障1%和一個(gè)較大故障5%進(jìn)行對(duì)比，并追蹤150個(gè)時(shí)隙內(nèi)策略的階段收益。如圖3和圖4所示，面對(duì)不同的故障，MTTFT策略都能夠保持平穩(wěn)的收益，與理想值相差不大。而TFTF策略和GTFT策略會(huì)受到較大的波動(dòng)，但仍會(huì)趨于一個(gè)穩(wěn)定的數(shù)值，而TFT策略和GT策略由于沒(méi)有恢復(fù)機(jī)制，所以階段收益持續(xù)走低，并不能在一個(gè)具體的數(shù)值上保持相對(duì)穩(wěn)定的狀態(tài)。

實(shí)驗(yàn)3考察不同策略下，節(jié)點(diǎn)數(shù)目N的變化對(duì)網(wǎng)絡(luò)總收益的影響。

此時(shí)故障率為1%，節(jié)點(diǎn)數(shù)目分別為30，40，50，T=500。為了較好地觀察結(jié)果，設(shè)定通信半徑Re=40，并統(tǒng)計(jì)五種策略在時(shí)隙內(nèi)的總收益。其結(jié)果如圖5所示，隨著總節(jié)點(diǎn)數(shù)目的增加，網(wǎng)絡(luò)總收益都隨之增加，但其總收益的數(shù)值大小仍是MTTFT>GTFT>TFTF>TFT>GT。

實(shí)驗(yàn)4考察不同合作概率下，MTTFT策略對(duì)自私節(jié)點(diǎn)的懲罰度，并引入IDEAL策略進(jìn)行對(duì)比。

實(shí)驗(yàn)1，2，3都為網(wǎng)絡(luò)節(jié)點(diǎn)處于故障的情況下討論的，證明了MTTFT策略對(duì)故障有較好的寬容性，但自私節(jié)點(diǎn)可能會(huì)利用這種寬容性來(lái)獲得不正當(dāng)收益。為了更好地觀察MTTFT策略對(duì)自私節(jié)點(diǎn)自私性的抵抗能力，設(shè)置T=100，自私節(jié)點(diǎn)數(shù)量為15，自私節(jié)點(diǎn)的合作概率為0.7。圖6的節(jié)點(diǎn)執(zhí)行MTTFT策略，而圖7為節(jié)點(diǎn)采用理想合作策略的對(duì)比圖。對(duì)比圖6和圖7可知執(zhí)行MTTFT策略的節(jié)點(diǎn)會(huì)對(duì)自私節(jié)點(diǎn)進(jìn)行懲罰，降低其平均收益。

圖5　節(jié)點(diǎn)數(shù)目變化對(duì)總收益的影響Fig.5　Total payoff comparison under differentnodes’ numbers

圖6　自私節(jié)點(diǎn)和誠(chéng)實(shí)節(jié)點(diǎn)的平均收益對(duì)比1Fig.6　Comparison of average payoff betweenthe selfish nodes and honest nodes 1

圖7　自私節(jié)點(diǎn)和誠(chéng)實(shí)節(jié)點(diǎn)的平均收益對(duì)比2Fig.7　Comparison of average payoff betweenthe selfish nodes and honest nodes 2

5結(jié)束語(yǔ)

Ad hoc網(wǎng)絡(luò)是未來(lái)無(wú)線通信發(fā)展的重點(diǎn)[17]，不需要昂貴的基礎(chǔ)設(shè)施就能自適應(yīng)連接，但缺乏中心控制也就意味著用戶的個(gè)體行為將會(huì)對(duì)網(wǎng)絡(luò)性能造成深遠(yuǎn)的影響。本文基于傳統(tǒng)的TFT策略提出了改進(jìn)，并通過(guò)仿真實(shí)驗(yàn)從網(wǎng)絡(luò)節(jié)點(diǎn)收益的角度來(lái)證明MTTFT策略具有一定的容錯(cuò)性，不會(huì)因?yàn)榕紶柕墓收蠈?dǎo)致節(jié)點(diǎn)間出現(xiàn)死循環(huán)的情況，并在一定程度上遏制了自私節(jié)點(diǎn)的自私性，優(yōu)于其它對(duì)比策略。

參考文獻(xiàn)：

[1]聞?dòng)⒂? 趙博, 趙宏. 基于博弈理論的移動(dòng)自組網(wǎng)激勵(lì)機(jī)制研究[J]. 通信學(xué)報(bào), 2014, 35(4): 44-52.

WEN Yingyou, ZHAO Bo, ZHAO Hong. Study on game-based incentive mechanism of mobile ad hoc network[J]. Journal on Communications, 2014, 35(4): 44-52.

[2]郭晶晶, 馬建峰, 李琦, 等. 基于博弈論的移動(dòng)自組織網(wǎng)絡(luò)的信任管理方法[J]. 通信學(xué)報(bào), 2014, 35(11): 50-58.GUO Jingjing, MA Jianfeng, LI Qi, et al. Game theory based trust management method for mobile ad hoc networks[J]. Journal on Communications, 2014, 35(11): 50-58.

[3]Al D A, OTROK H, MIZOUNI R, et al. Enhanced Reputation-based Tit-for-Tat Strategy for Collaborative Social Applications [C] //Interactive Collaborative Learning, 2013 International Conference on.[s.l.]: IEEE, 2013: 192-197.

[4]NIU B,ZHAO H V,JIANG H.A cooperation stimulation strategy in wireless multicast networks[J].Signal Processing,IEEE Transactions on,2011,59(5):2355-2369.

[5]PENG D, LIU W, LIN C, et al. Enhancing tit-for-tat strategy to cope with free-riding in unreliable p2p networks [C] //Internet and Web Applications and Services, Third International Conference on. New York:IEEE, 2008: 336-341.

[6]徐占洋. 基于博弈激勵(lì)的移動(dòng)自組織網(wǎng)絡(luò)關(guān)鍵技術(shù)研究[D]. 南京：南京郵電大學(xué), 2013.

XU Zhanyang. Key Thchnology Research in Mobile Ad Hoc Network Base on Game Theory[D]. Nanjing: Nanjing University of Posts and Telecommunications, 2013.

[7]王銳,朱青林,錢(qián)德沛,等.一種可容錯(cuò)的覆蓋網(wǎng)節(jié)點(diǎn)合作激勵(lì)策略[J].電子學(xué)報(bào),2010,38(2):327-332.

WANG Rui, ZHU Qinglin, QIAN Depei, et al. A Faul-t Tolerant Cooperation Incentive Strategy for Overlay Network Nodes[J]. ACTA ELECTRONICA SINICA, 2010, 38(2): 327-332.

[8]SUN L, ZHANG L, WANG Y. The research on tit-for-tat strategy in network evolution [C] //Control and Decision Conference, 2009. CCDC'09. Chinese:IEEE, 2009: 4190-4194.

[9]AL D A, MIZOUNI R, OTROK H, et al. Game theoretical analysis of collaborative social applications [C] //Collaborative Computing: Networking Applications and Worksharing, 2012 8th intemational Conference on. Pittsburgn: IEEE, 2012: 628-634.

[10] MACKENZIE A B,DASILVA L A.Game theory for wireless engineers[M].New York：Morgan and Claypool, 2006.[11] TOOTAGHAJ D Z, FARHAT F, PAKRAVAN M R, et al. Game-theoretic approach to mitigate packet dropping in wireless Ad-hoc networks [C] //Consumer Communications and Networking Conference(CCNC). New York: IEEE, 2011: 163-165.

[12] 張健. 基于博弈論的移動(dòng) Ad Hoc 網(wǎng)絡(luò)節(jié)點(diǎn)合作策略研究[D]. 杭州：浙江工業(yè)大學(xué), 2013.

ZHANG Jian. Research on Mobile Ad Hoc Network Node Cooperation Strategy Based on Game Theory[D]. Hangzhou: Zhejiang University of Technology, 2013.

[13] 孫玉星, 趙燕飛, 李婭, 等. 基于概率博弈的無(wú)線自組網(wǎng)信任推薦激勵(lì)策略的研究[J]. 計(jì)算機(jī)科學(xué), 2011, 38(4): 65-71.

SUN Yuxing, ZHAO Yanfei, LI Ya, et al. On Incentive Strategies for Trust Recommendations in Wireless Ad Hoc Networks with Probability Game[J]. Computer Science, 2011, 38(4): 65-71.

[14] 王博, 黃傳河, 楊文忠, 等. Ad Hoc 網(wǎng)絡(luò)中基于懲罰機(jī)制的激勵(lì)合作轉(zhuǎn)發(fā)模型[J]. 計(jì)算機(jī)研究與發(fā)展, 2011, 48(3): 398-406.

WANG Bo, HUANG Chuanhe, YANG Wenzhong, et al. An Incentive-Cooperative Forwarding Model Based on Punishment Mechanism in Wireless Ad Hoc Networks[J]. Journal of Computer Research and Development, 2011, 48(3): 398-406.

[15] 何世彪，吳樂(lè)華，胡中豫.無(wú)線網(wǎng)絡(luò)中的博弈論[M].北

京：國(guó)防工業(yè)出版社，2016.

HE Shibiao, WU Lehua, HU Zhongyu. Game Theory for Wireless Networks[M]. Beijing: National Defense Industry Press, 2016.

[16] 陸音, 石進(jìn), 謝立. 基于重復(fù)博弈的無(wú)線自組網(wǎng)絡(luò)協(xié)作增強(qiáng)模型[J]. 軟件學(xué)報(bào), 2008, 19(3): 755-768.

LU Yin, SHI Jin, XIE Li. Repeated-Game Modeling of Cooperation Enforcement in Wireless Ad Hoc Network[J]. Journal of Software, 2008, 19(3): 755-768.

[17] 聶志,劉靜,甘小鶯, 等. 移動(dòng)Ad Hoc網(wǎng)絡(luò)中機(jī)會(huì)路由轉(zhuǎn)發(fā)策略的研究[J]. 重慶郵電大學(xué)學(xué)報(bào)：自然科學(xué)版,2010,(4):421-425，449.

NIE Zhi, LIU Jing, GAN Xiaoying, et al. A relay node selection technique for opportunistic routing in mobile Ad Hoc networks[J]. Journal of Chongqing University of Posts and Telecommunications：Natural Science Edition,2010,04:421-425，449.

A fault-tolerant node cooperation strategy of ad hoc network based on repeated game

TAN Mian1,2, HE Shibiao1, SONG Bo1, YANG Gang1, ZHANG Hui1

(1.Chongqing Communication Institute, Chongqing 400035, P.R. China; 2.Logistical Engineering Institute, Chongqing 401331, P.R. China)

Abstract:According to possible selfish behaviors of wireless ad hoc network nodes showed during the process of data transforming and analyzing from static state based on game theory, this paper regards neighboring nodes as the researched object, and analyzes the fragility of Tit-for-Tat strategy in the repeated game. This paper proposes an improved Tit-for-Tat strategy, and proves incentive of improved strategy theoretically. This improved strategy can tolerate a certain degree of network failure, and can restart nodes into cooperation status again after failure happened. The simulation results show that the improved strategy has a better network fault tolerance compared with several other strategies, prompts node cooperation more effectively, gets higher node payoffs, reduces the interests of selfish nodes.

Keywords：wireless ad hoc network； perfect game theory；tit-for-tat；selfish nodes；network failure

DOI：10.3979/j.issn.1673-825X.2016.03.010

收稿日期：2015-04-28

修訂日期：2016-06-07通訊作者：譚冕304365049@qq.com

基金項(xiàng)目：重慶市自然科學(xué)基金資助項(xiàng)目(cstc2014jcyjA40051)

Foundation Item：The Natural Science Foundation Project of CQ CSTC(cstc2014jcyjA40051)

中圖分類(lèi)號(hào)：TN92

文獻(xiàn)標(biāo)志碼：A

文章編號(hào)：1673-825X(2016)03-0342-07

作者簡(jiǎn)介：

譚冕(1989-)，男，重慶人，博士研究生。主要研究方向無(wú)線自組網(wǎng)。E-mail:304365049@qq.com。

(編輯：張誠(chéng))