多射频多信道无线Mesh网络的跨层设计
|
摘要
无线Mesh网络作为一种新型无线宽带接入技术,融合了无线局域网和Ad Hoc网络的优势,具有自组网、自修复、多跳级联、节点自我管理等智能优势以及移动宽带、无线定位等特点,并成为无线宽带接入的一种有效手段。近年来,使用多射频多信道技术来提高无线Mesh网络的可用带宽成为学术界普遍关注的焦点。多射频多信道技术是指网络中节点配有多个无线网络接口卡(NIC),并且整个网络中使用不止有一个可用信道。但是由于网络中,无线网络接口卡和信道的数量限制,使得多射频多信道无线Mesh网络中的路由和信道分配问题成为一种NP-Hard问题。
本文在介绍多射频多信道无线Mesh网络基本特点、框架、应用及跨层设计思想的前提下,提出了一种对多射频多信道无线Mesh网络的跨层设计,该设计重点关注于该网络下的路由和信道分配相结合的问题。在路由选择方面,我们使用加权累积期望传输时间作为路由度量,该度量跨层的考虑了物理层信道多样性的问题,在运用路由度量进行路由选择方面,本文提出一种使用模拟退火方法的优化算法,在网络中寻找最佳的路由方案。并为该路由中的每个链路设计出信道分配的方法,从而增大网络吞吐量,减少网络延迟。
Wireless Mesh Network is a new kind of Wireless Broadband Access Network. Wireless Mesh Network has the advantages of both WLAN and Ad Hoc networks that it is self-organized, self-healed, multi-hop and with self-managed nodes, mobile bandwidth and wireless localization. These advantages make Wireless Mesh Network become an efficient solution for wireless broadband access. Recently, more and more researchers are working on using multi-radio multi-channel technology in wireless mesh networks to improve network throughput. In multi-radio multi-channel technology, nodes in the network are equipped by multi-NICs (Network Interface Card), and there are more than one channels in the network. But for the limitation of the number of NIC and the channel, the routing and channel assignment in Wireless Mesh Network is a NP-hard problem.
Based on the introduction of basic characters, architecture, application of multi-radio multi-channel Wireless Mesh Networks and the concept of cross-layer design, this paper proposes a cross-layer design in multi-radio multi-channel Wireless Mesh Network, focusing on joint routing and channel assignment. We use weighted cumulative expected transmission time as the routing metric which considers the channel diversity in the physic layer. On routing by this metric, we propose a heuristic algorithm using Simulated Annealing to find the optimal routing solution. Then, by the proposed channel assignment algorithm, we assign channels for the links on the path. Our final goal is to maximize the network throughput and minimize the network delay.
本文在介绍多射频多信道无线Mesh网络基本特点、框架、应用及跨层设计思想的前提下,提出了一种对多射频多信道无线Mesh网络的跨层设计,该设计重点关注于该网络下的路由和信道分配相结合的问题。在路由选择方面,我们使用加权累积期望传输时间作为路由度量,该度量跨层的考虑了物理层信道多样性的问题,在运用路由度量进行路由选择方面,本文提出一种使用模拟退火方法的优化算法,在网络中寻找最佳的路由方案。并为该路由中的每个链路设计出信道分配的方法,从而增大网络吞吐量,减少网络延迟。
Wireless Mesh Network is a new kind of Wireless Broadband Access Network. Wireless Mesh Network has the advantages of both WLAN and Ad Hoc networks that it is self-organized, self-healed, multi-hop and with self-managed nodes, mobile bandwidth and wireless localization. These advantages make Wireless Mesh Network become an efficient solution for wireless broadband access. Recently, more and more researchers are working on using multi-radio multi-channel technology in wireless mesh networks to improve network throughput. In multi-radio multi-channel technology, nodes in the network are equipped by multi-NICs (Network Interface Card), and there are more than one channels in the network. But for the limitation of the number of NIC and the channel, the routing and channel assignment in Wireless Mesh Network is a NP-hard problem.
Based on the introduction of basic characters, architecture, application of multi-radio multi-channel Wireless Mesh Networks and the concept of cross-layer design, this paper proposes a cross-layer design in multi-radio multi-channel Wireless Mesh Network, focusing on joint routing and channel assignment. We use weighted cumulative expected transmission time as the routing metric which considers the channel diversity in the physic layer. On routing by this metric, we propose a heuristic algorithm using Simulated Annealing to find the optimal routing solution. Then, by the proposed channel assignment algorithm, we assign channels for the links on the path. Our final goal is to maximize the network throughput and minimize the network delay.
引文
[1]I. Akyildiz, X. Wang, and W. Wang, "Wireless Mesh Network:A Survey," Comp. Networks, vol.47, no.47,2005, pp.445-87.
[2]X. Wang, W. Wang, and M. Nova, "A High Performance Single-Channel IEEE 802.11 MAC with Distributed TDMA," Tech. rep., Kiyon, Inc. (submitted for patent application), Oct.2004
[3]J.So and N. Vaidya, "Multi-channel MAC for Ad Hoc Networks:Handling Multi-channel Hidden Terminals using a Single Transceiver," Proc. ACM Mobihoc, 2004, pp.222-33
[4]P. Bahl, R. Chandra and J. Dunagan, "SSCH:Slotted Seeded Channel Hopping for Capacity Improvement in IEEE 802.11 Ad-Hoc Wireless Networks," Proc. ACM Mobicom,2004, pp.216-30
[5]Ching-Ju Lin, Sung-Han Lin and Cheng-Fu Chou, "Performance Study of Optimal Routing and Channel Assignment in Wireless Mesh Networks," GLOBECOM'07. IEEE Nov.2007 Page(s):4818-4822
[6]http://labs.chinamobile.com/mblog/122_5025
[7]Whitehead P., "Mesh networks; a new architecture for broadband wireless accesssystems," Radio and Wireless Conference,2000. RAWCON 2000.2000 IEEE, Volume, Issue,2000 Page(s):43-46
[8]陈琳琳,刘乃安.无线Mesh网络与IEEE802系列标准.中兴通信技术,2008年14卷第2期.
[9]孙伟峰.基于802.11无线—结合网络的QoS研究.合肥：中国科技大学,2007.
[10]W. Steven Conner, Jan Kruys, Kyeongsoo (Joseph) Kim, Juan Carlos Zuniga, "IEEE 802.11s Tutorial", November 2006
[11]方旭明,戚彩霞,向征.IEEE 802系列无线网络网状组网与移动切换技术综述.计算机应用,2006,26(8)：1756-1761.
[12]董晓鲁,党梅梅,沈嘉等.WiMAX技术、标准与应用.人民邮电出版社,2007
[13]IEEE802.20Standard Group WebSite. http://www.ieee802.org/20/.
[14]焦健.高速移动数据传输新标准IEEE802.20及其切换策略研究.北京：北京交通大学,2006.
[15]W. Xiang, T. Pratt, X. Wang, "A software radio testbed for two-transmitter two-receiver space time coding wireless LAN," IEEE Communications Magazine 42(6)(2004) S20-S28
[16]K. Sundaresan, R. Sivakumar, M. A. Ingram, T.-Y. Chang, "A fair medium access control protocol for ad-hoc networks with MIMO links," IEEE Annual Conference on Computer Communications (INFOCOM),2004, pp.2559-2570
[17]A. Adya, P. Bahl, J. Padhye, A. Wolman, L. Zhou, "A multi-radio unification protocol for IEEE 802.11 wireless networks," International Conference on Broadband Networks (BroadNets),2004
[18]R. Drave, J. Padhye, and B. Zill, "Routing in Multi-Radio, Multi-Hop Wireless Mesh Networks," ACM MobiCom, Sept.2004, pp.114-28.
[19]方旭明,马建忠,“无线Mesh网络跨层设计”,《数据通信》2005年第4期
[20]David B Johnson and David A Maltz, "Dynamic Source Routing in Ad Hoc Wireless Networks," in Mobile Computing.1996, vol.353, Kluwer Academic Publishers.
[21]Charles Perkins, "Ad-hoc on-demand distance vector routing," In MILCOM panel on Ad Hoc Networks,1997.
[22]Charles Perkins and Pravin Bhagwat, "Highly dynamic destinationsequenced distance-vector routing (DSDV) for mobile computers," In ACM SIGCOMM,1994.
[23]Tsu-Wei Chen and Mario Gerla, "Global State Routing:A New Routing Schemes for Ad-hoc Wireless Networks," in IEEE ICC,1998.
[24]Douglas S. J. De Couto, Daniel Aguayo, John Bicket, and Robert Morris, "A High-Throughput Path Metric for Multi-Hop Wireless Routing", In ACM Mobicom, 2003.
[25]Skalli, H. Ghosh, S. Das, S.K. Lenzini, L. Conti, M., "Channel Assignment Strategies for Multiradio Wireless Mesh Networks:Issues and Solutions", Communications Magazine, IEEE, November 2007
[26]A. Raniwala, K. Gopalan, and T. Chiueh, "Centralized Channel Assignment and Routing Algorithm for Multi-channel Wireless Mesh Networks," ACM Mobile Comp. and Commun. Rev., Apr.2004, pp.50-65.
[27]A. Raniwala, and T. Chiueh, "Architecture and Algorithms for an IEEE 802.11-Based Multi-Channel Wireless Mesh Network," Proc. IEEE INFOCOM, Mar 2005, pp.2223-34.
[28]K. Ramachandran et al., "Interference Aware Channel Assignment in Multi-Radio Wireless Mesh Networks," Proc. IEEE INFOCOM, Apr.2006.
[29]http://en.wikipedia.org/wiki/AODV
[30]Guo-jun Shui, Shu-qun Shen, "A Cross-Layer Design for Distributed Channel Assignment over Multi-Radio Multi-Channel Wireless Mesh Networks," First International Conference on Intelligent Networks and Intelligent Systems,1-3 Nov. 2008 Page(s):209-212
[31]K. Jain, J. Padhye, V. N. Padmanabhan, and L. Qiu, "Impact of Interference on Multi-Hop Wireless Network Performance," Proc. ACM MobiCom,2003
[32]Haitao Wu, Fan Yang, Kun Tan, et al, "Distributed Channel Assignment and Routing in Multiradio Multichannel Multihop Wireless Networks," IEEE Journal on Selected Areas in Communications, Volume 24, Issue 11, Nov.2006 Page(s):1972-1983
[33]"Introduction to Network Simulator NS2"
[34]"Hyacinth:An IEEE 802.11-based Multi-channel Wireless Mesh Network", http://www.ecsl.cs.sunysb.edu/multichannel/
[35]http://www.q2s.ntnu.no/-paquerea/ns.php
[36]Anand Prabhu Subramanian, Himanshu Gupta, Samir R. Das, "Minimum Interference Channel Assignment in Multi-Radio Wireless Mesh Networks," Proc. of the Fourth Annual IEEE Communications Society Conference on Sensor, Mesh, and Ad Hoc Communications and Networks (SECON 2007), San Diego, California, USA, June 18-21,2007.
[37]Ying-Yu Chen, Shang-Chun Liu, and Chien Chen. "Channel Assignment and Routing for Multi-Channel Wireless Mesh Networks Using Simulated Annealing," Global Telecommunications Conference,2006. GLOBECOM'06. IEEE Nov.27 2006-Dec.1 2006 Page(s):1-5
[38]Yaling Yang, Jun Wang, and Robin Kravets, "Interference-aware Load Balancing for Multihop Wireless Networks," Tech. Rep. UIUCDCS-R-2005-2526, Department of Computer Science, University of Illinois at Urbana-Champaign,2005.
[2]X. Wang, W. Wang, and M. Nova, "A High Performance Single-Channel IEEE 802.11 MAC with Distributed TDMA," Tech. rep., Kiyon, Inc. (submitted for patent application), Oct.2004
[3]J.So and N. Vaidya, "Multi-channel MAC for Ad Hoc Networks:Handling Multi-channel Hidden Terminals using a Single Transceiver," Proc. ACM Mobihoc, 2004, pp.222-33
[4]P. Bahl, R. Chandra and J. Dunagan, "SSCH:Slotted Seeded Channel Hopping for Capacity Improvement in IEEE 802.11 Ad-Hoc Wireless Networks," Proc. ACM Mobicom,2004, pp.216-30
[5]Ching-Ju Lin, Sung-Han Lin and Cheng-Fu Chou, "Performance Study of Optimal Routing and Channel Assignment in Wireless Mesh Networks," GLOBECOM'07. IEEE Nov.2007 Page(s):4818-4822
[6]http://labs.chinamobile.com/mblog/122_5025
[7]Whitehead P., "Mesh networks; a new architecture for broadband wireless accesssystems," Radio and Wireless Conference,2000. RAWCON 2000.2000 IEEE, Volume, Issue,2000 Page(s):43-46
[8]陈琳琳,刘乃安.无线Mesh网络与IEEE802系列标准.中兴通信技术,2008年14卷第2期.
[9]孙伟峰.基于802.11无线—结合网络的QoS研究.合肥：中国科技大学,2007.
[10]W. Steven Conner, Jan Kruys, Kyeongsoo (Joseph) Kim, Juan Carlos Zuniga, "IEEE 802.11s Tutorial", November 2006
[11]方旭明,戚彩霞,向征.IEEE 802系列无线网络网状组网与移动切换技术综述.计算机应用,2006,26(8)：1756-1761.
[12]董晓鲁,党梅梅,沈嘉等.WiMAX技术、标准与应用.人民邮电出版社,2007
[13]IEEE802.20Standard Group WebSite. http://www.ieee802.org/20/.
[14]焦健.高速移动数据传输新标准IEEE802.20及其切换策略研究.北京：北京交通大学,2006.
[15]W. Xiang, T. Pratt, X. Wang, "A software radio testbed for two-transmitter two-receiver space time coding wireless LAN," IEEE Communications Magazine 42(6)(2004) S20-S28
[16]K. Sundaresan, R. Sivakumar, M. A. Ingram, T.-Y. Chang, "A fair medium access control protocol for ad-hoc networks with MIMO links," IEEE Annual Conference on Computer Communications (INFOCOM),2004, pp.2559-2570
[17]A. Adya, P. Bahl, J. Padhye, A. Wolman, L. Zhou, "A multi-radio unification protocol for IEEE 802.11 wireless networks," International Conference on Broadband Networks (BroadNets),2004
[18]R. Drave, J. Padhye, and B. Zill, "Routing in Multi-Radio, Multi-Hop Wireless Mesh Networks," ACM MobiCom, Sept.2004, pp.114-28.
[19]方旭明,马建忠,“无线Mesh网络跨层设计”,《数据通信》2005年第4期
[20]David B Johnson and David A Maltz, "Dynamic Source Routing in Ad Hoc Wireless Networks," in Mobile Computing.1996, vol.353, Kluwer Academic Publishers.
[21]Charles Perkins, "Ad-hoc on-demand distance vector routing," In MILCOM panel on Ad Hoc Networks,1997.
[22]Charles Perkins and Pravin Bhagwat, "Highly dynamic destinationsequenced distance-vector routing (DSDV) for mobile computers," In ACM SIGCOMM,1994.
[23]Tsu-Wei Chen and Mario Gerla, "Global State Routing:A New Routing Schemes for Ad-hoc Wireless Networks," in IEEE ICC,1998.
[24]Douglas S. J. De Couto, Daniel Aguayo, John Bicket, and Robert Morris, "A High-Throughput Path Metric for Multi-Hop Wireless Routing", In ACM Mobicom, 2003.
[25]Skalli, H. Ghosh, S. Das, S.K. Lenzini, L. Conti, M., "Channel Assignment Strategies for Multiradio Wireless Mesh Networks:Issues and Solutions", Communications Magazine, IEEE, November 2007
[26]A. Raniwala, K. Gopalan, and T. Chiueh, "Centralized Channel Assignment and Routing Algorithm for Multi-channel Wireless Mesh Networks," ACM Mobile Comp. and Commun. Rev., Apr.2004, pp.50-65.
[27]A. Raniwala, and T. Chiueh, "Architecture and Algorithms for an IEEE 802.11-Based Multi-Channel Wireless Mesh Network," Proc. IEEE INFOCOM, Mar 2005, pp.2223-34.
[28]K. Ramachandran et al., "Interference Aware Channel Assignment in Multi-Radio Wireless Mesh Networks," Proc. IEEE INFOCOM, Apr.2006.
[29]http://en.wikipedia.org/wiki/AODV
[30]Guo-jun Shui, Shu-qun Shen, "A Cross-Layer Design for Distributed Channel Assignment over Multi-Radio Multi-Channel Wireless Mesh Networks," First International Conference on Intelligent Networks and Intelligent Systems,1-3 Nov. 2008 Page(s):209-212
[31]K. Jain, J. Padhye, V. N. Padmanabhan, and L. Qiu, "Impact of Interference on Multi-Hop Wireless Network Performance," Proc. ACM MobiCom,2003
[32]Haitao Wu, Fan Yang, Kun Tan, et al, "Distributed Channel Assignment and Routing in Multiradio Multichannel Multihop Wireless Networks," IEEE Journal on Selected Areas in Communications, Volume 24, Issue 11, Nov.2006 Page(s):1972-1983
[33]"Introduction to Network Simulator NS2"
[34]"Hyacinth:An IEEE 802.11-based Multi-channel Wireless Mesh Network", http://www.ecsl.cs.sunysb.edu/multichannel/
[35]http://www.q2s.ntnu.no/-paquerea/ns.php
[36]Anand Prabhu Subramanian, Himanshu Gupta, Samir R. Das, "Minimum Interference Channel Assignment in Multi-Radio Wireless Mesh Networks," Proc. of the Fourth Annual IEEE Communications Society Conference on Sensor, Mesh, and Ad Hoc Communications and Networks (SECON 2007), San Diego, California, USA, June 18-21,2007.
[37]Ying-Yu Chen, Shang-Chun Liu, and Chien Chen. "Channel Assignment and Routing for Multi-Channel Wireless Mesh Networks Using Simulated Annealing," Global Telecommunications Conference,2006. GLOBECOM'06. IEEE Nov.27 2006-Dec.1 2006 Page(s):1-5
[38]Yaling Yang, Jun Wang, and Robin Kravets, "Interference-aware Load Balancing for Multihop Wireless Networks," Tech. Rep. UIUCDCS-R-2005-2526, Department of Computer Science, University of Illinois at Urbana-Champaign,2005.