[發明專利]無線多跳網絡中基于網絡編碼的背壓調度方法

有效

• 申請號: 201810435998.6
• 申請日: 2018-05-09
• 公開（公告）號: CN108599898B
• 公開（公告）日: 2020-10-16
• 發明（設計）人: 梅中輝;胡燕燕
• 申請（專利權）人: 南京郵電大學
• 主分類號: H04L1/00
• 分類號: H04L1/00;H04L12/24;H04W72/12
• 代理公司: 南京縱橫知識產權代理有限公司 32224
• 代理人: 董建林

1.無線多跳網絡中基于網絡編碼的背壓調度方法，其特征是，具體包括：

(1)構建表示流之間編碼關系的編碼機會概率矩陣；

(2)將步驟(1)確定的編碼機會概率矩陣作為鄰接矩陣構建網絡編碼圖，并將基于網絡編碼的背壓調度問題轉化為最大權重團問題；

(3)搜索網絡編碼圖中權重和最大的團W_max并對團W_max中的頂點流進行編碼；

步驟(2)具體包括：用無向圖G(V，E)表示網絡編碼圖，其中頂點集V＝{v_i|i＝1，2，...，k}表示流f_i(i＝1，2，...，k)，邊集E＝{e_ij|i，j＝1，2，...，k}表示流之間的編碼關系；頂點權重W＝{w_i|i∈1，2，...，k}表示每個流到下一跳的背壓，邊權重P＝{p_ij|i，j∈V}表示流之間編碼機會概率；

用x_j∈(0，1)表示頂點v_j的狀態，當v_j∈C時x_j＝1，否則x_j＝0，其中C為候選圖；G的一個補圖用表示，即有目基于網絡編碼的背壓調度問題可用如下表達式建模：

s.t.x_i∈{0，1}，i＝1，...，k (3)，

步驟(3)具體包括：

S31：選擇頂點權重最大的頂點v_i；

S32：搜索包含v_i的最大權重的團并記錄第j次搜索得到的最大團權重和以及其對應的流

S33：刪除權重最大的頂點v_i及與之相連的邊；

S34：在剩余圖中重復步驟S31-S33操作n次；

S35:找到n次搜索的最大團中權重和最大的，表達是如下：

S36：選擇W_max這個團對應的頂點流進行編碼。

2.根據權利要求1所述的基于網絡編碼的背壓調度方法，其特征是，構建表示流之間編碼關系的編碼機會概率矩陣時考慮有干擾模式和無干擾模式。

3.根據權利要求2所述的基于網絡編碼的背壓調度方法，其特征是，在無干擾模式下，流之間滿足編碼條件就可以編碼；在有干擾模式下，滿足編碼條件的流能否編碼由編碼機會概率決定。

4.根據權利要求3所述的基于網絡編碼的背壓調度方法，其特征是，構建表示流之間編碼關系的編碼機會概率矩陣的具體步驟為：

S1：在無干擾模式下，滿足編碼條件的流之間的編碼機會概率為1；

S2：在有干擾模式下，滿足編碼條件的流之間的編碼機會概率是區間(0,1)上的隨機小數；

S3：設置編碼門限值δ，大于等于此門限時可編碼，其編碼機會概率設置為1，否則不可編碼，其編碼機會概率置0；根據確定的流之間的編碼機會概率確定編碼機會概率矩陣P。

5.根據權利要求1所述的基于網絡編碼的背壓調度方法，其特征是，搜索包含v_i的最大權重的團時設定選擇最大頂點權重次數n。

6.根據權利要求1所述的基于網絡編碼的背壓調度方法，其特征是，搜索包含v_i的最大權重的團時設定包含最大權重頂點的最大權重團的最大團大小m。