DTN中基于消息綜合屬性的緩存管理策略

崔建群,余東海,常亞楠,孫佳悅,鄔 堯

(華中師范大學(xué) 計(jì)算機(jī)學(xué)院,武漢 430079)

1 引 言

延遲容忍網(wǎng)絡(luò)[1](Delay Tolerant Network,DTN)是指能在長(zhǎng)時(shí)延、連接頻繁斷開(kāi)等受限網(wǎng)絡(luò)條件下進(jìn)行通信的一種新型網(wǎng)絡(luò)體系.DTN網(wǎng)絡(luò)中節(jié)點(diǎn)密度稀疏且傳輸范圍有限,節(jié)點(diǎn)之間很難進(jìn)行通信[2],因此DTN利用節(jié)點(diǎn)的移動(dòng),當(dāng)節(jié)點(diǎn)進(jìn)入彼此的通信范圍時(shí),通過(guò)節(jié)點(diǎn)建立連接實(shí)現(xiàn)通信.然而,節(jié)點(diǎn)的移動(dòng)性同樣會(huì)導(dǎo)致連接中斷情況的發(fā)生,使得DTN網(wǎng)絡(luò)具有間歇性連接的特點(diǎn)[3].

網(wǎng)絡(luò)間歇性連接和節(jié)點(diǎn)的移動(dòng)性等因素使得相鄰節(jié)點(diǎn)在很長(zhǎng)時(shí)間內(nèi)無(wú)法進(jìn)行通信,節(jié)點(diǎn)需要長(zhǎng)時(shí)間攜帶消息等待下一次通信機(jī)會(huì),因此DTN通過(guò)在傳輸層和應(yīng)用層之間添加一個(gè)捆綁層,采取“存儲(chǔ)-攜帶-轉(zhuǎn)發(fā)”[4]路由機(jī)制進(jìn)行數(shù)據(jù)傳輸:當(dāng)節(jié)點(diǎn)接收一個(gè)消息,將其存儲(chǔ)在緩存中,在移動(dòng)時(shí)攜帶此消息,在下一次與其他節(jié)點(diǎn)連接時(shí)根據(jù)路由策略進(jìn)行消息轉(zhuǎn)發(fā).

DTN路由策略分為單拷貝策略和多拷貝策略[5].前者消耗資源較少但很難實(shí)現(xiàn)消息的成功傳輸,為了增加消息的投遞率和降低傳輸時(shí)延,通常采用多拷貝策略.多拷貝策略下,由于價(jià)格、體積等因素的影響[3],節(jié)點(diǎn)有限的緩存空間無(wú)法滿足大量消息副本的存放需求,導(dǎo)致在傳輸過(guò)程中部分消息副本遭到丟棄而無(wú)法到達(dá)目的節(jié)點(diǎn),從而使得整體網(wǎng)絡(luò)投遞率下降.因此,如何制定有效的緩存管理策略,對(duì)不同消息副本進(jìn)行分類和評(píng)估,做到有針對(duì)性的存放和刪除消息副本,是提高網(wǎng)絡(luò)整體性能所需要解決的關(guān)鍵問(wèn)題之一.

傳統(tǒng)的緩存管理策略不考慮或只考慮單一的消息屬性對(duì)消息進(jìn)行丟棄,具有一定的盲目性.近年來(lái),國(guó)內(nèi)外大量科學(xué)文獻(xiàn)對(duì)傳統(tǒng)緩存管理策略進(jìn)行了改進(jìn),多集中于通過(guò)將消息屬性進(jìn)行疊加來(lái)確定消息優(yōu)先級(jí),并依據(jù)此制定出消息丟棄策略,以得到網(wǎng)絡(luò)性能的提升[6-8].然而,在實(shí)際網(wǎng)絡(luò)環(huán)境中,消息屬性對(duì)網(wǎng)絡(luò)性能的影響程度會(huì)隨著時(shí)間的推移而不斷變化,大多數(shù)文獻(xiàn)并未對(duì)這一變化進(jìn)行深入討論,因此其方法有待進(jìn)一步改進(jìn)和提升.

本文在Spray and Wait[9]路由算法的基礎(chǔ)上提出了一種基于消息綜合屬性的緩存管理策略MCA-BMS:綜合考慮了消息大小、消息生存時(shí)間和消息轉(zhuǎn)發(fā)次數(shù)三種消息屬性確定消息的優(yōu)先級(jí),決定消息的轉(zhuǎn)發(fā)和丟棄順序,此外緩存管理策略中還引入了ACK確認(rèn)機(jī)制[10],刪除已經(jīng)投遞成功的冗余消息,以提高網(wǎng)絡(luò)資源利用率.通過(guò)與SHLI[11]、DLC[12]、MPBBM[6]和SAD[13]進(jìn)行仿真實(shí)驗(yàn)對(duì)比,MCA-BMS在投遞率、傳輸時(shí)延和網(wǎng)絡(luò)開(kāi)銷等網(wǎng)絡(luò)整體性能方面有較大的提升.

2 相關(guān)工作

正如前文所述,多拷貝路由算法的性能會(huì)因?yàn)楣?jié)點(diǎn)緩存空間有限但無(wú)法容納傳入的消息副本所發(fā)生的緩存溢出現(xiàn)象而下降.為了減輕緩沖區(qū)溢出的影響,需要對(duì)節(jié)點(diǎn)緩存中的消息進(jìn)行丟棄,緩存管理策略決定了在緩存溢出時(shí)需要丟棄的消息.

傳統(tǒng)的緩存管理策略[11,14],包括如DLR,FIFO等不考慮消息的屬性而僅考慮消息進(jìn)入緩存空間的先后順序和滯留時(shí)間;又如MOFO,SHLI等傳統(tǒng)緩存管理策略僅考慮轉(zhuǎn)發(fā)次數(shù)或消息生存時(shí)間單一的消息屬性,這些傳統(tǒng)緩存管理策略沒(méi)有對(duì)消息屬性進(jìn)行全面的考慮和衡量,具有一定的盲目性,因此之后的大部分研究對(duì)消息屬性進(jìn)行了劃分和綜合來(lái)對(duì)傳統(tǒng)緩存管理策略進(jìn)行改進(jìn).

現(xiàn)有的緩存管理策略可以分為根據(jù)局部信息設(shè)計(jì)和根據(jù)全局信息設(shè)計(jì).全局信息包括網(wǎng)絡(luò)中消息副本數(shù)、消息轉(zhuǎn)發(fā)次數(shù)等,文獻(xiàn)[15]針對(duì)Epidemic[16]路由算法提出了依據(jù)報(bào)文質(zhì)量的擁塞控制策略DmQ,通過(guò)估計(jì)網(wǎng)絡(luò)中消息轉(zhuǎn)發(fā)次數(shù),并綜合消息生存時(shí)間確定消息丟棄順序,以得到更好的網(wǎng)絡(luò)性能.文獻(xiàn)[6]針對(duì)Epidemic路由算法綜合消息生存時(shí)間和轉(zhuǎn)發(fā)次數(shù),將消息生存時(shí)間和消息在網(wǎng)絡(luò)中的轉(zhuǎn)發(fā)次數(shù)進(jìn)行歸一化處理,提出一種基于消息特性的緩存管理算法MPBBM,將消息生存時(shí)間取對(duì)數(shù)處理使之與消息轉(zhuǎn)發(fā)次數(shù)處于同一數(shù)量級(jí),并將兩者疊加決定消息丟棄順序,有效提高Epidemic算法的性能.然而沒(méi)有為消息生存時(shí)間和轉(zhuǎn)發(fā)次數(shù)分配相應(yīng)的權(quán)重,因而無(wú)法調(diào)整兩者的影響程度以適應(yīng)不同的環(huán)境.

由于DTN網(wǎng)絡(luò)的間斷性連接和節(jié)點(diǎn)的移動(dòng)性,很難獲得和維護(hù)整個(gè)網(wǎng)絡(luò)的全局信息,只能通過(guò)節(jié)點(diǎn)相遇交換信息來(lái)對(duì)全局信息進(jìn)行預(yù)測(cè),這種預(yù)測(cè)往往是不準(zhǔn)確的,并且節(jié)點(diǎn)需要額外空間保存全局信息,造成緩存空間的消耗,因此采用下述局部信息設(shè)計(jì)緩存管理策略更符合DTN的網(wǎng)絡(luò)特點(diǎn).

文獻(xiàn)[12]針對(duì)Binary Spray and Wait路由算法提出了基于二分散發(fā)和等待路由的自適應(yīng)擁塞控制策略DLC.主要思想是利用路由算法的特點(diǎn),用消息副本數(shù)作為轉(zhuǎn)發(fā)次數(shù)、存在時(shí)間和散發(fā)能力的綜合表現(xiàn),優(yōu)先丟棄消息副本數(shù)少的消息來(lái)達(dá)到提高投遞率和減少開(kāi)銷的目的.然而只考慮轉(zhuǎn)發(fā)次數(shù)這一種消息屬性不夠全面,沒(méi)有考慮消息生存時(shí)間等消息屬性對(duì)網(wǎng)絡(luò)性能產(chǎn)生的影響.

文獻(xiàn)[13]不同于以上緩存管理策略,考慮了消息大小因素,提出了可感知大小的丟棄策略SAD,其主要思想是根據(jù)消息大小盡可能最小化丟棄副本數(shù)量來(lái)達(dá)到最小化網(wǎng)絡(luò)開(kāi)銷的目的,以避免頻繁丟棄消息浪費(fèi)網(wǎng)絡(luò)資源.

綜上所述,消息大小、消息生存時(shí)間和消息轉(zhuǎn)發(fā)次數(shù)對(duì)于網(wǎng)絡(luò)性能有著重要的影響.然而,很少有緩存管理策略能夠綜合考慮這3種消息屬性,且大多數(shù)緩存管理策略都是針對(duì)Epidemic算法進(jìn)行改進(jìn),很少有根據(jù)Spray and Wait消息轉(zhuǎn)發(fā)特性專門針對(duì)Spray and Wait算法的緩存管理策略.因此,本文提出一種針對(duì)Spray and Wait路由算法基于消息綜合屬性的緩存管理策略MCA-BMS,通過(guò)同時(shí)考慮消息大小、消息生存時(shí)間和消息轉(zhuǎn)發(fā)次數(shù)決定消息的轉(zhuǎn)發(fā)和丟棄順序,提升網(wǎng)絡(luò)綜合性能.

3 網(wǎng)絡(luò)模型

3.1 消息大小

消息大小直接影響節(jié)點(diǎn)緩存中可以容納的消息數(shù)量.當(dāng)節(jié)點(diǎn)發(fā)生擁塞導(dǎo)致部分消息副本需要被丟棄時(shí),必須考慮到消息大小對(duì)消息丟棄數(shù)量的影響,否則有可能會(huì)出現(xiàn)丟棄多個(gè)消息節(jié)點(diǎn)之后緩存仍然難以容納新到來(lái)消息的情況,從而造成不必要的消息丟失,使得整個(gè)網(wǎng)絡(luò)中消息投遞率下降;另一方面,頻繁的消息丟棄會(huì)消耗節(jié)點(diǎn)能量,也會(huì)增大網(wǎng)絡(luò)開(kāi)銷.

因此,為了減少這種情況的發(fā)生,本文提出了消息大小閾值的概念,根據(jù)閾值對(duì)節(jié)點(diǎn)緩存中的消息進(jìn)行篩選,盡可能最小化丟棄消息數(shù)量,來(lái)達(dá)到降低網(wǎng)絡(luò)開(kāi)銷,提高投遞率的目的.

消息大小閾值Sthreshold表示接收消息需要空出的緩存空間大小,其計(jì)算方法如公式(1)所示:

Sthreshold=Msize-FBsize

(1)

其中Msize表示節(jié)點(diǎn)即將接收消息大小,是消息生成后的固定屬性,可以直接獲取;FBsize表示緩存空閑大小,可以通過(guò)節(jié)點(diǎn)緩存占用比、節(jié)點(diǎn)緩存大小計(jì)算進(jìn)行獲取.

由于同一節(jié)點(diǎn)在不同時(shí)刻接收消息的大小、節(jié)點(diǎn)緩存空閑大小不盡相同,因此消息大小閾值并不是一個(gè)定值,而是不斷變化的.

消息丟棄策略中首先篩選出消息大小大于閾值的消息進(jìn)行丟棄,以最小化消息丟棄數(shù)量,從而降低網(wǎng)絡(luò)開(kāi)銷.

3.2 消息生存時(shí)間

節(jié)點(diǎn)在創(chuàng)建消息的時(shí)候,會(huì)為每個(gè)消息分配初始生存時(shí)間,隨著仿真時(shí)間的增加,消息的剩余生存時(shí)間會(huì)逐漸減少.節(jié)點(diǎn)每隔一段時(shí)間會(huì)對(duì)緩存空間中的消息進(jìn)行檢查,刪除消息生存時(shí)間到期的消息.

消息剩余生存時(shí)間直接影響消息能否到達(dá)目的節(jié)點(diǎn).當(dāng)節(jié)點(diǎn)進(jìn)行消息丟棄時(shí),需要考慮消息剩余生存時(shí)間對(duì)消息丟棄策略造成的影響,否則那些生存時(shí)間快要到期的消息可能滯留在緩存中,而那些新創(chuàng)建的消息可能還沒(méi)來(lái)得及轉(zhuǎn)發(fā)就被丟棄.對(duì)于那些生存時(shí)間快要到期的消息,一方面這些消息的副本可能已經(jīng)被成功投遞;另一方面,這些消息大概率會(huì)在傳輸過(guò)程中因生存時(shí)間到期而被節(jié)點(diǎn)刪除,很難到達(dá)目的節(jié)點(diǎn),從而加大整個(gè)網(wǎng)絡(luò)消息傳輸時(shí)延.對(duì)于那些新創(chuàng)建的消息,由于消息副本還沒(méi)有得到充分的轉(zhuǎn)發(fā)就被丟棄,使得網(wǎng)絡(luò)中的消息副本數(shù)較少,擴(kuò)散范圍較小,成功投遞的概率較低,從而降低整個(gè)網(wǎng)絡(luò)的消息投遞率.

因此本文通過(guò)定義生存時(shí)間閾值,根據(jù)閾值對(duì)緩存中消息隊(duì)列進(jìn)行劃分,在消息生存時(shí)間小于閾值時(shí),優(yōu)先丟棄消息生存時(shí)間小的消息來(lái)減少上述情況的發(fā)生.

消息生存時(shí)間閾值如公式(2)所示:

TTLthreshold=δ*TTLinit

(2)

式中TTLthreshold表示消息生存時(shí)間閾值,TTLinit表示消息初始生存時(shí)間,δ為0～1之間的數(shù),后文中通過(guò)實(shí)驗(yàn)確定δ在當(dāng)前仿真環(huán)境下的值,從而確定生存時(shí)間閾值.

3.3 消息轉(zhuǎn)發(fā)次數(shù)

除了上述消息大小和消息生存時(shí)間,消息的轉(zhuǎn)發(fā)次數(shù)也同樣需要考慮.消息的轉(zhuǎn)發(fā)次數(shù)越多,則網(wǎng)絡(luò)中該消息的副本越多,消息已經(jīng)成功投遞的可能性越大,并且即使沒(méi)有被成功投遞,部分節(jié)點(diǎn)丟棄這種消息,其他節(jié)點(diǎn)仍有很大的轉(zhuǎn)發(fā)機(jī)會(huì),不會(huì)對(duì)整體消息投遞率造成很大影響;然而若丟棄消息轉(zhuǎn)發(fā)次數(shù)少的消息,由于消息并沒(méi)有得到充分轉(zhuǎn)發(fā)機(jī)會(huì),消息很難到達(dá)目的節(jié)點(diǎn),使得消息投遞率下降,因此消息轉(zhuǎn)發(fā)次數(shù)影響了消息的投遞率.

對(duì)于一般多拷貝算法,消息的轉(zhuǎn)發(fā)次數(shù)屬于全局信息,需要通過(guò)節(jié)點(diǎn)維護(hù)這一全局信息并通過(guò)節(jié)點(diǎn)間接觸對(duì)消息轉(zhuǎn)發(fā)次數(shù)進(jìn)行更新,而使用全局信息必定會(huì)帶來(lái)消息緩存的占用和預(yù)測(cè)的不準(zhǔn)確性.然而基于本文所改進(jìn)的路由算法Spray and Wait的特點(diǎn),可以采用消息副本對(duì)消息轉(zhuǎn)發(fā)次數(shù)進(jìn)行替代.由于Spray and Wait路由算法中節(jié)點(diǎn)維護(hù)了緩存空間中消息副本數(shù),且每次噴發(fā)只復(fù)制一個(gè)消息,因此消息副本數(shù)越少就意味著該消息的轉(zhuǎn)發(fā)次數(shù)越多.在消息生存時(shí)間充足的時(shí)候,即生存時(shí)間大于生存時(shí)間閾值的時(shí)候,優(yōu)先對(duì)轉(zhuǎn)發(fā)次數(shù)多的消息即消息副本少的消息進(jìn)行丟棄,可以給轉(zhuǎn)發(fā)次數(shù)少的消息更多轉(zhuǎn)發(fā)機(jī)會(huì),提高消息投遞率.

3.4 消息效用值

通過(guò)上述對(duì)消息3個(gè)重要屬性進(jìn)行分析,可以得到消息大小主要影響網(wǎng)絡(luò)開(kāi)銷,消息生存時(shí)間主要影響傳輸時(shí)延,消息轉(zhuǎn)發(fā)次數(shù)主要影響消息投遞率,那么如何平衡這3個(gè)消息屬性的影響程度,使得網(wǎng)絡(luò)中綜合性能最優(yōu)成為我們需要解決的問(wèn)題.

本文采用定義消息效用值的方法將消息生存時(shí)間和消息轉(zhuǎn)發(fā)次數(shù)兩種消息屬性進(jìn)行綜合,通過(guò)消息生存時(shí)間閾值來(lái)確定兩種消息屬性的影響程度.消息效用值的定義以更加直觀的方式來(lái)衡量消息轉(zhuǎn)發(fā)和丟棄的優(yōu)先級(jí),從而確定轉(zhuǎn)發(fā)和丟棄的順序.具體定義如公式(3)所示:

(3)

式中TTLthreshold表示消息生存時(shí)間閾值,Copiesk表示節(jié)點(diǎn)攜帶消息mk的消息副本數(shù),TTLk表示該節(jié)點(diǎn)中消息的剩余生存時(shí)間.

由于本文采用的路由算法為Spray and Wait算法,因此節(jié)點(diǎn)中消息初始副本數(shù)可以預(yù)先設(shè)置,并且可以為每個(gè)消息增加消息副本字段來(lái)記錄消息副本數(shù).

在消息剩余生存時(shí)間小于生存時(shí)間閾值時(shí),則消息剩余生存時(shí)間成為丟棄消息所需要考慮的主要因素,通過(guò)優(yōu)先丟棄消息剩余生存時(shí)間小的消息,以降低網(wǎng)絡(luò)傳輸時(shí)延.

當(dāng)消息剩余生存時(shí)間大于消息生存時(shí)間閾值時(shí),可以認(rèn)為消息有足夠的時(shí)間到達(dá)目的節(jié)點(diǎn),消息剩余生存時(shí)間不再是比較丟棄順序的主要因素,因此將轉(zhuǎn)發(fā)次數(shù)即消息副本數(shù)作為選擇丟棄消息的依據(jù),通過(guò)優(yōu)先丟棄消息副本數(shù)少的消息,讓消息轉(zhuǎn)發(fā)次數(shù)少的消息有更多的轉(zhuǎn)發(fā)機(jī)會(huì),以提高網(wǎng)絡(luò)消息投遞率.

4 基于消息綜合屬性的緩存管理策略MCA-BMS

本文提出的基于Spray and Wait的綜合緩存管理策略MCA-BMS綜合了節(jié)點(diǎn)攜帶消息大小、生存時(shí)間和副本數(shù),對(duì)Spray and Wait算法的消息的轉(zhuǎn)發(fā)和丟棄策略進(jìn)行改進(jìn),本節(jié)從ACK確認(rèn)機(jī)制、消息轉(zhuǎn)發(fā)和丟棄順序、消息轉(zhuǎn)發(fā)策略以及消息丟棄策略4個(gè)方面進(jìn)行介紹.

4.1 ACK確認(rèn)機(jī)制

DTN的ACK確認(rèn)機(jī)制不同于傳統(tǒng)Internet的TCP確認(rèn)機(jī)制,其目的并不是為了提供可靠傳輸,而只是為了根據(jù)確認(rèn)信息丟棄已經(jīng)投遞的冗余消息,緩解網(wǎng)絡(luò)壓力,達(dá)到降低網(wǎng)絡(luò)負(fù)載,提高投遞率的目的.

本文引入的ACK確認(rèn)機(jī)制[17]原理實(shí)現(xiàn)如下:

1)每個(gè)節(jié)點(diǎn)維護(hù)一個(gè)ACK消息列表,用于記錄節(jié)點(diǎn)中已經(jīng)投遞成功的消息id.

2)當(dāng)節(jié)點(diǎn)中有消息成功投遞到目的節(jié)點(diǎn)時(shí),記錄消息ID添加到ACK列表中,并將該消息從緩存中刪除.

3)當(dāng)兩個(gè)節(jié)點(diǎn)如vi和vj相遇時(shí),首先會(huì)交換彼此的ACK列表,將對(duì)方的表中的消息id添加到自己的ACK列表中.接著,節(jié)點(diǎn)vi和節(jié)點(diǎn)vj分別檢索自身ACK列表,判斷緩存中是否含有ACK列表中id所對(duì)應(yīng)的消息:如果存在這樣的消息且該消息不是正在傳輸則將其從緩存空間中刪除.

本文引入ACK確認(rèn)機(jī)制,對(duì)冗余消息進(jìn)行刪除,一方面使得節(jié)點(diǎn)緩存能容納更多消息,減少了因緩存空間不足而造成頻繁丟棄現(xiàn)象的發(fā)生,提升網(wǎng)絡(luò)的整體性能;另一方面,可以減少冗余消息對(duì)緩存管理策略中消息選擇所造成的影響,盡量避免非冗余消息丟棄而冗余消息仍滯留在緩存情況的發(fā)生.

4.2 消息優(yōu)先級(jí)隊(duì)列

根據(jù)前文定義的消息效用值對(duì)緩存中消息進(jìn)行排序,得到如圖1所示的消息優(yōu)先級(jí)隊(duì)列.

圖1 消息優(yōu)先級(jí)隊(duì)列Fig.1 Message priority queue

當(dāng)消息效用值相同,則很難進(jìn)行緩存隊(duì)列的管理,因此使用了類似{SAD;FIFO}的隊(duì)列組策略:消息效用值相同時(shí)先比較消息大小,若仍相同則比較消息進(jìn)入緩沖區(qū)的時(shí)間.其中消息大小較小的消息具有更高的效用值,這是為了在丟棄消息時(shí)丟棄消息大小大的消息以騰出更多的緩存空間容納更多消息,在接收消息時(shí)接收消息大小較小的消息以接收更多的消息.

4.3 消息轉(zhuǎn)發(fā)策略和丟棄策略

消息轉(zhuǎn)發(fā)策略:節(jié)點(diǎn)在遇到其他節(jié)點(diǎn)需要進(jìn)行消息轉(zhuǎn)發(fā)時(shí),每次選擇緩存中消息優(yōu)先級(jí)隊(duì)列隊(duì)首的消息對(duì)消息進(jìn)行轉(zhuǎn)發(fā).

消息丟棄策略:當(dāng)兩節(jié)點(diǎn)相遇時(shí),首先進(jìn)行ACK確認(rèn)機(jī)制,刪除兩節(jié)點(diǎn)中已經(jīng)成功投遞的消息;當(dāng)接收節(jié)點(diǎn)空閑緩存不足以容納鄰居節(jié)點(diǎn)即將傳輸過(guò)來(lái)的消息時(shí),根據(jù)消息大小篩選出消息大小大于或等于消息大小閾值Sthreshold的消息,優(yōu)先丟棄效用值低的消息;若消息大小均小于Sthreshold則優(yōu)先丟棄緩存中消息優(yōu)先級(jí)隊(duì)列隊(duì)尾的消息并重新計(jì)算Sthreshold.

具體消息丟棄策略圖2所示.

圖2 消息丟棄策略Fig.2 Message discarding strategy

具體消息丟棄算法如算法1所示.

算法1.消息丟棄算法

輸入:即將到來(lái)消息Mnew;

輸出:丟棄成功返回TRUE,失敗返回FALSE;

1. IFMnew.size > BufferSize

2. RETURN FALSE

3. END IF

教學(xué)設(shè)計(jì)：教師依據(jù)學(xué)情分析結(jié)果，綜合課程教學(xué)目標(biāo)、課程教學(xué)內(nèi)容、課程知識(shí)重難點(diǎn)等，并參考學(xué)生預(yù)習(xí)檢測(cè)統(tǒng)計(jì)分析和討論的情況，完善教學(xué)設(shè)計(jì)方案、準(zhǔn)備多媒體教學(xué)資料。[3]

4. WHILEFreeBufferSize

5.Sthr←Mnew-FreeBufferSize

6.FOR eachMkinMBuffer

7.IFMk.size ≥Sthr

8. pushMkinto temporary queueQ

9. END IF

10. END FOR

12. delete least utility messageMoldinQ

13.FreeBufferSize+=Mold.size

14. ELSE

15. delete tail of queue in BufferMtail

16.FreeBufferSize+=Mtail.size

17. END IF

18. END WHILE

19. RETURN TRUE

算法1行-3行表示整個(gè)緩存空間不足以容納即將到來(lái)的消息,這時(shí)就不會(huì)接收該消息;4行-10行表示把緩存隊(duì)列中消息大于消息閾值Sthr的消息放入臨時(shí)隊(duì)列Q中;11行-13行表示若隊(duì)列Q不為空即緩存中有消息大于消息閾值Sthr的消息,則篩選出隊(duì)列Q中效用值最小的消息Mold進(jìn)行刪除;14行-16行表示若緩存中沒(méi)有消息大于消息閾值Sthr的消息,則刪除緩存隊(duì)列中效用值最小的消息Mtail,即對(duì)隊(duì)尾的消息進(jìn)行刪除.

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

5.1 仿真環(huán)境配置

本實(shí)驗(yàn)采用ONE仿真平臺(tái)[18]在Spray and Wait路由算法的基礎(chǔ)上對(duì)DLC,MPBBM,SHLI,SAD和本文提出的MCA-BMS算法進(jìn)行仿真.仿真采用ONE平臺(tái)自帶的赫爾辛基市地圖作為移動(dòng)場(chǎng)景,大小為4500m×3400m,節(jié)點(diǎn)數(shù)量設(shè)置為126個(gè),共分為3類節(jié)點(diǎn):行人、出租車、有軌電車.其中行人組80個(gè)節(jié)點(diǎn),出租車組40個(gè)節(jié)點(diǎn),這兩組按照基于地圖路線的最短路徑模型移動(dòng),有軌電車組共6個(gè)節(jié)點(diǎn),按照基于地圖的固定路線模型移動(dòng).具體的仿真參數(shù)設(shè)置如表1所示,其它參數(shù)采用ONE平臺(tái)自帶的默認(rèn)配置文件default_settings.txt中的默認(rèn)設(shè)置.

表1 仿真參數(shù)Table 1 Simulation parameters

5.2 評(píng)價(jià)指標(biāo)

本文采用以下指標(biāo)來(lái)評(píng)估相關(guān)算法的性能[19].

1)投遞率(Delivery Ratio)

投遞率=成功投遞到目標(biāo)節(jié)點(diǎn)的消息數(shù)量/網(wǎng)絡(luò)中生成的所有消息數(shù)量.

2)平均時(shí)延(Average Latency)

平均時(shí)延=網(wǎng)絡(luò)中所有被成功投遞的消息從源節(jié)點(diǎn)產(chǎn)生開(kāi)始到目標(biāo)節(jié)點(diǎn)完整接收到所經(jīng)過(guò)的平均時(shí)間.

3)網(wǎng)絡(luò)負(fù)載率(Overhead ratio)

網(wǎng)絡(luò)負(fù)載率:需要投遞的消息的發(fā)送總次數(shù)/成功投遞到目標(biāo)節(jié)點(diǎn)的消息數(shù)量.

5.3 生存時(shí)間閾值設(shè)置實(shí)驗(yàn)

由于生存時(shí)間閾值直接影響何時(shí)比較副本數(shù),何時(shí)比較消息生存時(shí)間,即效用值的確定,進(jìn)而影響消息投遞率和傳輸時(shí)延,因此確定固定仿真條件下生存時(shí)間閾值顯得尤為重要.消息生存時(shí)間閾值由消息初始生存時(shí)間的比例確定,即為確定比例系數(shù)δ,使得算法在投遞率和傳輸時(shí)延方面均能表現(xiàn)較好.

首先在[0,1]區(qū)間,以0.05為間距確定參數(shù)δ的大致范圍,投遞率和平均時(shí)延分別如圖3所示.

從圖3(a)和圖3(b)可以看出δ在0.2和0.35時(shí)MCA-BMS投遞率相對(duì)較高,相差不是很明顯,但在傳輸時(shí)延方面δ為0.35比δ為0.2時(shí)下降了很多,因此將參數(shù)δ的取值范圍確定在0.35附近.為了進(jìn)一步精確確定參數(shù)δ的值,在[0.29-0.36]之間以0.01為間距,得到MCA-BMS的投遞率和平均時(shí)延,如圖4所示.

圖3 δ不同取值條件下的性能比較Fig.3 Comparison of performance under different values of δ

綜合圖4(a)和圖4(b)可以很明顯看出當(dāng)參數(shù)δ取0.35時(shí)MCA-BMS在投遞率和傳輸時(shí)延綜合方面表現(xiàn)最優(yōu).

5.4 算法比較及分析

為了驗(yàn)證MCA-BMS算法的高效性,進(jìn)行了3組仿真實(shí)驗(yàn),在不同的消息生存時(shí)間、不同的仿真時(shí)間以及不同的消息產(chǎn)生速率下對(duì)5種算法在消息投遞率、網(wǎng)絡(luò)負(fù)載率和平均傳輸時(shí)延等網(wǎng)絡(luò)性能方面進(jìn)行評(píng)估,并且除了傳統(tǒng)算法SHLI均加入了ACK確認(rèn)機(jī)制以達(dá)到控制變量的目的.實(shí)驗(yàn)結(jié)果表明,MCA-BMS對(duì)網(wǎng)絡(luò)的性能提升最大.

圖4 δ不同取值條件下的性能比較Fig.4 Comparison of performance under different values of δ

1)不同消息生存周期

在前面環(huán)境配置下,改變消息生存周期,對(duì)比各種算法在不同消息生存周期下消息投遞率(如圖5(a)所示)、網(wǎng)絡(luò)負(fù)載率(如圖5(b)所示)、平均時(shí)延(如圖5(c)所示)3個(gè)方面的變化情況.

圖5(a)顯示了各個(gè)算法在不同的消息生存時(shí)間變化下消息投遞率的變化情況.由于隨著消息生存時(shí)間的增加,許多消息不會(huì)因?yàn)橄⑹Ｓ嗌鏁r(shí)間短被丟棄而能夠成功投遞,因此各個(gè)算法的投遞率基本呈現(xiàn)上升趨勢(shì).其中本文提出的算法MCA-BMS投遞率最高:MCA-BMS的消息投遞率相較MPBBM平均提高了3.46%,相較DLC平均提高了6.24%,相較SHLI平均提高了17.72%,相較SAD提升了33.59%.

圖5 不同消息生存周期條件下的性能比較Fig.5 Comparison of performance under different message time to live

MCA-BMS的消息投遞率高于MPBBM的可能原因有兩個(gè):一是MPBBM算法未考慮消息的大小,因此可能多次出現(xiàn)接收一個(gè)消息而刪除多個(gè)消息的情況;二是MPBBM算法僅僅將消息生存時(shí)間和消息副本數(shù)保持在一個(gè)數(shù)量級(jí),而未考慮兩者的占比情況,一般說(shuō)來(lái)消息副本數(shù)占比越多則消息投遞率越高.

SAD的消息投遞率最低的原因是該算法只考慮消息的大小,保證每次丟棄消息的個(gè)數(shù)最小,并沒(méi)有對(duì)消息生存時(shí)間和消息副本數(shù)進(jìn)行考慮,因此可能丟棄消息副本數(shù)大即還未得到轉(zhuǎn)發(fā)的消息,導(dǎo)致投遞率很低.

圖5(b)比較了各個(gè)路由算法的網(wǎng)絡(luò)負(fù)載率.其中SAD算法的網(wǎng)絡(luò)負(fù)載率最低,這是由于該算法為了使每次丟棄的消息個(gè)數(shù)最少,因此優(yōu)先將消息大小大的消息進(jìn)行丟棄,而這樣會(huì)為緩沖區(qū)騰出大量的空間,使得整個(gè)網(wǎng)絡(luò)的負(fù)載率較低.

DLC算法的負(fù)載率最高的原因是該算法丟棄副本數(shù)最低的消息,即轉(zhuǎn)發(fā)次數(shù)最多的消息,使得總的消息轉(zhuǎn)發(fā)次數(shù)大大增加,網(wǎng)絡(luò)負(fù)載率最高.

圖5(c)評(píng)估了各個(gè)算法的平均時(shí)延的變化情況.從圖中可以看出SHLI的平均時(shí)延最低,MCA-BMS次之,這是由于SHLI算法只考慮丟棄生存時(shí)間最短的消息,使得成功投遞的消息生存時(shí)間偏高,計(jì)算出的平均時(shí)延較低,然而由于可能丟棄一些消息生存時(shí)間低但能成功投遞的消息,導(dǎo)致該算法的投遞率偏低;本文中算法MCA-BMS能夠在保持高投遞率的情況下,平均時(shí)延方面性能僅次于SHLI.

DLC的平均時(shí)延是最高的,這是因?yàn)樵撍惴ㄊ沟棉D(zhuǎn)發(fā)次數(shù)少的消息得到更多的轉(zhuǎn)發(fā)機(jī)會(huì),這就會(huì)導(dǎo)致轉(zhuǎn)發(fā)次數(shù)少且需要長(zhǎng)時(shí)間到達(dá)目的節(jié)點(diǎn)的消息得到轉(zhuǎn)發(fā),造成整體的平均時(shí)延較高.

綜上所述,MCA-BMS在消息投遞率方面優(yōu)于其他4種算法,在網(wǎng)絡(luò)負(fù)載率和平均時(shí)延方面均是次優(yōu),因此可以得出在不同的消息生存周期MCA-BMS的整體性能是最好的.

2)不同仿真時(shí)間

在不同的仿真時(shí)間條件下,比較和分析各個(gè)算法在消息投遞率(如圖6(a)所示)、網(wǎng)絡(luò)負(fù)載率(如圖6(b)所示)、平均時(shí)延(如圖6(c)所示)3個(gè)方面的變化情況.

圖6(a)顯示了各個(gè)算法在不同的仿真時(shí)間下消息投遞率的變化情況.隨著仿真時(shí)間的增加,有更多的消息被成功投遞,因此各個(gè)算法的投遞率基本呈現(xiàn)上升趨勢(shì).其中本文提出的算法MCA-BMS投遞率最高:MCA-BMS在不同仿真時(shí)間下的投遞率相較MPBBM平均提高了7.03%,相較DLC平均提高了7.82%,相較SHLI平均提高了22.32%,相較SAD提升了37.33%.

圖6 不同仿真時(shí)間條件下的性能比較Fig.6 Comparison of performance under different simulation time

圖6(b)比較了各個(gè)算法的網(wǎng)絡(luò)負(fù)載率.結(jié)果依然是SAD算法網(wǎng)絡(luò)負(fù)載率最低,MCA-BMS算法次優(yōu).MCA-BMS算法的網(wǎng)絡(luò)負(fù)載率隨仿真時(shí)間的增加先增加后趨于穩(wěn)定,是因?yàn)橄乳_(kāi)始消息的生存時(shí)間基本大于消息生存時(shí)間閾值,因此大都按照消息副本對(duì)消息進(jìn)行丟棄,使得消息得到大量轉(zhuǎn)發(fā),網(wǎng)絡(luò)負(fù)載率升高;隨著時(shí)間的推移,消息生存時(shí)間占主要因素,因此網(wǎng)絡(luò)負(fù)載率趨向于SHLI算法.

圖6(c)評(píng)估了在不同仿真時(shí)間下網(wǎng)絡(luò)的平均時(shí)延的變化.從圖中可以看出隨著仿真時(shí)間的增加,MCA-BMS算法的平均時(shí)延逐漸增加并趨于平緩,仍然是高于SHLI算法,比其他3種算法低,處于次優(yōu).

綜上所述,隨著仿真時(shí)間的增加,由于MCA-BMS綜合考慮了消息大小、消息生存時(shí)間和消息副本數(shù),與其他算法的優(yōu)勢(shì)逐漸明顯,從總體上來(lái)看,MCA-BMS在各個(gè)方面都有顯著優(yōu)勢(shì).

3)不同消息生成間隔

消息生成間隔與消息產(chǎn)生速率呈反比,通過(guò)改變消息生成間隔,即改變消息產(chǎn)生速率,比較和分析各個(gè)算法在消息投遞率(如圖7(a)所示)、平均時(shí)延(如圖7(b)所示)、網(wǎng)絡(luò)負(fù)載率(如圖7(c)所示)3個(gè)方面的變化情況.

圖7 不同消息生成間隔條件下的性能比較Fig.7 Comparison of performance under different message generation interval

圖7(a)顯示了各個(gè)算法的消息投遞率的變化.5種算法的投遞率都呈現(xiàn)上升的趨勢(shì),這是因?yàn)殡S著消息生成間隔的增加,消息產(chǎn)生速率逐漸變小,網(wǎng)絡(luò)中的消息逐漸變少,資源利用率變高,減少大量消息因?yàn)榫彺娌蛔愣l繁丟棄的情況,因此投遞率均呈現(xiàn)上升的趨勢(shì),這時(shí)對(duì)于消息的轉(zhuǎn)發(fā)和丟棄策略直接影響著消息是否能成功轉(zhuǎn)發(fā)到目的節(jié)點(diǎn).對(duì)比圖中的數(shù)據(jù)可以得出,MCA-BMS的消息投遞率相較MPBBM平均提高了6.93%,相較DLC平均提高了8.52%,相較SHLI平均提高了26.00%,相較SAD提升了53.45%.

圖7(b)比較了各個(gè)算法的網(wǎng)絡(luò)負(fù)載率隨消息產(chǎn)生速率的變化情況.與之前不同的是當(dāng)消息生成間隔低的時(shí)候,MCA-BMS算法的網(wǎng)絡(luò)負(fù)載率會(huì)高于SHLI算法,這是因?yàn)橄⑸砷g隔低,就會(huì)有大量新消息的產(chǎn)生,由于新產(chǎn)生的消息的生存時(shí)間基本大于消息生存時(shí)間閾值,所以基本按照消息副本數(shù)對(duì)消息進(jìn)行丟棄,許多消息被轉(zhuǎn)發(fā),網(wǎng)絡(luò)負(fù)載率提高,而隨著消息生成間隔增加,新消息的生成速率降低,網(wǎng)絡(luò)負(fù)載率逐漸降低,由于同時(shí)考慮了消息大小和消息生存時(shí)間,因此比單一考慮消息生存時(shí)間的SHLI網(wǎng)絡(luò)負(fù)載率低.

圖7(c)評(píng)估了各個(gè)算法在不同的消息產(chǎn)生速率下平均時(shí)延的變化情況.隨著消息產(chǎn)生速率逐漸降低,MCA-BMS的平均時(shí)延方面的性能仍僅次于SHLI算法,DLC算法的平均時(shí)延依然為最高.

綜上所述,在不同的消息產(chǎn)生速率條件下,綜合考慮投遞率、負(fù)載率以及平均時(shí)延方面,MCA-BMS對(duì)網(wǎng)絡(luò)的性能提升最大.

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

本文針對(duì)Spray and Wait路由算法提出了基于消息綜合屬性:消息生存時(shí)間、消息大小和消息副本數(shù)的緩存管理策略MCA-BMS.該算法首先通過(guò)消息大小盡可能減少消息丟棄的數(shù)量,減少因丟棄消息大小不足造成頻繁丟棄的情況,降低網(wǎng)絡(luò)負(fù)載率,再按照消息生存時(shí)間和消息副本數(shù)對(duì)消息優(yōu)先級(jí)進(jìn)行排序,實(shí)現(xiàn)消息投遞率和平均傳輸時(shí)延的平衡,最后通過(guò)加入ACK確認(rèn)機(jī)制,刪除網(wǎng)絡(luò)中的大量冗余消息副本,緩解網(wǎng)絡(luò)擁塞情況,進(jìn)一步提升網(wǎng)絡(luò)整體性能.

仿真結(jié)果顯示,對(duì)比其他四種算法,MCA-BMS在投遞率上始終是最高的,在網(wǎng)絡(luò)負(fù)載率和消息傳輸時(shí)延方面是次優(yōu)的,因此從整體上來(lái)看MCA-BMS要優(yōu)于其他4種緩存管理策略,但是由于消息生存時(shí)間閾值是根據(jù)本文仿真環(huán)境實(shí)驗(yàn)進(jìn)行確定,經(jīng)過(guò)組內(nèi)研究討論,下一步將研究如何動(dòng)態(tài)確定消息生存時(shí)間閾值,從而使得MCA-BMS能夠適應(yīng)不同緩存等其他仿真環(huán)境.