Analysis of Routing Algorithms in Wireless Networks

Introduction

Actuality

The purpose of this work is research routing algorithms in wireless networks and, on their basis, to develop the improved algorithm. The subject is actual, thanks to fast development of the wireless networks step-by-step superseding the wire.

Scientific and practical novelty

Prospective novelty consists in refinement of existing algorithms and protocols. It should allow to reduce «the parasitic traffic» and, probably, to improve quality of selected paths. The appropriate driver for the new protocol is not planned to write yet as before implementation it is necessary to spend at first modeling and matching of efficiency with existing clones.

The main content

Routing algorithms

First, will be modeled AODV (Ad-hoc On-Demand Vector Routing[2]) protocol, which using Distance Vector algorithm. It is the reactive routing protocol, which installing the path to a target on demand (by means of sending of packages RREQ). In AODV transmission of the path information (except greeting messages) is not carried on, while there is no necessity for installation or path restoring.

Before sending of the data, the node dispatches package RREQ (inquiry of the path) to neighbors through the allowed band. Near nodes, in turn, transfer inquiry to the neighbors and so on (see fig. 1) while the package with inquiry will not reach the receiver. At transfer, intermediate nodes do a mark about the previous node (thus, registering the part of the path), and also about initial and finite items of the path. In a case if the intermediate node will receive some identical packages (that it is possible to watch under number of inquiry selected by the node so that not to be intersected with others) from them the package with the least quantity of jumps (hops) will be selected, providing thus a choice of the optimal path.

If the intermediate node already has the path to the node of assignment and flag D (to supply to the assignment node) in package RREQ is inactive, he responds a source package RREP (or dispatches RREQ to the receiver directly), confirming path installation (and doing a mark for itself in the routing table). If flag D is active, possibility usage of already known path is ignored (as the network topology varies in due course, this path could become nonoptimal, unreliable or at all disappears).

For additional confirmation package RREP-ACK dispatched by a source on receipt RREP (it can be used for path check in networks with unreliable link) can be used.

In a general view, it is possible to present the received path in the form of the coherent list (physically distributed on intermediate nodes) which each link is written in the appropriate table of routing. If flag D in inquiry about path installation is inactive, some paths can be intersected, that is their lists can contain the common chains of links (probably, this feature will be used for algorithm optimization). In the protocol following methods of struggle against the parasitic traffic are used:

• Limitation of time of a life of a package (TTL) to value of prospective number of intermediate nodes in a network;
• Limitation of frequency of repetition of sending of inquiry RREQ, in case of path corrupting (or unsuccessful search, for example, if for some time the path to the node has ceased to exist in general as that). In this case the source expects time twice larger, than it was necessary for path installation.

The protocol possesses following advantages:

• Simplicity of implementation;
• Absence of the additional traffic at transfer of the data;
• Low resource requirements.

Disadvantage of the protocol is the big installation time of the path.

DSR protocol (Dynamic Source Routing[1]), which applied in mesh networks, is similar to AODV in that it forms a route on-demand when a transmitting computer requests one (a reactive routing protocol). The main difference that DSR stores the information on the path not in routing tables, but direct in an inquiry package. The main disadvantage – substantial growth of the size of a package at long paths or addresses (in this case accumulation of addresses is disabled, and routing tables are used directly).

Modeling

In master’s work it is planned to model a wireless network, routed on modified AODV protocol and, probably, mesh-networks with DSR. The main difference of wireless networks from wire clones is badly structured and dynamically varying topology, at unreliable link between nodes.

The topology of a wireless network (for i-th instant) is usually described by the graph. As the majority of wireless networks at data transfer uses the mechanism of confirmations, link between nodes (tops of the graph) - usually two-forked. Accordingly edges of a graph can be not routed.

Also each of channels is characterized by capacity (communication quality) and way of access depending on which the channel can be carried to one of following types:

• The dedicated channel – is used for unidirectional data transfer between pair nodes, thus other nodes in a network do not have access to channel resources;
• The divided channel – is intended for unidirectional data exchange between several nodes;
• The channel of the common type – can be used both as selected, and as the divided channel.

For definition of criteria of efficiency of data exchange between nodes in a network we will consider this process from the point of view of digital mathematics and the theory of sets. Let some ‘i’ node is gathered to transfer them to the neighbor ‘j’ some message. In this case ‘i’ node should select for data transfer one of channels k, satisfying to a condition:

where

That is, the subset k is a set of channels linking these two node. Physically this subset can represent a set unengaged other nodes of radio frequencies (or bars of radio frequencies) on which link between ‘i’ and ‘j’ is possible. After clearing of one of channels of this subset (from the above-stated classification follows that the other nodes can occupy channel), the node force it in a state "is occupied" (for example, starting preamble and frame sending). Thus given channel cannot be used any of cluster nodes into which enter i and j (as physically they divide the same air). More precisely, in a cluster ‘i’ (the ether can broadcast to which this node on the given channel) transmission, and in a cluster ‘j’ (the ether in which this node can listen to the given channel) - reception cannot be carried out.

For multi-channel data transfer sending repeats several times that, naturally, leads to increase in size of the traffic really serviced by a network, in N+1 time, where N – quantity of intermediate nodes of retranslators in the path of transmission of the message.

On the basis of resulted above the description cool to enter parameter of a traffic activity which is added from a traffic activity, created by the node, and activity of the relayed traffic and is the characteristic of a stream of the data serviced by the node.

«For wireless packet-switched networks one of the major parameters is the average delay at data transfer. This parameter can be calculated as follows:

where

For a network consisting of identical devices, parameter T is to constants for all nodes and depends, basically, from length of a package and capacity of a data link.

The parameter ‘ti’ depends on intensity of serviced each i-th traffic, therefore for each node it makes sense to carry on one more additional parameter – intensity of the serviced traffic for a cluster of the given node, or shareable resource capacity factor (resources, in case them a little).»[2]

Modeling software

Input data for modeling is the graph of a network. The dynamic essence of a network will be displayed in probability characteristics (most probably, one on all channels) edges of a graph according to which for each instant capacity of an edge will vary, and also in probability of activity of the node (that is nodes in the course of modeling can be switched off or, probably to move to other cluster, in a random way). Links between nodes can vary in the course of modeling.

Also at modeling it is necessary to consider hardware features of implementation, in particular specialization of separate nodes (an access point, a router, a node).

Modeling software GUI

In GUI implementation of the following functionality is planned:

• Graph editor (it is possible, with import of the data from a XML-file)
• Modeling schedules (display load on nodes, a transfer rate of packages etc.)
• Graph and parameters editing during modelling (in a pause mode)
• Configuration of devices (MAС-адрес, IP, etc.)
• Routing protocol changing.

Modeling software IDE

Has selected Java (Eclipse IDE) because:

• It is independent of a platform
• Supports OOP
• The program can be realized in the form of an applet to a browser
• There are external resources for implementation of graphs (for example - JGraph).

Modeling software core structure

In modeling software it is planned to implement following classes:

• Node – describes the node (the linked device)
• Device – describes the communication device (device parameters, the table of links, the routing table)
  • WirelessDevice
  • AP – an access point
  • WirelessRouter
• Packet – describes a package transferred on a network.
  • RoutingPacket – the service package intended for installation of the path
  • Hello – a greeting package (it is referred at node activation, i.e. at its addition in a network)
• Link – describes link (edge) between nodes
• Net – contains the list of net points and its some characteristics
• Packets – contains the list of watched packages and their total characteristics

Modeling results

The developed software should represent statistics for different routing information protocols, at different topology that will allow to compare them (protocols in a context of topology) to developed algorithm, and to draw outputs on efficiency of application. Basically, following criteria will be used:

• Load on nodes
• Load on channels
• Delay by transmission of packages