[發明專利]基于消息下一跳動態規劃的機會網絡路由機制實現方法

有效

• 申請號: 201910021927.6
• 申請日: 2019-01-10
• 公開（公告）號: CN109525494B
• 公開（公告）日: 2021-05-07
• 發明（設計）人: 曾鋒;段偉昊
• 申請（專利權）人: 中南大學
• 主分類號: H04L12/721
• 分類號: H04L12/721;H04L12/733;H04L12/751;H04W40/24
• 代理公司: 長沙市融智專利事務所(普通合伙) 43114
• 代理人: 歐陽迪奇

1.一種基于消息下一跳動態規劃的機會網絡路由機制實現方法，其特征在于，包括以下步驟：

步驟一，為每個路由路徑上的節點建立一個用于存儲該節點的歷史信息的信息表，歷史信息包括該節點和其他節點的歷史相遇信息以及歷史相遇次數；

步驟二，每個節點維護一張路由規劃表，用來存儲動態規劃機制計算得出的消息的下一跳轉發節點信息；

步驟三，當某節點A與B相遇時，建立兩個節點間的信道，查詢節點A的規劃表中是否存在節點B的信息，如果存在，節點A將需要轉發的對應消息轉發給節點B，然后斷開信道并返回步驟三循環執行，否則進入步驟四；

步驟四，節點A獲取B信息表中的數據，計算用于評估節點信息負載量的轉發評估值，并與閾值比較，如果轉發評估值超過閾值則進入步驟五，否則跳轉步驟六；

步驟五，基于動態規劃機制來動態規劃合適的下一跳節點隊列，并記錄在節點A的路由規劃表中，然后返回步驟三循環執行；

步驟六，節點A轉發消息給B，并返回步驟三循環執行；

所述的步驟四中，所述的轉發評估值為：

對于節點A中的消息x，綜合考慮消息x的成熟度和節點B的負載度做出轉發決策，定義E(A,B,x)為轉發評估值：

E(A,B,x)＝f_A(x)×d(B) (1)

f_A(x)表示節點A的消息隊列中存在消息x的成熟度，表達式為：

其中g_A(x)表示消息x所經過的跳數，h(x)表示消息x在網絡中的存在時間與其最大存活時間之比，α和β為兩部分的權重系數且α+β＝1；

d(B)表示相遇節點B的負載度，假設節點B的發送隊列中有m個消息，消息i的等待時間為t_i，則節點B的負載度d(B)定義為下式：

2.根據權利要求1所述的一種基于消息下一跳動態規劃的機會網絡路由機制實現方法，其特征在于，所述的步驟一中，所述的歷史信息在兩個節點相遇時進行計數，若相遇節點的信息表中存在本節點，則將表中相遇次數加1，若不存在，則將本節點信息加入相遇節點的信息表中，并將相遇次數設置為1。

3.根據權利要求1所述的一種基于消息下一跳動態規劃的機會網絡路由機制實現方法，其特征在于，所述的步驟二中，所述的每個節點維護一張路由規劃表的過程為：通過動態規劃機制計算出下一跳轉發節點信息后，節點將該節點信息和對應的消息信息一起存入節點規劃表中，一個消息對應至少一個下一跳轉發節點信息。

4.根據權利要求3所述的一種基于消息下一跳動態規劃的機會網絡路由機制實現方法，其特征在于，所述的存入節點規劃表中與節點信息對應的消息信息是正在進行動態規劃的需要由路由節點進行轉發的當前消息。

5.根據權利要求1所述的一種基于消息下一跳動態規劃的機會網絡路由機制實現方法，其特征在于，所述的步驟三中，節點A將對應消息轉發給節點B中所述的對應消息，是在節點A的路由規劃表中根據節點B的ID去反向查找動態規劃分配給此節點的消息。

6.根據權利要求1所述的一種基于消息下一跳動態規劃的機會網絡路由機制實現方法，其特征在于，所述的步驟五中，基于動態規劃機制來動態規劃合適的下一跳節點隊列包括以下步驟：

(1)將本節點信息表T中的所有節點構成局部優先隊列，這些節點的順序由相遇次數t值從小到大排列，t值相等的節點就按照節點信息攜帶量m由小到大排列，形成一個優先隊列L₁；

(2)在L₁中采用二分法選取中間點，假設L₁中存在N₁、N₂、N₃、...N_d個節點，中間點為N_i，選取規則如下：

其中g(x)是獲取節點相遇次數t的函數，R(x)是通過節點相遇次數t返回節點索引r的函數；

(3)將L₁中相遇次數小于中間點N_i相遇次數的節點選出，組成新隊列L₂；

(4)將L₂中的所有節點按照節點信息攜帶量m由小到大排列，在m相同的前提下再按照節點攜帶信息總跳數n由小到大的順序排列，形成一個優先隊列L₃；

(5)按照n的大小將L₃劃分為若干區間，n值越大，節點所獲得的區間長度越大，通過隨機函數產生一顆隨機種子，該種子隨機落在L₃的某個區間中并由區間長度決定隨機種子落在相應區間的可能性，種子落在的區間對應的節點即為閾值節點，然后利用這個閾值節點的信息攜帶量exp_m作為樣例閾值；

(6)在隊列L₃中，將m值小于閾值節點的節點選取出；

(7)將這些選取出來的節點重新形成一個新的臨時優先隊列L₄，然后在L₄中按照節點攜帶信息總跳數n排序，如果節點的n值相等，那么就按照t值由小到大的順序排列；

(8)根據預先設定的規劃值大小，取出L₄中相應規模的節點作為動態規劃獲得的節點隊列L_e，并記錄在本節點的規劃表中；

(9)當攜帶有這些規劃節點記錄的節點與某個規劃節點相遇時，則會向規劃節點轉發消息。