黃沁芳

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

0 引 言

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

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

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

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

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

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

1.1 基本思想

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

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

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

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

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

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

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

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

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

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

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

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

2)傳輸延遲：消息到達目的節(jié)點所耗費的平均時間;

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

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

圖2 傳輸率隨時間的變化

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

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

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

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

3 結(jié)束語

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

[參考文獻]

[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].計算機研究與發(fā)展,2009,46(7):1065-1073.

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

[4] 樊秀梅,單志廣,張寶賢.容遲網(wǎng)絡(luò)體系結(jié)構(gòu)及其關(guān)鍵技術(shù)研究[J].電子學(xué)報,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.