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

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

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

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

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

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

1 相關(guān)工作

1.1 Epidemic路由協(xié)議

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

1.2 Prophet路由協(xié)議

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

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

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

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

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

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

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

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

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

1.3 多屬性丟包策略

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

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

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

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

2 ERC2路由協(xié)議

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

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

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

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

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

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

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

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

2.2 ERC2路由模型

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

2.2.1 確認反饋機制

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

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

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

2.2.2 消息管理隊列

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3）擁塞處理階段。

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

4 仿真實驗與分析

4.1 性能指標(biāo)

為了驗證分析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)該為百分數(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ò)負載率。

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

4.2 仿真場景設(shè)置

本文運用ONE（Opportunistic Networking Environment）仿真工具對實驗場景進行模擬仿真。該采用Working Day Movement（WDM）[16]模型描述節(jié)點移動。仿真場景大小為1000m×8000m，由120個節(jié)點、40個地點組成。節(jié)點分為兩組，根據(jù)兩組節(jié)點的特征分別進行設(shè)置。第一組為汽車節(jié)點，速度為7～10m/s，停車等待時間為20～40s，傳輸速率為1.25MB/s，傳輸半徑為1000m，節(jié)點20個;第二組為行人節(jié)點，速度為1～1.5m/s，傳輸速率為0.25MB/s，傳輸半徑為20m，節(jié)點100個。默認仿真參數(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é)點生成消息的速率為每秒20個，每個消息的生命周期為10h。

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

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

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

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

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

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

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

圖5（c）比較了各個算法的平均轉(zhuǎn)發(fā)次數(shù)。平均轉(zhuǎn)發(fā)次數(shù)越低通常表明路由中繼選擇根據(jù)準(zhǔn)確平均轉(zhuǎn)發(fā)次數(shù)越低通常表明路由選擇中繼節(jié)點時越準(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ò)負載率圖5～7中，是否均少了子圖“（d） 網(wǎng)絡(luò)負載率”，4.1節(jié)中有該性能的說明，需作相應(yīng)調(diào)整。若補充了子圖（d），請?zhí)峁┦噶繄D來比較，ERC2明顯低于Epidemic算法，因此其路由性能更加穩(wěn)定，使用價值更高。

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

在中度擁塞網(wǎng)絡(luò)環(huán)境下，分別對Epidemic、Prophet路由算法和具有擁塞控制的傳染路由ERC2進行實驗仿真，仿真結(jié)果圖6比較了網(wǎng)絡(luò)中度擁塞時各個算法的3項性能指標(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卻保持著較低的傳輸時延，這驗證了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ù)隨著仿真時間的增加而增大，這是因為消息的生命周期更長，致使消息的轉(zhuǎn)發(fā)次數(shù)更多。圖6（d）評估了Epidemic、Prophet和ERC2的網(wǎng)絡(luò)負載率未見圖6（d）。隨著仿真時間的增加，它們的負載率都在上升，但是ERC2的增長趨勢明顯弱于Epidemic。分析其中的原因是ERC2通過設(shè)置半擁塞門限有效地控制了冗余消息副本的數(shù)量，減少了節(jié)點緩存資源浪費，因而ERC2的負載率明顯低于Epidemic。

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

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

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

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

圖7（b）描述了網(wǎng)絡(luò)重度擁塞時Epidemic、Prophet算法和ERC2的傳輸時延變化情況。由于消息生成速率變大，固定時間內(nèi)生成的消息副本數(shù)不斷增加，從而導(dǎo)致網(wǎng)絡(luò)更易發(fā)生擁塞而無法正常工作，因此無擁塞控制機制的Epidemic的消息平均傳輸時延迅速上升;同時由于ERC2的路由選擇機制比Prophet更加嚴格，資源利用率更加高效，故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é)點緩存資源受限的DTN，缺乏冗余副本數(shù)控制機制的Epidemic會浪費大量網(wǎng)絡(luò)資源。Prophet是基于Epidemic的概率轉(zhuǎn)發(fā)路由，雖然在一定程度上控制了副本數(shù)量，但其性能比ERC2較差。ERC2利用節(jié)點意愿度和預(yù)測投遞值選擇更優(yōu)的中繼節(jié)點，優(yōu)化了節(jié)點緩存管理，從而有效地避免了消息副本的擴散，降低了網(wǎng)絡(luò)負載。

5 結(jié)語

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

參考文獻 （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].計算機工程與應(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] 王賀哲，王慧強，朱金美，等.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].計算機學(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擁塞控制機制及其應(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.）