Linear network coding capacity region of the smart repeater with broadcast erasure channels
Jaemin Han, Chih-Chun Wang · 2016
This work considers the smart repeater network where a single source s wants to send two independent packet streams to destinations {d1, d2} with the help of relay r. The transmission from s or r is modeled by packet erasure channels: For each time slot, a packet transmitted by s may be received, with some probabilities, by a random subset of {d1, d2, r}; and those transmitted by r will be received by a random subset of {d1, d2}. Interference is avoided by allowing at most one of {s, r} to transmit in each time slot. One example of this model is any cellular network that supports two cell-edge users when a relay in the middle uses the same downlink resources for throughput/safety enhancement. In this setting, we study the capacity region of (R1, R2) when allowing linear network coding (LNC). The proposed LNC inner bound introduces more advanced packing-mixing operations other than the previously well-known butterfly-style XOR operation on overheard packets of two co-existing flows. A new LNC outer bound is derived by exploring the inherent algebraic structure of the LNC problem. Numerical results show that, with more than 85% of the experiments, the relative sum-rate gap between the proposed outer and inner bounds is smaller than 0.08%, thus effectively bracketing the LNC capacity of the smart repeater problem.