WMNs中基于重復(fù)博弈的機(jī)會路由激勵機(jī)制研究

吳 軍，莫偉偉，印新棋，白光偉

南京工業(yè)大學(xué) 計算機(jī)科學(xué)與技術(shù)學(xué)院，南京 211816

1 引言

無線Mesh網(wǎng)絡(luò)（WMNs）是動態(tài)地自組織、自配置的分布式無線接入網(wǎng)絡(luò)。WMNs由Mesh路由器（mesh routers）和客戶端節(jié)點（client nodes）兩種類型節(jié)點組成[1]，在混合結(jié)構(gòu)的WMNs中，Mesh路由器移動性較小，構(gòu)成WMNs的骨干結(jié)構(gòu)；而無線Mesh客戶端節(jié)點中具有大量移動節(jié)點，其中多數(shù)節(jié)點仍然有能源、帶寬等限制，本文的策略正是針對混合結(jié)構(gòu)無線Mesh網(wǎng)絡(luò)中的移動客戶端節(jié)點，此外，本文的研究前提是面向任意時刻總是連通的無線多跳網(wǎng)絡(luò)[2]。

機(jī)會路由[3]利用了無線網(wǎng)絡(luò)的廣播特性。網(wǎng)絡(luò)中節(jié)點覆蓋范圍內(nèi)的鄰居節(jié)點都參與監(jiān)聽接收，均有機(jī)會加入轉(zhuǎn)發(fā)候選集，通過多跳轉(zhuǎn)發(fā)完成數(shù)據(jù)傳輸。其中，ExOR是典型機(jī)會路由協(xié)議。相對于傳統(tǒng)路由協(xié)議，采用機(jī)會路由協(xié)議具有更大的吞吐量。理論上網(wǎng)絡(luò)中的節(jié)點均是理性節(jié)點，愿意參與合作轉(zhuǎn)發(fā)。但是在實際應(yīng)用中，移動節(jié)點可能來自很多方面，由于該節(jié)點性能、能源等原因，節(jié)點表現(xiàn)出自私性，尤其是拒絕為其他節(jié)點轉(zhuǎn)發(fā)，但是其仍然使用網(wǎng)絡(luò)發(fā)送與接收數(shù)據(jù)包。這種不參與合作轉(zhuǎn)發(fā)的自私節(jié)點將會極大降低機(jī)會路由的性能。

本文針對機(jī)會路由中的節(jié)點的自私行為，從能量、成功轉(zhuǎn)發(fā)概率以及收益方面考慮，定義一種度量鄰居節(jié)點合作水平的合作度評估函數(shù)，并建立基于合作度評估函數(shù)的寬容針鋒相對策略節(jié)點重復(fù)博弈模型（Cooperation degree Generous Tit-for-Tat，CGTFT）。模擬實驗表明該機(jī)制能夠有效抑制節(jié)點自私行為，激勵節(jié)點參與合作轉(zhuǎn)發(fā)，提高網(wǎng)絡(luò)性能。

2 相關(guān)研究

針對機(jī)會路由的相關(guān)研究主要有：文獻(xiàn)[3]提出的ExOR以及文獻(xiàn)[4]中SOAR協(xié)議都是將無線信道的廣播特性利用到路由轉(zhuǎn)發(fā)中；Biswas等人文中最早提出機(jī)會路由概念，利用轉(zhuǎn)發(fā)候選集來提高網(wǎng)絡(luò)吞吐量。文獻(xiàn)[5]中提出MORE協(xié)議，將網(wǎng)絡(luò)編碼結(jié)合到機(jī)會路由中，進(jìn)一步改善了網(wǎng)絡(luò)吞吐量。本文的路由算法基于ExOR協(xié)議，提出的機(jī)會路由重復(fù)博弈激勵機(jī)制。

針對機(jī)會路由中的節(jié)點不合作與自私行為，當(dāng)前研究主要有以下幾種解決方法：文獻(xiàn)[6]中采用的基于聲譽(yù)的方法激勵自私節(jié)點，聲譽(yù)方法需要根據(jù)節(jié)點的歷史交易行為，綜合考慮直接信譽(yù)以及第三方信息對節(jié)點行為作出最終判斷，目前聲譽(yù)機(jī)制中監(jiān)測的不準(zhǔn)確性是主要問題。在文獻(xiàn)[7]中運(yùn)用VGG機(jī)制鼓勵節(jié)點匯報轉(zhuǎn)發(fā)所需要的真實成本，還給予一定的額外報酬，實現(xiàn)對自私節(jié)點的激勵，該策略的局限是需要單獨(dú)第三方執(zhí)行清算運(yùn)算。文獻(xiàn)[8]中，提出節(jié)點公平競價激勵機(jī)制來激勵網(wǎng)絡(luò)中自私節(jié)點，并且模型化競價過程為一個競價博弈，存在貝葉斯納什均衡使博弈達(dá)到平衡。

本文主要針對機(jī)會路由中節(jié)點自私問題，設(shè)計鄰居節(jié)點合作度評估函數(shù)，并結(jié)合寬容針鋒相對思想[9]，建立CGTFT重復(fù)博弈策略，激勵網(wǎng)絡(luò)中節(jié)點參與合作。通過重復(fù)博弈策略，迫使鄰居節(jié)點考慮未來收益，積極參與合作轉(zhuǎn)發(fā)，從而提高網(wǎng)絡(luò)的性能。

3 機(jī)會路由中節(jié)點自私性分析

在機(jī)會路由利用廣播特性進(jìn)行路由發(fā)現(xiàn)階段，網(wǎng)絡(luò)中節(jié)點通過信息交互獲得其鄰居節(jié)點以及相應(yīng)的鏈路情況。此時，自私節(jié)點為了避免轉(zhuǎn)發(fā)鄰居數(shù)據(jù)包，會有多種策略來使自己逃避轉(zhuǎn)發(fā)工作。根據(jù)節(jié)點的行為，自私節(jié)點分為以下幾類[10-11]：（1）節(jié)點參與網(wǎng)絡(luò)服務(wù)，但是不愿轉(zhuǎn)發(fā)數(shù)據(jù)包。典型策略是丟棄來自其他節(jié)點的數(shù)據(jù)包或者延遲至空閑期轉(zhuǎn)發(fā)。節(jié)點不參與轉(zhuǎn)發(fā)工作將會節(jié)省大量能量。（2）不參與路由服務(wù)，在ExOR路由協(xié)議中，自私節(jié)點阻止網(wǎng)絡(luò)把自己作為中繼節(jié)點，自私節(jié)點可以直接忽視其他節(jié)點的路由請求，不參與鏈路狀態(tài)應(yīng)答。

上述不合作的自私行為將導(dǎo)致機(jī)會路由候選集中節(jié)點減少，網(wǎng)絡(luò)吞吐量下降。所以需要一種機(jī)制來激勵鄰居節(jié)點參與合作轉(zhuǎn)發(fā)。

4 基于合作評估函數(shù)的CGTFT策略

4.1 時隙博弈與重復(fù)博弈

首先作如下假設(shè)：

（1）網(wǎng)絡(luò)中節(jié)點均為理性自私節(jié)點。

（2）網(wǎng)絡(luò)為離散時間模型，每個時隙t內(nèi)均為一次博弈過程，博弈策略相同。

（3）整個網(wǎng)絡(luò)G有N個節(jié)點隨機(jī)分布，且節(jié)點僅有有限能量，初始能量為Ei。

（4）假設(shè)傳輸數(shù)據(jù)包傳輸失敗主要是節(jié)點的自私和不合作所致。

數(shù)據(jù)從源節(jié)點S發(fā)送至目的節(jié)點D，需要一個或多個中間節(jié)點概率性轉(zhuǎn)發(fā)。假設(shè)節(jié)點 j根據(jù)自身情況決定對數(shù)據(jù)包是轉(zhuǎn)發(fā)還是丟棄，節(jié)點i將給予r的獎勵來激勵節(jié)點 j轉(zhuǎn)發(fā)數(shù)據(jù)，同時節(jié)點 j付出s能源來完成轉(zhuǎn)發(fā)。上述情況中，時隙博弈相當(dāng)于囚徒困境，節(jié)點在博弈中追求利益最大化，最終選擇(0,0)策略達(dá)到納什均衡。時隙博弈收益和策略見表1。

表1 博弈收益和策略

機(jī)會路由中，每個節(jié)點由于能源等限制，趨向于不參與合作，選擇自私，單次博弈無法激勵自私節(jié)點。實際網(wǎng)絡(luò)中，所有節(jié)點都周期性選擇策略，這樣對于所有節(jié)點，形成無限重復(fù)博弈；當(dāng)博弈結(jié)束時間無法預(yù)期，節(jié)點將評估其采取的策略對其將來收益的影響。

假設(shè)一個節(jié)點接受轉(zhuǎn)發(fā)概率為 f,f=0表示拒絕轉(zhuǎn)發(fā)，f=1表示接受所有轉(zhuǎn)發(fā)請求。任意一個節(jié)點用i表示，則-i表示博弈對方節(jié)點。若時隙tn節(jié)點收益為：

則重復(fù)博弈收益函數(shù)為：

當(dāng)經(jīng)過重復(fù)博弈后，網(wǎng)絡(luò)中節(jié)點都趨向合作，采取合作策略，接受轉(zhuǎn)發(fā)請求，則節(jié)點i重復(fù)博弈后的收益函數(shù)為：

4.2 合作度評估函數(shù)

由于機(jī)會路由中移動節(jié)點動態(tài)拓?fù)浼版溌返牟淮_定性，數(shù)據(jù)會傳輸失敗及重傳。定義節(jié)點i成功轉(zhuǎn)發(fā)數(shù)據(jù)包為pis(t)，接收數(shù)據(jù)包為 pir(t)，則該節(jié)點時隙t時數(shù)據(jù)包成功轉(zhuǎn)發(fā)概率為：

在面對節(jié)點的路由請求時，自私節(jié)點在博弈時有下列傾向：其一，自私節(jié)點更愿意選擇轉(zhuǎn)發(fā)成功率高以及能量高的鄰居節(jié)點作為備選節(jié)點來轉(zhuǎn)發(fā)數(shù)據(jù)包。其二，鄰居節(jié)點的合作水平與其獲得的效益相關(guān)，獲得的效益越大，那么其接受請求的概率也越高。為了選出趨向合作的下一跳節(jié)點，本文定義合作度評估函數(shù)（以下簡稱合作度），見公式（5）：

4.3 基于合作度評估函數(shù)的CGTFT策略

針鋒相對TFT[12]是重復(fù)博弈的一個典型策略。思想如下：博弈雙方節(jié)點i和 j，在某一時隙節(jié)點i的策略總是參照上一個時隙對方節(jié)點 j采用的策略；若 j選擇轉(zhuǎn)發(fā)，i也選擇轉(zhuǎn)發(fā)策略，若 j拒絕，i亦拒絕。該策略中，節(jié)點一旦進(jìn)入懲罰期，無法恢復(fù)合作狀態(tài)。而GTFT策略是在TFT策略的基礎(chǔ)上添加遺忘因子g來幫助節(jié)點恢復(fù)合作。

本文結(jié)合合作度評估函數(shù)與GTFT思想，建立CGTFT博弈激勵策略，以鄰居節(jié)點的合作度作為博弈判斷的標(biāo)準(zhǔn)。在博弈中，添加遺忘因子g到策略中，使節(jié)點具有恢復(fù)合作機(jī)制，模型化基于合作度評估函數(shù)的CGTFT策略如下所示，其中表示鄰居節(jié)點的合作度評價函數(shù)，m=[(1 -p)g]且假定為偶數(shù)：

當(dāng)網(wǎng)絡(luò)中每個節(jié)點均采用CGTFT策略，若節(jié)點i單方面改變其接受請求概率，則其合作度評估函數(shù)也會隨之改變，令節(jié)點合作度評估函數(shù)為 p，那么其對手節(jié)點根據(jù)CGTFT策略做出響應(yīng)：（1）對節(jié)點行為輕微程度的偏離，p≥1-g，將會容忍，其正常轉(zhuǎn)發(fā)數(shù)據(jù)；（2）對節(jié)點行為偏離程度較大的節(jié)點，p＜1-g，定義為不合作，其對手將會調(diào)整合作度至 p+g。表2為單次不合作的博弈策略。

表2 CGTFT單次不合作博弈策略

根據(jù)公式（2）得，CGTFT策略中單次不合作時，節(jié)點i收益函數(shù)：

經(jīng)過CGTFT策略激勵后，重復(fù)博弈趨向合作平衡時需滿足：

因為g＞0且0＜δ＜1，上式可轉(zhuǎn)換為：

因為上式兩括號內(nèi)多項式均大于0，所以CGTFT激勵策略激勵節(jié)點達(dá)到合作平衡的條件是：

假設(shè)機(jī)會路由中所有節(jié)點均遵從CGTFT博弈激勵策略，若符合平衡臨界條件r/s＞H，節(jié)點i以任意概率接受請求，0＜p＜1，那么節(jié)點單方面改變獲得的收益都小于采取合作獲得的收益，最終節(jié)點將趨向于選擇合作，達(dá)到納什均衡，起到抑制自私行為的目的。

在CGTFT策略中，在滿足該策略平衡臨界條件下，遺忘因子g的降低以及貼現(xiàn)因子δ的增加都有利于抑制自私行為，從而促使各節(jié)點趨向于合作。證明如下：在公式（8）中，對ECGTFT求g偏導(dǎo)，在r,s,p,δ等參數(shù)不變情況下，降低g導(dǎo)致ECGTFT增加，即自私行為受到懲罰將增加；對ECGTFT求δ偏導(dǎo)，在r,s,p,g等參數(shù)不變情況下，增加δ導(dǎo)致ECGTFT的增加，即采取自私行為所受懲罰增大。在CGTFT中，除了貼現(xiàn)因子δ外，遺忘因子g對自私行為所受懲罰有重要影響，g的大小影響節(jié)點采取自私行為后恢復(fù)合作狀態(tài)所需要的單階段博弈次數(shù)，g越小，恢復(fù)合作所需要的博弈次數(shù)越多，遭受的懲罰期越長。

4.4 基于合作度評價函數(shù)的CGTFT博弈算法

本文的博弈算法是網(wǎng)絡(luò)中數(shù)據(jù)包發(fā)送節(jié)點與鄰居節(jié)點之間，通過CGTFT策略進(jìn)行兩兩博弈的過程，博弈的判斷標(biāo)準(zhǔn)是本文提出的鄰居節(jié)點合作度評價函數(shù)，網(wǎng)絡(luò)中所有節(jié)點都將周期性地選擇策略，整體上看，形成一個重復(fù)博弈的過程。其算法的具體流程描述如下所示[13-14]：

（1）初始化參數(shù)。

（2）源點向鄰居節(jié)點廣播發(fā)送路由請求，以及評估各鄰居節(jié)點的合作度。

（3）對比ExOR候選集中所有節(jié)點的合作度，將合作度低于閾值 pthreshold節(jié)點排除出候選集，然后選取ETX值最大的節(jié)點為下一跳轉(zhuǎn)發(fā)節(jié)點。

（4）對于該節(jié)點采取何種行為，根據(jù)本文的CGTFT策略可知，該源點即對手在上個時隙合作度是 p，若p≥1-g，則容忍行為偏離，執(zhí)行轉(zhuǎn)發(fā)策略，并跳轉(zhuǎn)（6）。

（5）若 p＜1-g，則定義該節(jié)點為自私節(jié)點，下個時隙該節(jié)點的對手節(jié)點將采取 p+g的合作度執(zhí)行策略，后面過程重復(fù)CGTFT策略。

（6）重復(fù)（2）到（6）步驟，直到數(shù)據(jù)到達(dá)目的節(jié)點，算法結(jié)束。

5 仿真實驗分析

本文運(yùn)用NS2進(jìn)行仿真實驗，其中MAC層協(xié)議采用IEEE802.11協(xié)議[15]。機(jī)會路由ExOR協(xié)議中節(jié)點隨機(jī)分布，節(jié)點都遵循相同的博弈策略。網(wǎng)絡(luò)中節(jié)點運(yùn)動按照Random Waypoint Model方式移動。規(guī)定在網(wǎng)絡(luò)生命周期內(nèi)，節(jié)點進(jìn)入懲罰期，節(jié)點可能由于能量耗盡或者過于自私原因，在本文的CGTFT策略激勵下，節(jié)點仍然無法重建，恢復(fù)合作，定義該節(jié)點死亡。其他仿真參數(shù)如表3所示。

表3 仿真參數(shù)

本文選擇的性能評價指標(biāo)是網(wǎng)絡(luò)生命周期的節(jié)點數(shù)變化情況、網(wǎng)絡(luò)總能耗變化情況以及不同比例自私節(jié)點情況下的吞吐量變化情況。

為了證實本文提出的CGTFT策略對節(jié)點自私行為的激勵效果，本文仿真了r/s=4,g=0.01,δ=0.6時策略性能比較[16]。圖1說明的是隨著博弈輪數(shù)的增加，網(wǎng)絡(luò)生命周期中的節(jié)點數(shù)變化情況。從圖1可知，隨著博弈輪數(shù)的增加，本文的CGTFT重復(fù)博弈策略的節(jié)點死亡數(shù)低于囚徒困境（TFT）策略，尤其在博弈前期，TFT策略中死亡節(jié)點增速明顯高于本文的CGTFT策略。原因有兩個：其一，本文在合作度評估函數(shù)中具有能量模型，剩余能量對節(jié)點的合作度評估有較大的影響，避免能耗不均衡和部分節(jié)點能量快速耗盡，一定程度上延長了節(jié)點生命時間。其二，本文CGTFT策略中提供合作重建機(jī)制，其策略中具有遺忘因子g，節(jié)點進(jìn)入懲罰期后，經(jīng)過一定周期，節(jié)點會恢復(fù)合作。

圖1 網(wǎng)絡(luò)生命周期

圖2說明的是網(wǎng)絡(luò)總能量消耗情況。從圖2可知，與TFT策略相比，本文CGTFT策略下的能耗增加總體比較平緩，并且總能耗也低于前者。這是因為在本文的鄰居節(jié)點合作度評估函數(shù)的定義中，考慮了成功轉(zhuǎn)發(fā)率以及能量因素，在路由選擇時，節(jié)點會選擇合作度高的節(jié)點轉(zhuǎn)發(fā)，一方面其成功轉(zhuǎn)發(fā)率高，減少傳輸失敗再重傳的能耗；另一方面能量模型可以均衡節(jié)點能源消耗，盡量避免節(jié)點能耗過低導(dǎo)致的傳輸失敗，繼而再重傳的耗能。

圖2 網(wǎng)絡(luò)總能耗

圖3給出的是在不同比例自私節(jié)點情況下，網(wǎng)絡(luò)吞吐量累計分布情況。從100個節(jié)點中隨機(jī)選取匹配發(fā)送節(jié)點和目的節(jié)點，統(tǒng)計發(fā)送數(shù)據(jù)包100次的結(jié)果，仿真比較以下三種情況的吞吐量累計分布：ExOR協(xié)議沒添加激勵策略時，網(wǎng)絡(luò)中分別存在20%和40%自私節(jié)點的吞吐量分布情況以及添加本文提出的CGTFT激勵策略時的吞吐量分布情況。仿真重復(fù)實驗5次，最終結(jié)果取平均值。如圖3所示，當(dāng)自私節(jié)點比例增加到40%。曲線左移，吞吐量較低，所占比例明顯增多。而當(dāng)加入本文的CGTFT激勵機(jī)制后，節(jié)點選擇合作度較高的節(jié)點來轉(zhuǎn)發(fā)。CGTFT激勵策略下網(wǎng)絡(luò)吞吐量和20%和40%自私節(jié)點時候相比，較高吞吐量所占比例有明顯提升；其中，在CGTFT激勵策略下，超過90%的鏈路吞吐量達(dá)到52數(shù)據(jù)包每秒。而無激勵時吞吐量分別為30和41個包每秒，主要因為合作度高的節(jié)點轉(zhuǎn)發(fā)成功率較高，而且均衡節(jié)點能量消耗，整體上提高了網(wǎng)絡(luò)性能。

圖3 吞吐量累計分布

6 總結(jié)

本文提出了一種基于鄰居節(jié)點合作度評估函數(shù)的CGTFT重復(fù)博弈模型。對于網(wǎng)絡(luò)中的理性節(jié)點，從節(jié)點剩余能量，成功轉(zhuǎn)發(fā)概率角度設(shè)計了合作度評估函數(shù)概念，然后通過CGTFT重復(fù)博弈策略進(jìn)行博弈，對網(wǎng)絡(luò)中參與合作轉(zhuǎn)發(fā)的節(jié)點給予一定收益，對自私不合作節(jié)點給予一定周期的懲罰，并添加了遺忘因子，對進(jìn)入懲罰期的節(jié)點進(jìn)行合作重建。仿真表明，該激勵機(jī)制能夠有效迫使網(wǎng)絡(luò)中自私節(jié)點參與合作，提高吞吐量以及網(wǎng)絡(luò)性能。

：

[1]Akyildiz I F，Wang X.A survey on wireless mesh networks[J].IEEE Communications Magazine，2005，43（9）.

[2]田克，張寶賢，馬建，等.無線多跳網(wǎng)絡(luò)中的機(jī)會路由[J].軟件學(xué)報，2010，21（10）：2542-2553.

[3]Biswas S，Morris R.ExOR：opportunistic multi-hop routing for wireless networks[J].ACM Special Interest Group on Data Communication，2005，35（4）：133-144.

[4]Rozner E，Seshadri J，Mehta Y，et al.SOAR：Simple Opportunistic Adaptive Routing protocol for Wireless Mesh Networks[J].IEEE TransactionsonMobileComputing，2009，8（12）：1622-1635.

[5]Chachulski S，Jennings M，Katti S，et al.Trading structure for randomness in wireless opportunistic routing[J].ACM Special Interest Group on Data Communication，2007，37（4）：169-180.

[6]Chen K，Nahrstedt K.iPass：an incentive compatible auction scheme to enable packet forwarding service in MANET[C]//InternationalConferenceonDistributedComputing Systems，2004：534-542.

[7]Anderegg L，Eidenbenz S.Ad hoc-VCG：a truthful and cost-efficient routing protocol for mobile ad hoc networks with selfish agents[C]//InternationalConference on Mobile Computing and Networking，2003：245-259.

[8]Han Z，Pandana C，Liu K J，et al.A self-learning repeated game framework for optimizing packet forwarding networks[C]//Wireless Communications and Networking Conference，2005：2131-2136.

[9]Wu F，Gong K，Zhang T，et al.COMO：a game-theoretic approach for joint multirate opportunistic routing and forwarding in non-cooperative wireless networks[J].IEEE Transactions on Wireless Communications，2015，14（2）：948-959.

[10]Dapeng Q U，Wang X，Huang M，et al.Selfish node detection and incentive mechanism in mobile P2P networks：selfish node detection and incentive mechanism in mobile P2P networks[J].Journal of Software，2014，24（4）：887-899.

[11]Zhang K，Wang R，Qian D，et al.AIM：an auction incentive mechanism in wireless networks with opportunistic routing[C]//Computational Science and Engineering，2010：28-33.

[12]Srivastava V，Neel J，Mackenzie A B，et al.Using game theory to analyze wireless ad hoc networks[J].Communications Surveys&Tutorials，2005，7（4）：46-56.

[13]Wu F，Chen T，Zhong S，et al.A game-theoretic approach to stimulate cooperation for probabilistic routing in opportunistic networks[J].IEEE Transactions on Wireless Communications，2013，12（4）：1573-1583.

[14]Froushani M H，Khalaj B H，Vakilinia S，et al.A novel approach to incentive-based cooperation in wireless ad hoc networks[C]//international Conference on Telecommunications，2011：78-83.

[15]Yan L，Hailes S，Capra L，et al.Analysis of packet relaying models and incentive strategies in wireless ad hoc networkswithgametheory[C]//AdvancedInformation Networking and Applications，2008：1062-1069.

[16]Sun Yuxing.On incentive strategies for trust recommendations in wireless ad hoc networks with probability game[J].Computer Science，2011，38（4）：65-71.