,, ,

(青島大學(xué) 計算機科學(xué)技術(shù)學(xué)院,山東 青島 266071)

0 概述

容遲網(wǎng)絡(luò)(Delay Tolerant Network,DTN)[1-3]是近幾年國內(nèi)外無線網(wǎng)絡(luò)研究領(lǐng)域內(nèi)的一個新興熱門研究方向,DTN是一種不需要在源節(jié)點和目的節(jié)點之間存在一條完整通信路徑,利用節(jié)點移動帶來的相遇機會實現(xiàn)網(wǎng)絡(luò)通信的自組織網(wǎng)絡(luò)。由于DTN中節(jié)點的移動性,以及移動節(jié)點的無線通信距離有限,節(jié)點間的通信頻繁中斷等特點[4-5],節(jié)點間只能進行間斷性互連,所以使得源節(jié)點到目的節(jié)點之間無法形成一條穩(wěn)定的通信路徑[6],整個網(wǎng)絡(luò)拓撲結(jié)構(gòu)處于動態(tài)變化中。這種極端的網(wǎng)絡(luò)環(huán)境使得傳統(tǒng)Internet的路由算法和網(wǎng)絡(luò)協(xié)議無法適用于DTN中。正是由于DTN的這種網(wǎng)絡(luò)特性,使其在支撐環(huán)境苛刻條件下的應(yīng)用獨具優(yōu)勢,因而使得容遲網(wǎng)絡(luò)成為了一個熱門研究方向,并得到了廣泛的關(guān)注和研究,DTN中實現(xiàn)消息的有效傳遞是最關(guān)鍵的問題[7],DTN路由算法研究目前也是DTN研究中研究成果最多,最為成熟的一個方向。目前DTN應(yīng)用的場景主要有,野生動物追蹤的傳感網(wǎng)絡(luò)[8-10]、移動車載網(wǎng)絡(luò)[11-13]、水下傳感器網(wǎng)絡(luò)[14-15]和Internet接入服務(wù)的信息網(wǎng)絡(luò)[16]等。

DTN利用節(jié)點在移動過程中相遇的機會(DTN中稱為Contact)進行消息傳輸,采用“存儲—攜帶—轉(zhuǎn)發(fā)”這一路由模式來實現(xiàn)節(jié)點間的通信。近幾年,在DTN路由算法方面許多學(xué)者提出了大量研究成果。從節(jié)點向網(wǎng)絡(luò)中注入消息副本的數(shù)量的角度來看,DTN的路由算法可以分為兩大類:基于復(fù)制策略的路由算法和基于轉(zhuǎn)發(fā)策略的路由算法。

基于復(fù)制策略的路由算法,通過提高消息在網(wǎng)絡(luò)中副本的數(shù)量,使得消息可以在同一時刻有多個副本在進行傳輸,從而來增加消息成功投遞至目的節(jié)點的概率,最具代表性的算法有傳染病算法Epidemic[17-19],Spray and Wait[20-22]和PRoPHET[23-24]。Epidemic算法會在2個節(jié)點相遇時向?qū)Ψ綇?fù)制其消息向量中沒有的消息。Spray and Wait算法通過控制網(wǎng)絡(luò)中消息副本的數(shù)量,在Spray階段將消息副本進行散播,在Wait階段一直等待遇到目的節(jié)點。PRoPHET算法利用節(jié)點對相遇的歷史信息和傳遞性來預(yù)測節(jié)點同目的節(jié)點相遇的概率,將消息傳遞給鄰居節(jié)點中投遞概率比當前節(jié)點更大的節(jié)點?；谵D(zhuǎn)發(fā)策略的路由算法中,算法會根據(jù)網(wǎng)絡(luò)的拓撲知識,然后按照一定的優(yōu)化目標進行有目的的選擇下一跳中繼節(jié)點進行消息傳遞,從而選擇出一條較優(yōu)的路徑將消息傳輸?shù)侥康墓?jié)點,在傳輸過程中,中繼節(jié)點不會對消息進行復(fù)制。最具代表性的算法有Direct Delivery[25]和FirstContact算法[26]。Direct Delivery算法中源節(jié)點會一直攜帶消息直到遇到目的節(jié)點才會進行消息傳輸。FirstContact算法中攜帶消息的源節(jié)點在整個移動過程中,將消息轉(zhuǎn)發(fā)給第一個相遇的節(jié)點。

目前一種比較認可的提高投遞率的方式是基于復(fù)制策略,增加網(wǎng)絡(luò)中消息副本數(shù)量。為此,本文提出一種基于歷史和位置信息的容遲網(wǎng)絡(luò)路由算法(Routing Algorithm in Delay Tolerant Network Based on History and Location Information,HLRA),從歷史策略和地理策略兩方面增加消息投遞率,降低消息傳輸?shù)钠骄鶗r延。

1 路由算法設(shè)計

1.1 動機

基于消息復(fù)制策略的路由算法,在網(wǎng)絡(luò)中對同一消息進行復(fù)制,使其產(chǎn)生大量消息副本,只要其中一個攜帶消息副本的節(jié)點與目的節(jié)點相遇,那么消息就傳輸成功。大量的研究結(jié)果表明,DTN中基于消息復(fù)制策略的路由算法可以有效地提高消息投遞率[27]。另一方面單純的增加消息副本,容易導(dǎo)致網(wǎng)絡(luò)中消息洪泛,并且由于網(wǎng)絡(luò)中節(jié)點的緩存空間、能量等資源有限,大量的消息副本會增加網(wǎng)絡(luò)中節(jié)點資源消耗,導(dǎo)致節(jié)點的緩存溢出,反而降低了網(wǎng)絡(luò)的路由性能。

為了在保持較高的消息投遞率的同時,降低網(wǎng)絡(luò)中節(jié)點資源的消耗,必須控制消息的盲目復(fù)制。很多學(xué)者想通過獲取網(wǎng)絡(luò)拓撲結(jié)構(gòu)知識或其他額外輔助信息來增加DTN消息投遞率,降低能耗和時延。但是由于網(wǎng)絡(luò)中節(jié)點的移動,節(jié)點耗盡能源而停止工作或者在網(wǎng)絡(luò)中添加新的節(jié)點,使得DTN的拓撲結(jié)構(gòu)時刻處于動態(tài)變化中,難以獲取,且時效性和準確性低。

然而只是獲取節(jié)點在網(wǎng)絡(luò)中的位置信息,通過GPS定位系統(tǒng)或者相關(guān)的定位算法即可實現(xiàn),節(jié)點中保存位置信息也不會消耗太多資源,獲取的位置信息比網(wǎng)絡(luò)拓撲知識準確性和時效性更強,并且地理路由算法實現(xiàn)相對簡單,不需要節(jié)點有太高的計算處理能力,對節(jié)點資源的消耗較少。

1.2 算法簡介

HLRA算法的整體執(zhí)行流程,如圖1所示。由于路由算法解決的是在消息傳輸過程中的“路徑”選擇問題,因此此流程圖中只描述了與路由算法相關(guān)的部分。

圖1 HLRA路由算法流程

在DTN中,只有當節(jié)點相遇的時候才會出現(xiàn)消息傳輸,所以流程開始,當節(jié)點相遇時,相遇節(jié)點各自更新自己所維護的節(jié)點歷史相遇次數(shù)表。之后根據(jù)節(jié)點所攜帶的消息,會從鄰居節(jié)點中選擇出所有消息的下一跳節(jié)點。首先會根據(jù)歷史策略進行,如果歷史策略選擇出了下一跳節(jié)點,則繼續(xù)處理下一個消息。如果歷史策略沒有為消息選擇出下一跳節(jié)點,則轉(zhuǎn)至運行地理策略為其選擇下一跳節(jié)點,之后繼續(xù)嘗試下一個消息,直到節(jié)點所攜帶的消息都已經(jīng)處理完畢。然后又會對新的相遇節(jié)點進行消息的整個傳輸流程[28]。

1.3 模型假設(shè)和符號說明

本文符號說明如表1所示,在詳細介紹本文提出的路由算法HLRA之前,先做出如下假設(shè):

1)網(wǎng)絡(luò)中的節(jié)點都在此網(wǎng)絡(luò)設(shè)置的整體范圍內(nèi)移動,不會移動到范圍以外。

2)網(wǎng)絡(luò)中的節(jié)點可以通過借助GPS來獲取其當前的位置信息。

3)節(jié)點在通信范圍內(nèi)與其他節(jié)點建立連接時,可以收集相遇次數(shù)等信息。

4)節(jié)點移動存在慣性。

表1 符號說明

1.4 下一跳節(jié)點選擇策略

在DTN路由算法中,由于節(jié)點的間歇性連接,無法實現(xiàn)通過建立一條完整通信路徑進行消息傳輸,只能依靠節(jié)點移動帶來的相遇機會來選擇消息的下一跳節(jié)點進行消息路由,好的下一跳節(jié)點會縮短消息成功投遞的時間,提高投遞率,降低時延。所以,路由算法中下一跳節(jié)點的篩選方法尤為重要,它對于消息的成功傳遞有著極大的影響[29]。

本文HLRA路由算法在下一跳節(jié)點的選擇上采用如下2個策略:

1)歷史策略,以節(jié)點間歷史相遇次數(shù)為依據(jù),在鄰居節(jié)點中選擇同消息的目的節(jié)點歷史相遇次數(shù)最大的鄰居節(jié)點作為下一跳節(jié)點,以此來增加消息投遞的準確性。

2)地理策略,當歷史策略未選出下一跳節(jié)點則執(zhí)行本策略。利用節(jié)點的位置信息,在當前消息節(jié)點的鄰居節(jié)點中選擇由兩個節(jié)點移動方向所構(gòu)成夾角最大的一對節(jié)點作為消息的下一跳節(jié)點,增大消息的覆蓋范圍,以減少消息的投遞時延。

1.4.1 歷史策略

為了防止盲目的過度復(fù)制消息,浪費節(jié)點資源。HLRA算法的歷史策略是盡可能提高消息傳輸至目的節(jié)點的準確性。在實際應(yīng)用中,DTN里的節(jié)點運動在很多情況下是有一定規(guī)律可循或者可以預(yù)測的,比如車載網(wǎng)絡(luò)中的汽車運行軌跡,野生動物追蹤網(wǎng)絡(luò)中動物遷徙路線等。在DTN中,節(jié)點在預(yù)先設(shè)定的網(wǎng)絡(luò)范圍中移動,會不斷地與其他節(jié)點相遇,2個節(jié)點在某一時刻相遇,很可能在之后某一時刻會再次相遇,也就意味著節(jié)點間的歷史相遇信息對于節(jié)點未來的相遇有較強的預(yù)測指示作用。

為提高消息的投遞率,在每次節(jié)點相遇的時刻,更新維護當前節(jié)點的歷史節(jié)點相遇次數(shù)表T。每個節(jié)點需要維護一個記錄與其他節(jié)點歷史相遇次數(shù)的表T,Cij=Ti(j)表示當前節(jié)點Ni與節(jié)點Nj歷史相遇的次數(shù)。為了評估當前節(jié)點Ni的相遇節(jié)點Nj是否有資格作為消息的下一跳節(jié)點,在每個消息中都會有一個次數(shù)等級S,用于記錄消息在傳輸過程中遇到的與其目的節(jié)點歷史相遇次數(shù)最大值,其初始值為0,用于在歷史策略中選擇下一跳節(jié)點時與鄰居節(jié)點中的T值進行比較,并且次數(shù)等級S的值會及時更新并隨著消息復(fù)制被拷貝到下一跳節(jié)點。

利用歷史策略進行下一跳節(jié)點選擇時,需要選出鄰居節(jié)點T表中與消息的目的節(jié)點的相遇次數(shù)C最大的鄰居節(jié)點,比較C是否大于消息的當前次數(shù)等級S,只有鄰居節(jié)點與消息目的節(jié)點歷史相遇次數(shù)C大于消息的次數(shù)等級S,才會將消息復(fù)制給此鄰居節(jié)點,反之,則說明此節(jié)點與消息的目的節(jié)點相遇機會沒有消息當前所在節(jié)點遇到目的節(jié)點的機率大,所以不會向此鄰居節(jié)點復(fù)制消息。如圖2所示,當前節(jié)點Ni攜帶消息M和節(jié)點Nj相遇,消息M的目的節(jié)點是N10,M的當前次數(shù)等級S是0。按照歷史策略,Ni和Nj首先各自更新自身的T表,檢查Nj是否可以作為下一跳節(jié)點,會首先對Ni節(jié)點攜帶的消息M中的次數(shù)等級S和從節(jié)點Nj的T中所獲得的Cj,10進行比較,S=0

圖2 歷史策略選擇下一跳節(jié)點示意圖

歷史策略在鄰居節(jié)點中選擇與消息的目的節(jié)點歷史相遇次數(shù)最多,且相遇次數(shù)C要大于消息的次數(shù)等級S的鄰居節(jié)點作為下一跳節(jié)點。

在算法第1行中,由于當前節(jié)點與周圍鄰居節(jié)點相遇,所以首先要更新各自維護的T表。算法第2行對若干個鄰居節(jié)點按照T表中消息目的節(jié)點的歷史相遇次數(shù)的大小降序排列,取序列第一個節(jié)點與消息的S值進行比較。算法第3行～第7行,將消息的次數(shù)等級S與之前獲得的第一個節(jié)點的歷史相遇次數(shù)C進行比較,如果S

算法1歷史策略算法描述

輸入currentNode,neighborNodeList,Message

輸出nextHop

1.更新currentNode和neigborNodeList各自的表 T

2.將neighborNodeList中的節(jié)點按C=T(Message.des)的大小降序排列,neighborNode = neighborNodeList中的第一個

3.If Message.S

4. Message.S=neighborNode.C

5. neighborNode.add(Message.replicate())

6. nextHop = neighborNode

7.end if

8.else nextHop = null

9.return nextHop

歷史策略算法第1步更新當前節(jié)點和鄰居節(jié)點歷史相遇次數(shù)表T中值,其時間復(fù)雜度Time(n)取決于要更新T表的節(jié)點數(shù)量n,Time(n)=O(n)。第2步對鄰居節(jié)點進行排序,選擇相對穩(wěn)定的快速排序,時間復(fù)雜度為Time(n)=O(nlogn)。第3步通過進行比較相遇相遇次數(shù)和次數(shù)等級的值來獲取下一跳節(jié)點時間復(fù)雜度O(1)。所以,歷史策略性能主要受算法第一步節(jié)點的數(shù)量影響,算法時間復(fù)雜度為Time(n)=O(n)。

1.4.2 地理策略

由于消息的次數(shù)等級S隨著遇到的節(jié)點越多而逐漸更新增大,因此到后期,次數(shù)等級S變大后,在一個區(qū)域內(nèi)可能很難再通過歷史策略找到與目的節(jié)點歷史相遇次數(shù)C大于S的節(jié)點作為下一跳節(jié)點。所以就需要擴大消息的覆蓋范圍,使得消息分布更廣,從而推動歷史策略的執(zhí)行,增加消息的投遞率。因此,地理策略的主要目的就是將消息擴散出去,通過增大消息覆蓋面積來縮短消息到達目的節(jié)點的時間,提高投遞率。

節(jié)點在一定時間段內(nèi),移動的方向大致是朝同一個方向的或者同一趨勢。所以,地理策略就是根據(jù)節(jié)點的移動方向從鄰居節(jié)點中篩選出合適的節(jié)點作為下一跳節(jié)點,進行消息復(fù)制,擴大消息的覆蓋面積。而地理策略的出發(fā)點就是盡可能選擇當前節(jié)點的周圍鄰居節(jié)點中由兩個節(jié)點移動方向所形成的夾角最大的兩個節(jié)點作為下一跳節(jié)點,以實現(xiàn)消息副本以當前節(jié)點移動方向為中軸向兩側(cè)均勻擴散,進而增大消息覆蓋面積。

如圖3所示,在某一時刻某一區(qū)域,當前節(jié)點Ns周圍有多個鄰居節(jié)點Na、Nb、Ni、Nj,它們都有各自的移動軌跡。虛線小圓圈代表節(jié)點上一時刻的位置,實線陰影小圓點代表節(jié)點當前位置。

圖3 消息擴散示意圖

(1)

計算出構(gòu)成夾角的2個節(jié)點的移動方向后,2個節(jié)點移動方向夾角差值的絕對值就是2個節(jié)點構(gòu)成的夾角的大小。通過式(2)計算此節(jié)點對移動方向所構(gòu)成的夾角的大小。就圖3中2個夾角θ1和θ2,其他節(jié)點暫時不比較,夾角θ1要更大一些,所以,Ni和Nj可以作為下一跳節(jié)點進行消息復(fù)制:

θ=|θi-θj|

(2)

夾角θ越大,則鄰居節(jié)點與攜帶信息的當前節(jié)點移動區(qū)域的重合概率就會越小,從而避免了相同消息的副本在同一塊區(qū)域內(nèi)冗余所造成的節(jié)點資源浪費。除了要考慮節(jié)點移動方向夾角的問題,還要考慮當前節(jié)點Ns的移動方向問題。因為通過最大夾角篩選出的節(jié)點對中,會存在某個節(jié)點的移動方向非常接近節(jié)點Ns的移動方向,如果選擇這樣的節(jié)點對作為下一跳節(jié)點,也會導(dǎo)致在一個區(qū)域內(nèi)同一消息副本冗余,造成節(jié)點資源浪費。

所以,本文通過增加一個條件來進行選擇,在節(jié)點對夾角最大的前提下,攜帶消息的當前節(jié)點Ns的移動方向Ds比較好的情況是在夾角的正中方向,這樣作為下一跳節(jié)點的Ni和Nj以當前節(jié)點Ns的移動方向Ds為中軸平均向兩邊輻射,消息覆蓋面積會更理想。通過比較所有節(jié)點對P所構(gòu)成移動方向夾角θ的大小,然后按照θ大小進行降序排列,選擇前3個夾角的節(jié)點對作為下一跳節(jié)點的候選節(jié)點,通過式(3)進一步判斷節(jié)點對P的中心方向D(P)和當前節(jié)點Ns的移動方向Ds的相對位置ω。D(P)可由節(jié)點對P中2個節(jié)點當前位置和歷史位置坐標中心點通過式(1)計算獲得。ω值越小,說明Ns的移動方向越接近夾角的中心位置,從而節(jié)點對P中的2個節(jié)點就會以Ns的移動方向平均向兩側(cè)輻射。式(4)通過比較節(jié)點對P1和P2的ω值,獲取ω值更小的節(jié)點對。若ω(P1)<ω(P2),則f(P1,P2)=P1,否則f(P1,P2)=P2。從3個夾角中利用式(4)計算出ω值最小的節(jié)點對P,將此節(jié)點對P中的2個節(jié)點作為下一跳節(jié)點進行消息復(fù)制,來有效地擴大消息覆蓋面積。

ω(P1) = |Ds-D(P)|

(3)

(4)

如果當前節(jié)點的鄰居節(jié)點的數(shù)量不大于2的時候,即無法進行節(jié)點對夾角的比較,只需要直接對鄰居節(jié)點進行消息復(fù)制。算法2給出了地理策略的算法描述。

算法2地理策略算法描述

輸入neighborNodeList

輸出nextHopPair

1.初始化nextHopPair

2.if neighborNodeList.length <= 2 then

3. nextHopPair = neighborNodeList.replicate()

4.else

6. 用式(1)、式(2)計算每一個組合的夾角

7. end for

8.按夾角大小照降序排列節(jié)點對

9.取序列前3

10.for P in P1,P2,P3

11. 用式(4)計算每一個節(jié)點對的ω值

12. Pbest=f(P1,P2)

13.end for

14.將Pbest中的2個節(jié)點加入到nextHopPair

15.end if

16.return nextHopPair

在算法2的第2行～第3行中,首先判斷周圍的鄰居節(jié)點的個數(shù),如果鄰居節(jié)點數(shù)量小于或等于2,那么直接將此節(jié)點選為下一跳鄰居節(jié)點進行消息復(fù)制。算法第5行～第7行,對鄰居節(jié)點中每對節(jié)點組合計算其移動方向的夾角θ。算法第8行,將所有節(jié)點對P按照計算出的移動方向夾角大小進行降序排序,以便后序?qū)的選取。算法第9行,在排好序的序列中,取出移動方向夾角θ最大的3對P作為候選節(jié)點。算法第10行～第13行,對上一步求出的3個節(jié)點對計算ω值,并利用式(4)進行比對,找出相對合適的節(jié)點對,之后算法第14行,將選出P的2個節(jié)點作為下一跳節(jié)點等待消息復(fù)制。

地理策略的算法中主要操作有,第5行～第7行計算節(jié)點組合夾角大小以及第8行對節(jié)點對進行排序,第5行～第7行的操作取決于節(jié)點組合的規(guī)模,所以,時間復(fù)雜度Time(n)=O(n)。對節(jié)點對進行快速排序,所以,時間復(fù)雜度Time(n)=O(nlogn)。地理策略算法的性能主要受節(jié)點組合規(guī)模的影響,因此,時間復(fù)雜度為Time(n)=O(n)。

2 仿真實驗

2.1 仿真環(huán)境

本文采用The ONE(Opportunity Networking Environ-ment)[30]模擬器來進行仿真實驗,基于Random Waypoint節(jié)點移動模型,對HLRA,Epidemic,Spray and Wait和First Contact算法進行了大量的仿真實驗,研究了這些路由算法在節(jié)點緩存空間、消息生成時間間隔、消息生存期產(chǎn)生變化下的路由性能表現(xiàn)。采取的衡量指標有:投遞率、負載率、平均時延和平均跳數(shù)。具體實驗仿真參數(shù)如表2所示。

表2 實驗仿真參數(shù)

2.2 仿真結(jié)果分析

2.2.1 節(jié)點緩存空間大小

圖4是4種算法的路由性能隨著節(jié)點緩存空間大小改變的變化情況。隨著緩存空間逐漸增大,節(jié)點可存儲的消息數(shù)量增加,即可以攜帶更多的消息進行轉(zhuǎn)發(fā),可以降低消息傳輸?shù)奶鴶?shù),增加消息成功投遞的機率。如圖4所示,當緩存空間在25 MB大小時,HLRA算法的消息投遞率比Epidemic提高了10%。平均時延方面,HLRA算法比傳染病算法Epidemic降低了50%,使得消息的時效性得以提高。

圖4 不同緩存空間下4種算法的性能表現(xiàn)

FirstContact算法投遞率最低,因為該算法只轉(zhuǎn)發(fā)一個消息副本,所以對緩存空間的要求并不高,當緩存空間大于10 MB其投遞率開始趨于穩(wěn)定,平均跳數(shù)和平均時延也遠遠多于其他算法,在作為下一跳路由選擇策略時并不理想。但是其網(wǎng)絡(luò)負載率很低,適合應(yīng)用于網(wǎng)絡(luò)資源珍貴,負載率較低的網(wǎng)絡(luò)。

由于HLRA是基于復(fù)制策略的路由算法,通過控制消息副本的數(shù)量來提高消息的投遞率,因此HLRA能達到與Epidemic相當?shù)妮^高的投遞率。在緩存空間增長的情況下,基于復(fù)制的多副本策略能夠有效地提高路由算法的表現(xiàn)。當緩存空間大于16 MB時,HLRA在投遞率方面逐漸高于Epidemic,這驗證了本文兩種策略相結(jié)合下一跳路由選擇算法在提高路由性能上的有效性。HLRA同時具有4個算法中最低的網(wǎng)絡(luò)平均延時,能夠提高消息的可靠性。但是因為HLRA在節(jié)點計算方面要復(fù)雜于其他3個算法,所以在網(wǎng)絡(luò)負載率方面要高于其他3個算法,隨著緩存空間增大,負載率逐漸降低,所以HLRA適用于那些節(jié)點緩存資源不充裕負載能力強的網(wǎng)絡(luò)。Epidemic和SprayAndWait算法都是基于復(fù)制策略的路由算法,后者是在前者的基礎(chǔ)上對消息副本的數(shù)量進行了限制,它們都有一個較高的投遞率,由于SprayAndWait對消息副本進行的限制,因此在緩存空間大于8 MB時,其投遞率開始低于Epidemic。但2個算法的網(wǎng)絡(luò)平均時延都高于HLRA,降低了消息的可靠性。

綜合圖4可以看出,在DTN中,當資源充足和網(wǎng)絡(luò)負載能力較低時,Epidemic和SprayAndWait算法有較高投遞率和較低的網(wǎng)絡(luò)負載率,具有比較高的價值。當網(wǎng)絡(luò)負載能力較強緩存空間不充裕時,HLRA算法是一個更好的選擇,在保持較高的投遞率的同時,具有較低的網(wǎng)絡(luò)平均時延,因而可以發(fā)揮出更高效的路由性能。

2.2.2 消息生成時間間隔

圖5是消息生成時間間隔對4種算法路由性能的影響。由圖5可以看出,在不同的消息生成時間間隔下,相比較于其他3種算法,HLRA在投遞率和平均時延上取得了一定優(yōu)勢。

圖5 不同消息生成時間間隔下4種算法的性能表現(xiàn)

進一步驗證了HLRA2種策略相結(jié)合下一跳路由選擇算法在提高路由性能上的有效性。HLRA在投遞率方面明顯的高于其他3個算法。FirstContact投遞率依然最低。當消息生成時間間隔較小時,網(wǎng)絡(luò)中會快速生成大量的消息,由于沒有對消息副本進行限制并且緩存空間的有限,基于復(fù)制策略的路由算法受到限制,因此HLRA,Epidemic和SprayAndWait在時間間隔小于50 s的時候,投遞率都不高,但隨著消息生成時間間隔逐漸增大,網(wǎng)絡(luò)中的消息增長速度減緩,對緩存資源的快速消耗得以緩解,3個算法的投遞率逐漸增高,由于HLRA通過歷史策略和地理策略對中繼節(jié)點進行篩選,并限制消息的復(fù)制能力,因此HLRA的投遞率明顯高于Epidemic和Spray And Wait算法。平均時延方面,HLRA依然占據(jù)了絕對的優(yōu)勢,擁有最低的平均時延。由于HLRA在節(jié)點計算方面要復(fù)雜于其他3個算法,所以在網(wǎng)絡(luò)負載率方面高于其他3個算法。

2.2.3 消息生存期

圖6、圖7是4種算法的路由性能隨著消息生存期長短的變化情況。

圖7 不同消息生存期下4種算法的性能表現(xiàn)2

由圖6、圖7可以看出,HLRA算法在投遞率和平均時延方面依然保持著優(yōu)勢。當消息生存期小于100 s時,HLRA相比其他3個算法,有一個較高的投遞率,FirstContact算法的投遞率依然很低。在平均時延方面,HLRA依然是明顯的低于其他算法,隨著消息生存期的逐漸增加,變化非常明顯。FirstContact由于只是將消息傳給第一個遇到的節(jié)點,所以平均跳數(shù)非常高,遠遠高于其他3個算法。而HLRA,Epidemic和SprayAndWait算法要較低且相對穩(wěn)定,其中HLRA要略高于Epidemic和SprayAndWait算法。負載率方面,HLRA算法的負載率還是明顯高于其他3個算法。

綜合圖6、圖7可以看出,相比其他3個算法,在消息周期較短時,HLRA算法是一個很好的選擇,因為其投遞率較高且網(wǎng)絡(luò)負載也相對較低。

3 結(jié)束語

本文提出基于歷史和位置信息的容遲網(wǎng)絡(luò)路由算法。利用節(jié)點的歷史相遇信息和位置信息篩選與目的節(jié)點歷史相遇次數(shù)更多的節(jié)點,將與當前節(jié)點移動方向夾角更大的節(jié)點作為下一跳候選節(jié)點進行消息復(fù)制,從一定程度上控制了洪泛策略中的消息盲目復(fù)制,減少了消息的冗余副本數(shù)量,在保持投遞率的基礎(chǔ)上降低了消息傳輸?shù)钠骄鶗r延。仿真結(jié)果表明,該算法平均時延低于Epidemic、FirstContact和Spray and Wait算法,投遞率也得到一定程度的提高。但是該算法網(wǎng)絡(luò)負載較高,因此,下一步將著重解決網(wǎng)絡(luò)負載較高的問題,并進一步提高算法的消息投遞率。

[1] FALL K.A Delay-tolerant network architecture for challenged Internets[C]//Proceedings of Conference on Applications,Technologies,Architectures,and Protocols for Computer Communications.New York,USA:ACM Press,2003,27-34.

[2] FATIMAH A,JOHARI R.Delay tolerant network:routing issues and performance[J].International Journal of Autonomic Computing,2016,2(2):99-113.

[3] MCMAHON A,FARRELL S.Delay and disruption tolerant networking[J].IEEE Internet Computing,2009,13(6):82-87.

[4] RAJ V S,CHEZIAN R M.DELAY-disruption tolerant network (DTN),its network characteristics and core applications[J].International Journal of Computer Science & Mobile Computing,2013,2(9):256-262.

[5] CAO Yue,SUN Zhili.Routing in delay/disruption tolerant networks:a taxonomy,survey and challenges[J].IEEE Communications Surveys & Tutorials,2013,15(2):654-677.

[6] LI Yun,WANG Xiaoying,LIU Zhanjun,et al.Analysis of link interruption characteristics in the DTN[J].Journal on Communications,2008,29(11):232-236.

[7] 胡四泉,汪紅兵,王俊峰.機會型網(wǎng)絡(luò)研究綜述[J].計算機科學(xué),2009,36(10):32-37.

[8] TOVAR A,FRIESEN T,FERENS K,et al.A DTN wireless sensor network for wildlife habitat monitoring[C]//Proceedings of Electrical and Computer Engineering.Washington D.C.,USA:IEEE Press,2010:1-5.

[9] JUANG P,OKI H,WANG Yong,et al.Energy-efficient computing for wildlife tracking:design tradeoffs and early experiences with Zebranet[J].ACM SIGARCH Computer Architecture News,2002,30(5):96-107.

[10] MCKOWN M W,LUKAC M,BORKER A,et al.A wireless acoustic sensor network for monitoring wildlife in remote locations[J].The Journal of the Acoustical Society of America,2012,132(3):2036.

[11] HULL B,BYCHKOVSKY V,ZHANG Yang,et al.CarTel:A distributed mobile sensor computing system[C]//Proceedings of International Conference on Embedded Networked Sensor Systems.New York,USA:ACM Press,2006:125-138.

[12] LI Xu,SHU Wei,LI Minglu,et al.DTN routing in vehicular sensor networks[C]//Proceedings of Global Telecommunications Conference.Washington D.C.,USA:IEEE Press,2008:1-5.

[13] LI Fan,ZHAO Lei,FAN Xiumei,et al.Hybrid Position-based and DTN forwarding for vehicular sensor networks[J].International Journal of Distributed Sensor Networks,2012,8(4):184-195.

[14] SMALL T,HAAS Z J.The shared wireless infostation model:a new ad hoc networking paradigm (or where there is a whale,there is a way)[C]//Proceedings of ACM Interational Symposium on Mobile Ad Hoc NETWORKING and Computing.New York,USA:ACM Press,2003:233-244.

[15] CHO H H,CHEN C Y,SHIH T K,et al.Survey on underwater delay/disruption tolerant wireless sensor network routing[J].IET Wireless Sensor Systems,2014,4(3):112-121.

[16] DEMMER M,FALL K.DTLSR:Delay tolerant routing for developing regions[C]//Proceedings of Workshop on Networked Systems for Developing Regions.New York,USA:ACM Press,2007:1-6.

[17] VAHDAT A,BECKER D.Epidemic routing for partially-connected ad hoc networks[EB/OL].[2010-11-21].https://www.mendeley.com/research-papers/epidemic-routing-partially-connected-ad-hoc-networks/.

[18] DE ABREU C S,SALLES R M.Modeling message diffusion in epidemical DTN[J].Ad Hoc Networks,2014,16(4):197-209.

[19] WU Yahui,SU Deng,HUANG Hongbin.Performance analysis of Hop-limited epidemic routing in DTN with limited forwarding times[J].International Journal of Communication Systems,2015,28(15):2035-2050.

[20] SPYROPOULOS T,PSOUNIS K,RAGHAVENDRA C S.Spray and wait:an efficient routing scheme for intermittently connected mobile networks[C]//Proceedings of ACM SIGCOMM Workshop on Delay-tolerant Networking.New York,USA:ACM Press,2005:252-259.

[21] SPYROPOULOS T,PSOUNIS K,RAGHAENDRA C S.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.Washington D.C.,USA:IEEE Press,2007:79-85.

[22] KIM E H,NAM J C,CHOI J I,et al.Probability-based spray and wait protocol in delay tolerant networks[C]//Proceedings of International Conference on Information Networking.Washington D.C.,USA:IEEE Press,2014:412-416.

[23] LINDGREN A,DORIA A,SCHELEN O.Probabilistic routing in intermittently connected networks[J].ACM Sigmobile Mobile Computing & Communications Review,2003,7(3):19-20.

[24] GRASIC S,DAVIES E,LINDGREN A,et al.The evolution of a DTN routing protocol——ProPHETv2[C]//Proceedings of the 6th ACM Workshop on Challenged Networks.New York,USA:ACM Press,2011:27-30.

[25] GROSSGLAUSER M,TSE D N C.Mobility increases the capacity of ad hoc wireless networks[J].IEEE/ACM Transactions on Networking,2002,10(10):477-486.

[26] JAIN S,FALL K,PATRA R.Routing in a delay tolerant network[C]//Proceedings of ACM SIGCOMM Conference on Applications,Technologies,Architectures,and Protocols for Computer Communication.New York,USA:ACM Press,2004:145-158.

[27] 王 欣.容遲網(wǎng)絡(luò)中基于復(fù)制策略的單播路由算法研究[J].電子設(shè)計工程,2013,21(6):24-26.

[28] 劉期烈,許 猛,李 云,等.基于歷史效用的機會網(wǎng)絡(luò)路由算法[J].計算機應(yīng)用,2013,33(2):361-364.

[29] 關(guān)禮安,汪斌強,朱宣勇.一種基于節(jié)點多可用下一跳的分級收斂算法[J].計算機應(yīng)用研究,2010,27(9):3493-3495.

[30] KER N A,OTT J.The ONE simulator for DTN protocol evaluation[C]//Proceedings of the 2nd International Conference on Simulation Tools and Techniques.Washington D.C.,USA:IEEE Press,2009:55.