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

有效

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

本發(fā)明公開了無線多跳網絡中基于網絡編碼的背壓調度方法，包括：構建表示流之間編碼關系的編碼機會概率矩陣；將編碼機會概率矩陣作為鄰接矩陣構建網絡編碼圖，并將基于網絡編碼的背壓調度問題轉化為最大權重團問題；搜索網絡編碼圖中權重和最大的團W_max并對團W_max中的頂點流進行編碼。本方法將流間網絡編碼與背壓調度相結合，以最大化編碼后選擇最大權重團為目標，與傳統(tǒng)的不考慮網絡編碼的背壓調度算法相比，自然釋放更多背壓，提高了網絡吞吐量；通過限定選擇最大頂點權重次數(shù)n來限制搜索到的最大權重團個數(shù)；同時限制在每次找到最大權重頂點之后，再尋找包含此頂點的最大權重團的最大團大小m，從而進一步較低計算復雜度。

技術領域

本發(fā)明涉及無線多跳網絡中節(jié)點的調度方法，尤其涉及基于網絡編碼的背壓調度方法，屬于網絡編碼技術領域和無線通信資源調度技術領域。

背景技術

背壓算法用在無線多跳網絡資源分配和路由調度中，是眾所周知的跨層調度算法。他由Tassiulas和Ephremides在IEEE Trans.Auto.Control,vol.37,no.12,Dec.1992,pp.1936–48上所發(fā)表的論文“Stability Properties of Constrained QueueingSystems and Scheduling Policies for Maximum Throughput in Multihop RadioNetworks”中提出，已經證明是吞吐量最優(yōu)的。由背壓調度算法獲得的調度策略能達到任意其它資源分配策略所支持的到達速率，背壓算法已經被用在擁塞控制和有效的路由協(xié)議中。

然而在廣泛應用之前，有很多問題急需解決，例如如何有效降低端到端時延、如何有效降低隊列復雜度、如何取得有效的跨層設計、如何提高網絡的吞吐量等。

發(fā)明內容

本發(fā)明所要解決的技術問題是克服現(xiàn)有技術的缺陷，提供基于網絡編碼的背壓調度方法，能夠使得每次調度釋放更多的背壓，提高了網絡的吞吐量，減小延時。

為解決上述技術問題，本發(fā)明提供無線多跳網絡中基于網絡編碼的背壓調度方法，其特征是，具體包括：

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

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

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

進一步地，構建表示流之間編碼關系的編碼機會概率矩陣時考慮有干擾模式和無干擾模式。

更進一步地，在無干擾模式下，流之間滿足編碼條件就可以編碼；在有干擾模式下，滿足編碼條件的流能否編碼由編碼機會概率決定。

再進一步地，構建表示流之間編碼關系的編碼機會概率矩陣的具體步驟為：

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

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

S3：設置編碼門限值δ，大于等于此門限時可編碼，其編碼機會概率設置為1，否則不可編碼，其編碼機會概率置0；根據(jù)確定的流之間的編碼機會概率確定編碼機會概率矩陣P。進一步地，步驟S3將有干擾和無干擾模式用編碼機會概率矩陣統(tǒng)一起來，構建網絡編碼圖并將基于網絡編碼的背壓調度問題轉化為最大權重團問題具體包括：