Ad Hoc网络中AODV-I协议的研究与实现
摘要
Ad Hoc网络是一个多跳的、自组织、无中心的网络,它由一组带有无线收发装置的移动终端组成的,无需任何固定的基础设施便能实现网络的快速部署,因此非常适合于军事、救灾、个人通信、无线传感器网络等领域。由于Ad Hoc网络拓扑频繁变化,传统的因特网路由协议不能满足其需求,因而路由协议成为Ad Hoc网络的研究重点。
本文对Ad Hoc按需路由协议(AODV)进行了深入的研究,探讨了其路由发现过程中存在的问题：路由请求(RREQ)消息的处理缺乏拥塞控制,路由应答(RREP)消息缺乏保障机制。本文针对这两个问题提出一个AODV改进协议AODV-I。AODV-I协议对RREQ消息的处理添加了拥塞控制,在建立新的路由时能够自动选择网络中相对空闲的节点；对RREP消息的转发过程中添加了路由修复机制,使得在路由断裂情况下该RREP消息仍能够返回到路由请求源节点,从而避免不必要的新一轮路由请求。通过对AODV协议的改进,能够减少网络丢包率和端到端延迟并提高网络资源的利用率。
本文介绍了Ad Hoc网络典型的路由协议及其优缺点；深入研究了AODV路由协议,探讨了其路由发现过程中存在的两个问题,并针对这两点问题提出了改进方案；修改NS代码,实现改进后协议的功能。最后,分析仿真结果及实验数据,验证所提出方案的性能。
Ad Hoc network is a multi-hop, autonomous, acentric system, which consists of mobile terminal with wireless transceiver, and it can be deployed rapidly without relying on any pre-established infrastructure, so it is quite suitable to some special field such as battlefield, disaster relief, personal communication and wireless sensor network etc. The traditional Internet routing protocols can't meet the demand of frequent topology changes in Ad Hoc network, so the routing protocols become an important research issue.
This paper conducts a deep research on AODV protocol and discusses two problems in its route discovery process:lacking congestion control on RREQ message sending by the requesting node and no guarantee mechanism of RREP message returning to the requesting node. This paper proposes an improvement protocol AODV-I based on the investigation above, in which congestion control in RREQ message transmitting process is adopted and route repair mechanism in RREP message forwarding process is utilized. The AODV-I can choose the relatively idle node automatically when establishing a new route, and also make sure that the RREP message returns to the requesting node under the circumstance of route fault, thus avoiding another unnecessary route request. With these improvements to AODV protocol, it is possible to reduce the rate of packet loss as well as end-to-end delay and increase network resource utilization.
This paper introduces several typical routing protocols, and analyzes their advantages and disadvantages. Through the deep research on the AODV protocol, two problems in the routing discovery process are discussed and improved schemes are put forward. The improved schemes are implemented by modifying the code in NS. Finally, the result of emulation is analyzed to verify the feasibility of the scheme.
本文对Ad Hoc按需路由协议(AODV)进行了深入的研究,探讨了其路由发现过程中存在的问题：路由请求(RREQ)消息的处理缺乏拥塞控制,路由应答(RREP)消息缺乏保障机制。本文针对这两个问题提出一个AODV改进协议AODV-I。AODV-I协议对RREQ消息的处理添加了拥塞控制,在建立新的路由时能够自动选择网络中相对空闲的节点；对RREP消息的转发过程中添加了路由修复机制,使得在路由断裂情况下该RREP消息仍能够返回到路由请求源节点,从而避免不必要的新一轮路由请求。通过对AODV协议的改进,能够减少网络丢包率和端到端延迟并提高网络资源的利用率。
本文介绍了Ad Hoc网络典型的路由协议及其优缺点；深入研究了AODV路由协议,探讨了其路由发现过程中存在的两个问题,并针对这两点问题提出了改进方案；修改NS代码,实现改进后协议的功能。最后,分析仿真结果及实验数据,验证所提出方案的性能。
Ad Hoc network is a multi-hop, autonomous, acentric system, which consists of mobile terminal with wireless transceiver, and it can be deployed rapidly without relying on any pre-established infrastructure, so it is quite suitable to some special field such as battlefield, disaster relief, personal communication and wireless sensor network etc. The traditional Internet routing protocols can't meet the demand of frequent topology changes in Ad Hoc network, so the routing protocols become an important research issue.
This paper conducts a deep research on AODV protocol and discusses two problems in its route discovery process:lacking congestion control on RREQ message sending by the requesting node and no guarantee mechanism of RREP message returning to the requesting node. This paper proposes an improvement protocol AODV-I based on the investigation above, in which congestion control in RREQ message transmitting process is adopted and route repair mechanism in RREP message forwarding process is utilized. The AODV-I can choose the relatively idle node automatically when establishing a new route, and also make sure that the RREP message returns to the requesting node under the circumstance of route fault, thus avoiding another unnecessary route request. With these improvements to AODV protocol, it is possible to reduce the rate of packet loss as well as end-to-end delay and increase network resource utilization.
This paper introduces several typical routing protocols, and analyzes their advantages and disadvantages. Through the deep research on the AODV protocol, two problems in the routing discovery process are discussed and improved schemes are put forward. The improved schemes are implemented by modifying the code in NS. Finally, the result of emulation is analyzed to verify the feasibility of the scheme.
引文
1.曹常义.Ad hoc技术[J],电信工程技术与标准化,2002,(5)：13-19.
2. C. Elliott and B. Heile. Self-Organizing, Self-Healing Wireless Networks [C]. Proc.2000 IEEE Int'l Conf. on Personal Wireless Comm, United States,2000, pp.355-362.
3. D. K. Kim. A New Mobile Environment:Mobile Ad Hoc Networks (MANET) [J], IEEE Vehic. Tech. Soc. News, August 2003, pp.29-35.
4. I. F. Akyildiz,. X. Wang,W. Wang. Wireless mesh networks:a survey [J], Computer Networks Journal,2005,47(3):445-487.
5. J. Macker and S. Corson. Mobile Ad Hoc Networks (MANET) [S], IETF WG Charter., http://www.ietf.org/html.charters/manet-charter.html,1997.
6. C. Perkins et al. Ad hoc On-Demand Distance Vector (AODV) Routing [S], RFC 3561, July 2003.
7. T. Clausen, P. Jacquet. Optimized Link State Routing protocol (OLSR) [S], RFC 3626, Oct.2003.
8. R. G. Ogier et al. Topology Dissemination Based on Reverse-Path Forwarding (TBRPF) [S], RFC 3684, Feb.2004.
9. C. Cheng, R. Reley, S.P.R. Kumar and J.J. Garcia-Luna-Aceves. A loop-free extended Bellman-Ford routing protocol without bouncing effect [J], ACMComp. Commun. Rev. 1989,19(4):224-236.
10. Shree Murthy, J. J. Garcia-Luna-Aceves. An efficient routing protocol for wireless networks [J], Mobile Networks and Applications, Oct.1996,2(1):183-197.
11. David B. Johnson, David A. Maltz, and Yih-Chun Hu. The Dynamic Source Routing Protocol for Mobile Ad Hoc Networks (DSR) [S], RFC 4728, February 2007.
12. V. Park and S. Corson. Temporally Ordered Routing Algorithm [S], IETF Internet Draft, draft-ietf-manet-tora-spec-04.txt, March 2004.
13. Z. J. Haas, M. R. Pearlman, and P. Samar. The zone routing protocol (ZRP) for ad hoc networks [S], IETF Internet Draft, draft-ietf-manet-zonezrp-04.txt, July 2002.
14. P. Karn. MAC A:a new channel access method for packet radio [C], Proc. of ARRL/CRRL, April 1990, pp.134-140.
15. J. J. Garcia-Luna-Aceves, C. L. Fullmer. Floor Acquisition Multiple Access (FAMA) in single-channel wireless networks [J], Mobile Networks and Applications,1999,4(3): 157-174.
16. David P. Anderson, Ralf G Herriwich, Carl Schaefer. SRP:A Resource Reservation Protocol for Guaranteed-Performance [C]. Technical Report:CSD-90-562, Jan.1990.
17. K. Sanzgiri, B. Dahill, B. N. Levine, C. Shields, E. M. Belding-Royer. A Secure Routing Protocol for Ad-hoc Networks [C], Proc. of International Conference on Network Protocols (ICNP), Nov.2002.
18. M. Guerrero Zapata. Secure ad hoc on-demand distance vector (saodv) routing [S], draft-guerrero-manet-saodv-OO.txt, Aug.2002.
19. T. Rouse, I. Band, and S. McLaughlin. Capacity and Power Investigation of Opportunity Driven Multiple Access (ODMA) Networks in TDD-CDMA Based Systems [C], IEEE International Conference on Communications (ICC),2002.
20. Hyung Ki Lee, Dong Sam Ha. SOPRANO:an efficient automatic test pattern generator for stuck-open faults in CMOS combinational circuits [C], Proceedings of the 27th ACM/IEEE conference, Orlando, Florida, United States, Jun.1990, pp.660-666.
21. A. Boukerche, S. K. Das, A. Fabbri. Analysis of Randomized Congestion Control in DSDV Routing [C],8th IEEE/ACM Syrup. MASCOTS'2000,2000, pp.65-72.
22. C.E. Perkins, P. Bhagwat, Highly Dynamic Destination-Sequenced Distance Vector Routing (DSDV) for Mobile Computers, Proceedings of ACM SIGCOMM'94, London, Aug 1994, pp.234-244.
23.张远,郭虹,刘洛琨.DSDV算法实现及其性能分析[J], Mobile Communications, 2004, (2):17-19.
24. M. A. Bhagyaveni, S. Shanmugavel. Performance of shadow cluster resource reservation mechanism in Ad hoc networks [C], Proceedings of SPIE-The International Society for Optical Engineering,2001,4531:301-308.
25. A. Tonnesen. Implementing and Extending the Optimized Link State Routing Protocol [M], University of Oslo, August 2004.
26. T. Plesse, J. Lecomte, C. Adjih, M. Badel. OLSR Performance Measurement in a Military Mobile Ad-hoc Network [C], Ad Hoc Networks Journal special issue on Data communication and topology control in ad-hoc networks, October 2004.
27. GPei, Mgerla, T-WChen. Fisheye state routing:A routing scheme for ad hoc wireless networks [C], The IEEE ICC, NewOrleans, LA,2000.
28. Thomas Heide Clausen. Combining Temporal and Spatial Partial Topology for MANET routing-Merging OLSR and FSR [C], Proc. of IEEE WPMC'03, Yokosuka, Japan, October 2003.
29. Ana Cavalli, Cyril Grepet. A Validation Model for the DSR Protocol [C], ICDCSW'04, Mar.2004, pp.768-773.
30. R. Bai, M. Singhal. DOA:DSR over AODV Routing for Mobile Ad Hoc Networks [J], IEEE Transactions on Mobile Computing, Oct.2006,5(10):1403-1416.
31. Wei Kuang Lai, Sheng-Yu Hsiao, Yuh-Chung Lin. Adaptive backup routing for ad-hoc networks [J], Computer Communications,2007,30(2):453-464.
32. S. J Lee, M. Gerla. AODV-BR:Backup Routing in Ad hoc network [C], Proc. IEEE WCNC 2000,2000,3:1311-1316.
33. Jing Feng, Huaibei Zhou. A Self-Repair Algorithm for Ad Hoc On-Demand Distance Vector Routing [C], Networking and Mobile Computing,2006, pp.1-4.
34. Patrick M. Carthy, PDan Grigoras. Multipath Associativity Based Routing [C], Proceedings of the Second Annual Conference,2005, pp.60-69.
35. PK. N. Sridhar, Jacob Lillykutty, Shorey Rajeev. Performance Evaluation and Enhancement of Link Stability Based Routing for MANETs [C], ICPPW,2004, pp. 133-140.
36. Corson M S, Papademetriou S. An Internet MANET encapsulation protocol (IMEP) specification[S], Internet draft, draft-ietf-manet-imep-spec-01.txt, August 1998.
37. T. Fuhrmann. The use of scalable source routing for networked sensors [C], Proceedings of the 2nd IEEE workshop,2005, pp.163-165.
38. Y.-B. Ko and N.H. Vaidya. Location-Aided Routing (LAR) in Mobile Ad Hoc Networks [C], Proceedings of ACM/IEEE MOBICOM'98, Dallas, TX, Oct.1998, pp.66-75.
39.Young-Bae Ko, Nitin H. Vaidya. Location-aided routing (LAR) in mobile ad hoc networks [J], Wireless Networks,2000,6(4):307-321.
40.徐雷鸣,庞博,赵耀.NS与网络模拟[M],北京：人民邮电出版社,2003,1-9
41. http://www.isi.edu/nsnam/ns
42. http://www.netforum.com.cn
43. S. Corson, J. Macker. Mobile Ad hoc Networking (MANET):Routing Protocol Performance Issues and Evaluation Considerations [S], RFC 2501, January 1999.
2. C. Elliott and B. Heile. Self-Organizing, Self-Healing Wireless Networks [C]. Proc.2000 IEEE Int'l Conf. on Personal Wireless Comm, United States,2000, pp.355-362.
3. D. K. Kim. A New Mobile Environment:Mobile Ad Hoc Networks (MANET) [J], IEEE Vehic. Tech. Soc. News, August 2003, pp.29-35.
4. I. F. Akyildiz,. X. Wang,W. Wang. Wireless mesh networks:a survey [J], Computer Networks Journal,2005,47(3):445-487.
5. J. Macker and S. Corson. Mobile Ad Hoc Networks (MANET) [S], IETF WG Charter., http://www.ietf.org/html.charters/manet-charter.html,1997.
6. C. Perkins et al. Ad hoc On-Demand Distance Vector (AODV) Routing [S], RFC 3561, July 2003.
7. T. Clausen, P. Jacquet. Optimized Link State Routing protocol (OLSR) [S], RFC 3626, Oct.2003.
8. R. G. Ogier et al. Topology Dissemination Based on Reverse-Path Forwarding (TBRPF) [S], RFC 3684, Feb.2004.
9. C. Cheng, R. Reley, S.P.R. Kumar and J.J. Garcia-Luna-Aceves. A loop-free extended Bellman-Ford routing protocol without bouncing effect [J], ACMComp. Commun. Rev. 1989,19(4):224-236.
10. Shree Murthy, J. J. Garcia-Luna-Aceves. An efficient routing protocol for wireless networks [J], Mobile Networks and Applications, Oct.1996,2(1):183-197.
11. David B. Johnson, David A. Maltz, and Yih-Chun Hu. The Dynamic Source Routing Protocol for Mobile Ad Hoc Networks (DSR) [S], RFC 4728, February 2007.
12. V. Park and S. Corson. Temporally Ordered Routing Algorithm [S], IETF Internet Draft, draft-ietf-manet-tora-spec-04.txt, March 2004.
13. Z. J. Haas, M. R. Pearlman, and P. Samar. The zone routing protocol (ZRP) for ad hoc networks [S], IETF Internet Draft, draft-ietf-manet-zonezrp-04.txt, July 2002.
14. P. Karn. MAC A:a new channel access method for packet radio [C], Proc. of ARRL/CRRL, April 1990, pp.134-140.
15. J. J. Garcia-Luna-Aceves, C. L. Fullmer. Floor Acquisition Multiple Access (FAMA) in single-channel wireless networks [J], Mobile Networks and Applications,1999,4(3): 157-174.
16. David P. Anderson, Ralf G Herriwich, Carl Schaefer. SRP:A Resource Reservation Protocol for Guaranteed-Performance [C]. Technical Report:CSD-90-562, Jan.1990.
17. K. Sanzgiri, B. Dahill, B. N. Levine, C. Shields, E. M. Belding-Royer. A Secure Routing Protocol for Ad-hoc Networks [C], Proc. of International Conference on Network Protocols (ICNP), Nov.2002.
18. M. Guerrero Zapata. Secure ad hoc on-demand distance vector (saodv) routing [S], draft-guerrero-manet-saodv-OO.txt, Aug.2002.
19. T. Rouse, I. Band, and S. McLaughlin. Capacity and Power Investigation of Opportunity Driven Multiple Access (ODMA) Networks in TDD-CDMA Based Systems [C], IEEE International Conference on Communications (ICC),2002.
20. Hyung Ki Lee, Dong Sam Ha. SOPRANO:an efficient automatic test pattern generator for stuck-open faults in CMOS combinational circuits [C], Proceedings of the 27th ACM/IEEE conference, Orlando, Florida, United States, Jun.1990, pp.660-666.
21. A. Boukerche, S. K. Das, A. Fabbri. Analysis of Randomized Congestion Control in DSDV Routing [C],8th IEEE/ACM Syrup. MASCOTS'2000,2000, pp.65-72.
22. C.E. Perkins, P. Bhagwat, Highly Dynamic Destination-Sequenced Distance Vector Routing (DSDV) for Mobile Computers, Proceedings of ACM SIGCOMM'94, London, Aug 1994, pp.234-244.
23.张远,郭虹,刘洛琨.DSDV算法实现及其性能分析[J], Mobile Communications, 2004, (2):17-19.
24. M. A. Bhagyaveni, S. Shanmugavel. Performance of shadow cluster resource reservation mechanism in Ad hoc networks [C], Proceedings of SPIE-The International Society for Optical Engineering,2001,4531:301-308.
25. A. Tonnesen. Implementing and Extending the Optimized Link State Routing Protocol [M], University of Oslo, August 2004.
26. T. Plesse, J. Lecomte, C. Adjih, M. Badel. OLSR Performance Measurement in a Military Mobile Ad-hoc Network [C], Ad Hoc Networks Journal special issue on Data communication and topology control in ad-hoc networks, October 2004.
27. GPei, Mgerla, T-WChen. Fisheye state routing:A routing scheme for ad hoc wireless networks [C], The IEEE ICC, NewOrleans, LA,2000.
28. Thomas Heide Clausen. Combining Temporal and Spatial Partial Topology for MANET routing-Merging OLSR and FSR [C], Proc. of IEEE WPMC'03, Yokosuka, Japan, October 2003.
29. Ana Cavalli, Cyril Grepet. A Validation Model for the DSR Protocol [C], ICDCSW'04, Mar.2004, pp.768-773.
30. R. Bai, M. Singhal. DOA:DSR over AODV Routing for Mobile Ad Hoc Networks [J], IEEE Transactions on Mobile Computing, Oct.2006,5(10):1403-1416.
31. Wei Kuang Lai, Sheng-Yu Hsiao, Yuh-Chung Lin. Adaptive backup routing for ad-hoc networks [J], Computer Communications,2007,30(2):453-464.
32. S. J Lee, M. Gerla. AODV-BR:Backup Routing in Ad hoc network [C], Proc. IEEE WCNC 2000,2000,3:1311-1316.
33. Jing Feng, Huaibei Zhou. A Self-Repair Algorithm for Ad Hoc On-Demand Distance Vector Routing [C], Networking and Mobile Computing,2006, pp.1-4.
34. Patrick M. Carthy, PDan Grigoras. Multipath Associativity Based Routing [C], Proceedings of the Second Annual Conference,2005, pp.60-69.
35. PK. N. Sridhar, Jacob Lillykutty, Shorey Rajeev. Performance Evaluation and Enhancement of Link Stability Based Routing for MANETs [C], ICPPW,2004, pp. 133-140.
36. Corson M S, Papademetriou S. An Internet MANET encapsulation protocol (IMEP) specification[S], Internet draft, draft-ietf-manet-imep-spec-01.txt, August 1998.
37. T. Fuhrmann. The use of scalable source routing for networked sensors [C], Proceedings of the 2nd IEEE workshop,2005, pp.163-165.
38. Y.-B. Ko and N.H. Vaidya. Location-Aided Routing (LAR) in Mobile Ad Hoc Networks [C], Proceedings of ACM/IEEE MOBICOM'98, Dallas, TX, Oct.1998, pp.66-75.
39.Young-Bae Ko, Nitin H. Vaidya. Location-aided routing (LAR) in mobile ad hoc networks [J], Wireless Networks,2000,6(4):307-321.
40.徐雷鸣,庞博,赵耀.NS与网络模拟[M],北京：人民邮电出版社,2003,1-9
41. http://www.isi.edu/nsnam/ns
42. http://www.netforum.com.cn
43. S. Corson, J. Macker. Mobile Ad hoc Networking (MANET):Routing Protocol Performance Issues and Evaluation Considerations [S], RFC 2501, January 1999.