容遲網絡中基于復制策略的單播路由算法研究

王欣

（青島遠洋船員職業學院 山東 青島 266071）

容遲網絡或者容延網絡（Delay/DisruptionTolerantNetworks，DTN）是近年來無線網絡領域內的一個研究熱點，泛指部署在極端環境下由于節點的移動或者能量調度等原因而導致節點間只能間歇性進行通信甚至長時間處于中斷狀態的一類網絡。與基于TCP/IP協議簇的Internet網絡和傳統的無線傳感網絡不同，DTN是端到端存儲轉發網絡體系結構，并且涉及的網絡環境多樣，且具有間歇連接，頻繁割裂，時延極高，非對稱的數據速率，較高的誤碼率等特點，故傳統的路由算法在DTN中不再適用。DTN路由算法研究正是希望使得這種拓撲結構隨時間動態變化的網絡信息交換更為有效、可靠。正因為具有這些特點，DTN的應用涵蓋了除了Internet之外的許多網絡。DTN最初主要應用于星際網絡和軍事網絡，之后又被應用于鄉村網絡，野生動物監控與追蹤網絡，以及移動Ad hoc網絡等。

如何做出正確高效的路由選擇一直是無線網絡領域內的關鍵技術和主要研究課題。由于傳輸鏈路的時變性和不確定性使得容遲網絡中的路由研究是一項挑戰性的課題，因此設計可靠有效的容遲網絡路由算法來提高網絡連接性、降低能量消耗和時延、增加消息投遞率就成為容遲網絡研究的一個核心問題。DTN的路由算法方面的研究越來越受到國內外學者的重視，文中將對基于復制策略的單播路由算法進行了研究討論。

1 基于復制策略的單播路由算法介紹

根據路由策略的不同，單播路由可以分為基于復制策略、基于轉發策略、以及常用于移動傳感網絡中的節點控制類型。在基于復制策略的路由算法中，源節點或者中繼節點在轉發消息時向與之關聯的多個鄰居節點復制該消息。在某一時刻，網絡中有該消息的多個副本在傳輸，這種方法是通過提高消息的冗余度來增加端到端消息傳輸的成功率。復制策略中分為基于洪泛，基于概率，基于調度（優先級），基于編碼4種類型。

1.1 基于洪泛（路由擴散/Flooding Strategy）策略

1.1.1 傳染病 （Epidemic）路由算法

著名的傳染病（Epidemic）路由算法是其中的一個代表性算法，該算法模仿生物環境中傳染性病毒的傳播方式，體現在DTN中，每個節點維護一個消息總結向量，當兩個節點能夠連接時通過交換消息向量來彼此交換缺少的消息。經過一段時間，網絡中的每個節點將收到所有的消息。傳染病路由算法本質上是基于洪泛策略（flooding）的，優點是不需要額外的拓撲控制信息，同時可以取得高的消息投遞率和低的端到端時延，無需對鏈路狀態進行預測與估計，實施起來較為簡單。缺點是網絡中存在大量的冗余副本將導致節點能耗增加和緩存溢出，進而導致網絡的資源利用率低和整體運行效能低下，該算法主要適用于緩存和帶寬充足的場景。

1.1.2 一跳傳輸（Single Hop Transmission）路由算法

與其它路由算法相比，基于一跳的路由算法是將信息從源節點傳送到目的節點最簡單的方法。當源節點與目的節點建立連接時，源節點立刻把信息傳送給目的節點。當源節點和目的節點之間只有一跳的距離時，這種策略既簡潔又有效。在這種策略中，不存在中繼的冗余信息。其優點是只需要消耗很少的資源，然而這種算法最大的缺點就是時延較大，并且信息傳輸成功的概率較低。Frenkiel R.H.和Badrinath B.R.提出了一種基于一跳傳輸的感染機制，利用這種方法可以增加無線網絡的信息傳輸量，并且降低傳輸開銷。在ad hoc網絡中使用一跳傳輸策略，節點的移動性會增加傳輸能力。

1.2 基于概率（歷史預測）的路由算法

基于歷史預測策略的路由算法是為了克服基于復制策略中消息復制的盲目性而提出的，通過消息歷史傳輸的成功概率進行估算和比較，選擇到達目的節點概率更高的中繼節點。通過這種有選擇性的復制消息，避免生成低效傳輸的消息副本，提高網絡的資源利用率。基于概率（歷史預測）的復制策略又可分為基于一跳和基于端到端兩種。

1.2.1 基于一跳的復制策略

1）PROPHET 路由算法

PROPHET（Probabilistic Routing Protocol Using History of Encounters and Transitivity）路由算法是基于歷史預測策略的典型代表，利用節點間的相遇的歷史信息和傳遞性來選擇下一跳節點。該算法定義一個稱之為投遞預測值（Delivery Predictability）的指標來描述節點之間成功傳輸消息的概率。與傳染病路由算法相比，每當兩個節點A和B相遇時，除了要交換向量，還需要交換投遞預測值只有當B到達目的節點的投遞預測值大于A時，A才向B復制消息。

2）CAR路由算法

CAR （Context-aware Adaptive Routing）是一種混合式路由算法，該算法根據傳輸可能性選擇中間轉發節點。其中傳輸可能性由節點通過環境信息（Context Information）合成，包括節點連通性變化的頻率和當前節點能量等因素。當源節點和目的節點之間存在端到端路徑時，該算法使用同步路由轉發數據，但若網絡中無端到端路徑，則選擇使用異步路由來傳輸數據。為了能準確有效地估計和更新路由表中的傳輸可能性，該算法使用濾波技術預測節點的環境信息變化。

1.2.2 基于端到端的復制策略

1）MV路由算法

MV（Meetings and Visits）則利用節點間的相遇概率來描述消息傳輸的成功概率，任意兩個節點間的相遇概率作為這對節點的傳輸概率，在此基礎上通過遞歸的方式計算多跳傳輸的成功概率。兩個節點相遇時，交換各自的消息以及傳輸概率信息，通過比較，節點僅向傳輸概率更高的中繼節點復制消息。與基于復制策略的路由算法相比，基于歷史預測策略的路由算法由于在選擇中繼節點時更有目標性和針對性，因此可以取得更高的消息投遞率和網絡資源利用率。

2）ORWAR路由算法

ORWAR （OpportunisticRoutingwith Window-Aware Replication）路由協議算法，其主要目標是減少資源消耗以及降低傳輸時的信息丟失率，減少零散的消息片段。當節點移動到傳輸范圍之外時，若此時傳輸操作仍在進行著，零散消息片段的數目就會增加。ORWAR計算了每次連接能夠被傳輸的數據總字節數，該做法有利于更有效的利用有限的帶寬。然而為了在網絡系統中部署ORWAR路由算法，每個節點都需要具有測量傳遞速度以及傳遞方向的能力，該方法目前只有在設備配有GPS系統時，才具有可行性。

1.3 基于調度（優先級）的路由算法

該算法最核心的思想是對束賦予優先級，并按照優先級的高低擇優傳遞信息。該算法需要使用針對傳輸和刪除操作的優先級函數。在洪泛傳遞信息時，該算法使用一些參數來對信息的優先級進行評估。其中某些參數用于評估信息從當前節點傳送到目的節點的開銷等。

1）基于優先級的傳染病路由算法 （Prioritized epidemic routing）

該算法的核心思想是給每一個叫做“束”（bundle）的信息指派一個優先級。對信息的傳輸和刪除操作是由優先級函數控制的。信息的洪泛策略是基于估計信息的優先級而進行的，某些參數被用于評估從當前節點到目的節點的開銷，或是連接的出現和消失的時間等。相比傳統的傳染病路由算法，該算法能夠結合網絡中的拓撲知識信息，更合理有效的利用網絡中有限的資源，缺點是由于引入了優先級函數，增大了每個節點的計算開銷。

2）MaxProp 算法

在使用該策略的情境下，網絡中的節點往往是城市中的公交車，它們具有較高的相遇概率，故在實施算法的過程中，城市的環境也被納入考慮范圍之內。MaxProp算法通過交換信息來獲知節點的未來行為，并利用總的開銷來篩選到目的節點的最優路徑。MaxProp算法將緩沖操作分為兩部分，在第一階段中，算法會基于信息經過的節點跳數，將其從跳數少到跳數多增序排序。第二階段是將信息按照開銷從高到低排序。緩沖區資源在使用中，兩方面都要納入考慮。

1.4 基于編碼的路由算法

基于擦除碼（Eraser Code）的路由算法也可以認為是基于復制策略的一種，它基于這樣的原理：源節點對消息進行分塊，然后這些分塊以某個大于1的常數因子進行復制轉發，當目的節點收到這些分塊中的一定比例時即可重構源消息。

基于網絡編碼（Network Coding）的路由算法。該算法在基于概率的路由算法的基礎上，引入線性網絡編碼技術來降低算法的代價。仿真實驗結果表明，在一個稀疏部署的移動網絡中，特別是在節點具有較高的丟包率時，引入網絡編碼技術以后，路由算法的性能提升尤為明顯。

2 路由算法策略比較

在復制策略中，大量的相同信息的拷貝將被創建，這些拷貝將會被傳輸給中繼結點。中繼節點接受這些拷貝，并將其存儲在自身的緩存中。當這些中繼節點和目標節點建立連接時，拷貝才會被傳輸到目的結點，并且中繼節點將傳送過去的信息的緩存清空。在DTN早期的算法研究工作中，這種策略經常被路由算法的設計者和研究者們使用。在某些移動傳感網絡中，節點的移動具有隨機性，此時，這種路由策略往往能夠有效的利用結點本身的這種隨機移動性，從而有效的將信息傳送到目的節點。信息的大量復制是增加傳輸成功概率的有效手段，使用這些協議并不需要預先獲知任何關于整個網絡的連接狀態或知識。本文重點比較基于洪泛和基于編碼的路由策略。

基于洪泛策略的路由算法實現起來較為簡單，該類算法的優點是：1）不需依賴對鏈路狀態的估計；2）若節點的資源充足，則該種策略下的路由算法可以較為快速的實現信息的傳遞與轉發，從而減小傳輸的時延，以及消息傳遞成功的概率。該類算法的缺點是：節點之間在傳輸報文時，擁有大量的冗余報文，增加了網絡傳輸負載。

基于編碼的方法，一般是將信息在源節點分塊，待其傳輸到目的節點，再將其重組。其優點是：提高了系統傳輸吞吐量。與基于其他3種策略的路由算法相比較，基于該策略的路由算法在網絡負載相同的情況下具有較低的傳輸時延。由于分組和編碼，在一定程度上有助于在網絡擁塞的情況下抗擊丟包。缺點是：編解碼操作會帶來一定的能量消耗。編解碼操作較為復雜。信息塊的拆分策略，目前無較好方案。

3 結束語

通過對容遲網絡路由算法相關的文獻，特別是近幾年來的主要研究成果進行研究總結發現目前的路由協議缺乏多項評估指標的綜合考慮，往往在個別指標上性能優越，但無法優化多項指標，網絡整體性能難以獲得極大的提升。因此需要利用新的分析工具研究容遲網絡路由，同時考慮多個設計目標進行優化，建立基于多目標優化的高效路由協議.例如，以節點能量消耗、時延、傳輸率為目標，進行多目標決策，設計出最優路由協議。

[1]張龍，周賢偉，王建萍，等.容遲與容斷網絡中的路由協議[J].軟件學報，2010，21（10）:2554-2572.

ZHANG Long，ZHOU Xian-wei，WANG Jian-ping，etal.Routing protocols for delay and disruption tolerant networks[J].Journal of Software，2010，21（10）:2554-2572.

[2]Vahdat A，Becker D.Epidemic routing for partially-connected AdHoc networks[R].Duke University，Tech.Rep.:CS-2000-06，2000.

[3]Groenevelt R，Nain P，Koole G.The message delay in mobile ad hoc networks[J].Elsevier Journal of Perform-ance Evaluation，2005，62（1-4）:210-228.

[4]Jain S，Demmer M，Patra R，et al.Using redundancy to cope with failures in a delay tolerant networks[C]//In:Proc.of the ACM SICOMM 2005，2005:109-120.

[5]周曉波，盧漢成，李津生，等.AED:一種用于DTN的增強型Earliest-Delivery算法[J].電子與信息學報，2007，29（8）:1687-1694.

ZHOU Xiao-bo，LU Han-cheng，LI Jin-sheng，et al.AED:advanced earliest-delivery algorithm used in DTN[J].Journal of Electronics&InformationTechnology，2007，29（8）:1687-1694.

[6]Lindgren A.Probabilistic routing in intermittently connected networks[J].Mobile Computing and Communications Review，2003，7（3）:19-26.

[7]劉舒拉.基于博弈論的無線傳感器網絡路由算法研究[J].現代電子技術，2011（9）：45-47.

LIU Shu-la.Game-theory based routing algorithms for wireless sensor network[J].Modern Electronics Technique，2011（9）：45-47.

[8]楊眉，李忠科，王忠.基于OWL-S語義柵格運動目標信息快速分發技術[J].電子科技，2012（7）：6-9，14.

YANG Mei，LI Zhong-ke，WANG Zhong.The research on rapidly distribution of moving target information based on OWL-S semantic grid[J].Electronic Science and Technology，2012（7）：6-9，14.