A Comparative Analysis of Routing Protocols in Vanet Enviromnent Using Realistic Vehicular

A COMPARATIVE ANALYSIS OF ROUTING PROTOCOLS IN VANET ENVIROMNENT USING REALISTIC VEHICULAR TRACES

A thesis submitted in partial fulfillment

of the requirements for the degree of

Master of Science (Computer and Information Science)

by

Junaid Mehboob Shaikh

Supervisor

Dr. Ivan Lee

School of Computer and Information Science

University of South Australia

JUNE 2010

DECLARATION

I declare the following to be my own work, unless otherwise referenced, as defined by the University’s policy on plagiarism.

…………………………………..

Junaid Mehboob Shaikh

June 2010

ABSTRACT

This research project is exploring the special application of infrastructure-less wireless system called ‘Vehicular ad-hoc networks (VANET)’ which is derived from its parent network of ‘Mobile ad hoc networks (MANET).’ The key focus of this work is considering the investigative and analysis study of particular routing protocols in VANET environment. The accumulated issues of these routing protocols at network layer like: network formation, traffic movements, and route hopping are examined thoroughly by involving the realistic traces of VANET mobility patterns using network simulator ns-2.

The overall purpose of this study is also associated with the understanding of available routing protocols along their effectiveness and underlying limitations within certain density levels of city and highway scenarios. The careful consideration of these ad hoc routing protocols: AODV, AOMDV, DSR, and DSDV are separately incorporated by simulation models of low, medium, and high concentration phases along with the precise parametric values of defined scenes. The evaluative metrics for the examination of these protocols are measured by packet delivery ratio (PDR) and average end-to-end delay respectively.

The generated and analyzed outputs as a result of the specified inputs by mean of extensive and rigorous simulations are reasonably rational for some and irrational for others. AOMDV and AODV are on the rational side and originated as the proper selection of ad hoc routing protocols for the given cases of city and highway models of VANET with varying traffic concentration.

ACKNOWLEDGEMENTS

First of all, I praise Allah Almighty for His favor to me in completing this study work. Secondly, I would like to express thanks to my supervisor Dr. Ivan Lee for his munificent support and encouragement throughout the research exercise. In addition, I’m also grateful to LST research group at ETH Zurich for providing the generated vehicular traces for further incorporation by the investigative community. Finally, my tremendous appreciations and gratitude are for my parents and brothers whose blessings and moral support always remained with me in every regard.

ABBREVIATIONS & SYMBOLS

Symbol/Abbreviation Term

AODV ------Ad Hoc on Demand Distance Vector

AOMDV ------Ad Hoc on Demand Multipath Distance Vector

CBR ------Constant Bit Rate

DSDV------Destination-Sequenced Distance-Vector

DSR ------Dynamic Source Routing

E2E ------End-to-End

MANET ------Mobile Ad Hoc Network

NS-2 ------Network Simulator 2

PDR ------Packet Delivery Ratio

PERL------Practical Extraction and Reporting Language

QOS ------Quality of Service

TCL ------Tool Command Language

TCP ------Transmission Control Protocol

UDP ------User Datagram Protocol

VANET ------Vehicular Ad Hoc Network

TABLE OF CONTENTS

------Page

DECLARATION---- ii

ABSTRACT------iii

ACKNOWLEDGEMENTS -----iv

ABBREVIATIONS & SYMBOLS v

TABLE OF CONTENTS vi

LIST OF TABLES ------viii

LIST OF FIGURES ix

CHAPTER 1 – INTRODUCTION 01

1.1 General------01

1.2 Problem Definition 03

1.3 Study Objectives 04

1.4 Scope of Work ------05

1.5 Organization of Thesis 05

CHAPTER 2 – LITERATURE REVIEW 07

2.1 Vehicular Ad hoc Networks 08

2.1.1 Mobile Models and Patterns in VANET 08

2.1.2 Reliability and Congestion Issues in VANET 11

2.2 Network Layer and Routing Protocols--- 13

2.2.1 Routing Protocols in VANET 13

2.2.2 Selected Routing Protocols 16

2.3 The Simulator---- 17

2.3.1 Network Simulator 2 (NS-2) 18

2.3.2 Simulaiton Components 18

2.3.3 Simulaiton Operations 19

CHAPTER 3 – RESEARCH METHODOLOGY 20

3.1 Simulations------20

3.1.1 Tool Command Language 22

3.1.2 Network Animator and Trace Files 22

3.1.3 Text Analyzer 24

3.2 Observations---- 24

3.2.1 Routing Metrics ----- 24

CHAPTER 4 – SIMULATIONS AND RESULTS 26

4.1 City Scene------26

4.1.1 Low Density Model 29

4.1.2 Medium Density Model 32

4.1.3 High Density Model 34

4.2 Highway Scene------36

4.2.1 Low Density Model 39

4.2.2 Medium Density Model 41

4.2.3 High Density Model 43

CHAPTER 5 – ANALYSIS AND DISCUSSION 46

5.1 City Results---- 47

5.2 Highway Results 49

5.3 Overall Results 50

CHAPTER 6 – CONCLUSIONS AND FUTURE WORK 54

REFERENCES------57

APPENDIX A – TCL & AWK SCRIPTS WITH TRAFFIC PATTERN FILE 61

APPENDIX B – ANALYZED SIMULATION RESULTS 70

LIST OF TABLES

Figure------Page

4.1 Common variables in city model 28

4.2 City (low density) variables 29

4.3 Analyzed data of city low density 30

4.4 City (medium density) variables 32

4.5 Analyzed data of city medium density 32

4.6 City (high density) variables 34

4.7 Analyzed data of city high density 35

4.8 Common variables in highway model 38

4.9 Highway (low density) varialbles 39

4.10 Analyzed data of highway low density 39

4.11 Highway (medium density) variables 41

4.12 Analyzed data of highway medium density 42

4.13 Highway (high density) variables 43

4.14 Analyzed data of highway high density 44

5.1 Overall evaluation matrix 51

LIST OF FIGURES

Figure------Page

1.1 Wireless infrastructure network 01

1.2 Wireless ad hoc network 02

3.1 Methodology flow 21

3.2 NAM file output 23

3.3 Trace file output 23

4.1 City movement traces on Google map 27

4.2 City movement traces on network animator 27

4.3 PDR at city low density 31

4,4 Average E2E at city low density 31

4.5 PDR at city medium density 33

4.6 Average E2E at city medium density 34

4.7 PDR at city high density 35

4.8 Average E2E at city high density 36

4.9 Highway movement traces on Google map 37

4.10 Highway movement traces on network animator 37

4.11 PDR at highway low density 40

4.12 Average E2E at highway low density 41

4.13 PDR at highway medium density 42

4.14 Average E2E at highway medium density 43

4.15 PDR at highway high density 44

4.16 Average E2E at highway high density 45

5.1 Generic review 46

5.2 PDR of routing protocols in city 47

5.3 Average end-to-end delay of routing protocols in city 48

5.4 PDR of routing protocols on highway 49

5.5 Average end-to-end delay of routing protocols on highway 50

5.6 Graphical representation of overall evaluation matrix 53

71

CHAPTER 1

INTRODUCTION

1.1  General

The advent of wireless networking is responsible for the entire drift of the communication paradigm we observe today. This is because of its easy deployment and setup phases. Devices are simply required to be powered by some source of energy and having their availability within the specified ranges to form a network and start communicating with each others with no wires or ducts. Furthermore, these wireless networks are classified depending on their deployment modes of fixed and flexible mobile scenarios, and therefore termed as wireless infrastructure and wireless ad-hoc networks respectively.

The fixed mode in wireless requires a firm infrastructure to be arranged before devices can start communication with each other. These devices (commonly known as nodes) are then come in contact with those centrally installed bridges or routers to forward and receive the data. This depending feature of nodes on fixed hardware devices is an example of an infrastructure mode of wireless network (Figure 1.1).

Figure 1.1: Wireless infrastructure network

On the other hand, there are circumstances where nodes do not require any preinstalled setup due to various reasons and can directly establish their communication by using the services of other co-joined nodes as a router for forwarding and receiving of data in between nodes. This is an example of wireless ad-hoc network (Figure 1.2). Moreover, ad-hoc networks with the manipulation of WLAN (802.11) standard and its built-in support in various devices of daily usage has introduced the notion of inexpensive and cheap communication models. It is the most obvious reason for wireless popularity nowadays.

Figure 1.2: Wireless ad hoc network

The communication area which is related with the scope of this thesis is an emerging and exciting application of an ad-hoc network where vehicles are serving as nodes. This area has certain promised aspects and activities to be offered, which are broadly related with the safety, convenience, entertainment, and various other topics of interest. It is an ad hoc network of vehicles, known as ‘Vehicular Ad Hoc Network (VANET).’

1.2 Problem Definition

Movement of vehicles on roads is constrained by different conditions, suggested in James (2009). These conditions are related with speed zones, traffic congestions, weather conditions, road works, etc. These kinds of limitations allow vehicles to form a group of clusters among them to manage traffic flow in all directions fairly and smoothly. Another condition discussed in Victor (2009) regarding the varying velocities of vehicles and abrupt move of paths without any notification. With these conditions and limitations it is sometimes not possible for vehicles to establish direct link between one another with the help of single hop, which is related with the specified area of coverage. Hence, internetworking among different clusters needs to be considered. To manage the communication link between out of ranged vehicles (nodes), different routing protocols are involved. Through relevant studies in Victor (2009), Tarik (2006), Chung (2006), and many other associated works, it is found that the available routing protocols for ad-hoc networks already proposed and implemented are not majorly compatible within VANET scenario due to above conditions. Hence, certain adaption and improvements being made with respect to available conditions of the said network and are still in focus of many researchers for revision.

This research work is therefore (an effort to) highlighting the importance of routing protocols in VANET environments under different conditions (especially through pragmatic scenarios) and to observe and analyze their effects accordingly by mean of rigorous simulation test cases and comparative analyses.

1.3 Study Objectives

The objectives of this research are devoted with the analyses of routing protocols in vehicular networking environment. This is done by considering the performance metrics of routes within various mobility models and densities of vehicles; also involving their communication paradigm and hoping techniques.

The mobility models are actually the movement patterns for vehicular network which are replicating the physical roads for simulation prototypes. Many of them are already available and could be converged according to their particular VANET scenarios. So this work will be emphasizing the study of most viable routing protocols which are self converged and flexible enough within such network situations. It also analyzes and examines the selected proposed protocols with their mentioned future deployments on top of existing routing protocols to observe their results. The major prominence for these analyses would be varying according to the conditions of routing metrics like: packet delivery ratios, average end-to-end delay, number of hop counts, and likewise.

Since many of the VANET research works are still simulation based but there are some quite exciting and upcoming projects expected to be available before long in the real world situations. Therefore, the study objectives highlighted here are also depending upon various rigorous simulation scenarios. In outcome, the analyzed results will show and differentiate the appropriate selection(s) of network layer protocols i.e. routing protocols within the given circumstances of feasible path selection in the vehicular traffic scenarios.

1.4 Scope of Work

The scope of this work is associated with the coverage of complete communication and routing paradigm in vehicular ad hoc networks.

Initially, the simulation schemes would be considering the generic mobility patterns of the road networks. These patterns will then be extended for the specified cases of traffic scenarios, like city movements and highway flows depending on the saturation capacity of the provided scenes. These aspects will then be broadly dealing with message broadcasting, multicasting, and unicasting requirements, depending on the nature of communication. Additionally, the routing investigations at variable densities of these mobility models would be simulated and formulated at their certain generated test-beds setup in the tool called Network Simulator (NS2).

1.5  Organization of Thesis

This report is written in chapter wise format with the total of six chapters. The first chapter gives the general idea regarding the motif and theme of the work. It also discusses the brief and concise overview of problems involved, study objectives and scope of work. The second chapter is of literature review which will be covering all the related topics in more detail for further understanding. The reason of this chapter is to make the grounding of work in depth through all the searched and reviewed stuff so that everything should be clear beforehand. The concerned topics for this chapter will be mainly related with finding of issues in VANETs and their proposed, deployed, and corresponding routing schemes along with the simulation tool. The third chapter is of research methodology where the useful working way will be conferred in the step wise layout. This chapter discusses the procedures and approaches to be adopted for achieving the objectives. The fourth chapter is the practical representation of its previous chapter in which the Simulations’ outcome and their Results are highlighted in both tabulated and graphical formats. This will then be followed by the comprehensive analysis and discussion section of chapter five. By academic tradition, the final chapter will be of conclusions and future work.

CHAPTER 2

LITERATURE REVIEW

This chapter covers the initial literature survey done for VANETs and their associated schemes including network layer issues in particular. It further followed by narrowing down to the specific literature reviews toward the selected topic and its achieving objectives.