Browsing by Author "Pei, Guanhong"
Now showing 1 - 3 of 3
Results Per Page
Sort Options
- Distributed Scheduling and Delay-Throughput Optimization in Wireless Networks under the Physical Interference ModelPei, Guanhong (Virginia Tech, 2013-01-21)We investigate diverse aspects of the performance of wireless networks, including throughput, delay and distributed complexity.
One of the main challenges for optimizing them arises from radio interference, an inherent factor in wireless networks.
Graph-based interference models represent a large class of interference models widely used for the study of wireless networks,
and suffer from the weakness of over-simplifying the interference caused by wireless signals in a local and binary way.
A more sophisticated interference model, the physical interference model, based on SINR constraints,
is considered more realistic but is more challenging to study (because of its non-linear form and non-local property).
In this dissertation, we study the connections between the two types of interference models -- graph-based and physical interference models --
and tackle a set of fundamental problems under the physical interference model;
previously, some of the problems were still open even under the graph-based interference model, and to those we have provided solutions under both types of interference models.
The underlying interference models affect scheduling and power control -- essential building blocks in the operation of wireless networks -- that directly deal with the wireless medium; the physical interference model (compared to graph-based interference model) compounds the problem of efficient scheduling and power control by making it non-local and non-linear.
The system performance optimization and tradeoffs with respect to throughput and delay require a ``global\'\' view across
transport, network, media access control (MAC), physical layers (referred to as cross-layer optimization)
to take advantage of the control planes in different levels of the wireless network protocol stack.
This can be achieved by regulating traffic rates, finding traffic flow paths for end-to-end sessions,
controlling the access to the wireless medium (or channels),
assigning the transmission power, and handling signal reception under interference.
The theme of the dissertation is
distributed algorithms and optimization of QoS objectives under the physical interference model.
We start by developing the first low-complexity distributed scheduling and power control algorithms for maximizing the efficiency ratio for different interference models;
we derive end-to-end per-flow delay upper-bounds for our scheduling algorithms and our delay upper-bounds are the first network-size-independent result known for multihop traffic.
Based on that, we design the first cross-layer multi-commodity optimization frameworks for delay-constrained throughput maximization by incorporating the routing and traffic control into the problem scope.
Scheduling and power control is also inherent to distributed computing of ``global problems\'\', e.g., the maximum independent set problems in terms of transmitting links and local broadcasts respectively, and the minimum spanning tree problems.
Under the physical interference model, we provide the first sub-linear time distributed solutions to the maximum independent set problems, and also solve the minimum spanning tree problems efficiently.
We develop new techniques and algorithms and exploit the availability of technologies (full-/half-duplex radios, fixed/software-defined power control) to further improve our algorithms.
%This fosters a deeper understanding of distributed scheduling from the network computing point of view.
We highlight our main technical contributions, which might be of independent interest to the design and analysis of optimization algorithms.
Our techniques involve the use of linear and mixed integer programs in delay-constrained throughput maximization. This demonstrates the combined use of different kinds of combinatorial optimization approaches for multi-criteria optimization.
We have developed techniques for queueing analysis under general stochastic traffic to analyze network throughput and delay properties.
We use randomized algorithms with rigorously analyzed performance guarantees to overcome the distributed nature of wireless data/control communications.
We factor in the availability of emerging radio technologies for performance improvements of our algorithms.
Some of our algorithmic techniques that would be of broader use in algorithms for the physical interference model include:
formal development of the distributed computing model in the SINR model, and reductions between models of different technological capabilities, the redefinition of interference sets in the setting of SINR constraints, and our techniques for distributed computation of rulings (informally, nodes or links which are well-separated covers). - Human Initiated Cascading Failures in Societal InfrastructuresBarrett, Christopher L.; Channakeshava, Karthik; Huang, Fei; Marathe, Achla; Marathe, Madhav V.; Pei, Guanhong; Saha, Sudip; Vullikanti, Anil Kumar S.; Kim, Junwhan; Subbiah, Balaaji S. P. (Public Library of Science, 2012-10-31)In this paper, we conduct a systematic study of human-initiated cascading failures in three critical inter-dependent societal infrastructures due to behavioral adaptations in response to a crisis. We focus on three closely coupled socio-technical networks here: (i) cellular and mesh networks, (ii) transportation networks and (iii) mobile call networks. In crises, changes in individual behaviors lead to altered travel, activity and calling patterns, which influence the transport network and the loads on wireless networks. The interaction between these systems and their co-evolution poses significant technical challenges for representing and reasoning about these systems. In contrast to system dynamics models for studying these interacting infrastructures, we develop interaction-based models in which individuals and infrastructure elements are represented in detail and are placed in a common geographic coordinate system. Using the detailed representation, we study the impact of a chemical plume that has been released in a densely populated urban region. Authorities order evacuation of the affected area, and this leads to individual behavioral adaptation wherein individuals drop their scheduled activities and drive to home or pre-specified evacuation shelters as appropriate. They also revise their calling behavior to communicate and coordinate among family members. These two behavioral adaptations cause flash-congestion in the urban transport network and the wireless network. The problem is exacerbated with a few, already occurring, road closures. We analyze how extended periods of unanticipated road congestion can result in failure of infrastructures, starting with the servicing base stations in the congested area. A sensitivity analysis on the compliance rate of evacuees shows non-intuitive effect on the spatial distribution of people and on the loading of the base stations. For example, an evacuation compliance rate of 70% results in higher number of overloaded base stations than the evacuation compliance rate of 90%.
- On a Self-Organizing MANET Event Routing Architecture with Causal Dependency AwarenessPei, Guanhong (Virginia Tech, 2009-11-23)Publish/subscribe (P/S) is a communication paradigm of growing popularity for information dissemination in large-scale distributed systems. The weak coupling between information producers and consumers in P/S systems is attractive for loosely coupled and dynamic network infrastructures such as ad hoc networks. However, achieving end-to-end timeliness and reliability properties when P/S events are causally dependent is an open problem in ad hoc networks. In this thesis, we present, evaluate benefits of, and compare with past work, an architecture design that can effectively support timely and reliable delivery of events and causally related events in ad hoc environments, and especially in mobile ad hoc networks (MANETs). With observations from both realistic application model and simulation experiments, we reveal causal dependencies among events and their significance in a typical use notional system. We also examine and propose engineering methodologies to further tailor an event-based system to facilitate its self-reorganizing capability and self-reconfiguration. Our design features a two-layer structure, including novel distributed algorithms and mechanisms for P/S tree construction and maintenance. The trace-based experimental simulation studies illustrate our design's effectiveness in both cases with and without causal dependencies.