Network coding decisions for wireless transmissions with delay consideration

Arupa Mohapatra, Natarajan Gautam, Srinivas Shakkottai, Alex Sprintson

Research output: Contribution to journalArticlepeer-review

17 Scopus citations


We consider a relay node that stochastically receives packets from two opposing flows. Whenever opportunities exist, the relay performs network coding to efficiently transmit packets. However, on one hand, because of the stochastic nature, as well as possible asymmetry between the opposing flows, it would not be possible to always code packets. On the other hand, waiting for a coding opportunity could result in excessive latency, and one may be better off transmitting packets without coding. Thus, one needs to decide at each transmission opportunity whether to transmit a packet uncoded or wait for a future transmission opportunity. To enable us to optimally make that decision, we consider costs for transmission and delay, and formulate our problem as a Markov decision process. We show that the optimal policy is threshold type under a sufficient condition, and we compute it by modeling the resulting system as a Markov chain. Through numerical analysis, we show the effectiveness of the threshold policy in the relay node network, as well as in a line network scenario. Further, we compare the threshold policy against a number of simple heuristic policies and identify situations where these policies can be effective.

Original languageEnglish (US)
Article number684768
Pages (from-to)2965-2976
Number of pages12
JournalIEEE Transactions on Communications
Issue number8
StatePublished - Aug 2014
Externally publishedYes


  • Markov decision processes
  • Network coding
  • energy-delay trade-off

ASJC Scopus subject areas

  • Electrical and Electronic Engineering


Dive into the research topics of 'Network coding decisions for wireless transmissions with delay consideration'. Together they form a unique fingerprint.

Cite this