無線Mesh網絡多播部分重疊信道分配方法
2023-10-09 05:41:59
無線Mesh網絡多播部分重疊信道分配方法
【專利摘要】本發明涉及一種無線Mesh網絡多播部分重疊信道分配方法，該方法如下：通過獲取網絡的拓撲信息及多播接收端列表得到網絡拓撲圖，構建對應的多播加權衝突圖；根據多播加權衝突圖與網絡拓撲圖的映射關係，得到網絡拓撲圖中各鏈路的權重；計算各未被覆蓋的多播接收端到網關的各路徑的路徑代價，從中選擇最小代價路徑並為相關鏈路分配信道；更新未被覆蓋的多播接收端列表及網絡拓撲圖中各鏈路的權重；重複上述步驟(3)和(4)，直到所有多播接收端均包含到多播樹中，多播樹構建及信道分配完畢。本發明能夠依據節點間的歐式距離及其信道間隔準確判斷節點之間的幹擾關係，在進行信道分配時充分利用無線廣播優勢，從而最小化網絡的帶寬消耗和幹擾。
【專利說明】無線Mesh網絡多播部分重疊信道分配方法
【技術領域】
[0001]本發明屬於無線通信【技術領域】，尤其涉及一種基於多播加權衝突圖的無線Mesh網絡多播部分重疊信道分配方法。
【背景技術】
[0002]無線Mesh網絡(Wireless Mesh Networks, WMNs)具有高帶寬、快速部署、易於安裝、維護簡單、前期投資成本低等優勢，能夠擴展無線網絡的覆蓋範圍，因此有望成為解決「最後一公裡」接入問題的理想解決方案。WMNs是由固定的Mesh路由器、固定或移動的Mesh客戶端組成的。部分Mesh路由器具有橋接功能,可以通過有線鏈路連接到Internet,充當WMNs的網關。
[0003]多播是WMNs中的一種重要通信方式，它一般以網關為源節點，通過有效的傳遞方式將信息同時傳遞給一組接收端，從而節省帶寬，這組接收端通常稱為多播接收端。近年來，WMNs中部署了很多基於多播的應用，比如大規模音頻/視頻會議、遠程教育、分布式交互遊戲等。這些應用對網絡容量、實時性和傳輸質量都有很高的要求，這對WMNs有限的容量帶來極大挑戰。信道分配通過為接口合理分配信道顯著降低幹擾，提升網絡容量。多播相比於單播最重要的區別在於多播具有無線廣播優勢(WirelessBroadcastAdvantage，WBA)，即從同一個節點接收數據的各節點之間不存在幹擾。通常我們將起始於同一個節點的多條鏈路稱為兄弟鏈路，在進行多播信道分配時儘量為兄弟鏈路分配相同信道以利用WBA。另外，現有研究成果表明部分重疊信道(PartiallyOverlappedChannels, POCs)，即頻譜上有交疊的信道的使用有助於克服IEEE802.llb/g標準正交信道資源有限的困難，幫助增加網絡中的並行傳輸鏈路數，進而提升網絡容量。在使用POCs時，信道間隔指兩條信道的信道號的差值，比如信道I與信道4之間的信道間隔為3。
[0004]目前WMNs中部分重疊信道下的多播信道分配主要針對於單個多播流，信道分配算法大致可以分為兩類:聯合多播路由與信道分配，分立多播路由與信道分配。聯合多播路由與信道分配方法考慮路由與信道分配的相互作用，將它們看成一個整體使用規劃方法進行求解，雖然規劃方法能得到最優解，但是其求解難度較大，很難應用於實際網絡。分立多播路由與信道分配方法先構建多播樹，然後為構建好的多播樹中的鏈路分配信道。該類方法求解的複雜度較低，通常能獲得次優解。在為節點分配信道時，現有分立多播路由與信道分配方法選擇與已經分配了信道的一跳或兩跳鄰居的幹擾和最小的信道，但是跳數距離並不能準確反映節點之間的幹擾關係。因此應使用歐式距離及信道間隔作為節點間是否幹擾的判據，以最小化網絡幹擾為目標、充分利用WBA來構建多播樹、完成信道分配，從而減少網絡中的帶寬消耗和幹擾，實現多播業務的有效傳輸。
【發明內容】
[0005]本發明要解決的技術問題是提供一種能夠準確判斷節點間幹擾關係，並能有效降低網絡帶寬消耗和網絡中的總幹擾、提升多播吞吐量的無線Mesh網絡多播部分重疊信道分配方法。
[0006]為了解決上述技術問題，本發明的無線Mesh網絡多播部分重疊信道分配方法包括:
[0007]I)獲取網絡的拓撲信息、多播接收端列表，得到原始網絡拓撲圖；
[0008]2)初始化已分配信道的鏈路列表及未被覆蓋的多播接收端列表；
[0009]3)根據步驟I)中的原始網絡拓撲圖及多播接收端列表，構建對應的多播加權衝突圖；多播加權衝突圖構建方法如下:
[0010](I)根據節點距離網關的跳數距離把原始網絡拓撲圖中的節點分成不同等級，取消同一等級內各節點之間的邊，得到改進的網絡拓撲圖；這裡網關節點定義為I級節點，其他節點等級依次遞增，離網關節點跳數距離越遠的節點等級越高；
[0011](2)將改進的網絡拓撲圖中起始於同一個節點的所有鏈路構成的鏈路集合作為多播加權衝突圖中的一個頂點；
[0012](3)按照下述方法確定多播加權衝突圖中任意一對頂點之間是否有邊及對應的邊權重，得到最終的多播加權衝突圖:
[0013]a)設多播加權衝突圖中的任意兩個頂點為SJP S」，其對應於改進的網絡拓撲圖中的鏈路集合Ei和Ej,定義頂點Si和Sj彼此互不幹擾所需的最小信道間隔為τ max並初始化為O ;
[0014]b)計算集合Ei中的任意一條鏈路a和集合中的任意一條鏈路b之間的歐式距離d (a, b), d (a, b)定義為鏈路a的任意一個端點與鏈路b的任意一個端點之間的歐式距離的最小值；
[0015]c)將d(a，b)與共信道幹擾範圍R" (O)進行比較，如果d(a，b)≤R" (0)，則轉入下一步驟d);否則轉入步驟f)；
[0016]d)將d(a，b)與對應於不同信道間隔τ的幹擾範圍R" (τ)進行比較，當滿足R" (τ)≤d(a，b)〈R" ( τ-1)條件時，鏈路a與鏈路b彼此互不幹擾所需的最小信道間隔
τ , = τ:
ab，
_ 7] e)當τ ab> τ max條件成立時，更新τ 為τ ab ;
[0018]f)判斷是否遍歷了中的所有鏈路，若是則轉入下一步驟g)，否則轉入步驟b)；
[0019]g)判斷是否遍歷了 Ei中的所有鏈路，若是則轉入下一步驟h)，否則轉入步驟b)；
[0020]h)根據τ max的值進行判斷，若τ _ = O,則多播加權衝突圖中頂點Si和S」之間沒有邊；否則，多播加權衝突圖中頂點Si和S」之間有邊，邊上的權重為τ max ；
[0021]4)通過步驟3)中構建出的多播加權衝突圖與改進的網絡拓撲圖的映射，得到改進的網絡拓撲圖中各鏈路上的權重；改進的網絡拓撲圖中各鏈路上的權重為多播加權衝突圖中與對應於該鏈路的頂點相連的邊上的權重之和；
[0022]5)利用公式(I)計算從各未被覆蓋的多播接收端到網關的各條路徑P的路徑代價
【權利要求】
1.一種無線Mesh網絡多播部分重疊信道分配方法，其特徵在於包括下述步驟: 1)獲取網絡的拓撲信息、多播接收端列表，得到原始網絡拓撲圖； 2)初始化已分配信道的鏈路列表及未被覆蓋的多播接收端列表； 3)根據步驟I)中的原始網絡拓撲圖及多播接收端列表，構建對應的多播加權衝突圖；多播加權衝突圖構建方法如下: (1)根據節點距離網關的跳數距離把原始網絡拓撲圖中的節點分成不同等級，取消同一等級內各節點之間的邊，得到改進的網絡拓撲圖；這裡網關節點定義為I級節點，其他節點等級依次遞增，離網關節點跳數距離越遠的節點等級越高； (2)將改進的網絡拓撲圖中起始於同一個節點的所有鏈路構成的鏈路集合作為多播加權衝突圖中的一個頂點； (3)按照下述方法確定多播加權衝突圖中任意一對頂點之間是否有邊及對應的邊權重，得到最終的多播加權衝突圖: a)設多播加權衝突圖中的任意兩個頂點為SJPSp其對應於改進的網絡拓撲圖中的鏈路集合Ei和Ej,定義頂點Si和Sj彼此互不幹擾所需的最小信道間隔為τ max並初始化為O ; b)計算集合Ei中的任意一條鏈路a和集合中的任意一條鏈路b之間的歐式距離d(a, b), d(a, b)定 義為鏈路a的任意一個端點與鏈路b的任意一個端點之間的歐式距離的最小值； c)將d(a，b)與共信道幹擾範圍R"(O)進行比較，如果d(a，b)≤R" (0)，則轉入下一步驟d);否則轉入步驟f)； d)將d(a，b)與對應於不同信道間隔τ的幹擾範圍R"(τ)進行比較，當滿足R" (τ)≤d(a，b)〈R" ( τ-1)條件時，鏈路a與鏈路b彼此互不幹擾所需的最小信道間隔τ , = τ:ab， e)當τab> τ max條件成立時，更新τ 為Tab; f)判斷是否遍歷了&中的所有鏈路，若是則轉入下一步驟g)，否則轉入步驟b)； g)判斷是否遍歷TEi中的所有鏈路，若是則轉入下一步驟h)，否則轉入步驟b)； h)根據τ_的值進行判斷，若τ_ = 0，則多播加權衝突圖中頂點Si和&之間沒有邊；否則，多播加權衝突圖中頂點Si和S」之間有邊，邊上的權重為τ max ； 4)通過步驟3)中構建出的多播加權衝突圖與改進的網絡拓撲圖的映射，得到改進的網絡拓撲圖中各鏈路上的權重；改進的網絡拓撲圖中各鏈路上的權重為多播加權衝突圖中與對應於該鏈路的頂點相連的邊上的權重之和； 5)利用公式(I)計算從各未被覆蓋的多播接收端到網關的各條路徑P的路徑代價
2.根據權利要求1所述的無線Mesh網絡多播部分重疊信道分配方法，其特徵在於所述步驟7)中為鏈路分配信道過程，包含如下步驟: (1)首先為路徑代價最小的路徑的任一相關鏈路分配信道，並將該鏈路及分配的對應信道添加到已分配信道的鏈路列表； (2)當為某一鏈路s分配信道時，根據公式(2)、(3)、(4)計算預為鏈路s分配信道.1，2，…，11時，鏈路s與網絡中已分配信道的鏈路之間的總幹擾Itrt ；
3.根據權利要求1所述的無線Mesh網絡多播部分重疊信道分配方法，其特徵在於所述步驟7)中為鏈路分配信道過程，包含如下步驟: (1)首先為路徑代價最小的路徑的相關鏈路中距離網關最近的鏈路分配信道，並將該鏈路及分配的對應信道添加到已分配信道的鏈路列表； (2)當為某一鏈路s分配信道時，判斷鏈路s是否有兄弟鏈路，若是則轉入下一步驟(3)，否則轉入步驟(4)； (3)判斷鏈路s的兄弟鏈路是否已經被分配了信道，若是，則將相同信道分配給鏈路S，以利用無線廣播優勢，轉入步驟(6);否則轉入下一步驟(4)； (4)根據公式(2)、(3)、⑷計算預為鏈路s分配信道1，2，…，11時，鏈路s與網絡中已分配信道的鏈路之間的總幹擾Itrt ；
【文檔編號】H04W72/08GK104038946SQ201410323250
【公開日】2014年9月10日 申請日期:2014年7月8日 優先權日:2014年7月8日
【發明者】石文孝, 王繼紅, 崔克強, 金鳳, 許銀龍 申請人:吉林大學