[發明專利]無線Mesh網絡中基于對偶分解的路由優化方法

有效

• 申請號: 201710557122.4
• 申請日: 2017-07-10
• 公開（公告）號: CN107343303B
• 公開（公告）日: 2019-11-01
• 發明（設計）人: 賈杰;陳劍;劉忠禹;范潤賢;王興偉
• 申請（專利權）人: 東北大學
• 主分類號: H04W40/24
• 分類號: H04W40/24;H04L12/721
• 代理公司: 北京易捷勝知識產權代理事務所(普通合伙) 11613
• 代理人: 齊勝杰

1.一種無線Mesh網絡中基于對偶分解的路由優化方法，其特征在于，包括：

步驟1：根據無線Mesh網絡路由優化過程中網絡層的約束條件和物理層資源分配的約束條件、基于無線Mesh網絡中每一鏈路的信道使用信息確定各鏈路的有效容量值，構建無線Mesh網絡的優化模型；步驟2：采用拉格朗日函數描述所述優化模型，并對優化模型的優化問題進行分解，得到網絡優化子問題和物理層優化子問題；步驟3：初始化拉格朗日函數的對偶變量；

步驟4：基于初始化后的對偶變量，采用凸優化方法處理所述網絡優化子問題，獲得第一處理結果；以及基于初始化后的對偶變量，采用遺傳算法處理所述物理層優化子問題，獲得第二處理結果；

步驟5：判斷第一處理結果和第二處理結果是否收斂，若收斂，則將第一處理結果和第二處理結果作為最優解輸出；

步驟6：若步驟5中的第一處理結果和第二處理結果不收斂，則根據第一處理結果和第二處理結果，對對偶變量進行更新，并基于更新的對偶變量重復步驟4和步驟5的過程，直至收斂；

其中，所述步驟1中構建無線Mesh網絡的優化模型具體包括：

假設無線Mesh網絡中包含N個節點和Q個路由請求，優化模型的目標函數為：

s.t.

其中，<s_q，d_q，r_q>是輸入參數，λ是決定物理層資源分配和路由選擇的優化變量，目標函數及Ui_j均包含非線性約束；

sq、dq、rq分別表示路由請求的源節點、目的節點、流量需求，表示路由請求q從節點i→j或j→i傳輸的流量，i，j∈V，i≠j；

對于任意次用戶i、j(i，j∈V)，定義次用戶i和次用戶j之間每次只能分配1個信道，即，

其中，表示次用戶i的信道分配情況，如果則i≠j，m∈全網的信道集OC，或否則，對任意次用戶i，

其中，表示針對無線Mesh網絡中的每一信道，當感知當前為空閑時，能夠正確檢測到當前信道為空閑的概率；

p_f^m表示針對無線Mesh網絡中的每一信道，當感知當前信道被主用戶占用時，能夠錯誤檢測到當前信道為空閑的概率；

表示針對無線Mesh網絡中的每一信道，將獲取到的主用戶占用當前信道的概率；

表示針對無線Mesh網絡中的每一信道，將獲取到的主用戶釋放當前信道的概率；

表示獲取當主用戶占用當前信道，同時次用戶使用當前信道通信時次用戶對應的SINR；

表示獲取當主用戶未占用當前信道，且次用使用當前信道通信時次用戶對應的SINR；

U_ij表示次用戶i與次用戶j之間使用當前信道的整體有效容量；

為當次用戶i與次用戶j使用信道m進行通信時的有效容量；

為鏈路資源分配變量；

λ_q為第q個路由數據的傳輸數據比例；

E為整個網絡中所有節點根據信道分配與功率控制結果形成的有向圖；

為優化模型的目標函數；

其中，所述步驟2中采用拉格朗日函數描述所述優化模型，并對優化模型的優化問題進行分解的具體步驟包括：

步驟2-1：對所述步驟1中約束條件十的公式進行拉格朗日改寫，得到對應的拉格朗日函數：

其中，為拉格朗日系數；

步驟2-2：對所述步驟2-1中的拉格朗日函數變形，獲得變形函數：

步驟2-3：從所述步驟2-2得到的變形函數中求解網絡優化子問題與物理層優化子問題

約束條件為：所述約束條件六至約束條件九；

約束條件為：所述約束條件一至約束條件五；

即，

步驟2-4：根據拉格朗日函數得到對偶問題為，

其中，步驟6中對偶變量的更新方式為：

為鏈路e的第t次迭代步長。

2.根據權利要求1所述的方法，其特征在于，構建無線Mesh網絡的優化模型之前，所述方法還包括：

基于無線Mesh網絡中認知用戶、主用戶對應的信道使用信息確定每一鏈路的有效容量值。