Transcript 2/17 - MMLab

AODV-OLSR Scalable Ad hoc Routing
J. Costa-Requena, T. Vadar, R. Kantolaand N. Beijar,
Helsinki University of Technology
Wireless Pervasive Computing
2006 1st International Symposium
16-18 Jan 2006
Wang Xiaofei
( [email protected] )
2006.05.16
1/17
Contents
1.Introduction
2.AODV-OLSR Scalable Ad hoc Routing Protocol
3.Virtual Backbone & Hierarchical Group
4.Simulation
5.Conclusion
2/17
1.Introduction (1/2)
Proactive Protocols
–
Build routes & exchange info among nodes periodically
• OLSR :Optimized Link State Routing
• DSDV :Dynamic Destination-Sequenced Distance-Vector
routing
…
Reactive Protocols
–
Build routes only when node requires
• AODV :Ad-hoc On-demand Distance-Vector routing
• DSR :Dynamic Source routing
• TORA :Temporally Ordered Routing Algorithm
…
3/17
1.Introduction (2/2)
Hybrid approaches
–
–
LAR :Location Aided Routing
ZRP :Zone Routing Protocol
• IARP :Intra-Zone Routing Protocol - proactive
• LERP :Inter-Zone Routing Protocol – reactive
…
–
SARP : Scalable Ad hoc Routing Protocol
4/17
2.AODV-OLSR Scalable Routing (1/2)
AODV-OLSR Scalable Ad hoc Routing Protocol
Two types of nodes:
–
Smart Node
• Have enough resources and willingness to maintain
route and service information.
• OLSR with other smart nodes for exchanging route
updates.
• AODV with dummy nodes.
–
Dummy Node
• Limited resources
• AODV only
5/17
2.AODV-OLSR Scalable Routing (2/2)
Scalable Ad hoc Routing
–
“Zone” : area of dummy nodes around a smart node
• Looks like an opposite approach to ZRP
–
Intra-zone : reactive (AODV)
• AODV suits much for small networks
–
Inter-zone : proactive (OLSR)
• OLSR suits much for relatively stable networks
• Smart nodes form virtual link paths
– Use OLSR in these paths.
– Virtual fully distributed backbone
6/17
3.Virtual Backbone & Hierarchical Group (1/4)
Virtual fully distributed backbone
virtual layer of backbone
Real network
Smart nodes create
virtual backbone and
exchange link state
information between
them for sharing
network topology
and increase the
overall scalability
Dummy nodes only
benefit from smart
nodes and use AODV
routing with others
7/17
3.Virtual Backbone & Hierarchical Group (2/4)
Hierarchical smart nodes group
–
–
Link State Updates
All the other smart nodes are included in different
group based on the distance (hop number)
Each smart node has OLSR route tables and
also a hierarchical group table
For example: This is
SmartNode1’s group table
SmartNode1 can take
6 hops to reach S7,
S10, S11 …
G1:
G2:
G3:
G4:
G5:
G6:
S2
S3, S4, S5
6
S8, S9
S7, S10, S11
“Group3” includes all
other smart nodes
located 3 hops away
How to form?
How to use?
8/17
Here is an example
network, and S1 is
requiring attachment
9/17
3.Virtual Backbone & Hierarchical Group (4/4)
Different routing
update frequency
G1:
G2:
G3:
G4:
G5:
G6:
S2
S3, S4, S5
6
S8, S9
S7, S10, S11
Far : lower freq.
Near: higher freq.
Link State Update
2K*T
Hop distance
T : minimum LSU
transmission period
10/17
4.Simulation (1/4)
SARP protocol is implemented in NS-2 integrating
existing implementations of AODV and OLSR
–
Parameters :
• Nodes :50
• Area :1500m x 300m
• 30 constant bit rate IP connections of 8packets/second
– 64 bytes/packet
• Mobility: 0 ~ 900s (pause time between movements)
• Average after 3 rounds of simulations
–
“SARP-10” : 10 smart, 40 dummy nodes
Comparison among signaling overhead, delay, data
throughput and node mobility
11/17
4.Simulation (2/4)
Routing overhead VS node mobility
12/17
4.Simulation (3/4)
Packet delay VS nodes mobility
Here, SARP-10&15 is
better than AODV !
13/17
4.Simulation (4/4)
Data throughput(%) VS Nodes mobility
Here, SARP-10 is
better than AODV !
Tradeoff : the density of smart nodes , node
mobility
14/17
5.Conclusion (1/2)
Conclusion:
–
–
–
Introduced and compared some Ad hoc routing
methods
Presented a new hybrid AODV-OLSR scalable routing.
Simulation and comparison
SARP has a good performance and even a little
better than AODV in some situations.
15/17
5.Conclusion (2/2)
Questions & future works:
–
–
–
Is it really feasible and effective to implement two
routing algorithms in one node…?
There should be a tradeoff on the ratio of smart nodes
number to dummy nodes number, then it could get
much better effect for various scenario ?
Scalability: in different situations, the density should
be able to be modified automatically to suit for the
whole network in order to get better performance.
16/17
Thank you !
Q&A or Comment
17/17