徐許亮 張明銘
摘 要: 本文針對(duì)無(wú)線(xiàn)網(wǎng)絡(luò)中自私節(jié)點(diǎn)的不協(xié)作行為,結(jié)合博弈理論建立了無(wú)線(xiàn)網(wǎng)絡(luò)的合理性假設(shè),在此基礎(chǔ)上提出了一個(gè)促使自私節(jié)點(diǎn)協(xié)作納什均衡的分析框架。
關(guān)鍵詞: 無(wú)線(xiàn)網(wǎng)絡(luò) 博弈論 節(jié)點(diǎn)協(xié)作
無(wú)線(xiàn)網(wǎng)絡(luò)是由一組帶有無(wú)線(xiàn)收發(fā)裝置的自主性設(shè)備通過(guò)無(wú)線(xiàn)信道連接而成的自治系統(tǒng)。網(wǎng)絡(luò)中的路由發(fā)現(xiàn)和分組轉(zhuǎn)發(fā)等服務(wù)不是通過(guò)專(zhuān)用的路由設(shè)備完成,而是通過(guò)普通節(jié)點(diǎn)(PDA、筆記本電腦、傳感器、車(chē)載電臺(tái)等設(shè)備)的共同協(xié)作來(lái)完成。由于無(wú)線(xiàn)節(jié)點(diǎn)的功率有限,通信半徑較小,因此與傳輸范圍之外的節(jié)點(diǎn)通信時(shí),需要中間節(jié)點(diǎn)的轉(zhuǎn)發(fā)。但是,在沒(méi)有統(tǒng)一管理機(jī)構(gòu)控制的無(wú)線(xiàn)網(wǎng)絡(luò)中,節(jié)點(diǎn)間的協(xié)作卻不能保證。如民用型無(wú)線(xiàn)網(wǎng)絡(luò),在這樣的網(wǎng)絡(luò)中,每個(gè)用戶(hù)獨(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)滿(mǎn)足自身通信的需求,它們會(huì)拒絕提供路由發(fā)現(xiàn)服務(wù)、拒絕轉(zhuǎn)發(fā)其他節(jié)點(diǎn)的分組等。
因此,如何激勵(lì)無(wú)線(xiàn)網(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ú)線(xiàn)網(wǎng)絡(luò)中自私節(jié)點(diǎn)的協(xié)作及其激勵(lì)方法是一種行之有效的辦法[2]。
一、無(wú)線(xiàn)網(wǎng)絡(luò)的合理性假設(shè)
利用博弈理論對(duì)無(wú)線(xiàn)網(wǎng)絡(luò)中自私節(jié)點(diǎn)的協(xié)作行為進(jìn)行研究,首先要建立無(wú)線(xiàn)網(wǎng)絡(luò)的博弈理論模型,但是在建立模型之前,還要對(duì)無(wú)線(xiàn)網(wǎng)絡(luò)進(jìn)行適當(dāng)?shù)睦碚摲治雠c處理。因此本文首先建立無(wú)線(xiàn)網(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ì)話(huà);
(3)無(wú)線(xiàn)網(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ì)話(huà)過(guò)程中路由沒(méi)有失效,節(jié)點(diǎn)也沒(méi)有出現(xiàn)故障;
(5)所有會(huì)話(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ì)話(huà)看做是一次博弈。如果兩個(gè)節(jié)點(diǎn)之間僅僅進(jìn)行一次會(huì)話(huà),我們稱(chēng)之為一次性博弈,如果兩個(gè)節(jié)點(diǎn)之間進(jìn)行兩次或兩次以上的會(huì)話(huà),我們稱(chēng)之為重復(fù)博弈。在重復(fù)博弈中,任何一個(gè)節(jié)點(diǎn)做出的策略選擇都會(huì)影響博弈的結(jié)果,同時(shí)也會(huì)對(duì)下次的會(huì)話(huà)產(chǎn)生直接的影響。
目前,針對(duì)無(wú)線(xiàn)網(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ú)線(xiàn)網(wǎng)絡(luò)中,自私節(jié)點(diǎn)的不協(xié)作行為雖然能夠增加自己的生存時(shí)間,卻大大降低了網(wǎng)絡(luò)的性能及網(wǎng)絡(luò)壽命。因此,無(wú)線(xiàn)網(wǎng)絡(luò)中自私節(jié)點(diǎn)之間一次性博弈的結(jié)果與囚徒困境的納什均衡相似,而這不是一個(gè)全局滿(mǎn)意的結(jié)果。因?yàn)橹貜?fù)博弈可以使囚徒擺脫相互不合作的困境,實(shí)現(xiàn)一個(gè)令人滿(mǎn)意的納什均衡,所以對(duì)自私節(jié)點(diǎn)重復(fù)博弈的納什均衡進(jìn)行研究,能夠從內(nèi)在的角度出發(fā)在本質(zhì)上提高無(wú)線(xiàn)網(wǎng)絡(luò)中自私節(jié)點(diǎn)的協(xié)作性。
用博弈論研究無(wú)線(xiàn)網(wǎng)絡(luò)中節(jié)點(diǎn)協(xié)作的納什均衡時(shí),必須先建立無(wú)線(xiàn)網(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ú)線(xiàn)網(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ú)線(xiàn)自組網(wǎng)絡(luò)協(xié)作增強(qiáng)模型[J].軟件學(xué)報(bào),19(3),2008:756-768.