Case Study: Tree Routing Protocol

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

i

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. 21: Four bit chipping code. 7

Fig. 22: Hidden Terminal. 7

Fig. 23: Exposed terminal. 8

Fig. 24: B cannot respond to A because B is deferring. 11

Fig. 25: C requests data from B with a CTS2. 13

Fig. 26: Nodes in a HAMA network with assigned priorities. 15

Fig. 27: A super frame. 17

Fig. 28: Classification of MAC protocols. 20

Fig. 31: The zones of LAR. 23

Fig. 32: Link breakage between node 4 and 5. 26

Fig. 33: A partial route where x forwards a packet to Y also heard by node Z. 29

Fig. 34: A part of a converging OLSR network. The fat circles are MPRs. 30

Fig. 41: Detection of link breakage. Messages are enumerated chronologically. 34

Fig. 42: Cwind expansion. 34

Fig. 51: Views of the network. 40

Fig. 52: A growing tree. 41

Fig. 53: An interlink between two trees. 42

Fig. 54: A node moves “up”. 42

Fig. 55: A node moves “down”. 43

Fig. 56: Change of root. 44

Fig. 57: RQM format. 46

Fig. 58: RQM broadcast. 47

Fig. 59: Message propagation. 48

Fig. 510: Incorrect storage time. 49

Fig. 511: Correct storage time. 50

Fig. 61: Two shortest paths are found between node 4 and node 1. 54

Fig. 71: 25 nodes in a 400x400 square meter area. 58

Fig. 72: 25 nodes in a 350x350 square meter area. 59

Fig. 73: 25 nodes in a 300x300 square meter area. 59

Fig. 74: Delivery rate of data messages. 61

Fig. 75: RQM rate. 61

Fig. 76: Route discovery delay. 62

Fig. 77: Relayed control messages. 62

i

1 INTRODUCTION

Ad 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.

1.1 Ad Hoc Networks

Wireless multi-hop[1] ad hoc networks comprise of lightweight mobile computers, also called mobile hosts (the synonym node may also be used), equipped with radio enabled network interface cards to meet communication needs. Every host can communicate directly with hosts to which the radio signal can be “heard”. These nodes are called the neighbors of mobile host. Direct communication between neighbors is facilitated by point-to-point radio links which are also called one “hop” in routing terminology. Radio frequency bands are a scarce resource and often shared among all hosts, some Medium Access Control (MAC[2]) protocol has to be used to coordinate access to the medium. This can be done in a centralized or distributed fashion. For instance, Bluetooth uses a centralized scheme where master of a network assigns turns for transmission to slaves. IEEE 802.11 is a MAC protocol that can utilize both schemes, but in ad hoc networks the distributed scheme is used. In this scheme nodes contend for transmission turns, but if more than one host wants to transmit at the same time, a random host is chosen for transmission. MAC protocols will be discussed in chapter 2 in detail.

In ad hoc networks, mobile hosts serve as user terminals as well as routers, implying that every host taking part in an ad hoc network has to be prepared to forward other host’s traffic. Some protocols are more flexible and allow hosts to omit routing functions when its batteries are showing weakening levels of power. Although a very important issue by itself, battery consumption is not within the scope of this text and only touched briefly upon in section 3 in this chapter. As with fixed networks, a routing protocol (OSI layer 3) has to be used in order to enable forwarding. This protocol performs routing which is a topology discovering process done by the nodes of the network. The type of the routing protocol specifies how much of this information has to be up-to-date (i.e. reactive or proactive). The output of the routing phase is a routing table, which can be consulted as forwarding is performed. This text will, to the largest part deal with routing protocols. Chapter 3 discusses existing routing protocols and chapter 5, 6, 7 and 8 presents a routing protocol developed as a case study for this text and results of the protocol simulation.

As with routing protocols, transport protocols (OSI layer 4) also have to be adapted for ad hoc networks. For instance, the Internet Transmission Control Protocol (TCP) for fixed networks has a congestion control mechanism that can misinterpret link breakage for congestion and slow down data rates in erroneous ways. Transport protocols are usually, in fixed networks, associated with end-to-end communication without intervention of intermediate routers, that is, the routers have no transport layer. In ad hoc networks the intermediate routers (normal nodes) must also participate in the transport layer functions in order to achieve optimal results [Chandran+98].

Security in wireless networks is a enormously intricate issue, requiring a complete text on its own, so an in-depth discussion of the issue will be beyond the scope of this text. A section with a summary of the issue can be found in section 1.2. Different security concerns exist on different layers, for instance at the MAC layer one has to guard against eavesdropping and signal sabotage whereas the network layer must see to it that no node tries to “free-ride” by refusing to forward traffic from other nodes. The network and transport layers may also implement various encryption techniques to hide sensitive data. A last issue covered in this introductory chapter includes applications for ad hoc networks.

1.2 Security

In wireless networks, one has to be extra mindful of the fact that everyone that is in the same area of the network could in theory have access to the medium. If no precaution is taken to prevent this, an unauthorized user could tune in to the right frequency and “listen” to data addressed to other users. The schemes that are briefly talked about in chapter two, called spread spectrum (SS) frequency hopping and SS direct sequence can prevent unauthorized access of the medium. These techniques see to it that the radio signal never stays on the same frequency for more than a fraction of a second and then jumps to another. Only an authenticated receiver is aware of the frequency sequence that the sender uses, so this can at least in theory block outsiders from “overhearing” secret data. In addition, because every node serves as a router as well, it is of outmost importance that a user cannot access data that is being forwarded for another node.

Because it is still possible for unauthorized users to monitor network activity provided that they know the pseudo random sequence, additional encryption techniques have to be provided. In 802.11b wireless networks this is provided with an encryption algorithm called “wireless equivalent privacy” (WEP). The WEP algorithm is, as they put it in [IEEE99] “reasonably strong”, which means that it is difficult enough to make it discouraging to try to discover the secret key with brute force methods in practice. WEP takes care of two things:

·  Encryption of binary data.

·  Protects against unauthorized data tampering.

The process of encryption begins by generating a 64-bit key k, by concatenating a random 24-bit Initialization Vector (IV) and a 40-bit secret key. The strength of the encryption correlates to the length of the secret key and the frequency of its alteration. K is then fed to a pseudo random number sequence generator whose output r is used to encrypt data d by executing r Å d = e. E will have equal length of d plus four bytes containing a Integrity Check Value (ICV). Thus, both the data and ICV is encrypted by r. The four byte ICV is generated by a CRC-32 algorithm based on the plaintext data d. The message that is sent to the other party begins with the IV (as plaintext) followed by e.

For deciphering e, the IV in the message is again concatenated with the pre-distributed[3] secret key and feed into the pseudo random number sequence generator to regenerate the r. The lifetime of the secret key will be prolonged since nodes only have to change the IV and new keys (k) can be generated. Consequently, executing r Å e will generate d.

To implement proper authentication, stations must implement WEP because the same shared secret keys are utilized in both. This works by requiring that a station wanting to connect to the network can encrypt a text string generated by a receiver, belonging to the network. If the requesting station encrypted the random text string so that the receiver can decrypt it, this means that the requesting station “knows” the secret key and is therefore authenticated.

1.3 Power Consumption

Devices in ad hoc networks are battery-driven and should be designed to consume as little power as possible. Energy conserving functions have been implemented at various levels of software. In fact, functions for controlling the power consumption of hardware[4] have been made available (BIOS interfaces) to operating systems. This means that a power consumption policy decisions can be made from user space applications. With this method, a high energy consuming hardware such as displays can be turn off instead of just invoking a screen saver. Also, different power saving states can be defined, corresponding to the current level of usage. Intelligent decisions can be made by the operating system since battery power levels can also be monitored with the help of the interfaces. For instance, a forced, graceful power-down is important before abrupt crashes of the computer happen when the battery suddenly becomes depleted.