楊萬鑫 汪學(xué)明 夏紅紅

1(貴州大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 貴州 貴陽 550025) 2(凱里學(xué)院大數(shù)據(jù)工程學(xué)院 貴州 凱里 556011)

0 引 言

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

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

因此，本文將對MDCE路由算法做進(jìn)一步改進(jìn)，使得在投遞率不變或變化很小的情況下降低丟包數(shù)及網(wǎng)絡(luò)負(fù)載率。

1 MDCE路由協(xié)議分析

1.1 MDCE下一跳節(jié)點(diǎn)的選擇

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

圖1 移動方向選擇

1.2 MDCE路由算法描述

DTN中節(jié)點(diǎn)的緩存有限，有的節(jié)點(diǎn)只愿意轉(zhuǎn)發(fā)與自己有社會關(guān)系的節(jié)點(diǎn)數(shù)據(jù)包[12]。因此MDCE路由算法使用消息經(jīng)過的跳數(shù)C(M)、已存活時(shí)間L(M)、能夠存活時(shí)間TTL作為優(yōu)先級參考的參考標(biāo)準(zhǔn)。使用H(M)、T(M)分別表示跳數(shù)和已存活時(shí)間對優(yōu)先級的作用大小；使用UP(M)表示最終的優(yōu)先級。設(shè)消息經(jīng)過跳數(shù)的門限值HOPthreshold=?log2NC」,NC為網(wǎng)絡(luò)中的節(jié)點(diǎn)數(shù)量。H(M)、T(M)、UP(M)計(jì)算公式如下：

(1)

(2)

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

(3)

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

1.3 存在問題

由于目的節(jié)點(diǎn)方向的不確定性，MDCE路由算法為了提高投遞率，導(dǎo)致網(wǎng)絡(luò)副本過多，存在如下問題：

1) 在實(shí)際的DTN環(huán)境中，由于環(huán)境條件及資源的限制，鄰居節(jié)點(diǎn)很難達(dá)到六個及以上。

2) 當(dāng)消息生存周期過長(超過30分鐘)時(shí)，因?yàn)橄⒏北具^多，高負(fù)載率降低了網(wǎng)絡(luò)性能使得消息大量丟棄，喪失了最佳的消息傳遞機(jī)會，導(dǎo)致投遞率快速下降。

3) 由于中繼節(jié)點(diǎn)過多，將會轉(zhuǎn)化為Epidemic路由算法，導(dǎo)致負(fù)載率高、緩存占用率高、消息副本過多。

4) 選擇的下一跳中繼節(jié)點(diǎn)的移動方向與當(dāng)前節(jié)點(diǎn)去過方向相反，會使得消息副本又向傳遞來的方向傳遞，而來向區(qū)域已經(jīng)存在較密集的消息副本，增加了網(wǎng)絡(luò)負(fù)載率、緩存占用率。

2 MDCE算法改進(jìn)

2.1 改進(jìn)MDCE算法下一跳節(jié)點(diǎn)的選擇

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

圖2 下一跳節(jié)點(diǎn)選擇

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

圖3 中繼節(jié)點(diǎn)選擇示意圖

2.2 MDCE改進(jìn)路由算法描述

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

輸出：下一跳中繼節(jié)點(diǎn)列表。

for (源節(jié)點(diǎn)或中繼節(jié)點(diǎn)的相鄰節(jié)點(diǎn)1 toN)計(jì)算MD和MDi的夾角

If (R1

if (relay List中已經(jīng)存在一個該方向上的中繼節(jié)點(diǎn))

選擇一個具有更小值的節(jié)點(diǎn)

return NodeList

If(node[i]==soursenode)

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

從NodeList節(jié)點(diǎn)列表中選擇節(jié)點(diǎn)向三個方向進(jìn)行傳遞，刪除消息副本

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

從NodeList相鄰節(jié)點(diǎn)列表中選擇節(jié)點(diǎn)進(jìn)行消息復(fù)制，且不刪除消息副本

If(node[i]==destination node)

廣播送達(dá)消息

If(當(dāng)前為中繼節(jié)點(diǎn))

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

從NodeList列表中選擇復(fù)制消息給相鄰節(jié)點(diǎn)

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

從相鄰節(jié)點(diǎn)列表中選擇節(jié)點(diǎn)進(jìn)行消息復(fù)制，且不刪除消息副本

NextNode列表NodeList選擇方法

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

圖4 消息模擬傳遞示意圖

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

3 實(shí) 驗(yàn)

本節(jié)使用ONE基于隨機(jī)路點(diǎn)模型對MDCE和改進(jìn)后的MDCE進(jìn)行仿真實(shí)驗(yàn)。四個衡量指標(biāo)分別為投遞率、負(fù)載率、平均跳數(shù)和丟包數(shù)，測試兩個算法在緩存空間、消息生存周期(TTL)、消息生成時(shí)間間隔的路由性能表現(xiàn)。容延網(wǎng)絡(luò)仿真平臺仿真參數(shù)如表1所示。

表1 隨機(jī)路點(diǎn)模型仿真參數(shù)

3.1 節(jié)點(diǎn)緩存空間

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

圖5 算法性能與緩存空間關(guān)系圖

可以得出，在隨機(jī)路點(diǎn)模型中，當(dāng)資源嚴(yán)重受限，網(wǎng)絡(luò)能力嚴(yán)重不足，緩存資源不是捉襟見肘時(shí)，改進(jìn)后的MDCE算法可以代替MDCE算法。此時(shí)，改進(jìn)后的MDCE路由算法在保持較高投遞率的同時(shí)，降低了負(fù)載率及消息丟包數(shù)，性能更加出色。

3.2 消息生存周期

圖6是兩種路由算法性能隨消息生存時(shí)間的變化情況。在不同的生存時(shí)間里，對比原MDCE算法，改進(jìn)后的MDCE在負(fù)載率、丟包數(shù)上有所降低，擁有一定優(yōu)勢。當(dāng)消息生存時(shí)間大于40 min時(shí)，改進(jìn)后的MDCE明顯優(yōu)于傳統(tǒng)MDCE算法。

圖6 算法性能與生存周期關(guān)系圖

可以得出，在隨機(jī)路點(diǎn)模型中，當(dāng)消息的生存時(shí)間較長時(shí)，改進(jìn)后的MDCE算法的消息傳遞率比原MDCE算法高，且改進(jìn)后的MDCE算法負(fù)載率更低，丟包數(shù)更少。在DTN特殊環(huán)境中，改進(jìn)后的MDCE算法路由性能更優(yōu)，性能更穩(wěn)定，雖然在跳數(shù)上略高，但在投遞率、丟包數(shù)、網(wǎng)絡(luò)負(fù)載率上更有優(yōu)勢。

3.3 生成消息的時(shí)間間隔

圖7是兩種路由算法性能隨著消息生成時(shí)間間隔的變化情況。改進(jìn)后的MDCE在網(wǎng)絡(luò)負(fù)載率、丟包數(shù)上仍然具有優(yōu)勢，平均路數(shù)相差不大，進(jìn)一步驗(yàn)證了改進(jìn)后的MDCE在性能上的優(yōu)勢及有效性。

圖7 算法性能與消息生成間隔相關(guān)圖

可以得出，在隨機(jī)路點(diǎn)模型的容遲網(wǎng)絡(luò)環(huán)境中，改進(jìn)后的MDCE算法適用于比原MDCE算法條件更為受限的情況，具有更好的性能。

4 結(jié) 語

因?yàn)镈TN網(wǎng)絡(luò)的特殊性，無法捕獲DTN網(wǎng)絡(luò)的全局拓?fù)浣Y(jié)構(gòu)(即使捕獲到也可能是無效的拓?fù)浣Y(jié)構(gòu))，所以DTN網(wǎng)絡(luò)的評價(jià)標(biāo)準(zhǔn)主要有消息傳遞的可靠性、丟包數(shù)、網(wǎng)絡(luò)負(fù)載率。在資源受限的DTN網(wǎng)絡(luò)中，行之有效的資源管理策略可以提高資源的利用率，減少丟包數(shù)，提高傳遞效率，并降低網(wǎng)絡(luò)負(fù)載率，減少資源消耗，提高整體路由性能。本文使用ONE對改進(jìn)后的MDCE路由算法進(jìn)行了仿真實(shí)驗(yàn)，結(jié)果表明，在基于隨機(jī)路點(diǎn)模型的網(wǎng)絡(luò)環(huán)境中，改進(jìn)后的MDCE算法除了在平均跳數(shù)上略差于MDCE算法，但其在取得較高消息投遞率的同時(shí)，網(wǎng)絡(luò)負(fù)載率及丟包數(shù)都優(yōu)于原來的MDCE算法。下一步研究將利用統(tǒng)計(jì)相關(guān)知識，針對DTN節(jié)點(diǎn)的活動頻率不同等特點(diǎn)，提出更加高效的DTN路由算法，并在具體的容遲網(wǎng)絡(luò)中進(jìn)行實(shí)際的部署應(yīng)用。