[發明專利]多速率無線Mesh網絡路由度量與信道分配聯合方法

有效

• 申請號: 201610013021.6
• 申請日: 2016-01-11
• 公開（公告）號: CN105704756B
• 公開（公告）日: 2019-01-04
• 發明（設計）人: 石文孝;劉吉平;王繼紅;崔克強;柴媛;吳芃霞
• 申請（專利權）人: 吉林大學
• 主分類號: H04W28/08
• 分類號: H04W28/08;H04W40/02;H04W40/12;H04W40/16
• 代理公司: 長春吉大專利代理有限責任公司 22201
• 代理人: 王淑秋

1.一種多速率無線Mesh網絡路由度量與信道分配聯合方法，其特征在于步驟如下：

步驟1)確定多速率無線Mesh網絡中的源節點到達目的節點的最短路徑及對應的轉發節點和所需傳輸速率，得到路由度量后的多速率無線Mesh網絡；

步驟2)基于速率分離原則對步驟1)得到的路由度量后的多速率無線Mesh網絡各節點上不同速率鏈路進行分離，將不同速率鏈路分配到不同接口上，使各節點吞吐量權值最大化；對于其中任意節點i吞吐量權值最大化步驟如下：

(1)網絡中的傳輸節點i有3個接口m₀、m₁、m₂，將節點i上的鏈路移入目標接口設為接口m₁；

(2)將連接到節點i的所有鏈路按照傳輸所需的預估時間T值的遞增順序進行排序，若連接到節點i的鏈路數為偶數，則將鏈路按照序列順序從中間分開為數量相等的高速率與低速率兩部分，若連接到節點i的鏈路數為奇數，則將處于中間的鏈路分配到高速率部分當中；將排序后高速率部分的鏈路分配給接口m₀，低速率部分的鏈路分配給接口m₂；對于當前的鏈路分配情況，計算出當前的節點i吞吐量權值；

(3)將m₀接口隊列中按照排序序列T值最高的鏈路暫時從接口m₀移動到目標接口m₁，并計算鏈路重分配后的節點i新的吞吐量權值；如果新的吞吐量權值比之前的吞吐量權值大，即吞吐量權值獲得了增益，那么將此鏈路永久的與接口m₁綁定，將節點i吞吐量權值更新；如果新的吞吐量權值比之前的吞吐量權值小，那么將此鏈路移回接口m₀，節點吞吐量權值不變；逐次將m₀接口隊列中T值最高的鏈路移動到目標接口m₁并重復上述步驟；直至移動到m₀接口上的鏈路不使節點i的吞吐量權值產生新的增益為止，將此時移動的鏈路移回原接口m₀，m₀接口鏈路分配結束；

(4)將m₂接口隊列中按照排序序列T值最低的鏈路暫時從接口m₂移動到目標接口m₁，并計算當前鏈路重分配后節點i的新的吞吐量權值；如果新的吞吐量權值比之前的吞吐量權值更大，即吞吐量權值獲得了增益，那么將此鏈路永久的與接口m₁綁定，將節點i吞吐量權值更新，如果新的吞吐量權值比之前的吞吐量權值小，那么將此鏈路移回接口m₁，節點i吞吐量權值不變；逐次將m₂接口隊列中T值最高的鏈路移動到目標接口m₁并重復上述步驟，直至移動到m₂接口上的鏈路不使節點i的吞吐量權值產生新的增益為止，將此時移動的鏈路移回原接口m₂，m₂接口鏈路分配結束；節點i的鏈路分配結束；

其中路由度量后的多速率無線Mesh網絡中任意節點i的吞吐量權值S_i的確定方法如下：

首先根據式(5)、式(6)、式(7)計算節點i的鏈路速率偏差V_i：

式中：m為節點i上的接口；v_m為節點i的接口m上鏈路速率偏差，M_i是節點i上接口的集合；l為接口m上的鏈路，L_m為接口m上的鏈路數，C_m為接口m上鏈路的集合；T_l為節點i的接口m上鏈路l傳輸所需的預估時間，s_l是節點i的接口m上鏈路l傳輸的數據包大小，r_l是節點i的接口m上鏈路l傳輸時所使用的速率；

根據式(9)求得節點i的Jain公平性指數J(i)為：

式中：m為節點i上的接口；L_m為接口m上的鏈路數，D為節點i的接口數；

根據式(10)求得節點i的吞吐量權值S_i：

S_i＝V_i×J(i) (10)

式中：V_i是式(5)得出的節點i鏈路速率偏差；J(i)是式(9)得出的節點i的Jain公平性指數；

步驟3)在步驟2)的基礎上，以節點上的接口為單位，進行信道分配，其方法如下：

首先從目的節點開始，根據到達目的節點的跳數多少依次進行信道分配，到達目的節點跳數少的節點優先進行信道分配；對任一節點i上的接口m分配信道時，取節點2跳或3跳范圍內的鄰居節點為干擾節點，干擾節點上的傳輸鏈路為干擾鏈路，根據式(11)，分別求在各可用信道上節點接口上鏈路傳輸所需的預估時間；

式中：是節點i上的接口m分配信道k時接口m上的鏈路傳輸所需的預估時間；是節點i上的接口m分配信道k時，在無干擾節點條件下，接口m上的鏈路l_m傳輸的預估時間，為此條件下接口m上所有鏈路傳輸預估時間之和，C_m為接口m上鏈路的集合；是節點i的2跳或3跳范圍內，與節點i的下一跳鏈路使用相同信道k的鄰居干擾節點x上的干擾鏈路l_x傳輸預估時間；B是節點i的2跳或3跳范圍內，與節點i的下一跳鏈路使用相同信道k的鄰居干擾節點上的干擾鏈路的集合；

選出使得最小的信道，將該信道分配給接口m上的鏈路。

2.根據權利要求1所述的多速率無線Mesh網絡路由度量與信道分配聯合方法，其特征在于所述步驟1)中在多速率網絡環境下，采取從目的節點逆向找路的方式，進行多速率最短路徑路由度量，通過計算不同條件下源節點到目的節點的路徑開銷，獲取源節點路徑的最小開銷，得到源節點到達目的節點的最短路徑，并得出轉發節點和所需傳輸速率；步驟如下：

(1)給定網絡圖G＝(V,E)，V是非空的由有限個節點所構成的集合，E是由節點對組成的邊的集合；R為網絡可用傳輸速率的集合；節點d為目的節點；將節點集V分為兩組：置定節點集G_p和未置定節點集G_u，G_u＝G-G_p，其中G_p內的所有置定節點，是已完成最短路徑的計算的節點，G_u內的節點是未置定節點；

(2)調整各未置定節點的最短路徑：對G_u中的任一節點x，x∈G_u，將G_p中的所有可連接的節點作為其轉發節點，對每種速率r∈R，依次計算從節點x使用速率r連接到G_p中各置定節點的路徑開銷；若節點x新計算出的路徑開銷小于上次計算的路徑開銷值，則更新節點x的路徑開銷W_x、轉發節點F_x和傳輸速率R_x，否則該節點的路徑開銷、轉發節點和傳輸速率均不變，直至遍歷所有G_p中的可連接轉發節點和可用傳輸速率為止，獲得節點x的最小路徑開銷W_x、轉發節點F_x和傳輸速率R_x；無法使用任一速率r通過置定節點集G_p中的節點作為轉發節點連接到目的節點d的節點，路徑開銷為無窮大；G_u中所有節點獲得最小路徑開銷后，對未置定節點集G_u中所有參與計算的節點x，x∈G_u，選出其中擁有最小路徑開銷的節點i，確定節點i的路徑開銷W_i，并確定此時節點i的轉發節點F_i與所使用的傳輸速率R_i，之后將i劃歸到G_p中；在更替的過程中，需要總保持從目的節點d到G_p中各節點的最小路徑開銷不大于從目的節點d到G_u中任何節點的最小路徑開銷；

(3)重復步驟(2)，至G_u最終成為空集時，即求得所有節點到目的節點d的最短路徑。