摘要
本论文所反映的工作研究背景是国家973项目电子鼠自组网。电子鼠自组网具有结点移动性高,拓扑变化频率高、带宽资源有限、电池电量有限等特点,这些也正符合了Ad hoc网络的特点。结点的移动性和有限的通信资源使得在电子鼠自组网中维护路由十分困难。正因为该网络的Ad hoc特性,使得Ad hoc网络的路由协议在该网络中扮演了重要的角色。
在Ad Hoc网络中,由于结点移动频繁造成网络拓扑结构不断地动态变化,使得路由问题成为Ad Hoc网络研究与应用中的热点和难点。对于电子鼠自组网来说,一个有效的路由协议对于屏蔽底层的不利因素,为上层提供稳定高效的通信支持起着至关重要的作用。现有的Ad hoc路由算法大都是单径路由,即只使用一条路径传输分组。当一条链路失效时,只能发起新的路由发现过程。频繁的路由发现过程将会带来很大的开销,并且增加发送包的端到端延时。针对这一问题,本文提出了一种多径路由算法MDMAODV (Most Disjointed Multipath On-Demand Vector Routing),该算法在尽量不增加路由开销的前提下去寻找最大不相交多径路由,并且根据Peter. P等的数学证明为每个源目的结点对最多设置三条路径,从而改善了单路径路由协议中由于链路失效造成的延时增加和丢包率问题。另一方面又考虑链路带宽状况,利用定时器和轮发机制进行负载分配,以防止出现网络拥塞。NS2仿真表明,MDMAODV路由协议运行在结点个数较多的(大于30个结点)电子鼠自组网的实验场景下,与AODV路由协议相比,能够在保证良好的分组投递率的情况下,拥有10%到40%的平均端到端延时改善。
论文工作的另一部分,是为了提高路由协议的可扩展性,针对在仿真试验中所发现的AODV单径路由协议在小规模低流量场景下优于MDMAODV路由协议的现象,设计了一个自适应的路由算法。该协议可以根据网络情况,自适应地采用最适合的路由协议(AODV或MDMAODV),目的是为了使其既可以适用于网络规模较大、负载较重的网络,也适用于网络规模较小、负载较轻的网络。通过NS2仿真实验证明,本论文提出的自适应路由协议算法,在平均情况下,的确有优于AODV协议和多路径路由协议的良好性能,在电子鼠平台下,运用本文设计的自适应路由协议,能够使得性能得到极大提升。
本项研究的贡献主要在于:
分析了电子鼠自组网的网络层特点以及对路由协议的要求。并对当前几个经典的Ad hoc网络路由协议进行了仿真比较,得出了按需矢量路由(AODV)机制更适合于该平台的结论。
在对AODV协议的基础之上,经过改良,提出了一个多路径路由协议,使得该协议在电子鼠自组网结点总数较多,数据流量较大的情况下,相比AODV协议有了更好的性能。
提出了自适应算法,使得路由策略可以根据网络的规模和流量的大小,自适应地在单路径和多路径之间进行切换,从而使得路由协议在不同规模的网络下,都能够以优秀的性能运行。
本文的仿真模拟实验采用美国加州大学柏克利分校开发的网络仿真软件NS2(Network simulator)。
The work presented in this dissertation is part of preliminary research activities on network architectures for Electronic Mice Swarm Intelligence platform. Electronic Mice Swarm Intelligence Platform is typical ad hoc network, whose fast moving nodes (electronic mice) have imposed difficulties on routing protocols. This dissertation is dedicated to multipath routing technique in ad hoc networks, more specifically on the Electronic Mice Platform.
In this dissertation, performance of three classic routing protocols for ad hoc network on Electronic Mice Platform is compared via experiments on NS2, in terms of average end-to-end delay, package delivery fraction and normalized routing overhead. The result illustrate that AODV routing protocol has the best performance on Electronic Mice Platform. Then, a multipath extension of AODV is proposed and implemented on NS2. In the multipath routing protocol, when the prime path is broken, the back-up paths could be used instead of initiating a new process of routing recovery. Thus, a lot of time is saved. In MDMAODV, a load balancing algorithm is also proposed. In this load balancing algorithm, a timer and a mechanism of data transmission are used to avoid congestion. Through the results of experiments, the new designed multipath routing protocol performs better than AODV protocol on Electronic Mice Platform with large amount of nodes and high frequency of communication. However, when the number of nodes in Electronic Mice Platform is small or the frequency of communication is low, the multipath routing protocol's performance is even worse than AODV. In order to make the protocol adapt to Electronic Mice Platform with different network size, a self-adaptive routing protocol is designed which combines the single-path AODV protocol and the multipath routing protocol MDMAODV.
The main contributions of this dissertation can be summarized as follows:
Firstly, the requirements of routing protocols for Electronic Mice Platform are summarized. And the performance of classic routing protocols of Ad hoc networks on Electronic Mice Swarm Intelligence Platform is obtained through simulation experiments on NS2. The AODV routing protocol is proved to be the best.
Secondly, a multipath extension of AODV has been proposed and implemented on NS2, and the results of the experiments illustrated the MDMAODV routing protocol can perform better than AODV in some certain application scenarios.
Thirdly, a self-adaptive routing protocol is proposed to adapt to Electronic Mice Platform with different network size, which performs good in most cases than AODV and MDMAODV.
引文
[1] Bonabeau. E , Dorigo. M, Theraulaz. G. Swarm Intelligence: From Natural to Artificial Systems[M]. New York: Oxford University Press, 1999.
[2]Truszkowski W, Hinchey M, Rash J , Rouff C. NASA’s swarm missions : The challenge of building autonomous software [J] . IT Professional , 2004 , 6(5) : 47-52.
[3]Dorigo M. Swarm bots[ EB/ OL ] . Http: / / www. swarm2bots. org, Oct 24 , 2006.
[4] Charles E. Perkins, Ad Hoc Networking, 2001, Addison-Wesley, London; ISBN: 0-201-30976-98-23
[5] http://www.ietf.org/html.charters/manet-charter.html, 2008-11
[6] CORSON S, MACKER J. Mobile Ad hoc networking: routing protocol performance Issues and evaluation considerations[EB/OL]. http://www.ietf.org/rfc/rfc2501.txt, Jan 1999.
[7] lizabeth M. Royer, Chai-Keong Toh. A review of current routing protocols for ad hoc mobile wireless networks, IEEE 1999
[8] Stephen Mueller, Rose P .Tsang, Dipak Ghosal. Multipath Routing in Mobile Ad Hoc Networks: Issues and Challenges[J]. Computer Science, 2004.
[9] C. E. Perk ins, P Bhagwat. Highly dynamic destination sequenced distance vector routing (DSDV) for mobile computers. The ACM SIGCOMM Conf. on Communications Architectures, London, 1994
[10] S. Murthy, J.J. Garcia Luna Aceves. An efficient routing protocol for wireless networks. ACM/Baltzer Mobile Networks and Applications (Special Issue on Routing immobile Communications Networks),1996, 1 (2):183-197
[11] G. Pei, M. Gerla, T. W. Chen. Fish eye state routing: A routing scheme for ad hoc wireless networks. The IEEE Int'l Conf on Communications (ICC), New Orleans, LA, 2000
[12] Philippe Jacquet, P. Muhlethaler, and A. Qayyum. Optimized Link State Routing Protocol Internet Draft (work in progress), INRIA Rocquencourt, February 2000 draft-ietf-manet-olsr-0l.txt
[13] T. Clausen, P. Jacquet, A. Laouiti, P. Muhlethaler, A. Qayyum and L. Viennot, "Optimized Link State Routing Protocol for Mobile Ad Hoc Networks", IEEE INMIC Pakistan 2001.
[14] P. Jacquet, P. Muhlethaler, and A. Qayyum, "Optimized Link State Routing Protocol", IETF Internet Draft, draft-ietf-manet-olsr-l0.txt, June 2002.
[15] C. Perkins, E. M. Royer, S. R. Das. Ad Hoc On-Demand Distance Vector (AODV)Routing. Internet Draft (work in progress), Sun Microsystems Labs, Univ. of California and Univ. of Texas, November 1997. draft-ietf-manet-AODV-03.txt
[16] J. Broch, D. B. Johnson and D. A. Maltz. The Dynamic Source Routing Protocol for Mobile Ad Hoc Networks. Internet Draft (work in progress), Carnegie Mellon University, June 1999. draft-ietf-manet-dsr-02.txt
[17] D. Johnson and D. Maltz, "Dynamic Source Routing in Ad Hoc wireless networks," Mobile Computing, E.Imielnski and H.Korth,eds.,Kluwer Academic Publ.,1996
[18] V. Park and S. Corson. Temporally-Ordered Routing Algorithm (TORA) Version Functional Specification. Internet Draft (work in progress), Naval Research Lab and Univ.of Maryland, November 1997.draft-ietf-manet-tora-spec-00.txt
[19]R. Dube, C. D. Rais, K.Y. Wang et al. Signal stability based adaptive routing(SSA)for ad hoc mobile networks. IEEE Personal Communications Magazine, 1997, 4 (1):36-45
[20] M.T.Toussaint, Overview of Multipath Routing Protocols for Mobile Ad-hoc Networks, http://www.cactus.tudelft.nl [21」安辉耀,卢锡城,移动自主网络多路径路由技术研究进展,计算机工程与科学,2005
[22] A. Nasipuri, R. Castaneda, and S. R. Das,“Performance of multipath routing for on-demand protocols in mobile ad hoc networks,”Mobile Networks and Applications, vol. 6, no. 4, pp. 339-349, August 2001.
[23] A. Nasipuri and S. R. Das, On-demand multipath routing for mobile Ad Hoc networks, Proceedins of IEEE International Conference on Computer Communication and Networks Korea. 1999 (7):64-70
[24] S.J. Lee and M. Gerla, Split Multi-path Routing with Maximally Disjoint Paths in Ad Hoc Networks, ICC2001,Helsinki, Finland. June 12, 2001.
[25] Peter P., Sylvie P., Performance Analysis of Reactive Shortest Path and Multi-path Routing Mechanism With Load Balance. IEEE INFOCOM (2003)
[26] S. De and S. Das,“Dynamic multipath routing (DMPR): An approach to improve resource utilization in networks for real-time traffic,”in Proceedings of Ninth International Symposium on Modeling, Analysis and Simulation of Computer and Telecommunication Systems, 2001,pp. 23-30.
[27] J. Zhao, B. Zhou, and J. Wu,“Quality of service based multipath routing for supporting real time wireless applications,”in Proceedings of International Conferences on Info-tech and Info-net, vol. 2, October-November 2001, pp. 122-127.
[28] J. Chen and S. H. Chan,“Multipath routing for video unicast over bandwidth-limited networks,”in Proceedings of IEEE GLOBECOM, vol. 3, November 2001, pp. 1963-1967.
[29] P. Leelapornchai and T. Stockhammer, "Progressive image transmission applying multipath routing in mobile ad hoc networks," in Proceedings of International Conference on Image Processing, vol. 1,September 2002, pp. 553-556.
[30] L.P. Chow C.C. Hsu, and F. Wu,“A reliable multipath routing protocol for ad-hoc network,”in Proceedings of 10th IEEE International Conference on Networks (ICON), August 2002, pp. 305-310.
[31] C. Lee. X.H. Lin, and Y-K. Kwok,“A multipath ad hoc routing approach to combat wireless link insecurity,”in Proceedings of IEEE International Conference on Communications (ICC), vol. 1, April 2003, pp. 448-452.
[32] W. Lou and Y Fang, "A multipath routing approach for secure data delivery," in Proceedings of IEEE MILCOM, vol. 2, October 2001,pp. 1467-1473.
[33] M.R. Pearlman and Z.J. Haas, P. Sholander, S.S. Tabrizi.“On the impact of alternate path routing for load balancing in mobile ad hoc networks”Proceedings of the first workshop on mobile and ad hoc networking and computing (MobiHoc 2000), Boston, MA, Aug. 2000.
[34] B. Bellur and R. Ogier,“A Reliable, Efficient Topology Broadcast Protocol for Dynamic Networks”, Proceedings IEEE INFOCOM’99, p.178-186, March 1999.
[35] B. Bellur, et. al,“Topology Dissemination Based on Reverse-Path Forwarding (TBRPF)”, IETF Internet Draft, draft-ietf-manet-tbrpf-08.txt, April 2003.
[36] S.J. Lee and M. Gerla, AODV-BR: Backup Routing in Ad Hoc Network, IEEE WCNC 2000, Chicago IL, Sept. 2000, pp. 1311-16.
[37] L. Wang, L. Zhang, Y. Shu, M. Dong, Multipath source routing in wireless ad hoc networks, in: Proceedings of Canadian Conference on Electrical and Computer Engineering 2000, vol. 1, March 2000, pp. 479–483.
[38] L. Wang, Y. Shu, M. Dong, L. Zhang, O.W.W. Yang, Adaptive multipath source routing in ad hoc networks, in: Proceedings of IEEE International Conference on Communications, vol. 3, June 2001, pp. 867–871.
[39] Roy Leung et al, "MP-DSR: A QoS-aware Multipath DSR Protocol for Wireless Ad-Hoc Networks,'" Proc. 26th LCN, 2001.3,p.132-p.142
[40] Alvin Valera, Winston K.G Seah and SV Rao.“Cooperative Packet Caching and Shortest Multipath Routing in Mobile Ad Hoc Networks,”Proceedings of the 22th IEEE INFOCOM, San Francisco, CA, April 1-3, 2003.
[41] A. Valera, W. Seah and S. Rao, "CHAMP: A Highly-Resilient and Energy-Efficient Routing Protocol for Mobile Ad hoc Networks"", Proc. of Fourth IEEE Conference on Mobile and Wireless Communications Networks (MWCN 2002), Sep 9-11,Stockholm, Sweden, 2002.
[42] J. Schaumann,“Analysis of the Zone Routing Protocol”, December 2002.
[43] Z. Haas and M. Pearlman,“The zone routing protocol (ZRP) for Ad Hoc networks”, IETF Internet Draft, draft-ietf-manet-zone-zrp-04.txt, July 2002.
[44] Z. Haas, "A New Routing Protocol for the Reconfigurable Wireless Networks", Proceedings of IEEE ICUPC'97, San Diego, CA, pp. 562-566, October 1997.
[45] Peter Phuc Pham, Congestion Avoidance Using Multipath Routing and Power Control In Mobile Ad Hoc Network,A Phd proposal submitted in partial fulfillment of the requirements for the degree of Ph.D. of Telecommunications University of South Australia March 28, 2002
[46] X. Lin, M. Lakshdisi, and I. Stojmenovic, "Location based localized alternate, disjoint, multipath and component routing schemes for wireless networks," in Proceedings of the 2nd ACM International Symposium on Mobile Ad Hoc Networking and Computing, October 2001,pp. 287-290.
[47] D. Niculescu and B. Nath, "Trajectory based forwarding and its applications," in Proceedings of the 9th Annual International Conference on Mobile computing and Networking, September 2003, pp. 260-272.