Buffer Management and Auxiliary Routing in AODV

论文摘要

移动自组织网络（ad hoc network）是由一组可移动的兼具终端和路由功能的设备通过无线链路形成的多跳临时性自治系统。它们是在一段时间内为特定目而构建一个临时网络。MANET在日常通信中,尤其在临时会议中有广泛的应用。由于MANET具有ad hoc网络的特性,同样存在资源稀缺的问题。特别是在使用音频和视频流的应用中,这一问题更加尖锐。为了保证使用音频和视频流的应用程序有效运作将需要更大的带宽,这使本来就资源受限的网络进一步受到限制。MANET也可用于紧急服务,家庭网络,嵌入式计算应用,个人区域网络等等。路由选择的有效性已成为MANET中一个备受关注的问题。这是因为移动网络需要这种在既没有专门设施,也没有固定位置的网络中进行路由选择。因此,任何有效和高效的MANET路由选择都必须解决移动节点所带来的挑战,例如能源有限,非均匀性等等。解决上述挑战,在一定程度上促进了MANET路由协议的发展。MANET路由协议分为以下两类：表驱动和按需驱动。本论文着重于后者,尤其关注ad hoc按需距离矢量（AODV）路由协议。按需路由协议AODV只在需要时构建路由表。然而,在高速移动和通信量大时,快速创建路由信息的开销会降低网络性能。过去十年里已经有大量的研究关注了这一问题。随着移动自组网中的资源越来越密集,应用也变得越来越复杂,改善这些路由协议的性能日益急切。本论文提出基于AODV改进的协议FOVA,算法将溢出和丢失的数据包进行缓存来改善存储管理,并提出了一个备份路由选择过程。这在很大的程度上,增加了分组投递率,降低了端到端的延迟。仿真结果证明了FOVA性能优于原始AODV。移动自组网（移动Ad hoc网络）的主要困难之一是路由选择的问题,由于节点的移动,无线干扰和网络分区引起的拓扑的频繁变化加剧了这一问题。研究者已经提出了许多路由协议。先验性路由是指每个节点在任何时候维护网络中的路由信息,而按需路由只有在需要时才找到新的路由。还有一些其它路由策略,如：利用地理位置信息构建路由。无线网络拓扑结构是动态的,不可预测的。在移动自组织网络中带宽通常有限,传统的有线网络中使用的路由协议不能直接应用于无线网络,因为一些常见的假设在这一动态网络中是不可行的,例如任何一个节点可以在同一个子网接收他人发送的广播消息。因此,在移动自组织网络中设计路由协议是一个巨大的挑战。已有学者对这一问题进行深入研究。C.R. Mandal和Rajiv Misra提出一种询问邻居节点旁路路由目的的算法。他们使用Glomosim将平均数据包交付率作为实验参数,该算法显著改善了平均数据包交付率。然而,他们的算法并不能在邻近节点没有旁路的情况下路由,在这种情况下,数据包将被丢弃。本论文提出了一种改进算法来处理这一具体情况。近年来,出现了支持互联网连接的移动自组织网一些解决方案,其中AODV协议被认为具有多个移动网关。MIPMANET（?）办议是互联网连接的移动IP和AODV的整合。互联网连接可能经常创建具有恒定比特速率的业务,这导致具有共同的目的流的受限问题。本文中,该算法弥补了AODV在受限的情况下的性能。Samir R. Das, Charles E. Perkins和Elizabeth M. Royer在不同的网络负载,移动性和网络规模的情况下,对AODV进行性能分析。他们认为要用拥塞相关的指标来进行评价（如队列长度）,而不应该使用最短路径跳数作为参数来对路由进行评价。作者指出从网络中删除旧的数据包有利于路由负载,尽管这些数据很可能会被重传。为保证数据包可达到网络中所有节点,许多研究提出了更有效的广播技术来减少重传次数。有些研究者将现有的广播技术分类并且比较。他们认为,邻近知识方法（SBA、 MPR、AHBF、LENWB等等）是最佳的广播协议类型。OLSR使用MPR洪水机制来减小它的广播消息。这个机制体现了OLSR的创新。它通过减少冗余消息来减小泛洪开销。每个节点选择两跳范围内的节点作为邻居节点。快速的OLSR是解决OLSR快速移动问题的扩展。当迅速发现一些邻居时,它维护与快速移动节点的连通性。快速OLSR通过观察邻居节点变动来监测节点的移动。我将这个机制融合到AODV协议中来减小RREQ泛洪的影响。在AODV-PA和DSR协议中,节点支持一条路径累积在路由发现的过程中存储一些路由信息。该协议不是源路由协议：实际上,每个节点将地址附加在控制数据包里。然而,每个节点都不使用此路径来发送数据包。本文将预测算法应用于两种流行的按需路由协议AODV和DSR。仿真结果表明,修改后两种协议都具有较高的数据包投递率和较低的控制信息开销。预测算法有效降低了由于断链引起的丢包数目,使得路由协议整体性能提高。本论文提出一种FOVA算法,该算法基于AODV（?）办议。与其他现有的ad hoc协议相比,选择AODV协议是原因如下：1.与其他协议相比,如DSR和TORA,AODV仅需要较少的修改就可以实现FOVA.2.它仅需要一个相对较低的开销,并具有良好的带宽和节约能源。3AODV本身是一个常用的协议。该算法对AODV协议进行了改进,通过改善缓存区管理,防止溢出造成数据包丢弃。该算法监测每个节点的缓冲级,通过备份选路系统重新选择路径来减小节点拥塞。拥塞是假设在缓冲区接近一个阈值,该阈值随后引发替换路由选路。本论文的贡献如下：1.提出了一种拥塞预测算法,该算法使用缓冲和中间节点的数据包,先入先出的速率来预测拥塞和随后的数据包丢失。它创建备份路由和管理缓存级来防止缓冲区丢包。仿真分析了算法的准确性和局限性。2.使用网络仿真器（NS2）提供的AODV（?）办议对该预测算法实现主动路由维护。针对具体的性能参数,提出了AODV（?）办议拥塞预测算法的综合评价方法。结果表明,主动路由维护可以明显减少由于断链引起的数据包丢弃数目20%左右,即使在考虑到控制消息数目增加的情况下仍然低于33%。3.对AODV的改进。提出了进一步改善避免丢包和减少控制信息的数量改进协议。在快速移动情况下,可选择路径的DSR路由协议在数据包投递率和端到端的延迟方面优于AODV.近年来,无线自组网已经应用领域不断扩大,并且这种趋势正在上升。由于无线自组网中资源稀缺,因此有必要寻找更有效的路由方法。本文提出了AODV。办议的改进方案—FOVA算法,该算法在AODV协议上实现可选路径路由协议,改善了原来AODV协议的性能。该算法在NS2仿真平台下进行一系列仿真,使用各种场景环境,如不同的移动速度和流量负载。仿真将包括以单个目的为目标的附加限制,进一步证实了飞跃算法（FOVA）的有效性。结果表明修改后的协议在数据包投递率和端到端的延迟上有着优异的表现。

论文目录

• TABLE OF CONTENTS
• LIST OF FIGURES
• LIST OF TABLES
• ABSTRACT
• 摘要
• ACKNOWLEDGEMENT
• LIST OF ABREVIATIONS
• CHAPTER 1:GENERAL INTRODUCTION
• 1.1 Background
• 1.2 Introduction
• 1.3 Review of previous work
• 1.4 Objectives
• 1.5 Motivation
• 1.6 ORGANIZATION OF THE THESIS
• CHAPTER 2:OVERVIEW OF MANET PROTOCOLS
• 2.1 Homogenous Mobile Device Network
• 2.2 Heterogenous Mobile Device Network
• 2.3 Movement of MDs
• 2.3.1 Displacement of MD in a Route
• 2.3.2 Displacement by subnet-Bridging MD
• 2.4 Existing Ad Hoc Wireless Network Routing Protocols
• 2.4.1 Table-Driven Routing Protocols
• 2.4.2 Source-Initiated On-Demand Routing Protocols
• 2.4.2.1 Temporally-Ordered Routing Algorithm（TORA）
• 2.4.2.2 Dynamic Source Routing（DSR）
• 2.4.2.3 Ad-hoc On-Demand Distance Vector Routing（AODV）
• 2.4.2.4 AODV over Partially Connected Ad hoc Networks
• 2.4.2.5 AODV Buffer management
• 2.4.2.6 Motivation for Selecting AODV
• 2.5 Other Protocols and Algorithms
• 2.6 Discussion
• 2.7 Table-Driven vs. On-Demand Routing Protocols
• 2.8 Summary
• CHAPTER THREE:PROBLEM STATEMENT AND HYPOTHESIS
• 3.1
• 3.1.1 AODV-Ad hoc On-Demand Distance Vector
• 3.1.2 AODV Protocol-control Packets
• 3.1.3 AODV Route Discovery
• 3.1.4 AODV Route Maintenance
• 3.1.5 Observed Problem
• 3.2 The proposed Fly-OVer Algorithm（FOVA）
• 3.2.1 The FOVA concept
• 3.2.1.1 Route Construction
• 3.2.1.2 Route Maintenance and Mesh Routes
• 3.2.1.3 The FOVA Algorithm
• 3.2.1.4 Assumptions
• 3.6 Summary
• CHAPTER FOUR:SIMULATION RESULTS AND ANALYSIS
• 4.1 Simulations
• 4.2 Simulation Metrics
• 4.3 Simulation Envi ronment
• 4.4 Results and Analysis
• 4.5 Summary
• CONCLUSION
• RECOMMENDATIONS
• REFERENCES
• APPENDIX A
• APPENDIX B