  In this article we introduce a new model to study stability in multi-hop
wireless networks in the framework of adversarial queueing. In such a model, a
routing protocol consists of three components: a transmission policy, a
scheduling policy to select the packet to transmit form a set of packets parked
at a node, and a hearing control mechanism to coordinate transmissions with
scheduling. For such a setting, we propose a definition of universal stability
that takes into account not only the scheduling policies (as in the standard
wireline adversarial model), but also the transmission policies. First, we show
that any scheduling policy that is unstable in the classical wireline
adversarial model remains unstable in the multi-hop radio network model, even
in scenarios free of inter- ferences. Then, we show that both SIS and LIS (two
well-known universally stable scheduling policies in the wireline adversarial
model) remain stable in the multi-hop radio network model, provided a proactive
hearing control is used. In contrast, such scheduling policies turn out to be
unstable when using a reactive hearing control. However, the scheduling policy
LIS can be enforced to be universally stable provided ties are resolved in a
permanent manner. Such a situation doesn't hold in the case of SIS, which
remains unstable regardless of how ties are resolved. Furthermore, for some
transmission policies which we call regular, we also show that all scheduling
policies that are universally stable when using proactive hearing control
(which include SIS and LIS) remain universally stable when using reactive
hearing control.
