無線mesh網(wǎng)絡(luò)中基于拓撲分層的多信道分配算法研究

肖偉　王麗文

摘要：無線Mesh網(wǎng)絡(luò)是具有多跳、自組織、自愈合和高健壯性等特點的寬帶網(wǎng)絡(luò)。因為結(jié)點信號之間存在干擾及頻譜資源的有限性，如何通過頻譜分配來提升網(wǎng)絡(luò)效率成為Mesh網(wǎng)絡(luò)研究的重要方向。該文給出一種多信道分配算法，目的在于改善無線mesh網(wǎng)絡(luò)可用信道頻率的綜合效率，基礎(chǔ)在于網(wǎng)絡(luò)結(jié)構(gòu)按拓撲進行結(jié)構(gòu)分層。該算法首先進行分層設(shè)計，然后在拓撲分層的基礎(chǔ)上根據(jù)信道的優(yōu)先級分配信道，達到頻率資源的有效分配的目標。仿真實驗說明該算法能有效地提高無線網(wǎng)絡(luò)整體性能。

關(guān)鍵詞：無線mesh網(wǎng)絡(luò)；信道分配；拓撲分層

中圖分類號：TP393 文獻標識碼：A 文章編號：1009-3044（2014）29-6839-03

Abstract： Wireless Mesh Network is the broadband wireless Networks with multi-hop， self-organization， self-healing， high robustness and other characteristics. Due to the limited spectrum resources and the signal transmission between nodes interfere with each other， how to distibute spectrum scope and increase the transmission performance becomes an important orientation in the Mesh network. for increasing the combined efficiency in wireless mesh network based on the available channels frequency utilization， this paper presents a novel algorithm based on topology hierarchy. Firstly， this algorithm realize the hierarchical topology， and then layered on the basis of the topology depend on the priority of the channels to assign channels. Simulation consequence indicates that the whole performance in Mesh networks would be improved using the algorithm.

Key words： wireless mesh networks； channel assignment； topology hierarchical

無線Mesh網(wǎng)絡(luò)[1，2]是一種在無線局域網(wǎng)的基礎(chǔ)上發(fā)展起來的，具有自組織、自愈合和高健壯性等優(yōu)點的新型寬帶無線網(wǎng)絡(luò)結(jié)構(gòu)。無線 Mesh 網(wǎng)絡(luò)技術(shù)采用多點到多點通信的網(wǎng)絡(luò)拓撲結(jié)構(gòu)，支持多種類型的網(wǎng)絡(luò)接入，被認為是未來無線通信發(fā)展的關(guān)鍵技術(shù)。

在無線Mesh網(wǎng)絡(luò)中，頻率通道選擇、功率控制和無線路由等將直接影響系統(tǒng)設(shè)備的傳輸能力和無線鏈路質(zhì)量等Qos性能。為了適應(yīng)無線Mesh網(wǎng)絡(luò)對傳輸性能的要求，近年來提出多射頻多信道（Multi-Radio Multi-Channel，MRMC）[3，4]技術(shù)應(yīng)用到無線 Mesh 網(wǎng)絡(luò)中，形成了多射頻多信道 Mesh 網(wǎng)絡(luò)（（Multi-Radio Multi-Channel WMN，MRMC-WMN）[5]。

MRMC-WMN 網(wǎng)絡(luò)具有提升網(wǎng)絡(luò)容量，增強數(shù)據(jù)傳輸可靠性，減輕網(wǎng)絡(luò)的信道干擾等諸多優(yōu)點。在此基礎(chǔ)上，高效的信道分配算法能有效地提高網(wǎng)絡(luò)的吞吐率，增加信道的重用性，優(yōu)化網(wǎng)絡(luò)的通信性能。該文在多射頻和多信道的條件下，基于拓撲分層及信道的優(yōu)先級分配通信信道，實現(xiàn)頻率資源的高效率分配利用。

1 無線信道分配約束

由于無線環(huán)境存在的頻道干擾以及相對有限的資源，無線網(wǎng)絡(luò)如何分配頻譜資源通常是無線Mesh網(wǎng)絡(luò)研究的重要方向。為了提高提升網(wǎng)絡(luò)的傳輸性能，通常處理方法是把網(wǎng)絡(luò)各種資源按單個的資源類型來分配，最后再綜合考慮整體性能，這樣就造成往往難以實現(xiàn)網(wǎng)絡(luò)資源分配的最優(yōu)化。該文中，我們主要研究Mesh無線網(wǎng)絡(luò)中信道分配策略，綜合考慮信道優(yōu)先級、干擾等因素，實現(xiàn)網(wǎng)絡(luò)資源的最優(yōu)分配。

無線網(wǎng)絡(luò)中信道的最優(yōu)化分配問題是NP-完全問題[6]，它通常滿足下面約束條件：第一，由于結(jié)點的射頻數(shù)量有限且固定，網(wǎng)絡(luò)的可用信道數(shù)量將固定，每個結(jié)點可以利用的信道數(shù)目也將受到限制，所以相互通信的兩個結(jié)點需要使用相同頻率；第二，網(wǎng)絡(luò)中相互通信的結(jié)點間具有信道依賴性，如果改變通信的頻率，將造成相鄰結(jié)點通信也相應(yīng)發(fā)生頻率變化；第三，信道分配需要考慮網(wǎng)絡(luò)的通信鏈路負載量，信道分配研究通常假設(shè)鏈路有相同的通信負載，但是在實際網(wǎng)絡(luò)中，鏈路的負載通常是不相同的，例如在網(wǎng)關(guān)結(jié)點的負載明顯要大些，而分配算法通常以分配更高帶寬的方式來解決；第四，信道分配通常還需考慮采用的路由分配算法的影響。

2 無線信道分配研究現(xiàn)狀

在多跳無線網(wǎng)絡(luò)中，無線信道的分配研究已取得了不少成果，主要的研究方向包括如下幾個方面：

1） 集中和分布式分配算法研究。文獻[7]給出了自我穩(wěn)定的信道分配算法，它通過貪婪法選擇頻道，減少局部目標函數(shù)對分配算法的影響。另外，文獻[8]提出了一種相對集中式分配算法，在不考慮流量等參數(shù)情況下，只利用局部結(jié)點的互動信息實現(xiàn)信道分配，但是算法執(zhí)行后，對網(wǎng)絡(luò)性能有影響。

2） 針對信道干擾研究。文獻[9]給出了DGA算法，它是基于干擾的分配算法，算法先利用Tabu-based算法找到一個可行的信道分配函數(shù)，然后再分配信道。其中MinC算法給出的信道分配算法能適應(yīng)數(shù)據(jù)流量分布的特點，但是網(wǎng)絡(luò)的吞吐量將受到影響，最終影響網(wǎng)絡(luò)的綜合性能。endprint

3） 基于拓撲結(jié)構(gòu)的算法研究。該算法是目前主要的研究方向，主要目標在保證網(wǎng)絡(luò)連通性的同時，合理分配信道。文獻[10]在保證網(wǎng)絡(luò)的連通性和最小的干擾性前提下，給出基于拓撲結(jié)構(gòu)的信道分配算法，但是忽略了結(jié)點的優(yōu)先級及網(wǎng)絡(luò)的流量對性能的影響。文獻[11，12]提出了網(wǎng)絡(luò)結(jié)構(gòu)與信道分配相互結(jié)合的分配方法，算法從邏輯拓撲結(jié)構(gòu)的設(shè)計來考慮多信道分配問題。

3 基于拓撲分層的多信道分配算法

本算法給出的基于拓撲分層的多信道分配算法，整體考慮了無線Mesh網(wǎng)絡(luò)的干擾模型及網(wǎng)絡(luò)連通性。該算法分為二個主要步驟，第一步實現(xiàn)對通信網(wǎng)絡(luò)中結(jié)點層號的確定，即拓撲分層。首先確定Mesh網(wǎng)絡(luò)的第一層，將與Mesh結(jié)點相鄰的結(jié)點都作為第一層，然后在第一層的基礎(chǔ)上按深度優(yōu)先的方法擴展，依次為每個結(jié)點分配層號；第二步在拓撲分層的基礎(chǔ)上，給所有的信道初始化優(yōu)先級，然后根據(jù)結(jié)節(jié)的層號及動態(tài)變化的信道優(yōu)先級，確定信道動態(tài)分配優(yōu)先級實現(xiàn)信道的分配。

3.1 算法使用模型

1） 網(wǎng)絡(luò)模型：無線mesh網(wǎng)絡(luò)中各結(jié)點構(gòu)成的連接圖是無向圖G（V， E），Vi表示結(jié)點， edge（i，j）表示結(jié)點i和j連通的邊。每個結(jié)點i有Ri個無線射頻接口，如果結(jié)點i和結(jié)點j的各自的射頻接口有一個相同的信道則可以通信。Gi表示網(wǎng)絡(luò)的第i層結(jié)構(gòu)，包含結(jié)點及相應(yīng)連通邊。chan[k]表示在網(wǎng)絡(luò)中有k個可用信道，K={1，2……k}，根據(jù)干擾模型的要求，可以設(shè)定k大于4。

2） 干擾模型：由于無線信道中的頻率存在信道干擾，干擾模型定義為連接信號通信會干擾網(wǎng)絡(luò)中已經(jīng)存在連接信號的模型。不同文獻提供了許多不同的干擾模型，例如物理和協(xié)議干擾模型等。該文參考TRCA干擾模型，即連續(xù)三跳內(nèi)同一信道的干擾非常大，它和網(wǎng)絡(luò)中的拓撲結(jié)構(gòu)有關(guān)。

3.2 算法過程

1） 結(jié)點分層階段

首先，算法確定鏈路干擾模型?？v向干擾和橫向干擾是無線鏈路最常見的干擾方式，因為縱向干擾對網(wǎng)絡(luò)性能的影響比橫向干擾大，所以網(wǎng)絡(luò)中應(yīng)盡量采用不同的措施減少縱向干擾對網(wǎng)絡(luò)的影響。因此，算法在對結(jié)點進行分層過程中，第一步確定與網(wǎng)關(guān)相鄰的結(jié)點為第一層，然后按深度優(yōu)先擴展方式依次對余下的各結(jié)點逐級進行分層處理。

在分層的實現(xiàn)中，定義邏輯型變量flag_embed作為結(jié)點是否分層標志，flag_embed∈{0，1}。由于分層越靠后的結(jié)點離網(wǎng)關(guān)結(jié)點就越遠，當某一層結(jié)點數(shù)量過多時，表明這些結(jié)點構(gòu)成的路徑不是最優(yōu)的，需設(shè)計一個變量來控制某層結(jié)點的數(shù)量。

2） 信道分配階段

本算法在第一階段給出的分層拓撲結(jié)構(gòu)基礎(chǔ)上，對信道進行分配。主要使用的是網(wǎng)絡(luò)的干擾模型與流量模型，要求信道分配不出現(xiàn)縱向干擾，盡量避免橫向干擾，采用的模型是TRCA干擾模型；網(wǎng)絡(luò)的流量負載從網(wǎng)關(guān)結(jié)點開始呈樹狀向四周逐步減少，為了實現(xiàn)網(wǎng)絡(luò)信道的負載平衡，算法利用給定的信道優(yōu)先級來控制信道的使用次數(shù)。信道最終的分配是依據(jù)信道優(yōu)先級動態(tài)進行，其中信道優(yōu)先級的確定是算法的重點因素，實現(xiàn)步驟如下：

STEP 1：給信道初始化，賦優(yōu)先值為1。

STEP 2：為G1的各個結(jié)點Vj分配信道，從擁有最低優(yōu)先級的信道開始，如每個信道的優(yōu)化值相同時，隨機選擇信道進行分配，每當分配完一個信道，此結(jié)點對應(yīng)的信道優(yōu)先級增加1。

STEP 3：為下一層G2的結(jié)點分配信道，同樣選擇從結(jié)點具有的最低優(yōu)先級開始，保證該結(jié)點的直接相連的結(jié)點不使用同一信道，如相同，剛往下移一個，分配完信道優(yōu)先級增加0.5。在實現(xiàn)優(yōu)先級增加以后，算法為同一層中其它結(jié)點分配信道，此時結(jié)點在分配完一個信道后，優(yōu)先級將依次遞減0.1。當同層的第二個結(jié)點分配完信道后，信道優(yōu)先級減0.2，如此遞減，直到完成這一層所有結(jié)點的信道優(yōu)先級分配為止，同時實現(xiàn)結(jié)點信道的分配。

STEP 4：返回執(zhí)行步驟2和3，實現(xiàn)每層中所有結(jié)點的信道分配。

4 仿真的實現(xiàn)及運行結(jié)果分析

本算法使用的仿真工具是NS2，結(jié)果分析工具采用gnuplot及gawk。硬件平臺：CPU：Intel 酷睿i5 4690， 1.60MHz，內(nèi)存：4GM，Window 7。圖1，圖2分別考慮了在4個可用信道和10個可用信道下公共信道分配（CCA）方案[10]和本算法吞吐量的比較情況。MAC層采用RTS/CTS機制，數(shù)據(jù)包的大小為1KB，傳輸速率為2Mbps。每個結(jié)點都有4個射頻端口。仿真結(jié)果如下圖：

5 結(jié)論

與其它的算法相比較，該文提出的算法從拓撲結(jié)構(gòu)分層，干擾模型，流量特點及信道優(yōu)先級等多方面綜合考慮，提高了整個網(wǎng)絡(luò)的吞吐量。仿真可以看出，當信道的數(shù)量的增加時，更能體現(xiàn)本算法的特點。另外，無線網(wǎng)絡(luò)路由算法也是影響信道分配效率的重要因素，本算法沒有充分考慮其作用，這是本算法繼續(xù)提升和改進的地方。

參考文獻：

[1] Ian F. Akyildiz， XudongWang， andWeilin Wang. Wireless mesh networks： a survey.

[2] Akyildiz I F， Wang Xudong， Wang Weilin. Wireless mesh networks： a survey[J]. Computer Networks and ISDN Systems， 2005，47（4）：445-487.

[3] So J， Vaidya N. Multi-channel MAC for ad hoc networks： handling multi-channel hidden terminals using a single transceiver[C]. ACM International Symposium on Mobile Ad Hoc Networking and Computing， 2004：222—233.endprint

[4] Adya A， Bahl P， Padhye J， et al. A multi-radio unication protocol for IEEE 802.11 wireless networks[C]. International Conferences on Broadband Networks， 2004：344-354.

[5] Hong X，Gu B，Hoque M，et al.Exploring multiple radios and multiple channels in wireless mesh networks[J]. IEEE Wireless Communications，2010，17（3）：76-85.

[6] 張勇，郭達.無線網(wǎng)狀網(wǎng)原理與技術(shù)[M].北京：電子工業(yè)出版社，2007.

[7] Bong-Jun Ko，Vishal Misra，Jitendra Padhye，Dan Rubenstein Distributed Channel Assignment in Multi-Radio 802.11 Mesh Networks Comput. Netw. ISDN Syst.，2005，47（4）.

[8] Krishna N. Ramachandran， Elizabeth M. Belding-Royer， Kevin C. Interference-aware channel assignment in multi-radio wireless mesh networks. In IEEE Infocom'06.

[9] Gupta P，Kumar P R. The Capacity of Wireless Networks.IEEE Transactions on Information Theory，2000，46（2）. （下轉(zhuǎn)第6845頁）

（上接第6841頁）

[10] Anand Prabhu Subramanian，Himanshu gupta， Samir R.Das Minimum Interference Channel Assignment inMulti-Radio Wireless Mesh Networks

[7] AVALLONE S， AKYILDIZ IF. A channel assignmentalgorithm for multi-radiowirelessmesh networks[J].Computer Communications，2008，31（7）：1343-1353.

[8] Raniwala A， Chiueh T C.Architecture and algorithm for an IEEE-based multi-channel wireless mesh network.Proc of IEEE Info-com.March 2005

[9] Mohsenian-Rad A H and Wong V W S. Joint logical topology design， interface assignment， channel allocation， and routing for multi-channel wireless mesh networks. IEEE Transactions on Wireless Communications，2007，6（12）：4432-4440.

[10] Jain K， Padhye J， Padmanabhan V N， et al. Impact of Interference on Multi-hop Wireless Network Performance. InMOBICOM， 2003.

[11] http：//www.cse.msu.edu/wangbo1/ns2/nshowto8.html

[12] Kodialam M， Nandagopal T. Characterizing the CapacityRegion in Multi-Radio.Multi-Channel Wireless Mesh Networks.In MOBICOM， 2005.endprint

[4] Adya A， Bahl P， Padhye J， et al. A multi-radio unication protocol for IEEE 802.11 wireless networks[C]. International Conferences on Broadband Networks， 2004：344-354.

[5] Hong X，Gu B，Hoque M，et al.Exploring multiple radios and multiple channels in wireless mesh networks[J]. IEEE Wireless Communications，2010，17（3）：76-85.

[6] 張勇，郭達.無線網(wǎng)狀網(wǎng)原理與技術(shù)[M].北京：電子工業(yè)出版社，2007.

[7] Bong-Jun Ko，Vishal Misra，Jitendra Padhye，Dan Rubenstein Distributed Channel Assignment in Multi-Radio 802.11 Mesh Networks Comput. Netw. ISDN Syst.，2005，47（4）.

[8] Krishna N. Ramachandran， Elizabeth M. Belding-Royer， Kevin C. Interference-aware channel assignment in multi-radio wireless mesh networks. In IEEE Infocom'06.

[9] Gupta P，Kumar P R. The Capacity of Wireless Networks.IEEE Transactions on Information Theory，2000，46（2）. （下轉(zhuǎn)第6845頁）

（上接第6841頁）

[10] Anand Prabhu Subramanian，Himanshu gupta， Samir R.Das Minimum Interference Channel Assignment inMulti-Radio Wireless Mesh Networks

[7] AVALLONE S， AKYILDIZ IF. A channel assignmentalgorithm for multi-radiowirelessmesh networks[J].Computer Communications，2008，31（7）：1343-1353.

[8] Raniwala A， Chiueh T C.Architecture and algorithm for an IEEE-based multi-channel wireless mesh network.Proc of IEEE Info-com.March 2005

[9] Mohsenian-Rad A H and Wong V W S. Joint logical topology design， interface assignment， channel allocation， and routing for multi-channel wireless mesh networks. IEEE Transactions on Wireless Communications，2007，6（12）：4432-4440.

[10] Jain K， Padhye J， Padmanabhan V N， et al. Impact of Interference on Multi-hop Wireless Network Performance. InMOBICOM， 2003.

[11] http：//www.cse.msu.edu/wangbo1/ns2/nshowto8.html

[12] Kodialam M， Nandagopal T. Characterizing the CapacityRegion in Multi-Radio.Multi-Channel Wireless Mesh Networks.In MOBICOM， 2005.endprint

[4] Adya A， Bahl P， Padhye J， et al. A multi-radio unication protocol for IEEE 802.11 wireless networks[C]. International Conferences on Broadband Networks， 2004：344-354.

[5] Hong X，Gu B，Hoque M，et al.Exploring multiple radios and multiple channels in wireless mesh networks[J]. IEEE Wireless Communications，2010，17（3）：76-85.

[6] 張勇，郭達.無線網(wǎng)狀網(wǎng)原理與技術(shù)[M].北京：電子工業(yè)出版社，2007.

[7] Bong-Jun Ko，Vishal Misra，Jitendra Padhye，Dan Rubenstein Distributed Channel Assignment in Multi-Radio 802.11 Mesh Networks Comput. Netw. ISDN Syst.，2005，47（4）.

[8] Krishna N. Ramachandran， Elizabeth M. Belding-Royer， Kevin C. Interference-aware channel assignment in multi-radio wireless mesh networks. In IEEE Infocom'06.

[9] Gupta P，Kumar P R. The Capacity of Wireless Networks.IEEE Transactions on Information Theory，2000，46（2）. （下轉(zhuǎn)第6845頁）

（上接第6841頁）

[10] Anand Prabhu Subramanian，Himanshu gupta， Samir R.Das Minimum Interference Channel Assignment inMulti-Radio Wireless Mesh Networks

[7] AVALLONE S， AKYILDIZ IF. A channel assignmentalgorithm for multi-radiowirelessmesh networks[J].Computer Communications，2008，31（7）：1343-1353.

[8] Raniwala A， Chiueh T C.Architecture and algorithm for an IEEE-based multi-channel wireless mesh network.Proc of IEEE Info-com.March 2005

[9] Mohsenian-Rad A H and Wong V W S. Joint logical topology design， interface assignment， channel allocation， and routing for multi-channel wireless mesh networks. IEEE Transactions on Wireless Communications，2007，6（12）：4432-4440.

[10] Jain K， Padhye J， Padmanabhan V N， et al. Impact of Interference on Multi-hop Wireless Network Performance. InMOBICOM， 2003.

[11] http：//www.cse.msu.edu/wangbo1/ns2/nshowto8.html

[12] Kodialam M， Nandagopal T. Characterizing the CapacityRegion in Multi-Radio.Multi-Channel Wireless Mesh Networks.In MOBICOM， 2005.endprint