0 引言

    機(jī)會(huì)網(wǎng)絡(luò)^[1-2]是一種不需要在源節(jié)點(diǎn)和目的節(jié)點(diǎn)之間存在完整鏈路,、利用節(jié)點(diǎn)移動(dòng)帶來(lái)的相遇機(jī)會(huì)實(shí)現(xiàn)通信的時(shí)延和分裂可容忍的無(wú)線自組織網(wǎng)絡(luò)，在軍事,、災(zāi)難救助以及偏遠(yuǎn)野外地區(qū)等領(lǐng)域有著廣泛的應(yīng)用,。目前，機(jī)會(huì)網(wǎng)絡(luò)的研究是基于節(jié)點(diǎn)具有良好的協(xié)作性,，然而,，由于機(jī)會(huì)網(wǎng)絡(luò)中節(jié)點(diǎn)的資源有限，為節(jié)約資源,，節(jié)點(diǎn)都存在一定的自私性,，自私節(jié)點(diǎn)通常會(huì)拒絕為其他節(jié)點(diǎn)轉(zhuǎn)發(fā)消息，這種自私行為勢(shì)必會(huì)嚴(yán)重影響機(jī)會(huì)網(wǎng)絡(luò)正常的路由和數(shù)據(jù)轉(zhuǎn)發(fā)功能,，從而導(dǎo)致網(wǎng)絡(luò)性能退化,。

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

    本研究基于上述研究成果,，并在文獻(xiàn)[4]的基礎(chǔ)上，提出了一種全新的角度——基于協(xié)作中繼的博弈模型,，對(duì)歸一化時(shí)間內(nèi)的機(jī)會(huì)網(wǎng)絡(luò)吞吐量及時(shí)延進(jìn)行了分析,，仿真實(shí)驗(yàn)證實(shí)了本模型的有效性。

1 網(wǎng)絡(luò)模型與問(wèn)題描述

1.1 系統(tǒng)描述

    設(shè)任一含自私節(jié)點(diǎn)的機(jī)會(huì)網(wǎng)絡(luò)中,，自私節(jié)點(diǎn)只轉(zhuǎn)發(fā)自己感興趣的數(shù)據(jù)分組,。BUTTYAN L等^[4]提出任何分組都有其潛在價(jià)值，當(dāng)前不感興趣的分組將來(lái)可用來(lái)交換感興趣的分組,。在Barter機(jī)制中,，節(jié)點(diǎn)感興趣的分組初始價(jià)值量為1，不感興趣的分組初始價(jià)值量是自身采取的博弈策略S_i={S₁,，S₂,，…，S_m}（0＜S_i＜1）,。部分變量定義如表1所示,。

1.2 機(jī)會(huì)網(wǎng)絡(luò)的博弈模型

    含自私節(jié)點(diǎn)的機(jī)會(huì)網(wǎng)絡(luò)中節(jié)點(diǎn)具有自私而有理性的特點(diǎn)，在模型方面與傳統(tǒng)的機(jī)會(huì)網(wǎng)絡(luò)有所不同,，故作出如下定義,。

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

    定義2 數(shù)據(jù)分組屬性：含自私節(jié)點(diǎn)的機(jī)會(huì)網(wǎng)絡(luò)中,，數(shù)據(jù)分組主要有兩種屬性：分組興趣屬性ζ(0<ζ<<1)與分組價(jià)值折扣屬性(見(jiàn)式(3))。

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

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

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

1.3 問(wèn)題描述

    (1)僵局問(wèn)題：由于交易的公平性要求，分組交換由可交換數(shù)目小的一方?jīng)Q定,，進(jìn)行等量交換,。若一個(gè)節(jié)點(diǎn)有分組需要轉(zhuǎn)發(fā)，對(duì)方節(jié)點(diǎn)無(wú)該節(jié)點(diǎn)需要的分組或無(wú)足夠分組與前者交換,，將導(dǎo)致網(wǎng)絡(luò)陷入僵局,，造成網(wǎng)絡(luò)等待時(shí)延，稱之為“僵局問(wèn)題”,。

    (2)現(xiàn)有的Barter機(jī)制在數(shù)據(jù)分組交易過(guò)程中存在冗余交互操作,。

    (3)根據(jù)現(xiàn)有Barter機(jī)制，價(jià)值量達(dá)到某一閾值的消息就簡(jiǎn)單丟棄,，然而,，這樣很可能刪除即將到達(dá)目的地址的分組，增大了消息傳輸時(shí)延,。

2 RACR算法

    本文提出一種基于協(xié)作中繼的高吞吐量機(jī)會(huì)網(wǎng)絡(luò)路由算法——RACR,。RACR算法采用引入?yún)f(xié)作中繼節(jié)點(diǎn)的轉(zhuǎn)發(fā)方式，對(duì)分組交易僵局問(wèn)題加以有效解決,，并重新設(shè)計(jì)滿足協(xié)作中繼的分組交易過(guò)程,，引入多方交易以激活數(shù)據(jù)分組的單向傳遞，從而削減數(shù)據(jù)分組傳遞次數(shù),。同時(shí),，對(duì)價(jià)值量小于閾值的分組先判斷其目的地址是否是鄰居節(jié)點(diǎn),，從而提高分組傳送成功率，降低數(shù)據(jù)分組傳輸時(shí)延,。

2.1 RACR算法新機(jī)制

2.1.1 協(xié)作中繼

    RACR算法針對(duì)現(xiàn)有Barter路由算法分組交易過(guò)程中的交易僵局問(wèn)題,，引入?yún)f(xié)作中繼機(jī)制加以解決?？紤]如下網(wǎng)絡(luò)場(chǎng)景：假設(shè)節(jié)點(diǎn)u,、v已完成兩兩之間的交易或節(jié)點(diǎn)u、v不存在相應(yīng)的分組交易,，若節(jié)點(diǎn)v仍有節(jié)點(diǎn)u需要而不能與之交易的分組,。同時(shí)，節(jié)點(diǎn)u,、v收到共同的鄰居節(jié)點(diǎn)w廣播的目的地址為v的分組索引,，若節(jié)點(diǎn)w在節(jié)點(diǎn)v與w、u與w兩兩交易完成后,，節(jié)點(diǎn)u,、v根據(jù)節(jié)點(diǎn)w的分組索引計(jì)算發(fā)現(xiàn)節(jié)點(diǎn)w仍有節(jié)點(diǎn)v需要的分組，同時(shí)節(jié)點(diǎn)u也有節(jié)點(diǎn)w需要的分組,。

    協(xié)作中繼節(jié)點(diǎn)的選取思路為：當(dāng)網(wǎng)絡(luò)出現(xiàn)上述情況時(shí),，如圖1(a)所示，根據(jù)Barter算法的原理,，消息交易將陷入僵局,。圖1(b)表示RACR算法的分組交易示意圖，如果網(wǎng)絡(luò)出現(xiàn)上述情況,，則節(jié)點(diǎn)w將會(huì)向節(jié)點(diǎn)v發(fā)送一個(gè)額外分組,，節(jié)點(diǎn)v收到節(jié)點(diǎn)w發(fā)送的額外分組后會(huì)給節(jié)點(diǎn)u發(fā)送一個(gè)額外分組。最后,，節(jié)點(diǎn)u給節(jié)點(diǎn)w需要的一個(gè)額外的分組,。若存在能滿足以上描述條件的節(jié)點(diǎn),，即是協(xié)作中繼節(jié)點(diǎn),。

2.1.2 分組傳遞次數(shù)削減

    RACR算法引入多方交易以激活數(shù)據(jù)分組的單向傳遞，對(duì)數(shù)據(jù)分組的傳遞次數(shù)進(jìn)行削減,?？紤]如下網(wǎng)絡(luò)場(chǎng)景：節(jié)點(diǎn)u、v和w在同一通信范圍內(nèi),，節(jié)點(diǎn)u需要通過(guò)節(jié)點(diǎn)v交易獲取節(jié)點(diǎn)v中的分組,，節(jié)點(diǎn)v需要獲取節(jié)點(diǎn)u中的分組用來(lái)交換節(jié)點(diǎn)w中的分組，同時(shí)節(jié)點(diǎn)u也有節(jié)點(diǎn)w需要的分組,。

    分組傳遞次數(shù)削減思路為：當(dāng)網(wǎng)絡(luò)出現(xiàn)上述情況時(shí),，如圖1（a）所示,，在Barter路由算法中，中間節(jié)點(diǎn)v進(jìn)行一次分組交換需要收,、發(fā)2個(gè)分組才能完成交易,。如圖1（b）所示，在RACR算法中,，首先發(fā)現(xiàn)節(jié)點(diǎn)間存在上述關(guān)系的節(jié)點(diǎn)向需要自身數(shù)據(jù)分組的節(jié)點(diǎn)發(fā)送一個(gè)數(shù)據(jù)分組,，收到該額外分組的理性節(jié)點(diǎn)進(jìn)行相同的操作，最后完成一個(gè)公平的交易,。則RACR算法的中間節(jié)點(diǎn)v僅需要收,、發(fā)1個(gè)分組，從而實(shí)現(xiàn)分組傳遞次數(shù)的削減,，減少數(shù)據(jù)分組的冗余交互操作,。

2.1.3 分組刪除判定優(yōu)化

    原始Barter路由算法中，節(jié)點(diǎn)對(duì)價(jià)值小于分組刪除閾值的數(shù)據(jù)分組采取簡(jiǎn)單的丟棄策略,。然而,，雖然刪除的分組價(jià)值量小，但很有可能即將到達(dá)分組的目的節(jié)點(diǎn),。在RACR算法中,，節(jié)點(diǎn)對(duì)價(jià)值量低于刪除閾值的分組，首先判斷該分組的目的地址是否為該節(jié)點(diǎn)的鄰居節(jié)點(diǎn),，若是則發(fā)起新的分組交易,，否則直接刪除該分組。這樣在不影響網(wǎng)絡(luò)開(kāi)銷(xiāo)的前提下,，提高網(wǎng)絡(luò)吞吐量,，同時(shí)降低傳輸時(shí)延。

2.2 RACR算法操作

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

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

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

    (3)若節(jié)點(diǎn)u通過(guò)計(jì)算,，最先獲知協(xié)作中繼節(jié)點(diǎn)w的參與情況,。節(jié)點(diǎn)u向節(jié)點(diǎn)w發(fā)送一個(gè)節(jié)點(diǎn)w需要的分組，節(jié)點(diǎn)w收到u發(fā)送的分組后,，立即向節(jié)點(diǎn)v發(fā)送一個(gè)節(jié)點(diǎn)v需要的分組,。同理，節(jié)點(diǎn)v向節(jié)點(diǎn)u發(fā)送一個(gè)u需要的分組,。

3 仿真

3.1 仿真環(huán)境

    本文使用OPNET軟件作為仿真平臺(tái),，選取Barter算法^[4]和DT算法^[8]作為比較對(duì)象，在相同仿真條件下分析比較它們的網(wǎng)絡(luò)吞吐量,、時(shí)延等性能,。主要仿真參數(shù)設(shè)置如表2所示。

3.2 仿真結(jié)果及分析

    (1)歸一化網(wǎng)絡(luò)吞吐量

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

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

    由圖3可知,，RACR算法的分組平均端到端時(shí)延低于DT和Barter算法,。主要原因是：①RACR算法通過(guò)引入?yún)f(xié)作中繼節(jié)點(diǎn)，解決了交易的僵局問(wèn)題,，有效地減少網(wǎng)絡(luò)等待時(shí)延,；②分組傳遞次數(shù)削減機(jī)制通過(guò)引入多方交易以激活數(shù)據(jù)分組的單向傳遞，從而加快數(shù)據(jù)分組的交換,，縮短數(shù)據(jù)分組交換的時(shí)延,。

    (3)歸一化控制開(kāi)銷(xiāo)

    由圖4可知，RACR算法能夠明顯減少歸一化控制開(kāi)銷(xiāo),。開(kāi)銷(xiāo)減少的原因主要是RACR協(xié)議引入?yún)f(xié)作中繼節(jié)點(diǎn),，提高了消息的交付率，減少了消息在網(wǎng)絡(luò)中的傳輸?shù)钠骄鴶?shù),。同時(shí),，優(yōu)化了分組交易機(jī)制，削減了分組交換次數(shù),，減少了消息交易過(guò)程中的額外開(kāi)銷(xiāo)，從而降低歸一化控制開(kāi)銷(xiāo),。

    (4)分組傳送成功率

    由圖5可知,，與DT算法和Barter算法相比,，RACR算法顯著提高了分組傳送成功率。主要原因是：①引入?yún)f(xié)作中繼節(jié)點(diǎn),，增加了分組交易機(jī)會(huì),；②優(yōu)化分組刪除判定機(jī)制，刪除緩存消息之前先判斷其目的地址是否是其鄰居節(jié)點(diǎn),，若是則重新發(fā)起分組交易,，從而提高了數(shù)據(jù)分組傳送成功率。

4 結(jié)束語(yǔ)

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

參考文獻(xiàn)

[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ī)會(huì)網(wǎng)絡(luò)路由協(xié)議[J].計(jì)算機(jī)應(yīng)用,，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,，F(xiàn)ELEGYHAZI 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ī)會(huì)網(wǎng)絡(luò)中激勵(lì)節(jié)點(diǎn)檢測(cè)策略研究[J].重慶郵電大學(xué)學(xué)報(bào)(自然科學(xué)報(bào))，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.

作者信息:

任  智，王中永,，張  勇 

（重慶郵電大學(xué) 移動(dòng)通信技術(shù)重慶市重點(diǎn)實(shí)驗(yàn)室,，重慶400065）