Transcript Location Directory Services

Location Directory Services
Vivek Sharma
9/26/2001
CS851: Large Scale Deeply
Embedded Networks
Overview




Problem Statement
Related work
Design Issues
Papers we shall discuss today
–
–


Grid’s Location Service (GLS)
Randomized Database Groups (RDG)
Comparison and Issues
Conclusion
Problem Statement

A directory service for a sensor network where
nodes can lookup the geographical location of
other nodes. The service implementation
should be
–
–
–
–
Distributed among the nodes
Resilient to node failures
Scalable to a large number of nodes
Should have low memory and communication/power
overheads
Related Work

Location Management in Mobile Systems
–
–
–

Ad Hoc Networks
–
–

tracking mobility of users to route calls efficiently
the network has fixed nodes with much more resources
most of the architectures are hierarchical and thus not fault
tolerant
conditions closest to a typical sensor network (no fixed
infrastructure)
additional power, communication and scalability issues apply
Smart Spaces
–
–
locating people and equipment in an office like environment
relative to a fixed set of wireless receivers
Related Work

Peer-to-Peer Applications
–
–

a distributed service to locate nodes with particular data items
no resource limitations or mobility in the system
Resource Location Problems
–
spatial gossip algorithms
Design Issues
Proactive
vs.
(maintaining location
information continuously)
Deterministic
(on demand determination)
vs.
(e.g., hashing or ID mapping)
Hierarchical
arrangement of location servers
Reactive
Non-Deterministic
(randomized approaches in
choosing location servers)
vs.
Flat distributed set of
location servers
Deterministic vs. Non-deterministic approaches



Non-deterministic approaches as opposed to
deterministic approaches are usually inherently
resilient and are capable of handling large degrees of
node failure and mobility
The main problem while using a random approach is to
control the randomization to provide desired behavior
and to reduce the overheads of a random approach
In deterministic approaches, one has to especially
work towards providing fault-tolerance. Generally, its
extra work to ensure that a system is resilient to
failures
Papers to be covered

Grid’s Location Service (GLS)
–
–

A scalable location service for geographic ad hoc routing –
Jannotti et al (MIT)
a location service based on selecting location servers based
on node ID hash values
Randomized Database Groups (RDG)
–
–
Ad-hoc mobility management with Randomized Database
Groups - Haas and Liang (Cornell)
a non-deterministic approach towards maintaining location
information
Grid’s Location Service (GLS)
GLS Overview




The location service is used to enable geographical
ad-hoc routing
The network is divided into ordered grids or squares
and each node is aware of the divisions
Each node determines its geographic position using a
mechanism such as GPS
Every node maintains a table of its current neighbor’s
identities and locations (each node broadcasts periodic
HELLO packets)
GLS Overview



Location Servers: Every node selects a group of nodes
(location servers for that node) distributed throughout
the network, where it maintains its current location.
Routing: the location of the destination is determined
by performing a location query and routing is then done
using Geographic Forwarding.
Geographic Forwarding: When a node needs to send a
packet towards location P, the node forwards the
packet to the node amongst its neighbors which is
closest to P.
Example
90
38
70
37
Order 3
91 62
1
Order 2
26
14
51
35
2 B:17
98
Order 1
61
31
50
5
23 63
44
39
45
43
11
19
B’s location
servers
72
41
28
10
6 21
76
20
84
Selecting and Querying Location Servers


Selection: A node recruits other nodes with IDs close
to its own ID as its location servers. Location servers
are selected in each sibling of a square that contains
the node.
Querying: A sends a request to the least node greater
than B for which it has information. That node forwards
the query in the same way. Eventually the query will
reach a location server of B which will forward the
query to B itself. B can now respond directly.
Querying Location Servers:
Example
90
38
70
37
91 62
1
5
26
23 63
44
14
50
51
35
2 B:17
98
61
31
39
45
43
11
19
72
41
28
10
6 21
A:76
20
84
Updating Location Information


A node updates its order-2 location servers every time
it moves a threshold distance d, its order-3 servers
when it moves a threshold distance 2d, and so on. So,
a node sends out updates proportional to its speed and
updates are sent to distant servers less often than to
local servers
Forwarding Pointers are used at the order 1 grid to let
farther nodes route correctly when a node moves out of
its square
Simulation Scenario


Monarch – CMU’s wireless extensions for ns.
802.11 Radio
–
–




Bandwidth:1Mbps
Radio range: 250m.
100 nodes/km2
Order-1 square side – 250 m
Mobility – “random waypoint” model
Network of 600 nodes – the scale of a campus or city
Results
Scalability of GLS
Results
Performance of GLS in
the presence of mobility
Results
Performance of GLS
with node failures
Pros and Cons

Pros
–
–

Each node has to maintain a small amount of state
The querying technique is not paralyzed by failure of location
servers
Cons
–
–
–
Prone to performance degradation due to node failures and
high degrees of mobility
Fixed size squares; nodes in high density areas have to
maintain more state information so there is much more stress
on these nodes in terms of power
The nodes should know the GRID structure beforehand
Randomized Database Groups
(RDG)
RDG Overview




A set of location databases form a virtual backbone,
which is dynamically formed and distributed among the
nodes.
Location update – a node writes its location to a
randomly chosen group of k databases
Location lookup – A randomly chosen group of k
databases is queried.
The destination node location is provided to the source
by the databases at the intersection of the queried
database group and the group last written to by the
destination node.
The virtual backbone


Formation: During initial setup, network
flooding could be used to find the set of nodes
that best serve as the backbone (e.g. uniformly
distributed)
Maintenance: When a backbone node is
detached from the network, a nearby nonbackbone node is recruited to take its place
Randomized Database Groups




Given a virtual backbone with n location databases,
any combination of k databases forms a RDG
When a node needs to update its location information,
it uses any “accessible” RDG out of the nCk possible.
Same for location query
k could be different for different nodes depending on
the node’s traffic and mobility patterns
With appropriately chosen k, the probability of nonintersection between the set of databases queried and
the set of databases updates can be made sufficiently
small
Example
1
n = 6 databases
2
e.g. of RDG:
all combinations of size k=3:
{{1,2,3},{1,2,4},{1,2,5},….}
A node accesses the set of
databases through the database
nearest to it.
3
B
5
A
4
6
Virtual Backbone and the Location Databases
Mobile Location Updates



Call-origination update: the querying node
writes its current location into the queried
databases.
Location-change update: When a node
changes location, it updates its new location in
a RDG.
Periodic Update: Apart from the above, a node
sends location information at every interval.
Mobility Management Costs






pe = probability that a database is inaccessible at any time instant.
fo(t) = PDF for the length of time between any two consecutive call
originations
fm(t) = PDF for the length of time between any two consecutive
location change updates.
Tp = Periodic update interval
cu = expected cost of accessing a database
cl = expected miss penalty.
1

1
1



 Tp  tfo(t )dt  tfm(t )dt 
Cupdate = k cu 
Closs = cl X Expected number of lost calls per unit time
Optimal RDG size determination
We can see that even for high pe, optimal cost is
achieved with low k due to the tradeoff in the
cost metric
Pros and Cons

Pros
–
–
–

Allows tuning of performance based on expected parameter
values for the system
Expected to handle large degrees of node failures well
Can be made adaptive to each node’s traffic and mobility
patterns
Cons
–
–
–
Communication overheads could be significant with respect to
other approaches due to maintaining redundant location info
Greater load on the location databases – so life time could be
low for those nodes (although these nodes need not be “on” all
the time)
Analytical results, a lot of assumptions. Unfortunately no
simulations to get an idea of performance in scenarios
Comparison
GLS


Deterministic ID based technique
to select location servers
Scalability
–
–


State maintenance overheads
are low
Location information is spread
out on all nodes (Asm: density)
Reasonably resilient to node
failures due to less state info and
robust querying method
Performance degradation in the
presence of a high degree of
mobility and node switch-offs
could be significant
RDG


Non-deterministic selection of
location databases
Scalability
–
–


k is likely to be high implying
storing more state information
Location servers are especially
marked out and hence greater
load on them (power)
Inherently fault resilient due to
the random approach
Expected to handle high
degrees of node mobility and
node switch-offs better (though
maybe at a higher cost?)
Conclusions



A randomized approach is attractive because of its
inherent capacity to handle high degrees of mobility
and provide high degrees of resilience
But some of these advantages could be offset by the
amount of overheads due to redundancy in the state
information maintained
The GLS technique uses techniques similar to hashing
to distribute location information evenly on the set of
nodes and uses intelligent heuristics to provide a
robust location querying service
Some Issues

The implementation of a location directory service
could impose significant overheads on the system
Questions to ask –
Do we really need a location directory service?



ID-less routing, Directed Diffusion
Is the value added more than the costs?
It might not sound feasible or necessary to have a
global location service for sensor networks. One could
consider having
–
–
a higher level directory service to map Data or Tasks to
locations, and
a lower level directory service to map node-IDs to locations
within groups
Thanks!!
Vivek Sharma