Transcript 3-1-4 georouting08

Proposed ad hoc Routing Approaches
• Conventional wired-type schemes (global
routing, proactive):
– Distance Vector; Link State
• Proactive ad hoc routing:
– OLSR, TBRPF
• On- Demand, reactive routing:
• DSR (Source routing), MSR
• AODV (Backward learning)
• Scalable routing :
– Hierarchical routing: HSR, Fisheye
– OLSR + Fisheye
– LANMAR (for teams/swarms)
• Geo-routing:
• GPSR, GeRaF, etc
• Motion assisted routing
• Direction Forwarding
Georouting - Key Idea
• Each node knows its geo-coordinates (eg,
from GPS or Galileo)
• Source knows destination geo-coordinates; it
stamps them in the packet
• Geo-forwarding: at each hop, the packet is
forwarded to the neighbor closest to
destination
• Options:
– Each node keeps track of neighbor
coordinates
– Nodes know nothing about neighbor
coordinates
Greedy Perimeter Stateless Routing
for Wireless Networks (GPSR)
– key elements
• Greedy forwarding
– Each nodes knows own coordinates
– Source knows coordinates of destination
– Greedy choice – “select” the most forward
node
Finding the most forward neighbor
• Beaconing: periodically each node
broadcasts to neighbors own {MAC ID,
IP ID, geo coordinates}
• Each data packet piggybacks sender
coordinates
• Alternatively (for low energy, low duty
cycle ops) the sender solicits “beacons”
with “neighbor request” packets
Greedy Perimeter Forwarding
D is the destination; x is the node where the
packet enters perimeter mode; forwarding
hops are solid arrows;
Got stuck? Perimeter forwarding
> Greedy forwarding failure. x is a local
maximum in its geographic proximity to D;
w and y are farther from D.
> Node x’s void with respect to destination D
GPSR vs DSR
Throughput (Kbps)
TCP over GPSR, AODV, DSR and DSDV
Speed(m/s)
Congestion Aware GPSR
Hot spot
Problem:
Congestion area will cause long packet delay and
high loss probability
Our approach:
1. Go around the congestion area will decrease the delay,
but detour path is usually longer than the shortest path.
Going through the long path will cause throughput
loss.
2. Study packet delay, the tradeoff between congestion
detour and throughput gain.
GPSR commentary
• Very scalable:
– small per-node routing state
– small routing protocol message complexity
– robust packet delivery on densely deployed,
mobile wireless networks
• TCP is extremely sensitive to path breakage
(timeout) -- It does very well with georouting
• Outperforms DSR and AODV
• Drawback: it requires knowledge of dest geo
coordinates (explicit forwarding node address)
– Beaconing overhead
– nodes may go to sleep (on and off) in
sensor networks
Geographic Random Forwarding (GeRaF)
- Forwarding in a Large Sensor Net
• Nodes in turns go to sleep and wake
up, source does not know which nodes
are on/off
• Source cannot explicitly address the
next hop, must randomly select
• ideally, the best available node to act
as a relay is chosen
• this selection is done a posteriori, i.e.,
after the transmission has taken place
• it is a receiver contention scheme
GeRaF: Key Idea
 Goal: pick the relay closest to the destination
 broadcast message is sent, all active nodes
within range receive it
 contention phase takes place: nodes closer to
the destination are likely to win
 the winner becomes itself the source
Practical Implementation
• major problem: how to pick the best relay?
• solution: partition the area and pick relays
from slice closest to the destination
• nodes can determine in which region they are
• nodes in highest priority region contend first
Contention Resolution
• Assume 802.11 RTS/CTS
• Source transmits RTS with source and
destination coordinates
• Stations in priority region #1 are
solicited
• If none responds, stations in region #2
are solicited
Conclusions
• nodes who receive a message
volunteer and contend to act as relays
• advantages: good for sensor net
– no need for complicated routing
tables or routing-related signaling
– near-optimal multihop behavior,
much better than alternative
solutions (eg GAF, SPAN)
– significant energy/latency gains if
nodes are densely deployed
Mobility assisted routing
• Mobility (of groups) was helpful to scale
the routing protocol – see LANMAR
• Can mobility help in other cases?
– Destination discovery (if coordinates not
know)
– Mobility induced distributed
route/directory tree
• Ref: H. Dubois Ferriere et al. ”Age Matters:
Efficient Route discovery in Mobile Ad Hoc
Networks Using Encounter ages, Mobihoc
2003
Mobility Diffusion and “last encounter”
routing
• Imagine a roaming node “sniffs” the
neighborhood and learns/stores neighbors’ IDs
• Roaming node carries around the info about
nodes it saw before
• Instead of searching for the destination, the
source node searches for any intermediate
node that encountered the destination more
recently than did the source node itself.
• The intermediate node then searches for a node
that encountered the destination yet more
recently, and the procedure iterates until the
destination is reached.
Mobility Diffusion and “last encounter”
routing (cont.)
• If nodes move randomly and uniformly in the
field (and the network is dense), there is a
trail of nodes – like pointers – tracing back to
each ID
• The superposition of these trails is a tree – it
is a routing tree (to send messages back to
source); or a distributed directory system (to
map node ID to geo-coordinates, for example)
• “Last encounter” routing: next hop is the
node that last saw the destination
Fresh algorithm
– H. Dubois Ferriere, Mobihoc 2003
Mobility induced, distributed
embedded route/directory tree
Benefits:
• (a) avoid overhead of periodic advertising
of node location (eg, Landmark routing)
• (b) reduce flood search O/H (to find ID)
• (c ) avoid registration to location server
(to DNS, say)
Issue:
• Motion pattern impact (localized vs
random roaming)
“Direction” forwarding for mobile,
large scale ad hoc networks
 Distance
Vector not robust to mobility
• In Distance Vector Routing (e.g., Bellman Ford,
AODV etc.) node keeps pointer to “predecessor”
DV update
Predecessor
Data flow
Source
Sink
• When the predecessor moves, the path is broken
• Alternate paths, even when available, are not used
 Proposed
solution: direction forwarding
Direction Forwarding
• Distance Vector update creates not only
“predecessor”, but also “direction” entry
Direction to Dest
DV Update
Primary Predecessor
Primary Path
Alternate Data Path
Source
Dest
• Select “most productive” neighbor in forward
direction
• If the network is reasonably dense, the path is
salvaged
How to compute the “direction”
 Need “stable” local orientation system (say,
virtual compass) to determine direction of
update
 Local (rather than global) reference is
required;
 Local reference system must be refreshed
fast enough to track avg local motion
 GPS will do (e.g., neighbors exchange (X, Y)
coordinates)
 If GPS not available, several non-GPS
coordinate systems have been recently
published
 Sextant [Mobihoc ’05]; beacon DV; RFID’s
etc
Computing the “direction”(cont)
 Compute “direction” to a destination when DV
updates are received:
 If a DV update packet with a more recent
Seq # or smaller hop distance is received:
 New “direction” replaces the old one
 The “direction” to the predecessor is used
as the “direction” to the destination
 If multiple DV updates received from
different “predecessors” with same hop
distance and seq # for the destination
 Take vector sum of directions
Computation of the “direction”
Suppose node A receives DV update packets from B & C
Compute the “directions” to predecessors
node B & C, respectively,

( c , rc )
C
“Direction” to a destination
r  ( X 2  X 1 ) 2  (Y2  Y1 ) 2
Y2  Y1
  tan (
)
X 2  X1
1
( c ,1)
d
A
( b ,1)
Directions to
predecessors
B
( b , rb )
Where the polar angle is the
radian from the x-axis that is
used as the direction of the
predecessor node.
Computation of the “direction”

Unit vectors are used to combine the two “directions”
Direction Forwarding vs Geo routing
• Geo-routing:
– Direction points to destination
– This direction may be unfeasible (holes, etc)
– Global geo-coordinates (eg, GPS)
– Geo Location Server
– Robust to mobility
• Direction Forwarding
– Direction of updates (always feasible)
– Local (not global) position reference system
– Advertisements from destination
– Robust to mobility
Case study: apply Direct Forwarding
(DFR) to LANMAR Routing
• LANMAR builds upon existing routing protocols
– (1) “local ” routing algorithm that keeps
accurate routes within local scope < k hops
(e.g., OLSR, FSR)
– (2) Landmark routes advertised to all mobiles
using a Distance Vector approach
Landmark
Logical Group
LANMAR +DFR
• LANMAR has proved to be very scalable to
size
• However, as speed increases, performance
degrades, even with group mobility!
• Problem was traced to failure of DV route
advertising in high mobility
• We first tried to refresh more frequently: it
did not work!
• Next step: try DFR
Simulation Experiments
• Simulator: QualNet 3.8
– Standard IEEE 802.11 radio with a channel
rate of 2Mbps and transmission range of
367 meters.
– Network field size: 2250m by 2250m
• LANMAR is the protocol “hosting” DFR
– 225 nodes (or 360 nodes) equally
distributed in 9 groups
– Mobility model: Group Mobility model
• Traffic: CBR, 1 packets/sec, 512 bytes/packet
– The # of source-destination pairs is varied
in the simulations to vary the offered traffic
load
Performance as a function of speed
1
DFR
0.9
Delivery Fraction
0.8
LANMAR
0.7
0.6
0.5
0.4
0.3
LANMAR(225 nodes)
0.2
DFR(225 nodes)
LANMAR(360 nodes)
0.1
DFR(360 nodes)
0
0
2
4
6
8
10
Mobility (m/sec)
12
14
16
Delivery ratio vs. speed
(Including packet loss due to disconnected destination)
Conclusions and Future Work
• DFR: new forwarding strategy for table driven
routing
• Direction Forwarding can improve LANMAR
performance dramatically at high speeds
• Future Work:
– Test DFR under local reference system
– Apply DFR concept to AODV - Hybrid
– TCP over {LANMAR, AODV} + DFR
– Compare DFR with other backup route
schemes
– Test DFR under more general mobility
models
Robust Ad Hoc Routing for
Lossy Wireless Environment
• Challenges for routing in mobile ad hoc network
– Route breakage
– High BER
– Scalability
• The shortcomings of on-demand routing
• Not scalable for mobility
• The shortcomings of proactive routing
• Constant and high routing overhead
• The shortcomings of current Geo-routing
• Need Geo-Location Service, GLS
• “Face routing” is inefficient
Hybrid Routing: AODV-DFR
(AODV with Directional Forwarding Routing)
• Combines on-demand and proactive routing
– When a source starts comm, it first finds the
destination as in an on-demand fashion
– Once the destination is notified, it initiates
periodic routing updates in a proactive fashion
• Utilizing an alternate path instantly based on
“direction” to the destination if a path fails
– resemblance with Georouting in the update
message
– No location server system is required (not
like GPSR)
AODV-DFR
• Source initiates route discovery a la AODV
– Destination, or any node that has a route,
replies
– The path is set up
• Destination begins proactive advertisements (a
la DV) after receiving data pkts from source
– Intermediate nodes rebroadcast ads
– Only for active connections
– Period increases with distance from
destination (Fisheye concept)
• Packet routing assisted by Direction Forward
• The destination stops advertisement if it does
not receive pkts for some time
Performance Evaluation
• Compare AODV, AODV-DFR, GPSR and ADV
(proactive and on-demand Hybrid Routing)
– Performance: Delivery ratio, Packet delay,
Routing Overhead
– Mobile & lossy network: UDP and TCP traffic
• Mobility Speed
• Packet loss: uniformly distributed on a link
• Simulation
– 100 nodes randomly moving in 1000x1000m
– The traffic pairs are randomly distributed
over the network
– UDP flows: pkt size 512 bytes, rate 1pkt/sec
– TCP flows: NewReno, pkt size 1460 bytes
Mobile Network: Delivery Ratio
80 UDP flows
Mobile Network: Packet delay
80 UDP flows
Mobile Network: Routing Overhead
80 UDP flows
Mobile & Lossy Network:
Delivery Ratio
UDP Flow number: 80
Mobility Speed: 10 m/s
Mobile & Lossy Network:
Routing Overhead
UDP Flow number: 80
Mobility Speed: 10 m/s
TCP in Mobile Network
40 TCP flows
TCP in Mobile & Lossy Network
TCP flow number: 40
Mobility: 10 m/s
AODV-DFR Contributions
• A hybrid routing: proactive + on-demand
• Robust to mobility and packet loss
• Utilize location information for directional
forwarding with only local updates.
• Low overhead
• Provide better performance than AODV and
GPSR
• Enhances AODV
• Competitive with GPSR (does not require
“global” positioning such as GPS)
• Ongoing work: local coordinate system;
integration of local and global coordinates
(indoor+outdoor)