TY - GEN

T1 - On minimizing the maximum broadcast decoding delay for instantly decodable network coding

AU - Douik, Ahmed S.

AU - Sorour, Sameh

AU - Alouini, Mohamed-Slim

AU - Al-Naffouri, Tareq Y.

N1 - KAUST Repository Item: Exported on 2020-10-01

PY - 2014/9

Y1 - 2014/9

N2 - In this paper, we consider the problem of minimizing the maximum broadcast decoding delay experienced by all the receivers of generalized instantly decodable network coding (IDNC). Unlike the sum decoding delay, the maximum decoding delay as a definition of delay for IDNC allows a more equitable distribution of the delays between the different receivers and thus a better Quality of Service (QoS). In order to solve this problem, we first derive the expressions for the probability distributions of maximum decoding delay increments. Given these expressions, we formulate the problem as a maximum weight clique problem in the IDNC graph. Although this problem is known to be NP-hard, we design a greedy algorithm to perform effective packet selection. Through extensive simulations, we compare the sum decoding delay and the max decoding delay experienced when applying the policies to minimize the sum decoding delay and our policy to reduce the max decoding delay. Simulations results show that our policy gives a good agreement among all the delay aspects in all situations and outperforms the sum decoding delay policy to effectively minimize the sum decoding delay when the channel conditions become harsher. They also show that our definition of delay significantly improve the number of served receivers when they are subject to strict delay constraints.

AB - In this paper, we consider the problem of minimizing the maximum broadcast decoding delay experienced by all the receivers of generalized instantly decodable network coding (IDNC). Unlike the sum decoding delay, the maximum decoding delay as a definition of delay for IDNC allows a more equitable distribution of the delays between the different receivers and thus a better Quality of Service (QoS). In order to solve this problem, we first derive the expressions for the probability distributions of maximum decoding delay increments. Given these expressions, we formulate the problem as a maximum weight clique problem in the IDNC graph. Although this problem is known to be NP-hard, we design a greedy algorithm to perform effective packet selection. Through extensive simulations, we compare the sum decoding delay and the max decoding delay experienced when applying the policies to minimize the sum decoding delay and our policy to reduce the max decoding delay. Simulations results show that our policy gives a good agreement among all the delay aspects in all situations and outperforms the sum decoding delay policy to effectively minimize the sum decoding delay when the channel conditions become harsher. They also show that our definition of delay significantly improve the number of served receivers when they are subject to strict delay constraints.

UR - http://hdl.handle.net/10754/564978

UR - http://arxiv.org/abs/arXiv:1404.0265v1

UR - http://www.scopus.com/inward/record.url?scp=84919430150&partnerID=8YFLogxK

U2 - 10.1109/VTCFall.2014.6966079

DO - 10.1109/VTCFall.2014.6966079

M3 - Conference contribution

SN - 9781479944491; 9781479944491

BT - 2014 IEEE 80th Vehicular Technology Conference (VTC2014-Fall)

PB - Institute of Electrical and Electronics Engineers (IEEE)

ER -