MDCE路由算法的分析與改進

楊萬鑫 汪學明 夏紅紅

1(貴州大學計算機科學與技術學院 貴州 貴陽 550025) 2(凱里學院大數據工程學院 貴州 凱里 556011)

0 引 言

延遲容忍網絡(Delay Tolerant Networks,DTN)使用“存儲-攜帶-轉發”的方式進行消息傳遞，于 2003年由Kevin Fall首次明確提出，其特點是高時延、移動性、資源受限、節點密度稀疏、網絡拓撲結構頻繁割裂，可能不存在一條源節點到目的節點的鏈路，而傳統的TCP/IP路由協議無法滿足DTN消息的傳遞要求。因此提高消息的投遞率、降低消息的傳輸時延、減少網絡負載率及資源消耗，成為當前DTN研究領域的主要研究課題[3-5]。目前DTN路由方案中一類為隨機性路由方案，主要以Epidemic/Random spray方式[9]為代表；另一類是基于確定性的路由方案，例如基于樹的方式[6]、修正的最短路徑方法[7]、時空路由[8]等。

在實際環境如移動車載自組網絡中，車必然沿著道路行走，只有在十字路口(或掉頭)才會改變其移動方向。在動物遷徙過程中，受遷徙路線及群體的影響，會沿著道路或水源行走，只有在道路或水流分叉的時候才改變遷徙方向。因此節點移動方向的變化頻率相對要低很多，具有更好的穩定性及可靠性，也避免了使用GPS時刻采集地理位置信息帶來的資源消耗問題。另一方面，在多數DTN應用場景中，網絡節點往往是沿著某一方向移動一段距離或者一段時間之后才會改變移動方向[9-11]，因此，利用中繼節點一段距離之內仍然會按照原來既定方向移動的特點，可以定向引導和控制消息副本的傳輸方向。徐吉興等[1]提出了MDCE路由算法，由于MDCE路由算法在網絡負載率、丟包數仍然很高，會演化為泛洪形式的傳播，這與L-C Epidemic、Epidemic情況類似，將會導致與以上兩者同樣高的負載率和緩存空間占用率，并且在實際的DTN環境中，由于條件及資源的限制及DTN特點，很難擁有六個或更多的節點。

因此，本文將對MDCE路由算法做進一步改進，使得在投遞率不變或變化很小的情況下降低丟包數及網絡負載率。

1 MDCE路由協議分析

1.1 MDCE下一跳節點的選擇

在基于地理位置的DTN路由算法中，任意時刻節點只能獲取一跳以內鄰居節點的信息，且頻繁獲取位置信息會增加額外的資源消耗，同時還無法獲取目的節點的信息。為了避免錯過消息傳遞成功的機會，路由選取應更為慎重。MDCE是基于移動方向的中繼節點選擇算法，避免了節點過分依賴GPS的信息，利用節點移動的方向來提高消息傳遞的準確性。由于目的節點可能存在于源節點周圍的任何方向。MDCE算法以當前節點Ni的移動方向作為參考方向，選擇了左、左前、右、右前、左后和右后六個方向的相鄰節點來復制消息副本，如圖1所示。

圖1 移動方向選擇

1.2 MDCE路由算法描述

DTN中節點的緩存有限，有的節點只愿意轉發與自己有社會關系的節點數據包[12]。因此MDCE路由算法使用消息經過的跳數C(M)、已存活時間L(M)、能夠存活時間TTL作為優先級參考的參考標準。使用H(M)、T(M)分別表示跳數和已存活時間對優先級的作用大小；使用UP(M)表示最終的優先級。設消息經過跳數的門限值HOPthreshold=?log2NC」,NC為網絡中的節點數量。H(M)、T(M)、UP(M)計算公式如下：

(1)

(2)

UP(M)=1-H(M)×β-T(M)×(1-β)

(3)

結合移動方向的選擇和緩存管理策略，MDCE路由協議算法描述詳見文獻[1]。

1.3 存在問題

由于目的節點方向的不確定性，MDCE路由算法為了提高投遞率，導致網絡副本過多，存在如下問題：

1) 在實際的DTN環境中，由于環境條件及資源的限制，鄰居節點很難達到六個及以上。

2) 當消息生存周期過長(超過30分鐘)時，因為消息副本過多，高負載率降低了網絡性能使得消息大量丟棄，喪失了最佳的消息傳遞機會，導致投遞率快速下降。

3) 由于中繼節點過多，將會轉化為Epidemic路由算法，導致負載率高、緩存占用率高、消息副本過多。

4) 選擇的下一跳中繼節點的移動方向與當前節點去過方向相反，會使得消息副本又向傳遞來的方向傳遞，而來向區域已經存在較密集的消息副本，增加了網絡負載率、緩存占用率。

2 MDCE算法改進

2.1 改進MDCE算法下一跳節點的選擇

針對MDCE路由算法的4個缺點，應該適當減少網絡中的消息副本，避免或減少緩存與其他資源爭奪，保證消息副本有足夠的存活時間，減少消息副本被丟棄的機率，從多個節點中選擇兩個方向作為節點的下一跳中繼節點進行消息復制，同時不刪除當前節點消息，即消息沿三個方向進行傳輸，如圖2所示。

圖2 下一跳節點選擇

這樣既減少了節點的計算量，又避免了MDCE路由協議轉換為純粹的Epidemic路由協議，解決了上述前3個缺點。在資源的利用上，也可以減少能量的消耗。由圖2可知，若A為消息生成節點則按照三個方向進行傳輸，若為消息攜帶者(中繼節點)，則按兩個方向進行傳輸，且自身消息副本不刪除，如果少于或等于兩個節點，則進行消息復制，同時源節點也保留消息副本。在節點的運動的過程中，可以通過原來位置S和現在的節點A，計算出下一跳中繼節點傳輸的移動方向，把消息往AB、AC方向傳輸，通過計算可得出左前和右前的夾角范圍分別是60°～180°和180°～300°。通過該角度范圍，使更加偏向于AB、AC方向上的節點復制消息，即面向區域A1、A2方向傳遞，效果如圖3所示，避免了前述的問題4。

圖3 中繼節點選擇示意圖

2.2 MDCE改進路由算法描述

結合移動方向的選擇和緩存管理策略，MDCE改進后路由算法描述如下：

輸出：下一跳中繼節點列表。

for (源節點或中繼節點的相鄰節點1 toN)計算MD和MDi的夾角

If (R1

if (relay List中已經存在一個該方向上的中繼節點)

選擇一個具有更小值的節點

return NodeList

If(node[i]==soursenode)

else if(nextnode[i]!=null&&i>3)

從NodeList節點列表中選擇節點向三個方向進行傳遞，刪除消息副本

else If(nextnode[i]!=null&&i<3)

從NodeList相鄰節點列表中選擇節點進行消息復制，且不刪除消息副本

If(node[i]==destination node)

廣播送達消息

If(當前為中繼節點)

else if(nextnode[i]!=null&&i>3)

從NodeList列表中選擇復制消息給相鄰節點

else If(nextnode[i]!=null&&i<3)

從相鄰節點列表中選擇節點進行消息復制，且不刪除消息副本

NextNode列表NodeList選擇方法

這樣，中繼節點在密度稀疏或稠密的情況下都能更好地控制消息冗余。對于改進后的算法，可以通過數學模型得到其覆蓋示意圖，如圖4所示，其中S為源節點。

圖4 消息模擬傳遞示意圖

對于緩存管理策略，本文采用與MDCE算法相同的管理方式。

3 實 驗

本節使用ONE基于隨機路點模型對MDCE和改進后的MDCE進行仿真實驗。四個衡量指標分別為投遞率、負載率、平均跳數和丟包數，測試兩個算法在緩存空間、消息生存周期(TTL)、消息生成時間間隔的路由性能表現。容延網絡仿真平臺仿真參數如表1所示。

表1 隨機路點模型仿真參數

3.1 節點緩存空間

圖5是兩種算法的路由性能隨節點緩存空間大小的變化情況。可以看出，改進后的MDCE算法在負載率、丟包數上都取得了一定優勢，在投遞率上相差不大，在可以接受的范圍，雖然平均跳數次于原來的MDCE算法，但在資源受限的條件下改進后的MDCE算法是比較有效的。

圖5 算法性能與緩存空間關系圖

可以得出，在隨機路點模型中，當資源嚴重受限，網絡能力嚴重不足，緩存資源不是捉襟見肘時，改進后的MDCE算法可以代替MDCE算法。此時，改進后的MDCE路由算法在保持較高投遞率的同時，降低了負載率及消息丟包數，性能更加出色。

3.2 消息生存周期

圖6是兩種路由算法性能隨消息生存時間的變化情況。在不同的生存時間里，對比原MDCE算法，改進后的MDCE在負載率、丟包數上有所降低，擁有一定優勢。當消息生存時間大于40 min時，改進后的MDCE明顯優于傳統MDCE算法。

圖6 算法性能與生存周期關系圖

可以得出，在隨機路點模型中，當消息的生存時間較長時，改進后的MDCE算法的消息傳遞率比原MDCE算法高，且改進后的MDCE算法負載率更低，丟包數更少。在DTN特殊環境中，改進后的MDCE算法路由性能更優，性能更穩定，雖然在跳數上略高，但在投遞率、丟包數、網絡負載率上更有優勢。

3.3 生成消息的時間間隔

圖7是兩種路由算法性能隨著消息生成時間間隔的變化情況。改進后的MDCE在網絡負載率、丟包數上仍然具有優勢，平均路數相差不大，進一步驗證了改進后的MDCE在性能上的優勢及有效性。

圖7 算法性能與消息生成間隔相關圖

可以得出，在隨機路點模型的容遲網絡環境中，改進后的MDCE算法適用于比原MDCE算法條件更為受限的情況，具有更好的性能。

4 結 語

因為DTN網絡的特殊性，無法捕獲DTN網絡的全局拓撲結構(即使捕獲到也可能是無效的拓撲結構)，所以DTN網絡的評價標準主要有消息傳遞的可靠性、丟包數、網絡負載率。在資源受限的DTN網絡中，行之有效的資源管理策略可以提高資源的利用率，減少丟包數，提高傳遞效率，并降低網絡負載率，減少資源消耗，提高整體路由性能。本文使用ONE對改進后的MDCE路由算法進行了仿真實驗，結果表明，在基于隨機路點模型的網絡環境中，改進后的MDCE算法除了在平均跳數上略差于MDCE算法，但其在取得較高消息投遞率的同時，網絡負載率及丟包數都優于原來的MDCE算法。下一步研究將利用統計相關知識，針對DTN節點的活動頻率不同等特點，提出更加高效的DTN路由算法，并在具體的容遲網絡中進行實際的部署應用。