We consider the problem of finding the minimum sum-rate strategy in cooperative data exchange systems that do not allow packet-splitting (NPS-CDE). In an NPS-CDE system, there are a number of geographically close cooperative clients who send packets to help the others recover a packet set. A minimum sum-rate strategy is the strategy that achieves universal recovery (the situation when all the clients recover the whole packet set) with the the minimal sum-rate (the total number of transmissions). We propose an iterative merging (IM) algorithm that recursively merges client sets based on a lower estimate of the minimum sum-rate and updates to the value of the minimum sum-rate. We also show that a minimum sum-rate strategy can be learned by allocating rates for the local recovery in each merged client set in the IM algorithm. We run an experiment to show that the complexity of the IM algorithm is lower than that of the existing deterministic algorithm when the number of clients is lower than 94.
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.
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.
In this paper, we study the problem of distributing a real-time video sequence to a group of partially connected cooperative wireless devices using instantly decodable network coding (IDNC). In such a scenario, the coding conflicts occur to service multiple devices with an immediately decodable packet and the transmission conflicts occur from simultaneous transmissions of multiple devices. To avoid these conflicts, we introduce a novel IDNC graph that represents all feasible coding and transmission conflict-free decisions in one unified framework. Moreover, a real-time video sequence has a hard deadline and unequal importance of video packets. Using these video characteristics and the new IDNC graph, we formulate the problem of minimizing the mean video distortion before the deadline as a finite horizon Markov decision process (MDP) problem. However, the backward induction algorithm that finds the optimal policy of the MDP formulation has high modelling and computational complexities. To reduce these complexities, we further design a two-stage maximal independent set selection algorithm, which can efficiently reduce the mean video distortion before the deadline. Simulation results over a real video sequence show that our proposed IDNC algorithms improve the received video quality compared to the existing IDNC algorithms.
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.
Information density and its exponential form, known as lift, play a central role in information privacy leakage measures. $\alpha$-lift is the power-mean of lift, which is tunable between the worst-case measure max-lift ($\alpha=\infty$) and more relaxed versions ($\alpha<\infty$). This paper investigates the optimization problem of the privacy-utility tradeoff where $\alpha$-lift and mutual information are privacy and utility measures, respectively. Due to the nonlinear nature of $\alpha$-lift for $\alpha<\infty$, finding the optimal solution is challenging. Therefore, we propose a heuristic algorithm to estimate the optimal utility for each value of $\alpha$, inspired by the optimal solution for $\alpha=\infty$. In proposing the algorithm, we prove and use the convexity of $\alpha$-lift with respect to the lift.
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 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 UEs. Otherwise, the broadcast transmission scheme is more appropriate.
Recent advancements in graph-based analysis and solutions of instantly decodable network coding (IDNC) trigger the interest to extend them to more complicated opportunistic network coding (ONC) scenarios, with limited increase in complexity. In this paper, we design a simple IDNC-like graph model for a specific subclass of ONC, by introducing a more generalized definition of its vertices and the notion of vertex aggregation in order to represent the storage of non-instantly-decodable packets in ONC. Based on this representation, we determine the set of pairwise vertex adjacency conditions that can populate this graph with edges so as to guarantee decodability or aggregation for the vertices of each clique in this graph. We then develop the algorithmic procedures that can be applied on the designed graph model to optimize any performance metric for this ONC subclass. A case study on reducing the completion time shows that the proposed framework improves on the performance of IDNC and gets very close to the optimal performance.
In this paper, we investigate the use of instantly decodable network coding (IDNC) for improving two fundamental performance metrics, namely, the completion time (as a measure of throughput) and mean decoding delay, in multicast cooperative data exchange (CDE) systems, where a group of geographically close clients cooperate with each other to obtain their missing packets. Here, an IDNC scheme is used for the transmissions across these clients. We utilize the stochastic shortest path (SSP) technique to study the minimum mean completion time problem. However, since finding the optimum solution is intractable, we use the obtained formulation to draw some theoretical guidelines to heuristically find solutions that can efficiently reduce the completion time. Second, we formulate the minimum mean decoding delay problem as selecting the appropriate maximal clique over well-structured graphs at the clients, and in order to reduce its complexity, we propose a simple heuristic algorithm for it. The effectiveness of our proposed algorithms is verified through extensive simulations and comparisons with existing techniques.
'/%3e%3c/defs%3e%3cpath fill='%23012169' d='M0 0h10080v5040H0z'/%3e%3cpath stroke='%23fff' stroke-width='.6' d='m0 0 6 3m0-3L0 3' clip-path='url(%23b)' transform='scale(840)'/%3e%3cpath stroke='%23e4002b' stroke-width='.4' d='m0 0 6 3m0-3L0 3' clip-path='url(%23c)' transform='scale(840)'/%3e%3cpath stroke='%23fff' stroke-width='840' d='M2520 0v2520M0 1260h5040'/%3e%3cpath stroke='%23e4002b' stroke-width='504' d='M2520 0v2520M0 1260h5040'/%3e%3cg fill='%23fff'%3e%3cuse xlink:href='%23d' x='2520' y='3780'/%3e%3cuse xlink:href='%23a' x='7560' y='4200'/%3e%3cuse xlink:href='%23a' x='6300' y='2205'/%3e%3cuse xlink:href='%23a' x='7560' y='840'/%3e%3cuse xlink:href='%23a' x='8680' y='1869'/%3e%3cuse xlink:href='%23e' x='8064' y='2730'/%3e%3c/g%3e%3c/svg%3e)
'%3e%3ccircle r='20' fill='%23008'/%3e%3ccircle r='17.5' fill='%23fff'/%3e%3ccircle r='3.5' fill='%23008'/%3e%3cg id='d'%3e%3cg id='c'%3e%3cg id='b'%3e%3cg id='a' fill='%23008'%3e%3ccircle r='.875' transform='rotate(7.5 -8.75 133.5)'/%3e%3cpath d='M0 17.5.6 7 0 2l-.6 5L0 17.5z'/%3e%3c/g%3e%3cuse xlink:href='%23a' transform='rotate(15)'/%3e%3c/g%3e%3cuse xlink:href='%23b' transform='rotate(30)'/%3e%3c/g%3e%3cuse xlink:href='%23c' transform='rotate(60)'/%3e%3c/g%3e%3cuse xlink:href='%23d' transform='rotate(120)'/%3e%3cuse xlink:href='%23d' transform='rotate(-120)'/%3e%3c/g%3e%3c/svg%3e)