Scheduling with pairwise XORing of packets under statistical overhearing information and feedback

We study the problem of scheduling packets from several flows traversing a given node which can mix packets belonging to different flows. Practical wireless network coding solutions depend on knowledge of overhearing events which is obtained either by acknowledgments or statistically. In the latter case, the knowledge about each packet improves progressively with feedback from the transmissions. We propose a virtual network mechanism in order to characterize the throughput region of such a system for the case where we allow only pairwise XORing. We also provide the policy which achieves the stability region and compare it to simple heuristics. The derived policy is a modification of the standard backpressure policy, designed to take into account the fact that in the proposed virtual network the destination of a transmitted packet is known only probabilistically. We demonstrate simulation results according to which scheduling with statistical information can provide significant throughput benefits even for overhearing probabilities as small as 0.6.