移动Ad Hoc网络路由协议研究
摘要
移动Ad Hoc网络是一种工作在无固定设施环境下,由一组带有无线收发装置的移动终端节点组成的多跳的临时性的自治系统。在这种环境中,由于节点的无线覆盖范围的有限性,两个无法直接通信的节点可以借助其它节点进行分组转发来进行数据通信。移动AdHoc网络节点之间通过多跳转发机制进行数据传输,因此路由协议的设计是移动AdHoc网络中非常重要的环节。
AODV协议是已经提出的适用于移动Ad Hoc网络的按需路由协议。尽管同表驱动路由协议相比,AODV具有路由开销小,系统效率高的特点,但是也有一些固有的局限性。
本文在R-AODV协议的基础上提出了一种LBR-AODV协议。该协议继承了R-AODV协议的反向路由查找机制,有效地降低了路由应答报文丢失造成的开销;引入了一种跨层的节点拥塞算法,有效地在路由查找过程中避免了拥塞节点,保证了网络的负载均衡,降低了路由开销。仿真结果表明,LBR-AODV协议在节点密度较大,拓扑变化比较频繁的条件下能够有效地降低路由开销和平均端到端时延,提高了传输成功率。
A mobile Ad Hoc network (MANET) is a collection of wireless mobile nodesdynamically forming a temporarymultiple-hop network without the use of any centralcontroller or existing net-infrastructure. In this condition, duo to the limitation of thetransmission range, nodes which could not communicate with each other directlymustuse another node to deliver the packet. Nodes in mobile ad hoc networks transmit databymulti-hop, so a routingprotocol to determine the waydata packet to be delivered isneeded. Thus, the design of routing protocol is one of the key issues of mobile ad hocnetworks.
AODV is a classical on-demand routing protocol for MANETs. Although AODVhas advantages such as low routing overhead and high efficiency compare withtable-drivenroutingprotocols,italsohavesomelimitationsofitsown.
In this paper, a novel routing protocol based on R-AODV was proposed. Theprotocol inherits the reverse routing mechanism of R-AODV which efficiently reducethe overhead caused by missing of routing request message. With a cross-layercongestion algorithm utilized in this protocol, congested nodes cam be avoided duringthe routing finding section, the load balance of the whole network and lower routingoverhead is ensured. The simulation result shows that LBR-AODV performs well indelayanddeliveryprobabilityunderdenseandrapidmovingcircumstances.
AODV协议是已经提出的适用于移动Ad Hoc网络的按需路由协议。尽管同表驱动路由协议相比,AODV具有路由开销小,系统效率高的特点,但是也有一些固有的局限性。
本文在R-AODV协议的基础上提出了一种LBR-AODV协议。该协议继承了R-AODV协议的反向路由查找机制,有效地降低了路由应答报文丢失造成的开销;引入了一种跨层的节点拥塞算法,有效地在路由查找过程中避免了拥塞节点,保证了网络的负载均衡,降低了路由开销。仿真结果表明,LBR-AODV协议在节点密度较大,拓扑变化比较频繁的条件下能够有效地降低路由开销和平均端到端时延,提高了传输成功率。
A mobile Ad Hoc network (MANET) is a collection of wireless mobile nodesdynamically forming a temporarymultiple-hop network without the use of any centralcontroller or existing net-infrastructure. In this condition, duo to the limitation of thetransmission range, nodes which could not communicate with each other directlymustuse another node to deliver the packet. Nodes in mobile ad hoc networks transmit databymulti-hop, so a routingprotocol to determine the waydata packet to be delivered isneeded. Thus, the design of routing protocol is one of the key issues of mobile ad hocnetworks.
AODV is a classical on-demand routing protocol for MANETs. Although AODVhas advantages such as low routing overhead and high efficiency compare withtable-drivenroutingprotocols,italsohavesomelimitationsofitsown.
In this paper, a novel routing protocol based on R-AODV was proposed. Theprotocol inherits the reverse routing mechanism of R-AODV which efficiently reducethe overhead caused by missing of routing request message. With a cross-layercongestion algorithm utilized in this protocol, congested nodes cam be avoided duringthe routing finding section, the load balance of the whole network and lower routingoverhead is ensured. The simulation result shows that LBR-AODV performs well indelayanddeliveryprobabilityunderdenseandrapidmovingcircumstances.
引文
[1] Leiner B M, Nelson D L , Tobagi F A, "Issues in Packet Radio Network Design",Proceedings IEEE,1987, 75(1), pp.6-20
[2] David A. Beyer, "Accomplishments of the DARPA Survivable Adaptive NetworksSURAN Program", Proceedings of the IEEE MILCOM Conference, 1990
[3] Barry M. Leiner, Robert Ruth, Ambatipudi R. Sastry, "Goals and Challenges of theDARPA GloMo Program", IEEE Personal Communications, Vol.3, No.6, 1996
[4] Internet Engineering Task Force (IETF) Mobile Ad Hoc Networks (MANET)Working Group Charter, http://www.ieft.org/html.charters/manet-charter.html, May,2000
[5] R.Ramanathan, Jason Redi, "A Brief Overview of Mobile Ad Hoc Networks:Challenges and Directions", IEEE Communications Magazine, 50th AnniversaryCommemorative Issue. New York USA, Cisco Press, 2002, pp.20-30
[6] J.Broch, D.A.Maltz, D.B.Johnson, "A Performance Comparison of Multi-hopWireless Ad Hoc Network Routing Protocols", Proceedings of ACM/IEEEMOBICOM'98, Dallas, TX, ACM Press, 1998, pp.85-97
[7] Perkins C E, Bhagwat P“Highly Dynamic Destination-sequenced Distance-VectorRouting (DSDV) for Mobile Computers”, ACMSIGCOMM' 94，London, Sep.19
[8] Murthy S, Barcia-lama-Aceves J.J, "An Efficient Routing Protocol(WRP) forWireless Networks", ACM Mobile Networks and Applications Journal, Specialissue on Routing in Mobile Communication Networks, 1996, 1(2), pp.183-193
[9] Perkins C E，Belding-Royer E, Das S,“Ad hoc On-Demand Distance Vector(AODV)Routing”, IETF RFC 3651，July 2003
[10]Johnson D B，Maltz D A，Hu Y C,“The Dynamic Source Routing Protocol forMobile ad hoc Networks (DSR)”. IETF Internet Draft, draft-ietf-manet-dsr- 10.txt,2004
[11]Park V D, Corson M S, "Temporally-Ordered Routing Algorithm (TORA) version1 functional specification", IETF Draft, draft-ietf-manet-tora-spec-04.txt, 2001
[12]Pottie G. J,“Wireless Senor Networks(WSN)”, Proc. IEEE Information TheoryWorkshop, Killarney, Ireland, 139-140, June, 1998
[13]Ratnjee P, Liljana G, "Research Challenges for Wireless Personal Area Networks",Proceedings of 3rd ICICS, Singapore, October 2001
[14]Olga Ratsimor, Tim Finin, Anupam Joshi, "A Framework for Intelligent Marketingin Mobile Peer-To-Peer Environment", The 5th ICEC, October 2003
[15]Zygmunt J.Haas, Siamak Tabrizi,“On Some Challenges and Design Choices in AdHoc Communication”, IEEE MILCOM’98, October, 1998
[16]C. L. Fullmer, J. J. Garcia-Luna-Aceves,“Solutions to Hidden Terminal ProblemsinWireless Networks”, Proc. of ACM SIGCOMM’97, 1997
[17]Zhou L, Haas Z,“Securing Ad Hoc Networks”, IEEE Network, 1999, 13(6),pp.24-30
[18]Sobrinho.J L, Krishnakumar A S,“Quality of Service in Ad Hoc Carrier SenseMultiple Access Networks”, IEEE Journal on Selected Areas in Communication,August, 1999
[19]Wenli Chen, Nitin Jain, and Suresh Singh,“ANMP:Ad Hoc Network ManagementProtocol”, IEEE Journal on Selected Areas in Communication, 1999, 17(8)
[20] Scott Croson M, Joseph P.Marcher and Gregory H.Cirincione,“Internet BasedMobile Ad Hoc Networking”, IEEE Internet Computing, July/August, 1999
[21]C.C. Chiang, "Routing in Clustered Multi-hop, Mobile Wireless Networks(CGSR)with Fading Channel", Proc. IEEE SICON'97, Apr, 1997, pp.197-211
[22]Jacquet P , Muhlethaler P, Clausen T,“Optimized Link State Routing Protocol(OLSR) for Ad Hoc Networks”, Proc of IEEE INMIC’01, Lahore, Pakistan, 2001,pp.62-68
[23]A B McDonald,“A Mobility-based Framework for Adaptive Clustering inWireless Ad-Hoc Networks”, IEEE Journal on Selected Areas in Communications,1999, 17(8), pp.1466-1487
[24]C-K Toh,“Associativity Based Long-Lived Routing(ABR)”, Special Issue onMobil Networking & Computing Systems, 1997:4(1)
[25]Hass Z J,“The Zone Routing Protocol(ZRP) for Ad Hoc Network”, Internet Draft,draft-zone-routing-protocol-00.txt, Nov.1997,Work in progress
[26]Pei Guangyu, Gerla Mario, Chen Tsu-Wei,“Fisheye State Routing(FSR) in MobileAd Hoc Networks”, Proc of ICC’2000, Taiwan, 2000, pp.71-78
[27]Chonggun Kim, Elmurod Talipov, Byoungchul Ahn,“A Reversed RoutingProtocol in Ad Hoc Mobile Networks”, EUC Workshops 2006, LNCS 4097, pp.522-531, 2006
[28]Zheng Xiangquan, Guo Wei,“Load-Balanced Routing Protocols in Ad HocNetworks”, Journal of Computer Science, 2004, 31(11), pp. 40-45 (in Chinese)
[29]Perkins D D, Hughes H D, Owen C B,“Factors Affecting the Performance of AdHoc Networks", IEEE International Conference, 2002, 4, pp.2048-2052
[30]Zhang Linfang, Zhao Zenghua, Shu Yantai, "Load balancing of Multi-path SourceRouting in Ad Hoc Networks", IEEE International Conference on Volume 5,pp.3197-3201, 2002, 5
[31]Pham P, Perreau S, "Multi-path Routing Protocol with Load Balancing Policy inMobile Ad Hoc Network", IFIP Int'l Conference on Mobile and WirelessCommunications Networks, Sept , 2002
[32]Nasipuri A, Castaneda R, Das S, "Performance of Multi-path Routing forOn-Demand Protocols in Mobile Ad Hoc Networks", ACM/Kluwer MobileNetworks and Applications (MANET) Journal, 2001,6(4), pp.339-349
[33]Ganjali Y, Keshavarzian A, "Load balancing in Ad Hoc Networks:single-pathRouting v.s. Multi-path Routing", INFOCOM 2004, 23th Annual Joint Conferenceof the IEEE Computer and Communications Societies, 2004, 2, pp.1120-1125
[34]A.Zhou, H.Hassanein, "Load-Balanced Wireless Ad Hoc Routing(LBAR)", Proc.Canadian Conf. and Computer Engineering, Toronto: Central Canada Council ofIEEE, Canada, 2001, pp.1157-1161
[35]Sung-Ju-Lee, Mario Gerla, "Dynamic Load-Aware Routing(DLAR) in Ad HocNetworks", Proc. IEEE Int'l Conf. Communications, Helsinki, Finland: IEEECommunication Society Press, 2001, pp.3206-3210
[36]K.Wu, J.Harms, "Load-Sensitive Routing for Mobile Ad Hoc Networks", Proc.10th IEEE Int'l Conf. Computer Communications and Network Proceedings, LosAlamitos, California: IEEE Computer Society Press, 2001, pp.540-546
[37]Joo-Han Song, V. Wong, V.C.M.Leung, "Load-Aware On-Demand RoutingProtocol for Mobile Ad Hoc Networks", Proc. 57th IEEE Semiannual VehicularTechnology Conference, Piscataway, NJ, IEEE Press, 2003, pp.1753-1757
[38]Yanjung Yi, Tack Jin Kwon, Mario Gerla, "A Load-Aware Routing Based on LocalInformation", IEEE Int'l Symposium on Personal, Indoor and Mobile RadioCommunications, San Diego, USA ,2001
[39]Yanjung Yi, Mario Gerla, Tack Jin Kwon, "The Selective Intermediate NodesScheme for Ad Hoc On-Demand Routing Protocols", Proc. IEEE Int'l Conf.Communications, Piscataway, NJ : IEEE Press, 2002, pp.3191-3196
[40]OPNET Modeler, http://www.opnet.com/products/modeler/home.html.2003-10-31
[41]Perkins C, Royer E, Das S, "Performance Comparison of two On-Demand RoutingProtocols for Ad Hoc Networks", IEEE Personal Communications, 2001, 8 (1),pp.16- 28
[42]郑少仁，王海涛，赵志峰，米志超，黎宁，“Ad Hoc网络技术”，人民邮电出版社，2005年1月第1版
[43]陈敏，“OPNET网络仿真”，2004年4月第1版，清华大学出版社
[44]郑相全等译，“无线自组织网络技术使用教程”，清华大学出版社，2001
[45]赵志峰，郑少仁，“Ad Hoc网络体系结构研究”，电信科学，Vol.17，No.1，2001年1月
[2] David A. Beyer, "Accomplishments of the DARPA Survivable Adaptive NetworksSURAN Program", Proceedings of the IEEE MILCOM Conference, 1990
[3] Barry M. Leiner, Robert Ruth, Ambatipudi R. Sastry, "Goals and Challenges of theDARPA GloMo Program", IEEE Personal Communications, Vol.3, No.6, 1996
[4] Internet Engineering Task Force (IETF) Mobile Ad Hoc Networks (MANET)Working Group Charter, http://www.ieft.org/html.charters/manet-charter.html, May,2000
[5] R.Ramanathan, Jason Redi, "A Brief Overview of Mobile Ad Hoc Networks:Challenges and Directions", IEEE Communications Magazine, 50th AnniversaryCommemorative Issue. New York USA, Cisco Press, 2002, pp.20-30
[6] J.Broch, D.A.Maltz, D.B.Johnson, "A Performance Comparison of Multi-hopWireless Ad Hoc Network Routing Protocols", Proceedings of ACM/IEEEMOBICOM'98, Dallas, TX, ACM Press, 1998, pp.85-97
[7] Perkins C E, Bhagwat P“Highly Dynamic Destination-sequenced Distance-VectorRouting (DSDV) for Mobile Computers”, ACMSIGCOMM' 94，London, Sep.19
[8] Murthy S, Barcia-lama-Aceves J.J, "An Efficient Routing Protocol(WRP) forWireless Networks", ACM Mobile Networks and Applications Journal, Specialissue on Routing in Mobile Communication Networks, 1996, 1(2), pp.183-193
[9] Perkins C E，Belding-Royer E, Das S,“Ad hoc On-Demand Distance Vector(AODV)Routing”, IETF RFC 3651，July 2003
[10]Johnson D B，Maltz D A，Hu Y C,“The Dynamic Source Routing Protocol forMobile ad hoc Networks (DSR)”. IETF Internet Draft, draft-ietf-manet-dsr- 10.txt,2004
[11]Park V D, Corson M S, "Temporally-Ordered Routing Algorithm (TORA) version1 functional specification", IETF Draft, draft-ietf-manet-tora-spec-04.txt, 2001
[12]Pottie G. J,“Wireless Senor Networks(WSN)”, Proc. IEEE Information TheoryWorkshop, Killarney, Ireland, 139-140, June, 1998
[13]Ratnjee P, Liljana G, "Research Challenges for Wireless Personal Area Networks",Proceedings of 3rd ICICS, Singapore, October 2001
[14]Olga Ratsimor, Tim Finin, Anupam Joshi, "A Framework for Intelligent Marketingin Mobile Peer-To-Peer Environment", The 5th ICEC, October 2003
[15]Zygmunt J.Haas, Siamak Tabrizi,“On Some Challenges and Design Choices in AdHoc Communication”, IEEE MILCOM’98, October, 1998
[16]C. L. Fullmer, J. J. Garcia-Luna-Aceves,“Solutions to Hidden Terminal ProblemsinWireless Networks”, Proc. of ACM SIGCOMM’97, 1997
[17]Zhou L, Haas Z,“Securing Ad Hoc Networks”, IEEE Network, 1999, 13(6),pp.24-30
[18]Sobrinho.J L, Krishnakumar A S,“Quality of Service in Ad Hoc Carrier SenseMultiple Access Networks”, IEEE Journal on Selected Areas in Communication,August, 1999
[19]Wenli Chen, Nitin Jain, and Suresh Singh,“ANMP:Ad Hoc Network ManagementProtocol”, IEEE Journal on Selected Areas in Communication, 1999, 17(8)
[20] Scott Croson M, Joseph P.Marcher and Gregory H.Cirincione,“Internet BasedMobile Ad Hoc Networking”, IEEE Internet Computing, July/August, 1999
[21]C.C. Chiang, "Routing in Clustered Multi-hop, Mobile Wireless Networks(CGSR)with Fading Channel", Proc. IEEE SICON'97, Apr, 1997, pp.197-211
[22]Jacquet P , Muhlethaler P, Clausen T,“Optimized Link State Routing Protocol(OLSR) for Ad Hoc Networks”, Proc of IEEE INMIC’01, Lahore, Pakistan, 2001,pp.62-68
[23]A B McDonald,“A Mobility-based Framework for Adaptive Clustering inWireless Ad-Hoc Networks”, IEEE Journal on Selected Areas in Communications,1999, 17(8), pp.1466-1487
[24]C-K Toh,“Associativity Based Long-Lived Routing(ABR)”, Special Issue onMobil Networking & Computing Systems, 1997:4(1)
[25]Hass Z J,“The Zone Routing Protocol(ZRP) for Ad Hoc Network”, Internet Draft,draft-zone-routing-protocol-00.txt, Nov.1997,Work in progress
[26]Pei Guangyu, Gerla Mario, Chen Tsu-Wei,“Fisheye State Routing(FSR) in MobileAd Hoc Networks”, Proc of ICC’2000, Taiwan, 2000, pp.71-78
[27]Chonggun Kim, Elmurod Talipov, Byoungchul Ahn,“A Reversed RoutingProtocol in Ad Hoc Mobile Networks”, EUC Workshops 2006, LNCS 4097, pp.522-531, 2006
[28]Zheng Xiangquan, Guo Wei,“Load-Balanced Routing Protocols in Ad HocNetworks”, Journal of Computer Science, 2004, 31(11), pp. 40-45 (in Chinese)
[29]Perkins D D, Hughes H D, Owen C B,“Factors Affecting the Performance of AdHoc Networks", IEEE International Conference, 2002, 4, pp.2048-2052
[30]Zhang Linfang, Zhao Zenghua, Shu Yantai, "Load balancing of Multi-path SourceRouting in Ad Hoc Networks", IEEE International Conference on Volume 5,pp.3197-3201, 2002, 5
[31]Pham P, Perreau S, "Multi-path Routing Protocol with Load Balancing Policy inMobile Ad Hoc Network", IFIP Int'l Conference on Mobile and WirelessCommunications Networks, Sept , 2002
[32]Nasipuri A, Castaneda R, Das S, "Performance of Multi-path Routing forOn-Demand Protocols in Mobile Ad Hoc Networks", ACM/Kluwer MobileNetworks and Applications (MANET) Journal, 2001,6(4), pp.339-349
[33]Ganjali Y, Keshavarzian A, "Load balancing in Ad Hoc Networks:single-pathRouting v.s. Multi-path Routing", INFOCOM 2004, 23th Annual Joint Conferenceof the IEEE Computer and Communications Societies, 2004, 2, pp.1120-1125
[34]A.Zhou, H.Hassanein, "Load-Balanced Wireless Ad Hoc Routing(LBAR)", Proc.Canadian Conf. and Computer Engineering, Toronto: Central Canada Council ofIEEE, Canada, 2001, pp.1157-1161
[35]Sung-Ju-Lee, Mario Gerla, "Dynamic Load-Aware Routing(DLAR) in Ad HocNetworks", Proc. IEEE Int'l Conf. Communications, Helsinki, Finland: IEEECommunication Society Press, 2001, pp.3206-3210
[36]K.Wu, J.Harms, "Load-Sensitive Routing for Mobile Ad Hoc Networks", Proc.10th IEEE Int'l Conf. Computer Communications and Network Proceedings, LosAlamitos, California: IEEE Computer Society Press, 2001, pp.540-546
[37]Joo-Han Song, V. Wong, V.C.M.Leung, "Load-Aware On-Demand RoutingProtocol for Mobile Ad Hoc Networks", Proc. 57th IEEE Semiannual VehicularTechnology Conference, Piscataway, NJ, IEEE Press, 2003, pp.1753-1757
[38]Yanjung Yi, Tack Jin Kwon, Mario Gerla, "A Load-Aware Routing Based on LocalInformation", IEEE Int'l Symposium on Personal, Indoor and Mobile RadioCommunications, San Diego, USA ,2001
[39]Yanjung Yi, Mario Gerla, Tack Jin Kwon, "The Selective Intermediate NodesScheme for Ad Hoc On-Demand Routing Protocols", Proc. IEEE Int'l Conf.Communications, Piscataway, NJ : IEEE Press, 2002, pp.3191-3196
[40]OPNET Modeler, http://www.opnet.com/products/modeler/home.html.2003-10-31
[41]Perkins C, Royer E, Das S, "Performance Comparison of two On-Demand RoutingProtocols for Ad Hoc Networks", IEEE Personal Communications, 2001, 8 (1),pp.16- 28
[42]郑少仁，王海涛，赵志峰，米志超，黎宁，“Ad Hoc网络技术”，人民邮电出版社，2005年1月第1版
[43]陈敏，“OPNET网络仿真”，2004年4月第1版，清华大学出版社
[44]郑相全等译，“无线自组织网络技术使用教程”，清华大学出版社，2001
[45]赵志峰，郑少仁，“Ad Hoc网络体系结构研究”，电信科学，Vol.17，No.1，2001年1月