0 引言

    機會網絡^[1-2]是一種不需要在源節點和目的節點之間存在完整鏈路、利用節點移動帶來的相遇機會實現通信的時延和分裂可容忍的無線自組織網絡，在軍事、災難救助以及偏遠野外地區等領域有著廣泛的應用。目前，機會網絡的研究是基于節點具有良好的協作性，然而，由于機會網絡中節點的資源有限，為節約資源，節點都存在一定的自私性，自私節點通常會拒絕為其他節點轉發消息，這種自私行為勢必會嚴重影響機會網絡正常的路由和數據轉發功能，從而導致網絡性能退化。

    目前，國內外對于含自私節點的機會網絡的研究已經取得了一些成果，人們提出了各種激勵機制來激勵節點協作^[3-7]，尤其是近年來越來越多地采用了經濟學方法中的博弈理論^[4-6]。基于Barter機制的算法是一類典型的基于博弈論的機會網絡路由算法，該算法基于互惠機制，博弈雙方互相交換彼此感興趣或者具有潛在價值的消息。BUTTYAN L等^[4]提出了Barter機制，主要用于激勵網絡中自私節點對自己不感興趣分組的“存儲-攜帶-轉發”。LIN C S等^[5]提出了基于Barter機制的針對對等網絡(P2P)流媒體系統中自私節點的機制。ZHANG C等^[6]結合信譽機制中虛擬貨幣交易的特點改進了原始Barter機制，提出了一種全新的激勵范式C4，但未考慮分布式網絡中節點的自私性。由上可知，現有基于Barter機制的路由算法仍然是僅考慮兩兩節點間進行的交易，未考慮分組交易存在的僵局問題，有進一步改善的需要。

    本研究基于上述研究成果，并在文獻[4]的基礎上，提出了一種全新的角度——基于協作中繼的博弈模型，對歸一化時間內的機會網絡吞吐量及時延進行了分析，仿真實驗證實了本模型的有效性。

1 網絡模型與問題描述

1.1 系統描述

    設任一含自私節點的機會網絡中，自私節點只轉發自己感興趣的數據分組。BUTTYAN L等^[4]提出任何分組都有其潛在價值，當前不感興趣的分組將來可用來交換感興趣的分組。在Barter機制中，節點感興趣的分組初始價值量為1，不感興趣的分組初始價值量是自身采取的博弈策略S_i={S₁，S₂，…，S_m}（0＜S_i＜1）。部分變量定義如表1所示。

1.2 機會網絡的博弈模型

    含自私節點的機會網絡中節點具有自私而有理性的特點，在模型方面與傳統的機會網絡有所不同，故作出如下定義。

    定義1 博弈模型：機會網絡的博弈模型為G=[V，{S_i}，{π_i}]；其中，節點集合V={v₁，v₂，…，v_n}，n>1，即為博弈參與者；策略集合S_i={S₁，S₂，…，S_m}，1≤m≤n(n-1)，表示節點對自己不感興趣分組與感興趣分組的比值；收益函數?仔i(S1，S2，…，Sm)表示網絡中參與者采取策略后網絡的實際吞吐量。

    定義2 數據分組屬性：含自私節點的機會網絡中，數據分組主要有兩種屬性：分組興趣屬性ζ(0<ζ<<1)與分組價值折扣屬性(見式(3))。

    定義3 實際吞吐量模型：實際吞吐量G_i(0≤G_i(t)≤1)是節點i在每個歸一化時間內成功傳遞分組獲得的累計價值，節點i的該值可以在一個理想的情況下表示為：

    在RACR中，博弈參與者的收益只依賴于其選擇的博弈策略，且博弈參與者在其策略空間中選取惟一確定的策略進行博弈，因此，這個博弈有對稱的純策略均衡解。

    綜上分析可知，不難判斷一個策略組合{s′}是否是納什均衡。對任意參與者i(i∈V)，若i采取背叛策略能夠獲得更多的收益，則{s′}不是納什均衡。由于參與者具有相同的收益函數，若{s′}是參與者i的最優策略，則{s′}也是其他參與者的最優策略。

1.3 問題描述

    (1)僵局問題：由于交易的公平性要求，分組交換由可交換數目小的一方決定，進行等量交換。若一個節點有分組需要轉發，對方節點無該節點需要的分組或無足夠分組與前者交換，將導致網絡陷入僵局，造成網絡等待時延，稱之為“僵局問題”。

    (2)現有的Barter機制在數據分組交易過程中存在冗余交互操作。

    (3)根據現有Barter機制，價值量達到某一閾值的消息就簡單丟棄，然而，這樣很可能刪除即將到達目的地址的分組，增大了消息傳輸時延。

2 RACR算法

    本文提出一種基于協作中繼的高吞吐量機會網絡路由算法——RACR。RACR算法采用引入協作中繼節點的轉發方式，對分組交易僵局問題加以有效解決，并重新設計滿足協作中繼的分組交易過程，引入多方交易以激活數據分組的單向傳遞，從而削減數據分組傳遞次數。同時，對價值量小于閾值的分組先判斷其目的地址是否是鄰居節點，從而提高分組傳送成功率，降低數據分組傳輸時延。

2.1 RACR算法新機制

2.1.1 協作中繼

    RACR算法針對現有Barter路由算法分組交易過程中的交易僵局問題，引入協作中繼機制加以解決。考慮如下網絡場景：假設節點u、v已完成兩兩之間的交易或節點u、v不存在相應的分組交易，若節點v仍有節點u需要而不能與之交易的分組。同時，節點u、v收到共同的鄰居節點w廣播的目的地址為v的分組索引，若節點w在節點v與w、u與w兩兩交易完成后，節點u、v根據節點w的分組索引計算發現節點w仍有節點v需要的分組，同時節點u也有節點w需要的分組。

    協作中繼節點的選取思路為：當網絡出現上述情況時，如圖1(a)所示，根據Barter算法的原理，消息交易將陷入僵局。圖1(b)表示RACR算法的分組交易示意圖，如果網絡出現上述情況，則節點w將會向節點v發送一個額外分組，節點v收到節點w發送的額外分組后會給節點u發送一個額外分組。最后，節點u給節點w需要的一個額外的分組。若存在能滿足以上描述條件的節點，即是協作中繼節點。

2.1.2 分組傳遞次數削減

    RACR算法引入多方交易以激活數據分組的單向傳遞，對數據分組的傳遞次數進行削減。考慮如下網絡場景：節點u、v和w在同一通信范圍內，節點u需要通過節點v交易獲取節點v中的分組，節點v需要獲取節點u中的分組用來交換節點w中的分組，同時節點u也有節點w需要的分組。

    分組傳遞次數削減思路為：當網絡出現上述情況時，如圖1（a）所示，在Barter路由算法中，中間節點v進行一次分組交換需要收、發2個分組才能完成交易。如圖1（b）所示，在RACR算法中，首先發現節點間存在上述關系的節點向需要自身數據分組的節點發送一個數據分組，收到該額外分組的理性節點進行相同的操作，最后完成一個公平的交易。則RACR算法的中間節點v僅需要收、發1個分組，從而實現分組傳遞次數的削減，減少數據分組的冗余交互操作。

2.1.3 分組刪除判定優化

    原始Barter路由算法中，節點對價值小于分組刪除閾值的數據分組采取簡單的丟棄策略。然而，雖然刪除的分組價值量小，但很有可能即將到達分組的目的節點。在RACR算法中，節點對價值量低于刪除閾值的分組，首先判斷該分組的目的地址是否為該節點的鄰居節點，若是則發起新的分組交易，否則直接刪除該分組。這樣在不影響網絡開銷的前提下，提高網絡吞吐量，同時降低傳輸時延。

2.2 RACR算法操作

    RACR算法主要操作步驟如下：

    (1)節點u、v相遇，按Barter機制兩兩之間交易完畢。此時，若節點v仍有節點u需要而不能與之交易的分組，則進行步驟(2)，否則結束；

    (2)節點u、v收到公共鄰居節點w發送的分組索引，根據節點w的分組索引計算判斷節點w是否符合協作中繼節點的要求。若符合，則進行步驟(3)，否則結束；

    (3)若節點u通過計算，最先獲知協作中繼節點w的參與情況。節點u向節點w發送一個節點w需要的分組，節點w收到u發送的分組后，立即向節點v發送一個節點v需要的分組。同理，節點v向節點u發送一個u需要的分組。

3 仿真

3.1 仿真環境

    本文使用OPNET軟件作為仿真平臺，選取Barter算法^[4]和DT算法^[8]作為比較對象，在相同仿真條件下分析比較它們的網絡吞吐量、時延等性能。主要仿真參數設置如表2所示。

3.2 仿真結果及分析

    (1)歸一化網絡吞吐量

    由圖2可知，與DT算法和Barter算法相比，RACR算法在網絡吞吐量上提高了7.9%以上。主要原因是：①采用協作中繼機制，從而選取合適的協作中繼節點，對分組交易僵局問題加以有效解決；②對價值量小于刪除閾值的分組首先判斷其目的地址是否為鄰居節點，若是則發起新的分組交易，從而提高網絡吞吐量。

    (2)分組平均端到端時延

    由圖3可知，RACR算法的分組平均端到端時延低于DT和Barter算法。主要原因是：①RACR算法通過引入協作中繼節點，解決了交易的僵局問題，有效地減少網絡等待時延；②分組傳遞次數削減機制通過引入多方交易以激活數據分組的單向傳遞，從而加快數據分組的交換，縮短數據分組交換的時延。

    (3)歸一化控制開銷

    由圖4可知，RACR算法能夠明顯減少歸一化控制開銷。開銷減少的原因主要是RACR協議引入協作中繼節點，提高了消息的交付率，減少了消息在網絡中的傳輸的平均跳數。同時，優化了分組交易機制，削減了分組交換次數，減少了消息交易過程中的額外開銷，從而降低歸一化控制開銷。

    (4)分組傳送成功率

    由圖5可知，與DT算法和Barter算法相比，RACR算法顯著提高了分組傳送成功率。主要原因是：①引入協作中繼節點，增加了分組交易機會；②優化分組刪除判定機制，刪除緩存消息之前先判斷其目的地址是否是其鄰居節點，若是則重新發起分組交易，從而提高了數據分組傳送成功率。

4 結束語

    本文通過深入研究博弈理論在含有自私節點的機會網絡的應用，提出了一種基于協作中繼的高吞吐量機會網絡路由算法RACR。RACR算法通過在Barter機制中采用協作中繼機制并引入多方交易以激活數據分組的單向傳遞，同時優化分組刪除的判定條件。仿真結果顯示，與DT路由算法和Barter路由算法相比，RACR算法能夠更加有效地促使含自私節點的機會網絡進行數據分組交易，從而增加網絡吞吐量，降低數據分組端到端時延。

參考文獻

[1] XIONG Y P，SUN L M，NIU J W，et al.Opportunistic networks[J].Journal of Software，2009，20(1)：124-137.

[2] 任智，黃勇，陳前斌.機會網絡路由協議[J].計算機應用，2010，30(3)：723-728.

[3] 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.

[4] BUTTYAN L，DORA L，FELEGYHAZI M，et al.Barter trade improves message delivery in opportunistic networks[J].Ad Hoc Networks，2010，8(1)：1-14.

[5] LIN C S，CHENG Y C.A Barter-based incentive mechanism for peer-to-peer media streaming[C].The 13th IEEE International Symposium on Consumer Electronics.Kyoto：IEEE Press，2009：871-875.

[6] ZHANG C，ZHU X，SONG Y，et al.C4：A new paradigm for providing incentives in multi-hop wireless networks[C].INFOCOM，2011 Proceedings IEEE.Shanghai：IEEE Press，2011：918-926.

[7] 劉期烈，候鵬翔.機會網絡中激勵節點檢測策略研究[J].重慶郵電大學學報(自然科學報)，2015，27(2)：266-272.

[8] SPYROPOULOS T，PSOUNIS K，RAGHAVENDRA C S.Efficient routing in intermittently connected mobile networks：the single-copy case[J].IEEE/ACM Transactions on Networking，2008，16(1)：63-76.

作者信息:

任  智，王中永，張  勇 

（重慶郵電大學 移動通信技術重慶市重點實驗室，重慶400065）