《電子技術(shù)應(yīng)用》
您所在的位置：首頁 > 通信與網(wǎng)絡(luò) > 設(shè)計(jì)應(yīng)用 > 基于議價(jià)博弈的高效機(jī)會網(wǎng)絡(luò)路由算法
基于議價(jià)博弈的高效機(jī)會網(wǎng)絡(luò)路由算法
2019年電子技術(shù)應(yīng)用第1期
任 智,，康 健，徐兆坤
重慶郵電大學(xué) 通信與信息工程學(xué)院,，重慶400065
摘要： 現(xiàn)有基于議價(jià)博弈的機(jī)會網(wǎng)絡(luò)路由算法存在著因節(jié)點(diǎn)交互過程偏多所引起的控制開銷過大,、對無用消息提出請求時(shí)帶來了額外開銷和博弈雙方達(dá)成交易概率不高所引起的時(shí)延以及SV列表中消息剩余跳數(shù)降為1時(shí)帶來了額外開銷等問題，對此提出了一種高效的機(jī)會網(wǎng)絡(luò)路由算法——EORB,。該算法通過采用自適應(yīng)精簡數(shù)據(jù)包摘要,、自適應(yīng)合并SV-DP消息和求購消息、綜合考慮買賣雙方收益的博弈策略等機(jī)制減少了冗余開銷,，加速了消息的轉(zhuǎn)發(fā)速率并提高了消息的到達(dá)率,。仿真結(jié)果表明，該算法有效提高了數(shù)據(jù)傳送到達(dá)的成功率,，降低了系統(tǒng)開銷以及消息的平均端到端時(shí)延,。
中圖分類號： TN92；TP393
文獻(xiàn)標(biāo)識碼： A
DOI：10.16157/j.issn.0258-7998.181682
中文引用格式： 任智,，康健,，徐兆坤. 基于議價(jià)博弈的高效機(jī)會網(wǎng)絡(luò)路由算法[J].電子技術(shù)應(yīng)用，2019,，45(1)：55-59,，63.
英文引用格式： Ren Zhi，Kang Jian,，Xu Zhaokun. Efficient opportunistic network routing algorithm based on bargaining game[J]. Application of Electronic Technique,，2019，45(1)：55-59,，63.
Efficient opportunistic network routing algorithm based on bargaining game
Ren Zhi,，Kang Jian，Xu Zhaokun
School of Communication and Information Engineering,，Chongqing University of Posts and Telecommunications,， Chongqing 400065，China
Abstract： The existing opportunistic network routing algorithms based on bargaining game has excessive control overhead caused by the excessive interaction process of nodes, the additional overhead caused by requesting for useless messages,，the additional cost and the delay caused by the low probability of the transaction between the two parties. Besides, when the number of remaining messages in the SV list drops to 1,，this condition will result in overhead as well. In response to the above problems, this paper proposes an efficient opportunity network routing algorithm——EORB. The algorithm reduces redundant overhead by adopting adaptive streamlined packet digest，adaptively merging SVDP messages and purchase messages, and comprehensively considering the game strategy of buyers′ and sellers′ benefits. It accelerates the message forwarding rate and improves the arrival rate of messages. The simulation results show that the algorithm effectively improves the rate of message delivery,reduces system overhead and reduces average end-to-end delay of messages.
Key words : bargaining game,；transaction success,；opportunity network

0 引言

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

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

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

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

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

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

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

1.2 問題描述

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

    (1)現(xiàn)有的GSCP算法在單次博弈中只有當(dāng)雙方的收益都不小于0時(shí)雙方才會達(dá)成交易并采取交易成功策略,，沒有考慮賣方在數(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)不會求購此數(shù)據(jù)包,，現(xiàn)有機(jī)制會將該類數(shù)據(jù)包的摘要加入SV并發(fā)給相遇節(jié)點(diǎn)，產(chǎn)生了數(shù)據(jù)包摘要的冗余,。

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

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

2 EORB算法

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

2.1 EORB算法新機(jī)制

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

    本文提出“自適應(yīng)精簡數(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消息,，從而避免裝入無用的數(shù)據(jù)包摘要，消除了因此而帶來的冗余控制信息,。

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

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

tx1-t1.gif

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

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

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

tx1-t2.gif

tx1-t3.gif

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

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

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

    否則，當(dāng)產(chǎn)生效益不足以抵消博弈過程中的發(fā)送與接收損耗時(shí),，買方節(jié)點(diǎn)下調(diào)報(bào)價(jià),，新報(bào)價(jià)為自身效益為0時(shí)對應(yīng)的價(jià)格，賣方節(jié)點(diǎn)根據(jù)判斷買進(jìn)該消息的效益值與此次買方提出的新報(bào)價(jià)下的效益值的和是否大于0來決定是否接受該報(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)入彼此通信范圍，通過鄰居發(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消息中沒有跳數(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列表中的該消息對應(yīng)的摘要從列表中刪除，然后發(fā)送SV-DP消息,。

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

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

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

    (6)節(jié)點(diǎn)B收到所購買的消息后,，生成帶有自身簽名的交易憑條并發(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中,，買賣雙方在博弈過程中效益值計(jì)算公式以及博弈均衡的最優(yōu)報(bào)價(jià)為：

     tx1-gs1-3.gif

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

    tx1-gs4.gif

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

    tx1-gs5.gif

    由式(3)和式(4)可知Pn>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算法中完成消息的傳送所需要的總能耗EGSCP及時(shí)延TGSCP為：

     tx1-gs6-7.gif

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

     tx1-gs8-9.gif

    可知EEORB<EGSCP,，TEORB<TGSCP,，得證。

    引理3： 采用“自適應(yīng)精簡數(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），單位長度的SV列表（指SV列表中只含有一個(gè)消息摘要）傳輸過程所需要的能耗為ε,，則未采用“自適應(yīng)精簡數(shù)據(jù)包摘要”的機(jī)制中,，當(dāng)前節(jié)點(diǎn)在與其他節(jié)點(diǎn)進(jìn)行SV交互時(shí)所消耗的能量為：

    tx1-gs10.gif

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

    tx1-gs11.gif

    可知,，Enew<Eorig,，得證,。           

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

3.1 仿真參數(shù)

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

tx1-b1.gif

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

    (1)控制開銷

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

tx1-t4.gif

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

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

tx1-t5.gif

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

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

tx1-t6.gif

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

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

tx1-t7.gif

4 結(jié)束語

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

參考文獻(xiàn)

[1] 熊永平,，孫利民，牛建偉,，等.機(jī)會網(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ī)會網(wǎng)絡(luò)中激勵(lì)節(jié)點(diǎn)檢測策略研究[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ī)會網(wǎng)絡(luò)高吞吐量低開銷概率路由算法[J].通信學(xué)報(bào),，2015，36(6)：2015129.




作者信息:

任  智,，康  健,，徐兆坤

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

此內(nèi)容為AET網(wǎng)站原創(chuàng),，未經(jīng)授權(quán)禁止轉(zhuǎn)載,。