基于效用的機會網絡“物—物交換”激勵機制

姚建盛，馬春光，袁琪

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

基于效用的機會網絡“物—物交換”激勵機制

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

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

針對機會網絡環境下簡單“物—物交換”（SBT, simple barter trade）激勵機制因盲目緩存而降低網絡性能的問題，設計一種基于效用的“物—物交換”（UBT, utility-based barter trade）激勵機制。UBT通過預測未來相遇節點和相遇節點轉發消息到目的節點的概率進行緩存決策從而提高了緩存效率和網絡性能。仿真實驗證明，和SBT相比，UBT在有效激勵節點協作的同時能用更少的網絡負載獲得更高的投遞率和更低的時延。

機會網絡；自私；“物—物交換”激勵機制；效用

1 引言

機會網絡[1,2]利用節點移動帶來的接觸機會實現不存在完整通信鏈路的節點間通信，這使手持便攜設備和車載設備等可以隨時隨地感知并擴散熱點區域信息，滿足物聯網泛在互聯與透徹感知的需求[3]，對IoT和普適計算有重要意義。

機會網絡之所以能實現間歇性連接網絡的通信，在于采用“存儲—攜帶—轉發”的路由模型，這顯然需要節點間的協作。然而，在實際機會網絡系統中，節點為了節省資源或安全等原因往往不愿意為其他節點緩存、攜帶并轉發數據，這種自私行為嚴重影響了機會網絡性能[4]。

針對自私問題，傳統激勵機制主要有基于reputation的激勵機制[5]和基于credit的激勵機制[6]，然而機會通信為設計這些激勵機制帶來很大挑戰。在基于 reputation的激勵機制中，監測下一跳節點的轉發行這一關鍵問題在間歇性鏈接的機會網絡中較難實現。在基于credit的激勵機制中，通常需要可信第三方或特殊硬件保障電子貨幣的可信，并需要解決向誰支付和支付多少的問題，這在拓撲高度動態的分布式機會網絡中也很難實現。

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

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

2 相關工作

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

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

在基于credit的激勵機制中，節點通過提供轉發服務獲取虛擬貨幣，然后用虛擬貨幣換取其他節點的轉發服務。如不向外提供服務，自己也沒有“資金”購買服務。然而，機會網絡的高度動態拓撲和隨機性路由使源節點很難預知向誰支付和支付多少的問題。為此，NING等[12]提出僅向最終投遞者支付酬金的激勵機制；MuRIS[13]通過定價和回報函數激勵節點協作；MobiCent[14]通過博弈論和算法機制設計激勵相容的支付機制；SIS[15]提出基于服務優先權的激勵機制代替credit機制。

國內學者在將傳統激勵機制應用于機會網絡的研究中也做了大量工作[16～19]。然而以上激勵機制研究都將下一跳節點的轉發當作服務，利用某種度量（信譽或虛擬貨幣）衡量節點提供服務的多少，決定其獲得服務的資本。這雖然增強了激勵機制的靈活性，如便于服務的轉移或傳遞，但也增加了在機會網絡環境下的設計難度。

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

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

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

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

3.1 效用值計算

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

設d是消息m的目的節點，tr是消息m的剩余生存時間，?v是節點v的中繼節點集，則v緩存消息m的效用為

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

3.2 度量值預測

本節給出效用計算中相關度量值的預測方法。

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

在經典獨立同分布移動模型下，文獻[27]已經驗證了在節點通信半徑遠小于移動區域時，節點相遇過程服從 Poisson分布，并給出相遇頻率的計算方法，即，其中，r是節點無線傳輸半徑，E[V*]是節點移動速度的數學期望，A是節點移動區域，θ是依賴于不同移動模型的常數，在RWP移動模型下θ=1.368 3。

在真實移動軌跡模型中，主流文獻認為節點相遇過程服從 Poisson分布[24,26]，但是也有研究人員認為服從冪率分布[2,3]。下面用皮爾遜χ2準則驗證Infocom06數據集近似服從Poisson分布并給出相遇頻率計算方法。

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

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

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

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

圖1 節點v的緩存

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

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

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

3.3 機制設計

在前面的效用計算中獲得節點相遇頻率是關鍵，3.2節給出在獨立同分布的經典移動模型下節點相遇頻率計算式和在真實移動軌跡中的計算方法，本節針對真實移動軌跡給出計算節點相遇頻率的詳細設計。

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

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

圖2 節點維護相遇頻率的數據結構

下面給出由Q計算cf的具體過程。節點在每次相遇時對相應隊列Q執行Q[rear]++；當開始新的統計區間時，更新對應的頻率值，但不需要遍歷整個隊列，因為相遇總數中只是多了rear指向的元素，少了rear將要覆蓋的元素，其他值都沒變，執行代碼為：

在實際系統中，節點只需動態地為相遇頻率較高的節點維護信息，所以L采用鏈式存儲。在真實移動軌跡中，與一個節點反復相遇的節點集是有限的、固定的。如圖3所示，與一個節點相遇次數大于1次、100次和200次的節點數相差不大。因此，節點要么經常相遇，要么很少相遇，甚至不相遇。

圖3 Infocom06數據集中節點相遇次數

下面給出機制在具體路由中的交互過程（以Epidemic路由為例），當 t時刻節點u和v相遇時，以v為例，消息交換過程如下。

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

3) 節點 v依據消息效用和節點資源狀況計算向節點u的最終請求消息列表

4) 節點按照對方最終的請求消息列表順序交換消息直到一方沒有數據或鏈路斷開。

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

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

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

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

3.4 開銷分析

UBT在提高網絡性能的同時，也帶來額外開銷，本節從存儲、通信和計算 3個方面分析 UBT的主要開銷。

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

通信開銷是指除傳輸數據消息外，為實現UBT而傳輸的控制信息，主要是在節點相遇時交換消息列表l和相遇頻率表f。消息列表長度取決于節點緩存大小和系統中消息流量大小，相遇頻率表的長度為鏈表L的長度，二者規模不大，而且l只包含消息id，f只包含節點id和相遇頻率信息。

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

4 仿真實驗

4.1 仿真設置

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

仿真分別在合作場景和不同自私度場景下進行仿真，并以ER性能作為比較參考線。比較的性能參數有投遞率、時延和網絡負載，其中，時延是統計成功投遞消息的平均時延，網絡負載是每個消息的平均轉發次數。

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

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

4.2 仿真結果與分析

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

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

在2種移動模型下，隨著節點緩存增加，投遞率增加，時延減小。這是因為緩存越大，節點同時緩存的消息增多，使消息在更短的時間內被轉發的機會增大，所以投遞率增加，時延減小。但是在 2種移動模型下的網絡負載隨緩存變化卻截然相反，如圖4(c)和圖5(c)所示。其原因是基于Infocom06的仿真中消息生存時間較長，若緩存較小則容易溢出，導致反復緩存相同消息從而增加網絡負載；而基于RWP移動模型的仿真中消息生存時間短，此時緩存越大帶來的轉發機會越多從而增加網絡負載。

SBT和UBT性能曲線升降趨勢和原因與ER的基本一致。SBT_4的投遞率和時延性能不如ER_4，但網絡負載低于ER_4；而UBTi_4和UBTr_4的性能遠優于ER_4，其中，投遞率與時延性能和ER_8的相當，而網絡負載遠低于ER_8。因為SBT和ER盲目緩存，影響網絡性能，而且SBT實行等價交換原則，因而減小了網絡負載，但也降低了投遞率和時延性能；而 UBT優先緩存那些能被下游節點以較高概率投遞到目的節點的消息，因此 UBT能用較小的緩存獲得較高的投遞率和較小的時延。UBTr_4與UBTi_4的性能相近，但是UBTr_4計算簡單且易于在實際系統中實現。

圖4 Infocom06移動模型下TTL對網絡性能影響

圖5 RWP移動模型下TTL對網絡性能影響

2) 在自私環境下，為了驗證UBT和SBT的激勵效果，并比較其在不同自私度下的網絡性能，在基于Infocom06的仿真中，選取TTL為0.8天和緩存為4時的數據，在基于RWP的實驗中選擇TTL為80 s和緩存為4時的數據。

如圖6和圖7所示，ER在沒有任何激勵機制情況下，隨自私節點增多，系統中數據的轉發次數減少，因而網絡負載減小，但是也降低了投遞率，增加了時延。而在SBT和UBT激勵下的ER，受自私節點數影響不大；UBT的性能優于SBT，同樣是因為 UBT通過效用緩存提高了網絡性能，用較小的網絡負載獲得較高的投遞率和較小的時延。UBTr_4與UBTi_4的性能相近，可見UBTr_4的估計值與理論值相差不大，且易于實現。

圖6 Infocom06移動模型下自私度對網絡性能的影響

圖7 RWP移動模型下自私度對網絡性能的影響

5 結束語

本文設計了一種基于效用的“物—物交換”（UBT）激勵機制，提高了簡單“物—物交換”（SBT）激勵機制的網絡性能，實驗證明，UBT不僅能有效激勵節點協作，而且和SBT相比，能用較小的緩存獲得較高的投遞率和較低的時延。下一步工作將該機制應用于機會網絡數據分發場景，并建立性能分析模型。

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

[2] 熊永平,孫利民,牛建偉,等. 機會網絡[J]. 軟件學報, 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]. 軟件學報, 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]. 通信學報, 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].通信學報, 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].計算機學報, 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]. 計算機研究與發展, 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

國家自然科學基金資助項目（No.61472097）；高等學校博士學科點專項科研基金資助項目（博導類）（No.20132304110017）

姚建盛（1980-），男，吉林農安人，哈爾濱工程大學博士生，主要研究方向為機會網絡路由和激勵機制。

馬春光（1974-），男，黑龍江雙鴨山人，博士，哈爾濱工程大學教授、博士生導師，主要研究方向為密碼學、信息安全、物聯網和機會網絡。

袁琪（1973-），女，黑龍江齊齊哈爾人，哈爾濱工程大學博士生，主要研究方向為無線傳感器網絡、信息安全。