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

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

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

關(guān)鍵詞：延遲容忍網(wǎng)絡(luò);傳染路由;擁塞控制;動態(tài)存儲;緩存管理

中圖分類號： TP393.08

文獻(xiàn)標(biāo)志碼：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 引言

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

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

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

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

1 相關(guān)工作

1.1 Epidemic路由協(xié)議

Epidemic路由協(xié)議是由Vahdat等[13]提出的一種典型的多副本路由算法，又稱為傳染路由，或者蔓延路由。傳染路由通過采用病毒感染式的傳遞方式，向接觸的每一個節(jié)點(diǎn)復(fù)制消息，其能夠?qū)⑾⒌某晒f交率最大化、端到端的傳染時延最小化，因此，在過去的研究過程中，傳染路由被廣泛采用并作為其他路由算法性能上的比較標(biāo)準(zhǔn);然而傳染路由的實(shí)現(xiàn)容易導(dǎo)致大量的資源浪費(fèi)，并且沒有考慮緩存管理的問題。消息的調(diào)度順序基于簡單的先進(jìn)先出隊(duì)列管理模型，這使得傳染路由的實(shí)際性能具有十分廣闊的優(yōu)化空間。

1.2 Prophet路由協(xié)議

Prophet[14]路由協(xié)議是一種基于節(jié)點(diǎn)歷史信息的概率路由轉(zhuǎn)發(fā)協(xié)議，在假設(shè)網(wǎng)絡(luò)中的節(jié)點(diǎn)時非完全隨機(jī)性移動的情況下，對節(jié)點(diǎn)的移動趨勢進(jìn)行概率性的預(yù)測，從而通過利用節(jié)點(diǎn)活動的重復(fù)性對網(wǎng)絡(luò)的緩存和資源進(jìn)行有效的控制。

Prophet協(xié)議中節(jié)點(diǎn)的相遇概率，其計(jì)算過程主要包括更新、衰減、傳遞三個部分。詳細(xì)計(jì)算過程如下。

1）更新。當(dāng)A、B節(jié)點(diǎn)相遇時，更新A節(jié)點(diǎn)到B節(jié)點(diǎn)的遞交預(yù)測值：

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

2）衰減。如果節(jié)點(diǎn)A、B有一段時間沒有相遇，則A、B節(jié)點(diǎn)的遞交預(yù)測概率就會衰減。

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

3）傳遞。如果節(jié)點(diǎn)A、B經(jīng)常通信，同時節(jié)點(diǎn)B、C又頻繁相遇，那么C就是A轉(zhuǎn)發(fā)消息過程中的一個潛在的優(yōu)良中繼節(jié)點(diǎn)。

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

由上述可知：式（1）用來不斷更新兩個節(jié)點(diǎn)相遇概率;式（2）用來計(jì)算兩個節(jié)點(diǎn)長時間沒有相遇而導(dǎo)致節(jié)點(diǎn)間的遞交預(yù)測概率衰減值;式（3）用來計(jì)算兩個不直接相遇的節(jié)點(diǎn)遞交預(yù)測概率。

1.3 多屬性丟包策略

多屬性丟包策略利用消息的預(yù)測傳輸概率與消息副本數(shù)、消息大小及消息剩余生存時間計(jì)算消息的保留權(quán)重，優(yōu)先丟棄保留權(quán)值最小的消息。該策略可以有效均衡分配存儲資源，緩解擁塞節(jié)點(diǎn)的存儲負(fù)擔(dān)及提高消息的成功遞交率。

保留權(quán)值的計(jì)算如下：

其中：Q表示消息的保留權(quán)值; f表示轉(zhuǎn)發(fā)消息到目的節(jié)點(diǎn)的預(yù)測傳輸概率，利用式（1）、（2）和（3）計(jì)算;t表示消息的剩余生存時間;s表示消息的大小;r表示消息的冗余數(shù)量。消息的預(yù)測傳輸概率越大，剩余生存時間越長，消息大小越小，消息的冗余數(shù)量越少，則保留權(quán)值越大;相反，消息的預(yù)測傳輸概率越小，剩余生存時間越短，消息大小越大，消息的冗余數(shù)量越多，則保留權(quán)值越小。

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

2 ERC2路由協(xié)議

考慮到網(wǎng)絡(luò)資源有限和網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)動態(tài)變化的特點(diǎn)，ERC2路由協(xié)議主要由動態(tài)存儲狀態(tài)模型和路由模型兩部分構(gòu)成。動態(tài)存儲狀態(tài)模型通過網(wǎng)絡(luò)狀況動態(tài)調(diào)整節(jié)點(diǎn)半擁塞狀態(tài)的門限，預(yù)防網(wǎng)絡(luò)擁塞的發(fā)生。路由模型包括ACK確認(rèn)反饋機(jī)制、消息隊(duì)列管理以及（α， β）-Epidemic算法，使節(jié)點(diǎn)存儲狀態(tài)隨著網(wǎng)絡(luò)負(fù)載的隨機(jī)變化而動態(tài)更新并主動刪除冗余包。下面對ERC2路由協(xié)議進(jìn)行詳細(xì)的介紹。

2.1 動態(tài)存儲狀態(tài)模型

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

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

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

當(dāng)DTN拓?fù)浣Y(jié)構(gòu)隨機(jī)動態(tài)變化時，為提升網(wǎng)絡(luò)性能的穩(wěn)定性，本文提出一種動態(tài)存儲狀態(tài)模型（Dynamic Storage State Model， DSSM）。根據(jù)網(wǎng)絡(luò)負(fù)載情況決定α的取值，根據(jù)網(wǎng)絡(luò)負(fù)載情況變換路由策略，增加多屬性丟包策略，從而實(shí)現(xiàn)動態(tài)感知網(wǎng)絡(luò)狀態(tài)以及網(wǎng)絡(luò)整體性能穩(wěn)定。

圖1表示在消息轉(zhuǎn)發(fā)過程中，當(dāng)節(jié)點(diǎn)出現(xiàn)丟包現(xiàn)象即節(jié)點(diǎn)發(fā)生擁塞時，就把半擁塞門限α更新為當(dāng)前緩存利用率的一半，并將當(dāng)前緩存利用率記為擁塞門限β。將α值設(shè)為擁塞窗口的一半的目的是使節(jié)點(diǎn)感知網(wǎng)絡(luò)狀態(tài)，及時調(diào)整以適應(yīng)網(wǎng)絡(luò)的變化。

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

2.2 ERC2路由模型

考慮到節(jié)點(diǎn)資源受限及拓?fù)浣Y(jié)構(gòu)隨機(jī)動態(tài)變化的問題，本文提出了基于動態(tài)存儲模型多屬性丟包策略的擁塞控制傳染路由（ERC2）方法。ERC2路由通過確認(rèn)反饋機(jī)制對已傳送到目的節(jié)點(diǎn)的消息進(jìn)行管理，并根據(jù)ACK索引刪除冗余副本。當(dāng)節(jié)點(diǎn)緩存空間不足時，為了具有足夠的空間存儲新的消息，節(jié)點(diǎn)采用多屬性丟包策略優(yōu)先在消息緩存隊(duì)列中刪除保留權(quán)值較小的消息。當(dāng)對消息進(jìn)行轉(zhuǎn)發(fā)時采用（α， β）-Epidemic算法作為路由轉(zhuǎn)發(fā)策略，有效地對節(jié)點(diǎn)擁塞進(jìn)行控制。

2.2.1 確認(rèn)反饋機(jī)制

當(dāng)消息到達(dá)目的節(jié)點(diǎn)后，網(wǎng)絡(luò)應(yīng)立即停止對消息的轉(zhuǎn)發(fā)及復(fù)制，并刪除該消息副本。確認(rèn)反饋機(jī)制犧牲少量存儲空間來存儲ACK索引表，在消息到達(dá)目的節(jié)點(diǎn)后立即向發(fā)送節(jié)點(diǎn)反饋ACK消息，接收到確認(rèn)反饋消息的節(jié)點(diǎn)根據(jù)索引的消息ID將成功交付的消息冗余副本刪除。

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

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

2.2.2 消息管理隊(duì)列

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

2.2.3 （α， β）-Epidemic的相關(guān)定義描述

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

1）直接交付路由策略Direct Delivery（α=β=0）：源節(jié)點(diǎn)直接將消息轉(zhuǎn)發(fā)給目的節(jié)點(diǎn)，無需任何節(jié)點(diǎn)的中繼轉(zhuǎn)發(fā)。

2）洪泛路由策略Epidemic（α=β=1）：每一個節(jié)點(diǎn)轉(zhuǎn)發(fā)消息副本給中繼節(jié)點(diǎn)，同時接收消息副本的概率為1。

3）多副本路由策略（α， β）-Epidemic（0<α， β≤1）：節(jié)點(diǎn)根據(jù)半擁塞門限α來動態(tài)調(diào)整路由策略，而擁塞門限β決定α的取值。

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

（α， β）-Epidemic路由策略的基本思想是在Epidemic協(xié)議的基礎(chǔ)上，根據(jù)節(jié)點(diǎn)緩存利用率將轉(zhuǎn)發(fā)過程劃分成兩個階段，即洪泛轉(zhuǎn)發(fā)和概率轉(zhuǎn)發(fā);同時，結(jié)合動態(tài)節(jié)點(diǎn)存儲模型，增加ACK索引以及保留權(quán)值，使得節(jié)點(diǎn)存儲狀態(tài)隨著網(wǎng)絡(luò)負(fù)載的隨機(jī)變化而動態(tài)更新并主動刪除冗余包，從而達(dá)到預(yù)防、避免、解除擁塞的目的。

假設(shè)DTN節(jié)點(diǎn)a與b相遇并建立通信連接，節(jié)點(diǎn)a、b相互交換彼此的ACK索引表。首先，根據(jù)確認(rèn)反饋刪除交付成功的消息并獲得待轉(zhuǎn)發(fā)消息集合;其次，動態(tài)更新緩存利用率以及半擁塞、擁塞門限?，F(xiàn)在節(jié)點(diǎn)a向b傳送消息，節(jié)點(diǎn)b根據(jù)其存儲狀態(tài)從而選擇路由策略。

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

由圖4可知，路由算法的轉(zhuǎn)發(fā)過程主要包括以下幾點(diǎn)。

1）洪泛轉(zhuǎn)發(fā)階段。

此階段利用典型的Epidemic路由算法，其中節(jié)點(diǎn)b的緩存利用率低于半擁塞門限，此時節(jié)點(diǎn)b無限制接收傳輸?shù)南?。緩存利用率低于半擁塞門限，說明節(jié)點(diǎn)的緩存資源充足，洪泛轉(zhuǎn)發(fā)可以提高消息遞交率。

2）概率轉(zhuǎn)發(fā)階段。

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

3）擁塞處理階段。

如果節(jié)點(diǎn)b出現(xiàn)丟包情況，則進(jìn)入擁塞狀態(tài)，同時停止接收消息。節(jié)點(diǎn)進(jìn)入擁塞處理階段，優(yōu)先丟棄緩存隊(duì)列隊(duì)尾的消息，并持續(xù)該操作直到節(jié)點(diǎn)擁塞解除。

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

4.1 性能指標(biāo)

為了驗(yàn)證分析ERC2的有效性，本文從消息遞交率、平均傳輸時延、平均轉(zhuǎn)發(fā)次數(shù)及網(wǎng)絡(luò)開銷率四個方面比較ERC2算法與經(jīng)典算法Prophet和Spray and Wait[15]等路由算法的網(wǎng)絡(luò)性能，指標(biāo)定義如下。

1）消息遞交率。

消息遞交率=（1.0×成功遞交的消息總數(shù)/網(wǎng)絡(luò)中總的消息個數(shù)1.0×在此處不適合吧，遞交率應(yīng)該為百分?jǐn)?shù)吧，所以此式是否應(yīng)該是“成功遞交的消息總數(shù)/網(wǎng)絡(luò)中總的消息個數(shù)×100%”，或者刪除“1.0×”，改為“成功遞交的消息總數(shù)/網(wǎng)絡(luò)中總的消息個數(shù)”？以哪個為準(zhǔn)？請明確。另，下面的2）～4）的指標(biāo)作相應(yīng)修改。

2）傳輸時延。

3）平均轉(zhuǎn)發(fā)次數(shù)。

4）網(wǎng)絡(luò)負(fù)載率。

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

4.2 仿真場景設(shè)置

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

為保證ERC2能夠適應(yīng)不同擁塞程度的網(wǎng)絡(luò)環(huán)境，具體的網(wǎng)絡(luò)環(huán)境設(shè)置如下：

無擁塞或輕度擁塞網(wǎng)絡(luò)[17] 網(wǎng)絡(luò)仿真時間為12h，網(wǎng)絡(luò)總共生成400個消息，節(jié)點(diǎn)生成消息的速率為每秒20個，每個消息的生命周期為10h。

中度擁塞網(wǎng)絡(luò)[17] 網(wǎng)絡(luò)仿真時間為18h，網(wǎng)絡(luò)總共生成2000個消息，節(jié)點(diǎn)生成消息的速率為每秒40個，每個消息的生命周期為15h。

重度擁塞網(wǎng)絡(luò)[17] 網(wǎng)絡(luò)仿真時間為20h，網(wǎng)絡(luò)總共生成10000個消息，節(jié)點(diǎn)生成消息的速率為每秒100個，每個消息的生命周期為18h。

4.3 仿真結(jié)果與分析

4.3.1 無擁塞或輕度擁塞網(wǎng)絡(luò)下性能分析

在無擁塞或輕度擁塞網(wǎng)絡(luò)環(huán)境下，分別對Epidemic、Prophet路由算法和具有擁塞控制的傳染路由ERC2進(jìn)行實(shí)驗(yàn)仿真，仿真結(jié)果圖5（a）～（c）分別比較了網(wǎng)絡(luò)無擁塞或輕度擁塞時各個算法的3項(xiàng)性能指標(biāo)。

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

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

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

綜合圖5來看，ERC2能夠在提高路由性能與降低傳輸成本之間取得更好的平衡。從消息遞交率和傳輸時延考慮，ERC2優(yōu)于Prophet算法;從平均轉(zhuǎn)發(fā)次數(shù)和網(wǎng)絡(luò)負(fù)載率圖5～7中，是否均少了子圖“（d） 網(wǎng)絡(luò)負(fù)載率”，4.1節(jié)中有該性能的說明，需作相應(yīng)調(diào)整。若補(bǔ)充了子圖（d），請?zhí)峁┦噶繄D來比較，ERC2明顯低于Epidemic算法，因此其路由性能更加穩(wěn)定，使用價值更高。

4.3.2 中度擁塞網(wǎng)絡(luò)下性能分析

在中度擁塞網(wǎng)絡(luò)環(huán)境下，分別對Epidemic、Prophet路由算法和具有擁塞控制的傳染路由ERC2進(jìn)行實(shí)驗(yàn)仿真，仿真結(jié)果圖6比較了網(wǎng)絡(luò)中度擁塞時各個算法的3項(xiàng)性能指標(biāo)。

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

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

圖6（c）比較了Epidemic、Prophet和ERC2的平均轉(zhuǎn)發(fā)次數(shù)?？梢钥闯觯S著仿真時間增加，ERC2的平均轉(zhuǎn)發(fā)次數(shù)基本接近于Prophet，這表明了ERC2在網(wǎng)絡(luò)中度擁塞環(huán)境下依然可以保持中繼選擇的高效性;而Epidemic算法的平均轉(zhuǎn)發(fā)次數(shù)隨著仿真時間的增加而增大，這是因?yàn)橄⒌纳芷诟L，致使消息的轉(zhuǎn)發(fā)次數(shù)更多。圖6（d）評估了Epidemic、Prophet和ERC2的網(wǎng)絡(luò)負(fù)載率未見圖6（d）。隨著仿真時間的增加，它們的負(fù)載率都在上升，但是ERC2的增長趨勢明顯弱于Epidemic。分析其中的原因是ERC2通過設(shè)置半擁塞門限有效地控制了冗余消息副本的數(shù)量，減少了節(jié)點(diǎn)緩存資源浪費(fèi)，因而ERC2的負(fù)載率明顯低于Epidemic。

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

4.3.3 重度擁塞網(wǎng)絡(luò)下性能分析

在重度擁塞網(wǎng)絡(luò)環(huán)境下，分別對Epidemic、Prophet路由算法和具有擁塞控制的傳染路由ERC2進(jìn)行實(shí)驗(yàn)仿真，仿真結(jié)果（如圖7）比較了網(wǎng)絡(luò)重度擁塞時各個算法的3項(xiàng)性能指標(biāo)。

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

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

圖7（c）評估了網(wǎng)絡(luò)重度擁塞時Epidemic、Prophet算法和ERC2的轉(zhuǎn)發(fā)次數(shù)。從圖中可以看出，Epidemic的平均轉(zhuǎn)發(fā)次數(shù)不斷升高，ERC2能夠?qū)⑵骄D(zhuǎn)發(fā)次數(shù)維持在一個較低的水平，并且ERC2總體上的路由性能要優(yōu)于Epidemic，但比Prophet性能較差。

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

5 結(jié)語

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

參考文獻(xiàn) （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].計(jì)算機(jī)工程與應(yīng)用，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] 王賀哲，王慧強(qiáng)，朱金美，等.OCIGM：面向DTN路由的優(yōu)化控制信息生成方法[J].北京郵電大學(xué)學(xué)報，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] 王恩，楊永健，李蒞.基于動態(tài)半馬爾可夫路徑搜索模型的DTN分簇路由方法[J].計(jì)算機(jī)學(xué)報，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].通信學(xué)報，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擁塞控制機(jī)制及其應(yīng)用研究[D].長沙：湖南大學(xué)，2013：33-37.（HUANG X J. Research on congestion control mechanism for DTN and its application [D]. Changsha： Hunan University， 2013：33-37.）