适合非对称链路的无线移动自组网路由协议的研究
|
摘要
近年来,随着无线通信技术的发展,移动自组网的研究成为了热点。移动自组网是由多个带有无线收发装置的移动节点组成的一个多跳的、没有中心节点和固定基站的自治网络系统。在这种网络中,各节点间的相互通信通常需要其他节点进行协助才能完成。在传统的移动自组网路由协议中,主要是基于节点间的链路是对称这样的假设来进行设计的。即所有节点有相同的信号覆盖范围。然而,对于现实的无线网络环境,各节点由于自身功率不同,往往造成非对称链路的存在。这就造成已有的路由协议不能较好适应这种情况。因此,设计适合非对称链路的无线移动自组网路由协议,对于移动自组网的发展有着重要的现实需求和学术意义。
本文针对目前移动组网路由协议的不足,对AODV协议进行改进,提出了能够适应存在非对称链路的无线移动自组网路由协议。为了实现研究目标,本文围绕移动自组网的路由策略问题展开研究。首先叙述了移动自组网的三种路由模式:先应式路由、后应式路由和混合式路由。并分别介绍了这三种路由模式的经典路由协议DSDV、AODV、ZRP,同时对这三个协议进行了优缺点分析;在第三章,指出在移动自组网环境中,非对称链路的普遍存在,并分析了它的产生原因,以及对网络的影响;在第四章,我们给出了一种适合非对称链路的无线移动自组网按需路由协议。该协议通过在路由请求报文和路由应答报文中携带经过的路径节点来发现前向路由和后向路由,并在路由发现过程中计算链路权值。如果找到的路由是纯双向链路,则该路由发现过程成为为近似AODV路由协议的路由发现过程。如果找到的路由不是纯双向链路,则源节点还需要将RACK报文沿找到的回路路由循环一次,通过RACK的传播来通知中间节点建立起相应的路由。对于路由维护,本文提出了完整的存在单向链路情况下的链路终断检测方案。提出了路径关联节点表,使得路由维护过程更加适用于非对称链路环境。最后,本文对该路由算法的性能进行了仿真分析,并与AODV协议,AODV-H协议和RODA协议进行对比。实验结果表明,本文提出的路由协议能较好适用于非对称链路无线移动自组网环境。
In recent years, with the development of wireless communication technology, the study of mobile ad hoc networks has been more and more popular. Mobile ad hoc networks is a kind of multi-hop and autonomous network system without central node and fixed base station, composed by a number of mobile nodes with wireless transceiver devices.In such a network, the communication between the nodes usually needs other nodes’assistance. The traditional routing protocols for mobile ad hoc networks are mainly designed on the base of the hypothesis that the links between nodes are symmetrical links. It means that all nodes have the same transmission range. However, the different power of nodes usally causes the existence of asymmetric links in real wireless network. Which will cause the existing routing protocols cannot better suit for this situation. Therefore, our research has the very practical demand and academic significance.
In this text, we make several improvements for AODV and give the routing protocol adapting to the MANET with asymmetric links. In order to achieve the object, we carry out studies surrounding the mobile ad hoc routing strategy. Firstly, we introduce the three types of routing protocols for mobile ad hoc network: proactive routing protocols, reactive routing protocols,hybrid routing protocols.We introduc DSDV, AODV and ZRP of the classical routing protocols for the three types and analyze their merits and drawbacks.In chapter 3, we give the opinion that there are asymmetric links in real MANET.Then,we analyze the factors of its exists and its influences in networks.In chapter 4,we put forward an on-demand routing protocol for mobile ad hoc with asymmetric links. The routing protocol use RREQ (request message) and RREP (response message) to search the forward route and backward route.In the route discovery phase, RREQ and RREP will record the nodes which relay it and compute the weights of the links. If the route is a pure two-way path, the routing finding process will become an approximate AODV. If it is not a pure two-way path which includes some asymmetric links, the source needs to spread the RACK along the route and inform the route-related nodes to establish the corresponding route. For the route maintenance, we give a complete scheme of detecing link for MANET with asymmetric links. We propose route-related nodes table.It makes route maintenance better for the suitation with asymmetric links.Finally; we conduct simulation and analysis against performance of the routing algorithms and make the comparison with three protocols, including AODV, AODV-H and RODA. The experiment results show that the proposed routing protocol is fit on mobile Ad hoc networks with asymmetric links.
本文针对目前移动组网路由协议的不足,对AODV协议进行改进,提出了能够适应存在非对称链路的无线移动自组网路由协议。为了实现研究目标,本文围绕移动自组网的路由策略问题展开研究。首先叙述了移动自组网的三种路由模式:先应式路由、后应式路由和混合式路由。并分别介绍了这三种路由模式的经典路由协议DSDV、AODV、ZRP,同时对这三个协议进行了优缺点分析;在第三章,指出在移动自组网环境中,非对称链路的普遍存在,并分析了它的产生原因,以及对网络的影响;在第四章,我们给出了一种适合非对称链路的无线移动自组网按需路由协议。该协议通过在路由请求报文和路由应答报文中携带经过的路径节点来发现前向路由和后向路由,并在路由发现过程中计算链路权值。如果找到的路由是纯双向链路,则该路由发现过程成为为近似AODV路由协议的路由发现过程。如果找到的路由不是纯双向链路,则源节点还需要将RACK报文沿找到的回路路由循环一次,通过RACK的传播来通知中间节点建立起相应的路由。对于路由维护,本文提出了完整的存在单向链路情况下的链路终断检测方案。提出了路径关联节点表,使得路由维护过程更加适用于非对称链路环境。最后,本文对该路由算法的性能进行了仿真分析,并与AODV协议,AODV-H协议和RODA协议进行对比。实验结果表明,本文提出的路由协议能较好适用于非对称链路无线移动自组网环境。
In recent years, with the development of wireless communication technology, the study of mobile ad hoc networks has been more and more popular. Mobile ad hoc networks is a kind of multi-hop and autonomous network system without central node and fixed base station, composed by a number of mobile nodes with wireless transceiver devices.In such a network, the communication between the nodes usually needs other nodes’assistance. The traditional routing protocols for mobile ad hoc networks are mainly designed on the base of the hypothesis that the links between nodes are symmetrical links. It means that all nodes have the same transmission range. However, the different power of nodes usally causes the existence of asymmetric links in real wireless network. Which will cause the existing routing protocols cannot better suit for this situation. Therefore, our research has the very practical demand and academic significance.
In this text, we make several improvements for AODV and give the routing protocol adapting to the MANET with asymmetric links. In order to achieve the object, we carry out studies surrounding the mobile ad hoc routing strategy. Firstly, we introduce the three types of routing protocols for mobile ad hoc network: proactive routing protocols, reactive routing protocols,hybrid routing protocols.We introduc DSDV, AODV and ZRP of the classical routing protocols for the three types and analyze their merits and drawbacks.In chapter 3, we give the opinion that there are asymmetric links in real MANET.Then,we analyze the factors of its exists and its influences in networks.In chapter 4,we put forward an on-demand routing protocol for mobile ad hoc with asymmetric links. The routing protocol use RREQ (request message) and RREP (response message) to search the forward route and backward route.In the route discovery phase, RREQ and RREP will record the nodes which relay it and compute the weights of the links. If the route is a pure two-way path, the routing finding process will become an approximate AODV. If it is not a pure two-way path which includes some asymmetric links, the source needs to spread the RACK along the route and inform the route-related nodes to establish the corresponding route. For the route maintenance, we give a complete scheme of detecing link for MANET with asymmetric links. We propose route-related nodes table.It makes route maintenance better for the suitation with asymmetric links.Finally; we conduct simulation and analysis against performance of the routing algorithms and make the comparison with three protocols, including AODV, AODV-H and RODA. The experiment results show that the proposed routing protocol is fit on mobile Ad hoc networks with asymmetric links.
引文
[1] B. David, Johnson.Routing in Ad Hoc Networks of Mobile Hosts[C].Proc.of the IEEE Workshop on Mobile Computing Systems and Applications, New Orleans, LA, USA. IEEE Press, Dec.1994:158-163.
[2]张蕾. Ad hoc综述[J].电子科学技术评论, 2005(05):35-38.
[3]林蔚.移动自组网的路由技术研究[D].哈尔滨:哈尔滨工程大学计算机科学与技术学院,2006,4:12-15.
[4] C. E.Perkins,P.Bhagwat.Highly dynamic destination-sequenced distance vector routing (DSDV) for mobile computers[C].In Proc. of the ACM SIGCOMM Conference on Communications Architectures,Protocols and Applications,London,UK. ACM, 1994:234-244P.
[5] G. Pei,M.Gerla, T.W Chen. Fisheye state routing:A routing scheme for Ad hoc wireless networks[C]. Proc.of the IEEE International Conference on Communications(ICC),New Orleans,LA,June 2000:70-74.
[6] T.Clausen,P.Jacquet.A.Laouiti,P.Muhlethaler,et al. Optimized link state routing protocol for Ad hoc networks[C].Proc.of IEEE International Multi-Topic Conference,Lahore,Pakistan. IEEE Press, 2001:62-68.
[7] AODV[EB/OL].Http://www.ietf.cnri.reston.va.us/rfc/rfc3561
[8] DSR[EB/OL].Http://www.ietf.org/draf-ietf-manet-dsr-l0.txt.
[9] TORA[EB/OL].Http://www.ietf.org/draft-ietf-manet-toraspec-00.txt
[10] R.Dube,C.D.Rais,K.-Y.Wang,S.K.Tripathi.Signal stability based adaptive routing (SSA) for Ad hoc mobile networks[J].IEEE Personal Communications Magazine,1997,4(1):36-45
[11] Josh Broch,David Maltz,David Johnson et al.A performance comparison of multi-hop wireless ad-hoc network routing protocols[C].Proc. 4th ACM/IEEE Conf. Mobile Comp. And Net.(MobiCom’98),Oct. 1998.
[12] K.A.Ra jagopal,R.Sivakumar,N.V.Arvind,et al.A Comprehensive Solution for True Hierarchical Timing and Crosstalk Delay Signoff[C].Proc.of the 19th International Conference on VLSI Design held jointly with 5th International Conference on Embedded Systems Design,Hyderabad. Jan 2006:277-282.
[13]杨晋宁,段吉海.一种基于节点位置的Ad Hoc和蜂窝混合网络路由算法[J].现代电子技术, 2008 31(3):57-60.
[14]王庆辉,孙俊锁,王光兴.一种带移动预测的Ad-Hoc网络路由协议[J].东北大学学报(自然科学版), 2005 26(2):114-117.
[15]邓曙光,王建新,陈松乔,陈建二. MANET中一种基于移动预测的unicast路由协议[J].计算机工程与应用, 2002 38(14):152-154.
[16]史美林,英春.自组网路由协议综述[J].通信学报.2001, Vol. 22, No.11:93-104.
[17] W.Wei,A.Zakhor.Multipath Unicast and Multicast Video Communication over Wireless Ad Hoc[C].Networks.Proc. of the 1th International Conference on Broadband Networks, San Jose, CA. IEEE Oct. 2004:496-505.
[18]魏滢,白光伟.多跳Ad Hoc网络基于路由协议的拥塞控制[J].计算机应用, 2007 27(9):2221-2223.
[19]郑相全,郭伟.自组网中的负载均衡路由协议[J].计算机科学, 2004 31(11):40-45.
[20]欧阳志鹏,沈富可. Ad Hoc网络基于路由协议的拥塞控制[J].计算机工程与设计, 2006 27(16):3102-3104.
[21] C.Huang,F.Dai,J.Wu.On-Demand Location-Aided QoS Routing in Ad Hoc Networks[C].Proc. of 2004 International Conference on Parallel Processing, Montreal,Quebec, Canada.IEEE Press,Aug 2004: 502-509.
[22] Y.H.Wang,H.Z.Lin,S.M.Chang.Interference on Multipath QoS Routing for Ad Hoc Wireless Network[C].Proc. of the 24th International Conference on Distributed Computing Systems Workshops,Tokyo,Japan.IEEE Press,Mar. 2004:104-109.
[23]施荣华,崔奕芳,江玲. Ad Hoc网络中QoS路由协议算法的研究[J].计算机科学,2008 35(7):55-56.
[24] Hu Y C,Johnson D B,Perrig A.SEAD:Secure efficient distance vector routing for mobile wireless ad hoc networks[C].Proc. of WMCSA’02.Washington:IEEE Computer Society,2002:3-13.
[25] Hu Y C,Perrig A,Jhonson D B.Ariadne:A secure on-demand routing protocol for ad hoc networks[J].Wireless Networks,2005 11(1-2):21-38.
[26] Joohan Song,et al.Secure position-based routing protocol for mobile ad hoc networks[J].Ad Hoc Networks,2007 5(1):76-86.
[27]刘玉梅,郭黎利,马惠珠.一种能量有效及负载均衡的Ad hoc路由协议[J].哈尔滨工程大学学报, 2008 29(3):294-297.
[28]黄超,石为人,周彬.一种能量感知的无线移动自组网路由协议[J].计算机工程与应用, 2007 43(36):163-165.
[29]翟卫丰,顾乃杰,张建明.一个基于能量消耗的域路由协议[J].计算机工程, 2006 32(12):163-165.
[30]黄浩,吴礼发等.一种用于单向链路网络的路由算法[J].软件学报,1999, (6),636-641.
[31]邓曙光,曾朝晖,习胜丰. Ad Hoc网络中基于能源节省的单向QoS路由协议[J].计算机工程与应用,2006, (24), 118-120.
[32]邓曙光,曾朝晖,曾专武. MANET中一种基于移动预测的单向QoS路由.小型微型计算机系统,2006, (12): 2246-2250.
[33]王亮,毛玉明. AODV路由协议在单、双向链路状态下的仿真分析[C].2004年中国西部青年通信学术会议论文集, 2004, 12, 01: 82-87.
[34] Donkyun KimToh,C.-K.Institute of Electric and Electronic Engineer.RODA:a new dynamic routing protocol using dual paths to support asymmetric links in mobile ad hoc networks[J].Computer Communications and Networks,2000.
[35]金彦亮,杨宇航.分级单向ad-hoc路由协议[J].上海交通大学学报,2004, 38(2), 263-267.
[36] Morino.H,Miyoshi.T,Ogawa.M.Ad Hoc Unidirectional Routing Protocol Based on Relay Control of Route Requests[C].Autonomous Decentralized Systems, 2005. ISADS 2005. Proceedings 4-8 April 2005 Page(s):675- 680.
[37] Higaki,Hiroaki.LBSR:Routing Protocol for MANETs with Unidirectional Links[C]. Wireless and Mobile Computing, Networking and Communications, 2007.WiMOB 2007.Third IEEE International Conference on 8-10 Oct. 2007 Page(s):84-84.
[38]王松健.无线网状网络路由技术研究[D].重庆:重庆大学计算机学院,2007,4:2-17.
[39] WRP [EB/OL]. http://en.wikipedia.org/wiki/Wireless_Routing_Protocol
[40] Optimized Link State Routing Protocol[EB/OL].http://hipercom.inria.fr/olsr/
[41] Source Tree Adaptive Routing Protocol [EB/OL].http://wiki.uni.lu/secan-lab/Source-Tree+Adaptive+Routing+Protocol.html
[42] Least Overhead Routing Approach[EB/OL]. http://wiki.uni.lu/secan-lab/Least+Overhead+Routing+Approach.html
[43] Topology Broadcast based on Reverse-Path Forwarding[EB/OL]. http://www.networksorcery.com/enp/protocol/tbrpf.htm
[44] Chai-Keong Toh.Associativity-Based Routing For Ad-Hoc Mobile Networks [J]. Wireless Personal Communication Journal, vol 4, no2, March 1997.
[45] Hollerung T.D.The Cluster-Based Routing Protocol [EB/OL].http:// gauge.upb.de /pgmanet /seminar / workout/cbrp.pdf
[46] Analysis of the Zone Routing Protocol[EB/OL].http://www.netmeister.org/misc/zrp/
[47]华云,苏福德.MANET的单向链路问题[J].计算机工程与应用,2003, (8): 160-162.
[48] Ravi Prakash,M Singhal.Impact of Unidirectional Links on Wireless Ad-hoc Networks[C].In Proceedings of the DIMACS Workshop on Mobile Networking and Computing,Rutgers University,1999.
[2]张蕾. Ad hoc综述[J].电子科学技术评论, 2005(05):35-38.
[3]林蔚.移动自组网的路由技术研究[D].哈尔滨:哈尔滨工程大学计算机科学与技术学院,2006,4:12-15.
[4] C. E.Perkins,P.Bhagwat.Highly dynamic destination-sequenced distance vector routing (DSDV) for mobile computers[C].In Proc. of the ACM SIGCOMM Conference on Communications Architectures,Protocols and Applications,London,UK. ACM, 1994:234-244P.
[5] G. Pei,M.Gerla, T.W Chen. Fisheye state routing:A routing scheme for Ad hoc wireless networks[C]. Proc.of the IEEE International Conference on Communications(ICC),New Orleans,LA,June 2000:70-74.
[6] T.Clausen,P.Jacquet.A.Laouiti,P.Muhlethaler,et al. Optimized link state routing protocol for Ad hoc networks[C].Proc.of IEEE International Multi-Topic Conference,Lahore,Pakistan. IEEE Press, 2001:62-68.
[7] AODV[EB/OL].Http://www.ietf.cnri.reston.va.us/rfc/rfc3561
[8] DSR[EB/OL].Http://www.ietf.org/draf-ietf-manet-dsr-l0.txt.
[9] TORA[EB/OL].Http://www.ietf.org/draft-ietf-manet-toraspec-00.txt
[10] R.Dube,C.D.Rais,K.-Y.Wang,S.K.Tripathi.Signal stability based adaptive routing (SSA) for Ad hoc mobile networks[J].IEEE Personal Communications Magazine,1997,4(1):36-45
[11] Josh Broch,David Maltz,David Johnson et al.A performance comparison of multi-hop wireless ad-hoc network routing protocols[C].Proc. 4th ACM/IEEE Conf. Mobile Comp. And Net.(MobiCom’98),Oct. 1998.
[12] K.A.Ra jagopal,R.Sivakumar,N.V.Arvind,et al.A Comprehensive Solution for True Hierarchical Timing and Crosstalk Delay Signoff[C].Proc.of the 19th International Conference on VLSI Design held jointly with 5th International Conference on Embedded Systems Design,Hyderabad. Jan 2006:277-282.
[13]杨晋宁,段吉海.一种基于节点位置的Ad Hoc和蜂窝混合网络路由算法[J].现代电子技术, 2008 31(3):57-60.
[14]王庆辉,孙俊锁,王光兴.一种带移动预测的Ad-Hoc网络路由协议[J].东北大学学报(自然科学版), 2005 26(2):114-117.
[15]邓曙光,王建新,陈松乔,陈建二. MANET中一种基于移动预测的unicast路由协议[J].计算机工程与应用, 2002 38(14):152-154.
[16]史美林,英春.自组网路由协议综述[J].通信学报.2001, Vol. 22, No.11:93-104.
[17] W.Wei,A.Zakhor.Multipath Unicast and Multicast Video Communication over Wireless Ad Hoc[C].Networks.Proc. of the 1th International Conference on Broadband Networks, San Jose, CA. IEEE Oct. 2004:496-505.
[18]魏滢,白光伟.多跳Ad Hoc网络基于路由协议的拥塞控制[J].计算机应用, 2007 27(9):2221-2223.
[19]郑相全,郭伟.自组网中的负载均衡路由协议[J].计算机科学, 2004 31(11):40-45.
[20]欧阳志鹏,沈富可. Ad Hoc网络基于路由协议的拥塞控制[J].计算机工程与设计, 2006 27(16):3102-3104.
[21] C.Huang,F.Dai,J.Wu.On-Demand Location-Aided QoS Routing in Ad Hoc Networks[C].Proc. of 2004 International Conference on Parallel Processing, Montreal,Quebec, Canada.IEEE Press,Aug 2004: 502-509.
[22] Y.H.Wang,H.Z.Lin,S.M.Chang.Interference on Multipath QoS Routing for Ad Hoc Wireless Network[C].Proc. of the 24th International Conference on Distributed Computing Systems Workshops,Tokyo,Japan.IEEE Press,Mar. 2004:104-109.
[23]施荣华,崔奕芳,江玲. Ad Hoc网络中QoS路由协议算法的研究[J].计算机科学,2008 35(7):55-56.
[24] Hu Y C,Johnson D B,Perrig A.SEAD:Secure efficient distance vector routing for mobile wireless ad hoc networks[C].Proc. of WMCSA’02.Washington:IEEE Computer Society,2002:3-13.
[25] Hu Y C,Perrig A,Jhonson D B.Ariadne:A secure on-demand routing protocol for ad hoc networks[J].Wireless Networks,2005 11(1-2):21-38.
[26] Joohan Song,et al.Secure position-based routing protocol for mobile ad hoc networks[J].Ad Hoc Networks,2007 5(1):76-86.
[27]刘玉梅,郭黎利,马惠珠.一种能量有效及负载均衡的Ad hoc路由协议[J].哈尔滨工程大学学报, 2008 29(3):294-297.
[28]黄超,石为人,周彬.一种能量感知的无线移动自组网路由协议[J].计算机工程与应用, 2007 43(36):163-165.
[29]翟卫丰,顾乃杰,张建明.一个基于能量消耗的域路由协议[J].计算机工程, 2006 32(12):163-165.
[30]黄浩,吴礼发等.一种用于单向链路网络的路由算法[J].软件学报,1999, (6),636-641.
[31]邓曙光,曾朝晖,习胜丰. Ad Hoc网络中基于能源节省的单向QoS路由协议[J].计算机工程与应用,2006, (24), 118-120.
[32]邓曙光,曾朝晖,曾专武. MANET中一种基于移动预测的单向QoS路由.小型微型计算机系统,2006, (12): 2246-2250.
[33]王亮,毛玉明. AODV路由协议在单、双向链路状态下的仿真分析[C].2004年中国西部青年通信学术会议论文集, 2004, 12, 01: 82-87.
[34] Donkyun KimToh,C.-K.Institute of Electric and Electronic Engineer.RODA:a new dynamic routing protocol using dual paths to support asymmetric links in mobile ad hoc networks[J].Computer Communications and Networks,2000.
[35]金彦亮,杨宇航.分级单向ad-hoc路由协议[J].上海交通大学学报,2004, 38(2), 263-267.
[36] Morino.H,Miyoshi.T,Ogawa.M.Ad Hoc Unidirectional Routing Protocol Based on Relay Control of Route Requests[C].Autonomous Decentralized Systems, 2005. ISADS 2005. Proceedings 4-8 April 2005 Page(s):675- 680.
[37] Higaki,Hiroaki.LBSR:Routing Protocol for MANETs with Unidirectional Links[C]. Wireless and Mobile Computing, Networking and Communications, 2007.WiMOB 2007.Third IEEE International Conference on 8-10 Oct. 2007 Page(s):84-84.
[38]王松健.无线网状网络路由技术研究[D].重庆:重庆大学计算机学院,2007,4:2-17.
[39] WRP [EB/OL]. http://en.wikipedia.org/wiki/Wireless_Routing_Protocol
[40] Optimized Link State Routing Protocol[EB/OL].http://hipercom.inria.fr/olsr/
[41] Source Tree Adaptive Routing Protocol [EB/OL].http://wiki.uni.lu/secan-lab/Source-Tree+Adaptive+Routing+Protocol.html
[42] Least Overhead Routing Approach[EB/OL]. http://wiki.uni.lu/secan-lab/Least+Overhead+Routing+Approach.html
[43] Topology Broadcast based on Reverse-Path Forwarding[EB/OL]. http://www.networksorcery.com/enp/protocol/tbrpf.htm
[44] Chai-Keong Toh.Associativity-Based Routing For Ad-Hoc Mobile Networks [J]. Wireless Personal Communication Journal, vol 4, no2, March 1997.
[45] Hollerung T.D.The Cluster-Based Routing Protocol [EB/OL].http:// gauge.upb.de /pgmanet /seminar / workout/cbrp.pdf
[46] Analysis of the Zone Routing Protocol[EB/OL].http://www.netmeister.org/misc/zrp/
[47]华云,苏福德.MANET的单向链路问题[J].计算机工程与应用,2003, (8): 160-162.
[48] Ravi Prakash,M Singhal.Impact of Unidirectional Links on Wireless Ad-hoc Networks[C].In Proceedings of the DIMACS Workshop on Mobile Networking and Computing,Rutgers University,1999.