Richard J. La - US grants

Abstract
0205330

The design, planning, control and management of high performance networks require a much more integrated approach than the conventional layered approach, where each layer is designed and optimized independently from the others. In this proposal the researchers propose to exploit inter-layer dependencies in network protocols for improved network performance. In particular, the researchers will focus on ad-hoc wireless networks, in which these interdependencies are more pronounced and in which the network will benefit significantly by crosslayer designs.

The main focus is on the interaction between the physical layer, the MAC layer, and the routing/transport layers. The researchers take into account the nature of the wireless medium by detailed modeling of the transmission parameters and of the detector structure and consider both TDMA(scheduled) and CDMAmedia-accesscontrol mechanisms. The researchers couple these with the flow and route assignment problems and, furthermore, consider how the transport protocol interacts with route selection and bandwidth allocation.

In addition, the researchers address the role of network control and management in ad-hoc wireless networks and exploit its interaction with the aforementioned layers. Finally, the researchers consider the interaction of signal compression with rate and quality control and are mindful of the energy consumption repercussions of the joint protocol design.

The overall goal of the proposed research is to enable a systematic network provisioning and dimensioning and resource allocation based on accurate traffic modeling for diverse traffic with a vision of providing end-to-end QoS guarantees. The proposed work focuses on four major research thrusts:
1. Development of stochastic and deterministic traffic models for elastic and real-time traffic : We will first build faithful stochastic traffic models to study the interaction between transport layer protocols and active queue management mechanisms for macro-management of a large number of connections. We will apply limiting theorems to investigate the asymptotic behavior of the system with a large number of flows and develop scalable macro-scale models. Our findings will be used to develop accurate and yet scalable nonlinear deterministic models to investigate the dynamics of a network with multiple bottlenecks and to predict the expected performance of flows. We will study the effects that congestion at one part of network has on other parts of network. We will also design distributed algorithms to enhance the stability (robustness) of network in case of instability.
2. Design of pricing schemes for between end users and service providers and between domains: We will develop non-cooperative incomplete information game models and study the end users' behavior, where users are not assumed to be aware of the precise utilities/actions of other users and/or network state. Based on our findings we will design a pricing mechanism that will improve the system efficiency and fairness. We will generalize the models to cases where the selfish users do not know their own utilities precisely. We will also model the problem of inter-domain pricing and service level agreements as a non-cooperative game, where cooperation may emerge as a result of presence of credible threat or incentive. We will use both pricing and QoS parameters of service level agreements as design parameters to induce efficiency among domains and design a distributed algorithm that will ensure convergence to a desired operating point.
3. Integration of physical and logical network management: We will propose the integration of physical and logical network management as a means of providing improved end-to-end QoS. We will formulate the problem of designing a unified suite of policies for managing the networks as a Multi-time scale Markov Decision Process (MMDP) problem. This will allow us to break the complex overall problem of designing integrated policies into several simpler MDP problems corresponding to different time scales. We will apply the detailed traffic models we develop for elastic and non-responsive traffic to predict the expected performance of a variety of applications as a function of network configurations and adopted policies. This will be used to design our optimal policies for different time scales, based on selected performance measures such as throughput of elastic traffic, packet loss rate and delay of real-time traffic, and a cost associated with reconfiguration of networks in the form of disrupted service for some flows.
4. Wireless link scheduling for end-to-end QoS guarantees: We will extend the optimization problem framework we have proposed recently for resource allocation over a wireless link for non-real-time flows. Using this framework as a starting point we will design an opportunistic wireless scheduling algorithm for real-time and non-real-time applications, which exploits channel conditions of the users. Our approach will be based on multi-objective optimization, which will allow us to efficiently trade-off the performance of one class for that of the other, based on our detailed traffic models for both elastic and inelastic traffic. We will first develop a method of translating the multiple objective functions to a scalar objective function, which allows the designer to achieve Pareto optimality using the simpler scalar objective function. The existence of such a scalar objective function and a mapping has been recently proved by Fleischer. The scalar objective function will then be used to design a wireless link scheduling algorithm that achieves Pareto optimality. The selection of actual operating point on the Pareto frontier will be governed by a set of constraints we impose. This technique will be extended to other resource allocation problems with multi-objective functions. Based on the proposed wireless link scheduling algorithm and its performance, we will investigate the issue of wireless network provisioning.

Towards modeling wireless networks -- When connectivity meets mobility!

The search for appropriate wireless network models that capture the effects of node locations and user interferences has led to the introduction of several classes of random graphs with increasingly complex notions of adjacency (i.e., one-hop connectivity). In such one-hop connectivity graph models, the presence of an edge between two nodes captures their ability to communicate directly and reliably with each other. However, viewed as systems, networks are "greater than the sum of their parts" -- One-hop connectivity gives rise to "network connectivity" as network resources collectively enable end-to-end data transfer between participating nodes.
When the graph determined by the one-hop connectivities is static (or slowly changing at the time scales of interest), network connectivity is readily identified with the usual notion of graph connectivity in the one-hop connectivity graph. In the presence of mobility, the one-hop connectivity structure of the network changes over time, graph connectivity may no longer be suitable to capture network connectivity and other, more appropriate, notions need to be considered. With this in mind, we introduce the notions of continuous connectivity and fly-through connectivity: Continuous connectivity requires that a path exists between every pair of nodes at all times. Fly-through connectivity only demands that a multi-hop end-to-end path be provided within acceptable delays, allowing for the possibility that the network is not continuously connected.

We explore how these different notions of network connectivity shape resource allocation (e.g., energy) in the presence of node mobility. Concerning continuous connectivity, emphasis is on (i) identifying zero-one laws and the attending critical scalings, and on (ii) determining the existence and width of associated phase transitions. The approach and methods are probabilistic in nature. Major efforts will be made to find useful characterizations for fly-through connectivity. Tools from algebraic graph theory and from the spectral theory of graphs are expected to play a key role. This should result in more realistic models for wireless networks for the purpose of designing robust and efficient resource allocation algorithms in the presence of node mobility, and for evaluating their performance.

Designing suitable network pricing mechanisms is important for both (i) recovering the cost of providing existing network services and (ii) encouraging deployment of new services and expansion of network capacities. Since service providers are often selfish private entities, the problem of network pricing is studied using tools from economics, in particular, game theory.

When there exists uncertainty regarding the payoff (i.e., profit) of the service providers, called players, recent findings show that risk averse players can behave very differently and change the interaction among the players considerably. As a result, even a pricing scheme that seems rather natural can provide them with an incentive to lie about their private information. This in turn causes a loss in the overall benefit and a significant drop in the profits to the players, discouraging the deployment of new services. Thus, this calls for a careful look at the consequences of uncertainty in payoffs and risk aversion by players on the overall social welfare and the payoffs to the players.

The goal of the project is to take the first step towards identifying suitable frameworks for designing efficient and fair network pricing mechanisms: The first part of the project will carry out a thorough investigation of the impacts of uncertainty in payoffs of the players and risk averse players on likely equilibria in a set of well formulated and targeted scenarios and their implications on the design of pricing mechanisms. The second part will examine how much of social welfare can be lost due to the selfish nature of the players and the uncertainty and aims to find suitable bounds when possible.

Expected outcomes from the project will help service providers identify more suitable pricing schemes that will encourage the deployment of new services through fair profit sharing and improved efficiency. This will promote collaboration among selfish service providers and bring more network services and lower prices to the consumers, while increasing the overall social benefits/welfare.

Designing semi-autonomous networks of miniature robots for inspection of bridges and other large civil infrastructure

According to the U.S. Department of Transportation, the United States has 605102 bridges of which 64% are 30 years or older and 11% are structurally deficient. Visual inspection is a standard procedure to identify structural flaws and possibly predict the imminent collapse of a bridge and determine effective precautionary measures and repairs. Experts who carry out this difficult task must travel to the location of the bridge and spend many hours assessing the integrity of the structure.

The proposal is to establish (i) new design and performance analysis principles and (ii) technologies for creating a self-organizing network of small robots to aid visual inspection of bridges and other large civilian infrastructure. The main idea is to use such a network to aid the experts in remotely and routinely inspecting complex structures, such as the typical girder assemblage that supports the decks of a suspension bridge. The robots will use wireless information exchange to autonomously coordinate and cooperate in the inspection of pre-specified portions of a bridge. At the end of the task, or whenever possible, they will report images as well as other key measurements back to the experts for further evaluation.

Common systems to aid visual inspection rely either on stationary cameras with restricted field of view, or tethered ground vehicles. Unmanned aerial vehicles cannot access constricted spaces and must be tethered due to power requirements and the need for uninterrupted communication to support the continual safety critical supervision by one or more operators. In contrast, the system proposed here would be able to access tight spaces, operate under any weather, and execute tasks autonomously over long periods of time.

The fact that the proposed framework allows remote expert supervision will reduce cost and time between inspections. The added flexibility as well as the increased regularity and longevity of the deployments will improve the detection and diagnosis of problems, which will increase safety and support effective preventive maintenance.

This project will be carried out by a multidisciplinary team specialized in diverse areas of cyber-physical systems and robotics, such as locomotion, network science, modeling, control systems, hardware sensor design and optimization. It involves collaboration between faculty from the University of Maryland (UMD) and Resensys, which specializes in remote bridge monitoring. The proposed system will be tested in collaboration with the Maryland State Highway Administration, which will also provide feedback and expertise throughout the project.

This project includes concrete plans to involve undergraduate students throughout its duration. The investigators, who have an established record of STEM outreach and education, will also leverage on exiting programs and resources at the Maryland Robotics Center to support this initiative and carry out outreach activities. In order to make student participation more productive and educational, the structure of the proposed system conforms to a hardware architecture adopted at UMD and many other schools for the teaching of undergraduate courses relevant to cyber-physical systems and robotics.

This grant will support research on fundamental principles and design of robotic and cyber-physical systems. It will focus on algorithm design for control and coordination, network science, performance evaluation, microfabrication and system integration to address the following challenges: (i) Devise new locomotion and adhesion principles to support mobility within steel and concrete girder structures. (ii) Investigate the design of location estimators, omniscience and coordination algorithms that are provably optimal, subject to power and computational constraints. (iii) Methods to design and analyze the performance of energy-efficient communication protocols to support robot coordination and localization in the presence of the severe propagation barriers caused by metal and concrete structures of a bridge.