Transcript Maximum query latency Network traffic per query

HERO: Online Real-time Vehicle
Tracking in Shanghai
Xuejia Lu
11/17/2008
SG Project Overview
 ShanghaiGrid(SG) project aims to provide abundant intelligent
transportation services
•
•
•
•
•
navigation
trip planning
optimal route selection to avoid congestion
bus arrival prediction
…
 Online real-time vehicle tracking is the most fundamental service
• active RFID tag is planted on the tire
• RFID readers and wireless APs are
installed on crossroads
• local node collecting data
• local node connects to Internet
SG Project Challenges
 Real-time requirement
• an query must be answered within a certain bounded time
• e.g. a stolen car
 Scalable
• up to millions of users and hundreds of thousands of vehicles
• huge number of simultaneous queries
 Robust to node failures
• thousands of local nodes
• system maintenance is not easy
Several Existing Solutions
 Centralized scheme
• centralized database
• stores all vehicles’ location information
• accepts all queries
• more than 22,000 crossroads in Shanghai, thousands of events/s
 Distributed schemes
• captured vehicle information can be stored locally at distributed nodes
• BUT no hint about the enquired vehicle for a query
Several Existing Solutions (cont’d)
 Distributed schemes
 Flooding: flood the query across the network
• large amount of traffic
• poor scalability
• fail to satisfy real-time requirement
 Random Walk: long query latency
 DHTs: map objects to peers
• Chord, Tapestry, Pastry etc.
• large computation and traffic overhead for large number
of rapid updates of moving objects
Proposed Solution: HERO
 HERO stands for : Hierarchical Exponential Region Organization
 GOAL :
• limit the maximum query response time
• minimize network traffic
 Core Idea:
update location information in a controlled way
Four Components
 Overlay construction
 Hierarchy initialization
 Restricted location updating
 Query Routing
Overlay construction
• overlay network matches underlying road network
• connection between two geographically neighboring local nodes
Hierarchy initialization
• Each region Ri has a radius ri (in hops)
• r1  r ri   r  k i 1 
• If ri 1   r  k i 1  ,then ri  ri 1  2


• Every node maintains a next-insider pointer that points to a node which
is on the boundary of the immediate inner region
• First node that captures a new vehicle trigger initialization procedure:
a packet contains router field and journey field, initializes to its IP address
and one
• Other nodes will set its next-insider to router
contained in the packet
• If journey value equals to the radius of certain ri :
1) modifies router field to its IP
2) marks itself the boundary node of Ri
Restricted location updating
• Chaser: the local node that moving vehicle passes by
• Chaser perform location updating and maintains the hierarchy
• Three cases to consider depending on the chaser’s location
• The simplest case 1 : chaser is an interior node with R1
chaser floods the vehicle’s information to all other nodes within R1
Case 2: boundary node of R1
• HERO needs to re-organize R1
• node a initiates update packet: similar to initialization but with an additional
scale field to indicate the propagate area, here it is R1
• nodes in R2 will be update to have the current position of the new R1
• special case: new R1 could be truncated by R2, to ensure container relationship
Case 3: common boundary node
•
•
•
•
HERO needs to re-organize R1
the several regions need to be re-build, node b will be the new circle center
nodes in R3 will be update to have the current position of the new R2
special case: new R2 could be truncated by R3, to ensure container relationship
The maximum network traffic overhead of location updating for a
vehicle moving a distance of D (network diameter) :
 ( D)  c(kD2  2r (r  k  1) D  6r 2 ) (c is a constant coefficient)
Query Routing
• R1 will always have the latest location information of the vehicle.
• A query can be issued from any node, when a boundary node receive the query,
unless it is on the R1, it will forward the query to the inner region’s boundary node.
• It takes at most logk ( D / r ) hops for a query to be answered,
where D is the network diameter.
Performance Evaluation
• small white dots: 1,000 nodes
• red dots: location captured, tax is vacant
• dark dots: tax is delivering
• one hour extensive trace data of 100 taxies,
real GPS data, randomly generate 100,000
queries that hour
Two Metrics:
 Maximum query latency
 Network traffic per query
Results
• latency drops when k and r increases: logk ( D / r )
Results(cont’d)
• traffic increases when k or r increases:  ( D)  c(kD 2  2r (r  k  1) D  6r 2 )
• extreme case: r=D or r=1, k=D
Assumptions and Limitations
 Assumes all vehicles have active RFID tag planted in tires
 Number of hierarchies could be up to the same as number of nodes
 A node could have many next-insider pointers, query routing would be
similar to that of Gnutella
 How to solve query routing for the vehicle that is not exist, could lead
to cycle
 System cost could be high, because of planning one node (server) on
every crossroad
 Privacy concern of tracking personal vehicle all the time