延遲容忍網(wǎng)絡(luò)中面向數(shù)據(jù)傳輸?shù)募顧C制研究

張 巖

延遲容忍網(wǎng)絡(luò)中面向數(shù)據(jù)傳輸?shù)募顧C制研究

張 巖

數(shù)據(jù)傳輸問題一直是DTN中的研究熱點,已有的數(shù)據(jù)傳輸算法均假設(shè)網(wǎng)絡(luò)結(jié)點為從不拒絕向其他結(jié)點提供服務(wù)的合作型結(jié)點，然而由于功率、存儲空間、連接機會等結(jié)點資源有限，實際上DTN未必總是滿足上述假設(shè)。為了解決已有算法的不足，針對支持自私結(jié)點和多興趣類型的DTN獨特環(huán)境，提出綜合了基于獎金的激勵機制和面向興趣的傳輸概率的一種新的激勵機制，并將結(jié)點通信建模為雙人合作博弈，通過Nash理論求解。最后，基于實際數(shù)據(jù)展開廣泛的模擬仿真，從數(shù)據(jù)傳輸率、時延、開銷方面對本文算法進行評估，仿真結(jié)果表明，算法的性能更優(yōu)。

延遲容忍網(wǎng)絡(luò)；數(shù)據(jù)傳輸；激勵機制；合作博弈；時延

0 引言

圖1 DTN中數(shù)據(jù)傳輸示例

本文重點研究移動無線網(wǎng)絡(luò)的數(shù)據(jù)傳輸問題，該型網(wǎng)絡(luò)由蜂窩手機、PDA、筆記本等移動設(shè)備組成。與基于蜂窩信道導(dǎo)致用戶承擔(dān)額外成本的數(shù)據(jù)通信方案不同，本文算法利用手機、PDA、筆記本普遍支持的無成本、低功率、短范圍（比如 Wifi或藍牙）無線傳輸功能，來建立間斷性連接的數(shù)據(jù)通信移動網(wǎng)絡(luò)。由于無線傳輸范圍較小，結(jié)點移動性不受限制，網(wǎng)絡(luò)連通性很低且動態(tài)性較高，其中一個結(jié)點只是偶爾與其他結(jié)點相連，進而形成容延網(wǎng)絡(luò)（DTN）[1]。如圖1所示：對運動、新聞和兼職招聘信息感興趣。他可以通過蜂窩信道下載信息，但成本太高。他經(jīng)常光顧咖啡廳、餐廳、教學(xué)樓，這些地方都普遍支持AP訪問點，因此，他希望對這些訪問點加以利用。他可以下載體育新聞或者兼職招聘信息，滿足自己需求的同時，通過藍牙或Wifi空閑給無法訪問AP訪問點的其他移動用戶（比如用戶B）共享信息。于是，數(shù)據(jù)傳播時可以不必指定接收方，只需宣布消息內(nèi)容的類型即可。路由傳輸不再尋找端到端路徑，而是網(wǎng)絡(luò)根據(jù)消息類型把數(shù)據(jù)傳輸給感興趣的用戶。

然而，DTN中的參與結(jié)點可能為合作結(jié)點也可能為自私結(jié)點。如果所有結(jié)點為合作結(jié)點，則每個結(jié)點都可以為其他結(jié)點義務(wù)攜帶部分消息。另一方面，如果一些結(jié)點受到自身的能量、緩存和帶寬等因素的影響，則它們可能除了自己感興趣的內(nèi)容外拒絕攜帶其他人的消息，從而成為自私結(jié)點。最壞情況下，所有結(jié)點均為自私結(jié)點，所有移動設(shè)備無任何數(shù)據(jù)共享，網(wǎng)絡(luò)性能很低。為此，急需開發(fā)一種激勵方案來促進結(jié)點合作，從而提高數(shù)據(jù)傳輸?shù)男省?/p>

1 相關(guān)工作

DTN數(shù)據(jù)傳播示例中，用戶A裝備了一個智能手機，

數(shù)據(jù)傳輸問題一直是DTN中的研究熱點之一，相繼有眾多研究者提出了一系列用于DTN數(shù)據(jù)傳輸?shù)姆椒?，如文獻[2] 提出了一種考慮用戶社交關(guān)系同時提高信息傳輸效率為目的數(shù)據(jù)傳輸方法。仿真實驗結(jié)果表明，該算法具有更高的數(shù)據(jù)傳輸成功率以及更低的傳輸時延，同時保證了節(jié)點更好的安全性。文獻[3]提出了一種在資源受限D(zhuǎn)TN網(wǎng)絡(luò)中高效數(shù)據(jù)傳輸?shù)腂AR(Buffer Aware Transmission Policy for DTNs)協(xié)議，BAR利用節(jié)點的相遇概率信息來提高中繼的方向性，還利用當前緩存信息來提高資源的利用效率。仿真結(jié)果表明，與現(xiàn)有的幾種主流傳輸策略相比，BAR在投遞率、傳輸延遲和資源消耗等方面都具有明顯的優(yōu)勢。文獻[4]提出了一種基于相對距離感知的動態(tài)數(shù)據(jù)傳輸策略RDAD。該策略采用傳感器節(jié)點到匯聚點的相對距離來計算節(jié)點傳輸概率的大小，并以此作為消息傳輸時選擇下一跳的依據(jù)。模擬實驗表明，RDAD 能夠以較低的數(shù)據(jù)傳輸能耗和傳輸延遲獲得較高的數(shù)據(jù)傳輸成功率，并且具有相對較長的網(wǎng)絡(luò)壽命。文獻[5]提出了一種基于概率復(fù)制的數(shù)據(jù)傳輸策略 PRD用于空間中間斷連通的延遲容忍移動傳感器網(wǎng)絡(luò)(DTMSN)數(shù)據(jù)傳輸。PRD由選擇復(fù)制策略和隊列管理組成，前者根據(jù)節(jié)點將消息傳遞給匯聚點的可能性，選擇下一跳進行復(fù)制傳輸；隊列管理則利用引入傳輸概率及復(fù)制數(shù)的消息生存時間決定隊列中消息丟棄原則。仿真分析表明，與現(xiàn)有的幾種數(shù)據(jù)傳輸策略相比，PRD 能以較低的數(shù)據(jù)復(fù)制數(shù)及傳輸延遲獲得較高的數(shù)據(jù)傳輸成功率。

另外還有，文獻[6]提出一種基于網(wǎng)絡(luò)編碼的高效廣播數(shù)據(jù)傳輸機制(NEBT)，基站傳感器節(jié)點將原始廣播數(shù)據(jù)分批進行編碼，以此來降低節(jié)點間的數(shù)據(jù)相似度，降低廣播時延；同時，傳感器節(jié)點根據(jù)自身的廣播增益，根據(jù)鄰居節(jié)點相對自身運動趨勢準確選擇數(shù)據(jù)交互時機，降低通信開銷。仿真結(jié)果表明，與常見的泛洪等機制相比，NEBT能進一步降低廣播時延并大幅度降低通信開銷。文獻[7]提出了一種基于分布式群組移動的事件分類傳輸策略 GMED。通過有效地發(fā)現(xiàn)和利用傳感器節(jié)點在運動過程中形成的群組，建立基于群組的事件分類傳輸模型，改善數(shù)據(jù)傳輸性能。仿真結(jié)果表明，GMED 能以較低的數(shù)據(jù)傳輸能耗和傳輸延遲獲得較高的數(shù)據(jù)傳輸成功率，且網(wǎng)絡(luò)壽命相對較長。

然而，以上的這些解決方案均假設(shè)網(wǎng)絡(luò)結(jié)點為從不拒絕向其他結(jié)點提供服務(wù)的合作型結(jié)點。由于功率、存儲空間、連接機會等結(jié)點資源有限，實際上DTN未必總是滿足上述假設(shè)。于是，結(jié)點如果不能獲得好處，一般不會向其他結(jié)點提供服務(wù)。所以，必須要有合適的激勵機制，以促進結(jié)點間的合作。激勵機制可分為3類：基于名譽的機制、基于獎金的機制和基于交換的機制。人們針對DTN提出了幾種激勵機制。例如，文獻[8]提出了配對Tit-for-Tat DTN激勵機制，以在TFT約束下實現(xiàn)結(jié)點吞吐量最大化。在文獻[9]中，每個報文被加密，結(jié)點著眼自身利益為網(wǎng)絡(luò)其他結(jié)點轉(zhuǎn)發(fā)數(shù)據(jù)。中繼結(jié)點需要向利益給予結(jié)點展現(xiàn)數(shù)據(jù)成功轉(zhuǎn)發(fā)的相關(guān)證據(jù)。否則，利益給予結(jié)點將在整個網(wǎng)絡(luò)廣播行為異常信息，最終將行為異常結(jié)點從網(wǎng)絡(luò)中刪除。文獻[10]提出了一種基于獎金的容擾網(wǎng)絡(luò)激勵機制，通過集成信用和加密技術(shù)解決結(jié)點間的邊緣插入和邊緣隱藏攻擊。它需要源結(jié)點和目的結(jié)點始終能夠訪問一個高可用性網(wǎng)絡(luò)，以進行消息控制，同時需要一個可靠的第三方負責(zé)驗證和支付服務(wù)管理。此外，文獻[11]提出一種 DTN社交自私路由算法，結(jié)點利用社交意愿度來確定是否為其他結(jié)點轉(zhuǎn)發(fā)報文。然而這些DTN激勵機制考慮的網(wǎng)絡(luò)和應(yīng)用環(huán)境與本文不同（例如，文獻[8,9]重點研究了單播問題，本文主要研究一對多通信模式），所以無法直接用于本文研究中。鑒于此，本文在現(xiàn)有研究工作的基礎(chǔ)上，對DTN中面向數(shù)據(jù)傳輸?shù)募顧C制展開研究，提出了一種改進的激勵機制，最后，基于實際數(shù)據(jù)展開廣泛的模擬仿真，從數(shù)據(jù)傳輸率、時延、開銷方面驗證了本文算法的有效性。

2 問題建模

本文考慮的結(jié)點自私且具有理性行為。更具體地，一個結(jié)點受其利益驅(qū)使。它只有能夠獲得收益了才會傳輸數(shù)據(jù)。否則，它不會消耗自己資源幫助他人，但也不會惡意攻擊他人。此外，我們假設(shè)具有驗證服務(wù)，結(jié)點不會通過偽造身份來進行欺騙，以獲得免費的轉(zhuǎn)發(fā)服務(wù)或者從其他結(jié)點獲得更多便宜。針對支持自私結(jié)點和多興趣類型的DTN獨特環(huán)境，本文提出綜合了基于獎金的激勵機制和面向興趣的傳輸概率的一種新的激勵機制。

2.1 相關(guān)定義

為便于闡述，我們首先介紹幾種基本概念，以此為基礎(chǔ)給出本文激勵機制。

定義1. 興趣是指結(jié)點希望得到的數(shù)據(jù)類型。

興趣例子包括：博客更新，分期賬單通知，天氣預(yù)報，事件提醒，商業(yè)廣告，各種新聞。

定義2. 興趣源是指生成對應(yīng)興趣相關(guān)數(shù)據(jù)消息的結(jié)點。

定義3. 興趣匯點是指希望獲得并且消費對應(yīng)興趣數(shù)據(jù)消息的結(jié)點。

對多種興趣，一個結(jié)點可能既是源結(jié)點也是匯點。同時，某個興趣的數(shù)據(jù)消息可能由多個源提供，多個結(jié)點可能是同一興趣的匯點。假設(shè)網(wǎng)絡(luò)有N個興趣類型，每個結(jié)點都是至少一個、最多N個興趣的匯點。

定義 4. 結(jié)點n關(guān)于興趣i的有效興趣接觸概率(EICP)表示結(jié)點n直接或間接接觸興趣i的匯點的概率。

EICP表示一個結(jié)點將數(shù)據(jù)以感興趣類型發(fā)送給它匯點的概率。該概率的值從本質(zhì)上取決于結(jié)點的移動性，由直接和間接接觸概率匯總而得。前一種概率，即結(jié)點n興趣i的直接興趣接觸概率，表示結(jié)點i直接接觸興趣i匯點的概率。后一種概率，即間接興趣接觸概率，表示結(jié)點i以間接方式通過其他結(jié)點，把數(shù)據(jù)傳遞給興趣i匯點的概率。本文采用指數(shù)加權(quán)移動均值（EWMA）算法來維護更新結(jié)點的有效興趣接觸概率[12]。EWMA算法是在線估計最有效的算法之一，在多個領(lǐng)域中得到廣泛應(yīng)用。該算法內(nèi)容簡單，計算量低，對微量位移的響應(yīng)及時，存儲空間需求穩(wěn)定。當兩個結(jié)點相遇時，其中任一結(jié)點均可執(zhí)行計算任務(wù)，更新結(jié)點的有效興趣接觸概率。

具體而言，每個結(jié)點維持一個計時器。如果在Δ時間內(nèi)與其他結(jié)點無接觸，計時器到期，生成過期事件。表示結(jié)點n興趣i的直接接觸概率。初始化為 0，每次與興趣i結(jié)點接觸或發(fā)生過期事件時進行更新（以先發(fā)生者為準）。更新函數(shù)如公式（1）：

其中，0≤α≤1為常數(shù)，用于存儲部分歷史接觸狀態(tài)。

定義5. 獎金是指用于激勵自私結(jié)點的虛擬貨幣。

設(shè)nλ為結(jié)點n的獎金量。nλ初始化為Λ，在消息傳輸時進行更新，這一點將在2.2節(jié)具體討論。

定義6. 獎勵策略明確了一個結(jié)點如何獲得獎金。

為對雙人合作博弈提供支持（將在 2.3節(jié)討論），我們采用了如下簡單獎勵策略：如果結(jié)點n從結(jié)點m接收到與其興趣相匹配的消息，前者向后者獎勵一個獎金。如果發(fā)送的消息與接收方興趣不匹配，則結(jié)點即不獲得獎金，也不支付獎金。

定義7. 每個數(shù)據(jù)消息關(guān)聯(lián)一個復(fù)制度，表示該消息的拷貝數(shù)量。

定義8. 每個數(shù)據(jù)消息關(guān)聯(lián)一個消息估價，表示消息的潛在價值。

定義9. 預(yù)期獎金獎勵表示結(jié)點獲得數(shù)據(jù)消息后預(yù)期獲得的獎金。

定義10. 當結(jié)點n與其他結(jié)點相遇時，需要決定是否與該結(jié)點交換信息。由于自身的自私性，如果進行消息交換，則結(jié)點n希望實現(xiàn)其預(yù)期獎金獎勵最大化。結(jié)點n此時在做出決策將要用到的效用函數(shù)為公式（5）：

其中，Un為結(jié)點n的效用函數(shù)，I為興趣類型總數(shù)，和分別為消息交換前和交換后，興趣i的消息集合。

2.2 本文激勵機制概述

基于以上定義，將本文激勵機制闡述如下。為方便討論，我們假設(shè)每個數(shù)據(jù)消息，比如結(jié)點n處的消息m，關(guān)聯(lián)了一個描述性元數(shù)據(jù)，內(nèi)容包括它的興趣類型（i），序列號（m），估價（），復(fù)制度（）。設(shè)為結(jié)點n的消息元數(shù)據(jù)集合，Φn為結(jié)點n的 EICP列表（即

當結(jié)點n與另一個結(jié)點（比如結(jié)點k）相遇時，遵循以下5個步驟獲得必要信息，并做出消息交換決策：

第四步：結(jié)點n和k然后協(xié)商交易哪些消息。這一過程描述為雙人合作博弈，并用Nash理論獲得最優(yōu)解，確定結(jié)點n和k將要交換的兩個最終消息列表，表示為Ln和Lk且。雙人合作博弈模型及其基于 Nash理論的求解方法將在3.3節(jié)做詳細討論。

第五步：最后，結(jié)點n和k按對交換Ln和Lk的消息。

2.3 博弈模型和Nash求解方法

在上節(jié)所述的激勵機制中，第4步涉及雙人合作博弈理論，需要詳細探討。根據(jù)文獻[14]可知，通過假設(shè)結(jié)點為理性結(jié)點（它們的行為受自身利益驅(qū)使），兩個結(jié)點間的交互可以建模為雙人合作博弈。博弈雙方理性且自私。換句話說，各方不會惡意損害他方利益，這為雙方合作打下了基礎(chǔ)。另一方面，由于本性自私，每方目的不同。請注意，該自私行為可能促進合作，也可能阻礙合作，具體視其能否給他們帶來利益決定。例如，根據(jù)本文網(wǎng)絡(luò)環(huán)境，自私結(jié)點的目的是實現(xiàn)式5定義的效用函數(shù)最大化。一個結(jié)點通過獲得新的數(shù)據(jù)消息可以提高它的效用函數(shù)。但這也會增加數(shù)據(jù)消息的復(fù)制度，降低其他結(jié)點的效用函數(shù)。雙人合作博弈允許各方根據(jù)可能發(fā)生沖突的利益情況，達成約束協(xié)定。這與禁止雙方達成約束協(xié)定的非合作博弈剛好相反。鑒于雙方的自私本性，只有惠及雙方才能達成約束協(xié)定。

通過實現(xiàn)Nash積最大化，獲得雙人合作博弈最優(yōu)解（或者Nash解）[14]，即公式（6）：

雖然上文對最優(yōu)解做了總體描述，但是在實際網(wǎng)絡(luò)中計算該最優(yōu)解非常復(fù)雜，原因有二：一是每個結(jié)點擁有的數(shù)據(jù)消息數(shù)量巨大，二是從所有可能解中確定和將會消耗大量時間。為此，通過每次考慮一對消息，我們采用了一種簡單的近似策略。具體來說，對每組消息和，通過假設(shè)消息mn和mk在結(jié)點n和k間交換來計算對應(yīng)的Nash積。選擇Nash積最大的一對消息進行交易。時間復(fù)雜度為。重復(fù)以上過程，直到結(jié)點n和k間的連接斷開，或者Ln或Lk為空，或者式6無解。

請注意，結(jié)點n發(fā)送消息m給結(jié)點k時，它仍然保存了消息的一份拷貝，且復(fù)制度做了更新。因此，網(wǎng)絡(luò)狀態(tài)穩(wěn)定后，結(jié)點數(shù)據(jù)隊列可能變滿。接收到一個消息后，意味著替換預(yù)期獎金獎勵最低的現(xiàn)有消息。在計算效用增益時，需要計算該消息的損失，也就是說，丟失的消息從式5的中排除。

3 仿真實驗

我們通過仿真實驗對本文激勵機制進行了性能評估。本節(jié)首先介紹實驗配置，然后進行性能比較和討論。

3.1 仿真設(shè)置

本文將文獻[15]中的劍橋大學(xué)Haggle項目和文獻[16]中的UMass DieselNet項目的跟蹤數(shù)據(jù)用作本文仿真。這兩個項目分別代表人類社交網(wǎng)絡(luò)和車載網(wǎng)絡(luò)。對Haggle項目，稱為iMotes的移動結(jié)點分發(fā)給參加IEEE INFOCOM會議的50名人員。它的數(shù)據(jù)集包括iMotes和藍牙設(shè)備間的通信情況。我們采用的數(shù)據(jù)集有98個iMotes和藍牙設(shè)備，仿真時間總共持續(xù)342915秒（或3天）。對UMass DieselNet項目，基于30-40輛公交車構(gòu)建DTN測試床，獲得約150平方英里的區(qū)域。跟蹤數(shù)據(jù)提供了公交車間的通信事件。本文仿真基于2012年1250847秒（或兩周）內(nèi)37輛公交車獲得的跟蹤數(shù)據(jù)。

我們通過改變結(jié)點的合作程度來對不同機制加以比較：“直接”機制(Direct)，結(jié)點間不存在合作，結(jié)點只從對應(yīng)的 AP訪問點下載自己感興趣的消息；“自我交換”機制(SelfExchange)，結(jié)點從AP或者移動結(jié)點處獲得感興趣的消息，但不攜帶自己不感興趣的消息；“隨機合作”機制(CooperRdm)，相遇結(jié)點隨機選擇部分消息（不僅僅包括自己感興趣的消息）進行交換；“合作”機制(Cooperative)，結(jié)點采取完全合作態(tài)度，在滿足自己需求后選擇攜帶最具價值的消息；本文“激勵”機制(Incentive)。另外，本文默認的網(wǎng)絡(luò)仿真環(huán)境有3個AP訪問點，15類興趣。源結(jié)點消息生成速率為每100秒一個消息。為充分反映歷史狀態(tài)的影響，式1和2中的和β均為0.1。我們隨機選擇部分結(jié)點為AP訪問點，運行20次以上仿真然后取均值作為最終結(jié)果。

我們的目標是將數(shù)據(jù)消息發(fā)送給對應(yīng)的匯點，且延時和流量開銷盡量低。在本文仿真研究中，我們對如下性能評估指標感興趣：整個網(wǎng)絡(luò)范圍的數(shù)據(jù)傳輸率，結(jié)點接收率分布情況，平均傳輸延時，消息轉(zhuǎn)發(fā)開銷。網(wǎng)絡(luò)數(shù)據(jù)傳輸率定義為被傳輸?shù)南⒖偭颗c應(yīng)該傳輸給網(wǎng)絡(luò)的消息總量之比。結(jié)點的接收率為結(jié)點感興趣的消息總量和源結(jié)點生成的結(jié)點感興趣消息總量之比。平均傳輸延時描述為結(jié)點得到感興趣消息需要的等待時間。消息轉(zhuǎn)發(fā)開銷是個成本因子，定義為消息傳遞的通信成本。開銷較低意味著網(wǎng)絡(luò)傳輸流量較低。

3.2 性能比較

如表1和表2所示：

表1 基于HAGGLE數(shù)據(jù)的總體性能比較

表2 基于DIESELNET數(shù)據(jù)的總體性能比較

基于Haggle和DieselNet數(shù)據(jù)對不同算法總體性能做了評估。從兩表可以看出，合作方案的網(wǎng)絡(luò)數(shù)據(jù)傳輸率最高，其次是激勵機制、合作隨機機制、自我交換機制、直接機制。合作機制的傳輸率最高，背后原因是：結(jié)點在滿足自己興趣后展開無私互助，始終選擇價值最大的消息傳送，因此該方案中的消息被傳達給興趣結(jié)點的概率最大。同時，我們注意到，雖然合作隨機機制也采取完全合作策略，結(jié)點愿意免費攜帶其他結(jié)點的消息，但是它的傳輸率遠低于本文激勵機制；這證明我們必須要利用消息的估計價值來決定是否值得攜帶該消息，尤其是當存儲資源有限時更是如此。對本文激勵機制，消息的估計價值有效促進了結(jié)點間的合作，高效利用了通信資源（由結(jié)點容量和結(jié)點會面概率決定），因此提高了傳輸率。最后，如果消息僅是隨機轉(zhuǎn)發(fā)，則消息的傳輸率變低。由于自我交換機制中，結(jié)點只交換它們感興趣的消息，拒絕攜帶其他結(jié)點感興趣的消息，大大限制了消息傳遞，降低了傳輸率。類似地，直接機制中的結(jié)點不存在合作，傳輸率最低。

合作機制和激勵機制的平均時延遠低于其他機制，原因是兩種機制均使用消息價值來估計消息的傳輸概率，并選擇最佳路由轉(zhuǎn)發(fā)消息，因此降低了消息的傳遞時間。雖然合作機制的傳遞率和平均時延均優(yōu)于激勵機制，但我們可以看出，前者的開銷遠大于后者，原因是它的無私性增加了消息在網(wǎng)絡(luò)中的復(fù)制量和分發(fā)量。相反，本文激勵機制中的結(jié)點，只有確認消息可以為其帶來收益時才會接收一份消息拷貝，因此開銷很低。很明顯，直接機制和自我交換機制結(jié)點只接收自己感興趣的消息，因此開銷始終為1如圖2所示：

圖2 基于Haggle數(shù)據(jù)的接收率分布、延時分布和開銷分布

圖2和圖3分別描述了基于Haggle和DieselNet數(shù)據(jù)時，各種機制的接受率、平均時延和結(jié)點開銷。如上文所述，直接機制和自我交換機制的開銷始終為1，因此此處省略。圖2表明，本文激勵機制大約48％的結(jié)點可以接收到90％自己感興趣的消息，直接機制的結(jié)點比例為 11％，自我交換機制為13％，合作隨機機制為35％。雖然合作機制52％的結(jié)點的接收率超過90％，但是30％的結(jié)點的開銷超過20。這表明，這些結(jié)點始終扮演中繼角色，對網(wǎng)絡(luò)的貢獻大于其他結(jié)點。相反，本文激勵機制促進了結(jié)點合作，允許結(jié)點在個體興趣和網(wǎng)絡(luò)貢獻間尋求平衡。如圖3所示：

于是，所有結(jié)點的開銷均低于 10。如圖2(b)所示，激勵機制 56％的結(jié)點在兩小時內(nèi)接收到感興趣消息，而直接機制、自我交換機制、隨機合作機制 20％以上結(jié)點的平均時延超過9小時。圖3基于DieselNet的結(jié)果也表現(xiàn)了類似趨勢。

圖3 基于DieselNet數(shù)據(jù)的接收率分布、延時分布和開銷分布

AP訪問點數(shù)量變化時不同機制和性能，如圖4所示：

圖4 AP訪問點數(shù)量變化

所有AP點通過互聯(lián)網(wǎng)，與按照一定速率生成消息的源結(jié)點相連。AP點數(shù)量上升后，結(jié)點有更多機會訪問數(shù)據(jù)源，更新消息緩存。這也解釋了為什么圖4(a)和4(b)中，所有機制的傳遞率上升而平均延時下降。我們也觀察到，合作機制的平均傳遞率只比本文激勵機制高3％左右，開銷比本文機制高5倍左右，如圖4(c)所示。這說明，激勵機制的交換過程大大降低了傳輸成本，同時保證了傳遞率和平均時延達到滿意水平。

圖5通過改變消息生成率來比較各機制的性能。在圖5(a)中，消息生成率變大時，直接機制、自我交換機制和隨機合作機制的傳遞率均有所下降，激勵機制和合作機制保持穩(wěn)定。消息生成速率變大時，源結(jié)點將會生成更多的消息。源結(jié)點生成的消息越多，網(wǎng)絡(luò)需要攜帶的負載越多。如果直接機制和自我交換機制等機制的結(jié)點對網(wǎng)絡(luò)貢獻有限，則在可接受的延時內(nèi)，源結(jié)點將會積聚更多消息，無法發(fā)送給對應(yīng)的匯點，降低了傳遞率。對合作機制，結(jié)點盡力提高消息發(fā)送量，無私貢獻它們的緩存和能量。這便解釋了它的傳遞率為何可以保持穩(wěn)定。下面解釋為何本文激勵機制的傳遞率沒有下降。原因是：新消息的價值始終較高，自私結(jié)點愿意獲得這些高價值結(jié)點，以實現(xiàn)收益最大化，如圖5所示：

圖5 數(shù)據(jù)消息生成速率變化

傳遞率穩(wěn)定的同時，開銷有所上升，因為有更多的消息在傳輸期間被復(fù)制。消息生成率上升后，延時增加，如圖5(b)所示。由于各個結(jié)點的資源有限，消息生成率越大，消息在源結(jié)點和中間結(jié)點的等待時間越長，延時也就越長。

興趣類型數(shù)量對網(wǎng)絡(luò)的影響，如圖6所示：

圖6 興趣類型數(shù)量變化

我們假設(shè)至少有一個興趣，最多有N個興趣，其中N是興趣類型最大值。圖6(a)表明，興趣類型增多時，自我交換、隨機合作和合作機制的傳遞率下降，激勵機制略有上升。這是因為結(jié)點興趣量較多時，激勵機制中的結(jié)點間展開合作，增加了消息在結(jié)點間互相傳遞的概率。從圖6(b)可以看出，除了直接機制外，所有機制的平均延時均略微上升。從圖6(c)可以看出，本文激勵機制的開銷比較穩(wěn)定。這是因為結(jié)點只選擇效益最大的消息進行交易，從不把資源浪費在搭便車行為上。

4 結(jié)論和未來工作

本文對延遲容忍網(wǎng)絡(luò)中面向數(shù)據(jù)傳輸?shù)募顧C制問題展開了研究。考慮到延遲容忍網(wǎng)絡(luò)的獨特性、連通的間斷性、結(jié)點興趣的多樣性，對于中間結(jié)點，一個消息的價值主要取決于由它發(fā)送消息的概率。該概率本身的估計值非常重要。此外，可能有多個移動用戶需要同一個消息。所以，該消息可能被多次“買”給不同的接收方。另外，消息在傳輸過程中可能會生成多個拷貝，接收方只為收到的第一個拷貝“買單”。這些特點綜合到一起后，大大增加了激勵機制開發(fā)的特殊性、有趣性和復(fù)雜性。鑒于此，本文提出了一種改進的激勵機制，并將結(jié)點通信表述為雙人合作博弈，通過 Nash理論求解，最后通過仿真實驗驗證了本文算法的有效性。我們下一步工作的重點是對DTN中節(jié)點間通信的可靠性進行建模，研究DTN中基于機會路由的數(shù)據(jù)傳輸可靠性問題。

[1] 李向群, 劉立祥, 胡曉惠, 等. 延遲/中斷可容忍網(wǎng)絡(luò)研究進展[J]. 計算機研究與發(fā)展, 2009, 46(8):1270-1277

[2] 黃海平, 盛勇華, 徐佳, 等. 一種基于社交關(guān)系的容遲網(wǎng)絡(luò)數(shù)據(jù)傳輸方法[J]. 解放軍理工大學(xué)學(xué)報, 2013,14(4)：123-130

[3] 陳卓, 馮大權(quán). BAT: 一種資源受限 DTN 中的高效數(shù)據(jù)傳輸策略[J]. 計算機工程與應(yīng)用, 2011, 47(21):28-30

[4] 許富龍, 劉明, 龔海剛, 等. 延遲容忍傳感器網(wǎng)絡(luò)基于相對距離的數(shù)據(jù)傳輸[J]. 軟件學(xué)報, 2010, 21(3):490-504

[5] 張可, 曾家智, 劉偉. 延遲容忍移動傳感器網(wǎng)絡(luò)中基于概率復(fù)制的數(shù)據(jù)傳輸策略及其性能研究[J]. 電子與信息學(xué)報, 2010, 32(3): 677-681

[6] 楊奎武, 郭淵博, 鄭康鋒, 等. 延遲容忍移動傳感器網(wǎng)絡(luò)高效廣播數(shù)據(jù)傳輸機制[J]. 北京郵電大學(xué)學(xué)報,2013, 1(18):167-175

[7] 吳磊, 王曉敏, 劉明, 等. 延遲容忍傳感器網(wǎng)絡(luò)中基于群組運動的事件傳輸[J]. Journal of Software, 2012,23(3)：629-647

[8] Shevade U, Song H H, Qiu L, et al. Incentive-aware routing in DTNs[C]. Network Protocols, 2008. ICNP 2008. IEEE International Conference on. IEEE, 2008:238-247.

[9] Mei A, Stefa J. Give2get: Forwarding in social mobile wireless networks of selfish individuals [J]. Dependable and Secure Computing, IEEE Transactions on, 2012, 9(4):569-582

[10] Chen B B, Chan M C. Mobicent: a credit-based incentive system for disruption tolerant network[C]. INFOCOM,2010 Proceedings IEEE. IEEE, 2010: 1-9

[11] Li Q, Zhu S, Cao G. Routing in socially selfish delay tolerant networks[C]. INFOCOM, 2010 Proceedings IEEE. IEEE, 2010: 1-9

[12] Wang Y, Wu H. Delay/fault-tolerant mobile sensor network (dft-msn): A new paradigm for pervasive information gathering [J]. Mobile Computing, IEEE Transactions on, 2007, 6(9): 1021-1034

[13] Jelasity M, Montresor A, Babaoglu O. Gossip-based aggregation in large dynamic networks [J]. ACM Transactions on Computer Systems (TOCS), 2005, 23(3):219-252

[14] Gu Y, Fan J, Tang G, et al. Maximum latency scheduling problem on two-person cooperative games [J]. Journal of Combinatorial Optimization, 2013: 1-11

[15] J. Scott, R. Gass, J. Crowcroft, P. Hui, C. Diot, and A.Chaintreau. CRAWDAD trace cambridge/haggle/imote/infocom. Downloaded from http://crawdad.cs.dartmouth.edu/cambridge/haggle/imote/infocom, Jan. 2006

[16] J. Burgess, B. N. Levine, R. Mahajan, J. Zahorjan, A.Balasubramanian, A. Venkataramani, Y. Zhou, B. Croft, N.Banerjee, M. Corner, and D. Towsley. CRAWDAD data set umass/diesel. Downloaded from http://crawdad.cs.

[17] dartmouth.edu/umass/diesel, Sept. 2008

Research on Incentive Mechanism for Data Transmission in Delay Tolerant Networks

Zhang Yan
(Dalian Commercial School,Dalian116033, China)

Data transmission problem is a research hotspot in delay tolerant networks. The existing data transmission algorithms assume that nodes in the network are cooperative and never declining service to other nodes. Such assumption is not always true in a real social network since the resources of a node, such as power, storage, and connection opportunities, are limited. To solve the lack of existing algorithms, under the unique setting of a DTN with selfish nodes and multiple interests types, we propose a novel incentive scheme that incorporates credit-based stimulation mechanism and interest-oriented delivery probability, and model the nodal communication as a two-person cooperative game, whose solution is found by using the Nash Theorem. Finally, extensive simulations are carried out based on real-world traces to evaluate the proposed scheme in terms of data delivery rate, delay and overhead.Simulation results show that the proposed algorithm performs better.

Delay Tolerant Networks; Data Transmission; Incentive Mechanism; Cooperative Game; Delay

TP393

：A

1007-757X(2014)04-0001-08

2014.04.03）

2011年國家自然科學(xué)基金面上項目（項目編號：61173051/F020104）

張巖（1962-），女，大連商業(yè)學(xué)校，遼寧大連人，碩士，講師，研究方向：DTN網(wǎng)絡(luò)，信息檢索，大連，116033