[發明專利]一種基于受限優先的逐輪遞增式時隙分配方法

有效

• 申請號: 201810734667.2
• 申請日: 2018-07-06
• 公開（公告）號: CN109041230B
• 公開（公告）日: 2022-03-18
• 發明（設計）人: 王葉群;曾浩洋;姜永廣;隋天宇;毛建兵;鄭重
• 申請（專利權）人: 中國電子科技集團公司第三十研究所
• 主分類號: H04W72/04
• 分類號: H04W72/04;H04W72/08
• 代理公司: 成都九鼎天元知識產權代理有限公司 51214
• 代理人: 鄧世燕

本發明公開了一種基于受限優先的逐輪遞增式時隙分配方法，采用逐輪遞增循環控制算法為路徑分配時隙資源，在每輪次時隙分配時，執行如下步驟：步驟一、通過優先鏈路選擇算法選出可用時隙數量最少的鏈路集，確定待分配時隙的鏈路；步驟二、通過優先時隙選擇算法為待分配時隙的鏈路，在可用時隙集中查找干擾程度最小的時隙；步驟三、通過時隙分配算法為待分配時隙的鏈路分配步驟二得到的干擾程度最小的時隙，并對一跳、兩跳鄰居鏈路的可用時隙集進行更新。本發明克服了現有的時隙分配方法難以同時滿足計算量小和獲取路徑最大帶寬這兩方面需求，為TDMA網絡路徑傳輸能力評估和QoS路徑選擇提供理論依據。

技術領域

本發明涉及一種基于受限優先的逐輪遞增式時隙分配方法。

背景技術

時分多址接入(Time Division Multiple Aceess,TDMA)是移動自組織網絡(Mobile Ad Hoc Networks,MANET)中常用的信道接入協議，通過動態的時隙分配和無沖突的空間復用，可有效提高信道資源的利用率和網絡整體性能。基于TDMA的MANET網絡(以下簡稱“TDMA網絡”)的路徑最大帶寬是進行路徑傳輸能力評估的重要指標，也是進行QoS路由選擇的判決依據，但TDMA網絡的路徑帶寬計算屬于典型的NP(Non-DeterminationPolynomial)完全問題，路徑帶寬大小由時隙分配方法決定，現有的路徑帶寬計算及時隙分配方法主要有以下三類：

一是使用構成該路徑各條鏈路的最小帶寬作為路徑最大帶寬，這顯然是不正確的。

二是采用基于前向/后向算法(Forwarding/Backward Algorithm,FA/BA)的啟發式分配方法，從源/目的節點開始逐跳計算局部最優解，直至到達目的/源節點后為止，該方法與AODV路由協議的尋址機制非常匹配，計算效率高，但由于求解的是本地最大帶寬，無法得到全局最優解,即獲取不了路徑最大帶寬。

三是從全局的角度進行時隙分配(Slot Assignment by Global Overview,SAGO)，優先為可用時隙資源少的鏈路分配時隙；優先分配對其它鏈路干擾小的時隙；當存在多條時隙資源最少的鏈路時，從中找出對其它鏈路干擾小的時隙，優先為該時隙所對應的鏈路分配時隙。與基于局部最優的啟發式時隙分配方法相比，SAGO時隙分配方法更有利于獲取全局最優的時隙分配方案；但SAGO主要用于判斷路徑是否滿足給定帶寬需求，而不是求解路徑最大帶寬，若定義“為1條鏈路分配1個時隙的計算量等于1”，則SAGO時隙分配方法獲取路徑最大帶寬的計算量略大于其中N為構成路徑的鏈路數，r_max為路徑最大帶寬。當r_max較大時，SAGO時隙分配方法的計算量遠大于啟發式分配方法的計算量N·r_max。

發明內容

為了克服現有技術的上述缺點，本發明提供了一種基于受限優先的逐輪遞增式時隙分配方法，旨在解決現有TDMA網絡路徑帶寬計算與時隙分配方法難以同時解決計算量和全局最優解的問題。

本發明解決其技術問題所采用的技術方案是：一種基于受限優先的逐輪遞增式時隙分配方法，采用逐輪遞增循環控制算法為路徑分配時隙資源，在每輪次時隙分配時，執行如下步驟：

步驟一、通過優先鏈路選擇算法選出可用時隙數量最少的鏈路集，確定待分配時隙的鏈路；

步驟二、通過優先時隙選擇算法為待分配時隙的鏈路，在可用時隙集中查找干擾程度最小的時隙；

步驟三、通過時隙分配算法為待分配時隙的鏈路分配步驟二得到的干擾程度最小的時隙，并對一跳、兩跳鄰居鏈路的可用時隙集進行更新。

與現有技術相比，本發明的積極效果是：

本發明提出的逐輪遞增循環分配、受限鏈路優先分配和低干擾時隙優先分配相結合的聯合分配方法，克服了現有的時隙分配方法難以同時滿足計算量小和獲取路徑最大帶寬這兩方面需求，為TDMA網絡路徑傳輸能力評估和QoS路徑選擇提供理論依據。