Pro 1

A dissertation submitted in partial fulfillment of a University of Greenwich Masters Degree in Computer Systems and Networking

Project Title Evaluating the performance of routing protocols for Mobile Ad Hoc Networks

Name: XXXX Student ID: XXXXXXX

Programme of Study: Computer Systems and Networking

Final Project Report

Project Hand In Date: November 2006

Supervisor: XXXXXXX

Abstract

E

fficient routing in mobile ad hoc networks is very important due to rapid changes in

network topology. Three routing protocols specifically designed for mobile ad hoc networks, namely AODV, DSR and OLSR are compared. Simulation studies using OPNET modeller show that AODV and OLSR perform better than DSR in highly mobile and dense networks, with DSR showing a slight performance improvement in networks with light to medium traffic load, but still cannot be compared to that shown by AODV and OLSR. Details of the simulation experiments and analysis of the results obtained are contained in this report.

MSc. Dissertation

ii

XXXXXXXXX

Acknowledgements

I

would like to thank my Supervisor XXXXXXXXX for all her support during the

implementation of this project, and for taking time out from her busy schedule to offer her assistance and guidance. I am very grateful to my parents for their support, financial and otherwise in the pursuit of my MSc degree, my sisters, brother and friends, for putting up with me during my most trying moments. I would also like to thank the technicians at Queen Mary hardware laboratory 440 for all their help and assistance.

MSc. Dissertation

iii

XXXXXXXXX

Table of Contents ABSTRACT ................................................................................................................................................. II ACKNOWLEDGEMENTS .......................................................................................................................III LIST OF TABLES...................................................................................................................................... VI LIST OF FIGURES...................................................................................................................................VII 1 INTRODUCTION .....................................................................................................................................1 1.1 EVOLUTION OF MANET (MOBILE AD HOC NETWORK) IN BRIEF ....................................................1 1.2 AIM AND OBJECTIVES ..........................................................................................................................2 1.3 PROJECT ROAD MAP............................................................................................................................2 2 LITERATURE REVIEW ..........................................................................................................................3 3 MOBILE AD HOC NETWORKS .........................................................................................................11 3.1 CONCEPTS ..........................................................................................................................................11 3.1.1 Usage and Applications..............................................................................................................12 3.1.2 Characteristics and Challenges .................................................................................................12 3.2 ROUTING.............................................................................................................................................13 3.2.1 Mechanism and Activities ..........................................................................................................13 3.2.2 Metrics ........................................................................................................................................14 3.2.3 Algorithms ..................................................................................................................................14 3.2.4 Desirability and Goals................................................................................................................15 3.3 AD HOC ROUTING PROTOCOLS .........................................................................................................16 3.3.1 Desirable Qualitative Properties ................................................................................................17 3.3.2 Ad Hoc On Demand Distance Vector Protocol – AODV ..........................................................18 3.3.2.1 Mode of Operation ............................................................................................................................ 18 3.3.2.1.1 Message types ............................................................................................................................ 18 3.3.2.1.2 Route Discovery and Requests ................................................................................................. 18 3.3.2.1.3 Sequence Number Maintenance............................................................................................... 20 3.3.2.1.4 Route Replies............................................................................................................................. 21 3.3.2.1.5 Route Maintenance ................................................................................................................... 22 3.3.2.1.6 Maintaining Connectivity............................................................................................................ 23

3.3.3 Dynamic Source Routing Protocol – DSR ................................................................................24 3.3.3.1 Mode of Operation ............................................................................................................................ 24 3.3.3.1.1 Route Discovery......................................................................................................................... 24 3.3.3.1.2 Route Maintenance ................................................................................................................... 26 3.3.3.2 Additional Features........................................................................................................................... 26 3.3.3.2.1 Caching Overhead Routing Information ................................................................................ 26

3.3.4 Optimized Link State Routing Protocol.....................................................................................27 3.3.4.1 Mode of Operation ............................................................................................................................ 28 3.3.4.1.1 Multi Point Relays..................................................................................................................... 29

3.3.5 Topology Dissemination Based On Reverse-Path Forwarding (TBRPF)................................29 3.3.5.1 Mode of Operation ............................................................................................................................ 29 3.3.5.1.1 Neighbour Discovery................................................................................................................. 29 3.3.5.1.2 Routing Module......................................................................................................................... 30

3.4 ROUTING PROTOCOL COMPARISON ..................................................................................................30 4 SIMULATION OVERVIEW ..................................................................................................................32 4.1 PRACTICES AND TECHNIQUES ...........................................................................................................33 4.2 OPNET MODELLER ...........................................................................................................................34 4.2.1 OPNET Architecture..................................................................................................................34 5 SIMULATION MODELS AND STUDY................................................................................................36

MSc. Dissertation

iv

XXXXXXXXX

5.1 MANET NODE STRUCTURE ..............................................................................................................36 5.2 METHODOLOGY AND IMPLEMENTATION ..........................................................................................36 5.2.1 Physical and MAC Layer Model................................................................................................37 5.2.2 Node Mobility Model..................................................................................................................38 5.2.3 Traffic Model..............................................................................................................................38 5.3 PERFORMANCE METRICS ..................................................................................................................38 5.4 IMPLEMENTATION DECISIONS ...........................................................................................................39 5.4.1 Summary of Routing Schemes...................................................................................................39 5.5 SIMULATION SETUP AND STUDY ........................................................................................................41 5.5.1 Mobility Scenario Simulation Setup..........................................................................................42 5.5.1.1 Results Analysis and Summary ........................................................................................................ 44

5.5.2 Offered Load Scenario Simulation Setup..................................................................................47 5.5.2.1 Results Analysis and Summary ........................................................................................................ 48

5.5.3 Network Node Density Scenario Simulation Setup...................................................................51 5.5.3.1 Results Analysis and Summary ........................................................................................................ 52

5.5.4 Results Summary: Mobility vs. Varied Pause Time ..................................................................55 5.5.5 Realistic Scenario – Small business meeting/conference .........................................................55 5.5.3.1 Results Analysis and Summary ........................................................................................................ 56

5.4 GENERAL OBSERVATIONS ..................................................................................................................57 6 CONCLUSION ........................................................................................................................................58 6.1 CONCLUSION ......................................................................................................................................58 6.2 PERSONAL REFLECTION AND CRITICAL ASSESSMENT .......................................................................59 6.3 FUTURE WORK ...................................................................................................................................60 REFERENCES ............................................................................................................................................61 APPENDIX A ..............................................................................................................................................64 AD HOC ROUTING PROTOCOL CHARACTERISTICS AND CLASSIFICATION...............................................64 APPENDIX B...............................................................................................................................................67 SIMULATION ENVIRONMENT AND SCENARIO SCREENSHOTS..................................................................67 Mobility Scenario ................................................................................................................................67 Offered Load Scenario........................................................................................................................72 Network size scenario..........................................................................................................................75 Realistic scenario ................................................................................................................................79 Setting Confidence Intervals...............................................................................................................81 MANET node structure.......................................................................................................................83 Configuring multiple random seed values .........................................................................................84 Ad hoc protocol default parameter configuration..............................................................................85 APPENDIX C ..............................................................................................................................................88 GLOSSARY OF ABBREVIATIONS ...............................................................................................................88 KEYWORDS...............................................................................................................................................89

MSc. Dissertation

v

XXXXXXXXX

List of Tables TABLE 1: SIMULATOR TOOL USAGE STATISTICS ....................................................................... 10 TABLE 2: ROUTING PROTOCOL COMPARISON............................................................................ 31 TABLE 3: PHYSICAL AND MAC LAYER PARAMETERS............................................................... 37 TABLE 4: AODV IMPLEMENTATION CONSTANTS ....................................................................... 39 TABLE 5: DSR IMPLEMENTATION CONSTANTS ........................................................................... 40 TABLE 6: OLSR IMPLEMENTATION CONSTANTS ........................................................................ 40 TABLE 7: MOBILITY SCENARIO PARAMETERS............................................................................ 43 TABLE 8: OFFERED LOAD SCENARIO PARAMETERS ................................................................. 47 TABLE 9: NETWORK NODE DENSITY SCENARIO PARAMETERS ............................................ 51 TABLE 10: REALISTIC SCENARIO PARAMETERS......................................................................... 55

MSc. Dissertation

vi

XXXXXXXXX

List of Figures FIGURE 1: BASIC CHARACTERISTICS OF PROACTIVE ROUTING PROTOCOLS .................. 4 FIGURE 2: OVERALL COMPARISON OF ROUTING CATEGORIES ............................................. 4 FIGURE 3: CLASSIFICATION OF AD HOC ROUTING PROTOCOLS............................................ 5 FIGURE 4: MAIN DIFFERENCES OF AD HOC ROUTING ALGORITHMS ................................... 6 FIGURE 5: SAMPLE PHYSICAL LAYER MODEL FOR MILITARY ENVIRONMENTS ............. 7 FIGURE 6: A TYPICAL AD HOC NETWORK .................................................................................... 11 FIGURE 7: CLASSIFICATION OF VARIOUS MAC SCHEMES ...................................................... 13 FIGURE 8: CLASSIFICATION OF AD HOC ROUTING PROTOCOLS.......................................... 16 FIGURE 9: AODV ROUTE DISCOVERY.............................................................................................. 19 FIGURE 10: AODV ROUTE DISCOVERY – RREQ ............................................................................ 19 FIGURE 11: AODV ROUTE DISCOVERY – RREP............................................................................. 21 FIGURE 12: AODV ROUTE MAINTENANCE – RERR...................................................................... 23 FIGURE 13: DSR BASIC ROUTE DISCOVERY .................................................................................. 25 FIGURE 14: DSR BASIC ROUTE MAINTENANCE............................................................................ 26 FIGURE 15: CACHING OVERHEAD ROUTING INFORMATION.................................................. 26 FIGURE 16: OLSR NETWORK SHOWING MPR AND NON MPR NODES ................................... 28 FIGURE 17: THE MODELING PROCESS ............................................................................................ 32 FIGURE 18: VALIDATION COST AGAINST MODEL CONFIDENCE........................................... 34 FIGURE 19: SIMULATION PROJECT CYCLE................................................................................... 35 FIGURE 20: MANET NODE STRUCTURE .......................................................................................... 36 FIGURE 21: EFFECTS OF INITIAL TRANSIENT ON RESULTS .................................................... 42 FIGURE 22: MOBILITY SCENARIO SIMULATION RESULTS ...................................................... 44 FIGURE 23: EFFECT OF END TO END DELAY ON THROUGHPUT - MOBILITY SCENARIO SIMULATION RESULTS ............................................................................................................... 46 FIGURE 24: OFFERED LOAD SCENARIO SIMULATION RESULTS............................................ 48 FIGURE 25: EFFECT OF END TO END DELAY ON THROUGHPUT – OFFERED LOAD SCENARIO SIMULATION RESULTS ......................................................................................... 50 FIGURE 26: NETWORK NODE DENSITY SCENARIO SIMULATION RESULTS....................... 52 FIGURE 27: MPR COUNT AGAINST NODE DENSITY..................................................................... 53 FIGURE 28: EFFECT OF END TO END DELAY ON THROUGHPUT – NETWORK NODE DENSITY SCENARIO SIMULATION RESULTS....................................................................... 54 FIGURE 29: REALISTIC SCENARIO SIMULATION RESULTS ..................................................... 56 FIGURE 30: AVERAGE ROUTE DISCOVERY TIME........................................................................ 57 FIGURE 31: (A.1) BASIC CHARACTERISTICS OF PROACTIVE ROUTING PROTOCOLS..... 64 FIGURE 32: (A.2) COMPLEX COMPARISON OF PROACTIVE ROUTING PROTOCOLS........ 64 FIGURE 33: (A.3) BASIC CHARACTERISTICS OF REACTIVE ROUTING PROTOCOLS........ 65 FIGURE 34: (A.4) COMPLEX COMPARISON OF PROACTIVE PROTOCOLS............................ 65 FIGURE 35: (A.5) BASIC CHARACTERISTICS OF HYBRID ROUTING PROTOCOLS............. 66 FIGURE 36: COMPLEX COMPARISON OF HYBRID ROUTING PROTOCOLS ......................... 66 FIGURE 37: (B.1) MOBILITY SCENARIO ENVIRONMENT............................................................ 67 FIGURE 38: (B.2) RANDOM WAYPOINT MODEL PARAMETERS................................................ 68 FIGURE 39: (B.3) ASSIGNMENT OF AD HOC ROUTING PROTOCOL AND RAW IP PACKET GENERATION PARAMETERS .................................................................................................... 69 FIGURE 40: (B.4) WIRELESS LAN PARAMETERS ........................................................................... 70 FIGURE 41: (B.5) WIRELESS LAN CHANNEL ATTRIBUTES ........................................................ 71 FIGURE 42: (B.6) OFFERED LOAD SCENARIO ENVIRONMENT ................................................. 72 FIGURE 43: (B.7) RANDOM WAYPOINT PARAMETERS USED IN THE OFFERED LOAD SCENARIO ....................................................................................................................................... 73 FIGURE 44: (B.8) RAW IP PACKET GENERATION PARAMETERS............................................. 74 FIGURE 45: (B.9) NETWORK NODE DENSITY SCENARIO – 30 NODES ..................................... 75 FIGURE 46: (B.10) NETWORK NODE DENSITY SCENARIO – 40 NODES ................................... 76

MSc. Dissertation

vii

XXXXXXXXX

FIGURE 47: (B.11) NETWORK NODE DENSITY SCENARIO – 50 NODES ................................... 77 FIGURE 48: (B.12) IP PACKET GENERATION PARAMETERS...................................................... 78 FIGURE 49: (B.13) REALISTIC SCENARIO ENVIRONMENT ........................................................ 79 FIGURE 50: (B.14) REALISTIC SCENARIO RWP PARAMETERS ................................................. 80 FIGURE 51: (B.15) CONFIGURING CONFIDENCE INTERVALS ................................................... 81 FIGURE 52: (B.16) CONFIGURING CONFIDENCE INTERVALS FROM EDITING GRAPH PANEL PROPERTIES..................................................................................................................... 82 FIGURE 53: MANET NODE STRUCTURE .......................................................................................... 83 FIGURE 54: (B.18) MULTIPLE RANDOM SEED VALUE CONFIGURATION.............................. 84 FIGURE 55: (B.19) AODV DEFAULT PARAMETERS ....................................................................... 85 FIGURE 56: (B.20) DSR DEFAULT PARAMETERS ........................................................................... 86 FIGURE 57: (B.21) OLSR DEFAULT PARAMETERS ........................................................................ 87

MSc. Dissertation

viii

XXXXXXXXX

1 Introduction “The networking opportunities for MANETs are intriguing and the engineering trade-offs are many and challenging”. Corson and Macker (Corson and Macker 1999) [6]

T

he interest in Mobile ad hoc networks has become very widespread due to the wide

availability of devices that can communicate using wireless means such as PDAs’ (Personal Digital Assistants) and laptops. This has led to the realisation that traditional routing methods used in wired networks, as good as they are will not be appropriate for ad hoc networks, where there is no centralized authority like access points or dedicated routers, to handle the routing of packets and making decisions on best routes, based on different routing metrics such as hop count, link cost, load, reliability and bandwidth, to name but a few.

1.1 Evolution of MANET (Mobile Ad Hoc Network) in Brief The interest in mobile ad hoc networks first started with a [1] military inclination, where it is more than likely there would be a necessity to form networks on the fly and in hostile territory. The idea of setting up base stations in such an environment is not feasible, and there is the possibility of failure of these equipment, hence the need for a completely distributed network where all devices involved act as peers and are equipped to relay information for one another with emphasis on cases where some devices may be out of communication range. The [1] Packet Radio Network was developed in 1972, sponsored by [4] DARPA, and combines the traditional packet switching technique with the above. This was followed by the [1] SURAN, the Survivable Radio Network in 1983 and several others were to follow subsequently. Ad hoc networks are ideal in certain scenarios and situations such as disaster recovery, emergency rescue and areas where no previous infrastructure existed. As wireless devices become more and more available, a number of routing protocols have been proposed. [2] The IETF set up the MANET working group in 1997 to review and standardise routing protocols suitable for ad hoc networks due to their wireless transmissions, dynamic topologies and mobility. Quite a number of routing protocols have been proposed to date, [3] presents a long but comprehensive list on information about the protocols available, including links to IETF drafts, RFCs’ where applicable, and other useful links that apply. The exact number cannot be determined currently. Only a few as listed in [4] have been accepted for publication as experimental RFC’s (Request For Comments). The MANET WG has made the RFCs’ for these protocols available at their website. The protocols available are Ad hoc On Demand Distance Vector (AODV) Routing (RFC 3561), Optimized link State routing Protocol (RFC 3626) and Topology Dissemination Based on Reverse-Path Forwarding (TBRPF) (RFC 3684).

MSc. Dissertation

1

XXXXXXXXX

1.2 Aim and Objectives The overall goal of this project is to measure the performance of three well known routing protocols under a variety of conditions, while incorporating the important simulation techniques of publishing all simulation model parameters and discarding the initial transient results. To achieve the above, a set of objectives was drawn up; the steps followed are presented below: • • • • •

•

Literature search and review of previous work by other researchers. Introductory background into mobile ad hoc networks. Theoretical analysis, classification and comparison of Ad hoc routing protocols. Simulation study of protocols in a variety of network conditions. Analysis of results obtained, and general observations. Conclusion and recommendations.

1.3 Project Road Map Chapter 2: Literature Review This chapter presents a critical evaluation of scholarly journals, articles, and other sources relevant to this project. Descriptions and summaries are provided for each work reviewed and the purpose is to give an overview of noteworthy literature on the project topic area. Chapter 3: Mobile Ad hoc Networks This chapter deals with mobile ad hoc networks, its concept, characteristics, usage and applications and detailed features and mode of operation of ad hoc routing protocols. General routing concepts are also discussed briefly. Chapter 4: Simulation Overview The principles and techniques of best simulation practices involved in carrying out successful simulation and modelling studies are covered here. This includes the simulation life cycle and modelling process. Also contained in this chapter is a short description of OPNET, the simulation tool used in the implementation phase. Chapter 5: Simulation Models and study The implementation stage is covered here, describing the implementation decisions and methodology. Model descriptions and parameters used are presented explicitly, as well as the set up of the variety of network conditions i.e. scenarios. The summary and analysis of results obtained as well as observations, round up this chapter. Chapter 6: Conclusion A summary of the main points from the study, personal reflection and critical assessment of work done, problems encountered and self development during the duration of the project, are presented in this concluding chapter. Also recommendations for future work and extensions to current study, come under this chapter.

MSc. Dissertation

2

XXXXXXXXX

2 Literature Review

T

he need to communicate on the fly is growing at a fast rate and the availability of

inexpensive wireless communication capable devices has led to the increasing interest in the research of mobile ad hoc networking. The National Institute of Standards [5] reckon that wireless networks are swiftly moving towards an era where situations will need swift deployment of mobile infrastructure with example scenarios such as disaster relief efforts, emergency rescue and military operations. The realisation that traditional routing methods and protocols used in wired networks would not be ideal for such dynamic networks as ad hoc, has led to the proposal of a number of ad hoc routing protocols. [2]The IETF set up the MANET working group in 1997 to review and standardise routing protocols, since then quite a number of them have been proposed. [3] Presents quite a long but comprehensive list on information about the protocols available, including links to IETF drafts, RFCs’ where applicable, and other useful links that apply. It is interesting to note that most of the protocols presented in that list do not seem to have enough information apart from their author’s details. The only ones with useful information are those with RFCs and links to the IETF website. The exact number cannot be determined currently but only a few as listed in [4] have been accepted for publication as experimental RFC’s (Request for comments). Owing to this, researchers are able to use the information available to evaluate and compare the performances of these protocols, under varying conditions. Corson and Macker [6] have come up with an interesting outline to evaluate the performance of routing protocols, using qualitative and quantitative metrics, as well as networking metrics. They believe these metrics are needed to determine the suitability of a routing protocol. Properties such as distributed operation, loop free, demand and proactive based operations, security, sleep period and unidirectional link support are some of the desirable qualitative properties, quantitative metrics such as end to end throughput and delay, route acquisition time and network metrics like network size, link capacity etc. In their view, the good and bad points of a protocol should be put forward so as to aid in the identification and classification as per its usage. The beauty of Corson and Macker’s [6] outline is that it makes clear what parameters that can and should be incorporated while evaluating a routing protocol. There seems to be scant literature on theoretical evaluation of routing protocols, Mehran Abolhasan et al [7] have incorporated in their simulation studies the view of Corson and Macker [6] on putting forward the advantages and disadvantages and also a classification of routing protocols. Their reasoning behind their work is due the fact that there are quite a number of routing protocols that have been proposed following the active research and interest in mobile networking and virtually every author argues the good points about their protocol strategies making it quite difficult to determine their individual performances. They have evaluated and classified protocols albeit theoretically using basic characteristics, complex comparisons grouping them into the 3 well known categories of Reactive, Proactive and Hybrid. Pandey and Fujinoki [20] also did similar work by comparing and categorizing ad hoc routing protocols in their simulation studies. Samples of their work are as shown below. Complete samples of the comparison exercise by [7], can be found at Appendix A.

MSc. Dissertation

3

XXXXXXXXX

Figure 1: Basic characteristics of proactive routing protocols [7]

Figure 2: Overall comparison of routing categories [7]

MSc. Dissertation

4

XXXXXXXXX

Figure 3: Classification of ad hoc routing protocols [20]

Simulation plays an important role in understanding and evaluating the performances of routing protocols on networks, which is why it is quite important that simulation tools models, default parameters, scenarios and assumptions are carefully described and understood. Perrone et al [8] expressed the above using 3 case studies and were concerned with how initial transient problem affects simulations and how not incorporating “the best practices of simulation techniques”[8] does not help the “advancement of scientific contributions” [8], as it makes it quite difficult for others to replicate or build on existing work. They also pointed out that the well known practice of using “warm up models”[8] which avoids the “initial transient” problems mostly associated with mobility models are hardly mentioned in most scientific publications, and authors do not give a listing of simulation parameter values due to lack of space, and this should be addressed by providing further information on websites. Several authors have gone ahead to research the performances of several routing protocols through simulation. Broch et al [9] and Das et al [10] incorporated the radio propagation model of 2 ray ground model (1/r4) for far distances and the Friss-space attenuation (1/r2) model for near distances, in their physical layer model while evaluating the AODV, DSR, DSDV, and TORA routing protocols. Ramachandra et al [11] focused on evaluating and comparing the protocols’ performance on 3 different Ad hoc architectures [9], including the ARP protocol in their protocol stack modelling, and their reasoning behind this is all routing protocols operate at the network layer; therefore IP addresses will need resolution. Boukerche [13] presented the main differences in a tabular form in evaluating the performance of AODV, PAODV, CBRP, DSR and DSDV, and

MSc. Dissertation

5

XXXXXXXXX

gave a good insight that despite the similarities exhibited, there were still important differences that impact on their individual performances.

Figure 4: Main differences of Ad hoc routing algorithms [13]

It is quite important to model a realistic physical layer model during simulations and not many performance studies do this, as rightly pointed out by Gauthier et al [12] while evaluating the performances of AODV, DSR, LANMAR and OLSR using a radio propagation model with and without interferences. Their conclusion was that “the amount of interferences is directly related to the quality of the route and more specifically to the number of hops and the quality of traffic” [12]. Some researchers have addressed the problem of not evaluating protocols in a realistic environment to analyze their performances. Marinoni and Kari [15], Jardosh et al [16] reason that most simulation studies do not consider the fact that obstacles such as buildings can act as sources of obstruction and interference. Moreover this should be the case since ad hoc networks are usually deployed in areas such as cities, campuses and the like. Choi and Ko [17], Marinoni and Kari [15], Jardosh et al [16] and Johansson et al [14], evaluated different routing protocols in various simulated realistic environment. Choi and Ko [17] employed a realistic military scenario with a physical layer model which they felt was more appropriate and reflected a typical military environment. They argued that most simulation studies usually make use of parameters that reflect a more “commercial setting” [17] where they make use of the 2.4GHz ISM band and its associated parameters, which is far removed from a military setting with typical ranges of 100MHz frequency band more likely VHF or HF, and with low data transmissions rates within the range 384Kbps. Below is a table from their journal, with summary of the parameters.

MSc. Dissertation

6

XXXXXXXXX

Figure 5: Sample physical layer model for military environments [17]

Marinoni and Kari [15] and Jardosh et al [16] focused on studying and analyzing the protocols in scenarios involving the presence of obstacles. Both authors proposed realistic mobility models that model realistic user behaviour and compared results of their mobility model with the random waypoint model. [15] proposed the Urban Mobility Model (UMM) which “describes real world details of a city-like environment that demonstrates the impact of realistic mobility patterns and radio propagation models on the performance of MANET routing protocols” [15], while [16] proposed the Object Mobility model (OM) which focuses on obstacle scenarios specifically on building type obstacles of varying sizes, using polygons to represent the obstacles. Both researchers came to the conclusion that obstacles do have an impact on the performance of routing protocols. Johansson et al [14] simulated 3 different realistic scenarios of conference, event coverage and disaster area to analyse the AODV, DSR and DSDV protocols. They discovered that the protocols were more challenged in the disaster area scenario, because of frequent network partitioning. Oliveira et al [18] and Campos and Elias [19] both studied and analyzed protocol performance over application programs. [18] “conducted a detailed study of a Gnutella like application (peerto-peer) running over a MANET” [18] using the DSDV, DSR and AODV routing protocols. Results showed that protocols performed well depending on the qualitative metric under which the protocol is being analyzed, and came to the conclusion of the “importance of considering characteristics of both application and network in order to have the best integrated solution” [18]. [19] studied the DSDV, DSR, AODV and TORA routing protocols in a “hybrid ad hoc network scenario used by mobile users to establish videophone sessions” [19]. It was discovered that the reactive protocols performed better than the proactive protocols reason being due to their on demand and route maintenance properties. They came to the conclusion that “the adoption of a given routing protocol ought to be guided by a comparative analysis that evaluates the particular network scenario and the interested application class” [19]. Mobility is another important simulation area and most researchers are interested in how this parameter affects the performance of routing protocol, since it is the basis of ad hoc networks. Marinoni and Kari [15], Jardosh et al [16], Ishibashi and Boutaba [21], Lenders et al [22], Bettstetter [23], Stepanov et al [24] and Sirivianos and Leontaris [25], all studied the impact of mobility in their performance evaluation of routing protocols under different environments.

MSc. Dissertation

7

XXXXXXXXX

Marinoni and Kari [15], Jardosh et al [16] and Bettstetter [23] all proposed various realistic mobility models which they compared with the random waypoint model, in their performance evaluation of the DSR [15] and AODV [16] protocols respectively. The UMM (Urban Mobility Model) model was proposed by [15] to model realistic user behaviour in a city like scenario complete with obstacles and are of the mind that “topology and movement are key simulation factors that affect protocol performance” [15]. [16] Proposed the OM (Obstacle Mobility) model to reflect a realistic college campus scenario based on the location of buildings in a selected area of the University of California. They believe that “simulations should reflect realistic mobility behaviour since it is important in order to carry out meaningful performance analysis of routing algorithms” [16]. Ishibashi and Boutaba [21] and Lenders et al [22] focused on how mobility affected links and route life time which is “considered important in designing MAC and network layer protocols” [22]. Lenders et al [22] were of the opinion that no “real-life measurements have been used to study the effects of node mobility on link and route lifetime” [22]. Hence they created a real ad hoc network of 20 PDAs’ “connected via 802.11b wireless interfaces”, [22] to analyse this issue. It was discovered that the failures associated with links was also caused by other factors such as collisions and interferences apart from human mobility. They also conducted simulations using the 2 popular mobility models, random way point and random reference point. A comparison of results from both the simulations and empirical study was possible due to the “isolation and separation of link failures caused by mobility and collisions or interferences” [22] and the conclusion arrived at was that the results were close and that user mobility was modelled the same, in both situations. Ishibashi and Boutaba [21] tackled the issue by studying their features through parameters such as node density, network dimension, radio transmission range and mobility settings of maximum speed and wait times. They discovered that “many links break after a relatively short time period” [21] and that node density can be an asset as well as a liability in regards to how it creates wireless medium contention while at the same time providing multiple routes, which helps in the reduction of broadcast messages. Bettstetter [23] proposed a 2 dimensional SMM (Smooth Random Mobility model) which is halfway between a realistic mobility model and the random waypoint model that reflects smoother user movement than in well known mobility models. He was of the view that not making the right choice in mobility model “could lead to incorrect simulation results.”[23] Stepanov et al [24] focused on modelling mobility that reflected user behaviour in out door scenarios, describing the “main factors that influence user movement” [24]. They base their mobility model on a user oriented mobility meta-model which is a generic mobility model”. Sirivianos and Leontaris [25] based their research on studying protocol performance “under extreme mobility (over 20m/s)” [25]. Results show that out of the 3 protocols i.e. AODV, DSR and FSR studied, AODV performed best. A few researchers have gone further by analysing protocol performance through conducting test bed emulations. Haq and Kunz [26] and Chin et al [27] focused their attention on this area. [26] Were interested in the extent to which simulation and emulation differ, in terms of results

MSc. Dissertation

8

XXXXXXXXX

obtained in both environments, to provide guidelines as to what tool would be appropriate when studying the performance of protocols. They studied the OLSR protocol in the test bed environment using 5 laptops with Linux OS equipped with 802.11b wireless NICs’, and using the GloMoSim and NS-2 tools for the simulations. It was discovered that at low traffic rates, results from simulations and test bed were close, but was the opposite at high traffic rates and even incomparable. They reckon that to obtain realistic results from a simulation, the use of lower bandwidth could be the key, as using a high bandwidth value could result in routing protocols not evaluated properly. Chin et al [27] argued that their work was a necessity due to a “lack of published results on the implementation of routing protocols on actual wireless networks”. [27] They emulated the AODV and DSDV protocols on a 5 hop 4 node test bed on Linux workstations equipped with 802.11b wireless LAN NICs, and discovered that “neither protocol could provide a stable route over any multi-hop network connection”.[27] They came to the conclusion that contrary to what was reported in most publications, routing protocols were not up to scratch in their performance when emulated rather than simulated. They highlighted the following areas for improvements: 1. 2. 3. 4.

Handling unreliable/unstable links. Minimizing the dependency on topology specific parameters. Mechanisms for handoff and reducing packet loss during handoff. Incorporating neighbour discovery and filtering into a neighbour selection sub-layer.

During the review of literature for this project it was discovered that researchers’ all used different simulation tools in their evaluation of routing protocols. The table below gives the statistics of the tool usage.

MSc. Dissertation

9

XXXXXXXXX

Table 1: Simulator tool usage statistics

MaRs 1

ns-2 6

GloMoSim 3

J-SIM 1

OPNET 0

QualNet 1

As can be seen, most researchers favoured the ns-2 simulator, which could be due to the fact that it is an open source tool. Comparing results from each work could prove a difficult task since there is a possibility that results could vary since modelled scenarios and their associated parameters, differ from researcher to researcher, depending on the area of interest under study. As reported by Cavin et al [28] during a study carried out on 3 popular simulators (OPNET, NS-2 and GloMoSim) to simulate a simple flooding algorithm involving 50 nodes, it was discovered that there was a “significant divergence” [28] in results obtained and in some cases, incomparable. Haq and Kunz [26] further buttress the above during their study that “despite all the cutting edge and technological achievement in the mobile wireless network field, there are growing concerns about the reliability of simulation results”.[26] Owing to these studies and discoveries above it follows that there would be considerable difficulty in comparing evaluation results as noted by Ishibashi and Boutaba [21]. Another area of discovery during the review was that some researchers do not include in their work the all important simulation parameter values used during their study. Only a few bother to state them and even at that it is either they give a mention of the protocol simulation parameters and not mention the MAC and Physical model parameters or vice versa. Broch et al [9] and Sirivianos, Leontaris [25] and Johansson et al [14] outshone the others in this very important aspect of simulation as stressed by Perrone et al [8]. On discarding the transient results during simulation, only Marinoni and Kari [15] kept to this practice in their work. This project will focus on evaluating ad hoc routing protocols using the OPNET simulator, and will try as much as possible to incorporate all the good practices of simulation techniques, in order to allow others to build and improve on. As rightly pointed out by Ishibashi and Boutaba [21], a “better understanding of MANET parameters and characteristics will: • • • •

Allow a wiser selection of scenarios for testing and evaluation. Reduce or eliminate design decisions based on faulty assumptions. Promote optimization of parameters for real network conditions Reveal characteristics to be used in developing future protocols”. [21]

MSc. Dissertation

10

XXXXXXXXX

3 Mobile Ad hoc Networks “The wireless environment is one of scarcity rather than abundance, wherein bandwidth is relatively limited, and energy may be as well”. Corson and Macker (Corson and Macker 1999) [6]

3.1 Concepts

A

n ad hoc network also known as wireless ad hoc network is a network with a collection of

nodes or devices with wireless capabilities. They are formed out of a need to communicate on the fly hence are different from conventional wired networks. They have no dedicated or centralized authority, all nodes are peers. Since there are no dedicated routers or central servers, all nodes in the network act as routers, hence the term multi-hop, meaning transmissions are relayed by several nodes along the path from the source to the final destination.

Figure 6: A typical Ad hoc network [1]

When the nodes in an ad hoc network are mobile, then it is referred to as a mobile ad hoc network. [30] Devices could be laptops, and PDAs’ (personal digital assistant). [6] Nodes can be found in or on aeroplanes, ships, cars, and individuals. The presence of no central authority ensures network availability and the chances of unavailability of resources are reduced in the event that a node suddenly moves out of transmission range of the others. Nodes are free to enter and leave the network whenever they wish since communications only last for specific time periods; therefore the network should ideally be able to adapt to the new conditions.

MSc. Dissertation

11

XXXXXXXXX

3.1.1 Usage and Applications Ad hoc networks are ideal and applicable for certain situations such as in areas where no previous infrastructure may have existed. Examples of such environments could be deep in a jungle, areas hit by a natural disaster, mountain climbing expeditions, and desert trips. Another important area is military operations especially in hostile territory where it is impossible to set up base stations to enable communications, and moreover they can easily be destroyed. Communication in military operations especially of the hostile type was the original idea behind ad hoc networks. Other areas are at conferences where participants can share files, disaster recovery and relief situations, emergency services, rescue operations, entertainment industry where audio or video content can be accessed interactively. More areas include [29] mobile commerce where real time business can be conducted while on the go.

3.1.2 Characteristics and Challenges Ad hoc networks are typically characterized by rapid and dynamic changes in network topology due to the mobility of participating nodes. Another feature is their limited transmission range and bandwidth [30] capacity when compared to wired networks. The ISM (Industrial, Scientific and Medical) band which is license free is usually utilized by ad hoc networks. Wireless network links are prone to certain factors such as interference, noise, signal fading, and congestion due to the constrained link capacity, which will always be a problem since mobile networks are seen as extensions [6] of fixed networks hence users’ demands and expectations in terms of network services will be the same. Nodes also suffer from limited CPU, storage capacity and battery power, and have to conserve energy. The limited battery power also affects the transmission range capabilities of the nodes. The links between communicating nodes are usually [30] bi-directional but could also be uni-directional which tends to happen when the transmission power between communicating nodes are different. Another important feature is that of security, since the wireless links are virtually in open air, they can easily be tapped into and transmissions intercepted. The MAC protocol scheme of CSMA/CD (Carrier Sense Medium Access Collision Detection) applied in wired networks cannot be used in wireless networks, since it involves medium contention which is not desirable in wireless networks since signal strength decreases as distance increases and a signal on the medium arriving at the receiving end may not be sensed by other nodes that are out of range. Several MAC protocol schemes have been developed for wireless networks, and can be classified into contention-free and contention-based. S. Kumar et al (2006) [30] used a hierarchical organizational chart to classify some of the various MAC schemes as reproduced below.

MSc. Dissertation

12

XXXXXXXXX

Figure 7: Classification of various MAC schemes [30]

3.2 Routing Routing [31] refers to a means by which information is transmitted from a given source to a destination in an internetwork. Routing is often mixed up with bridging, while the latter operates in layer 2 of the OSI reference model using MAC addresses’, the former operates at layer 3 of the OSI reference layer using IP addresses. Routing involves maintaining what is known as a routing table containing a list of known IP addresses of various network destinations. Each router in a network maintains a routing table which is used to make forwarding decisions when a packet is received for a given destination. The tables contain a listing of destination IP addresses - next hop mappings. The next hop could either be indicated by the outgoing interface number of the router or its IP address.

3.2.1 Mechanism and Activities Routing involves basically two activities which are actually moving a packet to its intended destination, also known as packet switching and finding the best path through which to route packets, also known as path determination [31]. While the former is a straight forward operation, which involves determining where a packet should be sent by examining the MAC address, the latter is a more complex activity of using metrics to calculate the best route to any given destination, and uses the IP address or Network ID to determine a packets destination. While switching involves the movement of packets within networks, routing involves moving packets between different networks.

MSc. Dissertation

13

XXXXXXXXX

3.2.2 Metrics Routing protocols use metrics to determine the best path for routing packets. These metrics differ from protocol to protocol depending on the routing algorithm in use. [31] Some common metrics are hop count, load, bandwidth, delay, communication cost, reliability, and protocols either use one, more, or a combination of these metrics, depending on their complexity. In general the more complex a routing protocol is, the more metrics employed in the routing process. A brief description of some of the metrics are outlined below •

Hop Count is the most common metric and refers to how far away a given destination is based on the number of intermediate routers a packet will have to go through, between the source and destination.

•

Load refers to how busy a network is, in terms of the amount of work the devices in the network have to perform. Load could be calculated as the number of packets being processed per second, CPU utilization, or memory usage.

•

Bandwidth refers to the capacity of a link in terms of the amount of data in bits, and how fast in terms of seconds a data packet can be transmitted, in other words the traffic capacity of a link.

•

Delay refers to the time it takes for a packet to travel from the source to the destination while taking into consideration factors such as congestion at the intermediate devices on the path between the source and destination, the distance and also queues at in-going router ports.

•

Reliability refers to how dependable a network link is in terms of how often it fails, how quickly it is repaired and how often it is utilized in routing packets. These factors are taken into account during the assignment of link reliability ratings which are numeric values that are arbitrarily decided on by the network administrator.

3.2.3 Algorithms Routing protocols use the mathematical rules as dictated by the algorithms to maintain their tables and choose the best route for packet forwarding from source to destination, and can be classified according to the type of algorithm used and other properties. They are either classified as distance vector or link state. The distance vector algorithm is based on the Bellman Ford algorithm [31]. Protocols based on this algorithm are aware of only neighbouring routers, and the routers exchange all or a portion of their routing tables with neighbouring routers only, periodically. The time interval between the exchanges of routing tables updates differ depending on the distance vector routing protocol in use. For example RIP uses an interval of 30 seconds and IGRP 90 seconds. Link State algorithm [31] also known as the shortest path first algorithm, is based on the Djikstra algorithm [31] where each router builds a complete view of the entire network. Updates are sent to all routers in the network only when a change in the network status occurs. The updates are small when compared to that of distance vector. At the initial network configuration the updates are flooded throughout the network, and then are only triggered when link state changes occur. These updates are also known as link state advertisements (LSA).

MSc. Dissertation

14

XXXXXXXXX

Link state algorithms are said to converge more quickly when compared to distance vector algorithms since all routers have up to date information and complete view of the network topology, which make them less prone to routing loops. Due to the initial flooding of updates, link state algorithms require more processing power and memory. Although they are more scalable than distance vector algorithms, they are more complicated to implement as well as expensive to maintain. Other routing algorithm types besides the popular 2 described above are listed below. • • • • •

Static versus Dynamic Single-Path versus Multi-path Flat versus Hierarchical Host-Intelligent versus Router-Intelligent Interdomain versus Intradomain

3.2.4 Desirability and Goals Routing algorithms usually have one or more design goals. Some of the goals and desirable properties according to the Cisco Internetworking Technologies Handbook (2002) [31] are: •

Optimality Being able to select the best route which depends on one or more metric used by the algorithm.

•

Simplicity and low overhead Routing algorithms should be simple to ensure they perform efficiently and with little or no overheads, especially when faced with limited hardware and software resources.

•

Robustness and stability Algorithms should be able to perform reasonably in the event of circumstances such as hardware failure, increased load. The best algorithms are those that can remain stable and reliable no matter the network condition.

•

Rapid convergence Routing algorithm should be able to converge quickly i.e. where all routers have the same knowledge of the network topology and are in agreement. Slow convergence could lead to routing loops and network outages.

•

Flexibility Routing algorithms should be flexible in the sense that they can be able to respond to and adapt to changes in the network topology. Such changes could be in the form of network bandwidth, delay and so on.

MSc. Dissertation

15

XXXXXXXXX

3.3 Ad Hoc Routing Protocols “A MANET protocol should function effectively over a wide range of networking contexts – from small, collaborative, ad hoc groups to larger mobile, multi-hop networks.” Corson and Macker (Corson and Macker 1999) [6]

Routing in mobile ad hoc networks is quite different from conventional routing in wired networks because it is more complex and challenging, and therefore requires special routing protocols to handle the challenges. Quite a number of MANET routing protocols have been proposed, with only a few published as experimental protocols using the Request For Comments documents, while others are available as Internet drafts. A full list of protocols, as regards their documentation and statuses, i.e. published, active, Internet drafts, expired etc, are available on the Internet Engineering Task Force (IETF) MANET status pages.[33]. Ad hoc routing protocols can be classified into reactive, proactive or hybrid as illustrated below in figure 2, depending on their mode of operation.

Figure 8: Classification of ad hoc routing protocols [20] Only some of the protocols have been discussed in this chapter to avoid going over the project documentation limit. More focus has been paid to the currently published protocols, and some of the more popular Internet draft protocols, as listed on the IETF MANET charter website. The three protocols to be evaluated in this project are also part of the discussion below, hence more detail has been provided compared to the others.

MSc. Dissertation

16

XXXXXXXXX

3.3.1 Desirable Qualitative Properties MANET routing protocols should be able to meet the above requirements as stated above as well as have certain desirable features. The Corson and Macker (Corson and Macker 1999), list of “desirable qualitative properties of MANET routing protocols” [6] covers some of the most important features as described below •

Distributed Operation. [6] Routing protocols should ideally be non-dependent on any central authority, since nodes in a MANET enter and leave freely at arbitrary times.

•

Loop-freedom. [6] Path determination from source to destination should be at most effortless and guaranteed route offers for packet forwarding without loops, is essential to avoid wastage of bandwidth, CPU and other scarce network resources.

•

Demand-based Operation. [6] Routing protocols should only react when there are changes in the network e.g. ideally they should only provide routes as and when needed instead of maintaining routes to destinations at all times. This operation will help conserve network resources such as bandwidth and energy, although at the cost of delays in discovering routes.

•

Proactive operation. [6] Is the opposite of demand-based operation. In some situations the demand-based delays in route discovery may not be ideal; hence proactive approach is often preferred, bearing in mind that bandwidth and other network resources need to be taken into consideration since this approach is resource intensive.

•

Security. [6] Wireless networks are prone to attacks due to their open air medium of communication. MANET routing protocols are open to attacks such as packet sniffing, packet header re-ordering, and transmission interception, to name but a few. Although these security issues are still an integral part of wired networks, but at least there is physical protection in wired networks, herein lays the difference between the wired and wireless environment. It goes without saying that wireless media are more difficult to protect since they are not seen physically. Security measures are needed and desired to prevent the disruption of routing activities. Techniques such as IPSec using transport or tunnel mode for protecting IP headers can be used to achieve the security requirements.

•

“Sleep” period operation. [6] Energy is needed for both signal transmission and reception. To conserve energy, MANET nodes may suspend these activities at intermittent periods. Routing protocols should be able to adapt to such situations without having too much effect on network operations.

•

Unidirectional link support. [6] Bi-directional links are always implied and seen as the de facto standard in terms of connection, in routing algorithms. But there are cases often in wireless networks, where links could be uni-directional especially where transmission capabilities differ between source and destination. Some routing algorithms cannot perform well, using uni-directional links. Sometimes the only connection available in a network, could be two uni-directional links but in opposite directions. Routing protocols should be able to utilize these connections.

MSc. Dissertation

17

XXXXXXXXX

3.3.2 Ad Hoc On Demand Distance Vector Protocol – AODV [32] The Ad Hoc On Demand Distance Vector routing protocol (AODV) [32] is a reactive protocol based on the distance vector algorithm, and allows mobile nodes that wish to communicate and form an ad hoc network, do so in a timely, self configuring manner. It offers routes quickly and on demand and does not require mobile nodes to maintain routes to destinations that are not in the active status. This protocol allows mobile nodes to respond quickly to changes in the network such as link outages. Although AODV [32] is a distance vector protocol which is based on the Bellman Ford algorithm, it ensures a loop-free routing environment and avoids the counting to infinity problem associated with this algorithm.

3.3.2.1 Mode of Operation

3.3.2.1.1 Message types AODV has three message types namely Route Requests (RREQs), Route Replies (RREPs) and Route Errors (RRERs). These messages use UDP port 654, as the transport layer protocol. Although RREQ messages are broadcasted, the extent to which the broadcast is heard depends on the TTL (Time To Live) value in the IP header.

3.3.2.1.2 Route Discovery and Requests Route Request messages are broadcasted when a new route is needed to a destination and there is no current known route entry for that destination. A route is established when the destination receives a RREQ message or an intermediate node, that has a more current entry to the said destination and this can only be acceptable if the sequence number associated with the route entry for that destination, is at least as great as the one in the RREQ message. All nodes that receive the RREQ [32] message as it is broadcasted, keep a copy and set up a reverse path back to the originator of the request message. This path is used to send back a reply i.e. RREP [32] message, which is a unicast type message, from the destination or any intermediate node capable of providing a reply.

MSc. Dissertation

18

XXXXXXXXX

Source

S

E F

B

C

M

L

J A

G H

Destination

D K I

N

Source S wants to send packets to destination D Figure 9: AODV Route Discovery [39]

Every RREQ message has an identifier, i.e. RREQ ID, which is unique to each message. The ID value is incremented by a node each time a new RREQ is generated. A node maintains only one RREQ ID, and sets the hop count field to zero. An originating node usually uses the FIFO (First In First Out) technique to buffer its own IP address and RREQ ID, before broadcasting the request message. This is to avoid processing the packet again, when received from a neighbouring node.

Reverse path RREQ S

E FF

B

M M

C

LL

JJ AA

GG HH

D

Destination

KK II

N

Represents a node that has received RREQ for D from S Figure 10: AODV Route Discovery – RREQ [39]

MSc. Dissertation

19

XXXXXXXXX

There is a limit to the amount of RREQ messages a node can generate per second. After each RREQ broadcast, a node waits for a RREP message and if not received within the specified time limit (in milliseconds), then the node may retry again. The maximum number of RREQ retries is equal to the maximum TTL value. The TTL value determines the range at which a RREQ message broadcast is heard and is set in the IP header for each retry. If no RREP message is received after the maximum retry limit, packets destined for that destination are dropped from the buffer and a destination unreachable message will be delivered. Originating nodes use what is known as the “expanding ring search” [32] technique, to avoid unnecessary propagation of RREQ in the network. In this technique, the TTL value in the RREQ packet IP header is initially set to a start value, and the maximum period for the reception of a RREP is also set i.e. timeout period. If no corresponding RREP message is received and the RREQ message times out, the node will re-broadcast the RREQ message and increment the TTL value. This operation continues until the TTL value reaches the threshold. When nodes receive RREQ messages, they check the source IP address and RREQ ID to ensure they have not been processed previously, if true then the messages are discarded, otherwise the hop count value is increased by one to account for the new hop through the node. Nodes other than the intended destination node that generate RREP messages in reply to RREQ messages, due to the fact that they possess an up to date route, must also in addition send back what is known as a gratuitous RREP message which is unicast to the original intended destination. This is done by setting the ‘G’ flag in the message. Originating nodes can also set the ‘G’ flag in RREQ messages, to ensure that intended destinations are aware of a route back to sources if and when needed.

3.3.2.1.3 Sequence Number Maintenance Every node maintains a route table entry containing IP addresses of known destinations; the latest sequence number of the destinations is also included in the entry. This must be updated whenever a node receives new information about a sequence number related to a given destination, either from a RREQ, RREP or RERR message. Sequence numbers are updated in any of the following circumstances •

Immediately before a RREQ message is sent, the source must increase its own sequence number. This is to avoid confusion as per reverse routes already known towards the source.[32]

•

Immediately before a destination sends a RREP message in response to a RREQ, it must update its own sequence number to the maximum of its current sequence number and the destination sequence number in the received RREQ packet.[32]

Before updating sequence numbers, a comparison must be carried out between the stored sequence number and the received one from any AODV message i.e. RREQ, RREP and RRER. This is to ensure that the information about a destination is current and not stale. The current sequence number is subtracted from the incoming received one and if the result is less than zero, then the information for the destination as reported by the message must be discarded since it is old compared to the information currently stored or known by the node. This process described is better known as sequence rollover.

MSc. Dissertation

20

XXXXXXXXX

3.3.2.1.4 Route Replies A route reply message is generated in response to a corresponding route request message. A node will reply to a RREQ message in the below circumstances: • •

If the node is the intended destination.[32] OR A node that has a more current route to the intended destination, after comparing the sequence number of the route table entry for the destination, with the sequence number in the RREQ message, and the route table sequence number is found to be greater.[32]

Before sending out a RREP message, a node will copy the source IP address and sequence number from the RREQ message into their corresponding fields in the RREP message. If it is the intended destination that generates a RREP in reply to a RREQ message, then it must increment its own sequence number by one, if it is equal in value to the one in the RREQ message, otherwise it will generate the RREP message. If it is an intermediate node that generates a reply, the RREP message is processed differently. The intermediate node copies the sequence number as it is known to it, of the original intended destination, into the destination sequence number field in the RREP message, updates the forward route entry and also its route table entry for the source, of the RREQ message. A forward path is set up by each node that receives a RREP message. This path points towards the destination or originator of the RREP message.

Forward path S

E F

B

C

M

L

J A

G H

D K I

RREP

N

Figure 11: AODV Route Discovery – RREP [39]

MSc. Dissertation

21

XXXXXXXXX

A precursor list is also maintained by every node, which contains the IP address of each neighbour that will likely use the node in question as a next hop towards any given destination. The information in this list is gotten when a RREP message is generated. A RREP message can only be sent to a node in the precursor list. A reverse path is set up by each node that receives a RREQ message, pointing back towards the source of the RREQ message. If a node sends or forwards a RREP message over a link it feels may be unidirectional or be unreliable, the node should appropriately set the ‘A’ flag which will require that the recipient of the RREP message sends back an acknowledgment i.e. RREP-ACK. This acknowledgment packet does not necessarily contain any important information about which RREP message it is acknowledging. The information contained is just enough to provide assurance to the source of the RREP message, about the current status of the link; this assurance is not permanent.

3.3.2.1.5 Route Maintenance When links are broken on a route that is active, Route Error (RERR) messages are sent out to inform nodes. These messages indicate destinations that are no longer reachable by way of the broken link, and are sent via nodes listed in the precursor list. A RERR message may be broadcasted or unicasted, depending on the number of nodes in the precursor list, and there is a limit to the amount of RERR messages a node can generate per second. Below are the conditions under which a RERR message is appropriate: •

If a link breakage is detected in an active route during transmission and an attempted repair did not work. [32] • A packet is received by a node for a destination, that it has no known active route for. A node receives a RERR message for one or more active routes, from a neighbour. [32]

MSc. Dissertation

22

XXXXXXXXX

Upstream Node of break F will broadcast RERR

S

E F

B

C

M

L

J A

G H

D K I

N RERR New route after rediscovery

Figure 12: AODV Route Maintenance – RERR [39]

3.3.2.1.6 Maintaining Connectivity Nodes use Hello messages to offer connectivity and they are broadcasted locally. Only nodes that are part of an active route may use Hello messages. A node will check at time intervals usually in milliseconds, to see if it has sent a broadcast and if not, it may then broadcast a RREP with the TTL value set to 1, which implies a Hello message. A node may listen for packets from its neighbours to ensure that there is connection. If it has received a hello message within what is known as the delete period and does not receive any packets whether hello or otherwise for more than the specified hello period, then the link is assumed to be unavailable.

MSc. Dissertation

23

XXXXXXXXX

3.3.3 Dynamic Source Routing Protocol – DSR [33] The Dynamic Source Routing protocol (DSR) is a simple, efficient and reliable protocol that allows networks to operate independently without the availability of any previous network infrastructure. DSR operates in 2 ways which help in discovering and maintaining source routes, namely Route discovery and Route maintenance, both are on-demand driven, hence DSR does not need periodic dissemination of control messages e.g. Hello messages for detecting connectivity with neighbours or link status advertisement messages, or even periodic routing table exchanges. The benefit of the above is that although DSR has a considerable amount of routing overhead, it still performs well when nodes are stationary as well as mobile because it only keeps track of active routes and does not react to network changes involving inactive routes. DSR supports multiple routes to destinations because nodes use a caching mechanism to maintain multiple routes. These routes are learnt either during a route discovery or from other control packets, they overhear. Multiple route support implies that there is instant reaction to changes and if one route fails, a node can quickly pick another from its cache. Caching also reduces the added overhead of performing a new route discovery every time a route fails. The source is responsible for determining the route a packet will take to its intended destination. This allows for loop free routing since the source can generate and avoid duplicates in the route selected.

3.3.3.1 Mode of Operation

3.3.3.1.1 Route Discovery The source determines the path a packet will take to its destination by placing what is known as the “source route” [33] in the header of the packet. The source route contains all intermediate nodes between the source and destination, a packet will traverse. The source route is gotten from the route cache of the sender, if one is available for the intended destination; otherwise a route discovery is initiated by the sender to find one to the destination. A route discovery request is a broadcast message and all nodes that are within the wireless transmission range of the originator, will receive this request. As illustrated below each route request is unique with an identification number determined by the originator. Each route request message also identifies the source and destination of the route discovery.

MSc. Dissertation

24

XXXXXXXXX

“A” Id=2 A

“A, B” Id=2 B

“A, B, C” Id=2 C

D

“A, B, C, D” Id=2 E

Figure 13: DSR Basic Route Discovery [33]

As illustrated above, at the beginning of the route discovery, the route request message set up by the originator node A, contains an empty list. Each route request is made up of a record list. This list is initially empty, containing only the originator node. As the route request message is forwarded towards the destination, the record list gets populated with the address of each intermediate node through which the message is forwarded. When a node receives a route request and it is the intended destination, it sends back a route reply to the originator. The route reply message also includes the route record accrued during the route request. On reception of the route reply, the originator caches the accrued route record in its route cache to be used as future reference in sending packets to that destination. On the other hand, if the node receiving the route request notices it has previously received the same message with same ID and destination credentials, from the originator, or its own address is listed in the route record in the route request, the node will discard the request. Otherwise it will add its address to the route record of the route request and re-broadcast the message onwards. In sending back a route reply to a route request message, a node will first consult its route cache to determine if there is a route back to the originator. If true then, it is used to deliver the reply packet. Otherwise the node will initiate a route discovery for the originator node. To avoid continuous repetition of the route discovery, the node must carry the route reply on the back of its route request, en route back to the originator. During the route discovery process by a source node, it maintains a buffer called the send buffer where it keeps a copy of all packets that currently do not have source routes to their intended destinations. Each packet placed in the buffer is time stamped and flushed out when the timeout period is reached. But while still in the buffer, it is the responsibility of the source node to periodically initiate a route discovery for each packet’s destination but there is a limit to the rate at which route discoveries for a particular address can be made since the destination may be unreachable which may be due to node mobility or limited coverage range.

MSc. Dissertation

25

XXXXXXXXX

3.3.3.1.2 Route Maintenance Every time a node originates, forwards or transmits a packet, it is in charge of ensuring that the link over which the packet will traverse to the next hop is reliable and that data can be carried on that link. For example as illustrated below:

A

B

?

C

D

E

Figure 14: DSR Basic Route Maintenance [33]

A is responsible for the link between itself and B; B is responsible for the link between itself and C and so on. Acknowledgements can be used to provide assurance that a given link is reliable. The acknowledgement could either be part and parcel of the MAC protocol in use, or nodes operate in some form of promiscuous state where they listen and overhear transmissions. For example, if B transmits or forwards a packet to C, to confirm that C received the packet, B will attempt to overhear C forwarding the packet on, to D. This operation is known as “passive acknowledgement” [33].

3.3.3.2 Additional Features

3.3.3.2.1 Caching Overhead Routing Information Ideally a node should fill up its cache with useful routing information gathered from packets forwarded or overheard but this also depends on the situation and characteristics of the link and the MAC protocol in use. There are 3 cases where the above applies. The first case is where the link is unidirectional only and the MAC protocol is only able to transmit unicast packets over unidirectional links. In this case a node should cache the source route carried in the packet, the accrued route record in the route request or the source route in a route reply provided the node is in the “forward direction”. In addition it is irrelevant if the packet was initially addressed to the node broadcaster or overheard, but the “reverse direction” in the packet header should not be cached. Using the example below to illustrate:

A

B

C

D

E

Figure 15: Caching overhead routing information [33]

MSc. Dissertation

26

XXXXXXXXX

Let’s say A is communicating with E and using the source route it has initiated. As the packet is being forwarded say at node C, towards E, C should update its cache with the information it gets from the header of the packet counting from itself to D and from D to E, but should not cache the reverse information in the header i.e. links from itself back to B and then back to A because the links might be unidirectional. The second case is when links may be unidirectional but not permanently so. In this case links should be cached both in the forward and reverse directions. The third case is where the MAC protocol can only transmit unicast packets over unidirectional links. Links in both directions should be cached with an exception where the packet carries a route reply as well which implies that travelled links only, should be cached and non travelled links should not.

3.3.4 Optimized Link State Routing Protocol [34] The optimized link state routing protocol is a proactive protocol and is called a table driven protocol because it involves nodes exchanging routing information consistently. Not all nodes in an OLSR network forward traffic, only those selected by their one-hop neighbours to act as “Multi-point relays” (MPR) [34]. Since only designated nodes flood network traffic, it reduces the amount of network overhead. The MPR nodes also provide the shortest path routes by making available periodic link status changes to nodes that have selected them. MPR nodes are selected by their one-hop neighbours on the basis of bi-directional links. This automatically implies that routes through MPRs’ will not have the problems associated with unidirectional links such as non acknowledgement of packets. The use of MPRs’ allows OLSR to scale well in large, mobile and densely populated networks. Each node in an OLSR network routes or forwards packets based on the local information known to it.

MSc. Dissertation

27

XXXXXXXXX

Figure 16: OLSR Network showing MPR and non MPR nodes [7]

OLSR is also applicable in networks where traffic is erratic and irregular and where communication between a set of nodes is not permanent, but changes constantly.

3.3.4.1 Mode of Operation OLSR is based on the link state algorithm and because of its proactive nature routes to destinations are readily available. Its use of selected nodes as MPRs’ to forward and flood control messages to other nodes in the network reduces the overhead associated with this operation. OLSR messages do not require to be delivered in order since the protocol uses sequence numbers for messages and is incremented for each new message. The sequence numbers are used to identify current messages. The OLSR protocol can also be extended to include support for important protocol characteristics such as sleep mode operation and multicast routing. These additions can be implemented in a way so as not to interfere with any backward compatibility issues of earlier versions of the protocol.

MSc. Dissertation

28

XXXXXXXXX

3.3.4.1.1 Multi Point Relays Nodes in an OLSR network appoint specific nodes known as MPRs’ to forward traffic on their behalf. The concept of MPRs’ is that they reduce the need for data re-transmission in a network since only designated nodes are responsible for this operation. The selected MPR nodes are usually selected based on a symmetric 1-hop distance. The MPR nodes are responsible for the set of nodes that selected them as MPRs’, and keep information pertaining to these nodes. They obtain node specific information from periodic Hello messages. Control messages or broadcasts re-transmitted by MPRs’ on behalf of neighbour nodes, can be received by the set of nodes that are symmetric only, and 2-hops away.

3.3.5 Topology Dissemination Based On Reverse-Path Forwarding (TBRPF) [35] Topology dissemination based on reverse path forwarding is a proactive protocol based on the conventional link state algorithm, using the hop-by-hop shortest path to provide routes to destinations. TBRPF nodes build a tree that provides shortest path to destinations that are reachable. The shortest path tree is built using only a part of the information available in a node’s routing table by applying the Djikstra algorithm. Nodes only exchange this partial tree which helps to reduce overhead. Neighbouring nodes keep each other informed by sending out their partial source tree. They do so either differentially and periodically. Neighbours are discovered with the help of Hello messages using the differential method. These Hello messages only report recent changes in neighbour status making them more compact compared to other link state protocols such as OSPF.

3.3.5.1 Mode of Operation TBRPF is made up of 2 operations namely neighbour discovery module and routing module.

3.3.5.1.1 Neighbour Discovery TBRPF neighbour discovery protocol also known as TND, discovers neighbours using “differential” [35] hello messages and these messages mention only recent changes in neighbour link status. Due to this, the hello messages are more compact, therefore can be sent out regularly allowing for rapid detection to changes in network topology. TND is only involved in neighbour discovery that are 1-hop away. Neighbours that are 2-hops away are discovered using the routing module hence TND is said to work independently of the routing module therefore can be utilized by other routing protocols. In fact TBRPF can replace TND with any other neighbour discovery protocol. TND operates on a per interface basis, therefore for each interface on a node there exist a neighbour table which implies then that a hello message from an interface will only have information about neighbours overheard on that interface. Since messages can be received from multiple interfaces of a neighbour node, hello messages also include the interface address.

MSc. Dissertation

29

XXXXXXXXX

3.3.5.1.2 Routing Module TBRPF nodes build a tree that provides shortest paths to destinations that are reachable. The tree also known as the source tree is updated using only part of the topology information in a node’s routing table, by applying the Djikstra algorithm. Nodes only exchange this partial source tree with neighbours, which reduces network overhead. The partial source tree also known as the sub-tree is reported by nodes, to their neighbours periodically while changes to the sub-tree are reported more regularly using differential updates. On the other hand, periodic updates are meant for disseminating information to new neighbours about reported sub-trees, ensuring they are aware even though they may more than likely not receive all updates. Differential updates ensure that network topology updates are quickly spread out to the nodes concerned. These topology updates when received do not get propagated but could amount to modifications or alterations in the reported sub-tree, which is announced in the subsequent periodic or differential update. Topology updates are as much as possible made a part of hello messages to help in the reduction of routing control message overheads.

3.4 Routing Protocol Comparison So far the protocols have been analyzed theoretically. The table below summarizes and compares the results from the analysis and shows some of the properties the protocols have or do not have, using some of the more desirable qualitative properties as proposed by Corson and Macker [6]. Other comparison attributes included are Quality of Service (QoS) support, periodic broadcasts, multicast support, and reliable and sequenced data delivery.

MSc. Dissertation

30

XXXXXXXXX

Table 2: Routing protocol comparison

Properties

AODV

DSR

OLSR

TBRPF

Loop-freedom Demand-based operation Proactive operation Distributed operation Security

Yes Yes

Yes Yes

Yes No

Yes No

No

No

Yes

Yes

Yes

Yes

Yes

Yes

No

No

No

“Sleep” period operation Unidirectional link support QoS support Periodic broadcast Sequenced data delivery

No

No

Yes

Yes (Packets can be authenticated and encapsulated using the IP AH and ESP headers. TBRPF can be extended to use the IETF Securing Neighbour Discovery i.e. SEND mechanism. No

Yes (using RREP-ACK) No Yes

Yes

Yes

Yes

No No

No Yes

No Yes

Yes

No

Multicast support

Yes

No

No No (Although uses sequence numbers which is incremented for each new message) Yes No

MSc. Dissertation

31

XXXXXXXXX

4 Simulation Overview

S

imulation plays an important role in understanding and evaluating the performances of

routing protocols on networks, which is why it is quite important that simulation tools models, default parameters, scenarios and assumptions are carefully described and understood. Simulations are carried out with usually a problem statement or statements. A model or several models is set up, that reflects the problem statement, and experiments are then carried out to solve the problem. The OPNET documentation on modelling and simulation basics, (OPNET Modelling Concepts Reference Manual 2005) presents a general workflow process that encompasses the techniques that can be adapted towards carrying out a successful modelling and simulation study.

Figure 17: The modeling process [36]

MSc. Dissertation

32

XXXXXXXXX

4.1 Practices and Techniques Computer simulations are the most common route taken to analyse wireless ad hoc networks since they provide a flexible, repeatable, scalable environment. Much of the knowledge gained today about ad hoc routing protocols, has been through the work of extensive simulation. In other to carry out a successful simulation there are some essential steps and techniques that should be followed. Ensuring that simulation models and their associated results are correct is very important especially to individuals or groups who may be making use of the information from studies carried out. The above can be achieved through the simulation techniques of model validation, verification and testing. The definition of model validation, according to Sargent (Sargent 2003) “is usually defined to mean substantiation that a computerized model within its domain of applicability possesses a satisfactory range of accuracy consistent with the intended application of the model” [37]. Balci’s (Balci 1995) explanation of model validation involves “building the right model” [38]. Model verification involves ensuring that a model performs as it should with as much accuracy as possible. Verification involves “building the model right” [38] (Balci 1995). Model testing involves showing that there are possibilities of errors in a model. During testing, a model is fed with test data in other to see if it functions as it should. Models should be set up depending on what purpose they are trying to achieve, so that the validation can be based on the purpose. A model may be set up to answer several questions; hence its validity should be able to answer each of the questions. A model may be valid for the experimental purpose it has been set up for, therefore will be considered invalid and not apply to any other experimental condition. Model validity is also based on the accuracy of the results obtained if they are within the acceptable range of the model’s purpose. However the fact that a model is accurate in several experimental conditions, does not guarantee that it is applicable in all conditions. Determining the absolute validity of a model as regards its intended purpose is often a costly and time consuming operation. The best that can be achieved is to carry out as much rigorous testing and evaluation up to the point where some confidence in the model’s intended purpose is reached. As illustrated by Sargent below (Sargent 2003) [37], validation costs are considerably higher in cases where high confidence in the model is a requirement. During the development of a model, determining what and what not to include in a bid to represent the real system as much as possible is an important issue. One method would be to include all details as humanly known to ensure important bits are not left out. As good as this sounds it is quite time consuming as per model building, and also in terms of simulation time runs. Deciding on what behavioural aspects to represent in a model is quite a difficult task since major aspects of the system, which accounts for the system behaviour may not be known in advance. Hence assumptions or theories should be made to answer relevant questions, and further down the study, can be changed and more sophisticated models built to highlight the different areas of the system. This approach helps in broadening knowledge as to the important aspects of a system with respect to a simulation study objectives.

MSc. Dissertation

33

XXXXXXXXX

Figure 18: Validation cost against model confidence [37]

An important simulation practice as pointed out by Perrone et al (Perrone 2003) [8] is the use of warm up models to avoid the initial transient problem. The initial transient problem usually rears its head in the simulation of wireless networks, which affects the outcome of results if not taken into account.

4.2 OPNET Modeller OPNET modeller is the simulation tool chosen for this project, since the full featured version is available for free at the University. OPNET is a network simulation tool that features an all inclusive development, “component-oriented” [36] environment for modelling communication networks and distributed systems. Performance of modelled systems can be analyzed using discrete event simulations. The OPNET environment comes with tools that aid the stages of a simulation study i.e. model design, simulation, data collection, and data analysis.

4.2.1 OPNET Architecture Apart from providing features to support general network modelling, OPNET also comes with extended features for the support of specific types of network situations. The OPNET software package contains tools that are each targeted at the phases of the modelling process. The OPNET architecture supports the simulation project cycle as illustrated below. The tools fall into the 3 broad stages of network modelling which are specification, data collection and simulation and analysis.

MSc. Dissertation

34

XXXXXXXXX

Figure 19: Simulation Project Cycle [36]

OPNET simulations support code in C and C++ and Proto-C, as well as the host operating system. Results from simulations are stored on the host computer file system either as vector, scalar or animation history, and can be displayed using the appropriate tool e.g. Analysis tool. Results depend on the type of statistic chosen, prior to running simulations; this could be global, local or both. The Discrete Event Simulation provides the most detailed results of a simulation and will be used as the analysis type for this project. Although it takes up much longer simulation run times, this is due to the fact that it performs an exhaustive analysis as regards explicit traffic, traffic between node pairs and link loads.

MSc. Dissertation

35

XXXXXXXXX

5 Simulation Models and Study 5.1 MANET Node Structure

T

he protocols to be simulated at this time are the AODV, DSR and OLSR. The structure of

a MANET node is as shown below:

Figure 20: MANET Node Structure [36]

The routing protocols operate at the IP layer with a root process called ip_dispatch, which in turn has a sub process called manet_mgr as shown in the figure above. The manet_mgr is a common interface to most MANET routing protocols, and produces the desired routing protocol child process as needed, depending on which protocol is configured on a node. Below the IP layer, is the ARP layer (Address Resolution Protocol) which maps known IP addresses to their corresponding unknown MAC addresses by performing network wide ARP broadcasts. A MANET node comes with a receiver and a transmitter represented in the above figure at the physical layer.

5.2 Methodology and Implementation The goal of this project is to measure the performance of the selected routing protocols and their ability to react to network topology changes and still carry out the purpose of delivering data packets successfully to their intended destinations.

MSc. Dissertation

36

XXXXXXXXX

To achieve the above, the basic methodology was to create a simulated network with 3 network scenarios, each depicting the 3 conditions under which the protocols are to be evaluated i.e. mobility, packet size (network load) and network size or node density. Each scenario was then duplicated thrice one for each protocol where the following parameters i.e. the speed of node mobility, packet size and node density were varied. Each scenario will be discussed in more detail in following sections. All network scenarios apart from the network size scenario for the protocol evaluation are based on a simulated 25 mobile and wireless nodes moving and forming an ad hoc network in a rectangular arena of 1500m x 1000m in dimension, for 900 seconds of simulated time. Broch et al (Broch 1998) [9] also used similar measurements in their study i.e. 1500m x 300m, and believe nodes will be forced to use longer routes in a rectangular space than a square space. The protocols performance was also evaluated in a more realistic scenario, the setup details and results can be found in section 5.5.5. To ensure fairness in the evaluation and comparison exercise, all protocols were given identical input variables and environmental conditions.

5.2.1 Physical and MAC Layer Model The IEEE 802.11 MAC standard is implemented at the link layer. The access scheme modelled at this layer is the Carrier sense multiple access and collision avoidance (CSMA/CD) Distributed coordination function (DCF) without RTS/CTS option. DCF reduces the probability of collisions by applying the technique of sensing the medium both virtually and physically. The maximum communication distance between 2 nodes is 300m which is in accordance with the IEEE 802.11 standard limits. Nodes operate at the ISM 2.4GHZ frequency band, with a transmit power of 0.03W (15dBm) which is the typical output from Wireless LAN devices. The reception threshold or receiver sensitivity of each node is set at -95dBm. Packets with reception power lower than the threshold will be treated as noise packets since the receivers cannot detect their signals. Packets are transmitted at 11Mbps, below is a table summarizing the physical and MAC layer model parameters.

Table 3: Physical and MAC layer parameters

Parameter Frequency Communication distance Transmit Power Receiver Sensitivity MAC Protocol Data rate

MSc. Dissertation

Value 2.4GHz 300m 0.03W (15dBm) -95dBm 802.11 DCF without RTS/CTS 11Mbps

37

XXXXXXXXX

5.2.2 Node Mobility Model As discussed earlier in this project, mobility is very important since it forms the basis of Ad hoc networks. Node movement are modelled using the Random Waypoint Model. Nodes using this model, select a random waypoint or destination within the simulated arena, travelling at a constant speed chosen from a uniform distribution range of values minimum to maximum. When a node reaches its destination, it pauses for a predefined time typically in seconds, and then chooses its next waypoint. This process repeats itself until the end of the simulation. Each node determines its path using a vector trajectory. Each node starts the simulation at a stationary position and then selects a random destination within the 1500m x 1000m area, moving at a uniformly distributed speed between minimum 5m/s and maximum 80m/. On reaching its destination a node pauses for the specified pause time, typically in seconds before choosing its next destination.

5.2.3 Traffic Model Traffic is generated using raw packet generation. Each MANET node is capable of generating raw traffic over IP and WLAN in the network. This can be done by editing the traffic generating attributes of a MANET node in the project editor. Raw packet generation comes under the “explicit traffic” type where better results are obtained since it models all protocol effects, which is the aim of this project. Source and destination pairs are spread and chosen randomly over the network. The packet inter-arrival time and packet size were 5 packets /second and 64 bytes (512 bits) respectively for all scenarios except the network load scenario where the packet size is varied.

5.3 Performance Metrics The following quantitative metrics were chosen to evaluate the 3 protocols during the simulations. They are: •

Throughput – this refers to the amount or ratio of data packets delivered to their destinations to those generated by the sources.

•

Average end to end delay – the amount of time in seconds it takes for a packet to get to its destination, and usually includes delays caused by buffering, retransmissions, and interface queues.

•

Packet delivery ratio – the fraction of data packets successfully received over the number of data packets generated. This metric measures the reliability of a protocol.

•

Routing overhead – the number of routing packets transmitted over the number of data packets delivered, and is a reflection of how efficient a routing protocol is.

MSc. Dissertation

38

XXXXXXXXX

5.4 Implementation Decisions All protocols have been implemented using the default parameters as described in their RFC’s and Internet drafts.

5.4.1 Summary of Routing Schemes AODV and DSR are known as on-demand routing protocols because routes are only discovered when needed. Both make use of a route discovery mechanism, but differ in the sense that DSR incurs additional overheads due to the use of source routing and caching features and does not maintain neighbour connectivity with the use of link update messages i.e. Hello messages. OLSR is a proactive, table driven protocol, and uses the concept of MPR (Multi Point Relay Nodes) to route traffic on behalf of other nodes. OLSR is termed proactive because routes to destinations are readily available in the routing tables of designated MPR nodes and hence does not have the additional overhead of performing a route discovery. Table 4: AODV Implementation Constants

Parameter Route Request Retries Route Request Rate Limit (pkts/sec) Active Route Timeout Hello Interval Allowed Hello Loss Network Diameter Node Traversal Time TTL start TTL Increment TTL Threshold

Value 5 10 3secs 1000ms(1sec) 2 35 0.04secs 1 2 7

A node will try a maximum of 5 times to rediscover a route, before broadcasting another route request. The rate at which a node generates route request packets is set at 10packets/second. Every routing table entry has an active route lifetime, and if a route is not used within the active route timeout period it is marked as invalid. If a node loses more than 2 hello packets, then it has to announce a link breakage.

MSc. Dissertation

39

XXXXXXXXX

Table 5: DSR Implementation Constants

Parameter Route Cache Expiry Send Buffer Timeout Request table Size Initial Interval between Route Discovery attempts(aka Initial Request Period) Maximum Buffer Size (packets) Maximum Number of attempts to confirm next hop reachability Maintenance Acknowledgement Timer

Value 300secs 30secs 64 nodes 500ms

50 2 0.5secs

Routes in the route cache expire after 300secs; packets in the send buffer expire after 30secs counting from when it was placed in the buffer initially.

Table 6: OLSR Implementation Constants

Parameter Willingness

Hello Interval Topology Control Interval Neighbour Hold Time Topology Hold Time Duplicate Message hold Time Maintenance Acknowledgement Timer

Value Willingness Default (value =3) 2secs 5secs 6secs 15secs 30secs 0.5secs

The willingness value for all nodes was set to the default with a value of 3. The willingness value can be set to any integer starting from 0 up to 7. The willingness feature indicates the extent to which a node is ready to forward traffic on behalf of other nodes. Willingness Never specifies a node not willing to forward traffic, while a node with the Willingness Always attribute set specifies a node that will always be picked to forward traffic. Willingness Never = 0 [34] Willingness Low = 1 [34] Willingness Default = 3 [34] Willingness High = 6 [34] Willingness Always = 7 [34]

MSc. Dissertation

40

XXXXXXXXX

5.5 Simulation Setup and Study This section describes how the simulations were carried out and the set up of the different scenarios and their associated parameters. All simulations run for a total of 900 seconds of simulated time, with nodes forming ad hoc networks in a rectangular arena of 1500m x 1000m. The decision to run all simulations for 900 seconds was due to CPU, Hard disk space and memory constraint when the number of simulations to be run is taken into consideration given that OPNET requires a lot of processing power. A total of 225 simulations were run, each with 3 random seed values to ensure accuracy and validation in results obtained. This amounts to 36 simulations for each scenario, breaking down to 9 simulations for each of the varied parameters, with 3 runs i.e. 3 random seeds for each protocol under study. 108 simulations with the same breakdown as above, was also carried out for the varied mobility against varied longer pause times, and an additional 9 runs for the realistic scenario, hence the grand total of 225. The first 10 seconds of each simulation run was discarded to account for the initial transient problem inherent in wireless networks. After 10 seconds of simulated time, a steady state is obtained. This decision was reached after observing the results. As shown in the graph below, it can be seen that the model attains a steady state after the first 10 seconds of the simulation. 95% confidence interval was set for each result obtained. A sample screenshot of how the confidence interval was set can be found in Appendix B. Simulation results were collected and collated using standard techniques and tools, and are available on the P (Project) drive, and also uploaded as supporting material with this report.

MSc. Dissertation

41

XXXXXXXXX

Effect of initial transient on results: Case study Mobility Scenario, AODV end to end delay 0.006

delay(secs)

0.005 0.004 0.003 0.002 0.001

882

819

756

693

630

567

504

441

378

315

252

189

126

63

0

0

Simulation time(secs) Delay at 5m/s

Delay at 10m/s

Delay at 15m/s

Delay at 20m/s

Delay at 50m/s

Delay at 80m/s

Figure 21: Effects of initial transient on results

5.5.1 Mobility Scenario – Simulation Environment Setup To evaluate the impact of mobility on the simulated protocols, the speed of each node was varied using 6 different values of 5, 10, 15 and 20, 50 and 80m/s. An increase in the speed value effectively increases node mobility. The pause time for each node was kept at 1second, and the packet Inter-arrival time and packet size were 5pkts/sec and 512 bits respectively, the packet size was kept small since it is the mobility factor that is under investigation. The interarrival time is exponential i.e. packet arrivals are a Poisson process at a rate of 5 packets/second. All nodes started and stopped transmitting at the same time. An investigation to see the effect of longer pause times on the performance of the protocols was also carried out. Longer pause times of 10, 50 and 100 seconds were varied for each mobility factor. Results from the investigation are discussed at the end of this section. Screenshots of the scenario model can be found in Appendix B. The simulation parameters used in this scenario are shown in the table below:

MSc. Dissertation

42

XXXXXXXXX

Table 7: Mobility Scenario Parameters

Parameter No of Nodes Pause Time Packet rate Packet Size No of Nodes generating traffic Bandwidth Speed(m/s)

MSc. Dissertation

Value 25 1sec 5pkts/sec 512bits 25 11Mbps 5,10,15,20,50,80m/s

43

XXXXXXXXX

5.5.1.1 Results Analysis and Summary

End to end delay with varied mobility

Throughput with varied mobility 500000

0.0006 0.0005

400000 350000

delay(sec)

Throughput(bits/sec)

450000

300000 250000 200000 150000 100000

0.0004 0.0003 0.0002 0.0001

50000

0

0 5

10

15

20

50

80

5

10

mobility(m/s) AODV

DSR

20

50

80

moblity(m/s) OLSR

AODV

DSR

OLSR

Routing Overhead with varied mobility

Packet delivery ratio with varied mobility 1.002

0.3

1

0.25

routing overhead

packet delivery ratio(%)

15

0.998 0.996 0.994 0.992 0.99

0.2 0.15 0.1 0.05

0.988

0

0.986 5

10

15

20

50

5

80

DSR

15

20

50

80

moblity(m/s)

mobility(m/s) AODV

10

AODV

OLSR

DSR

OLSR

Figure 22: Mobility scenario simulation results

As shown in the graphs above each protocol maintains an average throughput range despite the increasing mobility. OLSR is the clear winner, as it has the highest throughput average which is due to the fact that it is a proactive table driven protocol and does not have the extra overhead involved in route discovery, since routing information is readily available. DSR has the lowest average throughput at 0.1 Mbps when compared to its reactive counterpart, AODV at 0.3Mbps. Both AODV and OLSR use Hello messages to maintain links and determine neighbour

MSc. Dissertation

44

XXXXXXXXX

connectivity, hence their impressive results, DSR has no such mechanism, which implies additional overhead in finding routes. OLSR and AODV have the lowest average end to end delay of 3.6 milliseconds and 3 milliseconds respectively, when compared to DSR, which is as a result of OLSR and AODV using Hello messages to determine link outages. AODV has the advantage over DSR with the use of Hello messages to find short, optimal and faster routes. AODV and OLSR maintain a 100% packet delivery rate average, despite the increasing mobility. DSR comes behind with an average packet delivery rate of 99%. Again this is as a result of AODV and OLSR using Hello messages to maintain neighbour connectivity during the routing process. DSR exhibits the highest routing overhead as expected, due to its source routing mechanism, where every packet header carries the entire source route which includes all intermediate nodes, en route to the final destination. OLSR has a slightly higher overhead due to its use of both Hello messages and Topology control messages, despite the 1 second Hello interval advantage over AODV. Clearly AODV and OLSR tend to perform better in environments where there is high degree of mobility, than DSR. Below are the graphs showing the effects of end to end delay on the maximum achievable throughput for the protocols, for each mobility factor. As expected, in the case of AODV and OLSR, the lower the delay, the higher the throughput and vice versa. With DSR on the other hand, a decrease in throughput leads to a decrease in delay, which is expected due to its source routing mechanism.

MSc. Dissertation

45

XXXXXXXXX

Effect of end to end delay on DSR throughput based on varied mobility scenario

Effect of end to end delay on AODV throughput based on varied mobility scenario 0.000318 0.000316

delay(secs)

0.000312 0.00031

Delay(secs)

0.000308 0.000306 0.000304 0.000302

Delay(secs)

299569 299776 299705 299336 297415 300023

101824 102219 102219 102165 102176 101720

Average throughput based on varied mobility(bits/sec)

Average throughput based on varied mobility(bits/sec)

Effect of end to end delay on OLSR throughput based on varied mobility scenario 0.000368 0.000367 0.000366

delay(secs)

delay(secs)

0.000314

0.0005645 0.000564 0.0005635 0.000563 0.0005625 0.000562 0.0005615 0.000561 0.0005605 0.00056 0.0005595

0.000365 0.000364

Delay(secs)

0.000363 0.000362 0.000361 0.00036 444053 443402 443402 443319 443315 443551

Average throughput based on varied mobility(bits/sec)

Figure 23: Effect of end to end delay on throughput - Mobility scenario simulation results

MSc. Dissertation

46

XXXXXXXXX

5.5.2 Offered Load Scenario – Simulation Environment Setup In this scenario, the packet size in bits was varied for each node participating in the network. Packet sizes of 512, 1024, 2048, 4096 and 8192 bits were used, while the speed, packet interarrival time and pause time were at 5m/s, 5packets/second and 1 second respectively. All nodes started and stopped transmitting at the same time. Screenshots of the scenario model can be found in Appendix B. The simulation parameters used in this scenario are shown in the table below: Table 8: Offered Load Scenario Parameters

Parameter No of Nodes Pause Time Packet rate Packet Size(bits) No of Nodes generating traffic Bandwidth Speed(m/s)

MSc. Dissertation

Value 25 1sec 5pkts/sec 512,1024,2048,4096,8192bits 25 11Mbps 5m/s

47

XXXXXXXXX

5.5.2.1 Results Analysis and Summary

End to end delay with varied packet size

Throughput with varied packet size 0.0016

1400000

0.0014

1200000

0.0012 delay(secs)

throughput(bits/sec)

1600000

1000000 800000 600000

0.001 0.0008 0.0006

400000

0.0004

200000

0.0002

0

0

512

1024

2048

4096

8192

512

1024

packet size(bits) AODV

DSR

4096

8192

packet size(bits)

OLSR

AODV

DSR

OLSR

Routing overhead with varied packet size

Packet delivery ratio with varied packet size 0.3 routing overhead

1.005 packet delivery ratio(% )

2048

1

0.995 0.99

0.985 512

1024

2048

4096

0.25 0.2 0.15 0.1 0.05

8192

512

packet size(bits) AODV

DSR

0 1024

2048

4096

packet size(bits)

OLSR

AODV

DSR

Figure 24: Offered load scenario simulation results

All protocols perform well as can be seen from the graph there is a steady increase in throughput as packet size increases, due to low mobility, and hence less time spent in re-establishing links. DSR still trails behind with the lowest average throughput, when compared to OLSR and AODV. DSR still has the highest average delay when compared to OLSR and AODV, and this is due to the fact that DSR queues packets that have no known routes yet, while it attempts to route discovery, hence the increased delay. The increase in end to end delay is expected since an

MSc. Dissertation

8192

48

XXXXXXXXX

OLSR

increase in packet size will imply for the on demand protocols, an increase in discovering routes for new packets with no known routes, as well as time spent in processing arriving packets. AODV and OLSR yet again outperform DSR with 100% packet delivery rate even with the 10% increase in the offered network load. As seen from the graph above routing overhead reduces as packet size increases. AODV and OLSR once again exhibit similar behaviour, both having smaller routing overhead compared to DSR. It is interesting to see how the overhead for all protocols converge to an average of approximately 0.19, at the highest offered load. This is due to the low mobility factor hence optimal routes are discovered faster. This average corresponds to the average routing overhead of the 3 protocols at 5m/s of the mobility scenario. It can be seen that routing overhead is lowest at low mobility rates because more routes are discovered, since there would be less link outages due to rapid movement. As shown in the graphs below, the higher the throughput, the higher the end to end delays, for all protocols. This is expected as packet size is increased gradually.

MSc. Dissertation

49

XXXXXXXXX

Effect of throughput on DSR end to end delay based on varied offered load scenario 0.0016

0.0007

0.0014

0.0006

0.0012

0.0005 0.0004

Delay(secs)

0.0003

d e l a y (s e c s )

0.0008

0.001 Delay(secs)

0.0008 0.0006

0.0002

0.0004

0.0001

0.0002

0

0

299569.3 362901.7 501006.5 743530.8 1249183

101824 164832 291314 538426 1052942

Average throughput based on varied offered load(bits/sec)

Average throughput based on varied offered load(bits/sec)

Effect of throughput on OLSR end to end delay based on varied offered load scenario 0.001 0.0008 delay(secs)

d e la y (s e c s )

Effect of throughput on AODV end to end delay based on varied offered load scenario

0.0006 Delay(secs) 0.0004 0.0002 0 444052.9 507898.9 632717.8 632717.8 1401419 Average throughput based on varied offered load(bits/sec)

Figure 25: Effect of end to end delay on throughput – Offered load scenario simulation results

MSc. Dissertation

50

XXXXXXXXX

5.5.3 Network Node Density Scenario – Simulation Environment Setup The node density was varied in this scenario starting with a network containing 25 nodes and was then increased to 30, 40 and finally 50 nodes. The aim of this scenario is to observe protocol performance as node density is increased gradually. Screenshots of the scenario model can be found in Appendix B. Table 9: Network Node Density Scenario Parameters

Parameter No of Nodes Pause Time Packet rate Packet Size No of Nodes generating traffic Bandwidth Speed(m/s)

MSc. Dissertation

Value 25,30,40,50 1sec 5pkts/sec 512bits 25 11Mbps 5m/s

51

XXXXXXXXX

5.5.3.1 Results Analysis and Summary

End to end delay with varied node density

Average throughput w ith varied node density

0.0016 0.0014

2500000

0.0012

delay(secs)

average throughpput(bps)

3000000

2000000 1500000 1000000

0.001 0.0008 0.0006 0.0004

500000

0.0002

0

0

25

30

40

25

50

DSR

40

50

network node density

netw ork node density AODV

30

OLSR

AODV

Packet delivery ratio with varied node density

DSR

OLSR

Routing overhead with varied node density 0.35 routing overhead

packet delivery ratio(%)

0.4 1.002 1 0.998 0.996 0.994 0.992 0.99 0.988 0.986

0.3 0.25 0.2 0.15 0.1 0.05 0

25

30

40

50

25

network node density AODV

DSR

30

40

50

netw ork node density

OLSR

AODV

DSR

OLSR

Figure 26: Network node density scenario simulation results As expected, DSR has the lowest average throughput when compared to AODV and OLSR and this is due to its lack of sensing neighbour connectivity despite the increase in the number of nodes in the network. AODV and OLSR on the other hand both have dramatic increase in throughput as node density increases. This is expected since both make use of the Hello message mechanism, therefore as the number of nodes increases, more nodes are available to offer routes and route packets to their destination, hence route discovery time is reduced dramatically, in the case of AODV. The routing overhead for AODV had a dramatic increase and this is attributed to the fact routing packets are sent 10 per second, hence as the number of nodes increases so does the number of routing packets and hence the increase in routing overhead. The number of OLSR

MSc. Dissertation

52

XXXXXXXXX

MPR designated nodes increases slightly as node density increases, therefore more nodes are willing to forward traffic on behalf of other nodes in the OLSR network. On the other hand the more the number of active nodes in the network the more traffic generated and hence high levels of routing overhead. As seen from the graph while DSR maintains an average overhead all through, OLSR has a dramatic increase in routing overhead due to the increase in exchange of Topology Control messages as well as Hello messages. It was discovered that on average, the number of MPR nodes in both the mobility and offered load scenario where node density was at 25, was 1; this number increased to an average of 3, in the node density scenario and was evident as the node count was experimentally increased to 35 to see the effect, as shown in the graph below. Obviously there would be an increase in routing overhead for OLSR as shown in the graph above, since the number of MPR nodes is not increasing at the rate of node density, and moreover only MPR nodes are designated to forward control traffic on behalf of other nodes.

MPR count against Node density

MPR count against Node density: Case study 35 nodes

3 3.5 3

2 MPR count

1.5 1 0.5

M PR coun t

MPR coun t

2.5

2.5 2 MPR count 1.5 1 0.5

0

0 25

30

40

25

50

30

35

40

50

Node density

Node density

Figure 27: MPR count against node density

Below are the graphs of end to end delay against throughput, and as expected all protocols exhibit similar behaviour, with an increase in delay as throughput increases. This is due to the increasing load on the network due to the number of nodes transmitting.

MSc. Dissertation

53

XXXXXXXXX

Effect of throughput on DSR end to end delay based on varied offered Network node density scenario

Effect of throughput on AODV end to end delay based on varied offered Network node density scenario 0.0016 0.0014

d elay(secs)

0.001 Delay(secs)

0.0008 0.0006 0.0004 0.0002 0

Delay(secs)

299569.33 413842.06 704908.13 1195035.8

101823.92 122786.35 163475.87 205110.07

Average throughput based on varied network node density(bits/sec)

Average throughput based on varied network node density(bits/sec)

Effect of throughput on OLSR end to end delay based on varied offered Network node density scenario 0.0006 0.0005 0.0004 delay(secs)

d elay(secs)

0.0012

0.001 0.0009 0.0008 0.0007 0.0006 0.0005 0.0004 0.0003 0.0002 0.0001 0

0.0003

Delay(secs)

0.0002 0.0001 0 444052.9383

692551.174

1439378.433

2601523.78

Average throughput based on varied network node density(bits/sec)

Figure 28: Effect of end to end delay on throughput – Network node density scenario simulation results

MSc. Dissertation

54

XXXXXXXXX

5.5.4 Results Summary: Mobility vs. Varied Pause Time As discussed earlier in section 5.5.1, an investigation was carried out to see the protocols performance when both the pause time and mobility was varied. Longer pause times of 10, 50 and 100 seconds were varied for each mobility factor of 5, 10, 15, 20, 50 and 80m/s. It was discovered that the results obtained for all 4 performance metrics i.e. throughput, end to end delay, packet delivery ratio and routing overhead were similar to those obtained for the initial mobility scenario. For example the average end to end delay for DSR for all mobility factors with a constant pause time of 1 second, was approximately 0.0006 seconds, which was approximately the same value obtained for each mobility factor with the longer pause times. The conclusion here is that longer pause times do not seem to have any adverse effect on protocol performance when it comes to mobility. Graphs obtained from the investigation are too numerous to present here. A total of 73 graphs are available showing the results and has been uploaded as a zip file as supporting material. The graphs are also available on the Project drive.

5.5.5 Realistic Scenario – Small business meeting/conference A network of 25 nodes was created with 6 randomly selected nodes generating traffic, stopping and starting at different times for the duration of the simulation. This scenario tries to depict a typical small business meeting or conference, where a small number of wireless devices would be communicating at any given time. The mobility in this scenario would typically be very low since participants would be seated most of the time, with occasional movements. Parameters used in this scenario are similar to those used by [14], with a slight difference to the number of nodes and channel bandwidth. The authors made use of 50 nodes and 2Mbps. They also incorporated obstacles in their implementation to obstruct radio signals, but this could not be achieved in this project as OPNET does not currently provide models to depict signal obstruction. In order to create a semi realistic scenario, a low mobility factor was used as well as a small number of nodes communicating randomly at different times. An attempt was made to use traffic flows to make the scenario more realistic, between the communicating nodes, but this proved to be unnecessary since the results obtained did not show protocol performance. This is due to the fact that traffic flows’ model background traffic, not explicit traffic. With Explicit traffic, better results are obtained since it models all protocol effects. Screenshots of the scenario model can be found in Appendix B. Below are the scenario parameters Table 10: Realistic Scenario Parameters

Parameter No of Nodes Pause Time Packet rate Packet Size No. of Nodes generating traffic Bandwidth Speed(m/s)

MSc. Dissertation

Value 25 300sec 5pkts/sec 512bits 6 11Mbps 1m/s

55

XXXXXXXXX

5.5.3.1 Results Analysis and Summary

Average end to end delay in a realistic scenario

Throughput in a realisitic scenario

0.0025 en d to en d delay(secs)

th r o u g h p u t(b its /s e c )

500000 400000 300000 200000 100000

0.002 0.0015 0.001 0.0005

0

81 14 4 20 7 27 0 33 3 39 6 45 9 52 2 58 5 64 8 71 1 77 4 83 7

18

18 72 126 180 234 288 342 396 450 504 558 612 666 720 774 828 882

0

simulation time(secs) DSR

AODV

simulation time(secs) DSR

OLSR

Packet delivery ratio in a realistic scenario

AODV

OLSR

Average routing overhead in a realistic scenario

1

AODV

4

OLSR

DSR

3.5

average routing overhead

packet delivery ratio(%)

1.01

0.99

3

2.5

0.98 0.97

2

1.5

DSR

0.96

AODV

1

OLSR

0.5

0.95

0 18

27

36

18

simulation time(secs)

27

36

simulation time(secs)

Figure 29: Realistic scenario simulation results

MSc. Dissertation

56

XXXXXXXXX

Again OLSR and AODV obtain the highest average throughput as expected, despite the small amount of node pairs communicating at specific intervals within the simulated time, DSR still exhibits the lowest average throughput, as discussed earlier this can be attributed to its lack of sensing neighbour connectivity, as well as the effect of carrying source routes in each packet header. While OLSR and AODV maintain a fairly low end to end delay all through, DSR exhibits some spikes within the 100-200, 400-500 seconds of simulation time. These spikes correspond to the time period when most nodes were active during the simulation i.e. at the 100-200 interval 4 nodes were transmitting, while at the 400-500seconds, all nodes were active. Hence more packets are been generated at these periods, and since DSR queues packets that have no known routes, the delay increases as a result. AODV and OLSR once again maintain once again a good packet delivery ratio, compared to DSR. DSR has a rather high routing overhead despite the low mobility, this could be due to the fact that since there is relatively less frequent and rapid mobility more packets would be successfully delivered, which also implies more source routes being carried by packets. The caching mechanism used by DSR could also be a reason for its poor performance, because stale routes may exist and end up being used to route packets. This effectively adds to the end to end delay as well as reduce throughput and increase the amount of overhead.

5.4 General observations It was discovered that DSR spends an average of 12 seconds in discovering routes, while AODV spends an average of 0.06 seconds, as shown in the graph below. The average is at its highest as expected, in the mobility scenario and lowest in the realistic scenario where node mobility was lowest at 1m/s and number of nodes transmitting at any given time was minimal. During the simulation implementation it was observed that DSR took quite a while to run compared to OLSR and AODV. DSR Average route discovery time

0.09

16

0.08

14

0.07 0.06 0.05

Average route discovery time

0.04 0.03 0.02 0.01

route discovery tim e(secs)

route discovery tim e(secs)

AODV Average route discovery time

12 10 Average route discovery time

8 6 4 2 0

0 Node density

Offered load

Mobility

Node density

Realistic

Offered load

Mobility

Realistic

scenarios

scenarios

Figure 30: Average route discovery time

MSc. Dissertation

57

XXXXXXXXX

6 Conclusion 6.1 Conclusion

T

he aim of this study to compare 3 ad hoc routing protocols under a variety of conditions,

has been successful with reasonable conclusions drawn, from observations and results obtained. Summary of the main points gathered from the study are: •

AODV and OLSR outperform DSR in all scenarios.

•

In particular AODV and OLSR perform better and are ideal in environments where there is high degree of mobility, compared to DSR.

•

DSR performs better in networks with light to medium traffic or load, in terms of achievable throughput and routing overhead, but still nowhere near the performances of AODV and OLSR.

•

As expected DSR does not perform well in a dense network which is in line with its RFC specification which states “that the DSR implementation is suitable for networks with nothing less than 200 nodes” [33]. The degradation in performance becomes apparent as node density begins to increase.

•

The use of the “expanding ring search”[32] mechanism by AODV accounts for its low routing overhead, since it helps in reducing the flooding of route requests.

•

The impressive performance of both AODV and OLSR is attributed to their use of Hello messages to maintain link status and neighbour connectivity. The same cannot be said of DSR whose overall poor performance is largely due to its use of source routes carried in every packet header. It’s caching mechanism although useful in providing multiple routes to destinations, also leads to the existence and use of stale routes.

MSc. Dissertation

58

XXXXXXXXX

6.2 Personal reflection and critical assessment The results obtained in this study are by no means exhaustive, given that scenarios used here and in most studies usually differ in parameters, scenarios and general model implementation. A more believable realistic scenario or several scenarios could have been implemented to evaluate protocol performance, but time constraint and OPNET restrictions in terms of available models, made it a bit difficult to achieve to an acceptable, personal level. It has to be said here that the licensing issues experienced with OPNET during the course of this study, slowed down the rate of work, but all in all time frames set, were still on target. This is the first major project undertaken, that involved conducting extensive background research on an important topic area in terms of advances in current technologies. Running large scale simulations and analyzing the results obtained, has been quite a novelty experience. Although not a software engineering based project, it is quite interesting to observe how some of the steps in the process, specifically 2 -5, were part of this project, during the implementation decisions and simulation phases. The learning curve was quite steep, when it came to improving on skills such as planning, time and project management. Also the technical skills of making assumptions, understanding and reading between the lines when there was lack of explicit information, was challenging and rewarding and is regarded as a merit in the learning and development process.

MSc. Dissertation

59

XXXXXXXXX

6.3 Future Work Due to time constraint, a number of interesting things and more research in certain areas could not be done. One is the altering and tuning of protocol parameters to see the effects on performance, since only the defaults as specified in their RFCs’ and Internet drafts, have been used in this study. Extending the study by introducing more protocols is another; this could not be achieved as at the time of this project due to limitations in model availability in OPNET. Comparing energy efficiency ratios of protocols as well as implementing higher layer protocols over Ad hoc routing protocols will be considered. It would be interesting to observe how the results of this study would have turned out if a radio propagation model had been incorporated in the design. This could not be included in this study, due to the non availability of a TMM (Terrain Modeling Module) license. Studying protocol performance using a real life Ad hoc network is also an area of high interest for future work.

MSc. Dissertation

60

XXXXXXXXX

References [1] Ad Hoc Networks. http://www.acorn.net.au/report/adhocnetworks/adhocnetworks.cfm. [2] Additional MANET Page. http://www.ianchak.com/manet/. [3] Ad Hoc Routing Protocol List. http://en.wikipedia.org/wiki/Ad_hoc_routing_protocol_list. [4] Mobile Ad-hoc Networks (MANET) http://www.ietf.org/html.charters/manet-charter.html [5] The National Institute of Standards. http://www.antd.nist.gov/wahn_mahn.shtml. [6] Corson S.M. and Macker J. (1999), Mobile Ad hoc Networking (MANET): Routing Protocol Performance Issues and Evaluation Considerations. IETF RFC 2501 / RFC2501. http://www.rfc-archive.org/getrfc.php?rfc=2501. January 1999, Pages 1-11 (Work in progress). [7] Mehran Abolhasan et al (2004), A Review of Routing Protocols for Mobile Ad hoc Networks, Vol. 2, Issue 1, January 2004, Pages 1-22. [8] Perrone L.F. et al (2003), Modelling and Simulation Best Practices for Wireless Ad hoc Networks. In Proc. 2003 Winter Simulation Conference, December 2003, Pages 685-693. [9] Broch J. et al (1998), A Performance Comparison of Multi-hop Wireless Ad Hoc Network Routing Protocols. In Proc. 4th annual ACM/IEEE Conference on Mobile Computing and Networking, October 1998, Pages 85-97. [10] Das S.R. et al (2000), Simulation-based Performance Evaluation of Routing Protocols for Mobile Ad hoc Networks, Vol. 5, Issue 3, September 2000, Pages 179-189. [11] Ramachandra K. et al (2004), Evaluating the Performance of Various Architectures for Wireless Ad hoc Networks, In Proc. 37th Hawaii International Conference on System Sciences, Pages 1-9. [12] Gauthier V. et al, On a Comparison of four Ad-hoc Routing Protocols when taking into account the Radio Interferences, Pages P42/1-P42/10. [13] Boukerche A. (2004), Performance Evaluation of Routing Protocols for Ad hoc Wireless Networks, Vol. 9, Issue 4, August 2004, Pages 333-342. [14] Johansson P. et al (1999) Scenario-based Performance Analysis of Routing Protocols for Mobile Ad hoc Networks. In Proc. 5th annual ACM/IEEE Conference on Mobile Computing and Networking, August 1999, Pages 195-206. [15] Marinoni S. and H.H. Kari Ad Hoc Routing Protocol Performance in a Realistic Environment. Pages 1-10.

MSc. Dissertation

61

XXXXXXXXX

[16] Jardosh A. et al (2003), Towards Realistic Mobility Models for Mobile Ad hoc Networks. In Proc. 9th annual International Conference on Mobile Computing and Networking, September 2003, Pages 217-229. [17] Choi J. and Ko Y. (2003), A Performance Evaluation for Ad Hoc Routing Protocols in Realistic Military Scenarios. Pages 1-5. [18] Oliveira L.B. et al (2005) On the Performance of Ad Hoc Routing Protocols Under a peer-topeer Application, Vol. 65, Issue 11, November 2005, Pages 1337-1347. [19] Campos G. and Elias G. (2005), Performance Issues of Ad Hoc Routing Protocols in a Network Scenario used for Videophone Applications, Proc. 38th Hawaii International Conference on System Sciences, Pages 1-10. [20] Pandey A.K. and Fujinoki H. (2005), Study of MANET Routing Protocols by GloMoSim Simulator, Vol. 15, Issue 6, November 2005, Pages 393-410. [21] Ishibashi B. and Boutaba R. (2005), Topology and Mobility Considerations in Mobile Ad Hoc Networks, Vol. 3, Issue 6, November 2005, Pages 762-776. [22] Lenders V. et al (2006), Analyzing the Impact of Mobility in Ad hoc Networks. In Proc. 2nd International Workshop on Multi-hop Ad hoc Networks: From theory to reality, May 2006, Pages 39-46. [23] Bettstetter C. (2001), Mobility Modelling in Wireless Networks: Categorization, Smooth Movement and border Effects. ACM SIGMOBILE Mobile Computing and Communications Review, Vol. 5 Issue 3, July 2001, Pages 55-66. [24] Stepanov I. et al (2005), Mobility Modelling of Outdoor Scenarios for MANETs. In Proc. 38th annual symposium on simulation, April 2005, Pages 312-322. [25] Sirivianos M. and Leontaris A. Comparative Evaluation of Ad-Hoc Routing Protocols in Highly Dynamic Environments. Pages 1-10. [26] Haq F. and Kunz T. Simulation vs. Emulation: Evaluating Mobile Ad Hoc Network Routing Protocols. Pages 1-6. [27] Chin K. et al (2002), Implementation Experience with MANET Routing Protocols, Vol. 32, Issue 5, November 2002, Pages 49-59. [28] Cavin D. et al (2002), On the Accuracy of MANET Simulators. In Proc. 2nd ACM International Workshop on Principles of Mobile Computing, October 2002, Pages 38-43. [29] Ad-Hoc Networking – Put your Network on Automatic. http://www.sarnoff.com/products_services/communications_solutions/ad_hoc/index.asp. [30] Kumar S. et al (2006), Medium Access Control Protocol for Ad Hoc Wireless networks: A Survey, Vol. 4, Issue 3, May 2006, Pages 326-358. [31] Cisco Internetworking Technologies Handbook (2002), Routing Basics, February 2002, Chapter 5, Pages 1-10. http://www.cisco.com/univercd/cc/td/doc/cisintwk/ito_doc/routing.htm

MSc. Dissertation

62

XXXXXXXXX

[32] Perkins et al. (2003), Ad hoc On-Demand Distance Vector (AODV) Routing RFC 3561 http://www.ietf.org/rfc/rfc3561 July 2003, Pages 1-37 (Work in progress). [33] Johnson et al (2004), Dynamic Source Routing Protocol for Mobile Ad hoc Networks http://www.ietf.org/internet-drafts/draft-ietf-manet-dsr-10.txt July 2004, Pages 1-111 (Work in progress). [34] Clausen T. and Jaquet P. (2003) Optimized Link State Routing Protocol RFC 3626 http://www.ietf.org/rfc/rfc3626 October 2003, Pages 1-75 (Work in progress). [35] Ogier R. et al (2004) Topology Dissemination Based on Reverse-Path Forwarding RFC 3684 http://www.ietf.org/rfc/rfc3684 February 2004, Pages 1-46 (Work in progress). [36] OPNET Modelling Concepts Reference Manual 2005 [37] Sargent R.G. (1998), Verification and Validation of Simulation Models. In Proc. 30th Conference on Winter Simulation, December 1998, Pages 121-130. [38] Balci O. (1995), Principles and Techniques of Simulation Validation, Verification and Testing. In Proc. 27th Conference on Winter Simulation, December 1995, Pages 147-154. [39] Yihu Li Performance Evaluation for an Ad Hoc Routing Protocol (Presentation from 2003) http://www.mast.queensu.ca/~math484/projects/projects.shtml http://www.mast.queensu.ca/~math484/projects/projects/Yihu03.ppt (Presentation) [40] MANET Status Pages, Mobile Ad-hoc Networks (Active WG) http://tools.ietf.org/wg/manet Page last updated June 30 2006, (Work in Progress).

MSc. Dissertation

63

XXXXXXXXX

Appendix A Ad hoc routing protocol characteristics and classification Characteristics as compiled by Mehran Abolhasan et al [7]

Figure 31: (A.1) Basic characteristics of proactive routing protocols [7]

Figure 32: (A.2) Complex comparison of proactive routing protocols [7]

MSc. Dissertation

64

XXXXXXXXX

Figure 33: (A.3) Basic characteristics of reactive routing protocols [7]

Figure 34: (A.4) Complex comparison of proactive protocols [7]

MSc. Dissertation

65

XXXXXXXXX

Figure 35: (A.5) Basic characteristics of hybrid routing protocols [7]

Figure 36: Complex comparison of hybrid routing protocols [7]

MSc. Dissertation

66

XXXXXXXXX

Appendix B Simulation Environment and scenario screenshots 1. Mobility Scenario

Figure 37: (B.1) Mobility scenario environment Figure (B.1) above shows the setup used for the Mobility scenario which is a 25 node network.

MSc. Dissertation

67

XXXXXXXXX

Figure 38: (B.2) Random Waypoint Model parameters Figure (B.2) above shows the Mobility Config Utility profile used in configuring the Random Waypoint parameters for nodes in the network. Parameters such as the speed, pause time, the maximum and minimum distance within the defined area where nodes can be mobile, are specified here. Right clicking the Mobility Profile Definition utility icon and choosing the edit attributes option from the menu brings up the above dialog box.

MSc. Dissertation

68

XXXXXXXXX

Figure 39: (B.3) Assignment of Ad hoc routing protocol and Raw IP packet generation parameters

Figure (B.3) above illustrates how the Ad hoc routing protocol and packet generation parameters are assigned on nodes. The OLSR protocol has been assigned in the example above. Nodes start generating packets 10 seconds into the simulation and stop at the end of the simulation. Right clicking on any node and choosing edit attributes will bring up the above dialog box.

MSc. Dissertation

69

XXXXXXXXX

Figure 40: (B.4) Wireless LAN parameters Figure (B.4) above illustrates how the Physical and MAC layer parameters are assigned on nodes. Parameters such as the transmit power, bandwidth or data rate, receiver sensitivity are specified under the WLAN attribute.

MSc. Dissertation

70

XXXXXXXXX

Figure 41: (B.5) Wireless LAN Channel attributes The figure above illustrates the WLAN channel attributes. These parameters are auto assigned by the application. Double clicking a node will bring up these channel attributes, where the minimum frequency can be specified. As shown above the ISM license free band of 2.4 GHz has been auto assigned.

MSc. Dissertation

71

XXXXXXXXX

2. Offered Load Scenario

Figure 42: (B.6) Offered Load scenario environment Figure (B.6) above shows the scenario setup for the offered load scenario which is also a 25 node network.

MSc. Dissertation

72

XXXXXXXXX

Figure 43: (B.7) Random Waypoint Parameters used in the offered load scenario Figure (B.7) above shows the RWP parameters used in the offered load scenario.

MSc. Dissertation

73

XXXXXXXXX

Figure 44: (B.8) Raw IP packet generation parameters The figure above shows the packet generation parameters used for the offered load scenario where the packet size was set at 8192 bits.

MSc. Dissertation

74

XXXXXXXXX

3. Network size scenario

Figure 45: (B.9) Network Node density scenario – 30 Nodes

MSc. Dissertation

75

XXXXXXXXX

Figure 46: (B.10) Network Node density scenario – 40 Nodes

MSc. Dissertation

76

XXXXXXXXX

Figure 47: (B.11) Network Node density scenario – 50 Nodes

MSc. Dissertation

77

XXXXXXXXX

Figure 48: (B.12) IP packet generation parameters Figure (B.12) above shows the traffic generation parameters used in the node density scenario.

MSc. Dissertation

78

XXXXXXXXX

4. Realistic scenario

Figure 49: (B.13) Realistic scenario environment Figure (B.13) above illustrates the scenario with 25 nodes, with 6 random nodes starting transmissions at different time intervals.

MSc. Dissertation

79

XXXXXXXXX

Figure 50: (B.14) Realistic scenario RWP parameters Figure (B.14) above shows the random waypoint parameters specified for the realistic scenario environment, with a speed of 1m/s and pause time of 300 seconds.

MSc. Dissertation

80

XXXXXXXXX

5. Setting Confidence Intervals

Figure 51: (B.15) Configuring Confidence Intervals Confidence intervals can be set by right clicking on any graph display panel and choosing edit graph properties, as shown below in figure (B.16).

MSc. Dissertation

81

XXXXXXXXX

Figure 52: (B.16) Configuring Confidence Intervals from editing graph panel properties

MSc. Dissertation

82

XXXXXXXXX

6. MANET node structure

Figure 53: (B.17) MANET node structure Figure (B.17) above illustrates the internal structure of a MANET node. Double clicking on a MANET node from the Process model editor, will open up the above structure display, in the Node model editor.

MSc. Dissertation

83

XXXXXXXXX

7. Configuring multiple random seed values

Figure 54: (B.18) multiple random seed value configuration

Figure (B.18) illustrates the random seed values generated for the simulation implementation. Multiple random seed values are generated from the Configure/run DES dialog box. Multiple seed values allow for multiple simulation runs.

MSc. Dissertation

84

XXXXXXXXX

8. Ad hoc protocol default parameter configuration

Figure 55: (B.19) AODV default parameters

MSc. Dissertation

85

XXXXXXXXX

Figure 56: (B.20) DSR default parameters

MSc. Dissertation

86

XXXXXXXXX

Figure 57: (B.21) OLSR default parameters

MSc. Dissertation

87

XXXXXXXXX

Appendix C 1. Glossary of Abbreviations AODV - Ad Hoc On Demand Distance Vector Protocol ARP – Address Resolution Protocol CPU - Central Processing Unit CSMA/CD – Carrier Sense Multiple Access with Collision Detection DARPA – Defense Advanced Research Projects Agency dBm – decibel; Unit of power levels measurement DCF – Distributed Co-ordination Function DSR – Dynamic Source Routing Protocol GHz – Gigahertz IETF – Internet Engineering Task Force IGRP – Interior Gateway Routing Protocol IP – Internet Protocol ISM – Industrial Scientific and Medical LAN - Local Area Network LANMAR – Landmark routing protocol LSA – Link State Advertisement MAC – Medium Access Control MANET – Mobile Ad hoc Network MPR – Multipoint Relays NIC – Network Interface Card OLSR – Optimized Link State Routing Protocol OSI – Open Systems Interconnection

MSc. Dissertation

88

XXXXXXXXX

QoS – Quality of Service RFC – Request For Comments RIP – Routing Information Protocol RREQ – Route Request RRER – Route Error RREP – Route Reply RTS/CTS – Request To Send/Clear To Send SURAN – Survivable Radio Network TBRPF – Topology Dissemination Based On Reverse-Path Forwarding TORA – Temporally-Ordered Routing Algorithm TTL – Time to Live WG – Working Group WLAN – Wireless LAN

2. Keywords: MANET, Routing protocols, Network performance, Mobile Ad hoc routing protocols, Simulation, Wireless networks, Performance metrics.

MSc. Dissertation

89

XXXXXXXXX