Coding-Based Data Broadcasting for Time-Critical Applications With Rate Adaptation

In this paper, we dynamically select the transmission rate and design wireless network coding to improve the quality of services, such as delay for time-critical applications. In a network coded system, with a low transmission rate and, hence, a longer transmission range, more packets may be encoded, which increases the coding opportunity. However, a low transmission rate may incur extra transmission delay, which is intolerable for time-critical applications. We design a novel joint rate selection and wireless network coding (RSNC) scheme with a delay constraint to maximize the total benefit (where we can define the benefit based on the priority or importance of a packet for example) of the packets that are successfully received at the destinations without missing their deadlines. We prove that the proposed problem is NP-hard and propose a novel graph model to mathematically formulate the problem. For the general case, we propose a transmission metric and design an efficient algorithm to determine the transmission rate and coding strategy for each transmission. For a special case when all delay constraints are the same, we study pairwise coding and present a polynomial-time pairwise coding algorithm that achieves an approximation ratio of 1 - (1/e) to the optimal pairwise coding solution, where e is the base of the natural logarithm. Finally, simulation results demonstrate the superiority of the proposed RSNC scheme.