Road transportation is a “grand challenge” societal problem. With close to a billion vehicles on the road today, and a doubling projected over the next 15-20 years, we face pressing challenges to the efficiency and the safety of this infrastructure. The CarTel project combines mobile computing and sensing, wireless networking, and data-intensive algorithms running on servers in the cloud to address these challenges. CarTel is a distributed, mobile sensing and computing system using phones and custom-built on-board telematics devices; one may think of it as a “vehicular cyber-physical system”.

CarTel helps applications easily collect, process, deliver, analyze, and visualize data from sensors located on mobile units (mobile phones and in-car embedded devices). Over the past several years, we have developed several versions of CarTel.

CarTel's research contributions include traffic mitigation (including the iCarTel iPhone app), road surface monitoring and hazard detection (the Pothole Patrol), vehicular networking (Cabernet, CafNet, vehicular WiFi measurements, mobile mesh networking), privacy protocols (VPriv and PrivStats), intermittently connected databases (ICEDB), and the design of multiple generations of in-car OBD+GPS hardware using only WiFi for connectivity.

Traffic Mitigation

VTrack and CTrack are two related systems that process error-prone position streams to accurately estimate trajectories and delays. VTrack is particularly effective when the raw data has errors (e.g., from WiFi or with outages) and each position sample in the stream is an approximate “median” or “centroid” of the various possible locations from which a given access point or base station might have been observed. CTrack is an improvement in that it uses “soft information” in the form of signal strengths, and can work well even when the position information is from cellular base stations alone (the raw error is several hundred meters here, but CTrack is able to handle that and produce accurate results). CTrack uses a two-stage hidden markov model, where the second stage is VTrack.

The results of VTrack/CTrack are accurate delay estimates for road segments. The system processes this data, combining real-time and historic delay estimates to produce predictions of future delays at various points in time in the future. We have developed a variety of predictive models, including one that is currently part of the iCartel iPhone app.

The results of the predictive model are sent to a commute portal where users can view the data, as well as to our traffic-aware routing engine, which implements various vehicular routing strategies. One strategy is practical stochastic routing: given an origin and destination, the routing method finds the best path that maximizes the probability of going between the two places within a deadline. The algorithm and its implementation are described here.

Please consider contributing to our traffic mitigation efforts by downloading and running our crowd-sourced traffic data collection and traffic-aware route planning iPhone Application.

  • Commute and traffic portal: A Web site that shows all the trips made by a driver and provides interesting ways to visualize one's trips, and tools to analyze this data. Our portal is now available for public use at icartel.net.
  • Fleet testbed, a 27-car CarTel deployment in the cars of a local limo company (PlanetTran). This testbed also serves as the “vehicle” for much of our research, allowing us to deploy software and applications on a running system (in addition, some user's cars also have CarTel nodes).

Pothole Patrol

P2 (Pothole Patrol) uses the CarTel infrastructure in conjunction with applied machine learning algorithms to automatically monitor and classify road surface conditions.

Software Infrastructure

The CarTel system has three main software components. The portal is the central location that hosts CarTel applications and functions as the point of control and configuration for the distributed system. The portal is also the sink for all data sent from the mobile nodes. To simplify application development, we have developed ICEDB, a delay-tolerant continuous query processor. To transfer data efficiently, we have developed opportunistic wireless network protocols that can connect rapidly (at vehicular speeds) to access points and techniques to cope with intermittent connectivity.

CarTel applications running on the portal can either issue continuous queries using an API exported by ICEDB, or simply ask to transfer a sequence of data items from one node to another akin to a pipe (using dpipe, explained below). Both models are simple and resemble SQL and UNIX pipes, respectively.

Networking

CarTel's network subsystem has three useful components that higher layers can choose to use: Cabernet, dpipe, and CafNet.

  • Cabernet: CarTel nodes are able to achieve end-to-end connectivity across a changing set of WiFi access points much faster than in current stacks, which makes it possible to use even when the client is in range of an access point for only a few seconds. The bulk of the time can then be spent in data transfer. Cabernet is a software stack that provides these features using QuickWifi (fast Wifi connectivity, within 400 ms or less from moving cars) and CTP, a new transport protocol that is better than TCP at high non-congestive loss rates (as in moving cars using WiFi).
  • dpipe: dpipe is a delay-tolerant pipe, a transport abstraction that allows a producer node and consumer node to reliably transport data even across an intermittently connected network. dpipe optimizes for the case when the IP address of an end-point changes often.
  • CafNet, cars-as-mules: CafNet (carry and forward network) is a delay-tolerant stack that enables mobile data muling and allows data to be sent across an intermittently connected network. CafNet delivers data between nodes even when there is no synchronously connected network path between them. For example, these protocols could be used to deliver data from sensor networks deployed in the field to Internet servers without requiring anything other than short-range radio connectivity on the sensors (or at the sensor gateway node). dpipe subsumes some of its functions now, but dpipe doesn't handle data muling. Our early motivation was that unlike traditional automotive telematics systems that rely on cellular or satellite connectivity, the CarTel embedded in-car device (i.e., when data is collected using the OBD-connected hardware) should use wireless networks opportunistically. It uses a combination of WiFi, Bluetooth, and cellular connectivity, using whatever mode is available and working well at any time, but shields applications from the underlying details. Applications running on the mobile nodes and the server use a simple API to communicate with each other. CarTel's communication protocols handle the variable and intermittent network connectivity.
  • Wi-Fi Monitoring, mapping the proliferation of 802.11 access points in the Boston metro area.

ICEDB

ICEDB is a continuous query processor to process streaming data, but differs from traditional stream processing applications in how query results are sent to the querying application (running on the portal). Because network connectivity is variable and intermittent, with ICEDB:

  • Queries specify what sensor data must be acquired and at what rate, how the data should be sub-sampled, filtered, and summarized on the mobile node, and in what (dynamic) priority order results should be sent back to the portal.
  • Query results stream in across an intermittently connected network, and populate a relational database at the portal.
  • Applications issue SQL queries on the portal's relational database to retrieve data they need for further analysis, visualization, etc. These are snapshot queries that run on whatever data is currently available. Applications do not wait synchronously for the results of continuous queries.

Thus, applications can think of the data distributed across the mobile network as being stored locally in a standard SQL relational database, which simplifies how they are written. The programming model is familiar, essentially the same as what web developers today use. ICEDB deals with the underlying complexity of distributing queries to the mobile nodes (where they run in situ), coping with the network's vagaries, and ensuring that the results are available locally.

ICEDB handles heterogeneous sensor data, allowing the set of sensors to be expanded without requiring major software changes on the remote nodes. Each sensor has an adapter running on the node that handles the details of configuring and extracting information from that sensor and converting it into a normalized form. To ease management and deployment, when a new sensor is added, or when the functions of an adapter need to be modified, only the adapter module needs to change.

Privacy Protocols

* VPriv protects the location privacy of users in systems like CarTel. More generally, a variety of location-based vehicular services are currently being woven into the national transportation infrastructure in many countries. These include usage- or congestion-based road pricing, traffic law enforcement, traffic monitoring, ``pay-as-you-go'' insurance, and vehicle safety systems. Although such applications promise clear benefits, there are significant potential violations of the locational privacy of drivers under standard implementations (i.e., GPS monitoring of cars as they drive, surveillance cameras, and toll transponders).

VPriv is a system that can be used by several such applications without violating the locational privacy of drivers. The starting point is the observation that in many applications, some centralized server needs to compute a function of a car's or user's {\em path}—a list of time-position tuples. VPriv provides two components: 1) a protocol to compute path functions in a way that does not reveal anything more than the result of the function to the server, and 2) an out-of-band enforcement mechanism using random spot checks that allows the server and application to handle misbehaving cars or users. Checkout the C++ code for VPriv.

* PrivStats: A significant and growing class of location-based mobile applications process position data from individual devices and compute aggregate statistics over these position streams. Because these devices can be linked to the movement of individuals, there is a significant danger that the aggregate computation will violate the location privacy of the individual. PrivStats is the first system for computing aggregate statistics over location data that simultaneously achieves two properties: first, provable guarantees on location privacy even in the face of any side information about user movement patterns known to the server, and second, accountability (i.e., protection against abusive clients uploading large amounts of spurious data) without compromising privacy. PrivStats achieves these properties using a new protocol for privacy supporting a wide range of aggregate statistic computations as well as a novel and efficient zero-knowledge proof of knowledge protocol we developed from scratch for accountability. It works reasonably efficiently on commodity smartphones (currently Android phones in our implementation).

The Portal

The portal includes a geo-spatial data visualization system that stores sensor data from cars. It organizes data in terms of traces, which are sets of sensor readings collected during a particular drive. Users are given a simple graphical query interface for selecting the traces they are interested in and visualizing various summaries, statistics, and maps within or across the traces they select.

Click here to see a brief walk-through of the portal.

Hardware Infrastructure

Version 0

box1_pen.jpgopenbox_pen.jpggps_pen.jpgobd_pen.jpg

A small yet powerful embedded computer running Linux 2.6 (previously, 2.4), the Soekris net4801, though other similar devices running Linux would also work. This unit has a 586-class processor running at 266 MHz with 128 MB of RAM and 1 GB (or more) of Flash. It has 2 serial ports and a USB 1.1 port for external devices. This expandable unit comes in rugged package.

Reasonably accurate location and time information are critical to most of our applications. We use a commodity GPS unit with a USB interface for this purpose.

Most cars made after 1996 provide access to the internal computer through OBD-II interface. We use an OBD-to-serial adapter from ScanTool.net. This adapter provides a modem-like interface and can be automatically queried over a serial port.

In order to upload collected data and download software updates we use miniPCI WiFi card. The picture shows the WiFi card is plugged into the MiniPCI slot of the embedded computer.

Many of the applications mentioned earlier deploy additional sensors, for vibration, images, etc. The embedded computer in the car also provides Bluetooth connectivity (via a USB dongle) to any external Bluetooth-enabled devices (e.g., cell phone).

Version 2

A custom-made device built from a commodity WiFi access point with additional enhancements for other sensors.

Software Downloads

Check out our iCarTel iPhone Application

Currently, we have released the following software packages. Please consult their respective pages for packages and documentation.

Papers

* Accurate, Low-Energy Trajectory Mapping for Mobile Devices. Arvind Thiagarajan, Lenin S. Ravindranath, Hari Balakrishnan, Samuel Madden, Lewis Girod, Proc. NSDI, Boston, MA, 2011. Paper (this is the paper on CTrack, using primarily inaccurate (but low-energy) cellular RF localization to produce accurate map-matched trajectories).

* Improving Wireless Network Performance Using Sensor Hints. Lenin S. Ravindranath, Calvin Newport, Hari Balakrishnan, Samuel Madden, Proc. NSDI, Boston, MA, 2011. Paper.

* VTrack: Accurate, Energy-Aware Road Traffic Delay Estimation Using Mobile Phones. Arvind Thiagarajan, Lenin Ravindranath, Katrina LaCurts, Sivan Toledo, Jakob Eriksson, Samuel Madden, Hari Balakrishnan, in Proc. 14th ACM SenSys, Berkeley, CA, November 2009. Paper. Winner of the best paper award.

* VPriv: Protecting Privacy in Location-Based Vehicular Services. Raluca Ada Popa, Hari Balakrishnan, Andrew Blumberg, in Proc. USENIX Security Symp., Montreal, Canada, August 2009. Paper.

* Cabernet: Vehicular Content Delivery Using WiFi. Jakob Eriksson, Hari Balakrishnan, Samuel Madden, in Proc. 14th ACM MOBICOM, San Francisco, CA, September 2008. Paper

* The Pothole Patrol: Using a Mobile Sensor Network for Road Surface Monitoring. Jakob Eriksson, Lewis Girod, Bret Hull, Ryan Newton, Samuel Madden, Hari Balakrishnan, in Proc. of the 6th Annual International conference on Mobile Systems, Applications and Services (MobiSys), Breckenridge, U.S.A., June 2008. Paper

* IceDB: Continuous Query Processing in an Intermittently Connected World. Yang Zhang, Bret Hull, Hari Balakrishnan, and Samuel Madden. In Proc. ICDE 2007. Abstract PDF

* A Measurement Study of Vehicular Internet Access Using Unplanned 802.11 Networks. Vladimir Bychkovsky, Bret Hull, Allen Miu, Hari Balakrishnan, and Samuel Madden, in Proc. ACM MOBICOM, 2006. Award paper. Abstract PDF

* CarTel: A Distributed Mobile Sensor Computing System. Bret Hull, Vladimir Bychkovsky, Kevin Chen, Michel Goraczko, Allen Miu, Eugene Shih, Yang Zhang, Hari Balakrishnan, and Samuel Madden, in Proc. ACM SenSys, 2006. Abstract PDF

* The CarTel Mobile Sensor Computing System. Demonstration at ACM SenSys 2006. Best demo award.

* CafNet: A Carry-and-Forward Delay-Tolerant Network. MEng Thesis, MIT EECS, Feb. 2007. Abstract with link to PDF

People

  • Current graduate students: Sejoon Lim, Paresh Malalur, Raluca Ada Popa, Lenin Ravindranath, Arvind Thiagarajan
  • Post-docs, collaborators, and research scientists: Jakob Eriksson, Sivan Toledo, Lewis Girod, Nikolaus Correll, Andrew Blumberg, Evdokia Nikolova

Funding/Acknowledgments

The CarTel project is currently funded by the NSF under a cyber-physical systems grant (2009-2012). In the past, it was funded by the National Science Foundation under grants CNS-0205445, CNS-0520032, and CAREER-0448124 and in part (Cabernet, the CafNet stack, and the WiFi measurement study) by the T-Party Project, a joint research program between MIT and Quanta Computer Inc., Taiwan, and in part by Google.

We are also grateful to Seth Riney of PlanetTran for his help.

Contact

To learn more, contact Hari Balakrishnan, Sam Madden, and/or the CarTel team (send a note to cartel at the domain nms.csail.mit.edu).

Related Projects

 
cartel.txt · Last modified: 2011/05/18 10:48 by hari
 
Recent changes RSS feed Creative Commons License Donate Powered by PHP Valid XHTML 1.0 Valid CSS Driven by DokuWiki