  We consider a system of several collocated nodes sharing a time slotted
wireless channel, and seek a MAC (medium access control) that (i) provides low
mean delay, (ii) has distributed control (i.e., there is no central scheduler),
and (iii) does not require explicit exchange of state information or control
signals. The design of such MAC protocols must keep in mind the need for
contention access at light traffic, and scheduled access in heavy traffic,
leading to the long-standing interest in hybrid, adaptive MACs.
  Working in the discrete time setting, for the distributed MAC design, we
consider a practical information structure where each node has local
information and some common information obtained from overhearing. In this
setting, "ZMAC" is an existing protocol that is hybrid and adaptive. We
approach the problem via two steps (1) We show that it is sufficient for the
policy to be "greedy" and "exhaustive". Limiting the policy to this class
reduces the problem to obtaining a queue switching policy at queue emptiness
instants. (2) Formulating the delay optimal scheduling as a POMDP (partially
observed Markov decision process), we show that the optimal switching rule is
Stochastic Largest Queue (SLQ).
  Using this theory as the basis, we then develop a practical distributed
scheduler, QZMAC, which is also tunable. We implement QZMAC on standard
off-the-shelf TelosB motes and also use simulations to compare QZMAC with the
full-knowledge centralized scheduler, and with ZMAC. We use our implementation
to study the impact of false detection while overhearing the common
information, and the efficiency of QZMAC. Our simulation results show that the
mean delay with QZMAC is close that of the full-knowledge centralized
scheduler.
