Transcript Presentation ( format)

Ad Hoc Wireless Networks:
Protocols and Applications
Capri Wireless School
Sept 13-17, 2004
Mario Gerla
Computer Science Dept
UCLA
Ad Hoc Networks - Outline
• What is an Ad Hoc Network
• Ad hoc network projects at UCLA
– The ONR Minuteman project
– The NSF WHYNET project
• The MAC protocol
• Scalable routing
– On demand routing
– Proactive routing
• Bringing ad hoc networks to market
• The vehicular grid
• The future of ad hoc networking
The three wireless network
“waves”
• Wave #1: cellular telephony (late 80’s)
– Still, biggest profit maker
• Wave #2 : wireless Internet access (mid
90s)
– Most Internet access on US campuses is via WiFi
– Hot spots are rapidly proliferating in the US; Europe and Asia
to follow soon
– 2.5 G and 3G trying to keep up; competitive edge?
• Wave #3: ad hoc wireless nets (now)
– Set up in an area with NO infrastructure; to respond to a
specific, time limited need
The 3rd Wave: Infrastructure vs Ad Hoc
Infrastructure Network (cellular or Hot spot)
Ad Hoc, Multihop wireless Network
General Ad Hoc Network Characteristics
• Instantly deployable, re-configurable (no fixed
infrastructure)
• Created to satisfy a “temporary” need
• Node portability (eg sensors), mobility
• Limited battery power
• Multi-hopping ( to save power, overcome
obstacles, enhance spatial spectrum reuse, etc.)
Ad Hoc Network Applications
Military
– Automated battlefield
– Special operations
– Homeland defense
Civilian
–
–
–
–
–
Disaster Recovery (flood, fire, earthquakes etc)
Law enforcement (crowd control)
Search and rescue in remote areas
Environment monitoring (sensors)
Space/planet exploration
(Issue: ad hoc nets vs sensor nets)
Ad Hoc Network Applications (cont)
Commercial
–
–
–
–
–
–
Sport events, festivals, conventions
Patient monitoring
Ad hoc collaborative computing (Bluetooth)
Sensors on cars (car navigation safety)
Car to car communications
Networked video games at amusement parks, etc
Commercial Killer Application?
….stay tuned!
The Battlefield
• Soon after ARPANET birth, DoD was quick to
understand the value of ad hoc networks for the
battlefield
• In 1971 (two years after ARPANET) DARPA starts
the Packet Radio project
• Since 1971, several DARPA, Army and Navy
programs supported ad hoc net research and
helped enhance this technology
• So far, government has been the main funding
source: battlefield is the “killer” application.
DARPA Packet Radio Project (1971-1985)
• Goals:
– extend P/S to mobile environment
– provide network access to mobile terminals
– quick (re) deployment
• Fully distributed design philosophy:
–
–
–
–
–
–
self initialization
dynamic reconfiguration
asynchronous MAC protocol (CSMA)
dynamic routing
automated network management
“compact”, portable radio design
Ad Hoc Networks - Outline
• What is an Ad Hoc Network
• Ad hoc network projects at UCLA
– The ONR Minuteman project
– The NSF WHYNET project
• The MAC protocol
• Scalable routing
– On demand routing
– Proactive routing
•
•
•
•
Scalable, fair TCP
Bringing ad hoc networks to market
The vehicular grid
The future of ad hoc networking
The AINS (Autonomous Intelligent Networked
Systems) Program at UCLA
• 5 year research program (Dec 2000 – Dec
2005) sponsored by ONR
• 7 Faculty Participants: 3 in CS Dept, 4 in EE
Dept
• Goal: design a robust, self-configurable,
scalable network architecture for intelligent,
autonomous mobile agents
SATELLITE
COMMS
SURVEILLANCE
MISSION
SURVEILLANCE
MISSION
UAV-UAV NETWORK
AIR-TO-AIR
MISSION
STRIKE
MISSION
COMM/TASKING
Unmanned
Control Platform
COMM/TASKING
COMM/TASKING
RESUPPLY
MISSION
UAV-UGV NETWORK
FRIENDLY
GROUND CONTROL
(MOBILE)
Manned
Control Platform
Network of Autonomous Agents
Urban warfare scenario: Swarm
communications
Autonomous
Perching
Central AINS theme: networking
FLIR
The AINS Project Field Demo at UCLA
May 2004
• Goals
-
Demonstrate the integration and interworking of various
protocols:
-
Routing
Multicast
Sensors
Adaptive video
• Approach
-
Aerial nodes: Blimps with laptops
Mobile ground nodes: men/robots carrying laptops
Routing protocol: ODMRP
Scenario: cooperative surveillance of a large area
Blimp driven by robot
Detailed Demo scenario:
1. Mobile robots with cameras do routine patrolling
Mobile robots
Command Post
2. Command post (CP) detects an irregular activity far away
3. CP sends out a mobile robot for a closer investigation; it becomes
disconnected due to the short radio range
4. Another robot moves in to re-connect
5. Another suspect activity detected
6. Second robot moves out to investigate, breaking the network
Bring in the Blimp to reconnect
View From the Blimp
QuickTime™ and a
TechSmith EnSharpen decompressor
are needed to see this picture.
QuickTime™ and a
TechSmith EnSharpen decompressor
are needed to see this picture.
WHYNET - Network Testbed at UCLA
• Wireless Hybrid Networked Testbed
• Sponsored by NSF (2003 to 2007)
• A “consortium” of seven Universities (UCLA,
USC, UCB, UCD, UCR, UCSD, U-Delaware)
• Main Goal: develop test environments/tools:
–
–
–
–
–
Radios (MIMO, OFDM, UWB, sensor radios, etc)
MAC protocols (directional antennae)
Sensor (low energy protocols)
Network protocols (QoS, Scalability, interconnection)
Security
• Approach: share results/code/platforms
• Center piece: hybrid emulation environment
Hybrid Emulation testbed
Simulated large-scale network
Access Nodes & Hybrid Simulation Server Cluster
Small-scale Real Testbed
Internet
Sample WHYNET projects
• Radio testbed for MIMO and smart
antenna technology
• A lab for UWB studies/experiemnts
• A MANET Security benchmark
• A vehicular ad hoc network testbed
• Interconnection of MANETs across the
Internet
Ad Hoc Networks - Outline
• What is an Ad Hoc Network
• Ad hoc network projects at UCLA
– The ONR Minuteman project
– The NSF WHYNET project
• The MAC protocol
• Scalable routing
– On demand routing
– Proactive routing
•
•
•
•
Scalable, fair TCP
Bringing ad hoc networks to market
The vehicular grid
The future of ad hoc networking
Wireless Nets – the MAC layer
•
•
•
•
MAC Protocols Overview
IEEE 802.11
Bluetooth
Zigbee
Multiple Access Control (MAC) Protocols
•
•
•
•
MAC protocol: coordinates transmissions to minimize/avoid
collisions
(a) Channel Partitioning : TDMA, FDMA, CDMA (cellular systems)
(b) Random Access : CSMA (802.11, Zig Bee)
(c) “Polling” : Bluetooth
•
Goal: efficient, fair, simple, decentralized
Random Access protocols
•
•
•
•
A node transmits at random (ie, no a priory coordination among
nodes) at full channel data rate R.
If two or more nodes “collide”, they retransmit at random times
The random access MAC protocol specifies how to detect
collisions and how to recover from them (via delayed
retransmissions, for example)
Examples of random access MAC protocols:
(a) SLOTTED ALOHA
(b) CSMA and CSMA/CD
Slotted Aloha
• Time is divided into equal size slots (= full packet size)
• a newly arriving station transmits a the beginning of the
next slot
• if collision occurs the source retransmits the packet at each
slot with probability P, until successful.
• Success (S), Collision (C), Empty (E) slots
CSMA (Carrier Sense Multiple Access)
• CSMA: listen before transmit. If channel is
sensed busy, defer transmission
• Persistent CSMA: retry immediately when
channel becomes idle (this may cause
instability)
• Non persistent CSMA: retry after random
interval
• Upon collision, reattempt tx after random
timeout
CSMA collisions
Wireless LAN Configurations
Peer-to-peer Networking
Ad-hoc Networking
BS
With or without control (base) station
IEEE 802.11 Wireless LAN
• IEEE 802.11 standards define MAC protocol;
unlicensed frequency spectrum bands: 900Mhz,
2.4Ghz, 5.7Ghz
• Like a bridged LAN (flat MAC address)
IEEE 802.11 MAC Protocol
CSMA Version of the Protocol:
sense channel idle for DISF sec (Distributed Inter Frame
Space)
transmit frame (no Collision Detection)
receiver returns ACK after SIFS (Short Inter Frame Space)
if channel sensed busy => binary backoff
NAV: Network Allocation Vector (min time of deferral)
Hidden Terminal effect
• CSMA inefficient in presence of hidden terminals
• Hidden terminals: A and B cannot hear each other because
of obstacles or signal attenuation; so, their packets collide
at B
• Solution? CSMA + RTS/CTS
Collision Avoidance with RTS/CTS
• RTS freezes stations near the transmitter
• CTS “freezes” stations within range of receiver (but
possibly hidden from transmitter); this prevents collisions
by hidden station during data transfer
• RTS and CTS are very short: collisions are thus very
unlikely
• Note: IEEE 802.11 allows both CSMA, CSMA+RTS/CTS
802.11 - CSMA basic access method
DIFS
DIFS
medium busy
direct access if
medium is free  DIFS
+ CWmin
contention window
(randomized back-off
mechanism)
next frame
t
slot time
– station ready to send starts sensing the medium (Carrier Sense
based on CCA, Clear Channel Assessment)
– if the medium is free for the duration of an Inter-Frame Space
(DIFS), the station can start sending after CWmin
– if the medium is busy, the station has to wait for a free DIFS, then
the station must additionally wait a random back-off time (collision
avoidance, multiple of slot-time)
– if another station occupies the medium during the back-off time of
the station, the back-off timer stops (fairness)
802.11 - CSMA (cont)
•
Sending unicast packets
–
–
–
station has to wait for DIFS (and CWmin) before sending data
receivers acknowledge at once (after waiting for SIFS) if the packet was received
correctly (CRC)
automatic retransmission of data packets in case of transmission errors
DIFS
sender
data
SIFS
receiver
ACK
DIFS
other
stations
waiting time
data
t
contention
802.11 - CSMA with RTS/CTS
• Sending unicast packets
– station can send RTS with reservation parameter after waiting for DIFS (reservation
declares amount of time the data packet needs the medium)
– acknowledgement via CTS after SIFS by receiver (if ready to receive)
– sender can now send data at once, acknowledgement via ACK
– other stations store medium reservations distributed via RTS and CTS
DIFS
sender
RTS
data
SIFS
receiver
other
stations
CTS SIFS
SIFS
NAV (RTS)
NAV (CTS)
defer access
ACK
DIFS
data
t
contention
MAC-PCF (Point Coordination Function)
like polling
t0 t1
medium busy PIFS
point
coordinator
wireless
stations
stations‘
NAV
SuperFrame
SIFS
D1
SIFS
SIFS
D2
SIFS
U1
U2
NAV
MAC-PCF (cont)
t2
point
coordinator
wireless
stations
stations‘
NAV
D3
PIFS
SIFS
D4
t3
t4
CFend
SIFS
U4
NAV
contention free period
contention
period
t
Higher Speeds?
• IEEE 802.11a
– compatible MAC, but now 5.7 GHz ISM band
– OFDM (orthogonal freq division multiplexing)
– transmission rates up to 50 Mbit/s
– close cooperation with BRAN (ETSI Broadband
Radio Access Network)
• IEEE 802.11 g: up to 50Mbps, in the 2.5 range
• IEEE 802.11 n: up to 100 Mbps, using OFDM and
MIMO technologies
Better QoS guarantees?
•
•
•
QoS guarantees desirable for real time traffic
IEEE 802.11 e is the answer
EDCF mode (Enhanced DCF):
–
–
•
HCF mode (Hybrid Coordination Function):
–
–
–
–
•
•
Traffic class dependent CWmin and DIFS
Frame bursting: RTS-CTS-DATA-ACK-DATA-ACK-DATA-ACK…..
Similar to the PCF of 802.11b
Alternation of CP (contention periods) and CFP (cont free periods)
During the contention period EDCF mode is enacted, except that the AP can issue a
QoS poll to specific stations (using PIFS)
High priority stations can tell the AP about their needs (to get the Poll)
Clearly, the Best Effort traffic is second citizen in this case!
Another challenge is the coexistence of 802.11b and e
Bluetooth : a polling/TDMA scheme
•February 1998: The Bluetooth SIG is formed
(Ericsson, IBM, Intel, Nokia, Toshiba)
What does Bluetooth do for you?
Synchronization
•
•
•
Automatic synchronization of
calendars, address books, business
cards
Push button synchronization
Proximity operation
Cordless Headset
Cordless
headset
User benefits
•
•
•
Multiple device access
Cordless phone benefits
Hands free operation
Putting it all together..
Landline
Cable
Replacement
Data/Voice
Access Points
…and combinations!
Personal Ad-hoc
Networks
Example...
Bluetooth Physical link
• Point to point link
–
–
master - slave relationship
radios can function as masters or slaves
m
m
• Piconet
– Master can connect to 7 slaves
– Each piconet has max capacity =1 Mbps
– hopping pattern is determined by the master
s
s
s
s
Piconet formation
• Page - scan protocol
– to establish links with nodes
in proximity
Master
Active Slave
Parked Slave
Standby
Piconet MAC protocol : Polling
FH/TDD
f1
f2
m
s1
s2
625 µsec
1600 hops/sec
f3
f4
f5
f6
Multi slot packets
FH/TDD
f1
f4
f5
m
s1
s2
625 µsec
Data rate depends on type of packet
f6
Data Packet Types
Symmetric
2/3 FEC
DM1
108.8 108.8 108.8
DM3
258.1 387.2
54.4
DM5
286.7 477.8
36.3
Symmetric
No FEC
Asymmetric
DH1
DH3
DH5
Asymmetric
172.8 172.8 172.8
390.4 585.6 86.4
433.9 723.2 57.6
Inter piconet communication
Cordless
headset
mouse
Cordless
headset
Cell phone
Cell phone
Cell phone
Cordless
headset
Scatternet
Scatternet, scenario 2
How to schedule presence in
two piconets?
Forwarding delay ?
Missed traffic?
Ad Hoc Networks - Outline
• What is an Ad Hoc Network
• Ad hoc network projects at UCLA
– The ONR Minuteman project
– The NSF WHYNET project
• The MAC protocol
• Scalable routing
– On demand routing
– Proactive routing
• Bringing ad hoc networks to market
• The vehicular grid
• The future of ad hoc networking
Current ad hoc routing solutions
• On demand routing (DSR, AODV)
• Proactive routing (eg, DSDV, Optimal
Links State Routing - OLSR)
• Explicit hierarchical routing
Ad Hoc On-Demand Routing
•
•
•
•
Dynamic Source Routing (DSR)
Ad-hoc On-demand Distance Vector (AODV)
Geo-routing
Motion assisted routing
On Demand Routing - Readings
• D. B. Johnson and D. A. Maltz, "Dynamic Source
Routing in Ad-Hoc Wireless
Networks," Mobile Computing, 1994.
Charles E. Perkins and Elizabeth M. Royer. "Ad
hoc On-Demand Distance Vector
Routing." Proceedings of the 2nd IEEE Workshop
on Mobile Computing Systems
and Applications, New Orleans, LA, February
1999, pp. 90-100.
On-Demand Routing Protocols
• Routes are established “on demand” as
requested by the source
• Only the active routes are maintained by each
node
• Channel/Memory overhead is minimized
• Two leading methods for route discovery: source
routing and backward learning (similar to LAN
interconnection routing)
Dynamic Source Routing (DSR)
• Forwarding: source route driven instead of hop-by-hop
route table driven
• No periodic routing update message is sent
• The first path discovered is selected as the route
• Two main phases
– Route Discovery
– Route Maintenance
DSR - Route Discovery
• To establish a route, the source floods a Route Request
message with a unique request ID
• The Route Request packet “picks up” the node ID numbers
• Route Reply message containing path information is sent
back to the source either by
– the destination, or
– intermediate nodes that have a route to the destination
• Each node maintains a Route Cache which records routes it
has learned and overheard over time
DSR - Route Maintenance
• Route maintenance performed only while
route is in use
• Monitors the validity of existing routes
by passively listening to
acknowledgments of data packets
transmitted to neighboring nodes
• When problem detected, send Route
Error packet to original sender to
perform new route discovery
Ad hoc On-Demand Distance Vector (AODV)
• Primary Objectives
– Provide unicast, broadcast, and multicast capability
– Initiate forward route discovery only on demand
• Characteristics
– On-demand route creation
– Two dimensional routing metric: <Seq#, HopCount>
– Storage of routes in Route Table
Unicast Route Discovery
• Source broadcasts Route Request (RREQ)
• Node can reply to RREQ if
– It is the destination, or
– It has a “fresh enough” route
to the destination
• Otherwise it rebroadcasts the request
• Nodes create reverse route entry
• Record Src IP Addr / Broadcast ID
to prevent multiple rebroadcasts
Source
Destination
Route Request Propagation
Forward Path Setup
• Destination, or intermediate node
with current route to destination,
unicasts Route Reply (RREP)
to source
• Nodes along path create forward
route
• Source begins sending data
when it receives first RREP
Source
Destination
Forward Path Formation
Path Maintenance
3’
3
1
Source
•
•
•
•
•
3’
Destination
2
4
Source
1
Destination
2
4
Movement of nodes not along active path does not trigger protocol action
If source node moves, it can reinitiate route discovery
When destination or intermediate node moves, upstream node of break
broadcasts Route Error (RERR) message
RERR contains list of all destinations no longer reachable due to link break
RERR propagated until node with no precursors for destination is reached
Georouting in ad hoc nets
•
References:
•
Brad Karp and H.T. Kung “GPSR: Greedy Perimeter Stateless Routing for
Wireless Networks”, Mobicom 2000
•
M. Zorzi, R.R. Rao, ``Geographic Random Forwarding (GeRaF) for ad hoc and
sensor networks: energy and latency performance,'' IEEE Trans. on Mobile
Computing, vol. 2, Oct.-Dec. 2003
•
H. Dubois Ferriere et al ”Age Matters: Efficient Route discovery in Mobile Ad
Hoc Networks Using Encounter ages”, Mobihoc June 2003
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
Geo routing – key elements
•
Greedy forwarding
–
–
–
Assume 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
Got stuck? Perimeter forwarding
GPSR vs DSR
GPRS commentary
• Very scalable:
– small per-node routing state
– small routing protocol message complexity
– robust packet delivery on densely deployed, mobile wireless networks
• Outperforms DSR
• Drawback: it requires explicit forwarding node address
– Beaconing overhead
– nodes may go to sleep (on and off)
Mobility assisted routing
• Mobility (of groups) will be shown to help scale
the routing protocol ( LANMAR)
• Can mobility help in other cases?
• (a) Mobility induced distributed route/directory
tree
• (b) Destination discovery (if coordinates not
know)
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
• 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);
• “Last encounter” routing: next hop is the node that last saw
the destination
•
Ref: H. Dubois Ferriere et al”Age Matters: Efficient Route discovery in
Mobile Ad Hoc Networks Using Encounter ages, Mobihoc June 2003.
Fresh algorithm – H. Dubois Ferriere, Mobihoc 2003
Ad Hoc Networks - Outline
• What is an Ad Hoc Network
• Ad hoc network projects at UCLA
– The ONR Minuteman project
– The NSF WHYNET project
• The MAC protocol
• Scalable routing
– On demand routing
– Proactive routing
• Bringing ad hoc networks to market
• The vehicular grid
• The future of ad hoc networking
Challenge in the AINS Project: Scalable
routing
•
•
•
•
Tens of thousands of nodes
Nodes move in various patterns
QoS communications requirements
Hostile environment – jamming
• On demand routing protocols require
“flood search”: too much O/H
• Enter Proactive Routing
Dest Sequenced Distance Vector (DSDV)
0
Routing table at node 5 :
Destination
Next Hop
Distance
0
2
3
1
2
2
Й
Й
Й
1
3
2
4
Tables grow linearly with # nodes
Control O/H grows with
mobility and size
5
Link State Routing
•
At node 5, based on the link
state pkts, topology table is
constructed:
0
1
2
3
4
5
•
0
1
1
0
0
0
0
1
1
1
1
1
0
0
2
0
1
1
0
1
1
3
0
1
0
1
1
0
4
0
0
1
1
1
1
5
0
0
1
0
1
1
0
{0,2,3}
1
3
{1,4,5}
{1,4}
2
4
Dijkstra’s Algorithm can then
be used for the shortest path
O/H grows linear with N
{1}
{2,4}
5
{2,3,5}
Making Link State “more” scalable
• Link State explodes because of Link State update
overhead
• Question: how can we reduce the O/H?
• Answer: “Topology reduction”
– (1) if the network is “dense”, use fewer forwarding
nodes
– (2) if the network is dense, advertise only a subset
of the links
• Result: IETF MANET OLSR : Optimal Link State
Routing
OLSR Overview
• In LSR protocol a lot of control messages are
unnecessarily duplicated
• In OLSR only a subset of neighbors (Multipoint
Relay Selectors) retransmit control messages
– Reduce flooding overhead
• OLSR retains all the advantages of LSR:
– Does not depend upon any central entity;
– Tolerates loss of control messages;
Optimized Link state routing (OLSR)
24 retransmissions to diffuse
a message up to 3 hops
Retransmission node
11 retransmission to diffuse a
message up to 3 hops
Retransmission node
MPR Selection
• MPR set need not to be optimal
– hard problem to find an optimal set
• Greedy heuristic:
– select node with best 2-hop cover increment
• MPR is recalculated after a change in onehop or two-hops neighborhood topology
Where do we stand?
• OLSR can dramatically reduce the “state” sent out on
update messages
• It effectively reduces the “working topology” in “dense”
networks.
• However, the state still grows with O(N)
• It cannot handle large scale nets in the thousands of nodes
• What to do?
APPROACH: use hierarchical routing to reduce table size and
table update overhead
Hierarchical Routing - multilevel partitions
3
1
Level = 2
HSR table at node 5:
DestID Path
2
3
1
Level = 1
4
2
6
3
1
Level = 0
(MAC addresses)
8
5
11
7
4
9
10
1
5-1
6
5-1-6
7
5-7
<1-2->
5-1-6
<1-4->
5-7
<3-->
5-7
Hierarchical
addresses
HID(5): <1-1-5>
HID(6): <3-2-6>
Fisheye State Routing
• Topology data base at each node
- similar to link state (e.g., OLSR)
• Routing update frequency decreases with
distance to destination
– Higher frequency updates within a close
zone and lower frequency updates to a
remote zone
– Highly accurate routing information about the
immediate neighborhood of a node;
progressively less detail for areas further
away from the node
Control O/H (Mbits/Cluster)
Control O/H vs. number of nodes
1.8
1.6
1.4
1.2
1
0.8
0.6
0.4
0.2
0
25
49
100
225
324
400
Number of nodes
On-demand
DSDV
HSR
FSR
Optimized Fisheye Link State Routing (OFLSR)
• OLSR + Fisheye Concept
• Different frequencies for propagating the Topology
Control (TC) message of OLSR to different scopes
(e.g. different hops away)
scope width
scope 4
scope 1
scope 2
scope 3
Scalability Property of OFLSR
• Scalability to Network Size
Data Packet Delivery Ratio
– Keep node density, increase # of nodes, no mobility
– OLSR configuration: hello interval = 2S, TC interval = 4S
– OFLSR configuration: 4 scopes, each scope is 2 hops except last one
1
0.9
0.8
0.7
0.6
0.5
0.4
0.3
0.2
0.1
0
OLSR
OLSR + FSR
100
200
300
400
Network Size (# of nodes)
Delivery rate vs Network Size
500
Our Approach: Landmark Routing
•
•
•
•
•
Main assumption: nodes move in groups
Groups are predefined or dynamically recognized
Node address = < group ID , Host address>
Landmark elected in each group
Landmarks advertisements maintain the landmark
overlay
Landmark
Logical Group
LANMAR Overlay Routing (cont)
• Builds upon existing MANET protocols
– (1) “local ” routing algorithm that keeps accurate routes
within local scope < k hops (e.g., OLSR)
– (2) Landmark routes advertised to all mobiles using
DSDV
Landmark
Logical Group
Landmark Routing In action (cont)
• Packet Forwarding:
– A packet to “local” destination is routed directly using
local tables
– A packet to remote destination is routed to Landmark
corresponding to logical addr.
– Once the landmark is “in sight”, the direct route to
destination is found in local tables.
• Benefits: low storage, low update traffic O/H
Landmark
Logical Subnet
Dynamic Group Formation
QuickTime™ and a
Microsoft Video 1 decompressor
are needed to see this picture.
LANMAR Overlay enhances MANET routing
schemes
We compare:
(a) MANET routing schemes: DSDV, OLSR and FSR;
and
(b) same MANET schemes, BUT with LANMAR
overlay on top
Delivery Ratio
LANMAR-DSDV
LANMAR-FSR
OLSR
LANMAR-OLSR
FSR
DSDV
•DSDV and FSR decrease quickly when number of nodes increases
•OLSR generates excessive control packets, cannot exceed 400 nodes
Physical, Mobile Backbone Overlay
• Landmark Overlay provides routing scalability
• However the network is still flat - paths have
many hops  poor TCP and QoS performance!!
• Solution: Mobile Backbone Overlay
• MBO is a physical overlay – ie long links
• MBO provides performance scalability
• LANMAR extends “transparently” to the MBO
Mobile Backbone Reconfiguration
QuickTime™ and a
Microsoft Video 1 decompressor
are needed to see this picture.
Variable Speed with 1000 nodes
Delivery fraction while increasing mobility speed
1
0.9
Delivery Fraction
0.8
0.7
0.6
0.5
0.4
0.3
H-LANMAR
0.2
Flat LANMAR
0.1
Flat AODV
0
0
2
4
6
Mobility Speed (m/s)
8
10
Ad Hoc Networks - Outline
• What is an Ad Hoc Network
• Ad hoc network projects at UCLA
– The ONR Minuteman project
– The NSF WHYNET project
• The MAC protocol
• Scalable routing
– On demand routing
– Proactive routing
• Bringing ad hoc networks to market
• The vehicular grid
• The future of ad hoc networking
Challenge : “commodity” ad hoc
networks
• Military and civilian (disaster recovery) and hoc networks
are motivated by:
–
–
–
–
Instant deployment
Lack of infrastructure
Very specialized mission/function
Cost not most critical issue
• Commercial, “commodity” ad hoc networks have different
requirements
– Cost is an issue (eg, ad hoc vs W-LAN vs 2.5 G)
– Connection to Internet is desirable (sometimes, a “must”)
– Multipurpose networking
• Enter “opportunistic ad hoc networking
Vision: Opportunistic Ad Hoc Networking
Commodity ad hoc networks will not “happen” as isolated,
self configured nets
Rather, they will coexist with the “infrastructure”
Ad hoc extensions (of Wireless Internet)
–
–
–
–
–
–
Indoor W-LAN extended coverage
Indoor network appliances (Bluetooth, Home RF)
Hot spots (Mesh Networks)
Campus, shopping mall, etc
Aircraft cabins
Urban vehicle grid
Urban “opportunistic” ad hoc networking
From Wireless to
Wired network
Via Multihop
Ad Hoc networking for Accident Recovery
Urban Ad Hoc net in action: Safe Driving
Vehicle type: Cadillac XLR
Curb weight: 3,547 lbs
Speed: 75 mph
Acceleration: + 20m/sec^2
Coefficient of friction: .65
Driver Attention: Yes
Etc.
Vehicle type: Cadillac XLR
Curb weight: 3,547 lbs
Speed: 65 mph
Acceleration: - 5m/sec^2
Coefficient of friction: .65
Driver Attention: Yes
Etc.
Alert Status: None
Alert Status: None
Alert Status: Inattentive Driver on Right
Alert Status: Slowing vehicle ahead
Alert Status: Passing vehicle on left
Vehicle type: Cadillac XLR
Curb weight: 3,547 lbs
Speed: 75 mph
Acceleration: + 10m/sec^2
Coefficient of friction: .65
Driver Attention: Yes
Etc.
Alert Status: Passing Vehicle on left
Vehicle type: Cadillac XLR
Curb weight: 3,547 lbs
Speed: 45 mph
Acceleration: - 20m/sec^2
Coefficient of friction: .65
Driver Attention: No
Etc.
Opportunistic piggy rides in the urban mesh
Pedestrian transmits a large file in blocks to the
passing cars, busses
The carriers deliver the blocks to the hot spot
Ad Hoc Networks - Outline
• What is an Ad Hoc Network
• Ad hoc network projects at UCLA
– The ONR Minuteman project
– The NSF WHYNET project
• The MAC protocol
• Scalable routing
– On demand routing
– Proactive routing
• Bringing ad hoc networks to market
• The vehicular grid
• The future of ad hoc networking
Hot Spot
Hot Spot
STOP
Power
Blackout
Hot Spot
Hot Spot
STOP
Power
Blackout
CarTorrent : A Swarming
Protocol for Vehicular
Networks
You are driving to Vegas
You hear of this new show on the radio
Video preview on the web (10MB)
Highway Infostation download
Internet
file
Partial download from Infostation
Internet
Download
Co-operative P2P Download
Internet
P2P Exchange of Pieces
Vehicle-Vehicle Communication
Ad Hoc Nets: the Future
• Commercial ad hoc networks will happen first as
“opportunistic extensions” of the wireless
infrastructure (3G, WLANs, Satellites, sensor fields,
etc)
• Ad hoc nets will play an important role in the 4G
wireless generation
• Aggressive research is critical for the smooth
integration of ad hoc into 4G:
–
–
–
–
P2P protocols
Soft handoff
Security
etc
The End
Thank You!