A New Kind of Selectors and Their Applications to Conflict Resolution in Wireless Multichannels Networks

摘要

We investigate the benefits of using multiple channels of communications in wireless networks, under the full-duplex multi-packet reception model of communication. The main question we address is the following: Is a speedup linear in the number of channels achievable, for some interesting communication primitive? We provide a positive answer to this interrogative for the Information Exchange Problem, in which k arbitrary nodes have information they intend to share with the entire network. To achieve this goal, we devise and exploit a combinatorial structure that generalizes well known combinatorial tools widely used in the area of data-exchange in multiple access channels (i.e., strongly selective families, selectors, and related mathematical objects). For our new combinatorial structures we provide both existential results, based on the Lovasz Local Lemma, and efficient constructions, leveraging on properties of error correcting codes. We also prove non existential results, showing that our constructions are not too far from being optimal.