Search

Federated learning aims to construct a global model that fits the dataset distributed across local devices without direct access to private data, leveraging communication between a server and the local devices. In the context of a practical communication scheme, we study the completion time required to achieve a target performance. Specifically, we analyze the number of iterations required for federated learning to reach a specific optimality gap from a minimum global loss. Subsequently, we characterize the time required for each iteration under two fundamental multiple access schemes: time-division multiple access (TDMA) and random access (RA). We propose a step-wise batch allocation, demonstrated to be optimal for TDMA-based federated learning systems. Additionally, we show that the non-zero batch gap between devices provided by the proposed step-wise batch allocation significantly reduces the completion time for RA-based learning systems. Numerical evaluations validate these analytical results through real-data experiments, highlighting the remarkable potential for substantial completion time reduction.

We consider a multi-user multi-server mobile edge computing (MEC) system, in which users arrive on a network randomly over time and generate computation tasks, which will be computed either locally on their own computing devices or be offloaded to one of the MEC servers. Under such a dynamic network environment, we propose a novel task offloading policy based on hybrid online-offline learning, which can efficiently reduce the overall computation delay and energy consumption only with information available at nearest MEC servers from each user. We provide a practical signaling and learning framework that can train deep neural networks for both online and offline learning and can adjust its offloading policy based on the queuing status of each MEC server and network dynamics. Numerical results demonstrate that the proposed scheme significantly reduces the average computation delay for a broad class of network environments compared to the conventional offloading methods. It is further shown that the proposed hybrid online-offline learning framework can be extended to a general cost function reflecting both delay and energy-dependent metrics., Comment: accepted by IEEE Transactions on Wireless Communications

In the upcoming 6G era, multiple access (MA) will play an essential role in achieving high throughput performances required in a wide range of wireless applications. Since MA and interference management are closely related issues, the conventional MA techniques are limited in that they cannot provide near-optimal performance in universal interference regimes. Recently, rate-splitting multiple access (RSMA) has been gaining much attention. RSMA splits an individual message into two parts: a common part, decodable by every user, and a private part, decodable only by the intended user. Each user first decodes the common message and then decodes its private message by applying successive interference cancellation (SIC). By doing so, RSMA not only embraces the existing MA techniques as special cases but also provides significant performance gains by efficiently mitigating inter-user interference in a broad range of interference regimes. In this article, we first present the theoretical foundation of RSMA. Subsequently, we put forth four key benefits of RSMA: spectral efficiency, robustness, scalability, and flexibility. Upon this, we describe how RSMA can enable ten promising scenarios and applications along with future research directions to pave the way for 6G., Comment: 17 pages, 6 figures, submitted to IEEE Network Magazine

Crowdsourcing is an emerging computing paradigm that takes advantage of the intelligence of a crowd to solve complex problems effectively. Besides collecting and processing data, it is also a great demand for the crowd to conduct optimization. Inspired by this, this paper intends to introduce crowdsourcing into evolutionary computation (EC) to propose a crowdsourcing-based evolutionary computation (CEC) paradigm for distributed optimization. EC is helpful for optimization tasks of crowdsourcing and in turn, crowdsourcing can break the spatial limitation of EC for large-scale distributed optimization. Therefore, this paper firstly introduces the paradigm of crowdsourcing-based distributed optimization. Then, CEC is elaborated. CEC performs optimization based on a server and a group of workers, in which the server dispatches a large task to workers. Workers search for promising solutions through EC optimizers and cooperate with connected neighbors. To eliminate uncertainties brought by the heterogeneity of worker behaviors and devices, the server adopts the competitive ranking and uncertainty detection strategy to guide the cooperation of workers. To illustrate the satisfactory performance of CEC, a crowdsourcing-based swarm optimizer is implemented as an example for extensive experiments. Comparison results on benchmark functions and a distributed clustering optimization problem demonstrate the potential applications of CEC.

We consider reconfigurable intelligent surface (RIS) aided sixth-generation (6G) terahertz (THz) communications for indoor environment in which a base station (BS) wishes to send independent messages to its serving users with the help of multiple RISs. For indoor environment, various obstacles such as pillars, walls, and other objects can result in no line-of-sight signal path between the BS and a user, which can significantly degrade performance. To overcome such limitation of indoor THz communication, we firstly optimize the placement of RISs to maximize the coverage area. Under the optimized RIS placement, we propose 3D hybrid beamforming at the BS and phase adjustment at RISs, which are jointly performed at the BS and RISs via codebook-based 3D beam scanning with low complexity. Numerical simulations demonstrate that the proposed scheme significantly improves the average sum rate compared to the cases of no RIS and randomly deployed RISs. It is further shown that the proposed codebook-based 3D beam scanning efficiently aligns analog beams between BS--user links or BS--RIS--user links and, as a consequence, achieves the average sum rate close to that of coherent beam alignment requiring global channel state information., Comment: This manuscript contains 18 pages and 9 figures

A new interference management scheme based on integer forcing (IF) receivers is studied for the two-user multiple-input and multiple-output (MIMO) interference channel. The proposed scheme employs a message splitting method that divides each data stream into common and private sub-streams, in which the private stream is recovered by the dedicated receiver only while the common stream is required to be recovered by both receivers. Specifically, to enable IF sum decoding at the receiver side, all streams are encoded using the same lattice code. Additionally, the number of common and private streams of each user is carefully determined by considering the number of antennas at transmitters and receivers, the channel matrices, and the effective signal-to-noise ratio (SNR) at each receiver to maximize the achievable rate. Furthermore, we consider various assumptions of channel state information at the transmitter side (CSIT) and propose low-complexity linear transmit beamforming suitable for each CSIT assumption. The achievable sum rate and rate region are analytically derived and extensively evaluated by simulation for various environments, demonstrating that the proposed interference management scheme strictly outperforms the previous benchmark schemes in a wide range of channel parameters due to the gain from IF sum decoding., Comment: Submitted to IEEE Trans. Wireless Commun. (in revision), 31 pages, 6 figures

We propose a hybrid coded modulation scheme which composes of inner and outer codes. The outer-code can be any standard binary linear code with efficient soft decoding capability (e.g. low-density parity-check (LDPC) codes). The inner code is designed using a deep neural network (DNN) which takes the channel coded bits and outputs modulated symbols. For training the DNN, we propose to use a loss function that is inspired by the generalized mutual information. The resulting constellations are shown to outperform the conventional quadrature amplitude modulation (QAM) based coding scheme for modulation order 16 and 64 with 5G standard LDPC codes.

We consider a multichannel random access system in which each user accesses a single channel at each time slot to communicate with an access point (AP). Users arrive to the system at random and be activated for a certain period of time slots and then disappear from the system. Under such dynamic network environment, we propose a distributed multichannel access protocol based on multi-agent reinforcement learning (RL) to improve both throughput and fairness between active users. Unlike the previous approaches adjusting channel access probabilities at each time slot, the proposed RL algorithm deterministically selects a set of channel access policies for several consecutive time slots. To effectively reduce the complexity of the proposed RL algorithm, we adopt a branching dueling Q-network architecture and propose an efficient training methodology for producing proper Q-values over time-varying user sets. We perform extensive simulations on realistic traffic environments and demonstrate that the proposed online learning improves both throughput and fairness compared to the conventional RL approaches and centralized scheduling policies., Comment: 20 pages, 12 figures

This paper proposes an adaptive transmission algorithm for slotted random access systems supporting the successive interference cancellation (SIC) at the access point (AP). When multiple users transmit packets simultaneously in a slot, owing to the SIC technique, the AP is able to decode them through SIC resolve procedures (SRPs), which may occupy multiple consequent slots. While such an SRP could potentially improve the system throughput, how to fully exploit this capability in practical systems is still questionable. In particular, the number of active users contending for the channel varies over time which complicates the algorithm design. By fully exploiting the potential of SIC, the proposed algorithm is designed to maximize the system throughput and minimize the access delay. For this purpose, an online estimation is introduced to estimate the number of active users in real-time and controls their transmissions accordingly. It is shown that the throughput of the proposed algorithm can reach up to 0.693 packets/slot under practical assumptions, which is the first result achieving the throughput limit proved by Yu-Giannakis. It is further shown that the system throughput of 0.559 packets/slot (80.6$\%$ of the throughput limit) is still achievable when the SIC capability is restricted by two., Comment: 16 pages, 10 figures, submitted to ISIT 2020

In this paper, we study an aerial drone base station (DBS) assisted cellular network that consists of a single ground macro base station (MBS), multiple DBSs, and multiple ground terminals (GT). We assume that the MBS transmits to the DBSs and the GTs in the licensed band while the DBSs use a separate unlicensed band (e.g. Wi-Fi) to transmit to the GTs. For the utilization of the DBSs, we propose a cooperative decode--forward (DF) protocol in which multiple DBSs assist the terminals simultaneously while maintaining a predetermined interference level on the coexisting unlicensed band users. For our network setup, we formulate a joint optimization problem for minimizing the aggregate gap between the target rates and the throughputs of terminals by optimizing over the 3D positions of the DBSs and the resources (power, time, bandwidth) of the network. To solve the optimization problem, we propose an efficient nested structured algorithm based on particle swarm optimization and convex optimization methods. Extensive numerical evaluations of the proposed algorithm is performed considering various aspects to demonstrate the performance of our algorithm and the gain for utilizing DBSs., Comment: 26 pages, 10 figures

Content-centric mobile hybrid Internet-of-Things (IoT) networks consisting of mobile devices and static femto access points (FAPs) are studied, where each device moves according to the random walk mobility model and requests a content object from the library independently at random according to a Zipf popularity distribution. Instead of allowing access to content objects at macro base stations via costly backhaul providing connection to the core network, we consider a more practical scenario where mobile devices and static FAPs, each having a finite-size cache space, are able to cache a subset of content objects so that each request is served by other mobile devices or static FAPs. Under a general multihop-based content delivery protocol, we analyze the order-optimal throughput--delay trade-off by presenting a new cache allocation strategy. In particular, under a given caching strategy, we first characterize a throughput--delay trade-off in terms of scaling laws along with the general content delivery multihop routing protocol. Then, the order-optimal throughput--delay trade-off is characterized by presenting the order-optimal cache allocation strategy, which jointly finds the replication sets at mobile devices and static FAPs via a novel variable decoupling approach. In our mobile IoT network, an interesting observation is that highly popular content objects are mainly served by mobile devices while the rest of content objects are served by static FAPs. We perform numerical evaluation to validate our analytical results. We also show that the order-optimal strategy strictly outperforms a baseline approach, where the replication sets at mobile devices and static FAPs are optimized separately., Comment: 18 pages, 7 figures, this paper is to be published in the IEEE Access and was presented in part at the IEEE International Symposium on Information Theory, Barcelona, Spain, July 2016

This paper studies the degrees of freedom of full-duplex multicell networks that share the spectrum among multiple cells in a non-orthogonal setting. In the considered network, we assume that {\em full-duplex} base stations with multiple transmit and receive antennas communicate with multiple single-antenna mobile users. By spectrum sharing among multiple cells and (simultaneously) enabling full-duplex radio, the network can utilize the spectrum more flexibly, but, at the same time, the network is subject to multiple sources of interference compared to a network with separately dedicated bands for distinct cells and uplink--downlink traffic. Consequently, to take advantage of the additional freedom in utilizing the spectrum, interference management is a crucial ingredient. In this work, we propose a novel strategy based on interference alignment which takes into account inter-cell interference and intra-cell interference caused by spectrum sharing and full-duplex to establish a general achievability result on the sum degrees of freedom of the considered network. Paired with an upper bound on the sum degrees of freedom, which is tight under certain conditions, we demonstrate how spectrum sharing and full-duplex can significantly improve the throughput over conventional cellular networks, especially for a network with large number of users and/or cells., Comment: 20 pages, 6 figures, submitted to IEEE Journal on Selected Areas in Communications

Full-duplex (FD) cellular networks are considered in which a FD base station (BS) simultaneously supports a set of half-duplex (HD) downlink (DL) users and a set of HD uplink (UL) users. The transmitter and the receiver of the BS are equipped with reconfigurable antennas, each of which can choose its transmit or receive mode from several preset modes. Under the no self-interference assumption arisen from FD operation at the BS, the sum degrees of freedom (DoF) of FD cellular networks is investigated for both no channel state information at the transmit side (CSIT) and partial CSIT. In particular, the sum DoF is completely characterized for no CSIT model and an achievable sum DoF is established for the partial CSIT model, which improves the sum DoF of the conventional HD cellular networks. For both no CSIT and partial CSIT models, the results show that the FD BS with reconfigurable antennas can double the sum DoF even in the presence of user-to-user interference as both the numbers of DL and UL users and preset modes increase. It is further demonstrated that such DoF improvement indeed yields the sum rate improvement at the finite and operational signal-to-noise ratio regime., Comment: Submitted to IEEE Transactions on Wireless Communications

We consider a wireless device-to-device (D2D) network where $n$ nodes are uniformly distributed at random over the network area. We let each node with storage capacity $M$ cache files from a library of size $m \geq M$. Each node in the network requests a file from the library independently at random, according to a popularity distribution, and is served by other nodes having the requested file in their local cache via (possibly) multihop transmissions. Under the classical "protocol model" of wireless networks, we characterize the optimal per-node capacity scaling law for a broad class of heavy-tailed popularity distributions including Zipf distributions with exponent less than one. In the parameter regimes of interest, we show that a decentralized random caching strategy with uniform probability over the library yields the optimal per-node capacity scaling of $\Theta(\sqrt{M/m})$, which is constant with $n$, thus yielding throughput scalability with the network size. Furthermore, the multihop capacity scaling can be significantly better than for the case of single-hop caching networks, for which the per-node capacity is $\Theta(M/m)$. The multihop capacity scaling law can be further improved for a Zipf distribution with exponent larger than some threshold $> 1$, by using a decentralized random caching uniformly across a subset of most popular files in the library. Namely, ignoring a subset of less popular files (i.e., effectively reducing the size of the library) can significantly improve the throughput scaling while guaranteeing that all nodes will be served with high probability as $n$ increases., Comment: 21 pages, 5 figures, submitted to IEEE Transactions on Information Theory

Throughput scaling laws of an ad hoc network equipping directional antennas at each node are analyzed. More specifically, this paper considers a general framework in which the beam width of each node can scale at an arbitrary rate relative to the number of nodes. We introduce an elastic routing protocol, which enables to increase per-hop distance elastically according to the beam width, while maintaining an average signal-to-interference-and-noise ratio at each receiver as a constant. We then identify fundamental operating regimes characterized according to the beam width scaling and analyze throughput scaling laws for each of the regimes. The elastic routing is shown to achieve a much better throughput scaling law than that of the conventional nearest-neighbor multihop for all operating regimes. The gain comes from the fact that more source--destination pairs can be simultaneously activated as the beam width becomes narrower, which eventually leads to a linear throughput scaling law. In addition, our framework is applied to a hybrid network consisting of both wireless ad hoc nodes and infrastructure nodes. As a result, in the hybrid network, we analyze a further improved throughput scaling law and identify the operating regime where the use of directional antennas is beneficial., Comment: 21 pages, 10 figures, Submitted to IEEE Transactions on Mobile Computing. Part of this paper was presented at the IEEE International Symposium on Information Theory, Honolulu, HI, June/July 2014

We study the degrees of freedom (DoF) of cellular networks in which a full duplex (FD) base station (BS) equipped with multiple transmit and receive antennas communicates with multiple mobile users. We consider two different scenarios. In the first scenario, we study the case when half duplex (HD) users, partitioned to either the uplink (UL) set or the downlink (DL) set, simultaneously communicate with the FD BS. In the second scenario, we study the case when FD users simultaneously communicate UL and DL data with the FD BS. Unlike conventional HD only systems, inter-user interference (within the cell) may severely limit the DoF, and must be carefully taken into account. With the goal of providing theoretical guidelines for designing such FD systems, we completely characterize the sum DoF of each of the two different FD cellular networks by developing an achievable scheme and obtaining a matching upper bound. The key idea of the proposed scheme is to carefully allocate UL and DL information streams using interference alignment and beamforming techniques. By comparing the DoFs of the considered FD systems with those of the conventional HD systems, we establish the DoF gain by enabling FD operation in various configurations. As a consequence of the result, we show that the DoF can approach the two-fold gain over the HD systems when the number of users becomes large enough as compared to the number of antennas at the BS., Comment: 21 pages, 16 figures, a shorter version of this paper has been submitted to the IEEE International Symposium on Information Theory (ISIT) 2015

An interference management problem among multiple overlapped random access networks (RANs) is investigated, each of which operates with slotted ALOHA protocol. Assuming that access points and users have multiple antennas, a novel opportunistic interference alignment~(OIA) is proposed to mitigate interference among overlapped RANs. The proposed technique intelligently combines the transmit beamforming technique at the physical layer and the opportunistic packet transmission at the medium access control layer. The transmit beamforming is based on interference alignment and the opportunistic packet transmission is based on the generating interference of users to other RANs, which can be regarded as a joint optimization of the physical layer and the medium access control layer. It is shown that the proposed OIA protocol significantly outperforms the conventional schemes such as multi-packet reception and interference nulling., Comment: 12 pages, 8 figures, to appear in IEEE Transactions on Vehicular Technology

The feasibility conditions of interference alignment (IA) are analyzed for reverse TDD systems, i.e., one cell operates as downlink (DL) but the other cell operates as uplink (UL). Under general multiple-input and multiple-output (MIMO) antenna configurations, a necessary condition and a sufficient condition for one-shot linear IA are established, i.e., linear IA without symbol or time extension. In several example networks, optimal sum degrees of freedom (DoF) is characterized by the derived necessary condition and sufficient condition. For symmetric DoF within each cell, a sufficient condition is established in a more compact expression, which yields the necessary and sufficient condition for a class of symmetric DoF. An iterative construction of transmit and received beamforming vectors is further proposed, which provides a specific beamforming design satisfying one-shot IA. Simulation results demonstrate that the proposed IA not only achieve lager DoF but also significantly improve the sum rate in the practical signal-to-noise ratio (SNR) regime., Comment: 12 pages; 5 figures

The K-user multiple-input and multiple-output (MIMO) broadcast channel (BC) with no channel state information at the transmitter (CSIT) is considered, where each receiver is assumed to be equipped with reconfigurable antennas capable of choosing a subset of receiving modes from several preset modes. Under general antenna configurations, the sum linear degrees of freedom (LDoF) of the K-user MIMO BC with reconfigurable antennas is completely characterized, which corresponds to the maximum sum DoF achievable by linear coding strategies. The LDoF region is further characterized for a class of antenna configurations. Similar analysis is extended to the K-user MIMO interference channels with reconfigurable antennas and the sum LDoF is characterized for a class of antenna configurations., Comment: 25 pages, 7 figures, submitted to IEEE Transactions on Information Theory

An uplink-downlink two-cell cellular network is studied in which the first base station (BS) with $M_1$ antennas receives independent messages from its $N_1$ serving users, while the second BS with $M_2$ antennas transmits independent messages to its $N_2$ serving users. That is, the first and second cells operate as uplink and downlink, respectively. Each user is assumed to have a single antenna. Under this uplink-downlink setting, the sum degrees of freedom (DoF) is completely characterized as the minimum of $(N_1N_2+\min(M_1,N_1)(N_1-N_2)^++\min(M_2,N_2)(N_2-N_1)^+)/\max(N_1,N_2)$, $M_1+N_2,M_2+N_1$, $\max(M_1,M_2)$, and $\max(N_1,N_2)$, where $a^+$ denotes $\max(0,a)$. The result demonstrates that, for a broad class of network configurations, operating one of the two cells as uplink and the other cell as downlink can strictly improve the sum DoF compared to the conventional uplink or downlink operation, in which both cells operate as either uplink or downlink. The DoF gain from such uplink-downlink operation is further shown to be achievable for heterogeneous cellular networks having hotspots and with delayed channel state information., Comment: 22 pages, 11 figures, in revision for IEEE Transactions on Information Theory

Function computation of arbitrarily correlated discrete sources over Gaussian networks with orthogonal components is studied. Two classes of functions are considered: the arithmetic sum function and the type function. The arithmetic sum function in this paper is defined as a set of multiple weighted arithmetic sums, which includes averaging of the sources and estimating each of the sources as special cases. The type or frequency histogram function counts the number of occurrences of each argument, which yields many important statistics such as mean, variance, maximum, minimum, median, and so on. The proposed computation coding first abstracts Gaussian networks into the corresponding modulo sum multiple-access channels via nested lattice codes and linear network coding and then computes the desired function by using linear Slepian-Wolf source coding. For orthogonal Gaussian networks (with no broadcast and multiple-access components), the computation capacity is characterized for a class of networks. For Gaussian networks with multiple-access components (but no broadcast), an approximate computation capacity is characterized for a class of networks., Comment: 30 pages, 12 figures, submitted to IEEE Transactions on Information Theory

In wireless sensor networks, various applications involve learning one or multiple functions of the measurements observed by sensors, rather than the measurements themselves. This paper focuses on type-threshold functions, e.g., the maximum and indicator functions. Previous work studied this problem under the collocated collision network model and showed that under many probabilistic models for the measurements, the achievable computation rates converge to zero as the number of sensors increases. This paper considers two network models reflecting both the broadcast and superposition properties of wireless channels: the collocated linear finite field network and the collocated Gaussian network. A general multi-round coding scheme exploiting not only the broadcast property but particularly also the superposition property of the networks is developed. Through careful scheduling of concurrent transmissions to reduce redundancy, it is shown that given any independent measurement distribution, all type-threshold functions can be computed reliably with a non-vanishing rate in the collocated Gaussian network, even if the number of sensors tends to infinity., Comment: 21 pages, 4 figures, submitted to IEEE Transactions on Information Theory

We consider a fading AWGN 2-user 2-hop network where the channel coefficients are independent and identically distributed (i.i.d.) drawn from a continuous distribution and vary over time. For a broad class of channel distributions, we characterize the ergodic sum capacity to within a constant number of bits/sec/Hz, independent of signal-to-noise ratio. The achievability follows from the analysis of an interference neutralization scheme where the relays are partitioned into $M$ pairs, and interference is neutralized separately by each pair of relays. When $M=1$, the proposed ergodic interference neutralization characterizes the ergodic sum capacity to within $4$ bits/sec/Hz for i.i.d. uniform phase fading and approximately $4.7$ bits/sec/Hz for i.i.d. Rayleigh fading. We further show that this gap can be tightened to $4\log \pi-4$ bits/sec/Hz (approximately $2.6$) for i.i.d. uniform phase fading and $4-4\log( \frac{3\pi}{8})$ bits/sec/Hz (approximately $3.1$) for i.i.d. Rayleigh fading in the limit of large $M$., Comment: 22 pages, 8 figures, submitted to IEEE Transactions on Information Theory

We show that the 2x2x2 interference channel, i.e., the multihop interference channel formed by concatenation of two 2-user interference channels achieves the min-cut outer bound value of 2 DoF, for almost all values of channel coefficients, for both time-varying or fixed channel coefficients. The key to this result is a new idea, called aligned interference neutralization, that provides a way to align interference terms over each hop in a manner that allows them to be cancelled over the air at the last hop.

We study a layered $K$-user $M$-hop Gaussian relay network consisting of $K_m$ nodes in the $m^{\operatorname{th}}$ layer, where $M\geq2$ and $K=K_1=K_{M+1}$. We observe that the time-varying nature of wireless channels or fading can be exploited to mitigate the inter-user interference. The proposed amplify-and-forward relaying scheme exploits such channel variations and works for a wide class of channel distributions including Rayleigh fading. We show a general achievable degrees of freedom (DoF) region for this class of Gaussian relay networks. Specifically, the set of all $(d_1,..., d_K)$ such that $d_i\leq 1$ for all $i$ and $\sum_{i=1}^K d_i\leq K_{\Sigma}$ is achievable, where $d_i$ is the DoF of the $i^{\operatorname{th}}$ source--destination pair and $K_{\Sigma}$ is the maximum integer such that $K_{\Sigma}\leq \min_m\{K_m\}$ and $M/K_{\Sigma}$ is an integer. We show that surprisingly the achievable DoF region coincides with the cut-set outer bound if $M/\min_m\{K_m\}$ is an integer, thus interference-free communication is possible in terms of DoF. We further characterize an achievable DoF region assuming multi-antenna nodes and general message set, which again coincides with the cut-set outer bound for a certain class of networks., Comment: 19 pages, 5 figures, published in IEEE Transactions on Information Theory

We study a multi-source Gaussian relay network consisting of $K$ source--destination pairs having $K$ unicast sessions. We assume $M$ layers of relays between the sources and the destinations. We find achievable degrees of freedom of the network. Our schemes are based on interference alignment at the transmitters and symbol extension and opportunistic interference cancellation at the relays. For $K$-$L$-$K$ networks, i.e., 2-hop network with $L$ relays, we show $\min\{K,K/2+L/(2(K-1))\}$ degrees of freedom are achievable. For $K$-hop networks with $K$ relays in each layer, we show the full $K$ degrees of freedom are achievable provided that $K$ is even and the channel distribution satisfies a certain symmetry., Comment: 6 pages, 2 figures, presented at the 47-th Allerton Conference on Communication, Control, and Computing, 2009

Characterizing the capacity region of multi-source wireless relay networks is one of the fundamental issues in network information theory. The problem is, however, quite challenging due to inter-user interference when there exist multiple source--destination (S--D) pairs in the network. By focusing on a special class of networks, we show that the capacity can be found. Namely, we study a layered linear binary field network with time-varying channels, which is a simplified model reflecting broadcast, interference, and fading natures of wireless communications. We observe that fading can play an important role in mitigating inter-user interference effectively for both single-hop and multi-hop networks. We propose new encoding and relaying schemes with randomized channel pairing, which exploit such channel variations, and derive their achievable rates. By comparing them with the cut-set upper bound, the capacity region of single-hop networks and the sum capacity of multi-hop networks can be characterized for some classes of channel distributions and network topologies. For these classes, we show that the capacity region or sum capacity can be interpreted as the max-flow min-cut theorem., Comment: 19 pages, 7 figures, submitted to IEEE trans. on Information Theory

We study a fading linear finite-field relay network having multiple source-destination pairs. Because of the interference created by different unicast sessions, the problem of finding its capacity region is in general difficult. We observe that, since channels are time-varying, relays can deliver their received signals by waiting for appropriate channel realizations such that the destinations can decode their messages without interference. We propose a block Markov encoding and relaying scheme that exploits such channel variations. By deriving a general cut-set upper bound and an achievable rate region, we characterize the sum capacity for some classes of channel distributions and network topologies. For example, when the channels are uniformly distributed, the sum capacity is given by the minimum average rank of the channel matrices constructed by all cuts that separate the entire sources and destinations. We also describe other cases where the capacity is characterized., Comment: 5 pages, 2 figures, to appear in proc. IEEE ISIT, June 2009

We consider a wireless network in which a single source node located at the center of a unit area having $m$ antennas transmits messages to $n$ randomly located destination nodes in the same area having a single antenna each. To achieve the sum-rate proportional to $m$ by transmit beamforming, channel state information (CSI) is essentially required at the transmitter (CSIT), which is hard to obtain in practice because of the time-varying nature of the channels and feedback overhead. We show that, even without CSIT, the achievable sum-rate scales as $\Theta(m\log m)$ if a cooperation between receivers is allowed. By deriving the cut-set upper bound, we also show that $\Theta(m\log m)$ scaling is optimal. Specifically, for $n=\omega(m^2)$, the simple TDMA-based quantize-and-forward is enough to achieve the capacity scaling. For $n=\omega(m)$ and $n=\operatorname{O}(m^2)$, on the other hand, we apply the hierarchical cooperation to achieve the capacity scaling., Comment: Submitted to the IEEE Transactions on Information Theory

This paper analyzes the impact and benefits of infrastructure support in improving the throughput scaling in networks of $n$ randomly located wireless nodes. The infrastructure uses multi-antenna base stations (BSs), in which the number of BSs and the number of antennas at each BS can scale at arbitrary rates relative to $n$. Under the model, capacity scaling laws are analyzed for both dense and extended networks. Two BS-based routing schemes are first introduced in this study: an infrastructure-supported single-hop (ISH) routing protocol with multiple-access uplink and broadcast downlink and an infrastructure-supported multi-hop (IMH) routing protocol. Then, their achievable throughput scalings are analyzed. These schemes are compared against two conventional schemes without BSs: the multi-hop (MH) transmission and hierarchical cooperation (HC) schemes. It is shown that a linear throughput scaling is achieved in dense networks, as in the case without help of BSs. In contrast, the proposed BS-based routing schemes can, under realistic network conditions, improve the throughput scaling significantly in extended networks. The gain comes from the following advantages of these BS-based protocols. First, more nodes can transmit simultaneously in the proposed scheme than in the MH scheme if the number of BSs and the number of antennas are large enough. Second, by improving the long-distance signal-to-noise ratio (SNR), the received signal power can be larger than that of the HC, enabling a better throughput scaling under extended networks. Furthermore, by deriving the corresponding information-theoretic cut-set upper bounds, it is shown under extended networks that a combination of four schemes IMH, ISH, MH, and HC is order-optimal in all operating regimes., Comment: 26 pages, 10 figures, 1 table, Under revision for IEEE Transactions on Information Theory

We study two distinct, but overlapping, networks that operate at the same time, space, and frequency. The first network consists of $n$ randomly distributed \emph{primary users}, which form either an ad hoc network, or an infrastructure-supported ad hoc network with $l$ additional base stations. The second network consists of $m$ randomly distributed, ad hoc secondary users or cognitive users. The primary users have priority access to the spectrum and do not need to change their communication protocol in the presence of secondary users. The secondary users, however, need to adjust their protocol based on knowledge about the locations of the primary nodes to bring little loss to the primary network's throughput. By introducing preservation regions around primary receivers and avoidance regions around primary base stations, we propose two modified multihop routing protocols for the cognitive users. Base on percolation theory, we show that when the secondary network is denser than the primary network, both networks can simultaneously achieve the same throughput scaling law as a stand-alone network. Furthermore, the primary network throughput is subject to only a vanishingly fractional loss. Specifically, for the ad hoc and the infrastructure-supported primary models, the primary network achieves sum throughputs of order $n^{1/2}$ and $\max\{n^{1/2},l\}$, respectively. For both primary network models, for any $\delta>0$, the secondary network can achieve sum throughput of order $m^{1/2-\delta}$ with an arbitrarily small fraction of outage. Thus, almost all secondary source-destination pairs can communicate at a rate of order $m^{-1/2-\delta}$., Comment: 28 pages, 12 figures, submitted to IEEE Trans. on Information Theory