基于重復博弈的Ad Hoc 網絡節點懲罰機制研究

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

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

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

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

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

1 系統模型

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

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

2)整個系統時間由一系列離散的協作時隙t 構成，時隙的長度足夠完成數據的傳輸。

3)用任意兩個相鄰節點為研究對象，如果一個網絡G 中任意兩個相鄰節點都呈現合作狀態，網絡整體就會呈現合作狀態。網絡中任意一組相鄰的節點對(i，j)，每個節點都有一定的數據需要對方轉發，也要為對方轉發一定的數據。

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

5)網絡中不存在直接通信的情況，任何源、目節點之間的跳數大于1。

6)時隙內的路由和連接性不變。

7)不考慮網絡故障的情況，出現不轉發的情況完全是因為節點的自私行為。

圖1 節點轉發模型

2 懲罰機制

2.1 重復博弈的節點收益

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

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

2.2 孤立懲罰［7］機制

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

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

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

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

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

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

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

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

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

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

2.4 普通懲罰［8］機制

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

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

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

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

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

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

化簡可得

為了刺激節點的合作轉發，需要滿足下式

所以有

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

3 仿真分析

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

仿真參數如下所示:b=6，c=2，Rm=100，Re=20，N=50，k=0.9，m=0.2，r=2，s=3，T=150，δ=0.9，自私節點數目為5，仿真語言為MATLAB。這里需要說明的是，由于網絡中的節點是隨機生成的，每個節點的鄰居節點數目不確定，且每個自私節點當前時隙按照概率選擇不合作行為，由于自私節點是理性的，一旦選擇不合作行為就會持續下去，直到被鄰居節點發現。

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

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

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

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

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

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

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

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

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

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

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

實驗3:考察貼現因子δ 對兩種機制下的網絡總收益的影響。

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

圖6 貼現因子對網絡總收益的影響

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

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

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

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

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

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

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

實驗共選擇了5 組數據，分別是(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 的增加反而會降低節點的階段總收益值，這是因為孤立懲罰機制的孤立期不僅降低了自私節點的收益也降低了正常節點的收益的緣故。

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

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

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

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

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

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

4)自私節點數目對兩種機制的影響。

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

4 結束語

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

圖12 自私節點數目對孤立懲罰機制的影響

圖13 自私節點數目對通用懲罰機制的影響

［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］聞英友，趙博，趙宏.基于博弈理論的移動自組網激勵機制研究［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］王銳，朱青林，錢德沛，等. 一種可容錯的覆蓋網節點合作激勵策略［J］.電子學報，2010，38(2):327－332.

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

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