Search

We present a framework for random access that is based on three elements: physical-layer network coding (PLNC), signature codes, and tree splitting. In presence of a collision, physical-layer network coding enables the receiver to decode, i.e., compute, the sum of the packets that were transmitted by the individual users. For each user, the packet consists of the user’s signature, as well as the data that the user wants to communicate. As long as no more than $K$ users collide, their identities can be recovered from the sum of their signatures. This framework for creating and transmitting packets can be used as a fundamental building block in random access algorithms, since it helps to deal efficiently with the uncertainty of the set of contending terminals. In this paper, we show how to apply the framework in conjunction with a tree-splitting algorithm, which is required to deal with the case that more than $K$ users collide. We demonstrate that our approach achieves throughput that tends to 1 rapidly as $K$ increases. We also present results on net data-rate of the system, showing the impact of the overheads of the constituent elements of the proposed protocol. We compare the performance of our scheme with an upper bound that is obtained under the assumption that the active users are a priori known. Also, we consider an upper bound on the net data-rate for any PLNC-based strategy in which one linear equation per slot is decoded. We show that already at modest packet lengths, the net data-rate of our scheme becomes close to the second upper bound, i.e., the overhead of the contention resolution algorithm and the signature codes vanishes. [ABSTRACT FROM AUTHOR]

In this paper, we propose a new coding scheme and establish new bounds on the capacity region for the multi-sender unicast index-coding problem. We revisit existing partitioned distributed composite coding (DCC) proposed by Sadeghi et al. and identify its limitations in the implementation of multi-sender composite coding and in the strategy of sender partitioning. We then propose two new coding components to overcome these limitations and develop a multi-sender cooperative composite coding (CCC). We show that CCC can strictly improve upon partitioned DCC, and is the key to achieve optimality for a number of index-coding instances. The usefulness of CCC and its special cases is illuminated via non-trivial examples, and the capacity region is established for each example. Comparisons between CCC and other non-cooperative schemes in recent works are also provided to further demonstrate the advantage of CCC. [ABSTRACT FROM AUTHOR]

Consider two remote nodes having binary sequences $X$ and Y$ , respectively. Y$ is an edited version of , where the editing involves random deletions, insertions, and substitutions, possibly in bursts. The goal is for the node with Y$ to reconstruct X$ with minimal exchange of information over a noiseless link. The communication is measured in terms of both the total number of bits exchanged and the number of interactive rounds of communication. This paper focuses on the setting where the number of edits is , where $n$ is the length of $X$ . We first consider the case where the edits are a mixture of insertions and deletions (indels), and propose an interactive synchronization algorithm with near-optimal communication rate and average computational complexity of $O(n)$ arithmetic operations. The algorithm uses interaction to efficiently split the source sequence into substrings containing exactly one deletion or insertion. Each of these substrings is then synchronized using an optimal one-way algorithm based on the single-deletion correcting channel codes of Varshamov and Tenengolts. We then build on this synchronization algorithm in three different ways. First, it is modified to work with a single round of interaction. The reduction in the number of rounds comes at the expense of higher communication, which is quantified. Next, we present an extension to the practically important case where the insertions and deletions may occur in (potentially large) bursts. Finally, we show how to synchronize the sources to within a target Hamming distance. This feature can be used to differentiate between substitution and indel edits. In addition to theoretical performance bounds, we provide several validating simulation results for the proposed algorithms. [ABSTRACT FROM PUBLISHER]

This paper investigates basic trade-offs between energy and delay in wireless communication systems using finite blocklength theory. We first assume that data arrive in constant stream of bits, which are put into packets and transmitted over a communications link. Our results show that depending on exactly how energy is measured, in general energy depends on $\sqrt {d^{-1}}$ or $\sqrt {d^{-1}\log {d}}$ , where $d$ is the delay. This means that the energy decreases quite slowly with increasing delay. Furthermore, to approach the absolute minimum of −1.59 dB on energy, bandwidth has to increase very rapidly, much more than what is predicted by infinite blocklength theory. We then consider the scenario when data arrive stochastically in packets and can be queued. We devise a scheduling algorithm based on finite blocklength theory and develop bounds for the energy-delay performance. Our results again show that the energy decreases quite slowly with increasing delay. [ABSTRACT FROM AUTHOR]

We consider a wireless device-to-device caching network where n nodes are placed on a regular grid of area A\left ({n}\right) . Each node caches L_{C}F$ (coded) bits from a library of size LF$ bits, where L$ is the number of files and F ). Moreover, we propose a cache-induced hierarchical cooperation scheme and associated cache content placement optimization algorithm to achieve the optimal per-node capacity scaling law. When the path loss exponent $\alpha <3$ , the optimal per-node capacity scaling law achieved by the cache-induced hierarchical cooperation can be significantly better than that achieved by the existing state-of-the-art schemes. To the best of our knowledge, this is the first work that completely characterizes the per-node capacity scaling law for wireless caching networks under the physical model and Zipf distribution with an arbitrary skewness parameter $\tau $ . While scaling law analysis yields clean results, it may not accurately reflect the throughput performance of a large network with a finite number of nodes. Therefore, we also analyze the throughput of the proposed cache-induced hierarchical cooperation for networks of practical size. The analysis and simulations verify that cache-induced hierarchical cooperation can also achieve a large throughput gain over the cache-assisted multihop scheme for networks of practical size. [ABSTRACT FROM PUBLISHER]

We study the problem of private key generation in a cooperative pairwise independent network (PIN), with $M+2$ terminals (Alice, Bob, and $M$ relays), $M\geq 2$ . In the PIN, the correlated source observed by every pair of terminals is independent of the sources observed by any other pairs of terminals. Moreover, all terminals can communicate with each other over a public channel, which is also observed by Eve, noiselessly. The objective is to generate a private key between Alice and Bob with the help of the $M$ relays; such a private key needs to be protected not only from Eve but also from all relays. A single-letter expression for the private key capacity of this PIN model is obtained, where the achievability part is established by proposing a random binning (RB)-based key generation algorithm, and the converse part is established by deriving upper bounds of $M$ enhanced source models. Next, we consider a cooperative wireless network and use the estimates of fading channels to generate private keys. It has been shown that the proposed RB key generation algorithm can achieve a multiplexing gain of $M-1$ , which is an improvement compared with the existing XOR algorithm, whose achievable multiplexing gain is $\lfloor M /2\rfloor $ . [ABSTRACT FROM PUBLISHER]