  It has been well established that wireless network coding can significantly
improve the efficiency of multi-hop 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. The paper
addresses this problem by formulating a stochastic dynamic program whose
objective is to minimize the long-run average cost per unit time incurred due
to transmissions and delays. In particular, we identify optimal control actions
that would balance between costs of transmission against the costs incurred due
to the delays. Moreover, we seek to address a crucial question: what should be
observed as the state of the system? We analytically show that observing queue
lengths suffices if the system can be modeled as a Markov decision process. We
also show that a stationary threshold type policy based on queue lengths is
optimal. We further substantiate our results with simulation experiments for
more generalized settings.
