Comparitive Performance Study Of Routing Protocols in Wireless Sensor Network

Table of Contents

1. Introduction
1.1 Background
1.2 Problem Definition
1.3 Motivation for Current Work
1.4 Research Question
1.5 Research Methodology
1.6 Aims and Objectives
1.7 Assumption
1.8 Thesis Contribution
1.9 Related work
1.10 Organization of the Thesis
Summary

2. Routing Protocols in IP-Datagram Networks
2.1 Introduction
2.2 Routing
2.3 Proprieties of Routing Protocols
2.4 Classification of Routing Protocol
2.5 Goals of Routing Protocol
2.6 Conventional Routing Protocols
2.6.1 Adaptive Routing Protocols
2.6.2 Open Shortest Path First (OSPF)
2.7 Enhanced Interior Gateway Routing Protocol (EIGRP)
2.7.1 Link-state- based Routing
2.8 Border Gateway Protocol or Path Vector- based Routing
2.9 Advance Routing Approaches
2.9.1 Self-Adjusting Routing Protocols
Summary

3. Routing Protocols in Wireless Ad-hHoc and Sensor Network
3.1 Introduction
3.2 Classification of Wireless Network
3.3 Conventional Ad-Hoc Routing Protocol
3.3.1 Optimal Source Routing (OSR)
3.3.2 Wireless Routing Protocol (WRP)
3.3.3 Global State Routing (GSR) Protocol
3.4 Wireless Sensor Network (WSNs)
3.4.1 Network Characteristics, Design Objectives
3.4.2 Network Design Objectives
3.4.3 WSNs Network Design Challenges
3.5 Routing
3.5.1 Routing in Wireless Sensor Network
3.5.2 Classification of Wireless Senor Network Routing Protocols
Summary

4. Design of Simulation Experiments
4.1 Introduction

List of Tables

3.1 Seven WSN’s routing protocols categories

4.1 Simulation Parameters Table
4.2 Parameters Table-Exp 1- Case 1: Rumor Routing Stationary Nodes
4.3 Parameters Table Experiment 1- Case 2: Rumor Routing Mobile Nodes
4.4 Parameters Table -Experiment 1- Case 2: Rumor Routing Mobile Nodes
4.5 Parameters Table -Exp1- Case 2: Rumor Routing Mobile Nodes
4.6 Parameters Table -Exp 2- Case 1: Stationary nodes using rumor routing
4.7 Parameters Table -Exp 2- Case 2: Mobile nodes using rumor routing
4.8 Parameters Table -Exp 2- Case 3: Mobile nodes using rumor routing
4.9 Parameters Table -Exp 2- Case 4: Mobile nodes using rumor routing
4.10 Parameters Table -Exp 3- Case 1: Stationary nodes using rumor routing
4.11 Parameters Table -Exp 3- Case 2: Mobile Nodes using rumor routing
4.12 Parameters Table -Exp 3- Case 3: Stationary Nodes using OSR routing
4.13 Parameters Table -Exp 3- Case 4: Mobile Nodes using OSR routing
4.14 Parameters Table -Experiment 4- case 1-Simulation Time
4.15 Parameters Table -Experiment 4- case 2-Simulation Time
4.16 Parameters Table -Experiment 4- case 3-Simulation Time
4.17 Parameters Table -Experiment 4- case 4-Simulation Time
4.18 Parameters Table -Experiment 5- case 1-Deployement Area
4.19 Parameters Table -Experiment 5- case 2-Deployment Area
4.20 Parameters Table -Experiment 5- case 3-Deployment Area
4.21 Parameters Table -Experiment 5- case 4-Deployment Area
4.22 Parameters Table Experiment 6- Case 1- Interference handler model
4.23 Parameters Table -Experiment 6- Case 2- Interference handler model
4.24 Parameters Table -Experiment 6- Case 3- Interference handler model
4.25 Parameters Table -Experiment 6- Case 4- Interference handler model

5.1 Parameters of IEEE802.11g WLAN standards
5.2 Parameters of IEEE802.11g WLAN standards
5.3 Parameters of IEEE802.11g WLAN standards
5.4 Parameters of IEEE802.11g WLAN standards
5.5 Parameters of IEEE802.11g WLAN standards
5.6 Parameters of IEEE802.11g WLAN standards

List Of Figures

1.1 Typical WSNs Components overview
1.2 (a) Represent small topology, ( b) Represent medium topology, (c) represent large topology
1.3 (a) Represents dense network in a smaller area, while figure (b) 5 Represents sparse network of the same size but in large area
1.4 Bar chart representation of simulation pause time
1.5 Represent interference and communication range

2.1 Classsfication of routing proctols startegies in IP-Datagram networks
2.2 Shortest path finding mechanism

3.1 Block diagram of wireless network classification
3.2 Ad-hoc routing protocols classification chart
3.3 OSR single node movements
3.4 Classification of spinal routing algorithm
3.5 Hierarchical diagram of WSNs routing protocols classification
3.6 Rumor routing chart representation
3.7 Query is originated and query source is looking for the path to reach to the event
3.8 Agents aggregating to multiple events
3.9 Represents the greedy approach from node x to node y, because these are located in close neighborhood
3.10 In Greedy Forwarding Routing the data packet is forwarded to a 60 neighbor that which is located in a close proximity
3.11 When greedy routing gets stuck in topology
3.12 When there is a hole in the network
3.13 Generic view of different faces of planner graph
3.14 Generic view of source and destination at planner graph
3.15 Represents base station, cluster head, and cluster
3.16 Different level of hierarchies

4.1 ShoX starting view
4.2 ShoX Configuration Panel
4.3 ShoX Architectural View
4.4 Network topology of 10 nodes
4.5 Network topology of 25 nodes
4.6 Network topology of 49 nodes

5.1 Relative performance comparison in small stationary topology of 10 92 mobile nodes
5.2 Relative performance comparison in small mobile topology of 10 nodes
5.3 Relative performance comparison in small stationary topology of 25 96 nodes
5.4 Relative performance comparison in small mobile topology of 25 nodes
5.5 Relative performance comparison in large stationary topology of 49 100 nodes
5.6 Relative performance comparison in large mobile topology of 49 nodes
5.7 Relative performance comparison at different simulation time
5.8 Relative performance comparison at different simulation time
5.9 Relative performance comparison at deployment area of 300 x 400 m
5.10 Relative performance comparison at deployment area of 300 x 400
m²
5.11 Relative performance comparison at minimum SNR interference model
5.12 Relative performance comparison at minimum SNR interference 112 model

List of Equations

3.1 Relation between Radio Range and Grid Size 56

illustration not visible in this excerpt

Disclaimer

I hereby certify that this material, which I now submit for assessment on the programme of study leading to the Degree of Masters of Science in Computing at Griffith College Dublin, is entirely my own work and has not been submitted for assessment for an academic purpose at this or any other academic institution other than in partial fulfillment of the requirements of that stated above.

Abstract

Modern wireless sensor network can be expanded into large geographical areas via cheap sensor devices which can sustain themselves itself with very a low power usage. The networking capability enables these sensor nodes to incorporate, collaborates, and coordinates with among each other , and this is a fundamental shift in the field of networks which differentiates sensor network nodes form other networks such as IP-datagram, Ad-Hoc and so on.

Currently, routing in the wireless sensor network faces multiple challenges, such as new scalability, coverage, packet loss, interference, real-time audio and video real time streaming, harsh weather environments, energy constraints and so forth. Network routing can be called an amalgamation of routing protocol and routing algorithm. The job of the routing protocols is to provide a cohesive view of network nodes topology while routing algorithm provides the intelligence in terms of optimal path calculation.

We set out to conduct a detailed study of routing protocols in a IP-datagram, wireless ad-hoc and sensor network, and also accomplished routing protocols comparison against the chosen network performance factor dropped packet ratio.

Routing protocols play an important role in modern wireless communication networks. Routing protocols’ performance can be measured by a number of factors such as packet dropped rate and so forth.

Rumour and Optimal Spinal Routing algorithms are compared using ShoX simulation and the results and analysis are based upon the simulation experiments.

Dedication

I dedicate my thesis to my beloved family, especially To my late father:

Haji. Muhammad Imran Khan ( Mamaan Khan), To my mother,

To my late grandfather and grandmother, To my uncles:

Haji. Muhammad Afsar Khan Haji. Muhammad Irshad Khan Haji. Tahir Muhammad Khan

Acknowledgments

In the name of Allah, most Gracious, most Compassionate.

First of all, I would like to offer my special thanks to Allah for the guidance and assistance in this thesis.

I wish to offer my special thanks to my supervisor Dr. Faheem Bukhatwa for his advice and support during the writing of this thesis.

I would like to pay special thanks to my family for their prayers and encouragement during my studies.

Finally, I would like to give special thanks to my all weather friends Kalpesh Nahire (Nasik India), M. Tahir Azam (Chakwal Pakistan), Sumit Walia (Delhi India), Asif Ali (Derby UK), Dr. M. Asim ( JMU Liverpool UK), Shah Fahad (Swat Pakistan), and M. Imran Akhtar (Haripur Pakistan).

Abid Afsar (Malang Palsapi) Griffith College

October 2012

Chapter 1 Introduction

1.1. Background

Wireless communication is rapidly growing in our day to day life because it is easy to deploy and is more flexible. In particular, the wireless sensor network (WSN’s) is one of the latest innovations in the field of wireless communication. It consists of tiny mote which hold a small battery, CPU and sensor. Today, sensor motes are widely used by the military in the battle field as a means to closely monitor enemy activities. Sensor networks are also used in healthcare, wide-life, temperature monitoring and many other applications. A diagrammatic components overview of WSNs is shown below,

illustration not visible in this excerpt

Figure 1.1. Typical WSNs components overview

The above diagram represents a number of WSNs components, such as sensor node architecture, base station, deployment area, and sensor nodes event region which are represented in blue and green colours. Routing is an important issue in a wireless sensor network and a number of routing protocols were proposed however, an efficient routing algorithm remains an issue The recent development of a wireless sensor network has led us to an innovative use of small sensory nodes which operate with a very low power in extreme environmental conditions. The group of small sensory nodes are randomly deployed in a sensor field. Theses nodes have the ability to organise themselves automatically and to detect neighbouring nodes to from an ad-hoc network. The nodes of the WSNs can plan what sort of sensing data to receive, send, or query some particular event. The query concept in sensor networks leads us to new ways of routing, for instance clustering sensor nodes, redundancy, and so forth.

Today, there are number of sensor motes commercially with low prices ranging from 50$ to 100$ per single mote. It is further expected that the price will go down in the next five years. One of the leading manufacturers is the Crossbow Inc., which makes Intel motes. There are number of development projects is in progress, such as Smart Dust Project which are going to optimise a large number of motes into a single chip, operating system called TinyOS which is currently freely available and being developed for a senor network. A programming language called EmStar is used for the development of sensor nodes, a communication interface called NesC is developed for sensor nodes and finally a database called TinyDB was developed to transfer data between heterogeneous sensor networks.

1.2. Problem Definition

The rationale of this thesis is to investigate efficient routing protocols which can successfully deliver data packets in sensor network. Wireless network protocols which are currently in place have suffered from a number of issues such as drop packets, address table overhead, topology convergence, throughput, data packets delay, routing overhead and so on. In WSNs there are number of issues which pose new challenges for the wireless sensor network. As we are aware that WSNs mote consist of a small battery with limited power and because of this limitation it gives birth to a new set of problems such as routing, and scalability in WSNs.

The motes perform their operations by the sensor on board but it’s quite challenging to route data when the intermediary motes lose battery power at transit or have low power, and it further leads to problems such as topology adjustment, mote data recovery and back-up and so forth. Therefore we believe that to route sensing data properly we need to have intelligent WSNs routing protocols which give better strategies in terms of energy and scalability WSNs routing is still a challenging area for the researcher. One problem is the energy in WSNs, so there is an open option to make routing decisions on the basis of energy awareness. The core issue involved with wireless senor network routing is related to rigorous resource constraints allocation in terms of computation, storage and energy consumption which make it not only interesting but challenging.

In the event of a problem the associated routing algorithm does not have an intelligence to adjust them dynamically and it is also termed as non-adaptive routing protocols.

In carrying out our research we found that a large amount of work has been done in the area of routing in WSNs, but these are largely individual contributions on specific routing protocols. We feel that there is a need for a detailed level of study in the area of WSNs routing protocols. There are a number of routing protocols proposed for WSNs routing but unfortunately the consideration and need for an efficient, intelligent routing mechanism was not taken on board.

1.3. Motivation for Current Work

- Routing is an important research area in wireless communication networks and particularly needs more research interest due to emerging technologies such as a wireless sensor network, network on chip and so on
- The wireless sensor network brought new opportunities and challenges, because of its non-infrastructure-based network, and can be deployed in a large territory having harsh environmental conditions, where sensory devices can be left unattended. We can also study environment-related events in real time with more precision and accuracy
- The WSNs-based network is further evolving towards a multimedia-based network which involves heavy traffic, such as live video monitoring of a remote event and so on. Therefore, the WSN is facing significant new challenges such as drop packet, routing overhead, packet delay, and so forth
- number of routing algorithms were proposed but there is an urgent need for a comparative study on these protocols which will be used as a guide tool for researcher and developer in the routing domain.

1.4. Research Questions

The research is focused on the comparison between some routing protocols. After some search and studies the choice of protocols was narrowed down to two: Rumour and OSR protocols. The research question can be outlined by one main question and further clarified by four sub-questions. The main question for this research is the following:

Q. Which of the two routing protocols: rumour protocol or OSR protocol, performs better under different circumstances?

The main research question is further defined as,

Q1. Which protocol performs better in small, medium, and large network topology?

illustration not visible in this excerpt

Figure 1.2. (a) Represent small topology, (b) represent medium topology, (c) represent large topology

Q2. Which protocol performs better with a different sized deployment area?

The node deployment area variants are explained with the help of the following two scenarios, where the geographical areas are different but the number of nodes remains the same.

illustration not visible in this excerpt

Figure 1.3. (a) represents a dense network in a smaller area, while figure (b) represents a sparse network of the same size but in a larger area

Q3. Which protocol performs better at different simulation times?

The different variant of simulation times, such as 20, 60, and 100 seconds and so on

illustration not visible in this excerpt

Figure 1.4. Bar chart representation of simulation time

Q4. Which protocol suffers more from interference?

The interference between nodes A, C and B is illustrated as,

illustration not visible in this excerpt

Figure 1.5. Represents interference and communication range

Moreover, the drop packet ratio will be used as a network performance evaluation metric for the aforesaid scenarios.

1.5. Research Methodology

Initially, we start our research by investigating the wire network routing protocol in detail which is detailed in Chapter 2. But later on we stick to wireless network routing protocols because it is an area which is rapidly expanding due to their low cost, high mobility, scalability, easy deployment and so forth.

Furthermore, our work consists of two parts. First, we design some proposed network scenarios and stimulate these by using the Scalable Ad-Hoc Network Simulator (ShoX) for the OSR routing algorithm and observe the performance and behaviour of OSR alone. Second, we apply the same network model to rumour routing algorithm using the ShoX simulator and judge the performance and behaviour of rumour alone. Furthermore, with respect to the evaluation comparison of OSR and rumour this is based on a metric such as the dropped packet ratio. ShoX simulator is used for the evolution and comparison of proposed protocols.

1.6. Aims and Objectives

The main aim of this thesis is to research the problem of routing in wireless communication networks particularly wireless sensor networks, and the constraints involved with routing such as packet drop, for example.

Our second aim is to perform a detailed study of routing protocols which are either deployed or proposed for WSNs.

Third, a comparative study and analysis of routing protocols can be done by means of network simulator. Network performance can be measured against metric like the dropped packet ratio using ShoX simulator. Furthermore, we also aim to provide a precise guideline tool to the developer and researcher with regard to a selection of efficient routing protocols in the future.

1.7. Assumption

Our assumption is based on routing protocols and their use in wireless sensor network application, which is listed as,

- We further assume that our sensor network is homogenous by nature, where all nodes are of equal size
- WSNs nodes assume that they know their local information, and are aware of their close neighbours for the purpose of packet forwarding.
- Wireless sensor routing protocols assume that they know the destination address in advance
- WSNs nodes can be mobile and stationary depending on the sensor application scenario.
- WSN motes for sensor application can be placed an unattended environment and we also assume that these nodes have the features of being self-organising and fault-tolerant.
- WSN nodes are deployed in an outdoor plain environment and environmental and atmospheric conditions are assumed at a normal level.
- WSN nodes transceivers use single channel and wireless antenna, are Omni-directional and propagate isotropic signals in all direction
- We also assume that mobile nodes choose their speed randomly
- We further assume that the collision model we use is CSMA, 802.11g

1.8. Thesis Contribution

The core contributions of this thesis are as follows:

First, the thesis provides a detailed study of routing protocols which includes wireless routing protocols and their architecture, design challenges, and other constraints.

Second, a comparative study of routing algorithms wireless sensor network can be presented for the selected list of protocols in the WSN routing domain.

Third, an extensive number of simulation experiments and analysis can be performed using ShoX simulation.

Fourth, the thesis would be a guideline tool for the selection of an efficient routing protocol and would alleviate the work of the developer and researcher in the routing domain in the near future.

1.9. Related Work

The routing has a significant function in computer networks both in terms of resource management, traffic management and routing. There are a number of routing strategies which are used such as the shortest path algorithm, optimal routing and so forth. The network’s performance level depends on the number of routing factors such as throughput, packet overhead, delay, congestion, and so on. [AX5]

Routing has been an interesting subject for last twenty years or more and significant material is available on the subject. Routing has experienced different types of loops such as forwarding loop, information loop and trace-rout loop and many of the routing algorithms have a pre-avoiding loops mechanism. [AX6]

The wireless senor network consists of tiny sensory nodes and these have the capability to maintain the network topology dynamically. The sensory nodes can be mobile but this depends on their application. Routing in a wireless sensor network is challenging because it does not involve a proper infrastructure. Energy, hardware and software resources are limited which makes routing difficult. The network performance can be measured by a number of factors such as throughput, network delay and so on. A number of routing protocols was proposed for the wireless sensor network such as AODV, OLSR, DYMO and many more. [AX7]

1.11. Organization of the Thesis

Our work is broadly planned as follows the thesis consists of six chapters. Chapter 1 presents the background of the thesis and problem definition. Chapter 2 presents the IP- datagram routing protocols in detail. Chapter 3 presents routing protocols in a wireless sensor network. Chapter 4 discusses design and simulation. Chapter 5 presents the simulation results and analysis and finally Chapter 6 presents the conclusion of the whole thesis, future work and bibliography.

Summary

In this chapter we introduced our project and the main statements of our research question and an overview to wireless sensor network. In the next chapter we will discuss IP-datagram protocols in details.

Chapter 2 Routing Protocols in IP-Datagram Networks

2.1. Introduction

This chapter presents a detailed study of routing protocols in the context of a best effort IP network.

2.2. Routing

Routing is the product of routing protocols and routing algorithms. The routing protocol gives the overview of the topology of the entire network while the routing algorithm adds the power of intelligence to how one computes the path between multiple network nodes. [swapnil]

Firstly, we will perform a detailed study of routing protocols. In the literature there is an abundance of material available on routing and it is an extensive area of study in itself. In data communication routing is the core feature of guiding and directing in large networks. Furthermore, routing provides an optimal path according to the metrics mentioned.

Routing is broadly divided into two main classes: adaptive routing and non-adaptive routing.

In static routing a route is not maintained automatically and needs to be updated manually. In a situation where the algorithm fails to update, the only way to recover it is to restart (?) the algorithm manually in order that it can accommodate itself within the specified network link requirements.

In addition, there are more routing classes such as delta routing, multi-path routing and hierarchal routing and so on.

2.3. Properties of Routing Protocols

There are a number of properties which routing protocols possess and they have a wide impact on today’s inter-connection networks. The author discusses this under the following headings:

Connectivity: It is the responsibility to assign a route for a packet coming from a source node to a destination node.

Adaptivity: The property guarantees that there should be an alternative path for each and every packet in case of link or network device failure.

Fault Tolerance: The property sates that the fault tolerance can be attained by applying a storing-and-forwarding technique to some nodes in two or more phases, while it can also be accomplished through adaptivity but it is not always applicable and true.

Deadlock or live-lock freedom: The property states that there should be no blockade and superfluous traffic in the network.

2.4. Classification of Routing Protocols

A ‘routing algorithm’ can be defined as a methodology through which a node makes a decision about its neighbouring route for the purpose of sending a packet to an expected destination. A Routing Table stores the local link information and is updated from time to time.

Ignasi Paredes Oliva defines the routing as “Driving packets from source node to destination node in a network”. Routing algorithms play a pivotal role in today’s computer networks. And also with the exponential increase in computer networks and distributed systems and other web applications it is obvious that the network traffic management and routing are the core issues. [BX5] The central job of the routing algorithm is to generate a path for the network packets. There are a number of routing algorithms mentioned in the literature, but our study will focus on the routing algorithms which are of particular use for computer inter-connection networks. We also focus on those routing algorithms which are important for future studies in relation to modern computer inter-connection networks.

Jose, Sudhakar, Lionel state that routing algorithms can be classified in many ways; broadly classify the routing algorithms according to the number of destination packets which need to be delivered. A packet can be sent uni-cast or multi-cast.

illustration not visible in this excerpt

Figure 2.1. Classsfication of routing proctols startegies in IP-Datagram networks

In data communication networks a routing algorithm can be classified as uni-cast, broadcast, multi-cast and any-cast.

Alternatively, Sharam classifies routing algorithms as flooding, static and dynamic routing.

1. Uni-cast Routing

In a uni-cast routing algorithm a packet is destined only for one specific destination from a source.

2. Broadcast Routing

In broadcasting a message is broadcast to all available links in the network, the reason being that the medium of communication is shared between all the network nodes.

The N point-to-point algorithm is a broadcast algorithm and it sends packets to every destination. The limitation is that it wastage of bandwidth and have the pre-knowledge of all destinations.

The next broadcast algorithm is ‘flooding’. The packet is sent to every host in the network. There is a strong likelihood that some hosts will receive dual packets and because of this mechanism the duplication arises in the network but the algorithm can detect the duplication of packets.

3. Multi-cast Routing

The main goal in the multi-cast routing is to send packets to a designated number of network hosts but not all.

4. Any-cast Routing

The main goal in the any-cast routing is to send packets to a particular single designated computer in the network.

According to Mischa Schwarz the routing algorithm is divided into four classes, Firstly, the routing path selection function and routing table creation can be performed in a centralised and decentralised or distributed approach.

Secondly, the routing mechanism can follow an adaptive approach. n this approach the routing path information is updated when changes occur in the network topology. The routing mechanism adapts itself according to the topological, traffic changes taking place in the network. It dynamically responds to all sorts of traffic conditions happening in the network.

Thirdly, a class of routing algorithm uses cost as a metric to link nodes for the purpose of routing path selection. In regard to cost calculation there are a number of parameters usually used such as network link bandwidth, link length, speed, expected delay, latency, level of security and so on. The cost can be a combination of multiple parameters such as link bandwidth and delay.

Fourthly, it is one of the best known and popular types of routing algorithms studied in the literature which works on the basis of performance and it is called ‘least-cost path algorithm’ or ‘shortest-path algorithm’. In the shortest path algorithmic approach the least cost path can be defined as the linear sum of the hops between source and destination. Furthermore, it also involves adaptive routing which includes full adaptive and partial adaptive algorithms because in these algorithms the link cost can be dynamically changed due to delay, error condition or speed and so on. The shortest path algorithmic mechanism is widely used in the routing of datagram communication networks.

In performance base routing algorithms the next category involves the use of a number of techniques to mitigate the time delay, network utilization and also use an estimated metric between source and destination. It further evaluates the performance between source and destination by using multiple paths.

2.5. Goals of Routing Protocols

[Tanenbaum], suggested that the following properties in relation to routing algorithms need to be taken into consideration in order to reach a solution to the routing problem:, Correctness: The property states that an algorithm should be able to accommodate itself within topological variation and network problematic conditions. The algorithm should also be able to find the optimal path in any circumstances for the network.

Simplicity: The property states that an algorithm needs to be simple, efficient and easy to implement.

Robustness: It is crucial that the network should have the capability to work in a situation like node failure, path congestion, like failure and so forth.

Stability: The property states that after specified runs of the time-frame window an algorithm needs to be in a stable position.

Fairness: The property states that for the delivery of a packet, the packet delivery time schedule must be followed.

Optimality: The property states that an optimal path should be found from a source to destination. The optimal path depends on the network parameter. It is not compulsory that an optimal must always be the shortest path, for instance a longest path can be considered an optimal path because of less buffer delay for example.

Scalability: The property states that an algorithm needs to be capable of improving and giving its best performance as the network resources expand and traffic grows.

In the commuter network literature the routing algorithm can also be classified into nonadaptive routing and distributive adaptive routing.

We further categorise the routing algorithm into two main groups, which are stated as, There are a number of routing algorithms which exist in the network routing domain but our research focuses on the set of conventional routing algorithms and an advance self-adjusting Q- learning routing algorithm and routing algorithm.

2.6. Conventional Routing Protocols

2.6.1. Adaptive Routing Protocols

In today’s global computer networks two routing algorithms are used, the shortest path and distance vector. These algorithms provide the foundation for many routing protocols which are deployed on the internet today. The routing information protocol (RIP) and interior gateway routing protocol (IGRP) are built upon the distance vector algorithm’s updated version. OSPF are built on the basis of the shortest path algorithm while EIGRP is the basis of the on dual routing algorithm. BGP is also based on path vector algorithm which is an improved version of distance vector algorithm.

2.6.2. Open Shortest Path First (OSPF)

The Open shortest path first (OSPF) is a link state routing protocol. The protocol was developed on the basis of Dijikstra shortest path first algorithm. The link state routing strategy is also used in the IS-IS routing protocol. In the link-state base routing each network node develops its own map of network topology.

OSPF is an intra-domain routing protocol and operates inside a single autonomous system and is the most dominant interior gateway protocol and is largely used in large organizational networks. OSPF is compatible with the variable link subnet mask VLSM and CIDR IP-subnet addressing mechanism.

The core concept in OSPF is that every network node has knowledge of the whole network topology.

OSPF Areas

OSPF divides the network routing domain into several areas and the initial area is called Area 0. A backbone is required when a packet is forwarded into another routing area.

OSPF Network Classes

The OSPF routing protocol divides the network into a number of classes such as nonbroadcast multi-access, multi-access, point to point and so on.

OSPF Timers

OSPF uses a number of timers, for instance if links are down for less than 30 seconds and then recovered again so in this case it is not noticed. When a link goes down for half or less than half an hour, then in this case OSPF floods LSA for both events including both the up and down status of a link.

The advantages and disadvantages are described as follows:

1. Advantages

- Performs fast convergence.
- Provides loop free routing paths.
- It is scalable and does not restrict network to hop counts limits.
- Updates occur every 30 seconds and there are no other updates.
- OSPF sends hello packets for the purpose of checking the status of the link and does not send a full routing table.

2. Drawbacks

- OSPF is very expensive in terms of memory and computational power.

2.6.1.1. Shortest Path Routing Algorithm

There are a number of algorithms in the network literature for finding the shortest path algorithm, but our study will only focus on the Dijiksta algorithm in this shortest path algorithm domain. Let s is source and u is the destination, and the shortest path from s to u can be described as,

illustration not visible in this excerpt

Figure 2.2: shortest path finding mechanism

1. Dijikstara Algorithm

The Dijaskrta algorithm in the literature is also termed as the shortest path or Greedy Algorithm. It is the most accepted algorithm because of its enormous use in today’s internet and because of its simplicity and ease of use. In terms of its route computation it uses cost metric. The cost metric differs as it can be computed by a number of distinct metrics such as delay, bandwidth, data rate and financial cost and so forth. The route optimization is the core functionality of the Dijikstar algorithm. It optimises the routing to an optimal path by performing computation at each node of network. [Firat]

Furthermore, a known limitation of the Dijikstara algorithm is that it selects an optimal path irrespective of the future network needs such as congestion on a path or link failure and it is obvious that current global networks are dynamic and distributive in nature. For example, if there is a queue of packets at of the middle network node buffer, and as a result the packets are delayed for a particular destination, in this situation it would be better to go for an alternative path but there is no guarantee that an alternative path would be the shortest and as a result it can achieve the shortest time delivery but not the shortest path. [F. Tekiner

et al].

Graphical Representation of Dijikstra Algorithm

The Dijikstra algorithm can be graphically represented as; in the networks each node computes its routes to other connected nodes. The scenario is represented with a diagram where each node is considered as an edge and link as a vertex, a vertex connecting two edges. In relation to the cost of the vertices it is taken as non-negative.

Let us consider that V is the set of all edges in the digraph, the array of the cost metrics of the vertices is c[s, w], and the array to least cost path for any node is D[w] which is to be computed. In the first step, the value for the shortest path to any edges in the digraph can be assumed as infinity i.e. D[w] =∞. Furthermore, let us consider that there are no edges in the digraph and every edge s starts its computation for the shortest path cost D[w] to connect to (V-s), with a minimal c[s, w] value. Next, it computes the routes forאother neighbour w the other edges v ϵ (V-s-w), and is a neighbour of w, consequently the resultant equation becomes:

D[v]= min(D[v], D[w]+c[w, v])

Where c[w, v] is the vertices cost metric connected to w, the relaxing nodes process is continued until all the digraph edges are visited. On completion of the process all the edges have the shortest path to each other node in the network.

Furthermore, to make sure not to recalculate the path for visited nodes, for this purpose these edges are marked to mitigate the chance of recalculation of the path. In case there is an e number and n number of vertices in the digraph the computational complexity for the Dijikstra shortest path algorithm is:

O(e log N), and N is the number of Nodes. [Firat][F. Tekiner et al].

Dijikstra Algorithm Pseudo-code

Merin stated the Pseudo-code for Dijikstra algorithm is: which are quoted as “ Procedure Dijsktra (V: set of vertices 1... n {Vertex 1 is the source} Adj[1…n] of adjacency lists;

EdgeCost(u, w): edge - cost functions;)

Var: sDist[1…n] of path costs from source (vertex 1); {sDist[j] will be equal to the length of the shortest path to j}

Begin:

Initialize

{Create a virtual set Frontier to store i where sDist[i] is already fully solved} Create empty Priority Queue New Frontier;

sDist[1] ←0; {The distance to the source is zero}

Comparative Performance Study of Routing Protocols in Wireless Sensor Network

forall vertices w in V - {1} do {no edges have been explored yet} sDist[w][Abbildung in dieser Leseprobe nicht enthalten]

end for;

Fill New Frontier with vertices w in V organized by priorities sDist[w]; End Initialize;

repeat

v[Abbildung in dieser Leseprobe nicht enthalten]DeleteMin{New Frontier}; {v is the new closest; sDist[v] is already correct} for all of the neighbors w in Adj[v] do

if sDist[w]>sDist[v] +EdgeCost(v,w) then sDist[w][Abbildung in dieser Leseprobe nicht enthalten]sDist[v] +EdgeCost(v,w)

update w in New Frontier {with new priority sDist[w]} endif (end of?)

endfor (one word or two?)

until New Frontier is empty”. [Merin].

2.6.1.2. Related Algorithm

1. A* Algorithm

A star is an algorithm from a graph tree class and it computes the path from a source node to a destination node and for the computation of a path it uses a heuristics estimate h(x). It computes the best path to a given node on the basis of these estimates. It visits every node to find the best path to fulfil the heurists estimate criteria.

2. Prime Algorithm

A prime algorithm is also termed a DJP algorithm. I, it computes the minimum shortest path in a connected weighted graph. It works on the concept of searching for subset edges that to make a tree in order to minimize total weighted edges in the tree. [Merin]

2.7. Enhanced Interior Gateway Routing Protocol (EIGRP)

EIGRP is an interior gateway routing protocol and was developed by Cisco. The EIGRP protocol is built on the basis of a Diffusion Update Algorithm (DUAL). EIGRP does optimization in terms of topological changes, computational power and memory consumption.

EIGRP Tables

Neighbours Table: In this table it stores the routing information associated with their close neighbours interface.

Advantages

i. Provides a fast convergence mechanism
ii. Guaranteed loop-free routing path

Diffusion Update Algorithm (DUAL)

J.J.Garcia Luna Aceves developed the DUAL algorithm at the Stanford Research Institute. The DUAL algorithm has the capability to respond dynamically to topological changes and automatically adjust the routing table entries on each individual router. The DUAL algorithm performs diffusion computation and guarantee loop free routing.

2.7.1. Link-state-based Routing

The link state routing algorithm is the replacement of the distance vector routing algorithm in the early 1970’s by ARPANET. Distance vector routing has suffered from two major problems which are delays and count-to-infinity problems. Today, a number of variants of the link state routing algorithm are widely deployed in internetworks.

Tenanbuam describes central points and the philosophy of the link state algorithm as, First, LS algorithms discover the location of the neighbour node and like to learn their address.

Second, calculate the cost or delay to each of its neighbours.

Third, to build a packet and inform the other neighbours what it has learned. Fourth, distribute the packet to all other neighbour routers. Fifth, calculate the shortest path to each neighbour. ink state routing algorithm works on a mechanism, a router or node advertising its local links to its neighbour unlike the distance vector algorithm’s incremental distance computation.

Furthermore, the link state algorithm uses a topological database. It is also termed as a routing table. The topological database is the core source for network mapping; it further forms a graph of the interconnected networks. In the graph each node and its interconnected link is represented in the network. In the network each node retains and tallies its routing table entries with the neighbour router, and attached links.[Firat]

It uses Dijikstra Shortest path algorithm for the least cost path computation, and looks after the routing table or topological database. In regards to LSA exchanges it uses a static algorithm called flooding; it sends the incoming packets to each outgoing link except its own link. The known disadvantage of the conventional flooding algorithm is the duplication of packets; an alternative technique for more practical flooding is also used and is called ‘selective flooding’. [Tenanbuam].

Link-state Routing Protocols Pseudo-code

Firtat et al (No reference?) describes the pseudo-code for the link state algorithm which is quoted as,

Set Dij to infinity for all j not equal to i Loop N

Find the node K not in N for which Dik is smallest Add K to N

illustration not visible in this excerpt

2.8. Border Gateway Protocol (BGP) or Path Vector- based Routing

The Path vector routing algorithm was the replacement for the previous DARPANET distance vector algorithm. The core reasons for the development of the path vector algorithm were to use the vector to eradicate the problem of the loop unlike the distance vector algorithm. It belongs to a class of inter-domain routing algorithms, in relation to routing p; the border gateway protocol (BGP) is built on the base over path vector routing algorithm.

In BGP the best-path algorithm always received a multiple number of paths to the same destination, then further the best-path algorithm making decision on which path must be installed in the routing table.

Path vector algorithm mechanics

Firstly, of all BGP choose the valid path as is the best path and then further compare it with the path that comes first in the list and continue until the valid path is finished.

Next it follows the rules stated for the election of best path, which are the following: Rule 1: Pick the path with the highest weight

Rule 2: Choose the path with the highest local preference LOCAL_PREF

Rule 3: Preference will be given to the path that was locally originated via a network

Rule 4: Preference would be given to the path which has the shortest autonomous path AS_PATH

Rule 5: Preference would be given to the shortest path which has the lowest origin type

Rule 6: Preference would be given to the path which has the lowest multi-exit discriminator (MED)

Rule 7: Preference would be given to eBGP over iBGP paths

Rule 8: Preference would be given to the path which has the lowest BGP metric to the subsequent BGP hop.

Rule 9: In case of multi-path make certain that if is there is any need for installation in the IP routing table for multiple paths.

Rule 10: In a case where if both are external paths then preference would be given to the path which came first in the order.

Rule 11: Preference will be given to the path which comes from the BGP router and has the lowest router ID.

Rule 12: In the case where the router ID is similar for multi-path, then preference will be given to the path which has a minimum cluster list length.

Rule 13: Preference would be given to the path which has a lowest neighbour address. BGP beast Path selection routing algorithm flow chart representation: Limitation of Path Vector Routing Problem Analysis and measurement showed that a packet forwarding loop exists in the inter-domain routing. But the exact reason behind the looping problem has not yet been discovered because of the size and convolution of the internet. Paxion performed a number of end-to- end trace-route experiments in 1994 and 1995 and found that a transient loops exists in the internet.

2.9. Advance Routing Approaches

2.9.1. Self-Adjusting Routing Protocols

The core disadvantage of a conventional routing algorithm is that of human intervention or algorithm designer supervision in the case of some unusual event or occurrence in the operation of an algorithm such as failure or link congestion and so forth and consequently, these algorithms are not able to adjust dynamically.

Moreover, the conventional routing algorithm has a lack of intelligence and it needs human help and supervision for adjustment in problematic conditions and network topological changes.

The problems of routing have been studied in the research domain for a long time. The routing problem comes within the scope of the NP-complete problem. The problem is very similar to sale-man route optimization problem. The need for an intelligence routing algorithm to adapt and adjust changes dynamically is introduced. With this approach not only does it boost the performance presentation of an algorithm it also improves the adaptability for associated changes in the network.

With an advance learning routing approach the algorithm can automatically adopt and maintain its performance for an event which is not described by the algorithm designer. This routing learning base algorithm is more appropriate for a communication network where topological variances are unforeseen and unpredictable. Nevertheless, the introduction of this sort of algorithm involves a couple of constraints such as, more time is needed for learning and also in terms of memory storage.

2.9.1.1. Reinforcement Learning Routing Protocols

Reinforcement learning (RL) is a form of learning in which we interact with an environment by carrying out some action and as a result learn from that action. In this regard it is the opposite of the traditional teaching method. Furthermore, RL is a form of learning where an agent undertakes trial and error and trail interaction in a dynamic environment. Although, RL is an old field but it has attracted much attention in the last decade from machine learning and the artificial intelligence domain.

The central concept of RL is the methodology of an agent reward and punishment approach. There is no pre-information stored for an agent, but it learns an input from interaction with the environment and after processing the input data it returns the output to the environment. As a result the state of the environment is updated. There is a possibility that an agent may take further action, but this is totally dependent upon the input. The aforesaid methodology is very useful in a situation where there is no supervised learning for an agent.

The RL mechanism would not be called an algorithm or protocol but in reality this is a very powerful initiative for the solution of some particular class of problems. The RL methodology can be further divided into two main streams of mechanisms i.e. a genetic algorithm and genetic programming, and statistical techniques and dynamic programming. [David Kelley].

In addition, a reinforcement learning base routing algorithm does not require the preknowledge of the network topology and network traffic pattern and is even capable of working out the best routing policy without the need for any centralised routing control system. [Michael Littman et al ].

However, the approach of reinforcement learning can be very highly-priced in terms of space and storage but there are different variants of reinforcement learning algorithms available. The one that we are selecting is the Q-learning algorithm and, in terms of space, it requires a little bit more space for the representation of a full routing policy. [Michael Littman et al ].

2.9.1.1.1. Q- Routing Protocols

The Q-learning is a mechanism of solving a problem on the basis of the reinforcement learning philosophy; it is used for the solution of the problem which involves a polyhierarchy of decisions. Q-learning can also be called an incremental edition of dynamic programming for the aforesaid problem.

In relation to an adaptive routing problem, the Q-learning mechanism working in a model base make-up and the routing organizer does not have pre-knowledge of the topology in this type of environment. Meanwhile the routing organiser has the priority to minimise the average packet delivery timeframe and particularly in the case of a dynamic environment where changes always occur it is extremely difficult to work out an optimal routing policy.

In Q-routing each individual in the network is a configured Q-routing algorithm mechanism. Q-Routing Protocols Mechanics The core steps of algorithm are quoted from David Kelly’s research paper, and are as follows:

Step 1: Initialization with 0’s or random values Q(s,a) for all s S and for all a A(s)

Step 2: Reiterate for each occurrence Step 3: Initialise

Step 4: Reiterate for each step occurrence

Step 5: Choose a from s using a policy derived from Q

Step 6: Take action a, observe resultant state s’ and the reward r

Step 7: Q(s,a) Q(s,a) + [r + maxa’Q(s’,a’)- Q(s,a)] Step 8: s s’; Until s is terminal.

2.9.1.2. Ant Colony Optimization (ACO) Routing Approach

Three are numerous insects living on the surface of the earth and one of them is the ant family. Ant species’ categories are numbered at 9000. These ants have unique intelligence and smart characteristics which enable them to live in large groups in vast numbers, and they can literally be found everywhere across the globe. An Ant Colony Optimization Algorithm (ACO) is an algorithmic technique through which we can work out the reduced path in the graphs.

In the recent past, the ant’s model of organization and its associated interaction with the environment were researched and computer scientist and engineers. The focus of attention was the ant’s unique features, such as their distributed control mechanism, fault tolerance approach, environment base interactive communication, individual level automaticity, and self-organization, strategies for collectivism and cooperation and the emergence complex behaviours, and a set of unique skills at each individual ant level. The aforesaid features of the ant societies make them an inspiration for a new multi-agent system and a way forward for the developments of new algorithms.

[...]