無線網絡的博弈論應用

徐許亮 張明銘

摘 要： 本文針對無線網絡中自私節點的不協作行為，結合博弈理論建立了無線網絡的合理性假設，在此基礎上提出了一個促使自私節點協作納什均衡的分析框架。

關鍵詞： 無線網絡 博弈論 節點協作

無線網絡是由一組帶有無線收發裝置的自主性設備通過無線信道連接而成的自治系統。網絡中的路由發現和分組轉發等服務不是通過專用的路由設備完成，而是通過普通節點（PDA、筆記本電腦、傳感器、車載電臺等設備）的共同協作來完成。由于無線節點的功率有限，通信半徑較小，因此與傳輸范圍之外的節點通信時，需要中間節點的轉發。但是，在沒有統一管理機構控制的無線網絡中，節點間的協作卻不能保證。如民用型無線網絡，在這樣的網絡中，每個用戶獨自控制設備（即網絡中的節點），不受他人的管理與監督；并且這樣的網絡一般沒有一個共同的目標或任務[1]。此外，節點協助其他節點時要消耗自己有限的資源，如電源能量、CPU處理時間等，因此一些節點為了保存更多的資源來滿足自身通信的需求，它們會拒絕提供路由發現服務、拒絕轉發其他節點的分組等。

因此，如何激勵無線網絡中的自私節點協作是一個需待解決的問題。博弈論主要研究公式化了的激勵結構間的相互作用，是研究具有斗爭或競爭性質現象的數學理論和方法。因此利用博弈理論的研究無線網絡中自私節點的協作及其激勵方法是一種行之有效的辦法[2]。

一、無線網絡的合理性假設

利用博弈理論對無線網絡中自私節點的協作行為進行研究，首先要建立無線網絡的博弈理論模型，但是在建立模型之前，還要對無線網絡進行適當的理論分析與處理。因此本文首先建立無線網絡如下合理性假設：

（1）網絡中存在n個節點，且都是理性且自私的。（理性且自私是指節點不會自愿提供分組轉發等服務，并始終將能夠最大化自身效益的策略作為最佳策略）；

（2）時間T被分隔成為時間槽T1，T2，T3，...，Tn，節點在每個時間槽內完成一次會話；

（3）無線網絡是一個多跳網絡，即不在彼此的傳輸范圍內的兩個節點進行通信時，需要借助其他節點的轉發；

（4）在整個會話過程中路由沒有失效，節點也沒有出現故障；

（5）所有會話中，分組最終到達目的節點所經過的平均跳數為M，整個網絡的轉發負載是均衡分布的；

（6）任何節點在接收和發送（包括轉發）分組時都要消耗有限的資源。與之相比，節點在處理分組時的資源消耗可以忽略不計；

（7）所有分組長度相同，節點發送一個分組時所消耗的資源相等，節點接收一個分組時所消耗的資源相等。

二、節點協作納什均衡的分析框架

根據以上的假設，我們可以將任何兩個節點之間的一次會話看做是一次博弈。如果兩個節點之間僅僅進行一次會話，我們稱之為一次性博弈，如果兩個節點之間進行兩次或兩次以上的會話，我們稱之為重復博弈。在重復博弈中，任何一個節點做出的策略選擇都會影響博弈的結果，同時也會對下次的會話產生直接的影響。

目前，針對無線網絡中節點協作的研究大致可分為外在、內在兩種角度。前者通過引入虛擬貨幣和聲譽值等外部機制來迫使節點協作，而后者則通過分析和利用利益驅動的本質對節點決策行為的影響來引導合作[3]。無線網絡中，自私節點的不協作行為雖然能夠增加自己的生存時間，卻大大降低了網絡的性能及網絡壽命。因此，無線網絡中自私節點之間一次性博弈的結果與囚徒困境的納什均衡相似，而這不是一個全局滿意的結果。因為重復博弈可以使囚徒擺脫相互不合作的困境，實現一個令人滿意的納什均衡，所以對自私節點重復博弈的納什均衡進行研究，能夠從內在的角度出發在本質上提高無線網絡中自私節點的協作性。

用博弈論研究無線網絡中節點協作的納什均衡時，必須先建立無線網絡的相關模型，然后利用模型進行相應的分析。而一個完善的節點協作的納什均衡分析框架應該包含以下幾個部分：

（1）分析單階段博弈中節點協作的納什均衡；

（2）分析重復博弈中采用經典策略（包括冷酷策略、禮尚往來策略、單步觸發策略等）時節點協作的納什均衡及條件；

（3）對重復博弈中不同策略的納什均衡條件進行比較。

首先，利用博弈論知識對第一部分進行了研究，建立了無線網絡中包轉發策略的分析模型，對合作和非合作策略下取得納什均衡的條件進行了分析，結果表明在非協同性的網絡中需要增加激勵機制以加強節點協作；其次，提出了一個改進型的禮尚往來策略，通過分析得出自私節點采用此策略時系統可以達到一個相對穩定的納什均衡點；最后，分析了單階段博弈和重復博弈中采用經典策略時節點協作的納什均衡及其條件。

綜合以上內容，可得出一個比較完善的納什均衡分析框架，具體描述如下：首先要提出一個節點協作的博弈理論模型，利用該模型對單階段博弈（即一次性博弈）中節點協作的納什均衡進行一次分析；其次分別構建重復博弈中節點采取冷酷策略、禮尚往來策略、單步觸發策略和完全協作策略時的概率模型，接著分析重復博弈中節點采用以上幾個策略時協作的納什均衡條件；最后再對不同策略的納什均衡條件進行比較，得到重復博弈中激勵自私節點協作的最佳策略。

參考文獻：

[1]L. Buttyan and J.-P. Hubaux，Stimulating Cooperation in Self-organizing Mobile Ad Hoc Networks[J].In ACM/Kluwer Mobile Networks and Applications，vol.8，no.5，pp.579-592，Oct. 2003.

[2]Seredynski， M&Bouvry P.Evolution of cooperation in Ad Hoc Networks under Game Theoretic Model[C].Proceedings of the 4th ACM international workshop on Mobility management and wireless access.Terromolinos，Sqain，2006：126-130.

[3]陸音，石進等.基于重復博弈的無線自組網絡協作增強模型[J].軟件學報，19（3），2008：756-768.