Institut für Betriebssysteme und RechnerverbundTechnische Universität Braunschweig

Multi hop Connectivity in Mobile Ad hoc Networks (MANETs)

Habib-ur Rehman

2/17Multi hop Connectivity in Mobile Ad hoc Networks (MANETs)

Habib-ur Rehman

Multi hop Connectivity

Multi hop connectivity is solved for wired networks long ago

Multi hop connectivity for wireless networks is also not new Many routing protocols like AODV, DSDV, DSR, TBRF etc. Still no widely accepted solution as we have in wired networks

Problem Analysis Ad hoc 802.11 MAC Future Plans

3/17Multi hop Connectivity in Mobile Ad hoc Networks (MANETs)

Habib-ur Rehman

Proactive vs. Reactive

Routing in MANETs Proactive routing protocols

– maintain consistent and up-to-date information about the network by constantly exchanging routing information among nodes

Reactive routing protocols– initiate an independent route discovery process whenever a source

node requires a route to some destination

Reactive approaches have less overhead but require more time to connect source and destination Reactive is preferable-more suits to low resource nature Reactive route discovery requires some attention

Problem Analysis Ad hoc 802.11 MAC Future Plans

4/17Multi hop Connectivity in Mobile Ad hoc Networks (MANETs)

Habib-ur Rehman

On-demand behavior in AODV

On-demand Features An approach based only on reaction to the offered traffic A reactive protocol might have some proactive (not on-demand)

features– In AODV, during the route discovery process, if an in-valid route

entry is already present in the routing table, the value of TTL field in the RREQ packet’s IP header is initially set to the hop count value in that entry.

In AODV which is a reactive protocol, dependency on proactive features or stale information is not beneficial

Problem Analysis Ad hoc 802.11 MAC Future Plans

5/17Multi hop Connectivity in Mobile Ad hoc Networks (MANETs)

Habib-ur Rehman

On-demand behavior in AODV

In these simulations AODV with a reduced proactive feature vs. AODV

– Initial value of TTL field will not depend on existing stale entry

AODV with additional proactive feature vs. AODV– Sharing of additional route information

S I1Knows (S)

I2Knows (S,

I1)

InKnows (S, In-1)

I3Knows (S,

I2)

Problem Analysis Ad hoc 802.11 MAC Future Plans

Learning during Route Discovery

S I1I2

Add entryfor (I1)

InAdd entryfor (I1,…,

In-1)

I3Add entryfor (I1, I2)

6/17Multi hop Connectivity in Mobile Ad hoc Networks (MANETs)

Habib-ur Rehman

On-demand behavior in AODV

Simulation Results NS2.28 with AODV-UU 100 nodes 40 and 80 source/destination

pairs Node speed 1 m/sec Pause Time 0 seconds CBR sources UDP packets of 1024 Bytes

Problem Analysis Ad hoc 802.11 MAC Future Plans

7/17Multi hop Connectivity in Mobile Ad hoc Networks (MANETs)

Habib-ur Rehman

Some other Issues

Broadcast transmissions Used extensively in both Proactive and Reactive protocols for

maintaining routing tables Is just not affordable No RTS/CTS which means high risk of collision

Scalability is the major problem in ad hoc networks Number of nodes Amount of mobility Offered load

Problem Analysis Ad hoc 802.11 MAC Future Plans

8/17Multi hop Connectivity in Mobile Ad hoc Networks (MANETs)

Habib-ur Rehman

Ad hoc 802.11 MAC

A multi hop extension for IEEE 802.11 MAC header

It is a reactive or on-demand in nature

Exploit the normal MAC operations– No special route/destination request packet/frame

– No special route/destination reply packet/frame

Exploits the use of data frame for destination discovery– reduce the delay for connecting source to destination

Problem Analysis Ad hoc 802.11 MAC Future Plans

9/17Multi hop Connectivity in Mobile Ad hoc Networks (MANETs)

Habib-ur Rehman

Modifications to 802.11 MAC

Additions to MAC header: Multi hop Data Frame (MDF) Address1 = Recipient Address (RA) Address2 = Transmitter Address (TA) Address3 = Destination Address (DA) Address4 = Source Address (SA) An additional 2 Bytes cost field

– Hop count

Problem Analysis Ad hoc 802.11 MAC Future Plans

Octets

FCSFrame Body

Address 4

SASequence Control

Address 3

DAAddress 2

TAAddress 1

RADuration / ID

Frame Control

40-23126266622

Octets

Cost

2

DS A BRA TA DA SAA S D S

RA TA DA SAD B D S

RA TA DA SAB A D S

10/17Multi hop Connectivity in Mobile Ad hoc Networks (MANETs)

Habib-ur Rehman

Modifications to 802.11 MAC

A Forwarding Table is maintained by each node Destination Address (6 Bytes) Next Hop (6 Bytes) Cost (2 Byte)

All 802.11 frames carry unique sequence number and fragment number in sequence control field (SCF) Nodes maintain a list of MAC address (sender/TA) and SCF

value pairs In Ad hoc 802.11 MAC, original sender is SA and not the TA

therefore in SCF list SAs should be stored

Problem Analysis Ad hoc 802.11 MAC Future Plans

11/17Multi hop Connectivity in Mobile Ad hoc Networks (MANETs)

Habib-ur Rehman

Protocol Components

Three main components Learning Forwarding Repair

Learning: learning about accessible nodes Whenever a node receives a multi hop data frame

– It adds entries in FWT for TA and SA of the frame if there is no entry for either of them

– If there is already an entry for either, this entry will be updated A repair operation will be performed if the cost of previously stored path

is less than the new path

Problem Analysis Ad hoc 802.11 MAC Future Plans

12/17Multi hop Connectivity in Mobile Ad hoc Networks (MANETs)

Habib-ur Rehman

Protocol Components

Forwarding Originating data frames

– If there is an entry for DA in FWT TA would be the next hop in this entry

– Else TA would be broadcast Relaying frames for other nodes

– If DA is broadcast and SCF is new Broadcast it once again

– If DA is uni-cast and SCF is new Follow same steps as in originating

– Frames carrying old SCF will always be dropped

Problem Analysis Ad hoc 802.11 MAC Future Plans

13/17Multi hop Connectivity in Mobile Ad hoc Networks (MANETs)

Habib-ur Rehman

Protocol Components

Repair Responsible for identifying anomalies in FWTS Also share information about these anomalies with other nodes Path Repair Frame (PRF)

– A multi hop data frame with no data in frame body

Problem Analysis Ad hoc 802.11 MAC Future Plans

Octets

FCSCostSASequence ControlDATARA

Duration / ID

Frame Control

426266622

14/17Multi hop Connectivity in Mobile Ad hoc Networks (MANETs)

Habib-ur Rehman

Protocol Components

Possible situations for Repair operation A node receives a data frame addressed to itself with RA as a

broadcast address– A path repair frame will be sent

RA in this frame would be broadcast SA and DA will be copied from the data frame just received The cost field will carry the SCF value of the data frame just received

A node receives a data frame addressed to itself through a path which has higher cost than a path already known to it

– A path repair frame will be sent to SA on the previously (low cost) known path

A node receives a data frame with RA as broadcast– A path repair frame will be sent to TA if DA is known

Problem Analysis Ad hoc 802.11 MAC Future Plans

15/17Multi hop Connectivity in Mobile Ad hoc Networks (MANETs)

Habib-ur Rehman

Some Results

25 Nodes 10 and 20

Source/Destination pairs Speed 1 m/sec Pause Time 0 seconds 4 packets of 1024 bytes per

second generated by each source. Max 10000 packets

CBR sources generating UDP packets

Normalized MAC overhead(Bytes)

0

500

1000

1500

2000

2500

3000

Byt

es

10 connections 20 connections

Problem Analysis Ad hoc 802.11 MAC Future Plans

Packet Delivery Ratio

0

0.1

0.2

0.3

0.4

0.5

0.6

0.7

0.8

0.9

1

10 connections 20 connections

Average End to End Delay for First Packet

0

0.5

1

1.5

2

2.5

3

3.5

Sec

on

ds

10 connections 20 connections

16/17Multi hop Connectivity in Mobile Ad hoc Networks (MANETs)

Habib-ur Rehman

Future Work

The initial simulation results show that scalability could be a big challenge A detailed analysis of network size, mobility, offered load

Detailed analysis of different components and their effects on performance

Comparison with other well known routing protocols Possibility of different cost metrics

Problem Analysis Ad hoc 802.11 MAC Future Plans

Institut für Betriebssysteme und RechnerverbundTechnische Universität Braunschweig

Thanks for your attention

Habib-ur Rehman