Optimal channel utilization with limited feedback

摘要

A channel with multiplicity feedback in case of collision returns the exact number of stations simultaneously transmitting. In this model, Θ((dlog⁡(n/d))/log⁡d) time rounds are sufficient and necessary to identify d transmitting stations out of n. In contrast, in the ternary feedback model the time complexity is Θ(dlog⁡(n/d)). Generalizing, we can define a feedback interval [x,y], where 0≤x≤y≤d, such that the channel returns the exact number of transmitting stations only if this number is within that interval. For a feedback interval centered in d/2 we show that it is possible to get the same optimal time complexity for the channel with multiplicity feedback even if the interval has only size O(dlog⁡d). On the other hand, if we further reduce the size to O(dlog⁡d), then we show that no protocol having time complexity Θ((dlog⁡(n/d))/(log⁡d)) is possible.