王欣

（青島遠(yuǎn)洋船員職業(yè)學(xué)院 山東 青島 266071）

容遲網(wǎng)絡(luò)或者容延網(wǎng)絡(luò)（Delay/DisruptionTolerantNetworks，DTN）是近年來(lái)無(wú)線網(wǎng)絡(luò)領(lǐng)域內(nèi)的一個(gè)研究熱點(diǎn)，泛指部署在極端環(huán)境下由于節(jié)點(diǎn)的移動(dòng)或者能量調(diào)度等原因而導(dǎo)致節(jié)點(diǎn)間只能間歇性進(jìn)行通信甚至長(zhǎng)時(shí)間處于中斷狀態(tài)的一類網(wǎng)絡(luò)。與基于TCP/IP協(xié)議簇的Internet網(wǎng)絡(luò)和傳統(tǒng)的無(wú)線傳感網(wǎng)絡(luò)不同，DTN是端到端存儲(chǔ)轉(zhuǎn)發(fā)網(wǎng)絡(luò)體系結(jié)構(gòu)，并且涉及的網(wǎng)絡(luò)環(huán)境多樣，且具有間歇連接，頻繁割裂，時(shí)延極高，非對(duì)稱的數(shù)據(jù)速率，較高的誤碼率等特點(diǎn)，故傳統(tǒng)的路由算法在DTN中不再適用。DTN路由算法研究正是希望使得這種拓?fù)浣Y(jié)構(gòu)隨時(shí)間動(dòng)態(tài)變化的網(wǎng)絡(luò)信息交換更為有效、可靠。正因?yàn)榫哂羞@些特點(diǎn)，DTN的應(yīng)用涵蓋了除了Internet之外的許多網(wǎng)絡(luò)。DTN最初主要應(yīng)用于星際網(wǎng)絡(luò)和軍事網(wǎng)絡(luò)，之后又被應(yīng)用于鄉(xiāng)村網(wǎng)絡(luò)，野生動(dòng)物監(jiān)控與追蹤網(wǎng)絡(luò)，以及移動(dòng)Ad hoc網(wǎng)絡(luò)等。

如何做出正確高效的路由選擇一直是無(wú)線網(wǎng)絡(luò)領(lǐng)域內(nèi)的關(guān)鍵技術(shù)和主要研究課題。由于傳輸鏈路的時(shí)變性和不確定性使得容遲網(wǎng)絡(luò)中的路由研究是一項(xiàng)挑戰(zhàn)性的課題，因此設(shè)計(jì)可靠有效的容遲網(wǎng)絡(luò)路由算法來(lái)提高網(wǎng)絡(luò)連接性、降低能量消耗和時(shí)延、增加消息投遞率就成為容遲網(wǎng)絡(luò)研究的一個(gè)核心問(wèn)題。DTN的路由算法方面的研究越來(lái)越受到國(guó)內(nèi)外學(xué)者的重視，文中將對(duì)基于復(fù)制策略的單播路由算法進(jìn)行了研究討論。

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

根據(jù)路由策略的不同，單播路由可以分為基于復(fù)制策略、基于轉(zhuǎn)發(fā)策略、以及常用于移動(dòng)傳感網(wǎng)絡(luò)中的節(jié)點(diǎn)控制類型。在基于復(fù)制策略的路由算法中，源節(jié)點(diǎn)或者中繼節(jié)點(diǎn)在轉(zhuǎn)發(fā)消息時(shí)向與之關(guān)聯(lián)的多個(gè)鄰居節(jié)點(diǎn)復(fù)制該消息。在某一時(shí)刻，網(wǎng)絡(luò)中有該消息的多個(gè)副本在傳輸，這種方法是通過(guò)提高消息的冗余度來(lái)增加端到端消息傳輸?shù)某晒β?。?fù)制策略中分為基于洪泛，基于概率，基于調(diào)度（優(yōu)先級(jí)），基于編碼4種類型。

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

1.1.1 傳染病 （Epidemic）路由算法

著名的傳染病（Epidemic）路由算法是其中的一個(gè)代表性算法，該算法模仿生物環(huán)境中傳染性病毒的傳播方式，體現(xiàn)在DTN中，每個(gè)節(jié)點(diǎn)維護(hù)一個(gè)消息總結(jié)向量，當(dāng)兩個(gè)節(jié)點(diǎn)能夠連接時(shí)通過(guò)交換消息向量來(lái)彼此交換缺少的消息。經(jīng)過(guò)一段時(shí)間，網(wǎng)絡(luò)中的每個(gè)節(jié)點(diǎn)將收到所有的消息。傳染病路由算法本質(zhì)上是基于洪泛策略（flooding）的，優(yōu)點(diǎn)是不需要額外的拓?fù)淇刂菩畔?，同時(shí)可以取得高的消息投遞率和低的端到端時(shí)延，無(wú)需對(duì)鏈路狀態(tài)進(jìn)行預(yù)測(cè)與估計(jì)，實(shí)施起來(lái)較為簡(jiǎn)單。缺點(diǎn)是網(wǎng)絡(luò)中存在大量的冗余副本將導(dǎo)致節(jié)點(diǎn)能耗增加和緩存溢出，進(jìn)而導(dǎo)致網(wǎng)絡(luò)的資源利用率低和整體運(yùn)行效能低下，該算法主要適用于緩存和帶寬充足的場(chǎng)景。

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

與其它路由算法相比，基于一跳的路由算法是將信息從源節(jié)點(diǎn)傳送到目的節(jié)點(diǎn)最簡(jiǎn)單的方法。當(dāng)源節(jié)點(diǎn)與目的節(jié)點(diǎn)建立連接時(shí)，源節(jié)點(diǎn)立刻把信息傳送給目的節(jié)點(diǎn)。當(dāng)源節(jié)點(diǎn)和目的節(jié)點(diǎn)之間只有一跳的距離時(shí)，這種策略既簡(jiǎn)潔又有效。在這種策略中，不存在中繼的冗余信息。其優(yōu)點(diǎn)是只需要消耗很少的資源，然而這種算法最大的缺點(diǎn)就是時(shí)延較大，并且信息傳輸成功的概率較低。Frenkiel R.H.和Badrinath B.R.提出了一種基于一跳傳輸?shù)母腥緳C(jī)制，利用這種方法可以增加無(wú)線網(wǎng)絡(luò)的信息傳輸量，并且降低傳輸開銷。在ad hoc網(wǎng)絡(luò)中使用一跳傳輸策略，節(jié)點(diǎn)的移動(dòng)性會(huì)增加傳輸能力。

1.2 基于概率（歷史預(yù)測(cè)）的路由算法

基于歷史預(yù)測(cè)策略的路由算法是為了克服基于復(fù)制策略中消息復(fù)制的盲目性而提出的，通過(guò)消息歷史傳輸?shù)某晒Ω怕蔬M(jìn)行估算和比較，選擇到達(dá)目的節(jié)點(diǎn)概率更高的中繼節(jié)點(diǎn)。通過(guò)這種有選擇性的復(fù)制消息，避免生成低效傳輸?shù)南⒏北荆岣呔W(wǎng)絡(luò)的資源利用率。基于概率（歷史預(yù)測(cè)）的復(fù)制策略又可分為基于一跳和基于端到端兩種。

1.2.1 基于一跳的復(fù)制策略

1）PROPHET 路由算法

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

2）CAR路由算法

CAR （Context-aware Adaptive Routing）是一種混合式路由算法，該算法根據(jù)傳輸可能性選擇中間轉(zhuǎn)發(fā)節(jié)點(diǎn)。其中傳輸可能性由節(jié)點(diǎn)通過(guò)環(huán)境信息（Context Information）合成，包括節(jié)點(diǎn)連通性變化的頻率和當(dāng)前節(jié)點(diǎn)能量等因素。當(dāng)源節(jié)點(diǎn)和目的節(jié)點(diǎn)之間存在端到端路徑時(shí)，該算法使用同步路由轉(zhuǎn)發(fā)數(shù)據(jù)，但若網(wǎng)絡(luò)中無(wú)端到端路徑，則選擇使用異步路由來(lái)傳輸數(shù)據(jù)。為了能準(zhǔn)確有效地估計(jì)和更新路由表中的傳輸可能性，該算法使用濾波技術(shù)預(yù)測(cè)節(jié)點(diǎn)的環(huán)境信息變化。

1.2.2 基于端到端的復(fù)制策略

1）MV路由算法

MV（Meetings and Visits）則利用節(jié)點(diǎn)間的相遇概率來(lái)描述消息傳輸?shù)某晒Ω怕剩我鈨蓚€(gè)節(jié)點(diǎn)間的相遇概率作為這對(duì)節(jié)點(diǎn)的傳輸概率，在此基礎(chǔ)上通過(guò)遞歸的方式計(jì)算多跳傳輸?shù)某晒Ω怕省蓚€(gè)節(jié)點(diǎn)相遇時(shí)，交換各自的消息以及傳輸概率信息，通過(guò)比較，節(jié)點(diǎn)僅向傳輸概率更高的中繼節(jié)點(diǎn)復(fù)制消息。與基于復(fù)制策略的路由算法相比，基于歷史預(yù)測(cè)策略的路由算法由于在選擇中繼節(jié)點(diǎn)時(shí)更有目標(biāo)性和針對(duì)性，因此可以取得更高的消息投遞率和網(wǎng)絡(luò)資源利用率。

2）ORWAR路由算法

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

1.3 基于調(diào)度（優(yōu)先級(jí)）的路由算法

該算法最核心的思想是對(duì)束賦予優(yōu)先級(jí)，并按照優(yōu)先級(jí)的高低擇優(yōu)傳遞信息。該算法需要使用針對(duì)傳輸和刪除操作的優(yōu)先級(jí)函數(shù)。在洪泛傳遞信息時(shí)，該算法使用一些參數(shù)來(lái)對(duì)信息的優(yōu)先級(jí)進(jìn)行評(píng)估。其中某些參數(shù)用于評(píng)估信息從當(dāng)前節(jié)點(diǎn)傳送到目的節(jié)點(diǎn)的開銷等。

1）基于優(yōu)先級(jí)的傳染病路由算法 （Prioritized epidemic routing）

該算法的核心思想是給每一個(gè)叫做“束”（bundle）的信息指派一個(gè)優(yōu)先級(jí)。對(duì)信息的傳輸和刪除操作是由優(yōu)先級(jí)函數(shù)控制的。信息的洪泛策略是基于估計(jì)信息的優(yōu)先級(jí)而進(jìn)行的，某些參數(shù)被用于評(píng)估從當(dāng)前節(jié)點(diǎn)到目的節(jié)點(diǎn)的開銷，或是連接的出現(xiàn)和消失的時(shí)間等。相比傳統(tǒng)的傳染病路由算法，該算法能夠結(jié)合網(wǎng)絡(luò)中的拓?fù)渲R(shí)信息，更合理有效的利用網(wǎng)絡(luò)中有限的資源，缺點(diǎn)是由于引入了優(yōu)先級(jí)函數(shù)，增大了每個(gè)節(jié)點(diǎn)的計(jì)算開銷。

2）MaxProp 算法

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

1.4 基于編碼的路由算法

基于擦除碼（Eraser Code）的路由算法也可以認(rèn)為是基于復(fù)制策略的一種，它基于這樣的原理：源節(jié)點(diǎn)對(duì)消息進(jìn)行分塊，然后這些分塊以某個(gè)大于1的常數(shù)因子進(jìn)行復(fù)制轉(zhuǎn)發(fā)，當(dāng)目的節(jié)點(diǎn)收到這些分塊中的一定比例時(shí)即可重構(gòu)源消息。

基于網(wǎng)絡(luò)編碼（Network Coding）的路由算法。該算法在基于概率的路由算法的基礎(chǔ)上，引入線性網(wǎng)絡(luò)編碼技術(shù)來(lái)降低算法的代價(jià)。仿真實(shí)驗(yàn)結(jié)果表明，在一個(gè)稀疏部署的移動(dòng)網(wǎng)絡(luò)中，特別是在節(jié)點(diǎn)具有較高的丟包率時(shí)，引入網(wǎng)絡(luò)編碼技術(shù)以后，路由算法的性能提升尤為明顯。

2 路由算法策略比較

在復(fù)制策略中，大量的相同信息的拷貝將被創(chuàng)建，這些拷貝將會(huì)被傳輸給中繼結(jié)點(diǎn)。中繼節(jié)點(diǎn)接受這些拷貝，并將其存儲(chǔ)在自身的緩存中。當(dāng)這些中繼節(jié)點(diǎn)和目標(biāo)節(jié)點(diǎn)建立連接時(shí)，拷貝才會(huì)被傳輸?shù)侥康慕Y(jié)點(diǎn)，并且中繼節(jié)點(diǎn)將傳送過(guò)去的信息的緩存清空。在DTN早期的算法研究工作中，這種策略經(jīng)常被路由算法的設(shè)計(jì)者和研究者們使用。在某些移動(dòng)傳感網(wǎng)絡(luò)中，節(jié)點(diǎn)的移動(dòng)具有隨機(jī)性，此時(shí)，這種路由策略往往能夠有效的利用結(jié)點(diǎn)本身的這種隨機(jī)移動(dòng)性，從而有效的將信息傳送到目的節(jié)點(diǎn)。信息的大量復(fù)制是增加傳輸成功概率的有效手段，使用這些協(xié)議并不需要預(yù)先獲知任何關(guān)于整個(gè)網(wǎng)絡(luò)的連接狀態(tài)或知識(shí)。本文重點(diǎn)比較基于洪泛和基于編碼的路由策略。

基于洪泛策略的路由算法實(shí)現(xiàn)起來(lái)較為簡(jiǎn)單，該類算法的優(yōu)點(diǎn)是：1）不需依賴對(duì)鏈路狀態(tài)的估計(jì)；2）若節(jié)點(diǎn)的資源充足，則該種策略下的路由算法可以較為快速的實(shí)現(xiàn)信息的傳遞與轉(zhuǎn)發(fā)，從而減小傳輸?shù)臅r(shí)延，以及消息傳遞成功的概率。該類算法的缺點(diǎn)是：節(jié)點(diǎn)之間在傳輸報(bào)文時(shí)，擁有大量的冗余報(bào)文，增加了網(wǎng)絡(luò)傳輸負(fù)載。

基于編碼的方法，一般是將信息在源節(jié)點(diǎn)分塊，待其傳輸?shù)侥康墓?jié)點(diǎn)，再將其重組。其優(yōu)點(diǎn)是：提高了系統(tǒng)傳輸吞吐量。與基于其他3種策略的路由算法相比較，基于該策略的路由算法在網(wǎng)絡(luò)負(fù)載相同的情況下具有較低的傳輸時(shí)延。由于分組和編碼，在一定程度上有助于在網(wǎng)絡(luò)擁塞的情況下抗擊丟包。缺點(diǎn)是：編解碼操作會(huì)帶來(lái)一定的能量消耗。編解碼操作較為復(fù)雜。信息塊的拆分策略，目前無(wú)較好方案。

3 結(jié)束語(yǔ)

通過(guò)對(duì)容遲網(wǎng)絡(luò)路由算法相關(guān)的文獻(xiàn)，特別是近幾年來(lái)的主要研究成果進(jìn)行研究總結(jié)發(fā)現(xiàn)目前的路由協(xié)議缺乏多項(xiàng)評(píng)估指標(biāo)的綜合考慮，往往在個(gè)別指標(biāo)上性能優(yōu)越，但無(wú)法優(yōu)化多項(xiàng)指標(biāo)，網(wǎng)絡(luò)整體性能難以獲得極大的提升。因此需要利用新的分析工具研究容遲網(wǎng)絡(luò)路由，同時(shí)考慮多個(gè)設(shè)計(jì)目標(biāo)進(jìn)行優(yōu)化，建立基于多目標(biāo)優(yōu)化的高效路由協(xié)議.例如，以節(jié)點(diǎn)能量消耗、時(shí)延、傳輸率為目標(biāo)，進(jìn)行多目標(biāo)決策，設(shè)計(jì)出最優(yōu)路由協(xié)議。

[1]張龍，周賢偉，王建萍，等.容遲與容斷網(wǎng)絡(luò)中的路由協(xié)議[J].軟件學(xué)報(bào)，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的增強(qiáng)型Earliest-Delivery算法[J].電子與信息學(xué)報(bào)，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]劉舒拉.基于博弈論的無(wú)線傳感器網(wǎng)絡(luò)路由算法研究[J].現(xiàn)代電子技術(shù)，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語(yǔ)義柵格運(yùn)動(dòng)目標(biāo)信息快速分發(fā)技術(shù)[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.