Transcript Scalable Location Management for Large Mobile Ad Hoc Networks

Scalable Location Management for
Large Mobile Ad hoc Networks
Sumesh J. Philip
Contents
Wireless Ad hoc networks


Issue of Scalability
Geographic Routing
Scalable Location Update based Routing
SLALoM - Scalable Location Management
Grid Location Service
Hierarchical Grid Location Management
Simulations and Results
Conclusion
Wireless Ad hoc networks
Infrastructure-less networks that can be easily
deployed
Each wireless host acts as an independent router
for relaying packets
Network topology changes frequently and
unpredictably
How to route packets?
Quite a lot of protocols proposed in literature
(table driven/reactive/hybrid)
Dynamic source Routing (DSR) works well for
small networks
Issue of Scalability
Increasing density increases average node
degree, decreases network diameter


Routing cost less
Any reasonable scheme might work!
To test scalability, area (playground size) must
increase with nodes


Average node degree constant
Will present a mobility model that consolidates the
above relationship
Traditional Protocols
Table driven


incur large overheads due to routing table
maintenance
Delayed control as good as no control
On-demand



flood the entire network with discovery packets
long latency for discovery
Path maintenance means additional state
No separation between data and control
Ultimately, data suffers!!
Any contenders ?
Not many invariants to play with (IP address,
local connectivity)
Nodes physically located closer likely to be
connected by a small number of radio hops
Possible to obtain node location via a GPS
receiver
Geographic forwarding


Packet header contains the destination’s location
Most forward with fixed radius
Geographic Forwarding
C’s radio range
A
D
C
B
F
G
E
A addresses a packet to G’s latitude, longitude
C only needs to know its immediate neighbors to forward
packets towards G.
Geographic forwarding needs location management!
Desirable Properties of
Location Management
Spread load evenly over all nodes
Degrade gracefully as nodes fail
Queries for nearby nodes stay local
Per-node storage and communication costs grow
slowly as the network size grows
Scalable Location based
Routing Protocol (SLURP)
Hybrid Protocol that has a deterministic manner
of discovering the destination
Topography divided into square grids
Each node (ID) selects a home region using
f(ID), and periodically registers with the HR
Nodes that wish to communicate with a node
query its HR using f--1(ID)
Use geographic forwarding to send data, once
location is known (e.g. MFR)
Example
[12]
- Home region
ID = 22; RT= 12;
HR=22%12 = 10;
- Update/Query
[10]
- Data
- Location
Database
f(ID)
- ID Mod(RT)
DST = 22;
RT= 12;
HR=22%12 = 10;
Cost of Location Management
Location Registration


Periodic
Triggered
Location Maintenance

Operations for database consistency
Location Discovery

Query/response
Data Transfer
Mobility Model
Each node moves independently and randomly
Direction [0  2 ] , Velocity [v-c, v+c] at t
New direction and velocity at destination
2

r
t
Node degree =
N
A
To keep degree constant, A must grow linearly
with N
Location update Overhead
  rate of region crossing
b  broadcast cost
u  number of hops
v  velocity of node
rt  transmiss ion range
2 R  side of region
a  area of region

v
2

 2 RCos d

v
4R
Location U pdate cost (cu )   (b  u ) / sec
 a 
b 1  2 
 rt 
Location update Overhead
z  most forward progress
n  average node degree
  mean inter - node distance
Az  Area of excluded region
  Average nodes in a region
G
N

 Number of regions
d R G R
N
v 2
N
(R  R
)
R

 O (v N )
1 e

cu   (b  u )   (b 

f z ( z) 
2 rt 2  z 2
rt
d
)
z
z   zf z ( z )dz
0
n
2
e Az
Home Region Maintenance
On region crossing
Inform previous region of departure
Inform new region of arrival
Update from any node in new region
cm   (2b   ); 1    
 a 
(2(1   2  )   )
4R
 rt 
Maintenanc e Overhead  O(v)

v
N  Total number of nodes
  Average number of nodes per region
Total Overhead
Cost of Locating
Send a Location query to Home region
cl  2u  2
d
 O( N )
z
Total Overhead = Sum of all overheads for all nodes
c  cu  cm  cl
 Nv N  Nv  N N
 O(vN N ) / sec
ScaLAble Location
Management (SLALoM)
Define a hierarchy of regions : Order(3), Order(2),
Order(1)
Each Order(2) region consists of K2 Order(1) regions
Each node assigned a HR in an Order(2) region
To reduce location update overhead, define far and
near HRs; near regions updated frequently
Nodes that wish to communicate with another node
query its HR in current Order(2) grid
Queries from far HRs find way to near ones for exact
location of destination
Protocol Operation
- Order 3
- Order 2
- Home region
- Update/Query
- Data
- Location
Database
K=3
Control Overhead
Location Update
Maintenance Overhead
cu  O( 1 (9b 2  un )   2 (
cm  1 (2b   ); 1    
 O (v )
 O(vK 
Cost of Locating
cl  O (
K
K
)  O( )
z
z
Total Overhead
N2
c  O(vKN  v 2 );
K
4
3
 O(vN )
minimized at K  N
1
3
vN
)
K2
Ab
 u f ))
K2
Grid Location Service (GLS)
sibling level-0
squares
sibling level-1
squares
sibling level-2
squares
s
n s
s
s
s
s
s
s
s
• s is n’s successor in that square.
(Successor is the node with “least ID greater than” n )
GLS Updates
... 1
11
2
...
9
1
9
11, 2
6
23
23, 2
Invariant (for all levels):
For node n in a square,
n’s successor in each
sibling square “knows”
about n.
...
3
...
2
16
29
...
7
6
...
...
17
...
26
...
21
5
...
25
...
4
...
location table content
8
...
19
location update
GLS Query
... 1
11
2
...
9
1
9
11, 2
6
23
23, 2
...
3
...
2
16
29
...
7
6
...
...
17
...
26
...
21
5
...
25
...
4
location table content
...
8
...
19
query from 23 for 1
HIEARCHICAL GRID LOCATION MGMT
Motivations
 Current solutions do not scale well or not robust with node
mobility
 Do not consider localized mobility or local communication needs
 Although there are grid based solutions, they use a single layer for
location management, and hence can be improved
Contributions
 Proposed a multi-layer Grid scheme which uses hierarchical
location management, suitable for large networks
 Analyzed cost for location management overhead
 Show that the proposed scheme performs better in large, dense
systems
LOCATION REGISTRATION
Mobile Node
Movement
Update msg
Nodes in unit grid aware of each other by
periodic broadcast
Nodes located in a region act as location
servers
Hierarchy of a server decided by its
position as well as the locale of the region
Nodes update servers as they cross grid
boundaries
Number of updates, and distance traversed
by the updates depends upon boundary
hierarchy
Localized movement results in few updates
that traverse short distances
LOCATION MAINTENANCE
Location
database
to store ?
A (A_loc)
B (B_loc)
…
Mobile Node
Movement
On entry into a grid, a node
announces its presence
If the unit grid is a server
region, a node already present
in the region replies with
location information that the
newly arrived node has to store
Use of timers to avoid a
broadcast storm
LOCATION DISCOVERY
& DATA TRANSFER
Query msg
Response msg
Data
If source, destination located in the
same unit grid, they can talk directly
If not, source initiates a query
message to discover the location of
the destination
Query visits leaders until the
approximate
location
of
the
destination is known
Data forwarded to the approximate
location
Data continues to be forwarded to
leaders that have more accurate
information of the destination or
until it reaches the destination
PERFORMANCE ANALYSIS:
Location Management Overhead
Observations
Cost of location management consists of registration, maintenance
and discovery
 The number of transmissions required per message proportional to
distance traversed by the message
 An update that resulted from an ith boundary crossing visits at
most (i +1) leader grids for (0  i  k )
 A query visits at most i leader grids, if source and destination
located in the same ith grid
Notations:

N - Number of Nodes
d - side of a unit grid
 - average nodes/unit grid
di - average distance for update
k - levels of hierarchy (
b - broadcast cost
log 2 N
)
2
for i th boundary crossing
 - rate of grid crossing
z - average forward progress
LOCATION REGISTRATION COST
Pr[
ith
server is updated]
= Pi 
1
2  (1  2k )( 2i  1)
k
(1  i  k )
Average distance traversed by update = D   Pi Di
2 2
k i 1
 2d (
)(
 1)  O(k ) for large k
k
4 k 1 2
Average number of broadcasts = b   iPi
k i 1
 2 k
 O(1) for large k
2 1
D
c


(
b)
Average location update cost = u
z
D
k
  (  O(1))    O( )
z
z
 O(   log 2 N )
 O(v  log 2 N ) packets/se c/node
LOCATION MAINTENANCE COST
When a node enters a new grid, it broadcasts its presence
A server node will respond with location information to store
In the worst case, all the nodes in the grid will broadcast back the
location maintenance message
1
Pr[node enters a server grid] =
4
Average location maintenance cost =
cm 
 b
4
(1   )
(1     )
 O(v) packets/se c/node
LOCATION DISCOVERY COST
Location query visits at most k leaders
Average distance for query in the kth grid = d k
3
 k (4 d1  4 2 d 2 ...  4 k 1 d k 1 ) 
4
24  32 k  31 4 k  7
42k
Assuming worst case distance in the ith grid,
3 2 k 1
dk 
(2  k )  O(2 k )
7
4
dk
2k
cd   ( )  O( )
Average location discovery cost =
z
z
 O(v N ) packets/se c/node
PERFORMANCE ANALYSIS:
Simulations (GloMoSim)
Compared against SLURP, a well known protocol in literature
Parameter values
 Topography size varied from 1000x1000m – 4000x4000m
 Node density 80 nodes/km2 (unit grid side 250 m)
 Transmission range 350 m, speed 2Mbps
 IEEE 802.11 MAC
 Random Waypoint mobility (Maximum speed 25 m/s, Minimum
speed 0 m/s, Pause Time 0s)
 Random, Constant Bit Rate traffic
 1024 bit payload
Performance Metrics
 Registration overhead, registration delay, data delivery ratio, data
delay
 Results shown for increasing number of nodes
RESULTS
Registration Overhead
Registration Delay
Data Delivery Ratio
Data Delay
CONCLUSIONS
Cost of location management is important in geographic forwarding
based protocols
Designed a multi-level grid ordering scheme for hierarchical location
management
Average location registration cost increases only logarithmically in
number of nodes for our scheme; hence scales well for large ad hoc
networks
Simulations show that our scheme outperforms SLURP
For dense networks, simulations indicate that the protocol is robust
with node mobility
For localized movements and local communication needs, hierarchical
grid location management should perform even better
References
C. Cheng, S. Philip, H. Lemberg, E. van den Berg, T. Zhang, SLALoM: A Scalable Location
Management Scheme for Large Mobile Ad-hoc Networks, to appear in Proceedings of
Wireless Communications and Networking Conference, March, 2002
Y. B. Ko, N. H. Vaidya, Location Aided Routing in Ad-Hoc networks, Proceedings of
ACM/IEEE Mobicom’98, Dallas, TX, Oct. 1998
Josh Broch, David A. Maltz, David B. Johnson, Yih-Chun Hu, and Jorjeta Jetcheva. A
Performance comparison of multi-hop wireless Ad-Hoc network routing protocols. In
Proceedings ACM/IEEE MobiCom, pages 85-97, October 1998.
Jinyang Li, John Janotti, Douglas S. J. De Couto, David R. Karger, and Robert Morris, A
Scalable Location Service for Geographic Ad Hoc Routing, The Sixth Annual International
Conference on Mobile Computing and Netwroking, pages 120-130, August 2000
Seung-Chul M. Woo and Suresh Singh, Scalable Routing in Ad-Hoc Networks, Technical
Report, TR00.001, March 2000
Basagni S. and Chlamtac, I. and Syrotiuk, V. R. and Woodward, B. A. A Distance Routing
Effect Algorithm for Mobility (DREAM), Proceedings of the Fourth Annual ACM/IEEE
International conference on Mobile Computing and Networking, MobiCom'98, pp. 76-84,
Dallas, TX, October 25-30, 998
K. Fall and K. Varadhan, NS notes and documentation, technical report, UC Berkeley, LBL,
USC/ISI and Xerox Parc, 1997. http://www.isi.edu/nsnam/ns