This paper investigates coded distributed matrix-vector multiplications in the context of eavesdropping, denial-of-service attacks, and computational accuracy. It is demonstrated that the coding problem can be reduced to analog secret sharing. The first analog zigzag-decodable secret-sharing scheme is introduced, and its mutual information security is derived. The encoding and decoding algorithms are shown to be numerically stable, relying solely on shift and addition operations, in contrast to existing methods that require matrix inversions or the solution of linear systems. The proposed scheme achieves comparable security levels while exhibiting a significantly smaller relative computation error than the analog Shamir’s secret-sharing scheme. Additionally, it is shown to outperform the analog Shamir’s scheme in model training accuracy when applied to linear regression and logistic regression problems.

Surrogate models are commonly employed to reduce computational expenses when dealing with expensive objective optimization problems. This paper introduces a hybrid approach that combines the global exploration capabilities of the Covariance Matrix Adaption Evolution Strategy (CMA-ES) algorithm with the localized search strategy of the Broyden-Fletcher-Goldfarb-Shanno (BFGS) method, incorporating a new non-parametric surrogate model derived from the computational geometry structure of a convex hull in multiple dimensions. After running CMA-ES for some time, the populations of the two most recent iterations are collected to construct the convex approximation of the actual problem landscape. Since the population tends to converge in a landscape basin, the local landscape can be simulated using the constructed convex surrogate model. The accuracy of the convex surrogate model is subsequently validated by the historical solutions and used to determine the probability of switching to a local search. Given BFGS's superior performance in handling unimodal optimization problems, this hybrid approach demonstrates its potential to accelerate the convergence process in finding the global optimum. The experiment is conducted on test functions of the BBOB benchmark with a small evaluation budget, and the results after applying Mann-Whitney U tests confirm the superiority of this method compared to CMA-ES and another global-local framework APrMF.

With the development of wireless computing devices, extending distributed computing to wireless networks deserves a closer look. This paper considers distributed computing over unreliable and insecure device-to-device (D2D) networks, in which each device is not always available to perform computation. The process of distributed devices exchanging calculated results with each other is vulnerable to eavesdropping in wireless environments. To handle the unreliable devices, we adopt repetition codes to build a novel system that supports general computations, called$\rho $-replication system, where each device has$\rho -1$replicas with duplicate data. A coded computation scheme for the$\rho $-replication system is proposed, which not only achieves the minimum communication load of the system but also ensures weak security of wireless transmissions during data exchange. Furthermore, the replication nature of the system can be exploited for beamforming transmissions, naturally leading to the idea of energy optimization. Simulation results show that increasing$\rho $does not necessarily improve energy efficiency, as the benefit of increased beamforming gain may be outweighed by the drawback of heavier communication load.

This paper studies distributed storage for protecting the confidentiality of partial data in the presence of storage node failures. It is required that not only the original data can be reconstructed from the remaining surviving nodes, but also the data lost by a failed node can be repaired from as few nodes as possible. The minimum number of surviving nodes required to repair a failed node is called the repair degree. Inspired by the zigzag-decodable secret sharing scheme, we propose a new shift-add secret sharing scheme based on the XOR and bitwise-shift operations, in which confidential data is protected by using random keys generated from non-confidential data. The reliability and repairability of the proposed scheme are measured by the message loss probability and the maximum repair degree among all nodes, respectively, and then compared with three benchmark schemes. In contrast to conventional zigzag-decodable codes, the special structure of our proposed scheme allows the design of fast parallel algorithms for modern devices with multi-core processors, which have a linear speedup in decoding time compared with various versions of serial zigzag decoding. Experiments are implemented on a multi-core computer, and the empirical results on decoding time are consistent with our theoretical observations.

Federated learning is emerging as a new paradigm for joint training of machine learning models across multiple distributed devices. In contrast to many existing works that require a central server to facilitate the exchange of local parameters with a star topology, this work considers fully decentralized operations over a wireless ring network. By increasing the radio coverage of each device, the convergence time, as indicated by the second largest singular value of the weighted adjacency matrix, can be shortened, but the mutual interference will be increased causing larger communication delay. The tradeoff between learning and communication delays is characterized by mathematical analysis of the singular-value gap and by numerical experiments on a linear regression problem. By carefully designing the consensus coefficients of the learning algorithm, a network coding scheme is crafted to improve the entire tradeoff curve without consuming more radio resources. It points to a new direction of using network coding to speed up wireless decentralized learning.

A computing task can be distributed in an edge network and offloaded to multiple edge devices, called workers, to expedite the processing. The computing speeds of the workers, however, are usually unknown or time-varying. To identify the fast workers, a Bayesian approach based on Thompson sampling is used. The estimation of the computing speeds of the workers is formulated as a multi-armed bandit problem. While existing schemes allocate the same amount of computation work to each selected worker, this paper exploits the heterogeneous computing speeds of the workers and formulates the task allocation problem with the objective of minimizing the overall computing delay. A lower bound for the delay is obtained and is proved to be minimized by a greedy algorithm. Simulation results show that our scheme outperforms other benchmarks.

To leverage the computing power in an edge network, one can divide a machine learning task into several subtasks and assign the subtasks to several computing devices to complete. Under master-worker architecture, the master divides and distributes the data to several workers. In each iteration, the master asks the workers to compute some function of the local data stored in the workers. For example, in gradient-based learning, this function can be the partial gradient function. Since the workers have different computing resources, the speed of the distributed learning is hindered by some workers with long latency, called the stragglers. Gradient coding solves the problem of stragglers by allowing the master to recover the desired feedback information in the presence of s stragglers. If the total number of stragglers is n, the master can just wait for the n−s fastest workers. In this paper we consider the problem of data allocation so that the gradient vector can be approximated obtained by the master node with small error. A block repetition scheme is proved to be the optimal data allocation scheme if we want to minimize the average recovery error.

Recently, over-the-air computation is considered an efficient scheme for enormous data transmission in distributed learning and computing systems. Its performance is limited by the aggregation errors, which may be caused by noise, channel fading, and insufficient device power budgets. Inspired by gradient coding, this paper considers to leverage the computing abilities of the edge devices to reap a diversity gain and alleviate the effects of inadequate transmit power. The edge server divides the whole dataset into subsets and distributes them to edge devices by some data assignment scheme. The edge devices send the computation results simultaneously back to the edge server by over-the-air transmission. This paper jointly optimizes the data assignment and power allocation problems in over-the-air distributed learning systems to minimize the mean square error (MSE) of the aggregation data. Given the data assignment scheme, the power allocation problem is solved optimally by block coordinate descent (BCD) and grid search. Besides, some optimality conditions for data assignment are proved. Accordingly, a heuristic data assignment scheme is proposed. Numerical results show our proposed scheme outperforms existing works in terms of MSE and learning metrics.

This paper considers the design of heterogeneous multi-cloud systems for big data storage and computing in the presence of cloud collusion and failures. A fundamental concept of such a system is the secrecy capacity, which represents the maximum amount of information that can be stored for each unit of storage space under the requirements of secure distributed computing. A capacity-achieving code is designed for matrix multiplication, a computing subroutine widely used in machine learning applications. The code allows fast parallel decoding and unequal data allocation in the clouds. Such a flexibility leads naturally to the idea of optimizing data allocation to minimize the computing time. Given any feasible storage budget, the optimal solution is derived, characterizing explicitly the fundamental tradeoff between storage and computing. Furthermore, it is shown via majorization theory that the whole tradeoff curve improves if the cloud computing rates are more even. Experiments on Amazon EC2 clusters are conducted, corroborating our theoretical observations and the negligibility of decoding overhead.

Edge computing is the next-generation computing paradigm that brings the processing capability closer to the location where it is needed. 5G and beyond 5G aim to achieve substantial improvement for the performance of edge computing in terms of e.g. higher throughput and lower latency. Smart base stations are often attached with edge datacenters consisting of many edge servers equipped with computing and storage capabilities. These servers are used to execute offloaded tasks from edge equipment such as Internet of Things. It is important to have an efficient offloading algorithm that can guarantee specific service-level objectives (SLOs) by assigning tasks to appropriate edge servers. Traditional offloading schemes such as static and learning-based algorithms either have limited performance or result in high overhead for task assignment to servers. In this paper, we propose an efficient game-theoretical scheduling algorithm for offloaded tasks at edge datacenters. The core contribution of the algorithm is to design a public goods investment model for edge servers. Based on the model, we design a lightweight scheduling algorithm to reduce the average load of edge servers and enhance the stability of edge datacenter systems. Experimental results demonstrate the significant benefits of the proposed algorithm in reducing the response latency of tasks and balancing the workload of edge servers.

Distributed data services usually rely on consensus protocols like Paxos and Raft to provide fault-tolerance and data consistency across global and local-distributed data centers. Erasure coding replication has appealing storage and network cost saving compared with full copy replication, which helps consensus protocols achieve low latency, high fault tolerance, and high throughput for data access. Applying erasure coding in consensus protocols directly will degrade the liveness level when the number of failure servers reaches a certain level. To address the challenge, CRaft just stores full copy replication instead of erasure coding replication when the number of failed servers reaches a certain threshold. In such situation, CRaft will be downgraded sharply to the same storage and network costs as Raft. To overcome the shortcoming of CRaft, we propose a protocol, called HRaft, which can adapt the placement of data blocks in order to always have enough blocks to recover the stored value when servers fail. By replenishing some coded blocks in healthy servers instead of full copy replication, it can avoid switching to the full replication when a certain threshold on the number of failures is reached. We designed and implemented a key-value (KV) storage prototype to validate the proposed protocol and evaluate its performance. The experimental results show HRaft can significantly reduce storage and network costs and improve write performance while keeping the liveness level compared to CRaft.

This paper considers a distributed computing system where nodes are grouped such that nodes in the same group compute the same function. To complete a computing task distributedly, nodes need to exchange their local computation results with each other, which incurs communication cost and security concerns. The objective of this work is to study the tradeoff between computation and communication and avoid exchanged information leakage to eavesdroppers. Given a fixed computation load, we derive lower bounds on the communication load for 1-group and 2-group systems. New coding schemes are proposed and shown to be weakly secure and achieve the optimal tradeoffs for 1-group systems and for 2-group systems with large computation load.

This paper studies cached-aided multicast transmissions in fronthaul fog radio access networks (F-RANs). While index coding and cached-aided non-orthogonal multiple access (NOMA) are techniques commonly used for utilizing cache contents to save transmit energy, there is a lack of general framework to integrate them. This work proposes index-coded NOMA and dynamic coded-NOMA to investigate energy performance of the integration of index coding and NOMA under whole-file and subfile caching, respectively. Besides, dynamic cache space allocation is applied to both caching schemes, which allocates cache sizes to the fog access points (F-APs) according to their large-scale channel conditions. For index-coded NOMA, the general grouping problem is proved to be NP-hard and optimal solutions for some special cases are given. Furthermore, efficient heuristic grouping algorithms are proposed. For dynamic coded-NOMA, we obtain the closed-form minimum transmit energy. The numerical results validate the good performance of our proposed algorithms. Index-coded NOMA and dynamic coded-NOMA have comparable performance and both of them save much energy than the existing schemes. When there are 12 F-APs under small-cache scenarios, index-coded NOMA saves energy by 70.3% compared to traditional NOMA.

Both index coding and non-orthogonal multiple access (NOMA) are useful techniques for a transmitter to send information to multiple cache-enabled receivers. In former works, either index coding or cache-aided NOMA is applied in the system, while the combination of index coding and cache-aided NOMA has not been fully investigated. This work is the first attempt to integrate these two techniques. A two-phase transmission algorithm is proposed to first partition receivers into index coding groups and next pair these groups up for superposition coding. Cache-aided interference cancellation (CIC) is employed at the receiver. This new method is applied to a cache-enabled fog radio access network (F-RAN). Besides, a distinct-file caching scheme with imbalanced cache size at fog access points (F-APs) is proposed. For this particular caching scheme, the two-phase algorithm can be fine-tuned in a way so that its time complexity becomes linear in the number of F-APs, which is very fast and particularly desirable from a practical viewpoint. Furthermore, simulation results show that our proposed method can significantly reduce the power consumption for transmissions over the fronthaul link of the F-RAN.

Distributed data services usually rely on consensus protocols, such as Paxos and Raft, to provide fault-tolerance and data consistency across distributed data centers and even edge networks. In consensus protocols, erasure coded replication has appealing storage and network cost savings compared with full copy replication, which help achieve low latency, high fault-tolerance and high throughput. However, the liveness level will inevitably decrease when erasure codes are naively applied in consensus protocols. To keep the original liveness level, an existing protocol, called CRaft, switches from erasure coded replication to full copy replication when the number of failures exceeds a certain threshold. Such a solution, however, degrades system performance sharply. To tackle this problem, this work proposes a novel protocol called HRaft to enable graceful degradation on storage and network efficiency when failures happen. Without using full copy replication, it replenishes some coded blocks in healthy servers to reduce storage and network costs and to keep data consistency. The performance of the proposed protocol will be evaluated by deploving it into practical networks.

We address the issue of maximizing the number of connected devices in a Narrowband Internet-of-Things (NB-IoT) network using nonorthogonal multiple access (NOMA) in the downlink. We first propose an optimal joint subcarrier and power allocation strategy assuming perfect channel state information (CSI) called stratified device allocation (SDA), which maximizes the connectivity under data rate, power, and bandwidth constraints. Then, we generalize the connectivity maximization problem to the case of partial CSI, where only the distance-dependent path-loss component of the channel gain is available at the base station (BS). We introduce a novel framework called the stochastic connectivity optimization (SCO) framework. In this framework, we propose a heuristic improvement to SDA, namely, SDA with excess power (SDA-EP) algorithm for operation under partial CSI. Furthermore, we derive a concave approximation (SCO-CA) algorithm of near-optimal performance to SCO given the same amount of CSI. Through computer simulations, we show that SDA-EP and SCO-CA outperform conventional NOMA and OMA schemes in the presence of partial CSI over a wide range of service scenarios.

This work considers cache placement for ultra-dense fog radio access networks (F-RANs). In an F-RAN, the fog access points (F-APs) form overlapping clusters based on their geographical locations. A cluster of F-APs then acts as a distributed cache to cooperatively serve user requests. The fronthaul traffic minimization problem is formulated in information-theoretic terms. For the k-association networks, cache placement can be optimized by concatenating an MDS code with a repetition code. By repeating the same packet in some F-APs, multicasting over the fronthaul link can be done in cache placement, which saves energy and bandwidth. Such an idea is applied to both uncoded and coded caching schemes based on hypergraph coloring. Their associated optimization problems are shown to be NP-complete. For the uncoded case, a suboptimal algorithm is proposed, which carefully repeats the subfiles. For the coded case, a heuristic algorithm that minimizes the field size requirement of the MDS repetition scheme is proposed. Simulation results demonstrate the outstanding performance of the proposed uncoded and coded caching schemes during both the cache placement phase and content delivery phase in reducing fronthaul traffic load and energy consumption.

This paper studies distributed power control for the uplink of multi-cell non-orthogonal multiple access (NOMA) systems. Within a cell, the transmissions of different users are modeled as a Gaussian multiple access channel, treating inter-cell interference as additive Gaussian noise. By analyzing the geometry of the feasible power region, using successive interference cancellation at each base station is proved to be optimal in minimizing the total transmission power of all users under rate constraints. The decoding order at each base station, however, remains to be determined. If the decoding order is decided without base station cooperation, the overall control algorithm is fully distributed but is suboptimal in general. To achieve optimality, a partially distributed algorithm is designed, which requires base stations to exchange control messages. Given any feasible instance, the algorithm is proved to converge to the optimal solution. The performance of the fully distributed and partially distributed power control algorithms is compared by computer simulations. The fully distributed algorithm is nearly optimal in terms of outage probability. When a high data rate is required, the partially distributed algorithm is able to reduce the total power consumption by about 20%.

A novel power-domain non-orthogonal multiple access (NOMA) scheme with high-dimensional modulation is proposed. Signals for two users, each of which selected from a high-dimensional modulation constellation matrix, are superimposed on the same time-frequency resource for transmissions. While inter-user interference is treated as noise at the receiver of the far user, successive interference cancellation is used at the receiver of the near user. By analyzing the upper bounds of the detection errors, the power allocation factor is derived, which depends only on the relative power gain of the two users, i.e., the ratio between the squared of the two channel gains, but not on the operating signal-to-noise ratio. This nice feature allows us to perform user pairing easily for a system with more than two users. The optimal user pairing strategy that minimizes the total power consumption is analytically derived. Simulation results show that our proposed design outperforms some benchmark scheme.

In fog radio access networks, the limited capacity of the fronthaul link is the bottleneck, which renders a high quality of service for video streaming difficult. To circumvent the problem, popular files can be cached in fog access points during off-peak hours. This work points out that beamforming in the access network can be exploited to reduce fronthaul traffic load by a joint design of cache placement scheme at the fog access points and index-coded transmission scheme over the fronthaul. Simulation results show that a percentage reduction of fronthaul traffic by more than 30% can be achieved.

A novel non-orthogonal multiple access (NOMA) scheme with spherical code superposition and its user pairing strategy are proposed. A transmitter transmits the superposition of the signals of two users, each of which is selected from the high dimensional spherical code on the same time-frequency resource by power-domain multiplexing NOMA. Upper bounds of the word error probabilities of the two users are derived. Based on them, a power allocation scheme for the two users is proposed, which guarantees that their word error probabilities are below a certain threshold. Under our power allocation scheme, the optimal user pairing strategy that minimizes the total power consumption in a general multi-user system is analytically found. Numerical results show that our proposed system outperforms some benchmark methods.

Cloud computing provides a flexible and cost-effective solution to big data applications. Data privacy, however, is a main concern. To avoid information leakage to a cloud service provider, a user may store portions of encoded data in multiple clouds and perform computing tasks in a distributed way. In this work, nested MDS codes and the criterion of perfect secrecy are adopted. The allocation of encoded data to be stored in heterogeneous clouds with different computing capability is formulated as an optimization problem, subject to data reliability and security constraints. The problem is shown to be feasible if and only if the storage budget is above a certain level. The tradeoff between minimum computation time and storage budget is analytically characterized, and the former is proved to be a piecewise-linear decreasing function of the latter. When the storage budget increases beyond a certain threshold, the optimal computation time levels off. Closed-form expressions of minimum computation time and optimal storage allocation are obtained. Numerical results show that the optimized allocation outperforms equal allocation significantly if the computing rates of different clouds have large variation.

Future wireless communication systems have been imposed high requirement on power efficiency for operator's profitability as well as to alleviate information and communication technology (ICT) global carbon emission. To meet these challenges, the power consumption minimization problem for a generic multi-cell multiple input and single output non-orthogonal multiple access (MISO-NOMA) system is studied in this work. The associated joint user grouping, beamforming (BF) and power control problem is a mixed integer non-convex programming problem, which is tackled by an iterative distributed methodology. Towards this end, the near-optimal zero-forcing (ZF) BF is leveraged, wherein the semiorthogonal user selection (SUS) strategy is applied to select BF users. Based on these, the BF vectors and BF users are determined for each cell using only local information. Then, two distributed user grouping strategies are proposed. The first one, called channel condition based user clustering (CCUC), performs user grouping in each cell based on the channel conditions. This is conducted independently of the power control part and has low computational complexity. Another algorithm, called power consumption based user clustering (PCUC), uses both the channel conditions and inter-cell interference information to minimize each cell's power consumption. In contrary to CCUC, PCUC is optimized jointly with the power control. Finally, with the obtained user grouping and BF vectors, the resultant power allocation problem is optimally solved via an iterative algorithm, whose convergence is mathematically proven given that the problem is feasible. We perform Monte-Carlo simulation and numerical results show that the proposed resource management methods outperform various conventional MISO schemes and the non-clustered MISO-NOMA strategy in several aspects, including power consumption, outage probability, energy efficiency, and connectivity efficiency.

The user pairing problem for cache-based timeslotted non-orthogonal multiple access (NOMA) system with index coding is investigated. During each time slot, the packets of two users are scheduled at the base station. In accordance with different cache information of the scheduled users, either superposition coding or index coding is applied for base station transmission. For some specific case, the superior performance on the aspect of power consumption of index coding compared to that of superposition coding is analyzed. Besides, the power saving of our design system when compared to that of the NOMA system with pure superposition coding is also demonstrated in a mathematical way. Subsequently, we show that the original user scheduling problem can be transformed in quadratic time into a minimum weight perfect matching problem of an undirected graph, which can be solved with time complexity O(K3), where K is the number of users. Based on this transformation, the feasibility of any given system is analyzed. Furthermore, we formulate the minimum weight perfect matching problem as an integer linear problem and solve it by integer linear programming. Numerical results validate the performance gains of our proposed system from the aspects of total transmit power and outage probability.

In this paper, we present a learning based data deduplication algorithm, called LIPA, which uses the reinforcement learning framework to build an adaptive indexing structure. It is rather different from previous inline chunk-based deduplication methods to solve the chunk-lookup disk bottleneck problem for large-scale backup. In previous methods, a full chunk index or a sampled chunk index often is often required to identify duplicate chunks, which is a critical stage for data deduplication. The full chunk index is hard to fit in RAM and the sampled chunk index directly affects the deduplication ratio dependent on the sampling ratio. Our learning based method only requires little memory overheads to store the index but achieves the same or even better deduplication ratio than previous methods. In our method, after the data stream is broken into relatively large segments, one or more representative chunk fingerprints are chosen as the feature of a segment. An incoming segment may share the same feature with previous segments. Thus we use a key-value structure to record the relationship between features and segments: a feature maps to a fixed number of segments. We train the similarities of these segments to a feature represented as scores by the reinforcement learning method. For an incoming segment, our method adaptively prefetches a segment and the successive ones into cache by using multi-armed bandits model. Our experimental results show that our method significantly reduces memory overheads and achieves effective deduplication.

Cooperative caching using maximum distance separable (MDS) codes and repetition codes in ultra-dense networks is studied, with the objective of maximizing the code rate while ensuring that end users can restore the file from the associating small base stations (SBSs) without the use of the backhaul link. It is proved that MDS-coded caching is optimal in general. In contrast, repetition caching is optimal only for some special cases. Repetition caching is, in general, suboptimal, and the associated code rate maximization problem is shown to be NP-hard and a heuristic algorithm is designed to evaluate the potential coding gain in arbitrary 2-dimensional (2D) network. Simulation results show that MDS-coded caching can save about 40% storage space when compared with repetition caching, and this coding gain increases when the amount of overlapping between clusters increases.

This paper considers a wireless communication network consisting of multiple interfering multicast sessions. Different from a unicast system where each transmitter has only one receiver, in a multicast system, each transmitter has multiple receivers and broadcasts a common message to all of them. It is a well-known result for wireless unicast systems that the feasibility of a signal-to-interference-plus-noise power ratio (SINR) without power constraint is decided by the spectral radius of a nonnegative matrix. We generalize this result and obtain necessary and sufficient conditions for the feasibility of an SINR in a wireless multicast system with and without power constraint. The feasible SINR region and its geometric properties are studied. Besides, an iterative algorithm is proposed, which can efficiently check the feasibility condition and compute the boundary points of the feasible SINR region.

In wireless distributed storage systems, storage nodes are connected by wireless channels, which are broadcast in nature. This paper exploits this unique feature to design an efficient repair mechanism, called broadcast repair, for wireless distributed storage systems in the presence of multiple-node failures. Due to the broadcast nature of wireless transmission, we advocate a new measure on repair performance called repair-transmission bandwidth. In contrast to repair bandwidth, which measures the average number of packets downloaded by a newcomer to replace a failed node, repair-transmission bandwidth measures the average number of packets transmitted by helper nodes per failed node. The storage system we considered can undergo an unlimited number of repair rounds. We obtain an upper bound on the maximum file size that can be supported by a cut analysis of a finite graph. The achievability is shown by codes constructed over a refined information flow graph, which is unbounded. In addition, the optimal storage-bandwidth tradeoff is obtained. The performance of broadcast repair is compared both analytically and numerically with that of cooperative repair, the basic repair method for wired distributed storage systems with multiple-node failures. While cooperative repair is based on the idea of allowing newcomers to exchange packets, broadcast repair is based on the idea of allowing a helper to broadcast packets to all newcomers simultaneously. We show that broadcast repair outperforms cooperative repair, offering a better tradeoff between storage efficiency and repair-transmission bandwidth.

The majority of works in distributed storage networks assume a simple network model with a collection of identical storage nodes with the same communication cost between the nodes. In this paper, we consider a realistic multi-rack distributed data storage network and present a code design framework for this model. Considering the cheaper data transmission within the racks, our code construction method is able to locally repair the nodes failure within the same rack by using only the survived nodes in the same rack. However, in the case of severe failure patterns when the information content of the survived nodes is not sufficient to repair the failures, other racks will participate in the repair process. By employing the criteria of our multi-rack storage code, we establish a linear programming bound on the size of the code in order to maximize the code rate.

In visible light communications (VLC) and visible light positioning (VLP), channel gains between receiver and light sources are required to be estimated. Although Time Division Multiple Access (TDMA) is typically used in the channel estimation phase of radio frequency systems, it may not be applicable for VLC and VLP systems due to the maximum power constraint and desired average power constraint that are unique to visible light systems. Recently, combinational code has been proposed as a coding scheme for channel estimation in VLC and VLP. Combinational code can work under the maximum and average power constraints, and it minimises the total and maximum noise variances experienced by the receiver. This paper reports some experimental results to compare combinational code and two schemes based on TDMA. Experimental results show that in terms of noise variance experienced by a receiver, combinational code significantly outperforms other schemes based on TDMA under the same power constraints. Challenges encountered in experiments for channel estimation are discussed and solutions are suggested to overcome these challenges.

In this paper, we investigate the distributed power allocation algorithm for the downlink of a two-cell multiple input and single output non- orthogonal multiple access (MISO-NOMA) system. The problem targets at minimizing the total power consumption of the base stations (BSs) while taking into consideration each user's data rate requirement. A distributed power control algorithm is devised. During each iteration, the BS updates the transmit power of its attached users according to the link gain vector and the inter-cell interference plus noise value at the users. For some special cases, we show that the proposed algorithm is guaranteed to converge to a unique fixed point that could be an optimal solution based on Yate's power control framework. Furthermore, some modifications are made for the iterative algorithm to enhance the convergence performance of the instances with feasible solutions. Simulation results demonstrate that the designed power allocation strategy can significantly improve system performance over conventional orthogonal multiple access (OMA) counterpart in terms of total transmit power and outage probability.

Non-orthogonal multiple access (NOMA) is an effective means to improve the spectral efficiency of a wireless communication system. When applied to cellular networks, cell edge users may suffer from low bit rate, or the associated base stations may need to use excessively high power to serve those users. In order to alleviate the problem, this paper considers the integration of NOMA with coordinated transmission techniques. A two-cell system is considered, in which there are two users near their associated base stations and a cell edge user served by both base stations. It is assumed that each user has a data rate requirement, and the system objective is to minimize the total transmit power. With a formal problem formulation, the feasibility of the problem is characterized by using Helly's theorem. When the problem is feasible, we design both centralized and distributed algorithms to solve it. Numerical results show that NOMA can significantly outperform an orthogonal multiple access scheme in terms of power consumption and outage probability.

In visible light communications (VLC) and visible light positioning (VLP), it is essential to obtain accurate estimates of the channel gains between receiver and multiple light sources. When there are multiple transmitters, time-division multiple access (TDMA) is typically used in the channel estimation phase of radio frequency systems. However, the estimation performance of TDMA-based schemes in VLC and VLP systems is substantially impacted by the maximum power constraint and desired average power constraint that are unique to visible light systems. Under these constraints, this paper explores coding schemes for the simultaneous channel gain estimations of multiple light sources such that the total and maximum noise variances of the channel estimates by the receiver are minimized. Although the minimization problem is non-convex, criteria for optimal codes are found by using majorization theory. Coding scheme satisfying these criteria is proposed that helps to characterize the fundamental tradeoff between noise variance and codeword length.

The classical threshold secret sharing scheme by Shamir requires high computation complexity. Many fast secret sharing schemes have been proposed to reduce the computation cost. Another problem of perfect secret sharing scheme is the large share size. Ramp sharing schemes were proposed as a solution to reduce the share size with sacrificing secrecy to some extent. This paper proposes a new ramp scheme, which is adapted from the zigzag-decodable erasure codes for data storage systems. The scheme is shown to approach a linear ramp scheme when the secret size grows to infinity. It is conceptually easy to understand, and has low computation cost, since both its encoding and decoding algorithms are based only on the XOR and bitwise-shift operations.

International audience

The instantiation of a maximally recoverable (MR) code is shown to be a special case of generic network coding. The defining condition of MR codes, called potential independence, is shown to be equivalent to maximal matching in bipartite graphs. Algorithms for MR instantiation are proposed and upper bounds on the required field size are derived.

A code is said to possess the combination property if k source packets are mapped into n k packets and any k out of these n packets are able to recover the information of the original k packets. While the class of maximum-distance-separable codes are well known to have this property, its decoding complexity is generally high. For this reason, a new class of codes which can be decoded by the zigzag-decoding algorithm is considered. It has a lower decoding complexity at the expense of extra storage overhead in each parity packet. In this work, a new construction of a zigzag decodable code is proposed. The novelty of this new construction lies in the careful selection of the amount of bit-shift of each source packet in obtaining each parity packet. Besides, an efficient on-the-air repair scheme based on physical-layer network coding is designed.

To obtain good network performance in Long Term Evolution-Advanced (LTE-A) heterogeneous networks (HetNets), enhanced inter-cell interference coordination (eICIC) and further eICIC (FeICIC) have been proposed by LTE standardization bodies to address the entangled inter-cell interference and the user association problems. We propose the distributed algorithms based on the exact potential game framework for both eICIC and FeICIC optimizations. We demonstrate via simulations a 64% gain on energy efficiency (EE) achieved by eICIC and another 17% gain on EE achieved by FeICIC. We also show that FeICIC can bring other significant gains in terms of cell-edge throughput, spectral efficiency, and fairness among user throughputs. Moreover, we propose a downlink scheduler based on a cake-cutting algorithm that can further improve the performance of the optimization algorithms compared with conventional schedulers.

This paper investigates the power control problem for the downlink of a multi-cell non-orthogonal multiple access system. The problem, called P-OPT, aims to minimize the total transmit power of all the base stations subject to the data rate requirements of the users. The feasibility and optimality properties of P-OPT are characterized through a related optimization problem, called Q-OPT, which is constituted by some relevant power control subproblems. First, we characterize the feasibility of Q-OPT and prove the uniqueness of its optimal solution. Next, we prove that the feasibility of P-OPT can be characterized by the Perron-Frobenius eigenvalues of the matrices arising from the power control subproblems. Subsequently, the relationship between the optimal solutions to P-OPT and that to Q-OPT is presented, which motivates us to obtain the optimal solution to P-OPT through solving the corresponding Q-OPT. Furthermore, a distributed algorithm to solve Q-OPT is designed, and the underlying iteration is shown to be a standard interference function. According to Yates's power control framework, the algorithm always converges to the optimal solution if exists. Numerical results validate the convergence of the distributed algorithm and quantify the improvement of our proposed method over fractional transmit power control and orthogonal multiple access schemes in terms of power consumption and outage probability.

This paper investigates the power control problem for the downlink of a non-orthogonal multiple access (NOMA) system with two cells. The problem, called p-Opt, aims to minimizes the total transmit power of the base stations subject to the data rate requirements of the users. The feasibility and optimality properties of p-Opt is first characterized. It is proved that the feasible power region of p-Opt can be represented by the feasible regions of four power control subproblems that constitute a related optimization problem called q-Opt. Furthermore, the optimal solution to p-Opt can be obtained by solving the corresponding instance of q-Opt. A distributed algorithm to solve q-Opt is designed and the underlying iteration is shown to be a standard interference function. According to Yates's power control framework, the algorithm always converges to the optimal solution if exists. Numerical results validate the convergence of the distributed algorithm and quantify the improvement of NOMA over its orthogonal multiple access counterparts in terms of power consumption and outage probability.

In visible light communication (VLC) systems, information are conveyed by visible light instead of radio-frequency electromagnetic waves. Based on received signal strength, accurate indoor positioning systems can also be built. Since a receiver obtains the superposition of signals from all light sources within line of sight together with ambient light, a multiple access scheme is necessary for the receiver to distinguish the received symbol and signal strength from each light source. This paper proposes two multiple access schemes for VLC. The first scheme supports information broadcast and positioning. By using 2Ntimeslots, N transmitters transmit 2N- 1 symbols in total. The second scheme supports positioning only but places emphasis on minimizing the required timeslots. In each 2N timeslots for an odd integer N, the channel gains of 3N - 1/2 transmitters can be estimated.

With the widely use of smart devices and rapid development of communication technologies, it becomes easier for base stations to obtain the context information of users. The context information can be utilized to optimize system resource allocation. This paper focuses on context-aware unicast cellular networks. Assuming that some channel state information (CSI) can be predicted based on user context such as user location and moving pattern, joint power control and transmission scheduling is applied to minimize the transmission energy consumption. By reducing the energy minimization problem to a semi-assignment problem, our proposed algorithm can find the optimal solution in polynomial time. Simulation results show that the proposed context-aware scheme outperforms the traditional round-robin scheduler and opportunistic scheduler, which do not consider the feature of context-awareness.

This paper investigates the power control problem for the uplink of a non-orthogonal multiple access (NOMA) system with two cells. The game-theoretic approach is used to study the stability of distributed power control algorithms. It is shown that a unique Nash equilibrium exists if the Perron-Frobenius eigenvalue of a certain link gain matrix is less than one. A distributed power control algorithm is constructed, which is guaranteed to converge to the Nash equilibrium. Furthermore, the optimality property of the Nash equilibrium is studied. It is shown that the equilibrium is globally optimal in minimizing total power consumption, provided that some technical conditions are satisfied. Numerical results show that the power-controlled NOMA system outperforms its orthogonal counterparts.

For a user to store data in the cloud, using services provided by multiple cloud storage providers (CSPs) is a promising approach to increase the level of data availability and confidentiality, as it is unlikely that different CSPs are out of service at the same time or collude with each other to extract information of a user. This paper investigates the problem of storing data reliably and securely in multiple CSPs constrained by given budgets with minimum cost. Previous works, with variations in problem formulations, typically tackle the problem by decoupling it into sub-problems and solve them separately. While such a decoupling approach is simple, the resultant solution is suboptimal. This paper is the first one which considers the problem as a whole and derives a jointly optimal coding and storage allocation scheme, which achieves perfect secrecy with minimum cost. The analytical result reveals that the optimal coding scheme is the nested maximum-distance-separable code and the optimal amount of data to be stored in the CSPs exhibits a certain structure. The exact parameters of the code and the exact storage amount to each CSP can be determined numerically by simple 2-D search.

This paper investigates the linear network coding problem for erasure broadcast channel with user feedback. An innovative linear network code is shown to be uniformly optimal for the system. In general, determining the existence of innovative packets is proved to be NP-complete. When the finite field size is larger than the number of users, innovative packets always exist and the problem of finding an innovative encoding vector with smallest Hamming weight is considered. The corresponding decision problem is shown to be NP-complete. Optimal and approximate network coding algorithms for maximizing the sparsity of encoding vectors are designed.

A new construction for sector-disk codes and partial MDS codes up to three sector erasures are proposed. In contrast to existing codes, which are based on the design of parity check matrix, our new code is based on the design of generator matrix. This new approach allows us to construct a code that requires a small field size. In particular, for the case when there is only one sector erasure, our field size requirement is independent of the number of sectors and is close to optimal. For the case when there are three sector erasures, we provide a condition which allows the code be constructed by computer search.

In this paper we propose a distributed algorithm for jointly optimizing almost blank subframe (ABS) and cell selection bias (CSB) patterns in Long Term Evolution- Advanced (LTE-A) heterogeneous networks (HetNets). We formulate the optimization problem as an exact potential game, where a Nash equilibrium point is guaranteed to be achieved within finite number of plays. Through simulations, we are able to demonstrate the fast convergence of the algorithm, an increase in average user rate, and a tremendous improvement on the service fairness of the users.

To optimize the network utility in 3GPP Long Term Evolution-Advanced (LTE-A) heterogeneous networks (HetNets), it is necessary to jointly consider inter-cell interference mitigation and user attachment. Based on potential game formulation, we optimize almost blank subframe (ABS) and/or cell selection bias (CSB) settings for both macrocells and picocells in a distributed manner. We demonstrate the need of joint ABS and CSB optimization via simulation case studies. Extensive simulations confirm that joint ABS and CSB optimizations can lead to a 20% improvement in spectral efficiency and a 46% improvement in energy efficiency while increasing the fairness of the achieved rates of users.

The problem of storing data reliably and securely in multiple cloud storage providers (CSPs) with minimum cost is investigated. A jointly optimal coding and storage allocation scheme, which achieves perfect secrecy with minimum cost, is derived. The optimal coding scheme is shown to be the nested maximum-distance-separable code and the optimal amounts of data to be stored in the CSPs is proven to exhibit a three-level structure. The exact parameters of the code and the exact storage amount to each CSP can be determined numerically by simple one-dimensional search.

The fundamental theorem of distributed storage systems characterizes the maximum file size that can be stored with certain assumptions on file retrieval and node repair. The result is composed of two parts, namely, the min-cut bound and that the bound can be achieved by linear network code with bounded field size. The derivation of the min-cut bound is reexamined and illuminated by making an implicit step explicit. Furthermore, a simple alternative proof for the achievability of the min-cut bound is presented, which is based on the construction of the generic storage code, a restricted form of generic network code. The proof techniques in this paper are expected to be extensible to other more complex models of distributed storage systems.

Locally repairable codes are used in distributed storage networks to minimise the number of survived nodes required to repair a failed node. However, the robustness of these codes is a main concern since locally repair procedure may fail when there are multiple node failures. This paper proposes a new class of robust locally repairable codes which guarantees that a failed node can be repaired locally even when there are multiple node failures. Upper bound on the size of robust locally repairable codes using linear programming tools are obtained and examples of robust locally repairable codes attaining these bounds are constructed.

In practical distributed storage networks, data centres house hundreds of racks, each of which contains several storage nodes. However, the majority of works in distributed storage assume a simple network model with a collection of identical storage nodes with same communication cost between the nodes. In this paper, we consider a more realistic rack model of storage network and present a code design framework for this model. Using our code construction method, node failures within a rack can be repaired locally by survived nodes in the same rack or by the other survived racks when the information content of the same rack is not sufficient to repair the failed nodes.

Locally repairable (LR) codes are used in distributed storage systems to minimize the number of storage nodes involved in node repair. While existing constructions of LR codes do not take the topology of the storage network into account, this work focuses on designing LR codes over a network. A new concept called node locality is introduced. It is shown that the decision problem of determining whether a binary linear LR code exists, subject to the constraints of code rate, symbol locality, node locality, and repair cost, is NP-complete. The corresponding optimization version, which aims to maximize the code rate, is also considered. It is proved that the problem can be reduced to the minimum k-set cover problem, and can be solved in polynomial time for the special case where the symbol locality is one. For the general case where the symbol locality is greater than or equal to two, the problem is NP-hard and can be approximately solved by a greedy algorithm.

This paper presents a flexible irregular model for heterogeneous cloud storage systems and investigates how the cost of repairing failed nodes can be minimized. The fractional repetition code, originally designed for minimizing repair bandwidth for homogeneous storage systems, is generalized to the irregular fractional repetition code, which is adaptable to heterogeneous environments. The code structure and the associated storage allocation can be obtained by solving an integer linear programming problem. For moderate sized networks, a heuristic algorithm is proposed and shown to be near-optimal by computer simulations.

Index coding (IC), which can be regarded as a special class of network coding, deals with the problem of sending a number of packets to a group of receivers, each of which requests one packet and may have some other packets in its cache. This paper generalizes the IC problem in that both the packet requested by a receiver and the packets in its cache can be linear combinations of the packets. To minimize the number of transmissions required, a heuristic algorithm based on the idea of partitioning the users into coding groups is designed. To realize this idea, a polynomial time algorithm to determine whether a set of users form a coding group over the binary field or a field with a size larger than the number of users is constructed. For users that form a coding group, the corresponding encoding vector can be also found. A lower bound is derived in order to evaluate the performance of the heuristic algorithm. Numerical results show that the number of transmissions required by the heuristic algorithm and the lower bound both grow roughly linearly with the number of users, and the heuristic algorithm outperforms some benchmark algorithms.

In erasure broadcast channels, network coding has been demonstrated to be an efficient way to satisfy each user's demand. However, the erasure broadcast channel model does not fully characterize the information available in a "lost" packet, and therefore any retransmission schemes designed based on the erasure broadcast channel model cannot make use of that information. In this paper, we characterize the quality of erroneous packets by Signal-to-Noise Ratio (SNR) and then design a network coding retransmission scheme with the knowledge of the SNRs of the erroneous packets, so that a user can immediately decode two source packets upon reception of a useful retransmission packet. We demonstrate that our proposed scheme, namely Quality-Aware Instantly Decodable Network Coding (QAIDNC), can increase the transmission efficiency significantly compared to the existing Instantly Decodable Network Coding (IDNC) and Random Linear Network Coding (RLNC).

A code is said to have the MDS property if it maps K source blocks into N coded blocks, while any K out of the N coded blocks allow recovery of the original K source blocks. A new vector code that has the MDS property is designed. It allows the source blocks to be recovered by using a fast algorithm called ZigZag decoding. It can serve as the Fractional Repetition code, a regenerating code for distributed storage systems. The overall design becomes very simple to implement, as node failure can be handled by uncoded and exact repair while data retrieval can be performed by XOR operations.

The multiple access relay channel (MARC) where multiple users send independent information to a single destination aided by a single relay under large-scale path loss and slow fading is investigated. At the beginning, the users take turns to transmit their packets. The relay is not aware of the erasure status of each packet at the destination but has the knowledge of the average signal-to-noise-ratio (SNR) of every communication link. With this knowledge, the relay applies network coded retransmission on the overheard packets so as to maximize the expected total number of recovered packets or minimize the average packet loss rate at the destination. Several network coding (NC) strategies at the relay are designed. In particular, for the case where the relay is given only one time slot for retransmission, an optimal NC construction is derived. For the multiple-slot case, three sub-optimal schemes are investigated, namely network coding with maximum distance separable (MDS) code (NC-MDS), the worst-user-first (WUF) scheme and a hybrid of NC-MDS and WUF. We prove that NC-MDS and WUF are asymptotically optimal in the high and low SNR regimes, respectively. A lower bound on the average packet loss rate has been derived. Numerical studies show that, in a cellular system, the hybrid scheme offers significant performance gain over a number of existing schemes in a wide range of SNR. We also observe that performance curves of both WUF and the hybrid scheme touch the derived lower bound in the low SNR regime.

In a heterogenous networking environment, a new practical distributed storage model is defined by introducing the concepts of repair topology and retrieval sets. How to repair a failed storage node so as to minimize the system repair cost is investigated. It is shown that the repair cost minimization problem can be decomposed into a combinatorial problem and an integer linear programming problem. Moreover, a heuristic algorithm to find suboptimal repair topologies is given.

We consider a two-way relay channel (TWRC) in which two terminals exchange messages with the help of a relay between them. The two terminals transmit messages to the relay through the Multiple Access Channel (MAC) and the relay transmits messages to the two terminals through the Broadcast Channel (BC). We assume that the MAC and the BC do not interfere with each other, and each terminal receives signals only from the relay but not the other terminal. All the nodes are assumed to be full-duplex, which means that they can transmit and receive information at the same time. A transmission scheme for the Gaussian TWRC is said to be analog-relaying if the relay does not need any codebook for encoding. The simplest analog-relaying scheme is amplify-and-forward (AF), under which the relay amplifies the received codeword and forwards the resultant codeword to the two terminals. In this paper, we propose a new analog-relaying scheme called amplify-and-modulo (AM) based on lattice operations. AM is a slight modification of AF. Under AM, the relay first amplifies the received codeword followed by reducing the power of the amplified codeword using the modulo-lattice operation, and then forwards the resultant codeword to the two terminals. After receiving the codeword transmitted by the relay, each terminal subtracts its own information before decoding. We prove an achievable rate region for AM, and obtain a necessary and sufficient condition under which AM outperforms AF. In addition, we show by graph that AM can achieve a strictly higher equal-rate than AF and another existing analog-relaying scheme together under some scenario.

In the original index coding problem, each user has a set of uncoded packets as side information, and wants to decode some other packets from the source node. The source node aims at satisfying the demands of all users as quickly as possible. With linear network coding, this is accomplished by broadcasting linear combinations of the source packets over some finite field. Since the broadcast is performed over a wireless channel, a user may overhear some coded packets that are not intended to him/her. This motivates a generalization of the index coding problem to the case where linearly coded packets are used as side information. We show that this generalized linear index coding problem is equivalent to solving a system of multi-variable polynomial equations. A heuristic solution is constructed and is applied to the broadcast relay channel.

In a distributed storage system, the storage costs of different storage nodes, in general, can be different. How to store a file in a given set of storage nodes so as to minimize the total storage cost is investigated. By analyzing the min-cut constraints of the information flow graph, the feasible region of the storage capacities of the nodes can be determined. The storage cost minimization can then be reduced to a linear programming problem, which can be readily solved. Moreover, the tradeoff between storage cost and repair-bandwidth is established.

In the application of linear network coding to wireless broadcasting with feedback, we prove that the problem of determining the existence of an innovative encoding vector is NP-complete when the finite field size is two. When the finite field size is larger than or equal to the number of users, it is shown that we can always find an encoding vector which is both innovative and sparse. The sparsity can be utilized in speeding up the decoding process. An efficient algorithm to generate innovative and sparse encoding vectors is developed. Simulations show that the delay performance of our scheme with binary finite field outperforms a number of existing schemes in terms of average and worst-case delay.

Energy saving is important for many wireless devices. In a multi-hop wireless network with multiple sessions, XOR network coding can be applied to opposite traffic flows so as to reduce the number of packet transmissions, which in turn reduce transmission energy. Such a change in packet forwarding, however, impacts the design of traffic routing. Traditional routing algorithms, which typically aim at finding shortest paths between source and destination nodes, may no longer work well. In this paper, an iterative routing algorithm is proposed, which favors paths that can provide more pair-wise XOR network coding opportunities. Simulation results show that this algorithm integrates well with the XOR forwarding method and can reduce energy cost significantly when compared with traditional shortest-path routing, with and without network coding.

This paper considers the scenario of the (1+1) evolutionary algorithm (EA) and randomized local search (RLS) with memory. Previously explored solutions are stored in memory until an improvement in fitness is obtained; then the stored information is discarded. This results in two new algorithms: (1+1) EA-m (with a raw list and hash table option) and RLS-m+ (and RLS-m if the function is a priori known to be unimodal). These two algorithms can be regarded as very simple forms of tabu search. Rigorous theoretical analysis of the expected time to find the globally optimal solutions for these algorithms is conducted for both unimodal and multimodal functions. A unified mathematical framework, involving the new concept of spatially invariant neighborhood, is proposed. Under this framework, both (1+1) EA with standard uniform mutation and RLS can be considered as particular instances and in the most general cases, all functions can be considered to be unimodal. Under this framework, it is found that for unimodal functions, the improvement by memory assistance is always positive but at most by one half. For multimodal functions, the improvement is significant; for functions with gaps and another hard function, the order of growth is reduced; for at least one example function, the order can change from exponential to polynomial. Empirical results, with a reasonable fitness evaluation time assumption, verify that (1+1) EA-m and RLS-m+ are superior to their conventional counterparts. Both new algorithms are promising for use in a memetic algorithm. In particular, RLS-m+ makes the previously impractical RLS practical, and surprisingly, does not require any extra memory in actual implementation.

A single source-destination pair communicating via a layer of parallel relay nodes under quasi-static slow fading environment is investigated. One existing transmission protocol is considered, namely, the combination of the distributed version of the half symbol-rate complex constellation orthogonal space-time block codes (OSTBC) with adaptive amplify-and-forward (AAF) relaying strategy. We call this transmission protocol as distributed orthogonal space-time block coded adaptive amplify-and-forward (DOSTBC-AAF). To improve the performance of DOSTBC-AAF, a distributed on-off power control (OOPC) rule applied to the relays is analytically derived and is proved to achieve full diversity order. The outage performance of DOSTBC-AAF with and without power control is evaluated. Our simulation results show that DOSTBC-AAF with all relays transmitting at full power (FP) achieves no diversity gain, whereas DOSTBC-AAF with OOPC achieves full diversity order. Correspondingly, at high signal-to-noise ratio (SNR), the diversity-multiplexing tradeoff (DMT) achieved by DOSTBC-AAF (OOPC) is analytically derived and is numerically shown to outperform DOSTBC-AAF (FP) significantly.

The achievable outage probability of the diamond relay network under Rayleigh fading is investigated. Two existing transmission protocols are considered, namely, the Alamouti-Coded Amplify-and-Forward (ACAF) and the Alamouti-Coded Decode-and-Forward (ACDF). For ACAF, a distributed optimal power control rule for the two relays is analytically derived. Simulation results show that with this power control rule, the diversity gain of ACAF increases from one to two, and its performance approaches that of ACDF in the high signal-to-noise ratio (SNR) regime. For ACDF, a performance bound is analytically obtained: for any outage probability e, its SNR offset is bounded above by 3 dB and its e-outage rate is within 1 bit of the e-outage capacity of the diamond relay network.

A receiver-cooperative scheme which divides the four-node cooperative system into two orthogonal sub-channels is considered. In each sub-channel, the system becomes a multipleaccess channel with multiple subcarriers. Our goal is to allocate subcarriers, power, and rate in a way that the sum rate is maximized. We propose two resource allocation strategies: time-sharing relaxation and heuristic subcarrier allocation with optimal power. We also give an upper bound for the sum rate achievable by our cooperative scheme. We compare the performance of our two proposed strategies with two other simple benchmarks in terms of sum rate and computation time. Simulation results shows the tradeoff between these two factors.

This paper investigates how much the rate region of the two-user Gaussian interference channel can be enlarged by allowing the two source nodes to cooperate. Two cooperative transmission schemes are proposed, based on dirty-paper coding and the assumption that the radio bandwidth is partitioned into two parts, and each part is utilized by one source node. The achievable rate regions and the outage performance of these two schemes are compared with the simplified Han-Kobayashi scheme, which is an efficient coding scheme for the interference channel. Simulation results show that in some channel realizations, the rate region of the Han-Kobayashi scheme is a subset of the rate regions of our two proposed cooperative transmission schemes. Furthermore, a significant gain in outage performance can be obtained, as the cooperative schemes have twice the diversity order of the simplified Han-Kobayashi scheme. While both cooperative schemes are able to yield large diversity gain, one of them can be implemented by simple decoder. Besides, it has an efficient algorithm for maximizing its weighted sum rate, and can be extended easily to the multi-channel case.

The complexity of the optimal phase control problem in wireless MIMO systems with scalar feedback quantization and equal-gain transmission is studied. The problem is shown to be NP-hard when the number of receive antennas grows linearly with the number of transmit antennas. For the case where the number of receive antennas is constant, the problem can be solved in polynomial time. An optimal algorithm is explicitly constructed. For practical purposes, a low-complexity algorithm based on local search is presented. Simulation results show that its performance is nearly optimal.

Protocol sequences are used for channel access in the collision channel without feedback. Each user is assigned a deterministic zero-one pattern, called protocol sequence. The zeros and ones in a protocol sequence are read out periodically, and a packet is sent if and only if it is one. A collision occurs if two or more users transmit at the same time. Due to the lack of feedback from the receiver and cooperation among users, the beginning of the protocol sequences cannot be synchronized and relative delay offsets are incurred. We study the design of protocol sequences from two different perspectives. Under the first one, called shift invariance, we aim at minimizing the fluctuation of throughput due to relative delay offsets. As for the second one, called user irrepressibility, we want to guarantee that each user can send at least one packet successfully in each period. For both design criteria, we derive a lower bound on sequence period and give an optimal construction that achieves this lower bound.

This paper deals with the weighted sum rate maximization problem in wireless networks consisting of multiple source-destination pairs. Since the optimization problem is non-convex, there are multiple local maxima. Here, we propose a simple iterative power control algorithm, namely round-robin (RR) power control, which has a low computational complexity. By comparing against benchmark problem instances, we show by simulation that the proposed algorithm converges to the global maximum with very high probability. Besides, a distributed implementation of the RR algorithm is established. The performance is satisfactory and the result is potential for practical use.

We propose a transmission scheme for the receiver cooperative wireless channel with two source-destination pairs, in which the receivers help each other by exchanging information. We decompose the channel into two orthogonal frequency bands. In each band, it reduces to a three-user multiple-access channel (MAC). Based on an encoding scheme for MAC with common information, a decode-and-forward-type transmission scheme is constructed. The resulting achievable rate region is numerically compared with an information-theoretic outer bound and two other transmission schemes.

We consider fair resource allocation in Gaussian frequency-division broadcast channel with intersymbol interference. The goal is to allocate power and subchannels in a way such that proportional fairness is achieved. We show that the subchannel allocation problem is NP-hard. If multiple users are allowed to time-share a subchannel, the relaxed problem is equivalent to the cake cutting problem and can be efficiently solved. For the joint power and subchannel allocation problem, we propose an iterative method, which solves the power allocation problem and subchannel allocation problem alternately. Simulation results show that its performance is nearly optimal.

The authors consider collision channel without feedback in which collided packets are considered unrecoverable. For each user, the transmission of packets follows a specific periodical pattern, called the protocol sequence. Due to the lack of feedback, the beginning of the protocol sequences cannot be synchronized and nonzero relative offsets are inevitable. It results in variation of throughput. In this paper, we investigate optimal protocol sequence sets, in the sense that the throughput variance is zero. Such protocol sequences are said to be shift-invariant (SI). The characterizing properties of SI protocol sequences are presented. We also prove that SI sequences are identifiable, meaning that the receiver is able to determine the sender of each successfully received packet without any packet header. A general construction of SI sequences that meets the lower bound on sequence length is given. Besides, we study the least periods of SI sequences, and show that the least periods must be distinct in some cases. The throughput performance is compared numerically with other protocol sequences.

Given any randomized search algorithm, we can avoid re-evaluating the fitness of previously visited points by storing the information in memory. This idea is applied to the (1+1) Evolutionary Algorithm with standard mutation and the Randomized Local Search (RLS) algorithm. Our analysis shows that a large reduction in running time can be obtained if we store recently visited points and execute those algorithms on some pseudo-boolean functions. Besides, the stored information can also be used to affect the generation of new search points. We illustrate this idea by designing an algorithm called Progressive Randomized Local Search. In contrary to RLS, it is capable of escaping from local maxima.

The performance limit of transmitter cooperation in a wireless network with two source-destination pairs is investigated. We assume that each source node is equipped with a receiver and acts as a relay node to the other source node. A decode-and-forward half-duplex coding scheme based on a novel use of dirty-paper coding is devised. An outer bound is derived and compared with the achievable rate region. We show by numerical example that the gap between them can be quite small.

The sum capacity of the one-sided parallel Gaussian interference channel is shown to be a concave function of user powers. Exploiting the inherent structure of the problem, we construct a numerical algorithm to compute it. Two suboptimal schemes are compared with the capacity-achieving scheme. One of the suboptimal schemes, namely iterative waterfilling, yields close-to-capacity performance when the cross link gain is small.

In this paper, we consider cooperative transmission between two source and destination pairs. Exchange of data is allowed between the two source nodes. In addition to the direct transmission link from the source to the intended destination, we have a two-hop relay link that sends the data via the neighboring source node. We partition the bandwidth into two parts, and each part is utilized by one source node, such that the transmissions from the two sources are orthogonal to each other. In this way, the cooperative interference channel is reduced to two independent broadcast channels. The bandwidth of each source node is divided into orthogonal sub-channels, and results from parallel broadcast channel is used to find the optimal allocation of power and rate to each links. We propose an iterative algorithm that maximizes the weighted sum rate, and plot the achievable rate region.

We propose an opportunistic power control (OPC) algorithm with rate adaptation. It exploits channel variation and transmits opportunistically to optimize system performance. We show that it can be used to support delay-sensitive services like video conference applications. It works well when the wireless channel is changing moderately fast. For slowly varying channels, OPC yields good performance when dumb antenna is used. It outperforms the traditional target tracking approach in terms of both user capacity and power consumption.

We investigate synchronous iterative waterfilling power allocation algorithm for parallel Gaussian interference channels. Mobile terminals are allowed to update their powers in a fully distributed manner We show that a Nash equilibrium always exists in such a system. Some sufficient conditions for convergence are also derived.

We can achieve all points in the capacity region of Gaussian multiple access channels by successive decoding and time-sharing. We discuss how to choose a particular point that is both Pareto optimal and fair to all users. The definition of our criterion of fairness is based on the theory of majorization. In economics, it is also known as the Lorenz order, which is used for measuring disparity in income distribution. We show that a unique solution according to such criterion exists in a large class of Gaussian multiple access channels. It turns out that the fair solution is the same as the well-known Nash bargaining solution. These two notions of fairness coincide due to the special structure of the capacity region. This provides a strong reason that we should pick it as the operational point. We also devise a fast algorithm that computes this point in some special cases

The problem of power control and signature sequence adaptation in code-division multiple-access (CDMA) systems is studied under a game-theoretic framework. Each user tries to maximize his own utility function, which may be different from others. Sufficient conditions for the existence of an equilibrium point in this multi-objective optimization problem are identified. The methodology for analyzing this class of problems is illustrated by examples.

An opportunistic power control algorithm was proposed in (C. W. Sund and K. K Leung, June 2004). While it provides significant throughput improvement, fairness has been a major challenge. In this paper, we propose an opportunistic power control algorithm with fairness consideration. Alongside the throughput enhancement of the power control algorithm, we prove the uniqueness, convergence and continuity properties of its fixed point

This paper considers the phase control problem in multiple-input single-output antenna system (MISO) with finite number of control bits. We propose an optimal algorithm which requires only O(nTlog nT) of computations, where nTis the number of transmit (input) antennas

Most power control algorithms that aim at hitting a signal-to-interference ratio (SIR) target fall within Yates' framework. However, for delay-tolerable applications, it is unnecessary to maintain the SIR at a certain level all the time. To maximize throughput, one should increase one's power when the interference level is low, and the information transmission rate is adjusted accordingly by adaptive modulation and coding techniques. This approach is called opportunistic communications. In this paper, we generalize Yates' result and establish a new framework, which is applicable to systems supporting opportunistic communications and with heterogeneous service requirements. Simulation results show that our proposed algorithm yields significant improvement in throughput when compared with the conventional target tracking approach.

When considering mobile communication systems we see that for services which can tolerate delay do not need to maintain a minimum signal-to-interference ratio (SIR). In fact, to achieve maximum throughput transmission power should be increased when the interference level is low, and information transmission rate adjusted accordingly through adaptive modulation and coding. This approach is called opportunistic communications. In this paper, we introduce an opportunistic power control algorithm, which exploits the channel fluctuation of wireless channels. The algorithm is distributed and is proven to converge to a unique fixed point. Simulation results show that a significant increase in system capacity can be achieved, when compared with the traditional target tracking approach.

We consider the convergence issues of distributed power-control algorithms for mobile cellular systems. A convergence theorem for power-control algorithms of canonical type is proved. Our result generalizes Yates' framework and provides a new outlook on the problem. The general applicability of the theorem is demonstrated by showing that many well-known distributed algorithms are canonical. Furthermore, by devising some new discrete algorithms, we exemplify how the theorem can be used to aid new design.

A mobile infostation network stipulates all transmissions to occur when nodes are in proximity. We evaluate the effect of mobility on highway mobile infostation networks. Each node enters a highway segment at a Poisson rate with a constant speed drawn from a known but arbitrary distribution. Both forward and reverse traffic are considered. For node speed that is uniformly distributed, the expected fraction of connection time, or expected number of connections in queueing terminology, is independent of observer node speed for reverse traffic, while it increases with observer node speed for forward traffic. We also extend our mobility model such that each node changes speed at each highway segment. The long run fraction of connection time of an observer node is dependent on the ratio of transmit range and connection time limit. Forward traffic connection yields better performance when the ratio is small and vice versa. We also compute the optimal transmit range and the corresponding data rate for both traffic types. We conclude that forward traffic connections yield much higher data rate in most scenarios.

In mobile ad hoc networks, it is often more important to optimize for energy efficiency than throughput. In this paper we investigate the effect of transmit range on energy efficiency of packet transmissions. We determine a common range for all nodes such that the average energy expenditure per received packet is minimized. In the first part of this paper, we consider stationary networks. We show that energy efficiency depends on various system parameters that includes path loss exponent of the channel, energy dissipation model and network offered load. In particular, when the path loss exponent is large, energy efficiency decreases when the transmit range increases. Hence, the network should be operated at the critical range that just maintains network connectivity. However, when the path loss exponent is small, operating at the critical range yields inferior throughput and energy efficiency. Our results show that energy efficiency is intimately connected to network connectivity. Three network connectivity regimes are identified as the transmit range of all nodes increases. In the second part, we examine the effect of node mobility on energy efficiency. We show that at normal offered load, an optimal transmit range exists such that energy efficiency is maximized The optimal range turns out to be insensitive to node mobility, and is much larger than the critical range. We show that the energy expenditure can be reduced by 15% to 73% in different mobility scenarios, if the network is operated at the optimal range.

In a mobile infostation network, any two nodes communicate when they are in proximity. Under this transmission constraint, any pair of nodes is intermittently connected as mobility shuffles the node locations. In this paper, we evaluate the effect of node mobility on highway mobile infostation networks. Each node enters a highway segment at a Poisson rate with a random speed drawn from a known but arbitrary distribution. Moreover, each node changes speed at each highway segment. Since nodes have different speed, a node may overtake other nodes or be overtaken as time evolves. Using arguments from renewal reward theory, the long run fraction of time an observer node is connected, and the long run average data rate can be derived. In this paper, however, we consider the special case of no speed change in each highway segment. In this case, the performance metrics are functions of the observer node speed. We consider both forward traffic scenarios, in which two nodes moving in the same direction have a transient connection when they are within range from each other, and reverse traffic scenarios in which two nodes travelling in opposite directions are connected transiently when they are in range. For node speed that is uniformly distributed, we reveal that the expected fraction of connection time, or expected number of connections in queuing terminology, is independent of the observer node speed in reverse traffic. In forward traffic, on the other hand, the fraction of connection time increases with observer speed. That is, the network performance improves with node mobility, which is unique to the mobile infostation networking paradigm.

We consider the sequence adaptation problem for cellular asynchronous code-division multiple-access (CDMA) systems. A game-theoretic approach is used to investigate the stability issues of distributed adaptation algorithms. It is shown that the Nash equilibrium may not exist for cellular CDMA systems if the traditional interference measure is used. In turn we propose a new interference measure which ensures system stability.

The effect of handoff techniques on fade margin is investigated. We provide an accurate comparison for soft and hard handoffs in a two-cell system. An upper bound on the fade margin for hard-handoff systems is derived and an approximation formula is obtained empirically. Simulation results show that this approximation is very accurate over reasonable ranges of system parameters. Extension of our analysis to multiple-cell systems are illustrated using a three-cell system as an example.

The authors consider a multirate code-division multiple acess system, in which all users have the same chip rate and vary their data rate by adjusting the processing gain. The receivers are assumed to be implemented using conventional matched filters, whose performance is sensitive to the received power levels. The authors' goal is to maximize the total system throughput by means of power control. A game theoretic approach is adopted. It is shown that for a certain type of pricing function, a unique Nash equilibrium solution exists and it possesses nice global properties. For example, it can be shown that for the optimal solution a high-rate connection should maintain a higher energy per bit than low-rate ones. The asymptotic spectral efficiency is also derived.

For a given set of background interference signals, it is well known that the optimal sequence can be obtained by solving an eigenvalue problem. However, one usual practical constraint on the sequences is that the sequence elements should have a constant amplitude. We show that when the choice is limited to binary sequences, the sequence assignment problem is NP-hard. We propose a local search method to find suboptimal solutions. This method can also be applied when polyphase sequences are used. Performance evaluation when applied to multipath channels is made.

The relation between interference reduction and capacity maximization in DS-CDMA systems is investigated. We show that the solution which minimizes the total weighted squared correlation (TWSC) happens to maximize the sum capacity of the system. Furthermore, we show that a distributed sequence adaptation algorithm based on the MMSE receiver reduces TWSC and increases sum capacity simultaneously at each iteration step. Simulation results show that the algorithm converges to the optimal solution.

In mobile radio communication systems, the power control algorithm adjusts the power of mobile users in order to make the signal to interference ratio (SIR) higher than a predefined threshold. Distributed algorithms are devised to solve the power control problem, using locally available quantities such as measured SIR. This paper studies the effect and impact of power quantization on the stability of these algorithms. In the IS-95 1-bit power control algorithm, the power trajectory goes up and down and will never stabilize on a power level. The usual notion of convergence in continuous power control algorithm may not apply in the discrete case. We address, the problem of whether the power of each mobile user fluctuates around the desired value. A new criterion is defined to measure the stability. This criterion is applied to three discrete power control algorithms and their stabilities are compared.

We consider the convergence issues of distributed power control algorithms for mobile cellular systems. A convergence theorem for power control algorithms of canonical type is proven. Our result generalizes Yates' (1995) framework and provides a new outlook on the problem. The general applicability of the theorem is demonstrated by showing that all the well-known algorithms are canonical. Furthermore, by devising a new discrete algorithm, we exemplify how the theorem can be used to aid new design.

A game theoretic approach is used to investigate the stability of distributed adaptation algorithms. We show that for cellular CDMA systems, Nash equilibria may not exist. On the other hand, for single-cell systems, there are multiple Nash equilibria. None of them is better than the others in the Pareto sense. Furthermore, the behavior of a distributed algorithm based on an MMSE receiver is studied. Simulation results show that it converges to the Nash equilibrium which maximizes sum capacity.

We consider a wireless multimedia code-division multiple-access system, in which the terminals transmit at different rates. We formulate the problem as a constrained optimization problem, with the objective of maximizing the total effective rate. An optimal power control strategy is derived. When the scale of the system is large, the optimal solution takes a simple form, which is easy to be applied practically. Furthermore, our basic model can be extended to include delay-sensitive traffic.

We consider a wireless multimedia CDMA system, in which the terminals transmit at different rates. We formulate the problem as a constrained optimization problem, with the objective of maximizing the total effective rate. An optimal power control strategy is derived. When the scale of the system is large, the optimal solution takes a simple form, which is easy to be applied practically. Furthermore, our basic model can be extended to include delay-sensitive traffic. We have shown that the problem can be decoupled and our results are still valid in the general model.

The huge amount of handoffs generated by microcells creates a problem for the future PCN. To alleviate the problem, we propose a hierarchical cellular system which comprises cells of different sizes. Ideally, one would like to use large cells to serve high-mobility users. A challenging issue is to obtain a good estimate of the user speed. A simple speed estimation is proposed and based on this estimate one can implement a number of dynamic channel allocation algorithms on such a hierarchical network. A comparative study of these algorithms will be presented based on a detailed simulation model.>