Routing Protocols in Mobile Ad-hoc Networks

routing protocols in wireless ad hoc networks a simulation study and multipath routing protocols in wireless mobile ad hoc networks pdf free download
JaydenGibbs Profile Pic
JaydenGibbs,United States,Teacher
Published Date:19-07-2017
Your Website URL(Optional)
Comment
1998:362 MASTER'S THESIS Routing Protocols in Wireless Ad-hoc Networks - A Simulation Study Tony Larsson, Nicklas Hedman Civilingenjörsprogrammet 1998:362 • ISSN: 1402-1617 • ISRN: LTU-EX98/362SEMaster’s thesis in Computer Science and Engineering Routing Protocols in Wireless Ad-hoc Networks - A Simulation Study Stockholm, 1998 Tony Larsson and Nicklas Hedman Luleå University of Technology Supervisor: Per Johansson Switchlab Ericsson Telecom AB Examiner: Mikael Degermark Department of Computer Science and Electrical Engineering Division of Computer Communications, Luleå University of TechnologyAbstract Ad-hoc networking is a concept in computer communications, which means that users wanting to communicate with each other form a temporary network, without any form of centralized administration. Each node participating in the network acts both as host and a router and must therefore be willing to forward packets for other nodes. For this purpose, a routing protocol is needed. An ad-hoc network has certain characteristics, which imposes new demands on the routing protocol. The most important characteristic is the dynamic topology, which is a consequence of node mobility. Nodes can change position quite frequently, which means that we need a routing protocol that quickly adapts to topology changes. The nodes in an ad-hoc network can consist of laptops and personal digital assistants and are often very limited in resources such as CPU capacity, storage capacity, battery power and bandwidth. This means that the routing protocol should try to minimize control traffic, such as periodic update messages. Instead the routing protocol should be reactive, thus only calculate routes upon receiving a specific request. The Internet Engineering Task Force currently has a working group named Mobile Ad-hoc Networks that is working on routing specifications for ad-hoc networks. This master thesis evaluates some of the protocols put forth by the working group. This evaluation is done by means of simulation using Network simulator 2 from Berkeley. The simulations have shown that there certainly is a need for a special ad-hoc routing protocol when mobility increases. More conventional routing protocols like DSDV have a dramatic decrease in performance when mobility is high. Two of the proposed protocols are DSR and AODV. They perform very well when mobility is high. However, we have found that a routing protocol that entirely depends on messages at the IP-level will not perform well. Some sort of support from the lower layer, for instance link failure detection or neighbor discovery is necessary for high performance. The size of the network and the offered traffic load affects protocols based on source routing, like DSR, to some extent. A large network with many mobile nodes and high offered load will increase the overhead for DSR quite drastically. In these situations, a hop-by-hop based routing protocol like AODV is more desirable.Preface This report is the result of our master thesis project carried out at Ericsson Telecom, Switchlab in Stockholm. This master thesis is also the last part of our Master of Science degree at Luleå University of Technology. Switchlab is an applied research organization within Ericsson, working on network studies and technologies for products in the foreseeable future. This master thesis project has been a cooperation between Switchlab in Stockholm and Ericsson Mobile Data Design (ERV) in Gothenburg. Our master thesis consisted of conducting a simulation study of proposed routing protocols in ad-hoc networks. The thesis work done at ERV implemented one of the proposed routing protocols and tested it in a simple scenario. This has made it possible to share thoughts and ideas with each other. We would like to thank the following persons: Per Johansson for being our supervisor at Switchlab, Bartosz Mielczarek for contribution of the realistic scenarios and Mikael Degermark for being our Examiner at Luleå University of Technology. Also thanks to Johan Köpman and Jerry Svedlund in Gothenburg for discussions and comments regarding AODV. Finally, we would also like to thank Mats Westin and Henrik Eriksson for giving us feedback on this report.Table of Contents 1 INTRODUCTION................................................................................................................................... 9 1.1 BACKGROUND.................................................................................................................................... 9 1.2 PROBLEM DESCRIPTION...................................................................................................................... 9 1.3 RELATED WORK ............................................................................................................................... 10 1.4 PROJECT ORGANIZATION .................................................................................................................. 10 1.5 DISPOSITION..................................................................................................................................... 11 1.6 ABBREVIATIONS............................................................................................................................... 11 2 GENERAL CONCEPTS....................................................................................................................... 12 2.1 WIRELESS AD-HOC NETWORKS......................................................................................................... 12 2.1.1 General.................................................................................................................................... 12 2.1.2 Usage....................................................................................................................................... 13 2.1.3 Characteristics ........................................................................................................................ 13 2.2 ROUTING.......................................................................................................................................... 14 2.2.1 Conventional protocols ........................................................................................................... 14 2.2.2 Link State................................................................................................................................. 14 2.2.3 Distance Vector ....................................................................................................................... 14 2.2.4 Source Routing ........................................................................................................................ 14 2.2.5 Flooding .................................................................................................................................. 15 2.2.6 Classification........................................................................................................................... 15 3 AD-HOC ROUTING PROTOCOLS................................................................................................... 16 3.1 DESIRABLE PROPERTIES ................................................................................................................... 16 3.2 MANET........................................................................................................................................... 17 3.3 DESTINATION SEQUENCED DISTANCE VECTOR - DSDV.................................................................. 17 3.3.1 Description .............................................................................................................................. 17 3.3.2 Properties ................................................................................................................................ 17 3.4 AD-HOC ON DEMAND DISTANCE VECTOR - AODV ......................................................................... 18 3.4.1 Description .............................................................................................................................. 18 3.4.2 Properties ................................................................................................................................ 19 3.5 DYNAMIC SOURCE ROUTING - DSR................................................................................................. 20 3.5.1 Description .............................................................................................................................. 20 3.5.2 Properties ................................................................................................................................ 20 3.6 ZONE ROUTING PROTOCOL - ZRP.................................................................................................... 21 3.6.1 Description .............................................................................................................................. 21 3.6.2 Properties ................................................................................................................................ 22 3.7 TEMPORALLY-ORDERED ROUTING ALGORITHM - TORA ................................................................ 22 3.7.1 Description .............................................................................................................................. 22 3.7.2 Properties ................................................................................................................................ 23 3.8 INTERNET MANET ENCAPSULATION PROTOCOL - IMEP................................................................ 24 3.8.1 Description .............................................................................................................................. 24 3.8.2 Properties ................................................................................................................................ 24 3.9 CLUSTER BASED ROUTING PROTOCOL - CBRP................................................................................ 24 3.9.1 Description .............................................................................................................................. 24 3.9.2 Properties ................................................................................................................................ 26 3.10 COMPARISON.................................................................................................................................... 26 4 SIMULATION ENVIRONMENT ....................................................................................................... 28 4.1 NETWORK SIMULATOR..................................................................................................................... 28 4.2 MOBILITY EXTENSION...................................................................................................................... 29 4.2.1 Shared media........................................................................................................................... 30 4.2.2 Mobile node............................................................................................................................. 304.3 SIMULATION OVERVIEW................................................................................................................... 31 4.4 MODIFICATIONS ............................................................................................................................... 32 4.4.1 AODV ...................................................................................................................................... 32 4.4.2 DSR.......................................................................................................................................... 33 4.4.3 DSDV....................................................................................................................................... 34 4.4.4 Flooding .................................................................................................................................. 34 4.4.5 The simulator........................................................................................................................... 34 5 SIMULATION STUDY ........................................................................................................................ 35 5.1 MEASUREMENTS .............................................................................................................................. 35 5.1.1 Quantitative metrics ................................................................................................................ 35 5.1.2 Parameters .............................................................................................................................. 35 5.1.3 Mobility ................................................................................................................................... 35 5.2 SIMULATION SETUP .......................................................................................................................... 38 5.3 MOBILITY SIMULATIONS .................................................................................................................. 39 5.3.1 Setup........................................................................................................................................ 39 5.3.2 Fraction of received packets.................................................................................................... 40 5.3.3 End-to-end delay ..................................................................................................................... 41 5.3.4 End-to-end throughput ............................................................................................................ 42 5.3.5 Overhead ................................................................................................................................. 43 5.3.6 Optimal path............................................................................................................................ 44 5.3.7 Summary mobility simulations................................................................................................. 46 5.4 OFFERED LOAD SIMULATIONS .......................................................................................................... 46 5.4.1 Setup........................................................................................................................................ 46 5.4.2 Fraction of received packets.................................................................................................... 47 5.4.3 End-to-end delay ..................................................................................................................... 48 5.4.4 End-to-end throughput ............................................................................................................ 49 5.4.5 Overhead ................................................................................................................................. 49 5.4.6 Optimal path............................................................................................................................ 51 5.4.7 Summary offered load simulations .......................................................................................... 51 5.5 NETWORK SIZE SIMULATIONS........................................................................................................... 52 5.6 REALISTIC SCENARIOS...................................................................................................................... 52 5.6.1 Setup........................................................................................................................................ 52 5.6.2 Conference............................................................................................................................... 53 5.6.3 Event coverage ........................................................................................................................ 55 5.6.4 Disaster area ........................................................................................................................... 57 5.6.5 Summary realistic scenarios.................................................................................................... 60 5.7 OBSERVATIONS ................................................................................................................................60 5.7.1 Ability to find routes ................................................................................................................ 60 5.7.2 Temporary backward routes.................................................................................................... 61 5.7.3 Buffers ..................................................................................................................................... 62 5.8 DISCUSSION...................................................................................................................................... 62 5.9 CLASSIFICATION............................................................................................................................... 62 5.9.1 Mobile networks ...................................................................................................................... 63 5.9.2 Size of networks ....................................................................................................................... 63 5.9.3 Network scenarios ................................................................................................................... 64 5.10 IMPROVEMENTS ............................................................................................................................... 64 6 IMPLEMENTATION STUDY ............................................................................................................ 65 DESIGN......................................................................................................................................................... 65 6.1.1 Main ........................................................................................................................................ 65 6.1.2 Event queue ............................................................................................................................. 66 6.1.3 Route table............................................................................................................................... 66 6.1.4 Neighbors / senders ................................................................................................................. 66 6.1.5 Request buffer.......................................................................................................................... 66 6.1.6 Message................................................................................................................................... 66 6.2 SETUP............................................................................................................................................... 66 6.3 TESTING ........................................................................................................................................... 67 6.3.1 Correctness.............................................................................................................................. 67 6.3.2 Performance ............................................................................................................................ 676.4 PROBLEMS / LIMITATIONS................................................................................................................ 67 6.5 IMPROVEMENTS ............................................................................................................................... 68 6.6 IMPLEMENTATION CONCLUSIONS ..................................................................................................... 68 7 CONCLUSIONS.................................................................................................................................... 69 7.1 RESULTS........................................................................................................................................... 69 7.2 FURTHER STUDIES ............................................................................................................................ 69 8 REFERENCES ...................................................................................................................................... 71 APPENDIX A - TERMINOLOGY.............................................................................................................. 73 A.1 GENERAL TERMS.............................................................................................................................. 73 A.2 AD-HOC RELATED TERMS................................................................................................................. 74 APPENDIX B - AODV IMPLEMENTATION FOR NS........................................................................... 75 B.1 MESSAGE FORMATS.......................................................................................................................... 75 B.1.1 Route Request – RREQ............................................................................................................ 75 B.1.2 Route Reply - RREP................................................................................................................. 76 B.1.3 Hello ........................................................................................................................................ 76 B.1.4 Link failure .............................................................................................................................. 76 B.2 DESIGN............................................................................................................................................. 77 B.3 IMPORTANT ROUTINES...................................................................................................................... 78 B.3.1 Sending RREQ......................................................................................................................... 78 B.3.2 Receiving RREQ ...................................................................................................................... 78 B.3.3 Forwarding RREQ................................................................................................................... 79 B.3.4 Forwarding RREP................................................................................................................... 79 B.3.5 Receiving RREP ...................................................................................................................... 79 B.3.6 Hello handling......................................................................................................................... 80 B.3.7 Forwarding packets................................................................................................................. 80 B.3.8 Sending Triggered RREP ........................................................................................................ 80 B.3.9 Receiving Triggered RREP...................................................................................................... 80 APPENDIX C - SIMULATOR SCREENSHOTS ...................................................................................... 81 C.1 NETWORK ANIMATOR ...................................................................................................................... 81 C.2 AD-HOCKEY ..................................................................................................................................... 82List of Figures Figure 1: Example of a simple ad-hoc network with three participating nodes. ......................................... 12 Figure 2: Block diagram of a mobile node acting both as hosts and as router............................................ 13 Figure 3: Network using ZRP. The dashed squares show the routing zones for nodes S and D................. 22 Figure 4: Directed acyclic graph rooted at destination................................................................................ 23 Figure 5: IMEP in the protocol stack. ......................................................................................................... 24 Figure 6: Bi-directional linked clusters....................................................................................................... 25 Figure 7: Network simulator 2.................................................................................................................... 28 Figure 8: Shared media model. ................................................................................................................... 30 Figure 9: A mobile node. ............................................................................................................................ 31 Figure 10: Simulation overview................................................................................................................ 32 Figure 11: Example of mobility. ............................................................................................................... 37 Figure 12: Relation between the number of link changes and mobility.................................................... 37 Figure 13: Mobility simulations - fraction of received packets. ............................................................... 40 Figure 14: Mobility simulations - delay.................................................................................................... 41 Figure 15: Mobility simulations - throughput........................................................................................... 42 Figure 16: Mobility simulations - overhead.............................................................................................. 43 Figure 17: Mobility simulations - optimal path difference. ...................................................................... 45 Figure 18: Offered load simulations - fraction of received packets. ......................................................... 47 Figure 19: Offered load simulations - average delay. ............................................................................... 48 Figure 20: Offered load simulations - average throughput. ...................................................................... 49 Figure 21: Offered load simulations - overhead........................................................................................ 50 Figure 22: Offered load simulations – optimal path.................................................................................. 51 Figure 23: Conference scenario. ............................................................................................................... 54 Figure 24: Event coverage scenario. ......................................................................................................... 56 Figure 25: Disaster area scenario. ............................................................................................................. 58 Figure 26: Simple example scenario......................................................................................................... 60 Figure 27: Overview of AODV daemon................................................................................................... 65 Figure 28: Different router identification approaches. From left to right: 3a, 3b, 3c................................ 70 Figure 29: Route request format. .............................................................................................................. 75 Figure 30: Route reply format................................................................................................................... 76 Figure 31: AODV design of implementation for simulator. ..................................................................... 77 Figure 32: Screenshot – Network animator............................................................................................... 81 Figure 33: Screenshot – Ad-hockey – Conference scenario. .................................................................... 82 Figure 34: Screenshot – Ad-hockey – Event coverage scenario. .............................................................. 83 Figure 35: Screenshot – Ad-hockey – Disaster area. ................................................................................ 83List of Tables Table 1: Neighbor table. ............................................................................................................................ 25 Table 2: Comparison between ad-hoc routing protocols. .......................................................................... 27 Table 3: Constants used in the AODV implementation............................................................................. 33 Table 4: Constants used in the DSR implementation. ...............................................................................33 Table 5: Constants used in the DSDV implementation. ............................................................................ 34 Table 6: Mobility variables........................................................................................................................ 36 Table 7: Parameters used during mobility simulations.............................................................................. 39 Table 8: Optimal path difference for all protocols..................................................................................... 45 Table 9: Parameters used during offered load simulations. ....................................................................... 47 Table 10: Parameters used during realistic simulations............................................................................... 53 Table 11: Parameters used during conference scenario............................................................................... 53 Table 12: Conference simulation results. .................................................................................................... 54 Table 13: Packet drops in conference scenario............................................................................................ 55 Table 14: Parameters used during event coverage scenario. ....................................................................... 55 Table 15: Event coverage simulation results. .............................................................................................. 57 Table 16: Packet drops in event coverage scenario. .................................................................................... 57 Table 17: Parameters used during disaster area scenario............................................................................. 57 Table 18: Disaster area simulation results. .................................................................................................. 59 Table 19: Packet drops in disaster area........................................................................................................ 59 Table 20: Routing tables for AODV after a route discovery process. ......................................................... 60 Table 21: Routing caches for DSR, after a route discovery process............................................................ 611 Introduction 1.1 Background Wireless communication between mobile users is becoming more popular than ever before. This due to recent technological advances in laptop computers and wireless data communication devices, such as wireless modems and wireless LANs. This has lead to lower prices and higher data rates, which are the two main reasons why mobile computing continues to enjoy rapid growth. There are two distinct approaches for enabling wireless communication between two hosts. The first approach is to let the existing cellular network infrastructure carry data as well as voice. The major problems include the problem of handoff, which tries to handle the situation when a connection should be smoothly handed over from one base station to another base station without noticeable delay or packet loss. Another problem is that networks based on the cellular infrastructure are limited to places where there exists such a cellular network infrastructure. The second approach is to form an ad-hoc network among all users wanting to communicate with each other. This means that all users participating in the ad-hoc network must be willing to forward data packets to make sure that the packets are delivered from source to destination. This form of networking is limited in range by the individual nodes transmission ranges and is typically smaller compared to the range of cellular systems. This does not mean that the cellular approach is better than the ad-hoc approach. Ad-hoc networks have several advantages compared to traditional cellular systems. These advantages include: x On demand setup x Fault tolerance x Unconstrained connectivity Ad-hoc networks do not rely on any pre-established infrastructure and can therefore be deployed in places with no infrastructure. This is useful in disaster recovery situations and places with non-existing or damaged communication infrastructure where rapid deployment of a communication network is needed. Ad- hoc networks can also be useful on conferences where people participating in the conference can form a temporary network without engaging the services of any pre-existing network. Because nodes are forwarding packets for each other, some sort of routing protocol is necessary to make the routing decisions. Currently there does not exist any standard for a routing protocol for ad-hoc networks, instead this is work in progress. Many problems remain to be solved before any standard can be determined. This thesis looks at some of these problems and tries to evaluate some of the currently proposed protocols. 1.2 Problem description The objective for this master thesis was to evaluate proposed routing protocols for wireless ad-hoc networks based on performance. This evaluation should be done theoretically and through simulation. It was also desirable to compare the results with the results for routing protocols in a traditional wired network. At the beginning of this master thesis, no implementation of the protocols had been released, so the first main task was to implement some of the protocols. The thesis also included the goal to generate a simulation environment that could be used as a platform for further studies within the area of ad-hoc networks. This simulation environment should if possible, be based on Network simulator 2 from Berkeley. 9The goal of this master thesis was to: x Get a general understanding of ad-hoc networks. x Generate a simulation environment that could be used for further studies. x Implement some of the proposed routing protocols for wireless ad-hoc networks. x Analyze the protocols theoretically and through simulation. x Produce a classification of the protocols with respect to applicability in combinations of small/large networks, and mobile/semi-mobile nodes. x Recommend protocols for specific network scenarios. 1.3 Related work Many routing protocols have been proposed 246810111216192226, but few comparisons between the different protocols have been made. Of the work that has been done in this field, only the work 1 done by the Monarch project at Carnegie Mellon University (CMU) has compared some of the different proposed routing protocols and evaluated them based on the same quantitative metrics. The result was presented in the article “A performance comparison of multi-hop ad hoc wireless network routing protocols” 3 that was released in the beginning of October 1998. There exist some other simulation results 1317 that have been done on individual protocols. These simulations have however not used the same metrics and are therefore not comparable with each other. In parallel with our master thesis, a master thesis project in Gothenburg 28 implemented the AODV 19 protocol and tested it in a environment that consisted of 5 computers with wireless interfaces. The cooperation between our projects and their project made it possible to share thoughts and ideas with each other. 1.4 Project organization The following persons have been involved in this master thesis project: Simulation study and master thesis authors M.Sc. Tony Larsson M.Sc. Nicklas Hedman Supervisor at Ericsson Telecom AB, Switchlab Tekn.Lic. Per Johansson Examiner at Luleå University of Technology Ph. D. Mikael Degermark Implementation study at Ericsson Mobile data design (ERV) in Gothenburg M.Sc. Johan Köpman M.Sc. Jerry Svedlund Supervisor at ERV M.Sc. Christoffer Kanljung Contribution of realistic scenarios Ph.D. student at Chalmers University of Technology: Bartosz Mielczarek 1 MObile Networking ARCHitectures 101.5 Disposition This report consists of 8 chapters and two appendices. Chapters 1 and 2 explain the concept of ad-hoc networks and routing in general. Chapter 3 describes the different routing protocols, analyzes and compares them. Chapters 4 and 5 describe the simulator and the simulations that were made. Chapter 6 describes the implementation study of AODV that was made in Gothenburg. Chapter 7 concludes the whole report and chapter 8 is the references that we have used. The appendices contain some terminology, details about the implementation of AODV that we did for the simulator and some screenshots of the simulator. 1.6 Abbreviations AODV Ad-hoc On-demand Distance Vector CBR Constant Bit Rate CBRP Cluster Based Routing Protocol DSDV Destination Sequenced Distance Vector DSR Dynamic Source Routing IEEE Institute of Electrical and Electronics Engineers IETF Internet Engineering Task Force LAN Local Area Network IP Internet Protocol MAC Media Access Protocol MANET Mobile Ad-hoc NETworks OLSR Optimized Link State Routing Protocol PDA Personal Digital Assistant QoS Quality of Service TCP Transmission Control Protocol TORA Temporally Ordered Routing Algorithm UDP User Datagram Protocol WINET Wireless InterNET ZRP Zone Routing Protocol 112 General Concepts 2.1 Wireless ad-hoc networks 2.1.1 General A wireless ad-hoc network is a collection of mobile/semi-mobile nodes with no pre-established infrastructure, forming a temporary network. Each of the nodes has a wireless interface and communicate with each other over either radio or infrared. Laptop computers and personal digital assistants that communicate directly with each other are some examples of nodes in an ad-hoc network. Nodes in the ad- hoc network are often mobile, but can also consist of stationary nodes, such as access points to the Internet. Semi mobile nodes can be used to deploy relay points in areas where relay points might be needed temporarily. Figure 1 shows a simple ad-hoc network with three nodes. The outermost nodes are not within transmitter range of each other. However the middle node can be used to forward packets between the outermost nodes. The middle node is acting as a router and the three nodes have formed an ad-hoc network. Figure 1: Example of a simple ad-hoc network with three participating nodes. An ad-hoc network uses no centralized administration. This is to be sure that the network wont collapse just because one of the mobile nodes moves out of transmitter range of the others. Nodes should be able to enter/leave the network as they wish. Because of the limited transmitter range of the nodes, multiple hops may be needed to reach other nodes. Every node wishing to participate in an ad-hoc network must be willing to forward packets for other nodes. Thus every node acts both as a host and as a router. A node can be viewed as an abstract entity consisting of a router and a set of affiliated mobile hosts (Figure 2). A router is an entity, which, among other things runs a routing protocol. A mobile host is simply an IP-addressable host/entity in the traditional sense. Ad-hoc networks are also capable of handling topology changes and malfunctions in nodes. It is fixed through network reconfiguration. For instance, if a node leaves the network and causes link breakages, affected nodes can easily request new routes and the problem will be solved. This will slightly increase the delay, but the network will still be operational. 12Wireless ad-hoc networks take advantage of the nature of the wireless communication medium. In other words, in a wired network the physical cabling is done a priori restricting the connection topology of the nodes. This restriction is not present in the wireless domain and, provided that two nodes are within transmitter range of each other, an instantaneous link between them may form. Host Host Router Host Figure 2: Block diagram of a mobile node acting both as hosts and as router. 2.1.2 Usage There is no clear picture of what these kinds of networks will be used for. The suggestions vary from document sharing at conferences to infrastructure enhancements and military applications. In areas where no infrastructure such as the Internet is available an ad-hoc network could be used by a group of wireless mobile hosts. This can be the case in areas where a network infrastructure may be undesirable due to reasons such as cost or convenience. Examples of such situations include disaster recovery personnel or military troops in cases where the normal infrastructure is either unavailable or destroyed. Other examples include business associates wishing to share files in an airport terminal, or a class of students needing to interact during a lecture. If each mobile host wishing to communicate is equipped with a wireless local area network interface, the group of mobile hosts may form an ad-hoc network. Access to the Internet and access to resources in networks such as printers are features that probably also will be supported. 2.1.3 Characteristics Ad-hoc networks are often characterized by a dynamic topology due to the fact that nodes change their physical location by moving around. This favors routing protocols that dynamically discover routes over conventional routing algorithms like distant vector and link state 23. Another characteristic is that a host/node have very limited CPU capacity, storage capacity, battery power and bandwidth, also referred to as a “thin client”. This means that the power usage must be limited thus leading to a limited transmitter range. The access media, the radio environment, also has special characteristics that must be considered when designing protocols for ad-hoc networks. One example of this may be unidirectional links. These links arise when for example two nodes have different strength on their transmitters, allowing only one of the host to hear the other, but can also arise from disturbances from the surroundings. Multihop in a radio environment may result in an overall transmit capacity gain and power gain, due to the squared relation between coverage and required output power. By using multihop, nodes can transmit the packets with a much lower output power. 132.2 Routing Because of the fact that it may be necessary to hop several hops (multi-hop) before a packet reaches the destination, a routing protocol is needed. The routing protocol has two main functions, selection of routes for various source-destination pairs and the delivery of messages to their correct destination. The second function is conceptually straightforward using a variety of protocols and data structures (routing tables). This report is focused on selecting and finding routes. 2.2.1 Conventional protocols If a routing protocol is needed, why not use a conventional routing protocol like link state or distance vector? They are well tested and most computer communications people are familiar with them. The main problem with link-state and distance vector is that they are designed for a static topology, which means that they would have problems to converge to a steady state in an ad-hoc network with a very frequently changing topology. Link state and distance vector would probably work very well in an ad-hoc network with low mobility, i.e. a network where the topology is not changing very often. The problem that still remains is that link-state and distance-vector are highly dependent on periodic control messages. As the number of network nodes can be large, the potential number of destinations is also large. This requires large and frequent exchange of data among the network nodes. This is in contradiction with the fact that all updates in a wireless interconnected ad hoc network are transmitted over the air and thus are costly in resources such as bandwidth, battery power and CPU. Because both link-state and distance vector tries to maintain routes to all reachable destinations, it is necessary to maintain these routes and this also wastes resources for the same reason as above. Another characteristic for conventional protocols are that they assume bi-directional links, e.g. that the transmission between two hosts works equally well in both directions. In the wireless radio environment this is not always the case. Because many of the proposed ad-hoc routing protocols have a traditional routing protocol as underlying algorithm, it is necessary to understand the basic operation for conventional protocols like distance vector, link state and source routing. 2.2.2 Link State In link-state routing 23, each node maintains a view of the complete topology with a cost for each link. To keep these costs consistent; each node periodically broadcasts the link costs of its outgoing links to all other nodes using flooding. As each node receives this information, it updates its view of the network and applies a shortest path algorithm to choose the next-hop for each destination. Some link costs in a node view can be incorrect because of long propagation delays, partitioned networks, etc. Such inconsistent network topology views can lead to formation of routing-loops. These loops are however short-lived, because they disappear in the time it takes a message to traverse the diameter of the network. 2.2.3 Distance Vector In distance vector 23 each node only monitors the cost of its outgoing links, but instead of broadcasting this information to all nodes, it periodically broadcasts to each of its neighbors an estimate of the shortest distance to every other node in the network. The receiving nodes then use this information to recalculate the routing tables, by using a shortest path algorithm. Compared to link-state, distance vector is more computation efficient, easier to implement and requires much less storage space. However, it is well known that distance vector can cause the formation of both short-lived and long-lived routing loops. The primary cause for this is that the nodes choose their next-hops in a completely distributed manner based on information that can be stale. 2.2.4 Source Routing Source routing 23 means that each packet must carry the complete path that the packet should take through the network. The routing decision is therefore made at the source. The advantage with this approach is that it is very easy to avoid routing loops. The disadvantage is that each packet requires a slight overhead. 142.2.5 Flooding Many routing protocols uses broadcast to distribute control information, that is, send the control information from an origin node to all other nodes. A widely used form of broadcasting is flooding 23 and operates as follows. The origin node sends its information to its neighbors (in the wireless case, this means all nodes that are within transmitter range). The neighbors relay it to their neighbors and so on, until the packet has reached all nodes in the network. A node will only relay a packet once and to ensure this some sort of sequence number can be used. This sequence number is increased for each new packet a node sends. 2.2.6 Classification Routing protocols can be classified 1 into different categories depending on their properties. x Centralized vs. Distributed x Static vs. Adaptive x Reactive vs. Proactive One way to categorize the routing protocols is to divide them into centralized and distributed algorithms. In centralized algorithms, all route choices are made at a central node, while in distributed algorithms, the computation of routes is shared among the network nodes. Another classification of routing protocols relates to whether they change routes in response to the traffic input patterns. In static algorithms, the route used by source-destination pairs is fixed regardless of traffic conditions. It can only change in response to a node or link failure. This type of algorithm cannot achieve high throughput under a broad variety of traffic input patterns. Most major packet networks uses some form of adaptive routing where the routes used to route between source-destination pairs may change in response to congestion A third classification that is more related to ad-hoc networks is to classify the routing algorithms as either proactive or reactive. Proactive protocols attempt to continuously evaluate the routes within the network, so that when a packet needs to be forwarded, the route is already known and can be immediately used. The family of Distance-Vector protocols is an example of a proactive scheme. Reactive protocols, on the other hand, invoke a route determination procedure on demand only. Thus, when a route is needed, some sort of global search procedure is employed. The family of classical flooding algorithms belongs to the reactive group. Proactive schemes have the advantage that when a route is needed, the delay before actual packets can be sent is very small. On the other side proactive schemes needs time to converge to a steady state. This can cause problems if the topology is changing frequently. 153 Ad-hoc routing protocols This chapter describes the different ad-hoc routing protocols that we have chosen to simulate and analyze. 3.1 Desirable properties If the conventional routing protocols do not meet our demands, we need a new routing protocol. The question is what properties such protocols should have? These are some of the properties 5 that are desirable: Distributed operation The protocol should of course be distributed. It should not be dependent on a centralized controlling node. This is the case even for stationary networks. The difference is that nodes in an ad-hoc network can enter/leave the network very easily and because of mobility the network can be partitioned. Loop free To improve the overall performance, we want the routing protocol to guarantee that the routes supplied are loop-free. This avoids any waste of bandwidth or CPU consumption. Demand based operation To minimize the control overhead in the network and thus not wasting network resources more than necessary, the protocol should be reactive. This means that the protocol should only react when needed and that the protocol should not periodically broadcast control information. Unidirectional link support The radio environment can cause the formation of unidirectional links. Utilization of these links and not only the bi-directional links improves the routing protocol performance. Security The radio environment is especially vulnerable to impersonation attacks, so to ensure the wanted behavior from the routing protocol, we need some sort of preventive security measures. Authentication and encryption is probably the way to go and the problem here lies within distributing keys among the nodes in the ad-hoc network. There are also discussions about using IP-sec 14 that uses tunneling to transport all packets. Power conservation The nodes in an ad-hoc network can be laptops and thin clients, such as PDAs that are very limited in battery power and therefore uses some sort of stand-by mode to save power. It is therefore important that the routing protocol has support for these sleep-modes. Multiple routes To reduce the number of reactions to topological changes and congestion multiple routes could be used. If one route has become invalid, it is possible that another stored route could still be valid and thus saving the routing protocol from initiating another route discovery procedure. Quality of service support Some sort of Quality of Service support is probably necessary to incorporate into the routing protocol. This has a lot to do with what these networks will be used for. It could for instance be real-time traffic support. None of the proposed protocols from MANET have all these properties, but it is necessary to remember that the protocols are still under development and are probably extended with more functionality. The primary function is still to find a route to the destination, not to find the best/optimal/shortest-path route. The remainder of this chapter will describe the different routing protocols and analyze them theoretically. 163.2 MANET IETF has a working group named MANET (Mobile Ad-hoc Networks) 15 that is working in the field of ad- hoc networks. They are currently developing routing specifications for ad-hoc IP networks that support scaling to a couple of hundred nodes. Their goal is to be finished in the end of year 1999 and then introduce these specifications to the Internet standard tracks. Even if MANET currently is working on routing protocols, it also serves as a meeting place and forum, so people can discuss issues concerning ad-hoc networks. Currently they have seven routing protocol drafts: x AODV - Ad-hoc On Demand Distance Vector 19 x ZRP - Zone Routing Protocol 8 x TORA / IMEP - Temporally Ordered Routing Algorithm / Internet MANET Encapsulation Protocol 61617 x DSR - Dynamic Source Routing 1213 x CBRP - Cluster Based Routing Protocol 11 x CEDAR - Core Extraction Distributed Ad hoc Routing 26 x AMRoute – Ad-hoc Multicast Routing Protocol 2 x OLSR - Optimized Link State Routing Protocol 10 Of these proposed protocols we have chosen to analyze AODV, DSR, ZRP, CBRP and TORA theoretically. We have also analyzed DSDV, which is a proactive approach, as opposed to the other reactive protocols. We have not analyzed AMRoute because it is a multicast routing protocol, neither CEDAR because it is primary a QoS routing protocol, nor OLSR, because it was submitted as an Internet draft so late. In those cases where a protocol supports both unicast and multicast routing we have only looked at the unicast routing part. Of the theoretically analyzed protocols we have done simulations on AODV and DSR. 3.3 Destination Sequenced Distance Vector - DSDV 3.3.1 Description DSDV 22 is a hop-by-hop distance vector routing protocol that in each node has a routing table that for all reachable destinations stores the next-hop and number of hops for that destination. Like distance-vector, DSDV requires that each node periodically broadcast routing updates. The advantage with DSDV over traditional distance vector protocols is that DSDV guarantees loop-freedom. To guarantee loop-freedom DSDV uses a sequence numbers to tag each route. The sequence number shows the freshness of a route and routes with higher sequence numbers are favorable. A route R is considered more favorable than R' if R has a greater sequence number or, if the routes have the same sequence number but R has lower hop-count. The sequence number is increased when a node A detects that a route to a destination D has broken. So the next time node A advertises its routes, it will advertise the route to D with an infinite hop-count and a sequence number that is larger than before. DSDV basically is distance vector with small adjustments to make it better suited for ad-hoc networks. These adjustments consist of triggered updates that will take care of topology changes in the time between broadcasts. To reduce the amount of information in these packets there are two types of update messages defined: full and incremental dump. The full dump carries all available routing information and the incremental dump that only carries the information that has changed since the last dump. 3.3.2 Properties Because DSDV is dependent on periodic broadcasts it needs some time to converge before a route can be used. This converge time can probably be considered negligible in a static wired network, where the topology is not changing so frequently. In an ad-hoc network on the other hand, where the topology is expected to be very dynamic, this converge time will probably mean a lot of dropped packets before a valid route is detected. The periodic broadcasts also add a large amount of overhead into the network. 173.4 Ad-hoc On Demand Distance vector - AODV 3.4.1 Description The Ad Hoc On-Demand Distance Vector (AODV) 19 routing protocol enables multi-hop routing between participating mobile nodes wishing to establish and maintain an ad-hoc network. AODV is based upon the distance vector algorithm. The difference is that AODV is reactive, as opposed to proactive protocols like DV, i.e. AODV only requests a route when needed and does not require nodes to maintain routes to destinations that are not actively used in communications. As long as the endpoints of a communication connection have valid routes to each other, AODV does not play any role. Features of this protocol include loop freedom and that link breakages cause immediate notifications to be sent to the affected set of nodes, but only that set. Additionally, AODV has support for multicast routing and avoids the Bellman Ford "counting to infinity" problem 27. The use of destination sequence numbers guarantees that a route is "fresh". The algorithm uses different messages to discover and maintain links. Whenever a node wants to try and find a route to another node, it broadcasts a Route Request (RREQ) to all its neighbors. The RREQ propagates through the network until it reaches the destination or a node with a fresh enough route to the destination. Then the route is made available by unicasting a RREP back to the source. The algorithm uses hello messages (a special RREP) that are broadcasted periodically to the immediate neighbors. These hello messages are local advertisements for the continued presence of the node and neighbors using routes through the broadcasting node will continue to mark the routes as valid. If hello messages stop coming from a particular node, the neighbor can assume that the node has moved away and mark that link to the node as broken and notify the affected set of nodes by sending a link failure notification (a special RREP) to that set of nodes. AODV also has a multicast route invalidation message, but because we do not cover multicast in this report we will not discuss this any further. Route table management AODV needs to keep track of the following information for each route table entry: x Destination IP Address: IP address for the destination node. x Destination Sequence Number: Sequence number for this destination. x Hop Count: Number of hops to the destination. x Next Hop: The neighbor, which has been designated to forward packets to the destination for this route entry. x Lifetime: The time for which the route is considered valid. x Active neighbor list: Neighbor nodes that are actively using this route entry. x Request buffer: Makes sure that a request is only processed once. Route discovery A node broadcasts a RREQ when it needs a route to a destination and does not have one available. This can happen if the route to the destination is unknown, or if a previously valid route expires. After broadcasting a RREQ, the node waits for a RREP. If the reply is not received within a certain time, the node may rebroadcast the RREQ or assume that there is no route to the destination. Forwarding of RREQs is done when the node receiving a RREQ does not have a route to the destination. It then rebroadcast the RREQ. The node also creates a temporary reverse route to the Source IP Address in its routing table with next hop equal to the IP address field of the neighboring node that sent the broadcast RREQ. This is done to keep track of a route back to the original node making the request, and might be used for an eventual RREP to find its way back to the requesting node. The route is temporary in the sense that it is valid for a much shorter time, than an actual route entry. When the RREQ reaches a node that either is the destination node or a node with a valid route to the destination, a RREP is generated and unicasted back to the requesting node. While this RREP is forwarded, a route is created to the destination and when the RREP reaches the source node, there exists a route from the source to the destination. 18Route maintenance When a node detects that a route to a neighbor no longer is valid, it will remove the routing entry and send a link failure message, a triggered route reply message to the neighbors that are actively using the route, informing them that this route no longer is valid. For this purpose AODV uses a active neighbor list to keep track of the neighbors that are using a particular route. The nodes that receive this message will repeat this procedure. The message will eventually be received by the affected sources that can chose to either stop sending data or requesting a new route by sending out a new RREQ. 3.4.2 Properties The advantage with AODV compared to classical routing protocols like distance vector and link-state is that AODV has greatly reduced the number of routing messages in the network. AODV achieves this by using a reactive approach. This is probably necessary in an ad-hoc network to get reasonably performance when the topology is changing often. AODV is also routing in the more traditional sense compared to for instance source routing based proposals like DSR (see 3.5). The advantage with a more traditional routing protocol in an ad-hoc network is that connections from the ad-hoc network to a wired network like the Internet is most likely easier. The sequence numbers that AODV uses represents the freshness of a route and is increased when something happens in the surrounding area. The sequence prevents loops from being formed, but can however also be the cause for new problems. What happens for instance when the sequence numbers no longer are synchronized in the network? This can happen when the network becomes partitioned, or the sequence numbers wrap around. AODV only support one route for each destination. It should however be fairly easy to modify AODV, so that it supports several routes per destination. Instead of requesting a new route when an old route becomes invalid, the next stored route to that destination could be tried. The probability for that route to still be valid should be rather high. Although the Triggered Route Replies are reduced in number by only sending the Triggered Route Replies to affected senders, they need to traverse the whole way from the failure to the senders. This distance can be quite high in numbers of hops. AODV sends one Triggered RREP for every active neighbor in the active neighbor list for all entries that have been affected of a link failure. This can mean that each active neighbor can receive several triggered RREPs informing about the same link failure, but for different destinations, if a large fraction of the network traffic is routed through the same node and this node goes down. An aggregated solution would be more appropriate here. AODV uses hello messages at the IP-level. This means that AODV does not need support from the link layer to work properly. It is however questionable if this kind of protocol can operate with good performance without support from the link layer. The hello messages adds a significant overhead to the protocol. AODV does not support unidirectional links. When a node receives a RREQ, it will setup a reverse route to the source by using the node that forwarded the RREQ as nexthop. This means that the route reply, in most cases is unicasted back the same way as the route request used. Unidirectional link support would make it possible to utilize all links and not only the bi-directional links. It is however questionable if unidirectional links are desirable in a real environment. The acknowledgements in the MAC protocol IEEE 802.11 would for instance not work with unidirectional links. 19

Advise: Why You Wasting Money in Costly SEO Tools, Use World's Best Free SEO Tool Ubersuggest.