聞英友，趙博，趙宏

(1.東北大學(xué) 醫(yī)學(xué)影像計算教育部重點實驗室，遼寧 沈陽 110819；2.東軟集團研究院，遼寧 沈陽 110719)

1 引言

移動自組網(wǎng)是由一組帶有無線收發(fā)裝置的移動節(jié)點組成的無須固定基礎(chǔ)設(shè)施支持的臨時性通信網(wǎng)絡(luò)，節(jié)點之間的通信通過無線信道、中繼節(jié)點的多跳轉(zhuǎn)發(fā)來完成，網(wǎng)絡(luò)的可用性直接依賴于節(jié)點無償與他人協(xié)作的意愿及其協(xié)作程度，因此節(jié)點間的協(xié)作至關(guān)重要。目前的移動自組網(wǎng)是基于節(jié)點合作這一基本假設(shè)的，然而這種假設(shè)在實際的網(wǎng)絡(luò)環(huán)境中并不一定成立，特別是當(dāng)網(wǎng)絡(luò)節(jié)點屬于多個不同組織的時候。網(wǎng)絡(luò)節(jié)點由于受到自身處理能力、存儲空間、電池容量等各種資源的限制，其行為呈現(xiàn)出一定的理性化趨勢：為了追求自身利益最大化，節(jié)點在使用網(wǎng)絡(luò)資源的同時，拒絕耗費自身有限的能量為他人提供服務(wù)，這勢必會影響到網(wǎng)絡(luò)正常的路由和數(shù)據(jù)轉(zhuǎn)發(fā)功能[1]。與惡意節(jié)點不同，自私節(jié)點并不是主動、直接破壞網(wǎng)絡(luò)的正常運行，因為主動、直接破壞將會消耗大量的能量，但節(jié)點自私性的影響卻是不可忽視的，研究表明，即便存在著小部分的自私節(jié)點(10%～40%)，也將導(dǎo)致網(wǎng)絡(luò)吞吐性能的顯著下降(16%～32%)[2]。因此，如何有效地激勵節(jié)點的協(xié)作行為，從而保障自組網(wǎng)的可用性及整體網(wǎng)絡(luò)性能，是當(dāng)前移動自組網(wǎng)研究領(lǐng)域面臨的重大挑戰(zhàn)之一。

針對上述問題，在假設(shè)節(jié)點理性的基礎(chǔ)上，提出了一種有效的懲罰策略，并利用重復(fù)博弈模型對網(wǎng)絡(luò)節(jié)點的協(xié)作過程進(jìn)行了分析，得出了激勵一致性條件，在此條件下，節(jié)點將迫于懲戒策略的威懾而自愿采取合作行為。利用演化博弈理論，進(jìn)一步對懲罰策略的穩(wěn)定性進(jìn)行了分析。

2 相關(guān)工作

目前，基于博弈論的移動自組網(wǎng)激勵機制主要包括如下。Srinivasan[3]提出了一種針對不同能量等級來調(diào)整節(jié)點轉(zhuǎn)發(fā)率的協(xié)作模型，從節(jié)點與網(wǎng)絡(luò)博弈的角度分析協(xié)作發(fā)生的可能性。作者對各能級的歸一化轉(zhuǎn)發(fā)率(NAR, normalized acceptance rate)進(jìn)行了求解，并提出了一種收斂于NAR的轉(zhuǎn)發(fā)策略GTFT(generous tit-for-tat)，然而，為計算NAR，必須獲知所有節(jié)點的能級及其作為源或中繼節(jié)點的概率分布，作者并沒有明確指出如何獲得這些信息；另一方面，能量等級的劃分也忽略了個體的差異性和機制的公平性。Wei Yu[4]等人利用博弈論框架對自組網(wǎng)中的合作激勵與安全問題進(jìn)行了分析，作者首先建立了2個節(jié)點間的分組轉(zhuǎn)發(fā)博弈模型，利用Pareto最優(yōu)、子博弈完美等最優(yōu)化標(biāo)準(zhǔn)對模型的納什均衡進(jìn)行了精煉，給出了最優(yōu)防欺詐分組轉(zhuǎn)發(fā)策略，然后將該策略擴展到多個節(jié)點的博弈場景中，提出了基于信譽的防欺詐、抗攻擊的合作激勵策略，不僅可有效激勵節(jié)點的自私行為，同時也應(yīng)對潛在的攻擊行為。Komathy[5]等人利用非合作博弈理論對鄰居節(jié)點的自私性進(jìn)行研究，采用馬科夫鏈分析了2個節(jié)點的分組轉(zhuǎn)發(fā)博弈，提出了一種強制合作策略BNS(best neighbor strategy)，并證明了該策略是演化穩(wěn)定的，能夠抵御自私策略的入侵。Urpi[6]等人將節(jié)點的能量等級作為參與人的類型特征，基于貝葉斯博弈對節(jié)點間的合作轉(zhuǎn)發(fā)行為進(jìn)行了建模，給出了相關(guān)均衡條件，并形式化地證明了：一般情況下，節(jié)點轉(zhuǎn)發(fā)的分組數(shù)量不會多于其自身發(fā)送的分組數(shù)量。Jaramillo[7]提出了一種在路由發(fā)現(xiàn)階段建立的合作轉(zhuǎn)發(fā)博弈模型，并通過鄰居發(fā)現(xiàn)協(xié)議來發(fā)現(xiàn)參與博弈的節(jié)點數(shù)，網(wǎng)絡(luò)中的節(jié)點通過混合策略中的概率轉(zhuǎn)發(fā)策略，實現(xiàn)了混合策略納什均衡。

在國內(nèi)研究方面，文獻(xiàn)[8～10]綜述了無線網(wǎng)絡(luò)中因自私節(jié)點而帶來的一些關(guān)鍵問題，特別對含有自私節(jié)點的無線環(huán)境中基于非合作博弈理論的路由機制進(jìn)行了分析和研究。陸音等[11]針對自組網(wǎng)絡(luò)節(jié)點的預(yù)期收益及其協(xié)作交互過程建立了一個重復(fù)博弈模型，改進(jìn)了文獻(xiàn)[12]中提出的孤立懲罰機制，給出了激勵一致性條件，在此條件下，節(jié)點將迫于懲戒機制威懾而自愿采取合作策略，同時分析了節(jié)點對將來利益重視程度、機制參數(shù)和作弊檢測效率對協(xié)作效果的影響。武漢大學(xué)的王博等[13]同樣采用懲罰機制促進(jìn)節(jié)點間的合作，設(shè)計了一種通用懲罰機制對節(jié)點的不合作行為進(jìn)行懲罰，從而抵消了節(jié)點從不合作行為中的獲益，并在此基礎(chǔ)上建立了基于懲罰機制的激勵合作轉(zhuǎn)發(fā)模型，得出了激勵節(jié)點之間合作的積極性條件，但是沒有給出懲罰機制具體的實現(xiàn)方法。由于懲罰是由鄰居節(jié)點實施的，節(jié)點的移動性會導(dǎo)致懲罰失效，因此上述基于本地監(jiān)測的懲罰機制在動態(tài)適應(yīng)性方面有待進(jìn)一步加強。黃蕾等[14]基于鄰居節(jié)點中繼和生成的路由請求分組之間的統(tǒng)計關(guān)系，提出了一種適用于按需路由協(xié)議尋路階段的自私行為檢測和懲罰機制, 并利用博弈論對激勵合作機制的有效性進(jìn)行了分析。

3 重復(fù)報文轉(zhuǎn)發(fā)博弈模型

移動自組網(wǎng)節(jié)點在長期使用網(wǎng)絡(luò)時，或無法預(yù)知何時退出網(wǎng)絡(luò)時，其行為特征將不再僅由歷史收益或眼前的既得利益所決定，而更取決于它對未來利益的期望，因此節(jié)點會表現(xiàn)得更加耐心，更具有合作的意愿。理性節(jié)點如果預(yù)見到其不合作行為將不可避免地招致懲罰并導(dǎo)致未來收益降低，那么它必將選擇合作行為，因此可針對節(jié)點的耐心程度來設(shè)計靈活的懲罰機制，以降低自私節(jié)點未來的收益，震懾其作弊的企圖，從而促成其合作。

依照重復(fù)博弈理論，將相鄰節(jié)點之間的報文轉(zhuǎn)發(fā)抽象成一個多次博弈的過程，將節(jié)點的耐心程度視為繼續(xù)參與下一次博弈的概率，以此建立重復(fù)報文轉(zhuǎn)發(fā)博弈模型，對節(jié)點的預(yù)期收益進(jìn)行分析，求解其納什均衡，最終得出激勵一致性條件。

3.1 單階段報文轉(zhuǎn)發(fā)博弈

在沒有采取任何懲罰策略的條件下，對相鄰節(jié)點間的報文轉(zhuǎn)發(fā)過程進(jìn)行建模，首先給出博弈的假設(shè)條件。

1) 整個移動自組網(wǎng)G(V,E)由N個理性節(jié)點構(gòu)成，G為連通圖，V,E則分別為G的節(jié)點及鏈路集合。

2) 節(jié)點間的通信鏈路是雙向的，即當(dāng)且僅當(dāng)節(jié)點u,v均處于彼此傳輸范圍內(nèi)時，它們之間的通信鏈路(u,v)∈E。

3) 由于相鄰節(jié)點直接通信時，不涉及到報文轉(zhuǎn)發(fā)，因此假定網(wǎng)絡(luò)中任意兩節(jié)點的通信至少經(jīng)過1個以上的中繼節(jié)點。

4) 整個系統(tǒng)時間由一系列離散的時隙t構(gòu)成，在任一時隙內(nèi)，單階段報文轉(zhuǎn)發(fā)博弈都會發(fā)生，每個節(jié)點均至少有1個報文待發(fā)送，且在同一時隙內(nèi)的路由狀態(tài)不會發(fā)生變化，確保每一報文均能抵達(dá)目標(biāo)節(jié)點。

5) 所有節(jié)點轉(zhuǎn)發(fā)單個報文消耗相同的能量e，而接收和處理報文的能耗相對較小，可忽略不計。

根據(jù)博弈假設(shè)條件，可定義節(jié)點間的單階段報文轉(zhuǎn)發(fā)博弈的如下。

定義1 單階段報文轉(zhuǎn)發(fā)博弈的基本式為G={Γ,S, μ}，其中參與人集合Γ={i, j}，i與j為鄰居節(jié)點；節(jié)點的策略空間為S={Si, Sj}，效用函數(shù)為μ={μi,μj}。

理性節(jié)點在報文轉(zhuǎn)發(fā)過程中，如按照協(xié)議規(guī)范進(jìn)行轉(zhuǎn)發(fā)，稱節(jié)點采取協(xié)作(cooperation)策略；不進(jìn)行轉(zhuǎn)發(fā)則稱節(jié)點采取不協(xié)作(non-cooperation)策略。因此節(jié)點的策略集合為Si=Sj={1,0}，其中1表示協(xié)作策略C，0表示不協(xié)作策略NC。不妨假設(shè)當(dāng)鄰居節(jié)點合作時，節(jié)點成功發(fā)送1個報文時的收益為b，接收報文的收益為0，則可將時隙t中節(jié)點i的效用函數(shù)定義為

類似地，節(jié)點j的效用函數(shù)為

其中，si∈Si，sj∈Sj，ni和nj分別為節(jié)點i和節(jié)點j在時隙t內(nèi)轉(zhuǎn)發(fā)的報文數(shù)量。結(jié)合節(jié)點的博弈策略和效用函數(shù)，可以得出一個二維的收益矩陣，如表1所示。

表1 節(jié)點單階段博弈收益矩陣

當(dāng)b＞enk，k=i，j時，不論鄰居節(jié)點合作與否，節(jié)點選擇NC策略的收益最大，因此，策略NC為單階段報文轉(zhuǎn)發(fā)博弈的優(yōu)超策略，所有理性節(jié)點都將采取NC策略，此時博弈達(dá)到納什均衡，網(wǎng)絡(luò)中將不存在任何的合作行為，且所有節(jié)點的收益均為0，這就形成了移動自組網(wǎng)中的“囚徒困境”。

3.2 嚴(yán)厲針鋒相對懲罰策略

導(dǎo)致上述協(xié)作困境的根本原因在于節(jié)點的作弊行為不會遭致相應(yīng)的后續(xù)懲罰，如果存在某種懲罰策略，使得節(jié)點作弊獲得的短期利益無法彌補因懲罰而帶來的未來利益損失，那么理性節(jié)點必將選取合作策略。

在重復(fù)博弈中，常見的懲罰策略包括：觸發(fā)策略(trigger strategy)、有限懲罰策略(limited punishment strategy)和針鋒相對策略(tit for tat strategy)。Robert Axelrod證明了在無限重復(fù)博弈中，參與人最好的應(yīng)對策略是針鋒相對策略[15]。針鋒相對策略(TFT)可簡述為：在博弈雙方策略可觀察的條件下，某參與者在第一個博弈階段(t=1)選擇協(xié)作；在t＞1的階段，選擇對手在t-1階段的策略?？梢钥闯?，TFT策略的懲罰是單期的(只能持續(xù)一個階段)，懲罰力度單一，無法對自私節(jié)點形成足夠的震懾。針對此問題，提出了一種新的基于本地監(jiān)測的懲罰機制：嚴(yán)厲針鋒相對策略(stern tit for tat strategy)。

嚴(yán)厲針鋒相對策略，簡稱STFT，可描述為：在博弈雙方策略可觀察的條件下，節(jié)點在第一個博弈階段(t=1)選擇協(xié)作；在t＞1的博弈階段，如果節(jié)點i在t-1階段選擇不協(xié)作，則從t階段開始所有鄰居節(jié)點對節(jié)點i實施T個階段的嚴(yán)厲懲罰。在懲罰期內(nèi)，所有以i為源或目標(biāo)的報文將被拒絕轉(zhuǎn)發(fā)，同時節(jié)點i必須為其余節(jié)點提供無償轉(zhuǎn)發(fā)服務(wù)；若節(jié)點i在懲罰內(nèi)，不接受懲罰而再次選擇不協(xié)作，則懲罰將變?yōu)闊o限期。在懲罰期結(jié)束后，節(jié)點i的不協(xié)作行為將被遺忘，其他節(jié)點回到合作狀態(tài)?？梢?，當(dāng)T=1時，STFT策略退化成TFT策略。

3.3 重復(fù)報文轉(zhuǎn)發(fā)博弈

在典型的囚徒困境特征的博弈模型中，由于參與人的自私性和機會主義傾向，對于一次性博弈的策略組合，{不協(xié)作，不協(xié)作}是各方的最優(yōu)策略選擇，即選擇盡可能大地去享用他人的服務(wù)和資源，同時盡可能拒絕為他人提供服務(wù)，以達(dá)到自身利益最大化。為了打破這種困境，引入了嚴(yán)厲針鋒相對策略，使得節(jié)點的作弊行為將受到后續(xù)懲罰，從而促使節(jié)點選擇不同的策略均衡，同時，考慮到節(jié)點無法預(yù)知博弈何時終止，相鄰節(jié)點間的多次報文轉(zhuǎn)發(fā)過程不再是一系列相互獨立的單階段報文轉(zhuǎn)發(fā)博弈，而是擴展成了一個無限重復(fù)報文轉(zhuǎn)發(fā)博弈。

結(jié)合上面給出的單階段博弈模型，利用無限重復(fù)博弈理論對節(jié)點間的報文轉(zhuǎn)發(fā)行為進(jìn)行建模，具體如下。

定義2 設(shè)G為階段博弈，移動自組網(wǎng)中節(jié)點之間的長期報文轉(zhuǎn)發(fā)交互過程是階段博弈G的不斷重復(fù)，并且在每次階段博弈開始前，所有以往博弈的歷史都被觀察到，那么這樣構(gòu)成的動態(tài)博弈就稱之為無限重復(fù)報文轉(zhuǎn)發(fā)博弈，記作G(∞,δ)，δ為貼現(xiàn)因子，且0＜δ＜1。各博弈方在G(∞,δ)中的收益等于各階段收益的貼現(xiàn)值之和，即節(jié)點i在整個重復(fù)博弈中的預(yù)期收益可表述為

為了便于分析，假設(shè)在穩(wěn)定的路由狀態(tài)下，節(jié)點i在每個時隙中所需轉(zhuǎn)發(fā)報文數(shù)量的平均值為n?？疾熘貜?fù)報文轉(zhuǎn)發(fā)博弈過程可以看出，理性節(jié)點如果在一次作弊后，不接受懲罰而選擇持續(xù)作弊，則其預(yù)期收益為

如果理性節(jié)點接受懲罰，那么在懲罰期結(jié)束后，節(jié)點將再次面臨相同的決策場景，即重復(fù)轉(zhuǎn)發(fā)博弈的每個子博弈階段，恰好都是原博弈本身，因此，理性節(jié)點仍將再次選擇不協(xié)作策略，在這種情況下，其預(yù)期收益為

為了激勵自私節(jié)點的協(xié)作行為，必須保證其在采取持續(xù)協(xié)作策略時的預(yù)期收益不低于采取不協(xié)作策略的預(yù)期收益。根據(jù)式(1)可計算節(jié)點在持續(xù)協(xié)作時的預(yù)期收益為

在理性節(jié)點做出決策之前，都會對將來的預(yù)期收益進(jìn)行評估，如果式(5)成立，則節(jié)點必將選擇協(xié)作策略。作為系統(tǒng)設(shè)計者，可針對不同的δ設(shè)置相應(yīng)的T值，使式(5)條件成立，從而促進(jìn)節(jié)點的協(xié)作。從式(5)中可以看出，懲罰機制是靠引入負(fù)收益來實現(xiàn)的，懲罰的力度取決于T。由表1可知，μi(C,C)=μi(NC,C)+μi(C,NC)，將式(5)化簡可得

其中，T≥1，式(6)即為無限重復(fù)報文轉(zhuǎn)發(fā)博弈的激勵一致性條件。當(dāng)節(jié)點采用嚴(yán)厲針鋒相對策略時，式(6)保證了每個單階段子博弈的{協(xié)作，協(xié)作}策略組合為子博弈的完美納什均衡，從而整個重復(fù)博弈也將處于納什均衡狀態(tài)，任何理性節(jié)點均無法形成足夠的動機來偏離協(xié)作策略。

3.4 重復(fù)報文轉(zhuǎn)發(fā)博弈參數(shù)分析

由式(6)可見，其右端是由節(jié)點所處網(wǎng)絡(luò)環(huán)境以及節(jié)點自身狀況所決定的，取值依賴于b、e和n。對于系統(tǒng)設(shè)計者而言，為了能夠依據(jù)激勵一致性條件選取適當(dāng)?shù)膽土P措施，必須首先對右式的取值進(jìn)行預(yù)測和評估。一般來說，n可設(shè)定為全網(wǎng)節(jié)點平均轉(zhuǎn)發(fā)報文數(shù)量的最大值；而參數(shù)b和e，對于不同節(jié)點，它們的取值可能是不同的，是由節(jié)點自身狀態(tài)所決定的，比如QoS等級、當(dāng)前剩余能量等，但是其比值可根據(jù)節(jié)點所處的具體應(yīng)用環(huán)境進(jìn)行設(shè)定。

式(6)的左端完全由貼現(xiàn)因子δ和懲罰參數(shù)T構(gòu)成，其中，δ由網(wǎng)絡(luò)和應(yīng)用的性質(zhì)決定，而參數(shù)T代表懲罰力度的大小，在不同的應(yīng)用環(huán)境中，可通過靈活設(shè)置T的取值來實現(xiàn)不同程度的協(xié)作激勵。令函數(shù)，由于0＜δ＜1，函數(shù)f(δ,T)是T的增函數(shù)，如圖1所示。

圖1 f(δ, T)函數(shù)

根據(jù)函數(shù)f(δ, T)的性質(zhì)，可對激勵一致性條件做進(jìn)一步分析。

命題1 T的增加有助于提升節(jié)點間的協(xié)作。

命題1說明，T越大，則節(jié)點預(yù)期收益中因不協(xié)作所遭受的損失就越大，那么理想節(jié)點便越傾向于選擇協(xié)作策略，這與直覺相一致。

命題2表明，當(dāng)節(jié)點極端注重眼前既得利益時，由于交易環(huán)境過于惡劣，懲戒策略將完全失效，節(jié)點將不受任何約束的自由選擇策略。然而，考慮到即使在這種最惡劣的環(huán)境下，還是可以通過限制節(jié)點最大轉(zhuǎn)發(fā)的報文數(shù)量n來進(jìn)行調(diào)整，以使式(6)成立，從而保證懲罰策略的有效性。

命題3給出了一種較為長期穩(wěn)定的交易場景，即理性節(jié)點由于不知何時會退出網(wǎng)絡(luò)，它對未來的預(yù)期利益會表現(xiàn)得更加重視，這時，僅需1次懲罰便足以震懾其作弊行為。

上述關(guān)于δ界限以及T取值設(shè)定的結(jié)論，為分析重復(fù)轉(zhuǎn)發(fā)博弈模型中的節(jié)點協(xié)作程度提供了基礎(chǔ)依據(jù)，使系統(tǒng)設(shè)計者能夠?qū)土P策略的適用性及其有效性做出迅速判斷，進(jìn)而做出相應(yīng)的調(diào)整。

4 基于演化博弈的節(jié)點協(xié)作性分析

傳統(tǒng)的重復(fù)博弈理論得到均衡是靜態(tài)的均衡，即博弈最終所能到達(dá)的穩(wěn)定狀態(tài)，它無法描述參與人達(dá)成均衡的動態(tài)演化過程，因此，本節(jié)將從整個群體的角度出發(fā)，對節(jié)點間的協(xié)作關(guān)系進(jìn)行分析，建立演化博弈模型，闡述節(jié)點由自私向協(xié)作的演化過程，并分析STFT策略的穩(wěn)定性。

4.1 演化博弈模型建立與求解

移動自組網(wǎng)中節(jié)點發(fā)送報文的同時，也需要轉(zhuǎn)發(fā)報文。本文假定參與網(wǎng)絡(luò)運行的實體節(jié)點可分為兩類：協(xié)作節(jié)點和自私節(jié)點。雙方的策略集合均為{STFT,NC}，系統(tǒng)通過“物競天澤，適者生存”的原則自發(fā)演化，各節(jié)點根據(jù)其他節(jié)點的策略選擇，通過學(xué)習(xí)、調(diào)整和模仿過程，以尋求最優(yōu)策略。節(jié)點間的協(xié)作報文轉(zhuǎn)發(fā)過程是在一個具有不確定性和有限理性的空間進(jìn)行，同時它們之間的策略選擇又是相互影響的。博弈雙方的收益矩陣如表2所示。

表2 演化博弈收益矩陣

由于演化博弈也是基于時間序列的，因此根據(jù)收益的貼現(xiàn)計算方法可得

假設(shè)節(jié)點中協(xié)作節(jié)點所占的比例為 ρ，則自私節(jié)點所占比例為1-ρ。由收益矩陣可計算。

協(xié)作節(jié)點的期望收益為

自私節(jié)點的期望收益為

由協(xié)作節(jié)點和自私節(jié)點的期望收益，可計算總體的平均收益為

可構(gòu)造協(xié)作節(jié)點的復(fù)制動態(tài)方程

式(7)描述了演化系統(tǒng)中的協(xié)作群體動態(tài)。令F(ρ)=0，若U(N, S)≠0，可求得 ρ1=0，ρ2=1；若U(N,S)=0，則對于任意ρ∈[0,1]都是上述方程式的解。

4.2 STFT策略穩(wěn)定性分析

由F(ρ)=0求出的均衡解并不一定都是穩(wěn)定的，但根據(jù)微分方程的穩(wěn)定性原理可知：穩(wěn)定狀態(tài)處的函數(shù)導(dǎo)數(shù)必須小于0，即F′(ρ*)＜0，ρ*表示穩(wěn)定狀態(tài)，即ρ*為演化穩(wěn)定策略。下面分別對求得的均衡解進(jìn)行穩(wěn)定性分析。

1) 當(dāng)U(N,S)=0，任意ρ∈[0,1]都是均衡解，且恒有F′(ρ)=0，這說明外界的任何擾動都不能使?fàn)顟B(tài)發(fā)生波動，因此 ρ∈[0,1]都是動態(tài)穩(wěn)定均衡解，此時復(fù)制動態(tài)方程的動態(tài)演化相位如圖2所示。

圖2 ρ∈[0,1]為穩(wěn)定狀態(tài)

2) 當(dāng)U(N,S)≠0，ρ1=0和 ρ2=1為均衡解。由F ′(ρ)=(1-2ρ)·U(N,S)可計算

圖3 ρ=ρ1為穩(wěn)定狀態(tài)點

圖4 ρ=ρ2為穩(wěn)定狀態(tài)點

5 仿真測試與分析

5.1 仿真方法與仿真設(shè)置

為驗證激勵一致性條件及嚴(yán)厲針鋒相對懲罰策略的正確性和有效性，本文在NS-2[16]仿真平臺上進(jìn)行了仿真實驗，采取的仿真方法如下。

1) 網(wǎng)絡(luò)拓?fù)湓O(shè)置：利用NS-2中的GT-ITM Topology Generator生成N個節(jié)點組成的隨機拓?fù)?，N默認(rèn)為20，網(wǎng)絡(luò)直徑為8跳。

2) 隨機流量設(shè)置：節(jié)點間的業(yè)務(wù)流量由cbrgen工具生成，隨機挑選源節(jié)點以及非相鄰的目標(biāo)節(jié)點，生成20對CBR業(yè)務(wù)流，每個CBR報文大小為512 B，每秒發(fā)送4個報文。任意一個節(jié)點在一輪協(xié)作時隙中均可發(fā)送12個報文。

3) 節(jié)點行為監(jiān)測與懲罰實施：采用Catch[17]協(xié)議對節(jié)點的轉(zhuǎn)發(fā)行為進(jìn)行監(jiān)控，一旦發(fā)現(xiàn)節(jié)點的作弊行為，則通過Catch的ANV機制實現(xiàn)鄰居節(jié)點對作弊節(jié)點的協(xié)同懲罰。

4) 路由協(xié)議采用DSR[18]協(xié)議，源節(jié)點在報文頭部中顯式的設(shè)定源路由信息，以便Catch中的Watchdog進(jìn)行信息統(tǒng)計與行為監(jiān)控。

5) 節(jié)點報文轉(zhuǎn)發(fā)決策：各節(jié)點依據(jù)當(dāng)前轉(zhuǎn)發(fā)報文數(shù)量ni，遵照式(6)對可行策略進(jìn)行評估，進(jìn)而選擇轉(zhuǎn)發(fā)行為(轉(zhuǎn)發(fā)/丟棄)。

6) 報文完成發(fā)送與轉(zhuǎn)發(fā)后，節(jié)點統(tǒng)計并存儲報文轉(zhuǎn)發(fā)信息，節(jié)點的下一階段策略選取隨本地監(jiān)控結(jié)果而改變，一輪交互時隙仿真結(jié)束。

仿真的物理環(huán)境設(shè)定如下：仿真區(qū)域的大小為800 m×800 m，節(jié)點移動速度在1～10 m/s之間均勻分布，節(jié)點持續(xù)運動，中間不作停留，每個節(jié)點的無線傳輸距離為250 m，帶寬為2 Mbit/s，信道和無線模型為Two-Ray Ground，鏈路層采用IEEE 802.11協(xié)議。重復(fù)博弈模型中的相關(guān)參數(shù)設(shè)置如下：b=1，e=0.048 63。

在仿真過程中，每一類實驗共進(jìn)行5次，每次實驗由50次隨機拓?fù)浣M成，針對每一拓?fù)潆S機產(chǎn)生200次CBR流量，即仿真時隙為200個，仿真結(jié)果取5次仿真實驗的平均值。

考慮到節(jié)點作弊行為所導(dǎo)致的直接后果就是分組丟失率上升，報文成功發(fā)送的比率下降，網(wǎng)絡(luò)可用性降低，因此，在下面的仿真實驗中，重點考察節(jié)點自私性、耐心程度及懲罰策略對報文投遞率的影響，進(jìn)而驗證激勵機制的有效性。這里定義報文投遞率(PDR, packet delivery ratio)為：所有成功到達(dá)目標(biāo)的報文與全部發(fā)送的報文的比值。

5.2 仿真結(jié)果與分析

1) 節(jié)點自私性對協(xié)作性的影響

如果缺乏懲罰策略的震懾，節(jié)點間的交互將逐漸退化為單階段報文轉(zhuǎn)發(fā)博弈，節(jié)點趨向選擇不協(xié)作，自私節(jié)點將越來越多。隨著自私節(jié)點比率的增加，越來越多的傳輸鏈路將被打斷，產(chǎn)生越來越多的路由分區(qū)，從而降低了整個網(wǎng)絡(luò)的可用性。如圖5所示，在沒有引入懲罰機制時，原始DSR協(xié)議的報文投遞率隨自私節(jié)點比率的增加而急劇下降，最終導(dǎo)致整個網(wǎng)絡(luò)癱瘓。

圖5 不同自私節(jié)點比率對報文投遞率的影響

圖5中也給出了懲罰機制存在時的情況，可以看出，雖然報文投遞率的整體趨勢都在下降，但是引入懲罰機制后，報文投遞率有了明顯的改善，提高幅度至少都在10%以上。當(dāng)δ=0.6時，即便自私節(jié)點比率高達(dá)80%以上，只要采取合適的懲罰力度(T=3)，也能確保92%以上的報文成功抵達(dá)目的地。這說明懲罰機制確實使得原來的自私節(jié)點重新審視其轉(zhuǎn)發(fā)策略，為了避免因懲罰而帶來的利益損失，自私節(jié)點將不得不與其他節(jié)點合作，開始轉(zhuǎn)發(fā)報文，從而提高了網(wǎng)絡(luò)的全局協(xié)作程度，增強了網(wǎng)絡(luò)的可用性，延長了網(wǎng)絡(luò)的生存時間。

鑒于自私節(jié)點比率為1時，網(wǎng)絡(luò)中不存在任何協(xié)作行為，此時網(wǎng)絡(luò)環(huán)境最差，因此在后續(xù)仿真實驗中，設(shè)置所有節(jié)點均為自私節(jié)點。

2) 節(jié)點耐心程度對協(xié)作性的影響

圖6為T=2時的報文投遞率隨δ的變化情況，從圖中可以看出，投遞率隨δ的增加而明顯提高，整個網(wǎng)絡(luò)的可用性隨節(jié)點耐心程度的增加而提高，這與觀察動態(tài)博弈中的無名氏定理相符。考察曲線N=20，當(dāng)b=1，e=0.048 63時，由命題3可知，δ＞0.917 7可保證節(jié)點均采取協(xié)作策略，圖6證實了這一點，此時的報文投遞率等于沒有自私節(jié)點的情況；而當(dāng)δ接近0時，注意到各曲線的PDR并不為0，這主要源于自私節(jié)點接受懲罰時的無償轉(zhuǎn)發(fā)服務(wù)，其貢獻(xiàn)十分有限，最多不足10%。

圖6 節(jié)點耐心程度對報文投遞率的影響(T=2)

由圖6可見，隨著N的增加，即使節(jié)點足夠耐心，報文投遞率仍然有所下降，當(dāng)δ=1時，N=50的報文投遞率與N=20的報文投遞率相比也下降了15%，此時的懲罰力度(T=2)已不能有效激勵自私節(jié)點合作的積極性。因為隨著N的增大，每個時隙中節(jié)點需要轉(zhuǎn)發(fā)的報文數(shù)量n也隨之增多，而懲罰力度卻相對固定，以致無法滿足激勵一致性條件的要求，節(jié)點趨向自私化。因此，網(wǎng)絡(luò)中的節(jié)點數(shù)量越多，懲罰機制應(yīng)越嚴(yán)厲。

圖7給出了更為嚴(yán)厲的懲罰措施下(T=3)的仿真結(jié)果，可以看出，報文投遞率同樣隨δ的增大而上升，同時，隨N的增大而降低。對比圖6和圖7，網(wǎng)絡(luò)規(guī)模相同時，懲罰力度加大，報文投遞率也隨之升高，而且當(dāng)δ增大時，T=3對投遞率的提高比T=2時更加明顯，這說明從整體角度來看T=3的激勵效果要好于T=2的激勵效果。因此，針對不同的網(wǎng)絡(luò)規(guī)模和不同的節(jié)點耐心程度，靈活配置合適的懲罰力度是激勵節(jié)點合作的關(guān)鍵。

圖7 節(jié)點耐心程度對報文投遞率的影響(T=3)

3) 懲罰機制對協(xié)作性的影響

圖8給出了懲罰力度對報文投遞率的影響，同時也給出了不同節(jié)點耐心程度時的情況。從圖中可以看出，T的增加對節(jié)點間的協(xié)作性起到了明顯的促進(jìn)作用，而這一效果在節(jié)點耐心程度較低時尤為明顯，這一觀察與命題1是相符合的。另一方面，當(dāng)T=1時，STFT懲罰機制退化為TFT懲罰機制，可以看出，TFT懲罰機制對節(jié)點協(xié)作性有一定的促進(jìn)作用，但是當(dāng)節(jié)點耐心程度較差時，其取得的效果并不理想，以δ=0.3為例，TFT只能將報文投遞率提升到58%，而STFT最多可將PDR提升到80%，因此，STFT懲罰機制更加靈活、有效，更具可擴展性。

圖8 懲罰機制對報文投遞率的影響

6 結(jié)束語

移動自組網(wǎng)中的節(jié)點受到自身處理能力、存儲空間和電池能量等各種資源的限制，經(jīng)常會表現(xiàn)出自私性，因此激勵自私節(jié)點的合作行為成為有待解決的關(guān)鍵問題。本文針對節(jié)點的報文轉(zhuǎn)發(fā)過程，首先建立了單階段的報文轉(zhuǎn)發(fā)博弈模型，分析了節(jié)點的自私性；提出了基于本地監(jiān)測的嚴(yán)厲針鋒相對懲罰策略，并以此為基礎(chǔ)構(gòu)建了無限重復(fù)報文轉(zhuǎn)發(fā)博弈模型，求得了激勵一致性條件。然后基于演化博弈理論對節(jié)點由自私向協(xié)作轉(zhuǎn)變的動態(tài)過程進(jìn)行了分析，并證明了嚴(yán)厲針鋒相對策略的演化穩(wěn)定性。最后通過仿真實驗驗證了激勵機制的有效性，仿真結(jié)果表明，通過合理選擇懲罰參數(shù)，可以有效激勵自私節(jié)點的協(xié)作轉(zhuǎn)發(fā)行為，提高網(wǎng)絡(luò)的可用性，延長網(wǎng)絡(luò)的生存時間，增加網(wǎng)絡(luò)的總體收益。

[1] URPI A, BONUCCELLI M, GIORDANO S. Modeling cooperation in mobile ad hoc networks: a formal description of selfishness[A]. Proceedings of 1st International Symposium on Modeling and Optimization in Mobile, Ad Hoc, and Wireless Networks[C]. Hingham, 2003. 3-5.

[2] MARTI S, GIULI T, LAI K. Mitigating routing misbehavior in mobile ad hoc networks[A]. Proceedings of the ACM MobiCom 2000[C].New York, 2000. 255-265.

[3] SRINIVASAN V, NUGGEHALLI P. Cooperation in wireless ad hoc networks[A]. Proceedings of the IEEE INFOCOM 2003[C]. Washington, 2003. 808-817.

[4] YU W, LIU K J R. Game theoretic analysis of cooperation stimulation and security in autonomous mobile ad hoc networks[J]. IEEE Transactions on Mobile Computing, 2007,6(5): 507-521.

[5] KOMATHY K, NARAYANASAMY. Best neighbor strategy to enforce cooperation among selfish nodes in wireless ad hoc networks[J].Computer Communications, 2007, 30(18): 3721-3735.

[6] URPI A, BONUCCELLI M A, GIORDANO A. Modeling cooperation in mobile ad hoc networks: a formal description of selfishness[J].IEEE/ACM Workshop WiOpt, 2003, 39(1): 118-124.

[7] JOSé J J, SRIKANT R. A game theory based reputation mechanism to incentivize cooperation in wireless ad hoc networks[J]. Ad Hoc Networks, 2010, 8(4): 416-429.

[8] ZHAO L, ZHANG J, YANG K, etal. Using incompletely cooperative game theory in mobile ad hoc networks[A]. Proceedings of IEEE International Conference on Communications 2007[C]. Piscataway, NJ,2007.3401-3406.

[9] ZHAO L, ZHAN G J, ZHANG H. GDCF: game-theoretic distributed co-ordination function in WLAN[J]. Electronics Letters, 2007, 43(9):510-511.

[10] 汪洋, 林闖, 李泉林等. 基于非合作博弈的無線網(wǎng)絡(luò)路由機制研究[J].計算機學(xué)報, 2009, 32(1): 54-68.WANG Y, LIN C, LI Q L. Non-cooperative game based research on routing schemes for wireless networks[J]. Chinese Journal of Computers, 2009, 32(1): 54-68.

[11] 陸音, 石進(jìn), 謝立. 基于重復(fù)博弈的無線自組網(wǎng)絡(luò)協(xié)作增強模型[J].軟件學(xué)報, 2008, 19(3): 755-768.LU Y, SHI J, XIE L. Repeated-game modeling of cooperation enforcement in wireless ad hoc network[J]. Journal of Software, 2008,19(3): 755-768.

[12] BANDYOPADHYAY S. A game-theoretic analysis on the conditions of cooperation in a wireless ad hoc network[A]. Proceedings of 3rd International Symposium on Modeling and Optimization in Mobile,Ad Hoc, and Wireless Networks[C]. Trentino, 2005. 54-58.

[13] 王博, 黃傳河, 楊文忠等. Ad Hoc網(wǎng)絡(luò)中基于懲罰機制的激勵合作轉(zhuǎn)發(fā)模型[J]. 計算機研究與發(fā)展, 2011, 48(3): 398-406.WANG B, HUANG C H, YANG W Z. An incentive-cooperative forwarding model based on punishment mechanism in wireless ad hoc networks[J]. Journal of Computer Research and Development, 2011,48(3): 398-406.

[14] 黃蕾, 劉立祥. Ad hoc網(wǎng)絡(luò)尋路階段的合作激勵機制研究[J]. 計算機學(xué)報, 2008, 31(2): 262-269.HUANG L, LIU L X. Study on cooperation stimulation mechanism in route discovery of ad hoc networks[J]. Chinese Journal of Computers,2008, 31(2): 262-269.

[15] AXELROD R. The Evolution of Cooperation[M]. New York: Basic Books, 1984.

[16] ns-2 network simulator[EB/OL]. http://www.isi.edu/nsnam/ns/,2011.

[17] MAHAJAN R, RODRIG M. Sustaining cooperation in multi-hop wireless networks[A]. Proceedings of the USENIX NSDI 2005 Symposium on Networked Systems Design & Implementation (NSDI 2005)[C]. Berkeley, 2005. 231-244.

[18] JOHNSON D B, MALTZ D A. Dynamic Source Routing in Ad Hoc Wireless Networks[M]. Norwell: Kluwer Academic Publishers, 1996.