Rack-aware storage systems organize the storage nodes in racks such that the cross-rack communication cost is much more expensive than the intra-rack communication cost. In this paper, we primarily investigate the cross-rack update bandwidth defined as the average amount of symbols transferred across different racks during an update process of one single node. It is critical to design erasure codes that minimize the cross-rack update bandwidth. Our main contributions are as follows. First, we establish the model of cross-rack update bandwidth of irregular array codes over rack-aware storage systems. Second, we derive the tight lower bound on cross-rack update bandwidth, and define minimum cross-rack update bandwidth (MCUB) codes as the irregular array codes that can achieve our tight lower bound. Third, we derive the tight lower bound on redundancy defined as the total number of parity symbols for MCUB codes, and define minimum redundancy MCUB (MR-MCUB) codes as the MCUB codes that can achieve the redundancy lower bound. Fourth, we present explicit constructions of MR-MCUB codes that achieve both the minimum cross-rack update bandwidth and the minimum redundancy, which means that the two lower bounds are tight. Last, we define intra-rack update bandwidth as the average amount of symbols incurred within one rack in an update process, and derive the lower bound of intra-rack update bandwidth of MCUB codes. Moreover, we show that our MCUB codes constructions can also achieve the lower bound of intra-rack update bandwidth.

Based on a recently proposed fast Fourier transform by Lin, Chung, and Han, this paper presents two fast erasure decoding algorithms for Reed–Solomon (RS) codes over binary extension fields of lengthNand dimensionK. The first algorithm applies to low-rate RS codes (i.e.,K/N≤ 0:5) and achieves a complexity ofO(N log K). The second algorithm applies to high-rate RS codes (i.e.,K/N≥ 0:5) and achieves a complexity ofO(N log(N–K)). Compared to recent state-of-the-art algorithms, both proposed algorithms achieve the best complexity, resulting in significant throughput improvements in Single Instruction Multiple Data (SIMD) based simulations. Besides yielding new fast algorithms for RS codes, this paper also presents a new interpolation formula, as well as related results, which may be of independent interest.

Analog error-correcting codes (Analog ECCs) can effectively detect and correct computational errors generated during vector-matrix multiplication in the real domain. Recently, several related classes of single-error and multiple-error Analog ECCs have been proposed. However, most existing constructions encounter limitations such as high storage overhead, limited code length range, and high decoding complexity, which diminish their practical applicability. In this paper, we first propose a new framework for generating MDS Analog ECCs with arbitrary code length for single-error detection and correction. Utilizing this framework, we propose a new decoding algorithm for our codes with lower decoding complexity than the existing decoding method. We divide decoding algorithm into two parts: syndrome calculation and error correction. We show that the error correction complexity of our method which is explicit is$O(\log (n))$, while the error correction complexity of existing decoding method based on geometric features which is not explicit is at least$O(n)$, here$n$represents the code length. Simulation experiments demonstrate that our decoding algorithm maintains a high error correction success rate for correcting a single outlying error, even when the error scale is significantly below our established theoretical threshold.

Piggybacking codes have garnered extensive research attention for their potential to reduce the repair bandwidth of traditional maximum distance separable (MDS) codes. The existing piggybacking codes are only considered for improving the repair performance for single-node erasure. In this paper, we propose a new piggybacking code construction with a small sub-packetization level. Through carefully designed piggyback functions, our code can effectively reduce the repair bandwidth for both single-node and double-node erasures. Specifically, we show that when$r$is large and$r \ll k$(here,$r$represents the number of parity nodes and$k$represents the number of data nodes), our code can achieve a reduction in the average repair bandwidth for double-node erasure by approximately 33 %, and for single-node erasure by around 50 %, when compared to the traditional MDS property-based repair method. To our knowledge, this is the first exploration for efficient repair of multi-node erasure under the piggybacking framework.

Matrix multiplication over the real field constitutes a foundational operation in the training of deep learning models, serving as a computational cornerstone for both forward and backward propagation processes. However, the presence of silent data corruption (SDC) in large-scale distributed training environments poses a significant threat to model convergence and predictive accuracy, particularly when such errors manifest during matrix multiplication. Due to their transient and non-intrusive nature, these errors often evade detection, allowing them to propagate and accumulate over time, ultimately leading to substantial degradation in model performance. In this paper, we introduce a novel error-correcting coding framework specifically tailored for matrix multiplication operations. Our proposed framework is designed to detect and correct multiple computational errors that may arise during the execution of matrix products. By leveraging a grid-based structural encoding scheme, our approach enhances error localization and correction capabilities across all participating matrices, thereby significantly improving the fault tolerance of the computation. Experimental results demonstrate that our method achieves deterministic correction of up to two erroneous symbols distributed across three matrices with 100% reliability, while incurring only a 24% overhead in computational time on GPU architectures. Furthermore, we provide a rigorous theoretical analysis of the error-correction properties inherent to our coding scheme, establishing its correctness and robustness under well-defined fault models.

Although applications involving long-context inputs are crucial for the effective utilization of large language models (LLMs), they also result in increased computational costs and reduced performance. To address this challenge, we propose an efficient, training-free prompt compression method that retains key information within compressed prompts. We identify specific attention heads in transformer-based LLMs, which we designate as evaluator heads, that are capable of selecting tokens in long inputs that are most significant for inference. Building on this discovery, we develop EHPC, an Evaluator Head-based Prompt Compression method, which enables LLMs to rapidly "skim through'' input prompts by leveraging only the first few layers with evaluator heads during the pre-filling stage, subsequently passing only the important tokens to the model for inference. EHPC achieves state-of-the-art results across two mainstream benchmarks: prompt compression and long-context inference acceleration. Consequently, it effectively improves performance with the reduced costs associated with commercial API calls compared to prompt compressing methods. We further demonstrate that EHPC attains competitive results compared to key-value cache-based acceleration methods, thereby highlighting its potential to enhance the efficiency of LLMs for long-context tasks.

The ultra-dense low-earth orbit (LEO) satellite networks (ULSNs) have become an important component of next-generation (6G) wireless networks, offering large-scale coverage and high-capacity service. Unlike traditional terrestrial network backbones deployed in closed, protected environments, satellite networks are exposed to highly dynamic environments, where space environment interference can severely affect channel conditions. This paper addresses the impact of sun outages, one of the most significant spatial interference factors, on satellite communication and proposes an adaptive coding and modulation scheme that dynamically adjusts the modulation and coding schemes (MCSs) based on real-time channel conditions to enhance the performance and communication quality of ULSNs. First, we model the channel environment of satellite-terrestrial microwave and inter-satellite laser links under sun outage interferences in ULSNs, which involves sun outage occurrence prediction and their interference quantification. Subsequently, to implement the ACM scheme, we use the seasonal autoregressive integrated moving average (SARIMA) algorithm combined with the bidirectional long short-term memory (BiLSTM) algorithm for time-series prediction of the channel state. Based on this, we apply the knowledge distillation-assisted proximal policy optimization (KD-PPO) algorithm to select the appropriate MCS. Simulation results show that by calculating the sun outage duration and the resulting interference, as well as predicting the channel state, the proposed KD-PPO algorithm can minimize the bit error rate (BER) and maximize the spectrum utilization (SU) in ULSNs.

Maximum distance separable (MDS) codes in distributed storage systems provide the optimal tradeoff between fault tolerance and storage overhead. As a kind of MDS codes, minimum storage regenerating (MSR) codes have attracted a lot of attention since they are also optimal in terms of repair bandwidth. However, MSR codes suffer from a high repair degree, meaning many helper nodes are needed in the node repair process. Compared to MSR codes, locally repairable codes (LRCs) can significantly reduce the repair degree at the cost of increased storage overhead. The recently introduced concept of vector LRCs combines the advantages of MSR codes and LRCs, providing a tradeoff between repair degree/repair bandwidth and storage overhead. Most existing vector LRCs are built on MSR codes or their shortened versions. However, existing MSR codes have an unavoidably large sub-packetization levels, which also result in large sub-packetization levels in the corresponding vector LRCs. In this paper, we propose a new vector LRC structure, where MDS array codes (without shortening) can be employed as the local codes. Based this new structure, we propose three constructions of vector LRCs with small sub-packetization levels and small repair bandwidth, whose required field sizes are comparable to the code lengths. Additionally, the first two constructions offer a flexible tradeoff between the sub-packetization level and the repair bandwidth, while the third construction has a sub-packetization level of 2, making it easy to implement. Compared to existing vector LRCs, the new vector LRCs provide significantly smaller sub-packetization levels and support a wider range of parameters.

Piggybacking codes are a class of maximum distance separable (MDS) array codes that can achieve repair bandwidth reduction of single-node erasure by adding some piggyback functions to a subset of parity symbols. However, the repair bandwidth reduction is limited since the number of parity symbols the piggyback function can be added should be strictly less than a value to maintain the MDS property. In this paper, we first propose a new transformation on parity nodes that can effectively reduce the repair bandwidth of parity nodes, and the MDS property can still be maintained without changing the field size of the base code. Combined with the new transformation, we jointly design piggyback functions to reduce the repair bandwidth of data nodes. Since the new transformation no longer obeys the constraints under the piggybacking framework, we call the newly obtained codes aspiggybacking+codes. We theoretically show that the repair bandwidth of the piggybacking+ code is strictly lower than that of the existing piggybacking codes at high-code-rate parameters. We also show that our piggybacking+ codes have 3% to 29% repair bandwidth reduction than the existing piggybacking codes for the evaluated high-code-rate parameters.

Reed-Solomon (RS) codes are widely used to correct errors in storage systems. Finding the error locator polynomial is one of the key steps in the error correction procedure of RS codes. Modular Approach (MA) is an effective algorithm for solving the Welch-Berlekamp (WB) key-equation problem to find the error locator polynomial that needs$2t$steps, wheretis the error correction capability. In this paper, we first present a new MA algorithm that only requires$2e$steps and then propose two fast decoding algorithms for RS codes based on our MA algorithm, whereeis the number of errors and$e\leq t$. We propose the Improved-Frequency Domain Modular Approach (I-FDMA) algorithm that needs$2e$steps to solve the error locator polynomial and present our first decoding algorithm based on the I-FDMA algorithm. We show that, compared with the existing methods based on MA algorithms, our I-FDMA algorithm can effectively reduce the decoding complexity of RS codes when$e\lt t$. Furthermore, we propose the$t_{0}$-Shortened I-FDMA ($t_{0}$-SI-FDMA) algorithm ($t_{0}$is a predetermined even number less than$2t-1$) based on the new termination mechanism to solve the error numberequickly. We propose our second decoding algorithm based on the SI-FDMA algorithm for RS codes and show that the multiplication complexity of our second decoding algorithm is lower than our first decoding algorithm (the I-FDMA decoding algorithm) when$2e\lt t_{0}+1$.

For large-scale wireless networks, the optimal network decomposition has been proposed from a graph theoretical perspective to maximize the number of decomposed subnetworks with an interference constraint. When each user is associated with multiple base-stations (BSs) to form its virtual cell, however, the optimal network decomposition may lead to highly unbalanced subnetwork sizes if the key system parameters are not properly set. In this paper, an analytical framework is proposed to characterize the distribution of subnetwork size in terms of the number of users in a randomly chosen subnetwork for virtual-cell-based optimal decomposition. The analysis reveals that the distribution of subnetwork size is crucially determined by the virtual cell size, i.e., the number of BSs associated with each user, and the ratio of the number of users to the number of BSs, both of which should be carefully tuned to produce balanced subnetworks.

Beam-level clustered cell-free networking that partitions beams from multiple base-stations (BSs) and users into non-overlapping subnetworks can enable cooperative transmission among BSs, while avoiding coordinating all the beams at a BS. Previous work adopted spectral clustering to group beams and users into subnetworks, which, however, has cubic complexity and cannot control the number of activated beams. In this paper, a tunable weighted kernel k-means algorithm along with a novel initialization approach and two tuning hyper-parameters are proposed. Simulation results show that the proposed algorithm can successfully accelerate clustered cell-free networking by avoiding eigenvalue decomposition as well as control the number of activated beams by carefully fine-tuning hyper-parameters.

Reed-Solomon (RS) codes are widely used to correct errors, finding the error locator polynomial is one of the key steps in the error correction procedure of RS codes. Modular Approach (MA) is a classical algorithm to solve the Welch-Berlekamp (WB) key-equation problem to find the error locator polynomial that needs$2t$steps, where$t$is the error correction capability. In this paper, we present a new MA algorithm that only requires$2e$steps, where$e$is the number of errors. Moreover, we propose a new error correction algorithm based on our MA algorithm, which is called the Improved-Frequency Domain Modular Approach (I-FDMA) algorithm. We show that, compared with the existing methods based on MA algorithms, our I-FDMA algorithm can effectively reduce the decoding complexity of RS codes when$e < t$.

Erasure codes have been widely employed in distributed storage systems to provide high data reliability at a cost of small redundancy. Modern distributed storage systems usually organize the storage nodes in racks, in which the cross-rack communication cost is much more expensive than the intra-rack communication cost. When the original data symbols stored in a single node are updated, it is critical to design erasure codes that can update the corresponding coded symbols with the cross-rack update bandwidth defined as the average amount of symbols transferred across different racks as small as possible. In this paper, we first derive a tight lower bound on the cross-rack update bandwidth under the condition of$(n, k)$reconstruction property that is any$k$out of the$n$nodes can retrieve all the data symbols. Moreover, we derive the lower bound on redundancy subject to the minimum cross-rack update bandwidth. Furthermore, we propose explicit constructions that can achieve both the minimum cross-rack update bandwidth and the minimum redundancy.

Maximum distance separable (MDS) codes facilitate the achievement of elevated levels of fault tolerance in storage systems while incurring minimal redundancy overhead. Reed-Solomon (RS) codes are typical MDS codes with the sub-packetization level being one, however, they require large repair bandwidth defined as the total amount of symbols downloaded from other surviving nodes during single-node failure/repair. In this paper, we present the set transformation, which can transform any MDS code into set transformed code such that (i) the sub-packetization level is flexible and ranges from 2 to$(n-k)^{\lfloor\frac{n}{n-k}\rfloor}$in which$n$is the number of nodes and$k$is the number of data nodes, (ii) the new code is MDS code, (iii) the new code has lower repair bandwidth for any single-node failure. We show that our set transformed codes have both lower repair bandwidth and lower field size than the existing related MDS array codes, such as elastic transformed codes [1]. Specifically, our set transformed codes have 2% - 6.6% repair bandwidth reduction compared with elastic transformed codes [1] for the evaluated typical parameters.

In this paper, we consider the problem of zero-error network function computation. In a directed acyclic network, a single sink node requires to compute with zero error a function of source messages generated by multiple source nodes. We are interested in the information-theoretic computing capacity, which is defined as the average number of times that the function can be computed with zero error for one use of the network. The explicit characterization of the computing capacity in general is extremely challenging. The best known upper bound, applicable to arbitrary network topologies and arbitrary target functions, is the one proved by Guang et al. using the cut-set strong partition approach. This bound is tight for all previously considered network function computation problems whose computing capacities are known. In this paper, we focus on the model of computing the binary arithmetic sum over an asymmetric diamond network, which is of great importance to illustrate the combinatorial nature of network function computation problem. We first prove an upper bound of 1 on the computing capacity by using a linear programming approach, which rectifies an invalid upper bound previously proposed in the literature. However, this upper bound does not surpass the best known upper bound for this model, which is also equal to 1. Further, by developing a different graph coloring approach, we obtain an improved upper bound 3–1 0.822). We thus show that the best known upper bound by Guang et al. is not tight for this model. On the other hand, we present an explicit code construction, which implies a lower bound 6 0.815) on the computing capacity. Comparing the improved upper and lower bounds thus obtained, there exists a rough 0.007 gap between them.

Reed-Solomon (RS) codes are widely used in storage systems to ensure data reliability. In this paper, we first propose a new construction of RS codes with between three to five parity symbols over a special finite field of size 256. We show that all the operations involved in the encoding/decoding process can be implemented by XOR and cyclic shift. Second, we present a fast encoding/decoding algorithm for our codes by designing a modified Reed-Muller (RM) transform that has both small computational complexity and space complexity. We show that our codes have much lower space complexity and nearly the same computational complexity, compared with the existing RM-based RS codes. Simulation results demonstrate that our codes improve encoding and decoding throughput by 34.06% and 31.66%, respectively, under evaluated parameters, compared with existing RM-based RS codes.

We consider a model of broadcast channel where a pair of base-user operates in the full-duplex mode. A partial decode-forward strategy together with Marton's coding are adopted to obtain an inner bound. An outer bound is also presented. Numerical evaluations are performed on a particular set of discrete memoryless channels to compare the sum-rates of these two bounds and the one of time division duplex.

As maximum distance separable (MDS) array codes, piggybacking codes can effectively reduce the repair bandwidth of traditional MDS codes for single-node failure with small sub-packetization. However, the requirement of maintaining MDS property over small field size imposes severe restrictions on the design of piggyback functions in the piggybacking framework, which limits the reduction of repair bandwidth. In this paper, we propose conjugate-piggybacking codes over a small sub-packetization level. We design conjugate transformation for piggyback functions in our codes, which enables some parity nodes to achieve optimal repair bandwidth. We show that our codes are MDS codes over a slightly larger field size than the existing related piggybacking codes. We also show that our codes have lower repair bandwidth than the existing related piggybacking codes under evaluated high-code-rate parameters and$\mathbb{F}_{2^{8}}$.

As a special class of array codes, piggybacking codes are maximum distance separable (MDS) codes that can achieve low repair bandwidth for single-node erasure. An (n,k,m) piggybacking code containskdata nodes andr=n-kparity nodes, each node storesmsymbols. In this paper, we propose a new piggybacking design by jointly designing piggyback functions for both data node repair and parity node repair to reduce the repair bandwidth. Our piggybacking codes can support flexible sub-packetizationmwith 2 ≤m≤r. Whenm=r, we derive a new lower bound of repair bandwidth based on our piggybacking structure and show that this lower bound is lower than the corresponding lower bounds derived from the existing piggybacking codes for 5r≪k. Whenmr, we show that our piggybacking codes have lower repair bandwidth than the existing piggybacking codes for all the evaluated high-code-rate parameters with 10 ≤r≤ 20,k= 100 andm≤ 5. Moreover, we derive the lower bound of repair complexity defined as the number of multiplication operations required in repairing single-node erasure under general piggybacking framework and show that our codes can achieve the repair complexity lower bound, i.e., our codes have optimal repair complexity.

Maximum distance separable (MDS) codes have the optimal trade-off between storage efficiency and fault tolerance, which are widely used in distributed storage systems. As typical non-MDS codes, simple regenerating codes (SRCs) can achieve both smaller repair bandwidth and smaller repair locality than traditional MDS codes in repairing single-node erasure. In this paper, we propose generalized simple regenerating codes (GSRCs) that can support much more parameters than that of SRCs. We show that there is a trade-off between sub-packetization and fault tolerance in our GSRCs, and SRCs achieve a special point of the trade-off of GSRCs. We show that the fault tolerance of our GSRCs increases when the sub-packetization increases linearly. We also show that our GSRCs can locally repair any single-symbol erasure and any single-node erasure, and the repair bandwidth of our GSRCs is smaller than that of the existing related codes.

Conditional graph entropy is known to be the minimal rate for a natural functional compression problem with side information at the receiver. In this paper we show that it can be formulated as an alternating minimization problem, which gives rise to a simple iterative algorithm for numerically computing (conditional) graph entropy. This also leads to a new formula which shows that conditional graph entropy is part of a more general framework: the solution of an optimization problem over a convex corner. In the special case of graph entropy (i.e., unconditioned version) this was known due to Csiszár, Körner, Lovász, Marton, and Simonyi. In that case the role of the convex corner was played by the so-called vertex packing polytope. In the conditional version it is a more intricate convex body but the function to minimize is the same. Furthermore, we describe a dual problem that leads to an optimality check and an error bound for the iterative algorithm.

As a special class of array codes,$(n,\ k,\ m)$piggy-backing codes are$n\times m$MDS array codes with each node storing$m$symbols that can achieve low repair bandwidth for single-node failure. The existing piggybacking codes design piggyback functions for either data node repair or parity node repair. In this paper, we propose new piggybacking codes by jointly designing piggyback functions for both data node repair and parity node repair that have lower repair bandwidth than the related existing piggybacking codes. In our piggybacking codes, the sub-packetization$m$satisfies that$2\leq m\leq n-k$. When$m=n-k$, we derive a lower bound of repair bandwidth for our piggybacking codes, and prove that this lower bound is lower than the corresponding lower bounds of the existing piggybacking codes for$5 < n-k\ll k$. When$m < n-k$, we show that our piggybacking codes have lower repair bandwidth than the existing piggybacking codes for all the evaluated high-code-rate parameters with$10 < n-k < 20, k=100$and$m\leq 5$.

Piggybacking codes are a class of maximum distance separable (MDS) array codes that can achieve repair bandwidth reduction of single-node failure by adding some piggyback functions in a subset of parity symbols. However, the repair bandwidth reduction is limited since the number of parity symbols of which the piggyback function can be added should be strictly less than a value in order to maintain the MDS property. In this paper, we present a new class of MDS array codes, call piggybacking+ codes with linear sub-packetization level and small finite field that can achieve lower repair bandwidth compared with the existing piggybacking codes. We show that our piggybacking+ codes have 3% to 29% repair bandwidth reduction of the existing piggybacking codes for the evaluated high -code- rate parameters. Our main idea is that we design piggyback functions for data node repair and transformation functions for parity node repair such that the number of parity symbols which can add piggyback function or transformation function is larger than that of the existing piggybacking codes.

Graph partitioning is crucial in distributed graph-parallel computing systems, and it is challenging for graph partitioning to optimize the communication cost and load balancing together. Existing state-of-the-art works, such as Powerlyra and TopoX, optimize the load balancing by randomly distributing the edges of high-degree vertices, which inevitably brings a high communication cost that is unbounded. This paper proposes a graph partition model that can minimize communication cost while maximizing load balancing. More specifically, we model the graph partition as the combinatorial design problem. Our proposed model can provide high-quality partition that guarantees that the computing load can be evenly distributed to each worker and minimizes the communication cost with a near-optimal theoretical boundary.Based on the proposed model, we extend the hybrid-cut partitioning algorithm for the power-law graph and propose HCPD, a hybrid-cut partitioning algorithm based on combinatorial design. HCPD uses the proposed model to optimize the load balancing and communication cost simultaneously for high-degree vertices, and assigns the high-degree vertices and their low-degree neighbors to the same workers by label propagation to reduce the overall communication cost. In this way, we partition the low-degree and high-degree vertices holistically and further improve the partition quality, unlike Powerlyra and TopoX, which deal with the two parts independently. Our experiments show that HCPD outperforms Powerlyra on PageRank task by up to 2× faster on real-world power-law graphs with billions of edges.

This paper presents a new erasure decoding algorithm for low-rate Reed–Solomon codes (rate ≤ 0.5) based on a recently proposed FFT known as LCH-FFT. The algorithm requires O(n log k) finite field operations, where n and k are the code’s length and dimension, respectively. Experiments based on the Intel AVX2 Instructions show that notable improvements in the throughput are achieved compared with the best-known algorithm with complexity O(n log n) (also based on LCH-FFT), and new speed records are created.

The nascent field of Rate-Distortion-Perception (RDP) theory is seeing a surge of research interest due to the application of machine learning techniques in the area of lossy compression. The information RDP function characterizes the three-way trade-off between description rate, average distortion, and perceptual quality measured by discrepancy between probability distributions. However, computing RDP functions has been a challenge due to the introduction of the perceptual constraint, and existing research often resorts to data-driven methods. In this paper, we show that the information RDP function can be transformed into a Wasserstein Barycenter problem. The non-strictly convexity brought by the perceptual constraint can be regularized by an entropy regularization term. We prove that the entropy regularized model converges to the original problem. Furthermore, we propose an alternating iteration method based on the Sinkhorn algorithm to numerically solve the regularized optimization problem. Experimental results demonstrate the efficiency and accuracy of the proposed algorithm.

Information bottleneck (IB) is a paradigm to extract information in one target random variable from another relevant random variable, which has aroused great interest due to its potential to explain deep neural networks in terms of information compression and prediction. Despite its great importance, finding the optimal bottleneck variable involves a difficult nonconvex optimization problem due to the nonconvexity of mutual information constraint. The Blahut-Arimoto algorithm and its variants provide an approach by considering its Lagrangian with fixed Lagrange multiplier. However, only the strictly concave IB curve can be fully obtained by the BA algorithm, which strongly limits its application in machine learning and related fields, as strict concavity cannot be guaranteed in those problems. To overcome the above difficulty, we derive an entropy regularized optimal transport (OT) model for IB problem from a posterior probability perspective. Correspondingly, we use the alternating optimization procedure and generalize the Sinkhorn algorithm to solve the above OT model. The effectiveness and efficiency of our approach are demonstrated via numerical experiments.

Recent advances in machine learning-aided lossy compression are incorporating perceptual fidelity into the rate-distortion theory. In this paper, we study the rate-distortion-perception trade-off when the perceptual quality is measured by the total variation distance between the empirical and product distributions of the discrete memoryless source and its reconstruction. We consider the general setting, where two types of resources are available at both the encoder and decoder: a common side information sequence, correlated with the source sequence, and common randomness. We consider both the strong perceptual constraint and the weaker empirical perceptual constraint. The required communication rate for achieving the distortion and empirical perceptual constraint is the minimum conditional mutual information, and similar result holds for strong perceptual constraint when sufficient common randomness is provided and the output along with the side information is constraint to an independent and identically distributed sequence.

This paper proposes the re-encoding transformed (ReT) based list decoding using the module basis reduction (BR) interpolation for algebraic geometric (AG) codes on Cabcurves. The two ReT approaches are introduced to facilitate the BR interpolation. One is realized by the bivariate Lagrange polynomial. The other is conducted by the ReT of Reed-Solomon (RS) codes based on the mathematical structure of AG codes. The ReT based BR interpolation (ReT-BR) algorithm for decoding the AG codes is further introduced. Finally, complexity of the proposed algorithm is analyzed and validated by the simulation results, demonstrating its complexity advantage over the non-ReT counterpart.

Sparse regression codes (SPARCs) are a promising coding scheme that can approach the Shannon limit over Additive White Gaussian Noise (AWGN) channels. Previous works have proven the capacity-achieving property of SPARCs with Gaussian design matrices. We generalize these results to right orthogonally invariant ensembles that allow for more structured design matrices. With the Vector Approximate Message Passing (VAMP) decoder, we rigorously demonstrate the exponentially decaying error probability for design matrices that satisfy a certain criterion with the exponentially decaying power allocation. For other spectra, we design a new power allocation scheme to show that the information theoretical threshold is achievable.

This paper presents a low-complexity lossy compression scheme for Gaussian vectors, using sparse regression codes (SRC) and a novel decimated approximate message passing (AMP) encoder. The sparse regression codebook is characterized by a design matrix and each codeword is a linear combination of selected columns of the matrix. In order to enable the convergence of AMP for lossy compression, we incorporate the concept of decimation into the AMP algorithm for the first time. Further, we show that the power allocation technique is beneficial for improving the rate-distortion performance. The computational complexity of the proposed encoding is O(log n) per source sample for a length-n source vector, using a sub-Fourier design matrix. Moreover, the proposed AMP encoder inherently supports successively refinable compression. Simulation results show that the proposed decimated AMP encoder significantly outperforms the existing successive-approximation encoding [1] and approaches the rate-distortion limit in low-rate regime.

In this paper, we propose a new framework named Communication Optimal Transport (CommOT) for computing the rate distortion (RD) function. This work is motivated by observing the fact that the transition law and the relative entropy in communication theory can be viewed as the transport plan and the regularized objective function in the optimal transport (OT) model. However, unlike in classical OT problems, the RD function only possesses one-side marginal distribution. Hence, to maintain the OT structure, we introduce slackness variables to fulfill the other-side marginal distribution and then propose a general framework (CommOT) for the RD function. The CommOT model is solved via the alternating optimization technique and the well-known Sinkhorn algorithm. In particular, the expected distortion threshold can be converted into finding the unique root of a one-dimensional monotonic function with only a few steps. Numerical experiments show that our proposed framework (CommOT) for solving the RD function with given distortion threshold is efficient and accurate.

SimRank is an important metric to measure the topological similarity between two nodes in a graph. In particular, single-source and top-k SimRank has numerous applications in recommendation systems, network analysis, and web mining, etc. Mathematically, given a vertex, the computation of single-machine and single-source SimRank mainly lies in matrix-matrix operations. However, it is almost impossible to directly compute on large graphs. Thus, existing works yield to two main operations: a series of random walks, and sparse matrix and dense vector multiplication operations. This brings about high computation cost for SimRank on large graphs. In real-world applications, there is always the query time and accuracy trade-off, which hinders the computation of high-precision SimRank on large-scale graphs. To handle this problem, this paper proposesClipSim, the first GPU-friendly parallel framework that accelerates the single-source SimRank on GPU with accuracy guarantee. We design a novel data structure and GPU-friendly parallel algorithms for efficient computation of all the operations of SimRank on GPU. Moreover, our theoretical derivation enables ClipSim to largely reduce the number of random walks required for each node, while maintaining the same theoretical accuracy as the state-of-the-art algorithm, ExactSim. We conduct extensive experiments on real-world and synthetic datasets to demonstrate the accuracy and efficiency of ClipSim. The results show that compared with ExactSim, ClipSim obtains single-source SimRank vectors with the same accuracy and up to 160× faster computation time.

Abundant high-rate$(n, k)$minimum storage regenerating (MSR) codes have been reported in the literature. However, most of them require contacting all the surviving nodes during a node repair process, resulting in a repair degree of$d=n-1$. In practical systems, it may not always be feasible to connect and download data from all surviving nodes, as some nodes may be unavailable. Therefore, there is a need for MSR code constructions with a repair degree of$d < n-1$. Up to now, only a few$(n, k)$MSR code constructions with repair degree$d < n-1$have been reported, some have a large sub-packetization level, a large finite field, or restrictions on the repair degree$d$. In this paper, we propose a new$(n, k)$MSR code construction that works for any repair degree$d>k$, and has a smaller sub-packetization level or finite field than some existing constructions. Additionally, in conjunction with a previous generic transformation to reduce the sub-packetization level, we obtain an MDS array code with a small sub-packetization level and$(1+\epsilon)$-optimal repair bandwidth (i.e.,$(1+\epsilon)$times the optimal repair bandwidth) for repair degree$d=n-1$. This code outperforms some existing ones in terms of either the sub-packetization level or the field size.

Maintaining the freshness of information in the Internet of Things (IoT) is a critical yet challenging problem. In this paper, we study cooperative data collection using multiple Unmanned Aerial Vehicles (UAVs) with the objective of minimizing the total average Age of Information (AoI). We consider various constraints of the UAVs, including kinematic, energy, trajectory, and collision avoidance, in order to optimize the data collection process. Specifically, each UAV, which has limited on-board energy, takes off from its initial location and flies over sensor nodes to collect update packets in cooperation with the other UAVs. The UAVs must land at their final destinations with non-negative residual energy after the specified time duration to ensure they have enough energy to complete their missions. It is crucial to design the trajectories of the UAVs and the transmission scheduling of the sensor nodes to enhance information freshness. We model the multi-UAV data collection problem as a Decentralized Partially Observable Markov Decision Process (Dec-POMDP), as each UAV is unaware of the dynamics of the environment and can only observe a part of the sensors. To address the challenges of this problem, we propose a multi-agent Deep Reinforcement Learning (DRL)-based algorithm with centralized learning and decentralized execution. In addition to the reward shaping, we use action masks to filter out invalid actions and ensure that the constraints are met. Simulation results demonstrate that the proposed algorithms can significantly reduce the total average AoI compared to the baseline algorithms, and the use of the action mask method can improve the convergence speed of the proposed algorithm.

Partial maximum distance separable (PMDS) codes are a kind of erasure codes where the nodes are divided into multiple groups with each forming an MDS code with a smaller code length, thus they allow repairing a failed node with only a few helper nodes and can correct all erasure patterns that are information-theoretically correctable. However, the repair of a failed node of PMDS codes still requires a large amount of communication if the group size is large. Recently, PMDS array codes with each local code being an MSR code were introduced to reduce the repair bandwidth further. However, they require extensive rebuilding access and unavoidably a significant sub-packetization level. In this paper, we first propose two constructions of PMDS array codes with two global parities that have smaller sub-packetization levels and much smaller finite fields than the existing one. One construction can support an arbitrary number of local parities and has$(1+\epsilon)$-optimal repair bandwidth (i.e.,$(1+\epsilon)$times the optimal repair bandwidth), while the other one is limited to two local parities but has significantly smaller rebuilding access and its sub-packetization level is only 2. In addition, we present a construction of PMDS array code with three global parities, which has a smaller sub-packetization level as well as$(1+\epsilon)$-optimal repair bandwidth, the required finite field is significantly smaller than existing ones.

Many network applications can be formulated as NP-hard combinatorial optimization problems of community detection (CD) that partitions nodes of a graph into several groups with dense linkage. Most existing CD methods are transductive , which independently optimized their models for each single graph, and can only ensure either high quality or efficiency of CD by respectively using advanced machine learning techniques or fast heuristic approximation. In this study, we consider the CD task and aims to alleviate its NP-hard challenge. Motivated by the efficient inductive inference of graph neural networks (GNNs), we explore the possibility to achieve a better tradeoff between the quality and efficiency of CD via an inductive embedding scheme across multiple graphs of a system and propose a novel inductive community detection (ICD) method. Concretely, ICD first conducts the offline training of an adversarial dual GNN structure on historical graphs to capture key properties of a system. The trained model is then directly generalized to new graphs of the same system for online CD without additional optimization, where a better tradeoff between quality and efficiency can be achieved. Compared with existing inductive approaches, we develop a novel feature extraction module based on graph coarsening, which can efficiently extract informative feature inputs for GNNs. Moreover, our original designs of adversarial dual GNN and clustering regularization loss further enable ICD to capture permutation-invariant community labels in the offline training and help derive community-preserved embedding to support the high-quality online CD. Experiments on a set of benchmarks demonstrate that ICD can achieve a significant tradeoff between quality and efficiency over various baselines.

Temporal link prediction (TLP) is an inference task on dynamic graphs that predicts future topology using historical graph snapshots. Existing TLP methods are usually designed for unweighted graphs with fixed node sets. Some of them cannot be generalized to the prediction of weighted graphs with non-fixed node sets. Although several methods can still be used to predict weighted graphs, they can only derivelow-qualityprediction snapshots sensitive to large edge weights but fail to distinguish small and zero weights in adjacency matrices. In this study, we consider the challenginghigh-qualityTLP on weighted dynamic graphs and propose a novel inductive dynamic embedding aggregation (IDEA) method, inspired by the high-resolution video prediction. IDEA combines conventional error minimization objectives with a scale difference minimization objective, which can generatehigh-qualityweighted prediction snapshots, distinguishing differences among large, small, and zero weights in adjacency matrices. Since IDEA adopts an inductive dynamic embedding scheme with an attentive node aligning unit and adaptive embedding aggregation module, it can also tackle the TLP on weighted graphs even with non-fixed node sets. Experiments on datasets of various scenarios validate that IDEA can derivehigh-qualityprediction results for weighted dynamic graphs and tackle the variation of node sets.

By moving to millimeter wave (mmWave) frequencies, base stations (BSs) will be densely deployed to provide seamless coverage in sixth generation (6G) mobile communication systems, which, unfortunately, leads to severe cell-edge problem. In addition, with massive multiple-input-multiple-output (MIMO) antenna arrays employed at BSs, the beamspace channel is sparse for each user, and thus there is no need to serve all the users in a cell by all the beams therein jointly. Therefore, it is of paramount importance to develop a flexible clustered cell-free networking scheme that can decompose the whole network into a number of weakly interfered small subnetworks operating independently and in parallel. Given a per-user rate constraint for service quality guarantee, this paper aims to maximize the number of decomposed subnetworks so as to reduce the signaling overhead and system complexity as much as possible. By formulating it as a bipartite graph partitioning problem, a rate-constrained network decomposition (RC-NetDecomp) algorithm is proposed, which can smoothly tune the network structure from the current cellular network with simple beam allocation to a fully cooperative network by increasing the required per-user rate. Simulation results demonstrate that the proposed RC-NetDecomp algorithm outperforms existing baselines in terms of average per-user rate, fairness among users and energy efficiency.

In this paper, we study a concatenate coding scheme based on sparse regression code (SPARC) and tree code for unsourced random access in massive multiple-input and multiple-output systems. Our focus is concentrated on efficient decoding for the inner SPARC with practical concerns. A two-stage method is proposed to achieve near-optimal performance while maintaining low computational complexity. Specifically, a one-step thresholding-based algorithm is first used for reducing large dimensions of the SPARC decoding, after which a relaxed maximum-likelihood estimator is employed for refinement. Adequate simulation results are provided to validate the near-optimal performance and the low computational complexity. Besides, for covariance-based sparse recovery method, theoretical analyses are given to characterize the upper bound of the number of active users supported when convex relaxation is considered, and the probability of successful dimension reduction by the one-step thresholding-based algorithm.

Wireless network capacity can be regarded as the most important performance metric for wireless communication systems. With the fast development of wireless communication technology, future wireless systems will become more and more complicated. As a result, the channel gain matrix will become a large-dimensional random matrix, leading to an extremely high computational cost to obtain the capacity. In this paper, we propose a moment passing method (MPM) to realize the fast and accurate capacity estimation for future ultra-dense wireless systems. It can determine the capacity with quadratic complexity, which is optimal considering that the cost of a single matrix operation is not less than quadratic complexity. Moreover, it has high accuracy. The simulation results show that the estimation error of this method is below 2%. Finally, our method is highly general, as it is independent of the distributions of BSs and users, and the shape of network areas. More importantly, it can be applied not only to the conventional multi-user multiple input and multiple output (MU-MIMO) networks, but also to the capacity-centric networks designed for B5G/6G.

Mismatch capacity characterizes the highest information rate for a channel under a prescribed decoding metric, and is thus a highly relevant fundamental performance metric when dealing with many practically important communication scenarios. Compared with the frequently used generalized mutual information (GMI), the LM rate has been known as a tighter lower bound of the mismatch capacity. The computation of the LM rate,11To our best knowledge, the name LM rate first appeared in the reference [1]. The capital letter LM seems to be the abbreviation of Lower bound on the Mismatch capacity. however, has been a difficult task, due to the fact that the LM rate involves a maximization over a function of the channel input, which becomes challenging as the input alphabet size grows, and direct numerical methods (e.g., interior point methods) suffer from intensive memory and computational resource requirements. Noting that the computation of the LM rate can also be formulated as an entropy-based optimization problem with constraints, in this work, we transform the task into an optimal transport (OT) problem with an extra constraint. This allows us to efficiently and accurately accomplish our task by using the well-known Sinkhorn algorithm. Indeed, only a few iterations are required for convergence, due to the fact that the formulated problem does not contain additional regularization terms. Moreover, we convert the extra constraint into a root-finding procedure for a one-dimensional monotonic function. Numerical experiments demonstrate the feasibility and efficiency of our OT approach to the computation of the LM rate.

In this paper, we study a concatenate coding scheme based on sparse regression code (SPARC) and tree code for unsourced random access in massive multiple-input and multiple-output systems. Our focus is concentrated on efficient decoding for the inner SPARC with practical concerns. A two-stage method is proposed to achieve near-optimal performance while maintaining low computational complexity [1]. Specifically, a one-step thresholding-based algorithm is first used for reducing large dimensions of the SPARC decoding, after which a relaxed maximum-likelihood estimator is employed for refinement. Adequate simulation results are provided to validate the near-optimal performance and the low computational complexity. Besides, for covariance-based sparse recovery method, theoretical analyses are given to characterize the upper bound of the number of active users supported when convex relaxation is considered, and the probability of successful dimension reduction by the one-step thresholding-based algorithm.

In this paper, we propose a Bi-layer Prediction-based Reduction Branch (BP-RB) framework to speed up the process of finding a high-quality feasible solution for Mixed Integer Programming (MIP) problems. A graph convolutional network (GCN) is employed to predict binary variables' values. After that, a subset of binary variables is fixed to the predicted value by a greedy method conditioned on the predicted probabilities. By exploring the logical consequences, a learning-based problem reduction method is proposed, significantly reducing the variable and constraint sizes. With the reductive sub- MIP problem, the second layer GCN framework is employed to update the prediction for the remaining binary variables' values and to determine the selection of variables which are then used for branching to generate the Branch and Bound (B&B) tree. Numerical examples show that our BP-RB framework speeds up the primal heuristic and finds the feasible solution with high quality.

Base-stations (BSs) will be densely deployed to provide seamless coverage in sixth generation (6G) mobile communication systems, which, unfortunately, leads to severe cell-edge problem. A flexible clustered cell-free networking scheme to replace the cellular network is studied in this paper, which decomposes the whole network into a number of subnetworks operating independently. In order to reduce signaling overhead and system complexity as far as possible, we aim to maximize the number of decomposed subnetworks with a per-user rate constraint for service quality guarantee. In addition, subnetworks with BSs only are allowed to enable BS sleep mode operation. A rate-constrained network decomposition (RC-NetDecomp) algorithm is proposed, which can smoothly tune the network structure from the current cellular network to the fully cooperative network by varying the required per-user rate. Simulation results demonstrate that it outperforms the existing baselines in terms of both average per-user rate and fairness among users.

The sixth generation (6G) era is envisioned to be a fully intelligent and autonomous era, with physical and digital lifestyles merged together. Future wireless network architectures should provide a solid support for such new lifestyles. A key problem thus arises that what kind of network architectures are suitable for 6G. In this paper, we propose a capacity-guaranteed network (CGN) architecture, which provides high capacity for wireless devices densely distributed everywhere, and ensures a superior scalability with low signaling overhead and computation complexity simultaneously. Our theorem proves that the essence of a CGN architecture is to decompose the whole network into non-overlapping clusters with equal cluster sum capacity. Simulation results reveal that in terms of the minimum cluster sum capacity, the proposed CGN can achieve at least 30% performance gain compared with existing base station clustering (BS-clustering) architectures. In addition, our theorem is sufficiently general and can be applied for networks with different distributions of BSs and users.

Reconfigurable intelligent surfaces (RISs) are regarded as one of the most promising techniques in the sixth-generation (6G) mobile communication networks. With the feature of smartly tuning the electromagnetic environment, RISs provide a possibility for ubiquitous and high-precision localization in 6G. However, proper system models for large indoor RIS-assisted networks and high-precision localization algorithms are still missing. In this paper, we propose a RIS-assisted downlink millimeter-wave (mmWave) indoor localization framework based on segment-by-segment far-field assumption. In addition, a brand new coarse-to-fine localization algorithm with low-complexity grid design is provided. Numerical results show that millimeter-level localization precision is achieved under the RIS-assisted indoor scenarios, which reveals that RIS can provide a solid support for accurate localization in the 6G era.

We consider a semantic cipher system, in which we protect only the semantic information of the source. The optimal tradeoff is characterized among the coding rate, the secret key rate, the semantic information leakage rate, the source reconstruction distortion, and the semantic distortion. It is shown that an efficient key with a small size suffices to protect the semantic information.

Large-scale high code-rate maximum distance separable (MDS) codes are critical and important in distributed storage systems that can provide high fault tolerance with extremely small storage redundancy. Repair access (defined as the total amount of symbols accessed in repairing one single-node failure) is a key metric of designing MDS codes. In large-scale MDS codes, one single-node failure can be recovered by connecting a large number of helper nodes. However, one or more helper nodes may be busy and can not send symbols during the repair process. In this paper, we define the total amount of symbols accessed in repairing one single-node failure with one or more busy nodes as the repair access with busy-node. We then propose a class of MDS array codes over a well-designed binary cyclic ring that is with small sub-packetization, small repair access, small repair access with busy-node, and small encoding complexity.

Partial maximum distance separable (PMDS) codes are a kind of erasure codes where the storage nodes are divided into multiple groups with each forming an MDS code of a smaller code length. They allow repairing a failed node by contacting only a few helper nodes and can correct all erasure patterns which are information-theoretically correctable. However, the repair of a failed node of PMDS codes still requires a large amount of communication if the group size is large. Recently, PMDS array codes with each local code being an MSR code were introduced to further reduce the repair bandwidth, but codes over small finite fields only exist for two global parities, and require large rebuilding access and unavoidably a large sub-packetization level. In this paper, we propose two constructions of PMDS array codes with two and three global parities, respectively. Both have a small sub-packetization level, small repair bandwidth, and much smaller finite fields than existing ones.

Piggybacking codes are an important class of array codes with small sub-packetization to achieve small repair bandwidth for single-node failures. In this paper, we propose new piggybacking codes such that the sub-packetization is equal to the number of parity nodes. Our piggybacking codes have an efficient repair method for any single-node failure, including both data nodes and parity nodes. We show that the proposed piggybacking codes have strictly less repair bandwidth for any single-node failure than that of the existing piggybacking codes, when the code rate is k/n = 0.8, 0.9 and the number of parity nodes ranges from 6 to 40.

In this paper, we propose a method of checking data integrity in distributed storage systems. Compare with conventionally used cyclic redundancy check (CRC) method, the proposed method may usually achieve a 99% reduction of bandwidth with the expense of losing only a little detection capacity. We also provide an analysis of performance and a suggestion of auxiliary matrix used in the proposed framework. Besides, a theoretical upper bound of CRC method’s detection capacity is given.

We study an estimation-compression (EC) separation scheme in a semantic communication system. Therein, the semantic information is intrinsic and not observable. The EC scheme first estimates the semantic information from the observed message and then compresses the estimation subject to a rate-distortion regime. The corresponding EC rate-distortion tradeoff is obtained. In particular, the EC separation scheme achieves the semantic rate-distortion function if the estimation is a sufficient statistic of the semantic information based on the observed message. Moreover, the extra distortion incurred by the compression in addition to the irreducible error in semantic estimation problems is also analyzed. A binary classification of vector Gaussian observations is investigated. We design an optimal soft decision estimator which is a sufficient statistic and show that it strictly outperforms the Bayesian decision estimator in terms of rate-distortion tradeoff. As the dimension of the observed Gaussian vector increases, the performance gap between the Bayesian decision estimator and the soft decision estimator becomes smaller and smaller until it is negligible.

We consider a problem of coding for computing, where the decoder wishes to estimate a function of its local message and the source message at the encoder within a given distortion. We show that the rate-distortion function can be characterized through a characteristic multi-hypergraph, which simplifies the evaluation of the rate-distortion function.

This paper considers a concatenated coding scheme of sparse regression codes (SPARC) and tree code for asynchronous uplink unsourced random access. The encoding of SPARC is limited in a single sub-carrier to counter the unknown delay due to asynchronization. A slotted structure, where both channel uses and potential users are divided into slots, is added to reduce the overall computational complexity and improve its reliability when the length of the coherence block is limited. An efficient two-stage decoder is applied for further computational complexity reduction at the cost of slightly higher per-user probability of error. Asymptotic and numerical results are provided to demonstrate the effectiveness of the proposed scheme.

Information freshness, which is characterized by a new performance metric called age of information (AoI), significantly influences decision making in numerous applications. In wireless sensor networks, unmanned aerial vehicle (UAV) has been widely adopted for fresh data collection. The key to applying UAV lies in UAV trajectory planning. Considering several fixed waypoints in UAV trajectory, the trajectory planning is an NP-hard combinatorial optimization problem, and is difficult to solve in practice. To well balance between the accuracy and efficiency, we propose an end-to-end AI-based framework in this paper to deal with the UAV trajectory planning within two stages. First, the hover positions of UAV and data transmission time are decided using a clustering module. Then, the AoI-minimal flight path is obtained through a neural trajectory solver. Compared with classic heuristic algorithms, the proposed AI-based framework achieves a smaller AoI with two orders of magnitude lower computational time. Besides, the proposed AI-based framework can be easily generalized to larger-scale scenarios (e.g., up to 2,000 sensor nodes) which cannot be solved by exact algorithms (e.g., dynamic programming) in a limited time. Moreover, the AI-based framework is comparable in accuracy with the commercial open-source solver Google OR-tools, but the efficiency is increased by 200%.

The accelerated convergence of digital and real-world lifestyles has imposed unprecedented demands on today’s wireless network architectures, as it is highly desirable for such architectures to support wireless devices everywhere with high capacity and minimal signaling overhead. Conventional architectures, such as cellular architectures, are not able to satisfy these requirements simultaneously, and are thus no longer suitable for the future era. In this paper, we propose a capacity-centric (C2) architecture for future wireless networking. It is designed based on the principles of maximizing the number of non-overlapping clusters with the average cluster capacity guaranteed to be higher than a certain threshold, and thus provides a flexible way to balance the capacity requirement against the signaling overhead. Our analytical results reveal that C2 has superior generality, wherein both the cellular and the fully coordinated architectures can be viewed as its extreme cases. Simulation results show that the average capacity of C2 is at least three times higher compared to that of the cellular architecture. More importantly, different from the widely adopted conventional wisdom that base-station distributions dominate architecture designs, we find that the C2 architecture is not over-reliant on base-station distributions, and instead the user-side information plays a vital role and cannot be ignored.

Piggybacking is a class of coding framework for MDS array codes that can achieve small repair bandwidth with small sub-packetization. An ($n, k, \alpha$) piggybacking code can be represented by an$n\times \alpha$array such that each node (row) stores$\alpha$symbols and any$k$rows can retrieve all$k\alpha$data symbols. In this paper, we first propose a new piggybacking framework for MDS array codes with lower sub-packetization and then propose two specific piggybacking codes based on the proposed framework. We show that the average repair bandwidth of any single-node failure of our piggybacking codes is lower than all the existing piggybacking codes with the same parameters when the sub-packetization is small (usually$\alpha\leq 8$) and$n-k\geq 10$.

In this paper, we consider two rack-aware storage systems. First, large-scale rack-aware storage system, which is very common in large-scale storage system, is a rack-aware storage system where all sizes of racks are at least the number of redundant nodes. For such storage system, we prove that any Maximum Distance Separable (MDS) codes can have optimal inter-rack repair bandwidth and give a closed-form representation of all repair schemes with optimal inter-rack repair bandwidth. Furthermore, we show that the optimal repair access and optimal inter-rack repair bandwidth can be attained simultaneously for such storage system. Second, we investigate the rack-aware storage system of all racks with the same size, which is called uniform rack-aware storage system. We prove that, except the trivial cases, we cannot attain optimal inter-rack repair bandwidth and optimal repair access for such storage system at the same time. Specifically, we establish the lower bound of repair access for a repair scheme with optimal interrack repair bandwidth, which is tight for some parameters, and also the tight lower bound of inter-rack repair bandwidth for a repair scheme with optimal repair access.

Regenerating codes are designed to reduce the repair bandwidth (access bandwidth) for rebuilding a fail node in an erasure-coded storage system. In practical systems, the fail node is not rebuilt immediately. Before its rebuilding, the data originally stored in the failed node might be accessed by the system. Hence, accessing the data in the failed disk (degraded read) with low latency is crucial for any practical storage system. In this work, to solve this problem, a new class of the regenerating codes based on the maximum distance separable (MDS) array codes is defined, named the MDS array code with the property of degraded read friendly (DRF). For the DRF MDS array codes with 2 redundant nodes and the sub-packetization level of 2, the lower bound of their access bandwidth is derived. A class of the DRF MDS array codes that achieves the derived bound is given to solidify the achievability of the proposed lower bound.

Data-driven approaches have recently emerged as promising remedies for communication system designs, which leverage deep learning techniques for automated development and optimization. In this paper, we revisit the designs of multi-input multi-output (MIMO) wireless systems and investigate the end-to-end learning for MIMO systems with temporal correlations. Our objective is to develop a MIMO transceiver to improve the communication performance by making fully use of the available temporal information. Although the end-to-end learning framework has been applied to various communication systems, existing designs largely rely on memoryless autoencoders (AEs) and overlook the time dependency. To overcome this issue, we propose a novel learning-based MIMO transceiver, namely, the TC-MIMONet, which extends the conventional memoryless AE-based transceivers by customizing two neural network components with memory. In particular, a long short-term memory (LSTM)-based CSI predictor is adopted at the transmitter, while a two-timescale LSTM-based decoder is developed for the receiver. Simulation results show that TC-MIMONet achieves significant block error rate reduction compared to two baseline schemes without utilizing the available temporal information.

With the advance of unmanned aerial vehicles (UAVs) and low earth orbit (LEO) satellites, the integration of space, air and ground networks has become a potential solution to the beyond fifth generation (B5G) Internet of remote things (IoRT) networks. However, due to the network heterogeneity and the high mobility of UAVs and LEOs, how to design an efficient UAV-LEO integrated data collection scheme without infrastructure support is very challenging. In this paper, we investigate the resource allocation problem for a two-hop uplink UAV-LEO integrated data collection for the B5G IoRT networks, where numerous UAVs gather data from IoT devices and transmit the IoT data to LEO satellites. In order to maximize the data gathering efficiency in the IoT-UAV data gathering process, we study the bandwidth allocation of IoT devices and the 3-dimensional (3D) trajectory design of UAVs. In the UAV-LEO data transmission process, we jointly optimize the transmit powers of UAVs and the selections of LEO satellites for the total uploaded data amount and the energy consumption of UAVs. Considering the relay role and the cache capacity limitations of UAVs, we merge the optimizations of IoT-UAV data gathering and UAV-LEO data transmission into an integrated optimization problem, which is solved with the aid of the successive convex approximation (SCA) and the block coordinate descent (BCD) techniques. Simulation results demonstrate that the proposed scheme achieves better performance than the benchmark algorithms in terms of both energy consumption and total upload data amount.

In this work, we study the UAV-enabled data collection problem for high information freshness in wireless sensor networks, where one UAV is dispatched to collect information of ground Sensor Nodes (SNs). The information freshness is measured by the Age of Information (AoI) of each SN, which is defined as the sum of the SN's data uploading time and the UAV's flight time after leaving this SN. Two optimization problems of age-optimal data collection are formulated to minimize the SNs' maximal AoI and average AoI, respectively. An iterative SN association and trajectory planning policy is proposed to seek the age-optimal solutions via an iterative two-step procedure. Firstly, SN association is performed based on the affinity propagation clustering method with an appropriate weight to find a set of data Collection Points (CPs) at which the UAV hovers to collect data and schedules which SNs to upload in what order. Based on this result, trajectory planning is performed to find the max-AoI-optimal and ave-AoI-optimal trajectories of the UAV along the CPs using dynamic programming or genetic algorithm. With the optimized clustering weight, the proposed scheme can always strike a balance between the SNs' uploading time and the UAV's flight time in various scenarios. Simulation results show that the proposed strategy can improve the freshness of information collected from all the SNs.

This paper concerns practical issues of sparse regression codes (SRCs) with approximate message passing (AMP) decoding. First, Gaussian signaling of SRC incurs a high peak-to-average-power ratio (PAPR) problem. Second, the finite length performance of SRCs is poor at low-to-medium rates and cannot be improved by spatial coupling or power allocation. We confront the two challenges by introducing clipping to SRC. For the encoder, clipping is applied to the Gaussian codeword of SRC for reducing the high PAPR. For the decoder, generalized approximate message passing (GAMP) is used to handle the nonlinear clipping distortion. Interestingly, we observe that clipping with proper thresholds can improve the performance of SRC and the performance gain is large at low rates. Based on the state evolution analysis of GAMP decoding, we provide an explanation for such observation from the curve-matching perspective. In the end, some guidelines are provided for choosing proper clipping thresholds empirically.

In data center networks, flows with different objectives coexist and compete for limited resources. From the application-level perspective, it is hard to satisfy the demands of different flows without effective resource planning. To address the bandwidth allocation problem under multi-objective scenarios, we study a multi-objective network utility maximization (NUM) problem and propose our practical bandwidth allocation framework HOMMO, which consists of an upper layer algorithm (ULA) and a lower layer algorithm (LLA). This hierarchical design helps to strike a balance between accuracy and efficiency. Implemented in network switches, ULA is an online learning-based scheme that allocates bandwidth for aggregated flows with different performances objectives. Taking the outputs from ULA as capacity constraints, LLA acts as a fast scheduling method at packet-level. We extend NUMFabric by implementing the design of isolate queues and corresponding dequeue strategy in switches and make it a feasible solution of the LLA. Therefore, HOMMO achieves satisfactory isolation across flows with different objectives, which is equivalent to provide a network slicing solution. To evaluate the proposed framework, we implement it in ns-3 and verify the performance under various scenarios. The simulation results show that HOMMO not only quickly converges to a near-optimal solution of the multi-objective NUM problem but also guarantees a Pareto-optimal solution. Moreover, it outperforms the well-known transport protocol (i.e., DCTCP) with 2x increase on average bandwidth utilization and 1.96x improvement in global network utility at the aggregated flow level.

The widespread application of unmanned aerial vehicles (UAVs) urgently requires an effective tracking algorithm as technical support. Particle filter has been widely applied in maneuvering target tracking, however, there has been no suitable solution to the trade-off between weight degeneracy and particle diversity during the process of resampling. In this paper, we propose an improved particle filter algorithm based on systematic resampling with additional random perturbation. This method ensures that particle filter maintains particle diversity and reduces weight degeneracy under environments with different noise types, simultaneously. The simulation results demonstrate that the proposed algorithm generates more accurate filtered trajectory than generic particle filter, especially under the environment with low noise.

With the development of data center networks, traditional TCP/IP cannot support the demand in data centers. Remote Direct Memory Access (RDMA) technology could improve the performance of DCN significantly because of high throughput and low latency. However, load balancing is a key issue in RDMA which has not been solved distribute. This paper will propose an algorithm to solve the load balance problem in RDMA on application layer without hardware changing. The main idea is to divide data to chunks and data chunks on multiple reachable paths for transmission. However, it is no trivial to find the optimal chunk size and the path number, some empirical values are found by varieties of experiments and tests. Moreover, the chunk allocation scheme also needs to consider the traffic condition in DCNs to find more free paths to transmit. We evaluate the algorithm in application layer with ns3 simulator. The experiment results show that with our algorithm the completion time can decrease 81.03% at most.

Modern data center applications need high throughput (40Gbps) and ultra-low latency (<;10us per hop), along with low CPU overhead. Remote Direct Memory Access (RDMA), which can be deployed in RDMA over commodity Ethernet (RoCEv2) protocol, has the potential to satisfy the requirements. RoCEv2 needs a lossless environment to achieve high performance. RoCEv2 provides Priority-based Flow Control (PFC) to prevent packet loss caused by buffer overflow. But packet loss can still happen in today’s data centers due to other reasons such as switch configuration error. There are two retransmission algorithms dealing with the packet loss recovery: Go-Back-0 and Go-Back-N. Unfortunately, by simply applying Go-Back-N algorithm to RoCEv2, the relative throughput will drop to nearly zero when the packet loss rate exceeds 1%. This is mainly caused by the improper triggering mechanism of generating NAK. This paper proposed an Improved Go-Back-N algorithm to solve this problem, which involves two mechanism. The Improved Go-Back-N is easy to be deployed in today’s data centers because it makes no changes on switches. It can improve the relative throughput to about 60% when the packet loss rate increases to 1%.

In this paper, we generally formulate the dynamics prediction problem of various network systems (e.g., the prediction of mobility, traffic and topology) as the temporal link prediction task. Different from conventional techniques of temporal link prediction that ignore the potential non-linear characteristics and the informative link weights in the dynamic network, we introduce a novel non-linear model GCN-GAN to tackle the challenging temporal link prediction task of weighted dynamic networks. The proposed model leverages the benefits of the graph convolutional network (GCN), long short-term memory (LSTM) as well as the generative adversarial network (GAN). Thus, the dynamics, topology structure and evolutionary patterns of weighted dynamic networks can be fully exploited to improve the temporal link prediction performance. Concretely, we first utilize GCN to explore the local topological characteristics of each single snapshot and then employ LSTM to characterize the evolving features of the dynamic networks. Moreover, GAN is used to enhance the ability of the model to generate the next weighted network snapshot, which can effectively tackle the sparsity and the wide-value-range problem of edge weights in real-life dynamic networks. To verify the model's effectiveness, we conduct extensive experiments on four datasets of different network systems and application scenarios. The experimental results demonstrate that our model achieves impressive results compared to the state-of-the-art competitors.

The emergence of diversified services in the Internet of Things (IoT) poses new challenges to the datacenter, which plays an important role in data transmission. For example, urban monitoring system no longer takes delay as the only performance measure, but also needs to consider the freshness of information. Therefore, modern datacenters need to support multiple services of IoT. However, many works for datacenter networks focus on optimizing the flow completion time (FCT). The Age of Information (AoI) which is a new and promising concept in many real-time applications has not been considered in datacenter. In this paper, we apply the concept of AoI to guarantee the information freshness and propose an age-optimized receiver-driven transport control scheme, referred to as ARTHost. In ARTHost, by utilizing the receiver-driven approach, we propose a priority flow scheduling mechanism, where we classify flows into AoI flows and normal flows, representing diverse services. Then, we design a Receiver-Driven (RD) sampling pattern for AoI flows to optimize the freshness of information. Meanwhile, the optimization of FCT for normal flows is also considered. Finally, the simulation results show that the proposed ARTHost can achieve significant performance gain for AoI flows, while the performance loss of normal flows is negligible.

Modern data centers are the host for multitude of large-scale distributed applications. These applications generate tremendous amount of network flows to complete their tasks. At this scale, efficient network control manages the network traffic at the level of flow aggregates (or slices ) who need to share the network with respect to operator’s proportionality policy. Existing slice scheduling mechanisms can not meet this goal in multi-path data center networks. Hence, in this paper, we aim to fulfil this goal and satisfy the congestion proportionality policy for network sharing. The policy is applied to the traffic traversing congested links in the network. We propose Uranus, a novel slice scheduler based on a combination of flow-level control mechanisms. The scheduler implements two-tier weight allocation to individual flows. Then, relying on a non-blocking big switch abstraction, slice weights are allocated at the inter-rack level by aggregating the weights of rack-to-rack flows. Finally, Uranus can dynamically divide the rack-level weight to its constituent flows. We also implement Weighted Virtual Congestion Control (WVCC), an end-host shim-layer that enforces weighted bandwidth sharing among competing flows. Trace-driven NS3 simulations demonstrate that Uranus closely approximates the congestion-proportionality and is able to improve the proportional fairness by 31.49% compared to the state-of-the-art mechanisms. The results also prove Uranus’s capability of intra-slice scheduling optimization. Moreover, Uranus’s throughput in Clos fabrics outperforms the state-of-the-art mechanisms by 10%.

Fog radio access network (Fog-RAN), which pushes caching and computing capabilities to the network edge, is capable of efficiently delivering content to users by using carefully designed caching placement and content replacement algorithms. In this paper, the transmission scheme design and coding parameter optimization will be considered for coded caching in FogRAN, where the reliability of content delivery, i.e., content outage probability, is used as the performance metric. The problem will be formulated as a complicated multi-objective probabilistic combinatorial optimization. A novel maximum b-matching approach will then be proposed to obtain the Pareto optimal solution with fairness constraint. Based on the fast message passing approach, a distributed algorithm with a low memory usage of O(M + N) is also proposed, where M is the number of users and N is the number of fog access points (Fog-APs). Although it is usually very difficult to derive the closed-form formulas for the optimal solution, the approximation formulas of the content outage probability will also be obtained as a function of coding parameters. The asymptotic optimal coding parameters can then be obtained by defining and deriving the outage exponent region and diversity-multiplexing region. Simulation results will illustrate the accuracy of the theoretical derivations, and verify the outage performance of the proposed approach. Therefore, this paper not only proposes a practical distributed Fog-AP selection algorithm for coded caching but also provides a systematic way to evaluate and optimize the performance of Fog-RANs.

Mobile cloud computing systems, or simply mobile clouds, have attracted tremendous attention because they allow mobile devices with limited computational resources to offload complex computations. However, due to the channel uncertainty and the complexity of a computation task, mobile computation offloading may suffer from poor outage performance that the offloaded task cannot be completed within the desired delay constraint. Thus, how to efficiently identify and overcome the outage bottleneck, which could be used to optimize resource allocation schemes and improve the system performance effectively is an open problem. In this paper, we shall develop a unified framework that minimizes the overall outage probability in various mobile computation offloading scenarios. More specifically, the outage bottleneck is defined and identified by adopting asymptotic analysis, without any need of the accurate outage probabilities in both transmissions and computations. To overcome the outage bottleneck, resource pairing, matching, and allocation policies are investigated. Both theoretical analysis and numerical results show that the outage bottleneck relies on not only the availability of spectrum and computation resources but also the probability distributions of computation complexities of the computation tasks.

Though the classical packet-level queueing theory, which treats each packet as an entry, has achieved a great success in network analysis, it can be inaccurate when directly applied to long-term evolution (LTE) networks. This is because arriving packets could be broken down at the LTE base station server across adjacent transmission time intervals (TTIs), which are the smallest scheduling time units in LTE networks. In this paper, we first propose an innovative bit-level queueing theory to address the challenges in performance analysis of LTE networks. To consider the randomness in packet arrivals and packet lengths, we propose two representative compound network traffic models-Poisson-Exponential (PE) and Zeta-Pareto (ZP) models-to approximate light-tailed and heavy-tailed network traffic, respectively. PE models are suitable for conventional voice and low-speed services, while ZP models, which compound power-law distributions, describe complicated high-speed network applications. We derive tail asymptotics for the distributions of the number of bit arrivals in one TTI and the corresponding waiting time. Based on the results in bit-level queueing theory, we present engineering applications that take into account user experience, including estimating the user experience rate (UER), the busy UER and hourly traffic volume. The theoretical results are then validated through extensive simulations. Our novel traffic estimation approach has been adopted by Wireless Product Line at Huawei for network capacity planning and also projected to International Telecommunication Union (ITU) to compose 5G standards.

To exploit the potential of content caching and device-to-device (D2D) communication, we propose a user-centric joint device caching and channel assignment (DCA) policy to facilitate content exchanges between user equipments (UEs). The objective is to minimize the average content delivery delay by effectively leveraging D2D communications using as few channels as possible, subject to the UEs' cache capacities and availability of D2D links. This joint design problem is formulated as a nonlinear combinatorial optimization problem which is NP-hard. We first analyze the optimal DCA policy in two special cases. Then, a low-complexity heuristic algorithm is proposed for general cases which alternatively performs greedy device caching and graphcoloring based channel allocating. Simulation results show that the proposed DCA policy can reduce the average content delivery delay by more than half, in contrast to baseline schemes with locally popular caching.

ECN is a powerful tool that can achieve low latency and high throughput simultaneously. Support ECN for multiqueue scenarios is an industry trend in datacenter networks. However, ECN schemes developed for per-port marking cannot be applied directly to the multi-queue scenarios. It hurts at least one metric among latency, throughput, and the scheduling policy. State-of-the-art multi-queue ECN marking schemes each has its own limitations. In this paper, we present per-Port Marking with Selective Blindness (PMSB). The intuition is that: if a flow is found to be a victim of per-port marking, we can either revoke the marking or cancel the flow back-off even if its packets qualify the per-port threshold (i.e., selective blindness). By breaking the fixed causal relationship between ECN marking and flow backoff, flows from un-congested queues can be protected. We evaluate PMSB with large-scale NS-3 simulations. Our results demonstrate that PMSB can preserve a given scheduling policy. Compared with the current practice, PMSB can reduce the average/99% completion time for small flows by 64.49%/72.89% respectively while delivering a slightly better performance for large flows.

Fog Computing which extends the cloud computing paradigm to the edge of the network provides great opportunities for applications with stringent latency requirement. How to allocate the limited caching resources of Fog Nodes (FNs)influences the performance of the fog computing system. In contrast to previous works on caching resource allocation with users' utility as the only consideration, we propose OptCaching which jointly optimize the utility of all network participants including Content Provider (CP), Internet Service Provider (ISP)and users. With caching incentive introduced, utility functions of these three roles are defined. Our joint utility optimization caching scheme is conducted in two stages combining global and local decision making. Firstly, interaction between CP and ISP is modeled as a non-cooperative hierarchy Stackelberg game to make decision on incentive caching prices and global caching amount aiming at optimizing the utility of all network participants. Secondly, for the purpose of further optimizing the utility of users, a belief propagation based cache placement algorithm which utilizes global caching amount constraint and local information is conducted by FNs to reduce users' average download delay. Mathematical analysis and simulation results show that the utility of CP, ISP and users are jointly optimized at Stackelberg equilibrium. The utility of users is further optimized by belief propagation based cache placement algorithm with users' average download delay reduced by 33.7% compared with global popularity based caching strategy.

Wireless cloud computing system with computation offloading has attracted much attention due to the potential of alleviating the restrictions of limited resources in mobile devices. During the computation offloading, the steps of transmissions and computation need to be completed within the required time, otherwise the system will be in outage. Due to uncertainties of channel fading and computational complexities, such outage is the result of either transmission outage or computation outage. In this paper, a theoretical framework is proposed to analyze the outage of the wireless cloud computing system with multiple subcarriers and computation resources. Through theoretical analysis of the outage probability, the outage bottleneck can be identified. Numerical results have verified the theoretical analysis and concluded that the outage bottleneck depends not only on the distributions of complexities of tasks but also on the numbers of subcarriers and computation resources.

Vehicle-to-everything (V2X) communications, enabled by cellular device-to-device (D2D) links, have recently drawn much attention due to its potential to improve traffic safety, efficiency, and comfort. In this context, however, intracell interference combined with demanding latency and reliability requirements of safety vehicular users (V-UEs) are challenging issues. In this paper, we study a resource allocation problem among safety V-UEs, non-safety V-UEs, and conventional cellular UEs (C-UEs). Firstly, the resource allocation problem is formulated as a three-dimensional matching problem, where the objective is to maximize the total throughput of non-safety V-UEs on condition of satisfying the requirements on C-UEs and on safety V-UEs. Due to its NP-hardness, we then exploit hypergraph theory and propose a local search based approximation algorithm to solve it. Through simulation results, we show that the proposed algorithm outperforms the existing scheme in terms of both throughput performance and computational complexity.

Proactive pushing and caching has recently emerged as a promising technology to improve the quality of service in mobile networks. Given the fact that users' demand for content is largely driven by social networking, this paper combines the analysis of social networking with proactive pushing and caching by constructing a human-in-the-loop system model with a physical multicasting transmission. By taking social network structure, prediction and joint pushing and caching (JPC) into account, a closed-loop system is obtained, in which the input consists of arrivals of new content items, the control procedure is based on prediction and JPC, and the output is the cache-hit ratio (CHR). A prediction and JPC based adjustment algorithm is proposed to maximize the CHR of this system. It is shown that the prediction window, which refers to how far in the future predictions are made, and the prediction error have a significant impact on the performance of the system.

Internet of Things (IoT) is a promising technology to connect tremendous devices together, where the major challenges are that the available energy is limited and computing capability is low. In this paper, we propose an efficient IoT computing tasks offloading mechanism based on cooperative communication and mobile cloud computing (MCC) system. The problem will be formulated as a joint optimization problem of computation and radio resource allocation aiming to minimize the system energy consumption, under the constraints of latency and transmission power. We will first propose a joint iterative computation offloading and resource allocation algorithm to solve the non-convex optimization problem. To further reduce the computation complexity, we also propose a matching based sub- optimal algorithm to solve this problem. Simulation results demonstrate that the proposed iterative algorithm achieves the goal to substantially reduce energy consumption by offloading computation. Moreover, the sub-optimal algorithm significantly reduces the computation complexity with only a small portion of performance loss.

Spectrum database plays an increasingly important role in spectrum measurements and monitoring, which lays foundations for accurate and real-time spectrum sensing in future cognitive radio networks. A successful identification of the channel propagation model is of great importance to construct spectrum database so as to give an accurate picture of spectrum use in real-world environments. In this paper, based on the principle behind the voting-based online sequential extreme learning machine (VOS-ELM) and the Spark cloud computing platform, a novel parallel VOS-ELM (PVOS-ELM) algorithm will be proposed and implemented for real-time channel model identification in real-world propagation environment. The power measurement, kurtosis and skewness etc. will be used as features which are extracted from the received signal. Furthermore, the novel data parallel and task parallel processing schemes will be proposed to improve the computation efficiency of the proposed algorithm on Spark cloud computing platform. Extensive simulations and experiments with real-world data samples will be carried out. The experimental results illustrate that the proposed Spark based PVOS-ELM algorithm enjoys a significant accuracy performance improvement in channel identification and a much higher computation efficiency.

Sparse code multiple access (SCMA) is being considered as a promising multiple access solution for 5G systems. A distinguishing feature of SCMA is that it combines the procedures of bit to constellation symbol mapping and subsequent spreading using multidimensional codebooks differentiated by users. Such codebooks dominate the system implementation as a main source of not only performance gain but also design complexity. This letter presents a joint constellation with mapping matrix design for SCMA codebooks, which formulates the constellations optimization as a nonconvex quadratically constrained quadratic programming problem based on a set of well-constructed mapping matrices. We elaborately solve the problem to achieve outperformance over existing SCMA design in terms of bit error rate (BER). For improving practicality, an approximate approach is further proposed to reduce the complexity significantly with a limited BER loss.

With the tremendous development of data science, using unstructured documents to analyze marketing dynamics is attracting a great deal of attention. In this letter, we propose an iterative scheme to extract the new words, which is often a bottleneck for Chinese natural language processing (NLP) in financial markets analysis. In contrast to existing static features, the key novelty is the proposed dynamic features that characterize the similarity of context patterns. Via iteration, distinguishable seed context patterns are extracted. Tested on a 203 MB corpus, 19 291 words representing emerging industries, entities, projects, and products were extracted with a precision of 89.8% and recall of 88.9%, which outperforms most competitor methods.

In massive network data analysis, especially online social network analysis, the complete network dataset is often difficult to obtain due to the huge cost in collecting and storing data. In order to recover missing data from sampled networks, we consider the network completion problem, which has attracted much attention from both academia and industry. In this letter, the network completion problem of sparse networks is solved by a proposed discrete-constrained nuclear-norm minimization (DNM) method. It is based on the sparsity of the number of nonzero elements and singular values, which leads to an optimization problem. Since the problem is NP-hard, relaxation and adjustment are applied to make it convex. The DNM method can be applied in many practical networks, as many real-world complex networks are sparse. The simulation results on real-world online social networks and artificially generated random networks indicate that the proposed DNM method outperforms many existing network completion methods.

5G cellular network may have the features of smaller cell size, much denser resource deployment and almost random geometric pattern, resulted from diminishing spectrum resource and rapidly increasing diversified communication demands. The random small-cell network results in much more complicated interference scenarios, which cannot be formulated as the well-accepted hexagonal grid model. Therefore, how to model the interference pattern, and how to reuse the scarce spectrum resource to achieve the optimal performance for 5G cellular networks have attracted much attention from both academia and industry. In this paper, a brand new approach, referred to as the matrix graph, is proposed. This approach is robust to interference and random topology. Based on the derived properties of the matrix graph, an asymptotic optimal algorithm with low complexity is obtained to address the spectrum allocation problem with interference constraints, which is known as an NP-hard problem. The proposed algorithm yields a fundamental tradeoff between spectrum reuse ratio and computational complexity. Simulation results also support the theoretical performance gains. As a result, the proposed matrix graph approach is specifically useful for characterizing the next-generation cellular networks.

The fundamental idea of network decomposition is to break a large-scale network into smaller parts such that the subnetworks can operate in parallel, each with a much lower dimensionality. For large-scale wireless networks, the cellular structure is based on the idea of network decomposition, where the network is decomposed into multiple subnetworks, i.e., cells, according to the coverage of each base-station (BS). Such a decomposition scheme, nevertheless, leads to strong interference among subnetworks, which becomes increasingly significant as the density of BSs grows. For the next-generation cellular network, where a massive amount of BSs need to be deployed to meet the ever-increasing demand of high data rate, it is of paramount importance to develop efficient network decomposition schemes to replace the current cellular structure. How to build such a decomposition framework, unfortunately, has remained largely unknown. This paper aims to establish a network decomposition theory for large-scale wireless networks from a graph-theoretic point of view. Specifically, we start from a novel bipartite graph representation of an infrastructure-based wireless network and show that in general the optimal network decomposition can be formulated as a graph partitioning problem. For demonstration, we focus on maximizing the number of subgraphs for a given cut ratio constraint and propose a binary search based spectral relaxation (BSSR) algorithm to solve it in two loops. The performance of the proposed BSSR algorithm is further examined and compared with the current cellular structure and BS clustering in various scenarios. Significant gains are shown to be achieved by the proposed BSSR algorithm, which corroborates that the optimal network decomposition of next-generation cellular networks should be performed based on a bipartite graph, where the geographical information of BSs and users are both included.

To deal with the rapid growth of high-speed and/or ultra-low latency data traffic for massive mobile users, fog radio access networks (Fog-RANs) have emerged as a promising architecture for next-generation wireless networks. In Fog-RANs, the edge nodes and user terminals possess storage, computation and communication functionalities to various degrees, which provide high flexibility for network operation, i.e., from fully centralized to fully distributed operation. In this paper, we study the cache placement problem in Fog-RANs, by taking into account flexible physical-layer transmission schemes and diverse content preferences of different users. We develop both centralized and distributed transmission aware cache placement strategies to minimize users' average download delay subject to the storage capacity constraints. In the centralized mode, the cache placement problem is transformed into a matroid constrained submodular maximization problem, and an approximation algorithm is proposed to find a solution within a constant factor to the optimum. In the distributed mode, a belief propagation-based distributed algorithm is proposed to provide a suboptimal solution, with iterative updates at each BS based on locally collected information. Simulation results show that by exploiting caching and cooperation gains, the proposed transmission aware caching algorithms can greatly reduce the users' average download delay.

The cloud radio access network (Cloud-RAN) based mobile cloud computing (MCC) system offers a promising solution to offload computation-intensive tasks from battery and computation capability limited mobile devices to a cloud service provider via wireless transmission, thereby reducing the energy consumption and latency for mobile devices. However, the extra energy and latency caused by wireless transmission for offloading may offset the gains of computation offloading. In this paper, we focus on minimizing the network energy consumption while satisfying the delay requirements by jointly optimizing the communication resources (i.e., uplink and downlink beamforming design), computation resources (i.e., computation capability) and offloading decision (i.e., offload or not offload). Unfortunately, this problem turns out to be an NP-hard non-convex mixed integer non-linear programming (MINLP) problem. To resolve this challenge, the principle of uplink and downlink duality is exploited to aid efficient beamforming design. Furthermore, an effective iterative algorithm with polynomial time complexity is proposed in a holistic way to guide the offloading decision. Simulation results will demonstrate that the proposed iterative algorithm achieves near-optimal energy efficiency in Cloud-RAN based mobile cloud computing system.

Cooperative communication is a promising technique, which can greatly improve the performance and extend the coverage of cellular networks. In this paper, the resource allocation problem is investigated for multi-carrier amplify-and-forward (AF) relay assisted multi-access networks with multiple users and subcarriers. The joint relay selection and subcarrier allocation problem is formulated as a combinatorial optimization problem so as to minimize the outage probability with fairness assurance. To solve this problem, we propose a constraint maximum H-matching approach, which is based on a correlated random bipartite graph (RBG) formulation. By analyzing the properties of H-matching method on correlated RBG, the tight approximation of outage probability will be obtained in closed-form formulas. By deriving the diversity-multiplexing tradeoff, it is shown that the proposed approach achieves the same frequency and cooperative diversity as if the network has only one user, while all of the users fairly share the multiplexing gain at the same time. The proposed H-matching method also enjoys a sublinear computation complexity for parallel implementations. Numerical results verified the theoretical derivations and optimality of the proposed approach.

Caching popular contents at the edge of wireless networks has recently emerged as a promising technology to improve the quality of service for mobile users, while balancing the peak-to-average transmissions over backhaul links. In contrast to existing works, where a central coordinator is required to design the cache placement strategy, we consider a distributed caching problem which is highly relevant in dense network settings. In the considered scenario, each Base Station (BS) has a cache storage of finite capacity, and each user will be served by one or multiple BSs depending on the employed transmission scheme. A belief propagation based distributed algorithm is proposed to solve the cache placement problem, where the parallel computations are performed by individual BSs based on limited local information and very few messages passed between neighboring BSs. Thus, no central coordinator is required to collect the information of the whole network, which significantly saves signaling overhead. Simulation results show that the proposed low-complexity distributed algorithm can greatly reduce the average download delay by collaborative caching and transmissions.

The cloud radio access network (Cloud-RAN) has recently been proposed as one of the cost-effective and energy-efficient techniques for 5G wireless networks. By moving the signal processing functionality to a single baseband unit (BBU) pool, centralized signal processing and resource allocation are enabled in cloud-RAN, thereby providing the promise of improving the energy efficiency via effective network adaptation and interference management. In this paper, we propose a holistic sparse optimization framework to design green cloud-RAN by taking into consideration the power consumption of the fronthaul links, multicast services, as well as user admission control. Specifically, we first identify the sparsity structures in the solutions of both the network power minimization and user admission control problems, which call for adaptive remote radio head (RRH) selection and user admission. However, finding the optimal sparsity structures turns out to be NP-hard, with the coupled challenges of the ℓ0-norm-based objective functions and the nonconvex quadratic QoS constraints due to multicast beamforming. In contrast to the previous works on convex but nonsmooth sparsity inducing approaches, e.g., the group sparse beamforming algorithm based on the mixed ℓ1/ℓ2-norm relaxation, we adopt the nonconvex but smoothed ℓp-minimization (02algorithm is developed, which will converge to a Karush-Kuhn-Tucker (KKT) point of the relaxed smoothed ℓp-minimization problem from the SDR technique. We illustrate the effectiveness of the proposed algorithms with extensive simulations for network power minimization and user admission control in multicast cloud-RAN.

In this paper, energy-efficient secure communications via untrusted two-way relaying are investigated considering physical layer security to prevent the relays from intercepting the confidential information of users. The performance metric of secure energy efficiency (EE), defined as the ratio of the secrecy sum rate to the total power consumption, is maximized by jointly optimizing power allocation for all nodes, with the constraints of the maximum allowed power and the minimum target secrecy rate. To deal with this intractable nonconvex optimization problem, some optimization methods termed as fractional programming, alternate optimization, penalty function method, and difference of convex functions programming, are jointly applied to address a solution scheme with comparatively lower complexity. With these above-mentioned optimization methods, the primal problem is transformed into simple subproblems hierarchically so as to adopt the corresponding optimization algorithm. By simulations, the achievable secure EE, the secrecy sum rate and the total transmission power of the proposed scheme are compared with those of secrecy sum rate maximization. It is demonstrated that the proposed scheme can improve secure EE remarkably yet at the cost of secrecy sum rate loss. This fact also reveals the inherent tradeoff between energy and security.

Device-to-device (D2D) communication has great potential to improve spectrum efficiency and offload traffic for cellular networks. In this paper, we focus on a multiflow two-way D2D network with decode-and-forward (DF) relays, coexisting with OFDMA cellular network. The spectrum sharing and relay selection are considered to minimize the outage probability of the device in D2D networks. The induced problem is a complicated probabilistic integral programming. A novel weighted random bipartite graph (WRBG)-based minimum weight maximum matching (MWMM) approach will be proposed in this paper. To offload not only the traffic but also the signaling and computation overhead, the improved min-sum algorithm will be applied to find the MWMM in the distributed manner with only polynomial complexity. The proposed approach enjoys an advantage that the close-form approximation formulas for optimal outage probability and diversity-multiplexing tradeoff can be derived by analyzing the properties of MWMM on WRBG. Both the theoretical derivations and simulation results will illustrate that the proposed approach for multiflow two-way D2D networks achieves the same performance as single-flow two-way D2D systems. Therefore, the distributed WRBG matching approach yields not only a practical distributed algorithm, but also a simple and elegant theoretical framework for multiflow two-way D2D networks.

For transmitting data in a secret and energy-efficient manner in collaborative amplify-and-forward relay networks, the secure energy efficiency (EE) defined as the secret bits transferred with unit energy is maximized to satisfy each node power constraint and target secrecy rate requirement, based on physical security framework. The secure EE is maximized by joint source and relay power allocation, which is a nonconvex optimization problem. To cope with this difficulty, a solution scheme and corresponding algorithms are developed by jointly applying fractional programming, exact penalty, alternate search, and difference of convex functions programming. The key idea of the scheme is to convert the primal problem into simple subproblems step by step, such that related methods are adopted. It is verified that, compared with secrecy rate maximization, the proposed scheme improves the secure EE significantly yet with a certain loss of the secrecy rate due to the tradeoff between secure EE and secrecy rate. Furthermore, the proposed scheme achieves higher secure EE and secrecy rate than total transmission power minimization does, while with a certain increase of power consumption. These results indicate that a reasonable balance among secure EE, secrecy rate, and power consumption can be reached by the proposed scheme.

The Cloud radio access network (Cloud-RAN) has great potentials to improve energy efficiency and increase capacity of wireless networks. In this paper, we investigate multicast beamforming design for network power minimization of Cloud-RAN, which is shown to be a highly intractable non-convex mixed integer non-linear programming problem. To provide an efficient solution to this highly complicated problem, we propose a three-stage algorithm based on the group-sparsity inducing norm, which minimizes network power by coordinated multicast beamforming and adaptively selecting active remote radio heads (RRHs). In particular, a novel quadratic variational weighted ℓ1=ℓ2-norm aided alternating algorithm is proposed to exploit the group-sparsity structure of the beamforming vector, thereby guiding the active RRH set selection. Given the selected RRH set, multicast beamforming is performed to minimize the network power consumption. Furthermore, to enhance the computation efficiency upon utilizing the shared computing resources in the cloud center, we employ the alternating direction method of multipliers (ADMM) algorithm to solve the resulting semidefinite programming problems in parallel. Extensive simulation results will demonstrate the effectiveness of the proposed multicast group sparse beamforming algorithm.

The security requirements of data transmission over wireless networks are energy-limited in many situations. In this paper, the secure energy efficiency (EE), is defined as the ratio of the secrecy rate to the total power, and is investigated in a systematic way considering a decode-and-forward (DF) relay network with a potential eavesdropper. We maximize the secure EE subject to the individual power constraint and the minimum decoding rate constraint of the relay. To deal with the nonconvexity of the formulated problem, a fractional programming approach embedded with DC (difference of convex functions) programming is proposed to solve the problem by two-layer iterations. The key point of the proposed algorithm is to translate the primal problem into a series of convex subproblems, which can be solved by convex programming. It is verified by simulation that the proposed algorithm achieves much better secure EE than the conventional secrecy rate maximization yet with a minor performance loss measured by average secrecy rate or secrecy outage probability.

In this paper, the secure green communication over amplify-and-forward (AF) relaying channels is investigated by using the metric of secure energy efficiency (EE), defined as the number of bits securely delivered per unit energy consumption. We maximize the secure EE with the given maximum power and the minimum secrecy rate requirements. The difficulty of the problem comes from the nonconvexity of both the objective function and the secrecy rate constraint. Therefore, a suboptimal solution scheme, based on fractional programming, dual decomposition, and DC (difference of convex functions) programming, is addressed to solve this problem iteratively. The proposed solution scheme composed of three-layer iterations transforms the primal problem into easier subproblems at each iterative layer, such that the resulting subproblems can be solved by the corresponding optimization methods mentioned above. The simulation results demonstrate that the secure EE of the proposed scheme is superior than that obtained by the conventional schemes with a small decrease of the average secrecy rate.

In this paper, we investigate the energy efficiency (EE) maximization in amplify-and-forward (AF) MIMO two-way relay channel (TWRC) combined with relay antenna selection (AS). An iterative energy efficient AS algorithm is proposed to jointly select the active receive and transmit antennas at the relay, as well as optimize the transmission power of the sources and relay. Specifically, the AS at each iteration is based on a derived closed-form iterative equation of EE, which guides us to select a pair of receive and transmit relay antennas that achieves the largest increment of EE under an initial transmission power. After the AS of each iteration, a power adaptation is immediately adopted where we calculate the optimal transmission power using fractional programming and set it as the initial one for the AS of the next iteration. Simulation results show that our proposed scheme achieves nearly the same performance of exhaustive search while with significantly reduced complexity. Moreover, it is capable of simultaneously improving EE and reducing the transmission power.

In this paper, we raise the concern on energy-efficient secure communication over a decode-and-forward relay network with potential eavesdroppers. Our objective is maximizing the secure energy efficiency (EE), which is defined as the ratio of secrecy rate to total power, subject to the given individual power, relay decoding rate, and target secrecy rate constraints. The problem is formulated as a unified mixed integer nonlinear optimization adapting to different assumptions of channel state information (CSI). To deal with this combinatorial optimization, a suboptimal solution scheme is developed upon some mathematical methods as decoupling of mixed integer programming, fractional programming, dual decomposition, and difference of convex functions programming. The core of the scheme is to transform the primal problem into simple subproblems step by step, and then convex programming can be exploited finally. The proposed scheme for the case with statistical eavesdropper's CSI, may be conditionally extended to the scenario with full CSI in which a local optimal solution may be obtained in certain cases. Finally, the performance and achievable secure EE of the proposed algorithm are demonstrated by simulations where the tradeoff between secure EE and secrecy rate is also revealed.

With tremendous power shortage and raising voice of greener energy usage, energy efficiency (EE) maximization in MIMO systems has received much attention in next generation wireless communications. Within recent years, there has been a lot of great work on power allocation and antenna selection in order to maximize EE under holistic power models. However, it is not a trivial work to derive a closed-form solution for energy efficiency optimization. In this paper, an asymptotic approach is adopted to obtain the analytical solutions of the EE optimal transmission schemes, as well as its performance limits. More specifically, we are interested in the capacity achieving dirty paper coding (DPC) and practical low-complexity zeroforcing beamforming (ZFBF), where EE is optimized with and without total power constraint. Closed-form formulas are given to determine the EE optimal number of antennas and transmit power. The proposed asymptotic analysis matches well with the numerical results when the number of users is moderately large, i.e., over 30.

The green communications, which focus on improving the energy efficiency, have attracted much attention from both academia and industry recently. In this paper, the tradeoff between outage probability and energy efficiency will be addressed for multi-flow cooperative communication systems with taking energy budget and devices energy consumption into consideration. The proposed approach will first formulate the multi-flow cooperative communication system as a weighted random bipartite graph (WRBG) model. The minimum weighted maximum matching (MWMM) method will then be proposed to select a relay for each source-destination (s-d) pair in order to minimize the outage probability and maximize the average energy efficiency simultaneously. By analyzing the properties of every sample of the WRBG model, the closed-form formulas for the outage probability and average energy efficiency will then be obtained. Therefore, based on the derived tradeoff, the outage probability and average energy efficiency can be balanced by adjusting the energy budgets and transmission rate according to the system requirement. Moreover, the proposed MWMM method also enjoys an advantage of the log-polynomial computation complexity for parallel implementations.

With the development of next generation mobile communications, the underlay coexistence problem of the OFDMA based Secondary System(SS) with LTE-A systems becomes more and more important, which yet has not been studied in a systematic way. In contrast to other Primary Systems(PS), the LTE-A system puts high demands on the low complexity of the coexistence strategies. This paper focuses on the resource allocation and interference mitigation issues in the aforementioned scenario, whose objective is to protect the spectrum utilization priority of PS as well as utilize secondary resource efficiently. The difficulty lies in the fact that even the subproblem, or power allocation with interference, is NP-Hard. Therefore, this paper will propose a two-phase resource allocation algorithm using maximum weighted Matching in the subcarrier allocation phase and interference Quantizing in the power allocation phase, referred to as the MQ algorithm. As presented in this paper, the MQ algorithm enjoys the advantage of polynomial complexity of O(KJ3+ LKJ), where K, J and L denote the number of SSs, subcarriers and quantizing steps, respectively. The simulation results will show that the proposed MQ algorithm is capable of achieving near optimal system and user throughputs, which are close to the exhaustive searching algorithm.

As the growth of wireless communications is accompanied by increased energy consumption, energy-efficient communication is becoming imperative. This paper will discuss the energy efficiency of MIMO systems with antenna selection. The optimal method for the maximization of energy efficiency is exhaustive search. To address the problem, an iterative algorithm which includes the transmit antenna selection and power adaptation is proposed. It is based on the iterative property of the energy efficiency, which is derived in this paper. This property guides us to select the antenna that achieves the largest energy efficiency increment at each step. There is also a power adaptation for each step where we calculate the optimal transmission power and then set it as the initial one for the next step. Moreover, one asymptotic property exists in the proposed algorithm, which states that the antenna selection and power adaptation can be decoupled in high and low SNR regimes. This fact reduces the complexity further and enables us to achieve the optimal performance with a greater probability. Simulation results show that the proposed algorithm achieves near-optimal performance in all the SNR regimes and has a remarkable gain over the no selection scheme in the energy efficiency and transmission power.

The channel state information at the transmitter side (CSIT) is playing a more and more important role in the design of OFDM/OFDMA communication systems. Unfortunately, it is not trivial to conduct a performance analysis of OFDM systems with partial CSIT. Using the saddle-point approximation method, this paper will develop an analytical design and performance analysis framework for OFDM channels with 1 bit CSIT, which we shall refer to as the conditional outage exponent. The proposed framework will then allow us to present the fundamental relationship among the outage probability, transmission rate, SNR, outage capacity, delay-limited capacity, ergodic capacity, diversity-multiplexing tradeoff (DMT), finite-SNR DMT, and the number of diversity branches. It is surprising that the outage performance with 1 bit CSIT (conditional outage exponent) is worse than the corresponding one without CSIT (non-conditional outage exponent) in most cases. This counter-intuitive phenomenon occurs because the observation of the channel at the transmitter side will result in a state space collapse of the channel gains, i.e., from the prior probability space to the posterior probability space. As a result, the conditional outage exponent based framework can be easily used to design and evaluate the performance of existing and upcoming OFDM/OFDMA multichannel systems with 1 bit CSIT.

The parallel fading channel, which consists of finite number of subchannels, is very important, because it can be used to formulate many practical communication systems. The outage probability, on the other hand, is widely used to analyze the relationship among the communication efficiency, reliability, signal-to-noise ratio (SNR), and channel fading. To the best of our knowledge, the previous works only studied the asymptotic outage performance of the parallel fading channels which are only valid for a large number of subchannels or high SNRs. In this paper, a unified performance metric, which we shall refer to as the outage exponent, will be proposed. Our approach is mainly based on the large deviations theory and Meijer'sG-function. It is shown that the proposed outage exponent is not only an accurate estimation of the outage probability for any number of subchannels, any SNR, and any target transmission rate, but also provides an easy way to compute the outage capacity, finite-SNR diversity-multiplexing tradeoff, and SNR gain. The asymptotic performance metrics, such as the delay-limited capacity, ergodic capacity, and diversity-multiplexing tradeoff can be directly obtained by letting the number of subchannels or SNR tend to infinity. Similar to Gallager's error exponent, a reliable function for parallel fading channels, which illustrates a fundamental relationship between the transmission reliability and efficiency, can also be defined from the outage exponent. Therefore, the proposed outage exponent provides a complete and comprehensive performance measure for parallel fading channels.

In this paper, a random combinatorial optimization approach, which we shall refer to as random bipartite graph (RBG) based maximum matching, will be proposed to investigate and solve the joint relay selection and subchannel allocation problem in cooperative networks. By studying the properties of the maximum matching on RBG, the outage probability and diversity-multiplexing tradeoff of the proposed RBG matching method will be obtained. It will then be demonstrated that the outage probability and diversity-multiplexing tradeoff of the RBG matching method for cooperative communication systems with multiple source-destination pairs is the same as that of relay systems with only one source and one destination, i.e., d(r) = N (K + 1)(1 - 2r), where N is the number of subchannels, and K is the number of relay nodes. In addition, it will be shown that the proposed algorithm for maximum matching enjoys a sublinear computation complexity O(N2/3). Simulation results will illustrate the potential of the proposed RBG matching method as well as verify the theoretical derivations.

Recent works have shown that cooperative diversity can be achieved by using relay selection (RS), distributed space-time coding (DSTC), and distributed beam-forming (DBF) in narrow-band decode-and-forward (DF) cooperative networks with one source-and-destination (s-d) pair. However, the joint resource allocation for broadband DF cooperative networks with multiple s-d flows has not received much attention yet. In this paper, a random hypergraph based unified matching framework is proposed, under which five feasible types of multi-flow DF cooperative networks will be considered. In each type, the maximum matching method will be applied to RS, DSTC, and DBF schemes so as to achieve the optimal channel allocation and relay selection with fairness assurance. By analyzing the properties of maximum matching, the outage probability of each s-d pair after resource allocation will be obtained. The results of diversity-multiplexing tradeoff will show that the proposed framework is capable of achieving the full frequency diversity and cooperative diversity for each s-d pair simultaneously, while the frequency multiplexing is equally shared. Based on the unified framework, the random rotation based parallel Hopcroft-Karp (R2PHK) algorithm will then be designed, which can work in each destination node independently, and shall enjoy a poly-logarithmic complexity O(log2loN), where N is the number of channels and lois a constant.

This paper introduces a new class of rate less forward error correction codes named semi-random Kite (SR-Kite) codes, which can be described by a sparse semi-random parity-check matrix in systematic form. SR-Kite codes have not only rate less property, but also low error floors. We present a simulation-based greedy optimization algorithm to design the degree distribution of SR-Kite codes for independent Rayleigh fading channels. The performances of SR-Kite codes under maximum likelihood decoding are analyzed for both AWGN and independent Rayleigh fading channels via union bound. Both the analysis and simulation results show that the proposed codes perform well over AWGN and fading channels within a wide range of signal-to-noise-ratios.

Analog network coding is a promising technique which can greatly improve the transmission efficiency of wireless communications. In two-way relay systems with multiple subchannels, multiple user pairs and multiple relays, however, the optimal joint relay selection and subchannel allocation problem has not been studied in a systematic way. In this paper, a random combinatorial optimization approach, referred to as the weighted random bipartite graph (WRBG) based minimum weighted matching (MWM) method, will be proposed to solve this problem. By analyzing the properties of the MWM on WRBG, we shall derive the outage probability and diversity-multiplexing tradeoff of each user after relay selection and channel allocation. Theoretical results will demonstrate that the outage probability, cooperative diversity, and frequency diversity of the proposed WRBG based MWM method for multi-user two-way relay systems is the same as that of two-way relay systems with only one user pair. The proposed algorithm for MWM also enjoys a low computation complexity of O(log2N) for parallel implementations, where N is the number of subchannels. Simulation results will illustrate the potential of the proposed method and also verify the theoretical derivations.

In cognitive radio networks (CRNs), dynamic spectrum access has been demonstrated as an effective way to improve the spectrum utilization. Spectrum holes can be exploited not only in certain time slots or frequency bands, but also at particular locations. In relay assisted CRNs, one relay at a certain location can help to identify and provide different spectrum holes over multiple channels. In this paper, a multi-dimensional combinatorial optimization problem is formulated for joint relay selection and channel allocation. We propose a weighted bipartite graph model and a minimum weighted assignment approach to efficiently get the optimal solution of the considered problem. Simulation results show that by applying this approach, spectrum efficiency, relay selection diversity and power efficiency can be improved simultaneously for the cognitive users. Besides, only the statistical channel state information is needed and the allocation results can be computed efficiently by using the proposed approach.

Relay selection has been shown to be a practical and effective way to achieve cooperative diversity. In wide-band OFDM cooperative communication systems with multiple source and destination nodes, however, the best relay selection and subchannel allocation has not been studied in a systematic way. In this paper, a random combinatorial optimization approach, referred to as the random bipartite graph based maximum matching (RBG matching), will be proposed to solve this problem. By applying the method of Euler beta function and generalized hypergeometric function, we will first derive a new closed-form outage probability for the best relay selection in the decode-and-forward (DF) scheme. Based on this result and the properties of the maximum matching on RBG, the outage probability and diversity-multiplexing tradeoff of the proposed RBG matching method will also be derived. As a result, we will demonstrate that the outage probability and the cooperative and frequency diversity-multiplexing tradeoff of the RBG matching method for cooperative communication systems with multiple source-destination pairs is the same as that of relay systems with only one source and one destination. Besides, the proposed algorithm for maximum matching also enjoys a sublinear computation complexity O(N2/3), where N is the number of subchannels. Simulation results will illustrate the potential of the proposed RBG matching method, and also verify the theoretical derivations.

Due to the potential of enhancing traffic safety, protecting environment, and enabling new applications, vehicular communications, especially vehicle-to-vehicle (V2V) communications, has recently been receiving much attention. Because of both safety and non-safety real-time applications, V2V communications has QoS requirements on rate, latency, and reliability. How to appropriately design channel allocation is therefore a key MAC/PHY layer issue in vehicular communications. The QoS requirements of real-time V2V communications can be met by achieving a low outage probability and high outage capacity. In this paper, we first formulate the subchannel allocation in V2V communications into a maximum matching problem on random bipartite graphs. A distributed shuffling based Hopcroft-Karp (DSHK) algorithm will then be proposed to solve this problem with a sub-linear complexity of O(N^{2/3}), where N is the number of subchannels. By studying the maximum matching generated by the DSHK algorithm on random bipartite graphs, the outage probabilities are derived in the high (two near vehicles) and low (two far away vehicles) SNR regimes, respectively. It is then demonstrated that the proposed method has a similar outage performance as the scenario of two communicating vehicles occupying N subchannels. By solving high degree algebraic equations, the outage capacity can be obtained to determine the maximum traffic rate given an outage probability constraint. It is also shown that the proposed scheme can take an advantage of small signaling overhead with only one-bit channel state information broadcasting for each subchannel.

OFDMA is a promising technique because it is capable of improving the transmission reliability and efficiency of multi-user wireless communications. However, previous works on the performance of OFDMA did not properly consider the fundamental relationship between multiplexing and diversity in OFDMA systems. As a comprehensive performance metric, the diversity-multiplexing tradeoff will be applied in this paper to evaluate the subcarrier allocation scheme. The OFDMA system will be formulated into a correlated random bipartite graph model, in which, whether the edges occur or not depends on the distribution of the channel fading. The \mathcal{H}-matching method, which is used to determine the maximum collection of vertex-disjoint copies of a fixed sub-graph \mathcal{H} contained in a given graph, will then be developed to address the optimal subcarrier allocation problem. Theoretical analysis will show that the proposed \mathcal{H}-matching method achieves the optimal outage performance at a given target multiplexing gain, which implies that the optimal diversity-multiplexing tradeoff can be achieved by only allocating subcarriers. Although the \mathcal{H}-matching problem is NP-complete, the proposed Random Rotation and Expansion based Hopcroft-Karp (R^2EHK) algorithm can still achieve the asymptotically optimal outage performance (i.e., optimal diversity-multiplexing tradeoff) with a sub-linear complexity. Furthermore, the channel state information needed is only one bit per subcarrier. Simulation results will verify the theoretical analysis and will show that the performance loss of the R^2EHK algorithm is negligible compared to the exhaustive search method. In addition, it is also shown that the R^2EHK algorithm has at least a 2 dB SNR gain compared to the interleaved subcarrier allocation with water-filling power allocation in IEEE 802.16 standards.

OFDM is playing a more and more important role in wireless communication systems. Unfortunately, it is not trivial to conduct a performance analysis of OFDM systems. Therefore, it is highly desired to develop an analytical design and performance analysis framework for OFDM channels. In this paper, we consider a unified performance metric for OFDM channels, which we shall refer to as outage exponent. The outage exponent, which is a special exponentially tight upper bound on outage probabilities, presents the fundamental relationship among the outage probability, target transmission rate, capacity of AWGN channel, SNR, and the number of diversity branches. The SNR gains of different coding schemes and the (finite-SNR and asymptotic) diversity-multiplexing tradeoff can be obtained from the outage exponent directly. In order to calculate the outage exponent for OFDM channels, we shall apply the large deviations theory, which will not only obtain an accurate estimation of the rate function, but also the coefficient of the exponential function. It is shown that the obtained outage exponent can allow the accurate estimation of the additional power required to decrease the outage probability by a specified value. Therefore, the outage exponent can be easily used to design and evaluate the performance of existing and upcoming OFDM systems.

The diversity-multiplexing tradeoff, which relates the transmission reliability and efficiency, is an important performance metric in wireless communications. So far only an asymptotic tradeoff result has been obtained for OFDM channels, and such result is only valid for high SNRs. To characterize the outage performance of OFDM systems in realistic SNRs, a finite-SNR framework that analyzes and describes the diversity-multiplexing tradeoff will be proposed in this paper. New upper and lower bounds on outage probabilities will be derived by using the method of integral round a contour, Laurent series, and the properties of Meijer's G-function and Gamma function. The finite-SNR diversity gain, as a function of the multiplexing gain and SNR, will also be computed by Meijer's G-function. We will then show that the finite-SNR diversity-multiplexing tradeoff will converge to the corresponding asymptotic results as SNR tends to infinity. As a result, the finite-SNR diversity-multiplexing tradeoff can be used to estimate the additional SNR required to decrease the outage probability by a specified amount for a given multiplexing gain.

OFDMA performs a fundamental role in wired/wireless communications. One of the key techniques in OFDMA is the resource allocation, which has been attaching much attention from both academia and industry. In this paper, we describe an innovative combinatorial method to study this problem. An OFDMA system will first be formulated into a random bipartite graph (RBG). To meet various system configurations and requirements, different matching methods will be proposed to perform subcarrier allocation. By studying the properties of RBG matching, we will obtain close-form formulas for outage probabilities so as to evaluate the performance of subcarrier allocation algorithms. It is then demonstrated that by exploiting the frequency diversity and multi-user diversity, the proposed matching method can minimize the outage probability with fairness assurance, and achieve the same diversity-multiplexing tradeoff as point-to-point OFDM systems. The induced subcarrier allocation algorithms also enjoy a sub-linear computation complexity of O(N2/3) for parallel implementations, where N is the number of subcarriers. Besides, the proposed RBG matching method only needs one-bit CSI feedback.

This paper considers the problem of optimal subcarrier allocation in OFDMA systems to achieve the minimum outage probability while guaranteeing fairness. The optimal subcarrier allocation algorithm and the maximum frequency diversity gain are both analyzed through the maximum matching method based on the random bipartite graph theory. Accordingly, a surprising result is found, which shows that the maximum frequency diversity gain in subcarrier-sharing OFDMA systems is the same as that in point-to-point OFDM systems that serve only one user by using N subcarriers. It is then demonstrated that this maximum frequency diversity gain can be achieved by a proposed Random Vertex Rotation based Hopcroft-Karp (RVRHK) algorithm with the time complexity of O(N2.5), where N is the number of subcarriers. Because the theoretical analysis and the RVRHK algorithm are both based on the maximum matching method, the maximum frequency diversity in OFDMA systems is referred to as the max-matching diversity in this paper.

OFDMA technology can significantly improve the transmission reliability and efficiency because of its inherent frequency diversity and frequency multiplexing. In our recent work [B.Bai,W.Chen, Z.Cao and K. B. Letaief (2009) ], we have derived the optimal diversity-multiplexing tradeoff for OFDMA systems under the assumption that each subcarrier occupies the entire coherence bandwidth. However in practical OFDMA systems, such as IEEE 802.16, there are many subcarriers in one coherence bandwidth, i.e., each coherence bandwidth is split into multiple subcarriers which brings the correlation of channel gains among these subcarriers. In this paper, we focus on the diversity-multiplexing tradeoff in this kind of OFDMA systems. First, a correlated random bipartite graph is adopted to formulate this problem. To resolve the user conflicts in subcarrier allocation, the maximum proper /-matching method is introduced to minimize the user outage probability with fairness assurance at given multiplexing gains. Based on this model, the optimal diversity-multiplexing tradeoff curve is obtained. Two extreme points are considered: (1) the full diversity gain is the number of coherence bands, i.e., the same as that in point-to-point OFDM systems; and (2) given a coherence bandwidth, the maximum multiplexing gain is equal to the frequency band equally allocated to each user. The random vertices rotation and extension based Hopcroft-Karp algorithm is then proposed as an optimal subcarrier allocation scheme, which can achieve the optimal tradeoff curve with the time complexity of O(S2.5), where S is the total number of subcarriers.

OFDMA is a potential technology that can flexibly allocate subcarriers while providing diversity gain to multiple users. In our recent work, we showed a surprising result that the maximum frequency diversity gain in OFDMA systems is equal to the number of independent subcarriers, i.e., the same as that in point-to-point OFDM systems despite of the fact that multiple users will share a common set of subcarriers. However, the diversity gain only characterizes the first-order outage performance in the high SNR regime, and the outage performance in the low SNR regime, which is very important in practice, is still an open problem. In this paper, we first formulate the subcarrier allocation problem in OFDMA systems as a random bipartite graph model. Then, a more precise outage probability is derived in the high SNR regime using a high-order analysis of the maximum matching on a random bipartite graph. An approximate outage probability in the low SNR regime is also obtained by studying the complement of a random bipartite graph. It is then demonstrated that the coefficient of the second-order term in the outage probability expression is zero except for the scenario of two users with two or three subcarriers.

OFDMA technology can significant improve the transmission reliability in multi-user communication systems because of its inherent frequency diversity. In a recent work, we have derived a surprising result which demonstrates that OFDMA systems can achieve a frequency diversity gain which is equal to the total number of independent subcarriers. In this paper, we shall show that the frequency diversity and the frequency multiplexing can be simultaneously achieved in OFDMA systems with a fundamental tradeoff between them. The random bipartite graph theory is used to model and analyze this diversity-multiplexing tradeoff problem. In particular, the maximum proper f-matching is introduced as a subcarrier allocation method which can minimize the user outage probability with fairness assurance given some multiplexing requirements. Similar to the Zheng-Tse tradeoff in MIMO systems, the optimal diversity-multiplexing tradeoff in multi-user OFDMA systems and it will be shown that its curve can be characterized by a piecewise linear function, despite of the user conflicts in the subcarrier allocation.

OFDM can provide frequency diversity gain for point-to-point communications over frequency-selective slow fading channel. Recent works show that OFDM may also form a flexible and efficient multiple access method, which is often referred to OFDMA. However, the user outage probability and the optimal frequency diversity gain in OFDMA systems are not known. In this paper, random bipartite graph is used to model and analyse the multi-user subcarrier allocation problem over frequency-selective slow fading channels. Our aim is to minimize the user outage probability as well as guarantee fairness by dynamic allocating various subcarrier to each user. An optimal subcarrier allocation algorithm, which we shall refer to as the Hungarian method with random vertices rotation, is introduced to achieve these objectives. A simple but effective approximation equation for user outage probability is then derived. It is shown that the optimal frequency diversity gain in OFDMA system is the same as the point-to-point OFDM system. In particular, the frequency diversity gain does not decay as the number of users increases.

In future wireless communication area, a key issue is the resource allocation and scheduling over wireless channel. Various aspects of this issue have been studied. However, few studies are on the QoS guaranteed uplink multiple traffic scheduling in multi-user wireless network. The scheduling problem is addressed in this paper. We consider the TDM-OFDMA uplink multi-access queuing system with four types of traffic. Each type has specific QoS requirements, such as minimum rate, maximum latency and maximum jitter. This QoS guaranteed cross-layer scheduling issue is modeled as a convex optimization problem. We also prove our scheduling method can guarantee the minimum rate, maximum latency and maximum jitter asymptotically, meanwhile it also minimizes the residual integrated workload. According to the solvability of this optimization problem, we define the scheduling algorithm stability region, and design a heuristic algorithm for connection admission control. The numerical results show the substantial performance of the proposed algorithm.

This paper introduces a convergence scheme for digital video/audio broadcasting (BCT) network and broadband wireless access (BWA) network. This convergence scheme supports the architecture based on both PMP topology and mesh topology. It works in the mode of time division with full spectrum multiplexing. Its frame length, BCT time-slot length and BWA time-slot length are adaptive to the arrival traffic and the whole network performance. Then the transmission and the process delay of the token and the performance of the network were analyzed. The main method used is based on M/G/l queue with vacation and time-limited service. The generating function and the mean values for the traffic load distribution in BCT BS and BWA BSs were given. Then it was simulated on the self-similar traffic background and compare with the fixed time-slot allocation scheme. This scheme can reduce the Hurst parameter in some extent.