DTN中適用于節點環境狀態的擁塞控制管理策略

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

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

0 引 言

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

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

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

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

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

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

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

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

1 相關工作

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

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

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

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

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

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

2 問題模型

2.1 網絡模型

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

2.2 節點緩存狀態

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

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

(1)

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

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

(2)

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

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

2.3 門限度

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

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

(3)

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

(4)

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

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

(5)

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

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

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

(6)

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

2.4 連接活躍值

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

(7)

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

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

(8)

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

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

(9)

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

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

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

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

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

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

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

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

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

2.5 丟棄優先級

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

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

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

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

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

(10)

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

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

(11)

其中,m表示在節點vi中總的消息個數.

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

(12)

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

(13)

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

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

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

(14)

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

3 適用于節點環境狀態的擁塞控制管理策略

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

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

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

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

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

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

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

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

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

3.IFPidCAid:

4.Reservek← true

5.ELSE:

6.Reservek← false

7.END IF

8.IFReservek==true:

9. 節點vj留存Mk

10.ELSE:

11. 節點vj丟棄Mk

12.END IF

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

3.2 節點自差異相關的丟包策略

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

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

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

輸入:vj處于CS狀態

輸出:丟棄消息列表dropMessagesList.

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

2.FOR eachMkINvj:

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

4. IFDropk>D_min:

5.dropMessagesList←Mk

6. END IF

7.END FOR

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

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

3.3 NEMS策略

如圖4所示,NEMS策略實現步驟如下:

圖4 NEMS策略實現步驟圖Fig.4 NEMS strategy implementation steps diagram

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

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

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

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

步驟5.節點vj留存消息Mk.

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

算法3.NEMS策略算法.

輸入:節點vj收到節點vi發來的消息Mk

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

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

2. IFNSj==BS:

3. 執行算法1

4. IFvj需要留存消息但節點vj不能直接接收消息Mk:

5. 執行算法2

6. END IF

7. ELSE IFNSj==CS:

8. 執行算法2

9. END IF

10.IFMk′s destination node isvj:

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

12.END IF

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

4 仿真實驗與結果分析

4.1 仿真環境配置

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

表1 仿真參數Table 1 Simulation parameters

4.2 仿真結果分析

4.2.1 對比Epidemic路由策略

1)不同緩存空間大小

基于前面的仿真環境配置,在Epidemic路由策略的基礎上,改變消息緩存空間的大小,對比加入NEMS、MPBBM、OANBMMS和SAD后和原生Epidemic路由在消息投遞率(如圖5所示)、網絡開銷(如圖6所示)、平均時延(如圖7所示)和平均跳數(如圖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的不同緩存大小下的平均跳數Fig.8 Average hop count for different cache sizes based on Epidemic

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

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

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

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

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

2)不同消息生存周期

在Epidemic路由策略的基礎上,改變消息生存周期的大小,對比分析加入NEMS、MPBBM、OANBMMS和SAD后和原生Epidemic路由在消息投遞率(如圖9所示)、網絡開銷(如圖10所示)、平均時延(如圖11所示)和平均跳數(如圖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的不同消息生存周期下的平均跳數Fig.12 Average hop count under different message lifetimes based on Epidemic

圖9顯示了在Epidemic中加入不同緩存管理策略后,隨著消息生存周期的增加,它們的消息成功投遞率.可以看出加入了NEMS后投遞率對比于加入MPBBM后增加了20.87%,對比于加入OANBMMS后增加了28.63%,對于于加入SAD后增加了69.38%.可以發現當消息的生存周期越來越大時,加入了NEMS策略之后的消息的投遞率并不會像原生Epidemic一樣由于消息在緩存空間停留時間過久,因為大量丟包情況而降低.相反加入了NEMS后隨著消息存活時間的增加,消息的投遞率不降反增,這是由于NEMS策略控制留存消息,防止了大量丟包情況的發生.同時消息生存時間比較長,在不考慮緩存空間匱乏的前提下還可以增加投遞到目的節點的機會.

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

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

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

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

4.2.2 對比Prophet路由策略

1)不同緩存空間大小

在Prophet路由策略的基礎上,改變不同節點緩存的大小,對比分析加入NEMS、MPBBM、OANBMMS和SAD后和原生Prophet路由在消息投遞率(如圖13所示)、網絡開銷(如圖14所示)、平均時延(如圖15所示)和平均跳數(如圖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的不同緩存大小下的平均跳數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策略根據節點自身狀態而做出調整存儲消息能夠使得節點盡可能為更高可能被投遞到目的節點的消息服務,從而提高消息的投遞率.

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

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

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

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

2)不同消息生存周期

在Prophet路由策略的基礎上,改變消息的生存周期大小,對比分析加入NEMS、MPBBM、OANBMMS和SAD后和原生Prophet路由在消息投遞率(如圖17所示)、網絡開銷(如圖18所示)、平均時延(如圖19所示)和平均跳數(如圖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的不同消息生存周期下的平均跳數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的加入,會大幅度提高消息成功投遞到目的節點的可能性,這都得益于NEMS策略中根據節點狀態和消息和節點的關系比較判斷來選擇性留存消息的操作,以及丟棄策略的引入可以控制網絡中丟包情況的發生.

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

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

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

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

5 結論與展望

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