Cross-Sender Bit-Mixing Coding
Journal article
Accepted version
Åpne
Permanent lenke
https://hdl.handle.net/11250/2649623Utgivelsesdato
2019Metadata
Vis full innførselSamlinger
Originalversjon
https://doi.org/10.1145/3302506.3310401Sammendrag
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/lnN). Here N is the number of nodes in the network, and R is the medium utilization rate.
Ideally, one would hope to achieve R = Θ(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 = Θ(1). We also prove that the space and time complexities of BMC encoding/decoding are all low-order polynomials