Random graph generation is an important tool for studying large complex networks. Despite abundance of random graph models, constructing models with application-driven constraints is poorly understood. In order to advance state-of-the-art in this are
a, we focus on random graphs without short cycles as a stylized family of graphs, and propose the RandGraph algorithm for randomly generating them. For any constant k, when m=O(n^{1+1/[2k(k+3)]}), RandGraph generates an asymptotically uniform random graph with n vertices, m edges, and no cycle of length at most k using O(n^2m) operations. We also characterize the approximation error for finite values of n. To the best of our knowledge, this is the first polynomial-time algorithm for the problem. RandGraph works by sequentially adding $m$ edges to an empty graph with n vertices. Recently, such sequential algorithms have been successful for random sampling problems. Our main contributions to this line of research includes introducing a new approach for sequentially approximating edge-specific probabilities at each step of the algorithm, and providing a new method for analyzing such algorithms.
Sparse Code Division Multiple Access (CDMA), a variation on the standard CDMA method in which the spreading (signature) matrix contains only a relatively small number of non-zero elements, is presented and analysed using methods of statistical physic
s. The analysis provides results on the performance of maximum likelihood decoding for sparse spreading codes in the large system limit. We present results for both cases of regular and irregular spreading matrices for the binary additive white Gaussian noise channel (BIAWGN) with a comparison to the canonical (dense) random spreading code.
A binary 1-error-correcting code can always be embedded in a 1-perfect code of some larger length
We study zero-forcing detection (ZF) for multiple-input/multiple-output (MIMO) spatial multiplexing under transmit-correlated Rician fading for an N_R X N_T channel matrix with rank-1 line-of-sight (LoS) component. By using matrix transformations and
multivariate statistics, our exact analysis yields the signal-to-noise ratio moment generating function (m.g.f.) as an infinite series of gamma distribution m.g.f.s and analogous series for ZF performance measures, e.g., outage probability and ergodic capacity. However, their numerical convergence is inherently problematic with increasing Rician K-factor, N_R , and N_T. We circumvent this limitation as follows. First, we derive differential equations satisfied by the performance measures with a novel automated approach employing a computer-algebra tool which implements Groebner basis computation and creative telescoping. These differential equations are then solved with the holonomic gradient method (HGM) from initial conditions computed with the infinite series. We demonstrate that HGM yields more reliable performance evaluation than by infinite series alone and more expeditious than by simulation, for realistic values of K , and even for N_R and N_T relevant to large MIMO systems. We envision extending the proposed approaches for exact analysis and reliable evaluation to more general Rician fading and other transceiver methods.
The mutual information between two jointly distributed random variables $X$ and $Y$ is a functional of the joint distribution $P_{XY},$ which is sometimes difficult to handle or estimate. A coarser description of the statistical behavior of $(X,Y)$ i
s given by the marginal distributions $P_X, P_Y$ and the adjacency relation induced by the joint distribution, where $x$ and $y$ are adjacent if $P(x,y)>0$. We derive a lower bound on the mutual information in terms of these entities. The bound is obtained by viewing the channel from $X$ to $Y$ as a probability distribution on a set of possible actions, where an action determines the output for any possible input, and is independently drawn. We also provide an alternative proof based on convex optimization, that yields a generally tighter bound. Finally, we derive an upper bound on the mutual information in terms of adjacency events between the action and the pair $(X,Y)$, where in this case an action $a$ and a pair $(x,y)$ are adjacent if $y=a(x)$. As an example, we apply our bounds to the binary deletion channel and show that for the special case of an i.i.d. input distribution and a range of deletion probabilities, our lower and upper bounds both outperform the best known bounds for the mutual information.
An uplink system with a single antenna transmitter and a single receiver with a large number of antennas is considered. We propose an energy-detection-based single-shot noncoherent communication scheme which does not use the instantaneous channel sta
te information (CSI), but rather only the knowledge of the channel statistics. The suggested system uses a transmitter that modulates information on the power of the symbols, and a receiver which measures only the average energy across the antennas. We propose constellation designs which are asymptotically optimal with respect to symbol error rate (SER) with an increasing number of antennas, for any finite signal to noise ratio (SNR) at the receiver, under different assumptions on the availability of CSI statistics (exact channel fading distribution or the first few moments of the channel fading distribution). We also consider the case of imperfect knowledge of the channel statistics and describe in detail the case when there is a bounded uncertainty on the moments of the fading distribution. We present numerical results on the SER performance achieved by these designs in typical scenarios and find that they may outperform existing noncoherent constellations, e.g., conventional Amplitude Shift Keying (ASK), and pilot-based schemes, e.g., Pulse Amplitude Modulation (PAM). We also observe that an optimized constellation for a specific channel distribution makes it very sensitive to uncertainties in the channel statistics. In particular, constellation designs based on optimistic channel conditions could lead to significant performance degradation in terms of the achieved symbol error rates.
In massive multiple-input multiple-output (MIMO) systems, it may not be power efficient to have a high-resolution analog-to-digital converter (ADC) for each antenna element. In this paper, a near maximum likelihood (nML) detector for uplink multiuser
massive MIMO systems is proposed where each antenna is connected to a pair of one-bit ADCs, i.e., one for each real and imaginary component of the baseband signal. The exhaustive search over all the possible transmitted vectors required in the original maximum likelihood (ML) detection problem is relaxed to formulate an ML estimation problem. Then, the ML estimation problem is converted into a convex optimization problem which can be efficiently solved. Using the solution, the base station can perform simple symbol-by-symbol detection for the transmitted signals from multiple users. To further improve detection performance, we also develop a two-stage nML detector that exploits the structures of both the original ML and the proposed (one-stage) nML detectors. Numerical results show that the proposed nML detectors are efficient enough to simultaneously support multiple uplink users adopting higher-order constellations, e.g., 16 quadrature amplitude modulation. Since our detectors exploit the channel state information as part of the detection, an ML channel estimation technique with one-bit ADCs that shares the same structure with our proposed nML detector is also developed. The proposed detectors and channel estimator provide a complete low power solution for the uplink of a massive MIMO system.
Achieving long battery lives or even self sustainability has been a long standing challenge for designing mobile devices. This paper presents a novel solution that seamlessly integrates two technologies, mobile cloud computing and microwave power tra
nsfer (MPT), to enable computation in passive low-complexity devices such as sensors and wearable computing devices. Specifically, considering a single-user system, a base station (BS) either transfers power to or offloads computation from a mobile to the cloud; the mobile uses harvested energy to compute given data either locally or by offloading. A framework for energy efficient computing is proposed that comprises a set of policies for controlling CPU cycles for the mode of local computing, time division between MPT and offloading for the other mode of offloading, and mode selection. Given the CPU-cycle statistics information and channel state information (CSI), the policies aim at maximizing the probability of successfully computing given data, called computing probability, under the energy harvesting and deadline constraints. The policy optimization is translated into the equivalent problems of minimizing the mobile energy consumption for local computing and maximizing the mobile energy savings for offloading which are solved using convex optimization theory. The structures of the resultant policies are characterized in closed form. Furthermore, given non-causal CSI, the said analytical framework is further developed to support computation load allocation over multiple channel realizations, which further increases computing probability. Last, simulation demonstrates the feasibility of wirelessly powered mobile cloud computing and the gain of its optimal control.
Energy harvesting multi-hop networks allow for perpetual operation of low cost, limited range wireless devices. Compared with their battery operated counterparts, the coupling of energy and data causality constraints with half duplex relay operation
makes it challenging to operate such networks. In this paper, a throughput maximization problem for energy harvesting two-hop networks with decode-and-forward half-duplex relays is investigated. For a system with two parallel relays, various combinations of the following four transmission modes are considered: Broadcast from the source, multi-access from the relays, and successive relaying phases I and II. Optimal transmission policies for one and two parallel relays are studied under the assumption of non-causal knowledge of energy arrivals and finite size relay data buffers. The problem is formulated using a convex optimization framework, which allows for efficient numerical solutions and helps identify important properties of optimal policies. Numerical results are presented to provide throughput comparisons and to investigate the impact of multiple relays, size of relay data buffers, transmission modes, and energy harvesting on the throughput.
This paper addresses the development of analytical tools for the computation of the moments of random Gram matrices with one side correlation. Such a question is mainly driven by applications in signal processing and wireless communications wherein s
uch matrices naturally arise. In particular, we derive closed-form expressions for the inverse moments and show that the obtained results can help approximate several performance metrics such as the average estimation error corresponding to the Best Linear Unbiased Estimator (BLUE) and the Linear Minimum Mean Square Error LMMSE or also other loss functions used to measure the accuracy of covariance matrix estimates.
