Ad-Hoc Network

Ad-Hoc Network

Avdhesh Kumar Sharma1

M.TECH IVth Sem (CSE), Swami Vivekanand Subharti University, Meerut, U.P., India CSE Deptt, Swami Vivekananda Subharti University, Meerut, U.P., India

Abstract:

Ad-hoc network do not need any infrastructure to operate. In ad-hoc network all nodes are mobile and can be connected dynamically in an arbitrary/absolute manner. In particular they do not need a base station controlling medium access. This type of network allows for spontaneous communication without previous planning between mobile devices.

Network- A network is a set of devices often referred to as nodes connected by media links. A node can be a computer, printer or any other device capable of sending or receiving data generated by other nodes on the network.

Networks are of two types:-

1. Wired Network:- These networks are generally connected with the help of wires and cables. These networks are usually more efficient, less expansive and much faster than wireless networks

   Fig 1. Wired network

2. Wireless Network:- These networks are generally created without the use of wires although made with the help of radio frequencies in air to transmit and receive data.

   Fig 2 wireless network

   Wireless Networks are of two types:-

   1. Infrastructure Network:- Infrastructure network consist of a network with fixed and wired gateways. A mobile host communicates with a bridge in the network (called base station) within its communication radius. The mobile unit can move geographically while it is communicating. When it goes out of range of one base station, it connects with new base station and starts communicating through it. This is called handoff. In this

      approach the base stations are fixed

      Fig 3. Infrastructure network

   2. Infrastructure Less (Ad hoc)

      Network:-

      In ad hoc networks all nodes are mobile and can be connected dynamically in an arbitrary manner. As the range of each hosts wireless transmission is limited, so to communicate with hosts outside its transmission range, a host needs to enlist the aid of its nearby hosts in forwarding packets to the destination. So all nodes of these networks behave as routers and take part in discovery and maintenance of routes to other nodes in the network. Ad hoc Networks are very useful in emergency search-and rescue operations, meetings.

      Fig 4. Infrastructure less network

      Example of infrastructure less (ad- hoc) network is Bluetooth:- Bluetooth is the best ad-hoc network for spontaneous communication between different peripherals (devices), such as mobile phones, notebooks, PDAs, etc.Each device can communicate with any other device. Within one piconet (a piconet is a collection of Bluetooth devices which are synchronized to the same hopping sequence).

      From Jochen Schiller This ad-hoc routing protocols can be divided into two categories:-

      1. Table-Driven Routing Protocols: In table driven routing protocols, consistent and up-to-date routing information to all nodes is maintained at each node.

         Example:-DSDV.DSR

      2. On-Demand Routing Protocols: In On-Demand routing protocols, the routes are created as and when required. When a source wants to send to a destination, it invokes the route discovery mechanisms to find the path to the destination.

Example:-AODV, TORA

Various protocols used in ad-hoc network are:-

1. DSDV (Destination Sequenced Distance Vector):- Destination Sequenced Distance Vector is a Proactive routing protocol that solves the major problem associated with the Distance Vector routing of wired networks i.e., Count to-infinity, by using Destination sequence numbers.

   Destination sequence number is the sequence number as originally stamped by the destination. The DSDV protocol requires each mobile station to advertise, to each of its current neighbors, its own routing table (for instance, by broadcasting its entries). The entries in this list may change fairly dynamically over time, so the advertisement must be made

   f

   fig 5. DSDV network

   often enough to ensure that every mobile computer can almost always locate every other mobile computer. In addition, each mobile computer agrees to relay data packets to other computers upon request. At all instants, the DSDV protocol guarantees loop- free paths to each destination. Routes with more recent sequence numbers are always preferred as the basis for making forwarding decisions, but not necessarily advertised. Of the paths with the same sequence number, those with the smallest metric will be used. The routing updates are sent in two ways: a full dump or incremental update. A full dump sends the full routing table to the neighbors and could span many packets whereas, in an incremental update only those entries from the routing table are sent that has a metric change since the last update and it must fit in a packet. When the network is relatively stable, incremental updates are sent to avoid extra traffic and full dump are relatively Infrequent. The update can be time periodic or event periodic.

   Advantages of DSDV:-

   1. DSDV protocol guarantees loop free paths.

   2. Count to infinity problem is reduced in DSDV.

   3. We can avoid extra traffic with incremental updates instead of full dump updates.

   4. Path Selection: DSDV maintains only the best path instead of maintaining multiple paths to every destination.

      Limitations of DSDV:-

      1. Wastage of bandwidth due to unnecessary advertising of routing information even if there is no change in the network topology.

      2. DSDV doesnt support Multi path

         Routing.

      3. It is difficult to determine a time delay for the advertisement of routes.

      4. It is difficult to maintain the routing tables advertisement for larger network.

2. DSR (Dynamic Source Routing):- Dynamic Source Routing is a reactive protocol i.e. it doesnt use periodic advertisements. It computes the routes when necessary and then maintains them. Source routing is a routing technique in which the

   sender of a packet determines the complete sequence of nodes through which the packet has to pass; the sender explicitly lists this route in the packets header, identifying each forwarding hop by the address of the next node to which to transmit the packet on its way to the destination host.

   There are two significant stages in working of DSR:

   Route Discovery and Route Maintenance. A host initiating a route discovery broadcasts a route request packet which may be received by those hosts within wireless transmission range of it. The route request packet identifies the host, referred to as the target of the route discovery, for which the route is requested. If the route discovery is successful the initiating host receives a route reply packet listing a sequence of network hops through which it may reach the target. In addition to the address of the original initiator of the request and the target of the request, each route request packet contains a route record, in which is accumulated a record of the sequence of ops taken by the route request packet as it is propagated through the network during this route discovery. While a host is using any source route, it monitors the continued correct operation of that route. This monitoring of the correct operation of a route in use is called route maintenance. When route maintenance detects a problem with a route in use, route discovery may be used again to discover a new, correct roue to the

   destination. To optimize route discovery process, DSR uses cache memory efficiently. from Wikipedia.

3. AODV (Ad-hoc On Demand Distance Vector). Ad hoc On- demand Distance Vector is essentially a combination of both DSR and DSDV. It borrows the basic on-demand mechanism of Route Discovery and Route Maintenance from DSR, plus the use of hop-by-hop routing, sequence numbers, and periodic beacons from DSDV. It uses destination sequence numbers to ensure loop freedom at all times and by avoiding the Bellman-Ford count-to-infinity problem offers quick convergence when the ad hoc network topology changes Route Requests (RREQ s), Route Replies (RREP s), and Route Errors (RERR s) are the message types defined by AODV. These message types are received via UDP, and normal IP header processing applies. As long as the endpoints of a communication connection have valid routes to each other, AODV does not play any role. When a route to a new destination is needed, the node broadcasts a RREQ to find a route to the destination. A route can be determined when the RREQ reaches either the destination itself, or an intermediate node with a 'fresh enough' route to the destination. A 'fresh enough' route is a valid route entry for the destination whose associated sequence number is at least as

   great as that contained in the RREQ. The route is made available by uncasing a RREP back to the origination of the RREQ. Each node receiving the request caches a route back to the originator of the request, so that the RREP can be uncast from the destination along a path to that originator, or likewise from any intermediate node that is able to satisfy the request. If intermediate nodes reply to every transmission of a given RREQ, the destination does not receive any copies of it. In this situation, the destination does not learn of a route to the originating node. In order that the destinations learn of routes to the originating node, the originating node SHOULD set the gratuitous RREP ('G') flag in the RREQ if for any reason the destination is likely to need a route to the originating node. If in response to a RREQ with the 'G' flag set, an intermediate node returns a RREP, it MUST also uncast a gratuitous RREP to the destination node. Nodes monitor the link status of next hops in active routes. In order to maintain routes.

   AODV normally requires that each node periodically transmit a HELLO message, with a default rate of once per every second. Failure to receive three consecutive HELLO messages from a neighbor is taken as an indication that the link to the neighbor in question is down. When a link break in an active route is detected, a RERR message is used to notify other nodes that

   the loss of that link has occurred. The RERR message indicates those destinations which are now unreachable due to the loss of the link. In order to enable this reporting mechanism, each node keeps a precursor list, containing the IP address for each of its neighbors that are likely to use it as a next hop towards the destination that is now unreachable.

   Fig 6. AODV network

   Advantages of AODV:-

   1. Minimal space complexity:

   2. Maximum utilization of the bandwidth.

      Limitations/Disadvantages of AODV:-

      1. Requirement on broadcast medium:- The algorithm expects/requires that the nodes in the broadcast medium can detect each others broadcasts

      2. It is vulnerable to misuse:-

         The messages can be misused for insider attacks including route disruption, route invasion, node isolation, and resource consumption.

      3. It is too expensive from google.co.in

4. TORA (Temporally- Ordered Routing Algorithms):- The Temporally- Ordered Routing Algorithm is an adaptive routing protocol for Multi hop networks that possesses the following attributes:

Distributed execution

Multipath routing

The protocol can simultaneously support both source-initiated, on- demand routing for some destinations and destination- initiated, proactive routing for other destinations.

Minimization of communication overhead via localization of algorithmic reaction to topological changes

TORA is distributed, in that routers need only maintain information about adjacent routers (i.e., one-hop knowledge). Like a distance-vector routing approach, TORA maintains state on a per-destination basis. However, TORA does not continuously execute a shortest- path computation and thus the metric used to establish the routing structure does not represent a distance. Invented by Vincent Park and M.Scott Corson from University of Maryland.

TORA essentially performs three tasks:-

1. Creation of a route from a source to a destination.

2. Maintenance of the route.

3. Erasure of the route when the route is no longer valid.

4. TORA attempts to build what is known as a directed acyclic graph (DAG) which is rooted at the destination.

The logically separate version of TORA is run for each destination to which routing is required. The TORA link reversal process creates short-lived routing loops that exist from the time that the ling-reversal starts until the time that all nodes that need to be aware of the reversal receive the corresponding update.

References:-

1. Charles E. Perkins. Ad hoc Wireless Networking, ADDISON WESLEY, 2001.

2. Andrew S. Tenenbaum. Computer Networks, 4Th Edition. PRENTICE HALL, 2002.

3. Jochen Schiller, Mobile Communications, PEARSON EDUCATION, 2003.

4. C.Siva Ram Murthy and B.S. Manoj.Ad hoc Wireless Networks Architecture and Protocols. PRENTICE HALL, 2004.

5. http://google.co.in

6. http://wikipedia.com