  Distributed opportunistic scheduling (DOS) is studied for wireless ad-hoc
networks in which many links contend for the channel using random access before
data transmissions. Simply put, DOS involves a process of joint channel probing
and distributed scheduling for ad-hoc (peer-to-peer) communications. Since, in
practice, link conditions are estimated with noisy observations, the
transmission rate has to be backed off from the estimated rate to avoid
transmission outages. Then, a natural question to ask is whether it is
worthwhile for the link with successful contention to perform further channel
probing to mitigate estimation errors, at the cost of additional probing. Thus
motivated, this work investigates DOS with two-level channel probing by
optimizing the tradeoff between the throughput gain from more accurate rate
estimation and the resulting additional delay. Capitalizing on optimal stopping
theory with incomplete information, we show that the optimal scheduling policy
is threshold-based and is characterized by either one or two thresholds,
depending on network settings. Necessary and sufficient conditions for both
cases are rigorously established. In particular, our analysis reveals that
performing second-level channel probing is optimal when the first-level
estimated channel condition falls in between the two thresholds. Numerical
results are provided to illustrate the effectiveness of the proposed DOS with
two-level channel probing. We also extend our study to the case with limited
feedback, where the feedback from the receiver to its transmitter takes the
form of (0,1,e).
