With the abundance of data, machine learning applications engaged increased attention in the last decade. An attractive approach to robustify the statistical analysis is to preprocess the data through clustering. This paper develops a low-complexity Riemannian optimization framework for solving optimization problems on the set of positive semidefinite stochastic matrices. The low-complexity feature of the proposed algorithms stems from the factorization of the optimization variable$\mathbf{X}=\mathbf{Y}\mathbf{Y}^{\mathrm{T}}$and deriving conditions on the number of columns of$\mathbf{Y}$under which the factorization yields a satisfactory solution. The paper further investigates the embedded and quotient geometries of the resulting Riemannian manifolds. In particular, the paper explicitly derives the tangent space, Riemannian gradients and Hessians, and a retraction operator allowing the design of efficient first and second-order optimization methods for the graph-based clustering applications of interest. The numerical results reveal that the resulting algorithms present a clear complexity advantage as compared with state-of-the-art Euclidean and Riemannian approaches for graph clustering applications.

Cloud radio access networks (C-RANs) are promising paradigms for the fifth-generation (5G) networks due to their interference management capabilities. In a C-RAN, a central processor (CP) is responsible for coordinating multiple Remote Radio Heads (RRHs) and scheduling users to their radio resource blocks (RRBs). In this paper, we develop a novelcross-layer network coding (CLNC)approach that proposes to optimize RRH’s transmit powers and user’s rates in making the coding decisions. As such, cross-layer throughput of the network is maximized. The joint user scheduling, file encoding, and power adaptation problem is solved by designing a subgraph for each RRB, in which each vertex represents potential user-RRH associations, encoded files, transmission rates, and power levels (PLs) for one RRB. It is then shown that the C-RAN throughput maximization problem is equivalent to a maximum-weight clique problem over the union of all such subgraphs, called herein the CRAN-CLNC graph. Numerical results revealed that the proposed joint and iterative schemes offer improved throughput performances as compared to the existing algorithms in the literature. Compared to our proposed joint scheme, our proposed iterative scheme has a certain degradation, roughly in the range of 9%–14%. This small degradation in the throughput performance of the iterative scheme comes at the achieved low computational complexity as compared to the high complexity of the joint scheme.

Since its first use by Euler on the problem of the seven bridges of Königsberg, graph theory has shown excellent abilities in solving and unveiling the properties of multiple discrete optimization problems. The study of the structure of some integer programs reveals equivalence with graph theory problems making a large body of the literature readily available for solving and characterizing the complexity of these problems. This tutorial presents a framework for utilizing a particular graph theory problem, known as the clique problem, for solving communications and signal processing problems. In particular, this article aims to illustrate the structural properties of integer programs that can be formulated as clique problems through multiple examples in communications and signal processing. To that end, the first part of the tutorial provides various optimal and heuristic solutions for the maximum clique, maximum weight clique, and ${k}$ -clique problems. The tutorial, further, illustrates the use of the clique formulation through numerous contemporary examples in communications and signal processing, mainly in maximum access for nonorthogonal multiple access networks, throughput maximization using index and instantly decodable network coding, collision-free radio-frequency identification networks, and resource allocation in cloud-radio access networks. Finally, the tutorial sheds light on the recent advances of such applications, and provides technical insights on ways of dealing with mixed discrete-continuous optimization problems.

This month’s issue offers insight into efficient compression and execution of DNNs, the challenge of connecting rural areas, and the clique problem in wireless communication. which

Several real-world applications, notably in non-negative matrix factorization, graph-based clustering, and machine learning, require solving a convex optimization problem over the set of stochastic and doubly stochastic matrices. A common feature of these problems is that the optimal solution is generally a low-rank matrix. This paper suggests reformulating the problem by taking advantage of the low-rank factorization X = UVTand develops a Riemannian optimization framework for solving optimization problems on the set of low-rank stochastic and doubly stochastic matrices. In particular, this paper introduces and studies the geometry of the low-rank stochastic multinomial and the doubly stochastic manifold in order to derive first-order optimization algorithms. Being carefully designed and of lower dimension than the original problem, the proposed Riemannian optimization framework presents a clear complexity advantage. The claim is attested through numerical experiments on real-world and synthetic data for Non-negative Matrix Factorization (NFM) applications. The proposed algorithm is shown to outperform, in terms of running time, state-of-the-art methods for NFM.

Cloud radio access networks (C-RAN) gained much attention thanks to their abilities in mitigating interference and providing high data rates by coordinating multiple Remote Radio Heads (RRHs). This paper considers the use of rate aware instantly decodable network coding (RA-IDNC) as a mean to accelerate the broadcast of a set of messages to a set of users in a C-RAN setting. While previous works focus either on rate-unaware IDNC or rate adaptation for traditional single transmitter systems, this paper extends the results to C-RANs. The various ergodic capacities of the different users to the different RRHs bring a new trade-off between the number of scheduled users and the transmission rates. The proposed framework incorporates such information in the network coding decisions, so as the scheduled users, coded messages, and transmission rates reduce the overall completion time. Given the intractability of the problem, the paper proposes relaxing the optimization by an online approach involving an anticipated version of the completion time which allows mapping the possible associations between users, RRHs, coded packets, and transmission rates to vertices in a newly designed graph. Afterward, the online completion time reduction problem is shown to be equivalent to a maximum weight independent set problem over the proposed graph. Simulation results reveal that the proposed scheme achieves substantial performance gain over uncoded and NC rate-unaware algorithms.

Given a data matrix with partially observed entries, the low-rank matrix completion problem is one of finding a matrix with the lowest rank that perfectly fits the given observations. While there exist convex relaxations for the low-rank completion problem, the underlying problem is inherently nonconvex, and most algorithms (alternating projection, Riemannian optimization, etc.) heavily depend on the initialization. This paper proposes an improved initialization that relies on successive rank-l updates. Further, the paper proposes theoretical guarantees under which the proposed initialization is closer to the unknown optimal solution than the all zeros initialization in the Frobenius norm. To cope with the problem of local minima, the paper introduces and uses random norms to change the position of the local minima while preserving the global one. Using a Riemannian optimization routine, simulation results reveal that the proposed solution succeeds in completing Gaussian partially observed matrices with a random set of revealed entries close to the information-theoretical limits, thereby significantly improving on prior methods.

This paper develops a Riemannian optimization framework for solving optimization problems on the set of symmetric positive semidefinite stochastic matrices. The paper first reformulates the problem by factorizing the optimization variable as $\mathbf{X}=\mathbf{Y}\mathbf{Y}^T$ and deriving conditions on $p$, i.e., the number of columns of $\mathbf{Y}$, under which the factorization yields a satisfactory solution. The reparameterization of the problem allows its formulation as an optimization over either an embedded or quotient Riemannian manifold whose geometries are investigated. In particular, the paper explicitly derives the tangent space, Riemannian gradients and retraction operator that allow the design of efficient optimization methods on the proposed manifolds. The numerical results reveal that, when the optimal solution has a known low-rank, the resulting algorithms present a clear complexity advantage when compared with state-of-the-art Euclidean and Riemannian approaches for graph clustering applications.

Cloud radio access network (CRAN) emerges as a promising architecture for large-scale interference management. This paper addresses the benefit of one particular type of coordinated resource allocation in CRANs through the combined effect of joint scheduling and beamforming. Consider the downlink of a CRAN where the cloud is connected to several remote radio heads (RRHs), each equipped with multiple antennas. The transmit frame of every RRH is formed by several radio resource blocks (RRBs), each capable of serving multiple single-antenna users via spatial multiplexing using beamforming. The paper focuses on the problem of maximizing the network-wide weighted sum-rate by jointly determining the set of scheduled users at each RRB, and their corresponding beamforming vectors. The main contribution of the paper is to solve such a mixed discrete-continuous optimization problem using a graph-theoretical based approach. The paper introduces the joint scheduling and beamforming graph, wherein each independent set accounts for a feasible schedule and feasible beamforming vectors. Afterward, the joint scheduling and beamforming problem is shown to be equivalent to a maximum independent set problem in the proposed graph. Simulation results suggest that the proposed joint solution provides appreciable performance improvements as compared to the classical iterative approach.

Recent studies on cloud-radio access networks assume either signal-level or scheduling-level coordination. This paper considers a hybrid coordinated scheme as a means to benefit from both policies. Consider the downlink of a multi-cloud radio access network, where each cloud is connected to several base-stations (BSs) via high capacity links and, therefore, allows for joint signal processing within the cloud transmission. Across the multiple clouds, however, only scheduling-level coordination is permitted, as low levels of backhaul communication are feasible. The frame structure of every BS is composed of various time/frequency blocks, called power-zones (PZs), which are maintained at a fixed power level. This paper addresses the problem of maximizing a network-wide utility by associating users to clouds and scheduling them to the PZs, under the practical constraints that each user is scheduled to a single cloud at most, but possibly to many BSs within the cloud, and can be served by one or more distinct PZs within the BSs' frame. This paper solves the problem using graph theory techniques by constructing the conflict graph. The considered scheduling problem is, then, shown to be equivalent to a maximum-weight independent set problem in the constructed graph, which can be solved using efficient techniques. This paper then proposes solving the problem using both optimal and heuristic algorithms that can be implemented in a distributed fashion across the network. The proposed distributed algorithms rely on the well-chosen structure of the constructed conflict graph utilized to solve the maximum-weight independent set problem. Simulation results suggest that the proposed optimal and heuristic hybrid scheduling strategies provide appreciable gain as compared with the scheduling-level coordinated networks, with a negligible degradation to signal-level coordination.

This paper considers a device-to-device (D2D) fog-radio access network wherein a set of users are required to store/receive a set of files. The D2D devices are connected to a subset of the cloud data centers and thus possess a subset of the data. This paper is interested in reducing the total time of communication, i.e., the completion time, required to disseminate all files among all devices using instantly decodable network coding (IDNC). Unlike previous studies that assume a fully connected communication network, this paper tackles the more realistic scenario of a partially connected network in which devices are not all in the transmission range of one another. The joint optimization of selecting the transmitting device(s) and the file combination(s) is first formulated, and its intractability is exhibited. The completion time is approximated using the celebrated decoding delay approach by deriving the relationship between the quantities in a partially connected network. The paper introduces the cooperation graph and demonstrates that the problem is equivalent to a maximum weight clique problem over the newly designed graph. Extensive simulations reveal that the proposed solution provides noticeable performance enhancement and outperforms previously proposed IDNC-based schemes.

This paper considers the problem of reducing the broadcast decoding delay of wireless networks using instantly decodable network coding- based device-to-device communications. In contrast with the previous works that assume a fully connected network, this paper investigates a partially connected configuration in which multiple devices are allowed to transmit simultaneously. To that end, different events occurring at each device are identified so as to derive an expression for the probability distribution of the decoding delay. Afterward, the joint optimization problem over the set of transmitting devices and packet combination of each is formulated. The optimal solution of the joint optimization problem is derived using a graph-theoretic approach by introducing the cooperation graph in which each vertex represents a transmitting device with a weight translating its contribution to the network. This paper solves the problem by reformulating it as a maximum weight clique problem which can efficiently be solved. Numerical results suggest that the proposed solution outperforms state-of-the-art schemes and provides significant gain, especially for poorly connected networks.

This paper considers a device-to-device (D2D) fog-radio access network wherein a set of devices are required to store a set of files. The D2D devices are connected to a subset of the cloud data centers and thus possess a subset of the data. This paper is interested in reducing the total time of communication, i.e., the completion time, needed to disseminate all files among the devices using instantly decodable network coding (IDNC). Unlike previous studies that assume a fully connected communication network, this paper tackles the more realistic scenario of a partially connected network in which devices can only target devices in their transmission range. The joint optimization of selecting the transmitting device(s) and the file combination(s) is first formulated and its intractability exhibited. The completion time is approximated using the celebrated decoding delay approach by deriving the relationship between the quantities in a partially connected network. The paper introduces the cooperation graph and demonstrates that under the collision-free transmissions assumption, the problem is equivalent to a maximum weight clique problem over the newly designed graph. Extensive simulations reveal that the proposed solution provides noticeable performance enhancement and outperforms previously proposed IDNC-based schemes.

This paper investigates the delay minimization problem for instantly decodable network coding (IDNC) based device-to-device (D2D) communications. In D2D enabled systems, users cooperate to recover all their missing packets. The paper proposes a game theoretic framework as a tool for improving the distributed solution by overcoming the need for a central controller or additional signaling in the system. The session is modeled by self-interested players in a non-cooperative potential game. The utility functions are designed so as increasing individual payoff results in a collective behavior which achieves both a desirable system performance in a shared network environment and the Nash equilibrium. Three games are developed whose first reduces the completion time, the second the maximum decoding delay and the third the sum decoding delay. The paper, further, improves the formulations by including a punishment policy upon collision occurrence so as to achieve the Nash bargaining solution. Learning algorithms are proposed for systems with complete and incomplete information, and for the imperfect feedback scenario. Numerical results suggest that the proposed game-theoretical formulation provides appreciable performance gain against the conventional point-to-multipoint (PMP), especially for reliable user-to-user channels.

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.

The radio-frequency (RF) technology is a scalable solution for the backhaul planning. However, its performance is limited in terms of data rate and latency. Free Space Optical (FSO) backhaul, on the other hand, offers a higher data rate but is sensitive to weather conditions. To combine the advantages of RF and FSO backhauls, this paper proposes a cost-efficient backhaul network using the hybrid RF/FSO technology. To ensure a resilient backhaul, the paper imposes a given degree of redundancy by connecting each node through K link-disjoint paths so as to cope with potential link failures. Hence, the network planning problem considered in this paper is the one of minimizing the total deployment cost by choosing the appropriate link type, i.e., either hybrid RF/FSO or optical fiber (OF), between each couple of base-stations while guaranteeing K link-disjoint connections, a data rate target, and a reliability threshold. The paper solves the problem using graph theory techniques. It reformulates the problem as a maximum weight clique problem in the planning graph, under a specified realistic assumption about the cost of OF and hybrid RF/FSO links. Simulation results show the cost of the different planning and suggest that the proposed heuristic solution has a close-to-optimal performance for a significant gain in computation complexity.

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.

In this paper, we address the problem of reducing the completion time of a radio access network to deliver a frame of messages using Rate Aware Instantly Decodable Network Coding (RA-IDNC). While previous works only considered a single base-station setting, this paper extends the results to a more modern paradigm of networks with multiple coordinated base-stations. The different rates of the base-stations to the various users will be thus incorporated in the network coding decisions, so as to schedule the coded messages and transmission rates jointly in order to reduce the overall completion time. Given the notorious intractability of the completion time reduction problem, the paper uses an online relaxation using an anticipated version of the completion time. This problem is then solved by showing that it is equivalent to a maximum weight independent set problem on a newly designed graph. An efficient multi-layer heuristic is further developed to address this problem in polynomial time. Simulation results suggest that the proposed solution outperforms the uncoded schemes.

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.

The deluge of date rate in today's networks imposes a cost burden on the backhaul network design. Developing cost-efficient backhaul solutions becomes an exciting, yet challenging, problem. Traditional technologies for backhaul networks, including either radio-frequency (RF) backhauls or optical fibers (OF). While RF is a cost-effective solution as compared with OF, it supports the lower data rate requirements. Another promising backhaul solution is the free-space optics (FSO) as it offers both a high data rate and a relatively low cost. The FSO, however, is sensitive to nature conditions, e.g., rain, fog, and line-of-sight. This paper combines both the RF and FSO advantages and proposes a hybrid RF/FSO backhaul solution. It considers the problem of minimizing the cost of the backhaul network by choosing either OF or hybrid RF/FSO backhaul links between the base stations, so as to satisfy data rate, connectivity, and reliability constraints. It shows that under a specified realistic assumption about the cost of OF and hybrid RF/FSO links, the problem is equivalent to a maximum weight clique problem, which can be solved with moderate complexity. Simulation results show that the proposed solution shows a close-to-optimal performance, especially for reasonable prices of the hybrid RF/FSO links. They further reveal that the hybrid RF/FSO is a cost-efficient solution and a good candidate for upgrading the existing backhaul networks.

This paper addresses the joint coordinated scheduling and power control problem in cloud-enabled networks. Consider the downlink of a cloud-radio access network (CRAN), where the cloud is only responsible for the scheduling policy, power control, and synchronization of the transmit frames across the single-antenna base-stations (BS). The transmit frame consists of several time/frequency blocks, called power-zones (PZs). The paper considers the problem of scheduling users to PZs and determining their power levels (PLs), by maximizing the weighted sum-rate under the practical constraints that each user cannot be served by more than one base-station, but can be served by one or more power-zones within each base-station frame. The paper solves the problem using a graph theoretical approach by introducing the joint scheduling and power control graph formed by several clusters, where each is formed by a set of vertices, representing the possible association of users, BSs, and PLs for one specific PZ. The problem is, then, formulated as a maximum-weight clique problem, in which the weight of each vertex is the sum of the benefits of the individual associations belonging to that vertex. Simulation results suggest that the proposed cross-layer scheme provides appreciable performance improvement as compared to schemes from recent literature.

In the context of resource allocation in cloud- radio access networks, recent studies assume either signal-level or scheduling-level coordination. This paper, instead, considers a hybrid level of coordination for the scheduling problem in the downlink of a multi-cloud radio- access network, so as to benefit from both scheduling policies. Consider a multi-cloud radio access network, where each cloud is connected to several base-stations (BSs) via high capacity links, and therefore allows joint signal processing between them. Across the multiple clouds, however, only scheduling-level coordination is permitted, as it requires a lower level of backhaul communication. The frame structure of every BS is composed of various time/frequency blocks, called power- zones (PZs), and kept at fixed power level. The paper addresses the problem of maximizing a network-wide utility by associating users to clouds and scheduling them to the PZs, under the practical constraints that each user is scheduled, at most, to a single cloud, but possibly to many BSs within the cloud, and can be served by one or more distinct PZs within the BSs' frame. The paper solves the problem using graph theory techniques by constructing the conflict graph. The scheduling problem is, then, shown to be equivalent to a maximum- weight independent set problem in the constructed graph, in which each vertex symbolizes an association of cloud, user, BS and PZ, with a weight representing the utility of that association. Simulation results suggest that the proposed hybrid scheduling strategy provides appreciable gain as compared to the scheduling-level coordinated networks, with a negligible degradation to signal-level coordination.

This paper addresses the coordinated scheduling problem in cloud-enabled networks. Consider the downlink of a cloud-radio access network (CRAN), where the cloud is only responsible for the scheduling policy and the synchronization of the transmit frames across the connected base-stations (BS). The transmitted frame of every BS consists of several time/frequency blocks, called power-zones (PZ), maintained at fixed transmit power. The paper considers the problem of scheduling users to PZs and BSs in a coordinated fashion across the network, by maximizing a network-wide utility under the practical constraint that each user cannot be served by more than one base-station, but can be served by one or more power-zones within each base-station frame. The paper solves the problem using a graph theoretical approach by introducing the scheduling graph in which each vertex represents an association of users, PZs and BSs. The problem is formulated as a maximum weight clique, in which the weight of each vertex is the benefit of the association represented by that vertex. The paper further presents heuristic algorithms with low computational complexity. Simulation results show the performance of the proposed algorithms and suggest that the heuristics perform near optimal in low shadowing environments.

This paper considers the multicast decoding delay reduction problem for generalized instantly decodable network coding (G-IDNC) over persistent erasure channels with feedback imperfections. The feedback scenario discussed is the most general situation in which the sender does not always receive acknowledgments from the receivers after each transmission and the feedback communications are subject to loss. The decoding delay increment expressions are derived and employed to express the decoding delay reduction problem as a maximum weight clique problem in the G-IDNC graph. This paper provides a theoretical analysis of the expected decoding delay increase at each time instant. Problem formulations in simpler channel and feedback models are shown to be special cases of the proposed generalized formulation. Since finding the optimal solution to the problem is known to be NP-hard, a suboptimal greedy algorithm is designed and compared with blind approaches proposed in the literature. Through extensive simulations, the proposed algorithm is shown to outperform the blind methods in all situations and to achieve significant improvement, particularly for high time-correlated channels.

For several years, the completion time and the decoding delay problems in Instantly Decodable Network Coding (IDNC) were considered separately and were thought to completely act against each other. Recently, some works aimed to balance the effects of these two important IDNC metrics but none of them studied a further optimization of one by controlling the other. In this paper, we study the effect of controlling the decoding delay to reduce the completion time below its currently best known solution. We first derive the decoding-delay-dependent expressions of the users' and their overall completion times. Although using such expressions to find the optimal overall completion time is NP-hard, we use a heuristic that minimizes the probability of increasing the maximum of these decoding-delay-dependent completion time expressions after each transmission through a layered control of their decoding delays. Simulation results show that this new algorithm achieves both a lower mean completion time and mean decoding delay compared to the best known heuristic for completion time reduction. The gap in performance becomes significant for harsh erasure scenarios.

In this paper, we introduce a game theoretic framework for studying the problem of minimizing the completion time of instantly decodable network coding (IDNC) for cooperative data exchange (CDE) in decentralized wireless network. In this configuration, clients cooperate with each other to recover the erased packets without a central controller. Game theory is employed herein as a tool for improving the distributed solution by overcoming the need for a central controller or additional signaling in the system. We model the session by self-interested players in a non-cooperative potential game. The utility function is designed such that increasing individual payoff results in a collective behavior achieving both a desirable system performance in a shared network environment and the Pareto optimal solution. We further show that our distributed solution achieves the centralized solution. Through extensive simulations, our approach is compared to the best performance that could be found in the conventional point-to-multipoint (PMP) recovery process. Numerical results show that our formulation largely outperforms the conventional PMP scheme in most practical situations and achieves a lower delay.

In this paper, we consider the problem of minimizing the maximum broadcast decoding delay experienced by all the receivers of generalized instantly decodable network coding (IDNC). Unlike the sum decoding delay, the maximum decoding delay as a definition of delay for IDNC allows a more equitable distribution of the delays between the different receivers and thus a better Quality of Service (QoS). In order to solve this problem, we first derive the expressions for the probability distributions of maximum decoding delay increments. Given these expressions, we formulate the problem as a maximum weight clique problem in the IDNC graph. Although this problem is known to be NP-hard, we design a greedy algorithm to perform effective packet selection. Through extensive simulations, we compare the sum decoding delay and the max decoding delay experienced when applying the policies to minimize the sum decoding delay and our policy to reduce the max decoding delay. Simulations results show that our policy gives a good agreement among all the delay aspects in all situations and outperforms the sum decoding delay policy to effectively minimize the sum decoding delay when the channel conditions become harsher. They also show that our definition of delay significantly improve the number of served receivers when they are subject to strict delay constraints.

In this paper, we study the multicast completion and decoding delay minimization problems for instantly decodable network coding (IDNC) in the case of lossy feedback. When feedback loss events occur, the sender falls into uncertainties about packet reception at the different receivers, which forces it to perform partially blind selections of packet combinations in subsequent transmissions. To determine efficient selection policies that reduce the completion and decoding delays of IDNC in such an environment, we first extend the perfect feedback formulation in our previous works to the lossy feedback environment, by incorporating the uncertainties resulting from unheard feedback events in these formulations. For the completion delay problem, we use this formulation to identify the maximum likelihood state of the network in events of unheard feedback and employ it to design a partially blind graph update extension to the multicast IDNC algorithm in our earlier work. For the decoding delay problem, we derive an expression for the expected decoding delay increment for any arbitrary transmission. This expression is then used to find the optimal policy that reduces the decoding delay in such lossy feedback environment. Results show that our proposed solutions both outperform previously proposed approaches and achieve tolerable degradation even at relatively high feedback loss rates.

In this paper, we study the effect of lossy intermittent feedback loss events on the multicast decoding delay performance of generalized instantly decodable network coding. These feedback loss events create uncertainty at the sender about the reception statues of different receivers and thus uncertainty to accurately determine subsequent instantly decodable coded packets. To solve this problem, we first identify the different possibilities of uncertain packets at the sender and their probabilities. We then derive the expression of the mean decoding delay. We formulate the Generalized Instantly Decodable Network Coding (G-IDNC) minimum decoding delay problem as a maximum weight clique problem. Since finding the optimal solution is NP-hard, we design a variant of the algorithm employed in [1]. Our algorithm is compared to the two blind graph update proposed in [2] through extensive simulations. Results show that our algorithm outperforms the blind approaches in all the situations and achieves a tolerable degradation, against the perfect feedback, for large feedback loss period.