  In this paper we consider the Max-Weight protocol for routing and scheduling
in wireless networks under an adversarial model. This protocol has received a
significant amount of attention dating back to the papers of Tassiulas and
Ephremides. In particular, this protocol is known to be throughput-optimal
whenever the traffic patterns and propagation conditions are governed by a
stationary stochastic process.
  However, the standard proof of throughput optimality (which is based on the
negative drift of a quadratic potential function) does not hold when the
traffic patterns and the edge capacity changes over time are governed by an
arbitrary adversarial process. Such an environment appears frequently in many
practical wireless scenarios when the assumption that channel conditions are
governed by a stationary stochastic process does not readily apply.
  In this paper we prove that even in the above adversarial setting, the
Max-Weight protocol keeps the queues in the network stable (i.e. keeps the
queue sizes bounded) whenever this is feasible by some routing and scheduling
algorithm. However, the proof is somewhat more complex than the negative
potential drift argument that applied in the stationary case. Our proof holds
for any arbitrary interference relationships among edges. We also prove the
stability of $\ep$-approximate Max-Weight under the adversarial model. We
conclude the paper with a discussion of queue sizes in the adversarial model as
well as a set of simulation results.
