肖偉 王麗文
摘要:無(wú)線Mesh網(wǎng)絡(luò)是具有多跳、自組織、自愈合和高健壯性等特點(diǎn)的寬帶網(wǎng)絡(luò)。因?yàn)榻Y(jié)點(diǎn)信號(hào)之間存在干擾及頻譜資源的有限性,如何通過(guò)頻譜分配來(lái)提升網(wǎng)絡(luò)效率成為Mesh網(wǎng)絡(luò)研究的重要方向。該文給出一種多信道分配算法,目的在于改善無(wú)線mesh網(wǎng)絡(luò)可用信道頻率的綜合效率,基礎(chǔ)在于網(wǎng)絡(luò)結(jié)構(gòu)按拓?fù)溥M(jìn)行結(jié)構(gòu)分層。該算法首先進(jìn)行分層設(shè)計(jì),然后在拓?fù)浞謱拥幕A(chǔ)上根據(jù)信道的優(yōu)先級(jí)分配信道,達(dá)到頻率資源的有效分配的目標(biāo)。仿真實(shí)驗(yàn)說(shuō)明該算法能有效地提高無(wú)線網(wǎng)絡(luò)整體性能。
關(guān)鍵詞:無(wú)線mesh網(wǎng)絡(luò);信道分配;拓?fù)浞謱?/p>
中圖分類(lèi)號(hào):TP393 文獻(xiàn)標(biāo)識(shí)碼:A 文章編號(hào):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
無(wú)線Mesh網(wǎng)絡(luò)[1,2]是一種在無(wú)線局域網(wǎng)的基礎(chǔ)上發(fā)展起來(lái)的,具有自組織、自愈合和高健壯性等優(yōu)點(diǎn)的新型寬帶無(wú)線網(wǎng)絡(luò)結(jié)構(gòu)。無(wú)線 Mesh 網(wǎng)絡(luò)技術(shù)采用多點(diǎn)到多點(diǎn)通信的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu),支持多種類(lèi)型的網(wǎng)絡(luò)接入,被認(rèn)為是未來(lái)無(wú)線通信發(fā)展的關(guān)鍵技術(shù)。
在無(wú)線Mesh網(wǎng)絡(luò)中,頻率通道選擇、功率控制和無(wú)線路由等將直接影響系統(tǒng)設(shè)備的傳輸能力和無(wú)線鏈路質(zhì)量等Qos性能。為了適應(yīng)無(wú)線Mesh網(wǎng)絡(luò)對(duì)傳輸性能的要求,近年來(lái)提出多射頻多信道(Multi-Radio Multi-Channel,MRMC)[3,4]技術(shù)應(yīng)用到無(wú)線 Mesh 網(wǎng)絡(luò)中,形成了多射頻多信道 Mesh 網(wǎng)絡(luò)((Multi-Radio Multi-Channel WMN,MRMC-WMN)[5]。
MRMC-WMN 網(wǎng)絡(luò)具有提升網(wǎng)絡(luò)容量,增強(qiáng)數(shù)據(jù)傳輸可靠性,減輕網(wǎng)絡(luò)的信道干擾等諸多優(yōu)點(diǎn)。在此基礎(chǔ)上,高效的信道分配算法能有效地提高網(wǎng)絡(luò)的吞吐率,增加信道的重用性,優(yōu)化網(wǎng)絡(luò)的通信性能。該文在多射頻和多信道的條件下,基于拓?fù)浞謱蛹靶诺赖膬?yōu)先級(jí)分配通信信道,實(shí)現(xiàn)頻率資源的高效率分配利用。
1 無(wú)線信道分配約束
由于無(wú)線環(huán)境存在的頻道干擾以及相對(duì)有限的資源,無(wú)線網(wǎng)絡(luò)如何分配頻譜資源通常是無(wú)線Mesh網(wǎng)絡(luò)研究的重要方向。為了提高提升網(wǎng)絡(luò)的傳輸性能,通常處理方法是把網(wǎng)絡(luò)各種資源按單個(gè)的資源類(lèi)型來(lái)分配,最后再綜合考慮整體性能,這樣就造成往往難以實(shí)現(xiàn)網(wǎng)絡(luò)資源分配的最優(yōu)化。該文中,我們主要研究Mesh無(wú)線網(wǎng)絡(luò)中信道分配策略,綜合考慮信道優(yōu)先級(jí)、干擾等因素,實(shí)現(xiàn)網(wǎng)絡(luò)資源的最優(yōu)分配。
無(wú)線網(wǎng)絡(luò)中信道的最優(yōu)化分配問(wèn)題是NP-完全問(wèn)題[6],它通常滿足下面約束條件:第一,由于結(jié)點(diǎn)的射頻數(shù)量有限且固定,網(wǎng)絡(luò)的可用信道數(shù)量將固定,每個(gè)結(jié)點(diǎn)可以利用的信道數(shù)目也將受到限制,所以相互通信的兩個(gè)結(jié)點(diǎn)需要使用相同頻率;第二,網(wǎng)絡(luò)中相互通信的結(jié)點(diǎn)間具有信道依賴(lài)性,如果改變通信的頻率,將造成相鄰結(jié)點(diǎn)通信也相應(yīng)發(fā)生頻率變化;第三,信道分配需要考慮網(wǎng)絡(luò)的通信鏈路負(fù)載量,信道分配研究通常假設(shè)鏈路有相同的通信負(fù)載,但是在實(shí)際網(wǎng)絡(luò)中,鏈路的負(fù)載通常是不相同的,例如在網(wǎng)關(guān)結(jié)點(diǎn)的負(fù)載明顯要大些,而分配算法通常以分配更高帶寬的方式來(lái)解決;第四,信道分配通常還需考慮采用的路由分配算法的影響。
2 無(wú)線信道分配研究現(xiàn)狀
在多跳無(wú)線網(wǎng)絡(luò)中,無(wú)線信道的分配研究已取得了不少成果,主要的研究方向包括如下幾個(gè)方面:
1) 集中和分布式分配算法研究。文獻(xiàn)[7]給出了自我穩(wěn)定的信道分配算法,它通過(guò)貪婪法選擇頻道,減少局部目標(biāo)函數(shù)對(duì)分配算法的影響。另外,文獻(xiàn)[8]提出了一種相對(duì)集中式分配算法,在不考慮流量等參數(shù)情況下,只利用局部結(jié)點(diǎn)的互動(dòng)信息實(shí)現(xiàn)信道分配,但是算法執(zhí)行后,對(duì)網(wǎng)絡(luò)性能有影響。
2) 針對(duì)信道干擾研究。文獻(xiàn)[9]給出了DGA算法,它是基于干擾的分配算法,算法先利用Tabu-based算法找到一個(gè)可行的信道分配函數(shù),然后再分配信道。其中MinC算法給出的信道分配算法能適應(yīng)數(shù)據(jù)流量分布的特點(diǎn),但是網(wǎng)絡(luò)的吞吐量將受到影響,最終影響網(wǎng)絡(luò)的綜合性能。endprint
3) 基于拓?fù)浣Y(jié)構(gòu)的算法研究。該算法是目前主要的研究方向,主要目標(biāo)在保證網(wǎng)絡(luò)連通性的同時(shí),合理分配信道。文獻(xiàn)[10]在保證網(wǎng)絡(luò)的連通性和最小的干擾性前提下,給出基于拓?fù)浣Y(jié)構(gòu)的信道分配算法,但是忽略了結(jié)點(diǎn)的優(yōu)先級(jí)及網(wǎng)絡(luò)的流量對(duì)性能的影響。文獻(xiàn)[11,12]提出了網(wǎng)絡(luò)結(jié)構(gòu)與信道分配相互結(jié)合的分配方法,算法從邏輯拓?fù)浣Y(jié)構(gòu)的設(shè)計(jì)來(lái)考慮多信道分配問(wèn)題。
3 基于拓?fù)浞謱拥亩嘈诺婪峙渌惴?/p>
本算法給出的基于拓?fù)浞謱拥亩嘈诺婪峙渌惴?,整體考慮了無(wú)線Mesh網(wǎng)絡(luò)的干擾模型及網(wǎng)絡(luò)連通性。該算法分為二個(gè)主要步驟,第一步實(shí)現(xiàn)對(duì)通信網(wǎng)絡(luò)中結(jié)點(diǎn)層號(hào)的確定,即拓?fù)浞謱?。首先確定Mesh網(wǎng)絡(luò)的第一層,將與Mesh結(jié)點(diǎn)相鄰的結(jié)點(diǎn)都作為第一層,然后在第一層的基礎(chǔ)上按深度優(yōu)先的方法擴(kuò)展,依次為每個(gè)結(jié)點(diǎn)分配層號(hào);第二步在拓?fù)浞謱拥幕A(chǔ)上,給所有的信道初始化優(yōu)先級(jí),然后根據(jù)結(jié)節(jié)的層號(hào)及動(dòng)態(tài)變化的信道優(yōu)先級(jí),確定信道動(dòng)態(tài)分配優(yōu)先級(jí)實(shí)現(xiàn)信道的分配。
3.1 算法使用模型
1) 網(wǎng)絡(luò)模型:無(wú)線mesh網(wǎng)絡(luò)中各結(jié)點(diǎn)構(gòu)成的連接圖是無(wú)向圖G(V, E),Vi表示結(jié)點(diǎn), edge(i,j)表示結(jié)點(diǎn)i和j連通的邊。每個(gè)結(jié)點(diǎn)i有Ri個(gè)無(wú)線射頻接口,如果結(jié)點(diǎn)i和結(jié)點(diǎn)j的各自的射頻接口有一個(gè)相同的信道則可以通信。Gi表示網(wǎng)絡(luò)的第i層結(jié)構(gòu),包含結(jié)點(diǎn)及相應(yīng)連通邊。chan[k]表示在網(wǎng)絡(luò)中有k個(gè)可用信道,K={1,2……k},根據(jù)干擾模型的要求,可以設(shè)定k大于4。
2) 干擾模型:由于無(wú)線信道中的頻率存在信道干擾,干擾模型定義為連接信號(hào)通信會(huì)干擾網(wǎng)絡(luò)中已經(jīng)存在連接信號(hào)的模型。不同文獻(xiàn)提供了許多不同的干擾模型,例如物理和協(xié)議干擾模型等。該文參考TRCA干擾模型,即連續(xù)三跳內(nèi)同一信道的干擾非常大,它和網(wǎng)絡(luò)中的拓?fù)浣Y(jié)構(gòu)有關(guān)。
3.2 算法過(guò)程
1) 結(jié)點(diǎn)分層階段
首先,算法確定鏈路干擾模型??v向干擾和橫向干擾是無(wú)線鏈路最常見(jiàn)的干擾方式,因?yàn)榭v向干擾對(duì)網(wǎng)絡(luò)性能的影響比橫向干擾大,所以網(wǎng)絡(luò)中應(yīng)盡量采用不同的措施減少縱向干擾對(duì)網(wǎng)絡(luò)的影響。因此,算法在對(duì)結(jié)點(diǎn)進(jìn)行分層過(guò)程中,第一步確定與網(wǎng)關(guān)相鄰的結(jié)點(diǎn)為第一層,然后按深度優(yōu)先擴(kuò)展方式依次對(duì)余下的各結(jié)點(diǎn)逐級(jí)進(jìn)行分層處理。
在分層的實(shí)現(xiàn)中,定義邏輯型變量flag_embed作為結(jié)點(diǎn)是否分層標(biāo)志,flag_embed∈{0,1}。由于分層越靠后的結(jié)點(diǎn)離網(wǎng)關(guān)結(jié)點(diǎn)就越遠(yuǎn),當(dāng)某一層結(jié)點(diǎn)數(shù)量過(guò)多時(shí),表明這些結(jié)點(diǎn)構(gòu)成的路徑不是最優(yōu)的,需設(shè)計(jì)一個(gè)變量來(lái)控制某層結(jié)點(diǎn)的數(shù)量。
2) 信道分配階段
本算法在第一階段給出的分層拓?fù)浣Y(jié)構(gòu)基礎(chǔ)上,對(duì)信道進(jìn)行分配。主要使用的是網(wǎng)絡(luò)的干擾模型與流量模型,要求信道分配不出現(xiàn)縱向干擾,盡量避免橫向干擾,采用的模型是TRCA干擾模型;網(wǎng)絡(luò)的流量負(fù)載從網(wǎng)關(guān)結(jié)點(diǎn)開(kāi)始呈樹(shù)狀向四周逐步減少,為了實(shí)現(xiàn)網(wǎng)絡(luò)信道的負(fù)載平衡,算法利用給定的信道優(yōu)先級(jí)來(lái)控制信道的使用次數(shù)。信道最終的分配是依據(jù)信道優(yōu)先級(jí)動(dòng)態(tài)進(jìn)行,其中信道優(yōu)先級(jí)的確定是算法的重點(diǎn)因素,實(shí)現(xiàn)步驟如下:
STEP 1:給信道初始化,賦優(yōu)先值為1。
STEP 2:為G1的各個(gè)結(jié)點(diǎn)Vj分配信道,從擁有最低優(yōu)先級(jí)的信道開(kāi)始,如每個(gè)信道的優(yōu)化值相同時(shí),隨機(jī)選擇信道進(jìn)行分配,每當(dāng)分配完一個(gè)信道,此結(jié)點(diǎn)對(duì)應(yīng)的信道優(yōu)先級(jí)增加1。
STEP 3:為下一層G2的結(jié)點(diǎn)分配信道,同樣選擇從結(jié)點(diǎn)具有的最低優(yōu)先級(jí)開(kāi)始,保證該結(jié)點(diǎn)的直接相連的結(jié)點(diǎn)不使用同一信道,如相同,剛往下移一個(gè),分配完信道優(yōu)先級(jí)增加0.5。在實(shí)現(xiàn)優(yōu)先級(jí)增加以后,算法為同一層中其它結(jié)點(diǎn)分配信道,此時(shí)結(jié)點(diǎn)在分配完一個(gè)信道后,優(yōu)先級(jí)將依次遞減0.1。當(dāng)同層的第二個(gè)結(jié)點(diǎn)分配完信道后,信道優(yōu)先級(jí)減0.2,如此遞減,直到完成這一層所有結(jié)點(diǎn)的信道優(yōu)先級(jí)分配為止,同時(shí)實(shí)現(xiàn)結(jié)點(diǎn)信道的分配。
STEP 4:返回執(zhí)行步驟2和3,實(shí)現(xiàn)每層中所有結(jié)點(diǎn)的信道分配。
4 仿真的實(shí)現(xiàn)及運(yùn)行結(jié)果分析
本算法使用的仿真工具是NS2,結(jié)果分析工具采用gnuplot及gawk。硬件平臺(tái):CPU:Intel 酷睿i5 4690, 1.60MHz,內(nèi)存:4GM,Window 7。圖1,圖2分別考慮了在4個(gè)可用信道和10個(gè)可用信道下公共信道分配(CCA)方案[10]和本算法吞吐量的比較情況。MAC層采用RTS/CTS機(jī)制,數(shù)據(jù)包的大小為1KB,傳輸速率為2Mbps。每個(gè)結(jié)點(diǎn)都有4個(gè)射頻端口。仿真結(jié)果如下圖:
5 結(jié)論
與其它的算法相比較,該文提出的算法從拓?fù)浣Y(jié)構(gòu)分層,干擾模型,流量特點(diǎn)及信道優(yōu)先級(jí)等多方面綜合考慮,提高了整個(gè)網(wǎng)絡(luò)的吞吐量。仿真可以看出,當(dāng)信道的數(shù)量的增加時(shí),更能體現(xiàn)本算法的特點(diǎn)。另外,無(wú)線網(wǎng)絡(luò)路由算法也是影響信道分配效率的重要因素,本算法沒(méi)有充分考慮其作用,這是本算法繼續(xù)提升和改進(jìn)的地方。
參考文獻(xiàn):
[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] 張勇,郭達(dá).無(wú)線網(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頁(yè))
(上接第6841頁(yè))
[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] 張勇,郭達(dá).無(wú)線網(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頁(yè))
(上接第6841頁(yè))
[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] 張勇,郭達(dá).無(wú)線網(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頁(yè))
(上接第6841頁(yè))
[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