容遲網絡中基于節點間相遇概率的路由算法

李廣強 何佳

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

關鍵詞： 容遲網絡; 路由算法; 節點間相遇概率; ACK確認機制

中圖分類號：TP312????????? 文獻標識碼：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]是一種源節點和目的節點間不存在穩定端到端的通信鏈路，利用節點移動帶來的相遇機會進行通信的自組織網絡。DTN間歇連接的特征使其可以在挑戰性的環境中使用，這一特征也導致了較長的傳輸延遲，難以符合TCP/IP網絡的基本要求[3]。因此，傳統的路由算法，即使是MANET路由協議也不能應用于容遲網絡中[4]。

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

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

1 基于節點間相遇概率的路由算法

1.1 網絡模型

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

1.2 相遇概率的計算與更新

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

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

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

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

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

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

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

1.3 RAEPBN路由算法

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

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

2 仿真實驗分析

2.1 仿真設置

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

2.2 仿真實驗結果分析

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

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

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

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

3 結束語

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

參考文獻（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

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

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