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

(華中師范大學 計算機學院,武漢 430079)

0 引 言

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

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

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

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

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

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

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

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

1 相關工作

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

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

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

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

在容遲網絡中,成功投遞的消息還是會占用網絡資源.在文獻[17]中提出ACK應答機制,清除網絡中已成功投遞的消息,避免冗余消息占用節(jié)點資源,將節(jié)點資源高效利用起來.

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

2 問題模型

2.1 網絡模型

假設整個網絡表示為G=(V,E),V={vi|1≤i≤n}是網絡中的節(jié)點集合,其中n為網絡中節(jié)點的個數(shù).E是節(jié)點間對應的邊的集合.

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

節(jié)點緩存消息的能力,隨著時間的遞增,因為剩余緩存空間越來越小而降低.為了針對節(jié)點的自身狀態(tài)采取相應的擁塞控制策略,本文提出一個節(jié)點緩存狀態(tài)的概念,根據(jù)節(jié)點占用率劃分節(jié)點的緩存狀態(tài).

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

(1)

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

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

(2)

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

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

2.3 門限度

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

更新:當節(jié)點vi和vj建立連接時,通過公式(3)來增加Pij.

(3)

衰退:當節(jié)點vi和vj很長一段時間沒有相遇時,根據(jù)公式(4)更新Pij.

(4)

其中,γ為衰減系數(shù),k為從上次相遇到當前時間經過的間隔塊.

傳遞:當節(jié)點vi和vj有相遇機會,節(jié)點vj和vz也有相遇機會,則節(jié)點vi和節(jié)點vz依賴此關系會獲得一定的相遇機會.計算如公式(5)所示:

(5)

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

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

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

(6)

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

2.4 連接活躍值

在容遲網絡中,節(jié)點能量有限.當節(jié)點間距離越近時,節(jié)點相遇的可能性更大.具體節(jié)點間距離的計算公式如公式(7)所示:

(7)

其中,xi和yi為節(jié)點vi在網絡圖中的橫坐標和縱坐標;xd和yd為對應目的節(jié)點的橫坐標和縱坐標.

因為節(jié)點的移動具有規(guī)律性,節(jié)點在一段時間內可能沿某一特定方向移動,因此節(jié)點間的連接可能性和節(jié)點的移動軌跡有關.當節(jié)點移動的趨勢越相近,未來遇到的可能性越大.本文利用節(jié)點與目的節(jié)點移動趨勢的夾角余弦值,判斷節(jié)點之后相遇的概率.具體夾角余弦值計算公式如公式(8)所示:

(8)

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

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

(9)

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

本模型網絡中的每個節(jié)點都攜帶一個最長長度為2的鏈表信息,如圖1所示(其中t0

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

該鏈表信息記錄了當前節(jié)點vi與鄰居節(jié)點vj建立連接時,vj的位置信息和當前記錄的時間信息.為避免網絡中的節(jié)點攜帶大量信息造成負載,因此定義每個節(jié)點最多記錄歷史相遇的同一個節(jié)點的兩個最新記錄.兩節(jié)點連接活躍值通過兩節(jié)點記錄鏈表信息來計算,但因為節(jié)點有歷史遇到過對應消息的目的節(jié)點,沒有遇到過和單次或多次遇到過的不同情況,所以需要針對不同境況進行分析,具體分析如下:

1)節(jié)點vi和鄰居節(jié)點vj中都不含消息Mi對應的目的節(jié)點vd的記錄.此時CAid和CAjd均為默認值1.

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

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

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

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

2.5 丟棄優(yōu)先級

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

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

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

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

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

(10)

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

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

(11)

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

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

(12)

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

(13)

其中C1、C2,C3和C4分別對應X1、X2,X3和X4對于消息重要程度計算的權重.

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

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

(14)

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

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

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

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

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

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

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

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

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

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

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

3.IFPidCAid:

4.Reservek← true

5.ELSE:

6.Reservek← false

7.END IF

8.IFReservek==true:

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

10.ELSE:

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

12.END IF

算法1中,行3～行7表示判斷是否需要留存消息Mk,行8～行12表示根據(jù)Reservek進行相應的留存和丟棄操作.因為算法1是用來判斷是否需要留存該消息,其時間復雜度為O(1).

3.2 節(jié)點自差異相關的丟包策略

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

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

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

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

輸出:丟棄消息列表dropMessagesList.

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

2.FOR eachMkINvj:

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

4. IFDropk>D_min:

5.dropMessagesList←Mk

6. END IF

7.END FOR

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

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

3.3 NEMS策略

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

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

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

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

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

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

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

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

算法3.NEMS策略算法.

輸入:節(jié)點vj收到節(jié)點vi發(fā)來的消息Mk

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

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

2. IFNSj==BS:

3. 執(zhí)行算法1

4. IFvj需要留存消息但節(jié)點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é)點vj的狀態(tài),行2～行6表示當vj處于BS狀態(tài)時對于留存消息選擇進行的一系列判斷,行7～行9表示當節(jié)點處于CS狀態(tài),即無法接受需要留存的消息時需要進行的丟棄行為,行10～行12表示當vj為消息Mk的目的節(jié)點時,需要留存該消息.算法3中由于包含了算法1和算法2,所以其時間復雜度為O(m).

4 仿真實驗與結果分析

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

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

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

4.2 仿真結果分析

4.2.1 對比Epidemic路由策略

1)不同緩存空間大小

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

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

圖6 基于Epidemic的不同緩存大小下的網絡開銷Fig.6 Network overhead with different cache sizes based on Epidemic

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

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

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

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

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

2)不同消息生存周期

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

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

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

圖11 基于Epidemic的不同消息生存周期下的平均時延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后投遞率對比于加入MPBBM后增加了20.87%,對比于加入OANBMMS后增加了28.63%,對于于加入SAD后增加了69.38%.可以發(fā)現(xiàn)當消息的生存周期越來越大時,加入了NEMS策略之后的消息的投遞率并不會像原生Epidemic一樣由于消息在緩存空間停留時間過久,因為大量丟包情況而降低.相反加入了NEMS后隨著消息存活時間的增加,消息的投遞率不降反增,這是由于NEMS策略控制留存消息,防止了大量丟包情況的發(fā)生.同時消息生存時間比較長,在不考慮緩存空間匱乏的前提下還可以增加投遞到目的節(jié)點的機會.

圖10比較了各個緩存管理策略加入,網絡開銷的大小隨著消息生存周期增加的變化.可以看出加入了NEMS策略后,網絡開銷降低的非常明顯.加入了MPBBM、OANBMMS和SAD策略后,網絡開銷大約降低了39.48%、46.46%和35.05%.但是加入了NEMS策略后,網絡開銷降低高達了約81.42%.這體現(xiàn)了加入NEMS緩存管理策略后,因為控制留存和丟棄會大大降低網絡中的開銷.

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

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

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

4.2.2 對比Prophet路由策略

1)不同緩存空間大小

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

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

圖14 基于Prophet的不同緩存大小下的網絡開銷Fig.14 Network overhead with different cache sizes based on Prophet

圖15 基于Prophet的不同緩存大小下的平均時延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的基礎上增加了100.93%.對比緩存策略MPBBM、OANBMMS和SAD策略對于Prophet路由策略投遞率的提高還分別增加了約18.38%、25.48%和56.82%.這恰恰反映了NEMS策略根據(jù)節(jié)點自身狀態(tài)而做出調整存儲消息能夠使得節(jié)點盡可能為更高可能被投遞到目的節(jié)點的消息服務,從而提高消息的投遞率.

圖14比較了加入不同的緩存管理策略后的Prophet的網絡開銷的降低情況.由圖可知加入不同的緩存管理策略能夠減低網絡開銷.加入NEMS、MPBBM、OANBMMS和SAD分別可以降低原生Prophet的網絡開銷大約為74.98%、25.74%、47.11%和32.03%.可以看出加入NEMS后能夠對開銷進行一個很好的控制,這是因為NEMS中對每個節(jié)點的留存消息的操作進行了控制.

圖15分析了加入不同緩存管理策略之后的Prophet的平均時延的變化.從圖15中可以發(fā)現(xiàn),加入緩存管理策略因為一定程度上增加了計算的步驟,所以時延都或多或少會有所增加.隨著節(jié)點緩存大小的增加,加入的NEMS策略后的平均時延會越來越高,且比原生Prophet的平均時延高約0.81千秒.這是因為NEMS策略的比較計算的過程比較多,所以會增加時延.

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

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

2)不同消息生存周期

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

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

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

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

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

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

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

總體來看,對于對比的3個緩存管理策略來說,NEMS策略的加入在消息投遞率和網絡開銷兩性能指標上有很大的優(yōu)勢,同時也可以保證平均跳數(shù)穩(wěn)定在極低的水平上.但是唯一的缺點在于NEMS策略因為本身的計算比較操作比較多,所以會增加平均時延.

5 結論與展望

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