Optimal Channel Utilization with Limited Feedback

摘要

A channel with multiplicity feedback is a shared channel that in case of collision (two or more stations transmitting simultaneously) returns as a feedback the exact number of stations simultaneously transmitting. It is known that in such a model Ө((d log(n/d))/log d) time rounds are sufficient and necessary to identify the IDs of d transmitting stations, from an ensemble of n. In contrast, the model with collision detection (or ternary feedback) allows only a limited feedback from the channel: 0 (silence), 1 (success) or 2+ (collision). In this case it is known that Ω(d log(n/d)) time rounds are necessary. 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. The collision detection model corresponds to x = 0 and y = 1, while the multiplicity feedback is obtained for x = 0 and y = d. It is natural to ask for which size of the feedback intervals we can still get the same optimal time complexity Ө((d log(n/d))/(log d)) valid for the channel with multiplicity feedback. In this paper we show that we can still use this number of time rounds even when the interval has a substantially smaller size: namely O((d log b)~(1/2)). On the other hand, we also prove that if we further reduce the size of the interval to O((d~(1/2))/log d) , then no protocol having time complexity Ө((d log(n/d))/(log d)) is possible.