摘? 要：為了解決傳統(tǒng)延遲容忍網(wǎng)絡(luò)（Delay Tolerant Networks， DTN）路由算法在災(zāi)后復(fù)雜場景中數(shù)據(jù)投遞率低、延遲高、路由開銷大等問題，提出適用于災(zāi)后場景的DTN路由算法。該算法分析災(zāi)后場景中節(jié)點(diǎn)的特點(diǎn)，根據(jù)節(jié)點(diǎn)的規(guī)律性移動(dòng)軌跡，計(jì)算每個(gè)節(jié)點(diǎn)到已知目的地的路徑成本。再綜合考慮節(jié)點(diǎn)的剩余緩存，使用熵權(quán)法平衡上述參數(shù)，計(jì)算副本分配數(shù)量。文中使用模擬器仿真了該方案，并將結(jié)果與以前的DTN路由算法進(jìn)行了比較。評估結(jié)果表明，與以前的方法相比，文中方法減少了每條消息的資源開銷，同時(shí)能夠保持良好的傳遞率。

關(guān)鍵詞：中繼節(jié)點(diǎn)；DTN；路由算法；應(yīng)急通信

中圖分類號：TP391.4；TN929.5 文獻(xiàn)標(biāo)識碼：A 文章編號：2096-4706（2023）09-0086-04

Abstract： In order to solve the problems of low data delivery rate， high latency， and high routing overhead of traditional delay tolerant network routing algorithms in complex post disaster scenarios， a DTN routing algorithm suitable for post disaster scenarios is proposed. This algorithm analyzes the characteristics of nodes in post disaster scenarios and calculates the path cost of each node to a known destination based on its regular movement trajectory. Taking into account the remaining cache of nodes， the entropy weight method is used to balance the above parameters and calculate the number of replica allocation. The scheme is simulated by using a simulator in this paper， and the results are compared with previous DTN routing algorithms. The evaluation results show that compared with previous methods， the proposed method reduces the resource overhead of each message while maintaining a good delivery rate.

Keywords： relay node; DTN; routing algorithm; emergency communication

0? 引? 言

網(wǎng)絡(luò)中的所有節(jié)點(diǎn)設(shè)備均支持TCP/IP協(xié)議，網(wǎng)絡(luò)中的安全機(jī)制可以保證消息的不丟包。然而近些年來，由于世界各地自然災(zāi)害頻繁發(fā)生，造成了難以估量的經(jīng)濟(jì)損失以及無法抹去的傷害，并且使得許多情況無法使用TCP/IP協(xié)議。災(zāi)后恢復(fù)通信對于后期的救援工作非常重要，因?yàn)橹挥性诹私鉃?zāi)后情況的前提下，救援隊(duì)才能更好地組織救援行動(dòng)。

在實(shí)際自然環(huán)境下，由于緊急、突發(fā)情況往往是不可預(yù)測的，因此重大的災(zāi)難發(fā)生后往往會(huì)造成大范圍的電力、道路以及通信設(shè)備的損毀，同時(shí)還會(huì)出現(xiàn)通信業(yè)務(wù)需求激增等現(xiàn)象，這時(shí)便可能會(huì)出現(xiàn)災(zāi)區(qū)通信困難、網(wǎng)絡(luò)資源受限、數(shù)據(jù)傳輸擁塞，從而出現(xiàn)不能正常進(jìn)行通信等問題。因此，災(zāi)后應(yīng)急通信網(wǎng)絡(luò)如何有效地建立是一個(gè)具有重要研究意義的方向。

1? 相關(guān)技術(shù)

延遲容忍網(wǎng)絡(luò)（Delay Tolerant Networks， DTN）是美國NASA噴氣式推進(jìn)實(shí)驗(yàn)室為解決星際互聯(lián)網(wǎng)（Interplanetary Internet）提出的一種網(wǎng)絡(luò)體系。在應(yīng)急通信網(wǎng)絡(luò)場景中，由于節(jié)點(diǎn)具有移動(dòng)性，節(jié)點(diǎn)之間通信鏈路不完整，網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)動(dòng)態(tài)變化，傳統(tǒng)的TCP/IP協(xié)議無法使用，因此，通過在傳輸層和應(yīng)用層之間引入Bundle層，采用“存儲(chǔ)—攜帶—轉(zhuǎn)發(fā)”機(jī)制解決網(wǎng)絡(luò)中間歇性連接，高延遲高誤碼率等問題。對應(yīng)的網(wǎng)絡(luò)結(jié)構(gòu)如圖1所示。

容遲容斷網(wǎng)絡(luò)（Delay and Disruption Tolerant Networks， DTN）是一種適應(yīng)較高延時(shí)、頻繁中斷、異構(gòu)互聯(lián)、端到端連接不能保證的新型網(wǎng)絡(luò)體系，作為MANET和WSN的發(fā)展，在災(zāi)后場景中應(yīng)用將十分廣泛。

2? 算法過程

2.1? 路由算法

在災(zāi)后場景中實(shí)體的運(yùn)動(dòng)不是完全隨機(jī)的，災(zāi)害響應(yīng)網(wǎng)絡(luò)中存在著遞歸性。具有這樣一些規(guī)律：物資被送到避難點(diǎn)，警車按照計(jì)劃路線巡邏，消防車不斷從消防站出發(fā)，志愿者最終到達(dá)相同的避難點(diǎn)。此外，還存在許多可用于消息的靜態(tài)點(diǎn)交接。例如，避難點(diǎn)、學(xué)校、消防站和滯留在公共路線上的車輛都可以作為中繼站，將數(shù)據(jù)從一個(gè)移動(dòng)實(shí)體傳遞到下一個(gè)實(shí)體。

所以我們需要建立一個(gè)相互接觸圖，如圖2所示，其中一個(gè)頂點(diǎn)表示兩個(gè)節(jié)點(diǎn)之間的相遇。兩個(gè)頂點(diǎn)之間的邊表示兩次相遇之間的延遲。例如ij表示節(jié)點(diǎn)i和j之間的相遇。如圖2，假設(shè)節(jié)點(diǎn)i沿著一條路線行走30分鐘。節(jié)點(diǎn)在這條路線上相繼遇到j(luò)節(jié)點(diǎn)和k節(jié)點(diǎn)，大約間隔3分鐘。之后，i在遇到k之后再間隔27分鐘才會(huì)再次看到j(luò)。因此，在頂點(diǎn)ij和ik的接觸圖中存在延遲3分鐘的有向邊。在頂點(diǎn)ik和ij之間存在一個(gè)延遲27分鐘的有向邊。這種不對稱性解釋了為什么相互接觸圖中的邊是有向的。

相互接觸圖中維護(hù)的每條邊ij?ik都由兩個(gè)值的元組（δ（ij?ik）， σ2（ij?ik））進(jìn)行標(biāo)記，其中δ（ij?ik）是節(jié)點(diǎn)i從經(jīng)過節(jié)點(diǎn)j到經(jīng)過節(jié)點(diǎn)k的平均延遲，σ2（ij?ik）是對應(yīng)的延遲方差。我們將相互接觸圖中的路徑表示為：ij?w是從聯(lián)系人ij到節(jié)點(diǎn)w的路徑。由于期望的線性和在邊緣獨(dú)立的假設(shè)下，我們定義路徑延遲表示為d（ij?w），路徑方差表示為σ2（ij?w）。如果從初始聯(lián)系人到目的地有多個(gè)路徑，則將存儲(chǔ)最佳路徑的參數(shù)以用于路由目的。通常并非所有節(jié)點(diǎn)都具有相同的網(wǎng)絡(luò)視圖，因此從給定節(jié)點(diǎn)的角度定義路徑延遲和方差是有意義的。因此，我們定義di（ij?w）和σ2i（ij?w）來表示由節(jié)點(diǎn)i計(jì)算的路徑延遲和方差。

在該算法中，接觸圖中頂點(diǎn)ij處的目的地w條目包含相應(yīng)的路徑延遲di（ij?w）和方差σ2i（ij?w）。我們將這兩個(gè)值存儲(chǔ)為節(jié)點(diǎn)i到達(dá)目的地w的最佳路徑的參數(shù)。

該算法存儲(chǔ)最優(yōu)路徑的參數(shù)。因?yàn)閭鬟f概率取決于消息在途中已經(jīng)花費(fèi)了多長時(shí)間。因此，無法建立與消息參數(shù)無關(guān)的最優(yōu)路徑。相反，為了確定要在路由表中存儲(chǔ)其參數(shù)的路徑，我們提出一個(gè)與消息無關(guān)的替代路徑成本，定義為路徑延遲的第95個(gè)百分位，如式（1）：

然后鄰居按pk降序進(jìn)行排序。每個(gè)鄰居k按此順序分配Pk×L個(gè)副本，并且從L中減去這些分配。該過程繼續(xù)進(jìn)行，直到L用完或直到所有鄰居都已被考慮。

4? 仿真結(jié)果

4.1? 仿真實(shí)驗(yàn)概述

本文采用ONE（Opportunistic Network Environment）模擬器進(jìn)行仿真實(shí)驗(yàn)，該仿真模擬器是基于Java開發(fā)，適用于DTN網(wǎng)絡(luò)仿真環(huán)境的路由算法模擬，并提供數(shù)據(jù)研究分析工具。我們將本文算法（BDECS）與傳統(tǒng)路由算法Epidemic算法相比較，通過平均時(shí)延、投遞率和網(wǎng)絡(luò)開銷三個(gè)指標(biāo)進(jìn)行對比。該仿真環(huán)境中設(shè)置50～300個(gè)普通節(jié)點(diǎn)，仿真時(shí)間為72 h，所有結(jié)果均是10次仿真的平均值，默認(rèn)仿真參數(shù)如表3所示。

4.2? 仿真結(jié)果及分析

根據(jù)延遲容忍網(wǎng)絡(luò)自身的特點(diǎn)，本文選用平均時(shí)延、投遞率和網(wǎng)絡(luò)開銷三種指標(biāo)分析該算法的性能。隨著節(jié)點(diǎn)個(gè)數(shù)的增加，數(shù)據(jù)投遞率都呈現(xiàn)出緩慢上升的變化趨勢，但該算法明顯較傳統(tǒng)算法網(wǎng)絡(luò)開銷少，平均時(shí)延低。這是因?yàn)楣?jié)點(diǎn)個(gè)數(shù)增多，增加了節(jié)點(diǎn)之間的接觸，可以找到更好的中繼節(jié)點(diǎn)選擇，并且該算法考慮了節(jié)點(diǎn)的剩余緩存，從而減少了平均時(shí)延和網(wǎng)絡(luò)開銷。詳細(xì)如圖3至圖5所示。

5? 結(jié)? 論

本文使用了一種用于容錯(cuò)網(wǎng)絡(luò)的新型多副本路由協(xié)議，組建災(zāi)后場景中的通信網(wǎng)絡(luò)，其目標(biāo)是滿足災(zāi)后場景中的通信需求。本文提出了一種基于路徑成本的方法，該方法使用一種名為“接觸間延遲”的新路由度量來計(jì)算到達(dá)目的地的路徑和成本，并充分考慮了節(jié)點(diǎn)的剩余緩存，使用熵權(quán)法平衡參數(shù)，從而選擇最佳中繼節(jié)點(diǎn)。仿真結(jié)果表明，通過仿真評估不同節(jié)點(diǎn)數(shù)量對網(wǎng)絡(luò)場景的影響程度與上述映射模型得到的理論結(jié)果相一致，驗(yàn)證了該模型的有效性。

參考文獻(xiàn)：

[1] FALL K. A delay-tolerant network architecture for challenged internets [C]//Proceedings of the 2003 conference on Applications， technologies， architectures， and protocols for computer communications.New York：Association for Computing Machinery，2003：27-34.

[2] UDDIN M Y S，AHMADI H，ABDELZAHER T，et al. A Low-energy， Multi-copy Inter-contact Routing Protocol for Disaster Response Networks [C]//2009 6th Annual IEEE Communications Society Conference on Sensor， Mesh and Ad Hoc Communications and Networks.Rome：IEEE，2009：1-9.

[3] 王朕，王新華，隋敬麒.機(jī)會(huì)網(wǎng)絡(luò)模擬器ONE及其擴(kuò)展研究 [J].計(jì)算機(jī)應(yīng)用研究，2012，29（1）：272-277.

[4] 徐雙，王興偉，黃敏，等.空間延遲/中斷容忍網(wǎng)絡(luò)的接觸圖路由研究綜述 [J].軟件學(xué)報(bào)，2019，30（2）：323-345.

[5] 王海濤.應(yīng)急通信的發(fā)展現(xiàn)狀和技術(shù)手段分析 [J].中國無線電，2010（11）：49-51.

[6] FALL K，F(xiàn)ARRELL S. DTN： an architectural retrospective [J].IEEE Journal on Selected Areas in Communications，2008，26（5）：828-836.

[7] ZHANG Z Z. Routing in intermittently connected mobile ad hoc networks and delay tolerant networks： overview and challenges [J].IEEE Communications Surveys & Tutorials，2007，8（1）：24-37.

作者簡介：董建華（1998—），男，漢族，黑龍江蘭西人，碩士研究生在讀，研究方向：延遲容忍網(wǎng)絡(luò)、路由算法。