Transcript CMPE 293: Wireless and Mobile Networking

CMPE 257: Wireless and
Mobile Networking
Spring 2002
Week 9
CMPE 257 Spring 2002
1
Announcements



Project status update.
Midterm grading.
Project demos and poster session.



Demos: May 31 – June 3.
Poster session: June 4.
Project deliverables.



Well-documented code.
README file explaining the contents of each file,
etc.
Short write-up (3-5 pages) describing architecture,
code structure, demo, lessons learned, etc.
CMPE 257 Spring 2002
2
Today

Location Management.
CMPE 257 Spring 2002
3
Why is location management
needed?

In wired networks, hosts don’t move.


Constant association between host (id,
address) and its location.
In mobile wireless networks, hosts can
move.


Host id/address no longer provides location
information.
Need location tracking mechanism to
deliver information destined to host.
CMPE 257 Spring 2002
4
Location databases


Home Location Register (HLR).
Visitor Location Register (VLR).
CMPE 257 Spring 2002
5
Home location register (HLR)



One HLR for each network.
User permanently associated to a HLR.
HLR keeps user profiles for each user.




Location information.
Services subscribed.
Billing information.
User profiles can be centralized in HLRs.

Problems?
CMPE 257 Spring 2002
6
Visitor location register (VLR)


VLR stores information about MHs
visiting the area.
Number and placement of VLRs vary.


One per network.
Tradeoffs?
CMPE 257 Spring 2002
7
Location lookup

When A wants to communicate with B,
A needs to find B’s location.


In HLR-only systems:


Response time is important!
A queries B’s HLR.
IN HLR-VLR systems:

Query local VLR first.
CMPE 257 Spring 2002
8
Location management

Standards:

Interim Standard 41 (IS-41).


GSM MAP.


North America.
Europe.
Both use 2-level location database
hierarchy
CMPE 257 Spring 2002
9
Location management tasks


Location registration.
Call delivery.
CMPE 257 Spring 2002
10
Location registration


Update location databases (HLR and
VLRs).
MH authentication when location info
available.
CMPE 257 Spring 2002
11
More on location registration…

MH performs location update.

Coverage area split into registration
(location) areas (RAs or LAs).


RA consists of several cells under same MSC.
VLR covers a number of RAs.
CMPE 257 Spring 2002
12
Location registration
procedure







MH moves to new cell and sends location update to
new BS.
BS informs MSC which contacts VLR.
VLR updates user profile for MH.
If new RA belongs to same VLR, update profile with
new RA info.
Else, VLR contacts MH’s HLR and updates MH’s HLR’s
location information.
HLR authenticates MH and sends ACK to new VLR;
HLR also de-registers MH with old VLR
Old VLR sends an ACK.
CMPE 257 Spring 2002
13
Call delivery

2 steps:


Finding current VLR.
Locating the MH current cell.
CMPE 257 Spring 2002
14
Call delivery procedure






Caller contacts callee’s MSC through nearby
BS.
MSC finds address of callee’s HLR and
contacts HLR.
HLR finds callee’s current VLR and MSC.
Connection is set up between caller and
callee’s MSC.
Polling to find where callee is within RA
(paging).
Callee responds.
CMPE 257 Spring 2002
15
Issues [Akyildiz96]

Location registration and call delivery
are expensive.

Signaling traffic.
CMPE 257 Spring 2002
16
Solutions

Still keeping the 2-level database
model.



Caching MH’s VLR.
Pointer forwarding: setting pointers from
previous VLR to new VLR.
Local anchor: use “nearby” VLR to receive
location updates from MH.


HLR keeps pointer to local anchor.
“Localizes” signaling traffic.
CMPE 257 Spring 2002
17
Solutions (Cont’d)

Deeper hierarchies.





Tree of location databases.
Leaf databases contain information on local MHs.
Higher level databases contain pointers (MH
id+database id) to next lower level database
storing profile or pointer to lower level.
In the worst case, query travels all the way to
root, down the appropriate subtree.
Partitioned databases.


Groups of location databases.
No location update if MH moves within same
partition.
CMPE 257 Spring 2002
18
HiPER [Jannink97]

Life-long numbering.


Same number irrespective of provider/location.
Hierarchical location database.





No concept of a “home site” (HRL/VRL).
Leaf databases store user profiles in a zone.
Higher-level databases store pointers to lowerlevel.
Root stores pointer to every user.
Scalability?
CMPE 257 Spring 2002
19
Locating a user…




When A calls B, query for B’s location
propagates up the hierarchy from A’s zone to
first database containing pointer to B; then,
down that subtree.
Drawbacks?
When a user moves, its record is sent to the
appropriate leaf database; databases along
the way to the least common ancestor for old
and new zones are updated.
How expensive is this?
CMPE 257 Spring 2002
20
Replication




Replicate user profile at other databases
in the hierarchy.
Tradeoff: lookup latency versus update
and storage cost.
“Lazy” consistency.
Where to replicate?


Locality of calls and mobility.
Also use intermediate nodes in the tree.
CMPE 257 Spring 2002
21
Replication parameters

Number of replicas.


Bound on storage requirements and/or number of
updates.
Replication cost-benefit.

Local call-to-mobility ratio (LCMR).




Benefits: number of local calls to user.
Cost: number of moves during given time period.
Ri,j = Ci,j/Mi.
Min and max threshold.
CMPE 257 Spring 2002
22
More parameters…

Highest hierarchical level user profile
may be replicated.


If site j replicates user i’s profile, all
ancestors of j will also be replicas.
L sets upper bound on replication level.
CMPE 257 Spring 2002
23
Off-line replica allocation



Inputs: database topology and estimated
LCMR.
Output: replication plan which is sent to the
databases.
1st. phase: bottom-up traversal.


For each user i, assign it to replica j if LCMRij >=
Rmax.
If n=N, additional replicas below L with
largest LCMRij-Rmin assigned to user i.
CMPE 257 Spring 2002
24
Evaluation

Implemented their own event-driven
simulator (Pleiades).



User movement models.
User calling models.
Simulations.


Model of the Bay Area geography and
demographics.
Compared several location management
techniques: HLR/VLR, centralized, caching, full
replication, simple hierarchy (no replication), hiper.
CMPE 257 Spring 2002
25
Location Management by
[Prakash96]

System model: cellular architecture.




Cells, base stations, MHs, location servers.
Node wishing to communicate with MH
needs to find MH’s location (cell).
Once location is determined, info sent to
BS (over wired network), who relays to
MH.
BS co-located with location servers.
CMPE 257 Spring 2002
26
Motivation

Distribute location management load
evenly across location servers.

Avoid “hot spots”.
CMPE 257 Spring 2002
27
Problem statement
“Which location servers will store an MH’s
location?”
 Single location server?
 Multiple statically assigned location servers?
 Multiple location servers based on MH’s
location?
 Multiple location servers based on location
and identity.
 Location servers change as MH moves.
 MHs in same cell will map to different sets of
servers.
CMPE 257 Spring 2002
28
Problem statement (cont’d)
“Given an MH and its current location (given by
the current BS), determine set of location
servers given the MH’s id and its location.”, or
h: BSxMH -> SBS.
 Function h determines the read set (replicas
to query when trying to locate MH) and write
set (replicas to update when MH moves) for
MH.
 Multiple id’s assigned to popular MHs.

Why?
CMPE 257 Spring 2002
29
Assigning location servers

Mapping MH id to virtual id.




“Cold” MHs have single id.
“Hot” MHs have multiple (two) ids.
Use hash function to map MH’s virtual id and
its BS id to set of BSs.
Quorum construction: partitioning BSs into
sets.

Small size (update load) and symmetric (load
balancing).
CMPE 257 Spring 2002
30
“Active” location management


Previously described systems rely on
MHs to update their location.
Some more recent systems take a
proactive approach: detect user and
figure out location (positioning).
CMPE 257 Spring 2002
31
Location for the Active Office
[Ward97]



Indoor sensor system that tracks
location of: people (active badge),
equipment (equipment tags), etc.
Requirements: accurate (within 15cm),
3 dimensions, scalable (number of
objects locatable, area covered), cost.
RF communication.
CMPE 257 Spring 2002
32
System components



Transmitters attached to every locatable
object.
Matrix of receiver elements in all rooms
where objects are to be tracked.
Controller which polls one mobile object
at a time.
CMPE 257 Spring 2002
33
Operation




Periodically, mobile node is polled.
Polled mobile broadcasts signal.
Controller synchronizes receivers, who
listen for some time to detect the peak
of mobile’s transmission.
Controller polls receivers for the
measured time interval between the
sync signal and the signal peak (if any).
CMPE 257 Spring 2002
34
Distance computation


Time measured by receiver composed
of: time to transmit the polling
signal+time to transmit pulse (function
of distance being
calculated)+processing time.
Distance between mobile and receiver
calculated.

Empirically computed speed of sound in
the room and service times.
CMPE 257 Spring 2002
35
Position calculation



Triangulation using 4 receivers to
determine a point in 3 dimensional
space as estimate of position.
In this particular set up, since all
receivers are in the ceiling, only 3
distances required.
Extra reported distances can be used
for higher accuracy.
CMPE 257 Spring 2002
36
Evaluation





Experiments with prototype show 95% of
readings within 14cm accuracy. Even better
accuracy for averaged readings.
Addresses limit number of trackable objects.
Large number of receivers and ultrasound
nature of transmission from mobile proved to
pay off regarding accuracy.
Power savings mode minimizes maintenance.
Low interference levels from office
equipment.
CMPE 257 Spring 2002
37