In this paper we present our experience on detecting and classifying traffic jams in real time from probe data. We classify traffic jams at two levels. At a higher level, we classify traffic jams into recurring and non-recurring jams. Then at a lower level we identify accidents out of non-recurring jams based on features that characterize upstream and downstream traffic patterns. Accidents are highly unpredictable and usually create heavy and long lasting congestion, and therefore are particularly worth detecting. We discuss the challenges of detecting accidents in real time as well as our approaches and results.

This paper proposes an algorithm called MACH for coding a hierarchical category structure to enable prefix matching between a publication and a subscription. Compared to fixed-length coding, the MACH algorithm generates shorter code lengths without losing the efficiency of matching. In addition, the MACH algorithm automatically identifies the bits that are not necessary for prefix matching. These bits are saved to allow growth of categories. The bit saving is prioritized according to a configurable criterion. Experiments with real world data and synthetic data are conducted to evaluate the benefit of the proposed algorithm.

Real-time parking availability information is important in urban areas, and if available could reduce congestion, pollution, and gas consumption. In this paper, we present a software solution called PhonePark for detecting the availability of on-street parking spaces. The solution uses the GPS and/or accelerometer sensors in a traveler's mobile phone to automatically detect when and where the traveler parked her car, and when she released a parking slot. PhonePark can also utilize the mobile phone's Bluetooth sensor or piggyback on street parking payment transactions for parking activity detection. Thus, the solution considers only mobile phones and does not rely on any external sensors such as cameras, wireless sensors embedded in the pavements, or ultrasonic sensors on vehicles. Further contributions include an algorithm to compute the historical parking availability profile for an arbitrary street block and algorithms to estimate the parking availability in real-time for a given street block. The algorithms are evaluated using real-time and real world street parking data.

The proliferation of mobile devices, location-based services and embedded wireless sensors has given rise to applications that seek to improve the efficiency of the transportation system. In particular, new applications are already available that help travelers to find parking in urban settings by conveying the parking slot availability near the desired destinations of travelers on their mobile devices.

In this paper we present a model of spatially located mobile agents and static resources, in which the agents are looking to obtain one of the resources while minimizing their costs to obtain the resource. The proliferation of mobile devices, location-based services and embedded wireless sensors has given rise to applications that could help the mobile agents have updated information of the location of the resources they are looking for. Nevertheless, while engaged in driving, travelers are better suited being guided to an ideal resource, rather than looking at a map and deciding which available resource to visit. Then the question of how an application should choose this ideal resource, to guide the agent towards it, becomes relevant. In this work we develop algorithms that are designed to guide users to these resources. They use a gravitational approach to guide a mobile agent through a road network in order to find this ideal resource. The performance of the algorithms is evaluated through simulations.

In this paper, we present a platform for aiding in the development and evaluation of novel ITS passive safety applications. Such applications work by having vehicles detect certain events that may be dangerous to other vehicles and disseminating reports about these events using wireless communication. A vehicle receiving the report about the event can then be warned. However, a large number of false warnings will lead to driver desensitization, which will reduce the safety benefit. To overcome this issue, a relevance estimator that will determine for which reports a warning will be given has to be devised for each new application. Our platform allows for an easy, fast method of developing these estimators and evaluating them in simulations. We demonstrated the feasibility of this approach with three example applications.

With the proliferation of location-based services, mobile devices, and embedded wireless sensors, more and more applications are being developed to improve the efficiency of the transportation system. In particular, new applications are arising to help vehicles locate open parking slots. Nevertheless, while engaged in driving, travelers are better suited being guided to an ideal parking slot, than looking at a map and choosing which slot to go to. Then the question of how an application should choose this ideal parking slot becomes relevant. Vehicular parking can be viewed as vehicles (players) competing for parking slots (resources with different costs). Based on this competition, we present a game-theoretic framework to analyze parking situations. We introduce and analyze parking slot assignment games and present algorithms that choose parking slots ideally in competitive parking simulations. We also present algorithms for incomplete information contexts and show how these algorithms outperform even algorithms with complete information in some cases.

Real-time street parking availability information is important in urban areas, and if available could reduce congestion, pollution, and gas consumption. In this paper, an advanced street parking system called PhonePark is presented. Using the GPS, accelerometer, and Bluetooth sensors on a traveler's mobile phone, in conjunction with geospatial data, we can automatically detect when and where the traveler parked her car, and when she released a parking slot.

In this paper, we compare two methods of estimating relevance for the emergency electronic brake light application: One method uses an analytically derived formula based on the minimum safety gap that is required to avoid a collision, whereas the other method uses a machine learning approach. The application works by disseminating reports about vehicles that perform emergency deceleration in an effort to warn drivers about the need to perform emergency braking. Vehicles that receive such reports have to decide on whether the information contained in the report is relevant to the driver and warn the driver if that is the case. Common ways of determining relevance are based on the lane or direction information, but using only these attributes can lead to many false warnings, which can desensitize the driver. Desensitized drivers may ignore warnings or completely turn off the system, thus eliminating any safety benefits of the application. We show that the machine learning method, compared with the analytically derived formula, can significantly reduce the number of false warnings by learning from the actions that drivers take after receiving a report. The methods were compared using simulated experiments with a range of traffic and communication parameters.

With the proliferation of location-based services, mobile devices, and embedded wireless sensors, more and more applications are being developed to improve the efficiency of the transportation system. In particular, new applications are arising to help vehicles locate open parking spaces. Nevertheless, while engaged in driving, travelers are better suited being guided to a particular and ideal parking slot, than looking at a map and choosing which spot to go to. Then the question of how an application should choose this ideal parking spot becomes relevant.

The transportation mode such as walking, cycling or on a train denotes an important characteristic of the mobile user's context. In this paper, we propose an approach to inferring a user's mode of transportation based on the GPS sensor on her mobile device and knowledge of the underlying transportation network. The transportation network information considered includes real time bus locations, spatial rail and spatial bus stop information. We identify and derive the relevant features related to transportation network information to improve classification effectiveness. This approach can achieve over 93.5% accuracy for inferring various transportation modes including: car, bus, aboveground train, walking, bike, and stationary. Our approach improves the accuracy of detection by 17% in comparison with the GPS only approach, and 9% in comparison with GPS with GIS models. The proposed approach is the first to distinguish between motorized transportation modes such as bus, car and aboveground train with such high accuracy. Additionally, if a user is travelling by bus, we provide further information about which particular bus the user is riding. Five different inference models including Bayesian Net, Decision Tree, Random Forest, Naïve Bayesian and Multilayer Perceptron, are tested in the experiments. The final classification system is deployed and available to the public.

In this paper, we compare two methods of estimating relevance for the emergency electronic brake light application. One uses an analytically derived formula based on the minimal safety gap required to avoid a collision. The other method uses a machine learning approach. The application works by disseminating reports about vehicles that are performing emergency deceleration in effort to warn drivers about the need to perform emergency braking. Vehicles receiving such reports have to decide whether the information contained in the report is relevant to the driver, and warn the driver if that is the case. Common ways to determine relevance are based on the lane or direction information, but using only these attributes can still lead to many false warnings, which can desensitize the driver. Desensitized drivers may ignore warnings or turn off the system completely, thus eliminating any safety benefits of the application. We show that the machine learning method, in comparison to the analytically derived formula, is able to significantly reduce the number of false warnings by learning from the actions drivers take after receiving a report. The methods were compared using simulated experiments with a range of traffic and communication parameters.

In this paper we study querying multimedia data such as video and voice clips in hybrid vehicular networks that consist of vehicles that are capable of both infrastructure-less short-range communication and infrastructure communication. We introduce a set of query processing strategies which differ from each other in terms of push versus pull, whether or not infrastructure communication is utilized, and whether metadata dissemination is separated from multimedia dissemination. We analyze these strategies theoretically and by simulations, and identify the one that is superior to the others.

In this paper we provide an architecture for Tactical Information Middleware for bandwidth constrained information management. We propose the ideas of rank-based data dissemination, and the use of a tactical information management query language. These ideas will deal with dynamic changes in bandwidth and explore opportunistic data dissemination. Thus, will lead to a cross layer design of a system capable of handling the dynamic data management issues relevant in many mission critical applications.

In this paper we consider a novel multimedia application, in which drivers may query multimedia clips captured by smartphones mounted on other vehicles. These multimedia clips visualize and voice-indicate the real-time traffic conditions on road segments ahead. We designed a systematic and exhaustive set of query processing strategies which differ from each other in terms of push versus pull, whether infrastructure communication is utilized, and whether metadata dissemination is separated from multimedia clip dissemination. We analyze these strategies theoretically and by simulations, and identify the one that is superior to the others.

The in-network query processing paradigm in sensor networks postulates that a query is routed among sensors and collects the answers from the sensors on its trajectory. It works for static and connected sensor networks. However, when the network consists of mobile sensors and is sparse, a different approach is necessary. In this paper we propose a query processing method that uses cooperative caching. It makes the data items satisfying a query flow to its originator. To cope with communication bandwidth and storage constraints, the method prioritizes the data-items in terms of their value, as reflected by supply and demand. Simulations based on real-life mobility traces identify the situations in which our approach outperforms a series of existing cooperative caching strategies and an existing mobile sensor network algorithm.

In this article we study the data dissemination problem in which data items are flooded to all the moving objects in a mobile ad hoc network by peer-to-peer transfer. We show that if memory and bandwidth are bounded at moving objects, then the problem of determining whether a set of data items can be disseminated to all the moving objects is NP-complete. For a heuristic solution we postulate that a moving object should save and transmit the data items that are most likely to be new (i.e., previously unknown) to future encountered moving objects. We propose a method to be used by each moving object to prioritize data items based on their probabilities of being new to future receivers. The method employs a machine learning system for estimation of the novelty probability and the machine learning system is progressively trained by received data items. Through simulations based on real mobility traces, we show the superiority of the method against some natural alternatives.

In this paper we study in-network query processing in disconnected mobile environments, where both ad-hoc communication and infrastructure communication are available. Depending on how the infrastructure is utilized, various query-processing schemes are classified. Analytical models are developed to compute the average delay and the average energy consumption for each of these schemes. Based on the analytical models, the query processing schemes are compared under various environment conditions. It is found that none of the studied schemes is optimal in all the conditions. Therefore the paper provides a method that allows the optimal scheme to be chosen for a given set of environmental conditions.

Peer-to-peer data dissemination in a mobile ad-hoc environment is characterized by three resource constraints, including energy, communication bandwidth, and storage. Most of the existing studies deal with these constraints separately. In this paper we propose an algorithm called RANk-based dissemination (RANDI), which provides an integral treatment to the three constraints. The contribution is in determining how to prioritize the reports in terms of their relevance, when to transmit the reports, and how many to transmit. We experimentally compare RANDI with IDS and PeopleNet, two mobile peer-to-peer dissemination algorithms. The results show that RANDI significantly outperforms both algorithms.

In this paper we propose a novel algorithm called Rank-Based Broadcast (RBB) for discovery of local resources in mobile P2P networks. With RBB, each moving object periodically broadcasts the most relevant resource reports and queries it knows to its neighbors, and the contribution is in determining how to rank the reports and queries in terms of their relevance, when to broadcast them, and how many to broadcast. A major difference between RBB and many existing algorithms in the resource discovery and publish/subscribe literature is that RBB does not rely on any pre-established routing structure, and therefore is able to adapt to both high mobility environments. In the paper we experimentally compare RBB with flooding and PSTree, a publish/subscribe algorithm for wireless ad-hoc networks. The results show that RBB by far outperforms the other two algorithms.

A mobile ad-hoc network (MANET) is a set of moving objects that communicate with each other via unregulated, short-range wireless technologies such as IEEE 802.11, Bluetooth, or Ultra Wide Band (UWB). No fixed infrastructure is assumed or relied upon. An important application domain of MANET’s is local resource discovery. In a local resource discovery application, a user finds local resources that satisfy specified criteria. For example, a driver finds an available parking slot in a region by receiving information generated by the parking meter, or gets the traffic conditions on a highway segment a mile ahead; a cab driver finds a near-by customer, or a participant at a convention finds another participant with a matching profile.

In this paper we examine resource discovery in inter-vehicle ad-hoc networks in an urban area, where moving vehicles communicate with each other via short-range wireless transmission. Our focus is on real-time location-specific information. We explore an opportunistic approach to resource recovery, in which a vehicle obtains information about resources from encountered vehicles. The vehicle uses a spatio-temporal relevance function to sort the resources, and save only the most relevant ones. Our theoretical and experimental analysis indicates that the opportunistic exchange algorithm automatically limits the distribution of a resource to a bounded spatial area and to the duration for which the resource is of interest.

Our Mobitrack prototype is intended to serve as a platform, or a toolkit for developing moving-objects-database type of applications. The system is the third in a three-layer architecture. The first layer is an object relational DBMS. The database stores the information about each moving object, including its plan of motion. The second layer is a GIS that adds capabilities and user interface primitives for storing, querying, and manipulating geographic information. The third layer, Mobitrack, adds temporal capabilities, capabilities of managing the uncertainty that is inherent in future motion plans, capabilities for location prediction, and a simulation testbed. Currently, Mobitrack runs on both Unix and MS Windows. On both platforms Mobitrack uses the Arc-View GIS. It uses the Informix DBMS on Unix, and DBAccess on MS Windows.

Consider a database that represents information about moving objects and their location. For example, for a database representing the location of taxi-cabs a typical query may be: retrieve the free cabs that are currently within 1 mile of 33 N. Michigan Ave., Chicago (to pick-up a customer); or for a trucking company database a typical query may be: retrieve the trucks that are currently within 1 mile of truck ABT312 (which needs assistance); or for a database representing the current location of objects in a battlefield a typical query may be: retrieve the friendly helicopters that are in a given region, or, retrieve the friendly helicopters that are expected to enter the region within the next 10 minutes. The queries may originate from the moving objects, or from stationary users. We will refer to applications with the above characteristics as moving-objects-database (MOD) applications, and to queries as the ones mentioned above as MOD queries.

Consider a database that represents information about moving objects and their location. For example, for a database representing the location of taxi-cabs a typical query may be: retrieve the free cabs that are currently within 1 mile of 33 N. Michigan Ave., Chicago (to pickup a customer). In the military, moving object database applications arise in the context of the digital battlefield and in the civilian industry they arise in transportation systems. Currently, moving object database applications are being developed in an ad hoc fashion. Database management system (DBMS) technology provides a potential foundation upon which to develop these applications, however DBMSs are currently not used for this purpose. The reason is that there is a critical set of capabilities that are needed by moving object database applications and are lacking in existing DBMSs. The objective of our Databases fOr MovINg Objects (DOMINO) project is to build an envelope containing these capabilities on top of existing DBMSs. We describe the problems and our proposed solutions.