一種基于節(jié)點(diǎn)活躍度和消息副本的DTN緩存策略

摘 要：本文針對(duì)DTN中基于洪泛算法，提出了機(jī)遇節(jié)點(diǎn)活躍和消息副本數(shù)目的緩存策略，旨在少量增加消息平均傳輸延遲外，大大提高了消息交付比率，降低了開銷比率。實(shí)驗(yàn)結(jié)果表明MC算法具有較優(yōu)的性能。

關(guān)鍵詞：洪泛算法；緩存策略；交付比率；開銷比率

中圖分類號(hào)：TN929.5

DTN（Delay Tolerant Network）路由是一個(gè)非常復(fù)雜的問題，其中一個(gè)極大問題就是DTN的節(jié)點(diǎn)資源有限，而且針對(duì)有限節(jié)點(diǎn)資源（如緩存、節(jié)點(diǎn)能量、帶寬等）的研究工作很少。DTN中的各個(gè)節(jié)點(diǎn)收到新消息后，先將消息存儲(chǔ)在自己的緩存空間中，然后等待，直到合適的下一跳節(jié)點(diǎn)到來(lái)才將該消息復(fù)制轉(zhuǎn)發(fā)給下一跳節(jié)點(diǎn)，因此消息被緩存的時(shí)間非常長(zhǎng)。當(dāng)節(jié)點(diǎn)的存儲(chǔ)空間有限、網(wǎng)絡(luò)中的通信量較大時(shí)，緩存空間不足時(shí)如何丟棄消息以騰出空間給新來(lái)的消息很重要。當(dāng)接收節(jié)點(diǎn)的緩存已滿時(shí)，節(jié)點(diǎn)必須騰出空間來(lái)存儲(chǔ)新消息，因此必須設(shè)計(jì)合適的緩存機(jī)制來(lái)解決該問題。

1 相關(guān)工作

常用的緩存管理策略有：先進(jìn)先出（FIFO）、后進(jìn)先出（LIFO）、隨機(jī)（Random），這些策略在傳統(tǒng)存在端到端路徑的網(wǎng)絡(luò)中運(yùn)行效果良好，但是在DTN中緩存受限的情況下，路由協(xié)議的性能將受到很大的影響。Epidemic算法[1，2]在緩存受限情況下，延時(shí)性能將急劇下降。文獻(xiàn)[2]中，Zhang等人評(píng)估了緩存受限情況下在Epidemic協(xié)議中使用的一些簡(jiǎn)單的丟棄策略。文獻(xiàn)[3]利用網(wǎng)絡(luò)全局信息提出了一種策略，并指出策略的不足之處，但是在DTN中能夠及時(shí)掌握全局信息，是較為困難的事情。

基于洪泛的路由算法（如Epidemic）工作原理是：源節(jié)點(diǎn)產(chǎn)生一個(gè)消息之后，擴(kuò)散給n個(gè)中繼節(jié)點(diǎn)，中繼節(jié)點(diǎn)以相同的方式進(jìn)行進(jìn)一步的復(fù)制擴(kuò)散。其中n為所有源節(jié)點(diǎn)的鄰居節(jié)點(diǎn)數(shù)。在一些改進(jìn)算法中限制了n的取值為一個(gè)常數(shù)a。而這些算法均不能根據(jù)緩存動(dòng)態(tài)調(diào)整消息副本數(shù)目。

2 基于消息副本的緩存算法（MC）

假設(shè)緩存隊(duì)列中的存在一個(gè)消息，并且設(shè)n的值為某個(gè)常數(shù)b，則消息通過一跳后網(wǎng)絡(luò)中消息m的副本數(shù)為1+b。這樣傳遞下去，隨著跳數(shù)的增加，消息副本數(shù)呈現(xiàn)出指數(shù)增長(zhǎng)，然而跳數(shù)的增長(zhǎng)和時(shí)間增長(zhǎng)一致，因此消息的增長(zhǎng)數(shù)隨時(shí)間呈指數(shù)增長(zhǎng)。文獻(xiàn)[4]提出了路徑爆發(fā)現(xiàn)象：在大多情況下，最優(yōu)路徑經(jīng)過很長(zhǎng)一段時(shí)間首先到達(dá)目的節(jié)點(diǎn)，緊接著許多路徑會(huì)在相對(duì)較短的時(shí)間內(nèi)相繼到達(dá)目的節(jié)點(diǎn)，這些路徑為次優(yōu)路徑，次優(yōu)路徑數(shù)隨時(shí)間呈指數(shù)增長(zhǎng)的趨勢(shì)。

針對(duì)DTN中每個(gè)新生成的消息，同時(shí)記下它的副本數(shù)目num。當(dāng)攜帶新生成消息的節(jié)點(diǎn)遇到下一個(gè)節(jié)點(diǎn)時(shí)，如果該節(jié)點(diǎn)沒有攜帶消息，則把消息的num加1，再將該消息傳給遇到的節(jié)點(diǎn)。根據(jù)各個(gè)小的num值，可以大致推斷出來(lái)，num越大，該消息已經(jīng)被復(fù)制多次，在網(wǎng)絡(luò)中存有它的副本較多；否則反之。

文獻(xiàn)[5]中指出根據(jù)消息副本數(shù)目值的大小，來(lái)決定刪除何種消息。該算法是當(dāng)一個(gè)節(jié)點(diǎn)的緩存不夠的情況下，刪除num值較大的那個(gè)消息。但沒有考慮如果該節(jié)點(diǎn)的活躍度較強(qiáng)時(shí)，就意味著該節(jié)點(diǎn)遇到目的節(jié)點(diǎn)的可能性更大。這樣盲目刪除副本數(shù)大的消息，同時(shí)降低了更接近目的節(jié)點(diǎn)的概率。

故在本文算法MC設(shè)計(jì)中，在刪除副本數(shù)目之前先判斷一下節(jié)點(diǎn)j的活躍度，hj（即在單位時(shí)間內(nèi)，一個(gè)節(jié)點(diǎn)鄰居數(shù)目）相對(duì)上一跳節(jié)點(diǎn)i的活躍度hi的大小，如果比值大于1，同時(shí)節(jié)點(diǎn)j緩存空間不夠，這時(shí)也只是按比例部分刪除副本的數(shù)目，即保留眾多消息中，刪除副本數(shù)目最大的消息副本數(shù)目直至為numj*┌hi/，hj┐。

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

采用芬蘭赫爾辛基理工大學(xué)開發(fā)的DTN仿真工具ONE，同樣采用了文獻(xiàn)[5]中，同樣的環(huán)境配置：即4500m×3400m的城市地圖，共設(shè)置了6組共126個(gè)節(jié)點(diǎn)，節(jié)點(diǎn)的運(yùn)動(dòng)模式都是采用基于地圖的最短路徑運(yùn)動(dòng)模式。其中前兩組每組40個(gè)節(jié)點(diǎn)，其速度為0.5～1.5m/s，模擬行人的運(yùn)動(dòng)軌跡；第3組節(jié)點(diǎn)數(shù)目為40，其速度為2.7～13.9m/s，模擬汽車的運(yùn)動(dòng)軌跡；后3組每組2個(gè)節(jié)點(diǎn)，運(yùn)行速度為7～10m/s，且只能在指定的軌道上運(yùn)動(dòng)，模擬有軌電車。每個(gè)節(jié)點(diǎn)的傳輸范圍為10m，傳輸速度為250kBps。仿真時(shí)間設(shè)置為43000s，其間每隔25～35秒隨機(jī)挑取節(jié)點(diǎn)對(duì)生成一個(gè)新的消息，消息大小為500kB～1MB，消息TTL為6h。我們?cè)谶@個(gè)實(shí)驗(yàn)環(huán)境下分別運(yùn)行了采取不同緩存丟棄策略的Epidemic協(xié)議。

3.1 采用不同緩存策略對(duì)Epidemic進(jìn)行分析

同文獻(xiàn)[5]一樣設(shè)置節(jié)點(diǎn)緩存大小從5M變化到50M，觀察各種緩存丟棄算法對(duì)Epidemic協(xié)議性能的影響。交付比率、開銷比率和平均延時(shí)分別如圖1、圖2、圖3所示。MC算法較之LIFO、FIFO，除了平均延時(shí)少有增加外，其他指標(biāo)均有較好的性能。

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

本文中設(shè)計(jì)的MC算法由于考慮了節(jié)點(diǎn)活躍度和節(jié)點(diǎn)副本數(shù)，除了在延時(shí)方面比其他傳統(tǒng)算法要略高之外，其他性能均優(yōu)。

參考文獻(xiàn)：

[1]Spyropoulos T，Psounis K，Raghavendra C S.Spray and wait：an efficient routing scheme for intermittently connected mobile networks.ACM SIGCOMM Workshop on Delay-Tolerant Networking （WDTN’05），2005：252-259.

[2]Zhang X，Neglia G，Kurose J F.Performance modeling of epidemic routing. Computer Networks，2006（51）：2867-2891.

[3]Krifa A，Barakat C，Spyropoulos T.Optimal buffer management policies for delay tolerant networks.IEEE SECON，2008：260-268.

[4]Erramilli V，Chaintreau A，Crovella M.Diversity of forwarding paths in pocket switched networks.ACM SIGCOMM IMC，2007：161-174.

[5]朱敬.延遲容忍網(wǎng)絡(luò)路由協(xié)議的研究[D].中南大學(xué)，2009：43-44.

作者簡(jiǎn)介：趙紅敏（1978-），女，河南鄭州人，講師，碩士，研究方向：無(wú)線網(wǎng)絡(luò)協(xié)議分析。

作者單位：中南林業(yè)科技大學(xué) 計(jì)算機(jī)與信息工程學(xué)院，長(zhǎng)沙 410004

基金項(xiàng)目：湖南省高等學(xué)?？茖W(xué)研究項(xiàng)目（項(xiàng)目編號(hào)：11C1306）。