Binary Countdown for Quality of Service in Ad Hoc and Sensor Networks

The holy grail for medium access control is freedom from collision, while the holy grail for prioritization is absolute differentiation, where higher-priority packets can be transmitted without being affected by lower-priority packets. Fairness can then be provisioned among packets of the same traffic category, and lower-priority traffic categories may be allowed some bandwidth to avoid starvation. However, even though absolute differentiation may be realized in wired networks or single-hop wireless networks without difficulties, it is a problem that has never been solved in distributed multihop wireless networks, including ad hoc, mesh, and sensor networks. In this paper, we present a technique called "detached binary countdown", where the well-know binary countdown mechanism is applied before data packet transmission/reception, but with a gap between them. Different traffic categories have different ranges for their gaps, but contrary to intuition, the secret is to allow higher-priority traffic categories to use larger durations for their gap, granting them the privilege to reserve the channel earlier. As shown through a mathematical proof, absolute differentiation can be achieved by the technique. The technique is of significant theoretical importance in that it is the very first solution reported in the literature thus far that can achieve absolute differentiation in distributed multihop wireless networks with variable packet lengths. Detached binary countdown also leads to freedom from collision, and the hidden and exposed terminal problems naturally do not exist.