多接口无线Mesh网络路由协议研究及实现
|
摘要
无线Mesh网络是宽带无线接入的关键技术,主要是为了实现区域范围的无线覆盖,增强网络的系统容量和连通能力,提高系统的抗毁性和自愈能力。在构建家庭网络、校园网、社区网络、企业网及城域网中有着广阔的应用前景。
本文对无线Mesh网络的路由协议进行研究,并根据项目的需要在开发平台上实现和验证。
论文首先研究单无线接口Mesh网络中的路由算法,并在单接口无线Mesh网络开发平台上实现了AODV和DSR路由协议。该平台能够为用户提供宽带无线接入、无线视频监控等服务。在平台上进行实验测量发现,路径吞吐量随着跳数增加迅速下降,这是因为在单接口无线Mesh网络中,所有链路都工作在一个无线接口上,信道间干扰比较严重。
多接口无线Mesh网络中的路由器都有多个无线接口,不同接口可以工作在相互正交的信道上。我们研究并设计实现了有效的多接口无线Mesh网络路由协议,可以将网络中的流量在不同的接口信道上进行均衡,有效降低相互间的干扰,大大提升了网络容量。论文首先提出一个基于最小路径干扰度的路由算法,该算法为端到端数据流选择干扰度最小的路径,在计算干扰度时考虑了路径上各链路之间的干扰(intra-flow interference)。NS-2的仿真结果表明该算法能有效提高网络性能。而后又提出一个基于信道相似度的路由算法,综合考虑跳数、负载以及信道间干扰,从仿真结果看出,该算法能有效提高多接口无线Mesh网络的吞吐量。最后,在前面研究的基础上,提出用于多接口无线Mesh网络的HCRL路由算法,该算法综合考虑路径跳数(HOP)、信道相似度(CSI)、接收信号强度指示(RSSI)、链路剩余容量(LRCL)等参数进行路径选择。该路由协议综合了先应式和按需方式的路由查找思想,可以通过表驱动实现源路由,支持多网关。我们在多接口Mesh网路开发平台上实现了该协议,实验测试结果表明采用HCRL路由协议可以有效地实现负载均衡,提高网络性能。
Wireless Mesh Network is the key point of broadband wireless access technology. It can achieve region-wide wireless coverage,enhance the network capacity and connectivity,improve the system survivability and self-healing capability.In a building,home,campus,community,enterprise networks and metropolitan area network,wireless Mesh network has wide application prospects.
In this paper,we study routing protocols of wireless Mesh network,then implement and verification them on platform.
Firstly,we survey routing algorithm of a single-interface Mesh network,then implement routing protocols of AODV and DSR on platform.This Mesh platform can provide us with wireless access,video surveillance and some other services. Experiment results demonstrate that the path throughput will decrease rapidly as the number of Hops increases.Because in a single interface Mesh network,all links are working on the same interface,which causes serious interference.
In multi-interface wireless Mesh networks,each Mesh router has multiple interfaces,and different interfaces work in mutually orthogonal channel.We design an effective multi-interface wireless Mesh network routing protocol,which can balance the network traffic through different interfaces,effectively reduce network interference and enhance capacity.This paper firstly propose a routing algorithm called minimum route interference,this metric take into account the intra-flow interference and select the minimum interference path to transmit data.NS-2 simulation results show that the algorithm can effectively improve the network performance.Secondly we propose a routing algorithm based on channel similarity, the number of hops,load,as well as inter-channel interference.Simulation results show that the algorithm can effectively improve the multi-interface wireless Mesh network throughput.Finally,we propose HCRL routing algorithm for multi-interface wireless Mesh network,which considers path hop(HOP),the channel similarity(CSI), received signal strength indication(RSSI).link residual capacity(LRCL) to select path.HCRL routing protocol has conbined the advantage of proactive and on-demand methods to find route,can achieve source routing based on table-driven,and support multi-gateways.As the measurement results show,HCRL routing algorithm can effectively improve the network performance,even in the condition of heavy load,the algorithm still can find a good path and balance the load in different interfaces.
本文对无线Mesh网络的路由协议进行研究,并根据项目的需要在开发平台上实现和验证。
论文首先研究单无线接口Mesh网络中的路由算法,并在单接口无线Mesh网络开发平台上实现了AODV和DSR路由协议。该平台能够为用户提供宽带无线接入、无线视频监控等服务。在平台上进行实验测量发现,路径吞吐量随着跳数增加迅速下降,这是因为在单接口无线Mesh网络中,所有链路都工作在一个无线接口上,信道间干扰比较严重。
多接口无线Mesh网络中的路由器都有多个无线接口,不同接口可以工作在相互正交的信道上。我们研究并设计实现了有效的多接口无线Mesh网络路由协议,可以将网络中的流量在不同的接口信道上进行均衡,有效降低相互间的干扰,大大提升了网络容量。论文首先提出一个基于最小路径干扰度的路由算法,该算法为端到端数据流选择干扰度最小的路径,在计算干扰度时考虑了路径上各链路之间的干扰(intra-flow interference)。NS-2的仿真结果表明该算法能有效提高网络性能。而后又提出一个基于信道相似度的路由算法,综合考虑跳数、负载以及信道间干扰,从仿真结果看出,该算法能有效提高多接口无线Mesh网络的吞吐量。最后,在前面研究的基础上,提出用于多接口无线Mesh网络的HCRL路由算法,该算法综合考虑路径跳数(HOP)、信道相似度(CSI)、接收信号强度指示(RSSI)、链路剩余容量(LRCL)等参数进行路径选择。该路由协议综合了先应式和按需方式的路由查找思想,可以通过表驱动实现源路由,支持多网关。我们在多接口Mesh网路开发平台上实现了该协议,实验测试结果表明采用HCRL路由协议可以有效地实现负载均衡,提高网络性能。
Wireless Mesh Network is the key point of broadband wireless access technology. It can achieve region-wide wireless coverage,enhance the network capacity and connectivity,improve the system survivability and self-healing capability.In a building,home,campus,community,enterprise networks and metropolitan area network,wireless Mesh network has wide application prospects.
In this paper,we study routing protocols of wireless Mesh network,then implement and verification them on platform.
Firstly,we survey routing algorithm of a single-interface Mesh network,then implement routing protocols of AODV and DSR on platform.This Mesh platform can provide us with wireless access,video surveillance and some other services. Experiment results demonstrate that the path throughput will decrease rapidly as the number of Hops increases.Because in a single interface Mesh network,all links are working on the same interface,which causes serious interference.
In multi-interface wireless Mesh networks,each Mesh router has multiple interfaces,and different interfaces work in mutually orthogonal channel.We design an effective multi-interface wireless Mesh network routing protocol,which can balance the network traffic through different interfaces,effectively reduce network interference and enhance capacity.This paper firstly propose a routing algorithm called minimum route interference,this metric take into account the intra-flow interference and select the minimum interference path to transmit data.NS-2 simulation results show that the algorithm can effectively improve the network performance.Secondly we propose a routing algorithm based on channel similarity, the number of hops,load,as well as inter-channel interference.Simulation results show that the algorithm can effectively improve the multi-interface wireless Mesh network throughput.Finally,we propose HCRL routing algorithm for multi-interface wireless Mesh network,which considers path hop(HOP),the channel similarity(CSI), received signal strength indication(RSSI).link residual capacity(LRCL) to select path.HCRL routing protocol has conbined the advantage of proactive and on-demand methods to find route,can achieve source routing based on table-driven,and support multi-gateways.As the measurement results show,HCRL routing algorithm can effectively improve the network performance,even in the condition of heavy load,the algorithm still can find a good path and balance the load in different interfaces.
引文
[1]Jungmin So,Nitin Vaidya.A Routing Protocol for Utilizing Multiple Channels in Multi-HOP Wireless Networks with a Single Transceiver.Technical Report October 2004
[2]Richard Draves Jitendra Padhye Brian Zill.Routing in Multi-Radio,Multi-HOP Wireless Mesh Networks.MobiCom '04,Sept.26-Oct
[3]Lan Tien Nguyen,Razvan Beurant,Yoichi Shinoda.A Load-aware Routing Metric for Wireless Mesh Networks.2008.1,429-435.
[4]Anand Prabhu Subramanian Milind M.Buddhikot,Scott Miller,Interference Aware Routing in Multi-Radio Wireless Mesh Networks,WiMesh06
[5]Anh-Ngoc Le,Dong-Won Kum,and You-Ze Cho.Load-aware Routing Protocol for Multi-radio Wireless Mesh Networks.2008.9,138-143.
[6]Y.Yang,J.Wang,and R.Kravts.Designing Routing Metrics for Mesh Network.wiMesh,2005.
[7]JANGEUN J,SICHITIU ML.The nominal capacity of wireless Mesh networks[J].IEEE Journal of Wireless Communications,2003,10(5):8-14.
[8]P.Gupta and P.R.Kumar.The Capacity of Wireless Networks.IEEE Transactions on Information Theory,46(2),2000,388-404.
[9]K.Jain,J.Padhye,V.N.Padmanabhan,and L.Qiu.Impact of Interference on Multi-HOP Wireless Network Performance.In MOBICOM,2003.
[10]Xun Chen,Zhaoyang Zhang and Haiyan Luo."Joint Optimization of Power Control,Channel Assignment and Scheduling in Wireless Mesh Network".Chinacom 08'.
[11]Liang Dai,Yuan Xue,Bin Chang,Yanchuan Cao,Yi Cui."Integrating Traffic Estimation and Routing Optimization for Multi-Radio Multi-Channel Wireless Mesh Networks".INFOCOM 2008.
[12]沈庆伟,胡云,杨寿保,王大鹏.多radio无线Mesh网络跨层路由协议.重庆大学学报,第32卷第4期.457-463.
[13]赵蕴龙,马延龙,李香.无线Mesh网链路不相交多路径路由策略.哈尔滨工程大学学报,第29卷第9期,967-972.
[14]王嵌琦,何新贵,徐明.无线Mesh网络的路径容量分析模型及算法.计算机研究与发展.2008.45,393-399.
[15]Krishna N.Ramachandran,Elizabeth M.Belding,Kevin C.Almeroth,Milind M.Buddhikot.Interference-Aware Channel Assignment in Multi-Radio Wireless Mesh Networks.Infocom 2006.
[16]Ashish Raniwala Kartik Gopalan Tzi-cker Chiueh.Centralized Channel Assignment and Routing Algorithms for Multi-Channel Wireless Mesh Networks.Mobile Computing and Communications Review,Volume 8,Number 2,50-65.
[17]Pradeep Kyasanur,Nitin H.Vaidys.Routing and Interface Assignment in Multi-Channel Multi-Interface Wireless Networks.WCNC 2005.
[18]Stefan Bouckaert,Nicolas Letor,Chris Blondia,Ingrid Moerman and Piet Demeester.Distributed On Demand Channel Selection in Multi Channel,Multi Interface Wireless Mesh Networks.GLOBECOM 2007.
[19]Mansoor Alicherry Randeep Bhatia Li(Erran) Li.Joint Channel Assignment and Routing for Throughput Optimization in Multi-radio Wireless Mesh Networks.MobiCom'05.
[20]Hon Sun Chiu,Kwan L.Yeung and King-Shan Lui.J-CAR:an Efficient Channel Assignment and Routing Protocol for Multi-channel Multi-interface Mobile Ad Hoc Networks.GLOBECOM 2006.
[21]Anastasios Giannoulis,Theodoros Salonidis,Edward Knightly.Congestion Control and Channel Assignment in Multi-Radio Wireless Mesh Networks.SECON 2008.
[22]Yaling Yang,Jun Wang,Robin Kravets.Designing Routing Metrics for Mesh Networks.WiMesh'05.
[23]Xiangrui Meng,Kun Tan,Qian Zhang.Joint Routing and Channel Assignment in Multi-Radio Wireless Mesh Networks.ICC 2006.
[24]Simone Merlin,Nitin Vaidya,Michele Zorzi.Resource Allocation in Multi-Radio Multi-Channel Multi-HOP Wireless Networks.INFOCOM 2008.
[25]CHI-YU LI,AN-KAI JENG AND RONG-HONG JAN.A MAC Protocol for Multi-Channel Multi-Interface Wireless Mesh Network using Hybrid Channel Assignment Scheme.JOURNAL OF INFORMATION SCIENCE AND ENGINEERING 23,1041-1055(2007),1041-1055.
[26]Jianfeng Wang,Yuguang Fang,Dapeng Wu.A Power-Saving Multi-radio Multi-channel MAC Protocol for Wireless Local Area Networks.Infocom 2006.
[27]Eunsook Shim,Seunghoon Baek,Joungsik Kim,and Dongkyun Kim.Multi-channel Multi-interface MAC Protocol in Wireless Ad hoc Networks.ICC 2008.
[28]Network Working Group,DSR_RFC4728,The Dynamic Source Routing Protocol(DSR) for Mobile Ad hoc Networks for IPv4,The IETF Trust,2007.
[29]肖世红,张连芳.DSR协议中路由缓存和局部搜索策略研究,[硕士学位论文].天津大学,2005.
[30]周帆,李红艳.动态路由协议(DSR)在linux下的实现,[硕士学位论文].西安电子科技大学,2006.
[31]姜少杰,吕光宏.基于移动预测的Ad Ho网络DSR路由研究,[硕士学位论文].四川大学,2006.
[32]袁盛嘉,李旭.基于嵌入式Linux操作系统的AODV算法研究与实现,[硕士学位论文].北京交通大学,2006.
[33]赵炜,杨余旺.AODV路由协议算法研究与设计实现,[硕士学位论文].南京理工大学,2006.
[34]谢世欢,郭伟.Linux系统上AODV路由协议的实现,[硕士学位论文].电子科技大学,2004.
[35]Network Working Group,AODV_RFC3561,Ad hoc On-Demand Distance Vector(AODV) Routing,The Internet Society,2003.
[36]Ian F.Akyildiz,Xudong Wang b,Weilin Wang.Wireless Mesh networks:a survey.Computer Networks 47(2005) 445-487.
[37]Muddesar Iqbal,Xinheng Wang,David Wertheim,XuZhou.Load Balanced Multiple Gateway Support in Wireless Mesh Networks for Broadband Services.WOCC 2009.
[38] Panlong Yang, Chao Dong, Hai Wang, Guihai Chen. Characterizing the Scaling Capacity of Multiple Gateway Access in Wireless Sensor Networks. EmbeddedCom-ScalCom.2009.
[39]Sally Floyd and Van Jacobson. Random Early Detection Gateways for Congestion Avoidance. IEEE/ACM TRANSACTIONS ON NETWORKING. VOL I . NO 1. AUGL1ST 1993, 397-413.
[40]Usman Ashraf, Slim Abdellatif and Guy Juanole. Usman Ashraf, Slim Abdellatif and Guy Juanole. WCNC 2009.
[41]Wenjia Wu, Junzhou Luo, Ming Yang. Gateway Placement Optimization for Load Balancing in Wireless Mesh Networks, the 2009 13th International Conference on Compute, 408-413.
[42] Bin Shen, Li Zou, Zhonggong Hu. Performance Comparison and Analysis of Three Gateway Discovery Protocols of Internet Connectivity for Ad hoc Networks. Journal of Communication and Computer, ISSN1548-7709, USA.
[2]Richard Draves Jitendra Padhye Brian Zill.Routing in Multi-Radio,Multi-HOP Wireless Mesh Networks.MobiCom '04,Sept.26-Oct
[3]Lan Tien Nguyen,Razvan Beurant,Yoichi Shinoda.A Load-aware Routing Metric for Wireless Mesh Networks.2008.1,429-435.
[4]Anand Prabhu Subramanian Milind M.Buddhikot,Scott Miller,Interference Aware Routing in Multi-Radio Wireless Mesh Networks,WiMesh06
[5]Anh-Ngoc Le,Dong-Won Kum,and You-Ze Cho.Load-aware Routing Protocol for Multi-radio Wireless Mesh Networks.2008.9,138-143.
[6]Y.Yang,J.Wang,and R.Kravts.Designing Routing Metrics for Mesh Network.wiMesh,2005.
[7]JANGEUN J,SICHITIU ML.The nominal capacity of wireless Mesh networks[J].IEEE Journal of Wireless Communications,2003,10(5):8-14.
[8]P.Gupta and P.R.Kumar.The Capacity of Wireless Networks.IEEE Transactions on Information Theory,46(2),2000,388-404.
[9]K.Jain,J.Padhye,V.N.Padmanabhan,and L.Qiu.Impact of Interference on Multi-HOP Wireless Network Performance.In MOBICOM,2003.
[10]Xun Chen,Zhaoyang Zhang and Haiyan Luo."Joint Optimization of Power Control,Channel Assignment and Scheduling in Wireless Mesh Network".Chinacom 08'.
[11]Liang Dai,Yuan Xue,Bin Chang,Yanchuan Cao,Yi Cui."Integrating Traffic Estimation and Routing Optimization for Multi-Radio Multi-Channel Wireless Mesh Networks".INFOCOM 2008.
[12]沈庆伟,胡云,杨寿保,王大鹏.多radio无线Mesh网络跨层路由协议.重庆大学学报,第32卷第4期.457-463.
[13]赵蕴龙,马延龙,李香.无线Mesh网链路不相交多路径路由策略.哈尔滨工程大学学报,第29卷第9期,967-972.
[14]王嵌琦,何新贵,徐明.无线Mesh网络的路径容量分析模型及算法.计算机研究与发展.2008.45,393-399.
[15]Krishna N.Ramachandran,Elizabeth M.Belding,Kevin C.Almeroth,Milind M.Buddhikot.Interference-Aware Channel Assignment in Multi-Radio Wireless Mesh Networks.Infocom 2006.
[16]Ashish Raniwala Kartik Gopalan Tzi-cker Chiueh.Centralized Channel Assignment and Routing Algorithms for Multi-Channel Wireless Mesh Networks.Mobile Computing and Communications Review,Volume 8,Number 2,50-65.
[17]Pradeep Kyasanur,Nitin H.Vaidys.Routing and Interface Assignment in Multi-Channel Multi-Interface Wireless Networks.WCNC 2005.
[18]Stefan Bouckaert,Nicolas Letor,Chris Blondia,Ingrid Moerman and Piet Demeester.Distributed On Demand Channel Selection in Multi Channel,Multi Interface Wireless Mesh Networks.GLOBECOM 2007.
[19]Mansoor Alicherry Randeep Bhatia Li(Erran) Li.Joint Channel Assignment and Routing for Throughput Optimization in Multi-radio Wireless Mesh Networks.MobiCom'05.
[20]Hon Sun Chiu,Kwan L.Yeung and King-Shan Lui.J-CAR:an Efficient Channel Assignment and Routing Protocol for Multi-channel Multi-interface Mobile Ad Hoc Networks.GLOBECOM 2006.
[21]Anastasios Giannoulis,Theodoros Salonidis,Edward Knightly.Congestion Control and Channel Assignment in Multi-Radio Wireless Mesh Networks.SECON 2008.
[22]Yaling Yang,Jun Wang,Robin Kravets.Designing Routing Metrics for Mesh Networks.WiMesh'05.
[23]Xiangrui Meng,Kun Tan,Qian Zhang.Joint Routing and Channel Assignment in Multi-Radio Wireless Mesh Networks.ICC 2006.
[24]Simone Merlin,Nitin Vaidya,Michele Zorzi.Resource Allocation in Multi-Radio Multi-Channel Multi-HOP Wireless Networks.INFOCOM 2008.
[25]CHI-YU LI,AN-KAI JENG AND RONG-HONG JAN.A MAC Protocol for Multi-Channel Multi-Interface Wireless Mesh Network using Hybrid Channel Assignment Scheme.JOURNAL OF INFORMATION SCIENCE AND ENGINEERING 23,1041-1055(2007),1041-1055.
[26]Jianfeng Wang,Yuguang Fang,Dapeng Wu.A Power-Saving Multi-radio Multi-channel MAC Protocol for Wireless Local Area Networks.Infocom 2006.
[27]Eunsook Shim,Seunghoon Baek,Joungsik Kim,and Dongkyun Kim.Multi-channel Multi-interface MAC Protocol in Wireless Ad hoc Networks.ICC 2008.
[28]Network Working Group,DSR_RFC4728,The Dynamic Source Routing Protocol(DSR) for Mobile Ad hoc Networks for IPv4,The IETF Trust,2007.
[29]肖世红,张连芳.DSR协议中路由缓存和局部搜索策略研究,[硕士学位论文].天津大学,2005.
[30]周帆,李红艳.动态路由协议(DSR)在linux下的实现,[硕士学位论文].西安电子科技大学,2006.
[31]姜少杰,吕光宏.基于移动预测的Ad Ho网络DSR路由研究,[硕士学位论文].四川大学,2006.
[32]袁盛嘉,李旭.基于嵌入式Linux操作系统的AODV算法研究与实现,[硕士学位论文].北京交通大学,2006.
[33]赵炜,杨余旺.AODV路由协议算法研究与设计实现,[硕士学位论文].南京理工大学,2006.
[34]谢世欢,郭伟.Linux系统上AODV路由协议的实现,[硕士学位论文].电子科技大学,2004.
[35]Network Working Group,AODV_RFC3561,Ad hoc On-Demand Distance Vector(AODV) Routing,The Internet Society,2003.
[36]Ian F.Akyildiz,Xudong Wang b,Weilin Wang.Wireless Mesh networks:a survey.Computer Networks 47(2005) 445-487.
[37]Muddesar Iqbal,Xinheng Wang,David Wertheim,XuZhou.Load Balanced Multiple Gateway Support in Wireless Mesh Networks for Broadband Services.WOCC 2009.
[38] Panlong Yang, Chao Dong, Hai Wang, Guihai Chen. Characterizing the Scaling Capacity of Multiple Gateway Access in Wireless Sensor Networks. EmbeddedCom-ScalCom.2009.
[39]Sally Floyd and Van Jacobson. Random Early Detection Gateways for Congestion Avoidance. IEEE/ACM TRANSACTIONS ON NETWORKING. VOL I . NO 1. AUGL1ST 1993, 397-413.
[40]Usman Ashraf, Slim Abdellatif and Guy Juanole. Usman Ashraf, Slim Abdellatif and Guy Juanole. WCNC 2009.
[41]Wenjia Wu, Junzhou Luo, Ming Yang. Gateway Placement Optimization for Load Balancing in Wireless Mesh Networks, the 2009 13th International Conference on Compute, 408-413.
[42] Bin Shen, Li Zou, Zhonggong Hu. Performance Comparison and Analysis of Three Gateway Discovery Protocols of Internet Connectivity for Ad hoc Networks. Journal of Communication and Computer, ISSN1548-7709, USA.