Cross-Sender Bit-Mixing Coding

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/ln N). Here N is the number of nodes in the network, and R is the medium utilization rate. Ideally, one would hope to achieve R = Theta(1), while avoiding all the complexities in scheduling. To this end, this paper proposes cross-sender bit-mixing coding (BMC), 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 = Theta(1). We also prove that the space and time complexities of BMC encoding/decoding are all low-order polynomials.