0 引言

    機(jī)會(huì)網(wǎng)絡(luò)^[1]是一種不需要源節(jié)點(diǎn)和目的節(jié)點(diǎn)之間存在完整的路徑，采取“儲(chǔ)存-攜帶-轉(zhuǎn)發(fā)”的路由模式并利用節(jié)點(diǎn)移動(dòng)性帶來(lái)的相遇機(jī)會(huì)實(shí)現(xiàn)通信的時(shí)延和分裂可容忍網(wǎng)絡(luò)^[2]。在實(shí)際中，由于節(jié)點(diǎn)自身資源的有限性，為保護(hù)自身資源，節(jié)點(diǎn)會(huì)表現(xiàn)出自私行為。針對(duì)機(jī)會(huì)網(wǎng)絡(luò)中節(jié)點(diǎn)的自私性問(wèn)題具體分為兩類：基于懲罰與基于獎(jiǎng)勵(lì)。

    基于懲罰機(jī)制的路由算法主要集中于基于TFT策略的路由算法。TFT^[3]策略，即在博弈開始階段，各節(jié)點(diǎn)都是以協(xié)作轉(zhuǎn)發(fā)策略進(jìn)行博弈，之后當(dāng)前節(jié)點(diǎn)采用對(duì)方節(jié)點(diǎn)在上一次博弈過(guò)程中采取的策略。

    基于獎(jiǎng)勵(lì)機(jī)制的路由算法主要以基于虛擬貨幣的路由算法為主。GIS機(jī)制^[4]中買賣雙方輪番出價(jià)，但必須在三輪之后終止，即對(duì)于第三次的出價(jià)，另一方必須接受。該機(jī)制能夠刺激自私節(jié)點(diǎn)的合作并減少多次博弈中因博弈過(guò)程引起的消耗。GSCP^[5]機(jī)制是一種基于概率路由的節(jié)點(diǎn)議價(jià)博弈機(jī)制，該機(jī)制假設(shè)消息對(duì)于節(jié)點(diǎn)的價(jià)值量與節(jié)點(diǎn)到達(dá)目的地址的概率成正比，消息從價(jià)值量低的節(jié)點(diǎn)賣出并由價(jià)值量高的節(jié)點(diǎn)進(jìn)行購(gòu)買，最終消息到達(dá)目的節(jié)點(diǎn)。

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

1.1 網(wǎng)絡(luò)模型

    定義1 （消息價(jià)值量）節(jié)點(diǎn)移動(dòng)過(guò)程中，消息對(duì)于節(jié)點(diǎn)的價(jià)值量跟節(jié)點(diǎn)與該消息的目的地址的相遇概率成正相關(guān)，假設(shè)P_i，d為節(jié)點(diǎn)i能夠?qū)⑾傳送到目的地址d的概率，ω為消息的初始價(jià)值量，V為消息m對(duì)于博弈參與節(jié)點(diǎn)i的價(jià)值量，其值為V=ω·P_i，d。

    定義2 （買賣模型）若節(jié)點(diǎn)B想要獲得節(jié)點(diǎn)S中的消息m，會(huì)向S發(fā)送購(gòu)買請(qǐng)求，并制定出購(gòu)買價(jià)格x，若在價(jià)格x下，S的效益值為正，則S同意B的出價(jià)，并將m發(fā)送給B；否則買賣雙方進(jìn)行下一輪議價(jià)博弈，直至達(dá)成協(xié)定或通信中斷。 

1.2 問(wèn)題描述

    在研究中發(fā)現(xiàn)現(xiàn)有的基于議價(jià)博弈的機(jī)會(huì)網(wǎng)絡(luò)算法存在下列問(wèn)題：

    (1)現(xiàn)有的GSCP算法在單次博弈中只有當(dāng)雙方的收益都不小于0時(shí)雙方才會(huì)達(dá)成交易并采取交易成功策略，沒(méi)有考慮賣方在數(shù)據(jù)包買入時(shí)可能已經(jīng)獲利，這降低了博弈雙方交易的達(dá)成率以及采取交易成功策略的比率。

    (2)節(jié)點(diǎn)在進(jìn)行數(shù)據(jù)包轉(zhuǎn)發(fā)前，需要先交換SV-DP消息:當(dāng)兩個(gè)節(jié)點(diǎn)相遇，DP列表交互完成后，收到DP列表的節(jié)點(diǎn)能得知雙方節(jié)點(diǎn)到其他節(jié)點(diǎn)的相遇概率；此時(shí)，若該節(jié)點(diǎn)到SV中某些數(shù)據(jù)包的目的節(jié)點(diǎn)的相遇概率高于相遇節(jié)點(diǎn)，則相遇節(jié)點(diǎn)不會(huì)求購(gòu)此數(shù)據(jù)包，現(xiàn)有機(jī)制會(huì)將該類數(shù)據(jù)包的摘要加入SV并發(fā)給相遇節(jié)點(diǎn)，產(chǎn)生了數(shù)據(jù)包摘要的冗余。

    (3)數(shù)據(jù)包交易的過(guò)程中存在冗余的控制消息。在現(xiàn)有相關(guān)文獻(xiàn)中數(shù)據(jù)包在兩節(jié)點(diǎn)之間交易時(shí)，請(qǐng)求購(gòu)買數(shù)據(jù)包的求購(gòu)消息需要由買方節(jié)點(diǎn)單獨(dú)發(fā)給賣方節(jié)點(diǎn)。經(jīng)過(guò)研究發(fā)現(xiàn)，求購(gòu)消息的源、目的節(jié)點(diǎn)與SV消息的源、目的節(jié)點(diǎn)相同，因此可以將SV-DP消息合并在一起進(jìn)行發(fā)送，從而減小網(wǎng)絡(luò)開銷。

    (4)在數(shù)據(jù)包交互過(guò)程中，節(jié)點(diǎn)無(wú)法通過(guò)控制消息(包括hello消息及SV消息)得知數(shù)據(jù)包的TTL字段值，導(dǎo)致節(jié)點(diǎn)有可能購(gòu)買生命期字段值為1的數(shù)據(jù)包，從而導(dǎo)致不必要的轉(zhuǎn)發(fā)開銷和操作。

2 EORB算法

    為了解決現(xiàn)有基于議價(jià)博弈的機(jī)會(huì)網(wǎng)絡(luò)路由算法中存在的以上問(wèn)題，本文提出了一種高效的機(jī)會(huì)網(wǎng)絡(luò)路由算法——EORB(Efficient Opportunistic network Routing algorithm based on Bargaining game)，采用自適應(yīng)精簡(jiǎn)數(shù)據(jù)包摘要、自適應(yīng)合并SV-DP消息和求購(gòu)消息、綜合考慮買賣收益的博弈策略等機(jī)制。

2.1 EORB算法新機(jī)制

2.1.1 自適應(yīng)精簡(jiǎn)數(shù)據(jù)包摘要

    本文提出“自適應(yīng)精簡(jiǎn)數(shù)據(jù)包摘要”，它的基本原理如下：節(jié)點(diǎn)在往SV-DP或 DP-SV-BUY消息中裝入數(shù)據(jù)包之前判斷數(shù)據(jù)包的生命期字段的值是否大于1，且本節(jié)點(diǎn)與數(shù)據(jù)包中的目的節(jié)點(diǎn)的相遇概率是否小于相遇節(jié)點(diǎn)到數(shù)據(jù)包中目的節(jié)點(diǎn)的相遇概率，若是，則當(dāng)前節(jié)點(diǎn)將該數(shù)據(jù)包的摘要裝入SV-DP或 DP-SV-BUY消息，從而避免裝入無(wú)用的數(shù)據(jù)包摘要，消除了因此而帶來(lái)的冗余控制信息。

2.1.2 自適應(yīng)合并SV-DP和求購(gòu)消息

    現(xiàn)有的機(jī)會(huì)網(wǎng)絡(luò)概率路由算法中，相遇節(jié)點(diǎn)在有消息進(jìn)行交互的過(guò)程如圖1所示，此交互過(guò)程存在信令冗余的問(wèn)題。

    針對(duì)此問(wèn)題，本文提出“自適應(yīng)合并SV-DP消息和求購(gòu)消息”，它的基本原理如下：

    在SV-DP消息交互階段的操作中，當(dāng)前節(jié)點(diǎn)在收到對(duì)方的SV-DP消息后，根據(jù)對(duì)方SV列表中消息的目的地址、對(duì)方概率列表中到該目的地址的概率及本節(jié)點(diǎn)概率列表中到該消息目的地址的概率來(lái)判斷是否購(gòu)買該消息。

    若購(gòu)買該消息，則計(jì)算該消息在博弈均衡下的最優(yōu)價(jià)格，在向?qū)Ψ焦?jié)點(diǎn)發(fā)送本節(jié)點(diǎn)的SV列表消息時(shí)，將需要購(gòu)買的消息加入SV列表后面，形成新的DP-SV-BUY消息格式，并將該消息的目的地址設(shè)置為對(duì)該消息的報(bào)價(jià)。對(duì)方節(jié)點(diǎn)在接收到DP-SV-BUY消息后，可以提取出對(duì)應(yīng)的購(gòu)買消息。DP-SV-BUY消息格式如圖2所示，其改進(jìn)后消息的交互流程如圖3所示。

2.1.3 綜合考慮買賣收益的博弈策略

    針對(duì)問(wèn)題(4)，本文提出了“綜合考慮買賣收益的博弈策略”的新機(jī)制，該新機(jī)制基本原理如下。

    當(dāng)賣方節(jié)點(diǎn)與目的節(jié)點(diǎn)相遇概率和買方節(jié)點(diǎn)與目的節(jié)點(diǎn)相遇概率的差值產(chǎn)生的效益可以抵消博弈過(guò)程中的發(fā)送與接收損耗時(shí)，由買方節(jié)點(diǎn)根據(jù)子博弈均衡的最優(yōu)價(jià)格向賣方節(jié)點(diǎn)提出報(bào)價(jià)。

    否則，當(dāng)產(chǎn)生效益不足以抵消博弈過(guò)程中的發(fā)送與接收損耗時(shí)，買方節(jié)點(diǎn)下調(diào)報(bào)價(jià)，新報(bào)價(jià)為自身效益為0時(shí)對(duì)應(yīng)的價(jià)格，賣方節(jié)點(diǎn)根據(jù)判斷買進(jìn)該消息的效益值與此次買方提出的新報(bào)價(jià)下的效益值的和是否大于0來(lái)決定是否接受該報(bào)價(jià)，若大于0，則接受，否則拒絕接受該報(bào)價(jià)。該機(jī)制在保證本節(jié)點(diǎn)綜合效益值（買進(jìn)與賣出）不小于0的前提下，使博弈雙方交易成功的概率得到提高，進(jìn)而加快了消息的轉(zhuǎn)發(fā)速率，降低了消息到達(dá)目的節(jié)點(diǎn)的時(shí)延。

2.2 EORB算法操作

    EORB算法操作步驟如下：

    (1)節(jié)點(diǎn)S、B進(jìn)入彼此通信范圍，通過(guò)鄰居發(fā)現(xiàn)得知彼此能進(jìn)行信息交互。

    (2)節(jié)點(diǎn)S將SV列表及概率列表消息組成的SV-DP消息發(fā)送給節(jié)點(diǎn)B，若當(dāng)前節(jié)點(diǎn)S的SV-DP消息中沒(méi)有跳數(shù)為1的消息時(shí)，節(jié)點(diǎn)S直接向相遇節(jié)點(diǎn)B發(fā)送自身的SV-DP消息；若當(dāng)前節(jié)點(diǎn)S的SV-DP消息中存在跳數(shù)為1的消息且該消息的目的地址不是此次相遇節(jié)點(diǎn)B，則將SV列表中的該消息對(duì)應(yīng)的摘要從列表中刪除，然后發(fā)送SV-DP消息。

    (3)節(jié)點(diǎn)B收到節(jié)點(diǎn)S的SV-DP消息后，首先按照步驟(2)中相同的操作對(duì)自身消息進(jìn)行處理，同時(shí)利用對(duì)方SV-DP消息判斷：若節(jié)點(diǎn)B與緩存中消息m的目的節(jié)點(diǎn)的相遇概率高于節(jié)點(diǎn)S，則從自身SV列表中將消息m對(duì)應(yīng)的摘要?jiǎng)h除；然后利用對(duì)方SV-DP消息中每個(gè)摘要消息的目的地址、對(duì)方概率列表中到目的地址的概率及本節(jié)點(diǎn)概率列表中到該消息目的地址的概率判斷是否購(gòu)買該消息。若購(gòu)買該消息，則計(jì)算該消息在博弈均衡下的最優(yōu)價(jià)格，在向?qū)Ψ焦?jié)點(diǎn)發(fā)送本節(jié)點(diǎn)的SV消息時(shí)，將需要購(gòu)買的消息加入SV-DP消息中，并將該消息的目的地址設(shè)置為對(duì)該消息的報(bào)價(jià)，組合成DP-SV-BUY消息。

    (4)節(jié)點(diǎn)S接收到節(jié)點(diǎn)B的DP-SV-BUY消息后，進(jìn)行SV列表檢索對(duì)比，若存在與自身SV源地址與消息標(biāo)號(hào)相同的消息，則表明是求購(gòu)該消息，并且目的地址的值是對(duì)該消息的報(bào)價(jià)，節(jié)點(diǎn)S通過(guò)綜合考慮買進(jìn)與賣出的收益總和值判斷是否接受該報(bào)價(jià)。

    (5)節(jié)點(diǎn)S接受節(jié)點(diǎn)B的報(bào)價(jià)后，發(fā)送對(duì)應(yīng)的消息給節(jié)點(diǎn)B。

    (6)節(jié)點(diǎn)B收到所購(gòu)買的消息后，生成帶有自身簽名的交易憑條并發(fā)送給節(jié)點(diǎn)S。

    (7)節(jié)點(diǎn)S收到交易憑條后，若之后與交易清算中心相遇(CCC)，則向CCC遞交交易憑條，CCC根據(jù)憑條向交易雙方賬戶進(jìn)行扣費(fèi)與充值。

2.3 性論分析

    引理1： 與GSCP算法相比，EORB算法的消息轉(zhuǎn)發(fā)率更高。

    在GSCP中，買賣雙方在博弈過(guò)程中效益值計(jì)算公式以及博弈均衡的最優(yōu)報(bào)價(jià)為：

式中，V_i表示消息m對(duì)節(jié)點(diǎn)i的價(jià)值量，c_i(r)表示第r輪博弈對(duì)于節(jié)點(diǎn)i的開銷，u_i表示節(jié)點(diǎn)i的效益，T(m)表示傳輸消息m的開銷，P(m)表示接收消息m的開銷，x表示消息交易價(jià)格。只有u_B和u_S都不小于0時(shí)，消息才能從賣方節(jié)點(diǎn)傳遞到買方節(jié)點(diǎn)，假設(shè)u_B和u_S不小于0的概率分別為P_b和P_s，則此次博弈消息的轉(zhuǎn)發(fā)概率為：

    在EORB算法中，買方節(jié)點(diǎn)在u_B不小于0時(shí)會(huì)同意購(gòu)買該消息，而賣方會(huì)綜合買進(jìn)該消息后獲得的效益u_b及此次賣出的效益u_S和值u_t，若u_t不小于0，則賣方節(jié)點(diǎn)同意賣出該消息。由于u_b恒為正值，假設(shè)u_t不小于0的概率為P_t，u_S小于0而u_t不小于0的概率為P_s1，則此次博弈消息的轉(zhuǎn)發(fā)概率為：

    由式(3)和式(4)可知P_n>P，EORB算法的消息轉(zhuǎn)發(fā)率更高，即得證。

    引理2： EORB算法的控制開銷低于GSCP算法及HLPR-MG^[6]算法。

    假設(shè)網(wǎng)絡(luò)中有m個(gè)消息，節(jié)點(diǎn)發(fā)送一次消息的能耗值為δ，消息由源節(jié)點(diǎn)到目的節(jié)點(diǎn)的平均跳數(shù)為ETX，節(jié)點(diǎn)攜帶每個(gè)消息的平均能耗為ε，消息傳輸?shù)臅r(shí)間為τ，則在GSCP算法中完成消息的傳送所需要的總能耗E_GSCP及時(shí)延T_GSCP為：

    而在EORB算法中完成消息的傳送所需的總能耗及時(shí)延為：

    可知E_EORB<E_GSCP，T_EORB<T_GSCP，得證。

    引理3： 采用“自適應(yīng)精簡(jiǎn)數(shù)據(jù)包摘要”機(jī)制能降低SV交互階段的開銷。

    假設(shè)網(wǎng)絡(luò)中節(jié)點(diǎn)攜帶的消息個(gè)數(shù)均值為m，消息中跳數(shù)已經(jīng)降為1且相遇節(jié)點(diǎn)非消息的目的節(jié)點(diǎn)的個(gè)數(shù)均值為n（n<m），單位長(zhǎng)度的SV列表（指SV列表中只含有一個(gè)消息摘要）傳輸過(guò)程所需要的能耗為ε，則未采用“自適應(yīng)精簡(jiǎn)數(shù)據(jù)包摘要”的機(jī)制中，當(dāng)前節(jié)點(diǎn)在與其他節(jié)點(diǎn)進(jìn)行SV交互時(shí)所消耗的能量為：

    采用“自適應(yīng)精簡(jiǎn)數(shù)據(jù)包摘要”的機(jī)制中，當(dāng)前節(jié)點(diǎn)在與其他節(jié)點(diǎn)進(jìn)行SV交互時(shí)所消耗的能量為：

    可知，E_new<E_orig，得證。           

3 仿真參數(shù)與統(tǒng)計(jì)量

3.1 仿真參數(shù)

    本文具體仿真參數(shù)如表1所示。

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

    (1)控制開銷

    從圖4可以看出，EORB算法的控制開銷在每個(gè)場(chǎng)景中均低于其他兩種算法。主要原因是：①自適應(yīng)地精簡(jiǎn)SV消息的內(nèi)容，使得控制消息的長(zhǎng)度得到降低；②自適應(yīng)合并SV-DP消息和求購(gòu)消息機(jī)制使得控制消息的個(gè)數(shù)得到降低。

    (2)網(wǎng)絡(luò)吞吐量

    從圖5可以看出，EORB算法的網(wǎng)絡(luò)吞吐量更大。這主要源自于：①綜合考慮買賣效益的博弈策略使得買賣雙方達(dá)成交易成功的概率得到提高；②自適應(yīng)合并SV-DP消息和求購(gòu)消息機(jī)制使得控制消息的個(gè)數(shù)得到降低，減少了無(wú)效的控制消息交互。

    (3)平均端到端時(shí)延

    從圖6中可以看出，EORB算法具有較低的平均端到端時(shí)延。這是由于：①綜合考慮買賣效益使得買賣雙方交易成功率得到提高；②自適應(yīng)合并SV-DP消息和求購(gòu)消息使得控制消息個(gè)數(shù)降低，控制消息的交互過(guò)程得到減少。  

    (4)消息到達(dá)率

    從圖7算法對(duì)比可知，EORB算法在消息傳送成功率上有所提升。這是因?yàn)椋孩倬C合考慮買賣效益的博弈策略使得買賣雙方達(dá)成交易成功的概率得到提高，提高了消息到達(dá)的成功率；②自適應(yīng)合并SV-DP消息和求購(gòu)消息機(jī)制使得控制消息的個(gè)數(shù)得到降低，控制消息的交互過(guò)程得到減少，有利于提高消息的到達(dá)率。

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

    本文針對(duì)現(xiàn)有基于議價(jià)博弈的機(jī)會(huì)網(wǎng)絡(luò)路由算法開銷過(guò)大與交易成功率不高的問(wèn)題，提出了一種高效的機(jī)會(huì)網(wǎng)絡(luò)路由算法——EORB。該算法采用自適應(yīng)精簡(jiǎn)數(shù)據(jù)包摘要、自適應(yīng)合并SV-DP消息和求購(gòu)消息、綜合考慮買賣收益的博弈策略等機(jī)制，加速了消息的轉(zhuǎn)發(fā)速率，提高了消息的到達(dá)率，減少了消息的平均時(shí)延，并降低了系統(tǒng)的開銷。

參考文獻(xiàn)

[1] 熊永平，孫利民，牛建偉，等.機(jī)會(huì)網(wǎng)絡(luò)[J].軟件學(xué)報(bào)，2009，20(1)：124-137.

[2] STAVROULAKI V，TSAGKARIS K，LOGOTHETIS M，et al.Opportunistic networks[J].IEEE Vehicular Technology Magazine，2011，6(3)：52-59.

[3] SHEVADE U，SONG H，QIU V，et al.Incentive-aware routing in DTNS[C].Proceeding of the IEEE International Conference on Network Protocols，Orland，USA，2008：238-247.

[4] 劉期烈，候鵬翔.機(jī)會(huì)網(wǎng)絡(luò)中激勵(lì)節(jié)點(diǎn)檢測(cè)策略研究[J].重慶郵電大學(xué)學(xué)報(bào)（自然科學(xué)報(bào)），2015，27(2)：266-272.

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

[6] 任智，索建偉，劉文朋，等.基于多方議價(jià)博弈的機(jī)會(huì)網(wǎng)絡(luò)高吞吐量低開銷概率路由算法[J].通信學(xué)報(bào)，2015，36(6)：2015129.

作者信息:

任  智，康  健，徐兆坤

（重慶郵電大學(xué) 通信與信息工程學(xué)院，重慶400065）