容遲網(wǎng)絡(luò)中基于節(jié)點(diǎn)間相遇概率的路由算法

李廣強(qiáng) 何佳

摘? 要： 容遲網(wǎng)絡(luò)DTN （Delay Tolerant Network）是物聯(lián)網(wǎng)中的一種新型的計算機(jī)網(wǎng)絡(luò)，該網(wǎng)絡(luò)中的源節(jié)點(diǎn)和目的節(jié)點(diǎn)之間可能并不總是存在完整的端到端的通信鏈路。DTN間歇連接的特點(diǎn)對設(shè)計有效路由算法是巨大的挑戰(zhàn)。文章在原有Epidemic和Prophet路由算法的基礎(chǔ)上，提出了一種改進(jìn)的基于節(jié)點(diǎn)間相遇概率的路由算法RAEPBN（Routing Algorithm Based on Encounter Probability Between Nodes），并詳細(xì)介紹了該算法的路由建立過程。仿真結(jié)果表明，與現(xiàn)有的Epidemic和Prophet路由算法相比，RAEPBN在投遞率、平均時延和網(wǎng)絡(luò)開銷上的性能均最優(yōu)。

關(guān)鍵詞： 容遲網(wǎng)絡(luò); 路由算法; 節(jié)點(diǎn)間相遇概率; ACK確認(rèn)機(jī)制

中圖分類號：TP312????????? 文獻(xiàn)標(biāo)識碼：A???? 文章編號：1006-8228（2021）01-33-04

A routing algorithm based on the probability of encounter between nodes

in delay-tolerant network

Li Guangqiang， He Jia

（Air Force EarlyWarning Academy， Wuhan， Hubei 430019， China）

Abstract： Delay Tolerant Network （DTN） is a new type of computer network in the Internet of Things. In DTN， a complete end-to-end communication link between the source node and the destination node may not always be available. The intermittent connection characteristics of DTN make the design of an effective routing algorithm face a huge challenge. Based on the original Epidemic and Prophet routing algorithms， this paper proposes an improved routing algorithm based on the encounter probability between nodes RAEPBN （Routing Algorithm Based on Encounter Probability Between Nodes）， and introduces the routing establishment process of the algorithm in detail. The simulation results show that RAEPBN has the best performance in delivery rate， average delay， and network overhead， compared with the existing Epidemic and Prophet routing algorithms.

Key words： Delay Tolerant Network; routing algorithm; encounter probability between nodes; acknowledge mechanism

0 引言

DTN（Delay Tolerant Network）[1-2]是一種源節(jié)點(diǎn)和目的節(jié)點(diǎn)間不存在穩(wěn)定端到端的通信鏈路，利用節(jié)點(diǎn)移動帶來的相遇機(jī)會進(jìn)行通信的自組織網(wǎng)絡(luò)。DTN間歇連接的特征使其可以在挑戰(zhàn)性的環(huán)境中使用，這一特征也導(dǎo)致了較長的傳輸延遲，難以符合TCP/IP網(wǎng)絡(luò)的基本要求[3]。因此，傳統(tǒng)的路由算法，即使是MANET路由協(xié)議也不能應(yīng)用于容遲網(wǎng)絡(luò)中[4]。

為了支持間歇連接，DTN路由采用“存儲—攜帶—轉(zhuǎn)發(fā)”方式把消息發(fā)送到目的節(jié)點(diǎn)[5]。如果節(jié)點(diǎn)由于間斷連接而不能立即發(fā)送消息，則需要將消息存儲在緩沖區(qū)中，直到節(jié)點(diǎn)有機(jī)會將消息轉(zhuǎn)發(fā)出去。近年來，國內(nèi)外研究學(xué)者提出了許多路由算法以解決DTN的固有特性。Epidemic算法是一種典型的基于洪泛策略的路由算法，該算法將消息發(fā)送給所有的相遇節(jié)點(diǎn)。在緩存資源充足的場景中，Epidemic[6]的路由算法性能最好，然而現(xiàn)實(shí)的應(yīng)用場景中，節(jié)點(diǎn)的緩存資源都是有限的。Prophet[7]路由算法利用相遇歷史和傳遞性提出了一種基于概率估計的路由算法，節(jié)點(diǎn)僅將消息轉(zhuǎn)發(fā)給與目的節(jié)點(diǎn)相遇概率高的鄰居節(jié)點(diǎn)。為了減小網(wǎng)絡(luò)開銷，Spray and wait[8]路由算法對源節(jié)點(diǎn)消息的最大拷貝數(shù)進(jìn)行了限制。盡管以往的研究表明DTN的各種舉措都具有良好的性能，但它們也存在一些缺點(diǎn)。首先，Epidemic路由算法基于泛洪的策略非常浪費(fèi)網(wǎng)絡(luò)資源。其次，Prophet在同一時刻將消息轉(zhuǎn)發(fā)給多個與目的節(jié)點(diǎn)相遇概率更高的鄰居節(jié)點(diǎn)，這將引起消息在一些局部范圍內(nèi)存在多個冗余的消息副本，增加了不必要的網(wǎng)絡(luò)開銷。Spray and wait已經(jīng)被證明是一個有效的方法，但該方法沒有將已經(jīng)成功傳遞到目的節(jié)點(diǎn)的消息進(jìn)行刪除，可能會導(dǎo)致網(wǎng)絡(luò)中的一些節(jié)點(diǎn)仍然試圖繼續(xù)將這些被成功傳遞的消息投遞到目的節(jié)點(diǎn)。

為了解決上述問題，文本提出了一種基于節(jié)點(diǎn)間相遇概率的路由算法RAEPBN（An Routing Algorithm Based on Encounter Probability Between Nodes）。當(dāng)節(jié)點(diǎn)在同一時刻有多個連接機(jī)會時，RAEPBN算法將比較所有相遇節(jié)點(diǎn)與目的節(jié)點(diǎn)間的相遇概率，僅將消息轉(zhuǎn)發(fā)給與目的節(jié)點(diǎn)相遇概率最高的鄰居節(jié)點(diǎn)，從而避免消息在某一局部區(qū)域內(nèi)存在過多的冗余副本，以減少不必要的網(wǎng)絡(luò)開銷。增加了ACK確認(rèn)機(jī)制，即當(dāng)某個消息被成功投遞到目的節(jié)點(diǎn)后，RAEPBN算法會生成對應(yīng)的ACK確認(rèn)消息，并將該確認(rèn)消息傳播到網(wǎng)絡(luò)中，其他節(jié)點(diǎn)在收到此ACK確認(rèn)消息之后，檢查自身的緩存中是否存在這條已經(jīng)被成功投遞的消息，如果存在則將此條已經(jīng)被成功投遞的消息從緩存中刪除，以避免不必要的消息轉(zhuǎn)發(fā)。

1 基于節(jié)點(diǎn)間相遇概率的路由算法

1.1 網(wǎng)絡(luò)模型

假設(shè)網(wǎng)絡(luò)中一共有n個節(jié)點(diǎn)，G=（V，E）表示網(wǎng)絡(luò)拓?fù)鋱D，V={vi |1≤i≤n}表示網(wǎng)絡(luò)中節(jié)點(diǎn)的集合，E是圖G上的邊的集合。網(wǎng)絡(luò)中的每個消息mk都有一個唯一標(biāo)識符（mk.ID）。當(dāng)一個節(jié)點(diǎn)生成一個新的消息mk時，將預(yù)先分配其對應(yīng)的目標(biāo)節(jié)點(diǎn)vk和生存周期。如果消息的生存周期過期，該消息將被丟棄。節(jié)點(diǎn)vi有一個匯總矢量屬性SVi，用來記錄節(jié)點(diǎn)vi緩存中待投遞的消息。當(dāng)節(jié)點(diǎn)vi與其他節(jié)點(diǎn)相遇時，節(jié)點(diǎn)vi選擇與目的節(jié)點(diǎn)相遇概率最大的鄰居節(jié)點(diǎn)vl作為中繼節(jié)點(diǎn)。如圖1所示，節(jié)點(diǎn)vi將匯總矢量SVi發(fā)送給與目的節(jié)點(diǎn)相遇概率最大的鄰居節(jié)點(diǎn)vl，[SVl]表示與目的節(jié)點(diǎn)相遇概率最大的鄰居節(jié)點(diǎn)vl緩存中沒有的消息，鄰居節(jié)點(diǎn)vl執(zhí)行SVi與[SVl]間的邏輯與運(yùn)算得到匯總矢量SV，即存儲在節(jié)點(diǎn)vi緩存中且節(jié)點(diǎn)vl沒有的消息。然后鄰居節(jié)點(diǎn)vl向節(jié)點(diǎn)vi請求這些消息，最終節(jié)點(diǎn)vi將節(jié)點(diǎn)vl請求的消息發(fā)送給vl。

1.2 相遇概率的計算與更新

網(wǎng)絡(luò)環(huán)境是相對不可預(yù)測性的，但人的移動性不是完全隨機(jī)的，如果節(jié)點(diǎn)vi過去經(jīng)常遇到節(jié)點(diǎn)vj，未來節(jié)點(diǎn)vi與節(jié)點(diǎn)vj很可能還會再次遇到。本文利用Prophet路由算法定義的相遇概率來反映任意兩個節(jié)點(diǎn)間的相遇概率，如果兩個節(jié)點(diǎn)經(jīng)常相遇，那么就可以認(rèn)為他們之間成功投遞消息的概率更高。當(dāng)兩個節(jié)點(diǎn)相遇時，根據(jù)相遇概率決定是否將消息轉(zhuǎn)發(fā)給另一個節(jié)點(diǎn)。相遇概率的計算包括以下三個部分。

⑴ 更新：若兩個節(jié)點(diǎn)經(jīng)常相遇，那么他們未來再次相遇的可能性更高。因此，當(dāng)節(jié)點(diǎn)vi遇到節(jié)點(diǎn)vj時，相遇概率應(yīng)按照⑴進(jìn)行更新。其中，Pinit為初始化常數(shù)，[P（i，j）old]表示此次更新前節(jié)點(diǎn)vi與節(jié)點(diǎn)vj的相遇概率。

[P（i，j）=P（i，j）old+（1-P（i，j）old）×Pinit]?? ⑴

⑵ 衰退：如果一對節(jié)點(diǎn)在一段時間后沒有相遇，那么未來它們彼此之間成功投遞消息的可能性較小，因此節(jié)點(diǎn)間的相遇概率必須有衰退的過程。公式⑵給出了相遇概率是如何衰退的。其中，[γ∈][0，1]為老化常數(shù)，k為自相遇概率最后一次衰退以來所經(jīng)過的時間單位數(shù)。

[P（i，j）=P（i，j）old?γk]? ⑵

⑶ 傳遞：如果節(jié)點(diǎn)vi經(jīng)常遇到節(jié)點(diǎn)vk，而節(jié)點(diǎn)vk又和節(jié)點(diǎn)vj經(jīng)常相遇，那么節(jié)點(diǎn)vk可能是一個較好的中繼節(jié)點(diǎn)。因此，節(jié)點(diǎn)間的相遇概率也具有傳遞性，公式⑶給出了傳遞性是如何影響節(jié)點(diǎn)間的相遇概率的。其中，β是一個常數(shù)，其決定了傳遞性對節(jié)點(diǎn)間相遇概率的影響比重。

[P（i，j）=P（i，j）old+（1-P（i，j）old）?P（i，k）?P（k，j）?β]?? ⑶

1.3 RAEPBN路由算法

由于大多數(shù)現(xiàn)有的路由算法在同一時刻可能會將消息轉(zhuǎn)發(fā)給多個鄰居節(jié)點(diǎn)，而這多個鄰居節(jié)點(diǎn)的位置相距較近，這將導(dǎo)致消息在某些局部范圍內(nèi)存在過多的冗余副本，增加了不必要的網(wǎng)絡(luò)開銷。因此本小節(jié)提出了一種改進(jìn)的基于節(jié)點(diǎn)間相遇概率的路由算法RAEPBN。在RAEPBN算法中，當(dāng)攜帶消息的節(jié)點(diǎn)在某一時刻有多個連接機(jī)會時，該節(jié)點(diǎn)僅將消息轉(zhuǎn)發(fā)給與目的節(jié)點(diǎn)相遇概率最高的鄰居節(jié)點(diǎn)，從而降低了路由算法的網(wǎng)絡(luò)開銷。其次，為了提高緩存資源的利用率，RAEPBN路由算法利用ACK確認(rèn)機(jī)制通知網(wǎng)絡(luò)中的節(jié)點(diǎn)刪除已經(jīng)被成功投遞到目的節(jié)點(diǎn)的消息。具體地說，每個節(jié)點(diǎn)有一個ACKmesID列表屬性，當(dāng)某個節(jié)點(diǎn)將消息成功投遞到目的節(jié)點(diǎn)后，該節(jié)點(diǎn)會將消息ID添加到自身的ACKmesID列表中，當(dāng)任意兩個節(jié)點(diǎn)相遇時，它們互相交換彼此的ACKmesID列表，并將對方ACKmesID列表中包含的而自身ACKmesID列表中沒有的消息ID加入到自身的ACKmesID列表中，若節(jié)點(diǎn)緩存中存在消息的ID在ACKmesID列表中，則從緩存中將這些消息刪除。

當(dāng)某個節(jié)點(diǎn)vi在某一時刻有多個鄰居時，節(jié)點(diǎn)vi遍歷緩存中的所有消息m，并獲取消息m的目的節(jié)點(diǎn)vd。然后遍歷節(jié)點(diǎn)vi的所有連接機(jī)會con，并獲取連接的鄰居節(jié)點(diǎn)vj，同時，更新節(jié)點(diǎn)vi與節(jié)點(diǎn)vj間的相遇概率P（i，j），節(jié)點(diǎn)vi和節(jié)點(diǎn)vj交換彼此的ACKmesID列表， 然后基于ACKmesID列表將自身緩存中已經(jīng)被成功投遞的消息刪除。若節(jié)點(diǎn)vj是消息m的目的節(jié)點(diǎn)，則節(jié)點(diǎn)vi將消息直接轉(zhuǎn)發(fā)給鄰居節(jié)點(diǎn)vj;否則篩選出與目的節(jié)點(diǎn)vd相遇概率更高的鄰居節(jié)點(diǎn)，并將消息轉(zhuǎn)發(fā)給該鄰居節(jié)點(diǎn)。

2 仿真實(shí)驗(yàn)分析

2.1 仿真設(shè)置

本文在開源的ONE仿真平臺上，對提出的RAEPBN路由算法進(jìn)行了仿真，并將該算法與Epidemi和Prophet路由算法在不同的緩存和生存周期下進(jìn)行了對比。詳細(xì)的參數(shù)設(shè)置如表1所示。

2.2 仿真實(shí)驗(yàn)結(jié)果分析

2.2.1 不同緩存下各算法的性能比較

圖2對比了Epidemic、Prophet和RAEPBN三種路由算法的性能。從圖2（a）中可以看出，RAEPBN路由算法的投遞率最高。這是因?yàn)镽AEPBN路由算法在有多個連接機(jī)會時僅將消息轉(zhuǎn)發(fā)給與目的節(jié)點(diǎn)相遇概率最高的鄰居節(jié)點(diǎn)，避免了消息在某一局部區(qū)域內(nèi)存在過多的冗余副本。圖2（a）顯示各算法的投遞率都隨著緩存的增加而增加，這是由于節(jié)點(diǎn)的緩存越大，所能攜帶的消息也就越多，由于緩存資源有限導(dǎo)致消息被丟棄的情況逐漸緩解。圖2（b）展示了各算法的平均時延。從圖2可以看出，RAEPBN算法的平均時延總體上最優(yōu)，且當(dāng)緩存越大時，RAEPBN算法在平均時延上的優(yōu)勢越明顯。從圖2（c）中可以看出RAEPBN路由算法的網(wǎng)絡(luò)開銷最低。這是因?yàn)樵赗AEPBN路由算法中，節(jié)點(diǎn)將消息成功投遞到目的節(jié)點(diǎn)后，會生成對應(yīng)的ACK確認(rèn)消息，并將ACK確認(rèn)消息傳播到網(wǎng)絡(luò)中，其他收到該確認(rèn)消息的節(jié)點(diǎn)會從緩存中將此條被成功投遞到目的節(jié)點(diǎn)的消息刪除。

2.2.2 不同TTL下各算法的路由性能

圖3對比了Epidemic、Prophet和RAEPBN三種路由算法在不同生存周期下的投遞率。從圖3（a）中可以觀察到RAEPBN路由算法的投遞率最高。當(dāng)生存周期大于200分鐘時，Epidemic和Prophet路由算法的投遞率都呈現(xiàn)下降的趨勢，這是因?yàn)楫?dāng)生存周期增加，消息能在節(jié)點(diǎn)的緩存中存儲更長的時間，但是節(jié)點(diǎn)的緩存是有限的，許多消息將會由于節(jié)點(diǎn)緩存溢出而被丟棄。從圖3（b）中可以看出RAEPBN路由算法的平均時延最低。圖3（c）顯示了RAEPBN路由算法的網(wǎng)絡(luò)開銷最低，且隨著生存周期的增加，RAEPBN路由算法在網(wǎng)絡(luò)開銷上的優(yōu)勢更明顯。

3 結(jié)束語

本文提出了一種基于節(jié)點(diǎn)間相遇概率的路由算法RAEPBN。在RAEPBN算法中，若某個節(jié)點(diǎn)在同一時刻有多個連接機(jī)會時，該節(jié)點(diǎn)僅選擇與目的節(jié)點(diǎn)相遇概率最高的鄰居節(jié)點(diǎn)作為中繼節(jié)點(diǎn)，而不是將消息轉(zhuǎn)發(fā)給所有與目的節(jié)點(diǎn)相遇的鄰居節(jié)點(diǎn)，以避免消息在某一局部區(qū)域內(nèi)存在過多的冗余副本。此外，為了降低網(wǎng)絡(luò)開銷，增加了ACK確認(rèn)機(jī)制，若某條消息被成功投遞到目的節(jié)點(diǎn)，RAEPBN算法就生成對應(yīng)的ACK確認(rèn)消息以通知網(wǎng)絡(luò)中的其他節(jié)點(diǎn)刪除此條已經(jīng)被成功投遞的消息，從而避免了不必要的消息副本的轉(zhuǎn)發(fā)。由于節(jié)點(diǎn)的緩存資源是有限的，未來我們將進(jìn)一步改進(jìn)ACK確認(rèn)消息的轉(zhuǎn)發(fā)方式，以進(jìn)一步提高路由算法的性能。并且搭建一個真實(shí)的DTN仿真環(huán)境，以進(jìn)一步驗(yàn)證所提出的路由算法的性能。

參考文獻(xiàn)（References）：

[1] Rosas E，Garay F，Hidalgo N.Context-aware self-adaptive

routing for delay tolerant network in disaster scenarios[J]. Ad Hoc Networks，2020.102：102095

[2] Rashidi L， Entezari-Maleki R ， Chatzopoulos D， et al.

Performance Evaluation of Epidemic Content Retrieval in DTNs With Restricted Mobility[J].IEEE Transactions on Network and Service Management，2019：701-714

[3] Spyropoulos T， Rais R N B， Turletti T， et al. Routing for

disruption tolerant networks： taxonomy and design[J]. Wireless networks，2010.16（8）：2349-2370

[4] Boukerche A， Turgut B， Aydin N， et al. Routing protocols

in ad hoc networks： A survey[J]. Computer networks， 2011.55（13）：3032-3080

[5] Zhang Z. Routing in intermittently connected mobile ad hoc

networks and delay tolerant networks： overview and challenges[J].IEEE Communications Surveys & Tutorials，2006.8（1）：24-37

[6] A. Vahdat and D. Becker， Epidemic routing for partially-

connected adhoc networks， Technical Report CS-2000-06，Duke University，2000.

[7] Lindgren A， Doria A， Schelén O. Probabilistic routing in

intermittently connected networks[J]. ACM SIGMOBILE mobile computing and communications review，2003.7（3）：19-20

[8] Spyropoulos T， Psounis K， Raghavendra C S. Spray and

wait： an efficient routing scheme for intermittently connected mobile networks[C]//Proceedings of the 2005 ACM SIGCOMM workshop on Delay-tolerant networking，2005：252-259

收稿日期：2020-08-14

作者簡介：李廣強(qiáng)（1978-），男，山西太谷人，碩士研究生，講師，主要研究方向：模擬訓(xùn)練仿真建模分析與研究。

通訊作者：何佳（1991-），女，湖北孝感人，碩士研究生，助教，主要研究方向：模擬訓(xùn)練仿真建模分析與研究。