Opportunities for Network Coding: To Wait or Not to Wait

Yu Pin Hsu, Navid Abedini, Natarajan Gautam, Alex Sprintson, Srinivas Shakkottai

Research output: Contribution to journalArticlepeer-review

14 Scopus citations


It has been well established that wireless network coding can significantly improve the efficiency of multihop wireless networks. However, in a stochastic environment, some of the packets might not have coding pairs, which limits the number of available coding opportunities. In this context, an important decision is whether to delay packet transmission in hope that a coding pair will be available in the future or transmit a packet without coding. This paper addresses this problem by establishing a stochastic dynamic framework whose objective is to minimize a long-run average cost. We identify an optimal control policy that minimizes the costs due to a combination of transmissions and packet delays. We show that the optimal policy would be stationary, deterministic, and threshold-type based on queue lengths. Our analytical approach is applicable for many cases of interest such as time-varying on/off channels. We further substantiate our results with simulation experiments for more generalized settings.

Original languageEnglish (US)
Article number6895314
Pages (from-to)1876-1889
Number of pages14
JournalIEEE/ACM Transactions on Networking
Issue number6
StatePublished - Dec 2015
Externally publishedYes


  • Delay-aware scheduling
  • Markov decision process
  • optimal control
  • wireless network coding

ASJC Scopus subject areas

  • Software
  • Computer Science Applications
  • Computer Networks and Communications
  • Electrical and Electronic Engineering


Dive into the research topics of 'Opportunities for Network Coding: To Wait or Not to Wait'. Together they form a unique fingerprint.

Cite this