Ad Hoc网络中按需路由协议的研究与改进
摘要
随着科技的发展，便携式计算机和掌上型电脑日益普遍，无线通信技术得到迅速发展。在某些场合，例如，战场上部队快速展开和推进、发生地震活水灾后的营救，需要一种不依赖于任何预先架设的网络设施的通信技术，Ad Hoc网络应运而生。Ad Hoc网络是移动网络的一种特殊形式，不需要固定的基站，由一组带有无线收发装置的自主的无线节点或终端通过相互合作形成的网络，是一种自创造、自组织和自管理的网络。
在Ad Hoc网络中，每一个主机都必须同时作为路由器。而且网络中的节点可以任意移动，导致Ad Hoc网络拓扑结构不可预测的频繁变化，路由协议就承担起及时维护和重建路径的工作。由于Ad Hoc网络的特殊特性使得传统的距离向量和链路状态路由协议并不适用于拓扑结构高度动态变化Ad Hoc网络。自从1970年美国国防部高级研究规划署资助了一项特别的研究——分组无线网络开始，Ad Hoc移动网络的大量协议就在不断的开发和发展中。Ad Hoc网络路由机制必须适应网络三个不断变化的基本特征：移动节点的总体密度，节点到节点的拓扑，网络的使用模式。
目前Ad Hoc网络的路由协议有表驱动路由协议和按需路由协议。从移动自组网的移动性，拓扑动态性，带宽受限，功率约束等特点来看，按需驱动路由更能适应移动Ad Hoc网络的需要。
本文首先阐述了课题研究的意义、目的和国内外研究现状及发展趋势。然后基于无线移动自组织网的网络环境，对多种Ad Hoc网络路由协议进行分析比较。采用AODV路由协议作为网络层协议，并且改进了传统的AODV路由协议算法，形成了改进的OAODV路由协议算法。
OAODV协议中，路由表添加了记录前两跳和后两跳的域。这样，在路由发现过程通过报文携带的信息，记录下路由及反向路由的前两跳信息。在发现断路需要进行局部修复时，断链处的下游节点发送修复信息到其前两跳。这样不仅增大了局部修复成功的概率，并且在发生断路后能快速修复，从而减少了端到端延迟，提高了数据报文的成功发送率。
本文采用目前流行的仿真平台NS2，在此平台的基础上，实现了OAODV路由协议算法。通过仿真比较传统的AODV路由协议和改进的OAODV路由协议的性能，验证了OAODV协议算法的性能优于原AODV协议。
With the development of science and technology, portable computer and palmtop computer are increasingly prevalent, and the wireless communication technology develops promptly. In some cases, for instance, the rapid expansion of the army in a war, the rescue after earthquake or flood, it needs one communication technology that needn't depend on any network facility erected beforehand. Then Ad Hoc network emerge as the times require. Ad Hoc network is one special kind of mobile networks that don't need fixed basestation. It's a self-creation, self-organization and self-supervisory network that formed by the cooperation of a boodle of autonomic wireless nodes or terminals with wireless R-T units.
In Ad Hoc network, every host must be a router at the same time. And nodes in the network could move discretionarily, which make the topology change frequently and the routing protocol be expected to reconstructing and maintaining routing path in time. Because of the highly dynamic variation of topology in Ad Hoc network, the conventional distance vector routing protocols and link status routing protocols are not suitable. Since 1970 year, DARPA subsidized one extraordinary research—Ad Hoc network, a lot of protocols of Ad Hoc are under exploitating and developing. The route mechanism of Ad Hoc network should conform to three basic features: the population density of mobile node, the topology of nodes, and the operating mode of network.
There are two kind of routing protocols for Ad Hoc network: table-driven and on-demand routing protocol. Considering the mobility, dynamic of topology, bandwidth limitation and power restriction, on-demand routing protocols are more suitable for Ad Hoc network.
The thesis firstly described the significance and its' target, it also describes the current status of the schedule. And then through analyzing and comparing many routing protocols of Ad Hoc Network, an optimized protocol: OAODV is presented which is preformed by AODV routing protocol.
Rout table in OAODV is extended by adding two fields to save the previous two hop and the next two hop. And then, according the discovery packets, marked down the previous two hop of the router and the reverse router. When break occurred and need to local repair, the downstream node of the break point send the repair packets to its previous two hop. Thus can not only increase the probability of success, also repair the router immediately which decreased the end-to-end delay and increased the data delivery ratio.
Simulation with different scenes is completed based on NS2, the popular simulated formwork, and performance of OAODV is analyzed according the data obtained by simulation to show that it is superior to the AODV.
This thesis is supported by National Natural Science Foundation of China (Projects No: 90304018, 60672137) and Specialized Research Fund for the Doctoral Program Foundation of Ministry of Education of China Under Gram (No. 20060497015 ).
在Ad Hoc网络中，每一个主机都必须同时作为路由器。而且网络中的节点可以任意移动，导致Ad Hoc网络拓扑结构不可预测的频繁变化，路由协议就承担起及时维护和重建路径的工作。由于Ad Hoc网络的特殊特性使得传统的距离向量和链路状态路由协议并不适用于拓扑结构高度动态变化Ad Hoc网络。自从1970年美国国防部高级研究规划署资助了一项特别的研究——分组无线网络开始，Ad Hoc移动网络的大量协议就在不断的开发和发展中。Ad Hoc网络路由机制必须适应网络三个不断变化的基本特征：移动节点的总体密度，节点到节点的拓扑，网络的使用模式。
目前Ad Hoc网络的路由协议有表驱动路由协议和按需路由协议。从移动自组网的移动性，拓扑动态性，带宽受限，功率约束等特点来看，按需驱动路由更能适应移动Ad Hoc网络的需要。
本文首先阐述了课题研究的意义、目的和国内外研究现状及发展趋势。然后基于无线移动自组织网的网络环境，对多种Ad Hoc网络路由协议进行分析比较。采用AODV路由协议作为网络层协议，并且改进了传统的AODV路由协议算法，形成了改进的OAODV路由协议算法。
OAODV协议中，路由表添加了记录前两跳和后两跳的域。这样，在路由发现过程通过报文携带的信息，记录下路由及反向路由的前两跳信息。在发现断路需要进行局部修复时，断链处的下游节点发送修复信息到其前两跳。这样不仅增大了局部修复成功的概率，并且在发生断路后能快速修复，从而减少了端到端延迟，提高了数据报文的成功发送率。
本文采用目前流行的仿真平台NS2，在此平台的基础上，实现了OAODV路由协议算法。通过仿真比较传统的AODV路由协议和改进的OAODV路由协议的性能，验证了OAODV协议算法的性能优于原AODV协议。
With the development of science and technology, portable computer and palmtop computer are increasingly prevalent, and the wireless communication technology develops promptly. In some cases, for instance, the rapid expansion of the army in a war, the rescue after earthquake or flood, it needs one communication technology that needn't depend on any network facility erected beforehand. Then Ad Hoc network emerge as the times require. Ad Hoc network is one special kind of mobile networks that don't need fixed basestation. It's a self-creation, self-organization and self-supervisory network that formed by the cooperation of a boodle of autonomic wireless nodes or terminals with wireless R-T units.
In Ad Hoc network, every host must be a router at the same time. And nodes in the network could move discretionarily, which make the topology change frequently and the routing protocol be expected to reconstructing and maintaining routing path in time. Because of the highly dynamic variation of topology in Ad Hoc network, the conventional distance vector routing protocols and link status routing protocols are not suitable. Since 1970 year, DARPA subsidized one extraordinary research—Ad Hoc network, a lot of protocols of Ad Hoc are under exploitating and developing. The route mechanism of Ad Hoc network should conform to three basic features: the population density of mobile node, the topology of nodes, and the operating mode of network.
There are two kind of routing protocols for Ad Hoc network: table-driven and on-demand routing protocol. Considering the mobility, dynamic of topology, bandwidth limitation and power restriction, on-demand routing protocols are more suitable for Ad Hoc network.
The thesis firstly described the significance and its' target, it also describes the current status of the schedule. And then through analyzing and comparing many routing protocols of Ad Hoc Network, an optimized protocol: OAODV is presented which is preformed by AODV routing protocol.
Rout table in OAODV is extended by adding two fields to save the previous two hop and the next two hop. And then, according the discovery packets, marked down the previous two hop of the router and the reverse router. When break occurred and need to local repair, the downstream node of the break point send the repair packets to its previous two hop. Thus can not only increase the probability of success, also repair the router immediately which decreased the end-to-end delay and increased the data delivery ratio.
Simulation with different scenes is completed based on NS2, the popular simulated formwork, and performance of OAODV is analyzed according the data obtained by simulation to show that it is superior to the AODV.
This thesis is supported by National Natural Science Foundation of China (Projects No: 90304018, 60672137) and Specialized Research Fund for the Doctoral Program Foundation of Ministry of Education of China Under Gram (No. 20060497015 ).
引文
[1] 李腊元，李春林．计算机网络技术(第二版)．北京，国防工业出版社，2004．26～28．
[2] R Ramanathan, Jason Redi. A Brief Overview of Mobile Ad Hoc Networks: Challenges ant Directions. IEEE Communications Magazine, 50th Anniversary Commemorative lssue 2002,(5).
[3] 王金龙，王呈贵．Ad Hoc移动无线网络．国防工业出版社，2004．5．3～5．
[4] 孙宝林，李腊元．多跳无线Ad Hoc路由协议技术研究．小型微型计算机系统，2004，25(10)：1737～1741
[5] 史美林，英春．自组网路由协议综述，通信学报，2001(11)：93～103．
[6] Dainiel Lang．A comprehensive overview about selected Ad Hoc Networking Routing Protocols．March 14，2003．
[7] 孙宝林，李腊元，李相棚．移动Ad Hoc网络多播路由协议的研究进展．计算机工程与应用，2004，40(32)：139～143
[8] 桂超，孙宝林，王虹．无线移动Ad Hoc网络的路由技术研究．计算机系统应用，(5)，2005．
[9] 廖登．基于NS2的移动Ad Hoc网络典型网络协议比较．邵阳学院学报(自然科学版)，2(3)，2005年9月．
[10] 肖书成，邱珊．Adhoc网络及其路由性能研究．重庆邮电学院学报，2004，16(3)：102～107
[11] 臧婉瑜，于勐，谢立，孙钟秀．按需式Ad Hoc网络路由协议的研究进展．计算机学报，25(10)，2002年10月．
[12] 张禄林，李承恕．MANET路由选择协议的比较分析研究．电子学报．2000(11)：88～92．
[13] 孙宝林，李腊元．Ad Hoc网络QoS多播路由协议．计算机学报，2004，27(10)：1402～1407
[14] Johnson D B. Routing in Ad Hoc networks of mobile hosts[A]. Proceedings of Work shop on Mobile Computing Systems and Applications[C]. 1994.158～163.
[15] G Pei, M Gerla, T-W chen, Fisheye state routing: A routing scheme for ad hoc wireless networks. The IEEE International Conference Communications (ICC), NewOrleans, LA, 2000.
[16] C E PERKINS, P BHAGWAT. Highly Dynamic Destination-Sequenced Distance-Vector Routing (DSDV) for Mobile Computer. In: Proc ACMSIGCOMM'94, 1994.8.
[17] 张远．DSDV算法实现及其性能分析．移动通信2004／S2
[18] SMURTHY, GARCIA2LUNA2ACEVES J J. An efficient routing protocol for wireless networks. ACM Balzer Mobile Networks and Applications (Special Issue on Routing in Mobile Communication Networks), 1996, 1 (2).
[19] Chiang CC, Wu HK, Liu W, GerlaM. Routing in clustered multihop mobile wireless networks with fading channel[C]. Proceedings of IEEESICON'97, Apr1997, 197～211.
[20] Johnson D, Maltz D. Dynamic source routing in Ad hoc wireless networks[A]. Mobile Computing, Im ielinski T, Korth H, Eds, Kluwer[C]. 1996.153～181
[21] Charles E. Perkins, Elizabeth M. Royer, Samir R. Das and Mahesh K. Marina. Performance Comparison of Two On-Demand Routing Protocols for Ad Hoc Networks. IEEE Personal Communications, February 2001
[22] Perkins C E, Royer E M. Ad Hoc on demand distance vector routing[A]. IEEE WMCSA 1999[C]. 1999.90～100
[23] C, Perkins, E. Belding-Royer, S. Das. Ad Hoc On-Demand Distance Vector (AODV) Routing. 3561. July 2003
[24] NIST Kernel AODV Implementation, http://w3.antd.nist.gov/wctg/aodv kernel
[25] Multicast Ad Hoc On-Demand Distance Vector(MAODV) Routing draft-ietf-manet-maodv-00.txt
[26] Elizabeth M. Royer, Charles E. Perkins. "Multicast Operation of the Ad-hoc On-demand Distance Vector Routing Protocol"
[27] 王亮，朱秋萍，马丽霞．Ad Hoc网络DSR路由协议的优化．武汉大学学报(理学版)June 2005
[28] 王晓燕，刘乃安．一种改进的多路径DSR协议．电子科技2005年第2期
[29] 吴东亚，侯紫峰，侯朝桢．移动自组网DSR协议路径缓存策略优化．计算机工程与应用．Sep 2004
[30] 陈曙光，李霞．一种高效的Ad Hoc网络AODV改进路由协议．东南大学学报(自然科学版)Mar．2003
[31] 郑相全，郭伟，李帆．自组网AODV路由协议中断链修复的改进．电子科技大学学报Oct．2003
[32] Lee S J, Mario G. AODV-BR: Backup Routing in Ad Hoc Networks[C]. Wireless Communications and Networking Conference,2000. WCNC. 2000 IEEE, 2000, 3: 1311～1316
[33] 苏静．移动Ad Hoc网中多信道AODV路由协议研究．电子科技大学硕士学位论文
[34] 卢昊，无线移动自组织网的路由技术研究[D]，成都，电子科技大学，2004-5-31
[35] 杨锦亚，郭虹，胡捍英．自组网路由协议性能比较．微计算机信息，2006，22(24)：196～198．
[36] Elizabeth M. Royerand Toh CK. A review of current routing protocols for Ad Hoc mobile wireless networks [J]. IEEE Personal Communications Magazine, Apr1999, 46～55.
[37] 胡罡．Ad Hoc路由协议的仿真及优化技术．[硕士学位论文]．长沙：国防科学技术大学研究生院，2004
[38] 吴继春．Ad Hoc网络路由协议的研究与NS2仿真：[硕士学位论文]．武汉：武汉理工大学计算机学院，2005
[39] 江李峰，于全，戴浩，孙小东．移动Ad Hoc网络的仿真框架．系统仿真学报，2002，14(8)：1100～1108
[40] Information Sciences Institute. The Network Simulator-ns-2. http://www.isi.edu/nsnam/ns/idex.html. 2004.6
[41] 俊洪，杨洋．网络仿真方法利OPNET仿真技术．计算机工程，2004，30(5)：105～108
[42] 徐雷鸣，庞博，赵耀．NS与网络模拟．人民邮电出版社．2003
[43] The Network Simulator ns-2[EB/OL], http://www.isi.edu/nsnam/ns/, 2005.
[44] Lee Breslau, Deborah Estrin etc. Advances in Network Simulation. IEEE Computer 2000(5)
[2] R Ramanathan, Jason Redi. A Brief Overview of Mobile Ad Hoc Networks: Challenges ant Directions. IEEE Communications Magazine, 50th Anniversary Commemorative lssue 2002,(5).
[3] 王金龙，王呈贵．Ad Hoc移动无线网络．国防工业出版社，2004．5．3～5．
[4] 孙宝林，李腊元．多跳无线Ad Hoc路由协议技术研究．小型微型计算机系统，2004，25(10)：1737～1741
[5] 史美林，英春．自组网路由协议综述，通信学报，2001(11)：93～103．
[6] Dainiel Lang．A comprehensive overview about selected Ad Hoc Networking Routing Protocols．March 14，2003．
[7] 孙宝林，李腊元，李相棚．移动Ad Hoc网络多播路由协议的研究进展．计算机工程与应用，2004，40(32)：139～143
[8] 桂超，孙宝林，王虹．无线移动Ad Hoc网络的路由技术研究．计算机系统应用，(5)，2005．
[9] 廖登．基于NS2的移动Ad Hoc网络典型网络协议比较．邵阳学院学报(自然科学版)，2(3)，2005年9月．
[10] 肖书成，邱珊．Adhoc网络及其路由性能研究．重庆邮电学院学报，2004，16(3)：102～107
[11] 臧婉瑜，于勐，谢立，孙钟秀．按需式Ad Hoc网络路由协议的研究进展．计算机学报，25(10)，2002年10月．
[12] 张禄林，李承恕．MANET路由选择协议的比较分析研究．电子学报．2000(11)：88～92．
[13] 孙宝林，李腊元．Ad Hoc网络QoS多播路由协议．计算机学报，2004，27(10)：1402～1407
[14] Johnson D B. Routing in Ad Hoc networks of mobile hosts[A]. Proceedings of Work shop on Mobile Computing Systems and Applications[C]. 1994.158～163.
[15] G Pei, M Gerla, T-W chen, Fisheye state routing: A routing scheme for ad hoc wireless networks. The IEEE International Conference Communications (ICC), NewOrleans, LA, 2000.
[16] C E PERKINS, P BHAGWAT. Highly Dynamic Destination-Sequenced Distance-Vector Routing (DSDV) for Mobile Computer. In: Proc ACMSIGCOMM'94, 1994.8.
[17] 张远．DSDV算法实现及其性能分析．移动通信2004／S2
[18] SMURTHY, GARCIA2LUNA2ACEVES J J. An efficient routing protocol for wireless networks. ACM Balzer Mobile Networks and Applications (Special Issue on Routing in Mobile Communication Networks), 1996, 1 (2).
[19] Chiang CC, Wu HK, Liu W, GerlaM. Routing in clustered multihop mobile wireless networks with fading channel[C]. Proceedings of IEEESICON'97, Apr1997, 197～211.
[20] Johnson D, Maltz D. Dynamic source routing in Ad hoc wireless networks[A]. Mobile Computing, Im ielinski T, Korth H, Eds, Kluwer[C]. 1996.153～181
[21] Charles E. Perkins, Elizabeth M. Royer, Samir R. Das and Mahesh K. Marina. Performance Comparison of Two On-Demand Routing Protocols for Ad Hoc Networks. IEEE Personal Communications, February 2001
[22] Perkins C E, Royer E M. Ad Hoc on demand distance vector routing[A]. IEEE WMCSA 1999[C]. 1999.90～100
[23] C, Perkins, E. Belding-Royer, S. Das. Ad Hoc On-Demand Distance Vector (AODV) Routing. 3561. July 2003
[24] NIST Kernel AODV Implementation, http://w3.antd.nist.gov/wctg/aodv kernel
[25] Multicast Ad Hoc On-Demand Distance Vector(MAODV) Routing draft-ietf-manet-maodv-00.txt
[26] Elizabeth M. Royer, Charles E. Perkins. "Multicast Operation of the Ad-hoc On-demand Distance Vector Routing Protocol"
[27] 王亮，朱秋萍，马丽霞．Ad Hoc网络DSR路由协议的优化．武汉大学学报(理学版)June 2005
[28] 王晓燕，刘乃安．一种改进的多路径DSR协议．电子科技2005年第2期
[29] 吴东亚，侯紫峰，侯朝桢．移动自组网DSR协议路径缓存策略优化．计算机工程与应用．Sep 2004
[30] 陈曙光，李霞．一种高效的Ad Hoc网络AODV改进路由协议．东南大学学报(自然科学版)Mar．2003
[31] 郑相全，郭伟，李帆．自组网AODV路由协议中断链修复的改进．电子科技大学学报Oct．2003
[32] Lee S J, Mario G. AODV-BR: Backup Routing in Ad Hoc Networks[C]. Wireless Communications and Networking Conference,2000. WCNC. 2000 IEEE, 2000, 3: 1311～1316
[33] 苏静．移动Ad Hoc网中多信道AODV路由协议研究．电子科技大学硕士学位论文
[34] 卢昊，无线移动自组织网的路由技术研究[D]，成都，电子科技大学，2004-5-31
[35] 杨锦亚，郭虹，胡捍英．自组网路由协议性能比较．微计算机信息，2006，22(24)：196～198．
[36] Elizabeth M. Royerand Toh CK. A review of current routing protocols for Ad Hoc mobile wireless networks [J]. IEEE Personal Communications Magazine, Apr1999, 46～55.
[37] 胡罡．Ad Hoc路由协议的仿真及优化技术．[硕士学位论文]．长沙：国防科学技术大学研究生院，2004
[38] 吴继春．Ad Hoc网络路由协议的研究与NS2仿真：[硕士学位论文]．武汉：武汉理工大学计算机学院，2005
[39] 江李峰，于全，戴浩，孙小东．移动Ad Hoc网络的仿真框架．系统仿真学报，2002，14(8)：1100～1108
[40] Information Sciences Institute. The Network Simulator-ns-2. http://www.isi.edu/nsnam/ns/idex.html. 2004.6
[41] 俊洪，杨洋．网络仿真方法利OPNET仿真技术．计算机工程，2004，30(5)：105～108
[42] 徐雷鸣，庞博，赵耀．NS与网络模拟．人民邮电出版社．2003
[43] The Network Simulator ns-2[EB/OL], http://www.isi.edu/nsnam/ns/, 2005.
[44] Lee Breslau, Deborah Estrin etc. Advances in Network Simulation. IEEE Computer 2000(5)
© 2004-2018 中国地质图书馆版权所有 京ICP备05064691号 京公网安备11010802017129号 地址：北京市海淀区学院路29号 邮编：100083 电话：办公室：(+86 10)66554848；文献借阅、咨询服务、科技查新：66554700 |