Transcript A Summary of the Publications Which Use the Data from SUVnet

A Summary of the Publications
That Use the Data from SUVnet
Xiaokai He
11.16.2010
Outline
•
•
•
•
•
Introduction
GPS Data Processing
Mobility Module
Vehicle Tracking / Locating
Traffic Perception / Estimation / Monitoring
under ITISDTN Routing
• Vehicle Navigation / Route
Introduction
• SUVnet
– Shanghai Urban Vehicular network
• 4000 taxies
• 30 bus lines, more than 700 buses
• Constantly report their location, speed and direction
which typically have an interval at about 1-2 minutes
• 6 months long sample period
Process the Traces
• Map Matching Algorithm
– A Practical Map-matching Algorithm for GPSbased Vehicular Networks in Shanghai Urban Area
• Xu Li;Minglu Li;Wei Shu;Minyou Wu;
• Wireless, Mobile and Sensor Networks, 2007.
(CCWMSN07).
A Practical Map-matching Algorithm for GPS-based
Vehicular Networks in Shanghai Urban Area
• Intend to handle the imperfect data (long sampling rate,
inaccurate GPS position)
• NMA(Naive) and EMA(Enhanced, with angle
information) are both based on the distance and angle
factors, verified by the field test.
• Since the sampling rate is too low, the algorithms are
not depended on the historical information, namely,
only interested in the current point. (How to utilize the
historical info even in this situation?)
• Map: B-graph (Node, Link, Road) (any better solution?)
A Practical Map-matching Algorithm for GPS-based
Vehicular Networks in Shanghai Urban Area – Con’d
• Evaluation results:
• Baseline of the further research, like
• connectivity, effective networking protocols,
• and mobility model
• Further work: map matching with more accurate timestamp?
• Questions: The GPS data only has two-dimension coordinates
Is the altitude information really so important?
Mobility Module (Pattern)
• Speed and direction of mobile nodes is chosen
randomly and constantly
– RWP: random waypoint model
– RD: random direction model
– Gauss-Markov model
• SUMO
– The Simulation of Urban Mobility
– A microscopic, space continuous and time discrete
traffic simulation package
• SUVnet mobility model
Impact of Traffic Influxes: Revealing Exponential
Inter-Contact Time in urban VANETs
– Zhu, H. ; Li, M. ; Fu, L. ; Xue, G. ; Zhu, Y. ; Ni, L. ;
– Parallel and Distributed Systems, 14 October 2010
The tail distribution of the
inter-contact time, which
Exhibits an exponential decay,
is observed by studying the data
of SUVnet. Proved common traffic
Influxes, where large volume of
traffic converges, play a major role
In generating the exponential tail
of the inter-contact time.
Impact of Traffic Influxes: Revealing Exponential InterContact Time in urban VANETs – Con’d
• Recent empirical results on the inter-contact
time based on extensive human mobility
traces – power law
• Traffic Influx
– Mobility module:
• Insert traffic influx to Random walks
Towards Mobility-based Clustering
• Siyuan Liu Yunhuai Liu Lionel M. Ni Jianping Fan Minglu Li
• International Conference on Knowledge Discovery and Data Mining 2010
Proceedings of the 16th ACM SIGKDD international conference on
Knowledge discovery and data mining
• Proposed a non-density-based approach called
mobility-based clustering to identify hot sports of
moving vehicles in an urban area.
• The idea is that sample objects are employed as
“sensors” to perceive the vehicle crowdedness in
nearby areas using their instant mobility.
Towards Mobility-based Clustering - Con’d
• A mobility-based model to quantify the crowdedness of
certain areas
– Use the instant speed of vehicles to sense the crowdedness
– Simple linear crowdedness function
– Statistical crowdedness function (much better)
• Several key factors impact on the accuracy of the
measurement are identified and investigated
• Show several top hot spots are quite locality consistent over
time, while more hot sports present more locality variations
• Performance compared with Umicro – more realisitc
Exploiting Temporal Stability and Low-Rank
Structure for Localization in Mobile Networks
• Swati Rallapalli Lili Qiu Yin Zhang Yi-Chao Chen
• International Conference on Mobile Computing and Networking 2010
• Used SUVnet data as one of the resources to analyze the
characteristics of real mobility traces.
• Two characteristics were found by analyze a number of real
mobility traces
– temporal stability
– low-rank structure.
Exploiting Temporal Stability and Low-Rank Structure
for Localization in Mobile Networks – Con’d
• A general framework and Three novel localization schemes
were developed then for mobile networks.
– For mobile sensors have no built-in GPS and need to be localized by
the algorithms. There are anchor nodes that are equipped with built-in
GPS and known locations.
– Low Rank based Localization
– Temporal Stability based Localization
– Temporal Stability and Low Rank based Localization
Traffic-Known Urban Vehicular Route Prediction
Based on Partial Mobility Patterns
• Guangtao Xue; Zhongwei Li; Hongzi Zhu; Yunhuai Liu;
• Parallel and Distributed Systems (ICPADS), 2009 15th
• Defined a mobility pattern as a consecutive series of road segment
selection
– Short memory feature
• Leveraged variable-oder markov models to mine mobility patterns
from the real taxi GPS trace data
– Impact of dynamic traffic conditions to the accuracy of route prediction
• Exploit Probabilistic Suffix Tree to predict driving routes
• Validate the prediction accuracy and pattern utilization
Traffic Perception / Estimation /
Monitoring under ITIS
• Traffic Monitoring
• Traffic Perception
• Traffic Control
Traffic Data Processing in
Vehicular Sensor Networks
•
•
Xu Li; Wei Shu; Minglu Li; Hongyu Huang; Pei-En Luo; Min-You Wu;
Computer Communications and Networks, 2008. ICCCN '08.
• Performance Evaluation of Vehicle-Based Mobile
Sensor Networks for Traffic Monitoring
•
•
Xu Li; Wei Shu; Minglu Li; ;Pei-En Luo; Hongyu Huang; Min-You Wu;
Vehicular Technology, IEEE Transactions on May 2009
• Focused on the traffic data processing in
vehicular sensor networks providing sparse and
incomplete information.
• Especially in Traffic Monitoring.
Traffic Data Processing in Vehicular
Sensor Networks – Con’d
• Two types of traffic status-estimation algorithms are introduced and
analyzed over SUVnet to understand the traffic-monitoring performance
that can be got from the vehicle-based mobile sensor networks
– Macroscopic Traffic-Flow Theory
• Flow rate
• Mean speed (used as a performance measure: mean traffic speed)
• density
– link-based
– vehicle-based
• utilize every available data pairs from the vehicle and disseminates them back to all links
traveled to estimate MTS
• A performance evaluation study was carried out over SUVnet.
– Demonstrates the feasibility of the system (with a 17.3% error rate)
– Historical based are useful when estimate the traffic status
– Algorithms remain accurate by using long sampling interval
ITIS: Intelligent Traffic Information
Service in ShanghaiGrid
• Xu Li; Junwei Wu; Xinhua Lin; Ying Li; Minglu Li;
• ChinaGrid Annual Conference, 2008. ChinaGrid '08
Propose a new grid middleware,
called SAGE (Simple Adaptive Grid Engine)
to provide the commutation support in ITIS
ITIS: Intelligent Traffic Information
Service in ShanghaiGrid – Con’d
• A prototype system of ITIS is implemented and a field
testing upon SUVnet was carried out.
• 2 sample applications
are proved
– traffic status estimation
– traffic surveillance/ control
SEER: Metropolitan-scale Traffic Perception
Based on Lossy Sensory Data
• Zhu, H.; Zhu, Y.; Li, M.; Ni, L.M.;
• INFOCOM 2009, IEEE
• SEER provides knowledge to setup statistical models for
inferring traffic condition. Utilized multichannel singular
spectrum analysis to iteratively estimate the real-time
traffic condition on surface streets. Uses historical
information to estimate current traffic condition.
– setup statistical models for inferring traffic condition
– multichannel singular spectrum analysis (MSSA)
• Spatio-Temporal Correlation
– How (much) historical information is related to the current
traffic condition :
• uncertainty about the average speed decreases when the previous
average speeds on the road segment are know
• uncertainty about the average speed on a road segment is least
when we know the average speeds at the same time on past days
• MSSA Based Traffic Perception
– Capable to distinguish signal from noise contained in the
traffic condition
– Use an iterative algorithm to deal with missing points in
the time series
Vehicle Tracking / Locating
• HERO
– Online Real-Time Vehicle Tracking
• ANTS
– Efficient Vehicle Locating Based on Ant Search in
ShanghaiGrid
ANTS: Efficient Vehicle Locating Based
on Ant Search in ShanghaiGrid
• Hongzi Zhu; Yanmin Zhu; Minglu Li; Ni, L.M.;
• Parallel Processing, 2007. ICPP 2007
• Aims to locate the nearest desirable vehicles
– Efficient searching strategy (Concept of a lost ant in searching for its nest)
• increase the excursion distance after each loop, choose neighbour to forward randomly
– Decentralized
•
• Requirement
– without relying on any costly updating strategy
– small query latency and modest network traffic with high probability to find
the vehicle
• RFID
HERO: Online Real-Time Vehicle Tracking
•
•
Hongzi Zhu; Yanmin Zhu; Minglu Li; Ni, L.M. ;
INFOCOM 2008
•
Vehicle tracking problem: locate the moving vehicles in real time
– Query for vehicle must be answered within a certain bounded time
– Network traffic (scale to support hundreds of thousands of vehicles)
•
•
•
•
Dynamically maintains a hierarchical structure over the overlay network of local
nodes to conservatively update the location information only in nearby nodes to
help accurately locate the positions of moving vehicles in real time.
Theoretical analysis to identify the tradeoff relationship between the
communication overhead and the query response time to gain the optimal
configuration
Prototypic implementation
Evaluation compare to Chord and Random Walks
DTN Routing
• Disruption-Tolerant Networks
• Flooding Based
– Epidemic routing
– PRoPHET routing protocol
– MaxProp
• RAPID Resource Allocation Protocol for Intentional DTN routing
• Spray and Wait attempts to gain the delivery ratio benefits of
replication-based routing as well as the low resource utilization
benefits of forwarding-based routing.
Performance Evaluation of SUVnet
with Real-Time Traffic Data
•
•
Hong-Yu Huang; Pei-En Luo; Minglu Li; Da Li; Xu Li; Wei Shu; Min-You Wu;
Vehicular Technology, IEEE Transactions on Nov. 2007
• Performance Evaluation of Vehicular DTN Routing under Realistic Mobility
Models
•
•
Pei'en Luo, Hongyu Huang, Wei Shu, Minglu Li, Min-You Wu
Wireless Communications and Networking Conference, 2008.
• Presented the characteristics and a mobility model of the SUVnet,
including network topology and connectivity
– traces, network, network partitions, number of neighbors and
intermittent
• DAER Distance-Aware-Epidemic Routing
– find the appropriate neighbors to replicate / with higher probability of deliver
– Distance-Based/ Max-Hops replacement
Performance Evaluation of SUVnet with
Real-Time Traffic Data – Con’d
• Compare with the non-geographic pure epidemic routing in the Mobility
Module SUVnet and SUMO
• Performance Evaluation and validation based on the real trace data
Routing in Large-Scale Buses
Ad Hoc Networks
• Sede, M.; Xu Li; Da Li; Min-You Wu; Minglu Li; Wei Shu;
• Wireless Communications and Networking Conference, 2008. WCNC 2008.
• Implemented a routing algorithm called BLER
which achieves effective routing in a buses
environment and evaluated on SUVnet
• BLER Bus Line-based Effective Routing
– bus-line-level instead of bus level
DTN Routing in Vehicular Sensor Network
•
•
Xu Li; Wei Shu; Minglu Li; Hongyu Huang; Min-You Wu;
Global Telecommunications Conference, 2008. IEEE GLOBECOM 2008.
• Packet-Oriented Routing in Delay-Tolerant Vehicular Sensor Networks
•
•
LI Xu ( ; HUANG Hong-Yu ; LI Ming-Lu ; WEI SHU ; WU Min-You ;
Journal of information science and engineering 2009
• Presented a new DTN routing protocol Delay-Tolerant Vehicular Sensor
Networks
• Packet-Oriented Routing protocol (POR)
– packet-aware neighbor selection consider the probability of successful
transferring of these packets
– calculate the marginal utility of each neighbor
– use the knowledge about network
DTN Routing in Vehicular Sensor Network – Con’d
The Algorithm / routing protocol is able to perform well in a large-scale network
With an somehow unrealistic assumption:
every node can obtain the locations of other nodes at any time from a
centralized location service, then why not use UMTS directly
A Passive Geographical
Routing Protocol in VANET
• Guangtao Xue, Jinsheng Feng, Minglu Li
• Asia-Pacific Services Computing Conference, 2008. APSCC '08
• A routing mechanism particularly designed for VANET
called Passive Geographical Routing (PGR) is presented,
which uses prior location information of the nodes and city
road map.
– Geographical location information will be used to predict nodes’
new positions in the network, which make routing strategy.
– City road map is used to determine nodes’ direction stable
duration and assist the prognostication of the vehicle’s mobility.
• Without global location query service system
– Performance better than AODV, worse than GPSR
A Passive Geographical
Routing Protocol in VANET – Con’d
• Geographical information local/remote propagation
(Announcement)
– Each node periodically propagate its geographical information to other
nodes along its velocity to the four orthogonal directions.
– With assistance of the city road map, the node can reduce frequency
of announcement propagating. The mobile node doesn't send
announcements periodically until its velocity direction changed
• Packet Forwarding
– no destination route information available. source sends data in its
movement direction.
– If source has destination’s route entry, it will prognosticate
destination’s current location and then forward packet to the best next
hop.
Max-Contribution: On Optimal Resource
Allocation in Delay Tolerant Networks
•
•
Kyunghan Lee; Yung Yi; Jaeseong Jeong; Hyungsuk Won; Injong Rhee; Song Chong;
INFOCOM, 2010
• Considered joint optimization of link scheduling, routing
and replication for disruption-tolerant networks (DTNs)
• A new notion of optimality: Snapshot optimality
– Adopt a temporal approximation to implement algorithm only
restricted in terms of available information
• A new approximation algorithm: Distributed MaxContribution (DMC)
– Link/Copy Scheduling Decomposition
– performs greedy resource allocation of scheduling, routing and
replication based only on locally and contemporarily available
information
Vehicle Navigation / Route
• Individual driver can benefit from route navigation
– Load Balancing
• Improve global transportation efficiency in terms of
dispersing/managing traffic, which plays a key role to
construct an effective vehicular CPS.
Quality Evaluation of Vehicle
Navigation with CPS
•
Yang Yang, Xu Li, Wei Shu and Min-You Wu
• Focused on vehicle route navigation, presented performance
comparisons of four routing algorithms using data from SUVnet.
–
–
–
–
Shortest Path Algorithm
Optimal Algorithm (shortest travel time)
Historical Based Algorithm
Adaptive Real time Algorithm
• The idea of Vehicle Infrastructure Integration (VII) and IntelliDrive
aims to improve transportation efficiency by utilizing cyber
technologies, which is also called Cyber Physical Systems (CPS) in
computer science domain.
– How different are various vehicle routing algorithms?
– How valuable is real-time traffic information or historical traffic information in
helping vehicle routing?
Quality Evaluation of Vehicle
Navigation with CPS – Con’d
Researches from MS Asia
• Map-Matching
– ST-Matching
– Interactive Voting-based Map Matching
• Diving Direction: T-Drive
• Data Set
– 33000 Taxis
– 3 months
– Average time interval 3.27 minutes
Map-Matching for Low-Sampling-Rate GPS Trajectories
• Local or Incremental Algorithms
• Global Algorithms
• Assumptions
– True path tend to be direct, rather than roundabout
– True path tend to follow the speed constraints of the road
• ST-Matching
– Candidate Preparation->Spatial and Temporal Analysis->Result Matching
– Spatial geometric and topological structures of the road network
– The temporal/speed constraints of the trajectories
– Compared with incremental algorithm and Average-Frechet-Distance (AFD) based
global map-matching algorithm
An Interactive-Voting Based Map
Matching Algorithm
• Interactive Voting-based Map Matching
– The position context of a GPS point as well as the topological
information of road networks
– The mutual influence between GPS points
– The strength of the mutual influence weighted by the distance
between GPS points
•
•
•
•
Candidates Preparation
Position Context Analysis
Mutual Influence Modeling
– Static
– Weighted
Interactive Voting
• Outperforms the ST-Matching
T-Drive: Driving Directions
Based on Taxi Trajectories
• Assumption: Taxi drivers are usually experienced in finding the
fastest route
• Mine smart driving directions from the historical GPS
trajectories of a large number of taxis
• A time-dependent landmark graph to model the intelligence
of taxi drivers and the properties of dynamic road networks
• A Variance-Entropy-Based Clustering approach to estimate the
distribution of travel time between two landmarks
• A two-stage routing algorithm to compute the fastest route
• Result: 60-70% of the routes suggested by the method are
faster than the competing method (Google/Bing Maps).
T-Drive: Driving Directions Based on
Taxi Trajectories – Con’d
• Challenges
– Intelligence Modeling
– Data sparseness and limited coverage
– Low-sampling-rate Problem
• Why Landmark (Time-Dependent Landmark Graph)
– Nature thinking pattern of people (necessary?)
– Facing the challenges above
T-Drive: Driving Directions Based on
Taxi Trajectories – Con’d
• Travel Time Estimation
– A set of distributions
corresponding to different
time slots
– Change over time of a day
• VE-Clustering
– V-clustering: cluster the travel
time of a landmark edge into
several categories
– E-clustering: learn a proper
time partition for each
landmark edge
T-Drive: Driving Directions Based on
Taxi Trajectories – Con’d
• Route Computing
– Rough Routing
• A typical time-dependent fastest path problem
– Refined Routing
• Dijkstra or A*-like Algorithms
• Evaluation
– Outperforms the RT approach
– Better than Google Maps (also Bing Maps :P)
Not Found / Published yet
•
Movement Activity Estimation for Opportunistic Networking Based on Urban
Mobility Traces
– Karin Anna Hummel, Andrea Hess
– IFIP Wireless Days 2010 - Venice, Italy
•
Feasibility study of using FM radio for data transmission in a Vehicular Network
– Kun-chan Lan, Mei-Wen Li
– ICS International Conference on International Computer Symposium
•
A measurement-based study of the effectiveness of DSRC
– Kun-chan Lan, Wei-Yen Lin, Mei-Wen Li, and Chung-Hsien Hsu
– Annual International Conference onNetwork Technologies & Communications NTC 2010
•
A comparison of 802.11a and 802.11p for V-to-I communication: a measurement
study
– Kun-chan Lan, Wei-Yen Lin, Mei-Wen Li,and Chung-Hsien Hsu
– 7th International ICST Conference on Heterogeneous Networking for Quality, Reliability,
Security and Robustness (International workshop on DSRC 2010)
Thank you for your attention!
[email protected]
? ? || /* */