[發(fā)明專利]基于消息下一跳動態(tài)規(guī)劃的機會網(wǎng)絡路由機制實現(xiàn)方法

有效

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

1.一種基于消息下一跳動態(tài)規(guī)劃的機會網(wǎng)絡路由機制實現(xiàn)方法，其特征在于，包括以下步驟：

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

步驟二，每個節(jié)點維護一張路由規(guī)劃表，用來存儲動態(tài)規(guī)劃機制計算得出的消息的下一跳轉發(fā)節(jié)點信息；

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

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

步驟五，基于動態(tài)規(guī)劃機制來動態(tài)規(guī)劃合適的下一跳節(jié)點隊列，并記錄在節(jié)點A的路由規(guī)劃表中，然后返回步驟三循環(huán)執(zhí)行；

步驟六，節(jié)點A轉發(fā)消息給B，并返回步驟三循環(huán)執(zhí)行；

所述的步驟四中，所述的轉發(fā)評估值為：

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

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

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

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

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

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

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

4.根據(jù)權利要求3所述的一種基于消息下一跳動態(tài)規(guī)劃的機會網(wǎng)絡路由機制實現(xiàn)方法，其特征在于，所述的存入節(jié)點規(guī)劃表中與節(jié)點信息對應的消息信息是正在進行動態(tài)規(guī)劃的需要由路由節(jié)點進行轉發(fā)的當前消息。

5.根據(jù)權利要求1所述的一種基于消息下一跳動態(tài)規(guī)劃的機會網(wǎng)絡路由機制實現(xiàn)方法，其特征在于，所述的步驟三中，節(jié)點A將對應消息轉發(fā)給節(jié)點B中所述的對應消息，是在節(jié)點A的路由規(guī)劃表中根據(jù)節(jié)點B的ID去反向查找動態(tài)規(guī)劃分配給此節(jié)點的消息。

6.根據(jù)權利要求1所述的一種基于消息下一跳動態(tài)規(guī)劃的機會網(wǎng)絡路由機制實現(xiàn)方法，其特征在于，所述的步驟五中，基于動態(tài)規(guī)劃機制來動態(tài)規(guī)劃合適的下一跳節(jié)點隊列包括以下步驟：

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

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

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

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

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

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

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

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

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

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