WMNs中基于重復博弈的機會路由激勵機制研究

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

南京工業大學 計算機科學與技術學院，南京 211816

1 引言

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

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

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

2 相關研究

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

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

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

3 機會路由中節點自私性分析

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

上述不合作的自私行為將導致機會路由候選集中節點減少，網絡吞吐量下降。所以需要一種機制來激勵鄰居節點參與合作轉發。

4 基于合作評估函數的CGTFT策略

4.1 時隙博弈與重復博弈

首先作如下假設：

（1）網絡中節點均為理性自私節點。

（2）網絡為離散時間模型，每個時隙t內均為一次博弈過程，博弈策略相同。

（3）整個網絡G有N個節點隨機分布，且節點僅有有限能量，初始能量為Ei。

（4）假設傳輸數據包傳輸失敗主要是節點的自私和不合作所致。

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

表1 博弈收益和策略

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

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

則重復博弈收益函數為：

當經過重復博弈后，網絡中節點都趨向合作，采取合作策略，接受轉發請求，則節點i重復博弈后的收益函數為：

4.2 合作度評估函數

由于機會路由中移動節點動態拓撲及鏈路的不確定性，數據會傳輸失敗及重傳。定義節點i成功轉發數據包為pis(t)，接收數據包為 pir(t)，則該節點時隙t時數據包成功轉發概率為：

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

4.3 基于合作度評估函數的CGTFT策略

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

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

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

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

根據公式（2）得，CGTFT策略中單次不合作時，節點i收益函數：

經過CGTFT策略激勵后，重復博弈趨向合作平衡時需滿足：

因為g＞0且0＜δ＜1，上式可轉換為：

因為上式兩括號內多項式均大于0，所以CGTFT激勵策略激勵節點達到合作平衡的條件是：

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

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

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

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

（1）初始化參數。

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

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

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

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

（6）重復（2）到（6）步驟，直到數據到達目的節點，算法結束。

5 仿真實驗分析

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

表3 仿真參數

本文選擇的性能評價指標是網絡生命周期的節點數變化情況、網絡總能耗變化情況以及不同比例自私節點情況下的吞吐量變化情況。

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

圖1 網絡生命周期

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

圖2 網絡總能耗

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

圖3 吞吐量累計分布

6 總結

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

：

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

[2]田克，張寶賢，馬建，等.無線多跳網絡中的機會路由[J].軟件學報，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.