Supervisor: Kaisa Sere
Download 298.62 Kb.
|
- Navigate this page:
- 1INTRODUCTION
|
AD HOC NETWORK PROTOCOLS Case Study: Tree Routing Protocol Robert Löfman Master’s Thesis Supervisor: Kaisa Sere Department of Computer Science Åbo Akademi University Turku, September 2003 Abstract
In ad hoc networks the nodes can be mobile and therefore need temporary communication links based on an unguided medium set up in order to meet the current networking needs. The links are radio channels which access must be coordinated with a medium access control (MAC) protocol. Nodes can communicate directly with nodes that are within the reach of the radio signal, also called neighbors. A network layer routing protocol has to be implemented if we want data packets to be relayed to nodes that are not in the neighborhood. The network protocols found in “normal” fixed networks do not work well for ad hoc networks and many ad hoc protocols have been “tuned” to take the unreliability of radio links into account. TCP must also be redone in order to reach optimality, for instance if fixed network TCP is run on an ad hoc network it can mistake link breakage for congestion. In this thesis we will study the protocols at data link, network and transport layers and then create our own routing protocol called Tree Routing Protocol (TRP). Lastly TRP is evaluated and the conclusions are given. Keywords: Ad hoc network, protocol, layer, MAC, IP, TCP, neighbor, node. Contents
1 INTRODUCTION 1 1.1 Ad Hoc Networks 1 1.2 Security 2 1.3 Power Consumption 3 1.4 Applications for Ad Hoc Networks 4 1.5 Problem Description and Overview of Our Work 5 2 WIRELESS MEDIA ACCESS CONTROL (MAC) 6 2.1 The Shared Medium Problem 7 2.2 MAC Protocols for Ad Hoc Networks 8 2.2.1 CSMA / CA 9 2.2.2 MACA 9 2.2.3 MACAW 10 2.2.4 MACA-BI 11 2.2.5 PAMAS 12 2.2.6 DBTMA 13 2.2.7 MARCH 13 2.2.8 HAMA 14 2.2.9 IEEE 802.11b 15 2.2.10 Bluetooth 17 2.3 Discussion 18 3 AD HOC ROUTING PROTOCOLS 21 3.1 The Routing Problem 21 3.2 Proactive and Reactive Protocols 22 3.3 Classification of Ad Hoc Routing Protocols 23 3.4 Ad hoc On-Demand Distance Vector (AODV) 24 3.4.1 Route Discovery 25 3.4.2 Path Maintenance 26 3.5 The Dynamic Source Routing (DSR) protocol 27 3.5.1 Route discovery process 28 3.5.2 Route Maintenance 28 3.5.3 Reflecting Shorter Routes 29 3.6 Optimized Link State Routing 29 3.7 Discussion 31 4 TCP FOR WIRELESS NETWORKS 32 4.1 Mobile IP 32 4.2 Connecting to the Internet – TCP-I 33 4.3 TCP within the Ad Hoc Network – TCP BuS 33 4.3.1 Domain Name Service 36 4.4 Discussion 37 5 CASE STUDY, TREE ROUTING PROTOCOL 38 5.1 Definitions 38 5.2 Introduction to TRP 39 5.3 Tree Construction - Routing 40 5.4 Forwarding 45 5.4.1 Forwarding of RQMs 45 5.4.2 Preventing Loops 47 5.4.3 Forwarding of Data Messages 51 6 PROOFS 52 7 SIMULATION 55 7.1 A Technical Description of the Protocol Simulator 55 7.1.1 The Virtual MAC Layer 56 7.1.2 The Network Layer 56 7.2 Simulation Settings 57 7.3 Results 60 8 CONCLUSIONS 64 8.1 Summary 64 8.1.1 Scalability 64 8.1.2 Connecting to the Internet 65 SVENSK SAMMANFATTNING ................................................................................... 67 REFERENCES ................................................................................................................. 79 List of Figures Fig. 2 1: Four bit chipping code. 7 Fig. 2 2: Hidden Terminal. 8 Fig. 2 3: Exposed terminal. 8 Fig. 2 4: B cannot respond to A because B is deferring. 11 Fig. 2 5: C requests data from B with a CTS2. 13 Fig. 2 6: Nodes in a HAMA network with assigned priorities. 15 Fig. 2 7: A super frame. 17 Fig. 2 8: Classification of MAC protocols. 20 Fig. 3 9: The zones of LAR. 23 Fig. 3 10: Link breakage between node 4 and 5. 26 Fig. 3 11: A partial route where x forwards a packet to Y also heard by node Z. 29 Fig. 3 12: A part of a converging OLSR network. The fat circles are MPRs. 30 Fig. 4 13: Detection of link breakage. Messages are enumerated chronologically. 34 Fig. 4 14: Cwind expansion. 34 Fig. 5 15: Views of the network. 40 Fig. 5 16: A growing tree. 41 Fig. 5 17: An interlink between two trees. 42 Fig. 5 18: A node moves “up”. 43 Fig. 5 19: A node moves “down”. 43 Fig. 5 20: Change of root. 44 Fig. 5 21: RQM format. 46 Fig. 5 22: RQM broadcast. 47 Fig. 5 23: Message propagation. 48 Fig. 5 24: Incorrect storage time. 49 Fig. 5 25: Correct storage time. 50 Fig. 6 26: Two shortest paths are found between node 4 and node 1. 54 Fig. 7 27: 25 nodes in a 400x400 square meter area. 58 Fig. 7 28: 25 nodes in a 350x350 square meter area. 59 Fig. 7 29: 25 nodes in a 300x300 square meter area. 59 Fig. 7 30: Delivery rate of data messages. 61 Fig. 7 31: RQM rate. 61 Fig. 7 32: Route discovery delay. 62 Fig. 7 33: Relayed control messages. 62
1INTRODUCTIONAd hoc wireless networks are infrastructureless, self-organizing networks of mobile computers operated by humans. The computers have to detect other computers and organize a temporary infrastructure for a dynamic network - hence the term infrastructureless. The temporary infrastructure consists of communication links that make use of unguided media like the radio waves or infrared light. In addition to detecting computers close-by they also have to be able to communicate indirectly with remote computers not in the vicinity. This can be done by letting intermediate computers relay information between two communicating peers. Because computers are mobile, or rather the users are mobile, the current infrastructure has to be known in order to be able to relay information between computers. The goal of ad hoc networking is to provide data communication anywhere that two or more computer users roam, directly or indirectly, as a secluded intranet or as a subnet of the Internet if some computer belonging to the ad hoc network can serve as a gateway. This text will elaborate on software structures, called protocols that make it possible to provide ad hoc wireless computing. Download 298.62 Kb. Share with your friends:
|