Threshold structure of channel aware distributed scheduling in ad-hoc networks: An optimal stopping view

As evidenced by measurement data, channel fading and co-channel interference occur on the same time scales, and it is therefore difficult to determine if packet losses are due to interference change or channel variation. The coupling between the timescales of fading and interference at the MAC layer calls for a unified PHY/MAC design. Using optimal stopping theory, we first devise channel aware distributed scheduling to exploit rich PHY/MAC diversities in single-hop ad-hoc networks, for a variety of PHY-layer models. We show that the optimal channel aware distributed scheduling algorithms have threshold structures, and hence are amenable to easy implementation. We then generalize the study to multi-hop wireless networks, and discuss further open issues such as the delay performance of distributed scheduling.