Cross-Sender Bit-Mixing Coding
share
Scheduling to avoid packet collisions is a long-standing challenge in networking, and has become even trickier in wireless networks with multiple senders and multiple receivers. In fact, researchers have proved that even perfect scheduling can only achieve R = O(1/ N). Here N is the number of nodes in the network, while R is the medium utilization rate. In this work, our vision is to achieve R = Θ(1), and avoid all the complexities in scheduling. To this end, this paper proposes cross-sender bit-mixing coding (or BMC in short), which does not rely on scheduling. Instead, users transmit simultaneously on suitably-chosen slots, and the amount of overlap in different user's slots is controlled via coding. We prove that in all possible network topologies, using BMC enables us to achieve R=Θ(1). We also prove that the space and time complexities of BMC encoding/decoding are all low-order polynomials.
READ FULL TEXT