無(wú)線網(wǎng)絡(luò)的博弈論應(yīng)用

徐許亮 張明銘

摘 要： 本文針對(duì)無(wú)線網(wǎng)絡(luò)中自私節(jié)點(diǎn)的不協(xié)作行為，結(jié)合博弈理論建立了無(wú)線網(wǎng)絡(luò)的合理性假設(shè)，在此基礎(chǔ)上提出了一個(gè)促使自私節(jié)點(diǎn)協(xié)作納什均衡的分析框架。

關(guān)鍵詞： 無(wú)線網(wǎng)絡(luò) 博弈論 節(jié)點(diǎn)協(xié)作

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

因此，如何激勵(lì)無(wú)線網(wǎng)絡(luò)中的自私節(jié)點(diǎn)協(xié)作是一個(gè)需待解決的問(wèn)題。博弈論主要研究公式化了的激勵(lì)結(jié)構(gòu)間的相互作用，是研究具有斗爭(zhēng)或競(jìng)爭(zhēng)性質(zhì)現(xiàn)象的數(shù)學(xué)理論和方法。因此利用博弈理論的研究無(wú)線網(wǎng)絡(luò)中自私節(jié)點(diǎn)的協(xié)作及其激勵(lì)方法是一種行之有效的辦法[2]。

一、無(wú)線網(wǎng)絡(luò)的合理性假設(shè)

利用博弈理論對(duì)無(wú)線網(wǎng)絡(luò)中自私節(jié)點(diǎn)的協(xié)作行為進(jìn)行研究，首先要建立無(wú)線網(wǎng)絡(luò)的博弈理論模型，但是在建立模型之前，還要對(duì)無(wú)線網(wǎng)絡(luò)進(jìn)行適當(dāng)?shù)睦碚摲治雠c處理。因此本文首先建立無(wú)線網(wǎng)絡(luò)如下合理性假設(shè)：

（1）網(wǎng)絡(luò)中存在n個(gè)節(jié)點(diǎn)，且都是理性且自私的。（理性且自私是指節(jié)點(diǎn)不會(huì)自愿提供分組轉(zhuǎn)發(fā)等服務(wù)，并始終將能夠最大化自身效益的策略作為最佳策略）；

（2）時(shí)間T被分隔成為時(shí)間槽T1，T2，T3，...，Tn，節(jié)點(diǎn)在每個(gè)時(shí)間槽內(nèi)完成一次會(huì)話；

（3）無(wú)線網(wǎng)絡(luò)是一個(gè)多跳網(wǎng)絡(luò)，即不在彼此的傳輸范圍內(nèi)的兩個(gè)節(jié)點(diǎn)進(jìn)行通信時(shí)，需要借助其他節(jié)點(diǎn)的轉(zhuǎn)發(fā)；

（4）在整個(gè)會(huì)話過(guò)程中路由沒(méi)有失效，節(jié)點(diǎn)也沒(méi)有出現(xiàn)故障；

（5）所有會(huì)話中，分組最終到達(dá)目的節(jié)點(diǎn)所經(jīng)過(guò)的平均跳數(shù)為M，整個(gè)網(wǎng)絡(luò)的轉(zhuǎn)發(fā)負(fù)載是均衡分布的；

（6）任何節(jié)點(diǎn)在接收和發(fā)送（包括轉(zhuǎn)發(fā)）分組時(shí)都要消耗有限的資源。與之相比，節(jié)點(diǎn)在處理分組時(shí)的資源消耗可以忽略不計(jì)；

（7）所有分組長(zhǎng)度相同，節(jié)點(diǎn)發(fā)送一個(gè)分組時(shí)所消耗的資源相等，節(jié)點(diǎn)接收一個(gè)分組時(shí)所消耗的資源相等。

二、節(jié)點(diǎn)協(xié)作納什均衡的分析框架

根據(jù)以上的假設(shè)，我們可以將任何兩個(gè)節(jié)點(diǎn)之間的一次會(huì)話看做是一次博弈。如果兩個(gè)節(jié)點(diǎn)之間僅僅進(jìn)行一次會(huì)話，我們稱之為一次性博弈，如果兩個(gè)節(jié)點(diǎn)之間進(jìn)行兩次或兩次以上的會(huì)話，我們稱之為重復(fù)博弈。在重復(fù)博弈中，任何一個(gè)節(jié)點(diǎn)做出的策略選擇都會(huì)影響博弈的結(jié)果，同時(shí)也會(huì)對(duì)下次的會(huì)話產(chǎn)生直接的影響。

目前，針對(duì)無(wú)線網(wǎng)絡(luò)中節(jié)點(diǎn)協(xié)作的研究大致可分為外在、內(nèi)在兩種角度。前者通過(guò)引入虛擬貨幣和聲譽(yù)值等外部機(jī)制來(lái)迫使節(jié)點(diǎn)協(xié)作，而后者則通過(guò)分析和利用利益驅(qū)動(dòng)的本質(zhì)對(duì)節(jié)點(diǎn)決策行為的影響來(lái)引導(dǎo)合作[3]。無(wú)線網(wǎng)絡(luò)中，自私節(jié)點(diǎn)的不協(xié)作行為雖然能夠增加自己的生存時(shí)間，卻大大降低了網(wǎng)絡(luò)的性能及網(wǎng)絡(luò)壽命。因此，無(wú)線網(wǎng)絡(luò)中自私節(jié)點(diǎn)之間一次性博弈的結(jié)果與囚徒困境的納什均衡相似，而這不是一個(gè)全局滿意的結(jié)果。因?yàn)橹貜?fù)博弈可以使囚徒擺脫相互不合作的困境，實(shí)現(xiàn)一個(gè)令人滿意的納什均衡，所以對(duì)自私節(jié)點(diǎn)重復(fù)博弈的納什均衡進(jìn)行研究，能夠從內(nèi)在的角度出發(fā)在本質(zhì)上提高無(wú)線網(wǎng)絡(luò)中自私節(jié)點(diǎn)的協(xié)作性。

用博弈論研究無(wú)線網(wǎng)絡(luò)中節(jié)點(diǎn)協(xié)作的納什均衡時(shí)，必須先建立無(wú)線網(wǎng)絡(luò)的相關(guān)模型，然后利用模型進(jìn)行相應(yīng)的分析。而一個(gè)完善的節(jié)點(diǎn)協(xié)作的納什均衡分析框架應(yīng)該包含以下幾個(gè)部分：

（1）分析單階段博弈中節(jié)點(diǎn)協(xié)作的納什均衡；

（2）分析重復(fù)博弈中采用經(jīng)典策略（包括冷酷策略、禮尚往來(lái)策略、單步觸發(fā)策略等）時(shí)節(jié)點(diǎn)協(xié)作的納什均衡及條件；

（3）對(duì)重復(fù)博弈中不同策略的納什均衡條件進(jìn)行比較。

首先，利用博弈論知識(shí)對(duì)第一部分進(jìn)行了研究，建立了無(wú)線網(wǎng)絡(luò)中包轉(zhuǎn)發(fā)策略的分析模型，對(duì)合作和非合作策略下取得納什均衡的條件進(jìn)行了分析，結(jié)果表明在非協(xié)同性的網(wǎng)絡(luò)中需要增加激勵(lì)機(jī)制以加強(qiáng)節(jié)點(diǎn)協(xié)作；其次，提出了一個(gè)改進(jìn)型的禮尚往來(lái)策略，通過(guò)分析得出自私節(jié)點(diǎn)采用此策略時(shí)系統(tǒng)可以達(dá)到一個(gè)相對(duì)穩(wěn)定的納什均衡點(diǎn)；最后，分析了單階段博弈和重復(fù)博弈中采用經(jīng)典策略時(shí)節(jié)點(diǎn)協(xié)作的納什均衡及其條件。

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

參考文獻(xiàn)：

[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ìn)等.基于重復(fù)博弈的無(wú)線自組網(wǎng)絡(luò)協(xié)作增強(qiáng)模型[J].軟件學(xué)報(bào)，19（3），2008：756-768.