姚建盛，馬春光，袁琪

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

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

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

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

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

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

1 引言

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

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

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

以上2種激勵機(jī)制都將下一跳節(jié)點(diǎn)的轉(zhuǎn)發(fā)行為當(dāng)作服務(wù)，增加了在機(jī)會網(wǎng)絡(luò)環(huán)境下的設(shè)計難度。相比之下，BUTTYáN[7]設(shè)計的基于barter的激勵機(jī)制，本文簡稱為簡單“物—物交換”（SBT，simplebarter trade）激勵機(jī)制，該激勵機(jī)制簡單、有效、易于實(shí)現(xiàn)。但SBT在激勵節(jié)點(diǎn)幫助其他節(jié)點(diǎn)緩存消息時并未考慮未來會和誰相遇以及相遇節(jié)點(diǎn)的需求，這會導(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)了帶寬和存儲資源，而且會因阻礙緩存合適消息而降低網(wǎng)絡(luò)性能。

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

2 相關(guān)工作

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

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

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

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

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

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

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

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

3.1 效用值計算

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

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

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

3.2 度量值預(yù)測

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

在實(shí)際系統(tǒng)中，節(jié)點(diǎn)只需動態(tài)地為相遇頻率較高的節(jié)點(diǎn)維護(hù)信息，所以L采用鏈?zhǔn)酱鎯?。在真?shí)移動軌跡中，與一個節(jié)點(diǎn)反復(fù)相遇的節(jié)點(diǎn)集是有限的、固定的。如圖3所示，與一個節(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ī)制在具體路由中的交互過程（以Epidemic路由為例），當(dāng) t時刻節(jié)點(diǎn)u和v相遇時，以v為例，消息交換過程如下。

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)資源狀況計算向節(jié)點(diǎn)u的最終請求消息列表

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

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

1) 初始化背包載重量為Rv，背包價值量為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ò)性能的同時，也帶來額外開銷，本節(jié)從存儲、通信和計算 3個方面分析 UBT的主要開銷。

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

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

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

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

4.1 仿真設(shè)置

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

5 結(jié)束語

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

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

[2] 熊永平,孫利民,牛建偉,等. 機(jī)會網(wǎng)絡(luò)[J]. 軟件學(xué)報, 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] 馬華東, 袁培燕, 趙東. 移動機(jī)會網(wǎng)絡(luò)路由問題研究進(jìn)展[J]. 軟件學(xué)報, 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] 任智, 索建偉, 劉文朋, 等. 基于多方議價博弈的機(jī)會網(wǎng)絡(luò)高吞吐量低開銷概率路由算法[J]. 通信學(xué)報, 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ī)會網(wǎng)絡(luò)中激勵感知的內(nèi)容分發(fā)的研究[J].通信學(xué)報, 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ī)會網(wǎng)絡(luò)節(jié)點(diǎn)激勵策略研究[J].計算機(jī)學(xué)報, 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激勵感知低時延路由[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

國家自然科學(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ī)會網(wǎng)絡(luò)路由和激勵機(jī)制。

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

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