Mobile Ad Hoc Networking

Carlos Cordeiro & Dharma Agrawal

OBR Research Center for Distributed and Mobile Computing
University of Cincinnati – USA

http://www.ececs.uc.edu/~cordeicm
cordeicm@ececs.uc.edu

Acknowledgments

g Some figures and slides were taken from Nitin

Vaidya’s MobiCom’2000 tutorial

1
 Course Outline

g Introduction
g Unicast routing
g Multicast routing
g Medium Access Control
g Sensor Networks
g Standards activities
g Open problems

Notes

g Only most important features of various schemes are

typically discussed
iThe concepts covered here enable you to understand any
protocol

g Most schemes include many more details, and

optimizations
iCourse handout has most details and references

2
 Mobile Ad Hoc Networks (MANET)

Introduction and Generalities

Traditional Cellular Network

g Single hop wireless connectivity to the wired world

iSpace divided into cells, where a base station is responsible
to communicate with hosts in its cell
iMobile hosts can change cells while communicating
iHand-off occurs when a mobile host starts communicating
via a new base station

MH
BS

Cell

MSC VLR
HLR 6

3
 Mobile Ad hoc NETworks (MANET)

g Formed by wireless hosts which may be mobile

g Without (necessarily) using a pre-existing

infrastructure

g Routes between nodes may potentially contain

multiple hops

Mobile Ad hoc NETworks (MANET)

g May need to traverse multiple links to reach a

destination

4
 Mobile Ad hoc NETworks (MANET)

g Mobility causes route changes

Why Ad Hoc Networks ?

g Setting up of fixed access points and backbone

infrastructure is not always viable
iInfrastructure may not be present in a disaster area or war
zone
iInfrastructure may not be practical for short-range radios;
Bluetooth (range ~ 10m)

g Ad hoc networks:
iDo not need backbone infrastructure support
iAre easy to deploy
iUseful when infrastructure is absent, destroyed or
impractical

10

5
 Many Applications

g Personal area networking (PAN)

icell phone, laptop, ear phone, wrist watch
g Military environments
isoldiers, tanks, planes
g Civilian environments
itaxi cab network
imeeting rooms
isports stadiums
iboats, small aircraft
g Emergency operations
isearch-and-rescue
ipolicing and fire fighting

11

Challenges in Mobile Environments

g Limitations of the Wireless Network

ipacket loss due to transmission errors
ivariable capacity links
ifrequent disconnections/partitions
ilimited communication bandwidth
ibroadcast nature of the communications

g Limitations Imposed by Mobility

idynamically changing topologies/routes
ilack of mobility awareness by system/applications

g Limitations of the Mobile Computer

ishort battery lifetime
ilimited capacities
12

6
 Effect of Mobility on the Protocol Stack

g Application
inew applications and adaptations
g Transport
icongestion and flow control
g Network
iaddressing and routing
g Link
imedia access and handoff
g Physical
itransmission errors and interference

13

Assumption

g Unless stated otherwise, fully symmetric (bi-

directional) environment is assumed implicitly

MH3
MH2
Symmetric link
Asymmetric link
MH1

14

7
 Routing in MANET

15

Routing Protocols
g Proactive (Table-driven) protocols
iTraditional distributed shortest-path protocols
iMaintain routes between every host pair at all times
iBased on periodic updates; High routing overhead
iExample: DSDV (destination sequenced distance vector)

g Reactive (On-Demand) protocols

iDetermine route if and when needed
iSource initiates route discovery
iExample: DSR (dynamic source routing)

g Hybrid protocols
iAdaptive; Combination of proactive and reactive
iExample : ZRP (zone routing protocol)
16

8
 Protocol Trade-offs

g Proactive protocols
iAlways maintain routes
iLittle or no delay for route determination
iConsume bandwidth to keep routes up-to-date
iMaintain routes which may never be used

g Reactive protocols
iLower overhead since routes are determined on demand
iSignificant delay in route determination
iEmploy flooding (global search)
iControl traffic may be bursty

g Which approach achieves a better trade-off depends on the

traffic and mobility patterns
17

Hop-by-Hop Routing
Dest. Next Hop #Hops Dest. Next Hop #Hops Dest. Next Hop #Hops
D A 3 D B 2 D D 1

Routing tables
S A B D on each node

Data D

g Routing table on each node = Hop-by-hop routing

g Data packet has only the destination address

18

9
 Source Routing

S A B D

Data S-A-B-D

g In source routing, the data packet has the complete

route (called source route) in the header
g Typically, the source node builds the whole route
g The data packet routes itself

19

Unicast Routing
in
Mobile Ad Hoc Networks

20

10
 Reactive (On-Demand) Routing Protocols

21

Dynamic Source Routing (DSR) [Johnson96]

g When node S wants to send a packet to node D, but

does not know a route to D, node S initiates a route
discovery

g Source node S floods Route Request (RREQ)

g Each node appends own identifier when forwarding

RREQ

22

11
 Route Discovery in DSR
Y

Z
S E
F
B
C M L
J
A G
H D
K
I N

Represents a node that has received RREQ for D from S

23

Route Discovery in DSR

Y
Broadcast transmission

[S] Z
S E
F
B
C M L
J
A G
H D
K
I N

Represents transmission of RREQ

[X,Y] Represents list of identifiers appended to RREQ 24

12
 Route Discovery in DSR
Y

Z
S [S,E]
E
F
B
C M L
J
A [S,C] G
H D
K
I N

• Node H receives packet RREQ from two neighbors:

potential for collision
25

Route Discovery in DSR

Y

Z
S E
F [S,E,F]
B
C M L
J
A G
H D
[S,C,G] K
I N

• Node C receives RREQ from G and H, but does not forward

it again, because node C has already forwarded RREQ once
26

13
 Route Discovery in DSR
Y

Z
S E
F [S,E,F,J]
B
C M L
J
A G
H D
K
I [S,C,G,K] N

• Nodes J and K both broadcast RREQ to node D

• Since nodes J and K are hidden from each other, their
transmissions may collide 27

Route Discovery in DSR

Y

Z
S E
[S,E,F,J,M]
F
B
C M L
J
A G
H D
K
I N

• Node D does not forward RREQ, because node D

is the intended target of the route discovery
28

14
 Route Discovery in DSR

g Destination D on receiving the first RREQ, sends a

Route Reply (RREP)

g RREP is sent on a route obtained by reversing the

route appended to received RREQ

g RREP includes the route from S to D on which RREQ

was received by node D

29

Route Reply in DSR

Y

Z
S RREP [S,E,F,J,D]
E
F
B
C M L
J
A G
H D
K
I N

Represents RREP control message

30

15
 Dynamic Source Routing (DSR)

g Node S on receiving RREP, caches the route

included in the RREP

g When node S sends a data packet to D, the entire

route is included in the packet header
ihence the name source routing

g Intermediate nodes use the source route included in

a packet to determine to whom a packet should be
forwarded

31

Data Delivery in DSR

Y

DATA [S,E,F,J,D] Z
S E
F
B
C M L
J
A G
H D
K
I N

Packet header size grows with route length

32

16
 DSR Optimization: Route Caching

g Each node caches a new route it learns by any

means
g When node S finds route [S,E,F,J,D] to node D, node
S also learns route [S,E,F] to node F
g When node K receives Route Request [S,C,G]
destined for node D, node K learns route [K,G,C,S] to
node S
g When node F forwards Route Reply RREP
[S,E,F,J,D], node F learns route [F,J,D] to node D
g When node E forwards Data [S,E,F,J,D] it learns
route [E,F,J,D] to node D
g A node may also learn a route when it overhears
Data
g Problem: Stale caches may increase overheads 33

Dynamic Source Routing: Advantages

g Routes maintained only between nodes who need to

communicate
ireduces overhead of route maintenance

g Route caching can further reduce route discovery

overhead

g A single route discovery may yield many routes to the

destination, due to intermediate nodes replying from
local caches

34

17
 Dynamic Source Routing: Disadvantages
g Packet header size grows with route length due to
source routing

g Flood of route requests may potentially reach all

nodes in the network

g Potential collisions between route requests

propagated by neighboring nodes
iinsertion of random delays before forwarding RREQ

g Increased contention if too many route replies come

back due to nodes replying using their local cache
iRoute Reply Storm problem

g Stale caches will lead to increased overhead 35

Ad Hoc On-Demand Distance Vector Routing

(AODV) [Perkins99Wmcsa]
g DSR includes source routes in packet headers

g Resulting large headers can sometimes degrade

performance
iparticularly when data contents of a packet are small

g AODV attempts to improve on DSR by maintaining

routing tables at the nodes, so that data packets do
not have to contain routes

g AODV retains the desirable feature of DSR that

routes are maintained only between nodes which
36
need to communicate

18
 AODV

g Route Requests (RREQ) are forwarded in a manner

similar to DSR

g When a node re-broadcasts a Route Request, it sets

up a reverse path pointing towards the source
iAODV assumes symmetric (bi-directional) links

g When the intended destination receives a Route

Request, it replies by sending a Route Reply

g Route Reply travels along the reverse path set-up

when Route Request is forwarded 37

Route Requests in AODV

Y

Z
S E
F
B
C M L
J
A G
H D
K
I N

Represents a node that has received RREQ for D from S

38

19
 Route Requests in AODV
Y
Broadcast transmission

Z
S E
F
B
C M L
J
A G
H D
K
I N

Represents transmission of RREQ

39

Route Requests in AODV

Y

Z
S E
F
B
C M L
J
A G
H D
K
I N

Represents links on Reverse Path

40

20
 Reverse Path Setup in AODV
Y

Z
S E
F
B
C M L
J
A G
H D
K
I N

• Node C receives RREQ from G and H, but does not forward

it again, because node C has already forwarded RREQ once
41

Reverse Path Setup in AODV

Y

Z
S E
F
B
C M L
J
A G
H D
K
I N

42

21
 Reverse Path Setup in AODV
Y

Z
S E
F
B
C M L
J
A G
H D
K
I N

• Node D does not forward RREQ, because node D

is the intended target of the RREQ
43

Route Reply in AODV

Y

Z
S E
F
B
C M L
J
A G
H D
K
I N

Represents links on path taken by RREP

44

22
 Forward Path Setup in AODV
Y

Z
S E
F
B
C M L
J
A G
H D
K
I N

Forward links are setup when RREP travels along

the reverse path

Represents a link on the forward path 45

Data Delivery in AODV

Y
DATA
Z
S E
F
B
C M L
J
A G
H D
K
I N

Routing table entries used to forward data packet.

Route is not included in packet header. 46

23
 Timeouts

g A routing table entry maintaining a reverse path is

purged after a timeout interval
itimeout should be long enough to allow RREP to come back

g A routing table entry maintaining a forward path is

purged if not used for a active_route_timeout interval
iif no is data being sent using a particular routing table entry,
that entry will be deleted from the routing table (even if the
route may actually still be valid)

47

Link Failure Detection

g Hello messages: Neighboring nodes periodically

exchange hello message

g Absence of hello message is used as an indication of

link failure
iWhen node X is unable to forward packet P (from node S to
node D) on link (X,Y), it generates a RERR message

g Alternatively, failure to receive several MAC-level

acknowledgement may be used as an indication of
link failure
48

24
 Summary: AODV

g Routes need not be included in packet headers

g Nodes maintain routing tables containing entries only

for routes that are in active use

g At most one next-hop per destination maintained at

each node
iDSR may maintain several routes for a single destination

49

Flooding of Control Packets

g How to reduce the scope of the route request flood ?

iLAR [Ko98Mobicom]
iQuery localization [Castaneda99Mobicom]

g How to reduce redundant broadcasts ?

iThe Broadcast Storm Problem [Ni99Mobicom]
iMore to come in subsequent slides …

50

25
Location-Aided Routing (LAR) [Ko98Mobicom]

g Exploits location information to limit scope of route

request flood
iLocation information may be obtained using GPS

g Expected Zone is determined as a region that is

expected to hold the current location of the
destination
iExpected region determined based on potentially old
location information, and knowledge of the destination’s
speed

g Route requests limited to a Request Zone that

contains the Expected Zone and location of the
sender node
51

Request Zone
g Define a Request Zone
g LAR is same as flooding, except that only nodes in
request zone forward route request
g Smallest rectangle including S and expected zone for
D
Request Zone
D

Expected Zone

x
Y
S
52

26
 Location Aided Routing (LAR)

g Advantages
ireduces the scope of route request flood
ireduces overhead of route discovery

g Disadvantages
iNodes need to know their physical locations
iDoes not take into account possible existence of
obstructions for radio transmissions

53

So far ...

g All protocols discussed so far perform some form of

flooding

g Now we will consider protocols which try to

reduce/avoid such behavior

54

27
 Link Reversal Algorithm [Gafni81]

A B F

C E G

55

Link Reversal Algorithm

A B F
Links are bi-directional

But algorithm imposes

logical directions on them
C E G

Maintain a directed acyclic

graph (DAG) for each
D destination, with the destination
being the only sink

This DAG is for destination

node D 56

28
 Link Reversal Algorithm

A B F

C E G

Link (G,D) broke

Any node, other than the destination, that has no outgoing links
reverses all its incoming links.
Node G has no outgoing links 57

Link Reversal Algorithm

A B F

C E G Represents a
link that was
reversed recently

Now nodes E and F have no outgoing links

58

29
 Link Reversal Algorithm

A B F

C E G Represents a
link that was
reversed recently

Now nodes B and G have no outgoing links

59

Link Reversal Algorithm

A B F

C E G Represents a
link that was
reversed recently

Now nodes A and F have no outgoing links

60

30
 Link Reversal Algorithm

A B F

C E G Represents a
link that was
reversed recently

Now all nodes (other than destination D) have an outgoing link

61

Link Reversal Algorithm

A B F

C E G

DAG has been restored with only the destination as a sink

62

31
 Link Reversal Algorithm

g Attempts to keep link reversals local to where the

failure occurred
iBut this is not guaranteed

g When the first packet is sent to a destination, the

destination oriented DAG is constructed

g The initial construction does result in flooding of

control packets

63

Link Reversal Algorithm

g The previous algorithm is called a full reversal

method since when a node reverses links, it reverses
all its incoming links

g Partial reversal method [Gafni81]: A node reverses

incoming links from only those neighbors who have
not themselves reversed links “previously”
iIf all neighbors have reversed links, then the node reverses
all its incoming links
i“Previously” at node X means since the last link reversal
done by node X

64

32
 Link Reversal Methods

g Advantages
iLink reversal methods attempt to limit updates to routing
tables at nodes in the vicinity of a broken link
•Partial reversal method tends to be better than full
reversal method
iEach node may potentially have multiple routes to a
destination (multipath)

g Disadvantages
iNeed a mechanism to detect link failure
• hello messages may be used
iIf network is partitioned, link reversals continue indefinitely
65

Temporally-Ordered Routing Algorithm

(TORA) [Park97Infocom]
g Route optimality is considered of secondary importance; longer
routes may be used

g At each node, a logically separate copy of TORA is run for each

destination, that computes the height of the node with respect to
the destination
iHeight captures number of hops and next hop
g Route discovery is by using query and update packets

g TORA modifies the partial link reversal method to be able to

detect partitions
g When a partition is detected, all nodes in the partition are
informed, and link reversals in that partition cease

66

33
 Other Protocols
g Many variations of using control packet flooding for route discovery

g Power-Aware Routing [Singh98Mobicom]

iAssign a weight to each link: function of energy consumed when
transmitting a packet on that link, as well as the residual energy level
iModify DSR to incorporate weights and prefer a route with the smallest
aggregate weight

g Associativity-Based Routing (ABR) [Toh97]

iOnly links that have been stable for some minimum duration are utilized
iNodes increment the associativity ticks of neighbors by using periodic
beacons

g Signal Stability Based Adaptive Routing (SSA) [Dube97]

iA node X re-broadcasts a Route Request received from Y only if the
(X,Y) link has a strong signal stability
iSignal stability is evaluated as a moving average of the signal strength
of packets received on the link in recent past 67

Proactive (Table-driven) Routing Protocols

68

34
 Broad Classification of Proactive Protocols

g Distance-Vector based
iDSDV (Destination-Sequenced Distance-Vector)

g Link-State based
iTBRPF (Topology Broadcast with Reverse Path Forwarding)
iOLSR (Optimized Link-State Routing)

69

Destination-Sequenced Distance-Vector
(DSDV) [Perkins94Sigcomm]
g Each node maintains a routing table which stores
inext hop towards each destination
ia cost metric for the path to each destination
ia destination sequence number that is created by the
destination itself
iSequence numbers used to avoid formation of loops
(indicate freshness of routes)

g Each node periodically forwards the routing table to

its neighbors
iEach node increments and appends its sequence number
when sending its local routing table
iThis sequence number will be attached to route entries
created for this node
70

35
 Destination-Sequenced Distance-Vector
(DSDV)
g Assume that node X receives routing information
from Y about a route to node Z

X Y Z

g Let S(X) and S(Y) denote the destination sequence

number for node Z as stored at node X, and as sent
by node Y with its routing table to node X,
respectively

71

Destination-Sequenced Distance-Vector
(DSDV)
g Node X takes the following steps:

X Y Z

iIf S(X) > S(Y), then X ignores the routing information

received from Y

iIf S(X) = S(Y), and cost of going through Y is smaller than

the route known to X, then X sets Y as the next hop to Z

iIf S(X) < S(Y), then X sets Y as the next hop to Z, and S(X)
is updated to equal S(Y)
72

36
 TBRPF (Topology Broadcast with Reverse Path
Forwarding) [Bellur99Infocom]
g Send link-state updates only via the minimum-hop
spanning tree rooted at the source of the update
g Little cost in maintaining the spanning tree
iThe network connectivity information is available

D D
2 transmissions
instead of 4

X Y Z X Y Z

S S

73

OLSR (Optimized Link-State Routing)

[Clausen01Inmic]
g Only multipoint relays (MPR) participate in the routing
g Each node maintains information about its MPR
g OLSR floods link-state information only through MPRs

74

37
 Hybrid Routing Protocols

75

Zone Routing Protocol (ZRP) [Haas98]

g ZRP combines proactive and reactive approaches

iMore like a framework

g All nodes within hop distance at most d from a node

X are said to be in the routing zone of node X
g All nodes at hop distance exactly d are said to be
peripheral nodes of node X’s routing zone

g Intra-zone routing: Proactively maintain routes to all

nodes within the source node’s own zone.
g Inter-zone routing: Use an on-demand protocol
(similar to DSR or AODV) to determine routes to
outside zone.
76

38
 Zone Routing Protocol (ZRP)

Radius of routing zone = 2

77

Routing Summary

g Protocols
iTypically divided into proactive, reactive and hybrid
iGeographic forwarding (does not really perform routing)

g Performance Studies
iTypically studied by simulations using NS, discrete event simulator
iNodes (10-200) remains stationary for pause time seconds (0-
900s) and then move to a random destination (1500m X 300m
space) at a uniform speed (0-20m/s). CBR traffic sources (4-30
packets/sec, 64-1024 bytes/packet)
iAttempt to estimate latency of route discovery, routing overhead …

g Actual trade-off depends a lot on traffic and mobility patterns

iHigher traffic diversity (more source-destination pairs) increases
overhead in on-demand protocols
iHigher mobility will always increase overhead in all protocols
78

39
 Other Routing Protocols

g Plenty of other routing protocols

g Discussion here is far from exhaustive

g Course handout contains descriptions (references) of

some other protocols

79

Multicast Routing
in
Mobile Ad Hoc Networks

80

40
 Multicasting

g A multicast group is defined with a unique group

identifier

g Nodes may join or leave the multicast group anytime

g In traditional networks, the physical network topology

does not change often

g In MANET, the physical topology can change often

81

Multicasting in MANET

g Need to take topology change into account when

designing a multicast protocol

g Several new protocols have been proposed for

multicasting in MANET
iAODV Multicast
iODMRP
iFlooding, AMRoute, CAMP, AMRIS, …

82

41
 AODV Multicasting [Royer00Mobicom]

g Each multicast group has a group leader

g Group leader is responsible for maintaining group

sequence number (which is used to ensure freshness
of routing information)
iSimilar to sequence numbers for AODV unicast

g First node joining a group becomes group leader

g A node on becoming a group leader, broadcasts a

Group Hello message
83

AODV Group Sequence Number

g In our illustrations, we will ignore the group sequence

numbers

g However, note that a node makes use of information

received only with recent enough sequence number

84

42
 AODV Multicast Tree

Multicast tree links

E Group leader
L
C
J
G
H D
K
A
B
N
Group and multicast tree member

Tree (but not group) member 85

Joining the Multicast Tree: AODV

E Group leader
L
C
J
G
H D
K
A
B N wishes to
N join the group:
it floods RREQ
Route Request (RREQ)
86

43
 Joining the Multicast Tree: AODV

E Group leader
L
C
J
G
H D
K
A
B
N N wishes to
join the group

Route Reply (RREP)

87

Joining the Multicast Tree: AODV

E Group leader
L
C
J
G
H D
K
A
B
N N wishes to
join the group

Multicast Activation (MACT)

88

44
 Joining the Multicast Tree: AODV

Multicast tree links

E Group leader
L
C
J
G
H D
K
A
B
N N has joined
Group member the group

Tree (but not group) member 89

Sending Data on the Multicast Tree

g Data is delivered along the tree edges maintained by

the Multicast AODV algorithm

g If a node which does not belong to the multicast

group wishes to multicast a packet
iIt sends a non-join RREQ which is treated similar in many
ways to RREQ for joining the group
iAs a result, the sender finds a route to a multicast group
member
iOnce data is delivered to this group member, the data is
delivered to remaining members along multicast tree edges

90

45
 Leaving a Multicast Tree: AODV

Multicast tree links

E Group leader
L J wishes to
C leave the group
J
G
H D
K
A
B
N

91

Leaving a Multicast Tree: AODV

Since J is not a leaf
node, it must remain
a tree member
E Group leader
L J has left
C the group
J
G
H D
K
A
B
N

92

46
 Leaving a Multicast Tree: AODV

E Group leader
L
C
J
G
H D
K
A
MACT (prune)
B
N

N wishes to leave
the multicast group 93

Leaving a Multicast Tree: AODV

E Group leader
L
C
J
G
H MACT
D
(prune)
K
A
B
N
Node N has removed itself from the multicast group.

Now node K has become a leaf, and K is not in the group. 94

So node K removes itself from the tree as well.

47
 Leaving a Multicast Tree: AODV

E Group leader
L
C
J
G
H D
K
A
B
N

Nodes N and K are no more in the multicast tree.

95

Summary: Multicast AODV

g Similar to unicast AODV

g Uses leaders to maintain group sequence numbers,

and to help in tree maintenance

g Provisions for handling network partitions are also

included

96

48
 On-Demand Multicast Routing Protocol
(ODMRP)

g ODMRP requires cooperation of nodes wishing to

send data to the multicast group
iTo construct the multicast mesh
g A sender node wishing to send multicast packets
periodically floods a Join Query packet throughout
the network
iPeriodic transmissions are used to update the routes

97

On-Demand Multicast Routing Protocol

(ODMRP)
g Each multicast group member on receiving a Join
Query, broadcasts a Join Reply to all its neighbors
g When node N receives the above broadcast, N
becomes member of the forwarding group

98

49
 Other Multicasting Protocols

g Several other multicasting protocols have been

proposed

g For a comparison study, see [Lee00Infocom]

99

Medium Access Control Protocols

100

50
 Motivation

g Can we apply media access methods from fixed networks?

g Example CSMA/CD
iCarrier Sense Multiple Access with Collision Detection
isend as soon as the medium is free, listen into the medium if a
collision occurs (original method in IEEE 802.3)

g MAC problems in wireless networks

isignal strength decreases proportional to the distance
isender would apply CS and CD, but the collisions happen at the
receiver
isender may not “hear” the collision, i.e., CD does not work
iCS might not work, e.g. if a terminal is “hidden”

101

MAC Protocols: Issues

g Hidden and Exposed Terminal Problems

g Reliability
g Collision avoidance
g Congestion control
g Energy efficiency

102

51
 Hidden Terminal Problem

g Hidden terminals
iA sends to B, C cannot detect A’s transmission
iC wants to send to B, C senses a “free” medium (CS fails)
icollision at B, A cannot detect the collision (CD fails)
iA is “hidden” for C

A B C

103

Exposed Terminal Problem

g Exposed terminals
iB sends to A, C wants to send to D
iC senses carrier, finds medium in use and has to wait
iA is outside the radio range of C, therefore waiting is not
necessary
iC is “exposed” to B

A B C D

104

52
 Multiple Access with Collision Avoidance
(MACA) [Karn90]
g MACA uses signaling packets for collision avoidance
iRTS (request to send)
• sender request the right to send from a receiver with a short
RTS packet before it sends a data packet
iCTS (clear to send)
• receiver grants the right to send as soon as it is ready to
receive

g Signaling packets contain

isender address
ireceiver address
iDuration

g Variants of this method are used in IEEE 802.11

105

MACA Solutions [Karn90]

g MACA avoids the problem of hidden terminals

iA and C want to
send to B
RTS
iA sends RTS first A B
iC waits after receiving C
CTS CTS
CTS from B

g MACA avoids the problem of exposed terminals

iB wants to send to A, C
to another terminal
RTS RTS
inow C does not have A B C
to wait, as it cannot CTS
receive CTS from A

106

53
 MAC: Reliability

g Wireless links are prone to errors. High packet loss rate is

detrimental to transport-layer performance.

g Solution: Use of acknowledgements

iWhen node B receives a data packet from node A, node B sends
an Acknowledgement (Ack).
iIf node A fails to receive an Ack, it will retransmit the packet
iThis approach adopted in many protocols [Bharghavan94, IEEE
802.11]

g IEEE 802.11 Wireless MAC

iDistributed and centralized MAC components
• Distributed Coordination Function (DCF)
• Point Coordination Function (PCF)
iPCF suitable for access point-based networking
iDCF suitable for ad hoc networking 107

IEEE 802.11 DCF

g Uses RTS-CTS exchange to avoid hidden terminal

problem
iAny node overhearing a RTS or CTS cannot transmit for the
duration of the transfer
iNote that RTS/CTS can collide

g Uses ACK to achieve reliability

g Any node receiving the RTS cannot transmit for the

duration of the transfer
iTo prevent collision with ACK when it arrives at the sender
iWhen B is sending data to C, node A will keep quite
A B C 108

54
 MAC: Collision Avoidance

g With half-duplex radios, collision detection is not possible

g Collision avoidance: Once channel becomes idle, the node waits
for a randomly chosen duration before attempting to transmit

g IEEE 802.11 DCF

iWhen transmitting a packet, choose a backoff interval in the range
[0,cw]; cw is contention window
iCount down the backoff interval when medium is idle
iCount-down is suspended if medium becomes busy
iWhen backoff interval reaches 0, transmit RTS

g Time spent counting down backoff intervals is a part of MAC

overhead
g large cw leads to larger backoff intervals
g small cw leads to larger number of collisions
109

DCF Example

B1 = 25 B1 = 5
wait data

data wait
B2 = 20 B2 = 15 B2 = 10

B1 and B2 are backoff intervals

cw = 31 at nodes 1 and 2
110

55
 MAC Protocols: Issues

g Hidden and Exposed Terminal Problems

g Reliability
g Collision avoidance
g Congestion control
g Energy efficiency

111

MAC: Congestion Control

g IEEE 802.11 DCF: Congestion control achieved by

dynamically choosing the contention window cw

g Binary Exponential Backoff in DCF:

iWhen a node fails to receive CTS in response to its RTS, it
increases the contention window
•cw is doubled (up to an upper bound)
iWhen a node successfully completes a data transfer, it
restores cw to CWmin

112

56
 MAC: Energy Conservation

g Proposals typically suggest turning the radio off when

not needed

g Power Saving Mode in IEEE 802.11 (Infrastructure

Mode)
iAn Access Point periodically transmits a beacon indicating
which nodes have packets waiting for them
iEach power saving (PS) node wakes up periodically to
receive the beacon
iIf a node has a packet waiting, then it sends a PS-Poll
•After waiting for a backoff interval in [0,CWmin]
iAccess Point sends the data in response to PS-poll
113

MAC Protocols: Summary

g Wireless medium is prone to hidden and exposed

terminal problems

g Protocols are typically based on CSMA/CA

g RTS/CTS based signaling
g ACKs for reliability

g Contention window is used for congestion control

g IEEE 802.11 wireless LAN standard
g Fairness issues are still unclear

114

57
 Other MAC Protocols

g Lot of other protocols !

g See past MobiCom, WCNC, MilCom, VTC, etc.,

conferences

115

Wireless Sensor Networks

116

58
 Applications

Military: battlefield surveillance

117

Applications
Scientific: eco-physiology, Infrastructure: contaminant
biocomplexity mapping flow monitoring

www.jamesreserve.edu

Engineering: monitoring
structures
118

59
 Wireless Sensor Networks

g Why not use proposed Ad Hoc protocols?

iThe number of sensor nodes in a sensor network can be several
orders of magnitude higher than the nodes in an ad hoc network.
iSensor nodes are densely deployed.
iSensor nodes are prone to failures.
iSensor nodes mainly use broadcast communication paradigm
whereas most ad hoc networks are based on point-to-point
communications.
iSensor nodes are limited in power, computational capacities, and
memory.
iSensor nodes may not have global identication (ID) because of the
large amount of overhead and large number of sensors.
iData-Centric
119

Wireless Sensor Networks

g Characteristics of sensor networks

iApplication Specific Requirements

iData-Aggregation

i“Data-Centric” Property

iLocation Awareness

120

60
 A Sensor Node

g May need to fit into a matchbox-sized module

g Smart dust mote
i4 MHz Atmel AVR 8535 micro-controller
i8 KB instruction flash memory
i512 bytes RAM
i512 bytes EEPROM
iTinyOS – 3500 bytes of code
g Each sensor node are assumed to be equipped with
a GPS unit
iOr a limited number of nodes have GPS and help others to
figure out their locations

121

Communication Architecture

g Basically of two types

Flat Hierarchical

122

61
 Routing in Sensor Networks

123

Classification of Sensor Networks

g Proactive Networks
iThe nodes in the network periodically switch on their
sensors and transmitters, sense the environment and
transmit the data of interest.
g Reactive Networks
iIn this scheme the nodes react immediately to sudden and
drastic changes in the value of sensed attribute.
g Hybrid Networks

124

62
 Routing in Sensor Networks
Directed Diffusion [Intanagonwiwat 2000]
g The query is flooded throughout the network (Flat).

g Does not fully exploit the feature of sensor networks125

that adjacent nodes have similar data.

Hierarchical Sensor Network Model

g Each cluster has a cluster head (CH) which collects

data form its cluster members.
g CH aggregates the data and sends it to the BS or an
upper level cluster head.
g All the nodes transmit only to their immediate CH.
g CH at increasing levels in the hierarchy need to
transmit data over relatively longer distances (energy
consumption)

126

63
 LEACH (Low-Energy Adaptive Clustering
Hierarchy) [Heinzelman 2000b]

g Proactive network protocol (Hierarchical)

iCluster-based
g MAC: TDMA/CDMA
iTDMA – Intra-Cluster (Fixed schedule)
iCDMA – Inter-Cluster (Different codes)

g Utilizes randomized rotation of local cluster-heads to

extend battery life
g Data collection is centralized and done periodically
iAppropriate for constant monitoring of networks

127

3.1 3.2

Base Station

3
3.3
2
2.3
1.0.1
1
1.0.2 2.1
1.2.5 1.2.4
2.2
1.0.3
1.2

1.1.2 1.1 1.1.3

1.2.1 1.2.3
1.1.4
1.2.2
1.1.1 1.1.5 Simple sensor node
First Level Cluster Head
128
Second Level Cluster Head
Hierarchical Clustering

64
 Reactive Network Protocol:TEEN

TEEN (Threshold sensitive Energy Efficient sensor

Network protocol) [Manjeshwar 2001]

g Designed for reactive networks.

iNodes sense their environment continuously
g In this scheme at every cluster change time, the CH
broadcasts the following to its members:
iHard Threshold (HT): This is a threshold value for the sensed
attribute.
iSoft Threshold (ST): This is a small change in the value of
the sensed attribute which triggers the node to switch on its
transmitter and transmit.
129

TEEN

g Advantages
iSuited for time critical sensing applications.
iMessage transmission consumes more energy than data
sensing. So the energy consumption in this scheme is less
than the proactive networks.
iThe soft threshold can be varied.
iAt every cluster change time, the parameters are broadcast
afresh and so, the user can change them as required.
g Disadvantage
iIf the thresholds are not reached, the nodes will never
communicate.

130

65
 Hybrid Networks

g Combining the best features of proactive and reactive

networks while minimizing their limitations to create a
new type of network is called a Hybrid Network

131

APTEEN (Adaptive TEEN)

[Manjeshwar 2002]
Functioning:

g The cluster heads broadcasts the following

parameters to sensors:
iAttributes (A): This is a set of physical parameters which the
user is interested in obtaining data about.
iThresholds: This parameter consists of a hard threshold (HT)
and a soft threshold (ST).
iSchedule: This is a TDMA schedule, assigning a slot to each
node.
iCount Time (CT): It is the maximum time period between two
successive reports sent by a node.

132

66
 APTEEN

g Proceeds exactly like TEEN plus

iIf a node does not send data for a time period equal to the count
time (CT), it is forced to sense and retransmit the data.

g TDMA schedule is used and each node in the cluster is

assigned a transmission slot.

133

APTEEN

g Advantages
iIt combines both proactive and reactive policies.
iIt offers a lot of flexibility by allowing the user to set the time
interval (CT) and the threshold values for the attributes.
iEnergy consumption can be controlled by changing the count
time as well as the threshold values.
g Disadvantages
iThe main drawback of the scheme is the additional
complexity required to implement the threshold functions and
the count time.
iRate of energy consumption is increased

134

67
 Wireless Sensor Networks
Hierarchical X Flat
Hierarchical Flat
Reservation-based scheduling Contention-based scheduling
Collisions avoided Collision overhead present
Reduced duty cycle due to periodic sleeping Variable duty cycle by controlling sleep time of
nodes
Data aggregation by cluster head Node on multi-hop path aggregates incoming
data from neighbors
Simple but non-optimal routing Routing is complex but optimal
Requires global and local synchronization Links formed in the fly, without synchronization
Overhead of cluster formation throughout the Routes formed only in regions that have data for
network transmission
Lower latency as multi-hop network formed by Latency in waking up intermediate nodes and
cluster-heads is always available setting up the multi-hop path
Energy dissipation is uniform Energy dissipation depends on traffic patterns
Energy dissipation cannot be controlled Energy dissipation adapts to traffic pattern
Fair channel allocation Fairness not guaranteed
135

Current Research Projects

136

68
 Related Standards Activities

137

Internet Engineering Task Force (IETF)

Activities

g IETF manet (Mobile Ad-hoc Networks) working

group
ihttp://www.ietf.org/html.charters/manet-charter.html

g IETF mobileip (IP Routing for Wireless/Mobile

Hosts) working group
ihttp://www.ietf.org/html.charters/mobileip-charter.html

138

69
 Related Standards Activities

g BlueTooth
ihttp://www.bluetooth.com

g IEEE 802.15
ihttp://grouper.ieee.org/groups/802/15/

g HomeRF [Lansford00ieee]
ihttp://www.homerf.org

g IEEE 802.11
ihttp://grouper.ieee.org/groups/802/11/

g HiperLan/2
ihttp://www.etsi.org/technicalactiv/hiperlan2.htm 139

Bluetooth
[Haartsen98]

g Features: Cheaper, smaller, low power, ubiquitous,

unlicensed frequency band (2.4GHz)

g Current Spec version 1.1 (1600+ pages)

g Promoter group consisting of 9

iEricsson, IBM, Intel, Nokia, Toshiba, 3Com, Agere,
Microsoft, Motorola

g 3000+ adopters
140

70
 Bluetooth: Link Types

g Designed to support multimedia applications that mix

voice and data
g Synchronous Connection-Oriented (SCO) link
iSymmetrical, circuit-switched, point-to-point connections
iSuitable for voice
iTwo consecutive slots (forward and return slots) reserved at
fixed intervals
g Asynchronous Connectionless (ACL) link
iSymmetrical or asymmetric, packet-switched, point-to-
multipoint
iSuitable for bursty data
iMaster units use a polling scheme to control ACL
connections
141

Bluetooth: Piconet

g A channel is characterized by a frequency-hopping

pattern
g Two or more terminals sharing a channel form a
piconet
iRoughly 1 Mbps per Piconet
g One terminal in a piconet acts as a master and up to
7 slaves
g Other terminals are slaves
g Polling scheme: A slave may send in a slave-to-
master slot when it has been addressed by its MAC
address in the previous master-to-slave slot

142

71
 Bluetooth: Scatternet

g Several piconets may exist in the same area (such

that units in different piconets are in each other’s
range)
iA large number of piconets in the vicinity may eventually
interfere with each other [Cordeiro01Globecom]
iInterference mitigation schemes [Cordeiro02Sbrc]
g A group of piconets is called a scatternet
iNew routing issues [Bhagwat99Momuc]

143

The Scope of the Various WLAN and WPAN

Standards

C P
o o
m w
p e
l r 802.11a
e HiperLAN
x C
i o 802.11g*
t n 802.11b
y s
u 802.11
m WLAN
p
t 802.15.1
i Bluetooth
o
n
802.15.4* WPAN

* Standards process in progress Data rate

144

72
 Open Issues
in
Mobile Ad Hoc Networking

145

Open Problems

g Issues other than routing have received much less

attention so far

Other interesting problems:

g Address configuration (DHCP ???)

g MAC protocols
g Improving interaction between protocol layers
g QoS issues
g Applications for MANET

146

73
 Thank you !!!

For more information, send e-mail to

Carlos Cordeiro at
cordeicm@ececs.uc.edu
or visit
http://www.ececs.uc.edu/~cordeicm

147

74