基于鄰居節點位置的受控傳染DTN 路由算法

李建波，由 磊，姜 山，戴晨曲，徐吉興

(青島大學信息工程學院，山東 青島 266071)

1 概述

容遲網絡(Delay Tolerant Networks，DTN)是近年來無線網絡領域內的一個研究熱點，泛指部署在極端環境下由于節點的移動或者能量調度等原因而導致節點間只能間歇性進行通信甚至長時間處于中斷狀態的一類網絡。其概念起源于星際互聯網絡(Inter Planetary Internet，IPN)，其主要目的是為了將因特網中的協議應用到星際之間的網絡互聯中。為此，國際互聯網研究任務組(Internet Research Task Force，IRTF)專門成立了星際網絡研究小組(Inter Planetary Internet Research Group，IPNRG)。星際網絡中消息傳輸的主要問題是長傳播時延，其過長的傳播時延會導致現有的網絡協議失效。非對稱的帶寬以及低比特率等也都給網絡協議設計帶來了非常大的困難和挑戰。

在2001 年和2002 年，IPN 研究者嘗試將IPN 的架構應用于其他一些陸地上的挑戰性網絡中，如用于發展中國家偏遠地區通信和Internet 接入服務的信息網絡［1］、湖泊環境下的水聲傳感器網［2］、野生動物追蹤網絡以及高速行駛的車輛組成的車輛Ad Hoc網絡［3-4］等。這些網絡具有間歇連接、時延極高、頻繁割裂、非對稱數據率、安全性差、較高的誤碼率與丟包率以及異構互聯等特性［5-6］。然而，與IPN 不同的是，陸地上的挑戰性網絡由于節點的強移動性等特點，其更加強調節點之間連接的頻繁中斷(disruption)，而IPN 由于節點之間具有極遠的距離，其更加強調節點之間傳播的高時延(delay)。2004 年，文獻［7］提出一種用于此類挑戰性網絡的架構，自此容遲網絡引起了空前的廣泛關注。隨著相關研究成果不斷涌現，容遲網絡這一名稱逐漸被研究者們接受，并被作為一個兼容各類異構網絡的覆蓋網絡的架構標準［8-9］，目前，容遲網絡已經成為網絡界最為熱門的研究課題之一。

如何做出正確高效的路由選擇一直是無線網絡領域內的關鍵技術和主要研究課題。傳統的基于TCP/IP 的Internet 路由協議、移動Ad Hoc 網絡和無線傳感網絡的路由協議均假設某一時刻存在一個穩定連通的端到端的通信鏈路［10］。但是這一假設在容遲網絡中不再成立，由于容遲網絡中的節點具有高度移動性并且稀疏部署，這將導致容遲網絡中的拓撲結構動態變化以及鏈路時斷時續，因此在某個時刻或者某段時間內不存在端到端路徑［11］。正是由于傳輸鏈路的這種時變性和不確定性使得容遲網絡中的路由研究是一項挑戰性的課題，因此設計可靠有效的容遲網絡路由算法來提高網絡連接性、降低能量消耗和時延、增加消息投遞率成為容遲網絡研究的一個核心問題。容遲網絡中的路由算法研究作為一項關鍵技術成為新一代無線通信網絡研究領域備受關注的前沿熱點課題。

文獻［12］提出的傳染病(epidemic)路由算法是基于傳染策略的一個代表性算法。文獻［13-15］在傳染策略上做了改進，如限制最大跳數以及副本數目，對隊列中待轉發的包進行排序等。文獻［16］提出的適用于星際網絡的路由算法是基于效用函數進行轉發的路由策略的典型代表，它將容遲網絡建模為有向多圖模型(即將網絡建模為多個連通的有向子圖，將子圖中的有向邊表示為節點間鏈路容量和傳輸時延的函數)，并提出了FC，MED，ED，EDLQ，EDAQ 和LP 6 個算法。文獻［17-19］進一步討論了基于效用函數進行下一跳選擇的路由策略。文獻［20］利用社會網絡中的集群性(community)概念，采用社區標簽(community label)來標識每個節點所屬的群體，節點在轉發消息時，要么轉發給消息目標節點，要么轉發給與消息目標節點所處在同一群體的節點。文獻［21］區別于文獻［20］，其利用節點的相似性(即節點的共同行為特征和興趣愛好等)和向心性(包括廣泛度、中介度和密切度3 種，用來衡量節點與其他節點的聯系能力)設計效用函數，并讓消息向效用更高的節點進行移交。實驗證明，在容遲網絡中利用社會網絡的概念，能夠在保證一定投遞率的基礎上減少網絡負載［22］。

本文采用多拷貝策略增加消息的投遞概率，并利用節點的一跳以內的位置信息，基于余弦定理設計路由選擇算法，從而實現消息的受控傳染。

2 路由設計

2.1 路由思想

大量研究結果表明，在挑戰性網絡中多拷貝策略是一個有效提高消息投遞率的方法［23-24］。然而，這類挑戰性網絡中的緩存資源以及能耗往往被嚴格限制，盲目地進行無選擇復制會快速耗盡網絡資源，從而降低路由性能。目前有很多研究成果，其策略是基于節點效用進行選擇復制，以實現受控傳染。然而，多數都需要依賴假設可知的拓撲信息或信息分發策略等。在機會網絡中，由于拓撲變化的頻繁以及高時延鏈路，維護和更新一張路由表是極其困難的，其原因是頻繁的拓撲變化以及高時延會使得拓撲更新信息難以分發，從而降低該類路由算法的實用性。即使能夠保證拓撲更新信息到達其他節點，高時延會讓信息的時效性減弱，從而導致選路的準確性下降。

從消息的時效性以及易得性方面來考慮，一跳鄰居信息較為可靠。首先，節點可以依靠周期性發送廣播包以探測其鄰居節點，并可在其中包含自身信息以通知其鄰居節點。鄰居節點可用攜帶信息的數據包予以響應。一輪探測結束后，該節點和其鄰居即可互相獲知對方信息。從另一方面講，當長期未收到來自鄰居的探測或響應信息，節點可認為該鄰居已不再活躍，可將其從所維護的鄰居節點中刪除。然而，若維護兩跳信息，問題就變得復雜很多。

本文提出基于節點位置信息的受控傳染(Location-based Controlled Epidemic，LC-Epidemic)路由算法，并保守假設只有一跳鄰居信息可以被實時獲得并利用。除此之外，不假設任何已知的關于目的節點的信息，包括目的節點的坐標。為了增大消息的投遞率，采用多拷貝策略進行消息洪泛，并利用節點的位置信息，對可用節點進行篩選以實現受控傳染。本文算法選擇距離較遠的節點能夠讓消息在網絡中獲得更大的覆蓋面積，從而增大消息傳遞到目的節點的可能性。

2.2 下一跳選擇算法

文獻［23］中對路由研究進行了總結:(1)實施多副本策略往往能夠有效增加投遞率;(2)實施多副本策略能夠有效降低投遞時延;(3)實施多副本策略會增加節點的能耗;(4)實施多副本策略會增加緩存需求可知，在容遲網絡中實施多拷貝策略有利有弊，一方面，在網絡資源充足的情況下，多副本策略能夠有效改善投遞率和投遞時延;另一方面，在實際情況中，網絡中節點的可用緩存以及能量等通常是嚴格受限的，盲目的進行洪泛策略，會導致網絡資源迅速耗盡，帶來網絡擁塞，從而降低路由性能表現，這就要求路由算法的設計者要考慮每一次復制及轉發操作的有效收益，從而合理進行下一跳節點選擇。文獻［23］中還提出了2 條路由設計準則:(1)節點應該有目標地選擇下一跳。在容遲網絡中，節點的緩存和能量嚴格受限。此外，緩存資源可通過刪除已存信息或完成投遞操作而重新獲得，然而能耗卻是難以恢復的。這就要求路由設計者應當采取一種合理的下一跳選擇策略，并對副本數量做一定限制。(2)節點需要做出有一定風險的選擇。在容遲網絡中，往往只能在一定程度上預測某節點與目的節點之間的期望接觸概率(或在某段時間之內節點的接觸概率)，然而實際上與目的節點真正接觸的，可能是期望概率較小的節點。因此，設計者在設計下一跳選擇算法時，也需考慮在讓節點做選擇時冒一定風險，即在一定程度上放寬對副本數量的限制。

基于以上2 條準則，本文提出基于節點位置信息的受控傳染路由算法LCE。假設節點只能獲得一跳以內的鄰居節點的位置信息，為了實現高投遞率，讓節點選擇張角最大的2 個鄰居節點進行復制，以盡可能增大所投遞消息在網絡中的覆蓋范圍。此外，略微放寬對消息副本數量的限制，即每個節點在完成消息復制操作后，仍然保留該消息的拷貝，以便在適當時機重新選擇新的中繼節點進行傳遞。

當網絡中節點分布較為稀疏時，對于每個節點，其周圍同時可用的一跳鄰居節點往往較少。若當前周圍無可用的鄰居節點，將把消息存入節點緩存中進行保管，以等待出現可用連接時進行傳遞。當可用鄰居節點數目小于2 個，可以推測網絡中節點的分布可能較稀疏。這意味著節點之間的接觸機會非常少。此時，遵循路由算法設計準則中的第(2)條，向這2 個鄰居節點都傳遞消息的拷貝，而不是首先考慮這2 個節點對于投遞該消息副本的合適程度。當可用的鄰居節點數目大于2 個時，遵循第(1)條準則，對周圍所有可用的鄰居節點進行選擇。其出發點是盡可能選擇與當前節點形成張角最大的2 個節點，以實現副本的擴散投遞。如圖1 所示，節點Ni是當前持有消息的節點，在其傳輸范圍之內共有3 個鄰居節點Nj，Nk和Nr，共能形成了C23=3 個可能的夾角，分別記為α(j，k)，α(j，r)，α(k，r)。這里對于節點Ni的任意2 個鄰居節點Nj和Nk，利用式(1)計算節點間的夾角:

其中，Vij代表節點Ni與Nj所確定的向量;Vjk代表節點Ni與Nk所確定的向量。

圖1 節點Ni與3 個鄰居節點之間組成兩兩夾角的關系

圖2 基于夾角與距離的中繼節點選擇

依據式(2)，以一種折中的方式進行節點選擇:

其中，C1 是所有鄰居節點中所呈夾角最大的節點對;C2 是所呈夾角次大的節點對。在進行中繼節點的選擇時，首先考慮節點所呈張角的大小，并用余弦值作為衡量標準，當其差值在ε 內時，則優先考慮距離因素。d(C1)是C1 中的節點對離當前節點x 的距離之和。C1={N_j，N_k}，C2={N_m，N_n}，預設ε=π/18，并利用余弦定理求得cosα(C1)，cosα(C2)。對于距離參數d(C1)及d(C2)計算如下:

最終計算獲得f(C1，C2)=C2，即選擇Nm，Nn作為下一跳中繼節點，向其拷貝消息副本。

算法1 LC-Epidemic 的下一跳選擇算法

2.3 LC-Epidemic 路由協議

LC-Epidemic 路由協議的主要工作為:(1)每個節點如何發現其鄰居節點，并定期實時維護鄰居節點狀態;(2)鄰居表(即維護鄰居節點位置的狀態表)的更新方式。

算法2 LC-Epidemic 路由算法

采用鏈路狀態法，令每個節點周期性廣播“Hello”探測包，包中包含該節點的坐標信息，用以通知其附近節點，以更新一跳鄰居的鏈路情況。由于下一跳選擇只依賴于鄰居節點的位置信息，因此鏈路狀態控制信息只在局部交換，不會在整個網絡中造成洪泛。算法2 第1 行～第5 行是節點探測其鄰居節點的相關操作。節點i 首先更新其一跳鄰居表neighborTable，若節點j 不在表目中，則將j 的相關信息添加入表，作為新的條目。否則，由于新到達的消息更具有時效性，用新的信息更新之前所保存的位置信息。此外，為了確保每一個在表中的鄰居當前都是活躍的，在更新鄰居表時將每條表目的最后一次更新時間與當前時間相比較，若時間差超過一定值，則認為該節點已不再活躍，并從表中刪除該節點。當鄰居表更新結束后，節點i 會向節點j 發送一條hello_response 消息，其目的是通知鄰居節點j 更新操作已結束，并將自己的相關信息通知給j。如算法2 的第6 行～第9 行，當收到hello_response 消息時，接收節點依此更新自己的鄰居節點表目，更新方法與收到hello 消息時的方法一樣，每個鄰居的時效性也將被檢查。

第10 行～第28 行是消息轉發與處理策略，當某條數據消息(記為data_msg)被節點j 傳遞給當前節點i 時，由于該此傳遞意味著節點j 對于節點i 仍然是活躍的，因此節點i 首先更新其鄰居表目，以保證維護的鄰居信息的準確性。然后節點i 將檢查數據消息data_msg 是否已在其隊列當中，若已在隊列當中，則直接將其丟棄，以避免冗余，并以MSG_DROPPED 信號通知運行的路由進程。若data_msg不在緩存隊列中，則將消息入隊以等待傳遞機會到來，如第17 行。第18 行的操作是將消息隊列按消息的剩余生存時間TTL 增序排序，以便最先傳遞TTL 最小的消息，從而一定程度上避免因傳遞時間的推遲而產生丟包。第19 行將從節點維護的鄰居表中讀取所有可用鄰居節點的信息，并存入可用節點列表AvailableHostsList 中。LCE 算法采用的受控傳染策略是，當可用節點的數目小于2 個時，采用傳統的傳染病算法，以增大消息的并行性。若可用節點的數目大于2 個，為了節省網絡中的緩存資源，降低能耗，如第24 行所示，采用算法1，對可用節點列表Available HostsList 進行過濾，篩選出2 個節點傳染消息。傳遞操作結束后，向路由進程返回MSG_SENT 信號。

3 仿真實驗與結果分析

通過實驗仿真，將LC-Epidemic 與Epidemic，Binary Spray ＆ Wait，FirstContact 3 個算法進行比較，分析相關算法的性能。主要衡量指標有成功傳輸的數據包個數、平均投遞時延，端到端平均跳數以及網絡開銷等。仿真平臺是容遲網絡環境模擬器ONE(Opportunistic Enviroment Evaluator)［25］。

3.1 LC-Epidemic 路由協議

ONE 模擬器是芬蘭赫爾辛基理工大學開發的一款基于Java 的機會網絡模擬工具，其核心為一個離散事件模擬器。支持移動模型的擴展以及利用真實數據集進行仿真，其模塊劃分清晰且便于功能擴展，并支持利用腳本配置模擬環境，受到網絡研究界的廣泛認可。本文中基于Random Walk 移動模型，對LC-Epidemic 以及其他3 種算法進行模擬，3 種算法介紹如下:

(1)Epidemic［12］。傳染病算法，嘗試最大化消耗網絡資源，任意一對節點相遇時，2 個節點都會檢查對方所持有的消息，并接受對方傳送的自己未持有的消息。在網絡資源充足時，該算法具有最高的投遞率和最低的平均投遞時延。

(2)Binary Spray ＆ Wait［14］。該算法給每條消息設定一個剩余可分發副本數L，當2 個節點相遇時，對于L ＞1 的消息，將復制份副本給對方，自己持有剩余的份副本。當L=1 時，使用Direct Delivery 策略［11］，即只有遇到消息的目的節點才進行傳遞。

(3)FirstContact［16］。該算法是單拷貝算法，即當前節點成功轉發消息后，會緩存中刪除該消息，避免再次轉發。轉發策略是將消息拷貝轉發給該節點最先遇到的下一節點。

主要評估指標有:

(1)消息投遞率

(2)平均時延

(3)網絡開銷

(4)平均跳數

模擬實驗中，網絡環境的詳細參數設定如表1所示。

表1 模擬參數

3.2 仿真結果分析

3.2.1 消息生成的時間間隔

圖3 比較了在改變消息產生的間隔時間時，4 種算法對應的4 項評估指標的變化。如圖3(a)所示，由于LC-Epidemic 是基于洪泛算法，其目的是最大化副本數量以增加投遞率，因此能達到與Epidemic相當的較高的消息投遞率;First Contact 算法取得次之的較低投遞率;Binary Spray ＆Wait 算法的投遞率最低。在網絡資源充足的情況下，多副本能夠改善路由算法的表現。因此，基于洪泛的路由算法會有較為理想的投遞率，FirstContact 雖能夠及時利用節點間每一次接觸機會，但由于其只維護一個消息副本，因此無并行性，使其投遞率大大低于基于洪泛的2 個多副本算法。Binary Spray ＆ Wait 雖是多副本算法，但其對副本的總量做了限制，此外在算法的Wait 階段，消息只能進行一跳直接傳遞，然而在Random Walk 模型下，某些節點之間直接接觸的機會可能為0，因此有大量消息無法傳遞，其投遞率最低。當消息的產生間隔時間很小時，網絡中的消息數量很多，此時由于節點的緩存資源受限，會降低基于洪泛的LC-Epidemic 以及Epidemic 的性能表現。但在本文設定的模擬環境下仍遠高于限制副本數量和跳數的Binary Spray ＆ Wait 算法?？傮w上，LCEpidemic 和Epidemic 的投遞率比FirstContact 約高25%，比Binary Spray ＆Wait 約高60%。

圖3(b)比較了4 種算法的端到端平均時延，Epidemic 無疑具有最低的端到端平均時延，因為其最大化利用了所有網絡可用資源。LC-Epidemic 的平均時延比Epidemic 約高4 倍，但仍然低于其他2 種算法。與圖3(a)類似，消息產生間隔小于20 s時，由于緩存資源受限，Binary Spray ＆ Wait 和FirstContact 的表現要好于基于洪泛的Epidemic 以及LC-Epidemic 算法。隨著消息產生間隔的持續增大，固定時間內的副本數量不斷減少，Epidemic 和LC-Epidemic 的消息端到端平均時延迅速下降，當消息產生間隔時間大于30 s 時，節點的緩存已不再是限制路由性能表現的瓶頸因素。Epidemic 和LCEpidemic 與其他2 種算法一樣，其端到端平均時延趨于穩定。比較4 種路由算法，FirstContact 的平均時延比BinarySpray ＆Wait 約低22%，且在圖3(a)中其投遞率比Binary Spray ＆Wait 高，因此綜合投遞率和平均時延來看，其表現勝過Binary Spray ＆Wait。

圖3(c)比較了4 種算法的網絡開銷。從圖3(a)、圖3(b)中的分析可知，在消息產生間隔小于30 s時，緩存資源是路由性能表現的瓶頸因素，然而此時LC-Epidemic 的網絡開銷約只有Epidemic 的55%。綜合圖3(a)～3(c)來看，在緩存資源受限的情況下，LC-Epidemic 能夠保證和Epidemic 投遞率幾乎持平的情況下，降低一半的網絡負載，代價是具有比Epidemic 高的平均時延。對于不刻意強調消息投遞時延的容遲網絡應用，可以用LC-Epidemic 替代Epidemic，以節省網絡資源開銷，相比傳統的Epidemic 對消息副本的盲目復制，LC-Epidemic 基于節點分布及相對位置選擇下一跳，因此其路由策略更有針對性。Binary Spray ＆Wait 和FirstContact 算法，前者是多拷貝算法，但限制了消息副本的數目和最大跳數，后者雖未對最大跳數做限制，但每條消息在網絡中最多只有一份拷貝，因此兩者的網絡開銷較低。綜合來看，兩者在投遞率和平均時延2 項指標上，表現都差于基于洪泛的Epidemic 和LCEpidemic，這在一定程度上限制了其應用價值。

圖3 消息產生時間間隔與消息投遞率、平均時延、網絡開銷以及平均跳數的關系

圖3(d)比較了Epidemic，LC-Epidemic 以及FirstContact 的端到端平均跳數。之所以不加入Binary Spray ＆ Wait 算法進行比較，是因為其已限制了副本的最大跳數，而其他3 種算法對此均無限制。可以看出，FirstContact 具有最高的平均跳數，原因是其相比Epidemic 和LC-Epidemic，只在網絡中維護消息的一份拷貝，因此該消息常需要多跳才能將副本傳輸到目的節點。該結果與圖3(b)中分析的結果相吻合，由于跳數較大，因此其平均時延也遠高于Epidemic 和LCEpidemic。LC-Epidemic 的平均跳數只比Epidemic 略高，其原因是LC-Epidemic 是受控洪泛，在一定程度上控制消息副本數目，進而控制網絡資源的利用，以換來更低的網絡開銷。

綜合圖3(a)～圖3(d)來看，LC-Epidemic 在投遞率和平均跳數2 項指標上都接近于最優的Epidemic，其網絡開銷比傳統Epidemic 算法低一半，若不刻意強調端到端時延，可以用LC-Epidemic 算法代替Epidemic。在節點移動速度較低的網絡場景下，Binary Spray ＆ Wait 以及FirstContact 的表現不甚理想，FirstContact 在投遞率、投遞時延以及網絡開銷三方面都要優于Binary Spray ＆ Wait。

3.2.2 節點緩沖區大小

圖4 比較了在改變節點的緩存大小時，4 種算法對應的4 項評估指標的變化。如圖4(a)所示，只有當節點緩存小于2.5 MB 時，才會成為限制FirstContact 和Binary Spray ＆ Wait 投遞率的瓶頸因素。緩存低于30 MB 時，LC-Epidemic 的投遞率一直略高于Epidemic，最后與Epidemic 幾乎持平，維持在接近1.0，這驗證了基于一跳鄰居實現受控傳染的策略能有效改善網絡資源的利用率。在緩存資源大于8 MB 時，LC-Epidemic 的投遞率高于Binary Spray ＆ Wait 和First Contact。與圖3(a)中的結果類似，FirstContact 的投遞率仍遠高于Binary Spray ＆ Wait。由此推斷，在節點位置相對穩定的環境下，不適宜對副本的最大跳數做限制。綜合來看，基于洪泛的Epidemic 和LC-Epidemic 在投遞率方面，性能表現勝過其余2 個算法。

圖4 節點緩沖區大小與消息投遞率、平均時延、網絡開銷以及平均跳數的關系

圖4(b)比較了當緩存容量變化時，4 種算法端到端平均時延的變化。當節點緩存容量較小時，4 種算法都具有較低的端到端平均時延。其原因是計算端到端平均時延的統計樣本為所有已完成傳遞的消息，由于受緩存大小限制，只有那些能夠被快速投遞的消息才會被統計，其他許多消息都被節點丟棄，如圖4(a)所示，此時4 種算法的投遞率都很低。隨著節點緩存的增加，這種嚴重丟包的情況漸漸緩解，當緩存容量達到5 MB 時4 種算法的平均時延都已攀升到最高點。在節點緩存容量從0.5 MB 增加到5 MB的這個過程中，所有算法的消息投遞率都是在增長的，且當緩存容量為5 MB 時Binary Spray ＆Wait 以及FirstContact 的投遞率也達到最大，此時緩存不再是Binary Spray ＆ Wait 以及FirstContact 性能表現的約束因素，即繼續增大緩存容量不會對這2 個算法的性能表現產生很大影響。體現在圖4(b)中，隨著緩存容量的繼續增大，Spray ＆ Wait 和FirstContact 的平均時延保持恒定?；诤榉翰呗缘腅pidemic 和受控傳染策略的LC-Epidemic，平均時延隨著節點緩存的繼續增大而逐漸降低。至緩存容量增大到30 MB 時趨于穩定，這與圖4(a)投遞率的穩定點相同。此時Epidemic 具有最低的端到端平均時延，LC-Epidemic 次之，結果類似于圖3(b)。

圖4(c)比較了4 種算法網絡開銷的變化。由于Binary Spray ＆ Wait 以及FirstContact 最大副本數量受限，兩者在緩存容量小于10 MB 時，具有遠低于Epidemic 和LC-Epidemic 的網絡開銷。如圖4(a)所示，此時FirstContact 的消息投遞率高于Epidemic 及LC-Epidemic，可知在緩存資源緊張時，多副本策略會降低路由性能。然而 LC-Epidemic 比傳統的Epidemic 的網絡開銷約低50%，數據曲線走勢與圖3(c)相似。

圖4(d)比較了Epidemic，LC-Epidemic 以及FirstContact 3 種算法的平均跳數，Binary Spray ＆Wait 仍不參與比較。FirstContact 具有最高的平均跳數，Epidemic 的平均跳數最低，而LC-Epidemic 完成消息投遞所需的平均跳數只比Epidemic 略高，比FirstContact 要低很多。理由與分析圖3(d)相同。

綜合圖4(a)～圖4(d)來看，在緩存資源稀缺時，宜采用單副本算法，如FirstContact;因為此時洪泛策略往往會讓網絡資源迅速耗盡，從而降低路由性能表現。然而FirstContact 這種盲目轉發策略，使得完成消息傳遞所需的平均跳數過大。如果要將跳數控制在一定范圍內，則宜采用受控傳染策略的路由算法LC-Epidemic，降低網絡開銷。通過圖3 以及圖4 可知，LC-Epidemic 基于節點位置的下一跳選擇算法能夠有效的控制網絡中消息副本數量，從而降低負載，并且能夠獲得與Epidemic 幾乎持平的投遞率，在一定程度上可以代替盲目的洪泛策略。

3.2.3 消息生命周期

圖5 在改變消息的生命周期(Time to Live，TTL)的情況下，比較了4 種算法的消息投遞率以及平均時延的變化。如圖5(a)所示，當TTL 小于50 min時，Epidemic 和LC-Epidemic 的投遞率遠高于Binary Spray ＆Wait 以及First Contact，其原因在于當消息生命周期受限時，Epidemic 和LC-Epidemic能夠有效地利用快速增加消息并行性的洪泛策略，及時完成消息的投遞，且圖3(b)與圖4(b)已說明當緩存資源不是瓶頸時，Epidemic 和LC-Epidemic具有比Binary Spray ＆Wait 以及FirstContact 低得多的平均時延。然而隨著TTL 的增大，前兩者的投遞率不斷下降，而后兩者的投遞率卻保持攀升，其原因是過大的TTL，會導致當使用洪泛策略時節點緩存中消息副本積壓，從而造成丟包，降低消息投遞率。而TTL 的延長，恰好彌補了Binary Spray ＆Wait 以及FirstContact 平均投遞時延過長的不足，從而增加消息投遞率。在本文實驗中，當消息生命周期大于250 min時，所有4 種算法的投遞率都趨于穩定，Binary Spray ＆ Wait 和FirstContact 要明顯優于其他2 個洪泛算法?？芍?，當消息TTL 較長時，宜采用嚴格控制副本數量的路由算法，摒棄洪泛。然而當TTL 較 短 時，Binary Spray ＆ Wait 以 及First Contact 的表現相比Epidemic 和LC-Epidemic 差很多。

圖5 消息生命周期與消息投遞率、平均時延的關系

圖5(b)比較了4 種算法的平均時延，隨著TTL的增大，所有4 個算法的平均時延都增大。此外，除了FirstContact 具有很長的平均時延之外，其他3 種算法的平均時延都相差甚小。LC-Epidemic 一直保持最低的平均時延，優于其他3 種算法。比較圖5(a)與圖5(b)可知，在TTL 較大時，宜采用Binary Spray ＆ Wait 算法，以在保證投遞率的基礎上獲得較低的平均時延。然而，當TTL 較小時，則宜采用基于洪泛的LC-Epidemic 算法。

3.3 LC-Epidemic 路由分析

綜合仿真結果來看，由于LC-Epidemic 本質是基于Epidemic 的算法，因此其路由表現與Epidemic 較接近。與傳統的Epidemic 不同的是，LC-Epidemic 將節點分布及節點相對位置等信息納入考慮之中，在傳遞消息時控制消息的副本數量，從而實現基于節點位置的受控洪泛路由。綜合仿真結果分析，當消息的TTL 較短時，不宜對消息的副本數量做過于嚴格的限制。這也是本文設計算法時，基于傳染病路由策略的初衷。從仿真結果看，LCEpidemic 的優化策略，其原理雖簡單，但確有一定成效，由于在DTN 多變的網絡環境中，收集實時有效的網絡拓撲信息非常困難，因此此時基于一跳位置信息的策略顯得更為實用。此外，在仿真程序設計過程中，所有節點都是以對等方式工作的，因此網絡的自組特性沒有被破壞，LCEpidemic 正適用于時延較高的自組網絡場景，特別是在TTL 較短的情況下。

4 結束語

在容遲網絡中，網絡的頻繁割裂和間歇性連接，以及節點的移動性使得路由問題變得更加富有挑戰性。路由策略的優劣在一定程度上依賴于對網絡拓撲信息的掌握，然而在這類挑戰性網絡中，很難獲得準確且具有時效性的網絡拓撲信息。本文研究如何利用一跳以內節點的位置信息進行下一跳節點選擇，從而一定程度上控制洪泛策略的副本數量，在保持較高投遞率以及較低的端到端平均時延的基礎上降低網絡開銷?；谟嘞叶ɡ?，設計了下一跳節點選擇算法，盡可能使消息擴張投遞，增大消息在整個網絡中的覆蓋面積，從而提高路由性能表現。此外，給出了LC-Epidemic 協議的詳細描述，利用鏈路狀態法維護一跳鄰居信息，從而實時更新鄰居表，維護可用節點隊列。

本文 對Epidemic，Binary Spray ＆ Wait，First-Contact 以及本文提出的LC-Epidemic 4 種路由算法進行大量仿真模擬。實驗結果表明，LC-Epidemic 的消息投遞率逼近于傳統的Epidemic 算法，然而其網絡開銷卻只有后者的50%。在消息TTL 較短的情況下，只要節點的緩存資源不過小，Epidemic 以及LC-Epidemic 在投遞率以及投遞時延方面明顯好于Binary Spray ＆Wait 以及FirstContact 算法。然而當消息的TTL 較大時，基于洪泛策略的路由算法難以獲得較好的表現。總之，多副本策略是解決容遲網絡中路由問題的一項基本且有效的手段，下一步研究將側重于依賴節點的移動模型以及移動方向進行路由算法的設計，并結合本文提出的基于鄰居節點位置的方法進行更有效的下一跳選擇，從而實現受控傳染。此外，考慮引入受控節點對消息進行定向傳輸，從而增大消息傳遞率并降低平均傳遞時延，這種方案雖然會在一定程度上破壞網絡的自組特性，然而若使用得當，將會大大增加網絡的連通性，從而有助于設計更靈活的路由算法。最后，考慮到目前存儲器的容量飛速增加以及成本迅速降低的趨勢，下一步將研究具有大緩存容量的節點路由問題，由于目前電池技術的限制，節點能耗更有可能成為容遲網絡中影響路由性能表現的主要因素，未來工作的重點將集中于此。

［1］Demmer M，Fall K.DTLSR:Delay Tolerant Routing for Developing Regions ［C］//Proceedings of 2007 Workshop on Networked Systems for Developing Regions.New York，USA:ACM Press，2007.

［2］Guo Zheng，Wang Bing，Cui Junhong.Generic Prediction Assisted Single-copy Routing in Underwater Delay Tolerant Sensor Networks［J］.Ad Hoc Networks，2013，11(3):1136-1149.

［3］Pereira P R，Casaca A，Rodrigues J J P C，et al.From Delay-tolerant Networks to Vehicular Delay-tolerant Networks ［J］.IEEE Communications Surveys ＆Tutorials，14(4)，2012:1166-1182.

［4］Soares V N G J，Rodrigues J J P C，Farahmand F.GeoSpray:A Geographic Routing Protocol for Vehicular Delay-tolerant Networks［J］.Information Fusion，2014，15:102-113.

［5］Cao Y.Routing in Delay/Disruption Tolerant Networks:A Taxonomy，Survey and Challenges ［J］.IEEE Communications Surveys ＆ Tutorials，2012，15 (2):654-677.

［6］張 龍，周賢偉，王建萍，等.容遲與容斷網絡中的路由協議［J］.軟件學報，2010，21(10):2254-2572.

［7］Fall K.A Delay-tolerant Network Architecture for Challenged Internets［C］//Proceedings of SIGCOMM'03.New York，USA:ACM Press，2003:27-34.

［8］Spyropoulos T，Rais R N B，Turletti T，et al.Routing for Disruption Tolerant Networks:Taxonomy and Design［J］.Wireless Networks，2010，16(8):2349-2370.

［9］樊秀梅，單志廣，張寶賢，等.容遲網絡體系結構及其關鍵技術研究［J］.電子學報，2008，36(1):161-170.

［10］Zhang Zhensheng.Routing in Intermittently Connected Mobile Ad Hoc Networks and Delay Tolerant Networks:Overview and Challenges［J］.IEEE Communications Surveys ＆Tutorials，2006，8(1):24-37.

［11］Ott J.Delay Tolerance and the Future Internet［C］//Proceedings of WPMC'08.［S.l.］:IEEE Press，2008.

［12］Vahdat A，Becker D.Epidemic Routing for Partially Connected Ad Hoc Networks［D］.Durham，USA:Duke University，2000.

［13］Grossglauser M，Tse D N C.Mobility Increases the Capacity of Ad Hoc Wireless Networks［J］.IEEE/ACM Trans.on Networking，2002，10(4):477-486.

［14］Spyropoulos T，Psounis K，Raghavendra C S.Spray and Wait:An Efficient Routing Scheme for Intermittently Connected Mobile Networks［C］//Proceedings of 2005 ACM SIGCOMM Workshop on Delay-tolerant Networking.New York，USA:ACM Press，2005:252-259.

［15］Spyropoulos T，Psounis K，Raghavendra C.Spray and Focus:Efficient Mobility-assisted Routing for Heterogeneous and Correlated Mobility［C］//Proceedings of the 5th Annual IEEE International Conference on Pervasive Computing and Communications Workshop.White Plains，USA:IEEE Press，2007:79-85.

［16］Jain S，Fall K，Patra R.Routing in a Delay Tolerant Network［J］.ACM SIGCOMM Computer Communication Review，2004，34(4):145-158.

［17］Erramilli V，Crovella M.Delegation Forwarding［C］//Proceedings of the 9th ACM International Symposium on Mobile Ad Hoc Networking and Computing.New York，USA:ACM Press，2008:251-260.

［18］Liu C，Wu J.On Multicopy Opportunistic Forwarding Protocols in Nondeterministic Delay Tolerant Networks［J］.IEEE Trans.on Parallel and Distribution Systems，2012，23(6):1121-1128.

［19］Hui P，Crowcroft J.How Small Labels Create Big Improvements［C］//Proceedings of the 5th Annual IEEE International Conference on Pervasive Computing and Communications Workshops.［S.l.］:IEEE Press，2006:65-70.

［20］Daly E M，Haahr M.Social Network Analysis for Routing in Disconnected Delay-tolerant MANETs［C］//Proceedings of the 8th ACM International Symposium on Mobile Ad Hoc Networking and Computing.New York，USA:ACM Press，2007:32-40.

［21］Zhu Y，Xu B，Shi X.A Survey of Social-based Routing in Delay Tolerant Networks:Positive and Negative Social Effects［J］.IEEE Communications Surveys ＆Tutorials，2013，15(1):387-401.

［22］Mangrulkar R，Atique M.Routing Protocol for Delay Tolerant Network:A Survey and Comparison［C］//Proceedings of 2010 IEEE International Conference on Communication Control and Computing Technologies.［S.l.］:IEEE Press，2010:210-215.

［23］Psaras I，Wang N，Tafazolli R.Six Years Since First DTN Papers:Is There a Clear Target?［C］//Proceedings of Extreme-Com'09.［S.l.］:IEEE Press，2009.

［24］Li Y，Hui P.Performance Evaluation of Routing Schemes for Energy-constrained Delay Tolerant Networks［C］//Proceedings of 2011 IEEE International Conference on Communications.［S.l.］:IEEE Press，2011:1-5.

［25］Ker?nen A，Ott J，K?rkk?inen T.The One Simulator for DTN Protocol Evaluation［C］//Proceedings of the 2nd International Conference on Simulation Tools and Techniques.［S.l.］:IEEE Press，2009:55-60.