2011/05/20 by Yu-Pin Hsu, Hsu, Yu-Pin, Navid Abedini +7
Computer Science · Mathematics · #FOS: Computer and information sciences #FOS: Mathematics #Information Theory (cs.IT) #Networking and Internet Architecture (cs.NI) #Optimization and Control (math.OC) #cs.IT #cs.NI #math.IT #math.OC
paper · pdf · doi:10.48550/arxiv.1105.4143
14 pages, journal version of arXiv:1105.4143v1, submitted to IEEE/ACM Transaction on Networking
arxiv created 2013/07/24 · arxiv updated 2015/03/19
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.