Transcript Document

Location-Based Services (LBS): An
Emerging Innovative Transport Service
Technology
STELLA Thematic Network
Focus Group 2 - ICT, Innovation and the Transport
System, Arlington, VA, USA
Jan 15-17, 2002
Tschangho John Kim, Professor
University of Illinois at Urbana-Champaign
7/20/2015
UP 419 S-01 wk 14 by Prof. Kim
1
Location-Based Services (LBS): An
Emerging Innovative Transport Service
Technology
•
•
•
•
•
Emergence of LBS
What is LBS?
Basic Use Cases
Location Service Concepts
Research Issues
– Accurate/Efficient Solution Algorithms
– Interoperability and Standard
7/20/2015
UP 419 S-01 wk 14 by Prof. Kim
2
Technical Business Innovations
1876
1980
1995
1999
2000
7/20/2015
Telephone
FAX
Internet
e-Everything
m – GIS and LBS
UP 419 S-01 wk 14 by Prof. Kim
3
Internet Users Worldwide
377.7 Million - September 2000
7/20/2015
UP 419 S-01 wk 14 by Prof. Kim
4
Mobile Location Based Services
“ The Internet will not be successfully
translated to the mobile world without
location awareness which is a
significant enabler in order to translate
the Internet into a viable mobile
economy”…
Bob Egan, Vice President
Mobile & Wireless, Gartner Group
7/20/2015
UP 419 S-01 wk 14 by Prof. Kim
5
SIM - Spatial Information Management
GIS
Business
Support Systems
Personal
Productivity
<5%
Current
Revenue
~ 75 %
~ 20 %
Growth Rate
2-5%
30 %
Potential Users
% Penetration
1999
< 1 Million ~ 8 Million
Near
Saturation
< 10 %
$ 1.1 billion USD worldwide
Too early
~ 20 Million
Too early
Nokia prognosis for 3G mobile
communication
Monthly income pr. user in euro (1 euro = 1 USD ca.)
100
Location based services
90
Div. telecomm.
80
Commercials
Text messages
Entertainment
70
Information services
Payment transactions
Music and video
Internet surfing
Download from internet
Chat on internet
Multimedia messages
Photo messages
60
50
40
Vide conferencing
30
20
Normal speech
10
Fixed subscription
fees
0
2000
2001
2002
2003
2004
2005
2006
2007
2008
2009
2010
2011
Spatial Trends
Spatially Enabled Society
Web-based
SIM
Mobile location based
services & solutions
Spatially Enabled Databases
Spatial
Development
Computer /
Automated
Cartography 1970
Geographic Information Systems
1985
1995
2000
2005
Time
7/20/2015
UP 419 S-01 wk 14 by Prof. Kim
8
Emergence of Location Based Services
Market Size
$10 Billion
Internet and Mobile
Location Services Market
$5 Billion
Inflection
Point
$1 Billion
GIS Market
1980
1990
2000
Time
2005
Recognizing the Value In Spatial
7/20/2015
UP 419 S-01 wk 14 by Prof. Kim
10
Location-Based Services (LBS): An
Emerging Innovative Transport Service
Technology
•
•
•
•
•
Emergence of LBS
What is LBS?
Basic Use Cases
Location Service Concepts
Research Issues
– Accurate/Efficient Solution Algorithms
– Interoperability and Standard
7/20/2015
UP 419 S-01 wk 14 by Prof. Kim
11
Thin Client of LBS: Cell Phone or PDA
7/20/2015
UP 419 S-01 wk 14 by Prof. Kim
12
7/20/2015
UP 419 S-01 wk 14 by Prof. Kim
13
7/20/2015
UP 419 S-01 wk 14 by Prof. Kim
14
The Pizza Story (circa 1997)
Voice
Recognition
“Want
Pizza!”
Pizza Place
Database
Nearest
Three
Map
Database
Broker
Location
Service
GPS
Preferences
Other Network
Services
7/20/2015
UP 419 S-01 wk 14 by Prof. Kim
Presentation
Service
15
Location-Based Services (LBS): An
Emerging Innovative Transport Service
Technology
•
•
•
•
•
Emergence of LBS
What is LBS?
Basic Use Cases
Location Service Concepts
Research Issues
– Accurate/Efficient Solution Algorithms
– Interoperability and Standard
7/20/2015
UP 419 S-01 wk 14 by Prof. Kim
16
Basic Use Cases
•
•
•
•
•
•
•
•
Provide Location
Location Calculus
Compute Route
Proximal Analysis
Proximal Search
Event Notification
Stolen Car
Mayday
7/20/2015
UP 419 S-01 wk 14 by Prof. Kim
17
Request for Location
GetLocation
Payload (object)
Location
Service
Location Payload
The Actor and the “object” may be the same or different,
and each may be mobile or fixed. The “object” can have
point, curve, segmented curve, or surface geometry.
The GetLocation Payload must specify the “type” of
location desired in the return payload.
7/20/2015
UP 419 S-01 wk 14 by Prof. Kim
18
Types of Location(1)
• Point Geometry
• Curve Geometry
• Segmented Curve, e.g.:
– a. 300 yards north of mile marker 143 on Interstate 66.
– b. Between two and three miles downstream from
reactor 3 on Two Mile Island.
– c. Third door on the right down this hall.
- d. At the intersection of 4th street and the city limits.
• Surface
7/20/2015
UP 419 S-01 wk 14 by Prof. Kim
19
Types of Location(2)
• Location Name
• Address and address range
• Types of Addresses:
–
–
–
–
–
7/20/2015
P.O. Box
Multiple Address Lines
Rural Routes
Apartment Numbering
Address Schema of Countries
UP 419 S-01 wk 14 by Prof. Kim
20
Provide Location
User
Needing
Location
Location data
Accuracy
Quality
etc.
Location
Needs &
Preferences
Requesting
Location
Device
Requester
7/20/2015
ID of item
To be located
Table of Fixed
Locations
Location
Target
Broker
Device
UP 419 S-01 wk 14 by Prof. Kim
Mobile
Location
Needs
Location
Target
Technology
Device
Triangulation,
GPS, etc.
21
Location Calculus
Request for Location
Calculus, preferences
Advanced
User
Results Payload
Location
Calculus
Service
•The LocationServices system
should address queries such as:
Broker
Thematic And
Regional
Catalog
Repository
–Where is the hardware store most convenient to my
route home?
– What are the three termite control companies nearest
my home?
7/20/2015
UP 419 S-01 wk 14 by Prof. Kim
22
Compute Route
Traveler
Request for
Route
with input
parameters
Route
(optimal
for chosen
parameters)
Compute
Route
Service
• Accepts origin and destination information
• Accepts real-time information (traffic,
reverse lanes, event & direction affected,
etc.)
• Accepts type of PathWay
–
–
–
–
Pedestrian - Automobile - Bicycle
Handicap – Electronic
Public Transportation
Multiple pickup and drop-off
• Accepts target function to optimize (e.g.,
time, cost, distance, or combination)
• Produces an optimal route of the desired
type
Real Time Data
7/20/2015
UP 419 S-01 wk 14 by Prof. Kim
23
Proximal Analysis
Needs &
Preferences
Broker
Regional
Point of
Interest
Server
Point of
Interest
Client
• What’s Within Proximity And Matches
Needs and Preferences
–- Walking, or by Auto, etc.
– Points of Retail Outlet
– What’s showing?
– What’s on Sale?
– Open Sessions with discovered “hits”
Regional
PoI
“Repository”
7/20/2015
–Time to be served
UP 419
S-01 wk 14information
by Prof. Kim
–Special
24
Event Notification
• Assesses impact of events on
one’s route
Event
Notification
parameters
Updated
Route
& Event
Notification
Event
Notification
Service
Event description
And duration
7/20/2015
– Duration
– Direction
– Hazmat Warning
• Triggers En-Route Update if
impact above threshold
External
Events
UP 419 S-01 wk 14 by Prof. Kim
25
Stolen Car, Mayday, Locked Key,
Assistance Request
• Triggers notification of
authorities
preferences
Periodic
Locate
Feedback
Stolen car
Service
Periodic
Notice
7/20/2015
Mayday
Service
Locked Key
Service
Notice
Notice
Assistance
Request Service
Notice
Authorities
UP 419 S-01 wk 14 by Prof. Kim
26
Location-Based Services (LBS): An
Emerging Innovative Transport Service
Technology
•
•
•
•
•
Emergence of LBS
What is LBS?
Basic Use Cases
Location Service Concepts
Research Issues
– Accurate/Efficient Solution Algorithms
– Interoperability and Standard
7/20/2015
UP 419 S-01 wk 14 by Prof. Kim
27
Location Service Concepts
 The
–
–
–
–
–
–
–
–

Device
Cell phone
Palm top
Lap-top
Kiosk
Car-based computer
Cell antenna
Mobile device
Display
Actors
7/20/2015

The Location
–
–
–
–
–
–
–
–
Point and Reference
Segmented Line
Address
Route
Descriptive Directions
Gazetteer
Direction
Polygon
 Payload
Items
UP 419 S-01 wk 14 by Prof. Kim
The Service

–
–
–
–
–
–
–
–
Routing
Avoiding Traffic
Tourism
Regional Attractions
Event Handling
Maps and Backdrops
Guidance
Preference
 Service
Providers
28
Building Blocks of Location
Services
Basic Functions
Position
Distance
Route
Selection
Proximity
Description
Directory
Area
Distribution
Relationship
Suitability
Presentation
Inventory
Frequency
Pattern
Trend
7/20/2015
Location
Servers
UP 419 S-01 wk 14 by Prof. Kim
Demographics
Directories
Positions
Routes
Reports,
Maps
GraphicViews,
Messages
Sites
Assets
Events
Service Points
Transactions
29
Location Services System Concept
GPS
Location
(Application)
Service Client &
Positioning
SW/HW
OpenLS Interface Focus Areas
Mobile
Terminal
GSM
Location
App
Server
Wireless - IP Platform
Location
App
Servers
Internet
or
Intranet
Location
Content
Servers
Database
Engine
(Core Network)
Gateway
Services
Network
Management
Network
Services
Mobile
Positioning
Server
Control
Location-Based Services (LBS): An
Emerging Innovative Transport Service
Technology
•
•
•
•
•
Emergence of LBS
What is LBS?
Basic Use Cases
Location Service Concepts
Research Issues
– Accurate/Efficient Solution Algorithms
– Interoperability and Standard
7/20/2015
UP 419 S-01 wk 14 by Prof. Kim
31
Real Time Traffic Information
• Real-Time Location Information,
– where is the nearest incident investigation site?
– Where is the nearest hospital, restaurant?
•
•
•
•
Tracking,
Traffic Monitoring and Routing,
Telematics,
Real Time Bus Location Information
Systems.
7/20/2015
UP 419 S-01 wk 14 by Prof. Kim
32
Traffic Information Services is NOT So Simple
(You are about to join a ten kilometer traffic queue)
• Create a planned route
• Periodically get device location
• Position device on appropriate transportation network
(usually streets)
– Route May be expressed as segmented line expression
– Examine planned route for obstacles
• Compute work-around if obstacle is discovered
• Process and Present (portray) work-around
• Obtain background road networks with street and place
names with scale and map up date as device moves
– Highlight planned route
– Highlight work-around route
• Explain the obstacle
Maneuver Examples
•
•
•
•
•
•
Turn onto street B
Bear to remain on street A
U-turn on street A
Turn to stay on highway A
Turn onto ramp B
Turn to enter a roundabout: pass n roads before
exiting
• Entering a boat ferry
• Turn to stay on street A (fork)
•7/20/2015
Stay straight through
complex intersection
UP 419 S-01 wk 14 by Prof. Kim
34
Source: NAVTECH
Advisory Examples
•
•
•
•
•
•
•
•
•
Approaching a toll booth
Exiting a tunnel
Entering a bridge
Entering a new country
Road name changes
Roads Merge
Approaching Intermediate WayPoint
Approaching Destination
Walk To Destination
7/20/2015
UP 419 S-01 wk 14 by Prof. Kim
35
Source: NAVTECH
Peak-hour Link
Time Table
Non Peak-hour
Link Time Table
Destination
4:30 PM
Origin
5:00 PM
4:00 PM
3:30 PM
7/20/2015
UP 419 S-01 wk 14 by Prof. Kim
36
Forecasting Spatio-Temporal Link Travel Time
7/20/2015
UP 419 S-01 wk 14 by Prof. Kim
37
Cost Functions for Routing and Navigation
Find a route from my current position, stopping at a gas station for 10 gallons of gas, a
pharmacy to pick up a bottle of Advil, and a flower shop for a dozen roses before arriving home.
Three costs are involved:
(1) the purchasing and stopping costs,
(2) costs related to the time spent on the road, and
(3) distance related costs such as gasoline used, and the wear and tear from the use of a car.
a (10)
b(10)
1
d(6)
2
g(6)
c(6)
e(8)
f(6)
n(10)
3
h(15)
l(4)
k(10)
5
Sample Network
4
Link unit: minute
Total Purchasing and Routing Cost Functions
C j  d j s j   (b mj B mj  d mj s mj )
(1)
m
dj = 1, if he/she decides to stop at location j , i.e. if any Bjm that is non-zero,
= 0, otherwise.
dmj =1, if he/she decides to purchase item m at stop j , i.e. for all Bjm that are non-zeros,
=0, otherwise.

B mj  B m
(2)
j
Cw  w
t
a  rij
d
Cd  d
a  rij
a
a
W   (d j s j )  (b mj B mj  d mj s mj )   w
j
m
(3)
(4)
t
a  rij
a
d
d
a  rij
a
(5)
20: $ 0
21: $ 15
22: $ 24
$3.3
$3.3
$1.98
5
$4.95
unit time cost = $0.33 per minute
Gasoline costs:
Gas station at node 2 = $1.5/gallon
Gas station at node 3= $2.0/gallon
Gas station at node 4= $1.3/gallon
$1.98
30: $ 0
1the cost for
link travel time
and purchasing costs at the end node.
A zero
Flower
costs:element in the
1
$3.3
3 : $ 20
matrix indicates that there
exists no link going from node i to node
j. shop at node 2 = $2.0/rose
Flower
3
3:$ 1
Flower shop at node 4= $2.5/rose
$2.64
$1.32
40: $ 0
41: $ 13
42: $ 30
43: $ 10
Node-to-Node
Adjacency Matrix
1
20
21
22
30
31
33
40
41
42
43
5
1
0
3.3
3.3
3.3
1.98
1.98
1.98
2.64
2.64
2.64
2.64
0
20
3.3
0
0
0
1.98
1.98
1.98
0
0
0
0
0
21
18.3
15.0
0
15.0
16.98
16.98
16.98
0
0
0
0
0
22
27.3
24.0
24.0
0
25.98
25.98
25.98
0
0
0
0
0
30
1.98
1.98
1.98
1.98
0
0
0
1.32
1.32
1.32
1.32
0
Pharmacy costs:
Advil at node 3= $1.0/bottle
Advil at node 4= $10.0/bottle
ham,wrij  ( d j s j  b mj B mj  d mj s mj )   w (t a  rij )  d ( d a  rij )
31
21.98
21.98
21.98
21.98
20.0
0
20.0
21.32
21.32
21.32
21.32
0
33
2.98
2.98
2.98
2.98
1.0
1.0
0
2.32
2.32
2.32
2.32
0
40
2.64
3.3
3.3
3.3
0
0
0
0
0
0
0
0
41
15.64
16.3
16.3
16.3
0
0
0
13.0
0
13.0
13.0
0
42
32.64
33.3
33.3
33.3
0
0
0
30.0
30.0
0
30.0
0
43
12.64
13.3
13.3
13.3
0
0
0
10.0
10.0
10.0
0
0
5
0
3.3
3.3
3.3
4.95
4.95
4.95
0
0
0
0
0
Available Solution Algorithms
Location-Based Services (LBS): An
Emerging Innovative Transport Service
Technology
•
•
•
•
•
•
Emergence of LBS
What is LBS?
Basic Use Cases
Location Service Concepts
Complicated Use Cases
Research Issues
– Accurate/Efficient Solution Algorithms
– Interoperability and Standard
7/20/2015
UP 419 S-01 wk 14 by Prof. Kim
42
Life Without Standards
• A different plug for every appliance
7/20/2015
UP 419 S-01 wk 14 by Prof. Kim
43
Life Without Standards
• Different traffic signs in each state
7/20/2015
UP 419 S-01 wk 14 by Prof. Kim
44
Kinds of Standards – Four Types
• By Level of Coverage • By Function
•
•
•
•
International
Multinational, Regional
National
Local
• Design Standards
• Interface Standards
• Framework Standards
• Performance Standards
• By Level of
Prescriptiveness
• Recommended Practice:
Advisory
• Information Report:
Informative
• Standard: Normative
7/20/2015
• Testing Methods
• Terminology
• By Development
Process
UP 419 S-01 wk 14 by Prof. Kim
• De facto
• Regulatory
• Consensus
45
A Conceptual Architecture for LBS: ISO
Thin Client
or Appliance
Location
Service
Medium Client or Application
Appliance Specific Network
Catalog / Metadata Service
Service Registry
(Name Space Registry)
Proxy or Service Broker
System
Configuration
Services
Network
Geoparser
Service
Data Service
Navigation
Service
Gazeteer
Service
Web
Feature
Service
Geocoding
Service
Web Map
Service
Coordinate
Transformation
Service
Yellow
Pages
Service
Application (Geomatics) Services
Other Services
(as yet undefined)
Transferring Geospatial Data between
Different H/w and S/w:
Geospatial data
S/W 2
7/20/2015
Geospatial data
Standard
UP 419 S-01 wk 14 by Prof. Kim
S/W 1
47
Transferring Geospatial Data:
XML Option
Expandable
Profiles (GML)
S/W 1
7/20/2015
XML
UP 419 S-01 wk 14 by Prof. Kim
S/W 2
48