Person:

Lin, Tsung-Han

This paper presents the design of MIMO/CON (“MIMO with concurrent channel access and estimation”), a PHY/MAC cross-layer design delivering throughput scalable to many users for multiuser MIMO wireless networking. By allowing concurrent launches of multiple data transmissions from multiple users, MIMO/CON can fully realize the capacity gain of a multi-antenna MIMO system. Using compressive sensing, MIMO/CON simultaneously estimates channel state information (CSI) of multiple channels from concurrently received preambles. Furthermore, MIMO/CON can boost channel utilization by allowing concurrent transmissions to exceed receive antennas momentarily. MIMO/CON has been implemented and evaluated on a lab testbed with software-defined radios. Further, simulation results suggest that MIMO/CON can achieve an improvement by up to 210% in MAC throughput over existing staggered access protocols in a 5×5 MIMO scenario.

We propose a medium access control (MAC) protocol for wireless local area networks (LANs) that leverages the theory of compressive sensing. The proposed compressive sensing MAC (CS-MAC) exploits the sparse property that, at a given time, only a few hosts are expected to request for radio channel access. Under CS-MAC, a central coordinator, such as a wireless access point (AP) can recover a multitude of these requests in one decoding operation, and then schedule multiple hosts accordingly. The coordinator is only required to receive a relatively small number of random projections of host requests, rather than polling individual hosts. This results in an efficient request-grant method. Via a hardware prototype based on a software-de ned radio platform, we demonstrate the feasibility of realizing CS-MAC with compressive measurements formed in the air to achieve high efficiency.

We characterize a general class of algorithms common in machine learning, scientific computing, and signal processing, whose computational dependencies are both sparse, and dynamically defined throughout execution. Existing parallel computing runtimes, like MapReduce and GraphLab, are a poor fit for this class because they assume statically defined dependencies for resource allocation and scheduling decisions. As a result, changing load characteristics and straggling compute units degrade performance significantly. However, we show that the sparsity of computational dependencies and these algorithms’ natural error tolerance can be exploited to implement a flexible execution model with large efficiency gains, using two simple primitives: selective push-pull and statistical barriers. With reconstruction for compressive time-lapse MRI as a motivating application, we deploy a large Orthogonal Matching Pursuit (OMP) computation on Amazon’s EC2 cluster to demonstrate a 19x speedup over current static execution models.

Conjugate gradient is an important iterative method used for solving least squares problems. It is compute-bound and generally involves only simple matrix computations. One would expect that we could fully parallelize such computation on the GPU architecture with multiple Stream Multiprocessors (SMs), each consisting of many SIMD processing units. While implementing a conjugate gradient method for compressive sensing signal reconstruction, we have noticed that large speed-up due to parallel processing is actually infeasible due to the high I/O cost between SMs and GPU global memory. WE have found that if SMs were linearly connected, we could gain a 15x speedup by loop unrolling. We conclude that adding these relatively inexpensive neighbor connections for SMs can significantly enhance the applicability of GPUs to a large class of similar matrix computations.

Wireless data transfer under high mobility, as found in unmanned aerial vehicle (UAV) applications, is a challenge due to varying channel quality and extended link outages. We present FlowCode, an easily deployable link-layer solution utilizing multiple transmitters and receivers for the purpose of supporting existing transport protocols such as TCP in these scenarios. By using multiple transmitters and receivers and by exploiting the resulting antenna beam diversity and parallel transmission effects, FlowCode increases throughput and reception range. In emulation, we show that TCP over FlowCode gives greater goodput over a larger portion of the flight path, compared to an enhanced TCP protocol using the standard 802.11 MAC. In the process, we make a strong case for using trace-modulated emulation when developing distributed protocols for complex wireless environments.

We consider the problem of mitigating a highly varying wireless channel between a transmitting ground node and receivers on a small, low-altitude unmanned aerial vehicle (UAV) in a 802.11 wireless mesh network. One approach is to use multiple transmitter and receiver nodes that exploit the channel's spatial/temporal diversity and that cooperate to improve overall packet reception. We present a series of measurement results from a real-world testbed that characterize the resulting wireless channel. We show that the correlation between receiver nodes on the airplane is poor at small time scales so receiver diversity can be exploited. Our measurements suggest that using several receiver nodes simultaneously can boost packet delivery rates substantially. Lastly, we show that similar results apply to transmitter selection diversity as well.

In this paper, we use a finite-state model to predict the performance of the Transmission Control Protocol (TCP) over a varying wireless channel between an unmanned aerial vehicle (UAV) and ground nodes. As a UAV traverses its flight path, the wireless channel may experience periods of significant packet loss, successful packet delivery, and intermittent reception. By capturing packet run-length and gap-length statistics at various locations on the flight path, this location-dependent model can predict TCP throughput in spite of dynamically changing channel characteristics. We train the model by using packet traces from flight tests in the field and validate it by comparing TCP throughput distributions for model-generated traces against those for actual traces randomly sampled from field data. Our modeling methodology is general and can be applied to any UAV flight path.

We present FlowCode, a system that exploits network coding at the granularity of traffic flows to facilitate fault-tolerant data exchange in wireless mesh networks. Applications include multi-site data replication in ad-hoc environments such as mesh networks or wireless data centers. By coupling an operand-driven transmission mechanism with a layered network topology, FlowCode allows us to realize the gains of network coding in application systems without a global scheduler. We analyze the resulting gains through modeling and simulation and validate our results on an outdoor testbed of 12 wireless devices. Results indicate that in high loss environments, FlowCode provides the most significant gains from improved fault tolerance over redundant paths.

Recent theoretical study shows that the sparsest solution to an underdetermined linear system is unique, provided the solution vector is sufficiently sparse, and the operator matrix has sufficiently incoherent column vectors. In addition, efficient algorithms have been discovered to find such solutions. This intriguing result opens a new door for many potential applications. In this thesis, we study the design of a class of greedy algorithms that are extremely efficient, e.g., Orthogonal Matching Pursuit (OMP). These greedy algorithms suffer from a stability issue that the greedy selection approach always make locally optimal decisions, thereby easily biasing and mistaking the solutions in particular under data noise. We propose a solution approach that in designing greedy algorithms, new constraints can be devised by leveraging application-specific insights and incorporated into the algorithms. Given that sparse recovery problems by definition are underdetermined, introducing additional constraints can significantly improve the stability of greedy algorithms, yet retain their efficiency.