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

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

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

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

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

1 系統(tǒng)模型

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

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

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

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

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

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

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

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

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

2 懲罰機制

2.1 重復博弈的節(jié)點收益

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

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

2.2 孤立懲罰［7］機制

1)合作階段:初始時刻節(jié)點都合作。

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

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

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

2.3 孤立懲罰機制的收斂證明

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

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

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

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

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

2.4 普通懲罰［8］機制

1)合作階段:初始時刻節(jié)點都合作。

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

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

2.5 通用懲罰機制的收斂證明

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

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

化簡可得

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

所以有

當滿足上式的時候，自私的節(jié)點傾向于合作。

3 仿真分析

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

仿真參數(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é)點數(shù)目為5，仿真語言為MATLAB。這里需要說明的是，由于網(wǎng)絡中的節(jié)點是隨機生成的，每個節(jié)點的鄰居節(jié)點數(shù)目不確定，且每個自私節(jié)點當前時隙按照概率選擇不合作行為，由于自私節(jié)點是理性的，一旦選擇不合作行為就會持續(xù)下去，直到被鄰居節(jié)點發(fā)現(xiàn)。

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

實驗1:考察兩種機制隨著時隙的變化，其階段總收益的變化。

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

圖2 兩種機制階段總收益的變化

實驗2:考察兩種機制下自私節(jié)點和正常節(jié)點的平均收益對比。

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

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

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

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

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

對比圖3、圖4 可知兩種機制都對自私節(jié)點進行了懲罰，降低了自私節(jié)點的平均收益，但孤立懲罰機制的懲罰力度大于通用懲罰機制，因為其節(jié)點收益更少。

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

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

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

實驗4:考察參數(shù)變化對兩種機制下節(jié)點收益的影響。

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

1)懲罰時長s 的變化對兩種機制的影響。

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

圖7 懲罰時長對孤立懲罰機制的影響

圖8 懲罰時長對通用懲罰機制的影響

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

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

由圖9 可知，當m 不變時，k 的增加，會略微增加階段的總收益值，當k 不變時，m 的增加反而會降低節(jié)點的階段總收益值，這是因為孤立懲罰機制的孤立期不僅降低了自私節(jié)點的收益也降低了正常節(jié)點的收益的緣故。

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

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

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

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

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

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

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

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

4 結(jié)束語

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

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

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

［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］.通信學報，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é)點合作激勵策略［J］.電子學報，2010，38(2):327－332.

［7］陸音，石進，謝立.基于重復博弈的無線自組網(wǎng)絡協(xié)作增強模型［J］.軟件學報，2008，19(3):755－768.

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