Uplink transmit power control is crucial for resource allocation and interference management in DS-CDMA systems. In literature, specific distributed algorithms are proposed and their convergence rates are evaluated. In this letter, we explore the optimal achievable convergence rate. We first understand power control as a channel coding problem and derive an upper bound on the convergence rate. Then we propose coding power control bits across users, suggesting the achievability of the bound. Finally we use this upper bound to evaluate the uplink power control overhead in IS-95 systems.

## Type of Work

Article (3) Book (0) Theses (5) Multimedia (0)

## Peer Review

Peer-reviewed only (8)

## Supplemental Material

Video (0) Audio (0) Images (0) Zip (0) Other files (0)

## Publication Year

## Campus

UC Berkeley (7) UC Davis (0) UC Irvine (0) UCLA (0) UC Merced (0) UC Riverside (0) UC San Diego (0) UCSF (0) UC Santa Barbara (0) UC Santa Cruz (0) UC Office of the President (1) Lawrence Berkeley National Laboratory (0) UC Agriculture & Natural Resources (0)

## Department

Research Grants Program Office (RGPO) (1)

## Journal

## Discipline

## Reuse License

## Scholarly Works (8 results)

Interference is a central phenomenon in wireless networks of all types, occurring whenever multiple users attempt to communicate over a shared medium. Current state-of-the-art systems rely on two basic approaches: orthogonalizing communication links, or treating interference as noise. These approaches both suffer from a swift degradation in performance as the number of users in the system grows large. Recently, interference alignment has emerged as a promising new perspective towards mitigating interference. The extent of the potential benefit of interference alignment was observed by Cadambe and Jafar (2008), who showed that for time-varying or frequency selective channels, K/2 total degrees of freedom are achievable in a K-user interference channel. In the context of the result, this means that interference causes essentially no degradation at all in performance as the number of users grows. However, a caveat is that the number of independent channel realizations needed over time or frequency, i.e. the channel diversity, is unbounded. Actual communication systems have only finite channel diversity, and thus the practical implications of interference alignment are uncertain: Just how much channel diversity is required in order to get substantial benefit from interference alignment? The first part of this thesis focuses on this question. Our first result characterizes the degrees of freedom for the three-user interference channel as a function of time or frequency diversity. We next focus on spatial diversity, in the form of multiple antennas at transmitters and receivers. We characterize the degrees of freedom for the symmetric three-user multiple-input multiple-output interference channel. This result is partially generalized to an arbitrary number of users, under a further symmetry assumption.

The second part of this thesis studies DNA sequencing from an information theory point-of-view. DNA sequencing is the basic workhorse of modern day biology and medicine. Shotgun sequencing is the dominant technique used: many randomly located short fragments called reads are extracted from the DNA sequence, and these reads are assembled to reconstruct the original sequence. During the last two decades, many assembly algorithms have been proposed, but comparing and evaluating them is difficult.

To clarify this, we ask: Given N reads of length L sampled from an arbitrary DNA sequence, is it possible to achieve some target probability 1-epsilon of successful reconstruction? We show that the answer depends on the repeat statistics of the DNA sequence to be assembled, and we compute these statistics for a number of reference genomes.

We construct lower bounds showing that reconstruction is impossible for certain choices of N and L, and complement this by analytically deriving the performance of several algorithms, both in terms of repeat statistics. In seeking an algorithm that matches the lower bounds on real DNA data, we are able to methodically progress towards an optimal assembly algorithm. The goal of this work is to advocate a new systematic approach to the design of assembly

algorithms with an optimality or near-optimality guarantee.

### Control and Optimization of Power Systems with Renewables: Voltage Regulation and Generator Dispatch

The electric power system is undergoing dramatic transformations due to the emergence of renewable resources. However, integrating these resources into the electric grid has proven to be difficult for two main reasons: these resources are uncertain and distributed. This thesis discusses how uncertainty and distributedness of the new resources are manifested as challenges in time and spatial scales, and how we can optimally control the power grid to overcome these challenges.

The theme of this thesis is that in order to control the new resources, we need a better understanding of the physical power flow in the system. To illustrate the spatial-scale challenge, we consider the voltage regulation problem for distribution networks. With a deep penetration of distributed energy resources the voltage magnitudes in a distribution system can fluctuate significantly. To control these resources such that voltage profiles remain flat, we need to coordinate the tens of thousands of households in the distribution network. By studying the geometry of power flows in the network, we show that even though the voltage regulation problem is non-convex, it can be convexified exactly through a semidefinite relaxation . Based on this insight, we an optimal and decentralized algorithm for this problem. Only communication between electrical neighbors are required in the algorithm, thus allowing it to scale to problem of large sizes.

The second problem we consider is dispatching generators in the transmission network under deep penetration of wind power. Because of on/off and ramp-rate constraints, traditional generators need to be dispatched before the actual time of delivery of energy. On the other hand, wind power cannot be dispatched and is difficult to predict in advance. This creates a mismatch in time-scale between the controls (traditional generators) and the randomness in the system (wind). We capture this challenge as a two-stage stochastic dispatch problem. In contrast to the standard Monte Carlo solutions, we show that the dimensional of the problem can be reduced dramatically by using forecast informations. This dimensional reduction is based on a better understanding of congested DC optimal power flow problems. Using this reduction, we show how to calculate the optimal reserve margin for the system in the presence of renewables, and quantify the intrinsic impact of uncertainties on the system cost.

The increasing complexity of communication networks in size and density provides us enormous opportunities to exploit interaction among multiple nodes, thus enabling higher date rate of data streams. On the flip side, however, this complexity comes with challenges in managing interference that multiple source-destination pairs in the network may cause to each other. In this dissertation, we make progress on how we exploit the opportunities, as well as how we overcome the challenges.

In the first part, we find that feedback - one of the common ways to enable interaction in networks - has a promising role in improving the capacity performance of networks. Earlier results on feedback capacity were somewhat discouraging. This is mainly due to Shannon's original result on feedback capacity where he showed that in point-to-point communication, feedback does not increase capacity. Hence, traditionally it is believed that feedback has had little impact on increasing capacity of communication links. Therefore, the use of feedback has been limited to improving the reliability of communications, usually in the form of ARQ. In this dissertation, we show that in stark contrast to the point-to-point case, feedback can improve the capacity of interference-limited network. In fact, the improvement can be unbounded. This result shows that feedback can have a potentially significant role to play in mitigating interference. Also in the process of deriving this conclusion, we characterize the feedback capacity of the two-user Gaussian interference channel to within 2 bits, one of the longstanding open problems in network information theory.

In the second part, we propose a new interference management technique for widely deployed cellular networks. Inspired by a recent breakthrough, the concept of interference alignment, we develop an interference alignment technique for cellular networks. Our technique promises almost interference-free communication with the increase of the number of clients in cellular networks. It shows substantial gain (around 30% to 60%) as compared to one of the interference management techniques in current cellular systems. In addition, it comes with implementation benefits: it can actually be implemented with small changes to emerging 4G cellular standards and architectures at the base-stations and clients. In particular, the required signal-processing circuitry, software control, and channel-state feedback mechanisms are extensions of existing implementations and standards.

Lastly, we extend the interference alignment principle, developed in the context of wireless networks, into other fields of network research such as storage networks. In an effort to protect information against node failures, storage networks employ coding techniques, such as maximum distance separable (MDS) erasure codes, known as optimal codes in reliability with respect to redundancy. However, these MDS codes come with prohibitive maintenance cost when it comes to repairing failed storage nodes. While only partial information stored in the failed node needs to be recovered, the conventional MDS codes focus on the complete data recovery (including unwanted data, corresponding to interference) by downloading too much information from survivor storage encoded nodes, thus causing the high repair cost. Building on the connection between wireless and wireline networks, we leverage the interference alignment principle to develop a new class of MDS codes that significantly reduces the repair cost over the conventional MDS codes and also achieves information-theoretic optimal bound on the repair cost for all admissible code parameters.

With the growing number of users along with ever-increasing demand for higher data rates and better quality of service in modern wireless networks, interference has become the major barrier against efficient utilization of limited resources. On the other hand, opportunities for cooperation among radios also increase with the growing number of users, which potentially lead to better interference management. In traditional wireless system design, however, such opportunities are usually neglected and only basic interference management schemes are employed, mainly due to lack of fundamental understanding of interference and cooperation.

In this dissertation, we study the fundamental aspects of cooperative interference management through the lens of network information theory. In the first and the second part, we characterize both qualitatively and quantitatively how limited cooperation between transmitting or receiving terminals helps mitigate interference in a canonical two-transmitter-two-receiver wireless system. We identify two regions regarding the gain from limited cooperation: linear and saturation regions. In the linear region cooperation is efficient and provides a degrees-of-freedom gain, which is either one cooperation bit buys one bit over the air or two cooperation bits buy one bit over the air until saturation. In the saturation region cooperation is inefficient and only provides a bounded power gain. The conclusions are drawn from the approximate characterization of the capacity regions.

In the third part, we investigate how intermediate relay nodes help resolve interference in delivering information from two sources to their respective destinations in multi-hop wireless networks. We focus on a linear deterministic approximate model for wireless networks, and when the minimum cut value between each source-destination pair is constrained to be 1, we completely characterize the capacity region. One of the interesting findings is that, at most four nodes need to take special coding operations so that interference can be canceled over-the-air or within-a-node, while other nodes can take oblivious operations. We also develop a systematic approach to identify these special nodes.

Shannon theory has been very successful in studying fundamental limits of communication in the classical setting, where one sender wishes to communicate a message to one receiver over an unreliable medium. The theory has also been successful in studying networks of small to moderate sizes, with multiple senders and multiple receivers. However, it has become well-known recently that understanding the fundamental limits of communication in a general network is a hard problem on numerous accounts.

In this dissertation, we suggest that a significant aspect of the difficulty in studying limits of communication over networks lies in the unidirectional aspect of the problem. Under different assumptions that rid the problem of this particular aspect by introducing a suitable symmetry, either in the underlying network or in the traffic model, we find that simple schemes are approximately optimal in achieving these fundamental limits. We demonstrate this as a meta-theorem in the class of wireline networks and Gaussian networks. The key contribution driving these results is a new outer bound that we call the Generalized Network Sharing bound.

We also study a problem of simulation of joint distributions in a non-interactive setup. Two agents observe correlated random variables and wish to simulate a certain joint distribution. We consider a non-asymptotic formulation of this problem and study tools that help prove impossibility results. We also study connections of this problem to existing problems in the literature.