David Ngar Ching Tse - US grants

ABSTRACT NCR-9734090 Tse, David Institution: University of California - Berkeley Title: CAREER: A Framework for Resource Allocation in Wireless Networks with Multi-User Receivers ________________________________________________________________ A central problem in the design of wireless networks is how to use the limited resources most to meet the quality-of-service requirements of applications. Two particular classes of techniques have received much attention: 1) at the physical layer, development of novel multi-user receiver structures which mitigate interference between users; 2) at the network layer, dynamic allocation of resources such as transmit power, bandwidth and bit-rates in adaptation to channel conditions. While the networking aspects for conventional multi-access techniques are well understood, the same cannot be said for problems of resource allocation and power control in the context of these multi-user receivers. In this project, we propose to establish a coherent framework to study problems of dynamic resource allocation for multi-user receivers in an integrated manner, drawing on information theory as a fundamental basis for performance evaluation. The specific topics we will study in the proposed framework are: 1) linear multi-user receivers: system capacity under optimal power control; 2) optimal resource allocation for Shannon capacity-achieving multi-user receivers; 3) capacity gain from the use of adaptive antenna arrays; 4) impact of multipath fading on achievable capacity; 5) resource allocation for cellular networks with multi-user receivers. The solution of problems in resource allocation and QOS provisioning in wireless networks requires a marriage of networking and physical layer concepts. With this in mind, my education plan aims to accomplish the more general goal of providing a solid theoretical basis to our students in networking and communications, as well as the more specific goal of highlighting the interplay between networking and physica l layer concepts in wireless networking. These goals will be implemented by course development in four subjects.

Integrated-services networks are expected to carry a class of traffic that has variable bit-rates and requires Quality of Service (QoS) guarantees. One of the main challenges is the provisioning of QoS to users while efficiently sharing network resources through statistical multiplexing. Admission control plays the essential role of limiting the number of flows admitted into the network such that each individual flow obtains the desired QoS. Measurement-based admission control (MBAC) is a practical way of achieving this objective through measuring the current and past variable traffic load in deciding how many flows can be admitted into the network.

Many issues have to be understood in the design of robust MBAC schemes. They include:

- impact of estimation errors on performance;
- effect of flow dynamics such as flow arrivals and departures;
- choice of measurement window size.

The goal of the proposed project is to establish a unified framework to study these and other issues in MBAC. We wish to obtain a set of guidelines for designing MBACs that are robust over a wide range of system parameters. Our methodology is to obtain insights from the analysis of a set of basic models, which are in turn validated with simulation experiments on real and synthetic traffic sources.

The preliminary investigation on a simple bufferless model yields simple expressions for the relevant performance measures as a function of key parameters such as system size, measurement window size, and
flow arrival and departure rates. The analysis provides basic insights for answering the questions asked above. One particularly interesting result is the identification of an important parameter ~T_h
which we call the critical time-scale for the MBAC problem. This parameter quantifies the amount of time a MBAC scheme has to predict into the future to provide good performance, and determine to a large extent the appropriate measurement window size.

The research proposes to build on this foundation and extend the framework to study the following issues:

- MBAC using aggregate versus individual flow measurements;
- MBAC for buffered links;
- impact of long-range dependency, multiple time-scale traffic dynamics, and non-stationarities;
- MBAC using direct QoS monitoring versus measurements of statistical parameters.

The design of efficient wireless communication systems relies on a
deep understanding of the basic characteristics of the underlying
channel. The most fundamental and unique characteristic of wireless
channels is the random time-variation of the channel strengths, a
phenomenon known as fading. Communication over fading channels has
been a topic of study since the 60's. A very different view of the
problem, however, emerges from recent research. The traditional view
of fading is that it is a source of unreliability that has to be
compensated for by various diversity techniques. The modern view is
much more
powerful and considers fading as a source of randomization from nature
that can be exploited to get very significant capacity boost.

The research project addresses several key problems within this
modern paradigm. They will be centered around two areas: 1)
opportunistic communication : the dynamic rate and power allocation
over the dimensions of time, frequency, antennas and users
so that transmission is done when and where the channel is strong;
2) multi-antenna communication: the use of multiple transmit and
receive antennas to increase the number of degrees of freedom available
for communication in richly scattered fading environments. The issues
studied are focused on how the random fading can be exploited even in
the face of
channel uncertainty, and the interplay between the modern and
traditional views of channel fading.

The next explosive growth in networks will come from connecting together billions of low cost, low power sensors, effectors, and smart devices. These will be communicating primarily through wireless means for reasons of mobility, ease of deployment, aesthetics, and cost. Even if such networks start out as special purpose local networks, people anticipate that they will come together in many ways. They will certainly be interconnected with each other through gateways to the broader wired Internet. The goal in this proposed project is to find the right architecture to enable Internet-like gains in the new context of wireless connectivity.

In order for wireless networks to support a wide range of applications and be suitable for mass deployment, they will need to posses the following characteristics: (1) negligible interference that allows peaceful co-existence with other independent wireless systems operating over the shared spectrum; (2) managing interference between nodes to efficiently and fairly share bandwidth; (3) dynamic and energy efficient routing and packet relaying algorithms that support mobility of network nodes; (4) scalability to support a large number of heterogeneous devices and links; (5) precise positioning capabilities to provide location information for the devices for which this is important; (6) robust and energy efficient network protocols that tolerate failure of some network nodes; (7) extremely low power wireless transceivers to ensure longevity for the energy-limited nodes; and (8) small and low cost wireless transceivers to enable widespread deployment.

This proposal is to study the above in the context of ultra-wideband (UWB) wireless signaling and multi-hop routing. Research is intended to achieve multiple objectives, Develop
(1) Efficient algorithms to determine the fundamental tradeoffs involved in tracking the positions of devices within a network of heterogeneous nodes;
(2) Robust and efficient protocols for routing digital communications within such networks and explore the fundamental capacity limits of such systems;
(3) Distributed signal processing algorithms that are network-energy and position aware to take advantage of correlations at the application layer to reduce resource consumption throughout the network hierarchy;
(4) Extremely low power, highly integrated single-chip CMOS architecture to UWB transceivers, and (5) An integrated test environment by combining an in-house FPGA-based testbed (as the digital back-end) with UWB analog front-end from AetherWire Inc. This will ultimately have approximately 30 UWB nodes from Aether Wire Inc. to test and therefore further discover issues involved with such networks.

Many of the innovative recent wireless devices rely on the unlicensed spectrum, spurred by its openness to new uses and users. At the same time, vast amounts of spectrum are still exclusively licensed to services with sparse demand and to standards that use antiquated technologies. The current way of sharing the
limited unlicensed spectrum that we do have is also far from perfect: devices suffer from very limited range even when there are no interference problems, and severe performance degradation when their local spectrum is shared by users from heterogeneous systems.

We look at spectrum management through the lens of the traditional 3 R's of resource use: Reduce, Reuse and Recycle. While Reduce has received by far the most attention from the engineering community, research in Recycle and Reuse is at a much more primitive state. But it is progress in the latter two areas that will be critical for the open and efficient sharing of the spectrum as a whole. Spectrum Recycling refers to fostering sharing and improving overall spectral efficiency while maintaining backward-compatibility with users of
legacy systems like analog broadcast and cellular standards. Spectrum Reuse refers to the collaborative coexistence of multiple wireless systems, using limited interaction to share the spectrum fairly and
efficiently. The proposed research takes a broad, systematic and inter-disciplinary approach to the fundamentals of these two problem areas, combining ideas from physical layer wireless communications,
multiuser information theory and distributed coding, resource allocation and game theoretic analysis.

ABSTRACT
0330514
Kannan Ramchandran
U of Cal Berkeley

Much of the current buzz around sensor networks has been driven by dramatic recent advances in sensor device technologies. Despite noteworthy efforts to build infrastructure and clever protocols to network these power-limited devices in order to push their operational envelopes for specific applications, a fundamental rather than an incremental understanding of the system performance limits of large-scale robust networks remains far from mature. It is a daunting system theory challenge to push the fundamental frontiers of sensor networks. It is this grand challenge that is the focus of this research. This study addresses scaling laws and robustness issues, but more importantly, aims at concrete design guidelines and algorithmic prescriptions. In short, this effort provides the much-needed systems theory expertise to make large-scale robust sensor networks a reality.

The overarching themes are (i) large scale, and (ii) robustness of sensor networks. Sensor networks are unique in that channel physics and sensor source models fundamentally underpin the sensor signals being acquired, processed, and distributed across the network for decision-making and control. Accordingly, channel physicsdrives scaling laws and percolates through all functional tasks. Percolation theory is used to study scaling laws and dictate designs for robust network connectivity. Sampling theory, is studied in a fundamental way to to address robustness versus performance tradeoffs between sensor oversampling density and per-sensor A/D precision under local communication constraints. Finally, this research ``closes the loop'' around sensor networks by studying distributed inference and robust control based on partial data using hybrid systems theory.

This collaborative research effort is organized into three highly coupled functional categories:

(i) Large-scale sensor network design guidelines: channel physics and percolation theory.

(ii) Sensor field representation and data acquisition: distributed sampling theory.

(iii) Distributed inference under communication constraints and robust adaptive control.

This award includes synergistic research in fundamental communications theory and the development of novel communications technologies. To make these research activities possible the principal investigators (PIs) will establish new and enhance the existing research infrastructure for research programs associated with the Center for Information Technology Research in the Interest of Society (CITRIS) and two of its members: the Berkeley Wireless Research Center (BWRC) and the Wireless Foundations Center (WFC). The purpose of this new infrastructure is to build a research environment that enables investigation of novel technologies for cognitive radios, high data rate transmission over wireless local area networks (WLANs), and wireless sensor networks.
The wireless explosion that the researchers are witnessing today can be largely attributed to the availability of unlicensed spectrum bands. New unlicensed bands are being allocated, for example the 5GHz of spectrum available worldwide at 60GHz. At the same time, a large majority of available spectrum is locked in by its pre-allocated use in legacy systems. The PIs will investigate methods of overlaying the legacy systems with new wireless systems, which allow the use of ultra-wideband (UWB) radios to operate in the 3-10GHz band. Simultaneously, the FCC is considering allowing unlicensed 'cognitive' radios to overlay allocated bands, such as TV spectrum overlay.
This award takes a broad and thorough inter-disciplinary approach to developing the fundamental understanding of the operation in new bands, such as 60GHz and UWB, spectrum reuse and spectrum recycling by cognitive radios, together with reducing the requirements of these systems to the basic hardware specifications of the underlying technology.
The researchers are developing a common computational, test and measurement infrastructure that will allow a quantum leap in wireless technology research and its applications. By building a common computational infrastructure, consisting of compute servers, clusters of workstations and FPGA-based emulation, the researchers will foster the propagation of information from theory to prototypes. To fundamentally understand the physical properties of new bands as well as new methods of spectrum utilization and coexistence of various systems, the researchers will make a major investment in test and measurement infrastructure.
Broader Impact. This common infrastructure will support the research of over a hundred graduate students, tens of undergraduate researchers and more than ten faculty. To maximize the impact, in addition to the traditional means of publications, the research results will be disseminated through participation in communications standardization processes, participation in government and NSF-sponsored studies on wireless technology and policies, and industry involvement. Research results will be used to form new graduate and undergraduate courses that will be taught in Berkeley and elsewhere.

Two important features distinguish wireless communication from wireline communication: the time-variations of the wireless links and the broadcast property of wireless transmissions.
In the past decade, a new fundamental understanding of time-variations from an information theoretic point of view has developed. This understanding has led to radical shifts in points of view regarding wireless system design, not only at the physical layer but also at
higher layers. In contrast, the progress in a fundamental understanding of the broadcast nature of wireless links has been far slower. Most of the techniques that exist as implemented in current wireless networks to deal with interference and cooperation are ad hoc.

In this project we focus on the broadcast nature of the wireless link by taking a cue from the success in dealing with the time varying nature of the wireless link: true progress in wireless communication comes from a synthesis of a fundamental and information theoretic understanding into networking ideas.

We propose to (a) obtain a fundamental understanding of how to optimally manage interference and achieve cooperation, (b) build an abstraction of the physical layer that captures the performance benefits of optimal interference management and cooperation, and (c) identify scenarios in which such optimal techniques yield significant improvement beyond
current techniques. We envision the broader impact of this research agenda to influence the design rules by which the interference and cooperation are dealt with in next generation of wireless networks.

Claude Shannon's point-to-point information theory is a basis for the design of all modern day communication systems, ranging from cellular communications, cable and DSL modems, statellite communications, compact disks, etc. Extending the theory from point-to-point communication to an entire network of communicating nodes is a holy grail of the communication field. It is expected that such an information theory of networks would have a significant impact for applications such as wireless and sensor networks. Yet, despite significant effort in the past 40 years, only isolated cases have been solved and there is still limited understanding of central issues such as interference, cooperation, broadcast and distributed compression of correlated information.

This research advocates a new general approach to attack network information theory problems. The new approach involves three steps: 1) approximate the noisy network with an appropriately chosen deterministic model which focuses on the interaction between the various signals rather than the noise; 2) analyze the analytically simpler deterministic model; 3) translate the insight into finding approximately optimal strategy for the original noisy network with guaranteed performance bound. Significant progress on several canonical long-standing open problems shows the power of the approach: 1) capacity region of the two-user Gaussian interference channel to within 1 bit/s/Hz per user; 2) capacity of the Gaussian (single-node) relay channel to within 1 bit/s/Hz; 3) capacity of the Gaussian relay network with arbitrary number of relays to within constant gap independent of the SNR's of the links; 4) rate region of the Gaussian multiple description problem to within a constant gap independent of the target distortions of the users.

Traditionally, feedback has been mainly used in communication systems for retransmission and for channel prediction. Several recent results in network information theory have identified a new role for feedback: exploiting side information to mitigate interference. Due to the broadcast nature of communication media, information intended for one user is often received by other users. Feedback can be used to exploit this side information to improve the efficiency of future transmissions. The proposed work builds upon these results to come up with a theory unifying the existing isolated results as well as broadening to more scenarios of interest. It will also identify specific problems to solve for realizing this new role of feedback in practice. The goal is to close the gap between feedback research in information theory and the design of feedback mechanisms in practice.

Objective:
The objective of this program is to build on the theoretical foundations of cooperative communications, and to develop key components of a communications system that would enable such a system in practice. In particular, the goal is to investigate the detailed implementation of a cooperation technique between the source terminal and multiple relays to increase the capacity of an uplink in the context of WLAN and cellular systems.

Intellectual merit:
The intellectual merit of this program is the development of the theoretical foundation, the necessary system design principles, and the demonstration of a prototype system of cooperative wireless systems that will enable future capacity scaling of wireless communications. The goal of this system will be to achieve a throughput gain in wireless systems that increases with the number of single-hop relays in the system, while maintaining low-complexity operations at each of the relays. The target system will be designed and evaluated on a configurable radio platform.

Broader impacts:
The broader impacts include the development of networks that meet the vision of inexpensive wireless broadband access everywhere as outlined in the National Broadband Plan. Through our industrial relations, the developed technology will be transformed from theory toward a commercial practice, simultaneously providing means for corresponding regulatory and standardization changes. A new generation of engineers will be educated, able to envision, analyze and develop practical wireless communications systems of the future. To broaden the impact, practical applications of our work will be incorporated in graduate curricula and outreach to underrepresented groups.

? DESCRIPTION (provided by applicant): RNA-Seq has revolutionized transcriptomics and is one of the most important high-throughput sequencing assays invented in recent years. The key computational problem is that of de novo assembly: the reconstruction of the transcripts and their abundances from tens to hundreds of millions of short reads. The problem is challenging due to a confluence of several factors: large number of different transcripts (tens of thousands), long repeat across transcripts due to alternative splicing, widely varying abundances across transcripts, and the presence of read errors. Existing assemblers are mostly designed based on heuristic considerations and implement ad hoc methods that lead to unreliable transcriptome reconstructions. An accurate RNA-Seq assembler would enable more accurate identification of fusions in cancer transcriptomes, better gene annotations in model and non-model organisms, and more complete analyses of the dynamics of alternative splicing driving developmental and regulatory programs. In this proposal, we offer a systematic approach to the design of RNA-Seq assemblers based on information theoretic principles. We start by determining conditions data that guarantee that there enough information to reconstruct the transcriptome, and then propose an assembly algorithm that can reconstruct with the minimal information. This algorithm optimally uses the available read information to resolve repeats and disambiguate isoforms. A key insight derived from the information theoretic approach is that widely varying abundances across transcripts, rather than a complication, can actually be exploited as signatures of different transcripts to disambiguate among them. Based on our initial ideas, we have built, evaluated and compared an initial prototype with several existing software, on both real and simulated data. The encouraging results provide evidence that our approach, which we will fully develop, implement and evaluated during the funded period, can significantly outperform existing software. Additional functionalities such as mixed short/long read assembly, genome-assisted assembly and joint processing of multiple RNA samples, will be designed and incorporated into the software as part of the proposed project.

The IEEE International Symposium on Information Theory (ISIT) is the annual conference of the information theory society, and has been held continuously since 1954. It covers a variety of topics related to the studies on information theory, including coding, communications and communication networks, complexity and cryptography, detection and estimation, learning, Shannon Theory, stochastic processes, and emerging applications of information theory. It is considered one of the premier IEEE conferences. ISIT has also traditionally attracted a large number of students, comprising around 40 percent of the participant population. ISIT is an excellent learning opportunity for students as well as a means to establish useful research collaborations for the future. Providing some support for student in the US to travel to ISIT, especially given the long distance they need to travel to ISIT 2015, will be crucial to ensuring a vibrant student participation.

This project therefore provides student travel support for the 2015 ISIT meeting.

Statistical-modeling is the cornerstone of analyzing modern data sets, and using observed data to learn the underlying statistical model is a crucial part of most data analysis tasks. However, with the success of data utilization came a vast increase in its complexity as expressed in complex models, numerous parameters, and high dimensional features. This research project studies problems in learning such high-dimensional models, both in theory and in practice with actual datasets in cutting-edge applications.

Learning high-dimensional models efficiently, both in terms of computation and in terms of the use of the data, is an important challenge. The research characterizes the fundamental limits on the sample and computational complexity of several key distribution learning problems, as well as the associated optimal learning algorithms that achieve the limits. The learning problems underpin important tasks such as clustering, multiple testing of hypothesis and information measure estimation. The new algorithms and new methodologies developed are evaluated and applied on real data from three specific applications: 1) denoising of high throughput transcriptomic data; 2) analysis of omics data for personalized medicine; 3) ecological population studies. While these applications are useful on their own right, there will also be many other potential applications in fields such as speech recognition, topic modeling, character recognition, neuroscience, etc.

In the modern era of big data, although the cost of labeling and analyzing a single data sample has been decreasing rapidly, it is usually outpaced by the unrivaled fast growth of dataset size, which makes it particularly timely to design unsupervised learning algorithms that are able to discover meaningful structures of data without extensive human efforts. Recently, Generative Adversarial Networks (GANs) have emerged as a thriving unsupervised machine learning technique that has led to significant advances in various fields such as computer vision, natural language processing, and others. GANs can generate high-quality realistic images based on unlabeled natural images and perform sophisticated tasks such as synthesizing photos from sketches and coloring images. However, there also exist challenges that need timely solutions. The training of GANs has been reportedly observed to be challenging, unstable, and not easily reproducible. This project seeks to conduct a systematic study of GANs through the fundamental formulation, generalization and optimization issues. The transformative potential of the project is in the development of foundational tools and practical guidelines through novel combinations of optimal transport, information theory, convex geometry, and empirical process theory.

The goal of this project is four-fold: (1) develop a theoretical framework for analyzing the generalization properties of GANs in high-dimensions; (2) suggest principled approaches to design GANs to achieve optimal statistical properties; (3) diagnose GANs when issues such as mode collapse or discriminator winning occur; (4) develop computationally efficient algorithms that can attain the statistical limits of well-designed GANs. The theory and algorithms developed within this projection will have impact on various engineering and scientific applications and provide insights for the proper usage of GANs in the real world.

This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.