基于效用的機(jī)會(huì)網(wǎng)絡(luò)“物—物交換”激勵(lì)機(jī)制

姚建盛，馬春光，袁琪

(1. 哈爾濱工程大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，黑龍江 哈爾濱 150001；2. 吉林師范大學(xué)計(jì)算機(jī)學(xué)院，吉林 四平 136000)

基于效用的機(jī)會(huì)網(wǎng)絡(luò)“物—物交換”激勵(lì)機(jī)制

姚建盛1,2，馬春光1，袁琪1

(1. 哈爾濱工程大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，黑龍江 哈爾濱 150001；2. 吉林師范大學(xué)計(jì)算機(jī)學(xué)院，吉林 四平 136000)

針對(duì)機(jī)會(huì)網(wǎng)絡(luò)環(huán)境下簡(jiǎn)單“物—物交換”（SBT, simple barter trade）激勵(lì)機(jī)制因盲目緩存而降低網(wǎng)絡(luò)性能的問(wèn)題，設(shè)計(jì)一種基于效用的“物—物交換”（UBT, utility-based barter trade）激勵(lì)機(jī)制。UBT通過(guò)預(yù)測(cè)未來(lái)相遇節(jié)點(diǎn)和相遇節(jié)點(diǎn)轉(zhuǎn)發(fā)消息到目的節(jié)點(diǎn)的概率進(jìn)行緩存決策從而提高了緩存效率和網(wǎng)絡(luò)性能。仿真實(shí)驗(yàn)證明，和SBT相比，UBT在有效激勵(lì)節(jié)點(diǎn)協(xié)作的同時(shí)能用更少的網(wǎng)絡(luò)負(fù)載獲得更高的投遞率和更低的時(shí)延。

機(jī)會(huì)網(wǎng)絡(luò)；自私；“物—物交換”激勵(lì)機(jī)制；效用

1 引言

機(jī)會(huì)網(wǎng)絡(luò)[1,2]利用節(jié)點(diǎn)移動(dòng)帶來(lái)的接觸機(jī)會(huì)實(shí)現(xiàn)不存在完整通信鏈路的節(jié)點(diǎn)間通信，這使手持便攜設(shè)備和車載設(shè)備等可以隨時(shí)隨地感知并擴(kuò)散熱點(diǎn)區(qū)域信息，滿足物聯(lián)網(wǎng)泛在互聯(lián)與透徹感知的需求[3]，對(duì)IoT和普適計(jì)算有重要意義。

機(jī)會(huì)網(wǎng)絡(luò)之所以能實(shí)現(xiàn)間歇性連接網(wǎng)絡(luò)的通信，在于采用“存儲(chǔ)—攜帶—轉(zhuǎn)發(fā)”的路由模型，這顯然需要節(jié)點(diǎn)間的協(xié)作。然而，在實(shí)際機(jī)會(huì)網(wǎng)絡(luò)系統(tǒng)中，節(jié)點(diǎn)為了節(jié)省資源或安全等原因往往不愿意為其他節(jié)點(diǎn)緩存、攜帶并轉(zhuǎn)發(fā)數(shù)據(jù)，這種自私行為嚴(yán)重影響了機(jī)會(huì)網(wǎng)絡(luò)性能[4]。

針對(duì)自私問(wèn)題，傳統(tǒng)激勵(lì)機(jī)制主要有基于reputation的激勵(lì)機(jī)制[5]和基于credit的激勵(lì)機(jī)制[6]，然而機(jī)會(huì)通信為設(shè)計(jì)這些激勵(lì)機(jī)制帶來(lái)很大挑戰(zhàn)。在基于 reputation的激勵(lì)機(jī)制中，監(jiān)測(cè)下一跳節(jié)點(diǎn)的轉(zhuǎn)發(fā)行這一關(guān)鍵問(wèn)題在間歇性鏈接的機(jī)會(huì)網(wǎng)絡(luò)中較難實(shí)現(xiàn)。在基于credit的激勵(lì)機(jī)制中，通常需要可信第三方或特殊硬件保障電子貨幣的可信，并需要解決向誰(shuí)支付和支付多少的問(wèn)題，這在拓?fù)涓叨葎?dòng)態(tài)的分布式機(jī)會(huì)網(wǎng)絡(luò)中也很難實(shí)現(xiàn)。

以上2種激勵(lì)機(jī)制都將下一跳節(jié)點(diǎn)的轉(zhuǎn)發(fā)行為當(dāng)作服務(wù)，增加了在機(jī)會(huì)網(wǎng)絡(luò)環(huán)境下的設(shè)計(jì)難度。相比之下，BUTTYáN[7]設(shè)計(jì)的基于barter的激勵(lì)機(jī)制，本文簡(jiǎn)稱為簡(jiǎn)單“物—物交換”（SBT，simplebarter trade）激勵(lì)機(jī)制，該激勵(lì)機(jī)制簡(jiǎn)單、有效、易于實(shí)現(xiàn)。但SBT在激勵(lì)節(jié)點(diǎn)幫助其他節(jié)點(diǎn)緩存消息時(shí)并未考慮未來(lái)會(huì)和誰(shuí)相遇以及相遇節(jié)點(diǎn)的需求，這會(huì)導(dǎo)致不必要的緩存而降低網(wǎng)絡(luò)性能。如節(jié)點(diǎn)u緩存消息m后，在以節(jié)點(diǎn)u為起點(diǎn)、轉(zhuǎn)發(fā)消息m的路徑上，所有節(jié)點(diǎn)都不能成功投遞m到其目的節(jié)點(diǎn)，那么緩存m不僅浪費(fèi)了帶寬和存儲(chǔ)資源，而且會(huì)因阻礙緩存合適消息而降低網(wǎng)絡(luò)性能。

基于效用的緩存能有效提高節(jié)點(diǎn)緩存效率[8]，為此，本文針對(duì)機(jī)會(huì)網(wǎng)絡(luò)設(shè)計(jì)一種基于效用的“物—物交換”（UBT，utility-based barter trade）激勵(lì)機(jī)制。然而，在機(jī)會(huì)網(wǎng)絡(luò)環(huán)境下設(shè)計(jì)合適的緩存效用并計(jì)算其值很有挑戰(zhàn)。首先通過(guò)預(yù)測(cè)未來(lái)相遇節(jié)點(diǎn)、相遇時(shí)是否能成功轉(zhuǎn)發(fā)消息給相遇節(jié)點(diǎn)以及相遇節(jié)點(diǎn)成功投遞消息到其目的節(jié)點(diǎn)的概率設(shè)計(jì)高效的緩存策略，然后給出相關(guān)度量的預(yù)測(cè)方法，最后設(shè)計(jì) UBT機(jī)制并分析其開銷。在真實(shí)移動(dòng)軌跡和人工移動(dòng)軌跡下的仿真實(shí)驗(yàn)表明，UBT不僅能有效激勵(lì)節(jié)點(diǎn)協(xié)作，而且和SBT相比通過(guò)更小的網(wǎng)絡(luò)負(fù)載達(dá)到更高的投遞率和更小的時(shí)延。

2 相關(guān)工作

本節(jié)給出和本文相關(guān)的研究工作，包括激勵(lì)機(jī)制和基于效用的緩存策略，激勵(lì)機(jī)制主要介紹基于reputation的激勵(lì)機(jī)制、基于credit的激勵(lì)機(jī)制和基于barter的激勵(lì)機(jī)制。

在基于 reputation的激勵(lì)機(jī)制中，節(jié)點(diǎn)通過(guò)提供轉(zhuǎn)發(fā)服務(wù)提高自己的信譽(yù)，信譽(yù)越高得到其他節(jié)點(diǎn)提供服務(wù)的機(jī)會(huì)越大。然而間歇性連接為監(jiān)測(cè)下一跳節(jié)點(diǎn)的轉(zhuǎn)發(fā)行為帶來(lái)困難。為此 PRI[9]提出成功轉(zhuǎn)發(fā)證書概念監(jiān)測(cè)節(jié)點(diǎn)轉(zhuǎn)發(fā)行為；SENSE[10]設(shè)計(jì)基于上下文的自私節(jié)點(diǎn)監(jiān)測(cè)算法；TRSS[11]利用社會(huì)相似性管理信任。

在基于credit的激勵(lì)機(jī)制中，節(jié)點(diǎn)通過(guò)提供轉(zhuǎn)發(fā)服務(wù)獲取虛擬貨幣，然后用虛擬貨幣換取其他節(jié)點(diǎn)的轉(zhuǎn)發(fā)服務(wù)。如不向外提供服務(wù)，自己也沒(méi)有“資金”購(gòu)買服務(wù)。然而，機(jī)會(huì)網(wǎng)絡(luò)的高度動(dòng)態(tài)拓?fù)浜碗S機(jī)性路由使源節(jié)點(diǎn)很難預(yù)知向誰(shuí)支付和支付多少的問(wèn)題。為此，NING等[12]提出僅向最終投遞者支付酬金的激勵(lì)機(jī)制；MuRIS[13]通過(guò)定價(jià)和回報(bào)函數(shù)激勵(lì)節(jié)點(diǎn)協(xié)作；MobiCent[14]通過(guò)博弈論和算法機(jī)制設(shè)計(jì)激勵(lì)相容的支付機(jī)制；SIS[15]提出基于服務(wù)優(yōu)先權(quán)的激勵(lì)機(jī)制代替credit機(jī)制。

國(guó)內(nèi)學(xué)者在將傳統(tǒng)激勵(lì)機(jī)制應(yīng)用于機(jī)會(huì)網(wǎng)絡(luò)的研究中也做了大量工作[16～19]。然而以上激勵(lì)機(jī)制研究都將下一跳節(jié)點(diǎn)的轉(zhuǎn)發(fā)當(dāng)作服務(wù)，利用某種度量（信譽(yù)或虛擬貨幣）衡量節(jié)點(diǎn)提供服務(wù)的多少，決定其獲得服務(wù)的資本。這雖然增強(qiáng)了激勵(lì)機(jī)制的靈活性，如便于服務(wù)的轉(zhuǎn)移或傳遞，但也增加了在機(jī)會(huì)網(wǎng)絡(luò)環(huán)境下的設(shè)計(jì)難度。

基于barter的激勵(lì)機(jī)制中，節(jié)點(diǎn)將上游節(jié)點(diǎn)提供的數(shù)據(jù)當(dāng)作服務(wù)，通過(guò)以物換物的方式激勵(lì)節(jié)點(diǎn)主動(dòng)緩存數(shù)據(jù)，在機(jī)會(huì)網(wǎng)絡(luò)中則比較容易實(shí)現(xiàn)。首先，通過(guò)判斷上游節(jié)點(diǎn)數(shù)據(jù)檢測(cè)其自私行為比較容易，不受鏈路斷開影響；其次，不使用虛擬貨幣，避免支付帶來(lái)的困難；最后，交易僅發(fā)生在2個(gè)相遇節(jié)點(diǎn)之間，使機(jī)制容易分布式實(shí)現(xiàn)。文獻(xiàn)[20]將該機(jī)制應(yīng)用于P2P網(wǎng)絡(luò)；文獻(xiàn)[7]首次將該機(jī)制引入機(jī)會(huì)網(wǎng)絡(luò)；LIU等[21]指出SBT存在降低網(wǎng)絡(luò)性能的問(wèn)題，并通過(guò)基于社區(qū)的“物—物交換”提高網(wǎng)絡(luò)性能；LI[22]給出機(jī)會(huì)網(wǎng)絡(luò)環(huán)境下基于barter激勵(lì)機(jī)制的研究現(xiàn)狀。

基于效用的緩存策略在機(jī)會(huì)網(wǎng)絡(luò)路由中有大量應(yīng)用，如基于移動(dòng)軌跡的效用[23]、基于社區(qū)的效用[24]、基于相遇歷史的效用[25]等。但是現(xiàn)有文獻(xiàn)很少有考慮到節(jié)點(diǎn)管理緩存時(shí)丟棄消息的因素[26]，本文在文獻(xiàn)[26]的基礎(chǔ)上給出更精確的消息丟棄概率預(yù)測(cè)方法，并設(shè)計(jì)適合基于barter激勵(lì)機(jī)制和機(jī)會(huì)網(wǎng)絡(luò)的緩存效用以提高網(wǎng)絡(luò)性能。

3 基于效用的“物—物交換”激勵(lì)機(jī)制

為提高SBT的網(wǎng)絡(luò)性能，首先設(shè)計(jì)一種高效的緩存效用并給出計(jì)算方法，然后設(shè)計(jì)基于效用的“物—物交換”激勵(lì)機(jī)制并分析機(jī)制的開銷。

3.1 效用值計(jì)算

計(jì)算效用值的原則是不僅有利于節(jié)點(diǎn)自身利益，而且能提高網(wǎng)絡(luò)整體性能。節(jié)點(diǎn)v為u緩存消息m的效用取決于v和u是否相遇以及相遇時(shí)u是否向v請(qǐng)求m，而u是否向v請(qǐng)求m取決于u是否為m的目的節(jié)點(diǎn)或者u的下游節(jié)點(diǎn)是否需要m。

設(shè)d是消息m的目的節(jié)點(diǎn)，tr是消息m的剩余生存時(shí)間，?v是節(jié)點(diǎn)v的中繼節(jié)點(diǎn)集，則v緩存消息m的效用為

當(dāng)v=d時(shí)，v直接緩存m，否則效用值由2部分組成：如果節(jié)點(diǎn)v在tr內(nèi)直接投遞消息m到d的概率較大，則越大，因?yàn)?d一定會(huì)請(qǐng)求消息m，這樣v可以從d那里交換消息；如果較高，則w向v請(qǐng)求m的概率較大，則也越大。

3.2 度量值預(yù)測(cè)

本節(jié)給出效用計(jì)算中相關(guān)度量值的預(yù)測(cè)方法。

這2個(gè)移動(dòng)模型下，節(jié)點(diǎn)相遇過(guò)程服都從 Poisson分布，則，其中，λuv是節(jié)點(diǎn)對(duì)(u, v)的相遇頻率。下面驗(yàn)證在這2個(gè)移動(dòng)模型中節(jié)點(diǎn)相遇過(guò)程是否可用 Poisson分布建模，并給出相遇頻率的計(jì)算方法。

在經(jīng)典獨(dú)立同分布移動(dòng)模型下，文獻(xiàn)[27]已經(jīng)驗(yàn)證了在節(jié)點(diǎn)通信半徑遠(yuǎn)小于移動(dòng)區(qū)域時(shí)，節(jié)點(diǎn)相遇過(guò)程服從 Poisson分布，并給出相遇頻率的計(jì)算方法，即，其中，r是節(jié)點(diǎn)無(wú)線傳輸半徑，E[V*]是節(jié)點(diǎn)移動(dòng)速度的數(shù)學(xué)期望，A是節(jié)點(diǎn)移動(dòng)區(qū)域，θ是依賴于不同移動(dòng)模型的常數(shù)，在RWP移動(dòng)模型下θ=1.368 3。

在真實(shí)移動(dòng)軌跡模型中，主流文獻(xiàn)認(rèn)為節(jié)點(diǎn)相遇過(guò)程服從 Poisson分布[24,26]，但是也有研究人員認(rèn)為服從冪率分布[2,3]。下面用皮爾遜χ2準(zhǔn)則驗(yàn)證Infocom06數(shù)據(jù)集近似服從Poisson分布并給出相遇頻率計(jì)算方法。

將節(jié)點(diǎn)對(duì)(u, v)相遇過(guò)程分成k個(gè)區(qū)間，統(tǒng)計(jì)每個(gè)區(qū)間中相遇次數(shù)n1,n2,?,nk，總相遇次數(shù)求出每個(gè)相遇區(qū)間的相遇頻率(i=1,2,?,k)和節(jié)點(diǎn)對(duì)的相遇頻率。令原假設(shè)H0服從Poisson分布，即X～P(λ)，求出隨機(jī)變量X落在每個(gè)區(qū)間的概率pi(i=1,2,?,k)。

為了檢驗(yàn)原假設(shè)H0，即檢驗(yàn)理論分布和統(tǒng)計(jì)分布是否符合，把偏差的加權(quán)平方和作為理論分布與統(tǒng)計(jì)分布之間的差異度。其中，ci是各個(gè)區(qū)間的權(quán)，依據(jù)皮爾遜準(zhǔn)則，如果取，則當(dāng)N→∞時(shí)，統(tǒng)計(jì)量ε的分布趨于自由度為k?γ?1的χ2分布， γ是理論分布中需要利用樣本觀測(cè)值估計(jì)的未知參數(shù)個(gè)數(shù)，這里取值為 1。經(jīng)過(guò)測(cè)試，在顯著性水平α=0.05時(shí)，Infocom06數(shù)據(jù)集中超過(guò)85% 的節(jié)點(diǎn)對(duì)(u, v)的相遇過(guò)程服從相遇頻率為的Poisson分布。

鑒于式(4)的計(jì)算復(fù)雜性較高，且很難在實(shí)際系統(tǒng)中計(jì)算其值，給出一種適用于實(shí)際系統(tǒng)的、簡(jiǎn)單的估計(jì)值，即

其中，TTL是消息m的生存周期，tr是消息m生存周期的剩余時(shí)間。該方法基于這樣的觀察：消息m在網(wǎng)絡(luò)中傳播時(shí)間越長(zhǎng)，d緩存到m的概率越大，反之則概率越小，該方法的預(yù)測(cè)結(jié)果和集中式計(jì)算的式(4)很接近，而且該方法計(jì)算簡(jiǎn)單，易于實(shí)現(xiàn)。

圖1 節(jié)點(diǎn)v的緩存

當(dāng)緩存滿后，節(jié)點(diǎn) u再收到新消息時(shí)，效用值最低的消息被丟棄。當(dāng)收到效用值小于m的消息時(shí)，對(duì)丟棄m不產(chǎn)生影響，當(dāng)收到效用值大于m的消息時(shí)，消息m會(huì)前移，當(dāng)收到多于k+i個(gè)效用值大于m的消息時(shí)，m被丟棄。因此，消息m在ξ時(shí)刻之前被節(jié)點(diǎn)u丟棄的概率按式(6)計(jì)算

其中，P1(τ?t)是從時(shí)間t到τ節(jié)點(diǎn)u收到s個(gè)任意效用值的消息的概率，按式(7)計(jì)算

P2(ξ?τ)是節(jié)點(diǎn) u從時(shí)間τ到ξ收到多于 k+i個(gè)效用值大于m的消息的概率，即

3.3 機(jī)制設(shè)計(jì)

在前面的效用計(jì)算中獲得節(jié)點(diǎn)相遇頻率是關(guān)鍵，3.2節(jié)給出在獨(dú)立同分布的經(jīng)典移動(dòng)模型下節(jié)點(diǎn)相遇頻率計(jì)算式和在真實(shí)移動(dòng)軌跡中的計(jì)算方法，本節(jié)針對(duì)真實(shí)移動(dòng)軌跡給出計(jì)算節(jié)點(diǎn)相遇頻率的詳細(xì)設(shè)計(jì)。

節(jié)點(diǎn)用如圖2所示的數(shù)據(jù)結(jié)構(gòu)記錄并計(jì)算和每個(gè)節(jié)點(diǎn)的相遇頻率。數(shù)據(jù)結(jié)構(gòu)的主體是一個(gè)鏈表L，head是頭指針，每個(gè)鏈表節(jié)點(diǎn)維護(hù)節(jié)點(diǎn)u和一個(gè)相遇節(jié)點(diǎn)的相遇頻率信息，鏈表元素是結(jié)構(gòu)體{id, cf,Qp, next}，其中，id是和節(jié)點(diǎn)u相遇的節(jié)點(diǎn)標(biāo)識(shí)，cf是二者的相遇頻率，Qp是指向二者相遇記錄隊(duì)列Q的指針，next指向下一個(gè)節(jié)點(diǎn)。cf由Qp指向的隊(duì)列Q計(jì)算，節(jié)點(diǎn)首先將時(shí)間離散化，等分成若干區(qū)間，然后記錄每個(gè)區(qū)間內(nèi)節(jié)點(diǎn)相遇次數(shù)，即隊(duì)列Q的元素，最后依據(jù)區(qū)間數(shù)和相遇次數(shù)計(jì)算cf。

隊(duì)列 Q的設(shè)計(jì)采用只有尾指針的順序循環(huán)隊(duì)列，既節(jié)省空間又易于操作。在實(shí)際系統(tǒng)中時(shí)間是無(wú)限的，節(jié)點(diǎn)不可能記錄所有區(qū)間的相遇記錄。并且真實(shí)移動(dòng)軌跡中節(jié)點(diǎn)相遇具有波動(dòng)性，如節(jié)點(diǎn)在白天相遇頻繁，晚上則很少相遇。因此為節(jié)省存儲(chǔ)空間并反映節(jié)點(diǎn)相遇的最新趨勢(shì)，引入滑動(dòng)窗口的概念，即節(jié)點(diǎn)只記錄當(dāng)前W個(gè)區(qū)間的相遇次數(shù)。當(dāng)隊(duì)列已滿并統(tǒng)計(jì)新區(qū)間時(shí)，rear指針處插入一條新記錄，就會(huì)覆蓋一條最老的記錄。

圖2 節(jié)點(diǎn)維護(hù)相遇頻率的數(shù)據(jù)結(jié)構(gòu)

下面給出由Q計(jì)算cf的具體過(guò)程。節(jié)點(diǎn)在每次相遇時(shí)對(duì)相應(yīng)隊(duì)列Q執(zhí)行Q[rear]++；當(dāng)開始新的統(tǒng)計(jì)區(qū)間時(shí)，更新對(duì)應(yīng)的頻率值，但不需要遍歷整個(gè)隊(duì)列，因?yàn)橄嘤隹倲?shù)中只是多了rear指向的元素，少了rear將要覆蓋的元素，其他值都沒(méi)變，執(zhí)行代碼為：

在實(shí)際系統(tǒng)中，節(jié)點(diǎn)只需動(dòng)態(tài)地為相遇頻率較高的節(jié)點(diǎn)維護(hù)信息，所以L采用鏈?zhǔn)酱鎯?chǔ)。在真實(shí)移動(dòng)軌跡中，與一個(gè)節(jié)點(diǎn)反復(fù)相遇的節(jié)點(diǎn)集是有限的、固定的。如圖3所示，與一個(gè)節(jié)點(diǎn)相遇次數(shù)大于1次、100次和200次的節(jié)點(diǎn)數(shù)相差不大。因此，節(jié)點(diǎn)要么經(jīng)常相遇，要么很少相遇，甚至不相遇。

圖3 Infocom06數(shù)據(jù)集中節(jié)點(diǎn)相遇次數(shù)

下面給出機(jī)制在具體路由中的交互過(guò)程（以Epidemic路由為例），當(dāng) t時(shí)刻節(jié)點(diǎn)u和v相遇時(shí)，以v為例，消息交換過(guò)程如下。

1) 節(jié)點(diǎn)u和v交換消息列表l和相遇頻率表f，其中，l依據(jù)消息緩存生成，只包含消息id，f依據(jù)L生成，只包含節(jié)點(diǎn)id和相遇頻率。

3) 節(jié)點(diǎn) v依據(jù)消息效用和節(jié)點(diǎn)資源狀況計(jì)算向節(jié)點(diǎn)u的最終請(qǐng)求消息列表

4) 節(jié)點(diǎn)按照對(duì)方最終的請(qǐng)求消息列表順序交換消息直到一方?jīng)]有數(shù)據(jù)或鏈路斷開。

其中，rm是緩存m消耗的資源(如能量、存儲(chǔ)空間和網(wǎng)絡(luò)帶寬等)，而Rv是節(jié)點(diǎn) v當(dāng)前擁有的資源，本文僅表示緩存，xm=0代表不緩存消息m，xm=1緩存消息m。式(9)采用如下貪心算法求解。

1) 初始化背包載重量為Rv，背包價(jià)值量為0。

2) 把l'中消息按照效用值從高到低排序。

3) 從未被緩存的消息中選擇效用最高的消息m，如果 size(m)+size(M)gt;Rv則返回 M；否則執(zhí)行M=M∪{m}，然后重復(fù)3)的操作。其中，M是已經(jīng)緩存消息的集合，初始值為空，size()函數(shù)返回消息大小或消息集合的總大小。

3.4 開銷分析

UBT在提高網(wǎng)絡(luò)性能的同時(shí)，也帶來(lái)額外開銷，本節(jié)從存儲(chǔ)、通信和計(jì)算 3個(gè)方面分析 UBT的主要開銷。

存儲(chǔ)開銷主要來(lái)源于圖2的數(shù)據(jù)結(jié)構(gòu)，取決于鏈表L的長(zhǎng)度和隊(duì)列Q的長(zhǎng)度W。鏈表長(zhǎng)度就是節(jié)點(diǎn)頻繁相遇節(jié)點(diǎn)集合大小，從圖3可見(jiàn)其規(guī)模很小，設(shè) E(|L|)為鏈表長(zhǎng)度的數(shù)學(xué)期望，并且一個(gè)鏈表節(jié)點(diǎn)空間是 4倍的隊(duì)列元素空間，則空間開銷為(4+W)E(|L|)，為了能準(zhǔn)確計(jì)算節(jié)點(diǎn)相遇頻率，W的取值不小于10。

通信開銷是指除傳輸數(shù)據(jù)消息外，為實(shí)現(xiàn)UBT而傳輸?shù)目刂菩畔?，主要是在?jié)點(diǎn)相遇時(shí)交換消息列表l和相遇頻率表f。消息列表長(zhǎng)度取決于節(jié)點(diǎn)緩存大小和系統(tǒng)中消息流量大小，相遇頻率表的長(zhǎng)度為鏈表L的長(zhǎng)度，二者規(guī)模不大，而且l只包含消息id，f只包含節(jié)點(diǎn)id和相遇頻率信息。

計(jì)算開銷主要有 3個(gè)方面：1)計(jì)算相遇頻率，在 3.3節(jié)中已給出分布式計(jì)算過(guò)程，時(shí)間復(fù)雜度為O(1)；2)計(jì)算效用比較復(fù)雜，經(jīng)過(guò)3.2節(jié)的簡(jiǎn)化，其計(jì)算規(guī)模為，其中， E(|l′ |)是最終請(qǐng)求列表長(zhǎng)度的數(shù)學(xué)期望，E(|?|)是節(jié)點(diǎn)頻繁相遇節(jié)點(diǎn)集元素?cái)?shù)的數(shù)學(xué)期望，E(|L|)是節(jié)點(diǎn)相遇鏈表長(zhǎng)度的數(shù)學(xué)期望，其中，E(|L|)=E(|?|)；從3.3節(jié)可知，因此，E(|l′|)不超過(guò)節(jié)點(diǎn)消息隊(duì)列長(zhǎng)度，從圖3中可以看出E(|?|)規(guī)模不大；3) 計(jì)算最終緩存消息列表，即0-1背包問(wèn)題求解，其問(wèn)題規(guī)模是對(duì)l′進(jìn)行遍歷，其規(guī)模小于等于消息隊(duì)列長(zhǎng)度。

4 仿真實(shí)驗(yàn)

4.1 仿真設(shè)置

基于ONE[28]設(shè)計(jì)仿真實(shí)驗(yàn)，主要驗(yàn)證UBT和SBT的激勵(lì)效果并比較UBT和SBT的網(wǎng)絡(luò)性能，因此選擇簡(jiǎn)單的ER[29]為路由基礎(chǔ)實(shí)現(xiàn)SBT和UBT激勵(lì)機(jī)制，下文仿真結(jié)果中曲線ER和SBT分別表示無(wú)激勵(lì)機(jī)制的ER和基于SBT的ER，UBTi和UBTr表示基于UBT的2個(gè)ER路由，前者是基于式(4)的集中式計(jì)算的理論值，后者是基于式(5)的近似估計(jì)值。

仿真分別在合作場(chǎng)景和不同自私度場(chǎng)景下進(jìn)行仿真，并以ER性能作為比較參考線。比較的性能參數(shù)有投遞率、時(shí)延和網(wǎng)絡(luò)負(fù)載，其中，時(shí)延是統(tǒng)計(jì)成功投遞消息的平均時(shí)延，網(wǎng)絡(luò)負(fù)載是每個(gè)消息的平均轉(zhuǎn)發(fā)次數(shù)。

實(shí)驗(yàn)選擇 Infocom06真實(shí)移動(dòng)軌跡數(shù)據(jù)集和RWP移動(dòng)模型。其中，Infocom06數(shù)據(jù)集包含 98個(gè)內(nèi)部節(jié)點(diǎn)，實(shí)驗(yàn)時(shí)去除包含外部節(jié)點(diǎn)和相遇持續(xù)時(shí)間為 0的記錄，合并相遇區(qū)間重疊的記錄。在RWP移動(dòng)模型中，仿真區(qū)域?yàn)?00 m×100 m，節(jié)點(diǎn)數(shù)為60，通信半徑為5 m，初始時(shí)隨機(jī)分布在仿真區(qū)域，仿真開始后，節(jié)點(diǎn)選擇一個(gè)目的位置，以一定速度(在5～10 m/s區(qū)間隨機(jī)選擇)移動(dòng)到目的位置，然后停止一段時(shí)間(在1～10 s區(qū)間隨機(jī)選擇)后，再做重復(fù)運(yùn)動(dòng)，直到仿真終止。

在基于Infocom06的仿真中每隔0.01天生成一個(gè)消息；在基于RWP的仿真中，在仿真的前500 s每隔1 s生成一個(gè)消息。每個(gè)消息隨機(jī)選擇源節(jié)點(diǎn)和一個(gè)目的節(jié)點(diǎn)。為簡(jiǎn)化節(jié)點(diǎn)交易和緩存管理，消息大小相等，緩存大小即緩存消息的個(gè)數(shù)。為保證所有消息都能正常傳輸，仿真時(shí)間進(jìn)行到所有消息都到達(dá)生存時(shí)間為止。

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

1) 在合作環(huán)境下，為了比較UBT和SBT對(duì)網(wǎng)絡(luò)性能的影響，選取緩存大小為4和8時(shí)的ER為參照，在圖4和圖5中用ER_4和ER_8表示，并在緩存大小為4的參數(shù)下仿真UBT和SBT。首先分析ER_X參考線，然后比較SBT和UBT的性能。

在2種移動(dòng)模型下，隨著消息生存時(shí)間TTL的增加，投遞率、時(shí)延和網(wǎng)絡(luò)負(fù)載都基本呈增長(zhǎng)趨勢(shì)。其原因是隨著TTL增長(zhǎng)：①消息被轉(zhuǎn)發(fā)機(jī)會(huì)增多，導(dǎo)致網(wǎng)絡(luò)負(fù)載增加和投遞率增大；②意味著消息可以在更晚些時(shí)候到達(dá)目的節(jié)點(diǎn)，從而增加了時(shí)延，也提高了投遞率。在緩存受到限制時(shí)，TTL較大的情況下，Infocom06的投遞率隨TTL的增加而下降，如圖4(a)所示。因?yàn)殡STTL的增加網(wǎng)絡(luò)中同時(shí)存在的消息增多，因此在緩存受限情況下，TTL較大時(shí)，導(dǎo)致網(wǎng)絡(luò)擁塞，投遞率下降。而RWP的消息TTL最大為100 s，在網(wǎng)絡(luò)中同時(shí)存在消息不多，因此沒(méi)有導(dǎo)致網(wǎng)絡(luò)擁塞情況。

在2種移動(dòng)模型下，隨著節(jié)點(diǎn)緩存增加，投遞率增加，時(shí)延減小。這是因?yàn)榫彺嬖酱?，?jié)點(diǎn)同時(shí)緩存的消息增多，使消息在更短的時(shí)間內(nèi)被轉(zhuǎn)發(fā)的機(jī)會(huì)增大，所以投遞率增加，時(shí)延減小。但是在 2種移動(dòng)模型下的網(wǎng)絡(luò)負(fù)載隨緩存變化卻截然相反，如圖4(c)和圖5(c)所示。其原因是基于Infocom06的仿真中消息生存時(shí)間較長(zhǎng)，若緩存較小則容易溢出，導(dǎo)致反復(fù)緩存相同消息從而增加網(wǎng)絡(luò)負(fù)載；而基于RWP移動(dòng)模型的仿真中消息生存時(shí)間短，此時(shí)緩存越大帶來(lái)的轉(zhuǎn)發(fā)機(jī)會(huì)越多從而增加網(wǎng)絡(luò)負(fù)載。

SBT和UBT性能曲線升降趨勢(shì)和原因與ER的基本一致。SBT_4的投遞率和時(shí)延性能不如ER_4，但網(wǎng)絡(luò)負(fù)載低于ER_4；而UBTi_4和UBTr_4的性能遠(yuǎn)優(yōu)于ER_4，其中，投遞率與時(shí)延性能和ER_8的相當(dāng)，而網(wǎng)絡(luò)負(fù)載遠(yuǎn)低于ER_8。因?yàn)镾BT和ER盲目緩存，影響網(wǎng)絡(luò)性能，而且SBT實(shí)行等價(jià)交換原則，因而減小了網(wǎng)絡(luò)負(fù)載，但也降低了投遞率和時(shí)延性能；而 UBT優(yōu)先緩存那些能被下游節(jié)點(diǎn)以較高概率投遞到目的節(jié)點(diǎn)的消息，因此 UBT能用較小的緩存獲得較高的投遞率和較小的時(shí)延。UBTr_4與UBTi_4的性能相近，但是UBTr_4計(jì)算簡(jiǎn)單且易于在實(shí)際系統(tǒng)中實(shí)現(xiàn)。

圖4 Infocom06移動(dòng)模型下TTL對(duì)網(wǎng)絡(luò)性能影響

圖5 RWP移動(dòng)模型下TTL對(duì)網(wǎng)絡(luò)性能影響

2) 在自私環(huán)境下，為了驗(yàn)證UBT和SBT的激勵(lì)效果，并比較其在不同自私度下的網(wǎng)絡(luò)性能，在基于Infocom06的仿真中，選取TTL為0.8天和緩存為4時(shí)的數(shù)據(jù)，在基于RWP的實(shí)驗(yàn)中選擇TTL為80 s和緩存為4時(shí)的數(shù)據(jù)。

如圖6和圖7所示，ER在沒(méi)有任何激勵(lì)機(jī)制情況下，隨自私節(jié)點(diǎn)增多，系統(tǒng)中數(shù)據(jù)的轉(zhuǎn)發(fā)次數(shù)減少，因而網(wǎng)絡(luò)負(fù)載減小，但是也降低了投遞率，增加了時(shí)延。而在SBT和UBT激勵(lì)下的ER，受自私節(jié)點(diǎn)數(shù)影響不大；UBT的性能優(yōu)于SBT，同樣是因?yàn)?UBT通過(guò)效用緩存提高了網(wǎng)絡(luò)性能，用較小的網(wǎng)絡(luò)負(fù)載獲得較高的投遞率和較小的時(shí)延。UBTr_4與UBTi_4的性能相近，可見(jiàn)UBTr_4的估計(jì)值與理論值相差不大，且易于實(shí)現(xiàn)。

圖6 Infocom06移動(dòng)模型下自私度對(duì)網(wǎng)絡(luò)性能的影響

圖7 RWP移動(dòng)模型下自私度對(duì)網(wǎng)絡(luò)性能的影響

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

本文設(shè)計(jì)了一種基于效用的“物—物交換”（UBT）激勵(lì)機(jī)制，提高了簡(jiǎn)單“物—物交換”（SBT）激勵(lì)機(jī)制的網(wǎng)絡(luò)性能，實(shí)驗(yàn)證明，UBT不僅能有效激勵(lì)節(jié)點(diǎn)協(xié)作，而且和SBT相比，能用較小的緩存獲得較高的投遞率和較低的時(shí)延。下一步工作將該機(jī)制應(yīng)用于機(jī)會(huì)網(wǎng)絡(luò)數(shù)據(jù)分發(fā)場(chǎng)景，并建立性能分析模型。

[1] BOLDRINI C, LEE K, ?NEN M, et al. Opportunistic networks[J].Computer Communications, 2014, 48(14):1-4.

[2] 熊永平,孫利民,牛建偉,等. 機(jī)會(huì)網(wǎng)絡(luò)[J]. 軟件學(xué)報(bào), 2009, 20(1):124-137.XIONG Y P, SUN L M, NIU J W, et al. Opportunistic networks [J].Journal of Software, 2009, 20(1): 124-137.

[3] 馬華東, 袁培燕, 趙東. 移動(dòng)機(jī)會(huì)網(wǎng)絡(luò)路由問(wèn)題研究進(jìn)展[J]. 軟件學(xué)報(bào), 2015, 26(3): 600-616.MA H D, YUAN P Y, ZHAO D. Research progress on routing problem in mobile opportunistic networks[J]. Journal of Software, 2015,26(3): 600-616.

[4] SERMPEZIS P, SPYTOPOULOS T. Understanding the effects of social selfishness on the performance of heterogeneous opportunistic networks[J]. Computer Communications, 2014, 48(1): 71-83.

[5] LIU L. A survey on reputation-based incentive mechanism in opportunistic networks[J]. Applied Mechanics amp; Materials, 2014, 543-547:4288-4290.

[6] ZHU H, LIN X, LU R, et al. SMART: a secure multilayer credit-based incentive scheme for delay-tolerant networks[J]. IEEE Transactions on Vehicular Technology, 2009, 58(8): 4628-4639.

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

[8] XIAO M, WU J, LIU C, et al. TOUR: time-sensitive opportunistic utility-based routing in delay tolerant networks[J]. Proceedings- IEEE INFOCOM, 2013, 12(11): 2085-2091.

[9] ZHANG X, WANG X F, LIU A N, et al. PRI: a practical reputation-based incentive scheme for delay tolerant networks[J]. Ksii Transactions on Internet and Information Systems, 2012, 6(4): 973-988.

[10] CIOBANU R I, DOBRE C, DASCALU M, et al. SENSE: a collaborative selfish node detection and incentive mechanism for opportunistic networks[J]. Journal of Network and Computer Applications, 2014,41(1): 240-249.

[11] YAO L, MAN Y, HUANG Z, et al. Secure routing based on social similarity in opportunistic networks[J]. IEEE Transactions on Wireless Communications, 2015,15(1): 594-605.

[12] NING T, YANG Z, XIE X, et al. Incentive-aware data dissemination in delay-tolerant mobile networks[C]//2011 8th Annual IEEE Communications Society Conference on Sensor, Mesh and Ad Hoc Communications and Networks (SECON`2011).2011: 539-547.

[13] WANG Y, CHUAH M C, CHEN Y. Incentive driven information sharing in delay tolerant mobile networks[C]//2012 IEEE Global Communications Conference. 2012: 5279-5284.

[14] CHEN B B, CHAN M C. MobiCent: a credit-based incentive system for disruption tolerant network[C]//2010 Proceedings IEEE INFOCOM. San Diego, 2010:1-9.

[15] XIE Y, ZHANG Y. A secure, service priority-based incentive scheme for delay tolerant networks[J]. Security amp; Communication Networks,2015, 9(1): 5-18.

[16] 任智, 索建偉, 劉文朋, 等. 基于多方議價(jià)博弈的機(jī)會(huì)網(wǎng)絡(luò)高吞吐量低開銷概率路由算法[J]. 通信學(xué)報(bào), 2015, 36(6): 45-52.REN Z, SUO J W, LIU W P, et al. High-throughput and low-overhead probabilistic routing based on multi-player bargaining game for opportunistic networks[J]. Journal on Communications, 2015, 36(6):45-52.

[17] 趙廣松, 陳鳴. 自私性機(jī)會(huì)網(wǎng)絡(luò)中激勵(lì)感知的內(nèi)容分發(fā)的研究[J].通信學(xué)報(bào), 2013, 34(2): 73-84.ZHAO G S, CHEN M. Research of incentive-aware data dissemination in selfish opportunistic networks[J]. Journal on Communications,2013, 34(2):73-84.

[18] 李云, 于季弘, 尤肖虎. 資源受限的機(jī)會(huì)網(wǎng)絡(luò)節(jié)點(diǎn)激勵(lì)策略研究[J].計(jì)算機(jī)學(xué)報(bào), 2013, 36(5): 947-956.LI Y, YU J K, YOU X H. An incentive protocol for opportunistic net-works with resources constraint[J]. Chinese Journal of Computers,2013, 36(5): 947-956.

[19] 蔣慶豐, 門朝光, 李香, 等. 基于虛擬貨幣的 DTNs激勵(lì)感知低時(shí)延路由[J]. 計(jì)算機(jī)研究與發(fā)展, 2015, 52(12): 2707-2724.JIANG Q F, MEN C G, LI X, et al. A virtual currency-based incentive-aware low delay routing for DTN[J]. Journal of Computer Research and Development, 2015, 52(12): 2707-2724.

[20] MENASCHE D S, MASSOULIE L, TOWSLEY D. Reciprocity and barter in peer-to-peer systems[C]//2010 Proceedings IEEE INFOCOM.San Diego, 2010: 1-9.

[21] LIU L, YANG Q, KONG X, et al. Com-BIS: a community-based barter incentive scheme in socially aware networking[J]. International Journal of Distributed Sensor Networks, 2015, 2015(1):1-14.

[22] LI L. A survey on barter-based incentive mechanism in opportunistic networks[C]// International Symposium on Instrumentation and Measurement, Sensor Network and Automation. 2013:365-367.

[23] SAHA B K, MISRA S, PAL S. Utility-based exploration for performance enhancement in opportunistic mobile networks[J]. IEEE Transactions on Computers, 2016, 65(4):1.

[24] GAO W, CAO G. User-centric data dissemination in disruption tolerant networks[C]//Infocom 2011. 2011:3119-3127.

[25] LIU Q, MENG X U, YUN L I, et al. Routing algorithm in opportunistic network based on historical utility[J]. Journal of Computer Applications, 2013, 33(2): 361-364.

[26] LIN C J, CHEN C W, CHOU C F. Preference-aware content dissemination in opportunistic mobile social networks[J]. 2012 Proceedings IEEE INFOCOM, Orlando, 2012, 131(5): 1960-1968.

[27] ZHANG X, NEGLIA G, KUROSE J, et al. Performance Modeling of Epidemic Routing[J]. Computer Networks, 2007, 51(10): 2867-2891.

[28] KERANEN A, JORG O, KARKKAINEN T. The opportunistic network environment simulator[EB/OL]. http://www.netlab.tkk.fi/tutkimus/dtn/theone/.2013-11-008.

[29] VAHDAT A, BECKER D. Epidemic routing for partially-connected ad hoc networks[R]. Duke University, 2000.CS-200006.

Utility-based barter trade incentive scheme in opportunistic network

YAO Jian-sheng1,2, MA Chun-guang1, YUAN Qi1
(1. College of Computer Science and Technology, Harbin Engineering University, Harbin 150001, China;2. College of Computer Science, Jilin Normal University, Siping 136000, China)

In opportunistic networks, existing simple barter trade (SBT) incentive scheme degraded the network performance due to the blindly caching strategy. So a utility-based barter trade (UBT) incentive mechanism was proposed. In the UBT scheme, nodes cache messages by predicting their future encounters and the probability that the encounters forward these messages to their destinations, which improved the caching efficiency and the network performance. Simulated results show that, compared with SBT, UBT can obtain higher delivery ratio and lower delay by less network cost and effectively motivate nodes’ cooperation as well.

opportunistic networks, selfishness, barter trade incentive mechanisms, utility

s: The National Natural Science Foundation of China (No.61472097), Education Ministry Doctoral Research Foundation of China (No.20132304110017)

TP393

A

10.11959/j.issn.1000-436x.2016182

2016-04-06；

2016-06-17

國(guó)家自然科學(xué)基金資助項(xiàng)目（No.61472097）；高等學(xué)校博士學(xué)科點(diǎn)專項(xiàng)科研基金資助項(xiàng)目（博導(dǎo)類）（No.20132304110017）

姚建盛（1980-），男，吉林農(nóng)安人，哈爾濱工程大學(xué)博士生，主要研究方向?yàn)闄C(jī)會(huì)網(wǎng)絡(luò)路由和激勵(lì)機(jī)制。

馬春光（1974-），男，黑龍江雙鴨山人，博士，哈爾濱工程大學(xué)教授、博士生導(dǎo)師，主要研究方向?yàn)槊艽a學(xué)、信息安全、物聯(lián)網(wǎng)和機(jī)會(huì)網(wǎng)絡(luò)。

袁琪（1973-），女，黑龍江齊齊哈爾人，哈爾濱工程大學(xué)博士生，主要研究方向?yàn)闊o(wú)線傳感器網(wǎng)絡(luò)、信息安全。