DTN中基于節點綜合性能的自適應噴射等待路由算法

崔建群 孫佳悅 常亞楠 余東海 鄔 堯 吳黎兵

1(華中師范大學計算機學院 武漢 430079)

2(武漢大學國家網絡安全學院 武漢 430072)

(jqcui@126.com)

延遲容忍網絡(delay tolerant network, DTN)是一種在源節點和目標節點之間難以形成穩定的端到端連接鏈路、利用節點移動帶來的相遇機會進行通信的自組織網絡[1].正是由于DTN的這種通信特點，其采用“存儲-攜帶-轉發”的路由機制[2]，消息由中間節點攜帶并隨其移動，直至到達目標節點.DTN適用于大傳輸時延、間歇性連接、高誤碼率的極限通信環境，在災難應急[3]、車載網絡[4]、星際網絡[5]、手持設備組網[6]等領域具有廣泛的應用前景，并將成為未來普適計算和泛在網絡的重要接入技術.因此DTN被認為是實現“無處不在的網絡”的一項關鍵技術，具有重要的研究意義.

在DTN路由算法中，SaW(spray and wait)[7]算法能夠在控制消息副本的前提下實現消息的高效投遞.該算法在Spray(噴射)階段采用對稱分配消息副本數，在Wait(等待)階段進行消息的被動傳輸.文獻[7]證明了在獨立同分布的節點移動模型中SaW算法是最優的，但是在大多數情況下并不存在嚴格的獨立同分布移動模型，因此SaW算法仍然有較大的改進空間.

目前對SaW算法的改進主要體現在3個方面：1)在Spray階段篩選中繼節點，根據效用函數選擇高效的候選節點作為下一跳，有利于提高消息投遞率[8]；2)在Spray階段噴射適當比例的副本，根據不同節點的質量和表現，分配不同的副本數量，使副本快速擴散，有效傳遞[9-10]；3)改進Wait階段的傳輸策略[11].然而，目前大多數SaW改進算法只是根據其中的1個或2個方面進行研究，很少考慮將這3個方面綜合起來對SaW進行改進，性能提高并不明顯.

基于以上分析，本文將中繼節點選擇、自適應分配消息副本數量以及Wait階段的改進綜合考慮進來，提出一種基于節點綜合性能的自適應噴射等待路由算法(adaptive spray and wait routing algorithm based on comprehensive performance of node, CPN-ASW).主要貢獻有5個方面：

1) 定義了節點相似度來反映節點運動軌跡的相似程度，利用節點相似度控制消息轉發條件，避免消息在運動軌跡相似的節點間傳輸，網絡開銷增大，投遞率無明顯變化情況的發生.

2) 引入節點活躍度概念來反映節點與其他節點的相遇能力，從而將較多的消息副本分配給活躍度高的節點，使消息能夠在短時間內擴散至較多的節點上.另外，采用劃分等長的時間窗口來更加準確地估計節點活躍度.

3) 結合節點活躍度和剩余緩存，提出節點相對效用值的概念.根據節點間的相對效用值自適應分配消息副本數，給活躍度高、剩余緩存多的節點分配更多的消息副本，使消息在網絡中擴散得更廣，進而提高消息到達目標節點的可能性.

4) 在Spray階段提出基于節點相似度和節點相對效用值的噴射策略，使在副本受限的情況下，消息得到有效擴散.

5) 在Wait階段充分利用節點間的相遇機會，提出基于節點投遞預測值的主動轉發策略，進一步降低傳輸時延.

1 相關工作

目前，在DTN的研究中，路由算法主要分為單拷貝路由協議和多拷貝路由協議.典型的單拷貝路由協議有Direct Delivery[12]和First Contact[12].這2種路由協議網絡開銷小，但是傳輸時延很高，且消息成功到達目標節點的概率很低.多拷貝路由協議中最具代表性路由協議有Epidemic[13]和Prophet[14].Epidemic是一種洪泛式路由算法，攜帶消息的節點向遇到的每一個節點都復制消息，其在網絡資源較充足的條件下投遞率較高，且傳輸時延低，但是在真實的網絡場景中，網絡資源往往受限，其盲目復制會導致網絡開銷巨大，最終降低網絡性能；Prophet算法利用節點間相遇歷史信息和傳遞性定義一個投遞預測值指標來描述節點之間成功傳輸消息的概率，每當2個節點相遇時，選擇到達目標節點投遞預測值更高的節點作為消息中繼節點，但是Prophet本質上仍是消息復制路由，相比Epidemic網絡開銷明顯減小，但由于進行中繼節點篩選，消息到達目標節點時延較大.

為了將Epidemic算法消息投遞的高效性與單副本直接傳輸的簡潔性相結合，相關研究者提出了SaW路由算法.該路由算法由Spray和Wait這2個階段組成，消息產生后，通過初始化消息副本數量來顯示消息轉發次數.SaW算法采用了2種模式，即Binary和非Binary模式.Binary模式下，在Spray階段，攜帶某消息副本數大于1的節點向遇到的未緩存該消息的節點轉發此消息一半副本，自身保留剩下的消息副本；當節點中某消息副本數為1時，節點轉入Wait階段，消息以Direct Delivery的方式進行傳輸，即攜帶消息的節點直至遇到目標節點才將消息轉發出去.Binary SaW可應用于多類場景中，其綜合性能要高于Epidemic和Prophet.該算法適用于節點均等分布、運動隨機的延遲容忍網絡，然而在真實的網絡環境中，節點運動不完全隨機，且節點將消息傳輸到目標節點的能力是不同的，因此，SaW算法在Spray階段的對稱分配副本數是不靈活的，并且在Wait階段的被動傳輸會進一步增加傳輸時延.針對SaW算法的主要弊端，目前國內外研究者已在SaW的改進上取得了一些成果.

文獻[8]對Prophet算法中定義的投遞預測值做了進一步改進，節點間的投遞預測值不僅考慮相遇次數，還結合了節點間的連接時間.在Spray階段根據消息到目標節點的投遞預測值篩選中繼節點，Wait階段同樣執行此操作，直至消息到達目標節點.文獻[9]結合節點的投遞預測值和節點相似度作為節點效用值，按照此效用值自適應分配副本數.文獻[10]提出基于節點歷史相遇信息的路由算法EBR，該算法直接根據節點活躍度自適應地分配消息副本數，將更多的消息副本分配給活躍度更高的節點.文獻[15]提出一種基于節點社會性的噴霧等待路由協議BSW-SN，該算法在Spray階段根據節點的移動模式和節點對消息的轉發效能來優化對中繼節點的選擇，然后按照節點的活躍度自適應分配消息副本數.文獻[16]提出一種基于節點質量度的路由算法QoN-ASW，在Spray階段考慮節點的質量度作為消息副本分配的依據；在Wait階段將消息轉發給到目標節點投遞預測值更高的中繼節點，從而減少消息傳輸時延.文獻[17]提出基于相遇概率的噴射等待路由算法PBSW，在Spray階段選擇與目標節點相遇概率更高的相遇節點作為中繼節點，然后根據兩者與目標節點的相遇概率分配適當比例的消息副本.然而，上述文獻只是從篩選中繼節點、靈活分配消息副本數、改進Wait階段傳輸策略中的1個或2個方面進行改進，從而改進策略不夠全面.

基于以上分析，本文綜合考慮中繼節點選擇、自適應分配消息副本數量、改進Wait階段傳輸策略這3個方面，提出一種基于節點綜合性能的自適應噴射等待路由算法CPN-ASW.該算法在Spray階段根據節點間的相似程度是否超過給定閾值而采用不同的中繼節點選擇策略，考慮相遇節點間的活躍度和剩余緩存作為節點的相對效用值，當節點間的相似程度小于給定閾值，直接根據節點的相對效用值自適應地分配消息副本數，否則，選擇合適的中繼節點后再根據節點相對效用值分配消息副本數；進一步為充分利用節點間的相遇機會，在Wait階段將副本數為1的消息轉發給到目標節點投遞預測值更高的中繼節點.

2 問題模型

2.1 網絡模型

假設網絡中包含n個節點，G=(V,E)為網絡拓撲圖，V={vi|1≤i≤n}表示網絡中的節點集合，E為定義在G上的邊集，代表節點對之間的連接.每個節點vi維護一個歷史相遇節點集合Ei={vj|ni,j≠0}，該集合記錄從仿真開始節點vi遇到過的每個節點.當節點vi和vj進入到彼此的通信范圍內，vi檢測Ei中是否包含節點vj，若節點vj不包含在Ei中，則節點vi將vj添加到Ei中，并且將Ei中的ni,j值加1；若節點已包含在Ei中，說明兩節點曾經相遇過，此時只將Ei中的ni,j加1.

2.2 節點相似度

我們在大多數的DTN應用場景中，具有通信功能的移動設備大多是由人類隨身攜帶的，人類的移動模式不是完全隨機的，他們會表現出一定的社會特征.例如，如果2個人擁有1個或者多個共同的朋友，那么這2個人成為熟人的可能性很高，這種現象稱為“聚類”，即這2個人的運動軌跡相似.如果消息在運動軌跡相似的節點間轉發，那么在增大網絡開銷的同時，對提高投遞率并沒有實質性的幫助.因此，在本文中提出節點相似度的概念來表示節點間運動軌跡的相似程度，如果2個節點間的相似度高，則需提高消息轉發條件，進而減少不必要的轉發次數.

定義1.節點相似度.節點vi與節點vj間的相似度是指節點vi和節點vj的歷史相遇節點集合中擁有的共同歷史相遇節點的個數與這2個節點中較大歷史相遇節點集合中節點個數的比值，記為SD(i,j)，其表示為

(1)

如果SD(i,j)越大，即節點間的相似度越高，意味著節點vi和節點vj的運動范圍和接觸節點越相似.

2.3 節點活躍度

在DTN中，活躍的節點能夠快速傳遞消息，使消息在較短的時間內擴散至較多的節點上，從而提高投遞率，降低傳輸時延.然而，DTN中網絡拓撲結構頻繁變化，節點相遇其他節點的能力在較長的仿真時間內可能波動比較大，因此，本文中通過劃分等長的時間窗口來更加準確估計節點活躍度，每當1個時間窗口到期，就更新節點活躍度.節點活躍度反映了節點向網絡中擴散消息的能力.

假設節點vi當前運動時刻位于第k+1個時間窗口內，在第k+1個時間窗口內相遇節點的數量是未知的，本文通過歷史k個時間窗口算出的活躍度估計vi在當前時間窗口內的活躍度.

(2)

2.4 節點相對效用值

為了使CPN-ASW的Spray階段副本分配更具有合理性，本文根據節點間的相對效用值對副本進行分配.節點的活躍度越高，則未來遇到目標節點的可能性越大，則給活躍度高的節點分配更多的消息副本，這會造成活躍度高的節點易發生緩存溢出的情況，造成消息丟包次數較多，反而沒有體現出活躍度高的節點能使消息在網絡中快速擴散的優勢.為了緩解活躍度高的節點上的擁塞程度，則同時將節點剩余緩存作為消息副本分配的依據，如果節點很活躍，但是剩余緩存已不足，則避免將較多的消息副本分配給此節點，防止節點頻繁擁塞導致消息丟包次數明顯增加，從而使較多的消息副本不能被有效傳遞.因此本文綜合利用節點的活躍度和剩余緩存，來體現節點相對效用值的高低.節點的活躍度越高，剩余緩存越多，其相對效用值越高,得到的轉發該消息的次數越多.

定義3.節點相對效用值.當節點vi和節點vj在第k+1個時間窗口內相遇時，節點vi的相對效用值記為Ui，其計算為

(3)

2.5 節點投遞預測值

在DTN中，節點運動并非完全隨機.如果節點vi和vj在過去的時間內接觸比較頻繁，那么未來它們的相遇概率也會比較高.Prophet路由算法正是基于歷史預測策略的代表.該算法利用節點間的相遇歷史信息和傳遞性來定義投遞預測值(delivery probability)，利用投遞預測值來描述節點間的相遇概率.當節點vi和vj相遇時，只有vj到消息目標節點的投遞預測值更高時，vi才將消息傳輸給vj，通過這種有選擇地復制消息副本，有效地降低網絡開銷.

假如用P(i,j)來表示節點和節點間的投遞預測值，P(i,j)的計算分為3個過程：更新、衰減和傳遞性.

1) 更新.當節點vi和vj相遇并建立連接時，更新投遞預測值：

P(i,j)=P(i,j) old+(1-P(i,j) old)×Pinit,

(4)

其中，P(i,j)表示節點vi和vj間的歷史投遞預測值，Pinit∈[0,1]是初始化常量.

2) 衰減.當節點vi和vj在一段時間內沒有遇到彼此，對投遞預測值進行衰減：

P(i,j)=P(i,j) old×yc,

(5)

其中，y表示衰減因子，c表示節點vi和vj從上次相遇到目前為止所經歷的時間塊的個數.

3) 傳遞性.節點投遞預測值也具有傳遞性，根據觀察，如果節點vi經常遇到節點vj，而節點vj經常遇到節點vh，那么對目標節點為節點vi的消息而言，節點vh可能是一個很好的中繼節點.這種傳遞性如何投遞預測值P(i,h)：

P(i,h)=P(i,h) old+(1-P(i,h) old)×
P(i,j)×P(j,h)×β.

(6)

3 CPN-ASW路由算法

基于節點綜合性能的自適應噴射等待路由算法CPN-ASW分為Spray和Wait這2個階段.在Spray階段，提出基于節點相似度和節點相對效用值的噴射策略；在Wait階段，提出基于節點投遞預測值的主動轉發策略.

3.1 Spray階段

在真實的DTN應用場景中，大量的移動設備通過人來攜帶，人的行為具有很強的社會性.例如，擁有相同興趣愛好的人通常會聚集在一起，即這些人的運動軌跡相似.在副本受限的情況下，應提高消息在相似度高的節點間的轉發條件，避免網絡開銷增大，投遞率卻無明顯提高情況的出現.另外，不同種類的節點緩存、移動速度不盡相同，因此承擔消息轉發任務的能力也有高低.在本文中通過定義節點相對效用值來描述節點轉發消息的能力，給相對效用值高的節點分配更多的消息副本，有利于消息得到有效擴散.

基于以上分析，本節提出一種基于節點相似度和節點相對效用值的噴射策略.根據節點相似度是否超過閾值采用不同的中繼節點選擇策略，確定好中繼節點后，按照節點相對效用值分配消息副本數量.具體噴射策略如下.

當節點vi和節點vj相遇時，若節點vj不攜帶vi持有消息ml，節點vi向節點vj分配消息ml副本數量的步驟為：

1) 判斷節點vj是否是目標節點，若是，則節點vi直接將消息的一個副本傳遞給vj，同時刪除該消息;否則，執行步驟2)或步驟3).

2) 若節點間的相似度SD(i,j)≥τ,說明這2個節點相遇節點集合高度重疊，此時為減少消息在運動范圍大致重疊且相對效用值相差不大的節點間的轉發次數，若滿足：

Uj>Ui+Uth×SD(i,j),

(7)

則節點vi確定節點vj為中繼節點；否則，vi等待與目標節點或其他節點相遇.其中，τ為相似度閾值，Uth為效用參數.

若轉發條件滿足式(7)，根據節點vi和節點vj的相對效用值按比例分配消息副本數，設節點vi中的消息ml副本數為Li old(ml)，分配給節點vj的消息副本數Ljnew(ml)為

(8)

節點vi自身保留消息ml副本數Li new(ml)為

Li new(ml)=Li old(ml)-Lj new(ml).

(9)

3) 若節點間的相似度SD(i,j)<τ，說明這2個節點的運動范圍相似性較小，此時為了消息的傳播范圍更廣，直接按照節點相對效用值在節點間按比例分配消息副本數，分配給vj的消息ml副本數Ljnew(ml)如式(8)所示，節點vi剩余消息ml副本數Li new(ml)如式(9)所示.

當節點vi和節點vj相遇，vi向vj分配消息副本過程如算法1所示：

算法1.Spray階段算法.

輸入：節點vi和節點vj相遇；

輸出：vi即將發送給vj的副本數大于1的消息集合MforwardList.

② 根據式(1)更新SD(i,j)；

③ 根據式(3)計算Ui,Uj；

④ FOR ?ml∈viandml?vj

⑤ IFLi old(ml)>1 THEN

⑥vd=ml.destination；

⑦ IFvd==vjTHEN

⑧ 節點vi將消息ml轉發給vj；

⑨ 節點vi刪除消息ml；

⑩ continue；

算法1中，行⑦～⑩表示當相遇節點vj是消息目標節點時，直接將消息轉發給vj并刪除節點vi中此消息；行～表示當節點vi和節點vj相似度大于閾值時，篩選合適中繼節點后再按照節點相對效用值計算分配消息副本數；行～表示vi和vj的相似度未超過閾值，直接按照節點相對效用值計算在節點間分配消息副本數；行～表示將符合條件的消息添加到MforwardList中；行～表示按照消息剩余生存時間從大到小的順序將MforwardList中消息轉發給vj.

假設網絡中的消息總數為M，在算法1中，主要時間消耗在行④～，時間復雜度為O(M)，因此，該算法的時間復雜度為O(M).

3.2 Wait階段

在傳統的SaW路由算法中，當節點所攜帶的某個消息的副本數為1時，進入到Wait階段，該階段存在弊端：節點攜帶消息直到遇到目標節點才將消息轉發出去，沒有充分利用節點間的相遇機會.

基于上述分析，本節提出基于節點投遞預測值的主動轉發策略.在Wait階段利用Prophet路由算法中的投遞預測值來描述節點間成功傳輸消息的概率，當節點vi中持有相遇節點vj中沒有的消息時，以相遇節點vj的緩存占用比來調節閾值大小，只有節點vj到消息目標節點的投遞預測值大于節點vi到消息目標節點的投遞預測值，并且兩者到消息目標節點的投遞預測值區分度大于給定閾值時，節點vi才將消息ml轉發給相遇節點vj.

當節點vi中的消息ml只剩下一個消息副本時，與未緩存消息ml的節點vj相遇，若滿足：

P(j,d)>P(i,d)+Pth×OBj,

(10)

則節點vi將該消息轉發給節點vj.其中，P(i,d)和P(j,d)分別表示節點vi和節點vj將消息ml成功投遞到目標節點vd的概率;Pth∈[0,1]為預設參數;OBj為相遇節點vj的緩存占用率.在轉發過程中通過利用相遇節點vj的緩存占用比來調節節點間的投遞預測值區分度，一方面避免消息在投遞概率近似的節點間轉發，另一方面隨著相遇節點vj的緩存占用率不斷增大，轉發條件越來越高，從而降低網絡開銷，較大程度上避免了擁塞情況的出現.

在Wait階段，節點vi和節點vj相遇時，節點vi執行的消息轉發過程如算法2所示：

算法2.Wait階段算法.

輸入：節點vi和節點vj相遇；

輸出：vi即將發送給vj的副本數為1的消息集合SforwardList.

① 根據式(4)更新P(i,j)；

② 節點間相互交換變量OBi,OBj；

③ FOR ?ml∈viandml?vj

④ IFLi old(ml)==1 THEN

⑤vd=ml.destination；

⑥ IFvd==vjTHEN

⑦ 節點vi將消息ml轉發給vj；

⑧ 節點vi刪除消息ml；

⑨ continue；

⑩ ELSE IFP(j,d)>P(i,d)+Pth×OBj

THEN

算法2中，行⑥～⑨表示當節點vj是消息目標節點時，直接將消息轉發給vj并刪除節點vi中此消息；行⑩～表示當節點vj不是消息目標節點時，只有滿足式(10)才將消息轉發給vj，同時vi刪除此消息；行～表示按照消息剩余生存時間從大到小的順序將SforwardList中消息轉發給vj.

4 仿真結果與分析

4.1 仿真環境配置

實驗采用ONE[18]仿真平臺，將CPN-ASW與Epidemic，SaW，EBR，PBSW在相同實驗環境下進行對比.仿真采用ONE自帶的赫爾辛基市地圖作為移動場景，大小為4 500 m×3 400 m，節點數量設置為126個，共分為3類節點：行人、出租車、有軌電車.其中行人組80個節點，出租車組40個節點，這2組按照基于地圖路線的最短路徑模型移動，有軌電車組共6個節點，按照基于地圖的固定路線模型移動.具體的仿真參數設置如表1所示，其他參數采用ONE平臺自帶的默認設置.對于初始常量Pinit、傳遞因子β、衰減參數y這3個參數設置可參考文獻[14]中設定的值，取Pinit=0.75,β=0.25,y=0.98.

Table 1 Simulation Parameters表1 仿真參數

4.2 評價指標

1) 投遞率

投遞率=成功投遞到目標節點的消息數量/網絡中源節點產生的消息數量.

2) 平均時延

平均時延=網絡中所有被成功投遞的消息從源節點產生開始到目標節點完整接收到所經過的平均時間.

3) 網絡開銷

網絡開銷.冗余的中繼轉發次數/成功投遞到目標節點的消息數量.

4) 平均跳數

平均跳數.網絡中所有被成功投遞的消息從源節點產生開始到目標節點完整接收到所經過的平均跳數.

4.3 參數設置實驗

4.3.1 活躍度平滑因子α設置

α的取值對CPN-ASW算法的實驗效果影響較大，在表1參數設置條件下更改α取值，綜合考慮投遞率和平均時延，α=0.8時實驗效果最佳.如圖1所示:

Fig. 1 Performance comparison of CPN-ASW under different α圖1 CPN-ASW在α不同取值下的性能比較

從圖1(a)中可以觀察到，α=0.6時投遞率最高，根據Markov預測法[19]，任何事件可通過其目前的狀況來預測該事件將來各個時刻(或時期)的變動狀況.由此可知近期活躍度高的節點在未來一段時間內也將延續較高的活躍性.當α取值偏重于最近1個完整時間窗口活躍度時，更能準確預測節點在未來一段時間的活躍度.但是同時觀察圖1(b)，α=0.6時投遞率最高，此時平均時延也最高.所以綜合考慮投遞率和平均時延，α=0.8時投遞率比α=0.6時要略低，但平均時延有了明顯的改善，所以本文中α=0.8時實驗效果最佳.

4.3.2 相對效用值參數w設置

w的取值直接影響消息副本分配數量的合理性，本文通過在w不同取值下的投遞率變化，得出w=0.3時投遞率最高，如圖2所示:

Fig. 2 Delivery ratio of CPN-ASW under different w圖2 CPN-ASW在w不同取值下的消息投遞率比較

4.4 算法比較及分析

為了驗證CPN-ASW算法的高效性，進行了2組仿真實驗，在不同的消息生存周期(TTL)、不同的節點緩存大小下對這5種算法在消息投遞率、平均時延、網絡開銷、平均跳數這4個方面進行評估.實驗結果表明CPN-ASW在提高消息投遞率、控制網絡開銷、降低平均時延方面效果顯著.

1) 不同消息生存周期

在4.1節的環境配置下，改變消息生存周期，對比各種算法在不同消息生存周期下消息投遞率(如圖3所示)、平均時延(如圖4所示)、網絡開銷(如圖5所示)、平均跳數(如圖6所示)這4個方面的變化情況.

Fig. 3 Delivery ratio under different TTL圖3 不同消息生存周期下的投遞率

圖3顯示了各種算法在不同消息生存周期下消息投遞率的變化情況.其中CPN-ASW算法的投遞率最高，相比Epidemic平均提高了58.55%，相比SaW平均提高了3.60%，相比EBR平均提高了1.20%，相比PBSW平均提高了11.22%.這主要歸結于2個原因：1)CPN-ASW算法在Spray階段根據節點間相似程度是否超過閾值而采用不同的中繼節點選擇策略，并根據節點間相對效用值實現自適應分配消息副本數，避免消息的盲目轉發；2)在Wait階段實現消息主動轉發，選擇到目標節點投遞預測值更高的中繼節點進行轉發.同時從實驗結果可以看出，Epidemic算法的投遞率遠低于其他算法，并且曲線呈現下降趨勢，這是因為此算法沒有限制消息副本的最大拷貝數，隨著消息生存周期的增加，消息在有限緩存中駐留時間更長，盲目洪泛易導致網絡中擠壓大量消息副本，引起網絡擁塞，消息投遞率反而下降.

圖4評估了各個算法平均時延的變化情況.5種算法的平均時延隨著消息生存周期的增加大體上呈現增長態勢，因為增加生存周期使原來在短時間內不能到達目標節點的消息能被成功投遞.其中CPN-ASW的平均時延最小，相比SaW下降了4.44%，相比EBR下降2.08%，相比PBSW下降9.67%.這主要是因為CPN-ASW算法在Wait階段實現了消息主動轉發，選擇更優的中繼節點進行傳輸，加快了消息到達目標節點的速度.Epidemic算法采用洪泛機制，過多的復制消息容易使網絡陷入擁塞，故平均時延相比其他算法來說是最大的.

Fig. 4 Average delay under different TTL圖4 不同消息生存周期下的平均時延

圖5比較各個路由算法的網絡開銷.由于SaW，EBR，PBSW，CPN-ASW均在一開始限制了消息副本拷貝數，也就是限制了轉發次數，故網絡開銷遠低于Epidemic算法.CPN-ASW算法網絡開銷相對SaW平均下降17.71%，這是因為相對SaW算法在Spray階段盲目轉發，CPN-ASW算法在Spray階段避免消息在運動范圍相似的節點間轉發，在一定程度上減少了不必要的中繼轉發次數，在Wait階段自適應控制轉發條件，最終網絡開銷較小.從圖5中還可看出，PBSW算法的網絡開銷最小，其原因主要體現在2個方面：1)Spray階段只將消息轉發給與目的節點相遇概率更高的節點，從而消息轉發次數受到限制；2)在Wait階段沒有任何優化策略，直到與目的節點相遇時才將消息轉發出去，不存在冗余的中繼轉發次數.

Fig. 5 Overhead ratio under different TTL圖5 不同消息生存周期下的網絡開銷

圖6比較了各個算法的平均跳數.其中CPN-ASW相對SaW平均跳數下降4.22%，主要原因在于CPN-ASW在Spray階段當節點間運動范圍高度相似時選擇更優的中繼節點分配消息副本數，在Wait階段雖然進行主動轉發，但是自適應控制轉發條件，最終平均跳數還是明顯低于SaW.其中PBSW的平均跳數最低，有2個原因：1)Spray階段對中繼節點的選擇更為苛刻，只給到目的節點投遞預測值更高的中繼節點分配消息副本；2)Wait階段被動等待，直到遇到目的節點才進行消息投遞.

Fig. 6 Average hop under different TTL圖6 不同消息生存周期下的平均跳數

總體來看，在不同的消息生存周期下，CPN-ASW相比其他4種算法均表現出較高的投遞率和較低的平均時延.并且在網絡開銷和平均跳數方面較SaW也表現出明顯的優勢.PBSW算法雖然在網絡開銷和平均跳數方面表現最優，但是相對于其他3種限制消息副本數的算法(SaW，EBR，CPN-ASW)來說，投遞率和平均時延方面均表現出明顯的劣勢.另外也可看出，Epidemic算法性能最差，說明在資源受限的真實場景中，洪泛式的轉發算法并不能取得良好的效果.

2) 不同節點緩存大小

在不同節點緩存大小下，比較和分析各個算法在消息投遞率(如圖7所示)、平均時延(如圖8所示)、網絡開銷(如圖9所示)、平均跳數(如圖10所示)這4個方面的變化情況.

圖7顯示了各個算法在不同節點緩存下消息投遞率的變化情況.5種算法的投遞率都隨著節點緩存的增加而提高，這是因為節點緩存越大，其所能攜帶的消息數量也越多，由于網絡擁塞導致的丟包情況會逐漸緩解，其中CPN-ASW算法的投遞率最高，相比Epidemic平均提高了67.07%，相比SaW平均提高了5.28%，相比EBR平均提高了2.55%，相比PBSW平均提高了9.12%.

Fig. 7 Delivery ratio under different buffer sizes圖7 不同緩存大小下的投遞率

圖8比較了各個算法的平均時延.CPN-ASW的平均時延相比PBSW平均下降10.26%.從圖8中還可觀察到，在節點緩存小于12 MB時，CPN-ASW的平均時延略大于SaW；當節點緩存超過12 MB，CPN-ASW的平均時延開始小于SaW的時延.這是由于CPN-ASW在Spray階段是按照節點間的相對效用值分配消息副本數，相對效用值綜合考慮節點活躍度和節點剩余緩存，當節點緩存本身較小時，節點的緩存利用率一直都很高，相對效用值中活躍度因素的重要性更為突出，活躍度高的節點易形成擁塞，消息丟包次數變多，需要經過更多的轉發次數才能到達目標節點，傳輸時延較大；隨著節點緩存的增加，活躍度高的節點上擁塞情況得到緩解，再加上CPN-ASW在Wait階段選擇更優的中繼節點進行轉發，最終CPN-ASW在平均時延方面的優越性得到體現.

Fig. 8 Average delay under different buffer sizes圖8 不同緩存大小下的平均時延

Fig. 9 Overhead ratio under different buffer sizes圖9 不同緩存大小下的網絡開銷

圖9顯示的是網絡開銷隨節點緩存的變化情況.當節點緩存逐漸增加，5種算法的網絡開銷都逐漸下降，這是因為緩存空間越小，節點就越有可能因為緩存占滿采用消息丟棄策略，使消息經過較多的轉發次數才能到達目標節點.其中CPN-ASW的網絡開銷較Epidemic平均下降了69.55%，較SaW平均下降了17.99%.此外，通過觀察圖9可知，Epidemic算法的網絡開銷隨著緩存的增加而急速下降，這表明此算法適用于資源充足的網絡，在緩存較充足時能有效降低網絡開銷，發揮出較好的效果.

圖10比較各個算法的平均跳數.其中PBSW的平均跳數最低，CPN-ASW平均跳數和EBR算法大致相同，CPN-ASW的平均跳數相對Epidemic平均下降了17.36%，相對SaW平均下降了2.50%.這說明了CPN-ASW算法采用的中繼節點選擇的合理性.

Fig. 10 Average hop under different buffer sizes圖10 不同緩存大小下的平均跳數

總體來看，在5種算法中，在不同節點緩存大小下，CPN-ASW算法消息投遞率最高，當緩存較充足時平均時延最小，且在網絡開銷和平均跳數方面也表現優越且穩定.

5 結束語

本文針對DTN長時延、間歇性連接等特點，提出一種基于節點綜合性能的噴射等待路由算法CPN-ASW.該算法在Spray階段根據節點間相似度是否超過給定閾值采用不同中繼節點選擇策略，并按照節點相對效用值自適應分配消息副本數；在Wait階段將消息轉發給到目標節點投遞預測值更高的中繼節點.由對比算法分析得出，本文提出算法能夠有效提高消息投遞率，控制網絡開銷和降低平均時延.

然而，從實驗中也可觀察到，CPN-ASW算法相對于傳統SaW來說，在節點緩存較小時平均時延較高.為進一步降低平均時延，設置一種有效的緩存管理策略是下一步研究工作的重點.

作者貢獻聲明：崔建群負責提出研究選題、優化論文；孫佳悅負責設計算法、設計實驗并開展實驗分析；常亞楠負責設計論文框架；余東海、鄔堯負責調研整理文獻、協助論文實驗；吳黎兵負責提出指導意見并修改論文.