We present EEPrune, a novel dataset pruning algorithm that leverages early exit networks during training. EEPrune utilizes the innate ability of early exit networks to assess the difficulty of individual samples and avoid overthinking. It applies multiple criteria to decide whether to prune them. Specifically, for a training sample to be discarded, the confidence level of the model at the early exit should be above a certain threshold, along with a correct classification at both the early exit and final layers. Extensive experiments and ablations on CIFAR-10, CIFAR-100, Tiny ImageNet, KMNIST, and ImageNet datasets demonstrate that EEPrune consistently outperforms other dataset pruning methods.

We introduce Model-Distributed Inference for Large-Language Models (MDI-LLM), a novel framework designed to facilitate the deployment of state-of-the-art large-language models (LLMs) across low-power devices at the edge. This is accomplished by dividing the model into multiple partitions, which are then assigned to different devices/nodes within the network. These nodes exchange intermediate activation vectors via device-to-device links, enabling collaborative computation. To enhance the efficiency of this process, we propose the "recurrent pipeline parallelism" technique, which reduces idle time on each device and facilitates parallel inference during the generation of multiple text sequences. By leveraging the combined computational resources of multiple edge devices, MDI-LLM enables the deployment of LLMs that exceed the memory capacity of individual devices, making it possible to perform inference on low-cost hardware. Furthermore, as the number of participating devices increases, MDI-LLM boosts token generation throughput and reduces memory usage.

We introduce the Humanistic Buddhism Corpus (HBC), a dataset containing over 80,000 Chinese-English parallel phrases extracted and translated from publications in the domain of Buddhism. HBC is one of the largest free domain-specific datasets that is publicly available for research, containing text from both classical and modern Chinese. Moreover, since HBC originates from religious texts, many phrases in the dataset contain metaphors and symbolism, and are subject to multiple interpretations. Compared to existing machine translation datasets, HBC presents difficult unique challenges. In this paper, we describe HBC in detail. We evaluate HBC within a machine translation setting, validating its use by establishing performance benchmarks using a Transformer model with different transfer learning setups.

Distributed inference techniques can be broadly classified into data-distributed and model-distributed schemes. In data-distributed inference (DDI), each worker carries the entire deep neural network (DNN) model but processes only a subset of the data. However, feeding the data to workers results in high communication costs, especially when the data is large. An emerging paradigm is model-distributed inference (MDI), where each worker carries only a subset of DNN layers. In MDI, a source device that has data processes a few layers of DNN and sends the output to a neighboring device, i.e., offloads the rest of the layers. This process ends when all layers are processed in a distributed manner. In this paper, we investigate the design and development of MDI with early-exit, which advocates that there is no need to process all the layers of a model for some data to reach the desired accuracy, i.e., we can exit the model without processing all the layers if target accuracy is reached. We design a framework MDI-Exit that adaptively determines early-exit and offloading policies as well as data admission at the source. Experimental results on a real-life testbed of NVIDIA Nano edge devices show that MDI-Exit processes more data when accuracy is fixed and results in higher accuracy for the fixed data rate.

We consider semantic segmentation of images using deep neural networks. To reduce the computational cost, we incorporate the idea of early exit, where different pixels can be classified earlier in different layers of the network. In this context, existing work utilizes a common threshold to determine the class confidences for early exit purposes. In this work, we propose Class Based Thresholding (CBT) for semantic segmentation. CBT assigns different threshold values to each class, so that the computation can be terminated sooner for pixels belonging to easy-to-predict classes. CBT does not require hyperparameter tuning; in fact, the threshold values are automatically determined by exploiting the naturally-occurring neural collapse phenomenon. We show the effectiveness of CBT on Cityscapes, ADE20 K and COCO-Stuff-10 K datasets using both convolutional neural networks and vision transformers. CBT can reduce the computational cost by up to 23% compared to the previous state-of-the-art early exit semantic segmentation models, while preserving the mean intersection over union (mIoU) performance.

Self-supervised representation learning and deep clustering are mutually beneficial to learn high-quality representations and cluster data simultaneously in centralized settings. However, it is not always feasible to gather large amounts of data at a central entity, considering data privacy requirements and computational resources. Federated Learning (FL) has been developed successfully to aggregate a global model while training on distributed local data, respecting the data privacy of edge devices. However, most FL research effort focuses on supervised learning algorithms. A fully unsupervised federated clustering scheme has not been considered in the existing literature. We present federated momentum contrastive clustering (FedMCC), a generic federated clustering framework that can not only cluster data automatically but also extract discriminative representations training from distributed local data over multiple users. In FedMCC, we demonstrate a two-stage federated learning paradigm where the first stage aims to learn differentiable instance embeddings and the second stage accounts for clustering data automatically. The experimental results show that FedMCC not only achieves superior clustering performance but also outperforms several existing federated self-supervised methods for linear evaluation and semi-supervised learning tasks. Additionally, FedMCC can easily be adapted to ordinary centralized clustering through what we call momentum contrastive clustering (MCC). We show that MCC achieves state-of-the-art clustering accuracy results in certain datasets such as STL-10 and ImageNet-10. We also present a method to reduce the memory footprint of our clustering schemes.

We consider the problem of clustering a dataset through multiple noisy observations of its members. The goal is to obtain a clustering that is as faithful to the clustering of the original dataset as possible. We propose a centroidal approach whose distortion measure is the sum of r th powers of the distances between the cluster center and the noisy observations. For r=2 , our scheme boils down to the well-known approach of clustering the average of noisy samples. First, we provide a mathematical analysis of our clustering scheme. In particular, we find formulas for the average distortion and the spatial distribution of the cluster centers in the asymptotic regime where the number of centers is large. We then provide an algorithm to numerically optimize the cluster centers in the finite regime. We extend our method to automatically assign weights to noisy observations. Finally, we show that for various practical noise models, with a suitable choice of r , our algorithms can outperform several other existing techniques over various datasets.

Random walk learning (RWL) has recently gained a lot of attention thanks to its potential for reducing communication and computation over edge networks in a decentralized fashion. In RWL, each node in a graph updates a global model with its local data, selects one of its neighbors randomly, and sends the updated global model. The selected neighbor becomes a newly activated node, so it updates the global model using its local data. This continues until convergence. Despite its promise, RWL has two challenges: (i) training time is long, and (ii) nodes should have the complete model. Thus, in this paper, we design Random Walking Snakes (RWS), where a set of nodes instead of one node is activated for model update, and each node in the set trains a part of the model. Thanks to model partitioning and parallel processing in the set of activated nodes, RWS reduces both the training time and the amount of the model that needs to be stored. We also design a novel policy that determines the set of activated nodes by taking into account the computing power of nodes. Simulation results show that RWS significantly reduces the convergence time as compared to RWL.

Existing deep learning-based Text-to-Speech (TTS) mechanisms are computationally intensive, which puts a strain in their practical applications especially over edge networks comprised of resource constrained devices. Our focus is on distributing TTS tasks across multiple devices (i.e., workers) at edge networks and providing TTS-aware resiliency against straggling workers. In particular, we design a REsilient DIstributed Tts (REDIT) framework by exploiting the text summarization as redundancy to provide resiliency for distributed TTS. We show analytically that REDIT improves the task completion time as compared to the distributed TTS without resiliency. We determine the optimum amount of redundancy/summary based on our task completion time analysis. We implement our REDIT framework in a real testbed consisting of NVIDIA Jetson Nano cards, and show that our REDIT algorithm improves the task completion delay as compared to baselines.

Power iteration is a fundamental algorithm in data analysis. It extracts the eigenvector corresponding to the largest eigenvalue of a given matrix. Applications include ranking algorithms, principal component analysis (PCA), among many others. Certain use cases may benefit from alternate, non-linear power methods with low complexity. In this paper, we introduce multiplication-avoiding power iteration (MAPI). MAPI replaces the standard ℓ2inner products that appear at the regular power iteration (RPI) with multiplication-free vector products, which are Mercer-type kernels that induce the ℓ1norm. For an n × n matrix, MAPI requires n multiplications, while RPI needs n2multiplications per iteration. Therefore, MAPI provides a significant reduction of the number of multiplication operations, which are known to be costly in terms of energy consumption. We provide applications of MAPI to PCA-based image reconstruction as well as to graph-based ranking algorithms. When compared to RPI, MAPI not only typically converges much faster, but also provides superior performance.

State-of-the-art neural networks with early exit mechanisms often need considerable amount of training and fine tuning to achieve good performance with low computational cost. We propose a novel early exit technique, Early Exit Class Means (E2CM), based on class means of samples. Unlike most existing schemes, ECM does not require gradient-based training of internal classifiers and it does not modify the base network by any means. This makes it particularly useful for neural network training in low-power devices, as in wireless edge networks. We evaluate the performance and overheads of E2CM over various base neural networks such as MobileNetV3, EfficientNet, ResNet, and datasets such as CIFAR-100, ImageNet, and KMNIST. Our results show that, given a fixed training time budget, E2CM achieves higher accuracy as compared to existing early exit mechanisms. Moreover, if there are no limitations on the training time budget, E2CM can be combined with an existing early exit scheme to boost the latter's performance, achieving a better trade-off between computational cost and network accuracy. We also show that E2CM can be used to decrease the computational cost in unsupervised learning tasks.

The traditional approach to distributed deep neural network (DNN) training is data-distributed learning, which partitions and distributes data to workers. This approach, although has good convergence properties, has high communication cost, which puts a strain especially on edge systems and increases delay. An emerging approach is model-distributed learning, where a training model is distributed across workers. Model-distributed learning is a promising approach to reduce communication and storage costs, which is crucial for edge systems. In this paper, we design ResPipe, a novel resilient model-distributed DNN training mechanism against delayed/failed workers. We analyze the communication cost of ResPipe and demonstrate the trade-off between resiliency and communication cost. We implement ResPipe in a real testbed consisting of Android-based smartphones, and show that it improves the convergence rate and accuracy of training for convolutional neural networks (CNNs).

We consider a model-distributed learning framework in which layers of a deep learning model is distributed across multiple workers. To achieve consistent gradient updates during the training phase, model-distributed learning requires the storage of multiple versions of the layer parameters at every worker. In this paper, we design mcPipe to reduce the memory cost of model-distributed learning, which is crucial in memory-constrained edge computing devices. mcPipe uses an on-demand weight updating policy, which reduces the amount of weights that should be stored at workers. We analyze the memory cost of mcPipe and demonstrate its superior performance as compared to existing model-distributed learning mechanisms. We implement mcPipe in a real testbed and show that it improves the memory cost without hurting converge rate and computation cost.

Conventional principal component analysis (PCA) finds a principal vector that maximizes the sum of second powers of principal components. We consider a generalized PCA that aims at maximizing the sum of an arbitrary convex function of principal components. We present a gradient ascent algorithm to solve the problem. For the kernel version of generalized PCA, we show that the solutions can be obtained as fixed points of a simple single-layer recurrent neural network. We also evaluate our algorithms on different datasets.

Robust and computationally efficient anomaly detection in videos is a problem in video surveillance systems. We propose a technique to increase robustness and reduce computational complexity in a Convolutional Neural Network (CNN) based anomaly detector that utilizes the optical flow information of video data. We reduce the complexity of the network by denoising the intermediate layer outputs of the CNN and by using powers-of-two weights, which replaces the computationally expensive multiplication operations with bit-shift operations. Denoising operation during inference forces small valued intermediate layer outputs to zero. The number of zeros in the network significantly increases as a result of denoising, we can implement the CNN about 10% faster than a comparable network while detecting all the anomalies in the testing set. It turns out that denoising operation also provides robustness because the contribution of small intermediate values to the final result is negligible. During training we also generate motion vector images by a Generative Adversarial Network (GAN) to improve the robustness of the overall system. We experimentally observe that the resulting system is robust to background motion.

We consider a distributed edge computing scenario consisting of several wireless nodes that are located over an area of interest. Specifically, some of the “master” nodes are tasked to sense the environment (e.g., by acquiring images or videos via cameras) and process the corresponding sensory data, while the other nodes are assigned as “workers” to help the computationally-intensive processing tasks of the masters. A new tradeoff that has not been previously explored in the existing literature arises in such a formulation: On one hand, one wishes to allocate as many master nodes as possible to cover a large area for accurate monitoring. On the other hand, one also wishes to allocate as many worker nodes as possible to maximize the computation rate of the sensed data. It is in the context of this tradeoff that this work is presented. By utilizing the basic physical layer principles of wireless communication systems, we formulate and analyze the tradeoff between the coverage and computation performance of spatial networks. We also present an algorithm to find the optimal tradeoff and demonstrate its performance through numerical simulations.

We consider multiple unmanned aerial vehicles (UAVs) at a common altitude serving as data collectors to a network of IoT devices. First, using a probabilistic line of sight channel model, the optimal assignment of IoT devices to the UAVs is determined. Next, for the asymptotic regimes of a large number of UAVs and/or large UAV altitudes, we propose closed-form analytical expressions for the optimal data rate and characterize the corresponding optimal UAV deployments. We also propose a simple iterative algorithm to find the optimal deployments with a small number of UAVs at high altitudes. Globally optimal numerical solutions to the general rate maximization problem are found using particle swarm optimization.

Traditional reliability approaches introduce relevant costs to achieve unconditional correctness during data processing. However, many application environments are inherently tolerant to a certain degree of inexactness or inaccuracy. In this article, we focus on the practical scenario of image processing in space, a domain where faults are a threat, while the applications are inherently tolerant to a certain degree of errors. We first introduce the concept of usability of the processed image to relax the traditional requirement of unconditional correctness, and to limit the computational overheads related to reliability. We then introduce our new flexible and lightweight fault management methodology for inaccurate application environments. A key novelty of our scheme is the utilization of neural networks to reduce the costs associated with the occurrence and the detection of faults. Experiments on two aerospace image processing case studies show overall time savings of 14.89 and 34.72 percent for the two applications, respectively, as compared with the baseline classical Duplication with Comparison scheme.

We consider multiple unmanned aerial vehicles (UAVs) serving a density of ground terminals (GTs) as mobile base stations. The objective is to minimize the outage probability of GT-to-UAV transmissions. In this context, the optimal placement of UAVs under different UAV altitude constraints and GT densities is studied. First, using a random deployment argument, a general upper bound on the optimal outage probability is found for any density of GTs and any number of UAVs. Lower bounds on the performance of optimal deployments are also determined. The upper and lower bounds are combined to show that the optimal outage probability decays exponentially with the number of UAVs for GT densities with finite support. Next, the structure of optimal deployments are studied when the common altitude constraint is large. In this case, for a wide class of GT densities, it is shown that all UAVs should be placed to the same location in an optimal deployment. A design implication is that one can use a single multi-antenna UAV as opposed to multiple single-antenna UAVs without loss of optimality. Numerical optimization of UAV deployments are carried out using particle swarm optimization. Simulation results are also presented to confirm the analytical findings.

We consider the ad-hoc networks consisting of n wireless nodes that are located on the plane. Any two given nodes are called neighbors if they are located within a certain distance (communication range) from one another. A given node can be directly connected to any one of its neighbors, and picks its connections according to a unique topology control algorithm that is available at every node. Given that each node knows only the indices (unique identification numbers) of its one and two-hop neighbors, we identify an algorithm that preserves connectivity and can operate without the need of any synchronization among nodes. Moreover, the algorithm results in a sparse graph with at most 5n edges and a maximum node degree of 10. Existing algorithms with the same promises further require neighbor distance and/or direction information at each node. We also evaluate the performance of our algorithm for random networks. In this case, our algorithm provides an asymptotically connected network with n(1+o(1)) edges with a degree less than or equal to 6 for 1-o(1) fraction of the nodes. We also introduce another asynchronous connectivity-preserving algorithm that can provide an upper bound as well as a lower bound on node degrees.

Multi-tier networks have many applications in different fields. We define a novel two-tier quantizer that can be applied to different node deployment problems including the energy conservation in two-tier wireless sensor networks consisting of N access points (APs) and M fusion centers (FCs). We aim at finding an optimal deployment of APs and FCs to minimize the average weighted total, or Lagrangian, of sensor and AP powers. For one FC, M = 1, we show that the optimal deployment of APs is simply a linear transformation of the optimal N-level quantizer for density f, and the sole FC should be located at the geometric centroid of the sensing field. We also provide the exact expression of the AP-Sensor power function and prove its convexity. For more than one FC, M > 1, we provide a necessary condition for the optimal deployment. Furthermore, to numerically optimize the AP and FC deployment, we propose three Lloyd-like algorithms and analyze their convergence. Simulation results show that our algorithms outperform the existing algorithms.

Optimal deployment and movement of multiple unmanned aerial vehicles (UAVs) is studied. The scenarios of variable data rate with fixed transmission power, and variable transmission power with fixed data rate are considered. First, the optimal deployment of UAVs is studied for the static case of a fixed ground terminal (GT) density. Using high resolution quantization theory, the corresponding best achievable performance (average data rate or transmission power) is determined in the asymptotic regime of a large number of UAVs. Next, the dynamic case where the GT density is allowed to vary periodically through time is considered. For one-dimensional networks, an accurate formula for the total amount of UAV movement that guarantees the best time-averaged performance is determined. In general, the tradeoff between the total UAV movement and the achievable performance is obtained through a Lagrangian approach. A corresponding trajectory optimization algorithm is introduced and shown to guarantee a convergent Lagrangian. Numerical simulations are also carried out to confirm the analytical findings.

We introduce and investigate the opportunities of multi-antenna communication schemes whose training and feedback stages are interleaved and mutually interacting. Specifically, unlike the traditional schemes, where the transmitter first trains all of its antennas at once and then receives a single feedback message, we consider a scenario, where the transmitter instead trains its antennas one by one and receives feedback information immediately after training each one of its antennas. The feedback message may ask the transmitter to train another antenna; or, it may terminate the feedback/training phase and provide the quantized codeword (e.g., a beamforming vector) to be utilized for data transmission. As a specific application, we consider a multiple-input single-output system with t transmit antennas, a short-term power constraint P , and target data rate p. We show that for any t, the same outage probability as a system with perfect transmitter and receiver channel state information can be achieved with a feedback rate of R1bits per channel state and via training R2transmit antennas on average, where R1and R2are independent oft, and depend only on p and P . In addition, we design variable-rate quantizers for channel coefficients to further minimize the feedback rate of our scheme.

We consider the single-cell multi-user multiple-input multiple-output uplink with several single antenna transmitters/users and one base station (BS) with N antennas in the N → ∞ regime. The BS antennas are evenly distributed to n admissible locations throughout the cell. First, we show that a reliable (per-user) rate of O(log n) is achievable through the optimal locational optimization of BS antennas. We also prove that an O(log n) rate is the best possible. Therefore, in contrast to a centralized or circular deployment, where the achievable rate is at most a constant, the rate with a general deployment can grow logarithmically with n, resulting in a certain form of “macro-multiplexing gain.” Second, using tools from high-resolution quantization theory, we present an accurate heuristic formula for the best achievable rate given any n and any user density function. According to our formula, the dependence of the optimal rate on the user density function f is curiously only through the differential entropy of f. In fact, the optimal rate decreases linearly with the differential entropy, and the worst-case scenario is a uniform user density. We also describe a modified gradient ascent procedure for the numerical optimization of antenna locations. Simulations confirm our analytical findings.

We study a two-tiered wireless sensor network (WSN) consisting of N access points (APs) and M base stations (BSs). The sensing data, which is distributed on the sensing field according to a density function f, is first transmitted to the APs and then forwarded to the BSs. Our goal is to find an optimal deployment of APs and BSs to minimize the average weighted total, or Lagrangian, of sensor and AP powers. For M = 1, we show that the optimal deployment of APs is simply a linear transformation of the optimal N-level quantizer for density f, and the sole BS should be located at the geometric centroid of the sensing field. Also, for a one-dimensional network and uniform f, we determine the optimal deployment of APs and BSs for any N and M. Moreover, to numerically optimize node deployment for general scenarios, we propose one-and two-tiered Lloyd algorithms and analyze their convergence properties. Simulation results show that, when compared to random deployment, our algorithms can save up to 79% of the power on average.

We consider ad-hoc networks consisting of n wireless nodes that are located on the plane. Any two given nodes are called neighbors if they are located within a certain distance (communication range) from one another. A given node can be directly connected to any one of its neighbors and picks its connections according to a unique topology control algorithm that is available at every node. Given that each node knows only the indices (unique identification numbers) of its one- and two-hop neighbors, we identify an algorithm that preserves connectivity and can operate without the need of any synchronization among nodes. Moreover, the algorithm results in a sparse graph with at most 5n edges and a maximum node degree of 10. Existing algorithms with the same promises further require neighbor distance and/or direction information at each node. We also evaluate the performance of our algorithm for random networks. In this case, our algorithm provides an asymptotically connected network with n(1 + 0(1)) edges with a degree less than or equal to 6 for 1-0(1) fraction of the nodes. Numerical results confirm our analytical findings.

We consider a slowly fading multicast channel with one T-antenna transmitter and K single-antenna receivers with the goal of minimizing channel outage probability using quantized beamforming. Our focus is on a distributed limited feedback scenario where each receiver can only quantize and send feedback information regarding its own receiving channels. A classical result in point-to-point quantized beamforming is that a necessary and sufficient condition for full diversity is to have ⌈log2T⌉ bits from the receiver with an appropriate quantizer. We first generalize this result to multicast beamforming systems and show that a necessary and sufficient condition to achieve full diversity for all receivers is to have ⌈log2T⌉ bits from each receiver with an appropriate quantizer. Achievable diversity gains with a long-term power constraint are also discussed. Moreover, for a two-receiver system and with R feedback bits per receiver, we show that the outage performance with quantized R beamforming is within O(2-R/32T2)dBs to the performance with full channel state information at the transmitter (CSIT). This constitutes, in the context of multicast channels, the first example of a distributed limited feedback scheme whose performance can provably approach the performance with full CSIT. Numerical simulations confirm our analytical findings.

In quantization theory, one typically works with a unique distortion function (e.g. the squared-error distortion function) that quantifies the cost of quantizing a given source sample to any given reproduction point of the quantizer. Many applications, however, induce quantization problems where different distortion functions should be associated with different reproduction points. In this paper, we consider the case where the distortion of a given reproduction point is the squared distance to the source sample weighted by a factor that varies from one reproduction point to another. For a uniform distribution of source samples, we determine the corresponding optimal scalar quantizers and their distortions. We also find upper and lower bounds on the distortion of optimal vector quantizers. For non-uniform distributions, we provide a high resolution analysis of the minimum possible distortion. As a byproduct of our analysis, we show that for certain distributions of weights, a tessellation of non-congruent quantization cells can outperform tessellations of congruent polytopes. This suggests that Gersho's conjecture cannot be extended to the case of squared-error distortion functions with weighted reproduction points.

We consider a slow-fading multicast channel with one T-antenna transmitter and K single-antenna receivers with the goal of minimizing channel outage probability using quantized beamforming. Our focus is on a distributed limited feedback scenario where each receiver can only quantize and send feedback information regarding its own receiving channels. A classical result in point-to-point quantized beamforming is that a necessary and sufficient condition for full diversity is to have ⌈log2T⌉ bits from the receiver. We first generalize this result to multicast beamforming systems and show that a necessary and sufficient condition to achieve full diversity for all receivers is to have ⌈log2T⌉ bits from each receiver. Also, for a two-receiver system and with R feedback bits per receiver, we show that the outage performance with quantized beamforming is within O(2−R/32T2)dBs of the performance with full channel state information at the transmitter (CSIT). This constitutes, in the context of multicast channels, the first example of a distributed limited feedback scheme whose performance can provably approach the performance with full CSIT.

We consider a fixed data rate slow-fading MIMO channel with a long-term power constraint P at the transmitter. A relevant performance limit is the delay-limited capacity, which is the largest data rate at which the outage probability is zero. It is well known that if both the transmitter and the receiver have full channel state information (CSI) and if either of them has multiple antennas, the delay-limited capacity is non-zero and grows logarithmically with P. Achieving even a positive delay-limited capacity, however, becomes a difficult task when the CSI at the transmitter (CSIT) is imperfect. In this context, the standard partial CSIT model where the transmitter has a fixed finite bit of quantized CSI feedback for each channel state results in zero delay-limited capacity. We show that by using a variable-length feedback scheme that utilizes a different number of feedback bits for different channel states, a non-zero delaylimited capacity can be achieved if the feedback rate is greater than 1 bit per channel state. Moreover, we show that the delaylimited capacity loss due to finite-rate feedback decays at least inverse linearly with respect to the feedback rate. We also discuss the applications to ergodic MIMO channels.

We study the channel quantization problem for amplify-and-forward (AF) relay networks and our target is to design a quantizer to minimize the outage probability. It is priorly known that any fixed-length quantizer with a finite-cardinality codebook cannot attain the same minimum outage probability as the case where all nodes in the AF relay networks have access to perfect channel state information (CSI). We propose variable-length quantizers with random infinite-cardinality codebooks for the sum and individual power constraints. We provide theoretical proofs and numerical simulations to validate that the proposed quantizers can achieve the full-CSI outage probabilities with finite average feedback rates.

We study the connectivity of wireless networks consisting of n nodes that are located independently and uniformly at random on the unit square. Our focus is on an orthogonal multiple access scenario where there are M orthogonal resources (e.g. time slots and/or frequency bands) that are to be assigned to each connection in the network. Correspondingly, we consider a disk-interference model where two nodes can be connected over resource m if (i) they are within communication range R, and (ii) no other node within distance R to either one of the two nodes uses the resource m. In such a scenario, it is known that if one is allowed to optimally choose (depending on the node locations) the node connections and the associated resources, the conditions R2∈ Θ(logn/n) and M ∈ Θ(log n) are necessary and sufficient to ensure asymptotically almost sure connectivity as n → ∞. We propose a distributed resource allocation scheme where each node, unaware of its (and other nodes') geographical location(s), decides on its connections and the associated resources by communicating with its neighboring nodes only. Our scheme provides a connected network under the best-possible conditions R2∈ O(log n/n) and M ∈ O(logn).

We study the channel quantization problem for amplify- and-forward (AF) relay networks with a sum power constraint for the relay nodes. Our target is to design a quantizer to minimize the outage probability. It is priorly known that any fixed-length quantizer with a finite- cardinality codebook cannot attain the same minimum outage probability as the case where all nodes in the AF relay networks have access to perfect channel state information (CSI). We propose a variable- length quantizer with a random infinite- cardinality codebook, and we prove that the proposed quantizer is able to achieve the full-CSI outage probability with a finite average feedback rate. Numerical simulations validate our theoretical analysis.

We introduce and investigate the opportunities of multi-antenna communication schemes whose training and feedback stages are interleaved and mutually interacting. Specifically, unlike the traditional schemes where the transmitter first trains all of its antennas at once and then receives a single feedback message, we consider a scenario where the transmitter instead trains its antennas one by one and receives feedback information immediately after training each one of its antennas. The feedback message may ask the transmitter to train another antenna; or, it may terminate the feedback/training phase and provide the quantized codeword (e.g., a beamforming vector) to be utilized for data transmission. As a specific application, we consider a multiple-input single-output system with t transmitter antennas, a short-term power constraint P, and target data rate ρ. We show that for any t, the same outage probability as a system with perfect transmitter and receiver channel state information can be achieved with a feedback rate of R1bits per channel state and via training R2transmitter antennas on average, where R1and R2are independent of t, and depend only on ρ and P.

We introduce cooperative quantizers for two-user interference channels where interference signals are treated as noise. Compared with the conventional quantizers where each receiver quantizes its own channel independently, the proposed cooperative quantizers allow multiple rounds of feedback communication in the form of conferencing between receivers. For both time-sharing and concurrent transmission strategies, we propose different cooperative quantizers to achieve the full-channel-state-information (full-CSI) network outage probability of sum rate and the full-CSI network outage probability of minimum rate, respectively. Our proposed quantizers only require finite average feedback rates, whereas the conventional quantizers require infinite rate to achieve the full-CSI performance. For the minimum rate, we also design cooperative quantizers for a joint time-sharing and concurrent transmission strategy that can approach the previously established optimal network outage probability with a negligible gap. Numerical simulations confirm that our cooperative quantizers based on conferencing outperform the conventional quantizers.

We investigate the channel quantization problem for two-user multicast networks where the transmitter is equipped with multiple antennas and either receiver is equipped with only a single antenna. Our goal is to design a global quantizer to minimize the outage probability. It is known that any fixed-length quantizer with a finite-cardinality codebook cannot obtain the same minimum outage probability as the case where all nodes in the network know perfect channel state information (CSI). To achieve the minimum outage probability, we propose a variable-length global quantizer that knows perfect CSI and sends quantized CSI to the transmitter and receivers. With a random infinite-cardinality codebook, we prove that the proposed quantizer is able to achieve the minimum outage probability with a low average feedback rate. We also extend the proposed quantizer to the multicast networks with more than two users. Numerical simulations validate our theoretical analysis.

We introduce conferencing-based distributed channel quantizers for two-user interference networks where interference signals are treated as noise. Compared with the conventional distributed quantizers where each receiver quantizes its own channel independently, the proposed quantizers allow multiple rounds of feedback communication in the form of conferencing between receivers. We take the network outage probabilities of sum rate and minimum rate as performance measures and consider quantizer design in the transmission strategies of time sharing and interference transmission. First, we propose distributed quantizers that achieve the optimal network outage probability of sum rate for both time sharing and interference transmission strategies with an average feedback rate of only two bits per channel state. Then, for the time sharing strategy, we propose a distributed quantizer that achieves the optimal network outage probability of minimum rate with finite average feedback rate; conventional quantizers require infinite rate to achieve the same performance. For the interference transmission strategy, a distributed quantizer that can approach the optimal network outage probability of minimum rate closely is also proposed. Numerical simulations confirm that our distributed quantizers based on conferencing outperform the conventional ones.

We investigate the channel quantization problem for two-user multicast networks where the transmitter is equipped with multiple antennas and either receiver is equipped with only a single antenna. Our goal is to design a global quantizer to minimize the outage probability. It is known that any fixed-length quantizer with a finite-cardinality codebook cannot achieve the same minimum outage probability as the case where all nodes in the network know perfect channel state information (CSI). To achieve the minimum outage probability, we propose a variable-length global quantizer that knows perfect CSI and sends quantized CSI to the transmitter and receivers. With a random infinite-cardinality codebook, we prove that the proposed quantizer is able to achieve the minimum outage probability with a low average feedback rate. Numerical simulations also validate our theoretical analysis.

We consider a fixed data rate slow-fading MIMO channel with a long-term power constraint P at the transmitter. A relevant performance limit is the delay-limited capacity, which is the largest data rate at which the outage probability is zero. It is well-known that if both the transmitter and the receiver have full channel state information (CSI) and if either of them has multiple antennas, the delay-limited capacity is non-zero and grows logarithmically with P. Achieving even a positive delay-limited capacity however becomes a difficult task when the CSI at the transmitter (CSIT) is imperfect. In this context, the standard partial CSIT model where the transmitter has a fixed finite bits of quantized CSI feedback for each channel state results in zero delay-limited capacity. We show that by using a variable-length feedback scheme that utilizes different number of feedback bits for different channel states, a non-zero delay-limited capacity can be achieved if the feedback rate is greater than 1 bit per channel state. Moreover, we show that the delay-limited capacity loss due to finite-rate feedback decays at least inverse linearly with respect to the feedback rate.

We study a multiple-input single-output fading channel, where we would like to minimize the channel outage probability or symbol error rate (SER) by employing beamforming via quantized channel state information at the transmitter (CSIT). We consider a variable-length limited feedback scheme where the quantized CSIT is acquired through feedback binary codewords of possibly different lengths. We design and analyze the performance of the associated variable-length quantizers (VLQs) and compare their performance with the previously studied fixed-length quantizers (FLQs). For the outage probability performance measure, we construct VLQs that can achieve the full-CSIT performance with finite rate. Moreover, as the signal-to-noise ratio P tends to infinity, we show that VLQs can achieve the full-CSIT outage probability performance with asymptotically zero feedback rate. For the SER performance measure, we show that while the SER with full-CSIT is not achievable at any finite feedback rate, the diversity and array gains with full-CSIT can be achieved using VLQs with asymptotically zero feedback rate as P → ∞. Our results show that VLQs can significantly improve upon the traditional FLQs that require infinite feedback rate to achieve the outage probability or the diversity and array gains with full-CSIT.

We identify a practical vector quantizer design problem where any fixed-length quantizer (FLQ) yields non-zero distortion at any finite rate, while there is a variable-length quantizer (VLQ) that can achieve zero distortion with arbitrarily low rate. The problem arises in a t × 1 multiple-antenna fading channel where we would like to minimize the channel outage probability by employing beam forming via quantized channel state information at the transmitter (CSIT). It is well-known that in such a scenario, finite-rate FLQs cannot achieve the full-CSIT (zero distortion) outage performance. We construct VLQs that can achieve the full-CSIT performance with finite rate. In particular, with P denoting the power constraint of the transmitter, we show that the necessary and sufficient VLQ rate that guarantees the full-CSIT performance is Θ(1/P). We also discuss several extensions (e.g. to precoding) of this result.

We consider a t × 1 multiple-antenna fading channel with quantized channel state information at the transmitter (CSIT). Our goal is to maximize the diversity and array gains that are associated with the symbol error rate (SER) performance of the system. It is well-known that for both beamforming and precoding strategies, finite-rate fixed-length quantizers (FLQs) cannot achieve the full-CSIT diversity and array gains. In this work, for any function f(P) ϵ ω(1), we construct variable-length quantizers (VLQs) that can achieve these full-CSIT gains with rates 1 + (/(P) log P)/P and 1 + f(P)/Ptfor the beamforming and precoding strategies, respectively, where P is the power constraint of the transmitter. We also show that these rates are the best possible up to o(l) multipliers in their P-dependent terms. In particular, although the full-CSIT SER is not achievable at any (even infinite) feedback rate, the full-CSIT diversity and array gains can be achieved with a feedback rate of 1 bit per channel state asymptotically as P → ∞.

We determine necessary conditions on the structure of symbol error rate (SER) optimal compact quantizer codebooks for limited feedback beamforming in wireless networks with one transmitter-receiver pair andRparallel amplify-and-forward relays. We call a codebook “small” if its cardinality is less thanR, and “large” otherwise. A “d-codebook” depends on the power constraints and can be optimized accordingly, while an “i-codebook” remains fixed. It was previously shown that any i-codebook that contains the single-relay selection (SRS) codebook achieves the full-diversity order,R. We prove the following: Every full-diversity i-codebook contains the SRS codebook, and thus is necessarily large. In general, as the power constraints grow to infinity, the limit of an SER-optimal large d-codebook contains an SRS codebook, provided that it exists. For small codebooks, the maximal diversity is equal to the codebook cardinality. Every diversity-optimal small i-codebook is an orthogonal multiple-relay selection (OMRS) codebook. Moreover, the limit of an SER-optimal small d-codebook is an OMRS codebook. We observe that SRS is nothing but a special case of OMRS for codebooks with cardinality equal to R. As a result, we call OMRS as "the universal necessary condition" for codebook optimality. Finally, we confirm our analytical findings through simulations.

We study fixed data rate communication schemes for wireless relay-interference networks with any number of transmitters, relays, and receivers. The transmitters and the relays have individual short-term power constraints. We analyze both amplify-and-forward (AF) and decode-and-forward (DF) relaying strategies with a two channel use quantized network beamforming protocol. We design the quantizer of the channel state information to minimize the probability that at least one receiver incorrectly decodes its desired symbol(s). Correspondingly, we introduce a generalized diversity measure that encapsulates the conventional one as the first-order diversity. Additionally, it incorporates the second-order diversity, which is concerned with the transmitter power dependent logarithmic terms that appear in the error rate expression. We first show that for AF relays, the maximal achievable diversity in the presence of interference is strictly less than the transmit diversity bound in terms of the second-order diversity. We then prove that it is possible to achieve the transmit diversity bound using DF relays as if there is no interference and as if coding over an arbitrary number of channel uses is allowed. Relay selection provides the best possible diversity gain for both relaying strategies. Finally, we show that all the aforementioned diversity gains can be achieved using distributed decision making with asymptotically zero feedback rate per receiver. Such a performance is made possible by a special distributed quantizer design method we have called localization .

We determine necessary conditions on the structure of symbol error rate optimal quantizers for limited feedback beamforming in wireless networks with one transmitter-receiver pair and R parallel amplify-and-forward relays. It was previously shown that any quantizer codebook that contains the single-relay selection (SRS) codebook achieves full-diversity. We prove the converse: Every full-diversity codebook contains the SRS codebook. We also determine the structure and the achievable diversity of codebooks with cardinality less than R.

We introduce a systematic distributed quantizer design method, called {\it{localization}}, in which, out of an existing centralized (global) quantizer, one synthesizes the distributed (local) quantizer using high-rate scalar quantization combined with entropy coding. The general localization procedure is presented, along with a practical application to a quantized beamforming problem for multiple-input multiple-output broadcast channels. For our particular application, not only localization provides high performance distributed quantizers with very low feedback rates, but also reveals an interesting property of finite rate feedback schemes that might be of theoretical interest: For single-user multiple-input single-output systems, one can achieve the performance of almost any quantized beamforming scheme with an arbitrarily low feedback rate, when the transmitter power is sufficiently large.

This paper is on quantized beamforming in wireless amplify-and-forward relay interference networks with multiple transmitter-receiver pairs. We design the quantizer of the feedback information specifically to optimize the union bound on the bit error rate performance. Two different quantization schemes are considered. First, using a global quantizer structure, we analytically show that a simple feedback scheme based on relay selection can achieve full diversity. Then, we design a local quantization scheme with distributed quantizer encoders, one at each receiver. We show that, with only a few feedback bits, high diversity gains can be obtained with the local quantizer structure as well. Simulations are also provided, confirming our analytical results. We observe that our designs guarantee an equal high diversity gain for each transmitter-receiver pair.

This paper is on quantized beamforming in wireless amplify-and-forward (AF) relay networks. We use the generalized Lloyd algorithm (GLA) to design the quantizer of the feedback information and specifically to optimize the bit error rate (BER) performance of the system. Achievable bounds for different performance measures are derived. First, we analytically show that a simple feedback scheme based on relay selection can achieve full diversity. Unlike the previous diversity analysis on the relay selection scheme, our analysis is not aided by any approximations or modified forwarding schemes. Then, for highrate feedback, we find an upper bound on the average signalto- noise ratio (SNR) loss. Using this result, we demonstrate that both the average SNR loss and the capacity loss decay at least exponentially with the number of feedback bits. In addition, we provide approximate upper and lower bounds on the BER, which can be calculated numerically.We observe that our designs can achieve both full diversity as well as high array gain with only a moderate number of feedback bits. Simulations also show that our approximate BER is a reliable estimation on the actual BER. We also generalize our analytical results to asynchronous networks, where perfect carrier level synchronization is not available among the relays.