Stability of the Max-Weight Protocol in Adversarial Wireless Networks

ABSTRACT In this paper we consider the Max-Weight protocol for routing and scheduling in wireless networks under an ad- versarial model. This protocol has received a signicant amount of attention dating back to the papers of Tassiulas and Ephremides. In particular, this protocol is known to be throughput-optimal (i.e. stable) whenever the traffic patterns and propagation conditions are governed by a sta- tionary 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 propagation conditions can be governed by an arbitrary adversarial process. We believe that such an environment is worthy of study since in many practical wireless scenarios the assumption that channel conditions are governed by a stationary stochastic process does not readily apply. In this paper we prove that even in an adversarial setting, the Max-Weight protocol remains stable. However, the proof is somewhat more complex than the negative potential drift argument that applied in the stationary case. Unlike the paper [1] (in which each edge could be scheduled independently) our proof holds even when there are arbitrary interference relationships among edges. We also prove the stability of "-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.