Research Projects

Active Research Projects:

Mingle

 

Locus: A Vehicular-based Content Management Network for Location-centric Applications

Given the demand for richer services for drivers and their passengers, the next generation of vehicles will be equipped with extensive communication and computing capabilities and will be outfitted with a wide range of mechanical and environmental sensors. This wealth of data and resources has the potential for enabling new classes of applications that cater to individuals on the road, supporting functions such as real-time (on-demand) traffic reports, fuel-saving and safety tips, lo- cal advisories, local search, and local advertising. The goal of this proposal is to design, develop, and test Locus, a delay-tolerant content-centric vehicular network architecture that geographically caches location-based content of interest to commuters. The architectural contribution of the pro- posed work lies in developing protocols to support this first location-centric content access paradigm for delay-tolerant networks, where content with location affinity is efficiently maintained on top of and served to a fleet of moving vehicles.

In participatory environmental sensing, data is inherently tied to the location where it was generated and not to the user who created it, transforming the primary entities of the network into the data objects rather than individual devices. In a mobile environment with limited resources, the accumulation of such location-specific data raises two important questions of where to store the data and how to access it. At first glance, remote access, where data lives on centralized servers, seems to be a natural choice for supporting these applications (e.g., Cartel). However, the reality is that the load generated from participatory sensing systems will overwhelm existing centralized infrastructures. For example, in Chicago there are on average 2500 vehicles per km2. If only 10% of those vehicles are generating data, the network must be able to support 250 data streams per km2. A typical 3G basestation coverage radius is several hundred meters, or approximately 100 users. Given an upload capacity of around 500 Kbps per basestation, that leaves only 5 Kbps per device. While this data rate can support simple sensor readings, transferring larger data objects like images or mp3s will exceed the capacity of the network. More importantly, whatever capacity the basestations do have is shared with competing applications for mobile Internet access. Given that the demand for mobile Internet access will only increase, centralized approaches for location-based applications likely will not have sufficient bandwidth.

A natural progression is to design and deploy decentralized location-centric solutions. In this context, we propose the design of Locus, a vehicular-based content management network that functions as a distributed data cache built on top of a fleet of moving vehicles to support location- centric applications. The novelty of this approach comes from decoupling of the data from the nodes that carry it. Instead, data in Locus is explicitly tied to the location where it was collected or most needed. Vehicles currently in the local area for that data temporarily store the data and pass it to new nodes as they enter the area or drop it as they leave the area. Support for this dynamic caching is enabled using techniques from routing in intermittently connected or Delay Tolerant Networks (DTNs).

 


 

Slides:

Locus presentation at CHANTS 2010 - [PDF] [PPTX]

Locus: A Vehicular-based Content Management Network for Location-centric Applications

Given the demand for richer services for drivers and their passengers, the next generation of vehicles will be equipped with extensive communication and computing capabilities and will be outfitted with a wide range of mechanical and environmental sensors. This wealth of data and resources has the potential for enabling new classes of applications that cater to individuals on the road, supporting functions such as real-time (on-demand) traffic reports, fuel-saving and safety tips, lo- cal advisories, local search, and local advertising. The goal of this proposal is to design, develop, and test Locus, a delay-tolerant content-centric vehicular network architecture that geographically caches location-based content of interest to commuters. The architectural contribution of the pro- posed work lies in developing protocols to support this first location-centric content access paradigm for delay-tolerant networks, where content with location affinity is efficiently maintained on top of and served to a fleet of moving vehicles.

In participatory environmental sensing, data is inherently tied to the location where it was generated and not to the user who created it, transforming the primary entities of the network into the data objects rather than individual devices. In a mobile environment with limited resources, the accumulation of such location-specific data raises two important questions of where to store the data and how to access it. At first glance, remote access, where data lives on centralized servers, seems to be a natural choice for supporting these applications (e.g., Cartel). However, the reality is that the load generated from participatory sensing systems will overwhelm existing centralized infrastructures. For example, in Chicago there are on average 2500 vehicles per km2. If only 10% of those vehicles are generating data, the network must be able to support 250 data streams per km2. A typical 3G basestation coverage radius is several hundred meters, or approximately 100 users. Given an upload capacity of around 500 Kbps per basestation, that leaves only 5 Kbps per device. While this data rate can support simple sensor readings, transferring larger data objects like images or mp3s will exceed the capacity of the network. More importantly, whatever capacity the basestations do have is shared with competing applications for mobile Internet access. Given that the demand for mobile Internet access will only increase, centralized approaches for location-based applications likely will not have sufficient bandwidth.

A natural progression is to design and deploy decentralized location-centric solutions. In this context, we propose the design of Locus, a vehicular-based content management network that functions as a distributed data cache built on top of a fleet of moving vehicles to support location- centric applications. The novelty of this approach comes from decoupling of the data from the nodes that carry it. Instead, data in Locus is explicitly tied to the location where it was collected or most needed. Vehicles currently in the local area for that data temporarily store the data and pass it to new nodes as they enter the area or drop it as they leave the area. Support for this dynamic caching is enabled using techniques from routing in intermittently connected or Delay Tolerant Networks (DTNs).

 


 

Slides:

Locus presentation at CHANTS 2010 - [PDF] [PPTX]

Type of Publication
Journal Articles
Crepaldi, R., R. Welsh, and R. Kravets, "ParkingMeter: Balancing Energy Savings and Service Availability", The Tenth ACM International Workshop on VehiculAr Inter-NETworking, Systems, and Applications (VANET), Taipei, Taiwan, 06/2013.  Download: [PDF] (467.01 KB)
Conference Articles
Crepaldi, R., R. Welsh, and R. Kravets, "Governing Energy for Parked Cars", The 10th Annual Conference on Wireless On-Demand Network System and Services (WONS), Banff, Alberta, 03/2013.  Download: [PDF] (968.59 KB)
Conference Articles
Crepaldi, R., M. Bakht, and R. Kravets, "QuickSilver: Application-driven Inter- and Intra-cluster Communication in VANETs", The Third ACM/SIGMOBILE International Workshop on Mobile Opportunistic Networking (MobiOpp), Zurich, 03/2012.  Download: [PDF] (665.5 KB)
Conference Articles
Crepaldi, R., R. Beavers, B. Ehrat, J. Sze, M. Jaeger, and R. Kravets, "LoadingZones: Leveraging Street Parking to Enable Vehicular Internet Access", 7th Workshop on Challenged Networks (CHANTS 2012), Istanbul, 08/2012.  Download: [PDF] (287.09 KB)
Conference Articles
Thompson, N., R. Crepaldi, and R. Kravets, "Locus: A Location-based Data Overlay For Disruption-Tolerant Networks", Fifth Workshop on Challenged Networks (CHANTS 2010), Chicago, IL, 09/2010.  Download: [PDF] (206.13 KB)
Conference Articles
Crepaldi, R., R. Beavers, B. Ehrat, and R. Kravets, "Illinois Vehicular Project, Live Data Sampling and Opportunistic Internet Connectivity", The Third ACM/SIGMOBILE International Workshop on Mobile Opportunistic Networking (MobiOpp), Zurich, 2012.
Conference Demos
Crepaldi, R., M. Bakht, T. Abdelzaher, and R. Kravets, "Illinois vehicular project, live data sampling and energy-efficient node discovery Riccardo Crepaldi, Mehedi Bakht and Robin Kravets", ACM Annual International Conference on Mobile Systems, Applications and Services (Mobisys), 2011.  Download: Poster [PDF] (2.18 MB); Abstract [PDF] (38.62 KB)
Conference Demos
Crepaldi, R., R. Beavers, B. Ehrat, J. Sze, M. Jaeger, and R. Kravets, "LoadingZones: Leveraging Street Parking to Enable Vehicular Internet Access", The 18th Annual International Conference on Mobile Computing and Networking (MOBICOM 2012), Istanbul, 2012.  Download: [PDF] (184.35 KB)
Conference Posters

Pulsar: A Cross-Layer Approach to Energy Conservation in Mobile Ad Hoc Networks

The increasing demand for long-lived mobile computing devices has brought power conservation to the forefront of research. Techniques for optimizing the energy consumption of every component of a mobile device have been shown to produce dramatic improvements in device lifetime. Improving lifetime is particularly important for mobile ad hoc and sensor networks where devices are expected to be deployed for long periods of time without the potential for recharging their batteries. Various application-level techniques can be used to reduce the amount of data to send, and so the amount of energy consumed to send that data. However, once the application decides to send some data, it is up to the ad hoc network to try to deliver it in an energy-efficient manner. To support energy-efficient communication, it is necessary to consider energy consumption at multiple layers in the network protocol stack. At the network layer, intelligent routing protocols can minimize overhead and ensure the use of minimum energy routes. At the medium access control (MAC) layer, techniques can be used to reduce the energy consumed during data transmission and reception. Additionally, an intelligent MAC protocol can turn off the wireless communication device when the node is idle. While many of these techniques have been studied in isolation, any change to communication at one of the layers impacts the other and so may impact energy consumption and communication quality. The design and development of the Pulsar framework provides a hierarchical approach to energy conservation that focuses on the interrelationships between layers.


The hierarchical design of Pulsar focuses on node, routing and global adaptations to achieve energy-efficient communication. At the node layer, power control (i.e., dynamically changing transmission power levels) reduces the energy consumption of data transmissions. Additionally, power management (i.e., placing the device in a low-power sleep mode) reduces the energy consumed unnecessarily during idle periods in communication. At the routing layer, energy consumption is reduced by finding minimum energy routes, maximizing the number of nodes in low-power mode and reducing the overhead of the routing protocol. At the global layer, Pulsar uses topology control to reduce transmission energy consumption and alleviate contention in the network. Given the cooperative nature of communication in ad hoc networks, energy conservation at one node may impact communication in the entire network. Additionally, greedy energy conservation at individual nodes may increase total energy consumption across all nodes. These issues make it challenging to support energy-efficient communication without a comprehensive understanding of the interrelationships between the various energy-conserving techniques. The goal of our research is to capture these relationships in the adaptations of Pulsar, through the following architecture:

 

The MOPED Project

As a user acquires multiple personal technology and communication devices, the efficiency of these devices is limited by their isolation from each other. When the resources of a device are completely consumed (e.g., a dead mobile phone battery), the user is completely cut off from key services. Similarly, if a user leaves the coverage area of a device, the services currently available via that device are no longer accessible. As a user moves through different environments, the cooperation of devices brings the potential for increased bandwidth and better connectivity by exposing to all devices the aggregation of services available to individual devices. Current technology and communication support provide connectivity between devices, but do not enable cooperation between devices. The goal of our research is to bridge this gap from communication to cooperation.

Our project presents a networking model that treats a user's set of personal devices as a MOPED, an autonomous set of MObile grouPEd Devices, which appears as a single entity to the rest of the Internet. All communication traffic for a MOPED user is delivered to the MOPED, where the final disposition of traffic is determined. Since a MOPED is designed to support a single user, communication with any of the devices in the MOPED is equivalent to communication with the user. This model enables the mapping of a group of devices into a point of presence on the Internet for a user. To the outside world, this MOPED appears as a single device with a single interface or identifier. In reality, the group of devices cooperates to provide better services to the user. 

The goal of the MOPED project is to provide service to a user through the cooperation of the MOPED devices that is better than the service provided by the devices working individually. Our solution provides four key benefits. First, a user can be connected via any of the services currently available to the individual devices. Second, if multiple devices have connectivity in a certain environment, the MOPED can take advantage of the additional bandwidth by routing different flows through different connections. Third, devices with no external connectivity can share the resources of other devices with external connectivity in their component. Finally, such connectivity enables smooth handoffs as individual devices gain and lose connectivity, allowing external connectivity to all devices as long as at least one device in the component has external connectivity. 

In addition to improved service, the design of the MOPED architecture provides three additional benefits that ease the integration and deployment of MOPEDs. First, our design supports the commonly accepted idea that non-mobile users should not have to be aware of the extra infrastructure needed to support mobile users. Our architecture supports communication with non-mobile-aware users as well as optimizations for mobile-aware users. This abstraction also provides the benefit of hiding the topology of the MOPED from external hosts, providing flexibility and anonymity. Second, any new device acquired by a user can be integrated into the MOPED as long as it can become part of the PAN connecting the MOPED. This covers the easy inclusion of new technology as well as legacy devices. The level of cooperation of the individual devices in the MOPED depends on whether or not the device is MOPED-enabled. Finally, the sharing of communication resources across devices allows each device to be specialized to its specific purpose -- A smart watch need not also be a phone. 

The results of our research will enable simultaneous connections through all available communication channels. This creates a very robust environment, where it becomes easier to guarantee complete communication coverage. It allows using MOPEDs for critical tasks such as patient monitoring where it is important to maintain connectivity at all time, through there may be some flexibility in the amount of data that is transferred as well as the importance of that data. If the communication patterns of such a MOPED are not well monitored, certain devices may unacceptably lose power due to inefficient connection management. 


This material is based upon work supported by the National Science Foundation under Grant No. 0081308 Any opinions, findings, and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the National Science Foundation

 

The-Day-After Networks: A First-Response Edge-Network Architecture for Disaster Relief

Recent disasters, including natural phenomena (e.g., hurricane Katrina) and terrorism (e.g., 9/11), have exposed the fragility of our national communication infrastructure. Many familiar services that are relied on for everyday communications (e.g., ubiquitous cell phone connectivity and always-on Internet connections) immediately become nonfunctional in emergency situations due to the failure of the supporting infrastructure through both system damage and system overuse. Unfortunately, these situations result in increased demand and so require effective communication support. Given the limitations of current network architectures, the goal of this proposal is to develop a new network architecture, including supporting communication mechanisms, to enable survivable communication and networking in disaster scenarios. The novelty of our architecture for the day after networks stems from the fact that the protocols and services will be designed from the bottom up to support the specific communication demands required for disaster management and recovery.

The main goal in supporting disaster rescue and recovery efforts is enabling effective communication amongst the diverse rescue workers, as well as providing connectivity to survivors. The day after networks (DAN) need to provide communication to support recovery and relief efforts. However, during a disaster, the standard communication infrastructure, including switching stations, underground fibers and cell phone towers, may be damaged, destroyed or without power. Consequently, landline phones, Internet modems, and television sets will not be operational. While emergency response personnel may have some backup communication support, current provisioning for emergency response personnel relies on infrastructure support, such as cell towers, that may not be operational during a major disaster. Since we cannot simply throw more traditional resources at DAN environments, it is important to first understand the real communication requirements needed in these environments. 

There are two main differences between traditional Internet communication and communication during disaster and recovery. First, the communication paradigm is inherently different than the standard host-to-host communication seen in the Internet today. Consider the site of a natural disaster. Survivors must be located, information regarding relief resources must be efficiently disseminated to rescue workers, survivors may want to connect with rescue workers or with their families, rescue workers may need fast communication channels with their superiors, and emergency organizers need to delegate tasks to volunteers. While the goal of the Internet has been to maintain end-to-end connectivity for hosts, the main goal of a DAN is to support the services needed by the users and so ensure host-to-service communication. Since the people involved in disaster recovery play particular roles to provide these services (e.g., police officers, fire fighters, rescue workers, volunteers, survivors), we believe that communication in disaster recovery networks must be role-based. 

Second, since repair of the existing infrastructure may be slow and the current provisioning for emergency response is insufficient, the need for more immediate connectivity demands the inclusion of all available communication resources, and so will result in a network with heterogeneous communication technologies that alone may only have intermittent connectivity to any remaining infrastructure. Unfortunately, the fundamental Internet design tenets make it ineffective to adopt the Internet architecture for communication and networking in disaster scenarios, even with incremental updates (e.g., adding redundancy and enriching the topological connectivity). First and foremost, the Internet was designed for fail-stop robustness. That is, the failure of some part of the Internet will be locally confined and will not propagate or impact the proper functioning of other surviving parts of the Internet. This fail-stop robustness was appropriate sixty years ago when the nation was under the threat of massive nuclear attacks. In the new century where the primary concerns have moved to natural and terrorism disasters, it is unacceptable to have a network that has parts that simply stop working in a crisis. Instead, the network must survive modern disasters, even with degraded performance. Second, the Internet was designed with the main goal of supporting scalable unicast routing. For modern disaster scenarios that focus on providing services, this focus on unicast communication is clearly off-target. Third, the Internet paradigm assumes connectivity at all times, and also assumes that all roads lead to the Internet. In DAN environments, nodes are expected to have intermittent connectivity and may be able to reach a different subset of nodes through different interfaces. Finally, the inherent need for prioritization and security of traffic demands that they be natively supported components in the network architecture. 

While support for communication in disconnected networks has been proposed using delay tolerant networking, the role-based communication needed for disaster recovery does not t the current model of delay tolerant networks. Although there will always be a need to support some host-to-host communication, the host-to-service model of communication demands different underlying communication paradigms at all layers of the protocol stack. At the routing layer, we believe that such communication can best be supported through native anycast routing, enabled with a combination of hop-by-hop reliability and intelligent flooding. At the transport layer, since the underlying communication paradigm is no longer host-to-host communication, the definition of end-to-end is no longer clear. Therefore, we believe that the transport layer will be a best effort entity that manages the expected reliability of communication through redundancy and caching. 

 We present Phoenix, a complete network architecture for the day after networks, including a suite of enabling mechanisms and algorithms for survivable communication and networking in disasters. Phoenix differs from the Internet in almost all aspects, including its infrastructure construction, naming, native communication paradigm, protocol stack structure, and built-in services. In the following sections, we identify the challenges and opportunities for Phoenix, present our design of the Phoenix architecture that is both technically feasible and practically usable, and propose controls and optimizations that will likely be enforced in future DANs.

If successful, this proposed work will lead to more robust national communication capabilities that will significantly improve disaster management. By providing an information backplane when it is most needed, the Phoenix will improve the efficiency of recovery efforts, significantly reducing the human and resource cost of catastrophic events. This work may also play a role in setting new standards for communication providers (e.g., cell phone manufacturers and service providers) and the automotive industry such that future generations of communication devices (including ones embedded in vehicles) are compliant with post-disaster requirements. Consequently, better safety is assured in a future where we become more dependent on technological artifacts and so are increasingly vulnerable to attacks that subvert them.

 

Mingle

 Mingle test

Mingle: Sensing the Social Interactions of Animals

Behavior defines any animal. Understanding why they do what they do and how they do it depends on the interactions individual animals have with their physical environment and other animals. Unfortunately, gathering data on who interacts with whom in different contexts on complex landscapes over large distances has limited our ability to deduce general rules that shape animal societies. Now, however, with the advent of efficient and relatively cheap sensors, behavioral scientists are on the verge of being able to make what has been invisible, visible, bringing a transformation to the field of animal behavior.

In an effort to lead this transformation, we have designed MINGLE, an adaptive sensor-based system that enables the tracking of social interactions between animals. The novelty of MINGLE comes from the observation that such social interactions can be tracked by monitoring the animals relative orientation and relative distance to each other. Since animals often change associations and form large groups, understanding the dynamics of who associates with whom will help formulate the rules that shape the dynamics of animal societies. However, the technical challenges of gathering such data at a fine-enough scale to provide these social in- sights are great. By relying on local information, MINGLE minimizes the need for expensive tracking of absolute location of all animals all of the time. Therefore, the design of MINGLE integrates the dynamic use of multiple radios and sensors by focusing on local relative orientation and proximity of all individuals in a population to provide sufficiently accurate estimates of association. Additionally, MINGLE optimizes energy efficiency by integrating local collaborative sensing with the judicious use of infrastructure-based so- lutions based on observations about the mobility of the animals. Finally, MINGLE integrates real application constraints to ultimately drive energy-efficient data collection.

Clearly, understanding patterns of association as measured by proximity or directed social networks de- rived from association data–whether pro- or anti-social–can provide insights into the structure and function of animal societies and the way they move about on landscapes. To date, however, social network analysis and their link to ecological context have been limited to small assemblages that have been studied for as little as a few days (e.g., guppies), to at most a season or year (e.g., equids and primates). The rich volume of data on a large number of individuals ranging widely and studied for long periods that will be available from MINGLE will enable new directions in the study of animal social behavior.

 

Mingle is a cross disciplinary, multi-university project funded by the National Science Foundation

 

Partcipants:

Robin Kravets, Department of Computer Science, University of Illinois

Tanya Berger-Wolf, Department of Computer Science, University of Illinois-Chicago

Joel Brown, Department of Biological Sciences, University of Illinois-Chicago

Yih-Chun Hu, Department of Electrical and Computer Engineering, University of Illinois

Dan Rubenstein, Department of Ecology and Evolutionary Biology, Princeton University

 
Publications:
2016
Ettore Randazzo (Ph.d Thesis). Inferring Interaction Network from Sensor Data. University of Illinois at Chicago.
J. Zhao (BS Thesis). Horsing around: quantifying the resilience of the social networks of equus caballus. Princeton University

 

2015

Li, J., Brugere, I., Ziebart, B., Berger-Wolf, T., Crofoot, M., Farine, D. Social Information Improves Location Prediction in the Wild. 2015 International Workshop on Trajectory-based Behaviour Analytics (TrBA’15). 

 

2013

Chayant Tantipathananandh Habiba and Tanya Berger-Wolf. Dynamic networks generative model for skewed component distribution. SIAM Workshop on Network Science. 

Chayant Tantipathananandh Haibiba and Tanya Berger-Wolf. Effect of network structure on influence maximization in dynamic networks. SIAM Workshop on Network Science. 

Jonathan Crall, Charles Stewart, Tanya Y. Berger-Wolf, Daniel Rubenstein. HotSpotter - Species Independent Animal Instance Recognition. Proceedings of the Workshop on the Applications of Computer Vision (WACV).