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

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

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

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

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

　　本文主要對DTN網絡的多復制路由方法進行改進，充分利用有限的轉發(fā)緩存空間來保證傳輸成功率和延遲時間。使用控制復制份數(shù)的二分法復制來進行多復制路由，使用基于復制許可數(shù)和報文優(yōu)先級的隨機丟棄方式處理不同報文爭搶有限轉發(fā)緩存的矛盾，獲得了更高的傳輸成功率和更低的平均傳輸延遲。本文還針對不同優(yōu)先級報文采用不同的復制路由和緩存管理策略，在略微犧牲低優(yōu)先級報文傳輸性能的代價下，使高優(yōu)先級報文的傳輸性能得到顯著提升。
參考文獻
[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.