ERC2：具有擁塞控制策略的DTN傳染路由方法

譚靜 董程鳳 王慧強 王賀哲 馮光升 呂宏武 袁泉 陳詩軍

摘 要：針對延遲容忍網絡（DTN）拓撲結構動態變化和節點存儲空間有限的問題，提出一種具有擁塞控制策略的DTN傳染路由（ERC2）方法。該方法基于一種動態存儲狀態模型（DSSM），節點可通過感知網絡狀況動態調整節點半擁塞狀態的門限降低網絡發生擁塞的可能性，增加ACK索引以及消息管理隊列，使節點存儲狀態隨著網絡負載的隨機變化而動態更新并主動刪除冗余包，并根據不同擁塞狀態結合傳染路由和Prophet路由的優點選擇單一或混合模式進行消息轉發，從而達到預防、避免、解除擁塞的目的，實現節點自適應緩存管理以及網絡的動態擁塞控制。在模擬器ONE上采用Working Day Movement模型進行仿真，其中與Prophet相比，ERC2方法在消息遞交率上提高66.18%，平均時延降低48.36%，轉發次數提高22.83%。仿真結果表明，在擁塞程度不同的場景中，ERC2與Epidemic、Prophet路由算法相比具有更好的網絡性能。

關鍵詞：延遲容忍網絡;傳染路由;擁塞控制;動態存儲;緩存管理

中圖分類號： TP393.08

文獻標志碼：A

Abstract： Delay Tolerant Network （DTN） has characteristics of dynamic topology changes and limited node storage space. A DTN Epidemic Routing with Congestion Control strategy （ERC2） method was proposed. The method was based on a Dynamic Storage State Model （DSSM）. According to sensing network conditions， the threshold of nodes semi-congested state was dynamically adjusted to reduce the possibility of network congestion by nodes. The ACK index and message management queue were added to make node storage state change randomly with network load， dynamically update and actively delete redundant packages. Single or mixed mode was selected for message forwarding according to different congestion states combining with advantages of Epidemic and Prophet routing， so as to achieve the purpose of preventing， avoiding and canceling congestion， realizing adaptive buffer management of nodes and dynamically controlling congestion of network. Simulations were conducted on the ONE（Opportunistic Networking Environment） platform using Working Day Movement （WDM） model. In the simulation， ERC2 was 66.18% higher than Prophet in message delivery rate. The average latency of ERC2 was decreased by 48.36%， and the forwarding number was increased by 22.83%. The simulation results show that ERC2 has better network performance than Epidemic and Prophet routing algorithms in scenarios with different levels of congestion.

Key words： Delay Tolerant Network （DTN）; epidemic routing; congestion control; dynamic storage; buffer management

0 引言

延遲容忍網絡（Delay Tolerant Network， DTN）[1]架構體系具有時延高、間歇性連接、資源受限等特點，被廣泛應用于環境質量監控、室內地圖生成、交通擁塞預報和災后現場救援[2]等各類場景。在DTN中，節點通過“存儲攜帶轉發”的路由模式進行消息傳輸[3]。為了保證消息的遞交率及延遲等網絡性能，網絡通常采用多副本路由進行消息轉發，當網絡中存在大量同一消息副本時，將會導致節點的有限緩存資源被迅速耗盡，最終造成節點緩存溢出[4]。

考慮到傳染路由協議在DTN研究中的重要意義，目前已存在大量基于傳染路由協議的DTN路由策略。例如，文獻[5]考慮節點的移動方向和速度，將移動軌跡匹配度高的節點分為一組，不同組的節點利用擺渡節點實現消息的傳送。文獻[6]針對口袋交換網絡（Pocket Switched Network， PSN）中節點的社會屬性，利用節點活躍度、橋接中心度、社區關系等實現中繼節點選擇。文獻[7]中提出了一種基于節點空間信息和傳遞性的多副本路由策略，主要針對已有研究成果缺乏對節點空間信息的考慮。其中，消息的路由選擇不僅考慮了節點連接的傳遞性還考慮了節點的停留時間。

文獻[8]中提出了一種換此處“換分布式路由”的描述對嗎？分布式路由。該策略主要針對利用消息多跳轉發擴展覆蓋范圍的網絡，能夠有效地控制消息的拷貝和轉發。文獻[9]中提出了一種基于社會感知的路由算法。其中，設計了基于轉發代價的節點中繼能力，并利用區域特性研究如何選擇下一跳節點。文獻[10]中提出一種滿足不同網絡模型的需求的路由策略，即為不同類型的網絡拓撲提供不同的轉發機制以此來確保最小的傳輸時延和最大的消息交付率。在文獻[11]中，在網絡中建立基站，充當網絡控制中心及數據收集中心，并在網絡中分發一定數量的令牌，使得節點獲得令牌才可以轉發消息。在文獻[12]中，對中繼節點到目的節點的時延和跳數進行評估，路由過程中選出到目的節點時延相對較少、跳數相對較少的節點作為中繼節點。

綜上所述，對于DTN傳染路由中擁塞控制的研究，國內外研究人員已經取得大量的成果。大多數路由算法主要利用節點的移動速度、位置方向、分布密度等自然屬性或者節點間相遇的時間、相遇次數等社會屬性來設計消息轉發策略;但是，已有研究成果并沒有考慮節點發生擁塞的情況，同時，節點不斷移動，很難獲得這些網絡的準確分布狀態，導致網絡性能出現極低、極高等不穩定現象，因此，本文在傳染路由的思想基礎上提出一種改進機制面向擁塞控制策略的傳染路由（Epidemic Routing with Congestion Control strategy， ERC2）方法。在網絡鏈路間斷性連接、網絡準確分布狀態難獲取的條件下，通過每個節點根據自身擁塞狀況動態調整路由轉發策略，結合對節點緩存進行有效管理，從而實現節點在消息傳輸的擁塞控制過程，有效地改善網絡各種性能。

1 相關工作

1.1 Epidemic路由協議

Epidemic路由協議是由Vahdat等[13]提出的一種典型的多副本路由算法，又稱為傳染路由，或者蔓延路由。傳染路由通過采用病毒感染式的傳遞方式，向接觸的每一個節點復制消息，其能夠將消息的成功遞交率最大化、端到端的傳染時延最小化，因此，在過去的研究過程中，傳染路由被廣泛采用并作為其他路由算法性能上的比較標準;然而傳染路由的實現容易導致大量的資源浪費，并且沒有考慮緩存管理的問題。消息的調度順序基于簡單的先進先出隊列管理模型，這使得傳染路由的實際性能具有十分廣闊的優化空間。

1.2 Prophet路由協議

Prophet[14]路由協議是一種基于節點歷史信息的概率路由轉發協議，在假設網絡中的節點時非完全隨機性移動的情況下，對節點的移動趨勢進行概率性的預測，從而通過利用節點活動的重復性對網絡的緩存和資源進行有效的控制。

Prophet協議中節點的相遇概率，其計算過程主要包括更新、衰減、傳遞三個部分。詳細計算過程如下。

1）更新。當A、B節點相遇時，更新A節點到B節點的遞交預測值：

其中： f（a，b）代表A節點到B節點的預測遞交概率; f（a，b）old代表更新前的節點A、B之間的預測遞交概率; f（a，b）init是一個初始常量，并且f（a，b）init∈（0，1）。

2）衰減。如果節點A、B有一段時間沒有相遇，則A、B節點的遞交預測概率就會衰減。

其中：k代表從上一次相遇到此次相遇經歷了k個時間單位;λ代表衰減參數，是一個初始常量。

3）傳遞。如果節點A、B經常通信，同時節點B、C又頻繁相遇，那么C就是A轉發消息過程中的一個潛在的優良中繼節點。

其中β表示常數因子，它們和f（a，b）init都表示一個初始常量。

由上述可知：式（1）用來不斷更新兩個節點相遇概率;式（2）用來計算兩個節點長時間沒有相遇而導致節點間的遞交預測概率衰減值;式（3）用來計算兩個不直接相遇的節點遞交預測概率。

1.3 多屬性丟包策略

多屬性丟包策略利用消息的預測傳輸概率與消息副本數、消息大小及消息剩余生存時間計算消息的保留權重，優先丟棄保留權值最小的消息。該策略可以有效均衡分配存儲資源，緩解擁塞節點的存儲負擔及提高消息的成功遞交率。

保留權值的計算如下：

其中：Q表示消息的保留權值; f表示轉發消息到目的節點的預測傳輸概率，利用式（1）、（2）和（3）計算;t表示消息的剩余生存時間;s表示消息的大小;r表示消息的冗余數量。消息的預測傳輸概率越大，剩余生存時間越長，消息大小越小，消息的冗余數量越少，則保留權值越大;相反，消息的預測傳輸概率越小，剩余生存時間越短，消息大小越大，消息的冗余數量越多，則保留權值越小。

綜上，Epidemic路由協議可以提高消息遞交率，但因無限制地創建消息副本，消耗大量節點緩存，造成網絡性能急劇下降。Prophet路由協議可選擇性地復制消息，在一定程度上避免生成地傳輸效率的副本避免生成過多副本此句不通順，請作相應調整，但時間成本和能耗過高。本文提出一種具有擁塞控制策略的DTN傳染路由方法，結合兩種路由協議的優勢，并引入多屬性丟包策略，在網絡資源、能量有限的應用場景中，進一步提升網絡整體性能。

2 ERC2路由協議

考慮到網絡資源有限和網絡拓撲結構動態變化的特點，ERC2路由協議主要由動態存儲狀態模型和路由模型兩部分構成。動態存儲狀態模型通過網絡狀況動態調整節點半擁塞狀態的門限，預防網絡擁塞的發生。路由模型包括ACK確認反饋機制、消息隊列管理以及（α， β）-Epidemic算法，使節點存儲狀態隨著網絡負載的隨機變化而動態更新并主動刪除冗余包。下面對ERC2路由協議進行詳細的介紹。

2.1 動態存儲狀態模型

在DTN中，節點發生擁塞是一個逐漸的過程。為了控制網絡擁塞的發生，依據節點緩存利用率劃分三種狀態：正常態（Normal State， NS）、半擁塞狀態（Semi-Congestion State， SCS）、擁塞狀態（Congestion State， CS）。在劃分節點存儲狀態時，需要考慮節點緩存利用率及消息轉發速度。在任意時刻，如果節點緩存利用率達到半擁塞門限值，并且在一段較小的時間里節點緩存利用率的最小值不低于半擁塞門限，則節點由NS轉換為SCS。同理，如果節點緩存利用率達到擁塞門限值，同時在一段較小的時間里節點的緩存利用率都大于擁塞門限，則節點由SCS轉換為CS。節點的存儲狀態劃分如下：

State（n）=NS， f（t，t+Δτ1）<αSCS，f（t，t+Δτ1）≥αCS，f（t，t+Δτ2）≥β （5）

其中：n表示DTN任意節點;State（n）表示節點n的存儲狀態，它有三個可能值NS、SCS、CS;t表示任意時刻;Δτ1表示半擁塞持續的時間;α表示半擁塞門限;Δτ2此處遺漏了一個變量，請補充表示擁塞持續的時間; β表示擁塞門限; f（t1，t2）表示在任意兩個時刻t1、t2節點的緩存利用率的最小值。

當DTN拓撲結構隨機動態變化時，為提升網絡性能的穩定性，本文提出一種動態存儲狀態模型（Dynamic Storage State Model， DSSM）。根據網絡負載情況決定α的取值，根據網絡負載情況變換路由策略，增加多屬性丟包策略，從而實現動態感知網絡狀態以及網絡整體性能穩定。

圖1表示在消息轉發過程中，當節點出現丟包現象即節點發生擁塞時，就把半擁塞門限α更新為當前緩存利用率的一半，并將當前緩存利用率記為擁塞門限β。將α值設為擁塞窗口的一半的目的是使節點感知網絡狀態，及時調整以適應網絡的變化。

圖1中，在t1時刻，節點出現擁塞，執行多屬性丟包策略。t1+Δt1時刻節點的擁塞門限記為β1，半擁塞門限記為α1，且α1=β1/2。同理，在t2時刻，節點出現擁塞，執行多屬性丟包策略。Δt2時間后節點的擁塞門限記為β2，半擁塞門限記為α2，且α2=β2/2，其中Δt1、Δt2是兩個極小的值。

2.2 ERC2路由模型

考慮到節點資源受限及拓撲結構隨機動態變化的問題，本文提出了基于動態存儲模型多屬性丟包策略的擁塞控制傳染路由（ERC2）方法。ERC2路由通過確認反饋機制對已傳送到目的節點的消息進行管理，并根據ACK索引刪除冗余副本。當節點緩存空間不足時，為了具有足夠的空間存儲新的消息，節點采用多屬性丟包策略優先在消息緩存隊列中刪除保留權值較小的消息。當對消息進行轉發時采用（α， β）-Epidemic算法作為路由轉發策略，有效地對節點擁塞進行控制。

2.2.1 確認反饋機制

當消息到達目的節點后，網絡應立即停止對消息的轉發及復制，并刪除該消息副本。確認反饋機制犧牲少量存儲空間來存儲ACK索引表，在消息到達目的節點后立即向發送節點反饋ACK消息，接收到確認反饋消息的節點根據索引的消息ID將成功交付的消息冗余副本刪除。

在DTN節點中建立ACK索引表，其中每條ACK索引由成功交付的消息ID、目的節點、剩余生命周期（Time To Live， TTL）組成，并且它們是相互獨立、唯一的。DTN節點的ACK索引表初始值為空，每接收到一個確認反饋消息，就生成一條對應的索引信息。ACK索引格式如圖2所示。

由于節點緩存有限，為了減少網絡開銷及資源競爭，索引表中每一條ACK索引都設有一個剩余TTL值，當剩余生命周期值遞減為0時，該條ACK索引就會自動消失，從而保證了ACK索引表的簡潔性及高效性。此外，兩節點相遇交換ACK索引表，一方面避免了冗余消息副本造成的資源浪費，另一方面也減輕了確認反饋信息在網絡中廣播所導致的網絡負載。

2.2.2 消息管理隊列

當節點緩存空間不足時，為了具有足夠的空間存儲新的消息，節點采用多屬性丟包策略優先刪除保留權值較小的消息;然而節點頻繁重復計算消息的保留權值同樣會消耗大量的網絡資源，為此本文提出節點緩存中消息隊列管理。其消息隊列按照保留權值排列，越靠近消息轉發端（或稱為隊頭）其權值越大;反之，越靠近消息丟棄端（或稱為隊尾）其權值越小。有新消息到來時，首先根據式（4）計算其保留權值，然后根據保留權值從大到小將其插入到緩存隊列中。節點與其他節點建立通信連接后，從隊頭開始傳輸消息。節點存儲空間不足時，從隊尾開始丟棄消息。節點中所有的消息都只計算一次保留權值，從而使得路由性能更佳。圖3為節點中消息隊列示意圖。

2.2.3 （α， β）-Epidemic的相關定義描述

為了解決DTN負載不均衡及節點緩存受限的問題，本文提出（α， β）-Epidemic，不僅能夠提高路由性能，還可以有效地控制網絡擁塞。假設一個節點產生數據包，需要被傳送到目的節點。當攜帶數據包的源節點遇到一個半擁塞門限和擁塞門限的值都為零的節點，中繼節點是目的節點并接收數據包副本，這種路由策略被稱為Direct路由。在ERC2路由模型中不會出現α=0， β=0的情形。當中繼節點的半擁塞門限和擁塞門限的值都為1時，采用Epidemic路由協議，接收一個數據包副本的概率為1。DTN中的消息負載是動態變化的，節點的緩存利用率是動態變化的，因此針對0<α， β=1和0<α， β<1的情形采用多副本路由策略（α， β）-Epidemic。該策略從接收方考慮是否接收，其中節點接收消息的意愿度為P。在DTN中，不存在半擁塞門限值為0而擁塞門限值為1的節點，因此，不存在α=0，0<β<1的節點轉發消息的過程。ERC2路由模型包含的多種消息轉發策略描述如下：

1）直接交付路由策略Direct Delivery（α=β=0）：源節點直接將消息轉發給目的節點，無需任何節點的中繼轉發。

2）洪泛路由策略Epidemic（α=β=1）：每一個節點轉發消息副本給中繼節點，同時接收消息副本的概率為1。

3）多副本路由策略（α， β）-Epidemic（0<α， β≤1）：節點根據半擁塞門限α來動態調整路由策略，而擁塞門限β決定α的取值。

在ERC2路由模型中，當α=β=1時，（α， β）-Epidemic路由算法退化為傳統的傳染路由Epidemic，此時路由算法無擁塞控制機制，網絡性能也會被降低，因此，本文只討論0<α， β≤1的情況。

（α， β）-Epidemic路由策略的基本思想是在Epidemic協議的基礎上，根據節點緩存利用率將轉發過程劃分成兩個階段，即洪泛轉發和概率轉發;同時，結合動態節點存儲模型，增加ACK索引以及保留權值，使得節點存儲狀態隨著網絡負載的隨機變化而動態更新并主動刪除冗余包，從而達到預防、避免、解除擁塞的目的。

假設DTN節點a與b相遇并建立通信連接，節點a、b相互交換彼此的ACK索引表。首先，根據確認反饋刪除交付成功的消息并獲得待轉發消息集合;其次，動態更新緩存利用率以及半擁塞、擁塞門限。現在節點a向b傳送消息，節點b根據其存儲狀態從而選擇路由策略。

由上述可知，（α， β）-Epidemic路由策略包括洪泛轉發、概率轉發、擁塞處理三個階段，其路由算法的詳細流程如圖4所示。

由圖4可知，路由算法的轉發過程主要包括以下幾點。

1）洪泛轉發階段。

此階段利用典型的Epidemic路由算法，其中節點b的緩存利用率低于半擁塞門限，此時節點b無限制接收傳輸的消息。緩存利用率低于半擁塞門限，說明節點的緩存資源充足，洪泛轉發可以提高消息遞交率。

2）概率轉發階段。

概率轉發階段中，節點b的緩存利用率高于半擁塞門限，且并未發生丟包情況。其中，如果節點b的緩存利用率大于半擁塞門限值，說明此時節點存儲資源不充足，其對于相遇節點a發送的消息并不是不問出處地全部接收。針對某一消息分別計算節點a、b的意愿度，并比較大小：若節點b的意愿度大于a，則拒絕接收此消息;若節點b的意愿度高于a，則接收此消息。

3）擁塞處理階段。

如果節點b出現丟包情況，則進入擁塞狀態，同時停止接收消息。節點進入擁塞處理階段，優先丟棄緩存隊列隊尾的消息，并持續該操作直到節點擁塞解除。

4 仿真實驗與分析

4.1 性能指標

為了驗證分析ERC2的有效性，本文從消息遞交率、平均傳輸時延、平均轉發次數及網絡開銷率四個方面比較ERC2算法與經典算法Prophet和Spray and Wait[15]等路由算法的網絡性能，指標定義如下。

1）消息遞交率。

消息遞交率=（1.0×成功遞交的消息總數/網絡中總的消息個數1.0×在此處不適合吧，遞交率應該為百分數吧，所以此式是否應該是“成功遞交的消息總數/網絡中總的消息個數×100%”，或者刪除“1.0×”，改為“成功遞交的消息總數/網絡中總的消息個數”？以哪個為準？請明確。另，下面的2）～4）的指標作相應修改。

2）傳輸時延。

3）平均轉發次數。

4）網絡負載率。

負載率=（1.0×延遲消息個數-傳輸成功消息個數）/傳輸成功消息個數1.0×在此處不合適，根據運算符號的先后順序，起碼在“延遲消息個數-傳輸成功消息個數”外面加上括號吧。另外，在4.3.1、4.3.2、4.3.3節中，一直都是提到了三個指標，沒有“網絡負載率”這個指標，但是在正文文字中卻又提到了這個指標，唯獨沒有子圖，此處的指標說明是否應該刪除？要特別注意修改的連貫性。

4.2 仿真場景設置

本文運用ONE（Opportunistic Networking Environment）仿真工具對實驗場景進行模擬仿真。該采用Working Day Movement（WDM）[16]模型描述節點移動。仿真場景大小為1000m×8000m，由120個節點、40個地點組成。節點分為兩組，根據兩組節點的特征分別進行設置。第一組為汽車節點，速度為7～10m/s，停車等待時間為20～40s，傳輸速率為1.25MB/s，傳輸半徑為1000m，節點20個;第二組為行人節點，速度為1～1.5m/s，傳輸速率為0.25MB/s，傳輸半徑為20m，節點100個。默認仿真參數如表1所示。

為保證ERC2能夠適應不同擁塞程度的網絡環境，具體的網絡環境設置如下：

無擁塞或輕度擁塞網絡[17] 網絡仿真時間為12h，網絡總共生成400個消息，節點生成消息的速率為每秒20個，每個消息的生命周期為10h。

中度擁塞網絡[17] 網絡仿真時間為18h，網絡總共生成2000個消息，節點生成消息的速率為每秒40個，每個消息的生命周期為15h。

重度擁塞網絡[17] 網絡仿真時間為20h，網絡總共生成10000個消息，節點生成消息的速率為每秒100個，每個消息的生命周期為18h。

4.3 仿真結果與分析

4.3.1 無擁塞或輕度擁塞網絡下性能分析

在無擁塞或輕度擁塞網絡環境下，分別對Epidemic、Prophet路由算法和具有擁塞控制的傳染路由ERC2進行實驗仿真，仿真結果圖5（a）～（c）分別比較了網絡無擁塞或輕度擁塞時各個算法的3項性能指標。

圖5（a）描述遞交率變化情況。其中，Epidemic路由的遞交率最高，ERC2路由的遞交率次之，Prophet路由的遞交率最低。其原因主要是Epidemic路由采用多個消息副本并行轉發，增加了節點間的相遇機會。在Prophet路由中，節點的投遞預測值限制了網絡中消息的冗余數量，從而減少降低了消息成功遞交到目的節點的概率。隨著仿真時間的增加，三種路由方法的遞交率均緩慢上升，其原因是ERC2針對節點緩存利用率采用了（α， β）-Epidemic路由算法，第一階段采用Epidemic算法，第二階段采用基于節點意愿度的概率路由，因此，遞交率會逐漸增加，表明了ERC2路由算法具有良好的實用性。

圖5（b）評估了各個算法的平均傳輸時延變化情況。Epidemic算法端到端傳輸時延最低，原因是它最大化利用了網絡資源。不同于Epidemic，Prophet通過捕獲節點間相遇的歷史信息，并利用節點的投遞預測值將消息轉發給預測值更高的節點，因此Prophet路由算法的傳輸時延最高。對于ERC2，當仿真時間為0～5hks此處的時間單位為ks，表示什么意思？是10的3次方秒嗎？請明確，這個表達不夠規范。回復：ks 修改為 小時時其傳輸時延與Epidemic算法基本一致;當仿真時間大于5ksh時，略高于Epidemic算法，但仍然大幅度低于Prophet路由算法，這是因為大于5ksh之后，ERC2采用基于概率的轉發路由，平均時延略有增加。

圖5（c）比較了各個算法的平均轉發次數。平均轉發次數越低通常表明路由中繼選擇根據準確平均轉發次數越低通常表明路由選擇中繼節點時越準確此句不通順，請調整。Epidemic的平均轉發次數最高，Prophet的平均轉發次數最低，ERC2的平均轉發次數處于兩者之間，而且隨著仿真時間的增加，ERC2的變化曲線逐漸接近Prophet，這意味著ERC2路由選擇的準確性、高效性綜合性能都優于Epidemic和Prophet算法。這句的描述不太合適，“準確性、高效性”并不都是最優，請修改語句描述，改為“綜合性能”合適嗎？

綜合圖5來看，ERC2能夠在提高路由性能與降低傳輸成本之間取得更好的平衡。從消息遞交率和傳輸時延考慮，ERC2優于Prophet算法;從平均轉發次數和網絡負載率圖5～7中，是否均少了子圖“（d） 網絡負載率”，4.1節中有該性能的說明，需作相應調整。若補充了子圖（d），請提供矢量圖來比較，ERC2明顯低于Epidemic算法，因此其路由性能更加穩定，使用價值更高。

4.3.2 中度擁塞網絡下性能分析

在中度擁塞網絡環境下，分別對Epidemic、Prophet路由算法和具有擁塞控制的傳染路由ERC2進行實驗仿真，仿真結果圖6比較了網絡中度擁塞時各個算法的3項性能指標。

圖6（a）描述了網絡中度擁塞時Epidemic、Prophet和ERC2的消息遞交率。其中，Epidemic算法仍然保持最高的遞交率，但是當仿真時間大于6ksh時，它的遞交率不斷下降。相比圖5（a），中度擁塞網絡的消息生成時間間隔變小，消息生存時間變久，而Epidemic路由算法無限制地復制消息使得整個網絡會快速生存大量的消息，甚至發生擁塞。此時，ERC2和Prophet算法都保持穩定的路由性能。

圖6（b）比較了網絡中度擁塞時各個路由算法的平均傳輸時延，從圖中可以看出，Prophet算法的傳輸時延最高，Epidemic算法的傳輸時延隨著仿真時間的增加而增長，而ERC2卻保持著較低的傳輸時延，這驗證了ERC2在提高路由性能上的高效性。

圖6（c）比較了Epidemic、Prophet和ERC2的平均轉發次數。可以看出，隨著仿真時間增加，ERC2的平均轉發次數基本接近于Prophet，這表明了ERC2在網絡中度擁塞環境下依然可以保持中繼選擇的高效性;而Epidemic算法的平均轉發次數隨著仿真時間的增加而增大，這是因為消息的生命周期更長，致使消息的轉發次數更多。圖6（d）評估了Epidemic、Prophet和ERC2的網絡負載率未見圖6（d）。隨著仿真時間的增加，它們的負載率都在上升，但是ERC2的增長趨勢明顯弱于Epidemic。分析其中的原因是ERC2通過設置半擁塞門限有效地控制了冗余消息副本的數量，減少了節點緩存資源浪費，因而ERC2的負載率明顯低于Epidemic。

綜合圖6可知，消息的生成間隔和生存周期會直接影響各個算法的路由性能。其中，消息的生成時間間隔直接反映了消息的生成速率。Epidemic的消息遞交率隨著消息生存周期的延長而下降，并伴隨著很高的負載率，所以Epidemic比較適用于消息生存周期較短的網絡。消息生存的時間越長，Prophet的消息遞交率也會逐漸增加并高于Epidemic，同時還會保持較低的負載率。ERC2的適用范圍受消息生成周期長短的影響較弱，它可以始終保持較高的遞交率和相對較低的負載率，具有更好的通用性。

4.3.3 重度擁塞網絡下性能分析

在重度擁塞網絡環境下，分別對Epidemic、Prophet路由算法和具有擁塞控制的傳染路由ERC2進行實驗仿真，仿真結果（如圖7）比較了網絡重度擁塞時各個算法的3項性能指標。

圖7（a）描述了網絡重度擁塞時Epidemic、Prophet算法和ERC2的消息遞交率。當仿真時間足夠長時，Epidemic的消息遞交率逐漸降低，Prophet的消息遞交率保持在一個穩定的范圍內，而ERC2的消息遞交率最高。這是由于在資源受限的DTN中，Epidemic缺乏擁塞控制機制，同時與Prophet相比，ERC2的優化控制策略選擇較優較少的中繼節點。ERC2路由具有較優的節點緩存策略，從而其消息遞交率更高。

圖7（b）描述了網絡重度擁塞時Epidemic、Prophet算法和ERC2的傳輸時延變化情況。由于消息生成速率變大，固定時間內生成的消息副本數不斷增加，從而導致網絡更易發生擁塞而無法正常工作，因此無擁塞控制機制的Epidemic的消息平均傳輸時延迅速上升;同時由于ERC2的路由選擇機制比Prophet更加嚴格，資源利用率更加高效，故ERC2相比Epidemic、Prophet的網絡性能更佳、更具普適性。

圖7（c）評估了網絡重度擁塞時Epidemic、Prophet算法和ERC2的轉發次數。從圖中可以看出，Epidemic的平均轉發次數不斷升高，ERC2能夠將平均轉發次數維持在一個較低的水平，并且ERC2總體上的路由性能要優于Epidemic，但比Prophet性能較差。

綜合圖7來看，導致這些路由性能差異的關鍵原因是，當消息生成時間間隔減小時，加之消息生存周期變長，整個網絡會在短時間內生成大量消息。對于節點緩存資源受限的DTN，缺乏冗余副本數控制機制的Epidemic會浪費大量網絡資源。Prophet是基于Epidemic的概率轉發路由，雖然在一定程度上控制了副本數量，但其性能比ERC2較差。ERC2利用節點意愿度和預測投遞值選擇更優的中繼節點，優化了節點緩存管理，從而有效地避免了消息副本的擴散，降低了網絡負載。

5 結語

在資源受限及拓撲結構動態變化的DTN中，為了提高消息遞交率、降低傳輸時延，本文提出一種具有擁塞控制策略的DTN傳染路由方法。該方法首先基于一種動態存儲模型DSSM，通過動態調整節點擁塞窗口閾值適應節點資源受限的情形，根據節點空間利用率控制消息的拷貝次數避免網絡擁塞;其次，綜合考慮節點擁塞控制機制和路由轉發算法，提出ERC2路由協議，該模型采用確認反饋機制對成功轉發的消息進行刪除，并引入消息管理隊列和多屬性丟包策略對產生擁塞的節點進行報文的舍棄，在此基礎上利用（α， β）-Epidemic算法對消息進行轉發，進一步有效地控制網絡擁塞。最后實驗結果表明，ERC2在遞交率、平均傳輸時延、平均轉發次數3個重要性能指標上相比Epidemic、Prophet都表現良好，能有效地減輕網絡負載，實現了具有主動擁塞控制的傳染路由協議。

參考文獻 （References）

[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 Computer Communications. New York： ACM， 2003：27-34.

[2] 王挺，張玉梅.一種基于DTN的震后救援路由新策略[J].計算機工程與應用，2017，53（22）：71-76.（WANG T， ZHANG Y M. Routing strategy for post earthquake rescue based on DTN[J]. Computer Engineering and Applications， 2017， 53（22）：71-76.）

[3] 王賀哲，王慧強，朱金美，等.OCIGM：面向DTN路由的優化控制信息生成方法[J].北京郵電大學學報，2017，40（1）：79-83.（WANG H Z， WANG H Q， ZHU J M， et al. OCIGM： an optimized control information generation method for DTN routing[J]. Journal of Beijing University of Posts and Telecommunications， 2017， 40（1）：79-83.）

[4] SIDERA A， TOUMPIS S. Wireless mobile DTN routing with the extended minimum estimated expected delay protocol [J]. Ad Hoc Networks， 2016， 42（C）：47-60.

[5] 王恩，楊永健，李蒞.基于動態半馬爾可夫路徑搜索模型的DTN分簇路由方法[J].計算機學報，2015，38（3）：483-499.（WANG E， YANG Y J， LI L. A clustering routing method based on semi-Markov process and path-finding strategy in DTN[J]. Chinese Journal of Computers， 2015， 38（3）：483-499.）

[6] 曹玖新，陳高君，楊婧，等.基于社會屬性的PSN消息路由算法[J].通信學報，2015，36（5）：13-22.（CAO J X， CHEN G J， YANG J， et al. Social-based routing in pocket switched networks[J]. Journal on Communications， 2015， 36（5）：13-22.）

[7] ZHANG L， CAI Z， LU J， et al. Mobility-aware routing in delay tolerant networks[J]. Personal & Ubiquitous Computing， 2015， 19（7）：1-13.

[8] NISHIYAMA H， TAKAHASHI A， KATO N， et al. Dynamic replication and forwarding control based on node surroundings in cooperative delay-tolerant networks[J]. IEEE Transactions on Parallel & Distributed Systems， 2015， 26（10）：2711-2719.

[9] WEI K， GUO S， ZENG D， et al. Exploiting small world properties for message forwarding in delay tolerant networks[J]. IEEE Transactions on Computers， 2015， 64（10）：2809-2818.

[10] MERGENCI C， KORPEOGLU I. Routing in delay tolerant net-works with periodic connections[J]. EURASIP Journal on Wireless Communications & Networking， 2015， 2015（1）：1-19.

[11] WANG H Z， LV H W， WANG H Q， et al. DCAR： DTN congestion avoidance routing algorithm based on tokens in an urban environment [J]. Journal of Sensors， 2017， 2017： Article ID 6523076.

[12] WANG H Z， FENG G S， WANG H Q， et al. RABP： Delay/disruption tolerant network routing and buffer management algorithm based on weight[J]. International Journal of Distributed Sensor Networks， 2018， 14（3）：155014771875787.

[13] VAHDAT A. Epidemic routing for partially-connected Ad Hoc networks[D]. Durham， NC： Duke University， 2000： 1-14.

[14] LINDGREN A， DORIA A， SCHELEN O. Probabilistic routing in intermittently connected networks [J]. Mobile Computing and Communications Review， 2003， 7（3）：19-26.

[15] 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 International Conference on the Applications， Technologies， Architectures， and Protocols for Computer Communication. New York： ACM， 2005：252-259.

[16] EKMAN F， KARVO J. Working day movement model[C]// Proceedings of the 1st ACM Special Interest Group on Mobility of Systems， Users， Data， and Computing. New York： ACM， 2008：33-40.

[17] 黃曉軍.DTN擁塞控制機制及其應用研究[D].長沙：湖南大學，2013：33-37.（HUANG X J. Research on congestion control mechanism for DTN and its application [D]. Changsha： Hunan University， 2013：33-37.）