We study an information-theoretic privacy mechanism design problem, where an agent observes useful data $Y$ that is arbitrarily correlated with sensitive data $X$, and design disclosed data $U$ generated from $Y$ (the agent has no direct access to $X$). We introduce \emph{sparse point-wise privacy leakage}, a worst-case privacy criterion that enforces two simultaneous constraints for every disclosed symbol $u\in\mathcal{U}$: (i) $u$ may be correlated with at most $N$ realizations of $X$, and (ii) the total leakage toward those realizations is bounded. In the high-privacy regime, we use concepts from information geometry to obtain a local quadratic approximation of mutual information which measures utility between $U$ and $Y$. When the leakage matrix $P_{X|Y}$ is invertible, this approximation reduces the design problem to a sparse quadratic maximization, known as the Rayleigh-quotient problem, with an $\ell_0$ constraint. We further show that, for the approximated problem, one can without loss of optimality restrict attention to a binary released variable $U$ with a uniform distribution. For small alphabet sizes, the exact sparsity-constrained optimum can be computed via combinatorial support enumeration, which quickly becomes intractable as the dimension grows. For general dimensions, the resulting sparse Rayleigh-quotient maximization is NP-hard and closely related to sparse principal component analysis (PCA). We propose a convex semidefinite programming (SDP) relaxation that is solvable in polynomial time and provides a tractable surrogate for the NP-hard design, together with a simple rounding procedure to recover a feasible leakage direction. We also identify a sparsity threshold beyond which the sparse optimum saturates at the unconstrained spectral value and the SDP relaxation becomes tight.

An information-theoretic privacy mechanism design is studied, where an agent observes useful data $Y$ which is correlated with the private data $X$. The agent wants to reveal the information to a user, hence, the agent utilizes a privacy mechanism to produce disclosed data $U$ that can be revealed. We assume that the agent has no direct access to $X$, i.e., the private data is hidden. We study privacy mechanism design that maximizes the disclosed information about $Y$, measured by the mutual information between $Y$ and $U$, while satisfying a point-wise constraint with different privacy leakage budgets. We introduce a new measure, called the \emph{multi-level point-wise leakage}, which allows us to impose different leakage levels for different realizations of $U$. In contrast to previous studies on point-wise measures, which use the same leakage level for each realization, we consider a more general scenario in which each data point can leak information up to a different threshold. As a result, this concept also covers cases in which some data points should not leak any information about the private data, i.e., they must satisfy perfect privacy. In other words, a combination of perfect privacy and non-zero leakage can be considered. When the leakage is sufficiently small, concepts from information geometry allow us to locally approximate the mutual information. We show that when the leakage matrix $P_{X|Y}$ is invertible, utilizing this approximation leads to a quadratic optimization problem that has closed-form solution under some constraints. In particular, we show that it is sufficient to consider only binary $U$ to attain the optimal utility. This leads to simple privacy designs with low complexity which are based on finding the maximum singular value and singular vector of a matrix.

We characterise bounds on the optimal broadcast rate for a few classes of pliable-index-coding instances. Unlike the majority of currently solved instances, which belong to a special class where all receivers with a certain side-information cardinality are either present or absent, we consider more general instances without this constraint. We devise a novel algorithm that constructs a decoding chain by iteratively adding a message that can be decoded by a receiver whose side information is already in the chain. If the decoding chain cannot proceed due to the absence of a receiver with the required messages, weskipa message by adding it to the chain regardless. We prove that a lower bound on the optimal broadcast rate is a function of the number of skipped messages, across all possible decoding choices of the receivers and any realisation of the algorithm for each decoding choice. While this result is not computationally feasible in isolation, it serves as a basis for deriving explicit lower bounds on the broadcast rate for specific classes of pliable-index-coding instances. These lower bounds depend on the number of absent receivers or the pattern of their side-information sets. Specifically, we explicitly characterise the optimal broadcast rate for instances with up to and including four absent receivers with any side-information pattern, as well as instances where the side-information sets are nested in particular ways.

This paper explores the implications of guaranteeing privacy by imposing a lower bound on the information density between the private and the public data. We introduce a novel and operationally meaningful privacy measure calledpointwise maximal cost(PMC) and demonstrate that imposing an upper bound on PMC is equivalent to enforcing a lower bound on the information density. PMC quantifies the information leakage about a secret to adversaries who aim to minimize non-negative cost functions after observing the outcome of a privacy mechanism. When restricted to finite alphabets, PMC can equivalently be defined as the information leakage to adversaries aiming to minimize the probability of incorrectly guessing randomized functions of the secret. We study the properties of PMC and apply it to standard privacy mechanisms to demonstrate its practical relevance. Through a detailed examination, we connect PMC with other privacy measures that impose upper or lower bounds on the information density. These are pointwise maximal leakage (PML), local differential privacy (LDP), and (asymmetric) local information privacy. In particular, we show that a mechanism satisfies LDP if and only if it has both bounded PMC and bounded PML. Overall, our work fills a conceptual and operational gap in the taxonomy of privacy measures, bridges existing disconnects between different frameworks, and offers insights for selecting a suitable notion of privacy in a given application.

In this paper, we propose an extended framework for quantitative information flow (QIF), aligned with the previously proposed core-concave generalization of entropy measures, to include adversaries that use Kolmogorov-Nagumo$f$-mean to infer secrets in a private system. Specifically, in our setting, an adversary uses Kolmogorov-Nagumo$f$-mean to compute its best actions before and after observing the system's randomized outputs. This leads to generalized notions of prior and posterior vulnerability and generalized axiomatic relations that we will derive to elucidate how these$f$-mean-based vulnerabilities interact with each other. We demonstrate the usefulness of this framework by showing how some notions of leakage that had been derived outside of the QIF framework and so far seemed incompatible with it are indeed explainable via such an extension of QIF. These leakage measures include$\alpha$-leakage, which is the same as Arimoto mutual information of order$\alpha$, maximal$\alpha$-leakage, which is the$\alpha$-leakage capacity, and maximal$(\alpha,\ \beta)$. leakage, which is a generalization of the above and captures local differential privacy as a special case. We define the notion of generalized capacity and provide partial results for special classes of functions used in the Kolmogorov-Nagumo mean. We also propose a new pointwise notion of gain function, which we coin pointwise information gain. We show that this pointwise information gain can explain Réyni divergence and Sibson mutual information of order$\alpha\in[0, \infty]$as the Kolmogorov-Nagumo average of the gain with a proper choice of function$f$.

We study an information-theoretic privacy mechanism design, where an agent observes useful data Y and wants to reveal the information to a user. Since the useful data is correlated with the private data X, the agent uses a privacy mechanism to produce disclosed data U that can be released. We assume that the agent observes Y and has no direct access to X, i.e., the private data is hidden. We study the privacy mechanism design that maximizes the revealed information about Y while satisfying a bounded Local Information Privacy (LIP) criterion. When the leakage is sufficiently small, concepts from information geometry allow us to locally approximate the mutual information. By utilizing this approximation the main privacy-utility trade-off problem can be rewritten as a quadratic optimization problem that has closed-form solution under some constraints. For the cases where the closed-form solution is not obtained we provide lower bounds on it. In contrast to the previous works that have complexity issues, here, we provide simple privacy designs with low complexity which are based on finding the maximum singular value and singular vector of a matrix. To do so, we follow two approaches where in the first one we find a lower bound on the main problem and then approximate it, however, in the second approach we approximate the main problem directly.In this work, we present geometrical studies of the proposed methods and in a numerical example we compare our results considering both approaches with the optimal solution and the previous methods. Finally, we discuss how the proposed methods can be applied to deal with differential privacy.

The study of leakage measures for privacy has been a subject of intensive research and is an important aspect of understanding how privacy leaks occur in computer systems. Differential privacy has been a focal point in the privacy community for some years and yet its leakage characteristics are not completely understood. In this paper we bring together two areas of research -information theory and the g-leakage framework of quantitative information flow (QIF)- to give an operational interpretation for the epsilon parameter of local differential privacy. We find that epsilon emerges as a capacity measure in both frameworks; via (log)-lift, a popular measure in information theory; and via max-case g-leakage, which we introduce to describe the leakage of any system to Bayesian adversaries modelled using “worst-case” assumptions under the QIF framework. Our characterisation resolves an important question of interpretability of epsilon and consolidates a number of disparate results covering the literature of both information theory and Quantitative information flow.

This paper proposes an$\alpha$-leakage measure for$\alpha\in\lceil 0, \infty)$by a cross entropy interpretation of Renyi entropy. While Renyi entropy was originally defined as an f -mean for$f(t)=\exp((1-\alpha{)}t)$, we reveal that it is also a$\tilde{f}\cdot$mean cross entropy measure for$\vec{f}(t)=\exp \left(\frac{1-\alpha}{\alpha} t\right)$. Minimizing this Renyi cross-entropy gives Renyi entropy. This is used to define the prior and posterior uncertainty measures corresponding to the adversary's knowledge gain on sensitive attribute before and after data release, respectively. The a-leakage is proposed as the difference between$\hat{f}$-mean prior and posterior uncertainty measures, which is exactly the Arimoto mutual information. This not only extends the existing$\alpha$-leakage from$\alpha\in\lceil 1, \infty)$to the overall Renyi order range$\alpha\in\lceil 0, \infty)$in a well-founded way with$\alpha=0$referring to nonstochastic leakage, but also reveals that the existing maximal leakage is a$\tilde{f}\cdot$mean of an elementary$\alpha$-leakage for all$\alpha\in\lceil 0, \infty)$, generalizing the existing pointwise maximal leakage.

This paper introduces a novel class of PICOD$(t)$problems referred to as g-group complete-S PICOD$(t)$problems. It constructs a multi-stage achievability scheme to generate pliable index codes for group complete PICOD problems when$S=\{s\}$is a singleton set. Using the maximum acyclic induced sub graph bound, lower bounds on the broadcast rate are derived for singleton$S$, which establishes the optimality of the achievable scheme for a range of values for$t$and for any$g$and$s$. For all other values, it is shown that the achievability scheme is optimal among a restricted class of broadcast codes.

We examine the relationship between privacy metrics that utilize information density to measure information leakage between a private and a disclosed random variable. Firstly, we prove that bounding the information density from above or below in turn implies a lower or upper bound on the information density, respectively. Using this result, we establish new relationships between local information privacy, asymmetric local information privacy, pointwise maximal leakage and local differential privacy. We further provide applications of these relations to privacy mechanism design. Secondly, we provide equivalence statements of lower bounds on information density and risk-averse adversaries. More specifically, we prove an equivalence between a guessing framework and a cost-function framework that both result in the same lower bound on the information density.

In many applications of differential privacy (DP), continuous distributions such as the Laplace or the Gaussian are employed to perturb data queries. However, continuous distributions are not particularly suitable for discrete data and their quantization can compromise the privacy guarantees of DP. In this letter, we extend a recently proposed continuous mechanism for DP called offset-symmetric Gaussian tail (OSGT) distribution to its discrete version, which we call DOSGT. Our findings demonstrate that the one-dimensional DOSGT mechanism achieves the same level of$(\varepsilon, \delta (\varepsilon))$-DP as the continuous OSGT, which is better than what is achievable by the discrete Gaussian at the same variance. We also derive the Rényi differential privacy (RDP) of the DOSGT mechanism. We then present a simple and efficient algorithm for accurately sampling from DOSGT distribution, showcasing its applicability in DP scenarios involving integer-valued queries.

We study the age of information (AoI) performance of a multiuser downlink system where a base station generates and transmits status updates to multiple user equipments (UEs). The question of whether to adopt broadcast transmission or distributed transmission for the optimal AoI performance is addressed analytically. In the broadcast transmission scheme, the status update for all UEs is jointly encoded into a packet for transmission, while in the distributed transmission scheme, the status update for each UE is encoded individually and transmitted by following the round robin policy. We first derive new closed-form expressions for the average AoI achieved by two transmission schemes. Then, we provide a criterion for selecting the better transmission scheme for a remote control system. Aided by simulation results, we investigate the impact of system parameters on the average AoI. For example, the distributed transmission scheme is more appropriate for the system with a large number UEs; otherwise, the broadcast transmission scheme is more appropriate.

We propose and study a variant of pliable index coding (PICOD) where receivers have preferences for their unknown messages and give each unknown message a preference ranking. We call this the preferential pliable index-coding (PPICOD) problem and study the Pareto trade-off between the code length and overall satisfaction metric among all receivers. We derive theoretical characteristics of the PPICOD problem in terms of interactions between achievable code length and satisfaction metric. We also conceptually characterise two methods for computation of the Pareto boundary of the set of all achievable code length-satisfaction pairs. As for a coding scheme, we extend the Greedy Cover Algorithm for PICOD by Brahma and Fragouli, 2015, to balance the number of satisfied receivers and average satisfaction metric in each iteration. We present numerical results which show the efficacy of our proposed algorithm in approaching the Pareto boundary, found via brute-force computation.

We analytically decide whether the broadcast transmission scheme or the unicast transmission scheme achieves the optimal age of information (AoI) performance of a multiuser system where a base station (BS) generates and transmits status updates to multiple user equipments (UEs). In the broadcast transmission scheme, the status update for all UEs is jointly encoded into a packet for transmission, while in the unicast transmission scheme, the status update for each UE is encoded individually and transmitted by following the round robin policy. For both transmission schemes, we examine three packet management strategies, namely the non-preemption strategy, the preemption in buffer strategy, and the preemption in serving strategy. We first derive new closed-form expressions for the average AoI achieved by two transmission schemes with three packet management strategies. Based on them, we compare the AoI performance of two transmission schemes in two systems, namely, the remote control system and the dynamic system. Aided by simulation results, we verify our analysis and investigate the impact of system parameters on the average AoI. For example, the unicast transmission scheme is more appropriate for the system with a large number of UEs. Otherwise, the broadcast transmission scheme is more appropriate.

This paper is concerned with enhancing data utility in the privacy watchdog method for attaining information-theoretic privacy. For a specific privacy constraint, the watchdog method filters out the high-risk data symbols through applying a uniform data regulation scheme, e.g., merging all high-risk symbols together. While this method entirely trades the symbols resolution off for privacy, we show that the data utility can be greatly improved by partitioning the high-risk symbols set and individually privatizing each subset. We further propose an agglomerative merging algorithm that finds a suitable partition of high-risk symbols: it starts with a singleton high-risk symbol, which is iteratively fused with others until the resulting subsets are private. Numerical simulations demonstrate the efficacy of this algorithm in privately achieving higher utilities in the watchdog scheme.

In this paper, we analyze the impact of different encoding schemes on the age of information (AoI) performance in a point-to-point system, where a source generates packets based on the status updates collected from multiple sensors and transmits the packets to a destination. In this system, we consider two encoding schemes, namely, the joint encoding scheme and the distributed encoding scheme. In the joint encoding scheme, the status updates from all the sensors are jointly encoded into a packet for transmission. In the distributed encoding scheme, the status update from each sensor is encoded individually and the sensors’ packets are transmitted following the round robin policy. To ensure the freshness of packets, the zero-wait policy is adopted in both schemes, where a new packet is immediately generated once the source finishes the transmission of the current packet. We derive closed-form expressions for the average AoI achieved by these two encoding schemes and compare their performances. Simulation results show that the distributed encoding scheme is more appropriate for systems with a relatively large number of sensors, compared with the joint encoding scheme.

The broadcasting nature of the wireless medium makes exposure to eavesdroppers a potential threat. Physical Layer Security (PLS) has been widely recognized as a promising security measure complementary to encryption. It has recently been demonstrated that PLS can be implemented using off-the-shelf equipment by spectrum-programming enhanced Software-Defined Networking (SDN), where a network controller is able to execute intelligent access point (AP) selection algorithms such that PLS can be achieved and secrecy capacity optimized. In this paper we provide a basic system model for such implementations. We also introduce a novel secrecy capacity optimization algorithm, in which we combine intelligent AP selection with the addition of Friendly Jamming (FJ) by the not-selected AP.

Information leakage to a guessing adversary in index coding is studied, where some messages in the system are sensitive and others are not. The non-sensitive messages can be used by the server like secret keys to mitigate leakage of the sensitive messages to the adversary. We construct a deterministic linear coding scheme, developed from the rank minimization method based on fitting matrices (Bar-Yossef et al. 2011). The linear scheme leads to a novel upper bound on the optimal information leakage rate, which is proved to be tight over all deterministic scalar linear codes. We also derive a converse result from a graph-theoretic perspective, which holds in general over all deterministic and stochastic coding schemes.

It has been known that the insufficiency of linear coding in achieving the optimal rate of the general index coding problem is rooted in its rate’s dependency on the field size. However, this dependency has been described only through the two well-known matroid instances, namely the Fano and non- Fano matroids, which, in turn, limits its scope only to the fields with characteristic two. In this paper, we extend this scope to demonstrate the reliance of linear coding rate on fields with characteristic three. By constructing two index coding instances of size 29, we prove that for the first instance, linear coding is optimal only over the fields with characteristic three, and for the second instance, linear coding over any field with characteristic three can never be optimal. Another main contribution of this paper is to reduce the key constraints on the space of the linear coding for each index coding instance of size 29 into a matroid instance with the ground set of size 9, whose linear representability is dependent on the fields with characteristic three. The proofs and discussions provided in this paper through using these two relatively small matroid instances will shed light on the underlying reason causing the linear coding to become insufficient for the general index coding problem.

This paper is eligible for the Jack Keil Wolf ISIT Student Paper Award. We generalize a previous framework for designing utility-optimal differentially private (DP) mechanisms via graphs, where datasets are vertices in the graph and edges represent dataset neighborhood. The boundary set contains datasets where an individual’s response changes the binary-valued query compared to its neighbors. Previous work was limited to the homogeneous case where the privacy parameter ε across all datasets was the same and the mechanism at boundary datasets was identical. In our work, the mechanism can take different distributions at the boundary and the privacy parameter ε is a function of neighboring datasets, which recovers an earlier definition of personalized DP as special case. The problem is how to extend the mechanism, which is only defined at the boundary set, to other datasets in the graph in a computationally efficient and utility optimal manner. Using the concept of strongest induced DP condition we solve this problem efficiently in polynomial time (in the size of the graph).

We extend a previous framework for designing differentially private (DP) mechanisms via randomized graph colorings that was restricted to binary functions, corresponding to colorings in a graph, to multi-valued functions. As before, datasets are nodes in the graph and any two neighboring datasets are connected by an edge. In our setting, we assume that each dataset has a preferential ordering for the possible outputs of the mechanism, each of which we refer to as a rainbow. Different rainbows partition the graph of datasets into different regions. We show that if the DP mechanism is pre-specified at the boundary of such regions and behaves identically for all same-rainbow boundary datasets, at most one optimal such mechanism can exist and the problem can be solved by means of a morphism to a line graph. We then show closed form expressions for the line graph in the case of ternary functions. Treatment of ternary queries in this paper displays enough richness to be extended to higher-dimensional query spaces with preferential query ordering, but the optimality proof does not seem to follow directly from the ternary proof.

This paper proposes a novel watchdog privatization scheme by generalizing local information privacy (LIP) to enhance data utility. To protect the sensitive features S correlated with some useful data X, LIP restricts the lift, the ratio of the posterior belief to the prior on S after and before accessing X. For each x, both maximum and minimum lift over sensitive features quantify the privacy risk of publishing this symbol and should be restricted for the privacy-preserving purpose. Previous works enforce the same bound for both max-lift and min-lift. However, empirical observations show that the min-lift is usually much smaller than the max-lift. In this work, we generalize the LIP definition to consider the unequal values of max and min lift, i.e., considering different bounds for max-lift and min-lift. This new definition is applied to the watchdog privacy mechanism. We demonstrate that the utility is enhanced under a given privacy constraint on local differential privacy. At the same time, the resulting max-lift is lower and, therefore, tightly restricts other privacy leakages, e.g., mutual information, maximal leakage, and α-leakage.

The Gaussian distribution is widely used in mechanism design for differential privacy (DP). Thanks to its sub-Gaussian tail, it significantly reduces the chance of outliers when responding to queries. However, it can only provide approximate (ε,δ(ε))-DP. In practice, δ(ε) must be much smaller than the size of the dataset, which may limit the use of the Gaussian mechanism for large datasets with strong privacy requirements. In this paper, we introduce and analyze a new distribution for use in DP that is based on the Gaussian distribution, but has improved privacy performance. The so-called offset-symmetric Gaussian tail (OSGT) distribution is obtained through using the normalized tails of two symmetric Gaussians around zero. Consequently, it can still have sub-Gaussian tail and lend itself to analytical derivations. We analytically derive the variance of the OSGT random variable and δ(ε) of the single-dimensional OSGT mechanism. We extend the OSGT mechanism tok-dimensional queries, iteratively compute its δk(ε), derive its Rényi differential privacy, and study its composition. Numerical results show the OSGT mechanism can offer better privacy-utility performance compared to the Gaussian and Laplace mechanisms. We also derive a method for post processing the output of the OSGT mechanism to approximate the query based on the minimum mean square error (MMSE) estimation technique. The simulation results of such processing confirm the efficacy of the OSGT mechanism over the Gaussian mechanism.

We present a framework for designing differentially private (DP) mechanisms for binary functions via a graph representation of datasets. Datasets are nodes in the graph and any two neighboring datasets are connected by an edge. The true binary function we want to approximate assigns a value (or true color) to a dataset. Randomized DP mechanisms are then equivalent to randomized colorings of the graph. A key notion we use is that of the boundary of the graph. Any two neighboring datasets assigned a different true color belong to the boundary. Under this framework, we show that fixing the mechanism behavior at the boundary induces a unique optimal mechanism. Moreover, if the mechanism is to have a homogeneous behavior at the boundary, we present a closed expression for the optimal mechanism, which is obtained by means of a pullback operation on the optimal mechanism of a line graph. For balanced mechanisms, not favoring one binary value over another, the optimal (ε, 6)-DP mechanism takes a particularly simple form, depending only on the minimum distance to the boundary, on ε, and on 6. A full version of this paper can be found in [1].

This paper proposes an$\alpha$-lift measure for data privacy and determines the optimal privatization scheme that minimizes the$\alpha$-lift in the watchdog method. To release useful data$X$that is correlated with sensitive data$S$, the ratio of the posterior belief to the prior belief on sensitive data with respect to the useful data is called ‘lift’, which quantifies privacy risk. The$\alpha$-lift denoted by$\ell_{\alpha}(x)$is proposed as the$L_{\alpha}$-norm of the lift for a given realization$x$. This is a tunable measure: when$\alpha < \infty$, each lift is weighted by its likelihood of appearing in the dataset (w.r.t. the marginal probability$p(s)$); for$\alpha=\infty,\ \alpha$-lift reduces to the existing maximum lift. To generate the sanitized data$Y$, we adopt the privacy watchdog method using$\alpha$-lift: obtain realizations of useful data such that the$\alpha$-lift is greater than a threshold$e^{\epsilon}$; apply a randomization mechanism to these ‘high-risk’ realizations, while all other realizations of$X$are published directly. For the resulting$\alpha$-lift denoted by$\ell_{\alpha}(y)$, it is shown that the Sibson mutual information$I_{\alpha}^{S}(S;Y)$is proportional to$\mathbb{E}[\ell_{\alpha}(y)]$. We further define a stronger privacy measure denoted$\overline{I}_{\alpha}^{S}(S;Y)$using the worst-case$\alpha$-lift:$\bar{I}_{\alpha}^{S}(S;Y)\propto\max\nolimits_{y}\ell_{\alpha}(y)$. We prove that the optimal watchdog randomization that minimizes both$I_{\alpha}^{S}(S;Y)$and$\overline{I}_{\alpha}^{S}(S;Y)$is$X$-invariant. Numerical experiments show that$\alpha$-lift can provide flexibility in the privacy-utility tradeoff.

We study the information leakage to a guessing adversary in zero-error source coding. The source coding problem is defined by a confusion graph capturing the distinguishability between source symbols. The information leakage is measured by the ratio of the adversary's successful guessing probability after and before eavesdropping the codeword, maximized over all possible source distributions. Such measurement under the basic adversarial model where the adversary makes a single guess and the guess is regarded successful if and only if the estimator sequence equals to the true source sequence is known as the maximum min-entropy leakage or the maximal leakage in the literature. We develop a single-letter characterization of the optimal normalized leakage under the basic adversarial model, together with an optimum-achieving memoryless stochastic mapping scheme. An interesting observation is that the optimal normalized leakage is equal to the optimal compression rate with fixed-length source codes, both of which can be simultaneously achieved by some deterministic coding schemes. We then extend the leakage measurement to generalized adversarial models where the adversary makes multiple guesses and allows a certain level of distortion, for which we derive single-letter lower and upper bounds.

In this paper, we propose a new scalar linear coding scheme for the index coding problem called update-based maximum column distance (UM CD) coding scheme. The central idea in each transmission is to code messages such that one of the receivers with the minimum size of side information is instantaneously eliminated from unsatisfied receivers. One main contribution of the paper is to prove that the other satisfied receivers can be identified after each transmission, using a polynomial-time algorithm solving the well-known maximum cardinality matching problem in graph theory. This leads to determining the total number of transmissions without knowing the coding coefficients. Once this number and what messages to transmit in each round is found, we then propose a method to determine all coding coefficients from a sufficiently large finite field. We provide concrete instances where the proposed UM CD scheme has a better broadcast performance compared to the most efficient existing linear coding schemes, including the recursive scheme (Arbabjolfaei and Kim, 2014) and the interlinked-cycle cover scheme (Thapa et al., 2017).

Insufficiency of linear coding for the network coding problem was first proved by providing an instance which is solvable only by nonlinear network coding (Dougherty et al., 2005). Based on the work of Effros et al., 2015, this specific network coding instance can be modeled as a groupcast index coding (GIC) instance with 74 messages and 80 users (where a message can be requested by multiple users). This proves the insufficiency of linear coding for the GIC problem. Using the systematic approach proposed by Maleki$et$al., 2014, the aforementioned GIC instance can be cast into a unicast index coding (UIC) instance with more than 200 users, each wanting a unique message. This confirms the necessity of nonlinear coding for the UIC problem, but only for achieving the entire capacity region. Nevertheless, the question of whether nonlinear coding is required to achieve the symmetric capacity (broadcast rate) of the UIC problem remained open. In this paper, we settle this question and prove the insufficiency of linear coding, by directly building a UIC instance with only 36 users for which there exists a nonlinear index code outperforming the optimal linear code in terms of the broadcast rate.

In this work, we study the secure index coding problem where there are security constraints on both legitimate receivers and eavesdroppers. We develop two performance bounds (i.e., converse results) on the symmetric secure capacity. The first one is an extended version of the basic acyclic chain bound (Liu and Sadeghi, 2019) that takes security constraints into account. The second converse result is a novel information-theoretic lower bound on the symmetric secure capacity, which is interesting as all the existing converse results in the literature for secure index coding give upper bounds on the capacity.

We study the information leakage to a guessing adversary in index coding with a general message distribution. Under both vanishing-error and zero-error decoding assumptions, we develop lower and upper bounds on the optimal leakage rate, which are based on the broadcast rate of the subproblem induced by the set of messages the adversary tries to guess. When the messages are independent and uniformly distributed, the lower and upper bounds match, establishing an equivalence between the two rates.

Communication for omniscience (CO) refers to the problem where the users in a finite set V observe a discrete multiple random source and want to exchange data over broadcast channels to reach omniscience, the state where everyone recovers the entire source. This paper studies how to improve the computational complexity for the problem of minimizing the sum-rate for attaining omniscience in V. While the existing algorithms rely on the submodular function minimization (SFM) techniques and complete in O(|V|2· SFM (|V|) time, we prove the strict strong map property of the nesting SFM problem. We propose a parametric (PAR) algorithm that utilizes the parametric SFM techniques and reduces the complexity to O(|V| · SFM (|V|). We propose efficient solutions to the successive omniscience (SO): attaining omniscience successively in user subsets. We first focus on how to determine a complimentary subset X*\subsetneq V in the existing two-stage SO such that if the local omniscience in X*is reached first, the global omniscience whereafter can still be attained with the minimum sum-rate. It is shown that such a subset can be extracted at one of the iterations of the PAR algorithm. We then propose a novel multi-stage SO strategy: a nesting sequence of complimentary user subsets X*(1)\subsetneq ...\subsetneq X*(K)= V, the omniscience in which is attained progressively by the monotonic rate vectorsrV(1)≤ ...≤rV(K). We propose algorithms to obtain this K-stage SO from the returned results by the PAR algorithm. The run time of these algorithms is the same as the PAR algorithm.

This paper studies the tradeoff in privacy and utility in a single-trial multi-terminal guessing (estimation) framework using a system model that is inspired by index coding. There are n independent discrete sources at a data curator. There are m legitimate users and one adversary, each with some side information about the sources. The data curator broadcasts a distorted function of sources to legitimate users, which is also overheard by the adversary. In terms of utility, each legitimate user wishes to perfectly reconstruct some of the unknown sources and attain a certain gain in the estimation correctness for the remaining unknown sources. In terms of privacy, the data curator wishes to minimize the maximal leakage: the worst-case guessing gain of the adversary in estimating any target function of its unknown sources after receiving the broadcast data. Given the system settings, we derive fundamental performance lower bounds on the maximal leakage to the adversary, which are inspired by the notion of confusion graph and performance bounds for the index coding problem. We also detail a greedy privacy enhancing mechanism, which is inspired by the agglomerative clustering algorithms in the information bottleneck and privacy funnel problems.

We study the problem of privacy preservation in data sharing, where S is a sensitive variable to be protected and X is a non-sensitive useful variable correlated with S. Variable X is randomized into variable Y, which will be shared or released according to pY |X(y|x). We measure privacy leakage by information privacy (also known as log-lift in the literature), which guarantees mutual information privacy and differential privacy (DP). Let ${\mathcal{X}}_\varepsilon ^c \subseteq {\mathcal{X}}$ contain elements in the alphabet of for which the absolute value of log-lift (abs-log-lift for short) is greater than a desired threshold ϵ. When elements $x \in {\mathcal{X}}_\varepsilon ^c$ are randomized into $y \in {\mathcal{Y}},$ we derive the best upper bound on the abs-log-lift across the resultant pairs (s, y). We then prove that this bound is achievable via an X-invariant randomization p(y|x) = R(y) for $x,y \in {\mathcal{X}}_\varepsilon ^c$. However, the utility measured by the mutual information I(X; Y) is severely damaged in imposing a strict upper bound ϵ on the abs-log-lift. To remedy this and inspired by the probabilistic (ϵ, δ)-DP, we propose a relaxed (ϵ, δ)-log-lift framework. To achieve this relaxation, we introduce a greedy algorithm which exempts some elements in ${\mathcal{X}}_\varepsilon ^c$ from randomization, as long as their abs-log-lift is bounded by ϵ with probability 1 − δ. Numerical results demonstrate efficacy of this algorithm in achieving a better privacy-utility tradeoff.

We propose a 4-dimensional (4D) basis and sampling scheme, along with a corresponding reconstruction algorithm, for the measurement and reconstruction of the b-tensor encoded diffusion signal in diffusion magnetic resonance imaging (MRI). This is only the second basis proposed for representing the b-tensor encoded diffusion signal and the first to allow for planar tensor measurements. We design a sampling scheme that attains an efficient number of samples, equal to the degrees of freedom required to represent the diffusion signal in the proposed 4D basis. The properties of the diffusion signal are studied to provide recommendations on how many b-tensor measurements to use. Evaluation of the proposed scheme using Monte Carlo simulations of the diffusion signal is done to show that the proposed scheme gives accurate interpolation of the signal.

In index coding, a server broadcasts multiple messages to their respective receivers, each with some side information that can be utilized to reduce the amount of communication from the server. Distributed index coding is an extension of index coding in which the messages are broadcast from multiple servers, each storing different subsets of the messages. In this paper, the optimal tradeoff among the message rates and the server broadcast rates, which is defined formally as the capacity region, is studied for a general distributed index coding problem. Inner and outer bounds on the capacity region are established that have matching sum-rates for all 218 non-isomorphic four-message problems with equal link capacities for all the links from servers to receivers. The proposed inner bound is built on a distributed composite coding scheme that outperforms the existing schemes by incorporating more flexible decoding configurations and enhanced fractional rate allocations into two-stage composite coding, a scheme that was originally introduced for centralized index coding. The proposed outer bound is built on the polymatroidal axioms of entropy, as well as functional dependences such as the fd-separation introduced by the multi-server nature of the problem. This outer bound utilizes general groupings of servers with different levels of granularity, which allows a natural tradeoff between computational complexity and tightness of the bound, and includes and improves upon all existing outer bounds for distributed index coding. Specific features of the proposed inner and outer bounds are demonstrated through concrete examples with four or five messages.

In this paper, we study the information-theoretic converse for the index coding problem. We generalize the definition for the alignment chain, introduced by Maleki et al., to capture more flexible relations among interfering messages at each receiver. Based on this, we derive improved converse results for the single-server index coding problem. Compared to the maximum acyclic induced subgraph (MAIS) bound, the new bounds are always as tight and can strictly outperform the MAIS bound. They can also be useful for large problems, where the generally tighter polymatroidal bound is computationally impractical. We then extend these new bounds to the multi-server index coding problem. We also present a separate, but related result where we identify a smaller single-server index coding instance, compared to those identified in the literature, for which non-Shannon-type inequalities are necessary to give a tighter converse.

For the relevant data S that nests in the observation X, the information bottleneck (IB) aims to encode X into X̂ in X, with order to maximize the extracted useful information I(S; X̂) with the minimum coding rate I(X; X). For the dual privacy funnel (PF) problem where S denotes the sensitive/private data, the goal is to minimize the privacy leakage I(S; X̂) while maintain a certain level of utility I(X; X̂). For both problems, we propose an efficient iterative agglomerative clustering algorithm based on the minimization of the difference of submodular functions (IAC-MDSF). It starts with the original alphabet X̂ := X and iteratively merges the elements in the current alphabet X̂ that optimizes the Lagrangian function I(S; X̂)-λI(X; X̂). We prove that the best merge in each iteration of IAC-MDSF can be searched efficiently over all subsets of X̂ by the existing MDSF algorithms. By varying the value of the Lagrangian multiplier λ, we obtain the experimental results on a heart disease data set in terms of the Pareto frontier: I(S; X̂) vs. -I(X; X̂). We show that our IAC-MDSF algorithm outperforms the existing iterative pairwise merge approaches for both PF and IB and is computationally much less complex.

This paper proposes a novel splitting (SPLIT) algorithm to achieve fairness in the multiterminal lossless data compression problem. It finds the egalitarian solution in the Slepian-Wolf region and completes in strongly polynomial time. We show that the SPLIT algorithm adaptively updates the source coding rates to the optimal solution, while recursively splitting the terminal set, enabling parallel and distributed computation. The result of an experiment demonstrates a significant reduction in computation time by the parallel implementation when the number of terminals becomes large. The achieved egalitarian solution is also shown to be superior to the Shapley value in distributed networks, e.g., wireless sensor networks, in that it best balances the nodes' energy consumption and is far less computationally complex to obtain.

We consider the problem of how to attain fairness in the multiterminal data compression problem by a game-theoretic approach and present a decomposition method for obtaining the Shapley value, a fair source coding rate vector in the Slepian-Wolf achievable region. We model a discrete memoryless multiple random source (DMMS) by a coalitional game where the entropy function quantifies the cost incurred by the source coding rates in each coalition. In the typical case for which the game is decomposable, we show that the Shapley value can be obtained separately for each subgame. The complexity of this decomposition method is determined by the maximum size of subgames, which is strictly smaller than the total number of terminals in the DMMS and contributes to a considerable reduction in computational complexity. An experimental result demonstrates large complexity reduction when the number of terminals in the DMMS becomes large.

Simplification methods are introduced for composite coding, which is an existing layered random coding technique for the index coding problem. As the problem size grows, the original number of composite indices grows exponentially and the number of possible decoding configurations (decoding sets) grows super exponentially, leading to considerably high computational complexity. The proposed simplifications address both issues and do not affect the performance (tightness) of the coding scheme. Removing composite indices is achieved by pairwise comparison of any two indices and removing one if its corresponding rate can be transferred without loss to the other in the expressions of the achievable rate region. Decoding configurations are reduced by establishing a baseline or natural decoding configuration, where no smaller decoding configuration can provide a strictly larger rate region. A heuristic method is also proposed for reducing the number of composite indices even further, but possibly with some performance loss. Numerical results demonstrate good performance with substantial reduction in complexity. To achieve the capacity region for all 9608 non-isomorphic index coding problems with n = 5, a single natural decoding configuration per problem and less than 3 out of 25-1=31 composite indices are sufficient, on average. In only 31 problems, 7 to at most 10 composite indices are used.

We extend the composite coding (CC) scheme for the index coding problem from two layers to more layers of random binning. We explicitly introduce the three-layer composite coding (TLCC) scheme and provide the achievable rate region and the error analysis for it. We present a concrete non-trivial example with n = 7 messages where the TLCC strictly outperforms the CC scheme. We also present a number of simplification methods for the TLCC scheme towards better understanding of the scheme, as well as significantly reducing its computational complexity. We further prove that even a simplified version of the TLCC, which can be possibly weaker than the TLCC, still subsumes the CC scheme.

We study the index coding problem in the presence of an eavesdropper, where the aim is to communicate without allowing the eavesdropper to learn any single message aside from the messages it may already know as side information. We establish an outer bound on the underlying secure capacity region of the index coding problem, which includes polymatroidal and security constraints, as well as the set of additional decoding constraints for legitimate receivers. We then propose a secure variant of the composite coding scheme, which yields an inner bound on the secure capacity region of the index coding problem. For the achievability of secure composite coding, a secret key with vanishingly small rate may be needed to ensure that each legitimate receiver who wants the same message as the eavesdropper, knows at least two more messages than the eavesdropper. For all securely feasible index coding problems with four or fewer messages, our numerical results establish the secure index coding capacity region.

We study the interplay between the throughput and average packet decoding delay (APDD) of linear network coded (LNC) wireless broadcast systems through studying the approximation of throughput and APDD. We first define strong and weak approximations (based on whether the approximation holds for every receiver or not). We then prove that LNC techniques that strongly approximate throughput can also strongly approximate APDD, but those that weakly approximate throughput do not necessarily weakly approximate APDD. We prove that all throughput-optimal LNC techniques, including random linear network coding, strongly approximate APDD with a ratio between 4/3 and 2. We also prove that all memoryless LNC techniques, including instantly decodable network coding techniques, cannot strongly or weakly approximate throughput, nor strongly approximate APDD.

This paper considers the communication for omniscience problem: a set of users observe a discrete memoryless multiple source and want to recover the entire multiple source via noise-free broadcast communications. We study the problem of how to determine an optimal rate vector that attains omniscience with the minimum sum rate, the total number of communications. The results cover both asymptotic and non-asymptotic models where the transmission rates are real and integral, respectively. We propose a modified decomposition algorithm (MDA) and a sum-rate increment algorithm (SIA) for the asymptotic and non-asymptotic models, respectively, both of which determine the value of the minimum sum rate and a corresponding optimal rate vector in polynomial time. For the coordinate saturation capacity algorithm, a nesting algorithm in MDA and SIA, we propose to implement it by a fusion method and show by experimental results that this fusion method contributes to a reduction in computation complexity. Finally, we show that the separable convex minimization problem over the optimal rate vector set in the asymptotic model can be decomposed by the fundamental partition, the optimal partition of the user set that determines the minimum sum rate, so that the problem can be solved more efficiently.

We study the problem of reducing the download time of multiple files requested by multiple clients from multiple cloud/fog storage servers. Given possible previous file downloads by the clients, network coding can be efficiently exploited to expedite the download process. Since each client can tune to only one server at a time, the sets of clients served by the different servers must be disjoint in order to guarantee a maximum reduction in download time. To accomplish disjoint download mechanisms, a dual conflict network coding graph is proposed. Given the intractability of the long-term optimal solution, we propose an online algorithm using the designed dual conflict graph. For the case of one file request per client, both asymptotic lower and upper bounds of the performance of the proposed conflict-free algorithm are derived. Simulation results show that this proposed algorithm exhibits near optimum performance compared to the optimum solution, and a significant reduction in download time as compared to the per-server network coding scheme. Furthermore, imperfect feedback environment scenarios are investigated. A maximum likelihood approach is employed at the server to estimate the network state, which is then incorporated in our proposed algorithm to reduce the download time in such scenarios.

The system that we study in this paper contains a set of users that observe a discrete memoryless multiple source and communicate via noise-free channels with the aim of attaining omniscience, the state that all users recover the entire multiple source. We adopt the concept of successive omniscience (SO), i.e., letting the local omniscience in some user subset be attained before the global omniscience in the entire system, and consider the problem of how to efficiently attain omniscience in a successive manner. Based on the existing results on SO, we propose a CompSetSO algorithm for determining a complimentary set, a user subset in which the local omniscience can be attained first without increasing the sum-rate, the total number of communications, for the global omniscience. We also derive a sufficient condition for a user subset to be complimentary so that running the CompSetSO algorithm only requires a lower bound, instead of the exact value of the minimum sum-rate for attaining global omniscience. The CompSetSO algorithm returns a complimentary user subset in polynomial time. We show by example how to recursively apply the CompSetSO algorithm so that the global omniscience can be attained by multi-stages of SO.

The distributed index coding problem is studied, whereby multiple messages are stored at different servers to be broadcast to receivers with side information. First, the existing composite coding scheme is enhanced for the centralized (single-server) index coding problem, which is then merged with fractional partitioning of servers to yield a new coding scheme for distributed index coding. New outer bounds on the capacity region are also established. For all distributed index coding problems with n ≤ 4 messages and equal server link capacities, the achievable sum-rate of the proposed distributed composite coding scheme match the outer bounds, thus establishing the sum-capacity for these problems.

This paper studies the cloud offloading gains of using heterogeneous enhanced remote radio heads (eRRHs) and dual-interface clients in fog radio access networks (F-RANs). First, the cloud offloading problem is formulated as a collection of independent sets selection problem over a network coding graph, and its NP-hardness is shown. Therefore, a computationally simple online heuristic algorithm is proposed, that maximizes cloud offloading by finding an efficient schedule of coded file transmissions from the eRRHs and the cloud base station (CBS). Furthermore, a lower bound on the average number of required CBS channels to serve all clients is derived. Simulation results show that our proposed framework that uses both network coding and a heterogeneous F-RAN setting enhances cloud offloading as compared to conventional homogeneous F-RANs with network coding.

This paper studies the problem of broadcasting layered video streams over heterogeneous single-hop wireless networks using feedback-free random linear network coding (RLNC). We combine RLNC with unequal error protection (UEP) and our main purpose is twofold: to systematically investigate the benefits of UEP+ RLNC layered approach in servicing users with different reception capabilities and to study the effect of not using feedback, by comparing feedback-free schemes with idealistic full-feedback schemes. To these ends, we study “expected percentage of decoded frames” as a key content-independent performance metric and propose a general framework for calculation of this metric, which can highlight the effect of key system, video, and channel parameters. We study the effect of number of layers and propose a scheme that selects the optimum number of layers adaptively to achieve the highest performance. Assessing the proposed schemes with real H.264 test streams, the trade-offs among the users' performances are discussed and the gain of adaptive selection of number of layers to improve the trade-offs is shown. Furthermore, it is observed that the performance gap between the proposed feedback-free scheme and the idealistic scheme is very small and the adaptive selection of number of video layers further closes the gap.

Current approaches to the practical implementation of network coding are batch-based, and often do not use feedback, except possibly to signal completion of a file download. In this paper, the various benefits of using feedback in a network coded system are studied. It is shown that network coding can be performed in a completely online manner, without the need for batches or generations, and that such online operation does not affect the throughput. Although these ideas are presented in a single-hop packet erasure broadcast setting, they naturally extend to more general lossy networks, which employ network coding in the presence of feedback. The impact of feedback on sender-side queue size and receiver-side decoding delay is studied in an asymptotic sense as the traffic load approaches capacity. Different notions of decoding delay are considered, including an order-sensitive notion, which assumes that packets are useful only when delivered in order. Strategies for adaptive coding based on feedback are presented. Our scheme achieves throughput optimality and asymptotically optimal sender queue size and is conjectured to achieve asymptotically optimal in-order delivery delay for any number of receivers. This paper may be viewed as a natural extension of Automatic Repeat reQuest to coded networks.

This paper considers a heterogeneous network architecture wherein devices use two wireless interfaces to receive packets from the base station and to transmit or receive packets from other devices concurrently. For such a network architecture, this paper focuses on time-critical and order-constrained applications that require quick and reliable in-order decoding of the packets. This paper first introduces the dual delivery delay as a measure of degradation compared with the optimal in-order packet delivery to the devices. It then addresses the minimum delivery delay problem using instantly decodable network coding (IDNC). In particular, the dual interface IDNC graph is constructed to represent all feasible coding opportunities and conflict-free transmissions. Subsequently, the minimum delivery delay problem is shown to be equivalent to a maximum weight independent set selection problem over the dual interface IDNC graph. Simulation results demonstrate that the proposed IDNC algorithm effectively reduces the delivery delay as compared with the existing network coding algorithms. Especially, for a layered video transmission, the proposed solution provides a sequential delivering of video layers to individual devices.

We propose a novel algorithm to design user load- achieving pilot sequences that mitigate pilot contamination in multi-cell massive multiple-input multiple-output (MIMO) networks. To this end, we first derive expressions for the user load and the load region of the network considering both small- scale and large-scale propagation effects. We then develop the pilot sequence algorithm for multi- cell massive MIMO networks as per the rules of generalized Welch bound equality design. Notably, we find that our algorithm and the corresponding downlink power allocation ensure that the user load is achieved when the signal-to-interference- plus-noise ratio (SINR) requirements for the users lie within the load region. Furthermore, we demonstrate the performance advantage of our proposed design relative to the existing designs, in terms of a larger load region and a higher maximum permitted SINR. Finally, we show that our proposed design can satisfy the pre-defined SINR requirements for users with a finite number of antennas at the base station (BS), while the existing designs cannot satisfy the same requirements even with an infinite number of antennas at the BS.

In this paper, we consider a fully connected device-to-device communications network, where a group of devices with heterogeneous channel capacities cooperate with each other to recover their missing packets. In such cooperative network, we aim to minimize the completion time required for recovering all missing packets at devices using instantly decodable network coding (IDNC). In particular, we first introduce a new IDNC graph to represent all feasible rate and coding decisions for all potential transmitting devices in one unified framework. We then show that finding the optimal schedule that minimizes the completion time is computationally complex. Nevertheless by using the new graph and the properties of the optimal schedule, we design a completion time reduction heuristic that balances between the transmission rate and the number of targeted devices with a new packet. Simulation results show that our proposed IDNC algorithm provides an appreciable completion time gain compared to the conventional rate oblivious network coding algorithms.

We consider the problem of how to fairly distribute the minimum sum-rate among the users in communication for omniscience (CO). We formulate a problem of minimizing a weighted quadratic function over a submodular base polyhedron which contains all achievable rate vectors, or transmission strategies, for CO that have the same sum-rate. By solving it, we can determine the rate vector that optimizes the Jain's fairness measure, a more commonly used fairness index than the Shapley value in communications engineering. We show that the optimizer is a lexicographically optimal (lex-optimal) base and can be determined by a decomposition algorithm (DA) that is based on submodular function minimization (SFM) algorithm and completes in strongly polynomial time. We prove that the lex-optimal minimum sum-rate strategy for CO can be determined by finding the lex-optimal base in each user subset in the fundamental partition and the complexity can be reduced accordingly.

In this paper, we study the capacity region of the general distributed index coding. In contrast to the traditional centralized index coding where a single server contains all n messages requested by the receivers, in the distributed index coding there are 2n- 1 servers, each containing a unique non-empty subset J of the messages and each is connected to all receivers via a noiseless independent broadcast link with an arbitrary capacity CJ≥ 0. First, we generalize the existing outer bound on the capacity region of the centralized problem to the distributed case. Next, building upon the existing centralized composite coding scheme, we propose three distributed composite coding schemes and derive the corresponding inner bounds on the capacity region. We present a number of interesting numerical examples, which highlight the subtleties and challenges of dealing with the distributed index coding, even for very small problem sizes of n = 3 and n = 4.

Consider a radio access network wherein a basestation is required to deliver a set of order-constrained messages to a set of users over independent erasure channels. This paper studies the delivery time reduction problem using instantly decodable network coding (IDNC). Motivated by time-critical and order-constrained applications, the delivery time is defined, at each transmission, as the number of undelivered messages. The delivery time minimization problem being computationally intractable, most of the existing literature on IDNC propose suboptimal online solutions. This paper suggests a novel method for solving the problem by introducing the delivery delay as a measure of distance to optimality. An expression characterizing the delivery time using the delivery delay is derived, allowing the approximation of the delivery time minimization problem by an optimization problem involving the delivery delay. The problem is, then, formulated as a maximum weight clique selection problem over the IDNC graph wherein the weight of each vertex reflects its corresponding user and message's delay. Simulation results suggest that the proposed solution achieves lower delivery and completion times as compared to the best-known heuristics for delivery time reduction.

We propose a novel pilot sequence design to mitigate pilot contamination in multi-cell multiuser massive multiple-input multiple-output networks. Our proposed design generates pilot sequences in the multi-cell network and devises power allocation at base stations (BSs) for downlink transmission. The pilot sequences together with the power allocation ensure that the user capacity of the network is achieved and the pre-defined signal-to-interference-plus-noise ratio (SINR) requirements of all users are met. To realize our design, we first derive new closed-form expressions for the user capacity and the user capacity region. Built upon these expressions, we then develop a new algorithm to obtain the required pilot sequences and power allocation. We further determine the minimum number of antennas required at the BSs to achieve certain SINR requirements of all users. The numerical results are presented to corroborate our analysis and to examine the impact of key parameters, such as the pilot sequence length and the total number of users, on the network performance. A pivotal conclusion is reached that our design achieves a larger user capacity region than the existing designs and needs less antennas at the BS to fulfill the pre-defined SINR requirements of all users in the network than the existing designs.

This paper considers a cross-layer adaptive modulation system that is modeled as a Markov decision process. We study how to utilize the monotonicity of the optimal transmission policy to relieve the computational complexity of dynamic programming (DP). In this system, a scheduler controls the bit rate of the m-quadrature amplitude modulation in order to minimize the long-term losses incurred by the queue overflow in the data link layer and the transmission power consumption in the physical layer. The work is done in two steps. First, we observe the L#-convexity and submodularity of DP to prove that the optimal policy is always nondecreasing in queue occupancy/state and derive the sufficient condition for it to be nondecreasing in both queue and channel states. We also show that, due to the L#-convexity of DP, the variation of the optimal policy in queue state is restricted by a bounded marginal effect. The increment of the optimal policy between adjacent queue states is no greater than one. Second, we use the monotonicity results to present two low complexity algorithms: monotonic policy iteration (MPI) based on L#-convexity and discrete simultaneous perturbation stochastic approximation (DSPSA). We run experiments to show that the time complexity of MPI based on L#-convexity is much lower than that of DP and the conventional MPI that is based on submodularity and DSPSA is able to adaptively track the optimal policy when the system parameters change.

This paper considers the discrete convexity of a cross-layer on-off transmission control problem in wireless communications. In this system, a scheduler decides whether or not to transmit in order to optimize the long-term quality of service (QoS) incurred by the queueing effects in the data link layer and the transmission power consumption in the physical (PHY) layer simultaneously. Using a Markov decision process (MDP) formulation, we show that the optimal policy can be determined by solving a minimization problem over a set of queue thresholds if the dynamic programming (DP) is submodular. We prove that this minimization problem is discrete convex. In order to search the minimizer, we consider two discrete stochastic approximation (DSA) algorithms: 1) discrete simultaneous perturbation stochastic approximation (DSPSA) and 2) L#-convex stochastic approximation (L#-convex SA). Through numerical studies, we show that the two DSA algorithms converge significantly faster than the existing continuous simultaneous perturbation stochastic approximation (CSPSA) algorithm in multiuser systems. Finally, we compare the convergence results and complexity of two DSA and CSPSA algorithms where we show that DSPSA achieves the best tradeoff between complexity and accuracy in multiuser systems.

Next-generation cellular networks are expected to be assisted by femtocaches (FCs), which collectively store the most popular files for the clients. Given any arbitrary non-fragmented placement of such files, a strict no-latency constraint, and clients' prior knowledge, new file download requests could be efficiently handled by both the FCs and the macrocell base station (MBS) using opportunistic network coding (ONC). In this paper, we aim to find the best allocation of coded file downloads to the FCs so as to minimize the MBS involvement in this download process. We first formulate this optimization problem over an ONC graph, and show that it is NP-hard. We then propose a greedy approach that maximizes the number of files downloaded by the FCs, with the goal to reduce the download share of the MBS. This allocation is performed using a dual conflict ONC graph to avoid conflicts among the FC downloads. Simulations show that our proposed scheme almost achieves the optimal performance and significantly saves on the MBS bandwidth.

We propose a super-resolution image reconstruction method which uses focused frequency time reversal (FFTR) matrices to focus in frequency for ultrawideband (UWB) ultrasound signals, as well as time reversal MUltiple SIgnal Classification (MUSIC) algorithm to focus spatially on the target location. Our combined method, which we refer to as FFTR-MUSIC, is motivated by the pressing need to improve the resolution of diagnostic ultrasound systems. Compared with the TR matched filter (TRMF) and incoherent TR-MUSIC approaches, our proposed method has lower computational complexity, higher visibility, higher robustness against noise, and higher accuracy for imaging point targets when the targets are closely located. Our simulation results show that under mild speckle and noise conditions, the FFTR-MUSIC can resolve objects less than 200 μm.

The paper investigates combining Compressive Sensing (CS) with the robust Capon beamformer (RCB) for the purpose of medical ultrasound image formation with a much reduced number of samples compared to those used in current state-of-art ultrasound. The proposed CS algorithm uses wave atom dictionary as a low dimension projection, a Bernouli random matrix as a sensing matrix and a regularized-l1optimization technique for recovery. The reconstructed signals are then pre-processed before using the RCB technique augmented with spatial smoothing and diagonal loading. This approach is demonstrated through simulations, wire phantom and in vivo cardiac data with a reduction of up to 1/8 in the processed data rate and ultrasound images of similar perceived quality.

In this paper, we design a conflict free instantly decodable network coding (IDNC) solution for file download from distributed storage servers. Considering previously downloaded files at the clients from these servers as side information, IDNC can speed up the current download process. However, transmission conflicts can occur since multiple servers can simultaneously send IDNC combinations of files to the same client, which can tune to only one of them at a time. To avoid such conflicts and design more efficient coded download patterns, we propose a dual conflict IDNC graph model, which extends the conventional IDNC graph model in order to guarantee conflict free server transmissions to each of the clients. We then formulate the download time minimization problem as a stochastic shortest path problem whose action space is defined by the independent sets of this new graph. Given the intractability of the solution, we design a channel-aware heuristic algorithm and show that it achieves a considerable reduction in the file download time, compared to applying the conventional IDNC approach separately at each of the servers.

This paper considers how to accurately estimate the minimum sum-rate so as to reduce the complexity of solving cooperative data exchange (CDE) problems. The CDE system contains a number of geographically close clients who send packets to help the others recover an entire packet set. The minimum sum-rate is the minimum value of total number of transmissions that achieves universal recovery (the situation when all the clients recover the whole packet set). Based on a necessary and sufficient condition for a supermodular base polyhedron to be nonempty, we show that the minimum sum-rate for a CDE system can be determined by a maximization over all possible partitions of the client set. Due to the high complexity of solving this maximization problem, we propose a deterministic algorithm to approximate a lower bound on the minimum sum-rate. We show by experiments that this lower bound is much tighter than those lower bounds derived in the existing literature. We also show that the deterministic algorithm prevents from repetitively running the existing algorithms for solving CDE problems so that the overall complexity can be reduced accordingly.

The articles in this special issue focus on fundamental approaches to network coding in wireless communications systems. Wireless communication network providers are constantly striving for more efficient and reliable service provision to billions of customers across the globe. As such, there exist great opportunities in the research and development of advanced network coding techniques in emerging wireless communication systems and applications for further improving network capacity and performance. Arguably, bandwidth-hungry applications,such as multimedia, are to benefit the most from the many advantages that wireless network coding can offer, particularly higher throughputs, lower delays, and better scalability. Wireless network coding has a great potential to be applied at the physical layer, harnessing inherent interference in the wireless channel for more spectral efficiency. It can significantly enhance the performance of relay-based, device-to-device, and cooperative communication techniques in current and future wireless systems.

In this paper we show that the spatially localized spherical harmonic transform (SLSHT), which represents a signal on the 2-sphere in the spatio-spectral domain, can be efficiently computed using new kernel-based formulations. In addition to the standard spatio-spectral domain, we show there are three other related transforms that provide alternative representations in the spatio-spatial, spectro-spatial and spectro-spectral domains. We provide inversion results that extend available results for the SLSHT. We show that for signals on the 2-sphere band-limited to degree L, the computational complexity using our class of kernel-based SLSHT transforms is O(L4) and outperforms the previous best known fast methods, which have complexity O(L5).

In random linear network coding, rate control is an important strategy for limiting the decoding delay of a system. In broadcast systems where the channel rate is either unknown or varies over time, we demonstrate that a target delay can be achieved using the queue threshold scheme that we introduce. At throughputs approaching the channel rate, the queue threshold rate control scheme is shown to achieve improved throughput delay performance compared with existing schemes. We demonstrate that it is possible to modify this rate control scheme to greatly reduce the amount of feedback required, in exchange for a slight degradation of the throughput delay performance. Furthermore, this rate control scheme is shown to perform reasonably well, even under lossy and delayed feedback.

In this paper, we study the problem of decoding delay reduction for instantly decodable network coding (IDNC) in broadcast cooperative systems, where a group of closely located clients cooperate with each other to obtain their missing packets. In such cooperative systems, one of the clients (referred to as the leader) decides the transmitting client and the packet combination for each transmission. We consider intermittent system status update (SSU) at the leader such that all other clients feed back their packet reception status to the leader after several cooperative transmissions. We first introduce an intermittent local IDNC (IL-IDNC) graph to represent all potential packet combinations for a transmitting client. We then formulate the joint client and packet selection problem that results in the minimum expected decoding delay in each cooperative transmission as a maximum weight clique problem over all the IL-IDNC graphs. Since solving the formulated problem is computationally complex, we propose a heuristic algorithm to select the transmitting client and the packet combination that can reduce the decoding delay. Simulation results show that the proposed heuristic algorithm can achieve a tolerable degradation compared to the full SSU performance while using a smaller number of SSUs.

Deterministic linear network coding (DLNC) is an important family of network coding techniques for wireless packet broadcast. In this paper, we show that DLNC is strongly related to and can be effectively studied using matroid theory without bridging index coding. We prove the equivalence between the DLNC solution and matrix matroid. We use this equivalence to study the performance limits of DLNC in terms of the number of transmissions and its dependence on the finite field size. Specifically, we derive the sufficient and necessary condition for the existence of perfect DLNC solutions and prove that such solutions may not exist over certain finite fields. We then show that identifying perfect solutions over any finite field is still an open problem in general. To fill this gap, we develop a heuristic algorithm which employs graphic matroids to find perfect DLNC solutions over any finite field. Numerical results show that its performance in terms of minimum number of transmissions is close to the lower bound, and is better than random linear network coding when the field size is not so large.

This paper studies the complicated interplay of the completion time (as a measure of throughput) and the decoding delay performance in instantly decodable network coded (IDNC) systems over wireless broadcast erasure channels with memory. We propose two new algorithms that enable a tradeoff for an improved balance between completion time and decoding delay of broadcasting a block of packets. We first formulate the IDNC packet selection problem that improves the balance between completion time and decoding delay as a statistical shortest path (SSP) problem. However, since finding such packet selection policy using the SSP technique is computationally complex, we employ its geometric structure to find some guidelines and use them to propose two efficient heuristic packet selection algorithms for broadcast erasure channels with a wide range of memory conditions. It is shown that each one of the two proposed algorithms is superior for a specific range of memory conditions. Furthermore, we show that the proposed algorithms achieve an improved fairness in terms of the decoding delay across all receivers.

In this paper, we consider the issue of throughput and packet drop rate (PDR) optimization as two performance metrics for delay sensitive applications in network coded time division duplex (TDD) satellite systems with large round trip times (RTTs). We adopt random linear network coding (RLNC) and our purpose is to obtain the optimum RLNC-based transmission strategy. We start with a single-user case and propose a systematic framework to investigate the advantage of using feedback by comparing feedback-free and feedback schemes. Showing analytically that the feedback-free scheme gives better performance for our system of interest, we extend it to multi-user broadcast case. To this end, we consider a number of different broadcast scenarios and optimize the system parameters such that the best overall performance is achieved. Furthermore, the complicated interplay of the mean throughputs and PDRs of different users with different packet erasure conditions is discussed. Finally, it is shown that the optimized feedback-free RLNC broadcast scheme works close enough to an idealistic RLNC scheme, where the complete and immediate knowledge about the reception status of all users is assumed to be available at the sender.

Our primary goal in this paper is to better understand and extend the achievable tradeoffs between the throughput and decoding delay performance of network coded wireless broadcast. To this end, we traverse the performance gap between two linear network coding schemes: random linear network coding (RLNC) and instantly decodable network coding (IDNC). Our approach is to appropriately partition a block of partially received data packets into subgenerations and broadcast them separately using RLNC. Through analyzing the factors that affect the performance of a generic partitioning scheme, we are led to develop a coding framework in which subgenerations are created from IDNC coding sets in an IDNC solution. This coding framework consists of a series of coding schemes, with classic RLNC and IDNC identified as two extreme schemes. We develop two basic partitioning guidelines, including disjoint partitioning and even partitioning. We design various implementations of this coding framework, such as partitioning algorithms and generation scheduling strategies, to further improve its throughput and decoding delay, to manage feedback frequency and coding complexity, or to achieve in-block performance adaption. Their effectiveness is verified through extensive simulations, and their performance is compared with an existing work in the literature.

In this paper, we provide theoretical and simulation-based study of the delivery delay performance of a number of existing throughput-optimal coding schemes and use the results to design a new dynamic rate adaptation scheme that achieves improved overall throughput-delay performance. Under a baseline rate control scheme, the receivers' delay performance is examined. Based on their Markov states, the knowledge difference between the sender and receiver, three distinct methods for packet delivery are identified: zero state, leader state, and coefficient-based delivery. We provide analyses of each of these and show that, in many cases, zero state delivery alone presents a tractable approximation of the expected packet delivery behavior. Interestingly, while coefficient-based delivery has so far been treated as a secondary effect in the literature, we find that the choice of coefficients is extremely important in determining the delay, and a well-chosen encoding scheme can, in fact, contribute a significant improvement to the delivery delay. Based on our delivery delay model, we develop a dynamic rate adaptation scheme that uses performance prediction models to determine the sender transmission rate. Surprisingly, taking this approach leads us to the simple conclusion that the sender should regulate its addition rate based on the total number of undelivered packets stored at the receivers. We show that despite its simplicity, our proposed dynamic rate adaptation scheme results in noticeably improved throughput-delay performance over existing schemes in the literature.

This paper investigates the use of instantly decodable network coding (IDNC) for minimizing the mean decoding delay in multicast cooperative data exchange systems, where the clients cooperate with each other to obtain their missing packets. Here, IDNC is used to reduce the decoding delay of each transmission across all clients. We first introduce a new framework to find the optimum client and coded packet that result in the minimum mean decoding delay. However, since finding the optimum solution of the proposed framework is NP-hard, we further propose a heuristic algorithm that aims to minimize the lower bound on the expected decoding delay in each transmission. The effectiveness of the proposed algorithm is assessed through simulations.

In this paper, a new network coding model is proposed to unify instantly decodable network coding (IDNC) and random linear network coding (RLNC), which have been considered to be incompatible in the literature. This model is based on a novel definition of generation, which is built upon optimal IDNC solutions. Under this model, IDNC and RLNC are only two extreme cases with specific generation sizes. Throughput and delay properties of this model, measured by block completion time and packet decoding delay, respectively, are studied, which fill the gap between IDNC and RLNC and thus provide a good understanding on the throughput-delay tradeoff of network coding. An efficient adaptive scheme is then designed, which allows in-block switch among IDNC and different levels of RLNC, so that the system's throughput and delay can be fine-tuned to meet the real-time requirements of the application. Extensive simulations are performed to demonstrate how the proposed generation size interacts with the number of receivers and the channel quality to affect the overall system performance.

In this paper, we consider the problem of guaranteeing the quality of service (QoS) in delay sensitive network coded broadcast systems over time division duplex (TDD) satellite channels. We adopt feedback-less systematic random linear network coding (RLNC) and our goal is to design the system such that the required QoS is guaranteed. We focus on two classes of QoS requirements that necessitate the minimum/mean throughput of the users be higher than a threshold with a predefined probability and at the same time the packet drop rates (PDR) of the users be minimized within the delivery deadline requirements of the system. To this end, we start with formulating the probability and cumulative density functions (PDF and CDF) of users' throughputs. Then by utilizing the calculated functions, the optimum system design parameters that meet the QoS requirements can be obtained. The achieved results on the PDF and CDF of users' throughputs offer good insights about the performances of different users with different packet erasure conditions, and more importantly provide design guidelines for TDD satellite broadcast systems. Furthermore, the results show that the proposed feedback-less scheme performs nearly as well as an idealistic scheme using immediate and perfect feedbacks.

In this paper, we consider the problem of minimizing the decoding delay of generalized instantly decodable network coding (G-IDNC) in persistent erasure channels (PECs). By persistent erasure channels, we mean erasure channels with memory, which are modeled as a Gilbert-Elliott two-state Markov model with good and bad channel states. In this scenario, the channel erasure dependence, represented by the transition probabilities of this channel model, is an important factor that could be exploited to reduce the decoding delay. We first formulate the G-IDNC minimum decoding delay problem in PECs as a maximum weight clique problem over the G-IDNC graph. Since finding the optimal solution of this formulation is NP-hard, we propose two heuristic algorithms to solve it and compare them using extensive simulations. Simulation results show that each of these heuristics outperforms the other in certain ranges of channel memory levels. They also show that the proposed heuristics significantly outperform both the optimal strict IDNC in the literature and the channel-unaware G-IDNC algorithms.

In this study, we analyse the error performance of decode and forward (DF) and amplify and forward (AF) multi‐way relay networks (MWRNs). The authors consider a MWRN with pair‐wise data exchange protocol using binary phase shift keying (BPSK) modulation in both additive white Gaussian noise (AWGN) and Rayleigh fading channels. The authors quantify the possible error events in an L ‐user DF or AF MWRN and derive accurate asymptotic bounds on the probability for the general case that a user incorrectly decodes the messages of exactly k ( k ∈ [1, L − 1]) users. They show that at high signal‐to‐noise ratio (SNR), the higher order error events ( k ≥ 3) are less probable in AF MWRN, but all error events are equally probable in a DF MWRN. They derive the average BER of a user in a DF or AF MWRN in both AWGN and Rayleigh fading channels under high SNR conditions. Simulation results validate the correctness of the derived expressions. The authors results show that at medium to high SNR, DF MWRN provides better error performance than AF MWRN in AWGN channels even with a large number of users (e.g. L = 100). Whereas, AF MWRN outperforms DF MWRN in Rayleigh fading channels even for much smaller number of users (e.g. L > 10).

We study information rate penalties for single-relay amplify and forward (AF) cooperative communication in the presence of unknown and time-varying fading. The penalty is defined as the gap between the information rate with perfect channel state information and that when the source-destination, source-relay and relay-destination channels are unknown at the receiving nodes. We prove that this gap in the cooperative system is the sum of gaps in the source-destination (single-hop) and source-relay-destination (dual-hop) channels. Under the assumption that the source and destination are mobile and the relay is stationary, we derive a closed-form accurate approximation for the asymptotic penalty of the mobile-to-mobile single-hop channel, which can also be used in computing asymptotic penalties for the mobile-fixed-mobile dual-hop channel. AF relaying induces non-Gaussian noise at the destination and hence, the penalty of the dual-hop channel is computed semi-analytically. We discuss a numerical technique for evaluation of destination noise entropy. One main observation of this paper is that non-negligible amplified relay noise can increase the cooperation information rate penalty of up to 1.5 times, as compared to non-relayed transmission. We provide extensive simulation results that characterize the behavior of penalty and include other mobility models for the source, relay and destination.

The ambiguity function and the Wigner distribution are fundamental tools in the time-frequency analysis. In this paper, we present an analog of the ambiguity function and the Wigner distribution for signals on the sphere. First, we formulate the ambiguity function for signals on the sphere which represents the signals in joint spatio-spectral domain and derive an inversion operation to obtain the signal from its ambiguity function. Next, we formulate the Wigner distribution for azimuthally symmetric signals on the sphere as a two dimensional spherical harmonics transform of the ambiguity function. We provide the matrix formulation of the Wigner distribution and discuss some of its useful properties. Finally, we illustrate the use of Wigner distribution for spatial and/or spectral localization of a signal in joint spatio-spectral domain. The obtained results provide the first step in designing more sophisticated transforms on the sphere.

The uncertainty principle is an important and powerful tool, with many applications in signal processing. This paper presents two concentration uncertainty principles for signals on the sphere which relate the localization of the concentration of a signal in spatial and spectral domains, as an analogue of the general Donoho and Stark uncertainty principles in time-frequency analysis. Using the spherical and spectral truncation operators, we derive the L1-norm and L2-norm uncertainty principles which respectively relate the signal concentration in spatial and spectral domains as absolute value and the energy of a signal. We also analyze the sharpness of the bound imposed by the derived L2-norm uncertainty principle. The proposed uncertainty measures can be applied to signal processing problems on the sphere.

In this paper, we consider the problem of signal extrapolation for discrete (i.e., sampled) signals on the sphere. We propose conjugate gradient based algorithm for estimating a signal on the sphere from limited or incomplete measurements in a spatial domain. We prove that the proposed algorithm is guaranteed to converge and show that it has faster convergence compared to the Papoulis algorithm. The results also show that the incomplete measurements distributed in different non-connected spatial regions yield better extrapolation results, compared to the connected region case.

The advantages of coded cooperative data exchange has been studied in the literature. In this problem, a group of wireless clients are interested in the same set of packets (a multicast scenario). Each client initially holds a subset of packets and wills to obtain its missing packets in a cooperative setting by exchanging packets with its peers. Cooperation via short range transmission links among the clients (which are faster, cheaper and more reliable) is an alternative for retransmissions by the base station. In this paper, we extend the problem of cooperative data exchange to the case of multiple unicasts to a set of n clients, where each client ciis interested in a specific message xiand the clients cooperate with each others to compensate the errors occurred over the downlink. Moreover, our proposed method maintains the secrecy of individuals' messages at the price of a substantially small overhead.

We propose a method to reduce the spectrum noise when compressed sensing (CS) is applied to spectrum sensing. Since CS is susceptible to noise, the quality of the recovered spectrum using CS can be significantly degraded if the measurements are contaminated with noise. This will be particularly problematic in case of detecting weak signals. In this paper, a method which exploits the diversity of CS measurements is introduced to reduce the noise of CS recovered spectrum. Diversity gain is extracted from measurements using only a single physical sensor, but with virtual parallel branches. The results show that the noise is reduced sufficiently to detect weak signals using our method.

This paper describes a novel mechanism for joint decoding of the network coded symbols in a multi-way relay node. The mechanism, based on belief propagation algorithm, utilizes the correlation between adjacent network coded symbols to minimize the error propagation problem significantly, compared with previous methods. In case of increasing degree of asynchrony, disjoint decoding exhibits poorer error performance, whereas joint decoding helps to maintain the performance level close to that in the synchronous case both in additive white Gaussian noise and fading channels. Thus, this method adds robustness to the multi-way relay channel against channel imperfections like asynchronism and fading in practical propagation environments.

This paper studies feedback based instantly decodable network coding with the aim of minimizing decoding delay per transmission over wireless broadcast erasure channels with memory. We model such channels with a Gilbert-Elliott two-state Markov model with good and bad states. We first present a weighted sum generalized instantly decodable network coding (G-IDNC) scheme, where the aim is to service a subset of receivers with expected good channel state. We then propose an improved variation of the weighted sum G-IDNC that appropriately targets a broader set of receivers (while giving initial priority to receivers with expected good channel state) to reduce decoding delay over a wider range of erasure channels with memory. Simulation results show that our proposed improved weighted sum G-IDNC algorithm always considerably outperforms an earlier approach in the literature for erasure channels with memory, namely the weighted sum strict instantly decodable network coding (S-IDNC).

In this paper we study in-order packet delivery delay of two recently proposed network coded transmission schemes with applications in wireless broadcast. Unlike previous works where asymptotic behaviour of decoding or delivery delay was presented, we provide a general analysis of the three conditions under which in-order packet delivery is possible at a receiver: by 1) catching up with the sender, 2) receiving while a leader, and 3) chance decoding. We use a Markov model to represent the difference between the knowledge space of the sender and a receiver. For the first condition, we calculate the expected distribution of decoding cycle lengths under the Markov model. For the second condition, we propose to use a simplifying independent Markov model among receivers to shed light on the factors that determine the probability of receiving while a leader. Finally, we compare the chance decoding probabilities of two transmission schemes and a baseline random transmission algorithm to show that surprisingly (and fortunately) the probability of chance decoding is significant in one of the transmission schemes. We verify our analysis by extensive simulations and discuss the usefulness of our study for understanding and design of better transmission algorithms.

Physical-layer network coding (PNC) promises a significant gain In overall network throughput for multi-user cooperative communications. In a multi-unicast scenario, one drawback associated with PNC is an additional noise term, coined as network coding (NC) noise, which severely degrades the system data rate. In this paper, our contribution to address this challenging problem is source and relay power control with the objective of maximization of the minimum average achievable rate among all the source-destination pairs subject to a given total power constraint. We further develop a joint power allocation and relay selection scheme, which only rely on long-term channel statistics, to extend our results to general network topologies. We show that the joint optimization problem can be divided into two problems: optimal power allocation and optimal relay selection where the former is scalable and leads to a power assignment algorithm that exhibits the same optimization complexity for any number of sources in the network and the latter can be performed in a decentralized manner. By means of simulations, we validate our theoretical developments and verify the efficiency of our algorithm in improving the average achievable rate compared to a multi-unicast system with no power control or relay selection. We conclude that the proposed algorithm largely combats the adverse effects of NC noise while achieving near optimal fairness.

Femtocell has appeared as a solution to increase both coverage and capacity of cellular networks. However, interference problem between the macrocell and the femtocell must be solved before any deployment. In this paper, we deal with the problem of joint subband, rate, and power allocation in OFDMA based two-tier femtocell networks. It is assumed that for macrocell users, spectrum allocation is accomplished through Fractional Frequency Reuse (FFR). Our objective is to maximize the femtocell user's throughput while maintaining as little as possible reduction in the macrocell users' performance. Our proposed algorithm is decentralized, and needs to be done only when femtocell access point is plugged in, based on some measurements. Simulation results show superior performance of the proposed scheme compared to the other methods.

We propose a new architecture for broadcasting an enormous amount of information over a large population of users in a typical urban area via multiple base stations for delay tolerant applications. The core idea is that each base station partially broadcasts the information instead of transmitting the whole information. In particular, the large target file is broken into M smaller chunks and is provided to N base stations. Each base station i independently generates Mi<; M linear combinations of the chunks using random linear network coding (RLNC) techniques and broadcasts it to the users in its coverage area. Users then code and exchange packets in their possession via their short range communication links (e.g. bluetooth). Thanks to the random nature of human mobility patterns, it is expected that after a while, the placement of the users would be mixed enough so that users can obtain sufficient number of chunks to decode the entire file. The proposed architecture provides a fundamentally bandwidth efficient scheme for delay tolerant broadcast applications and has the potential to be implemented in practice. In particular, the proposed approach is completely opportunistic i.e. it does not require any routing algorithm. We evaluate the performance of the proposed architecture via extensive simulations using a well known human mobility patterns simulator.

In this study, the authors optimise the outage probability of amplify and forward incremental relaying (IR) scheme using two different power allocation methods in the presence of channel estimation errors. The authors find the outage probability of IR scheme and minimise it subject to traditional power (TP) constraint in which the sum of nodes' powers is fixed and outage-dependent power (ODP) constraint which is compatible with the physical concept of IR and takes into account the quality of the direct path in the optimisation problem. The authors provide closed-form expressions to allocate power to pilot and data symbols of both the source and the relay. Although, their analysis uses high signal-to-noise-ratio (SNR) approximation, the analytical solutions perform very close to optimal ones obtained through global numerical search. The authors show that ODP constraint has substantial superiority over TP constraint, especially when the relay is placed close to the source. Moreover, the authors compare power-optimised IR subject to the mentioned power constraints with equal power allocation scheme and show the impact of power optimisation on the outage performance of IR system.

Synchronization between the received signals from several transmitters is a challenging problem for cooperative communications. In the literature it is often assumed that the signals are somehow perfectly synchronized, but the problem of communication with asynchronism is rarely addressed. Moreover, in the few works where the problem is addressed, the proposed techniques are designed for a maximum delay whose value determines the decoding complexity. Thus in practice, only small delays can be dealt with. In this paper, instead of trying to avoid asynchronism between the received signals from two different transmitters, we propose to exploit it to provide cooperative diversity by optimally combining the two signals resulting from forward and backward zigzag interference cancellation. In addition to being tolerant to any delay, our bit error rate derivations and simulations show that the proposed scheme provides similar performance as delay-tolerant space-time block codes, such as the delay-tolerant Alamouti code, with a much lower complexity compared to a maximum likelihood (ML) decoder.

This paper considers the problem of construction of low-pass filters on the unit sphere, which has wide ranging applications in the processing of signals on the unit sphere. We propose a design criterion for the construction of strictly bandlimited low-pass filters in the spectral domain with optimal concentration in the specified polar cap region in the spatial domain. Our approach uses the weighted sum of the first optimally concentrated eigenfunctions from appropriately formulated Slepian concentration problems on the sphere. Furthermore, in order to reduce the computational complexity of the proposed algorithm, we develop a closed-form expression to accurately model these eigenfunctions. We illustrate the construction of low-pass filters using the proposed approach and demonstrate the advantage of our method approach compared to a diffusion based approach in the literature in terms of control over both bandwidth in the spectral domain and concentration in the spatial domain.

In this paper we propose a novel timing and frequency synchronization and decoding method for the PI symbol in DVB-T2 based on the correlation between the received signal and the time domain PI symbols. This method does not require post-FFT decoding and is insensitive to the frequency-shift offset and continuous-wave (CW) interference. The performance of the proposed method is evaluated via computer simulations, which shows that not only does it achieve good synchronization performance, but also it provides a decoding SNR gain of at least 6dB in AWGN channel and at least 2dB in multipath Rayleigh fading channel compared with the performance reported in the standard guidelines.

We introduce a homogeneous r-regular network model for a peer-to-peer (P2P) video broadcast network. Such networks are simple to construct and allow the implementation of fairness strategies. We use our model to show why the greedy and rarest first push-based strategies give the suboptimal performance often observed in the literature. We propose a novel network coding based transmission strategy and prove that it results in optimal playback delay and throughput performance.

In this paper, we propose to implement the dynamic decode-and-forward (DDF) protocol with distributed rotations. In addition to being one of the first implementations of the DDF protocol proposed for any number of relays, this technique allows to exploit cooperative diversity without inducing the high decoding complexity of a space-time code. The analysis of outage probabilities for different number of relays and rotations shows that the performance of this technique is close to optimal. Moreover, a lower-bound on the diversity-multiplexing gain tradeoff (DMT) is provided in the case of a single relay and two rotations. This lower-bound reaches the optimal DDF's DMT when the frame-length grows to infinity, which shows that even a small number of rotations is enough to obtain good performance.

Network coding (NC) is known as a promising approach to improve the cooperative communication network throughput. However, in certain situations, it can introduce additional noise terms which is recently referred to as NC noise. We consider such a problem in a two-unicast wireless system and seek to answer the following question: “Can we reduce or remove network coding noise by proper power allocation at the relay?” To this end, we provide a mathematical framework for the output signal-to-noise (SNR) ratio and instantaneous sum-rate of the network-coded cooperative communication (NC-CC) system with the notion of power assignment at the relay. Based on this framework, we provide two novel closed-form power allocation techniques that are suitable for slow and fast fading conditions. Numerical analysis is used to confirm the accuracy of the derived theory and to show the effectiveness of proposed solutions in terms of average sum-rate and outage probability. It is shown that such techniques offer a significant advantage in overcoming the adverse effects of NC noise, especially in slow fading, without introducing significant extra costs or system complexity.

In this paper, we generalize the problem of network coded cooperative data exchange from a fixed broadcast topology to dynamic networks with mobile peers. In this problem a group of wireless clients are interested in obtaining a set of packets through cooperation, where each client initially holds a subset of packets. Unlike recent studies where cooperation is enabled through a fixed error free broadcast channel among fixed or stationary peers, we assume that peers move randomly between transmission rounds, have a limited transmission range and suffer from packet erasures. In this case giving an exact solution to the problem of minimum number of transmissions is difficult, if not impossible. Therefore, we propose two different heuristic transmission strategies to decrease the total number of transmissions compared to uncoded transmissions. We compare the performance of these two strategies in terms of energy consumption (total number of transmissions) by analysis and simulations. In particular, we show that when packet delivery delay is not an issue, the total number of transmissions can be dramatically decreased at the price of a small overhead.

We formulate a capacity lower bound for the dual-hop wireless relay channel which employs an amplify-and-forward (AF) protocol at the relay node. In AF relaying, even when the fading channel in both hops is complex Gaussian distributed, the overall dual-hop channel is non-Gaussian. WPe highlight that there is a fundamental difference between Gaussian and non-Gaussian channels in terms of deriving their capacity lower bound. Specifically for non-Gaussian channels, the channel estimation error variance depends on the received pilot signal and is, in general, different from the average error variance. Whereas for Gaussian distributed channels, which have been predominantly studied in the literature, the channel estimation error variance conditioned on the observed pilot signal coincides with the average error variance. We provide an example using the AF dual-hop channel to exhibit the numerical difference between the true capacity lower bound and that obtained by using the average instead of the conditional error variance.

This paper studies the statistical properties of the signal-to-noise ratio (SNR) of the dual-hop relaying link in a cooperative wireless communication system in the presence of channel estimation errors for fixed-gain (FG) and variable-gain (VG) relays. The SNR expression is derived and three different analytical approaches with different simplifying assumptions are proposed to obtain the probability distribution function of the SNR and the outage probability in each mode. All but one approach result in closed-form expressions for the outage probability. The simplest approach in each mode has been used to find an optimum power allocation scheme for pilot and data symbols transmission at the source and the relay that results in minimizing the outage probability. Numerical analysis is used to confirm the accuracy of the derived theory and to show that the analytical approaches have a good outage performance, especially as the relay-destination distance increases. It is shown that significant power savings (e.g. 6 dB in VG mode) can be obtained by using the proposed power optimization method.

We consider scenarios where wireless clients are missing some packets, but they collectively know every packet. The clients collaborate to exchange missing packets over an error-free broadcast channel with capacity of one packet per channel use. First, we present an algorithm that allows each client to obtain missing packets, with minimum number of transmissions. The algorithm employs random linear coding over a sufficiently large field. Next, we show that the field size can be reduced while maintaining the same number of transmissions. Finally, we establish lower and upper bounds on the minimum number of transmissions that are easily computable and often tight as demonstrated by numerical simulations.

We study the design of training-based multiple-input multiple-output systems in two block-wise transmission schemes. The conventional transmission scheme has a fixed amount of energy to be used in each block, hence transmission takes place in every block. For this scheme, we study the optimality of using all available time in each block for transmission and provide bounds to significantly reduce the ranges of the possible values of the optimal training and data lengths. The second scheme, called the flashy transmission scheme, is constrained by an average amount of energy per block, and uses some but not necessarily all blocks for transmission. For this scheme, we find the optimal fraction of blocks to be used for transmission. When this optimal fraction is less than one, we show that the optimal training and data lengths are independent of the energy constraint.

In this letter, we consider multiple-input single-output (MISO) systems with two-way training based transmission. We focus on the long-term system performance and study the optimal power allocation between reverse training, forward training and data transmission. We derive closed-form solutions for the optimal power allocation using high signal-to-noise ratio (SNR) approximations, and show that they achieve near optimal performance in terms of symbol error rate (SER) for different modulation schemes over a wide range of SNR values.

We consider a wireless multi-hop network and design an algorithm for jointly optimal scheduling of packet transmissions and network coding. We consider network coding across different users, however with the restriction that packets have to be decoded after one hop. We compute the stability region of this scheme and propose an online algorithm that stabilizes every arrival rate vector within the stability region. The online algorithm requires computation of stable sets in an appropriately defined conflict graph. We show by means of simulations that this inherently hard problem is tractable for some instances and that network coding extends the stability region over routing and leads, on average, to a smaller backlog.

In this paper, we consider multiple-input multiple-output (MIMO) communication systems with combined channel covariance feedback (CCF) and channel gain feedback (CGF), hereafter called hybrid CCF-CGF systems. Using an ergodic capacity lower bound as the figure of merit, we investigate the optimal training and data transmission strategies as well as the optimal transmit resource allocation. We prove that the optimal structure for data transmission follows a water-filling solution according to the estimated channel gains, rotated and truncated into the trained eigen-directions. We analytically find the range of the optimal training length. Through numerical evaluations we also show that a closed-form solution of the training power allocation achieves near optimal performance. Finally, we show that the capacity of hybrid CCF-CGF systems can be significantly increased by adding extra transmit antennas without increasing the training resources or feedback overhead.

We consider the problem of modelling a randomly time-varying frequency-selective fading channel as a finite-state Markov channel (FSMC). For a fading channel with two correlated taps and given statistical parameters, the accuracy of an FSMC is assessed by comparing its information rate, when the receiver has ideal channel-state information, to that of the original continuous-valued channel. We show that in order to construct an FSMC with a given desired accuracy, fewer states are required if the correlation between taps is taken into account than if the taps are treated as being independent. These results demonstrate the suitability and accuracy of FSMCs for modelling a time-varying frequency-selective fading channel with memory.

We consider the problem of minimizing upper bounds and maximizing lower bounds on information rates of stationary and ergodic discrete-time channels with memory. The channels we consider can have a finite number of states, such as partial response channels, or they can have an infinite state space, such as time-varying fading channels. We optimize recently proposed information rate bounds for such channels, which make use of auxiliary finite-state machine channels (FSMCs). Our main contribution in this paper is to provide iterative expectation-maximization (EM) type algorithms to optimize the parameters of the auxiliary FSMC to tighten these bounds. We provide an explicit, iterative algorithm that improves the upper bound at each iteration. We also provide an effective method for iteratively optimizing the lower bound. To demonstrate the effectiveness of our algorithms, we provide several examples of partial response and fading channels where the proposed optimization techniques significantly tighten the initial upper and lower bounds. Finally, we compare our results with results obtained by the conjugate gradient optimization algorithm and an improved variation of the simplex algorithm, called Soblex. While the computational complexities of our algorithms are similar to the conjugate gradient method and less than the Soblex algorithm, our algorithms robustly find the tightest bounds. Interestingly, from a channel coding/decoding perspective, optimizing the lower bound is related to increasing the achievable mismatched information rate, i.e., the information rate of a communication system where the decoder at the receiver is matched to the auxiliary channel, and not to the original channel.

We consider the optimum design of pilot-symbol-assisted modulation (PSAM) schemes with feedback. The received signal is periodically fed back to the transmitter through a noiseless delayed link and the time-varying channel is modeled as a Gauss-Markov process. We optimize a lower bound on the channel capacity which incorporates the PSAM parameters and Kalman-based channel estimation and prediction. The parameters available for the capacity optimization are the data power adaptation strategy, pilot spacing and pilot power ratio, subject to an average power constraint. Compared to the optimized open-loop PSAM (i.e., the case where no feedback is provided from the receiver), our results show that even in the presence of feedback delay, the optimized power adaptation provides higher information rates at low signal-to-noise ratios (SNR) in medium-rate fading channels. However, in fast fading channels, even the presence of modest feedback delay dissipates the advantages of power adaptation.

We study the optimal antenna configuration (i.e. number of transmit and receive antennas) for multiple-input multiple-output systems in pilot-symbol-assisted modulation schemes with imperfect channel estimation. We assume block flat-fading channels and focus on a practical range of high signal-to-noise ratio. An ergodic capacity lower bound is used as the objective function to be maximized. We analytically study the capacity gain from adding extra antennas to the transmitter or to the receiver in two different scenarios. Our numerical results show that the optimal antenna configuration under imperfect channel estimation can be significantly different from that under perfect channel estimation assumption. In addition, we investigate the capacity gain from optimizing antenna configuration and find that the gain can be larger than that achieved by optimizing transmit power over pilot and data symbols, particularly for large block lengths.

We study the design parameters of pilot-symbol-assisted modulation (PSAM) schemes for spatially correlated single-input multiple-output (SIMO) systems in time-varying Gauss-Markov flat-fading channels. We use an information capacity lower bound as our figure of merit. We investigate the optimum design parameters, including the ratio of power allocated to the pilots and the fraction of time occupied by the pilots, for SIMO systems with different antenna sizes and with spatial channel correlation. Our main finding is that by optimally designing the training parameters for single-input single-output (SISO) systems, the same parameters can be used to achieve near optimum capacity in both spatially independent and correlated SIMO systems for the same fading rate and signal-to-noise ratio (SNR). In addition, we show that spatially independent channels give the lowest capacity at sufficiently low SNR. These findings provide insights into the design of practical PSAM systems.

We study information rates of time-varying flat-fading channels (FFC) modeled as finite-state Markov channels (FSMC). FSMCs have two main applications for FFCs: modeling channel error bursts and decoding at the receiver. Our main finding in the first application is that receiver observation noise can more adversely affect higher-order FSMCs than lower-order FSMCs, resulting in lower capacities. This is despite the fact that the underlying higher-order FFC and its corresponding FSMC are more predictable. Numerical analysis shows that at low to medium SNR conditions (SNR lsim 12 dB) and at medium to fast normalized fading rates (0.01 lsim fDT lsim 0.10), FSMC information rates are non-increasing functions of memory order. We conclude that BERs obtained by low-order FSMC modeling can provide optimistic results. To explain the capacity behavior, we present a methodology that enables analytical comparison of FSMC capacities with different memory orders. We establish sufficient conditions that predict higher/lower capacity of a reduced-order FSMC, compared to its original high-order FSMC counterpart. Finally, we investigate the achievable information rates in FSMC-based receivers for FFCs. We observe that high-order FSMC modeling at the receiver side results in a negligible information rate increase for normalized fading rates fDT lsim 0.01.

Conventional mutual information (Ml)-based registration using pixel intensities is time-consuming and ignores spatial information, which can lead to misalignment. We propose a method to overcome these limitation by acquiring initial estimates of transformation parameters. We introduce the concept of 'gradient intensity' as a measure of spatial strength of an image in a given direction. We determine the rotation parameter by maximizing the MI between gradient intensity histograms. Calculation of the gradient intensity MI function is extremely efficient. Our method is designed to be invariant to scale and translation between the images. We then obtain estimates of scale and translation parameters using methods based on the centroids of gradient images. The estimated parameters are used to initialize an optimization algorithm which is designed to converge more quickly than the standard Powell algorithm in close proximity of the minimum. Experiments show that our method significantly improves the performance of the registration task and reduces the overall computational complexity by an order of magnitude.

In this paper, we present a novel approach to detection of one dimensional bar code images. Our algorithm is particularly designed to recognize bar codes, where the image may be of low resolution, low quality or suffer from substantial blurring, de-focusing, non-uniform illumination, noise and color saturation. The algorithm is accurate, fast, scalable and can be easily adjusted to search for a valid result within a specified time constraint. Our algorithm is particularly useful for real-time recognition of bar codes in portable hand-held devices with limited processing capability, such as mobile phones.

We present a fast and accurate framework for registration of multi-modal volumetric images based on decoupled estimation of registration parameters utilizing spatial information in the form of 'gradient intensity'. We introduce gradient intensity as a measure of spatial strength of an image in a given direction and show that it can be used to determine the rotational misalignment independent of translation between the images. The rotation parameters are obtained by maximizing the mutual information of 2D gradient intensity matrices obtained from 3D images, hence reducing the dimensionality of the problem and improving efficiency. The rotation parameters along with estimations of translation are then used to initialize an optimization step over a conventional pixel intensity-based method to achieve sub-voxel accuracy. Our optimization algorithm converges quickly and is less subject to the common problem of misregistration due to local extrema. Experiments show that our method significantly improves the robustness, performance and efficiency of registration compared to conventional pixel intensity-based methods.

We consider the problem of optimizing information rate upper and lower bounds for communication channels with (possibly large) memory. A recently proposed auxiliary-channel- based technique allows one to efficiently compute upper and lower bounds on the information rate of such channels. Towards tightening these bounds, we propose iterative expectation- maximization (EM) type algorithms to optimize the parameters of the auxiliary finite-state machine channel (FSMC). From a channel coding perspective, optimizing the lower bound is related to increasing the achievable mismatched information rate, i.e. the information rate of a communication system where the maximum-likelihood decoder at the receiver is matched to the auxiliary channel and not to the true channel. We provide explicit solutions for optimizing the upper bound and the difference between the upper and the lower bound and we discuss a method for the optimization of the lower bound for data-controllable channels with memory. We discuss examples of channels with memory, for which application of the developed theory results in noticeably tighter information rate bounds.

We study the dimensions or degrees of freedom of random multipath fields in wireless communications. Random multipath fields are presented as solutions to the wave equation in an infinite-dimensional vector space. We prove a universal bound for the dimension of random multipath field in the mean square error sense. The derived maximum dimension is directly proportional to the radius of the two-dimensional spatial region where the field is coupled to. Using the Karhunen-Loeve expansion of multipath fields, we prove that, among all random multipath fields, isotropic random multipath achieves the maximum dimension bound. These results mathematically quantify the imprecise notion of rich scattering that is often used in multiple-antenna communication theory and show that even the richest scatterer (isotropic) has a finite intrinsic dimension

In this paper, we study the effect of directional random scattering on the capacity of multiple-input multiple-output (MIMO) systems. First, we use the spatial decomposition of the MIMO channel matrix to analyze the randomness (entropy) of directional scattering. The analysis shows that directional scatterers (with at least a null in the angular power spectrum) will no longer be random when the receiver observation radius is sufficiently large. Therefore, directional scattering limits the expected linear increase of MIMO capacity with increasing the number of antennas. Second, we consider the effect of receiver antenna arrangement (positions) on the capacity of MIMO systems. For any random scatterer with a given angular power spectrum, we show that it is possible to choose the receiver antenna arrangement with the optimum whitening of the MIMO channel matrix that, in turn, maximizes MIMO channel capacity.

In this paper, we study the effect of channel memory order on the information rate bounds in time-varying flat-fading (FF) channels. We model time variations of the FF channel with autoregressive (AR) processes with varying degrees of model order. We observe that in high SNR conditions (SNR 20 dB), the information rate penalty of not knowing the AR channel is a non-increasing function of the AR model order. This is expected, since the AR channel predictability cannot decrease with increasing its order. However, in low SNR conditions, the information rate penalty in low-order AR channels can be lower than those in high-order AR channels. Likewise, the intuitive and universal monotonic increase of the information rate bounds with the AR model order is only observed in almost noiseless conditions. In the low SNR regime, however, the achievable information rate bounds in low-order AR channels can be higher than those in high-order AR channels.

In this paper, we study the effect of memory order on the capacity of finite-state Markov channels (FSMC). We analytically compare the capacity of an originally high-order FSMC model with the capacity of its reduced memory order version. We show that the capacity difference is caused by two factors: 1) the channel entropy difference, and 2) the channel observability difference between the two models. While the first factor, alone, results in underestimation of the original FSMC capacity by the reduced-order FSMC model, due to the existence of the second factor, capacity overestimation can also occur. Explicit examples of FSMC models are provided, where the reduced-order FSMC model overestimates the capacity of the original high-order channel. To show the practical significance of the analysis, we model time-varying flat-fading (FF) channels with FSMC models. It is observed that the first-order FSMC models can provide both higher and lower estimates of the FF channel capacity, compared to higher order FSMC models

In this paper, time-varying flat-fading channels are modeled as first-order finite-state Markov channels (FSMC). The effect of this modeling on the channel information capacity is addressed. The approximation accuracy of the first-order memory assumption in the Markov model is validated by comparing the FSMC capacity with the channel capacity assuming perfect state information at the receiver side. The results indicate that the first-order Markovian assumption is accurate for normalized Doppler frequencies f/sub d/T /spl lsim/ 0.01, in amplitude-only quantization of the channel gain for noncoherent binary signaling. In phase-only and joint phase and amplitude quantization of the channel gain for coherent binary signaling, the first-order Markovian assumption is accurate for f/sub d/T /spl lsim/ 0.001. Furthermore, the effect of channel quantization thresholds on the FSMC capacity is studied. In high signal-to-noise ratio (SNR) conditions, nonuniform two-level amplitude quantization scheme outperforms equiprobable quantization method by 0.8-1.5 dB.

The effect of channel gain quantization on the information capacity of unknown time varying flat fading channels is investigated. The phase and/or amplitude of the flat fading channel gain is modelled as a finite state Markov (FSM) process and the information capacity of the FSM channel is calculated numerically as a measure for choosing the number of channel quantization levels, as well as quantization thresholds. The results indicate that for binary signalling, the capacity is saturated beyond 8 to 16 levels of phase and 8 to 16 levels of amplitude quantization.

In this paper we compare two different methods for receiver training in flat fading channels. The first method is the traditional way in which periodic training sequences are sent to the receiver (explicit training). In the second method, recently proposed, the information source emits bits with unequal probabilities of being '0' and '1'. This method is called implicit training, since the training is implied in the non-symmetrical source structure. BPSK signaling is used as the simplest example of constant-envelope phase modulations. We map the phase component of the flat fading channel response to a simple two-state Markov model. Then joint iterative trellis-based maximum a posteriori probability (MAP) method is used for channel state estimation and decoding. The results of computer simulations for the receiver bit error rate (BER) performance in various channel fading rates and information rates are presented. The results indicate superior performance of implicit training. In slow fading conditions, the gain is 4 dB at information rate of 0.15 bits/channel use and 1.2 dB for information rate of 0.25 bits/channel use.