覃秋玉，劉丹丹，張 健

QIN Qiuyu1,LIU Dandan2,ZHANG Jian2

1.武漢大學(xué) 計(jì)算機(jī)學(xué)院，武漢 430072

2.武漢大學(xué) 計(jì)算機(jī)學(xué)院 軟件工程國家重點(diǎn)實(shí)驗(yàn)室，武漢 430072

1.Computer School,Wuhan University,Wuhan 430072,China

2.State Key Lab of Software Engineering,Computer School,Wuhan University,Wuhan 430072,China

1 引言

延遲容忍網(wǎng)絡(luò)[1-2]（Delay Tolerant Network，DTN）是一種自組織網(wǎng)絡(luò)，用于解決無線應(yīng)用中無法提供穩(wěn)定連接的問題。DTN技術(shù)能用于特殊的網(wǎng)絡(luò)應(yīng)用場景，一些典型的應(yīng)用有野生動(dòng)物追蹤、手持設(shè)備組網(wǎng)、車載網(wǎng)絡(luò)服務(wù)和網(wǎng)絡(luò)接入服務(wù)等[3-4]。在DTN中，網(wǎng)絡(luò)節(jié)點(diǎn)之間的連接經(jīng)常斷開，網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)動(dòng)態(tài)變化，端到端傳輸路徑難以維持。為克服網(wǎng)絡(luò)的中斷性，DTN中采用“存儲(chǔ)-攜帶-轉(zhuǎn)發(fā)”的路由模式，利用節(jié)點(diǎn)移動(dòng)帶來的相遇機(jī)會(huì)進(jìn)行通信[5]。由于長延時(shí)和中斷特性，以及節(jié)點(diǎn)的資源受限性，在DTN中很容易出現(xiàn)擁塞。此外，很多現(xiàn)有路由協(xié)議采用多副本的傳輸方式[6-7]，冗余的副本可以顯著地提高交付率，但是另一方面，其也會(huì)帶來額外的開銷，從而加劇擁塞。如果不采取有效的擁塞控制策略，網(wǎng)絡(luò)性能可能會(huì)迅速地惡化，嚴(yán)重影響網(wǎng)絡(luò)的服務(wù)質(zhì)量（Quality of Service，QoS）。

傳統(tǒng)的網(wǎng)絡(luò)中擁塞控制方法是基于端到端反饋機(jī)制。傳統(tǒng)Internet中TCP傳輸層的擁塞控制包括慢啟動(dòng)、擁塞避免、快速重傳、快速恢復(fù)策略，是基于可靠的延時(shí)短的端到端反饋機(jī)制。然而在DTN中網(wǎng)絡(luò)之間的連接經(jīng)常斷開，無法維持可靠的端到端的路徑，且消息傳輸延時(shí)長，無法使用基于反饋的控制策略，傳統(tǒng)網(wǎng)絡(luò)中控制擁塞的方法對(duì)DTN并不適用。作為一種受限網(wǎng)絡(luò)，DTN中的擁塞控制是一個(gè)更加重要的問題。

近年來，DTN中的擁塞控制策略[8-9]得到了廣泛的關(guān)注。在DTN中全局網(wǎng)絡(luò)信息是難以獲取和維持的，因此擁塞控制策略中節(jié)點(diǎn)要能夠僅僅利用局部信息來判斷當(dāng)前擁塞程度并做出相應(yīng)的措施。為避免冗余的副本消耗過多的資源帶來過多的開銷，多副本路由方式中必須對(duì)副本的數(shù)量加以控制。傳染路由[10]（Epidemic Routing）沒有限制消息副本的數(shù)量，會(huì)迅速耗盡節(jié)點(diǎn)的存儲(chǔ)空間。散發(fā)等待協(xié)議[11]（Spray and Wait）限定了消息的最大副本數(shù)，但是難以確定一個(gè)合適的副本數(shù)量，且固定的副本數(shù)量難以適應(yīng)動(dòng)態(tài)變化的網(wǎng)絡(luò)環(huán)境。簡單計(jì)數(shù)協(xié)議[12]（Simple Counting）是一種基于計(jì)數(shù)的副本控制方案，這是一種動(dòng)態(tài)的副本控制方式。節(jié)點(diǎn)對(duì)于每個(gè)消息維持兩個(gè)計(jì)數(shù)，分別表示該節(jié)點(diǎn)連續(xù)遇到的攜帶或不攜帶該消息的其他節(jié)點(diǎn)的次數(shù)，如果計(jì)數(shù)超過閾值，就分別復(fù)制或丟棄消息副本。

網(wǎng)絡(luò)中流量分布是不均勻的，因此在產(chǎn)生局部擁塞的時(shí)候可以轉(zhuǎn)移部分負(fù)載到狀態(tài)比較好的區(qū)域。Seligman在文獻(xiàn)[13]中提出了一種節(jié)點(diǎn)間的數(shù)據(jù)轉(zhuǎn)移方案，通過將儲(chǔ)存的數(shù)據(jù)轉(zhuǎn)移到鄰居節(jié)點(diǎn)來解決DTN中的存儲(chǔ)擁塞問題。類似的，文獻(xiàn)[14]提出了一種存儲(chǔ)路由，其使用局部范圍的分布式算法來確定將哪些消息轉(zhuǎn)移到哪些鄰居節(jié)點(diǎn)。這些基于存儲(chǔ)轉(zhuǎn)移的調(diào)度方法能夠充分利用其他節(jié)點(diǎn)的空閑緩存空間，提高網(wǎng)絡(luò)存儲(chǔ)利用率，但是轉(zhuǎn)移算法會(huì)增加路由的復(fù)雜性，過多的消息轉(zhuǎn)移加重了網(wǎng)絡(luò)的通信開銷。

消息丟棄可以分為主動(dòng)丟棄和被動(dòng)丟棄。被動(dòng)丟棄是指節(jié)點(diǎn)緩存空間滿時(shí)為了接收新的消息必須丟棄部分消息，關(guān)鍵在于確定重要性度量丟棄對(duì)網(wǎng)絡(luò)傳輸影響最小的消息副本。主動(dòng)丟棄與存儲(chǔ)狀態(tài)無關(guān)，只要消息滿足設(shè)定的要求就刪除副本。Small等人在文獻(xiàn)[15]中介紹了幾種副本清除方法，包括JUST_TTL、FULL_ERASE和VACCINE等。其中最簡單的方法是JUST_TTL，節(jié)點(diǎn)刪除那些超過生存時(shí)間的失效消息。VACCINE方法引入了anti-packet這一標(biāo)識(shí)，對(duì)成功交付的消息保持一個(gè)標(biāo)識(shí)，代表該標(biāo)識(shí)對(duì)應(yīng)的消息已經(jīng)傳輸成功。節(jié)點(diǎn)間通過共享這一信息可以刪除已有的無用消息，并拒絕再次接收同樣的消息，類似于免疫。在這種情況下，即使接收節(jié)點(diǎn)沒有存儲(chǔ)的分組的副本，節(jié)點(diǎn)也可以從另一節(jié)點(diǎn)接收反分組。

本文提出了一種基于節(jié)點(diǎn)狀態(tài)的自適應(yīng)的擁塞控制策略（Adaptive Congestion Control mechanism based on Node State，ACC-NS），節(jié)點(diǎn)僅利用本地信息來自主決策消息的接收行為，從而動(dòng)態(tài)地調(diào)整副本的數(shù)量。本文的主要貢獻(xiàn)如下：（1）將消息進(jìn)行了分類。消息分為普通消息和特殊消息，在擁塞控制的同時(shí)針對(duì)消息類別做了些QoS控制。（2）提出了自適應(yīng)的消息接收策略，節(jié)點(diǎn)可以根據(jù)自己的擁塞狀態(tài)動(dòng)態(tài)地調(diào)整消息的接收概率，使得消息數(shù)據(jù)較為均勻地分布到網(wǎng)絡(luò)中。（3）針對(duì)冗余副本的清除，結(jié)合了VACCINE方法和基于消息相遇計(jì)數(shù)的方法，可以較為快速地清除消息副本同時(shí)保證較高的可靠性。

2 自適應(yīng)的擁塞控制策略

2.1 消息類別和節(jié)點(diǎn)狀態(tài)劃分

為更好地反映現(xiàn)實(shí)組網(wǎng)的不同服務(wù)需求情況，本文對(duì)消息類別做出了一些差異化設(shè)定。將消息分為普通消息和特殊消息，根據(jù)消息的重要性進(jìn)行歸類。例如興趣推送可以歸為普通消息，email可以歸為特殊消息，一般人們希望email能正確收到。因此特殊消息會(huì)要求更高的交付率，在傳輸過程中不會(huì)將其隨意丟棄。

根據(jù)節(jié)點(diǎn)的緩存空間使用率劃分節(jié)點(diǎn)的擁塞程度，將節(jié)點(diǎn)分為未擁塞（No Congestion，NC）、輕擁塞（Low Congestion，LC）和重?fù)砣℉igh Congestion，HC）三種狀態(tài)。定義r為緩沖空間使用率，其中r∈[0 ,1]。定義Rl為輕擁塞的緩存空間使用率臨界值，Rh為重?fù)砣呐R界值，其中0＜R1＜Rh＜1。未擁塞的節(jié)點(diǎn)的狀態(tài)為NC，其中其緩沖空間使用率滿足r∈[0 ,Rl]；輕擁塞的節(jié)點(diǎn)狀態(tài)為LC，r∈[Rl,Rh]；重?fù)砣墓?jié)點(diǎn)狀態(tài)為HC，r∈[Rh,1]。節(jié)點(diǎn)狀態(tài)描述圖如圖1所示。

圖1 節(jié)點(diǎn)狀態(tài)描述圖

隨著網(wǎng)絡(luò)不斷運(yùn)行，節(jié)點(diǎn)可能在三種狀態(tài)間反復(fù)轉(zhuǎn)換。剛開始時(shí)節(jié)點(diǎn)處于NC狀態(tài)，隨著新消息的轉(zhuǎn)入和不能及時(shí)轉(zhuǎn)發(fā)出去的消息在緩存空間累積，節(jié)點(diǎn)逐漸進(jìn)入LC狀態(tài)。隨著進(jìn)一步的消息累積，可利用的空閑緩存空間越來越少，節(jié)點(diǎn)逐漸進(jìn)入HC狀態(tài)。而處于HC狀態(tài)的節(jié)點(diǎn)可以通過一定的策略丟棄或轉(zhuǎn)移部分消息以釋放緩存空間，擁塞程度得到改善轉(zhuǎn)換為LC狀態(tài)，可能還進(jìn)一步退回到NC狀態(tài)。

網(wǎng)絡(luò)的擁塞度會(huì)不斷處于動(dòng)態(tài)變化中，每一時(shí)刻網(wǎng)絡(luò)中可能會(huì)存在三種狀態(tài)的節(jié)點(diǎn)，不同的是各種狀態(tài)節(jié)點(diǎn)所占比例。節(jié)點(diǎn)各自的擁塞狀態(tài)可以反映出網(wǎng)絡(luò)總體的擁塞狀況，如果網(wǎng)絡(luò)中處于NC狀態(tài)的節(jié)點(diǎn)占很大比例，那么網(wǎng)絡(luò)整體擁塞狀態(tài)較好。反過來如果網(wǎng)絡(luò)中處于HC狀態(tài)的節(jié)點(diǎn)占比例高，那么網(wǎng)絡(luò)整體擁塞情況較重。節(jié)點(diǎn)對(duì)于網(wǎng)絡(luò)整體的擁塞狀況并不知情，它們只是根據(jù)自己的擁塞狀況做出不同的反應(yīng)策略。

NC狀態(tài)沒有產(chǎn)生擁塞，同時(shí)也意味著節(jié)點(diǎn)中緩存的消息較少，如果很多節(jié)點(diǎn)都處于NC狀態(tài)，就表明網(wǎng)絡(luò)總體較為空閑，負(fù)載較小，網(wǎng)絡(luò)使用率不高，沒有充分利用資源。HC狀態(tài)的節(jié)點(diǎn)處于重度擁塞，節(jié)點(diǎn)緩存中已經(jīng)存在很多消息占用了大量存儲(chǔ)空間，如果網(wǎng)絡(luò)中很多節(jié)點(diǎn)處于HC狀態(tài)，表明網(wǎng)絡(luò)整體上已經(jīng)出現(xiàn)較嚴(yán)重的擁塞，如果不采取措施會(huì)使得擁塞程度進(jìn)一步惡化，節(jié)點(diǎn)的服務(wù)能力大幅下降，最終使得整個(gè)網(wǎng)絡(luò)性能惡化。因此比較理想的狀態(tài)是LC，網(wǎng)絡(luò)有著較高的使用率，同時(shí)又不至于過于擁塞降低網(wǎng)絡(luò)效用，在網(wǎng)絡(luò)利用率和資源消耗之間取得平衡。將節(jié)點(diǎn)狀態(tài)進(jìn)行劃分，可以讓節(jié)點(diǎn)針對(duì)不同的擁塞程度做出不同的反映，實(shí)現(xiàn)動(dòng)態(tài)控制。

2.2 自適應(yīng)的接收策略

自適應(yīng)的接收策略，就是節(jié)點(diǎn)根據(jù)自身所處的不同擁塞狀態(tài)和消息的類別動(dòng)態(tài)調(diào)整消息的接收概率。使得節(jié)點(diǎn)既能夠充分使用資源提高網(wǎng)絡(luò)性能，又不至于讓資源過度消耗使網(wǎng)絡(luò)性能迅速惡化?？偟膩碚f，自適應(yīng)的接收策略是一種動(dòng)態(tài)調(diào)節(jié)策略，其目的是在網(wǎng)絡(luò)收益和資源消耗之間取得平衡，從而提高網(wǎng)絡(luò)性能。以下將根據(jù)不同的節(jié)點(diǎn)狀態(tài)分別進(jìn)行討論。

2.2.1 未擁塞的節(jié)點(diǎn)

節(jié)點(diǎn)處于NC狀態(tài)時(shí)，緩沖空間充足，可以為所有其他節(jié)點(diǎn)的所有消息提供中繼服務(wù)，可以接收其他節(jié)點(diǎn)轉(zhuǎn)發(fā)的任何消息，存到緩沖區(qū)中攜帶。這樣可以迅速將存儲(chǔ)空間使用率提高到一個(gè)較高的水平，避免存儲(chǔ)空間長時(shí)間空閑，有利于提高消息的交付率和減小消息的傳輸延時(shí)。這個(gè)狀態(tài)下節(jié)點(diǎn)間的通信行為方式非常類似于傳染路由，只要有機(jī)會(huì)就相互交換彼此沒有的消息。因?yàn)榇藸顟B(tài)下節(jié)點(diǎn)存儲(chǔ)空間尚且足夠，就盡可能的多攜帶多轉(zhuǎn)發(fā)消息，不對(duì)消息的接收作任何限定，充分使用較為空閑的網(wǎng)絡(luò)資源。

2.2.2 輕擁塞的節(jié)點(diǎn)

當(dāng)節(jié)點(diǎn)處于LC狀態(tài)時(shí)，緩存空間使用率已經(jīng)較高了，如果還按照之前的方式接收消息，節(jié)點(diǎn)的緩存空間會(huì)迅速占滿。為抑制緩存使用量的增長速度，同時(shí)保證特殊消息的服務(wù)，這個(gè)狀態(tài)下的節(jié)點(diǎn)以概率1接收特殊消息，以變化的概率接收普通消息。

定義該狀態(tài)下普通消息的接收概率為P，這一概率應(yīng)該隨著緩存空間使用率的增加而減小，同時(shí)為了在進(jìn)入這個(gè)狀態(tài)后達(dá)到較明顯的緩存增長抑制效果，接收概率減小的程度應(yīng)該先迅速后逐漸趨于平緩。為此將P關(guān)于r的函數(shù)設(shè)計(jì)為一個(gè)遞減的凹函數(shù)，其中r∈[Rl,Rh]，在Rl處取得最大值，在Rh處取得最小值?？紤]最簡單的二次函數(shù) f(x)，端點(diǎn)Rl處 f(Rl)=1，頂點(diǎn)Rh處 f(Rh)=0，由此確定一個(gè)二次函數(shù)，如式（1）所示。

x從Rl到Rh的變化過程中，當(dāng)x與Rl差值較小時(shí)，函數(shù)值接近于1，即這時(shí)候的接收概率太高，需要適度修正。于是在原 f(r)值的基礎(chǔ)上再乘以可用緩存的百分比1-r，最終得到P與r之間的函數(shù)對(duì)應(yīng)關(guān)系，如式（2）所示。

2.2.3 重?fù)砣墓?jié)點(diǎn)

當(dāng)節(jié)點(diǎn)處于HC狀態(tài)時(shí)，可用的存儲(chǔ)空間已經(jīng)很小了。這時(shí)候節(jié)點(diǎn)不再作為中繼者接收普通消息，促使普通消息選擇狀態(tài)更好的下一跳節(jié)點(diǎn)。為避免頻繁的消息丟棄，只以一定的小概率接收普通消息，簡單將接收概率取為1-r。

值得注意的是，以上的接收概率都是指節(jié)點(diǎn)作為中間節(jié)點(diǎn)接收消息的概率，消息的目的節(jié)點(diǎn)總是以概率1接收發(fā)給自己的消息。節(jié)點(diǎn)在復(fù)制轉(zhuǎn)發(fā)每個(gè)消息前都要向接收節(jié)點(diǎn)發(fā)送一個(gè)包含該消息摘要信息的發(fā)送請(qǐng)求，則接收節(jié)點(diǎn)判斷是否接收該消息并返回應(yīng)答，應(yīng)答的類型決定了發(fā)送節(jié)點(diǎn)的下一步具體操作。

綜合以上不同節(jié)點(diǎn)狀態(tài)和消息類別下的消息接收概率如表1所示。節(jié)點(diǎn)根據(jù)自身不同的擁塞程度選擇不同的消息接收概率，擁塞情況越嚴(yán)重，其接收消息的概率越小。DTN中可能在某個(gè)相遇時(shí)刻，節(jié)點(diǎn)周圍有幾個(gè)鄰居節(jié)點(diǎn)，或者在后面移動(dòng)過程中遇到多個(gè)不同節(jié)點(diǎn)。擁塞比較嚴(yán)重的節(jié)點(diǎn)有更高的概率拒絕接收消息，狀態(tài)好的節(jié)點(diǎn)卻可以更輕易接收消息，使得消息更有可能被傳遞到狀態(tài)較好的節(jié)點(diǎn)。這種控制方法可以有效指引消息選擇狀態(tài)好的下一跳節(jié)點(diǎn)并復(fù)制消息，使網(wǎng)絡(luò)流量較為均衡地分布到所有節(jié)點(diǎn)，起到負(fù)載均衡的效果。針對(duì)普通消息和特殊消息采用不同的接收策略，給特殊消息更多的接收機(jī)會(huì)，盡量滿足其傳輸率要求，又不至于讓特殊消息過多剝奪普通消息的資源，取得一個(gè)較好的平衡。

表1 不同節(jié)點(diǎn)狀態(tài)和消息類別下的消息接收概率

2.3 緩沖區(qū)管理

為清除冗余的消息副本，將VACCINE方法和基于相遇計(jì)數(shù)的方法[12]進(jìn)行結(jié)合。VACCINE方法中每個(gè)節(jié)點(diǎn)維持一個(gè)已交付的消息標(biāo)識(shí)列表，列表的基本元素是消息ID，代表對(duì)應(yīng)的消息已經(jīng)成功交付了。節(jié)點(diǎn)在相遇期間交換和更新彼此的標(biāo)識(shí)列表，刪除并拒絕接收對(duì)應(yīng)于列表中的消息。

VACCINE方法是在消息成功交付之后再擴(kuò)散該消息的交付信息，在網(wǎng)絡(luò)中擴(kuò)散這一信息讓所有節(jié)點(diǎn)都知道，可能要經(jīng)歷很長時(shí)間。為此還采用基于消息相遇計(jì)數(shù)的副本清除方法。該方法中節(jié)點(diǎn)對(duì)每個(gè)消息維持一個(gè)相遇計(jì)數(shù)值，計(jì)數(shù)表示節(jié)點(diǎn)遇到攜帶有同樣消息的其他節(jié)點(diǎn)的次數(shù)。當(dāng)遇到攜有相同消息的其他節(jié)點(diǎn)時(shí)對(duì)消息的相遇計(jì)數(shù)值加1，如果某一消息的計(jì)數(shù)值超過閾值，就將其從存儲(chǔ)空間中刪除，同時(shí)將消息的計(jì)數(shù)值設(shè)置為-1，并不再更新。與VACCINE相比這是一種不可靠的副本刪除方式，但是計(jì)數(shù)值超過閾值可以反映出網(wǎng)絡(luò)中已經(jīng)產(chǎn)生較多該消息的副本了，刪除這類消息對(duì)消息傳輸影響較小。這兩種方式結(jié)合可以更有效清除多余副本，同時(shí)保證較高的可靠性。

為確定緩沖區(qū)中消息的發(fā)送和丟棄順序，將消息組織成一個(gè)優(yōu)先級(jí)隊(duì)列。由于特殊消息要求較高的交付率，應(yīng)該給予其較高的優(yōu)先級(jí)。此外，每個(gè)消息都有一個(gè)相遇計(jì)數(shù)，計(jì)數(shù)的大小可以反映網(wǎng)絡(luò)中產(chǎn)生的該消息副本數(shù)的多少。應(yīng)該給副本數(shù)較少的消息更多的發(fā)送機(jī)會(huì)，因此相遇計(jì)數(shù)較小的消息優(yōu)先級(jí)更高。計(jì)數(shù)相同的消息，剩余生存時(shí)間較長的享有更高的優(yōu)先級(jí)。按照以上規(guī)則，相遇期間優(yōu)先發(fā)送隊(duì)首的消息，當(dāng)存儲(chǔ)空間不足而必須接收新消息時(shí)優(yōu)先刪除隊(duì)尾的消息。

2.4 ACC-NS路由策略

綜合以上內(nèi)容，給出完整的基于節(jié)點(diǎn)狀態(tài)（Node State，NS）的自適應(yīng)擁塞控制（Adaptive Congestion Control，ACC）路由策略，簡稱為ACC-NS。以節(jié)點(diǎn) M和節(jié)點(diǎn)N相遇時(shí)它們之間的一次消息傳輸為例來說明，假設(shè)消息由M復(fù)制轉(zhuǎn)發(fā)給N，ACC-NS策略的流程圖如圖2和圖3所示。流程圖分別從節(jié)點(diǎn)N和節(jié)點(diǎn)M的角度闡述策略執(zhí)行過程，其中圖2是描述節(jié)點(diǎn)N決策是否能接收消息m的過程，圖3是描述節(jié)點(diǎn)M嘗試給節(jié)點(diǎn)N發(fā)送消息的過程。節(jié)點(diǎn)具體的操作步驟如下所述：

（1）節(jié)點(diǎn)M和N之間相遇建立連接，執(zhí)行VACCINE方法，兩節(jié)點(diǎn)相互交換彼此的已交付消息標(biāo)識(shí)列表，更新各自交付列表并刪除相應(yīng)消息。

（2）節(jié)點(diǎn)M從消息隊(duì)列中取出下一個(gè)消息m（初始的時(shí)候?yàn)殛?duì)首消息），如果已經(jīng)位于隊(duì)尾沒有下一個(gè)消息，則停止發(fā)送過程。否則，節(jié)點(diǎn)M向節(jié)點(diǎn)N發(fā)出發(fā)送請(qǐng)求，請(qǐng)求中有消息m的關(guān)鍵信息。

圖2 節(jié)點(diǎn)N決策是否能接收消息m

圖3 節(jié)點(diǎn)M嘗試給節(jié)點(diǎn)N發(fā)送消息

（3）節(jié)點(diǎn)N檢查m相關(guān)信息，如果節(jié)點(diǎn)N是消息m的目的節(jié)點(diǎn)，則返回“接收”應(yīng)答。跳轉(zhuǎn)到第（6）步。

（4）如果節(jié)點(diǎn)N的消息相遇計(jì)數(shù)列表中有m的記錄，則返回拒收應(yīng)答。拒收的類型是“已有”，代表對(duì)方節(jié)點(diǎn)已經(jīng)有該消息不必重復(fù)發(fā)送。如果計(jì)數(shù)不為-1，則對(duì)計(jì)數(shù)加1。如果加1后超過計(jì)數(shù)閾值，節(jié)點(diǎn)N就從消息隊(duì)列中刪除消息m，同時(shí)將其計(jì)數(shù)置為-1。跳轉(zhuǎn)到第（6）步。

（5）節(jié)點(diǎn)N計(jì)算自己的緩存使用率r，根據(jù)所處的擁塞等級(jí)和消息m的類別，按照自適應(yīng)的接收策略，以表1中的概率，決定是否接收消息，分別向節(jié)點(diǎn)M返回接收或拒收的應(yīng)答。拒收的類型是“擁塞”，表示對(duì)方節(jié)點(diǎn)為避免擁塞而拒絕此次發(fā)送嘗試。

（6）節(jié)點(diǎn)M 檢查應(yīng)答的類型，如果是“接收”，則正式開始復(fù)制轉(zhuǎn)發(fā)消息m。否則重新返回到第（2）步，進(jìn)行下一次嘗試。另外，如果拒收類型是“已有”，則對(duì)消息m的計(jì)數(shù)加1，超過閾值則刪除消息m并將計(jì)數(shù)置為-1。

（7）節(jié)點(diǎn)N開始接收消息m。如果可用緩存空間不足，就依次丟棄消息隊(duì)列的隊(duì)尾消息釋放空間。假設(shè)消息成功傳輸了，如果N是消息m的目的節(jié)點(diǎn)，則分別在M和N的交付消息標(biāo)識(shí)列表中添加一條消息m的記錄；否則將消息m插入節(jié)點(diǎn)N中消息隊(duì)列的合適位置，在相遇計(jì)數(shù)列表中添加一條m的記錄并將計(jì)數(shù)初始化為0。

這種動(dòng)態(tài)策略與靜態(tài)策略相比大大提高了控制的靈活性，可以根據(jù)網(wǎng)絡(luò)的狀態(tài)變化不斷調(diào)整，從而保證網(wǎng)絡(luò)的整體性能。且擁塞狀態(tài)劃分不依賴于全局的變量，每個(gè)節(jié)點(diǎn)僅僅根據(jù)自己的緩存利用狀態(tài)做出自主決策，空閑存儲(chǔ)空間較充足時(shí)作為中繼者多接收些消息，空閑空間不足時(shí)少接收消息，有必要時(shí)則采用消息丟棄策略舍棄部分消息。受限于DTN的網(wǎng)絡(luò)特殊性，全局網(wǎng)絡(luò)狀態(tài)變量很難獲得，這種不依賴于全局信息的節(jié)點(diǎn)自主局部決策是更符合實(shí)際需求的。

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

3.1 實(shí)驗(yàn)設(shè)置

本文實(shí)驗(yàn)所用的仿真工具是ONE模擬器[16]（Opportunistic Network Environment simulator），是專門設(shè)計(jì)用來評(píng)估DTN路由和應(yīng)用協(xié)議的工具。實(shí)驗(yàn)場景中，仿真世界大小為2 500 m×2 500 m，共有60個(gè)節(jié)點(diǎn)，采用RandomWaypoint移動(dòng)模型。該模型中，節(jié)點(diǎn)以恒定的速度運(yùn)動(dòng)到目的位置后，在該位置停留一個(gè)隨機(jī)的時(shí)間，再以隨機(jī)生成的速度勻速運(yùn)動(dòng)到區(qū)域中另一個(gè)隨機(jī)產(chǎn)生的位置，以此往復(fù)。本文主要研究的是擁塞控制策略，需要獲得存儲(chǔ)空間條件下本文提出的策略的表現(xiàn)，為此改變緩沖空間大小多次重復(fù)實(shí)驗(yàn)，其中存儲(chǔ)大小變化范圍為4～14 MB。實(shí)驗(yàn)重要參數(shù)設(shè)置如表2所示。

ACC-NS策略中有三個(gè)重要的參數(shù)，包括兩個(gè)擁塞度臨界值Rl和Rh以及消息相遇計(jì)數(shù)閾值n。為了便于將ACC-NS策略與傳染路由（Epidemic）和散發(fā)等待路由（SNW）協(xié)議進(jìn)行對(duì)比。固定ACC-NS策略中參數(shù)的取值，令Rl=0.6,Rh=0.9,n=4，將會(huì)在后面給出關(guān)于不同參數(shù)取值的結(jié)果與討論。

為了將ACC-NS協(xié)議與另外的兩種協(xié)議對(duì)比，Epidemic、SNW的相關(guān)設(shè)置與上面的設(shè)置保持一致。針對(duì)每個(gè)變化的存儲(chǔ)空間，調(diào)整最大副本數(shù)進(jìn)行重復(fù)實(shí)驗(yàn)，找出對(duì)應(yīng)于每個(gè)緩沖空間大小的最合適的最大副本數(shù)值，以這種最好的路由狀態(tài)參與對(duì)比。

表2 仿真參數(shù)設(shè)置

實(shí)驗(yàn)分別從消息交付率（delivery ratio）、消息傳輸開銷比（delivery overhead ratio）、消息平均延時(shí)（average delivery latency）和平均緩存使用率（average buffer usage ratio）四方面進(jìn)行對(duì)比和分析，實(shí)驗(yàn)結(jié)果和分析如下。

3.2 實(shí)驗(yàn)結(jié)果分析

由圖4可知，ACC-NS策略可以保證特殊消息有較高的交付率，同時(shí)整體消息交付率也較另兩種協(xié)議有所提高。消息傳輸開銷比按式（3）計(jì)算，其中relayed為總的消息轉(zhuǎn)發(fā)次數(shù)，delivered為成功交付的消息數(shù)量。圖5表明，ACC-NS策略可以顯著減小消息傳輸開銷比。這是因?yàn)锳CC-NS策略限制了消息的接收行為，避免盲目的消息接收帶來頻繁的消息丟棄。

圖4 消息交付率隨緩沖空間大小變化圖

圖5 消息傳輸開銷隨緩沖空間大小變化圖

由于限制了節(jié)點(diǎn)間消息的流通，ACC-NS策略的消息平均延時(shí)和另兩種協(xié)議相比有略微的增加，如圖6所示。最后對(duì)比了三種協(xié)議中平均緩存使用率隨時(shí)間的變化情況，如圖7所示。其中Epidemic算法和SNW算法的曲線變化趨勢(shì)圖有很多相似，平均緩存使用率會(huì)迅速增長達(dá)到高峰并趨于穩(wěn)定。因?yàn)镋pidemic路由對(duì)消息的發(fā)送和接收沒有限制，SNW路由噴射副本數(shù)對(duì)消息發(fā)送的限制作用也很小，故兩者的曲線變化很相似。隨著時(shí)間的變化消息迅速累積，平均緩存使用率迅速增長，直到緩沖空間幾乎被占滿，此后一直保持緩存占滿的狀態(tài)。而ACC-NS策略的使用率增長較為平和，且趨于穩(wěn)定后的平均緩存使用率較另兩種協(xié)議低很多。ACC-NS則限制了節(jié)點(diǎn)接收新消息，當(dāng)發(fā)生擁塞時(shí)擁塞程度越大則節(jié)點(diǎn)接收消息的概率越小，從而減緩了消息進(jìn)入緩沖空間的速率。當(dāng)網(wǎng)絡(luò)運(yùn)行時(shí)間足夠長時(shí)，三種協(xié)議的平均緩存使用率隨著時(shí)間的變化趨于穩(wěn)定，僅僅只有小幅度的波動(dòng)。這表明ACC-NS策略可以較好地控制緩存空間的增長速度，將數(shù)據(jù)流量較為均勻地分布到網(wǎng)絡(luò)中的節(jié)點(diǎn)。

圖6 消息平均延時(shí)隨緩沖空間大小變化圖

圖7 平均緩存使用率隨運(yùn)行時(shí)間變化圖

3.3 相關(guān)參數(shù)討論

在固定Rl和緩沖大小的情況下，Rh由0.65每次遞增0.1直到0.95，傳輸率、開銷比等隨著變化的結(jié)果如表3所示?？傁鬏斅屎拖⑵骄訒r(shí)波動(dòng)很小，而特殊消息傳輸率和傳輸開銷比隨著Rh的增加遞增很明顯。Rh設(shè)置得越小，節(jié)點(diǎn)越容易進(jìn)入重?fù)砣麪顟B(tài)，網(wǎng)絡(luò)中進(jìn)入重?fù)砣墓?jié)點(diǎn)占比越大，消息的傳遞方式越趨近于直接交付，而直接交付是開銷比最小的一種路由方式，使得網(wǎng)絡(luò)整體傳輸開銷比越小。節(jié)點(diǎn)在進(jìn)入重?fù)砣笆且愿怕?接收特殊消息，之后接收特殊消息的幾率大大減小，Rh設(shè)置越大意味著特殊消息有更多的機(jī)會(huì)和更久的時(shí)間享受特殊的接收待遇，導(dǎo)致明顯的特殊消息傳輸率的提升。特殊消息傳輸率更高的同時(shí)，也帶來了更大的傳輸開銷比，因此實(shí)際網(wǎng)絡(luò)中需要權(quán)衡選擇一個(gè)更恰當(dāng)?shù)闹怠?/p>

表3 重?fù)砣R界值對(duì)仿真結(jié)果的影響

輕擁塞臨界值Rl對(duì)仿真結(jié)果的影響如表4所示。在固定緩沖空間大小和Rh的情況下，隨著Rl的變化，傳輸開銷比和消息平均延時(shí)波動(dòng)很小，變化不是很明顯，總消息傳輸率隨著Rl增大而增大，特殊消息傳輸率隨著Rl增大而減小，這種趨勢(shì)是符合預(yù)期的。Rl是節(jié)點(diǎn)進(jìn)入輕擁塞的臨界值，當(dāng)緩存使用率低于Rl的時(shí)候所有消息都是以概率1被節(jié)點(diǎn)所接收，Rl越大會(huì)給普通消息更多的接收機(jī)會(huì)，從而提高總體的消息傳輸率；同時(shí)Rl增大會(huì)讓Rl到Rh的區(qū)段越小，當(dāng)節(jié)點(diǎn)進(jìn)入輕擁塞后特殊消息享有的特殊接收待遇區(qū)間也變小了，導(dǎo)致特殊消息傳出率會(huì)下降。可以看到特殊消息傳輸率和總的消息傳輸率是難以同時(shí)提高的，因?yàn)榫W(wǎng)絡(luò)中的資源是限定的。這兩種傳輸率是部分與整體的關(guān)系，依特殊消息的服務(wù)質(zhì)量需求可以相應(yīng)調(diào)整Rl的大小，在局部需求和總體需求之間取得最合適的平衡。

表4 輕擁塞臨界值對(duì)仿真結(jié)果的影響

固定Rl、Rh和緩沖空間大小，依次將計(jì)數(shù)閾值加1，最大相遇計(jì)數(shù)閾值對(duì)仿真結(jié)果的影響如表5所示。從表中可以看出，當(dāng)計(jì)數(shù)閾值為2的時(shí)候，網(wǎng)絡(luò)各方面性能表現(xiàn)很差，此時(shí)相遇丟棄率更是達(dá)到了80%以上。消息副本的兩種丟棄方式中，VACCINE是一種可靠的消息丟棄，而基于計(jì)數(shù)閾值的消息副本丟棄是一種不可靠的估計(jì)丟棄。當(dāng)計(jì)數(shù)閾值設(shè)置得太小，消息來不及生成很多副本就被清除了，表現(xiàn)為很高的相遇丟棄率。當(dāng)計(jì)數(shù)閾值進(jìn)一步增大，情況會(huì)好得多，表中閾值設(shè)置為3的時(shí)候總消息傳輸率和消息平均延時(shí)都是最好的，但是特殊消息傳輸率偏小。相遇計(jì)數(shù)閾值設(shè)置為4和5時(shí)顯著提高了特殊消息傳輸率。

表5 最大相遇計(jì)數(shù)閾值對(duì)仿真結(jié)果的影響

實(shí)際上，ACC-NS中的控制參數(shù)是可以根據(jù)實(shí)際網(wǎng)絡(luò)需求來調(diào)整的。在其他條件不變的情況下，增大Rh會(huì)提高特殊消息的傳輸率，但會(huì)造成更大的消息傳輸開銷比。增大Rl會(huì)提高總的消息傳輸率，但會(huì)降低特殊消息的傳輸率。在消息相遇計(jì)數(shù)很小的時(shí)候，因相遇計(jì)數(shù)超過閾值而丟棄的消息數(shù)量占丟棄總數(shù)的比例很高，而計(jì)數(shù)丟棄方式是一種不穩(wěn)定的清除方式，不穩(wěn)定因素占主導(dǎo)使得網(wǎng)絡(luò)各方面性能表現(xiàn)較差。增大相遇計(jì)數(shù)會(huì)提高消息的交付率，但是過大的計(jì)數(shù)閾值不會(huì)帶來性能的進(jìn)一步提升，因計(jì)數(shù)超過閾值而清除的消息占比已經(jīng)很小了。當(dāng)節(jié)點(diǎn)緩沖空間較大時(shí)，相應(yīng)的Rh和n的取值可以適當(dāng)增大些?？傊梢愿鶕?jù)實(shí)際網(wǎng)絡(luò)環(huán)境和服務(wù)需求，調(diào)整參數(shù)使得網(wǎng)絡(luò)的性能達(dá)到較好的平衡。

4 結(jié)束語

本文提出了ACC-NS路由策略，這是一種動(dòng)態(tài)的擁塞控制策略，節(jié)點(diǎn)根據(jù)自己的狀態(tài)和消息的類別動(dòng)態(tài)調(diào)整消息的接收概率，使得數(shù)據(jù)流量可以較為均勻地分布到網(wǎng)絡(luò)中。針對(duì)網(wǎng)絡(luò)中的冗余副本，結(jié)合了兩種方法，可以更為有效地清除多余副本。除此之外，本文在擁塞控制的同時(shí)做了一些QoS方面的控制，可以滿足特殊消息的較高傳輸率要求，同時(shí)總體的消息傳輸率也有所提高。仿真結(jié)果表明，本文提出的策略可以提高網(wǎng)絡(luò)性能和減小傳輸開銷。

參考文獻(xiàn)：

[1]Li Y，Hui P，Jin D，et al.Delay-tolerant network protocol testing and evaluation[J].IEEE Communications Magazine，2015，53（1）：258-266.

[2]Chen I R，Bao F，Chang M J，et al.Dynamic trust management for delay tolerant networks and its application to secure routing[J].IEEE Transactionson Parallel&Distributed Systems，2014，25（5）：1200-1210.

[3]Tornell S M，Calafate C T，Cano J C，et al.DTN protocols for vehicular networks：An application oriented overview[J].IEEE Communications Surveys&Tutorials，2015，17（2）.

[4]Elshafee A，El Menshawi M，Saeed M.Integrating social network services with vehicle tracking technologies[J].International Journal of Advanced Computer Science&Applications，2013，72：22-30.

[5]Conan V，F(xiàn)riedman T，Leguay J.DTN routing in a mobility pattern space[J].Computer Science，2012：276-283.

[6]Xiao M，Wu J，Huang L.Home-based zero-knowledge multi-copy routing in mobile social networks[J].IEEE Transactions on Parallel&Distributed Systems，2015，26（5）：1238-1250.

[7]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）.

[8]Kafi M A，Djenouri D，Ben-Othman J，et al.Congestion control protocols in wireless sensor networks：A survey[J].IEEE Communications Surveys&Tutorials，2014，16（3）：1369-1390.

[9]Silva A P，Burleigh S，Hirata C M，et al.A survey on congestion control for delay and disruption tolerant networks[J].Ad Hoc Networks，2015，25：480-494.

[10]Vahdat A，Becker D.Epidemic routing for partially connected ad hoc networks，CS-200006[R].Duke University，2000.

[11]Spyropoulos T，Psounis K，Raghavendra C S.Spray and wait：an efficient routing scheme for intermittently connectedmobilenetworks[C]//ACM SIGCOMM Workshop on Delay-Tolerant Networking，2005：252-259.

[12]Walker B D，Glenn J K，Clancy T C.Analysis of simple counting protocols for delay-tolerant networks[C]//The Workshop on Challenged Networks，2007：19-26.

[13]Seligman M，F(xiàn)all K，Mundur P.Alternative custodians for congestion control in delay tolerant networks[C]//SIGCOMM Workshop on Challenged Networks，2006：229-236.

[14]Seligman M，F(xiàn)all K，Mundur P.Storage routing for DTN congestion control：Research articles[J].Wireless Communications&Mobile Computing，2007，7（10）：1183-1196.

[15]Small T，Haas Z J.Resource and performance tradeoffs in delay-tolerant wireless networks[C]//ACM Workshop on Delay Tolerant Networking，2005：260-267.

[16]Ker，Nen A，Ott J，et al.The ONE simulator for DTN protocol evaluation[C]//International Conference on Simulation TOOLS and Techniques for Communications，Networks and Systems，Simutools 2009，Rome，Italy，2009.