无线Mesh网络多路径路由技术研究
|
摘要
无线网状网(Wireless Mesh Network,简称WMN)是一种新型的无线通信网络。路由协议对无线Mesh网的性能有着重要的影响,因此路由协议一直是无线Mesh网的研究热点。而现有的按需路由协议大多数是基于单条路径,即根据一定的评判指标(时延、跳数等),选择一条最优的路径,由于节点移动性、节点失效以及无线信道的动态特征,单路径中的链路可能会临时失效从而导致路径不可达,而寻找替代路径的开销大,并且可能带来报文转发中的额外的时延以及分组投递率降低的问题。由于多路径路由协议在提高网络可靠性和容错性上有很大的优势,因此本文主要研究多路径路由协议。使用多路径的目的是为了向应用层提供更加可靠和健壮的端到端连接或者提供更高的带宽,从而减小系统的端到端时延和提高分组投递率,更好地支持包括实时业务在内的多种应用。
DSR协议是一种典型的按需路由协议,基于DSR协议改进的多路径路由协议有很多,SIMR协议就是其中的一种,SIMR协议能在源节点和目的节点之间建立不相交路由,但是该协议发现不相交路由的能力有限。多路径路由协议中各条路由的相关性影响着协议的健壮性。本文在深入分析DSR协议和SIMR协议的特点的基础上,分别提出了基于DSR协议的链路不相交多路径路由协议LDSR和基于DSR协议的节点不相交多路径路由协议NDSR。仿真结果表明,在节点密度较稀疏且节点运动速度较快的网络中,与SIMR协议相比,LDSR协议能提高网络的分组投递率,减少端到端时延。在节点密度较大且节点运动速度较快的网络中,与SIMR协议相比,NDSR协议能提高网络的分组投递率,减少端到端时延。
Wireless Mesh Network(WMN)is a new kind of broadband wireless networks.Routing protocols play one of the most important parts in WMN, so the research on routing protocol is always a hot issue of WMN. The majority of on-demand routing protocols are based on a single path which is chosen according to certain indicators such as delay or hop-count.The link of single path may temporarily fail because of node mobility, node fails and dynamic characteristics of wireless channel. The overhead of searching alternative paths is high which may cause an additional delay and reduction of packet delivery ratio.The main advantage of multi-path routing is to provide high reliability and fault tolerance,so the paper focuses on multi-path routing protocol.The purpose of using multiple paths is to provide a more reliable and robust end to end connections or provide higher bandwidth to application layer. It will reduce the end to end delay and improve the packet delivery ratio and provide a better support for a variety of applications including real-time service.
DSR is a typical on-demand routing protocol.Many multi-path routing protocols are based on DSR and SIMR is one of them.SIMR can find disjoint routes between source and destination.But its ability of finding disjoint routes is limited. The relevance of main path and alternative path affects the robustness of a routing protocol.After the study of DSR and SIMR, a new link-disjoint routing protocol LDSR and node-disjoint routing protocol NDSR which is based on DSR are given.
The simulation results show that LDSR protocol can improve the packet delivery ratio and reduce end to end delay compared to SIMR in the sparse and fast motion network. NDSR protocol can improve the packet delivery ratio and reduce end to end delay compared to SIMR in the dense and fast motion network.
DSR协议是一种典型的按需路由协议,基于DSR协议改进的多路径路由协议有很多,SIMR协议就是其中的一种,SIMR协议能在源节点和目的节点之间建立不相交路由,但是该协议发现不相交路由的能力有限。多路径路由协议中各条路由的相关性影响着协议的健壮性。本文在深入分析DSR协议和SIMR协议的特点的基础上,分别提出了基于DSR协议的链路不相交多路径路由协议LDSR和基于DSR协议的节点不相交多路径路由协议NDSR。仿真结果表明,在节点密度较稀疏且节点运动速度较快的网络中,与SIMR协议相比,LDSR协议能提高网络的分组投递率,减少端到端时延。在节点密度较大且节点运动速度较快的网络中,与SIMR协议相比,NDSR协议能提高网络的分组投递率,减少端到端时延。
Wireless Mesh Network(WMN)is a new kind of broadband wireless networks.Routing protocols play one of the most important parts in WMN, so the research on routing protocol is always a hot issue of WMN. The majority of on-demand routing protocols are based on a single path which is chosen according to certain indicators such as delay or hop-count.The link of single path may temporarily fail because of node mobility, node fails and dynamic characteristics of wireless channel. The overhead of searching alternative paths is high which may cause an additional delay and reduction of packet delivery ratio.The main advantage of multi-path routing is to provide high reliability and fault tolerance,so the paper focuses on multi-path routing protocol.The purpose of using multiple paths is to provide a more reliable and robust end to end connections or provide higher bandwidth to application layer. It will reduce the end to end delay and improve the packet delivery ratio and provide a better support for a variety of applications including real-time service.
DSR is a typical on-demand routing protocol.Many multi-path routing protocols are based on DSR and SIMR is one of them.SIMR can find disjoint routes between source and destination.But its ability of finding disjoint routes is limited. The relevance of main path and alternative path affects the robustness of a routing protocol.After the study of DSR and SIMR, a new link-disjoint routing protocol LDSR and node-disjoint routing protocol NDSR which is based on DSR are given.
The simulation results show that LDSR protocol can improve the packet delivery ratio and reduce end to end delay compared to SIMR in the sparse and fast motion network. NDSR protocol can improve the packet delivery ratio and reduce end to end delay compared to SIMR in the dense and fast motion network.
引文
[1]P. Whitehead,Mesh networks-a new architecture for broadband wireless access system.2000 IEEE Radio and Wireless Conference,10-13 September.2000, pp.43-46.
[2]Akyildez.Ian F, Wang Xudong, Wang Weilin. Wireless mesh networks:a survey [J].Computer Networks,2005,47(4):445-487.
[3]Zhang Yan, Luo Jijun, Hu Honglin. Wireless mesh networking:architectures, protocols and standards [M],New York, NY, USA:Auerbach Publications, Taylor and Francis Group,2006.
[4]MeshNetworks.http://www.meshnetworks.com.
[5]方旭明等,下一代无线因特网技术：无线MESH网络.人民邮电出版社
[6]单瑛,朱晓东.IEEES02.11s的MAC协议相关研究,《数据通信》,第4期,2005年
[7]Lei Wang, Lianfang Zhang, Yantai Shu and Miao Dong,"Multipath Source Routing in Wireless Ad hoc Networks",2000 Canadian Conference on Electrical and Computer Engineering, Vol.1, pp.479-483
[8]Richard Draves, Jitendra Padhye,"Routing in Multi-Radio, Multi-hop wireless MESH network", ACM Inetnational Conference, August 2004
[9]A.K.Saha, D.B.Johnson,"Self-organizing hierarchical routing for scalable ad hoc networking", Technical Report, TR04-433, Department of Computer Sceince, Rice University
[10]Douglas S.J.De Couto," A high-throughput path metric for multi-hop wireless routing", ACM, Sep.2003
[11]R.Draves, J.Padhye, B.Zill,"Comparisons of routing metrics for static multi-hop wireless networks", ACM Annual Conference of the Special Interest Group on Data Communication(SIGCOMM), August 2004, pp.133-144
[12]S.Shakkottai,S.T. Rappaport, P.C. Karlsson, Cross-Layer Design for Wireless Networks. IEEE Communications Magazine, October 2003,pp.74-80.
[13]Luigi Iannone, Ramin Khalili, Kav'e Salamatian, Serge Fdida, "Cross-Layer Routing in Wireless MESH Networks", Computer Networks, March2005,pp.445-487.
[14]Skalli.H,Ghosh.S,Dass.K. at el. Channel assignment strategies for multi-radio wireless Mesh networks:Issues and solutions [J].IEEE Communications Magazine.2007.45(11).86-95.
[15]Zongwu Ke,Layuan Li,Qiang Sun. A Qos Multicast Routing Algorithm for Wireless Mesh Networks.Eighth ACIS International Conference.Aug 2007.Vol:835-840.
[16]Telecommunications Industry Association(TIA), "Wideband Air Interface(SAM) Radio Channel Coding Specification Public Safety Wideband Standards Project Digital Radio Technical Standards," TIA-902 BAAD,September 2002.
[17]Ye Yan,Hua Cai,Seung Woo Seo.Performance Analysis of IEEE802.11 Wireless Mesh Networks.IEEE International Conference on 19-23.May2008,pp.2547-2551.
[18]Ashrfu,Juanoleg.Evaluating routing protocols for the wireless mesh backbone [C].Proceedings of 3rd IEEE International Conference on Wireless and Mobile Computing.Networking and Communications.Oct2007,pp.40-47.
[19]Charles E. Perkins, Elizabeth M. Royer. Ad-hoc On-Demand Distance Vector Routing.2nd IEEE Workshop on Mobile Computing Systems and Applications, WMCSA1999. IEEE, February 25-26,1999. pp.90-100.
[20]RFC 3561:http://www.ietf.org/rfc/rfc3561.txt
[21]David B. Johnson, David A. Maltz. Dynamic Source Routing in Ad Hoc Wireless Networks. Kluwer Academic Publisher:Mobile Computing. Chapter 5, Vol.353,1996. pp.153-181.
[22]http://www.ietf.org/internet-drafts/draft-ietf-manet-dsr-10.txt
[23]V. Park and S.Corson. Temporally-Ordered Routing Algorithm (TORA) Version 1-Functional Specification.Internet Draft (working in progress),Naval Research Lab and Univ. of Maryland, November 1997. draft-ietf-manet-tora-spec-OO.txt
[24]M.R.Pearlman,Z.J.Haas,P.Sholander et al."On the impact of alternate path routing for load balancing in mobile ad hoc networks."Porceedings of the first workshop on mobile and ad hoc networking and computing (MobiHoc 2000), Boston,MA,Aug.2000.
[25]B.Bellur and R.Ogier, "A Reliable Efficient Topology Broadcast Protocol for Dynamic Networks", Proceedings IEEE INFOCOM'99, p.178-186, March 1999.
[26]B.Bellur,et.al, "Topology Dissemination Based on Reverse-Path Forwarding(TBRPF)",IETF Internet Draft,draft-ietf-manet-tbrpf-08.txt,April 2003.
[27]Roy Leung etal, "MP-DSR:A QoS-aware Multi-path DSR Protocol for Wireless Ad-Hoc Networks,"Proc.26th LCN,p.132-142,March 2001.
[28]Philippe Jacquet, P.Muhlethaler, and A.Qayyum.Optimized Link State Routing Protocol. Internet Draft (working in progress), INRIA Rocquencourt, February 2000.
[29]T.Clausen,P.Jacquet,A.Laouiti et al "Optimized Link State Routing Protocol for Mobile Ad Hoc Networks", IEEE INMIC Pakistan 2001.
[30]P.Jacquet,P.Muhlethaler and A.Qayyum. "Optimized Link State Routing Protocol",IETF Internet Draft,draft-ietf-manet-olsr-10.txt,June 2002.
[31]S.J.Lee, M..Gerla. Split Multi-Path Routing with maximally Disjoint Paths in Ad Hoc Networks. In Proc. ICC2001,vol.10, June 2001,3201-3205.
[32]A. Nasiputi, S.R. Das. On Demand Multipath Routing for Mobile Ad Hoc Networks, Proceedings of IEEE ICCCN'99, Boston, MA, Oct.1999. pp.64-70.
[33]S.J.Lee, M.Gerla, AODV-BR:Backup routing in Ad Hoc networks [J].IEEE WCNC,2000(9):1311-1316.
[34]Yan-Tai Shu, Guang-HongWang, Lei Wang, Olvier W. W. Yang, Yong-Jie Fan. Provisioning QoS Guarantee by Multipath Routing and Reservation in Ad Hoc Networks[J].Computer Science and Technology.2004,19 (2):128-137.
[35]李占波,庞海波.Ad Hoc网络中AOMDV协议的一种改进方案,第24卷第11-3期,2008年
[36]J.J.Galvez, P. M. Ruiz and A. F. G Skarmeta, "Spatially Disjoint Multipath Routing Protocol without Location Information," University of Murcia, Spain, Tech. Rep.,2008, TR-DⅡC 1/08.
[37]薛飞,唐红.基于MAODV协议的多路径扩展方法,《微计算机信息》第25卷第1-3期,2009年
[38]朱伟,Ad hoc网络独立多路径路由的研究与改进,2006年
[2]Akyildez.Ian F, Wang Xudong, Wang Weilin. Wireless mesh networks:a survey [J].Computer Networks,2005,47(4):445-487.
[3]Zhang Yan, Luo Jijun, Hu Honglin. Wireless mesh networking:architectures, protocols and standards [M],New York, NY, USA:Auerbach Publications, Taylor and Francis Group,2006.
[4]MeshNetworks.http://www.meshnetworks.com.
[5]方旭明等,下一代无线因特网技术：无线MESH网络.人民邮电出版社
[6]单瑛,朱晓东.IEEES02.11s的MAC协议相关研究,《数据通信》,第4期,2005年
[7]Lei Wang, Lianfang Zhang, Yantai Shu and Miao Dong,"Multipath Source Routing in Wireless Ad hoc Networks",2000 Canadian Conference on Electrical and Computer Engineering, Vol.1, pp.479-483
[8]Richard Draves, Jitendra Padhye,"Routing in Multi-Radio, Multi-hop wireless MESH network", ACM Inetnational Conference, August 2004
[9]A.K.Saha, D.B.Johnson,"Self-organizing hierarchical routing for scalable ad hoc networking", Technical Report, TR04-433, Department of Computer Sceince, Rice University
[10]Douglas S.J.De Couto," A high-throughput path metric for multi-hop wireless routing", ACM, Sep.2003
[11]R.Draves, J.Padhye, B.Zill,"Comparisons of routing metrics for static multi-hop wireless networks", ACM Annual Conference of the Special Interest Group on Data Communication(SIGCOMM), August 2004, pp.133-144
[12]S.Shakkottai,S.T. Rappaport, P.C. Karlsson, Cross-Layer Design for Wireless Networks. IEEE Communications Magazine, October 2003,pp.74-80.
[13]Luigi Iannone, Ramin Khalili, Kav'e Salamatian, Serge Fdida, "Cross-Layer Routing in Wireless MESH Networks", Computer Networks, March2005,pp.445-487.
[14]Skalli.H,Ghosh.S,Dass.K. at el. Channel assignment strategies for multi-radio wireless Mesh networks:Issues and solutions [J].IEEE Communications Magazine.2007.45(11).86-95.
[15]Zongwu Ke,Layuan Li,Qiang Sun. A Qos Multicast Routing Algorithm for Wireless Mesh Networks.Eighth ACIS International Conference.Aug 2007.Vol:835-840.
[16]Telecommunications Industry Association(TIA), "Wideband Air Interface(SAM) Radio Channel Coding Specification Public Safety Wideband Standards Project Digital Radio Technical Standards," TIA-902 BAAD,September 2002.
[17]Ye Yan,Hua Cai,Seung Woo Seo.Performance Analysis of IEEE802.11 Wireless Mesh Networks.IEEE International Conference on 19-23.May2008,pp.2547-2551.
[18]Ashrfu,Juanoleg.Evaluating routing protocols for the wireless mesh backbone [C].Proceedings of 3rd IEEE International Conference on Wireless and Mobile Computing.Networking and Communications.Oct2007,pp.40-47.
[19]Charles E. Perkins, Elizabeth M. Royer. Ad-hoc On-Demand Distance Vector Routing.2nd IEEE Workshop on Mobile Computing Systems and Applications, WMCSA1999. IEEE, February 25-26,1999. pp.90-100.
[20]RFC 3561:http://www.ietf.org/rfc/rfc3561.txt
[21]David B. Johnson, David A. Maltz. Dynamic Source Routing in Ad Hoc Wireless Networks. Kluwer Academic Publisher:Mobile Computing. Chapter 5, Vol.353,1996. pp.153-181.
[22]http://www.ietf.org/internet-drafts/draft-ietf-manet-dsr-10.txt
[23]V. Park and S.Corson. Temporally-Ordered Routing Algorithm (TORA) Version 1-Functional Specification.Internet Draft (working in progress),Naval Research Lab and Univ. of Maryland, November 1997. draft-ietf-manet-tora-spec-OO.txt
[24]M.R.Pearlman,Z.J.Haas,P.Sholander et al."On the impact of alternate path routing for load balancing in mobile ad hoc networks."Porceedings of the first workshop on mobile and ad hoc networking and computing (MobiHoc 2000), Boston,MA,Aug.2000.
[25]B.Bellur and R.Ogier, "A Reliable Efficient Topology Broadcast Protocol for Dynamic Networks", Proceedings IEEE INFOCOM'99, p.178-186, March 1999.
[26]B.Bellur,et.al, "Topology Dissemination Based on Reverse-Path Forwarding(TBRPF)",IETF Internet Draft,draft-ietf-manet-tbrpf-08.txt,April 2003.
[27]Roy Leung etal, "MP-DSR:A QoS-aware Multi-path DSR Protocol for Wireless Ad-Hoc Networks,"Proc.26th LCN,p.132-142,March 2001.
[28]Philippe Jacquet, P.Muhlethaler, and A.Qayyum.Optimized Link State Routing Protocol. Internet Draft (working in progress), INRIA Rocquencourt, February 2000.
[29]T.Clausen,P.Jacquet,A.Laouiti et al "Optimized Link State Routing Protocol for Mobile Ad Hoc Networks", IEEE INMIC Pakistan 2001.
[30]P.Jacquet,P.Muhlethaler and A.Qayyum. "Optimized Link State Routing Protocol",IETF Internet Draft,draft-ietf-manet-olsr-10.txt,June 2002.
[31]S.J.Lee, M..Gerla. Split Multi-Path Routing with maximally Disjoint Paths in Ad Hoc Networks. In Proc. ICC2001,vol.10, June 2001,3201-3205.
[32]A. Nasiputi, S.R. Das. On Demand Multipath Routing for Mobile Ad Hoc Networks, Proceedings of IEEE ICCCN'99, Boston, MA, Oct.1999. pp.64-70.
[33]S.J.Lee, M.Gerla, AODV-BR:Backup routing in Ad Hoc networks [J].IEEE WCNC,2000(9):1311-1316.
[34]Yan-Tai Shu, Guang-HongWang, Lei Wang, Olvier W. W. Yang, Yong-Jie Fan. Provisioning QoS Guarantee by Multipath Routing and Reservation in Ad Hoc Networks[J].Computer Science and Technology.2004,19 (2):128-137.
[35]李占波,庞海波.Ad Hoc网络中AOMDV协议的一种改进方案,第24卷第11-3期,2008年
[36]J.J.Galvez, P. M. Ruiz and A. F. G Skarmeta, "Spatially Disjoint Multipath Routing Protocol without Location Information," University of Murcia, Spain, Tech. Rep.,2008, TR-DⅡC 1/08.
[37]薛飞,唐红.基于MAODV协议的多路径扩展方法,《微计算机信息》第25卷第1-3期,2009年
[38]朱伟,Ad hoc网络独立多路径路由的研究与改进,2006年