TY - JOUR
T1 - Opportunities for Network Coding
T2 - To Wait or Not to Wait
AU - Hsu, Yu Pin
AU - Abedini, Navid
AU - Gautam, Natarajan
AU - Sprintson, Alex
AU - Shakkottai, Srinivas
N1 - Funding Information:
This material is based upon work supported in part by the NSF under Grants CNS-0954153, CNS-0963818, CNS-0904520, and CNS-1149458, the AFOSR under Contract No. FA9550-13-1-0008, and the DTRA under Grant HDTRA1-13-1-0030. An earlier version of this paper was presented at the IEEE International Symposium on Information Theory (ISIT), St. Petersburg, Russia, July 31-August 5, 2011. The authors are grateful to D. B. H. Cline, V. Borkar, and R. Sundaresan for the useful discussions.
Publisher Copyright:
© 2014 IEEE.
PY - 2015/12
Y1 - 2015/12
N2 - 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.
AB - 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.
KW - Delay-aware scheduling
KW - Markov decision process
KW - optimal control
KW - wireless network coding
UR - http://www.scopus.com/inward/record.url?scp=84961926914&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84961926914&partnerID=8YFLogxK
U2 - 10.1109/TNET.2014.2347339
DO - 10.1109/TNET.2014.2347339
M3 - Article
AN - SCOPUS:84961926914
VL - 23
SP - 1876
EP - 1889
JO - IEEE/ACM Transactions on Networking
JF - IEEE/ACM Transactions on Networking
SN - 1063-6692
IS - 6
M1 - 6895314
ER -