This paper considers the downlink traffic from a base station to two different clients. When assuming infinite backlog, it is known that inter-session network coding (INC) can significantly increase the throughput. However, the corresponding scheduling solution (when assuming dynamic arrivals instead and requiring bounded delay) is still nascent. For the two-flow downlink scenario, we propose the first opportunistic INC + scheduling solution that is provably optimal for time-varying channels, i.e., the corresponding stability region matches the optimal Shannon capacity. In particular, we first introduce a new binary INC operation, which is distinctly different from the traditional wisdom of XORing two overheard packets. We then develop a queue-length-based scheduling scheme and prove that it, with the help of the new INC operation, achieves the optimal stability region with time-varying channel quality. The proposed algorithm is later generalized to include the capability of rate adaptation. Simulation results show that it again achieves the optimal throughput with rate adaptation. A byproduct of our results is a scheduling scheme for stochastic processing networks with random departure, which relaxes the assumption of deterministic departure in the existing results.

This paper considers the downlink traffic from a base station to two different clients. Assuming infinite backlog, it is known that inter-session network coding (INC) can significantly increase the throughput of each flow. However, the corresponding scheduling solution (assuming dynamic arrivals and requiring bounded delay) is still nascent. For the 2-flow downlink scenario, we propose the first opportunistic INC + scheduling solution that is provably optimal for time-varying channels, i.e., the corresponding stability region matches the optimal linear-INC capacity. To that end, we first introduce a new binary INC operation, which is distinctly different from the traditional wisdom of XORing two overheard packets. We then develop a queue-length-based scheduling scheme, which, with the help of the new INC operation, can robustly and optimally adapt to time-varying channel quality. A byproduct of our results is a scheduling scheme for stochastic processing networks (SPNs) with random departure. The new SPN results relax the previous assumption of deterministic departure, a major limitation of the existing SPN model, by considering stochastic packet departure behavior, and could further broaden the applications of SPN scheduling to other real-world scenarios.

This paper characterizes the full capacity region of the COPE principle for 2-flow wireless butterfly networks with broadcast packet erasure channels (PECs). The capacity results in this paper allow for random overhearing with arbitrary overhearing probabilities, arbitrary scheduling policies, network-wide channel state information (CSI) feedback after each transmission, and potential use of nonlinear network codes. An information-theoretic outer bound is derived that takes into account the delayed CSI feedback of the underlying broadcast packet erasure channels. For the achievability, this paper proposes a new class of linear network codes, named as the space-based linear network coding (SBLNC), that achieves the capacity outer bound. Further, the proposed outer and inner bounds are later generalized for the setting in which a transmission may be heard by its 2-hop neighbor(s), the so-called opportunistic routing scenario. When allowing the possibility of opportunistic routing, the proposed inner and outer bounds do not always meet. Numerical experiments, however, show that the relative gap of the two bounds is less than 0.08% in average. The proposed bounds thus tightly bracket the capacity region even when combining the COPE principle with opportunistic routing.

This work studies the capacity of 2-user 1-hop relay networks, for which the sources, destinations, and the common relay are interconnected by broadcast packet erasure channels. In contrast with the existing results, this paper allows (i) transmission from a source being heard directly by its 2-hop-away destination, the so-called opportunistic routing scenario, (ii) instant channel status feedback among all network nodes, and (iii) per-slot scheduling decisions that are functions of the traffic loads and the past channel status. A new pair of inner and outer bounds is provided, and a condition is identified for the scenario in which the bounds coincide. Numerical experiments show that for commonly encountered scenarios, the gap between the inner and the outer bounds is less than 0.2%, which demonstrates the effectiveness of the proposed bounding techniques.