[發明專利]一種用于多信道無線網絡的鏈路分配方法

無效

• 申請號: 201110241522.7
• 申請日: 2011-08-22
• 公開（公告）號: CN102256362A
• 公開（公告）日: 2011-11-23
• 發明（設計）人: 余旭濤;徐進
• 申請（專利權）人: 東南大學;南京浩博科技有限公司
• 主分類號: H04W72/04
• 分類號: H04W72/04
• 代理公司: 南京蘇高專利商標事務所(普通合伙) 32204
• 代理人: 柏尚春

技術領域

本發明涉及無線通信和信息傳播技術，尤其涉及一種用于多信道無線網絡的鏈路分配方法。

背景技術

單信道無線網絡中存在的一個主要問題就是多個節點同時傳輸時，彼此間的干擾帶來的容量降低的問題。針對該問題，可以采用多信道無線網絡。在多信道無線網絡中，節點可以通過無線網絡接口卡工作在不同的信道上，使得鏈路可以同時進行數據包的傳輸。由于節點可用的無線網絡接口卡以及可分配的信道數目受限，因此存在如何將鏈路分配到不同的信道，以降低網絡干擾、增加網絡容量的問題。

目前節點將鏈路分配到不同的信道主要有以下幾種方法：

1、節點按一定的規律在不同的信道間切換：如SSCH(Slotted?Seeded?Channel?Hopping)協議，每個節點可配備一個無線網卡，將時間劃分為多個時隙，每個時隙按照已設定的信道序列進行切換，采用該方法，網絡中各個節點需要知道其相鄰節點的信道跳變序列，與其通信時，將網卡工作在對應信道；

2、節點采用專門的控制信道，通過控制信道協商各個鏈路傳輸數據包所采用的信道：如DCA(Dynamic?Channel?Allocation)協議，該協議將信道分為控制信道和數據信道，節點配備多個無線網卡，一個網卡工作于控制信道用于交換控制信息協商信道，其余可以在多個數據信道間切換用于鏈路傳送數據包和應答包；

3、從最優化網絡某項性能指標(如網絡容量、公平性等)的角度考慮，利用線性規劃或者非線性規劃的方法，為鏈路分配對應的無線網卡以及信道：如Mansoor?Alicherry等人提出的方法，以最大化無線Mesh網絡客戶端網絡容量為目標建模，在線性規劃基礎上，進行信道分配。

發明內容

發明目的：為了克服現有技術中存在的不足，本發明提供一種用于多信道無線網絡的鏈路分配方法，將多信道無線網絡的鏈路分配到各信道，使得網絡中的鏈路可以工作在不同的信道上。

技術方案：為實現上述目的，本發明采用的技術方案為：

一種用于多信道無線網絡的鏈路分配方法，包括如下步驟：

(1)根據多信道無線網絡可用的信道數目m，將該無線網絡劃分為與可用信道數目相同的m個子網；

(2)根據上述多信道無線網絡的拓撲圖獲得網絡沖突圖G；

(3)根據步驟(2)中獲得的網絡沖突圖G，得到上述網絡的最大獨立集序列I，最大獨立集序列I內的最大獨立集的數目為n；

(4)將步驟(3)中得到的最大獨立集序列I分配到步驟(1)中劃分的各個子網；

其中，m、n為自然數。

所述步驟(1)中，可用的信道與劃分得到的子網一一對應。

所述步驟(2)中，網絡沖突圖G通過以下方式得到：

在多信道無線網絡拓撲圖中的節點用頂點表示，鏈路用邊表示；在網絡沖突圖G中，多信道無線網絡拓撲圖中的鏈路用頂點表示，如果在單信道下，兩條鏈路間存在沖突關系，則相應頂點間會存在一條邊。所述步驟(2)中，只需要將多信道網絡拓撲圖中的邊轉換為網絡沖突圖G中的頂點，然后將有沖突關系的頂點用邊連接，就可以得到網絡沖突圖G。

所述步驟(3)具體包括如下步驟：

(3.1)初始化，設最大獨立集序列I為空集，計數值i＝0，其中i為自然數；

(3.2)根據網絡沖突圖G，獲得該網絡沖突圖G的最大獨立集，將該最大獨立集添加到最大獨立集序列I，記為I_i；

(3.3)從網絡沖突圖G中去掉步驟(3.2)中獲得的最大獨立集I_i中所包含的頂點以及與這些頂點的相連邊，得到新的網絡沖突圖G；

(3.4)判斷步驟(3.3)中得到的網絡沖突圖G是否為空圖，如果判斷結果為否，則i＝i+1，返回步驟(3.2)；

(3.5)如果步驟(3.4)的判斷結果為是，停止計算，n＝i+1，得到最大獨立集序列I。

在步驟3中，如果網絡沖突圖G中同時存在多個最大獨立集，則取獨立集中所有頂點度數之和最小的最大獨立集作為該網絡沖突圖G對應的最大獨立集；如果同時存在多個頂點度數之和相等的最大獨立集，則從中任意選擇一個作為最大獨立集。這里一個頂點的度數指的是與這個頂點相連的邊的數目。

所述步驟(4)中，首先比較m和n的大小，若m≥n，則從m個子網中任意選出n個子網，將n個最大獨立集任意分配到選出的n個子網上，且每個子網內有且僅有一個最大獨立集；若m＜n，則將n個最大獨立集合并成m個集，然后將合并后的m個集任意分配到m子網上，且每個子網內有且僅有一個集。