一種基於資源受限條件下的自適應DTN路由算法的製作方法

2023-07-01 22:17:26 1

一、技術領域

本發明涉及容遲網絡技術領域，尤其涉及一種基於資源受限條件下的自適應dtn路由算法。

二、

背景技術：

隨著信息技術的發展，internet網絡的出現極大改變了人類社會的生產生活方式。internet網絡節點始終保持著端到端連接路徑，且丟包率小、傳輸時延低。這類網絡是以tcp/ip協議簇作為基礎的，適用於大部分的網絡環境。然而，隨著信息技術的不斷深入發展，常常需要在一些極端環境中部署網絡。由此出現了眾多不同於傳統網絡特徵的場景。這些網絡具有連結頻繁中斷、傳輸時延高、丟包率高、上行和下行數據率不對稱等特點。例如，在衛星通信中，由於經濟和技術方面的原因導致網絡節點數量較少，且衛星時常移動，導致衛星通信網絡連接時常中斷；海洋、湖泊、山川等極端環境下為了節約節點能量消耗，在節點不工作時，採取待機或者關閉措施，造成網絡連接中斷。

具有上述連接時常中斷、傳輸時延高等特點的網絡稱為容遲容斷網絡(delaytolerantnetwork,dtn)。這類網絡特點使得傳統的基於tpc/ip協議簇的路由算法不再適用。dtn網絡傳遞信息採用的是「存儲-攜帶-轉發」的模式。路由算法作為信息傳遞的關鍵，隨著dtn網絡應用場景越來越多，各類dtn路由算法被相繼提出。

基於網絡拓撲是否先驗，可將路由算法分為確定性路由算法和隨機路由算法。確定性路由假設網絡拓撲在進行數據傳輸之前就已經確定。隨機路由算法適用於網絡拓撲未知的場景。此類算法通常基於網絡動態拓撲傳遞數據，並且記錄各節點參量選擇下一跳。

根據路由算法制定路由規則依賴的指標不同，可以將dtn路由算法分為基於社交屬性的路由算法和非基於社交屬性的路由算法。基於社交屬性路由算法又可分為基於積極社交屬性和基於消極社交屬性。積極社交屬性主要指網絡的中心度、相關度、度分布等指標，消極社交屬性主要指網絡中節點「自私」程度，即有些節點可能由於能耗、隱私等原因不願作為中繼節點傳輸數據。典型的基於積極社交屬性的路由算法包括multi-simbet,bubblerap,levelrouting等算法；基於消極社交屬性的路由算法包括tit-for-tat,smart,mobicent等算法。

根據算法優先於哪個服務指標又可將路由算法分為flood-based,historyandencounter-based,socialbehavior-based,knowledge-based等。其中flood-based算法以泛洪為基礎思想，傳輸成功率較高，典型的flood-based算法有epidemicrouting,sprayandwait,rapid，multi-simbet算法等；historyandencounter-based算法以相遇概率推算為基礎思想，性能開銷較小，典型的historyandencounter-based算法有prophet,singlerecent,sprayandfocus算法等；socialbehavior-based算法類似於前文提到的基於社交屬性的算法，主要通過計算節點社交屬性選擇下一跳，成功率較高，典型的socialbehavior-based算法有bubble-rap,simbet等算法；knowledge-based算法則與前文提到的確定性路由算法相似，適用於網絡拓撲先驗的場景。

根據算法路由策略可以將dtn路由算法分為泛洪路由算法和轉發路由算法。泛洪路由算法允許網絡中包含多個信息副本以便提高網絡傳輸成功率，適用於網絡資源較為豐富的場景，典型的泛洪路由算法有epidemic,sprayandwait,sprayandfocus,multi-simbet等；轉發路由算法則只允許同一時刻網絡中最多存在信息的一個副本，此類算法成功率不如泛洪路由算法，但適用於資源緊缺的場景。典型的轉發路由算法有singlerecent,directtransmission,onehopencounterprediction算法。

三、

技術實現要素：

本發明的目的是，針對上述各類典型dtn路由算法存在的優缺點，提出一種基於資源受限條件下的自適應dtn路由算法。該算法能夠根據網絡實時資源負載消耗情況選擇合適的典型dtn路由算法。旨在提高網絡吞吐量，達到提高傳輸成功率的同時降低平均時延的效果。

本發明的技術方案是：一種基於資源受限條件下的自適應dtn(容遲容斷網絡)路由算法即基於節點負載的自適應路由算法，合理利用泛洪路由算法傳輸成功率高、轉發路由算法資源消耗低的優點，根據節點當前負載選擇適用的路由算法。算法分為兩個階段：訓練階段和傳輸階段。

1)訓練階段，主要任務為根據所選擇的路由算法確定節點負載和網絡負載計算參數，並確定各個算法適用的負載區間；

2)傳輸階段，主要任務為對未過期的數據根據訓練階段定義的節點負載計算公式計算得到節點負載，判斷節點負載所在的負載區間及負載區間對應的路由算法。然後根據這個路由算法進行路由。同時根據這一跳路由情況更新訓練階段定義的節點負載計算所需參數，以及對應負載區間的更新。

通過對路由算法的靈活選擇，達到提高網絡傳輸成功率和降低資源消耗的目的。

如附圖1所示，訓練階段1)過程具體為：

步驟1.1：根據實際應用場景選取幾個典型的dtn路由算法，需要包含轉發路由算法和泛洪路由算法；

步驟1.2：根據網絡情況按照選取的典型路由算法分別進行路由傳輸，並統計這段時間算法的傳輸成功率、網絡平均時延、網絡平均路由資源消耗、性能資源消耗比隨著時間的變化情況。同時統計路由傳輸過程中每個節點接收到的消息總數按照消息來源上次與當前節點接觸時間差的分布情況；

步驟1.3：定義並計算每個節點負載情況以及網絡平均負載；

步驟1.4：根據步驟1.3計算得到的負載情況確定各個典型路由算法適用的負載區間；

如附圖2所示，傳輸階段2)具體為：

步驟2.1：當前節點向目的節點發送消息；

步驟2.2：判斷消息是否已經過期，如果過期則直接廢棄消息；

步驟2.3：查看當前節點所有鄰居，首先驗證鄰居節點中是否有目的節點，如果有，則直接將消息傳送到目的節點；

步驟2.4：對於當前節點的每個鄰居，根據步驟1.3定義的公式計算每個鄰居的節點負載情況；

步驟2.5：判斷各個鄰居節點適用於哪種典型路由算法，並用此算法進行路由；

步驟2.6：更新步驟1.3節點負載計算公式中的參數以及步驟1.4各個路由算法使用的負載區間；返回步驟2.1。

以上步驟只表述一個數據在網絡中的傳輸情況。多個數據的情況類似。

網絡傳輸成功率計算如下：

其中，n代表網絡中總傳輸數據數量，當信息mk最終成功傳輸時dk＝1，否則dk＝0。

網絡平均時延計算如下：

其中，n代表網絡中成功傳輸的消息數量，receivetimek以及createtimek代表消息k產生和最終成功傳輸的時間。

網絡傳輸資源消耗計算如下：

其中，n代表網絡傳輸過程中產生的所有消息數量，ck指消息mk在網絡中副本個數。網絡平均路由資源消耗代表每傳遞一份消息，需要伴隨多少消息副本散布在網絡中。

性能消耗比計算如下：

其中，deliveryratio指網絡傳輸成功率；averageoverhead指網絡傳輸資源消耗。

路由傳輸過程中每個節點接收到的消息總數按照消息來源上次與當前節點接觸時間差的分布情況具體計算方式如下：

對於每個鄰居節點，當要接收當前節點傳來的消息時，記錄下這個鄰居節點與當前節點上次相遇時間與當前時間的差值。最後統計整個網絡傳輸過程中，消息接收過程中接收消息總量隨著相鄰節點上次相遇時間差的分布情況。進行這項統計是為了後續計算節點負載的權重。

節點負載情況計算如下：

其中，指節點i的平均負載情況，ηi指節點i當前需要處理的消息總數，li指節點i的緩存大小，這是根據網絡實際情況確定的。βj指節點j當前負載情況權重大小，是節點i與節點j上次相遇時間差的函數。t指當前時間，tij指節點i與節點j上次相遇時間。q是根據消息總量對數隨相遇時間差分布進行線性回歸得到的衰減因子。

衰減因子q計算如下：

按照每個節點接收到的消息總數按照消息來源上次與當前節點接觸時間差的分布情況能夠得到如下幾個公式：

z＝k(t-tij)+b

z＝lny

其中y指接收消息數量，t指當前時間，tij指節點i與節點j上次相遇時間。k與b是按照線性回歸方程計算得到的。

整理上面兩個公式可以得到如下關係：

q＝ek

網絡負載按照如下公式進行計算：

其中，n是網絡中節點數量，指節點i的平均負載情況。

在路由傳輸過程中，每過一個時間間隔，按照上式計算網絡負載。

各個典型算法適用的負載區間計算如下：

步驟1：根據網絡負載隨時間分布以及傳輸成功率隨時間分布的數據，得到各個路由算法傳輸成功率差分隨網絡負載變化的數據；

步驟2：對於每一個網絡負載，根據步驟1得到的數據，存在一個算法在這個負載下對成功率增長變化最大。自適應算法在這個負載下將選擇此算法進行路由；

步驟3：總結步驟2得到的每個網絡負載對應選擇的路由算法，得到每個路由算法適用的負載區間。

傳輸階段更新權重大小主要是重新統計接收消息數量隨著相遇時間差分布情況，同時更新衰減因子q進而更新網絡權重，最後達到更新算法適用區間的目的。

本發明的有益效果，本發明自適應算法能夠通過少量的訓練自適應的根據網絡當前負載情況合理選擇路由算法進行數據傳輸。能夠根據當前網絡環境選擇成功率最高的路由算法進行路由，同時避免網絡由於過度泛洪而發生擁塞。進而降低網絡資源消耗。

四、附圖說明

圖1是訓練階段算法流程圖

圖2是傳輸階段算法流程圖

圖3是自適應算法和典型路由算法傳輸成功率對比

圖4是自適應算法和典型路由算法平均路由資源消耗對比

圖5是路由傳輸過程中每個節點接收到的消息總數按照消息來源上次與當前節點接觸時間差的分布情況。

圖6是訓練階段結束各算法適用區間分布情況。

五、具體實施方式

下面通過具體實施方式結合附圖對本發明作進一步詳細說明。

首先，本實例是在mit移動用戶數據集下選取epidemic、multi-simbet、sprayandwait、singlerecent、directtransmission五個算法作為典型算法進行仿真。其中，mit移動用戶數據集包含94個移動用戶。這94個用戶中，75人為mit數字實驗室的學生和工作人員，其餘用戶為mitsloanbusiness實驗室學生。組成數據集的包括這94個用戶在2004年9月到2005年3月期間的電話，簡訊，位置等信息。此數據集符合dtn網絡節點動態移動、網絡連接斷開頻繁的特性；在以上五個典型路由算法中，epidemic、multi-simbet、sprayandwait是泛洪路由算法，singlerecent、directtransmission是轉發路由算法。

其次，訓練階段測試各個算法性能指標及消息總數分布情況並計算負載區間。圖3和圖4表明上面五個路由算法進行路由傳輸並統計傳輸成功率、平均路由資源消耗。圖5表明路由傳輸過程中每個節點接收到的消息總數按照消息來源上次與當前節點接觸時間差的分布情況。根據圖5進行線性回歸得到衰減因子q。圖6給出各個算法根據衰減因子q計算的節點負載對成功率的增加情況。由圖6得到epidemic算法適用的負載區間是[0,0.37]，multi-simbet算法適用區間是[0.37,0.62]，sprayandwait算法適用的負載區間是[0.62,0.75]。

接著進入傳輸階段。對於任意一個節點及其鄰居，按照如下流程進行路由：

步驟1：如果鄰居節點就是目的節點，則直接將消息傳送到鄰居節點，路由結束；

步驟2：如果此消息已經過期，則直接廢棄，路由結束；

步驟3：如果鄰居節點負載大於0.75，則使用singlerecent算法進行路由，轉到步驟7；

步驟4：如果鄰居節點負載小於0.75大於0.62，則使用sprayandwait算法進行路由，轉到步驟7；

步驟5：如果鄰居節點負載小於0.62大於0.37，則使用multi-simbet算法進行路由，轉到步驟7；

步驟6：如果鄰居節點負載小於0.37則使用epidemic算法進行路由；

步驟7：確定路由算法之後，更新圖5和圖6以便進行下一跳路由，轉到步驟1。