In this paper, we introduce a game theoretic frame- work for studying the problem of minimizing the delay 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 functions are designed such that increasing individual payoff results in a collective behavior achieving both a desirable system performance in a shared network environment and the Nash bargaining solution. Three games are developed: the first aims to reduce the completion time, the second to reduce the maximum decoding delay and the third the sum decoding delay. We improve these formulations to include punishment policy upon collision occurrence and achieve the Nash bargaining solution. Through extensive simulations, our framework is tested against the best performance that could be found in the conventional point- to-multipoint (PMP) recovery process in numerous cases: first we simulate the problem with complete information. We, then, simulate with incomplete information and finally we test it in lossy feedback scenario. Numerical results show that our formulation with complete information largely outperforms the conventional PMP scheme in most situations and achieves a lower delay. They also show that the completion time formulation with incomplete information also outperforms the conventional PMP. Index Terms—Cooperative data exchange, instantly decodable network coding, non-cooperative games, potential game, Nash equilibrium.
The aforementioned work considered a perfect and prompt feedback from all the players. This assumption is too idealistic given the impairments on feedback link @cite_18 of wireless networks, due to shadowing, high interference and fading. In this situation, players will need to transmit several subsequent packets without having any information (or partial information) about their reception status at the other players. Moreover, this scenario introduce a new dimension to the problem since the information at the different players is no longer common knowledge. When IDNC based CDE is used in such uncertainties and non symmetric information, the players will no longer be certain on the outcome of their actions, and thus will not be certain about the resulting completion time and decoding delays.
@cite_18
2950479988 1975409994 1594194634 1485005937
Consider a scenario of broadcasting a common content to a group of cooperating wireless nodes that are within proximity of each other. Nodes in this group may receive partial content from the source due to packet losses over wireless broadcast links. We further consider that packet losses are different for different nodes. The remaining missing content at each node can then be recovered, thanks to cooperation among the nodes. In this context, the minimum amount of time that can guarantee a complete acquisition of the common content at every node is referred to as the completion time. It has been shown that instantly decodable network coding (IDNC) reduces the completion time as compared to no network coding in this scenario. Yet, for applications such as video streaming, not all packets have the same importance and not all users are interested in the same quality of content. This problem is even more interesting when additional, but realistic constraints, such as strict deadline, bandwidth, or limited energy are added to the problem formulation. We assert that direct application of IDNC in such a scenario yields poor performance in terms of content quality and completion time. In this paper, we propose a novel Content-Aware IDNC scheme that improves content quality and network coding opportunities jointly by taking into account significance of each packet towards the desired quality of service (QoS). Our proposed Content-Aware IDNC maximizes the quality under the completion time constraint, and minimizes the completion time under the quality constraint.We demonstrate the benefits of Content-Aware IDNC through simulations. In this paper, we consider the problem of minimizing the completion delay for instantly decodable network coding (IDNC) in wireless multicast and broadcast scenarios. We are interested in this class of network coding due to its numerous benefits, such as low decoding delay, low coding and decoding complexities, and simple receiver requirements. We first extend the IDNC graph, which represents all feasible IDNC coding opportunities, to efficiently operate in both multicast and broadcast scenarios. We then formulate the minimum completion delay problem for IDNC as a stochastic shortest path (SSP) problem. Although finding the optimal policy using SSP is intractable, we use this formulation to draw the theoretical guidelines for the policies that can minimize the completion delay in IDNC. Based on these guidelines, we design a maximum weight clique selection algorithm, which can efficiently reduce the IDNC completion delay in polynomial time. We also design a quadratic-time heuristic clique selection algorithm, which can operate in real-time applications. Simulation results show that our proposed algorithms significantly reduce the IDNC completion delay compared to the random and maximum-rate algorithms, and almost achieve the global optimal completion delay performance over all network codes in broadcast scenarios. This paper considers the problem of reducing the broadcast delay of wireless networks using instantly decodable network coding (IDNC) based device-to-device (D2D) communications. In D2D-enabled networks, devices help hasten the recovery of the lost packets of devices in their transmission range by sending network coded packets. To solve the problem, the different events occurring at each device are identified so as to derive an expression for the probability distribution of the decoding delay. The joint optimization problem over the set of transmitting devices and the packet combinations of each is formulated. Due to the high complexity of finding the optimal solution, this paper focuses on cooperation without interference between the transmitting users. The optimal solution, in such interference-less scenario, is expressed using a graph theory approach by introducing the cooperation graph. Extensive simulations compare the decoding delay experienced in the Point to Multi-Point (PMP), the fully connected D2D (FC-D2D) and the more practical partially connected D2D (PC-D2D) configurations and suggest that the PC-D2D outperforms the FC-D2D in all situations and provides an enormous gain for poorly connected networks. In this paper, we consider the problem of min- imizing the multicast decoding delay of generalized instantly decodable network coding (G-IDNC) over persistent forward and feedback erasure channels with feedback intermittence. In such an environment, the sender does not always receive acknowledgement from the receivers after each transmission. Moreover, both the forward and feedback channels are subject to persistent erasures, which can be modelled by a two state (good and bad states) Markov chain known as Gilbert-Elliott channel (GEC). Due to such feedback imperfections, the sender is unable to determine subsequent instantly decodable packets combination for all receivers. Given this harsh channel and feedback model, we first derive expressions for the probability distributions of decoding delay increments and then employ these expressions in formulating the minimum decoding problem in such environment as a maximum weight clique problem in the G-IDNC graph. We also show that the problem formulations in simpler channel and feedback models are special cases of our generalized formulation. Since this problem is NP-hard, we design a greedy algorithm to solve it and compare it to blind approaches proposed in literature. Through extensive simulations, our adaptive algorithm is shown to outperform the blind approaches in all situations and to achieve significant improvement in the decoding delay, especially when the channel is highly persistent. Index Terms—Multicast Channels, Persistent Erasure Chan- nels, G-IDNC, Decoding Delay, Lossy Intermittent Feedback, Maximum Weight Clique Problem.