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

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

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

1 概述

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

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

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

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

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

2 路由設(shè)計

2.1 路由思想

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

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

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

2.2 下一跳選擇算法

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

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

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

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

圖1 節(jié)點Ni與3 個鄰居節(jié)點之間組成兩兩夾角的關(guān)系

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

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

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

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

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

2.3 LC-Epidemic 路由協(xié)議

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

算法2 LC-Epidemic 路由算法

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

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

3 仿真實驗與結(jié)果分析

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

3.1 LC-Epidemic 路由協(xié)議

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

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

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

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

主要評估指標有:

(1)消息投遞率

(2)平均時延

(3)網(wǎng)絡(luò)開銷

(4)平均跳數(shù)

模擬實驗中，網(wǎng)絡(luò)環(huán)境的詳細參數(shù)設(shè)定如表1所示。

表1 模擬參數(shù)

3.2 仿真結(jié)果分析

3.2.1 消息生成的時間間隔

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

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

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

圖3 消息產(chǎn)生時間間隔與消息投遞率、平均時延、網(wǎng)絡(luò)開銷以及平均跳數(shù)的關(guān)系

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

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

3.2.2 節(jié)點緩沖區(qū)大小

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

圖4 節(jié)點緩沖區(qū)大小與消息投遞率、平均時延、網(wǎng)絡(luò)開銷以及平均跳數(shù)的關(guān)系

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

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

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

綜合圖4(a)～圖4(d)來看，在緩存資源稀缺時，宜采用單副本算法，如FirstContact;因為此時洪泛策略往往會讓網(wǎng)絡(luò)資源迅速耗盡，從而降低路由性能表現(xiàn)。然而FirstContact 這種盲目轉(zhuǎn)發(fā)策略，使得完成消息傳遞所需的平均跳數(shù)過大。如果要將跳數(shù)控制在一定范圍內(nèi)，則宜采用受控傳染策略的路由算法LC-Epidemic，降低網(wǎng)絡(luò)開銷。通過圖3 以及圖4 可知，LC-Epidemic 基于節(jié)點位置的下一跳選擇算法能夠有效的控制網(wǎng)絡(luò)中消息副本數(shù)量，從而降低負載，并且能夠獲得與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，會導致當使用洪泛策略時節(jié)點緩存中消息副本積壓，從而造成丟包，降低消息投遞率。而TTL 的延長，恰好彌補了Binary Spray ＆Wait 以及FirstContact 平均投遞時延過長的不足，從而增加消息投遞率。在本文實驗中，當消息生命周期大于250 min時，所有4 種算法的投遞率都趨于穩(wěn)定，Binary Spray ＆ Wait 和FirstContact 要明顯優(yōu)于其他2 個洪泛算法?？芍?，當消息TTL 較長時，宜采用嚴格控制副本數(shù)量的路由算法，摒棄洪泛。然而當TTL 較 短 時，Binary Spray ＆ Wait 以 及First Contact 的表現(xiàn)相比Epidemic 和LC-Epidemic 差很多。

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

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

3.3 LC-Epidemic 路由分析

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

4 結(jié)束語

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

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

［1］Demmer M，F(xiàn)all 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，F(xiàn)arahmand 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］張 龍，周賢偉，王建萍，等.容遲與容斷網(wǎng)絡(luò)中的路由協(xié)議［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］樊秀梅，單志廣，張寶賢，等.容遲網(wǎng)絡(luò)體系結(jié)構(gòu)及其關(guān)鍵技術(shù)研究［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，F(xiàn)all 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.