文獻標識碼： A
DOI：10.16157/j.issn.0258-7998.181682
中文引用格式： 任智，康健，徐兆坤. 基于議價博弈的高效機會網絡路由算法[J].電子技術應用，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.
0 引言
機會網絡[1]是一種不需要源節(jié)點和目的節(jié)點之間存在完整的路徑，采取“儲存-攜帶-轉發(fā)”的路由模式并利用節(jié)點移動性帶來的相遇機會實現(xiàn)通信的時延和分裂可容忍網絡[2]。在實際中，由于節(jié)點自身資源的有限性，為保護自身資源，節(jié)點會表現(xiàn)出自私行為。針對機會網絡中節(jié)點的自私性問題具體分為兩類：基于懲罰與基于獎勵。
基于懲罰機制的路由算法主要集中于基于TFT策略的路由算法。TFT[3]策略，即在博弈開始階段，各節(jié)點都是以協(xié)作轉發(fā)策略進行博弈，之后當前節(jié)點采用對方節(jié)點在上一次博弈過程中采取的策略。
基于獎勵機制的路由算法主要以基于虛擬貨幣的路由算法為主。GIS機制[4]中買賣雙方輪番出價，但必須在三輪之后終止，即對于第三次的出價，另一方必須接受。該機制能夠刺激自私節(jié)點的合作并減少多次博弈中因博弈過程引起的消耗。GSCP[5]機制是一種基于概率路由的節(jié)點議價博弈機制，該機制假設消息對于節(jié)點的價值量與節(jié)點到達目的地址的概率成正比，消息從價值量低的節(jié)點賣出并由價值量高的節(jié)點進行購買，最終消息到達目的節(jié)點。
1 網絡模型與問題描述
1.1 網絡模型
定義1 （消息價值量）節(jié)點移動過程中，消息對于節(jié)點的價值量跟節(jié)點與該消息的目的地址的相遇概率成正相關，假設Pi，d為節(jié)點i能夠將消息m傳送到目的地址d的概率，ω為消息的初始價值量，V為消息m對于博弈參與節(jié)點i的價值量，其值為V=ω·Pi，d。
定義2 （買賣模型）若節(jié)點B想要獲得節(jié)點S中的消息m，會向S發(fā)送購買請求，并制定出購買價格x，若在價格x下，S的效益值為正，則S同意B的出價，并將m發(fā)送給B；否則買賣雙方進行下一輪議價博弈，直至達成協(xié)定或通信中斷。
1.2 問題描述
在研究中發(fā)現(xiàn)現(xiàn)有的基于議價博弈的機會網絡算法存在下列問題：
(1)現(xiàn)有的GSCP算法在單次博弈中只有當雙方的收益都不小于0時雙方才會達成交易并采取交易成功策略，沒有考慮賣方在數(shù)據包買入時可能已經獲利，這降低了博弈雙方交易的達成率以及采取交易成功策略的比率。
(2)節(jié)點在進行數(shù)據包轉發(fā)前，需要先交換SV-DP消息:當兩個節(jié)點相遇，DP列表交互完成后，收到DP列表的節(jié)點能得知雙方節(jié)點到其他節(jié)點的相遇概率；此時，若該節(jié)點到SV中某些數(shù)據包的目的節(jié)點的相遇概率高于相遇節(jié)點，則相遇節(jié)點不會求購此數(shù)據包，現(xiàn)有機制會將該類數(shù)據包的摘要加入SV并發(fā)給相遇節(jié)點，產生了數(shù)據包摘要的冗余。
(3)數(shù)據包交易的過程中存在冗余的控制消息。在現(xiàn)有相關文獻中數(shù)據包在兩節(jié)點之間交易時，請求購買數(shù)據包的求購消息需要由買方節(jié)點單獨發(fā)給賣方節(jié)點。經過研究發(fā)現(xiàn)，求購消息的源、目的節(jié)點與SV消息的源、目的節(jié)點相同，因此可以將SV-DP消息合并在一起進行發(fā)送，從而減小網絡開銷。
(4)在數(shù)據包交互過程中，節(jié)點無法通過控制消息(包括hello消息及SV消息)得知數(shù)據包的TTL字段值，導致節(jié)點有可能購買生命期字段值為1的數(shù)據包，從而導致不必要的轉發(fā)開銷和操作。
2 EORB算法
為了解決現(xiàn)有基于議價博弈的機會網絡路由算法中存在的以上問題，本文提出了一種高效的機會網絡路由算法——EORB(Efficient Opportunistic network Routing algorithm based on Bargaining game)，采用自適應精簡數(shù)據包摘要、自適應合并SV-DP消息和求購消息、綜合考慮買賣收益的博弈策略等機制。
2.1 EORB算法新機制
2.1.1 自適應精簡數(shù)據包摘要
本文提出“自適應精簡數(shù)據包摘要”，它的基本原理如下：節(jié)點在往SV-DP或 DP-SV-BUY消息中裝入數(shù)據包之前判斷數(shù)據包的生命期字段的值是否大于1，且本節(jié)點與數(shù)據包中的目的節(jié)點的相遇概率是否小于相遇節(jié)點到數(shù)據包中目的節(jié)點的相遇概率，若是，則當前節(jié)點將該數(shù)據包的摘要裝入SV-DP或 DP-SV-BUY消息，從而避免裝入無用的數(shù)據包摘要，消除了因此而帶來的冗余控制信息。
2.1.2 自適應合并SV-DP和求購消息
現(xiàn)有的機會網絡概率路由算法中，相遇節(jié)點在有消息進行交互的過程如圖1所示，此交互過程存在信令冗余的問題。
針對此問題，本文提出“自適應合并SV-DP消息和求購消息”，它的基本原理如下：
在SV-DP消息交互階段的操作中，當前節(jié)點在收到對方的SV-DP消息后，根據對方SV列表中消息的目的地址、對方概率列表中到該目的地址的概率及本節(jié)點概率列表中到該消息目的地址的概率來判斷是否購買該消息。
若購買該消息，則計算該消息在博弈均衡下的最優(yōu)價格，在向對方節(jié)點發(fā)送本節(jié)點的SV列表消息時，將需要購買的消息加入SV列表后面，形成新的DP-SV-BUY消息格式，并將該消息的目的地址設置為對該消息的報價。對方節(jié)點在接收到DP-SV-BUY消息后，可以提取出對應的購買消息。DP-SV-BUY消息格式如圖2所示，其改進后消息的交互流程如圖3所示。
2.1.3 綜合考慮買賣收益的博弈策略
針對問題(4)，本文提出了“綜合考慮買賣收益的博弈策略”的新機制，該新機制基本原理如下。
當賣方節(jié)點與目的節(jié)點相遇概率和買方節(jié)點與目的節(jié)點相遇概率的差值產生的效益可以抵消博弈過程中的發(fā)送與接收損耗時，由買方節(jié)點根據子博弈均衡的最優(yōu)價格向賣方節(jié)點提出報價。
否則，當產生效益不足以抵消博弈過程中的發(fā)送與接收損耗時，買方節(jié)點下調報價，新報價為自身效益為0時對應的價格，賣方節(jié)點根據判斷買進該消息的效益值與此次買方提出的新報價下的效益值的和是否大于0來決定是否接受該報價，若大于0，則接受，否則拒絕接受該報價。該機制在保證本節(jié)點綜合效益值（買進與賣出）不小于0的前提下，使博弈雙方交易成功的概率得到提高，進而加快了消息的轉發(fā)速率，降低了消息到達目的節(jié)點的時延。
2.2 EORB算法操作
EORB算法操作步驟如下：
(1)節(jié)點S、B進入彼此通信范圍，通過鄰居發(fā)現(xiàn)得知彼此能進行信息交互。
(2)節(jié)點S將SV列表及概率列表消息組成的SV-DP消息發(fā)送給節(jié)點B，若當前節(jié)點S的SV-DP消息中沒有跳數(shù)為1的消息時，節(jié)點S直接向相遇節(jié)點B發(fā)送自身的SV-DP消息；若當前節(jié)點S的SV-DP消息中存在跳數(shù)為1的消息且該消息的目的地址不是此次相遇節(jié)點B，則將SV列表中的該消息對應的摘要從列表中刪除，然后發(fā)送SV-DP消息。
(3)節(jié)點B收到節(jié)點S的SV-DP消息后，首先按照步驟(2)中相同的操作對自身消息進行處理，同時利用對方SV-DP消息判斷：若節(jié)點B與緩存中消息m的目的節(jié)點的相遇概率高于節(jié)點S，則從自身SV列表中將消息m對應的摘要刪除；然后利用對方SV-DP消息中每個摘要消息的目的地址、對方概率列表中到目的地址的概率及本節(jié)點概率列表中到該消息目的地址的概率判斷是否購買該消息。若購買該消息，則計算該消息在博弈均衡下的最優(yōu)價格，在向對方節(jié)點發(fā)送本節(jié)點的SV消息時，將需要購買的消息加入SV-DP消息中，并將該消息的目的地址設置為對該消息的報價，組合成DP-SV-BUY消息。
(4)節(jié)點S接收到節(jié)點B的DP-SV-BUY消息后，進行SV列表檢索對比，若存在與自身SV源地址與消息標號相同的消息，則表明是求購該消息，并且目的地址的值是對該消息的報價，節(jié)點S通過綜合考慮買進與賣出的收益總和值判斷是否接受該報價。
(5)節(jié)點S接受節(jié)點B的報價后，發(fā)送對應的消息給節(jié)點B。
(6)節(jié)點B收到所購買的消息后，生成帶有自身簽名的交易憑條并發(fā)送給節(jié)點S。
(7)節(jié)點S收到交易憑條后，若之后與交易清算中心相遇(CCC)，則向CCC遞交交易憑條，CCC根據憑條向交易雙方賬戶進行扣費與充值。
2.3 性論分析
引理1： 與GSCP算法相比，EORB算法的消息轉發(fā)率更高。
在GSCP中，買賣雙方在博弈過程中效益值計算公式以及博弈均衡的最優(yōu)報價為：
式中，Vi表示消息m對節(jié)點i的價值量，ci(r)表示第r輪博弈對于節(jié)點i的開銷，ui表示節(jié)點i的效益，T(m)表示傳輸消息m的開銷，P(m)表示接收消息m的開銷，x表示消息交易價格。只有uB和uS都不小于0時，消息才能從賣方節(jié)點傳遞到買方節(jié)點，假設uB和uS不小于0的概率分別為Pb和Ps，則此次博弈消息的轉發(fā)概率為：
在EORB算法中，買方節(jié)點在uB不小于0時會同意購買該消息，而賣方會綜合買進該消息后獲得的效益ub及此次賣出的效益uS和值ut，若ut不小于0，則賣方節(jié)點同意賣出該消息。由于ub恒為正值，假設ut不小于0的概率為Pt，uS小于0而ut不小于0的概率為Ps1，則此次博弈消息的轉發(fā)概率為：
由式(3)和式(4)可知Pn>P，EORB算法的消息轉發(fā)率更高，即得證。
引理2： EORB算法的控制開銷低于GSCP算法及HLPR-MG[6]算法。
假設網絡中有m個消息，節(jié)點發(fā)送一次消息的能耗值為δ，消息由源節(jié)點到目的節(jié)點的平均跳數(shù)為ETX，節(jié)點攜帶每個消息的平均能耗為ε，消息傳輸?shù)臅r間為τ，則在GSCP算法中完成消息的傳送所需要的總能耗EGSCP及時延TGSCP為：
而在EORB算法中完成消息的傳送所需的總能耗及時延為：
可知EEORB<EGSCP，TEORB<TGSCP，得證。
引理3： 采用“自適應精簡數(shù)據包摘要”機制能降低SV交互階段的開銷。
假設網絡中節(jié)點攜帶的消息個數(shù)均值為m，消息中跳數(shù)已經降為1且相遇節(jié)點非消息的目的節(jié)點的個數(shù)均值為n（n<m），單位長度的SV列表（指SV列表中只含有一個消息摘要）傳輸過程所需要的能耗為ε，則未采用“自適應精簡數(shù)據包摘要”的機制中，當前節(jié)點在與其他節(jié)點進行SV交互時所消耗的能量為：
采用“自適應精簡數(shù)據包摘要”的機制中，當前節(jié)點在與其他節(jié)點進行SV交互時所消耗的能量為：
可知，Enew<Eorig，得證。
3 仿真參數(shù)與統(tǒng)計量
3.1 仿真參數(shù)
本文具體仿真參數(shù)如表1所示。
3.2 仿真結果與分析
(1)控制開銷
從圖4可以看出，EORB算法的控制開銷在每個場景中均低于其他兩種算法。主要原因是：①自適應地精簡SV消息的內容，使得控制消息的長度得到降低；②自適應合并SV-DP消息和求購消息機制使得控制消息的個數(shù)得到降低。
(2)網絡吞吐量
從圖5可以看出，EORB算法的網絡吞吐量更大。這主要源自于：①綜合考慮買賣效益的博弈策略使得買賣雙方達成交易成功的概率得到提高；②自適應合并SV-DP消息和求購消息機制使得控制消息的個數(shù)得到降低，減少了無效的控制消息交互。
(3)平均端到端時延
從圖6中可以看出，EORB算法具有較低的平均端到端時延。這是由于：①綜合考慮買賣效益使得買賣雙方交易成功率得到提高；②自適應合并SV-DP消息和求購消息使得控制消息個數(shù)降低，控制消息的交互過程得到減少。
(4)消息到達率
從圖7算法對比可知，EORB算法在消息傳送成功率上有所提升。這是因為：①綜合考慮買賣效益的博弈策略使得買賣雙方達成交易成功的概率得到提高，提高了消息到達的成功率；②自適應合并SV-DP消息和求購消息機制使得控制消息的個數(shù)得到降低，控制消息的交互過程得到減少，有利于提高消息的到達率。
4 結束語
本文針對現(xiàn)有基于議價博弈的機會網絡路由算法開銷過大與交易成功率不高的問題，提出了一種高效的機會網絡路由算法——EORB。該算法采用自適應精簡數(shù)據包摘要、自適應合并SV-DP消息和求購消息、綜合考慮買賣收益的博弈策略等機制，加速了消息的轉發(fā)速率，提高了消息的到達率，減少了消息的平均時延，并降低了系統(tǒng)的開銷。
參考文獻
[1] 熊永平，孫利民，牛建偉，等.機會網絡[J].軟件學報，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] 劉期烈，候鵬翔.機會網絡中激勵節(jié)點檢測策略研究[J].重慶郵電大學學報（自然科學報），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] 任智，索建偉，劉文朋，等.基于多方議價博弈的機會網絡高吞吐量低開銷概率路由算法[J].通信學報，2015，36(6)：2015129.
作者信息:
任 智，康 健，徐兆坤
（重慶郵電大學 通信與信息工程學院，重慶400065）