Mobile Computing - Chapter 4: Mobile Ad-hoc Network

Mobile Ad-hoc Network

MANET Characteristics

• Every node functions as a router.

• Nodes move arbitrarily, resulting in a dynamic network topology.

• Wireless connectivity limits the network's bandwidth and capacity.

• Advantages:

  • Easy and fast deployment.

  • Robust and low-cost.

  • Forms the basis for pervasive and ubiquitous computing.

• Applications: PANs (cell phones, laptops, wearable computers).

MANETs Classification

Ad-hoc networks are classified based on coverage area:

BAN (Body Area Network):

1. Correlated with wearable computers.

2. Components are distributed on the body, providing connectivity among devices.

3. Main requirement: interconnecting heterogeneous devices (mobile phones, microphones, displays, wearable computers).

4. Communication range: approximately 1 to 2 meters.

PAN (Personal Area Network):

• Network in the person's environment; BAN is dedicated to interconnecting one person via wearable devices.

1. Communication range: 10 meters.

2. Connects mobile devices carried by users to other mobile and stationary devices.

WLANs (Wireless Local Area Network):

1. Greater flexibility compared to wired LANs.

2. Communication range typical of a single building or a cluster of buildings.

3. Range: 100 – 500 meters.

MANETs Routing Protocol Expectations:

4. Tolerance of unexpected network faults.

5. Resilience to increasing traffic loads.

6. Minimal energy consumption.

Traditional Routing Protocols

Wired networks routing protocols have two types:

Distance Vector Routing Protocols:

• Routing tables are exchanged between neighboring nodes.

• Routes are obtained by comparing distances to destinations and computing the shortest path to each host, e.g., RIP.

Link State Routing Protocols:

• Neighboring nodes exchange link states only.

• Routes are obtained by computing a graph of the most recent network topology, independently on every participating node, and computing the shortest distance to each host, e.g., Open Shortest Path First (OSPF).

Requirements for Routing Protocols

1. Operate in a distributed, multi-hop, and loop-free manner for best results.

2. Operate in a demand-based mode (reactive or proactive) because of rapid topology changes.

3. Should be scalable.

4. Provision for a 'sleepy period'.

5. Support unidirectional links.

6. Security.

Two basic parts to the routing protocols:

1. Route discovery: required frequently due to high node mobility.

• Route maintenance: required for the same reason and due to noise, interference, link breakage, etc.

Classification of Routing Protocols

Routing protocols can be classified as unicast or multicast.

• Unicast routing protocols are general protocols that use position information.

• The general protocols are proactive, reactive, and hybrid.

Proactive Routing Protocols:

• Calculate all possible paths in the network independently of their use.

  • Advantage: When a packet needs to be forwarded, the path is already known and can be used immediately.

Reactive Routing Protocols:

• Source-initiated on-demand routing protocols that invoke the route determination procedure only on demand.

Hybrid Routing Protocols:

• Merges the features of proactive and reactive protocols.

Proactive Routing Protocols - The DSDV Protocol

• The most popular proactive routing protocol is the destination-sequenced distance vector routing protocol (DSDV).

• This is a table-driven algorithm based on the classical Bellman-Ford distance vector routing algorithm used for wired networks.

• Improvements include freedom from loops in routing tables.

There are four distinct phases in DSDV:

Route Advertisements:

• Every mobile node maintains a routing table with all possible destinations and the number of hops to each destination.

• Each entry is marked with a sequence number assigned by the destination node.

Routing Table Entry Structure:

The data broadcast by each mobile node contains the new sequence number and the following information for each new route:

• The destination address

• Number of hops required to reach the destination

• Sequence number of the information received

Responding to Topology Changes:

To maintain the consistency of routing tables in a dynamically varying topology, routing table updates are periodically transmitted by a mobile node to each of its current neighbors in the network.

• Updates are transmitted immediately when significant new information is available.

• To help reduce the potentially large amount of network traffic that such updates can generate, two possible types of packets are used:

  • Full dumps: carry all available routing information and can require multiple NPDUs (network protocol data units).

  • Incremental dumps: relay only that information that has changed since the last full dump and fit in one network protocol data unit (NPDU) only.

Route Selection Criteria:

When a mobile host receives new routing information through an incremental packet, it compares it to that already available from previous routing packets.

• The more recent sequence number is used & old sequence numbers are discarded.

Reactive Routing Protocols

• Reactive routing protocols maintain routing information about 'active' routes only.

• Routes are created when desired by the Source node.

• Protocols are known as on-Demand routing protocols.

• Route discovery procedure is needed before data transmission.

• Examples of RRP are

  • Dynamic source routing (DSR)

  • Adaptive on-demand vector (AODV)

  • Temporarily ordered routing algorithm (TORA)

Dynamic Source Routing - DSR

• DSR is an example of a reactive routing protocol that does both route discovery and route maintenance.

• Source routing is a routing technique in which the sender of a packet determines the complete sequence of nodes through which to forward a packet.

• Sender explicitly lists the route in the packet's header, identifying each forwarding 'hop' by the address of the next node.

• Each router maintains a route cache.

  • If a route is found, the sender uses it to transmit the packet; else, it may attempt to discover a route using the Route Discovery Protocol.

  • If any intermediate host moves out of the transmission range, the route can no longer be used to reach the destination.

• Route maintenance: monitoring of the correct operation of a route is called route maintenance.

Route Discovery in DSR

• When a node A wants to route packets to a destination E, it first searches its Route Cache to see if any route is available. If not, it initiates a discovery process.

• A transmits a ROUTE REQUEST message as a single “local broadcast” packet.

• All nodes within wireless range receive this packet.

• ROUTE REQUEST packet includes initiator ID and request ID.

• Route record, which includes intermediate nodes, is embedded into the packet.

• When the target of the route discovery receives this, it responds with a ROUTE REPLY message.

• The initiator caches this route and uses it for routing subsequent packets.

• If an intermediate node receives a route request and notices that its address is already listed in the route record, it discards the request.

• Upon receiving the route request, E will first look in its cache to see if there is a route to A.

• If no route is found, it might perform its own Route Discovery.

Route Maintenance in DSR

• Link layer reliability: A is responsible for the packet reaching B, B is responsible for the packet reaching C, and so on.

• MAC layer ack or passive overhearing – example: B overhears C’s transmission to D.

• If a packet is re-transmitted a maximum number of times across a link, but no confirmation of receipt is obtained (e.g., across C -> D), a ROUTE ERROR message is generated reporting this link is broken and sent to A.

Adaptive On-Demand Distance Vector Protocol - AODV

• AODV is a reactive, distance vector routing protocol based on the distributed Bellman-Ford routing algorithm.

• AODV also attempts to improve on DSR by maintaining routing tables at the nodes, so that data packets do not have to contain routes.

• Like DSR, a node wanting to send a packet must first discover a route to that destination.

• A route discovery procedure is required.

Route Discovery in AODV

• Route Requests (RREQ) are forwarded in a manner similar to DSR.

• When a node re-broadcasts a RREQ, it sets up a reverse path pointing towards the source.

• This is so that the RREP can get back to the source.

• When the intended destination receives a RREQ, it replies by sending a RREP.

• RREP travels along the reverse path set up when RREQ is forwarded.

Route Maintenance in AODV

• A path being used is called an active path.

• Movements that are not along any active path do not trigger any protocol action.

• If the source node moves, it can reinitiate route discovery to re-establish the connection to the destination.

• When either the destination or some intermediate node moves, a RERR message is sent to the affected source nodes.

• This RERR message is initiated by the nodes upstream of the failed link (as in DSR).

• The RERR message would list the destinations that are now unreachable.

• If the node upstream of the break has one or more precursor nodes for the destination, it broadcasts the RERR message to those nodes.

• This message now propagates towards the source.

• When the source receives the RERR, if it still needs to reach the destination, it can re-initiate route discovery.

Comparison between DSR and AODV

• AODV shows fairly stable results even after increasing the number of sources.

• DSR is based on a source routing mechanism, whereas AODV uses a combination of DSR & DSDV.

• DSR has less routing overhead than AODV.

• AODV has less normalized MAC overhead than DSR.

• AODV has better performance than DSR in higher-reliability scenarios.

• DSR has less frequent route discovery process than AODV.

Hybrid Routing Protocol

• A Hybrid Routing protocol has the advantages of both Distance Vector and Link State RPs and merges them into a new protocol.

• Typically, hybrid routing protocols are based on a Distance Vector protocol but contain many of the features and advantages of Link State RPs.

• EIGRP (Enhanced Interior Gateway RP).