基于重復(fù)博弈的Ad Hoc 網(wǎng)絡(luò)節(jié)點(diǎn)懲罰機(jī)制研究

譚 冕，何世彪，李映成，楊 剛，肖利麗

(重慶通信學(xué)院，重慶400035)

無線Ad Hoc 網(wǎng)絡(luò)的正常運(yùn)作，需要依靠節(jié)點(diǎn)間的合作才能保證數(shù)據(jù)的成功到達(dá)目的節(jié)點(diǎn)［1］。在通常情況下，理性的參與者受到自身資源的限制，將采取損害網(wǎng)絡(luò)性能的行為［2］。即便是只存在少量自私節(jié)點(diǎn)的網(wǎng)絡(luò)，其性能也會受損。

目前通過博弈論的方法來解決節(jié)點(diǎn)之間的合作問題已經(jīng)較為普遍。文獻(xiàn)［3］認(rèn)為重復(fù)博弈可以作為解決節(jié)點(diǎn)的合作問題，但設(shè)計(jì)的策略不會區(qū)分自私者或者合作者是否不具備合作的能力，故此提出了一種增強(qiáng)的基于聲譽(yù)值的針鋒相對模型，不僅依靠懲罰措施，還通過收益鼓勵節(jié)點(diǎn)參與轉(zhuǎn)發(fā)過程。文獻(xiàn)［4］提出了一種嚴(yán)厲的針鋒相對策略，讓自私節(jié)點(diǎn)的所有鄰居節(jié)點(diǎn)對其進(jìn)行懲罰，并通過懲罰機(jī)制參數(shù)的調(diào)整來觀察其對總體收益的影響。文獻(xiàn)［5］設(shè)計(jì)了一種基于重復(fù)博弈的全局懲罰模型，鄰居節(jié)點(diǎn)會通過降低自身的轉(zhuǎn)發(fā)概率來懲罰不合作節(jié)點(diǎn)。

上述機(jī)制存在實(shí)現(xiàn)較為復(fù)雜的缺點(diǎn)，本文從節(jié)點(diǎn)收益的角度，分析網(wǎng)絡(luò)是否處于一個(gè)收斂的穩(wěn)定狀態(tài)，并分析不同參數(shù)對兩種機(jī)制收斂的影響。有所區(qū)別的是，孤立懲罰機(jī)制存在一個(gè)孤立期和所有鄰居節(jié)點(diǎn)一起懲罰自私節(jié)點(diǎn)的不合作行為，而通用懲罰機(jī)制則是被不合作的節(jié)點(diǎn)對自私節(jié)點(diǎn)進(jìn)行懲罰，與其他鄰居節(jié)點(diǎn)無關(guān)。相同的是，兩種機(jī)制都能對節(jié)點(diǎn)的自私行為進(jìn)行懲罰，減少其收益。

1 系統(tǒng)模型

為方便分析起見，對本文建立的Ad Hoc 網(wǎng)絡(luò)作如下假設(shè)［6］:

1)當(dāng)前網(wǎng)絡(luò)G(V，E)由N 個(gè)理性的節(jié)點(diǎn)構(gòu)成，其中G 為連通圖，V 代表G 的節(jié)點(diǎn)，E 代表鏈路集合。相鄰節(jié)點(diǎn)間的鏈路(i，j)∈E，且為雙向。

2)整個(gè)系統(tǒng)時(shí)間由一系列離散的協(xié)作時(shí)隙t 構(gòu)成，時(shí)隙的長度足夠完成數(shù)據(jù)的傳輸。

3)用任意兩個(gè)相鄰節(jié)點(diǎn)為研究對象，如果一個(gè)網(wǎng)絡(luò)G 中任意兩個(gè)相鄰節(jié)點(diǎn)都呈現(xiàn)合作狀態(tài)，網(wǎng)絡(luò)整體就會呈現(xiàn)合作狀態(tài)。網(wǎng)絡(luò)中任意一組相鄰的節(jié)點(diǎn)對(i，j)，每個(gè)節(jié)點(diǎn)都有一定的數(shù)據(jù)需要對方轉(zhuǎn)發(fā)，也要為對方轉(zhuǎn)發(fā)一定的數(shù)據(jù)。

4)所有的數(shù)據(jù)長度一樣，如圖1 所示，如果節(jié)點(diǎn)i 的數(shù)據(jù)被鄰居節(jié)點(diǎn)j 轉(zhuǎn)發(fā)，那么就會得到b 的收益，而節(jié)點(diǎn)j 得到－c的收益(其中b，c 大于0，且b ＞c)。

5)網(wǎng)絡(luò)中不存在直接通信的情況，任何源、目節(jié)點(diǎn)之間的跳數(shù)大于1。

6)時(shí)隙內(nèi)的路由和連接性不變。

7)不考慮網(wǎng)絡(luò)故障的情況，出現(xiàn)不轉(zhuǎn)發(fā)的情況完全是因?yàn)楣?jié)點(diǎn)的自私行為。

圖1 節(jié)點(diǎn)轉(zhuǎn)發(fā)模型

2 懲罰機(jī)制

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

階段博弈的節(jié)點(diǎn)合作收益不理想，是因?yàn)楣?jié)點(diǎn)不會因?yàn)楫?dāng)前時(shí)隙的不合作行為而受到懲罰，當(dāng)階段博弈不斷進(jìn)行，就會構(gòu)成重復(fù)博弈。參與者會根據(jù)當(dāng)前博弈收益和將來可能的收益，選擇適合的決策。

根據(jù)重復(fù)博弈的原理，節(jié)點(diǎn)的收益會在每一個(gè)階段有δ(0 ＜δ ＜1)的折扣率，它代表的是節(jié)點(diǎn)的歷史行為對未來利益的影響，若其值越大則表示節(jié)點(diǎn)更加重視一個(gè)長期的利益，根據(jù)重復(fù)博弈中基于貼現(xiàn)準(zhǔn)則的收益評估方式，用Ui代表節(jié)點(diǎn)的收益

2.2 孤立懲罰［7］機(jī)制

1)合作階段:初始時(shí)刻節(jié)點(diǎn)都合作。

2)檢測階段:自私節(jié)點(diǎn)i 按照概率k 去合作，當(dāng)它出現(xiàn)不合作行為時(shí)，將會采取持續(xù)不合作的策略以獲得更大的收益。由于受到網(wǎng)絡(luò)信道、干擾等因素，其不合作行為不一定會被鄰居節(jié)點(diǎn)檢測到，如果被鄰居節(jié)點(diǎn)檢測到，即轉(zhuǎn)入孤立階段(被檢測到的概率為m)。

3)孤立階段:自私節(jié)點(diǎn)i 的所有鄰居節(jié)點(diǎn)拒絕轉(zhuǎn)發(fā)i 的數(shù)據(jù)持續(xù)r 個(gè)時(shí)隙(需要說明的是，由于本文僅研究相鄰節(jié)點(diǎn)對之間的關(guān)系，并未討論目的節(jié)點(diǎn)是否收到數(shù)據(jù)，所以孤立的意思為鄰居節(jié)點(diǎn)集體拒絕轉(zhuǎn)發(fā)i 的數(shù)據(jù))，由于理性的節(jié)點(diǎn)知道對方的策略，故節(jié)點(diǎn)i 在孤立階段最好的應(yīng)對策略就是不轉(zhuǎn)發(fā)數(shù)據(jù)。

4)懲罰階段:自私節(jié)點(diǎn)i 需要提供s 個(gè)時(shí)隙的無償轉(zhuǎn)發(fā)服務(wù)，而此時(shí)所有鄰居節(jié)點(diǎn)仍拒絕轉(zhuǎn)發(fā)A 的數(shù)據(jù)。懲罰階段結(jié)束后，節(jié)點(diǎn)i 再次回到網(wǎng)絡(luò)，其不合作行為被遺忘。

2.3 孤立懲罰機(jī)制的收斂證明

當(dāng)理性節(jié)點(diǎn)i 決定不合作，若作弊w 次后，才被它周圍的鄰居節(jié)點(diǎn)發(fā)現(xiàn)的概率為m(1－m)w－1，此時(shí)節(jié)點(diǎn)i 的作弊獲益為

由前文可知懲罰參數(shù)為(r，s)，則節(jié)點(diǎn)i 在作弊w 次后被發(fā)現(xiàn)，其自私行為所導(dǎo)致的收益的損失為

又因?yàn)楫?dāng)節(jié)點(diǎn)i 經(jīng)歷孤立期和懲罰期，重新加入網(wǎng)絡(luò)時(shí)，它面對的情況是相同的，令Si為當(dāng)前情景下節(jié)點(diǎn)i 選擇不合作行為能獲得的總收益現(xiàn)值期望，可如下所示

為了消除節(jié)點(diǎn)的自私性，需要讓節(jié)點(diǎn)持續(xù)合作的收益至少不小于作弊收益期望Si，即為

當(dāng)滿足上式的時(shí)候，自私的節(jié)點(diǎn)將更傾向于合作而非背叛。由于δ 和m ∈(0，1)，故式(7)對m 求導(dǎo)為負(fù)，當(dāng)m 越大時(shí)，式(7)將越發(fā)容易滿足，這跟常理相符:當(dāng)檢測概率數(shù)值較低的時(shí)候，懲罰機(jī)制的效率也偏低，作弊節(jié)點(diǎn)的收益也就越高。

2.4 普通懲罰［8］機(jī)制

1)合作階段:初始時(shí)刻節(jié)點(diǎn)都合作。

2)檢測階段:自私節(jié)點(diǎn)i 按照概率k 去合作，當(dāng)它對鄰居節(jié)點(diǎn)j 出現(xiàn)不合作行為時(shí)，將會采取持續(xù)不合作的策略以獲得更大的收益。由于受到網(wǎng)絡(luò)信道、干擾等因素，其不合作行為不一定會被鄰居節(jié)點(diǎn)檢測到，如果被鄰居節(jié)點(diǎn)j 檢測到，即轉(zhuǎn)入懲罰階段(被檢測到的概率為m)。

3)懲罰階段:自私節(jié)點(diǎn)i 需要為節(jié)點(diǎn)j 提供s 個(gè)(s=)時(shí)隙的無償轉(zhuǎn)發(fā)服務(wù)，而它的數(shù)據(jù)會被鄰居節(jié)點(diǎn)j 拒絕轉(zhuǎn)發(fā)。懲罰階段結(jié)束后，節(jié)點(diǎn)i 重新回到網(wǎng)絡(luò)，其不合作行為被遺忘。

2.5 通用懲罰機(jī)制的收斂證明

類似于孤立機(jī)制的收斂證明，節(jié)點(diǎn)之間都進(jìn)行合作的總收益為Vi，如下式所示

節(jié)點(diǎn)i 經(jīng)歷懲罰期后，重新加入網(wǎng)絡(luò)時(shí)，它面對的情況相同。假設(shè)節(jié)點(diǎn)i 因不合作行為而被懲罰后的總收益為，可如下所示

化簡可得

為了刺激節(jié)點(diǎn)的合作轉(zhuǎn)發(fā)，需要滿足下式

所以有

當(dāng)滿足上式的時(shí)候，自私的節(jié)點(diǎn)傾向于合作。

3 仿真分析

在理論分析后，筆者用仿真實(shí)驗(yàn)驗(yàn)證上述兩種機(jī)制的性質(zhì)。仿真實(shí)驗(yàn)共分4 組，分別考察懲罰機(jī)制是否穩(wěn)定、機(jī)制下的平均節(jié)點(diǎn)收益對比，貼現(xiàn)因子對網(wǎng)絡(luò)總收益的影響、參數(shù)變化對節(jié)點(diǎn)收益的影響。

仿真參數(shù)如下所示:b=6，c=2，Rm=100，Re=20，N=50，k=0.9，m=0.2，r=2，s=3，T=150，δ=0.9，自私節(jié)點(diǎn)數(shù)目為5，仿真語言為MATLAB。這里需要說明的是，由于網(wǎng)絡(luò)中的節(jié)點(diǎn)是隨機(jī)生成的，每個(gè)節(jié)點(diǎn)的鄰居節(jié)點(diǎn)數(shù)目不確定，且每個(gè)自私節(jié)點(diǎn)當(dāng)前時(shí)隙按照概率選擇不合作行為，由于自私節(jié)點(diǎn)是理性的，一旦選擇不合作行為就會持續(xù)下去，直到被鄰居節(jié)點(diǎn)發(fā)現(xiàn)。

另外仍需注明的是，以下實(shí)驗(yàn)為做了1 000 次蒙特卡洛仿真求其平均值得到的，雖然會有誤差，但仍可以揭示一些特性。

實(shí)驗(yàn)1:考察兩種機(jī)制隨著時(shí)隙的變化，其階段總收益的變化。

如圖2 所示，在初始的合作階段之后，兩種機(jī)制的階段總收益迅速下降，逐步穩(wěn)定下來，可以看出的是由于孤立懲罰機(jī)制多一個(gè)孤立期的存在，其收斂速度慢于通用懲罰機(jī)制，通用懲罰機(jī)制大概在第10 時(shí)隙收斂，而孤立懲罰機(jī)制在第40 個(gè)時(shí)隙附近接近穩(wěn)定狀態(tài)。

圖2 兩種機(jī)制階段總收益的變化

實(shí)驗(yàn)2:考察兩種機(jī)制下自私節(jié)點(diǎn)和正常節(jié)點(diǎn)的平均收益對比。

為方便比較起見，將完全合作機(jī)制引入，即正常節(jié)點(diǎn)采取完全合作的態(tài)度。由于自私節(jié)點(diǎn)數(shù)目僅為5 個(gè)，故其鄰居節(jié)點(diǎn)數(shù)目偏少，在本文中也意味著平均收益偏少，但不影響本實(shí)驗(yàn)的對比。圖3 為采取孤立懲罰機(jī)制，圖4 為采取通用懲罰機(jī)制，圖5 為完全合作機(jī)制。

圖3 孤立懲罰機(jī)制下的平均收益對比

圖4 通用懲罰機(jī)制下的平均收益對比

如圖5 所示，盡管初始正常節(jié)點(diǎn)的平均收益高于自私節(jié)點(diǎn)的收益，由于自私節(jié)點(diǎn)是按照概率來選擇不合作行為，但是一旦選擇不合作行為就會一直持續(xù)下去，而正常節(jié)點(diǎn)采取完全合作態(tài)度。4 個(gè)時(shí)隙后，自私節(jié)點(diǎn)的平均收益大于正常節(jié)點(diǎn)的平均收益。

圖5 完全合作機(jī)制下的平均收益對比

對比圖3、圖4 可知兩種機(jī)制都對自私節(jié)點(diǎn)進(jìn)行了懲罰，降低了自私節(jié)點(diǎn)的平均收益，但孤立懲罰機(jī)制的懲罰力度大于通用懲罰機(jī)制，因?yàn)槠涔?jié)點(diǎn)收益更少。

實(shí)驗(yàn)3:考察貼現(xiàn)因子δ 對兩種機(jī)制下的網(wǎng)絡(luò)總收益的影響。

由圖6 可知，貼現(xiàn)因子δ 對網(wǎng)絡(luò)總收益的影響是巨大的，當(dāng)δ=0.6 和δ=0.9 時(shí)，它們之間的收益差接近7 000。當(dāng)貼現(xiàn)因子較小的時(shí)候，兩種機(jī)制在網(wǎng)絡(luò)總收益上的差距不大，曲線幾乎靠在一起;當(dāng)貼現(xiàn)因子較大的時(shí)候，曲線有一定的區(qū)分度。

圖6 貼現(xiàn)因子對網(wǎng)絡(luò)總收益的影響

實(shí)驗(yàn)4:考察參數(shù)變化對兩種機(jī)制下節(jié)點(diǎn)收益的影響。

實(shí)驗(yàn)的具體參數(shù)變化為懲罰時(shí)長s、m－k 數(shù)值組合，r－s 數(shù)值組合，自私節(jié)點(diǎn)數(shù)目，共計(jì)4 種。

1)懲罰時(shí)長s 的變化對兩種機(jī)制的影響。

懲罰時(shí)長s 的大小代表著鄰居節(jié)點(diǎn)對自私節(jié)點(diǎn)懲罰時(shí)間的長短，從圖7 中可以得知，由于孤立懲罰機(jī)制是由孤立期和懲罰期構(gòu)成，所以懲罰時(shí)長單獨(dú)的變化對其收斂的具體數(shù)值影響微弱，但影響了曲線的收斂速度，周期越短，收斂速度越快。從圖8 可知，普通懲罰在穩(wěn)定后的收益值上對懲罰時(shí)長較為敏感，隨著s 的增加，收益值穩(wěn)定下降，收斂速度幾乎不變。

圖7 懲罰時(shí)長對孤立懲罰機(jī)制的影響

圖8 懲罰時(shí)長對通用懲罰機(jī)制的影響

2)m－k 數(shù)值組合對兩種機(jī)制的影響。

實(shí)驗(yàn)共選擇了5 組數(shù)據(jù)，分別是(0.3，0.7)，(0.4，0.7)，(0.3，0.8)，(0.4，0.8)，(0.5，0.8)。

由圖9 可知，當(dāng)m 不變時(shí)，k 的增加，會略微增加階段的總收益值，當(dāng)k 不變時(shí)，m 的增加反而會降低節(jié)點(diǎn)的階段總收益值，這是因?yàn)楣铝土P機(jī)制的孤立期不僅降低了自私節(jié)點(diǎn)的收益也降低了正常節(jié)點(diǎn)的收益的緣故。

圖9 m－k 組合對孤立懲罰機(jī)制的影響

由圖10 可知，對比圖9，當(dāng)m 不變的時(shí)候，k 的增加會讓整體數(shù)值有一個(gè)較大的增幅。當(dāng)k 不變的時(shí)候，m 數(shù)值的增加，會讓通用懲罰機(jī)制的階段總收益值上升，這點(diǎn)和孤立懲罰機(jī)制不同。

圖10 m－k 組合對通用懲罰機(jī)制的影響

3)r－s 數(shù)值組合對孤立懲罰機(jī)制的影響。

由于孤立期是孤立懲罰機(jī)制特有的，所以本實(shí)驗(yàn)只能考察對孤立懲罰機(jī)制的影響，共選取5 組數(shù)據(jù)，由圖11 可知，當(dāng)懲罰時(shí)長s 不變時(shí)，孤立時(shí)長r 的增加，使其收益減少。而當(dāng)孤立時(shí)長r 固定時(shí)，懲罰時(shí)長的增加對其影響主要作用于收斂的速度上，如數(shù)組(2，2)、(2，3)或者數(shù)組(4，4)、(4，6)所示，也驗(yàn)證了實(shí)驗(yàn)4 中1)的結(jié)論。

圖11 r－s 組合對孤立懲罰機(jī)制的影響

4)自私節(jié)點(diǎn)數(shù)目對兩種機(jī)制的影響。

從圖12 和圖13 可知，自私節(jié)點(diǎn)數(shù)目的增加，階段總收益穩(wěn)定下降。由于孤立期的存在使得圖12 的收益波動較大，最后仍趨于穩(wěn)定。與實(shí)驗(yàn)1、實(shí)驗(yàn)2 對應(yīng)的是，孤立懲罰機(jī)制的懲罰力度較通用懲罰機(jī)制更大。

4 結(jié)束語

本文中，節(jié)點(diǎn)由于具有理性而不愿消耗能量為其他節(jié)點(diǎn)轉(zhuǎn)發(fā)數(shù)據(jù)包，為此引入兩種懲罰機(jī)制，從兩種懲罰機(jī)制在仿真實(shí)驗(yàn)中的對比可以得到一些具體的結(jié)論，驗(yàn)證了理論分析。仿真結(jié)果證明，兩種機(jī)制有共同點(diǎn):對自私節(jié)點(diǎn)的不合作行為都會給與懲罰，自私節(jié)點(diǎn)個(gè)數(shù)的增加都會使得收益減小等;不同點(diǎn):孤立懲罰機(jī)制對自私節(jié)點(diǎn)的懲罰力度較大，對孤立期時(shí)長更為敏感。

圖12 自私節(jié)點(diǎn)數(shù)目對孤立懲罰機(jī)制的影響

圖13 自私節(jié)點(diǎn)數(shù)目對通用懲罰機(jī)制的影響

［1］DASH M，BALABANTARAY M. Routing problem:MANET and Ant colony algorithm［J］.IJRCCT，2014，3(9):954－960.

［2］RAMTIN A，HAKAMI V，DEHGHAN M. Computer Networks and Distributed Systems［M］.［S.l.］:Springer International Publishing，2014.

［3］AL－DHANHANI A，OTROK H，MIZOUNI R，et al. Enhanced reputation－based tit－for－tat strategy for collaborative social applications［C］//Proc.2013 International Conference on Interactive Collaborative Learning(ICL).［S.l.］:IEEE Press，2013:192－197.

［4］聞英友，趙博，趙宏.基于博弈理論的移動自組網(wǎng)激勵機(jī)制研究［J］.通信學(xué)報(bào)，2014，35(4):44－52.

［5］WANG K，WU M，DING C，et al.Game－based modeling of node cooperation in ad hoc networks［C］//Proc. Wireless and Optical Communications Conference(WOCC)，2010 19th Annual. ［S.l.］:IEEE Press，2010:1－5.

［6］王銳，朱青林，錢德沛，等. 一種可容錯的覆蓋網(wǎng)節(jié)點(diǎn)合作激勵策略［J］.電子學(xué)報(bào)，2010，38(2):327－332.

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

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