摘 要： 提出一種針對(duì)緩存容量受限的容遲移動(dòng)網(wǎng)絡(luò)的多復(fù)制路由和緩存管理的方法。該方法能充分利用有限的網(wǎng)絡(luò)資源，實(shí)現(xiàn)更高的傳送成功率，降低平均發(fā)送延遲，同時(shí)實(shí)現(xiàn)不同重要性報(bào)文的服務(wù)質(zhì)量分級(jí)。
關(guān)鍵詞： 容遲移動(dòng)網(wǎng)絡(luò)； 容量受限； 多復(fù)制路由

　　當(dāng)前的Internet體系結(jié)構(gòu)和其中許多協(xié)議不能很好地適用于存在高延時(shí)路徑和頻繁分裂的網(wǎng)絡(luò)。像陸地移動(dòng)網(wǎng)絡(luò)、軍事無(wú)線自組織網(wǎng)絡(luò)、星際網(wǎng)絡(luò)及傳感器網(wǎng)絡(luò)等都存在網(wǎng)絡(luò)斷開的問(wèn)題，這一類的網(wǎng)絡(luò)被稱作為受限網(wǎng)絡(luò)。容遲網(wǎng)絡(luò)DTN（Delay Tolerant Network）是一種新型的網(wǎng)絡(luò)，最早在2003年的國(guó)際會(huì)議上由FALL K提出[1]。DTN網(wǎng)絡(luò)通常延遲比較大，網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)不斷變化，不能用傳統(tǒng)的路由方法來(lái)解決。所以DTN網(wǎng)絡(luò)體系結(jié)構(gòu)中采用了基于信息存儲(chǔ)轉(zhuǎn)發(fā)的端到端覆蓋層——捆綁層。捆綁層的重要組成部分之一是保管傳遞，將信息從一個(gè)DTN保管節(jié)點(diǎn)可靠地傳輸?shù)较乱粋€(gè)保管節(jié)點(diǎn)等候轉(zhuǎn)發(fā)，直到遇到目的節(jié)點(diǎn)為止[2]。為了維持這個(gè)保管傳遞，每個(gè)節(jié)點(diǎn)都需要一定的轉(zhuǎn)發(fā)緩存來(lái)暫存其他節(jié)點(diǎn)發(fā)送過(guò)來(lái)的數(shù)據(jù)，等到合適的時(shí)機(jī)再傳給下個(gè)節(jié)點(diǎn)。
　　近距離無(wú)線社會(huì)網(wǎng)絡(luò)就是一種利用社會(huì)中普遍存在的“弱鏈接”關(guān)系的無(wú)線自組織網(wǎng)絡(luò)，它符合DTN網(wǎng)絡(luò)的特點(diǎn)，并充分利用社會(huì)群體的移動(dòng)特性與短距離無(wú)線通信相結(jié)合所帶來(lái)的空間復(fù)用能力，提高社會(huì)網(wǎng)絡(luò)的吞吐量，降低社會(huì)網(wǎng)絡(luò)對(duì)固定設(shè)備的依賴性，增強(qiáng)對(duì)不同應(yīng)用的適應(yīng)能力。因此，無(wú)線社會(huì)網(wǎng)絡(luò)在小型移動(dòng)傳感器網(wǎng)絡(luò)、手持通信設(shè)備的基礎(chǔ)上可以實(shí)現(xiàn)火災(zāi)預(yù)警、高危人群身體健康狀況監(jiān)控、廣告信息投遞等各種類型的社會(huì)功能。
　　DTN網(wǎng)絡(luò)的路由技術(shù)是DTN網(wǎng)絡(luò)研究的重要方向之一。DTN的路由可以分為兩類：?jiǎn)尾ヂ酚蒣3]和多復(fù)制路由。
　　單播路由就是在一個(gè)數(shù)據(jù)報(bào)文開始發(fā)送后，并不對(duì)其本身進(jìn)行復(fù)制，而是不斷向下一個(gè)節(jié)點(diǎn)傳遞，直到傳送到目的節(jié)點(diǎn)為止。由于數(shù)據(jù)報(bào)文只有一份，在DTN這種節(jié)點(diǎn)隨意移動(dòng)、網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)不能保證的網(wǎng)絡(luò)條件下，難以確保這唯一一份報(bào)文能否向正確的方向傳輸，可能造成數(shù)據(jù)不能到達(dá)或者延遲非常大。
　　多復(fù)制路由的優(yōu)點(diǎn)是采用多條路徑傳輸，有更大的幾率以比較低的延遲將報(bào)文傳送到目的節(jié)點(diǎn)，代價(jià)是復(fù)制出來(lái)的報(bào)文拷貝大量占用轉(zhuǎn)發(fā)節(jié)點(diǎn)的轉(zhuǎn)發(fā)緩存，如果緩存空間占滿導(dǎo)致不能再接收新的轉(zhuǎn)發(fā)數(shù)據(jù)，則結(jié)果是得不償失的。
　　在DTN多復(fù)制路由中，常用的方法是路由擴(kuò)散(Epidemic Routing)[4]。路由擴(kuò)散是洪泛的極端情況，因?yàn)樗噲D在所有的路徑上發(fā)送報(bào)文。這會(huì)產(chǎn)生很大的冗余，但是對(duì)節(jié)點(diǎn)和網(wǎng)絡(luò)錯(cuò)誤很健壯，如果資源充足，它會(huì)選擇傳輸時(shí)間最小的路徑。
　　源節(jié)點(diǎn)復(fù)制路由(Source Spay)[5]的提出就是為了控制泛洪的規(guī)模，避免太大的冗余。當(dāng)報(bào)文在源節(jié)點(diǎn)產(chǎn)生時(shí)，除了一個(gè)唯一的ID用來(lái)表示以外，還在報(bào)文頭上附上一個(gè)復(fù)制許可計(jì)數(shù)器，記錄該報(bào)文被許可復(fù)制的份數(shù)N。當(dāng)N值大于0時(shí)，該報(bào)文還能被復(fù)制到轉(zhuǎn)發(fā)節(jié)點(diǎn)，N為0時(shí)就停止復(fù)制。每當(dāng)這個(gè)報(bào)文從源節(jié)點(diǎn)被復(fù)制到一個(gè)轉(zhuǎn)發(fā)節(jié)點(diǎn)時(shí)，源節(jié)點(diǎn)中的復(fù)制許可計(jì)數(shù)器減一，而轉(zhuǎn)發(fā)節(jié)點(diǎn)只轉(zhuǎn)發(fā)，沒(méi)有權(quán)限對(duì)報(bào)文進(jìn)行復(fù)制。
1 路由和緩存管理方法的設(shè)計(jì)和實(shí)現(xiàn)
1.1 路由
　　本文采用的路由方法是基于多復(fù)制路由的思路。路由擴(kuò)散方法泛洪規(guī)模過(guò)大，對(duì)節(jié)點(diǎn)轉(zhuǎn)發(fā)緩存要求太高；而源節(jié)點(diǎn)復(fù)制路由的復(fù)制環(huán)節(jié)在源節(jié)點(diǎn)處，范圍有限。本文采用一種能夠充分利用網(wǎng)絡(luò)縱深的復(fù)制路由方法——二分法復(fù)制，獲得比路由擴(kuò)散或源節(jié)點(diǎn)復(fù)制路由更好的效果。與源節(jié)點(diǎn)復(fù)制路由方法類似，報(bào)文在源節(jié)點(diǎn)產(chǎn)生時(shí)，也有一個(gè)復(fù)制許可計(jì)數(shù)器，記錄該報(bào)文被許可復(fù)制的份數(shù)N。當(dāng)N值大于0時(shí)，該報(bào)文還能被復(fù)制到轉(zhuǎn)發(fā)節(jié)點(diǎn)，N為0時(shí)就停止復(fù)制。當(dāng)這個(gè)報(bào)文被復(fù)制到目的節(jié)點(diǎn)時(shí)，發(fā)送節(jié)點(diǎn)把一半的復(fù)制許可交給對(duì)方節(jié)點(diǎn)，即雙方報(bào)文中復(fù)制許可計(jì)數(shù)器的值都變成N/2。在節(jié)點(diǎn)相遇時(shí)，如果對(duì)方節(jié)點(diǎn)沒(méi)有該報(bào)文并且復(fù)制許可計(jì)數(shù)器的值大于1，則繼續(xù)二分法復(fù)制，直到許可域的值為1。這里N的初始值就用2的整數(shù)次冪。二分法復(fù)制使復(fù)制環(huán)節(jié)不局限在源節(jié)點(diǎn)處，同時(shí)又控制了泛洪的規(guī)模。
1.2 緩存管理機(jī)制
　　緩存管理機(jī)制主要是處理緩存已經(jīng)占滿，同時(shí)又有新的需要轉(zhuǎn)發(fā)的報(bào)文到達(dá)的情況。
傳統(tǒng)的緩存管理一般采用先入先出(FIFO)，在緩存占滿的情況下最先到達(dá)的報(bào)文被后面到來(lái)的擠出丟棄；或者是不丟棄報(bào)文的策略，只要緩存處于占滿的狀態(tài)就不再接受新的報(bào)文。本文采用了隨機(jī)丟棄報(bào)文的策略。
當(dāng)一個(gè)節(jié)點(diǎn)的轉(zhuǎn)發(fā)緩存已滿，又遇到其他結(jié)點(diǎn)要傳送報(bào)文給它時(shí)，就隨機(jī)丟棄轉(zhuǎn)發(fā)緩存中的一個(gè)報(bào)文，接受新傳送來(lái)的報(bào)文。因?yàn)橐粋€(gè)報(bào)文在其源節(jié)點(diǎn)的源緩存中總是保留一個(gè)備份，所以在轉(zhuǎn)發(fā)緩存中的丟棄不會(huì)造成該報(bào)文的永久丟失。隨機(jī)丟棄在這種報(bào)文被多次復(fù)制的路由方法中，比起拒不接受新報(bào)文或者先入先丟棄的方法是具有一定優(yōu)勢(shì)的。因?yàn)閺娜W(wǎng)絡(luò)的整體上看，被復(fù)制的次數(shù)比較多的報(bào)文被隨機(jī)選中并丟棄的概率要大于被復(fù)制的次數(shù)少的報(bào)文。也就意味著原本傳送可能性較小、傳送難度大的報(bào)文被丟棄的概率小，一定程度上保持了公平。
1.3 移動(dòng)和相遇模型
　　考慮到系統(tǒng)的應(yīng)用背景是短距離的無(wú)線社會(huì)網(wǎng)絡(luò)，個(gè)人手持通信設(shè)備以及傳感器的傳輸距離有限，參與人數(shù)眾多，個(gè)人的移動(dòng)性比較隨機(jī)，所以本文采用隨機(jī)路點(diǎn)(Random Waypoint)[6]作為系統(tǒng)的移動(dòng)模型，最為接近現(xiàn)實(shí)情況。
2 仿真結(jié)果
　　為了評(píng)價(jià)所提出的路由方法的優(yōu)劣，本文用C++寫了一個(gè)仿真過(guò)程。由于在該效用路由方法中，底層協(xié)議不會(huì)影響到本文對(duì)路由協(xié)議的評(píng)價(jià)，所以本文把主要精力集中在路由協(xié)議的仿真運(yùn)行上。在仿真路由協(xié)議時(shí)，假設(shè)每個(gè)報(bào)文的長(zhǎng)度是有限制的，節(jié)點(diǎn)間的傳輸帶寬是足夠充裕的。兩個(gè)節(jié)點(diǎn)在相遇時(shí)，有充足的帶寬來(lái)迅速交換彼此的報(bào)文，不會(huì)出現(xiàn)報(bào)文尚未傳輸完成就丟失連接的情況。
2.1 仿真參數(shù)
　　選取一個(gè)矩形區(qū)域作為隨機(jī)路點(diǎn)模型的移動(dòng)范圍，長(zhǎng)寬a、b各為3 000 m。節(jié)點(diǎn)的移動(dòng)速度v為5 m/s~15 m/s中服從均勻分布的一個(gè)隨機(jī)值。節(jié)點(diǎn)的收發(fā)半徑r=20 m，數(shù)量為30個(gè)，轉(zhuǎn)發(fā)緩存容量為20條報(bào)文。
　　每個(gè)節(jié)點(diǎn)每隔10 s產(chǎn)生一個(gè)報(bào)文，總共產(chǎn)生100個(gè)報(bào)文。其中有10個(gè)是高優(yōu)先級(jí)的報(bào)文，90個(gè)為低優(yōu)先級(jí)的。每個(gè)報(bào)文的生存時(shí)間為500 s。所以整個(gè)系統(tǒng)的仿真時(shí)間定為1 500 s，保證最后產(chǎn)生的報(bào)文也能在系統(tǒng)仿真結(jié)束前自然消亡。
2.2 仿真結(jié)果分析
　　本文在DTN網(wǎng)絡(luò)模型中實(shí)現(xiàn)了普通的單播路由、路由擴(kuò)散以及二分法路由，在多播路由的緩存管理上嘗試了丟棄最早報(bào)文方式、拒絕新報(bào)文方式和隨機(jī)丟棄報(bào)文方式。
2.2.1 報(bào)文的傳輸失敗率
　　圖1反映的是數(shù)據(jù)包丟失的總數(shù)和緩存容量的關(guān)系。在單播路由下，由于不涉及到報(bào)文的復(fù)制，所以緩存容量對(duì)于系統(tǒng)性能沒(méi)有影響，丟失的數(shù)據(jù)包總數(shù)均為321個(gè)。路由擴(kuò)散由于不限制報(bào)文的拷貝份數(shù)，在早先時(shí)間生成的報(bào)文會(huì)被大量復(fù)制，占據(jù)緩存空間，這些報(bào)文在沒(méi)有到達(dá)目的地之前，阻止了后面生成的報(bào)文的復(fù)制傳輸，造成后續(xù)的報(bào)文難以到達(dá)目的地，在生存時(shí)間截止后被丟棄。在緩存容量較小的情況下，路由擴(kuò)散方式丟失的報(bào)文數(shù)遠(yuǎn)大于單播路由方式，證明其不適用于節(jié)點(diǎn)緩存容量較小的系統(tǒng)。隨著緩存容量的增加，路由擴(kuò)散方式的丟包數(shù)大幅下降，最后小于單播路由的丟包數(shù)。說(shuō)明當(dāng)轉(zhuǎn)發(fā)緩存不被輕易占滿的情況下，多復(fù)制路由的性能會(huì)優(yōu)于單播路由方式。二分法復(fù)制則由于考慮到節(jié)點(diǎn)轉(zhuǎn)發(fā)緩存的容量，限制了報(bào)文復(fù)制的份數(shù)。在復(fù)制份數(shù)上限為8的情況下，所有報(bào)文的丟包數(shù)隨著轉(zhuǎn)發(fā)緩存容量的增加而減小，在轉(zhuǎn)發(fā)緩存容量為60時(shí)就低于單播路由方式的丟包數(shù)，體現(xiàn)出明顯的性能優(yōu)勢(shì)。尤其是高優(yōu)先級(jí)的報(bào)文，丟包數(shù)一直穩(wěn)定在30個(gè)以下，小于10%的丟包率，并隨著轉(zhuǎn)發(fā)緩存容量的增加進(jìn)一步減小，在緩存容量為200時(shí)丟包率小于3%。低優(yōu)先級(jí)的報(bào)文在緩存容量為20時(shí)丟包率為18.1%，隨著緩存容量增加到200，丟包率減小到3%左右，和高優(yōu)先級(jí)的報(bào)文相當(dāng)。這說(shuō)明在緩存容量足夠的情況下，優(yōu)先級(jí)的高低造成的丟棄或保留對(duì)于系統(tǒng)已經(jīng)幾乎沒(méi)有影響，報(bào)文的丟失主要是因?yàn)槁窂酵耆豢蛇_(dá)。而在緩存容量較小的情況下，高優(yōu)先級(jí)的報(bào)文的丟包率明顯小于低優(yōu)先級(jí)的，說(shuō)明該路由與緩存管理策略對(duì)緊急數(shù)據(jù)的傳輸有較好的支持。

2.2.2 報(bào)文的平均傳輸延遲
　圖2 比較了三種不同的緩存管理策略的平均傳輸延遲表現(xiàn)。轉(zhuǎn)發(fā)緩存容量固定為20，在復(fù)制許可份數(shù)較小的情況下，三種緩存管理策略的差異不大。拒絕接受新報(bào)文方式在復(fù)制許可數(shù)超過(guò)4之后延遲反而增加，說(shuō)明先前的報(bào)文沒(méi)發(fā)送出去時(shí),后面的報(bào)文無(wú)法被復(fù)制、傳輸，直接增加了這些報(bào)文的延遲，所以出現(xiàn)性能下降。當(dāng)選擇兩種丟棄方式后，報(bào)文的平均傳輸延遲在復(fù)制許可份數(shù)為8時(shí)獲得最低值，而在復(fù)制許可份數(shù)為16時(shí)平均延遲略有增加。說(shuō)明在轉(zhuǎn)發(fā)緩存容量為20時(shí)，太多的復(fù)制許可份數(shù)反而造成部分報(bào)文被不必要地大量復(fù)制，而有些報(bào)文得不到復(fù)制機(jī)會(huì)，反而影響了總的平均延遲。8份復(fù)制許可的二分法復(fù)制方式是最為合適的。由于隨機(jī)丟棄方式在總體上丟棄已經(jīng)被復(fù)制較多次數(shù)的報(bào)文的概率大一些，而被復(fù)制次數(shù)少的報(bào)文被隨機(jī)選中丟棄的概率小一些，這從一定程度上保證了公平，使那些后來(lái)的報(bào)文剛開始能多保留一些備份進(jìn)行傳輸，所以性能略優(yōu)于丟棄最早報(bào)文方式。

　　圖3比較了不同路由方式下的平均傳輸延遲。如前文所述，單播路由的延遲不隨緩存容量的增加而變化。路由擴(kuò)散方式在緩存容量較小時(shí)延遲最大，隨著緩存容量增加，延遲顯著減小。而二分法復(fù)制始終擁有較小的傳輸延遲，在緩存容量超過(guò)80后延遲的減小趨于平穩(wěn)。復(fù)制許可N=4的平均延遲始終高于N=8或16的平均延遲，說(shuō)明未能充分利用轉(zhuǎn)發(fā)緩存。復(fù)制許可N=8、緩存小于160時(shí)，平均延遲小于N=16的情況，說(shuō)明當(dāng)緩存不夠大時(shí)，太多的復(fù)制許可份數(shù)反而影響總平均延遲。因此在緩存容量不是非常充裕時(shí)，復(fù)制許可為8份能夠提供最小的傳輸延遲。

　　最后在N=8的情況下比較高低兩種優(yōu)先級(jí)報(bào)文的平均延遲。由圖4可以看出，本文中針對(duì)不同優(yōu)先級(jí)報(bào)文的處理方式保證了無(wú)論緩存容量充裕與否，高優(yōu)先級(jí)報(bào)文的平均延遲都明顯小于低優(yōu)先級(jí)報(bào)文，在緩存容量較小的情況下，這種優(yōu)勢(shì)尤為明顯。

　　本文主要對(duì)DTN網(wǎng)絡(luò)的多復(fù)制路由方法進(jìn)行改進(jìn)，充分利用有限的轉(zhuǎn)發(fā)緩存空間來(lái)保證傳輸成功率和延遲時(shí)間。使用控制復(fù)制份數(shù)的二分法復(fù)制來(lái)進(jìn)行多復(fù)制路由，使用基于復(fù)制許可數(shù)和報(bào)文優(yōu)先級(jí)的隨機(jī)丟棄方式處理不同報(bào)文爭(zhēng)搶有限轉(zhuǎn)發(fā)緩存的矛盾，獲得了更高的傳輸成功率和更低的平均傳輸延遲。本文還針對(duì)不同優(yōu)先級(jí)報(bào)文采用不同的復(fù)制路由和緩存管理策略，在略微犧牲低優(yōu)先級(jí)報(bào)文傳輸性能的代價(jià)下，使高優(yōu)先級(jí)報(bào)文的傳輸性能得到顯著提升。
參考文獻(xiàn)
[1]  FALL K. A delay-tolerant network architecture for challenged internets. In Proceedings ACM SIGCOMM，2003，August 2003:25-29.
[2]  FALL K， HONG W， MADDEN S.  Custody transfer for reliable delivery in delay tolerant networks. Technical Report IRB-TR-03-030，Intel Research Berkeley，2003.
[3]  JAIN S, FALL K, PATRA R. Routing in a delay tolerant network. In Proceedings of ACM SIGCOMM,ACM Press, 2004,34:145-158.
[4]  VAHDAT A, BECKER D. Epidemic routing for partially-connected ad hoc networks,” Duke University, Tech. Rep., July 2000.
[5]  THRASYVOULOS SPYROPOULOS K P, RAGHAVENDRA C S. Spray and wait: an efficient routing scheme for intermittently connected mobile networks. in WDTN-05, 2005.
[6]  JOHNSON D B, MALTZ D A. Dynamic source routing in ad hoc wireless networks. In Tomasz Imielinski and Hank Korth, editors, Mobile Computing.Kluwer Academic Publishers, 1996. Chapter 5, 353:153-181.