[發明專利]一種實現無線Mesh網絡最大吞吐率方法

有效

• 申請號: 201611190627.3
• 申請日: 2016-12-21
• 公開（公告）號: CN106856618B
• 公開（公告）日: 2019-05-31
• 發明（設計）人: 范子樵;朱潔;劉濤
• 申請（專利權）人: 陜西尚品信息科技有限公司
• 主分類號: H04W40/02
• 分類號: H04W40/02;H04W40/12;H04W40/16;H04W40/18;H04W84/18
• 代理公司: 暫無信息
• 代理人: 暫無信息

1.一種實現無線Mesh網絡最大吞吐率方法，其特征在于，包括以下步驟：

步驟一：建立無線Mesh網絡拓撲結構：

(1-1)建立全向無線傳播的無線Mesh網絡，并用無向無環簡單圖G＝(R,L)表示，R是節點的集合，L是節點間路徑的集合，網絡中所有節點均為靜態且不移動；R_i表示Mesh網絡中的節點，R_i∈R；l_ij表示節點R_i到節點R_j(1≤i,j≤|R|,i≠j)間的傳輸路徑，l_ij∈L；c_ij表示l_ij的路徑容量，即該路徑單位時間內所能傳輸的信息量，也稱為傳輸速率，單位為bit/s(bps)；

(1-2)建立時隙集合T，所述無線Mesh網絡中，有k個時隙，用t₁,t₂,…,t_k表示，組成時隙集合{t₁，t₂，…，t_k}；表示節點R_j在時隙t_k內接收到的來自節點R_i的信息，的單位為bits；

在無線Mesh網絡中，假設只有發端節點R_s可創建數據包，且發端節點總有數據包可傳輸，不考慮收端節點收到重復的數據包，同時假設節點使用MAC協議實現數據傳輸，則無線Mesh網絡傳輸標準為IEEE制定的802.11a/b/g，從而實現多速率傳輸；

步驟二：確保無線Mesh網絡的無碰撞傳輸：

R_i為無線Mesh網絡中的一個節點，N(R_i)表示R_i的相鄰節點集合；

無線Mesh網絡中節點在一次干擾下無碰撞傳輸，網絡中任一節點R_m向其相鄰節點R_n傳輸時，不再接收任何其他相鄰節點R_j傳輸的信息，網絡中節點在一次干擾下無碰撞傳輸的約束條件為：

且

其中R_j∈N(R_m)，j≠n，表示如果R_m傳輸信息至其相鄰節點R_n，R_m不能接收任何來自其他相鄰節點R_j傳輸的信息；

確保無線Mesh網絡中節點在二次干擾下無碰撞傳輸，網絡中任一節點R_n在接收其相鄰節點R_m的傳輸時，R_n的其他相鄰節點R_i不能同時傳輸信息，并且確保在R_n在接收R_m的傳輸時不能同時傳輸信息至R_n的其他相鄰節點R_i(i≠m)；

網絡中節點在二次干擾下無碰撞傳輸的約束條件為：

表示當R_n在接收R_m的傳輸時，那么R_n的相鄰節點，除R_m外，不能同時傳輸信息至R_n；表示當R_n在接收R_m的傳輸時，R_n不能同時傳輸信息至其相鄰節點；

步驟三：確定路由路徑：

從選擇一條路徑開始搜索，能夠到達接收端節點就采用該路徑，不能到達接收端節點就返回上一節點重新選擇其相鄰節點嘗試搜索，直至找到發端到收端的路徑；

無線Mesh網絡的發端節點R_s，從R_s開始查詢R_s的相鄰節點，如果查找到其鄰居節點是收端節點R_d；否則，選擇R_s的相鄰節點R_1x，查詢R_1x的相鄰節點，查找收端節點R_d；否則，選擇R_1x的相鄰節點R_2x，查詢R_2x的相鄰節點，查找收端節點R_d；直到查找到收端節點R_d，建立路徑L_sd；

發端節點R_s到收端節點R_d存在多條路徑，刪除不必要的路徑以減少計算成本，其中不必要的路徑指存在某一時隙，使得在該條路徑上有信息正在進行傳輸，若存在一條路徑，該路徑中兩節點R_i和R_j，在某一時隙t_k，使得則稱L_ij為不必要的路徑；

刪除所有不必要的路徑，組成路徑發端節點R_s到收端節點R_d的路由路徑集合L(p)；

步驟四：基于空間復用的時隙分配：

以空間復用作為基礎，給每條路徑分配時隙，時隙集合{t₁，t₂，…，t_k}，按如下步驟進行：

(4-1)記路徑p分配的時隙數為T_a(p)，L(t)為路徑集合L(p)中時隙分配包含第t個時隙的路徑集合，并初始化T_a(p)＝0，L(t)＝NULL，t＝1；

(4-2)所述路徑中，任選一條分配時隙數最少的路徑p₁，為其分配時隙t，即將路徑p₁作為集合L(t)的元素，同時執行T_a(p1)+1；

(4-3)對于已經分配的任一時隙t，在L(p)-L(t)中，如果當前時隙中的任一路徑p₂與路徑p₁具有相同的節點，則這兩條路徑不能分配同一時隙；如果當前時隙中的任一路徑p₂與路徑p₁具有完全不同的節點，則這兩條路徑可以分配同一時隙，即給路徑p₂也分配時隙t，同時將路徑p₂加入L(t)，T_a(p₂)+1；

(4-4)每分配一個時隙，時隙序號t＝t+1，然后對所有路徑按照各路徑目前分配的時隙數T_a從小到大重新排序，對時隙t進行分配，若所有路徑均分配到至少一個時隙，則結束時隙分配，否則返回步驟(4-2)，繼續分配時隙；

(4-5)將所有分配好的時隙記為T＝{t₁，t₂，…，t_t}，t≤k，按這種方法分配保證了分配到的時隙數最少，即最小；

步驟五：尋找額外路徑來提高吞吐率：

g為路徑集合L(p)中的路徑總數，f代表其中的一條路徑，c_ij(f)表示路徑f中每一條路徑的路徑容量，一條路徑的瓶頸路徑容量為min{c_ij(f)}，時隙t_k的持續時間為d(t_k)；

路徑吞吐率為所有路徑的瓶頸路徑容量之和與已分配時隙的總時間之比，即總的路徑吞吐率：

所述最小，可以得到最大化的吞吐率；

若步驟四中分配的時隙數t滿足t<k，則在步驟三中刪除的不必要路徑中查找額外路徑；若存在路徑滿足在時隙m∈(t,k]內有f_ij,tm＝0，即在未分配的時隙內，存在不必要路徑處于空閑狀態，則將該不必要路徑作為額外路徑；反之，則不存在額外路徑；所述分配的時隙數t＝k，則同樣不存在額外路徑；

將上述找到的額外路徑記為l(g+1)，用δ表示額外路徑l(g+1)所分配時隙的持續時間，若該額外路徑滿足加上該路徑后整體路由吞吐率比原來有增加，即：

則在已給出路徑流量的情況下，只有增加一條額外路徑l(g+1)可以使得整體路由吞吐率比原本路由吞吐率更大時，才能增加額外路徑；

在無線Mesh網絡中，若存在一條從發端到收端的路徑滿足使得路徑吞吐率提高，則可以添加該路徑達到吞吐率最大化。