黃沁芳

(集美大學(xué) 誠(chéng)毅學(xué)院， 福建 廈門 361021)

0 引 言

延遲容忍網(wǎng)絡(luò)[1-2](Delay Tolerant Network，DTN)是一種具有鏈路頻繁斷裂、高延遲、網(wǎng)絡(luò)拓?fù)鋭?dòng)態(tài)變化、節(jié)點(diǎn)資源有限等特點(diǎn)的新型網(wǎng)絡(luò)體系結(jié)構(gòu)。在現(xiàn)實(shí)中很多應(yīng)用領(lǐng)域都屬于這類網(wǎng)絡(luò)，例如車載網(wǎng)絡(luò)、無(wú)線傳感網(wǎng)絡(luò)、救災(zāi)現(xiàn)場(chǎng)、野戰(zhàn)通信、星際網(wǎng)絡(luò)等[3]。

與傳統(tǒng)網(wǎng)絡(luò)的端到端的通信機(jī)制不同，在DTN中，節(jié)點(diǎn)與節(jié)點(diǎn)之間并不一定能建立一條穩(wěn)定可靠地端到端的通信路徑，先探路后轉(zhuǎn)發(fā)的傳統(tǒng)路由方式不再適用，因此DTN中使用的是一種“存儲(chǔ)—攜帶—轉(zhuǎn)發(fā)”的路由方式[4]：當(dāng)一個(gè)節(jié)點(diǎn)收到消息時(shí)，如果沒(méi)有路徑可到達(dá)目標(biāo)節(jié)點(diǎn)或其它節(jié)點(diǎn)，先將消息保存在緩存中，并且一直攜帶直到遇到一個(gè)可轉(zhuǎn)發(fā)消息的節(jié)點(diǎn)。轉(zhuǎn)發(fā)路徑的路由選擇可以是隨機(jī)的，也可以根據(jù)節(jié)點(diǎn)的歷史信息預(yù)測(cè)。在延遲容忍網(wǎng)絡(luò)中，由于鏈路頻繁斷裂、網(wǎng)絡(luò)拓?fù)鋭?dòng)態(tài)變化等特點(diǎn)，要獲得節(jié)點(diǎn)的完整信息不是容易的事情，那么消息的傳輸就變得很難確定。如何有效地將消息轉(zhuǎn)發(fā)出去，是DTN路由要解決的問(wèn)題。

近年來(lái)，研究者們已經(jīng)提出了幾種典型的DTN路由算法，其中Epidemic算法[5]是最為經(jīng)典的算法之一，就是將消息類似病毒的方式傳播給網(wǎng)絡(luò)中所有遇到的節(jié)點(diǎn)，直至達(dá)到目標(biāo)節(jié)點(diǎn)。Epidemic算法是以不斷擴(kuò)散消息副本的方式將消息傳送到目的節(jié)點(diǎn)，在某些特定的網(wǎng)絡(luò)中具有很高的傳輸成功率和很小的延遲，但它需消耗大量的網(wǎng)絡(luò)資源，如帶寬、緩存、能量等，因此當(dāng)網(wǎng)絡(luò)擴(kuò)大，消息副本數(shù)量增加時(shí)，其網(wǎng)絡(luò)性能就會(huì)大大降低。

為了控制資源開銷，Spray and Wait算法[6]采用將消息副本數(shù)量固定一個(gè)配額，消息的轉(zhuǎn)發(fā)方式分為傳播(Spray)和等待(Wait)兩個(gè)階段。在消息產(chǎn)生的時(shí)候就確定了副本數(shù)量為L(zhǎng)。在傳播階段，當(dāng)攜帶有消息副本的節(jié)點(diǎn)與無(wú)相同消息的節(jié)點(diǎn)相遇時(shí)，節(jié)點(diǎn)會(huì)將攜帶的消息副本的一半發(fā)送給對(duì)方節(jié)點(diǎn)，自己保留剩余的一半，直到所攜帶的消息副本數(shù)量為1為止；在等待階段，收到消息的節(jié)點(diǎn)等待與目標(biāo)節(jié)點(diǎn)相遇并將消息轉(zhuǎn)發(fā)給目標(biāo)節(jié)點(diǎn)。由于消息副本的配額是固定的，副本數(shù)量L不會(huì)隨著網(wǎng)絡(luò)中節(jié)點(diǎn)數(shù)的增加而增大，因而有很好的擴(kuò)展性，有效地控制了開銷。

本文基于Spray and Wait算法，提出了基于節(jié)點(diǎn)接觸頻率的有效路由算法(Efficient Routing Based on Inter-contact Frequencies，ERBIF)。該算法根據(jù)本節(jié)點(diǎn)在網(wǎng)絡(luò)中與其它節(jié)點(diǎn)曾有過(guò)的接觸頻率，動(dòng)態(tài)分配消息副本，接觸頻率高的節(jié)點(diǎn)優(yōu)先獲得消息副本。

1 基于節(jié)點(diǎn)接觸頻率的路由算法

1.1 基本思想

圖1 節(jié)點(diǎn)接觸頻率分配示例

在某些DTN網(wǎng)絡(luò)中，節(jié)點(diǎn)的移動(dòng)頻率和范圍都很大，節(jié)點(diǎn)與節(jié)點(diǎn)之間的接觸頻率也會(huì)不一樣，那么有些節(jié)點(diǎn)與其它節(jié)點(diǎn)的接觸頻率就會(huì)比較高。當(dāng)節(jié)點(diǎn)要轉(zhuǎn)發(fā)消息時(shí)，應(yīng)先將消息轉(zhuǎn)發(fā)給接觸頻率最高的相鄰節(jié)點(diǎn)。例如，網(wǎng)絡(luò)中有如圖1所示節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)都需要維護(hù)一張自己與其它節(jié)點(diǎn)的接觸頻率值的數(shù)據(jù)表，假設(shè)節(jié)點(diǎn)A要轉(zhuǎn)發(fā)消息，根據(jù)其接觸頻率值數(shù)據(jù)表，與節(jié)點(diǎn)A接觸頻率由高到低的節(jié)點(diǎn)依次是B、C、D，那么節(jié)點(diǎn)A就將消息副本(數(shù)量為L(zhǎng))的一半先轉(zhuǎn)發(fā)給節(jié)點(diǎn)B，然后再將剩余的消息副本(此時(shí)數(shù)量為L(zhǎng)/2)的一半轉(zhuǎn)發(fā)給節(jié)點(diǎn)C，再將剩余一半轉(zhuǎn)發(fā)給D，直至節(jié)點(diǎn)A的消息副本數(shù)量減小到1為止。節(jié)點(diǎn)B收到消息后，根據(jù)其接觸頻率值數(shù)據(jù)表按照接觸頻率由高到低將消息依次轉(zhuǎn)發(fā)給節(jié)點(diǎn)C、G、F。其它收到消息副本的節(jié)點(diǎn)以同樣的方法按照自己的接觸頻率值數(shù)據(jù)表來(lái)轉(zhuǎn)發(fā)消息。這樣可以很快將緩存的消息發(fā)送到目標(biāo)節(jié)點(diǎn)，能降低延遲，節(jié)省緩存空間，也有效地防止數(shù)據(jù)的丟失和溢出。

1.2 節(jié)點(diǎn)的接觸頻率

根據(jù)LIAO Yong等[7]給出的一種計(jì)算節(jié)點(diǎn)間平均接觸頻率的方法，定義時(shí)間單元t內(nèi)的平均接觸頻率為fi j=Ci j/t。將此平均接觸頻率記錄在每個(gè)節(jié)點(diǎn)的接觸頻率值數(shù)據(jù)表中，以此來(lái)估計(jì)一個(gè)節(jié)點(diǎn)遇到其它節(jié)點(diǎn)的概率。數(shù)據(jù)表中所有頻率值按從大到小排列。平均接觸頻率值越大，遇到相應(yīng)節(jié)點(diǎn)的機(jī)會(huì)就越高。

由于fi j可以由節(jié)點(diǎn)i與節(jié)點(diǎn)j的歷史相遇信息得到，隨著時(shí)間的推移，兩節(jié)點(diǎn)相遇的頻率值可以得到逐步更新。從而使得消息副本的轉(zhuǎn)發(fā)能夠按照當(dāng)前的節(jié)點(diǎn)運(yùn)動(dòng)規(guī)律進(jìn)行。但當(dāng)網(wǎng)絡(luò)規(guī)模很大，節(jié)點(diǎn)數(shù)很多的時(shí)候，對(duì)于節(jié)點(diǎn)接觸頻率的預(yù)估會(huì)變得很復(fù)雜，因此，此種機(jī)制僅適用于小規(guī)模的DTN網(wǎng)絡(luò)，本文假設(shè)在只有兩跳的網(wǎng)絡(luò)中來(lái)實(shí)現(xiàn)。在簡(jiǎn)化的只有兩跳的虛擬網(wǎng)絡(luò)中只有源節(jié)點(diǎn)、目的節(jié)點(diǎn)及鄰居節(jié)點(diǎn)，從源節(jié)點(diǎn)到目的節(jié)點(diǎn)可能有m條路徑，只需要按照m條路徑的節(jié)點(diǎn)接觸頻率值來(lái)分配消息副本即可。

1.3 節(jié)點(diǎn)間消息副本的分配

Spray and Wait算法將消息副本數(shù)量固定一個(gè)配額，在源節(jié)點(diǎn)就確定了需要轉(zhuǎn)發(fā)的消息副本數(shù)量。由于DTN網(wǎng)絡(luò)動(dòng)態(tài)變化，由源節(jié)點(diǎn)確定的消息副本數(shù)量不一定適合中繼節(jié)點(diǎn)。在ERBIF算法中，每個(gè)節(jié)點(diǎn)根據(jù)當(dāng)前所處位置與相鄰節(jié)點(diǎn)的接觸頻率來(lái)動(dòng)態(tài)選擇要轉(zhuǎn)發(fā)的消息副本數(shù)量。

網(wǎng)絡(luò)中節(jié)點(diǎn)的中心性[8]是節(jié)點(diǎn)重要性的度量。例如在社會(huì)網(wǎng)絡(luò)中，中心性高的人比較活躍，接觸其他人的頻率也較高。同樣的，中心性高的節(jié)點(diǎn)也維持了更多和網(wǎng)絡(luò)中其它節(jié)點(diǎn)的接觸，從而有更多和其它節(jié)點(diǎn)通信的機(jī)會(huì)。當(dāng)兩個(gè)節(jié)點(diǎn)相遇時(shí)，接觸頻率高的節(jié)點(diǎn)自然將獲得較多的消息副本。

假定有N個(gè)節(jié)點(diǎn)的DTN網(wǎng)絡(luò)中，源節(jié)點(diǎn)產(chǎn)生的消息副本數(shù)量為L(zhǎng)。當(dāng)攜帶消息副本的節(jié)點(diǎn)A遇到節(jié)點(diǎn)B，如果節(jié)點(diǎn)B攜帶相同的消息，則不轉(zhuǎn)發(fā)；如果節(jié)點(diǎn)B沒(méi)有此消息，則根據(jù)接觸頻率值數(shù)據(jù)表，找出A、B兩節(jié)點(diǎn)的接觸頻率fAB，根據(jù)fAB值在數(shù)據(jù)表中排列的順序號(hào)(假設(shè)為m，m≥1)，則節(jié)點(diǎn)A向節(jié)點(diǎn)B轉(zhuǎn)發(fā)消息副本數(shù)量為L(zhǎng)/2m。fAB在數(shù)據(jù)表中值最大，則m=1；排第二時(shí)，m=2；以此類推。節(jié)點(diǎn)B也按類似的方式將消息副本轉(zhuǎn)發(fā)出去，直至消息副本最終到達(dá)目的節(jié)點(diǎn)。

2 仿真結(jié)果及分析

本文使用ONE仿真軟件作為實(shí)驗(yàn)?zāi)M平臺(tái)，版本1.5.0。采用RWP移動(dòng)模型，在相同場(chǎng)景下，對(duì)本文提出的ERBIF算法和Epidemic以及Spray and Wait算法的性能進(jìn)行對(duì)比，并用以下3個(gè)參數(shù)進(jìn)行性能評(píng)估：

1)傳輸率：目的節(jié)點(diǎn)成功接受到的消息數(shù)量與源節(jié)點(diǎn)產(chǎn)生的消息總數(shù)之比;

2)傳輸延遲：消息到達(dá)目的節(jié)點(diǎn)所耗費(fèi)的平均時(shí)間;

3)傳輸次數(shù)：消息從源節(jié)點(diǎn)到目的節(jié)點(diǎn)傳輸?shù)目偞螖?shù)。

網(wǎng)絡(luò)的仿真環(huán)境：800 m×800 m的網(wǎng)絡(luò)中，隨機(jī)分布25個(gè)節(jié)點(diǎn)，節(jié)點(diǎn)的移動(dòng)速度在0.5～2.0 m/s范圍內(nèi)，并且在0～120 s區(qū)間中隨機(jī)確定暫停時(shí)間，每個(gè)節(jié)點(diǎn)的移動(dòng)范圍為30 m，緩存空間為5 MB。消息產(chǎn)生的時(shí)間間隔為20～30 s之間，每個(gè)消息大小為512 KB。

圖2 傳輸率隨時(shí)間的變化

從圖2可以看出，隨著時(shí)間推移，3種算法的傳輸率逐漸趨于一致，增長(zhǎng)幅度也趨于平緩。Epidemic算法和Spray and Wait算法對(duì)于消息的轉(zhuǎn)發(fā)是隨機(jī)的，隨著時(shí)間的增長(zhǎng)，所需緩存增加，丟棄的數(shù)據(jù)也會(huì)增加，而ERBIF算法依據(jù)節(jié)點(diǎn)的接觸頻率，消息的轉(zhuǎn)發(fā)機(jī)會(huì)變多，其傳輸率也會(huì)有所提高。相對(duì)其它兩種算法而言，ERBIF算法的傳輸率也略高。

從圖3可以看出，隨著時(shí)間增長(zhǎng)，3種算法的傳輸延遲也會(huì)逐漸增大。如果節(jié)點(diǎn)間的接觸頻率高，那么消息的轉(zhuǎn)發(fā)速度也會(huì)變快，基于接觸頻率的ERBIF算法能夠以更大的機(jī)會(huì)，以更快的速度將消息轉(zhuǎn)發(fā)到目的節(jié)點(diǎn)，因此它的傳輸延遲會(huì)略低于Epidemic算法和Spray and Wait算法。

圖4反映了ERBIF、Epidemic和Spray and Wait 3種算法消耗網(wǎng)絡(luò)資源的情況，隨著時(shí)間增加，傳輸次數(shù)不斷增加，其消耗的帶寬、能量和緩存也越來(lái)越多。Epidemic算法由于沒(méi)有限制消息副本的數(shù)量，消息的轉(zhuǎn)發(fā)是隨機(jī)的，因此其傳輸次數(shù)最多；有固定消息副本配額的Spray and Wait算法傳輸次數(shù)相對(duì)較少。而ERBIF算法，由于消息副本數(shù)量是固定一個(gè)配額，且按節(jié)點(diǎn)間接觸頻率大小，以最大機(jī)會(huì)到達(dá)目的節(jié)點(diǎn)來(lái)轉(zhuǎn)發(fā)消息，因此其傳輸次數(shù)也是最少的。

圖3 傳輸延遲隨時(shí)間的變化 圖4 傳輸次數(shù)隨時(shí)間的變化

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

在Epidemic算法和Spray and Wait算法的基礎(chǔ)上，本文引入了一種基于接觸頻率的路由算法。通過(guò)統(tǒng)計(jì)節(jié)點(diǎn)與節(jié)點(diǎn)之間在某一時(shí)間段內(nèi)的接觸頻率值，根據(jù)所有頻率值大小來(lái)動(dòng)態(tài)分配轉(zhuǎn)發(fā)消息副本的順序和數(shù)量。仿真結(jié)果顯示，在有限的網(wǎng)絡(luò)資源，網(wǎng)絡(luò)規(guī)模不大的情況下，這種基于節(jié)點(diǎn)的接觸頻率來(lái)轉(zhuǎn)發(fā)消息的算法，能較好地提高DTN網(wǎng)絡(luò)的性能，有效地節(jié)約資源，降低延遲。

[參考文獻(xiàn)]

[1] FALL K.A delay-tolerant network architecture for challenged internets[C]//Proceedings of SIGCOMM.New York:ACM Press,2003:27-34.

[2] 肖明軍,黃劉生.容遲網(wǎng)絡(luò)路由算法[J].計(jì)算機(jī)研究與發(fā)展,2009,46(7):1065-1073.

[3] 陳晨,高新波.一種無(wú)線傳感器網(wǎng)絡(luò)移動(dòng)性支持自適應(yīng)MAC協(xié)議[J].西安電子科技大學(xué)學(xué)報(bào):自然科學(xué)版，2010,37(2):279-284.

[4] 樊秀梅,單志廣,張寶賢.容遲網(wǎng)絡(luò)體系結(jié)構(gòu)及其關(guān)鍵技術(shù)研究[J].電子學(xué)報(bào),2008,36(1):161-170.

[5] VAHDAT A,BECKER D.Epidemic routing for partially connected ad hoc networks.Duke Technical Report CS-2000-06[R].Dur-ham:Duke University,2000.

[6] SPYROPOULOS T,PSOUNIS K,RAGHAVENDRA C S.Spray and Wait:An efficient routing scheme for intermittently connect-ed mobile networks[C]//Proceedings of the ACM SIGCOMM Workshop on Delay-Tolerant Networking.Philadelphia,Pennsylvania,USA,2005:252-259.

[7] LIAO Yong,TAN Kun.Estimation based Erasure-coding Routing in Delay Tolerant Networks[C]//Proceeding of the 2006 International Conference on Wireless Communication and Mobile Computing.British Columbia:Vancouver,2006:557-562.

[8] DALY E M,HAAHR M.Social network analysis for information flow in disconnected delay-tolerant MANETs[J].IEEE Trans on Mobile Computing,2009,8(5):606-621.