DTN中適用于節(jié)點(diǎn)環(huán)境狀態(tài)的擁塞控制管理策略

崔建群,陳紫怡,常亞楠,陳歡歡,龔 雙

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

0 引 言

在容遲網(wǎng)絡(luò)(Delay Tolerant Networks,DTN)[1]中,節(jié)點(diǎn)之間只能通過(guò)節(jié)點(diǎn)的移動(dòng)性進(jìn)行間歇連接通信,所以在DTN中,節(jié)點(diǎn)以“存儲(chǔ)-攜帶-轉(zhuǎn)發(fā)”[2]作為路由機(jī)制.該路由機(jī)制使得消息長(zhǎng)期存在于節(jié)點(diǎn)的緩存空間中,但由于節(jié)點(diǎn)緩存空間通常很小,擁塞情況頻繁出現(xiàn),大量數(shù)據(jù)包丟失,路由性能也隨之大大降低,因此研究緩存管理一直是DTN研究的一個(gè)重點(diǎn).但針對(duì)緩存管理的系統(tǒng)化研究并不多,大部分只是一些零散的緩存管理方案.

目前,緩存管理的設(shè)計(jì)大部分圍繞消息的自身屬性.很多學(xué)者考慮消息大小,消息跳數(shù)和消息在節(jié)點(diǎn)中留存時(shí)間等一個(gè)或多個(gè)屬性提出相應(yīng)的緩存管理策略[7-12].根據(jù)消息自身屬性的特征,判斷消息在網(wǎng)絡(luò)中擴(kuò)散程度,衡量消息的重要性.當(dāng)必要?jiǎng)h除消息情況出現(xiàn)時(shí),優(yōu)先刪除對(duì)整體性能影響較小的消息,保證重要消息的投遞機(jī)會(huì),使重要消息盡可能傳遞到其目的節(jié)點(diǎn).實(shí)驗(yàn)結(jié)果表示,在路由策略中引入緩存管理策略,消息投遞率,網(wǎng)絡(luò)負(fù)載和平均時(shí)延性能都有一定的提升.這表明利用緩存管理,受限的網(wǎng)絡(luò)資源可以得到高效利用,消息傳遞到目的節(jié)點(diǎn)的概率越大.然而這些緩存管理策略,考慮的影響因素通常不夠全面,且沒有考慮在不同節(jié)點(diǎn)中,各個(gè)消息屬性的影響有異,即不同節(jié)點(diǎn)中,評(píng)估消息的側(cè)重指標(biāo)不同.同時(shí),有些丟棄消息策略[13]局限于考慮消息自身屬性,雖基于消息和整體網(wǎng)絡(luò)環(huán)境的關(guān)系,盡可能保留稀有消息,避免稀有消息丟棄,保證網(wǎng)絡(luò)性能,但并未考慮消息與目的節(jié)點(diǎn)的相遇可能,由于不同節(jié)點(diǎn)攜帶消息投遞的能力具有差異性,在高能力節(jié)點(diǎn)中盡可能留存消息具有必要性,避免丟棄消息選擇的片面性.

基于以上分析,本文將在不同節(jié)點(diǎn)中消息屬性的影響差異、節(jié)點(diǎn)攜帶消息成功投遞的能力綜合考慮,預(yù)測(cè)節(jié)點(diǎn)狀態(tài)到達(dá)擁塞的速度,提出了一種適用于節(jié)點(diǎn)環(huán)境狀態(tài)的擁塞控制管理策略NEMS.主要的貢獻(xiàn)總結(jié)如下:

1)本文將節(jié)點(diǎn)劃分為空閑、忙碌和崩潰3種狀態(tài).通過(guò)定義門限度的概念將剩余緩存空間和消息成功投遞率結(jié)合起來(lái),限制忙碌節(jié)點(diǎn)留存消息,減緩忙碌節(jié)點(diǎn)轉(zhuǎn)變?yōu)楸罎⒐?jié)點(diǎn)的速度;

2)本文定義節(jié)點(diǎn)間連接活躍值的概念.考慮節(jié)點(diǎn)間相遇時(shí)刻,移動(dòng)方向和距離的不同,計(jì)算節(jié)點(diǎn)和目的節(jié)點(diǎn)間的連接活躍值,將緩存空間優(yōu)先分配給和其目的節(jié)點(diǎn)連接活躍值更大的消息,高效利用網(wǎng)絡(luò)資源,使消息能夠更快到達(dá)目的地;

3)本文定義丟棄優(yōu)先級(jí)的概念.首先利用熵權(quán)法動(dòng)態(tài)計(jì)算在不同節(jié)點(diǎn)中消息屬性對(duì)于消息重要性計(jì)算的影響權(quán)重,考慮消息生命周期,消息停留時(shí)間,消息跳數(shù)和大小計(jì)算消息的丟棄優(yōu)先級(jí).優(yōu)先刪除丟棄優(yōu)先級(jí)大的消息,確保節(jié)點(diǎn)的稀缺資源被更重要的消息利用,從而提高消息的成功投遞率;

4)當(dāng)節(jié)點(diǎn)處于忙碌狀態(tài)時(shí),本文提出節(jié)點(diǎn)間位置差異相關(guān)的控制保留策略選擇性留存消息,減慢轉(zhuǎn)化為崩潰節(jié)點(diǎn)的速度,盡可能留有更多稀缺資源供給給依據(jù)該節(jié)點(diǎn)能獲取更大成功投遞機(jī)會(huì)的消息;

5)當(dāng)節(jié)點(diǎn)處于崩潰狀態(tài)時(shí),本文提出節(jié)點(diǎn)自差異相關(guān)的丟包策略來(lái)優(yōu)先刪除丟棄優(yōu)先級(jí)高的消息,保證重要消息不被丟棄,降低擁塞情況帶來(lái)的性能損耗.

1 相關(guān)工作

由于節(jié)點(diǎn)間緩存狀態(tài)不同,預(yù)防節(jié)點(diǎn)到達(dá)擁塞狀態(tài)能有效控制擁塞發(fā)生造成的性能損失.陳夢(mèng)婷等人[3]提出QPCC-CS擁塞控制機(jī)制,該機(jī)制基于節(jié)點(diǎn)存儲(chǔ)率的不同將節(jié)點(diǎn)分為不同狀態(tài),針對(duì)不同狀態(tài)采取不同的擁塞控制處理,靈活處理不同狀態(tài)的節(jié)點(diǎn),延緩衛(wèi)星網(wǎng)絡(luò)擁塞.當(dāng)發(fā)生擁塞時(shí),利用消息生存時(shí)間和被節(jié)點(diǎn)接受的時(shí)刻重新對(duì)緩存隊(duì)列排序,利用隊(duì)列盡可能保留高質(zhì)量消息.在文獻(xiàn)[4]中提出時(shí)刻監(jiān)控節(jié)點(diǎn)緩存變化情況的思路,在節(jié)點(diǎn)即將發(fā)生擁塞前,采取預(yù)防到達(dá)擁塞的措施,可以有效控制擁塞情況的發(fā)生.由實(shí)驗(yàn)結(jié)果得知,在節(jié)點(diǎn)將要達(dá)到擁塞情況時(shí),限制節(jié)點(diǎn)接受消息的能力,能夠延緩節(jié)點(diǎn)到達(dá)擁塞狀態(tài)的速度,進(jìn)而避免擁塞的發(fā)生.

因?yàn)楣?jié)點(diǎn)是按照一定路線規(guī)律性移動(dòng),在文獻(xiàn)[5]中提出與位置相關(guān)的路由策略.利用節(jié)點(diǎn)移動(dòng)的方向針對(duì)性選擇傳遞概率更大的節(jié)點(diǎn)協(xié)助投遞,使消息可以更快轉(zhuǎn)發(fā)給其目的節(jié)點(diǎn).文獻(xiàn)[6]中也提出基于方向選擇的MDCE路由算法.這種指向性選擇中繼的思路使消息更有針對(duì)性向目的節(jié)點(diǎn)移動(dòng).

當(dāng)節(jié)點(diǎn)發(fā)生溢出時(shí),丟棄策略的設(shè)計(jì)能直接關(guān)系到網(wǎng)絡(luò)性能的提升.有些研究學(xué)者針對(duì)消息自身屬性出發(fā),設(shè)計(jì)緩存丟棄策略.在近兩年的文獻(xiàn)[7]中提到了一種緩存管理機(jī)制OANBM-MS.當(dāng)節(jié)點(diǎn)發(fā)生擁塞時(shí),優(yōu)先丟棄刪除在網(wǎng)絡(luò)中分布更多和在緩存中停留時(shí)間更長(zhǎng)的消息.實(shí)驗(yàn)結(jié)果表明,添加OANBM-MS機(jī)制后,能有效提升網(wǎng)絡(luò)性能.王慧強(qiáng)等人在文獻(xiàn)[8]中提出MPBBM算法,該算法認(rèn)為轉(zhuǎn)發(fā)次數(shù)少且在網(wǎng)絡(luò)中生存時(shí)間短的消息為活躍消息,優(yōu)先留存這類活躍消息.但在MPBBM中,并沒有給消息轉(zhuǎn)發(fā)次數(shù)和生存周期動(dòng)態(tài)設(shè)置權(quán)重系數(shù),無(wú)法適應(yīng)性調(diào)整這兩個(gè)因素對(duì)消息重要程度計(jì)算的影響比重.在文獻(xiàn)[9]中提出RABP,RABP估計(jì)消息到目的節(jié)點(diǎn)的消息延遲和跳數(shù),構(gòu)造延遲和跳數(shù)的權(quán)重函數(shù).利用權(quán)重函數(shù)幫助中繼選擇以及進(jìn)行緩存管理.有些學(xué)者為了減少丟棄數(shù)據(jù)包的數(shù)量,選擇考慮消息的大小作為丟棄數(shù)據(jù)包的依據(jù).在文獻(xiàn)[10]中SS-Drop先確定需要的緩沖區(qū)空間,選擇要丟棄的適當(dāng)大小的消息.在文獻(xiàn)[11]中也是選擇最佳消息大小進(jìn)行丟棄.文獻(xiàn)[12]提出SAD比較接收消息與剩余緩存空間的大小.當(dāng)不足以接收新消息時(shí),根據(jù)大小丟棄消息,通過(guò)丟棄極少的消息數(shù)量接受新的消息.SAD提出通過(guò)消息的大小來(lái)選擇性丟棄消息,但并未結(jié)合其他屬性綜合評(píng)估消息的重要程度,如消息經(jīng)歷的跳數(shù),消息的生命周期等.同時(shí),將消息自身屬性和節(jié)點(diǎn)轉(zhuǎn)發(fā)消息能力結(jié)合起來(lái),將更全面考慮消息在不同節(jié)點(diǎn)中的重要程度.崔建群等人在文獻(xiàn)[13]中提出基于消息質(zhì)量和節(jié)點(diǎn)可信度的擁塞控制策略CCMQ,CCMQ利用消息在網(wǎng)絡(luò)中的擴(kuò)散程度定義消息的重要程度,結(jié)合不同節(jié)點(diǎn)轉(zhuǎn)發(fā)能力的不同,動(dòng)態(tài)性分配緩存.由實(shí)驗(yàn)結(jié)果可知,綜合節(jié)點(diǎn)屬性和消息屬性能夠更全面分析消息丟失帶來(lái)的損失情況,加以控制,能在一定程度上改善網(wǎng)絡(luò)性能.在文獻(xiàn)[14]中提出一種緩沖區(qū)管理方案,該方案考慮消息的傳輸概率等信息.文獻(xiàn)[15]中使用全局網(wǎng)絡(luò)信息設(shè)定一個(gè)效用函數(shù),計(jì)算每個(gè)消息的效用,根據(jù)效用刪除低效用數(shù)據(jù)包.

節(jié)點(diǎn)溢出時(shí),節(jié)點(diǎn)接收的新消息不一定比丟棄的消息在網(wǎng)絡(luò)中的存在價(jià)值更高.在文獻(xiàn)[16]中將節(jié)點(diǎn)空間劃分為3個(gè)隊(duì)列.當(dāng)節(jié)點(diǎn)發(fā)生擁塞情況時(shí),不會(huì)一味的從大到小刪除權(quán)重更大的消息,而是會(huì)對(duì)緩存空間中一部分消息進(jìn)行保護(hù).劃分隊(duì)列控制刪除操作,確保緩存空間中存在價(jià)值較高的消息不被低價(jià)值的消息替換,保證消息高投遞率.

在容遲網(wǎng)絡(luò)中,成功投遞的消息還是會(huì)占用網(wǎng)絡(luò)資源.在文獻(xiàn)[17]中提出ACK應(yīng)答機(jī)制,清除網(wǎng)絡(luò)中已成功投遞的消息,避免冗余消息占用節(jié)點(diǎn)資源,將節(jié)點(diǎn)資源高效利用起來(lái).

基于以上分析,本文將在不同節(jié)點(diǎn)中消息屬性的影響各有不同、節(jié)點(diǎn)攜帶消息成功投遞的能力綜合考慮,預(yù)測(cè)節(jié)點(diǎn)到達(dá)擁塞的速度,提出了一種適用于節(jié)點(diǎn)環(huán)境狀態(tài)的擁塞控制管理策略NEMS.該策略首先根據(jù)節(jié)點(diǎn)剩余緩存空間判斷節(jié)點(diǎn)處于什么狀態(tài).當(dāng)節(jié)點(diǎn)處于忙碌狀態(tài)時(shí),定義門限度和連接活躍值的概念,采用節(jié)點(diǎn)間位置差異相關(guān)的控制保留策略選擇性留存消息.當(dāng)節(jié)點(diǎn)處于崩潰狀態(tài)時(shí),采用節(jié)點(diǎn)自差異相關(guān)的丟包策略.首先根據(jù)熵權(quán)法動(dòng)態(tài)計(jì)算消息各個(gè)屬性的影響權(quán)重,然后結(jié)合消息屬性,如消息的剩余生命周期等計(jì)算消息的丟棄優(yōu)先級(jí),優(yōu)先選擇丟棄優(yōu)先級(jí)高的消息進(jìn)行刪除.同時(shí)結(jié)合ACK機(jī)制,消除占用網(wǎng)絡(luò)資源的不必要消息.

2 問題模型

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

假設(shè)整個(gè)網(wǎng)絡(luò)表示為G=(V,E),V={vi|1≤i≤n}是網(wǎng)絡(luò)中的節(jié)點(diǎn)集合,其中n為網(wǎng)絡(luò)中節(jié)點(diǎn)的個(gè)數(shù).E是節(jié)點(diǎn)間對(duì)應(yīng)的邊的集合.

2.2 節(jié)點(diǎn)緩存狀態(tài)

節(jié)點(diǎn)緩存消息的能力,隨著時(shí)間的遞增,因?yàn)槭Ｓ嗑彺婵臻g越來(lái)越小而降低.為了針對(duì)節(jié)點(diǎn)的自身狀態(tài)采取相應(yīng)的擁塞控制策略,本文提出一個(gè)節(jié)點(diǎn)緩存狀態(tài)的概念,根據(jù)節(jié)點(diǎn)占用率劃分節(jié)點(diǎn)的緩存狀態(tài).

定義1.節(jié)點(diǎn)占用率.節(jié)點(diǎn)vi的節(jié)點(diǎn)占用率是指vi緩存中消息大小的總和與vi初始緩存大小的比值,記為OccupyBufferi,表示如公式(1)所示:

(1)

其中MessageSize為節(jié)點(diǎn)vi中每個(gè)消息的大小,Bufferi為節(jié)點(diǎn)vi的初始緩存空間大小.OccupyBufferi越大,vi中剩余的空間越小.

定義2.節(jié)點(diǎn)緩存狀態(tài).基于節(jié)點(diǎn)vi的占用率和節(jié)點(diǎn)vi是否能接受新消息,本文可以根據(jù)公式(2)將節(jié)點(diǎn)vi的狀態(tài)(NSi)分為IS(空閑)、BS(忙碌)和CS(崩潰)3種狀態(tài).

(2)

其中incomingMessage表示節(jié)點(diǎn)vi需要接受的消息,restSpace表示節(jié)點(diǎn)vi中的剩余緩存空間大小.

本文主要是針對(duì)BS和CS來(lái)進(jìn)行分析,動(dòng)態(tài)控制節(jié)點(diǎn)留存消息的能力.對(duì)于處于BS狀態(tài)的節(jié)點(diǎn),本文引入門限度的概念控制留存消息.因?yàn)楫?dāng)節(jié)點(diǎn)處于BS狀態(tài)時(shí),節(jié)點(diǎn)的剩余緩存空間不多,節(jié)點(diǎn)有較快趨勢(shì)到達(dá)CS狀態(tài),此時(shí)需對(duì)消息的留存操作加以控制,以防節(jié)點(diǎn)快速到達(dá)CS狀態(tài),出現(xiàn)大量丟包情況.

2.3 門限度

當(dāng)鄰居節(jié)點(diǎn)處于BS狀態(tài)時(shí),認(rèn)為該節(jié)點(diǎn)快要達(dá)到CS狀態(tài),此時(shí)提高該節(jié)點(diǎn)接受消息的門限值.本文利用節(jié)點(diǎn)間歷史相遇記錄,定義節(jié)點(diǎn)間的相遇概率值.節(jié)點(diǎn)vi和節(jié)點(diǎn)vj的相遇概率值記為Pij,分為更新、衰退,傳遞3種情況,表示如下:

更新:當(dāng)節(jié)點(diǎn)vi和vj建立連接時(shí),通過(guò)公式(3)來(lái)增加Pij.

(3)

衰退:當(dāng)節(jié)點(diǎn)vi和vj很長(zhǎng)一段時(shí)間沒有相遇時(shí),根據(jù)公式(4)更新Pij.

(4)

其中,γ為衰減系數(shù),k為從上次相遇到當(dāng)前時(shí)間經(jīng)過(guò)的間隔塊.

傳遞:當(dāng)節(jié)點(diǎn)vi和vj有相遇機(jī)會(huì),節(jié)點(diǎn)vj和vz也有相遇機(jī)會(huì),則節(jié)點(diǎn)vi和節(jié)點(diǎn)vz依賴此關(guān)系會(huì)獲得一定的相遇機(jī)會(huì).計(jì)算如公式(5)所示:

(5)

其中β為傳遞系數(shù),表示節(jié)點(diǎn)間的傳遞性對(duì)相遇概率值計(jì)算的影響程度.

當(dāng)節(jié)點(diǎn)處于BS狀態(tài)時(shí),需減少節(jié)點(diǎn)留存消息行為,減緩轉(zhuǎn)化為CS狀態(tài)的速度.本文通過(guò)定義門限度的概念,實(shí)現(xiàn)動(dòng)態(tài)改變BS節(jié)點(diǎn)留存消息的能力.

定義3.門限度.當(dāng)節(jié)點(diǎn)vi要向BS節(jié)點(diǎn)vj傳遞消息時(shí),節(jié)點(diǎn)vj接受消息的門限度為節(jié)點(diǎn)vj到目的節(jié)點(diǎn)的投遞概率與節(jié)點(diǎn)vi的剩余緩存空間占比的乘積,記為Ceilj,表示如公式(6)所示:

(6)

其中,Pjd為BS節(jié)點(diǎn)vj與目的節(jié)點(diǎn)vd之間的相遇概率值,restBufferi表示節(jié)點(diǎn)vi的剩余緩存空間大小,Bufferi表示節(jié)點(diǎn)vi的初始緩存空間大小.當(dāng)節(jié)點(diǎn)vj處在BS時(shí),若發(fā)送消息的節(jié)點(diǎn)vi的剩余緩存空間很小,節(jié)點(diǎn)vj將放松留存該消息的要求.

2.4 連接活躍值

在容遲網(wǎng)絡(luò)中,節(jié)點(diǎn)能量有限.當(dāng)節(jié)點(diǎn)間距離越近時(shí),節(jié)點(diǎn)相遇的可能性更大.具體節(jié)點(diǎn)間距離的計(jì)算公式如公式(7)所示:

(7)

其中,xi和yi為節(jié)點(diǎn)vi在網(wǎng)絡(luò)圖中的橫坐標(biāo)和縱坐標(biāo);xd和yd為對(duì)應(yīng)目的節(jié)點(diǎn)的橫坐標(biāo)和縱坐標(biāo).

因?yàn)楣?jié)點(diǎn)的移動(dòng)具有規(guī)律性,節(jié)點(diǎn)在一段時(shí)間內(nèi)可能沿某一特定方向移動(dòng),因此節(jié)點(diǎn)間的連接可能性和節(jié)點(diǎn)的移動(dòng)軌跡有關(guān).當(dāng)節(jié)點(diǎn)移動(dòng)的趨勢(shì)越相近,未來(lái)遇到的可能性越大.本文利用節(jié)點(diǎn)與目的節(jié)點(diǎn)移動(dòng)趨勢(shì)的夾角余弦值,判斷節(jié)點(diǎn)之后相遇的概率.具體夾角余弦值計(jì)算公式如公式(8)所示:

(8)

本文設(shè)定當(dāng)節(jié)點(diǎn)處于BS狀態(tài)時(shí),為避免僅考慮門限度選擇接受消息的片面性,引入連接活躍值的概念.

定義4.連接活躍值.連接活躍值考慮節(jié)點(diǎn)間最近相遇時(shí)刻,移動(dòng)方向夾角和距離預(yù)測(cè)下一次連接的可能性.節(jié)點(diǎn)vi和vd之間的連接活躍值記為CAid,表示如公式(9)所示:

(9)

其中,LTid表示節(jié)點(diǎn)vi和其緩存空間中消息mi的目的節(jié)點(diǎn)vd最近一次相遇時(shí)刻,默認(rèn)為0.最近一次相遇時(shí)刻越大,表示最近一次相遇的時(shí)刻離當(dāng)前時(shí)刻越近,此時(shí)CAid更大.cosɑid表示節(jié)點(diǎn)vi與vd的方向夾角的余弦值,默認(rèn)值為1.當(dāng)cosɑid越大,表示節(jié)點(diǎn)vi與vd的移動(dòng)趨勢(shì)相似,此時(shí)CAid更大.Did表示節(jié)點(diǎn)vi和目的節(jié)點(diǎn)vd之間的距離,默認(rèn)為0.當(dāng)距離越小,表示節(jié)點(diǎn)vi和節(jié)點(diǎn)vd處于同一活動(dòng)范圍,此時(shí)CAid更大.當(dāng)CAid越大時(shí),兩節(jié)點(diǎn)未來(lái)更有可能相遇.

本模型網(wǎng)絡(luò)中的每個(gè)節(jié)點(diǎn)都攜帶一個(gè)最長(zhǎng)長(zhǎng)度為2的鏈表信息,如圖1所示(其中t0

圖1 vi鄰居節(jié)點(diǎn)的位置信息圖Fig.1 Location information graph of vi neighbor nodes

該鏈表信息記錄了當(dāng)前節(jié)點(diǎn)vi與鄰居節(jié)點(diǎn)vj建立連接時(shí),vj的位置信息和當(dāng)前記錄的時(shí)間信息.為避免網(wǎng)絡(luò)中的節(jié)點(diǎn)攜帶大量信息造成負(fù)載,因此定義每個(gè)節(jié)點(diǎn)最多記錄歷史相遇的同一個(gè)節(jié)點(diǎn)的兩個(gè)最新記錄.兩節(jié)點(diǎn)連接活躍值通過(guò)兩節(jié)點(diǎn)記錄鏈表信息來(lái)計(jì)算,但因?yàn)楣?jié)點(diǎn)有歷史遇到過(guò)對(duì)應(yīng)消息的目的節(jié)點(diǎn),沒有遇到過(guò)和單次或多次遇到過(guò)的不同情況,所以需要針對(duì)不同境況進(jìn)行分析,具體分析如下:

1)節(jié)點(diǎn)vi和鄰居節(jié)點(diǎn)vj中都不含消息Mi對(duì)應(yīng)的目的節(jié)點(diǎn)vd的記錄.此時(shí)CAid和CAjd均為默認(rèn)值1.

2)節(jié)點(diǎn)vi和鄰居節(jié)點(diǎn)vj中一共只含有一條關(guān)于目的節(jié)點(diǎn)vd的記錄.此時(shí)默認(rèn)該記錄中關(guān)于vd的信息為最新記錄.以這條記錄中vd的位置為基準(zhǔn),根據(jù)公式(7)去分別計(jì)算Did和Djd.同時(shí)判斷這條記錄是由哪個(gè)節(jié)點(diǎn)提供的,若是vi提供的記錄,則LTid為該記錄中的相遇時(shí)刻,而LTjd為默認(rèn)值0.因?yàn)橐还仓挥幸粭l記錄,兩節(jié)點(diǎn)關(guān)于vd的方向的夾角不計(jì)入考慮,轉(zhuǎn)而考慮兩節(jié)點(diǎn)與vd間的夾角.當(dāng)cosɑij>π/2,則表示節(jié)點(diǎn)vj和節(jié)vi的活動(dòng)區(qū)域不一樣,節(jié)點(diǎn)vj有必要接受消息,此時(shí)把cosɑjd設(shè)為2,cosɑid設(shè)為默認(rèn)值1.

3)節(jié)點(diǎn)vi和節(jié)點(diǎn)vj中一共包含大于或等于2條記錄.此時(shí)比較這些記錄的時(shí)間信息,以最近時(shí)刻的記錄中目的節(jié)點(diǎn)的位置為基準(zhǔn),根據(jù)公式(7)去分別計(jì)算Did和Djd.對(duì)于節(jié)點(diǎn)vi中和節(jié)點(diǎn)vj中的記錄均選擇各自最近記錄中的時(shí)刻賦值給LTid和LTjd.不含記錄的節(jié)點(diǎn)的LT則記為默認(rèn)值0.在記錄中選擇最新的兩條記錄d1和d2,定義最新記錄的目的節(jié)點(diǎn)位置信息記為d(to)(即為目的節(jié)點(diǎn)vd最近可能在的位置),其次新記錄的目的節(jié)點(diǎn)位置信息記為d(from)(即目的節(jié)點(diǎn)vd移動(dòng)的來(lái)源位置).把d(from)到d(to)的位置方向定義為目的節(jié)點(diǎn)的移動(dòng)方向,根據(jù)公式(8)計(jì)算cosɑid和cosɑjd.對(duì)于節(jié)點(diǎn)與目的節(jié)點(diǎn)移動(dòng)方向的夾角余弦值計(jì)算來(lái)說(shuō),記錄新舊記錄信息是非常有必要的,具體分析如下:

由圖2(a)可以看出,節(jié)點(diǎn)vi和目的節(jié)點(diǎn)vd的方向夾角ɑ(i,d)小于節(jié)點(diǎn)vj和vd的方向夾角ɑ(j,d).由圖2(b)可以看出,此時(shí)ɑ(i,d)>ɑ(j,d).綜上分析可得,當(dāng)記錄相同的目的節(jié)點(diǎn)的位置信息,最新目的節(jié)點(diǎn)位置的選擇,會(huì)直接影響節(jié)點(diǎn)與目的節(jié)點(diǎn)移動(dòng)趨勢(shì)夾角余弦值的最終計(jì)算.

圖2 目的節(jié)點(diǎn)移動(dòng)方向分析圖Fig.2 Analysis diagram of destination node moving direction

2.5 丟棄優(yōu)先級(jí)

在網(wǎng)絡(luò)中,消息跳數(shù)大,該消息分布在網(wǎng)絡(luò)中各個(gè)節(jié)點(diǎn)中的可能性更大,即消息在網(wǎng)絡(luò)中擴(kuò)散程度越大.同時(shí),消息在節(jié)點(diǎn)中的時(shí)間越長(zhǎng),側(cè)面表示該消息在節(jié)點(diǎn)中未能快速轉(zhuǎn)發(fā)出去.消息剩余生命周期小,消息不久會(huì)自行清除,在節(jié)點(diǎn)緩存中存在的意義不大.最后,由于節(jié)點(diǎn)緩存有限,大的消息會(huì)降低節(jié)點(diǎn)接受新消息的能力.在不同節(jié)點(diǎn)緩存中的消息,側(cè)重評(píng)估消息重要程度的指標(biāo)也不同.本文基于熵權(quán)法動(dòng)態(tài)計(jì)算在不同節(jié)點(diǎn)中各個(gè)屬性影響占比,后結(jié)合消息的屬性值計(jì)算各個(gè)消息在該節(jié)點(diǎn)中的丟棄優(yōu)先級(jí).

本文利用信息熵的概念計(jì)算在不同節(jié)點(diǎn)下各屬性的影響比重.熵值越大表示概率分布越平均,數(shù)據(jù)差異越明顯,評(píng)判價(jià)值高,此時(shí)提高該因素權(quán)重?cái)?shù)值,具體步驟如下:

1)節(jié)點(diǎn)vi中有m條記錄數(shù)據(jù)如圖3所示,其中每條記錄對(duì)應(yīng)著4列數(shù)據(jù)X1、X2,X3和X4.這m條記錄對(duì)應(yīng)在節(jié)點(diǎn)vi中的m條不同消息,每條記錄的4列數(shù)據(jù)分別對(duì)應(yīng)著該消息的消耗生命周期與初始生命周期的比值,在緩存中停留的時(shí)間與運(yùn)行時(shí)間的比值,消息經(jīng)歷跳數(shù)與網(wǎng)絡(luò)中總節(jié)點(diǎn)個(gè)數(shù)的比值和消息大小與節(jié)點(diǎn)占有緩存空間的比值.

圖3 節(jié)點(diǎn)vi中的消息記錄表圖Fig.3 Message record table diagram in vi

2)對(duì)于步驟1中的對(duì)應(yīng)的4列記錄分別進(jìn)行歸一化處理,將每條記錄中的各列記錄數(shù)據(jù)控制在0～1之間.歸一化處理后值的大小表示在該影響因素下,每個(gè)消息相較于所有消息的數(shù)據(jù)大小,具體歸一化處理公式如公式(10)所示:

(10)

其中,Xik表示每個(gè)消息的各個(gè)屬性,Xk表示該影響因素下的數(shù)據(jù)(k=1,2,3,4),max(Xk)和min(Xk)分別表示各個(gè)影響因素下的最大值和最小值.

3)通過(guò)步驟2得到經(jīng)過(guò)歸一化處理后的各項(xiàng)數(shù)據(jù),接著計(jì)算在每項(xiàng)影響因素下,每條消息對(duì)于這項(xiàng)影響因素的記錄占整個(gè)這項(xiàng)影響因素的數(shù)據(jù)的比重,具體如公式(11)所示:

(11)

其中,m表示在節(jié)點(diǎn)vi中總的消息個(gè)數(shù).

4)計(jì)算關(guān)于各項(xiàng)影響因素的熵值,獲得對(duì)于各項(xiàng)影響因素記錄數(shù)據(jù)的變化程度,具體如公式(12)所示:

(12)

5)熵值越大的影響因素,概率分布越平均,數(shù)據(jù)差異化越明顯,評(píng)判價(jià)值越高,此時(shí)調(diào)高該影響因素的權(quán)值,具體計(jì)算權(quán)重的公式如公式(13)所示:

(13)

其中C1、C2,C3和C4分別對(duì)應(yīng)X1、X2,X3和X4對(duì)于消息重要程度計(jì)算的權(quán)重.

因?yàn)樵谌葸t網(wǎng)絡(luò)中,消息的生命有限,但由于節(jié)點(diǎn)稀疏分布,很多消息在存活期等不到投遞機(jī)會(huì),直到剩余生命殆盡也無(wú)法成功交付.同時(shí),因節(jié)點(diǎn)緩存空間不足,隨路由的進(jìn)行,節(jié)點(diǎn)資源占滿,為接受新消息,大量數(shù)據(jù)包丟失,網(wǎng)絡(luò)性能急劇下降.

定義5.丟棄優(yōu)先級(jí).當(dāng)節(jié)點(diǎn)vj處于BS狀態(tài)時(shí),節(jié)點(diǎn)中消息Mk將消息生命周期、在緩存中停留時(shí)間、跳數(shù)和消息大小結(jié)合起來(lái),利用公式(10)～公式(13)計(jì)算出的各項(xiàng)指標(biāo)權(quán)重計(jì)算Mk在節(jié)點(diǎn)vj中的丟棄優(yōu)先級(jí),節(jié)點(diǎn)vj中消息Mk的丟棄優(yōu)先級(jí)記為Dropk,具體計(jì)算公式如公式(14)所示:

(14)

其中,TTLinit為消息Mk的初始生命周期,TTLrest為消息Mk的剩余生命周期,Tcurrent為當(dāng)前時(shí)刻,Treceive為節(jié)點(diǎn)vj接收消息Mk的時(shí)刻,Countmk為消息Mk已經(jīng)歷的跳數(shù),Countmax為網(wǎng)絡(luò)中總節(jié)點(diǎn)個(gè)數(shù),Sizemk為消息Mk的數(shù)據(jù)大小,Bufferoccupy為節(jié)點(diǎn)vj緩存已占用空間.C1、C2,C3和C4為在節(jié)點(diǎn)vj中分別對(duì)應(yīng)消息生命周期,在緩存中停留時(shí)間,跳數(shù)和消息大小各自對(duì)于丟棄優(yōu)先級(jí)的影響權(quán)重.當(dāng)消息剩余生命周期越大,消息更有機(jī)會(huì)等待投遞到目的節(jié)點(diǎn),相應(yīng)丟棄優(yōu)先級(jí)越低.當(dāng)消息在節(jié)點(diǎn)中時(shí)間越長(zhǎng),消息憑借該節(jié)點(diǎn)轉(zhuǎn)發(fā)的機(jī)會(huì)不大,消息丟棄優(yōu)先級(jí)越高.當(dāng)消息經(jīng)歷跳數(shù)越多,說(shuō)明消息在網(wǎng)絡(luò)中分布的越廣,此時(shí)消息丟棄優(yōu)先級(jí)越高.當(dāng)消息越大,釋放該消息的占用空間能助于接受更多新消息,其丟棄優(yōu)先級(jí)越高.

3 適用于節(jié)點(diǎn)環(huán)境狀態(tài)的擁塞控制管理策略

鄰居節(jié)點(diǎn)vj自身剩余緩存的大小一定程度上可以預(yù)測(cè)在后續(xù)路由過(guò)程中是否有大量丟包情況的發(fā)生.因此,本文針對(duì)鄰居節(jié)點(diǎn)vj處于BS狀態(tài)時(shí),采取一種節(jié)點(diǎn)間位置差異相關(guān)的控制保留策略選擇性留存一些較重要的消息,預(yù)防大量丟包情況的發(fā)生,確保大部分消息能更快的成功投遞.同時(shí),因消息在不同節(jié)點(diǎn)中的重要程度不同,在節(jié)點(diǎn)剩余資源較稀缺的情況下,盡可能地保留更重要的消息,高效利用節(jié)點(diǎn)資源.當(dāng)節(jié)點(diǎn)剩余空間不足以接受新消息時(shí),本文采取一種節(jié)點(diǎn)自差異相關(guān)的丟包策略來(lái)對(duì)節(jié)點(diǎn)緩存中的消息進(jìn)行刪除優(yōu)先級(jí)的排序,通過(guò)刪除丟棄優(yōu)先級(jí)高的消息,避免丟棄行為帶來(lái)的大量性能損失.

3.1 節(jié)點(diǎn)間位置差異相關(guān)的控制保留策略

當(dāng)鄰居節(jié)點(diǎn)vj處于BS狀態(tài)時(shí),因剩余緩存空間不多,所以需判別鄰居節(jié)點(diǎn)vj是否有必要留存消息Mk.

具體的算法如算法1所示.

算法1.節(jié)點(diǎn)間位置差異相關(guān)的控制保留策略算法.

輸入:vj收到vi傳送的消息Mk,vj處于BS狀態(tài),Pid,Pjd

輸出:vj是否留存消息Mk記為布爾值Reservek.

1.根據(jù)公式(6)計(jì)算得Ceilj

2.根據(jù)公式(7)、(8)、(9)計(jì)算得到CAid和CAjd

3.IFPidCAid:

4.Reservek← true

5.ELSE:

6.Reservek← false

7.END IF

8.IFReservek==true:

9. 節(jié)點(diǎn)vj留存Mk

10.ELSE:

11. 節(jié)點(diǎn)vj丟棄Mk

12.END IF

算法1中,行3～行7表示判斷是否需要留存消息Mk,行8～行12表示根據(jù)Reservek進(jìn)行相應(yīng)的留存和丟棄操作.因?yàn)樗惴?是用來(lái)判斷是否需要留存該消息,其時(shí)間復(fù)雜度為O(1).

3.2 節(jié)點(diǎn)自差異相關(guān)的丟包策略

在網(wǎng)絡(luò)中,消息跳數(shù)越大,該消息分布在網(wǎng)絡(luò)中的節(jié)點(diǎn)越多.同時(shí),當(dāng)消息在節(jié)點(diǎn)緩存空間中停留時(shí)間越久,說(shuō)明該消息并未通過(guò)此節(jié)點(diǎn)得到優(yōu)質(zhì)的轉(zhuǎn)發(fā)機(jī)會(huì).而且當(dāng)消息剩余生命周期越短,將自動(dòng)在節(jié)點(diǎn)中刪除.最后,因節(jié)點(diǎn)緩存空間受限,消息數(shù)據(jù)大,占用節(jié)點(diǎn)緩存資源越多,節(jié)點(diǎn)接受其他消息的能力減弱.在不同節(jié)點(diǎn)緩存空間中的消息,消息重要程度的計(jì)算側(cè)重指標(biāo)不一樣,所以本文提出一種利用熵權(quán)法計(jì)算不同節(jié)點(diǎn)中各個(gè)屬性權(quán)重大小的方法.動(dòng)態(tài)計(jì)算得到影響占比C1、C2,C3和C4后,根據(jù)公式(14)計(jì)算各個(gè)消息在該節(jié)點(diǎn)中的丟棄優(yōu)先級(jí).當(dāng)節(jié)點(diǎn)緩存不足時(shí),選擇性的優(yōu)先刪除丟棄優(yōu)先級(jí)高的消息.

具體的算法如算法2所示.

算法2.節(jié)點(diǎn)自差異相關(guān)的丟包策略算法.

輸入:vj處于CS狀態(tài)

輸出:丟棄消息列表dropMessagesList.

1.根據(jù)公式(10)、(11)、(12)、(13)計(jì)算得到C1、C2,C3和C4

2.FOR eachMkINvj:

3. 根據(jù)公式(14)計(jì)算得到Dropk

4. IFDropk>D_min:

5.dropMessagesList←Mk

6. END IF

7.END FOR

8.刪除中在dropMessagesList列表中的消息

算法2中,行1表示動(dòng)態(tài)計(jì)算在節(jié)點(diǎn)vj中消息不同指標(biāo)X1、X2,X3和X4的權(quán)重系數(shù)C1、C2,C3和C4.行2～行7表示對(duì)于vj的消息進(jìn)行遍歷,計(jì)算Dropk和D_min(本文設(shè)置的避免丟棄界限,D_min為常數(shù)值),比較判斷是否將消息添加至丟棄列表.行8表示對(duì)丟棄消息列表中的消息進(jìn)行丟棄.算法2中需要對(duì)節(jié)點(diǎn)中所有消息進(jìn)行遍歷,所以時(shí)間復(fù)雜度為O(m).

3.3 NEMS策略

如圖4所示,NEMS策略實(shí)現(xiàn)步驟如下:

圖4 NEMS策略實(shí)現(xiàn)步驟圖Fig.4 NEMS strategy implementation steps diagram

步驟1.當(dāng)兩個(gè)節(jié)點(diǎn)相遇時(shí),假設(shè)節(jié)點(diǎn)vi需要復(fù)制消息Mk給節(jié)點(diǎn)vj,根據(jù)公式(1)、公式(2)判斷節(jié)點(diǎn)狀態(tài).當(dāng)節(jié)點(diǎn)vj為BS狀態(tài)時(shí),執(zhí)行步驟2;當(dāng)剩余緩存空間不足以接受Mk時(shí),即節(jié)點(diǎn)vj為CS狀態(tài)時(shí),執(zhí)行步驟3.當(dāng)節(jié)點(diǎn)vj為IS狀態(tài)時(shí),執(zhí)行步驟5;否則,執(zhí)行步驟3.

步驟2.執(zhí)行節(jié)點(diǎn)間位置差異相關(guān)的控制保留策略算法,即算法1.當(dāng)vj需留存消息但節(jié)點(diǎn)vj不能直接接收消息Mk時(shí),執(zhí)行步驟3.當(dāng)節(jié)點(diǎn)vj可以直接接受消息Mk時(shí),執(zhí)行步驟5.當(dāng)由算法1判斷需丟棄消息Mk時(shí),執(zhí)行步驟4.

步驟3.執(zhí)行節(jié)點(diǎn)自差異相關(guān)的丟包策略,即算法2.當(dāng)節(jié)點(diǎn)vj還是不能接受消息Mk,則執(zhí)行步驟4;否則,執(zhí)行步驟5.

步驟4.判斷節(jié)點(diǎn)vj是否是Mk的目的節(jié)點(diǎn).當(dāng)節(jié)點(diǎn)vj是Mk的目的節(jié)點(diǎn),則依次刪除在節(jié)點(diǎn)vj緩存中丟棄優(yōu)先級(jí)高的消息,直至接受消息Mk,執(zhí)行步驟5;否則,節(jié)點(diǎn)vj拒絕留存消息Mk.

步驟5.節(jié)點(diǎn)vj留存消息Mk.

具體的算法如算法3所示.

算法3.NEMS策略算法.

輸入:節(jié)點(diǎn)vj收到節(jié)點(diǎn)vi發(fā)來(lái)的消息Mk

輸出:節(jié)點(diǎn)成功留存返回true,丟棄返回false

1. 根據(jù)公式(1)、公式(2)計(jì)算得到NS

2. IFNSj==BS:

3. 執(zhí)行算法1

4. IFvj需要留存消息但節(jié)點(diǎn)vj不能直接接收消息Mk:

5. 執(zhí)行算法2

6. END IF

7. ELSE IFNSj==CS:

8. 執(zhí)行算法2

9. END IF

10.IFMk′s destination node isvj:

11. 刪除vj中的消息直到接受Mk

12.END IF

算法3中,行1表示判斷鄰居節(jié)點(diǎn)vj的狀態(tài),行2～行6表示當(dāng)vj處于BS狀態(tài)時(shí)對(duì)于留存消息選擇進(jìn)行的一系列判斷,行7～行9表示當(dāng)節(jié)點(diǎn)處于CS狀態(tài),即無(wú)法接受需要留存的消息時(shí)需要進(jìn)行的丟棄行為,行10～行12表示當(dāng)vj為消息Mk的目的節(jié)點(diǎn)時(shí),需要留存該消息.算法3中由于包含了算法1和算法2,所以其時(shí)間復(fù)雜度為O(m).

4 仿真實(shí)驗(yàn)與結(jié)果分析

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

本文基于ONE[18](Opportunistic Network Environment)平臺(tái).因?yàn)閭鹘y(tǒng)的Epidemic[19]策略是一個(gè)基于洪泛思想的經(jīng)典策略,該策略向網(wǎng)絡(luò)中復(fù)制大量的消息副本,從而導(dǎo)致大量丟包情況的出現(xiàn).同時(shí),因?yàn)閭鹘y(tǒng)的Prophet[20]策略基于歷史預(yù)測(cè)策略,不盲目的給鄰居節(jié)點(diǎn)復(fù)制消息副本.但是,并未針對(duì)性控制在網(wǎng)絡(luò)中丟包情況的發(fā)生.為更好地展示算法性能,本文將NEMS策略、SAD策略、MPBBM算法中的緩存策略,和OANBM路由算法中的緩存管理OANBM-MS策略分別加在傳統(tǒng)的Epidemic路由策略和Prophet路由策略上,通過(guò)改變節(jié)點(diǎn)存儲(chǔ)空間的大小從消息成功投遞率,網(wǎng)絡(luò)負(fù)載率,平均傳輸時(shí)延,平均跳數(shù)4個(gè)方面來(lái)比較在傳統(tǒng)路由策略上不加NEMS策略、加NEMS策略、加SAD策略、加MPBBM算法中緩存策略,和加OANBM-MS策略的各個(gè)網(wǎng)絡(luò)性能.具體的仿真配置如表1所示.

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

4.2 仿真結(jié)果分析

4.2.1 對(duì)比Epidemic路由策略

1)不同緩存空間大小

基于前面的仿真環(huán)境配置,在Epidemic路由策略的基礎(chǔ)上,改變消息緩存空間的大小,對(duì)比加入NEMS、MPBBM、OANBMMS和SAD后和原生Epidemic路由在消息投遞率(如圖5所示)、網(wǎng)絡(luò)開銷(如圖6所示)、平均時(shí)延(如圖7所示)和平均跳數(shù)(如圖8所示)這4個(gè)性能指標(biāo)的變化情況.

圖5 基于Epidemic的不同緩存大小下的投遞率Fig.5 Delivery rate under different cache sizes based on Epidemic

圖6 基于Epidemic的不同緩存大小下的網(wǎng)絡(luò)開銷Fig.6 Network overhead with different cache sizes based on Epidemic

圖7 基于Epidemic的不同緩存大小下的平均時(shí)延Fig.7 Average latency of different cache sizes based on Epidemic

圖8 基于Epidemic的不同緩存大小下的平均跳數(shù)Fig.8 Average hop count for different cache sizes based on Epidemic

圖5顯示了不同緩存管理策略對(duì)于Epidemic路由策略和優(yōu)化后的Epidemic路由策略在不同緩存大小下消息投遞率的變化趨勢(shì).隨著節(jié)點(diǎn)緩存空間的擴(kuò)增,投遞率均呈現(xiàn)陸續(xù)增加.因?yàn)楫?dāng)節(jié)點(diǎn)緩存空間變多時(shí),避免網(wǎng)絡(luò)中出現(xiàn)擁塞,降低丟包數(shù)量,消息到目的節(jié)點(diǎn)的概率越高.從圖5中還可以看出,加入NEMS后的投遞率相較于加入MPBBM平均提高了29.50%,相較于加入OANBMMS平均提高了34.24%,相較于加入SAD平均提高了77.69%,相較于原生的Epidemic投遞率更是平均增長(zhǎng)了124.16%.這主要得益于NEMS策略的2個(gè)本質(zhì)原因:1)NEMS策略對(duì)于BS節(jié)點(diǎn)是否留存消息的決定綜合了門限度和與目的節(jié)點(diǎn)的連接活躍值兩方面考慮,保證了接收投遞可能性更大的消息;2)NEMS策略中制定的消息丟棄策略,采用了熵權(quán)法來(lái)動(dòng)態(tài)求消息的各個(gè)自身屬性在不同節(jié)點(diǎn)中的影響,這樣設(shè)計(jì)的丟棄策略能夠保證價(jià)值更高的消息留存于節(jié)點(diǎn)中,也能控制網(wǎng)絡(luò)中的丟包數(shù)目,提高消息投遞到其目的節(jié)點(diǎn)的概率.

圖6表示了在Epidemic路由策略中加入不同緩存管理策略和Epidemic路由策略,隨著緩存空間的增大,它們?cè)诰W(wǎng)絡(luò)中的開銷.可以發(fā)現(xiàn)加入了NEMS之后,網(wǎng)絡(luò)開銷在節(jié)點(diǎn)緩存空間增至約3MB的時(shí)候,就降到了不到16,并一直處于一個(gè)很低的水平.可以發(fā)現(xiàn)加入NEMS之后的網(wǎng)絡(luò)開銷大大降低,相較于原生Epidemic路由策略降低了約74.08%,比起加入MPBBM、OANBMMS和SAD之后Epidemic路由策略的網(wǎng)絡(luò)開銷的降低程度的還要高約2倍.這都是由于NEMS策略提高了BS節(jié)點(diǎn)留存消息的要求,使得較少的緩存空間能被充分高效利用.

圖7比較了加入不同緩存管理之后和原生Epidemic策略在隨著緩存大小增加,它們消息成功到達(dá)目的節(jié)點(diǎn)的平均時(shí)延的高低.可以發(fā)現(xiàn)加入了NEMS后,它的平均時(shí)延在緩存空間約為2～7MB之間時(shí)高于其他.這是因?yàn)榧尤肓薔EMS會(huì)增加大量的計(jì)算和判斷來(lái)控制擁塞情況的發(fā)生,這也導(dǎo)致了在時(shí)間上的損耗和犧牲.

圖8則表示了加入NEMS緩存管理策略和加入其他緩存策略和原生Epidemic路由在緩存空間不斷增大的前提下,它們的平均跳數(shù)的變化.可以發(fā)現(xiàn)在緩存大小為約1～5MB之間時(shí),加入NEMS的平均跳數(shù)是低于其他的,當(dāng)緩存空間大小大于約6MB時(shí),又高于加入MPBBM后的Epidemic的平均條數(shù).這是因?yàn)镹EMS策略本身控制消息的洪泛,對(duì)于節(jié)點(diǎn)留存消息進(jìn)行一定的控制,所以可以在一定程度上降低平均跳數(shù).

綜上分析可得,加入了NEMS緩存管理策略后的Epidemic相較于加入其他緩存管理策略如MPBBM、OANBMMS和SAD在投遞率和網(wǎng)絡(luò)開銷性能上都有較大的提升,針對(duì)平均條數(shù)在除了加了MPBBM策略的部分情況外,也有一定的改善.但是加入了NEMS策略后,明顯的劣勢(shì)在于平均時(shí)延有一定的增長(zhǎng),這也是由于NEMS策略本身的大量控制計(jì)算的原因所導(dǎo)致的.

2)不同消息生存周期

在Epidemic路由策略的基礎(chǔ)上,改變消息生存周期的大小,對(duì)比分析加入NEMS、MPBBM、OANBMMS和SAD后和原生Epidemic路由在消息投遞率(如圖9所示)、網(wǎng)絡(luò)開銷(如圖10所示)、平均時(shí)延(如圖11所示)和平均跳數(shù)(如圖12所示)這4個(gè)性能指標(biāo)的變化情況.

圖9 基于Epidemic的不同消息生存周期下的投遞率Fig.9 Delivery rate of different message lifetimes based on Epidemic

圖10 基于Epidemic的不同消息生存周期下的網(wǎng)絡(luò)開銷Fig.10 Network overhead with different message lifetimes based on Epidemic

圖11 基于Epidemic的不同消息生存周期下的平均時(shí)延Fig.11 Average delay under different message lifetimes based on Epidemic

圖12 基于Epidemic的不同消息生存周期下的平均跳數(shù)Fig.12 Average hop count under different message lifetimes based on Epidemic

圖9顯示了在Epidemic中加入不同緩存管理策略后,隨著消息生存周期的增加,它們的消息成功投遞率.可以看出加入了NEMS后投遞率對(duì)比于加入MPBBM后增加了20.87%,對(duì)比于加入OANBMMS后增加了28.63%,對(duì)于于加入SAD后增加了69.38%.可以發(fā)現(xiàn)當(dāng)消息的生存周期越來(lái)越大時(shí),加入了NEMS策略之后的消息的投遞率并不會(huì)像原生Epidemic一樣由于消息在緩存空間停留時(shí)間過(guò)久,因?yàn)榇罅縼G包情況而降低.相反加入了NEMS后隨著消息存活時(shí)間的增加,消息的投遞率不降反增,這是由于NEMS策略控制留存消息,防止了大量丟包情況的發(fā)生.同時(shí)消息生存時(shí)間比較長(zhǎng),在不考慮緩存空間匱乏的前提下還可以增加投遞到目的節(jié)點(diǎn)的機(jī)會(huì).

圖10比較了各個(gè)緩存管理策略加入,網(wǎng)絡(luò)開銷的大小隨著消息生存周期增加的變化.可以看出加入了NEMS策略后,網(wǎng)絡(luò)開銷降低的非常明顯.加入了MPBBM、OANBMMS和SAD策略后,網(wǎng)絡(luò)開銷大約降低了39.48%、46.46%和35.05%.但是加入了NEMS策略后,網(wǎng)絡(luò)開銷降低高達(dá)了約81.42%.這體現(xiàn)了加入NEMS緩存管理策略后,因?yàn)榭刂屏舸婧蛠G棄會(huì)大大降低網(wǎng)絡(luò)中的開銷.

圖11比較了加入各種緩存管理策略后,在消息生存周期不同的前提下,Epidemic路由策略在平均時(shí)延上的變化.可以看出加入了NEMS、MPBBM、OANBMMS和SAD策略后的平均時(shí)延相較于原生Epidemic都增加了約23.21%、14.02%、3.76%和14.67%.這是由于消息存活時(shí)間越久,在網(wǎng)絡(luò)節(jié)點(diǎn)中的消息越多,但節(jié)點(diǎn)數(shù)目不變,這導(dǎo)致消息越晚投遞到目的節(jié)點(diǎn).相較于其他的緩存管理策略,加入NEMS策略后的平均時(shí)延的增加略高,這是因?yàn)镹EMS策略為了選擇留存和丟棄消息有大量的計(jì)算過(guò)程.

圖12可以看出加入各種緩存管理策略后,在消息生存周期不同的前提下,Epidemic路由策略在平均跳數(shù)上的變化.加入了NEMS或者加入了MPBBM后,平均跳數(shù)控制在大概2跳的水平.加入了SAD策略后也可以將平均跳數(shù)也大概處于3跳.相較于別的策略,加入OANBMMS后平均跳數(shù)相較于原生Epidemic策略還增加了不到1跳.

總體分析,加入不同的緩存管理策略后的Epidemic,隨著消息生存周期的增加,加入NEMS策略后的路由策略在消息的投遞率、網(wǎng)絡(luò)開銷和平均跳數(shù)都有很好的性能提升.

4.2.2 對(duì)比Prophet路由策略

1)不同緩存空間大小

在Prophet路由策略的基礎(chǔ)上,改變不同節(jié)點(diǎn)緩存的大小,對(duì)比分析加入NEMS、MPBBM、OANBMMS和SAD后和原生Prophet路由在消息投遞率(如圖13所示)、網(wǎng)絡(luò)開銷(如圖14所示)、平均時(shí)延(如圖15所示)和平均跳數(shù)(如圖16所示)這4個(gè)性能指標(biāo)的變化情況.

圖13 基于Prophet的不同緩存大小下的投遞率Fig.13 Delivery rate under different cache sizes based on Prophet

圖14 基于Prophet的不同緩存大小下的網(wǎng)絡(luò)開銷Fig.14 Network overhead with different cache sizes based on Prophet

圖15 基于Prophet的不同緩存大小下的平均時(shí)延Fig.15 Average latency of different cache sizes based on Prophet

圖16 基于Prophet的不同緩存大小下的平均跳數(shù)Fig.16 Average hop count with different cache sizes based on Prophet

圖13顯示了加入NEMS策略后,投遞率在原生Prophet的基礎(chǔ)上增加了100.93%.對(duì)比緩存策略MPBBM、OANBMMS和SAD策略對(duì)于Prophet路由策略投遞率的提高還分別增加了約18.38%、25.48%和56.82%.這恰恰反映了NEMS策略根據(jù)節(jié)點(diǎn)自身狀態(tài)而做出調(diào)整存儲(chǔ)消息能夠使得節(jié)點(diǎn)盡可能為更高可能被投遞到目的節(jié)點(diǎn)的消息服務(wù),從而提高消息的投遞率.

圖14比較了加入不同的緩存管理策略后的Prophet的網(wǎng)絡(luò)開銷的降低情況.由圖可知加入不同的緩存管理策略能夠減低網(wǎng)絡(luò)開銷.加入NEMS、MPBBM、OANBMMS和SAD分別可以降低原生Prophet的網(wǎng)絡(luò)開銷大約為74.98%、25.74%、47.11%和32.03%.可以看出加入NEMS后能夠?qū)﹂_銷進(jìn)行一個(gè)很好的控制,這是因?yàn)镹EMS中對(duì)每個(gè)節(jié)點(diǎn)的留存消息的操作進(jìn)行了控制.

圖15分析了加入不同緩存管理策略之后的Prophet的平均時(shí)延的變化.從圖15中可以發(fā)現(xiàn),加入緩存管理策略因?yàn)橐欢ǔ潭壬显黾恿擞?jì)算的步驟,所以時(shí)延都或多或少會(huì)有所增加.隨著節(jié)點(diǎn)緩存大小的增加,加入的NEMS策略后的平均時(shí)延會(huì)越來(lái)越高,且比原生Prophet的平均時(shí)延高約0.81千秒.這是因?yàn)镹EMS策略的比較計(jì)算的過(guò)程比較多,所以會(huì)增加時(shí)延.

圖16顯示了加入不同緩存策略之后消息成功投遞的平均跳數(shù)的大小.加入NEMS策略、MPBBM、OANBMMS和SAD策略后的平均跳數(shù)約為2.20、2.26、3.33和2.84跳,而原生的Prophet的平均跳數(shù)約為3.03.可以發(fā)現(xiàn)除了OANBMMS緩存策略的加入會(huì)增加一些平均跳數(shù)之外,其他緩存策略的加入都可以減低一些平均跳數(shù).其中加入NEMS策略之后,平均跳數(shù)能大概降低0.83,這是因?yàn)楣?jié)點(diǎn)控制留存消息會(huì)控制消息在網(wǎng)絡(luò)中的分布情況.

結(jié)合上述分析,可以發(fā)現(xiàn)加入了NEMS緩存策略之后可以提高原來(lái)Prophet路由策略的消息成功投遞率,還可以大幅度降低網(wǎng)絡(luò)開銷,還可以降低一定的平均消息到達(dá)目的節(jié)點(diǎn)的跳數(shù).

2)不同消息生存周期

在Prophet路由策略的基礎(chǔ)上,改變消息的生存周期大小,對(duì)比分析加入NEMS、MPBBM、OANBMMS和SAD后和原生Prophet路由在消息投遞率(如圖17所示)、網(wǎng)絡(luò)開銷(如圖18所示)、平均時(shí)延(如圖19所示)和平均跳數(shù)(如圖20所示)這4個(gè)性能指標(biāo)的變化情況.

圖17 基于Prophet的不同消息生存周期下的投遞率Fig.17 Delivery rate of different message lifetimes based on Prophet

圖18 基于Prophet的不同消息生存周期下的網(wǎng)絡(luò)開銷Fig.18 Network overhead with different message lifetimes based on Prophet

圖19 基于Prophet的不同消息生存周期下的平均時(shí)延Fig.19 Average delay of different message lifetimes based on Prophet

圖20 基于Prophet的不同消息生存周期下的平均跳數(shù)Fig.20 Average hop count under different message lifetimes based on Prophet

圖17中,對(duì)比分析了加入不同的緩存機(jī)制后,隨著消息生存周期的增加投遞率的變化情況.從圖中可以注意到除了Prophet隨著消息生存周期的增加投遞率會(huì)有所降低外,其他加入了緩存管理的路由的消息投遞率大致都是呈增長(zhǎng)趨勢(shì).其中NEMS的加入對(duì)比MPBBM、OANBMMS和SAD策略的加入投遞率還高出了約13.18%、23.51%和57.89%.這表示了NEMS的加入,會(huì)大幅度提高消息成功投遞到目的節(jié)點(diǎn)的可能性,這都得益于NEMS策略中根據(jù)節(jié)點(diǎn)狀態(tài)和消息和節(jié)點(diǎn)的關(guān)系比較判斷來(lái)選擇性留存消息的操作,以及丟棄策略的引入可以控制網(wǎng)絡(luò)中丟包情況的發(fā)生.

圖18比較分析了加入不同的緩存管理策略后,在網(wǎng)絡(luò)開銷性能上的降低情況.加入NEMS策略之后相較于Prophet策略的網(wǎng)絡(luò)開銷降低了約76.05%,加入MPBBM相較于Prophet降低了約22.89%,加入OANBMMS相較于Prophet降低了約46.17%,加入SAD相較于Prophet降低了約27.21%.比較分析可得,加入NEMS策略后,由于對(duì)于留存消息進(jìn)行控制,網(wǎng)絡(luò)開銷可以大幅度的降低.

圖19中分析了各個(gè)緩存策略的加入,隨著消息生存周期的增加平均時(shí)延的變化.由圖19可得,當(dāng)消息生存周期變大時(shí),平均時(shí)延呈現(xiàn)一個(gè)增長(zhǎng)的狀態(tài).這是因?yàn)橄⑸鏁r(shí)間變長(zhǎng),在節(jié)點(diǎn)中停留的時(shí)間變久,消息到達(dá)目的節(jié)點(diǎn)的平均時(shí)延就會(huì)有所增加.總體分析可以發(fā)現(xiàn)加入了NEMS后的平均時(shí)延的增長(zhǎng)趨勢(shì)最明顯,這源自于NEMS中繁瑣的計(jì)算體系.

圖20中分析了隨著消息生存周期的增加,加入不同緩存機(jī)制后消息到達(dá)目的節(jié)點(diǎn)的歷經(jīng)跳數(shù)數(shù)目個(gè)數(shù).從圖中可以看出,除了加入OANBMMS策略后跳數(shù)會(huì)增加之外,加入其他的緩存管理策略都會(huì)降低一定的平均跳數(shù).其中加入NEMS策略后的平均跳數(shù)減少的最多,約減小了0.90跳.這也體現(xiàn)了加入了NEMS策略之后,相對(duì)于會(huì)充分利用節(jié)點(diǎn)的傳送機(jī)會(huì).

總體來(lái)看,對(duì)于對(duì)比的3個(gè)緩存管理策略來(lái)說(shuō),NEMS策略的加入在消息投遞率和網(wǎng)絡(luò)開銷兩性能指標(biāo)上有很大的優(yōu)勢(shì),同時(shí)也可以保證平均跳數(shù)穩(wěn)定在極低的水平上.但是唯一的缺點(diǎn)在于NEMS策略因?yàn)楸旧淼挠?jì)算比較操作比較多,所以會(huì)增加平均時(shí)延.

5 結(jié)論與展望

本文針對(duì)在容遲網(wǎng)絡(luò)中由于節(jié)點(diǎn)緩存空間有限導(dǎo)致大量數(shù)據(jù)包丟失,從而影響網(wǎng)絡(luò)性能的問題提出了一種適用于節(jié)點(diǎn)環(huán)境狀態(tài)的擁塞控制管理策略NEMS.該策略根據(jù)節(jié)點(diǎn)緩存狀態(tài)的不同,采取相應(yīng)的處理策略:當(dāng)節(jié)點(diǎn)處于BS狀態(tài)時(shí),采用節(jié)點(diǎn)間位置差異相關(guān)的控制保留策略來(lái)選擇性進(jìn)行留存操作;當(dāng)節(jié)點(diǎn)處于CS狀態(tài)時(shí),采用節(jié)點(diǎn)自差異相關(guān)的丟包策略來(lái)優(yōu)先刪除丟棄優(yōu)先級(jí)高的消息.通過(guò)將不同的緩存管理策略引入Epidemic和Prophet路由策略中做對(duì)比分析可得,NEMS擁塞控制策略的引入可以有效提高消息投遞率,還可以大幅度的降低網(wǎng)絡(luò)開銷,同時(shí)還可以穩(wěn)定平均跳數(shù)在一個(gè)極低的水平.然而由于NEMS策略中復(fù)雜的計(jì)算比較步驟會(huì)導(dǎo)致平均時(shí)延的增加,這也是下一步研究工作的重點(diǎn).